LLVM 17.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"
28#include "llvm/Config/llvm-config.h"
29#include "llvm/IR/BasicBlock.h"
32#include "llvm/MC/MCAsmInfo.h"
33#include "llvm/MC/MCContext.h"
34#include "llvm/Support/Debug.h"
37#include <algorithm>
38#include <cmath>
39using namespace llvm;
40
41#define DEBUG_TYPE "codegen"
42
44 "print-slotindexes",
45 cl::desc("When printing machine IR, annotate instructions and blocks with "
46 "SlotIndexes when available"),
47 cl::init(true), cl::Hidden);
48
49MachineBasicBlock::MachineBasicBlock(MachineFunction &MF, const BasicBlock *B)
50 : BB(B), Number(-1), xParent(&MF) {
51 Insts.Parent = this;
52 if (B)
53 IrrLoopHeaderWeight = B->getIrrLoopHeaderWeight();
54}
55
56MachineBasicBlock::~MachineBasicBlock() = default;
57
58/// Return the MCSymbol for this basic block.
60 if (!CachedMCSymbol) {
61 const MachineFunction *MF = getParent();
62 MCContext &Ctx = MF->getContext();
63
64 // We emit a non-temporary symbol -- with a descriptive name -- if it begins
65 // a section (with basic block sections). Otherwise we fall back to use temp
66 // label.
67 if (MF->hasBBSections() && isBeginSection()) {
68 SmallString<5> Suffix;
69 if (SectionID == MBBSectionID::ColdSectionID) {
70 Suffix += ".cold";
71 } else if (SectionID == MBBSectionID::ExceptionSectionID) {
72 Suffix += ".eh";
73 } else {
74 // For symbols that represent basic block sections, we add ".__part." to
75 // allow tools like symbolizers to know that this represents a part of
76 // the original function.
77 Suffix = (Suffix + Twine(".__part.") + Twine(SectionID.Number)).str();
78 }
79 CachedMCSymbol = Ctx.getOrCreateSymbol(MF->getName() + Suffix);
80 } else {
81 const StringRef Prefix = Ctx.getAsmInfo()->getPrivateLabelPrefix();
82 CachedMCSymbol = Ctx.getOrCreateSymbol(Twine(Prefix) + "BB" +
84 "_" + Twine(getNumber()));
85 }
86 }
87 return CachedMCSymbol;
88}
89
91 if (!CachedEHCatchretMCSymbol) {
92 const MachineFunction *MF = getParent();
93 SmallString<128> SymbolName;
94 raw_svector_ostream(SymbolName)
95 << "$ehgcr_" << MF->getFunctionNumber() << '_' << getNumber();
96 CachedEHCatchretMCSymbol = MF->getContext().getOrCreateSymbol(SymbolName);
97 }
98 return CachedEHCatchretMCSymbol;
99}
100
102 if (!CachedEndMCSymbol) {
103 const MachineFunction *MF = getParent();
104 MCContext &Ctx = MF->getContext();
105 auto Prefix = Ctx.getAsmInfo()->getPrivateLabelPrefix();
106 CachedEndMCSymbol = Ctx.getOrCreateSymbol(Twine(Prefix) + "BB_END" +
107 Twine(MF->getFunctionNumber()) +
108 "_" + Twine(getNumber()));
109 }
110 return CachedEndMCSymbol;
111}
112
114 MBB.print(OS);
115 return OS;
116}
117
119 return Printable([&MBB](raw_ostream &OS) { return MBB.printAsOperand(OS); });
120}
121
122/// When an MBB is added to an MF, we need to update the parent pointer of the
123/// MBB, the MBB numbering, and any instructions in the MBB to be on the right
124/// operand list for registers.
125///
126/// MBBs start out as #-1. When a MBB is added to a MachineFunction, it
127/// gets the next available unique MBB number. If it is removed from a
128/// MachineFunction, it goes back to being #-1.
131 MachineFunction &MF = *N->getParent();
132 N->Number = MF.addToMBBNumbering(N);
133
134 // Make sure the instructions have their operands in the reginfo lists.
135 MachineRegisterInfo &RegInfo = MF.getRegInfo();
136 for (MachineInstr &MI : N->instrs())
137 MI.addRegOperandsToUseLists(RegInfo);
138}
139
142 N->getParent()->removeFromMBBNumbering(N->Number);
143 N->Number = -1;
144}
145
146/// When we add an instruction to a basic block list, we update its parent
147/// pointer and add its operands from reg use/def lists if appropriate.
149 assert(!N->getParent() && "machine instruction already in a basic block");
150 N->setParent(Parent);
151
152 // Add the instruction's register operands to their corresponding
153 // use/def lists.
154 MachineFunction *MF = Parent->getParent();
155 N->addRegOperandsToUseLists(MF->getRegInfo());
156 MF->handleInsertion(*N);
157}
158
159/// When we remove an instruction from a basic block list, we update its parent
160/// pointer and remove its operands from reg use/def lists if appropriate.
162 assert(N->getParent() && "machine instruction not in a basic block");
163
164 // Remove from the use/def lists.
165 if (MachineFunction *MF = N->getMF()) {
166 MF->handleRemoval(*N);
167 N->removeRegOperandsFromUseLists(MF->getRegInfo());
168 }
169
170 N->setParent(nullptr);
171}
172
173/// When moving a range of instructions from one MBB list to another, we need to
174/// update the parent pointers and the use/def lists.
176 instr_iterator First,
177 instr_iterator Last) {
178 assert(Parent->getParent() == FromList.Parent->getParent() &&
179 "cannot transfer MachineInstrs between MachineFunctions");
180
181 // If it's within the same BB, there's nothing to do.
182 if (this == &FromList)
183 return;
184
185 assert(Parent != FromList.Parent && "Two lists have the same parent?");
186
187 // If splicing between two blocks within the same function, just update the
188 // parent pointers.
189 for (; First != Last; ++First)
190 First->setParent(Parent);
191}
192
194 assert(!MI->getParent() && "MI is still in a block!");
195 Parent->getParent()->deleteMachineInstr(MI);
196}
197
200 while (I != E && I->isPHI())
201 ++I;
202 assert((I == E || !I->isInsideBundle()) &&
203 "First non-phi MI cannot be inside a bundle!");
204 return I;
205}
206
210
211 iterator E = end();
212 while (I != E && (I->isPHI() || I->isPosition() ||
213 TII->isBasicBlockPrologue(*I)))
214 ++I;
215 // FIXME: This needs to change if we wish to bundle labels
216 // inside the bundle.
217 assert((I == E || !I->isInsideBundle()) &&
218 "First non-phi / non-label instruction is inside a bundle!");
219 return I;
220}
221
224 bool SkipPseudoOp) {
226
227 iterator E = end();
228 while (I != E && (I->isPHI() || I->isPosition() || I->isDebugInstr() ||
229 (SkipPseudoOp && I->isPseudoProbe()) ||
230 TII->isBasicBlockPrologue(*I)))
231 ++I;
232 // FIXME: This needs to change if we wish to bundle labels / dbg_values
233 // inside the bundle.
234 assert((I == E || !I->isInsideBundle()) &&
235 "First non-phi / non-label / non-debug "
236 "instruction is inside a bundle!");
237 return I;
238}
239
241 iterator B = begin(), E = end(), I = E;
242 while (I != B && ((--I)->isTerminator() || I->isDebugInstr()))
243 ; /*noop */
244 while (I != E && !I->isTerminator())
245 ++I;
246 return I;
247}
248
251 while (I != B && ((--I)->isTerminator() || I->isDebugInstr()))
252 ; /*noop */
253 while (I != E && !I->isTerminator())
254 ++I;
255 return I;
256}
257
259 return find_if(instrs(), [](auto &II) { return II.isTerminator(); });
260}
261
264 // Skip over begin-of-block dbg_value instructions.
265 return skipDebugInstructionsForward(begin(), end(), SkipPseudoOp);
266}
267
270 // Skip over end-of-block dbg_value instructions.
272 while (I != B) {
273 --I;
274 // Return instruction that starts a bundle.
275 if (I->isDebugInstr() || I->isInsideBundle())
276 continue;
277 if (SkipPseudoOp && I->isPseudoProbe())
278 continue;
279 return I;
280 }
281 // The block is all debug values.
282 return end();
283}
284
286 for (const MachineBasicBlock *Succ : successors())
287 if (Succ->isEHPad())
288 return true;
289 return false;
290}
291
293 return getParent()->begin() == getIterator();
294}
295
296#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
298 print(dbgs());
299}
300#endif
301
303 for (const MachineBasicBlock *Succ : successors()) {
304 if (Succ->isInlineAsmBrIndirectTarget())
305 return true;
306 }
307 return false;
308}
309
312 return false;
313 return true;
314}
315
317 if (const BasicBlock *LBB = getBasicBlock())
318 return LBB->getName();
319 else
320 return StringRef("", 0);
321}
322
323/// Return a hopefully unique identifier for this block.
325 std::string Name;
326 if (getParent())
327 Name = (getParent()->getName() + ":").str();
328 if (getBasicBlock())
329 Name += getBasicBlock()->getName();
330 else
331 Name += ("BB" + Twine(getNumber())).str();
332 return Name;
333}
334
336 bool IsStandalone) const {
337 const MachineFunction *MF = getParent();
338 if (!MF) {
339 OS << "Can't print out MachineBasicBlock because parent MachineFunction"
340 << " is null\n";
341 return;
342 }
343 const Function &F = MF->getFunction();
344 const Module *M = F.getParent();
345 ModuleSlotTracker MST(M);
347 print(OS, MST, Indexes, IsStandalone);
348}
349
351 const SlotIndexes *Indexes,
352 bool IsStandalone) const {
353 const MachineFunction *MF = getParent();
354 if (!MF) {
355 OS << "Can't print out MachineBasicBlock because parent MachineFunction"
356 << " is null\n";
357 return;
358 }
359
360 if (Indexes && PrintSlotIndexes)
361 OS << Indexes->getMBBStartIdx(this) << '\t';
362
364 OS << ":\n";
365
367 const MachineRegisterInfo &MRI = MF->getRegInfo();
369 bool HasLineAttributes = false;
370
371 // Print the preds of this block according to the CFG.
372 if (!pred_empty() && IsStandalone) {
373 if (Indexes) OS << '\t';
374 // Don't indent(2), align with previous line attributes.
375 OS << "; predecessors: ";
376 ListSeparator LS;
377 for (auto *Pred : predecessors())
378 OS << LS << printMBBReference(*Pred);
379 OS << '\n';
380 HasLineAttributes = true;
381 }
382
383 if (!succ_empty()) {
384 if (Indexes) OS << '\t';
385 // Print the successors
386 OS.indent(2) << "successors: ";
387 ListSeparator LS;
388 for (auto I = succ_begin(), E = succ_end(); I != E; ++I) {
389 OS << LS << printMBBReference(**I);
390 if (!Probs.empty())
391 OS << '('
392 << format("0x%08" PRIx32, getSuccProbability(I).getNumerator())
393 << ')';
394 }
395 if (!Probs.empty() && IsStandalone) {
396 // Print human readable probabilities as comments.
397 OS << "; ";
398 ListSeparator LS;
399 for (auto I = succ_begin(), E = succ_end(); I != E; ++I) {
401 OS << LS << printMBBReference(**I) << '('
402 << format("%.2f%%",
403 rint(((double)BP.getNumerator() / BP.getDenominator()) *
404 100.0 * 100.0) /
405 100.0)
406 << ')';
407 }
408 }
409
410 OS << '\n';
411 HasLineAttributes = true;
412 }
413
414 if (!livein_empty() && MRI.tracksLiveness()) {
415 if (Indexes) OS << '\t';
416 OS.indent(2) << "liveins: ";
417
418 ListSeparator LS;
419 for (const auto &LI : liveins()) {
420 OS << LS << printReg(LI.PhysReg, TRI);
421 if (!LI.LaneMask.all())
422 OS << ":0x" << PrintLaneMask(LI.LaneMask);
423 }
424 HasLineAttributes = true;
425 }
426
427 if (HasLineAttributes)
428 OS << '\n';
429
430 bool IsInBundle = false;
431 for (const MachineInstr &MI : instrs()) {
432 if (Indexes && PrintSlotIndexes) {
433 if (Indexes->hasIndex(MI))
434 OS << Indexes->getInstructionIndex(MI);
435 OS << '\t';
436 }
437
438 if (IsInBundle && !MI.isInsideBundle()) {
439 OS.indent(2) << "}\n";
440 IsInBundle = false;
441 }
442
443 OS.indent(IsInBundle ? 4 : 2);
444 MI.print(OS, MST, IsStandalone, /*SkipOpers=*/false, /*SkipDebugLoc=*/false,
445 /*AddNewLine=*/false, &TII);
446
447 if (!IsInBundle && MI.getFlag(MachineInstr::BundledSucc)) {
448 OS << " {";
449 IsInBundle = true;
450 }
451 OS << '\n';
452 }
453
454 if (IsInBundle)
455 OS.indent(2) << "}\n";
456
457 if (IrrLoopHeaderWeight && IsStandalone) {
458 if (Indexes) OS << '\t';
459 OS.indent(2) << "; Irreducible loop header weight: " << *IrrLoopHeaderWeight
460 << '\n';
461 }
462}
463
464/// Print the basic block's name as:
465///
466/// bb.{number}[.{ir-name}] [(attributes...)]
467///
468/// The {ir-name} is only printed when the \ref PrintNameIr flag is passed
469/// (which is the default). If the IR block has no name, it is identified
470/// numerically using the attribute syntax as "(%ir-block.{ir-slot})".
471///
472/// When the \ref PrintNameAttributes flag is passed, additional attributes
473/// of the block are printed when set.
474///
475/// \param printNameFlags Combination of \ref PrintNameFlag flags indicating
476/// the parts to print.
477/// \param moduleSlotTracker Optional ModuleSlotTracker. This method will
478/// incorporate its own tracker when necessary to
479/// determine the block's IR name.
480void MachineBasicBlock::printName(raw_ostream &os, unsigned printNameFlags,
481 ModuleSlotTracker *moduleSlotTracker) const {
482 os << "bb." << getNumber();
483 bool hasAttributes = false;
484
485 auto PrintBBRef = [&](const BasicBlock *bb) {
486 os << "%ir-block.";
487 if (bb->hasName()) {
488 os << bb->getName();
489 } else {
490 int slot = -1;
491
492 if (moduleSlotTracker) {
493 slot = moduleSlotTracker->getLocalSlot(bb);
494 } else if (bb->getParent()) {
495 ModuleSlotTracker tmpTracker(bb->getModule(), false);
496 tmpTracker.incorporateFunction(*bb->getParent());
497 slot = tmpTracker.getLocalSlot(bb);
498 }
499
500 if (slot == -1)
501 os << "<ir-block badref>";
502 else
503 os << slot;
504 }
505 };
506
507 if (printNameFlags & PrintNameIr) {
508 if (const auto *bb = getBasicBlock()) {
509 if (bb->hasName()) {
510 os << '.' << bb->getName();
511 } else {
512 hasAttributes = true;
513 os << " (";
514 PrintBBRef(bb);
515 }
516 }
517 }
518
519 if (printNameFlags & PrintNameAttributes) {
521 os << (hasAttributes ? ", " : " (");
522 os << "machine-block-address-taken";
523 hasAttributes = true;
524 }
525 if (isIRBlockAddressTaken()) {
526 os << (hasAttributes ? ", " : " (");
527 os << "ir-block-address-taken ";
528 PrintBBRef(getAddressTakenIRBlock());
529 hasAttributes = true;
530 }
531 if (isEHPad()) {
532 os << (hasAttributes ? ", " : " (");
533 os << "landing-pad";
534 hasAttributes = true;
535 }
537 os << (hasAttributes ? ", " : " (");
538 os << "inlineasm-br-indirect-target";
539 hasAttributes = true;
540 }
541 if (isEHFuncletEntry()) {
542 os << (hasAttributes ? ", " : " (");
543 os << "ehfunclet-entry";
544 hasAttributes = true;
545 }
546 if (getAlignment() != Align(1)) {
547 os << (hasAttributes ? ", " : " (");
548 os << "align " << getAlignment().value();
549 hasAttributes = true;
550 }
551 if (getSectionID() != MBBSectionID(0)) {
552 os << (hasAttributes ? ", " : " (");
553 os << "bbsections ";
554 switch (getSectionID().Type) {
556 os << "Exception";
557 break;
559 os << "Cold";
560 break;
561 default:
562 os << getSectionID().Number;
563 }
564 hasAttributes = true;
565 }
566 if (getBBID().has_value()) {
567 os << (hasAttributes ? ", " : " (");
568 os << "bb_id " << *getBBID();
569 hasAttributes = true;
570 }
571 }
572
573 if (hasAttributes)
574 os << ')';
575}
576
578 bool /*PrintType*/) const {
579 OS << '%';
580 printName(OS, 0);
581}
582
584 LiveInVector::iterator I = find_if(
585 LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
586 if (I == LiveIns.end())
587 return;
588
589 I->LaneMask &= ~LaneMask;
590 if (I->LaneMask.none())
591 LiveIns.erase(I);
592}
593
596 // Get non-const version of iterator.
597 LiveInVector::iterator LI = LiveIns.begin() + (I - LiveIns.begin());
598 return LiveIns.erase(LI);
599}
600
603 LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
604 return I != livein_end() && (I->LaneMask & LaneMask).any();
605}
606
608 llvm::sort(LiveIns,
609 [](const RegisterMaskPair &LI0, const RegisterMaskPair &LI1) {
610 return LI0.PhysReg < LI1.PhysReg;
611 });
612 // Liveins are sorted by physreg now we can merge their lanemasks.
613 LiveInVector::const_iterator I = LiveIns.begin();
614 LiveInVector::const_iterator J;
615 LiveInVector::iterator Out = LiveIns.begin();
616 for (; I != LiveIns.end(); ++Out, I = J) {
617 MCRegister PhysReg = I->PhysReg;
618 LaneBitmask LaneMask = I->LaneMask;
619 for (J = std::next(I); J != LiveIns.end() && J->PhysReg == PhysReg; ++J)
620 LaneMask |= J->LaneMask;
621 Out->PhysReg = PhysReg;
622 Out->LaneMask = LaneMask;
623 }
624 LiveIns.erase(Out, LiveIns.end());
625}
626
629 assert(getParent() && "MBB must be inserted in function");
630 assert(Register::isPhysicalRegister(PhysReg) && "Expected physreg");
631 assert(RC && "Register class is required");
632 assert((isEHPad() || this == &getParent()->front()) &&
633 "Only the entry block and landing pads can have physreg live ins");
634
635 bool LiveIn = isLiveIn(PhysReg);
639
640 // Look for an existing copy.
641 if (LiveIn)
642 for (;I != E && I->isCopy(); ++I)
643 if (I->getOperand(1).getReg() == PhysReg) {
644 Register VirtReg = I->getOperand(0).getReg();
645 if (!MRI.constrainRegClass(VirtReg, RC))
646 llvm_unreachable("Incompatible live-in register class.");
647 return VirtReg;
648 }
649
650 // No luck, create a virtual register.
651 Register VirtReg = MRI.createVirtualRegister(RC);
652 BuildMI(*this, I, DebugLoc(), TII.get(TargetOpcode::COPY), VirtReg)
653 .addReg(PhysReg, RegState::Kill);
654 if (!LiveIn)
655 addLiveIn(PhysReg);
656 return VirtReg;
657}
658
660 getParent()->splice(NewAfter->getIterator(), getIterator());
661}
662
664 getParent()->splice(++NewBefore->getIterator(), getIterator());
665}
666
668 MachineBasicBlock *PreviousLayoutSuccessor) {
669 LLVM_DEBUG(dbgs() << "Updating terminators on " << printMBBReference(*this)
670 << "\n");
671
673 // A block with no successors has no concerns with fall-through edges.
674 if (this->succ_empty())
675 return;
676
677 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
680 bool B = TII->analyzeBranch(*this, TBB, FBB, Cond);
681 (void) B;
682 assert(!B && "UpdateTerminators requires analyzable predecessors!");
683 if (Cond.empty()) {
684 if (TBB) {
685 // The block has an unconditional branch. If its successor is now its
686 // layout successor, delete the branch.
688 TII->removeBranch(*this);
689 } else {
690 // The block has an unconditional fallthrough, or the end of the block is
691 // unreachable.
692
693 // Unfortunately, whether the end of the block is unreachable is not
694 // immediately obvious; we must fall back to checking the successor list,
695 // and assuming that if the passed in block is in the succesor list and
696 // not an EHPad, it must be the intended target.
697 if (!PreviousLayoutSuccessor || !isSuccessor(PreviousLayoutSuccessor) ||
698 PreviousLayoutSuccessor->isEHPad())
699 return;
700
701 // If the unconditional successor block is not the current layout
702 // successor, insert a branch to jump to it.
703 if (!isLayoutSuccessor(PreviousLayoutSuccessor))
704 TII->insertBranch(*this, PreviousLayoutSuccessor, nullptr, Cond, DL);
705 }
706 return;
707 }
708
709 if (FBB) {
710 // The block has a non-fallthrough conditional branch. If one of its
711 // successors is its layout successor, rewrite it to a fallthrough
712 // conditional branch.
713 if (isLayoutSuccessor(TBB)) {
715 return;
716 TII->removeBranch(*this);
717 TII->insertBranch(*this, FBB, nullptr, Cond, DL);
718 } else if (isLayoutSuccessor(FBB)) {
719 TII->removeBranch(*this);
720 TII->insertBranch(*this, TBB, nullptr, Cond, DL);
721 }
722 return;
723 }
724
725 // We now know we're going to fallthrough to PreviousLayoutSuccessor.
726 assert(PreviousLayoutSuccessor);
727 assert(!PreviousLayoutSuccessor->isEHPad());
728 assert(isSuccessor(PreviousLayoutSuccessor));
729
730 if (PreviousLayoutSuccessor == TBB) {
731 // We had a fallthrough to the same basic block as the conditional jump
732 // targets. Remove the conditional jump, leaving an unconditional
733 // fallthrough or an unconditional jump.
734 TII->removeBranch(*this);
735 if (!isLayoutSuccessor(TBB)) {
736 Cond.clear();
737 TII->insertBranch(*this, TBB, nullptr, Cond, DL);
738 }
739 return;
740 }
741
742 // The block has a fallthrough conditional branch.
743 if (isLayoutSuccessor(TBB)) {
745 // We can't reverse the condition, add an unconditional branch.
746 Cond.clear();
747 TII->insertBranch(*this, PreviousLayoutSuccessor, nullptr, Cond, DL);
748 return;
749 }
750 TII->removeBranch(*this);
751 TII->insertBranch(*this, PreviousLayoutSuccessor, nullptr, Cond, DL);
752 } else if (!isLayoutSuccessor(PreviousLayoutSuccessor)) {
753 TII->removeBranch(*this);
754 TII->insertBranch(*this, TBB, PreviousLayoutSuccessor, Cond, DL);
755 }
756}
757
759#ifndef NDEBUG
760 int64_t Sum = 0;
761 for (auto Prob : Probs)
762 Sum += Prob.getNumerator();
763 // Due to precision issue, we assume that the sum of probabilities is one if
764 // the difference between the sum of their numerators and the denominator is
765 // no greater than the number of successors.
767 Probs.size() &&
768 "The sum of successors's probabilities exceeds one.");
769#endif // NDEBUG
770}
771
773 BranchProbability Prob) {
774 // Probability list is either empty (if successor list isn't empty, this means
775 // disabled optimization) or has the same size as successor list.
776 if (!(Probs.empty() && !Successors.empty()))
777 Probs.push_back(Prob);
778 Successors.push_back(Succ);
779 Succ->addPredecessor(this);
780}
781
783 // We need to make sure probability list is either empty or has the same size
784 // of successor list. When this function is called, we can safely delete all
785 // probability in the list.
786 Probs.clear();
787 Successors.push_back(Succ);
788 Succ->addPredecessor(this);
789}
790
793 bool NormalizeSuccProbs) {
794 succ_iterator OldI = llvm::find(successors(), Old);
795 assert(OldI != succ_end() && "Old is not a successor of this block!");
797 "New is already a successor of this block!");
798
799 // Add a new successor with equal probability as the original one. Note
800 // that we directly copy the probability using the iterator rather than
801 // getting a potentially synthetic probability computed when unknown. This
802 // preserves the probabilities as-is and then we can renormalize them and
803 // query them effectively afterward.
804 addSuccessor(New, Probs.empty() ? BranchProbability::getUnknown()
805 : *getProbabilityIterator(OldI));
806 if (NormalizeSuccProbs)
808}
809
811 bool NormalizeSuccProbs) {
812 succ_iterator I = find(Successors, Succ);
813 removeSuccessor(I, NormalizeSuccProbs);
814}
815
818 assert(I != Successors.end() && "Not a current successor!");
819
820 // If probability list is empty it means we don't use it (disabled
821 // optimization).
822 if (!Probs.empty()) {
823 probability_iterator WI = getProbabilityIterator(I);
824 Probs.erase(WI);
825 if (NormalizeSuccProbs)
827 }
828
829 (*I)->removePredecessor(this);
830 return Successors.erase(I);
831}
832
834 MachineBasicBlock *New) {
835 if (Old == New)
836 return;
837
839 succ_iterator NewI = E;
840 succ_iterator OldI = E;
841 for (succ_iterator I = succ_begin(); I != E; ++I) {
842 if (*I == Old) {
843 OldI = I;
844 if (NewI != E)
845 break;
846 }
847 if (*I == New) {
848 NewI = I;
849 if (OldI != E)
850 break;
851 }
852 }
853 assert(OldI != E && "Old is not a successor of this block");
854
855 // If New isn't already a successor, let it take Old's place.
856 if (NewI == E) {
857 Old->removePredecessor(this);
858 New->addPredecessor(this);
859 *OldI = New;
860 return;
861 }
862
863 // New is already a successor.
864 // Update its probability instead of adding a duplicate edge.
865 if (!Probs.empty()) {
866 auto ProbIter = getProbabilityIterator(NewI);
867 if (!ProbIter->isUnknown())
868 *ProbIter += *getProbabilityIterator(OldI);
869 }
870 removeSuccessor(OldI);
871}
872
875 if (!Orig->Probs.empty())
877 else
879}
880
881void MachineBasicBlock::addPredecessor(MachineBasicBlock *Pred) {
882 Predecessors.push_back(Pred);
883}
884
885void MachineBasicBlock::removePredecessor(MachineBasicBlock *Pred) {
886 pred_iterator I = find(Predecessors, Pred);
887 assert(I != Predecessors.end() && "Pred is not a predecessor of this block!");
888 Predecessors.erase(I);
889}
890
892 if (this == FromMBB)
893 return;
894
895 while (!FromMBB->succ_empty()) {
896 MachineBasicBlock *Succ = *FromMBB->succ_begin();
897
898 // If probability list is empty it means we don't use it (disabled
899 // optimization).
900 if (!FromMBB->Probs.empty()) {
901 auto Prob = *FromMBB->Probs.begin();
902 addSuccessor(Succ, Prob);
903 } else
905
906 FromMBB->removeSuccessor(Succ);
907 }
908}
909
910void
912 if (this == FromMBB)
913 return;
914
915 while (!FromMBB->succ_empty()) {
916 MachineBasicBlock *Succ = *FromMBB->succ_begin();
917 if (!FromMBB->Probs.empty()) {
918 auto Prob = *FromMBB->Probs.begin();
919 addSuccessor(Succ, Prob);
920 } else
922 FromMBB->removeSuccessor(Succ);
923
924 // Fix up any PHI nodes in the successor.
925 Succ->replacePhiUsesWith(FromMBB, this);
926 }
928}
929
931 return is_contained(predecessors(), MBB);
932}
933
935 return is_contained(successors(), MBB);
936}
937
940 return std::next(I) == MachineFunction::const_iterator(MBB);
941}
942
944 return Successors.size() == 1 ? Successors[0] : nullptr;
945}
946
949 ++Fallthrough;
950 // If FallthroughBlock is off the end of the function, it can't fall through.
951 if (Fallthrough == getParent()->end())
952 return nullptr;
953
954 // If FallthroughBlock isn't a successor, no fallthrough is possible.
955 if (!isSuccessor(&*Fallthrough))
956 return nullptr;
957
958 // Analyze the branches, if any, at the end of the block.
959 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
962 if (TII->analyzeBranch(*this, TBB, FBB, Cond)) {
963 // If we couldn't analyze the branch, examine the last instruction.
964 // If the block doesn't end in a known control barrier, assume fallthrough
965 // is possible. The isPredicated check is needed because this code can be
966 // called during IfConversion, where an instruction which is normally a
967 // Barrier is predicated and thus no longer an actual control barrier.
968 return (empty() || !back().isBarrier() || TII->isPredicated(back()))
969 ? &*Fallthrough
970 : nullptr;
971 }
972
973 // If there is no branch, control always falls through.
974 if (!TBB) return &*Fallthrough;
975
976 // If there is some explicit branch to the fallthrough block, it can obviously
977 // reach, even though the branch should get folded to fall through implicitly.
978 if (!JumpToFallThrough && (MachineFunction::iterator(TBB) == Fallthrough ||
979 MachineFunction::iterator(FBB) == Fallthrough))
980 return &*Fallthrough;
981
982 // If it's an unconditional branch to some block not the fall through, it
983 // doesn't fall through.
984 if (Cond.empty()) return nullptr;
985
986 // Otherwise, if it is conditional and has no explicit false block, it falls
987 // through.
988 return (FBB == nullptr) ? &*Fallthrough : nullptr;
989}
990
992 return getFallThrough() != nullptr;
993}
994
996 bool UpdateLiveIns,
997 LiveIntervals *LIS) {
998 MachineBasicBlock::iterator SplitPoint(&MI);
999 ++SplitPoint;
1000
1001 if (SplitPoint == end()) {
1002 // Don't bother with a new block.
1003 return this;
1004 }
1005
1006 MachineFunction *MF = getParent();
1007
1008 LivePhysRegs LiveRegs;
1009 if (UpdateLiveIns) {
1010 // Make sure we add any physregs we define in the block as liveins to the
1011 // new block.
1013 LiveRegs.init(*MF->getSubtarget().getRegisterInfo());
1014 LiveRegs.addLiveOuts(*this);
1015 for (auto I = rbegin(), E = Prev.getReverse(); I != E; ++I)
1016 LiveRegs.stepBackward(*I);
1017 }
1018
1020
1021 MF->insert(++MachineFunction::iterator(this), SplitBB);
1022 SplitBB->splice(SplitBB->begin(), this, SplitPoint, end());
1023
1024 SplitBB->transferSuccessorsAndUpdatePHIs(this);
1025 addSuccessor(SplitBB);
1026
1027 if (UpdateLiveIns)
1028 addLiveIns(*SplitBB, LiveRegs);
1029
1030 if (LIS)
1031 LIS->insertMBBInMaps(SplitBB);
1032
1033 return SplitBB;
1034}
1035
1037 MachineBasicBlock *Succ, Pass &P,
1038 std::vector<SparseBitVector<>> *LiveInSets) {
1039 if (!canSplitCriticalEdge(Succ))
1040 return nullptr;
1041
1042 MachineFunction *MF = getParent();
1043 MachineBasicBlock *PrevFallthrough = getNextNode();
1044 DebugLoc DL; // FIXME: this is nowhere
1045
1047 MF->insert(std::next(MachineFunction::iterator(this)), NMBB);
1048 LLVM_DEBUG(dbgs() << "Splitting critical edge: " << printMBBReference(*this)
1049 << " -- " << printMBBReference(*NMBB) << " -- "
1050 << printMBBReference(*Succ) << '\n');
1051
1052 LiveIntervals *LIS = P.getAnalysisIfAvailable<LiveIntervals>();
1053 SlotIndexes *Indexes = P.getAnalysisIfAvailable<SlotIndexes>();
1054 if (LIS)
1055 LIS->insertMBBInMaps(NMBB);
1056 else if (Indexes)
1057 Indexes->insertMBBInMaps(NMBB);
1058
1059 // On some targets like Mips, branches may kill virtual registers. Make sure
1060 // that LiveVariables is properly updated after updateTerminator replaces the
1061 // terminators.
1062 LiveVariables *LV = P.getAnalysisIfAvailable<LiveVariables>();
1063
1064 // Collect a list of virtual registers killed by the terminators.
1065 SmallVector<Register, 4> KilledRegs;
1066 if (LV)
1067 for (MachineInstr &MI :
1069 for (MachineOperand &MO : MI.operands()) {
1070 if (!MO.isReg() || MO.getReg() == 0 || !MO.isUse() || !MO.isKill() ||
1071 MO.isUndef())
1072 continue;
1073 Register Reg = MO.getReg();
1074 if (Reg.isPhysical() || LV->getVarInfo(Reg).removeKill(MI)) {
1075 KilledRegs.push_back(Reg);
1076 LLVM_DEBUG(dbgs() << "Removing terminator kill: " << MI);
1077 MO.setIsKill(false);
1078 }
1079 }
1080 }
1081
1082 SmallVector<Register, 4> UsedRegs;
1083 if (LIS) {
1084 for (MachineInstr &MI :
1086 for (const MachineOperand &MO : MI.operands()) {
1087 if (!MO.isReg() || MO.getReg() == 0)
1088 continue;
1089
1090 Register Reg = MO.getReg();
1091 if (!is_contained(UsedRegs, Reg))
1092 UsedRegs.push_back(Reg);
1093 }
1094 }
1095 }
1096
1097 ReplaceUsesOfBlockWith(Succ, NMBB);
1098
1099 // If updateTerminator() removes instructions, we need to remove them from
1100 // SlotIndexes.
1102 if (Indexes) {
1103 for (MachineInstr &MI :
1105 Terminators.push_back(&MI);
1106 }
1107
1108 // Since we replaced all uses of Succ with NMBB, that should also be treated
1109 // as the fallthrough successor
1110 if (Succ == PrevFallthrough)
1111 PrevFallthrough = NMBB;
1112 updateTerminator(PrevFallthrough);
1113
1114 if (Indexes) {
1115 SmallVector<MachineInstr*, 4> NewTerminators;
1116 for (MachineInstr &MI :
1118 NewTerminators.push_back(&MI);
1119
1120 for (MachineInstr *Terminator : Terminators) {
1121 if (!is_contained(NewTerminators, Terminator))
1122 Indexes->removeMachineInstrFromMaps(*Terminator);
1123 }
1124 }
1125
1126 // Insert unconditional "jump Succ" instruction in NMBB if necessary.
1127 NMBB->addSuccessor(Succ);
1128 if (!NMBB->isLayoutSuccessor(Succ)) {
1131 TII->insertBranch(*NMBB, Succ, nullptr, Cond, DL);
1132
1133 if (Indexes) {
1134 for (MachineInstr &MI : NMBB->instrs()) {
1135 // Some instructions may have been moved to NMBB by updateTerminator(),
1136 // so we first remove any instruction that already has an index.
1137 if (Indexes->hasIndex(MI))
1138 Indexes->removeMachineInstrFromMaps(MI);
1139 Indexes->insertMachineInstrInMaps(MI);
1140 }
1141 }
1142 }
1143
1144 // Fix PHI nodes in Succ so they refer to NMBB instead of this.
1145 Succ->replacePhiUsesWith(this, NMBB);
1146
1147 // Inherit live-ins from the successor
1148 for (const auto &LI : Succ->liveins())
1149 NMBB->addLiveIn(LI);
1150
1151 // Update LiveVariables.
1153 if (LV) {
1154 // Restore kills of virtual registers that were killed by the terminators.
1155 while (!KilledRegs.empty()) {
1156 Register Reg = KilledRegs.pop_back_val();
1157 for (instr_iterator I = instr_end(), E = instr_begin(); I != E;) {
1158 if (!(--I)->addRegisterKilled(Reg, TRI, /* AddIfNotFound= */ false))
1159 continue;
1160 if (Reg.isVirtual())
1161 LV->getVarInfo(Reg).Kills.push_back(&*I);
1162 LLVM_DEBUG(dbgs() << "Restored terminator kill: " << *I);
1163 break;
1164 }
1165 }
1166 // Update relevant live-through information.
1167 if (LiveInSets != nullptr)
1168 LV->addNewBlock(NMBB, this, Succ, *LiveInSets);
1169 else
1170 LV->addNewBlock(NMBB, this, Succ);
1171 }
1172
1173 if (LIS) {
1174 // After splitting the edge and updating SlotIndexes, live intervals may be
1175 // in one of two situations, depending on whether this block was the last in
1176 // the function. If the original block was the last in the function, all
1177 // live intervals will end prior to the beginning of the new split block. If
1178 // the original block was not at the end of the function, all live intervals
1179 // will extend to the end of the new split block.
1180
1181 bool isLastMBB =
1182 std::next(MachineFunction::iterator(NMBB)) == getParent()->end();
1183
1184 SlotIndex StartIndex = Indexes->getMBBEndIdx(this);
1185 SlotIndex PrevIndex = StartIndex.getPrevSlot();
1186 SlotIndex EndIndex = Indexes->getMBBEndIdx(NMBB);
1187
1188 // Find the registers used from NMBB in PHIs in Succ.
1189 SmallSet<Register, 8> PHISrcRegs;
1191 I = Succ->instr_begin(), E = Succ->instr_end();
1192 I != E && I->isPHI(); ++I) {
1193 for (unsigned ni = 1, ne = I->getNumOperands(); ni != ne; ni += 2) {
1194 if (I->getOperand(ni+1).getMBB() == NMBB) {
1195 MachineOperand &MO = I->getOperand(ni);
1196 Register Reg = MO.getReg();
1197 PHISrcRegs.insert(Reg);
1198 if (MO.isUndef())
1199 continue;
1200
1201 LiveInterval &LI = LIS->getInterval(Reg);
1202 VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
1203 assert(VNI &&
1204 "PHI sources should be live out of their predecessors.");
1205 LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
1206 }
1207 }
1208 }
1209
1211 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
1213 if (PHISrcRegs.count(Reg) || !LIS->hasInterval(Reg))
1214 continue;
1215
1216 LiveInterval &LI = LIS->getInterval(Reg);
1217 if (!LI.liveAt(PrevIndex))
1218 continue;
1219
1220 bool isLiveOut = LI.liveAt(LIS->getMBBStartIdx(Succ));
1221 if (isLiveOut && isLastMBB) {
1222 VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
1223 assert(VNI && "LiveInterval should have VNInfo where it is live.");
1224 LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
1225 } else if (!isLiveOut && !isLastMBB) {
1226 LI.removeSegment(StartIndex, EndIndex);
1227 }
1228 }
1229
1230 // Update all intervals for registers whose uses may have been modified by
1231 // updateTerminator().
1232 LIS->repairIntervalsInRange(this, getFirstTerminator(), end(), UsedRegs);
1233 }
1234
1235 if (MachineDominatorTree *MDT =
1236 P.getAnalysisIfAvailable<MachineDominatorTree>())
1237 MDT->recordSplitCriticalEdge(this, Succ, NMBB);
1238
1239 if (MachineLoopInfo *MLI = P.getAnalysisIfAvailable<MachineLoopInfo>())
1240 if (MachineLoop *TIL = MLI->getLoopFor(this)) {
1241 // If one or the other blocks were not in a loop, the new block is not
1242 // either, and thus LI doesn't need to be updated.
1243 if (MachineLoop *DestLoop = MLI->getLoopFor(Succ)) {
1244 if (TIL == DestLoop) {
1245 // Both in the same loop, the NMBB joins loop.
1246 DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase());
1247 } else if (TIL->contains(DestLoop)) {
1248 // Edge from an outer loop to an inner loop. Add to the outer loop.
1249 TIL->addBasicBlockToLoop(NMBB, MLI->getBase());
1250 } else if (DestLoop->contains(TIL)) {
1251 // Edge from an inner loop to an outer loop. Add to the outer loop.
1252 DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase());
1253 } else {
1254 // Edge from two loops with no containment relation. Because these
1255 // are natural loops, we know that the destination block must be the
1256 // header of its loop (adding a branch into a loop elsewhere would
1257 // create an irreducible loop).
1258 assert(DestLoop->getHeader() == Succ &&
1259 "Should not create irreducible loops!");
1260 if (MachineLoop *P = DestLoop->getParentLoop())
1261 P->addBasicBlockToLoop(NMBB, MLI->getBase());
1262 }
1263 }
1264 }
1265
1266 return NMBB;
1267}
1268
1270 const MachineBasicBlock *Succ) const {
1271 // Splitting the critical edge to a landing pad block is non-trivial. Don't do
1272 // it in this generic function.
1273 if (Succ->isEHPad())
1274 return false;
1275
1276 // Splitting the critical edge to a callbr's indirect block isn't advised.
1277 // Don't do it in this generic function.
1278 if (Succ->isInlineAsmBrIndirectTarget())
1279 return false;
1280
1281 const MachineFunction *MF = getParent();
1282 // Performance might be harmed on HW that implements branching using exec mask
1283 // where both sides of the branches are always executed.
1284 if (MF->getTarget().requiresStructuredCFG())
1285 return false;
1286
1287 // We may need to update this's terminator, but we can't do that if
1288 // analyzeBranch fails. If this uses a jump table, we won't touch it.
1290 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1292 // AnalyzeBanch should modify this, since we did not allow modification.
1293 if (TII->analyzeBranch(*const_cast<MachineBasicBlock *>(this), TBB, FBB, Cond,
1294 /*AllowModify*/ false))
1295 return false;
1296
1297 // Avoid bugpoint weirdness: A block may end with a conditional branch but
1298 // jumps to the same MBB is either case. We have duplicate CFG edges in that
1299 // case that we can't handle. Since this never happens in properly optimized
1300 // code, just skip those edges.
1301 if (TBB && TBB == FBB) {
1302 LLVM_DEBUG(dbgs() << "Won't split critical edge after degenerate "
1303 << printMBBReference(*this) << '\n');
1304 return false;
1305 }
1306 return true;
1307}
1308
1309/// Prepare MI to be removed from its bundle. This fixes bundle flags on MI's
1310/// neighboring instructions so the bundle won't be broken by removing MI.
1312 // Removing the first instruction in a bundle.
1313 if (MI->isBundledWithSucc() && !MI->isBundledWithPred())
1314 MI->unbundleFromSucc();
1315 // Removing the last instruction in a bundle.
1316 if (MI->isBundledWithPred() && !MI->isBundledWithSucc())
1317 MI->unbundleFromPred();
1318 // If MI is not bundled, or if it is internal to a bundle, the neighbor flags
1319 // are already fine.
1320}
1321
1325 return Insts.erase(I);
1326}
1327
1330 MI->clearFlag(MachineInstr::BundledPred);
1331 MI->clearFlag(MachineInstr::BundledSucc);
1332 return Insts.remove(MI);
1333}
1334
1337 assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
1338 "Cannot insert instruction with bundle flags");
1339 // Set the bundle flags when inserting inside a bundle.
1340 if (I != instr_end() && I->isBundledWithPred()) {
1341 MI->setFlag(MachineInstr::BundledPred);
1342 MI->setFlag(MachineInstr::BundledSucc);
1343 }
1344 return Insts.insert(I, MI);
1345}
1346
1347/// This method unlinks 'this' from the containing function, and returns it, but
1348/// does not delete it.
1350 assert(getParent() && "Not embedded in a function!");
1351 getParent()->remove(this);
1352 return this;
1353}
1354
1355/// This method unlinks 'this' from the containing function, and deletes it.
1357 assert(getParent() && "Not embedded in a function!");
1358 getParent()->erase(this);
1359}
1360
1361/// Given a machine basic block that branched to 'Old', change the code and CFG
1362/// so that it branches to 'New' instead.
1364 MachineBasicBlock *New) {
1365 assert(Old != New && "Cannot replace self with self!");
1366
1368 while (I != instr_begin()) {
1369 --I;
1370 if (!I->isTerminator()) break;
1371
1372 // Scan the operands of this machine instruction, replacing any uses of Old
1373 // with New.
1374 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
1375 if (I->getOperand(i).isMBB() &&
1376 I->getOperand(i).getMBB() == Old)
1377 I->getOperand(i).setMBB(New);
1378 }
1379
1380 // Update the successor information.
1381 replaceSuccessor(Old, New);
1382}
1383
1385 MachineBasicBlock *New) {
1386 for (MachineInstr &MI : phis())
1387 for (unsigned i = 2, e = MI.getNumOperands() + 1; i != e; i += 2) {
1388 MachineOperand &MO = MI.getOperand(i);
1389 if (MO.getMBB() == Old)
1390 MO.setMBB(New);
1391 }
1392}
1393
1394/// Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE
1395/// instructions. Return UnknownLoc if there is none.
1398 // Skip debug declarations, we don't want a DebugLoc from them.
1400 if (MBBI != instr_end())
1401 return MBBI->getDebugLoc();
1402 return {};
1403}
1404
1406 // Skip debug declarations, we don't want a DebugLoc from them.
1408 if (!MBBI->isDebugInstr())
1409 return MBBI->getDebugLoc();
1410 return {};
1411}
1412
1413/// Find the previous valid DebugLoc preceding MBBI, skipping and DBG_VALUE
1414/// instructions. Return UnknownLoc if there is none.
1416 if (MBBI == instr_begin()) return {};
1417 // Skip debug instructions, we don't want a DebugLoc from them.
1419 if (!MBBI->isDebugInstr()) return MBBI->getDebugLoc();
1420 return {};
1421}
1422
1424 if (MBBI == instr_rend())
1425 return {};
1426 // Skip debug declarations, we don't want a DebugLoc from them.
1428 if (MBBI != instr_rend())
1429 return MBBI->getDebugLoc();
1430 return {};
1431}
1432
1433/// Find and return the merged DebugLoc of the branch instructions of the block.
1434/// Return UnknownLoc if there is none.
1437 DebugLoc DL;
1438 auto TI = getFirstTerminator();
1439 while (TI != end() && !TI->isBranch())
1440 ++TI;
1441
1442 if (TI != end()) {
1443 DL = TI->getDebugLoc();
1444 for (++TI ; TI != end() ; ++TI)
1445 if (TI->isBranch())
1446 DL = DILocation::getMergedLocation(DL, TI->getDebugLoc());
1447 }
1448 return DL;
1449}
1450
1451/// Return probability of the edge from this block to MBB.
1454 if (Probs.empty())
1455 return BranchProbability(1, succ_size());
1456
1457 const auto &Prob = *getProbabilityIterator(Succ);
1458 if (Prob.isUnknown()) {
1459 // For unknown probabilities, collect the sum of all known ones, and evenly
1460 // ditribute the complemental of the sum to each unknown probability.
1461 unsigned KnownProbNum = 0;
1462 auto Sum = BranchProbability::getZero();
1463 for (const auto &P : Probs) {
1464 if (!P.isUnknown()) {
1465 Sum += P;
1466 KnownProbNum++;
1467 }
1468 }
1469 return Sum.getCompl() / (Probs.size() - KnownProbNum);
1470 } else
1471 return Prob;
1472}
1473
1474/// Set successor probability of a given iterator.
1476 BranchProbability Prob) {
1477 assert(!Prob.isUnknown());
1478 if (Probs.empty())
1479 return;
1480 *getProbabilityIterator(I) = Prob;
1481}
1482
1483/// Return probability iterator corresonding to the I successor iterator
1484MachineBasicBlock::const_probability_iterator
1485MachineBasicBlock::getProbabilityIterator(
1487 assert(Probs.size() == Successors.size() && "Async probability list!");
1488 const size_t index = std::distance(Successors.begin(), I);
1489 assert(index < Probs.size() && "Not a current successor!");
1490 return Probs.begin() + index;
1491}
1492
1493/// Return probability iterator corresonding to the I successor iterator.
1494MachineBasicBlock::probability_iterator
1495MachineBasicBlock::getProbabilityIterator(MachineBasicBlock::succ_iterator I) {
1496 assert(Probs.size() == Successors.size() && "Async probability list!");
1497 const size_t index = std::distance(Successors.begin(), I);
1498 assert(index < Probs.size() && "Not a current successor!");
1499 return Probs.begin() + index;
1500}
1501
1502/// Return whether (physical) register "Reg" has been <def>ined and not <kill>ed
1503/// as of just before "MI".
1504///
1505/// Search is localised to a neighborhood of
1506/// Neighborhood instructions before (searching for defs or kills) and N
1507/// instructions after (searching just for defs) MI.
1510 MCRegister Reg, const_iterator Before,
1511 unsigned Neighborhood) const {
1512 unsigned N = Neighborhood;
1513
1514 // Try searching forwards from Before, looking for reads or defs.
1515 const_iterator I(Before);
1516 for (; I != end() && N > 0; ++I) {
1517 if (I->isDebugOrPseudoInstr())
1518 continue;
1519
1520 --N;
1521
1523
1524 // Register is live when we read it here.
1525 if (Info.Read)
1526 return LQR_Live;
1527 // Register is dead if we can fully overwrite or clobber it here.
1528 if (Info.FullyDefined || Info.Clobbered)
1529 return LQR_Dead;
1530 }
1531
1532 // If we reached the end, it is safe to clobber Reg at the end of a block of
1533 // no successor has it live in.
1534 if (I == end()) {
1535 for (MachineBasicBlock *S : successors()) {
1536 for (const MachineBasicBlock::RegisterMaskPair &LI : S->liveins()) {
1537 if (TRI->regsOverlap(LI.PhysReg, Reg))
1538 return LQR_Live;
1539 }
1540 }
1541
1542 return LQR_Dead;
1543 }
1544
1545
1546 N = Neighborhood;
1547
1548 // Start by searching backwards from Before, looking for kills, reads or defs.
1549 I = const_iterator(Before);
1550 // If this is the first insn in the block, don't search backwards.
1551 if (I != begin()) {
1552 do {
1553 --I;
1554
1555 if (I->isDebugOrPseudoInstr())
1556 continue;
1557
1558 --N;
1559
1561
1562 // Defs happen after uses so they take precedence if both are present.
1563
1564 // Register is dead after a dead def of the full register.
1565 if (Info.DeadDef)
1566 return LQR_Dead;
1567 // Register is (at least partially) live after a def.
1568 if (Info.Defined) {
1569 if (!Info.PartialDeadDef)
1570 return LQR_Live;
1571 // As soon as we saw a partial definition (dead or not),
1572 // we cannot tell if the value is partial live without
1573 // tracking the lanemasks. We are not going to do this,
1574 // so fall back on the remaining of the analysis.
1575 break;
1576 }
1577 // Register is dead after a full kill or clobber and no def.
1578 if (Info.Killed || Info.Clobbered)
1579 return LQR_Dead;
1580 // Register must be live if we read it.
1581 if (Info.Read)
1582 return LQR_Live;
1583
1584 } while (I != begin() && N > 0);
1585 }
1586
1587 // If all the instructions before this in the block are debug instructions,
1588 // skip over them.
1589 while (I != begin() && std::prev(I)->isDebugOrPseudoInstr())
1590 --I;
1591
1592 // Did we get to the start of the block?
1593 if (I == begin()) {
1594 // If so, the register's state is definitely defined by the live-in state.
1596 if (TRI->regsOverlap(LI.PhysReg, Reg))
1597 return LQR_Live;
1598
1599 return LQR_Dead;
1600 }
1601
1602 // At this point we have no idea of the liveness of the register.
1603 return LQR_Unknown;
1604}
1605
1606const uint32_t *
1608 // EH funclet entry does not preserve any registers.
1609 return isEHFuncletEntry() ? TRI->getNoPreservedMask() : nullptr;
1610}
1611
1612const uint32_t *
1614 // If we see a return block with successors, this must be a funclet return,
1615 // which does not preserve any registers. If there are no successors, we don't
1616 // care what kind of return it is, putting a mask after it is a no-op.
1617 return isReturnBlock() && !succ_empty() ? TRI->getNoPreservedMask() : nullptr;
1618}
1619
1621 LiveIns.clear();
1622}
1623
1625 assert(getParent()->getProperties().hasProperty(
1627 "Liveness information is accurate");
1628 return LiveIns.begin();
1629}
1630
1632 const MachineFunction &MF = *getParent();
1635 "Liveness information is accurate");
1636
1637 const TargetLowering &TLI = *MF.getSubtarget().getTargetLowering();
1638 MCPhysReg ExceptionPointer = 0, ExceptionSelector = 0;
1639 if (MF.getFunction().hasPersonalityFn()) {
1640 auto PersonalityFn = MF.getFunction().getPersonalityFn();
1641 ExceptionPointer = TLI.getExceptionPointerRegister(PersonalityFn);
1642 ExceptionSelector = TLI.getExceptionSelectorRegister(PersonalityFn);
1643 }
1644
1645 return liveout_iterator(*this, ExceptionPointer, ExceptionSelector, false);
1646}
1647
1649 unsigned Cntr = 0;
1650 auto R = instructionsWithoutDebug(begin(), end());
1651 for (auto I = R.begin(), E = R.end(); I != E; ++I) {
1652 if (++Cntr > Limit)
1653 return true;
1654 }
1655 return false;
1656}
1657
1659 uint8_t BBAddrMapVersion = getParent()->getContext().getBBAddrMapVersion();
1660 return BBAddrMapVersion < 2 ? getNumber() : *getBBID();
1661}
1662
1664const MBBSectionID
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
MachineBasicBlock MachineBasicBlock::iterator MBBI
SmallVector< MachineOperand, 4 > Cond
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:492
#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 void unbundleSingleMI(MachineInstr *MI)
Prepare MI to be removed from its bundle.
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
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.
This file describes how to lower LLVM code to machine code.
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
static uint32_t getDenominator()
static BranchProbability getUnknown()
uint32_t getNumerator() const
static BranchProbability getZero()
static const DILocation * getMergedLocation(const DILocation *LocA, const 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:803
Constant * getPersonalityFn() const
Get the personality function associated with this function.
Definition: Function.cpp:1995
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:686
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 segment from this 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:669
Context object for machine code objects.
Definition: MCContext.h:76
uint8_t getBBAddrMapVersion() const
Definition: MCContext.h:684
const MCAsmInfo * getAsmInfo() const
Definition: MCContext.h:446
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:24
MCSymbol - Instances of this class represent a symbol name in the MC file, and MCSymbols are created ...
Definition: MCSymbol.h:41
bool isInlineAsmBrIndirectTarget() const
Returns true if this is the indirect dest of an INLINEASM_BR.
DebugLoc rfindPrevDebugLoc(reverse_instr_iterator MBBI)
Has exact same behavior as findPrevDebugLoc (it also searches from the last to the first MI of this M...
void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB)
Transfers all the successors, as in transferSuccessors, and update PHI operands in the successor bloc...
iterator SkipPHIsLabelsAndDebug(iterator I, bool SkipPseudoOp=true)
Return the first instruction in MBB after I that is not a PHI, label or debug.
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.
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.
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...
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().
std::optional< unsigned > getBBID() const
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.
MachineBasicBlock * getFallThrough(bool JumpToFallThrough=false)
Return the fallthrough block if the block can implicitly transfer control to the block after it by fa...
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.
unsigned getBBIDOrNumber() const
Returns the BBID of the block when BBAddrMapVersion >= 2, otherwise returns MachineBasicBlock::Number...
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.
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 from the first to the last MI of this MBB) ...
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 DBG_VALUE and DBG_LABEL 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 and DBG_VALUE 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.
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.
void copySuccessor(MachineBasicBlock *Orig, succ_iterator I)
Copy a successor (and any probability info) from original block to this block's.
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.
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *bb=nullptr)
CreateMachineBasicBlock - Allocate a new MachineBasicBlock.
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.
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 splice(iterator InsertPt, iterator MBBI)
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:68
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:884
void incorporateFunction(const Function &F)
Incorporate the given function.
Definition: AsmWriter.cpp:870
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:91
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 bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:65
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:82
SlotIndex getPrevSlot() const
Returns the previous slot in the index list.
Definition: SlotIndexes.h:294
SlotIndexes pass.
Definition: SlotIndexes.h:319
SlotIndex getInstructionIndex(const MachineInstr &MI, bool IgnoreBundle=false) const
Returns the base index for the given instruction.
Definition: SlotIndexes.h:390
SlotIndex getMBBStartIdx(unsigned Num) const
Returns the first index in the given basic block number.
Definition: SlotIndexes.h:471
bool hasIndex(const MachineInstr &instr) const
Returns true if the given machine instr is mapped to an index, otherwise returns false.
Definition: SlotIndexes.h:385
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:164
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:177
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:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
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:308
Iterator for intrusive lists based on ilist_node.
MachineBasicBlock * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:289
iterator erase(iterator where)
Definition: ilist.h:268
pointer remove(iterator &IT)
Definition: ilist.h:252
iterator insert(iterator where, pointer New)
Definition: ilist.h:229
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:672
#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:445
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:1755
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:1683
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:124
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:292
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:1762
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1869
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.
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