[PowerPC] Eliminate compares - add handling for logical operations without the use of condition registers

[nemanjai]

Summary

This adds the code gen and testing for logical operations on i1 values without using condition registers (when possible).
It handles:

• logical operations with SETCC inputs
• logical operations with TRUNCATE inputs
• logical operations with logical operations as inputs
• zero extensions of logical operations on i1 values (as above)

[nemanjai]

lib/Target/PowerPC/PPCISelDAGToDAG.cpp

2560–2677

These two variables were erroneously left in after I refactored the code to not need them. They'll be removed on the commit.

[nemanjai]

This is a significantly scoped-down version of this patch to make it more manageable for review. It simply extends the use of the existing handling of ISD::SETCC in GPRs to their uses in logic operations (AND/OR/XOR).

Furthermore, this adds a restriction to the SETCC handling to only perform the expansion if all the uses need the value in a GPR since doing the expansion in such a situation would be a net addition of instructions without being able to eliminate the compare instruction.

[echristo]

A few inline comments, a couple of refactorings and some cleanup, otherwise looks OK.

One other comment: This is starting to feel like we're doing all of isel in C++ in the backend. I'd like to look at being able to do as much of this in generic code as possible. Perhaps take a look and see what we can manage that way and a comment at some point before all of this in the source?

Thanks!

lib/Target/PowerPC/PPCISelDAGToDAG.cpp

2511

Comment?

2569

bool operand :)

2578

The naming convention here is a little hard to parse later on. I'm seeing IsNot as !a and not a ^ -1...

2609

Maybe call them LHS and RHS? :)

2662

Needs the same commentary as the previous patch.

2814

Description?

2850

This should probably be an earlier return before you do the work above?

3207

fallthrough?

[nemanjai]

lib/Target/PowerPC/PPCISelDAGToDAG.cpp

3207

Ah good catch. I missed that. Thanks.

[nemanjai]

Addressed comments to add some documentation, remove a bool parameter and add the missing break in the switch.

[echristo]

lib/Target/PowerPC/PPCISelDAGToDAG.cpp

280

Part of asking for the enum is wondering why it's necessary. It seems odd to say "getLogicOpInGPR" to want to know whether or not to put something in a GPR.

[nemanjai]

lib/Target/PowerPC/PPCISelDAGToDAG.cpp

280

That's a good point. Perhaps the naming is a poor choice. I could rename it to performLogicOpInGPR().
The idea would be to convey the fact that this simply defers moving the data out of a GPR. What it does is take something like:
(and (i1 (setcc %a, %b, CC), (setcc %c, %d, CC2))) and convert it to a sequence that does the comparisons and the logical operation in a GPR.
That of course still leaves the question of whether we want the result of the logical operation itself to stay in a GPR (for further extended operations) or to be moved out to a CR (for use in branches, ISEL, etc.).

So I think maybe renaming the function and/or providing a clearer comment as to what's happening might be the right choice here. What do you think?

[echristo]

lib/Target/PowerPC/PPCISelDAGToDAG.cpp

280

I'd probably just separate out the performLogicOptInGPR and then just add code where you'd pass the bool argument to pull it into a CR if you need it after the call?

[nemanjai]

This revision does away with the Boolean parameter to getLogicOpInGPR and adds the logic to extract the CR result at the only call of that function that needs it.
Furthermore, this patch eliminates bitwise negations if they're produced by instructions that have a record-form.

[echristo]

couple of inline comments.

lib/Target/PowerPC/PPCISelDAGToDAG.cpp

2569

Maybe "computeLogicOpInGPR"?

2700–2702

I think you mean "single bit" rather than "CR bit" at least I'm reading it that way rather than in a cc register right?

[nemanjai]

lib/Target/PowerPC/PPCISelDAGToDAG.cpp

2569

Will do.

2700–2702

We have produced a record-form machine node above. The code immediately after this comment actually gets a single bit out of CR0 (which was set by the record-form op) and selects this logical operation to that bit. So it is a single bit, but it is in a CR - CR0 to be specific.
Perhaps it is clearer if I set the comment to this:

// Select this node to a single bit from CR0 set by the record-form node
// just created. For bitwise negation, use the EQ bit which is the equivalent
// of negating the result (i.e. it is a bit set when the result of the operation
// is zero).

