#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/MemoryDependenceAnalysis.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Transforms/Utils/Local.h"
namespace {
struct VISIBILITY_HIDDEN DSE : public FunctionPass {
static char ID; // Pass identification, replacement for typeid
- DSE() : FunctionPass((intptr_t)&ID) {}
+ DSE() : FunctionPass(&ID) {}
virtual bool runOnFunction(Function &F) {
bool Changed = false;
SetVector<Instruction*>& possiblyDead);
void DeleteDeadInstructionChains(Instruction *I,
SetVector<Instruction*> &DeadInsts);
-
- /// Find the base pointer that a pointer came from
- /// Because this is used to find pointers that originate
- /// from allocas, it is safe to ignore GEP indices, since
- /// either the store will be in the alloca, and thus dead,
- /// or beyond the end of the alloca, and thus undefined.
- void TranslatePointerBitCasts(Value*& v, bool zeroGepsOnly = false) {
- assert(isa<PointerType>(v->getType()) &&
- "Translating a non-pointer type?");
- while (true) {
- if (BitCastInst* C = dyn_cast<BitCastInst>(v))
- v = C->getOperand(0);
- else if (GetElementPtrInst* G = dyn_cast<GetElementPtrInst>(v))
- if (!zeroGepsOnly || G->hasAllZeroIndices()) {
- v = G->getOperand(0);
- } else {
- break;
- }
- else
- break;
- }
- }
+
// getAnalysisUsage - We require post dominance frontiers (aka Control
// Dependence Graph)
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>();
}
// If we find a store or a free...
if (!isa<StoreInst>(BBI) && !isa<FreeInst>(BBI))
continue;
-
+
Value* pointer = 0;
if (StoreInst* S = dyn_cast<StoreInst>(BBI)) {
- if (!S->isVolatile())
- pointer = S->getPointerOperand();
- else
+ if (S->isVolatile())
continue;
- } else
+ pointer = S->getPointerOperand();
+ } else {
pointer = cast<FreeInst>(BBI)->getPointerOperand();
-
- TranslatePointerBitCasts(pointer, true);
+ }
+
+ pointer = pointer->stripPointerCasts();
StoreInst*& last = lastStore[pointer];
bool deletedStore = false;
-
+
// ... to a pointer that has been stored to before...
if (last) {
Instruction* dep = MD.getDependency(BBI);
// No known stores after the free
last = 0;
} else {
- // Update our most-recent-store map.
- last = cast<StoreInst>(BBI);
+ StoreInst* S = cast<StoreInst>(BBI);
+
+ // 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))) {
+ Instruction* dep = MD.getDependency(S);
+ DominatorTree& DT = getAnalysis<DominatorTree>();
+
+ if (!S->isVolatile() && S->getParent() == L->getParent() &&
+ S->getPointerOperand() == L->getPointerOperand() &&
+ ( dep == MemoryDependenceAnalysis::None ||
+ dep == MemoryDependenceAnalysis::NonLocal ||
+ DT.dominates(dep, L))) {
+ if (Instruction* D = dyn_cast<Instruction>(S->getOperand(0)))
+ possiblyDead.insert(D);
+ if (Instruction* D = dyn_cast<Instruction>(S->getOperand(1)))
+ possiblyDead.insert(D);
+
+ // Avoid iterator invalidation.
+ BBI--;
+
+ MD.removeInstruction(S);
+ S->eraseFromParent();
+ NumFastStores++;
+ MadeChange = true;
+ } else
+ // Update our most-recent-store map.
+ last = S;
+ } else
+ // Update our most-recent-store map.
+ last = S;
}
}
// If we find a store whose pointer is dead...
if (StoreInst* S = dyn_cast<StoreInst>(BBI)) {
if (!S->isVolatile()) {
- Value* pointerOperand = S->getPointerOperand();
// See through pointer-to-pointer bitcasts
- TranslatePointerBitCasts(pointerOperand);
-
+ Value* pointerOperand = S->getPointerOperand()->getUnderlyingObject();
+
// Alloca'd pointers or byval arguments (which are functionally like
// alloca's) are valid candidates for removal.
if (deadPointers.count(pointerOperand)) {
possiblyDead.insert(D);
BBI++;
+ MD.removeInstruction(S);
S->eraseFromParent();
NumFastStores++;
MadeChange = true;
// We can also remove memcpy's to local variables at the end of a function
} else if (MemCpyInst* M = dyn_cast<MemCpyInst>(BBI)) {
- Value* dest = M->getDest();
- TranslatePointerBitCasts(dest);
-
+ Value* dest = M->getDest()->getUnderlyingObject();
+
if (deadPointers.count(dest)) {
MD.removeInstruction(M);
// If we encounter a use of the pointer, it is no longer considered dead
if (LoadInst* L = dyn_cast<LoadInst>(BBI)) {
- // However, if this load is unused and not volatile, we can go ahead and remove it,
- // and not have to worry about it making our pointer undead!
+ // However, if this load is unused and not volatile, we can go ahead and
+ // remove it, and not have to worry about it making our pointer undead!
if (L->use_empty() && !L->isVolatile()) {
MD.removeInstruction(L);
if (!killPointer)
continue;
-
- TranslatePointerBitCasts(killPointer);
-
+
+ killPointer = killPointer->getUnderlyingObject();
+
// Deal with undead pointers
MadeChange |= RemoveUndeadPointers(killPointer, killPointerSize, BBI,
deadPointers, possiblyDead);
projects / oota-llvm.git / blobdiff