contrib/llvm/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/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
  28 using namespace llvm;
  29
  30 STATISTIC(FilledSlots, "Number of delay slots filled");
  31
  32 namespace llvm {
  33 cl::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
  40 namespace {
  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
  67 static 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
  93 static 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
 107 static 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
 181 static 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
 190 static 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
 206 static MachineBasicBlock::iterator
 207 findDelayInstr(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.
 232 bool 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
 255 FunctionPass *llvm::createMBlazeDelaySlotFillerPass(MBlazeTargetMachine &tm) {
 256   return new Filler(tm);
 257 }
 258