Conservative fix for DSE across loops

[DefCon42]

Summary

This is essentially just https://reviews.llvm.org/D68006 with a few fixes for the comments.

To address the last comment about the CFG visiting: This simply prevents DSE from analyzing through back-edges (and instead assuming memory modification) because it had the potential to break certain types of loops. I heard somewhere that there will be a proper fix for this in @fhahn 's MemorySSA-backed DSE, so this is essentially a band-aid I suppose.

Don't know who to tag for this, sorry.

[DefCon42]

Looks like @fhahn posted a proper fix for this almost at the exact same time that I posted this one. Heh.

[fhahn]

In D73758#1850971, @DefCon42 wrote:

Looks like @fhahn posted a proper fix for this almost at the exact same time that I posted this one. Heh.

If the MemorySSA-backed DSE lands, I expect it to take at least a few months until it will be mature enough. IMO we should fix the issue in the current DSE regardless of any MemorySSA based work.

[DefCon42]

Looks like I missed the fact that that *was* for MemorySSA-backed DSE. oops :^)
Guess I'm reopening this, but again this is essentially a band-aid.

[asbirlea]

Does @test31 in test/Transforms/DeadStoreElimination/simple.ll pass with this patch?

Can you add the test from PR44704?

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

 #include "llvm/ADT/StringRef.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/CaptureTracking.h"
+#include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/MemoryDependenceAnalysis.h"

 //===----------------------------------------------------------------------===//
 using OverlapIntervalsTy = std::map<int64_t, int64_t>;
 using InstOverlapIntervalsTy = DenseMap<Instruction *, OverlapIntervalsTy>;