[nemanjai]

Address cosmetic comments - name change and line comment.

[echristo]

SGTM. It still seems a bit overly complicated, but I don't think there's anything for it at the moment.

lib/Target/PowerPC/PPCISelDAGToDAG.cpp

2700–2702

SGTM.

lib/Target/PowerPC/PPCISelDAGToDAG.cpp

 STATISTIC(NumSextSetcc,
           "Number of (sext(setcc)) nodes expanded into GPR sequence.");
 STATISTIC(NumZextSetcc,
           "Number of (zext(setcc)) nodes expanded into GPR sequence.");
 STATISTIC(SignExtensionsAdded,
           "Number of sign extensions for compare inputs added.");
 STATISTIC(ZeroExtensionsAdded,
           "Number of zero extensions for compare inputs added.");
+STATISTIC(NumLogicOpsOnComparison,
+          "Number of logical ops on i1 values calculated in GPR.");
+STATISTIC(OmittedForNonExtendUses,
+          "Number of compares not eliminated as they have non-extending uses.");
+
 // FIXME: Remove this once the bug has been fixed!
 cl::opt<bool> ANDIGlueBug("expose-ppc-andi-glue-bug",
 cl::desc("expose the ANDI glue bug on PPC"), cl::Hidden);
 
 static cl::opt<bool>
     UseBitPermRewriter("ppc-use-bit-perm-rewriter", cl::init(true),
                        cl::desc("use aggressive ppc isel for bit permutations"),
                        cl::Hidden);
private:
 
     // Modifiers to guide how an ISD::SETCC node's result is to be computed
     // in a GPR.
     // ZExtOrig - use the original condition code, zero-extend value
     // ZExtInvert - invert the condition code, zero-extend value
     // SExtOrig - use the original condition code, sign-extend value
     // SExtInvert - invert the condition code, sign-extend value
     enum SetccInGPROpts { ZExtOrig, ZExtInvert, SExtOrig, SExtInvert };
 
     bool trySETCC(SDNode *N);
     bool tryEXTEND(SDNode *N);
+    bool tryLogicOpOfCompares(SDNode *N);
+    SDValue getLogicOpInGPR(SDValue LogicOp, bool KeepInGPR);
     SDValue signExtendInputIfNeeded(SDValue Input);
     SDValue zeroExtendInputIfNeeded(SDValue Input);
     SDValue addExtOrTrunc(SDValue NatWidthRes, ExtOrTruncConversion Conv);
     SDValue get32BitZExtCompare(SDValue LHS, SDValue RHS, ISD::CondCode CC,
                                 int64_t RHSValue, SDLoc dl);
     SDValue get32BitSExtCompare(SDValue LHS, SDValue RHS, ISD::CondCode CC,
                                 int64_t RHSValue, SDLoc dl);
     SDValue getSETCCInGPR(SDValue Compare, SetccInGPROpts ConvOpts);
bool PPCDAGToDAGISel::trySETCC(SDNode *N) {
 
   // Get the specified bit.
   SDValue Tmp =
     SDValue(CurDAG->getMachineNode(PPC::RLWINM, dl, MVT::i32, Ops), 0);
   CurDAG->SelectNodeTo(N, PPC::XORI, MVT::i32, Tmp, getI32Imm(1, dl));
   return true;
 }
 
