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 (MachineFunction::iterator FI = F.begin(), FE = F.end();
57            FI != FE; ++FI)
58         Changed |= runOnMachineBasicBlock(*FI);
59       return Changed;
60     }
61 
62     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 ///
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 ///
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
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 
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 
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.
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.
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 
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 
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 
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 
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 
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