+using BackedgesTy = SmallSet<std::pair<const BasicBlock *, const BasicBlock *>, 8>;
 
 /// Delete this instruction.  Before we do, go through and zero out all the
 /// operands of this instruction.  If any of them become dead, delete them and

 /// instruction.
 static bool memoryIsNotModifiedBetween(Instruction *FirstI,
                                        Instruction *SecondI,
-                                       AliasAnalysis *AA) {
-  SmallVector<BasicBlock *, 16> WorkList;
+                                       AliasAnalysis *AA,
+                                       BackedgesTy &Backedges) {
+  // Do a backwards scan through the CFG from SecondI to FirstI. Look for
+  // instructions which can modify the memory location accessed by SecondI.
+  //
+  // While scanning through the CFG keep track whether we visited the block
+  // through a back edge. If we visited through a back edge it means that we are
+  // analyzing instructions across different iterations of the loop. We
+  // need to be more conservative in this case. Consider this example:
+  //   a = calloc(n+1)
+  //   for (int i = 0; i < n; i++) {
+  //     store 1, a[i+1] // (1)
+  //     store 0, a[i]   // (2)
+  //   }
+  // Scanning from store (2) to the calloc we'll visit the loop basic block
+  // through the backedge. If we ask BasicAA whether store (1) aliases with
+  // store (2) it would report NoAlias since the two addresses are distinct
+  // offsets from the same base (a[i] and a[i+1]). It's correct within one
+  // iteration of the loop, but across different iterations they alias.
+  //
+  // If we visit a block through a backedge we treat any may-write-to-memory
+  // instruction as a clobber.
+  //
+  // We use PointerIntPair to track the BasicBlock to visit along with the fact
+  // whether we visited it through a back edge or not.
+  using Block = PointerIntPair<BasicBlock *, 1, bool>;
+  SmallVector<Block, 16> WorkList;
   SmallPtrSet<BasicBlock *, 8> Visited;
   BasicBlock::iterator FirstBBI(FirstI);
   ++FirstBBI;

   BasicBlock *SecondBB = SecondI->getParent();
   MemoryLocation MemLoc = MemoryLocation::get(SecondI);
 
-  // Start checking the store-block.
-  WorkList.push_back(SecondBB);
+  // Start from the block that has the store instruction.
+  WorkList.emplace_back(SecondBB, /*VisitedThroughBackedge=*/false);
   bool isFirstBlock = true;
 
-  // Check all blocks going backward until we reach the load-block.
+  // Check all blocks going backward until we reach the block that has the load instruction.
   while (!WorkList.empty()) {
-    BasicBlock *B = WorkList.pop_back_val();
+    Block CurBlock = WorkList.pop_back_val();
+    BasicBlock *B = CurBlock.getPointer();
+    bool VisitedThroughBackedge = CurBlock.getInt();
 
-    // Ignore instructions before LI if this is the FirstBB.
+    // Ignore instructions before the load instruction if this is the FirstBB.
     BasicBlock::iterator BI = (B == FirstBB ? FirstBBI : B->begin());
 
     BasicBlock::iterator EI;
     if (isFirstBlock) {
-      // Ignore instructions after SI if this is the first visit of SecondBB.
+      // Ignore instructions after the store instruction if this is the first visit of SecondBB.
       assert(B == SecondBB && "first block is not the store block");
       EI = SecondBBI;
       isFirstBlock = false;

     }
     for (; BI != EI; ++BI) {
       Instruction *I = &*BI;
-      if (I->mayWriteToMemory() && I != SecondI)
+      if (I->mayWriteToMemory() && I != SecondI) {
+        if (VisitedThroughBackedge)
+          // If we visited this block through a backedge we are analyzing
+          // instructions across different iterations. Be conservative and
+          // treat any may-write-to-memory as clobbering.
+          return false;
         if (isModSet(AA->getModRefInfo(I, MemLoc)))
           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) {
-        if (!Visited.insert(*PredI).second)
+      for (auto PredIterator = pred_begin(B), PE = pred_end(B); PredIterator != PE; ++PredIterator) {
+        BasicBlock *PredBB = *PredIterator;
+        if (!Visited.insert(PredBB).second)
           continue;
-        WorkList.push_back(*PredI);
+        bool IsBackedge = Backedges.count(std::make_pair(B, PredBB));
+        WorkList.emplace_back(PredBB, VisitedThroughBackedge | IsBackedge);
       }
     }
   }

                                const TargetLibraryInfo *TLI,
                                InstOverlapIntervalsTy &IOL,
                                OrderedBasicBlock &OBB,
-                               MapVector<Instruction *, bool> &ThrowableInst) {
+                               MapVector<Instruction *, bool> &ThrowableInst,
+                               BackedgesTy &Backedges) {
   // Must be a store instruction.
   StoreInst *SI = dyn_cast<StoreInst>(Inst);
   if (!SI)

   // 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)) {
+        isRemovable(SI) &&
+        memoryIsNotModifiedBetween(DepLoad, SI, AA, Backedges)) {
 
       LLVM_DEBUG(
           dbgs() << "DSE: Remove Store Of Load from same pointer:\n  LOAD: "

         dyn_cast<Instruction>(GetUnderlyingObject(SI->getPointerOperand(), DL));
 
     if (UnderlyingPointer && isCallocLikeFn(UnderlyingPointer, TLI) &&
-        memoryIsNotModifiedBetween(UnderlyingPointer, SI, AA)) {
+        memoryIsNotModifiedBetween(UnderlyingPointer, SI, AA, Backedges)) {
       LLVM_DEBUG(
           dbgs() << "DSE: Remove null store to the calloc'ed object:\n  DEAD: "
                  << *Inst << "\n  OBJECT: " << *UnderlyingPointer << '\n');

 
 static bool eliminateDeadStores(BasicBlock &BB, AliasAnalysis *AA,
                                 MemoryDependenceResults *MD, DominatorTree *DT,
-                                const TargetLibraryInfo *TLI) {
+                                const TargetLibraryInfo *TLI,
+                                BackedgesTy &Backedges) {
   const DataLayout &DL = BB.getModule()->getDataLayout();
   bool MadeChange = false;
 

 
     // eliminateNoopStore will update in iterator, if necessary.
     if (eliminateNoopStore(Inst, BBI, AA, MD, DL, TLI, IOL, OBB,
-                           ThrowableInst)) {
+                           ThrowableInst, Backedges)) {
       MadeChange = true;
       continue;
     }

               Later && isa<ConstantInt>(Later->getValueOperand()) &&
               DL.typeSizeEqualsStoreSize(
                   Later->getValueOperand()->getType()) &&
-              memoryIsNotModifiedBetween(Earlier, Later, AA)) {
+              memoryIsNotModifiedBetween(Earlier, Later, AA, Backedges)) {
             // If the store we find is:
             //   a) partially overwritten by the store to 'Loc'
             //   b) the later store is fully contained in the earlier one and

 static bool eliminateDeadStores(Function &F, AliasAnalysis *AA,
                                 MemoryDependenceResults *MD, DominatorTree *DT,
                                 const TargetLibraryInfo *TLI) {
+  SmallVector<std::pair<const BasicBlock *, const BasicBlock *>, 8> BackedgeVector;
+  llvm::FindFunctionBackedges(F, BackedgeVector);
+  BackedgesTy BackEdges;
+  for (auto BE : BackedgeVector)
+    BackEdges.insert(BE);
+
   bool MadeChange = false;
   for (BasicBlock &BB : F)
     // Only check non-dead blocks.  Dead blocks may have strange pointer
     // cycles that will confuse alias analysis.
     if (DT->isReachableFromEntry(&BB))
-      MadeChange |= eliminateDeadStores(BB, AA, MD, DT, TLI);
+      MadeChange |= eliminateDeadStores(BB, AA, MD, DT, TLI, BackEdges);
 
   return MadeChange;
 }