[llvm] Convert iterable SmallPtrSet's to SmallSetVector's in Codegen

[mgrang]

Summary

Iteration of SmallPtrSet's are a cause of non-determinism in codegen because
the iteration order is not fixed. This results in different codegen from
run-to-run, release vs release+asserts and on linux vs windows.

The fix is to use SmallSetVector where the iteration order is deterministic.

[vsk]

Thanks for working on this. I have questions about the overhead of this patch and about how to test it. First, what kind of compile-time/memory usage hit should we be willing to take to get this fixed? What happens to compile-time and peak memory consumption of the test suite after applying this patch? Is there a bot somewhere that checks for non-determinism in repeated builds of the test suite?

[mgrang]

Thanks for the comments.

I will run LNT testsuite with and without my patch and post the results.

As for a way to check non-determinism, I guess for we can add a test which compiles the same test multiple times, although I am not sure how reliable/reproducible that will be. But I don't think there is a way to compare codegen of a release toolchain with release+asserts toolchain or linux vs windows toolchains.

[rnk]

I don't think we should have a blanket rule banning iteration of unordered sets. Some of these do look like bugs, though. I think we should probably consider perturbing (maybe randomizing?) iteration order in NDEBUG builds to shake out these kinds of bugs.

lib/CodeGen/CodeGenPrepare.cpp

320–321

This change makes this loop O(n^2), which is not acceptable.

lib/CodeGen/MachineVerifier.cpp

1460–1461

There is a comment here suggesting that iteration order truly doesn't matter.

[mgrang]

Yes, this is an attempt to preempt potential non-determinism caused due to iteration of unordered sets.

If this seems too aggressive then we can take the approach of identifying the exact causes and fixing just those.

Let me spin-off a few test runs on our internal test suite and I will come back with new fix/fixes.

Thanks,
Mandeep

[mgrang]

No longer needed.

include/llvm/CodeGen/LiveRangeEdit.h

private:
   /// FirstNew - Index of the first register added to NewRegs.
   const unsigned FirstNew;
 
   /// ScannedRemattable - true when remattable values have been identified.
   bool ScannedRemattable;
 
   /// DeadRemats - The saved instructions which have already been dead after
   /// rematerialization but not deleted yet -- to be done in postOptimization.
-  SmallPtrSet<MachineInstr *, 32> *DeadRemats;
+  SmallSetVector<MachineInstr *, 32> *DeadRemats;
 
   /// Remattable - Values defined by remattable instructions as identified by
   /// tii.isTriviallyReMaterializable().
   SmallPtrSet<const VNInfo*,4> Remattable;
 
   /// Rematted - Values that were actually rematted, and so need to have their
   /// live range trimmed or entirely removed.
   SmallPtrSet<const VNInfo*,4> Rematted;
public:
   /// @param vrm Map of virtual registers to physical registers for this
   ///            function.  If NULL, no virtual register map updates will
   ///            be done.  This could be the case if called before Regalloc.
   /// @param deadRemats The collection of all the instructions defining an
   ///                   original reg and are dead after remat.
   LiveRangeEdit(LiveInterval *parent, SmallVectorImpl<unsigned> &newRegs,
                 MachineFunction &MF, LiveIntervals &lis, VirtRegMap *vrm,
                 Delegate *delegate = nullptr,
-                SmallPtrSet<MachineInstr *, 32> *deadRemats = nullptr)
+                SmallSetVector<MachineInstr *, 32> *deadRemats = nullptr)
       : Parent(parent), NewRegs(newRegs), MRI(MF.getRegInfo()), LIS(lis),
         VRM(vrm), TII(*MF.getSubtarget().getInstrInfo()), TheDelegate(delegate),
         FirstNew(newRegs.size()), ScannedRemattable(false),
         DeadRemats(deadRemats) {
     MRI.setDelegate(this);
   }
 
   ~LiveRangeEdit() override { MRI.resetDelegate(this); }

lib/CodeGen/CodeGenPrepare.cpp

 // This pass munges the code in the input function to better prepare it for
 // SelectionDAG-based code generation. This works around limitations in it's
 // basic-block-at-a-time approach. It should eventually be removed.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/ProfileSummaryInfo.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
