contrib/llvm/lib/CodeGen/BranchRelaxation.cpp

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