[EarlyCSE] Fix handling of target memory intrinsics for CSE'ing loads.
[oota-llvm.git] / lib / Transforms / Scalar / ADCE.cpp
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.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 using namespace llvm;
30
31 #define DEBUG_TYPE "adce"
32
33 STATISTIC(NumRemoved, "Number of instructions removed");
34
35 namespace {
36 struct ADCE : public FunctionPass {
37   static char ID; // Pass identification, replacement for typeid
38   ADCE() : FunctionPass(ID) {
39     initializeADCEPass(*PassRegistry::getPassRegistry());
40   }
41
42   bool runOnFunction(Function& F) override;
43
44   void getAnalysisUsage(AnalysisUsage& AU) const override {
45     AU.setPreservesCFG();
46     AU.addPreserved<GlobalsAAWrapperPass>();
47   }
48 };
49 }
50
51 char ADCE::ID = 0;
52 INITIALIZE_PASS(ADCE, "adce", "Aggressive Dead Code Elimination", false, false)
53
54 bool ADCE::runOnFunction(Function& F) {
55   if (skipOptnoneFunction(F))
56     return false;
57
58   SmallPtrSet<Instruction*, 128> Alive;
59   SmallVector<Instruction*, 128> Worklist;
60
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()) {
65       Alive.insert(&I);
66       Worklist.push_back(&I);
67     }
68   }
69
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);
77     }
78   }
79
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();
88     }
89   }
90
91   for (Instruction *&I : Worklist) {
92     ++NumRemoved;
93     I->eraseFromParent();
94   }
95
96   return !Worklist.empty();
97 }
98
99 FunctionPass *llvm::createAggressiveDCEPass() {
100   return new ADCE();
101 }