[CaptureTracking] Add optimistic capture tracker for stores

[JDevlieghere]

Summary

The current capture tracking implementation always considers a store instruction to capture the given use. The example below shows a situation where this is overly pessimistic. The current implementation considers %ptr to be captured because it's the operand of the second store.

define void @sample() {
entry:
  %ptr = alloca i32
  store i32 1, i32* %ptr
  %ptrtoptr = alloca i32*
  store i32* %ptr, i32** %ptrtoptr
  ret void
}

This patch adds a new capture tracker implementation called OptimisticCaptureTracker. It can be used through a slightly modified interface that expects alias analysis results as an additional argument. If storeCaptures is set to true or no AA is provided, the OptimisticCaptureTracker behaves exactly as the current SimpleCaptureTracker. Otherwise, it only consider %ptr to escape in the previous example if it is stored to either a global or to one of the arguments of the function.

[hfinkel]

Otherwise, it only consider %ptr to escape in the previous example if it is stored to either a global or to one of the arguments of the function.

I suppose this is named "optimistic" because it might return a false negative? If the pointer value is stored into some alloca then read and the read value stored into some global, then the value is captured but your analysis will return false. Is this what you intend?

[JDevlieghere]

In D27585#621863, @hfinkel wrote:

Otherwise, it only consider %ptr to escape in the previous example if it is stored to either a global or to one of the arguments of the function.

I suppose this is named "optimistic" because it might return a false negative? If the pointer value is stored into some alloca then read and the read value stored into some global, then the value is captured but your analysis will return false. Is this what you intend?

Does the example below cover what you have in mind?

@global = external global i32*

define void @sample() {
entry:
  %ptr = alloca i32
  store i32 1, i32* %ptr
  %ptrtoptr = alloca i32*
  store i32* %ptr, i32** %ptrtoptr
  %deref = load i32*, i32** %ptrtoptr
  store i32* %deref , i32** @global
  ret void
}

If so, the escape of %ptr is properly detected by my change. I have a small printer pass for capture tracking which enables me to easily verify this kind of stuff. I will update my diff to include it, we can always remove it again later.

[JDevlieghere]

Added small printer pass for capture tracking.

[hfinkel]

In D27585#621980, @JDevlieghere wrote:

In D27585#621863, @hfinkel wrote:

Otherwise, it only consider %ptr to escape in the previous example if it is stored to either a global or to one of the arguments of the function.

I suppose this is named "optimistic" because it might return a false negative? If the pointer value is stored into some alloca then read and the read value stored into some global, then the value is captured but your analysis will return false. Is this what you intend?

Does the example below cover what you have in mind?

@global = external global i32*

define void @sample() {
entry:
  %ptr = alloca i32
  store i32 1, i32* %ptr
  %ptrtoptr = alloca i32*
  store i32* %ptr, i32** %ptrtoptr
  %deref = load i32*, i32** %ptrtoptr
  store i32* %deref , i32** @global
  ret void
}

If so, the escape of %ptr is properly detected by my change. I have a small printer pass for capture tracking which enables me to easily verify this kind of stuff. I will update my diff to include it, we can always remove it again later.

Can you please explain how this is detected? The store is to an alloca, and I don't believe that the system does any kind of memory-based data-flow tracking.

In any cases, some regression test cases will be necessary.

lib/Analysis/CaptureTracking.cpp

81

An Argument is always a Value, so this cast/check should never be necessary.

82

This check won't work correctly if the value is stored into some offset based on the argument. You can make the right kind of query, but only if you construct a Location with an unknown size based on the value.

90

Again, this cast/check is not necessary (a Global is always a Value).

91

Same comment here about the size/offset issue.

101

Remove this blank line.

218

