Missed Optimization: max(max(x, c1) << c2, c3) —> max(x << c2, c3) when c3 >= c1 * 2 ^ c2

[Cancelll]

define i8 @src(i8 %arg0) {
  %1 = call i8 @llvm.umax.i8(i8 %arg0, i8 1)
  %2 = shl nuw i8 %1, 1
  %3 = call i8 @llvm.umax.i8(i8 %2, i8 16)
  %4 = icmp sgt i8 %1, -1
  %5 = select i1 %4, i8 %3, i8 -1
  ret i8 %3
}

define i8 @tgt(i8 %arg0) {
  %1 = shl nuw i8 %arg0, 1
  %2 = call i8 @llvm.umax.i8(i8 %1, i8 16)
  %3 = icmp sgt i8 %2, -1
  %4 = select i1 %3, i8 %2, i8 -1
  ret i8 %2
}

Alive2: https://alive2.llvm.org/ce/z/on2tJE

Found this pattern at: https://github.com/dtcxzyw/llvm-opt-benchmark/blob/94dab89f901fdfae3e47dc6696c06d591fdd7993/bench/openssl/optimized/packet.ll#L1086-L1094

I think this transformation can be generalized to operations other than shift and also to min().

[dtcxzyw]

Solution1: Canonicalize max(x << shamt, c << shamt) into max(x, c) << shamt: https://alive2.llvm.org/ce/z/mQEDAQ
We already did similar things in moveAddAfterMinMax .

Solution2: Generalize to fold max(max(x, c1) binop c2, c3) —> max(x binop c2, c3).

[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: Zhenyang Xu (Cancelll)

```llvm define i8 @src(i8 %arg0) { %1 = call i8 @llvm.umax.i8(i8 %arg0, i8 1) %2 = shl nuw i8 %1, 1 %3 = call i8 @llvm.umax.i8(i8 %2, i8 16) %4 = icmp sgt i8 %1, -1 %5 = select i1 %4, i8 %3, i8 -1 ret i8 %3 }

define i8 @tgt(i8 %arg0) {
%1 = shl nuw i8 %arg0, 1
%2 = call i8 @llvm.umax.i8(i8 %1, i8 16)
%3 = icmp sgt i8 %2, -1
%4 = select i1 %3, i8 %2, i8 -1
ret i8 %2
}

Alive2: https://alive2.llvm.org/ce/z/on2tJE

Found this pattern at: https://github.com/dtcxzyw/llvm-opt-benchmark/blob/94dab89f901fdfae3e47dc6696c06d591fdd7993/bench/openssl/optimized/packet.ll#L1086-L1094

I think this transformation can be generalized to operations other than shift and also to min().
</details>

[Rajveer100]

@dtcxzyw
I am currently on f9f2bf8, and the transformation seems to work:

build/bin/opt -passes=instsimplify debug-instcombine-139786.ll -S

; ModuleID = 'debug-instcombine-139786.ll'
source_filename = "debug-instcombine-139786.ll"

define i8 @f(i8 %arg0) {
  %1 = call i8 @llvm.umax.i8(i8 %arg0, i8 1)
  %2 = shl nuw i8 %1, 1
  %3 = call i8 @llvm.umax.i8(i8 %2, i8 16)
  ret i8 %3
}

; Function Attrs: nocallback nofree nosync nounwind speculatable willreturn memory(none)
declare i8 @llvm.umax.i8(i8, i8) #0

attributes #0 = { nocallback nofree nosync nounwind speculatable willreturn memory(none) }

Checking with godbolt as well: https://godbolt.org/z/E65dzssGo

[Rajveer100]

@dtcxzyw I am currently on f9f2bf8, and the transformation seems to work:

build/bin/opt -passes=instsimplify debug-instcombine-139786.ll -S
; ModuleID = 'debug-instcombine-139786.ll'
source_filename = "debug-instcombine-139786.ll"

define i8 @f(i8 %arg0) {
%1 = call i8 @llvm.umax.i8(i8 %arg0, i8 1)
%2 = shl nuw i8 %1, 1
%3 = call i8 @llvm.umax.i8(i8 %2, i8 16)
ret i8 %3
}

; Function Attrs: nocallback nofree nosync nounwind speculatable willreturn memory(none)
declare i8 @llvm.umax.i8(i8, i8) #0

attributes #0 = { nocallback nofree nosync nounwind speculatable willreturn memory(none) }
Checking with godbolt as well: https://godbolt.org/z/E65dzssGo

Oops, my bad, it's indeed missing.

[Charukesh827]

can you assign this to me?

[dtcxzyw]

@Charukesh827 Please read https://llvm.org/docs/InstCombineContributorGuide.html before submitting a patch. Have fun :)