[PPC][DAGCombine] Convert SETCC to subtract when the result is zero extended

[amehsan]

Summary

The code here can be extended. I post this patch right now, to get some feedback before adding those extensions.

When we see a SETCC whose only users are zero extend operations, we can replace it with a subtraction. This results in doing all calculation in GPRs and avoids CR use.

Extensions that I plan to look into:

1- Check if this works for any_extend/sign extend
2- Implement similar change for signed condition codes.
3- Look into handling equal and not equal cases, using cntlz
4- More tests should be added

Please let me know if there are other ways for extending this.

[nemanjai]

lib/Target/PowerPC/PPCISelLowering.cpp

9920

I'm not sure why the variable names are lowercase here.

9922

I think some sort of assert is in order here to ensure this function is called with the correct type of node.

9932

Could the expression size - 1 ever be zero, thereby making this a redundant shift operation?

9946

Perhaps a comment describing why it's not valid to do this prior to legalization.

9957

I think an assert should be added somewhere in this function as well to make sure you have the right node type or else this may trip an assert in a location that will make it difficult to debug.

9958

Do we really need this much indirection? Is there not a getValueType() member function in the SDValue operand? Will SDValue::getValueSizeInBits() not produce the right value?

9960

Shouldn't there be a check somewhere to ensure we're not in 32-bit mode?

[kbarton]

lib/Target/PowerPC/PPCISelLowering.cpp

9920

Need comments here about the logic and what the assumptions are in terms of input parameters, etc.

9957

Some guidelines on the types of casts that can be used are here: http://llvm.org/docs/ProgrammersManual.html#the-isa-cast-and-dyn-cast-templates

It's probably good to pick one, and then either put the appropriate checks earlier, or make sure to add comments stating it is assumed this is only called with nodes of a specific type.

[amehsan]

This comment has been deleted.

[amehsan]

lib/Target/PowerPC/PPCISelLowering.cpp

9920

Will fix lower case var names.

9920

Will add comments.

9922

Will add

9932

No, this is going to be the size of largest legal integer.

9946

Will add

9957

Yes, this function is only called for ISD::SETCC. Will add more comments and assertions.

9958

Yes, I think SDValue::getValueSizeInBits will do what I need.

9960

This should be taken from DataLayout object. Will fix that.

[amehsan]

There is one comment not yet addressed. Size of latest legal integer is currently hardcoded. As I responded to that comment I will fix it. I want to look at this a bit more to see if it makes sense to add some extensions to it.

I have added more comments, so hopefully the code will be more clear.

[nemanjai]

lib/Target/PowerPC/PPCISelLowering.cpp

9946

I'm just curious why we don't see this shift in the test.

test/CodeGen/PowerPC/setcc-to-sub.ll

41

I'm kind of thinking that this should be a slightly stronger test - to show that the operands are swapped on the sub. The base register for the two loads is known, so maybe that can be used.

43

I don't think this is guaranteed to be R3 until the next instruction.

48

I think for completeness, you should include tests for the other two condition codes.

[amehsan]

Thanks Nemanja for comments on the testcase.

I will revise the tests according to your comments. This patch originally being a draft to get feedback on the optimization approach, was not meant to provide finalized and exhaustive test.

[amehsan]

lib/Target/PowerPC/PPCISelLowering.cpp

9946

That should be an oversight. I will add this. I think I probably use CHECK-NEXT to make sure all the sequence is there.

test/CodeGen/PowerPC/setcc-to-sub.ll

41

Will look into it.

43

That is correct. Will change it. (Even though I hope our register allocation never makes that mistake :)

48

Sure . Will do.

[amehsan]

Completed the unit test and code. I decided that extending this for signed comparison is not necessary good, because two zero extends that we generate for unsigned comparison, will be sign extension for signed comparison. That means the signed version will have two more instructions. There might be still more useful cases, but I think they are different enough and we don't need to make them part of this patch.

[amehsan]

Just finished lnt test and there are some failures. I will update when my investigation of the failures is done.

[amehsan]

now fully tested with test-suite.

[nemanjai]

lib/Target/PowerPC/PPCISelLowering.cpp

9925

s/GenerateEquivalentSub/generateEquivalentSub

[kbarton]

