[MemCpyOpt] Use EarliestEscapeInfo instead of callCapturesBefore.

[fhahn]

Summary

D110368 exposed 'earliest escape' handling in BatchAA. We can use this
via BatchAA instead of the single call of callCapturesBefore in
MemCpyOpt to improve the results in most cases.

On SPEC2006/SPEC2017/MultiSource we get the following changes:

Metric: memcpyopt.NumCallSlot

test-suite.../CINT2006/403.gcc/403.gcc.test    17.00  26.00       52.9%
test-suite...510.parest_r/510.parest_r.test   718.00 773.00        7.7%
test-suite...006/447.dealII/447.dealII.test    12.00  12.00        0.0%
test-suite...yApps-C++/PENNANT/PENNANT.test     9.00   9.00        0.0%
test-suite...speed/602.gcc_s/602.gcc_s.test    15.00  14.00       -6.7%
test-suite...7rate/502.gcc_r/502.gcc_r.test    15.00  14.00       -6.7%

Metric: memcpyopt.NumMemCpyInstr
test-suite.../CINT2006/403.gcc/403.gcc.test     47.00   62.00      31.9%
test-suite...510.parest_r/510.parest_r.test   1600.00 1654.00       3.4%
test-suite...006/447.dealII/447.dealII.test    108.00  108.00       0.0%
test-suite...marks/7zip/7zip-benchmark.test     10.00   10.00       0.0%
test-suite...yApps-C++/PENNANT/PENNANT.test     13.00   13.00       0.0%
test-suite...speed/602.gcc_s/602.gcc_s.test     91.00   90.00      -1.1%
test-suite...7rate/502.gcc_r/502.gcc_r.test     91.00   90.00      -1.1%

Metric: memcpyopt.NumMoveToCpy
test-suite...marks/7zip/7zip-benchmark.test     4.00  19.00       375.0%
test-suite...006/447.dealII/447.dealII.test   122.00 150.00        23.0%
test-suite...510.parest_r/510.parest_r.test   322.00 394.00        22.4%
test-suite...speed/602.gcc_s/602.gcc_s.test      NaN    NaN          NaN
test-suite...7rate/502.gcc_r/502.gcc_r.test      NaN    NaN          NaN
test-suite.../CINT2006/403.gcc/403.gcc.test      NaN    NaN          NaN
test-suite...yApps-C++/PENNANT/PENNANT.test      NaN   4.00          NaN

No changes for memcpyopt.NumMemSetInfer

Compile-time impact

NewPM-O3: +0.02 (outlier mafft +0.31%)
NewPM-ReleaseThinLTO: +0.01% (no notable outliers)
NewPM-ReleaseLTO-g: +0.03% (no notable outliers)

[nikic]

The global use of BatchAA in DSE is based on the justification that DSE does not add new instructions while BatchAA is in use -- this means that even though there may be stale entries in the alias cache (stale in the sense of having the location pointing to a deleted instruction), these will not get accidentally reused by newly allocated instructions.

I don't believe that this logic holds up for MemCpyOpt, which does create new instructions. I also suspect that it may modify existing instructions in ways that could render cached alias information invalid (not sure on that though).

[asbirlea]

+1 on Nikita's comment that BatchAA cannot be used with a single instance for MemCpyOpt.

However, perhaps it's worth considering using it on the call paths when no memory instructions are created, and at least some of the improved results will remain.
The question is what's the cost of creating a BatchAA instance every time one of the calls in iterateOnFunction returns true (either all those adding instructions, or change all APIs to return a {MadeChange, AddedMemInstr} pair).

I'd compare the cost of the extra memory for keeping the EI and BAA alongside AA, plus compile for creating the BAA instance on every mem instruction insert, with the improved metrics obtained, and see if it's worth pursuing.

[fhahn]

Thanks for raising the issue @nikic & @asbirlea!

Unfortunately I do not really have time to dig deeper here for now. I don't think trying to invalidate BatchAA/EI would be worth the effort, but trying @asbirlea seems interesting. I might pick that up some time in the future. If anyone is interested in picking this up in the meantime that would be great as well :)

llvm/include/llvm/Analysis/AliasAnalysis.h

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;
+  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) {}
+  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.

