]>
git.proxmox.com Git - rustc.git/blob - src/llvm/lib/Transforms/Scalar/ADCE.cpp
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
{
51 INITIALIZE_PASS(ADCE
, "adce", "Aggressive Dead Code Elimination", false, false)
53 bool ADCE::runOnFunction(Function
& F
) {
54 if (skipOptnoneFunction(F
))
57 SmallPtrSet
<Instruction
*, 128> alive
;
58 SmallVector
<Instruction
*, 128> worklist
;
60 // Collect the set of "root" instructions that are known live.
61 for (inst_iterator I
= inst_begin(F
), E
= inst_end(F
); I
!= E
; ++I
)
62 if (isa
<TerminatorInst
>(I
.getInstructionIterator()) ||
63 isa
<DbgInfoIntrinsic
>(I
.getInstructionIterator()) ||
64 isa
<LandingPadInst
>(I
.getInstructionIterator()) ||
65 I
->mayHaveSideEffects()) {
66 alive
.insert(I
.getInstructionIterator());
67 worklist
.push_back(I
.getInstructionIterator());
70 // Propagate liveness backwards to operands.
71 while (!worklist
.empty()) {
72 Instruction
* curr
= worklist
.pop_back_val();
73 for (Instruction::op_iterator OI
= curr
->op_begin(), OE
= curr
->op_end();
75 if (Instruction
* Inst
= dyn_cast
<Instruction
>(OI
))
76 if (alive
.insert(Inst
).second
)
77 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 (inst_iterator I
= inst_begin(F
), E
= inst_end(F
); I
!= E
; ++I
)
85 if (!alive
.count(I
.getInstructionIterator())) {
86 worklist
.push_back(I
.getInstructionIterator());
87 I
->dropAllReferences();
90 for (SmallVectorImpl
<Instruction
*>::iterator I
= worklist
.begin(),
91 E
= worklist
.end(); I
!= E
; ++I
) {
93 (*I
)->eraseFromParent();
96 return !worklist
.empty();
99 FunctionPass
*llvm::createAggressiveDCEPass() {