Challenges with named types and shared generics

[AndyAyersMS]

We're starting to see cases now where we have types that are structurally equivalent but not name equivalent. This happens when we have shared generics. This leads to typing violations in LLVM IR, since LLVM uses name equivalence if you give types names. We've gotten away with it for a while because with generic ref classes we could cast our way out of trouble (though Eugene has an example where even this fails). But for value classes we can't fix things easily by casting.

One example is from TinyCsc.Main in Roslyn, here we have:

.locals 
   ....
           valuetype [System.Collections.Immutable]System.Collections.Immutable.ImmutableArray`1/Enumerator<class [Microsoft.CodeAnalysis]Microsoft.CodeAnalysis.Diagnostic> V_16,
   ....
    IL_018e:  call       instance valuetype [System.Collections.Immutable]System.Collections.Immutable.ImmutableArray`1/Enumerator<!0> valuetype [System.Collections.Immutable]System.Collections.Immutable.ImmutableArray`1<class [Microsoft.CodeAnalysis]Microsoft.CodeAnalysis.Diagnostic>::GetEnumerator()
    IL_0193:  stloc.s    V_16

At the stloc we have type

%"System.Collections.Immutable.ImmutableArray`1+Enumerator[System.__Canon]" = type <{ %"System.__Canon[]" addrspace(1)*, i32, [4 x i8] }>

on the stack, and type

%"System.Collections.Immutable.ImmutableArray`1+Enumerator[Microsoft.CodeAnalysis.Diagnostic]" = type <{ %"System.__Canon[]" addrspace(1)*, i32, [4 x i8] }>

for the local.

Since these are structs, we can't just cast from one type to the other.

Either we need to canonicalize the names somehow (which seems tricky since we don't know offhand when the EE will decide to share) or we need to give up on having the names there in the first place. Or maybe some other clever fix.

[JosephTremoulet]

This may not be pretty, but for stloc in particular, couldn't we pointer-cast the address of the local to give the referent type the other name? Continuing that idea, don't most operations on structs involve a pointer that we could force the cast on? Struct arguments/returns are the only counterexample that immediately comes to mind, but in those cases I'd think we could always dummy up a function type using the other name and pointer-cast the function pointer...

[AndyAyersMS]

How about a struct PHI? I think we'd be stuck there. Say the example above but where we call on one side and ldloc on the other. At the join we ...?

Pat notes that if we carry out the program to keep aggregates in memory then pointer casts do the trick. I hate the idea that giving types useful names and the IR representation for value types gets coupled, but if we're going down that road anyways....

[JosephTremoulet]

At the join I suppose we could go back and rewrite either the call or the ldloc (and then have some horrible code to update any other uses of the retyped def, which would have to chase the web if some of those other uses are phis...)

I hate the idea that giving types useful names and the IR representation for value types gets coupled, but if we're going down that road anyways....

I agree with both parts of that.

One appeal of forcing this into pointer-casts is that the ugly code can be removed if the plans to remove referent types from LLVM IR come to fruition.

[xen2]

If I understood the problem right, I actually had the same issue on a similar project:

I was using LLVM first-class aggregates (FCA) with SSA in LLVM to represent value types on stack. PHI nodes were used for stack merges. It seems like the natural/clean thing to do.

I could make most of it work, however there was some issues/limitations:

• Phi node if types are different (same as your case)
• Layout Explicit/Sequential struct were implemented with i8[] to properly handle all cases like union, but of course it wasn't practical to fetch any element due to lack of GEP (seems it's not your case?)
• Due to ABI requirements, some platforms behave differently if passing by struct or with byval/sret and you have to select the proper way to pass values (sometimes you even need to cast to i32 so that it is properly passed by register) -- difficult to do with first-class struct. More details: http://llvm.org/devmtg/2014-10/Slides/Skip%20the%20FFI.pdf and http://lists.cs.uiuc.edu/pipermail/llvmdev/2014-December/080150.html
• Clang transforms struct on the stack as alloca+pointer. Consequently, it's much more tested/optimized as a real-world scenario.
• Performance: I found some posts that were mentionning FCA not being well optimized in LLVM (could not find them right now, it was probably on LLVM mailing list). Probably related to major compiler (i.e. clang) not actually using them much.

