wasm: support Generic Virtual Method Calls & Shared Generics (was: some linq methods fail to compile)

[yowl]

When attempting to build an Uno Platform project, it fails on a method

{[System.Linq]System.Linq.Enumerable+Iterator`1<Windows.UI.Xaml.Documents.Inline>.Select<string>(Func``2<Inline,string>)}

in the ctor for WebAssemblyVTableSlotNode on the assert

Debug.Assert(!targetMethod.HasInstantiation);

Not done any more investigation yet.

[MichalStrehovsky]

This is generic virtual method calls - similar to what was hit in CppCodegen mode here: #6147

The fix is more involved because it includes implementing shared generic code, but it will be probably pretty similar to the fix in CppCodegen: #6467. It's doable in a single pull request.

I've been meaning to write a doc on how shared generic code works. If you would like to work on this, I can sit down and write an overview doc (it might make the CppCodegen changes easier to parse).

[yowl]

Thanks, I'll update the title. I've a few other things to finish so will not look at it straight away. If no one else picks it up I'll have a go later, a few months probably.

[yowl]

This has become an itch that I have to scratch, so have started to look at the changes in #6467 and how they apply to wasm.

[yowl]

I'm enabling shared generics for wasm and have added a test copied from the main test suite, but before the compiler gets there, I'm hitting the assert at

corert/src/ILCompiler.Compiler/src/Compiler/DependencyAnalysis/GCStaticsNode.cs

Line 22 in 24f99b7

Debug.Assert(!type.IsCanonicalSubtype(CanonicalFormKind.Specific));

for the type {[S.P.CoreLib]System.Array`1+ArrayEnumerator<System.__Canon>}. What is a GCStaticsNode, why is it invalid for a subtype of a canonical type (if thats the right name), I had a look at the c++ implementation at

corert/src/ILCompiler.CppCodeGen/src/CppCodeGen/ILToCppImporter.cs

