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 {
  33   struct Filler : public MachineFunctionPass {
  34
  35     TargetMachine &TM;
  36     const TargetInstrInfo *TII;
  37
  38     static char ID;
  39     Filler(TargetMachine &tm)
  40       : MachineFunctionPass(ID), TM(tm), TII(tm.getInstrInfo()) { }
  41
  42     virtual const char *getPassName() const {
  43       return "MBlaze Delay Slot Filler";
  44     }
  45
  46     bool runOnMachineBasicBlock(MachineBasicBlock &MBB);
  47     bool runOnMachineFunction(MachineFunction &F) {
  48       bool Changed = false;
  49       for (MachineFunction::iterator FI = F.begin(), FE = F.end();
  50            FI != FE; ++FI)
  51         Changed |= runOnMachineBasicBlock(*FI);
  52       return Changed;
  53     }
  54
  55   };
  56   char Filler::ID = 0;
  57 } // end of anonymous namespace
  58
  59 static bool hasImmInstruction(MachineBasicBlock::iterator &candidate) {
  60     // Any instruction with an immediate mode operand greater than
  61     // 16-bits requires an implicit IMM instruction.
  62     unsigned numOper = candidate->getNumOperands();
  63     for (unsigned op = 0; op < numOper; ++op) {
  64         if (candidate->getOperand(op).isImm() &&
  65             (candidate->getOperand(op).getImm() & 0xFFFFFFFFFFFF0000LL) != 0)
  66             return true;
  67
  68         // FIXME: we could probably check to see if the FP value happens
  69         //        to not need an IMM instruction. For now we just always
  70         //        assume that FP values always do.
  71         if (candidate->getOperand(op).isFPImm())
  72             return true;
  73     }
  74
  75     return false;
  76 }
  77
  78 static bool delayHasHazard(MachineBasicBlock::iterator &candidate,
  79                            MachineBasicBlock::iterator &slot) {
  80     // Loop over all of the operands in the branch instruction
  81     // and make sure that none of them are defined by the
  82     // candidate instruction.
  83     unsigned numOper = slot->getNumOperands();
  84     for (unsigned op = 0; op < numOper; ++op) {
  85         if (!slot->getOperand(op).isReg() ||
  86             !slot->getOperand(op).isUse() ||
  87             slot->getOperand(op).isImplicit())
  88             continue;
  89
  90         unsigned cnumOper = candidate->getNumOperands();
  91         for (unsigned cop = 0; cop < cnumOper; ++cop) {
  92             if (candidate->getOperand(cop).isReg() &&
  93                 candidate->getOperand(cop).isDef() &&
  94                 candidate->getOperand(cop).getReg() ==
  95                 slot->getOperand(op).getReg())
  96                 return true;
  97         }
  98     }
  99
 100     // There are no hazards between the two instructions
 101     return false;
 102 }
 103
 104 static bool usedBeforeDelaySlot(MachineBasicBlock::iterator &candidate,
 105                                 MachineBasicBlock::iterator &slot) {
 106   MachineBasicBlock::iterator I = candidate;
 107   for (++I; I != slot; ++I) {
 108         unsigned numOper = I->getNumOperands();
 109         for (unsigned op = 0; op < numOper; ++op) {
 110             if (I->getOperand(op).isReg() &&
 111                 I->getOperand(op).isUse()) {
 112                 unsigned reg = I->getOperand(op).getReg();
 113                 unsigned cops = candidate->getNumOperands();
 114                 for (unsigned cop = 0; cop < cops; ++cop) {
 115                     if (candidate->getOperand(cop).isReg() &&
 116                         candidate->getOperand(cop).isDef() &&
 117                         candidate->getOperand(cop).getReg() == reg)
 118                         return true;
 119                 }
 120             }
 121         }
 122   }
 123
 124   return false;
 125 }
 126
 127 static bool isDelayFiller(MachineBasicBlock &MBB,
 128                           MachineBasicBlock::iterator candidate) {
 129   if (candidate == MBB.begin())
 130     return false;
 131
 132   TargetInstrDesc brdesc = (--candidate)->getDesc();
 133   return (brdesc.hasDelaySlot());
 134 }
 135
 136 static MachineBasicBlock::iterator
 137 findDelayInstr(MachineBasicBlock &MBB,MachineBasicBlock::iterator slot) {
 138   MachineBasicBlock::iterator I = slot;
 139   while (true) {
 140     if (I == MBB.begin())
 141       break;
 142
 143     --I;
 144     TargetInstrDesc desc = I->getDesc();
 145     if (desc.hasDelaySlot() || desc.isBranch() || isDelayFiller(MBB,I))
 146       break;
 147
 148     if (desc.mayLoad() || desc.mayStore() || hasImmInstruction(I) ||
 149         delayHasHazard(I,slot) || usedBeforeDelaySlot(I,slot))
 150       continue;
 151
 152     return I;
 153   }
 154
 155   return MBB.end();
 156 }
 157
 158 /// runOnMachineBasicBlock - Fill in delay slots for the given basic block.
 159 /// Currently, we fill delay slots with NOPs. We assume there is only one
 160 /// delay slot per delayed instruction.
 161 bool Filler::runOnMachineBasicBlock(MachineBasicBlock &MBB) {
 162   bool Changed = false;
 163   for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ++I)
 164     if (I->getDesc().hasDelaySlot()) {
 165       MachineBasicBlock::iterator D = findDelayInstr(MBB,I);
 166       MachineBasicBlock::iterator J = I;
 167
 168       ++FilledSlots;
 169       Changed = true;
 170
 171       if (D == MBB.end())
 172         BuildMI(MBB, ++J, I->getDebugLoc(), TII->get(MBlaze::NOP));
 173       else
 174         MBB.splice(++J, &MBB, D);
 175     }
 176   return Changed;
 177 }
 178
 179 /// createMBlazeDelaySlotFillerPass - Returns a pass that fills in delay
 180 /// slots in MBlaze MachineFunctions
 181 FunctionPass *llvm::createMBlazeDelaySlotFillerPass(MBlazeTargetMachine &tm) {
 182   return new Filler(tm);
 183 }
 184