contrib/llvm/lib/CodeGen/MachineBasicBlock.cpp

   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 MachineBasicBlock::MachineBasicBlock(MachineFunction &MF, const BasicBlock *B)
  43     : BB(B), Number(-1), xParent(&MF) {
  44   Insts.Parent = this;
  45 }
  46
  47 MachineBasicBlock::~MachineBasicBlock() {
  48 }
  49
  50 /// Return the MCSymbol for this basic block.
  51 MCSymbol *MachineBasicBlock::getSymbol() const {
  52   if (!CachedMCSymbol) {
  53     const MachineFunction *MF = getParent();
  54     MCContext &Ctx = MF->getContext();
  55     auto Prefix = Ctx.getAsmInfo()->getPrivateLabelPrefix();
  56     assert(getNumber() >= 0 && "cannot get label for unreachable MBB");
  57     CachedMCSymbol = Ctx.getOrCreateSymbol(Twine(Prefix) + "BB" +
  58                                            Twine(MF->getFunctionNumber()) +
  59                                            "_" + Twine(getNumber()));
  60   }
  61
  62   return CachedMCSymbol;
  63 }
  64
  65
  66 raw_ostream &llvm::operator<<(raw_ostream &OS, const MachineBasicBlock &MBB) {
  67   MBB.print(OS);
  68   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 void ilist_callback_traits<MachineBasicBlock>::addNodeToList(
  79     MachineBasicBlock *N) {
  80   MachineFunction &MF = *N->getParent();
  81   N->Number = MF.addToMBBNumbering(N);
  82
  83   // Make sure the instructions have their operands in the reginfo lists.
  84   MachineRegisterInfo &RegInfo = MF.getRegInfo();
  85   for (MachineBasicBlock::instr_iterator
  86          I = N->instr_begin(), E = N->instr_end(); I != E; ++I)
  87     I->AddRegOperandsToUseLists(RegInfo);
  88 }
  89
  90 void ilist_callback_traits<MachineBasicBlock>::removeNodeFromList(
  91     MachineBasicBlock *N) {
  92   N->getParent()->removeFromMBBNumbering(N->Number);
  93   N->Number = -1;
  94 }
  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 void ilist_traits<MachineInstr>::addNodeToList(MachineInstr *N) {
  99   assert(!N->getParent() && "machine instruction already in a basic block");
 100   N->setParent(Parent);
 101
 102   // Add the instruction's register operands to their corresponding
 103   // use/def lists.
 104   MachineFunction *MF = Parent->getParent();
 105   N->AddRegOperandsToUseLists(MF->getRegInfo());
 106 }
 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 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   if (MachineFunction *MF = N->getParent()->getParent())
 115     N->RemoveRegOperandsFromUseLists(MF->getRegInfo());
 116
 117   N->setParent(nullptr);
 118 }
 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 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   for (; First != Last; ++First)
 133     First->setParent(Parent);
 134 }
 135
 136 void ilist_traits<MachineInstr>::deleteNode(MachineInstr *MI) {
 137   assert(!MI->getParent() && "MI is still in a block!");
 138   Parent->getParent()->DeleteMachineInstr(MI);
 139 }
 140
 141 MachineBasicBlock::iterator MachineBasicBlock::getFirstNonPHI() {
 142   instr_iterator I = instr_begin(), E = instr_end();
 143   while (I != E && I->isPHI())
 144     ++I;
 145   assert((I == E || !I->isInsideBundle()) &&
 146          "First non-phi MI cannot be inside a bundle!");
 147   return I;
 148 }
 149
 150 MachineBasicBlock::iterator
 151 MachineBasicBlock::SkipPHIsAndLabels(MachineBasicBlock::iterator I) {
 152   const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
 153
 154   iterator E = end();
 155   while (I != E && (I->isPHI() || I->isPosition() ||
 156                     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   return I;
 163 }
 164
 165 MachineBasicBlock::iterator
 166 MachineBasicBlock::SkipPHIsLabelsAndDebug(MachineBasicBlock::iterator I) {
 167   const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
 168
 169   iterator E = end();
 170   while (I != E && (I->isPHI() || I->isPosition() || I->isDebugValue() ||
 171                     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   return I;
 179 }
 180
 181 MachineBasicBlock::iterator MachineBasicBlock::getFirstTerminator() {
 182   iterator B = begin(), E = end(), I = E;
 183   while (I != B && ((--I)->isTerminator() || I->isDebugValue()))
 184     ; /*noop */
 185   while (I != E && !I->isTerminator())
 186     ++I;
 187   return I;
 188 }
 189
 190 MachineBasicBlock::instr_iterator MachineBasicBlock::getFirstInstrTerminator() {
 191   instr_iterator B = instr_begin(), E = instr_end(), I = E;
 192   while (I != B && ((--I)->isTerminator() || I->isDebugValue()))
 193     ; /*noop */
 194   while (I != E && !I->isTerminator())
 195     ++I;
 196   return I;
 197 }
 198
 199 MachineBasicBlock::iterator MachineBasicBlock::getFirstNonDebugInstr() {
 200   // Skip over begin-of-block dbg_value instructions.
 201   return skipDebugInstructionsForward(begin(), end());
 202 }
 203
 204 MachineBasicBlock::iterator MachineBasicBlock::getLastNonDebugInstr() {
 205   // Skip over end-of-block dbg_value instructions.
 206   instr_iterator B = instr_begin(), I = instr_end();
 207   while (I != B) {
 208     --I;
 209     // Return instruction that starts a bundle.
 210     if (I->isDebugValue() || I->isInsideBundle())
 211       continue;
 212     return I;
 213   }
 214   // The block is all debug values.
 215   return end();
 216 }
 217
 218 bool MachineBasicBlock::hasEHPadSuccessor() const {
 219   for (const_succ_iterator I = succ_begin(), E = succ_end(); I != E; ++I)
 220     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 bool MachineBasicBlock::isLegalToHoistInto() const {
 232   if (isReturnBlock() || hasEHPadSuccessor())
 233     return false;
 234   return true;
 235 }
 236
 237 StringRef MachineBasicBlock::getName() const {
 238   if (const BasicBlock *LBB = getBasicBlock())
 239     return LBB->getName();
 240   else
 241     return StringRef("", 0);
 242 }
 243
 244 /// Return a hopefully unique identifier for this block.
 245 std::string MachineBasicBlock::getFullName() const {
 246   std::string Name;
 247   if (getParent())
 248     Name = (getParent()->getName() + ":").str();
 249   if (getBasicBlock())
 250     Name += getBasicBlock()->getName();
 251   else
 252     Name += ("BB" + Twine(getNumber())).str();
 253   return Name;
 254 }
 255
 256 void MachineBasicBlock::print(raw_ostream &OS, const SlotIndexes *Indexes)
 257     const {
 258   const MachineFunction *MF = getParent();
 259   if (!MF) {
 260     OS << "Can't print out MachineBasicBlock because parent MachineFunction"
 261        << " is null\n";
 262     return;
 263   }
 264   const Function *F = MF->getFunction();
 265   const Module *M = F ? F->getParent() : nullptr;
 266   ModuleSlotTracker MST(M);
 267   print(OS, MST, Indexes);
 268 }
 269
 270 void MachineBasicBlock::print(raw_ostream &OS, ModuleSlotTracker &MST,
 271                               const SlotIndexes *Indexes) const {
 272   const MachineFunction *MF = getParent();
 273   if (!MF) {
 274     OS << "Can't print out MachineBasicBlock because parent MachineFunction"
 275        << " is null\n";
 276     return;
 277   }
 278
 279   if (Indexes)
 280     OS << Indexes->getMBBStartIdx(this) << '\t';
 281
 282   OS << "BB#" << getNumber() << ": ";
 283
 284   const char *Comma = "";
 285   if (const BasicBlock *LBB = getBasicBlock()) {
 286     OS << Comma << "derived from LLVM BB ";
 287     LBB->printAsOperand(OS, /*PrintType=*/false, MST);
 288     Comma = ", ";
 289   }
 290   if (isEHPad()) { OS << Comma << "EH LANDING PAD"; Comma = ", "; }
 291   if (hasAddressTaken()) { OS << Comma << "ADDRESS TAKEN"; Comma = ", "; }
 292   if (Alignment)
 293     OS << Comma << "Align " << Alignment << " (" << (1u << Alignment)
 294        << " bytes)";
 295
 296   OS << '\n';
 297
 298   const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
 299   if (!livein_empty()) {
 300     if (Indexes) OS << '\t';
 301     OS << "    Live Ins:";
 302     for (const auto &LI : LiveIns) {
 303       OS << ' ' << PrintReg(LI.PhysReg, TRI);
 304       if (!LI.LaneMask.all())
 305         OS << ':' << PrintLaneMask(LI.LaneMask);
 306     }
 307     OS << '\n';
 308   }
 309   // Print the preds of this block according to the CFG.
 310   if (!pred_empty()) {
 311     if (Indexes) OS << '\t';
 312     OS << "    Predecessors according to CFG:";
 313     for (const_pred_iterator PI = pred_begin(), E = pred_end(); PI != E; ++PI)
 314       OS << " BB#" << (*PI)->getNumber();
 315     OS << '\n';
 316   }
 317
 318   for (auto &I : instrs()) {
 319     if (Indexes) {
 320       if (Indexes->hasIndex(I))
 321         OS << Indexes->getInstructionIndex(I);
 322       OS << '\t';
 323     }
 324     OS << '\t';
 325     if (I.isInsideBundle())
 326       OS << "  * ";
 327     I.print(OS, MST);
 328   }
 329
 330   // Print the successors of this block according to the CFG.
 331   if (!succ_empty()) {
 332     if (Indexes) OS << '\t';
 333     OS << "    Successors according to CFG:";
 334     for (const_succ_iterator SI = succ_begin(), E = succ_end(); SI != E; ++SI) {
 335       OS << " BB#" << (*SI)->getNumber();
 336       if (!Probs.empty())
 337         OS << '(' << *getProbabilityIterator(SI) << ')';
 338     }
 339     OS << '\n';
 340   }
 341 }
 342
 343 void MachineBasicBlock::printAsOperand(raw_ostream &OS,
 344                                        bool /*PrintType*/) const {
 345   OS << "BB#" << getNumber();
 346 }
 347
 348 void MachineBasicBlock::removeLiveIn(MCPhysReg Reg, LaneBitmask LaneMask) {
 349   LiveInVector::iterator I = find_if(
 350       LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
 351   if (I == LiveIns.end())
 352     return;
 353
 354   I->LaneMask &= ~LaneMask;
 355   if (I->LaneMask.none())
 356     LiveIns.erase(I);
 357 }
 358
 359 MachineBasicBlock::livein_iterator
 360 MachineBasicBlock::removeLiveIn(MachineBasicBlock::livein_iterator I) {
 361   // Get non-const version of iterator.
 362   LiveInVector::iterator LI = LiveIns.begin() + (I - LiveIns.begin());
 363   return LiveIns.erase(LI);
 364 }
 365
 366 bool MachineBasicBlock::isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask) const {
 367   livein_iterator I = find_if(
 368       LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
 369   return I != livein_end() && (I->LaneMask & LaneMask).any();
 370 }
 371
 372 void MachineBasicBlock::sortUniqueLiveIns() {
 373   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   LiveInVector::const_iterator I = LiveIns.begin();
 379   LiveInVector::const_iterator J;
 380   LiveInVector::iterator Out = LiveIns.begin();
 381   for (; I != LiveIns.end(); ++Out, I = J) {
 382     unsigned PhysReg = I->PhysReg;
 383     LaneBitmask LaneMask = I->LaneMask;
 384     for (J = std::next(I); J != LiveIns.end() && J->PhysReg == PhysReg; ++J)
 385       LaneMask |= J->LaneMask;
 386     Out->PhysReg = PhysReg;
 387     Out->LaneMask = LaneMask;
 388   }
 389   LiveIns.erase(Out, LiveIns.end());
 390 }
 391
 392 unsigned
 393 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   bool LiveIn = isLiveIn(PhysReg);
 401   iterator I = SkipPHIsAndLabels(begin()), E = end();
 402   MachineRegisterInfo &MRI = getParent()->getRegInfo();
 403   const TargetInstrInfo &TII = *getParent()->getSubtarget().getInstrInfo();
 404
 405   // Look for an existing copy.
 406   if (LiveIn)
 407     for (;I != E && I->isCopy(); ++I)
 408       if (I->getOperand(1).getReg() == PhysReg) {
 409         unsigned VirtReg = I->getOperand(0).getReg();
 410         if (!MRI.constrainRegClass(VirtReg, RC))
 411           llvm_unreachable("Incompatible live-in register class.");
 412         return VirtReg;
 413       }
 414
 415   // No luck, create a virtual register.
 416   unsigned VirtReg = MRI.createVirtualRegister(RC);
 417   BuildMI(*this, I, DebugLoc(), TII.get(TargetOpcode::COPY), VirtReg)
 418     .addReg(PhysReg, RegState::Kill);
 419   if (!LiveIn)
 420     addLiveIn(PhysReg);
 421   return VirtReg;
 422 }
 423
 424 void MachineBasicBlock::moveBefore(MachineBasicBlock *NewAfter) {
 425   getParent()->splice(NewAfter->getIterator(), getIterator());
 426 }
 427
 428 void MachineBasicBlock::moveAfter(MachineBasicBlock *NewBefore) {
 429   getParent()->splice(++NewBefore->getIterator(), getIterator());
 430 }
 431
 432 void MachineBasicBlock::updateTerminator() {
 433   const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
 434   // A block with no successors has no concerns with fall-through edges.
 435   if (this->succ_empty())
 436     return;
 437
 438   MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
 439   SmallVector<MachineOperand, 4> Cond;
 440   DebugLoc DL = findBranchDebugLoc();
 441   bool B = TII->analyzeBranch(*this, TBB, FBB, Cond);
 442   (void) B;
 443   assert(!B && "UpdateTerminators requires analyzable predecessors!");
 444   if (Cond.empty()) {
 445     if (TBB) {
 446       // The block has an unconditional branch. If its successor is now its
 447       // layout successor, delete the branch.
 448       if (isLayoutSuccessor(TBB))
 449         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       for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; ++SI) {
 455         if ((*SI)->isEHPad())
 456           continue;
 457         assert(!TBB && "Found more than one non-landing-pad successor!");
 458         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       if (!TBB)
 464         return;
 465
 466       // Finally update the unconditional successor to be reached via a branch
 467       // if it would not be reached by fallthrough.
 468       if (!isLayoutSuccessor(TBB))
 469         TII->insertBranch(*this, TBB, nullptr, Cond, DL);
 470     }
 471     return;
 472   }
 473
 474   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     if (isLayoutSuccessor(TBB)) {
 479       if (TII->reverseBranchCondition(Cond))
 480         return;
 481       TII->removeBranch(*this);
 482       TII->insertBranch(*this, FBB, nullptr, Cond, DL);
 483     } else if (isLayoutSuccessor(FBB)) {
 484       TII->removeBranch(*this);
 485       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   MachineBasicBlock *FallthroughBB = nullptr;
 494   for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; ++SI) {
 495     if ((*SI)->isEHPad() || *SI == TBB)
 496       continue;
 497     assert(!FallthroughBB && "Found more than one fallthrough successor.");
 498     FallthroughBB = *SI;
 499   }
 500
 501   if (!FallthroughBB) {
 502     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       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       if (!isLayoutSuccessor(TBB))
 512         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     TII->removeBranch(*this);
 520     Cond.clear();
 521     TII->insertBranch(*this, TBB, nullptr, Cond, DL);
 522     return;
 523   }
 524
 525   // The block has a fallthrough conditional branch.
 526   if (isLayoutSuccessor(TBB)) {
 527     if (TII->reverseBranchCondition(Cond)) {
 528       // We can't reverse the condition, add an unconditional branch.
 529       Cond.clear();
 530       TII->insertBranch(*this, FallthroughBB, nullptr, Cond, DL);
 531       return;
 532     }
 533     TII->removeBranch(*this);
 534     TII->insertBranch(*this, FallthroughBB, nullptr, Cond, DL);
 535   } else if (!isLayoutSuccessor(FallthroughBB)) {
 536     TII->removeBranch(*this);
 537     TII->insertBranch(*this, TBB, FallthroughBB, Cond, DL);
 538   }
 539 }
 540
 541 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 }
 554
 555 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   if (!(Probs.empty() && !Successors.empty()))
 560     Probs.push_back(Prob);
 561   Successors.push_back(Succ);
 562   Succ->addPredecessor(this);
 563 }
 564
 565 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   Probs.clear();
 570   Successors.push_back(Succ);
 571   Succ->addPredecessor(this);
 572 }
 573
 574 void MachineBasicBlock::removeSuccessor(MachineBasicBlock *Succ,
 575                                         bool NormalizeSuccProbs) {
 576   succ_iterator I = find(Successors, Succ);
 577   removeSuccessor(I, NormalizeSuccProbs);
 578 }
 579
 580 MachineBasicBlock::succ_iterator
 581 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   if (!Probs.empty()) {
 587     probability_iterator WI = getProbabilityIterator(I);
 588     Probs.erase(WI);
 589     if (NormalizeSuccProbs)
 590       normalizeSuccProbs();
 591   }
 592
 593   (*I)->removePredecessor(this);
 594   return Successors.erase(I);
 595 }
 596
 597 void MachineBasicBlock::replaceSuccessor(MachineBasicBlock *Old,
 598                                          MachineBasicBlock *New) {
 599   if (Old == New)
 600     return;
 601
 602   succ_iterator E = succ_end();
 603   succ_iterator NewI = E;
 604   succ_iterator OldI = E;
 605   for (succ_iterator I = succ_begin(); I != E; ++I) {
 606     if (*I == Old) {
 607       OldI = I;
 608       if (NewI != E)
 609         break;
 610     }
 611     if (*I == New) {
 612       NewI = I;
 613       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   if (NewI == E) {
 621     Old->removePredecessor(this);
 622     New->addPredecessor(this);
 623     *OldI = New;
 624     return;
 625   }
 626
 627   // New is already a successor.
 628   // Update its probability instead of adding a duplicate edge.
 629   if (!Probs.empty()) {
 630     auto ProbIter = getProbabilityIterator(NewI);
 631     if (!ProbIter->isUnknown())
 632       *ProbIter += *getProbabilityIterator(OldI);
 633   }
 634   removeSuccessor(OldI);
 635 }
 636
 637 void MachineBasicBlock::addPredecessor(MachineBasicBlock *Pred) {
 638   Predecessors.push_back(Pred);
 639 }
 640
 641 void MachineBasicBlock::removePredecessor(MachineBasicBlock *Pred) {
 642   pred_iterator I = find(Predecessors, Pred);
 643   assert(I != Predecessors.end() && "Pred is not a predecessor of this block!");
 644   Predecessors.erase(I);
 645 }
 646
 647 void MachineBasicBlock::transferSuccessors(MachineBasicBlock *FromMBB) {
 648   if (this == FromMBB)
 649     return;
 650
 651   while (!FromMBB->succ_empty()) {
 652     MachineBasicBlock *Succ = *FromMBB->succ_begin();
 653
 654     // If probability list is empty it means we don't use it (disabled optimization).
 655     if (!FromMBB->Probs.empty()) {
 656       auto Prob = *FromMBB->Probs.begin();
 657       addSuccessor(Succ, Prob);
 658     } else
 659       addSuccessorWithoutProb(Succ);
 660
 661     FromMBB->removeSuccessor(Succ);
 662   }
 663 }
 664
 665 void
 666 MachineBasicBlock::transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB) {
 667   if (this == FromMBB)
 668     return;
 669
 670   while (!FromMBB->succ_empty()) {
 671     MachineBasicBlock *Succ = *FromMBB->succ_begin();
 672     if (!FromMBB->Probs.empty()) {
 673       auto Prob = *FromMBB->Probs.begin();
 674       addSuccessor(Succ, Prob);
 675     } else
 676       addSuccessorWithoutProb(Succ);
 677     FromMBB->removeSuccessor(Succ);
 678
 679     // Fix up any PHI nodes in the successor.
 680     for (MachineBasicBlock::instr_iterator MI = Succ->instr_begin(),
 681            ME = Succ->instr_end(); MI != ME && MI->isPHI(); ++MI)
 682       for (unsigned i = 2, e = MI->getNumOperands()+1; i != e; i += 2) {
 683         MachineOperand &MO = MI->getOperand(i);
 684         if (MO.getMBB() == FromMBB)
 685           MO.setMBB(this);
 686       }
 687   }
 688   normalizeSuccProbs();
 689 }
 690
 691 bool MachineBasicBlock::isPredecessor(const MachineBasicBlock *MBB) const {
 692   return is_contained(predecessors(), MBB);
 693 }
 694
 695 bool MachineBasicBlock::isSuccessor(const MachineBasicBlock *MBB) const {
 696   return is_contained(successors(), MBB);
 697 }
 698
 699 bool MachineBasicBlock::isLayoutSuccessor(const MachineBasicBlock *MBB) const {
 700   MachineFunction::const_iterator I(this);
 701   return std::next(I) == MachineFunction::const_iterator(MBB);
 702 }
 703
 704 MachineBasicBlock *MachineBasicBlock::getFallThrough() {
 705   MachineFunction::iterator Fallthrough = getIterator();
 706   ++Fallthrough;
 707   // If FallthroughBlock is off the end of the function, it can't fall through.
 708   if (Fallthrough == getParent()->end())
 709     return nullptr;
 710
 711   // If FallthroughBlock isn't a successor, no fallthrough is possible.
 712   if (!isSuccessor(&*Fallthrough))
 713     return nullptr;
 714
 715   // Analyze the branches, if any, at the end of the block.
 716   MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
 717   SmallVector<MachineOperand, 4> Cond;
 718   const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
 719   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     return (empty() || !back().isBarrier() || TII->isPredicated(back()))
 726                ? &*Fallthrough
 727                : nullptr;
 728   }
 729
 730   // If there is no branch, control always falls through.
 731   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   if (MachineFunction::iterator(TBB) == Fallthrough ||
 736       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   if (Cond.empty()) return nullptr;
 742
 743   // Otherwise, if it is conditional and has no explicit false block, it falls
 744   // through.
 745   return (FBB == nullptr) ? &*Fallthrough : nullptr;
 746 }
 747
 748 bool MachineBasicBlock::canFallThrough() {
 749   return getFallThrough() != nullptr;
 750 }
 751
 752 MachineBasicBlock *MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ,
 753                                                         Pass &P) {
 754   if (!canSplitCriticalEdge(Succ))
 755     return nullptr;
 756
 757   MachineFunction *MF = getParent();
 758   DebugLoc DL;  // FIXME: this is nowhere
 759
 760   MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock();
 761   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   LiveIntervals *LIS = P.getAnalysisIfAvailable<LiveIntervals>();
 768   SlotIndexes *Indexes = P.getAnalysisIfAvailable<SlotIndexes>();
 769   if (LIS)
 770     LIS->insertMBBInMaps(NMBB);
 771   else if (Indexes)
 772     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   LiveVariables *LV = P.getAnalysisIfAvailable<LiveVariables>();
 778
 779   // Collect a list of virtual registers killed by the terminators.
 780   SmallVector<unsigned, 4> KilledRegs;
 781   if (LV)
 782     for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
 783          I != E; ++I) {
 784       MachineInstr *MI = &*I;
 785       for (MachineInstr::mop_iterator OI = MI->operands_begin(),
 786            OE = MI->operands_end(); OI != OE; ++OI) {
 787         if (!OI->isReg() || OI->getReg() == 0 ||
 788             !OI->isUse() || !OI->isKill() || OI->isUndef())
 789           continue;
 790         unsigned Reg = OI->getReg();
 791         if (TargetRegisterInfo::isPhysicalRegister(Reg) ||
 792             LV->getVarInfo(Reg).removeKill(*MI)) {
 793           KilledRegs.push_back(Reg);
 794           DEBUG(dbgs() << "Removing terminator kill: " << *MI);
 795           OI->setIsKill(false);
 796         }
 797       }
 798     }
 799
 800   SmallVector<unsigned, 4> UsedRegs;
 801   if (LIS) {
 802     for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
 803          I != E; ++I) {
 804       MachineInstr *MI = &*I;
 805
 806       for (MachineInstr::mop_iterator OI = MI->operands_begin(),
 807            OE = MI->operands_end(); OI != OE; ++OI) {
 808         if (!OI->isReg() || OI->getReg() == 0)
 809           continue;
 810
 811         unsigned Reg = OI->getReg();
 812         if (!is_contained(UsedRegs, Reg))
 813           UsedRegs.push_back(Reg);
 814       }
 815     }
 816   }
 817
 818   ReplaceUsesOfBlockWith(Succ, NMBB);
 819
 820   // If updateTerminator() removes instructions, we need to remove them from
 821   // SlotIndexes.
 822   SmallVector<MachineInstr*, 4> Terminators;
 823   if (Indexes) {
 824     for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
 825          I != E; ++I)
 826       Terminators.push_back(&*I);
 827   }
 828
 829   updateTerminator();
 830
 831   if (Indexes) {
 832     SmallVector<MachineInstr*, 4> NewTerminators;
 833     for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
 834          I != E; ++I)
 835       NewTerminators.push_back(&*I);
 836
 837     for (SmallVectorImpl<MachineInstr*>::iterator I = Terminators.begin(),
 838         E = Terminators.end(); I != E; ++I) {
 839       if (!is_contained(NewTerminators, *I))
 840         Indexes->removeMachineInstrFromMaps(**I);
 841     }
 842   }
 843
 844   // Insert unconditional "jump Succ" instruction in NMBB if necessary.
 845   NMBB->addSuccessor(Succ);
 846   if (!NMBB->isLayoutSuccessor(Succ)) {
 847     SmallVector<MachineOperand, 4> Cond;
 848     const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
 849     TII->insertBranch(*NMBB, Succ, nullptr, Cond, DL);
 850
 851     if (Indexes) {
 852       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         if (Indexes->hasIndex(MI))
 856           Indexes->removeMachineInstrFromMaps(MI);
 857         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          i = Succ->instr_begin(),e = Succ->instr_end();
 865        i != e && i->isPHI(); ++i)
 866     for (unsigned ni = 1, ne = i->getNumOperands(); ni != ne; ni += 2)
 867       if (i->getOperand(ni+1).getMBB() == this)
 868         i->getOperand(ni+1).setMBB(NMBB);
 869
 870   // Inherit live-ins from the successor
 871   for (const auto &LI : Succ->liveins())
 872     NMBB->addLiveIn(LI);
 873
 874   // Update LiveVariables.
 875   const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
 876   if (LV) {
 877     // Restore kills of virtual registers that were killed by the terminators.
 878     while (!KilledRegs.empty()) {
 879       unsigned Reg = KilledRegs.pop_back_val();
 880       for (instr_iterator I = instr_end(), E = instr_begin(); I != E;) {
 881         if (!(--I)->addRegisterKilled(Reg, TRI, /* addIfNotFound= */ false))
 882           continue;
 883         if (TargetRegisterInfo::isVirtualRegister(Reg))
 884           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     LV->addNewBlock(NMBB, this, Succ);
 891   }
 892
 893   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       std::next(MachineFunction::iterator(NMBB)) == getParent()->end();
 903
 904     SlotIndex StartIndex = Indexes->getMBBEndIdx(this);
 905     SlotIndex PrevIndex = StartIndex.getPrevSlot();
 906     SlotIndex EndIndex = Indexes->getMBBEndIdx(NMBB);
 907
 908     // Find the registers used from NMBB in PHIs in Succ.
 909     SmallSet<unsigned, 8> PHISrcRegs;
 910     for (MachineBasicBlock::instr_iterator
 911          I = Succ->instr_begin(), E = Succ->instr_end();
 912          I != E && I->isPHI(); ++I) {
 913       for (unsigned ni = 1, ne = I->getNumOperands(); ni != ne; ni += 2) {
 914         if (I->getOperand(ni+1).getMBB() == NMBB) {
 915           MachineOperand &MO = I->getOperand(ni);
 916           unsigned Reg = MO.getReg();
 917           PHISrcRegs.insert(Reg);
 918           if (MO.isUndef())
 919             continue;
 920
 921           LiveInterval &LI = LIS->getInterval(Reg);
 922           VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
 923           assert(VNI &&
 924                  "PHI sources should be live out of their predecessors.");
 925           LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
 926         }
 927       }
 928     }
 929
 930     MachineRegisterInfo *MRI = &getParent()->getRegInfo();
 931     for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
 932       unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
 933       if (PHISrcRegs.count(Reg) || !LIS->hasInterval(Reg))
 934         continue;
 935
 936       LiveInterval &LI = LIS->getInterval(Reg);
 937       if (!LI.liveAt(PrevIndex))
 938         continue;
 939
 940       bool isLiveOut = LI.liveAt(LIS->getMBBStartIdx(Succ));
 941       if (isLiveOut && isLastMBB) {
 942         VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
 943         assert(VNI && "LiveInterval should have VNInfo where it is live.");
 944         LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
 945       } else if (!isLiveOut && !isLastMBB) {
 946         LI.removeSegment(StartIndex, EndIndex);
 947       }
 948     }
 949
 950     // Update all intervals for registers whose uses may have been modified by
 951     // updateTerminator().
 952     LIS->repairIntervalsInRange(this, getFirstTerminator(), end(), UsedRegs);
 953   }
 954
 955   if (MachineDominatorTree *MDT =
 956           P.getAnalysisIfAvailable<MachineDominatorTree>())
 957     MDT->recordSplitCriticalEdge(this, Succ, NMBB);
 958
 959   if (MachineLoopInfo *MLI = P.getAnalysisIfAvailable<MachineLoopInfo>())
 960     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       if (MachineLoop *DestLoop = MLI->getLoopFor(Succ)) {
 964         if (TIL == DestLoop) {
 965           // Both in the same loop, the NMBB joins loop.
 966           DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase());
 967         } else if (TIL->contains(DestLoop)) {
 968           // Edge from an outer loop to an inner loop.  Add to the outer loop.
 969           TIL->addBasicBlockToLoop(NMBB, MLI->getBase());
 970         } else if (DestLoop->contains(TIL)) {
 971           // Edge from an inner loop to an outer loop.  Add to the outer loop.
 972           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           if (MachineLoop *P = DestLoop->getParentLoop())
 981             P->addBasicBlockToLoop(NMBB, MLI->getBase());
 982         }
 983       }
 984     }
 985
 986   return NMBB;
 987 }
 988
 989 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   if (Succ->isEHPad())
 994     return false;
 995
 996   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   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   const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
