Implement a caching version of virtual method enumeration algorithm (#1439)

When compiling hello world, computing virtual method overrides shows up as pretty hot. Turns out the slowdown is mostly caused by the enumeration being slow. I'm introducing a caching version of the algorithm.

This drops hello world compilation time from ~3.4 seconds to ~3.2 seconds (!).

Some notes:
* Caching only the methods on definitions, not on instantiated types.
* I'm not adding cache invalidation. Since I'm not caching methods on generic instantiations, this shouldn't explode too much.
* We might get further benefit if we change `IEnumerable<MethodDesc>` to `MethodDesc[]` in the method signature, but I'm not sure we would want to do that.

3 files changed, 72 insertions, 0 deletions

diff --git a/src/ILCompiler.TypeSystem/src/ILCompiler.TypeSystem.csproj b/src/ILCompiler.TypeSystem/src/ILCompiler.TypeSystem.csproj
index 546c7ce91..da7a25e4e 100644
--- a/src/ILCompiler.TypeSystem/src/ILCompiler.TypeSystem.csproj
+++ b/src/ILCompiler.TypeSystem/src/ILCompiler.TypeSystem.csproj
@@ -71,6 +71,9 @@
     <Compile Include="..\..\Common\src\TypeSystem\Common\AlignmentHelper.cs">
       <Link>Utilities\AlignmentHelper.cs</Link>
     </Compile>
+    <Compile Include="..\..\Common\src\TypeSystem\Common\CachingVirtualMethodEnumerationAlgorithm.cs">
+      <Link>TypeSystem\Common\CachingVirtualMethodEnumerationAlgorithm.cs</Link>
+    </Compile>
     <Compile Include="..\..\Common\src\TypeSystem\Common\CastingHelper.cs">
       <Link>TypeSystem\Common\CastingHelper.cs</Link>
     </Compile>
diff --git a/src/ILCompiler.TypeSystem/tests/TypeSystem.Tests.csproj b/src/ILCompiler.TypeSystem/tests/TypeSystem.Tests.csproj
index 0daef9090..4d735d9b3 100644
--- a/src/ILCompiler.TypeSystem/tests/TypeSystem.Tests.csproj
+++ b/src/ILCompiler.TypeSystem/tests/TypeSystem.Tests.csproj
@@ -49,6 +49,7 @@
     <Compile Include="InstanceFieldLayoutTests.cs" />
     <Compile Include="StaticFieldLayoutTests.cs" />
     <Compile Include="TestTypeSystemContext.cs" />
+    <Compile Include="VirtualMethodEnumerationAlgorithmTests.cs" />
     <Compile Include="WellKnownTypeTests.cs" />
   </ItemGroup>
   <ItemGroup>
diff --git a/src/ILCompiler.TypeSystem/tests/VirtualMethodEnumerationAlgorithmTests.cs b/src/ILCompiler.TypeSystem/tests/VirtualMethodEnumerationAlgorithmTests.cs
new file mode 100644
index 000000000..8c1f30e6b
--- /dev/null
+++ b/src/ILCompiler.TypeSystem/tests/VirtualMethodEnumerationAlgorithmTests.cs
@@ -0,0 +1,68 @@
+// 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.Collections.Generic;
+using System.Linq;
+
+using Internal.TypeSystem;
+
+using Xunit;
+
+
+namespace TypeSystemTests
+{
+    public class VirtualMethodEnumerationAlgorithmTests
+    {
+        TestTypeSystemContext _context;
+        ModuleDesc _testModule;
+        MetadataType _testType;
+
+        public VirtualMethodEnumerationAlgorithmTests()
+        {
+            _context = new TestTypeSystemContext(TargetArchitecture.Unknown);
+            var systemModule = _context.CreateModuleForSimpleName("CoreTestAssembly");
+            _context.SetSystemModule(systemModule);
+
+            _testModule = systemModule;
+
+            _testType = _testModule.GetType("VirtualFunctionOverride", "SimpleGeneric`1")
+                .MakeInstantiatedType(_context.GetWellKnownType(WellKnownType.Object));
+        }
+
+        [Fact]
+        public void TestMetadataEnumerationAlgorithm()
+        {
+            var algo = new MetadataVirtualMethodEnumerationAlgorithm();
+
+            DefType objectType = _context.GetWellKnownType(WellKnownType.Object);
+            var objectMethods = algo.ComputeAllVirtualMethods(objectType).ToArray();
+            Assert.Equal(4, objectMethods.Length);
+            Assert.Superset(new HashSet<string> { "Equals", "GetHashCode", "ToString", "Finalize" },
+                new HashSet<string>(objectMethods.Select(m => m.Name)));
+
+            var testTypeMethods = algo.ComputeAllVirtualMethods(_testType).ToArray();
+            Assert.Equal(1, testTypeMethods.Length);
+            Assert.Equal("ToString", testTypeMethods[0].Name);
+            Assert.Equal(_testType, testTypeMethods[0].OwningType);
+        }
+
+        [Fact]
+        public void TestCachingEnumerationAlgorithm()
+        {
+            var algo = new CachingVirtualMethodEnumerationAlgorithm();
+
+            DefType objectType = _context.GetWellKnownType(WellKnownType.Object);
+            var objectMethods = algo.ComputeAllVirtualMethods(objectType).ToArray();
+            Assert.Equal(4, objectMethods.Length);
+            Assert.Superset(new HashSet<string> { "Equals", "GetHashCode", "ToString", "Finalize" },
+                new HashSet<string>(objectMethods.Select(m => m.Name)));
+
+            var testTypeMethods = algo.ComputeAllVirtualMethods(_testType).ToArray();
+            Assert.Equal(1, testTypeMethods.Length);
+            Assert.Equal("ToString", testTypeMethods[0].Name);
+            Assert.Equal(_testType, testTypeMethods[0].OwningType);
+        }
+    }
+}