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