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