1 //===- ADCE.cpp - Code to perform dead code elimination -------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
15 //===----------------------------------------------------------------------===//
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"
31 #define DEBUG_TYPE "adce"
33 STATISTIC(NumRemoved, "Number of instructions removed");
36 struct ADCE : public FunctionPass {
37 static char ID; // Pass identification, replacement for typeid
38 ADCE() : FunctionPass(ID) {
39 initializeADCEPass(*PassRegistry::getPassRegistry());
42 bool runOnFunction(Function& F) override;
44 void getAnalysisUsage(AnalysisUsage& AU) const override {
46 AU.addPreserved<GlobalsAAWrapperPass>();
52 INITIALIZE_PASS(ADCE, "adce", "Aggressive Dead Code Elimination", false, false)
54 bool ADCE::runOnFunction(Function& F) {
55 if (skipOptnoneFunction(F))
58 SmallPtrSet<Instruction*, 128> Alive;
59 SmallVector<Instruction*, 128> Worklist;
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()) {
66 Worklist.push_back(&I);
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);
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();
91 for (Instruction *&I : Worklist) {
96 return !Worklist.empty();
99 FunctionPass *llvm::createAggressiveDCEPass() {