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