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;
Filler__anon57726bff0111::Filler48     Filler(TargetMachine &tm) : MachineFunctionPass(ID), TM(tm) {}
49 
getPassName__anon57726bff0111::Filler50     const char *getPassName() const override {
51       return "SPARC Delay Slot Filler";
52     }
53 
54     bool runOnMachineBasicBlock(MachineBasicBlock &MBB);
runOnMachineFunction__anon57726bff0111::Filler55     bool runOnMachineFunction(MachineFunction &F) override {
56       bool Changed = false;
57       Subtarget = &F.getSubtarget<SparcSubtarget>();
58 
59       // This pass invalidates liveness information when it reorders
60       // instructions to fill delay slot.
61       F.getRegInfo().invalidateLiveness();
62 
63       for (MachineFunction::iterator FI = F.begin(), FE = F.end();
64            FI != FE; ++FI)
65         Changed |= runOnMachineBasicBlock(*FI);
66       return Changed;
67     }
68 
69     void insertCallDefsUses(MachineBasicBlock::iterator MI,
70                             SmallSet<unsigned, 32>& RegDefs,
71                             SmallSet<unsigned, 32>& RegUses);
72 
73     void insertDefsUses(MachineBasicBlock::iterator MI,
74                         SmallSet<unsigned, 32>& RegDefs,
75                         SmallSet<unsigned, 32>& RegUses);
76 
77     bool IsRegInSet(SmallSet<unsigned, 32>& RegSet,
78                     unsigned Reg);
79 
80     bool delayHasHazard(MachineBasicBlock::iterator candidate,
81                         bool &sawLoad, bool &sawStore,
82                         SmallSet<unsigned, 32> &RegDefs,
83                         SmallSet<unsigned, 32> &RegUses);
84 
85     MachineBasicBlock::iterator
86     findDelayInstr(MachineBasicBlock &MBB, MachineBasicBlock::iterator slot);
87 
88     bool needsUnimp(MachineBasicBlock::iterator I, unsigned &StructSize);
89 
90     bool tryCombineRestoreWithPrevInst(MachineBasicBlock &MBB,
91                                        MachineBasicBlock::iterator MBBI);
92 
93   };
94   char Filler::ID = 0;
95 } // end of anonymous namespace
96 
97 /// createSparcDelaySlotFillerPass - Returns a pass that fills in delay
98 /// slots in Sparc MachineFunctions
99 ///
createSparcDelaySlotFillerPass(TargetMachine & tm)100 FunctionPass *llvm::createSparcDelaySlotFillerPass(TargetMachine &tm) {
101   return new Filler(tm);
102 }
103 
104 
105 /// runOnMachineBasicBlock - Fill in delay slots for the given basic block.
106 /// We assume there is only one delay slot per delayed instruction.
107 ///
runOnMachineBasicBlock(MachineBasicBlock & MBB)108 bool Filler::runOnMachineBasicBlock(MachineBasicBlock &MBB) {
109   bool Changed = false;
110   Subtarget = &MBB.getParent()->getSubtarget<SparcSubtarget>();
111   const TargetInstrInfo *TII = Subtarget->getInstrInfo();
112 
113   for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ) {
114     MachineBasicBlock::iterator MI = I;
115     ++I;
116 
117     // If MI is restore, try combining it with previous inst.
118     if (!DisableDelaySlotFiller &&
119         (MI->getOpcode() == SP::RESTORErr
120          || MI->getOpcode() == SP::RESTOREri)) {
121       Changed |= tryCombineRestoreWithPrevInst(MBB, MI);
122       continue;
123     }
124 
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
findDelayInstr(MachineBasicBlock & MBB,MachineBasicBlock::iterator slot)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 value
210     if (I->isDebugValue())
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 
delayHasHazard(MachineBasicBlock::iterator candidate,bool & sawLoad,bool & sawStore,SmallSet<unsigned,32> & RegDefs,SmallSet<unsigned,32> & RegUses)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     unsigned 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   return false;
270 }
271 
272 
insertCallDefsUses(MachineBasicBlock::iterator MI,SmallSet<unsigned,32> & RegDefs,SmallSet<unsigned,32> & RegUses)273 void Filler::insertCallDefsUses(MachineBasicBlock::iterator MI,
274                                 SmallSet<unsigned, 32>& RegDefs,
275                                 SmallSet<unsigned, 32>& RegUses)
276 {
277   // Call defines o7, which is visible to the instruction in delay slot.
278   RegDefs.insert(SP::O7);
279 
280   switch(MI->getOpcode()) {
281   default: llvm_unreachable("Unknown opcode.");
282   case SP::CALL: break;
283   case SP::CALLrr:
284   case SP::CALLri:
285     assert(MI->getNumOperands() >= 2);
286     const MachineOperand &Reg = MI->getOperand(0);
287     assert(Reg.isReg() && "CALL first operand is not a register.");
288     assert(Reg.isUse() && "CALL first operand is not a use.");
289     RegUses.insert(Reg.getReg());
290 
291     const MachineOperand &RegOrImm = MI->getOperand(1);
292     if (RegOrImm.isImm())
293         break;
294     assert(RegOrImm.isReg() && "CALLrr second operand is not a register.");
295     assert(RegOrImm.isUse() && "CALLrr second operand is not a use.");
296     RegUses.insert(RegOrImm.getReg());
297     break;
298   }
299 }
300 
301 // Insert Defs and Uses of MI into the sets RegDefs and RegUses.
insertDefsUses(MachineBasicBlock::iterator MI,SmallSet<unsigned,32> & RegDefs,SmallSet<unsigned,32> & RegUses)302 void Filler::insertDefsUses(MachineBasicBlock::iterator MI,
303                             SmallSet<unsigned, 32>& RegDefs,
304                             SmallSet<unsigned, 32>& RegUses)
305 {
306   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
307     const MachineOperand &MO = MI->getOperand(i);
308     if (!MO.isReg())
309       continue;
310 
311     unsigned Reg = MO.getReg();
312     if (Reg == 0)
313       continue;
314     if (MO.isDef())
315       RegDefs.insert(Reg);
316     if (MO.isUse()) {
317       // Implicit register uses of retl are return values and
318       // retl does not use them.
319       if (MO.isImplicit() && MI->getOpcode() == SP::RETL)
320         continue;
321       RegUses.insert(Reg);
322     }
323   }
324 }
325 
326 // returns true if the Reg or its alias is in the RegSet.
IsRegInSet(SmallSet<unsigned,32> & RegSet,unsigned Reg)327 bool Filler::IsRegInSet(SmallSet<unsigned, 32>& RegSet, unsigned Reg)
328 {
329   // Check Reg and all aliased Registers.
330   for (MCRegAliasIterator AI(Reg, Subtarget->getRegisterInfo(), true);
331        AI.isValid(); ++AI)
332     if (RegSet.count(*AI))
333       return true;
334   return false;
335 }
336 
needsUnimp(MachineBasicBlock::iterator I,unsigned & StructSize)337 bool Filler::needsUnimp(MachineBasicBlock::iterator I, unsigned &StructSize)
338 {
339   if (!I->isCall())
340     return false;
341 
342   unsigned structSizeOpNum = 0;
343   switch (I->getOpcode()) {
344   default: llvm_unreachable("Unknown call opcode.");
345   case SP::CALL: structSizeOpNum = 1; break;
346   case SP::CALLrr:
347   case SP::CALLri: structSizeOpNum = 2; break;
348   case SP::TLS_CALL: return false;
349   }
350 
351   const MachineOperand &MO = I->getOperand(structSizeOpNum);
352   if (!MO.isImm())
353     return false;
354   StructSize = MO.getImm();
355   return true;
356 }
357 
combineRestoreADD(MachineBasicBlock::iterator RestoreMI,MachineBasicBlock::iterator AddMI,const TargetInstrInfo * TII)358 static bool combineRestoreADD(MachineBasicBlock::iterator RestoreMI,
359                               MachineBasicBlock::iterator AddMI,
360                               const TargetInstrInfo *TII)
361 {
362   // Before:  add  <op0>, <op1>, %i[0-7]
363   //          restore %g0, %g0, %i[0-7]
364   //
365   // After :  restore <op0>, <op1>, %o[0-7]
366 
367   unsigned reg = AddMI->getOperand(0).getReg();
368   if (reg < SP::I0 || reg > SP::I7)
369     return false;
370 
371   // Erase RESTORE.
372   RestoreMI->eraseFromParent();
373 
374   // Change ADD to RESTORE.
375   AddMI->setDesc(TII->get((AddMI->getOpcode() == SP::ADDrr)
376                           ? SP::RESTORErr
377                           : SP::RESTOREri));
378 
379   // Map the destination register.
380   AddMI->getOperand(0).setReg(reg - SP::I0 + SP::O0);
381 
382   return true;
383 }
384 
combineRestoreOR(MachineBasicBlock::iterator RestoreMI,MachineBasicBlock::iterator OrMI,const TargetInstrInfo * TII)385 static bool combineRestoreOR(MachineBasicBlock::iterator RestoreMI,
386                              MachineBasicBlock::iterator OrMI,
387                              const TargetInstrInfo *TII)
388 {
389   // Before:  or  <op0>, <op1>, %i[0-7]
390   //          restore %g0, %g0, %i[0-7]
391   //    and <op0> or <op1> is zero,
392   //
393   // After :  restore <op0>, <op1>, %o[0-7]
394 
395   unsigned reg = OrMI->getOperand(0).getReg();
396   if (reg < SP::I0 || reg > SP::I7)
397     return false;
398 
399   // check whether it is a copy.
400   if (OrMI->getOpcode() == SP::ORrr
401       && OrMI->getOperand(1).getReg() != SP::G0
402       && OrMI->getOperand(2).getReg() != SP::G0)
403     return false;
404 
405   if (OrMI->getOpcode() == SP::ORri
406       && OrMI->getOperand(1).getReg() != SP::G0
407       && (!OrMI->getOperand(2).isImm() || OrMI->getOperand(2).getImm() != 0))
408     return false;
409 
410   // Erase RESTORE.
411   RestoreMI->eraseFromParent();
412 
413   // Change OR to RESTORE.
414   OrMI->setDesc(TII->get((OrMI->getOpcode() == SP::ORrr)
415                          ? SP::RESTORErr
416                          : SP::RESTOREri));
417 
418   // Map the destination register.
419   OrMI->getOperand(0).setReg(reg - SP::I0 + SP::O0);
420 
421   return true;
422 }
423 
combineRestoreSETHIi(MachineBasicBlock::iterator RestoreMI,MachineBasicBlock::iterator SetHiMI,const TargetInstrInfo * TII)424 static bool combineRestoreSETHIi(MachineBasicBlock::iterator RestoreMI,
425                                  MachineBasicBlock::iterator SetHiMI,
426                                  const TargetInstrInfo *TII)
427 {
428   // Before:  sethi imm3, %i[0-7]
429   //          restore %g0, %g0, %g0
430   //
431   // After :  restore %g0, (imm3<<10), %o[0-7]
432 
433   unsigned reg = SetHiMI->getOperand(0).getReg();
434   if (reg < SP::I0 || reg > SP::I7)
435     return false;
436 
437   if (!SetHiMI->getOperand(1).isImm())
438     return false;
439 
440   int64_t imm = SetHiMI->getOperand(1).getImm();
441 
442   // Is it a 3 bit immediate?
443   if (!isInt<3>(imm))
444     return false;
445 
446   // Make it a 13 bit immediate.
447   imm = (imm << 10) & 0x1FFF;
448 
449   assert(RestoreMI->getOpcode() == SP::RESTORErr);
450 
451   RestoreMI->setDesc(TII->get(SP::RESTOREri));
452 
453   RestoreMI->getOperand(0).setReg(reg - SP::I0 + SP::O0);
454   RestoreMI->getOperand(1).setReg(SP::G0);
455   RestoreMI->getOperand(2).ChangeToImmediate(imm);
456 
457 
458   // Erase the original SETHI.
459   SetHiMI->eraseFromParent();
460 
461   return true;
462 }
463 
tryCombineRestoreWithPrevInst(MachineBasicBlock & MBB,MachineBasicBlock::iterator MBBI)464 bool Filler::tryCombineRestoreWithPrevInst(MachineBasicBlock &MBB,
465                                         MachineBasicBlock::iterator MBBI)
466 {
467   // No previous instruction.
468   if (MBBI == MBB.begin())
469     return false;
470 
471   // assert that MBBI is a "restore %g0, %g0, %g0".
472   assert(MBBI->getOpcode() == SP::RESTORErr
473          && MBBI->getOperand(0).getReg() == SP::G0
474          && MBBI->getOperand(1).getReg() == SP::G0
475          && MBBI->getOperand(2).getReg() == SP::G0);
476 
477   MachineBasicBlock::iterator PrevInst = std::prev(MBBI);
478 
479   // It cannot be combined with a bundled instruction.
480   if (PrevInst->isBundledWithSucc())
481     return false;
482 
483   const TargetInstrInfo *TII = Subtarget->getInstrInfo();
484 
485   switch (PrevInst->getOpcode()) {
486   default: break;
487   case SP::ADDrr:
488   case SP::ADDri: return combineRestoreADD(MBBI, PrevInst, TII); break;
489   case SP::ORrr:
490   case SP::ORri:  return combineRestoreOR(MBBI, PrevInst, TII); break;
491   case SP::SETHIi: return combineRestoreSETHIi(MBBI, PrevInst, TII); break;
492   }
493   // It cannot combine with the previous instruction.
494   return false;
495 }
496