[STLExtras] Add distance() for ranges, pred_size(), and succ_size()

[vsk]

Summary

This commit adds a wrapper for std::distance() which works with ranges.
As it would be a common case to write distance(predecessors(BB)), this
also introduces pred_size() and succ_size() helpers to make that
easier to write.

[craig.topper]

I sort of wonder if we should have a pred_size and succ_size helper.

lib/AsmParser/LLParser.cpp

6760 ↗

(On Diff #146038)

Should this just be V->getNumUses()?

lib/Bitcode/Writer/ValueEnumerator.cpp

492 ↗

(On Diff #146038)

V->getNumUses()?

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

1814 ↗

(On Diff #146038)

Def->getNumUses()

[vsk]

In D46668#1093851, @craig.topper wrote:

I sort of wonder if we should have a pred_size and succ_size helper.

One motivation for this might be that meaning of distance(predecessors(b)) isn't obvious at first glance. Is that your concern?

If so, maybe it would be even simpler to name the new helper size. This would be more general than introducing pred_size/succ_size/etc, and might be easier to read overall. Wdyt?

[craig.topper]

I think if its equivalent to range-based version of std::distance its name should be llvm::distance.

My comment was just an observation that a majority of the uses were for predecessors/successors and maybe we should just make that easier. We already have pred_empty and succ_empty. pred_size and succ_size don't seem like much of a stretch.

[vsk]

• Add {pred,succ}_size helpers and use getNumUses() as suggested.

[bjope]

Nice, I was looking for something like this when updating MergedLoadStoreMotion.cpp.

LGTM! (assuming that @craig.topper is happy with the last update)

[craig.topper]

LGTM

[dblaikie]

I feel like a range-based version of std::distance isn't so much distance
anymore, by virtue of it being over a range & is actually probably more
suitably named 'size'. (in the case of std::distance, the name is really
talking about the two elements separately "what's the distance from this
iterator to this other iterator" not talking about a range defined by those
two iterators - so the name make sense there in a way that I don't think it
makes sense for ranges ("what is the distance of a range?" isn't a
cromulant question, I think... ))

I'd vote for llvm::size (& I think the general idea/concept/thing is a good
thing to add).

Though I guess one issue with size/distance is: how expensive is this? I'd
sort of be inclined only to provide this for ranges over random access
iterators (so it's only O(1), never O(N)), maybe? Let the more obscure
cases use std::distance(begin, end) to hopefully clarify that they're
weird/interesting/maybe expensive.

llvm/trunk/include/llvm/ADT/STLExtras.h

 ///
 /// This version works for any container with an erase method call accepting
 /// two iterators.
 template <typename Container, typename UnaryPredicate>
 void erase_if(Container &C, UnaryPredicate P) {
   C.erase(remove_if(C, P), C.end());
 }
 
+/// Wrapper function around std::distance which works with ranges.
+template <typename R>
+auto distance(R &&Range)
+    -> decltype(std::distance(Range.begin(), Range.end())) {
+  return std::distance(Range.begin(), Range.end());
+}
+
 //===----------------------------------------------------------------------===//
 //     Extra additions to <memory>
 //===----------------------------------------------------------------------===//
 
 // Implement make_unique according to N3656.
 
 /// Constructs a `new T()` with the given args and returns a
 ///        `unique_ptr<T>` which owns the object.

llvm/trunk/include/llvm/IR/CFG.h

 }
 inline pred_iterator pred_end(BasicBlock *BB) { return pred_iterator(BB, true);}
 inline const_pred_iterator pred_end(const BasicBlock *BB) {
   return const_pred_iterator(BB, true);
 }
 inline bool pred_empty(const BasicBlock *BB) {
   return pred_begin(BB) == pred_end(BB);
 }
+inline unsigned pred_size(const BasicBlock *BB) {
+  return std::distance(pred_begin(BB), pred_end(BB));
+}
 inline pred_range predecessors(BasicBlock *BB) {
   return pred_range(pred_begin(BB), pred_end(BB));
 }
 inline pred_const_range predecessors(const BasicBlock *BB) {
   return pred_const_range(pred_begin(BB), pred_end(BB));
 }
 
 //===----------------------------------------------------------------------===//
inline succ_iterator succ_end(BasicBlock *BB) {
   return succ_iterator(BB->getTerminator(), true);
 }
 inline succ_const_iterator succ_end(const BasicBlock *BB) {
   return succ_const_iterator(BB->getTerminator(), true);
 }
 inline bool succ_empty(const BasicBlock *BB) {
   return succ_begin(BB) == succ_end(BB);
 }
+inline unsigned succ_size(const BasicBlock *BB) {
+  return std::distance(succ_begin(BB), succ_end(BB));
+}
 inline succ_range successors(BasicBlock *BB) {
   return succ_range(succ_begin(BB), succ_end(BB));
 }
 inline succ_const_range successors(const BasicBlock *BB) {
   return succ_const_range(succ_begin(BB), succ_end(BB));
 }
 
 template <typename T, typename U>

llvm/trunk/lib/Analysis/BranchProbabilityInfo.cpp

 BranchProbability
 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
                                           unsigned IndexInSuccessors) const {
   auto I = Probs.find(std::make_pair(Src, IndexInSuccessors));
 
   if (I != Probs.end())
     return I->second;
 
-  return {1,
-          static_cast<uint32_t>(std::distance(succ_begin(Src), succ_end(Src)))};
+  return {1, static_cast<uint32_t>(succ_size(Src))};
 }
 
 BranchProbability
 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
                                           succ_const_iterator Dst) const {
   return getEdgeProbability(Src, Dst.getSuccessorIndex());
 }
 

