File Manager

003 File Manager

Current Path: /usr/src/contrib/llvm-project/llvm/lib/CodeGen

usr / src / contrib / llvm-project / llvm / lib / CodeGen /

📁 ..
📄 AggressiveAntiDepBreaker.cpp(37.23 KB)
📄 AggressiveAntiDepBreaker.h(6.8 KB)
📄 AllocationOrder.cpp(1.96 KB)
📄 AllocationOrder.h(2.96 KB)
📄 Analysis.cpp(32.62 KB)
📁 AsmPrinter
📄 AtomicExpandPass.cpp(71.86 KB)
📄 BBSectionsPrepare.cpp(18.8 KB)
📄 BasicTargetTransformInfo.cpp(1.53 KB)
📄 BranchFolding.cpp(77.92 KB)
📄 BranchFolding.h(7.36 KB)
📄 BranchRelaxation.cpp(19.45 KB)
📄 BreakFalseDeps.cpp(9.79 KB)
📄 BuiltinGCs.cpp(4.88 KB)
📄 CFGuardLongjmp.cpp(3.73 KB)
📄 CFIInstrInserter.cpp(17.53 KB)
📄 CalcSpillWeights.cpp(10.22 KB)
📄 CallingConvLower.cpp(10.4 KB)
📄 CodeGen.cpp(5.28 KB)
📄 CodeGenPrepare.cpp(295.01 KB)
📄 CommandFlags.cpp(24.89 KB)
📄 CriticalAntiDepBreaker.cpp(27.91 KB)
📄 CriticalAntiDepBreaker.h(4.22 KB)
📄 DFAPacketizer.cpp(10.91 KB)
📄 DeadMachineInstructionElim.cpp(6.52 KB)
📄 DetectDeadLanes.cpp(20.74 KB)
📄 DwarfEHPrepare.cpp(9.01 KB)
📄 EarlyIfConversion.cpp(37.51 KB)
📄 EdgeBundles.cpp(3.21 KB)
📄 ExecutionDomainFix.cpp(14.67 KB)
📄 ExpandMemCmp.cpp(33.66 KB)
📄 ExpandPostRAPseudos.cpp(7.28 KB)
📄 ExpandReductions.cpp(7.23 KB)
📄 FEntryInserter.cpp(1.81 KB)
📄 FaultMaps.cpp(4.99 KB)
📄 FinalizeISel.cpp(2.65 KB)
📄 FixupStatepointCallerSaved.cpp(11.06 KB)
📄 FuncletLayout.cpp(2.21 KB)
📄 GCMetadata.cpp(5.1 KB)
📄 GCMetadataPrinter.cpp(748 B)
📄 GCRootLowering.cpp(11.46 KB)
📄 GCStrategy.cpp(708 B)
📁 GlobalISel
📄 GlobalMerge.cpp(24.52 KB)
📄 HardwareLoops.cpp(18.44 KB)
📄 IfConversion.cpp(89.43 KB)
📄 ImplicitNullChecks.cpp(25.14 KB)
📄 IndirectBrExpandPass.cpp(7.79 KB)
📄 InlineSpiller.cpp(58.24 KB)
📄 InterferenceCache.cpp(8.83 KB)
📄 InterferenceCache.h(7.22 KB)
📄 InterleavedAccessPass.cpp(16.59 KB)
📄 InterleavedLoadCombinePass.cpp(42.35 KB)
📄 IntrinsicLowering.cpp(17.08 KB)
📄 LLVMTargetMachine.cpp(10.25 KB)
📄 LatencyPriorityQueue.cpp(5.64 KB)
📄 LazyMachineBlockFrequencyInfo.cpp(3.36 KB)
📄 LexicalScopes.cpp(12.16 KB)
📄 LiveDebugValues.cpp(78.98 KB)
📄 LiveDebugVariables.cpp(51.79 KB)
📄 LiveDebugVariables.h(2.15 KB)
📄 LiveInterval.cpp(46.67 KB)
📄 LiveIntervalCalc.cpp(7.62 KB)
📄 LiveIntervalUnion.cpp(6.36 KB)
📄 LiveIntervals.cpp(64.59 KB)
📄 LivePhysRegs.cpp(11.08 KB)
📄 LiveRangeCalc.cpp(15.72 KB)
📄 LiveRangeEdit.cpp(17.03 KB)
📄 LiveRangeShrink.cpp(8.69 KB)
📄 LiveRangeUtils.h(2.12 KB)
📄 LiveRegMatrix.cpp(7.47 KB)
📄 LiveRegUnits.cpp(4.72 KB)
📄 LiveStacks.cpp(2.95 KB)
📄 LiveVariables.cpp(30.26 KB)
📄 LocalStackSlotAllocation.cpp(17.26 KB)
📄 LoopTraversal.cpp(2.89 KB)
📄 LowLevelType.cpp(1.93 KB)
📄 LowerEmuTLS.cpp(5.66 KB)
📄 MBFIWrapper.cpp(1.57 KB)
📄 MIRCanonicalizerPass.cpp(12.46 KB)
📄 MIRNamerPass.cpp(2.16 KB)
📁 MIRParser
📄 MIRPrinter.cpp(32.67 KB)
📄 MIRPrintingPass.cpp(1.99 KB)
📄 MIRVRegNamerUtils.cpp(6.04 KB)
📄 MIRVRegNamerUtils.h(3.25 KB)
📄 MachineBasicBlock.cpp(50.47 KB)
📄 MachineBlockFrequencyInfo.cpp(10.13 KB)
📄 MachineBlockPlacement.cpp(137.61 KB)
📄 MachineBranchProbabilityInfo.cpp(3.5 KB)
📄 MachineCSE.cpp(31.82 KB)
📄 MachineCombiner.cpp(28.13 KB)
📄 MachineCopyPropagation.cpp(29.21 KB)
📄 MachineDebugify.cpp(6.47 KB)
📄 MachineDominanceFrontier.cpp(1.83 KB)
📄 MachineDominators.cpp(4.86 KB)
📄 MachineFrameInfo.cpp(9.77 KB)
📄 MachineFunction.cpp(42.97 KB)
📄 MachineFunctionPass.cpp(4.78 KB)
📄 MachineFunctionPrinterPass.cpp(2.3 KB)
📄 MachineInstr.cpp(76.39 KB)
📄 MachineInstrBundle.cpp(11.49 KB)
📄 MachineLICM.cpp(57.05 KB)
📄 MachineLoopInfo.cpp(4.98 KB)
📄 MachineLoopUtils.cpp(5.16 KB)
📄 MachineModuleInfo.cpp(9.9 KB)
📄 MachineModuleInfoImpls.cpp(1.5 KB)
📄 MachineOperand.cpp(39.6 KB)
📄 MachineOptimizationRemarkEmitter.cpp(3.29 KB)
📄 MachineOutliner.cpp(42.13 KB)
📄 MachinePipeliner.cpp(111.33 KB)
📄 MachinePostDominators.cpp(2.42 KB)
📄 MachineRegionInfo.cpp(4.75 KB)
📄 MachineRegisterInfo.cpp(22.97 KB)
📄 MachineSSAUpdater.cpp(12.99 KB)
📄 MachineScheduler.cpp(136.89 KB)
📄 MachineSink.cpp(51.94 KB)
📄 MachineSizeOpts.cpp(8.76 KB)
📄 MachineStripDebug.cpp(3.76 KB)
📄 MachineTraceMetrics.cpp(49.58 KB)
📄 MachineVerifier.cpp(107.98 KB)
📄 MacroFusion.cpp(7.55 KB)
📄 ModuloSchedule.cpp(85.09 KB)
📄 NonRelocatableStringpool.cpp(1.65 KB)
📄 OptimizePHIs.cpp(6.7 KB)
📄 PHIElimination.cpp(27.73 KB)
📄 PHIEliminationUtils.cpp(2.56 KB)
📄 PHIEliminationUtils.h(972 B)
📄 ParallelCG.cpp(3.71 KB)
📄 PatchableFunction.cpp(3.44 KB)
📄 PeepholeOptimizer.cpp(78.41 KB)
📄 PostRAHazardRecognizer.cpp(3.5 KB)
📄 PostRASchedulerList.cpp(24.31 KB)
📄 PreISelIntrinsicLowering.cpp(7.91 KB)
📄 ProcessImplicitDefs.cpp(5.4 KB)
📄 PrologEpilogInserter.cpp(50.45 KB)
📄 PseudoSourceValue.cpp(4.71 KB)
📄 RDFGraph.cpp(58.39 KB)
📄 RDFLiveness.cpp(40.7 KB)
📄 RDFRegisters.cpp(11.29 KB)
📄 ReachingDefAnalysis.cpp(21.74 KB)
📄 RegAllocBase.cpp(6.31 KB)
📄 RegAllocBase.h(4.63 KB)
📄 RegAllocBasic.cpp(11.33 KB)
📄 RegAllocFast.cpp(45.78 KB)
📄 RegAllocGreedy.cpp(123.32 KB)
📄 RegAllocPBQP.cpp(33.14 KB)
📄 RegUsageInfoCollector.cpp(7.39 KB)
📄 RegUsageInfoPropagate.cpp(5.07 KB)
📄 RegisterClassInfo.cpp(6.62 KB)
📄 RegisterCoalescer.cpp(151.71 KB)
📄 RegisterCoalescer.h(4.04 KB)
📄 RegisterPressure.cpp(48.86 KB)
📄 RegisterScavenging.cpp(27.48 KB)
📄 RegisterUsageInfo.cpp(3.18 KB)
📄 RenameIndependentSubregs.cpp(14.79 KB)
📄 ResetMachineFunctionPass.cpp(3.48 KB)
📄 SafeStack.cpp(34.12 KB)
📄 SafeStackLayout.cpp(5.3 KB)
📄 SafeStackLayout.h(2.41 KB)
📄 ScalarizeMaskedMemIntrin.cpp(31.46 KB)
📄 ScheduleDAG.cpp(21.34 KB)
📄 ScheduleDAGInstrs.cpp(54.59 KB)
📄 ScheduleDAGPrinter.cpp(3.21 KB)
📄 ScoreboardHazardRecognizer.cpp(7.96 KB)
📁 SelectionDAG
📄 ShadowStackGCLowering.cpp(14.16 KB)
📄 ShrinkWrap.cpp(23.03 KB)
📄 SjLjEHPrepare.cpp(18.93 KB)
📄 SlotIndexes.cpp(9.35 KB)
📄 SpillPlacement.cpp(12.58 KB)
📄 SpillPlacement.h(6.67 KB)
📄 SplitKit.cpp(66.39 KB)
📄 SplitKit.h(23.7 KB)
📄 StackColoring.cpp(49.03 KB)
📄 StackMapLivenessAnalysis.cpp(6.16 KB)
📄 StackMaps.cpp(19.74 KB)
📄 StackProtector.cpp(22.94 KB)
📄 StackSlotColoring.cpp(17.12 KB)
📄 SwiftErrorValueTracking.cpp(11.37 KB)
📄 SwitchLoweringUtils.cpp(18.33 KB)
📄 TailDuplication.cpp(3.32 KB)
📄 TailDuplicator.cpp(38.29 KB)
📄 TargetFrameLoweringImpl.cpp(6.24 KB)
📄 TargetInstrInfo.cpp(51.1 KB)
📄 TargetLoweringBase.cpp(82.53 KB)
📄 TargetLoweringObjectFileImpl.cpp(80.52 KB)
📄 TargetOptionsImpl.cpp(2 KB)
📄 TargetPassConfig.cpp(48.89 KB)
📄 TargetRegisterInfo.cpp(19.15 KB)
📄 TargetSchedule.cpp(13.16 KB)
📄 TargetSubtargetInfo.cpp(1.89 KB)
📄 TwoAddressInstructionPass.cpp(62.08 KB)
📄 TypePromotion.cpp(32.46 KB)
📄 UnreachableBlockElim.cpp(7.48 KB)
📄 ValueTypes.cpp(19.87 KB)
📄 VirtRegMap.cpp(21.4 KB)
📄 WasmEHPrepare.cpp(17.48 KB)
📄 WinEHPrepare.cpp(51.16 KB)
📄 XRayInstrumentation.cpp(9.66 KB)

