From f55c62cdb87a0d5bab5dc9a2aff770d6323f5831 Mon Sep 17 00:00:00 2001 From: Nick Lewycky Date: Tue, 10 Nov 2009 06:46:40 +0000 Subject: [PATCH] Reapply r86359, "Teach dead store elimination that certain intrinsics write to memory just like a store" with bug fixed (partial-overwrite.ll is the regression test). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@86667 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/DeadStoreElimination.cpp | 181 ++++++++++++++------- test/Transforms/DeadStoreElimination/lifetime.ll | 19 +++ .../DeadStoreElimination/memintrinsics.ll | 47 ++++++ .../DeadStoreElimination/partial-overwrite.ll | 14 ++ 4 files changed, 198 insertions(+), 63 deletions(-) create mode 100644 test/Transforms/DeadStoreElimination/lifetime.ll create mode 100644 test/Transforms/DeadStoreElimination/memintrinsics.ll create mode 100644 test/Transforms/DeadStoreElimination/partial-overwrite.ll diff --git a/lib/Transforms/Scalar/DeadStoreElimination.cpp b/lib/Transforms/Scalar/DeadStoreElimination.cpp index 90436f4066..a85cf7b28b 100644 --- a/lib/Transforms/Scalar/DeadStoreElimination.cpp +++ b/lib/Transforms/Scalar/DeadStoreElimination.cpp @@ -78,19 +78,84 @@ static RegisterPass X("dse", "Dead Store Elimination"); FunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); } -/// isValueAtLeastAsBigAs - Return true if V1 is greater than or equal to the -/// stored size of V2. This returns false if we don't know. +/// doesClobberMemory - Does this instruction clobber (write without reading) +/// some memory? +static bool doesClobberMemory(Instruction *I) { + if (isa(I)) + return true; + if (IntrinsicInst *II = dyn_cast(I)) { + switch (II->getIntrinsicID()) { + default: return false; + case Intrinsic::memset: case Intrinsic::memmove: case Intrinsic::memcpy: + case Intrinsic::lifetime_end: return true; + } + } + return false; +} + +/// isElidable - If the memory this instruction and the memory it writes to is +/// unused, may we delete this instrtction? +static bool isElidable(Instruction *I) { + assert(doesClobberMemory(I)); + if (IntrinsicInst *II = dyn_cast(I)) + return II->getIntrinsicID() != Intrinsic::lifetime_end; + if (StoreInst *SI = dyn_cast(I)) + return !SI->isVolatile(); + return true; +} + +/// getPointerOperand - Return the pointer that is being clobbered. +static Value *getPointerOperand(Instruction *I) { + assert(doesClobberMemory(I)); + if (StoreInst *SI = dyn_cast(I)) + return SI->getPointerOperand(); + if (MemIntrinsic *MI = dyn_cast(I)) + return MI->getOperand(1); + assert(cast(I)->getIntrinsicID() == Intrinsic::lifetime_end); + return cast(I)->getOperand(2); +} + +/// getStoreSize - Return the length in bytes of the write by the clobbering +/// instruction. If variable or unknown, returns -1. +static unsigned getStoreSize(Instruction *I, const TargetData *TD) { + assert(doesClobberMemory(I)); + if (StoreInst *SI = dyn_cast(I)) { + if (!TD) return -1u; + const PointerType *PTy = + cast(SI->getPointerOperand()->getType()); + return TD->getTypeStoreSize(PTy->getElementType()); + } + + Value *Len; + if (MemIntrinsic *MI = dyn_cast(I)) { + Len = MI->getLength(); + } else { + IntrinsicInst *II = cast(I); + assert(II->getIntrinsicID() == Intrinsic::lifetime_end); + Len = II->getOperand(0); + } + if (ConstantInt *LenCI = dyn_cast(Len)) + if (!LenCI->isAllOnesValue()) + return LenCI->getZExtValue(); + return -1u; +} + +/// isStoreAtLeastAsWideAs - Return true if the size of the store in I1 is +/// greater than or equal to the store in I2. This returns false if we don't +/// know. /// -static bool isValueAtLeastAsBigAs(Value *V1, Value *V2, const TargetData *TD) { - const Type *V1Ty = V1->getType(), *V2Ty = V2->getType(); +static bool isStoreAtLeastAsWideAs(Instruction *I1, Instruction *I2, + const TargetData *TD) { + const Type *I1Ty = getPointerOperand(I1)->getType(); + const Type *I2Ty = getPointerOperand(I2)->getType(); // Exactly the same type, must have exactly the same size. - if (V1Ty == V2Ty) return true; + if (I1Ty == I2Ty) return true; - // If we don't have target data, we don't know. - if (TD == 0) return false; + int I1Size = getStoreSize(I1, TD); + int I2Size = getStoreSize(I2, TD); - return TD->getTypeStoreSize(V1Ty) >= TD->getTypeStoreSize(V2Ty); + return I1Size != -1 && I2Size != -1 && I1Size >= I2Size; } bool DSE::runOnBasicBlock(BasicBlock &BB) { @@ -104,14 +169,9 @@ bool DSE::runOnBasicBlock(BasicBlock &BB) { Instruction *Inst = BBI++; // If we find a store or a free, get its memory dependence. - if (!isa(Inst) && !isFreeCall(Inst)) + if (!doesClobberMemory(Inst) && !isFreeCall(Inst)) continue; - // Don't molest volatile stores or do queries that will return "clobber". - if (StoreInst *SI = dyn_cast(Inst)) - if (SI->isVolatile()) - continue; - MemDepResult InstDep = MD.getDependency(Inst); // Ignore non-local stores. @@ -124,16 +184,16 @@ bool DSE::runOnBasicBlock(BasicBlock &BB) { continue; } - StoreInst *SI = cast(Inst); - // If not a definite must-alias dependency, ignore it. if (!InstDep.isDef()) continue; // If this is a store-store dependence, then the previous store is dead so // long as this store is at least as big as it. - if (StoreInst *DepStore = dyn_cast(InstDep.getInst())) - if (isValueAtLeastAsBigAs(SI->getOperand(0), DepStore->getOperand(0),TD)){ + if (doesClobberMemory(InstDep.getInst())) { + Instruction *DepStore = InstDep.getInst(); + if (isStoreAtLeastAsWideAs(Inst, DepStore, TD) && + isElidable(DepStore)) { // Delete the store and now-dead instructions that feed it. DeleteDeadInstruction(DepStore); NumFastStores++; @@ -146,37 +206,43 @@ bool DSE::runOnBasicBlock(BasicBlock &BB) { --BBI; continue; } + } + + if (!isElidable(Inst)) + continue; // If we're storing the same value back to a pointer that we just // loaded from, then the store can be removed. - if (LoadInst *DepLoad = dyn_cast(InstDep.getInst())) { - if (SI->getPointerOperand() == DepLoad->getPointerOperand() && - SI->getOperand(0) == DepLoad) { - // DeleteDeadInstruction can delete the current instruction. Save BBI - // in case we need it. - WeakVH NextInst(BBI); - - DeleteDeadInstruction(SI); - - if (NextInst == 0) // Next instruction deleted. - BBI = BB.begin(); - else if (BBI != BB.begin()) // Revisit this instruction if possible. - --BBI; - NumFastStores++; - MadeChange = true; - continue; + if (StoreInst *SI = dyn_cast(Inst)) { + if (LoadInst *DepLoad = dyn_cast(InstDep.getInst())) { + if (SI->getPointerOperand() == DepLoad->getPointerOperand() && + SI->getOperand(0) == DepLoad) { + // DeleteDeadInstruction can delete the current instruction. Save BBI + // in case we need it. + WeakVH NextInst(BBI); + + DeleteDeadInstruction(SI); + + if (NextInst == 0) // Next instruction deleted. + BBI = BB.begin(); + else if (BBI != BB.begin()) // Revisit this instruction if possible. + --BBI; + NumFastStores++; + MadeChange = true; + continue; + } } } // If this is a lifetime end marker, we can throw away the store. - if (IntrinsicInst* II = dyn_cast(InstDep.getInst())) { + if (IntrinsicInst *II = dyn_cast(InstDep.getInst())) { if (II->getIntrinsicID() == Intrinsic::lifetime_end) { // Delete the store and now-dead instructions that feed it. // DeleteDeadInstruction can delete the current instruction. Save BBI // in case we need it. WeakVH NextInst(BBI); - DeleteDeadInstruction(SI); + DeleteDeadInstruction(Inst); if (NextInst == 0) // Next instruction deleted. BBI = BB.begin(); @@ -202,11 +268,11 @@ bool DSE::runOnBasicBlock(BasicBlock &BB) { bool DSE::handleFreeWithNonTrivialDependency(Instruction *F, MemDepResult Dep) { AliasAnalysis &AA = getAnalysis(); - StoreInst *Dependency = dyn_cast_or_null(Dep.getInst()); - if (!Dependency || Dependency->isVolatile()) + Instruction *Dependency = Dep.getInst(); + if (!Dependency || !doesClobberMemory(Dependency) || !isElidable(Dependency)) return false; - Value *DepPointer = Dependency->getPointerOperand()->getUnderlyingObject(); + Value *DepPointer = getPointerOperand(Dependency)->getUnderlyingObject(); // Check for aliasing. if (AA.alias(F->getOperand(1), 1, DepPointer, 1) != @@ -251,39 +317,28 @@ bool DSE::handleEndBlock(BasicBlock &BB) { --BBI; // If we find a store whose pointer is dead. - if (StoreInst* S = dyn_cast(BBI)) { - if (!S->isVolatile()) { + if (doesClobberMemory(BBI)) { + if (isElidable(BBI)) { // See through pointer-to-pointer bitcasts - Value* pointerOperand = S->getPointerOperand()->getUnderlyingObject(); + Value *pointerOperand = getPointerOperand(BBI)->getUnderlyingObject(); // Alloca'd pointers or byval arguments (which are functionally like // alloca's) are valid candidates for removal. if (deadPointers.count(pointerOperand)) { // DCE instructions only used to calculate that store. + Instruction *Dead = BBI; BBI++; - DeleteDeadInstruction(S, &deadPointers); + DeleteDeadInstruction(Dead, &deadPointers); NumFastStores++; MadeChange = true; + continue; } } - continue; - } - - // We can also remove memcpy's to local variables at the end of a function. - if (MemCpyInst *M = dyn_cast(BBI)) { - Value *dest = M->getDest()->getUnderlyingObject(); - - if (deadPointers.count(dest)) { - BBI++; - DeleteDeadInstruction(M, &deadPointers); - NumFastOther++; - MadeChange = true; + // Because a memcpy or memmove is also a load, we can't skip it if we + // didn't remove it. + if (!isa(BBI)) continue; - } - - // Because a memcpy is also a load, we can't skip it if we didn't remove - // it. } Value* killPointer = 0; @@ -304,11 +359,11 @@ bool DSE::handleEndBlock(BasicBlock &BB) { killPointer = L->getPointerOperand(); } else if (VAArgInst* V = dyn_cast(BBI)) { killPointer = V->getOperand(0); - } else if (isa(BBI) && - isa(cast(BBI)->getLength())) { - killPointer = cast(BBI)->getSource(); + } else if (isa(BBI) && + isa(cast(BBI)->getLength())) { + killPointer = cast(BBI)->getSource(); killPointerSize = cast( - cast(BBI)->getLength())->getZExtValue(); + cast(BBI)->getLength())->getZExtValue(); } else if (AllocaInst* A = dyn_cast(BBI)) { deadPointers.erase(A); diff --git a/test/Transforms/DeadStoreElimination/lifetime.ll b/test/Transforms/DeadStoreElimination/lifetime.ll new file mode 100644 index 0000000000..b2da790db2 --- /dev/null +++ b/test/Transforms/DeadStoreElimination/lifetime.ll @@ -0,0 +1,19 @@ +; RUN: opt -S -dse < %s | FileCheck %s + +declare void @llvm.lifetime.end(i64, i8*) +declare void @llvm.memset.i8(i8*, i8, i8, i32) + +define void @test1() { +; CHECK: @test1 + %A = alloca i8 + + store i8 0, i8* %A ;; Written to by memset + call void @llvm.lifetime.end(i64 1, i8* %A) +; CHECK: lifetime.end + + call void @llvm.memset.i8(i8* %A, i8 0, i8 -1, i32 0) +; CHECK-NOT: memset + + ret void +; CHECK: ret void +} diff --git a/test/Transforms/DeadStoreElimination/memintrinsics.ll b/test/Transforms/DeadStoreElimination/memintrinsics.ll new file mode 100644 index 0000000000..e31e9fa3ca --- /dev/null +++ b/test/Transforms/DeadStoreElimination/memintrinsics.ll @@ -0,0 +1,47 @@ +; RUN: opt -S -dse < %s | FileCheck %s + +declare void @llvm.memcpy.i8(i8*, i8*, i8, i32) +declare void @llvm.memmove.i8(i8*, i8*, i8, i32) +declare void @llvm.memset.i8(i8*, i8, i8, i32) + +define void @test1() { +; CHECK: @test1 + %A = alloca i8 + %B = alloca i8 + + store i8 0, i8* %A ;; Written to by memcpy +; CHECK-NOT: store + + call void @llvm.memcpy.i8(i8* %A, i8* %B, i8 -1, i32 0) + + ret void +; CHECK: ret void +} + +define void @test2() { +; CHECK: @test2 + %A = alloca i8 + %B = alloca i8 + + store i8 0, i8* %A ;; Written to by memmove +; CHECK-NOT: store + + call void @llvm.memmove.i8(i8* %A, i8* %B, i8 -1, i32 0) + + ret void +; CHECK: ret void +} + +define void @test3() { +; CHECK: @test3 + %A = alloca i8 + %B = alloca i8 + + store i8 0, i8* %A ;; Written to by memset +; CHECK-NOT: store + + call void @llvm.memset.i8(i8* %A, i8 0, i8 -1, i32 0) + + ret void +; CHECK: ret void +} diff --git a/test/Transforms/DeadStoreElimination/partial-overwrite.ll b/test/Transforms/DeadStoreElimination/partial-overwrite.ll new file mode 100644 index 0000000000..048d4645fc --- /dev/null +++ b/test/Transforms/DeadStoreElimination/partial-overwrite.ll @@ -0,0 +1,14 @@ +; RUN: opt -dse -S %s | FileCheck %s +; Note that we could do better by merging the two stores into one. + +target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128" +target triple = "x86_64-unknown-linux-gnu" + +define void @test(i32* %P) { + store i32 0, i32* %P +; CHECK: store i32 + %Q = bitcast i32* %P to i16* + store i16 1, i16* %Q +; CHECK: store i16 + ret void +} -- 2.11.4.GIT