Avoid overly large SmallPtrSet/SmallSet

[MatzeB]

Summary

These sets perform linear searching in small mode so it is never a good
idea to use SmallSize/N bigger than 32.

[echristo]

LGTM.

-eric

[MatzeB]

Committed in r259283, thanks for the review!

include/llvm/Analysis/DemandedBits.h

void determineLiveOperandBits(const Instruction *UserI,
                                 APInt &KnownZero2, APInt &KnownOne2);
 
   AssumptionCache *AC;
   DominatorTree *DT;
   Function *F;
   bool Analyzed;
 
   // The set of visited instructions (non-integer-typed only).
-  SmallPtrSet<Instruction*, 128> Visited;
+  SmallPtrSet<Instruction*, 32> Visited;
   DenseMap<Instruction *, APInt> AliveBits;
 };
 
 /// Create a demanded bits analysis pass.
 FunctionPass *createDemandedBitsPass();
 
 } // End llvm namespace
 
 #endif

include/llvm/IR/DebugInfo.h

public:
   unsigned scope_count() const { return Scopes.size(); }
 
 private:
   SmallVector<DICompileUnit *, 8> CUs;
   SmallVector<DISubprogram *, 8> SPs;
   SmallVector<DIGlobalVariable *, 8> GVs;
   SmallVector<DIType *, 8> TYs;
   SmallVector<DIScope *, 8> Scopes;
-  SmallPtrSet<const MDNode *, 64> NodesSeen;
+  SmallPtrSet<const MDNode *, 32> NodesSeen;
   DITypeIdentifierMap TypeIdentifierMap;
 
   /// \brief Specify if TypeIdentifierMap is initialized.
   bool TypeMapInitialized;
 };
 
 } // end namespace llvm
 
 #endif

include/llvm/MC/MCAssembler.h

private:
 
   /// The set of function symbols for which a .thumb_func directive has
   /// been seen.
   //
   // FIXME: We really would like this in target specific code rather than
   // here. Maybe when the relocation stuff moves to target specific,
   // this can go with it? The streamer would need some target specific
   // refactoring too.
-  mutable SmallPtrSet<const MCSymbol *, 64> ThumbFuncs;
+  mutable SmallPtrSet<const MCSymbol *, 32> ThumbFuncs;
 
   /// \brief The bundle alignment size currently set in the assembler.
   ///
   /// By default it's 0, which means bundling is disabled.
   unsigned BundleAlignSize;
 
   unsigned RelaxAll : 1;
   unsigned SubsectionsViaSymbols : 1;

lib/Analysis/CFG.cpp

