[STLExtras] Add size() for ranges, and remove distance()

[vsk]

Summary

r332057 introduced distance() for ranges. Based on post-commit feedback,
this renames distance() to size(). The new size() is also only enabled
when the operation is O(1).

[dblaikie]

I'm good with this (since I suggested it) if @craig.topper is.

[craig.topper]

LGTM

lib/CodeGen/ImplicitNullChecks.cpp

600 ↗

(On Diff #147177)

Can you just change this to NumDefs == 1? The end for defs() is calculated with MI->getDesc().getNumDefs() which is what NumDefs is assigned to.

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.
+/// Get the size of a range. This is a wrapper function around std::distance
+/// which is only enabled when the operation is O(1).
 template <typename R>
-auto distance(R &&Range)
+auto size(R &&Range, typename std::enable_if<
+                         std::is_same<typename std::iterator_traits<decltype(
+                                          Range.begin())>::iterator_category,
+                                      std::random_access_iterator_tag>::value,
+                         void>::type * = nullptr)
     -> decltype(std::distance(Range.begin(), Range.end())) {
   return std::distance(Range.begin(), Range.end());
 }
 
 //===----------------------------------------------------------------------===//
 //     Extra additions to <memory>
 //===----------------------------------------------------------------------===//
 

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 (distance(RefSCCNodes) == NumRefSCCNodes) {
+      if (llvm::size(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 = distance(C);
+  ptrdiff_t Size = size(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 = distance(C);
+  ptrdiff_t Size = size(C);
   OS << "  RefSCC with " << Size << " call SCCs:\n";
 
   for (LazyCallGraph::SCC &InnerC : C)
     printSCC(OS, InnerC);
 
   OS << "\n";
 }
 

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(distance(MI->defs()) == 1 && "expected exactly one def!");
+    assert(NumDefs == 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/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)distance(uses()); }
+unsigned Value::getNumUses() const {
+  return (unsigned)std::distance(use_begin(), use_end());
+}
 
 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/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)distance(C))
+    if (TI->getNumSuccessors() > (unsigned)size(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/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 = distance(Pred1->instructionsWithoutDebug());
+  auto InstsNoDbg = Pred1->instructionsWithoutDebug();
+  int Size1 = std::distance(InstsNoDbg.begin(), InstsNoDbg.end());
   int NStores = 0;
 
   for (BasicBlock::reverse_iterator RBI = Pred0->rbegin(), RBE = Pred0->rend();
        RBI != RBE;) {
 
     Instruction *I = &*RBI;
     ++RBI;
 

llvm/trunk/unittests/ADT/IteratorTest.cpp

TEST(ZipIteratorTest, Reverse) {
   // 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));
+  EXPECT_EQ(std::distance(v1.begin(), v1.end()), size(v1));
+  EXPECT_EQ(std::distance(v2.begin(), v2.end()), size(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(distance(Phis), 3);
+  EXPECT_EQ(std::distance(Phis.begin(), Phis.end()), 3);
   EXPECT_EQ(&*Phis.begin(), P1);
-  EXPECT_EQ(distance(ReversedPhis), 3);
+  EXPECT_EQ(std::distance(ReversedPhis.begin(), ReversedPhis.end()), 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(distance(Range1), distance(Range2));                               \
+  EXPECT_EQ(std::distance(Range1.begin(), Range1.end()),                       \
+            std::distance(Range2.begin(), Range2.end()));                      \
   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)};