Index: llvm/trunk/lib/Transforms/Scalar/DeadStoreElimination.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/DeadStoreElimination.cpp +++ llvm/trunk/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, @@ -495,19 +497,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'); @@ -521,13 +518,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); @@ -627,6 +631,63 @@ 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); + bool isFirstBlock = true; + + // Check all blocks going backward until we reach the load-block. + while (!WorkList.empty()) { + BasicBlock *B = WorkList.pop_back_val(); + + // Ignore instructions before LI if this is the LoadBB. + BasicBlock::iterator BI = (B == LoadBB ? LoadBBI : B->begin()); + + BasicBlock::iterator EI; + if (isFirstBlock) { + // Ignore instructions after SI if this is the first visit of StoreBB. + assert(B == StoreBB && "first block is not the store block"); + EI = StoreBBI; + isFirstBlock = false; + } else { + // It's not StoreBB or (in case of a loop) the second visit of StoreBB. + // In this case we also have to look at instructions after SI. + EI = B->end(); + } + for (; BI != EI; ++BI) { + Instruction *I = BI; + if (I->mayWriteToMemory() && I != SI) { + 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: llvm/trunk/test/Transforms/DeadStoreElimination/simple.ll =================================================================== --- llvm/trunk/test/Transforms/DeadStoreElimination/simple.ll +++ llvm/trunk/test/Transforms/DeadStoreElimination/simple.ll @@ -350,3 +350,150 @@ store i8 %tmp, i8* %p.4, align 1 ret i8* %q } + +; Remove redundant 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 redundant 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 redundant 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 redundant 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 redundant 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 +} + +; Remove redundant store if loaded value is in another block inside a loop. +; CHECK-LABEL: @test31( +; CHECK-NOT: store +; CHECK: ret +define i32 @test31(i1 %c, i32* %p, i32 %i) { +entry: + %v = load i32, i32* %p, align 4 + br label %bb1 +bb1: + store i32 %v, i32* %p, align 4 + br i1 undef, label %bb1, label %bb2 +bb2: + ret i32 0 +} + +; Don't remove redundant store in a loop with a may-alias store. +; CHECK-LABEL: @test32( +; CHECK: bb1: +; CHECK-NEXT: store i32 %v +; CHECK-NEXT: call void @unknown_func +define i32 @test32(i1 %c, i32* %p, i32 %i) { +entry: + %v = load i32, i32* %p, align 4 + br label %bb1 +bb1: + store i32 %v, i32* %p, align 4 + ; Might read and overwrite value at %p + call void @unknown_func() + br i1 undef, label %bb1, label %bb2 +bb2: + ret i32 0 +} + +; Remove redundant store, which is in the lame loop as the load. +; CHECK-LABEL: @test33( +; CHECK-NOT: store +; CHECK: ret +define i32 @test33(i1 %c, i32* %p, i32 %i) { +entry: + br label %bb1 +bb1: + %v = load i32, i32* %p, align 4 + br label %bb2 +bb2: + store i32 %v, i32* %p, align 4 + ; Might read and overwrite value at %p, but doesn't matter. + call void @unknown_func() + br i1 undef, label %bb1, label %bb3 +bb3: + ret i32 0 +} +