LCOV - code coverage report
Current view: top level - lib/CodeGen - MachineBasicBlock.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 490 584 83.9 %
Date: 2018-02-21 17:27:13 Functions: 64 69 92.8 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13