1 //===- ADCE.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/Analysis/GlobalsModRef.h" 23 #include "llvm/IR/BasicBlock.h" 24 #include "llvm/IR/CFG.h" 25 #include "llvm/IR/InstIterator.h" 26 #include "llvm/IR/Instructions.h" 27 #include "llvm/IR/IntrinsicInst.h" 28 #include "llvm/Pass.h" 29 using namespace llvm; 30 31 #define DEBUG_TYPE "adce" 32 33 STATISTIC(NumRemoved, "Number of instructions removed"); 34 35 namespace { 36 struct ADCE : public FunctionPass { 37 static char ID; // Pass identification, replacement for typeid 38 ADCE() : FunctionPass(ID) { 39 initializeADCEPass(*PassRegistry::getPassRegistry()); 40 } 41 42 bool runOnFunction(Function& F) override; 43 44 void getAnalysisUsage(AnalysisUsage& AU) const override { 45 AU.setPreservesCFG(); 46 AU.addPreserved<GlobalsAAWrapperPass>(); 47 } 48 }; 49 } 50 51 char ADCE::ID = 0; 52 INITIALIZE_PASS(ADCE, "adce", "Aggressive Dead Code Elimination", false, false) 53 54 bool ADCE::runOnFunction(Function& F) { 55 if (skipOptnoneFunction(F)) 56 return false; 57 58 SmallPtrSet<Instruction*, 128> Alive; 59 SmallVector<Instruction*, 128> Worklist; 60 61 // Collect the set of "root" instructions that are known live. 62 for (Instruction &I : instructions(F)) { 63 if (isa<TerminatorInst>(I) || isa<DbgInfoIntrinsic>(I) || I.isEHPad() || 64 I.mayHaveSideEffects()) { 65 Alive.insert(&I); 66 Worklist.push_back(&I); 67 } 68 } 69 70 // Propagate liveness backwards to operands. 71 while (!Worklist.empty()) { 72 Instruction *Curr = Worklist.pop_back_val(); 73 for (Use &OI : Curr->operands()) { 74 if (Instruction *Inst = dyn_cast<Instruction>(OI)) 75 if (Alive.insert(Inst).second) 76 Worklist.push_back(Inst); 77 } 78 } 79 80 // The inverse of the live set is the dead set. These are those instructions 81 // which have no side effects and do not influence the control flow or return 82 // value of the function, and may therefore be deleted safely. 83 // NOTE: We reuse the Worklist vector here for memory efficiency. 84 for (Instruction &I : instructions(F)) { 85 if (!Alive.count(&I)) { 86 Worklist.push_back(&I); 87 I.dropAllReferences(); 88 } 89 } 90 91 for (Instruction *&I : Worklist) { 92 ++NumRemoved; 93 I->eraseFromParent(); 94 } 95 96 return !Worklist.empty(); 97 } 98 99 FunctionPass *llvm::createAggressiveDCEPass() { 100 return new ADCE(); 101 } 102