[AA] Move earliest escape tracking from DSE to AA

[nikic]

Summary

This is a followup to D109844 (and alternative to D109907), which integrates the new "earliest escape" tracking into AliasAnalysis. This is done by replacing the pre-existing context-free capture cache in AAQueryInfo with a replaceable (virtual) object with two implementations: The SimpleCaptureInfo implements the previous behavior (check whether object is captured at all), while EarliestEscapeInfo implements the new behavior from DSE.

This combines the "earliest escape" analysis with the full power of BasicAA: It subsumes the call handling from D109907, considers a wider range of escape sources, a wider context, and works with AA recursion.

It does come at a slightly higher compile-time cost: http://llvm-compile-time-tracker.com/compare.php?from=1e3c6fc7cb9d2ee6a5328881f95d6643afeadbff&to=23296d5394689e40a0b4376f080cfab18c43442c&stat=instructions (The comparison point would be https://llvm-compile-time-tracker.com/compare.php?from=7faf1285f2c416494aacf7ee13e70e330b2f0540&to=a4964cf36bb0f777d82d6a1025435bbd9f67bc4f&stat=instructions for D109907).

[fhahn]

This combines the "earliest escape" analysis with the full power of BasicAA:

Are there any test cases that show the benefit of that, other than the improvements for the load-load case discussed in D109844 ?

[nikic]

Rebase over additional tests.

[nikic]

Fix unit test build.

[nikic]

In D110368#3020035, @fhahn wrote:

This combines the "earliest escape" analysis with the full power of BasicAA:

Are there any test cases that show the benefit of that, other than the improvements for the load-load case discussed in D109844 ?

See the last three tests in captures-before-load.ll. Only the last one truly requires BasicAA integration though.

Ultimately my main interest here is to integrate this functionality in a way that does not require reimplementing parts of AA in DSE. Better analysis quality is just a nice side effect.

[fhahn]

In D110368#3021556, @nikic wrote:

In D110368#3020035, @fhahn wrote:

This combines the "earliest escape" analysis with the full power of BasicAA:

Are there any test cases that show the benefit of that, other than the improvements for the load-load case discussed in D109844 ?

See the last three tests in captures-before-load.ll. Only the last one truly requires BasicAA integration though.

Great thanks!

Ultimately my main interest here is to integrate this functionality in a way that does not require reimplementing parts of AA in DSE. Better analysis quality is just a nice side effect.

Agreed, just wanted to double check w.r.t. the description.

LGTM, I am just wondering if the change in isEscapeSource is required or can be split off?

llvm/include/llvm/Analysis/AliasAnalysis.h

383

nit: could just be a struct?

407

I should have added doc-comments in the original DSE version but unfortunately did not. Might be good to add some here.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

122–123

this seems unrelated or could at least be split off?

[hans]

A Chromium developer reported compiler non-determinism that we bisected to this change. see https://bugs.chromium.org/p/chromium/issues/detail?id=1268247#c12 for a reproducer with preprocessed source.

[hans]

In D110368#3131219, @hans wrote:

A Chromium developer reported compiler non-determinism that we bisected to this change. see https://bugs.chromium.org/p/chromium/issues/detail?id=1268247#c12 for a reproducer with preprocessed source.