+static bool isLogicOp(unsigned Opc) {
+  return Opc == ISD::AND || Opc == ISD::OR || Opc == ISD::XOR;
+}
+
 /// If this node is a sign/zero extension of an integer comparison,
 /// it can usually be computed in GPR's rather than using comparison
 /// instructions and ISEL. We only do this on 64-bit targets for now
 /// as the code is specialized for 64-bit (it uses 64-bit instructions
 /// and assumes 64-bit registers).
 bool PPCDAGToDAGISel::tryEXTEND(SDNode *N) {
   if (TM.getOptLevel() == CodeGenOpt::None || !TM.isPPC64())
     return false;
   assert((N->getOpcode() == ISD::ZERO_EXTEND ||
           N->getOpcode() == ISD::SIGN_EXTEND) &&
           "Expecting a zero/sign extend node!");
 
-  if (N->getOperand(0).getOpcode() != ISD::SETCC)
+  SDValue WideRes;
+  // If we are zero-extending the result of a logical operation on i1
+  // values, we can keep the values in GPRs.
+  if (isLogicOp(N->getOperand(0).getOpcode()) &&
+      N->getOperand(0).getValueType() == MVT::i1 &&
+      N->getOpcode() == ISD::ZERO_EXTEND)
+    WideRes = getLogicOpInGPR(N->getOperand(0), true);
+  else if (N->getOperand(0).getOpcode() != ISD::SETCC)
     return false;
-
-  SDValue WideRes =
+  else
+    WideRes =
       getSETCCInGPR(N->getOperand(0),
                     N->getOpcode() == ISD::SIGN_EXTEND ?
                     SetccInGPROpts::SExtOrig : SetccInGPROpts::ZExtOrig);
 
   if (!WideRes)
     return false;
 
   SDLoc dl(N);
   bool Inputs32Bit = N->getOperand(0).getOperand(0).getValueType() == MVT::i32;
   bool Output32Bit = N->getValueType(0) == MVT::i32;
 
   NumSextSetcc += N->getOpcode() == ISD::SIGN_EXTEND ? 1 : 0;
   NumZextSetcc += N->getOpcode() == ISD::SIGN_EXTEND ? 0 : 1;
 
   SDValue ConvOp = WideRes;
   if (Inputs32Bit != Output32Bit)
     ConvOp = addExtOrTrunc(WideRes, Inputs32Bit ? ExtOrTruncConversion::Ext :
                            ExtOrTruncConversion::Trunc);
   ReplaceNode(N, ConvOp.getNode());
 
   return true;
 }
 
