Index: lib/Transforms/Scalar/DeadStoreElimination.cpp =================================================================== --- lib/Transforms/Scalar/DeadStoreElimination.cpp +++ lib/Transforms/Scalar/DeadStoreElimination.cpp @@ -40,6 +40,7 @@ #define DEBUG_TYPE "dse" +STATISTIC(NumRedundantStores, "Number of redundant stores deleted"); STATISTIC(NumFastStores, "Number of stores deleted"); STATISTIC(NumFastOther , "Number of other instrs removed"); @@ -76,6 +77,7 @@ } bool runOnBasicBlock(BasicBlock &BB); + bool MemoryIsNotModifiedBetween(LoadInst *LI, StoreInst *SI); bool HandleFree(CallInst *F); bool handleEndBlock(BasicBlock &BB); void RemoveAccessedObjects(const MemoryLocation &LoadedLoc, @@ -491,19 +493,14 @@ if (!hasMemoryWrite(Inst, TLI)) continue; - MemDepResult InstDep = MD->getDependency(Inst); - - // Ignore any store where we can't find a local dependence. - // FIXME: cross-block DSE would be fun. :) - if (!InstDep.isDef() && !InstDep.isClobber()) - continue; - // If we're storing the same value back to a pointer that we just // loaded from, then the store can be removed. if (StoreInst *SI = dyn_cast(Inst)) { - if (LoadInst *DepLoad = dyn_cast(InstDep.getInst())) { + if (LoadInst *DepLoad = dyn_cast(SI->getValueOperand())) { if (SI->getPointerOperand() == DepLoad->getPointerOperand() && - SI->getOperand(0) == DepLoad && isRemovable(SI)) { + isRemovable(SI) && + MemoryIsNotModifiedBetween(DepLoad, SI)) { + DEBUG(dbgs() << "DSE: Remove Store Of Load from same pointer:\n " << "LOAD: " << *DepLoad << "\n STORE: " << *SI << '\n'); @@ -517,13 +514,20 @@ BBI = BB.begin(); else if (BBI != BB.begin()) // Revisit this instruction if possible. --BBI; - ++NumFastStores; + ++NumRedundantStores; MadeChange = true; continue; } } } + MemDepResult InstDep = MD->getDependency(Inst); + + // Ignore any store where we can't find a local dependence. + // FIXME: cross-block DSE would be fun. :) + if (!InstDep.isDef() && !InstDep.isClobber()) + continue; + // Figure out what location is being stored to. MemoryLocation Loc = getLocForWrite(Inst, *AA); @@ -624,6 +628,50 @@ return MadeChange; } +/// Returns true if the memory which is accessed by the store instruction is not +/// modified between the load and the store instruction. +/// Precondition: The store instruction must be dominated by the load +/// instruction. +bool DSE::MemoryIsNotModifiedBetween(LoadInst *LI, StoreInst *SI) { + SmallVector WorkList; + SmallPtrSet Visited; + BasicBlock::iterator LoadBBI(LI); + ++LoadBBI; + BasicBlock::iterator StoreBBI(SI); + BasicBlock *LoadBB = LI->getParent(); + BasicBlock *StoreBB = SI->getParent(); + MemoryLocation StoreLoc = MemoryLocation::get(SI); + + // Start checking the store-block. + WorkList.push_back(StoreBB); + Visited.insert(StoreBB); + + // Check all blocks going backward until we reach the load-block. + while (!WorkList.empty()) { + BasicBlock *B = WorkList.pop_back_val(); + auto BI = (B == LoadBB ? LoadBBI : B->begin()); + auto BE = (B == StoreBB ? StoreBBI : B->end()); + for (; BI != BE; ++BI) { + Instruction *I = BI; + if (I->mayWriteToMemory()) { + auto Res = AA->getModRefInfo(I, StoreLoc); + if (Res != MRI_NoModRef) + return false; + } + } + if (B != LoadBB) { + assert(B != &LoadBB->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) + continue; + WorkList.push_back(*PredI); + } + } + } + return true; +} + /// Find all blocks that will unconditionally lead to the block BB and append /// them to F. static void FindUnconditionalPreds(SmallVectorImpl &Blocks, Index: test/Transforms/DeadStoreElimination/simple.ll =================================================================== --- test/Transforms/DeadStoreElimination/simple.ll +++ test/Transforms/DeadStoreElimination/simple.ll @@ -350,3 +350,98 @@ store i8 %tmp, i8* %p.4, align 1 ret i8* %q } + +; Remove redudant store if loaded value is in another block. +; CHECK-LABEL: @test26( +; CHECK-NOT: store +; CHECK: ret +define i32 @test26(i1 %c, i32* %p) { +entry: + %v = load i32, i32* %p, align 4 + br i1 %c, label %bb1, label %bb2 +bb1: + br label %bb3 +bb2: + store i32 %v, i32* %p, align 4 + br label %bb3 +bb3: + ret i32 0 +} + +; Remove redudant store if loaded value is in another block. +; CHECK-LABEL: @test27( +; CHECK-NOT: store +; CHECK: ret +define i32 @test27(i1 %c, i32* %p) { +entry: + %v = load i32, i32* %p, align 4 + br i1 %c, label %bb1, label %bb2 +bb1: + br label %bb3 +bb2: + br label %bb3 +bb3: + store i32 %v, i32* %p, align 4 + ret i32 0 +} + +; Don't remove redudant store because of may-aliased store. +; CHECK-LABEL: @test28( +; CHECK: bb3: +; CHECK-NEXT: store i32 %v +define i32 @test28(i1 %c, i32* %p, i32* %p2, i32 %i) { +entry: + %v = load i32, i32* %p, align 4 + + ; Might overwrite value at %p + store i32 %i, i32* %p2, align 4 + br i1 %c, label %bb1, label %bb2 +bb1: + br label %bb3 +bb2: + br label %bb3 +bb3: + store i32 %v, i32* %p, align 4 + ret i32 0 +} + +; Don't remove redudant store because of may-aliased store. +; CHECK-LABEL: @test29( +; CHECK: bb3: +; CHECK-NEXT: store i32 %v +define i32 @test29(i1 %c, i32* %p, i32* %p2, i32 %i) { +entry: + %v = load i32, i32* %p, align 4 + br i1 %c, label %bb1, label %bb2 +bb1: + br label %bb3 +bb2: + ; Might overwrite value at %p + store i32 %i, i32* %p2, align 4 + br label %bb3 +bb3: + store i32 %v, i32* %p, align 4 + ret i32 0 +} + +declare void @unknown_func() + +; Don't remove redudant store because of unknown call. +; CHECK-LABEL: @test30( +; CHECK: bb3: +; CHECK-NEXT: store i32 %v +define i32 @test30(i1 %c, i32* %p, i32 %i) { +entry: + %v = load i32, i32* %p, align 4 + br i1 %c, label %bb1, label %bb2 +bb1: + br label %bb3 +bb2: + ; Might overwrite value at %p + call void @unknown_func() + br label %bb3 +bb3: + store i32 %v, i32* %p, align 4 + ret i32 0 +} +