Generate runs of interface dispatch cells

When interface dispatch was initially implemented in CoreRT, we took a number of shortcuts (dotnet/corert#626). Skipping the size on disk optimization around generating runs of interface dispatch cells with the same slot number was one of the shortcuts (each cell represented its own run).

With this, I'm implementing the same optimization that binder does. For PureNative shared library, this saves 100 kB. I didn't measure savings for apps, but I expect them to be similar.

[tfs-changeset: 1708487]

5 files changed, 168 insertions, 25 deletions

diff --git a/src/ILCompiler.Compiler/src/Compiler/DependencyAnalysis/InterfaceDispatchCellNode.cs b/src/ILCompiler.Compiler/src/Compiler/DependencyAnalysis/InterfaceDispatchCellNode.cs
index d6025238d..4bcd90215 100644
--- a/src/ILCompiler.Compiler/src/Compiler/DependencyAnalysis/InterfaceDispatchCellNode.cs
+++ b/src/ILCompiler.Compiler/src/Compiler/DependencyAnalysis/InterfaceDispatchCellNode.cs
@@ -2,6 +2,7 @@
 // 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.Collections.Generic;
 using System.Diagnostics;
 
 using Internal.Runtime;
@@ -10,11 +11,15 @@ using Internal.TypeSystem;
 
 namespace ILCompiler.DependencyAnalysis
 {
-    public class InterfaceDispatchCellNode : ObjectNode, ISymbolDefinitionNode
+    public class InterfaceDispatchCellNode : EmbeddedObjectNode, ISymbolDefinitionNode
     {
         private readonly MethodDesc _targetMethod;
         private readonly string _callSiteIdentifier;
 
+        internal MethodDesc TargetMethod => _targetMethod;
+
+        internal string CallSiteIdentifier => _callSiteIdentifier;
+
         public InterfaceDispatchCellNode(MethodDesc targetMethod, string callSiteIdentifier)
         {
             Debug.Assert(targetMethod.OwningType.IsInterface);
@@ -27,7 +32,10 @@ namespace ILCompiler.DependencyAnalysis
         {
             sb.Append(GetMangledName(nameMangler, _targetMethod, _callSiteIdentifier));
         }
-        public int Offset => 0;
+
+        int ISymbolDefinitionNode.Offset => OffsetFromBeginningOfArray;
+
+        int ISymbolNode.Offset => 0;
 
         public override bool IsShareable => false;
 
@@ -45,11 +53,9 @@ namespace ILCompiler.DependencyAnalysis
 
         protected override string GetName(NodeFactory factory) => this.GetMangledName(factory.NameMangler);
 
-        public override ObjectNodeSection Section => ObjectNodeSection.DataSection;
-
         public override bool StaticDependenciesAreComputed => true;
 
-        protected override DependencyList ComputeNonRelocationBasedDependencies(NodeFactory factory)
+        public override IEnumerable<DependencyListEntry> GetStaticDependencies(NodeFactory factory)
         {
             DependencyList result = new DependencyList();
 
@@ -59,18 +65,25 @@ namespace ILCompiler.DependencyAnalysis
             }
 
             factory.MetadataManager.GetDependenciesDueToVirtualMethodReflectability(ref result, factory, _targetMethod);
-            
+
+            TargetArchitecture targetArchitecture = factory.Target.Architecture;
+            if (targetArchitecture == TargetArchitecture.ARM ||
+                targetArchitecture == TargetArchitecture.ARMEL)
+            {
+                result.Add(factory.InitialInterfaceDispatchStub, "Initial interface dispatch stub");
+            }
+            else
+            {
+                result.Add(factory.ExternSymbol("RhpInitialDynamicInterfaceDispatch"), "Initial interface dispatch stub");
+            }
+
+            result.Add(factory.NecessaryTypeSymbol(_targetMethod.OwningType), "Interface type");
+
             return result;
         }
 
-        public override ObjectData GetData(NodeFactory factory, bool relocsOnly = false)
+        public override void EncodeData(ref ObjectDataBuilder objData, NodeFactory factory, bool relocsOnly)
         {
-            ObjectDataBuilder objData = new ObjectDataBuilder(factory, relocsOnly);
-            // The interface dispatch cell has an alignment requirement of 2 * [Pointer size] as part of the 
-            // synchronization mechanism of the two values in the runtime.
-            objData.RequireInitialAlignment(_targetMethod.Context.Target.PointerSize * 2);
-            objData.AddSymbol(this);
-
             TargetArchitecture targetArchitecture = factory.Target.Architecture;
             if (targetArchitecture == TargetArchitecture.ARM ||
                 targetArchitecture == TargetArchitecture.ARMEL)
@@ -101,17 +114,11 @@ namespace ILCompiler.DependencyAnalysis
                 // 32 bits on targets whose pointer size is 64 bit. 
                 objData.EmitInt(0);
             }
+        }
 
-            // End the run of dispatch cells
-            objData.EmitZeroPointer();
-
-            // Avoid consulting VTable slots until they're guaranteed complete during final data emission
-            if (!relocsOnly)
-            {
-                objData.EmitNaturalInt(VirtualMethodSlotHelper.GetVirtualMethodSlot(factory, _targetMethod, _targetMethod.OwningType));
-            }
-
-            return objData.ToObjectData();
+        protected override void OnMarked(NodeFactory factory)
+        {
+            factory.InterfaceDispatchCellSection.AddEmbeddedObject(this);
         }
 
         public override int ClassCode => -2023802120;
diff --git a/src/ILCompiler.Compiler/src/Compiler/DependencyAnalysis/InterfaceDispatchCellSectionNode.cs b/src/ILCompiler.Compiler/src/Compiler/DependencyAnalysis/InterfaceDispatchCellSectionNode.cs
new file mode 100644
index 000000000..274a4254a
--- /dev/null
+++ b/src/ILCompiler.Compiler/src/Compiler/DependencyAnalysis/InterfaceDispatchCellSectionNode.cs
@@ -0,0 +1,132 @@
+// 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 Internal.TypeSystem;
+
+using Debug = System.Diagnostics.Debug;
+
+namespace ILCompiler.DependencyAnalysis
+{
+    /// <summary>
+    /// Represents a section of the executable where interface dispatch cells and their slot information
+    /// is stored.
+    /// </summary>
+    public class InterfaceDispatchCellSectionNode : ArrayOfEmbeddedDataNode<InterfaceDispatchCellNode>
+    {
+        public InterfaceDispatchCellSectionNode(NodeFactory factory)
+            : base("__InterfaceDispatchCellSection_Start", "__InterfaceDispatchCellSection_End", new DispatchCellComparer(factory))
+        {
+        }
+
+        protected override void GetElementDataForNodes(ref ObjectDataBuilder builder, NodeFactory factory, bool relocsOnly)
+        {
+            if (relocsOnly)
+                return;
+
+            // The interface dispatch cell has an alignment requirement of 2 * [Pointer size] as part of the 
+            // synchronization mechanism of the two values in the runtime.
+            builder.RequireInitialAlignment(factory.Target.PointerSize * 2);
+
+            // This number chosen to be high enough that the cost of recording slot numbers is cheap.
+            const int InterfaceDispatchCellRunLength = 32;
+
+            const int NoSlot = -1;
+
+            //
+            // We emit the individual dispatch cells in groups. The purpose of the grouping is to save
+            // us the number of slots we need to emit. The grouping looks like this:
+            //
+            // DispatchCell1
+            // DispatchCell2
+            // ...
+            // DispatchCellN
+            // Null
+            // Slot of the above dispatch cells
+            //
+            int runLength = 0;
+            int currentSlot = NoSlot;
+            foreach (InterfaceDispatchCellNode node in NodesList)
+            {
+                MethodDesc targetMethod = node.TargetMethod;
+                int targetSlot = VirtualMethodSlotHelper.GetVirtualMethodSlot(factory, targetMethod, targetMethod.OwningType);
+                if (currentSlot == NoSlot)
+                {
+                    // This is the first dispatch cell we're emitting
+                    currentSlot = targetSlot;
+                }
+                else if (currentSlot != targetSlot || runLength == InterfaceDispatchCellRunLength)
+                {
+                    // Make sure we are sorted
+                    Debug.Assert(targetSlot >= currentSlot);
+
+                    // End the run of dispatch cells
+                    builder.EmitZeroPointer();
+                    builder.EmitNaturalInt(currentSlot);
+
+                    currentSlot = targetSlot;
+                    runLength = 0;
+                }
+
+                node.InitializeOffsetFromBeginningOfArray(builder.CountBytes);
+                node.EncodeData(ref builder, factory, relocsOnly);
+                builder.AddSymbol(node);
+
+                runLength++;
+            }
+
+            if (runLength > 0)
+            {
+                // End the run of dispatch cells
+                builder.EmitZeroPointer();
+                builder.EmitNaturalInt(currentSlot);
+            }
+        }
+
+        public override int ClassCode => -1389343;
+
+        /// <summary>
+        /// Comparer that groups interface dispatch cells by their slot number.
+        /// </summary>
+        private class DispatchCellComparer : IComparer<InterfaceDispatchCellNode>
+        {
+            private readonly NodeFactory _factory;
+            private readonly TypeSystemComparer _comparer = new TypeSystemComparer();
+
+            public DispatchCellComparer(NodeFactory factory)
+            {
+                _factory = factory;
+            }
+
+            public int Compare(InterfaceDispatchCellNode x, InterfaceDispatchCellNode y)
+            {
+                MethodDesc methodX = x.TargetMethod;
+                MethodDesc methodY = y.TargetMethod;
+
+                // The primary purpose of this comparer is to sort everything by slot
+                int slotX = VirtualMethodSlotHelper.GetVirtualMethodSlot(_factory, methodX, methodX.OwningType);
+                int slotY = VirtualMethodSlotHelper.GetVirtualMethodSlot(_factory, methodY, methodY.OwningType);
+
+                int result = slotX - slotY;
+                if (result != 0)
+                    return result;
+
+                // If slots are the same, compare the method and callsite identifier to get
+                // a deterministic order within the group.
+                result = _comparer.Compare(methodX, methodY);
+                if (result != 0)
+                    return result;
+
+                result = StringComparer.Ordinal.Compare(x.CallSiteIdentifier, y.CallSiteIdentifier);
+                if (result != 0)
+                    return result;
+
+                Debug.Assert(x == y);
+                return 0;
+            }
+        }
+    }
+}
diff --git a/src/ILCompiler.Compiler/src/Compiler/DependencyAnalysis/NodeFactory.cs b/src/ILCompiler.Compiler/src/Compiler/DependencyAnalysis/NodeFactory.cs
index be26fcd91..d6ecd195c 100644
--- a/src/ILCompiler.Compiler/src/Compiler/DependencyAnalysis/NodeFactory.cs
+++ b/src/ILCompiler.Compiler/src/Compiler/DependencyAnalysis/NodeFactory.cs
@@ -6,7 +6,6 @@ using System;
 using System.Collections.Generic;
 using System.Collections.Concurrent;
 using System.Diagnostics;
-using System.Runtime.InteropServices;
 using System.Text;
 
 using ILCompiler.DependencyAnalysisFramework;
@@ -15,7 +14,6 @@ using Internal.Text;
 using Internal.TypeSystem;
 using Internal.Runtime;
 using Internal.IL;
-using Internal.NativeFormat;
 
 namespace ILCompiler.DependencyAnalysis
 {
@@ -51,6 +49,7 @@ namespace ILCompiler.DependencyAnalysis
             MetadataManager = metadataManager;
             LazyGenericsPolicy = lazyGenericsPolicy;
             _importedNodeProvider = importedNodeProvider;
+            InterfaceDispatchCellSection = new InterfaceDispatchCellSectionNode(this);
         }
 
         public void SetMarkingComplete()
@@ -1018,6 +1017,8 @@ namespace ILCompiler.DependencyAnalysis
             "__ImportTablesTableEnd",
             new SortableDependencyNode.ObjectNodeComparer(new CompilerComparer()));
 
+        public InterfaceDispatchCellSectionNode InterfaceDispatchCellSection { get; }
+
         public ReadyToRunHeaderNode ReadyToRunHeader;
 
         public Dictionary<ISymbolNode, string> NodeAliases = new Dictionary<ISymbolNode, string>();
@@ -1037,6 +1038,7 @@ namespace ILCompiler.DependencyAnalysis
             graph.AddRoot(TypeManagerIndirection, "TypeManagerIndirection is always generated");
             graph.AddRoot(DispatchMapTable, "DispatchMapTable is always generated");
             graph.AddRoot(FrozenSegmentRegion, "FrozenSegmentRegion is always generated");
+            graph.AddRoot(InterfaceDispatchCellSection, "Interface dispatch cell section is always generated");
             if (Target.IsWindows)
             {
                 // We need 2 delimiter symbols to bound the unboxing stubs region on Windows platforms (these symbols are
diff --git a/src/ILCompiler.Compiler/src/Compiler/DependencyAnalysis/UtcNodeFactory.cs b/src/ILCompiler.Compiler/src/Compiler/DependencyAnalysis/UtcNodeFactory.cs
index f9226fe98..ef614be4f 100644
--- a/src/ILCompiler.Compiler/src/Compiler/DependencyAnalysis/UtcNodeFactory.cs
+++ b/src/ILCompiler.Compiler/src/Compiler/DependencyAnalysis/UtcNodeFactory.cs
@@ -159,6 +159,7 @@ namespace ILCompiler
             graph.AddRoot(EagerCctorTable, "EagerCctorTable is always generated");
             graph.AddRoot(DispatchMapTable, "DispatchMapTable is always generated");
             graph.AddRoot(FrozenSegmentRegion, "FrozenSegmentRegion is always generated");
+            graph.AddRoot(InterfaceDispatchCellSection, "Interface dispatch cell section is always generated");
             graph.AddRoot(TypeManagerIndirection, "ModuleManagerIndirection is always generated");
             graph.AddRoot(GCStaticsRegion, "GC StaticsRegion is always generated");
             graph.AddRoot(GCStaticDescRegion, "GC Static Desc is always generated");
diff --git a/src/ILCompiler.Compiler/src/ILCompiler.Compiler.csproj b/src/ILCompiler.Compiler/src/ILCompiler.Compiler.csproj
index 05f3c956f..e42d3a4a4 100644
--- a/src/ILCompiler.Compiler/src/ILCompiler.Compiler.csproj
+++ b/src/ILCompiler.Compiler/src/ILCompiler.Compiler.csproj
@@ -103,6 +103,7 @@
     <Compile Include="Compiler\DependencyAnalysis\ExternSymbolsImportedNodeProvider.cs" />
     <Compile Include="Compiler\DependencyAnalysis\ExternSymbolsWithIndirectionImportedNodeProvider.cs" />
     <Compile Include="Compiler\DependencyAnalysis\IndirectionExtensions.cs" />
+    <Compile Include="Compiler\DependencyAnalysis\InterfaceDispatchCellSectionNode.cs" />
     <Compile Include="Compiler\DependencyAnalysis\MrtImportImportedNodeProvider.cs" />
     <Compile Include="Compiler\DependencyAnalysis\MrtImports.cs" />
     <Compile Include="Compiler\DependencyAnalysis\MrtProcessedExportAddressTableNode.cs" />