1 //===- DeadMachineInstructionElim.cpp - Remove dead machine instructions --===//
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 is an extremely simple MachineInstr-level dead-code-elimination pass.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #define DEBUG_TYPE "codegen-dce"
15 #include "llvm/CodeGen/Passes.h"
16 #include "llvm/Pass.h"
17 #include "llvm/CodeGen/MachineFunctionPass.h"
18 #include "llvm/CodeGen/MachineRegisterInfo.h"
19 #include "llvm/Support/Debug.h"
20 #include "llvm/Support/raw_ostream.h"
21 #include "llvm/Target/TargetInstrInfo.h"
22 #include "llvm/Target/TargetMachine.h"
23 #include "llvm/ADT/Statistic.h"
24 using namespace llvm;
25
26 STATISTIC(NumDeletes, "Number of dead instructions deleted");
27
28 namespace {
29 class DeadMachineInstructionElim : public MachineFunctionPass {
30 virtual bool runOnMachineFunction(MachineFunction &MF);
31
32 const TargetRegisterInfo *TRI;
33 const MachineRegisterInfo *MRI;
34 const TargetInstrInfo *TII;
35 BitVector LivePhysRegs;
36 BitVector ReservedRegs;
37
38 public:
39 static char ID; // Pass identification, replacement for typeid
DeadMachineInstructionElim()40 DeadMachineInstructionElim() : MachineFunctionPass(ID) {
41 initializeDeadMachineInstructionElimPass(*PassRegistry::getPassRegistry());
42 }
43
44 private:
45 bool isDead(const MachineInstr *MI) const;
46 };
47 }
48 char DeadMachineInstructionElim::ID = 0;
49 char &llvm::DeadMachineInstructionElimID = DeadMachineInstructionElim::ID;
50
51 INITIALIZE_PASS(DeadMachineInstructionElim, "dead-mi-elimination",
52 "Remove dead machine instructions", false, false)
53
isDead(const MachineInstr * MI) const54 bool DeadMachineInstructionElim::isDead(const MachineInstr *MI) const {
55 // Technically speaking inline asm without side effects and no defs can still
56 // be deleted. But there is so much bad inline asm code out there, we should
57 // let them be.
58 if (MI->isInlineAsm())
59 return false;
60
61 // Don't delete instructions with side effects.
62 bool SawStore = false;
63 if (!MI->isSafeToMove(TII, 0, SawStore) && !MI->isPHI())
64 return false;
65
66 // Examine each operand.
67 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
68 const MachineOperand &MO = MI->getOperand(i);
69 if (MO.isReg() && MO.isDef()) {
70 unsigned Reg = MO.getReg();
71 if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
72 // Don't delete live physreg defs, or any reserved register defs.
73 if (LivePhysRegs.test(Reg) || ReservedRegs.test(Reg))
74 return false;
75 } else {
76 if (!MRI->use_nodbg_empty(Reg))
77 // This def has a non-debug use. Don't delete the instruction!
78 return false;
79 }
80 }
81 }
82
83 // If there are no defs with uses, the instruction is dead.
84 return true;
85 }
86
runOnMachineFunction(MachineFunction & MF)87 bool DeadMachineInstructionElim::runOnMachineFunction(MachineFunction &MF) {
88 bool AnyChanges = false;
89 MRI = &MF.getRegInfo();
90 TRI = MF.getTarget().getRegisterInfo();
91 TII = MF.getTarget().getInstrInfo();
92
93 // Treat reserved registers as always live.
94 ReservedRegs = TRI->getReservedRegs(MF);
95
96 // Loop over all instructions in all blocks, from bottom to top, so that it's
97 // more likely that chains of dependent but ultimately dead instructions will
98 // be cleaned up.
99 for (MachineFunction::reverse_iterator I = MF.rbegin(), E = MF.rend();
100 I != E; ++I) {
101 MachineBasicBlock *MBB = &*I;
102
103 // Start out assuming that reserved registers are live out of this block.
104 LivePhysRegs = ReservedRegs;
105
106 // Also add any explicit live-out physregs for this block.
107 if (!MBB->empty() && MBB->back().isReturn())
108 for (MachineRegisterInfo::liveout_iterator LOI = MRI->liveout_begin(),
109 LOE = MRI->liveout_end(); LOI != LOE; ++LOI) {
110 unsigned Reg = *LOI;
111 if (TargetRegisterInfo::isPhysicalRegister(Reg))
112 LivePhysRegs.set(Reg);
113 }
114
115 // Add live-ins from sucessors to LivePhysRegs. Normally, physregs are not
116 // live across blocks, but some targets (x86) can have flags live out of a
117 // block.
118 for (MachineBasicBlock::succ_iterator S = MBB->succ_begin(),
119 E = MBB->succ_end(); S != E; S++)
120 for (MachineBasicBlock::livein_iterator LI = (*S)->livein_begin();
121 LI != (*S)->livein_end(); LI++)
122 LivePhysRegs.set(*LI);
123
124 // Now scan the instructions and delete dead ones, tracking physreg
125 // liveness as we go.
126 for (MachineBasicBlock::reverse_iterator MII = MBB->rbegin(),
127 MIE = MBB->rend(); MII != MIE; ) {
128 MachineInstr *MI = &*MII;
129
130 // If the instruction is dead, delete it!
131 if (isDead(MI)) {
132 DEBUG(dbgs() << "DeadMachineInstructionElim: DELETING: " << *MI);
133 // It is possible that some DBG_VALUE instructions refer to this
134 // instruction. Examine each def operand for such references;
135 // if found, mark the DBG_VALUE as undef (but don't delete it).
136 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
137 const MachineOperand &MO = MI->getOperand(i);
138 if (!MO.isReg() || !MO.isDef())
139 continue;
140 unsigned Reg = MO.getReg();
141 if (!TargetRegisterInfo::isVirtualRegister(Reg))
142 continue;
143 MachineRegisterInfo::use_iterator nextI;
144 for (MachineRegisterInfo::use_iterator I = MRI->use_begin(Reg),
145 E = MRI->use_end(); I!=E; I=nextI) {
146 nextI = llvm::next(I); // I is invalidated by the setReg
147 MachineOperand& Use = I.getOperand();
148 MachineInstr *UseMI = Use.getParent();
149 if (UseMI==MI)
150 continue;
151 assert(Use.isDebug());
152 UseMI->getOperand(0).setReg(0U);
153 }
154 }
155 AnyChanges = true;
156 MI->eraseFromParent();
157 ++NumDeletes;
158 MIE = MBB->rend();
159 // MII is now pointing to the next instruction to process,
160 // so don't increment it.
161 continue;
162 }
163
164 // Record the physreg defs.
165 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
166 const MachineOperand &MO = MI->getOperand(i);
167 if (MO.isReg() && MO.isDef()) {
168 unsigned Reg = MO.getReg();
169 if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
170 LivePhysRegs.reset(Reg);
171 // Check the subreg set, not the alias set, because a def
172 // of a super-register may still be partially live after
173 // this def.
174 for (MCSubRegIterator SR(Reg, TRI); SR.isValid(); ++SR)
175 LivePhysRegs.reset(*SR);
176 }
177 } else if (MO.isRegMask()) {
178 // Register mask of preserved registers. All clobbers are dead.
179 LivePhysRegs.clearBitsNotInMask(MO.getRegMask());
180 }
181 }
182 // Record the physreg uses, after the defs, in case a physreg is
183 // both defined and used in the same instruction.
184 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
185 const MachineOperand &MO = MI->getOperand(i);
186 if (MO.isReg() && MO.isUse()) {
187 unsigned Reg = MO.getReg();
188 if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
189 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
190 LivePhysRegs.set(*AI);
191 }
192 }
193 }
194
195 // We didn't delete the current instruction, so increment MII to
196 // the next one.
197 ++MII;
198 }
199 }
200
201 LivePhysRegs.clear();
202 return AnyChanges;
203 }
204