Using that reproducer, it seems the non-deterministic output is coming from DSE: sometimes a store before a call is removed, and sometimes not (see comment at https://bugs.chromium.org/p/chromium/issues/detail?id=1268247#c16)

[nikic]

I believe this is caused by non-determinism in DT child order, which is fixed by D110292.

[nikic]

@hans As the DT patch landed, could you please confirm whether the non-determinism is fixed on your side? I'm no longer able to reproduce it with the test case at least.

[hans]

In D110368#3163552, @nikic wrote:

@hans As the DT patch landed, could you please confirm whether the non-determinism is fixed on your side? I'm no longer able to reproduce it with the test case at least.

Thanks! Confirmed that it looks fixed on our end.

llvm/include/llvm/Analysis/AliasAnalysis.h

 class BasicAAResult;
 class BasicBlock;
 class CatchPadInst;
 class CatchReturnInst;
 class DominatorTree;
 class FenceInst;
 class Function;
 class InvokeInst;
+class LoopInfo;
 class PreservedAnalyses;
 class TargetLibraryInfo;
 class Value;
 
 /// The possible results of an alias query.
 ///
 /// These results are always computed between two MemoryLocation objects as
 /// a query to some alias analysis.

 // to obtain a valid ModRefInfo. The benefit of using the wrapper is that if
 // ModRefInfo enum changes, the wrapper can be updated to & with the new enum
 // entry with all bits set to 1.
 LLVM_NODISCARD inline ModRefInfo
 createModRefInfo(const FunctionModRefBehavior FMRB) {
   return ModRefInfo(FMRB & static_cast<int>(ModRefInfo::ModRef));
 }
 
+/// Virtual base class for providers of capture information.
+struct CaptureInfo {
+  virtual ~CaptureInfo() = 0;
+  virtual bool isNotCapturedBeforeOrAt(const Value *Object,
+                                       const Instruction *I) = 0;
+};
+
+/// Context-free CaptureInfo provider, which computes and caches whether an
+/// object is captured in the function at all, but does not distinguish whether
+/// it was captured before or after the context instruction.
+class SimpleCaptureInfo final : public CaptureInfo {
+  SmallDenseMap<const Value *, bool, 8> IsCapturedCache;
+
+public:
+  bool isNotCapturedBeforeOrAt(const Value *Object,
+                               const Instruction *I) override;
+};
+
+/// Context-sensitive CaptureInfo provider, which computes and caches the
+/// earliest common dominator closure of all captures. It provides a good
+/// approximation to a precise "captures before" analysis.
+class EarliestEscapeInfo final : public CaptureInfo {
+  DominatorTree &DT;
+  const LoopInfo &LI;
+
+  /// Map from identified local object to an instruction before which it does
+  /// not escape, or nullptr if it never escapes. The "earliest" instruction
+  /// may be a conservative approximation, e.g. the first instruction in the
+  /// function is always a legal choice.
+  DenseMap<const Value *, Instruction *> EarliestEscapes;
+
+  /// Reverse map from instruction to the objects it is the earliest escape for.
+  /// This is used for cache invalidation purposes.
+  DenseMap<Instruction *, TinyPtrVector<const Value *>> Inst2Obj;
+
+public:
+  EarliestEscapeInfo(DominatorTree &DT, const LoopInfo &LI) : DT(DT), LI(LI) {}
+
+  bool isNotCapturedBeforeOrAt(const Value *Object,
+                               const Instruction *I) override;
+
+  void removeInstruction(Instruction *I);
+};
+
 /// Reduced version of MemoryLocation that only stores a pointer and size.
 /// Used for caching AATags independent BasicAA results.
 struct AACacheLoc {
   const Value *Ptr;
   LocationSize Size;
 };
 
 template <> struct DenseMapInfo<AACacheLoc> {
struct CacheEntry {
     /// 0 for assumptions that have not been used, -1 for definitive results.
     int NumAssumptionUses;
     /// Whether this is a definitive (non-assumption) result.
     bool isDefinitive() const { return NumAssumptionUses < 0; }
   };
   using AliasCacheT = SmallDenseMap<LocPair, CacheEntry, 8>;
   AliasCacheT AliasCache;
 
-  using IsCapturedCacheT = SmallDenseMap<const Value *, bool, 8>;
-  IsCapturedCacheT IsCapturedCache;
+  CaptureInfo *CI;
 
   /// Query depth used to distinguish recursive queries.
   unsigned Depth = 0;
 
   /// How many active NoAlias assumption uses there are.
   int NumAssumptionUses = 0;
 
   /// Location pairs for which an assumption based result is currently stored.
   /// Used to remove all potentially incorrect results from the cache if an
   /// assumption is disproven.
   SmallVector<AAQueryInfo::LocPair, 4> AssumptionBasedResults;
 
-  AAQueryInfo() : AliasCache(), IsCapturedCache() {}
+  AAQueryInfo(CaptureInfo *CI) : CI(CI) {}
 
   /// Create a new AAQueryInfo based on this one, but with the cache cleared.
   /// This is used for recursive queries across phis, where cache results may
   /// not be valid.
   AAQueryInfo withEmptyCache() {
-    AAQueryInfo NewAAQI;
+    AAQueryInfo NewAAQI(CI);
     NewAAQI.Depth = Depth;
     return NewAAQI;
   }
 };
 
+/// AAQueryInfo that uses SimpleCaptureInfo.
+class SimpleAAQueryInfo : public AAQueryInfo {
+  SimpleCaptureInfo CI;
+
+public:
+  SimpleAAQueryInfo() : AAQueryInfo(&CI) {}
+};
+
 class BatchAAResults;
 
 class AAResults {
 public:
   // Make these results default constructable and movable. We have to spell
   // these out because MSVC won't synthesize them.
   AAResults(const TargetLibraryInfo &TLI) : TLI(TLI) {}
   AAResults(AAResults &&Arg);
public:
   /// An instruction that doesn't read or write memory may be trivially LICM'd
   /// for example.
   ///
   /// For function calls, this delegates to the alias-analysis specific
   /// call-site mod-ref behavior queries. Otherwise it delegates to the specific
   /// helpers above.
   ModRefInfo getModRefInfo(const Instruction *I,
                            const Optional<MemoryLocation> &OptLoc) {
-    AAQueryInfo AAQIP;
+    SimpleAAQueryInfo AAQIP;
     return getModRefInfo(I, OptLoc, AAQIP);
   }
 
   /// A convenience wrapper for constructing the memory location.
   ModRefInfo getModRefInfo(const Instruction *I, const Value *P,
                            LocationSize Size) {
     return getModRefInfo(I, MemoryLocation(P, Size));
   }
public:
   /// Return information about whether a particular call site modifies
   /// or reads the specified memory location \p MemLoc before instruction \p I
   /// in a BasicBlock.
   /// Early exits in callCapturesBefore may lead to ModRefInfo::Must not being
   /// set.
   ModRefInfo callCapturesBefore(const Instruction *I,
                                 const MemoryLocation &MemLoc,
                                 DominatorTree *DT) {
-    AAQueryInfo AAQIP;
+    SimpleAAQueryInfo AAQIP;
     return callCapturesBefore(I, MemLoc, DT, AAQIP);
   }
 
   /// A convenience wrapper to synthesize a memory location.
   ModRefInfo callCapturesBefore(const Instruction *I, const Value *P,
                                 LocationSize Size, DominatorTree *DT) {
     return callCapturesBefore(I, MemoryLocation(P, Size), DT);
   }

 /// only when there are no IR changes inbetween queries. BatchAAResults is
 /// reusing the same `AAQueryInfo` to preserve the state across queries,
 /// esentially making AA work in "batch mode". The internal state cannot be
 /// cleared, so to go "out-of-batch-mode", the user must either use AAResults,
 /// or create a new BatchAAResults.
 class BatchAAResults {
   AAResults &AA;
   AAQueryInfo AAQI;
+  SimpleCaptureInfo SimpleCI;
 
 public:
-  BatchAAResults(AAResults &AAR) : AA(AAR), AAQI() {}
+  BatchAAResults(AAResults &AAR) : AA(AAR), AAQI(&SimpleCI) {}
+  BatchAAResults(AAResults &AAR, CaptureInfo *CI) : AA(AAR), AAQI(CI) {}
+
   AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
     return AA.alias(LocA, LocB, AAQI);
   }
   bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal = false) {
     return AA.pointsToConstantMemory(Loc, AAQI, OrLocal);
   }
   ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc) {
     return AA.getModRefInfo(Call, Loc, AAQI);

llvm/lib/Analysis/AliasAnalysis.cpp

 }
 
 //===----------------------------------------------------------------------===//
 // Default chaining methods
 //===----------------------------------------------------------------------===//
 
 AliasResult AAResults::alias(const MemoryLocation &LocA,
                              const MemoryLocation &LocB) {
-  AAQueryInfo AAQIP;
+  SimpleAAQueryInfo AAQIP;
   return alias(LocA, LocB, AAQIP);
 }
 
 AliasResult AAResults::alias(const MemoryLocation &LocA,
                              const MemoryLocation &LocB, AAQueryInfo &AAQI) {
   AliasResult Result = AliasResult::MayAlias;
 
   if (EnableAATrace) {
if (AAQI.Depth == 0) {
     else
       ++NumMayAlias;
   }
   return Result;
 }
 
 bool AAResults::pointsToConstantMemory(const MemoryLocation &Loc,
                                        bool OrLocal) {
-  AAQueryInfo AAQIP;
+  SimpleAAQueryInfo AAQIP;
   return pointsToConstantMemory(Loc, AAQIP, OrLocal);
 }
 
 bool AAResults::pointsToConstantMemory(const MemoryLocation &Loc,
                                        AAQueryInfo &AAQI, bool OrLocal) {
   for (const auto &AA : AAs)
     if (AA->pointsToConstantMemory(Loc, AAQI, OrLocal))
       return true;
for (const auto &AA : AAs) {
     if (isNoModRef(Result))
       return ModRefInfo::NoModRef;
   }
 
   return Result;
 }
 
 ModRefInfo AAResults::getModRefInfo(Instruction *I, const CallBase *Call2) {
-  AAQueryInfo AAQIP;
+  SimpleAAQueryInfo AAQIP;
   return getModRefInfo(I, Call2, AAQIP);
 }
 
 ModRefInfo AAResults::getModRefInfo(Instruction *I, const CallBase *Call2,
                                     AAQueryInfo &AAQI) {
   // We may have two calls.
   if (const auto *Call1 = dyn_cast<CallBase>(I)) {
     // Check if the two calls modify the same memory.
ModRefInfo AAResults::getModRefInfo(Instruction *I, const CallBase *Call2,
   ModRefInfo MR = getModRefInfo(Call2, DefLoc, AAQI);
   if (isModOrRefSet(MR))
     return setModAndRef(MR);
   return ModRefInfo::NoModRef;
 }
 
 ModRefInfo AAResults::getModRefInfo(const CallBase *Call,
                                     const MemoryLocation &Loc) {
-  AAQueryInfo AAQIP;
+  SimpleAAQueryInfo AAQIP;
   return getModRefInfo(Call, Loc, AAQIP);
 }
 
 ModRefInfo AAResults::getModRefInfo(const CallBase *Call,
                                     const MemoryLocation &Loc,
                                     AAQueryInfo &AAQI) {
   ModRefInfo Result = ModRefInfo::ModRef;
 
ModRefInfo AAResults::getModRefInfo(const CallBase *Call,
   if (isModSet(Result) && pointsToConstantMemory(Loc, AAQI, /*OrLocal*/ false))
     Result = clearMod(Result);
 
   return Result;
 }
 
 ModRefInfo AAResults::getModRefInfo(const CallBase *Call1,
                                     const CallBase *Call2) {
-  AAQueryInfo AAQIP;
+  SimpleAAQueryInfo AAQIP;
   return getModRefInfo(Call1, Call2, AAQIP);
 }
 
 ModRefInfo AAResults::getModRefInfo(const CallBase *Call1,
                                     const CallBase *Call2, AAQueryInfo &AAQI) {
   ModRefInfo Result = ModRefInfo::ModRef;
 
   for (const auto &AA : AAs) {

 }
 
 //===----------------------------------------------------------------------===//
 // Helper method implementation
 //===----------------------------------------------------------------------===//
 
 ModRefInfo AAResults::getModRefInfo(const LoadInst *L,
                                     const MemoryLocation &Loc) {
-  AAQueryInfo AAQIP;
+  SimpleAAQueryInfo AAQIP;
   return getModRefInfo(L, Loc, AAQIP);
 }
 ModRefInfo AAResults::getModRefInfo(const LoadInst *L,
                                     const MemoryLocation &Loc,
                                     AAQueryInfo &AAQI) {
   // Be conservative in the face of atomic.
   if (isStrongerThan(L->getOrdering(), AtomicOrdering::Unordered))
     return ModRefInfo::ModRef;
 
   // If the load address doesn't alias the given address, it doesn't read
   // or write the specified memory.
   if (Loc.Ptr) {
     AliasResult AR = alias(MemoryLocation::get(L), Loc, AAQI);
     if (AR == AliasResult::NoAlias)
       return ModRefInfo::NoModRef;
     if (AR == AliasResult::MustAlias)
       return ModRefInfo::MustRef;
   }
   // Otherwise, a load just reads.
   return ModRefInfo::Ref;
 }
 
 ModRefInfo AAResults::getModRefInfo(const StoreInst *S,
                                     const MemoryLocation &Loc) {
-  AAQueryInfo AAQIP;
+  SimpleAAQueryInfo AAQIP;
   return getModRefInfo(S, Loc, AAQIP);
 }
 ModRefInfo AAResults::getModRefInfo(const StoreInst *S,
                                     const MemoryLocation &Loc,
                                     AAQueryInfo &AAQI) {
   // Be conservative in the face of atomic.
   if (isStrongerThan(S->getOrdering(), AtomicOrdering::Unordered))
     return ModRefInfo::ModRef;
if (AR == AliasResult::MustAlias)
       return ModRefInfo::MustMod;
   }
 
   // Otherwise, a store just writes.
   return ModRefInfo::Mod;
 }
 
 ModRefInfo AAResults::getModRefInfo(const FenceInst *S, const MemoryLocation &Loc) {
-  AAQueryInfo AAQIP;
+  SimpleAAQueryInfo AAQIP;
   return getModRefInfo(S, Loc, AAQIP);
 }
 
 ModRefInfo AAResults::getModRefInfo(const FenceInst *S,
                                     const MemoryLocation &Loc,
                                     AAQueryInfo &AAQI) {
   // If we know that the location is a constant memory location, the fence
   // cannot modify this location.
   if (Loc.Ptr && pointsToConstantMemory(Loc, AAQI))
     return ModRefInfo::Ref;
   return ModRefInfo::ModRef;
 }
 
 ModRefInfo AAResults::getModRefInfo(const VAArgInst *V,
                                     const MemoryLocation &Loc) {
-  AAQueryInfo AAQIP;
+  SimpleAAQueryInfo AAQIP;
   return getModRefInfo(V, Loc, AAQIP);
 }
 
 ModRefInfo AAResults::getModRefInfo(const VAArgInst *V,
                                     const MemoryLocation &Loc,
                                     AAQueryInfo &AAQI) {
   if (Loc.Ptr) {
     AliasResult AR = alias(MemoryLocation::get(V), Loc, AAQI);
ModRefInfo AAResults::getModRefInfo(const VAArgInst *V,
   }
 
   // Otherwise, a va_arg reads and writes.
   return ModRefInfo::ModRef;
 }
 
 ModRefInfo AAResults::getModRefInfo(const CatchPadInst *CatchPad,
                                     const MemoryLocation &Loc) {
-  AAQueryInfo AAQIP;
+  SimpleAAQueryInfo AAQIP;
   return getModRefInfo(CatchPad, Loc, AAQIP);
 }
 
 ModRefInfo AAResults::getModRefInfo(const CatchPadInst *CatchPad,
                                     const MemoryLocation &Loc,
                                     AAQueryInfo &AAQI) {
   if (Loc.Ptr) {
     // If the pointer is a pointer to constant memory,
     // then it could not have been modified by this catchpad.
     if (pointsToConstantMemory(Loc, AAQI))
       return ModRefInfo::NoModRef;
   }
 
   // Otherwise, a catchpad reads and writes.
   return ModRefInfo::ModRef;
 }
 
 ModRefInfo AAResults::getModRefInfo(const CatchReturnInst *CatchRet,
                                     const MemoryLocation &Loc) {
-  AAQueryInfo AAQIP;
+  SimpleAAQueryInfo AAQIP;
   return getModRefInfo(CatchRet, Loc, AAQIP);
 }
 
 ModRefInfo AAResults::getModRefInfo(const CatchReturnInst *CatchRet,
                                     const MemoryLocation &Loc,
                                     AAQueryInfo &AAQI) {
   if (Loc.Ptr) {
     // If the pointer is a pointer to constant memory,
     // then it could not have been modified by this catchpad.
     if (pointsToConstantMemory(Loc, AAQI))
       return ModRefInfo::NoModRef;
   }
 
   // Otherwise, a catchret reads and writes.
   return ModRefInfo::ModRef;
 }
 
 ModRefInfo AAResults::getModRefInfo(const AtomicCmpXchgInst *CX,
                                     const MemoryLocation &Loc) {
-  AAQueryInfo AAQIP;
+  SimpleAAQueryInfo AAQIP;
   return getModRefInfo(CX, Loc, AAQIP);
 }
 
 ModRefInfo AAResults::getModRefInfo(const AtomicCmpXchgInst *CX,
                                     const MemoryLocation &Loc,
                                     AAQueryInfo &AAQI) {
   // Acquire/Release cmpxchg has properties that matter for arbitrary addresses.
   if (isStrongerThanMonotonic(CX->getSuccessOrdering()))
if (AR == AliasResult::MustAlias)
       return ModRefInfo::MustModRef;
   }
 
   return ModRefInfo::ModRef;
 }
 
 ModRefInfo AAResults::getModRefInfo(const AtomicRMWInst *RMW,
                                     const MemoryLocation &Loc) {
-  AAQueryInfo AAQIP;
+  SimpleAAQueryInfo AAQIP;
   return getModRefInfo(RMW, Loc, AAQIP);
 }
 
 ModRefInfo AAResults::getModRefInfo(const AtomicRMWInst *RMW,
                                     const MemoryLocation &Loc,
                                     AAQueryInfo &AAQI) {
   // Acquire/Release atomicrmw has properties that matter for arbitrary addresses.
   if (isStrongerThanMonotonic(RMW->getOrdering()))

llvm/lib/Analysis/BasicAliasAnalysis.cpp

 // Useful predicates
 //===----------------------------------------------------------------------===//
 
 /// Returns true if the pointer is one which would have been considered an
 /// escape by isNonEscapingLocalObject.
 static bool isEscapeSource(const Value *V) {
   if (isa<CallBase>(V))
     return true;
 
   // The load case works because isNonEscapingLocalObject considers all
   // stores to be escapes (it passes true for the StoreCaptures argument
   // to PointerMayBeCaptured).
   if (isa<LoadInst>(V))
     return true;
 
   // The inttoptr case works because isNonEscapingLocalObject considers all
   // means of converting or equating a pointer to an int (ptrtoint, ptr store
   // which could be followed by an integer load, ptr<->int compare) as

 /// Returns true if we can prove that the object specified by V has size Size.
 static bool isObjectSize(const Value *V, uint64_t Size, const DataLayout &DL,
                          const TargetLibraryInfo &TLI, bool NullIsValidLoc) {
   uint64_t ObjectSize = getObjectSize(V, DL, TLI, NullIsValidLoc);
   return ObjectSize != MemoryLocation::UnknownSize && ObjectSize == Size;
 }
 
 //===----------------------------------------------------------------------===//
+// CaptureInfo implementations
+//===----------------------------------------------------------------------===//
+
+CaptureInfo::~CaptureInfo() = default;
+
+bool SimpleCaptureInfo::isNotCapturedBeforeOrAt(const Value *Object,
+                                                const Instruction *I) {
+  return isNonEscapingLocalObject(Object, &IsCapturedCache);
+}
+
+bool EarliestEscapeInfo::isNotCapturedBeforeOrAt(const Value *Object,
+                                                 const Instruction *I) {
+  if (!isIdentifiedFunctionLocal(Object))
+    return false;
+
+  auto Iter = EarliestEscapes.insert({Object, nullptr});
+  if (Iter.second) {
+    Instruction *EarliestCapture = FindEarliestCapture(
+        Object, *const_cast<Function *>(I->getFunction()),
+        /*ReturnCaptures=*/false, /*StoreCaptures=*/true, DT);
+    if (EarliestCapture) {
+      auto Ins = Inst2Obj.insert({EarliestCapture, {}});
+      Ins.first->second.push_back(Object);
+    }
+    Iter.first->second = EarliestCapture;
+  }
+
+  // No capturing instruction.
+  if (!Iter.first->second)
+    return true;
+
+  return I != Iter.first->second &&
+         !isPotentiallyReachable(Iter.first->second, I, nullptr, &DT, &LI);
+}
+
+void EarliestEscapeInfo::removeInstruction(Instruction *I) {
+  auto Iter = Inst2Obj.find(I);
+  if (Iter != Inst2Obj.end()) {
+    for (const Value *Obj : Iter->second)
+      EarliestEscapes.erase(Obj);
+    Inst2Obj.erase(I);
+  }
+}
+
+//===----------------------------------------------------------------------===//
 // GetElementPtr Instruction Decomposition and Analysis
 //===----------------------------------------------------------------------===//
 
 namespace {
 /// Represents zext(sext(V)).
 struct ExtendedValue {
   const Value *V;
   unsigned ZExtBits;
ModRefInfo BasicAAResult::getModRefInfo(const CallBase *Call,
   if (auto *AI = dyn_cast<AllocaInst>(Object))
     if (!AI->isStaticAlloca() && isIntrinsicCall(Call, Intrinsic::stackrestore))
       return ModRefInfo::Mod;
 
   // If the pointer is to a locally allocated object that does not escape,
   // then the call can not mod/ref the pointer unless the call takes the pointer
   // as an argument, and itself doesn't capture it.
   if (!isa<Constant>(Object) && Call != Object &&
-      isNonEscapingLocalObject(Object, &AAQI.IsCapturedCache)) {
+      AAQI.CI->isNotCapturedBeforeOrAt(Object, Call)) {
 
     // Optimistically assume that call doesn't touch Object and check this
     // assumption in the following loop.
     ModRefInfo Result = ModRefInfo::NoModRef;
     bool IsMustAlias = true;
 
     unsigned OperandNo = 0;
     for (auto CI = Call->data_operands_begin(), CE = Call->data_operands_end();
if (O1 != O2) {
     // object couldn't escape to a point where the call could return it.
     //
     // Note that if the pointers are in different functions, there are a
     // variety of complications. A call with a nocapture argument may still
     // temporary store the nocapture argument's value in a temporary memory
     // location if that memory location doesn't escape. Or it may pass a
     // nocapture value to other functions as long as they don't capture it.
     if (isEscapeSource(O1) &&
-        isNonEscapingLocalObject(O2, &AAQI.IsCapturedCache))
+        AAQI.CI->isNotCapturedBeforeOrAt(O2, cast<Instruction>(O1)))
       return AliasResult::NoAlias;
     if (isEscapeSource(O2) &&
-        isNonEscapingLocalObject(O1, &AAQI.IsCapturedCache))
+        AAQI.CI->isNotCapturedBeforeOrAt(O1, cast<Instruction>(O2)))
       return AliasResult::NoAlias;
   }
 
   // If the size of one access is larger than the entire object on the other
   // side, then we know such behavior is undefined and can assume no alias.
   bool NullIsValidLocation = NullPointerIsDefined(&F);
   if ((isObjectSmallerThan(
           O2, getMinimalExtentFrom(*V1, V1Size, DL, NullIsValidLocation), DL,

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Analysis/AliasAnalysis.h"
-#include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/MemoryLocation.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/MustExecute.h"
if (isNoopIntrinsic(DI))
     return true;
 
   return false;
 }
 
 struct DSEState {
   Function &F;
   AliasAnalysis &AA;
+  EarliestEscapeInfo EI;
 
   /// The single BatchAA instance that is used to cache AA queries. It will
   /// not be invalidated over the whole run. This is safe, because:
   /// 1. Only memory writes are removed, so the alias cache for memory
   ///    locations remains valid.
   /// 2. No new instructions are added (only instructions removed), so cached
   ///    information for a deleted value cannot be accessed by a re-used new
   ///    value pointer.
struct DSEState {
   // Post-order numbers for each basic block. Used to figure out if memory
   // accesses are executed before another access.
   DenseMap<BasicBlock *, unsigned> PostOrderNumbers;
 
   /// Keep track of instructions (partly) overlapping with killing MemoryDefs per
   /// basic block.
   DenseMap<BasicBlock *, InstOverlapIntervalsTy> IOLs;
 
-  DenseMap<const Value *, Instruction *> EarliestEscapes;
-  DenseMap<Instruction *, TinyPtrVector<const Value *>> Inst2Obj;
-
   DSEState(Function &F, AliasAnalysis &AA, MemorySSA &MSSA, DominatorTree &DT,
            PostDominatorTree &PDT, const TargetLibraryInfo &TLI,
            const LoopInfo &LI)
-      : F(F), AA(AA), BatchAA(AA), MSSA(MSSA), DT(DT), PDT(PDT), TLI(TLI),
-        DL(F.getParent()->getDataLayout()), LI(LI) {}
+      : F(F), AA(AA), EI(DT, LI), BatchAA(AA, &EI), MSSA(MSSA), DT(DT),
+        PDT(PDT), TLI(TLI), DL(F.getParent()->getDataLayout()), LI(LI) {}
 
   static DSEState get(Function &F, AliasAnalysis &AA, MemorySSA &MSSA,
                       DominatorTree &DT, PostDominatorTree &PDT,
                       const TargetLibraryInfo &TLI, const LoopInfo &LI) {
     DSEState State(F, AA, MSSA, DT, PDT, TLI, LI);
     // Collect blocks with throwing instructions not modeled in MemorySSA and
     // alloc-like objects.
     unsigned PO = 0;
if (MaybeTermLoc->second) {
       return BatchAA.isMustAlias(TermLoc.Ptr, LocUO);
     }
     int64_t InstWriteOffset = 0;
     int64_t DepWriteOffset = 0;
     return isOverwrite(MaybeTerm, AccessI, TermLoc, Loc, InstWriteOffset,
                        DepWriteOffset) == OW_Complete;
   }
 
-  /// Returns true if \p Object is not captured before or by \p I.
-  bool notCapturedBeforeOrAt(const Value *Object, Instruction *I) {
-    if (!isIdentifiedFunctionLocal(Object))
-      return false;
-
-    auto Iter = EarliestEscapes.insert({Object, nullptr});
-    if (Iter.second) {
-      Instruction *EarliestCapture = FindEarliestCapture(
-          Object, F, /*ReturnCaptures=*/false, /*StoreCaptures=*/true, DT);
-      if (EarliestCapture) {
-        auto Ins = Inst2Obj.insert({EarliestCapture, {}});
-        Ins.first->second.push_back(Object);
-      }
-      Iter.first->second = EarliestCapture;
-    }
-
-    // No capturing instruction.
-    if (!Iter.first->second)
-      return true;
-
-    return I != Iter.first->second &&
-           !isPotentiallyReachable(Iter.first->second, I, nullptr, &DT, &LI);
-  }
-
   // Returns true if \p Use may read from \p DefLoc.
   bool isReadClobber(const MemoryLocation &DefLoc, Instruction *UseInst) {
     if (isNoopIntrinsic(UseInst))
       return false;
 
     // Monotonic or weaker atomic stores can be re-ordered and do not need to be
     // treated as read clobber.
     if (auto SI = dyn_cast<StoreInst>(UseInst))
       return isStrongerThan(SI->getOrdering(), AtomicOrdering::Monotonic);
 
     if (!UseInst->mayReadFromMemory())
       return false;
 
     if (auto *CB = dyn_cast<CallBase>(UseInst))
       if (CB->onlyAccessesInaccessibleMemory())
         return false;
 
-    // BasicAA does not spend linear time to check whether local objects escape
-    // before potentially aliasing accesses. To improve DSE results, compute and
-    // cache escape info for local objects in certain circumstances.
-    if (auto *LI = dyn_cast<LoadInst>(UseInst)) {
-      // If the loads reads from a loaded underlying object accesses the load
-      // cannot alias DefLoc, if DefUO is a local object that has not escaped
-      // before the load.
-      auto *ReadUO = getUnderlyingObject(LI->getPointerOperand());
-      auto *DefUO = getUnderlyingObject(DefLoc.Ptr);
-      auto *ReadLI = dyn_cast<LoadInst>(ReadUO);
-      if (ReadLI && notCapturedBeforeOrAt(DefUO, ReadLI)) {
-        assert(
-            !PointerMayBeCapturedBefore(DefLoc.Ptr, false, true, ReadLI, &DT,
-                                        false, 0, &this->LI) &&
-            "cached analysis disagrees with fresh PointerMayBeCapturedBefore");
-        return false;
-      }
-    }
-
     // NOTE: For calls, the number of stores removed could be slightly improved
     // by using AA.callCapturesBefore(UseInst, DefLoc, &DT), but that showed to
     // be expensive compared to the benefits in practice. For now, avoid more
     // expensive analysis to limit compile-time.
     return isRefSet(BatchAA.getModRefInfo(UseInst, DefLoc));
   }
 
   /// Returns true if a dependency between \p Current and \p KillingDef is
while (!NowDeadInsts.empty()) {
       // Remove its operands
       for (Use &O : DeadInst->operands())
         if (Instruction *OpI = dyn_cast<Instruction>(O)) {
           O = nullptr;
           if (isInstructionTriviallyDead(OpI, &TLI))
             NowDeadInsts.push_back(OpI);
         }
 
-      // Clear any cached escape info for objects associated with the
-      // removed instructions.
-      auto Iter = Inst2Obj.find(DeadInst);
-      if (Iter != Inst2Obj.end()) {
-        for (const Value *Obj : Iter->second)
-          EarliestEscapes.erase(Obj);
-        Inst2Obj.erase(DeadInst);
-      }
+      EI.removeInstruction(DeadInst);
       DeadInst->eraseFromParent();
     }
   }
 
   // Check for any extra throws between \p KillingI and \p DeadI that block
   // DSE.  This only checks extra maythrows (those that aren't MemoryDef's).
   // MemoryDef that may throw are handled during the walk from one def to the
   // next.

llvm/test/Transforms/DeadStoreElimination/captures-before-call.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes='dse' -S %s | FileCheck %s
 
 target datalayout = "e-m:o-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 
 ; Test case from PR50220.
 define i32 @other_value_escapes_before_call() {
 ; CHECK-LABEL: @other_value_escapes_before_call(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[V1:%.*]] = alloca i32, align 4
 ; CHECK-NEXT:    [[V2:%.*]] = alloca i32, align 4
 ; CHECK-NEXT:    store i32 0, i32* [[V1]], align 4
 ; CHECK-NEXT:    call void @escape(i32* nonnull [[V1]])
-; CHECK-NEXT:    store i32 55555, i32* [[V2]], align 4
 ; CHECK-NEXT:    [[CALL:%.*]] = call i32 @getval()
 ; CHECK-NEXT:    store i32 [[CALL]], i32* [[V2]], align 4
 ; CHECK-NEXT:    call void @escape(i32* nonnull [[V2]])
 ; CHECK-NEXT:    [[LOAD_V2:%.*]] = load i32, i32* [[V2]], align 4
 ; CHECK-NEXT:    [[LOAD_V1:%.*]] = load i32, i32* [[V1]], align 4
 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[LOAD_V2]], [[LOAD_V1]]
 ; CHECK-NEXT:    ret i32 [[ADD]]
 ;

 
 declare void @escape_and_clobber(i32*)
 declare void @escape_writeonly(i32*) writeonly
 declare void @clobber()
 
 define i32 @test_not_captured_before_call_same_bb() {
 ; CHECK-LABEL: @test_not_captured_before_call_same_bb(
 ; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
-; CHECK-NEXT:    store i32 55, i32* [[A]], align 4
 ; CHECK-NEXT:    [[R:%.*]] = call i32 @getval()
 ; CHECK-NEXT:    store i32 99, i32* [[A]], align 4
 ; CHECK-NEXT:    call void @escape_and_clobber(i32* [[A]])
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %a = alloca i32, align 4
   store i32 55, i32* %a
   %r = call i32 @getval()
   store i32 99, i32* %a, align 4
   call void @escape_and_clobber(i32* %a)
   ret i32 %r
 }
 
 define i32 @test_not_captured_before_call_same_bb_escape_unreachable_block() {
 ; CHECK-LABEL: @test_not_captured_before_call_same_bb_escape_unreachable_block(
 ; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
-; CHECK-NEXT:    store i32 55, i32* [[A]], align 4
 ; CHECK-NEXT:    [[R:%.*]] = call i32 @getval()
 ; CHECK-NEXT:    store i32 99, i32* [[A]], align 4
 ; CHECK-NEXT:    call void @escape_and_clobber(i32* [[A]])
 ; CHECK-NEXT:    ret i32 [[R]]
 ; CHECK:       unreach:
 ; CHECK-NEXT:    call void @escape_and_clobber(i32* [[A]])
 ; CHECK-NEXT:    ret i32 0
 ;
;
   store i32 99, i32* %a, align 4
   call void @clobber()
   ret i32 %r
 }
 
 define i32 @test_captured_after_call_same_bb_2_clobbered_later() {
 ; CHECK-LABEL: @test_captured_after_call_same_bb_2_clobbered_later(
 ; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
-; CHECK-NEXT:    store i32 55, i32* [[A]], align 4
 ; CHECK-NEXT:    [[R:%.*]] = call i32 @getval()
 ; CHECK-NEXT:    call void @escape_writeonly(i32* [[A]])
 ; CHECK-NEXT:    store i32 99, i32* [[A]], align 4
 ; CHECK-NEXT:    call void @clobber()
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %a = alloca i32, align 4
   store i32 55, i32* %a
   %r = call i32 @getval()
   call void @escape_writeonly(i32* %a)
   store i32 99, i32* %a, align 4
   call void @clobber()
   ret i32 %r
 }
 
 define i32 @test_captured_sibling_path_to_call_other_blocks_1(i1 %c.1) {
 ; CHECK-LABEL: @test_captured_sibling_path_to_call_other_blocks_1(
 ; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
-; CHECK-NEXT:    store i32 55, i32* [[A]], align 4
 ; CHECK-NEXT:    br i1 [[C_1:%.*]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    call void @escape_writeonly(i32* [[A]])
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       else:
 ; CHECK-NEXT:    [[R:%.*]] = call i32 @getval()
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
exit:
   call void @escape_writeonly(i32* %a)
   call void @clobber()
   ret i32 %r
 }
 
 define i32 @test_not_captured_before_call_other_blocks_1(i1 %c.1) {
 ; CHECK-LABEL: @test_not_captured_before_call_other_blocks_1(
 ; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
-; CHECK-NEXT:    store i32 55, i32* [[A]], align 4
 ; CHECK-NEXT:    [[R:%.*]] = call i32 @getval()
 ; CHECK-NEXT:    store i32 99, i32* [[A]], align 4
 ; CHECK-NEXT:    br i1 [[C_1:%.*]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       else:
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:

 exit:
   call void @escape_and_clobber(i32* %a)
   ret i32 %r
 }
 
 define i32 @test_not_captured_before_call_other_blocks_2(i1 %c.1) {
 ; CHECK-LABEL: @test_not_captured_before_call_other_blocks_2(
 ; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
-; CHECK-NEXT:    store i32 55, i32* [[A]], align 4
 ; CHECK-NEXT:    [[R:%.*]] = call i32 @getval()
 ; CHECK-NEXT:    store i32 99, i32* [[A]], align 4
 ; CHECK-NEXT:    br i1 [[C_1:%.*]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    call void @escape_and_clobber(i32* [[A]])
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       else:
 ; CHECK-NEXT:    call void @escape_and_clobber(i32* [[A]])

 
 exit:
   ret i32 %r
 }
 
 define i32 @test_not_captured_before_call_other_blocks_3(i1 %c.1) {
 ; CHECK-LABEL: @test_not_captured_before_call_other_blocks_3(
 ; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
-; CHECK-NEXT:    store i32 55, i32* [[A]], align 4
 ; CHECK-NEXT:    [[R:%.*]] = call i32 @getval()
 ; CHECK-NEXT:    store i32 99, i32* [[A]], align 4
 ; CHECK-NEXT:    br i1 [[C_1:%.*]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    call void @escape_and_clobber(i32* [[A]])
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       else:
 ; CHECK-NEXT:    br label [[EXIT]]

 
 exit:
   ret i32 %r
 }
 
 define i32 @test_not_captured_before_call_other_blocks_4(i1 %c.1) {
 ; CHECK-LABEL: @test_not_captured_before_call_other_blocks_4(
 ; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
-; CHECK-NEXT:    store i32 55, i32* [[A]], align 4
 ; CHECK-NEXT:    br i1 [[C_1:%.*]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       else:
 ; CHECK-NEXT:    [[R:%.*]] = call i32 @getval()
 ; CHECK-NEXT:    call void @escape_writeonly(i32* [[A]])
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
exit:
   call void @clobber()
   ret i32 %p
 }
 
 define i32 @test_not_captured_before_call_other_blocks_5(i1 %c.1) {
 ; CHECK-LABEL: @test_not_captured_before_call_other_blocks_5(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
-; CHECK-NEXT:    store i32 55, i32* [[A]], align 4
 ; CHECK-NEXT:    br i1 [[C_1:%.*]], label [[THEN:%.*]], label [[EXIT:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    [[R:%.*]] = call i32 @getval()
 ; CHECK-NEXT:    call void @escape_writeonly(i32* [[A]])
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[P:%.*]] = phi i32 [ [[R]], [[THEN]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    store i32 99, i32* [[A]], align 4
exit:
   call void @clobber()
   ret i32 %p
 }
 
 define i32 @test_not_captured_before_call_other_blocks_7(i1 %c.1) {
 ; CHECK-LABEL: @test_not_captured_before_call_other_blocks_7(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
-; CHECK-NEXT:    store i32 55, i32* [[A]], align 4
 ; CHECK-NEXT:    [[R:%.*]] = call i32 @getval()
 ; CHECK-NEXT:    call void @escape_writeonly(i32* [[A]])
 ; CHECK-NEXT:    br i1 [[C_1:%.*]], label [[THEN:%.*]], label [[EXIT:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    call void @escape_writeonly(i32* [[A]])
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[P:%.*]] = phi i32 [ 0, [[THEN]] ], [ [[R]], [[ENTRY:%.*]] ]
;
   call void @escape_and_clobber(i32* %a)
   %res = add i32 %r, %lv
   ret i32 %res
 }
 
 define i32 @test_captured_after_loop(i1 %c.1) {
 ; CHECK-LABEL: @test_captured_after_loop(
 ; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
-; CHECK-NEXT:    store i32 55, i32* [[A]], align 4
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[R:%.*]] = call i32 @getval()
 ; CHECK-NEXT:    store i32 99, i32* [[A]], align 4
 ; CHECK-NEXT:    br i1 [[C_1:%.*]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    call void @escape_and_clobber(i32* [[A]])
 ; CHECK-NEXT:    ret i32 [[R]]

 }
 
 declare void @llvm.memcpy.p0i8.p0i8.i64(i8*, i8*, i64, i1)
 define void @test_escaping_store_removed(i8* %src, i64** %escape) {
 ; CHECK-LABEL: @test_escaping_store_removed(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    [[A:%.*]] = alloca i64, align 8
 ; CHECK-NEXT:    [[EXT_A:%.*]] = bitcast i64* [[A]] to i8*
-; CHECK-NEXT:    store i64 0, i64* [[A]], align 8
 ; CHECK-NEXT:    call void @clobber()
 ; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* [[EXT_A]], i8* [[SRC:%.*]], i64 8, i1 false)
 ; CHECK-NEXT:    store i64* [[A]], i64** [[ESCAPE:%.*]], align 8
 ; CHECK-NEXT:    call void @clobber()
 ; CHECK-NEXT:    store i64 99, i64* [[A]], align 8
 ; CHECK-NEXT:    call void @clobber()
 ; CHECK-NEXT:    ret void
 ;
bb:
   ret void
 }
 
 
 define void @test_invoke_captures() personality i8* undef {
 ; CHECK-LABEL: @test_invoke_captures(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
-; CHECK-NEXT:    store i32 99, i32* [[A]], align 4
 ; CHECK-NEXT:    invoke void @clobber()
 ; CHECK-NEXT:    to label [[BB2:%.*]] unwind label [[BB5:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    store i32 0, i32* [[A]], align 8
 ; CHECK-NEXT:    invoke void @escape(i32* [[A]])
 ; CHECK-NEXT:    to label [[BB9:%.*]] unwind label [[BB10:%.*]]
 ; CHECK:       bb4:
 ; CHECK-NEXT:    ret void

 }
 
 declare noalias i32* @alloc() nounwind
 declare i32 @getval_nounwind() nounwind
 
 define i32 @test_not_captured_before_load_same_bb_noalias_call() {
 ; CHECK-LABEL: @test_not_captured_before_load_same_bb_noalias_call(
 ; CHECK-NEXT:    [[A:%.*]] = call i32* @alloc()
-; CHECK-NEXT:    store i32 55, i32* [[A]], align 4
 ; CHECK-NEXT:    [[R:%.*]] = call i32 @getval_nounwind()
 ; CHECK-NEXT:    store i32 99, i32* [[A]], align 4
 ; CHECK-NEXT:    call void @escape_and_clobber(i32* [[A]])
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %a = call i32* @alloc()
   store i32 55, i32* %a
   %r = call i32 @getval_nounwind()
   store i32 99, i32* %a, align 4
   call void @escape_and_clobber(i32* %a)
   ret i32 %r
 }
 
 define i32 @test_not_captured_before_load_same_bb_noalias_arg(i32* noalias %a) {
 ; CHECK-LABEL: @test_not_captured_before_load_same_bb_noalias_arg(
-; CHECK-NEXT:    store i32 55, i32* [[A:%.*]], align 4
 ; CHECK-NEXT:    [[R:%.*]] = call i32 @getval_nounwind()
-; CHECK-NEXT:    store i32 99, i32* [[A]], align 4
+; CHECK-NEXT:    store i32 99, i32* [[A:%.*]], align 4
 ; CHECK-NEXT:    call void @escape_and_clobber(i32* [[A]])
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   store i32 55, i32* %a
   %r = call i32 @getval_nounwind()
   store i32 99, i32* %a, align 4
   call void @escape_and_clobber(i32* %a)
   ret i32 %r
 }

llvm/test/Transforms/DeadStoreElimination/captures-before-load.ll

;
   store i32 99, i32* %a, align 4
   call void @clobber()
   ret i32 %in.lv.2
 }
 
 define i32 @test_not_captured_before_load_same_bb_clobber(i32** %in.ptr) {
 ; CHECK-LABEL: @test_not_captured_before_load_same_bb_clobber(
 ; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
-; CHECK-NEXT:    store i32 55, i32* [[A]], align 4
 ; CHECK-NEXT:    call void @clobber()
 ; CHECK-NEXT:    [[IN_LV_1:%.*]] = load i32*, i32** [[IN_PTR:%.*]], align 2
 ; CHECK-NEXT:    [[IN_LV_2:%.*]] = load i32, i32* [[IN_LV_1]], align 2
 ; CHECK-NEXT:    store i32 99, i32* [[A]], align 4
 ; CHECK-NEXT:    call void @escape_and_clobber(i32* [[A]])
 ; CHECK-NEXT:    ret i32 [[IN_LV_2]]
 ;
   %a = alloca i32, align 4

 ; CHECK:       then:
 ; CHECK-NEXT:    call void @escape_writeonly(i32* [[A]])
 ; CHECK-NEXT:    ret i32 0
 ; CHECK:       else:
 ; CHECK-NEXT:    [[IN_LV_1:%.*]] = load i32*, i32** [[IN_PTR:%.*]], align 2
 ; CHECK-NEXT:    [[IN_LV_2:%.*]] = load i32, i32* [[IN_LV_1]], align 2
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    store i32 99, i32* [[A]], align 4
 ; CHECK-NEXT:    call void @clobber()
 ; CHECK-NEXT:    ret i32 [[IN_LV_2]]
 ;
   %a = alloca i32, align 4
   store i32 55, i32* %a
   br i1 %c.1, label %then, label %else
 
 then:
entry:
   %a.2.cast = bitcast i64* %a.2 to i8*
   call void @llvm.lifetime.end.p0i8(i64 8, i8* %a.2.cast)
   ret i64 %lv.2
 }
 
 define i32 @test_not_captured_before_load_of_ptrtoint(i64 %in) {
 ; CHECK-LABEL: @test_not_captured_before_load_of_ptrtoint(
 ; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
-; CHECK-NEXT:    store i32 55, i32* [[A]], align 4
 ; CHECK-NEXT:    [[IN_PTR:%.*]] = inttoptr i64 [[IN:%.*]] to i32*
 ; CHECK-NEXT:    [[IN_PTR_LOAD:%.*]] = load i32, i32* [[IN_PTR]], align 4
 ; CHECK-NEXT:    store i32 99, i32* [[A]], align 4
 ; CHECK-NEXT:    call void @escape_and_clobber(i32* [[A]])
 ; CHECK-NEXT:    ret i32 [[IN_PTR_LOAD]]
 ;
   %a = alloca i32, align 4
   store i32 55, i32* %a
   %in.ptr = inttoptr i64 %in to i32*
   %in.ptr.load = load i32, i32* %in.ptr
   store i32 99, i32* %a
   call void @escape_and_clobber(i32* %a)
   ret i32 %in.ptr.load
 }
 
 declare i32* @getptr()
 
 define i32 @test_not_captured_before_load_of_call() {
 ; CHECK-LABEL: @test_not_captured_before_load_of_call(
 ; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
-; CHECK-NEXT:    store i32 55, i32* [[A]], align 4
 ; CHECK-NEXT:    [[IN_PTR:%.*]] = call i32* @getptr() #[[ATTR4:[0-9]+]]
 ; CHECK-NEXT:    [[IN_PTR_LOAD:%.*]] = load i32, i32* [[IN_PTR]], align 4
 ; CHECK-NEXT:    store i32 99, i32* [[A]], align 4
 ; CHECK-NEXT:    call void @escape_and_clobber(i32* [[A]])
 ; CHECK-NEXT:    ret i32 [[IN_PTR_LOAD]]
 ;
   %a = alloca i32, align 4
   store i32 55, i32* %a
   %in.ptr = call i32* @getptr() readnone
   %in.ptr.load = load i32, i32* %in.ptr
   store i32 99, i32* %a
   call void @escape_and_clobber(i32* %a)
   ret i32 %in.ptr.load
 }
 
 define i32 @test_not_captured_multiple_objects(i1 %c, i32** %in.ptr) {
 ; CHECK-LABEL: @test_not_captured_multiple_objects(
 ; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
 ; CHECK-NEXT:    [[B:%.*]] = alloca i32, align 4
 ; CHECK-NEXT:    [[O:%.*]] = select i1 [[C:%.*]], i32* [[A]], i32* [[B]]
-; CHECK-NEXT:    store i32 55, i32* [[O]], align 4
 ; CHECK-NEXT:    [[IN_LV_1:%.*]] = load i32*, i32** [[IN_PTR:%.*]], align 2
 ; CHECK-NEXT:    [[IN_LV_2:%.*]] = load i32, i32* [[IN_LV_1]], align 2
 ; CHECK-NEXT:    store i32 99, i32* [[O]], align 4
 ; CHECK-NEXT:    call void @escape_and_clobber(i32* [[O]])
 ; CHECK-NEXT:    ret i32 [[IN_LV_2]]
 ;
   %a = alloca i32, align 4
   %b = alloca i32, align 4
   %o = select i1 %c, i32* %a, i32* %b
   store i32 55, i32* %o
   %in.lv.1 = load i32* , i32** %in.ptr, align 2
   %in.lv.2 = load i32 , i32* %in.lv.1, align 2
   store i32 99, i32* %o
   call void @escape_and_clobber(i32* %o)
   ret i32 %in.lv.2
 }

llvm/unittests/Analysis/BasicAliasAnalysisTest.cpp

protected:
   TargetLibraryInfo TLI;
   Function *F;
 
   // Things that we need to build after the function is created.
   struct TestAnalyses {
     DominatorTree DT;
     AssumptionCache AC;
     BasicAAResult BAA;
-    AAQueryInfo AAQI;
+    SimpleAAQueryInfo AAQI;
 
     TestAnalyses(BasicAATest &Test)
         : DT(*Test.F), AC(*Test.F), BAA(Test.DL, *Test.F, Test.TLI, AC, &DT),
           AAQI() {}
   };
 
   llvm::Optional<TestAnalyses> Analyses;