[x86] add SBB optimization for SETAE (uge) condition code

[spatel]

Summary

x86 scalar select-of-constants (Cond ? C1 : C2) combining/lowering is a mess with missing optimizations. We handle some patterns, but miss logical variants.

To clean that up, we should convert all select-of-constants to logic/math and enhance the combining for the expected patterns from that. DAGCombiner already has the foundation to allow the transforms, so we just need to fill in the holes for x86 math op lowering. Selecting 0 or -1 needs extra attention to produce the optimal code as shown here.

Attempt to verify that all of these IR forms are logically equivalent:
http://rise4fun.com/Alive/plxs

Earlier steps in this series:
rL306040
rL306072

[zvi]

test/CodeGen/X86/sbb.ll

149 ↗

(On Diff #104035)

AFAIK, the processor does avoid false-dependency stalls for the case 'sbb EAX EAX' (unlike xor's and sub's).
So we may want to ensure a 'xor EAX EAX' is placed before.

[zvi]

test/CodeGen/X86/sbb.ll

149 ↗

(On Diff #104035)

Typo fix: the processor does not avoid false-dependency stalls for the case 'sbb EAX EAX'

[spatel]

test/CodeGen/X86/sbb.ll

149 ↗

(On Diff #104035)

Yes, I think that might be a concern. I took a quick look at this, but it's not a small fix from what I can tell:

1. We can't put the xor in the tablegen pat/def because we can't interfere with the EFLAGS result coming from the cmp (the xor must occur before the cmp).
2. We can't use the existing hasUndefRegUpdate() as-is because it's specifically checking operand 1 (and I'm not sure if it would account for #1 either).

The xor for the setcc code is produced by the x86-fixup-setcc pass. We'd probably need to graft into that or create another similar pass?

[spatel]

Ping.

According to Agner's latest docs:
http://www.agner.org/optimize/microarchitecture.pdf

All recent AMD uarch *do* recognize sbb with the same operands as an idiom. See Chapters 18/19/20:
"The following instructions are recognized as independent of the input when both operands are the same register:
XOR, SUB, SBB (depends on carry flag only)..."

That would further the case that we want a later pass to insert the xor based on CPU model. Adding those as part of isel would just be code bloat for AMD.

[zvi]

I would like to run some internal benchmarks on this patch. Are you ok with waiting a couple more days?

[spatel]

In D34652#798420, @zvi wrote:

I would like to run some internal benchmarks on this patch. Are you ok with waiting a couple more days?

Sure - no problem. I haven't been able to see anything over noise level in my testing. I'll start looking at the later fixup passes to see if I can account for this case with the existing machinery.

[zvi]

LGTM. Internal testing did not reveal any performance impact for better or worse. Thanks.

[spatel]

In D34652#798894, @zvi wrote:

LGTM. Internal testing did not reveal any performance impact for better or worse. Thanks.

Thanks for checking! FWIW, this patch increases the likelihood of producing the sbb. However, if a 'naked sbb' is a problem, then I think that pattern already exists anytime we create X86ISD::SETCC_CARRY directly or with materializeSBB(). So we should have the fixup pass independent of this patch assuming that the false dependency stall is a problem.

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

if (CC == X86::COND_B) {
     // X - SETB Z --> X - (mask SBB Z, Z)
     // TODO: Produce ADC/SBB here directly and avoid SETCC_CARRY?
     SDValue SBB = materializeSBB(Y.getNode(), Y.getOperand(1), DAG);
     if (SBB.getValueSizeInBits() != VT.getSizeInBits())
       SBB = DAG.getZExtOrTrunc(SBB, DL, VT);
     return DAG.getNode(IsSub ? ISD::SUB : ISD::ADD, DL, VT, X, SBB);
   }
 
+  auto *ConstantX = dyn_cast<ConstantSDNode>(X);
+  if (!IsSub && ConstantX && ConstantX->isAllOnesValue()) {
+    if (CC == X86::COND_AE) {
+      // This is a complicated way to get -1 or 0 from the carry flag:
+      // -1 + SETAE --> -1 + (!CF) --> CF ? -1 : 0 --> SBB %eax, %eax
+      // We don't have to match the subtract equivalent because sub X, 1 is
+      // canonicalized to add X, -1.
+      return DAG.getNode(X86ISD::SETCC_CARRY, DL, VT,
+                         DAG.getConstant(X86::COND_B, DL, MVT::i8),
+                         Y.getOperand(1));
+    }
+
+    // TODO: Handle COND_BE if it was produced by X86ISD::SUB similar to below.
+  }
+
   if (CC == X86::COND_A) {
     SDValue EFLAGS = Y->getOperand(1);
     // Try to convert COND_A into COND_B in an attempt to facilitate
     // materializing "setb reg".
     //
     // Do not flip "e > c", where "c" is a constant, because Cmp instruction
     // cannot take an immediate as its first operand.
     //
if (Cmp.getOpcode() != X86ISD::CMP || !Cmp.hasOneUse() ||
       !Cmp.getOperand(0).getValueType().isInteger())
     return SDValue();
 
   SDValue Z = Cmp.getOperand(0);
   EVT ZVT = Z.getValueType();
 
   // If X is -1 or 0, then we have an opportunity to avoid constants required in
   // the general case below.
-  if (auto *ConstantX = dyn_cast<ConstantSDNode>(X)) {
+  if (ConstantX) {
     // 'neg' sets the carry flag when Z != 0, so create 0 or -1 using 'sbb' with
     // fake operands:
     //  0 - (Z != 0) --> sbb %eax, %eax, (neg Z)
     // -1 + (Z == 0) --> sbb %eax, %eax, (neg Z)
     if ((IsSub && CC == X86::COND_NE && ConstantX->isNullValue()) ||
         (!IsSub && CC == X86::COND_E && ConstantX->isAllOnesValue())) {
       SDValue Zero = DAG.getConstant(0, DL, ZVT);
       SDVTList X86SubVTs = DAG.getVTList(ZVT, MVT::i32);

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

 }
 
 ; Invert the predicate and effectively swap the select operands:
 ; (X >=u Y) ? 0 : -1 --> (X <u Y) ? -1 : 0 --> cmp, sbb
 
 define i32 @uge_select_0_or_neg1(i32 %x, i32 %y) nounwind {
 ; CHECK-LABEL: uge_select_0_or_neg1:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    cmpl %esi, %edi
-; CHECK-NEXT:    setae %al
-; CHECK-NEXT:    decl %eax
+; CHECK-NEXT:    sbbl %eax, %eax
 ; CHECK-NEXT:    retq
   %cmp = icmp uge i32 %x, %y
   %ext = zext i1 %cmp to i32
   %add = add i32 %ext, -1
   ret i32 %add
 }
 
 ; Swap the predicate and compare operands:

 }
 
 ; Verify that subtract with constant is the same thing.
 ; (X >=u Y) ? 0 : -1 --> (X <u Y) ? -1 : 0 --> cmp, sbb
 
 define i32 @uge_select_0_or_neg1_sub(i32 %x, i32 %y) nounwind {
 ; CHECK-LABEL: uge_select_0_or_neg1_sub:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    cmpl %esi, %edi
-; CHECK-NEXT:    setae %al
-; CHECK-NEXT:    decl %eax
+; CHECK-NEXT:    sbbl %eax, %eax
 ; CHECK-NEXT:    retq
   %cmp = icmp uge i32 %x, %y
   %ext = zext i1 %cmp to i32
   %sub = sub i32 %ext, 1
   ret i32 %sub
 }
 
 ; Make sure we're creating nodes with the right value types. This would crash.