#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/Dominators.h"
+#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/MemoryDependenceAnalysis.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Transforms/Utils/Local.h"
-#include "llvm/Support/Compiler.h"
using namespace llvm;
STATISTIC(NumFastStores, "Number of stores deleted");
STATISTIC(NumFastOther , "Number of other instrs removed");
namespace {
- struct VISIBILITY_HIDDEN DSE : public FunctionPass {
+ struct DSE : public FunctionPass {
+ TargetData *TD;
+
static char ID; // Pass identification, replacement for typeid
DSE() : FunctionPass(&ID) {}
return Changed;
}
- typedef MemoryDependenceAnalysis::DepResultTy DepResultTy;
-
bool runOnBasicBlock(BasicBlock &BB);
- bool handleFreeWithNonTrivialDependency(FreeInst *F, DepResultTy Dep);
+ bool handleFreeWithNonTrivialDependency(Instruction *F, MemDepResult Dep);
bool handleEndBlock(BasicBlock &BB);
- bool RemoveUndeadPointers(Value* pointer, uint64_t killPointerSize,
- BasicBlock::iterator& BBI,
- SmallPtrSet<Value*, 64>& deadPointers);
+ bool RemoveUndeadPointers(Value *Ptr, uint64_t killPointerSize,
+ BasicBlock::iterator &BBI,
+ SmallPtrSet<Value*, 64> &deadPointers);
void DeleteDeadInstruction(Instruction *I,
SmallPtrSet<Value*, 64> *deadPointers = 0);
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
AU.addRequired<DominatorTree>();
- AU.addRequired<TargetData>();
AU.addRequired<AliasAnalysis>();
AU.addRequired<MemoryDependenceAnalysis>();
AU.addPreserved<DominatorTree>();
AU.addPreserved<AliasAnalysis>();
AU.addPreserved<MemoryDependenceAnalysis>();
}
+
+ unsigned getPointerSize(Value *V) const;
};
}
FunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); }
-bool DSE::runOnBasicBlock(BasicBlock &BB) {
- MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
- TargetData &TD = getAnalysis<TargetData>();
+/// doesClobberMemory - Does this instruction clobber (write without reading)
+/// some memory?
+static bool doesClobberMemory(Instruction *I) {
+ if (isa<StoreInst>(I))
+ return true;
+ if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
+ switch (II->getIntrinsicID()) {
+ default:
+ return false;
+ case Intrinsic::memset:
+ case Intrinsic::memmove:
+ case Intrinsic::memcpy:
+ case Intrinsic::init_trampoline:
+ case Intrinsic::lifetime_end:
+ return true;
+ }
+ }
+ return false;
+}
+
+/// isElidable - If the value of 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<IntrinsicInst>(I))
+ return II->getIntrinsicID() != Intrinsic::lifetime_end;
+ if (StoreInst *SI = dyn_cast<StoreInst>(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<StoreInst>(I))
+ return SI->getPointerOperand();
+ if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I))
+ return MI->getOperand(1);
+
+ switch (cast<IntrinsicInst>(I)->getIntrinsicID()) {
+ default: assert(false && "Unexpected intrinsic!");
+ case Intrinsic::init_trampoline:
+ return I->getOperand(1);
+ case Intrinsic::lifetime_end:
+ return 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<StoreInst>(I)) {
+ if (!TD) return -1u;
+ return TD->getTypeStoreSize(SI->getOperand(0)->getType());
+ }
+
+ Value *Len;
+ if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
+ Len = MI->getLength();
+ } else {
+ switch (cast<IntrinsicInst>(I)->getIntrinsicID()) {
+ default: assert(false && "Unexpected intrinsic!");
+ case Intrinsic::init_trampoline:
+ return -1u;
+ case Intrinsic::lifetime_end:
+ Len = I->getOperand(1);
+ break;
+ }
+ }
+ if (ConstantInt *LenCI = dyn_cast<ConstantInt>(Len))
+ if (!LenCI->isAllOnesValue())
+ return LenCI->getZExtValue();
+ return -1u;
+}
- // Record the last-seen store to this pointer
- DenseMap<Value*, StoreInst*> lastStore;
+/// 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 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 (I1Ty == I2Ty) return true;
+
+ int I1Size = getStoreSize(I1, TD);
+ int I2Size = getStoreSize(I2, TD);
+
+ return I1Size != -1 && I2Size != -1 && I1Size >= I2Size;
+}
+
+bool DSE::runOnBasicBlock(BasicBlock &BB) {
+ MemoryDependenceAnalysis &MD = getAnalysis<MemoryDependenceAnalysis>();
+ TD = getAnalysisIfAvailable<TargetData>();
+
bool MadeChange = false;
- // Do a top-down walk on the BB
+ // Do a top-down walk on the BB.
for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) {
Instruction *Inst = BBI++;
- // If we find a store or a free...
- if (!isa<StoreInst>(Inst) && !isa<FreeInst>(Inst))
+ // If we find a store or a free, get its memory dependence.
+ if (!doesClobberMemory(Inst) && !isFreeCall(Inst))
+ continue;
+
+ MemDepResult InstDep = MD.getDependency(Inst);
+
+ // Ignore non-local stores.
+ // FIXME: cross-block DSE would be fun. :)
+ if (InstDep.isNonLocal()) continue;
+
+ // Handle frees whose dependencies are non-trivial.
+ if (isFreeCall(Inst)) {
+ MadeChange |= handleFreeWithNonTrivialDependency(Inst, InstDep);
continue;
-
- Value* pointer = 0;
- if (StoreInst* S = dyn_cast<StoreInst>(Inst)) {
- if (S->isVolatile())
- continue;
- pointer = S->getPointerOperand();
- } else {
- pointer = cast<FreeInst>(Inst)->getPointerOperand();
}
-
- pointer = pointer->stripPointerCasts();
- StoreInst *&last = lastStore[pointer];
-
- // ... to a pointer that has been stored to before...
- if (last) {
- DepResultTy dep = MD.getDependency(Inst);
- bool deletedStore = false;
- // ... and no other memory dependencies are between them....
- while (dep.getInt() == MemoryDependenceAnalysis::Normal &&
- isa<StoreInst>(dep.getPointer())) {
- if (dep.getPointer() != last ||
- TD.getTypeStoreSize(last->getOperand(0)->getType()) >
- TD.getTypeStoreSize(Inst->getOperand(0)->getType())) {
- dep = MD.getDependency(Inst, dep.getPointer());
- continue;
- }
-
+ // 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 (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(last);
+ DeleteDeadInstruction(DepStore);
NumFastStores++;
- deletedStore = true;
MadeChange = true;
- break;
- }
-
- // If we deleted a store, reinvestigate this instruction.
- if (deletedStore) {
- if (!isa<TerminatorInst>(BB.begin()))
+
+ // DeleteDeadInstruction can delete the current instruction in loop
+ // cases, reset BBI.
+ BBI = Inst;
+ if (BBI != BB.begin())
--BBI;
continue;
}
}
- // Handle frees whose dependencies are non-trivial.
- if (FreeInst* F = dyn_cast<FreeInst>(Inst)) {
- MadeChange |= handleFreeWithNonTrivialDependency(F, MD.getDependency(F));
-
- // No known stores after the free.
- last = 0;
- } else {
- StoreInst* S = cast<StoreInst>(Inst);
-
- // If we're storing the same value back to a pointer that we just
- // loaded from, then the store can be removed;
- if (LoadInst* L = dyn_cast<LoadInst>(S->getOperand(0))) {
- // FIXME: Don't do dep query if Parents don't match and other stuff!
- DepResultTy dep = MD.getDependency(S);
- DominatorTree& DT = getAnalysis<DominatorTree>();
-
- if (!S->isVolatile() && S->getParent() == L->getParent() &&
- S->getPointerOperand() == L->getPointerOperand() &&
- (dep.getInt() == MemoryDependenceAnalysis::None ||
- dep.getInt() == MemoryDependenceAnalysis::NonLocal ||
- DT.dominates(dep.getPointer(), L))) {
+ 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 (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
+ if (LoadInst *DepLoad = dyn_cast<LoadInst>(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(S);
- if (!isa<TerminatorInst>(BB.begin()))
+ 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;
- } else
- // Update our most-recent-store map.
- last = S;
- } else
- // Update our most-recent-store map.
- last = S;
+ continue;
+ }
+ }
+ }
+
+ // If this is a lifetime end marker, we can throw away the store.
+ if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(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(Inst);
+
+ if (NextInst == 0) // Next instruction deleted.
+ BBI = BB.begin();
+ else if (BBI != BB.begin()) // Revisit this instruction if possible.
+ --BBI;
+ NumFastStores++;
+ MadeChange = true;
+ continue;
+ }
}
}
/// handleFreeWithNonTrivialDependency - Handle frees of entire structures whose
/// dependency is a store to a field of that structure.
-bool DSE::handleFreeWithNonTrivialDependency(FreeInst* F, DepResultTy dep) {
- TargetData &TD = getAnalysis<TargetData>();
+bool DSE::handleFreeWithNonTrivialDependency(Instruction *F, MemDepResult Dep) {
AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
- if (dep.getInt() == MemoryDependenceAnalysis::None ||
- dep.getInt() == MemoryDependenceAnalysis::NonLocal)
- return false;
-
- StoreInst* dependency = dyn_cast<StoreInst>(dep.getPointer());
- if (!dependency)
- return false;
- else if (dependency->isVolatile())
+ Instruction *Dependency = Dep.getInst();
+ if (!Dependency || !doesClobberMemory(Dependency) || !isElidable(Dependency))
return false;
- Value* depPointer = dependency->getPointerOperand();
- const Type* depType = dependency->getOperand(0)->getType();
- unsigned depPointerSize = TD.getTypeStoreSize(depType);
-
- // Check for aliasing
- AliasAnalysis::AliasResult A = AA.alias(F->getPointerOperand(), ~0U,
- depPointer, depPointerSize);
+ Value *DepPointer = getPointerOperand(Dependency)->getUnderlyingObject();
- if (A != AliasAnalysis::MustAlias)
+ // Check for aliasing.
+ if (AA.alias(F->getOperand(1), 1, DepPointer, 1) !=
+ AliasAnalysis::MustAlias)
return false;
// DCE instructions only used to calculate that store
- DeleteDeadInstruction(dependency);
+ DeleteDeadInstruction(Dependency);
NumFastStores++;
return true;
}
/// store i32 1, i32* %A
/// ret void
bool DSE::handleEndBlock(BasicBlock &BB) {
- TargetData &TD = getAnalysis<TargetData>();
AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
bool MadeChange = false;
--BBI;
// If we find a store whose pointer is dead.
- if (StoreInst* S = dyn_cast<StoreInst>(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<MemCpyInst>(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<MemTransferInst>(BBI))
continue;
- }
-
- // Because a memcpy is also a load, we can't skip it if we didn't remove
- // it.
}
- Value* killPointer = 0;
+ Value *killPointer = 0;
uint64_t killPointerSize = ~0UL;
// If we encounter a use of the pointer, it is no longer considered dead
}
killPointer = L->getPointerOperand();
- } else if (VAArgInst* V = dyn_cast<VAArgInst>(BBI)) {
+ } else if (VAArgInst *V = dyn_cast<VAArgInst>(BBI)) {
killPointer = V->getOperand(0);
- } else if (isa<MemCpyInst>(BBI) &&
- isa<ConstantInt>(cast<MemCpyInst>(BBI)->getLength())) {
- killPointer = cast<MemCpyInst>(BBI)->getSource();
+ } else if (isa<MemTransferInst>(BBI) &&
+ isa<ConstantInt>(cast<MemTransferInst>(BBI)->getLength())) {
+ killPointer = cast<MemTransferInst>(BBI)->getSource();
killPointerSize = cast<ConstantInt>(
- cast<MemCpyInst>(BBI)->getLength())->getZExtValue();
- } else if (AllocaInst* A = dyn_cast<AllocaInst>(BBI)) {
+ cast<MemTransferInst>(BBI)->getLength())->getZExtValue();
+ } else if (AllocaInst *A = dyn_cast<AllocaInst>(BBI)) {
deadPointers.erase(A);
// Dead alloca's can be DCE'd when we reach them
deadPointers.clear();
return MadeChange;
}
-
- // Get size information for the alloca
- unsigned pointerSize = ~0U;
- if (AllocaInst* A = dyn_cast<AllocaInst>(*I)) {
- if (ConstantInt* C = dyn_cast<ConstantInt>(A->getArraySize()))
- pointerSize = C->getZExtValue() *
- TD.getABITypeSize(A->getAllocatedType());
- } else {
- const PointerType* PT = cast<PointerType>(
- cast<Argument>(*I)->getType());
- pointerSize = TD.getABITypeSize(PT->getElementType());
- }
-
+
// See if the call site touches it
- AliasAnalysis::ModRefResult A = AA.getModRefInfo(CS, *I, pointerSize);
+ AliasAnalysis::ModRefResult A = AA.getModRefInfo(CS, *I,
+ getPointerSize(*I));
if (A == AliasAnalysis::ModRef)
modRef++;
/// RemoveUndeadPointers - check for uses of a pointer that make it
/// undead when scanning for dead stores to alloca's.
-bool DSE::RemoveUndeadPointers(Value* killPointer, uint64_t killPointerSize,
+bool DSE::RemoveUndeadPointers(Value *killPointer, uint64_t killPointerSize,
BasicBlock::iterator &BBI,
- SmallPtrSet<Value*, 64>& deadPointers) {
- TargetData &TD = getAnalysis<TargetData>();
+ SmallPtrSet<Value*, 64> &deadPointers) {
AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
-
+
// If the kill pointer can be easily reduced to an alloca,
// don't bother doing extraneous AA queries.
if (deadPointers.count(killPointer)) {
bool MadeChange = false;
SmallVector<Value*, 16> undead;
-
+
for (SmallPtrSet<Value*, 64>::iterator I = deadPointers.begin(),
- E = deadPointers.end(); I != E; ++I) {
- // Get size information for the alloca.
- unsigned pointerSize = ~0U;
- if (AllocaInst* A = dyn_cast<AllocaInst>(*I)) {
- if (ConstantInt* C = dyn_cast<ConstantInt>(A->getArraySize()))
- pointerSize = C->getZExtValue() *
- TD.getABITypeSize(A->getAllocatedType());
- } else {
- const PointerType* PT = cast<PointerType>(cast<Argument>(*I)->getType());
- pointerSize = TD.getABITypeSize(PT->getElementType());
- }
-
+ E = deadPointers.end(); I != E; ++I) {
// See if this pointer could alias it
- AliasAnalysis::AliasResult A = AA.alias(*I, pointerSize,
+ AliasAnalysis::AliasResult A = AA.alias(*I, getPointerSize(*I),
killPointer, killPointerSize);
// If it must-alias and a store, we can delete it
if (isa<StoreInst>(BBI) && A == AliasAnalysis::MustAlias) {
- StoreInst* S = cast<StoreInst>(BBI);
+ StoreInst *S = cast<StoreInst>(BBI);
// Remove it!
- BBI++;
+ ++BBI;
DeleteDeadInstruction(S, &deadPointers);
NumFastStores++;
MadeChange = true;
if (ValueSet) ValueSet->erase(DeadInst);
}
}
+
+unsigned DSE::getPointerSize(Value *V) const {
+ if (TD) {
+ if (AllocaInst *A = dyn_cast<AllocaInst>(V)) {
+ // Get size information for the alloca
+ if (ConstantInt *C = dyn_cast<ConstantInt>(A->getArraySize()))
+ return C->getZExtValue() * TD->getTypeAllocSize(A->getAllocatedType());
+ } else {
+ assert(isa<Argument>(V) && "Expected AllocaInst or Argument!");
+ const PointerType *PT = cast<PointerType>(V->getType());
+ return TD->getTypeAllocSize(PT->getElementType());
+ }
+ }
+ return ~0U;
+}