Editing: BranchRelaxation.cpp

//===- BranchRelaxation.cpp -----------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/LivePhysRegs.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/RegisterScavenging.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/Config/llvm-config.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/Format.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include <cassert>
#include <cstdint>
#include <iterator>
#include <memory>

using namespace llvm;

#define DEBUG_TYPE "branch-relaxation"

STATISTIC(NumSplit, "Number of basic blocks split");
STATISTIC(NumConditionalRelaxed, "Number of conditional branches relaxed");
STATISTIC(NumUnconditionalRelaxed, "Number of unconditional branches relaxed");

#define BRANCH_RELAX_NAME "Branch relaxation pass"

namespace {

class BranchRelaxation : public MachineFunctionPass {
  /// BasicBlockInfo - Information about the offset and size of a single
  /// basic block.
  struct BasicBlockInfo {
    /// Offset - Distance from the beginning of the function to the beginning
    /// of this basic block.
    ///
    /// The offset is always aligned as required by the basic block.
    unsigned Offset = 0;

/// Size - Size of the basic block in bytes.  If the block contains
    /// inline assembly, this is a worst case estimate.
    ///
    /// The size does not include any alignment padding whether from the
    /// beginning of the block, or from an aligned jump table at the end.
    unsigned Size = 0;

BasicBlockInfo() = default;

/// Compute the offset immediately following this block. \p MBB is the next
    /// block.
    unsigned postOffset(const MachineBasicBlock &MBB) const {
      const unsigned PO = Offset + Size;
      const Align Alignment = MBB.getAlignment();
      const Align ParentAlign = MBB.getParent()->getAlignment();
      if (Alignment <= ParentAlign)
        return alignTo(PO, Alignment);

// The alignment of this MBB is larger than the function's alignment, so we
      // can't tell whether or not it will insert nops. Assume that it will.
      return alignTo(PO, Alignment) + Alignment.value() - ParentAlign.value();
    }
  };

SmallVector<BasicBlockInfo, 16> BlockInfo;
  std::unique_ptr<RegScavenger> RS;
  LivePhysRegs LiveRegs;

MachineFunction *MF;
  const TargetRegisterInfo *TRI;
  const TargetInstrInfo *TII;

bool relaxBranchInstructions();
  void scanFunction();

MachineBasicBlock *createNewBlockAfter(MachineBasicBlock &BB);

MachineBasicBlock *splitBlockBeforeInstr(MachineInstr &MI,
                                           MachineBasicBlock *DestBB);
  void adjustBlockOffsets(MachineBasicBlock &Start);
  bool isBlockInRange(const MachineInstr &MI, const MachineBasicBlock &BB) const;

bool fixupConditionalBranch(MachineInstr &MI);
  bool fixupUnconditionalBranch(MachineInstr &MI);
  uint64_t computeBlockSize(const MachineBasicBlock &MBB) const;
  unsigned getInstrOffset(const MachineInstr &MI) const;
  void dumpBBs();
  void verify();

public:
  static char ID;

BranchRelaxation() : MachineFunctionPass(ID) {}

bool runOnMachineFunction(MachineFunction &MF) override;

StringRef getPassName() const override { return BRANCH_RELAX_NAME; }
};

} // end anonymous namespace

