[DSE,MemorySSA] Use BatchAA for AA queries.

[fhahn]

Summary

We can use BatchAA to avoid some repeated AA queries. We only remove
stores, so I think we will get away with using a single BatchAA instance
for the complete run.

The changes in AliasAnalysis.h mirror the changes in D85583.

The change improves compile-time by roughly 1%.
http://llvm-compile-time-tracker.com/compare.php?from=67ad786353dfcc7633c65de11601d7823746378e&to=10529e5b43809808e8c198f88fffd8f756554e45&stat=instructions

This is part of the patches to bring down compile-time to the level
referenced in
http://lists.llvm.org/pipermail/llvm-dev/2020-August/144417.html

[asbirlea]

The improvement looks great!

The alias cache relies on MemoryLocations and should be valid. The nonEscaping cache relies on pointers, so here I had reservations on what happens if a store is in cache and gets removed. There are no future queries for it, and there are no new values in DSE that may reuse that pointer. So I *think* this is correct, but it needs some documentation in the pass on why BatchAA is ok to use here.
I think it's necessary for the assumptions to be made clear in case the pass changes for some reason and breaks those assumptions; also if new caches are added in BatchAA, its users should have it clearly specified on what behavior they rely.

[fhahn]

In D86275#2229617, @asbirlea wrote:

The improvement looks great!

Yep, but just to note, this improvements is already included in the numbers shared on llvm-dev.

The alias cache relies on MemoryLocations and should be valid. The nonEscaping cache relies on pointers, so here I had reservations on what happens if a store is in cache and gets removed. There are no future queries for it, and there are no new values in DSE that may reuse that pointer. So I *think* this is correct, but it needs some documentation in the pass on why BatchAA is ok to use here.
I think it's necessary for the assumptions to be made clear in case the pass changes for some reason and breaks those assumptions; also if new caches are added in BatchAA, its users should have it clearly specified on what behavior they rely.

That makes sense! I added a comment to the BatchAA member in DSEState. Do you think that is sufficient?

[asbirlea]

Yes, that looks good to me, thank you!

llvm/include/llvm/Analysis/AliasAnalysis.h

ModRefInfo getModRefInfo(Instruction *I, const CallBase *Call2) {
     return AA.getModRefInfo(I, Call2, AAQI);
   }
   ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) {
     return AA.getArgModRefInfo(Call, ArgIdx);
   }
   FunctionModRefBehavior getModRefBehavior(const CallBase *Call) {
     return AA.getModRefBehavior(Call);
   }
+  bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
+    return alias(LocA, LocB) == MustAlias;
+  }
+  bool isMustAlias(const Value *V1, const Value *V2) {
+    return alias(MemoryLocation(V1, LocationSize::precise(1)),
+                 MemoryLocation(V2, LocationSize::precise(1))) == MustAlias;
+  }
 };
 
 /// Temporary typedef for legacy code that uses a generic \c AliasAnalysis
 /// pointer or reference.
 using AliasAnalysis = AAResults;
 
 /// A private abstract base class describing the concept of an individual alias
 /// analysis implementation.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

 } // end anonymous namespace
 
 /// Return 'OW_Complete' if a store to the 'Later' location completely
 /// overwrites a store to the 'Earlier' location. Return OW_MaybePartial
 /// if \p Later does not completely overwrite \p Earlier, but they both
 /// write to the same underlying object. In that case, use isPartialOverwrite to
 /// check if \p Later partially overwrites \p Earlier. Returns 'OW_Unknown' if
 /// nothing can be determined.
