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