1 //===-- DelaySlotFiller.cpp - SPARC delay slot filler ---------------------===//
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 a simple local pass that attempts to fill delay slots with useful
11 // instructions. If no instructions can be moved into the delay slot, then a
12 // NOP is placed.
13 //===----------------------------------------------------------------------===//
14
15 #define DEBUG_TYPE "delay-slot-filler"
16 #include "Sparc.h"
17 #include "llvm/CodeGen/MachineFunctionPass.h"
18 #include "llvm/CodeGen/MachineInstrBuilder.h"
19 #include "llvm/Support/CommandLine.h"
20 #include "llvm/Target/TargetMachine.h"
21 #include "llvm/Target/TargetInstrInfo.h"
22 #include "llvm/Target/TargetRegisterInfo.h"
23 #include "llvm/ADT/SmallSet.h"
24 #include "llvm/ADT/Statistic.h"
25
26 using namespace llvm;
27
28 STATISTIC(FilledSlots, "Number of delay slots filled");
29
30 static cl::opt<bool> DisableDelaySlotFiller(
31 "disable-sparc-delay-filler",
32 cl::init(false),
33 cl::desc("Disable the Sparc delay slot filler."),
34 cl::Hidden);
35
36 namespace {
37 struct Filler : public MachineFunctionPass {
38 /// Target machine description which we query for reg. names, data
39 /// layout, etc.
40 ///
41 TargetMachine &TM;
42 const TargetInstrInfo *TII;
43
44 static char ID;
Filler__anon64e2ec450111::Filler45 Filler(TargetMachine &tm)
46 : MachineFunctionPass(ID), TM(tm), TII(tm.getInstrInfo()) { }
47
getPassName__anon64e2ec450111::Filler48 virtual const char *getPassName() const {
49 return "SPARC Delay Slot Filler";
50 }
51
52 bool runOnMachineBasicBlock(MachineBasicBlock &MBB);
runOnMachineFunction__anon64e2ec450111::Filler53 bool runOnMachineFunction(MachineFunction &F) {
54 bool Changed = false;
55 for (MachineFunction::iterator FI = F.begin(), FE = F.end();
56 FI != FE; ++FI)
57 Changed |= runOnMachineBasicBlock(*FI);
58 return Changed;
59 }
60
61 bool isDelayFiller(MachineBasicBlock &MBB,
62 MachineBasicBlock::iterator candidate);
63
64 void insertCallUses(MachineBasicBlock::iterator MI,
65 SmallSet<unsigned, 32>& RegUses);
66
67 void insertDefsUses(MachineBasicBlock::iterator MI,
68 SmallSet<unsigned, 32>& RegDefs,
69 SmallSet<unsigned, 32>& RegUses);
70
71 bool IsRegInSet(SmallSet<unsigned, 32>& RegSet,
72 unsigned Reg);
73
74 bool delayHasHazard(MachineBasicBlock::iterator candidate,
75 bool &sawLoad, bool &sawStore,
76 SmallSet<unsigned, 32> &RegDefs,
77 SmallSet<unsigned, 32> &RegUses);
78
79 MachineBasicBlock::iterator
80 findDelayInstr(MachineBasicBlock &MBB, MachineBasicBlock::iterator slot);
81
82 bool needsUnimp(MachineBasicBlock::iterator I, unsigned &StructSize);
83
84 };
85 char Filler::ID = 0;
86 } // end of anonymous namespace
87
88 /// createSparcDelaySlotFillerPass - Returns a pass that fills in delay
89 /// slots in Sparc MachineFunctions
90 ///
createSparcDelaySlotFillerPass(TargetMachine & tm)91 FunctionPass *llvm::createSparcDelaySlotFillerPass(TargetMachine &tm) {
92 return new Filler(tm);
93 }
94
95
96 /// runOnMachineBasicBlock - Fill in delay slots for the given basic block.
97 /// We assume there is only one delay slot per delayed instruction.
98 ///
runOnMachineBasicBlock(MachineBasicBlock & MBB)99 bool Filler::runOnMachineBasicBlock(MachineBasicBlock &MBB) {
100 bool Changed = false;
101
102 for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ++I)
103 if (I->hasDelaySlot()) {
104 MachineBasicBlock::iterator D = MBB.end();
105 MachineBasicBlock::iterator J = I;
106
107 if (!DisableDelaySlotFiller)
108 D = findDelayInstr(MBB, I);
109
110 ++FilledSlots;
111 Changed = true;
112
113 if (D == MBB.end())
114 BuildMI(MBB, ++J, I->getDebugLoc(), TII->get(SP::NOP));
115 else
116 MBB.splice(++J, &MBB, D);
117 unsigned structSize = 0;
118 if (needsUnimp(I, structSize)) {
119 MachineBasicBlock::iterator J = I;
120 ++J; //skip the delay filler.
121 BuildMI(MBB, ++J, I->getDebugLoc(),
122 TII->get(SP::UNIMP)).addImm(structSize);
123 }
124 }
125 return Changed;
126 }
127
128 MachineBasicBlock::iterator
findDelayInstr(MachineBasicBlock & MBB,MachineBasicBlock::iterator slot)129 Filler::findDelayInstr(MachineBasicBlock &MBB,
130 MachineBasicBlock::iterator slot)
131 {
132 SmallSet<unsigned, 32> RegDefs;
133 SmallSet<unsigned, 32> RegUses;
134 bool sawLoad = false;
135 bool sawStore = false;
136
137 MachineBasicBlock::iterator I = slot;
138
139 if (slot->getOpcode() == SP::RET)
140 return MBB.end();
141
142 if (slot->getOpcode() == SP::RETL) {
143 --I;
144 if (I->getOpcode() != SP::RESTORErr)
145 return MBB.end();
146 //change retl to ret
147 slot->setDesc(TII->get(SP::RET));
148 return I;
149 }
150
151 //Call's delay filler can def some of call's uses.
152 if (slot->isCall())
153 insertCallUses(slot, RegUses);
154 else
155 insertDefsUses(slot, RegDefs, RegUses);
156
157 bool done = false;
158
159 while (!done) {
160 done = (I == MBB.begin());
161
162 if (!done)
163 --I;
164
165 // skip debug value
166 if (I->isDebugValue())
167 continue;
168
169
170 if (I->hasUnmodeledSideEffects()
171 || I->isInlineAsm()
172 || I->isLabel()
173 || I->hasDelaySlot()
174 || isDelayFiller(MBB, I))
175 break;
176
177 if (delayHasHazard(I, sawLoad, sawStore, RegDefs, RegUses)) {
178 insertDefsUses(I, RegDefs, RegUses);
179 continue;
180 }
181
182 return I;
183 }
184 return MBB.end();
185 }
186
delayHasHazard(MachineBasicBlock::iterator candidate,bool & sawLoad,bool & sawStore,SmallSet<unsigned,32> & RegDefs,SmallSet<unsigned,32> & RegUses)187 bool Filler::delayHasHazard(MachineBasicBlock::iterator candidate,
188 bool &sawLoad,
189 bool &sawStore,
190 SmallSet<unsigned, 32> &RegDefs,
191 SmallSet<unsigned, 32> &RegUses)
192 {
193
194 if (candidate->isImplicitDef() || candidate->isKill())
195 return true;
196
197 if (candidate->mayLoad()) {
198 sawLoad = true;
199 if (sawStore)
200 return true;
201 }
202
203 if (candidate->mayStore()) {
204 if (sawStore)
205 return true;
206 sawStore = true;
207 if (sawLoad)
208 return true;
209 }
210
211 for (unsigned i = 0, e = candidate->getNumOperands(); i!= e; ++i) {
212 const MachineOperand &MO = candidate->getOperand(i);
213 if (!MO.isReg())
214 continue; // skip
215
216 unsigned Reg = MO.getReg();
217
218 if (MO.isDef()) {
219 //check whether Reg is defined or used before delay slot.
220 if (IsRegInSet(RegDefs, Reg) || IsRegInSet(RegUses, Reg))
221 return true;
222 }
223 if (MO.isUse()) {
224 //check whether Reg is defined before delay slot.
225 if (IsRegInSet(RegDefs, Reg))
226 return true;
227 }
228 }
229 return false;
230 }
231
232
insertCallUses(MachineBasicBlock::iterator MI,SmallSet<unsigned,32> & RegUses)233 void Filler::insertCallUses(MachineBasicBlock::iterator MI,
234 SmallSet<unsigned, 32>& RegUses)
235 {
236
237 switch(MI->getOpcode()) {
238 default: llvm_unreachable("Unknown opcode.");
239 case SP::CALL: break;
240 case SP::JMPLrr:
241 case SP::JMPLri:
242 assert(MI->getNumOperands() >= 2);
243 const MachineOperand &Reg = MI->getOperand(0);
244 assert(Reg.isReg() && "JMPL first operand is not a register.");
245 assert(Reg.isUse() && "JMPL first operand is not a use.");
246 RegUses.insert(Reg.getReg());
247
248 const MachineOperand &RegOrImm = MI->getOperand(1);
249 if (RegOrImm.isImm())
250 break;
251 assert(RegOrImm.isReg() && "JMPLrr second operand is not a register.");
252 assert(RegOrImm.isUse() && "JMPLrr second operand is not a use.");
253 RegUses.insert(RegOrImm.getReg());
254 break;
255 }
256 }
257
258 //Insert Defs and Uses of MI into the sets RegDefs and RegUses.
insertDefsUses(MachineBasicBlock::iterator MI,SmallSet<unsigned,32> & RegDefs,SmallSet<unsigned,32> & RegUses)259 void Filler::insertDefsUses(MachineBasicBlock::iterator MI,
260 SmallSet<unsigned, 32>& RegDefs,
261 SmallSet<unsigned, 32>& RegUses)
262 {
263 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
264 const MachineOperand &MO = MI->getOperand(i);
265 if (!MO.isReg())
266 continue;
267
268 unsigned Reg = MO.getReg();
269 if (Reg == 0)
270 continue;
271 if (MO.isDef())
272 RegDefs.insert(Reg);
273 if (MO.isUse())
274 RegUses.insert(Reg);
275
276 }
277 }
278
279 //returns true if the Reg or its alias is in the RegSet.
IsRegInSet(SmallSet<unsigned,32> & RegSet,unsigned Reg)280 bool Filler::IsRegInSet(SmallSet<unsigned, 32>& RegSet, unsigned Reg)
281 {
282 // Check Reg and all aliased Registers.
283 for (MCRegAliasIterator AI(Reg, TM.getRegisterInfo(), true);
284 AI.isValid(); ++AI)
285 if (RegSet.count(*AI))
286 return true;
287 return false;
288 }
289
290 // return true if the candidate is a delay filler.
isDelayFiller(MachineBasicBlock & MBB,MachineBasicBlock::iterator candidate)291 bool Filler::isDelayFiller(MachineBasicBlock &MBB,
292 MachineBasicBlock::iterator candidate)
293 {
294 if (candidate == MBB.begin())
295 return false;
296 if (candidate->getOpcode() == SP::UNIMP)
297 return true;
298 --candidate;
299 return candidate->hasDelaySlot();
300 }
301
needsUnimp(MachineBasicBlock::iterator I,unsigned & StructSize)302 bool Filler::needsUnimp(MachineBasicBlock::iterator I, unsigned &StructSize)
303 {
304 if (!I->isCall())
305 return false;
306
307 unsigned structSizeOpNum = 0;
308 switch (I->getOpcode()) {
309 default: llvm_unreachable("Unknown call opcode.");
310 case SP::CALL: structSizeOpNum = 1; break;
311 case SP::JMPLrr:
312 case SP::JMPLri: structSizeOpNum = 2; break;
313 }
314
315 const MachineOperand &MO = I->getOperand(structSizeOpNum);
316 if (!MO.isImm())
317 return false;
318 StructSize = MO.getImm();
319 return true;
320 }
321