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
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
|
//==--- MachineLateInstrsCleanup.cpp - Late Instructions Cleanup Pass -----===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This simple pass removes any identical and redundant immediate or address
// loads to the same register. The immediate loads removed can originally be
// the result of rematerialization, while the addresses are redundant frame
// addressing anchor points created during Frame Indices elimination.
//
//===----------------------------------------------------------------------===//
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
using namespace llvm;
#define DEBUG_TYPE "machine-latecleanup"
STATISTIC(NumRemoved, "Number of redundant instructions removed.");
namespace {
class MachineLateInstrsCleanup : public MachineFunctionPass {
const TargetRegisterInfo *TRI = nullptr;
const TargetInstrInfo *TII = nullptr;
// Data structures to map regs to their definitions and kills per MBB.
struct Reg2MIMap : public SmallDenseMap<Register, MachineInstr *> {
bool hasIdentical(Register Reg, MachineInstr *ArgMI) {
MachineInstr *MI = lookup(Reg);
return MI && MI->isIdenticalTo(*ArgMI);
}
};
std::vector<Reg2MIMap> RegDefs;
std::vector<Reg2MIMap> RegKills;
// Walk through the instructions in MBB and remove any redundant
// instructions.
bool processBlock(MachineBasicBlock *MBB);
void removeRedundantDef(MachineInstr *MI);
void clearKillsForDef(Register Reg, MachineBasicBlock *MBB,
MachineBasicBlock::iterator I,
BitVector &VisitedPreds);
public:
static char ID; // Pass identification, replacement for typeid
MachineLateInstrsCleanup() : MachineFunctionPass(ID) {
initializeMachineLateInstrsCleanupPass(*PassRegistry::getPassRegistry());
}
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.setPreservesCFG();
MachineFunctionPass::getAnalysisUsage(AU);
}
bool runOnMachineFunction(MachineFunction &MF) override;
MachineFunctionProperties getRequiredProperties() const override {
return MachineFunctionProperties().set(
MachineFunctionProperties::Property::NoVRegs);
}
};
} // end anonymous namespace
char MachineLateInstrsCleanup::ID = 0;
char &llvm::MachineLateInstrsCleanupID = MachineLateInstrsCleanup::ID;
INITIALIZE_PASS(MachineLateInstrsCleanup, DEBUG_TYPE,
"Machine Late Instructions Cleanup Pass", false, false)
bool MachineLateInstrsCleanup::runOnMachineFunction(MachineFunction &MF) {
if (skipFunction(MF.getFunction()))
return false;
TRI = MF.getSubtarget().getRegisterInfo();
TII = MF.getSubtarget().getInstrInfo();
RegDefs.clear();
RegDefs.resize(MF.getNumBlockIDs());
RegKills.clear();
RegKills.resize(MF.getNumBlockIDs());
// Visit all MBBs in an order that maximises the reuse from predecessors.
bool Changed = false;
ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
for (MachineBasicBlock *MBB : RPOT)
Changed |= processBlock(MBB);
return Changed;
}
// Clear any previous kill flag on Reg found before I in MBB. Walk backwards
// in MBB and if needed continue in predecessors until a use/def of Reg is
// encountered. This seems to be faster in practice than tracking kill flags
// in a map.
void MachineLateInstrsCleanup::
clearKillsForDef(Register Reg, MachineBasicBlock *MBB,
MachineBasicBlock::iterator I,
BitVector &VisitedPreds) {
VisitedPreds.set(MBB->getNumber());
// Kill flag in MBB
if (MachineInstr *KillMI = RegKills[MBB->getNumber()].lookup(Reg)) {
KillMI->clearRegisterKills(Reg, TRI);
return;
}
// Def in MBB (missing kill flag)
if (MachineInstr *DefMI = RegDefs[MBB->getNumber()].lookup(Reg))
if (DefMI->getParent() == MBB)
return;
// If an earlier def is not in MBB, continue in predecessors.
if (!MBB->isLiveIn(Reg))
MBB->addLiveIn(Reg);
assert(!MBB->pred_empty() && "Predecessor def not found!");
for (MachineBasicBlock *Pred : MBB->predecessors())
if (!VisitedPreds.test(Pred->getNumber()))
clearKillsForDef(Reg, Pred, Pred->end(), VisitedPreds);
}
void MachineLateInstrsCleanup::removeRedundantDef(MachineInstr *MI) {
Register Reg = MI->getOperand(0).getReg();
BitVector VisitedPreds(MI->getMF()->getNumBlockIDs());
clearKillsForDef(Reg, MI->getParent(), MI->getIterator(), VisitedPreds);
MI->eraseFromParent();
++NumRemoved;
}
// Return true if MI is a potential candidate for reuse/removal and if so
// also the register it defines in DefedReg. A candidate is a simple
// instruction that does not touch memory, has only one register definition
// and the only reg it may use is FrameReg. Typically this is an immediate
// load or a load-address instruction.
static bool isCandidate(const MachineInstr *MI, Register &DefedReg,
Register FrameReg) {
DefedReg = MCRegister::NoRegister;
bool SawStore = true;
if (!MI->isSafeToMove(nullptr, SawStore) || MI->isImplicitDef() ||
MI->isInlineAsm())
return false;
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
const MachineOperand &MO = MI->getOperand(i);
if (MO.isReg()) {
if (MO.isDef()) {
if (i == 0 && !MO.isImplicit() && !MO.isDead())
DefedReg = MO.getReg();
else
return false;
} else if (MO.getReg() && MO.getReg() != FrameReg)
return false;
} else if (!(MO.isImm() || MO.isCImm() || MO.isFPImm() || MO.isCPI() ||
MO.isGlobal() || MO.isSymbol()))
return false;
}
return DefedReg.isValid();
}
bool MachineLateInstrsCleanup::processBlock(MachineBasicBlock *MBB) {
bool Changed = false;
Reg2MIMap &MBBDefs = RegDefs[MBB->getNumber()];
Reg2MIMap &MBBKills = RegKills[MBB->getNumber()];
// Find reusable definitions in the predecessor(s).
if (!MBB->pred_empty() && !MBB->isEHPad() &&
!MBB->isInlineAsmBrIndirectTarget()) {
MachineBasicBlock *FirstPred = *MBB->pred_begin();
for (auto [Reg, DefMI] : RegDefs[FirstPred->getNumber()])
if (llvm::all_of(
drop_begin(MBB->predecessors()),
[&, &Reg = Reg, &DefMI = DefMI](const MachineBasicBlock *Pred) {
return RegDefs[Pred->getNumber()].hasIdentical(Reg, DefMI);
})) {
MBBDefs[Reg] = DefMI;
LLVM_DEBUG(dbgs() << "Reusable instruction from pred(s): in "
<< printMBBReference(*MBB) << ": " << *DefMI;);
}
}
// Process MBB.
MachineFunction *MF = MBB->getParent();
const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
Register FrameReg = TRI->getFrameRegister(*MF);
for (MachineInstr &MI : llvm::make_early_inc_range(*MBB)) {
// If FrameReg is modified, no previous load-address instructions (using
// it) are valid.
if (MI.modifiesRegister(FrameReg, TRI)) {
MBBDefs.clear();
MBBKills.clear();
continue;
}
Register DefedReg;
bool IsCandidate = isCandidate(&MI, DefedReg, FrameReg);
// Check for an earlier identical and reusable instruction.
if (IsCandidate && MBBDefs.hasIdentical(DefedReg, &MI)) {
LLVM_DEBUG(dbgs() << "Removing redundant instruction in "
<< printMBBReference(*MBB) << ": " << MI;);
removeRedundantDef(&MI);
Changed = true;
continue;
}
// Clear any entries in map that MI clobbers.
for (auto DefI : llvm::make_early_inc_range(MBBDefs)) {
Register Reg = DefI.first;
if (MI.modifiesRegister(Reg, TRI)) {
MBBDefs.erase(Reg);
MBBKills.erase(Reg);
} else if (MI.findRegisterUseOperandIdx(Reg, true /*isKill*/, TRI) != -1)
// Keep track of register kills.
MBBKills[Reg] = &MI;
}
// Record this MI for potential later reuse.
if (IsCandidate) {
LLVM_DEBUG(dbgs() << "Found interesting instruction in "
<< printMBBReference(*MBB) << ": " << MI;);
MBBDefs[DefedReg] = &MI;
assert(!MBBKills.count(DefedReg) && "Should already have been removed.");
}
}
return Changed;
}
|