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