1843 lines · cpp
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-exception6//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/STLExtras.h"15#include "llvm/ADT/StringExtras.h"16#include "llvm/CodeGen/LiveIntervals.h"17#include "llvm/CodeGen/LivePhysRegs.h"18#include "llvm/CodeGen/LiveVariables.h"19#include "llvm/CodeGen/MachineDomTreeUpdater.h"20#include "llvm/CodeGen/MachineDominators.h"21#include "llvm/CodeGen/MachineFunction.h"22#include "llvm/CodeGen/MachineInstrBuilder.h"23#include "llvm/CodeGen/MachineJumpTableInfo.h"24#include "llvm/CodeGen/MachineLoopInfo.h"25#include "llvm/CodeGen/MachineRegisterInfo.h"26#include "llvm/CodeGen/SlotIndexes.h"27#include "llvm/CodeGen/TargetInstrInfo.h"28#include "llvm/CodeGen/TargetLowering.h"29#include "llvm/CodeGen/TargetRegisterInfo.h"30#include "llvm/CodeGen/TargetSubtargetInfo.h"31#include "llvm/Config/llvm-config.h"32#include "llvm/IR/BasicBlock.h"33#include "llvm/IR/ModuleSlotTracker.h"34#include "llvm/MC/MCAsmInfo.h"35#include "llvm/MC/MCContext.h"36#include "llvm/Support/Debug.h"37#include "llvm/Support/raw_ostream.h"38#include "llvm/Target/TargetMachine.h"39#include <algorithm>40#include <cmath>41using namespace llvm;42 43#define DEBUG_TYPE "codegen"44 45static cl::opt<bool> PrintSlotIndexes(46 "print-slotindexes",47 cl::desc("When printing machine IR, annotate instructions and blocks with "48 "SlotIndexes when available"),49 cl::init(true), cl::Hidden);50 51MachineBasicBlock::MachineBasicBlock(MachineFunction &MF, const BasicBlock *B)52 : BB(B), Number(-1), xParent(&MF) {53 Insts.Parent = this;54 if (B)55 IrrLoopHeaderWeight = B->getIrrLoopHeaderWeight();56}57 58MachineBasicBlock::~MachineBasicBlock() = default;59 60/// Return the MCSymbol for this basic block.61MCSymbol *MachineBasicBlock::getSymbol() const {62 if (!CachedMCSymbol) {63 const MachineFunction *MF = getParent();64 MCContext &Ctx = MF->getContext();65 66 // We emit a non-temporary symbol -- with a descriptive name -- if it begins67 // a section (with basic block sections). Otherwise we fall back to use temp68 // label.69 if (MF->hasBBSections() && isBeginSection()) {70 SmallString<5> Suffix;71 if (SectionID == MBBSectionID::ColdSectionID) {72 Suffix += ".cold";73 } else if (SectionID == MBBSectionID::ExceptionSectionID) {74 Suffix += ".eh";75 } else {76 // For symbols that represent basic block sections, we add ".__part." to77 // allow tools like symbolizers to know that this represents a part of78 // the original function.79 Suffix = (Suffix + Twine(".__part.") + Twine(SectionID.Number)).str();80 }81 CachedMCSymbol = Ctx.getOrCreateSymbol(MF->getName() + Suffix);82 } else {83 // If the block occurs as label in inline assembly, parsing the assembly84 // needs an actual label name => set AlwaysEmit in these cases.85 CachedMCSymbol = Ctx.createBlockSymbol(86 "BB" + Twine(MF->getFunctionNumber()) + "_" + Twine(getNumber()),87 /*AlwaysEmit=*/hasLabelMustBeEmitted());88 }89 }90 return CachedMCSymbol;91}92 93MCSymbol *MachineBasicBlock::getEHContSymbol() const {94 if (!CachedEHContMCSymbol) {95 const MachineFunction *MF = getParent();96 SmallString<128> SymbolName;97 raw_svector_ostream(SymbolName)98 << "$ehgcr_" << MF->getFunctionNumber() << '_' << getNumber();99 CachedEHContMCSymbol = MF->getContext().getOrCreateSymbol(SymbolName);100 }101 return CachedEHContMCSymbol;102}103 104MCSymbol *MachineBasicBlock::getEndSymbol() const {105 if (!CachedEndMCSymbol) {106 const MachineFunction *MF = getParent();107 MCContext &Ctx = MF->getContext();108 CachedEndMCSymbol = Ctx.createBlockSymbol(109 "BB_END" + Twine(MF->getFunctionNumber()) + "_" + Twine(getNumber()),110 /*AlwaysEmit=*/false);111 }112 return CachedEndMCSymbol;113}114 115raw_ostream &llvm::operator<<(raw_ostream &OS, const MachineBasicBlock &MBB) {116 MBB.print(OS);117 return OS;118}119 120Printable llvm::printMBBReference(const MachineBasicBlock &MBB) {121 return Printable([&MBB](raw_ostream &OS) { return MBB.printAsOperand(OS); });122}123 124/// When an MBB is added to an MF, we need to update the parent pointer of the125/// MBB, the MBB numbering, and any instructions in the MBB to be on the right126/// operand list for registers.127///128/// MBBs start out as #-1. When a MBB is added to a MachineFunction, it129/// gets the next available unique MBB number. If it is removed from a130/// MachineFunction, it goes back to being #-1.131void ilist_callback_traits<MachineBasicBlock>::addNodeToList(132 MachineBasicBlock *N) {133 MachineFunction &MF = *N->getParent();134 N->Number = MF.addToMBBNumbering(N);135 136 // Make sure the instructions have their operands in the reginfo lists.137 MachineRegisterInfo &RegInfo = MF.getRegInfo();138 for (MachineInstr &MI : N->instrs())139 MI.addRegOperandsToUseLists(RegInfo);140}141 142void ilist_callback_traits<MachineBasicBlock>::removeNodeFromList(143 MachineBasicBlock *N) {144 N->getParent()->removeFromMBBNumbering(N->Number);145 N->Number = -1;146}147 148/// When we add an instruction to a basic block list, we update its parent149/// pointer and add its operands from reg use/def lists if appropriate.150void ilist_traits<MachineInstr>::addNodeToList(MachineInstr *N) {151 assert(!N->getParent() && "machine instruction already in a basic block");152 N->setParent(Parent);153 154 // Add the instruction's register operands to their corresponding155 // use/def lists.156 MachineFunction *MF = Parent->getParent();157 N->addRegOperandsToUseLists(MF->getRegInfo());158 MF->handleInsertion(*N);159}160 161/// When we remove an instruction from a basic block list, we update its parent162/// pointer and remove its operands from reg use/def lists if appropriate.163void ilist_traits<MachineInstr>::removeNodeFromList(MachineInstr *N) {164 assert(N->getParent() && "machine instruction not in a basic block");165 166 // Remove from the use/def lists.167 if (MachineFunction *MF = N->getMF()) {168 MF->handleRemoval(*N);169 N->removeRegOperandsFromUseLists(MF->getRegInfo());170 }171 172 N->setParent(nullptr);173}174 175/// When moving a range of instructions from one MBB list to another, we need to176/// update the parent pointers and the use/def lists.177void ilist_traits<MachineInstr>::transferNodesFromList(ilist_traits &FromList,178 instr_iterator First,179 instr_iterator Last) {180 assert(Parent->getParent() == FromList.Parent->getParent() &&181 "cannot transfer MachineInstrs between MachineFunctions");182 183 // If it's within the same BB, there's nothing to do.184 if (this == &FromList)185 return;186 187 assert(Parent != FromList.Parent && "Two lists have the same parent?");188 189 // If splicing between two blocks within the same function, just update the190 // parent pointers.191 for (; First != Last; ++First)192 First->setParent(Parent);193}194 195void ilist_traits<MachineInstr>::deleteNode(MachineInstr *MI) {196 assert(!MI->getParent() && "MI is still in a block!");197 Parent->getParent()->deleteMachineInstr(MI);198}199 200MachineBasicBlock::iterator MachineBasicBlock::getFirstNonPHI() {201 instr_iterator I = instr_begin(), E = instr_end();202 while (I != E && I->isPHI())203 ++I;204 assert((I == E || !I->isInsideBundle()) &&205 "First non-phi MI cannot be inside a bundle!");206 return I;207}208 209MachineBasicBlock::iterator210MachineBasicBlock::SkipPHIsAndLabels(MachineBasicBlock::iterator I) {211 const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();212 213 iterator E = end();214 while (I != E && (I->isPHI() || I->isPosition() ||215 TII->isBasicBlockPrologue(*I)))216 ++I;217 // FIXME: This needs to change if we wish to bundle labels218 // inside the bundle.219 assert((I == E || !I->isInsideBundle()) &&220 "First non-phi / non-label instruction is inside a bundle!");221 return I;222}223 224MachineBasicBlock::iterator225MachineBasicBlock::SkipPHIsLabelsAndDebug(MachineBasicBlock::iterator I,226 Register Reg, bool SkipPseudoOp) {227 const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();228 229 iterator E = end();230 while (I != E && (I->isPHI() || I->isPosition() || I->isDebugInstr() ||231 (SkipPseudoOp && I->isPseudoProbe()) ||232 TII->isBasicBlockPrologue(*I, Reg)))233 ++I;234 // FIXME: This needs to change if we wish to bundle labels / dbg_values235 // inside the bundle.236 assert((I == E || !I->isInsideBundle()) &&237 "First non-phi / non-label / non-debug "238 "instruction is inside a bundle!");239 return I;240}241 242MachineBasicBlock::iterator MachineBasicBlock::getFirstTerminator() {243 iterator B = begin(), E = end(), I = E;244 while (I != B && ((--I)->isTerminator() || I->isDebugInstr()))245 ; /*noop */246 while (I != E && !I->isTerminator())247 ++I;248 return I;249}250 251MachineBasicBlock::instr_iterator MachineBasicBlock::getFirstInstrTerminator() {252 instr_iterator B = instr_begin(), E = instr_end(), I = E;253 while (I != B && ((--I)->isTerminator() || I->isDebugInstr()))254 ; /*noop */255 while (I != E && !I->isTerminator())256 ++I;257 return I;258}259 260MachineBasicBlock::iterator MachineBasicBlock::getFirstTerminatorForward() {261 return find_if(instrs(), [](auto &II) { return II.isTerminator(); });262}263 264MachineBasicBlock::iterator265MachineBasicBlock::getFirstNonDebugInstr(bool SkipPseudoOp) {266 // Skip over begin-of-block dbg_value instructions.267 return skipDebugInstructionsForward(begin(), end(), SkipPseudoOp);268}269 270MachineBasicBlock::iterator271MachineBasicBlock::getLastNonDebugInstr(bool SkipPseudoOp) {272 // Skip over end-of-block dbg_value instructions.273 instr_iterator B = instr_begin(), I = instr_end();274 while (I != B) {275 --I;276 // Return instruction that starts a bundle.277 if (I->isDebugInstr() || I->isInsideBundle())278 continue;279 if (SkipPseudoOp && I->isPseudoProbe())280 continue;281 return I;282 }283 // The block is all debug values.284 return end();285}286 287bool MachineBasicBlock::hasEHPadSuccessor() const {288 for (const MachineBasicBlock *Succ : successors())289 if (Succ->isEHPad())290 return true;291 return false;292}293 294bool MachineBasicBlock::isEntryBlock() const {295 return getParent()->begin() == getIterator();296}297 298#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)299LLVM_DUMP_METHOD void MachineBasicBlock::dump() const {300 print(dbgs());301}302#endif303 304bool MachineBasicBlock::mayHaveInlineAsmBr() const {305 for (const MachineBasicBlock *Succ : successors()) {306 if (Succ->isInlineAsmBrIndirectTarget())307 return true;308 }309 return false;310}311 312bool MachineBasicBlock::isLegalToHoistInto() const {313 if (isReturnBlock() || hasEHPadSuccessor() || mayHaveInlineAsmBr())314 return false;315 return true;316}317 318bool MachineBasicBlock::hasName() const {319 if (const BasicBlock *LBB = getBasicBlock())320 return LBB->hasName();321 return false;322}323 324StringRef MachineBasicBlock::getName() const {325 if (const BasicBlock *LBB = getBasicBlock())326 return LBB->getName();327 else328 return StringRef("", 0);329}330 331/// Return a hopefully unique identifier for this block.332std::string MachineBasicBlock::getFullName() const {333 std::string Name;334 if (getParent())335 Name = (getParent()->getName() + ":").str();336 if (getBasicBlock())337 Name += getBasicBlock()->getName();338 else339 Name += ("BB" + Twine(getNumber())).str();340 return Name;341}342 343void MachineBasicBlock::print(raw_ostream &OS, const SlotIndexes *Indexes,344 bool IsStandalone) const {345 const MachineFunction *MF = getParent();346 if (!MF) {347 OS << "Can't print out MachineBasicBlock because parent MachineFunction"348 << " is null\n";349 return;350 }351 const Function &F = MF->getFunction();352 const Module *M = F.getParent();353 ModuleSlotTracker MST(M);354 MST.incorporateFunction(F);355 print(OS, MST, Indexes, IsStandalone);356}357 358void MachineBasicBlock::print(raw_ostream &OS, ModuleSlotTracker &MST,359 const SlotIndexes *Indexes,360 bool IsStandalone) const {361 const MachineFunction *MF = getParent();362 if (!MF) {363 OS << "Can't print out MachineBasicBlock because parent MachineFunction"364 << " is null\n";365 return;366 }367 368 if (Indexes && PrintSlotIndexes)369 OS << Indexes->getMBBStartIdx(this) << '\t';370 371 printName(OS, PrintNameIr | PrintNameAttributes, &MST);372 OS << ":\n";373 374 const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();375 const MachineRegisterInfo &MRI = MF->getRegInfo();376 const TargetInstrInfo &TII = *getParent()->getSubtarget().getInstrInfo();377 bool HasLineAttributes = false;378 379 // Print the preds of this block according to the CFG.380 if (!pred_empty() && IsStandalone) {381 if (Indexes) OS << '\t';382 // Don't indent(2), align with previous line attributes.383 OS << "; predecessors: ";384 ListSeparator LS;385 for (auto *Pred : predecessors())386 OS << LS << printMBBReference(*Pred);387 OS << '\n';388 HasLineAttributes = true;389 }390 391 if (!succ_empty()) {392 if (Indexes) OS << '\t';393 // Print the successors394 OS.indent(2) << "successors: ";395 ListSeparator LS;396 for (auto I = succ_begin(), E = succ_end(); I != E; ++I) {397 OS << LS << printMBBReference(**I);398 if (!Probs.empty())399 OS << '('400 << format("0x%08" PRIx32, getSuccProbability(I).getNumerator())401 << ')';402 }403 if (!Probs.empty() && IsStandalone) {404 // Print human readable probabilities as comments.405 OS << "; ";406 ListSeparator LS;407 for (auto I = succ_begin(), E = succ_end(); I != E; ++I) {408 const BranchProbability &BP = getSuccProbability(I);409 OS << LS << printMBBReference(**I) << '('410 << format("%.2f%%",411 rint(((double)BP.getNumerator() / BP.getDenominator()) *412 100.0 * 100.0) /413 100.0)414 << ')';415 }416 }417 418 OS << '\n';419 HasLineAttributes = true;420 }421 422 if (!livein_empty() && MRI.tracksLiveness()) {423 if (Indexes) OS << '\t';424 OS.indent(2) << "liveins: ";425 426 ListSeparator LS;427 for (const auto &LI : liveins()) {428 OS << LS << printReg(LI.PhysReg, TRI);429 if (!LI.LaneMask.all())430 OS << ":0x" << PrintLaneMask(LI.LaneMask);431 }432 HasLineAttributes = true;433 }434 435 if (HasLineAttributes)436 OS << '\n';437 438 bool IsInBundle = false;439 for (const MachineInstr &MI : instrs()) {440 if (Indexes && PrintSlotIndexes) {441 if (Indexes->hasIndex(MI))442 OS << Indexes->getInstructionIndex(MI);443 OS << '\t';444 }445 446 if (IsInBundle && !MI.isInsideBundle()) {447 OS.indent(2) << "}\n";448 IsInBundle = false;449 }450 451 OS.indent(IsInBundle ? 4 : 2);452 MI.print(OS, MST, IsStandalone, /*SkipOpers=*/false, /*SkipDebugLoc=*/false,453 /*AddNewLine=*/false, &TII);454 455 if (!IsInBundle && MI.getFlag(MachineInstr::BundledSucc)) {456 OS << " {";457 IsInBundle = true;458 }459 OS << '\n';460 }461 462 if (IsInBundle)463 OS.indent(2) << "}\n";464 465 if (IrrLoopHeaderWeight && IsStandalone) {466 if (Indexes) OS << '\t';467 OS.indent(2) << "; Irreducible loop header weight: " << *IrrLoopHeaderWeight468 << '\n';469 }470}471 472/// Print the basic block's name as:473///474/// bb.{number}[.{ir-name}] [(attributes...)]475///476/// The {ir-name} is only printed when the \ref PrintNameIr flag is passed477/// (which is the default). If the IR block has no name, it is identified478/// numerically using the attribute syntax as "(%ir-block.{ir-slot})".479///480/// When the \ref PrintNameAttributes flag is passed, additional attributes481/// of the block are printed when set.482///483/// \param printNameFlags Combination of \ref PrintNameFlag flags indicating484/// the parts to print.485/// \param moduleSlotTracker Optional ModuleSlotTracker. This method will486/// incorporate its own tracker when necessary to487/// determine the block's IR name.488void MachineBasicBlock::printName(raw_ostream &os, unsigned printNameFlags,489 ModuleSlotTracker *moduleSlotTracker) const {490 os << "bb." << getNumber();491 bool hasAttributes = false;492 493 auto PrintBBRef = [&](const BasicBlock *bb) {494 os << "%ir-block.";495 if (bb->hasName()) {496 os << bb->getName();497 } else {498 int slot = -1;499 500 if (moduleSlotTracker) {501 slot = moduleSlotTracker->getLocalSlot(bb);502 } else if (bb->getParent()) {503 ModuleSlotTracker tmpTracker(bb->getModule(), false);504 tmpTracker.incorporateFunction(*bb->getParent());505 slot = tmpTracker.getLocalSlot(bb);506 }507 508 if (slot == -1)509 os << "<ir-block badref>";510 else511 os << slot;512 }513 };514 515 if (printNameFlags & PrintNameIr) {516 if (const auto *bb = getBasicBlock()) {517 if (bb->hasName()) {518 os << '.' << bb->getName();519 } else {520 hasAttributes = true;521 os << " (";522 PrintBBRef(bb);523 }524 }525 }526 527 if (printNameFlags & PrintNameAttributes) {528 if (isMachineBlockAddressTaken()) {529 os << (hasAttributes ? ", " : " (");530 os << "machine-block-address-taken";531 hasAttributes = true;532 }533 if (isIRBlockAddressTaken()) {534 os << (hasAttributes ? ", " : " (");535 os << "ir-block-address-taken ";536 PrintBBRef(getAddressTakenIRBlock());537 hasAttributes = true;538 }539 if (isEHPad()) {540 os << (hasAttributes ? ", " : " (");541 os << "landing-pad";542 hasAttributes = true;543 }544 if (isInlineAsmBrIndirectTarget()) {545 os << (hasAttributes ? ", " : " (");546 os << "inlineasm-br-indirect-target";547 hasAttributes = true;548 }549 if (isEHFuncletEntry()) {550 os << (hasAttributes ? ", " : " (");551 os << "ehfunclet-entry";552 hasAttributes = true;553 }554 if (getAlignment() != Align(1)) {555 os << (hasAttributes ? ", " : " (");556 os << "align " << getAlignment().value();557 hasAttributes = true;558 }559 if (getSectionID() != MBBSectionID(0)) {560 os << (hasAttributes ? ", " : " (");561 os << "bbsections ";562 switch (getSectionID().Type) {563 case MBBSectionID::SectionType::Exception:564 os << "Exception";565 break;566 case MBBSectionID::SectionType::Cold:567 os << "Cold";568 break;569 default:570 os << getSectionID().Number;571 }572 hasAttributes = true;573 }574 if (getBBID().has_value()) {575 os << (hasAttributes ? ", " : " (");576 os << "bb_id " << getBBID()->BaseID;577 if (getBBID()->CloneID != 0)578 os << " " << getBBID()->CloneID;579 hasAttributes = true;580 }581 if (CallFrameSize != 0) {582 os << (hasAttributes ? ", " : " (");583 os << "call-frame-size " << CallFrameSize;584 hasAttributes = true;585 }586 }587 588 if (hasAttributes)589 os << ')';590}591 592void MachineBasicBlock::printAsOperand(raw_ostream &OS,593 bool /*PrintType*/) const {594 OS << '%';595 printName(OS, 0);596}597 598void MachineBasicBlock::removeLiveIn(MCRegister Reg, LaneBitmask LaneMask) {599 LiveInVector::iterator I = find_if(600 LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });601 if (I == LiveIns.end())602 return;603 604 I->LaneMask &= ~LaneMask;605 if (I->LaneMask.none())606 LiveIns.erase(I);607}608 609void MachineBasicBlock::removeLiveInOverlappedWith(MCRegister Reg) {610 const MachineFunction *MF = getParent();611 const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();612 // Remove Reg and its subregs from live in set.613 for (MCPhysReg S : TRI->subregs_inclusive(Reg))614 removeLiveIn(S);615 616 // Remove live-in bitmask in super registers as well.617 for (MCPhysReg Super : TRI->superregs(Reg)) {618 for (MCSubRegIndexIterator SRI(Super, TRI); SRI.isValid(); ++SRI) {619 if (Reg == SRI.getSubReg()) {620 unsigned SubRegIndex = SRI.getSubRegIndex();621 LaneBitmask SubRegLaneMask = TRI->getSubRegIndexLaneMask(SubRegIndex);622 removeLiveIn(Super, SubRegLaneMask);623 break;624 }625 }626 }627}628 629MachineBasicBlock::livein_iterator630MachineBasicBlock::removeLiveIn(MachineBasicBlock::livein_iterator I) {631 // Get non-const version of iterator.632 LiveInVector::iterator LI = LiveIns.begin() + (I - LiveIns.begin());633 return LiveIns.erase(LI);634}635 636bool MachineBasicBlock::isLiveIn(MCRegister Reg, LaneBitmask LaneMask) const {637 livein_iterator I = find_if(638 LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });639 return I != livein_end() && (I->LaneMask & LaneMask).any();640}641 642void MachineBasicBlock::sortUniqueLiveIns() {643 llvm::sort(LiveIns,644 [](const RegisterMaskPair &LI0, const RegisterMaskPair &LI1) {645 return LI0.PhysReg < LI1.PhysReg;646 });647 // Liveins are sorted by physreg now we can merge their lanemasks.648 LiveInVector::const_iterator I = LiveIns.begin();649 LiveInVector::const_iterator J;650 LiveInVector::iterator Out = LiveIns.begin();651 for (; I != LiveIns.end(); ++Out, I = J) {652 MCRegister PhysReg = I->PhysReg;653 LaneBitmask LaneMask = I->LaneMask;654 for (J = std::next(I); J != LiveIns.end() && J->PhysReg == PhysReg; ++J)655 LaneMask |= J->LaneMask;656 Out->PhysReg = PhysReg;657 Out->LaneMask = LaneMask;658 }659 LiveIns.erase(Out, LiveIns.end());660}661 662Register663MachineBasicBlock::addLiveIn(MCRegister PhysReg, const TargetRegisterClass *RC) {664 assert(getParent() && "MBB must be inserted in function");665 assert(PhysReg.isPhysical() && "Expected physreg");666 assert(RC && "Register class is required");667 assert((isEHPad() || this == &getParent()->front()) &&668 "Only the entry block and landing pads can have physreg live ins");669 670 bool LiveIn = isLiveIn(PhysReg);671 iterator I = SkipPHIsAndLabels(begin()), E = end();672 MachineRegisterInfo &MRI = getParent()->getRegInfo();673 const TargetInstrInfo &TII = *getParent()->getSubtarget().getInstrInfo();674 675 // Look for an existing copy.676 if (LiveIn)677 for (;I != E && I->isCopy(); ++I)678 if (I->getOperand(1).getReg() == PhysReg) {679 Register VirtReg = I->getOperand(0).getReg();680 if (!MRI.constrainRegClass(VirtReg, RC))681 llvm_unreachable("Incompatible live-in register class.");682 return VirtReg;683 }684 685 // No luck, create a virtual register.686 Register VirtReg = MRI.createVirtualRegister(RC);687 BuildMI(*this, I, DebugLoc(), TII.get(TargetOpcode::COPY), VirtReg)688 .addReg(PhysReg, RegState::Kill);689 if (!LiveIn)690 addLiveIn(PhysReg);691 return VirtReg;692}693 694void MachineBasicBlock::moveBefore(MachineBasicBlock *NewAfter) {695 getParent()->splice(NewAfter->getIterator(), getIterator());696}697 698void MachineBasicBlock::moveAfter(MachineBasicBlock *NewBefore) {699 getParent()->splice(++NewBefore->getIterator(), getIterator());700}701 702static int findJumpTableIndex(const MachineBasicBlock &MBB) {703 MachineBasicBlock::const_iterator TerminatorI = MBB.getFirstTerminator();704 if (TerminatorI == MBB.end())705 return -1;706 const MachineInstr &Terminator = *TerminatorI;707 const TargetInstrInfo *TII = MBB.getParent()->getSubtarget().getInstrInfo();708 return TII->getJumpTableIndex(Terminator);709}710 711void MachineBasicBlock::updateTerminator(712 MachineBasicBlock *PreviousLayoutSuccessor) {713 LLVM_DEBUG(dbgs() << "Updating terminators on " << printMBBReference(*this)714 << "\n");715 716 const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();717 // A block with no successors has no concerns with fall-through edges.718 if (this->succ_empty())719 return;720 721 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;722 SmallVector<MachineOperand, 4> Cond;723 DebugLoc DL = findBranchDebugLoc();724 bool B = TII->analyzeBranch(*this, TBB, FBB, Cond);725 (void) B;726 assert(!B && "UpdateTerminators requires analyzable predecessors!");727 if (Cond.empty()) {728 if (TBB) {729 // The block has an unconditional branch. If its successor is now its730 // layout successor, delete the branch.731 if (isLayoutSuccessor(TBB))732 TII->removeBranch(*this);733 } else {734 // The block has an unconditional fallthrough, or the end of the block is735 // unreachable.736 737 // Unfortunately, whether the end of the block is unreachable is not738 // immediately obvious; we must fall back to checking the successor list,739 // and assuming that if the passed in block is in the succesor list and740 // not an EHPad, it must be the intended target.741 if (!PreviousLayoutSuccessor || !isSuccessor(PreviousLayoutSuccessor) ||742 PreviousLayoutSuccessor->isEHPad())743 return;744 745 // If the unconditional successor block is not the current layout746 // successor, insert a branch to jump to it.747 if (!isLayoutSuccessor(PreviousLayoutSuccessor))748 TII->insertBranch(*this, PreviousLayoutSuccessor, nullptr, Cond, DL);749 }750 return;751 }752 753 if (FBB) {754 // The block has a non-fallthrough conditional branch. If one of its755 // successors is its layout successor, rewrite it to a fallthrough756 // conditional branch.757 if (isLayoutSuccessor(TBB)) {758 if (TII->reverseBranchCondition(Cond))759 return;760 TII->removeBranch(*this);761 TII->insertBranch(*this, FBB, nullptr, Cond, DL);762 } else if (isLayoutSuccessor(FBB)) {763 TII->removeBranch(*this);764 TII->insertBranch(*this, TBB, nullptr, Cond, DL);765 }766 return;767 }768 769 // We now know we're going to fallthrough to PreviousLayoutSuccessor.770 assert(PreviousLayoutSuccessor);771 assert(!PreviousLayoutSuccessor->isEHPad());772 assert(isSuccessor(PreviousLayoutSuccessor));773 774 if (PreviousLayoutSuccessor == TBB) {775 // We had a fallthrough to the same basic block as the conditional jump776 // targets. Remove the conditional jump, leaving an unconditional777 // fallthrough or an unconditional jump.778 TII->removeBranch(*this);779 if (!isLayoutSuccessor(TBB)) {780 Cond.clear();781 TII->insertBranch(*this, TBB, nullptr, Cond, DL);782 }783 return;784 }785 786 // The block has a fallthrough conditional branch.787 if (isLayoutSuccessor(TBB)) {788 if (TII->reverseBranchCondition(Cond)) {789 // We can't reverse the condition, add an unconditional branch.790 Cond.clear();791 TII->insertBranch(*this, PreviousLayoutSuccessor, nullptr, Cond, DL);792 return;793 }794 TII->removeBranch(*this);795 TII->insertBranch(*this, PreviousLayoutSuccessor, nullptr, Cond, DL);796 } else if (!isLayoutSuccessor(PreviousLayoutSuccessor)) {797 TII->removeBranch(*this);798 TII->insertBranch(*this, TBB, PreviousLayoutSuccessor, Cond, DL);799 }800}801 802void MachineBasicBlock::validateSuccProbs() const {803#ifndef NDEBUG804 int64_t Sum = 0;805 for (auto Prob : Probs)806 Sum += Prob.getNumerator();807 // Due to precision issue, we assume that the sum of probabilities is one if808 // the difference between the sum of their numerators and the denominator is809 // no greater than the number of successors.810 assert((uint64_t)std::abs(Sum - BranchProbability::getDenominator()) <=811 Probs.size() &&812 "The sum of successors's probabilities exceeds one.");813#endif // NDEBUG814}815 816void MachineBasicBlock::addSuccessor(MachineBasicBlock *Succ,817 BranchProbability Prob) {818 // Probability list is either empty (if successor list isn't empty, this means819 // disabled optimization) or has the same size as successor list.820 if (!(Probs.empty() && !Successors.empty()))821 Probs.push_back(Prob);822 Successors.push_back(Succ);823 Succ->addPredecessor(this);824}825 826void MachineBasicBlock::addSuccessorWithoutProb(MachineBasicBlock *Succ) {827 // We need to make sure probability list is either empty or has the same size828 // of successor list. When this function is called, we can safely delete all829 // probability in the list.830 Probs.clear();831 Successors.push_back(Succ);832 Succ->addPredecessor(this);833}834 835void MachineBasicBlock::splitSuccessor(MachineBasicBlock *Old,836 MachineBasicBlock *New,837 bool NormalizeSuccProbs) {838 succ_iterator OldI = llvm::find(successors(), Old);839 assert(OldI != succ_end() && "Old is not a successor of this block!");840 assert(!llvm::is_contained(successors(), New) &&841 "New is already a successor of this block!");842 843 // Add a new successor with equal probability as the original one. Note844 // that we directly copy the probability using the iterator rather than845 // getting a potentially synthetic probability computed when unknown. This846 // preserves the probabilities as-is and then we can renormalize them and847 // query them effectively afterward.848 addSuccessor(New, Probs.empty() ? BranchProbability::getUnknown()849 : *getProbabilityIterator(OldI));850 if (NormalizeSuccProbs)851 normalizeSuccProbs();852}853 854void MachineBasicBlock::removeSuccessor(MachineBasicBlock *Succ,855 bool NormalizeSuccProbs) {856 succ_iterator I = find(Successors, Succ);857 removeSuccessor(I, NormalizeSuccProbs);858}859 860MachineBasicBlock::succ_iterator861MachineBasicBlock::removeSuccessor(succ_iterator I, bool NormalizeSuccProbs) {862 assert(I != Successors.end() && "Not a current successor!");863 864 // If probability list is empty it means we don't use it (disabled865 // optimization).866 if (!Probs.empty()) {867 probability_iterator WI = getProbabilityIterator(I);868 Probs.erase(WI);869 if (NormalizeSuccProbs)870 normalizeSuccProbs();871 }872 873 (*I)->removePredecessor(this);874 return Successors.erase(I);875}876 877void MachineBasicBlock::replaceSuccessor(MachineBasicBlock *Old,878 MachineBasicBlock *New) {879 if (Old == New)880 return;881 882 succ_iterator E = succ_end();883 succ_iterator NewI = E;884 succ_iterator OldI = E;885 for (succ_iterator I = succ_begin(); I != E; ++I) {886 if (*I == Old) {887 OldI = I;888 if (NewI != E)889 break;890 }891 if (*I == New) {892 NewI = I;893 if (OldI != E)894 break;895 }896 }897 assert(OldI != E && "Old is not a successor of this block");898 899 // If New isn't already a successor, let it take Old's place.900 if (NewI == E) {901 Old->removePredecessor(this);902 New->addPredecessor(this);903 *OldI = New;904 return;905 }906 907 // New is already a successor.908 // Update its probability instead of adding a duplicate edge.909 if (!Probs.empty()) {910 auto ProbIter = getProbabilityIterator(NewI);911 if (!ProbIter->isUnknown())912 *ProbIter += *getProbabilityIterator(OldI);913 }914 removeSuccessor(OldI);915}916 917void MachineBasicBlock::copySuccessor(const MachineBasicBlock *Orig,918 succ_iterator I) {919 if (!Orig->Probs.empty())920 addSuccessor(*I, Orig->getSuccProbability(I));921 else922 addSuccessorWithoutProb(*I);923}924 925void MachineBasicBlock::addPredecessor(MachineBasicBlock *Pred) {926 Predecessors.push_back(Pred);927}928 929void MachineBasicBlock::removePredecessor(MachineBasicBlock *Pred) {930 pred_iterator I = find(Predecessors, Pred);931 assert(I != Predecessors.end() && "Pred is not a predecessor of this block!");932 Predecessors.erase(I);933}934 935void MachineBasicBlock::transferSuccessors(MachineBasicBlock *FromMBB) {936 if (this == FromMBB)937 return;938 939 while (!FromMBB->succ_empty()) {940 MachineBasicBlock *Succ = *FromMBB->succ_begin();941 942 // If probability list is empty it means we don't use it (disabled943 // optimization).944 if (!FromMBB->Probs.empty()) {945 auto Prob = *FromMBB->Probs.begin();946 addSuccessor(Succ, Prob);947 } else948 addSuccessorWithoutProb(Succ);949 950 FromMBB->removeSuccessor(Succ);951 }952}953 954void955MachineBasicBlock::transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB) {956 if (this == FromMBB)957 return;958 959 while (!FromMBB->succ_empty()) {960 MachineBasicBlock *Succ = *FromMBB->succ_begin();961 if (!FromMBB->Probs.empty()) {962 auto Prob = *FromMBB->Probs.begin();963 addSuccessor(Succ, Prob);964 } else965 addSuccessorWithoutProb(Succ);966 FromMBB->removeSuccessor(Succ);967 968 // Fix up any PHI nodes in the successor.969 Succ->replacePhiUsesWith(FromMBB, this);970 }971 normalizeSuccProbs();972}973 974bool MachineBasicBlock::isPredecessor(const MachineBasicBlock *MBB) const {975 return is_contained(predecessors(), MBB);976}977 978bool MachineBasicBlock::isSuccessor(const MachineBasicBlock *MBB) const {979 return is_contained(successors(), MBB);980}981 982bool MachineBasicBlock::isLayoutSuccessor(const MachineBasicBlock *MBB) const {983 MachineFunction::const_iterator I(this);984 return std::next(I) == MachineFunction::const_iterator(MBB);985}986 987const MachineBasicBlock *MachineBasicBlock::getSingleSuccessor() const {988 return Successors.size() == 1 ? Successors[0] : nullptr;989}990 991const MachineBasicBlock *MachineBasicBlock::getSinglePredecessor() const {992 return Predecessors.size() == 1 ? Predecessors[0] : nullptr;993}994 995MachineBasicBlock *MachineBasicBlock::getFallThrough(bool JumpToFallThrough) {996 MachineFunction::iterator Fallthrough = getIterator();997 ++Fallthrough;998 // If FallthroughBlock is off the end of the function, it can't fall through.999 if (Fallthrough == getParent()->end())1000 return nullptr;1001 1002 // If FallthroughBlock isn't a successor, no fallthrough is possible.1003 if (!isSuccessor(&*Fallthrough))1004 return nullptr;1005 1006 // Analyze the branches, if any, at the end of the block.1007 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;1008 SmallVector<MachineOperand, 4> Cond;1009 const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();1010 if (TII->analyzeBranch(*this, TBB, FBB, Cond)) {1011 // If we couldn't analyze the branch, examine the last instruction.1012 // If the block doesn't end in a known control barrier, assume fallthrough1013 // is possible. The isPredicated check is needed because this code can be1014 // called during IfConversion, where an instruction which is normally a1015 // Barrier is predicated and thus no longer an actual control barrier.1016 return (empty() || !back().isBarrier() || TII->isPredicated(back()))1017 ? &*Fallthrough1018 : nullptr;1019 }1020 1021 // If there is no branch, control always falls through.1022 if (!TBB) return &*Fallthrough;1023 1024 // If there is some explicit branch to the fallthrough block, it can obviously1025 // reach, even though the branch should get folded to fall through implicitly.1026 if (JumpToFallThrough && (MachineFunction::iterator(TBB) == Fallthrough ||1027 MachineFunction::iterator(FBB) == Fallthrough))1028 return &*Fallthrough;1029 1030 // If it's an unconditional branch to some block not the fall through, it1031 // doesn't fall through.1032 if (Cond.empty()) return nullptr;1033 1034 // Otherwise, if it is conditional and has no explicit false block, it falls1035 // through.1036 return (FBB == nullptr) ? &*Fallthrough : nullptr;1037}1038 1039bool MachineBasicBlock::canFallThrough() {1040 return getFallThrough() != nullptr;1041}1042 1043MachineBasicBlock *MachineBasicBlock::splitAt(MachineInstr &MI,1044 bool UpdateLiveIns,1045 LiveIntervals *LIS) {1046 MachineBasicBlock::iterator SplitPoint(&MI);1047 ++SplitPoint;1048 1049 if (SplitPoint == end()) {1050 // Don't bother with a new block.1051 return this;1052 }1053 1054 MachineFunction *MF = getParent();1055 1056 LivePhysRegs LiveRegs;1057 if (UpdateLiveIns) {1058 // Make sure we add any physregs we define in the block as liveins to the1059 // new block.1060 MachineBasicBlock::iterator Prev(&MI);1061 LiveRegs.init(*MF->getSubtarget().getRegisterInfo());1062 LiveRegs.addLiveOuts(*this);1063 for (auto I = rbegin(), E = Prev.getReverse(); I != E; ++I)1064 LiveRegs.stepBackward(*I);1065 }1066 1067 MachineBasicBlock *SplitBB = MF->CreateMachineBasicBlock(getBasicBlock());1068 1069 MF->insert(++MachineFunction::iterator(this), SplitBB);1070 SplitBB->splice(SplitBB->begin(), this, SplitPoint, end());1071 1072 SplitBB->transferSuccessorsAndUpdatePHIs(this);1073 addSuccessor(SplitBB);1074 1075 if (UpdateLiveIns)1076 addLiveIns(*SplitBB, LiveRegs);1077 1078 if (LIS)1079 LIS->insertMBBInMaps(SplitBB);1080 1081 return SplitBB;1082}1083 1084// Returns `true` if there are possibly other users of the jump table at1085// `JumpTableIndex` except for the ones in `IgnoreMBB`.1086static bool jumpTableHasOtherUses(const MachineFunction &MF,1087 const MachineBasicBlock &IgnoreMBB,1088 int JumpTableIndex) {1089 assert(JumpTableIndex >= 0 && "need valid index");1090 const MachineJumpTableInfo &MJTI = *MF.getJumpTableInfo();1091 const MachineJumpTableEntry &MJTE = MJTI.getJumpTables()[JumpTableIndex];1092 // Take any basic block from the table; every user of the jump table must1093 // show up in the predecessor list.1094 const MachineBasicBlock *MBB = nullptr;1095 for (MachineBasicBlock *B : MJTE.MBBs) {1096 if (B != nullptr) {1097 MBB = B;1098 break;1099 }1100 }1101 if (MBB == nullptr)1102 return true; // can't rule out other users if there isn't any block.1103 const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();1104 SmallVector<MachineOperand, 4> Cond;1105 for (MachineBasicBlock *Pred : MBB->predecessors()) {1106 if (Pred == &IgnoreMBB)1107 continue;1108 MachineBasicBlock *DummyT = nullptr;1109 MachineBasicBlock *DummyF = nullptr;1110 Cond.clear();1111 if (!TII.analyzeBranch(*Pred, DummyT, DummyF, Cond,1112 /*AllowModify=*/false)) {1113 // analyzable direct jump1114 continue;1115 }1116 int PredJTI = findJumpTableIndex(*Pred);1117 if (PredJTI >= 0) {1118 if (PredJTI == JumpTableIndex)1119 return true;1120 continue;1121 }1122 // Be conservative for unanalyzable jumps.1123 return true;1124 }1125 return false;1126}1127 1128class SlotIndexUpdateDelegate : public MachineFunction::Delegate {1129private:1130 MachineFunction &MF;1131 SlotIndexes *Indexes;1132 SmallSetVector<MachineInstr *, 2> Insertions;1133 1134public:1135 SlotIndexUpdateDelegate(MachineFunction &MF, SlotIndexes *Indexes)1136 : MF(MF), Indexes(Indexes) {1137 MF.setDelegate(this);1138 }1139 1140 ~SlotIndexUpdateDelegate() override {1141 MF.resetDelegate(this);1142 for (auto MI : Insertions)1143 Indexes->insertMachineInstrInMaps(*MI);1144 }1145 1146 void MF_HandleInsertion(MachineInstr &MI) override {1147 // This is called before MI is inserted into block so defer index update.1148 if (Indexes)1149 Insertions.insert(&MI);1150 }1151 1152 void MF_HandleRemoval(MachineInstr &MI) override {1153 if (Indexes && !Insertions.remove(&MI))1154 Indexes->removeMachineInstrFromMaps(MI);1155 }1156};1157 1158MachineBasicBlock *MachineBasicBlock::SplitCriticalEdge(1159 MachineBasicBlock *Succ, Pass *P, MachineFunctionAnalysisManager *MFAM,1160 std::vector<SparseBitVector<>> *LiveInSets, MachineDomTreeUpdater *MDTU) {1161#define GET_RESULT(RESULT, GETTER, INFIX) \1162 [MF, P, MFAM]() { \1163 if (P) { \1164 auto *Wrapper = P->getAnalysisIfAvailable<RESULT##INFIX##WrapperPass>(); \1165 return Wrapper ? &Wrapper->GETTER() : nullptr; \1166 } \1167 return MFAM->getCachedResult<RESULT##Analysis>(*MF); \1168 }()1169 1170 assert((P || MFAM) && "Need a way to get analysis results!");1171 MachineFunction *MF = getParent();1172 LiveIntervals *LIS = GET_RESULT(LiveIntervals, getLIS, );1173 SlotIndexes *Indexes = GET_RESULT(SlotIndexes, getSI, );1174 LiveVariables *LV = GET_RESULT(LiveVariables, getLV, );1175 MachineLoopInfo *MLI = GET_RESULT(MachineLoop, getLI, Info);1176 return SplitCriticalEdge(Succ, {LIS, Indexes, LV, MLI}, LiveInSets, MDTU);1177#undef GET_RESULT1178}1179 1180MachineBasicBlock *MachineBasicBlock::SplitCriticalEdge(1181 MachineBasicBlock *Succ, const SplitCriticalEdgeAnalyses &Analyses,1182 std::vector<SparseBitVector<>> *LiveInSets, MachineDomTreeUpdater *MDTU) {1183 if (!canSplitCriticalEdge(Succ, Analyses.MLI))1184 return nullptr;1185 1186 MachineFunction *MF = getParent();1187 MachineBasicBlock *PrevFallthrough = getNextNode();1188 1189 MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock();1190 NMBB->setCallFrameSize(Succ->getCallFrameSize());1191 1192 // Is there an indirect jump with jump table?1193 bool ChangedIndirectJump = false;1194 int JTI = findJumpTableIndex(*this);1195 if (JTI >= 0) {1196 MachineJumpTableInfo &MJTI = *MF->getJumpTableInfo();1197 MJTI.ReplaceMBBInJumpTable(JTI, Succ, NMBB);1198 ChangedIndirectJump = true;1199 }1200 1201 MF->insert(std::next(MachineFunction::iterator(this)), NMBB);1202 LLVM_DEBUG(dbgs() << "Splitting critical edge: " << printMBBReference(*this)1203 << " -- " << printMBBReference(*NMBB) << " -- "1204 << printMBBReference(*Succ) << '\n');1205 auto *LIS = Analyses.LIS;1206 if (LIS)1207 LIS->insertMBBInMaps(NMBB);1208 else if (Analyses.SI)1209 Analyses.SI->insertMBBInMaps(NMBB);1210 1211 // On some targets like Mips, branches may kill virtual registers. Make sure1212 // that LiveVariables is properly updated after updateTerminator replaces the1213 // terminators.1214 auto *LV = Analyses.LV;1215 // Collect a list of virtual registers killed by the terminators.1216 SmallVector<Register, 4> KilledRegs;1217 if (LV)1218 for (MachineInstr &MI :1219 llvm::make_range(getFirstInstrTerminator(), instr_end())) {1220 for (MachineOperand &MO : MI.all_uses()) {1221 if (MO.getReg() == 0 || !MO.isKill() || MO.isUndef())1222 continue;1223 Register Reg = MO.getReg();1224 if (Reg.isPhysical() || LV->getVarInfo(Reg).removeKill(MI)) {1225 KilledRegs.push_back(Reg);1226 LLVM_DEBUG(dbgs() << "Removing terminator kill: " << MI);1227 MO.setIsKill(false);1228 }1229 }1230 }1231 1232 SmallVector<Register, 4> UsedRegs;1233 if (LIS) {1234 for (MachineInstr &MI :1235 llvm::make_range(getFirstInstrTerminator(), instr_end())) {1236 for (const MachineOperand &MO : MI.operands()) {1237 if (!MO.isReg() || MO.getReg() == 0)1238 continue;1239 1240 Register Reg = MO.getReg();1241 if (!is_contained(UsedRegs, Reg))1242 UsedRegs.push_back(Reg);1243 }1244 }1245 }1246 1247 ReplaceUsesOfBlockWith(Succ, NMBB);1248 1249 // Since we replaced all uses of Succ with NMBB, that should also be treated1250 // as the fallthrough successor1251 if (Succ == PrevFallthrough)1252 PrevFallthrough = NMBB;1253 auto *Indexes = Analyses.SI;1254 if (!ChangedIndirectJump) {1255 SlotIndexUpdateDelegate SlotUpdater(*MF, Indexes);1256 updateTerminator(PrevFallthrough);1257 }1258 1259 // Insert unconditional "jump Succ" instruction in NMBB if necessary.1260 NMBB->addSuccessor(Succ);1261 if (!NMBB->isLayoutSuccessor(Succ)) {1262 SlotIndexUpdateDelegate SlotUpdater(*MF, Indexes);1263 SmallVector<MachineOperand, 4> Cond;1264 const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();1265 1266 // In original 'this' BB, there must be a branch instruction targeting at1267 // Succ. We can not find it out since currently getBranchDestBlock was not1268 // implemented for all targets. However, if the merged DL has column or line1269 // number, the scope and non-zero column and line number is same with that1270 // branch instruction so we can safely use it.1271 DebugLoc DL, MergedDL = findBranchDebugLoc();1272 if (MergedDL && (MergedDL.getLine() || MergedDL.getCol()))1273 DL = MergedDL;1274 TII->insertBranch(*NMBB, Succ, nullptr, Cond, DL);1275 }1276 1277 // Fix PHI nodes in Succ so they refer to NMBB instead of this.1278 Succ->replacePhiUsesWith(this, NMBB);1279 1280 // Inherit live-ins from the successor1281 for (const auto &LI : Succ->liveins())1282 NMBB->addLiveIn(LI);1283 1284 // Update LiveVariables.1285 const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();1286 if (LV) {1287 // Restore kills of virtual registers that were killed by the terminators.1288 while (!KilledRegs.empty()) {1289 Register Reg = KilledRegs.pop_back_val();1290 for (instr_iterator I = instr_end(), E = instr_begin(); I != E;) {1291 if (!(--I)->addRegisterKilled(Reg, TRI, /* AddIfNotFound= */ false))1292 continue;1293 if (Reg.isVirtual())1294 LV->getVarInfo(Reg).Kills.push_back(&*I);1295 LLVM_DEBUG(dbgs() << "Restored terminator kill: " << *I);1296 break;1297 }1298 }1299 // Update relevant live-through information.1300 if (LiveInSets != nullptr)1301 LV->addNewBlock(NMBB, this, Succ, *LiveInSets);1302 else1303 LV->addNewBlock(NMBB, this, Succ);1304 }1305 1306 if (LIS) {1307 // After splitting the edge and updating SlotIndexes, live intervals may be1308 // in one of two situations, depending on whether this block was the last in1309 // the function. If the original block was the last in the function, all1310 // live intervals will end prior to the beginning of the new split block. If1311 // the original block was not at the end of the function, all live intervals1312 // will extend to the end of the new split block.1313 1314 bool isLastMBB =1315 std::next(MachineFunction::iterator(NMBB)) == getParent()->end();1316 1317 SlotIndex StartIndex = Indexes->getMBBEndIdx(this);1318 SlotIndex PrevIndex = StartIndex.getPrevSlot();1319 SlotIndex EndIndex = Indexes->getMBBEndIdx(NMBB);1320 1321 // Find the registers used from NMBB in PHIs in Succ.1322 SmallSet<Register, 8> PHISrcRegs;1323 for (MachineBasicBlock::instr_iterator1324 I = Succ->instr_begin(), E = Succ->instr_end();1325 I != E && I->isPHI(); ++I) {1326 for (unsigned ni = 1, ne = I->getNumOperands(); ni != ne; ni += 2) {1327 if (I->getOperand(ni+1).getMBB() == NMBB) {1328 MachineOperand &MO = I->getOperand(ni);1329 Register Reg = MO.getReg();1330 PHISrcRegs.insert(Reg);1331 if (MO.isUndef())1332 continue;1333 1334 LiveInterval &LI = LIS->getInterval(Reg);1335 VNInfo *VNI = LI.getVNInfoAt(PrevIndex);1336 assert(VNI &&1337 "PHI sources should be live out of their predecessors.");1338 LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));1339 for (auto &SR : LI.subranges())1340 SR.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));1341 }1342 }1343 }1344 1345 MachineRegisterInfo *MRI = &getParent()->getRegInfo();1346 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {1347 Register Reg = Register::index2VirtReg(i);1348 if (PHISrcRegs.count(Reg) || !LIS->hasInterval(Reg))1349 continue;1350 1351 LiveInterval &LI = LIS->getInterval(Reg);1352 if (!LI.liveAt(PrevIndex))1353 continue;1354 1355 bool isLiveOut = LI.liveAt(LIS->getMBBStartIdx(Succ));1356 if (isLiveOut && isLastMBB) {1357 VNInfo *VNI = LI.getVNInfoAt(PrevIndex);1358 assert(VNI && "LiveInterval should have VNInfo where it is live.");1359 LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));1360 // Update subranges with live values1361 for (auto &SR : LI.subranges()) {1362 VNInfo *VNI = SR.getVNInfoAt(PrevIndex);1363 if (VNI)1364 SR.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));1365 }1366 } else if (!isLiveOut && !isLastMBB) {1367 LI.removeSegment(StartIndex, EndIndex);1368 for (auto &SR : LI.subranges())1369 SR.removeSegment(StartIndex, EndIndex);1370 }1371 }1372 1373 // Update all intervals for registers whose uses may have been modified by1374 // updateTerminator().1375 LIS->repairIntervalsInRange(this, getFirstTerminator(), end(), UsedRegs);1376 }1377 1378 if (MDTU)1379 MDTU->splitCriticalEdge(this, Succ, NMBB);1380 1381 if (MachineLoopInfo *MLI = Analyses.MLI)1382 if (MachineLoop *TIL = MLI->getLoopFor(this)) {1383 // If one or the other blocks were not in a loop, the new block is not1384 // either, and thus LI doesn't need to be updated.1385 if (MachineLoop *DestLoop = MLI->getLoopFor(Succ)) {1386 if (TIL == DestLoop) {1387 // Both in the same loop, the NMBB joins loop.1388 DestLoop->addBasicBlockToLoop(NMBB, *MLI);1389 } else if (TIL->contains(DestLoop)) {1390 // Edge from an outer loop to an inner loop. Add to the outer loop.1391 TIL->addBasicBlockToLoop(NMBB, *MLI);1392 } else if (DestLoop->contains(TIL)) {1393 // Edge from an inner loop to an outer loop. Add to the outer loop.1394 DestLoop->addBasicBlockToLoop(NMBB, *MLI);1395 } else {1396 // Edge from two loops with no containment relation. Because these1397 // are natural loops, we know that the destination block must be the1398 // header of its loop (adding a branch into a loop elsewhere would1399 // create an irreducible loop).1400 assert(DestLoop->getHeader() == Succ &&1401 "Should not create irreducible loops!");1402 if (MachineLoop *P = DestLoop->getParentLoop())1403 P->addBasicBlockToLoop(NMBB, *MLI);1404 }1405 }1406 }1407 1408 return NMBB;1409}1410 1411bool MachineBasicBlock::canSplitCriticalEdge(const MachineBasicBlock *Succ,1412 const MachineLoopInfo *MLI) const {1413 // Splitting the critical edge to a landing pad block is non-trivial. Don't do1414 // it in this generic function.1415 if (Succ->isEHPad())1416 return false;1417 1418 // Splitting the critical edge to a callbr's indirect block isn't advised.1419 // Don't do it in this generic function.1420 if (Succ->isInlineAsmBrIndirectTarget())1421 return false;1422 1423 const MachineFunction *MF = getParent();1424 // Performance might be harmed on HW that implements branching using exec mask1425 // where both sides of the branches are always executed.1426 1427 if (MF->getTarget().requiresStructuredCFG()) {1428 // If `Succ` is a loop header, splitting the critical edge will not1429 // break structured CFG.1430 if (MLI) {1431 const MachineLoop *L = MLI->getLoopFor(Succ);1432 return L && L->getHeader() == Succ;1433 }1434 1435 return false;1436 }1437 1438 // Do we have an Indirect jump with a jumptable that we can rewrite?1439 int JTI = findJumpTableIndex(*this);1440 if (JTI >= 0 && !jumpTableHasOtherUses(*MF, *this, JTI))1441 return true;1442 1443 // We may need to update this's terminator, but we can't do that if1444 // analyzeBranch fails.1445 const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();1446 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;1447 SmallVector<MachineOperand, 4> Cond;1448 // AnalyzeBanch should modify this, since we did not allow modification.1449 if (TII->analyzeBranch(*const_cast<MachineBasicBlock *>(this), TBB, FBB, Cond,1450 /*AllowModify*/ false))1451 return false;1452 1453 // Avoid bugpoint weirdness: A block may end with a conditional branch but1454 // jumps to the same MBB is either case. We have duplicate CFG edges in that1455 // case that we can't handle. Since this never happens in properly optimized1456 // code, just skip those edges.1457 if (TBB && TBB == FBB) {1458 LLVM_DEBUG(dbgs() << "Won't split critical edge after degenerate "1459 << printMBBReference(*this) << '\n');1460 return false;1461 }1462 return true;1463}1464 1465/// Prepare MI to be removed from its bundle. This fixes bundle flags on MI's1466/// neighboring instructions so the bundle won't be broken by removing MI.1467static void unbundleSingleMI(MachineInstr *MI) {1468 // Removing the first instruction in a bundle.1469 if (MI->isBundledWithSucc() && !MI->isBundledWithPred())1470 MI->unbundleFromSucc();1471 // Removing the last instruction in a bundle.1472 if (MI->isBundledWithPred() && !MI->isBundledWithSucc())1473 MI->unbundleFromPred();1474 // If MI is not bundled, or if it is internal to a bundle, the neighbor flags1475 // are already fine.1476}1477 1478MachineBasicBlock::instr_iterator1479MachineBasicBlock::erase(MachineBasicBlock::instr_iterator I) {1480 unbundleSingleMI(&*I);1481 return Insts.erase(I);1482}1483 1484MachineInstr *MachineBasicBlock::remove_instr(MachineInstr *MI) {1485 unbundleSingleMI(MI);1486 MI->clearFlag(MachineInstr::BundledPred);1487 MI->clearFlag(MachineInstr::BundledSucc);1488 return Insts.remove(MI);1489}1490 1491MachineBasicBlock::instr_iterator1492MachineBasicBlock::insert(instr_iterator I, MachineInstr *MI) {1493 assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&1494 "Cannot insert instruction with bundle flags");1495 // Set the bundle flags when inserting inside a bundle.1496 if (I != instr_end() && I->isBundledWithPred()) {1497 MI->setFlag(MachineInstr::BundledPred);1498 MI->setFlag(MachineInstr::BundledSucc);1499 }1500 return Insts.insert(I, MI);1501}1502 1503/// This method unlinks 'this' from the containing function, and returns it, but1504/// does not delete it.1505MachineBasicBlock *MachineBasicBlock::removeFromParent() {1506 assert(getParent() && "Not embedded in a function!");1507 getParent()->remove(this);1508 return this;1509}1510 1511/// This method unlinks 'this' from the containing function, and deletes it.1512void MachineBasicBlock::eraseFromParent() {1513 assert(getParent() && "Not embedded in a function!");1514 getParent()->erase(this);1515}1516 1517/// Given a machine basic block that branched to 'Old', change the code and CFG1518/// so that it branches to 'New' instead.1519void MachineBasicBlock::ReplaceUsesOfBlockWith(MachineBasicBlock *Old,1520 MachineBasicBlock *New) {1521 assert(Old != New && "Cannot replace self with self!");1522 1523 MachineBasicBlock::instr_iterator I = instr_end();1524 while (I != instr_begin()) {1525 --I;1526 if (!I->isTerminator()) break;1527 1528 // Scan the operands of this machine instruction, replacing any uses of Old1529 // with New.1530 for (MachineOperand &MO : I->operands())1531 if (MO.isMBB() && MO.getMBB() == Old)1532 MO.setMBB(New);1533 }1534 1535 // Update the successor information.1536 replaceSuccessor(Old, New);1537}1538 1539void MachineBasicBlock::replacePhiUsesWith(MachineBasicBlock *Old,1540 MachineBasicBlock *New) {1541 for (MachineInstr &MI : phis())1542 for (unsigned i = 2, e = MI.getNumOperands() + 1; i != e; i += 2) {1543 MachineOperand &MO = MI.getOperand(i);1544 if (MO.getMBB() == Old)1545 MO.setMBB(New);1546 }1547}1548 1549/// Find the next valid DebugLoc starting at MBBI, skipping any debug1550/// instructions. Return UnknownLoc if there is none.1551DebugLoc1552MachineBasicBlock::findDebugLoc(instr_iterator MBBI) {1553 // Skip debug declarations, we don't want a DebugLoc from them.1554 MBBI = skipDebugInstructionsForward(MBBI, instr_end());1555 if (MBBI != instr_end())1556 return MBBI->getDebugLoc();1557 return {};1558}1559 1560DebugLoc MachineBasicBlock::rfindDebugLoc(reverse_instr_iterator MBBI) {1561 if (MBBI == instr_rend())1562 return findDebugLoc(instr_begin());1563 // Skip debug declarations, we don't want a DebugLoc from them.1564 MBBI = skipDebugInstructionsBackward(MBBI, instr_rbegin());1565 if (!MBBI->isDebugInstr())1566 return MBBI->getDebugLoc();1567 return {};1568}1569 1570/// Find the previous valid DebugLoc preceding MBBI, skipping any debug1571/// instructions. Return UnknownLoc if there is none.1572DebugLoc MachineBasicBlock::findPrevDebugLoc(instr_iterator MBBI) {1573 if (MBBI == instr_begin())1574 return {};1575 // Skip debug instructions, we don't want a DebugLoc from them.1576 MBBI = prev_nodbg(MBBI, instr_begin());1577 if (!MBBI->isDebugInstr())1578 return MBBI->getDebugLoc();1579 return {};1580}1581 1582DebugLoc MachineBasicBlock::rfindPrevDebugLoc(reverse_instr_iterator MBBI) {1583 if (MBBI == instr_rend())1584 return {};1585 // Skip debug declarations, we don't want a DebugLoc from them.1586 MBBI = next_nodbg(MBBI, instr_rend());1587 if (MBBI != instr_rend())1588 return MBBI->getDebugLoc();1589 return {};1590}1591 1592/// Find and return the merged DebugLoc of the branch instructions of the block.1593/// Return UnknownLoc if there is none.1594DebugLoc1595MachineBasicBlock::findBranchDebugLoc() {1596 DebugLoc DL;1597 auto TI = getFirstTerminator();1598 while (TI != end() && !TI->isBranch())1599 ++TI;1600 1601 if (TI != end()) {1602 DL = TI->getDebugLoc();1603 for (++TI ; TI != end() ; ++TI)1604 if (TI->isBranch())1605 DL = DebugLoc::getMergedLocation(DL, TI->getDebugLoc());1606 }1607 return DL;1608}1609 1610/// Return probability of the edge from this block to MBB.1611BranchProbability1612MachineBasicBlock::getSuccProbability(const_succ_iterator Succ) const {1613 if (Probs.empty())1614 return BranchProbability(1, succ_size());1615 1616 const auto &Prob = *getProbabilityIterator(Succ);1617 if (!Prob.isUnknown())1618 return Prob;1619 // For unknown probabilities, collect the sum of all known ones, and evenly1620 // ditribute the complemental of the sum to each unknown probability.1621 unsigned KnownProbNum = 0;1622 auto Sum = BranchProbability::getZero();1623 for (const auto &P : Probs) {1624 if (!P.isUnknown()) {1625 Sum += P;1626 KnownProbNum++;1627 }1628 }1629 return Sum.getCompl() / (Probs.size() - KnownProbNum);1630}1631 1632bool MachineBasicBlock::canPredictBranchProbabilities() const {1633 if (succ_size() <= 1)1634 return true;1635 if (!hasSuccessorProbabilities())1636 return true;1637 1638 SmallVector<BranchProbability, 8> Normalized(Probs.begin(), Probs.end());1639 BranchProbability::normalizeProbabilities(Normalized);1640 1641 // Normalize assuming unknown probabilities. This will assign equal1642 // probabilities to all successors.1643 SmallVector<BranchProbability, 8> Equal(Normalized.size());1644 BranchProbability::normalizeProbabilities(Equal);1645 1646 return llvm::equal(Normalized, Equal);1647}1648 1649/// Set successor probability of a given iterator.1650void MachineBasicBlock::setSuccProbability(succ_iterator I,1651 BranchProbability Prob) {1652 assert(!Prob.isUnknown());1653 if (Probs.empty())1654 return;1655 *getProbabilityIterator(I) = Prob;1656}1657 1658/// Return probability iterator corresonding to the I successor iterator1659MachineBasicBlock::const_probability_iterator1660MachineBasicBlock::getProbabilityIterator(1661 MachineBasicBlock::const_succ_iterator I) const {1662 assert(Probs.size() == Successors.size() && "Async probability list!");1663 const size_t index = std::distance(Successors.begin(), I);1664 assert(index < Probs.size() && "Not a current successor!");1665 return Probs.begin() + index;1666}1667 1668/// Return probability iterator corresonding to the I successor iterator.1669MachineBasicBlock::probability_iterator1670MachineBasicBlock::getProbabilityIterator(MachineBasicBlock::succ_iterator I) {1671 assert(Probs.size() == Successors.size() && "Async probability list!");1672 const size_t index = std::distance(Successors.begin(), I);1673 assert(index < Probs.size() && "Not a current successor!");1674 return Probs.begin() + index;1675}1676 1677/// Return whether (physical) register "Reg" has been <def>ined and not <kill>ed1678/// as of just before "MI".1679///1680/// Search is localised to a neighborhood of1681/// Neighborhood instructions before (searching for defs or kills) and N1682/// instructions after (searching just for defs) MI.1683MachineBasicBlock::LivenessQueryResult1684MachineBasicBlock::computeRegisterLiveness(const TargetRegisterInfo *TRI,1685 MCRegister Reg, const_iterator Before,1686 unsigned Neighborhood) const {1687 unsigned N = Neighborhood;1688 1689 // Try searching forwards from Before, looking for reads or defs.1690 const_iterator I(Before);1691 for (; I != end() && N > 0; ++I) {1692 if (I->isDebugOrPseudoInstr())1693 continue;1694 1695 --N;1696 1697 PhysRegInfo Info = AnalyzePhysRegInBundle(*I, Reg, TRI);1698 1699 // Register is live when we read it here.1700 if (Info.Read)1701 return LQR_Live;1702 // Register is dead if we can fully overwrite or clobber it here.1703 if (Info.FullyDefined || Info.Clobbered)1704 return LQR_Dead;1705 }1706 1707 // If we reached the end, it is safe to clobber Reg at the end of a block of1708 // no successor has it live in.1709 if (I == end()) {1710 for (MachineBasicBlock *S : successors()) {1711 for (const MachineBasicBlock::RegisterMaskPair &LI : S->liveins()) {1712 if (TRI->regsOverlap(LI.PhysReg, Reg))1713 return LQR_Live;1714 }1715 }1716 1717 return LQR_Dead;1718 }1719 1720 1721 N = Neighborhood;1722 1723 // Start by searching backwards from Before, looking for kills, reads or defs.1724 I = const_iterator(Before);1725 // If this is the first insn in the block, don't search backwards.1726 if (I != begin()) {1727 do {1728 --I;1729 1730 if (I->isDebugOrPseudoInstr())1731 continue;1732 1733 --N;1734 1735 PhysRegInfo Info = AnalyzePhysRegInBundle(*I, Reg, TRI);1736 1737 // Defs happen after uses so they take precedence if both are present.1738 1739 // Register is dead after a dead def of the full register.1740 if (Info.DeadDef)1741 return LQR_Dead;1742 // Register is (at least partially) live after a def.1743 if (Info.Defined) {1744 if (!Info.PartialDeadDef)1745 return LQR_Live;1746 // As soon as we saw a partial definition (dead or not),1747 // we cannot tell if the value is partial live without1748 // tracking the lanemasks. We are not going to do this,1749 // so fall back on the remaining of the analysis.1750 break;1751 }1752 // Register is dead after a full kill or clobber and no def.1753 if (Info.Killed || Info.Clobbered)1754 return LQR_Dead;1755 // Register must be live if we read it.1756 if (Info.Read)1757 return LQR_Live;1758 1759 } while (I != begin() && N > 0);1760 }1761 1762 // If all the instructions before this in the block are debug instructions,1763 // skip over them.1764 while (I != begin() && std::prev(I)->isDebugOrPseudoInstr())1765 --I;1766 1767 // Did we get to the start of the block?1768 if (I == begin()) {1769 // If so, the register's state is definitely defined by the live-in state.1770 for (const MachineBasicBlock::RegisterMaskPair &LI : liveins())1771 if (TRI->regsOverlap(LI.PhysReg, Reg))1772 return LQR_Live;1773 1774 return LQR_Dead;1775 }1776 1777 // At this point we have no idea of the liveness of the register.1778 return LQR_Unknown;1779}1780 1781const uint32_t *1782MachineBasicBlock::getBeginClobberMask(const TargetRegisterInfo *TRI) const {1783 // EH funclet entry does not preserve any registers.1784 return isEHFuncletEntry() ? TRI->getNoPreservedMask() : nullptr;1785}1786 1787const uint32_t *1788MachineBasicBlock::getEndClobberMask(const TargetRegisterInfo *TRI) const {1789 // If we see a return block with successors, this must be a funclet return,1790 // which does not preserve any registers. If there are no successors, we don't1791 // care what kind of return it is, putting a mask after it is a no-op.1792 return isReturnBlock() && !succ_empty() ? TRI->getNoPreservedMask() : nullptr;1793}1794 1795void MachineBasicBlock::clearLiveIns() {1796 LiveIns.clear();1797}1798 1799void MachineBasicBlock::clearLiveIns(1800 std::vector<RegisterMaskPair> &OldLiveIns) {1801 assert(OldLiveIns.empty() && "Vector must be empty");1802 std::swap(LiveIns, OldLiveIns);1803}1804 1805MachineBasicBlock::livein_iterator MachineBasicBlock::livein_begin() const {1806 assert(getParent()->getProperties().hasTracksLiveness() &&1807 "Liveness information is accurate");1808 return LiveIns.begin();1809}1810 1811MachineBasicBlock::liveout_iterator MachineBasicBlock::liveout_begin() const {1812 const MachineFunction &MF = *getParent();1813 const TargetLowering &TLI = *MF.getSubtarget().getTargetLowering();1814 MCRegister ExceptionPointer, ExceptionSelector;1815 if (MF.getFunction().hasPersonalityFn()) {1816 auto PersonalityFn = MF.getFunction().getPersonalityFn();1817 ExceptionPointer = TLI.getExceptionPointerRegister(PersonalityFn);1818 ExceptionSelector = TLI.getExceptionSelectorRegister(PersonalityFn);1819 }1820 1821 return liveout_iterator(*this, ExceptionPointer, ExceptionSelector, false);1822}1823 1824bool MachineBasicBlock::sizeWithoutDebugLargerThan(unsigned Limit) const {1825 unsigned Cntr = 0;1826 auto R = instructionsWithoutDebug(begin(), end());1827 for (auto I = R.begin(), E = R.end(); I != E; ++I) {1828 if (++Cntr > Limit)1829 return true;1830 }1831 return false;1832}1833 1834void MachineBasicBlock::removePHIsIncomingValuesForPredecessor(1835 const MachineBasicBlock &PredMBB) {1836 for (MachineInstr &Phi : phis())1837 Phi.removePHIIncomingValueFor(PredMBB);1838}1839 1840const MBBSectionID MBBSectionID::ColdSectionID(MBBSectionID::SectionType::Cold);1841const MBBSectionID1842 MBBSectionID::ExceptionSectionID(MBBSectionID::SectionType::Exception);1843