xref: /freebsd/contrib/llvm-project/llvm/lib/CodeGen/MachineBasicBlock.cpp (revision 7ef62cebc2f965b0f640263e179276928885e33d)
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 
13 #include "llvm/CodeGen/MachineBasicBlock.h"
14 #include "llvm/ADT/STLExtras.h"
15 #include "llvm/CodeGen/LiveIntervals.h"
16 #include "llvm/CodeGen/LivePhysRegs.h"
17 #include "llvm/CodeGen/LiveVariables.h"
18 #include "llvm/CodeGen/MachineDominators.h"
19 #include "llvm/CodeGen/MachineFunction.h"
20 #include "llvm/CodeGen/MachineInstrBuilder.h"
21 #include "llvm/CodeGen/MachineLoopInfo.h"
22 #include "llvm/CodeGen/MachineRegisterInfo.h"
23 #include "llvm/CodeGen/SlotIndexes.h"
24 #include "llvm/CodeGen/TargetInstrInfo.h"
25 #include "llvm/CodeGen/TargetLowering.h"
26 #include "llvm/CodeGen/TargetRegisterInfo.h"
27 #include "llvm/CodeGen/TargetSubtargetInfo.h"
28 #include "llvm/Config/llvm-config.h"
29 #include "llvm/IR/BasicBlock.h"
30 #include "llvm/IR/DebugInfoMetadata.h"
31 #include "llvm/IR/ModuleSlotTracker.h"
32 #include "llvm/MC/MCAsmInfo.h"
33 #include "llvm/MC/MCContext.h"
34 #include "llvm/Support/Debug.h"
35 #include "llvm/Support/raw_ostream.h"
36 #include "llvm/Target/TargetMachine.h"
37 #include <algorithm>
38 #include <cmath>
39 using namespace llvm;
40 
41 #define DEBUG_TYPE "codegen"
42 
43 static cl::opt<bool> PrintSlotIndexes(
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 
49 MachineBasicBlock::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 
56 MachineBasicBlock::~MachineBasicBlock() = default;
57 
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 
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" +
83                                              Twine(MF->getFunctionNumber()) +
84                                              "_" + Twine(getNumber()));
85     }
86   }
87   return CachedMCSymbol;
88 }
89 
90 MCSymbol *MachineBasicBlock::getEHCatchretSymbol() const {
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 
101 MCSymbol *MachineBasicBlock::getEndSymbol() const {
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 
113 raw_ostream &llvm::operator<<(raw_ostream &OS, const MachineBasicBlock &MBB) {
114   MBB.print(OS);
115   return OS;
116 }
117 
118 Printable llvm::printMBBReference(const MachineBasicBlock &MBB) {
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.
129 void ilist_callback_traits<MachineBasicBlock>::addNodeToList(
130     MachineBasicBlock *N) {
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 
140 void ilist_callback_traits<MachineBasicBlock>::removeNodeFromList(
141     MachineBasicBlock *N) {
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.
148 void ilist_traits<MachineInstr>::addNodeToList(MachineInstr *N) {
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.
161 void ilist_traits<MachineInstr>::removeNodeFromList(MachineInstr *N) {
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.
175 void ilist_traits<MachineInstr>::transferNodesFromList(ilist_traits &FromList,
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 
193 void ilist_traits<MachineInstr>::deleteNode(MachineInstr *MI) {
194   assert(!MI->getParent() && "MI is still in a block!");
195   Parent->getParent()->deleteMachineInstr(MI);
196 }
197 
198 MachineBasicBlock::iterator MachineBasicBlock::getFirstNonPHI() {
199   instr_iterator I = instr_begin(), E = instr_end();
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 
207 MachineBasicBlock::iterator
208 MachineBasicBlock::SkipPHIsAndLabels(MachineBasicBlock::iterator I) {
209   const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
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 
222 MachineBasicBlock::iterator
223 MachineBasicBlock::SkipPHIsLabelsAndDebug(MachineBasicBlock::iterator I,
224                                           bool SkipPseudoOp) {
225   const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
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 
240 MachineBasicBlock::iterator MachineBasicBlock::getFirstTerminator() {
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 
249 MachineBasicBlock::instr_iterator MachineBasicBlock::getFirstInstrTerminator() {
250   instr_iterator B = instr_begin(), E = instr_end(), I = E;
251   while (I != B && ((--I)->isTerminator() || I->isDebugInstr()))
252     ; /*noop */
253   while (I != E && !I->isTerminator())
254     ++I;
255   return I;
256 }
257 
258 MachineBasicBlock::iterator MachineBasicBlock::getFirstTerminatorForward() {
259   return find_if(instrs(), [](auto &II) { return II.isTerminator(); });
260 }
261 
262 MachineBasicBlock::iterator
263 MachineBasicBlock::getFirstNonDebugInstr(bool SkipPseudoOp) {
264   // Skip over begin-of-block dbg_value instructions.
265   return skipDebugInstructionsForward(begin(), end(), SkipPseudoOp);
266 }
267 
268 MachineBasicBlock::iterator
269 MachineBasicBlock::getLastNonDebugInstr(bool SkipPseudoOp) {
270   // Skip over end-of-block dbg_value instructions.
271   instr_iterator B = instr_begin(), I = instr_end();
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 
285 bool MachineBasicBlock::hasEHPadSuccessor() const {
286   for (const MachineBasicBlock *Succ : successors())
287     if (Succ->isEHPad())
288       return true;
289   return false;
290 }
291 
292 bool MachineBasicBlock::isEntryBlock() const {
293   return getParent()->begin() == getIterator();
294 }
295 
296 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
297 LLVM_DUMP_METHOD void MachineBasicBlock::dump() const {
298   print(dbgs());
299 }
300 #endif
301 
302 bool MachineBasicBlock::mayHaveInlineAsmBr() const {
303   for (const MachineBasicBlock *Succ : successors()) {
304     if (Succ->isInlineAsmBrIndirectTarget())
305       return true;
306   }
307   return false;
308 }
309 
310 bool MachineBasicBlock::isLegalToHoistInto() const {
311   if (isReturnBlock() || hasEHPadSuccessor() || mayHaveInlineAsmBr())
312     return false;
313   return true;
314 }
315 
316 StringRef MachineBasicBlock::getName() const {
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.
324 std::string MachineBasicBlock::getFullName() const {
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 
335 void MachineBasicBlock::print(raw_ostream &OS, const SlotIndexes *Indexes,
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);
346   MST.incorporateFunction(F);
347   print(OS, MST, Indexes, IsStandalone);
348 }
349 
350 void MachineBasicBlock::print(raw_ostream &OS, ModuleSlotTracker &MST,
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 
363   printName(OS, PrintNameIr | PrintNameAttributes, &MST);
364   OS << ":\n";
365 
366   const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
367   const MachineRegisterInfo &MRI = MF->getRegInfo();
368   const TargetInstrInfo &TII = *getParent()->getSubtarget().getInstrInfo();
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) {
400         const BranchProbability &BP = getSuccProbability(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.
480 void 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) {
520     if (isMachineBlockAddressTaken()) {
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     }
536     if (isInlineAsmBrIndirectTarget()) {
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) {
555       case MBBSectionID::SectionType::Exception:
556         os << "Exception";
557         break;
558       case MBBSectionID::SectionType::Cold:
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 
577 void MachineBasicBlock::printAsOperand(raw_ostream &OS,
578                                        bool /*PrintType*/) const {
579   OS << '%';
580   printName(OS, 0);
581 }
582 
583 void MachineBasicBlock::removeLiveIn(MCPhysReg Reg, LaneBitmask LaneMask) {
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 
594 MachineBasicBlock::livein_iterator
595 MachineBasicBlock::removeLiveIn(MachineBasicBlock::livein_iterator I) {
596   // Get non-const version of iterator.
597   LiveInVector::iterator LI = LiveIns.begin() + (I - LiveIns.begin());
598   return LiveIns.erase(LI);
599 }
600 
601 bool MachineBasicBlock::isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask) const {
602   livein_iterator I = find_if(
603       LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
604   return I != livein_end() && (I->LaneMask & LaneMask).any();
605 }
606 
607 void MachineBasicBlock::sortUniqueLiveIns() {
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 
627 Register
628 MachineBasicBlock::addLiveIn(MCRegister PhysReg, const TargetRegisterClass *RC) {
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);
636   iterator I = SkipPHIsAndLabels(begin()), E = end();
637   MachineRegisterInfo &MRI = getParent()->getRegInfo();
638   const TargetInstrInfo &TII = *getParent()->getSubtarget().getInstrInfo();
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 
659 void MachineBasicBlock::moveBefore(MachineBasicBlock *NewAfter) {
660   getParent()->splice(NewAfter->getIterator(), getIterator());
661 }
662 
663 void MachineBasicBlock::moveAfter(MachineBasicBlock *NewBefore) {
664   getParent()->splice(++NewBefore->getIterator(), getIterator());
665 }
666 
667 void MachineBasicBlock::updateTerminator(
668     MachineBasicBlock *PreviousLayoutSuccessor) {
669   LLVM_DEBUG(dbgs() << "Updating terminators on " << printMBBReference(*this)
670                     << "\n");
671 
672   const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
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;
678   SmallVector<MachineOperand, 4> Cond;
679   DebugLoc DL = findBranchDebugLoc();
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.
687       if (isLayoutSuccessor(TBB))
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)) {
714       if (TII->reverseBranchCondition(Cond))
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)) {
744     if (TII->reverseBranchCondition(Cond)) {
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 
758 void MachineBasicBlock::validateSuccProbs() const {
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.
766   assert((uint64_t)std::abs(Sum - BranchProbability::getDenominator()) <=
767              Probs.size() &&
768          "The sum of successors's probabilities exceeds one.");
769 #endif // NDEBUG
770 }
771 
772 void MachineBasicBlock::addSuccessor(MachineBasicBlock *Succ,
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 
782 void MachineBasicBlock::addSuccessorWithoutProb(MachineBasicBlock *Succ) {
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 
791 void MachineBasicBlock::splitSuccessor(MachineBasicBlock *Old,
792                                        MachineBasicBlock *New,
793                                        bool NormalizeSuccProbs) {
794   succ_iterator OldI = llvm::find(successors(), Old);
795   assert(OldI != succ_end() && "Old is not a successor of this block!");
796   assert(!llvm::is_contained(successors(), New) &&
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)
807     normalizeSuccProbs();
808 }
809 
810 void MachineBasicBlock::removeSuccessor(MachineBasicBlock *Succ,
811                                         bool NormalizeSuccProbs) {
812   succ_iterator I = find(Successors, Succ);
813   removeSuccessor(I, NormalizeSuccProbs);
814 }
815 
816 MachineBasicBlock::succ_iterator
817 MachineBasicBlock::removeSuccessor(succ_iterator I, bool NormalizeSuccProbs) {
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)
826       normalizeSuccProbs();
827   }
828 
829   (*I)->removePredecessor(this);
830   return Successors.erase(I);
831 }
832 
833 void MachineBasicBlock::replaceSuccessor(MachineBasicBlock *Old,
834                                          MachineBasicBlock *New) {
835   if (Old == New)
836     return;
837 
838   succ_iterator E = succ_end();
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 
873 void MachineBasicBlock::copySuccessor(MachineBasicBlock *Orig,
874                                       succ_iterator I) {
875   if (!Orig->Probs.empty())
876     addSuccessor(*I, Orig->getSuccProbability(I));
877   else
878     addSuccessorWithoutProb(*I);
879 }
880 
881 void MachineBasicBlock::addPredecessor(MachineBasicBlock *Pred) {
882   Predecessors.push_back(Pred);
883 }
884 
885 void 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 
891 void MachineBasicBlock::transferSuccessors(MachineBasicBlock *FromMBB) {
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
904       addSuccessorWithoutProb(Succ);
905 
906     FromMBB->removeSuccessor(Succ);
907   }
908 }
909 
910 void
911 MachineBasicBlock::transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB) {
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
921       addSuccessorWithoutProb(Succ);
922     FromMBB->removeSuccessor(Succ);
923 
924     // Fix up any PHI nodes in the successor.
925     Succ->replacePhiUsesWith(FromMBB, this);
926   }
927   normalizeSuccProbs();
928 }
929 
930 bool MachineBasicBlock::isPredecessor(const MachineBasicBlock *MBB) const {
931   return is_contained(predecessors(), MBB);
932 }
933 
934 bool MachineBasicBlock::isSuccessor(const MachineBasicBlock *MBB) const {
935   return is_contained(successors(), MBB);
936 }
937 
938 bool MachineBasicBlock::isLayoutSuccessor(const MachineBasicBlock *MBB) const {
939   MachineFunction::const_iterator I(this);
940   return std::next(I) == MachineFunction::const_iterator(MBB);
941 }
942 
943 const MachineBasicBlock *MachineBasicBlock::getSingleSuccessor() const {
944   return Successors.size() == 1 ? Successors[0] : nullptr;
945 }
946 
947 MachineBasicBlock *MachineBasicBlock::getFallThrough(bool JumpToFallThrough) {
948   MachineFunction::iterator Fallthrough = getIterator();
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;
960   SmallVector<MachineOperand, 4> Cond;
961   const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
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 
991 bool MachineBasicBlock::canFallThrough() {
992   return getFallThrough() != nullptr;
993 }
994 
995 MachineBasicBlock *MachineBasicBlock::splitAt(MachineInstr &MI,
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.
1012     MachineBasicBlock::iterator Prev(&MI);
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 
1019   MachineBasicBlock *SplitBB = MF->CreateMachineBasicBlock(getBasicBlock());
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 
1036 MachineBasicBlock *MachineBasicBlock::SplitCriticalEdge(
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 
1046   MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock();
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 :
1068          llvm::make_range(getFirstInstrTerminator(), instr_end())) {
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 :
1085          llvm::make_range(getFirstInstrTerminator(), instr_end())) {
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.
1101   SmallVector<MachineInstr*, 4> Terminators;
1102   if (Indexes) {
1103     for (MachineInstr &MI :
1104          llvm::make_range(getFirstInstrTerminator(), instr_end()))
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 :
1117          llvm::make_range(getFirstInstrTerminator(), instr_end()))
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)) {
1129     SmallVector<MachineOperand, 4> Cond;
1130     const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
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.
1152   const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
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;
1190     for (MachineBasicBlock::instr_iterator
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 
1210     MachineRegisterInfo *MRI = &getParent()->getRegInfo();
1211     for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
1212       Register Reg = Register::index2VirtReg(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 
1269 bool MachineBasicBlock::canSplitCriticalEdge(
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.
1289   const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
1290   MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1291   SmallVector<MachineOperand, 4> Cond;
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.
1311 static void unbundleSingleMI(MachineInstr *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 
1322 MachineBasicBlock::instr_iterator
1323 MachineBasicBlock::erase(MachineBasicBlock::instr_iterator I) {
1324   unbundleSingleMI(&*I);
1325   return Insts.erase(I);
1326 }
1327 
1328 MachineInstr *MachineBasicBlock::remove_instr(MachineInstr *MI) {
1329   unbundleSingleMI(MI);
1330   MI->clearFlag(MachineInstr::BundledPred);
1331   MI->clearFlag(MachineInstr::BundledSucc);
1332   return Insts.remove(MI);
1333 }
1334 
1335 MachineBasicBlock::instr_iterator
1336 MachineBasicBlock::insert(instr_iterator I, MachineInstr *MI) {
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.
1349 MachineBasicBlock *MachineBasicBlock::removeFromParent() {
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.
1356 void MachineBasicBlock::eraseFromParent() {
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.
1363 void MachineBasicBlock::ReplaceUsesOfBlockWith(MachineBasicBlock *Old,
1364                                                MachineBasicBlock *New) {
1365   assert(Old != New && "Cannot replace self with self!");
1366 
1367   MachineBasicBlock::instr_iterator I = instr_end();
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 
1384 void MachineBasicBlock::replacePhiUsesWith(MachineBasicBlock *Old,
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.
1396 DebugLoc
1397 MachineBasicBlock::findDebugLoc(instr_iterator MBBI) {
1398   // Skip debug declarations, we don't want a DebugLoc from them.
1399   MBBI = skipDebugInstructionsForward(MBBI, instr_end());
1400   if (MBBI != instr_end())
1401     return MBBI->getDebugLoc();
1402   return {};
1403 }
1404 
1405 DebugLoc MachineBasicBlock::rfindDebugLoc(reverse_instr_iterator MBBI) {
1406   // Skip debug declarations, we don't want a DebugLoc from them.
1407   MBBI = skipDebugInstructionsBackward(MBBI, instr_rbegin());
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.
1415 DebugLoc MachineBasicBlock::findPrevDebugLoc(instr_iterator MBBI) {
1416   if (MBBI == instr_begin()) return {};
1417   // Skip debug instructions, we don't want a DebugLoc from them.
1418   MBBI = prev_nodbg(MBBI, instr_begin());
1419   if (!MBBI->isDebugInstr()) return MBBI->getDebugLoc();
1420   return {};
1421 }
1422 
1423 DebugLoc MachineBasicBlock::rfindPrevDebugLoc(reverse_instr_iterator MBBI) {
1424   if (MBBI == instr_rend())
1425     return {};
1426   // Skip debug declarations, we don't want a DebugLoc from them.
1427   MBBI = next_nodbg(MBBI, instr_rend());
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.
1435 DebugLoc
1436 MachineBasicBlock::findBranchDebugLoc() {
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.
1452 BranchProbability
1453 MachineBasicBlock::getSuccProbability(const_succ_iterator Succ) const {
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.
1475 void MachineBasicBlock::setSuccProbability(succ_iterator I,
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
1484 MachineBasicBlock::const_probability_iterator
1485 MachineBasicBlock::getProbabilityIterator(
1486     MachineBasicBlock::const_succ_iterator I) const {
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.
1494 MachineBasicBlock::probability_iterator
1495 MachineBasicBlock::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.
1508 MachineBasicBlock::LivenessQueryResult
1509 MachineBasicBlock::computeRegisterLiveness(const TargetRegisterInfo *TRI,
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 
1522     PhysRegInfo Info = AnalyzePhysRegInBundle(*I, Reg, TRI);
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 
1560       PhysRegInfo Info = AnalyzePhysRegInBundle(*I, Reg, TRI);
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.
1595     for (const MachineBasicBlock::RegisterMaskPair &LI : liveins())
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 
1606 const uint32_t *
1607 MachineBasicBlock::getBeginClobberMask(const TargetRegisterInfo *TRI) const {
1608   // EH funclet entry does not preserve any registers.
1609   return isEHFuncletEntry() ? TRI->getNoPreservedMask() : nullptr;
1610 }
1611 
1612 const uint32_t *
1613 MachineBasicBlock::getEndClobberMask(const TargetRegisterInfo *TRI) const {
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 
1620 void MachineBasicBlock::clearLiveIns() {
1621   LiveIns.clear();
1622 }
1623 
1624 MachineBasicBlock::livein_iterator MachineBasicBlock::livein_begin() const {
1625   assert(getParent()->getProperties().hasProperty(
1626       MachineFunctionProperties::Property::TracksLiveness) &&
1627       "Liveness information is accurate");
1628   return LiveIns.begin();
1629 }
1630 
1631 MachineBasicBlock::liveout_iterator MachineBasicBlock::liveout_begin() const {
1632   const MachineFunction &MF = *getParent();
1633   assert(MF.getProperties().hasProperty(
1634       MachineFunctionProperties::Property::TracksLiveness) &&
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 
1648 bool MachineBasicBlock::sizeWithoutDebugLargerThan(unsigned Limit) const {
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 
1658 unsigned MachineBasicBlock::getBBIDOrNumber() const {
1659   uint8_t BBAddrMapVersion = getParent()->getContext().getBBAddrMapVersion();
1660   return BBAddrMapVersion < 2 ? getNumber() : *getBBID();
1661 }
1662 
1663 const MBBSectionID MBBSectionID::ColdSectionID(MBBSectionID::SectionType::Cold);
1664 const MBBSectionID
1665     MBBSectionID::ExceptionSectionID(MBBSectionID::SectionType::Exception);
1666