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 const StringRef Prefix = Ctx.getAsmInfo()->getPrivateLabelPrefix();
84 CachedMCSymbol = Ctx.getOrCreateSymbol(Twine(Prefix) + "BB" +
86 "_" + Twine(getNumber()));
87 }
88 }
89 return CachedMCSymbol;
90}
91
93 if (!CachedEHCatchretMCSymbol) {
94 const MachineFunction *MF = getParent();
95 SmallString<128> SymbolName;
96 raw_svector_ostream(SymbolName)
97 << "$ehgcr_" << MF->getFunctionNumber() << '_' << getNumber();
98 CachedEHCatchretMCSymbol = MF->getContext().getOrCreateSymbol(SymbolName);
99 }
100 return CachedEHCatchretMCSymbol;
101}
102
104 if (!CachedEndMCSymbol) {
105 const MachineFunction *MF = getParent();
106 MCContext &Ctx = MF->getContext();
107 auto Prefix = Ctx.getAsmInfo()->getPrivateLabelPrefix();
108 CachedEndMCSymbol = Ctx.getOrCreateSymbol(Twine(Prefix) + "BB_END" +
109 Twine(MF->getFunctionNumber()) +
110 "_" + Twine(getNumber()));
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->getName();
321 else
322 return StringRef("", 0);
323}
324
325/// Return a hopefully unique identifier for this block.
327 std::string Name;
328 if (getParent())
329 Name = (getParent()->getName() + ":").str();
330 if (getBasicBlock())
331 Name += getBasicBlock()->getName();
332 else
333 Name += ("BB" + Twine(getNumber())).str();
334 return Name;
335}
336
338 bool IsStandalone) const {
339 const MachineFunction *MF = getParent();
340 if (!MF) {
341 OS << "Can't print out MachineBasicBlock because parent MachineFunction"
342 << " is null\n";
343 return;
344 }
345 const Function &F = MF->getFunction();
346 const Module *M = F.getParent();
347 ModuleSlotTracker MST(M);
349 print(OS, MST, Indexes, IsStandalone);
350}
351
353 const SlotIndexes *Indexes,
354 bool IsStandalone) const {
355 const MachineFunction *MF = getParent();
356 if (!MF) {
357 OS << "Can't print out MachineBasicBlock because parent MachineFunction"
358 << " is null\n";
359 return;
360 }
361
362 if (Indexes && PrintSlotIndexes)
363 OS << Indexes->getMBBStartIdx(this) << '\t';
364
366 OS << ":\n";
367
369 const MachineRegisterInfo &MRI = MF->getRegInfo();
371 bool HasLineAttributes = false;
372
373 // Print the preds of this block according to the CFG.
374 if (!pred_empty() && IsStandalone) {
375 if (Indexes) OS << '\t';
376 // Don't indent(2), align with previous line attributes.
377 OS << "; predecessors: ";
378 ListSeparator LS;
379 for (auto *Pred : predecessors())
380 OS << LS << printMBBReference(*Pred);
381 OS << '\n';
382 HasLineAttributes = true;
383 }
384
385 if (!succ_empty()) {
386 if (Indexes) OS << '\t';
387 // Print the successors
388 OS.indent(2) << "successors: ";
389 ListSeparator LS;
390 for (auto I = succ_begin(), E = succ_end(); I != E; ++I) {
391 OS << LS << printMBBReference(**I);
392 if (!Probs.empty())
393 OS << '('
394 << format("0x%08" PRIx32, getSuccProbability(I).getNumerator())
395 << ')';
396 }
397 if (!Probs.empty() && IsStandalone) {
398 // Print human readable probabilities as comments.
399 OS << "; ";
400 ListSeparator LS;
401 for (auto I = succ_begin(), E = succ_end(); I != E; ++I) {
403 OS << LS << printMBBReference(**I) << '('
404 << format("%.2f%%",
405 rint(((double)BP.getNumerator() / BP.getDenominator()) *
406 100.0 * 100.0) /
407 100.0)
408 << ')';
409 }
410 }
411
412 OS << '\n';
413 HasLineAttributes = true;
414 }
415
416 if (!livein_empty() && MRI.tracksLiveness()) {
417 if (Indexes) OS << '\t';
418 OS.indent(2) << "liveins: ";
419
420 ListSeparator LS;
421 for (const auto &LI : liveins()) {
422 OS << LS << printReg(LI.PhysReg, TRI);
423 if (!LI.LaneMask.all())
424 OS << ":0x" << PrintLaneMask(LI.LaneMask);
425 }
426 HasLineAttributes = true;
427 }
428
429 if (HasLineAttributes)
430 OS << '\n';
431
432 bool IsInBundle = false;
433 for (const MachineInstr &MI : instrs()) {
434 if (Indexes && PrintSlotIndexes) {
435 if (Indexes->hasIndex(MI))
436 OS << Indexes->getInstructionIndex(MI);
437 OS << '\t';
438 }
439
440 if (IsInBundle && !MI.isInsideBundle()) {
441 OS.indent(2) << "}\n";
442 IsInBundle = false;
443 }
444
445 OS.indent(IsInBundle ? 4 : 2);
446 MI.print(OS, MST, IsStandalone, /*SkipOpers=*/false, /*SkipDebugLoc=*/false,
447 /*AddNewLine=*/false, &TII);
448
449 if (!IsInBundle && MI.getFlag(MachineInstr::BundledSucc)) {
450 OS << " {";
451 IsInBundle = true;
452 }
453 OS << '\n';
454 }
455
456 if (IsInBundle)
457 OS.indent(2) << "}\n";
458
459 if (IrrLoopHeaderWeight && IsStandalone) {
460 if (Indexes) OS << '\t';
461 OS.indent(2) << "; Irreducible loop header weight: " << *IrrLoopHeaderWeight
462 << '\n';
463 }
464}
465
466/// Print the basic block's name as:
467///
468/// bb.{number}[.{ir-name}] [(attributes...)]
469///
470/// The {ir-name} is only printed when the \ref PrintNameIr flag is passed
471/// (which is the default). If the IR block has no name, it is identified
472/// numerically using the attribute syntax as "(%ir-block.{ir-slot})".
473///
474/// When the \ref PrintNameAttributes flag is passed, additional attributes
475/// of the block are printed when set.
476///
477/// \param printNameFlags Combination of \ref PrintNameFlag flags indicating
478/// the parts to print.
479/// \param moduleSlotTracker Optional ModuleSlotTracker. This method will
480/// incorporate its own tracker when necessary to
481/// determine the block's IR name.
482void MachineBasicBlock::printName(raw_ostream &os, unsigned printNameFlags,
483 ModuleSlotTracker *moduleSlotTracker) const {
484 os << "bb." << getNumber();
485 bool hasAttributes = false;
486
487 auto PrintBBRef = [&](const BasicBlock *bb) {
488 os << "%ir-block.";
489 if (bb->hasName()) {
490 os << bb->getName();
491 } else {
492 int slot = -1;
493
494 if (moduleSlotTracker) {
495 slot = moduleSlotTracker->getLocalSlot(bb);
496 } else if (bb->getParent()) {
497 ModuleSlotTracker tmpTracker(bb->getModule(), false);
498 tmpTracker.incorporateFunction(*bb->getParent());
499 slot = tmpTracker.getLocalSlot(bb);
500 }
501
502 if (slot == -1)
503 os << "<ir-block badref>";
504 else
505 os << slot;
506 }
507 };
508
509 if (printNameFlags & PrintNameIr) {
510 if (const auto *bb = getBasicBlock()) {
511 if (bb->hasName()) {
512 os << '.' << bb->getName();
513 } else {
514 hasAttributes = true;
515 os << " (";
516 PrintBBRef(bb);
517 }
518 }
519 }
520
521 if (printNameFlags & PrintNameAttributes) {
523 os << (hasAttributes ? ", " : " (");
524 os << "machine-block-address-taken";
525 hasAttributes = true;
526 }
527 if (isIRBlockAddressTaken()) {
528 os << (hasAttributes ? ", " : " (");
529 os << "ir-block-address-taken ";
530 PrintBBRef(getAddressTakenIRBlock());
531 hasAttributes = true;
532 }
533 if (isEHPad()) {
534 os << (hasAttributes ? ", " : " (");
535 os << "landing-pad";
536 hasAttributes = true;
537 }
539 os << (hasAttributes ? ", " : " (");
540 os << "inlineasm-br-indirect-target";
541 hasAttributes = true;
542 }
543 if (isEHFuncletEntry()) {
544 os << (hasAttributes ? ", " : " (");
545 os << "ehfunclet-entry";
546 hasAttributes = true;
547 }
548 if (getAlignment() != Align(1)) {
549 os << (hasAttributes ? ", " : " (");
550 os << "align " << getAlignment().value();
551 hasAttributes = true;
552 }
553 if (getSectionID() != MBBSectionID(0)) {
554 os << (hasAttributes ? ", " : " (");
555 os << "bbsections ";
556 switch (getSectionID().Type) {
558 os << "Exception";
559 break;
561 os << "Cold";
562 break;
563 default:
564 os << getSectionID().Number;
565 }
566 hasAttributes = true;
567 }
568 if (getBBID().has_value()) {
569 os << (hasAttributes ? ", " : " (");
570 os << "bb_id " << getBBID()->BaseID;
571 if (getBBID()->CloneID != 0)
572 os << " " << getBBID()->CloneID;
573 hasAttributes = true;
574 }
575 if (CallFrameSize != 0) {
576 os << (hasAttributes ? ", " : " (");
577 os << "call-frame-size " << CallFrameSize;
578 hasAttributes = true;
579 }
580 }
581
582 if (hasAttributes)
583 os << ')';
584}
585
587 bool /*PrintType*/) const {
588 OS << '%';
589 printName(OS, 0);
590}
591
593 LiveInVector::iterator I = find_if(
594 LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
595 if (I == LiveIns.end())
596 return;
597
598 I->LaneMask &= ~LaneMask;
599 if (I->LaneMask.none())
600 LiveIns.erase(I);
601}
602
605 // Get non-const version of iterator.
606 LiveInVector::iterator LI = LiveIns.begin() + (I - LiveIns.begin());
607 return LiveIns.erase(LI);
608}
609
612 LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
613 return I != livein_end() && (I->LaneMask & LaneMask).any();
614}
615
617 llvm::sort(LiveIns,
618 [](const RegisterMaskPair &LI0, const RegisterMaskPair &LI1) {
619 return LI0.PhysReg < LI1.PhysReg;
620 });
621 // Liveins are sorted by physreg now we can merge their lanemasks.
622 LiveInVector::const_iterator I = LiveIns.begin();
623 LiveInVector::const_iterator J;
624 LiveInVector::iterator Out = LiveIns.begin();
625 for (; I != LiveIns.end(); ++Out, I = J) {
626 MCRegister PhysReg = I->PhysReg;
627 LaneBitmask LaneMask = I->LaneMask;
628 for (J = std::next(I); J != LiveIns.end() && J->PhysReg == PhysReg; ++J)
629 LaneMask |= J->LaneMask;
630 Out->PhysReg = PhysReg;
631 Out->LaneMask = LaneMask;
632 }
633 LiveIns.erase(Out, LiveIns.end());
634}
635
638 assert(getParent() && "MBB must be inserted in function");
639 assert(Register::isPhysicalRegister(PhysReg) && "Expected physreg");
640 assert(RC && "Register class is required");
641 assert((isEHPad() || this == &getParent()->front()) &&
642 "Only the entry block and landing pads can have physreg live ins");
643
644 bool LiveIn = isLiveIn(PhysReg);
648
649 // Look for an existing copy.
650 if (LiveIn)
651 for (;I != E && I->isCopy(); ++I)
652 if (I->getOperand(1).getReg() == PhysReg) {
653 Register VirtReg = I->getOperand(0).getReg();
654 if (!MRI.constrainRegClass(VirtReg, RC))
655 llvm_unreachable("Incompatible live-in register class.");
656 return VirtReg;
657 }
658
659 // No luck, create a virtual register.
660 Register VirtReg = MRI.createVirtualRegister(RC);
661 BuildMI(*this, I, DebugLoc(), TII.get(TargetOpcode::COPY), VirtReg)
662 .addReg(PhysReg, RegState::Kill);
663 if (!LiveIn)
664 addLiveIn(PhysReg);
665 return VirtReg;
666}
667
669 getParent()->splice(NewAfter->getIterator(), getIterator());
670}
671
673 getParent()->splice(++NewBefore->getIterator(), getIterator());
674}
675
678 if (TerminatorI == MBB.end())
679 return -1;
680 const MachineInstr &Terminator = *TerminatorI;
682 return TII->getJumpTableIndex(Terminator);
683}
684
686 MachineBasicBlock *PreviousLayoutSuccessor) {
687 LLVM_DEBUG(dbgs() << "Updating terminators on " << printMBBReference(*this)
688 << "\n");
689
691 // A block with no successors has no concerns with fall-through edges.
692 if (this->succ_empty())
693 return;
694
695 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
698 bool B = TII->analyzeBranch(*this, TBB, FBB, Cond);
699 (void) B;
700 assert(!B && "UpdateTerminators requires analyzable predecessors!");
701 if (Cond.empty()) {
702 if (TBB) {
703 // The block has an unconditional branch. If its successor is now its
704 // layout successor, delete the branch.
706 TII->removeBranch(*this);
707 } else {
708 // The block has an unconditional fallthrough, or the end of the block is
709 // unreachable.
710
711 // Unfortunately, whether the end of the block is unreachable is not
712 // immediately obvious; we must fall back to checking the successor list,
713 // and assuming that if the passed in block is in the succesor list and
714 // not an EHPad, it must be the intended target.
715 if (!PreviousLayoutSuccessor || !isSuccessor(PreviousLayoutSuccessor) ||
716 PreviousLayoutSuccessor->isEHPad())
717 return;
718
719 // If the unconditional successor block is not the current layout
720 // successor, insert a branch to jump to it.
721 if (!isLayoutSuccessor(PreviousLayoutSuccessor))
722 TII->insertBranch(*this, PreviousLayoutSuccessor, nullptr, Cond, DL);
723 }
724 return;
725 }
726
727 if (FBB) {
728 // The block has a non-fallthrough conditional branch. If one of its
729 // successors is its layout successor, rewrite it to a fallthrough
730 // conditional branch.
731 if (isLayoutSuccessor(TBB)) {
733 return;
734 TII->removeBranch(*this);
735 TII->insertBranch(*this, FBB, nullptr, Cond, DL);
736 } else if (isLayoutSuccessor(FBB)) {
737 TII->removeBranch(*this);
738 TII->insertBranch(*this, TBB, nullptr, Cond, DL);
739 }
740 return;
741 }
742
743 // We now know we're going to fallthrough to PreviousLayoutSuccessor.
744 assert(PreviousLayoutSuccessor);
745 assert(!PreviousLayoutSuccessor->isEHPad());
746 assert(isSuccessor(PreviousLayoutSuccessor));
747
748 if (PreviousLayoutSuccessor == TBB) {
749 // We had a fallthrough to the same basic block as the conditional jump
750 // targets. Remove the conditional jump, leaving an unconditional
751 // fallthrough or an unconditional jump.
752 TII->removeBranch(*this);
753 if (!isLayoutSuccessor(TBB)) {
754 Cond.clear();
755 TII->insertBranch(*this, TBB, nullptr, Cond, DL);
756 }
757 return;
758 }
759
760 // The block has a fallthrough conditional branch.
761 if (isLayoutSuccessor(TBB)) {
763 // We can't reverse the condition, add an unconditional branch.
764 Cond.clear();
765 TII->insertBranch(*this, PreviousLayoutSuccessor, nullptr, Cond, DL);
766 return;
767 }
768 TII->removeBranch(*this);
769 TII->insertBranch(*this, PreviousLayoutSuccessor, nullptr, Cond, DL);
770 } else if (!isLayoutSuccessor(PreviousLayoutSuccessor)) {
771 TII->removeBranch(*this);
772 TII->insertBranch(*this, TBB, PreviousLayoutSuccessor, Cond, DL);
773 }
774}
775
777#ifndef NDEBUG
778 int64_t Sum = 0;
779 for (auto Prob : Probs)
780 Sum += Prob.getNumerator();
781 // Due to precision issue, we assume that the sum of probabilities is one if
782 // the difference between the sum of their numerators and the denominator is
783 // no greater than the number of successors.
785 Probs.size() &&
786 "The sum of successors's probabilities exceeds one.");
787#endif // NDEBUG
788}
789
791 BranchProbability Prob) {
792 // Probability list is either empty (if successor list isn't empty, this means
793 // disabled optimization) or has the same size as successor list.
794 if (!(Probs.empty() && !Successors.empty()))
795 Probs.push_back(Prob);
796 Successors.push_back(Succ);
797 Succ->addPredecessor(this);
798}
799
801 // We need to make sure probability list is either empty or has the same size
802 // of successor list. When this function is called, we can safely delete all
803 // probability in the list.
804 Probs.clear();
805 Successors.push_back(Succ);
806 Succ->addPredecessor(this);
807}
808
811 bool NormalizeSuccProbs) {
812 succ_iterator OldI = llvm::find(successors(), Old);
813 assert(OldI != succ_end() && "Old is not a successor of this block!");
815 "New is already a successor of this block!");
816
817 // Add a new successor with equal probability as the original one. Note
818 // that we directly copy the probability using the iterator rather than
819 // getting a potentially synthetic probability computed when unknown. This
820 // preserves the probabilities as-is and then we can renormalize them and
821 // query them effectively afterward.
822 addSuccessor(New, Probs.empty() ? BranchProbability::getUnknown()
823 : *getProbabilityIterator(OldI));
824 if (NormalizeSuccProbs)
826}
827
829 bool NormalizeSuccProbs) {
830 succ_iterator I = find(Successors, Succ);
831 removeSuccessor(I, NormalizeSuccProbs);
832}
833
836 assert(I != Successors.end() && "Not a current successor!");
837
838 // If probability list is empty it means we don't use it (disabled
839 // optimization).
840 if (!Probs.empty()) {
841 probability_iterator WI = getProbabilityIterator(I);
842 Probs.erase(WI);
843 if (NormalizeSuccProbs)
845 }
846
847 (*I)->removePredecessor(this);
848 return Successors.erase(I);
849}
850
852 MachineBasicBlock *New) {
853 if (Old == New)
854 return;
855
857 succ_iterator NewI = E;
858 succ_iterator OldI = E;
859 for (succ_iterator I = succ_begin(); I != E; ++I) {
860 if (*I == Old) {
861 OldI = I;
862 if (NewI != E)
863 break;
864 }
865 if (*I == New) {
866 NewI = I;
867 if (OldI != E)
868 break;
869 }
870 }
871 assert(OldI != E && "Old is not a successor of this block");
872
873 // If New isn't already a successor, let it take Old's place.
874 if (NewI == E) {
875 Old->removePredecessor(this);
876 New->addPredecessor(this);
877 *OldI = New;
878 return;
879 }
880
881 // New is already a successor.
882 // Update its probability instead of adding a duplicate edge.
883 if (!Probs.empty()) {
884 auto ProbIter = getProbabilityIterator(NewI);
885 if (!ProbIter->isUnknown())
886 *ProbIter += *getProbabilityIterator(OldI);
887 }
888 removeSuccessor(OldI);
889}
890
893 if (!Orig->Probs.empty())
895 else
897}
898
899void MachineBasicBlock::addPredecessor(MachineBasicBlock *Pred) {
900 Predecessors.push_back(Pred);
901}
902
903void MachineBasicBlock::removePredecessor(MachineBasicBlock *Pred) {
904 pred_iterator I = find(Predecessors, Pred);
905 assert(I != Predecessors.end() && "Pred is not a predecessor of this block!");
906 Predecessors.erase(I);
907}
908
910 if (this == FromMBB)
911 return;
912
913 while (!FromMBB->succ_empty()) {
914 MachineBasicBlock *Succ = *FromMBB->succ_begin();
915
916 // If probability list is empty it means we don't use it (disabled
917 // optimization).
918 if (!FromMBB->Probs.empty()) {
919 auto Prob = *FromMBB->Probs.begin();
920 addSuccessor(Succ, Prob);
921 } else
923
924 FromMBB->removeSuccessor(Succ);
925 }
926}
927
928void
930 if (this == FromMBB)
931 return;
932
933 while (!FromMBB->succ_empty()) {
934 MachineBasicBlock *Succ = *FromMBB->succ_begin();
935 if (!FromMBB->Probs.empty()) {
936 auto Prob = *FromMBB->Probs.begin();
937 addSuccessor(Succ, Prob);
938 } else
940 FromMBB->removeSuccessor(Succ);
941
942 // Fix up any PHI nodes in the successor.
943 Succ->replacePhiUsesWith(FromMBB, this);
944 }
946}
947
949 return is_contained(predecessors(), MBB);
950}
951
953 return is_contained(successors(), MBB);
954}
955
958 return std::next(I) == MachineFunction::const_iterator(MBB);
959}
960
962 return Successors.size() == 1 ? Successors[0] : nullptr;
963}
964
966 return Predecessors.size() == 1 ? Predecessors[0] : nullptr;
967}
968
971 ++Fallthrough;
972 // If FallthroughBlock is off the end of the function, it can't fall through.
973 if (Fallthrough == getParent()->end())
974 return nullptr;
975
976 // If FallthroughBlock isn't a successor, no fallthrough is possible.
977 if (!isSuccessor(&*Fallthrough))
978 return nullptr;
979
980 // Analyze the branches, if any, at the end of the block.
981 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
984 if (TII->analyzeBranch(*this, TBB, FBB, Cond)) {
985 // If we couldn't analyze the branch, examine the last instruction.
986 // If the block doesn't end in a known control barrier, assume fallthrough
987 // is possible. The isPredicated check is needed because this code can be
988 // called during IfConversion, where an instruction which is normally a
989 // Barrier is predicated and thus no longer an actual control barrier.
990 return (empty() || !back().isBarrier() || TII->isPredicated(back()))
991 ? &*Fallthrough
992 : nullptr;
993 }
994
995 // If there is no branch, control always falls through.
996 if (!TBB) return &*Fallthrough;
997
998 // If there is some explicit branch to the fallthrough block, it can obviously
999 // reach, even though the branch should get folded to fall through implicitly.
1000 if (JumpToFallThrough && (MachineFunction::iterator(TBB) == Fallthrough ||
1001 MachineFunction::iterator(FBB) == Fallthrough))
1002 return &*Fallthrough;
1003
1004 // If it's an unconditional branch to some block not the fall through, it
1005 // doesn't fall through.
1006 if (Cond.empty()) return nullptr;
1007
1008 // Otherwise, if it is conditional and has no explicit false block, it falls
1009 // through.
1010 return (FBB == nullptr) ? &*Fallthrough : nullptr;
1011}
1012
1014 return getFallThrough() != nullptr;
1015}
1016
1018 bool UpdateLiveIns,
1019 LiveIntervals *LIS) {
1020 MachineBasicBlock::iterator SplitPoint(&MI);
1021 ++SplitPoint;
1022
1023 if (SplitPoint == end()) {
1024 // Don't bother with a new block.
1025 return this;
1026 }
1027
1028 MachineFunction *MF = getParent();
1029
1030 LivePhysRegs LiveRegs;
1031 if (UpdateLiveIns) {
1032 // Make sure we add any physregs we define in the block as liveins to the
1033 // new block.
1035 LiveRegs.init(*MF->getSubtarget().getRegisterInfo());
1036 LiveRegs.addLiveOuts(*this);
1037 for (auto I = rbegin(), E = Prev.getReverse(); I != E; ++I)
1038 LiveRegs.stepBackward(*I);
1039 }
1040
1042
1043 MF->insert(++MachineFunction::iterator(this), SplitBB);
1044 SplitBB->splice(SplitBB->begin(), this, SplitPoint, end());
1045
1046 SplitBB->transferSuccessorsAndUpdatePHIs(this);
1047 addSuccessor(SplitBB);
1048
1049 if (UpdateLiveIns)
1050 addLiveIns(*SplitBB, LiveRegs);
1051
1052 if (LIS)
1053 LIS->insertMBBInMaps(SplitBB);
1054
1055 return SplitBB;
1056}
1057
1058// Returns `true` if there are possibly other users of the jump table at
1059// `JumpTableIndex` except for the ones in `IgnoreMBB`.
1061 const MachineBasicBlock &IgnoreMBB,
1062 int JumpTableIndex) {
1063 assert(JumpTableIndex >= 0 && "need valid index");
1064 const MachineJumpTableInfo &MJTI = *MF.getJumpTableInfo();
1065 const MachineJumpTableEntry &MJTE = MJTI.getJumpTables()[JumpTableIndex];
1066 // Take any basic block from the table; every user of the jump table must
1067 // show up in the predecessor list.
1068 const MachineBasicBlock *MBB = nullptr;
1069 for (MachineBasicBlock *B : MJTE.MBBs) {
1070 if (B != nullptr) {
1071 MBB = B;
1072 break;
1073 }
1074 }
1075 if (MBB == nullptr)
1076 return true; // can't rule out other users if there isn't any block.
1079 for (MachineBasicBlock *Pred : MBB->predecessors()) {
1080 if (Pred == &IgnoreMBB)
1081 continue;
1082 MachineBasicBlock *DummyT = nullptr;
1083 MachineBasicBlock *DummyF = nullptr;
1084 Cond.clear();
1085 if (!TII.analyzeBranch(*Pred, DummyT, DummyF, Cond,
1086 /*AllowModify=*/false)) {
1087 // analyzable direct jump
1088 continue;
1089 }
1090 int PredJTI = findJumpTableIndex(*Pred);
1091 if (PredJTI >= 0) {
1092 if (PredJTI == JumpTableIndex)
1093 return true;
1094 continue;
1095 }
1096 // Be conservative for unanalyzable jumps.
1097 return true;
1098 }
1099 return false;
1100}
1101
1103private:
1104 MachineFunction &MF;
1105 SlotIndexes *Indexes;
1107
1108public:
1110 : MF(MF), Indexes(Indexes) {
1111 MF.setDelegate(this);
1112 }
1113
1115 MF.resetDelegate(this);
1116 for (auto MI : Insertions)
1117 Indexes->insertMachineInstrInMaps(*MI);
1118 }
1119
1121 // This is called before MI is inserted into block so defer index update.
1122 if (Indexes)
1123 Insertions.insert(&MI);
1124 }
1125
1127 if (Indexes && !Insertions.remove(&MI))
1129 }
1130};
1131
1133 MachineBasicBlock *Succ, Pass &P,
1134 std::vector<SparseBitVector<>> *LiveInSets) {
1135 if (!canSplitCriticalEdge(Succ))
1136 return nullptr;
1137
1138 MachineFunction *MF = getParent();
1139 MachineBasicBlock *PrevFallthrough = getNextNode();
1140
1142 NMBB->setCallFrameSize(Succ->getCallFrameSize());
1143
1144 // Is there an indirect jump with jump table?
1145 bool ChangedIndirectJump = false;
1146 int JTI = findJumpTableIndex(*this);
1147 if (JTI >= 0) {
1149 MJTI.ReplaceMBBInJumpTable(JTI, Succ, NMBB);
1150 ChangedIndirectJump = true;
1151 }
1152
1153 MF->insert(std::next(MachineFunction::iterator(this)), NMBB);
1154 LLVM_DEBUG(dbgs() << "Splitting critical edge: " << printMBBReference(*this)
1155 << " -- " << printMBBReference(*NMBB) << " -- "
1156 << printMBBReference(*Succ) << '\n');
1157
1158 LiveIntervals *LIS = P.getAnalysisIfAvailable<LiveIntervals>();
1159 SlotIndexes *Indexes = P.getAnalysisIfAvailable<SlotIndexes>();
1160 if (LIS)
1161 LIS->insertMBBInMaps(NMBB);
1162 else if (Indexes)
1163 Indexes->insertMBBInMaps(NMBB);
1164
1165 // On some targets like Mips, branches may kill virtual registers. Make sure
1166 // that LiveVariables is properly updated after updateTerminator replaces the
1167 // terminators.
1168 LiveVariables *LV = P.getAnalysisIfAvailable<LiveVariables>();
1169
1170 // Collect a list of virtual registers killed by the terminators.
1171 SmallVector<Register, 4> KilledRegs;
1172 if (LV)
1173 for (MachineInstr &MI :
1175 for (MachineOperand &MO : MI.all_uses()) {
1176 if (MO.getReg() == 0 || !MO.isKill() || MO.isUndef())
1177 continue;
1178 Register Reg = MO.getReg();
1179 if (Reg.isPhysical() || LV->getVarInfo(Reg).removeKill(MI)) {
1180 KilledRegs.push_back(Reg);
1181 LLVM_DEBUG(dbgs() << "Removing terminator kill: " << MI);
1182 MO.setIsKill(false);
1183 }
1184 }
1185 }
1186
1187 SmallVector<Register, 4> UsedRegs;
1188 if (LIS) {
1189 for (MachineInstr &MI :
1191 for (const MachineOperand &MO : MI.operands()) {
1192 if (!MO.isReg() || MO.getReg() == 0)
1193 continue;
1194
1195 Register Reg = MO.getReg();
1196 if (!is_contained(UsedRegs, Reg))
1197 UsedRegs.push_back(Reg);
1198 }
1199 }
1200 }
1201
1202 ReplaceUsesOfBlockWith(Succ, NMBB);
1203
1204 // Since we replaced all uses of Succ with NMBB, that should also be treated
1205 // as the fallthrough successor
1206 if (Succ == PrevFallthrough)
1207 PrevFallthrough = NMBB;
1208
1209 if (!ChangedIndirectJump) {
1210 SlotIndexUpdateDelegate SlotUpdater(*MF, Indexes);
1211 updateTerminator(PrevFallthrough);
1212 }
1213
1214 // Insert unconditional "jump Succ" instruction in NMBB if necessary.
1215 NMBB->addSuccessor(Succ);
1216 if (!NMBB->isLayoutSuccessor(Succ)) {
1217 SlotIndexUpdateDelegate SlotUpdater(*MF, Indexes);
1220
1221 // In original 'this' BB, there must be a branch instruction targeting at
1222 // Succ. We can not find it out since currently getBranchDestBlock was not
1223 // implemented for all targets. However, if the merged DL has column or line
1224 // number, the scope and non-zero column and line number is same with that
1225 // branch instruction so we can safely use it.
1226 DebugLoc DL, MergedDL = findBranchDebugLoc();
1227 if (MergedDL && (MergedDL.getLine() || MergedDL.getCol()))
1228 DL = MergedDL;
1229 TII->insertBranch(*NMBB, Succ, nullptr, Cond, DL);
1230 }
1231
1232 // Fix PHI nodes in Succ so they refer to NMBB instead of this.
1233 Succ->replacePhiUsesWith(this, NMBB);
1234
1235 // Inherit live-ins from the successor
1236 for (const auto &LI : Succ->liveins())
1237 NMBB->addLiveIn(LI);
1238
1239 // Update LiveVariables.
1241 if (LV) {
1242 // Restore kills of virtual registers that were killed by the terminators.
1243 while (!KilledRegs.empty()) {
1244 Register Reg = KilledRegs.pop_back_val();
1245 for (instr_iterator I = instr_end(), E = instr_begin(); I != E;) {
1246 if (!(--I)->addRegisterKilled(Reg, TRI, /* AddIfNotFound= */ false))
1247 continue;
1248 if (Reg.isVirtual())
1249 LV->getVarInfo(Reg).Kills.push_back(&*I);
1250 LLVM_DEBUG(dbgs() << "Restored terminator kill: " << *I);
1251 break;
1252 }
1253 }
1254 // Update relevant live-through information.
1255 if (LiveInSets != nullptr)
1256 LV->addNewBlock(NMBB, this, Succ, *LiveInSets);
1257 else
1258 LV->addNewBlock(NMBB, this, Succ);
1259 }
1260
1261 if (LIS) {
1262 // After splitting the edge and updating SlotIndexes, live intervals may be
1263 // in one of two situations, depending on whether this block was the last in
1264 // the function. If the original block was the last in the function, all
1265 // live intervals will end prior to the beginning of the new split block. If
1266 // the original block was not at the end of the function, all live intervals
1267 // will extend to the end of the new split block.
1268
1269 bool isLastMBB =
1270 std::next(MachineFunction::iterator(NMBB)) == getParent()->end();
1271
1272 SlotIndex StartIndex = Indexes->getMBBEndIdx(this);
1273 SlotIndex PrevIndex = StartIndex.getPrevSlot();
1274 SlotIndex EndIndex = Indexes->getMBBEndIdx(NMBB);
1275
1276 // Find the registers used from NMBB in PHIs in Succ.
1277 SmallSet<Register, 8> PHISrcRegs;
1279 I = Succ->instr_begin(), E = Succ->instr_end();
1280 I != E && I->isPHI(); ++I) {
1281 for (unsigned ni = 1, ne = I->getNumOperands(); ni != ne; ni += 2) {
1282 if (I->getOperand(ni+1).getMBB() == NMBB) {
1283 MachineOperand &MO = I->getOperand(ni);
1284 Register Reg = MO.getReg();
1285 PHISrcRegs.insert(Reg);
1286 if (MO.isUndef())
1287 continue;
1288
1289 LiveInterval &LI = LIS->getInterval(Reg);
1290 VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
1291 assert(VNI &&
1292 "PHI sources should be live out of their predecessors.");
1293 LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
1294 for (auto &SR : LI.subranges())
1295 SR.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
1296 }
1297 }
1298 }
1299
1301 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
1303 if (PHISrcRegs.count(Reg) || !LIS->hasInterval(Reg))
1304 continue;
1305
1306 LiveInterval &LI = LIS->getInterval(Reg);
1307 if (!LI.liveAt(PrevIndex))
1308 continue;
1309
1310 bool isLiveOut = LI.liveAt(LIS->getMBBStartIdx(Succ));
1311 if (isLiveOut && isLastMBB) {
1312 VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
1313 assert(VNI && "LiveInterval should have VNInfo where it is live.");
1314 LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
1315 // Update subranges with live values
1316 for (auto &SR : LI.subranges()) {
1317 VNInfo *VNI = SR.getVNInfoAt(PrevIndex);
1318 if (VNI)
1319 SR.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
1320 }
1321 } else if (!isLiveOut && !isLastMBB) {
1322 LI.removeSegment(StartIndex, EndIndex);
1323 for (auto &SR : LI.subranges())
1324 SR.removeSegment(StartIndex, EndIndex);
1325 }
1326 }
1327
1328 // Update all intervals for registers whose uses may have been modified by
1329 // updateTerminator().
1330 LIS->repairIntervalsInRange(this, getFirstTerminator(), end(), UsedRegs);
1331 }
1332
1333 if (MachineDominatorTree *MDT =
1334 P.getAnalysisIfAvailable<MachineDominatorTree>())
1335 MDT->recordSplitCriticalEdge(this, Succ, NMBB);
1336
1337 if (MachineLoopInfo *MLI = P.getAnalysisIfAvailable<MachineLoopInfo>())
1338 if (MachineLoop *TIL = MLI->getLoopFor(this)) {
1339 // If one or the other blocks were not in a loop, the new block is not
1340 // either, and thus LI doesn't need to be updated.
1341 if (MachineLoop *DestLoop = MLI->getLoopFor(Succ)) {
1342 if (TIL == DestLoop) {
1343 // Both in the same loop, the NMBB joins loop.
1344 DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase());
1345 } else if (TIL->contains(DestLoop)) {
1346 // Edge from an outer loop to an inner loop. Add to the outer loop.
1347 TIL->addBasicBlockToLoop(NMBB, MLI->getBase());
1348 } else if (DestLoop->contains(TIL)) {
1349 // Edge from an inner loop to an outer loop. Add to the outer loop.
1350 DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase());
1351 } else {
1352 // Edge from two loops with no containment relation. Because these
1353 // are natural loops, we know that the destination block must be the
1354 // header of its loop (adding a branch into a loop elsewhere would
1355 // create an irreducible loop).
1356 assert(DestLoop->getHeader() == Succ &&
1357 "Should not create irreducible loops!");
1358 if (MachineLoop *P = DestLoop->getParentLoop())
1359 P->addBasicBlockToLoop(NMBB, MLI->getBase());
1360 }
1361 }
1362 }
1363
1364 return NMBB;
1365}
1366
1368 const MachineBasicBlock *Succ) const {
1369 // Splitting the critical edge to a landing pad block is non-trivial. Don't do
1370 // it in this generic function.
1371 if (Succ->isEHPad())
1372 return false;
1373
1374 // Splitting the critical edge to a callbr's indirect block isn't advised.
1375 // Don't do it in this generic function.
1376 if (Succ->isInlineAsmBrIndirectTarget())
1377 return false;
1378
1379 const MachineFunction *MF = getParent();
1380 // Performance might be harmed on HW that implements branching using exec mask
1381 // where both sides of the branches are always executed.
1382 if (MF->getTarget().requiresStructuredCFG())
1383 return false;
1384
1385 // Do we have an Indirect jump with a jumptable that we can rewrite?
1386 int JTI = findJumpTableIndex(*this);
1387 if (JTI >= 0 && !jumpTableHasOtherUses(*MF, *this, JTI))
1388 return true;
1389
1390 // We may need to update this's terminator, but we can't do that if
1391 // analyzeBranch fails.
1393 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1395 // AnalyzeBanch should modify this, since we did not allow modification.
1396 if (TII->analyzeBranch(*const_cast<MachineBasicBlock *>(this), TBB, FBB, Cond,
1397 /*AllowModify*/ false))
1398 return false;
1399
1400 // Avoid bugpoint weirdness: A block may end with a conditional branch but
1401 // jumps to the same MBB is either case. We have duplicate CFG edges in that
1402 // case that we can't handle. Since this never happens in properly optimized
1403 // code, just skip those edges.
1404 if (TBB && TBB == FBB) {
1405 LLVM_DEBUG(dbgs() << "Won't split critical edge after degenerate "
1406 << printMBBReference(*this) << '\n');
1407 return false;
1408 }
1409 return true;
1410}
1411
1412/// Prepare MI to be removed from its bundle. This fixes bundle flags on MI's
1413/// neighboring instructions so the bundle won't be broken by removing MI.
1415 // Removing the first instruction in a bundle.
1416 if (MI->isBundledWithSucc() && !MI->isBundledWithPred())
1417 MI->unbundleFromSucc();
1418 // Removing the last instruction in a bundle.
1419 if (MI->isBundledWithPred() && !MI->isBundledWithSucc())
1420 MI->unbundleFromPred();
1421 // If MI is not bundled, or if it is internal to a bundle, the neighbor flags
1422 // are already fine.
1423}
1424
1428 return Insts.erase(I);
1429}
1430
1433 MI->clearFlag(MachineInstr::BundledPred);
1434 MI->clearFlag(MachineInstr::BundledSucc);
1435 return Insts.remove(MI);
1436}
1437
1440 assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
1441 "Cannot insert instruction with bundle flags");
1442 // Set the bundle flags when inserting inside a bundle.
1443 if (I != instr_end() && I->isBundledWithPred()) {
1444 MI->setFlag(MachineInstr::BundledPred);
1445 MI->setFlag(MachineInstr::BundledSucc);
1446 }
1447 return Insts.insert(I, MI);
1448}
1449
1450/// This method unlinks 'this' from the containing function, and returns it, but
1451/// does not delete it.
1453 assert(getParent() && "Not embedded in a function!");
1454 getParent()->remove(this);
1455 return this;
1456}
1457
1458/// This method unlinks 'this' from the containing function, and deletes it.
1460 assert(getParent() && "Not embedded in a function!");
1461 getParent()->erase(this);
1462}
1463
1464/// Given a machine basic block that branched to 'Old', change the code and CFG
1465/// so that it branches to 'New' instead.
1467 MachineBasicBlock *New) {
1468 assert(Old != New && "Cannot replace self with self!");
1469
1471 while (I != instr_begin()) {
1472 --I;
1473 if (!I->isTerminator()) break;
1474
1475 // Scan the operands of this machine instruction, replacing any uses of Old
1476 // with New.
1477 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
1478 if (I->getOperand(i).isMBB() &&
1479 I->getOperand(i).getMBB() == Old)
1480 I->getOperand(i).setMBB(New);
1481 }
1482
1483 // Update the successor information.
1484 replaceSuccessor(Old, New);
1485}
1486
1488 MachineBasicBlock *New) {
1489 for (MachineInstr &MI : phis())
1490 for (unsigned i = 2, e = MI.getNumOperands() + 1; i != e; i += 2) {
1491 MachineOperand &MO = MI.getOperand(i);
1492 if (MO.getMBB() == Old)
1493 MO.setMBB(New);
1494 }
1495}
1496
1497/// Find the next valid DebugLoc starting at MBBI, skipping any debug
1498/// instructions. Return UnknownLoc if there is none.
1501 // Skip debug declarations, we don't want a DebugLoc from them.
1503 if (MBBI != instr_end())
1504 return MBBI->getDebugLoc();
1505 return {};
1506}
1507
1509 if (MBBI == instr_rend())
1510 return findDebugLoc(instr_begin());
1511 // Skip debug declarations, we don't want a DebugLoc from them.
1513 if (!MBBI->isDebugInstr())
1514 return MBBI->getDebugLoc();
1515 return {};
1516}
1517
1518/// Find the previous valid DebugLoc preceding MBBI, skipping any debug
1519/// instructions. Return UnknownLoc if there is none.
1521 if (MBBI == instr_begin())
1522 return {};
1523 // Skip debug instructions, we don't want a DebugLoc from them.
1525 if (!MBBI->isDebugInstr())
1526 return MBBI->getDebugLoc();
1527 return {};
1528}
1529
1531 if (MBBI == instr_rend())
1532 return {};
1533 // Skip debug declarations, we don't want a DebugLoc from them.
1535 if (MBBI != instr_rend())
1536 return MBBI->getDebugLoc();
1537 return {};
1538}
1539
1540/// Find and return the merged DebugLoc of the branch instructions of the block.
1541/// Return UnknownLoc if there is none.
1544 DebugLoc DL;
1545 auto TI = getFirstTerminator();
1546 while (TI != end() && !TI->isBranch())
1547 ++TI;
1548
1549 if (TI != end()) {
1550 DL = TI->getDebugLoc();
1551 for (++TI ; TI != end() ; ++TI)
1552 if (TI->isBranch())
1553 DL = DILocation::getMergedLocation(DL, TI->getDebugLoc());
1554 }
1555 return DL;
1556}
1557
1558/// Return probability of the edge from this block to MBB.
1561 if (Probs.empty())
1562 return BranchProbability(1, succ_size());
1563
1564 const auto &Prob = *getProbabilityIterator(Succ);
1565 if (Prob.isUnknown()) {
1566 // For unknown probabilities, collect the sum of all known ones, and evenly
1567 // ditribute the complemental of the sum to each unknown probability.
1568 unsigned KnownProbNum = 0;
1569 auto Sum = BranchProbability::getZero();
1570 for (const auto &P : Probs) {
1571 if (!P.isUnknown()) {
1572 Sum += P;
1573 KnownProbNum++;
1574 }
1575 }
1576 return Sum.getCompl() / (Probs.size() - KnownProbNum);
1577 } else
1578 return Prob;
1579}
1580
1581/// Set successor probability of a given iterator.
1583 BranchProbability Prob) {
1584 assert(!Prob.isUnknown());
1585 if (Probs.empty())
1586 return;
1587 *getProbabilityIterator(I) = Prob;
1588}
1589
1590/// Return probability iterator corresonding to the I successor iterator
1591MachineBasicBlock::const_probability_iterator
1592MachineBasicBlock::getProbabilityIterator(
1594 assert(Probs.size() == Successors.size() && "Async probability list!");
1595 const size_t index = std::distance(Successors.begin(), I);
1596 assert(index < Probs.size() && "Not a current successor!");
1597 return Probs.begin() + index;
1598}
1599
1600/// Return probability iterator corresonding to the I successor iterator.
1601MachineBasicBlock::probability_iterator
1602MachineBasicBlock::getProbabilityIterator(MachineBasicBlock::succ_iterator I) {
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 whether (physical) register "Reg" has been <def>ined and not <kill>ed
1610/// as of just before "MI".
1611///
1612/// Search is localised to a neighborhood of
1613/// Neighborhood instructions before (searching for defs or kills) and N
1614/// instructions after (searching just for defs) MI.
1618 unsigned Neighborhood) const {
1619 unsigned N = Neighborhood;
1620
1621 // Try searching forwards from Before, looking for reads or defs.
1623 for (; I != end() && N > 0; ++I) {
1624 if (I->isDebugOrPseudoInstr())
1625 continue;
1626
1627 --N;
1628
1630
1631 // Register is live when we read it here.
1632 if (Info.Read)
1633 return LQR_Live;
1634 // Register is dead if we can fully overwrite or clobber it here.
1635 if (Info.FullyDefined || Info.Clobbered)
1636 return LQR_Dead;
1637 }
1638
1639 // If we reached the end, it is safe to clobber Reg at the end of a block of
1640 // no successor has it live in.
1641 if (I == end()) {
1642 for (MachineBasicBlock *S : successors()) {
1643 for (const MachineBasicBlock::RegisterMaskPair &LI : S->liveins()) {
1644 if (TRI->regsOverlap(LI.PhysReg, Reg))
1645 return LQR_Live;
1646 }
1647 }
1648
1649 return LQR_Dead;
1650 }
1651
1652
1653 N = Neighborhood;
1654
1655 // Start by searching backwards from Before, looking for kills, reads or defs.
1657 // If this is the first insn in the block, don't search backwards.
1658 if (I != begin()) {
1659 do {
1660 --I;
1661
1662 if (I->isDebugOrPseudoInstr())
1663 continue;
1664
1665 --N;
1666
1668
1669 // Defs happen after uses so they take precedence if both are present.
1670
1671 // Register is dead after a dead def of the full register.
1672 if (Info.DeadDef)
1673 return LQR_Dead;
1674 // Register is (at least partially) live after a def.
1675 if (Info.Defined) {
1676 if (!Info.PartialDeadDef)
1677 return LQR_Live;
1678 // As soon as we saw a partial definition (dead or not),
1679 // we cannot tell if the value is partial live without
1680 // tracking the lanemasks. We are not going to do this,
1681 // so fall back on the remaining of the analysis.
1682 break;
1683 }
1684 // Register is dead after a full kill or clobber and no def.
1685 if (Info.Killed || Info.Clobbered)
1686 return LQR_Dead;
1687 // Register must be live if we read it.
1688 if (Info.Read)
1689 return LQR_Live;
1690
1691 } while (I != begin() && N > 0);
1692 }
1693
1694 // If all the instructions before this in the block are debug instructions,
1695 // skip over them.
1696 while (I != begin() && std::prev(I)->isDebugOrPseudoInstr())
1697 --I;
1698
1699 // Did we get to the start of the block?
1700 if (I == begin()) {
1701 // If so, the register's state is definitely defined by the live-in state.
1703 if (TRI->regsOverlap(LI.PhysReg, Reg))
1704 return LQR_Live;
1705
1706 return LQR_Dead;
1707 }
1708
1709 // At this point we have no idea of the liveness of the register.
1710 return LQR_Unknown;
1711}
1712
1713const uint32_t *
1715 // EH funclet entry does not preserve any registers.
1716 return isEHFuncletEntry() ? TRI->getNoPreservedMask() : nullptr;
1717}
1718
1719const uint32_t *
1721 // If we see a return block with successors, this must be a funclet return,
1722 // which does not preserve any registers. If there are no successors, we don't
1723 // care what kind of return it is, putting a mask after it is a no-op.
1724 return isReturnBlock() && !succ_empty() ? TRI->getNoPreservedMask() : nullptr;
1725}
1726
1728 LiveIns.clear();
1729}
1730
1732 assert(getParent()->getProperties().hasProperty(
1734 "Liveness information is accurate");
1735 return LiveIns.begin();
1736}
1737
1739 const MachineFunction &MF = *getParent();
1742 "Liveness information is accurate");
1743
1744 const TargetLowering &TLI = *MF.getSubtarget().getTargetLowering();
1745 MCPhysReg ExceptionPointer = 0, ExceptionSelector = 0;
1746 if (MF.getFunction().hasPersonalityFn()) {
1747 auto PersonalityFn = MF.getFunction().getPersonalityFn();
1748 ExceptionPointer = TLI.getExceptionPointerRegister(PersonalityFn);
1749 ExceptionSelector = TLI.getExceptionSelectorRegister(PersonalityFn);
1750 }
1751
1752 return liveout_iterator(*this, ExceptionPointer, ExceptionSelector, false);
1753}
1754
1756 unsigned Cntr = 0;
1757 auto R = instructionsWithoutDebug(begin(), end());
1758 for (auto I = R.begin(), E = R.end(); I != E; ++I) {
1759 if (++Cntr > Limit)
1760 return true;
1761 }
1762 return false;
1763}
1764
1766const 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:529
#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
#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:60
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:851
Constant * getPersonalityFn() const
Get the personality function associated with this function.
Definition: Function.cpp:1892
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:50
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:68
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.
StringRef getPrivateLabelPrefix() const
Definition: MCAsmInfo.h:665
Context object for machine code objects.
Definition: MCContext.h:81
const MCAsmInfo * getAsmInfo() const
Definition: MCContext.h:453
MCSymbol * getOrCreateSymbol(const Twine &Name)
Lookup the symbol inside with the specified Name.
Definition: MCContext.cpp:201
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:40
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...
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.
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
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:913
void incorporateFunction(const Function &F)
Incorporate the given function.
Definition: AsmWriter.cpp:899
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:68
SlotIndex getPrevSlot() const
Returns the previous slot in the index list.
Definition: SlotIndexes.h:275
SlotIndexes pass.
Definition: SlotIndexes.h:300
SlotIndex insertMachineInstrInMaps(MachineInstr &MI, bool Late=false)
Insert the given machine instruction into the mapping.
Definition: SlotIndexes.h:523
void removeMachineInstrFromMaps(MachineInstr &MI, bool AllowBundled=false)
Removes machine instruction (bundle) MI from the mapping.
SlotIndex getInstructionIndex(const MachineInstr &MI, bool IgnoreBundle=false) const
Returns the base index for the given instruction.
Definition: SlotIndexes.h:371
SlotIndex getMBBStartIdx(unsigned Num) const
Returns the first index in the given basic block number.
Definition: SlotIndexes.h:452
bool hasIndex(const MachineInstr &instr) const
Returns true if the given machine instr is mapped to an index, otherwise returns false.
Definition: SlotIndexes.h:366
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
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:316
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:690
#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:450
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.
#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:95
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:90
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