MipsDelaySlotFiller.cpp revision 1f0aca857b899b397a9d82bb21cb1ca819419a90
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 45// This option can be used to silence complaints by machine verifier passes. 46static 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 52static 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 58static 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 64static 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 70namespace { 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 261static bool hasUnoccupiedSlot(const MachineInstr *MI) { 262 return MI->hasDelaySlot() && !MI->isBundledWithSucc(); 263} 264 265/// This function inserts clones of Filler into predecessor blocks. 266static 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. 280static 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 300RegDefsUses::RegDefsUses(TargetMachine &TM) 301 : TRI(*TM.getRegisterInfo()), Defs(TRI.getNumRegs(), false), 302 Uses(TRI.getNumRegs(), false) {} 303 304void 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 321void 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 337void 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 350void 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 360bool 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 377bool 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 390bool 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 398bool 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 420bool 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 439MemDefsUses::MemDefsUses(const MachineFrameInfo *MFI_) 440 : InspectMemInstr(false), MFI(MFI_), SeenNoObjLoad(false), 441 SeenNoObjStore(false) {} 442 443bool 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 466bool 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 474bool MemDefsUses:: 475getUnderlyingObjects(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. 501bool 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 534FunctionPass *llvm::createMipsDelaySlotFillerPass(MipsTargetMachine &tm) { 535 return new Filler(tm); 536} 537 538template<typename IterTy> 539bool 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 563bool 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 583bool 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 604bool 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 648MachineBasicBlock *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 658std::pair<MipsInstrInfo::BranchType, MachineInstr *> 659Filler::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 694bool 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 715bool 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 725bool Filler::terminateSearch(const MachineInstr &Candidate) const { 726 return (Candidate.isTerminator() || Candidate.isCall() || 727 Candidate.isLabel() || Candidate.isInlineAsm() || 728 Candidate.hasUnmodeledSideEffects()); 729} 730