ARM64BranchRelaxation.cpp [plain text]
#define DEBUG_TYPE "arm64-branch-relax"
#include "ARM64.h"
#include "ARM64InstrInfo.h"
#include "ARM64MachineFunctionInfo.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/Format.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/CommandLine.h"
using namespace llvm;
static cl::opt<bool>
BranchRelaxation("arm64-branch-relax", cl::Hidden, cl::init(true),
cl::desc("Relax out of range conditional branches"));
static cl::opt<unsigned>
TBZDisplacementBits("arm64-tbz-offset-bits", cl::Hidden, cl::init(14),
cl::desc("Restrict range of TB[N]Z instructions (DEBUG)"));
static cl::opt<unsigned>
CBZDisplacementBits("arm64-cbz-offset-bits", cl::Hidden, cl::init(19),
cl::desc("Restrict range of CB[N]Z instructions (DEBUG)"));
static cl::opt<unsigned>
BCCDisplacementBits("arm64-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 ARM64BranchRelaxation : public MachineFunctionPass {
struct BasicBlockInfo {
unsigned Offset;
unsigned Size;
BasicBlockInfo() : Offset(0), Size(0) {}
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 ARM64InstrInfo *TII;
bool relaxBranchInstructions();
void scanFunction();
MachineBasicBlock *splitBlockBeforeInstr(MachineInstr *MI);
void adjustBlockOffsets(MachineBasicBlock *BB);
bool isBlockInRange(MachineInstr *MI, MachineBasicBlock *BB, unsigned Disp);
bool fixupConditionalBranch(MachineInstr *MI);
void computeBlockSize(MachineBasicBlock *MBB);
unsigned getInstrOffset(MachineInstr *MI) const;
void dumpBBs();
void verify();
public:
static char ID;
ARM64BranchRelaxation() : MachineFunctionPass(ID) {}
virtual bool runOnMachineFunction(MachineFunction &MF);
virtual const char *getPassName() const {
return "ARM64 branch relaxation pass";
}
};
char ARM64BranchRelaxation::ID = 0;
}
void ARM64BranchRelaxation::verify() {
#ifndef NDEBUG
unsigned PrevNum = MF->begin()->getNumber();
for (MachineFunction::iterator MBBI = MF->begin(), E = MF->end();
MBBI != E; ++MBBI) {
MachineBasicBlock *MBB = MBBI;
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
}
void ARM64BranchRelaxation::dumpBBs() {
for (MachineFunction::iterator MBBI = MF->begin(), E = MF->end();
MBBI != E; ++MBBI) {
const BasicBlockInfo &BBI = BlockInfo[MBBI->getNumber()];
dbgs() << format("BB#%u\toffset=%08x\t", MBBI->getNumber(), BBI.Offset)
<< format("size=%#x\n", BBI.Size);
}
}
static bool BBHasFallthrough(MachineBasicBlock *MBB) {
MachineFunction::iterator MBBI = MBB;
if (llvm::next(MBBI) == MBB->getParent()->end())
return false;
MachineBasicBlock *NextBB = llvm::next(MBBI);
for (MachineBasicBlock::succ_iterator I = MBB->succ_begin(),
E = MBB->succ_end(); I != E; ++I)
if (*I == NextBB)
return true;
return false;
}
void ARM64BranchRelaxation::scanFunction() {
BlockInfo.clear();
BlockInfo.resize(MF->getNumBlockIDs());
for (MachineFunction::iterator I = MF->begin(), E = MF->end(); I != E; ++I)
computeBlockSize(I);
adjustBlockOffsets(MF->begin());
}
void ARM64BranchRelaxation::computeBlockSize(MachineBasicBlock *MBB) {
unsigned Size = 0;
for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E;
++I)
Size += TII->GetInstSizeInBytes(I);
BlockInfo[MBB->getNumber()].Size = Size;
}
unsigned ARM64BranchRelaxation::getInstrOffset(MachineInstr *MI) const {
MachineBasicBlock *MBB = MI->getParent();
unsigned Offset = BlockInfo[MBB->getNumber()].Offset;
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 ARM64BranchRelaxation::adjustBlockOffsets(MachineBasicBlock *Start) {
unsigned PrevNum = Start->getNumber();
MachineFunction::iterator MBBI = Start, E = MF->end();
for (++MBBI; MBBI != E; ++MBBI) {
MachineBasicBlock *MBB = MBBI;
unsigned Num = MBB->getNumber();
if (!Num) continue;
unsigned LogAlign = MBBI->getAlignment();
BlockInfo[Num].Offset = BlockInfo[PrevNum].postOffset(LogAlign);
PrevNum = Num;
}
}
MachineBasicBlock *
ARM64BranchRelaxation::splitBlockBeforeInstr(MachineInstr *MI) {
MachineBasicBlock *OrigBB = MI->getParent();
MachineBasicBlock *NewBB =
MF->CreateMachineBasicBlock(OrigBB->getBasicBlock());
MachineFunction::iterator MBBI = OrigBB; ++MBBI;
MF->insert(MBBI, NewBB);
NewBB->splice(NewBB->end(), OrigBB, MI, OrigBB->end());
BuildMI(OrigBB, DebugLoc(), TII->get(ARM64::B)).addMBB(NewBB);
BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
computeBlockSize(OrigBB);
computeBlockSize(NewBB);
adjustBlockOffsets(OrigBB);
++NumSplit;
return NewBB;
}
bool ARM64BranchRelaxation::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);
if (BrOffset <= DestOffset)
return (DestOffset-BrOffset <= MaxOffs);
return (BrOffset-DestOffset <= MaxOffs);
}
static bool isConditionalBranch(unsigned Opc) {
switch(Opc) {
default: return false;
case ARM64::TBZ: case ARM64::TBNZ:
case ARM64::CBZW: case ARM64::CBNZW:
case ARM64::CBZX: case ARM64::CBNZX:
case ARM64::Bcc:
return true;
}
}
static MachineBasicBlock *getDestBlock(MachineInstr *MI) {
switch(MI->getOpcode()) {
default: assert(0 && "unexpected opcode!");
case ARM64::TBZ: case ARM64::TBNZ:
return MI->getOperand(2).getMBB();
case ARM64::CBZW: case ARM64::CBNZW:
case ARM64::CBZX: case ARM64::CBNZX:
case ARM64::Bcc:
return MI->getOperand(1).getMBB();
}
}
static unsigned getOppositeConditionOpcode(unsigned Opc) {
switch(Opc) {
default: assert(0 && "unexpected opcode!");
case ARM64::TBNZ: return ARM64::TBZ;
case ARM64::TBZ: return ARM64::TBNZ;
case ARM64::CBNZW: return ARM64::CBZW;
case ARM64::CBNZX: return ARM64::CBZX;
case ARM64::CBZW: return ARM64::CBNZW;
case ARM64::CBZX: return ARM64::CBNZX;
case ARM64::Bcc: return ARM64::Bcc; }
}
static unsigned getBranchDisplacementBits(unsigned Opc) {
switch(Opc) {
default: assert(0 && "unexpected opcode!");
case ARM64::TBNZ: case ARM64::TBZ:
return TBZDisplacementBits;
case ARM64::CBNZW: case ARM64::CBZW:
case ARM64::CBNZX: case ARM64::CBZX:
return CBZDisplacementBits;
case ARM64::Bcc:
return BCCDisplacementBits;
}
}
static inline void invertBccCondition(MachineInstr *MI) {
assert(MI->getOpcode() == ARM64::Bcc && "Unexpected opcode!");
ARM64CC::CondCode CC = (ARM64CC::CondCode)MI->getOperand(0).getImm();
CC = ARM64CC::getInvertedCondCode(CC);
MI->getOperand(0).setImm((int64_t)CC);
}
bool ARM64BranchRelaxation::fixupConditionalBranch(MachineInstr *MI) {
MachineBasicBlock *DestBB = getDestBlock(MI);
MachineBasicBlock *MBB = MI->getParent();
MachineInstr *BMI = &MBB->back();
bool NeedSplit = (BMI != MI) || !BBHasFallthrough(MBB);
if (BMI != MI) {
if (llvm::next(MachineBasicBlock::iterator(MI)) ==
prior(MBB->getLastNonDebugInstr()) && BMI->getOpcode() == ARM64::B) {
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() == ARM64::TBZ || MI->getOpcode() == ARM64::TBNZ) ?
2 : 1;
MI->getOperand(OpNum).setMBB(NewDest);
MI->setDesc(TII->get(getOppositeConditionOpcode(MI->getOpcode())));
if (MI->getOpcode() == ARM64::Bcc)
invertBccCondition(MI);
return true;
}
}
}
if (NeedSplit) {
MachineBasicBlock *TBB, *FBB;
SmallVector<MachineOperand,2> Cond;
TII->AnalyzeBranch(*MBB, TBB, FBB, Cond, false);
MachineBasicBlock *NewBB = splitBlockBeforeInstr(MI);
int delta = TII->GetInstSizeInBytes(&MBB->back());
BlockInfo[MBB->getNumber()].Size -= delta;
MBB->back().eraseFromParent();
MBB->replaceSuccessor(FBB, NewBB);
NewBB->addSuccessor(FBB);
}
MachineBasicBlock *NextBB = llvm::next(MachineFunction::iterator(MBB));
DEBUG(dbgs() << " Insert B to BB#" << DestBB->getNumber()
<< ", invert condition and change dest. to BB#"
<< NextBB->getNumber() << "\n");
MachineInstrBuilder MIB =
BuildMI(MBB, DebugLoc(),
TII->get(getOppositeConditionOpcode(MI->getOpcode())))
.addOperand(MI->getOperand(0));
if (MI->getOpcode() == ARM64::TBZ || MI->getOpcode() == ARM64::TBNZ)
MIB.addOperand(MI->getOperand(1));
if (MI->getOpcode() == ARM64::Bcc)
invertBccCondition(MIB);
MIB.addMBB(NextBB);
BlockInfo[MBB->getNumber()].Size += TII->GetInstSizeInBytes(&MBB->back());
BuildMI(MBB, DebugLoc(), TII->get(ARM64::B)).addMBB(DestBB);
BlockInfo[MBB->getNumber()].Size += TII->GetInstSizeInBytes(&MBB->back());
BlockInfo[MI->getParent()->getNumber()].Size -= TII->GetInstSizeInBytes(MI);
MI->eraseFromParent();
adjustBlockOffsets(MBB);
return true;
}
bool ARM64BranchRelaxation::relaxBranchInstructions() {
bool Changed = false;
for (MachineFunction::iterator I = MF->begin(); I != MF->end(); ++I) {
MachineInstr *MI = I->getFirstTerminator();
if (isConditionalBranch(MI->getOpcode()) &&
!isBlockInRange(MI, getDestBlock(MI),
getBranchDisplacementBits(MI->getOpcode()))) {
fixupConditionalBranch(MI);
++NumRelaxed;
Changed = true;
}
}
return Changed;
}
bool ARM64BranchRelaxation::runOnMachineFunction(MachineFunction &mf) {
MF = &mf;
if (!BranchRelaxation)
return false;
DEBUG(dbgs() << "***** ARM64BranchRelaxation *****\n");
TII = (const ARM64InstrInfo*)MF->getTarget().getInstrInfo();
MF->RenumberBlocks();
scanFunction();
DEBUG(dbgs() << " Basic blocks before relaxation\n");
DEBUG(dumpBBs());
bool MadeChange = false;
while (relaxBranchInstructions())
MadeChange = true;
verify();
DEBUG(dbgs() << " Basic blocks after relaxation\n");
DEBUG(dbgs() << '\n'; dumpBBs());
BlockInfo.clear();
return MadeChange;
}
FunctionPass *llvm::createARM64BranchRelaxation() {
return new ARM64BranchRelaxation();
}