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