Optimize std::max(X, 1u) and save one instruction

[kazutakahirata]

It looks like std::max(X, 1u) can be optimized a little bit.

Compile the following with clang++ -O2 on x86:

#include <algorithm>

unsigned foo();

unsigned UnsignedMaxOneA() {
  unsigned X = foo();
  return std::max(X, 1u);
}

unsigned UnsignedMaxOneB() {
  unsigned X = foo();
  return X + (X == 0);
}

I get:

        testl   %eax, %eax
        movl    $1, %ecx
        cmovel  %ecx, %eax

        cmpl    $1, %eax
        adcl    $0, %eax

I'm using foo() so that we can use %eax as the starting point (as opposed to %edi for a parameter).

Both sequences have dependency tree height of 2. They are encoded with 10 bytes and 6 bytes, respectively.

[llvmbot]

@llvm/issue-subscribers-backend-x86

[rotateright]

Before we get to an x86 codegen optimization, we should recognize that neither of the source examples is reduced to the canonical umax intrinsic in IR. Also, that canonical IR produces different x86 asm than either of the other IR variants:
https://alive2.llvm.org/ce/z/fFVbT5

[rotateright]

Also note that there are likely "umin" siblings for these transforms and possibly signed min/max too. It's possible that we already handle one or more of those variants but missed the umax equivalency.

[kazutakahirata]

Thank you for looking into this. It's interesting to see three different sequences just for "unsigned min with 1u".

So, it looks like we have two things to do:

• Canonicalize select into llvm.umax.i32 at the LLVM IR level.
• Generate the best sequence for llvm.umax.i32 in the x86 backend.

You've mentioned umin and signed min/max. As far as feeding icmp eq into select, we could recognize the LLVM IR for the following as llvm.[us]{max,min}.i32:

std::min(signed_var, INT_MAX-1)     // difficult to generate a carry
std::max(signed_var, INT_MIN+1)     // difficult to generate a carry
std::min(unsigned_var, UINT_MAX-1)  // "cmp -1" followed by "sbb"
std::max(unsigned_var, 1u)          // this issue

That said, std::max(unsigned_var, 1) might be the only common and profitable one.

[rotateright]

Thank you for looking into this. It's interesting to see three different sequences just for "unsigned min with 1u".

So, it looks like we have two things to do:

* Canonicalize `select` into `llvm.umax.i32` at the LLVM IR level. 
* Generate the best sequence for `llvm.umax.i32` in the x86 backend.

Yes - it's actually (at least) 2 patches in IR (InstCombine) to get the IR normalized. At that level, we don't really know which form leads to the best codegen, but we usually want the minimum instruction sequence.

For codegen, even for x86 alone, we may need more than 1 patch to get the ideal assembly for all data types/subtargets. For example, the vector variation of these patterns shows that we have to account for when the umax operation has a specialized instruction to handle it:
https://alive2.llvm.org/ce/z/didmjC

That said, std::max(unsigned_var, 1) might be the only common and profitable one.

OK - thanks for checking. I have not looked at all of the variations, but we will want to add (many!) tests to make sure we have the optimal code for all cases.

[kazutakahirata]

I just posted a patch for the x86 backend for scalar values:

https://reviews.llvm.org/D144451