llvm / llvm/llvm-project

[DivRemPairs] Missed optimization when remainder is "folded" into icmp

Open
#168,749 2 comments 0 reactions 0 assignees View on GitHub
llvm:optimizations missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

https://gcc.godbolt.org/z/G13GK4M1c

```LLVM
define i8 @src1(i8 noundef %n, i8 noundef %c) {
%div = udiv i8 %n, %c
%mul = mul i8 %div, %c
%rem = sub i8 %n, %mul
%cmp1 = icmp eq i8 %rem, 0
%cmp2 = icmp ult i8 %div, %c
%cond = select i1 %cmp1, i8 42, i8 24
%retval = select i1 %cmp2, i8 %n, i8 %cond
ret i8 %retval
}

define i8 @src2(i8 noundef %n, i8 noundef %c) {
%div = udiv i8 %n, %c
%mul = mul i8 %div, %c
%cmp1 = icmp eq i8 %n, %mul ; %rem folded into %cmp1
%cmp2 = icmp ult i8 %div, %c
%cond = select i1 %cmp1, i8 42, i8 24
%retval = select i1 %cmp2, i8 %n, i8 %cond
ret i8 %retval
}
```

The difference between the two functions is that in the second one `%rem` is "folded" into `%cmp1 = icmp eq`.
It could be optimized as well: https://alive2.llvm.org/ce/z/P_pFDU

The pattern is found in libc++: https://github.com/llvm/llvm-project/blob/a4456a5ce3fd4a57343c0cc6dd46b2d024985bc4/libcxx/src/hash.cpp#L93

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.