llvm/include/llvm/Transforms/Scalar/MemCpyOptimizer.h

 
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/PassManager.h"
 #include <cstdint>
 #include <functional>
 
 namespace llvm {
 
-class AAResults;
+class BatchAAResults;
 class AssumptionCache;
 class CallBase;
 class CallInst;
 class DominatorTree;
 class Function;
 class Instruction;
 class LoadInst;
 class MemCpyInst;
 class MemMoveInst;
 class MemorySSA;
 class MemorySSAUpdater;
 class MemSetInst;
 class StoreInst;
 class TargetLibraryInfo;
 class Value;
 
 class MemCpyOptPass : public PassInfoMixin<MemCpyOptPass> {
   TargetLibraryInfo *TLI = nullptr;
-  AAResults *AA = nullptr;
+  BatchAAResults *AA = nullptr;
   AssumptionCache *AC = nullptr;
   DominatorTree *DT = nullptr;
   MemorySSA *MSSA = nullptr;
   MemorySSAUpdater *MSSAU = nullptr;
 
 public:
   MemCpyOptPass() = default;
 
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 
   // Glue for the old PM.
-  bool runImpl(Function &F, TargetLibraryInfo *TLI, AAResults *AA,
+  bool runImpl(Function &F, TargetLibraryInfo *TLI, BatchAAResults *AA,
                AssumptionCache *AC, DominatorTree *DT, MemorySSA *MSSA);
 
 private:
   // Helper functions
   bool processStore(StoreInst *SI, BasicBlock::iterator &BBI);
   bool processMemSet(MemSetInst *SI, BasicBlock::iterator &BBI);
   bool processMemCpy(MemCpyInst *M, BasicBlock::iterator &BBI);
   bool processMemMove(MemMoveInst *M);

llvm/lib/Analysis/BasicAliasAnalysis.cpp

if (Iter.second) {
     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);
+         !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);

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, const TargetLibraryInfo &TLI,
            const LoopInfo &LI)
-      : F(F), AA(AA), EI(DT, LI), BatchAA(AA, &EI), MSSA(MSSA), DT(DT),
+      : F(F), AA(AA), EI(DT, &LI), 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);

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

 
 void MemCpyOptPass::eraseInstruction(Instruction *I) {
   MSSAU->removeMemoryAccess(I);
   I->eraseFromParent();
 }
 
 // Check for mod or ref of Loc between Start and End, excluding both boundaries.
 // Start and End must be in the same block
