lib/Target/Mips/MipsDelaySlotFiller.cpp

   1 //===-- MipsDelaySlotFiller.cpp - Mips 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 // Simple pass to fill delay slots with useful instructions.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #define DEBUG_TYPE "delay-slot-filler"
  15
  16 #include "Mips.h"
  17 #include "MipsTargetMachine.h"
  18 #include "llvm/ADT/BitVector.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/Target/TargetInstrInfo.h"
  24 #include "llvm/Target/TargetMachine.h"
  25 #include "llvm/Target/TargetRegisterInfo.h"
  26
  27 using namespace llvm;
  28
  29 STATISTIC(FilledSlots, "Number of delay slots filled");
  30 STATISTIC(UsefulSlots, "Number of delay slots filled with instructions that"
  31                        " are not NOP.");
  32
  33 static cl::opt<bool> DisableDelaySlotFiller(
  34   "disable-mips-delay-filler",
  35   cl::init(false),
  36   cl::desc("Fill all delay slots with NOPs."),
  37   cl::Hidden);
  38
  39 // This option can be used to silence complaints by machine verifier passes.
  40 static cl::opt<bool> SkipDelaySlotFiller(
  41   "skip-mips-delay-filler",
  42   cl::init(false),
  43   cl::desc("Skip MIPS' delay slot filling pass."),
  44   cl::Hidden);
  45
  46 namespace {
  47   class Filler : public MachineFunctionPass {
  48   public:
  49     Filler(TargetMachine &tm)
  50       : MachineFunctionPass(ID), TM(tm), TII(tm.getInstrInfo()) { }
  51
  52     virtual const char *getPassName() const {
  53       return "Mips Delay Slot Filler";
  54     }
  55
  56     bool runOnMachineFunction(MachineFunction &F) {
  57       if (SkipDelaySlotFiller)
  58         return false;
  59
  60       bool Changed = false;
  61       for (MachineFunction::iterator FI = F.begin(), FE = F.end();
  62            FI != FE; ++FI)
  63         Changed |= runOnMachineBasicBlock(*FI);
  64       return Changed;
  65     }
  66
  67   private:
  68     typedef MachineBasicBlock::iterator Iter;
  69     typedef MachineBasicBlock::reverse_iterator ReverseIter;
  70
  71     bool runOnMachineBasicBlock(MachineBasicBlock &MBB);
  72
  73     /// Initialize RegDefs and RegUses.
  74     void initRegDefsUses(const MachineInstr &MI, BitVector &RegDefs,
  75                          BitVector &RegUses) const;
  76
  77     bool isRegInSet(const BitVector &RegSet, unsigned Reg) const;
  78
  79     bool checkRegDefsUses(const BitVector &RegDefs, const BitVector &RegUses,
  80                           BitVector &NewDefs, BitVector &NewUses,
  81                           unsigned Reg, bool IsDef) const;
  82
  83     bool checkRegDefsUses(BitVector &RegDefs, BitVector &RegUses,
  84                           const MachineInstr &MI, unsigned Begin,
  85                           unsigned End) const;
  86
  87     /// This function checks if it is valid to move Candidate to the delay slot
  88     /// and returns true if it isn't. It also updates load and store flags and
  89     /// register defs and uses.
  90     bool delayHasHazard(const MachineInstr &Candidate, bool &SawLoad,
  91                         bool &SawStore, BitVector &RegDefs,
  92                         BitVector &RegUses) const;
  93
  94     bool findDelayInstr(MachineBasicBlock &MBB, Iter slot, Iter &Filler) const;
  95
  96     bool terminateSearch(const MachineInstr &Candidate) const;
  97
  98     TargetMachine &TM;
  99     const TargetInstrInfo *TII;
 100
 101     static char ID;
 102   };
 103   char Filler::ID = 0;
 104 } // end of anonymous namespace
 105
 106 /// runOnMachineBasicBlock - Fill in delay slots for the given basic block.
 107 /// We assume there is only one delay slot per delayed instruction.
 108 bool Filler::runOnMachineBasicBlock(MachineBasicBlock &MBB) {
 109   bool Changed = false;
 110
 111   for (Iter I = MBB.begin(); I != MBB.end(); ++I) {
 112     if (!I->hasDelaySlot())
 113       continue;
 114
 115     ++FilledSlots;
 116     Changed = true;
 117     Iter D;
 118
 119     // Delay slot filling is disabled at -O0.
 120     if (!DisableDelaySlotFiller && (TM.getOptLevel() != CodeGenOpt::None) &&
 121         findDelayInstr(MBB, I, D)) {
 122       MBB.splice(llvm::next(I), &MBB, D);
 123       ++UsefulSlots;
 124     } else
 125       BuildMI(MBB, llvm::next(I), I->getDebugLoc(), TII->get(Mips::NOP));
 126
 127     // Bundle the delay slot filler to the instruction with the delay slot.
 128     MIBundleBuilder(MBB, I, llvm::next(llvm::next(I)));
 129   }
 130
 131   return Changed;
 132 }
 133
 134 /// createMipsDelaySlotFillerPass - Returns a pass that fills in delay
 135 /// slots in Mips MachineFunctions
 136 FunctionPass *llvm::createMipsDelaySlotFillerPass(MipsTargetMachine &tm) {
 137   return new Filler(tm);
 138 }
 139
 140 bool Filler::findDelayInstr(MachineBasicBlock &MBB, Iter Slot,
 141                             Iter &Filler) const {
 142   unsigned NumRegs = TM.getRegisterInfo()->getNumRegs();
 143   BitVector RegDefs(NumRegs), RegUses(NumRegs);
 144
 145   initRegDefsUses(*Slot, RegDefs, RegUses);
 146
 147   bool SawLoad = false;
 148   bool SawStore = false;
 149
 150   for (ReverseIter I(Slot); I != MBB.rend(); ++I) {
 151     // skip debug value
 152     if (I->isDebugValue())
 153       continue;
 154
 155     if (terminateSearch(*I))
 156       break;
 157
 158     if (delayHasHazard(*I, SawLoad, SawStore, RegDefs, RegUses))
 159       continue;
 160
 161     Filler = llvm::next(I).base();
 162     return true;
 163   }
 164
 165   return false;
 166 }
 167
 168 bool Filler::checkRegDefsUses(const BitVector &RegDefs,
 169                               const BitVector &RegUses,
 170                               BitVector &NewDefs, BitVector &NewUses,
 171                               unsigned Reg, bool IsDef) const {
 172   if (IsDef) {
 173     NewDefs.set(Reg);
 174     // check whether Reg has already been defined or used.
 175     return (isRegInSet(RegDefs, Reg) || isRegInSet(RegUses, Reg));
 176   }
 177
 178   NewUses.set(Reg);
 179   // check whether Reg has already been defined.
 180   return isRegInSet(RegDefs, Reg);
 181 }
 182
 183 bool Filler::checkRegDefsUses(BitVector &RegDefs, BitVector &RegUses,
 184                               const MachineInstr &MI, unsigned Begin,
 185                               unsigned End) const {
 186   unsigned NumRegs = TM.getRegisterInfo()->getNumRegs();
 187   BitVector NewDefs(NumRegs), NewUses(NumRegs);
 188   bool HasHazard = false;
 189
 190   for (unsigned I = Begin; I != End; ++I) {
 191     const MachineOperand &MO = MI.getOperand(I);
 192
 193     if (MO.isReg() && MO.getReg())
 194       HasHazard |= checkRegDefsUses(RegDefs, RegUses, NewDefs, NewUses,
 195                                     MO.getReg(), MO.isDef());
 196   }
 197
 198   RegDefs |= NewDefs;
 199   RegUses |= NewUses;
 200
 201   return HasHazard;
 202 }
 203
 204 bool Filler::delayHasHazard(const MachineInstr &Candidate, bool &SawLoad,
 205                             bool &SawStore, BitVector &RegDefs,
 206                             BitVector &RegUses) const {
 207   bool HasHazard = (Candidate.isImplicitDef() || Candidate.isKill());
 208
 209   // Loads or stores cannot be moved past a store to the delay slot
 210   // and stores cannot be moved past a load.
 211   if (Candidate.mayStore() || Candidate.hasOrderedMemoryRef()) {
 212     HasHazard |= SawStore | SawLoad;
 213     SawStore = true;
 214   } else if (Candidate.mayLoad()) {
 215     HasHazard |= SawStore;
 216     SawLoad = true;
 217   }
 218
 219   assert((!Candidate.isCall() && !Candidate.isReturn()) &&
 220          "Cannot put calls or returns in delay slot.");
 221
 222   HasHazard |= checkRegDefsUses(RegDefs, RegUses, Candidate, 0,
 223                                 Candidate.getNumOperands());
 224
 225   return HasHazard;
 226 }
 227
 228 void Filler::initRegDefsUses(const MachineInstr &MI, BitVector &RegDefs,
 229                              BitVector &RegUses) const {
 230   // Add all register operands which are explicit and non-variadic.
 231   checkRegDefsUses(RegDefs, RegUses, MI, 0, MI.getDesc().getNumOperands());
 232
 233   // If MI is a call, add RA to RegDefs to prevent users of RA from going into
 234   // delay slot.
 235   if (MI.isCall())
 236     RegDefs.set(Mips::RA);
 237
 238   // Add all implicit register operands of branch instructions except
 239   // register AT.
 240   if (MI.isBranch()) {
 241     checkRegDefsUses(RegDefs, RegUses, MI, MI.getDesc().getNumOperands(),
 242                      MI.getNumOperands());
 243     RegDefs.reset(Mips::AT);
 244   }
 245 }
 246
 247 //returns true if the Reg or its alias is in the RegSet.
 248 bool Filler::isRegInSet(const BitVector &RegSet, unsigned Reg) const {
 249   // Check Reg and all aliased Registers.
 250   for (MCRegAliasIterator AI(Reg, TM.getRegisterInfo(), true);
 251        AI.isValid(); ++AI)
 252     if (RegSet.test(*AI))
 253       return true;
 254   return false;
 255 }
 256
 257 bool Filler::terminateSearch(const MachineInstr &Candidate) const {
 258   return (Candidate.isTerminator() || Candidate.isCall() ||
 259           Candidate.isLabel() || Candidate.isInlineAsm() ||
 260           Candidate.hasUnmodeledSideEffects());
 261 }