1 files changed, 103 insertions, 19 deletions

diff --git a/contrib/llvm/lib/Analysis/CaptureTracking.cpp b/contrib/llvm/lib/Analysis/CaptureTracking.cpp
index 79fab1be4413..f2f8877af1a2 100644
--- a/contrib/llvm/lib/Analysis/CaptureTracking.cpp
+++ b/contrib/llvm/lib/Analysis/CaptureTracking.cpp
@@ -20,24 +20,26 @@
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/CaptureTracking.h"
+#include "llvm/Analysis/CFG.h"
+#include "llvm/IR/CallSite.h"
 #include "llvm/IR/Constants.h"
+#include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
-#include "llvm/Support/CallSite.h"
 
 using namespace llvm;
 
 CaptureTracker::~CaptureTracker() {}
 
-bool CaptureTracker::shouldExplore(Use *U) { return true; }
+bool CaptureTracker::shouldExplore(const Use *U) { return true; }
 
 namespace {
   struct SimpleCaptureTracker : public CaptureTracker {
     explicit SimpleCaptureTracker(bool ReturnCaptures)
       : ReturnCaptures(ReturnCaptures), Captured(false) {}
 
-    void tooManyUses() { Captured = true; }
+    void tooManyUses() override { Captured = true; }
 
-    bool captured(Use *U) {
+    bool captured(const Use *U) override {
       if (isa<ReturnInst>(U->getUser()) && !ReturnCaptures)
         return false;
 
@@ -49,6 +51,65 @@ namespace {
 
     bool Captured;
   };
+
+  /// Only find pointer captures which happen before the given instruction. Uses
+  /// the dominator tree to determine whether one instruction is before another.
+  /// Only support the case where the Value is defined in the same basic block
+  /// as the given instruction and the use.
+  struct CapturesBefore : public CaptureTracker {
+    CapturesBefore(bool ReturnCaptures, const Instruction *I, DominatorTree *DT,
+                   bool IncludeI)
+      : BeforeHere(I), DT(DT), ReturnCaptures(ReturnCaptures),
+        IncludeI(IncludeI), Captured(false) {}
+
+    void tooManyUses() override { Captured = true; }
+
+    bool shouldExplore(const Use *U) override {
+      Instruction *I = cast<Instruction>(U->getUser());
+      if (BeforeHere == I && !IncludeI)
+        return false;
+
+      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;
+      // 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;
+    }
+
+    bool captured(const Use *U) override {
+      if (isa<ReturnInst>(U->getUser()) && !ReturnCaptures)
+        return false;
+
+      Instruction *I = cast<Instruction>(U->getUser());
+      if (BeforeHere == I && !IncludeI)
+        return false;
+
+      BasicBlock *BB = I->getParent();
+      // Same logic as in shouldExplore.
+      if (BeforeHere != I && !DT->isReachableFromEntry(BB))
+        return false;
+      if (BeforeHere != I && DT->dominates(BeforeHere, I) &&
+          !isPotentiallyReachable(I, BeforeHere, DT))
+        return false;
+      Captured = true;
+      return true;
+    }
+
+    const Instruction *BeforeHere;
+    DominatorTree *DT;
+
+    bool ReturnCaptures;
+    bool IncludeI;
+
+    bool Captured;
+  };
 }
 
 /// PointerMayBeCaptured - Return true if this pointer value may be captured
@@ -74,6 +135,32 @@ bool llvm::PointerMayBeCaptured(const Value *V,
   return SCT.Captured;
 }
 
+/// PointerMayBeCapturedBefore - Return true if this pointer value may be
+/// captured by the enclosing function (which is required to exist). If a
+/// DominatorTree is provided, only captures which happen before the given
+/// instruction are considered. This routine can be expensive, so consider
+/// caching the results.  The boolean ReturnCaptures specifies whether
+/// returning the value (or part of it) from the function counts as capturing
+/// it or not.  The boolean StoreCaptures specified whether storing the value
+/// (or part of it) into memory anywhere automatically counts as capturing it
+/// or not.
+bool llvm::PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures,
+                                      bool StoreCaptures, const Instruction *I,
+                                      DominatorTree *DT, bool IncludeI) {
+  assert(!isa<GlobalValue>(V) &&
+         "It doesn't make sense to ask whether a global is captured.");
+
+  if (!DT)
+    return PointerMayBeCaptured(V, ReturnCaptures, StoreCaptures);
+
+  // TODO: See comment in PointerMayBeCaptured regarding what could be done
+  // with StoreCaptures.
+
+  CapturesBefore CB(ReturnCaptures, I, DT, IncludeI);
+  PointerMayBeCaptured(V, &CB);
+  return CB.Captured;
+}
+
 /// TODO: Write a new FunctionPass AliasAnalysis so that it can keep
 /// a cache. Then we can move the code from BasicAliasAnalysis into
 /// that path, and remove this threshold.
@@ -81,25 +168,23 @@ static int const Threshold = 20;
 
 void llvm::PointerMayBeCaptured(const Value *V, CaptureTracker *Tracker) {
   assert(V->getType()->isPointerTy() && "Capture is for pointers only!");
-  SmallVector<Use*, Threshold> Worklist;
-  SmallSet<Use*, Threshold> Visited;
+  SmallVector<const Use *, Threshold> Worklist;
+  SmallSet<const Use *, Threshold> Visited;
   int Count = 0;
 
-  for (Value::const_use_iterator UI = V->use_begin(), UE = V->use_end();
-       UI != UE; ++UI) {
+  for (const Use &U : V->uses()) {
     // 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();
 
-    Use *U = &UI.getUse();
-    if (!Tracker->shouldExplore(U)) continue;
-    Visited.insert(U);
-    Worklist.push_back(U);
+    if (!Tracker->shouldExplore(&U)) continue;
+    Visited.insert(&U);
+    Worklist.push_back(&U);
   }
 
   while (!Worklist.empty()) {
-    Use *U = Worklist.pop_back_val();
+    const Use *U = Worklist.pop_back_val();
     Instruction *I = cast<Instruction>(U->getUser());
     V = U->get();
 
@@ -145,19 +230,18 @@ void llvm::PointerMayBeCaptured(const Value *V, CaptureTracker *Tracker) {
     case Instruction::GetElementPtr:
     case Instruction::PHI:
     case Instruction::Select:
+    case Instruction::AddrSpaceCast:
       // The original value is not captured via this if the new value isn't.
       Count = 0;
-      for (Instruction::use_iterator UI = I->use_begin(), UE = I->use_end();
-           UI != UE; ++UI) {
+      for (Use &UU : I->uses()) {
         // 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();
 
-        Use *U = &UI.getUse();
-        if (Visited.insert(U))
-          if (Tracker->shouldExplore(U))
-            Worklist.push_back(U);
+        if (Visited.insert(&UU))
+          if (Tracker->shouldExplore(&UU))
+            Worklist.push_back(&UU);
       }
       break;
     case Instruction::ICmp: