1 //===-- DelaySlotFiller.cpp - SPARC delay slot filler ---------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This is a simple local pass that attempts to fill delay slots with useful
11 // instructions. If no instructions can be moved into the delay slot, then a
12 // NOP is placed.
13 //===----------------------------------------------------------------------===//
14 
15 #include "Sparc.h"
16 #include "SparcSubtarget.h"
17 #include "llvm/ADT/SmallSet.h"
18 #include "llvm/ADT/Statistic.h"
19 #include "llvm/CodeGen/MachineFunctionPass.h"
20 #include "llvm/CodeGen/MachineInstrBuilder.h"
21 #include "llvm/CodeGen/MachineRegisterInfo.h"
22 #include "llvm/Support/CommandLine.h"
23 #include "llvm/Target/TargetInstrInfo.h"
24 #include "llvm/Target/TargetMachine.h"
25 #include "llvm/Target/TargetRegisterInfo.h"
26 
27 using namespace llvm;
28 
29 #define DEBUG_TYPE "delay-slot-filler"
30 
31 STATISTIC(FilledSlots, "Number of delay slots filled");
32 
33 static cl::opt<bool> DisableDelaySlotFiller(
34   "disable-sparc-delay-filler",
35   cl::init(false),
36   cl::desc("Disable the Sparc delay slot filler."),
37   cl::Hidden);
38 
39 namespace {
40   struct Filler : public MachineFunctionPass {
41     /// Target machine description which we query for reg. names, data
42     /// layout, etc.
43     ///
44     TargetMachine &TM;
45     const SparcSubtarget *Subtarget;
46 
47     static char ID;
48     Filler(TargetMachine &tm)
49       : MachineFunctionPass(ID), TM(tm),
50         Subtarget(&TM.getSubtarget<SparcSubtarget>()) {
51     }
52 
53     const char *getPassName() const override {
54       return "SPARC Delay Slot Filler";
55     }
56 
57     bool runOnMachineBasicBlock(MachineBasicBlock &MBB);
58     bool runOnMachineFunction(MachineFunction &F) override {
59       bool Changed = false;
60 
61       // This pass invalidates liveness information when it reorders
62       // instructions to fill delay slot.
63       F.getRegInfo().invalidateLiveness();
64 
65       for (MachineFunction::iterator FI = F.begin(), FE = F.end();
66            FI != FE; ++FI)
67         Changed |= runOnMachineBasicBlock(*FI);
68       return Changed;
69     }
70 
71     void insertCallDefsUses(MachineBasicBlock::iterator MI,
72                             SmallSet<unsigned, 32>& RegDefs,
73                             SmallSet<unsigned, 32>& RegUses);
74 
75     void insertDefsUses(MachineBasicBlock::iterator MI,
76                         SmallSet<unsigned, 32>& RegDefs,
77                         SmallSet<unsigned, 32>& RegUses);
78 
79     bool IsRegInSet(SmallSet<unsigned, 32>& RegSet,
80                     unsigned Reg);
81 
82     bool delayHasHazard(MachineBasicBlock::iterator candidate,
83                         bool &sawLoad, bool &sawStore,
84                         SmallSet<unsigned, 32> &RegDefs,
85                         SmallSet<unsigned, 32> &RegUses);
86 
87     MachineBasicBlock::iterator
88     findDelayInstr(MachineBasicBlock &MBB, MachineBasicBlock::iterator slot);
89 
90     bool needsUnimp(MachineBasicBlock::iterator I, unsigned &StructSize);
91 
92     bool tryCombineRestoreWithPrevInst(MachineBasicBlock &MBB,
93                                        MachineBasicBlock::iterator MBBI);
94 
95   };
96   char Filler::ID = 0;
97 } // end of anonymous namespace
98 
99 /// createSparcDelaySlotFillerPass - Returns a pass that fills in delay
100 /// slots in Sparc MachineFunctions
101 ///
102 FunctionPass *llvm::createSparcDelaySlotFillerPass(TargetMachine &tm) {
103   return new Filler(tm);
104 }
105 
106 
107 /// runOnMachineBasicBlock - Fill in delay slots for the given basic block.
108 /// We assume there is only one delay slot per delayed instruction.
109 ///
110 bool Filler::runOnMachineBasicBlock(MachineBasicBlock &MBB) {
111   bool Changed = false;
112 
113   const TargetInstrInfo *TII = TM.getSubtargetImpl()->getInstrInfo();
114 
115   for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ) {
116     MachineBasicBlock::iterator MI = I;
117     ++I;
118 
119     // If MI is restore, try combining it with previous inst.
120     if (!DisableDelaySlotFiller &&
121         (MI->getOpcode() == SP::RESTORErr
122          || MI->getOpcode() == SP::RESTOREri)) {
123       Changed |= tryCombineRestoreWithPrevInst(MBB, MI);
124       continue;
125     }
126 
127     if (!Subtarget->isV9() &&
128         (MI->getOpcode() == SP::FCMPS || MI->getOpcode() == SP::FCMPD
129          || MI->getOpcode() == SP::FCMPQ)) {
130       BuildMI(MBB, I, MI->getDebugLoc(), TII->get(SP::NOP));
131       Changed = true;
132       continue;
133     }
134 
135     // If MI has no delay slot, skip.
136     if (!MI->hasDelaySlot())
137       continue;
138 
139     MachineBasicBlock::iterator D = MBB.end();
140 
141     if (!DisableDelaySlotFiller)
142       D = findDelayInstr(MBB, MI);
143 
144     ++FilledSlots;
145     Changed = true;
146 
147     if (D == MBB.end())
148       BuildMI(MBB, I, MI->getDebugLoc(), TII->get(SP::NOP));
149     else
150       MBB.splice(I, &MBB, D);
151 
152     unsigned structSize = 0;
153     if (needsUnimp(MI, structSize)) {
154       MachineBasicBlock::iterator J = MI;
155       ++J; // skip the delay filler.
156       assert (J != MBB.end() && "MI needs a delay instruction.");
157       BuildMI(MBB, ++J, MI->getDebugLoc(),
158               TII->get(SP::UNIMP)).addImm(structSize);
159       // Bundle the delay filler and unimp with the instruction.
160       MIBundleBuilder(MBB, MachineBasicBlock::iterator(MI), J);
161     } else {
162       MIBundleBuilder(MBB, MachineBasicBlock::iterator(MI), I);
163     }
164   }
165   return Changed;
166 }
167 
168 MachineBasicBlock::iterator
169 Filler::findDelayInstr(MachineBasicBlock &MBB,
170                        MachineBasicBlock::iterator slot)
171 {
172   SmallSet<unsigned, 32> RegDefs;
173   SmallSet<unsigned, 32> RegUses;
174   bool sawLoad = false;
175   bool sawStore = false;
176 
177   if (slot == MBB.begin())
178     return MBB.end();
179 
180   if (slot->getOpcode() == SP::RET || slot->getOpcode() == SP::TLS_CALL)
181     return MBB.end();
182 
183   if (slot->getOpcode() == SP::RETL) {
184     MachineBasicBlock::iterator J = slot;
185     --J;
186 
187     if (J->getOpcode() == SP::RESTORErr
188         || J->getOpcode() == SP::RESTOREri) {
189       // change retl to ret.
190       slot->setDesc(TM.getSubtargetImpl()->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 value
212     if (I->isDebugValue())
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     unsigned 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   return false;
272 }
273 
274 
275 void Filler::insertCallDefsUses(MachineBasicBlock::iterator MI,
276                                 SmallSet<unsigned, 32>& RegDefs,
277                                 SmallSet<unsigned, 32>& RegUses)
278 {
279   // Call defines o7, which is visible to the instruction in delay slot.
280   RegDefs.insert(SP::O7);
281 
282   switch(MI->getOpcode()) {
283   default: llvm_unreachable("Unknown opcode.");
284   case SP::CALL: break;
285   case SP::CALLrr:
286   case SP::CALLri:
287     assert(MI->getNumOperands() >= 2);
288     const MachineOperand &Reg = MI->getOperand(0);
289     assert(Reg.isReg() && "CALL first operand is not a register.");
290     assert(Reg.isUse() && "CALL first operand is not a use.");
291     RegUses.insert(Reg.getReg());
292 
293     const MachineOperand &RegOrImm = MI->getOperand(1);
294     if (RegOrImm.isImm())
295         break;
296     assert(RegOrImm.isReg() && "CALLrr second operand is not a register.");
297     assert(RegOrImm.isUse() && "CALLrr second operand is not a use.");
298     RegUses.insert(RegOrImm.getReg());
299     break;
300   }
301 }
302 
303 // Insert Defs and Uses of MI into the sets RegDefs and RegUses.
304 void Filler::insertDefsUses(MachineBasicBlock::iterator MI,
305                             SmallSet<unsigned, 32>& RegDefs,
306                             SmallSet<unsigned, 32>& RegUses)
307 {
308   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
309     const MachineOperand &MO = MI->getOperand(i);
310     if (!MO.isReg())
311       continue;
312 
313     unsigned Reg = MO.getReg();
314     if (Reg == 0)
315       continue;
316     if (MO.isDef())
317       RegDefs.insert(Reg);
318     if (MO.isUse()) {
319       // Implicit register uses of retl are return values and
320       // retl does not use them.
321       if (MO.isImplicit() && MI->getOpcode() == SP::RETL)
322         continue;
323       RegUses.insert(Reg);
324     }
325   }
326 }
327 
328 // returns true if the Reg or its alias is in the RegSet.
329 bool Filler::IsRegInSet(SmallSet<unsigned, 32>& RegSet, unsigned Reg)
330 {
331   // Check Reg and all aliased Registers.
332   for (MCRegAliasIterator AI(Reg, TM.getSubtargetImpl()->getRegisterInfo(),
333                              true);
334        AI.isValid(); ++AI)
335     if (RegSet.count(*AI))
336       return true;
337   return false;
338 }
339 
340 bool Filler::needsUnimp(MachineBasicBlock::iterator I, unsigned &StructSize)
341 {
342   if (!I->isCall())
343     return false;
344 
345   unsigned structSizeOpNum = 0;
346   switch (I->getOpcode()) {
347   default: llvm_unreachable("Unknown call opcode.");
348   case SP::CALL: structSizeOpNum = 1; break;
349   case SP::CALLrr:
350   case SP::CALLri: structSizeOpNum = 2; break;
351   case SP::TLS_CALL: return false;
352   }
353 
354   const MachineOperand &MO = I->getOperand(structSizeOpNum);
355   if (!MO.isImm())
356     return false;
357   StructSize = MO.getImm();
358   return true;
359 }
360 
361 static bool combineRestoreADD(MachineBasicBlock::iterator RestoreMI,
362                               MachineBasicBlock::iterator AddMI,
363                               const TargetInstrInfo *TII)
364 {
365   // Before:  add  <op0>, <op1>, %i[0-7]
366   //          restore %g0, %g0, %i[0-7]
367   //
368   // After :  restore <op0>, <op1>, %o[0-7]
369 
370   unsigned reg = AddMI->getOperand(0).getReg();
371   if (reg < SP::I0 || reg > SP::I7)
372     return false;
373 
374   // Erase RESTORE.
375   RestoreMI->eraseFromParent();
376 
377   // Change ADD to RESTORE.
378   AddMI->setDesc(TII->get((AddMI->getOpcode() == SP::ADDrr)
379                           ? SP::RESTORErr
380                           : SP::RESTOREri));
381 
382   // Map the destination register.
383   AddMI->getOperand(0).setReg(reg - SP::I0 + SP::O0);
384 
385   return true;
386 }
387 
388 static bool combineRestoreOR(MachineBasicBlock::iterator RestoreMI,
389                              MachineBasicBlock::iterator OrMI,
390                              const TargetInstrInfo *TII)
391 {
392   // Before:  or  <op0>, <op1>, %i[0-7]
393   //          restore %g0, %g0, %i[0-7]
394   //    and <op0> or <op1> is zero,
395   //
396   // After :  restore <op0>, <op1>, %o[0-7]
397 
398   unsigned reg = OrMI->getOperand(0).getReg();
399   if (reg < SP::I0 || reg > SP::I7)
400     return false;
401 
402   // check whether it is a copy.
403   if (OrMI->getOpcode() == SP::ORrr
404       && OrMI->getOperand(1).getReg() != SP::G0
405       && OrMI->getOperand(2).getReg() != SP::G0)
406     return false;
407 
408   if (OrMI->getOpcode() == SP::ORri
409       && OrMI->getOperand(1).getReg() != SP::G0
410       && (!OrMI->getOperand(2).isImm() || OrMI->getOperand(2).getImm() != 0))
411     return false;
412 
413   // Erase RESTORE.
414   RestoreMI->eraseFromParent();
415 
416   // Change OR to RESTORE.
417   OrMI->setDesc(TII->get((OrMI->getOpcode() == SP::ORrr)
418                          ? SP::RESTORErr
419                          : SP::RESTOREri));
420 
421   // Map the destination register.
422   OrMI->getOperand(0).setReg(reg - SP::I0 + SP::O0);
423 
424   return true;
425 }
426 
427 static bool combineRestoreSETHIi(MachineBasicBlock::iterator RestoreMI,
428                                  MachineBasicBlock::iterator SetHiMI,
429                                  const TargetInstrInfo *TII)
430 {
431   // Before:  sethi imm3, %i[0-7]
432   //          restore %g0, %g0, %g0
433   //
434   // After :  restore %g0, (imm3<<10), %o[0-7]
435 
436   unsigned reg = SetHiMI->getOperand(0).getReg();
437   if (reg < SP::I0 || reg > SP::I7)
438     return false;
439 
440   if (!SetHiMI->getOperand(1).isImm())
441     return false;
442 
443   int64_t imm = SetHiMI->getOperand(1).getImm();
444 
445   // Is it a 3 bit immediate?
446   if (!isInt<3>(imm))
447     return false;
448 
449   // Make it a 13 bit immediate.
450   imm = (imm << 10) & 0x1FFF;
451 
452   assert(RestoreMI->getOpcode() == SP::RESTORErr);
453 
454   RestoreMI->setDesc(TII->get(SP::RESTOREri));
455 
456   RestoreMI->getOperand(0).setReg(reg - SP::I0 + SP::O0);
457   RestoreMI->getOperand(1).setReg(SP::G0);
458   RestoreMI->getOperand(2).ChangeToImmediate(imm);
459 
460 
461   // Erase the original SETHI.
462   SetHiMI->eraseFromParent();
463 
464   return true;
465 }
466 
467 bool Filler::tryCombineRestoreWithPrevInst(MachineBasicBlock &MBB,
468                                         MachineBasicBlock::iterator MBBI)
469 {
470   // No previous instruction.
471   if (MBBI == MBB.begin())
472     return false;
473 
474   // assert that MBBI is a "restore %g0, %g0, %g0".
475   assert(MBBI->getOpcode() == SP::RESTORErr
476          && MBBI->getOperand(0).getReg() == SP::G0
477          && MBBI->getOperand(1).getReg() == SP::G0
478          && MBBI->getOperand(2).getReg() == SP::G0);
479 
480   MachineBasicBlock::iterator PrevInst = std::prev(MBBI);
481 
482   // It cannot be combined with a bundled instruction.
483   if (PrevInst->isBundledWithSucc())
484     return false;
485 
486   const TargetInstrInfo *TII = TM.getSubtargetImpl()->getInstrInfo();
487 
488   switch (PrevInst->getOpcode()) {
489   default: break;
490   case SP::ADDrr:
491   case SP::ADDri: return combineRestoreADD(MBBI, PrevInst, TII); break;
492   case SP::ORrr:
493   case SP::ORri:  return combineRestoreOR(MBBI, PrevInst, TII); break;
494   case SP::SETHIi: return combineRestoreSETHIi(MBBI, PrevInst, TII); break;
495   }
496   // It cannot combine with the previous instruction.
497   return false;
498 }
499