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/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/InstIterator.h"
26 #include "llvm/IR/Instructions.h"
27 #include "llvm/IR/IntrinsicInst.h"
28 #include "llvm/Pass.h"
29 #include "llvm/Transforms/Scalar.h"
32 #define DEBUG_TYPE "adce"
34 STATISTIC(NumRemoved, "Number of instructions removed");
36 static bool aggressiveDCE(Function& F) {
37 SmallPtrSet<Instruction*, 128> Alive;
38 SmallVector<Instruction*, 128> Worklist;
40 // Collect the set of "root" instructions that are known live.
41 for (Instruction &I : instructions(F)) {
42 if (isa<TerminatorInst>(I) || isa<DbgInfoIntrinsic>(I) || I.isEHPad() ||
43 I.mayHaveSideEffects()) {
45 Worklist.push_back(&I);
49 // Propagate liveness backwards to operands.
50 while (!Worklist.empty()) {
51 Instruction *Curr = Worklist.pop_back_val();
52 for (Use &OI : Curr->operands()) {
53 if (Instruction *Inst = dyn_cast<Instruction>(OI))
54 if (Alive.insert(Inst).second)
55 Worklist.push_back(Inst);
59 // The inverse of the live set is the dead set. These are those instructions
60 // which have no side effects and do not influence the control flow or return
61 // value of the function, and may therefore be deleted safely.
62 // NOTE: We reuse the Worklist vector here for memory efficiency.
63 for (Instruction &I : instructions(F)) {
64 if (!Alive.count(&I)) {
65 Worklist.push_back(&I);
66 I.dropAllReferences();
70 for (Instruction *&I : Worklist) {
75 return !Worklist.empty();
78 PreservedAnalyses ADCEPass::run(Function &F) {
80 return PreservedAnalyses::none();
81 return PreservedAnalyses::all();
85 struct ADCELegacyPass : public FunctionPass {
86 static char ID; // Pass identification, replacement for typeid
87 ADCELegacyPass() : FunctionPass(ID) {
88 initializeADCELegacyPassPass(*PassRegistry::getPassRegistry());
91 bool runOnFunction(Function& F) override {
92 if (skipOptnoneFunction(F))
94 return aggressiveDCE(F);
97 void getAnalysisUsage(AnalysisUsage& AU) const override {
99 AU.addPreserved<GlobalsAAWrapperPass>();
104 char ADCELegacyPass::ID = 0;
105 INITIALIZE_PASS(ADCELegacyPass, "adce", "Aggressive Dead Code Elimination",
108 FunctionPass *llvm::createAggressiveDCEPass() { return new ADCELegacyPass(); }