1 //===- DCE.cpp - Code to perform dead code elimination --------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file implements the Aggressive Dead Code Elimination pass. This pass 11 // optimistically assumes that all instructions are dead until proven otherwise, 12 // allowing it to eliminate dead computations that other DCE passes do not 13 // catch, particularly involving loop computations. 14 // 15 //===----------------------------------------------------------------------===// 16 17 #include "llvm/Transforms/Scalar.h" 18 #include "llvm/ADT/DepthFirstIterator.h" 19 #include "llvm/ADT/SmallPtrSet.h" 20 #include "llvm/ADT/SmallVector.h" 21 #include "llvm/ADT/Statistic.h" 22 #include "llvm/IR/BasicBlock.h" 23 #include "llvm/IR/CFG.h" 24 #include "llvm/IR/InstIterator.h" 25 #include "llvm/IR/Instructions.h" 26 #include "llvm/IR/IntrinsicInst.h" 27 #include "llvm/Pass.h" 28 using namespace llvm; 29 30 #define DEBUG_TYPE "adce" 31 32 STATISTIC(NumRemoved, "Number of instructions removed"); 33 34 namespace { 35 struct ADCE : public FunctionPass { 36 static char ID; // Pass identification, replacement for typeid 37 ADCE() : FunctionPass(ID) { 38 initializeADCEPass(*PassRegistry::getPassRegistry()); 39 } 40 41 bool runOnFunction(Function& F) override; 42 43 void getAnalysisUsage(AnalysisUsage& AU) const override { 44 AU.setPreservesCFG(); 45 } 46 }; 47 } 48 49 char ADCE::ID = 0; 50 INITIALIZE_PASS(ADCE, "adce", "Aggressive Dead Code Elimination", false, false) 51 52 bool ADCE::runOnFunction(Function& F) { 53 if (skipOptnoneFunction(F)) 54 return false; 55 56 SmallPtrSet<Instruction*, 128> Alive; 57 SmallVector<Instruction*, 128> Worklist; 58 59 // Collect the set of "root" instructions that are known live. 60 for (Instruction &I : inst_range(F)) { 61 if (isa<TerminatorInst>(I) || isa<DbgInfoIntrinsic>(I) || 62 isa<LandingPadInst>(I) || I.mayHaveSideEffects()) { 63 Alive.insert(&I); 64 Worklist.push_back(&I); 65 } 66 } 67 68 // Propagate liveness backwards to operands. 69 while (!Worklist.empty()) { 70 Instruction *Curr = Worklist.pop_back_val(); 71 for (Use &OI : Curr->operands()) { 72 if (Instruction *Inst = dyn_cast<Instruction>(OI)) 73 if (Alive.insert(Inst).second) 74 Worklist.push_back(Inst); 75 } 76 } 77 78 // The inverse of the live set is the dead set. These are those instructions 79 // which have no side effects and do not influence the control flow or return 80 // value of the function, and may therefore be deleted safely. 81 // NOTE: We reuse the Worklist vector here for memory efficiency. 82 for (Instruction &I : inst_range(F)) { 83 if (!Alive.count(&I)) { 84 Worklist.push_back(&I); 85 I.dropAllReferences(); 86 } 87 } 88 89 for (Instruction *&I : Worklist) { 90 ++NumRemoved; 91 I->eraseFromParent(); 92 } 93 94 return !Worklist.empty(); 95 } 96 97 FunctionPass *llvm::createAggressiveDCEPass() { 98 return new ADCE(); 99 } 100