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