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