LLVM 19.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
1139 MachineBasicBlock *Succ, Pass &P,
1140 std::vector<SparseBitVector<>> *LiveInSets) {
1141 if (!canSplitCriticalEdge(Succ))
1142 return nullptr;
1143
1144 MachineFunction *MF = getParent();
1145 MachineBasicBlock *PrevFallthrough = getNextNode();
1146
1148 NMBB->setCallFrameSize(Succ->getCallFrameSize());
1149
1150 // Is there an indirect jump with jump table?
1151 bool ChangedIndirectJump = false;
1152 int JTI = findJumpTableIndex(*this);
1153 if (JTI >= 0) {
1155 MJTI.ReplaceMBBInJumpTable(JTI, Succ, NMBB);
1156 ChangedIndirectJump = true;
1157 }
1158
1159 MF->insert(std::next(MachineFunction::iterator(this)), NMBB);
1160 LLVM_DEBUG(dbgs() << "Splitting critical edge: " << printMBBReference(*this)
1161 << " -- " << printMBBReference(*NMBB) << " -- "
1162 << printMBBReference(*Succ) << '\n');
1163
1164 auto *LISWrapper = P.getAnalysisIfAvailable<LiveIntervalsWrapperPass>();
1165 LiveIntervals *LIS = LISWrapper ? &LISWrapper->getLIS() : nullptr;
1166 auto *SIWrapper = P.getAnalysisIfAvailable<SlotIndexesWrapperPass>();
1167 SlotIndexes *Indexes = SIWrapper ? &SIWrapper->getSI() : nullptr;
1168 if (LIS)
1169 LIS->insertMBBInMaps(NMBB);
1170 else if (Indexes)
1171 Indexes->insertMBBInMaps(NMBB);
1172
1173 // On some targets like Mips, branches may kill virtual registers. Make sure
1174 // that LiveVariables is properly updated after updateTerminator replaces the
1175 // terminators.
1176 auto *LVWrapper = P.getAnalysisIfAvailable<LiveVariablesWrapperPass>();
1177 LiveVariables *LV = LVWrapper ? &LVWrapper->getLV() : nullptr;
1178
1179 // Collect a list of virtual registers killed by the terminators.
1180 SmallVector<Register, 4> KilledRegs;
1181 if (LV)
1182 for (MachineInstr &MI :
1184 for (MachineOperand &MO : MI.all_uses()) {
1185 if (MO.getReg() == 0 || !MO.isKill() || MO.isUndef())
1186 continue;
1187 Register Reg = MO.getReg();
1188 if (Reg.isPhysical() || LV->getVarInfo(Reg).removeKill(MI)) {
1189 KilledRegs.push_back(Reg);
1190 LLVM_DEBUG(dbgs() << "Removing terminator kill: " << MI);
1191 MO.setIsKill(false);
1192 }
1193 }
1194 }
1195
1196 SmallVector<Register, 4> UsedRegs;
1197 if (LIS) {
1198 for (MachineInstr &MI :
1200 for (const MachineOperand &MO : MI.operands()) {
1201 if (!MO.isReg() || MO.getReg() == 0)
1202 continue;
1203
1204 Register Reg = MO.getReg();
1205 if (!is_contained(UsedRegs, Reg))
1206 UsedRegs.push_back(Reg);
1207 }
1208 }
1209 }
1210
1211 ReplaceUsesOfBlockWith(Succ, NMBB);
1212
1213 // Since we replaced all uses of Succ with NMBB, that should also be treated
1214 // as the fallthrough successor
1215 if (Succ == PrevFallthrough)
1216 PrevFallthrough = NMBB;
1217
1218 if (!ChangedIndirectJump) {
1219 SlotIndexUpdateDelegate SlotUpdater(*MF, Indexes);
1220 updateTerminator(PrevFallthrough);
1221 }
1222
1223 // Insert unconditional "jump Succ" instruction in NMBB if necessary.
1224 NMBB->addSuccessor(Succ);
1225 if (!NMBB->isLayoutSuccessor(Succ)) {
1226 SlotIndexUpdateDelegate SlotUpdater(*MF, Indexes);
1229
1230 // In original 'this' BB, there must be a branch instruction targeting at
1231 // Succ. We can not find it out since currently getBranchDestBlock was not
1232 // implemented for all targets. However, if the merged DL has column or line
1233 // number, the scope and non-zero column and line number is same with that
1234 // branch instruction so we can safely use it.
1235 DebugLoc DL, MergedDL = findBranchDebugLoc();
1236 if (MergedDL && (MergedDL.getLine() || MergedDL.getCol()))
1237 DL = MergedDL;
1238 TII->insertBranch(*NMBB, Succ, nullptr, Cond, DL);
1239 }
1240
1241 // Fix PHI nodes in Succ so they refer to NMBB instead of this.
1242 Succ->replacePhiUsesWith(this, NMBB);
1243
1244 // Inherit live-ins from the successor
1245 for (const auto &LI : Succ->liveins())
1246 NMBB->addLiveIn(LI);
1247
1248 // Update LiveVariables.
1250 if (LV) {
1251 // Restore kills of virtual registers that were killed by the terminators.
1252 while (!KilledRegs.empty()) {
1253 Register Reg = KilledRegs.pop_back_val();
1254 for (instr_iterator I = instr_end(), E = instr_begin(); I != E;) {
1255 if (!(--I)->addRegisterKilled(Reg, TRI, /* AddIfNotFound= */ false))
1256 continue;
1257 if (Reg.isVirtual())
1258 LV->getVarInfo(Reg).Kills.push_back(&*I);
1259 LLVM_DEBUG(dbgs() << "Restored terminator kill: " << *I);
1260 break;
1261 }
1262 }
1263 // Update relevant live-through information.
1264 if (LiveInSets != nullptr)
1265 LV->addNewBlock(NMBB, this, Succ, *LiveInSets);
1266 else
1267 LV->addNewBlock(NMBB, this, Succ);
1268 }
1269
1270 if (LIS) {
1271 // After splitting the edge and updating SlotIndexes, live intervals may be
1272 // in one of two situations, depending on whether this block was the last in
1273 // the function. If the original block was the last in the function, all
1274 // live intervals will end prior to the beginning of the new split block. If
1275 // the original block was not at the end of the function, all live intervals
1276 // will extend to the end of the new split block.
1277
1278 bool isLastMBB =
1279 std::next(MachineFunction::iterator(NMBB)) == getParent()->end();
1280
1281 SlotIndex StartIndex = Indexes->getMBBEndIdx(this);
1282 SlotIndex PrevIndex = StartIndex.getPrevSlot();
1283 SlotIndex EndIndex = Indexes->getMBBEndIdx(NMBB);
1284
1285 // Find the registers used from NMBB in PHIs in Succ.
1286 SmallSet<Register, 8> PHISrcRegs;
1288 I = Succ->instr_begin(), E = Succ->instr_end();
1289 I != E && I->isPHI(); ++I) {
1290 for (unsigned ni = 1, ne = I->getNumOperands(); ni != ne; ni += 2) {
1291 if (I->getOperand(ni+1).getMBB() == NMBB) {
1292 MachineOperand &MO = I->getOperand(ni);
1293 Register Reg = MO.getReg();
1294 PHISrcRegs.insert(Reg);
1295 if (MO.isUndef())
1296 continue;
1297
1298 LiveInterval &LI = LIS->getInterval(Reg);
1299 VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
1300 assert(VNI &&
1301 "PHI sources should be live out of their predecessors.");
1302 LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
1303 for (auto &SR : LI.subranges())
1304 SR.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
1305 }
1306 }
1307 }
1308
1310 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
1312 if (PHISrcRegs.count(Reg) || !LIS->hasInterval(Reg))
1313 continue;
1314
1315 LiveInterval &LI = LIS->getInterval(Reg);
1316 if (!LI.liveAt(PrevIndex))
1317 continue;
1318
1319 bool isLiveOut = LI.liveAt(LIS->getMBBStartIdx(Succ));
1320 if (isLiveOut && isLastMBB) {
1321 VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
1322 assert(VNI && "LiveInterval should have VNInfo where it is live.");
1323 LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
1324 // Update subranges with live values
1325 for (auto &SR : LI.subranges()) {
1326 VNInfo *VNI = SR.getVNInfoAt(PrevIndex);
1327 if (VNI)
1328 SR.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
1329 }
1330 } else if (!isLiveOut && !isLastMBB) {
1331 LI.removeSegment(StartIndex, EndIndex);
1332 for (auto &SR : LI.subranges())
1333 SR.removeSegment(StartIndex, EndIndex);
1334 }
1335 }
1336
1337 // Update all intervals for registers whose uses may have been modified by
1338 // updateTerminator().
1339 LIS->repairIntervalsInRange(this, getFirstTerminator(), end(), UsedRegs);
1340 }
1341
1342 if (auto *MDTWrapper =
1343 P.getAnalysisIfAvailable<MachineDominatorTreeWrapperPass>())
1344 MDTWrapper->getDomTree().recordSplitCriticalEdge(this, Succ, NMBB);
1345
1346 auto *MLIWrapper = P.getAnalysisIfAvailable<MachineLoopInfoWrapperPass>();
1347 if (MachineLoopInfo *MLI = MLIWrapper ? &MLIWrapper->getLI() : nullptr)
1348 if (MachineLoop *TIL = MLI->getLoopFor(this)) {
1349 // If one or the other blocks were not in a loop, the new block is not
1350 // either, and thus LI doesn't need to be updated.
1351 if (MachineLoop *DestLoop = MLI->getLoopFor(Succ)) {
1352 if (TIL == DestLoop) {
1353 // Both in the same loop, the NMBB joins loop.
1354 DestLoop->addBasicBlockToLoop(NMBB, *MLI);
1355 } else if (TIL->contains(DestLoop)) {
1356 // Edge from an outer loop to an inner loop. Add to the outer loop.
1357 TIL->addBasicBlockToLoop(NMBB, *MLI);
1358 } else if (DestLoop->contains(TIL)) {
1359 // Edge from an inner loop to an outer loop. Add to the outer loop.
1360 DestLoop->addBasicBlockToLoop(NMBB, *MLI);
1361 } else {
1362 // Edge from two loops with no containment relation. Because these
1363 // are natural loops, we know that the destination block must be the
1364 // header of its loop (adding a branch into a loop elsewhere would
1365 // create an irreducible loop).
1366 assert(DestLoop->getHeader() == Succ &&
1367 "Should not create irreducible loops!");
1368 if (MachineLoop *P = DestLoop->getParentLoop())
1369 P->addBasicBlockToLoop(NMBB, *MLI);
1370 }
1371 }
1372 }
1373
1374 return NMBB;
1375}
1376
1378 const MachineBasicBlock *Succ) const {
1379 // Splitting the critical edge to a landing pad block is non-trivial. Don't do
1380 // it in this generic function.
1381 if (Succ->isEHPad())
1382 return false;
1383
1384 // Splitting the critical edge to a callbr's indirect block isn't advised.
1385 // Don't do it in this generic function.
1386 if (Succ->isInlineAsmBrIndirectTarget())
1387 return false;
1388
1389 const MachineFunction *MF = getParent();
1390 // Performance might be harmed on HW that implements branching using exec mask
1391 // where both sides of the branches are always executed.
1392 if (MF->getTarget().requiresStructuredCFG())
1393 return false;
1394
1395 // Do we have an Indirect jump with a jumptable that we can rewrite?
1396 int JTI = findJumpTableIndex(*this);
1397 if (JTI >= 0 && !jumpTableHasOtherUses(*MF, *this, JTI))
1398 return true;
1399
1400 // We may need to update this's terminator, but we can't do that if
1401 // analyzeBranch fails.
1403 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1405 // AnalyzeBanch should modify this, since we did not allow modification.
1406 if (TII->analyzeBranch(*const_cast<MachineBasicBlock *>(this), TBB, FBB, Cond,
1407 /*AllowModify*/ false))
1408 return false;
1409
1410 // Avoid bugpoint weirdness: A block may end with a conditional branch but
1411 // jumps to the same MBB is either case. We have duplicate CFG edges in that
1412 // case that we can't handle. Since this never happens in properly optimized
1413 // code, just skip those edges.
1414 if (TBB && TBB == FBB) {
1415 LLVM_DEBUG(dbgs() << "Won't split critical edge after degenerate "
1416 << printMBBReference(*this) << '\n');
1417 return false;
1418 }
1419 return true;
1420}
1421
1422/// Prepare MI to be removed from its bundle. This fixes bundle flags on MI's
1423/// neighboring instructions so the bundle won't be broken by removing MI.
1425 // Removing the first instruction in a bundle.
1426 if (MI->isBundledWithSucc() && !MI->isBundledWithPred())
1427 MI->unbundleFromSucc();
1428 // Removing the last instruction in a bundle.
1429 if (MI->isBundledWithPred() && !MI->isBundledWithSucc())
1430 MI->unbundleFromPred();
1431 // If MI is not bundled, or if it is internal to a bundle, the neighbor flags
1432 // are already fine.
1433}
1434
1438 return Insts.erase(I);
1439}
1440
1443 MI->clearFlag(MachineInstr::BundledPred);
1444 MI->clearFlag(MachineInstr::BundledSucc);
1445 return Insts.remove(MI);
1446}
1447
1450 assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
1451 "Cannot insert instruction with bundle flags");
1452 // Set the bundle flags when inserting inside a bundle.
1453 if (I != instr_end() && I->isBundledWithPred()) {
1454 MI->setFlag(MachineInstr::BundledPred);
1455 MI->setFlag(MachineInstr::BundledSucc);
1456 }
1457 return Insts.insert(I, MI);
1458}
1459
1460/// This method unlinks 'this' from the containing function, and returns it, but
1461/// does not delete it.
1463 assert(getParent() && "Not embedded in a function!");
1464 getParent()->remove(this);
1465 return this;
1466}
1467
1468/// This method unlinks 'this' from the containing function, and deletes it.
1470 assert(getParent() && "Not embedded in a function!");
1471 getParent()->erase(this);
1472}
1473
1474/// Given a machine basic block that branched to 'Old', change the code and CFG
1475/// so that it branches to 'New' instead.
1477 MachineBasicBlock *New) {
1478 assert(Old != New && "Cannot replace self with self!");
1479
1481 while (I != instr_begin()) {
1482 --I;
1483 if (!I->isTerminator()) break;
1484
1485 // Scan the operands of this machine instruction, replacing any uses of Old
1486 // with New.
1487 for (MachineOperand &MO : I->operands())
1488 if (MO.isMBB() && MO.getMBB() == Old)
1489 MO.setMBB(New);
1490 }
1491
1492 // Update the successor information.
1493 replaceSuccessor(Old, New);
1494}
1495
1497 MachineBasicBlock *New) {
1498 for (MachineInstr &MI : phis())
1499 for (unsigned i = 2, e = MI.getNumOperands() + 1; i != e; i += 2) {
1500 MachineOperand &MO = MI.getOperand(i);
1501 if (MO.getMBB() == Old)
1502 MO.setMBB(New);
1503 }
1504}
1505
1506/// Find the next valid DebugLoc starting at MBBI, skipping any debug
1507/// instructions. Return UnknownLoc if there is none.
1510 // Skip debug declarations, we don't want a DebugLoc from them.
1512 if (MBBI != instr_end())
1513 return MBBI->getDebugLoc();
1514 return {};
1515}
1516
1518 if (MBBI == instr_rend())
1519 return findDebugLoc(instr_begin());
1520 // Skip debug declarations, we don't want a DebugLoc from them.
1522 if (!MBBI->isDebugInstr())
1523 return MBBI->getDebugLoc();
1524 return {};
1525}
1526
1527/// Find the previous valid DebugLoc preceding MBBI, skipping any debug
1528/// instructions. Return UnknownLoc if there is none.
1530 if (MBBI == instr_begin())
1531 return {};
1532 // Skip debug instructions, we don't want a DebugLoc from them.
1534 if (!MBBI->isDebugInstr())
1535 return MBBI->getDebugLoc();
1536 return {};
1537}
1538
1540 if (MBBI == instr_rend())
1541 return {};
1542 // Skip debug declarations, we don't want a DebugLoc from them.
1544 if (MBBI != instr_rend())
1545 return MBBI->getDebugLoc();
1546 return {};
1547}
1548
1549/// Find and return the merged DebugLoc of the branch instructions of the block.
1550/// Return UnknownLoc if there is none.
1553 DebugLoc DL;
1554 auto TI = getFirstTerminator();
1555 while (TI != end() && !TI->isBranch())
1556 ++TI;
1557
1558 if (TI != end()) {
1559 DL = TI->getDebugLoc();
1560 for (++TI ; TI != end() ; ++TI)
1561 if (TI->isBranch())
1562 DL = DILocation::getMergedLocation(DL, TI->getDebugLoc());
1563 }
1564 return DL;
1565}
1566
1567/// Return probability of the edge from this block to MBB.
1570 if (Probs.empty())
1571 return BranchProbability(1, succ_size());
1572
1573 const auto &Prob = *getProbabilityIterator(Succ);
1574 if (Prob.isUnknown()) {
1575 // For unknown probabilities, collect the sum of all known ones, and evenly
1576 // ditribute the complemental of the sum to each unknown probability.
1577 unsigned KnownProbNum = 0;
1578 auto Sum = BranchProbability::getZero();
1579 for (const auto &P : Probs) {
1580 if (!P.isUnknown()) {
1581 Sum += P;
1582 KnownProbNum++;
1583 }
1584 }
1585 return Sum.getCompl() / (Probs.size() - KnownProbNum);
1586 } else
1587 return Prob;
1588}
1589
1590/// Set successor probability of a given iterator.
1592 BranchProbability Prob) {
1593 assert(!Prob.isUnknown());
1594 if (Probs.empty())
1595 return;
1596 *getProbabilityIterator(I) = Prob;
1597}
1598
1599/// Return probability iterator corresonding to the I successor iterator
1600MachineBasicBlock::const_probability_iterator
1601MachineBasicBlock::getProbabilityIterator(
1603 assert(Probs.size() == Successors.size() && "Async probability list!");
1604 const size_t index = std::distance(Successors.begin(), I);
1605 assert(index < Probs.size() && "Not a current successor!");
1606 return Probs.begin() + index;
1607}
1608
1609/// Return probability iterator corresonding to the I successor iterator.
1610MachineBasicBlock::probability_iterator
1611MachineBasicBlock::getProbabilityIterator(MachineBasicBlock::succ_iterator I) {
1612 assert(Probs.size() == Successors.size() && "Async probability list!");
1613 const size_t index = std::distance(Successors.begin(), I);
1614 assert(index < Probs.size() && "Not a current successor!");
1615 return Probs.begin() + index;
1616}
1617
1618/// Return whether (physical) register "Reg" has been <def>ined and not <kill>ed
1619/// as of just before "MI".
1620///
1621/// Search is localised to a neighborhood of
1622/// Neighborhood instructions before (searching for defs or kills) and N
1623/// instructions after (searching just for defs) MI.
1627 unsigned Neighborhood) const {
1628 unsigned N = Neighborhood;
1629
1630 // Try searching forwards from Before, looking for reads or defs.
1632 for (; I != end() && N > 0; ++I) {
1633 if (I->isDebugOrPseudoInstr())
1634 continue;
1635
1636 --N;
1637
1639
1640 // Register is live when we read it here.
1641 if (Info.Read)
1642 return LQR_Live;
1643 // Register is dead if we can fully overwrite or clobber it here.
1644 if (Info.FullyDefined || Info.Clobbered)
1645 return LQR_Dead;
1646 }
1647
1648 // If we reached the end, it is safe to clobber Reg at the end of a block of
1649 // no successor has it live in.
1650 if (I == end()) {
1651 for (MachineBasicBlock *S : successors()) {
1652 for (const MachineBasicBlock::RegisterMaskPair &LI : S->liveins()) {
1653 if (TRI->regsOverlap(LI.PhysReg, Reg))
1654 return LQR_Live;
1655 }
1656 }
1657
1658 return LQR_Dead;
1659 }
1660
1661
1662 N = Neighborhood;
1663
1664 // Start by searching backwards from Before, looking for kills, reads or defs.
1666 // If this is the first insn in the block, don't search backwards.
1667 if (I != begin()) {
1668 do {
1669 --I;
1670
1671 if (I->isDebugOrPseudoInstr())
1672 continue;
1673
1674 --N;
1675
1677
1678 // Defs happen after uses so they take precedence if both are present.
1679
1680 // Register is dead after a dead def of the full register.
1681 if (Info.DeadDef)
1682 return LQR_Dead;
1683 // Register is (at least partially) live after a def.
1684 if (Info.Defined) {
1685 if (!Info.PartialDeadDef)
1686 return LQR_Live;
1687 // As soon as we saw a partial definition (dead or not),
1688 // we cannot tell if the value is partial live without
1689 // tracking the lanemasks. We are not going to do this,
1690 // so fall back on the remaining of the analysis.
1691 break;
1692 }
1693 // Register is dead after a full kill or clobber and no def.
1694 if (Info.Killed || Info.Clobbered)
1695 return LQR_Dead;
1696 // Register must be live if we read it.
1697 if (Info.Read)
1698 return LQR_Live;
1699
1700 } while (I != begin() && N > 0);
1701 }
1702
1703 // If all the instructions before this in the block are debug instructions,
1704 // skip over them.
1705 while (I != begin() && std::prev(I)->isDebugOrPseudoInstr())
1706 --I;
1707
1708 // Did we get to the start of the block?
1709 if (I == begin()) {
1710 // If so, the register's state is definitely defined by the live-in state.
1712 if (TRI->regsOverlap(LI.PhysReg, Reg))
1713 return LQR_Live;
1714
1715 return LQR_Dead;
1716 }
1717
1718 // At this point we have no idea of the liveness of the register.
1719 return LQR_Unknown;
1720}
1721
1722const uint32_t *
1724 // EH funclet entry does not preserve any registers.
1725 return isEHFuncletEntry() ? TRI->getNoPreservedMask() : nullptr;
1726}
1727
1728const uint32_t *
1730 // If we see a return block with successors, this must be a funclet return,
1731 // which does not preserve any registers. If there are no successors, we don't
1732 // care what kind of return it is, putting a mask after it is a no-op.
1733 return isReturnBlock() && !succ_empty() ? TRI->getNoPreservedMask() : nullptr;
1734}
1735
1737 LiveIns.clear();
1738}
1739
1741 std::vector<RegisterMaskPair> &OldLiveIns) {
1742 assert(OldLiveIns.empty() && "Vector must be empty");
1743 std::swap(LiveIns, OldLiveIns);
1744}
1745
1747 assert(getParent()->getProperties().hasProperty(
1749 "Liveness information is accurate");
1750 return LiveIns.begin();
1751}
1752
1754 const MachineFunction &MF = *getParent();
1757 "Liveness information is accurate");
1758
1759 const TargetLowering &TLI = *MF.getSubtarget().getTargetLowering();
1760 MCPhysReg ExceptionPointer = 0, ExceptionSelector = 0;
1761 if (MF.getFunction().hasPersonalityFn()) {
1762 auto PersonalityFn = MF.getFunction().getPersonalityFn();
1763 ExceptionPointer = TLI.getExceptionPointerRegister(PersonalityFn);
1764 ExceptionSelector = TLI.getExceptionSelectorRegister(PersonalityFn);
1765 }
1766
1767 return liveout_iterator(*this, ExceptionPointer, ExceptionSelector, false);
1768}
1769
1771 unsigned Cntr = 0;
1772 auto R = instructionsWithoutDebug(begin(), end());
1773 for (auto I = R.begin(), E = R.end(); I != E; ++I) {
1774 if (++Cntr > Limit)
1775 return true;
1776 }
1777 return false;
1778}
1779
1781const 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
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.
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:868
Constant * getPersonalityFn() const
Get the personality function associated with this function.
Definition: Function.cpp:1963
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 insertMBBInMaps(MachineBasicBlock *MBB)
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
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.
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.
std::vector< MachineBasicBlock * >::const_iterator const_succ_iterator
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.
std::vector< MachineBasicBlock * >::iterator succ_iterator
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.
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...
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 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.
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
Analysis pass which computes a MachineDominatorTree.
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:916
void incorporateFunction(const Function &F)
Incorporate the given function.
Definition: AsmWriter.cpp:902
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 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:94
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
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
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