[DSE] Use correct memory location for read clobber check

[nikic]

Summary

MSSA DSE starts at a killing store, finds an earlier store and then checks that the earlier store is not read along any paths (without being killed first). However, it uses the memory location of the killing store for that, not the earlier store that we're attempting to eliminate.

This has a number of problems:

• Mismatches between what BasicAA considers aliasing and what DSE considers an overwrite (even though both are correct in isolation) can result in miscompiles. This is PR48279, which D92045 tries to fix in a different way. The problem is that we're using a location from a store that is potentially not executed and thus may be UB, in which case analysis results can be arbitrary.
• Metadata on the killing store may be used to determine aliasing, but there is no guarantee that the metadata is valid, as the specific killing store may not be executed. Using the metadata on the earlier store is valid (it is the store we're removing, so on any execution where its removal may be observed, it must be executed).
• The location is imprecise. For full overwrites the killing store will always have a location that is larger or equal than the earlier access location, so it's beneficial to use the earlier access location. This is not the case for partial overwrites, in which case either location might be smaller. There is some room for improvement here.

Using the earlier access location means that we can no longer cache which accesses are read for a given killing store, as we may be querying different locations. However, it turns out that simply dropping the cache has no notable impact on compile-time, so that seems fine: https://llvm-compile-time-tracker.com/compare.php?from=3d56644f18eefe30e353e7fae3cb5e5daf0a0ffb&to=9bdb4e5b085bc3d054c30f6256c344a14748a715&stat=instructions

[fhahn]

LGTM, thanks!

Using the earlier access location means that we can no longer cache which accesses are read for a given killing store, as we may be querying different locations. However, it turns out that simply dropping the cache has no notable impact on compile-time.

Yes that should be fine. There were some major changes after the caching was added which meant that now the 'check-for-reads' loop is not as critical to compile time as before. The cache mostly helped to explore further before running out of budget. So there are some cases we will miss without caching, but from the stats I collected for this patch, it seems there are only minor negative swings and it is best to get this fix in and then potentially tweak it further.

[fhahn]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1944

Can this just be MemoryLocation CurrentLoc? We should skip the case when it would be None and it should always be != None before after the loop.

[nikic]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1944

This uses Optional<MemoryLocation> because getLocForWriteEx() returns it that way. Should I copy it into a separate non-Optional variable after the check that it is not None?

[fhahn]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1944

I'd put the result of getLocForWriteEx into a new temprary and move the content to CurrentLoc after the check. Or have something like

if (auto Loc = getLocForWriteEx(....)) {
  CurrentLoc = *Loc;
} else {
  StepAgain = true;
  ....
  continue;
}

[nikic]

Drop Optional<> wrapper.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1944

I liked your second suggestion. Does the new version look fine?

[fhahn]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1944

that looks good, thanks!

[tambre]

llvm/test/Transforms/DeadStoreElimination/MSSA/out-of-bounds-stores.ll

33

Should the "FIXME." have been removed?

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

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;
 
-  struct CheckCache {
-    SmallPtrSet<MemoryAccess *, 16> KnownNoReads;
-    SmallPtrSet<MemoryAccess *, 16> KnownReads;
-
-    bool isKnownNoRead(MemoryAccess *A) const {
-      return KnownNoReads.find(A) != KnownNoReads.end();
-    }
-    bool isKnownRead(MemoryAccess *A) const {
-      return KnownReads.find(A) != KnownReads.end();
-    }
-  };
-
   DSEState(Function &F, AliasAnalysis &AA, MemorySSA &MSSA, DominatorTree &DT,
            PostDominatorTree &PDT, const TargetLibraryInfo &TLI)
       : F(F), AA(AA), BatchAA(AA), MSSA(MSSA), DT(DT), PDT(PDT), TLI(TLI),
         DL(F.getParent()->getDataLayout()) {}
 
   static DSEState get(Function &F, AliasAnalysis &AA, MemorySSA &MSSA,
                       DominatorTree &DT, PostDominatorTree &PDT,
                       const TargetLibraryInfo &TLI) {
struct DSEState {
   // 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 *StartAccess,
                   const MemoryLocation &DefLoc, const Value *DefUO,
-                  CheckCache &Cache, unsigned &ScanLimit,
-                  unsigned &WalkerStepLimit, bool IsMemTerm,
-                  unsigned &PartialLimit) {
+                  unsigned &ScanLimit, unsigned &WalkerStepLimit,
+                  bool IsMemTerm, unsigned &PartialLimit) {
     if (ScanLimit == 0 || WalkerStepLimit == 0) {
       LLVM_DEBUG(dbgs() << "\n    ...  hit scan limit\n");
       return None;
     }
 
     MemoryAccess *Current = StartAccess;
     Instruction *KillingI = KillingDef->getMemoryInst();
     bool StepAgain;
     LLVM_DEBUG(dbgs() << "  trying to get dominating access\n");
 
     // Find the next clobbering Mod access for DefLoc, starting at StartAccess.
+    Optional<MemoryLocation> CurrentLoc;
     do {
       StepAgain = false;
       LLVM_DEBUG({
         dbgs() << "   visiting " << *Current;
         if (!MSSA.isLiveOnEntryDef(Current) && isa<MemoryUseOrDef>(Current))
           dbgs() << " (" << *cast<MemoryUseOrDef>(Current)->getMemoryInst()
                  << ")";
         dbgs() << "\n";
do {
         LLVM_DEBUG(dbgs() << "  ... skip, barrier\n");
         return None;
       }
 
       // If Current is known to be on path that reads DefLoc or is a read
       // clobber, bail out, as the path is not profitable. We skip this check
       // for intrinsic calls, because the code knows how to handle memcpy
       // intrinsics.
-      if (!isa<IntrinsicInst>(CurrentI) &&
-          (Cache.KnownReads.contains(Current) ||
-           isReadClobber(DefLoc, CurrentI))) {
-        Cache.KnownReads.insert(Current);
+      if (!isa<IntrinsicInst>(CurrentI) && isReadClobber(DefLoc, CurrentI))
         return None;
-      }
 
       // Quick check if there are direct uses that are read-clobbers.
       if (any_of(Current->uses(), [this, &DefLoc, StartAccess](Use &U) {
             if (auto *UseOrDef = dyn_cast<MemoryUseOrDef>(U.getUser()))
               return !MSSA.dominates(StartAccess, UseOrDef) &&
                      isReadClobber(DefLoc, UseOrDef->getMemoryInst());
             return false;
           })) {
-        Cache.KnownReads.insert(Current);
         LLVM_DEBUG(dbgs() << "   ...  found a read clobber\n");
         return None;
       }
 
       // If Current cannot be analyzed or is not removable, check the next
       // candidate.
       if (!hasAnalyzableMemoryWrite(CurrentI, TLI) || !isRemovable(CurrentI)) {
         StepAgain = true;
         Current = CurrentDef->getDefiningAccess();
         continue;
       }
 
       // If Current does not have an analyzable write location, skip it
-      auto CurrentLoc = getLocForWriteEx(CurrentI);
+      CurrentLoc = getLocForWriteEx(CurrentI);
       if (!CurrentLoc) {
         StepAgain = true;
         Current = CurrentDef->getDefiningAccess();
         continue;
       }
 
-      if (IsMemTerm) {
-        // If the killing def is a memory terminator (e.g. lifetime.end), check
-        // the next candidate if the current Current does not write the same
-        // underlying object as the terminator.
-        if (!isMemTerminator(*CurrentLoc, CurrentI, KillingI)) {
-          StepAgain = true;
-          Current = CurrentDef->getDefiningAccess();
-        }
-        continue;
-      } else {
-        // AliasAnalysis does not account for loops. Limit elimination to
-        // candidates for which we can guarantee they always store to the same
-        // memory location and not multiple locations in a loop.
-        if (Current->getBlock() != KillingDef->getBlock() &&
-            !IsGuaranteedLoopInvariant(const_cast<Value *>(CurrentLoc->Ptr))) {
-          StepAgain = true;
-          Current = CurrentDef->getDefiningAccess();
-          WalkerStepLimit -= 1;
-          continue;
-        }
 
+      if (IsMemTerm) {
+        // If the killing def is a memory terminator (e.g. lifetime.end), check
+        // the next candidate if the current Current does not write the same
+        // underlying object as the terminator.
+        if (!isMemTerminator(*CurrentLoc, CurrentI, KillingI)) {
+          StepAgain = true;
+          Current = CurrentDef->getDefiningAccess();
+        }
+        continue;
+      } else {
         int64_t InstWriteOffset, DepWriteOffset;
         auto OR = isOverwrite(KillingI, CurrentI, DefLoc, *CurrentLoc, DL, TLI,
                               DepWriteOffset, InstWriteOffset, BatchAA, &F);
         // If Current does not write to the same object as KillingDef, check
         // the next candidate.
         if (OR == OW_Unknown) {
           StepAgain = true;
           Current = CurrentDef->getDefiningAccess();
for (unsigned I = 0; I < WorkList.size(); I++) {
       LLVM_DEBUG(dbgs() << "   " << *UseAccess);
       // Bail out if the number of accesses to check exceeds the scan limit.
       if (ScanLimit < (WorkList.size() - I)) {
         LLVM_DEBUG(dbgs() << "\n    ...  hit scan limit\n");
         return None;
       }
       --ScanLimit;
       NumDomMemDefChecks++;
-
-      // Check if we already visited this access.
-      if (Cache.isKnownNoRead(UseAccess)) {
-        LLVM_DEBUG(dbgs() << " ... skip, discovered that " << *UseAccess
-                          << " is safe earlier.\n");
-        continue;
-      }
-      if (Cache.isKnownRead(UseAccess)) {
-        LLVM_DEBUG(dbgs() << " ... bail out, discovered that " << *UseAccess
-                          << " has a read-clobber earlier.\n");
-        return None;
-      }
       KnownNoReads.insert(UseAccess);
 
       if (isa<MemoryPhi>(UseAccess)) {
         if (any_of(KillingDefs, [this, UseAccess](Instruction *KI) {
               return DT.properlyDominates(KI->getParent(),
                                           UseAccess->getBlock());
             })) {
           LLVM_DEBUG(dbgs() << " ... skipping, dominated by killing block\n");
for (unsigned I = 0; I < WorkList.size(); I++) {
             return DT.dominates(KI, UseInst);
           })) {
         LLVM_DEBUG(dbgs() << " ... skipping, dominated by killing def\n");
         continue;
       }
 
       // A memory terminator kills all preceeding MemoryDefs and all succeeding
       // MemoryAccesses. We do not have to check it's users.
-      if (isMemTerminator(DefLoc, KillingI, UseInst)) {
+      if (isMemTerminator(*CurrentLoc, EarlierMemInst, UseInst)) {
         LLVM_DEBUG(
             dbgs()
             << " ... skipping, memterminator invalidates following accesses\n");
         continue;
       }
 
       if (isNoopIntrinsic(cast<MemoryUseOrDef>(UseAccess)->getMemoryInst())) {
         LLVM_DEBUG(dbgs() << "    ... adding uses of intrinsic\n");
         PushMemUses(UseAccess);
         continue;
       }
 
       if (UseInst->mayThrow() && !isInvisibleToCallerBeforeRet(DefUO)) {
         LLVM_DEBUG(dbgs() << "  ... found throwing instruction\n");
-        Cache.KnownReads.insert(UseAccess);
-        Cache.KnownReads.insert(StartAccess);
-        Cache.KnownReads.insert(EarlierAccess);
         return None;
       }
 
       // Uses which may read the original MemoryDef mean we cannot eliminate the
       // original MD. Stop walk.
-      if (isReadClobber(DefLoc, UseInst)) {
+      if (isReadClobber(*CurrentLoc, UseInst)) {
         LLVM_DEBUG(dbgs() << "    ... found read clobber\n");
-        Cache.KnownReads.insert(UseAccess);
-        Cache.KnownReads.insert(StartAccess);
-        Cache.KnownReads.insert(EarlierAccess);
         return None;
       }
 
       // For the KillingDef and EarlierAccess we only have to check if it reads
       // the memory location.
       // TODO: It would probably be better to check for self-reads before
       // calling the function.
       if (KillingDef == UseAccess || EarlierAccess == UseAccess) {
         LLVM_DEBUG(dbgs() << "    ... skipping killing def/dom access\n");
         continue;
       }
 
       // Check all uses for MemoryDefs, except for defs completely overwriting
       // the original location. Otherwise we have to check uses of *all*
       // MemoryDefs we discover, including non-aliasing ones. Otherwise we might
       // miss cases like the following
       //   1 = Def(LoE) ; <----- EarlierDef stores [0,1]
       //   2 = Def(1)   ; (2, 1) = NoAlias,   stores [2,3]
       //   Use(2)       ; MayAlias 2 *and* 1, loads [0, 3].
       //                  (The Use points to the *first* Def it may alias)
       //   3 = Def(1)   ; <---- Current  (3, 2) = NoAlias, (3,1) = MayAlias,
       //                  stores [0,1]
       if (MemoryDef *UseDef = dyn_cast<MemoryDef>(UseAccess)) {
-        if (isCompleteOverwrite(DefLoc, KillingI, UseInst)) {
+        if (isCompleteOverwrite(*CurrentLoc, EarlierMemInst, UseInst)) {
           if (!isInvisibleToCallerAfterRet(DefUO) &&
               UseAccess != EarlierAccess) {
             BasicBlock *MaybeKillingBlock = UseInst->getParent();
             if (PostOrderNumbers.find(MaybeKillingBlock)->second <
                 PostOrderNumbers.find(EarlierAccess->getBlock())->second) {
 
               LLVM_DEBUG(dbgs()
                          << "    ... found killing def " << *UseInst << "\n");
if (!isInvisibleToCallerAfterRet(DefUO)) {
         NumCFGSuccess++;
         return {EarlierAccess};
       }
       return None;
     }
 
     // No aliasing MemoryUses of EarlierAccess found, EarlierAccess is
     // potentially dead.
-    Cache.KnownNoReads.insert(KnownNoReads.begin(), KnownNoReads.end());
     return {EarlierAccess};
   }
 
   // Delete dead memory defs
   void deleteDeadInstruction(Instruction *SI) {
     MemorySSAUpdater Updater(&MSSA);
     SmallVector<Instruction *, 32> NowDeadInsts;
     NowDeadInsts.push_back(SI);
for (unsigned I = 0; I < State.MemDefs.size(); I++) {
     // Worklist of MemoryAccesses that may be killed by KillingDef.
     SetVector<MemoryAccess *> ToCheck;
 
     if (SILocUnd)
       ToCheck.insert(KillingDef->getDefiningAccess());
 
     bool Shortend = false;
     bool IsMemTerm = State.isMemTerminatorInst(SI);
-    DSEState::CheckCache Cache;
     // Check if MemoryAccesses in the worklist are killed by KillingDef.
     for (unsigned I = 0; I < ToCheck.size(); I++) {
       Current = ToCheck[I];
       if (State.SkipStores.count(Current))
         continue;
 
       Optional<MemoryAccess *> Next = State.getDomMemoryDef(
-          KillingDef, Current, SILoc, SILocUnd, Cache, ScanLimit,
-          WalkerStepLimit, IsMemTerm, PartialLimit);
+          KillingDef, Current, SILoc, SILocUnd, ScanLimit, WalkerStepLimit,
+          IsMemTerm, PartialLimit);
 
       if (!Next) {
         LLVM_DEBUG(dbgs() << "  finished walk\n");
         continue;
       }
 
       MemoryAccess *EarlierAccess = *Next;
       LLVM_DEBUG(dbgs() << " Checking if we can kill " << *EarlierAccess);

llvm/test/Transforms/DeadStoreElimination/MSSA/multiblock-memintrinsics.ll

bb2:
   %arrayidx1 = getelementptr inbounds i32, i32* %P, i64 1
   store i32 1, i32* %arrayidx1, align 4
   br label %bb3
 bb3:
   ret void
 }
 
 ; Post-dominating store.
+; TODO: The memset can be shortened.
 define void @accessible_after_return_2(i32* noalias %P, i1 %c) {
 ; CHECK-LABEL: @accessible_after_return_2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[ARRAYIDX0:%.*]] = getelementptr inbounds i32, i32* [[P:%.*]], i64 1
 ; CHECK-NEXT:    [[P3:%.*]] = bitcast i32* [[ARRAYIDX0]] to i8*
-; CHECK-NEXT:    [[TMP0:%.*]] = getelementptr inbounds i8, i8* [[P3]], i64 4
-; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[TMP0]], i8 0, i64 24, i1 false)
+; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[P3]], i8 0, i64 28, i1 false)
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1
 ; CHECK-NEXT:    store i32 1, i32* [[ARRAYIDX1]], align 4
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    [[ARRAYIDX2:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1
 ; CHECK-NEXT:    store i32 1, i32* [[ARRAYIDX2]], align 4

llvm/test/Transforms/DeadStoreElimination/MSSA/out-of-bounds-stores.ll

;
   call void @use(i32 %lv1)
   ret i32 0
 }
 
 ; Make sure that out-of-bound stores are not considered killing other stores to
 ; the same underlying object, if they are in different basic blocks. The
 ; out-of-bounds store may not be executed.
 ;
 ; Test case from PR48279. FIXME.
 define i32 @test_out_of_bounds_store_nonlocal(i1 %c) {
 ; CHECK-LABEL: @test_out_of_bounds_store_nonlocal(
 ; CHECK-NEXT:    [[D:%.*]] = alloca [1 x i32], align 4
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds [1 x i32], [1 x i32]* [[D]], i64 0, i64 0
+; CHECK-NEXT:    store i32 10, i32* [[ARRAYIDX]], align 4
 ; CHECK-NEXT:    br label [[FOR_INC:%.*]]
 ; CHECK:       for.inc:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[FOR_BODY_1:%.*]], label [[FOR_END:%.*]]
 ; CHECK:       for.body.1:
 ; CHECK-NEXT:    ret i32 1
 ; CHECK:       for.end:
 ; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds [1 x i32], [1 x i32]* [[D]], i64 0, i64 0
 ; CHECK-NEXT:    [[LV1:%.*]] = load i32, i32* [[ARRAYIDX1]], align 4

llvm/test/Transforms/DeadStoreElimination/MSSA/overlap.ll

bb1:
   br label %end
 
 end:
   store i8 0, i8* %ptr1
   call void @use(i64* %a)
   ret void
 }
 
-; TODO: The store to %a0 is dead, because only %a1 is read later.
+; The store to %a0 is dead, because only %a1 is read later.
 define void @test3(i1 %c) {
 ; CHECK-LABEL: @test3(
 ; CHECK-NEXT:    [[A:%.*]] = alloca [2 x i8], align 1
-; CHECK-NEXT:    [[A0:%.*]] = getelementptr [2 x i8], [2 x i8]* [[A]], i32 0, i32 0
 ; CHECK-NEXT:    [[A1:%.*]] = getelementptr [2 x i8], [2 x i8]* [[A]], i32 0, i32 1
-; CHECK-NEXT:    store i8 1, i8* [[A0]], align 1
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[IF:%.*]], label [[ELSE:%.*]]
 ; CHECK:       if:
 ; CHECK-NEXT:    store [2 x i8] zeroinitializer, [2 x i8]* [[A]], align 1
 ; CHECK-NEXT:    br label [[ELSE]]
 ; CHECK:       else:
 ; CHECK-NEXT:    [[TMP1:%.*]] = load i8, i8* [[A1]], align 1
 ; CHECK-NEXT:    ret void
 ;
else:
   ret void
 }
 
 ; Variation on the previous test case, where only the store to %a0 is dead,
 ; but not the one to %a1. This tests for a potential caching bug.
 define void @test4(i1 %c) {
 ; CHECK-LABEL: @test4(
 ; CHECK-NEXT:    [[A:%.*]] = alloca [2 x i8], align 1
-; CHECK-NEXT:    [[A0:%.*]] = getelementptr [2 x i8], [2 x i8]* [[A]], i32 0, i32 0
 ; CHECK-NEXT:    [[A1:%.*]] = getelementptr [2 x i8], [2 x i8]* [[A]], i32 0, i32 1
 ; CHECK-NEXT:    store i8 1, i8* [[A1]], align 1
-; CHECK-NEXT:    store i8 1, i8* [[A0]], align 1
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[IF:%.*]], label [[ELSE:%.*]]
 ; CHECK:       if:
 ; CHECK-NEXT:    store [2 x i8] zeroinitializer, [2 x i8]* [[A]], align 1
 ; CHECK-NEXT:    br label [[ELSE]]
 ; CHECK:       else:
 ; CHECK-NEXT:    [[TMP1:%.*]] = load i8, i8* [[A1]], align 1
 ; CHECK-NEXT:    ret void
 ;

llvm/test/Transforms/DeadStoreElimination/MSSA/scoped-noalias.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -scoped-noalias-aa -dse < %s | FileCheck %s
 
 ; Assume that %p1 != %p2 if and only if %c is true. In that case the noalias
 ; metadata is correct, but the first store cannot be eliminated, as it may be
 ; read-clobbered by the load.
-; TODO The store is incorrectly eliminated.
 define void @test(i1 %c, i8* %p1, i8* %p2) {
 ; CHECK-LABEL: @test(
+; CHECK-NEXT:    store i8 0, i8* [[P1:%.*]], align 1
 ; CHECK-NEXT:    [[TMP1:%.*]] = load i8, i8* [[P2:%.*]], align 1, !alias.scope !0
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[IF:%.*]], label [[ELSE:%.*]]
 ; CHECK:       if:
-; CHECK-NEXT:    store i8 1, i8* [[P1:%.*]], align 1, !noalias !0
+; CHECK-NEXT:    store i8 1, i8* [[P1]], align 1, !noalias !0
 ; CHECK-NEXT:    ret void
 ; CHECK:       else:
 ; CHECK-NEXT:    store i8 2, i8* [[P1]], align 1
 ; CHECK-NEXT:    ret void
 ;
   store i8 0, i8* %p1
   load i8, i8* %p2, !alias.scope !2
   br i1 %c, label %if, label %else