You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
464 lines
16 KiB
464 lines
16 KiB
//===-- SystemZLongBranch.cpp - Branch lengthening for SystemZ ------------===//
|
|
//
|
|
// The LLVM Compiler Infrastructure
|
|
//
|
|
// This file is distributed under the University of Illinois Open Source
|
|
// License. See LICENSE.TXT for details.
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
//
|
|
// This pass makes sure that all branches are in range. There are several ways
|
|
// in which this could be done. One aggressive approach is to assume that all
|
|
// branches are in range and successively replace those that turn out not
|
|
// to be in range with a longer form (branch relaxation). A simple
|
|
// implementation is to continually walk through the function relaxing
|
|
// branches until no more changes are needed and a fixed point is reached.
|
|
// However, in the pathological worst case, this implementation is
|
|
// quadratic in the number of blocks; relaxing branch N can make branch N-1
|
|
// go out of range, which in turn can make branch N-2 go out of range,
|
|
// and so on.
|
|
//
|
|
// An alternative approach is to assume that all branches must be
|
|
// converted to their long forms, then reinstate the short forms of
|
|
// branches that, even under this pessimistic assumption, turn out to be
|
|
// in range (branch shortening). This too can be implemented as a function
|
|
// walk that is repeated until a fixed point is reached. In general,
|
|
// the result of shortening is not as good as that of relaxation, and
|
|
// shortening is also quadratic in the worst case; shortening branch N
|
|
// can bring branch N-1 in range of the short form, which in turn can do
|
|
// the same for branch N-2, and so on. The main advantage of shortening
|
|
// is that each walk through the function produces valid code, so it is
|
|
// possible to stop at any point after the first walk. The quadraticness
|
|
// could therefore be handled with a maximum pass count, although the
|
|
// question then becomes: what maximum count should be used?
|
|
//
|
|
// On SystemZ, long branches are only needed for functions bigger than 64k,
|
|
// which are relatively rare to begin with, and the long branch sequences
|
|
// are actually relatively cheap. It therefore doesn't seem worth spending
|
|
// much compilation time on the problem. Instead, the approach we take is:
|
|
//
|
|
// (1) Work out the address that each block would have if no branches
|
|
// need relaxing. Exit the pass early if all branches are in range
|
|
// according to this assumption.
|
|
//
|
|
// (2) Work out the address that each block would have if all branches
|
|
// need relaxing.
|
|
//
|
|
// (3) Walk through the block calculating the final address of each instruction
|
|
// and relaxing those that need to be relaxed. For backward branches,
|
|
// this check uses the final address of the target block, as calculated
|
|
// earlier in the walk. For forward branches, this check uses the
|
|
// address of the target block that was calculated in (2). Both checks
|
|
// give a conservatively-correct range.
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
#include "SystemZTargetMachine.h"
|
|
#include "llvm/ADT/Statistic.h"
|
|
#include "llvm/CodeGen/MachineFunctionPass.h"
|
|
#include "llvm/CodeGen/MachineInstrBuilder.h"
|
|
#include "llvm/IR/Function.h"
|
|
#include "llvm/Support/MathExtras.h"
|
|
#include "llvm/Target/TargetInstrInfo.h"
|
|
#include "llvm/Target/TargetMachine.h"
|
|
#include "llvm/Target/TargetRegisterInfo.h"
|
|
|
|
using namespace llvm;
|
|
|
|
#define DEBUG_TYPE "systemz-long-branch"
|
|
|
|
STATISTIC(LongBranches, "Number of long branches.");
|
|
|
|
namespace {
|
|
// Represents positional information about a basic block.
|
|
struct MBBInfo {
|
|
// The address that we currently assume the block has.
|
|
uint64_t Address;
|
|
|
|
// The size of the block in bytes, excluding terminators.
|
|
// This value never changes.
|
|
uint64_t Size;
|
|
|
|
// The minimum alignment of the block, as a log2 value.
|
|
// This value never changes.
|
|
unsigned Alignment;
|
|
|
|
// The number of terminators in this block. This value never changes.
|
|
unsigned NumTerminators;
|
|
|
|
MBBInfo()
|
|
: Address(0), Size(0), Alignment(0), NumTerminators(0) {}
|
|
};
|
|
|
|
// Represents the state of a block terminator.
|
|
struct TerminatorInfo {
|
|
// If this terminator is a relaxable branch, this points to the branch
|
|
// instruction, otherwise it is null.
|
|
MachineInstr *Branch;
|
|
|
|
// The address that we currently assume the terminator has.
|
|
uint64_t Address;
|
|
|
|
// The current size of the terminator in bytes.
|
|
uint64_t Size;
|
|
|
|
// If Branch is nonnull, this is the number of the target block,
|
|
// otherwise it is unused.
|
|
unsigned TargetBlock;
|
|
|
|
// If Branch is nonnull, this is the length of the longest relaxed form,
|
|
// otherwise it is zero.
|
|
unsigned ExtraRelaxSize;
|
|
|
|
TerminatorInfo() : Branch(nullptr), Size(0), TargetBlock(0),
|
|
ExtraRelaxSize(0) {}
|
|
};
|
|
|
|
// Used to keep track of the current position while iterating over the blocks.
|
|
struct BlockPosition {
|
|
// The address that we assume this position has.
|
|
uint64_t Address;
|
|
|
|
// The number of low bits in Address that are known to be the same
|
|
// as the runtime address.
|
|
unsigned KnownBits;
|
|
|
|
BlockPosition(unsigned InitialAlignment)
|
|
: Address(0), KnownBits(InitialAlignment) {}
|
|
};
|
|
|
|
class SystemZLongBranch : public MachineFunctionPass {
|
|
public:
|
|
static char ID;
|
|
SystemZLongBranch(const SystemZTargetMachine &tm)
|
|
: MachineFunctionPass(ID), TII(nullptr) {}
|
|
|
|
const char *getPassName() const override {
|
|
return "SystemZ Long Branch";
|
|
}
|
|
|
|
bool runOnMachineFunction(MachineFunction &F) override;
|
|
MachineFunctionProperties getRequiredProperties() const override {
|
|
return MachineFunctionProperties().set(
|
|
MachineFunctionProperties::Property::AllVRegsAllocated);
|
|
}
|
|
|
|
private:
|
|
void skipNonTerminators(BlockPosition &Position, MBBInfo &Block);
|
|
void skipTerminator(BlockPosition &Position, TerminatorInfo &Terminator,
|
|
bool AssumeRelaxed);
|
|
TerminatorInfo describeTerminator(MachineInstr &MI);
|
|
uint64_t initMBBInfo();
|
|
bool mustRelaxBranch(const TerminatorInfo &Terminator, uint64_t Address);
|
|
bool mustRelaxABranch();
|
|
void setWorstCaseAddresses();
|
|
void splitBranchOnCount(MachineInstr *MI, unsigned AddOpcode);
|
|
void splitCompareBranch(MachineInstr *MI, unsigned CompareOpcode);
|
|
void relaxBranch(TerminatorInfo &Terminator);
|
|
void relaxBranches();
|
|
|
|
const SystemZInstrInfo *TII;
|
|
MachineFunction *MF;
|
|
SmallVector<MBBInfo, 16> MBBs;
|
|
SmallVector<TerminatorInfo, 16> Terminators;
|
|
};
|
|
|
|
char SystemZLongBranch::ID = 0;
|
|
|
|
const uint64_t MaxBackwardRange = 0x10000;
|
|
const uint64_t MaxForwardRange = 0xfffe;
|
|
} // end anonymous namespace
|
|
|
|
FunctionPass *llvm::createSystemZLongBranchPass(SystemZTargetMachine &TM) {
|
|
return new SystemZLongBranch(TM);
|
|
}
|
|
|
|
// Position describes the state immediately before Block. Update Block
|
|
// accordingly and move Position to the end of the block's non-terminator
|
|
// instructions.
|
|
void SystemZLongBranch::skipNonTerminators(BlockPosition &Position,
|
|
MBBInfo &Block) {
|
|
if (Block.Alignment > Position.KnownBits) {
|
|
// When calculating the address of Block, we need to conservatively
|
|
// assume that Block had the worst possible misalignment.
|
|
Position.Address += ((uint64_t(1) << Block.Alignment) -
|
|
(uint64_t(1) << Position.KnownBits));
|
|
Position.KnownBits = Block.Alignment;
|
|
}
|
|
|
|
// Align the addresses.
|
|
uint64_t AlignMask = (uint64_t(1) << Block.Alignment) - 1;
|
|
Position.Address = (Position.Address + AlignMask) & ~AlignMask;
|
|
|
|
// Record the block's position.
|
|
Block.Address = Position.Address;
|
|
|
|
// Move past the non-terminators in the block.
|
|
Position.Address += Block.Size;
|
|
}
|
|
|
|
// Position describes the state immediately before Terminator.
|
|
// Update Terminator accordingly and move Position past it.
|
|
// Assume that Terminator will be relaxed if AssumeRelaxed.
|
|
void SystemZLongBranch::skipTerminator(BlockPosition &Position,
|
|
TerminatorInfo &Terminator,
|
|
bool AssumeRelaxed) {
|
|
Terminator.Address = Position.Address;
|
|
Position.Address += Terminator.Size;
|
|
if (AssumeRelaxed)
|
|
Position.Address += Terminator.ExtraRelaxSize;
|
|
}
|
|
|
|
// Return a description of terminator instruction MI.
|
|
TerminatorInfo SystemZLongBranch::describeTerminator(MachineInstr &MI) {
|
|
TerminatorInfo Terminator;
|
|
Terminator.Size = TII->getInstSizeInBytes(MI);
|
|
if (MI.isConditionalBranch() || MI.isUnconditionalBranch()) {
|
|
switch (MI.getOpcode()) {
|
|
case SystemZ::J:
|
|
// Relaxes to JG, which is 2 bytes longer.
|
|
Terminator.ExtraRelaxSize = 2;
|
|
break;
|
|
case SystemZ::BRC:
|
|
// Relaxes to BRCL, which is 2 bytes longer.
|
|
Terminator.ExtraRelaxSize = 2;
|
|
break;
|
|
case SystemZ::BRCT:
|
|
case SystemZ::BRCTG:
|
|
// Relaxes to A(G)HI and BRCL, which is 6 bytes longer.
|
|
Terminator.ExtraRelaxSize = 6;
|
|
break;
|
|
case SystemZ::CRJ:
|
|
case SystemZ::CLRJ:
|
|
// Relaxes to a C(L)R/BRCL sequence, which is 2 bytes longer.
|
|
Terminator.ExtraRelaxSize = 2;
|
|
break;
|
|
case SystemZ::CGRJ:
|
|
case SystemZ::CLGRJ:
|
|
// Relaxes to a C(L)GR/BRCL sequence, which is 4 bytes longer.
|
|
Terminator.ExtraRelaxSize = 4;
|
|
break;
|
|
case SystemZ::CIJ:
|
|
case SystemZ::CGIJ:
|
|
// Relaxes to a C(G)HI/BRCL sequence, which is 4 bytes longer.
|
|
Terminator.ExtraRelaxSize = 4;
|
|
break;
|
|
case SystemZ::CLIJ:
|
|
case SystemZ::CLGIJ:
|
|
// Relaxes to a CL(G)FI/BRCL sequence, which is 6 bytes longer.
|
|
Terminator.ExtraRelaxSize = 6;
|
|
break;
|
|
default:
|
|
llvm_unreachable("Unrecognized branch instruction");
|
|
}
|
|
Terminator.Branch = &MI;
|
|
Terminator.TargetBlock =
|
|
TII->getBranchInfo(MI).Target->getMBB()->getNumber();
|
|
}
|
|
return Terminator;
|
|
}
|
|
|
|
// Fill MBBs and Terminators, setting the addresses on the assumption
|
|
// that no branches need relaxation. Return the size of the function under
|
|
// this assumption.
|
|
uint64_t SystemZLongBranch::initMBBInfo() {
|
|
MF->RenumberBlocks();
|
|
unsigned NumBlocks = MF->size();
|
|
|
|
MBBs.clear();
|
|
MBBs.resize(NumBlocks);
|
|
|
|
Terminators.clear();
|
|
Terminators.reserve(NumBlocks);
|
|
|
|
BlockPosition Position(MF->getAlignment());
|
|
for (unsigned I = 0; I < NumBlocks; ++I) {
|
|
MachineBasicBlock *MBB = MF->getBlockNumbered(I);
|
|
MBBInfo &Block = MBBs[I];
|
|
|
|
// Record the alignment, for quick access.
|
|
Block.Alignment = MBB->getAlignment();
|
|
|
|
// Calculate the size of the fixed part of the block.
|
|
MachineBasicBlock::iterator MI = MBB->begin();
|
|
MachineBasicBlock::iterator End = MBB->end();
|
|
while (MI != End && !MI->isTerminator()) {
|
|
Block.Size += TII->getInstSizeInBytes(*MI);
|
|
++MI;
|
|
}
|
|
skipNonTerminators(Position, Block);
|
|
|
|
// Add the terminators.
|
|
while (MI != End) {
|
|
if (!MI->isDebugValue()) {
|
|
assert(MI->isTerminator() && "Terminator followed by non-terminator");
|
|
Terminators.push_back(describeTerminator(*MI));
|
|
skipTerminator(Position, Terminators.back(), false);
|
|
++Block.NumTerminators;
|
|
}
|
|
++MI;
|
|
}
|
|
}
|
|
|
|
return Position.Address;
|
|
}
|
|
|
|
// Return true if, under current assumptions, Terminator would need to be
|
|
// relaxed if it were placed at address Address.
|
|
bool SystemZLongBranch::mustRelaxBranch(const TerminatorInfo &Terminator,
|
|
uint64_t Address) {
|
|
if (!Terminator.Branch)
|
|
return false;
|
|
|
|
const MBBInfo &Target = MBBs[Terminator.TargetBlock];
|
|
if (Address >= Target.Address) {
|
|
if (Address - Target.Address <= MaxBackwardRange)
|
|
return false;
|
|
} else {
|
|
if (Target.Address - Address <= MaxForwardRange)
|
|
return false;
|
|
}
|
|
|
|
return true;
|
|
}
|
|
|
|
// Return true if, under current assumptions, any terminator needs
|
|
// to be relaxed.
|
|
bool SystemZLongBranch::mustRelaxABranch() {
|
|
for (auto &Terminator : Terminators)
|
|
if (mustRelaxBranch(Terminator, Terminator.Address))
|
|
return true;
|
|
return false;
|
|
}
|
|
|
|
// Set the address of each block on the assumption that all branches
|
|
// must be long.
|
|
void SystemZLongBranch::setWorstCaseAddresses() {
|
|
SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin();
|
|
BlockPosition Position(MF->getAlignment());
|
|
for (auto &Block : MBBs) {
|
|
skipNonTerminators(Position, Block);
|
|
for (unsigned BTI = 0, BTE = Block.NumTerminators; BTI != BTE; ++BTI) {
|
|
skipTerminator(Position, *TI, true);
|
|
++TI;
|
|
}
|
|
}
|
|
}
|
|
|
|
// Split BRANCH ON COUNT MI into the addition given by AddOpcode followed
|
|
// by a BRCL on the result.
|
|
void SystemZLongBranch::splitBranchOnCount(MachineInstr *MI,
|
|
unsigned AddOpcode) {
|
|
MachineBasicBlock *MBB = MI->getParent();
|
|
DebugLoc DL = MI->getDebugLoc();
|
|
BuildMI(*MBB, MI, DL, TII->get(AddOpcode))
|
|
.addOperand(MI->getOperand(0))
|
|
.addOperand(MI->getOperand(1))
|
|
.addImm(-1);
|
|
MachineInstr *BRCL = BuildMI(*MBB, MI, DL, TII->get(SystemZ::BRCL))
|
|
.addImm(SystemZ::CCMASK_ICMP)
|
|
.addImm(SystemZ::CCMASK_CMP_NE)
|
|
.addOperand(MI->getOperand(2));
|
|
// The implicit use of CC is a killing use.
|
|
BRCL->addRegisterKilled(SystemZ::CC, &TII->getRegisterInfo());
|
|
MI->eraseFromParent();
|
|
}
|
|
|
|
// Split MI into the comparison given by CompareOpcode followed
|
|
// a BRCL on the result.
|
|
void SystemZLongBranch::splitCompareBranch(MachineInstr *MI,
|
|
unsigned CompareOpcode) {
|
|
MachineBasicBlock *MBB = MI->getParent();
|
|
DebugLoc DL = MI->getDebugLoc();
|
|
BuildMI(*MBB, MI, DL, TII->get(CompareOpcode))
|
|
.addOperand(MI->getOperand(0))
|
|
.addOperand(MI->getOperand(1));
|
|
MachineInstr *BRCL = BuildMI(*MBB, MI, DL, TII->get(SystemZ::BRCL))
|
|
.addImm(SystemZ::CCMASK_ICMP)
|
|
.addOperand(MI->getOperand(2))
|
|
.addOperand(MI->getOperand(3));
|
|
// The implicit use of CC is a killing use.
|
|
BRCL->addRegisterKilled(SystemZ::CC, &TII->getRegisterInfo());
|
|
MI->eraseFromParent();
|
|
}
|
|
|
|
// Relax the branch described by Terminator.
|
|
void SystemZLongBranch::relaxBranch(TerminatorInfo &Terminator) {
|
|
MachineInstr *Branch = Terminator.Branch;
|
|
switch (Branch->getOpcode()) {
|
|
case SystemZ::J:
|
|
Branch->setDesc(TII->get(SystemZ::JG));
|
|
break;
|
|
case SystemZ::BRC:
|
|
Branch->setDesc(TII->get(SystemZ::BRCL));
|
|
break;
|
|
case SystemZ::BRCT:
|
|
splitBranchOnCount(Branch, SystemZ::AHI);
|
|
break;
|
|
case SystemZ::BRCTG:
|
|
splitBranchOnCount(Branch, SystemZ::AGHI);
|
|
break;
|
|
case SystemZ::CRJ:
|
|
splitCompareBranch(Branch, SystemZ::CR);
|
|
break;
|
|
case SystemZ::CGRJ:
|
|
splitCompareBranch(Branch, SystemZ::CGR);
|
|
break;
|
|
case SystemZ::CIJ:
|
|
splitCompareBranch(Branch, SystemZ::CHI);
|
|
break;
|
|
case SystemZ::CGIJ:
|
|
splitCompareBranch(Branch, SystemZ::CGHI);
|
|
break;
|
|
case SystemZ::CLRJ:
|
|
splitCompareBranch(Branch, SystemZ::CLR);
|
|
break;
|
|
case SystemZ::CLGRJ:
|
|
splitCompareBranch(Branch, SystemZ::CLGR);
|
|
break;
|
|
case SystemZ::CLIJ:
|
|
splitCompareBranch(Branch, SystemZ::CLFI);
|
|
break;
|
|
case SystemZ::CLGIJ:
|
|
splitCompareBranch(Branch, SystemZ::CLGFI);
|
|
break;
|
|
default:
|
|
llvm_unreachable("Unrecognized branch");
|
|
}
|
|
|
|
Terminator.Size += Terminator.ExtraRelaxSize;
|
|
Terminator.ExtraRelaxSize = 0;
|
|
Terminator.Branch = nullptr;
|
|
|
|
++LongBranches;
|
|
}
|
|
|
|
// Run a shortening pass and relax any branches that need to be relaxed.
|
|
void SystemZLongBranch::relaxBranches() {
|
|
SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin();
|
|
BlockPosition Position(MF->getAlignment());
|
|
for (auto &Block : MBBs) {
|
|
skipNonTerminators(Position, Block);
|
|
for (unsigned BTI = 0, BTE = Block.NumTerminators; BTI != BTE; ++BTI) {
|
|
assert(Position.Address <= TI->Address &&
|
|
"Addresses shouldn't go forwards");
|
|
if (mustRelaxBranch(*TI, Position.Address))
|
|
relaxBranch(*TI);
|
|
skipTerminator(Position, *TI, false);
|
|
++TI;
|
|
}
|
|
}
|
|
}
|
|
|
|
bool SystemZLongBranch::runOnMachineFunction(MachineFunction &F) {
|
|
TII = static_cast<const SystemZInstrInfo *>(F.getSubtarget().getInstrInfo());
|
|
MF = &F;
|
|
uint64_t Size = initMBBInfo();
|
|
if (Size <= MaxForwardRange || !mustRelaxABranch())
|
|
return false;
|
|
|
|
setWorstCaseAddresses();
|
|
relaxBranches();
|
|
return true;
|
|
}
|