+// Lower a logical operation on i1 values into a GPR sequence if possible.
+// The result can be kept in a GPR if requested.
+// Three types of inputs can be handled:
+// - SETCC
+// - TRUNCATE
+// - Logical operation (AND/OR/XOR)
+// There is also a special case that is handled (namely a complement operation
+// achieved with xor %a, -1).
+SDValue PPCDAGToDAGISel::getLogicOpInGPR(SDValue LogicOp, bool KeepInGPR) {
+  assert(isLogicOp(LogicOp.getOpcode()) &&
+         "Can only handle logic operations here.");
+  assert(LogicOp.getValueType() == MVT::i1 &&
+         "Can only handle logic operations on i1 values here.");
+  SDLoc dl(LogicOp);
+  SDValue Op1, Op2;
+
+  // Special case: xor %a, -1
+  bool IsNot = isBitwiseNot(LogicOp);
+
+  // Produces a GPR sequence for each operand of the binary logic operation.
+  // For SETCC, it produces the respective comparison, for TRUNCATE it truncates
+  // the value in a GPR and for logic operations, it will recursively produce
+  // a GPR sequence for the operation.
+  auto getLogicOperand = [&] (SDValue Operand) -> SDValue {
+    unsigned OperandOpcode = Operand.getOpcode();
+    if (OperandOpcode == ISD::SETCC)
+      return getSETCCInGPR(Operand, SetccInGPROpts::ZExtOrig);
+    else if (OperandOpcode == ISD::TRUNCATE) {
+      SDValue InputOp = Operand.getOperand(0);
+      EVT InVT = InputOp.getValueType();
+      // If this is a (xor (trunc to i1), -1), no need to truncate twice.
+      if (IsNot && !KeepInGPR)
+        return InVT == MVT::i64 ? InputOp :
+          addExtOrTrunc(InputOp, ExtOrTruncConversion::Ext);
+      return
+        SDValue(CurDAG->getMachineNode(InVT == MVT::i32 ? PPC::RLDICL_32 :
+                                       PPC::RLDICL, dl, InVT, InputOp,
+                                       getI64Imm(0, dl), getI64Imm(63, dl)), 0);
+    } else if (isLogicOp(OperandOpcode))
+      return getLogicOpInGPR(Operand, true);
+    return SDValue();
+  };
+  Op1 = getLogicOperand(LogicOp.getOperand(0));
+  Op2 = getLogicOperand(LogicOp.getOperand(1));
+
+  // If a GPR sequence can't be produced for the LHS we can't proceed.
+  // Not producing a GPR sequence for the RHS is only a problem if this isn't
+  // a bitwise negation operation.
+  if (!Op1 || (!Op2 && !IsNot))
+    return SDValue();
+
+  NumLogicOpsOnComparison++;
+
+  // We will use the inputs as 64-bit values.
+  if (Op1.getValueType() == MVT::i32)
+    Op1 = addExtOrTrunc(Op1, ExtOrTruncConversion::Ext);
+  if (!IsNot && Op2.getValueType() == MVT::i32)
+    Op2 = addExtOrTrunc(Op2, ExtOrTruncConversion::Ext);
+
+  unsigned NewOpc;
+  switch (LogicOp.getOpcode()) {
+  default: llvm_unreachable("Unknown logic operation.");
+  case ISD::AND: NewOpc = KeepInGPR ? PPC::AND8 : PPC::AND8o; break;
+  case ISD::OR:  NewOpc = KeepInGPR ? PPC::OR8  : PPC::OR8o;  break;
+  case ISD::XOR: NewOpc = KeepInGPR ? PPC::XOR8 : PPC::XOR8o; break;
+  }
+
+  SDValue CR0Reg = CurDAG->getRegister(PPC::CR0, MVT::i32);
+  // We can negate an i1 value (in a GPR) by clearing the top 63 bits and using
+  // the EQ bit. If we had a zero in the least significant bit, the result is
+  // zero and the EQ bit is set. Otherwise, it isn't set.
+  if (IsNot) {
+    if (!KeepInGPR) {
+      SDValue WideOp =
+        SDValue(CurDAG->getMachineNode(PPC::RLDICLo, dl, MVT::i64, MVT::Glue,
+                                       Op1, getI64Imm(0, dl),
+                                       getI64Imm(63, dl)), 0);
+      SDValue SRIdxVal =
+        CurDAG->getTargetConstant(PPC::sub_eq, dl, MVT::i32);
+      return SDValue(CurDAG->getMachineNode(TargetOpcode::EXTRACT_SUBREG, dl,
+                                            MVT::i1, CR0Reg, SRIdxVal,
+                                            WideOp.getValue(1)), 0);
+    }
+    Op2 = getI64Imm(1, dl);
+    NewOpc = PPC::XORI8;
+  }
+
+  if (KeepInGPR)
+    return SDValue(CurDAG->getMachineNode(NewOpc, dl, MVT::i64, Op1, Op2), 0);
+
+  SDValue WideOp =
+    SDValue(CurDAG->getMachineNode(NewOpc, dl, MVT::i64, MVT::Glue, Op1,
+                                   Op2), 0);
+  SDValue SRIdxVal =
+    CurDAG->getTargetConstant(PPC::sub_gt, dl, MVT::i32);
+  return SDValue(CurDAG->getMachineNode(TargetOpcode::EXTRACT_SUBREG, dl,
+                                        MVT::i1, CR0Reg, SRIdxVal,
+                                        WideOp.getValue(1)), 0);
+}
+
+bool PPCDAGToDAGISel::tryLogicOpOfCompares(SDNode *N) {
+  if (TM.getOptLevel() == CodeGenOpt::None || !TM.isPPC64())
+    return false;
+  SDLoc dl(N);
+  if (N->getValueType(0) != MVT::i1)
+    return false;
+  assert(isLogicOp(N->getOpcode()) &&
+         "Expected a logic operation on setcc results.");
+  SDValue LoweredLogical = getLogicOpInGPR(SDValue(N, 0), false);
+  if (!LoweredLogical)
+    return false;
+
+  ReplaceNode(N, LoweredLogical.getNode());
+  return true;
+}
+
 /// If the value isn't guaranteed to be sign-extended to 64-bits, extend it.
 /// Useful when emitting comparison code for 32-bit values without using
 /// the compare instruction (which only considers the lower 32-bits).
 SDValue PPCDAGToDAGISel::signExtendInputIfNeeded(SDValue Input) {
   assert(Input.getValueType() == MVT::i32 &&
          "Can only sign-extend 32-bit values here.");
   unsigned Opc = Input.getOpcode();
 
   // The value was sign extended and then truncated to 32-bits. No need to
   // sign extend it again.
   if (Opc == ISD::TRUNCATE &&
       (Input.getOperand(0).getOpcode() == ISD::AssertSext ||
        Input.getOperand(0).getOpcode() == ISD::SIGN_EXTEND))
     return Input;
 
   LoadSDNode *InputLoad = dyn_cast<LoadSDNode>(Input);
   // The input is a sign-extending load. No reason to sign-extend.
   if (InputLoad && InputLoad->getExtensionType() == ISD::SEXTLOAD)
     return Input;
 
   ConstantSDNode *InputConst = dyn_cast<ConstantSDNode>(Input);
   // We don't sign-extend constants and already sign-extended values.
   if (InputConst || Opc == ISD::AssertSext || Opc == ISD::SIGN_EXTEND_INREG ||
       Opc == ISD::SIGN_EXTEND)
     return Input;
 
   SDLoc dl(Input);
   SignExtensionsAdded++;
   return SDValue(CurDAG->getMachineNode(PPC::EXTSW_32, dl, MVT::i32, Input), 0);
 }
 
 /// If the value isn't guaranteed to be zero-extended to 64-bits, extend it.
 /// Useful when emitting comparison code for 32-bit values without using
 /// the compare instruction (which only considers the lower 32-bits).
