llvm / llvm/llvm-project

[InstCombine] Missing divceil fold with an assumed dividend range

Open
#220,849 0 comments 0 reactions 0 assignees View on GitHub
llvm:instcombine missed-optimization
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.