-static OverwriteResult isOverwrite(const MemoryLocation &Later,
-                                   const MemoryLocation &Earlier,
-                                   const DataLayout &DL,
-                                   const TargetLibraryInfo &TLI,
-                                   int64_t &EarlierOff, int64_t &LaterOff,
-                                   AliasAnalysis &AA, const Function *F) {
+template <typename AATy>
+static OverwriteResult
+isOverwrite(const MemoryLocation &Later, const MemoryLocation &Earlier,
+            const DataLayout &DL, const TargetLibraryInfo &TLI,
+            int64_t &EarlierOff, int64_t &LaterOff, AATy &AA,
+            const Function *F) {
   // FIXME: Vet that this works for size upper-bounds. Seems unlikely that we'll
   // get imprecise values here, though (except for unknown sizes).
   if (!Later.Size.isPrecise() || !Earlier.Size.isPrecise())
     return OW_Unknown;
 
   const uint64_t LaterSize = Later.Size.getValue();
   const uint64_t EarlierSize = Earlier.Size.getValue();
 
static bool isPossibleSelfRead(Instruction *Inst,
   // then it can't be considered dead.
   return true;
 }
 
 /// Returns true if the memory which is accessed by the second instruction is not
 /// modified between the first and the second instruction.
 /// Precondition: Second instruction must be dominated by the first
 /// instruction.
-static bool memoryIsNotModifiedBetween(Instruction *FirstI,
-                                       Instruction *SecondI,
-                                       AliasAnalysis *AA,
-                                       const DataLayout &DL,
-                                       DominatorTree *DT) {
+template <typename AATy>
+static bool
+memoryIsNotModifiedBetween(Instruction *FirstI, Instruction *SecondI, AATy &AA,
+                           const DataLayout &DL, DominatorTree *DT) {
   // Do a backwards scan through the CFG from SecondI to FirstI. Look for
   // instructions which can modify the memory location accessed by SecondI.
   //
   // While doing the walk keep track of the address to check. It might be
   // different in different basic blocks due to PHI translation.
   using BlockAddressPair = std::pair<BasicBlock *, PHITransAddr>;
   SmallVector<BlockAddressPair, 16> WorkList;
   // Keep track of the address we visited each block with. Bail out if we
while (!WorkList.empty()) {
     } else {
       // It's not SecondBB or (in case of a loop) the second visit of SecondBB.
       // In this case we also have to look at instructions after SecondI.
       EI = B->end();
     }
     for (; BI != EI; ++BI) {
       Instruction *I = &*BI;
       if (I->mayWriteToMemory() && I != SecondI)
-        if (isModSet(AA->getModRefInfo(I, MemLoc.getWithNewPtr(Ptr))))
+        if (isModSet(AA.getModRefInfo(I, MemLoc.getWithNewPtr(Ptr))))
           return false;
     }
     if (B != FirstBB) {
       assert(B != &FirstBB->getParent()->getEntryBlock() &&
           "Should not hit the entry block because SI must be dominated by LI");
       for (auto PredI = pred_begin(B), PE = pred_end(B); PredI != PE; ++PredI) {
         PHITransAddr PredAddr = Addr;
         if (PredAddr.NeedsPHITranslationFromBlock(B)) {
static bool eliminateNoopStore(Instruction *Inst, BasicBlock::iterator &BBI,
   if (!SI)
     return false;
 
   // If we're storing the same value back to a pointer that we just loaded from,
   // then the store can be removed.
   if (LoadInst *DepLoad = dyn_cast<LoadInst>(SI->getValueOperand())) {
     if (SI->getPointerOperand() == DepLoad->getPointerOperand() &&
         isRemovable(SI) &&
-        memoryIsNotModifiedBetween(DepLoad, SI, AA, DL, DT)) {
+        memoryIsNotModifiedBetween(DepLoad, SI, *AA, DL, DT)) {
 
       LLVM_DEBUG(
           dbgs() << "DSE: Remove Store Of Load from same pointer:\n  LOAD: "
                  << *DepLoad << "\n  STORE: " << *SI << '\n');
 
       deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL, ThrowableInst);
       ++NumRedundantStores;
       return true;
     }
   }
 
   // Remove null stores into the calloc'ed objects
   Constant *StoredConstant = dyn_cast<Constant>(SI->getValueOperand());
   if (StoredConstant && StoredConstant->isNullValue() && isRemovable(SI)) {
     Instruction *UnderlyingPointer =
         dyn_cast<Instruction>(getUnderlyingObject(SI->getPointerOperand()));
 
     if (UnderlyingPointer && isCallocLikeFn(UnderlyingPointer, TLI) &&
-        memoryIsNotModifiedBetween(UnderlyingPointer, SI, AA, DL, DT)) {
+        memoryIsNotModifiedBetween(UnderlyingPointer, SI, *AA, DL, DT)) {
       LLVM_DEBUG(
           dbgs() << "DSE: Remove null store to the calloc'ed object:\n  DEAD: "
                  << *Inst << "\n  OBJECT: " << *UnderlyingPointer << '\n');
 
       deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL, ThrowableInst);
       ++NumRedundantStores;
       return true;
     }
   }
   return false;
 }
 
-static Constant *
-tryToMergePartialOverlappingStores(StoreInst *Earlier, StoreInst *Later,
-                                   int64_t InstWriteOffset,
-                                   int64_t DepWriteOffset, const DataLayout &DL,
-                                   AliasAnalysis *AA, DominatorTree *DT) {
+template <typename AATy>
+static Constant *tryToMergePartialOverlappingStores(
+    StoreInst *Earlier, StoreInst *Later, int64_t InstWriteOffset,
+    int64_t DepWriteOffset, const DataLayout &DL, AATy &AA, DominatorTree *DT) {
 
   if (Earlier && isa<ConstantInt>(Earlier->getValueOperand()) &&
       DL.typeSizeEqualsStoreSize(Earlier->getValueOperand()->getType()) &&
       Later && isa<ConstantInt>(Later->getValueOperand()) &&
       DL.typeSizeEqualsStoreSize(Later->getValueOperand()->getType()) &&
       memoryIsNotModifiedBetween(Earlier, Later, AA, DL, DT)) {
     // If the store we find is:
     //   a) partially overwritten by the store to 'Loc'
while (InstDep.isDef() || InstDep.isClobber()) {
           bool IsOverwriteEnd = (OR == OW_End);
           MadeChange |= tryToShorten(DepWrite, DepWriteOffset, EarlierSize,
                                     InstWriteOffset, LaterSize, IsOverwriteEnd);
         } else if (EnablePartialStoreMerging &&
                    OR == OW_PartialEarlierWithFullLater) {
           auto *Earlier = dyn_cast<StoreInst>(DepWrite);
           auto *Later = dyn_cast<StoreInst>(Inst);
           if (Constant *C = tryToMergePartialOverlappingStores(
-                  Earlier, Later, InstWriteOffset, DepWriteOffset, DL, AA,
+                  Earlier, Later, InstWriteOffset, DepWriteOffset, DL, *AA,
                   DT)) {
             auto *SI = new StoreInst(
                 C, Earlier->getPointerOperand(), false, Earlier->getAlign(),
                 Earlier->getOrdering(), Earlier->getSyncScopeID(), DepWrite);
 
             unsigned MDToKeep[] = {LLVMContext::MD_dbg, LLVMContext::MD_tbaa,
                                    LLVMContext::MD_alias_scope,
                                    LLVMContext::MD_noalias,
if (isNoopIntrinsic(D))
     return true;
 
   return false;
 }
 
 struct DSEState {
   Function &F;
   AliasAnalysis &AA;
+
+  /// 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.
+  BatchAAResults BatchAA;
+
   MemorySSA &MSSA;
   DominatorTree &DT;
   PostDominatorTree &PDT;
   const TargetLibraryInfo &TLI;
 
   // All MemoryDefs that potentially could kill other MemDefs.
   SmallVector<MemoryDef *, 64> MemDefs;
   // Any that should be skipped as they are already deleted
struct DSEState {
   DenseMap<BasicBlock *, unsigned> PostOrderNumbers;
 
   /// Keep track of instructions (partly) overlapping with killing MemoryDefs per
   /// basic block.
   DenseMap<BasicBlock *, InstOverlapIntervalsTy> IOLs;
 
   DSEState(Function &F, AliasAnalysis &AA, MemorySSA &MSSA, DominatorTree &DT,
            PostDominatorTree &PDT, const TargetLibraryInfo &TLI)
-      : F(F), AA(AA), MSSA(MSSA), DT(DT), PDT(PDT), TLI(TLI) {}
+      : F(F), AA(AA), BatchAA(AA), MSSA(MSSA), DT(DT), PDT(PDT), TLI(TLI) {}
 
   static DSEState get(Function &F, AliasAnalysis &AA, MemorySSA &MSSA,
                       DominatorTree &DT, PostDominatorTree &PDT,
                       const TargetLibraryInfo &TLI) {
     DSEState State(F, AA, MSSA, DT, PDT, TLI);
     // Collect blocks with throwing instructions not modeled in MemorySSA and
     // alloc-like objects.
     unsigned PO = 0;
if (auto *CB = dyn_cast<CallBase>(I)) {
       }
       return None;
     }
 
     return MemoryLocation::getOrNone(I);
   }
 
   /// Returns true if \p Use completely overwrites \p DefLoc.
-  bool isCompleteOverwrite(MemoryLocation DefLoc, Instruction *UseInst) const {
+  bool isCompleteOverwrite(MemoryLocation DefLoc, Instruction *UseInst) {
     // UseInst has a MemoryDef associated in MemorySSA. It's possible for a
     // MemoryDef to not write to memory, e.g. a volatile load is modeled as a
     // MemoryDef.
     if (!UseInst->mayWriteToMemory())
       return false;
 
     if (auto *CB = dyn_cast<CallBase>(UseInst))
       if (CB->onlyAccessesInaccessibleMemory())
         return false;
 
     int64_t InstWriteOffset, DepWriteOffset;
     auto CC = getLocForWriteEx(UseInst);
     const DataLayout &DL = F.getParent()->getDataLayout();
     return CC && isOverwrite(*CC, DefLoc, DL, TLI, DepWriteOffset,
-                             InstWriteOffset, AA, &F) == OW_Complete;
+                             InstWriteOffset, BatchAA, &F) == OW_Complete;
   }
 
   /// Returns true if \p Def is not read before returning from the function.
   bool isWriteAtEndOfFunction(MemoryDef *Def) {
     LLVM_DEBUG(dbgs() << "  Check if def " << *Def << " ("
                       << *Def->getMemoryInst()
                       << ") is at the end the function \n");
 
struct DSEState {
   bool isMemTerminatorInst(Instruction *I) const {
     IntrinsicInst *II = dyn_cast<IntrinsicInst>(I);
     return (II && II->getIntrinsicID() == Intrinsic::lifetime_end) ||
            isFreeCall(I, &TLI);
   }
 
   /// Returns true if \p MaybeTerm is a memory terminator for the same
   /// underlying object as \p DefLoc.
-  bool isMemTerminator(MemoryLocation DefLoc, Instruction *MaybeTerm) const {
+  bool isMemTerminator(MemoryLocation DefLoc, Instruction *MaybeTerm) {
     Optional<std::pair<MemoryLocation, bool>> MaybeTermLoc =
         getLocForTerminator(MaybeTerm);
 
     if (!MaybeTermLoc)
       return false;
 
     // If the terminator is a free-like call, all accesses to the underlying
     // object can be considered terminated.
     if (MaybeTermLoc->second) {
       DataLayout DL = MaybeTerm->getParent()->getModule()->getDataLayout();
       DefLoc = MemoryLocation(getUnderlyingObject(DefLoc.Ptr));
     }
-    return AA.isMustAlias(MaybeTermLoc->first, DefLoc);
+    return BatchAA.isMustAlias(MaybeTermLoc->first, DefLoc);
   }
 
   // Returns true if \p Use may read from \p DefLoc.
-  bool isReadClobber(MemoryLocation DefLoc, Instruction *UseInst) const {
+  bool isReadClobber(MemoryLocation DefLoc, Instruction *UseInst) {
     if (!UseInst->mayReadFromMemory())
       return false;
 
     if (auto *CB = dyn_cast<CallBase>(UseInst))
       if (CB->onlyAccessesInaccessibleMemory())
         return false;
 
-    ModRefInfo MR = AA.getModRefInfo(UseInst, DefLoc);
+    ModRefInfo MR = BatchAA.getModRefInfo(UseInst, DefLoc);
     // If necessary, perform additional analysis.
     if (isRefSet(MR))
       MR = AA.callCapturesBefore(UseInst, DefLoc, &DT);
     return isRefSet(MR);
   }
 
   // Find a MemoryDef writing to \p DefLoc and dominating \p Current, with no
   // read access between them or on any other path to a function exit block if
   // \p DefLoc is not accessible after the function returns. If there is no such
   // MemoryDef, return None. The returned value may not (completely) overwrite
   // \p DefLoc. Currently we bail out when we encounter an aliasing MemoryUse
   // (read).
   Optional<MemoryAccess *>
   getDomMemoryDef(MemoryDef *KillingDef, MemoryAccess *Current,
                   MemoryLocation DefLoc, bool DefVisibleToCallerBeforeRet,
-                  bool DefVisibleToCallerAfterRet, unsigned &ScanLimit) const {
+                  bool DefVisibleToCallerAfterRet, unsigned &ScanLimit) {
     if (ScanLimit == 0) {
       LLVM_DEBUG(dbgs() << "\n    ...  hit scan limit\n");
       return None;
     }
 
     MemoryAccess *DomAccess;
     bool StepAgain;
     LLVM_DEBUG(dbgs() << "  trying to get dominating access for " << *Current
for (unsigned I = 0; I < ToCheck.size(); I++) {
                           << "\n  KILLER: " << *SI << '\n');
         State.deleteDeadInstruction(NI);
         ++NumFastStores;
         MadeChange = true;
       } else {
         // Check if NI overwrites SI.
         int64_t InstWriteOffset, DepWriteOffset;
         OverwriteResult OR = isOverwrite(SILoc, NILoc, DL, TLI, DepWriteOffset,
-                                         InstWriteOffset, State.AA, &F);
+                                         InstWriteOffset, State.BatchAA, &F);
         if (OR == OW_MaybePartial) {
           auto Iter = State.IOLs.insert(
               std::make_pair<BasicBlock *, InstOverlapIntervalsTy>(
                   NI->getParent(), InstOverlapIntervalsTy()));
           auto &IOL = Iter.first->second;
           OR = isPartialOverwrite(SILoc, NILoc, DepWriteOffset, InstWriteOffset,
                                   NI, IOL);
         }
 
         if (EnablePartialStoreMerging && OR == OW_PartialEarlierWithFullLater) {
           auto *Earlier = dyn_cast<StoreInst>(NI);
           auto *Later = dyn_cast<StoreInst>(SI);
           // We are re-using tryToMergePartialOverlappingStores, which requires
           // Earlier to domiante Later.
           // TODO: implement tryToMergeParialOverlappingStores using MemorySSA.
           if (Earlier && Later && DT.dominates(Earlier, Later)) {
             if (Constant *Merged = tryToMergePartialOverlappingStores(
-                    Earlier, Later, InstWriteOffset, DepWriteOffset, DL, &AA,
-                    &DT)) {
+                    Earlier, Later, InstWriteOffset, DepWriteOffset, DL,
+                    State.BatchAA, &DT)) {
 
               // Update stored value of earlier store to merged constant.
               Earlier->setOperand(0, Merged);
               ++NumModifiedStores;
               MadeChange = true;
 
               // Remove later store and remove any outstanding overlap intervals
               // for the updated store.