DelaySlotFiller.cpp revision d6b4caf291aa8c3cd4bcb5f3b55b72621b506278 
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  MachineBasicBlock::iterator I = slot;
139
140  if (slot->getOpcode() == SP::RET)
141    return MBB.end();
142
143  if (slot->getOpcode() == SP::RETL) {
144    --I;
145    if (I->getOpcode() != SP::RESTORErr)
146      return MBB.end();
147    //change retl to ret
148    slot->setDesc(TII->get(SP::RET));
149    return I;
150  }
151
152  //Call's delay filler can def some of call's uses.
153  if (slot->isCall())
154    insertCallDefsUses(slot, RegDefs, RegUses);
155  else
156    insertDefsUses(slot, RegDefs, RegUses);
157
158  bool done = false;
159
160  while (!done) {
161    done = (I == MBB.begin());
162
163    if (!done)
164      --I;
165
166    // skip debug value
167    if (I->isDebugValue())
168      continue;
169
170
171    if (I->hasUnmodeledSideEffects()
172        || I->isInlineAsm()
173        || I->isLabel()
174        || I->hasDelaySlot()
175        || isDelayFiller(MBB, I))
176      break;
177
178    if (delayHasHazard(I, sawLoad, sawStore, RegDefs, RegUses)) {
179      insertDefsUses(I, RegDefs, RegUses);
180      continue;
181    }
182
183    return I;
184  }
185  return MBB.end();
186}
187
188bool Filler::delayHasHazard(MachineBasicBlock::iterator candidate,
189                            bool &sawLoad,
190                            bool &sawStore,
191                            SmallSet<unsigned, 32> &RegDefs,
192                            SmallSet<unsigned, 32> &RegUses)
193{
194
195  if (candidate->isImplicitDef() || candidate->isKill())
196    return true;
197
198  if (candidate->mayLoad()) {
199    sawLoad = true;
200    if (sawStore)
201      return true;
202  }
203
204  if (candidate->mayStore()) {
205    if (sawStore)
206      return true;
207    sawStore = true;
208    if (sawLoad)
209      return true;
210  }
211
212  for (unsigned i = 0, e = candidate->getNumOperands(); i!= e; ++i) {
213    const MachineOperand &MO = candidate->getOperand(i);
214    if (!MO.isReg())
215      continue; // skip
216
217    unsigned Reg = MO.getReg();
218
219    if (MO.isDef()) {
220      //check whether Reg is defined or used before delay slot.
221      if (IsRegInSet(RegDefs, Reg) || IsRegInSet(RegUses, Reg))
222        return true;
223    }
224    if (MO.isUse()) {
225      //check whether Reg is defined before delay slot.
226      if (IsRegInSet(RegDefs, Reg))
227        return true;
228    }
229  }
230  return false;
231}
232
233
234void Filler::insertCallDefsUses(MachineBasicBlock::iterator MI,
235                                SmallSet<unsigned, 32>& RegDefs,
236                                SmallSet<unsigned, 32>& RegUses)
237{
238  //Call defines o7, which is visible to the instruction in delay slot.
239  RegDefs.insert(SP::O7);
240
241  switch(MI->getOpcode()) {
242  default: llvm_unreachable("Unknown opcode.");
243  case SP::CALL: break;
244  case SP::JMPLrr:
245  case SP::JMPLri:
246    assert(MI->getNumOperands() >= 2);
247    const MachineOperand &Reg = MI->getOperand(0);
248    assert(Reg.isReg() && "JMPL first operand is not a register.");
249    assert(Reg.isUse() && "JMPL first operand is not a use.");
250    RegUses.insert(Reg.getReg());
251
252    const MachineOperand &RegOrImm = MI->getOperand(1);
253    if (RegOrImm.isImm())
254        break;
255    assert(RegOrImm.isReg() && "JMPLrr second operand is not a register.");
256    assert(RegOrImm.isUse() && "JMPLrr second operand is not a use.");
257    RegUses.insert(RegOrImm.getReg());
258    break;
259  }
260}
261
262//Insert Defs and Uses of MI into the sets RegDefs and RegUses.
263void Filler::insertDefsUses(MachineBasicBlock::iterator MI,
264                            SmallSet<unsigned, 32>& RegDefs,
265                            SmallSet<unsigned, 32>& RegUses)
266{
267  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
268    const MachineOperand &MO = MI->getOperand(i);
269    if (!MO.isReg())
270      continue;
271
272    unsigned Reg = MO.getReg();
273    if (Reg == 0)
274      continue;
275    if (MO.isDef())
276      RegDefs.insert(Reg);
277    if (MO.isUse())
278      RegUses.insert(Reg);
279
280  }
281}
282
283//returns true if the Reg or its alias is in the RegSet.
284bool Filler::IsRegInSet(SmallSet<unsigned, 32>& RegSet, unsigned Reg)
285{
286  // Check Reg and all aliased Registers.
287  for (MCRegAliasIterator AI(Reg, TM.getRegisterInfo(), true);
288       AI.isValid(); ++AI)
289    if (RegSet.count(*AI))
290      return true;
291  return false;
292}
293
294// return true if the candidate is a delay filler.
295bool Filler::isDelayFiller(MachineBasicBlock &MBB,
296                           MachineBasicBlock::iterator candidate)
297{
298  if (candidate == MBB.begin())
299    return false;
300  if (candidate->getOpcode() == SP::UNIMP)
301    return true;
302  --candidate;
303  return candidate->hasDelaySlot();
304}
305
306bool Filler::needsUnimp(MachineBasicBlock::iterator I, unsigned &StructSize)
307{
308  if (!I->isCall())
309    return false;
310
311  unsigned structSizeOpNum = 0;
312  switch (I->getOpcode()) {
313  default: llvm_unreachable("Unknown call opcode.");
314  case SP::CALL: structSizeOpNum = 1; break;
315  case SP::JMPLrr:
316  case SP::JMPLri: structSizeOpNum = 2; break;
317  }
318
319  const MachineOperand &MO = I->getOperand(structSizeOpNum);
320  if (!MO.isImm())
321    return false;
322  StructSize = MO.getImm();
323  return true;
324}
325