20#include "llvm/Config/llvm-config.h"
37#define DEBUG_TYPE "branch-relaxation"
40STATISTIC(NumConditionalRelaxed,
"Number of conditional branches relaxed");
41STATISTIC(NumUnconditionalRelaxed,
"Number of unconditional branches relaxed");
43#define BRANCH_RELAX_NAME "Branch relaxation pass"
69 const unsigned PO = Offset + Size;
72 if (Alignment <= ParentAlign)
87 RelaxedUnconditionals;
88 std::unique_ptr<RegScavenger> RS;
96 bool relaxBranchInstructions();
127char BranchRelaxation::ID = 0;
134void BranchRelaxation::
verify() {
136 unsigned PrevNum = MF->begin()->getNumber();
139 assert(!Num || BlockInfo[PrevNum].postOffset(
MBB) <= BlockInfo[Num].
Offset);
146 J !=
MBB.
end(); J = std::next(J)) {
148 if (!
MI.isConditionalBranch() && !
MI.isUnconditionalBranch())
150 if (
MI.getOpcode() == TargetOpcode::FAULTING_OP)
153 assert(isBlockInRange(
MI, *DestBB) ||
154 RelaxedUnconditionals.contains({&MBB, DestBB}));
160#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
163 for (
auto &
MBB : *MF) {
173void BranchRelaxation::scanFunction() {
175 BlockInfo.resize(MF->getNumBlockIDs());
177 TrampolineInsertionPoint =
nullptr;
178 RelaxedUnconditionals.clear();
189 TrampolineInsertionPoint = &
MBB;
193 adjustBlockOffsets(*MF->begin());
195 if (TrampolineInsertionPoint ==
nullptr) {
196 LLVM_DEBUG(
dbgs() <<
" No suitable trampoline insertion point found in "
197 << MF->getName() <<
".\n");
212unsigned BranchRelaxation::getInstrOffset(
const MachineInstr &
MI)
const {
222 assert(
I !=
MBB->
end() &&
"Didn't find MI in its own basic block?");
230 unsigned PrevNum = Start.getNumber();
236 BlockInfo[Num].Offset = BlockInfo[PrevNum].postOffset(
MBB);
287 NewBB->
splice(NewBB->
end(), OrigBB,
MI.getIterator(), OrigBB->
end());
293 TII->insertUnconditionalBranch(*OrigBB, NewBB,
DebugLoc());
311 BlockInfo[OrigBB->
getNumber()].Size = computeBlockSize(*OrigBB);
315 BlockInfo[NewBB->
getNumber()].Size = computeBlockSize(*NewBB);
318 adjustBlockOffsets(*OrigBB);
321 if (
TRI->trackLivenessAfterRegAlloc(*MF))
331bool BranchRelaxation::isBlockInRange(
333 int64_t BrOffset = getInstrOffset(
MI);
334 int64_t DestOffset = BlockInfo[DestBB.
getNumber()].Offset;
338 if (
TII->isBranchOffsetInRange(
MI.getOpcode(),
340 ?
TM->getMaxCodeSize()
341 : DestOffset - BrOffset))
347 << DestOffset <<
" offset " << DestOffset - BrOffset <<
'\t'
367 TII->insertUnconditionalBranch(*
MBB, DestBB,
DL, &NewBrSize);
382 BBSize -= RemovedSize;
388 adjustBlockOffsets(*
MBB);
391 if (NewBB &&
TRI->trackLivenessAfterRegAlloc(*MF))
396 assert(!
Fail &&
"branches to be relaxed must be analyzable");
411 TrampolineInsertionPoint !=
nullptr) {
416 if (isBlockInRange(
MI, *NewBB)) {
420 insertUncondBranch(NewBB,
TBB);
428 insertBranch(
MBB, NewBB, FBB,
Cond);
430 TrampolineInsertionPoint = NewBB;
431 finalizeBlockChanges(
MBB, NewBB);
436 dbgs() <<
" Trampoline insertion point out of range for Bcc from "
439 TrampolineInsertionPoint->setIsEndSection(NewBB->
isEndSection());
453 if (FBB && isBlockInRange(
MI, *FBB)) {
462 "its destination with "
467 finalizeBlockChanges(
MBB,
nullptr);
473 NewBB = createNewBlockAfter(*
MBB);
475 insertUncondBranch(NewBB, FBB);
487 <<
", invert condition and change dest. to "
494 finalizeBlockChanges(
MBB, NewBB);
500 <<
" Insert a new BB after " <<
MBB->
back());
516 NewBB = createNewBlockAfter(*
MBB);
517 insertUncondBranch(NewBB,
TBB);
521 <<
" Keep the exiting condition.\n"
523 <<
" In the new BB: Insert B to "
532 insertBranch(
MBB, NewBB, FBB,
Cond);
534 finalizeBlockChanges(
MBB, NewBB);
538bool BranchRelaxation::fixupUnconditionalBranch(
MachineInstr &
MI) {
541 unsigned OldBrSize =
TII->getInstSizeInBytes(
MI);
544 int64_t DestOffset = BlockInfo[DestBB->
getNumber()].Offset;
545 int64_t SrcOffset = getInstrOffset(
MI);
549 ?
TM->getMaxCodeSize()
550 : DestOffset - SrcOffset));
559 BranchBB = createNewBlockAfter(*
MBB);
570 if (TrampolineInsertionPoint ==
MBB)
571 TrampolineInsertionPoint = BranchBB;
575 MI.eraseFromParent();
586 TII->insertIndirectBranch(*BranchBB, *DestBB, *RestoreBB,
DL,
588 ?
TM->getMaxCodeSize()
589 : DestOffset - SrcOffset,
592 BlockInfo[BranchBB->
getNumber()].Size = computeBlockSize(*BranchBB);
593 adjustBlockOffsets(*
MBB);
596 if (!RestoreBB->
empty()) {
602 TII->insertUnconditionalBranch(*NewBB, DestBB,
DebugLoc());
603 BlockInfo[NewBB->
getNumber()].Size = computeBlockSize(*NewBB);
606 TrampolineInsertionPoint = NewBB;
627 TII->insertUnconditionalBranch(*PrevBB, FT,
DebugLoc());
628 BlockInfo[PrevBB->
getNumber()].Size = computeBlockSize(*PrevBB);
635 if (
TRI->trackLivenessAfterRegAlloc(*MF))
638 BlockInfo[RestoreBB->
getNumber()].Size = computeBlockSize(*RestoreBB);
640 adjustBlockOffsets(*PrevBB);
646 RelaxedUnconditionals.insert({BranchBB, RestoreBB});
649 MF->erase(RestoreBB);
650 RelaxedUnconditionals.insert({BranchBB, DestBB});
656bool BranchRelaxation::relaxBranchInstructions() {
657 bool Changed =
false;
672 if (
Last->isUnconditionalBranch()) {
677 !RelaxedUnconditionals.contains({&MBB, DestBB})) {
678 fixupUnconditionalBranch(*
Last);
679 ++NumUnconditionalRelaxed;
688 J !=
MBB.
end(); J = Next) {
692 if (!
MI.isConditionalBranch())
695 if (
MI.getOpcode() == TargetOpcode::FAULTING_OP)
701 if (!isBlockInRange(
MI, *DestBB)) {
702 if (Next !=
MBB.
end() && Next->isConditionalBranch()) {
707 splitBlockBeforeInstr(*Next, DestBB);
709 fixupConditionalBranch(
MI);
710 ++NumConditionalRelaxed;
730 TII =
ST.getInstrInfo();
731 TM = &MF->getTarget();
733 TRI =
ST.getRegisterInfo();
734 if (
TRI->trackLivenessAfterRegAlloc(*MF))
739 MF->RenumberBlocks();
745 LLVM_DEBUG(
dbgs() <<
" Basic blocks before relaxation\n"; dumpBBs(););
747 bool MadeChange =
false;
748 while (relaxBranchInstructions())
754 LLVM_DEBUG(
dbgs() <<
" Basic blocks after relaxation\n\n"; dumpBBs());
757 RelaxedUnconditionals.clear();
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
#define BRANCH_RELAX_NAME
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
const HexagonInstrInfo * TII
This file implements the LivePhysRegs utility for tracking liveness of physical registers.
unsigned const TargetRegisterInfo * TRI
const char LLVMTargetMachineRef TM
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB
const SmallVectorImpl< MachineOperand > & Cond
This file declares the machine register scavenger class.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
LLVM Basic Block Representation.
unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const override
Remove the branching code at the end of the specific MBB.
bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify) const override
Analyze the branching code at the end of MBB, returning true if it cannot be understood (e....
bool reverseBranchCondition(SmallVectorImpl< MachineOperand > &Cond) const override
Reverses the branch condition of the specified condition list, returning false on success and true if...
unsigned insertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB, MachineBasicBlock *FBB, ArrayRef< MachineOperand > Cond, const DebugLoc &DL, int *BytesAdded=nullptr) const override
Insert branch code into the end of the specified MachineBasicBlock.
bool isTailCall(const MachineInstr &MI) const override
A set of physical registers with utility functions to track liveness when walking backward/forward th...
void setIsEndSection(bool V=true)
MachineBasicBlock * getLogicalFallThrough()
Return the fallthrough block if the block can implicitly transfer control to it's successor,...
void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New)
Replace successor OLD with NEW and update probability info.
void transferSuccessors(MachineBasicBlock *FromMBB)
Transfers all the successors from MBB to this machine basic block (i.e., copies all the successors Fr...
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
void updateTerminator(MachineBasicBlock *PreviousLayoutSuccessor)
Update the terminator instructions in block to account for changes to block layout which may have bee...
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
MBBSectionID getSectionID() const
Returns the section ID of this basic block.
bool isEntryBlock() const
Returns true if this is the entry block of the function.
void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
void sortUniqueLiveIns()
Sorts and uniques the LiveIns vector.
void setSectionID(MBBSectionID V)
Sets the section ID for this basic block.
iterator getLastNonDebugInstr(bool SkipPseudoOp=true)
Returns an iterator to the last non-debug instruction in the basic block, or end().
void addLiveIn(MCRegister PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
bool isBeginSection() const
Returns true if this block begins any section.
iterator_range< succ_iterator > successors()
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...
bool isEndSection() const
Returns true if this block ends any section.
Align getAlignment() const
Return alignment of the basic block.
void setIsBeginSection(bool V=true)
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
Align getAlignment() const
getAlignment - Return the alignment of the function.
Representation of each machine instruction.
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Implements a dense probed hash-table based set with some number of buckets stored inline.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
TargetInstrInfo - Interface to description of machine instruction set.
Primary interface to the complete machine description for the target machine.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
TargetSubtargetInfo - Generic base class for all target subtargets.
self_iterator getIterator()
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
This is an optimization pass for GlobalISel generic memory operations.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
char & BranchRelaxationPassID
BranchRelaxation - This pass replaces branches that need to jump further than is supported by a branc...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
void computeAndAddLiveIns(LivePhysRegs &LiveRegs, MachineBasicBlock &MBB)
Convenience function combining computeLiveIns() and addLiveIns().
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
This struct is a compact representation of a valid (non-zero power of two) alignment.
uint64_t value() const
This is a hole in the type system and should not be abused.
BasicBlockInfo - Information about the offset and size of a single basic block.
unsigned Size
Size - Size of the basic block in bytes.
unsigned Offset
Offset - Distance from the beginning of the function to the beginning of this basic block.
static const MBBSectionID ColdSectionID
Pair of physical register and lane mask.