[CaptureTracking] Ignore ephemeral values in EarliestEscapeInfo

[aeubanks]

Summary

And thread DSE's ephemeral values to EarliestEscapeInfo.

This allows more precise analysis in DSEState::isReadClobber() via BatchAA.

Followup to D123162.

[nikic]

LGTM

llvm/include/llvm/Analysis/AliasAnalysis.h

 class CatchReturnInst;
 class DominatorTree;
 class FenceInst;
 class Function;
 class LoopInfo;
 class PreservedAnalyses;
 class TargetLibraryInfo;
 class Value;
+template <typename> class SmallPtrSetImpl;
 
 /// The possible results of an alias query.
 ///
 /// These results are always computed between two MemoryLocation objects as
 /// a query to some alias analysis.
 ///
 /// Note that these are unscoped enumerations because we would like to support
 /// implicitly testing a result for the existence of any possible aliasing with
class EarliestEscapeInfo final : public CaptureInfo {
   /// 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;
 
+  const SmallPtrSetImpl<const Value *> &EphValues;
+
 public:
-  EarliestEscapeInfo(DominatorTree &DT, const LoopInfo &LI) : DT(DT), LI(LI) {}
+  EarliestEscapeInfo(DominatorTree &DT, const LoopInfo &LI,
+                     const SmallPtrSetImpl<const Value *> &EphValues)
+      : DT(DT), LI(LI), EphValues(EphValues) {}
 
   bool isNotCapturedBeforeOrAt(const Value *Object,
                                const Instruction *I) override;
 
   void removeInstruction(Instruction *I);
 };
 
 /// Reduced version of MemoryLocation that only stores a pointer and size.

llvm/include/llvm/Analysis/CaptureTracking.h

namespace llvm {
   // Returns the 'earliest' instruction that captures \p V in \F. An instruction
   // A is considered earlier than instruction B, if A dominates B. If 2 escapes
   // do not dominate each other, the terminator of the common dominator is
   // chosen. If not all uses can be analyzed, the earliest escape is set to
   // the first instruction in the function entry block. If \p V does not escape,
   // nullptr is returned. Note that the caller of the function has to ensure
   // that the instruction the result value is compared against is not in a
   // cycle.
-  Instruction *FindEarliestCapture(const Value *V, Function &F,
-                                   bool ReturnCaptures, bool StoreCaptures,
-                                   const DominatorTree &DT,
-                                   unsigned MaxUsesToExplore = 0);
+  Instruction *
+  FindEarliestCapture(const Value *V, Function &F, bool ReturnCaptures,
+                      bool StoreCaptures, const DominatorTree &DT,
+                      const SmallPtrSetImpl<const Value *> &EphValues,
 
   /// This callback is used in conjunction with PointerMayBeCaptured. In
   /// addition to the interface here, you'll need to provide your own getters
   /// to see whether anything was captured.
   struct CaptureTracker {
     virtual ~CaptureTracker();
 
     /// tooManyUses - The depth of traversal has breached a limit. There may be

llvm/lib/Analysis/BasicAliasAnalysis.cpp

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);
+        /*ReturnCaptures=*/false, /*StoreCaptures=*/true, DT, EphValues);
     if (EarliestCapture) {
       auto Ins = Inst2Obj.insert({EarliestCapture, {}});
       Ins.first->second.push_back(Object);
     }
     Iter.first->second = EarliestCapture;
   }
 
   // No capturing instruction.

llvm/lib/Analysis/CaptureTracking.cpp

namespace {
   /// B, if A dominates B. If 2 escapes do not dominate each other, the
   /// terminator of the common dominator is chosen. If not all uses cannot be
   /// analyzed, the earliest escape is set to the first instruction in the
   /// function entry block.
   // NOTE: Users have to make sure instructions compared against the earliest
   // escape are not in a cycle.
   struct EarliestCaptures : public CaptureTracker {
 
-    EarliestCaptures(bool ReturnCaptures, Function &F, const DominatorTree &DT)
-        : DT(DT), ReturnCaptures(ReturnCaptures), F(F) {}
+    EarliestCaptures(bool ReturnCaptures, Function &F, const DominatorTree &DT,
+                     const SmallPtrSetImpl<const Value *> &EphValues)
+        : EphValues(EphValues), DT(DT), ReturnCaptures(ReturnCaptures), F(F) {}
 
