From a96c1f665af2d8bc8539e7d202b058cb0853c2b7 Mon Sep 17 00:00:00 2001 From: Owen Anderson Date: Wed, 11 Jul 2007 23:19:17 +0000 Subject: [PATCH] Handle the case where an entire structure is freed, and its dependency is a store to a field within that structure. Also, refactor the runOnBasicBlock() function, splitting some of the special cases into separate functions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@39762 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/FastDSE.cpp | 143 +++++++++++++++++++++--------- 1 file changed, 101 insertions(+), 42 deletions(-) diff --git a/lib/Transforms/Scalar/FastDSE.cpp b/lib/Transforms/Scalar/FastDSE.cpp index cd85b7caef7..e2d81794d81 100644 --- a/lib/Transforms/Scalar/FastDSE.cpp +++ b/lib/Transforms/Scalar/FastDSE.cpp @@ -23,7 +23,9 @@ #include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/AliasAnalysis.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; @@ -44,6 +46,9 @@ namespace { } bool runOnBasicBlock(BasicBlock &BB); + bool handleFreeWithNonTrivialDependency(FreeInst* F, StoreInst* dependency, + SetVector& possiblyDead); + bool handleEndBlock(BasicBlock& BB, SetVector& possiblyDead); void DeleteDeadInstructionChains(Instruction *I, SetVector &DeadInsts); @@ -51,7 +56,10 @@ namespace { // Dependence Graph) virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesCFG(); + AU.addRequired(); + AU.addRequired(); AU.addRequired(); + AU.addPreserved(); AU.addPreserved(); } }; @@ -62,6 +70,7 @@ namespace { FunctionPass *llvm::createFastDeadStoreEliminationPass() { return new FDSE(); } bool FDSE::runOnBasicBlock(BasicBlock &BB) { + AliasAnalysis &AA = getAnalysis(); MemoryDependenceAnalysis& MD = getAnalysis(); // Record the last-seen store to this pointer @@ -92,6 +101,7 @@ bool FDSE::runOnBasicBlock(BasicBlock &BB) { // Remove it! MD.removeInstruction(last); + AA.deleteValue(last); // DCE instructions only used to calculate that store if (Instruction* D = dyn_cast(last->getOperand(0))) @@ -100,7 +110,10 @@ bool FDSE::runOnBasicBlock(BasicBlock &BB) { last->eraseFromParent(); NumFastStores++; MadeChange = true; - } + + // If this is a free, check for a non-trivial dependency + } else if (FreeInst* F = dyn_cast(BBI)) + MadeChange |= handleFreeWithNonTrivialDependency(F, last, possiblyDead); } // Update our most-recent-store map @@ -113,47 +126,8 @@ bool FDSE::runOnBasicBlock(BasicBlock &BB) { // If this block ends in a return, unwind, unreachable, and eventually // tailcall, then all allocas are dead at its end. - if (BB.getTerminator()->getNumSuccessors() == 0) { - // Pointers alloca'd in this function are dead in the end block - SmallPtrSet deadPointers; - - // Find all of the alloca'd pointers in the entry block - BasicBlock *Entry = BB.getParent()->begin(); - for (BasicBlock::iterator I = Entry->begin(), E = Entry->end(); I != E; ++I) - if (AllocaInst *AI = dyn_cast(I)) - deadPointers.insert(AI); - - // Scan the basic block backwards - for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){ - --BBI; - - if (deadPointers.empty()) - break; - - // If we find a store whose pointer is dead... - if (StoreInst* S = dyn_cast(BBI)) { - if (deadPointers.count(S->getPointerOperand())){ - // Remove it! - MD.removeInstruction(S); - - // DCE instructions only used to calculate that store - if (Instruction* D = dyn_cast(S->getOperand(0))) - possiblyDead.insert(D); - - BBI++; - S->eraseFromParent(); - NumFastStores++; - MadeChange = true; - } - - // If we encounter a use of the pointer, it is no longer considered dead - } else if (LoadInst* L = dyn_cast(BBI)) { - deadPointers.erase(L->getPointerOperand()); - } else if (VAArgInst* V = dyn_cast(BBI)) { - deadPointers.erase(V->getOperand(0)); - } - } - } + if (BB.getTerminator()->getNumSuccessors() == 0) + MadeChange |= handleEndBlock(BB, possiblyDead); // Do a trivial DCE while (!possiblyDead.empty()) { @@ -165,6 +139,90 @@ bool FDSE::runOnBasicBlock(BasicBlock &BB) { return MadeChange; } +/// handleFreeWithNonTrivialDependency - Handle frees of entire structures whose +/// dependency is a store to a field of that structure +bool FDSE::handleFreeWithNonTrivialDependency(FreeInst* F, StoreInst* dependency, + SetVector& possiblyDead) { + TargetData &TD = getAnalysis(); + AliasAnalysis &AA = getAnalysis(); + MemoryDependenceAnalysis& MD = getAnalysis(); + + Value* depPointer = dependency->getPointerOperand(); + unsigned depPointerSize = TD.getTypeSize(dependency->getOperand(0)->getType()); + + // Check for aliasing + AliasAnalysis::AliasResult A = AA.alias(F->getPointerOperand(), ~0UL, + depPointer, depPointerSize); + + if (A == AliasAnalysis::MustAlias) { + // Remove it! + MD.removeInstruction(dependency); + AA.deleteValue(dependency); + + // DCE instructions only used to calculate that store + if (Instruction* D = dyn_cast(dependency->getOperand(0))) + possiblyDead.insert(D); + + dependency->eraseFromParent(); + NumFastStores++; + return true; + } + + return false; +} + +/// handleEndBlock - Remove dead stores to stack-allocated locations in the function +/// end block +bool FDSE::handleEndBlock(BasicBlock& BB, SetVector& possiblyDead) { + AliasAnalysis &AA = getAnalysis(); + MemoryDependenceAnalysis &MD = getAnalysis(); + + bool MadeChange = false; + + // Pointers alloca'd in this function are dead in the end block + SmallPtrSet deadPointers; + + // Find all of the alloca'd pointers in the entry block + BasicBlock *Entry = BB.getParent()->begin(); + for (BasicBlock::iterator I = Entry->begin(), E = Entry->end(); I != E; ++I) + if (AllocaInst *AI = dyn_cast(I)) + deadPointers.insert(AI); + + // Scan the basic block backwards + for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){ + --BBI; + + if (deadPointers.empty()) + break; + + // If we find a store whose pointer is dead... + if (StoreInst* S = dyn_cast(BBI)) { + if (deadPointers.count(S->getPointerOperand())){ + // Remove it! + MD.removeInstruction(S); + AA.deleteValue(S); + + // DCE instructions only used to calculate that store + if (Instruction* D = dyn_cast(S->getOperand(0))) + possiblyDead.insert(D); + + BBI++; + S->eraseFromParent(); + NumFastStores++; + MadeChange = true; + } + + // If we encounter a use of the pointer, it is no longer considered dead + } else if (LoadInst* L = dyn_cast(BBI)) { + deadPointers.erase(L->getPointerOperand()); + } else if (VAArgInst* V = dyn_cast(BBI)) { + deadPointers.erase(V->getOperand(0)); + } + } + + return MadeChange; +} + void FDSE::DeleteDeadInstructionChains(Instruction *I, SetVector &DeadInsts) { // Instruction must be dead. @@ -172,6 +230,7 @@ void FDSE::DeleteDeadInstructionChains(Instruction *I, // Let the memory dependence know getAnalysis().removeInstruction(I); + getAnalysis().deleteValue(I); // See if this made any operands dead. We do it this way in case the // instruction uses the same operand twice. We don't want to delete a -- 2.34.1