Aside from some minor formatting of comments, this LGTM.

lib/Target/PowerPC/PPCISelLowering.cpp

9924

doxygen-style comments please

lib/Target/PowerPC/PPCISelLowering.h

973

Can you please convert to doxygen-style comments?

test/CodeGen/PowerPC/setcc-to-sub.ll

2

Is there any reason this has to be run on pwr8?

[amehsan]

https://reviews.llvm.org/rL287329

lib/Target/PowerPC/PPCISelLowering.h

private:
     SDValue lowerEH_SJLJ_SETJMP(SDValue Op, SelectionDAG &DAG) const;
     SDValue lowerEH_SJLJ_LONGJMP(SDValue Op, SelectionDAG &DAG) const;
 
     SDValue DAGCombineExtBoolTrunc(SDNode *N, DAGCombinerInfo &DCI) const;
     SDValue DAGCombineBuildVector(SDNode *N, DAGCombinerInfo &DCI) const;
     SDValue DAGCombineTruncBoolExt(SDNode *N, DAGCombinerInfo &DCI) const;
     SDValue combineFPToIntToFP(SDNode *N, DAGCombinerInfo &DCI) const;
 
+    // This function looks at SETCC that compares integers. It replaces SETCC
+    // with integer subtraction when (1) there is a legal way of doing it.
+    // (2) keeping the result of comparison in GPR has some performance benefit.
+    SDValue ConvertSETCCToSubtract(SDNode *N, DAGCombinerInfo &DCI) const;
+
     SDValue getRsqrtEstimate(SDValue Operand, SelectionDAG &DAG, int Enabled,
                              int &RefinementSteps,
                              bool &UseOneConstNR) const override;
     SDValue getRecipEstimate(SDValue Operand, SelectionDAG &DAG, int Enabled,
                              int &RefinementSteps) const override;
     unsigned combineRepeatedFPDivisors() const override;
 
     CCAssignFn *useFastISelCCs(unsigned Flag) const;

lib/Target/PowerPC/PPCISelLowering.cpp

while (!Queue.empty()) {
             UI->getOpcode() == ISD::TokenFactor) && !Visited.count(*UI))
           Queue.push_back(*UI);
     }
   }
 
   return false;
 }
 