char BranchRelaxation::ID = 0;

char &llvm::BranchRelaxationPassID = BranchRelaxation::ID;

INITIALIZE_PASS(BranchRelaxation, DEBUG_TYPE, BRANCH_RELAX_NAME, false, false)

/// verify - check BBOffsets, BBSizes, alignment of islands
void BranchRelaxation::verify() {
#ifndef NDEBUG
  unsigned PrevNum = MF->begin()->getNumber();
  for (MachineBasicBlock &MBB : *MF) {
    const unsigned Num = MBB.getNumber();
    assert(!Num || BlockInfo[PrevNum].postOffset(MBB) <= BlockInfo[Num].Offset);
    assert(BlockInfo[Num].Size == computeBlockSize(MBB));
    PrevNum = Num;
  }
#endif
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
/// print block size and offset information - debugging
LLVM_DUMP_METHOD void BranchRelaxation::dumpBBs() {
  for (auto &MBB : *MF) {
    const BasicBlockInfo &BBI = BlockInfo[MBB.getNumber()];
    dbgs() << format("%%bb.%u\toffset=%08x\t", MBB.getNumber(), BBI.Offset)
           << format("size=%#x\n", BBI.Size);
  }
}
#endif

/// scanFunction - Do the initial scan of the function, building up
/// information about each block.
void BranchRelaxation::scanFunction() {
  BlockInfo.clear();
  BlockInfo.resize(MF->getNumBlockIDs());

// First thing, compute the size of all basic blocks, and see if the function
  // has any inline assembly in it. If so, we have to be conservative about
  // alignment assumptions, as we don't know for sure the size of any
  // instructions in the inline assembly.
  for (MachineBasicBlock &MBB : *MF)
    BlockInfo[MBB.getNumber()].Size = computeBlockSize(MBB);

// Compute block offsets and known bits.
  adjustBlockOffsets(*MF->begin());
}

/// computeBlockSize - Compute the size for MBB.
uint64_t BranchRelaxation::computeBlockSize(const MachineBasicBlock &MBB) const {
  uint64_t Size = 0;
  for (const MachineInstr &MI : MBB)
    Size += TII->getInstSizeInBytes(MI);
  return Size;
}

/// getInstrOffset - Return the current offset of the specified machine
/// instruction from the start of the function.  This offset changes as stuff is
/// moved around inside the function.
unsigned BranchRelaxation::getInstrOffset(const MachineInstr &MI) const {
  const MachineBasicBlock *MBB = MI.getParent();

// The offset is composed of two things: the sum of the sizes of all MBB's
  // before this instruction's block, and the offset from the start of the block
  // it is in.
  unsigned Offset = BlockInfo[MBB->getNumber()].Offset;

// Sum instructions before MI in MBB.
  for (MachineBasicBlock::const_iterator I = MBB->begin(); &*I != &MI; ++I) {
    assert(I != MBB->end() && "Didn't find MI in its own basic block?");
    Offset += TII->getInstSizeInBytes(*I);
  }

return Offset;
}

void BranchRelaxation::adjustBlockOffsets(MachineBasicBlock &Start) {
  unsigned PrevNum = Start.getNumber();
  for (auto &MBB :
       make_range(std::next(MachineFunction::iterator(Start)), MF->end())) {
    unsigned Num = MBB.getNumber();
    // Get the offset and known bits at the end of the layout predecessor.
    // Include the alignment of the current block.
    BlockInfo[Num].Offset = BlockInfo[PrevNum].postOffset(MBB);

PrevNum = Num;
  }
}

/// Insert a new empty basic block and insert it after \BB
MachineBasicBlock *BranchRelaxation::createNewBlockAfter(MachineBasicBlock &BB) {
  // Create a new MBB for the code after the OrigBB.
  MachineBasicBlock *NewBB =
      MF->CreateMachineBasicBlock(BB.getBasicBlock());
  MF->insert(++BB.getIterator(), NewBB);

// Insert an entry into BlockInfo to align it properly with the block numbers.
  BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());

return NewBB;
}

