Avoid nondeterministic ordering of output (#1522)

Most people agree that it is a Good Thing when compilers are deterministic: the exact same input bits produce the exact same output bits every time the compiler is run. Bonus points are awarded if the results are independent of the platform the compiler was compiled for and run on.

One of the easiest kinds of nondeterminism to have sneak into a compiler is for it to produce the "same" code inside functions, but sometimes emits functions or other global symbols in a different order from run to run. Right now, the Slang compiler has some of this kind of nondeterminism.

The main way (but not necessarily the only way) that a compiler ends up producing output with a different ordering across runs is by iterating over the contents of a hash-based container (in our codebase, a `Dictionary` or `HashSet`), where the keys make use of pointers. Most operating systems intentionally try to randomize the address space of processes across runs (as a security feature), so that exact pointer values are not stable across runs, and thus hash value are not stable across runs, and thus the ordering of entries is not stable across runs.

This change identifies a few cases of iterating over dictionaries or sets that could have produced output non-determinism:

* The `HLSLIntrinsicSet` was using a `Dictionary` to store intrinsics that had been referenced, and would later produce a linear list of those intrinsics based on their order in the dictionary.

* The `WitnessTable`s produced by the front-end stored a `Dictionary` or requirements, and lowering from AST->IR was iterating over that dictionary to ensure that everythign got emitted.

* The `SharedSemanticsContext` was tracking a `HashSet` of modules that were imported into scope (so that their `extension`s should be visible), and an iteration over that list was used when producing candidate extensions during lookup. This case is unlikely to cause any nondeterminism in final output, but could lead to nondeterministic ordering in diagnostic messages for ambiguous reference/overload cases.

* The IR linker maintains a `Dictionary` of symbols based on their mangled names, and iterates over it in code that clones all witness tables into the linked IR whether or not they are referenced.

For most of these cases the fix is simple:

* Keep both a `Dictionary`/`HashSet` and a `List` of the appropriate type
* Whenever adding to the hash-based container also add to the list
* Whenever iterating, iterate over the list

In the final case of the IR linker, the relevant code was marked with a `TODO` comment noting that it shouldn't actually be needed, so I simply dropped it and the change doesn't seem to break any of our tests. I've been fairly confident that code wasn't needed for a while.

This change isn't exactly elegant, and a better long term solution might be to introduce two new types, `OrderedDictionary` and `OrderedSet`, which are similar to `Dictionary` and `HashSet` except that they guarantee a deterministic order of enumeration of their contents, based on insertion order.

(Note that a `SortedDictionary` and/or `SortedSet` that use something like a binary tree to produce a "determinsitc" sorted order wouldn't actually help here, because sorting entries by pointer values wouldn't solve the underlying problem that the pointer values aren't stable across runs)

I've chosen to avoid adding new types to `core` in the interest of making the change as small as possible. If we all agree that new types are warranted, it should be easy to clean up these use cases.

Testing this change is difficult, because we can't produce a reliable test to rule out nondeterminism. I have done best-effort testing by hand by crafting shaders that show output nondeterminism, and then compiling them both with and without these changes.

8 files changed, 50 insertions, 36 deletions

diff --git a/source/slang/slang-ast-support-types.h b/source/slang/slang-ast-support-types.h
index 39932ea4e..99ced8187 100644
--- a/source/slang/slang-ast-support-types.h
+++ b/source/slang/slang-ast-support-types.h
@@ -1318,8 +1318,11 @@ namespace Slang
 
     struct WitnessTable : RefObject
     {
+        List<KeyValuePair<Decl*, RequirementWitness>> requirementList;
         RequirementDictionary requirementDictionary;
 
+        void add(Decl* decl, RequirementWitness const& witness);
+
         // The type that the witness table witnesses conformance to (e.g. an Interface)
         Type* baseType;
 
diff --git a/source/slang/slang-check-decl.cpp b/source/slang/slang-check-decl.cpp
index 4fa5fff17..79d9e4bd7 100644
--- a/source/slang/slang-check-decl.cpp
+++ b/source/slang/slang-check-decl.cpp
@@ -1271,7 +1271,7 @@ namespace Slang
 
         // TODO: actually implement matching here. For now we'll
         // just pretend that things are satisfied in order to make progress..
-        witnessTable->requirementDictionary.Add(
+        witnessTable->add(
             requiredMemberDeclRef.getDecl(),
             RequirementWitness(satisfyingMemberDeclRef));
         return true;
@@ -1361,7 +1361,7 @@ namespace Slang
         //
         for( auto p : mapRequiredToSatisfyingAccessorDeclRef )
         {
-            witnessTable->requirementDictionary.Add(
+            witnessTable->add(
                 p.Key,
                 RequirementWitness(p.Value));
         }
@@ -1378,7 +1378,7 @@ namespace Slang
         // represents a witness value that is only needed by the front-end,
         // and that can be ignored by IR and emit logic.
         //
-        witnessTable->requirementDictionary.Add(
+        witnessTable->add(
             requiredMemberDeclRef.getDecl(),
             RequirementWitness(satisfyingMemberDeclRef));
         return true;
@@ -1465,7 +1465,7 @@ namespace Slang
             {
                 // If a subtype witness was found, then the conformance
                 // appears to hold, and we can satisfy that requirement.
-                witnessTable->requirementDictionary.Add(requiredConstraintDeclRef, RequirementWitness(witness));
+                witnessTable->add(requiredConstraintDeclRef, RequirementWitness(witness));
             }
             else
             {
@@ -1482,7 +1482,7 @@ namespace Slang
         {
             // If all the constraints were satisfied, then the chosen
             // type can indeed satisfy the interface requirement.
-            witnessTable->requirementDictionary.Add(
+            witnessTable->add(
                 requiredAssociatedTypeDeclRef.getDecl(),
                 RequirementWitness(satisfyingType));
         }
@@ -1871,7 +1871,7 @@ namespace Slang
         // difference between our synthetic method and a hand-written
         // one with the same behavior.
         //
-        witnessTable->requirementDictionary.Add(requiredMemberDeclRef,
+        witnessTable->add(requiredMemberDeclRef,
             RequirementWitness(makeDeclRef(synFuncDecl)));
         return true;
     }
@@ -2210,9 +2210,9 @@ namespace Slang
         //
         for(auto p : mapRequiredAccessorToSynAccessor)
         {
-            witnessTable->requirementDictionary.Add(p.Key, RequirementWitness(makeDeclRef(p.Value)));
+            witnessTable->add(p.Key, RequirementWitness(makeDeclRef(p.Value)));
         }
-        witnessTable->requirementDictionary.Add(requiredMemberDeclRef,
+        witnessTable->add(requiredMemberDeclRef,
             RequirementWitness(makeDeclRef(synPropertyDecl)));
         return true;
     }
@@ -2319,7 +2319,7 @@ namespace Slang
             if(!satisfyingWitnessTable)
                 return false;
 
-            witnessTable->requirementDictionary.Add(
+            witnessTable->add(
                 requiredInheritanceDeclRef.getDecl(),
                 RequirementWitness(satisfyingWitnessTable));
             return true;
@@ -3047,7 +3047,7 @@ namespace Slang
             }
 
             // Okay, add the conformance witness for `__Tag` being satisfied by `tagType`
-            witnessTable->requirementDictionary.Add(tagAssociatedTypeDecl, RequirementWitness(tagType));
+            witnessTable->add(tagAssociatedTypeDecl, RequirementWitness(tagType));
 
             // TODO: we actually also need to synthesize a witness for the conformance of `tagType`
             // to the `__BuiltinIntegerType` interface, because that is a constraint on the
@@ -4553,12 +4553,15 @@ namespace Slang
     {
         // If we've imported this one already, then
         // skip the step where we modify the current scope.
-        auto& importedModules = getShared()->importedModules;
-        if (importedModules.Contains(moduleDecl))
+        auto& importedModulesList = getShared()->importedModulesList;
+        auto& importedModulesSet = getShared()->importedModulesSet;
+        if (importedModulesSet.Contains(moduleDecl))
         {
             return;
         }
-        importedModules.Add(moduleDecl);
+        importedModulesList.add(moduleDecl);
+        importedModulesSet.Add(moduleDecl);
+
 
 
         // Create a new sub-scope to wire the module
@@ -4746,7 +4749,7 @@ namespace Slang
                 // member on the `SharedSemanticsContext` is accurate in this case.
                 //
                 _addCandidateExtensionsFromModule(m_module->getModuleDecl());
-                for( auto moduleDecl : this->importedModules )
+                for( auto moduleDecl : this->importedModulesList )
                 {
                     _addCandidateExtensionsFromModule(moduleDecl);
                 }
diff --git a/source/slang/slang-check-impl.h b/source/slang/slang-check-impl.h
index a9f861d3d..b3c5e46f9 100644
--- a/source/slang/slang-check-impl.h
+++ b/source/slang/slang-check-impl.h
@@ -211,12 +211,13 @@ namespace Slang
             return m_sink;
         }
 
-        // We need to track what has been `import`ed,
-        // to avoid importing the same thing more than once
+        // We need to track what has been `import`ed into
+        // the scope of this semantic checking session,
+        // and also to avoid importing the same thing more
+        // than once.
         //
-        // TODO: a smarter approach might be to filter
-        // out duplicate references during lookup.
-        HashSet<ModuleDecl*> importedModules;
+        List<ModuleDecl*> importedModulesList;
+        HashSet<ModuleDecl*> importedModulesSet;
 
     public:
         SharedSemanticsContext(
diff --git a/source/slang/slang-hlsl-intrinsic-set.cpp b/source/slang/slang-hlsl-intrinsic-set.cpp
index 27871141d..b73aa4e8e 100644
--- a/source/slang/slang-hlsl-intrinsic-set.cpp
+++ b/source/slang/slang-hlsl-intrinsic-set.cpp
@@ -400,9 +400,9 @@ SlangResult HLSLIntrinsicSet::makeIntrinsic(IRInst* inst, HLSLIntrinsic& out)
 
 void HLSLIntrinsicSet::getIntrinsics(List<const HLSLIntrinsic*>& out) const
 {
-    for (auto& pair : m_intrinsics)
+    for (auto& intrinsic : m_intrinsicsList)
     {
-        out.add(pair.Value);
+        out.add(intrinsic);
     }
 }
 
@@ -414,13 +414,18 @@ HLSLIntrinsic* HLSLIntrinsicSet::add(const HLSLIntrinsic& intrinsic)
     HLSLIntrinsic* copy = (HLSLIntrinsic*)m_intrinsicFreeList.allocate();
     *copy = intrinsic;
     HLSLIntrinsicRef ref(copy);
-    HLSLIntrinsic** found =  m_intrinsics.TryGetValueOrAdd(ref, copy);
+    HLSLIntrinsic** found =  m_intrinsicsDict.TryGetValueOrAdd(ref, copy);
     if (found)
     {
         // If we have found an intrinsic, we can free the copy
         m_intrinsicFreeList.deallocate(copy);
         return *found;
     }
+
+    // If we are adding an intrinsic for the first time,
+    // it should be added to the deduplicated list
+    m_intrinsicsList.add(copy);
+
     return copy;
 }
 
diff --git a/source/slang/slang-hlsl-intrinsic-set.h b/source/slang/slang-hlsl-intrinsic-set.h
index c19ab3a7c..6682e848e 100644
--- a/source/slang/slang-hlsl-intrinsic-set.h
+++ b/source/slang/slang-hlsl-intrinsic-set.h
@@ -215,7 +215,8 @@ protected:
     // NOTE that this function must only be called with unique types (ie from the m_typeSet)
     void _calcIntrinsic(HLSLIntrinsic::Op op, IRType* returnType, IRType*const* inArgs, Index argsCount, HLSLIntrinsic& out);
     
-    Dictionary<HLSLIntrinsicRef, HLSLIntrinsic*> m_intrinsics;
+    List<HLSLIntrinsic*> m_intrinsicsList;
+    Dictionary<HLSLIntrinsicRef, HLSLIntrinsic*> m_intrinsicsDict;
 
     FreeList m_intrinsicFreeList;           ///< the storage for the intrinsics when they are in the map
 
diff --git a/source/slang/slang-ir-link.cpp b/source/slang/slang-ir-link.cpp
index 274fbf6d9..1008c94a1 100644
--- a/source/slang/slang-ir-link.cpp
+++ b/source/slang/slang-ir-link.cpp
@@ -1425,17 +1425,6 @@ LinkedIR linkIR(
 
     context->builder->setInsertInto(context->getModule()->getModuleInst());
 
-    // for now, clone all unreferenced witness tables
-    //
-    // TODO: This step should *not* be needed with the current IR
-    // specialization approach, so we should consider removing it.
-    //
-    for (auto sym : context->getSymbols())
-    {
-        if (sym.Value->irGlobalValue->op == kIROp_WitnessTable)
-            cloneGlobalValue(context, (IRWitnessTable*)sym.Value->irGlobalValue);
-    }
-
     // Next, we make sure to clone the global value for
     // the entry point function itself, and rely on
     // this step to recursively copy over anything else
diff --git a/source/slang/slang-lower-to-ir.cpp b/source/slang/slang-lower-to-ir.cpp
index f7c71adf9..539027e74 100644
--- a/source/slang/slang-lower-to-ir.cpp
+++ b/source/slang/slang-lower-to-ir.cpp
@@ -5170,7 +5170,7 @@ struct DeclLoweringVisitor : DeclVisitor<DeclLoweringVisitor, LoweredValInfo>
     {
         auto subBuilder = subContext->irBuilder;
 
-        for(auto entry : astWitnessTable->requirementDictionary)
+        for(auto entry : astWitnessTable->requirementList)
         {
             auto requiredMemberDecl = entry.Key;
             auto satisfyingWitness = entry.Value;
diff --git a/source/slang/slang-syntax.cpp b/source/slang/slang-syntax.cpp
index aa11b1b0f..ea17ad1d1 100644
--- a/source/slang/slang-syntax.cpp
+++ b/source/slang/slang-syntax.cpp
@@ -322,7 +322,19 @@ Index getFilterCountImpl(const ReflectClassInfo& clsInfo, MemberFilterStyle filt
         return RequirementWitness();
     }
 
-   
+    //
+    // WitnessTable
+    //
+
+    void WitnessTable::add(Decl* decl, RequirementWitness const& witness)
+    {
+        SLANG_ASSERT(!requirementDictionary.ContainsKey(decl));
+
+        requirementDictionary.Add(decl, witness);
+        requirementList.add(KeyValuePair<Decl*, RequirementWitness>(decl, witness));
+    }
+
+    //
 
     static Type* ExtractGenericArgType(Val* val)
     {