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