     void tooManyUses() override {
       Captured = true;
       EarliestCapture = &*F.getEntryBlock().begin();
     }
 
     bool captured(const Use *U) override {
       Instruction *I = cast<Instruction>(U->getUser());
       if (isa<ReturnInst>(I) && !ReturnCaptures)
         return false;
 
+      if (EphValues.contains(I))
+        return false;
+
       if (!EarliestCapture) {
         EarliestCapture = I;
       } else if (EarliestCapture->getParent() == I->getParent()) {
         if (I->comesBefore(EarliestCapture))
           EarliestCapture = I;
       } else {
         BasicBlock *CurrentBB = I->getParent();
         BasicBlock *EarliestBB = EarliestCapture->getParent();
bool captured(const Use *U) override {
       }
       Captured = true;
 
       // Return false to continue analysis; we need to see all potential
       // captures.
       return false;
     }
 
+    const SmallPtrSetImpl<const Value *> &EphValues;
+
     Instruction *EarliestCapture = nullptr;
 
     const DominatorTree &DT;
 
     bool ReturnCaptures;
 
     bool Captured = false;
 
bool llvm::PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures,
   PointerMayBeCaptured(V, &CB, MaxUsesToExplore);
   if (CB.Captured)
     ++NumCapturedBefore;
   else
     ++NumNotCapturedBefore;
   return CB.Captured;
 }
 
-Instruction *llvm::FindEarliestCapture(const Value *V, Function &F,
-                                       bool ReturnCaptures, bool StoreCaptures,
-                                       const DominatorTree &DT,
-                                       unsigned MaxUsesToExplore) {
+Instruction *
+llvm::FindEarliestCapture(const Value *V, Function &F, bool ReturnCaptures,
+                          bool StoreCaptures, const DominatorTree &DT,
+
+                          const SmallPtrSetImpl<const Value *> &EphValues,
   assert(!isa<GlobalValue>(V) &&
          "It doesn't make sense to ask whether a global is captured.");
 
-  EarliestCaptures CB(ReturnCaptures, F, DT);
+  EarliestCaptures CB(ReturnCaptures, F, DT, EphValues);
   PointerMayBeCaptured(V, &CB, MaxUsesToExplore);
   if (CB.Captured)
     ++NumCapturedBefore;
   else
     ++NumNotCapturedBefore;
   return CB.EarliestCapture;
 }
 

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

struct DSEState {
 
   // Class contains self-reference, make sure it's not copied/moved.
   DSEState(const DSEState &) = delete;
   DSEState &operator=(const DSEState &) = delete;
 
   DSEState(Function &F, AliasAnalysis &AA, MemorySSA &MSSA, DominatorTree &DT,
            PostDominatorTree &PDT, AssumptionCache &AC,
            const TargetLibraryInfo &TLI, const LoopInfo &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) {
+      : F(F), AA(AA), EI(DT, LI, EphValues), BatchAA(AA, &EI), MSSA(MSSA),
+        DT(DT), PDT(PDT), TLI(TLI), DL(F.getParent()->getDataLayout()), LI(LI) {
     // Collect blocks with throwing instructions not modeled in MemorySSA and
     // alloc-like objects.
     unsigned PO = 0;
     for (BasicBlock *BB : post_order(&F)) {
       PostOrderNumbers[BB] = PO++;
       for (Instruction &I : *BB) {
         MemoryAccess *MA = MSSA.getMemoryAccess(&I);
         if (I.mayThrow() && !MA)

llvm/test/Transforms/DeadStoreElimination/assume.ll

;
   ret void
 }
 
 define void @f2() {
 ; CHECK-LABEL: @f2(
 ; CHECK-NEXT:    [[TMP1:%.*]] = call noalias i8* @_Znwm(i64 32)
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp ugt i8* [[TMP1]], @global
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[TMP2]])
-; CHECK-NEXT:    store i8 0, i8* [[TMP1]], align 1
 ; CHECK-NEXT:    call void @quux(i8* @global)
 ; CHECK-NEXT:    ret void
 ;
   %tmp1 = call noalias i8* @_Znwm(i64 32)
   %tmp2 = icmp ugt i8* %tmp1, @global
   call void @llvm.assume(i1 %tmp2)
   store i8 0, i8* %tmp1, align 1
   call void @quux(i8* @global)
   ret void
 }
 
 declare i8* @_Znwm(i64)
 
 declare void @llvm.assume(i1)
 
 declare void @quux(i8*)