llvm / llvm/llvm-project

[AggressiveInstCombine] testcase in the pass is not optimized as expected with -O3 once

Open
#221,257 0 comments 1 reaction 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

`mul_carry_comm` from `llvm/test/Transforms/AggressiveInstCombine/umulh_carry.ll` optimized with aggressive instcombine, but not with -O3 once.

https://github.com/llvm/llvm-project/blob/4154b56ccc70220dca3fa1226fc8a24bafd90ac3/llvm/test/Transforms/AggressiveInstCombine/umulh_carry.ll#L132-L161

I found that running `-O3` twice, then the testcse finally optimized as expected, but with `-pass=instcombine`, it totally loses the change for optimization.

```llvm
; run -O3 once
define i32 @mul_carry_comm(i32 %x, i32 %y) local_unnamed_addr #0 {
entry:
%shr = lshr i32 %x, 16
%and = and i32 %x, 65535
%shr1 = lshr i32 %y, 16
%and2 = and i32 %y, 65535
%mul = mul nuw i32 %and2, %shr
%mul3 = mul nuw i32 %shr1, %and
%add = add i32 %mul3, %mul
%mul4 = mul nuw i32 %and2, %and
%shr5 = lshr i32 %mul4, 16
%add6 = add i32 %add, %shr5
%cmp = icmp ult i32 %add6, %mul
%cond = select i1 %cmp, i32 65536, i32 0
%mul8 = mul nuw i32 %shr1, %shr
%shr10 = lshr i32 %add6, 16
%add9 = add nuw i32 %shr10, %mul8
%add11 = add i32 %add9, %cond
ret i32 %add11
}
; run -O3 twice (as expected)
define i32 @mul_carry_comm(i32 %x, i32 %y) {
entry:
%0 = zext i32 %x to i64
%1 = zext i32 %y to i64
%2 = mul nuw i64 %0, %1
%3 = lshr i64 %2, 32
%add11 = trunc nuw i64 %3 to i32
ret i32 %add11
}
; with -passes=instcombine
define i32 @mul_carry_comm(i32 %x, i32 %y) {
entry:
%shr = lshr i32 %x, 16
%and = and i32 %x, 65535
%shr1 = lshr i32 %y, 16
%and2 = and i32 %y, 65535
%mul = mul nuw i32 %and2, %shr
%mul3 = mul nuw i32 %shr1, %and
%add = add i32 %mul3, %mul
%mul4 = mul nuw i32 %and, %and2
%shr5 = lshr i32 %mul4, 16
%add6 = add i32 %shr5, %add
%cmp = icmp ult i32 %add6, %mul
%cond = select i1 %cmp, i32 65536, i32 0
%mul8 = mul nuw i32 %shr, %shr1
%shr10 = lshr i32 %add6, 16
%add9 = or disjoint i32 %cond, %shr10
%add11 = add i32 %add9, %mul8
ret i32 %add11
}
```

And run both with `-passes=aggressive-instcombine`,
```llvm
; with O3
define i32 @mul_carry_comm_O3(i32 %x, i32 %y) {
entry:
%0 = zext i32 %x to i64
%1 = zext i32 %y to i64
%2 = mul nuw i64 %0, %1
%3 = lshr i64 %2, 32
%add11 = trunc nuw i64 %3 to i32
ret i32 %add11
}

; with instcombine
define i32 @mul_carry_comm_instcombine(i32 %x, i32 %y) {
entry:
%shr = lshr i32 %x, 16
%and = and i32 %x, 65535
%shr1 = lshr i32 %y, 16
%and2 = and i32 %y, 65535
%mul = mul nuw i32 %and2, %shr
%mul3 = mul nuw i32 %shr1, %and
%add = add i32 %mul3, %mul
%mul4 = mul nuw i32 %and, %and2
%shr5 = lshr i32 %mul4, 16
%add6 = add i32 %shr5, %add
%cmp = icmp ult i32 %add6, %mul
%cond = select i1 %cmp, i32 65536, i32 0
%mul8 = mul nuw i32 %shr, %shr1
%shr10 = lshr i32 %add6, 16
%add9 = or disjoint i32 %cond, %shr10
%add11 = add i32 %add9, %mul8
ret i32 %add11
}
```

godbolt: https://godbolt.org/z/EWMjs4GWf

Contributor guide

Open the contributing guide

Research direction

Start with llvm/test/Transforms/AggressiveInstCombine/umulh_carry.ll, especially the mul_carry_comm testcase at lines 132-161. Reproduce the difference between -O3, -O3 run twice, -passes=instcombine, and -passes=aggressive-instcombine using the provided IR or Godbolt link. Trace the pass pipeline to identify why the expected multiply-high form is not reached in one run; done means the testcase optimizes consistently as expected.

Written by the indexing model from the issue text.

Assessment

Domain
compilers
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
50/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.