MipsDelaySlotFiller.cpp revision 0c8f21afbd31e796c18a6a59b9f1039a71145c96
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), TII(tm.getInstrInfo()) { } 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 const TargetInstrInfo *TII; 247 248 static char ID; 249 }; 250 char Filler::ID = 0; 251} // end of anonymous namespace 252 253static bool hasUnoccupiedSlot(const MachineInstr *MI) { 254 return MI->hasDelaySlot() && !MI->isBundledWithSucc(); 255} 256 257/// This function inserts clones of Filler into predecessor blocks. 258static void insertDelayFiller(Iter Filler, const BB2BrMap &BrMap) { 259 MachineFunction *MF = Filler->getParent()->getParent(); 260 261 for (BB2BrMap::const_iterator I = BrMap.begin(); I != BrMap.end(); ++I) { 262 if (I->second) { 263 MIBundleBuilder(I->second).append(MF->CloneMachineInstr(&*Filler)); 264 ++UsefulSlots; 265 } else { 266 I->first->insert(I->first->end(), MF->CloneMachineInstr(&*Filler)); 267 } 268 } 269} 270 271/// This function adds registers Filler defines to MBB's live-in register list. 272static void addLiveInRegs(Iter Filler, MachineBasicBlock &MBB) { 273 for (unsigned I = 0, E = Filler->getNumOperands(); I != E; ++I) { 274 const MachineOperand &MO = Filler->getOperand(I); 275 unsigned R; 276 277 if (!MO.isReg() || !MO.isDef() || !(R = MO.getReg())) 278 continue; 279 280#ifndef NDEBUG 281 const MachineFunction &MF = *MBB.getParent(); 282 assert(MF.getTarget().getRegisterInfo()->getAllocatableSet(MF).test(R) && 283 "Shouldn't move an instruction with unallocatable registers across " 284 "basic block boundaries."); 285#endif 286 287 if (!MBB.isLiveIn(R)) 288 MBB.addLiveIn(R); 289 } 290} 291 292RegDefsUses::RegDefsUses(TargetMachine &TM) 293 : TRI(*TM.getRegisterInfo()), Defs(TRI.getNumRegs(), false), 294 Uses(TRI.getNumRegs(), false) {} 295 296void RegDefsUses::init(const MachineInstr &MI) { 297 // Add all register operands which are explicit and non-variadic. 298 update(MI, 0, MI.getDesc().getNumOperands()); 299 300 // If MI is a call, add RA to Defs to prevent users of RA from going into 301 // delay slot. 302 if (MI.isCall()) 303 Defs.set(Mips::RA); 304 305 // Add all implicit register operands of branch instructions except 306 // register AT. 307 if (MI.isBranch()) { 308 update(MI, MI.getDesc().getNumOperands(), MI.getNumOperands()); 309 Defs.reset(Mips::AT); 310 } 311} 312 313void RegDefsUses::setCallerSaved(const MachineInstr &MI) { 314 assert(MI.isCall()); 315 316 // If MI is a call, add all caller-saved registers to Defs. 317 BitVector CallerSavedRegs(TRI.getNumRegs(), true); 318 319 CallerSavedRegs.reset(Mips::ZERO); 320 CallerSavedRegs.reset(Mips::ZERO_64); 321 322 for (const MCPhysReg *R = TRI.getCalleeSavedRegs(); *R; ++R) 323 for (MCRegAliasIterator AI(*R, &TRI, true); AI.isValid(); ++AI) 324 CallerSavedRegs.reset(*AI); 325 326 Defs |= CallerSavedRegs; 327} 328 329void RegDefsUses::setUnallocatableRegs(const MachineFunction &MF) { 330 BitVector AllocSet = TRI.getAllocatableSet(MF); 331 332 for (int R = AllocSet.find_first(); R != -1; R = AllocSet.find_next(R)) 333 for (MCRegAliasIterator AI(R, &TRI, false); AI.isValid(); ++AI) 334 AllocSet.set(*AI); 335 336 AllocSet.set(Mips::ZERO); 337 AllocSet.set(Mips::ZERO_64); 338 339 Defs |= AllocSet.flip(); 340} 341 342void RegDefsUses::addLiveOut(const MachineBasicBlock &MBB, 343 const MachineBasicBlock &SuccBB) { 344 for (MachineBasicBlock::const_succ_iterator SI = MBB.succ_begin(), 345 SE = MBB.succ_end(); SI != SE; ++SI) 346 if (*SI != &SuccBB) 347 for (MachineBasicBlock::livein_iterator LI = (*SI)->livein_begin(), 348 LE = (*SI)->livein_end(); LI != LE; ++LI) 349 Uses.set(*LI); 350} 351 352bool RegDefsUses::update(const MachineInstr &MI, unsigned Begin, unsigned End) { 353 BitVector NewDefs(TRI.getNumRegs()), NewUses(TRI.getNumRegs()); 354 bool HasHazard = false; 355 356 for (unsigned I = Begin; I != End; ++I) { 357 const MachineOperand &MO = MI.getOperand(I); 358 359 if (MO.isReg() && MO.getReg()) 360 HasHazard |= checkRegDefsUses(NewDefs, NewUses, MO.getReg(), MO.isDef()); 361 } 362 363 Defs |= NewDefs; 364 Uses |= NewUses; 365 366 return HasHazard; 367} 368 369bool RegDefsUses::checkRegDefsUses(BitVector &NewDefs, BitVector &NewUses, 370 unsigned Reg, bool IsDef) const { 371 if (IsDef) { 372 NewDefs.set(Reg); 373 // check whether Reg has already been defined or used. 374 return (isRegInSet(Defs, Reg) || isRegInSet(Uses, Reg)); 375 } 376 377 NewUses.set(Reg); 378 // check whether Reg has already been defined. 379 return isRegInSet(Defs, Reg); 380} 381 382bool RegDefsUses::isRegInSet(const BitVector &RegSet, unsigned Reg) const { 383 // Check Reg and all aliased Registers. 384 for (MCRegAliasIterator AI(Reg, &TRI, true); AI.isValid(); ++AI) 385 if (RegSet.test(*AI)) 386 return true; 387 return false; 388} 389 390bool InspectMemInstr::hasHazard(const MachineInstr &MI) { 391 if (!MI.mayStore() && !MI.mayLoad()) 392 return false; 393 394 if (ForbidMemInstr) 395 return true; 396 397 OrigSeenLoad = SeenLoad; 398 OrigSeenStore = SeenStore; 399 SeenLoad |= MI.mayLoad(); 400 SeenStore |= MI.mayStore(); 401 402 // If MI is an ordered or volatile memory reference, disallow moving 403 // subsequent loads and stores to delay slot. 404 if (MI.hasOrderedMemoryRef() && (OrigSeenLoad || OrigSeenStore)) { 405 ForbidMemInstr = true; 406 return true; 407 } 408 409 return hasHazard_(MI); 410} 411 412bool LoadFromStackOrConst::hasHazard_(const MachineInstr &MI) { 413 if (MI.mayStore()) 414 return true; 415 416 if (!MI.hasOneMemOperand() || !(*MI.memoperands_begin())->getValue()) 417 return true; 418 419 const Value *V = (*MI.memoperands_begin())->getValue(); 420 421 if (isa<FixedStackPseudoSourceValue>(V)) 422 return false; 423 424 if (const PseudoSourceValue *PSV = dyn_cast<const PseudoSourceValue>(V)) 425 return !PSV->PseudoSourceValue::isConstant(0) && 426 (V != PseudoSourceValue::getStack()); 427 428 return true; 429} 430 431MemDefsUses::MemDefsUses(const MachineFrameInfo *MFI_) 432 : InspectMemInstr(false), MFI(MFI_), SeenNoObjLoad(false), 433 SeenNoObjStore(false) {} 434 435bool MemDefsUses::hasHazard_(const MachineInstr &MI) { 436 bool HasHazard = false; 437 SmallVector<const Value *, 4> Objs; 438 439 // Check underlying object list. 440 if (getUnderlyingObjects(MI, Objs)) { 441 for (SmallVector<const Value *, 4>::const_iterator I = Objs.begin(); 442 I != Objs.end(); ++I) 443 HasHazard |= updateDefsUses(*I, MI.mayStore()); 444 445 return HasHazard; 446 } 447 448 // No underlying objects found. 449 HasHazard = MI.mayStore() && (OrigSeenLoad || OrigSeenStore); 450 HasHazard |= MI.mayLoad() || OrigSeenStore; 451 452 SeenNoObjLoad |= MI.mayLoad(); 453 SeenNoObjStore |= MI.mayStore(); 454 455 return HasHazard; 456} 457 458bool MemDefsUses::updateDefsUses(const Value *V, bool MayStore) { 459 if (MayStore) 460 return !Defs.insert(V) || Uses.count(V) || SeenNoObjStore || SeenNoObjLoad; 461 462 Uses.insert(V); 463 return Defs.count(V) || SeenNoObjStore; 464} 465 466bool MemDefsUses:: 467getUnderlyingObjects(const MachineInstr &MI, 468 SmallVectorImpl<const Value *> &Objects) const { 469 if (!MI.hasOneMemOperand() || !(*MI.memoperands_begin())->getValue()) 470 return false; 471 472 const Value *V = (*MI.memoperands_begin())->getValue(); 473 474 SmallVector<Value *, 4> Objs; 475 GetUnderlyingObjects(const_cast<Value *>(V), Objs); 476 477 for (SmallVector<Value*, 4>::iterator I = Objs.begin(), E = Objs.end(); 478 I != E; ++I) { 479 if (const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(*I)) { 480 if (PSV->isAliased(MFI)) 481 return false; 482 } else if (!isIdentifiedObject(V)) 483 return false; 484 485 Objects.push_back(*I); 486 } 487 488 return true; 489} 490 491/// runOnMachineBasicBlock - Fill in delay slots for the given basic block. 492/// We assume there is only one delay slot per delayed instruction. 493bool Filler::runOnMachineBasicBlock(MachineBasicBlock &MBB) { 494 bool Changed = false; 495 496 for (Iter I = MBB.begin(); I != MBB.end(); ++I) { 497 if (!hasUnoccupiedSlot(&*I)) 498 continue; 499 500 ++FilledSlots; 501 Changed = true; 502 503 // Delay slot filling is disabled at -O0. 504 if (!DisableDelaySlotFiller && (TM.getOptLevel() != CodeGenOpt::None)) { 505 if (searchBackward(MBB, I)) 506 continue; 507 508 if (I->isTerminator()) { 509 if (searchSuccBBs(MBB, I)) 510 continue; 511 } else if (searchForward(MBB, I)) { 512 continue; 513 } 514 } 515 516 // Bundle the NOP to the instruction with the delay slot. 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 MBB.splice(llvm::next(Slot), &MBB, llvm::next(Filler).base()); 567 MIBundleBuilder(MBB, Slot, llvm::next(llvm::next(Slot))); 568 ++UsefulSlots; 569 return true; 570 } 571 572 return false; 573} 574 575bool Filler::searchForward(MachineBasicBlock &MBB, Iter Slot) const { 576 // Can handle only calls. 577 if (DisableForwardSearch || !Slot->isCall()) 578 return false; 579 580 RegDefsUses RegDU(TM); 581 NoMemInstr NM; 582 Iter Filler; 583 584 RegDU.setCallerSaved(*Slot); 585 586 if (searchRange(MBB, llvm::next(Slot), MBB.end(), RegDU, NM, Filler)) { 587 MBB.splice(llvm::next(Slot), &MBB, Filler); 588 MIBundleBuilder(MBB, Slot, llvm::next(llvm::next(Slot))); 589 ++UsefulSlots; 590 return true; 591 } 592 593 return false; 594} 595 596bool Filler::searchSuccBBs(MachineBasicBlock &MBB, Iter Slot) const { 597 if (DisableSuccBBSearch) 598 return false; 599 600 MachineBasicBlock *SuccBB = selectSuccBB(MBB); 601 602 if (!SuccBB) 603 return false; 604 605 RegDefsUses RegDU(TM); 606 bool HasMultipleSuccs = false; 607 BB2BrMap BrMap; 608 OwningPtr<InspectMemInstr> IM; 609 Iter Filler; 610 611 // Iterate over SuccBB's predecessor list. 612 for (MachineBasicBlock::pred_iterator PI = SuccBB->pred_begin(), 613 PE = SuccBB->pred_end(); PI != PE; ++PI) 614 if (!examinePred(**PI, *SuccBB, RegDU, HasMultipleSuccs, BrMap)) 615 return false; 616 617 // Do not allow moving instructions which have unallocatable register operands 618 // across basic block boundaries. 619 RegDU.setUnallocatableRegs(*MBB.getParent()); 620 621 // Only allow moving loads from stack or constants if any of the SuccBB's 622 // predecessors have multiple successors. 623 if (HasMultipleSuccs) { 624 IM.reset(new LoadFromStackOrConst()); 625 } else { 626 const MachineFrameInfo *MFI = MBB.getParent()->getFrameInfo(); 627 IM.reset(new MemDefsUses(MFI)); 628 } 629 630 if (!searchRange(MBB, SuccBB->begin(), SuccBB->end(), RegDU, *IM, Filler)) 631 return false; 632 633 insertDelayFiller(Filler, BrMap); 634 addLiveInRegs(Filler, *SuccBB); 635 Filler->eraseFromParent(); 636 637 return true; 638} 639 640MachineBasicBlock *Filler::selectSuccBB(MachineBasicBlock &B) const { 641 if (B.succ_empty()) 642 return NULL; 643 644 // Select the successor with the larget edge weight. 645 CmpWeight Cmp(B, getAnalysis<MachineBranchProbabilityInfo>()); 646 MachineBasicBlock *S = *std::max_element(B.succ_begin(), B.succ_end(), Cmp); 647 return S->isLandingPad() ? NULL : S; 648} 649 650std::pair<MipsInstrInfo::BranchType, MachineInstr *> 651Filler::getBranch(MachineBasicBlock &MBB, const MachineBasicBlock &Dst) const { 652 const MipsInstrInfo *TII = 653 static_cast<const MipsInstrInfo*>(TM.getInstrInfo()); 654 MachineBasicBlock *TrueBB = 0, *FalseBB = 0; 655 SmallVector<MachineInstr*, 2> BranchInstrs; 656 SmallVector<MachineOperand, 2> Cond; 657 658 MipsInstrInfo::BranchType R = 659 TII->AnalyzeBranch(MBB, TrueBB, FalseBB, Cond, false, BranchInstrs); 660 661 if ((R == MipsInstrInfo::BT_None) || (R == MipsInstrInfo::BT_NoBranch)) 662 return std::make_pair(R, (MachineInstr*)NULL); 663 664 if (R != MipsInstrInfo::BT_CondUncond) { 665 if (!hasUnoccupiedSlot(BranchInstrs[0])) 666 return std::make_pair(MipsInstrInfo::BT_None, (MachineInstr*)NULL); 667 668 assert(((R != MipsInstrInfo::BT_Uncond) || (TrueBB == &Dst))); 669 670 return std::make_pair(R, BranchInstrs[0]); 671 } 672 673 assert((TrueBB == &Dst) || (FalseBB == &Dst)); 674 675 // Examine the conditional branch. See if its slot is occupied. 676 if (hasUnoccupiedSlot(BranchInstrs[0])) 677 return std::make_pair(MipsInstrInfo::BT_Cond, BranchInstrs[0]); 678 679 // If that fails, try the unconditional branch. 680 if (hasUnoccupiedSlot(BranchInstrs[1]) && (FalseBB == &Dst)) 681 return std::make_pair(MipsInstrInfo::BT_Uncond, BranchInstrs[1]); 682 683 return std::make_pair(MipsInstrInfo::BT_None, (MachineInstr*)NULL); 684} 685 686bool Filler::examinePred(MachineBasicBlock &Pred, const MachineBasicBlock &Succ, 687 RegDefsUses &RegDU, bool &HasMultipleSuccs, 688 BB2BrMap &BrMap) const { 689 std::pair<MipsInstrInfo::BranchType, MachineInstr *> P = 690 getBranch(Pred, Succ); 691 692 // Return if either getBranch wasn't able to analyze the branches or there 693 // were no branches with unoccupied slots. 694 if (P.first == MipsInstrInfo::BT_None) 695 return false; 696 697 if ((P.first != MipsInstrInfo::BT_Uncond) && 698 (P.first != MipsInstrInfo::BT_NoBranch)) { 699 HasMultipleSuccs = true; 700 RegDU.addLiveOut(Pred, Succ); 701 } 702 703 BrMap[&Pred] = P.second; 704 return true; 705} 706 707bool Filler::delayHasHazard(const MachineInstr &Candidate, RegDefsUses &RegDU, 708 InspectMemInstr &IM) const { 709 bool HasHazard = (Candidate.isImplicitDef() || Candidate.isKill()); 710 711 HasHazard |= IM.hasHazard(Candidate); 712 HasHazard |= RegDU.update(Candidate, 0, Candidate.getNumOperands()); 713 714 return HasHazard; 715} 716 717bool Filler::terminateSearch(const MachineInstr &Candidate) const { 718 return (Candidate.isTerminator() || Candidate.isCall() || 719 Candidate.isLabel() || Candidate.isInlineAsm() || 720 Candidate.hasUnmodeledSideEffects()); 721} 722