llvm / llvm/llvm-project

[InstCombine] Missed fold of (x + 1) * y to y << x when x is known to be in {0, 1}

Open
#211,183 9 comments 0 reactions 1 assignee Claimed by @user1342234 View on GitHub
llvm:instcombine missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

For the below C code:
```c
uint16_t f(uint16_t x, uint16_t y) {
uint16_t bounded = x < 2 ? x : 0;
return (uint16_t)((bounded + 1) * y);
}
```
LLVM produces the following suboptimal IR under -O3 (https://godbolt.org/z/M7q1r6Kbx):
```llvm ir
define i16 @f(i16 noundef %0, i16 noundef %1) {
%3 = add nuw nsw i16 %0, 1
%4 = icmp ugt i16 %0, 1
%5 = select i1 %4, i16 1, i16 %3
%6 = mul i16 %5, %1
ret i16 %6
}
```
which could be further optimized as (https://alive2.llvm.org/ce/z/cSYLr-):
```llvm ir
define i16 @f(i16 noundef %x, i16 noundef %y) {
%in.range = icmp ult i16 %x, 2
%bounded = select i1 %in.range, i16 %x, i16 0
%result = shl i16 %y, %bounded
ret i16 %result
}
```
The problem is LLVM already has success testcases for such a fold in `llvm/test/Transforms/InstCombine/mul.ll`, like the one below:
```llvm ir
define i16 @mul_add_one(i16 range(i16 0, 2) %x, i16 %y) {
; CHECK-LABEL: @mul_add_one(
; CHECK-NEXT: [[RET:%.*]] = shl i16 [[Y:%.*]], [[X:%.*]]
; CHECK-NEXT: ret i16 [[RET]]
;
%add = add i16 %x, 1
%ret = mul i16 %add, %y
ret i16 %ret
}
```
It appears that the existing fold is not applied when the same {0, 1} range is established through a select rather than a range attribute.

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.