| //===-- 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/CodeGen/MachineInstrBuilder.h" |
| #include "llvm/Support/CommandLine.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" |
| |
| static cl::opt<bool> |
| BranchRelaxation("aarch64-branch-relax", cl::Hidden, cl::init(true), |
| cl::desc("Relax out of range conditional branches")); |
| |
| static cl::opt<unsigned> |
| TBZDisplacementBits("aarch64-tbz-offset-bits", cl::Hidden, cl::init(14), |
| cl::desc("Restrict range of TB[N]Z instructions (DEBUG)")); |
| |
| static cl::opt<unsigned> |
| CBZDisplacementBits("aarch64-cbz-offset-bits", cl::Hidden, cl::init(19), |
| cl::desc("Restrict range of CB[N]Z instructions (DEBUG)")); |
| |
| static cl::opt<unsigned> |
| BCCDisplacementBits("aarch64-bcc-offset-bits", cl::Hidden, cl::init(19), |
| cl::desc("Restrict range of Bcc instructions (DEBUG)")); |
| |
| STATISTIC(NumSplit, "Number of basic blocks split"); |
| STATISTIC(NumRelaxed, "Number of conditional branches relaxed"); |
| |
| 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<BasicBlockInfo, 16> BlockInfo; |
| |
| MachineFunction *MF; |
| const AArch64InstrInfo *TII; |
| |
| bool relaxBranchInstructions(); |
| void scanFunction(); |
| MachineBasicBlock *splitBlockBeforeInstr(MachineInstr *MI); |
| void adjustBlockOffsets(MachineBasicBlock &MBB); |
| bool isBlockInRange(MachineInstr *MI, MachineBasicBlock *BB, unsigned Disp); |
| bool fixupConditionalBranch(MachineInstr *MI); |
| void computeBlockSize(const MachineBasicBlock &MBB); |
| unsigned getInstrOffset(MachineInstr *MI) const; |
| void dumpBBs(); |
| void verify(); |
| |
| public: |
| static char ID; |
| AArch64BranchRelaxation() : MachineFunctionPass(ID) {} |
| |
| bool runOnMachineFunction(MachineFunction &MF) override; |
| |
| const char *getPassName() const override { |
| return "AArch64 branch relaxation pass"; |
| } |
| }; |
| char AArch64BranchRelaxation::ID = 0; |
| } |
| |
| /// 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); |
| } |
| } |
| |
| /// BBHasFallthrough - Return true if the specified basic block can fallthrough |
| /// into the block immediately after it. |
| static bool BBHasFallthrough(MachineBasicBlock *MBB) { |
| // Get the next machine basic block in the function. |
| MachineFunction::iterator MBBI = MBB; |
| // Can't fall off end of function. |
| MachineBasicBlock *NextBB = std::next(MBBI); |
| if (NextBB == MBB->getParent()->end()) |
| return false; |
| |
| for (MachineBasicBlock *S : MBB->successors()) |
| if (S == NextBB) |
| return true; |
| |
| return false; |
| } |
| |
| /// 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(MachineInstr *MI) 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::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()); |
| MachineFunction::iterator MBBI = OrigBB; |
| ++MBBI; |
| MF->insert(MBBI, NewBB); |
| |
| // Splice the instructions starting with MI over to NewBB. |
| NewBB->splice(NewBB->end(), OrigBB, MI, 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. |
| BuildMI(OrigBB, DebugLoc(), TII->get(AArch64::B)).addMBB(NewBB); |
| |
| // 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(MachineInstr *MI, |
| MachineBasicBlock *DestBB, |
| unsigned Bits) { |
| unsigned MaxOffs = ((1 << (Bits - 1)) - 1) << 2; |
| unsigned BrOffset = getInstrOffset(MI); |
| unsigned DestOffset = BlockInfo[DestBB->getNumber()].Offset; |
| |
| DEBUG(dbgs() << "Branch of destination BB#" << DestBB->getNumber() |
| << " from BB#" << MI->getParent()->getNumber() |
| << " max delta=" << MaxOffs << " from " << getInstrOffset(MI) |
| << " to " << DestOffset << " offset " |
| << int(DestOffset - BrOffset) << "\t" << *MI); |
| |
| // Branch before the Dest. |
| if (BrOffset <= DestOffset) |
| return (DestOffset - BrOffset <= MaxOffs); |
| return (BrOffset - DestOffset <= MaxOffs); |
| } |
| |
| static bool isConditionalBranch(unsigned Opc) { |
| switch (Opc) { |
| default: |
| return false; |
| case AArch64::TBZW: |
| case AArch64::TBNZW: |
| case AArch64::TBZX: |
| case AArch64::TBNZX: |
| case AArch64::CBZW: |
| case AArch64::CBNZW: |
| case AArch64::CBZX: |
| case AArch64::CBNZX: |
| case AArch64::Bcc: |
| return true; |
| } |
| } |
| |
| static MachineBasicBlock *getDestBlock(MachineInstr *MI) { |
| switch (MI->getOpcode()) { |
| default: |
| llvm_unreachable("unexpected opcode!"); |
| case AArch64::TBZW: |
| case AArch64::TBNZW: |
| case AArch64::TBZX: |
| case AArch64::TBNZX: |
| return MI->getOperand(2).getMBB(); |
| case AArch64::CBZW: |
| case AArch64::CBNZW: |
| case AArch64::CBZX: |
| case AArch64::CBNZX: |
| case AArch64::Bcc: |
| return MI->getOperand(1).getMBB(); |
| } |
| } |
| |
| static unsigned getOppositeConditionOpcode(unsigned Opc) { |
| switch (Opc) { |
| default: |
| llvm_unreachable("unexpected opcode!"); |
| case AArch64::TBNZW: return AArch64::TBZW; |
| case AArch64::TBNZX: return AArch64::TBZX; |
| case AArch64::TBZW: return AArch64::TBNZW; |
| case AArch64::TBZX: return AArch64::TBNZX; |
| case AArch64::CBNZW: return AArch64::CBZW; |
| case AArch64::CBNZX: return AArch64::CBZX; |
| case AArch64::CBZW: return AArch64::CBNZW; |
| case AArch64::CBZX: return AArch64::CBNZX; |
| case AArch64::Bcc: return AArch64::Bcc; // Condition is an operand for Bcc. |
| } |
| } |
| |
| static unsigned getBranchDisplacementBits(unsigned Opc) { |
| switch (Opc) { |
| default: |
| llvm_unreachable("unexpected opcode!"); |
| case AArch64::TBNZW: |
| case AArch64::TBZW: |
| case AArch64::TBNZX: |
| case AArch64::TBZX: |
| return TBZDisplacementBits; |
| case AArch64::CBNZW: |
| case AArch64::CBZW: |
| case AArch64::CBNZX: |
| case AArch64::CBZX: |
| return CBZDisplacementBits; |
| case AArch64::Bcc: |
| return BCCDisplacementBits; |
| } |
| } |
| |
| static inline void invertBccCondition(MachineInstr *MI) { |
| assert(MI->getOpcode() == AArch64::Bcc && "Unexpected opcode!"); |
| AArch64CC::CondCode CC = (AArch64CC::CondCode)MI->getOperand(0).getImm(); |
| CC = AArch64CC::getInvertedCondCode(CC); |
| MI->getOperand(0).setImm((int64_t)CC); |
| } |
| |
| /// 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) { |
| MachineBasicBlock *DestBB = getDestBlock(MI); |
| |
| // Add an unconditional branch to the destination and invert the branch |
| // condition to jump over it: |
| // tbz L1 |
| // => |
| // tbnz L2 |
| // b L1 |
| // L2: |
| |
| // If the branch is at the end of its MBB and that has a fall-through block, |
| // direct the updated conditional branch to the fall-through block. Otherwise, |
| // split the MBB before the next instruction. |
| MachineBasicBlock *MBB = MI->getParent(); |
| MachineInstr *BMI = &MBB->back(); |
| bool NeedSplit = (BMI != MI) || !BBHasFallthrough(MBB); |
| |
| if (BMI != MI) { |
| if (std::next(MachineBasicBlock::iterator(MI)) == |
| std::prev(MBB->getLastNonDebugInstr()) && |
| BMI->getOpcode() == AArch64::B) { |
| // Last MI in the BB is an unconditional branch. Can we simply invert the |
| // condition and swap destinations: |
| // beq L1 |
| // b L2 |
| // => |
| // bne L2 |
| // b L1 |
| MachineBasicBlock *NewDest = BMI->getOperand(0).getMBB(); |
| if (isBlockInRange(MI, NewDest, |
| getBranchDisplacementBits(MI->getOpcode()))) { |
| DEBUG(dbgs() << " Invert condition and swap its destination with " |
| << *BMI); |
| BMI->getOperand(0).setMBB(DestBB); |
| unsigned OpNum = (MI->getOpcode() == AArch64::TBZW || |
| MI->getOpcode() == AArch64::TBNZW || |
| MI->getOpcode() == AArch64::TBZX || |
| MI->getOpcode() == AArch64::TBNZX) |
| ? 2 |
| : 1; |
| MI->getOperand(OpNum).setMBB(NewDest); |
| MI->setDesc(TII->get(getOppositeConditionOpcode(MI->getOpcode()))); |
| if (MI->getOpcode() == AArch64::Bcc) |
| invertBccCondition(MI); |
| return true; |
| } |
| } |
| } |
| |
| if (NeedSplit) { |
| // Analyze the branch so we know how to update the successor lists. |
| MachineBasicBlock *TBB, *FBB; |
| SmallVector<MachineOperand, 2> Cond; |
| TII->AnalyzeBranch(*MBB, TBB, FBB, Cond, false); |
| |
| MachineBasicBlock *NewBB = splitBlockBeforeInstr(MI); |
| // No need for the branch to the next block. We're adding an unconditional |
| // branch to the destination. |
| int delta = TII->GetInstSizeInBytes(&MBB->back()); |
| BlockInfo[MBB->getNumber()].Size -= delta; |
| MBB->back().eraseFromParent(); |
| // BlockInfo[SplitBB].Offset is wrong temporarily, fixed below |
| |
| // 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); |
| } |
| MachineBasicBlock *NextBB = std::next(MachineFunction::iterator(MBB)); |
| |
| DEBUG(dbgs() << " Insert B to BB#" << DestBB->getNumber() |
| << ", invert condition and change dest. to BB#" |
| << NextBB->getNumber() << "\n"); |
| |
| // Insert a new conditional branch and a new unconditional branch. |
| MachineInstrBuilder MIB = BuildMI( |
| MBB, DebugLoc(), TII->get(getOppositeConditionOpcode(MI->getOpcode()))) |
| .addOperand(MI->getOperand(0)); |
| if (MI->getOpcode() == AArch64::TBZW || MI->getOpcode() == AArch64::TBNZW || |
| MI->getOpcode() == AArch64::TBZX || MI->getOpcode() == AArch64::TBNZX) |
| MIB.addOperand(MI->getOperand(1)); |
| if (MI->getOpcode() == AArch64::Bcc) |
| invertBccCondition(MIB); |
| MIB.addMBB(NextBB); |
| BlockInfo[MBB->getNumber()].Size += TII->GetInstSizeInBytes(&MBB->back()); |
| BuildMI(MBB, DebugLoc(), TII->get(AArch64::B)).addMBB(DestBB); |
| BlockInfo[MBB->getNumber()].Size += TII->GetInstSizeInBytes(&MBB->back()); |
| |
| // Remove the old conditional branch. It may or may not still be in MBB. |
| BlockInfo[MI->getParent()->getNumber()].Size -= TII->GetInstSizeInBytes(MI); |
| MI->eraseFromParent(); |
| |
| // 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 (auto &MBB : *MF) { |
| MachineInstr *MI = MBB.getFirstTerminator(); |
| if (isConditionalBranch(MI->getOpcode()) && |
| !isBlockInRange(MI, getDestBlock(MI), |
| getBranchDisplacementBits(MI->getOpcode()))) { |
| fixupConditionalBranch(MI); |
| ++NumRelaxed; |
| Changed = true; |
| } |
| } |
| return Changed; |
| } |
| |
| bool AArch64BranchRelaxation::runOnMachineFunction(MachineFunction &mf) { |
| MF = &mf; |
| |
| // If the pass is disabled, just bail early. |
| if (!BranchRelaxation) |
| return false; |
| |
| DEBUG(dbgs() << "***** AArch64BranchRelaxation *****\n"); |
| |
| TII = (const AArch64InstrInfo *)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"); |
| DEBUG(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"); |
| DEBUG(dbgs() << '\n'; dumpBBs()); |
| |
| BlockInfo.clear(); |
| |
| return MadeChange; |
| } |
| |
| /// createAArch64BranchRelaxation - returns an instance of the constpool |
| /// island pass. |
| FunctionPass *llvm::createAArch64BranchRelaxation() { |
| return new AArch64BranchRelaxation(); |
| } |