[ConstantHoisting] Fix non-determinism.

[mgrang]

Have you tried measuring compile-time on some benchmark with this patch. Changing unordered containers to ordered ones can increase compile-time. What if you simply sort the containers before iteration?

[efriedma]

The keys are subclasses of llvm::Value, so sorting is hard. There's no obvious comparator to sort global variables. Instructions and basic blocks could be sorted based on DFS numbers, or something like that, but it would be a lot more complicated.

Looking again, a couple of these might not actually need to be ordered; in particular, BBs, and ConstCandMap. I'll spend a bit more time to try and verify that.

[efriedma]

Got rid of a few changes that were clearly unnecessary, because we never iterated over the maps in question.

It's possible there are more lightweight solutions in a few of these cases. But anything that affects the order of the modifications performed by ConstantHoisting affects the use lists, at the very least, and the algorithms mostly don't impose any sort of natural ordering.

[mgrang]

LGTM.

llvm/trunk/include/llvm/Transforms/Scalar/ConstantHoisting.h

 // %0 = load i64* inttoptr (i64 big_constant to i64*)
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H
 #define LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H
 
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/PointerUnion.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/IR/PassManager.h"
 #include <algorithm>
 #include <vector>
 
 namespace llvm {
 
private:
   BlockFrequencyInfo *BFI;
   LLVMContext *Ctx;
   const DataLayout *DL;
   BasicBlock *Entry;
   ProfileSummaryInfo *PSI;
 
   /// Keeps track of constant candidates found in the function.
   using ConstCandVecType = std::vector<consthoist::ConstantCandidate>;
-  using GVCandVecMapType = DenseMap<GlobalVariable *, ConstCandVecType>;
+  using GVCandVecMapType = MapVector<GlobalVariable *, ConstCandVecType>;
   ConstCandVecType ConstIntCandVec;
   GVCandVecMapType ConstGEPCandMap;
 
   /// These are the final constants we decided to hoist.
   using ConstInfoVecType = SmallVector<consthoist::ConstantInfo, 8>;
-  using GVInfoVecMapType = DenseMap<GlobalVariable *, ConstInfoVecType>;
+  using GVInfoVecMapType = MapVector<GlobalVariable *, ConstInfoVecType>;
   ConstInfoVecType ConstIntInfoVec;
   GVInfoVecMapType ConstGEPInfoMap;
 
   /// Keep track of cast instructions we already cloned.
-  SmallDenseMap<Instruction *, Instruction *> ClonedCastMap;
+  MapVector<Instruction *, Instruction *> ClonedCastMap;
 
   Instruction *findMatInsertPt(Instruction *Inst, unsigned Idx = ~0U) const;
-  SmallPtrSet<Instruction *, 8>
+  SetVector<Instruction *>
   findConstantInsertionPoint(const consthoist::ConstantInfo &ConstInfo) const;
   void collectConstantCandidates(ConstCandMapType &ConstCandMap,
                                  Instruction *Inst, unsigned Idx,
                                  ConstantInt *ConstInt);
   void collectConstantCandidates(ConstCandMapType &ConstCandMap,
                                  Instruction *Inst, unsigned Idx,
                                  ConstantExpr *ConstExpr);
   void collectConstantCandidates(ConstCandMapType &ConstCandMap,

llvm/trunk/lib/Transforms/Scalar/ConstantHoisting.cpp

Instruction *ConstantHoistingPass::findMatInsertPt(Instruction *Inst,
   return IDom->getBlock()->getTerminator();
 }
 
 /// Given \p BBs as input, find another set of BBs which collectively
 /// dominates \p BBs and have the minimal sum of frequencies. Return the BB
 /// set found in \p BBs.
 static void findBestInsertionSet(DominatorTree &DT, BlockFrequencyInfo &BFI,
                                  BasicBlock *Entry,
-                                 SmallPtrSet<BasicBlock *, 8> &BBs) {
+                                 SetVector<BasicBlock *> &BBs) {
   assert(!BBs.count(Entry) && "Assume Entry is not in BBs");
   // Nodes on the current path to the root.
   SmallPtrSet<BasicBlock *, 8> Path;
   // Candidates includes any block 'BB' in set 'BBs' that is not strictly
   // dominated by any other blocks in set 'BBs', and all nodes in the path
   // in the dominator tree from Entry to 'BB'.
   SmallPtrSet<BasicBlock *, 16> Candidates;
   for (auto BB : BBs) {
while (Idx != Orders.size()) {
     for (auto ChildDomNode : DT.getNode(Node)->getChildren()) {
       if (Candidates.count(ChildDomNode->getBlock()))
         Orders.push_back(ChildDomNode->getBlock());
     }
   }
 
   // Visit Orders in bottom-up order.
   using InsertPtsCostPair =
-      std::pair<SmallPtrSet<BasicBlock *, 16>, BlockFrequency>;
+      std::pair<SetVector<BasicBlock *>, BlockFrequency>;
 
   // InsertPtsMap is a map from a BB to the best insertion points for the
   // subtree of BB (subtree not including the BB itself).
   DenseMap<BasicBlock *, InsertPtsCostPair> InsertPtsMap;
   InsertPtsMap.reserve(Orders.size() + 1);
   for (auto RIt = Orders.rbegin(); RIt != Orders.rend(); RIt++) {
     BasicBlock *Node = *RIt;
     bool NodeInBBs = BBs.count(Node);
-    SmallPtrSet<BasicBlock *, 16> &InsertPts = InsertPtsMap[Node].first;
+    auto &InsertPts = InsertPtsMap[Node].first;
     BlockFrequency &InsertPtsFreq = InsertPtsMap[Node].second;
 
     // Return the optimal insert points in BBs.
     if (Node == Entry) {
       BBs.clear();
       if (InsertPtsFreq > BFI.getBlockFreq(Node) ||
           (InsertPtsFreq == BFI.getBlockFreq(Node) && InsertPts.size() > 1))
         BBs.insert(Entry);
       else
         BBs.insert(InsertPts.begin(), InsertPts.end());
       break;
     }
 
     BasicBlock *Parent = DT.getNode(Node)->getIDom()->getBlock();
     // Initially, ParentInsertPts is empty and ParentPtsFreq is 0. Every child
     // will update its parent's ParentInsertPts and ParentPtsFreq.
-    SmallPtrSet<BasicBlock *, 16> &ParentInsertPts = InsertPtsMap[Parent].first;
+    auto &ParentInsertPts = InsertPtsMap[Parent].first;
     BlockFrequency &ParentPtsFreq = InsertPtsMap[Parent].second;
     // Choose to insert in Node or in subtree of Node.
     // Don't hoist to EHPad because we may not find a proper place to insert
     // in EHPad.
     // If the total frequency of InsertPts is the same as the frequency of the
     // target Node, and InsertPts contains more than one nodes, choose hoisting
     // to reduce code size.
     if (NodeInBBs ||
         (!Node->isEHPad() &&
          (InsertPtsFreq > BFI.getBlockFreq(Node) ||
           (InsertPtsFreq == BFI.getBlockFreq(Node) && InsertPts.size() > 1)))) {
       ParentInsertPts.insert(Node);
       ParentPtsFreq += BFI.getBlockFreq(Node);
     } else {
       ParentInsertPts.insert(InsertPts.begin(), InsertPts.end());
       ParentPtsFreq += InsertPtsFreq;
     }
   }
 }
 
 /// Find an insertion point that dominates all uses.
-SmallPtrSet<Instruction *, 8> ConstantHoistingPass::findConstantInsertionPoint(
+SetVector<Instruction *> ConstantHoistingPass::findConstantInsertionPoint(
     const ConstantInfo &ConstInfo) const {
   assert(!ConstInfo.RebasedConstants.empty() && "Invalid constant info entry.");
   // Collect all basic blocks.
-  SmallPtrSet<BasicBlock *, 8> BBs;
-  SmallPtrSet<Instruction *, 8> InsertPts;
+  SetVector<BasicBlock *> BBs;
+  SetVector<Instruction *> InsertPts;
   for (auto const &RCI : ConstInfo.RebasedConstants)
     for (auto const &U : RCI.Uses)
       BBs.insert(findMatInsertPt(U.Inst, U.OpndIdx)->getParent());
 
   if (BBs.count(Entry)) {
     InsertPts.insert(&Entry->front());
     return InsertPts;
   }
 
   if (BFI) {
     findBestInsertionSet(*DT, *BFI, Entry, BBs);
     for (auto BB : BBs) {
       BasicBlock::iterator InsertPt = BB->begin();
       for (; isa<PHINode>(InsertPt) || InsertPt->isEHPad(); ++InsertPt)
         ;
       InsertPts.insert(&*InsertPt);
     }
     return InsertPts;
   }
 
   while (BBs.size() >= 2) {
     BasicBlock *BB, *BB1, *BB2;
-    BB1 = *BBs.begin();
-    BB2 = *std::next(BBs.begin());
+    BB1 = BBs.pop_back_val();
+    BB2 = BBs.pop_back_val();
     BB = DT->findNearestCommonDominator(BB1, BB2);
     if (BB == Entry) {
       InsertPts.insert(&Entry->front());
       return InsertPts;
     }
-    BBs.erase(BB1);
-    BBs.erase(BB2);
     BBs.insert(BB);
   }
   assert((BBs.size() == 1) && "Expected only one element.");
   Instruction &FirstInst = (*BBs.begin())->front();
   InsertPts.insert(findMatInsertPt(&FirstInst));
   return InsertPts;
 }
 

 
 /// Hoist and hide the base constant behind a bitcast and emit
 /// materialization code for derived constants.
 bool ConstantHoistingPass::emitBaseConstants(GlobalVariable *BaseGV) {
   bool MadeChange = false;
   SmallVectorImpl<consthoist::ConstantInfo> &ConstInfoVec =
       BaseGV ? ConstGEPInfoMap[BaseGV] : ConstIntInfoVec;
   for (auto const &ConstInfo : ConstInfoVec) {
-    SmallPtrSet<Instruction *, 8> IPSet = findConstantInsertionPoint(ConstInfo);
+    SetVector<Instruction *> IPSet = findConstantInsertionPoint(ConstInfo);
     // We can have an empty set if the function contains unreachable blocks.
     if (IPSet.empty())
       continue;
 
     unsigned UsesNum = 0;
     unsigned ReBasesNum = 0;
     unsigned NotRebasedNum = 0;
     for (Instruction *IP : IPSet) {