[DFAJumpThreading] make update order deterministic

[ollef]

Summary

We tracked down some non-determinism in compilation output to the
DFAJumpThreading pass. These changes fixed our issue:

• Make the DefMap type a MapVector to make its iteration order depend on insertion order.
• Sort the values to be inserted into NewDefs by instruction order to make the insertion order deterministic. Since these values come from iterating over a ValueMap, which doesn't have deterministic iteration order, I couldn't fix this at its source.

[alexey.zhikhar]

llvm/lib/Transforms/Scalar/DFAJumpThreading.cpp

1129

Please use SmallVector instead of the STL vector.

1150

Structured binding is a C++17 feature and as far as I know LLVM is still C++14

https://llvm.org/docs/CodingStandards.html#c-standard-versions

[ollef]

Address review comments

• Use SmallVector instead of std::vector.
• Stick to C++14 features (no destructuring bindings).

[alexey.zhikhar]

Thank you @ollef this LGTM

[ollef]

There are some seemingly unrelated failures in the Debian build. How do we handle that?

[alexey.zhikhar]

In D118590#3286616, @ollef wrote:

There are some seemingly unrelated failures in the Debian build. How do we handle that?

I've seen it before, it's unrelated, please ignore

[ollef]

Thanks!

I don't have commit access. Can you help me get this landed? :)

llvm/lib/Transforms/Scalar/DFAJumpThreading.cpp

 
 // This data structure keeps track of all blocks that have been cloned.  If two
 // different ThreadingPaths clone the same block for a certain state it should
 // be reused, and it can be looked up in this map.
 typedef DenseMap<BasicBlock *, CloneList> DuplicateBlockMap;
 
 // This map keeps track of all the new definitions for an instruction. This
 // information is needed when restoring SSA form after cloning blocks.
-typedef DenseMap<Instruction *, std::vector<Instruction *>> DefMap;
+typedef MapVector<Instruction *, std::vector<Instruction *>> DefMap;
 
 inline raw_ostream &operator<<(raw_ostream &OS, const PathType &Path) {
   OS << "< ";
   for (const BasicBlock *BB : Path) {
     std::string BBName;
     if (BB->hasName())
       raw_string_ostream(BBName) << BB->getName();
     else
void updatePredecessor(BasicBlock *PrevBB, BasicBlock *OldBB,
     }
     DTU->applyUpdates({{DominatorTree::Delete, PrevBB, OldBB},
                        {DominatorTree::Insert, PrevBB, NewBB}});
   }
 
   /// Add new value mappings to the DefMap to keep track of all new definitions
   /// for a particular instruction. These will be used while updating SSA form.
   void updateDefMap(DefMap &NewDefs, ValueToValueMapTy &VMap) {
+    SmallVector<std::pair<Instruction *, Instruction *>> NewDefsVector;
+    NewDefsVector.reserve(VMap.size());
+
     for (auto Entry : VMap) {
       Instruction *Inst =
           dyn_cast<Instruction>(const_cast<Value *>(Entry.first));
       if (!Inst || !Entry.second || isa<BranchInst>(Inst) ||
           isa<SwitchInst>(Inst)) {
         continue;
       }
 
       Instruction *Cloned = dyn_cast<Instruction>(Entry.second);
       if (!Cloned)
         continue;
 
-      if (NewDefs.find(Inst) == NewDefs.end())
-        NewDefs[Inst] = {Cloned};
-      else
-        NewDefs[Inst].push_back(Cloned);
+      NewDefsVector.push_back({Inst, Cloned});
     }
+
+    // Sort the defs to get deterministic insertion order into NewDefs.
+    sort(NewDefsVector, [](const auto &LHS, const auto &RHS) {
+      if (LHS.first == RHS.first)
+        return LHS.second->comesBefore(RHS.second);
+      return LHS.first->comesBefore(RHS.first);
+    });
+
+    for (const auto &KV : NewDefsVector)
+      NewDefs[KV.first].push_back(KV.second);
   }
 
   /// Update the last branch of a particular cloned path to point to the correct
   /// case successor.
   ///
   /// Note that this is an optional step and would have been done in later
   /// optimizations, but it makes the CFG significantly easier to work with.
   void updateLastSuccessor(ThreadingPath &TPath,