Implement escape analysis and stack allocation of non-box objects without gc fields.

This change implements a conservative flow-insensitive escape analysis and stack allocation
of non-box objects without gc fields.

Handling of objects with gc fields, box objects, and fixed-size arrays is future work.

Escape analysis is based on the one described here: https://www.cc.gatech.edu/~harrold/6340/cs6340_fall2009/Readings/choi99escape.pdf

Main limitations of this version of the escape analysis:
1. The analysis is flow-insensitive.
2. The analysis is intra-procedural and only sees the current method and the inlined methods.
3. The analysis assumes that references passed to non-pure-helper calls escape.
4. The analysis assumes that any references assigned to fields of objects escape.

Some of these limitations will be removed in future work.

I started with prior prototypes from @echesakovMSFT and @AndyAyersMS and extended and refactored
parts of them.

I also added tests for cases that are currently handled or will be handled soon.

2 files changed, 286 insertions, 0 deletions

diff --git a/tests/src/JIT/opt/ObjectStackAllocation/ObjectStackAllocationTests.cs b/tests/src/JIT/opt/ObjectStackAllocation/ObjectStackAllocationTests.cs
new file mode 100644
index 0000000000..b01636802b
--- /dev/null
+++ b/tests/src/JIT/opt/ObjectStackAllocation/ObjectStackAllocationTests.cs
@@ -0,0 +1,232 @@
+// Licensed to the .NET Foundation under one or more agreements.
+// The .NET Foundation licenses this file to you under the MIT license.
+// See the LICENSE file in the project root for more information.
+
+using System;
+using System.Reflection;
+using System.Diagnostics;
+using System.Runtime.CompilerServices;
+
+namespace ObjectStackAllocation
+{
+    class SimpleClassA
+    {
+        public int f1;
+        public int f2;
+
+        public SimpleClassA(int f1, int f2)
+        {
+            this.f1 = f1;
+            this.f2 = f2;
+        }
+    }
+
+    sealed class SimpleClassB
+    {
+        public long f1;
+        public long f2;
+
+        public SimpleClassB(long f1, long f2)
+        {
+            this.f1 = f1;
+            this.f2 = f2;
+        }
+    }
+
+    class SimpleClassWithGCField : SimpleClassA
+    {
+        public object o;
+
+        public SimpleClassWithGCField(int f1, int f2, object o) : base(f1, f2)
+        {
+            this.o = o;
+        }
+    }
+
+    class ClassWithNestedStruct
+    {
+        public ClassWithNestedStruct(int f1, int f2)
+        {
+            ns.f1 = f1;
+            ns.f2 = f2;
+            ns.s.f1 = f1;
+            ns.s.f2 = f2;
+        }
+
+        public NestedStruct ns;
+    }
+
+    struct SimpleStruct
+    {
+        public int f1;
+        public int f2;
+    }
+
+    struct NestedStruct
+    {
+        public int f1;
+        public int f2;
+        public SimpleStruct s;
+    }
+
+    class Tests
+    {
+        static volatile int f1 = 5;
+        static volatile int f2 = 7;
+
+        delegate int Test();
+
+        static int methodResult = 100;
+
+        public static int Main()
+        {
+            bool spcOptimizationEnabled = SPCOptimizationsEnabled();
+
+            CallTestAndVerifyAllocation(AllocateSimpleClassAndAddFields, 12, !spcOptimizationEnabled);
+
+            CallTestAndVerifyAllocation(AllocateSimpleClassesAndEQCompareThem, 0, !spcOptimizationEnabled);
+
+            CallTestAndVerifyAllocation(AllocateSimpleClassesAndNECompareThem, 1, !spcOptimizationEnabled);
+
+            CallTestAndVerifyAllocation(AllocateSimpleClassAndCheckType, 1, !spcOptimizationEnabled);
+
+            CallTestAndVerifyAllocation(AllocateSimpleClassAndCast, 7, !spcOptimizationEnabled);
+
+            CallTestAndVerifyAllocation(AllocateSimpleClassAndGetField, 7, !spcOptimizationEnabled);
+
+            CallTestAndVerifyAllocation(AllocateClassWithNestedStructAndGetField, 5, !spcOptimizationEnabled);
+
+            CallTestAndVerifyAllocation(AllocateClassWithNestedStructAndAddFields, 24, !spcOptimizationEnabled);
+
+            // Stack allocation of classes with GC fields is currently disabled
+            CallTestAndVerifyAllocation(AllocateSimpleClassWithGCFieldAndAddFields, 12, true);
+
+            // Assigning class ref to a field of another object currently always disables stack allocation
+            CallTestAndVerifyAllocation(AllocateSimpleClassAndAssignRefToAField, 12, true);
+
+            // Stack allocation of boxed structs is currently disabled
+            CallTestAndVerifyAllocation(BoxSimpleStructAndAddFields, 12, true);
+
+            return methodResult;
+        }
+
+        static bool SPCOptimizationsEnabled()
+        {
+            Assembly objectAssembly = Assembly.GetAssembly(typeof(object));
+            object[] attribs = objectAssembly.GetCustomAttributes(typeof(DebuggableAttribute),
+                                                        false);
+            DebuggableAttribute debuggableAttribute = attribs[0] as DebuggableAttribute;
+            return ((debuggableAttribute == null) || !debuggableAttribute.IsJITOptimizerDisabled);
+        }
+
+        static void CallTestAndVerifyAllocation(Test test, int expectedResult, bool expectHeapAllocations)
+        {
+            long allocatedBytesBefore = GC.GetAllocatedBytesForCurrentThread();
+            int testResult = test();
+            long allocatedBytesAfter = GC.GetAllocatedBytesForCurrentThread();
+            string methodName = test.Method.Name;
+
+            if (testResult != expectedResult) {
+                Console.WriteLine($"FAILURE ({methodName}): expected {expectedResult}, got {testResult}");
+                methodResult = -1;
+            }
+            else if (!expectHeapAllocations && (allocatedBytesBefore != allocatedBytesAfter)) {
+                Console.WriteLine($"FAILURE ({methodName}): unexpected allocation of {allocatedBytesAfter - allocatedBytesBefore} bytes");
+                methodResult = -1;
+            }
+            else if (expectHeapAllocations && (allocatedBytesBefore == allocatedBytesAfter)) {
+                Console.WriteLine($"FAILURE ({methodName}): unexpected stack allocation");
+                methodResult = -1;
+            }
+            else {
+                Console.WriteLine($"SUCCESS ({methodName})");
+            }
+        }
+
+        [MethodImpl(MethodImplOptions.NoInlining)]
+        static int AllocateSimpleClassAndAddFields()
+        {
+            SimpleClassA a = new SimpleClassA(f1, f2);
+            GC.Collect();
+            return a.f1 + a.f2;
+        }
+
+        [MethodImpl(MethodImplOptions.NoInlining)]
+        static int AllocateSimpleClassesAndEQCompareThem()
+        {
+            SimpleClassA a1 = new SimpleClassA(f1, f2);
+            SimpleClassA a2 = (f1 == 0) ? a1 : new SimpleClassA(f2, f1);
+            return (a1 == a2) ? 1 : 0;
+        }
+
+        [MethodImpl(MethodImplOptions.NoInlining)]
+        static int AllocateSimpleClassesAndNECompareThem()
+        {
+            SimpleClassA a1 = new SimpleClassA(f1, f2);
+            SimpleClassA a2 = (f1 == 0) ? a1 : new SimpleClassA(f2, f1);
+            return (a1 != a2) ? 1 : 0;
+        }
+
+        [MethodImpl(MethodImplOptions.NoInlining)]
+        static int AllocateSimpleClassAndCheckType()
+        {
+            object o = (f1 == 0) ? (object)new SimpleClassB(f1, f2) : (object)new SimpleClassA(f1, f2);
+            return (o is SimpleClassB) || !(o is SimpleClassA) ? 0 : 1;
+        }
+
+        [MethodImpl(MethodImplOptions.NoInlining)]
+        static int AllocateSimpleClassAndCast()
+        {
+            object o = (f1 == 0) ? (object)new SimpleClassB(f1, f2) : (object)new SimpleClassA(f2, f1);
+            return ((SimpleClassA)o).f1;
+        }
+
+        [MethodImpl(MethodImplOptions.NoInlining)]
+        static int AllocateSimpleClassAndGetField()
+        {
+            SimpleClassA a = new SimpleClassA(f1, f2);
+            ref int f = ref a.f2;
+            return f;
+        }
+
+        [MethodImpl(MethodImplOptions.NoInlining)]
+        static int AllocateClassWithNestedStructAndGetField()
+        {
+            ClassWithNestedStruct c = new ClassWithNestedStruct(f1, f2);
+            ref int f = ref c.ns.s.f1;
+            return f;
+        }
+
+        [MethodImpl(MethodImplOptions.NoInlining)]
+        static int AllocateClassWithNestedStructAndAddFields()
+        {
+            ClassWithNestedStruct c = new ClassWithNestedStruct(f1, f2);
+            return c.ns.f1 + c.ns.f2 + c.ns.s.f1 + c.ns.s.f2;
+        }
+
+        [MethodImpl(MethodImplOptions.NoInlining)]
+        static int AllocateSimpleClassWithGCFieldAndAddFields()
+        {
+            SimpleClassWithGCField c = new SimpleClassWithGCField(f1, f2, null);
+            return c.f1 + c.f2;
+        }
+
+        static int AllocateSimpleClassAndAssignRefToAField()
+        {
+            SimpleClassWithGCField c = new SimpleClassWithGCField(f1, f2, null);
+            SimpleClassA a = new SimpleClassA(f1, f2);
+            c.o = a;
+            return c.f1 + c.f2;
+        }
+
+        [MethodImpl(MethodImplOptions.NoInlining)]
+        static int BoxSimpleStructAndAddFields()
+        {
+            SimpleStruct str;
+            str.f1 = f1;
+            str.f2 = f2;
+            object boxedSimpleStruct = (object)str;
+            return ((SimpleStruct)boxedSimpleStruct).f1 + ((SimpleStruct)boxedSimpleStruct).f2;
+        }
+    }
+}
diff --git a/tests/src/JIT/opt/ObjectStackAllocation/ObjectStackAllocationTests.csproj b/tests/src/JIT/opt/ObjectStackAllocation/ObjectStackAllocationTests.csproj
new file mode 100644
index 0000000000..280c9912f0
--- /dev/null
+++ b/tests/src/JIT/opt/ObjectStackAllocation/ObjectStackAllocationTests.csproj
@@ -0,0 +1,54 @@
+<?xml version="1.0" encoding="utf-8"?>
+<Project ToolsVersion="12.0" DefaultTargets="Build" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
+  <Import Project="$([MSBuild]::GetDirectoryNameOfFileAbove($(MSBuildThisFileDirectory), dir.props))\dir.props" />
+  <PropertyGroup>
+    <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
+    <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
+    <AssemblyName>$(MSBuildProjectName)</AssemblyName>
+    <SchemaVersion>2.0</SchemaVersion>
+    <ProjectGuid>{95DFC527-4DC1-495E-97D7-E94EE1F7140D}</ProjectGuid>
+    <OutputType>Exe</OutputType>
+    <ProjectTypeGuids>{786C830F-07A1-408B-BD7F-6EE04809D6DB};{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}</ProjectTypeGuids>
+    <SolutionDir Condition="$(SolutionDir) == '' Or $(SolutionDir) == '*Undefined*'">..\..\</SolutionDir>
+  </PropertyGroup>
+  <!-- Default configurations to help VS understand the configurations -->
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' "></PropertyGroup>
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' "></PropertyGroup>
+  <ItemGroup>
+    <CodeAnalysisDependentAssemblyPaths Condition=" '$(VS100COMNTOOLS)' != '' " Include="$(VS100COMNTOOLS)..\IDE\PrivateAssemblies">
+      <Visible>False</Visible>
+    </CodeAnalysisDependentAssemblyPaths>
+  </ItemGroup>
+  <PropertyGroup>
+    <DebugType>None</DebugType>
+    <Optimize>True</Optimize>
+  </PropertyGroup>
+  <ItemGroup>
+    <Compile Include="$(MSBuildProjectName).cs" />
+  </ItemGroup>
+  <PropertyGroup>
+    <CLRTestBatchPreCommands>
+      <![CDATA[
+$(CLRTestBatchPreCommands)
+set COMPlus_TieredCompilation=0
+set COMPlus_JitMinOpts=0
+set COMPlus_JitDebuggable=0
+set COMPlus_JitObjectStackAllocation=1
+]]>
+    </CLRTestBatchPreCommands>
+    <BashCLRTestPreCommands>
+      <![CDATA[
+$(BashCLRTestPreCommands)
+export COMPlus_TieredCompilation=0
+export COMPlus_JitMinOpts=0
+export COMPlus_JitDebuggable=0
+export COMPlus_JitObjectStackAllocation=1
+]]>
+    </BashCLRTestPreCommands>
+  </PropertyGroup>
+  <ItemGroup>
+    <Service Include="{82A7F48D-3B50-4B1E-B82E-3ADA8210C358}" />
+  </ItemGroup>
+  <Import Project="$([MSBuild]::GetDirectoryNameOfFileAbove($(MSBuildThisFileDirectory), dir.targets))\dir.targets" />
+  <PropertyGroup Condition=" '$(MsBuildProjectDirOverride)' != '' "></PropertyGroup>
+</Project>