+
+// This function is called when we have proved that a SETCC node can be replaced
+// by subtraction (and other supporting instructions) so that the result of
+// comparison is kept in a GPR instead of CR. This function is purely for
+// codegen purposes and has some flags to guide the codegen process.
+static SDValue GenerateEquivalentSub(SDNode *N, int Size, bool Complement,
+                                     bool Swap, SDLoc &DL, SelectionDAG &DAG) {
+
+  assert(N->getOpcode() == ISD::SETCC && "ISD::SETCC Expected.");
+
+  // Zero extend the operands to the largest legal integer. Originally, they
+  // must be of a strictly smaller size.
+  auto Op0 = DAG.getNode(ISD::ZERO_EXTEND, DL, MVT::i64, N->getOperand(0),
+                         DAG.getConstant(Size, DL, MVT::i32));
+  auto Op1 = DAG.getNode(ISD::ZERO_EXTEND, DL, MVT::i64, N->getOperand(1),
+                         DAG.getConstant(Size, DL, MVT::i32));
+
+  // Swap if needed. Depends on the condition code.
+  if (Swap)
+    std::swap(Op0, Op1);
+
+  // Subtract extended integers.
+  auto SubNode = DAG.getNode(ISD::SUB, DL, MVT::i64, Op0, Op1);
+
+  // Move the sign bit to the least significant position and zero out the rest.
+  // Now the least significant bit carries the result of original comparison.
+  auto Shifted = DAG.getNode(ISD::SRL, DL, MVT::i64, SubNode,
+                             DAG.getConstant(Size - 1, DL, MVT::i32));
+  auto Final = Shifted;
+
+  // Complement the result if needed. Based on the condition code.
+  if (Complement)
+    Final = DAG.getNode(ISD::XOR, DL, MVT::i64, Shifted,
+                        DAG.getConstant(1, DL, MVT::i64));
+
+  return DAG.getNode(ISD::TRUNCATE, DL, MVT::i1, Final);
+}
+
+SDValue PPCTargetLowering::ConvertSETCCToSubtract(SDNode *N,
+                                                  DAGCombinerInfo &DCI) const {
+
+  assert(N->getOpcode() == ISD::SETCC && "ISD::SETCC Expected.");
+
+  SelectionDAG &DAG = DCI.DAG;
+  SDLoc DL(N);
+
+  // Size of integers being compared has a critical role in the following
+  // analysis, so we prefer to do this when all types are legal.
+  if (!DCI.isAfterLegalizeVectorOps())
+    return SDValue();
+
+  // If all users of SETCC extend its value to a legal integer type
+  // then we replace SETCC with a subtraction
+  for (SDNode::use_iterator UI = N->use_begin(),
+       UE = N->use_end(); UI != UE; ++UI) {
+    if (UI->getOpcode() != ISD::ZERO_EXTEND)
+      return SDValue();
+  }
+
+  ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(2))->get();
+  auto OpSize = N->getOperand(0).getValueSizeInBits();
+
+  unsigned Size = DAG.getDataLayout().getLargestLegalIntTypeSizeInBits();
+
+  if (OpSize < Size) {
+    switch (CC) {
+    default: break;
+    case ISD::SETULT:
+      return GenerateEquivalentSub(N, Size, false, false, DL, DAG);
+    case ISD::SETULE:
+      return GenerateEquivalentSub(N, Size, true, true, DL, DAG);
+    case ISD::SETUGT:
+      return GenerateEquivalentSub(N, Size, false, true, DL, DAG);
+    case ISD::SETUGE:
+      return GenerateEquivalentSub(N, Size, true, false, DL, DAG);
+    }
+  }
+
+  return SDValue();
+}
+
 SDValue PPCTargetLowering::DAGCombineTruncBoolExt(SDNode *N,
                                                   DAGCombinerInfo &DCI) const {
   SelectionDAG &DAG = DCI.DAG;
   SDLoc dl(N);
 
   assert(Subtarget.useCRBits() && "Expecting to be tracking CR bits");
   // If we're tracking CR bits, we need to be careful that we don't have:
   //   trunc(binary-ops(zext(x), zext(y)))
if (ISD::isSignedIntSetCC(CC)) {
       if (DAG.ComputeNumSignBits(N->getOperand(0)) != OpBits ||
           DAG.ComputeNumSignBits(N->getOperand(1)) != OpBits)
         return SDValue();
     } else if (ISD::isUnsignedIntSetCC(CC)) {
       if (!DAG.MaskedValueIsZero(N->getOperand(0),
                                  APInt::getHighBitsSet(OpBits, OpBits-1)) ||
           !DAG.MaskedValueIsZero(N->getOperand(1),
                                  APInt::getHighBitsSet(OpBits, OpBits-1)))
-        return SDValue();
+        return (N->getOpcode() == ISD::SETCC ? ConvertSETCCToSubtract(N, DCI)
+                                             : SDValue());
     } else {
       // This is neither a signed nor an unsigned comparison, just make sure
       // that the high bits are equal.
       APInt Op1Zero, Op1One;
       APInt Op2Zero, Op2One;
       DAG.computeKnownBits(N->getOperand(0), Op1Zero, Op1One);
       DAG.computeKnownBits(N->getOperand(1), Op2Zero, Op2One);
 

pzero-fp-xored.ll

-; RUN: llc -mtriple=powerpc-unknown-linux-gnu -mattr=+vsx < %s |  \
-; RUN:   FileCheck %s --implicit-check-not lxvd2x --implicit-check-not lfs
-; RUN: llc -mtriple=powerpc-unknown-linux-gnu -mattr=-vsx -mattr=-p8altivec < %s | \
-; RUN:   FileCheck %s --check-prefix=CHECK-NVSXP8A --implicit-check-not xxlxor \
-; RUN:                                             --implicit-check-not vxor
-
-define signext i32 @t1(float %x) local_unnamed_addr #0 {
-entry:
-  %cmp = fcmp ogt float %x, 0.000000e+00
-  %tmp = select i1 %cmp, i32 43, i32 11
-  ret i32 %tmp
-
-; CHECK-LABEL: t1:
-; CHECK: xxlxor [[REG1:[0-9]+]], [[REG1]], [[REG1]]
-; CHECK: fcmpu {{[0-9]+}}, {{[0-9]+}}, [[REG1]]
-; CHECK: blr
-; CHECK-NVSXP8A: lfs [[REG1:[0-9]+]]
-; CHECK-NVSXP8A: fcmpu {{[0-9]+}}, {{[0-9]+}}, [[REG1]]
-; CHECK-NVSXP8A: blr
-}
-
-define signext i32 @t2(double %x) local_unnamed_addr #0 {
-entry:
-  %cmp = fcmp ogt double %x, 0.000000e+00
-  %tmp = select i1 %cmp, i32 43, i32 11
-  ret i32 %tmp
-
-; CHECK-LABEL: t2:
-; CHECK: xxlxor [[REG2:[0-9]+]], [[REG2]], [[REG2]]
-; CHECK: xscmpudp {{[0-9]+}}, {{[0-9]+}}, [[REG2]]
-; CHECK: blr
-; CHECK-NVSXP8A: lfs [[REG2:[0-9]+]]
-; CHECK-NVSXP8A: fcmpu {{[0-9]+}}, {{[0-9]+}}, [[REG2]]
-; CHECK-NVSXP8A: blr
-}
-
-define signext i32 @t3(ppc_fp128 %x) local_unnamed_addr #0 {
-entry:
-  %cmp = fcmp ogt ppc_fp128 %x, 0xM00000000000000000000000000000000
-  %tmp = select i1 %cmp, i32 43, i32 11
-  ret i32 %tmp
-
-; CHECK-LABEL: t3:
-; CHECK: xxlxor [[REG3:[0-9]+]], [[REG3]], [[REG3]]
-; CHECK: fcmpu {{[0-9]+}}, {{[0-9]+}}, [[REG3]]
-; CHECK: fcmpu {{[0-9]+}}, {{[0-9]+}}, [[REG3]]
-; CHECK: blr
-; CHECK-NVSXP8A: lfs [[REG3:[0-9]+]]
-; CHECK-NVSXP8A: fcmpu {{[0-9]+}}, {{[0-9]+}}, [[REG3]]
-; CHECK-NVSXP8A: blr
-}
-
-define <2 x double> @t4() local_unnamed_addr #0 {
-  ret <2 x double> zeroinitializer
-; CHECK-LABEL: t4:
-; CHECK: vxor [[REG4:[0-9]+]], [[REG4]], [[REG4]]
-; CHECK: blr
-; CHECK-NVSXP8A: lfs [[REG4:[0-9]+]]
-; CHECK-NVSXP8A: fmr {{[0-9]+}}, [[REG4:[0-9]+]]
-; CHECK-NVSXP8A: blr
-}
-
-define <2 x i64> @t5() local_unnamed_addr #0 {
-  ret <2 x i64> zeroinitializer
-; CHECK-LABEL: t5:
-; CHECK: vxor [[REG5:[0-9]+]], [[REG5]], [[REG5]]
-; CHECK: blr
-; CHECK-NVSXP8A: lvx
-; CHECK-NVSXP8A: blr
-}
-