case ISD::SETEQ: {
     SDValue Sldi =
       SDValue(CurDAG->getMachineNode(PPC::RLDICR_32, dl, MVT::i32, SHLOps), 0);
     return SDValue(CurDAG->getMachineNode(PPC::SRADI_32, dl, MVT::i32, Sldi,
                                           getI32Imm(63, dl)), 0);
   }
   }
 }
 
+static bool allUsesExtend(SDValue Compare) {
+  if (Compare.hasOneUse())
+    return true;
+  for (auto CompareUse : Compare.getNode()->uses())
+    if (CompareUse->getOpcode() != ISD::SIGN_EXTEND &&
+        CompareUse->getOpcode() != ISD::ZERO_EXTEND &&
+        CompareUse->getOpcode() != ISD::SELECT &&
+        !isLogicOp(CompareUse->getOpcode())) {
+      OmittedForNonExtendUses++;
+      return false;
+    }
+  return true;
+}
+
 /// Returns an equivalent of a SETCC node but with the result the same width as
 /// the inputs. This can nalso be used for SELECT_CC if either the true or false
 /// values is a power of two while the other is zero.
 SDValue PPCDAGToDAGISel::getSETCCInGPR(SDValue Compare,
                                        SetccInGPROpts ConvOpts) {
   assert((Compare.getOpcode() == ISD::SETCC ||
           Compare.getOpcode() == ISD::SELECT_CC) &&
          "An ISD::SETCC node required here.");
 
   SDValue LHS = Compare.getOperand(0);
   SDValue RHS = Compare.getOperand(1);
 
   // The condition code is operand 2 for SETCC and operand 4 for SELECT_CC.
   int CCOpNum = Compare.getOpcode() == ISD::SELECT_CC ? 4 : 2;
   ISD::CondCode CC =
     cast<CondCodeSDNode>(Compare.getOperand(CCOpNum))->get();
   EVT InputVT = LHS.getValueType();
   if (InputVT != MVT::i32)
     return SDValue();
 
+  // Don't convert this comparison to a GPR sequence because there are uses
+  // of the i1 result (i.e. uses that require the result in the CR).
+  if ((Compare.getOpcode() == ISD::SETCC) && !allUsesExtend(Compare))
+    return SDValue();
+
   SDLoc dl(Compare);
   ConstantSDNode *RHSConst = dyn_cast<ConstantSDNode>(RHS);
   int64_t RHSValue = RHSConst ? RHSConst->getSExtValue() : INT64_MAX;
 
   if (ConvOpts == SetccInGPROpts::ZExtInvert ||
       ConvOpts == SetccInGPROpts::SExtInvert)
     CC = ISD::getSetCCInverse(CC, true);
 
if (Offset.getOpcode() == ISD::TargetConstant ||
           PPCLowering->getPointerTy(CurDAG->getDataLayout()), MVT::Other, Ops);
       transferMemOperands(N, MN);
       ReplaceNode(N, MN);
       return;
     }
   }
 
   case ISD::AND: {
+    if (tryLogicOpOfCompares(N))
+      return;
+
     unsigned Imm, Imm2, SH, MB, ME;
     uint64_t Imm64;
 
     // If this is an and of a value rotated between 0 and 31 bits and then and'd
     // with a mask, emit rlwinm
     if (isInt32Immediate(N->getOperand(1), Imm) &&
         isRotateAndMask(N->getOperand(0).getNode(), Imm, false, SH, MB, ME)) {
       SDValue Val = N->getOperand(0).getOperand(0);
case ISD::AND: {
     // Other cases are autogenerated.
     break;
   }
   case ISD::OR: {
     if (N->getValueType(0) == MVT::i32)
       if (tryBitfieldInsert(N))
         return;
 
+    if (tryLogicOpOfCompares(N))
+      return;
+
     short Imm;
     if (N->getOperand(0)->getOpcode() == ISD::FrameIndex &&
         isIntS16Immediate(N->getOperand(1), Imm)) {
       KnownBits LHSKnown;
       CurDAG->computeKnownBits(N->getOperand(0), LHSKnown);
 
       // If this is equivalent to an add, then we can fold it with the
       // FrameIndex calculation.
       if ((LHSKnown.Zero.getZExtValue()|~(uint64_t)Imm) == ~0ULL) {
         selectFrameIndex(N, N->getOperand(0).getNode(), (int)Imm);
         return;
       }
     }
 
     // Other cases are autogenerated.
     break;
   }
+  case ISD::XOR: {
+    if (tryLogicOpOfCompares(N))
+      return;
+  }
   case ISD::ADD: {
     short Imm;
     if (N->getOperand(0)->getOpcode() == ISD::FrameIndex &&
         isIntS16Immediate(N->getOperand(1), Imm)) {
       selectFrameIndex(N, N->getOperand(0).getNode(), (int)Imm);
       return;
     }
 

test/CodeGen/PowerPC/logic-ops-on-compares.ll

+; RUN: llc -verify-machineinstrs -mtriple=powerpc64-unknown-linux-gnu -O2 \
+; RUN:   -ppc-asm-full-reg-names -mcpu=pwr8 < %s | FileCheck %s \
+; RUN:  --implicit-check-not cmpw --implicit-check-not cmpd --implicit-check-not cmpl
+; RUN: llc -verify-machineinstrs -mtriple=powerpc64le-unknown-linux-gnu -O2 \
+; RUN:   -ppc-asm-full-reg-names -mcpu=pwr8 < %s | FileCheck %s \
+; RUN:  --implicit-check-not cmpw --implicit-check-not cmpd --implicit-check-not cmpl
+
+; Function Attrs: nounwind
+define signext i32 @test(i32 signext %a, i32 signext %b, i32 signext %c) {
+; CHECK-LABEL: test:
+; CHECK:    xor r7, r3, r4
+; CHECK-NEXT:    li r6, 55
+; CHECK-NEXT:    xor r5, r5, r6
+; CHECK-NEXT:    or r7, r7, r4
+; CHECK-NEXT:    cntlzw r5, r5
+; CHECK-NEXT:    cntlzw r6, r7
+; CHECK-NEXT:    srwi r6, r6, 5
+; CHECK-NEXT:    srwi r5, r5, 5
+; CHECK-NEXT:    or. r5, r6, r5
+; CHECK-NEXT:    bc 4, 1, .LBB0_2
+entry:
+  %tobool = icmp eq i32 %a, %b
+  %tobool1 = icmp eq i32 %b, 0
+  %or.cond = and i1 %tobool, %tobool1
+  %tobool3 = icmp eq i32 %c, 55
+  %or.cond5 = or i1 %or.cond, %tobool3
+  br i1 %or.cond5, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  %call = tail call signext i32 @foo(i32 signext %a) #2
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %call4 = tail call signext i32 @bar(i32 signext %b) #2
+  br label %return
+
+return:                                           ; preds = %if.end, %if.then
+  %retval.0 = phi i32 [ %call4, %if.end ], [ %call, %if.then ]
+  ret i32 %retval.0
+}
+declare signext i32 @foo(i32 signext)
+declare signext i32 @bar(i32 signext)