1006   MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1007   SmallVector<MachineOperand, 4> Cond;
1008   // AnalyzeBanch should modify this, since we did not allow modification.
1009   if (TII->analyzeBranch(*const_cast<MachineBasicBlock *>(this), TBB, FBB, Cond,
1010                          /*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   if (TBB && TBB == FBB) {
1018     DEBUG(dbgs() << "Won't split critical edge after degenerate BB#"
1019                  << getNumber() << '\n');
1020     return false;
1021   }
1022   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 static void unbundleSingleMI(MachineInstr *MI) {
1028   // Removing the first instruction in a bundle.
1029   if (MI->isBundledWithSucc() && !MI->isBundledWithPred())
1030     MI->unbundleFromSucc();
1031   // Removing the last instruction in a bundle.
1032   if (MI->isBundledWithPred() && !MI->isBundledWithSucc())
1033     MI->unbundleFromPred();
1034   // If MI is not bundled, or if it is internal to a bundle, the neighbor flags
1035   // are already fine.
1036 }
1037
1038 MachineBasicBlock::instr_iterator
1039 MachineBasicBlock::erase(MachineBasicBlock::instr_iterator I) {
1040   unbundleSingleMI(&*I);
1041   return Insts.erase(I);
1042 }
1043
1044 MachineInstr *MachineBasicBlock::remove_instr(MachineInstr *MI) {
1045   unbundleSingleMI(MI);
1046   MI->clearFlag(MachineInstr::BundledPred);
1047   MI->clearFlag(MachineInstr::BundledSucc);
1048   return Insts.remove(MI);
1049 }
1050
1051 MachineBasicBlock::instr_iterator
1052 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   if (I != instr_end() && I->isBundledWithPred()) {
1057     MI->setFlag(MachineInstr::BundledPred);
1058     MI->setFlag(MachineInstr::BundledSucc);
1059   }
1060   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 MachineBasicBlock *MachineBasicBlock::removeFromParent() {
1066   assert(getParent() && "Not embedded in a function!");
1067   getParent()->remove(this);
1068   return this;
1069 }
1070
1071 /// This method unlinks 'this' from the containing function, and deletes it.
1072 void MachineBasicBlock::eraseFromParent() {
1073   assert(getParent() && "Not embedded in a function!");
1074   getParent()->erase(this);
1075 }
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 void MachineBasicBlock::ReplaceUsesOfBlockWith(MachineBasicBlock *Old,
1080                                                MachineBasicBlock *New) {
1081   assert(Old != New && "Cannot replace self with self!");
1082
1083   MachineBasicBlock::instr_iterator I = instr_end();
1084   while (I != instr_begin()) {
1085     --I;
1086     if (!I->isTerminator()) break;
1087
1088     // Scan the operands of this machine instruction, replacing any uses of Old
1089     // with New.
1090     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
1091       if (I->getOperand(i).isMBB() &&
1092           I->getOperand(i).getMBB() == Old)
1093         I->getOperand(i).setMBB(New);
1094   }
1095
1096   // Update the successor information.
1097   replaceSuccessor(Old, New);
1098 }
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 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   bool Changed = false;
1125
1126   MachineBasicBlock *FallThru = getNextNode();
1127
1128   if (!DestA && !DestB) {
1129     // Block falls through to successor.
1130     DestA = FallThru;
1131     DestB = FallThru;
1132   } else if (DestA && !DestB) {
1133     if (IsCond)
1134       // Block ends in conditional jump that falls through to successor.
1135       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   SmallPtrSet<const MachineBasicBlock*, 8> SeenMBBs;
1144   MachineBasicBlock::succ_iterator SI = succ_begin();
1145   while (SI != succ_end()) {
1146     const MachineBasicBlock *MBB = *SI;
1147     if (!SeenMBBs.insert(MBB).second ||
1148         (MBB != DestA && MBB != DestB && !MBB->isEHPad())) {
1149       // This is a superfluous edge, remove it.
1150       SI = removeSuccessor(SI);
1151       Changed = true;
1152     } else {
1153       ++SI;
1154     }
1155   }
1156
1157   if (Changed)
1158     normalizeSuccProbs();
1159   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 MachineBasicBlock::findDebugLoc(instr_iterator MBBI) {
1166   // Skip debug declarations, we don't want a DebugLoc from them.
1167   MBBI = skipDebugInstructionsForward(MBBI, instr_end());
1168   if (MBBI != instr_end())
1169     return MBBI->getDebugLoc();
1170   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 MachineBasicBlock::findBranchDebugLoc() {
1177   DebugLoc DL;
1178   auto TI = getFirstTerminator();
1179   while (TI != end() && !TI->isBranch())
1180     ++TI;
1181
1182   if (TI != end()) {
1183     DL = TI->getDebugLoc();
1184     for (++TI ; TI != end() ; ++TI)
1185       if (TI->isBranch())
1186         DL = DILocation::getMergedLocation(DL, TI->getDebugLoc());
1187   }
1188   return DL;
1189 }
1190
1191 /// Return probability of the edge from this block to MBB.
1192 BranchProbability
1193 MachineBasicBlock::getSuccProbability(const_succ_iterator Succ) const {
1194   if (Probs.empty())
1195     return BranchProbability(1, succ_size());
1196
1197   const auto &Prob = *getProbabilityIterator(Succ);
1198   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     unsigned KnownProbNum = 0;
1202     auto Sum = BranchProbability::getZero();
1203     for (auto &P : Probs) {
1204       if (!P.isUnknown()) {
1205         Sum += P;
1206         KnownProbNum++;
1207       }
1208     }
1209     return Sum.getCompl() / (Probs.size() - KnownProbNum);
1210   } else
1211     return Prob;
1212 }
1213
1214 /// Set successor probability of a given iterator.
1215 void MachineBasicBlock::setSuccProbability(succ_iterator I,
1216                                            BranchProbability Prob) {
1217   assert(!Prob.isUnknown());
1218   if (Probs.empty())
1219     return;
1220   *getProbabilityIterator(I) = Prob;
1221 }
1222
1223 /// Return probability iterator corresonding to the I successor iterator
1224 MachineBasicBlock::const_probability_iterator
1225 MachineBasicBlock::getProbabilityIterator(
1226     MachineBasicBlock::const_succ_iterator I) const {
1227   assert(Probs.size() == Successors.size() && "Async probability list!");
1228   const size_t index = std::distance(Successors.begin(), I);
1229   assert(index < Probs.size() && "Not a current successor!");
1230   return Probs.begin() + index;
1231 }
1232
1233 /// Return probability iterator corresonding to the I successor iterator.
1234 MachineBasicBlock::probability_iterator
1235 MachineBasicBlock::getProbabilityIterator(MachineBasicBlock::succ_iterator I) {
1236   assert(Probs.size() == Successors.size() && "Async probability list!");
1237   const size_t index = std::distance(Successors.begin(), I);
1238   assert(index < Probs.size() && "Not a current successor!");
1239   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 MachineBasicBlock::computeRegisterLiveness(const TargetRegisterInfo *TRI,
1250                                            unsigned Reg, const_iterator Before,
1251                                            unsigned Neighborhood) const {
1252   unsigned N = Neighborhood;
1253
1254   // Start by searching backwards from Before, looking for kills, reads or defs.
1255   const_iterator I(Before);
1256   // If this is the first insn in the block, don't search backwards.
1257   if (I != begin()) {
1258     do {
1259       --I;
1260
1261       MachineOperandIteratorBase::PhysRegInfo Info =
1262           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       if (Info.DeadDef)
1268         return LQR_Dead;
1269       // Register is (at least partially) live after a def.
1270       if (Info.Defined) {
1271         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         break;
1278       }
1279       // Register is dead after a full kill or clobber and no def.
1280       if (Info.Killed || Info.Clobbered)
1281         return LQR_Dead;
1282       // Register must be live if we read it.
1283       if (Info.Read)
1284         return LQR_Live;
1285     } while (I != begin() && --N > 0);
1286   }
1287
1288   // Did we get to the start of the block?
1289   if (I == begin()) {
1290     // If so, the register's state is definitely defined by the live-in state.
1291     for (MCRegAliasIterator RAI(Reg, TRI, /*IncludeSelf=*/true); RAI.isValid();
1292          ++RAI)
1293       if (isLiveIn(*RAI))
1294         return LQR_Live;
1295
1296     return LQR_Dead;
1297   }
1298
1299   N = Neighborhood;
1300
1301   // Try searching forwards from Before, looking for reads or defs.
1302   I = const_iterator(Before);
1303   // If this is the last insn in the block, don't search forwards.
1304   if (I != end()) {
1305     for (++I; I != end() && N > 0; ++I, --N) {
1306       MachineOperandIteratorBase::PhysRegInfo Info =
1307           ConstMIOperands(*I).analyzePhysReg(Reg, TRI);
1308
1309       // Register is live when we read it here.
1310       if (Info.Read)
1311         return LQR_Live;
1312       // Register is dead if we can fully overwrite or clobber it here.
1313       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 MachineBasicBlock::getBeginClobberMask(const TargetRegisterInfo *TRI) const {
1324   // EH funclet entry does not preserve any registers.
1325   return isEHFuncletEntry() ? TRI->getNoPreservedMask() : nullptr;
1326 }
1327
1328 const uint32_t *
1329 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   return isReturnBlock() && !succ_empty() ? TRI->getNoPreservedMask() : nullptr;
1334 }
1335
1336 void MachineBasicBlock::clearLiveIns() {
1337   LiveIns.clear();
1338 }
1339
1340 MachineBasicBlock::livein_iterator MachineBasicBlock::livein_begin() const {
1341   assert(getParent()->getProperties().hasProperty(
1342       MachineFunctionProperties::Property::TracksLiveness) &&
1343       "Liveness information is accurate");
1344   return LiveIns.begin();
1345 }