Index: include/llvm/CodeGen/Passes.h =================================================================== --- include/llvm/CodeGen/Passes.h +++ include/llvm/CodeGen/Passes.h @@ -181,6 +181,10 @@ /// branches. extern char &BranchFolderPassID; + /// BranchRelaxation - This pass replaces branches that need to jump further + /// than is supported by a branch instruction. + extern char &BranchRelaxationPassID; + /// MachineFunctionPrinterPass - This pass prints out MachineInstr's. extern char &MachineFunctionPrinterPassID; Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -79,6 +79,7 @@ void initializeBoundsCheckingPass(PassRegistry&); void initializeBranchFolderPassPass(PassRegistry&); void initializeBranchProbabilityInfoWrapperPassPass(PassRegistry&); +void initializeBranchRelaxationPass(PassRegistry&); void initializeBreakCriticalEdgesPass(PassRegistry&); void initializeCFGOnlyPrinterPass(PassRegistry&); void initializeCFGOnlyViewerPass(PassRegistry&); Index: lib/CodeGen/BranchRelaxation.cpp =================================================================== --- /dev/null +++ lib/CodeGen/BranchRelaxation.cpp @@ -0,0 +1,406 @@ +//===-- BranchRelaxation.cpp ----------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "llvm/CodeGen/Passes.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetSubtargetInfo.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/Format.h" +#include "llvm/Support/raw_ostream.h" + +using namespace llvm; + +#define DEBUG_TYPE "branch-relaxation" + +STATISTIC(NumSplit, "Number of basic blocks split"); +STATISTIC(NumConditionalRelaxed, "Number of conditional 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; + + /// 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; + + BasicBlockInfo() : Offset(0), Size(0) {} + + /// Compute the offset immediately following this block. If LogAlign is + /// specified, return the offset the successor block will get if it has + /// this alignment. + unsigned postOffset(unsigned LogAlign = 0) const { + unsigned PO = Offset + Size; + unsigned Align = 1 << LogAlign; + return (PO + Align - 1) / Align * Align; + } + }; + + SmallVector BlockInfo; + + MachineFunction *MF; + const TargetInstrInfo *TII; + + bool relaxBranchInstructions(); + void scanFunction(); + MachineBasicBlock *splitBlockBeforeInstr(MachineInstr &MI); + void adjustBlockOffsets(MachineBasicBlock &MBB); + bool isBlockInRange(const MachineInstr &MI, const MachineBasicBlock &BB) const; + + bool fixupConditionalBranch(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; + + const char *getPassName() const override { + return BRANCH_RELAX_NAME; + } +}; + +} + +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) { + unsigned Align = MBB.getAlignment(); + unsigned Num = MBB.getNumber(); + assert(BlockInfo[Num].Offset % (1u << Align) == 0); + assert(!Num || BlockInfo[PrevNum].postOffset() <= BlockInfo[Num].Offset); + PrevNum = Num; + } +#endif +} + +/// print block size and offset information - debugging +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); + } +} + +/// 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(MachineFunction::iterator(Start), MF->end())) { + unsigned Num = MBB.getNumber(); + if (!Num) // block zero is never changed from offset zero. + continue; + // Get the offset and known bits at the end of the layout predecessor. + // Include the alignment of the current block. + unsigned LogAlign = MBB.getAlignment(); + BlockInfo[Num].Offset = BlockInfo[PrevNum].postOffset(LogAlign); + PrevNum = Num; + } +} + +/// 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. +/// NOTE: Successor list of the original BB is out of date after this function, +/// and must be updated by the caller! Other transforms follow using this +/// utility function, so no point updating now rather than waiting. +MachineBasicBlock *BranchRelaxation::splitBlockBeforeInstr(MachineInstr &MI) { + 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()); + + // 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); + + ++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; + + DEBUG( + dbgs() << "Out of range branch to destination BB#" << DestBB.getNumber() + << " from BB#" << MI.getParent()->getNumber() + << " 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; + SmallVector Cond; + + 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: + + 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 + DEBUG(dbgs() << " Invert condition and swap " + "its destination with " << MBB->back()); + + TII->reverseBranchCondition(Cond); + int OldSize = 0, NewSize = 0; + TII->removeBranch(*MBB, &OldSize); + TII->insertBranch(*MBB, FBB, TBB, Cond, DL, &NewSize); + + BlockInfo[MBB->getNumber()].Size += (NewSize - OldSize); + return true; + } else if (FBB) { + // We need to split the basic block here to obtain two long-range + // unconditional branches. + auto &NewBB = *MF->CreateMachineBasicBlock(MBB->getBasicBlock()); + MF->insert(++MBB->getIterator(), &NewBB); + + // Insert an entry into BlockInfo to align it properly with the block + // numbers. + BlockInfo.insert(BlockInfo.begin() + NewBB.getNumber(), BasicBlockInfo()); + + unsigned &NewBBSize = BlockInfo[NewBB.getNumber()].Size; + int NewBrSize; + TII->insertUnconditionalBranch(NewBB, FBB, DL, &NewBrSize); + NewBBSize += NewBrSize; + + // Update the successor 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 invert the condition. + MachineBasicBlock &NextBB = *std::next(MachineFunction::iterator(MBB)); + + DEBUG(dbgs() << " Insert B to BB#" << TBB->getNumber() + << ", invert condition and change dest. to BB#" + << NextBB.getNumber() << '\n'); + + unsigned &MBBSize = BlockInfo[MBB->getNumber()].Size; + + // Insert a new conditional branch and a new unconditional branch. + int RemovedSize = 0; + TII->reverseBranchCondition(Cond); + TII->removeBranch(*MBB, &RemovedSize); + MBBSize -= RemovedSize; + + int AddedSize = 0; + TII->insertBranch(*MBB, &NextBB, TBB, Cond, DL, &AddedSize); + MBBSize += AddedSize; + + // Finally, keep the block offsets up to date. + 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; + MachineBasicBlock::iterator J = MBB.getFirstTerminator(); + if (J == MBB.end()) + continue; + + + 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. + + MachineBasicBlock *NewBB = splitBlockBeforeInstr(*Next); + NewBB->transferSuccessors(&MBB); + MBB.addSuccessor(NewBB); + MBB.addSuccessor(DestBB); + + // Cleanup potential unconditional branch to successor block. + NewBB->updateTerminator(); + MBB.updateTerminator(); + } 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; + + DEBUG(dbgs() << "***** BranchRelaxation *****\n"); + + TII = MF->getSubtarget().getInstrInfo(); + + // 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(); + + 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(); + + DEBUG(dbgs() << " Basic blocks after relaxation\n\n"; dumpBBs()); + + BlockInfo.clear(); + + return MadeChange; +} Index: lib/CodeGen/CMakeLists.txt =================================================================== --- lib/CodeGen/CMakeLists.txt +++ lib/CodeGen/CMakeLists.txt @@ -5,6 +5,7 @@ AtomicExpandPass.cpp BasicTargetTransformInfo.cpp BranchFolding.cpp + BranchRelaxation.cpp BuiltinGCs.cpp CalcSpillWeights.cpp CallingConvLower.cpp Index: lib/CodeGen/CodeGen.cpp =================================================================== --- lib/CodeGen/CodeGen.cpp +++ lib/CodeGen/CodeGen.cpp @@ -22,6 +22,7 @@ void llvm::initializeCodeGen(PassRegistry &Registry) { initializeAtomicExpandPass(Registry); initializeBranchFolderPassPass(Registry); + initializeBranchRelaxationPass(Registry); initializeCodeGenPreparePass(Registry); initializeCountingFunctionInserterPass(Registry); initializeDeadMachineInstructionElimPass(Registry); Index: lib/Target/AArch64/AArch64.h =================================================================== --- lib/Target/AArch64/AArch64.h +++ lib/Target/AArch64/AArch64.h @@ -30,7 +30,6 @@ FunctionPass *createAArch64RedundantCopyEliminationPass(); FunctionPass *createAArch64ConditionalCompares(); FunctionPass *createAArch64AdvSIMDScalar(); -FunctionPass *createAArch64BranchRelaxation(); FunctionPass *createAArch64ISelDag(AArch64TargetMachine &TM, CodeGenOpt::Level OptLevel); FunctionPass *createAArch64StorePairSuppressPass(); @@ -50,7 +49,6 @@ void initializeAArch64A57FPLoadBalancingPass(PassRegistry&); void initializeAArch64AddressTypePromotionPass(PassRegistry&); void initializeAArch64AdvSIMDScalarPass(PassRegistry&); -void initializeAArch64BranchRelaxationPass(PassRegistry&); void initializeAArch64CollectLOHPass(PassRegistry&); void initializeAArch64ConditionalComparesPass(PassRegistry&); void initializeAArch64ConditionOptimizerPass(PassRegistry&); Index: lib/Target/AArch64/AArch64BranchRelaxation.cpp =================================================================== --- lib/Target/AArch64/AArch64BranchRelaxation.cpp +++ /dev/null @@ -1,418 +0,0 @@ -//===-- AArch64BranchRelaxation.cpp - AArch64 branch relaxation -----------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#include "AArch64.h" -#include "AArch64InstrInfo.h" -#include "AArch64MachineFunctionInfo.h" -#include "AArch64Subtarget.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/CodeGen/MachineFunctionPass.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/ErrorHandling.h" -#include "llvm/Support/Format.h" -#include "llvm/Support/raw_ostream.h" -using namespace llvm; - -#define DEBUG_TYPE "aarch64-branch-relax" - -STATISTIC(NumSplit, "Number of basic blocks split"); -STATISTIC(NumConditionalRelaxed, "Number of conditional branches relaxed"); - -namespace llvm { -void initializeAArch64BranchRelaxationPass(PassRegistry &); -} - -#define AARCH64_BR_RELAX_NAME "AArch64 branch relaxation pass" - -namespace { -class AArch64BranchRelaxation : 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; - - /// 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; - - BasicBlockInfo() : Offset(0), Size(0) {} - - /// Compute the offset immediately following this block. If LogAlign is - /// specified, return the offset the successor block will get if it has - /// this alignment. - unsigned postOffset(unsigned LogAlign = 0) const { - unsigned PO = Offset + Size; - unsigned Align = 1 << LogAlign; - return (PO + Align - 1) / Align * Align; - } - }; - - SmallVector BlockInfo; - - MachineFunction *MF; - const AArch64InstrInfo *TII; - - bool relaxBranchInstructions(); - void scanFunction(); - MachineBasicBlock *splitBlockBeforeInstr(MachineInstr &MI); - void adjustBlockOffsets(MachineBasicBlock &MBB); - bool isBlockInRange(const MachineInstr &MI, const MachineBasicBlock &BB) const; - - bool fixupConditionalBranch(MachineInstr &MI); - void computeBlockSize(const MachineBasicBlock &MBB); - unsigned getInstrOffset(const MachineInstr &MI) const; - void dumpBBs(); - void verify(); - -public: - static char ID; - AArch64BranchRelaxation() : MachineFunctionPass(ID) { - initializeAArch64BranchRelaxationPass(*PassRegistry::getPassRegistry()); - } - - bool runOnMachineFunction(MachineFunction &MF) override; - - const char *getPassName() const override { - return AARCH64_BR_RELAX_NAME; - } -}; -char AArch64BranchRelaxation::ID = 0; -} - -INITIALIZE_PASS(AArch64BranchRelaxation, "aarch64-branch-relax", - AARCH64_BR_RELAX_NAME, false, false) - -/// verify - check BBOffsets, BBSizes, alignment of islands -void AArch64BranchRelaxation::verify() { -#ifndef NDEBUG - unsigned PrevNum = MF->begin()->getNumber(); - for (MachineBasicBlock &MBB : *MF) { - unsigned Align = MBB.getAlignment(); - unsigned Num = MBB.getNumber(); - assert(BlockInfo[Num].Offset % (1u << Align) == 0); - assert(!Num || BlockInfo[PrevNum].postOffset() <= BlockInfo[Num].Offset); - PrevNum = Num; - } -#endif -} - -/// print block size and offset information - debugging -void AArch64BranchRelaxation::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); - } -} - -/// scanFunction - Do the initial scan of the function, building up -/// information about each block. -void AArch64BranchRelaxation::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) - computeBlockSize(MBB); - - // Compute block offsets and known bits. - adjustBlockOffsets(*MF->begin()); -} - -/// computeBlockSize - Compute the size for MBB. -/// This function updates BlockInfo directly. -void AArch64BranchRelaxation::computeBlockSize(const MachineBasicBlock &MBB) { - unsigned Size = 0; - for (const MachineInstr &MI : MBB) - Size += TII->getInstSizeInBytes(MI); - BlockInfo[MBB.getNumber()].Size = 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 AArch64BranchRelaxation::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 AArch64BranchRelaxation::adjustBlockOffsets(MachineBasicBlock &Start) { - unsigned PrevNum = Start.getNumber(); - for (auto &MBB : make_range(MachineFunction::iterator(Start), MF->end())) { - unsigned Num = MBB.getNumber(); - if (!Num) // block zero is never changed from offset zero. - continue; - // Get the offset and known bits at the end of the layout predecessor. - // Include the alignment of the current block. - unsigned LogAlign = MBB.getAlignment(); - BlockInfo[Num].Offset = BlockInfo[PrevNum].postOffset(LogAlign); - PrevNum = Num; - } -} - -/// 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. -/// NOTE: Successor list of the original BB is out of date after this function, -/// and must be updated by the caller! Other transforms follow using this -/// utility function, so no point updating now rather than waiting. -MachineBasicBlock * -AArch64BranchRelaxation::splitBlockBeforeInstr(MachineInstr &MI) { - 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()); - - // 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.) - computeBlockSize(*OrigBB); - - // Figure out how large the NewMBB is. As the second half of the original - // block, it may contain a tablejump. - computeBlockSize(*NewBB); - - // All BBOffsets following these blocks must be modified. - adjustBlockOffsets(*OrigBB); - - ++NumSplit; - - return NewBB; -} - -/// isBlockInRange - Returns true if the distance between specific MI and -/// specific BB can fit in MI's displacement field. -bool AArch64BranchRelaxation::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; - - DEBUG( - dbgs() << "Out of range branch to destination BB#" << DestBB.getNumber() - << " from BB#" << MI.getParent()->getNumber() - << " 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 AArch64BranchRelaxation::fixupConditionalBranch(MachineInstr &MI) { - DebugLoc DL = MI.getDebugLoc(); - MachineBasicBlock *MBB = MI.getParent(); - MachineBasicBlock *TBB = nullptr, *FBB = nullptr; - SmallVector Cond; - - 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: - - 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 - DEBUG(dbgs() << " Invert condition and swap " - "its destination with " << MBB->back()); - - TII->reverseBranchCondition(Cond); - int OldSize = 0, NewSize = 0; - TII->removeBranch(*MBB, &OldSize); - TII->insertBranch(*MBB, FBB, TBB, Cond, DL, &NewSize); - - BlockInfo[MBB->getNumber()].Size += (NewSize - OldSize); - return true; - } else if (FBB) { - // We need to split the basic block here to obtain two long-range - // unconditional branches. - auto &NewBB = *MF->CreateMachineBasicBlock(MBB->getBasicBlock()); - MF->insert(++MBB->getIterator(), &NewBB); - - // Insert an entry into BlockInfo to align it properly with the block - // numbers. - BlockInfo.insert(BlockInfo.begin() + NewBB.getNumber(), BasicBlockInfo()); - - unsigned &NewBBSize = BlockInfo[NewBB.getNumber()].Size; - int NewBrSize; - TII->insertUnconditionalBranch(NewBB, FBB, DL, &NewBrSize); - NewBBSize += NewBrSize; - - // Update the successor 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 invert the condition. - MachineBasicBlock &NextBB = *std::next(MachineFunction::iterator(MBB)); - - DEBUG(dbgs() << " Insert B to BB#" << TBB->getNumber() - << ", invert condition and change dest. to BB#" - << NextBB.getNumber() << '\n'); - - unsigned &MBBSize = BlockInfo[MBB->getNumber()].Size; - - // Insert a new conditional branch and a new unconditional branch. - int RemovedSize = 0; - TII->reverseBranchCondition(Cond); - TII->removeBranch(*MBB, &RemovedSize); - MBBSize -= RemovedSize; - - int AddedSize = 0; - TII->insertBranch(*MBB, &NextBB, TBB, Cond, DL, &AddedSize); - MBBSize += AddedSize; - - // Finally, keep the block offsets up to date. - adjustBlockOffsets(*MBB); - return true; -} - -bool AArch64BranchRelaxation::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; - MachineBasicBlock::iterator J = MBB.getFirstTerminator(); - if (J == MBB.end()) - continue; - - 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. - - MachineBasicBlock *NewBB = splitBlockBeforeInstr(*Next); - NewBB->transferSuccessors(&MBB); - MBB.addSuccessor(NewBB); - MBB.addSuccessor(DestBB); - - // Cleanup potential unconditional branch to successor block. - NewBB->updateTerminator(); - MBB.updateTerminator(); - } else { - fixupConditionalBranch(MI); - ++NumConditionalRelaxed; - } - - Changed = true; - - // This may have modified all of the terminators, so start over. - Next = MBB.getFirstTerminator(); - } - - } - } - } - - return Changed; -} - -bool AArch64BranchRelaxation::runOnMachineFunction(MachineFunction &mf) { - MF = &mf; - - DEBUG(dbgs() << "***** AArch64BranchRelaxation *****\n"); - - TII = MF->getSubtarget().getInstrInfo(); - - // 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(); - - 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(); - - DEBUG(dbgs() << " Basic blocks after relaxation\n\n"; dumpBBs()); - - BlockInfo.clear(); - - return MadeChange; -} - -/// Returns an instance of the AArch64 Branch Relaxation pass. -FunctionPass *llvm::createAArch64BranchRelaxation() { - return new AArch64BranchRelaxation(); -} Index: lib/Target/AArch64/AArch64TargetMachine.cpp =================================================================== --- lib/Target/AArch64/AArch64TargetMachine.cpp +++ lib/Target/AArch64/AArch64TargetMachine.cpp @@ -135,7 +135,6 @@ initializeAArch64A57FPLoadBalancingPass(*PR); initializeAArch64AddressTypePromotionPass(*PR); initializeAArch64AdvSIMDScalarPass(*PR); - initializeAArch64BranchRelaxationPass(*PR); initializeAArch64CollectLOHPass(*PR); initializeAArch64ConditionalComparesPass(*PR); initializeAArch64ConditionOptimizerPass(*PR); @@ -487,7 +486,8 @@ // Relax conditional branch instructions if they're otherwise out of // range of their destination. if (BranchRelaxation) - addPass(createAArch64BranchRelaxation()); + addPass(&BranchRelaxationPassID); + if (TM->getOptLevel() != CodeGenOpt::None && EnableCollectLOH && TM->getTargetTriple().isOSBinFormatMachO()) addPass(createAArch64CollectLOHPass()); Index: lib/Target/AArch64/CMakeLists.txt =================================================================== --- lib/Target/AArch64/CMakeLists.txt +++ lib/Target/AArch64/CMakeLists.txt @@ -38,7 +38,6 @@ AArch64AddressTypePromotion.cpp AArch64AdvSIMDScalarPass.cpp AArch64AsmPrinter.cpp - AArch64BranchRelaxation.cpp AArch64CleanupLocalDynamicTLSPass.cpp AArch64CollectLOH.cpp AArch64ConditionalCompares.cpp Index: test/CodeGen/MIR/AArch64/inst-size-patchpoint.mir =================================================================== --- test/CodeGen/MIR/AArch64/inst-size-patchpoint.mir +++ test/CodeGen/MIR/AArch64/inst-size-patchpoint.mir @@ -1,4 +1,4 @@ -# RUN: llc -mtriple=aarch64-unknown -run-pass aarch64-branch-relax -aarch64-tbz-offset-bits=4 %s -o - | FileCheck %s +# RUN: llc -mtriple=aarch64-unknown -run-pass branch-relaxation -aarch64-tbz-offset-bits=4 %s -o - | FileCheck %s --- | ; ModuleID = '/tmp/test.ll' source_filename = "test.ll" Index: test/CodeGen/MIR/AArch64/inst-size-stackmap.mir =================================================================== --- test/CodeGen/MIR/AArch64/inst-size-stackmap.mir +++ test/CodeGen/MIR/AArch64/inst-size-stackmap.mir @@ -1,4 +1,4 @@ -# RUN: llc -mtriple=aarch64-unknown -run-pass aarch64-branch-relax -aarch64-tbz-offset-bits=4 %s -o - | FileCheck %s +# RUN: llc -mtriple=aarch64-unknown -run-pass branch-relaxation -aarch64-tbz-offset-bits=4 %s -o - | FileCheck %s --- | ; ModuleID = 'test.ll' source_filename = "test.ll" Index: test/CodeGen/MIR/AArch64/inst-size-tlsdesc-callseq.mir =================================================================== --- test/CodeGen/MIR/AArch64/inst-size-tlsdesc-callseq.mir +++ test/CodeGen/MIR/AArch64/inst-size-tlsdesc-callseq.mir @@ -1,4 +1,4 @@ -# RUN: llc -mtriple=aarch64-unknown -run-pass aarch64-branch-relax -aarch64-tbz-offset-bits=4 %s -o - | FileCheck %s +# RUN: llc -mtriple=aarch64-unknown -run-pass branch-relaxation -aarch64-tbz-offset-bits=4 %s -o - | FileCheck %s --- | ; ModuleID = 'test.ll' source_filename = "test.ll"