[SystemZ] Register compare-and-branch support

This patch adds support for the CRJ and CGRJ instructions.  Support for
the immediate forms will be a separate patch.

The architecture has a large number of comparison instructions.  I think
it's generally better to concentrate on using the "best" comparison
instruction first and foremost, then only use something like CRJ if
CR really was the natual choice of comparison instruction.  The patch
therefore opportunistically converts separate CR and BRC instructions
into a single CRJ while emitting instructions in ISelLowering.


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

7 files changed, 237 insertions, 28 deletions

diff --git a/lib/Target/SystemZ/SystemZISelLowering.cpp b/lib/Target/SystemZ/SystemZISelLowering.cpp
index f575911fad..03a6da6dc4 100644
--- a/lib/Target/SystemZ/SystemZISelLowering.cpp
+++ b/lib/Target/SystemZ/SystemZISelLowering.cpp
@@ -1609,6 +1609,33 @@ static MachineBasicBlock *splitBlockAfter(MachineInstr *MI,
   return NewMBB;
 }
 
+bool SystemZTargetLowering::
+convertPrevCompareToBranch(MachineBasicBlock *MBB,
+                           MachineBasicBlock::iterator MBBI,
+                           unsigned CCMask, MachineBasicBlock *Target) const {
+  MachineBasicBlock::iterator Compare = MBBI;
+  MachineBasicBlock::iterator Begin = MBB->begin();
+  do
+    {
+      if (Compare == Begin)
+        return false;
+      --Compare;
+    }
+  while (Compare->isDebugValue());
+
+  const SystemZInstrInfo *TII = TM.getInstrInfo();
+  unsigned FusedOpcode = TII->getCompareAndBranch(Compare->getOpcode());
+  if (!FusedOpcode)
+    return false;
+
+  DebugLoc DL = Compare->getDebugLoc();
+  BuildMI(*MBB, MBBI, DL, TII->get(FusedOpcode))
+    .addOperand(Compare->getOperand(0)).addOperand(Compare->getOperand(1))
+    .addImm(CCMask).addMBB(Target);
+  Compare->removeFromParent();
+  return true;
+}
+
 // Implement EmitInstrWithCustomInserter for pseudo Select* instruction MI.
 MachineBasicBlock *
 SystemZTargetLowering::emitSelect(MachineInstr *MI,
@@ -1626,13 +1653,17 @@ SystemZTargetLowering::emitSelect(MachineInstr *MI,
   MachineBasicBlock *FalseMBB = emitBlockAfter(StartMBB);
 
   //  StartMBB:
-  //   ...
-  //   TrueVal = ...
-  //   cmpTY ccX, r1, r2
-  //   jCC JoinMBB
+  //   BRC CCMask, JoinMBB
   //   # fallthrough to FalseMBB
+  //
+  // The original DAG glues comparisons to their uses, both to ensure
+  // that no CC-clobbering instructions are inserted between them, and
+  // to ensure that comparison results are not reused.  This means that
+  // this Select is the sole user of any preceding comparison instruction
+  // and that we can try to use a fused compare and branch instead.
   MBB = StartMBB;
-  BuildMI(MBB, DL, TII->get(SystemZ::BRC)).addImm(CCMask).addMBB(JoinMBB);
+  if (!convertPrevCompareToBranch(MBB, MI, CCMask, JoinMBB))
+    BuildMI(MBB, DL, TII->get(SystemZ::BRC)).addImm(CCMask).addMBB(JoinMBB);
   MBB->addSuccessor(JoinMBB);
   MBB->addSuccessor(FalseMBB);
 
@@ -1854,10 +1885,17 @@ SystemZTargetLowering::emitAtomicLoadMinMax(MachineInstr *MI,
   if (IsSubWord)
     BuildMI(MBB, DL, TII->get(SystemZ::RLL), RotatedOldVal)
       .addReg(OldVal).addReg(BitShift).addImm(0);
-  BuildMI(MBB, DL, TII->get(CompareOpcode))
-    .addReg(RotatedOldVal).addReg(Src2);
-  BuildMI(MBB, DL, TII->get(SystemZ::BRC))
-    .addImm(KeepOldMask).addMBB(UpdateMBB);
+  unsigned FusedOpcode = TII->getCompareAndBranch(CompareOpcode);
+  if (FusedOpcode)
+    BuildMI(MBB, DL, TII->get(FusedOpcode))
+      .addReg(RotatedOldVal).addReg(Src2)
+      .addImm(KeepOldMask).addMBB(UpdateMBB);
+  else {
+    BuildMI(MBB, DL, TII->get(CompareOpcode))
+      .addReg(RotatedOldVal).addReg(Src2);
+    BuildMI(MBB, DL, TII->get(SystemZ::BRC))
+      .addImm(KeepOldMask).addMBB(UpdateMBB);
+  }
   MBB->addSuccessor(UpdateMBB);
   MBB->addSuccessor(UseAltMBB);
 
@@ -1959,8 +1997,7 @@ SystemZTargetLowering::emitAtomicCmpSwapW(MachineInstr *MI,
   //                      ^^ Replace the upper 32-BitSize bits of the
   //                         comparison value with those that we loaded,
   //                         so that we can use a full word comparison.
-  //   CR %Dest, %RetryCmpVal
-  //   JNE DoneMBB
+  //   CRJNE %Dest, %RetryCmpVal, DoneMBB
   //   # Fall through to SetMBB
   MBB = LoopMBB;
   BuildMI(MBB, DL, TII->get(SystemZ::PHI), OldVal)
@@ -1976,9 +2013,9 @@ SystemZTargetLowering::emitAtomicCmpSwapW(MachineInstr *MI,
     .addReg(OldVal).addReg(BitShift).addImm(BitSize);
   BuildMI(MBB, DL, TII->get(SystemZ::RISBG32), RetryCmpVal)
     .addReg(CmpVal).addReg(Dest).addImm(32).addImm(63 - BitSize).addImm(0);
-  BuildMI(MBB, DL, TII->get(SystemZ::CR))
-    .addReg(Dest).addReg(RetryCmpVal);
-  BuildMI(MBB, DL, TII->get(SystemZ::BRC)).addImm(MaskNE).addMBB(DoneMBB);
+  BuildMI(MBB, DL, TII->get(SystemZ::CRJ))
+    .addReg(Dest).addReg(RetryCmpVal)
+    .addImm(MaskNE).addMBB(DoneMBB);
   MBB->addSuccessor(DoneMBB);
   MBB->addSuccessor(SetMBB);
 
@@ -2227,6 +2264,16 @@ EmitInstrWithCustomInserter(MachineInstr *MI, MachineBasicBlock *MBB) const {
 
   case SystemZ::ATOMIC_CMP_SWAPW:
     return emitAtomicCmpSwapW(MI, MBB);
+  case SystemZ::BRC:
+    // The original DAG glues comparisons to their uses, both to ensure
+    // that no CC-clobbering instructions are inserted between them, and
+    // to ensure that comparison results are not reused.  This means that
+    // a BRC is the sole user of a preceding comparison and that we can
+    // try to use a fused compare and branch instead.
+    if (convertPrevCompareToBranch(MBB, MI, MI->getOperand(0).getImm(),
+                                   MI->getOperand(1).getMBB()))
+      MI->eraseFromParent();
+    return MBB;
   default:
     llvm_unreachable("Unexpected instr type to insert");
   }
diff --git a/lib/Target/SystemZ/SystemZISelLowering.h b/lib/Target/SystemZ/SystemZISelLowering.h
index e408bd280a..129165df6a 100644
--- a/lib/Target/SystemZ/SystemZISelLowering.h
+++ b/lib/Target/SystemZ/SystemZISelLowering.h
@@ -16,6 +16,7 @@
 #define LLVM_TARGET_SystemZ_ISELLOWERING_H
 
 #include "SystemZ.h"
+#include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/SelectionDAG.h"
 #include "llvm/Target/TargetLowering.h"
 
@@ -189,6 +190,15 @@ private:
   SDValue lowerSTACKSAVE(SDValue Op, SelectionDAG &DAG) const;
   SDValue lowerSTACKRESTORE(SDValue Op, SelectionDAG &DAG) const;
 
+  // If the last instruction before MBBI in MBB was some form of COMPARE,
+  // try to replace it with a COMPARE AND BRANCH just before MBBI.
+  // CCMask and Target are the BRC-like operands for the branch.
+  // Return true if the change was made.
+  bool convertPrevCompareToBranch(MachineBasicBlock *MBB,
+                                  MachineBasicBlock::iterator MBBI,
+                                  unsigned CCMask,
+                                  MachineBasicBlock *Target) const;
+
   // Implement EmitInstrWithCustomInserter for individual operation types.
   MachineBasicBlock *emitSelect(MachineInstr *MI,
                                 MachineBasicBlock *BB) const;
diff --git a/lib/Target/SystemZ/SystemZInstrFormats.td b/lib/Target/SystemZ/SystemZInstrFormats.td
index a9bc5629d0..c52e2a29f3 100644
--- a/lib/Target/SystemZ/SystemZInstrFormats.td
+++ b/lib/Target/SystemZ/SystemZInstrFormats.td
@@ -110,6 +110,25 @@ class InstRI<bits<12> op, dag outs, dag ins, string asmstr, list<dag> pattern>
   let Inst{15-0}  = I2;
 }
 
+class InstRIEb<bits<16> op, dag outs, dag ins, string asmstr, list<dag> pattern>
+  : InstSystemZ<6, outs, ins, asmstr, pattern> {
+  field bits<48> Inst;
+  field bits<48> SoftFail = 0;
+
+  bits<4> R1;
+  bits<4> R2;
+  bits<4> M3;
+  bits<16> RI4;
+
+  let Inst{47-40} = op{15-8};
+  let Inst{39-36} = R1;
+  let Inst{35-32} = R2;
+  let Inst{31-16} = RI4;
+  let Inst{15-12} = M3;
+  let Inst{11-8}  = 0;
+  let Inst{7-0}   = op{7-0};
+}
+
 class InstRIEf<bits<16> op, dag outs, dag ins, string asmstr, list<dag> pattern>
   : InstSystemZ<6, outs, ins, asmstr, pattern> {
   field bits<48> Inst;
diff --git a/lib/Target/SystemZ/SystemZInstrInfo.cpp b/lib/Target/SystemZ/SystemZInstrInfo.cpp
index 6296e4a480..dcce5a7b7f 100644
--- a/lib/Target/SystemZ/SystemZInstrInfo.cpp
+++ b/lib/Target/SystemZ/SystemZInstrInfo.cpp
@@ -132,6 +132,10 @@ bool SystemZInstrInfo::AnalyzeBranch(MachineBasicBlock &MBB,
     if (!Branch.Target->isMBB())
       return true;
 
+    // Punt on compound branches.
+    if (Branch.Type != SystemZII::BranchNormal)
+      return true;
+
     if (Branch.CCMask == SystemZ::CCMASK_ANY) {
       // Handle unconditional branches.
       if (!AllowModify) {
@@ -361,11 +365,21 @@ SystemZInstrInfo::getBranchInfo(const MachineInstr *MI) const {
   case SystemZ::BR:
   case SystemZ::J:
   case SystemZ::JG:
-    return SystemZII::Branch(SystemZ::CCMASK_ANY, &MI->getOperand(0));
+    return SystemZII::Branch(SystemZII::BranchNormal, SystemZ::CCMASK_ANY,
+                             &MI->getOperand(0));
 
   case SystemZ::BRC:
   case SystemZ::BRCL:
-    return SystemZII::Branch(MI->getOperand(0).getImm(), &MI->getOperand(1));
+    return SystemZII::Branch(SystemZII::BranchNormal,
+                             MI->getOperand(0).getImm(), &MI->getOperand(1));
+
+  case SystemZ::CRJ:
+    return SystemZII::Branch(SystemZII::BranchC, MI->getOperand(2).getImm(),
+                             &MI->getOperand(3));
+
+  case SystemZ::CGRJ:
+    return SystemZII::Branch(SystemZII::BranchCG, MI->getOperand(2).getImm(),
+                             &MI->getOperand(3));
 
   default:
     llvm_unreachable("Unrecognized branch opcode");
@@ -426,6 +440,17 @@ unsigned SystemZInstrInfo::getOpcodeForOffset(unsigned Opcode,
   return 0;
 }
 
+unsigned SystemZInstrInfo::getCompareAndBranch(unsigned Opcode) const {
+  switch (Opcode) {
+  case SystemZ::CR:
+    return SystemZ::CRJ;
+  case SystemZ::CGR:
+    return SystemZ::CGRJ;
+  default:
+    return 0;
+  }
+}
+
 void SystemZInstrInfo::loadImmediate(MachineBasicBlock &MBB,
                                      MachineBasicBlock::iterator MBBI,
                                      unsigned Reg, uint64_t Value) const {
diff --git a/lib/Target/SystemZ/SystemZInstrInfo.h b/lib/Target/SystemZ/SystemZInstrInfo.h
index 322219c52f..e4a984025f 100644
--- a/lib/Target/SystemZ/SystemZInstrInfo.h
+++ b/lib/Target/SystemZ/SystemZInstrInfo.h
@@ -42,16 +42,32 @@ namespace SystemZII {
     // @GOT (aka @GOTENT)
     MO_GOT = (1 << 0)
   };
+  // Classifies a branch.
+  enum BranchType {
+    // An instruction that branches on the current value of CC.
+    BranchNormal,
+
+    // An instruction that peforms a 32-bit signed comparison and branches
+    // on the result.
+    BranchC,
+
+    // An instruction that peforms a 64-bit signed comparison and branches
+    // on the result.
+    BranchCG
+  };
   // Information about a branch instruction.
   struct Branch {
+    // The type of the branch.
+    BranchType Type;
+
     // CCMASK_<N> is set if the branch should be taken when CC == N.
     unsigned CCMask;
 
     // The target of the branch.
     const MachineOperand *Target;
 
-    Branch(unsigned ccMask, const MachineOperand *target)
-      : CCMask(ccMask), Target(target) {}
+    Branch(BranchType type, unsigned ccMask, const MachineOperand *target)
+      : Type(type), CCMask(ccMask), Target(target) {}
   };
 }
 
@@ -125,6 +141,10 @@ public:
   // exists.
   unsigned getOpcodeForOffset(unsigned Opcode, int64_t Offset) const;
 
+  // If Opcode is a COMPARE opcode for which an associated COMPARE AND
+  // BRANCH exists, return the opcode for the latter, otherwise return 0.
+  unsigned getCompareAndBranch(unsigned Opcode) const;
+
   // Emit code before MBBI in MI to move immediate value Value into
   // physical register Reg.
   void loadImmediate(MachineBasicBlock &MBB,
diff --git a/lib/Target/SystemZ/SystemZInstrInfo.td b/lib/Target/SystemZ/SystemZInstrInfo.td
index a27d62bcf4..bc3997b857 100644
--- a/lib/Target/SystemZ/SystemZInstrInfo.td
+++ b/lib/Target/SystemZ/SystemZInstrInfo.td
@@ -58,25 +58,52 @@ let isBranch = 1, isTerminator = 1, isBarrier = 1, R1 = 15 in {
 // in their raw BRC/BRCL form, with the 4-bit condition-code mask being
 // the first operand.  It seems friendlier to use mnemonic forms like
 // JE and JLH when writing out the assembly though.
-multiclass CondBranches<Operand imm, string short, string long> {
+//
+// Using a custom inserter for BRC gives us a chance to convert the BRC
+// and a preceding compare into a single compare-and-branch instruction.
+// The inserter makes no change in cases where a separate branch really
+// is needed.
+multiclass CondBranches<Operand ccmask, string short, string long> {
   let isBranch = 1, isTerminator = 1, Uses = [CC] in {
-    def "" : InstRI<0xA74, (outs), (ins imm:$R1, brtarget16:$I2), short, []>;
-    def L  : InstRIL<0xC04, (outs), (ins imm:$R1, brtarget32:$I2), long, []>;
+    def "" : InstRI<0xA74, (outs), (ins ccmask:$R1, brtarget16:$I2), short, []>;
+    def L  : InstRIL<0xC04, (outs), (ins ccmask:$R1, brtarget32:$I2), long, []>;
   }
 }
-let isCodeGenOnly = 1 in
+let isCodeGenOnly = 1, usesCustomInserter = 1 in
   defm BRC : CondBranches<cond4, "j$R1\t$I2", "jg$R1\t$I2">;
 defm AsmBRC : CondBranches<uimm8zx4, "brc\t$R1, $I2", "brcl\t$R1, $I2">;
 
 def : Pat<(z_br_ccmask cond4:$cond, bb:$dst), (BRC cond4:$cond, bb:$dst)>;
 
-// Define AsmParser mnemonics for each condition code.
-multiclass CondExtendedMnemonic<bits<4> Cond, string name> {
-  let R1 = Cond in {
-    def "" : InstRI<0xA74, (outs), (ins brtarget16:$I2),
-                    "j"##name##"\t$I2", []>;
+// Fused compare-and-branch instructions.  As for normal branches,
+// we handle these instructions internally in their raw CRJ-like form,
+// but use assembly macros like CRJE when writing them out.
+//
+// These instructions do not use or clobber the condition codes.
+// We nevertheless pretend that they clobber CC, so that we can lower
+// them to separate comparisons and BRCLs if the branch ends up being
+// out of range.
+multiclass CompareBranches<Operand ccmask, string pos1, string pos2> {
+  let isBranch = 1, isTerminator = 1, Defs = [CC] in {
+    def RJ  : InstRIEb<0xEC76, (outs), (ins GR32:$R1, GR32:$R2, ccmask:$M3,
+                                            brtarget16:$RI4),
+                       "crj"#pos1#"\t$R1, $R2, "#pos2#"$RI4", []>;
+    def GRJ : InstRIEb<0xEC64, (outs), (ins GR64:$R1, GR64:$R2, ccmask:$M3,
+                                            brtarget16:$RI4),
+                       "cgrj"#pos1#"\t$R1, $R2, "#pos2#"$RI4", []>;
+  }
+}
+let isCodeGenOnly = 1 in
+  defm C : CompareBranches<cond4, "$M3", "">;
+defm AsmC : CompareBranches<uimm8zx4, "", "$M3, ">;
+
+// Define AsmParser mnemonics for each general condition-code mask
+// (integer or floating-point)
+multiclass CondExtendedMnemonic<bits<4> ccmask, string name> {
+  let R1 = ccmask in {
+    def "" : InstRI<0xA74, (outs), (ins brtarget16:$I2), "j"#name#"\t$I2", []>;
     def L  : InstRIL<0xC04, (outs), (ins brtarget32:$I2),
-                    "jg"##name##"\t$I2", []>;
+                     "jg"#name#"\t$I2", []>;
   }
 }
 defm AsmJO   : CondExtendedMnemonic<1,  "o">;
@@ -94,6 +121,35 @@ defm AsmJLE  : CondExtendedMnemonic<12, "le">;
 defm AsmJNH  : CondExtendedMnemonic<13, "nh">;
 defm AsmJNO  : CondExtendedMnemonic<14, "no">;
 
+// Define AsmParser mnemonics for each integer condition-code mask.
+// This is like the list above, except that condition 3 is not possible
+// and that the low bit of the mask is therefore always 0.  This means
+// that each condition has two names.  Conditions "o" and "no" are not used.
+//
+// We don't make one of the two names an alias of the other because
+// we need the custom parsing routines to select the correct register class.
+multiclass IntCondExtendedMnemonicA<bits<4> ccmask, string name> {
+  let M3 = ccmask in {
+    def CR  : InstRIEb<0xEC76, (outs), (ins GR32:$R1, GR32:$R2,
+                                            brtarget16:$RI4),
+                       "crj"##name##"\t$R1, $R2, $RI4", []>;
+    def CGR : InstRIEb<0xEC64, (outs), (ins GR64:$R1, GR64:$R2,
+                                            brtarget16:$RI4),
+                       "cgrj"##name##"\t$R1, $R2, $RI4", []>;
+  }
+}
+multiclass IntCondExtendedMnemonic<bits<4> ccmask, string name1, string name2>
+  : IntCondExtendedMnemonicA<ccmask, name1> {
+  let isAsmParserOnly = 1 in
+    defm Alt : IntCondExtendedMnemonicA<ccmask, name2>;
+}
+defm AsmJH   : IntCondExtendedMnemonic<2,  "h",  "nle">;
+defm AsmJL   : IntCondExtendedMnemonic<4,  "l",  "nhe">;
+defm AsmJLH  : IntCondExtendedMnemonic<6,  "lh", "ne">;
+defm AsmJE   : IntCondExtendedMnemonic<8,  "e",  "nlh">;
+defm AsmJHE  : IntCondExtendedMnemonic<10, "he", "nl">;
+defm AsmJLE  : IntCondExtendedMnemonic<12, "le", "nh">;
+
 def Select32 : SelectWrapper<GR32>;
 def Select64 : SelectWrapper<GR64>;
 
diff --git a/lib/Target/SystemZ/SystemZLongBranch.cpp b/lib/Target/SystemZ/SystemZLongBranch.cpp
index 9db4f2d600..2fc85f50f0 100644
--- a/lib/Target/SystemZ/SystemZLongBranch.cpp
+++ b/lib/Target/SystemZ/SystemZLongBranch.cpp
@@ -151,6 +151,7 @@ namespace {
     bool mustRelaxBranch(const TerminatorInfo &Terminator, uint64_t Address);
     bool mustRelaxABranch();
     void setWorstCaseAddresses();
+    void splitCompareBranch(MachineInstr *MI, unsigned CompareOpcode);
     void relaxBranch(TerminatorInfo &Terminator);
     void relaxBranches();
 
@@ -220,6 +221,14 @@ TerminatorInfo SystemZLongBranch::describeTerminator(MachineInstr *MI) {
       // Relaxes to BRCL, which is 2 bytes longer.
       Terminator.ExtraRelaxSize = 2;
       break;
+    case SystemZ::CRJ:
+      // Relaxes to a CR/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.
+      Terminator.ExtraRelaxSize = 4;
+      break;
     default:
       llvm_unreachable("Unrecognized branch instruction");
     }
@@ -319,6 +328,23 @@ void SystemZLongBranch::setWorstCaseAddresses() {
   }
 }
 
+// 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))
+    .addOperand(MI->getOperand(2))
+    .addOperand(MI->getOperand(3));
+  // The implicit use of CC is a killing use.
+  BRCL->getOperand(2).setIsKill();
+  MI->eraseFromParent();
+}
+
 // Relax the branch described by Terminator.
 void SystemZLongBranch::relaxBranch(TerminatorInfo &Terminator) {
   MachineInstr *Branch = Terminator.Branch;
@@ -329,6 +355,12 @@ void SystemZLongBranch::relaxBranch(TerminatorInfo &Terminator) {
   case SystemZ::BRC:
     Branch->setDesc(TII->get(SystemZ::BRCL));
     break;
+  case SystemZ::CRJ:
+    splitCompareBranch(Branch, SystemZ::CR);
+    break;
+  case SystemZ::CGRJ:
+    splitCompareBranch(Branch, SystemZ::CGR);
+    break;
   default:
     llvm_unreachable("Unrecognized branch");
   }