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 #define DEBUG_TYPE "delay-slot-filler"
16 #include "Sparc.h"
17 #include "SparcSubtarget.h"
18 #include "llvm/ADT/SmallSet.h"
19 #include "llvm/ADT/Statistic.h"
20 #include "llvm/CodeGen/MachineFunctionPass.h"
21 #include "llvm/CodeGen/MachineInstrBuilder.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 STATISTIC(FilledSlots, "Number of delay slots filled");
30 
31 static cl::opt<bool> DisableDelaySlotFiller(
32   "disable-sparc-delay-filler",
33   cl::init(false),
34   cl::desc("Disable the Sparc delay slot filler."),
35   cl::Hidden);
36 
37 namespace {
38   struct Filler : public MachineFunctionPass {
39     /// Target machine description which we query for reg. names, data
40     /// layout, etc.
41     ///
42     TargetMachine &TM;
43     const SparcSubtarget *Subtarget;
44 
45     static char ID;
46     Filler(TargetMachine &tm)
47       : MachineFunctionPass(ID), TM(tm),
48         Subtarget(&TM.getSubtarget<SparcSubtarget>()) {
49     }
50 
51     virtual const char *getPassName() const {
52       return "SPARC Delay Slot Filler";
53     }
54 
55     bool runOnMachineBasicBlock(MachineBasicBlock &MBB);
56     bool runOnMachineFunction(MachineFunction &F) {
57       bool Changed = false;
58       for (MachineFunction::iterator FI = F.begin(), FE = F.end();
59            FI != FE; ++FI)
60         Changed |= runOnMachineBasicBlock(*FI);
61       return Changed;
62     }
63 
64     bool isDelayFiller(MachineBasicBlock &MBB,
65                        MachineBasicBlock::iterator candidate);
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(TargetMachine &tm) {
99   return new Filler(tm);
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 
109   const TargetInstrInfo *TII = TM.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     if (!Subtarget->isV9() &&
124         (MI->getOpcode() == SP::FCMPS || MI->getOpcode() == SP::FCMPD
125          || MI->getOpcode() == SP::FCMPQ)) {
126       BuildMI(MBB, I, MI->getDebugLoc(), TII->get(SP::NOP));
127       Changed = true;
128       continue;
129     }
130 
131     // If MI has no delay slot, skip.
132     if (!MI->hasDelaySlot())
133       continue;
134 
135     MachineBasicBlock::iterator D = MBB.end();
136 
137     if (!DisableDelaySlotFiller)
138       D = findDelayInstr(MBB, MI);
139 
140     ++FilledSlots;
141     Changed = true;
142 
143     if (D == MBB.end())
144       BuildMI(MBB, I, MI->getDebugLoc(), TII->get(SP::NOP));
145     else
146       MBB.splice(I, &MBB, D);
147 
148     unsigned structSize = 0;
149     if (needsUnimp(MI, structSize)) {
150       MachineBasicBlock::iterator J = MI;
151       ++J; // skip the delay filler.
152       assert (J != MBB.end() && "MI needs a delay instruction.");
153       BuildMI(MBB, ++J, MI->getDebugLoc(),
154               TII->get(SP::UNIMP)).addImm(structSize);
155     }
156   }
157   return Changed;
158 }
159 
160 MachineBasicBlock::iterator
161 Filler::findDelayInstr(MachineBasicBlock &MBB,
162                        MachineBasicBlock::iterator slot)
163 {
164   SmallSet<unsigned, 32> RegDefs;
165   SmallSet<unsigned, 32> RegUses;
166   bool sawLoad = false;
167   bool sawStore = false;
168 
169   if (slot == MBB.begin())
170     return MBB.end();
171 
172   if (slot->getOpcode() == SP::RET || slot->getOpcode() == SP::TLS_CALL)
173     return MBB.end();
174 
175   if (slot->getOpcode() == SP::RETL) {
176     MachineBasicBlock::iterator J = slot;
177     --J;
178 
179     if (J->getOpcode() == SP::RESTORErr
180         || J->getOpcode() == SP::RESTOREri) {
181       // change retl to ret.
182       slot->setDesc(TM.getInstrInfo()->get(SP::RET));
183       return J;
184     }
185   }
186 
187   // Call's delay filler can def some of call's uses.
188   if (slot->isCall())
189     insertCallDefsUses(slot, RegDefs, RegUses);
190   else
191     insertDefsUses(slot, RegDefs, RegUses);
192 
193   bool done = false;
194 
195   MachineBasicBlock::iterator I = slot;
196 
197   while (!done) {
198     done = (I == MBB.begin());
199 
200     if (!done)
201       --I;
202 
203     // skip debug value
204     if (I->isDebugValue())
205       continue;
206 
207 
208     if (I->hasUnmodeledSideEffects()
209         || I->isInlineAsm()
210         || I->isLabel()
211         || I->hasDelaySlot()
212         || isDelayFiller(MBB, I))
213       break;
214 
215     if (delayHasHazard(I, sawLoad, sawStore, RegDefs, RegUses)) {
216       insertDefsUses(I, RegDefs, RegUses);
217       continue;
218     }
219 
220     return I;
221   }
222   return MBB.end();
223 }
224 
225 bool Filler::delayHasHazard(MachineBasicBlock::iterator candidate,
226                             bool &sawLoad,
227                             bool &sawStore,
228                             SmallSet<unsigned, 32> &RegDefs,
229                             SmallSet<unsigned, 32> &RegUses)
230 {
231 
232   if (candidate->isImplicitDef() || candidate->isKill())
233     return true;
234 
235   if (candidate->mayLoad()) {
236     sawLoad = true;
237     if (sawStore)
238       return true;
239   }
240 
241   if (candidate->mayStore()) {
242     if (sawStore)
243       return true;
244     sawStore = true;
245     if (sawLoad)
246       return true;
247   }
248 
249   for (unsigned i = 0, e = candidate->getNumOperands(); i!= e; ++i) {
250     const MachineOperand &MO = candidate->getOperand(i);
251     if (!MO.isReg())
252       continue; // skip
253 
254     unsigned Reg = MO.getReg();
255 
256     if (MO.isDef()) {
257       // check whether Reg is defined or used before delay slot.
258       if (IsRegInSet(RegDefs, Reg) || IsRegInSet(RegUses, Reg))
259         return true;
260     }
261     if (MO.isUse()) {
262       // check whether Reg is defined before delay slot.
263       if (IsRegInSet(RegDefs, Reg))
264         return true;
265     }
266   }
267   return false;
268 }
269 
270 
271 void Filler::insertCallDefsUses(MachineBasicBlock::iterator MI,
272                                 SmallSet<unsigned, 32>& RegDefs,
273                                 SmallSet<unsigned, 32>& RegUses)
274 {
275   // Call defines o7, which is visible to the instruction in delay slot.
276   RegDefs.insert(SP::O7);
277 
278   switch(MI->getOpcode()) {
279   default: llvm_unreachable("Unknown opcode.");
280   case SP::CALL: break;
281   case SP::JMPLrr:
282   case SP::JMPLri:
283     assert(MI->getNumOperands() >= 2);
284     const MachineOperand &Reg = MI->getOperand(0);
285     assert(Reg.isReg() && "JMPL first operand is not a register.");
286     assert(Reg.isUse() && "JMPL first operand is not a use.");
287     RegUses.insert(Reg.getReg());
288 
289     const MachineOperand &RegOrImm = MI->getOperand(1);
290     if (RegOrImm.isImm())
291         break;
292     assert(RegOrImm.isReg() && "JMPLrr second operand is not a register.");
293     assert(RegOrImm.isUse() && "JMPLrr second operand is not a use.");
294     RegUses.insert(RegOrImm.getReg());
295     break;
296   }
297 }
298 
299 // Insert Defs and Uses of MI into the sets RegDefs and RegUses.
300 void Filler::insertDefsUses(MachineBasicBlock::iterator MI,
301                             SmallSet<unsigned, 32>& RegDefs,
302                             SmallSet<unsigned, 32>& RegUses)
303 {
304   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
305     const MachineOperand &MO = MI->getOperand(i);
306     if (!MO.isReg())
307       continue;
308 
309     unsigned Reg = MO.getReg();
310     if (Reg == 0)
311       continue;
312     if (MO.isDef())
313       RegDefs.insert(Reg);
314     if (MO.isUse()) {
315       // Implicit register uses of retl are return values and
316       // retl does not use them.
317       if (MO.isImplicit() && MI->getOpcode() == SP::RETL)
318         continue;
319       RegUses.insert(Reg);
320     }
321   }
322 }
323 
324 // returns true if the Reg or its alias is in the RegSet.
325 bool Filler::IsRegInSet(SmallSet<unsigned, 32>& RegSet, unsigned Reg)
326 {
327   // Check Reg and all aliased Registers.
328   for (MCRegAliasIterator AI(Reg, TM.getRegisterInfo(), true);
329        AI.isValid(); ++AI)
330     if (RegSet.count(*AI))
331       return true;
332   return false;
333 }
334 
335 // return true if the candidate is a delay filler.
336 bool Filler::isDelayFiller(MachineBasicBlock &MBB,
337                            MachineBasicBlock::iterator candidate)
338 {
339   if (candidate == MBB.begin())
340     return false;
341   if (candidate->getOpcode() == SP::UNIMP)
342     return true;
343   --candidate;
344   return candidate->hasDelaySlot();
345 }
346 
347 bool Filler::needsUnimp(MachineBasicBlock::iterator I, unsigned &StructSize)
348 {
349   if (!I->isCall())
350     return false;
351 
352   unsigned structSizeOpNum = 0;
353   switch (I->getOpcode()) {
354   default: llvm_unreachable("Unknown call opcode.");
355   case SP::CALL: structSizeOpNum = 1; break;
356   case SP::JMPLrr:
357   case SP::JMPLri: structSizeOpNum = 2; break;
358   case SP::TLS_CALL: return false;
359   }
360 
361   const MachineOperand &MO = I->getOperand(structSizeOpNum);
362   if (!MO.isImm())
363     return false;
364   StructSize = MO.getImm();
365   return true;
366 }
367 
368 static bool combineRestoreADD(MachineBasicBlock::iterator RestoreMI,
369                               MachineBasicBlock::iterator AddMI,
370                               const TargetInstrInfo *TII)
371 {
372   // Before:  add  <op0>, <op1>, %i[0-7]
373   //          restore %g0, %g0, %i[0-7]
374   //
375   // After :  restore <op0>, <op1>, %o[0-7]
376 
377   unsigned reg = AddMI->getOperand(0).getReg();
378   if (reg < SP::I0 || reg > SP::I7)
379     return false;
380 
381   // Erase RESTORE.
382   RestoreMI->eraseFromParent();
383 
384   // Change ADD to RESTORE.
385   AddMI->setDesc(TII->get((AddMI->getOpcode() == SP::ADDrr)
386                           ? SP::RESTORErr
387                           : SP::RESTOREri));
388 
389   // Map the destination register.
390   AddMI->getOperand(0).setReg(reg - SP::I0 + SP::O0);
391 
392   return true;
393 }
394 
395 static bool combineRestoreOR(MachineBasicBlock::iterator RestoreMI,
396                              MachineBasicBlock::iterator OrMI,
397                              const TargetInstrInfo *TII)
398 {
399   // Before:  or  <op0>, <op1>, %i[0-7]
400   //          restore %g0, %g0, %i[0-7]
401   //    and <op0> or <op1> is zero,
402   //
403   // After :  restore <op0>, <op1>, %o[0-7]
404 
405   unsigned reg = OrMI->getOperand(0).getReg();
406   if (reg < SP::I0 || reg > SP::I7)
407     return false;
408 
409   // check whether it is a copy.
410   if (OrMI->getOpcode() == SP::ORrr
411       && OrMI->getOperand(1).getReg() != SP::G0
412       && OrMI->getOperand(2).getReg() != SP::G0)
413     return false;
414 
415   if (OrMI->getOpcode() == SP::ORri
416       && OrMI->getOperand(1).getReg() != SP::G0
417       && (!OrMI->getOperand(2).isImm() || OrMI->getOperand(2).getImm() != 0))
418     return false;
419 
420   // Erase RESTORE.
421   RestoreMI->eraseFromParent();
422 
423   // Change OR to RESTORE.
424   OrMI->setDesc(TII->get((OrMI->getOpcode() == SP::ORrr)
425                          ? SP::RESTORErr
426                          : SP::RESTOREri));
427 
428   // Map the destination register.
429   OrMI->getOperand(0).setReg(reg - SP::I0 + SP::O0);
430 
431   return true;
432 }
433 
434 static bool combineRestoreSETHIi(MachineBasicBlock::iterator RestoreMI,
435                                  MachineBasicBlock::iterator SetHiMI,
436                                  const TargetInstrInfo *TII)
437 {
438   // Before:  sethi imm3, %i[0-7]
439   //          restore %g0, %g0, %g0
440   //
441   // After :  restore %g0, (imm3<<10), %o[0-7]
442 
443   unsigned reg = SetHiMI->getOperand(0).getReg();
444   if (reg < SP::I0 || reg > SP::I7)
445     return false;
446 
447   if (!SetHiMI->getOperand(1).isImm())
448     return false;
449 
450   int64_t imm = SetHiMI->getOperand(1).getImm();
451 
452   // Is it a 3 bit immediate?
453   if (!isInt<3>(imm))
454     return false;
455 
456   // Make it a 13 bit immediate.
457   imm = (imm << 10) & 0x1FFF;
458 
459   assert(RestoreMI->getOpcode() == SP::RESTORErr);
460 
461   RestoreMI->setDesc(TII->get(SP::RESTOREri));
462 
463   RestoreMI->getOperand(0).setReg(reg - SP::I0 + SP::O0);
464   RestoreMI->getOperand(1).setReg(SP::G0);
465   RestoreMI->getOperand(2).ChangeToImmediate(imm);
466 
467 
468   // Erase the original SETHI.
469   SetHiMI->eraseFromParent();
470 
471   return true;
472 }
473 
474 bool Filler::tryCombineRestoreWithPrevInst(MachineBasicBlock &MBB,
475                                         MachineBasicBlock::iterator MBBI)
476 {
477   // No previous instruction.
478   if (MBBI == MBB.begin())
479     return false;
480 
481   // assert that MBBI is a "restore %g0, %g0, %g0".
482   assert(MBBI->getOpcode() == SP::RESTORErr
483          && MBBI->getOperand(0).getReg() == SP::G0
484          && MBBI->getOperand(1).getReg() == SP::G0
485          && MBBI->getOperand(2).getReg() == SP::G0);
486 
487   MachineBasicBlock::iterator PrevInst = MBBI; --PrevInst;
488 
489   // It cannot combine with a delay filler.
490   if (isDelayFiller(MBB, PrevInst))
491     return false;
492 
493   const TargetInstrInfo *TII = TM.getInstrInfo();
494 
495   switch (PrevInst->getOpcode()) {
496   default: break;
497   case SP::ADDrr:
498   case SP::ADDri: return combineRestoreADD(MBBI, PrevInst, TII); break;
499   case SP::ORrr:
500   case SP::ORri:  return combineRestoreOR(MBBI, PrevInst, TII); break;
501   case SP::SETHIi: return combineRestoreSETHIi(MBBI, PrevInst, TII); break;
502   }
503   // It cannot combine with the previous instruction.
504   return false;
505 }
506