test/CodeGen/PowerPC/setcc-to-sub.ll

+; RUN: llc -verify-machineinstrs -mtriple=powerpc64le-unknown-linux-gnu \
+; RUN: -mcpu=pwr8 < %s | FileCheck %s
+
+%class.PB2 = type { [1 x i32], %class.PB1* }
+%class.PB1 = type { [1 x i32], i64, i64, i32 }
+
+; Function Attrs: norecurse nounwind readonly
+define zeroext i1 @test1(%class.PB2* %s_a, %class.PB2* %s_b) local_unnamed_addr #0 {
+entry:
+  %arrayidx.i6 = bitcast %class.PB2* %s_a to i32*
+  %0 = load i32, i32* %arrayidx.i6, align 8, !tbaa !1
+  %and.i = and i32 %0, 8
+  %arrayidx.i37 = bitcast %class.PB2* %s_b to i32*
+  %1 = load i32, i32* %arrayidx.i37, align 8, !tbaa !1
+  %and.i4 = and i32 %1, 8
+  %cmp.i5 = icmp ult i32 %and.i, %and.i4
+  ret i1 %cmp.i5
+
+; CHECK-LABEL: @test1
+; CHECK: rlwinm [[REG1:[0-9]*]]
+; CHECK-NEXT: rlwinm [[REG2:[0-9]*]]
+; CHECK-NEXT: sub [[REG3:[0-9]*]], [[REG1]], [[REG2]]
+; CHECK-NEXT: rldicl 3, [[REG3]]
+; CHECK: blr
+
+}
+
+; Function Attrs: norecurse nounwind readonly
+define zeroext i1 @test2(%class.PB2* %s_a, %class.PB2* %s_b) local_unnamed_addr #0 {
+entry:
+  %arrayidx.i6 = bitcast %class.PB2* %s_a to i32*
+  %0 = load i32, i32* %arrayidx.i6, align 8, !tbaa !1
+  %and.i = and i32 %0, 8
+  %arrayidx.i37 = bitcast %class.PB2* %s_b to i32*
+  %1 = load i32, i32* %arrayidx.i37, align 8, !tbaa !1
+  %and.i4 = and i32 %1, 8
+  %cmp.i5 = icmp ule i32 %and.i, %and.i4
+  ret i1 %cmp.i5
+
+; CHECK-LABEL: @test2
+; CHECK: rlwinm [[REG1:[0-9]*]]
+; CHECK-NEXT: rlwinm [[REG2:[0-9]*]]
+; CHECK-NEXT: sub [[REG3:[0-9]*]], [[REG2]], [[REG1]]
+; CHECK-NEXT: rldicl [[REG4:[0-9]*]], [[REG3]]
+; CHECK-NEXT: xori 3, [[REG4]], 1
+; CHECK: blr
+
+}
+
+; Function Attrs: norecurse nounwind readonly
+define zeroext i1 @test3(%class.PB2* %s_a, %class.PB2* %s_b) local_unnamed_addr #0 {
+entry:
+  %arrayidx.i6 = bitcast %class.PB2* %s_a to i32*
+  %0 = load i32, i32* %arrayidx.i6, align 8, !tbaa !1
+  %and.i = and i32 %0, 8
+  %arrayidx.i37 = bitcast %class.PB2* %s_b to i32*
+  %1 = load i32, i32* %arrayidx.i37, align 8, !tbaa !1
+  %and.i4 = and i32 %1, 8
+  %cmp.i5 = icmp ugt i32 %and.i, %and.i4
+  ret i1 %cmp.i5
+
+; CHECK-LABEL: @test3
+; CHECK: rlwinm [[REG1:[0-9]*]]
+; CHECK-NEXT: rlwinm [[REG2:[0-9]*]]
+; CHECK-NEXT: sub [[REG3:[0-9]*]], [[REG2]], [[REG1]]
+; CHECK-NEXT: rldicl 3, [[REG3]]
+; CHECK: blr
+
+}
+
+; Function Attrs: norecurse nounwind readonly
+define zeroext i1 @test4(%class.PB2* %s_a, %class.PB2* %s_b) local_unnamed_addr #0 {
+entry:
+  %arrayidx.i6 = bitcast %class.PB2* %s_a to i32*
+  %0 = load i32, i32* %arrayidx.i6, align 8, !tbaa !1
+  %and.i = and i32 %0, 8
+  %arrayidx.i37 = bitcast %class.PB2* %s_b to i32*
+  %1 = load i32, i32* %arrayidx.i37, align 8, !tbaa !1
+  %and.i4 = and i32 %1, 8
+  %cmp.i5 = icmp uge i32 %and.i, %and.i4
+  ret i1 %cmp.i5
+
+; CHECK-LABEL: @test4
+; CHECK: rlwinm [[REG1:[0-9]*]]
+; CHECK-NEXT: rlwinm [[REG2:[0-9]*]]
+; CHECK-NEXT: sub [[REG3:[0-9]*]], [[REG1]], [[REG2]]
+; CHECK-NEXT: rldicl [[REG4:[0-9]*]], [[REG3]]
+; CHECK-NEXT: xori 3, [[REG4]], 1
+; CHECK: blr
+
+}
+
+!1 = !{!2, !2, i64 0}
+!2 = !{!"int", !3, i64 0}
+!3 = !{!"omnipotent char", !4, i64 0}
+!4 = !{!"Simple C++ TBAA"}