// are actually relatively cheap. It therefore doesn't seem worth spending
// much compilation time on the problem. Instead, the approach we take is:
//
-// (1) Check whether all branches can be short (the usual case). Exit the
-// pass if so.
-// (2) If one branch needs to be long, work out the address that each block
-// would have if all branches need to be long, as for shortening above.
-// (3) Relax any branch that is out of range according to this pessimistic
-// assumption.
+// (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.
//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "systemz-long-branch"
-
#include "SystemZTargetMachine.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
using namespace llvm;
+#define DEBUG_TYPE "systemz-long-branch"
+
STATISTIC(LongBranches, "Number of long branches.");
namespace {
- typedef MachineBasicBlock::iterator Iter;
-
- // Represents positional information about a basic block.
- struct MBBInfo {
- // The address that we currently assume the block has, relative to
- // the start of the function. This is designed so that taking the
- // difference between two addresses gives a conservative upper bound
- // on the distance between them.
- 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 current address of the terminator, in the same form as
- // for BlockInfo.
- 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(0), Size(0), TargetBlock(0), ExtraRelaxSize(0) {}
- };
-
- // Used to keep track of the current position while iterating over the blocks.
- struct BlockPosition {
- // The offset from the start of the function, in the same form
- // as BlockInfo.
- 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(static_cast<const SystemZInstrInfo *>(tm.getInstrInfo())) {}
-
- virtual const char *getPassName() const {
- return "SystemZ Long Branch";
- }
-
- bool runOnMachineFunction(MachineFunction &F);
-
- 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);
- bool mustRelaxABranch();
- void setWorstCaseAddresses();
- void relaxBranch(TerminatorInfo &Terminator);
- void relaxBranches();
-
- const SystemZInstrInfo *TII;
- MachineFunction *MF;
- SmallVector<MBBInfo, 16> MBBs;
- SmallVector<TerminatorInfo, 16> Terminators;
- };
-
- char SystemZLongBranch::ID = 0;
+// 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";
+ }
- const uint64_t MaxBackwardRange = 0x10000;
- const uint64_t MaxForwardRange = 0xfffe;
-} // end of anonymous namespace
+ bool runOnMachineFunction(MachineFunction &F) override;
+
+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);
TerminatorInfo Terminator;
Terminator.Size = TII->getInstSizeInBytes(MI);
if (MI->isConditionalBranch() || MI->isUnconditionalBranch()) {
- Terminator.Branch = MI;
switch (MI->getOpcode()) {
case SystemZ::J:
// Relaxes to JG, which is 2 bytes longer.
- Terminator.TargetBlock = MI->getOperand(0).getMBB()->getNumber();
Terminator.ExtraRelaxSize = 2;
break;
case SystemZ::BRC:
- // Relaxes to BRCL, which is 2 bytes longer. Operand 0 is the
- // condition code mask.
- Terminator.TargetBlock = MI->getOperand(1).getMBB()->getNumber();
+ // 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;
}
return Position.Address;
}
-// Return true if, under current assumptions, Terminator needs to be relaxed.
-bool SystemZLongBranch::mustRelaxBranch(const TerminatorInfo &Terminator) {
+// 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 (Target.Address < Terminator.Address) {
- if (Terminator.Address - Target.Address <= MaxBackwardRange)
+ if (Address >= Target.Address) {
+ if (Address - Target.Address <= MaxBackwardRange)
return false;
} else {
- if (Target.Address - Terminator.Address <= MaxForwardRange)
+ if (Target.Address - Address <= MaxForwardRange)
return false;
}
// Return true if, under current assumptions, any terminator needs
// to be relaxed.
bool SystemZLongBranch::mustRelaxABranch() {
- for (SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin(),
- TE = Terminators.end(); TI != TE; ++TI)
- if (mustRelaxBranch(*TI))
+ for (auto &Terminator : Terminators)
+ if (mustRelaxBranch(Terminator, Terminator.Address))
return true;
return false;
}
void SystemZLongBranch::setWorstCaseAddresses() {
SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin();
BlockPosition Position(MF->getAlignment());
- for (SmallVector<MBBInfo, 16>::iterator BI = MBBs.begin(), BE = MBBs.end();
- BI != BE; ++BI) {
- skipNonTerminators(Position, *BI);
- for (unsigned BTI = 0, BTE = BI->NumTerminators; BTI != BTE; ++BTI) {
+ 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;
- default:
- llvm_unreachable("Unrecognized branch");
- }
+ 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 = 0;
+ Terminator.Branch = nullptr;
++LongBranches;
}
-// Relax any branches that need to be relaxed, under current assumptions.
+// Run a shortening pass and relax any branches that need to be relaxed.
void SystemZLongBranch::relaxBranches() {
- for (SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin(),
- TE = Terminators.end(); TI != TE; ++TI)
- if (mustRelaxBranch(*TI))
- relaxBranch(*TI);
+ 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())