Missed optimization: `umax(1 << x, 1 << y) => 1 << umax(x, y)`

[Kmeakin]

C code

https://godbolt.org/z/YnEj5KGrW

#include <stdint.h>

uint32_t src1(uint32_t x, uint32_t y) {
    uint32_t shl_x = 1 << x;
    uint32_t shl_y = 1 << y;
    return (shl_x > shl_y) ? shl_x : shl_y;
}

uint32_t tgt1(uint32_t x, uint32_t y) {
    uint32_t shl_x = 1 << x;
    uint32_t shl_y = 1 << y;
    return (x > y) ? shl_x : shl_y;
}

uint32_t src2(uint32_t x, uint32_t y) {
    uint32_t shl_x = 1 << x;
    uint32_t shl_y = 1 << y;
    return (shl_x < shl_y) ? shl_x : shl_y;
}

uint32_t tgt2(uint32_t x, uint32_t y) {
    uint32_t shl_x = 1 << x;
    uint32_t shl_y = 1 << y;
    return (x < y) ? shl_x : shl_y;
}

Alive proof

https://alive2.llvm.org/ce/z/bv698b

----------------------------------------
define i32 @src1(i32 noundef %#0, i32 noundef %#1) nofree willreturn memory(none) {
#2:
  %#3 = shl nuw i32 1, noundef %#0
  %#4 = shl nuw i32 1, noundef %#1
  %#5 = umax i32 %#3, %#4
  %#range_0_%#5 = !range i32 %#5, i32 1, i32 2147483649
  ret i32 %#range_0_%#5
}
=>
define i32 @tgt1(i32 noundef %#0, i32 noundef %#1) nofree willreturn memory(none) {
#2:
  %#3 = umax i32 noundef %#0, noundef %#1
  %#4 = shl nuw i32 1, %#3
  %#range_0_%#4 = !range i32 %#4, i32 1, i32 2147483649
  ret i32 %#range_0_%#4
}
Transformation seems to be correct!


----------------------------------------
define i32 @src2(i32 noundef %#0, i32 noundef %#1) nofree willreturn memory(none) {
#2:
  %#3 = shl nuw i32 1, noundef %#0
  %#4 = shl nuw i32 1, noundef %#1
  %#5 = umin i32 %#3, %#4
  %#range_0_%#5 = !range i32 %#5, i32 1, i32 2147483649
  ret i32 %#range_0_%#5
}
=>
define i32 @tgt2(i32 noundef %#0, i32 noundef %#1) nofree willreturn memory(none) {
#2:
  %#3 = umin i32 noundef %#0, noundef %#1
  %#4 = shl nuw i32 1, %#3
  %#range_0_%#4 = !range i32 %#4, i32 1, i32 2147483649
  ret i32 %#range_0_%#4
}
Transformation seems to be correct!

Summary:
  2 correct transformations
  0 incorrect transformations
  0 failed-to-prove transformations
  0 Alive2 errors

AArch64 assembly

src1:
        mov     w8, #1
        lsl     w9, w8, w0
        lsl     w8, w8, w1
        cmp     w9, w8
        csel    w0, w9, w8, hi
        ret

tgt1:
        cmp     w0, w1
        mov     w8, #1
        csel    w9, w0, w1, hi
        lsl     w0, w8, w9
        ret

src2:
        mov     w8, #1
        lsl     w9, w8, w0
        lsl     w8, w8, w1
        cmp     w9, w8
        csel    w0, w9, w8, lo
        ret

tgt2:
        cmp     w0, w1
        mov     w8, #1
        csel    w9, w0, w1, lo
        lsl     w0, w8, w9
        ret

[llvmbot]

Hi!

This issue may be a good introductory issue for people new to working on LLVM. If you would like to work on this issue, your first steps are:

1. Check that no other contributor has already been assigned to this issue. If you believe that no one is actually working on it despite an assignment, ping the person. After one week without a response, the assignee may be changed.
2. In the comments of this issue, request for it to be assigned to you, or just create a pull request after following the steps below. Mention this issue in the description of the pull request.
3. Fix the issue locally.
4. Run the test suite locally. Remember that the subdirectories under test/ create fine-grained testing targets, so you can e.g. use make check-clang-ast to only run Clang's AST tests.
5. Create a Git commit.
6. Run git clang-format HEAD~1 to format your changes.
7. Open a pull request to the upstream repository on GitHub. Detailed instructions can be found in GitHub's documentation. Mention this issue in the description of the pull request.

If you have any further questions about this issue, don't hesitate to ask via a comment in the thread below.

[llvmbot]

@llvm/issue-subscribers-good-first-issue

