1//===-- DelaySlotFiller.cpp - MBlaze 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// A pass that attempts to fill instructions with delay slots. If no
11// instructions can be moved into the delay slot then a NOP is placed there.
12//
13//===----------------------------------------------------------------------===//
14
15#define DEBUG_TYPE "delay-slot-filler"
16
17#include "MBlaze.h"
18#include "MBlazeTargetMachine.h"
19#include "llvm/CodeGen/MachineFunctionPass.h"
20#include "llvm/CodeGen/MachineInstrBuilder.h"
21#include "llvm/Target/TargetInstrInfo.h"
22#include "llvm/ADT/Statistic.h"
23#include "llvm/Support/CommandLine.h"
24#include "llvm/Support/Debug.h"
25#include "llvm/Support/ErrorHandling.h"
26#include "llvm/Support/raw_ostream.h"
27
28using namespace llvm;
29
30STATISTIC(FilledSlots, "Number of delay slots filled");
31
32static cl::opt<bool> MBDisableDelaySlotFiller(
33  "disable-mblaze-delay-filler",
34  cl::init(false),
35  cl::desc("Disable the MBlaze delay slot filter."),
36  cl::Hidden);
37
38namespace {
39  struct Filler : public MachineFunctionPass {
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 "MBlaze 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  };
62  char Filler::ID = 0;
63} // end of anonymous namespace
64
65static bool hasImmInstruction(MachineBasicBlock::iterator &candidate) {
66    // Any instruction with an immediate mode operand greater than
67    // 16-bits requires an implicit IMM instruction.
68    unsigned numOper = candidate->getNumOperands();
69    for (unsigned op = 0; op < numOper; ++op) {
70        MachineOperand &mop = candidate->getOperand(op);
71
72        // The operand requires more than 16-bits to represent.
73        if (mop.isImm() && (mop.getImm() < -0x8000 || mop.getImm() > 0x7fff))
74          return true;
75
76        // We must assume that unknown immediate values require more than
77        // 16-bits to represent.
78        if (mop.isGlobal() || mop.isSymbol() || mop.isJTI() || mop.isCPI())
79          return true;
80
81        // FIXME: we could probably check to see if the FP value happens
82        //        to not need an IMM instruction. For now we just always
83        //        assume that FP values do.
84        if (mop.isFPImm())
85          return true;
86    }
87
88    return false;
89}
90
91static unsigned getLastRealOperand(MachineBasicBlock::iterator &instr) {
92  switch (instr->getOpcode()) {
93  default: return instr->getNumOperands();
94
95  // These instructions have a variable number of operands but the first two
96  // are the "real" operands that we care about during hazard detection.
97  case MBlaze::BRLID:
98  case MBlaze::BRALID:
99  case MBlaze::BRLD:
100  case MBlaze::BRALD:
101    return 2;
102  }
103}
104
105static bool delayHasHazard(MachineBasicBlock::iterator &candidate,
106                           MachineBasicBlock::iterator &slot) {
107  // Hazard check
108  MachineBasicBlock::iterator a = candidate;
109  MachineBasicBlock::iterator b = slot;
110
111  // MBB layout:-
112  //    candidate := a0 = operation(a1, a2)
113  //    ...middle bit...
114  //    slot := b0 = operation(b1, b2)
115
116  // Possible hazards:-/
117  // 1. a1 or a2 was written during the middle bit
118  // 2. a0 was read or written during the middle bit
119  // 3. a0 is one or more of {b0, b1, b2}
120  // 4. b0 is one or more of {a1, a2}
121  // 5. a accesses memory, and the middle bit
122  //    contains a store operation.
123  bool a_is_memory = candidate->mayLoad() || candidate->mayStore();
124
125  // Determine the number of operands in the slot instruction and in the
126  // candidate instruction.
127  const unsigned aend = getLastRealOperand(a);
128  const unsigned bend = getLastRealOperand(b);
129
130  // Check hazards type 1, 2 and 5 by scanning the middle bit
131  MachineBasicBlock::iterator m = a;
132  for (++m; m != b; ++m) {
133    for (unsigned aop = 0; aop<aend; ++aop) {
134      bool aop_is_reg = a->getOperand(aop).isReg();
135      if (!aop_is_reg) continue;
136
137      bool aop_is_def = a->getOperand(aop).isDef();
138      unsigned aop_reg = a->getOperand(aop).getReg();
139
140      const unsigned mend = getLastRealOperand(m);
141      for (unsigned mop = 0; mop<mend; ++mop) {
142        bool mop_is_reg = m->getOperand(mop).isReg();
143        if (!mop_is_reg) continue;
144
145        bool mop_is_def = m->getOperand(mop).isDef();
146        unsigned mop_reg = m->getOperand(mop).getReg();
147
148        if (aop_is_def && (mop_reg == aop_reg))
149            return true; // Hazard type 2, because aop = a0
150        else if (mop_is_def && (mop_reg == aop_reg))
151            return true; // Hazard type 1, because aop in {a1, a2}
152      }
153    }
154
155    // Check hazard type 5
156    if (a_is_memory && m->mayStore())
157      return true;
158  }
159
160  // Check hazard type 3 & 4
161  for (unsigned aop = 0; aop<aend; ++aop) {
162    if (a->getOperand(aop).isReg()) {
163      unsigned aop_reg = a->getOperand(aop).getReg();
164
165      for (unsigned bop = 0; bop<bend; ++bop) {
166        if (b->getOperand(bop).isReg() && !b->getOperand(bop).isImplicit()) {
167          unsigned bop_reg = b->getOperand(bop).getReg();
168          if (aop_reg == bop_reg)
169            return true;
170        }
171      }
172    }
173  }
174
175  return false;
176}
177
178static bool isDelayFiller(MachineBasicBlock &MBB,
179                          MachineBasicBlock::iterator candidate) {
180  if (candidate == MBB.begin())
181    return false;
182
183  --candidate;
184  return (candidate->hasDelaySlot());
185}
186
187static bool hasUnknownSideEffects(MachineBasicBlock::iterator &I) {
188  if (!I->hasUnmodeledSideEffects())
189    return false;
190
191  unsigned op = I->getOpcode();
192  if (op == MBlaze::ADDK || op == MBlaze::ADDIK ||
193      op == MBlaze::ADDC || op == MBlaze::ADDIC ||
194      op == MBlaze::ADDKC || op == MBlaze::ADDIKC ||
195      op == MBlaze::RSUBK || op == MBlaze::RSUBIK ||
196      op == MBlaze::RSUBC || op == MBlaze::RSUBIC ||
197      op == MBlaze::RSUBKC || op == MBlaze::RSUBIKC)
198    return false;
199
200  return true;
201}
202
203static MachineBasicBlock::iterator
204findDelayInstr(MachineBasicBlock &MBB,MachineBasicBlock::iterator slot) {
205  MachineBasicBlock::iterator I = slot;
206  while (true) {
207    if (I == MBB.begin())
208      break;
209
210    --I;
211    if (I->hasDelaySlot() || I->isBranch() || isDelayFiller(MBB,I) ||
212        I->isCall() || I->isReturn() || I->isBarrier() ||
213        hasUnknownSideEffects(I))
214      break;
215
216    if (hasImmInstruction(I) || delayHasHazard(I,slot))
217      continue;
218
219    return I;
220  }
221
222  return MBB.end();
223}
224
225/// runOnMachineBasicBlock - Fill in delay slots for the given basic block.
226/// Currently, we fill delay slots with NOPs. We assume there is only one
227/// delay slot per delayed instruction.
228bool Filler::runOnMachineBasicBlock(MachineBasicBlock &MBB) {
229  bool Changed = false;
230  for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ++I)
231    if (I->hasDelaySlot()) {
232      MachineBasicBlock::iterator D = MBB.end();
233      MachineBasicBlock::iterator J = I;
234
235      if (!MBDisableDelaySlotFiller)
236        D = findDelayInstr(MBB,I);
237
238      ++FilledSlots;
239      Changed = true;
240
241      if (D == MBB.end())
242        BuildMI(MBB, ++J, I->getDebugLoc(), TII->get(MBlaze::NOP));
243      else
244        MBB.splice(++J, &MBB, D);
245    }
246  return Changed;
247}
248
249/// createMBlazeDelaySlotFillerPass - Returns a pass that fills in delay
250/// slots in MBlaze MachineFunctions
251FunctionPass *llvm::createMBlazeDelaySlotFillerPass(MBlazeTargetMachine &tm) {
252  return new Filler(tm);
253}
254
255