1 //===- DCE.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/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"
30 #define DEBUG_TYPE "adce"
32 STATISTIC(NumRemoved, "Number of instructions removed");
35 struct ADCE : public FunctionPass {
36 static char ID; // Pass identification, replacement for typeid
37 ADCE() : FunctionPass(ID) {
38 initializeADCEPass(*PassRegistry::getPassRegistry());
41 bool runOnFunction(Function& F) override;
43 void getAnalysisUsage(AnalysisUsage& AU) const override {
50 INITIALIZE_PASS(ADCE, "adce", "Aggressive Dead Code Elimination", false, false)
52 bool ADCE::runOnFunction(Function& F) {
53 if (skipOptnoneFunction(F))
56 SmallPtrSet<Instruction*, 128> Alive;
57 SmallVector<Instruction*, 128> Worklist;
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()) {
64 Worklist.push_back(&I);
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);
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();
89 for (Instruction *&I : Worklist) {
94 return !Worklist.empty();
97 FunctionPass *llvm::createAggressiveDCEPass() {