lib/Target/MBlaze/MBlazeDelaySlotFiller.cpp

   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/ADT/Statistic.h"
  20 #include "llvm/CodeGen/MachineFunctionPass.h"
  21 #include "llvm/CodeGen/MachineInstrBuilder.h"
  22 #include "llvm/Support/CommandLine.h"
  23 #include "llvm/Support/Debug.h"
  24 #include "llvm/Support/ErrorHandling.h"
  25 #include "llvm/Support/raw_ostream.h"
  26 #include "llvm/Target/TargetInstrInfo.h"
  27
  28 using namespace llvm;
  29
  30 STATISTIC(FilledSlots, "Number of delay slots filled");
  31
  32 static 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
  38 namespace {
  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
  65 static 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
  91 static 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
 105 static 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
 178 static 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
 187 static 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
 203 static MachineBasicBlock::iterator
 204 findDelayInstr(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.
 228 bool 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
 251 FunctionPass *llvm::createMBlazeDelaySlotFillerPass(MBlazeTargetMachine &tm) {
 252   return new Filler(tm);
 253 }
 254