Add a space in between the for and the ( [same for the lines below for for/if].

[JDevlieghere]

• Addressed @hfinkel's comments
• Added a few simple tests

[JDevlieghere]

• Fixed style comment (not sure why clang-format missed it?)
• Only print values that have a name

[JDevlieghere]

In D27585#622381, @hfinkel wrote:

In D27585#621980, @JDevlieghere wrote:

In D27585#621863, @hfinkel wrote:

Otherwise, it only consider %ptr to escape in the previous example if it is stored to either a global or to one of the arguments of the function.

I suppose this is named "optimistic" because it might return a false negative? If the pointer value is stored into some alloca then read and the read value stored into some global, then the value is captured but your analysis will return false. Is this what you intend?

Does the example below cover what you have in mind?

@global = external global i32*

define void @sample() {
entry:
  %ptr = alloca i32
  store i32 1, i32* %ptr
  %ptrtoptr = alloca i32*
  store i32* %ptr, i32** %ptrtoptr
  %deref = load i32*, i32** %ptrtoptr
  store i32* %deref , i32** @global
  ret void
}

If so, the escape of %ptr is properly detected by my change. I have a small printer pass for capture tracking which enables me to easily verify this kind of stuff. I will update my diff to include it, we can always remove it again later.

Can you please explain how this is detected? The store is to an alloca, and I don't believe that the system does any kind of memory-based data-flow tracking.

I don't know enough about AA to make a definitive statement about this. Conceptually, everything makes sense up the isNoAlias call. The two pointers do point to the same value, so assuming a perfect AA implementation, the results is not totally unexpected. Maybe the default is very conservative and says that's it can't say for sure that the pointer and the global don't alias. As a result the pointer is considered to be captured. The test case I added for storing to the function argument behaves exactly the same, it reports the pointer being captured as desired. I'll dig deeper into AA, because I want to understand what happens, but for now this is the best explanation I can give.

In any cases, some regression test cases will be necessary.

I've added 3 tests to illustrate the added merit of this change. Since the printer pass makes it easy to test the current CT implementation, I'm planning on adding more tests for the other parts of the algorithm in a separate differential.

[hfinkel]

In D27585#622547, @JDevlieghere wrote:

In D27585#622381, @hfinkel wrote:

In D27585#621980, @JDevlieghere wrote:

In D27585#621863, @hfinkel wrote:

Otherwise, it only consider %ptr to escape in the previous example if it is stored to either a global or to one of the arguments of the function.

I suppose this is named "optimistic" because it might return a false negative? If the pointer value is stored into some alloca then read and the read value stored into some global, then the value is captured but your analysis will return false. Is this what you intend?

Does the example below cover what you have in mind?

@global = external global i32*

define void @sample() {
entry:
  %ptr = alloca i32
  store i32 1, i32* %ptr
  %ptrtoptr = alloca i32*
  store i32* %ptr, i32** %ptrtoptr
  %deref = load i32*, i32** %ptrtoptr
  store i32* %deref , i32** @global
  ret void
}

If so, the escape of %ptr is properly detected by my change. I have a small printer pass for capture tracking which enables me to easily verify this kind of stuff. I will update my diff to include it, we can always remove it again later.

Can you please explain how this is detected? The store is to an alloca, and I don't believe that the system does any kind of memory-based data-flow tracking.

I don't know enough about AA to make a definitive statement about this. Conceptually, everything makes sense up the isNoAlias call. The two pointers do point to the same value, so assuming a perfect AA implementation, the results is not totally unexpected. Maybe the default is very conservative and says that's it can't say for sure that the pointer and the global don't alias. As a result the pointer is considered to be captured. The test case I added for storing to the function argument behaves exactly the same, it reports the pointer being captured as desired. I'll dig deeper into AA, because I want to understand what happens, but for now this is the best explanation I can give.

Yea, we need to figure this out. Do you have BasicAA enabled? What happens if you add -aa-pipeline=basic-aa to the opt command?

In any cases, some regression test cases will be necessary.

I've added 3 tests to illustrate the added merit of this change. Since the printer pass makes it easy to test the current CT implementation, I'm planning on adding more tests for the other parts of the algorithm in a separate differential.

[JDevlieghere]

In D27585#623234, @hfinkel wrote:

Yea, we need to figure this out. Do you have BasicAA enabled? What happens if you add -aa-pipeline=basic-aa to the opt command?

With basic AA it is indeed not working; The results are only as good as the AA method provided, and in a sense it's optimistic in that regard. Would you agree that this is fair behavior, because the interface explicitly expects AA results and a flag indicating whether or not a store should capture? This would need to be documented of course.

[hfinkel]

In D27585#623431, @JDevlieghere wrote:

In D27585#623234, @hfinkel wrote:

Yea, we need to figure this out. Do you have BasicAA enabled? What happens if you add -aa-pipeline=basic-aa to the opt command?

With basic AA it is indeed not working; The results are only as good as the AA method provided, and in a sense it's optimistic in that regard. Would you agree that this is fair behavior, because the interface explicitly expects AA results and a flag indicating whether or not a store should capture? This would need to be documented of course.

Can you explain the use case for a capture-tracking mode that might return false negatives?

[JDevlieghere]

Let's consider the following table:

	No AA	Basic AA	Advanced AA
Current Capture Tracking	false positives (a)	n/a	n/a
Optimistic Capture Tracking	false positives (b)	false negatives (c)	less false positives (d)

Right now, only situation (a) exists, where we get false positives for stores to non-aliasing function arguments and globals, as illustrated by the example in the original description of this patch. Optimistic capture tracking behaves exactly the same if no AA is provided, so situation (a) and (b) are identical.

The interesting cases are (c) and (d), especially in combination with the situation you described, where a "value is stored into some alloca then read and the read value stored into some global".

• For (c), basic AA doesn't perform memory-based data-flow tracking and it returns a false negative, which in turn causes the optimistic capture tracker to return a false negative as well. Returning a false negative is less desirable than returning a false positive, i.e. situation (a). So I suggest we enforce that this scenario can not occur, e.g. with an assert.
• For (d), it properly detects that the two variables might alias, and we reduce the set of false positives generated by stores to globals and function argument. The lit tests verify this.

The net result is that we ether end up in (a) or (d) which is in my opinion more desirable than what we currently have.

[JDevlieghere]

ping

[sanjoy]

In D27585#623685, @JDevlieghere wrote:

Let's consider the following table:

	No AA	Basic AA	Advanced AA
Current Capture Tracking	false positives (a)	n/a	n/a
Optimistic Capture Tracking	false positives (b)	false negatives (c)	less false positives (d)

Right now, only situation (a) exists, where we get false positives for stores to non-aliasing function arguments and globals, as illustrated by the example in the original description of this patch. Optimistic capture tracking behaves exactly the same if no AA is provided, so situation (a) and (b) are identical.

The interesting cases are (c) and (d), especially in combination with the situation you described, where a "value is stored into some alloca then read and the read value stored into some global".

• For (c), basic AA doesn't perform memory-based data-flow tracking and it returns a false negative, which in turn causes the optimistic capture tracker to return a false negative as well. Returning a false negative is less desirable than returning a false positive, i.e. situation (a). So I suggest we enforce that this scenario can not occur, e.g. with an assert.

What would you assert? That is, what would the assert look like?

• For (d), it properly detects that the two variables might alias, and we reduce the set of false positives generated by stores to globals and function argument. The lit tests verify this.

Which lit test?

In any case we can't rely on the AA being smart or advanced for correctness. That is, a less aggressive / more conservative AA should not cause us to miscompile code.

The net result is that we ether end up in (a) or (c) which is in my opinion more desirable than what we currently have.

Optimizations based on (c) will generally be incorrect and so (a) or (c) is less desirable than (a). That is, (a) == "always correct", (a) or (c) == "sometimes wrong".

I think Hal's question was more of the tune of: do you have optimizations that will be correct even with false negatives? That is, even if the optimization thinks a value did not escape when it actually did, the transform it does will be be correct? If so, that is interestingly different from what LLVM does today, and worth discussion _before_ we add this new capture tracker to LLVM.

[sanjoy]

As per previous comment.

[hfinkel]

In D27585#630030, @sanjoy wrote:

In D27585#623685, @JDevlieghere wrote:

Let's consider the following table:

...

I think Hal's question was more of the tune of: do you have optimizations that will be correct even with false negatives? That is, even if the optimization thinks a value did not escape when it actually did, the transform it does will be be correct? If so, that is interestingly different from what LLVM does today, and worth discussion _before_ we add this new capture tracker to LLVM.

Yes, this is exactly what I'd like to know.

[JDevlieghere]

In D27585#630030, @sanjoy wrote:

In D27585#623685, @JDevlieghere wrote:

Let's consider the following table:

	No AA	Basic AA	Advanced AA
Current Capture Tracking	false positives (a)	n/a	n/a
Optimistic Capture Tracking	false positives (b)	false negatives (c)	less false positives (d)

Right now, only situation (a) exists, where we get false positives for stores to non-aliasing function arguments and globals, as illustrated by the example in the original description of this patch. Optimistic capture tracking behaves exactly the same if no AA is provided, so situation (a) and (b) are identical.

The interesting cases are (c) and (d), especially in combination with the situation you described, where a "value is stored into some alloca then read and the read value stored into some global".

• For (c), basic AA doesn't perform memory-based data-flow tracking and it returns a false negative, which in turn causes the optimistic capture tracker to return a false negative as well. Returning a false negative is less desirable than returning a false positive, i.e. situation (a). So I suggest we enforce that this scenario can not occur, e.g. with an assert.

What would you assert? That is, what would the assert look like?

Originally I wanted to assert the algorithm used for AA. However, now I understand that unless the AA algorithm is perfect, there will always be a case where this generates a false negative. What I'd need for this to work properly is for AA to provide a guaranteed must not alias result. Unfortunately for me, this is inherently incompatible with what we have now. LLVM is (correctly) conservative in saying that something aliases, while I would need an implementation that is conservative in saying that something does not alias.

• For (d), it properly detects that the two variables might alias, and we reduce the set of false positives generated by stores to globals and function argument. The lit tests verify this.

Which lit test?

captureindirectstore.ll

In any case we can't rely on the AA being smart or advanced for correctness. That is, a less aggressive / more conservative AA should not cause us to miscompile code.

Of course, this goes without saying!

The net result is that we ether end up in (a) or (c) which is in my opinion more desirable than what we currently have.

Optimizations based on (c) will generally be incorrect and so (a) or (c) is less desirable than (a). That is, (a) == "always correct", (a) or (c) == "sometimes wrong".

This was a typo on my part, it should've said (a) or (d). However, it doesn't really matter anymore, because of the reason I mentioned above.

I think Hal's question was more of the tune of: do you have optimizations that will be correct even with false negatives? That is, even if the optimization thinks a value did not escape when it actually did, the transform it does will be be correct? If so, that is interestingly different from what LLVM does today, and worth discussion _before_ we add this new capture tracker to LLVM.

No, I don't have an optimization that can deal with a false negative. I originally extended the capture tracker because I ran into a lot of false negatives for my use cases. This extension made sense from a theoretical point of view, and after testing it, I was able to correctly classify every case I could come up with. I think I confused both you and myself by calling it optimistic. I didn't mean for it to be optimistic in the sense that it would misclassify captures, rather that it could do better than what we currently have with the help of AA. Anyway, now I understand that I can't guarantee my desired scenario (d). I don't really see a way around this limitation, without implementing a inverse-conservative variant of AA.

Do you guys have an alternative idea for reducing the amount of false positives? If not I guess I'll have to abandon this change. :-(

In D27585#630064, @hfinkel wrote:

Yes, this is exactly what I'd like to know.

Thank you both for the clarification. I guess I must have misunderstood the question, sorry!

[hfinkel]

In D27585#631486, @JDevlieghere wrote:

In D27585#630030, @sanjoy wrote:

In D27585#623685, @JDevlieghere wrote:

Let's consider the following table:

...

Do you guys have an alternative idea for reducing the amount of false positives? If not I guess I'll have to abandon this change. :-(

To literally do what you'd like, you'll need to do some kind of data-flow analysis. This is possible, but first we should understand the use case. Specifically, why are the variables in question being stored such that the values don't escape but nevertheless mem2reg is not promoting them to SSA values.

include/llvm/Analysis/CaptureTracking.h

 //===----- llvm/Analysis/CaptureTracking.h - Pointer capture ----*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file contains routines that help determine which pointers are captured.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_CAPTURETRACKING_H
 #define LLVM_ANALYSIS_CAPTURETRACKING_H
 
+#include "llvm/IR/PassManager.h"
+#include "llvm/Pass.h"
+
 namespace llvm {
 
-  class Value;
-  class Use;
-  class Instruction;
+  class AAResults;
   class DominatorTree;
+  class Function;
+  class Instruction;
   class OrderedBasicBlock;
+  class Use;
+  class Value;
+  class raw_ostream;
 
   /// PointerMayBeCaptured - Return true if this pointer value may be captured
   /// by the enclosing function (which is required to exist).  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 PointerMayBeCaptured(const Value *V,
                             bool ReturnCaptures,
                             bool StoreCaptures);
 
+  /// PointerMayBeCaptured - Return true if this pointer value may be captured
+  /// by the enclosing function (which is required to exist).  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. For the latter to have
+  /// effect, Alias Analysis results are required.
+  bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures,
+                            bool StoreCaptures, AAResults *AA);
+
   /// 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
