Index: include/llvm/Analysis/CaptureTracking.h
===================================================================
--- include/llvm/Analysis/CaptureTracking.h
+++ include/llvm/Analysis/CaptureTracking.h
@@ -50,18 +50,28 @@
   /// addition to the interface here, you'll need to provide your own getters
   /// to see whether anything was captured.
   struct CaptureTracker {
+
+    /// Action - The possible actions shouldExplore must return.
+    enum Action {
+      Search,
+      Prune,
+      TooExpensive
+    };
+
     virtual ~CaptureTracker();
 
-    /// tooManyUses - The depth of traversal has breached a limit. There may be
+    /// tooExpensive - The depth of traversal or the number of instructions
+    /// to search inside a basic block has breached a limit. There may be
     /// capturing instructions that will not be passed into captured().
-    virtual void tooManyUses() = 0;
+    virtual void tooExpensive() = 0;
 
-    /// shouldExplore - This is the use of a value derived from the pointer.
-    /// To prune the search (ie., assume that none of its users could possibly
-    /// capture) return false. To search it, return true.
+    /// shouldExplore - This is the use of a value derived from the pointer. To
+    /// prune the search (ie., assume that none of its users could possibly
+    /// capture) return Action::Prune. To search it, return Action::Search.
+    /// To avoid really expensive compile time, return Action::TooExpensive.
     ///
     /// U->getUser() is always an Instruction.
-    virtual bool shouldExplore(const Use *U);
+    virtual Action shouldExplore(const Use *U);
 
     /// captured - Information about the pointer was captured by the user of
     /// use U. Return true to stop the traversal or false to continue looking
Index: lib/Analysis/CaptureTracking.cpp
===================================================================
--- lib/Analysis/CaptureTracking.cpp
+++ lib/Analysis/CaptureTracking.cpp
@@ -30,14 +30,15 @@
 
 CaptureTracker::~CaptureTracker() {}
 
-bool CaptureTracker::shouldExplore(const Use *U) { return true; }
+CaptureTracker::Action CaptureTracker::shouldExplore(const Use *U)
+  { return CaptureTracker::Search; }
 
 namespace {
   struct SimpleCaptureTracker : public CaptureTracker {
     explicit SimpleCaptureTracker(bool ReturnCaptures)
       : ReturnCaptures(ReturnCaptures), Captured(false) {}
 
-    void tooManyUses() override { Captured = true; }
+    void tooExpensive() override { Captured = true; }
 
     bool captured(const Use *U) override {
       if (isa<ReturnInst>(U->getUser()) && !ReturnCaptures)
@@ -62,25 +63,59 @@
       : BeforeHere(I), DT(DT), ReturnCaptures(ReturnCaptures),
         IncludeI(IncludeI), Captured(false) {}
 
-    void tooManyUses() override { Captured = true; }
+    void tooExpensive() override { Captured = true; }
 
-    bool shouldExplore(const Use *U) override {
+    // Limit for the number of instructions to scan in a block.
+    static const unsigned int BlockScanLimit = 1000;
+
+    CaptureTracker::Action shouldExplore(const Use *U) override {
       Instruction *I = cast<Instruction>(U->getUser());
+
       if (BeforeHere == I && !IncludeI)
-        return false;
+        return CaptureTracker::Prune;
 
       BasicBlock *BB = I->getParent();
       // We explore this usage only if the usage can reach "BeforeHere".
       // If use is not reachable from entry, there is no need to explore.
       if (BeforeHere != I && !DT->isReachableFromEntry(BB))
-        return false;
+        return CaptureTracker::Prune;
+
+      // Early compute the case where both instructions are inside the same
+      // basic block and limit the number of instructions to search. We avoid
+      // using 'dominates' and 'isPotentiallyReachable' since both get very
+      // expensive in large basic block scenarios.
+      if (BB == BeforeHere->getParent()) {
+        if (BeforeHere == I)
+          return CaptureTracker::Search;
+
+        // Loop through the basic block until we find BeforeHere or I.
+        unsigned int Limit = BlockScanLimit;
+        BasicBlock::const_iterator II = BB->begin();
+        for (; Limit && &*II != BeforeHere && &*II != I; ++II, --Limit)
+          /*empty*/;
+
+        if (!Limit)
+          return CaptureTracker::TooExpensive;
+
+        // BeforeHere dominates I, we can also conservatively assume there's no
+        // path from I to BeforeHere if we're on the entry block or if there are
+        // no BB successors.
+        if (BeforeHere != I && &*II == BeforeHere &&
+            (BB == &BB->getParent()->getEntryBlock() ||
+             !BB->getTerminator()->getNumSuccessors()))
+          return CaptureTracker::Prune;
+
+        return CaptureTracker::Search;
+      }
+
       // If the value is defined in the same basic block as use and BeforeHere,
       // there is no need to explore the use if BeforeHere dominates use.
       // Check whether there is a path from I to BeforeHere.
       if (BeforeHere != I && DT->dominates(BeforeHere, I) &&
           !isPotentiallyReachable(I, BeforeHere, DT))
-        return false;
-      return true;
+        return CaptureTracker::Prune;
+
+      return CaptureTracker::Search;
     }
 
     bool captured(const Use *U) override {
@@ -176,9 +211,14 @@
     // If there are lots of uses, conservatively say that the value
     // is captured to avoid taking too much compile time.
     if (Count++ >= Threshold)
-      return Tracker->tooManyUses();
+      return Tracker->tooExpensive();
+
+    CaptureTracker::Action Res = Tracker->shouldExplore(&U);
+    if (Res == CaptureTracker::TooExpensive)
+      return Tracker->tooExpensive();
+    if (Res == CaptureTracker::Prune)
+      continue;
 
-    if (!Tracker->shouldExplore(&U)) continue;
     Visited.insert(&U);
     Worklist.push_back(&U);
   }
@@ -237,11 +277,16 @@
         // If there are lots of uses, conservatively say that the value
         // is captured to avoid taking too much compile time.
         if (Count++ >= Threshold)
-          return Tracker->tooManyUses();
+          return Tracker->tooExpensive();
+
+        if (Visited.insert(&UU).second) {
+          CaptureTracker::Action Res = Tracker->shouldExplore(&UU);
 
-        if (Visited.insert(&UU).second)
-          if (Tracker->shouldExplore(&UU))
+          if (Res == CaptureTracker::Search)
             Worklist.push_back(&UU);
+          if (Res == CaptureTracker::TooExpensive)
+            return Tracker->tooExpensive();
+        }
       }
       break;
     case Instruction::ICmp:
Index: lib/Transforms/IPO/FunctionAttrs.cpp
===================================================================
--- lib/Transforms/IPO/FunctionAttrs.cpp
+++ lib/Transforms/IPO/FunctionAttrs.cpp
@@ -346,7 +346,7 @@
     ArgumentUsesTracker(const SmallPtrSet<Function*, 8> &SCCNodes)
       : Captured(false), SCCNodes(SCCNodes) {}
 
-    void tooManyUses() override { Captured = true; }
+    void tooExpensive() override { Captured = true; }
 
     bool captured(const Use *U) override {
       CallSite CS(U->getUser());