1 //===- DeadMachineInstructionElim.cpp - Remove dead machine instructions --===//
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 is an extremely simple MachineInstr-level dead-code-elimination pass.
12 //===----------------------------------------------------------------------===//
14 #define DEBUG_TYPE "codegen-dce"
15 #include "llvm/CodeGen/Passes.h"
16 #include "llvm/ADT/Statistic.h"
17 #include "llvm/CodeGen/MachineFunctionPass.h"
18 #include "llvm/CodeGen/MachineRegisterInfo.h"
19 #include "llvm/Pass.h"
20 #include "llvm/Support/Debug.h"
21 #include "llvm/Support/raw_ostream.h"
22 #include "llvm/Target/TargetInstrInfo.h"
23 #include "llvm/Target/TargetMachine.h"
26 STATISTIC(NumDeletes
, "Number of dead instructions deleted");
29 class DeadMachineInstructionElim
: public MachineFunctionPass
{
30 virtual bool runOnMachineFunction(MachineFunction
&MF
);
32 const TargetRegisterInfo
*TRI
;
33 const MachineRegisterInfo
*MRI
;
34 const TargetInstrInfo
*TII
;
35 BitVector LivePhysRegs
;
38 static char ID
; // Pass identification, replacement for typeid
39 DeadMachineInstructionElim() : MachineFunctionPass(ID
) {
40 initializeDeadMachineInstructionElimPass(*PassRegistry::getPassRegistry());
44 bool isDead(const MachineInstr
*MI
) const;
47 char DeadMachineInstructionElim::ID
= 0;
48 char &llvm::DeadMachineInstructionElimID
= DeadMachineInstructionElim::ID
;
50 INITIALIZE_PASS(DeadMachineInstructionElim
, "dead-mi-elimination",
51 "Remove dead machine instructions", false, false)
53 bool DeadMachineInstructionElim::isDead(const MachineInstr
*MI
) const {
54 // Technically speaking inline asm without side effects and no defs can still
55 // be deleted. But there is so much bad inline asm code out there, we should
57 if (MI
->isInlineAsm())
60 // Don't delete instructions with side effects.
61 bool SawStore
= false;
62 if (!MI
->isSafeToMove(TII
, 0, SawStore
) && !MI
->isPHI())
65 // Examine each operand.
66 for (unsigned i
= 0, e
= MI
->getNumOperands(); i
!= e
; ++i
) {
67 const MachineOperand
&MO
= MI
->getOperand(i
);
68 if (MO
.isReg() && MO
.isDef()) {
69 unsigned Reg
= MO
.getReg();
70 if (TargetRegisterInfo::isPhysicalRegister(Reg
)) {
71 // Don't delete live physreg defs, or any reserved register defs.
72 if (LivePhysRegs
.test(Reg
) || MRI
->isReserved(Reg
))
75 if (!MRI
->use_nodbg_empty(Reg
))
76 // This def has a non-debug use. Don't delete the instruction!
82 // If there are no defs with uses, the instruction is dead.
86 bool DeadMachineInstructionElim::runOnMachineFunction(MachineFunction
&MF
) {
87 bool AnyChanges
= false;
88 MRI
= &MF
.getRegInfo();
89 TRI
= MF
.getTarget().getRegisterInfo();
90 TII
= MF
.getTarget().getInstrInfo();
92 // Loop over all instructions in all blocks, from bottom to top, so that it's
93 // more likely that chains of dependent but ultimately dead instructions will
95 for (MachineFunction::reverse_iterator I
= MF
.rbegin(), E
= MF
.rend();
97 MachineBasicBlock
*MBB
= &*I
;
99 // Start out assuming that reserved registers are live out of this block.
100 LivePhysRegs
= MRI
->getReservedRegs();
102 // Add live-ins from sucessors to LivePhysRegs. Normally, physregs are not
103 // live across blocks, but some targets (x86) can have flags live out of a
105 for (MachineBasicBlock::succ_iterator S
= MBB
->succ_begin(),
106 E
= MBB
->succ_end(); S
!= E
; S
++)
107 for (MachineBasicBlock::livein_iterator LI
= (*S
)->livein_begin();
108 LI
!= (*S
)->livein_end(); LI
++)
109 LivePhysRegs
.set(*LI
);
111 // Now scan the instructions and delete dead ones, tracking physreg
112 // liveness as we go.
113 for (MachineBasicBlock::reverse_iterator MII
= MBB
->rbegin(),
114 MIE
= MBB
->rend(); MII
!= MIE
; ) {
115 MachineInstr
*MI
= &*MII
;
117 // If the instruction is dead, delete it!
119 DEBUG(dbgs() << "DeadMachineInstructionElim: DELETING: " << *MI
);
120 // It is possible that some DBG_VALUE instructions refer to this
121 // instruction. Examine each def operand for such references;
122 // if found, mark the DBG_VALUE as undef (but don't delete it).
123 for (unsigned i
= 0, e
= MI
->getNumOperands(); i
!= e
; ++i
) {
124 const MachineOperand
&MO
= MI
->getOperand(i
);
125 if (!MO
.isReg() || !MO
.isDef())
127 unsigned Reg
= MO
.getReg();
128 if (!TargetRegisterInfo::isVirtualRegister(Reg
))
130 MachineRegisterInfo::use_iterator nextI
;
131 for (MachineRegisterInfo::use_iterator I
= MRI
->use_begin(Reg
),
132 E
= MRI
->use_end(); I
!=E
; I
=nextI
) {
133 nextI
= llvm::next(I
); // I is invalidated by the setReg
134 MachineOperand
& Use
= I
.getOperand();
135 MachineInstr
*UseMI
= Use
.getParent();
138 assert(Use
.isDebug());
139 UseMI
->getOperand(0).setReg(0U);
143 MI
->eraseFromParent();
146 // MII is now pointing to the next instruction to process,
147 // so don't increment it.
151 // Record the physreg defs.
152 for (unsigned i
= 0, e
= MI
->getNumOperands(); i
!= e
; ++i
) {
153 const MachineOperand
&MO
= MI
->getOperand(i
);
154 if (MO
.isReg() && MO
.isDef()) {
155 unsigned Reg
= MO
.getReg();
156 if (TargetRegisterInfo::isPhysicalRegister(Reg
)) {
157 // Check the subreg set, not the alias set, because a def
158 // of a super-register may still be partially live after
160 for (MCSubRegIterator
SR(Reg
, TRI
,/*IncludeSelf=*/true);
162 LivePhysRegs
.reset(*SR
);
164 } else if (MO
.isRegMask()) {
165 // Register mask of preserved registers. All clobbers are dead.
166 LivePhysRegs
.clearBitsNotInMask(MO
.getRegMask());
169 // Record the physreg uses, after the defs, in case a physreg is
170 // both defined and used in the same instruction.
171 for (unsigned i
= 0, e
= MI
->getNumOperands(); i
!= e
; ++i
) {
172 const MachineOperand
&MO
= MI
->getOperand(i
);
173 if (MO
.isReg() && MO
.isUse()) {
174 unsigned Reg
= MO
.getReg();
175 if (TargetRegisterInfo::isPhysicalRegister(Reg
)) {
176 for (MCRegAliasIterator
AI(Reg
, TRI
, true); AI
.isValid(); ++AI
)
177 LivePhysRegs
.set(*AI
);
182 // We didn't delete the current instruction, so increment MII to
188 LivePhysRegs
.clear();