llvm / llvm/llvm-project

AggressiveInstCombine misses mul-high idiom after inverted carry predicate

Open
#205,261 2 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

Hi, this seems to be an AggressiveInstCombine missed optimization.
The original form is recognized and folded with `-passes=aggressive-instcombine`, but the equivalent form is not optimized.

```llvm
define i128 @src(i128 %x, i128 %y) {
entry:
%shr = lshr i128 %x, 64
%and = and i128 %x, 18446744073709551615
%shr1 = lshr i128 %y, 64
%and2 = and i128 %y, 18446744073709551615
%mul = mul nuw i128 %shr, %and2
%mul3 = mul nuw i128 %and, %shr1
%add = add i128 %mul, %mul3
%mul4 = mul nuw i128 %and, %and2
%shr5 = lshr i128 %mul4, 64
%add6 = add i128 %add, %shr5
%cmp = icmp ult i128 %add6, %mul
%cond = select i1 %cmp, i128 18446744073709551616, i128 0
%mul8 = mul nuw i128 %shr, %shr1
%add9 = add nuw i128 %mul8, %cond
%shr10 = lshr i128 %add6, 64
%add11 = add i128 %add9, %shr10
ret i128 %add11
}
```

after optimization

```llvm
define i128 @src(i128 %x, i128 %y) {
entry:
%0 = zext i128 %x to i256
%1 = zext i128 %y to i256
%2 = mul nuw i256 %0, %1
%3 = lshr i256 %2, 128
%add11 = trunc nuw i256 %3 to i128
ret i128 %add11
}
```

but the equivalent form

```llvm
define i128 @src(i128 %x, i128 %y) {
entry:
%shr = lshr i128 %x, 64
%and = and i128 %x, 18446744073709551615
%shr1 = lshr i128 %y, 64
%and2 = and i128 %y, 18446744073709551615
%mul = mul nuw i128 %shr, %and2
%mul3 = mul nuw i128 %and, %shr1
%add = add i128 %mul, %mul3
%mul4 = mul nuw i128 %and, %and2
%shr5 = lshr i128 %mul4, 64
%add6 = add i128 %add, %shr5
%cmp = icmp uge i128 %add6, %mul
%cond = select i1 %cmp, i128 0, i128 18446744073709551616
%mul8 = mul nuw i128 %shr, %shr1
%add9 = add nuw i128 %mul8, %cond
%shr10 = lshr i128 %add6, 64
%add11 = add i128 %add9, %shr10
ret i128 %add11
}
```
godbolt Link:https://godbolt.org/z/b71Wc5b5W

Contributor guide

Open the contributing guide

Research direction

Start by reproducing both LLVM IR forms with opt -passes=aggressive-instcombine and compare the resulting IR. Trace the AggressiveInstCombine handling of the mul-high idiom and inverted carry predicate; done means the equivalent form folds to the same widened multiplication and shifted result as the original.

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
Quiet
Clarity
Clearly specified
Newbie friendliness
55/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.