bool llvm::isPotentiallyReachableFromMany(
   // When the stop block is unreachable, it's dominated from everywhere,
   // regardless of whether there's a path between the two blocks.
   if (DT && !DT->isReachableFromEntry(StopBB))
     DT = nullptr;
 
   // Limit the number of blocks we visit. The goal is to avoid run-away compile
   // times on large CFGs without hampering sensible code. Arbitrarily chosen.
   unsigned Limit = 32;
-  SmallSet<const BasicBlock*, 64> Visited;
+  SmallPtrSet<const BasicBlock*, 32> Visited;
   do {
     BasicBlock *BB = Worklist.pop_back_val();
     if (!Visited.insert(BB).second)
       continue;
     if (BB == StopBB)
       return true;
     if (DT && DT->dominates(BB, StopBB))
       return true;

lib/Analysis/GlobalsModRef.cpp

GlobalsAAResult::getFunctionInfo(const Function *F) {
   return nullptr;
 }
 
 /// AnalyzeGlobals - Scan through the users of all of the internal
 /// GlobalValue's in the program.  If none of them have their "address taken"
 /// (really, their address passed to something nontrivial), record this fact,
 /// and record the functions that they are used directly in.
 void GlobalsAAResult::AnalyzeGlobals(Module &M) {
-  SmallPtrSet<Function *, 64> TrackedFunctions;
+  SmallPtrSet<Function *, 32> TrackedFunctions;
   for (Function &F : M)
     if (F.hasLocalLinkage())
       if (!AnalyzeUsesOfPointer(&F)) {
         // Remember that we are tracking this global.
         NonAddressTakenGlobals.insert(&F);
         TrackedFunctions.insert(&F);
         Handles.emplace_front(*this, &F);
         Handles.front().I = Handles.begin();
         ++NumNonAddrTakenFunctions;
       }
 
-  SmallPtrSet<Function *, 64> Readers, Writers;
+  SmallPtrSet<Function *, 16> Readers, Writers;
   for (GlobalVariable &GV : M.globals())
     if (GV.hasLocalLinkage()) {
       if (!AnalyzeUsesOfPointer(&GV, &Readers,
                                 GV.isConstant() ? nullptr : &Writers)) {
         // Remember that we are tracking this global, and the mod/ref fns
         NonAddressTakenGlobals.insert(&GV);
         Handles.emplace_front(*this, &GV);
         Handles.front().I = Handles.begin();

lib/Analysis/MemoryDependenceAnalysis.cpp

if (!Cache.empty()) {
     for (BasicBlock *Pred : PredCache.get(QueryBB))
       DirtyBlocks.push_back(Pred);
     ++NumUncacheNonLocal;
   }
 
   // isReadonlyCall - If this is a read-only call, we can be more aggressive.
   bool isReadonlyCall = AA->onlyReadsMemory(QueryCS);
 
-  SmallPtrSet<BasicBlock*, 64> Visited;
+  SmallPtrSet<BasicBlock*, 32> Visited;
 
   unsigned NumSortedEntries = Cache.size();
   DEBUG(AssertSorted(Cache));
 
   // Iterate while we still have blocks to update.
   while (!DirtyBlocks.empty()) {
     BasicBlock *DirtyBB = DirtyBlocks.back();
     DirtyBlocks.pop_back();

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

class DAGCombiner {
     /// them) when they are deleted from the underlying DAG. It relies on
     /// stable indices of nodes within the worklist.
     DenseMap<SDNode *, unsigned> WorklistMap;
 
     /// \brief Set of nodes which have been combined (at least once).
     ///
     /// This is used to allow us to reliably add any operands of a DAG node
     /// which have not yet been combined to the worklist.
-    SmallPtrSet<SDNode *, 64> CombinedNodes;
+    SmallPtrSet<SDNode *, 32> CombinedNodes;
 
     // AA - Used for DAG load/store alias analysis.
     AliasAnalysis &AA;
 
     /// When an instruction is simplified, add all users of the instruction to
     /// the work lists because they might get more simplified now.
     void AddUsersToWorklist(SDNode *N) {
       for (SDNode *Node : N->uses())

lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp

void ScheduleDAGSDNodes::BuildSchedUnits() {
   // ensure that reallocation of the vector won't happen, so SUnit*'s won't get
   // invalidated.
   // FIXME: Multiply by 2 because we may clone nodes during scheduling.
   // This is a temporary workaround.
   SUnits.reserve(NumNodes * 2);
 
   // Add all nodes in depth first order.
   SmallVector<SDNode*, 64> Worklist;
-  SmallPtrSet<SDNode*, 64> Visited;
+  SmallPtrSet<SDNode*, 32> Visited;
   Worklist.push_back(DAG->getRoot().getNode());
   Visited.insert(DAG->getRoot().getNode());
 
   SmallVector<SUnit*, 8> CallSUnits;
   while (!Worklist.empty()) {
     SDNode *NI = Worklist.pop_back_val();
 
     // Add all operands to the worklist unless they've already been added.

lib/CodeGen/SelectionDAG/SelectionDAGDumper.cpp

static bool printOperand(raw_ostream &OS, const SelectionDAG *G,
   } else {
     OS << PrintNodeId(*Value.getNode());
     if (unsigned RN = Value.getResNo())
       OS << ':' << RN;
     return false;
   }
 }
 
-typedef SmallPtrSet<const SDNode *, 128> VisitedSDNodeSet;
+typedef SmallPtrSet<const SDNode *, 32> VisitedSDNodeSet;
 static void DumpNodesr(raw_ostream &OS, const SDNode *N, unsigned indent,
                        const SelectionDAG *G, VisitedSDNodeSet &once) {
   if (!once.insert(N).second) // If we've been here before, return now.
     return;
 
   // Dump the current SDNode, but don't end the line yet.
   OS.indent(indent);
   N->printr(OS, G);

lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp

void SelectionDAGISel::SelectBasicBlock(BasicBlock::const_iterator Begin,
   HadTailCall = SDB->HasTailCall;
   SDB->clear();
 
   // Final step, emit the lowered DAG as machine code.
   CodeGenAndEmitDAG();
 }
 
 void SelectionDAGISel::ComputeLiveOutVRegInfo() {
-  SmallPtrSet<SDNode*, 128> VisitedNodes;
+  SmallPtrSet<SDNode*, 16> VisitedNodes;
   SmallVector<SDNode*, 128> Worklist;
 
   Worklist.push_back(CurDAG->getRoot().getNode());
 
   APInt KnownZero;
   APInt KnownOne;
 
   do {

lib/CodeGen/SelectionDAG/StatepointLowering.cpp

 /// StackMap section.  It has no effect on the number of spill slots required
 /// or the actual lowering.
 static void removeDuplicatesGCPtrs(SmallVectorImpl<const Value *> &Bases,
                                    SmallVectorImpl<const Value *> &Ptrs,
                                    SmallVectorImpl<const Value *> &Relocs,
                                    SelectionDAGBuilder &Builder) {
 
   // This is horribly inefficient, but I don't care right now
-  SmallSet<SDValue, 64> Seen;
+  SmallSet<SDValue, 32> Seen;
 
   SmallVector<const Value *, 64> NewBases, NewPtrs, NewRelocs;
   for (size_t i = 0; i < Ptrs.size(); i++) {
     SDValue SD = Builder.getValue(Ptrs[i]);
     // Only add non-duplicates
     if (Seen.count(SD) == 0) {
       NewBases.push_back(Bases[i]);
       NewPtrs.push_back(Ptrs[i]);

lib/CodeGen/SjLjEHPrepare.cpp

for (BasicBlock::iterator II = BB->begin(), IIE = BB->end(); II != IIE;
       SmallVector<Instruction *, 16> Users;
       for (User *U : Inst->users()) {
         Instruction *UI = cast<Instruction>(U);
         if (UI->getParent() != BB || isa<PHINode>(UI))
           Users.push_back(UI);
       }
 
       // Find all of the blocks that this value is live in.
-      SmallPtrSet<BasicBlock *, 64> LiveBBs;
+      SmallPtrSet<BasicBlock *, 32> LiveBBs;
       LiveBBs.insert(Inst->getParent());
       while (!Users.empty()) {
         Instruction *U = Users.back();
         Users.pop_back();
 
         if (!isa<PHINode>(U)) {
           MarkBlocksLiveIn(U->getParent(), LiveBBs);
         } else {

lib/Support/CommandLine.cpp

static int OptNameCompare(const std::pair<const char *, Option *> *LHS,
                           const std::pair<const char *, Option *> *RHS) {
   return strcmp(LHS->first, RHS->first);
 }
 
 // Copy Options into a vector so we can sort them as we like.
 static void sortOpts(StringMap<Option *> &OptMap,
                      SmallVectorImpl<std::pair<const char *, Option *>> &Opts,
                      bool ShowHidden) {
-  SmallPtrSet<Option *, 128> OptionSet; // Duplicate option detection.
+  SmallPtrSet<Option *, 32> OptionSet; // Duplicate option detection.
 
   for (StringMap<Option *>::iterator I = OptMap.begin(), E = OptMap.end();
        I != E; ++I) {
     // Ignore really-hidden options.
     if (I->second->getOptionHiddenFlag() == ReallyHidden)
       continue;
 
     // Unless showhidden is set, ignore hidden flags.

lib/Target/ARM/ARMISelLowering.cpp

for (MachineBasicBlock::iterator
         MaxCSNum = std::max(MaxCSNum, *CSI);
       }
       break;
     }
   }
 
   // Get an ordered list of the machine basic blocks for the jump table.
   std::vector<MachineBasicBlock*> LPadList;
-  SmallPtrSet<MachineBasicBlock*, 64> InvokeBBs;
+  SmallPtrSet<MachineBasicBlock*, 32> InvokeBBs;
   LPadList.reserve(CallSiteNumToLPad.size());
   for (unsigned I = 1; I <= MaxCSNum; ++I) {
     SmallVectorImpl<MachineBasicBlock*> &MBBList = CallSiteNumToLPad[I];
     for (SmallVectorImpl<MachineBasicBlock*>::iterator
            II = MBBList.begin(), IE = MBBList.end(); II != IE; ++II) {
       LPadList.push_back(*II);
       InvokeBBs.insert((*II)->pred_begin(), (*II)->pred_end());
     }

lib/Transforms/IPO/MergeFunctions.cpp

if (cmpValues(&*ArgLI, &*ArgRI) != 0)
       llvm_unreachable("Arguments repeat!");
   }
 
   // We do a CFG-ordered walk since the actual ordering of the blocks in the
   // linked list is immaterial. Our walk starts at the entry block for both
   // functions, then takes each block from each terminator in order. As an
   // artifact, this also means that unreachable blocks are ignored.
   SmallVector<const BasicBlock *, 8> FnLBBs, FnRBBs;
-  SmallSet<const BasicBlock *, 128> VisitedBBs; // in terms of F1.
+  SmallPtrSet<const BasicBlock *, 32> VisitedBBs; // in terms of F1.
 
   FnLBBs.push_back(&FnL->getEntryBlock());
   FnRBBs.push_back(&FnR->getEntryBlock());
 
   VisitedBBs.insert(FnLBBs[0]);
   while (!FnLBBs.empty()) {
     const BasicBlock *BBL = FnLBBs.pop_back_val();
     const BasicBlock *BBR = FnRBBs.pop_back_val();

lib/Transforms/IPO/SampleProfile.cpp

protected:
 
   /// \brief Map edges to their computed weights.
   ///
   /// Edge weights are computed by propagating basic block weights in
   /// SampleProfile::propagateWeights.
   EdgeWeightMap EdgeWeights;
 
   /// \brief Set of visited blocks during propagation.
-  SmallPtrSet<const BasicBlock *, 128> VisitedBlocks;
+  SmallPtrSet<const BasicBlock *, 32> VisitedBlocks;
 
   /// \brief Set of visited edges during propagation.
-  SmallSet<Edge, 128> VisitedEdges;
+  SmallSet<Edge, 32> VisitedEdges;
 
   /// \brief Equivalence classes for block weights.
   ///
   /// Two blocks BB1 and BB2 are in the same equivalence class if they
   /// dominate and post-dominate each other, and they are in the same loop
   /// nest. When this happens, the two blocks are guaranteed to execute
   /// the same number of times.
   EquivalenceClassMap EquivalenceClass;

lib/Transforms/InstCombine/InstructionCombining.cpp

 static bool prepareICWorklistFromFunction(Function &F, const DataLayout &DL,
                                           TargetLibraryInfo *TLI,
                                           InstCombineWorklist &ICWorklist) {
   bool MadeIRChange = false;
 
   // Do a depth-first traversal of the function, populate the worklist with
   // the reachable instructions.  Ignore blocks that are not reachable.  Keep
   // track of which blocks we visit.
-  SmallPtrSet<BasicBlock *, 64> Visited;
+  SmallPtrSet<BasicBlock *, 32> Visited;
   MadeIRChange |=
       AddReachableCodeToWorklist(&F.front(), DL, Visited, ICWorklist, TLI);
 
   // Do a quick scan over the function.  If we find any blocks that are
   // unreachable, remove any instructions inside of them.  This prevents
   // the instcombine code from having to deal with some bad special cases.
   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
     if (Visited.count(&*BB))

lib/Transforms/Scalar/ADCE.cpp

 #include "llvm/Transforms/Scalar.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "adce"
 
 STATISTIC(NumRemoved, "Number of instructions removed");
 
 static bool aggressiveDCE(Function& F) {
-  SmallPtrSet<Instruction*, 128> Alive;
+  SmallPtrSet<Instruction*, 32> Alive;
   SmallVector<Instruction*, 128> Worklist;
 
   // Collect the set of "root" instructions that are known live.
   for (Instruction &I : instructions(F)) {
     if (isa<TerminatorInst>(I) || isa<DbgInfoIntrinsic>(I) || I.isEHPad() ||
         I.mayHaveSideEffects()) {
       Alive.insert(&I);
       Worklist.push_back(&I);

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

static void checkBasicSSA(DominatorTree &DT, GCPtrLivenessData &Data,
   checkBasicSSA(DT, Data.LiveOut[&BB], BB.getTerminator(), true);
   checkBasicSSA(DT, Data.LiveIn[&BB], BB.getTerminator());
 }
 #endif
 
 static void computeLiveInValues(DominatorTree &DT, Function &F,
                                 GCPtrLivenessData &Data) {
 
-  SmallSetVector<BasicBlock *, 200> Worklist;
+  SmallSetVector<BasicBlock *, 32> Worklist;
   auto AddPredsToWorklist = [&](BasicBlock *BB) {
     // We use a SetVector so that we don't have duplicates in the worklist.
     Worklist.insert(pred_begin(BB), pred_end(BB));
   };
   auto NextItem = [&]() {
     BasicBlock *BB = Worklist.back();
     Worklist.pop_back();
     return BB;

lib/Transforms/Utils/Local.cpp

void llvm::removeUnwindEdge(BasicBlock *BB) {
   TI->replaceAllUsesWith(NewTI);
   TI->eraseFromParent();
 }
 
 /// removeUnreachableBlocksFromFn - Remove blocks that are not reachable, even
 /// if they are in a dead cycle.  Return true if a change was made, false
 /// otherwise.
 bool llvm::removeUnreachableBlocks(Function &F, LazyValueInfo *LVI) {
-  SmallPtrSet<BasicBlock*, 128> Reachable;
+  SmallPtrSet<BasicBlock*, 16> Reachable;
   bool Changed = markAliveBlocks(F, Reachable);
 
   // If there are unreachable blocks in the CFG...
   if (Reachable.size() == F.size())
     return Changed;
 
   assert(Reachable.size() < F.size());
   NumRemoved += F.size()-Reachable.size();

lib/Transforms/Utils/SplitModule.cpp

std::priority_queue<std::pair<unsigned, unsigned>,
                       decltype(CompareClusters)>
       BalancinQueue(CompareClusters);
   // Pre-populate priority queue with N slot blanks.
   for (unsigned i = 0; i < N; ++i)
     BalancinQueue.push(std::make_pair(i, 0));
 
   typedef std::pair<unsigned, ClusterMapType::iterator> SortType;
   SmallVector<SortType, 64> Sets;
-  SmallPtrSet<const GlobalValue *, 64> Visited;
+  SmallPtrSet<const GlobalValue *, 32> Visited;
 
   // To guarantee determinism, we have to sort SCC according to size.
   // When size is the same, use leader's name.
   for (ClusterMapType::iterator I = GVtoClusterMap.begin(),
                                 E = GVtoClusterMap.end(); I != E; ++I)
     if (I->isLeader())
       Sets.push_back(
           std::make_pair(std::distance(GVtoClusterMap.member_begin(I),

tools/bugpoint/CrashDebugger.cpp

 
 bool ReduceCrashingInstructions::TestInsts(std::vector<const Instruction*>
                                            &Insts) {
   // Clone the program to try hacking it apart...
   ValueToValueMapTy VMap;
   Module *M = CloneModule(BD.getProgram(), VMap).release();
 
   // Convert list to set for fast lookup...
-  SmallPtrSet<Instruction*, 64> Instructions;
+  SmallPtrSet<Instruction*, 32> Instructions;
   for (unsigned i = 0, e = Insts.size(); i != e; ++i) {
     assert(!isa<TerminatorInst>(Insts[i]));
     Instructions.insert(cast<Instruction>(VMap[Insts[i]]));
   }
 
   outs() << "Checking for crash with only " << Instructions.size();
   if (Instructions.size() == 1)
     outs() << " instruction: ";
public:
 
   bool TestNamedMDOps(std::vector<const MDNode *> &NamedMDOps);
 };
 }
 
 bool ReduceCrashingNamedMDOps::TestNamedMDOps(
     std::vector<const MDNode *> &NamedMDOps) {
   // Convert list to set for fast lookup...
-  SmallPtrSet<const MDNode *, 64> OldMDNodeOps;
+  SmallPtrSet<const MDNode *, 32> OldMDNodeOps;
   for (unsigned i = 0, e = NamedMDOps.size(); i != e; ++i) {
     OldMDNodeOps.insert(NamedMDOps[i]);
   }
 
   outs() << "Checking for crash with only " << OldMDNodeOps.size();
   if (OldMDNodeOps.size() == 1)
     outs() << " named metadata operand: ";
   else