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/SmallPtrSet.h"
15#include "llvm/CodeGen/LiveIntervals.h"
16#include "llvm/CodeGen/LiveVariables.h"
17#include "llvm/CodeGen/MachineDominators.h"
18#include "llvm/CodeGen/MachineFunction.h"
19#include "llvm/CodeGen/MachineInstrBuilder.h"
20#include "llvm/CodeGen/MachineLoopInfo.h"
21#include "llvm/CodeGen/MachineRegisterInfo.h"
22#include "llvm/CodeGen/SlotIndexes.h"
23#include "llvm/CodeGen/TargetInstrInfo.h"
24#include "llvm/CodeGen/TargetRegisterInfo.h"
25#include "llvm/CodeGen/TargetSubtargetInfo.h"
26#include "llvm/Config/llvm-config.h"
27#include "llvm/IR/BasicBlock.h"
28#include "llvm/IR/DataLayout.h"
29#include "llvm/IR/DebugInfoMetadata.h"
30#include "llvm/IR/ModuleSlotTracker.h"
31#include "llvm/MC/MCAsmInfo.h"
32#include "llvm/MC/MCContext.h"
33#include "llvm/Support/DataTypes.h"
34#include "llvm/Support/Debug.h"
35#include "llvm/Support/raw_ostream.h"
36#include "llvm/Target/TargetMachine.h"
37#include <algorithm>
38using namespace llvm;
39
40#define DEBUG_TYPE "codegen"
41
42static cl::opt<bool> PrintSlotIndexes(
43    "print-slotindexes",
44    cl::desc("When printing machine IR, annotate instructions and blocks with "
45             "SlotIndexes when available"),
46    cl::init(true), cl::Hidden);
47
48MachineBasicBlock::MachineBasicBlock(MachineFunction &MF, const BasicBlock *B)
49    : BB(B), Number(-1), xParent(&MF) {
50  Insts.Parent = this;
51  if (B)
52    IrrLoopHeaderWeight = B->getIrrLoopHeaderWeight();
53}
54
55MachineBasicBlock::~MachineBasicBlock() {
56}
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    auto Prefix = Ctx.getAsmInfo()->getPrivateLabelPrefix();
64    assert(getNumber() >= 0 && "cannot get label for unreachable MBB");
65    CachedMCSymbol = Ctx.getOrCreateSymbol(Twine(Prefix) + "BB" +
66                                           Twine(MF->getFunctionNumber()) +
67                                           "_" + Twine(getNumber()));
68  }
69
70  return CachedMCSymbol;
71}
72
73
74raw_ostream &llvm::operator<<(raw_ostream &OS, const MachineBasicBlock &MBB) {
75  MBB.print(OS);
76  return OS;
77}
78
79Printable llvm::printMBBReference(const MachineBasicBlock &MBB) {
80  return Printable([&MBB](raw_ostream &OS) { return MBB.printAsOperand(OS); });
81}
82
83/// When an MBB is added to an MF, we need to update the parent pointer of the
84/// MBB, the MBB numbering, and any instructions in the MBB to be on the right
85/// operand list for registers.
86///
87/// MBBs start out as #-1. When a MBB is added to a MachineFunction, it
88/// gets the next available unique MBB number. If it is removed from a
89/// MachineFunction, it goes back to being #-1.
90void ilist_callback_traits<MachineBasicBlock>::addNodeToList(
91    MachineBasicBlock *N) {
92  MachineFunction &MF = *N->getParent();
93  N->Number = MF.addToMBBNumbering(N);
94
95  // Make sure the instructions have their operands in the reginfo lists.
96  MachineRegisterInfo &RegInfo = MF.getRegInfo();
97  for (MachineBasicBlock::instr_iterator
98         I = N->instr_begin(), E = N->instr_end(); I != E; ++I)
99    I->AddRegOperandsToUseLists(RegInfo);
100}
101
102void ilist_callback_traits<MachineBasicBlock>::removeNodeFromList(
103    MachineBasicBlock *N) {
104  N->getParent()->removeFromMBBNumbering(N->Number);
105  N->Number = -1;
106}
107
108/// When we add an instruction to a basic block list, we update its parent
109/// pointer and add its operands from reg use/def lists if appropriate.
110void ilist_traits<MachineInstr>::addNodeToList(MachineInstr *N) {
111  assert(!N->getParent() && "machine instruction already in a basic block");
112  N->setParent(Parent);
113
114  // Add the instruction's register operands to their corresponding
115  // use/def lists.
116  MachineFunction *MF = Parent->getParent();
117  N->AddRegOperandsToUseLists(MF->getRegInfo());
118  MF->handleInsertion(*N);
119}
120
121/// When we remove an instruction from a basic block list, we update its parent
122/// pointer and remove its operands from reg use/def lists if appropriate.
123void ilist_traits<MachineInstr>::removeNodeFromList(MachineInstr *N) {
124  assert(N->getParent() && "machine instruction not in a basic block");
125
126  // Remove from the use/def lists.
127  if (MachineFunction *MF = N->getMF()) {
128    MF->handleRemoval(*N);
129    N->RemoveRegOperandsFromUseLists(MF->getRegInfo());
130  }
131
132  N->setParent(nullptr);
133}
134
135/// When moving a range of instructions from one MBB list to another, we need to
136/// update the parent pointers and the use/def lists.
137void ilist_traits<MachineInstr>::transferNodesFromList(ilist_traits &FromList,
138                                                       instr_iterator First,
139                                                       instr_iterator Last) {
140  assert(Parent->getParent() == FromList.Parent->getParent() &&
141         "cannot transfer MachineInstrs between MachineFunctions");
142
143  // If it's within the same BB, there's nothing to do.
144  if (this == &FromList)
145    return;
146
147  assert(Parent != FromList.Parent && "Two lists have the same parent?");
148
149  // If splicing between two blocks within the same function, just update the
150  // parent pointers.
151  for (; First != Last; ++First)
152    First->setParent(Parent);
153}
154
155void ilist_traits<MachineInstr>::deleteNode(MachineInstr *MI) {
156  assert(!MI->getParent() && "MI is still in a block!");
157  Parent->getParent()->DeleteMachineInstr(MI);
158}
159
160MachineBasicBlock::iterator MachineBasicBlock::getFirstNonPHI() {
161  instr_iterator I = instr_begin(), E = instr_end();
162  while (I != E && I->isPHI())
163    ++I;
164  assert((I == E || !I->isInsideBundle()) &&
165         "First non-phi MI cannot be inside a bundle!");
166  return I;
167}
168
169MachineBasicBlock::iterator
170MachineBasicBlock::SkipPHIsAndLabels(MachineBasicBlock::iterator I) {
171  const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
172
173  iterator E = end();
174  while (I != E && (I->isPHI() || I->isPosition() ||
175                    TII->isBasicBlockPrologue(*I)))
176    ++I;
177  // FIXME: This needs to change if we wish to bundle labels
178  // inside the bundle.
179  assert((I == E || !I->isInsideBundle()) &&
180         "First non-phi / non-label instruction is inside a bundle!");
181  return I;
182}
183
184MachineBasicBlock::iterator
185MachineBasicBlock::SkipPHIsLabelsAndDebug(MachineBasicBlock::iterator I) {
186  const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
187
188  iterator E = end();
189  while (I != E && (I->isPHI() || I->isPosition() || I->isDebugInstr() ||
190                    TII->isBasicBlockPrologue(*I)))
191    ++I;
192  // FIXME: This needs to change if we wish to bundle labels / dbg_values
193  // inside the bundle.
194  assert((I == E || !I->isInsideBundle()) &&
195         "First non-phi / non-label / non-debug "
196         "instruction is inside a bundle!");
197  return I;
198}
199
200MachineBasicBlock::iterator MachineBasicBlock::getFirstTerminator() {
201  iterator B = begin(), E = end(), I = E;
202  while (I != B && ((--I)->isTerminator() || I->isDebugInstr()))
203    ; /*noop */
204  while (I != E && !I->isTerminator())
205    ++I;
206  return I;
207}
208
209MachineBasicBlock::instr_iterator MachineBasicBlock::getFirstInstrTerminator() {
210  instr_iterator B = instr_begin(), E = instr_end(), I = E;
211  while (I != B && ((--I)->isTerminator() || I->isDebugInstr()))
212    ; /*noop */
213  while (I != E && !I->isTerminator())
214    ++I;
215  return I;
216}
217
218MachineBasicBlock::iterator MachineBasicBlock::getFirstNonDebugInstr() {
219  // Skip over begin-of-block dbg_value instructions.
220  return skipDebugInstructionsForward(begin(), end());
221}
222
223MachineBasicBlock::iterator MachineBasicBlock::getLastNonDebugInstr() {
224  // Skip over end-of-block dbg_value instructions.
225  instr_iterator B = instr_begin(), I = instr_end();
226  while (I != B) {
227    --I;
228    // Return instruction that starts a bundle.
229    if (I->isDebugInstr() || I->isInsideBundle())
230      continue;
231    return I;
232  }
233  // The block is all debug values.
234  return end();
235}
236
237bool MachineBasicBlock::hasEHPadSuccessor() const {
238  for (const_succ_iterator I = succ_begin(), E = succ_end(); I != E; ++I)
239    if ((*I)->isEHPad())
240      return true;
241  return false;
242}
243
244#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
245LLVM_DUMP_METHOD void MachineBasicBlock::dump() const {
246  print(dbgs());
247}
248#endif
249
250bool MachineBasicBlock::isLegalToHoistInto() const {
251  if (isReturnBlock() || hasEHPadSuccessor())
252    return false;
253  return true;
254}
255
256StringRef MachineBasicBlock::getName() const {
257  if (const BasicBlock *LBB = getBasicBlock())
258    return LBB->getName();
259  else
260    return StringRef("", 0);
261}
262
263/// Return a hopefully unique identifier for this block.
264std::string MachineBasicBlock::getFullName() const {
265  std::string Name;
266  if (getParent())
267    Name = (getParent()->getName() + ":").str();
268  if (getBasicBlock())
269    Name += getBasicBlock()->getName();
270  else
271    Name += ("BB" + Twine(getNumber())).str();
272  return Name;
273}
274
275void MachineBasicBlock::print(raw_ostream &OS, const SlotIndexes *Indexes,
276                              bool IsStandalone) const {
277  const MachineFunction *MF = getParent();
278  if (!MF) {
279    OS << "Can't print out MachineBasicBlock because parent MachineFunction"
280       << " is null\n";
281    return;
282  }
283  const Function &F = MF->getFunction();
284  const Module *M = F.getParent();
285  ModuleSlotTracker MST(M);
286  MST.incorporateFunction(F);
287  print(OS, MST, Indexes, IsStandalone);
288}
289
290void MachineBasicBlock::print(raw_ostream &OS, ModuleSlotTracker &MST,
291                              const SlotIndexes *Indexes,
292                              bool IsStandalone) const {
293  const MachineFunction *MF = getParent();
294  if (!MF) {
295    OS << "Can't print out MachineBasicBlock because parent MachineFunction"
296       << " is null\n";
297    return;
298  }
299
300  if (Indexes && PrintSlotIndexes)
301    OS << Indexes->getMBBStartIdx(this) << '\t';
302
303  OS << "bb." << getNumber();
304  bool HasAttributes = false;
305  if (const auto *BB = getBasicBlock()) {
306    if (BB->hasName()) {
307      OS << "." << BB->getName();
308    } else {
309      HasAttributes = true;
310      OS << " (";
311      int Slot = MST.getLocalSlot(BB);
312      if (Slot == -1)
313        OS << "<ir-block badref>";
314      else
315        OS << (Twine("%ir-block.") + Twine(Slot)).str();
316    }
317  }
318
319  if (hasAddressTaken()) {
320    OS << (HasAttributes ? ", " : " (");
321    OS << "address-taken";
322    HasAttributes = true;
323  }
324  if (isEHPad()) {
325    OS << (HasAttributes ? ", " : " (");
326    OS << "landing-pad";
327    HasAttributes = true;
328  }
329  if (getAlignment() != Align::None()) {
330    OS << (HasAttributes ? ", " : " (");
331    OS << "align " << Log2(getAlignment());
332    HasAttributes = true;
333  }
334  if (HasAttributes)
335    OS << ")";
336  OS << ":\n";
337
338  const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
339  const MachineRegisterInfo &MRI = MF->getRegInfo();
340  const TargetInstrInfo &TII = *getParent()->getSubtarget().getInstrInfo();
341  bool HasLineAttributes = false;
342
343  // Print the preds of this block according to the CFG.
344  if (!pred_empty() && IsStandalone) {
345    if (Indexes) OS << '\t';
346    // Don't indent(2), align with previous line attributes.
347    OS << "; predecessors: ";
348    for (auto I = pred_begin(), E = pred_end(); I != E; ++I) {
349      if (I != pred_begin())
350        OS << ", ";
351      OS << printMBBReference(**I);
352    }
353    OS << '\n';
354    HasLineAttributes = true;
355  }
356
357  if (!succ_empty()) {
358    if (Indexes) OS << '\t';
359    // Print the successors
360    OS.indent(2) << "successors: ";
361    for (auto I = succ_begin(), E = succ_end(); I != E; ++I) {
362      if (I != succ_begin())
363        OS << ", ";
364      OS << printMBBReference(**I);
365      if (!Probs.empty())
366        OS << '('
367           << format("0x%08" PRIx32, getSuccProbability(I).getNumerator())
368           << ')';
369    }
370    if (!Probs.empty() && IsStandalone) {
371      // Print human readable probabilities as comments.
372      OS << "; ";
373      for (auto I = succ_begin(), E = succ_end(); I != E; ++I) {
374        const BranchProbability &BP = getSuccProbability(I);
375        if (I != succ_begin())
376          OS << ", ";
377        OS << printMBBReference(**I) << '('
378           << format("%.2f%%",
379                     rint(((double)BP.getNumerator() / BP.getDenominator()) *
380                          100.0 * 100.0) /
381                         100.0)
382           << ')';
383      }
384    }
385
386    OS << '\n';
387    HasLineAttributes = true;
388  }
389
390  if (!livein_empty() && MRI.tracksLiveness()) {
391    if (Indexes) OS << '\t';
392    OS.indent(2) << "liveins: ";
393
394    bool First = true;
395    for (const auto &LI : liveins()) {
396      if (!First)
397        OS << ", ";
398      First = false;
399      OS << printReg(LI.PhysReg, TRI);
400      if (!LI.LaneMask.all())
401        OS << ":0x" << PrintLaneMask(LI.LaneMask);
402    }
403    HasLineAttributes = true;
404  }
405
406  if (HasLineAttributes)
407    OS << '\n';
408
409  bool IsInBundle = false;
410  for (const MachineInstr &MI : instrs()) {
411    if (Indexes && PrintSlotIndexes) {
412      if (Indexes->hasIndex(MI))
413        OS << Indexes->getInstructionIndex(MI);
414      OS << '\t';
415    }
416
417    if (IsInBundle && !MI.isInsideBundle()) {
418      OS.indent(2) << "}\n";
419      IsInBundle = false;
420    }
421
422    OS.indent(IsInBundle ? 4 : 2);
423    MI.print(OS, MST, IsStandalone, /*SkipOpers=*/false, /*SkipDebugLoc=*/false,
424             /*AddNewLine=*/false, &TII);
425
426    if (!IsInBundle && MI.getFlag(MachineInstr::BundledSucc)) {
427      OS << " {";
428      IsInBundle = true;
429    }
430    OS << '\n';
431  }
432
433  if (IsInBundle)
434    OS.indent(2) << "}\n";
435
436  if (IrrLoopHeaderWeight && IsStandalone) {
437    if (Indexes) OS << '\t';
438    OS.indent(2) << "; Irreducible loop header weight: "
439                 << IrrLoopHeaderWeight.getValue() << '\n';
440  }
441}
442
443void MachineBasicBlock::printAsOperand(raw_ostream &OS,
444                                       bool /*PrintType*/) const {
445  OS << "%bb." << getNumber();
446}
447
448void MachineBasicBlock::removeLiveIn(MCPhysReg Reg, LaneBitmask LaneMask) {
449  LiveInVector::iterator I = find_if(
450      LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
451  if (I == LiveIns.end())
452    return;
453
454  I->LaneMask &= ~LaneMask;
455  if (I->LaneMask.none())
456    LiveIns.erase(I);
457}
458
459MachineBasicBlock::livein_iterator
460MachineBasicBlock::removeLiveIn(MachineBasicBlock::livein_iterator I) {
461  // Get non-const version of iterator.
462  LiveInVector::iterator LI = LiveIns.begin() + (I - LiveIns.begin());
463  return LiveIns.erase(LI);
464}
465
466bool MachineBasicBlock::isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask) const {
467  livein_iterator I = find_if(
468      LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
469  return I != livein_end() && (I->LaneMask & LaneMask).any();
470}
471
472void MachineBasicBlock::sortUniqueLiveIns() {
473  llvm::sort(LiveIns,
474             [](const RegisterMaskPair &LI0, const RegisterMaskPair &LI1) {
475               return LI0.PhysReg < LI1.PhysReg;
476             });
477  // Liveins are sorted by physreg now we can merge their lanemasks.
478  LiveInVector::const_iterator I = LiveIns.begin();
479  LiveInVector::const_iterator J;
480  LiveInVector::iterator Out = LiveIns.begin();
481  for (; I != LiveIns.end(); ++Out, I = J) {
482    unsigned PhysReg = I->PhysReg;
483    LaneBitmask LaneMask = I->LaneMask;
484    for (J = std::next(I); J != LiveIns.end() && J->PhysReg == PhysReg; ++J)
485      LaneMask |= J->LaneMask;
486    Out->PhysReg = PhysReg;
487    Out->LaneMask = LaneMask;
488  }
489  LiveIns.erase(Out, LiveIns.end());
490}
491
492unsigned
493MachineBasicBlock::addLiveIn(MCRegister PhysReg, const TargetRegisterClass *RC) {
494  assert(getParent() && "MBB must be inserted in function");
495  assert(PhysReg.isPhysical() && "Expected physreg");
496  assert(RC && "Register class is required");
497  assert((isEHPad() || this == &getParent()->front()) &&
498         "Only the entry block and landing pads can have physreg live ins");
499
500  bool LiveIn = isLiveIn(PhysReg);
501  iterator I = SkipPHIsAndLabels(begin()), E = end();
502  MachineRegisterInfo &MRI = getParent()->getRegInfo();
503  const TargetInstrInfo &TII = *getParent()->getSubtarget().getInstrInfo();
504
505  // Look for an existing copy.
506  if (LiveIn)
507    for (;I != E && I->isCopy(); ++I)
508      if (I->getOperand(1).getReg() == PhysReg) {
509        Register VirtReg = I->getOperand(0).getReg();
510        if (!MRI.constrainRegClass(VirtReg, RC))
511          llvm_unreachable("Incompatible live-in register class.");
512        return VirtReg;
513      }
514
515  // No luck, create a virtual register.
516  Register VirtReg = MRI.createVirtualRegister(RC);
517  BuildMI(*this, I, DebugLoc(), TII.get(TargetOpcode::COPY), VirtReg)
518    .addReg(PhysReg, RegState::Kill);
519  if (!LiveIn)
520    addLiveIn(PhysReg);
521  return VirtReg;
522}
523
524void MachineBasicBlock::moveBefore(MachineBasicBlock *NewAfter) {
525  getParent()->splice(NewAfter->getIterator(), getIterator());
526}
527
528void MachineBasicBlock::moveAfter(MachineBasicBlock *NewBefore) {
529  getParent()->splice(++NewBefore->getIterator(), getIterator());
530}
531
532void MachineBasicBlock::updateTerminator() {
533  const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
534  // A block with no successors has no concerns with fall-through edges.
535  if (this->succ_empty())
536    return;
537
538  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
539  SmallVector<MachineOperand, 4> Cond;
540  DebugLoc DL = findBranchDebugLoc();
541  bool B = TII->analyzeBranch(*this, TBB, FBB, Cond);
542  (void) B;
543  assert(!B && "UpdateTerminators requires analyzable predecessors!");
544  if (Cond.empty()) {
545    if (TBB) {
546      // The block has an unconditional branch. If its successor is now its
547      // layout successor, delete the branch.
548      if (isLayoutSuccessor(TBB))
549        TII->removeBranch(*this);
550    } else {
551      // The block has an unconditional fallthrough. If its successor is not its
552      // layout successor, insert a branch. First we have to locate the only
553      // non-landing-pad successor, as that is the fallthrough block.
554      for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; ++SI) {
555        if ((*SI)->isEHPad())
556          continue;
557        assert(!TBB && "Found more than one non-landing-pad successor!");
558        TBB = *SI;
559      }
560
561      // If there is no non-landing-pad successor, the block has no fall-through
562      // edges to be concerned with.
563      if (!TBB)
564        return;
565
566      // Finally update the unconditional successor to be reached via a branch
567      // if it would not be reached by fallthrough.
568      if (!isLayoutSuccessor(TBB))
569        TII->insertBranch(*this, TBB, nullptr, Cond, DL);
570    }
571    return;
572  }
573
574  if (FBB) {
575    // The block has a non-fallthrough conditional branch. If one of its
576    // successors is its layout successor, rewrite it to a fallthrough
577    // conditional branch.
578    if (isLayoutSuccessor(TBB)) {
579      if (TII->reverseBranchCondition(Cond))
580        return;
581      TII->removeBranch(*this);
582      TII->insertBranch(*this, FBB, nullptr, Cond, DL);
583    } else if (isLayoutSuccessor(FBB)) {
584      TII->removeBranch(*this);
585      TII->insertBranch(*this, TBB, nullptr, Cond, DL);
586    }
587    return;
588  }
589
590  // Walk through the successors and find the successor which is not a landing
591  // pad and is not the conditional branch destination (in TBB) as the
592  // fallthrough successor.
593  MachineBasicBlock *FallthroughBB = nullptr;
594  for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; ++SI) {
595    if ((*SI)->isEHPad() || *SI == TBB)
596      continue;
597    assert(!FallthroughBB && "Found more than one fallthrough successor.");
598    FallthroughBB = *SI;
599  }
600
601  if (!FallthroughBB) {
602    if (canFallThrough()) {
603      // We fallthrough to the same basic block as the conditional jump targets.
604      // Remove the conditional jump, leaving unconditional fallthrough.
605      // FIXME: This does not seem like a reasonable pattern to support, but it
606      // has been seen in the wild coming out of degenerate ARM test cases.
607      TII->removeBranch(*this);
608
609      // Finally update the unconditional successor to be reached via a branch if
610      // it would not be reached by fallthrough.
611      if (!isLayoutSuccessor(TBB))
612        TII->insertBranch(*this, TBB, nullptr, Cond, DL);
613      return;
614    }
615
616    // We enter here iff exactly one successor is TBB which cannot fallthrough
617    // and the rest successors if any are EHPads.  In this case, we need to
618    // change the conditional branch into unconditional branch.
619    TII->removeBranch(*this);
620    Cond.clear();
621    TII->insertBranch(*this, TBB, nullptr, Cond, DL);
622    return;
623  }
624
625  // The block has a fallthrough conditional branch.
626  if (isLayoutSuccessor(TBB)) {
627    if (TII->reverseBranchCondition(Cond)) {
628      // We can't reverse the condition, add an unconditional branch.
629      Cond.clear();
630      TII->insertBranch(*this, FallthroughBB, nullptr, Cond, DL);
631      return;
632    }
633    TII->removeBranch(*this);
634    TII->insertBranch(*this, FallthroughBB, nullptr, Cond, DL);
635  } else if (!isLayoutSuccessor(FallthroughBB)) {
636    TII->removeBranch(*this);
637    TII->insertBranch(*this, TBB, FallthroughBB, Cond, DL);
638  }
639}
640
641void MachineBasicBlock::validateSuccProbs() const {
642#ifndef NDEBUG
643  int64_t Sum = 0;
644  for (auto Prob : Probs)
645    Sum += Prob.getNumerator();
646  // Due to precision issue, we assume that the sum of probabilities is one if
647  // the difference between the sum of their numerators and the denominator is
648  // no greater than the number of successors.
649  assert((uint64_t)std::abs(Sum - BranchProbability::getDenominator()) <=
650             Probs.size() &&
651         "The sum of successors's probabilities exceeds one.");
652#endif // NDEBUG
653}
654
655void MachineBasicBlock::addSuccessor(MachineBasicBlock *Succ,
656                                     BranchProbability Prob) {
657  // Probability list is either empty (if successor list isn't empty, this means
658  // disabled optimization) or has the same size as successor list.
659  if (!(Probs.empty() && !Successors.empty()))
660    Probs.push_back(Prob);
661  Successors.push_back(Succ);
662  Succ->addPredecessor(this);
663}
664
665void MachineBasicBlock::addSuccessorWithoutProb(MachineBasicBlock *Succ) {
666  // We need to make sure probability list is either empty or has the same size
667  // of successor list. When this function is called, we can safely delete all
668  // probability in the list.
669  Probs.clear();
670  Successors.push_back(Succ);
671  Succ->addPredecessor(this);
672}
673
674void MachineBasicBlock::splitSuccessor(MachineBasicBlock *Old,
675                                       MachineBasicBlock *New,
676                                       bool NormalizeSuccProbs) {
677  succ_iterator OldI = llvm::find(successors(), Old);
678  assert(OldI != succ_end() && "Old is not a successor of this block!");
679  assert(llvm::find(successors(), New) == succ_end() &&
680         "New is already a successor of this block!");
681
682  // Add a new successor with equal probability as the original one. Note
683  // that we directly copy the probability using the iterator rather than
684  // getting a potentially synthetic probability computed when unknown. This
685  // preserves the probabilities as-is and then we can renormalize them and
686  // query them effectively afterward.
687  addSuccessor(New, Probs.empty() ? BranchProbability::getUnknown()
688                                  : *getProbabilityIterator(OldI));
689  if (NormalizeSuccProbs)
690    normalizeSuccProbs();
691}
692
693void MachineBasicBlock::removeSuccessor(MachineBasicBlock *Succ,
694                                        bool NormalizeSuccProbs) {
695  succ_iterator I = find(Successors, Succ);
696  removeSuccessor(I, NormalizeSuccProbs);
697}
698
699MachineBasicBlock::succ_iterator
700MachineBasicBlock::removeSuccessor(succ_iterator I, bool NormalizeSuccProbs) {
701  assert(I != Successors.end() && "Not a current successor!");
702
703  // If probability list is empty it means we don't use it (disabled
704  // optimization).
705  if (!Probs.empty()) {
706    probability_iterator WI = getProbabilityIterator(I);
707    Probs.erase(WI);
708    if (NormalizeSuccProbs)
709      normalizeSuccProbs();
710  }
711
712  (*I)->removePredecessor(this);
713  return Successors.erase(I);
714}
715
716void MachineBasicBlock::replaceSuccessor(MachineBasicBlock *Old,
717                                         MachineBasicBlock *New) {
718  if (Old == New)
719    return;
720
721  succ_iterator E = succ_end();
722  succ_iterator NewI = E;
723  succ_iterator OldI = E;
724  for (succ_iterator I = succ_begin(); I != E; ++I) {
725    if (*I == Old) {
726      OldI = I;
727      if (NewI != E)
728        break;
729    }
730    if (*I == New) {
731      NewI = I;
732      if (OldI != E)
733        break;
734    }
735  }
736  assert(OldI != E && "Old is not a successor of this block");
737
738  // If New isn't already a successor, let it take Old's place.
739  if (NewI == E) {
740    Old->removePredecessor(this);
741    New->addPredecessor(this);
742    *OldI = New;
743    return;
744  }
745
746  // New is already a successor.
747  // Update its probability instead of adding a duplicate edge.
748  if (!Probs.empty()) {
749    auto ProbIter = getProbabilityIterator(NewI);
750    if (!ProbIter->isUnknown())
751      *ProbIter += *getProbabilityIterator(OldI);
752  }
753  removeSuccessor(OldI);
754}
755
756void MachineBasicBlock::copySuccessor(MachineBasicBlock *Orig,
757                                      succ_iterator I) {
758  if (Orig->Probs.empty())
759    addSuccessor(*I, Orig->getSuccProbability(I));
760  else
761    addSuccessorWithoutProb(*I);
762}
763
764void MachineBasicBlock::addPredecessor(MachineBasicBlock *Pred) {
765  Predecessors.push_back(Pred);
766}
767
768void MachineBasicBlock::removePredecessor(MachineBasicBlock *Pred) {
769  pred_iterator I = find(Predecessors, Pred);
770  assert(I != Predecessors.end() && "Pred is not a predecessor of this block!");
771  Predecessors.erase(I);
772}
773
774void MachineBasicBlock::transferSuccessors(MachineBasicBlock *FromMBB) {
775  if (this == FromMBB)
776    return;
777
778  while (!FromMBB->succ_empty()) {
779    MachineBasicBlock *Succ = *FromMBB->succ_begin();
780
781    // If probability list is empty it means we don't use it (disabled
782    // optimization).
783    if (!FromMBB->Probs.empty()) {
784      auto Prob = *FromMBB->Probs.begin();
785      addSuccessor(Succ, Prob);
786    } else
787      addSuccessorWithoutProb(Succ);
788
789    FromMBB->removeSuccessor(Succ);
790  }
791}
792
793void
794MachineBasicBlock::transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB) {
795  if (this == FromMBB)
796    return;
797
798  while (!FromMBB->succ_empty()) {
799    MachineBasicBlock *Succ = *FromMBB->succ_begin();
800    if (!FromMBB->Probs.empty()) {
801      auto Prob = *FromMBB->Probs.begin();
802      addSuccessor(Succ, Prob);
803    } else
804      addSuccessorWithoutProb(Succ);
805    FromMBB->removeSuccessor(Succ);
806
807    // Fix up any PHI nodes in the successor.
808    Succ->replacePhiUsesWith(FromMBB, this);
809  }
810  normalizeSuccProbs();
811}
812
813bool MachineBasicBlock::isPredecessor(const MachineBasicBlock *MBB) const {
814  return is_contained(predecessors(), MBB);
815}
816
817bool MachineBasicBlock::isSuccessor(const MachineBasicBlock *MBB) const {
818  return is_contained(successors(), MBB);
819}
820
821bool MachineBasicBlock::isLayoutSuccessor(const MachineBasicBlock *MBB) const {
822  MachineFunction::const_iterator I(this);
823  return std::next(I) == MachineFunction::const_iterator(MBB);
824}
825
826MachineBasicBlock *MachineBasicBlock::getFallThrough() {
827  MachineFunction::iterator Fallthrough = getIterator();
828  ++Fallthrough;
829  // If FallthroughBlock is off the end of the function, it can't fall through.
830  if (Fallthrough == getParent()->end())
831    return nullptr;
832
833  // If FallthroughBlock isn't a successor, no fallthrough is possible.
834  if (!isSuccessor(&*Fallthrough))
835    return nullptr;
836
837  // Analyze the branches, if any, at the end of the block.
838  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
839  SmallVector<MachineOperand, 4> Cond;
840  const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
841  if (TII->analyzeBranch(*this, TBB, FBB, Cond)) {
842    // If we couldn't analyze the branch, examine the last instruction.
843    // If the block doesn't end in a known control barrier, assume fallthrough
844    // is possible. The isPredicated check is needed because this code can be
845    // called during IfConversion, where an instruction which is normally a
846    // Barrier is predicated and thus no longer an actual control barrier.
847    return (empty() || !back().isBarrier() || TII->isPredicated(back()))
848               ? &*Fallthrough
849               : nullptr;
850  }
851
852  // If there is no branch, control always falls through.
853  if (!TBB) return &*Fallthrough;
854
855  // If there is some explicit branch to the fallthrough block, it can obviously
856  // reach, even though the branch should get folded to fall through implicitly.
857  if (MachineFunction::iterator(TBB) == Fallthrough ||
858      MachineFunction::iterator(FBB) == Fallthrough)
859    return &*Fallthrough;
860
861  // If it's an unconditional branch to some block not the fall through, it
862  // doesn't fall through.
863  if (Cond.empty()) return nullptr;
864
865  // Otherwise, if it is conditional and has no explicit false block, it falls
866  // through.
867  return (FBB == nullptr) ? &*Fallthrough : nullptr;
868}
869
870bool MachineBasicBlock::canFallThrough() {
871  return getFallThrough() != nullptr;
872}
873
874MachineBasicBlock *MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ,
875                                                        Pass &P) {
876  if (!canSplitCriticalEdge(Succ))
877    return nullptr;
878
879  MachineFunction *MF = getParent();
880  DebugLoc DL;  // FIXME: this is nowhere
881
882  MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock();
883  MF->insert(std::next(MachineFunction::iterator(this)), NMBB);
884  LLVM_DEBUG(dbgs() << "Splitting critical edge: " << printMBBReference(*this)
885                    << " -- " << printMBBReference(*NMBB) << " -- "
886                    << printMBBReference(*Succ) << '\n');
887
888  LiveIntervals *LIS = P.getAnalysisIfAvailable<LiveIntervals>();
889  SlotIndexes *Indexes = P.getAnalysisIfAvailable<SlotIndexes>();
890  if (LIS)
891    LIS->insertMBBInMaps(NMBB);
892  else if (Indexes)
893    Indexes->insertMBBInMaps(NMBB);
894
895  // On some targets like Mips, branches may kill virtual registers. Make sure
896  // that LiveVariables is properly updated after updateTerminator replaces the
897  // terminators.
898  LiveVariables *LV = P.getAnalysisIfAvailable<LiveVariables>();
899
900  // Collect a list of virtual registers killed by the terminators.
901  SmallVector<unsigned, 4> KilledRegs;
902  if (LV)
903    for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
904         I != E; ++I) {
905      MachineInstr *MI = &*I;
906      for (MachineInstr::mop_iterator OI = MI->operands_begin(),
907           OE = MI->operands_end(); OI != OE; ++OI) {
908        if (!OI->isReg() || OI->getReg() == 0 ||
909            !OI->isUse() || !OI->isKill() || OI->isUndef())
910          continue;
911        Register Reg = OI->getReg();
912        if (Register::isPhysicalRegister(Reg) ||
913            LV->getVarInfo(Reg).removeKill(*MI)) {
914          KilledRegs.push_back(Reg);
915          LLVM_DEBUG(dbgs() << "Removing terminator kill: " << *MI);
916          OI->setIsKill(false);
917        }
918      }
919    }
920
921  SmallVector<unsigned, 4> UsedRegs;
922  if (LIS) {
923    for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
924         I != E; ++I) {
925      MachineInstr *MI = &*I;
926
927      for (MachineInstr::mop_iterator OI = MI->operands_begin(),
928           OE = MI->operands_end(); OI != OE; ++OI) {
929        if (!OI->isReg() || OI->getReg() == 0)
930          continue;
931
932        Register Reg = OI->getReg();
933        if (!is_contained(UsedRegs, Reg))
934          UsedRegs.push_back(Reg);
935      }
936    }
937  }
938
939  ReplaceUsesOfBlockWith(Succ, NMBB);
940
941  // If updateTerminator() removes instructions, we need to remove them from
942  // SlotIndexes.
943  SmallVector<MachineInstr*, 4> Terminators;
944  if (Indexes) {
945    for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
946         I != E; ++I)
947      Terminators.push_back(&*I);
948  }
949
950  updateTerminator();
951
952  if (Indexes) {
953    SmallVector<MachineInstr*, 4> NewTerminators;
954    for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
955         I != E; ++I)
956      NewTerminators.push_back(&*I);
957
958    for (SmallVectorImpl<MachineInstr*>::iterator I = Terminators.begin(),
959        E = Terminators.end(); I != E; ++I) {
960      if (!is_contained(NewTerminators, *I))
961        Indexes->removeMachineInstrFromMaps(**I);
962    }
963  }
964
965  // Insert unconditional "jump Succ" instruction in NMBB if necessary.
966  NMBB->addSuccessor(Succ);
967  if (!NMBB->isLayoutSuccessor(Succ)) {
968    SmallVector<MachineOperand, 4> Cond;
969    const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
970    TII->insertBranch(*NMBB, Succ, nullptr, Cond, DL);
971
972    if (Indexes) {
973      for (MachineInstr &MI : NMBB->instrs()) {
974        // Some instructions may have been moved to NMBB by updateTerminator(),
975        // so we first remove any instruction that already has an index.
976        if (Indexes->hasIndex(MI))
977          Indexes->removeMachineInstrFromMaps(MI);
978        Indexes->insertMachineInstrInMaps(MI);
979      }
980    }
981  }
982
983  // Fix PHI nodes in Succ so they refer to NMBB instead of this.
984  Succ->replacePhiUsesWith(this, NMBB);
985
986  // Inherit live-ins from the successor
987  for (const auto &LI : Succ->liveins())
988    NMBB->addLiveIn(LI);
989
990  // Update LiveVariables.
991  const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
992  if (LV) {
993    // Restore kills of virtual registers that were killed by the terminators.
994    while (!KilledRegs.empty()) {
995      unsigned Reg = KilledRegs.pop_back_val();
996      for (instr_iterator I = instr_end(), E = instr_begin(); I != E;) {
997        if (!(--I)->addRegisterKilled(Reg, TRI, /* AddIfNotFound= */ false))
998          continue;
999        if (Register::isVirtualRegister(Reg))
1000          LV->getVarInfo(Reg).Kills.push_back(&*I);
1001        LLVM_DEBUG(dbgs() << "Restored terminator kill: " << *I);
1002        break;
1003      }
1004    }
1005    // Update relevant live-through information.
1006    LV->addNewBlock(NMBB, this, Succ);
1007  }
1008
1009  if (LIS) {
1010    // After splitting the edge and updating SlotIndexes, live intervals may be
1011    // in one of two situations, depending on whether this block was the last in
1012    // the function. If the original block was the last in the function, all
1013    // live intervals will end prior to the beginning of the new split block. If
1014    // the original block was not at the end of the function, all live intervals
1015    // will extend to the end of the new split block.
1016
1017    bool isLastMBB =
1018      std::next(MachineFunction::iterator(NMBB)) == getParent()->end();
1019
1020    SlotIndex StartIndex = Indexes->getMBBEndIdx(this);
1021    SlotIndex PrevIndex = StartIndex.getPrevSlot();
1022    SlotIndex EndIndex = Indexes->getMBBEndIdx(NMBB);
1023
1024    // Find the registers used from NMBB in PHIs in Succ.
1025    SmallSet<unsigned, 8> PHISrcRegs;
1026    for (MachineBasicBlock::instr_iterator
1027         I = Succ->instr_begin(), E = Succ->instr_end();
1028         I != E && I->isPHI(); ++I) {
1029      for (unsigned ni = 1, ne = I->getNumOperands(); ni != ne; ni += 2) {
1030        if (I->getOperand(ni+1).getMBB() == NMBB) {
1031          MachineOperand &MO = I->getOperand(ni);
1032          Register Reg = MO.getReg();
1033          PHISrcRegs.insert(Reg);
1034          if (MO.isUndef())
1035            continue;
1036
1037          LiveInterval &LI = LIS->getInterval(Reg);
1038          VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
1039          assert(VNI &&
1040                 "PHI sources should be live out of their predecessors.");
1041          LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
1042        }
1043      }
1044    }
1045
1046    MachineRegisterInfo *MRI = &getParent()->getRegInfo();
1047    for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
1048      unsigned Reg = Register::index2VirtReg(i);
1049      if (PHISrcRegs.count(Reg) || !LIS->hasInterval(Reg))
1050        continue;
1051
1052      LiveInterval &LI = LIS->getInterval(Reg);
1053      if (!LI.liveAt(PrevIndex))
1054        continue;
1055
1056      bool isLiveOut = LI.liveAt(LIS->getMBBStartIdx(Succ));
1057      if (isLiveOut && isLastMBB) {
1058        VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
1059        assert(VNI && "LiveInterval should have VNInfo where it is live.");
1060        LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
1061      } else if (!isLiveOut && !isLastMBB) {
1062        LI.removeSegment(StartIndex, EndIndex);
1063      }
1064    }
1065
1066    // Update all intervals for registers whose uses may have been modified by
1067    // updateTerminator().
1068    LIS->repairIntervalsInRange(this, getFirstTerminator(), end(), UsedRegs);
1069  }
1070
1071  if (MachineDominatorTree *MDT =
1072          P.getAnalysisIfAvailable<MachineDominatorTree>())
1073    MDT->recordSplitCriticalEdge(this, Succ, NMBB);
1074
1075  if (MachineLoopInfo *MLI = P.getAnalysisIfAvailable<MachineLoopInfo>())
1076    if (MachineLoop *TIL = MLI->getLoopFor(this)) {
1077      // If one or the other blocks were not in a loop, the new block is not
1078      // either, and thus LI doesn't need to be updated.
1079      if (MachineLoop *DestLoop = MLI->getLoopFor(Succ)) {
1080        if (TIL == DestLoop) {
1081          // Both in the same loop, the NMBB joins loop.
1082          DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase());
1083        } else if (TIL->contains(DestLoop)) {
1084          // Edge from an outer loop to an inner loop.  Add to the outer loop.
1085          TIL->addBasicBlockToLoop(NMBB, MLI->getBase());
1086        } else if (DestLoop->contains(TIL)) {
1087          // Edge from an inner loop to an outer loop.  Add to the outer loop.
1088          DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase());
1089        } else {
1090          // Edge from two loops with no containment relation.  Because these
1091          // are natural loops, we know that the destination block must be the
1092          // header of its loop (adding a branch into a loop elsewhere would
1093          // create an irreducible loop).
1094          assert(DestLoop->getHeader() == Succ &&
1095                 "Should not create irreducible loops!");
1096          if (MachineLoop *P = DestLoop->getParentLoop())
1097            P->addBasicBlockToLoop(NMBB, MLI->getBase());
1098        }
1099      }
1100    }
1101
1102  return NMBB;
1103}
1104
1105bool MachineBasicBlock::canSplitCriticalEdge(
1106    const MachineBasicBlock *Succ) const {
1107  // Splitting the critical edge to a landing pad block is non-trivial. Don't do
1108  // it in this generic function.
1109  if (Succ->isEHPad())
1110    return false;
1111
1112  const MachineFunction *MF = getParent();
1113
1114  // Performance might be harmed on HW that implements branching using exec mask
1115  // where both sides of the branches are always executed.
1116  if (MF->getTarget().requiresStructuredCFG())
1117    return false;
1118
1119  // We may need to update this's terminator, but we can't do that if
1120  // AnalyzeBranch fails. If this uses a jump table, we won't touch it.
1121  const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
1122  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1123  SmallVector<MachineOperand, 4> Cond;
1124  // AnalyzeBanch should modify this, since we did not allow modification.
1125  if (TII->analyzeBranch(*const_cast<MachineBasicBlock *>(this), TBB, FBB, Cond,
1126                         /*AllowModify*/ false))
1127    return false;
1128
1129  // Avoid bugpoint weirdness: A block may end with a conditional branch but
1130  // jumps to the same MBB is either case. We have duplicate CFG edges in that
1131  // case that we can't handle. Since this never happens in properly optimized
1132  // code, just skip those edges.
1133  if (TBB && TBB == FBB) {
1134    LLVM_DEBUG(dbgs() << "Won't split critical edge after degenerate "
1135                      << printMBBReference(*this) << '\n');
1136    return false;
1137  }
1138  return true;
1139}
1140
1141/// Prepare MI to be removed from its bundle. This fixes bundle flags on MI's
1142/// neighboring instructions so the bundle won't be broken by removing MI.
1143static void unbundleSingleMI(MachineInstr *MI) {
1144  // Removing the first instruction in a bundle.
1145  if (MI->isBundledWithSucc() && !MI->isBundledWithPred())
1146    MI->unbundleFromSucc();
1147  // Removing the last instruction in a bundle.
1148  if (MI->isBundledWithPred() && !MI->isBundledWithSucc())
1149    MI->unbundleFromPred();
1150  // If MI is not bundled, or if it is internal to a bundle, the neighbor flags
1151  // are already fine.
1152}
1153
1154MachineBasicBlock::instr_iterator
1155MachineBasicBlock::erase(MachineBasicBlock::instr_iterator I) {
1156  unbundleSingleMI(&*I);
1157  return Insts.erase(I);
1158}
1159
1160MachineInstr *MachineBasicBlock::remove_instr(MachineInstr *MI) {
1161  unbundleSingleMI(MI);
1162  MI->clearFlag(MachineInstr::BundledPred);
1163  MI->clearFlag(MachineInstr::BundledSucc);
1164  return Insts.remove(MI);
1165}
1166
1167MachineBasicBlock::instr_iterator
1168MachineBasicBlock::insert(instr_iterator I, MachineInstr *MI) {
1169  assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
1170         "Cannot insert instruction with bundle flags");
1171  // Set the bundle flags when inserting inside a bundle.
1172  if (I != instr_end() && I->isBundledWithPred()) {
1173    MI->setFlag(MachineInstr::BundledPred);
1174    MI->setFlag(MachineInstr::BundledSucc);
1175  }
1176  return Insts.insert(I, MI);
1177}
1178
1179/// This method unlinks 'this' from the containing function, and returns it, but
1180/// does not delete it.
1181MachineBasicBlock *MachineBasicBlock::removeFromParent() {
1182  assert(getParent() && "Not embedded in a function!");
1183  getParent()->remove(this);
1184  return this;
1185}
1186
1187/// This method unlinks 'this' from the containing function, and deletes it.
1188void MachineBasicBlock::eraseFromParent() {
1189  assert(getParent() && "Not embedded in a function!");
1190  getParent()->erase(this);
1191}
1192
1193/// Given a machine basic block that branched to 'Old', change the code and CFG
1194/// so that it branches to 'New' instead.
1195void MachineBasicBlock::ReplaceUsesOfBlockWith(MachineBasicBlock *Old,
1196                                               MachineBasicBlock *New) {
1197  assert(Old != New && "Cannot replace self with self!");
1198
1199  MachineBasicBlock::instr_iterator I = instr_end();
1200  while (I != instr_begin()) {
1201    --I;
1202    if (!I->isTerminator()) break;
1203
1204    // Scan the operands of this machine instruction, replacing any uses of Old
1205    // with New.
1206    for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
1207      if (I->getOperand(i).isMBB() &&
1208          I->getOperand(i).getMBB() == Old)
1209        I->getOperand(i).setMBB(New);
1210  }
1211
1212  // Update the successor information.
1213  replaceSuccessor(Old, New);
1214}
1215
1216void MachineBasicBlock::replacePhiUsesWith(MachineBasicBlock *Old,
1217                                           MachineBasicBlock *New) {
1218  for (MachineInstr &MI : phis())
1219    for (unsigned i = 2, e = MI.getNumOperands() + 1; i != e; i += 2) {
1220      MachineOperand &MO = MI.getOperand(i);
1221      if (MO.getMBB() == Old)
1222        MO.setMBB(New);
1223    }
1224}
1225
1226/// Various pieces of code can cause excess edges in the CFG to be inserted.  If
1227/// we have proven that MBB can only branch to DestA and DestB, remove any other
1228/// MBB successors from the CFG.  DestA and DestB can be null.
1229///
1230/// Besides DestA and DestB, retain other edges leading to LandingPads
1231/// (currently there can be only one; we don't check or require that here).
1232/// Note it is possible that DestA and/or DestB are LandingPads.
1233bool MachineBasicBlock::CorrectExtraCFGEdges(MachineBasicBlock *DestA,
1234                                             MachineBasicBlock *DestB,
1235                                             bool IsCond) {
1236  // The values of DestA and DestB frequently come from a call to the
1237  // 'TargetInstrInfo::AnalyzeBranch' method. We take our meaning of the initial
1238  // values from there.
1239  //
1240  // 1. If both DestA and DestB are null, then the block ends with no branches
1241  //    (it falls through to its successor).
1242  // 2. If DestA is set, DestB is null, and IsCond is false, then the block ends
1243  //    with only an unconditional branch.
1244  // 3. If DestA is set, DestB is null, and IsCond is true, then the block ends
1245  //    with a conditional branch that falls through to a successor (DestB).
1246  // 4. If DestA and DestB is set and IsCond is true, then the block ends with a
1247  //    conditional branch followed by an unconditional branch. DestA is the
1248  //    'true' destination and DestB is the 'false' destination.
1249
1250  bool Changed = false;
1251
1252  MachineBasicBlock *FallThru = getNextNode();
1253
1254  if (!DestA && !DestB) {
1255    // Block falls through to successor.
1256    DestA = FallThru;
1257    DestB = FallThru;
1258  } else if (DestA && !DestB) {
1259    if (IsCond)
1260      // Block ends in conditional jump that falls through to successor.
1261      DestB = FallThru;
1262  } else {
1263    assert(DestA && DestB && IsCond &&
1264           "CFG in a bad state. Cannot correct CFG edges");
1265  }
1266
1267  // Remove superfluous edges. I.e., those which aren't destinations of this
1268  // basic block, duplicate edges, or landing pads.
1269  SmallPtrSet<const MachineBasicBlock*, 8> SeenMBBs;
1270  MachineBasicBlock::succ_iterator SI = succ_begin();
1271  while (SI != succ_end()) {
1272    const MachineBasicBlock *MBB = *SI;
1273    if (!SeenMBBs.insert(MBB).second ||
1274        (MBB != DestA && MBB != DestB && !MBB->isEHPad())) {
1275      // This is a superfluous edge, remove it.
1276      SI = removeSuccessor(SI);
1277      Changed = true;
1278    } else {
1279      ++SI;
1280    }
1281  }
1282
1283  if (Changed)
1284    normalizeSuccProbs();
1285  return Changed;
1286}
1287
1288/// Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE
1289/// instructions.  Return UnknownLoc if there is none.
1290DebugLoc
1291MachineBasicBlock::findDebugLoc(instr_iterator MBBI) {
1292  // Skip debug declarations, we don't want a DebugLoc from them.
1293  MBBI = skipDebugInstructionsForward(MBBI, instr_end());
1294  if (MBBI != instr_end())
1295    return MBBI->getDebugLoc();
1296  return {};
1297}
1298
1299/// Find the previous valid DebugLoc preceding MBBI, skipping and DBG_VALUE
1300/// instructions.  Return UnknownLoc if there is none.
1301DebugLoc MachineBasicBlock::findPrevDebugLoc(instr_iterator MBBI) {
1302  if (MBBI == instr_begin()) return {};
1303  // Skip debug declarations, we don't want a DebugLoc from them.
1304  MBBI = skipDebugInstructionsBackward(std::prev(MBBI), instr_begin());
1305  if (!MBBI->isDebugInstr()) return MBBI->getDebugLoc();
1306  return {};
1307}
1308
1309/// Find and return the merged DebugLoc of the branch instructions of the block.
1310/// Return UnknownLoc if there is none.
1311DebugLoc
1312MachineBasicBlock::findBranchDebugLoc() {
1313  DebugLoc DL;
1314  auto TI = getFirstTerminator();
1315  while (TI != end() && !TI->isBranch())
1316    ++TI;
1317
1318  if (TI != end()) {
1319    DL = TI->getDebugLoc();
1320    for (++TI ; TI != end() ; ++TI)
1321      if (TI->isBranch())
1322        DL = DILocation::getMergedLocation(DL, TI->getDebugLoc());
1323  }
1324  return DL;
1325}
1326
1327/// Return probability of the edge from this block to MBB.
1328BranchProbability
1329MachineBasicBlock::getSuccProbability(const_succ_iterator Succ) const {
1330  if (Probs.empty())
1331    return BranchProbability(1, succ_size());
1332
1333  const auto &Prob = *getProbabilityIterator(Succ);
1334  if (Prob.isUnknown()) {
1335    // For unknown probabilities, collect the sum of all known ones, and evenly
1336    // ditribute the complemental of the sum to each unknown probability.
1337    unsigned KnownProbNum = 0;
1338    auto Sum = BranchProbability::getZero();
1339    for (auto &P : Probs) {
1340      if (!P.isUnknown()) {
1341        Sum += P;
1342        KnownProbNum++;
1343      }
1344    }
1345    return Sum.getCompl() / (Probs.size() - KnownProbNum);
1346  } else
1347    return Prob;
1348}
1349
1350/// Set successor probability of a given iterator.
1351void MachineBasicBlock::setSuccProbability(succ_iterator I,
1352                                           BranchProbability Prob) {
1353  assert(!Prob.isUnknown());
1354  if (Probs.empty())
1355    return;
1356  *getProbabilityIterator(I) = Prob;
1357}
1358
1359/// Return probability iterator corresonding to the I successor iterator
1360MachineBasicBlock::const_probability_iterator
1361MachineBasicBlock::getProbabilityIterator(
1362    MachineBasicBlock::const_succ_iterator I) const {
1363  assert(Probs.size() == Successors.size() && "Async probability list!");
1364  const size_t index = std::distance(Successors.begin(), I);
1365  assert(index < Probs.size() && "Not a current successor!");
1366  return Probs.begin() + index;
1367}
1368
1369/// Return probability iterator corresonding to the I successor iterator.
1370MachineBasicBlock::probability_iterator
1371MachineBasicBlock::getProbabilityIterator(MachineBasicBlock::succ_iterator I) {
1372  assert(Probs.size() == Successors.size() && "Async probability list!");
1373  const size_t index = std::distance(Successors.begin(), I);
1374  assert(index < Probs.size() && "Not a current successor!");
1375  return Probs.begin() + index;
1376}
1377
1378/// Return whether (physical) register "Reg" has been <def>ined and not <kill>ed
1379/// as of just before "MI".
1380///
1381/// Search is localised to a neighborhood of
1382/// Neighborhood instructions before (searching for defs or kills) and N
1383/// instructions after (searching just for defs) MI.
1384MachineBasicBlock::LivenessQueryResult
1385MachineBasicBlock::computeRegisterLiveness(const TargetRegisterInfo *TRI,
1386                                           unsigned Reg, const_iterator Before,
1387                                           unsigned Neighborhood) const {
1388  unsigned N = Neighborhood;
1389
1390  // Try searching forwards from Before, looking for reads or defs.
1391  const_iterator I(Before);
1392  for (; I != end() && N > 0; ++I) {
1393    if (I->isDebugInstr())
1394      continue;
1395
1396    --N;
1397
1398    PhysRegInfo Info = AnalyzePhysRegInBundle(*I, Reg, TRI);
1399
1400    // Register is live when we read it here.
1401    if (Info.Read)
1402      return LQR_Live;
1403    // Register is dead if we can fully overwrite or clobber it here.
1404    if (Info.FullyDefined || Info.Clobbered)
1405      return LQR_Dead;
1406  }
1407
1408  // If we reached the end, it is safe to clobber Reg at the end of a block of
1409  // no successor has it live in.
1410  if (I == end()) {
1411    for (MachineBasicBlock *S : successors()) {
1412      for (const MachineBasicBlock::RegisterMaskPair &LI : S->liveins()) {
1413        if (TRI->regsOverlap(LI.PhysReg, Reg))
1414          return LQR_Live;
1415      }
1416    }
1417
1418    return LQR_Dead;
1419  }
1420
1421
1422  N = Neighborhood;
1423
1424  // Start by searching backwards from Before, looking for kills, reads or defs.
1425  I = const_iterator(Before);
1426  // If this is the first insn in the block, don't search backwards.
1427  if (I != begin()) {
1428    do {
1429      --I;
1430
1431      if (I->isDebugInstr())
1432        continue;
1433
1434      --N;
1435
1436      PhysRegInfo Info = AnalyzePhysRegInBundle(*I, Reg, TRI);
1437
1438      // Defs happen after uses so they take precedence if both are present.
1439
1440      // Register is dead after a dead def of the full register.
1441      if (Info.DeadDef)
1442        return LQR_Dead;
1443      // Register is (at least partially) live after a def.
1444      if (Info.Defined) {
1445        if (!Info.PartialDeadDef)
1446          return LQR_Live;
1447        // As soon as we saw a partial definition (dead or not),
1448        // we cannot tell if the value is partial live without
1449        // tracking the lanemasks. We are not going to do this,
1450        // so fall back on the remaining of the analysis.
1451        break;
1452      }
1453      // Register is dead after a full kill or clobber and no def.
1454      if (Info.Killed || Info.Clobbered)
1455        return LQR_Dead;
1456      // Register must be live if we read it.
1457      if (Info.Read)
1458        return LQR_Live;
1459
1460    } while (I != begin() && N > 0);
1461  }
1462
1463  // If all the instructions before this in the block are debug instructions,
1464  // skip over them.
1465  while (I != begin() && std::prev(I)->isDebugInstr())
1466    --I;
1467
1468  // Did we get to the start of the block?
1469  if (I == begin()) {
1470    // If so, the register's state is definitely defined by the live-in state.
1471    for (const MachineBasicBlock::RegisterMaskPair &LI : liveins())
1472      if (TRI->regsOverlap(LI.PhysReg, Reg))
1473        return LQR_Live;
1474
1475    return LQR_Dead;
1476  }
1477
1478  // At this point we have no idea of the liveness of the register.
1479  return LQR_Unknown;
1480}
1481
1482const uint32_t *
1483MachineBasicBlock::getBeginClobberMask(const TargetRegisterInfo *TRI) const {
1484  // EH funclet entry does not preserve any registers.
1485  return isEHFuncletEntry() ? TRI->getNoPreservedMask() : nullptr;
1486}
1487
1488const uint32_t *
1489MachineBasicBlock::getEndClobberMask(const TargetRegisterInfo *TRI) const {
1490  // If we see a return block with successors, this must be a funclet return,
1491  // which does not preserve any registers. If there are no successors, we don't
1492  // care what kind of return it is, putting a mask after it is a no-op.
1493  return isReturnBlock() && !succ_empty() ? TRI->getNoPreservedMask() : nullptr;
1494}
1495
1496void MachineBasicBlock::clearLiveIns() {
1497  LiveIns.clear();
1498}
1499
1500MachineBasicBlock::livein_iterator MachineBasicBlock::livein_begin() const {
1501  assert(getParent()->getProperties().hasProperty(
1502      MachineFunctionProperties::Property::TracksLiveness) &&
1503      "Liveness information is accurate");
1504  return LiveIns.begin();
1505}
1506