-static bool accessedBetween(AliasAnalysis &AA, MemoryLocation Loc,
+static bool accessedBetween(BatchAAResults &AA, MemoryLocation Loc,
                             const MemoryUseOrDef *Start,
                             const MemoryUseOrDef *End) {
   assert(Start->getBlock() == End->getBlock() && "Only local supported");
   for (const MemoryAccess &MA :
        make_range(++Start->getIterator(), End->getIterator())) {
     if (isModOrRefSet(AA.getModRefInfo(cast<MemoryUseOrDef>(MA).getMemoryInst(),
                                        Loc)))
       return true;
if (!DT->dominates(cpyDest, C)) {
     else
       return false;
   }
 
   // In addition to knowing that the call does not access src in some
   // unexpected manner, for example via a global, which we deduce from
   // the use analysis, we also need to know that it does not sneakily
   // access dest.  We rely on AA to figure this out for us.
-  ModRefInfo MR = AA->getModRefInfo(C, cpyDest, LocationSize::precise(srcSize));
-  // If necessary, perform additional analysis.
-  if (isModOrRefSet(MR))
-    MR = AA->callCapturesBefore(C, cpyDest, LocationSize::precise(srcSize), DT);
+  ModRefInfo MR = AA->getModRefInfo(
+      C, MemoryLocation(cpyDest, LocationSize::precise(srcSize)));
   if (isModOrRefSet(MR))
     return false;
 
   // We can't create address space casts here because we don't know if they're
   // safe for the target.
   if (cpySrc->getType()->getPointerAddressSpace() !=
       cpyDest->getType()->getPointerAddressSpace())
     return false;
bool MemCpyOptPass::processMemSetMemCpyDependence(MemCpyInst *MemCpy,
   MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
 
   eraseInstruction(MemSet);
   return true;
 }
 
 /// Determine whether the instruction has undefined content for the given Size,
 /// either because it was freshly alloca'd or started its lifetime.
-static bool hasUndefContents(MemorySSA *MSSA, AliasAnalysis *AA, Value *V,
+static bool hasUndefContents(MemorySSA *MSSA, BatchAAResults *AA, Value *V,
                              MemoryDef *Def, Value *Size) {
   if (MSSA->isLiveOnEntryDef(Def))
     return isa<AllocaInst>(getUnderlyingObject(V));
 
   if (IntrinsicInst *II =
           dyn_cast_or_null<IntrinsicInst>(Def->getMemoryInst())) {
     if (II->getIntrinsicID() == Intrinsic::lifetime_start) {
       ConstantInt *LTSize = cast<ConstantInt>(II->getArgOperand(0));

 
 PreservedAnalyses MemCpyOptPass::run(Function &F, FunctionAnalysisManager &AM) {
   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
   auto *AA = &AM.getResult<AAManager>(F);
   auto *AC = &AM.getResult<AssumptionAnalysis>(F);
   auto *DT = &AM.getResult<DominatorTreeAnalysis>(F);
   auto *MSSA = &AM.getResult<MemorySSAAnalysis>(F);
 
-  bool MadeChange = runImpl(F, &TLI, AA, AC, DT, &MSSA->getMSSA());
+  EarliestEscapeInfo EI(*DT, nullptr);
+  BatchAAResults BatchAA(*AA, &EI);
+
+  bool MadeChange = runImpl(F, &TLI, &BatchAA, AC, DT, &MSSA->getMSSA());
   if (!MadeChange)
     return PreservedAnalyses::all();
 
   PreservedAnalyses PA;
   PA.preserveSet<CFGAnalyses>();
   PA.preserve<MemorySSAAnalysis>();
   return PA;
 }
 
 bool MemCpyOptPass::runImpl(Function &F, TargetLibraryInfo *TLI_,
-                            AliasAnalysis *AA_, AssumptionCache *AC_,
+                            BatchAAResults *AA_, AssumptionCache *AC_,
                             DominatorTree *DT_, MemorySSA *MSSA_) {
   bool MadeChange = false;
   TLI = TLI_;
   AA = AA_;
   AC = AC_;
   DT = DT_;
   MSSA = MSSA_;
   MemorySSAUpdater MSSAU_(MSSA_);
if (skipFunction(F))
     return false;
 
   auto *TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
   auto *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
   auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
   auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   auto *MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
 
-  return Impl.runImpl(F, TLI, AA, AC, DT, MSSA);
+  EarliestEscapeInfo EI(*DT, nullptr);
+  BatchAAResults BatchAA(*AA, &EI);
+
+  return Impl.runImpl(F, TLI, &BatchAA, AC, DT, MSSA);
 }

llvm/test/Transforms/MemCpyOpt/callslot.ll

 ; CHECK-NEXT:    [[SRC:%.*]] = alloca [16 x i8], align 1
 ; CHECK-NEXT:    [[DEST_I8:%.*]] = bitcast [16 x i8]* [[DEST]] to i8*
 ; CHECK-NEXT:    [[SRC_I8:%.*]] = bitcast [16 x i8]* [[SRC]] to i8*
 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[CAPTURES:%.*]], label [[NOCAPTURES:%.*]]
 ; CHECK:       captures:
 ; CHECK-NEXT:    call void @accept_ptr(i8* [[DEST_I8]])
 ; CHECK-NEXT:    ret i32 10
 ; CHECK:       nocaptures:
-; CHECK-NEXT:    call void @accept_ptr(i8* [[SRC_I8]]) #[[ATTR3]]
+; CHECK-NEXT:    [[DEST1:%.*]] = bitcast [16 x i8]* [[DEST]] to i8*
+; CHECK-NEXT:    call void @accept_ptr(i8* [[DEST1]]) #[[ATTR3]]
 ; CHECK-NEXT:    [[LV_1:%.*]] = load i32*, i32** [[PTR:%.*]], align 8
 ; CHECK-NEXT:    [[LV_2:%.*]] = load i32, i32* [[LV_1]], align 4
-; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* [[DEST_I8]], i8* [[SRC_I8]], i64 16, i1 false)
 ; CHECK-NEXT:    ret i32 [[LV_2]]
 ;
   %dest = alloca [16 x i8]
   %src = alloca [16 x i8]
   %dest.i8 = bitcast [16 x i8]* %dest to i8*
   %src.i8 = bitcast [16 x i8]* %src to i8*
   br i1 %cond, label %captures, label %nocaptures
 

llvm/test/Transforms/MemCpyOpt/load-store-to-memcpy.ll

 }
 
 define void @form_memcpy_captures_after_load_store(i32** %ptr) {
 ; CHECK-LABEL: @form_memcpy_captures_after_load_store(
 ; CHECK-NEXT:    [[A:%.*]] = alloca [[T:%.*]], align 8
 ; CHECK-NEXT:    [[B:%.*]] = alloca [[T]], align 8
 ; CHECK-NEXT:    [[A_I8:%.*]] = bitcast %T* [[A]] to i8*
 ; CHECK-NEXT:    call void @use(i8* [[A_I8]])
-; CHECK-NEXT:    [[VAL:%.*]] = load [[T]], %T* [[A]], align 8
 ; CHECK-NEXT:    [[LV_1:%.*]] = load i32*, i32** [[PTR:%.*]], align 8
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast %T* [[B]] to i8*
+; CHECK-NEXT:    [[TMP2:%.*]] = bitcast %T* [[A]] to i8*
+; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 16 [[TMP1]], i8* align 8 [[TMP2]], i64 8, i1 false)
 ; CHECK-NEXT:    store i32 0, i32* [[LV_1]], align 4
-; CHECK-NEXT:    store [[T]] [[VAL]], %T* [[B]], align 16
-; CHECK-NEXT:    [[TMP1:%.*]] = bitcast %T* [[A]] to i8*
-; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[TMP1]], i8 0, i64 8, i1 false)
+; CHECK-NEXT:    [[TMP3:%.*]] = bitcast %T* [[A]] to i8*
+; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[TMP3]], i8 0, i64 8, i1 false)
 ; CHECK-NEXT:    [[B_I8:%.*]] = bitcast %T* [[B]] to i8*
 ; CHECK-NEXT:    call void @use(i8* [[B_I8]])
 ; CHECK-NEXT:    call void @use(i8* [[A_I8]])
 ; CHECK-NEXT:    ret void
 ;
   %a = alloca %T
   %b = alloca %T
   %a.i8 = bitcast %T* %a to i8*

 }
 
 define void @form_memcpy_captures_after_call(i32** %ptr) {
 ; CHECK-LABEL: @form_memcpy_captures_after_call(
 ; CHECK-NEXT:    [[A:%.*]] = alloca [[T:%.*]], align 8
 ; CHECK-NEXT:    [[B:%.*]] = alloca [[T]], align 8
 ; CHECK-NEXT:    [[A_I8:%.*]] = bitcast %T* [[A]] to i8*
 ; CHECK-NEXT:    call void @use(i8* [[A_I8]])
-; CHECK-NEXT:    [[VAL:%.*]] = load [[T]], %T* [[A]], align 8
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast %T* [[B]] to i8*
+; CHECK-NEXT:    [[TMP2:%.*]] = bitcast %T* [[A]] to i8*
+; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 16 [[TMP1]], i8* align 8 [[TMP2]], i64 8, i1 false)
 ; CHECK-NEXT:    call void @clobber()
-; CHECK-NEXT:    store [[T]] [[VAL]], %T* [[B]], align 16
-; CHECK-NEXT:    [[TMP1:%.*]] = bitcast %T* [[A]] to i8*
-; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[TMP1]], i8 0, i64 8, i1 false)
+; CHECK-NEXT:    [[TMP3:%.*]] = bitcast %T* [[A]] to i8*
+; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[TMP3]], i8 0, i64 8, i1 false)
 ; CHECK-NEXT:    [[B_I8:%.*]] = bitcast %T* [[B]] to i8*
 ; CHECK-NEXT:    call void @use(i8* [[B_I8]])
 ; CHECK-NEXT:    call void @use(i8* [[A_I8]])
 ; CHECK-NEXT:    ret void
 ;
   %a = alloca %T
   %b = alloca %T
   %a.i8 = bitcast %T* %a to i8*