struct CaptureTracker {
     virtual bool 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
     /// for more capturing instructions.
     virtual bool captured(const Use *U) = 0;
   };
 
+  /// Printer pass for the EscapeInfo results.
+  class CaptureTrackingPrinterPass
+      : public PassInfoMixin<CaptureTrackingPrinterPass> {
+
+  public:
+    explicit CaptureTrackingPrinterPass(raw_ostream &OS);
+    PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
+
+  private:
+    raw_ostream &OS;
+  };
+
   /// PointerMayBeCaptured - Visit the value and the values derived from it and
   /// find values which appear to be capturing the pointer value. This feeds
   /// results into and is controlled by the CaptureTracker object.
   void PointerMayBeCaptured(const Value *V, CaptureTracker *Tracker);
 } // end namespace llvm
 
 #endif

include/llvm/Transforms/Utils/LoopUtils.h

public:
   /// this induction. If by some other means the caller has a better SCEV
   /// expression for \p Phi than the one returned by the ScalarEvolution
   /// analysis, it can be passed through \p Expr.
   static bool isInductionPHI(PHINode *Phi, const Loop* L, ScalarEvolution *SE,
                              InductionDescriptor &D,
                              const SCEV *Expr = nullptr);
 
   /// Returns true if \p Phi is a floating point induction in the loop \p L.
