X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTarget%2FSystemZ%2FSystemZElimCompare.cpp;h=16f9adc79f1763b649933c857015978ac0dfad88;hb=d4cdf1962b2242fb155ee2203199dd043725e7e1;hp=9b0bdd8505ec229eee9c79f7a2fb8e2521465d3c;hpb=66fbb4781841a8411a772b6909a7e0de182b896f;p=oota-llvm.git diff --git a/lib/Target/SystemZ/SystemZElimCompare.cpp b/lib/Target/SystemZ/SystemZElimCompare.cpp index 9b0bdd8505e..16f9adc79f1 100644 --- a/lib/Target/SystemZ/SystemZElimCompare.cpp +++ b/lib/Target/SystemZ/SystemZElimCompare.cpp @@ -13,8 +13,6 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "systemz-elim-compare" - #include "SystemZTargetMachine.h" #include "llvm/ADT/Statistic.h" #include "llvm/CodeGen/MachineFunctionPass.h" @@ -28,46 +26,79 @@ using namespace llvm; +#define DEBUG_TYPE "systemz-elim-compare" + +STATISTIC(BranchOnCounts, "Number of branch-on-count instructions"); STATISTIC(EliminatedComparisons, "Number of eliminated comparisons"); STATISTIC(FusedComparisons, "Number of fused compare-and-branch instructions"); namespace { - class SystemZElimCompare : public MachineFunctionPass { - public: - static char ID; - SystemZElimCompare(const SystemZTargetMachine &tm) - : MachineFunctionPass(ID), TII(0), TRI(0) {} - - virtual const char *getPassName() const { - return "SystemZ Comparison Elimination"; - } +// Represents the references to a particular register in one or more +// instructions. +struct Reference { + Reference() + : Def(false), Use(false), IndirectDef(false), IndirectUse(false) {} + + Reference &operator|=(const Reference &Other) { + Def |= Other.Def; + IndirectDef |= Other.IndirectDef; + Use |= Other.Use; + IndirectUse |= Other.IndirectUse; + return *this; + } + + explicit operator bool() const { return Def || Use; } + + // True if the register is defined or used in some form, either directly or + // via a sub- or super-register. + bool Def; + bool Use; - bool processBlock(MachineBasicBlock *MBB); - bool runOnMachineFunction(MachineFunction &F); + // True if the register is defined or used indirectly, by a sub- or + // super-register. + bool IndirectDef; + bool IndirectUse; +}; - private: - bool adjustCCMasksForInstr(MachineInstr *MI, MachineInstr *Compare, - SmallVectorImpl &CCUsers); - bool optimizeCompareZero(MachineInstr *Compare, +class SystemZElimCompare : public MachineFunctionPass { +public: + static char ID; + SystemZElimCompare(const SystemZTargetMachine &tm) + : MachineFunctionPass(ID), TII(nullptr), TRI(nullptr) {} + + const char *getPassName() const override { + return "SystemZ Comparison Elimination"; + } + + bool processBlock(MachineBasicBlock &MBB); + bool runOnMachineFunction(MachineFunction &F) override; + +private: + Reference getRegReferences(MachineInstr *MI, unsigned Reg); + bool convertToBRCT(MachineInstr *MI, MachineInstr *Compare, + SmallVectorImpl &CCUsers); + bool convertToLoadAndTest(MachineInstr *MI); + bool adjustCCMasksForInstr(MachineInstr *MI, MachineInstr *Compare, SmallVectorImpl &CCUsers); - bool fuseCompareAndBranch(MachineInstr *Compare, - SmallVectorImpl &CCUsers); + bool optimizeCompareZero(MachineInstr *Compare, + SmallVectorImpl &CCUsers); + bool fuseCompareAndBranch(MachineInstr *Compare, + SmallVectorImpl &CCUsers); - const SystemZInstrInfo *TII; - const TargetRegisterInfo *TRI; - }; + const SystemZInstrInfo *TII; + const TargetRegisterInfo *TRI; +}; - char SystemZElimCompare::ID = 0; -} // end of anonymous namespace +char SystemZElimCompare::ID = 0; +} // end anonymous namespace FunctionPass *llvm::createSystemZElimComparePass(SystemZTargetMachine &TM) { return new SystemZElimCompare(TM); } // Return true if CC is live out of MBB. -static bool isCCLiveOut(MachineBasicBlock *MBB) { - for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), - SE = MBB->succ_end(); SI != SE; ++SI) +static bool isCCLiveOut(MachineBasicBlock &MBB) { + for (auto SI = MBB.succ_begin(), SE = MBB.succ_end(); SI != SE; ++SI) if ((*SI)->isLiveIn(SystemZ::CC)) return true; return false; @@ -83,9 +114,114 @@ static bool resultTests(MachineInstr *MI, unsigned Reg, unsigned SubReg) { MI->getOperand(0).getSubReg() == SubReg) return true; + switch (MI->getOpcode()) { + case SystemZ::LR: + case SystemZ::LGR: + case SystemZ::LGFR: + case SystemZ::LTR: + case SystemZ::LTGR: + case SystemZ::LTGFR: + case SystemZ::LER: + case SystemZ::LDR: + case SystemZ::LXR: + case SystemZ::LTEBR: + case SystemZ::LTDBR: + case SystemZ::LTXBR: + if (MI->getOperand(1).getReg() == Reg && + MI->getOperand(1).getSubReg() == SubReg) + return true; + } + return false; } +// Describe the references to Reg in MI, including sub- and super-registers. +Reference SystemZElimCompare::getRegReferences(MachineInstr *MI, unsigned Reg) { + Reference Ref; + for (unsigned I = 0, E = MI->getNumOperands(); I != E; ++I) { + const MachineOperand &MO = MI->getOperand(I); + if (MO.isReg()) { + if (unsigned MOReg = MO.getReg()) { + if (MOReg == Reg || TRI->regsOverlap(MOReg, Reg)) { + if (MO.isUse()) { + Ref.Use = true; + Ref.IndirectUse |= (MOReg != Reg); + } + if (MO.isDef()) { + Ref.Def = true; + Ref.IndirectDef |= (MOReg != Reg); + } + } + } + } + } + return Ref; +} + +// Compare compares the result of MI against zero. If MI is an addition +// of -1 and if CCUsers is a single branch on nonzero, eliminate the addition +// and convert the branch to a BRCT(G). Return true on success. +bool +SystemZElimCompare::convertToBRCT(MachineInstr *MI, MachineInstr *Compare, + SmallVectorImpl &CCUsers) { + // Check whether we have an addition of -1. + unsigned Opcode = MI->getOpcode(); + unsigned BRCT; + if (Opcode == SystemZ::AHI) + BRCT = SystemZ::BRCT; + else if (Opcode == SystemZ::AGHI) + BRCT = SystemZ::BRCTG; + else + return false; + if (MI->getOperand(2).getImm() != -1) + return false; + + // Check whether we have a single JLH. + if (CCUsers.size() != 1) + return false; + MachineInstr *Branch = CCUsers[0]; + if (Branch->getOpcode() != SystemZ::BRC || + Branch->getOperand(0).getImm() != SystemZ::CCMASK_ICMP || + Branch->getOperand(1).getImm() != SystemZ::CCMASK_CMP_NE) + return false; + + // We already know that there are no references to the register between + // MI and Compare. Make sure that there are also no references between + // Compare and Branch. + unsigned SrcReg = Compare->getOperand(0).getReg(); + MachineBasicBlock::iterator MBBI = Compare, MBBE = Branch; + for (++MBBI; MBBI != MBBE; ++MBBI) + if (getRegReferences(MBBI, SrcReg)) + return false; + + // The transformation is OK. Rebuild Branch as a BRCT(G). + MachineOperand Target(Branch->getOperand(2)); + Branch->RemoveOperand(2); + Branch->RemoveOperand(1); + Branch->RemoveOperand(0); + Branch->setDesc(TII->get(BRCT)); + MachineInstrBuilder(*Branch->getParent()->getParent(), Branch) + .addOperand(MI->getOperand(0)) + .addOperand(MI->getOperand(1)) + .addOperand(Target) + .addReg(SystemZ::CC, RegState::ImplicitDefine); + MI->removeFromParent(); + return true; +} + +// If MI is a load instruction, try to convert it into a LOAD AND TEST. +// Return true on success. +bool SystemZElimCompare::convertToLoadAndTest(MachineInstr *MI) { + unsigned Opcode = TII->getLoadAndTest(MI->getOpcode()); + if (!Opcode) + return false; + + MI->setDesc(TII->get(Opcode)); + MachineInstrBuilder(*MI->getParent()->getParent(), MI) + .addReg(SystemZ::CC, RegState::ImplicitDefine); + return true; +} + // The CC users in CCUsers are testing the result of a comparison of some // value X against zero and we know that any CC value produced by MI // would also reflect the value of X. Try to adjust CCUsers so that @@ -99,15 +235,12 @@ adjustCCMasksForInstr(MachineInstr *MI, MachineInstr *Compare, unsigned MIFlags = Desc.TSFlags; // See which compare-style condition codes are available. - unsigned ReusableCCMask = 0; - if (MIFlags & SystemZII::CCHasZero) - ReusableCCMask |= SystemZ::CCMASK_CMP_EQ; + unsigned ReusableCCMask = SystemZII::getCompareZeroCCMask(MIFlags); // For unsigned comparisons with zero, only equality makes sense. unsigned CompareFlags = Compare->getDesc().TSFlags; - if (!(CompareFlags & SystemZII::IsLogical) && - (MIFlags & SystemZII::CCHasOrder)) - ReusableCCMask |= SystemZ::CCMASK_CMP_LT | SystemZ::CCMASK_CMP_GT; + if (CompareFlags & SystemZII::IsLogical) + ReusableCCMask &= SystemZ::CCMASK_CMP_EQ; if (ReusableCCMask == 0) return false; @@ -166,6 +299,21 @@ adjustCCMasksForInstr(MachineInstr *MI, MachineInstr *Compare, return true; } +// Return true if Compare is a comparison against zero. +static bool isCompareZero(MachineInstr *Compare) { + switch (Compare->getOpcode()) { + case SystemZ::LTEBRCompare: + case SystemZ::LTDBRCompare: + case SystemZ::LTXBRCompare: + return true; + + default: + return (Compare->getNumExplicitOperands() == 2 && + Compare->getOperand(1).isImm() && + Compare->getOperand(1).getImm() == 0); + } +} + // Try to optimize cases where comparison instruction Compare is testing // a value against zero. Return true on success and if Compare should be // deleted as dead. CCUsers is the list of instructions that use the CC @@ -173,27 +321,39 @@ adjustCCMasksForInstr(MachineInstr *MI, MachineInstr *Compare, bool SystemZElimCompare:: optimizeCompareZero(MachineInstr *Compare, SmallVectorImpl &CCUsers) { - // Check whether this is a comparison against zero. - if (Compare->getNumExplicitOperands() != 2 || - !Compare->getOperand(1).isImm() || - Compare->getOperand(1).getImm() != 0) + if (!isCompareZero(Compare)) return false; // Search back for CC results that are based on the first operand. unsigned SrcReg = Compare->getOperand(0).getReg(); unsigned SrcSubReg = Compare->getOperand(0).getSubReg(); - MachineBasicBlock *MBB = Compare->getParent(); - MachineBasicBlock::iterator MBBI = Compare, MBBE = MBB->begin(); + MachineBasicBlock &MBB = *Compare->getParent(); + MachineBasicBlock::iterator MBBI = Compare, MBBE = MBB.begin(); + Reference CCRefs; + Reference SrcRefs; while (MBBI != MBBE) { --MBBI; MachineInstr *MI = MBBI; - if (resultTests(MI, SrcReg, SrcSubReg) && - adjustCCMasksForInstr(MI, Compare, CCUsers)) { - EliminatedComparisons += 1; - return true; + if (resultTests(MI, SrcReg, SrcSubReg)) { + // Try to remove both MI and Compare by converting a branch to BRCT(G). + // We don't care in this case whether CC is modified between MI and + // Compare. + if (!CCRefs.Use && !SrcRefs && convertToBRCT(MI, Compare, CCUsers)) { + BranchOnCounts += 1; + return true; + } + // Try to eliminate Compare by reusing a CC result from MI. + if ((!CCRefs && convertToLoadAndTest(MI)) || + (!CCRefs.Def && adjustCCMasksForInstr(MI, Compare, CCUsers))) { + EliminatedComparisons += 1; + return true; + } } - if (MI->modifiesRegister(SrcReg, TRI) || - MI->modifiesRegister(SystemZ::CC, TRI)) + SrcRefs |= getRegReferences(MI, SrcReg); + if (SrcRefs.Def) + return false; + CCRefs |= getRegReferences(MI, SystemZ::CC); + if (CCRefs.Use && CCRefs.Def) return false; } return false; @@ -263,7 +423,7 @@ fuseCompareAndBranch(MachineInstr *Compare, // Process all comparison instructions in MBB. Return true if something // changed. -bool SystemZElimCompare::processBlock(MachineBasicBlock *MBB) { +bool SystemZElimCompare::processBlock(MachineBasicBlock &MBB) { bool Changed = false; // Walk backwards through the block looking for comparisons, recording @@ -271,8 +431,8 @@ bool SystemZElimCompare::processBlock(MachineBasicBlock *MBB) { // instructions before it. bool CompleteCCUsers = !isCCLiveOut(MBB); SmallVector CCUsers; - MachineBasicBlock::iterator MBBI = MBB->end(); - while (MBBI != MBB->begin()) { + MachineBasicBlock::iterator MBBI = MBB.end(); + while (MBBI != MBB.begin()) { MachineInstr *MI = --MBBI; if (CompleteCCUsers && MI->isCompare() && @@ -286,26 +446,24 @@ bool SystemZElimCompare::processBlock(MachineBasicBlock *MBB) { continue; } - if (MI->definesRegister(SystemZ::CC, TRI)) { + Reference CCRefs(getRegReferences(MI, SystemZ::CC)); + if (CCRefs.Def) { CCUsers.clear(); - CompleteCCUsers = true; - } else if (MI->modifiesRegister(SystemZ::CC, TRI)) - CompleteCCUsers = false; - - if (CompleteCCUsers && MI->readsRegister(SystemZ::CC, TRI)) + CompleteCCUsers = !CCRefs.IndirectDef; + } + if (CompleteCCUsers && CCRefs.Use) CCUsers.push_back(MI); } return Changed; } bool SystemZElimCompare::runOnMachineFunction(MachineFunction &F) { - TII = static_cast(F.getTarget().getInstrInfo()); + TII = static_cast(F.getSubtarget().getInstrInfo()); TRI = &TII->getRegisterInfo(); bool Changed = false; - for (MachineFunction::iterator MFI = F.begin(), MFE = F.end(); - MFI != MFE; ++MFI) - Changed |= processBlock(MFI); + for (auto &MBB : F) + Changed |= processBlock(MBB); return Changed; }