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