-  /// If \p Phi is an induction, the induction descriptor \p D will contain 
+  /// If \p Phi is an induction, the induction descriptor \p D will contain
   /// the data describing this induction.
   static bool isFPInductionPHI(PHINode *Phi, const Loop* L,
                                ScalarEvolution *SE, InductionDescriptor &D);
 
   /// Returns true if \p Phi is a loop \p L induction, in the context associated
   /// with the run-time predicate of PSE. If \p Assume is true, this can add
   /// further SCEV predicates to \p PSE in order to prove that \p Phi is an
   /// induction.

 /// loop invariant. It takes AliasSet, Loop exit blocks vector, loop exit blocks
 /// insertion point vector, PredIteratorCache, LoopInfo, DominatorTree, Loop,
 /// AliasSet information for all instructions of the loop and loop safety
 /// information as arguments. It returns changed status.
 bool promoteLoopAccessesToScalars(AliasSet &, SmallVectorImpl<BasicBlock *> &,
                                   SmallVectorImpl<Instruction *> &,
                                   PredIteratorCache &, LoopInfo *,
                                   DominatorTree *, const TargetLibraryInfo *,
-                                  Loop *, AliasSetTracker *, LoopSafetyInfo *);
+                                  AliasAnalysis *AA, Loop *, AliasSetTracker *,
+                                  LoopSafetyInfo *);
 
 /// \brief Computes safety information for a loop
 /// checks loop body & header for the possibility of may throw
 /// exception, it takes LoopSafetyInfo and loop as argument.
 /// Updates safety information in LoopSafetyInfo argument.
 void computeLoopSafetyInfo(LoopSafetyInfo *, Loop *);
 
 /// Returns true if the instruction in a loop is guaranteed to execute at least

