1 //===-- DelaySlotFiller.cpp - SPARC delay slot filler ---------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This is a simple local pass that attempts to fill delay slots with useful
10 // instructions. If no instructions can be moved into the delay slot, then a
11 // NOP is placed.
12 //===----------------------------------------------------------------------===//
13
14 #include "Sparc.h"
15 #include "SparcSubtarget.h"
16 #include "llvm/ADT/SmallSet.h"
17 #include "llvm/ADT/Statistic.h"
18 #include "llvm/CodeGen/MachineFunctionPass.h"
19 #include "llvm/CodeGen/MachineInstrBuilder.h"
20 #include "llvm/CodeGen/MachineRegisterInfo.h"
21 #include "llvm/CodeGen/TargetInstrInfo.h"
22 #include "llvm/CodeGen/TargetRegisterInfo.h"
23 #include "llvm/Support/CommandLine.h"
24 #include "llvm/Target/TargetMachine.h"
25
26 using namespace llvm;
27
28 #define DEBUG_TYPE "delay-slot-filler"
29
30 STATISTIC(FilledSlots, "Number of delay slots filled");
31
32 static cl::opt<bool> DisableDelaySlotFiller(
33 "disable-sparc-delay-filler",
34 cl::init(false),
35 cl::desc("Disable the Sparc delay slot filler."),
36 cl::Hidden);
37
38 namespace {
39 struct Filler : public MachineFunctionPass {
40 const SparcSubtarget *Subtarget = nullptr;
41
42 static char ID;
Filler__anonbbd962150111::Filler43 Filler() : MachineFunctionPass(ID) {}
44
getPassName__anonbbd962150111::Filler45 StringRef getPassName() const override { return "SPARC Delay Slot Filler"; }
46
47 bool runOnMachineBasicBlock(MachineBasicBlock &MBB);
runOnMachineFunction__anonbbd962150111::Filler48 bool runOnMachineFunction(MachineFunction &F) override {
49 bool Changed = false;
50 Subtarget = &F.getSubtarget<SparcSubtarget>();
51
52 // This pass invalidates liveness information when it reorders
53 // instructions to fill delay slot.
54 F.getRegInfo().invalidateLiveness();
55
56 for (MachineFunction::iterator FI = F.begin(), FE = F.end();
57 FI != FE; ++FI)
58 Changed |= runOnMachineBasicBlock(*FI);
59 return Changed;
60 }
61
getRequiredProperties__anonbbd962150111::Filler62 MachineFunctionProperties getRequiredProperties() const override {
63 return MachineFunctionProperties().set(
64 MachineFunctionProperties::Property::NoVRegs);
65 }
66
67 void insertCallDefsUses(MachineBasicBlock::iterator MI,
68 SmallSet<unsigned, 32>& RegDefs,
69 SmallSet<unsigned, 32>& RegUses);
70
71 void insertDefsUses(MachineBasicBlock::iterator MI,
72 SmallSet<unsigned, 32>& RegDefs,
73 SmallSet<unsigned, 32>& RegUses);
74
75 bool IsRegInSet(SmallSet<unsigned, 32>& RegSet,
76 unsigned Reg);
77
78 bool delayHasHazard(MachineBasicBlock::iterator candidate,
79 bool &sawLoad, bool &sawStore,
80 SmallSet<unsigned, 32> &RegDefs,
81 SmallSet<unsigned, 32> &RegUses);
82
83 MachineBasicBlock::iterator
84 findDelayInstr(MachineBasicBlock &MBB, MachineBasicBlock::iterator slot);
85
86 bool needsUnimp(MachineBasicBlock::iterator I, unsigned &StructSize);
87
88 bool tryCombineRestoreWithPrevInst(MachineBasicBlock &MBB,
89 MachineBasicBlock::iterator MBBI);
90
91 };
92 char Filler::ID = 0;
93 } // end of anonymous namespace
94
95 /// createSparcDelaySlotFillerPass - Returns a pass that fills in delay
96 /// slots in Sparc MachineFunctions
97 ///
createSparcDelaySlotFillerPass()98 FunctionPass *llvm::createSparcDelaySlotFillerPass() {
99 return new Filler;
100 }
101
102
103 /// runOnMachineBasicBlock - Fill in delay slots for the given basic block.
104 /// We assume there is only one delay slot per delayed instruction.
105 ///
runOnMachineBasicBlock(MachineBasicBlock & MBB)106 bool Filler::runOnMachineBasicBlock(MachineBasicBlock &MBB) {
107 bool Changed = false;
108 Subtarget = &MBB.getParent()->getSubtarget<SparcSubtarget>();
109 const TargetInstrInfo *TII = Subtarget->getInstrInfo();
110
111 for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ) {
112 MachineBasicBlock::iterator MI = I;
113 ++I;
114
115 // If MI is restore, try combining it with previous inst.
116 if (!DisableDelaySlotFiller &&
117 (MI->getOpcode() == SP::RESTORErr
118 || MI->getOpcode() == SP::RESTOREri)) {
119 Changed |= tryCombineRestoreWithPrevInst(MBB, MI);
120 continue;
121 }
122
123 // TODO: If we ever want to support v7, this needs to be extended
124 // to cover all floating point operations.
125 if (!Subtarget->isV9() &&
126 (MI->getOpcode() == SP::FCMPS || MI->getOpcode() == SP::FCMPD
127 || MI->getOpcode() == SP::FCMPQ)) {
128 BuildMI(MBB, I, MI->getDebugLoc(), TII->get(SP::NOP));
129 Changed = true;
130 continue;
131 }
132
133 // If MI has no delay slot, skip.
134 if (!MI->hasDelaySlot())
135 continue;
136
137 MachineBasicBlock::iterator D = MBB.end();
138
139 if (!DisableDelaySlotFiller)
140 D = findDelayInstr(MBB, MI);
141
142 ++FilledSlots;
143 Changed = true;
144
145 if (D == MBB.end())
146 BuildMI(MBB, I, MI->getDebugLoc(), TII->get(SP::NOP));
147 else
148 MBB.splice(I, &MBB, D);
149
150 unsigned structSize = 0;
151 if (needsUnimp(MI, structSize)) {
152 MachineBasicBlock::iterator J = MI;
153 ++J; // skip the delay filler.
154 assert (J != MBB.end() && "MI needs a delay instruction.");
155 BuildMI(MBB, ++J, MI->getDebugLoc(),
156 TII->get(SP::UNIMP)).addImm(structSize);
157 // Bundle the delay filler and unimp with the instruction.
158 MIBundleBuilder(MBB, MachineBasicBlock::iterator(MI), J);
159 } else {
160 MIBundleBuilder(MBB, MachineBasicBlock::iterator(MI), I);
161 }
162 }
163 return Changed;
164 }
165
166 MachineBasicBlock::iterator
findDelayInstr(MachineBasicBlock & MBB,MachineBasicBlock::iterator slot)167 Filler::findDelayInstr(MachineBasicBlock &MBB,
168 MachineBasicBlock::iterator slot)
169 {
170 SmallSet<unsigned, 32> RegDefs;
171 SmallSet<unsigned, 32> RegUses;
172 bool sawLoad = false;
173 bool sawStore = false;
174
175 if (slot == MBB.begin())
176 return MBB.end();
177
178 if (slot->getOpcode() == SP::RET || slot->getOpcode() == SP::TLS_CALL)
179 return MBB.end();
180
181 if (slot->getOpcode() == SP::RETL) {
182 MachineBasicBlock::iterator J = slot;
183 --J;
184
185 if (J->getOpcode() == SP::RESTORErr
186 || J->getOpcode() == SP::RESTOREri) {
187 // change retl to ret.
188 slot->setDesc(Subtarget->getInstrInfo()->get(SP::RET));
189 return J;
190 }
191 }
192
193 // Call's delay filler can def some of call's uses.
194 if (slot->isCall())
195 insertCallDefsUses(slot, RegDefs, RegUses);
196 else
197 insertDefsUses(slot, RegDefs, RegUses);
198
199 bool done = false;
200
201 MachineBasicBlock::iterator I = slot;
202
203 while (!done) {
204 done = (I == MBB.begin());
205
206 if (!done)
207 --I;
208
209 // skip debug instruction
210 if (I->isDebugInstr())
211 continue;
212
213 if (I->hasUnmodeledSideEffects() || I->isInlineAsm() || I->isPosition() ||
214 I->hasDelaySlot() || I->isBundledWithSucc())
215 break;
216
217 if (delayHasHazard(I, sawLoad, sawStore, RegDefs, RegUses)) {
218 insertDefsUses(I, RegDefs, RegUses);
219 continue;
220 }
221
222 return I;
223 }
224 return MBB.end();
225 }
226
delayHasHazard(MachineBasicBlock::iterator candidate,bool & sawLoad,bool & sawStore,SmallSet<unsigned,32> & RegDefs,SmallSet<unsigned,32> & RegUses)227 bool Filler::delayHasHazard(MachineBasicBlock::iterator candidate,
228 bool &sawLoad,
229 bool &sawStore,
230 SmallSet<unsigned, 32> &RegDefs,
231 SmallSet<unsigned, 32> &RegUses)
232 {
233
234 if (candidate->isImplicitDef() || candidate->isKill())
235 return true;
236
237 if (candidate->mayLoad()) {
238 sawLoad = true;
239 if (sawStore)
240 return true;
241 }
242
243 if (candidate->mayStore()) {
244 if (sawStore)
245 return true;
246 sawStore = true;
247 if (sawLoad)
248 return true;
249 }
250
251 for (unsigned i = 0, e = candidate->getNumOperands(); i!= e; ++i) {
252 const MachineOperand &MO = candidate->getOperand(i);
253 if (!MO.isReg())
254 continue; // skip
255
256 Register Reg = MO.getReg();
257
258 if (MO.isDef()) {
259 // check whether Reg is defined or used before delay slot.
260 if (IsRegInSet(RegDefs, Reg) || IsRegInSet(RegUses, Reg))
261 return true;
262 }
263 if (MO.isUse()) {
264 // check whether Reg is defined before delay slot.
265 if (IsRegInSet(RegDefs, Reg))
266 return true;
267 }
268 }
269
270 unsigned Opcode = candidate->getOpcode();
271 // LD and LDD may have NOPs inserted afterwards in the case of some LEON
272 // processors, so we can't use the delay slot if this feature is switched-on.
273 if (Subtarget->insertNOPLoad()
274 &&
275 Opcode >= SP::LDDArr && Opcode <= SP::LDrr)
276 return true;
277
278 // Same as above for FDIV and FSQRT on some LEON processors.
279 if (Subtarget->fixAllFDIVSQRT()
280 &&
281 Opcode >= SP::FDIVD && Opcode <= SP::FSQRTD)
282 return true;
283
284
285 return false;
286 }
287
288
insertCallDefsUses(MachineBasicBlock::iterator MI,SmallSet<unsigned,32> & RegDefs,SmallSet<unsigned,32> & RegUses)289 void Filler::insertCallDefsUses(MachineBasicBlock::iterator MI,
290 SmallSet<unsigned, 32>& RegDefs,
291 SmallSet<unsigned, 32>& RegUses)
292 {
293 // Call defines o7, which is visible to the instruction in delay slot.
294 RegDefs.insert(SP::O7);
295
296 switch(MI->getOpcode()) {
297 default: llvm_unreachable("Unknown opcode.");
298 case SP::CALL: break;
299 case SP::CALLrr:
300 case SP::CALLri:
301 assert(MI->getNumOperands() >= 2);
302 const MachineOperand &Reg = MI->getOperand(0);
303 assert(Reg.isReg() && "CALL first operand is not a register.");
304 assert(Reg.isUse() && "CALL first operand is not a use.");
305 RegUses.insert(Reg.getReg());
306
307 const MachineOperand &Operand1 = MI->getOperand(1);
308 if (Operand1.isImm() || Operand1.isGlobal())
309 break;
310 assert(Operand1.isReg() && "CALLrr second operand is not a register.");
311 assert(Operand1.isUse() && "CALLrr second operand is not a use.");
312 RegUses.insert(Operand1.getReg());
313 break;
314 }
315 }
316
317 // Insert Defs and Uses of MI into the sets RegDefs and RegUses.
insertDefsUses(MachineBasicBlock::iterator MI,SmallSet<unsigned,32> & RegDefs,SmallSet<unsigned,32> & RegUses)318 void Filler::insertDefsUses(MachineBasicBlock::iterator MI,
319 SmallSet<unsigned, 32>& RegDefs,
320 SmallSet<unsigned, 32>& RegUses)
321 {
322 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
323 const MachineOperand &MO = MI->getOperand(i);
324 if (!MO.isReg())
325 continue;
326
327 Register Reg = MO.getReg();
328 if (Reg == 0)
329 continue;
330 if (MO.isDef())
331 RegDefs.insert(Reg);
332 if (MO.isUse()) {
333 // Implicit register uses of retl are return values and
334 // retl does not use them.
335 if (MO.isImplicit() && MI->getOpcode() == SP::RETL)
336 continue;
337 RegUses.insert(Reg);
338 }
339 }
340 }
341
342 // returns true if the Reg or its alias is in the RegSet.
IsRegInSet(SmallSet<unsigned,32> & RegSet,unsigned Reg)343 bool Filler::IsRegInSet(SmallSet<unsigned, 32>& RegSet, unsigned Reg)
344 {
345 // Check Reg and all aliased Registers.
346 for (MCRegAliasIterator AI(Reg, Subtarget->getRegisterInfo(), true);
347 AI.isValid(); ++AI)
348 if (RegSet.count(*AI))
349 return true;
350 return false;
351 }
352
needsUnimp(MachineBasicBlock::iterator I,unsigned & StructSize)353 bool Filler::needsUnimp(MachineBasicBlock::iterator I, unsigned &StructSize)
354 {
355 if (!I->isCall())
356 return false;
357
358 unsigned structSizeOpNum = 0;
359 switch (I->getOpcode()) {
360 default: llvm_unreachable("Unknown call opcode.");
361 case SP::CALL: structSizeOpNum = 1; break;
362 case SP::CALLrr:
363 case SP::CALLri: structSizeOpNum = 2; break;
364 case SP::TLS_CALL: return false;
365 }
366
367 const MachineOperand &MO = I->getOperand(structSizeOpNum);
368 if (!MO.isImm())
369 return false;
370 StructSize = MO.getImm();
371 return true;
372 }
373
combineRestoreADD(MachineBasicBlock::iterator RestoreMI,MachineBasicBlock::iterator AddMI,const TargetInstrInfo * TII)374 static bool combineRestoreADD(MachineBasicBlock::iterator RestoreMI,
375 MachineBasicBlock::iterator AddMI,
376 const TargetInstrInfo *TII)
377 {
378 // Before: add <op0>, <op1>, %i[0-7]
379 // restore %g0, %g0, %i[0-7]
380 //
381 // After : restore <op0>, <op1>, %o[0-7]
382
383 Register reg = AddMI->getOperand(0).getReg();
384 if (reg < SP::I0 || reg > SP::I7)
385 return false;
386
387 // Erase RESTORE.
388 RestoreMI->eraseFromParent();
389
390 // Change ADD to RESTORE.
391 AddMI->setDesc(TII->get((AddMI->getOpcode() == SP::ADDrr)
392 ? SP::RESTORErr
393 : SP::RESTOREri));
394
395 // Map the destination register.
396 AddMI->getOperand(0).setReg(reg - SP::I0 + SP::O0);
397
398 return true;
399 }
400
combineRestoreOR(MachineBasicBlock::iterator RestoreMI,MachineBasicBlock::iterator OrMI,const TargetInstrInfo * TII)401 static bool combineRestoreOR(MachineBasicBlock::iterator RestoreMI,
402 MachineBasicBlock::iterator OrMI,
403 const TargetInstrInfo *TII)
404 {
405 // Before: or <op0>, <op1>, %i[0-7]
406 // restore %g0, %g0, %i[0-7]
407 // and <op0> or <op1> is zero,
408 //
409 // After : restore <op0>, <op1>, %o[0-7]
410
411 Register reg = OrMI->getOperand(0).getReg();
412 if (reg < SP::I0 || reg > SP::I7)
413 return false;
414
415 // check whether it is a copy.
416 if (OrMI->getOpcode() == SP::ORrr
417 && OrMI->getOperand(1).getReg() != SP::G0
418 && OrMI->getOperand(2).getReg() != SP::G0)
419 return false;
420
421 if (OrMI->getOpcode() == SP::ORri
422 && OrMI->getOperand(1).getReg() != SP::G0
423 && (!OrMI->getOperand(2).isImm() || OrMI->getOperand(2).getImm() != 0))
424 return false;
425
426 // Erase RESTORE.
427 RestoreMI->eraseFromParent();
428
429 // Change OR to RESTORE.
430 OrMI->setDesc(TII->get((OrMI->getOpcode() == SP::ORrr)
431 ? SP::RESTORErr
432 : SP::RESTOREri));
433
434 // Map the destination register.
435 OrMI->getOperand(0).setReg(reg - SP::I0 + SP::O0);
436
437 return true;
438 }
439
combineRestoreSETHIi(MachineBasicBlock::iterator RestoreMI,MachineBasicBlock::iterator SetHiMI,const TargetInstrInfo * TII)440 static bool combineRestoreSETHIi(MachineBasicBlock::iterator RestoreMI,
441 MachineBasicBlock::iterator SetHiMI,
442 const TargetInstrInfo *TII)
443 {
444 // Before: sethi imm3, %i[0-7]
445 // restore %g0, %g0, %g0
446 //
447 // After : restore %g0, (imm3<<10), %o[0-7]
448
449 Register reg = SetHiMI->getOperand(0).getReg();
450 if (reg < SP::I0 || reg > SP::I7)
451 return false;
452
453 if (!SetHiMI->getOperand(1).isImm())
454 return false;
455
456 int64_t imm = SetHiMI->getOperand(1).getImm();
457
458 // Is it a 3 bit immediate?
459 if (!isInt<3>(imm))
460 return false;
461
462 // Make it a 13 bit immediate.
463 imm = (imm << 10) & 0x1FFF;
464
465 assert(RestoreMI->getOpcode() == SP::RESTORErr);
466
467 RestoreMI->setDesc(TII->get(SP::RESTOREri));
468
469 RestoreMI->getOperand(0).setReg(reg - SP::I0 + SP::O0);
470 RestoreMI->getOperand(1).setReg(SP::G0);
471 RestoreMI->getOperand(2).ChangeToImmediate(imm);
472
473
474 // Erase the original SETHI.
475 SetHiMI->eraseFromParent();
476
477 return true;
478 }
479
tryCombineRestoreWithPrevInst(MachineBasicBlock & MBB,MachineBasicBlock::iterator MBBI)480 bool Filler::tryCombineRestoreWithPrevInst(MachineBasicBlock &MBB,
481 MachineBasicBlock::iterator MBBI)
482 {
483 // No previous instruction.
484 if (MBBI == MBB.begin())
485 return false;
486
487 // assert that MBBI is a "restore %g0, %g0, %g0".
488 assert(MBBI->getOpcode() == SP::RESTORErr
489 && MBBI->getOperand(0).getReg() == SP::G0
490 && MBBI->getOperand(1).getReg() == SP::G0
491 && MBBI->getOperand(2).getReg() == SP::G0);
492
493 MachineBasicBlock::iterator PrevInst = std::prev(MBBI);
494
495 // It cannot be combined with a bundled instruction.
496 if (PrevInst->isBundledWithSucc())
497 return false;
498
499 const TargetInstrInfo *TII = Subtarget->getInstrInfo();
500
501 switch (PrevInst->getOpcode()) {
502 default: break;
503 case SP::ADDrr:
504 case SP::ADDri: return combineRestoreADD(MBBI, PrevInst, TII); break;
505 case SP::ORrr:
506 case SP::ORri: return combineRestoreOR(MBBI, PrevInst, TII); break;
507 case SP::SETHIi: return combineRestoreSETHIi(MBBI, PrevInst, TII); break;
508 }
509 // It cannot combine with the previous instruction.
510 return false;
511 }
512