[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, 11 insertions, 270 deletions

diff --git a/lib/Target/SystemZ/SystemZLongBranch.cpp b/lib/Target/SystemZ/SystemZLongBranch.cpp
index f0ea3e20be..c5c4cab6af 100644
--- a/lib/Target/SystemZ/SystemZLongBranch.cpp
+++ b/lib/Target/SystemZ/SystemZLongBranch.cpp
@@ -7,44 +7,16 @@
 //
 //===----------------------------------------------------------------------===//
 //
-// This pass does three things:
-// (1) try to remove compares if CC already contains the required information
-// (2) fuse compares and branches into COMPARE AND BRANCH instructions
-// (3) make sure that all branches are in range.
-//
-// We do (1) here rather than earlier because some transformations can
-// change the set of available CC values and we generally want those
-// transformations to have priority over (1).  This is especially true in
-// the commonest case where the CC value is used by a single in-range branch
-// instruction, since (2) will then be able to fuse the compare and the
-// branch instead.
-//
-// For example, two-address NILF can sometimes be converted into
-// three-address RISBLG.  NILF produces a CC value that indicates whether
-// the low word is zero, but RISBLG does not modify CC at all.  On the
-// other hand, 64-bit ANDs like NILL can sometimes be converted to RISBG.
-// The CC value produced by NILL isn't useful for our purposes, but the
-// value produced by RISBG can be used for any comparison with zero
-// (not just equality).  So there are some transformations that lose
-// CC values (while still being worthwhile) and others that happen to make
-// the CC result more useful than it was originally.
-//
-// We do (2) here rather than earlier because the fused form prevents
-// predication.  It also has to happen after (1).
-//
-// Doing (2) 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 (3) 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
@@ -99,8 +71,6 @@ using namespace llvm;
 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.
@@ -174,8 +144,6 @@ namespace {
     void skipTerminator(BlockPosition &Position, TerminatorInfo &Terminator,
                         bool AssumeRelaxed);
     TerminatorInfo describeTerminator(MachineInstr *MI);
-    bool optimizeCompareZero(MachineInstr *PrevCCSetter, MachineInstr *Compare);
-    bool fuseCompareAndBranch(MachineInstr *Compare);
     uint64_t initMBBInfo();
     bool mustRelaxBranch(const TerminatorInfo &Terminator, uint64_t Address);
     bool mustRelaxABranch();
@@ -273,226 +241,10 @@ TerminatorInfo SystemZLongBranch::describeTerminator(MachineInstr *MI) {
   return Terminator;
 }
 
-// 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 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;
-  }
-
-  return isCCLiveOut(MBB);
-}
-
-// Return true if all uses of the CC value produced by MBBI could make do
-// with the CC values in ReusableCCMask.  When returning true, point AlterMasks
-// to the "CC valid" and "CC mask" operands for each condition.
-static bool canRestrictCCMask(MachineBasicBlock::iterator MBBI,
-                              unsigned ReusableCCMask,
-                              SmallVectorImpl<MachineOperand *> &AlterMasks,
-                              const TargetRegisterInfo *TRI) {
-  MachineBasicBlock *MBB = MBBI->getParent();
-  MachineBasicBlock::iterator MBBE = MBB->end();
-  for (++MBBI; MBBI != MBBE; ++MBBI) {
-    if (MBBI->readsRegister(SystemZ::CC, TRI)) {
-      // Fail if this isn't a use of CC that we understand.
-      unsigned MBBIFlags = MBBI->getDesc().TSFlags;
-      unsigned FirstOpNum;
-      if (MBBIFlags & SystemZII::CCMaskFirst)
-        FirstOpNum = 0;
-      else if (MBBIFlags & SystemZII::CCMaskLast)
-        FirstOpNum = MBBI->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 = MBBI->getOperand(FirstOpNum).getImm();
-      unsigned CCMask = MBBI->getOperand(FirstOpNum + 1).getImm();
-      unsigned OutValid = ~ReusableCCMask & CCValid;
-      unsigned OutMask = ~ReusableCCMask & CCMask;
-      if (OutMask != 0 && OutMask != OutValid)
-        return false;
-
-      AlterMasks.push_back(&MBBI->getOperand(FirstOpNum));
-      AlterMasks.push_back(&MBBI->getOperand(FirstOpNum + 1));
-
-      // Succeed if this was the final use of the CC value.
-      if (MBBI->killsRegister(SystemZ::CC, TRI))
-        return true;
-    }
-    // Succeed if the instruction redefines CC.
-    if (MBBI->definesRegister(SystemZ::CC, TRI))
-      return true;
-  }
-  // Fail if there are other uses of CC that we didn't see.
-  return !isCCLiveOut(MBB);
-}
-
-// Try to make Compare redundant with PrevCCSetter, the previous setter of CC,
-// by looking for cases where Compare compares the result of PrevCCSetter
-// against zero.  Return true on success and if Compare can therefore
-// be deleted.
-bool SystemZLongBranch::optimizeCompareZero(MachineInstr *PrevCCSetter,
-                                            MachineInstr *Compare) {
-  if (MF->getTarget().getOptLevel() == CodeGenOpt::None)
-    return false;
-
-  // Check whether this is a comparison against zero.
-  if (Compare->getNumExplicitOperands() != 2 ||
-      !Compare->getOperand(1).isImm() ||
-      Compare->getOperand(1).getImm() != 0)
-    return false;
-
-  // See which compare-style condition codes are available after PrevCCSetter.
-  unsigned PrevFlags = PrevCCSetter->getDesc().TSFlags;
-  unsigned ReusableCCMask = 0;
-  if (PrevFlags & 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) &&
-      (PrevFlags & SystemZII::CCHasOrder))
-    ReusableCCMask |= SystemZ::CCMASK_CMP_LT | SystemZ::CCMASK_CMP_GT;
-
-  if (ReusableCCMask == 0)
-    return false;
-
-  // Make sure that PrevCCSetter sets the value being compared.
-  unsigned SrcReg = Compare->getOperand(0).getReg();
-  unsigned SrcSubReg = Compare->getOperand(0).getSubReg();
-  if (!PrevCCSetter->getOperand(0).isReg() ||
-      !PrevCCSetter->getOperand(0).isDef() ||
-      PrevCCSetter->getOperand(0).getReg() != SrcReg ||
-      PrevCCSetter->getOperand(0).getSubReg() != SrcSubReg)
-    return false;
-
-  // Make sure that SrcReg survives until Compare.
-  MachineBasicBlock::iterator MBBI = PrevCCSetter, MBBE = Compare;
-  const TargetRegisterInfo *TRI = &TII->getRegisterInfo();
-  for (++MBBI; MBBI != MBBE; ++MBBI)
-    if (MBBI->modifiesRegister(SrcReg, TRI))
-      return false;
-
-  // See whether all uses of Compare's CC value could make do with
-  // the values produced by PrevCCSetter.
-  SmallVector<MachineOperand *, 4> AlterMasks;
-  if (!canRestrictCCMask(Compare, ReusableCCMask, AlterMasks, TRI))
-    return false;
-
-  // Alter the CC masks that canRestrictCCMask says need to be altered.
-  unsigned CCValues = SystemZII::getCCValues(PrevFlags);
-  assert((ReusableCCMask & ~CCValues) == 0 && "Invalid CCValues");
-  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 PrevCCSetter.
-  int CCDef = PrevCCSetter->findRegisterDefOperandIdx(SystemZ::CC, false,
-                                                      true, TRI);
-  assert(CCDef >= 0 && "Couldn't find CC set");
-  PrevCCSetter->getOperand(CCDef).setIsDead(false);
-
-  // Clear any intervening kills of CC.
-  MBBI = PrevCCSetter;
-  for (++MBBI; MBBI != MBBE; ++MBBI)
-    MBBI->clearRegisterKills(SystemZ::CC, TRI);
-
-  return true;
-}
-
-// 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(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");
-      MBBI->RemoveOperand(CCUse);
-      MBBI->RemoveOperand(2);
-      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.
 uint64_t SystemZLongBranch::initMBBInfo() {
-  const TargetRegisterInfo *TRI = &TII->getRegisterInfo();
-
   MF->RenumberBlocks();
   unsigned NumBlocks = MF->size();
 
@@ -513,20 +265,9 @@ uint64_t SystemZLongBranch::initMBBInfo() {
     // Calculate the size of the fixed part of the block.
     MachineBasicBlock::iterator MI = MBB->begin();
     MachineBasicBlock::iterator End = MBB->end();
-    MachineInstr *PrevCCSetter = 0;
     while (MI != End && !MI->isTerminator()) {
-      MachineInstr *Current = MI;
+      Block.Size += TII->getInstSizeInBytes(MI);
       ++MI;
-      if (Current->isCompare()) {
-        if ((PrevCCSetter && optimizeCompareZero(PrevCCSetter, Current)) ||
-            fuseCompareAndBranch(Current)) {
-          Current->removeFromParent();
-          continue;
-        }
-      }
-      if (Current->modifiesRegister(SystemZ::CC, TRI))
-        PrevCCSetter = Current;
-      Block.Size += TII->getInstSizeInBytes(Current);
     }
     skipNonTerminators(Position, Block);