LCOV - code coverage report
Current view: top level - lib/CodeGen - BranchRelaxation.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 153 166 92.2 %
Date: 2018-07-13 00:08:38 Functions: 21 21 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       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       11956 : 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        7141 :     unsigned postOffset(const MachineBasicBlock &MBB) const {
      68        7141 :       unsigned PO = Offset + Size;
      69        7141 :       unsigned Align = MBB.getAlignment();
      70        7141 :       if (Align == 0)
      71             :         return PO;
      72             : 
      73           8 :       unsigned AlignAmt = 1 << Align;
      74           8 :       unsigned ParentAlign = MBB.getParent()->getAlignment();
      75           8 :       if (Align <= ParentAlign)
      76          12 :         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           4 :       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 &MBB);
     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        3006 :   BranchRelaxation() : MachineFunctionPass(ID) {}
     113             : 
     114             :   bool runOnMachineFunction(MachineFunction &MF) override;
     115             : 
     116        2974 :   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      146610 : 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       32145 : void BranchRelaxation::scanFunction() {
     156       32145 :   BlockInfo.clear();
     157       64290 :   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      101120 :   for (MachineBasicBlock &MBB : *MF)
     164       73660 :     BlockInfo[MBB.getNumber()].Size = computeBlockSize(MBB);
     165             : 
     166             :   // Compute block offsets and known bits.
     167       64290 :   adjustBlockOffsets(*MF->begin());
     168       32145 : }
     169             : 
     170             : /// computeBlockSize - Compute the size for MBB.
     171       36832 : uint64_t BranchRelaxation::computeBlockSize(const MachineBasicBlock &MBB) const {
     172             :   uint64_t Size = 0;
     173      492055 :   for (const MachineInstr &MI : MBB)
     174      418391 :     Size += TII->getInstSizeInBytes(MI);
     175       36832 :   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        2841 : unsigned BranchRelaxation::getInstrOffset(const MachineInstr &MI) const {
     182        2841 :   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        5682 :   unsigned Offset = BlockInfo[MBB->getNumber()].Offset;
     188             : 
     189             :   // Sum instructions before MI in MBB.
     190       39595 :   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       33913 :     Offset += TII->getInstSizeInBytes(*I);
     193             :   }
     194             : 
     195        2841 :   return Offset;
     196             : }
     197             : 
     198       32265 : void BranchRelaxation::adjustBlockOffsets(MachineBasicBlock &Start) {
     199       32265 :   unsigned PrevNum = Start.getNumber();
     200      103858 :   for (auto &MBB : make_range(MachineFunction::iterator(Start), MF->end())) {
     201       39328 :     unsigned Num = MBB.getNumber();
     202       39328 :     if (!Num) // block zero is never changed from offset zero.
     203       32187 :       continue;
     204             :     // Get the offset and known bits at the end of the layout predecessor.
     205             :     // Include the alignment of the current block.
     206       21423 :     BlockInfo[Num].Offset = BlockInfo[PrevNum].postOffset(MBB);
     207             : 
     208             :     PrevNum = Num;
     209             :   }
     210       32265 : }
     211             : 
     212             : /// Insert a new empty basic block and insert it after \BB
     213          39 : MachineBasicBlock *BranchRelaxation::createNewBlockAfter(MachineBasicBlock &BB) {
     214             :   // Create a new MBB for the code after the OrigBB.
     215             :   MachineBasicBlock *NewBB =
     216          39 :       MF->CreateMachineBasicBlock(BB.getBasicBlock());
     217          39 :   MF->insert(++BB.getIterator(), NewBB);
     218             : 
     219             :   // Insert an entry into BlockInfo to align it properly with the block numbers.
     220          78 :   BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
     221             : 
     222          39 :   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           1 : MachineBasicBlock *BranchRelaxation::splitBlockBeforeInstr(MachineInstr &MI,
     229             :                                                            MachineBasicBlock *DestBB) {
     230           1 :   MachineBasicBlock *OrigBB = MI.getParent();
     231             : 
     232             :   // Create a new MBB for the code after the OrigBB.
     233             :   MachineBasicBlock *NewBB =
     234           1 :       MF->CreateMachineBasicBlock(OrigBB->getBasicBlock());
     235           1 :   MF->insert(++OrigBB->getIterator(), NewBB);
     236             : 
     237             :   // Splice the instructions starting with MI over to NewBB.
     238           1 :   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           2 :   TII->insertUnconditionalBranch(*OrigBB, NewBB, DebugLoc());
     245             : 
     246             :   // Insert an entry into BlockInfo to align it properly with the block numbers.
     247           2 :   BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
     248             : 
     249           1 :   NewBB->transferSuccessors(OrigBB);
     250           1 :   OrigBB->addSuccessor(NewBB);
     251           1 :   OrigBB->addSuccessor(DestBB);
     252             : 
     253             :   // Cleanup potential unconditional branch to successor block.
     254             :   // Note that updateTerminator may change the size of the blocks.
     255           1 :   NewBB->updateTerminator();
     256           1 :   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           2 :   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           2 :   BlockInfo[NewBB->getNumber()].Size = computeBlockSize(*NewBB);
     268             : 
     269             :   // All BBOffsets following these blocks must be modified.
     270           1 :   adjustBlockOffsets(*OrigBB);
     271             : 
     272             :   // Need to fix live-in lists if we track liveness.
     273           1 :   if (TRI->trackLivenessAfterRegAlloc(*MF))
     274           1 :     computeAndAddLiveIns(LiveRegs, *NewBB);
     275             : 
     276             :   ++NumSplit;
     277             : 
     278           1 :   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        2806 : bool BranchRelaxation::isBlockInRange(
     284             :   const MachineInstr &MI, const MachineBasicBlock &DestBB) const {
     285        2806 :   int64_t BrOffset = getInstrOffset(MI);
     286        5612 :   int64_t DestOffset = BlockInfo[DestBB.getNumber()].Offset;
     287             : 
     288        5612 :   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         125 :   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          85 : bool BranchRelaxation::fixupConditionalBranch(MachineInstr &MI) {
     304             :   DebugLoc DL = MI.getDebugLoc();
     305          85 :   MachineBasicBlock *MBB = MI.getParent();
     306          85 :   MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
     307             :   MachineBasicBlock *NewBB = nullptr;
     308             :   SmallVector<MachineOperand, 4> Cond;
     309             : 
     310             :   auto insertUncondBranch = [&](MachineBasicBlock *MBB,
     311           4 :                                 MachineBasicBlock *DestBB) {
     312           4 :     unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
     313           4 :     int NewBrSize = 0;
     314           4 :     TII->insertUnconditionalBranch(*MBB, DestBB, DL, &NewBrSize);
     315           4 :     BBSize += NewBrSize;
     316          89 :   };
     317             :   auto insertBranch = [&](MachineBasicBlock *MBB, MachineBasicBlock *TBB,
     318             :                           MachineBasicBlock *FBB,
     319          85 :                           SmallVectorImpl<MachineOperand>& Cond) {
     320          85 :     unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
     321          85 :     int NewBrSize = 0;
     322         170 :     TII->insertBranch(*MBB, TBB, FBB, Cond, DL, &NewBrSize);
     323          85 :     BBSize += NewBrSize;
     324         170 :   };
     325          85 :   auto removeBranch = [&](MachineBasicBlock *MBB) {
     326          85 :     unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
     327          85 :     int RemovedSize = 0;
     328          85 :     TII->removeBranch(*MBB, &RemovedSize);
     329          85 :     BBSize -= RemovedSize;
     330         170 :   };
     331             : 
     332             :   auto finalizeBlockChanges = [&](MachineBasicBlock *MBB,
     333          85 :                                   MachineBasicBlock *NewBB) {
     334             :     // Keep the block offsets up to date.
     335          93 :     adjustBlockOffsets(*MBB);
     336             : 
     337             :     // Need to fix live-in lists if we track liveness.
     338          89 :     if (NewBB && TRI->trackLivenessAfterRegAlloc(*MF))
     339           4 :       computeAndAddLiveIns(LiveRegs, *NewBB);
     340         170 :   };
     341             : 
     342          85 :   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          85 :   bool ReversedCond = !TII->reverseBranchCondition(Cond);
     355          85 :   if (ReversedCond) {
     356          85 :     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           0 :       removeBranch(MBB);
     369           0 :       insertBranch(MBB, FBB, TBB, Cond);
     370             :       finalizeBlockChanges(MBB, nullptr);
     371           0 :       return true;
     372             :     }
     373          85 :     if (FBB) {
     374             :       // We need to split the basic block here to obtain two long-range
     375             :       // unconditional branches.
     376           4 :       NewBB = createNewBlockAfter(*MBB);
     377             : 
     378           4 :       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           4 :       MBB->replaceSuccessor(FBB, NewBB);
     382           4 :       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          85 :     removeBranch(MBB);
     394             :     // Insert a new conditional branch and a new unconditional branch.
     395          85 :     insertBranch(MBB, &NextBB, TBB, Cond);
     396             : 
     397          85 :     finalizeBlockChanges(MBB, NewBB);
     398          85 :     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           0 :   if (!FBB)
     406           0 :     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           0 :   NewBB = createNewBlockAfter(*MBB);
     420           0 :   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           0 :   MBB->replaceSuccessor(TBB, NewBB);
     431           0 :   NewBB->addSuccessor(TBB);
     432             : 
     433             :   // Replace branch in the current (MBB) block.
     434           0 :   removeBranch(MBB);
     435           0 :   insertBranch(MBB, NewBB, FBB, Cond);
     436             : 
     437           0 :   finalizeBlockChanges(MBB, NewBB);
     438           0 :   return true;
     439             : }
     440             : 
     441          35 : bool BranchRelaxation::fixupUnconditionalBranch(MachineInstr &MI) {
     442          35 :   MachineBasicBlock *MBB = MI.getParent();
     443             : 
     444          35 :   unsigned OldBrSize = TII->getInstSizeInBytes(MI);
     445          35 :   MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
     446             : 
     447          70 :   int64_t DestOffset = BlockInfo[DestBB->getNumber()].Offset;
     448          35 :   int64_t SrcOffset = getInstrOffset(MI);
     449             : 
     450             :   assert(!TII->isBranchOffsetInRange(MI.getOpcode(), DestOffset - SrcOffset));
     451             : 
     452          70 :   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          35 :   if (!MBB->empty()) {
     459          35 :     BranchBB = createNewBlockAfter(*MBB);
     460             : 
     461             :     // Add live outs.
     462          99 :     for (const MachineBasicBlock *Succ : MBB->successors()) {
     463         354 :       for (const MachineBasicBlock::RegisterMaskPair &LiveIn : Succ->liveins())
     464             :         BranchBB->addLiveIn(LiveIn);
     465             :     }
     466             : 
     467          35 :     BranchBB->sortUniqueLiveIns();
     468          35 :     BranchBB->addSuccessor(DestBB);
     469          35 :     MBB->replaceSuccessor(DestBB, BranchBB);
     470             :   }
     471             : 
     472             :   DebugLoc DL = MI.getDebugLoc();
     473          35 :   MI.eraseFromParent();
     474         104 :   BlockInfo[BranchBB->getNumber()].Size += TII->insertIndirectBranch(
     475          35 :     *BranchBB, *DestBB, DL, DestOffset - SrcOffset, RS.get());
     476             : 
     477          34 :   adjustBlockOffsets(*MBB);
     478          34 :   return true;
     479             : }
     480             : 
     481       32206 : bool BranchRelaxation::relaxBranchInstructions() {
     482             :   bool Changed = false;
     483             : 
     484             :   // Relaxing branches involves creating new basic blocks, so re-eval
     485             :   // end() for termination.
     486      171388 :   for (MachineFunction::iterator I = MF->begin(); I != MF->end(); ++I) {
     487             :     MachineBasicBlock &MBB = *I;
     488             : 
     489             :     // Empty block?
     490       37386 :     MachineBasicBlock::iterator Last = MBB.getLastNonDebugInstr();
     491       37386 :     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       37265 :     if (Last->isUnconditionalBranch()) {
     500             :       // Unconditional branch destination might be unanalyzable, assume these
     501             :       // are OK.
     502         563 :       if (MachineBasicBlock *DestBB = TII->getBranchDestBlock(*Last)) {
     503         563 :         if (!isBlockInRange(*Last, *DestBB)) {
     504          35 :           fixupUnconditionalBranch(*Last);
     505             :           ++NumUnconditionalRelaxed;
     506             :           Changed = true;
     507             :         }
     508             :       }
     509             :     }
     510             : 
     511             :     // Loop over the conditional branches.
     512             :     MachineBasicBlock::iterator Next;
     513       37264 :     for (MachineBasicBlock::iterator J = MBB.getFirstTerminator();
     514       73219 :          J != MBB.end(); J = Next) {
     515             :       Next = std::next(J);
     516             :       MachineInstr &MI = *J;
     517             : 
     518       35955 :       if (MI.isConditionalBranch()) {
     519        2239 :         MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
     520        2239 :         if (!isBlockInRange(MI, *DestBB)) {
     521          86 :           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           1 :             splitBlockBeforeInstr(*Next, DestBB);
     527             :           } else {
     528          85 :             fixupConditionalBranch(MI);
     529             :             ++NumConditionalRelaxed;
     530             :           }
     531             : 
     532             :           Changed = true;
     533             : 
     534             :           // This may have modified all of the terminators, so start over.
     535          86 :           Next = MBB.getFirstTerminator();
     536             :         }
     537             :       }
     538             :     }
     539             :   }
     540             : 
     541       32205 :   return Changed;
     542             : }
     543             : 
     544       32145 : bool BranchRelaxation::runOnMachineFunction(MachineFunction &mf) {
     545       32145 :   MF = &mf;
     546             : 
     547             :   LLVM_DEBUG(dbgs() << "***** BranchRelaxation *****\n");
     548             : 
     549       32145 :   const TargetSubtargetInfo &ST = MF->getSubtarget();
     550       32145 :   TII = ST.getInstrInfo();
     551             : 
     552       32145 :   TRI = ST.getRegisterInfo();
     553       32145 :   if (TRI->trackLivenessAfterRegAlloc(*MF))
     554       32145 :     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       32145 :   MF->RenumberBlocks();
     559             : 
     560             :   // Do the initial scan of the function, building up information about the
     561             :   // sizes of each block.
     562       32145 :   scanFunction();
     563             : 
     564             :   LLVM_DEBUG(dbgs() << "  Basic blocks before relaxation\n"; dumpBBs(););
     565             : 
     566             :   bool MadeChange = false;
     567       32206 :   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       32144 :   return MadeChange;
     578             : }

Generated by: LCOV version 1.13