X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FDeadStoreElimination.cpp;h=09c01d314124e65ff3c7767db50d7f99eeb93ee9;hb=040056fd11693ffc41ce9b777281c71705d0dc1f;hp=c06015a18b0f7ee1a0dae5d6abd1298a08184347;hpb=4c724006256032e827177afeae04ea62436796e7;p=oota-llvm.git

diff --git a/lib/Transforms/Scalar/DeadStoreElimination.cpp b/lib/Transforms/Scalar/DeadStoreElimination.cpp
index c06015a18b0..09c01d31412 100644
--- a/lib/Transforms/Scalar/DeadStoreElimination.cpp
+++ b/lib/Transforms/Scalar/DeadStoreElimination.cpp
@@ -26,33 +26,41 @@
 #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) {}
 
     virtual bool runOnFunction(Function &F) {
       bool Changed = false;
+      
+      DominatorTree &DT = getAnalysis<DominatorTree>();
+      
       for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
-        Changed |= runOnBasicBlock(*I);
+        // Only check non-dead blocks.  Dead blocks may have strange pointer
+        // cycles that will confuse alias analysis.
+        if (DT.isReachableFromEntry(I))
+          Changed |= runOnBasicBlock(*I);
       return Changed;
     }
     
     bool runOnBasicBlock(BasicBlock &BB);
-    bool handleFreeWithNonTrivialDependency(FreeInst *F, MemDepResult 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);
     
@@ -62,13 +70,14 @@ namespace {
     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;
   };
 }
 
@@ -77,96 +86,194 @@ static RegisterPass<DSE> X("dse", "Dead Store Elimination");
 
 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) {
-      MemDepResult dep = MD.getDependency(Inst);
-      bool deletedStore = false;
     
-      // ... and no other memory dependencies are between them....
-      while (StoreInst *DepStore = dyn_cast_or_null<StoreInst>(dep.getInst())) {
-        if (DepStore != last ||
-            TD.getTypeStoreSize(last->getOperand(0)->getType()) >
-            TD.getTypeStoreSize(Inst->getOperand(0)->getType())) {
-          dep = MD.getDependency(Inst, DepStore);
-          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!
-        MemDepResult dep = MD.getDependency(S);
-        DominatorTree& DT = getAnalysis<DominatorTree>();
-        
-        if (!S->isVolatile() && S->getParent() == L->getParent() &&
-            S->getPointerOperand() == L->getPointerOperand() &&
-            (!dep.isNormal() || DT.dominates(dep.getInst(), 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(SI);
           
-          DeleteDeadInstruction(S);
-          if (!isa<TerminatorInst>(BB.begin()))
+          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;
+      }
     }
   }
   
@@ -180,29 +287,22 @@ bool DSE::runOnBasicBlock(BasicBlock &BB) {
 
 /// handleFreeWithNonTrivialDependency - Handle frees of entire structures whose
 /// dependency is a store to a field of that structure.
-bool DSE::handleFreeWithNonTrivialDependency(FreeInst* F, MemDepResult dep) {
-  TargetData &TD = getAnalysis<TargetData>();
+bool DSE::handleFreeWithNonTrivialDependency(Instruction *F, MemDepResult Dep) {
   AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
   
-  StoreInst* dependency = dyn_cast_or_null<StoreInst>(dep.getInst());
-  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;
 }
@@ -214,7 +314,6 @@ bool DSE::handleFreeWithNonTrivialDependency(FreeInst* F, MemDepResult dep) {
 /// store i32 1, i32* %A
 /// ret void
 bool DSE::handleEndBlock(BasicBlock &BB) {
-  TargetData &TD = getAnalysis<TargetData>();
   AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
   
   bool MadeChange = false;
@@ -240,42 +339,31 @@ bool DSE::handleEndBlock(BasicBlock &BB) {
     --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
@@ -291,14 +379,14 @@ bool DSE::handleEndBlock(BasicBlock &BB) {
       }
       
       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
@@ -332,21 +420,10 @@ bool DSE::handleEndBlock(BasicBlock &BB) {
           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++;
@@ -387,12 +464,11 @@ bool DSE::handleEndBlock(BasicBlock &BB) {
 
 /// 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)) {
@@ -407,30 +483,19 @@ bool DSE::RemoveUndeadPointers(Value* killPointer, uint64_t killPointerSize,
   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;
@@ -464,9 +529,8 @@ void DSE::DeleteDeadInstruction(Instruction *I,
 
   // Before we touch this instruction, remove it from memdep!
   MemoryDependenceAnalysis &MDA = getAnalysis<MemoryDependenceAnalysis>();
-  while (!NowDeadInsts.empty()) {
-    Instruction *DeadInst = NowDeadInsts.back();
-    NowDeadInsts.pop_back();
+  do {
+    Instruction *DeadInst = NowDeadInsts.pop_back_val();
     
     ++NumFastOther;
     
@@ -490,5 +554,20 @@ void DSE::DeleteDeadInstruction(Instruction *I,
     DeadInst->eraseFromParent();
     
     if (ValueSet) ValueSet->erase(DeadInst);
+  } while (!NowDeadInsts.empty());
+}
+
+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;
 }