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

Generated by: LCOV version 1.13