[SystemZ] Split out comparison elimination into a separate pass

Perhaps predictably, doing comparison elimination on the fly during
SystemZLongBranch turned out to be a bad idea.  The next patches make
use of LOAD AND TEST and BRANCH ON COUNT, both of which require
changes to earlier instructions.

No functionality change intended.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@187718 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 311 insertions, 0 deletions

diff --git a/lib/Target/SystemZ/SystemZElimCompare.cpp b/lib/Target/SystemZ/SystemZElimCompare.cpp
new file mode 100644
index 0000000000..9b0bdd8505
--- /dev/null
+++ b/lib/Target/SystemZ/SystemZElimCompare.cpp
@@ -0,0 +1,311 @@
+//===-- SystemZElimCompare.cpp - Eliminate comparison instructions --------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass:
+// (1) tries to remove compares if CC already contains the required information
+// (2) fuses compares and branches into COMPARE AND BRANCH instructions
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "systemz-elim-compare"
+
+#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/CommandLine.h"
+#include "llvm/Support/MathExtras.h"
+#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/Target/TargetMachine.h"
+#include "llvm/Target/TargetRegisterInfo.h"
+
+using namespace llvm;
+
+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";
+    }
+
+    bool processBlock(MachineBasicBlock *MBB);
+    bool runOnMachineFunction(MachineFunction &F);
+
+  private:
+    bool adjustCCMasksForInstr(MachineInstr *MI, MachineInstr *Compare,
+                               SmallVectorImpl<MachineInstr *> &CCUsers);
+    bool optimizeCompareZero(MachineInstr *Compare,
+                             SmallVectorImpl<MachineInstr *> &CCUsers);
+    bool fuseCompareAndBranch(MachineInstr *Compare,
+                              SmallVectorImpl<MachineInstr *> &CCUsers);
+
+    const SystemZInstrInfo *TII;
+    const TargetRegisterInfo *TRI;
+  };
+
+  char SystemZElimCompare::ID = 0;
+} // end of 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)
+    if ((*SI)->isLiveIn(SystemZ::CC))
+      return true;
+  return false;
+}
+
+// Return true if any CC result of MI would reflect the value of subreg
+// SubReg of Reg.
+static bool resultTests(MachineInstr *MI, unsigned Reg, unsigned SubReg) {
+  if (MI->getNumOperands() > 0 &&
+      MI->getOperand(0).isReg() &&
+      MI->getOperand(0).isDef() &&
+      MI->getOperand(0).getReg() == Reg &&
+      MI->getOperand(0).getSubReg() == SubReg)
+    return true;
+
+  return false;
+}
+
+// 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
+// they test the result of MI directly, returning true on success.
+// Leave everything unchanged on failure.
+bool SystemZElimCompare::
+adjustCCMasksForInstr(MachineInstr *MI, MachineInstr *Compare,
+                      SmallVectorImpl<MachineInstr *> &CCUsers) {
+  int Opcode = MI->getOpcode();
+  const MCInstrDesc &Desc = TII->get(Opcode);
+  unsigned MIFlags = Desc.TSFlags;
+
+  // See which compare-style condition codes are available.
+  unsigned ReusableCCMask = 0;
+  if (MIFlags & SystemZII::CCHasZero)
+    ReusableCCMask |= SystemZ::CCMASK_CMP_EQ;
+
+  // 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 (ReusableCCMask == 0)
+    return false;
+
+  unsigned CCValues = SystemZII::getCCValues(MIFlags);
+  assert((ReusableCCMask & ~CCValues) == 0 && "Invalid CCValues");
+
+  // Now check whether these flags are enough for all users.
+  SmallVector<MachineOperand *, 4> AlterMasks;
+  for (unsigned int I = 0, E = CCUsers.size(); I != E; ++I) {
+    MachineInstr *MI = CCUsers[I];
+
+    // Fail if this isn't a use of CC that we understand.
+    unsigned Flags = MI->getDesc().TSFlags;
+    unsigned FirstOpNum;
+    if (Flags & SystemZII::CCMaskFirst)
+      FirstOpNum = 0;
+    else if (Flags & SystemZII::CCMaskLast)
+      FirstOpNum = MI->getNumExplicitOperands() - 2;
+    else
+      return false;
+
+    // Check whether the instruction predicate treats all CC values
+    // outside of ReusableCCMask in the same way.  In that case it
+    // doesn't matter what those CC values mean.
+    unsigned CCValid = MI->getOperand(FirstOpNum).getImm();
+    unsigned CCMask = MI->getOperand(FirstOpNum + 1).getImm();
+    unsigned OutValid = ~ReusableCCMask & CCValid;
+    unsigned OutMask = ~ReusableCCMask & CCMask;
+    if (OutMask != 0 && OutMask != OutValid)
+      return false;
+
+    AlterMasks.push_back(&MI->getOperand(FirstOpNum));
+    AlterMasks.push_back(&MI->getOperand(FirstOpNum + 1));
+  }
+
+  // All users are OK.  Adjust the masks for MI.
+  for (unsigned I = 0, E = AlterMasks.size(); I != E; I += 2) {
+    AlterMasks[I]->setImm(CCValues);
+    unsigned CCMask = AlterMasks[I + 1]->getImm();
+    if (CCMask & ~ReusableCCMask)
+      AlterMasks[I + 1]->setImm((CCMask & ReusableCCMask) |
+                                (CCValues & ~ReusableCCMask));
+  }
+
+  // CC is now live after MI.
+  int CCDef = MI->findRegisterDefOperandIdx(SystemZ::CC, false, true, TRI);
+  assert(CCDef >= 0 && "Couldn't find CC set");
+  MI->getOperand(CCDef).setIsDead(false);
+
+  // Clear any intervening kills of CC.
+  MachineBasicBlock::iterator MBBI = MI, MBBE = Compare;
+  for (++MBBI; MBBI != MBBE; ++MBBI)
+    MBBI->clearRegisterKills(SystemZ::CC, TRI);
+
+  return true;
+}
+
+// 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
+// value produced by Compare.
+bool SystemZElimCompare::
+optimizeCompareZero(MachineInstr *Compare,
+                    SmallVectorImpl<MachineInstr *> &CCUsers) {
+  // Check whether this is a comparison against zero.
+  if (Compare->getNumExplicitOperands() != 2 ||
+      !Compare->getOperand(1).isImm() ||
+      Compare->getOperand(1).getImm() != 0)
+    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();
+  while (MBBI != MBBE) {
+    --MBBI;
+    MachineInstr *MI = MBBI;
+    if (resultTests(MI, SrcReg, SrcSubReg) &&
+        adjustCCMasksForInstr(MI, Compare, CCUsers)) {
+      EliminatedComparisons += 1;
+      return true;
+    }
+    if (MI->modifiesRegister(SrcReg, TRI) ||
+        MI->modifiesRegister(SystemZ::CC, TRI))
+      return false;
+  }
+  return false;
+}
+
+// Try to fuse comparison instruction Compare into a later branch.
+// Return true on success and if Compare is therefore redundant.
+bool SystemZElimCompare::
+fuseCompareAndBranch(MachineInstr *Compare,
+                     SmallVectorImpl<MachineInstr *> &CCUsers) {
+  // See whether we have a comparison that can be fused.
+  unsigned FusedOpcode = TII->getCompareAndBranch(Compare->getOpcode(),
+                                                  Compare);
+  if (!FusedOpcode)
+    return false;
+
+  // See whether we have a single branch with which to fuse.
+  if (CCUsers.size() != 1)
+    return false;
+  MachineInstr *Branch = CCUsers[0];
+  if (Branch->getOpcode() != SystemZ::BRC)
+    return false;
+
+  // Make sure that the operands are available at the branch.
+  unsigned SrcReg = Compare->getOperand(0).getReg();
+  unsigned SrcReg2 = (Compare->getOperand(1).isReg() ?
+                      Compare->getOperand(1).getReg() : 0);
+  MachineBasicBlock::iterator MBBI = Compare, MBBE = Branch;
+  for (++MBBI; MBBI != MBBE; ++MBBI)
+    if (MBBI->modifiesRegister(SrcReg, TRI) ||
+        (SrcReg2 && MBBI->modifiesRegister(SrcReg2, TRI)))
+      return false;
+
+  // Read the branch mask and target.
+  MachineOperand CCMask(MBBI->getOperand(1));
+  MachineOperand Target(MBBI->getOperand(2));
+  assert((CCMask.getImm() & ~SystemZ::CCMASK_ICMP) == 0 &&
+         "Invalid condition-code mask for integer comparison");
+
+  // Clear out all current operands.
+  int CCUse = MBBI->findRegisterUseOperandIdx(SystemZ::CC, false, TRI);
+  assert(CCUse >= 0 && "BRC must use CC");
+  Branch->RemoveOperand(CCUse);
+  Branch->RemoveOperand(2);
+  Branch->RemoveOperand(1);
+  Branch->RemoveOperand(0);
+
+  // Rebuild Branch as a fused compare and branch.
+  Branch->setDesc(TII->get(FusedOpcode));
+  MachineInstrBuilder(*Branch->getParent()->getParent(), Branch)
+    .addOperand(Compare->getOperand(0))
+    .addOperand(Compare->getOperand(1))
+    .addOperand(CCMask)
+    .addOperand(Target)
+    .addReg(SystemZ::CC, RegState::ImplicitDefine);
+
+  // 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);
+  }
+  FusedComparisons += 1;
+  return true;
+}
+
+// Process all comparison instructions in MBB.  Return true if something
+// changed.
+bool SystemZElimCompare::processBlock(MachineBasicBlock *MBB) {
+  bool Changed = false;
+
+  // Walk backwards through the block looking for comparisons, recording
+  // all CC users as we go.  The subroutines can delete Compare and
+  // instructions before it.
+  bool CompleteCCUsers = !isCCLiveOut(MBB);
+  SmallVector<MachineInstr *, 4> CCUsers;
+  MachineBasicBlock::iterator MBBI = MBB->end();
+  while (MBBI != MBB->begin()) {
+    MachineInstr *MI = --MBBI;
+    if (CompleteCCUsers &&
+        MI->isCompare() &&
+        (optimizeCompareZero(MI, CCUsers) ||
+         fuseCompareAndBranch(MI, CCUsers))) {
+      ++MBBI;
+      MI->removeFromParent();
+      Changed = true;
+      CCUsers.clear();
+      CompleteCCUsers = true;
+      continue;
+    }
+
+    if (MI->definesRegister(SystemZ::CC, TRI)) {
+      CCUsers.clear();
+      CompleteCCUsers = true;
+    } else if (MI->modifiesRegister(SystemZ::CC, TRI))
+      CompleteCCUsers = false;
+
+    if (CompleteCCUsers && MI->readsRegister(SystemZ::CC, TRI))
+      CCUsers.push_back(MI);
+  }
+  return Changed;
+}
+
+bool SystemZElimCompare::runOnMachineFunction(MachineFunction &F) {
+  TII = static_cast<const SystemZInstrInfo *>(F.getTarget().getInstrInfo());
+  TRI = &TII->getRegisterInfo();
+
+  bool Changed = false;
+  for (MachineFunction::iterator MFI = F.begin(), MFE = F.end();
+       MFI != MFE; ++MFI)
+    Changed |= processBlock(MFI);
+
+  return Changed;
+}