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