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 "MCTargetDesc/MipsMCNaCl.h"
  17 #include "Mips.h"
  18 #include "MipsInstrInfo.h"
  19 #include "MipsTargetMachine.h"
  20 #include "llvm/ADT/BitVector.h"
  21 #include "llvm/ADT/SmallPtrSet.h"
  22 #include "llvm/ADT/Statistic.h"
  23 #include "llvm/Analysis/AliasAnalysis.h"
  24 #include "llvm/Analysis/ValueTracking.h"
  25 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
  26 #include "llvm/CodeGen/MachineFunctionPass.h"
  27 #include "llvm/CodeGen/MachineInstrBuilder.h"
  28 #include "llvm/CodeGen/PseudoSourceValue.h"
  29 #include "llvm/Support/CommandLine.h"
  30 #include "llvm/Target/TargetInstrInfo.h"
  31 #include "llvm/Target/TargetMachine.h"
  32 #include "llvm/Target/TargetRegisterInfo.h"
  33
  34 using namespace llvm;
  35
  36 STATISTIC(FilledSlots, "Number of delay slots filled");
  37 STATISTIC(UsefulSlots, "Number of delay slots filled with instructions that"
  38                        " are not NOP.");
  39
  40 static cl::opt<bool> DisableDelaySlotFiller(
  41   "disable-mips-delay-filler",
  42   cl::init(false),
  43   cl::desc("Fill all delay slots with NOPs."),
  44   cl::Hidden);
  45
  46 static cl::opt<bool> DisableForwardSearch(
  47   "disable-mips-df-forward-search",
  48   cl::init(true),
  49   cl::desc("Disallow MIPS delay filler to search forward."),
  50   cl::Hidden);
  51
  52 static cl::opt<bool> DisableSuccBBSearch(
  53   "disable-mips-df-succbb-search",
  54   cl::init(true),
  55   cl::desc("Disallow MIPS delay filler to search successor basic blocks."),
  56   cl::Hidden);
  57
  58 static cl::opt<bool> DisableBackwardSearch(
  59   "disable-mips-df-backward-search",
  60   cl::init(false),
  61   cl::desc("Disallow MIPS delay filler to search backward."),
  62   cl::Hidden);
  63
  64 namespace {
  65   typedef MachineBasicBlock::iterator Iter;
  66   typedef MachineBasicBlock::reverse_iterator ReverseIter;
  67   typedef SmallDenseMap<MachineBasicBlock*, MachineInstr*, 2> BB2BrMap;
  68
  69   class RegDefsUses {
  70   public:
  71     RegDefsUses(TargetMachine &TM);
  72     void init(const MachineInstr &MI);
  73
  74     /// This function sets all caller-saved registers in Defs.
  75     void setCallerSaved(const MachineInstr &MI);
  76
  77     /// This function sets all unallocatable registers in Defs.
  78     void setUnallocatableRegs(const MachineFunction &MF);
  79
  80     /// Set bits in Uses corresponding to MBB's live-out registers except for
  81     /// the registers that are live-in to SuccBB.
  82     void addLiveOut(const MachineBasicBlock &MBB,
  83                     const MachineBasicBlock &SuccBB);
  84
  85     bool update(const MachineInstr &MI, unsigned Begin, unsigned End);
  86
  87   private:
  88     bool checkRegDefsUses(BitVector &NewDefs, BitVector &NewUses, unsigned Reg,
  89                           bool IsDef) const;
  90
  91     /// Returns true if Reg or its alias is in RegSet.
  92     bool isRegInSet(const BitVector &RegSet, unsigned Reg) const;
  93
  94     const TargetRegisterInfo &TRI;
  95     BitVector Defs, Uses;
  96   };
  97
  98   /// Base class for inspecting loads and stores.
  99   class InspectMemInstr {
 100   public:
 101     InspectMemInstr(bool ForbidMemInstr_)
 102       : OrigSeenLoad(false), OrigSeenStore(false), SeenLoad(false),
 103         SeenStore(false), ForbidMemInstr(ForbidMemInstr_) {}
 104
 105     /// Return true if MI cannot be moved to delay slot.
 106     bool hasHazard(const MachineInstr &MI);
 107
 108     virtual ~InspectMemInstr() {}
 109
 110   protected:
 111     /// Flags indicating whether loads or stores have been seen.
 112     bool OrigSeenLoad, OrigSeenStore, SeenLoad, SeenStore;
 113
 114     /// Memory instructions are not allowed to move to delay slot if this flag
 115     /// is true.
 116     bool ForbidMemInstr;
 117
 118   private:
 119     virtual bool hasHazard_(const MachineInstr &MI) = 0;
 120   };
 121
 122   /// This subclass rejects any memory instructions.
 123   class NoMemInstr : public InspectMemInstr {
 124   public:
 125     NoMemInstr() : InspectMemInstr(true) {}
 126   private:
 127     virtual bool hasHazard_(const MachineInstr &MI) { return true; }
 128   };
 129
 130   /// This subclass accepts loads from stacks and constant loads.
 131   class LoadFromStackOrConst : public InspectMemInstr {
 132   public:
 133     LoadFromStackOrConst() : InspectMemInstr(false) {}
 134   private:
 135     virtual bool hasHazard_(const MachineInstr &MI);
 136   };
 137
 138   /// This subclass uses memory dependence information to determine whether a
 139   /// memory instruction can be moved to a delay slot.
 140   class MemDefsUses : public InspectMemInstr {
 141   public:
 142     MemDefsUses(const MachineFrameInfo *MFI);
 143
 144   private:
 145     typedef PointerUnion<const Value *, const PseudoSourceValue *> ValueType;
 146
 147     virtual bool hasHazard_(const MachineInstr &MI);
 148
 149     /// Update Defs and Uses. Return true if there exist dependences that
 150     /// disqualify the delay slot candidate between V and values in Uses and
 151     /// Defs.
 152     bool updateDefsUses(ValueType V, bool MayStore);
 153
 154     /// Get the list of underlying objects of MI's memory operand.
 155     bool getUnderlyingObjects(const MachineInstr &MI,
 156                               SmallVectorImpl<ValueType> &Objects) const;
 157
 158     const MachineFrameInfo *MFI;
 159     SmallPtrSet<ValueType, 4> Uses, Defs;
 160
 161     /// Flags indicating whether loads or stores with no underlying objects have
 162     /// been seen.
 163     bool SeenNoObjLoad, SeenNoObjStore;
 164   };
 165
 166   class Filler : public MachineFunctionPass {
 167   public:
 168     Filler(TargetMachine &tm)
 169       : MachineFunctionPass(ID), TM(tm) { }
 170
 171     virtual const char *getPassName() const {
 172       return "Mips Delay Slot Filler";
 173     }
 174
 175     bool runOnMachineFunction(MachineFunction &F) {
 176       bool Changed = false;
 177       for (MachineFunction::iterator FI = F.begin(), FE = F.end();
 178            FI != FE; ++FI)
 179         Changed |= runOnMachineBasicBlock(*FI);
 180       return Changed;
 181     }
 182
 183     void getAnalysisUsage(AnalysisUsage &AU) const {
 184       AU.addRequired<MachineBranchProbabilityInfo>();
 185       MachineFunctionPass::getAnalysisUsage(AU);
 186     }
 187
 188   private:
 189     bool runOnMachineBasicBlock(MachineBasicBlock &MBB);
 190
 191     /// This function checks if it is valid to move Candidate to the delay slot
 192     /// and returns true if it isn't. It also updates memory and register
 193     /// dependence information.
 194     bool delayHasHazard(const MachineInstr &Candidate, RegDefsUses &RegDU,
 195                         InspectMemInstr &IM) const;
 196
 197     /// This function searches range [Begin, End) for an instruction that can be
 198     /// moved to the delay slot. Returns true on success.
 199     template<typename IterTy>
 200     bool searchRange(MachineBasicBlock &MBB, IterTy Begin, IterTy End,
 201                      RegDefsUses &RegDU, InspectMemInstr &IM,
 202                      IterTy &Filler) const;
 203
 204     /// This function searches in the backward direction for an instruction that
 205     /// can be moved to the delay slot. Returns true on success.
 206     bool searchBackward(MachineBasicBlock &MBB, Iter Slot) const;
 207
 208     /// This function searches MBB in the forward direction for an instruction
 209     /// that can be moved to the delay slot. Returns true on success.
 210     bool searchForward(MachineBasicBlock &MBB, Iter Slot) const;
 211
 212     /// This function searches one of MBB's successor blocks for an instruction
 213     /// that can be moved to the delay slot and inserts clones of the
 214     /// instruction into the successor's predecessor blocks.
 215     bool searchSuccBBs(MachineBasicBlock &MBB, Iter Slot) const;
 216
 217     /// Pick a successor block of MBB. Return NULL if MBB doesn't have a
 218     /// successor block that is not a landing pad.
 219     MachineBasicBlock *selectSuccBB(MachineBasicBlock &B) const;
 220
 221     /// This function analyzes MBB and returns an instruction with an unoccupied
 222     /// slot that branches to Dst.
 223     std::pair<MipsInstrInfo::BranchType, MachineInstr *>
 224     getBranch(MachineBasicBlock &MBB, const MachineBasicBlock &Dst) const;
 225
 226     /// Examine Pred and see if it is possible to insert an instruction into
 227     /// one of its branches delay slot or its end.
 228     bool examinePred(MachineBasicBlock &Pred, const MachineBasicBlock &Succ,
 229                      RegDefsUses &RegDU, bool &HasMultipleSuccs,
 230                      BB2BrMap &BrMap) const;
 231
 232     bool terminateSearch(const MachineInstr &Candidate) const;
 233
 234     TargetMachine &TM;
 235
 236     static char ID;
 237   };
 238   char Filler::ID = 0;
 239 } // end of anonymous namespace
 240
 241 static bool hasUnoccupiedSlot(const MachineInstr *MI) {
 242   return MI->hasDelaySlot() && !MI->isBundledWithSucc();
 243 }
 244
 245 /// This function inserts clones of Filler into predecessor blocks.
 246 static void insertDelayFiller(Iter Filler, const BB2BrMap &BrMap) {
 247   MachineFunction *MF = Filler->getParent()->getParent();
 248
 249   for (BB2BrMap::const_iterator I = BrMap.begin(); I != BrMap.end(); ++I) {
 250     if (I->second) {
 251       MIBundleBuilder(I->second).append(MF->CloneMachineInstr(&*Filler));
 252       ++UsefulSlots;
 253     } else {
 254       I->first->insert(I->first->end(), MF->CloneMachineInstr(&*Filler));
 255     }
 256   }
 257 }
 258
 259 /// This function adds registers Filler defines to MBB's live-in register list.
 260 static void addLiveInRegs(Iter Filler, MachineBasicBlock &MBB) {
 261   for (unsigned I = 0, E = Filler->getNumOperands(); I != E; ++I) {
 262     const MachineOperand &MO = Filler->getOperand(I);
 263     unsigned R;
 264
 265     if (!MO.isReg() || !MO.isDef() || !(R = MO.getReg()))
 266       continue;
 267
 268 #ifndef NDEBUG
 269     const MachineFunction &MF = *MBB.getParent();
 270     assert(MF.getTarget().getRegisterInfo()->getAllocatableSet(MF).test(R) &&
 271            "Shouldn't move an instruction with unallocatable registers across "
 272            "basic block boundaries.");
 273 #endif
 274
 275     if (!MBB.isLiveIn(R))
 276       MBB.addLiveIn(R);
 277   }
 278 }
 279
 280 RegDefsUses::RegDefsUses(TargetMachine &TM)
 281   : TRI(*TM.getRegisterInfo()), Defs(TRI.getNumRegs(), false),
 282     Uses(TRI.getNumRegs(), false) {}
 283
 284 void RegDefsUses::init(const MachineInstr &MI) {
 285   // Add all register operands which are explicit and non-variadic.
 286   update(MI, 0, MI.getDesc().getNumOperands());
 287
 288   // If MI is a call, add RA to Defs to prevent users of RA from going into
 289   // delay slot.
 290   if (MI.isCall())
 291     Defs.set(Mips::RA);
 292
 293   // Add all implicit register operands of branch instructions except
 294   // register AT.
 295   if (MI.isBranch()) {
 296     update(MI, MI.getDesc().getNumOperands(), MI.getNumOperands());
 297     Defs.reset(Mips::AT);
 298   }
 299 }
 300
 301 void RegDefsUses::setCallerSaved(const MachineInstr &MI) {
 302   assert(MI.isCall());
 303
 304   // If MI is a call, add all caller-saved registers to Defs.
 305   BitVector CallerSavedRegs(TRI.getNumRegs(), true);
 306
 307   CallerSavedRegs.reset(Mips::ZERO);
 308   CallerSavedRegs.reset(Mips::ZERO_64);
 309
 310   for (const MCPhysReg *R = TRI.getCalleeSavedRegs(); *R; ++R)
 311     for (MCRegAliasIterator AI(*R, &TRI, true); AI.isValid(); ++AI)
 312       CallerSavedRegs.reset(*AI);
 313
 314   Defs |= CallerSavedRegs;
 315 }
 316
 317 void RegDefsUses::setUnallocatableRegs(const MachineFunction &MF) {
 318   BitVector AllocSet = TRI.getAllocatableSet(MF);
 319
 320   for (int R = AllocSet.find_first(); R != -1; R = AllocSet.find_next(R))
 321     for (MCRegAliasIterator AI(R, &TRI, false); AI.isValid(); ++AI)
 322       AllocSet.set(*AI);
 323
 324   AllocSet.set(Mips::ZERO);
 325   AllocSet.set(Mips::ZERO_64);
 326
 327   Defs |= AllocSet.flip();
 328 }
 329
 330 void RegDefsUses::addLiveOut(const MachineBasicBlock &MBB,
 331                              const MachineBasicBlock &SuccBB) {
 332   for (MachineBasicBlock::const_succ_iterator SI = MBB.succ_begin(),
 333        SE = MBB.succ_end(); SI != SE; ++SI)
 334     if (*SI != &SuccBB)
 335       for (MachineBasicBlock::livein_iterator LI = (*SI)->livein_begin(),
 336            LE = (*SI)->livein_end(); LI != LE; ++LI)
 337         Uses.set(*LI);
 338 }
 339
 340 bool RegDefsUses::update(const MachineInstr &MI, unsigned Begin, unsigned End) {
 341   BitVector NewDefs(TRI.getNumRegs()), NewUses(TRI.getNumRegs());
 342   bool HasHazard = false;
 343
 344   for (unsigned I = Begin; I != End; ++I) {
 345     const MachineOperand &MO = MI.getOperand(I);
 346
 347     if (MO.isReg() && MO.getReg())
 348       HasHazard |= checkRegDefsUses(NewDefs, NewUses, MO.getReg(), MO.isDef());
 349   }
 350
 351   Defs |= NewDefs;
 352   Uses |= NewUses;
 353
 354   return HasHazard;
 355 }
 356
 357 bool RegDefsUses::checkRegDefsUses(BitVector &NewDefs, BitVector &NewUses,
 358                                    unsigned Reg, bool IsDef) const {
 359   if (IsDef) {
 360     NewDefs.set(Reg);
 361     // check whether Reg has already been defined or used.
 362     return (isRegInSet(Defs, Reg) || isRegInSet(Uses, Reg));
 363   }
 364
 365   NewUses.set(Reg);
 366   // check whether Reg has already been defined.
 367   return isRegInSet(Defs, Reg);
 368 }
 369
 370 bool RegDefsUses::isRegInSet(const BitVector &RegSet, unsigned Reg) const {
 371   // Check Reg and all aliased Registers.
 372   for (MCRegAliasIterator AI(Reg, &TRI, true); AI.isValid(); ++AI)
 373     if (RegSet.test(*AI))
 374       return true;
 375   return false;
 376 }
 377
 378 bool InspectMemInstr::hasHazard(const MachineInstr &MI) {
 379   if (!MI.mayStore() && !MI.mayLoad())
 380     return false;
 381
 382   if (ForbidMemInstr)
 383     return true;
 384
 385   OrigSeenLoad = SeenLoad;
 386   OrigSeenStore = SeenStore;
 387   SeenLoad |= MI.mayLoad();
 388   SeenStore |= MI.mayStore();
 389
 390   // If MI is an ordered or volatile memory reference, disallow moving
 391   // subsequent loads and stores to delay slot.
 392   if (MI.hasOrderedMemoryRef() && (OrigSeenLoad || OrigSeenStore)) {
 393     ForbidMemInstr = true;
 394     return true;
 395   }
 396
 397   return hasHazard_(MI);
 398 }
 399
 400 bool LoadFromStackOrConst::hasHazard_(const MachineInstr &MI) {
 401   if (MI.mayStore())
 402     return true;
 403
 404   if (!MI.hasOneMemOperand() || !(*MI.memoperands_begin())->getPseudoValue())
 405     return true;
 406
 407   if (const PseudoSourceValue *PSV =
 408       (*MI.memoperands_begin())->getPseudoValue()) {
 409     if (isa<FixedStackPseudoSourceValue>(PSV))
 410       return false;
 411     return !PSV->isConstant(0) && PSV != PseudoSourceValue::getStack();
 412   }
 413
 414   return true;
 415 }
 416
 417 MemDefsUses::MemDefsUses(const MachineFrameInfo *MFI_)
 418   : InspectMemInstr(false), MFI(MFI_), SeenNoObjLoad(false),
 419     SeenNoObjStore(false) {}
 420
 421 bool MemDefsUses::hasHazard_(const MachineInstr &MI) {
 422   bool HasHazard = false;
 423   SmallVector<ValueType, 4> Objs;
 424
 425   // Check underlying object list.
 426   if (getUnderlyingObjects(MI, Objs)) {
 427     for (SmallVectorImpl<ValueType>::const_iterator I = Objs.begin();
 428          I != Objs.end(); ++I)
 429       HasHazard |= updateDefsUses(*I, MI.mayStore());
 430
 431     return HasHazard;
 432   }
 433
 434   // No underlying objects found.
 435   HasHazard = MI.mayStore() && (OrigSeenLoad || OrigSeenStore);
 436   HasHazard |= MI.mayLoad() || OrigSeenStore;
 437
 438   SeenNoObjLoad |= MI.mayLoad();
 439   SeenNoObjStore |= MI.mayStore();
 440
 441   return HasHazard;
 442 }
 443
 444 bool MemDefsUses::updateDefsUses(ValueType V, bool MayStore) {
 445   if (MayStore)
 446     return !Defs.insert(V) || Uses.count(V) || SeenNoObjStore || SeenNoObjLoad;
 447
 448   Uses.insert(V);
 449   return Defs.count(V) || SeenNoObjStore;
 450 }
 451
 452 bool MemDefsUses::
 453 getUnderlyingObjects(const MachineInstr &MI,
 454                      SmallVectorImpl<ValueType> &Objects) const {
 455   if (!MI.hasOneMemOperand() ||
 456       (!(*MI.memoperands_begin())->getValue() &&
 457        !(*MI.memoperands_begin())->getPseudoValue()))
 458     return false;
 459
 460   if (const PseudoSourceValue *PSV =
 461       (*MI.memoperands_begin())->getPseudoValue()) {
 462     if (!PSV->isAliased(MFI))
 463       return false;
 464     Objects.push_back(PSV);
 465     return true;
 466   }
 467
 468   const Value *V = (*MI.memoperands_begin())->getValue();
 469
 470   SmallVector<Value *, 4> Objs;
 471   GetUnderlyingObjects(const_cast<Value *>(V), Objs);
 472
 473   for (SmallVectorImpl<Value *>::iterator I = Objs.begin(), E = Objs.end();
 474        I != E; ++I) {
 475     if (!isIdentifiedObject(V))
 476       return false;
 477
 478     Objects.push_back(*I);
 479   }
 480
 481   return true;
 482 }
 483
 484 /// runOnMachineBasicBlock - Fill in delay slots for the given basic block.
 485 /// We assume there is only one delay slot per delayed instruction.
 486 bool Filler::runOnMachineBasicBlock(MachineBasicBlock &MBB) {
 487   bool Changed = false;
 488
 489   for (Iter I = MBB.begin(); I != MBB.end(); ++I) {
 490     if (!hasUnoccupiedSlot(&*I))
 491       continue;
 492
 493     ++FilledSlots;
 494     Changed = true;
 495
 496     // Delay slot filling is disabled at -O0.
 497     if (!DisableDelaySlotFiller && (TM.getOptLevel() != CodeGenOpt::None)) {
 498       if (searchBackward(MBB, I))
 499         continue;
 500
 501       if (I->isTerminator()) {
 502         if (searchSuccBBs(MBB, I))
 503           continue;
 504       } else if (searchForward(MBB, I)) {
 505         continue;
 506       }
 507     }
 508
 509     // Bundle the NOP to the instruction with the delay slot.
 510     const MipsInstrInfo *TII =
 511       static_cast<const MipsInstrInfo*>(TM.getInstrInfo());
 512     BuildMI(MBB, std::next(I), I->getDebugLoc(), TII->get(Mips::NOP));
 513     MIBundleBuilder(MBB, I, std::next(I, 2));
 514   }
 515
 516   return Changed;
 517 }
 518
 519 /// createMipsDelaySlotFillerPass - Returns a pass that fills in delay
 520 /// slots in Mips MachineFunctions
 521 FunctionPass *llvm::createMipsDelaySlotFillerPass(MipsTargetMachine &tm) {
 522   return new Filler(tm);
 523 }
 524
 525 template<typename IterTy>
 526 bool Filler::searchRange(MachineBasicBlock &MBB, IterTy Begin, IterTy End,
 527                          RegDefsUses &RegDU, InspectMemInstr& IM,
 528                          IterTy &Filler) const {
 529   for (IterTy I = Begin; I != End; ++I) {
 530     // skip debug value
 531     if (I->isDebugValue())
 532       continue;
 533
 534     if (terminateSearch(*I))
 535       break;
 536
 537     assert((!I->isCall() && !I->isReturn() && !I->isBranch()) &&
 538            "Cannot put calls, returns or branches in delay slot.");
 539
 540     if (delayHasHazard(*I, RegDU, IM))
 541       continue;
 542
 543     if (TM.getSubtarget<MipsSubtarget>().isTargetNaCl()) {
 544       // In NaCl, instructions that must be masked are forbidden in delay slots.
 545       // We only check for loads, stores and SP changes.  Calls, returns and
 546       // branches are not checked because non-NaCl targets never put them in
 547       // delay slots.
 548       unsigned AddrIdx;
 549       if ((isBasePlusOffsetMemoryAccess(I->getOpcode(), &AddrIdx)
 550            && baseRegNeedsLoadStoreMask(I->getOperand(AddrIdx).getReg()))
 551           || I->modifiesRegister(Mips::SP, TM.getRegisterInfo()))
 552         continue;
 553     }
 554
 555     Filler = I;
 556     return true;
 557   }
 558
 559   return false;
 560 }
 561
 562 bool Filler::searchBackward(MachineBasicBlock &MBB, Iter Slot) const {
 563   if (DisableBackwardSearch)
 564     return false;
 565
 566   RegDefsUses RegDU(TM);
 567   MemDefsUses MemDU(MBB.getParent()->getFrameInfo());
 568   ReverseIter Filler;
 569
 570   RegDU.init(*Slot);
 571
 572   if (!searchRange(MBB, ReverseIter(Slot), MBB.rend(), RegDU, MemDU, Filler))
 573     return false;
 574
 575   MBB.splice(std::next(Slot), &MBB, std::next(Filler).base());
 576   MIBundleBuilder(MBB, Slot, std::next(Slot, 2));
 577   ++UsefulSlots;
 578   return true;
 579 }
 580
 581 bool Filler::searchForward(MachineBasicBlock &MBB, Iter Slot) const {
 582   // Can handle only calls.
 583   if (DisableForwardSearch || !Slot->isCall())
 584     return false;
 585
 586   RegDefsUses RegDU(TM);
 587   NoMemInstr NM;
 588   Iter Filler;
 589
 590   RegDU.setCallerSaved(*Slot);
 591
 592   if (!searchRange(MBB, std::next(Slot), MBB.end(), RegDU, NM, Filler))
 593     return false;
 594
 595   MBB.splice(std::next(Slot), &MBB, Filler);
 596   MIBundleBuilder(MBB, Slot, std::next(Slot, 2));
 597   ++UsefulSlots;
 598   return true;
 599 }
 600
 601 bool Filler::searchSuccBBs(MachineBasicBlock &MBB, Iter Slot) const {
 602   if (DisableSuccBBSearch)
 603     return false;
 604
 605   MachineBasicBlock *SuccBB = selectSuccBB(MBB);
 606
 607   if (!SuccBB)
 608     return false;
 609
 610   RegDefsUses RegDU(TM);
 611   bool HasMultipleSuccs = false;
 612   BB2BrMap BrMap;
 613   OwningPtr<InspectMemInstr> IM;
 614   Iter Filler;
 615
 616   // Iterate over SuccBB's predecessor list.
 617   for (MachineBasicBlock::pred_iterator PI = SuccBB->pred_begin(),
 618        PE = SuccBB->pred_end(); PI != PE; ++PI)
 619     if (!examinePred(**PI, *SuccBB, RegDU, HasMultipleSuccs, BrMap))
 620       return false;
 621
 622   // Do not allow moving instructions which have unallocatable register operands
 623   // across basic block boundaries.
 624   RegDU.setUnallocatableRegs(*MBB.getParent());
 625
 626   // Only allow moving loads from stack or constants if any of the SuccBB's
 627   // predecessors have multiple successors.
 628   if (HasMultipleSuccs) {
 629     IM.reset(new LoadFromStackOrConst());
 630   } else {
 631     const MachineFrameInfo *MFI = MBB.getParent()->getFrameInfo();
 632     IM.reset(new MemDefsUses(MFI));
 633   }
 634
 635   if (!searchRange(MBB, SuccBB->begin(), SuccBB->end(), RegDU, *IM, Filler))
 636     return false;
 637
 638   insertDelayFiller(Filler, BrMap);
 639   addLiveInRegs(Filler, *SuccBB);
 640   Filler->eraseFromParent();
 641
 642   return true;
 643 }
 644
 645 MachineBasicBlock *Filler::selectSuccBB(MachineBasicBlock &B) const {
 646   if (B.succ_empty())
 647     return NULL;
 648
 649   // Select the successor with the larget edge weight.
 650   auto &Prob = getAnalysis<MachineBranchProbabilityInfo>();
 651   MachineBasicBlock *S = *std::max_element(B.succ_begin(), B.succ_end(),
 652                                            [&](const MachineBasicBlock *Dst0,
 653                                                const MachineBasicBlock *Dst1) {
 654     return Prob.getEdgeWeight(&B, Dst0) < Prob.getEdgeWeight(&B, Dst1);
 655   });
 656   return S->isLandingPad() ? NULL : S;
 657 }
 658
 659 std::pair<MipsInstrInfo::BranchType, MachineInstr *>
 660 Filler::getBranch(MachineBasicBlock &MBB, const MachineBasicBlock &Dst) const {
 661   const MipsInstrInfo *TII =
 662     static_cast<const MipsInstrInfo*>(TM.getInstrInfo());
 663   MachineBasicBlock *TrueBB = 0, *FalseBB = 0;
 664   SmallVector<MachineInstr*, 2> BranchInstrs;
 665   SmallVector<MachineOperand, 2> Cond;
 666
 667   MipsInstrInfo::BranchType R =
 668     TII->AnalyzeBranch(MBB, TrueBB, FalseBB, Cond, false, BranchInstrs);
 669
 670   if ((R == MipsInstrInfo::BT_None) || (R == MipsInstrInfo::BT_NoBranch))
 671     return std::make_pair(R, (MachineInstr*)NULL);
 672
 673   if (R != MipsInstrInfo::BT_CondUncond) {
 674     if (!hasUnoccupiedSlot(BranchInstrs[0]))
 675       return std::make_pair(MipsInstrInfo::BT_None, (MachineInstr*)NULL);
 676
 677     assert(((R != MipsInstrInfo::BT_Uncond) || (TrueBB == &Dst)));
 678
 679     return std::make_pair(R, BranchInstrs[0]);
 680   }
 681
 682   assert((TrueBB == &Dst) || (FalseBB == &Dst));
 683
 684   // Examine the conditional branch. See if its slot is occupied.
 685   if (hasUnoccupiedSlot(BranchInstrs[0]))
 686     return std::make_pair(MipsInstrInfo::BT_Cond, BranchInstrs[0]);
 687
 688   // If that fails, try the unconditional branch.
 689   if (hasUnoccupiedSlot(BranchInstrs[1]) && (FalseBB == &Dst))
 690     return std::make_pair(MipsInstrInfo::BT_Uncond, BranchInstrs[1]);
 691
 692   return std::make_pair(MipsInstrInfo::BT_None, (MachineInstr*)NULL);
 693 }
 694
 695 bool Filler::examinePred(MachineBasicBlock &Pred, const MachineBasicBlock &Succ,
 696                          RegDefsUses &RegDU, bool &HasMultipleSuccs,
 697                          BB2BrMap &BrMap) const {
 698   std::pair<MipsInstrInfo::BranchType, MachineInstr *> P =
 699     getBranch(Pred, Succ);
 700
 701   // Return if either getBranch wasn't able to analyze the branches or there
 702   // were no branches with unoccupied slots.
 703   if (P.first == MipsInstrInfo::BT_None)
 704     return false;
 705
 706   if ((P.first != MipsInstrInfo::BT_Uncond) &&
 707       (P.first != MipsInstrInfo::BT_NoBranch)) {
 708     HasMultipleSuccs = true;
 709     RegDU.addLiveOut(Pred, Succ);
 710   }
 711
 712   BrMap[&Pred] = P.second;
 713   return true;
 714 }
 715
 716 bool Filler::delayHasHazard(const MachineInstr &Candidate, RegDefsUses &RegDU,
 717                             InspectMemInstr &IM) const {
 718   bool HasHazard = (Candidate.isImplicitDef() || Candidate.isKill());
 719
 720   HasHazard |= IM.hasHazard(Candidate);
 721   HasHazard |= RegDU.update(Candidate, 0, Candidate.getNumOperands());
 722
 723   return HasHazard;
 724 }
 725
 726 bool Filler::terminateSearch(const MachineInstr &Candidate) const {
 727   return (Candidate.isTerminator() || Candidate.isCall() ||
 728           Candidate.isPosition() || Candidate.isInlineAsm() ||
 729           Candidate.hasUnmodeledSideEffects());
 730 }