lib/Analysis/CaptureTracking.cpp

bool captured(const Use *U) override {
       return true;
     }
 
     bool ReturnCaptures;
 
     bool Captured;
   };
 
+  struct OptimisticCaptureTracker : public CaptureTracker {
+
+    OptimisticCaptureTracker(bool ReturnCaptures, bool StoreCaptures,
+                             AliasAnalysis *AA)
+        : ReturnCaptures(ReturnCaptures), StoreCaptures(StoreCaptures), AA(AA),
+          Captured(false) {}
+
+    void tooManyUses() override { Captured = true; }
+
+    bool storeCaptures(const StoreInst *S) {
+      if (StoreCaptures)
+        return true;
+
+      if (!AA)
+        return true;
+
+      const Function *F = S->getFunction();
+      const Value *Ptr = S->getPointerOperand();
+
+      // Check if the pointer is stored to a function argument.
+      for (auto &Arg : F->getArgumentList()) {
+        if (!isa<PointerType>(Arg.getType()))
+          continue;
+
+        if (!AA->isNoAlias(Ptr, MemoryLocation::UnknownSize, &Arg,
+                           MemoryLocation::UnknownSize))
+          return true;
+      }
+
+      // Check if the pointer is stored to a global.
+      for (auto &Global : F->getParent()->globals()) {
+        if (!AA->isNoAlias(Ptr, MemoryLocation::UnknownSize, &Global,
+                           MemoryLocation::UnknownSize))
+          return true;
+      }
+
+      return false;
+    }
+
+    bool captured(const Use *U) override {
+      if (isa<ReturnInst>(U->getUser()) && !ReturnCaptures)
+        return false;
+
+      if (auto *S = dyn_cast<StoreInst>(U->getUser()))
+        if (!storeCaptures(S))
+          return false;
+
+      Captured = true;
+      return true;
+    }
+
+    bool ReturnCaptures;
+    bool StoreCaptures;
+
+    AliasAnalysis *AA;
+
+    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, OrderedBasicBlock *IC)
struct CapturesBefore : public CaptureTracker {
 
