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