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