X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FADCE.cpp;h=590a52da6b192665f4d1574cf80063aa5312027b;hb=40288f72380d2951cd2d4034922c2c515acb6cfd;hp=f7035e576b3039dac4d1be16582662d555c6432b;hpb=77d76b7ef7fba0cf694977ef5abbdea28e600833;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/ADCE.cpp b/lib/Transforms/Scalar/ADCE.cpp index f7035e576b3..590a52da6b1 100644 --- a/lib/Transforms/Scalar/ADCE.cpp +++ b/lib/Transforms/Scalar/ADCE.cpp @@ -1,4 +1,4 @@ -//===- DCE.cpp - Code to perform dead code elimination --------------------===// +//===- ADCE.cpp - Code to perform dead code elimination -------------------===// // // The LLVM Compiler Infrastructure // @@ -9,130 +9,100 @@ // // This file implements the Aggressive Dead Code Elimination pass. This pass // optimistically assumes that all instructions are dead until proven otherwise, -// allowing it to eliminate dead computations that other DCE passes do not +// allowing it to eliminate dead computations that other DCE passes do not // catch, particularly involving loop computations. // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "adce" -#include "llvm/Transforms/Scalar.h" -#include "llvm/BasicBlock.h" -#include "llvm/Instructions.h" -#include "llvm/Pass.h" -#include "llvm/Support/CFG.h" -#include "llvm/Support/Compiler.h" -#include "llvm/Support/InstIterator.h" -#include "llvm/ADT/DenseSet.h" +#include "llvm/Transforms/Scalar/ADCE.h" #include "llvm/ADT/DepthFirstIterator.h" -#include "llvm/ADT/Statistic.h" +#include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" - +#include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/GlobalsModRef.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/CFG.h" +#include "llvm/IR/InstIterator.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/Pass.h" +#include "llvm/Transforms/Scalar.h" using namespace llvm; -STATISTIC(NumRemoved, "Number of instructions removed"); +#define DEBUG_TYPE "adce" -namespace { - struct VISIBILITY_HIDDEN ADCE : public FunctionPass { - static char ID; // Pass identification, replacement for typeid - ADCE() : FunctionPass((intptr_t)&ID) {} - - DenseSet alive; - SmallVector worklist; - - DenseSet reachable; - SmallVector unreachable; - - virtual bool runOnFunction(Function& F); - - virtual void getAnalysisUsage(AnalysisUsage& AU) const { - AU.setPreservesCFG(); - } - - }; -} +STATISTIC(NumRemoved, "Number of instructions removed"); -char ADCE::ID = 0; -static RegisterPass X("adce", "Aggressive Dead Code Elimination"); +static bool aggressiveDCE(Function& F) { + SmallPtrSet Alive; + SmallVector Worklist; -bool ADCE::runOnFunction(Function& F) { - alive.clear(); - worklist.clear(); - reachable.clear(); - unreachable.clear(); - - // First, collect the set of reachable blocks ... - for (df_iterator DI = df_begin(&F.getEntryBlock()), - DE = df_end(&F.getEntryBlock()); DI != DE; ++DI) - reachable.insert(*DI); - - // ... and then invert it into the list of unreachable ones. These - // blocks will be removed from the function. - for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) - if (!reachable.count(FI)) - unreachable.push_back(FI); - - // Prepare to remove blocks by removing the PHI node entries for those blocks - // in their successors, and remove them from reference counting. - for (SmallVector::iterator UI = unreachable.begin(), - UE = unreachable.end(); UI != UE; ++UI) { - BasicBlock* BB = *UI; - for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); - SI != SE; ++SI) { - BasicBlock* succ = *SI; - BasicBlock::iterator succ_inst = succ->begin(); - while (PHINode* P = dyn_cast(succ_inst)) { - P->removeIncomingValue(BB); - ++succ_inst; - } - } - - BB->dropAllReferences(); - } - - // Finally, erase the unreachable blocks. - for (SmallVector::iterator UI = unreachable.begin(), - UE = unreachable.end(); UI != UE; ++UI) - (*UI)->eraseFromParent(); - // Collect the set of "root" instructions that are known live. - for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) - if (isa(I.getInstructionIterator()) || - I->mayWriteToMemory()) { - alive.insert(I.getInstructionIterator()); - worklist.push_back(I.getInstructionIterator()); + for (Instruction &I : instructions(F)) { + if (isa(I) || isa(I) || I.isEHPad() || + I.mayHaveSideEffects()) { + Alive.insert(&I); + Worklist.push_back(&I); } - + } + // Propagate liveness backwards to operands. - while (!worklist.empty()) { - Instruction* curr = worklist.back(); - worklist.pop_back(); - - for (Instruction::op_iterator OI = curr->op_begin(), OE = curr->op_end(); - OI != OE; ++OI) - if (Instruction* Inst = dyn_cast(OI)) - if (alive.insert(Inst)) - worklist.push_back(Inst); + while (!Worklist.empty()) { + Instruction *Curr = Worklist.pop_back_val(); + for (Use &OI : Curr->operands()) { + if (Instruction *Inst = dyn_cast(OI)) + if (Alive.insert(Inst).second) + Worklist.push_back(Inst); + } } - + // The inverse of the live set is the dead set. These are those instructions // which have no side effects and do not influence the control flow or return // value of the function, and may therefore be deleted safely. - // NOTE: We reuse the worklist vector here for memory efficiency. - for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) - if (!alive.count(I.getInstructionIterator())) { - worklist.push_back(I.getInstructionIterator()); - I->dropAllReferences(); + // NOTE: We reuse the Worklist vector here for memory efficiency. + for (Instruction &I : instructions(F)) { + if (!Alive.count(&I)) { + Worklist.push_back(&I); + I.dropAllReferences(); } - - for (SmallVector::iterator I = worklist.begin(), - E = worklist.end(); I != E; ++I) { - NumRemoved++; - (*I)->eraseFromParent(); } - - return !worklist.empty(); + + for (Instruction *&I : Worklist) { + ++NumRemoved; + I->eraseFromParent(); + } + + return !Worklist.empty(); +} + +PreservedAnalyses ADCEPass::run(Function &F) { + if (aggressiveDCE(F)) + return PreservedAnalyses::none(); + return PreservedAnalyses::all(); } -FunctionPass *llvm::createAggressiveDCEPass() { - return new ADCE(); +namespace { +struct ADCELegacyPass : public FunctionPass { + static char ID; // Pass identification, replacement for typeid + ADCELegacyPass() : FunctionPass(ID) { + initializeADCELegacyPassPass(*PassRegistry::getPassRegistry()); + } + + bool runOnFunction(Function& F) override { + if (skipOptnoneFunction(F)) + return false; + return aggressiveDCE(F); + } + + void getAnalysisUsage(AnalysisUsage& AU) const override { + AU.setPreservesCFG(); + AU.addPreserved(); + } +}; } + +char ADCELegacyPass::ID = 0; +INITIALIZE_PASS(ADCELegacyPass, "adce", "Aggressive Dead Code Elimination", + false, false) + +FunctionPass *llvm::createAggressiveDCEPass() { return new ADCELegacyPass(); }