MipsDelaySlotFiller.cpp revision 226633 
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> EnableDelaySlotFiller(
34  "enable-mips-delay-filler",
35  cl::init(false),
36  cl::desc("Fill the Mips delay slots useful instructions."),
37  cl::Hidden);
38
39namespace {
40  struct Filler : public MachineFunctionPass {
41
42    TargetMachine &TM;
43    const TargetInstrInfo *TII;
44    MachineBasicBlock::iterator LastFiller;
45
46    static char ID;
47    Filler(TargetMachine &tm)
48      : MachineFunctionPass(ID), TM(tm), TII(tm.getInstrInfo()) { }
49
50    virtual const char *getPassName() const {
51      return "Mips Delay Slot Filler";
52    }
53
54    bool runOnMachineBasicBlock(MachineBasicBlock &MBB);
55    bool runOnMachineFunction(MachineFunction &F) {
56      bool Changed = false;
57      for (MachineFunction::iterator FI = F.begin(), FE = F.end();
58           FI != FE; ++FI)
59        Changed |= runOnMachineBasicBlock(*FI);
60      return Changed;
61    }
62
63    bool isDelayFiller(MachineBasicBlock &MBB,
64                       MachineBasicBlock::iterator candidate);
65
66    void insertCallUses(MachineBasicBlock::iterator MI,
67                        SmallSet<unsigned, 32>& RegDefs,
68                        SmallSet<unsigned, 32>& RegUses);
69
70    void insertDefsUses(MachineBasicBlock::iterator MI,
71                        SmallSet<unsigned, 32>& RegDefs,
72                        SmallSet<unsigned, 32>& RegUses);
73
74    bool IsRegInSet(SmallSet<unsigned, 32>& RegSet,
75                    unsigned Reg);
76
77    bool delayHasHazard(MachineBasicBlock::iterator candidate,
78                        bool &sawLoad, bool &sawStore,
79                        SmallSet<unsigned, 32> &RegDefs,
80                        SmallSet<unsigned, 32> &RegUses);
81
82    bool
83    findDelayInstr(MachineBasicBlock &MBB, MachineBasicBlock::iterator slot,
84                   MachineBasicBlock::iterator &Filler);
85
86
87  };
88  char Filler::ID = 0;
89} // end of anonymous namespace
90
91/// runOnMachineBasicBlock - Fill in delay slots for the given basic block.
92/// We assume there is only one delay slot per delayed instruction.
93bool Filler::
94runOnMachineBasicBlock(MachineBasicBlock &MBB) {
95  bool Changed = false;
96  LastFiller = MBB.end();
97
98  for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ++I)
99    if (I->getDesc().hasDelaySlot()) {
100      ++FilledSlots;
101      Changed = true;
102
103      MachineBasicBlock::iterator D;
104
105      if (EnableDelaySlotFiller && findDelayInstr(MBB, I, D)) {
106        MBB.splice(llvm::next(I), &MBB, D);
107        ++UsefulSlots;
108      }
109      else
110        BuildMI(MBB, llvm::next(I), I->getDebugLoc(), TII->get(Mips::NOP));
111
112      // Record the filler instruction that filled the delay slot.
113      // The instruction after it will be visited in the next iteration.
114      LastFiller = ++I;
115     }
116  return Changed;
117
118}
119
120/// createMipsDelaySlotFillerPass - Returns a pass that fills in delay
121/// slots in Mips MachineFunctions
122FunctionPass *llvm::createMipsDelaySlotFillerPass(MipsTargetMachine &tm) {
123  return new Filler(tm);
124}
125
126bool Filler::findDelayInstr(MachineBasicBlock &MBB,
127                            MachineBasicBlock::iterator slot,
128                            MachineBasicBlock::iterator &Filler) {
129  SmallSet<unsigned, 32> RegDefs;
130  SmallSet<unsigned, 32> RegUses;
131
132  insertDefsUses(slot, RegDefs, RegUses);
133
134  bool sawLoad = false;
135  bool sawStore = false;
136
137  for (MachineBasicBlock::reverse_iterator I(slot); I != MBB.rend(); ++I) {
138    // skip debug value
139    if (I->isDebugValue())
140      continue;
141
142    // Convert to forward iterator.
143    MachineBasicBlock::iterator FI(llvm::next(I).base());
144
145    if (I->hasUnmodeledSideEffects()
146        || I->isInlineAsm()
147        || I->isLabel()
148        || FI == LastFiller
149        || I->getDesc().isPseudo()
150        //
151        // Should not allow:
152        // ERET, DERET or WAIT, PAUSE. Need to add these to instruction
153        // list. TBD.
154        )
155      break;
156
157    if (delayHasHazard(FI, sawLoad, sawStore, RegDefs, RegUses)) {
158      insertDefsUses(FI, RegDefs, RegUses);
159      continue;
160    }
161
162    Filler = FI;
163    return true;
164  }
165
166  return false;
167}
168
169bool Filler::delayHasHazard(MachineBasicBlock::iterator candidate,
170                            bool &sawLoad,
171                            bool &sawStore,
172                            SmallSet<unsigned, 32> &RegDefs,
173                            SmallSet<unsigned, 32> &RegUses) {
174  if (candidate->isImplicitDef() || candidate->isKill())
175    return true;
176
177  MCInstrDesc MCID = candidate->getDesc();
178  // Loads or stores cannot be moved past a store to the delay slot
179  // and stores cannot be moved past a load.
180  if (MCID.mayLoad()) {
181    if (sawStore)
182      return true;
183    sawLoad = true;
184  }
185
186  if (MCID.mayStore()) {
187    if (sawStore)
188      return true;
189    sawStore = true;
190    if (sawLoad)
191      return true;
192  }
193
194  assert((!MCID.isCall() && !MCID.isReturn()) &&
195         "Cannot put calls or returns in delay slot.");
196
197  for (unsigned i = 0, e = candidate->getNumOperands(); i!= e; ++i) {
198    const MachineOperand &MO = candidate->getOperand(i);
199    unsigned Reg;
200
201    if (!MO.isReg() || !(Reg = MO.getReg()))
202      continue; // skip
203
204    if (MO.isDef()) {
205      // check whether Reg is defined or used before delay slot.
206      if (IsRegInSet(RegDefs, Reg) || IsRegInSet(RegUses, Reg))
207        return true;
208    }
209    if (MO.isUse()) {
210      // check whether Reg is defined before delay slot.
211      if (IsRegInSet(RegDefs, Reg))
212        return true;
213    }
214  }
215  return false;
216}
217
218// Insert Defs and Uses of MI into the sets RegDefs and RegUses.
219void Filler::insertDefsUses(MachineBasicBlock::iterator MI,
220                            SmallSet<unsigned, 32>& RegDefs,
221                            SmallSet<unsigned, 32>& RegUses) {
222  // If MI is a call or return, just examine the explicit non-variadic operands.
223  MCInstrDesc MCID = MI->getDesc();
224  unsigned e = MCID.isCall() || MCID.isReturn() ? MCID.getNumOperands() :
225                                                  MI->getNumOperands();
226
227  // Add RA to RegDefs to prevent users of RA from going into delay slot.
228  if (MCID.isCall())
229    RegDefs.insert(Mips::RA);
230
231  for (unsigned i = 0; i != e; ++i) {
232    const MachineOperand &MO = MI->getOperand(i);
233    unsigned Reg;
234
235    if (!MO.isReg() || !(Reg = MO.getReg()))
236      continue;
237
238    if (MO.isDef())
239      RegDefs.insert(Reg);
240    else if (MO.isUse())
241      RegUses.insert(Reg);
242  }
243}
244
245//returns true if the Reg or its alias is in the RegSet.
246bool Filler::IsRegInSet(SmallSet<unsigned, 32>& RegSet, unsigned Reg) {
247  if (RegSet.count(Reg))
248    return true;
249  // check Aliased Registers
250  for (const unsigned *Alias = TM.getRegisterInfo()->getAliasSet(Reg);
251       *Alias; ++Alias)
252    if (RegSet.count(*Alias))
253      return true;
254
255  return false;
256}
257