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>
39using namespace llvm;
40
41#define DEBUG_TYPE "codegen"
42
43static 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
49MachineBasicBlock::MachineBasicBlock(MachineFunction &MF, const BasicBlock *B)
50    : BB(B), Number(-1), xParent(&MF) {
51  Insts.Parent = this;
52  if (B)
53    IrrLoopHeaderWeight = B->getIrrLoopHeaderWeight();
54}
55
56MachineBasicBlock::~MachineBasicBlock() = default;
57
58/// Return the MCSymbol for this basic block.
59MCSymbol *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
90MCSymbol *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
101MCSymbol *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
113raw_ostream &llvm::operator<<(raw_ostream &OS, const MachineBasicBlock &MBB) {
114  MBB.print(OS);
115  return OS;
116}
117
118Printable 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.
129void 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
140void 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.
148void 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.
161void 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.
175void 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
193void ilist_traits<MachineInstr>::deleteNode(MachineInstr *MI) {
194  assert(!MI->getParent() && "MI is still in a block!");
195  Parent->getParent()->deleteMachineInstr(MI);
196}
197
198MachineBasicBlock::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
207MachineBasicBlock::iterator
208MachineBasicBlock::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
222MachineBasicBlock::iterator
223MachineBasicBlock::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
240MachineBasicBlock::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
249MachineBasicBlock::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
258MachineBasicBlock::iterator MachineBasicBlock::getFirstTerminatorForward() {
259  return find_if(instrs(), [](auto &II) { return II.isTerminator(); });
260}
261
262MachineBasicBlock::iterator
263MachineBasicBlock::getFirstNonDebugInstr(bool SkipPseudoOp) {
264  // Skip over begin-of-block dbg_value instructions.
265  return skipDebugInstructionsForward(begin(), end(), SkipPseudoOp);
266}
267
268MachineBasicBlock::iterator
269MachineBasicBlock::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
285bool MachineBasicBlock::hasEHPadSuccessor() const {
286  for (const MachineBasicBlock *Succ : successors())
287    if (Succ->isEHPad())
288      return true;
289  return false;
290}
291
292bool MachineBasicBlock::isEntryBlock() const {
293  return getParent()->begin() == getIterator();
294}
295
296#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
297LLVM_DUMP_METHOD void MachineBasicBlock::dump() const {
298  print(dbgs());
299}
300#endif
301
302bool MachineBasicBlock::mayHaveInlineAsmBr() const {
303  for (const MachineBasicBlock *Succ : successors()) {
304    if (Succ->isInlineAsmBrIndirectTarget())
305      return true;
306  }
307  return false;
308}
309
310bool MachineBasicBlock::isLegalToHoistInto() const {
311  if (isReturnBlock() || hasEHPadSuccessor() || mayHaveInlineAsmBr())
312    return false;
313  return true;
314}
315
316StringRef 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.
324std::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
335void 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
350void 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.
480void MachineBasicBlock::printName(raw_ostream &os, unsigned printNameFlags,
481                                  ModuleSlotTracker *moduleSlotTracker) const {
482  os << "bb." << getNumber();
483  bool hasAttributes = false;
484
485  auto PrintBBRef = [&](const BasicBlock *bb) {
486    os << "%ir-block.";
487    if (bb->hasName()) {
488      os << bb->getName();
489    } else {
490      int slot = -1;
491
492      if (moduleSlotTracker) {
493        slot = moduleSlotTracker->getLocalSlot(bb);
494      } else if (bb->getParent()) {
495        ModuleSlotTracker tmpTracker(bb->getModule(), false);
496        tmpTracker.incorporateFunction(*bb->getParent());
497        slot = tmpTracker.getLocalSlot(bb);
498      }
499
500      if (slot == -1)
501        os << "<ir-block badref>";
502      else
503        os << slot;
504    }
505  };
506
507  if (printNameFlags & PrintNameIr) {
508    if (const auto *bb = getBasicBlock()) {
509      if (bb->hasName()) {
510        os << '.' << bb->getName();
511      } else {
512        hasAttributes = true;
513        os << " (";
514        PrintBBRef(bb);
515      }
516    }
517  }
518
519  if (printNameFlags & PrintNameAttributes) {
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
577void MachineBasicBlock::printAsOperand(raw_ostream &OS,
578                                       bool /*PrintType*/) const {
579  OS << '%';
580  printName(OS, 0);
581}
582
583void 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
594MachineBasicBlock::livein_iterator
595MachineBasicBlock::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
601bool 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
607void 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
627Register
628MachineBasicBlock::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
659void MachineBasicBlock::moveBefore(MachineBasicBlock *NewAfter) {
660  getParent()->splice(NewAfter->getIterator(), getIterator());
661}
662
663void MachineBasicBlock::moveAfter(MachineBasicBlock *NewBefore) {
664  getParent()->splice(++NewBefore->getIterator(), getIterator());
665}
666
667void 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
758void 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
772void 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
782void 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
791void 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
810void MachineBasicBlock::removeSuccessor(MachineBasicBlock *Succ,
811                                        bool NormalizeSuccProbs) {
812  succ_iterator I = find(Successors, Succ);
813  removeSuccessor(I, NormalizeSuccProbs);
814}
815
816MachineBasicBlock::succ_iterator
817MachineBasicBlock::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
833void 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
873void 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
881void MachineBasicBlock::addPredecessor(MachineBasicBlock *Pred) {
882  Predecessors.push_back(Pred);
883}
884
885void MachineBasicBlock::removePredecessor(MachineBasicBlock *Pred) {
886  pred_iterator I = find(Predecessors, Pred);
887  assert(I != Predecessors.end() && "Pred is not a predecessor of this block!");
888  Predecessors.erase(I);
889}
890
891void 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
910void
911MachineBasicBlock::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
930bool MachineBasicBlock::isPredecessor(const MachineBasicBlock *MBB) const {
931  return is_contained(predecessors(), MBB);
932}
933
934bool MachineBasicBlock::isSuccessor(const MachineBasicBlock *MBB) const {
935  return is_contained(successors(), MBB);
936}
937
938bool MachineBasicBlock::isLayoutSuccessor(const MachineBasicBlock *MBB) const {
939  MachineFunction::const_iterator I(this);
940  return std::next(I) == MachineFunction::const_iterator(MBB);
941}
942
943const MachineBasicBlock *MachineBasicBlock::getSingleSuccessor() const {
944  return Successors.size() == 1 ? Successors[0] : nullptr;
945}
946
947MachineBasicBlock *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
991bool MachineBasicBlock::canFallThrough() {
992  return getFallThrough() != nullptr;
993}
994
995MachineBasicBlock *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
1036MachineBasicBlock *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
1269bool 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.
1311static 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
1322MachineBasicBlock::instr_iterator
1323MachineBasicBlock::erase(MachineBasicBlock::instr_iterator I) {
1324  unbundleSingleMI(&*I);
1325  return Insts.erase(I);
1326}
1327
1328MachineInstr *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
1335MachineBasicBlock::instr_iterator
1336MachineBasicBlock::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.
1349MachineBasicBlock *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.
1356void 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.
1363void 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
1384void 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.
1396DebugLoc
1397MachineBasicBlock::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
1405DebugLoc 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.
1415DebugLoc 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
1423DebugLoc 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.
1435DebugLoc
1436MachineBasicBlock::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.
1452BranchProbability
1453MachineBasicBlock::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.
1475void 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
1484MachineBasicBlock::const_probability_iterator
1485MachineBasicBlock::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.
1494MachineBasicBlock::probability_iterator
1495MachineBasicBlock::getProbabilityIterator(MachineBasicBlock::succ_iterator I) {
1496  assert(Probs.size() == Successors.size() && "Async probability list!");
1497  const size_t index = std::distance(Successors.begin(), I);
1498  assert(index < Probs.size() && "Not a current successor!");
1499  return Probs.begin() + index;
1500}
1501
1502/// Return whether (physical) register "Reg" has been <def>ined and not <kill>ed
1503/// as of just before "MI".
1504///
1505/// Search is localised to a neighborhood of
1506/// Neighborhood instructions before (searching for defs or kills) and N
1507/// instructions after (searching just for defs) MI.
1508MachineBasicBlock::LivenessQueryResult
1509MachineBasicBlock::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
1606const uint32_t *
1607MachineBasicBlock::getBeginClobberMask(const TargetRegisterInfo *TRI) const {
1608  // EH funclet entry does not preserve any registers.
1609  return isEHFuncletEntry() ? TRI->getNoPreservedMask() : nullptr;
1610}
1611
1612const uint32_t *
1613MachineBasicBlock::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
1620void MachineBasicBlock::clearLiveIns() {
1621  LiveIns.clear();
1622}
1623
1624MachineBasicBlock::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
1631MachineBasicBlock::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
1648bool 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
1658unsigned MachineBasicBlock::getBBIDOrNumber() const {
1659  uint8_t BBAddrMapVersion = getParent()->getContext().getBBAddrMapVersion();
1660  return BBAddrMapVersion < 2 ? getNumber() : *getBBID();
1661}
1662
1663const MBBSectionID MBBSectionID::ColdSectionID(MBBSectionID::SectionType::Cold);
1664const MBBSectionID
1665    MBBSectionID::ExceptionSectionID(MBBSectionID::SectionType::Exception);
1666