/// Split the basic block containing MI into two blocks, which are joined by
/// an unconditional branch.  Update data structures and renumber blocks to
/// account for this change and returns the newly created block.
MachineBasicBlock *BranchRelaxation::splitBlockBeforeInstr(MachineInstr &MI,
                                                           MachineBasicBlock *DestBB) {
  MachineBasicBlock *OrigBB = MI.getParent();

// Create a new MBB for the code after the OrigBB.
  MachineBasicBlock *NewBB =
      MF->CreateMachineBasicBlock(OrigBB->getBasicBlock());
  MF->insert(++OrigBB->getIterator(), NewBB);

// Splice the instructions starting with MI over to NewBB.
  NewBB->splice(NewBB->end(), OrigBB, MI.getIterator(), OrigBB->end());

// Add an unconditional branch from OrigBB to NewBB.
  // Note the new unconditional branch is not being recorded.
  // There doesn't seem to be meaningful DebugInfo available; this doesn't
  // correspond to anything in the source.
  TII->insertUnconditionalBranch(*OrigBB, NewBB, DebugLoc());

// Insert an entry into BlockInfo to align it properly with the block numbers.
  BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());

NewBB->transferSuccessors(OrigBB);
  OrigBB->addSuccessor(NewBB);
  OrigBB->addSuccessor(DestBB);

