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/Pass.h"
  23 #include "llvm/Support/Compiler.h"
  24 #include "llvm/Support/Debug.h"
  25 #include "llvm/Support/Format.h"
  26 #include "llvm/Support/MathExtras.h"
  27 #include "llvm/Support/raw_ostream.h"
  28 #include <cassert>
  29 #include <cstdint>
  30 #include <iterator>
  31 #include <memory>
  32
  33 using namespace llvm;
  34
  35 #define DEBUG_TYPE "branch-relaxation"
  36
  37 STATISTIC(NumSplit, "Number of basic blocks split");
  38 STATISTIC(NumConditionalRelaxed, "Number of conditional branches relaxed");
  39 STATISTIC(NumUnconditionalRelaxed, "Number of unconditional branches relaxed");
  40
  41 #define BRANCH_RELAX_NAME "Branch relaxation pass"
  42
  43 namespace {
  44
  45 class BranchRelaxation : public MachineFunctionPass {
  46   /// BasicBlockInfo - Information about the offset and size of a single
  47   /// basic block.
  48   struct BasicBlockInfo {
  49     /// Offset - Distance from the beginning of the function to the beginning
  50     /// of this basic block.
  51     ///
  52     /// The offset is always aligned as required by the basic block.
  53     unsigned Offset = 0;
  54
  55     /// Size - Size of the basic block in bytes.  If the block contains
  56     /// inline assembly, this is a worst case estimate.
  57     ///
  58     /// The size does not include any alignment padding whether from the
  59     /// beginning of the block, or from an aligned jump table at the end.
  60     unsigned Size = 0;
  61
  62     BasicBlockInfo() = default;
  63
  64     /// Compute the offset immediately following this block. \p MBB is the next
  65     /// block.
  66     unsigned postOffset(const MachineBasicBlock &MBB) const {
  67       unsigned PO = Offset + Size;
  68       unsigned Align = MBB.getAlignment();
  69       if (Align == 0)
  70         return PO;
  71
  72       unsigned AlignAmt = 1 << Align;
  73       unsigned ParentAlign = MBB.getParent()->getAlignment();
  74       if (Align <= ParentAlign)
  75         return PO + OffsetToAlignment(PO, AlignAmt);
  76
  77       // The alignment of this MBB is larger than the function's alignment, so we
  78       // can't tell whether or not it will insert nops. Assume that it will.
  79       return PO + AlignAmt + OffsetToAlignment(PO, AlignAmt);
  80     }
  81   };
  82
  83   SmallVector<BasicBlockInfo, 16> BlockInfo;
  84   std::unique_ptr<RegScavenger> RS;
  85   LivePhysRegs LiveRegs;
  86
  87   MachineFunction *MF;
  88   const TargetRegisterInfo *TRI;
  89   const TargetInstrInfo *TII;
  90
  91   bool relaxBranchInstructions();
  92   void scanFunction();
  93
  94   MachineBasicBlock *createNewBlockAfter(MachineBasicBlock &BB);
  95
  96   MachineBasicBlock *splitBlockBeforeInstr(MachineInstr &MI,
  97                                            MachineBasicBlock *DestBB);
  98   void adjustBlockOffsets(MachineBasicBlock &Start);
  99   bool isBlockInRange(const MachineInstr &MI, const MachineBasicBlock &BB) const;
 100
 101   bool fixupConditionalBranch(MachineInstr &MI);
 102   bool fixupUnconditionalBranch(MachineInstr &MI);
 103   uint64_t computeBlockSize(const MachineBasicBlock &MBB) const;
 104   unsigned getInstrOffset(const MachineInstr &MI) const;
 105   void dumpBBs();
 106   void verify();
 107
 108 public:
 109   static char ID;
 110
 111   BranchRelaxation() : MachineFunctionPass(ID) {}
 112
 113   bool runOnMachineFunction(MachineFunction &MF) override;
 114
 115   StringRef getPassName() const override { return BRANCH_RELAX_NAME; }
 116 };
 117
 118 } // end anonymous namespace
 119
 120 char BranchRelaxation::ID = 0;
 121
 122 char &llvm::BranchRelaxationPassID = BranchRelaxation::ID;
 123
 124 INITIALIZE_PASS(BranchRelaxation, DEBUG_TYPE, BRANCH_RELAX_NAME, false, false)
 125
 126 /// verify - check BBOffsets, BBSizes, alignment of islands
 127 void BranchRelaxation::verify() {
 128 #ifndef NDEBUG
 129   unsigned PrevNum = MF->begin()->getNumber();
 130   for (MachineBasicBlock &MBB : *MF) {
 131     unsigned Align = MBB.getAlignment();
 132     unsigned Num = MBB.getNumber();
 133     assert(BlockInfo[Num].Offset % (1u << Align) == 0);
 134     assert(!Num || BlockInfo[PrevNum].postOffset(MBB) <= BlockInfo[Num].Offset);
 135     assert(BlockInfo[Num].Size == computeBlockSize(MBB));
 136     PrevNum = Num;
 137   }
 138 #endif
 139 }
 140
 141 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 142 /// print block size and offset information - debugging
 143 LLVM_DUMP_METHOD void BranchRelaxation::dumpBBs() {
 144   for (auto &MBB : *MF) {
 145     const BasicBlockInfo &BBI = BlockInfo[MBB.getNumber()];
 146     dbgs() << format("%bb.%u\toffset=%08x\t", MBB.getNumber(), BBI.Offset)
 147            << format("size=%#x\n", BBI.Size);
 148   }
 149 }
 150 #endif
 151
 152 /// scanFunction - Do the initial scan of the function, building up
 153 /// information about each block.
 154 void BranchRelaxation::scanFunction() {
 155   BlockInfo.clear();
 156   BlockInfo.resize(MF->getNumBlockIDs());
 157
 158   // First thing, compute the size of all basic blocks, and see if the function
 159   // has any inline assembly in it. If so, we have to be conservative about
 160   // alignment assumptions, as we don't know for sure the size of any
 161   // instructions in the inline assembly.
 162   for (MachineBasicBlock &MBB : *MF)
 163     BlockInfo[MBB.getNumber()].Size = computeBlockSize(MBB);
 164
 165   // Compute block offsets and known bits.
 166   adjustBlockOffsets(*MF->begin());
 167 }
 168
 169 /// computeBlockSize - Compute the size for MBB.
 170 uint64_t BranchRelaxation::computeBlockSize(const MachineBasicBlock &MBB) const {
 171   uint64_t Size = 0;
 172   for (const MachineInstr &MI : MBB)
 173     Size += TII->getInstSizeInBytes(MI);
 174   return Size;
 175 }
 176
 177 /// getInstrOffset - Return the current offset of the specified machine
 178 /// instruction from the start of the function.  This offset changes as stuff is
 179 /// moved around inside the function.
 180 unsigned BranchRelaxation::getInstrOffset(const MachineInstr &MI) const {
 181   const MachineBasicBlock *MBB = MI.getParent();
 182
 183   // The offset is composed of two things: the sum of the sizes of all MBB's
 184   // before this instruction's block, and the offset from the start of the block
 185   // it is in.
 186   unsigned Offset = BlockInfo[MBB->getNumber()].Offset;
 187
 188   // Sum instructions before MI in MBB.
 189   for (MachineBasicBlock::const_iterator I = MBB->begin(); &*I != &MI; ++I) {
 190     assert(I != MBB->end() && "Didn't find MI in its own basic block?");
 191     Offset += TII->getInstSizeInBytes(*I);
 192   }
 193
 194   return Offset;
 195 }
 196
 197 void BranchRelaxation::adjustBlockOffsets(MachineBasicBlock &Start) {
 198   unsigned PrevNum = Start.getNumber();
 199   for (auto &MBB : make_range(MachineFunction::iterator(Start), MF->end())) {
 200     unsigned Num = MBB.getNumber();
 201     if (!Num) // block zero is never changed from offset zero.
 202       continue;
 203     // Get the offset and known bits at the end of the layout predecessor.
 204     // Include the alignment of the current block.
 205     BlockInfo[Num].Offset = BlockInfo[PrevNum].postOffset(MBB);
 206
 207     PrevNum = Num;
 208   }
 209 }
 210
 211 /// Insert a new empty basic block and insert it after \BB
 212 MachineBasicBlock *BranchRelaxation::createNewBlockAfter(MachineBasicBlock &BB) {
 213   // Create a new MBB for the code after the OrigBB.
 214   MachineBasicBlock *NewBB =
 215       MF->CreateMachineBasicBlock(BB.getBasicBlock());
 216   MF->insert(++BB.getIterator(), NewBB);
 217
 218   // Insert an entry into BlockInfo to align it properly with the block numbers.
 219   BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
 220
 221   return NewBB;
 222 }
 223
 224 /// Split the basic block containing MI into two blocks, which are joined by
 225 /// an unconditional branch.  Update data structures and renumber blocks to
 226 /// account for this change and returns the newly created block.
 227 MachineBasicBlock *BranchRelaxation::splitBlockBeforeInstr(MachineInstr &MI,
 228                                                            MachineBasicBlock *DestBB) {
 229   MachineBasicBlock *OrigBB = MI.getParent();
 230
 231   // Create a new MBB for the code after the OrigBB.
 232   MachineBasicBlock *NewBB =
 233       MF->CreateMachineBasicBlock(OrigBB->getBasicBlock());
 234   MF->insert(++OrigBB->getIterator(), NewBB);
 235
 236   // Splice the instructions starting with MI over to NewBB.
 237   NewBB->splice(NewBB->end(), OrigBB, MI.getIterator(), OrigBB->end());
 238
 239   // Add an unconditional branch from OrigBB to NewBB.
 240   // Note the new unconditional branch is not being recorded.
 241   // There doesn't seem to be meaningful DebugInfo available; this doesn't
 242   // correspond to anything in the source.
 243   TII->insertUnconditionalBranch(*OrigBB, NewBB, DebugLoc());
 244
 245   // Insert an entry into BlockInfo to align it properly with the block numbers.
 246   BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
 247
 248   NewBB->transferSuccessors(OrigBB);
 249   OrigBB->addSuccessor(NewBB);
 250   OrigBB->addSuccessor(DestBB);
 251
 252   // Cleanup potential unconditional branch to successor block.
 253   // Note that updateTerminator may change the size of the blocks.
 254   NewBB->updateTerminator();
 255   OrigBB->updateTerminator();
 256
 257   // Figure out how large the OrigBB is.  As the first half of the original
 258   // block, it cannot contain a tablejump.  The size includes
 259   // the new jump we added.  (It should be possible to do this without
 260   // recounting everything, but it's very confusing, and this is rarely
 261   // executed.)
 262   BlockInfo[OrigBB->getNumber()].Size = computeBlockSize(*OrigBB);
 263
 264   // Figure out how large the NewMBB is. As the second half of the original
 265   // block, it may contain a tablejump.
 266   BlockInfo[NewBB->getNumber()].Size = computeBlockSize(*NewBB);
 267
 268   // All BBOffsets following these blocks must be modified.
 269   adjustBlockOffsets(*OrigBB);
 270
 271   // Need to fix live-in lists if we track liveness.
 272   if (TRI->trackLivenessAfterRegAlloc(*MF))
 273     computeAndAddLiveIns(LiveRegs, *NewBB);
 274
 275   ++NumSplit;
 276
 277   return NewBB;
 278 }
 279
 280 /// isBlockInRange - Returns true if the distance between specific MI and
 281 /// specific BB can fit in MI's displacement field.
 282 bool BranchRelaxation::isBlockInRange(
 283   const MachineInstr &MI, const MachineBasicBlock &DestBB) const {
 284   int64_t BrOffset = getInstrOffset(MI);
 285   int64_t DestOffset = BlockInfo[DestBB.getNumber()].Offset;
 286
 287   if (TII->isBranchOffsetInRange(MI.getOpcode(), DestOffset - BrOffset))
 288     return true;
 289
 290   LLVM_DEBUG(dbgs() << "Out of range branch to destination "
 291                     << printMBBReference(DestBB) << " from "
 292                     << printMBBReference(*MI.getParent()) << " to "
 293                     << DestOffset << " offset " << DestOffset - BrOffset << '\t'
 294                     << MI);
 295
 296   return false;
 297 }
 298
 299 /// fixupConditionalBranch - Fix up a conditional branch whose destination is
 300 /// too far away to fit in its displacement field. It is converted to an inverse
 301 /// conditional branch + an unconditional branch to the destination.
 302 bool BranchRelaxation::fixupConditionalBranch(MachineInstr &MI) {
 303   DebugLoc DL = MI.getDebugLoc();
 304   MachineBasicBlock *MBB = MI.getParent();
 305   MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
 306   MachineBasicBlock *NewBB = nullptr;
 307   SmallVector<MachineOperand, 4> Cond;
 308
 309   auto insertUncondBranch = [&](MachineBasicBlock *MBB,
 310                                 MachineBasicBlock *DestBB) {
 311     unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
 312     int NewBrSize = 0;
 313     TII->insertUnconditionalBranch(*MBB, DestBB, DL, &NewBrSize);
 314     BBSize += NewBrSize;
 315   };
 316   auto insertBranch = [&](MachineBasicBlock *MBB, MachineBasicBlock *TBB,
 317                           MachineBasicBlock *FBB,
 318                           SmallVectorImpl<MachineOperand>& Cond) {
 319     unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
 320     int NewBrSize = 0;
 321     TII->insertBranch(*MBB, TBB, FBB, Cond, DL, &NewBrSize);
 322     BBSize += NewBrSize;
 323   };
 324   auto removeBranch = [&](MachineBasicBlock *MBB) {
 325     unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
 326     int RemovedSize = 0;
 327     TII->removeBranch(*MBB, &RemovedSize);
 328     BBSize -= RemovedSize;
 329   };
 330
 331   auto finalizeBlockChanges = [&](MachineBasicBlock *MBB,
 332                                   MachineBasicBlock *NewBB) {
 333     // Keep the block offsets up to date.
 334     adjustBlockOffsets(*MBB);
 335
 336     // Need to fix live-in lists if we track liveness.
 337     if (NewBB && TRI->trackLivenessAfterRegAlloc(*MF))
 338       computeAndAddLiveIns(LiveRegs, *NewBB);
 339   };
 340
 341   bool Fail = TII->analyzeBranch(*MBB, TBB, FBB, Cond);
 342   assert(!Fail && "branches to be relaxed must be analyzable");
 343   (void)Fail;
 344
 345   // Add an unconditional branch to the destination and invert the branch
 346   // condition to jump over it:
 347   // tbz L1
 348   // =>
 349   // tbnz L2
 350   // b   L1
 351   // L2:
 352
 353   bool ReversedCond = !TII->reverseBranchCondition(Cond);
 354   if (ReversedCond) {
 355     if (FBB && isBlockInRange(MI, *FBB)) {
 356       // Last MI in the BB is an unconditional branch. We can simply invert the
 357       // condition and swap destinations:
 358       // beq L1
 359       // b   L2
 360       // =>
 361       // bne L2
 362       // b   L1
 363       LLVM_DEBUG(dbgs() << "  Invert condition and swap "
 364                            "its destination with "
 365                         << MBB->back());
 366
 367       removeBranch(MBB);
 368       insertBranch(MBB, FBB, TBB, Cond);
 369       finalizeBlockChanges(MBB, nullptr);
 370       return true;
 371     }
 372     if (FBB) {
 373       // We need to split the basic block here to obtain two long-range
 374       // unconditional branches.
 375       NewBB = createNewBlockAfter(*MBB);
 376
 377       insertUncondBranch(NewBB, FBB);
 378       // Update the succesor lists according to the transformation to follow.
 379       // Do it here since if there's no split, no update is needed.
 380       MBB->replaceSuccessor(FBB, NewBB);
 381       NewBB->addSuccessor(FBB);
 382     }
 383
 384     // We now have an appropriate fall-through block in place (either naturally or
 385     // just created), so we can use the inverted the condition.
 386     MachineBasicBlock &NextBB = *std::next(MachineFunction::iterator(MBB));
 387
 388     LLVM_DEBUG(dbgs() << "  Insert B to " << printMBBReference(*TBB)
 389                       << ", invert condition and change dest. to "
 390                       << printMBBReference(NextBB) << '\n');
 391
 392     removeBranch(MBB);
 393     // Insert a new conditional branch and a new unconditional branch.
 394     insertBranch(MBB, &NextBB, TBB, Cond);
 395
 396     finalizeBlockChanges(MBB, NewBB);
 397     return true;
 398   }
 399   // Branch cond can't be inverted.
 400   // In this case we always add a block after the MBB.
 401   LLVM_DEBUG(dbgs() << "  The branch condition can't be inverted. "
 402                     << "  Insert a new BB after " << MBB->back());
 403
 404   if (!FBB)
 405     FBB = &(*std::next(MachineFunction::iterator(MBB)));
 406
 407   // This is the block with cond. branch and the distance to TBB is too long.
 408   //    beq L1
 409   // L2:
 410
 411   // We do the following transformation:
 412   //    beq NewBB
 413   //    b L2
 414   // NewBB:
 415   //    b L1
 416   // L2:
 417
 418   NewBB = createNewBlockAfter(*MBB);
 419   insertUncondBranch(NewBB, TBB);
 420
 421   LLVM_DEBUG(dbgs() << "  Insert cond B to the new BB "
 422                     << printMBBReference(*NewBB)
 423                     << "  Keep the exiting condition.\n"
 424                     << "  Insert B to " << printMBBReference(*FBB) << ".\n"
 425                     << "  In the new BB: Insert B to "
 426                     << printMBBReference(*TBB) << ".\n");
 427
 428   // Update the successor lists according to the transformation to follow.
 429   MBB->replaceSuccessor(TBB, NewBB);
 430   NewBB->addSuccessor(TBB);
 431
 432   // Replace branch in the current (MBB) block.
 433   removeBranch(MBB);
 434   insertBranch(MBB, NewBB, FBB, Cond);
 435
 436   finalizeBlockChanges(MBB, NewBB);
 437   return true;
 438 }
 439
 440 bool BranchRelaxation::fixupUnconditionalBranch(MachineInstr &MI) {
 441   MachineBasicBlock *MBB = MI.getParent();
 442
 443   unsigned OldBrSize = TII->getInstSizeInBytes(MI);
 444   MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
 445
 446   int64_t DestOffset = BlockInfo[DestBB->getNumber()].Offset;
 447   int64_t SrcOffset = getInstrOffset(MI);
 448
 449   assert(!TII->isBranchOffsetInRange(MI.getOpcode(), DestOffset - SrcOffset));
 450
 451   BlockInfo[MBB->getNumber()].Size -= OldBrSize;
 452
 453   MachineBasicBlock *BranchBB = MBB;
 454
 455   // If this was an expanded conditional branch, there is already a single
 456   // unconditional branch in a block.
 457   if (!MBB->empty()) {
 458     BranchBB = createNewBlockAfter(*MBB);
 459
 460     // Add live outs.
 461     for (const MachineBasicBlock *Succ : MBB->successors()) {
 462       for (const MachineBasicBlock::RegisterMaskPair &LiveIn : Succ->liveins())
 463         BranchBB->addLiveIn(LiveIn);
 464     }
 465
 466     BranchBB->sortUniqueLiveIns();
 467     BranchBB->addSuccessor(DestBB);
 468     MBB->replaceSuccessor(DestBB, BranchBB);
 469   }
 470
 471   DebugLoc DL = MI.getDebugLoc();
 472   MI.eraseFromParent();
 473   BlockInfo[BranchBB->getNumber()].Size += TII->insertIndirectBranch(
 474     *BranchBB, *DestBB, DL, DestOffset - SrcOffset, RS.get());
 475
 476   adjustBlockOffsets(*MBB);
 477   return true;
 478 }
 479
 480 bool BranchRelaxation::relaxBranchInstructions() {
 481   bool Changed = false;
 482
 483   // Relaxing branches involves creating new basic blocks, so re-eval
 484   // end() for termination.
 485   for (MachineFunction::iterator I = MF->begin(); I != MF->end(); ++I) {
 486     MachineBasicBlock &MBB = *I;
 487
 488     // Empty block?
 489     MachineBasicBlock::iterator Last = MBB.getLastNonDebugInstr();
 490     if (Last == MBB.end())
 491       continue;
 492
 493     // Expand the unconditional branch first if necessary. If there is a
 494     // conditional branch, this will end up changing the branch destination of
 495     // it to be over the newly inserted indirect branch block, which may avoid
 496     // the need to try expanding the conditional branch first, saving an extra
 497     // jump.
 498     if (Last->isUnconditionalBranch()) {
 499       // Unconditional branch destination might be unanalyzable, assume these
 500       // are OK.
 501       if (MachineBasicBlock *DestBB = TII->getBranchDestBlock(*Last)) {
 502         if (!isBlockInRange(*Last, *DestBB)) {
 503           fixupUnconditionalBranch(*Last);
 504           ++NumUnconditionalRelaxed;
 505           Changed = true;
 506         }
 507       }
 508     }
 509
 510     // Loop over the conditional branches.
 511     MachineBasicBlock::iterator Next;
 512     for (MachineBasicBlock::iterator J = MBB.getFirstTerminator();
 513          J != MBB.end(); J = Next) {
 514       Next = std::next(J);
 515       MachineInstr &MI = *J;
 516
 517       if (MI.isConditionalBranch()) {
 518         MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
 519         if (!isBlockInRange(MI, *DestBB)) {
 520           if (Next != MBB.end() && Next->isConditionalBranch()) {
 521             // If there are multiple conditional branches, this isn't an
 522             // analyzable block. Split later terminators into a new block so
 523             // each one will be analyzable.
 524
 525             splitBlockBeforeInstr(*Next, DestBB);
 526           } else {
 527             fixupConditionalBranch(MI);
 528             ++NumConditionalRelaxed;
 529           }
 530
 531           Changed = true;
 532
 533           // This may have modified all of the terminators, so start over.
 534           Next = MBB.getFirstTerminator();
 535         }
 536       }
 537     }
 538   }
 539
 540   return Changed;
 541 }
 542
 543 bool BranchRelaxation::runOnMachineFunction(MachineFunction &mf) {
 544   MF = &mf;
 545
 546   LLVM_DEBUG(dbgs() << "***** BranchRelaxation *****\n");
 547
 548   const TargetSubtargetInfo &ST = MF->getSubtarget();
 549   TII = ST.getInstrInfo();
 550
 551   TRI = ST.getRegisterInfo();
 552   if (TRI->trackLivenessAfterRegAlloc(*MF))
 553     RS.reset(new RegScavenger());
 554
 555   // Renumber all of the machine basic blocks in the function, guaranteeing that
 556   // the numbers agree with the position of the block in the function.
 557   MF->RenumberBlocks();
 558
 559   // Do the initial scan of the function, building up information about the
 560   // sizes of each block.
 561   scanFunction();
 562
 563   LLVM_DEBUG(dbgs() << "  Basic blocks before relaxation\n"; dumpBBs(););
 564
 565   bool MadeChange = false;
 566   while (relaxBranchInstructions())
 567     MadeChange = true;
 568
 569   // After a while, this might be made debug-only, but it is not expensive.
 570   verify();
 571
 572   LLVM_DEBUG(dbgs() << "  Basic blocks after relaxation\n\n"; dumpBBs());
 573
 574   BlockInfo.clear();
 575
 576   return MadeChange;
 577 }