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