LLVM 20.0.0git
MachineBasicBlock.cpp
Go to the documentation of this file.
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
14#include "llvm/ADT/STLExtras.h"
30#include "llvm/Config/llvm-config.h"
31#include "llvm/IR/BasicBlock.h"
34#include "llvm/MC/MCAsmInfo.h"
35#include "llvm/MC/MCContext.h"
36#include "llvm/Support/Debug.h"
39#include <algorithm>
40#include <cmath>
41using namespace llvm;
42
43#define DEBUG_TYPE "codegen"
44
46 "print-slotindexes",
47 cl::desc("When printing machine IR, annotate instructions and blocks with "
48 "SlotIndexes when available"),
49 cl::init(true), cl::Hidden);
50
51MachineBasicBlock::MachineBasicBlock(MachineFunction &MF, const BasicBlock *B)
52 : BB(B), Number(-1), xParent(&MF) {
53 Insts.Parent = this;
54 if (B)
55 IrrLoopHeaderWeight = B->getIrrLoopHeaderWeight();
56}
57
58MachineBasicBlock::~MachineBasicBlock() = default;
59
60/// Return the MCSymbol for this basic block.
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(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 "BB" + Twine(MF->getFunctionNumber()) + "_" + Twine(getNumber()),
87 /*AlwaysEmit=*/hasLabelMustBeEmitted());
88 }
89 }
90 return CachedMCSymbol;
91}
92
94 if (!CachedEHCatchretMCSymbol) {
95 const MachineFunction *MF = getParent();
96 SmallString<128> SymbolName;
97 raw_svector_ostream(SymbolName)
98 << "$ehgcr_" << MF->getFunctionNumber() << '_' << getNumber();
99 CachedEHCatchretMCSymbol = MF->getContext().getOrCreateSymbol(SymbolName);
100 }
101 return CachedEHCatchretMCSymbol;
102}
103
105 if (!CachedEndMCSymbol) {
106 const MachineFunction *MF = getParent();
107 MCContext &Ctx = MF->getContext();
108 CachedEndMCSymbol = Ctx.createBlockSymbol(
109 "BB_END" + Twine(MF->getFunctionNumber()) + "_" + Twine(getNumber()),
110 /*AlwaysEmit=*/false);
111 }
112 return CachedEndMCSymbol;
113}
114
116 MBB.print(OS);
117 return OS;
118}
119
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.
133 MachineFunction &MF = *N->getParent();
134 N->Number = MF.addToMBBNumbering(N);
135
136 // Make sure the instructions have their operands in the reginfo lists.
137 MachineRegisterInfo &RegInfo = MF.getRegInfo();
138 for (MachineInstr &MI : N->instrs())
139 MI.addRegOperandsToUseLists(RegInfo);
140}
141
144 N->getParent()->removeFromMBBNumbering(N->Number);
145 N->Number = -1;
146}
147
148/// When we add an instruction to a basic block list, we update its parent
149/// pointer and add its operands from reg use/def lists if appropriate.
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(*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.
164 assert(N->getParent() && "machine instruction not in a basic block");
165
166 // Remove from the use/def lists.
167 if (MachineFunction *MF = N->getMF()) {
168 MF->handleRemoval(*N);
169 N->removeRegOperandsFromUseLists(MF->getRegInfo());
170 }
171
172 N->setParent(nullptr);
173}
174
175/// When moving a range of instructions from one MBB list to another, we need to
176/// update the parent pointers and the use/def lists.
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
196 assert(!MI->getParent() && "MI is still in a block!");
197 Parent->getParent()->deleteMachineInstr(MI);
198}
199
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
212
213 iterator E = end();
214 while (I != E && (I->isPHI() || I->isPosition() ||
215 TII->isBasicBlockPrologue(*I)))
216 ++I;
217 // FIXME: This needs to change if we wish to bundle 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
226 Register Reg, bool SkipPseudoOp) {
228
229 iterator E = end();
230 while (I != E && (I->isPHI() || I->isPosition() || I->isDebugInstr() ||
231 (SkipPseudoOp && I->isPseudoProbe()) ||
232 TII->isBasicBlockPrologue(*I, Reg)))
233 ++I;
234 // FIXME: This needs to change if we wish to bundle labels / dbg_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
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
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
261 return find_if(instrs(), [](auto &II) { return II.isTerminator(); });
262}
263
266 // Skip over begin-of-block dbg_value instructions.
267 return skipDebugInstructionsForward(begin(), end(), SkipPseudoOp);
268}
269
272 // Skip over end-of-block dbg_value instructions.
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
288 for (const MachineBasicBlock *Succ : successors())
289 if (Succ->isEHPad())
290 return true;
291 return false;
292}
293
295 return getParent()->begin() == getIterator();
296}
297
298#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
300 print(dbgs());
301}
302#endif
303
305 for (const MachineBasicBlock *Succ : successors()) {
306 if (Succ->isInlineAsmBrIndirectTarget())
307 return true;
308 }
309 return false;
310}
311
314 return false;
315 return true;
316}
317
319 if (const BasicBlock *LBB = getBasicBlock())
320 return LBB->hasName();
321 return false;
322}
323
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.
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
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);
355 print(OS, MST, Indexes, IsStandalone);
356}
357
359 const SlotIndexes *Indexes,
360 bool IsStandalone) const {
361 const MachineFunction *MF = getParent();
362 if (!MF) {
363 OS << "Can't print out MachineBasicBlock because parent MachineFunction"
364 << " is null\n";
365 return;
366 }
367
368 if (Indexes && PrintSlotIndexes)
369 OS << Indexes->getMBBStartIdx(this) << '\t';
370
372 OS << ":\n";
373
375 const MachineRegisterInfo &MRI = MF->getRegInfo();
377 bool HasLineAttributes = false;
378
379 // Print the preds of this block according to the CFG.
380 if (!pred_empty() && IsStandalone) {
381 if (Indexes) OS << '\t';
382 // Don't indent(2), align with previous line attributes.
383 OS << "; predecessors: ";
384 ListSeparator LS;
385 for (auto *Pred : predecessors())
386 OS << LS << printMBBReference(*Pred);
387 OS << '\n';
388 HasLineAttributes = true;
389 }
390
391 if (!succ_empty()) {
392 if (Indexes) OS << '\t';
393 // Print the successors
394 OS.indent(2) << "successors: ";
395 ListSeparator LS;
396 for (auto I = succ_begin(), E = succ_end(); I != E; ++I) {
397 OS << LS << printMBBReference(**I);
398 if (!Probs.empty())
399 OS << '('
400 << format("0x%08" PRIx32, getSuccProbability(I).getNumerator())
401 << ')';
402 }
403 if (!Probs.empty() && IsStandalone) {
404 // Print human readable probabilities as comments.
405 OS << "; ";
406 ListSeparator LS;
407 for (auto I = succ_begin(), E = succ_end(); I != E; ++I) {
409 OS << LS << printMBBReference(**I) << '('
410 << format("%.2f%%",
411 rint(((double)BP.getNumerator() / BP.getDenominator()) *
412 100.0 * 100.0) /
413 100.0)
414 << ')';
415 }
416 }
417
418 OS << '\n';
419 HasLineAttributes = true;
420 }
421
422 if (!livein_empty() && MRI.tracksLiveness()) {
423 if (Indexes) OS << '\t';
424 OS.indent(2) << "liveins: ";
425
426 ListSeparator LS;
427 for (const auto &LI : liveins()) {
428 OS << LS << printReg(LI.PhysReg, TRI);
429 if (!LI.LaneMask.all())
430 OS << ":0x" << PrintLaneMask(LI.LaneMask);
431 }
432 HasLineAttributes = true;
433 }
434
435 if (HasLineAttributes)
436 OS << '\n';
437
438 bool IsInBundle = false;
439 for (const MachineInstr &MI : instrs()) {
440 if (Indexes && PrintSlotIndexes) {
441 if (Indexes->hasIndex(MI))
442 OS << Indexes->getInstructionIndex(MI);
443 OS << '\t';
444 }
445
446 if (IsInBundle && !MI.isInsideBundle()) {
447 OS.indent(2) << "}\n";
448 IsInBundle = false;
449 }
450
451 OS.indent(IsInBundle ? 4 : 2);
452 MI.print(OS, MST, IsStandalone, /*SkipOpers=*/false, /*SkipDebugLoc=*/false,
453 /*AddNewLine=*/false, &TII);
454
455 if (!IsInBundle && MI.getFlag(MachineInstr::BundledSucc)) {
456 OS << " {";
457 IsInBundle = true;
458 }
459 OS << '\n';
460 }
461
462 if (IsInBundle)
463 OS.indent(2) << "}\n";
464
465 if (IrrLoopHeaderWeight && IsStandalone) {
466 if (Indexes) OS << '\t';
467 OS.indent(2) << "; Irreducible loop header weight: " << *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(bb);
502 } else if (bb->getParent()) {
503 ModuleSlotTracker tmpTracker(bb->getModule(), false);
504 tmpTracker.incorporateFunction(*bb->getParent());
505 slot = tmpTracker.getLocalSlot(bb);
506 }
507
508 if (slot == -1)
509 os << "<ir-block badref>";
510 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) {
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 }
545 os << (hasAttributes ? ", " : " (");
546 os << "inlineasm-br-indirect-target";
547 hasAttributes = true;
548 }
549 if (isEHFuncletEntry()) {
550 os << (hasAttributes ? ", " : " (");
551 os << "ehfunclet-entry";
552 hasAttributes = true;
553 }
554 if (getAlignment() != Align(1)) {
555 os << (hasAttributes ? ", " : " (");
556 os << "align " << getAlignment().value();
557 hasAttributes = true;
558 }
559 if (getSectionID() != MBBSectionID(0)) {
560 os << (hasAttributes ? ", " : " (");
561 os << "bbsections ";
562 switch (getSectionID().Type) {
564 os << "Exception";
565 break;
567 os << "Cold";
568 break;
569 default:
570 os << getSectionID().Number;
571 }
572 hasAttributes = true;
573 }
574 if (getBBID().has_value()) {
575 os << (hasAttributes ? ", " : " (");
576 os << "bb_id " << getBBID()->BaseID;
577 if (getBBID()->CloneID != 0)
578 os << " " << getBBID()->CloneID;
579 hasAttributes = true;
580 }
581 if (CallFrameSize != 0) {
582 os << (hasAttributes ? ", " : " (");
583 os << "call-frame-size " << CallFrameSize;
584 hasAttributes = true;
585 }
586 }
587
588 if (hasAttributes)
589 os << ')';
590}
591
593 bool /*PrintType*/) const {
594 OS << '%';
595 printName(OS, 0);
596}
597
599 LiveInVector::iterator I = find_if(
600 LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
601 if (I == LiveIns.end())
602 return;
603
604 I->LaneMask &= ~LaneMask;
605 if (I->LaneMask.none())
606 LiveIns.erase(I);
607}
608
611 // Get non-const version of iterator.
612 LiveInVector::iterator LI = LiveIns.begin() + (I - LiveIns.begin());
613 return LiveIns.erase(LI);
614}
615
618 LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
619 return I != livein_end() && (I->LaneMask & LaneMask).any();
620}
621
623 llvm::sort(LiveIns,
624 [](const RegisterMaskPair &LI0, const RegisterMaskPair &LI1) {
625 return LI0.PhysReg < LI1.PhysReg;
626 });
627 // Liveins are sorted by physreg now we can merge their lanemasks.
628 LiveInVector::const_iterator I = LiveIns.begin();
629 LiveInVector::const_iterator J;
630 LiveInVector::iterator Out = LiveIns.begin();
631 for (; I != LiveIns.end(); ++Out, I = J) {
632 MCRegister PhysReg = I->PhysReg;
633 LaneBitmask LaneMask = I->LaneMask;
634 for (J = std::next(I); J != LiveIns.end() && J->PhysReg == PhysReg; ++J)
635 LaneMask |= J->LaneMask;
636 Out->PhysReg = PhysReg;
637 Out->LaneMask = LaneMask;
638 }
639 LiveIns.erase(Out, LiveIns.end());
640}
641
644 assert(getParent() && "MBB must be inserted in function");
645 assert(Register::isPhysicalRegister(PhysReg) && "Expected physreg");
646 assert(RC && "Register class is required");
647 assert((isEHPad() || this == &getParent()->front()) &&
648 "Only the entry block and landing pads can have physreg live ins");
649
650 bool LiveIn = isLiveIn(PhysReg);
654
655 // Look for an existing copy.
656 if (LiveIn)
657 for (;I != E && I->isCopy(); ++I)
658 if (I->getOperand(1).getReg() == PhysReg) {
659 Register VirtReg = I->getOperand(0).getReg();
660 if (!MRI.constrainRegClass(VirtReg, RC))
661 llvm_unreachable("Incompatible live-in register class.");
662 return VirtReg;
663 }
664
665 // No luck, create a virtual register.
666 Register VirtReg = MRI.createVirtualRegister(RC);
667 BuildMI(*this, I, DebugLoc(), TII.get(TargetOpcode::COPY), VirtReg)
668 .addReg(PhysReg, RegState::Kill);
669 if (!LiveIn)
670 addLiveIn(PhysReg);
671 return VirtReg;
672}
673
675 getParent()->splice(NewAfter->getIterator(), getIterator());
676}
677
679 getParent()->splice(++NewBefore->getIterator(), getIterator());
680}
681
684 if (TerminatorI == MBB.end())
685 return -1;
686 const MachineInstr &Terminator = *TerminatorI;
688 return TII->getJumpTableIndex(Terminator);
689}
690
692 MachineBasicBlock *PreviousLayoutSuccessor) {
693 LLVM_DEBUG(dbgs() << "Updating terminators on " << printMBBReference(*this)
694 << "\n");
695
697 // A block with no successors has no concerns with fall-through edges.
698 if (this->succ_empty())
699 return;
700
701 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
704 bool B = TII->analyzeBranch(*this, TBB, FBB, Cond);
705 (void) B;
706 assert(!B && "UpdateTerminators requires analyzable predecessors!");
707 if (Cond.empty()) {
708 if (TBB) {
709 // The block has an unconditional branch. If its successor is now its
710 // layout successor, delete the branch.
712 TII->removeBranch(*this);
713 } else {
714 // The block has an unconditional fallthrough, or the end of the block is
715 // unreachable.
716
717 // Unfortunately, whether the end of the block is unreachable is not
718 // immediately obvious; we must fall back to checking the successor list,
719 // and assuming that if the passed in block is in the succesor list and
720 // not an EHPad, it must be the intended target.
721 if (!PreviousLayoutSuccessor || !isSuccessor(PreviousLayoutSuccessor) ||
722 PreviousLayoutSuccessor->isEHPad())
723 return;
724
725 // If the unconditional successor block is not the current layout
726 // successor, insert a branch to jump to it.
727 if (!isLayoutSuccessor(PreviousLayoutSuccessor))
728 TII->insertBranch(*this, PreviousLayoutSuccessor, nullptr, Cond, DL);
729 }
730 return;
731 }
732
733 if (FBB) {
734 // The block has a non-fallthrough conditional branch. If one of its
735 // successors is its layout successor, rewrite it to a fallthrough
736 // conditional branch.
737 if (isLayoutSuccessor(TBB)) {
739 return;
740 TII->removeBranch(*this);
741 TII->insertBranch(*this, FBB, nullptr, Cond, DL);
742 } else if (isLayoutSuccessor(FBB)) {
743 TII->removeBranch(*this);
744 TII->insertBranch(*this, TBB, nullptr, Cond, DL);
745 }
746 return;
747 }
748
749 // We now know we're going to fallthrough to PreviousLayoutSuccessor.
750 assert(PreviousLayoutSuccessor);
751 assert(!PreviousLayoutSuccessor->isEHPad());
752 assert(isSuccessor(PreviousLayoutSuccessor));
753
754 if (PreviousLayoutSuccessor == TBB) {
755 // We had a fallthrough to the same basic block as the conditional jump
756 // targets. Remove the conditional jump, leaving an unconditional
757 // fallthrough or an unconditional jump.
758 TII->removeBranch(*this);
759 if (!isLayoutSuccessor(TBB)) {
760 Cond.clear();
761 TII->insertBranch(*this, TBB, nullptr, Cond, DL);
762 }
763 return;
764 }
765
766 // The block has a fallthrough conditional branch.
767 if (isLayoutSuccessor(TBB)) {
769 // We can't reverse the condition, add an unconditional branch.
770 Cond.clear();
771 TII->insertBranch(*this, PreviousLayoutSuccessor, nullptr, Cond, DL);
772 return;
773 }
774 TII->removeBranch(*this);
775 TII->insertBranch(*this, PreviousLayoutSuccessor, nullptr, Cond, DL);
776 } else if (!isLayoutSuccessor(PreviousLayoutSuccessor)) {
777 TII->removeBranch(*this);
778 TII->insertBranch(*this, TBB, PreviousLayoutSuccessor, Cond, DL);
779 }
780}
781
783#ifndef NDEBUG
784 int64_t Sum = 0;
785 for (auto Prob : Probs)
786 Sum += Prob.getNumerator();
787 // Due to precision issue, we assume that the sum of probabilities is one if
788 // the difference between the sum of their numerators and the denominator is
789 // no greater than the number of successors.
791 Probs.size() &&
792 "The sum of successors's probabilities exceeds one.");
793#endif // NDEBUG
794}
795
797 BranchProbability Prob) {
798 // Probability list is either empty (if successor list isn't empty, this means
799 // disabled optimization) or has the same size as successor list.
800 if (!(Probs.empty() && !Successors.empty()))
801 Probs.push_back(Prob);
802 Successors.push_back(Succ);
803 Succ->addPredecessor(this);
804}
805
807 // We need to make sure probability list is either empty or has the same size
808 // of successor list. When this function is called, we can safely delete all
809 // probability in the list.
810 Probs.clear();
811 Successors.push_back(Succ);
812 Succ->addPredecessor(this);
813}
814
817 bool NormalizeSuccProbs) {
818 succ_iterator OldI = llvm::find(successors(), Old);
819 assert(OldI != succ_end() && "Old is not a successor of this block!");
821 "New is already a successor of this block!");
822
823 // Add a new successor with equal probability as the original one. Note
824 // that we directly copy the probability using the iterator rather than
825 // getting a potentially synthetic probability computed when unknown. This
826 // preserves the probabilities as-is and then we can renormalize them and
827 // query them effectively afterward.
828 addSuccessor(New, Probs.empty() ? BranchProbability::getUnknown()
829 : *getProbabilityIterator(OldI));
830 if (NormalizeSuccProbs)
832}
833
835 bool NormalizeSuccProbs) {
836 succ_iterator I = find(Successors, Succ);
837 removeSuccessor(I, NormalizeSuccProbs);
838}
839
842 assert(I != Successors.end() && "Not a current successor!");
843
844 // If probability list is empty it means we don't use it (disabled
845 // optimization).
846 if (!Probs.empty()) {
847 probability_iterator WI = getProbabilityIterator(I);
848 Probs.erase(WI);
849 if (NormalizeSuccProbs)
851 }
852
853 (*I)->removePredecessor(this);
854 return Successors.erase(I);
855}
856
858 MachineBasicBlock *New) {
859 if (Old == New)
860 return;
861
863 succ_iterator NewI = E;
864 succ_iterator OldI = E;
865 for (succ_iterator I = succ_begin(); I != E; ++I) {
866 if (*I == Old) {
867 OldI = I;
868 if (NewI != E)
869 break;
870 }
871 if (*I == New) {
872 NewI = I;
873 if (OldI != E)
874 break;
875 }
876 }
877 assert(OldI != E && "Old is not a successor of this block");
878
879 // If New isn't already a successor, let it take Old's place.
880 if (NewI == E) {
881 Old->removePredecessor(this);
882 New->addPredecessor(this);
883 *OldI = New;
884 return;
885 }
886
887 // New is already a successor.
888 // Update its probability instead of adding a duplicate edge.
889 if (!Probs.empty()) {
890 auto ProbIter = getProbabilityIterator(NewI);
891 if (!ProbIter->isUnknown())
892 *ProbIter += *getProbabilityIterator(OldI);
893 }
894 removeSuccessor(OldI);
895}
896
899 if (!Orig->Probs.empty())
901 else
903}
904
905void MachineBasicBlock::addPredecessor(MachineBasicBlock *Pred) {
906 Predecessors.push_back(Pred);
907}
908
909void MachineBasicBlock::removePredecessor(MachineBasicBlock *Pred) {
910 pred_iterator I = find(Predecessors, Pred);
911 assert(I != Predecessors.end() && "Pred is not a predecessor of this block!");
912 Predecessors.erase(I);
913}
914
916 if (this == FromMBB)
917 return;
918
919 while (!FromMBB->succ_empty()) {
920 MachineBasicBlock *Succ = *FromMBB->succ_begin();
921
922 // If probability list is empty it means we don't use it (disabled
923 // optimization).
924 if (!FromMBB->Probs.empty()) {
925 auto Prob = *FromMBB->Probs.begin();
926 addSuccessor(Succ, Prob);
927 } else
929
930 FromMBB->removeSuccessor(Succ);
931 }
932}
933
934void
936 if (this == FromMBB)
937 return;
938
939 while (!FromMBB->succ_empty()) {
940 MachineBasicBlock *Succ = *FromMBB->succ_begin();
941 if (!FromMBB->Probs.empty()) {
942 auto Prob = *FromMBB->Probs.begin();
943 addSuccessor(Succ, Prob);
944 } else
946 FromMBB->removeSuccessor(Succ);
947
948 // Fix up any PHI nodes in the successor.
949 Succ->replacePhiUsesWith(FromMBB, this);
950 }
952}
953
955 return is_contained(predecessors(), MBB);
956}
957
959 return is_contained(successors(), MBB);
960}
961
964 return std::next(I) == MachineFunction::const_iterator(MBB);
965}
966
968 return Successors.size() == 1 ? Successors[0] : nullptr;
969}
970
972 return Predecessors.size() == 1 ? Predecessors[0] : nullptr;
973}
974
977 ++Fallthrough;
978 // If FallthroughBlock is off the end of the function, it can't fall through.
979 if (Fallthrough == getParent()->end())
980 return nullptr;
981
982 // If FallthroughBlock isn't a successor, no fallthrough is possible.
983 if (!isSuccessor(&*Fallthrough))
984 return nullptr;
985
986 // Analyze the branches, if any, at the end of the block.
987 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
990 if (TII->analyzeBranch(*this, TBB, FBB, Cond)) {
991 // If we couldn't analyze the branch, examine the last instruction.
992 // If the block doesn't end in a known control barrier, assume fallthrough
993 // is possible. The isPredicated check is needed because this code can be
994 // called during IfConversion, where an instruction which is normally a
995 // Barrier is predicated and thus no longer an actual control barrier.
996 return (empty() || !back().isBarrier() || TII->isPredicated(back()))
997 ? &*Fallthrough
998 : nullptr;
999 }
1000
1001 // If there is no branch, control always falls through.
1002 if (!TBB) return &*Fallthrough;
1003
1004 // If there is some explicit branch to the fallthrough block, it can obviously
1005 // reach, even though the branch should get folded to fall through implicitly.
1006 if (JumpToFallThrough && (MachineFunction::iterator(TBB) == Fallthrough ||
1007 MachineFunction::iterator(FBB) == Fallthrough))
1008 return &*Fallthrough;
1009
1010 // If it's an unconditional branch to some block not the fall through, it
1011 // doesn't fall through.
1012 if (Cond.empty()) return nullptr;
1013
1014 // Otherwise, if it is conditional and has no explicit false block, it falls
1015 // through.
1016 return (FBB == nullptr) ? &*Fallthrough : nullptr;
1017}
1018
1020 return getFallThrough() != nullptr;
1021}
1022
1024 bool UpdateLiveIns,
1025 LiveIntervals *LIS) {
1026 MachineBasicBlock::iterator SplitPoint(&MI);
1027 ++SplitPoint;
1028
1029 if (SplitPoint == end()) {
1030 // Don't bother with a new block.
1031 return this;
1032 }
1033
1034 MachineFunction *MF = getParent();
1035
1036 LivePhysRegs LiveRegs;
1037 if (UpdateLiveIns) {
1038 // Make sure we add any physregs we define in the block as liveins to the
1039 // new block.
1041 LiveRegs.init(*MF->getSubtarget().getRegisterInfo());
1042 LiveRegs.addLiveOuts(*this);
1043 for (auto I = rbegin(), E = Prev.getReverse(); I != E; ++I)
1044 LiveRegs.stepBackward(*I);
1045 }
1046
1048
1049 MF->insert(++MachineFunction::iterator(this), SplitBB);
1050 SplitBB->splice(SplitBB->begin(), this, SplitPoint, end());
1051
1052 SplitBB->transferSuccessorsAndUpdatePHIs(this);
1053 addSuccessor(SplitBB);
1054
1055 if (UpdateLiveIns)
1056 addLiveIns(*SplitBB, LiveRegs);
1057
1058 if (LIS)
1059 LIS->insertMBBInMaps(SplitBB);
1060
1061 return SplitBB;
1062}
1063
1064// Returns `true` if there are possibly other users of the jump table at
1065// `JumpTableIndex` except for the ones in `IgnoreMBB`.
1067 const MachineBasicBlock &IgnoreMBB,
1068 int JumpTableIndex) {
1069 assert(JumpTableIndex >= 0 && "need valid index");
1070 const MachineJumpTableInfo &MJTI = *MF.getJumpTableInfo();
1071 const MachineJumpTableEntry &MJTE = MJTI.getJumpTables()[JumpTableIndex];
1072 // Take any basic block from the table; every user of the jump table must
1073 // show up in the predecessor list.
1074 const MachineBasicBlock *MBB = nullptr;
1075 for (MachineBasicBlock *B : MJTE.MBBs) {
1076 if (B != nullptr) {
1077 MBB = B;
1078 break;
1079 }
1080 }
1081 if (MBB == nullptr)
1082 return true; // can't rule out other users if there isn't any block.
1085 for (MachineBasicBlock *Pred : MBB->predecessors()) {
1086 if (Pred == &IgnoreMBB)
1087 continue;
1088 MachineBasicBlock *DummyT = nullptr;
1089 MachineBasicBlock *DummyF = nullptr;
1090 Cond.clear();
1091 if (!TII.analyzeBranch(*Pred, DummyT, DummyF, Cond,
1092 /*AllowModify=*/false)) {
1093 // analyzable direct jump
1094 continue;
1095 }
1096 int PredJTI = findJumpTableIndex(*Pred);
1097 if (PredJTI >= 0) {
1098 if (PredJTI == JumpTableIndex)
1099 return true;
1100 continue;
1101 }
1102 // Be conservative for unanalyzable jumps.
1103 return true;
1104 }
1105 return false;
1106}
1107
1109private:
1110 MachineFunction &MF;
1111 SlotIndexes *Indexes;
1113
1114public:
1116 : MF(MF), Indexes(Indexes) {
1117 MF.setDelegate(this);
1118 }
1119
1121 MF.resetDelegate(this);
1122 for (auto MI : Insertions)
1123 Indexes->insertMachineInstrInMaps(*MI);
1124 }
1125
1127 // This is called before MI is inserted into block so defer index update.
1128 if (Indexes)
1129 Insertions.insert(&MI);
1130 }
1131
1133 if (Indexes && !Insertions.remove(&MI))
1135 }
1136};
1137
1138#define GET_RESULT(RESULT, GETTER, INFIX) \
1139 [MF, P, MFAM]() { \
1140 if (P) { \
1141 auto *Wrapper = P->getAnalysisIfAvailable<RESULT##INFIX##WrapperPass>(); \
1142 return Wrapper ? &Wrapper->GETTER() : nullptr; \
1143 } \
1144 return MFAM->getCachedResult<RESULT##Analysis>(*MF); \
1145 }()
1146
1149 std::vector<SparseBitVector<>> *LiveInSets) {
1150 assert((P || MFAM) && "Need a way to get analysis results!");
1151 if (!canSplitCriticalEdge(Succ))
1152 return nullptr;
1153
1154 MachineFunction *MF = getParent();
1155 MachineBasicBlock *PrevFallthrough = getNextNode();
1156
1158 NMBB->setCallFrameSize(Succ->getCallFrameSize());
1159
1160 // Is there an indirect jump with jump table?
1161 bool ChangedIndirectJump = false;
1162 int JTI = findJumpTableIndex(*this);
1163 if (JTI >= 0) {
1165 MJTI.ReplaceMBBInJumpTable(JTI, Succ, NMBB);
1166 ChangedIndirectJump = true;
1167 }
1168
1169 MF->insert(std::next(MachineFunction::iterator(this)), NMBB);
1170 LLVM_DEBUG(dbgs() << "Splitting critical edge: " << printMBBReference(*this)
1171 << " -- " << printMBBReference(*NMBB) << " -- "
1172 << printMBBReference(*Succ) << '\n');
1173
1174 LiveIntervals *LIS = GET_RESULT(LiveIntervals, getLIS, );
1175 SlotIndexes *Indexes = GET_RESULT(SlotIndexes, getSI, );
1176 if (LIS)
1177 LIS->insertMBBInMaps(NMBB);
1178 else if (Indexes)
1179 Indexes->insertMBBInMaps(NMBB);
1180
1181 // On some targets like Mips, branches may kill virtual registers. Make sure
1182 // that LiveVariables is properly updated after updateTerminator replaces the
1183 // terminators.
1184 LiveVariables *LV = GET_RESULT(LiveVariables, getLV, );
1185
1186 // Collect a list of virtual registers killed by the terminators.
1187 SmallVector<Register, 4> KilledRegs;
1188 if (LV)
1189 for (MachineInstr &MI :
1191 for (MachineOperand &MO : MI.all_uses()) {
1192 if (MO.getReg() == 0 || !MO.isKill() || MO.isUndef())
1193 continue;
1194 Register Reg = MO.getReg();
1195 if (Reg.isPhysical() || LV->getVarInfo(Reg).removeKill(MI)) {
1196 KilledRegs.push_back(Reg);
1197 LLVM_DEBUG(dbgs() << "Removing terminator kill: " << MI);
1198 MO.setIsKill(false);
1199 }
1200 }
1201 }
1202
1203 SmallVector<Register, 4> UsedRegs;
1204 if (LIS) {
1205 for (MachineInstr &MI :
1207 for (const MachineOperand &MO : MI.operands()) {
1208 if (!MO.isReg() || MO.getReg() == 0)
1209 continue;
1210
1211 Register Reg = MO.getReg();
1212 if (!is_contained(UsedRegs, Reg))
1213 UsedRegs.push_back(Reg);
1214 }
1215 }
1216 }
1217
1218 ReplaceUsesOfBlockWith(Succ, NMBB);
1219
1220 // Since we replaced all uses of Succ with NMBB, that should also be treated
1221 // as the fallthrough successor
1222 if (Succ == PrevFallthrough)
1223 PrevFallthrough = NMBB;
1224
1225 if (!ChangedIndirectJump) {
1226 SlotIndexUpdateDelegate SlotUpdater(*MF, Indexes);
1227 updateTerminator(PrevFallthrough);
1228 }
1229
1230 // Insert unconditional "jump Succ" instruction in NMBB if necessary.
1231 NMBB->addSuccessor(Succ);
1232 if (!NMBB->isLayoutSuccessor(Succ)) {
1233 SlotIndexUpdateDelegate SlotUpdater(*MF, Indexes);
1236
1237 // In original 'this' BB, there must be a branch instruction targeting at
1238 // Succ. We can not find it out since currently getBranchDestBlock was not
1239 // implemented for all targets. However, if the merged DL has column or line
1240 // number, the scope and non-zero column and line number is same with that
1241 // branch instruction so we can safely use it.
1242 DebugLoc DL, MergedDL = findBranchDebugLoc();
1243 if (MergedDL && (MergedDL.getLine() || MergedDL.getCol()))
1244 DL = MergedDL;
1245 TII->insertBranch(*NMBB, Succ, nullptr, Cond, DL);
1246 }
1247
1248 // Fix PHI nodes in Succ so they refer to NMBB instead of this.
1249 Succ->replacePhiUsesWith(this, NMBB);
1250
1251 // Inherit live-ins from the successor
1252 for (const auto &LI : Succ->liveins())
1253 NMBB->addLiveIn(LI);
1254
1255 // Update LiveVariables.
1257 if (LV) {
1258 // Restore kills of virtual registers that were killed by the terminators.
1259 while (!KilledRegs.empty()) {
1260 Register Reg = KilledRegs.pop_back_val();
1261 for (instr_iterator I = instr_end(), E = instr_begin(); I != E;) {
1262 if (!(--I)->addRegisterKilled(Reg, TRI, /* AddIfNotFound= */ false))
1263 continue;
1264 if (Reg.isVirtual())
1265 LV->getVarInfo(Reg).Kills.push_back(&*I);
1266 LLVM_DEBUG(dbgs() << "Restored terminator kill: " << *I);
1267 break;
1268 }
1269 }
1270 // Update relevant live-through information.
1271 if (LiveInSets != nullptr)
1272 LV->addNewBlock(NMBB, this, Succ, *LiveInSets);
1273 else
1274 LV->addNewBlock(NMBB, this, Succ);
1275 }
1276
1277 if (LIS) {
1278 // After splitting the edge and updating SlotIndexes, live intervals may be
1279 // in one of two situations, depending on whether this block was the last in
1280 // the function. If the original block was the last in the function, all
1281 // live intervals will end prior to the beginning of the new split block. If
1282 // the original block was not at the end of the function, all live intervals
1283 // will extend to the end of the new split block.
1284
1285 bool isLastMBB =
1286 std::next(MachineFunction::iterator(NMBB)) == getParent()->end();
1287
1288 SlotIndex StartIndex = Indexes->getMBBEndIdx(this);
1289 SlotIndex PrevIndex = StartIndex.getPrevSlot();
1290 SlotIndex EndIndex = Indexes->getMBBEndIdx(NMBB);
1291
1292 // Find the registers used from NMBB in PHIs in Succ.
1293 SmallSet<Register, 8> PHISrcRegs;
1295 I = Succ->instr_begin(), E = Succ->instr_end();
1296 I != E && I->isPHI(); ++I) {
1297 for (unsigned ni = 1, ne = I->getNumOperands(); ni != ne; ni += 2) {
1298 if (I->getOperand(ni+1).getMBB() == NMBB) {
1299 MachineOperand &MO = I->getOperand(ni);
1300 Register Reg = MO.getReg();
1301 PHISrcRegs.insert(Reg);
1302 if (MO.isUndef())
1303 continue;
1304
1305 LiveInterval &LI = LIS->getInterval(Reg);
1306 VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
1307 assert(VNI &&
1308 "PHI sources should be live out of their predecessors.");
1309 LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
1310 for (auto &SR : LI.subranges())
1311 SR.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
1312 }
1313 }
1314 }
1315
1317 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
1319 if (PHISrcRegs.count(Reg) || !LIS->hasInterval(Reg))
1320 continue;
1321
1322 LiveInterval &LI = LIS->getInterval(Reg);
1323 if (!LI.liveAt(PrevIndex))
1324 continue;
1325
1326 bool isLiveOut = LI.liveAt(LIS->getMBBStartIdx(Succ));
1327 if (isLiveOut && isLastMBB) {
1328 VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
1329 assert(VNI && "LiveInterval should have VNInfo where it is live.");
1330 LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
1331 // Update subranges with live values
1332 for (auto &SR : LI.subranges()) {
1333 VNInfo *VNI = SR.getVNInfoAt(PrevIndex);
1334 if (VNI)
1335 SR.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
1336 }
1337 } else if (!isLiveOut && !isLastMBB) {
1338 LI.removeSegment(StartIndex, EndIndex);
1339 for (auto &SR : LI.subranges())
1340 SR.removeSegment(StartIndex, EndIndex);
1341 }
1342 }
1343
1344 // Update all intervals for registers whose uses may have been modified by
1345 // updateTerminator().
1346 LIS->repairIntervalsInRange(this, getFirstTerminator(), end(), UsedRegs);
1347 }
1348
1349 if (auto *MDT = GET_RESULT(MachineDominatorTree, getDomTree, ))
1350 MDT->recordSplitCriticalEdge(this, Succ, NMBB);
1351
1352 if (MachineLoopInfo *MLI = GET_RESULT(MachineLoop, getLI, Info))
1353 if (MachineLoop *TIL = MLI->getLoopFor(this)) {
1354 // If one or the other blocks were not in a loop, the new block is not
1355 // either, and thus LI doesn't need to be updated.
1356 if (MachineLoop *DestLoop = MLI->getLoopFor(Succ)) {
1357 if (TIL == DestLoop) {
1358 // Both in the same loop, the NMBB joins loop.
1359 DestLoop->addBasicBlockToLoop(NMBB, *MLI);
1360 } else if (TIL->contains(DestLoop)) {
1361 // Edge from an outer loop to an inner loop. Add to the outer loop.
1362 TIL->addBasicBlockToLoop(NMBB, *MLI);
1363 } else if (DestLoop->contains(TIL)) {
1364 // Edge from an inner loop to an outer loop. Add to the outer loop.
1365 DestLoop->addBasicBlockToLoop(NMBB, *MLI);
1366 } else {
1367 // Edge from two loops with no containment relation. Because these
1368 // are natural loops, we know that the destination block must be the
1369 // header of its loop (adding a branch into a loop elsewhere would
1370 // create an irreducible loop).
1371 assert(DestLoop->getHeader() == Succ &&
1372 "Should not create irreducible loops!");
1373 if (MachineLoop *P = DestLoop->getParentLoop())
1374 P->addBasicBlockToLoop(NMBB, *MLI);
1375 }
1376 }
1377 }
1378
1379 return NMBB;
1380}
1381
1383 const MachineBasicBlock *Succ) const {
1384 // Splitting the critical edge to a landing pad block is non-trivial. Don't do
1385 // it in this generic function.
1386 if (Succ->isEHPad())
1387 return false;
1388
1389 // Splitting the critical edge to a callbr's indirect block isn't advised.
1390 // Don't do it in this generic function.
1391 if (Succ->isInlineAsmBrIndirectTarget())
1392 return false;
1393
1394 const MachineFunction *MF = getParent();
1395 // Performance might be harmed on HW that implements branching using exec mask
1396 // where both sides of the branches are always executed.
1397 if (MF->getTarget().requiresStructuredCFG())
1398 return false;
1399
1400 // Do we have an Indirect jump with a jumptable that we can rewrite?
1401 int JTI = findJumpTableIndex(*this);
1402 if (JTI >= 0 && !jumpTableHasOtherUses(*MF, *this, JTI))
1403 return true;
1404
1405 // We may need to update this's terminator, but we can't do that if
1406 // analyzeBranch fails.
1408 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1410 // AnalyzeBanch should modify this, since we did not allow modification.
1411 if (TII->analyzeBranch(*const_cast<MachineBasicBlock *>(this), TBB, FBB, Cond,
1412 /*AllowModify*/ false))
1413 return false;
1414
1415 // Avoid bugpoint weirdness: A block may end with a conditional branch but
1416 // jumps to the same MBB is either case. We have duplicate CFG edges in that
1417 // case that we can't handle. Since this never happens in properly optimized
1418 // code, just skip those edges.
1419 if (TBB && TBB == FBB) {
1420 LLVM_DEBUG(dbgs() << "Won't split critical edge after degenerate "
1421 << printMBBReference(*this) << '\n');
1422 return false;
1423 }
1424 return true;
1425}
1426
1427/// Prepare MI to be removed from its bundle. This fixes bundle flags on MI's
1428/// neighboring instructions so the bundle won't be broken by removing MI.
1430 // Removing the first instruction in a bundle.
1431 if (MI->isBundledWithSucc() && !MI->isBundledWithPred())
1432 MI->unbundleFromSucc();
1433 // Removing the last instruction in a bundle.
1434 if (MI->isBundledWithPred() && !MI->isBundledWithSucc())
1435 MI->unbundleFromPred();
1436 // If MI is not bundled, or if it is internal to a bundle, the neighbor flags
1437 // are already fine.
1438}
1439
1443 return Insts.erase(I);
1444}
1445
1448 MI->clearFlag(MachineInstr::BundledPred);
1449 MI->clearFlag(MachineInstr::BundledSucc);
1450 return Insts.remove(MI);
1451}
1452
1455 assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
1456 "Cannot insert instruction with bundle flags");
1457 // Set the bundle flags when inserting inside a bundle.
1458 if (I != instr_end() && I->isBundledWithPred()) {
1459 MI->setFlag(MachineInstr::BundledPred);
1460 MI->setFlag(MachineInstr::BundledSucc);
1461 }
1462 return Insts.insert(I, MI);
1463}
1464
1465/// This method unlinks 'this' from the containing function, and returns it, but
1466/// does not delete it.
1468 assert(getParent() && "Not embedded in a function!");
1469 getParent()->remove(this);
1470 return this;
1471}
1472
1473/// This method unlinks 'this' from the containing function, and deletes it.
1475 assert(getParent() && "Not embedded in a function!");
1476 getParent()->erase(this);
1477}
1478
1479/// Given a machine basic block that branched to 'Old', change the code and CFG
1480/// so that it branches to 'New' instead.
1482 MachineBasicBlock *New) {
1483 assert(Old != New && "Cannot replace self with self!");
1484
1486 while (I != instr_begin()) {
1487 --I;
1488 if (!I->isTerminator()) break;
1489
1490 // Scan the operands of this machine instruction, replacing any uses of Old
1491 // with New.
1492 for (MachineOperand &MO : I->operands())
1493 if (MO.isMBB() && MO.getMBB() == Old)
1494 MO.setMBB(New);
1495 }
1496
1497 // Update the successor information.
1498 replaceSuccessor(Old, New);
1499}
1500
1502 MachineBasicBlock *New) {
1503 for (MachineInstr &MI : phis())
1504 for (unsigned i = 2, e = MI.getNumOperands() + 1; i != e; i += 2) {
1505 MachineOperand &MO = MI.getOperand(i);
1506 if (MO.getMBB() == Old)
1507 MO.setMBB(New);
1508 }
1509}
1510
1511/// Find the next valid DebugLoc starting at MBBI, skipping any debug
1512/// instructions. Return UnknownLoc if there is none.
1515 // Skip debug declarations, we don't want a DebugLoc from them.
1517 if (MBBI != instr_end())
1518 return MBBI->getDebugLoc();
1519 return {};
1520}
1521
1523 if (MBBI == instr_rend())
1524 return findDebugLoc(instr_begin());
1525 // Skip debug declarations, we don't want a DebugLoc from them.
1527 if (!MBBI->isDebugInstr())
1528 return MBBI->getDebugLoc();
1529 return {};
1530}
1531
1532/// Find the previous valid DebugLoc preceding MBBI, skipping any debug
1533/// instructions. Return UnknownLoc if there is none.
1535 if (MBBI == instr_begin())
1536 return {};
1537 // Skip debug instructions, we don't want a DebugLoc from them.
1539 if (!MBBI->isDebugInstr())
1540 return MBBI->getDebugLoc();
1541 return {};
1542}
1543
1545 if (MBBI == instr_rend())
1546 return {};
1547 // Skip debug declarations, we don't want a DebugLoc from them.
1549 if (MBBI != instr_rend())
1550 return MBBI->getDebugLoc();
1551 return {};
1552}
1553
1554/// Find and return the merged DebugLoc of the branch instructions of the block.
1555/// Return UnknownLoc if there is none.
1558 DebugLoc DL;
1559 auto TI = getFirstTerminator();
1560 while (TI != end() && !TI->isBranch())
1561 ++TI;
1562
1563 if (TI != end()) {
1564 DL = TI->getDebugLoc();
1565 for (++TI ; TI != end() ; ++TI)
1566 if (TI->isBranch())
1567 DL = DILocation::getMergedLocation(DL, TI->getDebugLoc());
1568 }
1569 return DL;
1570}
1571
1572/// Return probability of the edge from this block to MBB.
1575 if (Probs.empty())
1576 return BranchProbability(1, succ_size());
1577
1578 const auto &Prob = *getProbabilityIterator(Succ);
1579 if (Prob.isUnknown()) {
1580 // For unknown probabilities, collect the sum of all known ones, and evenly
1581 // ditribute the complemental of the sum to each unknown probability.
1582 unsigned KnownProbNum = 0;
1583 auto Sum = BranchProbability::getZero();
1584 for (const auto &P : Probs) {
1585 if (!P.isUnknown()) {
1586 Sum += P;
1587 KnownProbNum++;
1588 }
1589 }
1590 return Sum.getCompl() / (Probs.size() - KnownProbNum);
1591 } else
1592 return Prob;
1593}
1594
1595/// Set successor probability of a given iterator.
1597 BranchProbability Prob) {
1598 assert(!Prob.isUnknown());
1599 if (Probs.empty())
1600 return;
1601 *getProbabilityIterator(I) = Prob;
1602}
1603
1604/// Return probability iterator corresonding to the I successor iterator
1605MachineBasicBlock::const_probability_iterator
1606MachineBasicBlock::getProbabilityIterator(
1608 assert(Probs.size() == Successors.size() && "Async probability list!");
1609 const size_t index = std::distance(Successors.begin(), I);
1610 assert(index < Probs.size() && "Not a current successor!");
1611 return Probs.begin() + index;
1612}
1613
1614/// Return probability iterator corresonding to the I successor iterator.
1615MachineBasicBlock::probability_iterator
1616MachineBasicBlock::getProbabilityIterator(MachineBasicBlock::succ_iterator I) {
1617 assert(Probs.size() == Successors.size() && "Async probability list!");
1618 const size_t index = std::distance(Successors.begin(), I);
1619 assert(index < Probs.size() && "Not a current successor!");
1620 return Probs.begin() + index;
1621}
1622
1623/// Return whether (physical) register "Reg" has been <def>ined and not <kill>ed
1624/// as of just before "MI".
1625///
1626/// Search is localised to a neighborhood of
1627/// Neighborhood instructions before (searching for defs or kills) and N
1628/// instructions after (searching just for defs) MI.
1632 unsigned Neighborhood) const {
1633 unsigned N = Neighborhood;
1634
1635 // Try searching forwards from Before, looking for reads or defs.
1637 for (; I != end() && N > 0; ++I) {
1638 if (I->isDebugOrPseudoInstr())
1639 continue;
1640
1641 --N;
1642
1644
1645 // Register is live when we read it here.
1646 if (Info.Read)
1647 return LQR_Live;
1648 // Register is dead if we can fully overwrite or clobber it here.
1649 if (Info.FullyDefined || Info.Clobbered)
1650 return LQR_Dead;
1651 }
1652
1653 // If we reached the end, it is safe to clobber Reg at the end of a block of
1654 // no successor has it live in.
1655 if (I == end()) {
1656 for (MachineBasicBlock *S : successors()) {
1657 for (const MachineBasicBlock::RegisterMaskPair &LI : S->liveins()) {
1658 if (TRI->regsOverlap(LI.PhysReg, Reg))
1659 return LQR_Live;
1660 }
1661 }
1662
1663 return LQR_Dead;
1664 }
1665
1666
1667 N = Neighborhood;
1668
1669 // Start by searching backwards from Before, looking for kills, reads or defs.
1671 // If this is the first insn in the block, don't search backwards.
1672 if (I != begin()) {
1673 do {
1674 --I;
1675
1676 if (I->isDebugOrPseudoInstr())
1677 continue;
1678
1679 --N;
1680
1682
1683 // Defs happen after uses so they take precedence if both are present.
1684
1685 // Register is dead after a dead def of the full register.
1686 if (Info.DeadDef)
1687 return LQR_Dead;
1688 // Register is (at least partially) live after a def.
1689 if (Info.Defined) {
1690 if (!Info.PartialDeadDef)
1691 return LQR_Live;
1692 // As soon as we saw a partial definition (dead or not),
1693 // we cannot tell if the value is partial live without
1694 // tracking the lanemasks. We are not going to do this,
1695 // so fall back on the remaining of the analysis.
1696 break;
1697 }
1698 // Register is dead after a full kill or clobber and no def.
1699 if (Info.Killed || Info.Clobbered)
1700 return LQR_Dead;
1701 // Register must be live if we read it.
1702 if (Info.Read)
1703 return LQR_Live;
1704
1705 } while (I != begin() && N > 0);
1706 }
1707
1708 // If all the instructions before this in the block are debug instructions,
1709 // skip over them.
1710 while (I != begin() && std::prev(I)->isDebugOrPseudoInstr())
1711 --I;
1712
1713 // Did we get to the start of the block?
1714 if (I == begin()) {
1715 // If so, the register's state is definitely defined by the live-in state.
1717 if (TRI->regsOverlap(LI.PhysReg, Reg))
1718 return LQR_Live;
1719
1720 return LQR_Dead;
1721 }
1722
1723 // At this point we have no idea of the liveness of the register.
1724 return LQR_Unknown;
1725}
1726
1727const uint32_t *
1729 // EH funclet entry does not preserve any registers.
1730 return isEHFuncletEntry() ? TRI->getNoPreservedMask() : nullptr;
1731}
1732
1733const uint32_t *
1735 // If we see a return block with successors, this must be a funclet return,
1736 // which does not preserve any registers. If there are no successors, we don't
1737 // care what kind of return it is, putting a mask after it is a no-op.
1738 return isReturnBlock() && !succ_empty() ? TRI->getNoPreservedMask() : nullptr;
1739}
1740
1742 LiveIns.clear();
1743}
1744
1746 std::vector<RegisterMaskPair> &OldLiveIns) {
1747 assert(OldLiveIns.empty() && "Vector must be empty");
1748 std::swap(LiveIns, OldLiveIns);
1749}
1750
1752 assert(getParent()->getProperties().hasProperty(
1754 "Liveness information is accurate");
1755 return LiveIns.begin();
1756}
1757
1759 const MachineFunction &MF = *getParent();
1762 "Liveness information is accurate");
1763
1764 const TargetLowering &TLI = *MF.getSubtarget().getTargetLowering();
1765 MCPhysReg ExceptionPointer = 0, ExceptionSelector = 0;
1766 if (MF.getFunction().hasPersonalityFn()) {
1767 auto PersonalityFn = MF.getFunction().getPersonalityFn();
1768 ExceptionPointer = TLI.getExceptionPointerRegister(PersonalityFn);
1769 ExceptionSelector = TLI.getExceptionSelectorRegister(PersonalityFn);
1770 }
1771
1772 return liveout_iterator(*this, ExceptionPointer, ExceptionSelector, false);
1773}
1774
1776 unsigned Cntr = 0;
1777 auto R = instructionsWithoutDebug(begin(), end());
1778 for (auto I = R.begin(), E = R.end(); I != E; ++I) {
1779 if (++Cntr > Limit)
1780 return true;
1781 }
1782 return false;
1783}
1784
1786const MBBSectionID
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
MachineBasicBlock MachineBasicBlock::iterator MBBI
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:537
#define LLVM_DEBUG(X)
Definition: Debug.h:101
std::string Name
const HexagonInstrInfo * TII
IRTranslator LLVM IR MI
This file implements the LivePhysRegs utility for tracking liveness of physical registers.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
#define GET_RESULT(RESULT, GETTER, INFIX)
static bool jumpTableHasOtherUses(const MachineFunction &MF, const MachineBasicBlock &IgnoreMBB, int JumpTableIndex)
static void unbundleSingleMI(MachineInstr *MI)
Prepare MI to be removed from its bundle.
static int findJumpTableIndex(const MachineBasicBlock &MBB)
static cl::opt< bool > PrintSlotIndexes("print-slotindexes", cl::desc("When printing machine IR, annotate instructions and blocks with " "SlotIndexes when available"), cl::init(true), cl::Hidden)
unsigned const TargetRegisterInfo * TRI
uint64_t IntrinsicInst * II
#define P(N)
uint32_t Number
Definition: Profile.cpp:47
const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool isLiveOut(const MachineBasicBlock &MBB, unsigned Reg)
This file contains some templates that are useful if you are working with the STL at all.
raw_pwrite_stream & OS
This file contains some functions that are useful when dealing with strings.
This file describes how to lower LLVM code to machine code.
SlotIndexUpdateDelegate(MachineFunction &MF, SlotIndexes *Indexes)
void MF_HandleRemoval(MachineInstr &MI) override
Callback before a removal. This should not modify the MI directly.
void MF_HandleInsertion(MachineInstr &MI) override
Callback after an insertion. This should not modify the MI directly.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:253
LLVM Basic Block Representation.
Definition: BasicBlock.h:61
static uint32_t getDenominator()
static BranchProbability getUnknown()
uint32_t getNumerator() const
static BranchProbability getZero()
static DILocation * getMergedLocation(DILocation *LocA, DILocation *LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
A debug info location.
Definition: DebugLoc.h:33
unsigned getLine() const
Definition: DebugLoc.cpp:24
unsigned getCol() const
Definition: DebugLoc.cpp:29
bool hasPersonalityFn() const
Check whether this function has a personality function.
Definition: Function.h:903
Constant * getPersonalityFn() const
Get the personality function associated with this function.
Definition: Function.cpp:1993
unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const override
Remove the branching code at the end of the specific MBB.
bool isPredicated(const MachineInstr &MI) const override
Returns true if the instruction is already predicated.
bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify) const override
Analyze the branching code at the end of MBB, returning true if it cannot be understood (e....
bool reverseBranchCondition(SmallVectorImpl< MachineOperand > &Cond) const override
Reverses the branch condition of the specified condition list, returning false on success and true if...
unsigned insertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB, MachineBasicBlock *FBB, ArrayRef< MachineOperand > Cond, const DebugLoc &DL, int *BytesAdded=nullptr) const override
Insert branch code into the end of the specified MachineBasicBlock.
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:687
iterator_range< subrange_iterator > subranges()
Definition: LiveInterval.h:782
void repairIntervalsInRange(MachineBasicBlock *MBB, MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, ArrayRef< Register > OrigRegs)
Update live intervals for instructions in a range of iterators.
bool hasInterval(Register Reg) const
SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const
Return the first index in the given basic block.
void insertMBBInMaps(MachineBasicBlock *MBB)
LiveInterval & getInterval(Register Reg)
A set of physical registers with utility functions to track liveness when walking backward/forward th...
Definition: LivePhysRegs.h:52
void stepBackward(const MachineInstr &MI)
Simulates liveness when stepping backwards over an instruction(bundle).
void init(const TargetRegisterInfo &TRI)
(re-)initializes and clears the set.
Definition: LivePhysRegs.h:70
void addLiveOuts(const MachineBasicBlock &MBB)
Adds all live-out registers of basic block MBB.
iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
bool liveAt(SlotIndex index) const
Definition: LiveInterval.h:401
void removeSegment(SlotIndex Start, SlotIndex End, bool RemoveDeadValNo=false)
Remove the specified interval from this live range.
VNInfo * getVNInfoAt(SlotIndex Idx) const
getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
Definition: LiveInterval.h:421
VarInfo & getVarInfo(Register Reg)
getVarInfo - Return the VarInfo structure for the specified VIRTUAL register.
void addNewBlock(MachineBasicBlock *BB, MachineBasicBlock *DomBB, MachineBasicBlock *SuccBB)
addNewBlock - Add a new basic block BB between DomBB and SuccBB.
Context object for machine code objects.
Definition: MCContext.h:83
MCSymbol * createBlockSymbol(const Twine &Name, bool AlwaysEmit=false)
Get or create a symbol for a basic block.
Definition: MCContext.cpp:325
MCSymbol * getOrCreateSymbol(const Twine &Name)
Lookup the symbol inside with the specified Name.
Definition: MCContext.cpp:213
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:33
MCSymbol - Instances of this class represent a symbol name in the MC file, and MCSymbols are created ...
Definition: MCSymbol.h:41
bool isInlineAsmBrIndirectTarget() const
Returns true if this is the indirect dest of an INLINEASM_BR.
DebugLoc rfindPrevDebugLoc(reverse_instr_iterator MBBI)
Has exact same behavior as findPrevDebugLoc (it also searches towards the beginning of this MBB) exce...
void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB)
Transfers all the successors, as in transferSuccessors, and update PHI operands in the successor bloc...
void normalizeSuccProbs()
Normalize probabilities of all successors so that the sum of them becomes one.
livein_iterator livein_end() const
iterator getFirstTerminatorForward()
Finds the first terminator in a block by scanning forward.
bool isEHPad() const
Returns true if the block is a landing pad.
void replacePhiUsesWith(MachineBasicBlock *Old, MachineBasicBlock *New)
Update all phi nodes in this basic block to refer to basic block New instead of basic block Old.
MachineInstr * remove_instr(MachineInstr *I)
Remove the possibly bundled instruction from the instruction list without deleting it.
instr_iterator instr_begin()
MachineInstrBundleIterator< const MachineInstr > const_iterator
MCSymbol * getSymbol() const
Return the MCSymbol for this basic block.
SmallVectorImpl< MachineBasicBlock * >::const_iterator const_succ_iterator
MCSymbol * getEHCatchretSymbol() const
Return the EHCatchret Symbol for this basic block.
void moveBefore(MachineBasicBlock *NewAfter)
Move 'this' block before or after the specified block.
void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New)
Replace successor OLD with NEW and update probability info.
MachineBasicBlock * getFallThrough(bool JumpToFallThrough=true)
Return the fallthrough block if the block can implicitly transfer control to the block after it by fa...
void transferSuccessors(MachineBasicBlock *FromMBB)
Transfers all the successors from MBB to this machine basic block (i.e., copies all the successors Fr...
bool hasLabelMustBeEmitted() const
Test whether this block must have its label emitted.
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
BranchProbability getSuccProbability(const_succ_iterator Succ) const
Return probability of the edge from this block to MBB.
iterator_range< livein_iterator > liveins() const
iterator_range< iterator > phis()
Returns a range that iterates over the phis in the basic block.
reverse_instr_iterator instr_rbegin()
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
iterator SkipPHIsAndLabels(iterator I)
Return the first instruction in MBB after I that is not a PHI or a label.
void addSuccessorWithoutProb(MachineBasicBlock *Succ)
Add Succ as a successor of this MachineBasicBlock.
bool hasName() const
Check if there is a name of corresponding LLVM basic block.
void setCallFrameSize(unsigned N)
Set the call frame size on entry to this basic block.
std::optional< UniqueBBID > getBBID() const
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
void splitSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New, bool NormalizeSuccProbs=false)
Split the old successor into old plus new and updates the probability info.
@ PrintNameIr
Add IR name where available.
@ PrintNameAttributes
Print attributes.
void updateTerminator(MachineBasicBlock *PreviousLayoutSuccessor)
Update the terminator instructions in block to account for changes to block layout which may have bee...
const MachineBasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor.
iterator SkipPHIsLabelsAndDebug(iterator I, Register Reg=Register(), bool SkipPseudoOp=true)
Return the first instruction in MBB after I that is not a PHI, label or debug.
bool isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll()) const
Return true if the specified register is in the live in set.
bool canFallThrough()
Return true if the block can implicitly transfer control to the block after it by falling off the end...
void setSuccProbability(succ_iterator I, BranchProbability Prob)
Set successor probability of a given iterator.
iterator getFirstNonDebugInstr(bool SkipPseudoOp=true)
Returns an iterator to the first non-debug instruction in the basic block, or end().
void printAsOperand(raw_ostream &OS, bool PrintType=true) const
void validateSuccProbs() const
Validate successors' probabilities and check if the sum of them is approximate one.
bool isIRBlockAddressTaken() const
Test whether this block is the target of an IR BlockAddress.
LiveInVector::const_iterator livein_iterator
MCSymbol * getEndSymbol() const
Returns the MCSymbol marking the end of this basic block.
void clearLiveIns()
Clear live in list.
bool isEHFuncletEntry() const
Returns true if this is the entry block of an EH funclet.
LivenessQueryResult computeRegisterLiveness(const TargetRegisterInfo *TRI, MCRegister Reg, const_iterator Before, unsigned Neighborhood=10) const
Return whether (physical) register Reg has been defined and not killed as of just before Before.
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
livein_iterator livein_begin() const
unsigned succ_size() const
bool isReturnBlock() const
Convenience function that returns true if the block ends in a return instruction.
const uint32_t * getBeginClobberMask(const TargetRegisterInfo *TRI) const
Get the clobber mask for the start of this basic block.
MBBSectionID getSectionID() const
Returns the section ID of this basic block.
bool isEntryBlock() const
Returns true if this is the entry block of the function.
void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
void copySuccessor(const MachineBasicBlock *Orig, succ_iterator I)
Copy a successor (and any probability info) from original block to this block's.
SmallVectorImpl< MachineBasicBlock * >::iterator succ_iterator
BasicBlock * getAddressTakenIRBlock() const
Retrieves the BasicBlock which corresponds to this MachineBasicBlock.
void sortUniqueLiveIns()
Sorts and uniques the LiveIns vector.
const MachineBasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
liveout_iterator liveout_begin() const
Iterator scanning successor basic blocks' liveins to determine the registers potentially live at the ...
void removeSuccessor(MachineBasicBlock *Succ, bool NormalizeSuccProbs=false)
Remove successor from the successors list of this MachineBasicBlock.
iterator getFirstNonPHI()
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
bool isPredecessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a predecessor of this block.
DebugLoc rfindDebugLoc(reverse_instr_iterator MBBI)
Has exact same behavior as findDebugLoc (it also searches towards the end of this MBB) except that th...
void print(raw_ostream &OS, const SlotIndexes *=nullptr, bool IsStandalone=true) const
reverse_instr_iterator instr_rend()
DebugLoc findDebugLoc(instr_iterator MBBI)
Find the next valid DebugLoc starting at MBBI, skipping any debug instructions.
Instructions::iterator instr_iterator
iterator getLastNonDebugInstr(bool SkipPseudoOp=true)
Returns an iterator to the last non-debug instruction in the basic block, or end().
void ReplaceUsesOfBlockWith(MachineBasicBlock *Old, MachineBasicBlock *New)
Given a machine basic block that branched to 'Old', change the code and CFG so that it branches to 'N...
bool isLayoutSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB will be emitted immediately after this block, such that if this bloc...
DebugLoc findPrevDebugLoc(instr_iterator MBBI)
Find the previous valid DebugLoc preceding MBBI, skipping any debug instructions.
MachineBasicBlock * splitAt(MachineInstr &SplitInst, bool UpdateLiveIns=true, LiveIntervals *LIS=nullptr)
Split a basic block into 2 pieces at SplitPoint.
void eraseFromParent()
This method unlinks 'this' from the containing function and deletes it.
instr_iterator instr_end()
void addLiveIn(MCRegister PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
std::string getFullName() const
Return a formatted string to identify this block and its parent function.
bool isBeginSection() const
Returns true if this block begins any section.
unsigned getCallFrameSize() const
Return the call frame size on entry to this basic block.
DebugLoc findBranchDebugLoc()
Find and return the merged DebugLoc of the branch instructions of the block.
iterator_range< succ_iterator > successors()
instr_iterator getFirstInstrTerminator()
Same getFirstTerminator but it ignores bundles and return an instr_iterator instead.
reverse_iterator rbegin()
bool isMachineBlockAddressTaken() const
Test whether this block is used as something other than the target of a terminator,...
void printName(raw_ostream &os, unsigned printNameFlags=PrintNameIr, ModuleSlotTracker *moduleSlotTracker=nullptr) const
Print the basic block's name as:
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
iterator_range< pred_iterator > predecessors()
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...
Align getAlignment() const
Return alignment of the basic block.
MachineBasicBlock * SplitCriticalEdge(MachineBasicBlock *Succ, Pass &P, std::vector< SparseBitVector<> > *LiveInSets=nullptr)
Split the critical edge from this block to the given successor block, and return the newly created bl...
bool canSplitCriticalEdge(const MachineBasicBlock *Succ) const
Check if the edge between this block and the given successor Succ, can be split.
bool isLegalToHoistInto() const
Returns true if it is legal to hoist instructions into this block.
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
bool mayHaveInlineAsmBr() const
Returns true if this block may have an INLINEASM_BR (overestimate, by checking if any of the successo...
void removeLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll())
Remove the specified register from the live in set.
LivenessQueryResult
Possible outcome of a register liveness query to computeRegisterLiveness()
@ LQR_Dead
Register is known to be fully dead.
@ LQR_Live
Register is known to be (at least partially) live.
@ LQR_Unknown
Register liveness not decidable from local neighborhood.
void moveAfter(MachineBasicBlock *NewBefore)
const uint32_t * getEndClobberMask(const TargetRegisterInfo *TRI) const
Get the clobber mask for the end of the basic block.
bool sizeWithoutDebugLargerThan(unsigned Limit) const
MachineBasicBlock * removeFromParent()
This method unlinks 'this' from the containing function, and returns it, but does not delete it.
Instructions::reverse_iterator reverse_instr_iterator
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
bool hasProperty(Property P) const
unsigned addToMBBNumbering(MachineBasicBlock *MBB)
Adds the MBB to the internal numbering.
unsigned getFunctionNumber() const
getFunctionNumber - Return a unique ID for the current function.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
bool hasBBSections() const
Returns true if this function has basic block sections enabled.
MCContext & getContext() const
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
void resetDelegate(Delegate *delegate)
Reset the currently registered delegate - otherwise assert.
Function & getFunction()
Return the LLVM function that this machine code represents.
const LLVMTargetMachine & getTarget() const
getTarget - Return the target machine this machine code is compiled with
void remove(iterator MBBI)
const MachineFunctionProperties & getProperties() const
Get the function properties.
void setDelegate(Delegate *delegate)
Set the delegate.
const MachineJumpTableInfo * getJumpTableInfo() const
getJumpTableInfo - Return the jump table info object for the current function.
void splice(iterator InsertPt, iterator MBBI)
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *BB=nullptr, std::optional< UniqueBBID > BBID=std::nullopt)
CreateMachineBasicBlock - Allocate a new MachineBasicBlock.
void erase(iterator MBBI)
void insert(iterator MBBI, MachineBasicBlock *MBB)
BasicBlockListType::const_iterator const_iterator
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
reverse_iterator getReverse() const
Get a reverse iterator to the same node.
Representation of each machine instruction.
Definition: MachineInstr.h:69
bool ReplaceMBBInJumpTable(unsigned Idx, MachineBasicBlock *Old, MachineBasicBlock *New)
ReplaceMBBInJumpTable - If Old is a target of the jump tables, update the jump table to branch to New...
const std::vector< MachineJumpTableEntry > & getJumpTables() const
MachineOperand class - Representation of each machine instruction operand.
MachineBasicBlock * getMBB() const
void setMBB(MachineBasicBlock *MBB)
Register getReg() const
getReg - Returns the register number.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Manage lifetime of a slot tracker for printing IR.
int getLocalSlot(const Value *V)
Return the slot number of the specified local value.
Definition: AsmWriter.cpp:917
void incorporateFunction(const Function &F)
Incorporate the given function.
Definition: AsmWriter.cpp:903
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:94
virtual void print(raw_ostream &OS, const Module *M) const
print - Print out the internal state of the pass.
Definition: Pass.cpp:130
Simple wrapper around std::function<void(raw_ostream&)>.
Definition: Printable.h:38
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
static Register index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
Definition: Register.h:84
static constexpr bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:65
bool remove(const value_type &X)
Remove an item from the set vector.
Definition: SetVector.h:188
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:162
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:65
SlotIndex getPrevSlot() const
Returns the previous slot in the index list.
Definition: SlotIndexes.h:272
SlotIndexes pass.
Definition: SlotIndexes.h:297
SlotIndex insertMachineInstrInMaps(MachineInstr &MI, bool Late=false)
Insert the given machine instruction into the mapping.
Definition: SlotIndexes.h:531
void removeMachineInstrFromMaps(MachineInstr &MI, bool AllowBundled=false)
Removes machine instruction (bundle) MI from the mapping.
void insertMBBInMaps(MachineBasicBlock *mbb)
Add the given MachineBasicBlock into the maps.
Definition: SlotIndexes.h:606
SlotIndex getMBBEndIdx(unsigned Num) const
Returns the last index in the given basic block number.
Definition: SlotIndexes.h:470
SlotIndex getInstructionIndex(const MachineInstr &MI, bool IgnoreBundle=false) const
Returns the base index for the given instruction.
Definition: SlotIndexes.h:379
SlotIndex getMBBStartIdx(unsigned Num) const
Returns the first index in the given basic block number.
Definition: SlotIndexes.h:460
bool hasIndex(const MachineInstr &instr) const
Returns true if the given machine instr is mapped to an index, otherwise returns false.
Definition: SlotIndexes.h:374
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:370
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:166
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:179
SmallString - A SmallString is just a SmallVector with methods and accessors that make it work better...
Definition: SmallString.h:26
bool empty() const
Definition: SmallVector.h:95
void push_back(const T &Elt)
Definition: SmallVector.h:427
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1210
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
TargetInstrInfo - Interface to description of machine instruction set.
virtual Register getExceptionPointerRegister(const Constant *PersonalityFn) const
If a physical register, this returns the register that receives the exception address on entry to an ...
virtual Register getExceptionSelectorRegister(const Constant *PersonalityFn) const
If a physical register, this returns the register that receives the exception typeid on entry to a la...
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
bool requiresStructuredCFG() const
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
virtual const TargetInstrInfo * getInstrInfo() const
virtual const TargetLowering * getTargetLowering() const
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
VNInfo - Value Number Information.
Definition: LiveInterval.h:53
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
MachineBasicBlock * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:353
iterator erase(iterator where)
Definition: ilist.h:204
pointer remove(iterator &IT)
Definition: ilist.h:188
iterator insert(iterator where, pointer New)
Definition: ilist.h:165
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
A raw_ostream that writes to an SmallVector or SmallString.
Definition: raw_ostream.h:691
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ Kill
The last use of a register.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
IterT next_nodbg(IterT It, IterT End, bool SkipPseudoOp=true)
Increment It, then continue incrementing it while it points to a debug instruction.
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1742
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
PhysRegInfo AnalyzePhysRegInBundle(const MachineInstr &MI, Register Reg, const TargetRegisterInfo *TRI)
AnalyzePhysRegInBundle - Analyze how the current instruction or bundle uses a physical register.
Printable PrintLaneMask(LaneBitmask LaneMask)
Create Printable object to print LaneBitmasks on a raw_ostream.
Definition: LaneBitmask.h:92
IterT skipDebugInstructionsForward(IterT It, IterT End, bool SkipPseudoOp=true)
Increment It until it points to a non-debug instruction or to End and return the resulting iterator.
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1647
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
auto instructionsWithoutDebug(IterT It, IterT End, bool SkipPseudoOp=true)
Construct a range iterator which begins at It and moves forwards until End is reached,...
IterT skipDebugInstructionsBackward(IterT It, IterT Begin, bool SkipPseudoOp=true)
Decrement It until it points to a non-debug instruction or to Begin and return the resulting iterator...
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
Definition: Format.h:125
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:293
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1749
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1879
IterT prev_nodbg(IterT It, IterT Begin, bool SkipPseudoOp=true)
Decrement It, then continue decrementing it while it points to a debug instruction.
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
void addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs)
Adds registers contained in LiveRegs to the block live-in list of MBB.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:860
#define N
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
uint64_t value() const
This is a hole in the type system and should not be abused.
Definition: Alignment.h:85
This represents a simple continuous liveness interval for a value.
Definition: LiveInterval.h:162
bool removeKill(MachineInstr &MI)
removeKill - Delete a kill corresponding to the specified machine instruction.
Definition: LiveVariables.h:93
std::vector< MachineInstr * > Kills
Kills - List of MachineInstruction's which are the last use of this virtual register (kill it) in the...
Definition: LiveVariables.h:88
static const MBBSectionID ExceptionSectionID
static const MBBSectionID ColdSectionID
enum llvm::MBBSectionID::SectionType Type
Pair of physical register and lane mask.
MachineJumpTableEntry - One jump table in the jump table info.
std::vector< MachineBasicBlock * > MBBs
MBBs - The vector of basic blocks from which to create the jump table.
Information about how a physical register Reg is used by a set of operands.
static void deleteNode(NodeTy *V)
Definition: ilist.h:42
void removeNodeFromList(NodeTy *)
Definition: ilist.h:67
void addNodeToList(NodeTy *)
Definition: ilist.h:66
void transferNodesFromList(ilist_callback_traits &OldList, Iterator, Iterator)
Callback before transferring nodes to this list.
Definition: ilist.h:72
Template traits for intrusive list.
Definition: ilist.h:90