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
ADCE__anonbfc843020111::ADCE37 ADCE() : FunctionPass(ID) {
38 initializeADCEPass(*PassRegistry::getPassRegistry());
39 }
40
41 bool runOnFunction(Function& F) override;
42
getAnalysisUsage__anonbfc843020111::ADCE43 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
runOnFunction(Function & F)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
createAggressiveDCEPass()97 FunctionPass *llvm::createAggressiveDCEPass() {
98 return new ADCE();
99 }
100