// Cleanup potential unconditional branch to successor block.
  // Note that updateTerminator may change the size of the blocks.
  OrigBB->updateTerminator(NewBB);

// Figure out how large the OrigBB is.  As the first half of the original
  // block, it cannot contain a tablejump.  The size includes
  // the new jump we added.  (It should be possible to do this without
  // recounting everything, but it's very confusing, and this is rarely
  // executed.)
  BlockInfo[OrigBB->getNumber()].Size = computeBlockSize(*OrigBB);

// Figure out how large the NewMBB is. As the second half of the original
  // block, it may contain a tablejump.
  BlockInfo[NewBB->getNumber()].Size = computeBlockSize(*NewBB);

// All BBOffsets following these blocks must be modified.
  adjustBlockOffsets(*OrigBB);

// Need to fix live-in lists if we track liveness.
  if (TRI->trackLivenessAfterRegAlloc(*MF))
    computeAndAddLiveIns(LiveRegs, *NewBB);

++NumSplit;

return NewBB;
}

/// isBlockInRange - Returns true if the distance between specific MI and
/// specific BB can fit in MI's displacement field.
bool BranchRelaxation::isBlockInRange(
  const MachineInstr &MI, const MachineBasicBlock &DestBB) const {
  int64_t BrOffset = getInstrOffset(MI);
  int64_t DestOffset = BlockInfo[DestBB.getNumber()].Offset;

if (TII->isBranchOffsetInRange(MI.getOpcode(), DestOffset - BrOffset))
    return true;

LLVM_DEBUG(dbgs() << "Out of range branch to destination "
                    << printMBBReference(DestBB) << " from "
                    << printMBBReference(*MI.getParent()) << " to "
                    << DestOffset << " offset " << DestOffset - BrOffset << '\t'
                    << MI);

return false;
}

