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