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