Author: Karl Meakin (Kmeakin)

# C code

https://godbolt.org/z/YnEj5KGrW

#include <stdint.h>

uint32_t src1(uint32_t x, uint32_t y) {
    uint32_t shl_x = 1 << x;
    uint32_t shl_y = 1 << y;
    return (shl_x > shl_y) ? shl_x : shl_y;
}

uint32_t tgt1(uint32_t x, uint32_t y) {
    uint32_t shl_x = 1 << x;
    uint32_t shl_y = 1 << y;
    return (x > y) ? shl_x : shl_y;
}

uint32_t src2(uint32_t x, uint32_t y) {
    uint32_t shl_x = 1 << x;
    uint32_t shl_y = 1 << y;
    return (shl_x < shl_y) ? shl_x : shl_y;
}

uint32_t tgt2(uint32_t x, uint32_t y) {
    uint32_t shl_x = 1 << x;
    uint32_t shl_y = 1 << y;
    return (x < y) ? shl_x : shl_y;
}

Alive proof

https://alive2.llvm.org/ce/z/bv698b

----------------------------------------
define i32 @<!-- -->src1(i32 noundef %#<!-- -->0, i32 noundef %#<!-- -->1) nofree willreturn memory(none) {
#<!-- -->2:
  %#<!-- -->3 = shl nuw i32 1, noundef %#<!-- -->0
  %#<!-- -->4 = shl nuw i32 1, noundef %#<!-- -->1
  %#<!-- -->5 = umax i32 %#<!-- -->3, %#<!-- -->4
  %#range_0_%#<!-- -->5 = !range i32 %#<!-- -->5, i32 1, i32 2147483649
  ret i32 %#range_0_%#<!-- -->5
}
=&gt;
define i32 @<!-- -->tgt1(i32 noundef %#<!-- -->0, i32 noundef %#<!-- -->1) nofree willreturn memory(none) {
#<!-- -->2:
  %#<!-- -->3 = umax i32 noundef %#<!-- -->0, noundef %#<!-- -->1
  %#<!-- -->4 = shl nuw i32 1, %#<!-- -->3
  %#range_0_%#<!-- -->4 = !range i32 %#<!-- -->4, i32 1, i32 2147483649
  ret i32 %#range_0_%#<!-- -->4
}
Transformation seems to be correct!


----------------------------------------
define i32 @<!-- -->src2(i32 noundef %#<!-- -->0, i32 noundef %#<!-- -->1) nofree willreturn memory(none) {
#<!-- -->2:
  %#<!-- -->3 = shl nuw i32 1, noundef %#<!-- -->0
  %#<!-- -->4 = shl nuw i32 1, noundef %#<!-- -->1
  %#<!-- -->5 = umin i32 %#<!-- -->3, %#<!-- -->4
  %#range_0_%#<!-- -->5 = !range i32 %#<!-- -->5, i32 1, i32 2147483649
  ret i32 %#range_0_%#<!-- -->5
}
=&gt;
define i32 @<!-- -->tgt2(i32 noundef %#<!-- -->0, i32 noundef %#<!-- -->1) nofree willreturn memory(none) {
#<!-- -->2:
  %#<!-- -->3 = umin i32 noundef %#<!-- -->0, noundef %#<!-- -->1
  %#<!-- -->4 = shl nuw i32 1, %#<!-- -->3
  %#range_0_%#<!-- -->4 = !range i32 %#<!-- -->4, i32 1, i32 2147483649
  ret i32 %#range_0_%#<!-- -->4
}
Transformation seems to be correct!

Summary:
  2 correct transformations
  0 incorrect transformations
  0 failed-to-prove transformations
  0 Alive2 errors

AArch64 assembly

src1:
        mov     w8, #<!-- -->1
        lsl     w9, w8, w0
        lsl     w8, w8, w1
        cmp     w9, w8
        csel    w0, w9, w8, hi
        ret

tgt1:
        cmp     w0, w1
        mov     w8, #<!-- -->1
        csel    w9, w0, w1, hi
        lsl     w0, w8, w9
        ret

src2:
        mov     w8, #<!-- -->1
        lsl     w9, w8, w0
        lsl     w8, w8, w1
        cmp     w9, w8
        csel    w0, w9, w8, lo
        ret

tgt2:
        cmp     w0, w1
        mov     w8, #<!-- -->1
        csel    w9, w0, w1, lo
        lsl     w0, w8, w9
        ret

[el-ev]

I would like to take this.

[nikic]

@el-ev Please take a look at https://llvm.org/docs/InstCombineContributorGuide.html when working on your patch.