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