diff --git a/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp b/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp --- a/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp +++ b/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp @@ -25,6 +25,7 @@ #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" @@ -92,6 +93,7 @@ //===----------------------------------------------------------------------===// using OverlapIntervalsTy = std::map; using InstOverlapIntervalsTy = DenseMap; +using BackedgesTy = SmallSet, 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 @@ -597,8 +599,33 @@ /// instruction. static bool memoryIsNotModifiedBetween(Instruction *FirstI, Instruction *SecondI, - AliasAnalysis *AA) { - SmallVector 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; + SmallVector WorkList; SmallPtrSet Visited; BasicBlock::iterator FirstBBI(FirstI); ++FirstBBI; @@ -607,20 +634,22 @@ 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; @@ -631,17 +660,25 @@ } 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); } } } @@ -1044,7 +1081,8 @@ const TargetLibraryInfo *TLI, InstOverlapIntervalsTy &IOL, OrderedBasicBlock &OBB, - MapVector &ThrowableInst) { + MapVector &ThrowableInst, + BackedgesTy &Backedges) { // Must be a store instruction. StoreInst *SI = dyn_cast(Inst); if (!SI) @@ -1054,7 +1092,8 @@ // then the store can be removed. if (LoadInst *DepLoad = dyn_cast(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: " @@ -1073,7 +1112,7 @@ dyn_cast(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'); @@ -1088,7 +1127,8 @@ 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; @@ -1122,7 +1162,7 @@ // eliminateNoopStore will update in iterator, if necessary. if (eliminateNoopStore(Inst, BBI, AA, MD, DL, TLI, IOL, OBB, - ThrowableInst)) { + ThrowableInst, Backedges)) { MadeChange = true; continue; } @@ -1240,7 +1280,7 @@ Later && isa(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 @@ -1339,12 +1379,18 @@ static bool eliminateDeadStores(Function &F, AliasAnalysis *AA, MemoryDependenceResults *MD, DominatorTree *DT, const TargetLibraryInfo *TLI) { + SmallVector, 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; }