Considering all that, I ended up replacing first-class aggregate struct on the stack with alloca and pointer. Not as beautiful, but at least PHI node were not a problem anymore (it happens on memory location instead of value, but I assume LLVM optimizes that well) and it became easy to work around ABI differences and control struct layout (i.e. fieldoffset) with GEP.

Maybe same approach can apply in your case?

[pgavlin]

@xen2 it's encouraging to know that you were successful with the Clang-style approach. Regarding some of the specific points above:

Layout Explicit/Sequential struct were implemented with i8[] to properly handle all cases like union, but of course it wasn't practical to fetch any element due to lack of GEP (seems it's not your case?)

Interesting. @AndyAyersMS @erozenfeld have we looked into any unsafe code that uses value types with overlapping fields yet?

Due to ABI requirements, some platforms behave differently if passing by struct or with byval/sret and you have to select the proper way to pass values

We have an approach to the ABI problem here and here that is working well so far with FCAs. I'd love to know if you have any feedback.

[xen2]

Layout Explicit/Sequential struct were implemented with i8[] to properly handle all cases like union, but of course it wasn't practical to fetch any element due to lack of GEP (seems it's not your case?)

Interesting. @AndyAyersMS @erozenfeld have we looked into any unsafe code that uses value types with overlapping fields yet?

Might not be phrased correctly. It wasn't possible to do GEP before the switch to alloca+pointer when using i8[]. As a result it was complicated to extract any field from it (i.e. many extractelement). After switching to alloca+pointer, it wasn't a problem anymore, I would just do a GEP + cast + load to get data from the offset I want and typed as I want (even struct inside larger struct, etc...).

I might have misunderstood, but from a very quick look at your code, it seems like you're not doing i8[], and that might be problematic to make general case work (i.e. a field that go from 0 to 50, and another at 12 that actually point to a subelement of it).

Note: the i8[] approach is something I was doing for both explicit and sequential layout (to control pack+size, size being sometimes big for fixed arrays types), but it is probably enough to do it only for explicit when there is actual overlap.

Due to ABI requirements, some platforms behave differently if passing by struct or with byval/sret and you have to select the proper way to pass values

We have an approach to the ABI problem here and here that is working well so far with FCAs. I'd love to know if you have any feedback.

Looks good!
In practice, does it means that FCA structs are copied back to alloca+pointer before dllimport call to properly be passed with byval* for some specific ABI? (that's what I had to do on some platforms to properly interop with C/C++) Also had to transform return value into sret as well (it was all depending on triplet and struct size).

[xen2]

Found back some details about optimizations concerns of FCA in LLVM (rust ran into it as well):

• Stop using first class aggregates rust-lang/rust#20450
• http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20141229/250758.html

As a side note, I don't know what Rust's ABI concerns are, but if at all
possible, I would suggest moving away from FCAs in the frontend as much as
possible. Everything I have seen in LLVM is that they obstruct optimization
in significant ways.

[AndyAyersMS]

We had some discussion of all this in the PR for the ABI changes (#394). Consensus is that we want to move away from FCA's. I though we had planned to have an issue open for this separate from how we represent types. If not I'll create one.

[pgavlin]

I wasn't sure that we had actually reached consensus on this. I agree that we should move away from FCAs in SSA. AFAICT there is no issue.

[pgavlin]

In practice, does it means that FCA structs are copied back to alloca+pointer before dllimport call to properly be passed with byval* for some specific ABI?

Yes, this is correct. Even if we were working with an alloca+pointer representation, however, something similar would be necessary, as we'd still need to make a copy of the argument before the call (unless we were able to use the byval attribtue, which isn't supported for all targets). Also, we do this for all calls, not just dllimport, since normal calls (mostly) follow the platform ABI.

[AndyAyersMS]

Ok, I will open an issue for FCAs. @xen2, as far as overlapping fields go, we bail out currently if we see these, but will be almost certainly putting in a suitably sized and located i8[] when we do support it. See #275.