[X86] Emit more efficient >= comparisons against 0

[majnemer]

Summary

We don't do a great job with >= 0 comparisons against zero when the
result is used as an i8.

Given something like:
void f(long long LL, bool *B) {

*B = LL >= 0;

}

We used to generate:

shrq    $63, %rdi
xorb    $1, %dil
movb    %dil, (%rsi)

Now we generate:

testq   %rdi, %rdi
setns   (%rsi)

[mbodart]

lib/Target/X86/X86ISelLowering.cpp

24077 ↗

(On Diff #32504)

It would be nice to have a brief comment here describing the general pattern.
Something like:

Attempt to transform signedness tests similar to (i8)(X >= 0), appearing in DAG form
as for example (xor i8 trunc(A i32 >> 31), 1), into setcc A SETGT -1.

24078 ↗

(On Diff #32504)

I would think we also want to suppress this if the xor has more than one user.

24113 ↗

(On Diff #32504)

This is fine. But just curious, is there a reason you chose SETGT -1 over SETGE 0?

[majnemer]

lib/Target/X86/X86ISelLowering.cpp

24077 ↗

(On Diff #32504)

Sure, will do!

24078 ↗

(On Diff #32504)

It might be a little early for me (no coffee, etc.), why is it undesirable to use a test/setns sequence if there is more than one user?

24113 ↗

(On Diff #32504)

We seem to normalize it to that: http://llvm.org/docs/doxygen/html/X86ISelLowering_8cpp_source.html#l03732

Using SETGE 0 works equally well but results in a test/setge sequence. The sequence is equivalent but also requires remembering that test sets OF to 0.

[mbodart]

lib/Target/X86/X86ISelLowering.cpp

24078 ↗

(On Diff #32504)

More than one user likley means the xor is still live.

So the transformation would just add more instructions, without removing any.

I'm a bit new to LLVM, so maybe there's some larger context I'm not seeing.
If so, please shed some light.

24113 ↗

(On Diff #32504)

OK, thanks for the explanation.

[majnemer]

lib/Target/X86/X86ISelLowering.cpp

24078 ↗

(On Diff #32504)

My understanding is that this would replace all users of the xor to instead use the setcc which would mean no additional instructions would get generated. However, I think it makes sense to check to see if the truncate and shift both have one use.

[majnemer]

• Address review comments

[spatel]

lib/Target/X86/X86ISelLowering.cpp

24089 ↗

(On Diff #32595)

typo: "aginst"

24107 ↗

(On Diff #32595)

typo: "ammount"

24121 ↗

(On Diff #32595)

This function description is too specific now.

test/CodeGen/X86/cmp.ll

215 ↗

(On Diff #32595)

B is not used in this test.

215–224 ↗

(On Diff #32595)

Add tests for an i1 output, i16 input, and i64 input?

[majnemer]

• Address review comments
• Address Sanjay's review comments.

[mbodart]

lib/Target/X86/X86ISelLowering.cpp

24078 ↗

(On Diff #32602)

Guess my coffee wasn't strong enough either ;-)
Yes, the trunc/shift usage counts were what I meant.

[spatel]

lib/Target/X86/X86ISelLowering.cpp

24112 ↗

(On Diff #32602)

It would be great to add the earlier review comment about the difference between SETGT -1 and SETGE 0 here in the code comment. Save someone a little wondering down the line. :)

I have no further comments.

Thanks, David!

llvm/trunk/lib/Target/X86/X86ISelLowering.cpp

if (ConstantSDNode *Y1C = dyn_cast<ConstantSDNode>(N1.getOperand(1)))
         SDValue Ops[] = { N0.getOperand(0), Neg,
                           DAG.getConstant(X86::COND_GE, DL, MVT::i8),
                           SDValue(Neg.getNode(), 1) };
         return DAG.getNode(X86ISD::CMOV, DL, DAG.getVTList(VT, MVT::Glue), Ops);
       }
   return SDValue();
 }
 
-// PerformXorCombine - Attempts to turn XOR nodes into BLSMSK nodes
+// Try to turn tests against the signbit in the form of:
+//   XOR(TRUNCATE(SRL(X, size(X)-1)), 1)
+// into:
+//   SETGT(X, -1)
+static SDValue foldXorTruncShiftIntoCmp(SDNode *N, SelectionDAG &DAG) {
+  // This is only worth doing if the output type is i8.
+  if (N->getValueType(0) != MVT::i8)
+    return SDValue();
+
+  SDValue N0 = N->getOperand(0);
+  SDValue N1 = N->getOperand(1);
+
+  // We should be performing an xor against a truncated shift.
+  if (N0.getOpcode() != ISD::TRUNCATE || !N0.hasOneUse())
+    return SDValue();
+
+  // Make sure we are performing an xor against one.
+  if (!isa<ConstantSDNode>(N1) || !cast<ConstantSDNode>(N1)->isOne())
+    return SDValue();
+
+  // SetCC on x86 zero extends so only act on this if it's a logical shift.
+  SDValue Shift = N0.getOperand(0);
+  if (Shift.getOpcode() != ISD::SRL || !Shift.hasOneUse())
+    return SDValue();
+
+  // Make sure we are truncating from one of i16, i32 or i64.
+  EVT ShiftTy = Shift.getValueType();
+  if (ShiftTy != MVT::i16 && ShiftTy != MVT::i32 && ShiftTy != MVT::i64)
+    return SDValue();
+
+  // Make sure the shift amount extracts the sign bit.
+  if (!isa<ConstantSDNode>(Shift.getOperand(1)) ||
+      Shift.getConstantOperandVal(1) != ShiftTy.getSizeInBits() - 1)
+    return SDValue();
+
+  // Create a greater-than comparison against -1.
+  // N.B. Using SETGE against 0 works but we want a canonical looking
+  // comparison, using SETGT matches up with what TranslateX86CC.
+  SDLoc DL(N);
+  SDValue ShiftOp = Shift.getOperand(0);
+  EVT ShiftOpTy = ShiftOp.getValueType();
+  SDValue Cond = DAG.getSetCC(DL, MVT::i8, ShiftOp,
+                              DAG.getConstant(-1, DL, ShiftOpTy), ISD::SETGT);
+  return Cond;
+}
+
 static SDValue PerformXorCombine(SDNode *N, SelectionDAG &DAG,
                                  TargetLowering::DAGCombinerInfo &DCI,
                                  const X86Subtarget *Subtarget) {
   if (DCI.isBeforeLegalizeOps())
     return SDValue();
 
+  if (SDValue RV = foldXorTruncShiftIntoCmp(N, DAG))
+    return RV;
+
   if (Subtarget->hasCMov())
     if (SDValue RV = performIntegerAbsCombine(N, DAG))
       return RV;
 
   return SDValue();
 }
 
 /// PerformLOADCombine - Do target-specific dag combines on LOAD nodes.

llvm/trunk/test/CodeGen/X86/cmp.ll

define zeroext i1 @test15(i32 %bf.load, i32 %n) {
   %cmp5 = icmp uge i32 %bf.lshr, %n
   %.cmp5 = or i1 %cmp2, %cmp5
   ret i1 %.cmp5
 
 ; CHECK-LABEL: test15:
 ; CHECK:  shrl  $16, %edi
 ; CHECK:  cmpl  %esi, %edi
 }
+
+define i8 @test16(i16 signext %L) {
+  %lshr  = lshr i16 %L, 15
+  %trunc = trunc i16 %lshr to i8
+  %not   = xor i8 %trunc, 1
+  ret i8 %not
+
+; CHECK-LABEL: test16:
+; CHECK:  testw   %di, %di
+; CHECK:  setns   %al
+}
+
+define i8 @test17(i32 %L) {
+  %lshr  = lshr i32 %L, 31
+  %trunc = trunc i32 %lshr to i8
+  %not   = xor i8 %trunc, 1
+  ret i8 %not
+
+; CHECK-LABEL: test17:
+; CHECK:  testl   %edi, %edi
+; CHECK:  setns   %al
+}
+
+define i8 @test18(i64 %L) {
+  %lshr  = lshr i64 %L, 63
+  %trunc = trunc i64 %lshr to i8
+  %not   = xor i8 %trunc, 1
+  ret i8 %not
+
+; CHECK-LABEL: test18:
+; CHECK:  testq   %rdi, %rdi
+; CHECK:  setns   %al
+}
+
+define zeroext i1 @test19(i32 %L) {
+  %lshr  = lshr i32 %L, 31
+  %trunc = trunc i32 %lshr to i1
+  %not   = xor i1 %trunc, 1
+  ret i1 %not
+
+; CHECK-LABEL: test19:
+; CHECK:  testl   %edi, %edi
+; CHECK:  setns   %al
+}