Lines 3661 to 3681 in 24f99b7

	private void AddFieldReference(FieldDesc field)
	{
	var owningType = field.OwningType;
	Debug.Assert(!owningType.IsRuntimeDeterminedSubtype);
	if (field.IsStatic)
	{
	var metadataType = owningType as MetadataType;
	Object node;
	if (field.IsThreadStatic)
	{
	node = _nodeFactory.TypeThreadStaticsSymbol(metadataType);
	}
	else
	{
	if (field.HasGCStaticBase)
	node = _nodeFactory.TypeGCStaticsSymbol(metadataType);
	else
	node = _nodeFactory.TypeNonGCStaticsSymbol(metadataType);

and it doesn't seem to do anything special to prevent hitting this assert as that conditional logic looks very similar to the wasm at

corert/src/ILCompiler.WebAssembly/src/CodeGen/ILToWebAssemblyImporter.cs

Lines 3283 to 3307 in 24f99b7

	if (field.IsThreadStatic)
	{
	// TODO: We need the right thread static per thread
	ExpressionEntry returnExp;
	node = TriggerCctorWithThreadStaticStorage(owningType, needsCctorCheck, out returnExp);
	staticBase = returnExp.ValueAsType(returnExp.Type, _builder);
	}
	else
	{
	if (field.HasGCStaticBase)
	{
	node = _compilation.NodeFactory.TypeGCStaticsSymbol(owningType);
	// We can't use GCStatics in the data section until we can successfully call
	// InitializeModules on startup, so stick with globals for now
	//LLVMValueRef basePtrPtr = LoadAddressOfSymbolNode(node);
	//staticBase = LLVM.BuildLoad(_builder, LLVM.BuildLoad(_builder, LLVM.BuildPointerCast(_builder, basePtrPtr, LLVM.PointerType(LLVM.PointerType(LLVM.PointerType(LLVM.Int8Type(), 0), 0), 0), "castBasePtrPtr"), "basePtr"), "base");
	staticBase = WebAssemblyObjectWriter.EmitGlobal(Module, field, _compilation.NameMangler);
	fieldOffset = 0;
	}
	else
	{
	node = _compilation.NodeFactory.TypeNonGCStaticsSymbol(owningType);
	staticBase = LoadAddressOfSymbolNode(node);
	}

Thanks

[yowl]

Ignore the cpp comparison I see where that differs now. I'm still not clear though on what a GCStaticNode is, sounds like a static object that can be GC collected, which I can see would happen for a ThreadStatic when the Thread is finished, but are there other uses? And why doesn't each subtype of the canonical type get its own GCStaticNode, I suppose that is what I dont understand. Maybe I don't really need to in order to move the same logic from cpp to wasm.

[MichalStrehovsky]

Wasm currently doesn't use the GCStatics node, but maybe it should start doing that (might be a candidate for a separate smaller pull request).

corert/src/ILCompiler.WebAssembly/src/CodeGen/ILToWebAssemblyImporter.cs

Lines 3296 to 3301 in bf9a1c9

	// We can't use GCStatics in the data section until we can successfully call
	// InitializeModules on startup, so stick with globals for now
	//LLVMValueRef basePtrPtr = LoadAddressOfSymbolNode(node);
	//staticBase = LLVM.BuildLoad(_builder, LLVM.BuildLoad(_builder, LLVM.BuildPointerCast(_builder, basePtrPtr, LLVM.PointerType(LLVM.PointerType(LLVM.PointerType(LLVM.Int8Type(), 0), 0), 0), "castBasePtrPtr"), "basePtr"), "base");
	staticBase = WebAssemblyObjectWriter.EmitGlobal(Module, field, _compilation.NameMangler);
	fieldOffset = 0;

The comment is referring to this code that I think we now run at startup in WASM:

corert/src/Common/src/Internal/Runtime/CompilerHelpers/StartupCodeHelpers.cs

Lines 270 to 299 in 635cf21

	private static unsafe void InitializeStatics(IntPtr gcStaticRegionStart, int length)
	{
	IntPtr gcStaticRegionEnd = (IntPtr)((byte*)gcStaticRegionStart + length);
	for (IntPtr* block = (IntPtr*)gcStaticRegionStart; block < (IntPtr*)gcStaticRegionEnd; block++)
	{
	// Gc Static regions can be shared by modules linked together during compilation. To ensure each
	// is initialized once, the static region pointer is stored with lowest bit set in the image.
	// The first time we initialize the static region its pointer is replaced with an object reference
	// whose lowest bit is no longer set.
	IntPtr* pBlock = (IntPtr*)*block;
	long blockAddr = (*pBlock).ToInt64();
	if ((blockAddr & GCStaticRegionConstants.Uninitialized) == GCStaticRegionConstants.Uninitialized)
	{
	object obj = RuntimeImports.RhNewObject(new EETypePtr(new IntPtr(blockAddr & ~GCStaticRegionConstants.Mask)));
	if ((blockAddr & GCStaticRegionConstants.HasPreInitializedData) == GCStaticRegionConstants.HasPreInitializedData)
	{
	// The next pointer is preinitialized data blob that contains preinitialized static GC fields,
	// which are pointer relocs to GC objects in frozen segment.
	// It actually has all GC fields including non-preinitialized fields and we simply copy over the
	// entire blob to this object, overwriting everything.
	IntPtr pPreInitDataAddr = *(pBlock + 1);
	RuntimeImports.RhBulkMoveWithWriteBarrier(ref obj.GetRawData(), ref *(byte *)pPreInitDataAddr, obj.GetRawDataSize());
	}
	*pBlock = RuntimeImports.RhHandleAlloc(obj, GCHandleType.Normal);
	}
	}
	}

GC statics (static fields for which HasGCStaticBase reports true) are allocated on the GC heap and are accessed differently from normal statics.

What the InitializeStatics method does is that it allocates a small object that holds data for all GC statics on the type. The compiler generates a fake EEType that has just enough information for the GC to work (it describes the offsets of GC pointers within the memory region that holds all GC static fields of the type). We ask the GC to allocate an instance of that type and store a GC handle to it in place.

All 3 categories of static fields (GC static, nonGC static, threadstatic) get laid out sequentially into the 3 bases.

class Foo
{
    static int X;
    static int Y;
    static string Z;
}

To access field X, you would ask for the NonGC static base (because FieldDesc.HasGCStaticBase reports false for X) of class Foo and access offset 0. To access field Y, would would ask for the NonGC static base and access offset 4. WASM already does that.

To access field Z, you would ask for the GC static base, do an indirection (the GC static base symbol has a GC handle that needs to be dereferenced), and then access offset 0 (the field Z got laid out in a different base, so the offsets start at 0 again).

[MichalStrehovsky]

The reason why we disallow GC static bases for canonical types is because it doesn't make sense to have them.

There is never an instance of a canonical type allocated. Only code can be canonical.

The gist of shared generics is basically about finding a way to save space when generating generic code - try to find a way how we could share the same code for different instantions of the same generic type definition.

If I have a class with this method:

class Generic<T>
{
    public void Frob(T x)
    {
        x.ToString();
    }
}

And I would like to compile method Generic<object>.Frob() and Generic<string>.Frob(). The generated code for both of them would be this:

G_M37205_IG01:
       4883EC28             sub      rsp, 40

G_M37205_IG02:
       488BCA               mov      rcx, rdx
       488B02               mov      rax, qword ptr [rdx]
       FF5028               call     gword ptr [rax+40]System.Object:ToString():ref:this
       90                   nop

G_M37205_IG03:
       4883C428             add      rsp, 40
       C3                   ret

It seems wasteful to generate this code twice, so we would like to find a way to share it. The easiest is to figure out the sharing scheme for all reference types. The reason why we restrict ourselves to reference types is basically that if T is substituted with a value type, a lot of thigs become different. E.g. here's Generic<double>.Frob()

G_M60901_IG01:
       4883EC28             sub      rsp, 40
       F20F114C2438         movsd    qword ptr [rsp+38H], xmm1

G_M60901_IG02:
       488D4C2438           lea      rcx, bword ptr [rsp+38H]
       E800000000           call     System.Double:ToString():ref:this
       90                   nop

G_M60901_IG03:
       4883C428             add      rsp, 40
       C3                   ret

As you can see, the immediate (huge) difference is that the calling convention is different - the argument was passed in the floating point xmm1 register instead of rdx.

But reference types are sufficiently the same - all of them are a single pointer, and they need to be reported to the GC.

We call code that can be shared by different instantiations "canonical code". The code is canonical because it's not tied to a specific T. The specific T can be subsituted at runtime and the code will do the right thing for it. In the type system, this is represented by a special type System.__Canon that is a reference type and can stand in for any other reference type. We could use System.Object, but then it would be difficult to figure out whether something is actually instantiated over object or represents this special thing that will only have an identity at runtime. Also, System.__Canon can be made to meet all generic constraints. Object wouldn't.

We could just use the same code for everything but the trouble is that whenever we use the T, the code gets a tiny bit different:

class Generic<T>
{
    static T s_field;

    public void Frob(T x)
    {
        Generic<T>.s_field = x;
    }
}

G_M37205_IG01:
       57                   push     rdi
       56                   push     rsi
       4883EC28             sub      rsp, 40
       48894C2420           mov      qword ptr [rsp+20H], rcx
       488BF1               mov      rsi, rcx
       488BFA               mov      rdi, rdx

G_M37205_IG02:
       // ***** Difference! - accessing static base of a particular instantiation *****
       4800000000           lea      eax, Static_Base_Of_Generic<object>
       488D4808             lea      rcx, bword ptr [rax+8]
       488BD7               mov      rdx, rdi
       E800000000           call     CORINFO_HELP_ASSIGN_REF
       90                   nop

G_M37205_IG03:
       4883C428             add      rsp, 40
       5E                   pop      rsi
       5F                   pop      rdi
       C3                   ret

As you can see, the static base we access will be different depending on whether we access Generic<object> or Generic<string>

The way to fix this and make the method canonical again (without a specific identity at compile time) is by adding an indirection. Whenever the canonical code would like to do something with its T (be it a cast, static base access, generic method call, etc.), the codegen will perform an indirection instead of doing a direct access. The indirection will use the runtime identity of the type and substitute the T with the specific thing.

There are 3 ways to supply identity to canonical code:

• For instance methods on generic reference types, we have this, from which we can figure out the specific instance at runtime. (AcquiresInstMethodTableFromThis)
• For generic methods, we inject a hidden argument to the method that supplies the identity (RequiresInstMethodDescArg)
• For static methods on generic types and instance method on generic value types, we inject a hidden argument that supplies the EEType of the owning type (RequiresInstMethodTableArg)

Once we have the identity (also called "generic context"), we can pass it to a helper to retrieve the right thing.

G_M37205_IG01:
       57                   push     rdi
       56                   push     rsi
       4883EC28             sub      rsp, 40
       48894C2420           mov      qword ptr [rsp+20H], rcx
       488BF1               mov      rsi, rcx
       488BFA               mov      rdi, rdx

G_M37205_IG02:
       // Loading `this` into RCX so that the helper can figure out what specific generic instantiation this is
       488B0E               mov      rcx, qword ptr [rsi]
       E800000000           call     CORINFO_HELP_READYTORUN_GENERIC_STATIC_BASE
       488D4808             lea      rcx, bword ptr [rax+8]
       488BD7               mov      rdx, rdi
       E800000000           call     CORINFO_HELP_ASSIGN_REF
       90                   nop

G_M37205_IG03:
       4883C428             add      rsp, 40
       5E                   pop      rsi
       5F                   pop      rdi
       C3                   ret

If we didn't add this indirection, the canonical code would try to retrieve the static base of Generic<__Canon>, but that's incorrect, because we need the static base of the concrete thing.

Static base of Generic<__Canon> doesn't really exist.

[yowl]

Thanks for the clear and detailed responses 👍

[yowl]

Yes, indeed InitializeStatics is run now in wasm, so I'll see if I can enable proper GCStatics instead of the globals that it does now.

[yowl]

I will need to extend

corert/src/ILCompiler.Compiler/src/Compiler/DependencyAnalysis/ReadyToRunGenericHelperNode.cs

Line 16 in 2b158f5

public abstract partial class ReadyToRunGenericHelperNode : AssemblyStubNode, INodeWithRuntimeDeterminedDependencies

or

corert/src/ILCompiler.Compiler/src/Compiler/DependencyAnalysis/ReadyToRunGenericHelperNode.cs

Line 296 in 2b158f5

public partial class ReadyToRunGenericLookupFromTypeNode : ReadyToRunGenericHelperNode

in order to write out the code to do the indirection, correct? I see that x64 does that.

[MichalStrehovsky]

The ReadyToRunGenericHelper node and it's descendants are a bit unfortunately tied to code generation backends where we can emit assembly helpers as bytes.

Eventually, we should probably factor them in a way that they can be reused. If you would like to try that, you can look into that (might be worth a separate pull request).

But I think the thing that would let you make progress the easiest it to just take the approach from CppCodegen - make a GetCodeForReadyToRunGenericHelper equivalent, and use the HelperNode classes as they are (you would use them to track stuff in the dependency graph, but you wouldn't use their GetObjectData to generate bytecode).

[yowl]

Would it be correct to store {[S.P.CoreLib]System.Collections.Generic.IEnumerable`1<System.Collections.Generic.KeyValuePair`2<System.__Canon,System.__Canon>>.GetEnumerator()} in a WebAssemblyVTableSlotNode ? I'm wondering whether I need to delete the assert at

corert/src/ILCompiler.WebAssembly/src/Compiler/DependencyAnalysis/WebAssemblyVTableSlotNode.cs

Line 20 in 4a576fe

Debug.Assert(!targetMethod.IsSharedByGenericInstantiations);

. The c++ code uses a VirtualMethodUseNode for this which is why I'm asking.