1 //===-- llvm/CodeGen/MachineBasicBlock.cpp ----------------------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 // Collect the sequence of machine instructions for a basic block.
11 //===----------------------------------------------------------------------===//
13 #include "llvm/CodeGen/MachineBasicBlock.h"
14 #include "llvm/ADT/SmallPtrSet.h"
15 #include "llvm/CodeGen/LiveIntervals.h"
16 #include "llvm/CodeGen/LiveVariables.h"
17 #include "llvm/CodeGen/MachineDominators.h"
18 #include "llvm/CodeGen/MachineFunction.h"
19 #include "llvm/CodeGen/MachineInstrBuilder.h"
20 #include "llvm/CodeGen/MachineLoopInfo.h"
21 #include "llvm/CodeGen/MachineRegisterInfo.h"
22 #include "llvm/CodeGen/SlotIndexes.h"
23 #include "llvm/CodeGen/TargetInstrInfo.h"
24 #include "llvm/CodeGen/TargetRegisterInfo.h"
25 #include "llvm/CodeGen/TargetSubtargetInfo.h"
26 #include "llvm/Config/llvm-config.h"
27 #include "llvm/IR/BasicBlock.h"
28 #include "llvm/IR/DataLayout.h"
29 #include "llvm/IR/DebugInfoMetadata.h"
30 #include "llvm/IR/ModuleSlotTracker.h"
31 #include "llvm/MC/MCAsmInfo.h"
32 #include "llvm/MC/MCContext.h"
33 #include "llvm/Support/DataTypes.h"
34 #include "llvm/Support/Debug.h"
35 #include "llvm/Support/raw_ostream.h"
36 #include "llvm/Target/TargetMachine.h"
40 #define DEBUG_TYPE "codegen"
42 static cl::opt
<bool> PrintSlotIndexes(
44 cl::desc("When printing machine IR, annotate instructions and blocks with "
45 "SlotIndexes when available"),
46 cl::init(true), cl::Hidden
);
48 MachineBasicBlock::MachineBasicBlock(MachineFunction
&MF
, const BasicBlock
*B
)
49 : BB(B
), Number(-1), xParent(&MF
) {
52 IrrLoopHeaderWeight
= B
->getIrrLoopHeaderWeight();
55 MachineBasicBlock::~MachineBasicBlock() {
58 /// Return the MCSymbol for this basic block.
59 MCSymbol
*MachineBasicBlock::getSymbol() const {
60 if (!CachedMCSymbol
) {
61 const MachineFunction
*MF
= getParent();
62 MCContext
&Ctx
= MF
->getContext();
63 auto Prefix
= Ctx
.getAsmInfo()->getPrivateLabelPrefix();
64 assert(getNumber() >= 0 && "cannot get label for unreachable MBB");
65 CachedMCSymbol
= Ctx
.getOrCreateSymbol(Twine(Prefix
) + "BB" +
66 Twine(MF
->getFunctionNumber()) +
67 "_" + Twine(getNumber()));
70 return CachedMCSymbol
;
74 raw_ostream
&llvm::operator<<(raw_ostream
&OS
, const MachineBasicBlock
&MBB
) {
79 Printable
llvm::printMBBReference(const MachineBasicBlock
&MBB
) {
80 return Printable([&MBB
](raw_ostream
&OS
) { return MBB
.printAsOperand(OS
); });
83 /// When an MBB is added to an MF, we need to update the parent pointer of the
84 /// MBB, the MBB numbering, and any instructions in the MBB to be on the right
85 /// operand list for registers.
87 /// MBBs start out as #-1. When a MBB is added to a MachineFunction, it
88 /// gets the next available unique MBB number. If it is removed from a
89 /// MachineFunction, it goes back to being #-1.
90 void ilist_callback_traits
<MachineBasicBlock
>::addNodeToList(
91 MachineBasicBlock
*N
) {
92 MachineFunction
&MF
= *N
->getParent();
93 N
->Number
= MF
.addToMBBNumbering(N
);
95 // Make sure the instructions have their operands in the reginfo lists.
96 MachineRegisterInfo
&RegInfo
= MF
.getRegInfo();
97 for (MachineBasicBlock::instr_iterator
98 I
= N
->instr_begin(), E
= N
->instr_end(); I
!= E
; ++I
)
99 I
->AddRegOperandsToUseLists(RegInfo
);
102 void ilist_callback_traits
<MachineBasicBlock
>::removeNodeFromList(
103 MachineBasicBlock
*N
) {
104 N
->getParent()->removeFromMBBNumbering(N
->Number
);
108 /// When we add an instruction to a basic block list, we update its parent
109 /// pointer and add its operands from reg use/def lists if appropriate.
110 void ilist_traits
<MachineInstr
>::addNodeToList(MachineInstr
*N
) {
111 assert(!N
->getParent() && "machine instruction already in a basic block");
112 N
->setParent(Parent
);
114 // Add the instruction's register operands to their corresponding
116 MachineFunction
*MF
= Parent
->getParent();
117 N
->AddRegOperandsToUseLists(MF
->getRegInfo());
118 MF
->handleInsertion(*N
);
121 /// When we remove an instruction from a basic block list, we update its parent
122 /// pointer and remove its operands from reg use/def lists if appropriate.
123 void ilist_traits
<MachineInstr
>::removeNodeFromList(MachineInstr
*N
) {
124 assert(N
->getParent() && "machine instruction not in a basic block");
126 // Remove from the use/def lists.
127 if (MachineFunction
*MF
= N
->getMF()) {
128 MF
->handleRemoval(*N
);
129 N
->RemoveRegOperandsFromUseLists(MF
->getRegInfo());
132 N
->setParent(nullptr);
135 /// When moving a range of instructions from one MBB list to another, we need to
136 /// update the parent pointers and the use/def lists.
137 void ilist_traits
<MachineInstr
>::transferNodesFromList(ilist_traits
&FromList
,
138 instr_iterator First
,
139 instr_iterator Last
) {
140 assert(Parent
->getParent() == FromList
.Parent
->getParent() &&
141 "cannot transfer MachineInstrs between MachineFunctions");
143 // If it's within the same BB, there's nothing to do.
144 if (this == &FromList
)
147 assert(Parent
!= FromList
.Parent
&& "Two lists have the same parent?");
149 // If splicing between two blocks within the same function, just update the
151 for (; First
!= Last
; ++First
)
152 First
->setParent(Parent
);
155 void ilist_traits
<MachineInstr
>::deleteNode(MachineInstr
*MI
) {
156 assert(!MI
->getParent() && "MI is still in a block!");
157 Parent
->getParent()->DeleteMachineInstr(MI
);
160 MachineBasicBlock::iterator
MachineBasicBlock::getFirstNonPHI() {
161 instr_iterator I
= instr_begin(), E
= instr_end();
162 while (I
!= E
&& I
->isPHI())
164 assert((I
== E
|| !I
->isInsideBundle()) &&
165 "First non-phi MI cannot be inside a bundle!");
169 MachineBasicBlock::iterator
170 MachineBasicBlock::SkipPHIsAndLabels(MachineBasicBlock::iterator I
) {
171 const TargetInstrInfo
*TII
= getParent()->getSubtarget().getInstrInfo();
174 while (I
!= E
&& (I
->isPHI() || I
->isPosition() ||
175 TII
->isBasicBlockPrologue(*I
)))
177 // FIXME: This needs to change if we wish to bundle labels
178 // inside the bundle.
179 assert((I
== E
|| !I
->isInsideBundle()) &&
180 "First non-phi / non-label instruction is inside a bundle!");
184 MachineBasicBlock::iterator
185 MachineBasicBlock::SkipPHIsLabelsAndDebug(MachineBasicBlock::iterator I
) {
186 const TargetInstrInfo
*TII
= getParent()->getSubtarget().getInstrInfo();
189 while (I
!= E
&& (I
->isPHI() || I
->isPosition() || I
->isDebugInstr() ||
190 TII
->isBasicBlockPrologue(*I
)))
192 // FIXME: This needs to change if we wish to bundle labels / dbg_values
193 // inside the bundle.
194 assert((I
== E
|| !I
->isInsideBundle()) &&
195 "First non-phi / non-label / non-debug "
196 "instruction is inside a bundle!");
200 MachineBasicBlock::iterator
MachineBasicBlock::getFirstTerminator() {
201 iterator B
= begin(), E
= end(), I
= E
;
202 while (I
!= B
&& ((--I
)->isTerminator() || I
->isDebugInstr()))
204 while (I
!= E
&& !I
->isTerminator())
209 MachineBasicBlock::instr_iterator
MachineBasicBlock::getFirstInstrTerminator() {
210 instr_iterator B
= instr_begin(), E
= instr_end(), I
= E
;
211 while (I
!= B
&& ((--I
)->isTerminator() || I
->isDebugInstr()))
213 while (I
!= E
&& !I
->isTerminator())
218 MachineBasicBlock::iterator
MachineBasicBlock::getFirstNonDebugInstr() {
219 // Skip over begin-of-block dbg_value instructions.
220 return skipDebugInstructionsForward(begin(), end());
223 MachineBasicBlock::iterator
MachineBasicBlock::getLastNonDebugInstr() {
224 // Skip over end-of-block dbg_value instructions.
225 instr_iterator B
= instr_begin(), I
= instr_end();
228 // Return instruction that starts a bundle.
229 if (I
->isDebugInstr() || I
->isInsideBundle())
233 // The block is all debug values.
237 bool MachineBasicBlock::hasEHPadSuccessor() const {
238 for (const_succ_iterator I
= succ_begin(), E
= succ_end(); I
!= E
; ++I
)
244 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
245 LLVM_DUMP_METHOD
void MachineBasicBlock::dump() const {
250 bool MachineBasicBlock::isLegalToHoistInto() const {
251 if (isReturnBlock() || hasEHPadSuccessor())
256 StringRef
MachineBasicBlock::getName() const {
257 if (const BasicBlock
*LBB
= getBasicBlock())
258 return LBB
->getName();
260 return StringRef("", 0);
263 /// Return a hopefully unique identifier for this block.
264 std::string
MachineBasicBlock::getFullName() const {
267 Name
= (getParent()->getName() + ":").str();
269 Name
+= getBasicBlock()->getName();
271 Name
+= ("BB" + Twine(getNumber())).str();
275 void MachineBasicBlock::print(raw_ostream
&OS
, const SlotIndexes
*Indexes
,
276 bool IsStandalone
) const {
277 const MachineFunction
*MF
= getParent();
279 OS
<< "Can't print out MachineBasicBlock because parent MachineFunction"
283 const Function
&F
= MF
->getFunction();
284 const Module
*M
= F
.getParent();
285 ModuleSlotTracker
MST(M
);
286 MST
.incorporateFunction(F
);
287 print(OS
, MST
, Indexes
, IsStandalone
);
290 void MachineBasicBlock::print(raw_ostream
&OS
, ModuleSlotTracker
&MST
,
291 const SlotIndexes
*Indexes
,
292 bool IsStandalone
) const {
293 const MachineFunction
*MF
= getParent();
295 OS
<< "Can't print out MachineBasicBlock because parent MachineFunction"
300 if (Indexes
&& PrintSlotIndexes
)
301 OS
<< Indexes
->getMBBStartIdx(this) << '\t';
303 OS
<< "bb." << getNumber();
304 bool HasAttributes
= false;
305 if (const auto *BB
= getBasicBlock()) {
307 OS
<< "." << BB
->getName();
309 HasAttributes
= true;
311 int Slot
= MST
.getLocalSlot(BB
);
313 OS
<< "<ir-block badref>";
315 OS
<< (Twine("%ir-block.") + Twine(Slot
)).str();
319 if (hasAddressTaken()) {
320 OS
<< (HasAttributes
? ", " : " (");
321 OS
<< "address-taken";
322 HasAttributes
= true;
325 OS
<< (HasAttributes
? ", " : " (");
327 HasAttributes
= true;
329 if (getAlignment() != llvm::Align::None()) {
330 OS
<< (HasAttributes
? ", " : " (");
331 OS
<< "align " << Log2(getAlignment());
332 HasAttributes
= true;
338 const TargetRegisterInfo
*TRI
= MF
->getSubtarget().getRegisterInfo();
339 const MachineRegisterInfo
&MRI
= MF
->getRegInfo();
340 const TargetInstrInfo
&TII
= *getParent()->getSubtarget().getInstrInfo();
341 bool HasLineAttributes
= false;
343 // Print the preds of this block according to the CFG.
344 if (!pred_empty() && IsStandalone
) {
345 if (Indexes
) OS
<< '\t';
346 // Don't indent(2), align with previous line attributes.
347 OS
<< "; predecessors: ";
348 for (auto I
= pred_begin(), E
= pred_end(); I
!= E
; ++I
) {
349 if (I
!= pred_begin())
351 OS
<< printMBBReference(**I
);
354 HasLineAttributes
= true;
358 if (Indexes
) OS
<< '\t';
359 // Print the successors
360 OS
.indent(2) << "successors: ";
361 for (auto I
= succ_begin(), E
= succ_end(); I
!= E
; ++I
) {
362 if (I
!= succ_begin())
364 OS
<< printMBBReference(**I
);
367 << format("0x%08" PRIx32
, getSuccProbability(I
).getNumerator())
370 if (!Probs
.empty() && IsStandalone
) {
371 // Print human readable probabilities as comments.
373 for (auto I
= succ_begin(), E
= succ_end(); I
!= E
; ++I
) {
374 const BranchProbability
&BP
= getSuccProbability(I
);
375 if (I
!= succ_begin())
377 OS
<< printMBBReference(**I
) << '('
379 rint(((double)BP
.getNumerator() / BP
.getDenominator()) *
387 HasLineAttributes
= true;
390 if (!livein_empty() && MRI
.tracksLiveness()) {
391 if (Indexes
) OS
<< '\t';
392 OS
.indent(2) << "liveins: ";
395 for (const auto &LI
: liveins()) {
399 OS
<< printReg(LI
.PhysReg
, TRI
);
400 if (!LI
.LaneMask
.all())
401 OS
<< ":0x" << PrintLaneMask(LI
.LaneMask
);
403 HasLineAttributes
= true;
406 if (HasLineAttributes
)
409 bool IsInBundle
= false;
410 for (const MachineInstr
&MI
: instrs()) {
411 if (Indexes
&& PrintSlotIndexes
) {
412 if (Indexes
->hasIndex(MI
))
413 OS
<< Indexes
->getInstructionIndex(MI
);
417 if (IsInBundle
&& !MI
.isInsideBundle()) {
418 OS
.indent(2) << "}\n";
422 OS
.indent(IsInBundle
? 4 : 2);
423 MI
.print(OS
, MST
, IsStandalone
, /*SkipOpers=*/false, /*SkipDebugLoc=*/false,
424 /*AddNewLine=*/false, &TII
);
426 if (!IsInBundle
&& MI
.getFlag(MachineInstr::BundledSucc
)) {
434 OS
.indent(2) << "}\n";
436 if (IrrLoopHeaderWeight
&& IsStandalone
) {
437 if (Indexes
) OS
<< '\t';
438 OS
.indent(2) << "; Irreducible loop header weight: "
439 << IrrLoopHeaderWeight
.getValue() << '\n';
443 void MachineBasicBlock::printAsOperand(raw_ostream
&OS
,
444 bool /*PrintType*/) const {
445 OS
<< "%bb." << getNumber();
448 void MachineBasicBlock::removeLiveIn(MCPhysReg Reg
, LaneBitmask LaneMask
) {
449 LiveInVector::iterator I
= find_if(
450 LiveIns
, [Reg
](const RegisterMaskPair
&LI
) { return LI
.PhysReg
== Reg
; });
451 if (I
== LiveIns
.end())
454 I
->LaneMask
&= ~LaneMask
;
455 if (I
->LaneMask
.none())
459 MachineBasicBlock::livein_iterator
460 MachineBasicBlock::removeLiveIn(MachineBasicBlock::livein_iterator I
) {
461 // Get non-const version of iterator.
462 LiveInVector::iterator LI
= LiveIns
.begin() + (I
- LiveIns
.begin());
463 return LiveIns
.erase(LI
);
466 bool MachineBasicBlock::isLiveIn(MCPhysReg Reg
, LaneBitmask LaneMask
) const {
467 livein_iterator I
= find_if(
468 LiveIns
, [Reg
](const RegisterMaskPair
&LI
) { return LI
.PhysReg
== Reg
; });
469 return I
!= livein_end() && (I
->LaneMask
& LaneMask
).any();
472 void MachineBasicBlock::sortUniqueLiveIns() {
474 [](const RegisterMaskPair
&LI0
, const RegisterMaskPair
&LI1
) {
475 return LI0
.PhysReg
< LI1
.PhysReg
;
477 // Liveins are sorted by physreg now we can merge their lanemasks.
478 LiveInVector::const_iterator I
= LiveIns
.begin();
479 LiveInVector::const_iterator J
;
480 LiveInVector::iterator Out
= LiveIns
.begin();
481 for (; I
!= LiveIns
.end(); ++Out
, I
= J
) {
482 unsigned PhysReg
= I
->PhysReg
;
483 LaneBitmask LaneMask
= I
->LaneMask
;
484 for (J
= std::next(I
); J
!= LiveIns
.end() && J
->PhysReg
== PhysReg
; ++J
)
485 LaneMask
|= J
->LaneMask
;
486 Out
->PhysReg
= PhysReg
;
487 Out
->LaneMask
= LaneMask
;
489 LiveIns
.erase(Out
, LiveIns
.end());
493 MachineBasicBlock::addLiveIn(MCRegister PhysReg
, const TargetRegisterClass
*RC
) {
494 assert(getParent() && "MBB must be inserted in function");
495 assert(PhysReg
.isPhysical() && "Expected physreg");
496 assert(RC
&& "Register class is required");
497 assert((isEHPad() || this == &getParent()->front()) &&
498 "Only the entry block and landing pads can have physreg live ins");
500 bool LiveIn
= isLiveIn(PhysReg
);
501 iterator I
= SkipPHIsAndLabels(begin()), E
= end();
502 MachineRegisterInfo
&MRI
= getParent()->getRegInfo();
503 const TargetInstrInfo
&TII
= *getParent()->getSubtarget().getInstrInfo();
505 // Look for an existing copy.
507 for (;I
!= E
&& I
->isCopy(); ++I
)
508 if (I
->getOperand(1).getReg() == PhysReg
) {
509 Register VirtReg
= I
->getOperand(0).getReg();
510 if (!MRI
.constrainRegClass(VirtReg
, RC
))
511 llvm_unreachable("Incompatible live-in register class.");
515 // No luck, create a virtual register.
516 Register VirtReg
= MRI
.createVirtualRegister(RC
);
517 BuildMI(*this, I
, DebugLoc(), TII
.get(TargetOpcode::COPY
), VirtReg
)
518 .addReg(PhysReg
, RegState::Kill
);
524 void MachineBasicBlock::moveBefore(MachineBasicBlock
*NewAfter
) {
525 getParent()->splice(NewAfter
->getIterator(), getIterator());
528 void MachineBasicBlock::moveAfter(MachineBasicBlock
*NewBefore
) {
529 getParent()->splice(++NewBefore
->getIterator(), getIterator());
532 void MachineBasicBlock::updateTerminator() {
533 const TargetInstrInfo
*TII
= getParent()->getSubtarget().getInstrInfo();
534 // A block with no successors has no concerns with fall-through edges.
535 if (this->succ_empty())
538 MachineBasicBlock
*TBB
= nullptr, *FBB
= nullptr;
539 SmallVector
<MachineOperand
, 4> Cond
;
540 DebugLoc DL
= findBranchDebugLoc();
541 bool B
= TII
->analyzeBranch(*this, TBB
, FBB
, Cond
);
543 assert(!B
&& "UpdateTerminators requires analyzable predecessors!");
546 // The block has an unconditional branch. If its successor is now its
547 // layout successor, delete the branch.
548 if (isLayoutSuccessor(TBB
))
549 TII
->removeBranch(*this);
551 // The block has an unconditional fallthrough. If its successor is not its
552 // layout successor, insert a branch. First we have to locate the only
553 // non-landing-pad successor, as that is the fallthrough block.
554 for (succ_iterator SI
= succ_begin(), SE
= succ_end(); SI
!= SE
; ++SI
) {
555 if ((*SI
)->isEHPad())
557 assert(!TBB
&& "Found more than one non-landing-pad successor!");
561 // If there is no non-landing-pad successor, the block has no fall-through
562 // edges to be concerned with.
566 // Finally update the unconditional successor to be reached via a branch
567 // if it would not be reached by fallthrough.
568 if (!isLayoutSuccessor(TBB
))
569 TII
->insertBranch(*this, TBB
, nullptr, Cond
, DL
);
575 // The block has a non-fallthrough conditional branch. If one of its
576 // successors is its layout successor, rewrite it to a fallthrough
577 // conditional branch.
578 if (isLayoutSuccessor(TBB
)) {
579 if (TII
->reverseBranchCondition(Cond
))
581 TII
->removeBranch(*this);
582 TII
->insertBranch(*this, FBB
, nullptr, Cond
, DL
);
583 } else if (isLayoutSuccessor(FBB
)) {
584 TII
->removeBranch(*this);
585 TII
->insertBranch(*this, TBB
, nullptr, Cond
, DL
);
590 // Walk through the successors and find the successor which is not a landing
591 // pad and is not the conditional branch destination (in TBB) as the
592 // fallthrough successor.
593 MachineBasicBlock
*FallthroughBB
= nullptr;
594 for (succ_iterator SI
= succ_begin(), SE
= succ_end(); SI
!= SE
; ++SI
) {
595 if ((*SI
)->isEHPad() || *SI
== TBB
)
597 assert(!FallthroughBB
&& "Found more than one fallthrough successor.");
601 if (!FallthroughBB
) {
602 if (canFallThrough()) {
603 // We fallthrough to the same basic block as the conditional jump targets.
604 // Remove the conditional jump, leaving unconditional fallthrough.
605 // FIXME: This does not seem like a reasonable pattern to support, but it
606 // has been seen in the wild coming out of degenerate ARM test cases.
607 TII
->removeBranch(*this);
609 // Finally update the unconditional successor to be reached via a branch if
610 // it would not be reached by fallthrough.
611 if (!isLayoutSuccessor(TBB
))
612 TII
->insertBranch(*this, TBB
, nullptr, Cond
, DL
);
616 // We enter here iff exactly one successor is TBB which cannot fallthrough
617 // and the rest successors if any are EHPads. In this case, we need to
618 // change the conditional branch into unconditional branch.
619 TII
->removeBranch(*this);
621 TII
->insertBranch(*this, TBB
, nullptr, Cond
, DL
);
625 // The block has a fallthrough conditional branch.
626 if (isLayoutSuccessor(TBB
)) {
627 if (TII
->reverseBranchCondition(Cond
)) {
628 // We can't reverse the condition, add an unconditional branch.
630 TII
->insertBranch(*this, FallthroughBB
, nullptr, Cond
, DL
);
633 TII
->removeBranch(*this);
634 TII
->insertBranch(*this, FallthroughBB
, nullptr, Cond
, DL
);
635 } else if (!isLayoutSuccessor(FallthroughBB
)) {
636 TII
->removeBranch(*this);
637 TII
->insertBranch(*this, TBB
, FallthroughBB
, Cond
, DL
);
641 void MachineBasicBlock::validateSuccProbs() const {
644 for (auto Prob
: Probs
)
645 Sum
+= Prob
.getNumerator();
646 // Due to precision issue, we assume that the sum of probabilities is one if
647 // the difference between the sum of their numerators and the denominator is
648 // no greater than the number of successors.
649 assert((uint64_t)std::abs(Sum
- BranchProbability::getDenominator()) <=
651 "The sum of successors's probabilities exceeds one.");
655 void MachineBasicBlock::addSuccessor(MachineBasicBlock
*Succ
,
656 BranchProbability Prob
) {
657 // Probability list is either empty (if successor list isn't empty, this means
658 // disabled optimization) or has the same size as successor list.
659 if (!(Probs
.empty() && !Successors
.empty()))
660 Probs
.push_back(Prob
);
661 Successors
.push_back(Succ
);
662 Succ
->addPredecessor(this);
665 void MachineBasicBlock::addSuccessorWithoutProb(MachineBasicBlock
*Succ
) {
666 // We need to make sure probability list is either empty or has the same size
667 // of successor list. When this function is called, we can safely delete all
668 // probability in the list.
670 Successors
.push_back(Succ
);
671 Succ
->addPredecessor(this);
674 void MachineBasicBlock::splitSuccessor(MachineBasicBlock
*Old
,
675 MachineBasicBlock
*New
,
676 bool NormalizeSuccProbs
) {
677 succ_iterator OldI
= llvm::find(successors(), Old
);
678 assert(OldI
!= succ_end() && "Old is not a successor of this block!");
679 assert(llvm::find(successors(), New
) == succ_end() &&
680 "New is already a successor of this block!");
682 // Add a new successor with equal probability as the original one. Note
683 // that we directly copy the probability using the iterator rather than
684 // getting a potentially synthetic probability computed when unknown. This
685 // preserves the probabilities as-is and then we can renormalize them and
686 // query them effectively afterward.
687 addSuccessor(New
, Probs
.empty() ? BranchProbability::getUnknown()
688 : *getProbabilityIterator(OldI
));
689 if (NormalizeSuccProbs
)
690 normalizeSuccProbs();
693 void MachineBasicBlock::removeSuccessor(MachineBasicBlock
*Succ
,
694 bool NormalizeSuccProbs
) {
695 succ_iterator I
= find(Successors
, Succ
);
696 removeSuccessor(I
, NormalizeSuccProbs
);
699 MachineBasicBlock::succ_iterator
700 MachineBasicBlock::removeSuccessor(succ_iterator I
, bool NormalizeSuccProbs
) {
701 assert(I
!= Successors
.end() && "Not a current successor!");
703 // If probability list is empty it means we don't use it (disabled
705 if (!Probs
.empty()) {
706 probability_iterator WI
= getProbabilityIterator(I
);
708 if (NormalizeSuccProbs
)
709 normalizeSuccProbs();
712 (*I
)->removePredecessor(this);
713 return Successors
.erase(I
);
716 void MachineBasicBlock::replaceSuccessor(MachineBasicBlock
*Old
,
717 MachineBasicBlock
*New
) {
721 succ_iterator E
= succ_end();
722 succ_iterator NewI
= E
;
723 succ_iterator OldI
= E
;
724 for (succ_iterator I
= succ_begin(); I
!= E
; ++I
) {
736 assert(OldI
!= E
&& "Old is not a successor of this block");
738 // If New isn't already a successor, let it take Old's place.
740 Old
->removePredecessor(this);
741 New
->addPredecessor(this);
746 // New is already a successor.
747 // Update its probability instead of adding a duplicate edge.
748 if (!Probs
.empty()) {
749 auto ProbIter
= getProbabilityIterator(NewI
);
750 if (!ProbIter
->isUnknown())
751 *ProbIter
+= *getProbabilityIterator(OldI
);
753 removeSuccessor(OldI
);
756 void MachineBasicBlock::copySuccessor(MachineBasicBlock
*Orig
,
758 if (Orig
->Probs
.empty())
759 addSuccessor(*I
, Orig
->getSuccProbability(I
));
761 addSuccessorWithoutProb(*I
);
764 void MachineBasicBlock::addPredecessor(MachineBasicBlock
*Pred
) {
765 Predecessors
.push_back(Pred
);
768 void MachineBasicBlock::removePredecessor(MachineBasicBlock
*Pred
) {
769 pred_iterator I
= find(Predecessors
, Pred
);
770 assert(I
!= Predecessors
.end() && "Pred is not a predecessor of this block!");
771 Predecessors
.erase(I
);
774 void MachineBasicBlock::transferSuccessors(MachineBasicBlock
*FromMBB
) {
778 while (!FromMBB
->succ_empty()) {
779 MachineBasicBlock
*Succ
= *FromMBB
->succ_begin();
781 // If probability list is empty it means we don't use it (disabled
783 if (!FromMBB
->Probs
.empty()) {
784 auto Prob
= *FromMBB
->Probs
.begin();
785 addSuccessor(Succ
, Prob
);
787 addSuccessorWithoutProb(Succ
);
789 FromMBB
->removeSuccessor(Succ
);
794 MachineBasicBlock::transferSuccessorsAndUpdatePHIs(MachineBasicBlock
*FromMBB
) {
798 while (!FromMBB
->succ_empty()) {
799 MachineBasicBlock
*Succ
= *FromMBB
->succ_begin();
800 if (!FromMBB
->Probs
.empty()) {
801 auto Prob
= *FromMBB
->Probs
.begin();
802 addSuccessor(Succ
, Prob
);
804 addSuccessorWithoutProb(Succ
);
805 FromMBB
->removeSuccessor(Succ
);
807 // Fix up any PHI nodes in the successor.
808 Succ
->replacePhiUsesWith(FromMBB
, this);
810 normalizeSuccProbs();
813 bool MachineBasicBlock::isPredecessor(const MachineBasicBlock
*MBB
) const {
814 return is_contained(predecessors(), MBB
);
817 bool MachineBasicBlock::isSuccessor(const MachineBasicBlock
*MBB
) const {
818 return is_contained(successors(), MBB
);
821 bool MachineBasicBlock::isLayoutSuccessor(const MachineBasicBlock
*MBB
) const {
822 MachineFunction::const_iterator
I(this);
823 return std::next(I
) == MachineFunction::const_iterator(MBB
);
826 MachineBasicBlock
*MachineBasicBlock::getFallThrough() {
827 MachineFunction::iterator Fallthrough
= getIterator();
829 // If FallthroughBlock is off the end of the function, it can't fall through.
830 if (Fallthrough
== getParent()->end())
833 // If FallthroughBlock isn't a successor, no fallthrough is possible.
834 if (!isSuccessor(&*Fallthrough
))
837 // Analyze the branches, if any, at the end of the block.
838 MachineBasicBlock
*TBB
= nullptr, *FBB
= nullptr;
839 SmallVector
<MachineOperand
, 4> Cond
;
840 const TargetInstrInfo
*TII
= getParent()->getSubtarget().getInstrInfo();
841 if (TII
->analyzeBranch(*this, TBB
, FBB
, Cond
)) {
842 // If we couldn't analyze the branch, examine the last instruction.
843 // If the block doesn't end in a known control barrier, assume fallthrough
844 // is possible. The isPredicated check is needed because this code can be
845 // called during IfConversion, where an instruction which is normally a
846 // Barrier is predicated and thus no longer an actual control barrier.
847 return (empty() || !back().isBarrier() || TII
->isPredicated(back()))
852 // If there is no branch, control always falls through.
853 if (!TBB
) return &*Fallthrough
;
855 // If there is some explicit branch to the fallthrough block, it can obviously
856 // reach, even though the branch should get folded to fall through implicitly.
857 if (MachineFunction::iterator(TBB
) == Fallthrough
||
858 MachineFunction::iterator(FBB
) == Fallthrough
)
859 return &*Fallthrough
;
861 // If it's an unconditional branch to some block not the fall through, it
862 // doesn't fall through.
863 if (Cond
.empty()) return nullptr;
865 // Otherwise, if it is conditional and has no explicit false block, it falls
867 return (FBB
== nullptr) ? &*Fallthrough
: nullptr;
870 bool MachineBasicBlock::canFallThrough() {
871 return getFallThrough() != nullptr;
874 MachineBasicBlock
*MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock
*Succ
,
876 if (!canSplitCriticalEdge(Succ
))
879 MachineFunction
*MF
= getParent();
880 DebugLoc DL
; // FIXME: this is nowhere
882 MachineBasicBlock
*NMBB
= MF
->CreateMachineBasicBlock();
883 MF
->insert(std::next(MachineFunction::iterator(this)), NMBB
);
884 LLVM_DEBUG(dbgs() << "Splitting critical edge: " << printMBBReference(*this)
885 << " -- " << printMBBReference(*NMBB
) << " -- "
886 << printMBBReference(*Succ
) << '\n');
888 LiveIntervals
*LIS
= P
.getAnalysisIfAvailable
<LiveIntervals
>();
889 SlotIndexes
*Indexes
= P
.getAnalysisIfAvailable
<SlotIndexes
>();
891 LIS
->insertMBBInMaps(NMBB
);
893 Indexes
->insertMBBInMaps(NMBB
);
895 // On some targets like Mips, branches may kill virtual registers. Make sure
896 // that LiveVariables is properly updated after updateTerminator replaces the
898 LiveVariables
*LV
= P
.getAnalysisIfAvailable
<LiveVariables
>();
900 // Collect a list of virtual registers killed by the terminators.
901 SmallVector
<unsigned, 4> KilledRegs
;
903 for (instr_iterator I
= getFirstInstrTerminator(), E
= instr_end();
905 MachineInstr
*MI
= &*I
;
906 for (MachineInstr::mop_iterator OI
= MI
->operands_begin(),
907 OE
= MI
->operands_end(); OI
!= OE
; ++OI
) {
908 if (!OI
->isReg() || OI
->getReg() == 0 ||
909 !OI
->isUse() || !OI
->isKill() || OI
->isUndef())
911 Register Reg
= OI
->getReg();
912 if (Register::isPhysicalRegister(Reg
) ||
913 LV
->getVarInfo(Reg
).removeKill(*MI
)) {
914 KilledRegs
.push_back(Reg
);
915 LLVM_DEBUG(dbgs() << "Removing terminator kill: " << *MI
);
916 OI
->setIsKill(false);
921 SmallVector
<unsigned, 4> UsedRegs
;
923 for (instr_iterator I
= getFirstInstrTerminator(), E
= instr_end();
925 MachineInstr
*MI
= &*I
;
927 for (MachineInstr::mop_iterator OI
= MI
->operands_begin(),
928 OE
= MI
->operands_end(); OI
!= OE
; ++OI
) {
929 if (!OI
->isReg() || OI
->getReg() == 0)
932 Register Reg
= OI
->getReg();
933 if (!is_contained(UsedRegs
, Reg
))
934 UsedRegs
.push_back(Reg
);
939 ReplaceUsesOfBlockWith(Succ
, NMBB
);
941 // If updateTerminator() removes instructions, we need to remove them from
943 SmallVector
<MachineInstr
*, 4> Terminators
;
945 for (instr_iterator I
= getFirstInstrTerminator(), E
= instr_end();
947 Terminators
.push_back(&*I
);
953 SmallVector
<MachineInstr
*, 4> NewTerminators
;
954 for (instr_iterator I
= getFirstInstrTerminator(), E
= instr_end();
956 NewTerminators
.push_back(&*I
);
958 for (SmallVectorImpl
<MachineInstr
*>::iterator I
= Terminators
.begin(),
959 E
= Terminators
.end(); I
!= E
; ++I
) {
960 if (!is_contained(NewTerminators
, *I
))
961 Indexes
->removeMachineInstrFromMaps(**I
);
965 // Insert unconditional "jump Succ" instruction in NMBB if necessary.
966 NMBB
->addSuccessor(Succ
);
967 if (!NMBB
->isLayoutSuccessor(Succ
)) {
968 SmallVector
<MachineOperand
, 4> Cond
;
969 const TargetInstrInfo
*TII
= getParent()->getSubtarget().getInstrInfo();
970 TII
->insertBranch(*NMBB
, Succ
, nullptr, Cond
, DL
);
973 for (MachineInstr
&MI
: NMBB
->instrs()) {
974 // Some instructions may have been moved to NMBB by updateTerminator(),
975 // so we first remove any instruction that already has an index.
976 if (Indexes
->hasIndex(MI
))
977 Indexes
->removeMachineInstrFromMaps(MI
);
978 Indexes
->insertMachineInstrInMaps(MI
);
983 // Fix PHI nodes in Succ so they refer to NMBB instead of this.
984 Succ
->replacePhiUsesWith(this, NMBB
);
986 // Inherit live-ins from the successor
987 for (const auto &LI
: Succ
->liveins())
990 // Update LiveVariables.
991 const TargetRegisterInfo
*TRI
= MF
->getSubtarget().getRegisterInfo();
993 // Restore kills of virtual registers that were killed by the terminators.
994 while (!KilledRegs
.empty()) {
995 unsigned Reg
= KilledRegs
.pop_back_val();
996 for (instr_iterator I
= instr_end(), E
= instr_begin(); I
!= E
;) {
997 if (!(--I
)->addRegisterKilled(Reg
, TRI
, /* AddIfNotFound= */ false))
999 if (Register::isVirtualRegister(Reg
))
1000 LV
->getVarInfo(Reg
).Kills
.push_back(&*I
);
1001 LLVM_DEBUG(dbgs() << "Restored terminator kill: " << *I
);
1005 // Update relevant live-through information.
1006 LV
->addNewBlock(NMBB
, this, Succ
);
1010 // After splitting the edge and updating SlotIndexes, live intervals may be
1011 // in one of two situations, depending on whether this block was the last in
1012 // the function. If the original block was the last in the function, all
1013 // live intervals will end prior to the beginning of the new split block. If
1014 // the original block was not at the end of the function, all live intervals
1015 // will extend to the end of the new split block.
1018 std::next(MachineFunction::iterator(NMBB
)) == getParent()->end();
1020 SlotIndex StartIndex
= Indexes
->getMBBEndIdx(this);
1021 SlotIndex PrevIndex
= StartIndex
.getPrevSlot();
1022 SlotIndex EndIndex
= Indexes
->getMBBEndIdx(NMBB
);
1024 // Find the registers used from NMBB in PHIs in Succ.
1025 SmallSet
<unsigned, 8> PHISrcRegs
;
1026 for (MachineBasicBlock::instr_iterator
1027 I
= Succ
->instr_begin(), E
= Succ
->instr_end();
1028 I
!= E
&& I
->isPHI(); ++I
) {
1029 for (unsigned ni
= 1, ne
= I
->getNumOperands(); ni
!= ne
; ni
+= 2) {
1030 if (I
->getOperand(ni
+1).getMBB() == NMBB
) {
1031 MachineOperand
&MO
= I
->getOperand(ni
);
1032 Register Reg
= MO
.getReg();
1033 PHISrcRegs
.insert(Reg
);
1037 LiveInterval
&LI
= LIS
->getInterval(Reg
);
1038 VNInfo
*VNI
= LI
.getVNInfoAt(PrevIndex
);
1040 "PHI sources should be live out of their predecessors.");
1041 LI
.addSegment(LiveInterval::Segment(StartIndex
, EndIndex
, VNI
));
1046 MachineRegisterInfo
*MRI
= &getParent()->getRegInfo();
1047 for (unsigned i
= 0, e
= MRI
->getNumVirtRegs(); i
!= e
; ++i
) {
1048 unsigned Reg
= Register::index2VirtReg(i
);
1049 if (PHISrcRegs
.count(Reg
) || !LIS
->hasInterval(Reg
))
1052 LiveInterval
&LI
= LIS
->getInterval(Reg
);
1053 if (!LI
.liveAt(PrevIndex
))
1056 bool isLiveOut
= LI
.liveAt(LIS
->getMBBStartIdx(Succ
));
1057 if (isLiveOut
&& isLastMBB
) {
1058 VNInfo
*VNI
= LI
.getVNInfoAt(PrevIndex
);
1059 assert(VNI
&& "LiveInterval should have VNInfo where it is live.");
1060 LI
.addSegment(LiveInterval::Segment(StartIndex
, EndIndex
, VNI
));
1061 } else if (!isLiveOut
&& !isLastMBB
) {
1062 LI
.removeSegment(StartIndex
, EndIndex
);
1066 // Update all intervals for registers whose uses may have been modified by
1067 // updateTerminator().
1068 LIS
->repairIntervalsInRange(this, getFirstTerminator(), end(), UsedRegs
);
1071 if (MachineDominatorTree
*MDT
=
1072 P
.getAnalysisIfAvailable
<MachineDominatorTree
>())
1073 MDT
->recordSplitCriticalEdge(this, Succ
, NMBB
);
1075 if (MachineLoopInfo
*MLI
= P
.getAnalysisIfAvailable
<MachineLoopInfo
>())
1076 if (MachineLoop
*TIL
= MLI
->getLoopFor(this)) {
1077 // If one or the other blocks were not in a loop, the new block is not
1078 // either, and thus LI doesn't need to be updated.
1079 if (MachineLoop
*DestLoop
= MLI
->getLoopFor(Succ
)) {
1080 if (TIL
== DestLoop
) {
1081 // Both in the same loop, the NMBB joins loop.
1082 DestLoop
->addBasicBlockToLoop(NMBB
, MLI
->getBase());
1083 } else if (TIL
->contains(DestLoop
)) {
1084 // Edge from an outer loop to an inner loop. Add to the outer loop.
1085 TIL
->addBasicBlockToLoop(NMBB
, MLI
->getBase());
1086 } else if (DestLoop
->contains(TIL
)) {
1087 // Edge from an inner loop to an outer loop. Add to the outer loop.
1088 DestLoop
->addBasicBlockToLoop(NMBB
, MLI
->getBase());
1090 // Edge from two loops with no containment relation. Because these
1091 // are natural loops, we know that the destination block must be the
1092 // header of its loop (adding a branch into a loop elsewhere would
1093 // create an irreducible loop).
1094 assert(DestLoop
->getHeader() == Succ
&&
1095 "Should not create irreducible loops!");
1096 if (MachineLoop
*P
= DestLoop
->getParentLoop())
1097 P
->addBasicBlockToLoop(NMBB
, MLI
->getBase());
1105 bool MachineBasicBlock::canSplitCriticalEdge(
1106 const MachineBasicBlock
*Succ
) const {
1107 // Splitting the critical edge to a landing pad block is non-trivial. Don't do
1108 // it in this generic function.
1109 if (Succ
->isEHPad())
1112 const MachineFunction
*MF
= getParent();
1114 // Performance might be harmed on HW that implements branching using exec mask
1115 // where both sides of the branches are always executed.
1116 if (MF
->getTarget().requiresStructuredCFG())
1119 // We may need to update this's terminator, but we can't do that if
1120 // AnalyzeBranch fails. If this uses a jump table, we won't touch it.
1121 const TargetInstrInfo
*TII
= MF
->getSubtarget().getInstrInfo();
1122 MachineBasicBlock
*TBB
= nullptr, *FBB
= nullptr;
1123 SmallVector
<MachineOperand
, 4> Cond
;
1124 // AnalyzeBanch should modify this, since we did not allow modification.
1125 if (TII
->analyzeBranch(*const_cast<MachineBasicBlock
*>(this), TBB
, FBB
, Cond
,
1126 /*AllowModify*/ false))
1129 // Avoid bugpoint weirdness: A block may end with a conditional branch but
1130 // jumps to the same MBB is either case. We have duplicate CFG edges in that
1131 // case that we can't handle. Since this never happens in properly optimized
1132 // code, just skip those edges.
1133 if (TBB
&& TBB
== FBB
) {
1134 LLVM_DEBUG(dbgs() << "Won't split critical edge after degenerate "
1135 << printMBBReference(*this) << '\n');
1141 /// Prepare MI to be removed from its bundle. This fixes bundle flags on MI's
1142 /// neighboring instructions so the bundle won't be broken by removing MI.
1143 static void unbundleSingleMI(MachineInstr
*MI
) {
1144 // Removing the first instruction in a bundle.
1145 if (MI
->isBundledWithSucc() && !MI
->isBundledWithPred())
1146 MI
->unbundleFromSucc();
1147 // Removing the last instruction in a bundle.
1148 if (MI
->isBundledWithPred() && !MI
->isBundledWithSucc())
1149 MI
->unbundleFromPred();
1150 // If MI is not bundled, or if it is internal to a bundle, the neighbor flags
1151 // are already fine.
1154 MachineBasicBlock::instr_iterator
1155 MachineBasicBlock::erase(MachineBasicBlock::instr_iterator I
) {
1156 unbundleSingleMI(&*I
);
1157 return Insts
.erase(I
);
1160 MachineInstr
*MachineBasicBlock::remove_instr(MachineInstr
*MI
) {
1161 unbundleSingleMI(MI
);
1162 MI
->clearFlag(MachineInstr::BundledPred
);
1163 MI
->clearFlag(MachineInstr::BundledSucc
);
1164 return Insts
.remove(MI
);
1167 MachineBasicBlock::instr_iterator
1168 MachineBasicBlock::insert(instr_iterator I
, MachineInstr
*MI
) {
1169 assert(!MI
->isBundledWithPred() && !MI
->isBundledWithSucc() &&
1170 "Cannot insert instruction with bundle flags");
1171 // Set the bundle flags when inserting inside a bundle.
1172 if (I
!= instr_end() && I
->isBundledWithPred()) {
1173 MI
->setFlag(MachineInstr::BundledPred
);
1174 MI
->setFlag(MachineInstr::BundledSucc
);
1176 return Insts
.insert(I
, MI
);
1179 /// This method unlinks 'this' from the containing function, and returns it, but
1180 /// does not delete it.
1181 MachineBasicBlock
*MachineBasicBlock::removeFromParent() {
1182 assert(getParent() && "Not embedded in a function!");
1183 getParent()->remove(this);
1187 /// This method unlinks 'this' from the containing function, and deletes it.
1188 void MachineBasicBlock::eraseFromParent() {
1189 assert(getParent() && "Not embedded in a function!");
1190 getParent()->erase(this);
1193 /// Given a machine basic block that branched to 'Old', change the code and CFG
1194 /// so that it branches to 'New' instead.
1195 void MachineBasicBlock::ReplaceUsesOfBlockWith(MachineBasicBlock
*Old
,
1196 MachineBasicBlock
*New
) {
1197 assert(Old
!= New
&& "Cannot replace self with self!");
1199 MachineBasicBlock::instr_iterator I
= instr_end();
1200 while (I
!= instr_begin()) {
1202 if (!I
->isTerminator()) break;
1204 // Scan the operands of this machine instruction, replacing any uses of Old
1206 for (unsigned i
= 0, e
= I
->getNumOperands(); i
!= e
; ++i
)
1207 if (I
->getOperand(i
).isMBB() &&
1208 I
->getOperand(i
).getMBB() == Old
)
1209 I
->getOperand(i
).setMBB(New
);
1212 // Update the successor information.
1213 replaceSuccessor(Old
, New
);
1216 void MachineBasicBlock::replacePhiUsesWith(MachineBasicBlock
*Old
,
1217 MachineBasicBlock
*New
) {
1218 for (MachineInstr
&MI
: phis())
1219 for (unsigned i
= 2, e
= MI
.getNumOperands() + 1; i
!= e
; i
+= 2) {
1220 MachineOperand
&MO
= MI
.getOperand(i
);
1221 if (MO
.getMBB() == Old
)
1226 /// Various pieces of code can cause excess edges in the CFG to be inserted. If
1227 /// we have proven that MBB can only branch to DestA and DestB, remove any other
1228 /// MBB successors from the CFG. DestA and DestB can be null.
1230 /// Besides DestA and DestB, retain other edges leading to LandingPads
1231 /// (currently there can be only one; we don't check or require that here).
1232 /// Note it is possible that DestA and/or DestB are LandingPads.
1233 bool MachineBasicBlock::CorrectExtraCFGEdges(MachineBasicBlock
*DestA
,
1234 MachineBasicBlock
*DestB
,
1236 // The values of DestA and DestB frequently come from a call to the
1237 // 'TargetInstrInfo::AnalyzeBranch' method. We take our meaning of the initial
1238 // values from there.
1240 // 1. If both DestA and DestB are null, then the block ends with no branches
1241 // (it falls through to its successor).
1242 // 2. If DestA is set, DestB is null, and IsCond is false, then the block ends
1243 // with only an unconditional branch.
1244 // 3. If DestA is set, DestB is null, and IsCond is true, then the block ends
1245 // with a conditional branch that falls through to a successor (DestB).
1246 // 4. If DestA and DestB is set and IsCond is true, then the block ends with a
1247 // conditional branch followed by an unconditional branch. DestA is the
1248 // 'true' destination and DestB is the 'false' destination.
1250 bool Changed
= false;
1252 MachineBasicBlock
*FallThru
= getNextNode();
1254 if (!DestA
&& !DestB
) {
1255 // Block falls through to successor.
1258 } else if (DestA
&& !DestB
) {
1260 // Block ends in conditional jump that falls through to successor.
1263 assert(DestA
&& DestB
&& IsCond
&&
1264 "CFG in a bad state. Cannot correct CFG edges");
1267 // Remove superfluous edges. I.e., those which aren't destinations of this
1268 // basic block, duplicate edges, or landing pads.
1269 SmallPtrSet
<const MachineBasicBlock
*, 8> SeenMBBs
;
1270 MachineBasicBlock::succ_iterator SI
= succ_begin();
1271 while (SI
!= succ_end()) {
1272 const MachineBasicBlock
*MBB
= *SI
;
1273 if (!SeenMBBs
.insert(MBB
).second
||
1274 (MBB
!= DestA
&& MBB
!= DestB
&& !MBB
->isEHPad())) {
1275 // This is a superfluous edge, remove it.
1276 SI
= removeSuccessor(SI
);
1284 normalizeSuccProbs();
1288 /// Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE
1289 /// instructions. Return UnknownLoc if there is none.
1291 MachineBasicBlock::findDebugLoc(instr_iterator MBBI
) {
1292 // Skip debug declarations, we don't want a DebugLoc from them.
1293 MBBI
= skipDebugInstructionsForward(MBBI
, instr_end());
1294 if (MBBI
!= instr_end())
1295 return MBBI
->getDebugLoc();
1299 /// Find the previous valid DebugLoc preceding MBBI, skipping and DBG_VALUE
1300 /// instructions. Return UnknownLoc if there is none.
1301 DebugLoc
MachineBasicBlock::findPrevDebugLoc(instr_iterator MBBI
) {
1302 if (MBBI
== instr_begin()) return {};
1303 // Skip debug declarations, we don't want a DebugLoc from them.
1304 MBBI
= skipDebugInstructionsBackward(std::prev(MBBI
), instr_begin());
1305 if (!MBBI
->isDebugInstr()) return MBBI
->getDebugLoc();
1309 /// Find and return the merged DebugLoc of the branch instructions of the block.
1310 /// Return UnknownLoc if there is none.
1312 MachineBasicBlock::findBranchDebugLoc() {
1314 auto TI
= getFirstTerminator();
1315 while (TI
!= end() && !TI
->isBranch())
1319 DL
= TI
->getDebugLoc();
1320 for (++TI
; TI
!= end() ; ++TI
)
1322 DL
= DILocation::getMergedLocation(DL
, TI
->getDebugLoc());
1327 /// Return probability of the edge from this block to MBB.
1329 MachineBasicBlock::getSuccProbability(const_succ_iterator Succ
) const {
1331 return BranchProbability(1, succ_size());
1333 const auto &Prob
= *getProbabilityIterator(Succ
);
1334 if (Prob
.isUnknown()) {
1335 // For unknown probabilities, collect the sum of all known ones, and evenly
1336 // ditribute the complemental of the sum to each unknown probability.
1337 unsigned KnownProbNum
= 0;
1338 auto Sum
= BranchProbability::getZero();
1339 for (auto &P
: Probs
) {
1340 if (!P
.isUnknown()) {
1345 return Sum
.getCompl() / (Probs
.size() - KnownProbNum
);
1350 /// Set successor probability of a given iterator.
1351 void MachineBasicBlock::setSuccProbability(succ_iterator I
,
1352 BranchProbability Prob
) {
1353 assert(!Prob
.isUnknown());
1356 *getProbabilityIterator(I
) = Prob
;
1359 /// Return probability iterator corresonding to the I successor iterator
1360 MachineBasicBlock::const_probability_iterator
1361 MachineBasicBlock::getProbabilityIterator(
1362 MachineBasicBlock::const_succ_iterator I
) const {
1363 assert(Probs
.size() == Successors
.size() && "Async probability list!");
1364 const size_t index
= std::distance(Successors
.begin(), I
);
1365 assert(index
< Probs
.size() && "Not a current successor!");
1366 return Probs
.begin() + index
;
1369 /// Return probability iterator corresonding to the I successor iterator.
1370 MachineBasicBlock::probability_iterator
1371 MachineBasicBlock::getProbabilityIterator(MachineBasicBlock::succ_iterator I
) {
1372 assert(Probs
.size() == Successors
.size() && "Async probability list!");
1373 const size_t index
= std::distance(Successors
.begin(), I
);
1374 assert(index
< Probs
.size() && "Not a current successor!");
1375 return Probs
.begin() + index
;
1378 /// Return whether (physical) register "Reg" has been <def>ined and not <kill>ed
1379 /// as of just before "MI".
1381 /// Search is localised to a neighborhood of
1382 /// Neighborhood instructions before (searching for defs or kills) and N
1383 /// instructions after (searching just for defs) MI.
1384 MachineBasicBlock::LivenessQueryResult
1385 MachineBasicBlock::computeRegisterLiveness(const TargetRegisterInfo
*TRI
,
1386 unsigned Reg
, const_iterator Before
,
1387 unsigned Neighborhood
) const {
1388 unsigned N
= Neighborhood
;
1390 // Try searching forwards from Before, looking for reads or defs.
1391 const_iterator
I(Before
);
1392 for (; I
!= end() && N
> 0; ++I
) {
1393 if (I
->isDebugInstr())
1398 MachineOperandIteratorBase::PhysRegInfo Info
=
1399 ConstMIOperands(*I
).analyzePhysReg(Reg
, TRI
);
1401 // Register is live when we read it here.
1404 // Register is dead if we can fully overwrite or clobber it here.
1405 if (Info
.FullyDefined
|| Info
.Clobbered
)
1409 // If we reached the end, it is safe to clobber Reg at the end of a block of
1410 // no successor has it live in.
1412 for (MachineBasicBlock
*S
: successors()) {
1413 for (const MachineBasicBlock::RegisterMaskPair
&LI
: S
->liveins()) {
1414 if (TRI
->regsOverlap(LI
.PhysReg
, Reg
))
1425 // Start by searching backwards from Before, looking for kills, reads or defs.
1426 I
= const_iterator(Before
);
1427 // If this is the first insn in the block, don't search backwards.
1432 if (I
->isDebugInstr())
1437 MachineOperandIteratorBase::PhysRegInfo Info
=
1438 ConstMIOperands(*I
).analyzePhysReg(Reg
, TRI
);
1440 // Defs happen after uses so they take precedence if both are present.
1442 // Register is dead after a dead def of the full register.
1445 // Register is (at least partially) live after a def.
1447 if (!Info
.PartialDeadDef
)
1449 // As soon as we saw a partial definition (dead or not),
1450 // we cannot tell if the value is partial live without
1451 // tracking the lanemasks. We are not going to do this,
1452 // so fall back on the remaining of the analysis.
1455 // Register is dead after a full kill or clobber and no def.
1456 if (Info
.Killed
|| Info
.Clobbered
)
1458 // Register must be live if we read it.
1462 } while (I
!= begin() && N
> 0);
1465 // Did we get to the start of the block?
1467 // If so, the register's state is definitely defined by the live-in state.
1468 for (const MachineBasicBlock::RegisterMaskPair
&LI
: liveins())
1469 if (TRI
->regsOverlap(LI
.PhysReg
, Reg
))
1475 // At this point we have no idea of the liveness of the register.
1480 MachineBasicBlock::getBeginClobberMask(const TargetRegisterInfo
*TRI
) const {
1481 // EH funclet entry does not preserve any registers.
1482 return isEHFuncletEntry() ? TRI
->getNoPreservedMask() : nullptr;
1486 MachineBasicBlock::getEndClobberMask(const TargetRegisterInfo
*TRI
) const {
1487 // If we see a return block with successors, this must be a funclet return,
1488 // which does not preserve any registers. If there are no successors, we don't
1489 // care what kind of return it is, putting a mask after it is a no-op.
1490 return isReturnBlock() && !succ_empty() ? TRI
->getNoPreservedMask() : nullptr;
1493 void MachineBasicBlock::clearLiveIns() {
1497 MachineBasicBlock::livein_iterator
MachineBasicBlock::livein_begin() const {
1498 assert(getParent()->getProperties().hasProperty(
1499 MachineFunctionProperties::Property::TracksLiveness
) &&
1500 "Liveness information is accurate");
1501 return LiveIns
.begin();