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 
19 #include "llvm/ADT/DepthFirstIterator.h"
20 #include "llvm/ADT/SmallPtrSet.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/ADT/Statistic.h"
23 #include "llvm/Analysis/GlobalsModRef.h"
24 #include "llvm/IR/BasicBlock.h"
25 #include "llvm/IR/CFG.h"
26 #include "llvm/IR/DebugInfoMetadata.h"
27 #include "llvm/IR/InstIterator.h"
28 #include "llvm/IR/Instructions.h"
29 #include "llvm/IR/IntrinsicInst.h"
30 #include "llvm/Pass.h"
31 #include "llvm/ProfileData/InstrProf.h"
32 #include "llvm/Transforms/Scalar.h"
33 using namespace llvm;
34 
35 #define DEBUG_TYPE "adce"
36 
37 STATISTIC(NumRemoved, "Number of instructions removed");
38 
39 namespace {
40 class AgggressiveDeadCodeElimination {
41   Function &F;
42   // Instructions known to be live
43   SmallPtrSet<Instruction *, 32> Alive;
44   // Instructions known to be live where we need to mark
45   // reaching definitions as live
46   SmallVector<Instruction *, 128> Worklist;
47   // Debug info scopes around a live instruction
48   SmallPtrSet<const Metadata *, 32> AliveScopes;
49 
50   void collectLiveScopes(const DILocalScope &LS);
51   void collectLiveScopes(const DILocation &DL);
52   bool isInstrumentsConstant(Instruction &I);
53 public:
54   AgggressiveDeadCodeElimination(Function &F) : F(F) {}
55   bool aggressiveDCE();
56 };
57 }
58 
59 void AgggressiveDeadCodeElimination::collectLiveScopes(
60     const DILocalScope &LS) {
61   if (!AliveScopes.insert(&LS).second)
62     return;
63 
64   if (isa<DISubprogram>(LS))
65     return;
66 
67   // Tail-recurse through the scope chain.
68   collectLiveScopes(cast<DILocalScope>(*LS.getScope()));
69 }
70 
71 void AgggressiveDeadCodeElimination::collectLiveScopes(const DILocation &DL) {
72   // Even though DILocations are not scopes, shove them into AliveScopes so we
73   // don't revisit them.
74   if (!AliveScopes.insert(&DL).second)
75     return;
76 
77   // Collect live scopes from the scope chain.
78   collectLiveScopes(*DL.getScope());
79 
80   // Tail-recurse through the inlined-at chain.
81   if (const DILocation *IA = DL.getInlinedAt())
82     collectLiveScopes(*IA);
83 }
84 
85 // Check if this instruction is a runtime call for value profiling and
86 // if it's instrumenting a constant.
87 bool AgggressiveDeadCodeElimination::isInstrumentsConstant(Instruction &I) {
88   if (CallInst *CI = dyn_cast<CallInst>(&I))
89     if (Function *Callee = CI->getCalledFunction())
90       if (Callee->getName().equals(getInstrProfValueProfFuncName()))
91         if (isa<Constant>(CI->getArgOperand(0)))
92           return true;
93   return false;
94 }
95 
96 bool AgggressiveDeadCodeElimination::aggressiveDCE() {
97 
98   // Collect the set of "root" instructions that are known live.
99   for (Instruction &I : instructions(F)) {
100     if (isa<TerminatorInst>(I) || I.isEHPad() || I.mayHaveSideEffects()) {
101       // Skip any value profile instrumentation calls if they are
102       // instrumenting constants.
103       if (isInstrumentsConstant(I))
104         continue;
105       Alive.insert(&I);
106       Worklist.push_back(&I);
107     }
108   }
109 
110   // Propagate liveness backwards to operands.  Keep track of live debug info
111   // scopes.
112   while (!Worklist.empty()) {
113     Instruction *Curr = Worklist.pop_back_val();
114 
115     // Collect the live debug info scopes attached to this instruction.
116     if (const DILocation *DL = Curr->getDebugLoc())
117       collectLiveScopes(*DL);
118 
119     for (Use &OI : Curr->operands()) {
120       if (Instruction *Inst = dyn_cast<Instruction>(OI))
121         if (Alive.insert(Inst).second)
122           Worklist.push_back(Inst);
123     }
124   }
125 
126   // The inverse of the live set is the dead set.  These are those instructions
127   // which have no side effects and do not influence the control flow or return
128   // value of the function, and may therefore be deleted safely.
129   // NOTE: We reuse the Worklist vector here for memory efficiency.
130   for (Instruction &I : instructions(F)) {
131     // Check if the instruction is alive.
132     if (Alive.count(&I))
133       continue;
134 
135     if (auto *DII = dyn_cast<DbgInfoIntrinsic>(&I)) {
136       // Check if the scope of this variable location is alive.
137       if (AliveScopes.count(DII->getDebugLoc()->getScope()))
138         continue;
139 
140       // Fallthrough and drop the intrinsic.
141       DEBUG({
142         // If intrinsic is pointing at a live SSA value, there may be an
143         // earlier optimization bug: if we know the location of the variable,
144         // why isn't the scope of the location alive?
145         if (Value *V = DII->getVariableLocation())
146           if (Instruction *II = dyn_cast<Instruction>(V))
147             if (Alive.count(II))
148               dbgs() << "Dropping debug info for " << *DII << "\n";
149       });
150     }
151 
152     // Prepare to delete.
153     Worklist.push_back(&I);
154     I.dropAllReferences();
155   }
156 
157   for (Instruction *&I : Worklist) {
158     ++NumRemoved;
159     I->eraseFromParent();
160   }
161 
162   return !Worklist.empty();
163 }
164 
165 PreservedAnalyses ADCEPass::run(Function &F, FunctionAnalysisManager &) {
166   if (!AgggressiveDeadCodeElimination(F).aggressiveDCE())
167     return PreservedAnalyses::all();
168 
169   // FIXME: This should also 'preserve the CFG'.
170   auto PA = PreservedAnalyses();
171   PA.preserve<GlobalsAA>();
172   return PA;
173 }
174 
175 namespace {
176 struct ADCELegacyPass : public FunctionPass {
177   static char ID; // Pass identification, replacement for typeid
178   ADCELegacyPass() : FunctionPass(ID) {
179     initializeADCELegacyPassPass(*PassRegistry::getPassRegistry());
180   }
181 
182   bool runOnFunction(Function &F) override {
183     if (skipFunction(F))
184       return false;
185     return AgggressiveDeadCodeElimination(F).aggressiveDCE();
186   }
187 
188   void getAnalysisUsage(AnalysisUsage &AU) const override {
189     AU.setPreservesCFG();
190     AU.addPreserved<GlobalsAAWrapperPass>();
191   }
192 };
193 }
194 
195 char ADCELegacyPass::ID = 0;
196 INITIALIZE_PASS(ADCELegacyPass, "adce", "Aggressive Dead Code Elimination",
197                 false, false)
198 
199 FunctionPass *llvm::createAggressiveDCEPass() { return new ADCELegacyPass(); }
200