X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTarget%2FSystemZ%2FSystemZLongBranch.cpp;h=8dab44e7f8af593b7e300e202b1ce7b73b46125f;hb=00552e3875ee5f382db6c98286a241a7d0efe1b8;hp=2d2605886b54ac3f1af33f10b4d0f02f017e1fdf;hpb=0416e3c599c22dc656a1115ac983116ad0b2d9da;p=oota-llvm.git diff --git a/lib/Target/SystemZ/SystemZLongBranch.cpp b/lib/Target/SystemZ/SystemZLongBranch.cpp index 2d2605886b5..8dab44e7f8a 100644 --- a/lib/Target/SystemZ/SystemZLongBranch.cpp +++ b/lib/Target/SystemZ/SystemZLongBranch.cpp @@ -7,26 +7,16 @@ // //===----------------------------------------------------------------------===// // -// This pass does two things: -// (1) fuse compares and branches into COMPARE AND BRANCH instructions -// (2) make sure that all branches are in range. -// -// We do (1) here rather than earlier because the fused form prevents -// predication. -// -// Doing it so late makes it more likely that a register will be reused -// between the compare and the branch, but it isn't clear whether preventing -// that would be a win or not. -// -// There are several ways in which (2) 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. +// 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 @@ -63,8 +53,6 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "systemz-long-branch" - #include "SystemZTargetMachine.h" #include "llvm/ADT/Statistic.h" #include "llvm/CodeGen/MachineFunctionPass.h" @@ -78,104 +66,105 @@ 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. - 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(0), 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(0) {} - - virtual const char *getPassName() const { - return "SystemZ Long Branch"; - } +// 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); - - private: - void skipNonTerminators(BlockPosition &Position, MBBInfo &Block); - void skipTerminator(BlockPosition &Position, TerminatorInfo &Terminator, - bool AssumeRelaxed); - TerminatorInfo describeTerminator(MachineInstr *MI); - bool fuseCompareAndBranch(MachineInstr *Compare); - uint64_t initMBBInfo(); - bool mustRelaxBranch(const TerminatorInfo &Terminator, uint64_t Address); - bool mustRelaxABranch(); - void setWorstCaseAddresses(); - void splitCompareBranch(MachineInstr *MI, unsigned CompareOpcode); - void relaxBranch(TerminatorInfo &Terminator); - void relaxBranches(); - - const SystemZInstrInfo *TII; - MachineFunction *MF; - SmallVector MBBs; - SmallVector Terminators; - }; - - char SystemZLongBranch::ID = 0; - - 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 MBBs; + SmallVector 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); @@ -231,12 +220,19 @@ TerminatorInfo SystemZLongBranch::describeTerminator(MachineInstr *MI) { // 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: - // Relaxes to a CR/BRCL sequence, which is 2 bytes longer. + case SystemZ::CLRJ: + // Relaxes to a C(L)R/BRCL sequence, which is 2 bytes longer. Terminator.ExtraRelaxSize = 2; break; case SystemZ::CGRJ: - // Relaxes to a CGR/BRCL sequence, which is 4 bytes longer. + case SystemZ::CLGRJ: + // Relaxes to a C(L)GR/BRCL sequence, which is 4 bytes longer. Terminator.ExtraRelaxSize = 4; break; case SystemZ::CIJ: @@ -244,6 +240,11 @@ TerminatorInfo SystemZLongBranch::describeTerminator(MachineInstr *MI) { // 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"); } @@ -254,90 +255,6 @@ TerminatorInfo SystemZLongBranch::describeTerminator(MachineInstr *MI) { return Terminator; } -// Return true if CC is live after MBBI. -static bool isCCLiveAfter(MachineBasicBlock::iterator MBBI, - const TargetRegisterInfo *TRI) { - if (MBBI->killsRegister(SystemZ::CC, TRI)) - return false; - - MachineBasicBlock *MBB = MBBI->getParent(); - MachineBasicBlock::iterator MBBE = MBB->end(); - for (++MBBI; MBBI != MBBE; ++MBBI) { - if (MBBI->readsRegister(SystemZ::CC, TRI)) - return true; - if (MBBI->definesRegister(SystemZ::CC, TRI)) - return false; - } - - for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), - SE = MBB->succ_end(); SI != SE; ++SI) - if ((*SI)->isLiveIn(SystemZ::CC)) - return true; - - return false; -} - -// Try to fuse compare instruction Compare into a later branch. Return -// true on success and if Compare is therefore redundant. -bool SystemZLongBranch::fuseCompareAndBranch(MachineInstr *Compare) { - if (MF->getTarget().getOptLevel() == CodeGenOpt::None) - return false; - - unsigned FusedOpcode = TII->getCompareAndBranch(Compare->getOpcode(), - Compare); - if (!FusedOpcode) - return false; - - unsigned SrcReg = Compare->getOperand(0).getReg(); - unsigned SrcReg2 = (Compare->getOperand(1).isReg() ? - Compare->getOperand(1).getReg() : 0); - const TargetRegisterInfo *TRI = &TII->getRegisterInfo(); - MachineBasicBlock *MBB = Compare->getParent(); - MachineBasicBlock::iterator MBBI = Compare, MBBE = MBB->end(); - for (++MBBI; MBBI != MBBE; ++MBBI) { - if (MBBI->getOpcode() == SystemZ::BRC && !isCCLiveAfter(MBBI, TRI)) { - // Read the branch mask and target. - MachineOperand CCMask(MBBI->getOperand(0)); - MachineOperand Target(MBBI->getOperand(1)); - - // Clear out all current operands. - int CCUse = MBBI->findRegisterUseOperandIdx(SystemZ::CC, false, TRI); - assert(CCUse >= 0 && "BRC must use CC"); - MBBI->RemoveOperand(CCUse); - MBBI->RemoveOperand(1); - MBBI->RemoveOperand(0); - - // Rebuild MBBI as a fused compare and branch. - MBBI->setDesc(TII->get(FusedOpcode)); - MachineInstrBuilder(*MBB->getParent(), MBBI) - .addOperand(Compare->getOperand(0)) - .addOperand(Compare->getOperand(1)) - .addOperand(CCMask) - .addOperand(Target); - - // Clear any intervening kills of SrcReg and SrcReg2. - MBBI = Compare; - for (++MBBI; MBBI != MBBE; ++MBBI) { - MBBI->clearRegisterKills(SrcReg, TRI); - if (SrcReg2) - MBBI->clearRegisterKills(SrcReg2, TRI); - } - return true; - } - - // Stop if we find another reference to CC before a branch. - if (MBBI->readsRegister(SystemZ::CC, TRI) || - MBBI->modifiesRegister(SystemZ::CC, TRI)) - return false; - - // Stop if we find another assignment to the registers before the branch. - if (MBBI->modifiesRegister(SrcReg, TRI) || - (SrcReg2 && MBBI->modifiesRegister(SrcReg2, TRI))) - return false; - } - return false; -} - // Fill MBBs and Terminators, setting the addresses on the assumption // that no branches need relaxation. Return the size of the function under // this assumption. @@ -363,12 +280,8 @@ uint64_t SystemZLongBranch::initMBBInfo() { MachineBasicBlock::iterator MI = MBB->begin(); MachineBasicBlock::iterator End = MBB->end(); while (MI != End && !MI->isTerminator()) { - MachineInstr *Current = MI; + Block.Size += TII->getInstSizeInBytes(MI); ++MI; - if (Current->isCompare() && fuseCompareAndBranch(Current)) - Current->removeFromParent(); - else - Block.Size += TII->getInstSizeInBytes(Current); } skipNonTerminators(Position, Block); @@ -409,9 +322,8 @@ bool SystemZLongBranch::mustRelaxBranch(const TerminatorInfo &Terminator, // Return true if, under current assumptions, any terminator needs // to be relaxed. bool SystemZLongBranch::mustRelaxABranch() { - for (SmallVectorImpl::iterator TI = Terminators.begin(), - TE = Terminators.end(); TI != TE; ++TI) - if (mustRelaxBranch(*TI, TI->Address)) + for (auto &Terminator : Terminators) + if (mustRelaxBranch(Terminator, Terminator.Address)) return true; return false; } @@ -421,16 +333,34 @@ bool SystemZLongBranch::mustRelaxABranch() { void SystemZLongBranch::setWorstCaseAddresses() { SmallVector::iterator TI = Terminators.begin(); BlockPosition Position(MF->getAlignment()); - for (SmallVectorImpl::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, @@ -441,10 +371,11 @@ void SystemZLongBranch::splitCompareBranch(MachineInstr *MI, .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->getOperand(2).setIsKill(); + BRCL->addRegisterKilled(SystemZ::CC, &TII->getRegisterInfo()); MI->eraseFromParent(); } @@ -458,6 +389,12 @@ void SystemZLongBranch::relaxBranch(TerminatorInfo &Terminator) { 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; @@ -470,13 +407,25 @@ void SystemZLongBranch::relaxBranch(TerminatorInfo &Terminator) { 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; } @@ -485,10 +434,9 @@ void SystemZLongBranch::relaxBranch(TerminatorInfo &Terminator) { void SystemZLongBranch::relaxBranches() { SmallVector::iterator TI = Terminators.begin(); BlockPosition Position(MF->getAlignment()); - for (SmallVectorImpl::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) { assert(Position.Address <= TI->Address && "Addresses shouldn't go forwards"); if (mustRelaxBranch(*TI, Position.Address)) @@ -500,7 +448,7 @@ void SystemZLongBranch::relaxBranches() { } bool SystemZLongBranch::runOnMachineFunction(MachineFunction &F) { - TII = static_cast(F.getTarget().getInstrInfo()); + TII = static_cast(F.getSubtarget().getInstrInfo()); MF = &F; uint64_t Size = initMBBInfo(); if (Size <= MaxForwardRange || !mustRelaxABranch())