     bool ReturnCaptures;
     bool IncludeI;
 
     bool Captured;
   };
 }
 
+CaptureTrackingPrinterPass::CaptureTrackingPrinterPass(raw_ostream &OS)
+    : OS(OS) {}
+
+PreservedAnalyses CaptureTrackingPrinterPass::run(Function &F,
+                                                 FunctionAnalysisManager &AM) {
+  OS << "Capture tracking results for function: " << F.getName() << "\n";
+  auto& AA = AM.getResult<AAManager>(F);
+  for (auto &BB : F) {
+    for (auto &I : BB) {
+      if (auto *V = dyn_cast<Value>(&I)) {
+        // Only print values with a name.
+        if (V->hasName() && V->getType()->isPointerTy() &&
+            PointerMayBeCaptured(V, true, false, &AA)) {
+          OS << V->getName() << " may be captured\n";
+        }
+      }
+    }
+  }
+
+  return PreservedAnalyses::all();
+}
+
 /// PointerMayBeCaptured - Return true if this pointer value may be captured
 /// by the enclosing function (which is required to exist).  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::PointerMayBeCaptured(const Value *V,
                                 bool ReturnCaptures, bool StoreCaptures) {
   assert(!isa<GlobalValue>(V) &&
          "It doesn't make sense to ask whether a global is captured.");
 
   // TODO: If StoreCaptures is not true, we could do Fancy analysis
   // to determine whether this store is not actually an escape point.
   // In that case, BasicAliasAnalysis should be updated as well to
   // take advantage of this.
-  (void)StoreCaptures;
+  //(void)StoreCaptures;
+
+  // TODO: We can essentially the SimpleCaptureTracker completely with the
+  // Optimistic one and possibly reuse the name?
 
-  SimpleCaptureTracker SCT(ReturnCaptures);
-  PointerMayBeCaptured(V, &SCT);
-  return SCT.Captured;
+  // SimpleCaptureTracker SCT(ReturnCaptures);
+  // PointerMayBeCaptured(V, &SCT);
+  // return SCT.Captured;
+
+  OptimisticCaptureTracker OCT(ReturnCaptures, StoreCaptures, nullptr);
+  PointerMayBeCaptured(V, &OCT);
+  return OCT.Captured;
+}
+
+/// PointerMayBeCaptured - Return true if this pointer value may be captured by
+/// the enclosing function (which is required to exist).  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. For the latter to have effect, Alias Analysis
+/// results are required.
+bool llvm::PointerMayBeCaptured(const Value *V, bool ReturnCaptures,
+                                bool StoreCaptures, AliasAnalysis *AA) {
+  assert(!isa<GlobalValue>(V) &&
+         "It doesn't make sense to ask whether a global is captured.");
+
+  OptimisticCaptureTracker OCT(ReturnCaptures, StoreCaptures, AA);
+  PointerMayBeCaptured(V, &OCT);
+  return OCT.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
case Instruction::Load:
       if (cast<LoadInst>(I)->isVolatile())
         if (Tracker->captured(U))
           return;
       break;
     case Instruction::VAArg:
       // "va-arg" from a pointer does not cause it to be captured.
       break;
     case Instruction::Store:
-        // Stored the pointer - conservatively assume it may be captured.
-        // Volatile stores make the address observable.
-      if (V == I->getOperand(0) || cast<StoreInst>(I)->isVolatile())
+      if (V == I->getOperand(0) || cast<StoreInst>(I)->isVolatile()) {
         if (Tracker->captured(U))
           return;
+      }
       break;
     case Instruction::AtomicRMW: {
       // atomicrmw conceptually includes both a load and store from
       // the same location.
       // As with a store, the location being accessed is not captured,
       // but the value being stored is.
       // Volatile stores make the address observable.
       auto *ARMWI = cast<AtomicRMWInst>(I);

lib/Passes/PassBuilder.cpp

 #include "llvm/ADT/StringSwitch.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AliasAnalysisEvaluator.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/BlockFrequencyInfoImpl.h"
 #include "llvm/Analysis/BranchProbabilityInfo.h"
+#include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/CFGPrinter.h"
 #include "llvm/Analysis/CFLAndersAliasAnalysis.h"
 #include "llvm/Analysis/CFLSteensAliasAnalysis.h"
 #include "llvm/Analysis/CGSCCPassManager.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/DemandedBits.h"
 #include "llvm/Analysis/DependenceAnalysis.h"
 #include "llvm/Analysis/DominanceFrontier.h"

lib/Passes/PassRegistry.def

 FUNCTION_PASS("lcssa", LCSSAPass())
 FUNCTION_PASS("loop-data-prefetch", LoopDataPrefetchPass())
 FUNCTION_PASS("loop-distribute", LoopDistributePass())
 FUNCTION_PASS("loop-vectorize", LoopVectorizePass())
 FUNCTION_PASS("print", PrintFunctionPass(dbgs()))
 FUNCTION_PASS("print<assumptions>", AssumptionPrinterPass(dbgs()))
 FUNCTION_PASS("print<block-freq>", BlockFrequencyPrinterPass(dbgs()))
 FUNCTION_PASS("print<branch-prob>", BranchProbabilityPrinterPass(dbgs()))
+FUNCTION_PASS("print<captures>", CaptureTrackingPrinterPass(dbgs()))
 FUNCTION_PASS("print<domtree>", DominatorTreePrinterPass(dbgs()))
 FUNCTION_PASS("print<postdomtree>", PostDominatorTreePrinterPass(dbgs()))
 FUNCTION_PASS("print<demanded-bits>", DemandedBitsPrinterPass(dbgs()))
 FUNCTION_PASS("print<domfrontier>", DominanceFrontierPrinterPass(dbgs()))
 FUNCTION_PASS("print<loops>", LoopPrinterPass(dbgs()))
 FUNCTION_PASS("print<memoryssa>", MemorySSAPrinterPass(dbgs()))
 FUNCTION_PASS("print<regions>", RegionInfoPrinterPass(dbgs()))
 FUNCTION_PASS("print<scalar-evolution>", ScalarEvolutionPrinterPass(dbgs()))

lib/Transforms/Scalar/DeadStoreElimination.cpp

while (InstDep.isDef() || InstDep.isClobber()) {
       if (DepIndex <= LastThrowingInstIndex) {
         const Value* Underlying = GetUnderlyingObject(DepLoc.Ptr, DL);
         bool IsStoreDeadOnUnwind = isa<AllocaInst>(Underlying);
         if (!IsStoreDeadOnUnwind) {
             // We're looking for a call to an allocation function
             // where the allocation doesn't escape before the last
             // throwing instruction; PointerMayBeCaptured
             // reasonably fast approximation.
-            IsStoreDeadOnUnwind = isAllocLikeFn(Underlying, TLI) &&
-                !PointerMayBeCaptured(Underlying, false, true);
+            IsStoreDeadOnUnwind =
+                isAllocLikeFn(Underlying, TLI) &&
+                !PointerMayBeCaptured(Underlying, false, false, AA);
         }
         if (!IsStoreDeadOnUnwind)
           break;
       }
 
       // If we find a write that is a) removable (i.e., non-volatile), b) is
       // completely obliterated by the store to 'Loc', and c) which we know that
       // 'Inst' doesn't load from, then we can remove it.

lib/Transforms/Scalar/LICM.cpp

bool LoopInvariantCodeMotion::runOnLoop(Loop *L, AliasAnalysis *AA,
   // memory references to scalars that we can.
   if (!DisablePromotion && (Preheader || L->hasDedicatedExits())) {
     SmallVector<BasicBlock *, 8> ExitBlocks;
     SmallVector<Instruction *, 8> InsertPts;
     PredIteratorCache PIC;
 
     // Loop over all of the alias sets in the tracker object.
     for (AliasSet &AS : *CurAST)
-      Changed |= promoteLoopAccessesToScalars(
-          AS, ExitBlocks, InsertPts, PIC, LI, DT, TLI, L, CurAST, &SafetyInfo);
+      Changed |=
+          promoteLoopAccessesToScalars(AS, ExitBlocks, InsertPts, PIC, LI, DT,
+                                       TLI, AA, L, CurAST, &SafetyInfo);
 
     // Once we have promoted values across the loop body we have to recursively
     // reform LCSSA as any nested loop may now have values defined within the
     // loop used in the outer loop.
     // FIXME: This is really heavy handed. It would be a bit better to use an
     // SSAUpdater strategy during promotion that was LCSSA aware and reformed
     // it as it went.
     if (Changed) {

 /// loop and moving loads to before the loop.  We do this by looping over
 /// the stores in the loop, looking for stores to Must pointers which are
 /// loop invariant.
 ///
 bool llvm::promoteLoopAccessesToScalars(
     AliasSet &AS, SmallVectorImpl<BasicBlock *> &ExitBlocks,
     SmallVectorImpl<Instruction *> &InsertPts, PredIteratorCache &PIC,
     LoopInfo *LI, DominatorTree *DT, const TargetLibraryInfo *TLI,
-    Loop *CurLoop, AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo) {
+    AliasAnalysis *AA, Loop *CurLoop, AliasSetTracker *CurAST,
+    LoopSafetyInfo *SafetyInfo) {
   // Verify inputs.
   assert(LI != nullptr && DT != nullptr && CurLoop != nullptr &&
          CurAST != nullptr && SafetyInfo != nullptr &&
          "Unexpected Input to promoteLoopAccessesToScalars");
 
   // We can promote this alias set if it has a store, if it is a "Must" alias
   // set, if the pointer is loop invariant, and if we are not eliminating any
   // volatile loads or stores.
bool llvm::promoteLoopAccessesToScalars(
 
   // Check legality per comment above. Otherwise, we can't promote.
   bool PromotionIsLegal = GuaranteedToExecute;
   if (!PromotionIsLegal && CanSpeculateLoad) {
     // If this is a thread local location, then we can insert stores along
     // paths which originally didn't have them without violating the memory
     // model.
     Value *Object = GetUnderlyingObject(SomePtr, MDL);
-    PromotionIsLegal =
-        isAllocLikeFn(Object, TLI) && !PointerMayBeCaptured(Object, true, true);
+    PromotionIsLegal = isAllocLikeFn(Object, TLI) &&
+                       !PointerMayBeCaptured(Object, true, false, AA);
   }
   if (!PromotionIsLegal)
     return Changed;
 
   // Figure out the loop exits and their insertion points, if this is the
   // first promotion.
   if (ExitBlocks.empty()) {
     CurLoop->getUniqueExitBlocks(ExitBlocks);

test/Analysis/CaptureTracking/captureargstore.ll

+; RUN: opt < %s -passes='print<captures>' -disable-output 2>&1 | FileCheck %s
+
+; CHECK: l may be captured
+; CHECK: n may be captured
+; CHECK: j may be captured
+
+define void @sample(i32* %i) #0 {
+entry:
+  %i.addr = alloca i32*, align 8
+  %k = alloca i32*, align 8
+  store i32* %i, i32** %i.addr, align 8
+  %call = call i8* @malloc(i64 4)
+  %l = bitcast i8* %call to i32*
+  store i32* %l, i32** %k, align 8
+  %m = load i32*, i32** %k, align 8
+  store i32 0, i32* %m, align 4
+  %n = load i32*, i32** %k, align 8
+  store i32* %n, i32** %i.addr, align 8
+  ret void
+}
+
+declare i8* @malloc(i64)
+
+define i32 @main() {
+entry:
+  %retval = alloca i32, align 4
+  %j = alloca i32, align 4
+  store i32 0, i32* %retval, align 4
+  store i32 1, i32* %j, align 4
+  call void @sample(i32* %j)
+  %0 = load i32, i32* %j, align 4
+  ret i32 %0
+}

test/Analysis/CaptureTracking/captureindirectstore.ll

+; RUN: opt < %s -passes='print<captures>' -disable-output 2>&1 | FileCheck %s
+
+; CHECK: ptr may be captured
+; CHECK-NOT: ptrtoptr may be captured
+; CHECK: deref may be captured
+
+@global = external global i32*
+
+define void @sample() {
+entry:
+  %ptr = alloca i32
+  store i32 1, i32* %ptr
+  %ptrtoptr = alloca i32*
+  store i32* %ptr, i32** %ptrtoptr
+  %deref = load i32*, i32** %ptrtoptr
+  store i32* %deref , i32** @global
+  ret void
+}

test/Analysis/CaptureTracking/nocapturestore.ll

+; RUN: opt < %s -passes='print<captures>' -disable-output 2>&1 | FileCheck %s
+
+; CHECK-NOT: ptr may be captured
+; CHECK-NOT: ptrtoptr may be captured
+
+define void @sample() {
+entry:
+  %ptr = alloca i32
+  store i32 1, i32* %ptr
+  %ptrtoptr = alloca i32*
+  store i32* %ptr, i32** %ptrtoptr
+  ret void
+}