20#include "llvm/Config/llvm-config.h"
36#define DEBUG_TYPE "branch-relaxation"
39STATISTIC(NumConditionalRelaxed,
"Number of conditional branches relaxed");
40STATISTIC(NumUnconditionalRelaxed,
"Number of unconditional branches relaxed");
42#define BRANCH_RELAX_NAME "Branch relaxation pass"
68 const unsigned PO = Offset + Size;
71 if (Alignment <= ParentAlign)
81 std::unique_ptr<RegScavenger> RS;
88 bool relaxBranchInstructions();
119char BranchRelaxation::ID = 0;
126void BranchRelaxation::
verify() {
128 unsigned PrevNum = MF->begin()->getNumber();
131 assert(!Num || BlockInfo[PrevNum].postOffset(
MBB) <= BlockInfo[Num].
Offset);
138 J !=
MBB.
end(); J = std::next(J)) {
140 if (!
MI.isConditionalBranch() && !
MI.isUnconditionalBranch())
142 if (
MI.getOpcode() == TargetOpcode::FAULTING_OP)
145 assert(isBlockInRange(
MI, *DestBB));
151#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
154 for (
auto &
MBB : *MF) {
164void BranchRelaxation::scanFunction() {
166 BlockInfo.resize(MF->getNumBlockIDs());
176 adjustBlockOffsets(*MF->begin());
190unsigned BranchRelaxation::getInstrOffset(
const MachineInstr &
MI)
const {
200 assert(
I !=
MBB->
end() &&
"Didn't find MI in its own basic block?");
208 unsigned PrevNum = Start.getNumber();
214 BlockInfo[Num].Offset = BlockInfo[PrevNum].postOffset(
MBB);
254 NewBB->
splice(NewBB->
end(), OrigBB,
MI.getIterator(), OrigBB->
end());
260 TII->insertUnconditionalBranch(*OrigBB, NewBB,
DebugLoc());
278 BlockInfo[OrigBB->
getNumber()].Size = computeBlockSize(*OrigBB);
282 BlockInfo[NewBB->
getNumber()].Size = computeBlockSize(*NewBB);
285 adjustBlockOffsets(*OrigBB);
288 if (
TRI->trackLivenessAfterRegAlloc(*MF))
298bool BranchRelaxation::isBlockInRange(
300 int64_t BrOffset = getInstrOffset(
MI);
301 int64_t DestOffset = BlockInfo[DestBB.
getNumber()].Offset;
303 if (
TII->isBranchOffsetInRange(
MI.getOpcode(), DestOffset - BrOffset))
309 << DestOffset <<
" offset " << DestOffset - BrOffset <<
'\t'
329 TII->insertUnconditionalBranch(*
MBB, DestBB,
DL, &NewBrSize);
344 BBSize -= RemovedSize;
350 adjustBlockOffsets(*
MBB);
353 if (NewBB &&
TRI->trackLivenessAfterRegAlloc(*MF))
358 assert(!
Fail &&
"branches to be relaxed must be analyzable");
371 if (FBB && isBlockInRange(
MI, *FBB)) {
380 "its destination with "
385 finalizeBlockChanges(
MBB,
nullptr);
391 NewBB = createNewBlockAfter(*
MBB);
393 insertUncondBranch(NewBB, FBB);
405 <<
", invert condition and change dest. to "
412 finalizeBlockChanges(
MBB, NewBB);
418 <<
" Insert a new BB after " <<
MBB->
back());
434 NewBB = createNewBlockAfter(*
MBB);
435 insertUncondBranch(NewBB,
TBB);
439 <<
" Keep the exiting condition.\n"
441 <<
" In the new BB: Insert B to "
450 insertBranch(
MBB, NewBB, FBB,
Cond);
452 finalizeBlockChanges(
MBB, NewBB);
456bool BranchRelaxation::fixupUnconditionalBranch(
MachineInstr &
MI) {
459 unsigned OldBrSize =
TII->getInstSizeInBytes(
MI);
462 int64_t DestOffset = BlockInfo[DestBB->
getNumber()].Offset;
463 int64_t SrcOffset = getInstrOffset(
MI);
465 assert(!
TII->isBranchOffsetInRange(
MI.getOpcode(), DestOffset - SrcOffset));
474 BranchBB = createNewBlockAfter(*
MBB);
488 MI.eraseFromParent();
496 TII->insertIndirectBranch(*BranchBB, *DestBB, *RestoreBB,
DL,
497 DestOffset - SrcOffset, RS.get());
499 BlockInfo[BranchBB->
getNumber()].Size = computeBlockSize(*BranchBB);
500 adjustBlockOffsets(*
MBB);
503 if (!RestoreBB->
empty()) {
514 TII->insertUnconditionalBranch(*PrevBB, FT,
DebugLoc());
515 BlockInfo[PrevBB->
getNumber()].Size = computeBlockSize(*PrevBB);
522 if (
TRI->trackLivenessAfterRegAlloc(*MF))
525 BlockInfo[RestoreBB->
getNumber()].Size = computeBlockSize(*RestoreBB);
527 adjustBlockOffsets(*PrevBB);
530 MF->erase(RestoreBB);
536bool BranchRelaxation::relaxBranchInstructions() {
537 bool Changed =
false;
552 if (
Last->isUnconditionalBranch()) {
556 if (!isBlockInRange(*
Last, *DestBB)) {
557 fixupUnconditionalBranch(*
Last);
558 ++NumUnconditionalRelaxed;
567 J !=
MBB.
end(); J = Next) {
571 if (!
MI.isConditionalBranch())
574 if (
MI.getOpcode() == TargetOpcode::FAULTING_OP)
580 if (!isBlockInRange(
MI, *DestBB)) {
581 if (Next !=
MBB.
end() && Next->isConditionalBranch()) {
586 splitBlockBeforeInstr(*Next, DestBB);
588 fixupConditionalBranch(
MI);
589 ++NumConditionalRelaxed;
609 TII =
ST.getInstrInfo();
611 TRI =
ST.getRegisterInfo();
612 if (
TRI->trackLivenessAfterRegAlloc(*MF))
617 MF->RenumberBlocks();
623 LLVM_DEBUG(
dbgs() <<
" Basic blocks before relaxation\n"; dumpBBs(););
625 bool MadeChange =
false;
626 while (relaxBranchInstructions())
632 LLVM_DEBUG(
dbgs() <<
" Basic blocks after relaxation\n\n"; dumpBBs());
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
SmallVector< MachineOperand, 4 > Cond
#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
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB
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.
A set of physical registers with utility functions to track liveness when walking backward/forward th...
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.
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.
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.
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 '...
Align getAlignment() const
Return alignment of the basic block.
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.
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.
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.
Pair of physical register and lane mask.