llvm/lib/CodeGen/BranchRelaxation.cpp

   1 //===- BranchRelaxation.cpp -----------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/ADT/SmallVector.h"
  10 #include "llvm/ADT/Statistic.h"
  11 #include "llvm/CodeGen/LivePhysRegs.h"
  12 #include "llvm/CodeGen/MachineBasicBlock.h"
  13 #include "llvm/CodeGen/MachineFunction.h"
  14 #include "llvm/CodeGen/MachineFunctionPass.h"
  15 #include "llvm/CodeGen/MachineInstr.h"
  16 #include "llvm/CodeGen/RegisterScavenging.h"
  17 #include "llvm/CodeGen/TargetInstrInfo.h"
  18 #include "llvm/CodeGen/TargetRegisterInfo.h"
  19 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  20 #include "llvm/Config/llvm-config.h"
  21 #include "llvm/IR/DebugLoc.h"
  22 #include "llvm/InitializePasses.h"
  23 #include "llvm/Pass.h"
  24 #include "llvm/Support/Compiler.h"
  25 #include "llvm/Support/Debug.h"
  26 #include "llvm/Support/ErrorHandling.h"
  27 #include "llvm/Support/Format.h"
  28 #include "llvm/Support/raw_ostream.h"
  29 #include "llvm/Target/TargetMachine.h"
  30 #include <cassert>
  31 #include <cstdint>
  32 #include <iterator>
  33 #include <memory>
  34
  35 using namespace llvm;
  36
  37 #define DEBUG_TYPE "branch-relaxation"
  38
  39 STATISTIC(NumSplit, "Number of basic blocks split");
  40 STATISTIC(NumConditionalRelaxed, "Number of conditional branches relaxed");
  41 STATISTIC(NumUnconditionalRelaxed, "Number of unconditional branches relaxed");
  42
  43 #define BRANCH_RELAX_NAME "Branch relaxation pass"
  44
  45 namespace {
  46
  47 class BranchRelaxation : public MachineFunctionPass {
  48   /// BasicBlockInfo - Information about the offset and size of a single
  49   /// basic block.
  50   struct BasicBlockInfo {
  51     /// Offset - Distance from the beginning of the function to the beginning
  52     /// of this basic block.
  53     ///
  54     /// The offset is always aligned as required by the basic block.
  55     unsigned Offset = 0;
  56
  57     /// Size - Size of the basic block in bytes.  If the block contains
  58     /// inline assembly, this is a worst case estimate.
  59     ///
  60     /// The size does not include any alignment padding whether from the
  61     /// beginning of the block, or from an aligned jump table at the end.
  62     unsigned Size = 0;
  63
  64     BasicBlockInfo() = default;
  65
  66     /// Compute the offset immediately following this block. \p MBB is the next
  67     /// block.
  68     unsigned postOffset(const MachineBasicBlock &MBB) const {
  69       const unsigned PO = Offset + Size;
  70       const Align Alignment = MBB.getAlignment();
  71       const Align ParentAlign = MBB.getParent()->getAlignment();
  72       if (Alignment <= ParentAlign)
  73         return alignTo(PO, Alignment);
  74
  75       // The alignment of this MBB is larger than the function's alignment, so we
  76       // can't tell whether or not it will insert nops. Assume that it will.
  77       return alignTo(PO, Alignment) + Alignment.value() - ParentAlign.value();
  78     }
  79   };
  80
  81   SmallVector<BasicBlockInfo, 16> BlockInfo;
  82
  83   // The basic block after which trampolines are inserted. This is the last
  84   // basic block that isn't in the cold section.
  85   MachineBasicBlock *TrampolineInsertionPoint = nullptr;
  86   SmallDenseSet<std::pair<MachineBasicBlock *, MachineBasicBlock *>>
  87       RelaxedUnconditionals;
  88   std::unique_ptr<RegScavenger> RS;
  89   LivePhysRegs LiveRegs;
  90
  91   MachineFunction *MF = nullptr;
  92   const TargetRegisterInfo *TRI = nullptr;
  93   const TargetInstrInfo *TII = nullptr;
  94   const TargetMachine *TM = nullptr;
  95
  96   bool relaxBranchInstructions();
  97   void scanFunction();
  98
  99   MachineBasicBlock *createNewBlockAfter(MachineBasicBlock &OrigMBB);
 100   MachineBasicBlock *createNewBlockAfter(MachineBasicBlock &OrigMBB,
 101                                          const BasicBlock *BB);
 102
 103   MachineBasicBlock *splitBlockBeforeInstr(MachineInstr &MI,
 104                                            MachineBasicBlock *DestBB);
 105   void adjustBlockOffsets(MachineBasicBlock &Start);
 106   bool isBlockInRange(const MachineInstr &MI, const MachineBasicBlock &BB) const;
 107
 108   bool fixupConditionalBranch(MachineInstr &MI);
 109   bool fixupUnconditionalBranch(MachineInstr &MI);
 110   uint64_t computeBlockSize(const MachineBasicBlock &MBB) const;
 111   unsigned getInstrOffset(const MachineInstr &MI) const;
 112   void dumpBBs();
 113   void verify();
 114
 115 public:
 116   static char ID;
 117
 118   BranchRelaxation() : MachineFunctionPass(ID) {}
 119
 120   bool runOnMachineFunction(MachineFunction &MF) override;
 121
 122   StringRef getPassName() const override { return BRANCH_RELAX_NAME; }
 123 };
 124
 125 } // end anonymous namespace
 126
 127 char BranchRelaxation::ID = 0;
 128
 129 char &llvm::BranchRelaxationPassID = BranchRelaxation::ID;
 130
 131 INITIALIZE_PASS(BranchRelaxation, DEBUG_TYPE, BRANCH_RELAX_NAME, false, false)
 132
 133 /// verify - check BBOffsets, BBSizes, alignment of islands
 134 void BranchRelaxation::verify() {
 135 #ifndef NDEBUG
 136   unsigned PrevNum = MF->begin()->getNumber();
 137   for (MachineBasicBlock &MBB : *MF) {
 138     const unsigned Num = MBB.getNumber();
 139     assert(!Num || BlockInfo[PrevNum].postOffset(MBB) <= BlockInfo[Num].Offset);
 140     assert(BlockInfo[Num].Size == computeBlockSize(MBB));
 141     PrevNum = Num;
 142   }
 143
 144   for (MachineBasicBlock &MBB : *MF) {
 145     for (MachineBasicBlock::iterator J = MBB.getFirstTerminator();
 146          J != MBB.end(); J = std::next(J)) {
 147       MachineInstr &MI = *J;
 148       if (!MI.isConditionalBranch() && !MI.isUnconditionalBranch())
 149         continue;
 150       if (MI.getOpcode() == TargetOpcode::FAULTING_OP)
 151         continue;
 152       MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
 153       assert(isBlockInRange(MI, *DestBB) ||
 154              RelaxedUnconditionals.contains({&MBB, DestBB}));
 155     }
 156   }
 157 #endif
 158 }
 159
 160 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 161 /// print block size and offset information - debugging
 162 LLVM_DUMP_METHOD void BranchRelaxation::dumpBBs() {
 163   for (auto &MBB : *MF) {
 164     const BasicBlockInfo &BBI = BlockInfo[MBB.getNumber()];
 165     dbgs() << format("%%bb.%u\toffset=%08x\t", MBB.getNumber(), BBI.Offset)
 166            << format("size=%#x\n", BBI.Size);
 167   }
 168 }
 169 #endif
 170
 171 /// scanFunction - Do the initial scan of the function, building up
 172 /// information about each block.
 173 void BranchRelaxation::scanFunction() {
 174   BlockInfo.clear();
 175   BlockInfo.resize(MF->getNumBlockIDs());
 176
 177   TrampolineInsertionPoint = nullptr;
 178   RelaxedUnconditionals.clear();
 179
 180   // First thing, compute the size of all basic blocks, and see if the function
 181   // has any inline assembly in it. If so, we have to be conservative about
 182   // alignment assumptions, as we don't know for sure the size of any
 183   // instructions in the inline assembly. At the same time, place the
 184   // trampoline insertion point at the end of the hot portion of the function.
 185   for (MachineBasicBlock &MBB : *MF) {
 186     BlockInfo[MBB.getNumber()].Size = computeBlockSize(MBB);
 187
 188     if (MBB.getSectionID() != MBBSectionID::ColdSectionID)
 189       TrampolineInsertionPoint = &MBB;
 190   }
 191
 192   // Compute block offsets and known bits.
 193   adjustBlockOffsets(*MF->begin());
 194
 195   if (TrampolineInsertionPoint == nullptr) {
 196     LLVM_DEBUG(dbgs() << "  No suitable trampoline insertion point found in "
 197                       << MF->getName() << ".\n");
 198   }
 199 }
 200
 201 /// computeBlockSize - Compute the size for MBB.
 202 uint64_t BranchRelaxation::computeBlockSize(const MachineBasicBlock &MBB) const {
 203   uint64_t Size = 0;
 204   for (const MachineInstr &MI : MBB)
 205     Size += TII->getInstSizeInBytes(MI);
 206   return Size;
 207 }
 208
 209 /// getInstrOffset - Return the current offset of the specified machine
 210 /// instruction from the start of the function.  This offset changes as stuff is
 211 /// moved around inside the function.
 212 unsigned BranchRelaxation::getInstrOffset(const MachineInstr &MI) const {
 213   const MachineBasicBlock *MBB = MI.getParent();
 214
 215   // The offset is composed of two things: the sum of the sizes of all MBB's
 216   // before this instruction's block, and the offset from the start of the block
 217   // it is in.
 218   unsigned Offset = BlockInfo[MBB->getNumber()].Offset;
 219
 220   // Sum instructions before MI in MBB.
 221   for (MachineBasicBlock::const_iterator I = MBB->begin(); &*I != &MI; ++I) {
 222     assert(I != MBB->end() && "Didn't find MI in its own basic block?");
 223     Offset += TII->getInstSizeInBytes(*I);
 224   }
 225
 226   return Offset;
 227 }
 228
 229 void BranchRelaxation::adjustBlockOffsets(MachineBasicBlock &Start) {
 230   unsigned PrevNum = Start.getNumber();
 231   for (auto &MBB :
 232        make_range(std::next(MachineFunction::iterator(Start)), MF->end())) {
 233     unsigned Num = MBB.getNumber();
 234     // Get the offset and known bits at the end of the layout predecessor.
 235     // Include the alignment of the current block.
 236     BlockInfo[Num].Offset = BlockInfo[PrevNum].postOffset(MBB);
 237
 238     PrevNum = Num;
 239   }
 240 }
 241
 242 /// Insert a new empty MachineBasicBlock and insert it after \p OrigMBB
 243 MachineBasicBlock *
 244 BranchRelaxation::createNewBlockAfter(MachineBasicBlock &OrigBB) {
 245   return createNewBlockAfter(OrigBB, OrigBB.getBasicBlock());
 246 }
 247
 248 /// Insert a new empty MachineBasicBlock with \p BB as its BasicBlock
 249 /// and insert it after \p OrigMBB
 250 MachineBasicBlock *
 251 BranchRelaxation::createNewBlockAfter(MachineBasicBlock &OrigMBB,
 252                                       const BasicBlock *BB) {
 253   // Create a new MBB for the code after the OrigBB.
 254   MachineBasicBlock *NewBB = MF->CreateMachineBasicBlock(BB);
 255   MF->insert(++OrigMBB.getIterator(), NewBB);
 256
 257   // Place the new block in the same section as OrigBB
 258   NewBB->setSectionID(OrigMBB.getSectionID());
 259   NewBB->setIsEndSection(OrigMBB.isEndSection());
 260   OrigMBB.setIsEndSection(false);
 261
 262   // Insert an entry into BlockInfo to align it properly with the block numbers.
 263   BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
 264
 265   return NewBB;
 266 }
 267
 268 /// Split the basic block containing MI into two blocks, which are joined by
 269 /// an unconditional branch.  Update data structures and renumber blocks to
 270 /// account for this change and returns the newly created block.
 271 MachineBasicBlock *
 272 BranchRelaxation::splitBlockBeforeInstr(MachineInstr &MI,
 273                                         MachineBasicBlock *DestBB) {
 274   MachineBasicBlock *OrigBB = MI.getParent();
 275
 276   // Create a new MBB for the code after the OrigBB.
 277   MachineBasicBlock *NewBB =
 278       MF->CreateMachineBasicBlock(OrigBB->getBasicBlock());
 279   MF->insert(++OrigBB->getIterator(), NewBB);
 280
 281   // Place the new block in the same section as OrigBB.
 282   NewBB->setSectionID(OrigBB->getSectionID());
 283   NewBB->setIsEndSection(OrigBB->isEndSection());
 284   OrigBB->setIsEndSection(false);
 285
 286   // Splice the instructions starting with MI over to NewBB.
 287   NewBB->splice(NewBB->end(), OrigBB, MI.getIterator(), OrigBB->end());
 288
 289   // Add an unconditional branch from OrigBB to NewBB.
 290   // Note the new unconditional branch is not being recorded.
 291   // There doesn't seem to be meaningful DebugInfo available; this doesn't
 292   // correspond to anything in the source.
 293   TII->insertUnconditionalBranch(*OrigBB, NewBB, DebugLoc());
 294
 295   // Insert an entry into BlockInfo to align it properly with the block numbers.
 296   BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
 297
 298   NewBB->transferSuccessors(OrigBB);
 299   OrigBB->addSuccessor(NewBB);
 300   OrigBB->addSuccessor(DestBB);
 301
 302   // Cleanup potential unconditional branch to successor block.
 303   // Note that updateTerminator may change the size of the blocks.
 304   OrigBB->updateTerminator(NewBB);
 305
 306   // Figure out how large the OrigBB is.  As the first half of the original
 307   // block, it cannot contain a tablejump.  The size includes
 308   // the new jump we added.  (It should be possible to do this without
 309   // recounting everything, but it's very confusing, and this is rarely
 310   // executed.)
 311   BlockInfo[OrigBB->getNumber()].Size = computeBlockSize(*OrigBB);
 312
 313   // Figure out how large the NewMBB is. As the second half of the original
 314   // block, it may contain a tablejump.
 315   BlockInfo[NewBB->getNumber()].Size = computeBlockSize(*NewBB);
 316
 317   // All BBOffsets following these blocks must be modified.
 318   adjustBlockOffsets(*OrigBB);
 319
 320   // Need to fix live-in lists if we track liveness.
 321   if (TRI->trackLivenessAfterRegAlloc(*MF))
 322     computeAndAddLiveIns(LiveRegs, *NewBB);
 323
 324   ++NumSplit;
 325
 326   return NewBB;
 327 }
 328
 329 /// isBlockInRange - Returns true if the distance between specific MI and
 330 /// specific BB can fit in MI's displacement field.
 331 bool BranchRelaxation::isBlockInRange(
 332   const MachineInstr &MI, const MachineBasicBlock &DestBB) const {
 333   int64_t BrOffset = getInstrOffset(MI);
 334   int64_t DestOffset = BlockInfo[DestBB.getNumber()].Offset;
 335
 336   const MachineBasicBlock *SrcBB = MI.getParent();
 337
 338   if (TII->isBranchOffsetInRange(MI.getOpcode(),
 339                                  SrcBB->getSectionID() != DestBB.getSectionID()
 340                                      ? TM->getMaxCodeSize()
 341                                      : DestOffset - BrOffset))
 342     return true;
 343
 344   LLVM_DEBUG(dbgs() << "Out of range branch to destination "
 345                     << printMBBReference(DestBB) << " from "
 346                     << printMBBReference(*MI.getParent()) << " to "
 347                     << DestOffset << " offset " << DestOffset - BrOffset << '\t'
 348                     << MI);
 349
 350   return false;
 351 }
 352
 353 /// fixupConditionalBranch - Fix up a conditional branch whose destination is
 354 /// too far away to fit in its displacement field. It is converted to an inverse
 355 /// conditional branch + an unconditional branch to the destination.
 356 bool BranchRelaxation::fixupConditionalBranch(MachineInstr &MI) {
 357   DebugLoc DL = MI.getDebugLoc();
 358   MachineBasicBlock *MBB = MI.getParent();
 359   MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
 360   MachineBasicBlock *NewBB = nullptr;
 361   SmallVector<MachineOperand, 4> Cond;
 362
 363   auto insertUncondBranch = [&](MachineBasicBlock *MBB,
 364                                 MachineBasicBlock *DestBB) {
 365     unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
 366     int NewBrSize = 0;
 367     TII->insertUnconditionalBranch(*MBB, DestBB, DL, &NewBrSize);
 368     BBSize += NewBrSize;
 369   };
 370   auto insertBranch = [&](MachineBasicBlock *MBB, MachineBasicBlock *TBB,
 371                           MachineBasicBlock *FBB,
 372                           SmallVectorImpl<MachineOperand>& Cond) {
 373     unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
 374     int NewBrSize = 0;
 375     TII->insertBranch(*MBB, TBB, FBB, Cond, DL, &NewBrSize);
 376     BBSize += NewBrSize;
 377   };
 378   auto removeBranch = [&](MachineBasicBlock *MBB) {
 379     unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
 380     int RemovedSize = 0;
 381     TII->removeBranch(*MBB, &RemovedSize);
 382     BBSize -= RemovedSize;
 383   };
 384
 385   auto finalizeBlockChanges = [&](MachineBasicBlock *MBB,
 386                                   MachineBasicBlock *NewBB) {
 387     // Keep the block offsets up to date.
 388     adjustBlockOffsets(*MBB);
 389
 390     // Need to fix live-in lists if we track liveness.
 391     if (NewBB && TRI->trackLivenessAfterRegAlloc(*MF))
 392       computeAndAddLiveIns(LiveRegs, *NewBB);
 393   };
 394
 395   bool Fail = TII->analyzeBranch(*MBB, TBB, FBB, Cond);
 396   assert(!Fail && "branches to be relaxed must be analyzable");
 397   (void)Fail;
 398
 399   // Since cross-section conditional branches to the cold section are rarely
 400   // taken, try to avoid inverting the condition. Instead, add a "trampoline
 401   // branch", which unconditionally branches to the branch destination. Place
 402   // the trampoline branch at the end of the function and retarget the
 403   // conditional branch to the trampoline.
 404   // tbz L1
 405   // =>
 406   // tbz L1Trampoline
 407   // ...
 408   // L1Trampoline: b  L1
 409   if (MBB->getSectionID() != TBB->getSectionID() &&
 410       TBB->getSectionID() == MBBSectionID::ColdSectionID &&
 411       TrampolineInsertionPoint != nullptr) {
 412     // If the insertion point is out of range, we can't put a trampoline there.
 413     NewBB =
 414         createNewBlockAfter(*TrampolineInsertionPoint, MBB->getBasicBlock());
 415
 416     if (isBlockInRange(MI, *NewBB)) {
 417       LLVM_DEBUG(dbgs() << "  Retarget destination to trampoline at "
 418                         << NewBB->back());
 419
 420       insertUncondBranch(NewBB, TBB);
 421
 422       // Update the successor lists to include the trampoline.
 423       MBB->replaceSuccessor(TBB, NewBB);
 424       NewBB->addSuccessor(TBB);
 425
 426       // Replace branch in the current (MBB) block.
 427       removeBranch(MBB);
 428       insertBranch(MBB, NewBB, FBB, Cond);
 429
 430       TrampolineInsertionPoint = NewBB;
 431       finalizeBlockChanges(MBB, NewBB);
 432       return true;
 433     }
 434
 435     LLVM_DEBUG(
 436         dbgs() << "  Trampoline insertion point out of range for Bcc from "
 437                << printMBBReference(*MBB) << " to " << printMBBReference(*TBB)
 438                << ".\n");
 439     TrampolineInsertionPoint->setIsEndSection(NewBB->isEndSection());
 440     MF->erase(NewBB);
 441   }
 442
 443   // Add an unconditional branch to the destination and invert the branch
 444   // condition to jump over it:
 445   // tbz L1
 446   // =>
 447   // tbnz L2
 448   // b   L1
 449   // L2:
 450
 451   bool ReversedCond = !TII->reverseBranchCondition(Cond);
 452   if (ReversedCond) {
 453     if (FBB && isBlockInRange(MI, *FBB)) {
 454       // Last MI in the BB is an unconditional branch. We can simply invert the
 455       // condition and swap destinations:
 456       // beq L1
 457       // b   L2
 458       // =>
 459       // bne L2
 460       // b   L1
 461       LLVM_DEBUG(dbgs() << "  Invert condition and swap "
 462                            "its destination with "
 463                         << MBB->back());
 464
 465       removeBranch(MBB);
 466       insertBranch(MBB, FBB, TBB, Cond);
 467       finalizeBlockChanges(MBB, nullptr);
 468       return true;
 469     }
 470     if (FBB) {
 471       // We need to split the basic block here to obtain two long-range
 472       // unconditional branches.
 473       NewBB = createNewBlockAfter(*MBB);
 474
 475       insertUncondBranch(NewBB, FBB);
 476       // Update the succesor lists according to the transformation to follow.
 477       // Do it here since if there's no split, no update is needed.
 478       MBB->replaceSuccessor(FBB, NewBB);
 479       NewBB->addSuccessor(FBB);
 480     }
 481
 482     // We now have an appropriate fall-through block in place (either naturally or
 483     // just created), so we can use the inverted the condition.
 484     MachineBasicBlock &NextBB = *std::next(MachineFunction::iterator(MBB));
 485
 486     LLVM_DEBUG(dbgs() << "  Insert B to " << printMBBReference(*TBB)
 487                       << ", invert condition and change dest. to "
 488                       << printMBBReference(NextBB) << '\n');
 489
 490     removeBranch(MBB);
 491     // Insert a new conditional branch and a new unconditional branch.
 492     insertBranch(MBB, &NextBB, TBB, Cond);
 493
 494     finalizeBlockChanges(MBB, NewBB);
 495     return true;
 496   }
 497   // Branch cond can't be inverted.
 498   // In this case we always add a block after the MBB.
 499   LLVM_DEBUG(dbgs() << "  The branch condition can't be inverted. "
 500                     << "  Insert a new BB after " << MBB->back());
 501
 502   if (!FBB)
 503     FBB = &(*std::next(MachineFunction::iterator(MBB)));
 504
 505   // This is the block with cond. branch and the distance to TBB is too long.
 506   //    beq L1
 507   // L2:
 508
 509   // We do the following transformation:
 510   //    beq NewBB
 511   //    b L2
 512   // NewBB:
 513   //    b L1
 514   // L2:
 515
 516   NewBB = createNewBlockAfter(*MBB);
 517   insertUncondBranch(NewBB, TBB);
 518
 519   LLVM_DEBUG(dbgs() << "  Insert cond B to the new BB "
 520                     << printMBBReference(*NewBB)
 521                     << "  Keep the exiting condition.\n"
 522                     << "  Insert B to " << printMBBReference(*FBB) << ".\n"
 523                     << "  In the new BB: Insert B to "
 524                     << printMBBReference(*TBB) << ".\n");
 525
 526   // Update the successor lists according to the transformation to follow.
 527   MBB->replaceSuccessor(TBB, NewBB);
 528   NewBB->addSuccessor(TBB);
 529
 530   // Replace branch in the current (MBB) block.
 531   removeBranch(MBB);
 532   insertBranch(MBB, NewBB, FBB, Cond);
 533
 534   finalizeBlockChanges(MBB, NewBB);
 535   return true;
 536 }
 537
 538 bool BranchRelaxation::fixupUnconditionalBranch(MachineInstr &MI) {
 539   MachineBasicBlock *MBB = MI.getParent();
 540   SmallVector<MachineOperand, 4> Cond;
 541   unsigned OldBrSize = TII->getInstSizeInBytes(MI);
 542   MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
 543
 544   int64_t DestOffset = BlockInfo[DestBB->getNumber()].Offset;
 545   int64_t SrcOffset = getInstrOffset(MI);
 546
 547   assert(!TII->isBranchOffsetInRange(
 548       MI.getOpcode(), MBB->getSectionID() != DestBB->getSectionID()
 549                           ? TM->getMaxCodeSize()
 550                           : DestOffset - SrcOffset));
 551
 552   BlockInfo[MBB->getNumber()].Size -= OldBrSize;
 553
 554   MachineBasicBlock *BranchBB = MBB;
 555
 556   // If this was an expanded conditional branch, there is already a single
 557   // unconditional branch in a block.
 558   if (!MBB->empty()) {
 559     BranchBB = createNewBlockAfter(*MBB);
 560
 561     // Add live outs.
 562     for (const MachineBasicBlock *Succ : MBB->successors()) {
 563       for (const MachineBasicBlock::RegisterMaskPair &LiveIn : Succ->liveins())
 564         BranchBB->addLiveIn(LiveIn);
 565     }
 566
 567     BranchBB->sortUniqueLiveIns();
 568     BranchBB->addSuccessor(DestBB);
 569     MBB->replaceSuccessor(DestBB, BranchBB);
 570     if (TrampolineInsertionPoint == MBB)
 571       TrampolineInsertionPoint = BranchBB;
 572   }
 573
 574   DebugLoc DL = MI.getDebugLoc();
 575   MI.eraseFromParent();
 576
 577   // Create the optional restore block and, initially, place it at the end of
 578   // function. That block will be placed later if it's used; otherwise, it will
 579   // be erased.
 580   MachineBasicBlock *RestoreBB = createNewBlockAfter(MF->back(),
 581                                                      DestBB->getBasicBlock());
 582   std::prev(RestoreBB->getIterator())
 583       ->setIsEndSection(RestoreBB->isEndSection());
 584   RestoreBB->setIsEndSection(false);
 585
 586   TII->insertIndirectBranch(*BranchBB, *DestBB, *RestoreBB, DL,
 587                             BranchBB->getSectionID() != DestBB->getSectionID()
 588                                 ? TM->getMaxCodeSize()
 589                                 : DestOffset - SrcOffset,
 590                             RS.get());
 591
 592   BlockInfo[BranchBB->getNumber()].Size = computeBlockSize(*BranchBB);
 593   adjustBlockOffsets(*MBB);
 594
 595   // If RestoreBB is required, place it appropriately.
 596   if (!RestoreBB->empty()) {
 597     // If the jump is Cold -> Hot, don't place the restore block (which is
 598     // cold) in the middle of the function. Place it at the end.
 599     if (MBB->getSectionID() == MBBSectionID::ColdSectionID &&
 600         DestBB->getSectionID() != MBBSectionID::ColdSectionID) {
 601       MachineBasicBlock *NewBB = createNewBlockAfter(*TrampolineInsertionPoint);
 602       TII->insertUnconditionalBranch(*NewBB, DestBB, DebugLoc());
 603       BlockInfo[NewBB->getNumber()].Size = computeBlockSize(*NewBB);
 604
 605       // New trampolines should be inserted after NewBB.
 606       TrampolineInsertionPoint = NewBB;
 607
 608       // Retarget the unconditional branch to the trampoline block.
 609       BranchBB->replaceSuccessor(DestBB, NewBB);
 610       NewBB->addSuccessor(DestBB);
 611
 612       DestBB = NewBB;
 613     }
 614
 615     // In all other cases, try to place just before DestBB.
 616
 617     // TODO: For multiple far branches to the same destination, there are
 618     // chances that some restore blocks could be shared if they clobber the
 619     // same registers and share the same restore sequence. So far, those
 620     // restore blocks are just duplicated for each far branch.
 621     assert(!DestBB->isEntryBlock());
 622     MachineBasicBlock *PrevBB = &*std::prev(DestBB->getIterator());
 623     // Fall through only if PrevBB has no unconditional branch as one of its
 624     // terminators.
 625     if (auto *FT = PrevBB->getLogicalFallThrough()) {
 626       assert(FT == DestBB);
 627       TII->insertUnconditionalBranch(*PrevBB, FT, DebugLoc());
 628       BlockInfo[PrevBB->getNumber()].Size = computeBlockSize(*PrevBB);
 629     }
 630     // Now, RestoreBB could be placed directly before DestBB.
 631     MF->splice(DestBB->getIterator(), RestoreBB->getIterator());
 632     // Update successors and predecessors.
 633     RestoreBB->addSuccessor(DestBB);
 634     BranchBB->replaceSuccessor(DestBB, RestoreBB);
 635     if (TRI->trackLivenessAfterRegAlloc(*MF))
 636       computeAndAddLiveIns(LiveRegs, *RestoreBB);
 637     // Compute the restore block size.
 638     BlockInfo[RestoreBB->getNumber()].Size = computeBlockSize(*RestoreBB);
 639     // Update the offset starting from the previous block.
 640     adjustBlockOffsets(*PrevBB);
 641
 642     // Fix up section information for RestoreBB and DestBB
 643     RestoreBB->setSectionID(DestBB->getSectionID());
 644     RestoreBB->setIsBeginSection(DestBB->isBeginSection());
 645     DestBB->setIsBeginSection(false);
 646     RelaxedUnconditionals.insert({BranchBB, RestoreBB});
 647   } else {
 648     // Remove restore block if it's not required.
 649     MF->erase(RestoreBB);
 650     RelaxedUnconditionals.insert({BranchBB, DestBB});
 651   }
 652
 653   return true;
 654 }
 655
 656 bool BranchRelaxation::relaxBranchInstructions() {
 657   bool Changed = false;
 658
 659   // Relaxing branches involves creating new basic blocks, so re-eval
 660   // end() for termination.
 661   for (MachineBasicBlock &MBB : *MF) {
 662     // Empty block?
 663     MachineBasicBlock::iterator Last = MBB.getLastNonDebugInstr();
 664     if (Last == MBB.end())
 665       continue;
 666
 667     // Expand the unconditional branch first if necessary. If there is a
 668     // conditional branch, this will end up changing the branch destination of
 669     // it to be over the newly inserted indirect branch block, which may avoid
 670     // the need to try expanding the conditional branch first, saving an extra
 671     // jump.
 672     if (Last->isUnconditionalBranch()) {
 673       // Unconditional branch destination might be unanalyzable, assume these
 674       // are OK.
 675       if (MachineBasicBlock *DestBB = TII->getBranchDestBlock(*Last)) {
 676         if (!isBlockInRange(*Last, *DestBB) && !TII->isTailCall(*Last) &&
 677             !RelaxedUnconditionals.contains({&MBB, DestBB})) {
 678           fixupUnconditionalBranch(*Last);
 679           ++NumUnconditionalRelaxed;
 680           Changed = true;
 681         }
 682       }
 683     }
 684
 685     // Loop over the conditional branches.
 686     MachineBasicBlock::iterator Next;
 687     for (MachineBasicBlock::iterator J = MBB.getFirstTerminator();
 688          J != MBB.end(); J = Next) {
 689       Next = std::next(J);
 690       MachineInstr &MI = *J;
 691
 692       if (!MI.isConditionalBranch())
 693         continue;
 694
 695       if (MI.getOpcode() == TargetOpcode::FAULTING_OP)
 696         // FAULTING_OP's destination is not encoded in the instruction stream
 697         // and thus never needs relaxed.
 698         continue;
 699
 700       MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
 701       if (!isBlockInRange(MI, *DestBB)) {
 702         if (Next != MBB.end() && Next->isConditionalBranch()) {
 703           // If there are multiple conditional branches, this isn't an
 704           // analyzable block. Split later terminators into a new block so
 705           // each one will be analyzable.
 706
 707           splitBlockBeforeInstr(*Next, DestBB);
 708         } else {
 709           fixupConditionalBranch(MI);
 710           ++NumConditionalRelaxed;
 711         }
 712
 713         Changed = true;
 714
 715         // This may have modified all of the terminators, so start over.
 716         Next = MBB.getFirstTerminator();
 717       }
 718     }
 719   }
 720
 721   return Changed;
 722 }
 723
 724 bool BranchRelaxation::runOnMachineFunction(MachineFunction &mf) {
 725   MF = &mf;
 726
 727   LLVM_DEBUG(dbgs() << "***** BranchRelaxation *****\n");
 728
 729   const TargetSubtargetInfo &ST = MF->getSubtarget();
 730   TII = ST.getInstrInfo();
 731   TM = &MF->getTarget();
 732
 733   TRI = ST.getRegisterInfo();
 734   if (TRI->trackLivenessAfterRegAlloc(*MF))
 735     RS.reset(new RegScavenger());
 736
 737   // Renumber all of the machine basic blocks in the function, guaranteeing that
 738   // the numbers agree with the position of the block in the function.
 739   MF->RenumberBlocks();
 740
 741   // Do the initial scan of the function, building up information about the
 742   // sizes of each block.
 743   scanFunction();
 744
 745   LLVM_DEBUG(dbgs() << "  Basic blocks before relaxation\n"; dumpBBs(););
 746
 747   bool MadeChange = false;
 748   while (relaxBranchInstructions())
 749     MadeChange = true;
 750
 751   // After a while, this might be made debug-only, but it is not expensive.
 752   verify();
 753
 754   LLVM_DEBUG(dbgs() << "  Basic blocks after relaxation\n\n"; dumpBBs());
 755
 756   BlockInfo.clear();
 757   RelaxedUnconditionals.clear();
 758
 759   return MadeChange;
 760 }