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