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