Implement localloc for WebAssembly (#5298)

* Implements localloc and fixes other issues required to make Int32.ToString work (which relies on stack allocation, Spans and various value type special cases). Includes:
* Allocating localloc buffers on the C++ stack since they're guaranteed not to have GC references and LLVM might be able to optimize them a bit better
* Handling newobj for value types by allocating them in a spill slot
* Implementing the ByReference.get_Value intrinsic
* Fixing various shadow stack management bugs around calls. In particular, return values are now spilled to avoid the next call overwriting them.
* A few new tests

2 files changed, 82 insertions, 32 deletions

diff --git a/src/ILCompiler.WebAssembly/src/CodeGen/EvaluationStack.cs b/src/ILCompiler.WebAssembly/src/CodeGen/EvaluationStack.cs
index bdc2b4564..92c191976 100644
--- a/src/ILCompiler.WebAssembly/src/CodeGen/EvaluationStack.cs
+++ b/src/ILCompiler.WebAssembly/src/CodeGen/EvaluationStack.cs
@@ -570,7 +570,10 @@ namespace Internal.IL
 
         protected override LLVMValueRef ValueAsTypeInternal(LLVMTypeRef type, LLVMBuilderRef builder, bool signExtend)
         {
-            return _importer.LoadTemp(LocalIndex, type);
+            LLVMTypeRef origLLVMType = ILImporter.GetLLVMTypeForTypeDesc(Type);
+            LLVMValueRef value = _importer.LoadTemp(LocalIndex, origLLVMType);
+
+            return ILImporter.CastIfNecessary(builder, value, type);
         }
 
         public override StackEntry Duplicate()
diff --git a/src/ILCompiler.WebAssembly/src/CodeGen/ILToWebAssemblyImporter.cs b/src/ILCompiler.WebAssembly/src/CodeGen/ILToWebAssemblyImporter.cs
index be76e7c25..c31744076 100644
--- a/src/ILCompiler.WebAssembly/src/CodeGen/ILToWebAssemblyImporter.cs
+++ b/src/ILCompiler.WebAssembly/src/CodeGen/ILToWebAssemblyImporter.cs
@@ -142,6 +142,11 @@ namespace Internal.IL
 
         private void GenerateProlog()
         {
+            if (!_methodIL.IsInitLocals)
+            {
+                return;
+            }
+
             int totalLocalSize = 0;
             foreach(LocalVariableDefinition local in _locals)
             {
@@ -149,7 +154,7 @@ namespace Internal.IL
             }
 
             var sp = LLVM.GetFirstParam(_llvmFunction);
-            int paramOffset = totalLocalSize.AlignUp(_pointerSize) + GetTotalParameterOffset();
+            int paramOffset = GetTotalParameterOffset();
             for (int i = 0; i < totalLocalSize; i++)
             {
                 var stackOffset = LLVM.BuildGEP(_builder, sp, new LLVMValueRef[] { LLVM.ConstInt(LLVM.Int32Type(), (ulong)(paramOffset + i), LLVMMisc.False) }, String.Empty);
@@ -187,8 +192,13 @@ namespace Internal.IL
         private void ImportCallMemset(LLVMValueRef targetPointer, byte value, int length)
         {
             LLVMValueRef objectSizeValue = BuildConstInt32(length);
+            ImportCallMemset(targetPointer, value, objectSizeValue);
+        }
+
+        private void ImportCallMemset (LLVMValueRef targetPointer, byte value, LLVMValueRef length)
+        {
             var memsetSignature = LLVM.FunctionType(LLVM.VoidType(), new LLVMTypeRef[] { LLVM.PointerType(LLVM.Int8Type(), 0), LLVM.Int8Type(), LLVM.Int32Type(), LLVM.Int32Type(), LLVM.Int1Type() }, false);
-            LLVM.BuildCall(_builder, GetOrCreateLLVMFunction("llvm.memset.p0i8.i32", memsetSignature), new LLVMValueRef[] { targetPointer, BuildConstInt8(value), objectSizeValue, BuildConstInt32(1), BuildConstInt1(0) }, String.Empty);
+            LLVM.BuildCall(_builder, GetOrCreateLLVMFunction("llvm.memset.p0i8.i32", memsetSignature), new LLVMValueRef[] { targetPointer, BuildConstInt8(value), length, BuildConstInt32(1), BuildConstInt1(0) }, String.Empty);
         }
 
         private void PushLoadExpression(StackValueKind kind, string name, LLVMValueRef rawLLVMValue, TypeDesc type)
@@ -430,7 +440,7 @@ namespace Internal.IL
             }
             else
             {
-                varBase = GetTotalRealLocalOffset();
+                varBase = GetTotalRealLocalOffset() + GetTotalParameterOffset();
                 GetSpillSizeAndOffsetAtIndex(index, out int localSize, out varOffset);
                 valueType = GetLLVMTypeForTypeDesc(_spilledExpressions[index].Type);
                 type = _spilledExpressions[index].Type;
@@ -846,7 +856,8 @@ namespace Internal.IL
 
             if (opcode == ILOpcode.newobj)
             {
-                if (callee.OwningType.IsString)
+                TypeDesc newType = callee.OwningType;
+                if (newType.IsString)
                 {
                     // String constructors actually look like regular method calls
                     IMethodNode node = _compilation.NodeFactory.StringAllocator(callee);
@@ -856,12 +867,32 @@ namespace Internal.IL
                 }
                 else
                 {
-                    StackEntry newObjResult = AllocateObject(callee.OwningType);
-                    //one for the real result and one to be consumed by ctor
                     if (callee.Signature.Length > _stack.Length) //System.Reflection.MemberFilter.ctor
                         throw new InvalidProgramException();
-                    _stack.InsertAt(newObjResult, _stack.Top - callee.Signature.Length);
-                    _stack.InsertAt(newObjResult, _stack.Top - callee.Signature.Length);
+
+                    StackEntry newObjResult;
+                    if (newType.IsValueType)
+                    {
+                        // Allocate a slot on the shadow stack for the value type
+                        int spillIndex = _spilledExpressions.Count;
+                        SpilledExpressionEntry spillEntry = new SpilledExpressionEntry(GetStackValueKind(newType), "newobj" + _currentOffset, newType, spillIndex, this);
+                        _spilledExpressions.Add(spillEntry);
+                        LLVMValueRef addrOfValueType = LoadVarAddress(spillIndex, LocalVarKind.Temp, out TypeDesc unused);
+                        AddressExpressionEntry valueTypeByRef = new AddressExpressionEntry(StackValueKind.ByRef, "newobj_slot" + _currentOffset, addrOfValueType, newType.MakeByRefType());
+
+                        // The ctor needs a reference to the spill slot, but the 
+                        // actual value ends up on the stack after the ctor is done
+                        _stack.InsertAt(spillEntry, _stack.Top - callee.Signature.Length);
+                        _stack.InsertAt(valueTypeByRef, _stack.Top - callee.Signature.Length);
+                    }
+                    else
+                    {
+                        newObjResult = AllocateObject(callee.OwningType);
+
+                        //one for the real result and one to be consumed by ctor
+                        _stack.InsertAt(newObjResult, _stack.Top - callee.Signature.Length);
+                        _stack.InsertAt(newObjResult, _stack.Top - callee.Signature.Length);
+                    }
                 }
             }
 
@@ -1000,12 +1031,13 @@ namespace Internal.IL
 
             switch (method.Name)
             {
-                // Workaround for not being able to build a WASM version of CoreLib. This method
-                // would return the x64 size, which is too large for WASM
-                case "get_OffsetToStringData":
-                    if (metadataType.Name == "RuntimeHelpers" && metadataType.Namespace == "System.Runtime.CompilerServices")
+                case "get_Value":
+                    if (metadataType.IsByReferenceOfT)
                     {
-                        _stack.Push(new Int32ConstantEntry(8, _method.Context.GetWellKnownType(WellKnownType.Int32)));
+                        StackEntry byRefHolder = _stack.Pop();
+
+                        TypeDesc byRefType = metadataType.Instantiation[0].MakeByRefType();
+                        PushLoadExpression(StackValueKind.ByRef, "byref", byRefHolder.ValueForStackKind(StackValueKind.ByRef, _builder, false), byRefType);
                         return true;
                     }
                     break;
@@ -1026,7 +1058,7 @@ namespace Internal.IL
             PushNonNull(HandleCall(callee, signature, argumentValues, opcode, calliTarget));
         }
 
-        private LoadExpressionEntry HandleCall(MethodDesc callee, MethodSignature signature, StackEntry[] argumentValues, ILOpcode opcode = ILOpcode.call, LLVMValueRef calliTarget = default(LLVMValueRef), TypeDesc forcedReturnType = null)
+        private ExpressionEntry HandleCall(MethodDesc callee, MethodSignature signature, StackEntry[] argumentValues, ILOpcode opcode = ILOpcode.call, LLVMValueRef calliTarget = default(LLVMValueRef), TypeDesc forcedReturnType = null)
         {
             if (opcode == ILOpcode.callvirt && callee.IsVirtual)
             {
@@ -1037,20 +1069,18 @@ namespace Internal.IL
                 AddMethodReference(callee);
             }
             var pointerSize = _compilation.NodeFactory.Target.PointerSize;
-            int offset = GetTotalParameterOffset() + GetTotalLocalOffset() +
-                signature.ReturnType.GetElementSize().AsInt;
 
             LLVMValueRef returnAddress;
             LLVMValueRef castReturnAddress;
-            if (signature.ReturnType != GetWellKnownType(WellKnownType.Void))
+            TypeDesc returnType = signature.ReturnType;
+            SpilledExpressionEntry returnSlot = null;
+            if (!returnType.IsVoid)
             {
-                offset = PadNextOffset(signature.ReturnType, offset);
-
-                int returnOffset = GetTotalParameterOffset() + GetTotalLocalOffset();
-                returnAddress = LLVM.BuildGEP(_builder, LLVM.GetFirstParam(_llvmFunction),
-                    new LLVMValueRef[] { LLVM.ConstInt(LLVM.Int32Type(), (uint)returnOffset, LLVMMisc.False) },
-                    String.Empty);
-                castReturnAddress = LLVM.BuildPointerCast(_builder, returnAddress, LLVM.PointerType(LLVM.Int8Type(), 0), "castreturnaddress");
+                int returnIndex = _spilledExpressions.Count;
+                returnSlot = new SpilledExpressionEntry(GetStackValueKind(returnType), callee?.Name + "_return", returnType, returnIndex, this);
+                _spilledExpressions.Add(returnSlot);
+                returnAddress = LoadVarAddress(returnIndex, LocalVarKind.Temp, out TypeDesc unused);
+                castReturnAddress = LLVM.BuildPointerCast(_builder, returnAddress, LLVM.PointerType(LLVM.Int8Type(), 0), callee?.Name + "_castreturn");
             }
             else
             {
@@ -1058,6 +1088,7 @@ namespace Internal.IL
                 castReturnAddress = returnAddress;
             }
 
+            int offset = GetTotalParameterOffset() + GetTotalLocalOffset();
             LLVMValueRef shadowStack = LLVM.BuildGEP(_builder, LLVM.GetFirstParam(_llvmFunction),
                 new LLVMValueRef[] { LLVM.ConstInt(LLVM.Int32Type(), (uint)offset, LLVMMisc.False) },
                 String.Empty);
@@ -1106,11 +1137,10 @@ namespace Internal.IL
                 castShadowStack,
                 castReturnAddress}, string.Empty);
 
-
-            if (!signature.ReturnType.IsVoid)
+            
+            if (!returnType.IsVoid)
             {
-                var returnType = forcedReturnType ?? signature.ReturnType;
-                return new LoadExpressionEntry(GetStackValueKind(returnType), String.Empty, returnAddress, returnType);
+                return returnSlot;
             }
             else
             {
@@ -1138,6 +1168,7 @@ namespace Internal.IL
                 arguments[arguments.Length - i - 1] = _stack.Pop();
             }
 
+
             PushNonNull(ImportRawPInvoke(method, arguments));
         }
 
@@ -1148,6 +1179,7 @@ namespace Internal.IL
                 throw new NotImplementedException();
 
             string realMethodName = method.Name;
+
             if (!method.IsPInvoke && method is TypeSystem.Ecma.EcmaMethod)
             {
                 realMethodName = ((TypeSystem.Ecma.EcmaMethod)method).GetRuntimeImportName() ?? method.Name;
@@ -1572,8 +1604,8 @@ namespace Internal.IL
             }
 
             LLVMValueRef result;
-            LLVMValueRef left = op1.ValueForStackKind(kind, _builder, false);
-            LLVMValueRef right = op2.ValueForStackKind(kind, _builder, false);
+            LLVMValueRef left = op2.ValueForStackKind(kind, _builder, false);
+            LLVMValueRef right = op1.ValueForStackKind(kind, _builder, false);
             if (kind == StackValueKind.Float)
             {
                 switch (opcode)
@@ -1948,6 +1980,16 @@ namespace Internal.IL
 
         private void ImportLocalAlloc()
         {
+            StackEntry allocSizeEntry = _stack.Pop();
+            LLVMValueRef allocSize = allocSizeEntry.ValueAsInt32(_builder, false);
+            LLVMValueRef allocatedMemory = LLVM.BuildArrayAlloca(_builder, LLVMTypeRef.Int8Type(), allocSize, "localloc" + _currentOffset);
+            LLVM.SetAlignment(allocatedMemory, (uint)_pointerSize);
+            if (_methodIL.IsInitLocals)
+            {
+                ImportCallMemset(allocatedMemory, 0, allocSize);
+            }
+
+            PushExpression(StackValueKind.NativeInt, "localloc" + _currentOffset, allocatedMemory, _compilation.TypeSystemContext.GetPointerType(GetWellKnownType(WellKnownType.Void)));
         }
 
         private void ImportEndFilter()
@@ -2343,9 +2385,14 @@ namespace Internal.IL
             {
                 addressValue = ((LoadExpressionEntry)entry).RawLLVMValue;
             }
+            else if (entry is SpilledExpressionEntry)
+            {
+                int spillIndex = ((SpilledExpressionEntry)entry).LocalIndex;
+                addressValue = LoadVarAddress(spillIndex, LocalVarKind.Temp, out TypeDesc unused);
+            }
             else
             {
-                //This path should only ever be taken for constants and the results of a primative cast (not writable)
+                //This path should only ever be taken for constants and the results of a primitive cast (not writable)
                 //all other cases should be operating on a LoadExpressionEntry
                 var entryIndex = _spilledExpressions.Count;
                 var newEntry = new SpilledExpressionEntry(entry.Kind, entry is ExpressionEntry ? ((ExpressionEntry)entry).Name : "address_of_temp" + entryIndex, entryType, entryIndex, this);