[InstCombine] Missing divceil fold with an assumed dividend range
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
InstCombine recognizes unsigned ceiling division written as a quotient plus an indicator for a nonzero remainder:
```text
udiv(X, Y) + (urem(X, Y) != 0)
```
When `Y` is nonzero and `X + (Y - 1)` cannot overflow, it rewrites this to:
```text
udiv(X + (Y - 1), Y)
```
For the following LLVM IR, the bound on `%x` is supplied by a dominating assumption:
```llvm
define i16 @src(i8 %x, i8 range(i8 1, 11) %y) {
entry:
%bound = icmp ule i8 %x, 100
call void @llvm.assume(i1 %bound)
%q = udiv i8 %x, %y
%r = urem i8 %x, %y
%has.rem = icmp ne i8 %r, 0
%q.ext = zext i8 %q to i16
%round = zext i1 %has.rem to i16
%result = add i16 %round, %q.ext
ret i16 %result
}
```
On current LLVM trunk, `opt -passes=instcombine` produces the following output (Godbolt: https://godbolt.org/z/rq7rrYvcf):
```llvm
define i16 @src(i8 %x, i8 range(i8 1, 11) %y) {
entry:
%bound = icmp ult i8 %x, 101
call void @llvm.assume(i1 %bound)
%q = udiv i8 %x, %y
%r = urem i8 %x, %y
%has.rem = icmp ne i8 %r, 0
%q.ext = zext nneg i8 %q to i16
%round = zext i1 %has.rem to i16
%result = add nuw nsw i16 %round, %q.ext
ret i16 %result
}
```
InstCombine has canonicalized the assumed condition to `%x
Contributor guide
Research direction
Start with InstCombine's divceil handling, especially checkDivCeilNUW() and its computeConstantRange() call, then compare the existing divceil_i8_var_divisor_zext testcase with the reproducer using llvm.assume. Verify the change with opt -passes=instcombine; done means the assumed-range case receives the same divceil fold without changing the intended result.
Written by the indexing model from the issue text.
Assessment
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 68/100