MipsDelaySlotFiller.cpp revision a032dbd62f46a40b2cf759ce0dd0ebd41ef0614c 
1//===-- DelaySlotFiller.cpp - Mips 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// Simple pass to fills delay slots with useful instructions.
11//
12//===----------------------------------------------------------------------===//
13
14#define DEBUG_TYPE "delay-slot-filler"
15
16#include "Mips.h"
17#include "MipsTargetMachine.h"
18#include "llvm/CodeGen/MachineFunctionPass.h"
19#include "llvm/CodeGen/MachineInstrBuilder.h"
20#include "llvm/Support/CommandLine.h"
21#include "llvm/Target/TargetMachine.h"
22#include "llvm/Target/TargetInstrInfo.h"
23#include "llvm/Target/TargetRegisterInfo.h"
24#include "llvm/ADT/SmallSet.h"
25#include "llvm/ADT/Statistic.h"
26
27using namespace llvm;
28
29STATISTIC(FilledSlots, "Number of delay slots filled");
30STATISTIC(UsefulSlots, "Number of delay slots filled with instructions that"
31                       " are not NOP.");
32
33static cl::opt<bool> DisableDelaySlotFiller(
34  "disable-mips-delay-filler",
35  cl::init(false),
36  cl::desc("Disable the delay slot filler, which attempts to fill the Mips"
37           "delay slots with useful instructions."),
38  cl::Hidden);
39
40// This option can be used to silence complaints by machine verifier passes.
41static cl::opt<bool> SkipDelaySlotFiller(
42  "skip-mips-delay-filler",
43  cl::init(false),
44  cl::desc("Skip MIPS' delay slot filling pass."),
45  cl::Hidden);
46
47namespace {
48  struct Filler : public MachineFunctionPass {
49    typedef MachineBasicBlock::instr_iterator InstrIter;
50    typedef MachineBasicBlock::reverse_instr_iterator ReverseInstrIter;
51
52    TargetMachine &TM;
53    const TargetInstrInfo *TII;
54    InstrIter LastFiller;
55
56    static char ID;
57    Filler(TargetMachine &tm)
58      : MachineFunctionPass(ID), TM(tm), TII(tm.getInstrInfo()) { }
59
60    virtual const char *getPassName() const {
61      return "Mips Delay Slot Filler";
62    }
63
64    bool runOnMachineBasicBlock(MachineBasicBlock &MBB);
65    bool runOnMachineFunction(MachineFunction &F) {
66      if (SkipDelaySlotFiller)
67        return false;
68
69      bool Changed = false;
70      for (MachineFunction::iterator FI = F.begin(), FE = F.end();
71           FI != FE; ++FI)
72        Changed |= runOnMachineBasicBlock(*FI);
73      return Changed;
74    }
75
76    bool isDelayFiller(MachineBasicBlock &MBB,
77                       InstrIter candidate);
78
79    void insertCallUses(InstrIter MI,
80                        SmallSet<unsigned, 32> &RegDefs,
81                        SmallSet<unsigned, 32> &RegUses);
82
83    void insertDefsUses(InstrIter MI,
84                        SmallSet<unsigned, 32> &RegDefs,
85                        SmallSet<unsigned, 32> &RegUses);
86
87    bool IsRegInSet(SmallSet<unsigned, 32> &RegSet,
88                    unsigned Reg);
89
90    bool delayHasHazard(InstrIter candidate,
91                        bool &sawLoad, bool &sawStore,
92                        SmallSet<unsigned, 32> &RegDefs,
93                        SmallSet<unsigned, 32> &RegUses);
94
95    bool
96    findDelayInstr(MachineBasicBlock &MBB, InstrIter slot,
97                   InstrIter &Filler);
98
99
100  };
101  char Filler::ID = 0;
102} // end of anonymous namespace
103
104/// runOnMachineBasicBlock - Fill in delay slots for the given basic block.
105/// We assume there is only one delay slot per delayed instruction.
106bool Filler::
107runOnMachineBasicBlock(MachineBasicBlock &MBB) {
108  bool Changed = false;
109  LastFiller = MBB.instr_end();
110
111  for (InstrIter I = MBB.instr_begin(); I != MBB.instr_end(); ++I)
112    if (I->hasDelaySlot()) {
113      ++FilledSlots;
114      Changed = true;
115
116      InstrIter D;
117
118      // Delay slot filling is disabled at -O0.
119      if (!DisableDelaySlotFiller && (TM.getOptLevel() != CodeGenOpt::None) &&
120          findDelayInstr(MBB, I, D)) {
121        MBB.splice(llvm::next(I), &MBB, D);
122        ++UsefulSlots;
123      } else
124        BuildMI(MBB, llvm::next(I), I->getDebugLoc(), TII->get(Mips::NOP));
125
126      // Record the filler instruction that filled the delay slot.
127      // The instruction after it will be visited in the next iteration.
128      LastFiller = ++I;
129
130      // Set InsideBundle bit so that the machine verifier doesn't expect this
131      // instruction to be a terminator.
132      LastFiller->setIsInsideBundle();
133     }
134  return Changed;
135
136}
137
138/// createMipsDelaySlotFillerPass - Returns a pass that fills in delay
139/// slots in Mips MachineFunctions
140FunctionPass *llvm::createMipsDelaySlotFillerPass(MipsTargetMachine &tm) {
141  return new Filler(tm);
142}
143
144bool Filler::findDelayInstr(MachineBasicBlock &MBB,
145                            InstrIter slot,
146                            InstrIter &Filler) {
147  SmallSet<unsigned, 32> RegDefs;
148  SmallSet<unsigned, 32> RegUses;
149
150  insertDefsUses(slot, RegDefs, RegUses);
151
152  bool sawLoad = false;
153  bool sawStore = false;
154
155  for (ReverseInstrIter I(slot); I != MBB.instr_rend(); ++I) {
156    // skip debug value
157    if (I->isDebugValue())
158      continue;
159
160    // Convert to forward iterator.
161    InstrIter FI(llvm::next(I).base());
162
163    if (I->hasUnmodeledSideEffects()
164        || I->isInlineAsm()
165        || I->isLabel()
166        || FI == LastFiller
167        || I->isPseudo()
168        //
169        // Should not allow:
170        // ERET, DERET or WAIT, PAUSE. Need to add these to instruction
171        // list. TBD.
172        )
173      break;
174
175    if (delayHasHazard(FI, sawLoad, sawStore, RegDefs, RegUses)) {
176      insertDefsUses(FI, RegDefs, RegUses);
177      continue;
178    }
179
180    Filler = FI;
181    return true;
182  }
183
184  return false;
185}
186
187bool Filler::delayHasHazard(InstrIter candidate,
188                            bool &sawLoad, bool &sawStore,
189                            SmallSet<unsigned, 32> &RegDefs,
190                            SmallSet<unsigned, 32> &RegUses) {
191  if (candidate->isImplicitDef() || candidate->isKill())
192    return true;
193
194  // Loads or stores cannot be moved past a store to the delay slot
195  // and stores cannot be moved past a load.
196  if (candidate->mayLoad()) {
197    if (sawStore)
198      return true;
199    sawLoad = true;
200  }
201
202  if (candidate->mayStore()) {
203    if (sawStore)
204      return true;
205    sawStore = true;
206    if (sawLoad)
207      return true;
208  }
209
210  assert((!candidate->isCall() && !candidate->isReturn()) &&
211         "Cannot put calls or returns in delay slot.");
212
213  for (unsigned i = 0, e = candidate->getNumOperands(); i!= e; ++i) {
214    const MachineOperand &MO = candidate->getOperand(i);
215    unsigned Reg;
216
217    if (!MO.isReg() || !(Reg = MO.getReg()))
218      continue; // skip
219
220    if (MO.isDef()) {
221      // check whether Reg is defined or used before delay slot.
222      if (IsRegInSet(RegDefs, Reg) || IsRegInSet(RegUses, Reg))
223        return true;
224    }
225    if (MO.isUse()) {
226      // check whether Reg is defined before delay slot.
227      if (IsRegInSet(RegDefs, Reg))
228        return true;
229    }
230  }
231  return false;
232}
233
234// Helper function for getting a MachineOperand's register number and adding it
235// to RegDefs or RegUses.
236static void insertDefUse(const MachineOperand &MO,
237                         SmallSet<unsigned, 32> &RegDefs,
238                         SmallSet<unsigned, 32> &RegUses,
239                         unsigned ExcludedReg = 0) {
240  unsigned Reg;
241
242  if (!MO.isReg() || !(Reg = MO.getReg()) || (Reg == ExcludedReg))
243    return;
244
245  if (MO.isDef())
246    RegDefs.insert(Reg);
247  else if (MO.isUse())
248    RegUses.insert(Reg);
249}
250
251// Insert Defs and Uses of MI into the sets RegDefs and RegUses.
252void Filler::insertDefsUses(InstrIter MI,
253                            SmallSet<unsigned, 32> &RegDefs,
254                            SmallSet<unsigned, 32> &RegUses) {
255  unsigned I, E = MI->getDesc().getNumOperands();
256
257  for (I = 0; I != E; ++I)
258    insertDefUse(MI->getOperand(I), RegDefs, RegUses);
259
260  // If MI is a call, add RA to RegDefs to prevent users of RA from going into
261  // delay slot.
262  if (MI->isCall()) {
263    RegDefs.insert(Mips::RA);
264    return;
265  }
266
267  // Return if MI is a return.
268  if (MI->isReturn())
269    return;
270
271  // Examine the implicit operands. Exclude register AT which is in the list of
272  // clobbered registers of branch instructions.
273  E = MI->getNumOperands();
274  for (; I != E; ++I)
275    insertDefUse(MI->getOperand(I), RegDefs, RegUses, Mips::AT);
276}
277
278//returns true if the Reg or its alias is in the RegSet.
279bool Filler::IsRegInSet(SmallSet<unsigned, 32> &RegSet, unsigned Reg) {
280  // Check Reg and all aliased Registers.
281  for (MCRegAliasIterator AI(Reg, TM.getRegisterInfo(), true);
282       AI.isValid(); ++AI)
283    if (RegSet.count(*AI))
284      return true;
285  return false;
286}
287