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