[X86] Optimize umax(X,1)

[kazu]

Summary

Without this patch:

%cond = call i32 @llvm.umax.i32(i32 %X, i32 1)

is compiled as:

83 ff 02                   cmp    $0x2,%edi
b8 01 00 00 00             mov    $0x1,%eax
0f 43 c7                   cmovae %edi,%eax

With this patch, the compiler generates:

89 f8                      mov    %edi,%eax
83 ff 01                   cmp    $0x1,%edi
83 d0 00                   adc    $0x0,%eax

saving 3 bytes. We should be able to save 5 bytes in larger functions
where the mov is unnecessary.

This patch converts the specific cmov pattern to cmp $1 followed by
adc $0.

This patch partially fixes:

https://github.com/llvm/llvm-project/issues/60374

The LLVM IR optimizer is yet to canonicalize max expressions to
actual @llvm.umax.

[goldstein.w.n]

Slightly unrelated, is it possible to get the codegen to be:

	xorl	%eax, %eax
	cmp	$0x1, %edi
	adc	%edi, %eax

?

If so that would be preferable (except in register pressure corner case b.c eax and edi now have slight live-range overlap).
On target like ICX it saves a full instruction b.c no move-elim.

[spatel]

This doesn't handle i8 and i16 the same way because truncates get in the way, right? Would it be better to match this as "umax(x, 1)" (before it becomes x86-specific instructions)? Or could we peek through a truncate and still generate the adc for i8/i16?

[goldstein.w.n]

In D144451#4142230, @spatel wrote:

This doesn't handle i8 and i16 the same way because truncates get in the way, right? Would it be better to match this as "umax(x, 1)" (before it becomes x86-specific instructions)? Or could we peek through a truncate and still generate the adc for i8/i16?

I think there is potentially a bit of danger of transforming umin as other patterns seem more likely to look for umin than the alternative (select or x86adc).

[goldstein.w.n]

llvm/lib/Target/X86/X86ISelLowering.cpp

47277

Can it also match X86ISD::CMP?

47286

Can ADC valuetype by different than comparison valuetype?

[goldstein.w.n]

In D144451#4142412, @goldstein.w.n wrote:

In D144451#4142230, @spatel wrote:

This doesn't handle i8 and i16 the same way because truncates get in the way, right? Would it be better to match this as "umax(x, 1)" (before it becomes x86-specific instructions)? Or could we peek through a truncate and still generate the adc for i8/i16?

I think there is potentially a bit of danger of transforming umin as other patterns seem more likely to look for umin than the alternative (select or x86adc).

Looking a little more, think you're right, best to do this in LowerSELECT before the X86ISD::CMOV logic.

[RKSimon]

Do we have i8/i16 test coverage anywhere?

[RKSimon]

Incidently, I'm guessing the vector equivalent code will be pretty poor as well when a umax op isn't available (v2i64 pre-AVX512 etc).

[spatel]

In D144451#4142962, @RKSimon wrote:

Incidently, I'm guessing the vector equivalent code will be pretty poor as well when a umax op isn't available (v2i64 pre-AVX512 etc).

Yes, I posted an example of that in https://github.com/llvm/llvm-project/issues/60374 :
https://alive2.llvm.org/ce/z/didmjC

If there's no legal/custom umax, we probably want to convert to setcc + add. Once that's done, we can take another step to canonicalize the IR icmp+zext+add sequence to umax.
There's a sibling pattern with umin:
https://alive2.llvm.org/ce/z/cXL_d9
...and related signed patterns too.

[kazu]

In D144451#4142080, @goldstein.w.n wrote:

Slightly unrelated, is it possible to get the codegen to be:

	xorl	%eax, %eax
	cmp	$0x1, %edi
	adc	%edi, %eax

?

If so that would be preferable (except in register pressure corner case b.c eax and edi now have slight live-range overlap).
On target like ICX it saves a full instruction b.c no move-elim.

I've never thought of that. Very interesting. The comparison of the two approaches is such a close call. I have a slight preference to the mov-cmp-adc route. If we assume that users typically do not care about the value of x past umax(x,1), which I haven't surveyed in real-world applications, we shouldn't have to make a copy of the source operand with a mov, especially in large enough functions where the calling conventions (edi->eax) aren't much of a constraint. Friendliness under high register pressure along with the 6-byte encoding (without a mov) is a plus.

[kazu]

In D144451#4142960, @RKSimon wrote:

Do we have i8/i16 test coverage anywhere?

I just checked in 86bd9c984154d625392bfab05541bbe9ee18b6ab. This patch being reviewed here does not handle i8/i16 yet.

[goldstein.w.n]

In D144451#4153259, @kazu wrote:

In D144451#4142960, @RKSimon wrote:

Do we have i8/i16 test coverage anywhere?

I just checked in 86bd9c984154d625392bfab05541bbe9ee18b6ab. This patch being reviewed here does not handle i8/i16 yet.

Think might make sense to move this to LowerSELECT so it can handle i8/i16. Also makes more sense to just lower this directly to adc/sbb rather than through cmovcc.

[kazu]

Add support for i8 and i16 by seeing through ISD::TRUNCATE.

[kazu]

Please take a look.

I settled on the idea of seeing trough ISD::TRUNCATE. I tried sending ISD::UMAX of MVT::i8 through MVT::i64 to LowerMINMAX with setOperationAction, but I ended up seeing various differences in the generated code even without my actual change for the optimization.

[RKSimon]

llvm/lib/Target/X86/X86ISelLowering.cpp

47439

Cond.hasOneUse() will only check the sub flags output has one use - what about the sub result? Cond->hasOneUse()?

47443

(style) auto *Sub1C =

[kazu]

Use auto and Cond->hasOneUse().

[kazu]

Please take a look. Thanks!

