DelaySlotFiller.cpp revision 530086925695f074b0e1e38a0d88ee6a4c91c54c 
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    const TargetInstrInfo *TII;
43
44    static char ID;
45    Filler(TargetMachine &tm)
46      : MachineFunctionPass(ID), TM(tm), TII(tm.getInstrInfo()) { }
47
48    virtual const char *getPassName() const {
49      return "SPARC Delay Slot Filler";
50    }
51
52    bool runOnMachineBasicBlock(MachineBasicBlock &MBB);
53    bool runOnMachineFunction(MachineFunction &F) {
54      bool Changed = false;
55      for (MachineFunction::iterator FI = F.begin(), FE = F.end();
56           FI != FE; ++FI)
57        Changed |= runOnMachineBasicBlock(*FI);
58      return Changed;
59    }
60
61    bool isDelayFiller(MachineBasicBlock &MBB,
62                       MachineBasicBlock::iterator candidate);
63
64    void insertCallDefsUses(MachineBasicBlock::iterator MI,
65                            SmallSet<unsigned, 32>& RegDefs,
66                            SmallSet<unsigned, 32>& RegUses);
67
68    void insertDefsUses(MachineBasicBlock::iterator MI,
69                        SmallSet<unsigned, 32>& RegDefs,
70                        SmallSet<unsigned, 32>& RegUses);
71
72    bool IsRegInSet(SmallSet<unsigned, 32>& RegSet,
73                    unsigned Reg);
74
75    bool delayHasHazard(MachineBasicBlock::iterator candidate,
76                        bool &sawLoad, bool &sawStore,
77                        SmallSet<unsigned, 32> &RegDefs,
78                        SmallSet<unsigned, 32> &RegUses);
79
80    MachineBasicBlock::iterator
81    findDelayInstr(MachineBasicBlock &MBB, MachineBasicBlock::iterator slot);
82
83    bool needsUnimp(MachineBasicBlock::iterator I, unsigned &StructSize);
84
85  };
86  char Filler::ID = 0;
87} // end of anonymous namespace
88
89/// createSparcDelaySlotFillerPass - Returns a pass that fills in delay
90/// slots in Sparc MachineFunctions
91///
92FunctionPass *llvm::createSparcDelaySlotFillerPass(TargetMachine &tm) {
93  return new Filler(tm);
94}
95
96
97/// runOnMachineBasicBlock - Fill in delay slots for the given basic block.
98/// We assume there is only one delay slot per delayed instruction.
99///
100bool Filler::runOnMachineBasicBlock(MachineBasicBlock &MBB) {
101  bool Changed = false;
102
103  for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ++I)
104    if (I->hasDelaySlot()) {
105      MachineBasicBlock::iterator D = MBB.end();
106      MachineBasicBlock::iterator J = I;
107
108      if (!DisableDelaySlotFiller)
109        D = findDelayInstr(MBB, I);
110
111      ++FilledSlots;
112      Changed = true;
113
114      if (D == MBB.end())
115        BuildMI(MBB, ++J, I->getDebugLoc(), TII->get(SP::NOP));
116      else
117        MBB.splice(++J, &MBB, D);
118      unsigned structSize = 0;
119      if (needsUnimp(I, structSize)) {
120        MachineBasicBlock::iterator J = I;
121        ++J; //skip the delay filler.
122        BuildMI(MBB, ++J, I->getDebugLoc(),
123                TII->get(SP::UNIMP)).addImm(structSize);
124      }
125    }
126  return Changed;
127}
128
129MachineBasicBlock::iterator
130Filler::findDelayInstr(MachineBasicBlock &MBB,
131                       MachineBasicBlock::iterator slot)
132{
133  SmallSet<unsigned, 32> RegDefs;
134  SmallSet<unsigned, 32> RegUses;
135  bool sawLoad = false;
136  bool sawStore = false;
137
138  if (slot == MBB.begin())
139    return MBB.end();
140
141  if (slot->getOpcode() == SP::RET)
142    return MBB.end();
143
144  if (slot->getOpcode() == SP::RETL) {
145    MachineBasicBlock::iterator J = slot;
146    --J;
147
148    if (J->getOpcode() == SP::RESTORErr
149        || J->getOpcode() == SP::RESTOREri) {
150      //change retl to ret
151      slot->setDesc(TII->get(SP::RET));
152      return J;
153    }
154  }
155
156  //Call's delay filler can def some of call's uses.
157  if (slot->isCall())
158    insertCallDefsUses(slot, RegDefs, RegUses);
159  else
160    insertDefsUses(slot, RegDefs, RegUses);
161
162  bool done = false;
163
164  MachineBasicBlock::iterator I = slot;
165
166  while (!done) {
167    done = (I == MBB.begin());
168
169    if (!done)
170      --I;
171
172    // skip debug value
173    if (I->isDebugValue())
174      continue;
175
176
177    if (I->hasUnmodeledSideEffects()
178        || I->isInlineAsm()
179        || I->isLabel()
180        || I->hasDelaySlot()
181        || isDelayFiller(MBB, I))
182      break;
183
184    if (delayHasHazard(I, sawLoad, sawStore, RegDefs, RegUses)) {
185      insertDefsUses(I, RegDefs, RegUses);
186      continue;
187    }
188
189    return I;
190  }
191  return MBB.end();
192}
193
194bool Filler::delayHasHazard(MachineBasicBlock::iterator candidate,
195                            bool &sawLoad,
196                            bool &sawStore,
197                            SmallSet<unsigned, 32> &RegDefs,
198                            SmallSet<unsigned, 32> &RegUses)
199{
200
201  if (candidate->isImplicitDef() || candidate->isKill())
202    return true;
203
204  if (candidate->mayLoad()) {
205    sawLoad = true;
206    if (sawStore)
207      return true;
208  }
209
210  if (candidate->mayStore()) {
211    if (sawStore)
212      return true;
213    sawStore = true;
214    if (sawLoad)
215      return true;
216  }
217
218  for (unsigned i = 0, e = candidate->getNumOperands(); i!= e; ++i) {
219    const MachineOperand &MO = candidate->getOperand(i);
220    if (!MO.isReg())
221      continue; // skip
222
223    unsigned Reg = MO.getReg();
224
225    if (MO.isDef()) {
226      //check whether Reg is defined or used before delay slot.
227      if (IsRegInSet(RegDefs, Reg) || IsRegInSet(RegUses, Reg))
228        return true;
229    }
230    if (MO.isUse()) {
231      //check whether Reg is defined before delay slot.
232      if (IsRegInSet(RegDefs, Reg))
233        return true;
234    }
235  }
236  return false;
237}
238
239
240void Filler::insertCallDefsUses(MachineBasicBlock::iterator MI,
241                                SmallSet<unsigned, 32>& RegDefs,
242                                SmallSet<unsigned, 32>& RegUses)
243{
244  //Call defines o7, which is visible to the instruction in delay slot.
245  RegDefs.insert(SP::O7);
246
247  switch(MI->getOpcode()) {
248  default: llvm_unreachable("Unknown opcode.");
249  case SP::CALL: break;
250  case SP::JMPLrr:
251  case SP::JMPLri:
252    assert(MI->getNumOperands() >= 2);
253    const MachineOperand &Reg = MI->getOperand(0);
254    assert(Reg.isReg() && "JMPL first operand is not a register.");
255    assert(Reg.isUse() && "JMPL first operand is not a use.");
256    RegUses.insert(Reg.getReg());
257
258    const MachineOperand &RegOrImm = MI->getOperand(1);
259    if (RegOrImm.isImm())
260        break;
261    assert(RegOrImm.isReg() && "JMPLrr second operand is not a register.");
262    assert(RegOrImm.isUse() && "JMPLrr second operand is not a use.");
263    RegUses.insert(RegOrImm.getReg());
264    break;
265  }
266}
267
268//Insert Defs and Uses of MI into the sets RegDefs and RegUses.
269void Filler::insertDefsUses(MachineBasicBlock::iterator MI,
270                            SmallSet<unsigned, 32>& RegDefs,
271                            SmallSet<unsigned, 32>& RegUses)
272{
273  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
274    const MachineOperand &MO = MI->getOperand(i);
275    if (!MO.isReg())
276      continue;
277
278    unsigned Reg = MO.getReg();
279    if (Reg == 0)
280      continue;
281    if (MO.isDef())
282      RegDefs.insert(Reg);
283    if (MO.isUse()) {
284      //Implicit register uses of retl are return values and
285      //retl does not use them.
286      if (MO.isImplicit() && MI->getOpcode() == SP::RETL)
287        continue;
288      RegUses.insert(Reg);
289    }
290  }
291}
292
293//returns true if the Reg or its alias is in the RegSet.
294bool Filler::IsRegInSet(SmallSet<unsigned, 32>& RegSet, unsigned Reg)
295{
296  // Check Reg and all aliased Registers.
297  for (MCRegAliasIterator AI(Reg, TM.getRegisterInfo(), true);
298       AI.isValid(); ++AI)
299    if (RegSet.count(*AI))
300      return true;
301  return false;
302}
303
304// return true if the candidate is a delay filler.
305bool Filler::isDelayFiller(MachineBasicBlock &MBB,
306                           MachineBasicBlock::iterator candidate)
307{
308  if (candidate == MBB.begin())
309    return false;
310  if (candidate->getOpcode() == SP::UNIMP)
311    return true;
312  --candidate;
313  return candidate->hasDelaySlot();
314}
315
316bool Filler::needsUnimp(MachineBasicBlock::iterator I, unsigned &StructSize)
317{
318  if (!I->isCall())
319    return false;
320
321  unsigned structSizeOpNum = 0;
322  switch (I->getOpcode()) {
323  default: llvm_unreachable("Unknown call opcode.");
324  case SP::CALL: structSizeOpNum = 1; break;
325  case SP::JMPLrr:
326  case SP::JMPLri: structSizeOpNum = 2; break;
327  }
328
329  const MachineOperand &MO = I->getOperand(structSizeOpNum);
330  if (!MO.isImm())
331    return false;
332  StructSize = MO.getImm();
333  return true;
334}
335