Index: llvm/trunk/include/llvm/ADT/STLExtras.h =================================================================== --- llvm/trunk/include/llvm/ADT/STLExtras.h +++ llvm/trunk/include/llvm/ADT/STLExtras.h @@ -1405,6 +1405,40 @@ Indices{}); } +/// Return true if the sequence [Begin, End) has exactly N items. Runs in O(N) +/// time. Not meant for use with random-access iterators. +template +bool hasNItems( + IterTy &&Begin, IterTy &&End, unsigned N, + typename std::enable_if< + !std::is_same< + typename std::iterator_traits::type>::iterator_category, + std::random_access_iterator_tag>::value, + void>::type * = nullptr) { + for (; N; --N, ++Begin) + if (Begin == End) + return false; // Too few. + return Begin == End; +} + +/// Return true if the sequence [Begin, End) has N or more items. Runs in O(N) +/// time. Not meant for use with random-access iterators. +template +bool hasNItemsOrMore( + IterTy &&Begin, IterTy &&End, unsigned N, + typename std::enable_if< + !std::is_same< + typename std::iterator_traits::type>::iterator_category, + std::random_access_iterator_tag>::value, + void>::type * = nullptr) { + for (; N; --N, ++Begin) + if (Begin == End) + return false; // Too few. + return true; +} + } // end namespace llvm #endif // LLVM_ADT_STLEXTRAS_H Index: llvm/trunk/include/llvm/IR/BasicBlock.h =================================================================== --- llvm/trunk/include/llvm/IR/BasicBlock.h +++ llvm/trunk/include/llvm/IR/BasicBlock.h @@ -237,6 +237,12 @@ static_cast(this)->getUniquePredecessor()); } + /// Return true if this block has exactly N predecessors. + bool hasNPredecessors(unsigned N) const; + + /// Return true if this block has N predecessors or more. + bool hasNPredecessorsOrMore(unsigned N) const; + /// Return the successor of this block if it has a single successor. /// Otherwise return a null pointer. /// Index: llvm/trunk/include/llvm/IR/CFG.h =================================================================== --- llvm/trunk/include/llvm/IR/CFG.h +++ llvm/trunk/include/llvm/IR/CFG.h @@ -117,6 +117,8 @@ inline bool pred_empty(const BasicBlock *BB) { return pred_begin(BB) == pred_end(BB); } +/// Get the number of predecessors of \p BB. This is a linear time operation. +/// Use \ref BasicBlock::hasNPredecessors() or hasNPredecessorsOrMore if able. inline unsigned pred_size(const BasicBlock *BB) { return std::distance(pred_begin(BB), pred_end(BB)); } Index: llvm/trunk/lib/Analysis/MemorySSAUpdater.cpp =================================================================== --- llvm/trunk/lib/Analysis/MemorySSAUpdater.cpp +++ llvm/trunk/lib/Analysis/MemorySSAUpdater.cpp @@ -1022,7 +1022,7 @@ MemoryPhi *Phi = MSSA->getMemoryAccess(Old); if (!Phi) return; - if (pred_size(Old) == 1) { + if (Old->hasNPredecessors(1)) { assert(pred_size(New) == Preds.size() && "Should have moved all predecessors."); MSSA->moveTo(Phi, New, MemorySSA::Beginning); Index: llvm/trunk/lib/IR/BasicBlock.cpp =================================================================== --- llvm/trunk/lib/IR/BasicBlock.cpp +++ llvm/trunk/lib/IR/BasicBlock.cpp @@ -260,6 +260,14 @@ return PredBB; } +bool BasicBlock::hasNPredecessors(unsigned N) const { + return hasNItems(pred_begin(this), pred_end(this), N); +} + +bool BasicBlock::hasNPredecessorsOrMore(unsigned N) const { + return hasNItemsOrMore(pred_begin(this), pred_end(this), N); +} + const BasicBlock *BasicBlock::getSingleSuccessor() const { succ_const_iterator SI = succ_begin(this), E = succ_end(this); if (SI == E) return nullptr; // no successors Index: llvm/trunk/lib/IR/Value.cpp =================================================================== --- llvm/trunk/lib/IR/Value.cpp +++ llvm/trunk/lib/IR/Value.cpp @@ -130,20 +130,11 @@ } bool Value::hasNUses(unsigned N) const { - const_use_iterator UI = use_begin(), E = use_end(); - - for (; N; --N, ++UI) - if (UI == E) return false; // Too few. - return UI == E; + return hasNItems(use_begin(), use_end(), N); } bool Value::hasNUsesOrMore(unsigned N) const { - const_use_iterator UI = use_begin(), E = use_end(); - - for (; N; --N, ++UI) - if (UI == E) return false; // Too few. - - return true; + return hasNItemsOrMore(use_begin(), use_end(), N); } bool Value::isUsedInBasicBlock(const BasicBlock *BB) const { Index: llvm/trunk/lib/Transforms/IPO/PartialInlining.cpp =================================================================== --- llvm/trunk/lib/Transforms/IPO/PartialInlining.cpp +++ llvm/trunk/lib/Transforms/IPO/PartialInlining.cpp @@ -403,7 +403,7 @@ auto IsSingleEntry = [](SmallVectorImpl &BlockList) { BasicBlock *Dom = BlockList.front(); - return BlockList.size() > 1 && pred_size(Dom) == 1; + return BlockList.size() > 1 && Dom->hasNPredecessors(1); }; auto IsSingleExit = Index: llvm/trunk/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp =================================================================== --- llvm/trunk/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp +++ llvm/trunk/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp @@ -1526,7 +1526,7 @@ // Check if the successor block has exactly 2 incoming edges. BasicBlock *StoreBB = SI.getParent(); BasicBlock *DestBB = StoreBB->getTerminator()->getSuccessor(0); - if (pred_size(DestBB) != 2) + if (!DestBB->hasNPredecessors(2)) return false; // Capture the other block (the block that doesn't contain our store). Index: llvm/trunk/lib/Transforms/Utils/Local.cpp =================================================================== --- llvm/trunk/lib/Transforms/Utils/Local.cpp +++ llvm/trunk/lib/Transforms/Utils/Local.cpp @@ -682,10 +682,9 @@ // DTU updates: Collect all the edges that enter // PredBB. These dominator edges will be redirected to DestBB. - std::vector Updates; + SmallVector Updates; if (DTU) { - Updates.reserve(1 + (2 * pred_size(PredBB))); Updates.push_back({DominatorTree::Delete, PredBB, DestBB}); for (auto I = pred_begin(PredBB), E = pred_end(PredBB); I != E; ++I) { Updates.push_back({DominatorTree::Delete, *I, PredBB}); @@ -989,9 +988,8 @@ LLVM_DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB); - std::vector Updates; + SmallVector Updates; if (DTU) { - Updates.reserve(1 + (2 * pred_size(BB))); Updates.push_back({DominatorTree::Delete, BB, Succ}); // All predecessors of BB will be moved to Succ. for (auto I = pred_begin(BB), E = pred_end(BB); I != E; ++I) { Index: llvm/trunk/lib/Transforms/Utils/SimplifyCFG.cpp =================================================================== --- llvm/trunk/lib/Transforms/Utils/SimplifyCFG.cpp +++ llvm/trunk/lib/Transforms/Utils/SimplifyCFG.cpp @@ -693,7 +693,7 @@ if (SwitchInst *SI = dyn_cast(TI)) { // Do not permit merging of large switch instructions into their // predecessors unless there is only one predecessor. - if (SI->getNumSuccessors() * pred_size(SI->getParent()) <= 128) + if (!SI->getParent()->hasNPredecessorsOrMore(128 / SI->getNumSuccessors())) CV = SI->getCondition(); } else if (BranchInst *BI = dyn_cast(TI)) if (BI->isConditional() && BI->getCondition()->hasOneUse()) @@ -2890,7 +2890,7 @@ if (!AlternativeV) break; - assert(pred_size(Succ) == 2); + assert(Succ->hasNPredecessors(2)); auto PredI = pred_begin(Succ); BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI; if (PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV) @@ -5774,7 +5774,7 @@ // backedge, so we can eliminate BB. bool NeedCanonicalLoop = Options.NeedCanonicalLoop && - (LoopHeaders && pred_size(BB) > 1 && + (LoopHeaders && BB->hasNPredecessorsOrMore(2) && (LoopHeaders->count(BB) || LoopHeaders->count(Succ))); BasicBlock::iterator I = BB->getFirstNonPHIOrDbg()->getIterator(); if (I->isTerminator() && BB != &BB->getParent()->getEntryBlock() && Index: llvm/trunk/lib/Transforms/Vectorize/VPlan.cpp =================================================================== --- llvm/trunk/lib/Transforms/Vectorize/VPlan.cpp +++ llvm/trunk/lib/Transforms/Vectorize/VPlan.cpp @@ -468,7 +468,7 @@ "One successor of a basic block does not lead to the other."); assert(InterimSucc->getSinglePredecessor() && "Interim successor has more than one predecessor."); - assert(pred_size(PostDomSucc) == 2 && + assert(PostDomSucc->hasNPredecessors(2) && "PostDom successor has more than two predecessors."); DT->addNewBlock(InterimSucc, BB); DT->addNewBlock(PostDomSucc, BB);