llvm/trunk/lib/Analysis/LazyCallGraph.cpp

do {
         return false;
       });
       auto RefSCCNodes = make_range(StackRI.base(), PendingRefSCCStack.end());
 
       // If we find a cycle containing all nodes originally in this RefSCC then
       // the removal hasn't changed the structure at all. This is an important
       // special case and we can directly exit the entire routine more
       // efficiently as soon as we discover it.
-      if (std::distance(RefSCCNodes.begin(), RefSCCNodes.end()) ==
-          NumRefSCCNodes) {
+      if (distance(RefSCCNodes) == NumRefSCCNodes) {
         // Clear out the low link field as we won't need it.
         for (Node *N : RefSCCNodes)
           N->LowLink = -1;
         // Return the empty result immediately.
         return Result;
       }
 
       // We've already marked the nodes internally with the RefSCC number so
static void printNode(raw_ostream &OS, LazyCallGraph::Node &N) {
   for (LazyCallGraph::Edge &E : N.populate())
     OS << "    " << (E.isCall() ? "call" : "ref ") << " -> "
        << E.getFunction().getName() << "\n";
 
   OS << "\n";
 }
 
 static void printSCC(raw_ostream &OS, LazyCallGraph::SCC &C) {
-  ptrdiff_t Size = std::distance(C.begin(), C.end());
+  ptrdiff_t Size = distance(C);
   OS << "    SCC with " << Size << " functions:\n";
 
   for (LazyCallGraph::Node &N : C)
     OS << "      " << N.getFunction().getName() << "\n";
 }
 
 static void printRefSCC(raw_ostream &OS, LazyCallGraph::RefSCC &C) {
-  ptrdiff_t Size = std::distance(C.begin(), C.end());
+  ptrdiff_t Size = distance(C);
   OS << "  RefSCC with " << Size << " call SCCs:\n";
 
   for (LazyCallGraph::SCC &InnerC : C)
     printSCC(OS, InnerC);
 
   OS << "\n";
 }
 

llvm/trunk/lib/Analysis/LoopInfo.cpp

for (BasicBlock *Successor : successors(BB)) {
       // This ensures that same exit block is not inserted twice into
       // ExitBlocks vector.
       if (BB != FirstPred)
         continue;
 
       // If a terminator has more then two successors, for example SwitchInst,
       // then it is possible that there are multiple edges from current block
       // to one exit block.
-      if (std::distance(succ_begin(BB), succ_end(BB)) <= 2) {
+      if (succ_size(BB) <= 2) {
         ExitBlocks.push_back(Successor);
         continue;
       }
 
       // In case of multiple edges from current block to exit block, collect
       // only one edge in ExitBlocks. Use switchExitBlocks to keep track of
       // duplicate edges.
       if (!is_contained(SwitchExitBlocks, Successor)) {

llvm/trunk/lib/AsmParser/LLParser.cpp

bool LLParser::sortUseListOrder(Value *V, ArrayRef<unsigned> Indexes,
   for (const Use &U : V->uses()) {
     if (++NumUses > Indexes.size())
       break;
     Order[&U] = Indexes[NumUses - 1];
   }
   if (NumUses < 2)
     return Error(Loc, "value only has one use");
   if (Order.size() != Indexes.size() || NumUses > Indexes.size())
-    return Error(Loc, "wrong number of indexes, expected " +
-                          Twine(std::distance(V->use_begin(), V->use_end())));
+    return Error(Loc,
+                 "wrong number of indexes, expected " + Twine(V->getNumUses()));
 
   V->sortUseList([&](const Use &L, const Use &R) {
     return Order.lookup(&L) < Order.lookup(&R);
   });
   return false;
 }
 
 /// ParseUseListOrderIndexes

llvm/trunk/lib/Bitcode/Writer/ValueEnumerator.cpp

for (ValueMapType::const_iterator I = Map.begin(),
     const Value *V = I->first;
     if (V->hasName())
       OS << "Value: " << V->getName();
     else
       OS << "Value: [null]\n";
     V->print(errs());
     errs() << '\n';
 
-    OS << " Uses(" << std::distance(V->use_begin(),V->use_end()) << "):";
+    OS << " Uses(" << V->getNumUses() << "):";
     for (const Use &U : V->uses()) {
       if (&U != &*V->use_begin())
         OS << ",";
       if(U->hasName())
         OS << " " << U->getName();
       else
         OS << " [null]";
 

llvm/trunk/lib/CodeGen/CodeGenPrepare.cpp

while (!Worklist.empty()) {
 
       Value *CurrentValue = Current.first;
       BasicBlock *CurrentBlock = Current.second;
       // CurrentValue must be a Phi node or select. All others must be covered
       // by anchors.
       Instruction *CurrentI = cast<Instruction>(CurrentValue);
       bool IsDefinedInThisBB = CurrentI->getParent() == CurrentBlock;
 
-      unsigned PredCount =
-          std::distance(pred_begin(CurrentBlock), pred_end(CurrentBlock));
+      unsigned PredCount = pred_size(CurrentBlock);
       // if Current Value is not defined in this basic block we are interested
       // in values in predecessors.
       if (!IsDefinedInThisBB) {
         assert(PredCount && "Unreachable block?!");
         PHINode *PHI = PHINode::Create(CommonType, PredCount, "sunk_phi",
                                        &CurrentBlock->front());
         Map[Current] = PHI;
         ST.insertNewPhi(PHI);

llvm/trunk/lib/CodeGen/ImplicitNullChecks.cpp

MachineInstr *ImplicitNullChecks::insertFaultingInstr(
 
   DebugLoc DL;
   unsigned NumDefs = MI->getDesc().getNumDefs();
   assert(NumDefs <= 1 && "other cases unhandled!");
 
   unsigned DefReg = NoRegister;
   if (NumDefs != 0) {
     DefReg = MI->defs().begin()->getReg();
-    assert(std::distance(MI->defs().begin(), MI->defs().end()) == 1 &&
-           "expected exactly one def!");
+    assert(distance(MI->defs()) == 1 && "expected exactly one def!");
   }
 
   FaultMaps::FaultKind FK;
   if (MI->mayLoad())
     FK =
         MI->mayStore() ? FaultMaps::FaultingLoadStore : FaultMaps::FaultingLoad;
   else
     FK = FaultMaps::FaultingStore;

llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

 SelectionDAGBuilder::getEdgeProbability(const MachineBasicBlock *Src,
                                         const MachineBasicBlock *Dst) const {
   BranchProbabilityInfo *BPI = FuncInfo.BPI;
   const BasicBlock *SrcBB = Src->getBasicBlock();
   const BasicBlock *DstBB = Dst->getBasicBlock();
   if (!BPI) {
     // If BPI is not available, set the default probability as 1 / N, where N is
     // the number of successors.
-    auto SuccSize = std::max<uint32_t>(
-        std::distance(succ_begin(SrcBB), succ_end(SrcBB)), 1);
+    auto SuccSize = std::max<uint32_t>(succ_size(SrcBB), 1);
     return BranchProbability(1, SuccSize);
   }
   return BPI->getEdgeProbability(SrcBB, DstBB);
 }
 
 void SelectionDAGBuilder::addSuccessorWithProb(MachineBasicBlock *Src,
                                                MachineBasicBlock *Dst,
                                                BranchProbability Prob) {

llvm/trunk/lib/IR/Value.cpp

for (; BI != BE && UI != UE; ++BI, ++UI) {
     // Scan use list: Check if the use at UI is in BB.
     const auto *User = dyn_cast<Instruction>(*UI);
     if (User && User->getParent() == BB)
       return true;
   }
   return false;
 }
 
-unsigned Value::getNumUses() const {
-  return (unsigned)std::distance(use_begin(), use_end());
-}
+unsigned Value::getNumUses() const { return (unsigned)distance(uses()); }
 
 static bool getSymTab(Value *V, ValueSymbolTable *&ST) {
   ST = nullptr;
   if (Instruction *I = dyn_cast<Instruction>(V)) {
     if (BasicBlock *P = I->getParent())
       if (Function *PP = P->getParent())
         ST = PP->getValueSymbolTable();
   } else if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) {

llvm/trunk/lib/Target/PowerPC/PPCLoopPreIncPrep.cpp

bool PPCLoopPreIncPrep::runOnLoop(Loop *L) {
 
   DEBUG(dbgs() << "PIP: Examining: " << *L << "\n");
 
   BasicBlock *Header = L->getHeader();
 
   const PPCSubtarget *ST =
     TM ? TM->getSubtargetImpl(*Header->getParent()) : nullptr;
 
-  unsigned HeaderLoopPredCount =
-    std::distance(pred_begin(Header), pred_end(Header));
+  unsigned HeaderLoopPredCount = pred_size(Header);
 
   // Collect buckets of comparable addresses used by loads and stores.
   SmallVector<Bucket, 16> Buckets;
   for (Loop::block_iterator I = L->block_begin(), IE = L->block_end();
        I != IE; ++I) {
     for (BasicBlock::iterator J = (*I)->begin(), JE = (*I)->end();
         J != JE; ++J) {
       Value *PtrValue;

llvm/trunk/lib/Transforms/IPO/PartialInlining.cpp

PartialInlinerImpl::computeOutliningColdRegionsInfo(Function *F,
   if (!PSI->hasInstrumentationProfile())
     return std::unique_ptr<FunctionOutliningMultiRegionInfo>();
 
   std::unique_ptr<FunctionOutliningMultiRegionInfo> OutliningInfo =
       llvm::make_unique<FunctionOutliningMultiRegionInfo>();
 
   auto IsSingleEntry = [](SmallVectorImpl<BasicBlock *> &BlockList) {
     BasicBlock *Dom = BlockList.front();
-    return BlockList.size() > 1 &&
-           std::distance(pred_begin(Dom), pred_end(Dom)) == 1;
+    return BlockList.size() > 1 && pred_size(Dom) == 1;
   };
 
   auto IsSingleExit =
       [&ORE](SmallVectorImpl<BasicBlock *> &BlockList) -> BasicBlock * {
     BasicBlock *ExitBlock = nullptr;
     for (auto *Block : BlockList) {
       for (auto SI = succ_begin(Block); SI != succ_end(Block); ++SI) {
         if (!is_contained(BlockList, *SI)) {
PartialInlinerImpl::computeOutliningInfo(Function *F) {
   if (!BR || BR->isUnconditional())
     return std::unique_ptr<FunctionOutliningInfo>();
 
   // Returns true if Succ is BB's successor
   auto IsSuccessor = [](BasicBlock *Succ, BasicBlock *BB) {
     return is_contained(successors(BB), Succ);
   };
 
-  auto SuccSize = [](BasicBlock *BB) {
-    return std::distance(succ_begin(BB), succ_end(BB));
-  };
-
   auto IsReturnBlock = [](BasicBlock *BB) {
     TerminatorInst *TI = BB->getTerminator();
     return isa<ReturnInst>(TI);
   };
 
   auto GetReturnBlock = [&](BasicBlock *Succ1, BasicBlock *Succ2) {
     if (IsReturnBlock(Succ1))
       return std::make_tuple(Succ1, Succ2);
PartialInlinerImpl::computeOutliningInfo(Function *F) {
   bool CandidateFound = false;
   do {
     // The number of blocks to be inlined has already reached
     // the limit. When MaxNumInlineBlocks is set to 0 or 1, this
     // disables partial inlining for the function.
     if (OutliningInfo->GetNumInlinedBlocks() >= MaxNumInlineBlocks)
       break;
 
-    if (SuccSize(CurrEntry) != 2)
+    if (succ_size(CurrEntry) != 2)
       break;
 
     BasicBlock *Succ1 = *succ_begin(CurrEntry);
     BasicBlock *Succ2 = *(succ_begin(CurrEntry) + 1);
 
     BasicBlock *ReturnBlock, *NonReturnBlock;
     std::tie(ReturnBlock, NonReturnBlock) = GetReturnBlock(Succ1, Succ2);
 
PartialInlinerImpl::computeOutliningInfo(Function *F) {
 
   if (!CheckAndNormalizeCandidate(OutliningInfo.get()))
     return std::unique_ptr<FunctionOutliningInfo>();
 
   // Now further growing the candidate's inlining region by
   // peeling off dominating blocks from the outlining region:
   while (OutliningInfo->GetNumInlinedBlocks() < MaxNumInlineBlocks) {
     BasicBlock *Cand = OutliningInfo->NonReturnBlock;
-    if (SuccSize(Cand) != 2)
+    if (succ_size(Cand) != 2)
       break;
 
     if (HasNonEntryPred(Cand))
       break;
 
     BasicBlock *Succ1 = *succ_begin(Cand);
     BasicBlock *Succ2 = *(succ_begin(Cand) + 1);
 

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

private:
   // They use similar idea in the forward graph to find fully redundant and
   // partially redundant expressions, here it is used in the inverse graph to
   // find fully anticipable instructions at merge point (post-dominator in
   // the inverse CFG).
   // Returns the edge via which an instruction in BB will get the values from.
 
   // Returns true when the values are flowing out to each edge.
   bool valueAnticipable(CHIArgs C, TerminatorInst *TI) const {
-    if (TI->getNumSuccessors() > (unsigned)std::distance(C.begin(), C.end()))
+    if (TI->getNumSuccessors() > (unsigned)distance(C))
       return false; // Not enough args in this CHI.
 
     for (auto CHI : C) {
       BasicBlock *Dest = CHI.Dest;
       // Find if all the edges have values flowing out of BB.
       bool Found = llvm::any_of(TI->successors(), [Dest](const BasicBlock *BB) {
           return BB == Dest; });
       if (!Found)

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

 ///
 /// Since we can pick an arbitrary destination, we pick the successor with the
 /// fewest predecessors.  This should reduce the in-degree of the others.
 static unsigned GetBestDestForJumpOnUndef(BasicBlock *BB) {
   TerminatorInst *BBTerm = BB->getTerminator();
   unsigned MinSucc = 0;
   BasicBlock *TestBB = BBTerm->getSuccessor(MinSucc);
   // Compute the successor with the minimum number of predecessors.
-  unsigned MinNumPreds = std::distance(pred_begin(TestBB), pred_end(TestBB));
+  unsigned MinNumPreds = pred_size(TestBB);
   for (unsigned i = 1, e = BBTerm->getNumSuccessors(); i != e; ++i) {
     TestBB = BBTerm->getSuccessor(i);
-    unsigned NumPreds = std::distance(pred_begin(TestBB), pred_end(TestBB));
+    unsigned NumPreds = pred_size(TestBB);
     if (NumPreds < MinNumPreds) {
       MinSucc = i;
       MinNumPreds = NumPreds;
     }
   }
 
   return MinSucc;
 }
bool JumpThreadingPass::ProcessThreadableEdges(Value *Cond, BasicBlock *BB,
   // If all edges were unthreadable, we fail.
   if (PredToDestList.empty())
     return false;
 
   // If all the predecessors go to a single known successor, we want to fold,
   // not thread. By doing so, we do not need to duplicate the current block and
   // also miss potential opportunities in case we dont/cant duplicate.
   if (OnlyDest && OnlyDest != MultipleDestSentinel) {
-    if (PredWithKnownDest ==
-        (size_t)std::distance(pred_begin(BB), pred_end(BB))) {
+    if (PredWithKnownDest == (size_t)pred_size(BB)) {
       bool SeenFirstBranchToOnlyDest = false;
       std::vector <DominatorTree::UpdateType> Updates;
       Updates.reserve(BB->getTerminator()->getNumSuccessors() - 1);
       for (BasicBlock *SuccBB : successors(BB)) {
         if (SuccBB == OnlyDest && !SeenFirstBranchToOnlyDest) {
           SeenFirstBranchToOnlyDest = true; // Don't modify the first branch.
         } else {
           SuccBB->removePredecessor(BB, true); // This is unreachable successor.

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

bool MergedLoadStoreMotion::mergeStores(BasicBlock *T) {
   ++PI;
   // tail block  of a diamond/hammock?
   if (Pred0 == Pred1)
     return false; // No.
   if (PI != E)
     return false; // No. More than 2 predecessors.
 
   // #Instructions in Succ1 for Compile Time Control
-  int Size1 = std::distance(Pred1->instructionsWithoutDebug().begin(),
-                            Pred1->instructionsWithoutDebug().end());
+  int Size1 = distance(Pred1->instructionsWithoutDebug());
   int NStores = 0;
 
   for (BasicBlock::reverse_iterator RBI = Pred0->rbegin(), RBE = Pred0->rend();
        RBI != RBE;) {
 
     Instruction *I = &*RBI;
     ++RBI;
 

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

for (auto Pair : States) {
     if (!State.isConflict())
       continue;
 
     /// Create and insert a new instruction which will represent the base of
     /// the given instruction 'I'.
     auto MakeBaseInstPlaceholder = [](Instruction *I) -> Instruction* {
       if (isa<PHINode>(I)) {
         BasicBlock *BB = I->getParent();
-        int NumPreds = std::distance(pred_begin(BB), pred_end(BB));
+        int NumPreds = pred_size(BB);
         assert(NumPreds > 0 && "how did we reach here");
         std::string Name = suffixed_name_or(I, ".base", "base_phi");
         return PHINode::Create(I->getType(), NumPreds, Name, I);
       } else if (SelectInst *SI = dyn_cast<SelectInst>(I)) {
         // The undef will be replaced later
         UndefValue *Undef = UndefValue::get(SI->getType());
         std::string Name = suffixed_name_or(I, ".base", "base_select");
         return SelectInst::Create(SI->getCondition(), Undef, Undef, Name, SI);
for (auto Pair : AllocaMap) {
     Value *Def = Pair.first;
     Value *Alloca = Pair.second;
 
     // We pre-record the uses of allocas so that we dont have to worry about
     // later update that changes the user information..
 
     SmallVector<Instruction *, 20> Uses;
     // PERF: trade a linear scan for repeated reallocation
-    Uses.reserve(std::distance(Def->user_begin(), Def->user_end()));
+    Uses.reserve(Def->getNumUses());
     for (User *U : Def->users()) {
       if (!isa<ConstantExpr>(U)) {
         // If the def has a ConstantExpr use, then the def is either a
         // ConstantExpr use itself or null.  In either case
         // (recursively in the first, directly in the second), the oop
         // it is ultimately dependent on is null and this particular
         // use does not need to be fixed up.
         Uses.push_back(cast<Instruction>(U));

llvm/trunk/lib/Transforms/Utils/CloneFunction.cpp

for (unsigned phino = 0, e = PHIToResolve.size(); phino != e; ) {
     }
     
     // The loop above has removed PHI entries for those blocks that are dead
     // and has updated others.  However, if a block is live (i.e. copied over)
     // but its terminator has been changed to not go to this block, then our
     // phi nodes will have invalid entries.  Update the PHI nodes in this
     // case.
     PHINode *PN = cast<PHINode>(NewBB->begin());
-    NumPreds = std::distance(pred_begin(NewBB), pred_end(NewBB));
+    NumPreds = pred_size(NewBB);
     if (NumPreds != PN->getNumIncomingValues()) {
       assert(NumPreds < PN->getNumIncomingValues());
       // Count how many times each predecessor comes to this block.
       std::map<BasicBlock*, unsigned> PredCount;
       for (pred_iterator PI = pred_begin(NewBB), E = pred_end(NewBB);
            PI != E; ++PI)
         --PredCount[*PI];
       

llvm/trunk/lib/Transforms/Utils/Local.cpp

void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, DominatorTree *DT,
   bool ReplaceEntryBB = false;
   if (PredBB == &DestBB->getParent()->getEntryBlock())
     ReplaceEntryBB = true;
 
   // Deferred DT update: Collect all the edges that enter PredBB. These
   // dominator edges will be redirected to DestBB.
   std::vector <DominatorTree::UpdateType> Updates;
   if (DDT && !ReplaceEntryBB) {
-    Updates.reserve(1 +
-                    (2 * std::distance(pred_begin(PredBB), pred_end(PredBB))));
+    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});
       // This predecessor of PredBB may already have DestBB as a successor.
       if (llvm::find(successors(*I), DestBB) == succ_end(*I))
         Updates.push_back({DominatorTree::Insert, *I, DestBB});
     }
   }
while (isa<PHINode>(*BBI)) {
       ++BBI;
     }
   }
 
   DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB);
 
   std::vector<DominatorTree::UpdateType> Updates;
   if (DDT) {
-    Updates.reserve(1 + (2 * std::distance(pred_begin(BB), pred_end(BB))));
+    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) {
       Updates.push_back({DominatorTree::Delete, *I, BB});
       // This predecessor of BB may already have Succ as a successor.
       if (llvm::find(successors(*I), Succ) == succ_end(*I))
         Updates.push_back({DominatorTree::Insert, *I, Succ});
     }

llvm/trunk/lib/Transforms/Utils/PromoteMemoryToRegister.cpp

void RemoveFromAllocasList(unsigned &AllocaIdx) {
     Allocas[AllocaIdx] = Allocas.back();
     Allocas.pop_back();
     --AllocaIdx;
   }
 
   unsigned getNumPreds(const BasicBlock *BB) {
     unsigned &NP = BBNumPreds[BB];
     if (NP == 0)
-      NP = std::distance(pred_begin(BB), pred_end(BB)) + 1;
+      NP = pred_size(BB) + 1;
     return NP - 1;
   }
 
   void ComputeLiveInBlocks(AllocaInst *AI, AllocaInfo &Info,
                            const SmallPtrSetImpl<BasicBlock *> &DefBlocks,
                            SmallPtrSetImpl<BasicBlock *> &LiveInBlocks);
   void RenamePass(BasicBlock *BB, BasicBlock *Pred,
                   RenamePassData::ValVector &IncVals,

llvm/trunk/lib/Transforms/Utils/SimplifyCFG.cpp

 
 /// Return true if the specified terminator checks
 /// to see if a value is equal to constant integer value.
 Value *SimplifyCFGOpt::isValueEqualityComparison(TerminatorInst *TI) {
   Value *CV = nullptr;
   if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
     // Do not permit merging of large switch instructions into their
     // predecessors unless there is only one predecessor.
-    if (SI->getNumSuccessors() * std::distance(pred_begin(SI->getParent()),
-                                               pred_end(SI->getParent())) <=
-        128)
+    if (SI->getNumSuccessors() * pred_size(SI->getParent()) <= 128)
       CV = SI->getCondition();
   } else if (BranchInst *BI = dyn_cast<BranchInst>(TI))
     if (BI->isConditional() && BI->getCondition()->hasOneUse())
       if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) {
         if (ICI->isEquality() && GetConstantInt(ICI->getOperand(1), DL))
           CV = ICI->getOperand(0);
       }
 
static Value *ensureValueAvailableInSuccessor(Value *V, BasicBlock *BB,
   BasicBlock *Succ = BB->getSingleSuccessor();
 
   for (auto I = Succ->begin(); isa<PHINode>(I); ++I)
     if (cast<PHINode>(I)->getIncomingValueForBlock(BB) == V) {
       PHI = cast<PHINode>(I);
       if (!AlternativeV)
         break;
 
-      assert(std::distance(pred_begin(Succ), pred_end(Succ)) == 2);
+      assert(pred_size(Succ) == 2);
       auto PredI = pred_begin(Succ);
       BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
       if (PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
         break;
       PHI = nullptr;
     }
   if (PHI)
     return PHI;
bool SimplifyCFGOpt::SimplifyUncondBranch(BranchInst *BI,
   // If LoopHeader is provided, check if the block or its successor is a loop
   // header. (This is for early invocations before loop simplify and
   // vectorization to keep canonical loop forms for nested loops. These blocks
   // can be eliminated when the pass is invoked later in the back-end.)
   // Note that if BB has only one predecessor then we do not introduce new
   // backedge, so we can eliminate BB.
   bool NeedCanonicalLoop =
       Options.NeedCanonicalLoop &&
-      (LoopHeaders && std::distance(pred_begin(BB), pred_end(BB)) > 1 &&
+      (LoopHeaders && pred_size(BB) > 1 &&
        (LoopHeaders->count(BB) || LoopHeaders->count(Succ)));
   BasicBlock::iterator I = BB->getFirstNonPHIOrDbg()->getIterator();
   if (I->isTerminator() && BB != &BB->getParent()->getEntryBlock() &&
       !NeedCanonicalLoop && TryToSimplifyUncondBranchFromEmptyBlock(BB))
     return true;
 
   // If the only instruction in the block is a seteq/setne comparison against a
   // constant, try to simplify the block.

llvm/trunk/lib/Transforms/Vectorize/VPlan.cpp

for (auto *BB = LoopHeaderBB; BB != LoopLatchBB; BB = PostDomSucc) {
     if (PostDomSucc->getSingleSuccessor() == InterimSucc) {
       PostDomSucc = Succs[1];
       InterimSucc = Succs[0];
     }
     assert(InterimSucc->getSingleSuccessor() == PostDomSucc &&
            "One successor of a basic block does not lead to the other.");
     assert(InterimSucc->getSinglePredecessor() &&
            "Interim successor has more than one predecessor.");
-    assert(std::distance(pred_begin(PostDomSucc), pred_end(PostDomSucc)) == 2 &&
+    assert(pred_size(PostDomSucc) == 2 &&
            "PostDom successor has more than two predecessors.");
     DT->addNewBlock(InterimSucc, BB);
     DT->addNewBlock(PostDomSucc, BB);
   }
 }
 
 const Twine VPlanPrinter::getUID(const VPBlockBase *Block) {
   return (isa<VPRegionBlock>(Block) ? "cluster_N" : "N") +

llvm/trunk/unittests/ADT/IteratorTest.cpp

for (auto tup : make_filter_range(reverse(zipped), odds)) {
     EXPECT_TRUE(get<0>(tup) & 0x01);
     get<0>(tup) += 1;
   }
 
   // Ensure that in-place mutation works.
   EXPECT_TRUE(all_of(ascending, [](unsigned n) { return (n & 0x01) == 0; }));
 }
 
+TEST(RangeTest, Distance) {
+  std::vector<int> v1;
+  std::vector<int> v2{1, 2, 3};
+
+  EXPECT_EQ(std::distance(v1.begin(), v1.end()), distance(v1));
+  EXPECT_EQ(std::distance(v2.begin(), v2.end()), distance(v2));
+}
+
 } // anonymous namespace

llvm/trunk/unittests/IR/BasicBlockTest.cpp

TEST(BasicBlockTest, PhiRange) {
   BasicBlock::const_phi_iterator CI;
   CI = BB->phis().begin();
   EXPECT_NE(CI, BB->phis().end());
 
   // Test that filtering iterators work with basic blocks.
   auto isPhi = [](Instruction &I) { return isa<PHINode>(&I); };
   auto Phis = make_filter_range(*BB, isPhi);
   auto ReversedPhis = reverse(make_filter_range(*BB, isPhi));
-  EXPECT_EQ(std::distance(Phis.begin(), Phis.end()), 3);
+  EXPECT_EQ(distance(Phis), 3);
   EXPECT_EQ(&*Phis.begin(), P1);
-  EXPECT_EQ(std::distance(ReversedPhis.begin(), ReversedPhis.end()), 3);
+  EXPECT_EQ(distance(ReversedPhis), 3);
   EXPECT_EQ(&*ReversedPhis.begin(), P3);
 
   // And iterate a const range.
   for (const auto &PN : const_cast<const BasicBlock *>(BB.get())->phis()) {
     EXPECT_EQ(BB.get(), PN.getIncomingBlock(0));
     EXPECT_EQ(BB1.get(), PN.getIncomingBlock(1));
     EXPECT_EQ(BB2.get(), PN.getIncomingBlock(2));
   }
 }
 
 #define CHECK_ITERATORS(Range1, Range2)                                        \
-  EXPECT_EQ(std::distance(Range1.begin(), Range1.end()),                       \
-            std::distance(Range2.begin(), Range2.end()));                      \
+  EXPECT_EQ(distance(Range1), distance(Range2));                               \
   for (auto Pair : zip(Range1, Range2))                                        \
     EXPECT_EQ(&std::get<0>(Pair), std::get<1>(Pair));
 
 TEST(BasicBlockTest, TestInstructionsWithoutDebug) {
   LLVMContext Ctx;
 
   Module *M = new Module("MyModule", Ctx);
   Type *ArgTy1[] = {Type::getInt32PtrTy(Ctx)};