llvm / llvm/llvm-project

[SCEV] Missed fold: umax(a, b) u<= umax(a, b, c) is trivially true

Open
#213,291 0 comments 0 reactions 1 assignee Claimed by @aleks-tmb View on GitHub
llvm:SCEV missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

Run `opt -passes=indvars` on the following IR:
```llvm
declare void @side_effect()

; umax(a, b) u<= umax(a, b, c) is trivially true, so the header exit is
; unreachable and IndVarSimplify replaces its branch condition with true.
define void @umax_subset_ule_folded(i32 %n, i32 %a, i32 %b, i32 %c) {
entry:
br label %loop
loop:
%iv = phi i32 [ 0, %entry ], [ %iv.next, %latch ]
%m1 = call i32 @llvm.umax.i32(i32 %a, i32 %b)
%tmp = call i32 @llvm.umax.i32(i32 %a, i32 %c)
%m2 = call i32 @llvm.umax.i32(i32 %tmp, i32 %b) ; = umax(a,b,c)
%inv.cond = icmp ule i32 %m1, %m2 ; always true
br i1 %inv.cond, label %latch, label %exit
latch:
call void @side_effect()
%iv.next = add nuw i32 %iv, 1
%ec = icmp ult i32 %iv.next, %n
br i1 %ec, label %loop, label %exit
exit:
ret void
}
```
https://godbolt.org/z/MW5GTY3Ee

Expected: `IndVarSimplify` replaces `%inv.cond` with `true`, eliminating the `%exit` edge from the loop header, since `umax(a, b) u<= umax(a, b, c)` is trivially true.

Actual: The comparison and branch are preserved unchanged.

Alive2 proof: https://alive2.llvm.org/ce/z/BTPBxP

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.