1 //===-- llvm/CodeGen/MachineBasicBlock.cpp ----------------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // Collect the sequence of machine instructions for a basic block. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "llvm/CodeGen/MachineBasicBlock.h" 14 #include "llvm/ADT/SmallPtrSet.h" 15 #include "llvm/CodeGen/LiveIntervals.h" 16 #include "llvm/CodeGen/LiveVariables.h" 17 #include "llvm/CodeGen/MachineDominators.h" 18 #include "llvm/CodeGen/MachineFunction.h" 19 #include "llvm/CodeGen/MachineInstrBuilder.h" 20 #include "llvm/CodeGen/MachineLoopInfo.h" 21 #include "llvm/CodeGen/MachineRegisterInfo.h" 22 #include "llvm/CodeGen/SlotIndexes.h" 23 #include "llvm/CodeGen/TargetInstrInfo.h" 24 #include "llvm/CodeGen/TargetRegisterInfo.h" 25 #include "llvm/CodeGen/TargetSubtargetInfo.h" 26 #include "llvm/Config/llvm-config.h" 27 #include "llvm/IR/BasicBlock.h" 28 #include "llvm/IR/DataLayout.h" 29 #include "llvm/IR/DebugInfoMetadata.h" 30 #include "llvm/IR/ModuleSlotTracker.h" 31 #include "llvm/MC/MCAsmInfo.h" 32 #include "llvm/MC/MCContext.h" 33 #include "llvm/Support/DataTypes.h" 34 #include "llvm/Support/Debug.h" 35 #include "llvm/Support/raw_ostream.h" 36 #include "llvm/Target/TargetMachine.h" 37 #include <algorithm> 38 using namespace llvm; 39 40 #define DEBUG_TYPE "codegen" 41 42 static cl::opt<bool> PrintSlotIndexes( 43 "print-slotindexes", 44 cl::desc("When printing machine IR, annotate instructions and blocks with " 45 "SlotIndexes when available"), 46 cl::init(true), cl::Hidden); 47 48 MachineBasicBlock::MachineBasicBlock(MachineFunction &MF, const BasicBlock *B) 49 : BB(B), Number(-1), xParent(&MF) { 50 Insts.Parent = this; 51 if (B) 52 IrrLoopHeaderWeight = B->getIrrLoopHeaderWeight(); 53 } 54 55 MachineBasicBlock::~MachineBasicBlock() { 56 } 57 58 /// Return the MCSymbol for this basic block. 59 MCSymbol *MachineBasicBlock::getSymbol() const { 60 if (!CachedMCSymbol) { 61 const MachineFunction *MF = getParent(); 62 MCContext &Ctx = MF->getContext(); 63 64 // We emit a non-temporary symbol -- with a descriptive name -- if it begins 65 // a section (with basic block sections). Otherwise we fall back to use temp 66 // label. 67 if (MF->hasBBSections() && isBeginSection()) { 68 SmallString<5> Suffix; 69 if (SectionID == MBBSectionID::ColdSectionID) { 70 Suffix += ".cold"; 71 } else if (SectionID == MBBSectionID::ExceptionSectionID) { 72 Suffix += ".eh"; 73 } else { 74 // For symbols that represent basic block sections, we add ".__part." to 75 // allow tools like symbolizers to know that this represents a part of 76 // the original function. 77 Suffix = (Suffix + Twine(".__part.") + Twine(SectionID.Number)).str(); 78 } 79 CachedMCSymbol = Ctx.getOrCreateSymbol(MF->getName() + Suffix); 80 } else { 81 const StringRef Prefix = Ctx.getAsmInfo()->getPrivateLabelPrefix(); 82 CachedMCSymbol = Ctx.getOrCreateSymbol(Twine(Prefix) + "BB" + 83 Twine(MF->getFunctionNumber()) + 84 "_" + Twine(getNumber())); 85 } 86 } 87 return CachedMCSymbol; 88 } 89 90 MCSymbol *MachineBasicBlock::getEndSymbol() const { 91 if (!CachedEndMCSymbol) { 92 const MachineFunction *MF = getParent(); 93 MCContext &Ctx = MF->getContext(); 94 auto Prefix = Ctx.getAsmInfo()->getPrivateLabelPrefix(); 95 CachedEndMCSymbol = Ctx.getOrCreateSymbol(Twine(Prefix) + "BB_END" + 96 Twine(MF->getFunctionNumber()) + 97 "_" + Twine(getNumber())); 98 } 99 return CachedEndMCSymbol; 100 } 101 102 raw_ostream &llvm::operator<<(raw_ostream &OS, const MachineBasicBlock &MBB) { 103 MBB.print(OS); 104 return OS; 105 } 106 107 Printable llvm::printMBBReference(const MachineBasicBlock &MBB) { 108 return Printable([&MBB](raw_ostream &OS) { return MBB.printAsOperand(OS); }); 109 } 110 111 /// When an MBB is added to an MF, we need to update the parent pointer of the 112 /// MBB, the MBB numbering, and any instructions in the MBB to be on the right 113 /// operand list for registers. 114 /// 115 /// MBBs start out as #-1. When a MBB is added to a MachineFunction, it 116 /// gets the next available unique MBB number. If it is removed from a 117 /// MachineFunction, it goes back to being #-1. 118 void ilist_callback_traits<MachineBasicBlock>::addNodeToList( 119 MachineBasicBlock *N) { 120 MachineFunction &MF = *N->getParent(); 121 N->Number = MF.addToMBBNumbering(N); 122 123 // Make sure the instructions have their operands in the reginfo lists. 124 MachineRegisterInfo &RegInfo = MF.getRegInfo(); 125 for (MachineBasicBlock::instr_iterator 126 I = N->instr_begin(), E = N->instr_end(); I != E; ++I) 127 I->AddRegOperandsToUseLists(RegInfo); 128 } 129 130 void ilist_callback_traits<MachineBasicBlock>::removeNodeFromList( 131 MachineBasicBlock *N) { 132 N->getParent()->removeFromMBBNumbering(N->Number); 133 N->Number = -1; 134 } 135 136 /// When we add an instruction to a basic block list, we update its parent 137 /// pointer and add its operands from reg use/def lists if appropriate. 138 void ilist_traits<MachineInstr>::addNodeToList(MachineInstr *N) { 139 assert(!N->getParent() && "machine instruction already in a basic block"); 140 N->setParent(Parent); 141 142 // Add the instruction's register operands to their corresponding 143 // use/def lists. 144 MachineFunction *MF = Parent->getParent(); 145 N->AddRegOperandsToUseLists(MF->getRegInfo()); 146 MF->handleInsertion(*N); 147 } 148 149 /// When we remove an instruction from a basic block list, we update its parent 150 /// pointer and remove its operands from reg use/def lists if appropriate. 151 void ilist_traits<MachineInstr>::removeNodeFromList(MachineInstr *N) { 152 assert(N->getParent() && "machine instruction not in a basic block"); 153 154 // Remove from the use/def lists. 155 if (MachineFunction *MF = N->getMF()) { 156 MF->handleRemoval(*N); 157 N->RemoveRegOperandsFromUseLists(MF->getRegInfo()); 158 } 159 160 N->setParent(nullptr); 161 } 162 163 /// When moving a range of instructions from one MBB list to another, we need to 164 /// update the parent pointers and the use/def lists. 165 void ilist_traits<MachineInstr>::transferNodesFromList(ilist_traits &FromList, 166 instr_iterator First, 167 instr_iterator Last) { 168 assert(Parent->getParent() == FromList.Parent->getParent() && 169 "cannot transfer MachineInstrs between MachineFunctions"); 170 171 // If it's within the same BB, there's nothing to do. 172 if (this == &FromList) 173 return; 174 175 assert(Parent != FromList.Parent && "Two lists have the same parent?"); 176 177 // If splicing between two blocks within the same function, just update the 178 // parent pointers. 179 for (; First != Last; ++First) 180 First->setParent(Parent); 181 } 182 183 void ilist_traits<MachineInstr>::deleteNode(MachineInstr *MI) { 184 assert(!MI->getParent() && "MI is still in a block!"); 185 Parent->getParent()->DeleteMachineInstr(MI); 186 } 187 188 MachineBasicBlock::iterator MachineBasicBlock::getFirstNonPHI() { 189 instr_iterator I = instr_begin(), E = instr_end(); 190 while (I != E && I->isPHI()) 191 ++I; 192 assert((I == E || !I->isInsideBundle()) && 193 "First non-phi MI cannot be inside a bundle!"); 194 return I; 195 } 196 197 MachineBasicBlock::iterator 198 MachineBasicBlock::SkipPHIsAndLabels(MachineBasicBlock::iterator I) { 199 const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo(); 200 201 iterator E = end(); 202 while (I != E && (I->isPHI() || I->isPosition() || 203 TII->isBasicBlockPrologue(*I))) 204 ++I; 205 // FIXME: This needs to change if we wish to bundle labels 206 // inside the bundle. 207 assert((I == E || !I->isInsideBundle()) && 208 "First non-phi / non-label instruction is inside a bundle!"); 209 return I; 210 } 211 212 MachineBasicBlock::iterator 213 MachineBasicBlock::SkipPHIsLabelsAndDebug(MachineBasicBlock::iterator I) { 214 const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo(); 215 216 iterator E = end(); 217 while (I != E && (I->isPHI() || I->isPosition() || I->isDebugInstr() || 218 TII->isBasicBlockPrologue(*I))) 219 ++I; 220 // FIXME: This needs to change if we wish to bundle labels / dbg_values 221 // inside the bundle. 222 assert((I == E || !I->isInsideBundle()) && 223 "First non-phi / non-label / non-debug " 224 "instruction is inside a bundle!"); 225 return I; 226 } 227 228 MachineBasicBlock::iterator MachineBasicBlock::getFirstTerminator() { 229 iterator B = begin(), E = end(), I = E; 230 while (I != B && ((--I)->isTerminator() || I->isDebugInstr())) 231 ; /*noop */ 232 while (I != E && !I->isTerminator()) 233 ++I; 234 return I; 235 } 236 237 MachineBasicBlock::instr_iterator MachineBasicBlock::getFirstInstrTerminator() { 238 instr_iterator B = instr_begin(), E = instr_end(), I = E; 239 while (I != B && ((--I)->isTerminator() || I->isDebugInstr())) 240 ; /*noop */ 241 while (I != E && !I->isTerminator()) 242 ++I; 243 return I; 244 } 245 246 MachineBasicBlock::iterator MachineBasicBlock::getFirstNonDebugInstr() { 247 // Skip over begin-of-block dbg_value instructions. 248 return skipDebugInstructionsForward(begin(), end()); 249 } 250 251 MachineBasicBlock::iterator MachineBasicBlock::getLastNonDebugInstr() { 252 // Skip over end-of-block dbg_value instructions. 253 instr_iterator B = instr_begin(), I = instr_end(); 254 while (I != B) { 255 --I; 256 // Return instruction that starts a bundle. 257 if (I->isDebugInstr() || I->isInsideBundle()) 258 continue; 259 return I; 260 } 261 // The block is all debug values. 262 return end(); 263 } 264 265 bool MachineBasicBlock::hasEHPadSuccessor() const { 266 for (const_succ_iterator I = succ_begin(), E = succ_end(); I != E; ++I) 267 if ((*I)->isEHPad()) 268 return true; 269 return false; 270 } 271 272 bool MachineBasicBlock::isEntryBlock() const { 273 return getParent()->begin() == getIterator(); 274 } 275 276 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 277 LLVM_DUMP_METHOD void MachineBasicBlock::dump() const { 278 print(dbgs()); 279 } 280 #endif 281 282 bool MachineBasicBlock::mayHaveInlineAsmBr() const { 283 for (const MachineBasicBlock *Succ : successors()) { 284 if (Succ->isInlineAsmBrIndirectTarget()) 285 return true; 286 } 287 return false; 288 } 289 290 bool MachineBasicBlock::isLegalToHoistInto() const { 291 if (isReturnBlock() || hasEHPadSuccessor() || mayHaveInlineAsmBr()) 292 return false; 293 return true; 294 } 295 296 StringRef MachineBasicBlock::getName() const { 297 if (const BasicBlock *LBB = getBasicBlock()) 298 return LBB->getName(); 299 else 300 return StringRef("", 0); 301 } 302 303 /// Return a hopefully unique identifier for this block. 304 std::string MachineBasicBlock::getFullName() const { 305 std::string Name; 306 if (getParent()) 307 Name = (getParent()->getName() + ":").str(); 308 if (getBasicBlock()) 309 Name += getBasicBlock()->getName(); 310 else 311 Name += ("BB" + Twine(getNumber())).str(); 312 return Name; 313 } 314 315 void MachineBasicBlock::print(raw_ostream &OS, const SlotIndexes *Indexes, 316 bool IsStandalone) const { 317 const MachineFunction *MF = getParent(); 318 if (!MF) { 319 OS << "Can't print out MachineBasicBlock because parent MachineFunction" 320 << " is null\n"; 321 return; 322 } 323 const Function &F = MF->getFunction(); 324 const Module *M = F.getParent(); 325 ModuleSlotTracker MST(M); 326 MST.incorporateFunction(F); 327 print(OS, MST, Indexes, IsStandalone); 328 } 329 330 void MachineBasicBlock::print(raw_ostream &OS, ModuleSlotTracker &MST, 331 const SlotIndexes *Indexes, 332 bool IsStandalone) const { 333 const MachineFunction *MF = getParent(); 334 if (!MF) { 335 OS << "Can't print out MachineBasicBlock because parent MachineFunction" 336 << " is null\n"; 337 return; 338 } 339 340 if (Indexes && PrintSlotIndexes) 341 OS << Indexes->getMBBStartIdx(this) << '\t'; 342 343 printName(OS, PrintNameIr | PrintNameAttributes, &MST); 344 OS << ":\n"; 345 346 const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo(); 347 const MachineRegisterInfo &MRI = MF->getRegInfo(); 348 const TargetInstrInfo &TII = *getParent()->getSubtarget().getInstrInfo(); 349 bool HasLineAttributes = false; 350 351 // Print the preds of this block according to the CFG. 352 if (!pred_empty() && IsStandalone) { 353 if (Indexes) OS << '\t'; 354 // Don't indent(2), align with previous line attributes. 355 OS << "; predecessors: "; 356 ListSeparator LS; 357 for (auto *Pred : predecessors()) 358 OS << LS << printMBBReference(*Pred); 359 OS << '\n'; 360 HasLineAttributes = true; 361 } 362 363 if (!succ_empty()) { 364 if (Indexes) OS << '\t'; 365 // Print the successors 366 OS.indent(2) << "successors: "; 367 ListSeparator LS; 368 for (auto I = succ_begin(), E = succ_end(); I != E; ++I) { 369 OS << LS << printMBBReference(**I); 370 if (!Probs.empty()) 371 OS << '(' 372 << format("0x%08" PRIx32, getSuccProbability(I).getNumerator()) 373 << ')'; 374 } 375 if (!Probs.empty() && IsStandalone) { 376 // Print human readable probabilities as comments. 377 OS << "; "; 378 ListSeparator LS; 379 for (auto I = succ_begin(), E = succ_end(); I != E; ++I) { 380 const BranchProbability &BP = getSuccProbability(I); 381 OS << LS << printMBBReference(**I) << '(' 382 << format("%.2f%%", 383 rint(((double)BP.getNumerator() / BP.getDenominator()) * 384 100.0 * 100.0) / 385 100.0) 386 << ')'; 387 } 388 } 389 390 OS << '\n'; 391 HasLineAttributes = true; 392 } 393 394 if (!livein_empty() && MRI.tracksLiveness()) { 395 if (Indexes) OS << '\t'; 396 OS.indent(2) << "liveins: "; 397 398 ListSeparator LS; 399 for (const auto &LI : liveins()) { 400 OS << LS << printReg(LI.PhysReg, TRI); 401 if (!LI.LaneMask.all()) 402 OS << ":0x" << PrintLaneMask(LI.LaneMask); 403 } 404 HasLineAttributes = true; 405 } 406 407 if (HasLineAttributes) 408 OS << '\n'; 409 410 bool IsInBundle = false; 411 for (const MachineInstr &MI : instrs()) { 412 if (Indexes && PrintSlotIndexes) { 413 if (Indexes->hasIndex(MI)) 414 OS << Indexes->getInstructionIndex(MI); 415 OS << '\t'; 416 } 417 418 if (IsInBundle && !MI.isInsideBundle()) { 419 OS.indent(2) << "}\n"; 420 IsInBundle = false; 421 } 422 423 OS.indent(IsInBundle ? 4 : 2); 424 MI.print(OS, MST, IsStandalone, /*SkipOpers=*/false, /*SkipDebugLoc=*/false, 425 /*AddNewLine=*/false, &TII); 426 427 if (!IsInBundle && MI.getFlag(MachineInstr::BundledSucc)) { 428 OS << " {"; 429 IsInBundle = true; 430 } 431 OS << '\n'; 432 } 433 434 if (IsInBundle) 435 OS.indent(2) << "}\n"; 436 437 if (IrrLoopHeaderWeight && IsStandalone) { 438 if (Indexes) OS << '\t'; 439 OS.indent(2) << "; Irreducible loop header weight: " 440 << IrrLoopHeaderWeight.getValue() << '\n'; 441 } 442 } 443 444 /// Print the basic block's name as: 445 /// 446 /// bb.{number}[.{ir-name}] [(attributes...)] 447 /// 448 /// The {ir-name} is only printed when the \ref PrintNameIr flag is passed 449 /// (which is the default). If the IR block has no name, it is identified 450 /// numerically using the attribute syntax as "(%ir-block.{ir-slot})". 451 /// 452 /// When the \ref PrintNameAttributes flag is passed, additional attributes 453 /// of the block are printed when set. 454 /// 455 /// \param printNameFlags Combination of \ref PrintNameFlag flags indicating 456 /// the parts to print. 457 /// \param moduleSlotTracker Optional ModuleSlotTracker. This method will 458 /// incorporate its own tracker when necessary to 459 /// determine the block's IR name. 460 void MachineBasicBlock::printName(raw_ostream &os, unsigned printNameFlags, 461 ModuleSlotTracker *moduleSlotTracker) const { 462 os << "bb." << getNumber(); 463 bool hasAttributes = false; 464 465 if (printNameFlags & PrintNameIr) { 466 if (const auto *bb = getBasicBlock()) { 467 if (bb->hasName()) { 468 os << '.' << bb->getName(); 469 } else { 470 hasAttributes = true; 471 os << " ("; 472 473 int slot = -1; 474 475 if (moduleSlotTracker) { 476 slot = moduleSlotTracker->getLocalSlot(bb); 477 } else if (bb->getParent()) { 478 ModuleSlotTracker tmpTracker(bb->getModule(), false); 479 tmpTracker.incorporateFunction(*bb->getParent()); 480 slot = tmpTracker.getLocalSlot(bb); 481 } 482 483 if (slot == -1) 484 os << "<ir-block badref>"; 485 else 486 os << (Twine("%ir-block.") + Twine(slot)).str(); 487 } 488 } 489 } 490 491 if (printNameFlags & PrintNameAttributes) { 492 if (hasAddressTaken()) { 493 os << (hasAttributes ? ", " : " ("); 494 os << "address-taken"; 495 hasAttributes = true; 496 } 497 if (isEHPad()) { 498 os << (hasAttributes ? ", " : " ("); 499 os << "landing-pad"; 500 hasAttributes = true; 501 } 502 if (isEHFuncletEntry()) { 503 os << (hasAttributes ? ", " : " ("); 504 os << "ehfunclet-entry"; 505 hasAttributes = true; 506 } 507 if (getAlignment() != Align(1)) { 508 os << (hasAttributes ? ", " : " ("); 509 os << "align " << getAlignment().value(); 510 hasAttributes = true; 511 } 512 if (getSectionID() != MBBSectionID(0)) { 513 os << (hasAttributes ? ", " : " ("); 514 os << "bbsections "; 515 switch (getSectionID().Type) { 516 case MBBSectionID::SectionType::Exception: 517 os << "Exception"; 518 break; 519 case MBBSectionID::SectionType::Cold: 520 os << "Cold"; 521 break; 522 default: 523 os << getSectionID().Number; 524 } 525 hasAttributes = true; 526 } 527 } 528 529 if (hasAttributes) 530 os << ')'; 531 } 532 533 void MachineBasicBlock::printAsOperand(raw_ostream &OS, 534 bool /*PrintType*/) const { 535 OS << '%'; 536 printName(OS, 0); 537 } 538 539 void MachineBasicBlock::removeLiveIn(MCPhysReg Reg, LaneBitmask LaneMask) { 540 LiveInVector::iterator I = find_if( 541 LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; }); 542 if (I == LiveIns.end()) 543 return; 544 545 I->LaneMask &= ~LaneMask; 546 if (I->LaneMask.none()) 547 LiveIns.erase(I); 548 } 549 550 MachineBasicBlock::livein_iterator 551 MachineBasicBlock::removeLiveIn(MachineBasicBlock::livein_iterator I) { 552 // Get non-const version of iterator. 553 LiveInVector::iterator LI = LiveIns.begin() + (I - LiveIns.begin()); 554 return LiveIns.erase(LI); 555 } 556 557 bool MachineBasicBlock::isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask) const { 558 livein_iterator I = find_if( 559 LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; }); 560 return I != livein_end() && (I->LaneMask & LaneMask).any(); 561 } 562 563 void MachineBasicBlock::sortUniqueLiveIns() { 564 llvm::sort(LiveIns, 565 [](const RegisterMaskPair &LI0, const RegisterMaskPair &LI1) { 566 return LI0.PhysReg < LI1.PhysReg; 567 }); 568 // Liveins are sorted by physreg now we can merge their lanemasks. 569 LiveInVector::const_iterator I = LiveIns.begin(); 570 LiveInVector::const_iterator J; 571 LiveInVector::iterator Out = LiveIns.begin(); 572 for (; I != LiveIns.end(); ++Out, I = J) { 573 MCRegister PhysReg = I->PhysReg; 574 LaneBitmask LaneMask = I->LaneMask; 575 for (J = std::next(I); J != LiveIns.end() && J->PhysReg == PhysReg; ++J) 576 LaneMask |= J->LaneMask; 577 Out->PhysReg = PhysReg; 578 Out->LaneMask = LaneMask; 579 } 580 LiveIns.erase(Out, LiveIns.end()); 581 } 582 583 Register 584 MachineBasicBlock::addLiveIn(MCRegister PhysReg, const TargetRegisterClass *RC) { 585 assert(getParent() && "MBB must be inserted in function"); 586 assert(Register::isPhysicalRegister(PhysReg) && "Expected physreg"); 587 assert(RC && "Register class is required"); 588 assert((isEHPad() || this == &getParent()->front()) && 589 "Only the entry block and landing pads can have physreg live ins"); 590 591 bool LiveIn = isLiveIn(PhysReg); 592 iterator I = SkipPHIsAndLabels(begin()), E = end(); 593 MachineRegisterInfo &MRI = getParent()->getRegInfo(); 594 const TargetInstrInfo &TII = *getParent()->getSubtarget().getInstrInfo(); 595 596 // Look for an existing copy. 597 if (LiveIn) 598 for (;I != E && I->isCopy(); ++I) 599 if (I->getOperand(1).getReg() == PhysReg) { 600 Register VirtReg = I->getOperand(0).getReg(); 601 if (!MRI.constrainRegClass(VirtReg, RC)) 602 llvm_unreachable("Incompatible live-in register class."); 603 return VirtReg; 604 } 605 606 // No luck, create a virtual register. 607 Register VirtReg = MRI.createVirtualRegister(RC); 608 BuildMI(*this, I, DebugLoc(), TII.get(TargetOpcode::COPY), VirtReg) 609 .addReg(PhysReg, RegState::Kill); 610 if (!LiveIn) 611 addLiveIn(PhysReg); 612 return VirtReg; 613 } 614 615 void MachineBasicBlock::moveBefore(MachineBasicBlock *NewAfter) { 616 getParent()->splice(NewAfter->getIterator(), getIterator()); 617 } 618 619 void MachineBasicBlock::moveAfter(MachineBasicBlock *NewBefore) { 620 getParent()->splice(++NewBefore->getIterator(), getIterator()); 621 } 622 623 void MachineBasicBlock::updateTerminator( 624 MachineBasicBlock *PreviousLayoutSuccessor) { 625 LLVM_DEBUG(dbgs() << "Updating terminators on " << printMBBReference(*this) 626 << "\n"); 627 628 const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo(); 629 // A block with no successors has no concerns with fall-through edges. 630 if (this->succ_empty()) 631 return; 632 633 MachineBasicBlock *TBB = nullptr, *FBB = nullptr; 634 SmallVector<MachineOperand, 4> Cond; 635 DebugLoc DL = findBranchDebugLoc(); 636 bool B = TII->analyzeBranch(*this, TBB, FBB, Cond); 637 (void) B; 638 assert(!B && "UpdateTerminators requires analyzable predecessors!"); 639 if (Cond.empty()) { 640 if (TBB) { 641 // The block has an unconditional branch. If its successor is now its 642 // layout successor, delete the branch. 643 if (isLayoutSuccessor(TBB)) 644 TII->removeBranch(*this); 645 } else { 646 // The block has an unconditional fallthrough, or the end of the block is 647 // unreachable. 648 649 // Unfortunately, whether the end of the block is unreachable is not 650 // immediately obvious; we must fall back to checking the successor list, 651 // and assuming that if the passed in block is in the succesor list and 652 // not an EHPad, it must be the intended target. 653 if (!PreviousLayoutSuccessor || !isSuccessor(PreviousLayoutSuccessor) || 654 PreviousLayoutSuccessor->isEHPad()) 655 return; 656 657 // If the unconditional successor block is not the current layout 658 // successor, insert a branch to jump to it. 659 if (!isLayoutSuccessor(PreviousLayoutSuccessor)) 660 TII->insertBranch(*this, PreviousLayoutSuccessor, nullptr, Cond, DL); 661 } 662 return; 663 } 664 665 if (FBB) { 666 // The block has a non-fallthrough conditional branch. If one of its 667 // successors is its layout successor, rewrite it to a fallthrough 668 // conditional branch. 669 if (isLayoutSuccessor(TBB)) { 670 if (TII->reverseBranchCondition(Cond)) 671 return; 672 TII->removeBranch(*this); 673 TII->insertBranch(*this, FBB, nullptr, Cond, DL); 674 } else if (isLayoutSuccessor(FBB)) { 675 TII->removeBranch(*this); 676 TII->insertBranch(*this, TBB, nullptr, Cond, DL); 677 } 678 return; 679 } 680 681 // We now know we're going to fallthrough to PreviousLayoutSuccessor. 682 assert(PreviousLayoutSuccessor); 683 assert(!PreviousLayoutSuccessor->isEHPad()); 684 assert(isSuccessor(PreviousLayoutSuccessor)); 685 686 if (PreviousLayoutSuccessor == TBB) { 687 // We had a fallthrough to the same basic block as the conditional jump 688 // targets. Remove the conditional jump, leaving an unconditional 689 // fallthrough or an unconditional jump. 690 TII->removeBranch(*this); 691 if (!isLayoutSuccessor(TBB)) { 692 Cond.clear(); 693 TII->insertBranch(*this, TBB, nullptr, Cond, DL); 694 } 695 return; 696 } 697 698 // The block has a fallthrough conditional branch. 699 if (isLayoutSuccessor(TBB)) { 700 if (TII->reverseBranchCondition(Cond)) { 701 // We can't reverse the condition, add an unconditional branch. 702 Cond.clear(); 703 TII->insertBranch(*this, PreviousLayoutSuccessor, nullptr, Cond, DL); 704 return; 705 } 706 TII->removeBranch(*this); 707 TII->insertBranch(*this, PreviousLayoutSuccessor, nullptr, Cond, DL); 708 } else if (!isLayoutSuccessor(PreviousLayoutSuccessor)) { 709 TII->removeBranch(*this); 710 TII->insertBranch(*this, TBB, PreviousLayoutSuccessor, Cond, DL); 711 } 712 } 713 714 void MachineBasicBlock::validateSuccProbs() const { 715 #ifndef NDEBUG 716 int64_t Sum = 0; 717 for (auto Prob : Probs) 718 Sum += Prob.getNumerator(); 719 // Due to precision issue, we assume that the sum of probabilities is one if 720 // the difference between the sum of their numerators and the denominator is 721 // no greater than the number of successors. 722 assert((uint64_t)std::abs(Sum - BranchProbability::getDenominator()) <= 723 Probs.size() && 724 "The sum of successors's probabilities exceeds one."); 725 #endif // NDEBUG 726 } 727 728 void MachineBasicBlock::addSuccessor(MachineBasicBlock *Succ, 729 BranchProbability Prob) { 730 // Probability list is either empty (if successor list isn't empty, this means 731 // disabled optimization) or has the same size as successor list. 732 if (!(Probs.empty() && !Successors.empty())) 733 Probs.push_back(Prob); 734 Successors.push_back(Succ); 735 Succ->addPredecessor(this); 736 } 737 738 void MachineBasicBlock::addSuccessorWithoutProb(MachineBasicBlock *Succ) { 739 // We need to make sure probability list is either empty or has the same size 740 // of successor list. When this function is called, we can safely delete all 741 // probability in the list. 742 Probs.clear(); 743 Successors.push_back(Succ); 744 Succ->addPredecessor(this); 745 } 746 747 void MachineBasicBlock::splitSuccessor(MachineBasicBlock *Old, 748 MachineBasicBlock *New, 749 bool NormalizeSuccProbs) { 750 succ_iterator OldI = llvm::find(successors(), Old); 751 assert(OldI != succ_end() && "Old is not a successor of this block!"); 752 assert(!llvm::is_contained(successors(), New) && 753 "New is already a successor of this block!"); 754 755 // Add a new successor with equal probability as the original one. Note 756 // that we directly copy the probability using the iterator rather than 757 // getting a potentially synthetic probability computed when unknown. This 758 // preserves the probabilities as-is and then we can renormalize them and 759 // query them effectively afterward. 760 addSuccessor(New, Probs.empty() ? BranchProbability::getUnknown() 761 : *getProbabilityIterator(OldI)); 762 if (NormalizeSuccProbs) 763 normalizeSuccProbs(); 764 } 765 766 void MachineBasicBlock::removeSuccessor(MachineBasicBlock *Succ, 767 bool NormalizeSuccProbs) { 768 succ_iterator I = find(Successors, Succ); 769 removeSuccessor(I, NormalizeSuccProbs); 770 } 771 772 MachineBasicBlock::succ_iterator 773 MachineBasicBlock::removeSuccessor(succ_iterator I, bool NormalizeSuccProbs) { 774 assert(I != Successors.end() && "Not a current successor!"); 775 776 // If probability list is empty it means we don't use it (disabled 777 // optimization). 778 if (!Probs.empty()) { 779 probability_iterator WI = getProbabilityIterator(I); 780 Probs.erase(WI); 781 if (NormalizeSuccProbs) 782 normalizeSuccProbs(); 783 } 784 785 (*I)->removePredecessor(this); 786 return Successors.erase(I); 787 } 788 789 void MachineBasicBlock::replaceSuccessor(MachineBasicBlock *Old, 790 MachineBasicBlock *New) { 791 if (Old == New) 792 return; 793 794 succ_iterator E = succ_end(); 795 succ_iterator NewI = E; 796 succ_iterator OldI = E; 797 for (succ_iterator I = succ_begin(); I != E; ++I) { 798 if (*I == Old) { 799 OldI = I; 800 if (NewI != E) 801 break; 802 } 803 if (*I == New) { 804 NewI = I; 805 if (OldI != E) 806 break; 807 } 808 } 809 assert(OldI != E && "Old is not a successor of this block"); 810 811 // If New isn't already a successor, let it take Old's place. 812 if (NewI == E) { 813 Old->removePredecessor(this); 814 New->addPredecessor(this); 815 *OldI = New; 816 return; 817 } 818 819 // New is already a successor. 820 // Update its probability instead of adding a duplicate edge. 821 if (!Probs.empty()) { 822 auto ProbIter = getProbabilityIterator(NewI); 823 if (!ProbIter->isUnknown()) 824 *ProbIter += *getProbabilityIterator(OldI); 825 } 826 removeSuccessor(OldI); 827 } 828 829 void MachineBasicBlock::copySuccessor(MachineBasicBlock *Orig, 830 succ_iterator I) { 831 if (!Orig->Probs.empty()) 832 addSuccessor(*I, Orig->getSuccProbability(I)); 833 else 834 addSuccessorWithoutProb(*I); 835 } 836 837 void MachineBasicBlock::addPredecessor(MachineBasicBlock *Pred) { 838 Predecessors.push_back(Pred); 839 } 840 841 void MachineBasicBlock::removePredecessor(MachineBasicBlock *Pred) { 842 pred_iterator I = find(Predecessors, Pred); 843 assert(I != Predecessors.end() && "Pred is not a predecessor of this block!"); 844 Predecessors.erase(I); 845 } 846 847 void MachineBasicBlock::transferSuccessors(MachineBasicBlock *FromMBB) { 848 if (this == FromMBB) 849 return; 850 851 while (!FromMBB->succ_empty()) { 852 MachineBasicBlock *Succ = *FromMBB->succ_begin(); 853 854 // If probability list is empty it means we don't use it (disabled 855 // optimization). 856 if (!FromMBB->Probs.empty()) { 857 auto Prob = *FromMBB->Probs.begin(); 858 addSuccessor(Succ, Prob); 859 } else 860 addSuccessorWithoutProb(Succ); 861 862 FromMBB->removeSuccessor(Succ); 863 } 864 } 865 866 void 867 MachineBasicBlock::transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB) { 868 if (this == FromMBB) 869 return; 870 871 while (!FromMBB->succ_empty()) { 872 MachineBasicBlock *Succ = *FromMBB->succ_begin(); 873 if (!FromMBB->Probs.empty()) { 874 auto Prob = *FromMBB->Probs.begin(); 875 addSuccessor(Succ, Prob); 876 } else 877 addSuccessorWithoutProb(Succ); 878 FromMBB->removeSuccessor(Succ); 879 880 // Fix up any PHI nodes in the successor. 881 Succ->replacePhiUsesWith(FromMBB, this); 882 } 883 normalizeSuccProbs(); 884 } 885 886 bool MachineBasicBlock::isPredecessor(const MachineBasicBlock *MBB) const { 887 return is_contained(predecessors(), MBB); 888 } 889 890 bool MachineBasicBlock::isSuccessor(const MachineBasicBlock *MBB) const { 891 return is_contained(successors(), MBB); 892 } 893 894 bool MachineBasicBlock::isLayoutSuccessor(const MachineBasicBlock *MBB) const { 895 MachineFunction::const_iterator I(this); 896 return std::next(I) == MachineFunction::const_iterator(MBB); 897 } 898 899 MachineBasicBlock *MachineBasicBlock::getFallThrough() { 900 MachineFunction::iterator Fallthrough = getIterator(); 901 ++Fallthrough; 902 // If FallthroughBlock is off the end of the function, it can't fall through. 903 if (Fallthrough == getParent()->end()) 904 return nullptr; 905 906 // If FallthroughBlock isn't a successor, no fallthrough is possible. 907 if (!isSuccessor(&*Fallthrough)) 908 return nullptr; 909 910 // Analyze the branches, if any, at the end of the block. 911 MachineBasicBlock *TBB = nullptr, *FBB = nullptr; 912 SmallVector<MachineOperand, 4> Cond; 913 const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo(); 914 if (TII->analyzeBranch(*this, TBB, FBB, Cond)) { 915 // If we couldn't analyze the branch, examine the last instruction. 916 // If the block doesn't end in a known control barrier, assume fallthrough 917 // is possible. The isPredicated check is needed because this code can be 918 // called during IfConversion, where an instruction which is normally a 919 // Barrier is predicated and thus no longer an actual control barrier. 920 return (empty() || !back().isBarrier() || TII->isPredicated(back())) 921 ? &*Fallthrough 922 : nullptr; 923 } 924 925 // If there is no branch, control always falls through. 926 if (!TBB) return &*Fallthrough; 927 928 // If there is some explicit branch to the fallthrough block, it can obviously 929 // reach, even though the branch should get folded to fall through implicitly. 930 if (MachineFunction::iterator(TBB) == Fallthrough || 931 MachineFunction::iterator(FBB) == Fallthrough) 932 return &*Fallthrough; 933 934 // If it's an unconditional branch to some block not the fall through, it 935 // doesn't fall through. 936 if (Cond.empty()) return nullptr; 937 938 // Otherwise, if it is conditional and has no explicit false block, it falls 939 // through. 940 return (FBB == nullptr) ? &*Fallthrough : nullptr; 941 } 942 943 bool MachineBasicBlock::canFallThrough() { 944 return getFallThrough() != nullptr; 945 } 946 947 MachineBasicBlock *MachineBasicBlock::splitAt(MachineInstr &MI, 948 bool UpdateLiveIns, 949 LiveIntervals *LIS) { 950 MachineBasicBlock::iterator SplitPoint(&MI); 951 ++SplitPoint; 952 953 if (SplitPoint == end()) { 954 // Don't bother with a new block. 955 return this; 956 } 957 958 MachineFunction *MF = getParent(); 959 960 LivePhysRegs LiveRegs; 961 if (UpdateLiveIns) { 962 // Make sure we add any physregs we define in the block as liveins to the 963 // new block. 964 MachineBasicBlock::iterator Prev(&MI); 965 LiveRegs.init(*MF->getSubtarget().getRegisterInfo()); 966 LiveRegs.addLiveOuts(*this); 967 for (auto I = rbegin(), E = Prev.getReverse(); I != E; ++I) 968 LiveRegs.stepBackward(*I); 969 } 970 971 MachineBasicBlock *SplitBB = MF->CreateMachineBasicBlock(getBasicBlock()); 972 973 MF->insert(++MachineFunction::iterator(this), SplitBB); 974 SplitBB->splice(SplitBB->begin(), this, SplitPoint, end()); 975 976 SplitBB->transferSuccessorsAndUpdatePHIs(this); 977 addSuccessor(SplitBB); 978 979 if (UpdateLiveIns) 980 addLiveIns(*SplitBB, LiveRegs); 981 982 if (LIS) 983 LIS->insertMBBInMaps(SplitBB); 984 985 return SplitBB; 986 } 987 988 MachineBasicBlock *MachineBasicBlock::SplitCriticalEdge( 989 MachineBasicBlock *Succ, Pass &P, 990 std::vector<SparseBitVector<>> *LiveInSets) { 991 if (!canSplitCriticalEdge(Succ)) 992 return nullptr; 993 994 MachineFunction *MF = getParent(); 995 MachineBasicBlock *PrevFallthrough = getNextNode(); 996 DebugLoc DL; // FIXME: this is nowhere 997 998 MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock(); 999 MF->insert(std::next(MachineFunction::iterator(this)), NMBB); 1000 LLVM_DEBUG(dbgs() << "Splitting critical edge: " << printMBBReference(*this) 1001 << " -- " << printMBBReference(*NMBB) << " -- " 1002 << printMBBReference(*Succ) << '\n'); 1003 1004 LiveIntervals *LIS = P.getAnalysisIfAvailable<LiveIntervals>(); 1005 SlotIndexes *Indexes = P.getAnalysisIfAvailable<SlotIndexes>(); 1006 if (LIS) 1007 LIS->insertMBBInMaps(NMBB); 1008 else if (Indexes) 1009 Indexes->insertMBBInMaps(NMBB); 1010 1011 // On some targets like Mips, branches may kill virtual registers. Make sure 1012 // that LiveVariables is properly updated after updateTerminator replaces the 1013 // terminators. 1014 LiveVariables *LV = P.getAnalysisIfAvailable<LiveVariables>(); 1015 1016 // Collect a list of virtual registers killed by the terminators. 1017 SmallVector<Register, 4> KilledRegs; 1018 if (LV) 1019 for (instr_iterator I = getFirstInstrTerminator(), E = instr_end(); 1020 I != E; ++I) { 1021 MachineInstr *MI = &*I; 1022 for (MachineInstr::mop_iterator OI = MI->operands_begin(), 1023 OE = MI->operands_end(); OI != OE; ++OI) { 1024 if (!OI->isReg() || OI->getReg() == 0 || 1025 !OI->isUse() || !OI->isKill() || OI->isUndef()) 1026 continue; 1027 Register Reg = OI->getReg(); 1028 if (Register::isPhysicalRegister(Reg) || 1029 LV->getVarInfo(Reg).removeKill(*MI)) { 1030 KilledRegs.push_back(Reg); 1031 LLVM_DEBUG(dbgs() << "Removing terminator kill: " << *MI); 1032 OI->setIsKill(false); 1033 } 1034 } 1035 } 1036 1037 SmallVector<Register, 4> UsedRegs; 1038 if (LIS) { 1039 for (instr_iterator I = getFirstInstrTerminator(), E = instr_end(); 1040 I != E; ++I) { 1041 MachineInstr *MI = &*I; 1042 1043 for (MachineInstr::mop_iterator OI = MI->operands_begin(), 1044 OE = MI->operands_end(); OI != OE; ++OI) { 1045 if (!OI->isReg() || OI->getReg() == 0) 1046 continue; 1047 1048 Register Reg = OI->getReg(); 1049 if (!is_contained(UsedRegs, Reg)) 1050 UsedRegs.push_back(Reg); 1051 } 1052 } 1053 } 1054 1055 ReplaceUsesOfBlockWith(Succ, NMBB); 1056 1057 // If updateTerminator() removes instructions, we need to remove them from 1058 // SlotIndexes. 1059 SmallVector<MachineInstr*, 4> Terminators; 1060 if (Indexes) { 1061 for (instr_iterator I = getFirstInstrTerminator(), E = instr_end(); 1062 I != E; ++I) 1063 Terminators.push_back(&*I); 1064 } 1065 1066 // Since we replaced all uses of Succ with NMBB, that should also be treated 1067 // as the fallthrough successor 1068 if (Succ == PrevFallthrough) 1069 PrevFallthrough = NMBB; 1070 updateTerminator(PrevFallthrough); 1071 1072 if (Indexes) { 1073 SmallVector<MachineInstr*, 4> NewTerminators; 1074 for (instr_iterator I = getFirstInstrTerminator(), E = instr_end(); 1075 I != E; ++I) 1076 NewTerminators.push_back(&*I); 1077 1078 for (SmallVectorImpl<MachineInstr*>::iterator I = Terminators.begin(), 1079 E = Terminators.end(); I != E; ++I) { 1080 if (!is_contained(NewTerminators, *I)) 1081 Indexes->removeMachineInstrFromMaps(**I); 1082 } 1083 } 1084 1085 // Insert unconditional "jump Succ" instruction in NMBB if necessary. 1086 NMBB->addSuccessor(Succ); 1087 if (!NMBB->isLayoutSuccessor(Succ)) { 1088 SmallVector<MachineOperand, 4> Cond; 1089 const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo(); 1090 TII->insertBranch(*NMBB, Succ, nullptr, Cond, DL); 1091 1092 if (Indexes) { 1093 for (MachineInstr &MI : NMBB->instrs()) { 1094 // Some instructions may have been moved to NMBB by updateTerminator(), 1095 // so we first remove any instruction that already has an index. 1096 if (Indexes->hasIndex(MI)) 1097 Indexes->removeMachineInstrFromMaps(MI); 1098 Indexes->insertMachineInstrInMaps(MI); 1099 } 1100 } 1101 } 1102 1103 // Fix PHI nodes in Succ so they refer to NMBB instead of this. 1104 Succ->replacePhiUsesWith(this, NMBB); 1105 1106 // Inherit live-ins from the successor 1107 for (const auto &LI : Succ->liveins()) 1108 NMBB->addLiveIn(LI); 1109 1110 // Update LiveVariables. 1111 const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo(); 1112 if (LV) { 1113 // Restore kills of virtual registers that were killed by the terminators. 1114 while (!KilledRegs.empty()) { 1115 Register Reg = KilledRegs.pop_back_val(); 1116 for (instr_iterator I = instr_end(), E = instr_begin(); I != E;) { 1117 if (!(--I)->addRegisterKilled(Reg, TRI, /* AddIfNotFound= */ false)) 1118 continue; 1119 if (Register::isVirtualRegister(Reg)) 1120 LV->getVarInfo(Reg).Kills.push_back(&*I); 1121 LLVM_DEBUG(dbgs() << "Restored terminator kill: " << *I); 1122 break; 1123 } 1124 } 1125 // Update relevant live-through information. 1126 if (LiveInSets != nullptr) 1127 LV->addNewBlock(NMBB, this, Succ, *LiveInSets); 1128 else 1129 LV->addNewBlock(NMBB, this, Succ); 1130 } 1131 1132 if (LIS) { 1133 // After splitting the edge and updating SlotIndexes, live intervals may be 1134 // in one of two situations, depending on whether this block was the last in 1135 // the function. If the original block was the last in the function, all 1136 // live intervals will end prior to the beginning of the new split block. If 1137 // the original block was not at the end of the function, all live intervals 1138 // will extend to the end of the new split block. 1139 1140 bool isLastMBB = 1141 std::next(MachineFunction::iterator(NMBB)) == getParent()->end(); 1142 1143 SlotIndex StartIndex = Indexes->getMBBEndIdx(this); 1144 SlotIndex PrevIndex = StartIndex.getPrevSlot(); 1145 SlotIndex EndIndex = Indexes->getMBBEndIdx(NMBB); 1146 1147 // Find the registers used from NMBB in PHIs in Succ. 1148 SmallSet<Register, 8> PHISrcRegs; 1149 for (MachineBasicBlock::instr_iterator 1150 I = Succ->instr_begin(), E = Succ->instr_end(); 1151 I != E && I->isPHI(); ++I) { 1152 for (unsigned ni = 1, ne = I->getNumOperands(); ni != ne; ni += 2) { 1153 if (I->getOperand(ni+1).getMBB() == NMBB) { 1154 MachineOperand &MO = I->getOperand(ni); 1155 Register Reg = MO.getReg(); 1156 PHISrcRegs.insert(Reg); 1157 if (MO.isUndef()) 1158 continue; 1159 1160 LiveInterval &LI = LIS->getInterval(Reg); 1161 VNInfo *VNI = LI.getVNInfoAt(PrevIndex); 1162 assert(VNI && 1163 "PHI sources should be live out of their predecessors."); 1164 LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI)); 1165 } 1166 } 1167 } 1168 1169 MachineRegisterInfo *MRI = &getParent()->getRegInfo(); 1170 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 1171 Register Reg = Register::index2VirtReg(i); 1172 if (PHISrcRegs.count(Reg) || !LIS->hasInterval(Reg)) 1173 continue; 1174 1175 LiveInterval &LI = LIS->getInterval(Reg); 1176 if (!LI.liveAt(PrevIndex)) 1177 continue; 1178 1179 bool isLiveOut = LI.liveAt(LIS->getMBBStartIdx(Succ)); 1180 if (isLiveOut && isLastMBB) { 1181 VNInfo *VNI = LI.getVNInfoAt(PrevIndex); 1182 assert(VNI && "LiveInterval should have VNInfo where it is live."); 1183 LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI)); 1184 } else if (!isLiveOut && !isLastMBB) { 1185 LI.removeSegment(StartIndex, EndIndex); 1186 } 1187 } 1188 1189 // Update all intervals for registers whose uses may have been modified by 1190 // updateTerminator(). 1191 LIS->repairIntervalsInRange(this, getFirstTerminator(), end(), UsedRegs); 1192 } 1193 1194 if (MachineDominatorTree *MDT = 1195 P.getAnalysisIfAvailable<MachineDominatorTree>()) 1196 MDT->recordSplitCriticalEdge(this, Succ, NMBB); 1197 1198 if (MachineLoopInfo *MLI = P.getAnalysisIfAvailable<MachineLoopInfo>()) 1199 if (MachineLoop *TIL = MLI->getLoopFor(this)) { 1200 // If one or the other blocks were not in a loop, the new block is not 1201 // either, and thus LI doesn't need to be updated. 1202 if (MachineLoop *DestLoop = MLI->getLoopFor(Succ)) { 1203 if (TIL == DestLoop) { 1204 // Both in the same loop, the NMBB joins loop. 1205 DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase()); 1206 } else if (TIL->contains(DestLoop)) { 1207 // Edge from an outer loop to an inner loop. Add to the outer loop. 1208 TIL->addBasicBlockToLoop(NMBB, MLI->getBase()); 1209 } else if (DestLoop->contains(TIL)) { 1210 // Edge from an inner loop to an outer loop. Add to the outer loop. 1211 DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase()); 1212 } else { 1213 // Edge from two loops with no containment relation. Because these 1214 // are natural loops, we know that the destination block must be the 1215 // header of its loop (adding a branch into a loop elsewhere would 1216 // create an irreducible loop). 1217 assert(DestLoop->getHeader() == Succ && 1218 "Should not create irreducible loops!"); 1219 if (MachineLoop *P = DestLoop->getParentLoop()) 1220 P->addBasicBlockToLoop(NMBB, MLI->getBase()); 1221 } 1222 } 1223 } 1224 1225 return NMBB; 1226 } 1227 1228 bool MachineBasicBlock::canSplitCriticalEdge( 1229 const MachineBasicBlock *Succ) const { 1230 // Splitting the critical edge to a landing pad block is non-trivial. Don't do 1231 // it in this generic function. 1232 if (Succ->isEHPad()) 1233 return false; 1234 1235 // Splitting the critical edge to a callbr's indirect block isn't advised. 1236 // Don't do it in this generic function. 1237 if (Succ->isInlineAsmBrIndirectTarget()) 1238 return false; 1239 1240 const MachineFunction *MF = getParent(); 1241 // Performance might be harmed on HW that implements branching using exec mask 1242 // where both sides of the branches are always executed. 1243 if (MF->getTarget().requiresStructuredCFG()) 1244 return false; 1245 1246 // We may need to update this's terminator, but we can't do that if 1247 // analyzeBranch fails. If this uses a jump table, we won't touch it. 1248 const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo(); 1249 MachineBasicBlock *TBB = nullptr, *FBB = nullptr; 1250 SmallVector<MachineOperand, 4> Cond; 1251 // AnalyzeBanch should modify this, since we did not allow modification. 1252 if (TII->analyzeBranch(*const_cast<MachineBasicBlock *>(this), TBB, FBB, Cond, 1253 /*AllowModify*/ false)) 1254 return false; 1255 1256 // Avoid bugpoint weirdness: A block may end with a conditional branch but 1257 // jumps to the same MBB is either case. We have duplicate CFG edges in that 1258 // case that we can't handle. Since this never happens in properly optimized 1259 // code, just skip those edges. 1260 if (TBB && TBB == FBB) { 1261 LLVM_DEBUG(dbgs() << "Won't split critical edge after degenerate " 1262 << printMBBReference(*this) << '\n'); 1263 return false; 1264 } 1265 return true; 1266 } 1267 1268 /// Prepare MI to be removed from its bundle. This fixes bundle flags on MI's 1269 /// neighboring instructions so the bundle won't be broken by removing MI. 1270 static void unbundleSingleMI(MachineInstr *MI) { 1271 // Removing the first instruction in a bundle. 1272 if (MI->isBundledWithSucc() && !MI->isBundledWithPred()) 1273 MI->unbundleFromSucc(); 1274 // Removing the last instruction in a bundle. 1275 if (MI->isBundledWithPred() && !MI->isBundledWithSucc()) 1276 MI->unbundleFromPred(); 1277 // If MI is not bundled, or if it is internal to a bundle, the neighbor flags 1278 // are already fine. 1279 } 1280 1281 MachineBasicBlock::instr_iterator 1282 MachineBasicBlock::erase(MachineBasicBlock::instr_iterator I) { 1283 unbundleSingleMI(&*I); 1284 return Insts.erase(I); 1285 } 1286 1287 MachineInstr *MachineBasicBlock::remove_instr(MachineInstr *MI) { 1288 unbundleSingleMI(MI); 1289 MI->clearFlag(MachineInstr::BundledPred); 1290 MI->clearFlag(MachineInstr::BundledSucc); 1291 return Insts.remove(MI); 1292 } 1293 1294 MachineBasicBlock::instr_iterator 1295 MachineBasicBlock::insert(instr_iterator I, MachineInstr *MI) { 1296 assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() && 1297 "Cannot insert instruction with bundle flags"); 1298 // Set the bundle flags when inserting inside a bundle. 1299 if (I != instr_end() && I->isBundledWithPred()) { 1300 MI->setFlag(MachineInstr::BundledPred); 1301 MI->setFlag(MachineInstr::BundledSucc); 1302 } 1303 return Insts.insert(I, MI); 1304 } 1305 1306 /// This method unlinks 'this' from the containing function, and returns it, but 1307 /// does not delete it. 1308 MachineBasicBlock *MachineBasicBlock::removeFromParent() { 1309 assert(getParent() && "Not embedded in a function!"); 1310 getParent()->remove(this); 1311 return this; 1312 } 1313 1314 /// This method unlinks 'this' from the containing function, and deletes it. 1315 void MachineBasicBlock::eraseFromParent() { 1316 assert(getParent() && "Not embedded in a function!"); 1317 getParent()->erase(this); 1318 } 1319 1320 /// Given a machine basic block that branched to 'Old', change the code and CFG 1321 /// so that it branches to 'New' instead. 1322 void MachineBasicBlock::ReplaceUsesOfBlockWith(MachineBasicBlock *Old, 1323 MachineBasicBlock *New) { 1324 assert(Old != New && "Cannot replace self with self!"); 1325 1326 MachineBasicBlock::instr_iterator I = instr_end(); 1327 while (I != instr_begin()) { 1328 --I; 1329 if (!I->isTerminator()) break; 1330 1331 // Scan the operands of this machine instruction, replacing any uses of Old 1332 // with New. 1333 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 1334 if (I->getOperand(i).isMBB() && 1335 I->getOperand(i).getMBB() == Old) 1336 I->getOperand(i).setMBB(New); 1337 } 1338 1339 // Update the successor information. 1340 replaceSuccessor(Old, New); 1341 } 1342 1343 void MachineBasicBlock::replacePhiUsesWith(MachineBasicBlock *Old, 1344 MachineBasicBlock *New) { 1345 for (MachineInstr &MI : phis()) 1346 for (unsigned i = 2, e = MI.getNumOperands() + 1; i != e; i += 2) { 1347 MachineOperand &MO = MI.getOperand(i); 1348 if (MO.getMBB() == Old) 1349 MO.setMBB(New); 1350 } 1351 } 1352 1353 /// Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE 1354 /// instructions. Return UnknownLoc if there is none. 1355 DebugLoc 1356 MachineBasicBlock::findDebugLoc(instr_iterator MBBI) { 1357 // Skip debug declarations, we don't want a DebugLoc from them. 1358 MBBI = skipDebugInstructionsForward(MBBI, instr_end()); 1359 if (MBBI != instr_end()) 1360 return MBBI->getDebugLoc(); 1361 return {}; 1362 } 1363 1364 /// Find the previous valid DebugLoc preceding MBBI, skipping and DBG_VALUE 1365 /// instructions. Return UnknownLoc if there is none. 1366 DebugLoc MachineBasicBlock::findPrevDebugLoc(instr_iterator MBBI) { 1367 if (MBBI == instr_begin()) return {}; 1368 // Skip debug instructions, we don't want a DebugLoc from them. 1369 MBBI = prev_nodbg(MBBI, instr_begin()); 1370 if (!MBBI->isDebugInstr()) return MBBI->getDebugLoc(); 1371 return {}; 1372 } 1373 1374 /// Find and return the merged DebugLoc of the branch instructions of the block. 1375 /// Return UnknownLoc if there is none. 1376 DebugLoc 1377 MachineBasicBlock::findBranchDebugLoc() { 1378 DebugLoc DL; 1379 auto TI = getFirstTerminator(); 1380 while (TI != end() && !TI->isBranch()) 1381 ++TI; 1382 1383 if (TI != end()) { 1384 DL = TI->getDebugLoc(); 1385 for (++TI ; TI != end() ; ++TI) 1386 if (TI->isBranch()) 1387 DL = DILocation::getMergedLocation(DL, TI->getDebugLoc()); 1388 } 1389 return DL; 1390 } 1391 1392 /// Return probability of the edge from this block to MBB. 1393 BranchProbability 1394 MachineBasicBlock::getSuccProbability(const_succ_iterator Succ) const { 1395 if (Probs.empty()) 1396 return BranchProbability(1, succ_size()); 1397 1398 const auto &Prob = *getProbabilityIterator(Succ); 1399 if (Prob.isUnknown()) { 1400 // For unknown probabilities, collect the sum of all known ones, and evenly 1401 // ditribute the complemental of the sum to each unknown probability. 1402 unsigned KnownProbNum = 0; 1403 auto Sum = BranchProbability::getZero(); 1404 for (auto &P : Probs) { 1405 if (!P.isUnknown()) { 1406 Sum += P; 1407 KnownProbNum++; 1408 } 1409 } 1410 return Sum.getCompl() / (Probs.size() - KnownProbNum); 1411 } else 1412 return Prob; 1413 } 1414 1415 /// Set successor probability of a given iterator. 1416 void MachineBasicBlock::setSuccProbability(succ_iterator I, 1417 BranchProbability Prob) { 1418 assert(!Prob.isUnknown()); 1419 if (Probs.empty()) 1420 return; 1421 *getProbabilityIterator(I) = Prob; 1422 } 1423 1424 /// Return probability iterator corresonding to the I successor iterator 1425 MachineBasicBlock::const_probability_iterator 1426 MachineBasicBlock::getProbabilityIterator( 1427 MachineBasicBlock::const_succ_iterator I) const { 1428 assert(Probs.size() == Successors.size() && "Async probability list!"); 1429 const size_t index = std::distance(Successors.begin(), I); 1430 assert(index < Probs.size() && "Not a current successor!"); 1431 return Probs.begin() + index; 1432 } 1433 1434 /// Return probability iterator corresonding to the I successor iterator. 1435 MachineBasicBlock::probability_iterator 1436 MachineBasicBlock::getProbabilityIterator(MachineBasicBlock::succ_iterator I) { 1437 assert(Probs.size() == Successors.size() && "Async probability list!"); 1438 const size_t index = std::distance(Successors.begin(), I); 1439 assert(index < Probs.size() && "Not a current successor!"); 1440 return Probs.begin() + index; 1441 } 1442 1443 /// Return whether (physical) register "Reg" has been <def>ined and not <kill>ed 1444 /// as of just before "MI". 1445 /// 1446 /// Search is localised to a neighborhood of 1447 /// Neighborhood instructions before (searching for defs or kills) and N 1448 /// instructions after (searching just for defs) MI. 1449 MachineBasicBlock::LivenessQueryResult 1450 MachineBasicBlock::computeRegisterLiveness(const TargetRegisterInfo *TRI, 1451 MCRegister Reg, const_iterator Before, 1452 unsigned Neighborhood) const { 1453 unsigned N = Neighborhood; 1454 1455 // Try searching forwards from Before, looking for reads or defs. 1456 const_iterator I(Before); 1457 for (; I != end() && N > 0; ++I) { 1458 if (I->isDebugInstr()) 1459 continue; 1460 1461 --N; 1462 1463 PhysRegInfo Info = AnalyzePhysRegInBundle(*I, Reg, TRI); 1464 1465 // Register is live when we read it here. 1466 if (Info.Read) 1467 return LQR_Live; 1468 // Register is dead if we can fully overwrite or clobber it here. 1469 if (Info.FullyDefined || Info.Clobbered) 1470 return LQR_Dead; 1471 } 1472 1473 // If we reached the end, it is safe to clobber Reg at the end of a block of 1474 // no successor has it live in. 1475 if (I == end()) { 1476 for (MachineBasicBlock *S : successors()) { 1477 for (const MachineBasicBlock::RegisterMaskPair &LI : S->liveins()) { 1478 if (TRI->regsOverlap(LI.PhysReg, Reg)) 1479 return LQR_Live; 1480 } 1481 } 1482 1483 return LQR_Dead; 1484 } 1485 1486 1487 N = Neighborhood; 1488 1489 // Start by searching backwards from Before, looking for kills, reads or defs. 1490 I = const_iterator(Before); 1491 // If this is the first insn in the block, don't search backwards. 1492 if (I != begin()) { 1493 do { 1494 --I; 1495 1496 if (I->isDebugInstr()) 1497 continue; 1498 1499 --N; 1500 1501 PhysRegInfo Info = AnalyzePhysRegInBundle(*I, Reg, TRI); 1502 1503 // Defs happen after uses so they take precedence if both are present. 1504 1505 // Register is dead after a dead def of the full register. 1506 if (Info.DeadDef) 1507 return LQR_Dead; 1508 // Register is (at least partially) live after a def. 1509 if (Info.Defined) { 1510 if (!Info.PartialDeadDef) 1511 return LQR_Live; 1512 // As soon as we saw a partial definition (dead or not), 1513 // we cannot tell if the value is partial live without 1514 // tracking the lanemasks. We are not going to do this, 1515 // so fall back on the remaining of the analysis. 1516 break; 1517 } 1518 // Register is dead after a full kill or clobber and no def. 1519 if (Info.Killed || Info.Clobbered) 1520 return LQR_Dead; 1521 // Register must be live if we read it. 1522 if (Info.Read) 1523 return LQR_Live; 1524 1525 } while (I != begin() && N > 0); 1526 } 1527 1528 // If all the instructions before this in the block are debug instructions, 1529 // skip over them. 1530 while (I != begin() && std::prev(I)->isDebugInstr()) 1531 --I; 1532 1533 // Did we get to the start of the block? 1534 if (I == begin()) { 1535 // If so, the register's state is definitely defined by the live-in state. 1536 for (const MachineBasicBlock::RegisterMaskPair &LI : liveins()) 1537 if (TRI->regsOverlap(LI.PhysReg, Reg)) 1538 return LQR_Live; 1539 1540 return LQR_Dead; 1541 } 1542 1543 // At this point we have no idea of the liveness of the register. 1544 return LQR_Unknown; 1545 } 1546 1547 const uint32_t * 1548 MachineBasicBlock::getBeginClobberMask(const TargetRegisterInfo *TRI) const { 1549 // EH funclet entry does not preserve any registers. 1550 return isEHFuncletEntry() ? TRI->getNoPreservedMask() : nullptr; 1551 } 1552 1553 const uint32_t * 1554 MachineBasicBlock::getEndClobberMask(const TargetRegisterInfo *TRI) const { 1555 // If we see a return block with successors, this must be a funclet return, 1556 // which does not preserve any registers. If there are no successors, we don't 1557 // care what kind of return it is, putting a mask after it is a no-op. 1558 return isReturnBlock() && !succ_empty() ? TRI->getNoPreservedMask() : nullptr; 1559 } 1560 1561 void MachineBasicBlock::clearLiveIns() { 1562 LiveIns.clear(); 1563 } 1564 1565 MachineBasicBlock::livein_iterator MachineBasicBlock::livein_begin() const { 1566 assert(getParent()->getProperties().hasProperty( 1567 MachineFunctionProperties::Property::TracksLiveness) && 1568 "Liveness information is accurate"); 1569 return LiveIns.begin(); 1570 } 1571 1572 const MBBSectionID MBBSectionID::ColdSectionID(MBBSectionID::SectionType::Cold); 1573 const MBBSectionID 1574 MBBSectionID::ExceptionSectionID(MBBSectionID::SectionType::Exception); 1575