MipsDelaySlotFiller.cpp revision cd7319dc5f91ac81ab9d8505f34937e91bfcf65d 
1//===-- MipsDelaySlotFiller.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 fill 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/BitVector.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("Fill all delay slots with NOPs."),
37  cl::Hidden);
38
39// This option can be used to silence complaints by machine verifier passes.
40static cl::opt<bool> SkipDelaySlotFiller(
41  "skip-mips-delay-filler",
42  cl::init(false),
43  cl::desc("Skip MIPS' delay slot filling pass."),
44  cl::Hidden);
45
46namespace {
47  class Filler : public MachineFunctionPass {
48  public:
49    Filler(TargetMachine &tm)
50      : MachineFunctionPass(ID), TM(tm), TII(tm.getInstrInfo()) { }
51
52    virtual const char *getPassName() const {
53      return "Mips Delay Slot Filler";
54    }
55
56    bool runOnMachineFunction(MachineFunction &F) {
57      if (SkipDelaySlotFiller)
58        return false;
59
60      bool Changed = false;
61      for (MachineFunction::iterator FI = F.begin(), FE = F.end();
62           FI != FE; ++FI)
63        Changed |= runOnMachineBasicBlock(*FI);
64      return Changed;
65    }
66
67  private:
68    typedef MachineBasicBlock::iterator Iter;
69    typedef MachineBasicBlock::reverse_iterator ReverseIter;
70
71    bool runOnMachineBasicBlock(MachineBasicBlock &MBB);
72
73    /// Initialize RegDefs and RegUses.
74    void initRegDefsUses(const MachineInstr &MI, BitVector &RegDefs,
75                         BitVector &RegUses) const;
76
77    bool isRegInSet(const BitVector &RegSet, unsigned Reg) const;
78
79    bool checkRegDefsUses(const BitVector &RegDefs, const BitVector &RegUses,
80                          BitVector &NewDefs, BitVector &NewUses,
81                          unsigned Reg, bool IsDef) const;
82
83    bool checkRegDefsUses(BitVector &RegDefs, BitVector &RegUses,
84                          const MachineInstr &MI, unsigned Begin,
85                          unsigned End) const;
86
87    /// This function checks if it is valid to move Candidate to the delay slot
88    /// and returns true if it isn't. It also updates load and store flags and
89    /// register defs and uses.
90    bool delayHasHazard(const MachineInstr &Candidate, bool &SawLoad,
91                        bool &SawStore, BitVector &RegDefs,
92                        BitVector &RegUses) const;
93
94    bool findDelayInstr(MachineBasicBlock &MBB, Iter slot, Iter &Filler) const;
95
96    bool terminateSearch(const MachineInstr &Candidate) const;
97
98    TargetMachine &TM;
99    const TargetInstrInfo *TII;
100
101    static char ID;
102  };
103  char Filler::ID = 0;
104} // end of anonymous namespace
105
106/// runOnMachineBasicBlock - Fill in delay slots for the given basic block.
107/// We assume there is only one delay slot per delayed instruction.
108bool Filler::runOnMachineBasicBlock(MachineBasicBlock &MBB) {
109  bool Changed = false;
110
111  for (Iter I = MBB.begin(); I != MBB.end(); ++I) {
112    if (!I->hasDelaySlot())
113      continue;
114
115    ++FilledSlots;
116    Changed = true;
117    Iter D;
118
119    // Delay slot filling is disabled at -O0.
120    if (!DisableDelaySlotFiller && (TM.getOptLevel() != CodeGenOpt::None) &&
121        findDelayInstr(MBB, I, D)) {
122      MBB.splice(llvm::next(I), &MBB, D);
123      ++UsefulSlots;
124    } else
125      BuildMI(MBB, llvm::next(I), I->getDebugLoc(), TII->get(Mips::NOP));
126
127    // Bundle the delay slot filler to the instruction with the delay slot.
128    MIBundleBuilder(MBB, I, llvm::next(llvm::next(I)));
129  }
130
131  return Changed;
132}
133
134/// createMipsDelaySlotFillerPass - Returns a pass that fills in delay
135/// slots in Mips MachineFunctions
136FunctionPass *llvm::createMipsDelaySlotFillerPass(MipsTargetMachine &tm) {
137  return new Filler(tm);
138}
139
140bool Filler::findDelayInstr(MachineBasicBlock &MBB, Iter Slot,
141                            Iter &Filler) const {
142  unsigned NumRegs = TM.getRegisterInfo()->getNumRegs();
143  BitVector RegDefs(NumRegs), RegUses(NumRegs);
144
145  initRegDefsUses(*Slot, RegDefs, RegUses);
146
147  bool SawLoad = false;
148  bool SawStore = false;
149
150  for (ReverseIter I(Slot); I != MBB.rend(); ++I) {
151    // skip debug value
152    if (I->isDebugValue())
153      continue;
154
155    if (terminateSearch(*I))
156      break;
157
158    if (delayHasHazard(*I, SawLoad, SawStore, RegDefs, RegUses))
159      continue;
160
161    Filler = llvm::next(I).base();
162    return true;
163  }
164
165  return false;
166}
167
168bool Filler::checkRegDefsUses(const BitVector &RegDefs,
169                              const BitVector &RegUses,
170                              BitVector &NewDefs, BitVector &NewUses,
171                              unsigned Reg, bool IsDef) const {
172  if (IsDef) {
173    NewDefs.set(Reg);
174    // check whether Reg has already been defined or used.
175    return (isRegInSet(RegDefs, Reg) || isRegInSet(RegUses, Reg));
176  }
177
178  NewUses.set(Reg);
179  // check whether Reg has already been defined.
180  return isRegInSet(RegDefs, Reg);
181}
182
183bool Filler::checkRegDefsUses(BitVector &RegDefs, BitVector &RegUses,
184                              const MachineInstr &MI, unsigned Begin,
185                              unsigned End) const {
186  unsigned NumRegs = TM.getRegisterInfo()->getNumRegs();
187  BitVector NewDefs(NumRegs), NewUses(NumRegs);
188  bool HasHazard = false;
189
190  for (unsigned I = Begin; I != End; ++I) {
191    const MachineOperand &MO = MI.getOperand(I);
192
193    if (MO.isReg() && MO.getReg())
194      HasHazard |= checkRegDefsUses(RegDefs, RegUses, NewDefs, NewUses,
195                                    MO.getReg(), MO.isDef());
196  }
197
198  RegDefs |= NewDefs;
199  RegUses |= NewUses;
200
201  return HasHazard;
202}
203
204bool Filler::delayHasHazard(const MachineInstr &Candidate, bool &SawLoad,
205                            bool &SawStore, BitVector &RegDefs,
206                            BitVector &RegUses) const {
207  bool HasHazard = (Candidate.isImplicitDef() || Candidate.isKill());
208
209  // Loads or stores cannot be moved past a store to the delay slot
210  // and stores cannot be moved past a load.
211  if (Candidate.mayStore()) {
212    HasHazard |= SawStore | SawLoad;
213    SawStore = true;
214  } else if (Candidate.mayLoad()) {
215    HasHazard |= SawStore;
216    SawLoad = true;
217  }
218
219  assert((!Candidate.isCall() && !Candidate.isReturn()) &&
220         "Cannot put calls or returns in delay slot.");
221
222  HasHazard |= checkRegDefsUses(RegDefs, RegUses, Candidate, 0,
223                                Candidate.getNumOperands());
224
225  return HasHazard;
226}
227
228void Filler::initRegDefsUses(const MachineInstr &MI, BitVector &RegDefs,
229                             BitVector &RegUses) const {
230  // Add all register operands which are explicit and non-variadic.
231  checkRegDefsUses(RegDefs, RegUses, MI, 0, MI.getDesc().getNumOperands());
232
233  // If MI is a call, add RA to RegDefs to prevent users of RA from going into
234  // delay slot.
235  if (MI.isCall())
236    RegDefs.set(Mips::RA);
237
238  // Add all implicit register operands of branch instructions except
239  // register AT.
240  if (MI.isBranch()) {
241    checkRegDefsUses(RegDefs, RegUses, MI, MI.getDesc().getNumOperands(),
242                     MI.getNumOperands());
243    RegDefs.reset(Mips::AT);
244  }
245}
246
247//returns true if the Reg or its alias is in the RegSet.
248bool Filler::isRegInSet(const BitVector &RegSet, unsigned Reg) const {
249  // Check Reg and all aliased Registers.
250  for (MCRegAliasIterator AI(Reg, TM.getRegisterInfo(), true);
251       AI.isValid(); ++AI)
252    if (RegSet.test(*AI))
253      return true;
254  return false;
255}
256
257bool Filler::terminateSearch(const MachineInstr &Candidate) const {
258  return (Candidate.isTerminator() || Candidate.isCall() ||
259          Candidate.isLabel() || Candidate.isInlineAsm() ||
260          Candidate.hasUnmodeledSideEffects());
261}
262