/// fixupConditionalBranch - Fix up a conditional branch whose destination is
/// too far away to fit in its displacement field. It is converted to an inverse
/// conditional branch + an unconditional branch to the destination.
bool BranchRelaxation::fixupConditionalBranch(MachineInstr &MI) {
  DebugLoc DL = MI.getDebugLoc();
  MachineBasicBlock *MBB = MI.getParent();
  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
  MachineBasicBlock *NewBB = nullptr;
  SmallVector<MachineOperand, 4> Cond;

auto insertUncondBranch = [&](MachineBasicBlock *MBB,
                                MachineBasicBlock *DestBB) {
    unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
    int NewBrSize = 0;
    TII->insertUnconditionalBranch(*MBB, DestBB, DL, &NewBrSize);
    BBSize += NewBrSize;
  };
  auto insertBranch = [&](MachineBasicBlock *MBB, MachineBasicBlock *TBB,
                          MachineBasicBlock *FBB,
                          SmallVectorImpl<MachineOperand>& Cond) {
    unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
    int NewBrSize = 0;
    TII->insertBranch(*MBB, TBB, FBB, Cond, DL, &NewBrSize);
    BBSize += NewBrSize;
  };
  auto removeBranch = [&](MachineBasicBlock *MBB) {
    unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
    int RemovedSize = 0;
    TII->removeBranch(*MBB, &RemovedSize);
    BBSize -= RemovedSize;
  };

auto finalizeBlockChanges = [&](MachineBasicBlock *MBB,
                                  MachineBasicBlock *NewBB) {
    // Keep the block offsets up to date.
    adjustBlockOffsets(*MBB);

// Need to fix live-in lists if we track liveness.
    if (NewBB && TRI->trackLivenessAfterRegAlloc(*MF))
      computeAndAddLiveIns(LiveRegs, *NewBB);
  };

bool Fail = TII->analyzeBranch(*MBB, TBB, FBB, Cond);
  assert(!Fail && "branches to be relaxed must be analyzable");
  (void)Fail;

// Add an unconditional branch to the destination and invert the branch
  // condition to jump over it:
  // tbz L1
  // =>
  // tbnz L2
  // b   L1
  // L2:

bool ReversedCond = !TII->reverseBranchCondition(Cond);
  if (ReversedCond) {
    if (FBB && isBlockInRange(MI, *FBB)) {
      // Last MI in the BB is an unconditional branch. We can simply invert the
      // condition and swap destinations:
      // beq L1
      // b   L2
      // =>
      // bne L2
      // b   L1
      LLVM_DEBUG(dbgs() << "  Invert condition and swap "
                           "its destination with "
                        << MBB->back());

removeBranch(MBB);
      insertBranch(MBB, FBB, TBB, Cond);
      finalizeBlockChanges(MBB, nullptr);
      return true;
    }
    if (FBB) {
      // We need to split the basic block here to obtain two long-range
      // unconditional branches.
      NewBB = createNewBlockAfter(*MBB);

insertUncondBranch(NewBB, FBB);
      // Update the succesor lists according to the transformation to follow.
      // Do it here since if there's no split, no update is needed.
      MBB->replaceSuccessor(FBB, NewBB);
      NewBB->addSuccessor(FBB);
    }

// We now have an appropriate fall-through block in place (either naturally or
    // just created), so we can use the inverted the condition.
    MachineBasicBlock &NextBB = *std::next(MachineFunction::iterator(MBB));

LLVM_DEBUG(dbgs() << "  Insert B to " << printMBBReference(*TBB)
                      << ", invert condition and change dest. to "
                      << printMBBReference(NextBB) << '\n');

removeBranch(MBB);
    // Insert a new conditional branch and a new unconditional branch.
    insertBranch(MBB, &NextBB, TBB, Cond);

finalizeBlockChanges(MBB, NewBB);
    return true;
  }
  // Branch cond can't be inverted.
  // In this case we always add a block after the MBB.
  LLVM_DEBUG(dbgs() << "  The branch condition can't be inverted. "
                    << "  Insert a new BB after " << MBB->back());

if (!FBB)
    FBB = &(*std::next(MachineFunction::iterator(MBB)));

// This is the block with cond. branch and the distance to TBB is too long.
  //    beq L1
  // L2:

// We do the following transformation:
  //    beq NewBB
  //    b L2
  // NewBB:
  //    b L1
  // L2:

NewBB = createNewBlockAfter(*MBB);
  insertUncondBranch(NewBB, TBB);

LLVM_DEBUG(dbgs() << "  Insert cond B to the new BB "
                    << printMBBReference(*NewBB)
                    << "  Keep the exiting condition.\n"
                    << "  Insert B to " << printMBBReference(*FBB) << ".\n"
                    << "  In the new BB: Insert B to "
                    << printMBBReference(*TBB) << ".\n");

// Update the successor lists according to the transformation to follow.
  MBB->replaceSuccessor(TBB, NewBB);
  NewBB->addSuccessor(TBB);

// Replace branch in the current (MBB) block.
  removeBranch(MBB);
  insertBranch(MBB, NewBB, FBB, Cond);

finalizeBlockChanges(MBB, NewBB);
  return true;
}

