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