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