bool BranchRelaxation::fixupUnconditionalBranch(MachineInstr &MI) {
  MachineBasicBlock *MBB = MI.getParent();

unsigned OldBrSize = TII->getInstSizeInBytes(MI);
  MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);

int64_t DestOffset = BlockInfo[DestBB->getNumber()].Offset;
  int64_t SrcOffset = getInstrOffset(MI);

assert(!TII->isBranchOffsetInRange(MI.getOpcode(), DestOffset - SrcOffset));

BlockInfo[MBB->getNumber()].Size -= OldBrSize;

MachineBasicBlock *BranchBB = MBB;

// If this was an expanded conditional branch, there is already a single
  // unconditional branch in a block.
  if (!MBB->empty()) {
    BranchBB = createNewBlockAfter(*MBB);

// Add live outs.
    for (const MachineBasicBlock *Succ : MBB->successors()) {
      for (const MachineBasicBlock::RegisterMaskPair &LiveIn : Succ->liveins())
        BranchBB->addLiveIn(LiveIn);
    }

BranchBB->sortUniqueLiveIns();
    BranchBB->addSuccessor(DestBB);
    MBB->replaceSuccessor(DestBB, BranchBB);
  }

DebugLoc DL = MI.getDebugLoc();
  MI.eraseFromParent();
  BlockInfo[BranchBB->getNumber()].Size += TII->insertIndirectBranch(
    *BranchBB, *DestBB, DL, DestOffset - SrcOffset, RS.get());