[RKSimon]

LGTM cheers

llvm/lib/Target/X86/X86ISelLowering.cpp

           CmpAgainst == dyn_cast<ConstantSDNode>(TrueOp)) {
         SDValue Ops[] = {FalseOp, Cond.getOperand(0),
                          DAG.getTargetConstant(CC, DL, MVT::i8), Cond};
         return DAG.getNode(X86ISD::CMOV, DL, N->getValueType(0), Ops);
       }
     }
   }
 
+  // Transform:
+  //
+  //   (cmov 1 T (uge T 2))
+  //
+  // to:
+  //
+  //   (adc T 0 (sub T 1))
+  if (CC == X86::COND_AE && isOneConstant(FalseOp) &&
+      Cond.getOpcode() == X86ISD::SUB && Cond.getOperand(0) == TrueOp &&
+      Cond.hasOneUse()) {
+    ConstantSDNode *Sub1C = dyn_cast<ConstantSDNode>(Cond.getOperand(1));
+    if (Sub1C && Sub1C->getZExtValue() == 2) {
+      EVT VT = Cond->getValueType(0);
+      // Subtract 1 and generate a carry.
+      SDValue NewSub = DAG.getNode(X86ISD::SUB, DL, Cond->getVTList(), TrueOp,
+                                   DAG.getConstant(1, DL, VT));
+      SDValue EFLAGS(NewSub.getNode(), 1);
+      return DAG.getNode(X86ISD::ADC, DL, DAG.getVTList(VT, MVT::i32), TrueOp,
+                         DAG.getConstant(0, DL, VT), EFLAGS);
+    }
+  }
+
   // Fold and/or of setcc's to double CMOV:
   //   (CMOV F, T, ((cc1 | cc2) != 0)) -> (CMOV (CMOV F, T, cc1), T, cc2)
   //   (CMOV F, T, ((cc1 & cc2) != 0)) -> (CMOV (CMOV T, F, !cc1), F, !cc2)
   //
   // This combine lets us generate:
   //   cmovcc1 (jcc1 if we don't have CMOV)
   //   cmovcc2 (same)
   // instead of:

                                const X86Subtarget &Subtarget) {
   // Check for legality
   // pmullw/pmulhw are not supported by SSE.
   if (!Subtarget.hasSSE2())
     return SDValue();
 
   // Check for profitability
   // pmulld is supported since SSE41. It is better to use pmulld
   // instead of pmullw+pmulhw, except for subtargets where pmulld is slower than
   // the expansion.
   bool OptForMinSize = DAG.getMachineFunction().getFunction().hasMinSize();
   if (Subtarget.hasSSE41() && (OptForMinSize || !Subtarget.isPMULLDSlow()))
     return SDValue();
 
   ShrinkMode Mode;
   if (!canReduceVMulWidth(N, DAG, Mode))
     return SDValue();
 
   SDLoc DL(N);
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);

llvm/test/CodeGen/X86/umax.ll

 ; X86-NEXT:    retl
   %r = call i32 @llvm.umax.i32(i32 %a, i32 %b)
   ret i32 %r
 }
 
 define i32 @test_i32_1(i32 %a) nounwind {
 ; X64-LABEL: test_i32_1:
 ; X64:       # %bb.0:
-; X64-NEXT:    cmpl $2, %edi
-; X64-NEXT:    movl $1, %eax
-; X64-NEXT:    cmovael %edi, %eax
+; X64-NEXT:    movl %edi, %eax
+; X64-NEXT:    cmpl $1, %edi
+; X64-NEXT:    adcl $0, %eax
 ; X64-NEXT:    retq
 ;
 ; X86-LABEL: test_i32_1:
 ; X86:       # %bb.0:
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    cmpl $2, %ecx
-; X86-NEXT:    movl $1, %eax
-; X86-NEXT:    cmovael %ecx, %eax
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    cmpl $1, %eax
+; X86-NEXT:    adcl $0, %eax
 ; X86-NEXT:    retl
   %r = call i32 @llvm.umax.i32(i32 %a, i32 1)
   ret i32 %r
 }
 
 define i64 @test_i64(i64 %a, i64 %b) nounwind {
 ; X64-LABEL: test_i64:
 ; X64:       # %bb.0:

 ; X86-NEXT:    retl
   %r = call i64 @llvm.umax.i64(i64 %a, i64 %b)
   ret i64 %r
 }
 
 define i64 @test_i64_1(i64 %a) nounwind {
 ; X64-LABEL: test_i64_1:
 ; X64:       # %bb.0:
-; X64-NEXT:    cmpq $2, %rdi
-; X64-NEXT:    movl $1, %eax
-; X64-NEXT:    cmovaeq %rdi, %rax
+; X64-NEXT:    movq %rdi, %rax
+; X64-NEXT:    cmpq $1, %rdi
+; X64-NEXT:    adcq $0, %rax
 ; X64-NEXT:    retq
 ;
 ; X86-LABEL: test_i64_1:
 ; X86:       # %bb.0:
 ; X86-NEXT:    pushl %esi
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %edx
-; X86-NEXT:    cmpl $2, %ecx
-; X86-NEXT:    movl $1, %eax
-; X86-NEXT:    movl $1, %esi
-; X86-NEXT:    cmovael %ecx, %esi
+; X86-NEXT:    cmpl $1, %ecx
+; X86-NEXT:    movl %ecx, %esi
+; X86-NEXT:    adcl $0, %esi
 ; X86-NEXT:    testl %edx, %edx
+; X86-NEXT:    movl $1, %eax
 ; X86-NEXT:    cmovnel %ecx, %eax
 ; X86-NEXT:    cmovel %esi, %eax
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
   %r = call i64 @llvm.umax.i64(i64 %a, i64 1)
   ret i64 %r
 }