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