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