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