while (MadeChange) {
     }
     EverMadeChange |= MadeChange;
   }
 
   SunkAddrs.clear();
 
   if (!DisableBranchOpts) {
     MadeChange = false;
-    SmallPtrSet<BasicBlock*, 8> WorkList;
+    SmallSetVector<BasicBlock*, 8> WorkList;
     for (BasicBlock &BB : F) {
       SmallVector<BasicBlock *, 2> Successors(succ_begin(&BB), succ_end(&BB));
       MadeChange |= ConstantFoldTerminator(&BB, true);
       if (!MadeChange) continue;
 
       for (SmallVectorImpl<BasicBlock*>::iterator
              II = Successors.begin(), IE = Successors.end(); II != IE; ++II)
         if (pred_begin(*II) == pred_end(*II))
           WorkList.insert(*II);
     }
 
     // Delete the dead blocks and any of their dead successors.
     MadeChange |= !WorkList.empty();
     while (!WorkList.empty()) {
       BasicBlock *BB = *WorkList.begin();
-      WorkList.erase(BB);
+      WorkList.remove(BB);
       SmallVector<BasicBlock*, 2> Successors(succ_begin(BB), succ_end(BB));
 
       DeleteDeadBlock(BB);
 
       for (SmallVectorImpl<BasicBlock*>::iterator
              II = Successors.begin(), IE = Successors.end(); II != IE; ++II)
         if (pred_begin(*II) == pred_end(*II))
           WorkList.insert(*II);

lib/CodeGen/InlineSpiller.cpp

class HoistSpillHelper : private LiveRangeEdit::Delegate {
 
   InsertPointAnalysis IPA;
 
   // Map from StackSlot to its original register.
   DenseMap<int, unsigned> StackSlotToReg;
   // Map from pair of (StackSlot and Original VNI) to a set of spills which
   // have the same stackslot and have equal values defined by Original VNI.
   // These spills are mergeable and are hoist candiates.
-  typedef MapVector<std::pair<int, VNInfo *>, SmallPtrSet<MachineInstr *, 16>>
+  typedef MapVector<std::pair<int, VNInfo *>, SmallSetVector<MachineInstr *, 16>>
       MergeableSpillsMap;
   MergeableSpillsMap MergeableSpills;
 
   /// This is the map from original register to a set containing all its
   /// siblings. To hoist a spill to another BB, we need to find out a live
   /// sibling there and use it as the source of the new spill.
   DenseMap<unsigned, SmallSetVector<unsigned, 16>> Virt2SiblingsMap;
 
   bool isSpillCandBB(unsigned OrigReg, VNInfo &OrigVNI, MachineBasicBlock &BB,
                      unsigned &LiveReg);
 
   void rmRedundantSpills(
-      SmallPtrSet<MachineInstr *, 16> &Spills,
+      SmallSetVector<MachineInstr *, 16> &Spills,
       SmallVectorImpl<MachineInstr *> &SpillsToRm,
       DenseMap<MachineDomTreeNode *, MachineInstr *> &SpillBBToSpill);
 
   void getVisitOrders(
-      MachineBasicBlock *Root, SmallPtrSet<MachineInstr *, 16> &Spills,
+      MachineBasicBlock *Root, SmallSetVector<MachineInstr *, 16> &Spills,
       SmallVectorImpl<MachineDomTreeNode *> &Orders,
       SmallVectorImpl<MachineInstr *> &SpillsToRm,
       DenseMap<MachineDomTreeNode *, unsigned> &SpillsToKeep,
       DenseMap<MachineDomTreeNode *, MachineInstr *> &SpillBBToSpill);
 
   void runHoistSpills(unsigned OrigReg, VNInfo &OrigVNI,
-                      SmallPtrSet<MachineInstr *, 16> &Spills,
+                      SmallSetVector<MachineInstr *, 16> &Spills,
                       SmallVectorImpl<MachineInstr *> &SpillsToRm,
                       DenseMap<MachineBasicBlock *, unsigned> &SpillsToIns);
 
 public:
   HoistSpillHelper(MachineFunctionPass &pass, MachineFunction &mf,
                    VirtRegMap &vrm)
       : MF(mf), LIS(pass.getAnalysis<LiveIntervals>()),
         LSS(pass.getAnalysis<LiveStacks>()),

 bool HoistSpillHelper::rmFromMergeableSpills(MachineInstr &Spill,
                                              int StackSlot) {
   int Original = StackSlotToReg[StackSlot];
   if (!Original)
     return false;
   SlotIndex Idx = LIS.getInstructionIndex(Spill);
   VNInfo *OrigVNI = LIS.getInterval(Original).getVNInfoAt(Idx.getRegSlot());
   std::pair<int, VNInfo *> MIdx = std::make_pair(StackSlot, OrigVNI);
-  return MergeableSpills[MIdx].erase(&Spill);
+  return MergeableSpills[MIdx].remove(&Spill);
 }
 
 /// Check BB to see if it is a possible target BB to place a hoisted spill,
 /// i.e., there should be a living sibling of OrigReg at the insert point.
 ///
 bool HoistSpillHelper::isSpillCandBB(unsigned OrigReg, VNInfo &OrigVNI,
                                      MachineBasicBlock &BB, unsigned &LiveReg) {
   SlotIndex Idx;
bool HoistSpillHelper::isSpillCandBB(unsigned OrigReg, VNInfo &OrigVNI,
   }
   return false;
 }
 
 /// Remove redundant spills in the same BB. Save those redundant spills in
 /// SpillsToRm, and save the spill to keep and its BB in SpillBBToSpill map.
 ///
 void HoistSpillHelper::rmRedundantSpills(
-    SmallPtrSet<MachineInstr *, 16> &Spills,
+    SmallSetVector<MachineInstr *, 16> &Spills,
     SmallVectorImpl<MachineInstr *> &SpillsToRm,
     DenseMap<MachineDomTreeNode *, MachineInstr *> &SpillBBToSpill) {
   // For each spill saw, check SpillBBToSpill[] and see if its BB already has
   // another spill inside. If a BB contains more than one spill, only keep the
   // earlier spill with smaller SlotIndex.
   for (const auto CurrentSpill : Spills) {
     MachineBasicBlock *Block = CurrentSpill->getParent();
     MachineDomTreeNode *Node = MDT.DT->getNode(Block);
     MachineInstr *PrevSpill = SpillBBToSpill[Node];
     if (PrevSpill) {
       SlotIndex PIdx = LIS.getInstructionIndex(*PrevSpill);
       SlotIndex CIdx = LIS.getInstructionIndex(*CurrentSpill);
       MachineInstr *SpillToRm = (CIdx > PIdx) ? CurrentSpill : PrevSpill;
       MachineInstr *SpillToKeep = (CIdx > PIdx) ? PrevSpill : CurrentSpill;
       SpillsToRm.push_back(SpillToRm);
       SpillBBToSpill[MDT.DT->getNode(Block)] = SpillToKeep;
     } else {
       SpillBBToSpill[MDT.DT->getNode(Block)] = CurrentSpill;
     }
   }
   for (const auto SpillToRm : SpillsToRm)
-    Spills.erase(SpillToRm);
+    Spills.remove(SpillToRm);
 }
 
 /// Starting from \p Root find a top-down traversal order of the dominator
 /// tree to visit all basic blocks containing the elements of \p Spills.
 /// Redundant spills will be found and put into \p SpillsToRm at the same
 /// time. \p SpillBBToSpill will be populated as part of the process and
 /// maps a basic block to the first store occurring in the basic block.
 /// \post SpillsToRm.union(Spills\@post) == Spills\@pre
 ///
 void HoistSpillHelper::getVisitOrders(
-    MachineBasicBlock *Root, SmallPtrSet<MachineInstr *, 16> &Spills,
+    MachineBasicBlock *Root, SmallSetVector<MachineInstr *, 16> &Spills,
     SmallVectorImpl<MachineDomTreeNode *> &Orders,
     SmallVectorImpl<MachineInstr *> &SpillsToRm,
     DenseMap<MachineDomTreeNode *, unsigned> &SpillsToKeep,
     DenseMap<MachineDomTreeNode *, MachineInstr *> &SpillBBToSpill) {
   // The set contains all the possible BB nodes to which we may hoist
   // original spills.
   SmallPtrSet<MachineDomTreeNode *, 8> WorkSet;
   // Save the BB nodes on the path from the first BB node containing

 #endif
 }
 
 /// Try to hoist spills according to BB hotness. The spills to removed will
 /// be saved in \p SpillsToRm. The spills to be inserted will be saved in
 /// \p SpillsToIns.
 ///
 void HoistSpillHelper::runHoistSpills(
-    unsigned OrigReg, VNInfo &OrigVNI, SmallPtrSet<MachineInstr *, 16> &Spills,
+    unsigned OrigReg, VNInfo &OrigVNI, SmallSetVector<MachineInstr *, 16> &Spills,
     SmallVectorImpl<MachineInstr *> &SpillsToRm,
     DenseMap<MachineBasicBlock *, unsigned> &SpillsToIns) {
   // Visit order of dominator tree nodes.
   SmallVector<MachineDomTreeNode *, 32> Orders;
   // SpillsToKeep contains all the nodes where spills are to be inserted
   // during hoisting. If the spill to be inserted is an original spill
   // (not a hoisted one), the value of the map entry is 0. If the spill
   // is a hoisted spill, the value of the map entry is the VReg to be used
void HoistSpillHelper::hoistAllSpills() {
   }
 
   // Each entry in MergeableSpills contains a spill set with equal values.
   for (auto &Ent : MergeableSpills) {
     int Slot = Ent.first.first;
     unsigned OrigReg = SlotToOrigReg[Slot];
     LiveInterval &OrigLI = LIS.getInterval(OrigReg);
     VNInfo *OrigVNI = Ent.first.second;
-    SmallPtrSet<MachineInstr *, 16> &EqValSpills = Ent.second;
+    SmallSetVector<MachineInstr *, 16> &EqValSpills = Ent.second;
     if (Ent.second.empty())
       continue;
 
     DEBUG({
       dbgs() << "\nFor Slot" << Slot << " and VN" << OrigVNI->id << ":\n"
              << "Equal spills in BB: ";
       for (const auto spill : EqValSpills)
         dbgs() << spill->getParent()->getNumber() << " ";

lib/CodeGen/MachineBlockPlacement.cpp

void MachineBlockPlacement::buildCFGChains() {
   SmallPtrSet<BlockChain *, 4> UpdatedPreds;
   for (MachineBasicBlock &MBB : *F)
     fillWorkLists(&MBB, UpdatedPreds);
 
   BlockChain &FunctionChain = *BlockToChain[&F->front()];
   buildChain(&F->front(), FunctionChain);
 
 #ifndef NDEBUG
-  typedef SmallPtrSet<MachineBasicBlock *, 16> FunctionBlockSetType;
+  typedef SmallSetVector<MachineBasicBlock *, 16> FunctionBlockSetType;
 #endif
   DEBUG({
     // Crash at the end so we get all of the debugging output first.
     bool BadFunc = false;
     FunctionBlockSetType FunctionBlockSet;
     for (MachineBasicBlock &MBB : *F)
       FunctionBlockSet.insert(&MBB);
 
     for (MachineBasicBlock *ChainBB : FunctionChain)
-      if (!FunctionBlockSet.erase(ChainBB)) {
+      if (!FunctionBlockSet.remove(ChainBB)) {
         BadFunc = true;
         dbgs() << "Function chain contains a block not in the function!\n"
                << "  Bad block:    " << getBlockName(ChainBB) << "\n";
       }
 
     if (!FunctionBlockSet.empty()) {
       BadFunc = true;
       for (MachineBasicBlock *RemainingBB : FunctionBlockSet)

lib/CodeGen/MachinePipeliner.cpp

class SwingSchedulerDAG : public ScheduleDAGInstrs {
   typedef SmallVectorImpl<MachineBasicBlock *> MBBVectorTy;
   typedef DenseMap<MachineInstr *, MachineInstr *> InstrMapTy;
 
   /// Instructions to change when emitting the final schedule.
   DenseMap<SUnit *, std::pair<unsigned, int64_t>> InstrChanges;
 
   /// We may create a new instruction, so remember it because it
   /// must be deleted when the pass is finished.
-  SmallPtrSet<MachineInstr *, 4> NewMIs;
+  SmallSetVector<MachineInstr *, 4> NewMIs;
 
   /// Helper class to implement Johnson's circuit finding algorithm.
   class Circuits {
     std::vector<SUnit> &SUnits;
     SetVector<SUnit *> Stack;
     BitVector Blocked;
-    SmallVector<SmallPtrSet<SUnit *, 4>, 10> B;
+    SmallVector<SmallSetVector<SUnit *, 4>, 10> B;
     SmallVector<SmallVector<int, 4>, 16> AdjK;
     unsigned NumPaths;
     static unsigned MaxPaths;
 
   public:
     Circuits(std::vector<SUnit> &SUs)
         : SUnits(SUs), Stack(), Blocked(SUs.size()), B(SUs.size()),
           AdjK(SUs.size()) {}
     /// Reset the data structures used in the circuit algorithm.
     void reset() {
       Stack.clear();
       Blocked.reset();
-      B.assign(SUnits.size(), SmallPtrSet<SUnit *, 4>());
+      B.assign(SUnits.size(), SmallSetVector<SUnit *, 4>());
       NumPaths = 0;
     }
     void createAdjacencyStructure(SwingSchedulerDAG *DAG);
     bool circuit(int V, int S, NodeSetType &NodeSets, bool HasBackedge = false);
     void unblock(int U);
   };
 
 public:
bool SwingSchedulerDAG::Circuits::circuit(int V, int S, NodeSetType &NodeSets,
   }
   Stack.pop_back();
   return F;
 }
 
 /// Unblock a node in the circuit finding algorithm.
 void SwingSchedulerDAG::Circuits::unblock(int U) {
   Blocked.reset(U);
-  SmallPtrSet<SUnit *, 4> &BU = B[U];
+  SmallSetVector<SUnit *, 4> &BU = B[U];
   while (!BU.empty()) {
-    SmallPtrSet<SUnit *, 4>::iterator SI = BU.begin();
+    SmallSetVector<SUnit *, 4>::iterator SI = BU.begin();
     assert(SI != BU.end() && "Invalid B set.");
     SUnit *W = *SI;
-    BU.erase(W);
+    BU.remove(W);
     if (Blocked.test(W->NodeNum))
       unblock(W->NodeNum);
   }
 }
 
 /// Identify all the elementary circuits in the dependence graph using
 /// Johnson's circuit algorithm.
 void SwingSchedulerDAG::findCircuits(NodeSetType &NodeSets) {

lib/CodeGen/MachineVerifier.cpp

 // variable LLVM_VERIFY_MACHINEINSTRS to the name of a file that will receive
 // the verifier errors.
 //===----------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/SetOperations.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/EHPersonalities.h"
 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
 #include "llvm/CodeGen/LiveStackAnalysis.h"
 #include "llvm/CodeGen/LiveVariables.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineMemOperand.h"

 }
 
 // Calculate the largest possible vregsPassed sets. These are the registers that
 // can pass through an MBB live, but may not be live every time. It is assumed
 // that all vregsPassed sets are empty before the call.
 void MachineVerifier::calcRegsPassed() {
   // First push live-out regs to successors' vregsPassed. Remember the MBBs that
   // have any vregsPassed.
-  SmallPtrSet<const MachineBasicBlock*, 8> todo;
+  SmallSetVector<const MachineBasicBlock*, 8> todo;
   for (const auto &MBB : *MF) {
     BBInfo &MInfo = MBBInfoMap[&MBB];
     if (!MInfo.reachable)
       continue;
     for (MachineBasicBlock::const_succ_iterator SuI = MBB.succ_begin(),
            SuE = MBB.succ_end(); SuI != SuE; ++SuI) {
       BBInfo &SInfo = MBBInfoMap[*SuI];
       if (SInfo.addPassed(MInfo.regsLiveOut))
         todo.insert(*SuI);
     }
   }
 
   // Iteratively push vregsPassed to successors. This will converge to the same
   // final state regardless of DenseSet iteration order.
   while (!todo.empty()) {
     const MachineBasicBlock *MBB = *todo.begin();
-    todo.erase(MBB);
+    todo.remove(MBB);
     BBInfo &MInfo = MBBInfoMap[MBB];
     for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
            SuE = MBB->succ_end(); SuI != SuE; ++SuI) {
       if (*SuI == MBB)
         continue;
       BBInfo &SInfo = MBBInfoMap[*SuI];
       if (SInfo.addPassed(MInfo.vregsPassed))
         todo.insert(*SuI);
     }
   }
 }
 
 // Calculate the set of virtual registers that must be passed through each basic
 // block in order to satisfy the requirements of successor blocks. This is very
 // similar to calcRegsPassed, only backwards.
 void MachineVerifier::calcRegsRequired() {
   // First push live-in regs to predecessors' vregsRequired.
-  SmallPtrSet<const MachineBasicBlock*, 8> todo;
+  SmallSetVector<const MachineBasicBlock*, 8> todo;
   for (const auto &MBB : *MF) {
     BBInfo &MInfo = MBBInfoMap[&MBB];
     for (MachineBasicBlock::const_pred_iterator PrI = MBB.pred_begin(),
            PrE = MBB.pred_end(); PrI != PrE; ++PrI) {
       BBInfo &PInfo = MBBInfoMap[*PrI];
       if (PInfo.addRequired(MInfo.vregsLiveIn))
         todo.insert(*PrI);
     }
   }
 
   // Iteratively push vregsRequired to predecessors. This will converge to the
   // same final state regardless of DenseSet iteration order.
   while (!todo.empty()) {
     const MachineBasicBlock *MBB = *todo.begin();
-    todo.erase(MBB);
+    todo.remove(MBB);
     BBInfo &MInfo = MBBInfoMap[MBB];
     for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
            PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
       if (*PrI == MBB)
         continue;
       BBInfo &SInfo = MBBInfoMap[*PrI];
       if (SInfo.addRequired(MInfo.vregsRequired))
         todo.insert(*PrI);

lib/CodeGen/OptimizePHIs.cpp

 //===-- OptimizePHIs.cpp - Optimize machine instruction PHIs --------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This pass optimizes machine instruction PHIs to take advantage of
 // opportunities created during DAG legalization.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/Passes.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/IR/Function.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetSubtargetInfo.h"
public:
     bool runOnMachineFunction(MachineFunction &MF) override;
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.setPreservesCFG();
       MachineFunctionPass::getAnalysisUsage(AU);
     }
 
   private:
-    typedef SmallPtrSet<MachineInstr*, 16> InstrSet;
-    typedef SmallPtrSetIterator<MachineInstr*> InstrSetIterator;
+    typedef SmallSetVector<MachineInstr*, 16> InstrSet;
+    typedef SmallSetVector<MachineInstr*, 16>::iterator InstrSetIterator;
 
     bool IsSingleValuePHICycle(MachineInstr *MI, unsigned &SingleValReg,
                                InstrSet &PHIsInCycle);
     bool IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle);
     bool OptimizeBB(MachineBasicBlock &MBB);
   };
 }
 

 /// have been scanned.
 bool OptimizePHIs::IsSingleValuePHICycle(MachineInstr *MI,
                                          unsigned &SingleValReg,
                                          InstrSet &PHIsInCycle) {
   assert(MI->isPHI() && "IsSingleValuePHICycle expects a PHI instruction");
   unsigned DstReg = MI->getOperand(0).getReg();
 
   // See if we already saw this register.
-  if (!PHIsInCycle.insert(MI).second)
+  if (!PHIsInCycle.insert(MI))
     return true;
 
   // Don't scan crazily complex things.
   if (PHIsInCycle.size() == 16)
     return false;
 
   // Scan the PHI operands.
   for (unsigned i = 1; i != MI->getNumOperands(); i += 2) {

 /// other PHIs in a cycle.
 bool OptimizePHIs::IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle) {
   assert(MI->isPHI() && "IsDeadPHICycle expects a PHI instruction");
   unsigned DstReg = MI->getOperand(0).getReg();
   assert(TargetRegisterInfo::isVirtualRegister(DstReg) &&
          "PHI destination is not a virtual register");
 
   // See if we already saw this register.
-  if (!PHIsInCycle.insert(MI).second)
+  if (!PHIsInCycle.insert(MI))
     return true;
 
   // Don't scan crazily complex things.
   if (PHIsInCycle.size() == 16)
     return false;
 
   for (MachineInstr &UseMI : MRI->use_instructions(DstReg)) {
     if (!UseMI.isPHI() || !IsDeadPHICycle(&UseMI, PHIsInCycle))

lib/CodeGen/PHIElimination.cpp

 // This pass eliminates machine instruction PHI nodes by inserting copy
 // instructions.  This destroys SSA information, but is the desired input for
 // some register allocators.
 //
 //===----------------------------------------------------------------------===//
 
 #include "PHIEliminationUtils.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
 #include "llvm/CodeGen/LiveVariables.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
private:
     bool isLiveOutPastPHIs(unsigned Reg, const MachineBasicBlock *MBB);
 
     typedef std::pair<unsigned, unsigned> BBVRegPair;
     typedef DenseMap<BBVRegPair, unsigned> VRegPHIUse;
 
     VRegPHIUse VRegPHIUseCount;
 
     // Defs of PHI sources which are implicit_def.
-    SmallPtrSet<MachineInstr*, 4> ImpDefs;
+    SmallSetVector<MachineInstr*, 4> ImpDefs;
 
     // Map reusable lowered PHI node -> incoming join register.
     typedef DenseMap<MachineInstr*, unsigned,
                      MachineInstrExpressionTrait> LoweredPHIMap;
     LoweredPHIMap LoweredPHIs;
   };
 }
 

lib/CodeGen/PrologEpilogInserter.cpp

static void updateLiveness(MachineFunction &MF) {
   MachineFrameInfo &MFI = MF.getFrameInfo();
   // Visited will contain all the basic blocks that are in the region
   // where the callee saved registers are alive:
   // - Anything that is not Save or Restore -> LiveThrough.
   // - Save -> LiveIn.
   // - Restore -> LiveOut.
   // The live-out is not attached to the block, so no need to keep
   // Restore in this set.
-  SmallPtrSet<MachineBasicBlock *, 8> Visited;
+  SmallSetVector<MachineBasicBlock *, 8> Visited;
   SmallVector<MachineBasicBlock *, 8> WorkList;
   MachineBasicBlock *Entry = &MF.front();
   MachineBasicBlock *Save = MFI.getSavePoint();
 
   if (!Save)
     Save = Entry;
 
   if (Entry != Save) {
while (!WorkList.empty()) {
     const MachineBasicBlock *CurBB = WorkList.pop_back_val();
     // By construction, the region that is after the save point is
     // dominated by the Save and post-dominated by the Restore.
     if (CurBB == Save && Save != Restore)
       continue;
     // Enqueue all the successors not already visited.
     // Those are by construction either before Save or after Restore.
     for (MachineBasicBlock *SuccBB : CurBB->successors())
-      if (Visited.insert(SuccBB).second)
+      if (Visited.insert(SuccBB))
         WorkList.push_back(SuccBB);
   }
 
   const std::vector<CalleeSavedInfo> &CSI = MFI.getCalleeSavedInfo();
 
   for (unsigned i = 0, e = CSI.size(); i != e; ++i) {
     for (MachineBasicBlock *MBB : Visited) {
       MCPhysReg Reg = CSI[i].getReg();

lib/CodeGen/RegAllocBase.h

 // This framework provides a way to engineer the compile time vs. code
 // quality trade-off without relying on a particular theoretical solver.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_LIB_CODEGEN_REGALLOCBASE_H
 #define LLVM_LIB_CODEGEN_REGALLOCBASE_H
 
+#include "llvm/ADT/SetVector.h"
 #include "llvm/CodeGen/LiveInterval.h"
 #include "llvm/CodeGen/RegisterClassInfo.h"
 
 namespace llvm {
 
 template<typename T> class SmallVectorImpl;
 class TargetRegisterInfo;
 class VirtRegMap;
protected:
   LiveIntervals *LIS;
   LiveRegMatrix *Matrix;
   RegisterClassInfo RegClassInfo;
 
   /// Inst which is a def of an original reg and whose defs are already all
   /// dead after remat is saved in DeadRemats. The deletion of such inst is
   /// postponed till all the allocations are done, so its remat expr is
   /// always available for the remat of all the siblings of the original reg.
-  SmallPtrSet<MachineInstr *, 32> DeadRemats;
+  SmallSetVector<MachineInstr *, 32> DeadRemats;
 
   RegAllocBase()
     : TRI(nullptr), MRI(nullptr), VRM(nullptr), LIS(nullptr), Matrix(nullptr) {}
 
   virtual ~RegAllocBase() {}
 
   // A RegAlloc pass should call this before allocatePhysRegs.
   void init(VirtRegMap &vrm, LiveIntervals &lis, LiveRegMatrix &mat);

lib/CodeGen/RegAllocGreedy.cpp

static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator",
                                        createGreedyRegisterAllocator);
 
 namespace {
 class RAGreedy : public MachineFunctionPass,
                  public RegAllocBase,
                  private LiveRangeEdit::Delegate {
   // Convenient shortcuts.
   typedef std::priority_queue<std::pair<unsigned, unsigned> > PQueue;
-  typedef SmallPtrSet<LiveInterval *, 4> SmallLISet;
+  typedef SmallSetVector<LiveInterval *, 4> SmallLISet;
   typedef SmallSet<unsigned, 16> SmallVirtRegSet;
 
   // context
   MachineFunction *MF;
 
   // Shortcuts to some useful interface.
   const TargetInstrInfo *TII;
   const TargetRegisterInfo *TRI;

lib/CodeGen/RegAllocPBQP.cpp

private:
   char *customPassID;
 
   RegSet VRegsToAlloc, EmptyIntervalVRegs;
 
   /// Inst which is a def of an original reg and whose defs are already all
   /// dead after remat is saved in DeadRemats. The deletion of such inst is
   /// postponed till all the allocations are done, so its remat expr is
   /// always available for the remat of all the siblings of the original reg.
-  SmallPtrSet<MachineInstr *, 32> DeadRemats;
+  SmallSetVector<MachineInstr *, 32> DeadRemats;
 
   /// \brief Finds the initial set of vreg intervals to allocate.
   void findVRegIntervalsToAlloc(const MachineFunction &MF, LiveIntervals &LIS);
 
   /// \brief Constructs an initial graph.
   void initializeGraph(PBQPRAGraph &G, VirtRegMap &VRM, Spiller &VRegSpiller);
 
   /// \brief Spill the given VReg.

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
 
   // Start the morphing.
   N->NodeType = Opc;
   N->ValueList = VTs.VTs;
   N->NumValues = VTs.NumVTs;
 
   // Clear the operands list, updating used nodes to remove this from their
   // use list.  Keep track of any operands that become dead as a result.
-  SmallPtrSet<SDNode*, 16> DeadNodeSet;
+  SmallSetVector<SDNode*, 16> DeadNodeSet;
   for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
     SDUse &Use = *I++;
     SDNode *Used = Use.getNode();
     Use.set(SDValue());
     if (Used->use_empty())
       DeadNodeSet.insert(Used);
   }
 

lib/CodeGen/SjLjEHPrepare.cpp

void SjLjEHPrepare::lowerAcrossUnwindEdges(Function &F,
   }
 
   // Go through the landing pads and remove any PHIs there.
   for (InvokeInst *Invoke : Invokes) {
     BasicBlock *UnwindBlock = Invoke->getUnwindDest();
     LandingPadInst *LPI = UnwindBlock->getLandingPadInst();
 
     // Place PHIs into a set to avoid invalidating the iterator.
-    SmallPtrSet<PHINode *, 8> PHIsToDemote;
+    SmallSetVector<PHINode *, 8> PHIsToDemote;
     for (BasicBlock::iterator PN = UnwindBlock->begin(); isa<PHINode>(PN); ++PN)
       PHIsToDemote.insert(cast<PHINode>(PN));
     if (PHIsToDemote.empty())
       continue;
 
     // Demote the PHIs to the stack.
     for (PHINode *PN : PHIsToDemote)
       DemotePHIToStack(PN);

lib/CodeGen/SplitKit.cpp

for (;;) {
     MBB = IDom->getBlock();
   }
 }
 
 void SplitEditor::computeRedundantBackCopies(
     DenseSet<unsigned> &NotToHoistSet, SmallVectorImpl<VNInfo *> &BackCopies) {
   LiveInterval *LI = &LIS.getInterval(Edit->get(0));
   LiveInterval *Parent = &Edit->getParent();
-  SmallVector<SmallPtrSet<VNInfo *, 8>, 8> EqualVNs(Parent->getNumValNums());
-  SmallPtrSet<VNInfo *, 8> DominatedVNIs;
+  SmallVector<SmallSetVector<VNInfo *, 8>, 8> EqualVNs(Parent->getNumValNums());
+  SmallSetVector<VNInfo *, 8> DominatedVNIs;
 
   // Aggregate VNIs having the same value as ParentVNI.
   for (VNInfo *VNI : LI->valnos) {
     if (VNI->isUnused())
       continue;
     VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
     EqualVNs[ParentVNI->id].insert(VNI);
   }
 
   // For VNI aggregation of each ParentVNI, collect dominated, i.e.,
   // redundant VNIs to BackCopies.
   for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) {
     VNInfo *ParentVNI = Parent->getValNumInfo(i);
     if (!NotToHoistSet.count(ParentVNI->id))
       continue;
-    SmallPtrSetIterator<VNInfo *> It1 = EqualVNs[ParentVNI->id].begin();
-    SmallPtrSetIterator<VNInfo *> It2 = It1;
+    SmallSetVector<VNInfo *, 8>::iterator It1 = EqualVNs[ParentVNI->id].begin();
+    SmallSetVector<VNInfo *, 8>::iterator It2 = It1;
     for (; It1 != EqualVNs[ParentVNI->id].end(); ++It1) {
       It2 = It1;
       for (++It2; It2 != EqualVNs[ParentVNI->id].end(); ++It2) {
         if (DominatedVNIs.count(*It1) || DominatedVNIs.count(*It2))
           continue;
 
         MachineBasicBlock *MBB1 = LIS.getMBBFromIndex((*It1)->def);
         MachineBasicBlock *MBB2 = LIS.getMBBFromIndex((*It2)->def);