Index: include/llvm/ADT/STLExtras.h
===================================================================
--- include/llvm/ADT/STLExtras.h
+++ include/llvm/ADT/STLExtras.h
@@ -1026,9 +1026,14 @@
   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());
 }
Index: lib/Analysis/LazyCallGraph.cpp
===================================================================
--- lib/Analysis/LazyCallGraph.cpp
+++ lib/Analysis/LazyCallGraph.cpp
@@ -1273,7 +1273,7 @@
       // 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;
@@ -1739,7 +1739,7 @@
 }
 
 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)
@@ -1747,7 +1747,7 @@
 }
 
 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)
Index: lib/CodeGen/ImplicitNullChecks.cpp
===================================================================
--- lib/CodeGen/ImplicitNullChecks.cpp
+++ lib/CodeGen/ImplicitNullChecks.cpp
@@ -597,7 +597,7 @@
   unsigned DefReg = NoRegister;
   if (NumDefs != 0) {
     DefReg = MI->defs().begin()->getReg();
-    assert(distance(MI->defs()) == 1 && "expected exactly one def!");
+    assert(size(MI->defs()) == 1 && "expected exactly one def!");
   }
 
   FaultMaps::FaultKind FK;
Index: lib/IR/Value.cpp
===================================================================
--- lib/IR/Value.cpp
+++ lib/IR/Value.cpp
@@ -167,7 +167,9 @@
   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;
Index: lib/Transforms/Scalar/GVNHoist.cpp
===================================================================
--- lib/Transforms/Scalar/GVNHoist.cpp
+++ lib/Transforms/Scalar/GVNHoist.cpp
@@ -578,7 +578,7 @@
 
   // 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) {
Index: lib/Transforms/Scalar/MergedLoadStoreMotion.cpp
===================================================================
--- lib/Transforms/Scalar/MergedLoadStoreMotion.cpp
+++ lib/Transforms/Scalar/MergedLoadStoreMotion.cpp
@@ -285,7 +285,8 @@
     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();
Index: unittests/ADT/IteratorTest.cpp
===================================================================
--- unittests/ADT/IteratorTest.cpp
+++ unittests/ADT/IteratorTest.cpp
@@ -369,8 +369,8 @@
   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
Index: unittests/IR/BasicBlockTest.cpp
===================================================================
--- unittests/IR/BasicBlockTest.cpp
+++ unittests/IR/BasicBlockTest.cpp
@@ -73,9 +73,9 @@
   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.
@@ -87,7 +87,8 @@
 }
 
 #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));