Stabilize object file images (#4818)

* Determinism test harness

Add a /determinism mode to runtest.cmd that will invoke ILC twice with different random determinism seeds. This causes graph expansion to be randomized based on seed (though deterministic for a given seed).

* Add Utf8String.CompareTo

Implementation taken from S.P.CoreLib. All the loop unrolling optimizations were excluded; we re-implement them if this function becomes a perf bottleneck.

* Define the mechanisms for determinism

To ensure deterministic output, all nodes that are emitted to the binary are sorted after compilation when retrieving the final marked nodes list. The overall approach is to sort nodes of the same type together (ie, all EETypeNodes come before NonGcStaticsNodes). Within nodes of the same type, a comparison function uses a CompilerComparer to compare the key identifying data of a node. For example, an EETypeNode is defined by a TypeDesc. The CompilerComparer provides a stable comparison function for comparing various type system primitives. Some nodes need to be emitted in an early and specific order for compiler correctness; this is provided by partitioning all sorted nodes into two phases: the first phase containined specifically ordered nodes, and a second phase for all other nodes whose ordering in the output binary doesn't matter.

Add SortableDependencyNode abstract class which provides the sortability layer on top of a DependencyNodeCore. Both ObjectNode and EmbeddedObjectNode derive from SortableDependencyNode to provide sortability across all nodes that are emitted to the output binary.

Introduce `ISortableSymbolNode` to provide sortability for nodes that are currently referred to in the compiler via the ISymbolNode interface. Such nodes are actually `ObjectNode` or `EmbeddedObjectNode` instances that we've lost type information for. Instances that implement `ISortableSymbolNode` redirect to the matching SortableDependencyNode methods.

Add `EmbeddedDataContainerNode` as a base class of `ArrayOfEmbeddedDataNode` to allow comparison of different instantiations.

Refactor the interface dispatch map index calculation so it's done when the dispatch map is emitted at the end of compilation. Previously it was done when the indirection cell in the dispatch map array got marked. This mechanism is incompatible with generating stable dispatch map indices.  The arrays of embedded nodes now stabilize IDs as they emit their final data. This introduces an output ordering dependency - OptionalEETypeNodes must be emitted after the dispatch map since they encode dispatch map indices. Manually enforce this with C++ code generation, since it doesn't emit the real dispatch map structure and builds its own.

Modify InterfaceDispatchMapNode to use the type name in name mangling instead of an index into the dispatch map table.

Modify ObjectDumper to also amit a sha256 hash of each node's data. This dump is used to diff the map files and prove determinism.

* Fill out ordering functions for all nodes

Most of these are not very interesting. Here's the overall approach:

- Every different type of node needs a unique ClassCode. These were generated using Math.Random.
- The various metadata / native layout nodes plus arrays of EmbeddedObjectNodes get placed in the Ordered phase with specific ordering of each.
- All other nodes go in the Unordered phase
- To order nodes of the same type, the data that represents the key for the node in NodeFactory is compared. Ie, for an EEType, that would be its defining TypeDesc, whereas a FrozenStringNode is defined by the string it represents).
- The marked nodes list also contains raw DependencyNodeCore<T> nodes, which aren't emitted. Those are all shuffled after the emitted nodes and not sorted amongst themselves. That hasn't proven to be a problem with determinism and saves a bunch of hopefully unnecessary comparisons.

1 files changed, 1 insertions, 0 deletions

diff --git a/src/BuildIntegration/Microsoft.NETCore.Native.targets b/src/BuildIntegration/Microsoft.NETCore.Native.targets
index 3ad2e68a7..6e522fe48 100644
--- a/src/BuildIntegration/Microsoft.NETCore.Native.targets
+++ b/src/BuildIntegration/Microsoft.NETCore.Native.targets
@@ -106,6 +106,7 @@ See the LICENSE file in the project root for more information.
       <IlcArg Condition="$(IlcMultiModule) == 'true'" Include="--multifile" />
       <IlcArg Condition="$(Optimize) == 'true'" Include="-O" />
       <IlcArg Condition="$(DebugSymbols) == 'true'" Include="-g" />
+      <IlcArg Condition="$(IlcGenerateMapFile) == 'true'" Include="--map:$(NativeIntermediateOutputPath)%(ManagedBinary.Filename).map.xml" />
     </ItemGroup>
 
     <MakeDir Directories="$(NativeIntermediateOutputPath)" />