adjustBlockOffsets(*MBB);
  return true;
}

bool BranchRelaxation::relaxBranchInstructions() {
  bool Changed = false;

// Relaxing branches involves creating new basic blocks, so re-eval
  // end() for termination.
  for (MachineFunction::iterator I = MF->begin(); I != MF->end(); ++I) {
    MachineBasicBlock &MBB = *I;

// Empty block?
    MachineBasicBlock::iterator Last = MBB.getLastNonDebugInstr();
    if (Last == MBB.end())
      continue;

// Expand the unconditional branch first if necessary. If there is a
    // conditional branch, this will end up changing the branch destination of
    // it to be over the newly inserted indirect branch block, which may avoid
    // the need to try expanding the conditional branch first, saving an extra
    // jump.
    if (Last->isUnconditionalBranch()) {
      // Unconditional branch destination might be unanalyzable, assume these
      // are OK.
      if (MachineBasicBlock *DestBB = TII->getBranchDestBlock(*Last)) {
        if (!isBlockInRange(*Last, *DestBB)) {
          fixupUnconditionalBranch(*Last);
          ++NumUnconditionalRelaxed;
          Changed = true;
        }
      }
    }

// Loop over the conditional branches.
    MachineBasicBlock::iterator Next;
    for (MachineBasicBlock::iterator J = MBB.getFirstTerminator();
         J != MBB.end(); J = Next) {
      Next = std::next(J);
      MachineInstr &MI = *J;

if (MI.isConditionalBranch()) {
        MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
        if (!isBlockInRange(MI, *DestBB)) {
          if (Next != MBB.end() && Next->isConditionalBranch()) {
            // If there are multiple conditional branches, this isn't an
            // analyzable block. Split later terminators into a new block so
            // each one will be analyzable.

splitBlockBeforeInstr(*Next, DestBB);
          } else {
            fixupConditionalBranch(MI);
            ++NumConditionalRelaxed;
          }

Changed = true;

// This may have modified all of the terminators, so start over.
          Next = MBB.getFirstTerminator();
        }
      }
    }
  }

return Changed;
}

bool BranchRelaxation::runOnMachineFunction(MachineFunction &mf) {
  MF = &mf;

LLVM_DEBUG(dbgs() << "***** BranchRelaxation *****\n");

const TargetSubtargetInfo &ST = MF->getSubtarget();
  TII = ST.getInstrInfo();

TRI = ST.getRegisterInfo();
  if (TRI->trackLivenessAfterRegAlloc(*MF))
    RS.reset(new RegScavenger());

// Renumber all of the machine basic blocks in the function, guaranteeing that
  // the numbers agree with the position of the block in the function.
  MF->RenumberBlocks();

// Do the initial scan of the function, building up information about the
  // sizes of each block.
  scanFunction();

LLVM_DEBUG(dbgs() << "  Basic blocks before relaxation\n"; dumpBBs(););

bool MadeChange = false;
  while (relaxBranchInstructions())
    MadeChange = true;

// After a while, this might be made debug-only, but it is not expensive.
  verify();

LLVM_DEBUG(dbgs() << "  Basic blocks after relaxation\n\n"; dumpBBs());

BlockInfo.clear();

return MadeChange;
}

003 File Manager

Editing: BranchRelaxation.cpp

Upload File

Create Folder