[CVP] Missed ctpop range fold after SimplifyCFG converts branch to select
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
Current `opt -O3` gives suboptimal results on the testcase `ctpop_fold` in `lvm/test/Transforms/CorrelatedValuePropagation/range.ll`.
For this case:
```llvm ir
define i1 @ctpop_fold(i16 %x) {
%cmp = icmp ult i16 %x, 256
br i1 %cmp, label %if, label %else
if:
%ctpop = call i16 @llvm.ctpop.i16(i16 %x)
%res = icmp ule i16 %ctpop, 8
ret i1 %res
else:
ret i1 true
}
```
`opt -O3` gives (https://godbolt.org/z/1Pdz65sze):
```llvm ir
define i1 @ctpop_fold(i16 %x) local_unnamed_addr #0 {
common.ret:
%cmp = icmp ugt i16 %x, 255
%ctpop = tail call range(i16 0, 17) i16 @llvm.ctpop.i16(i16 %x)
%res = icmp samesign ult i16 %ctpop, 9
%common.ret.op = select i1 %cmp, i1 true, i1 %res
ret i1 %common.ret.op
}
```
which could be essentially wrapped into a constant `ret true`: https://alive2.llvm.org/ce/z/U7es_P.
This miss is due to the SimplifyCFG runs before CVP, which canonicalizes branches into select inst, removing the dominating `x < 256` comparison over `ctpop`. CVP can not infer the precondition from the select and return semantics, leaving them as-is.
This case can be optimized if we explicitly adds the range guard on `x` again:
```llvm ir
define i1 @explicit_known_bits(i16 noundef %x) {
entry:
%guard = icmp ult i16 %x, 256
br i1 %guard, label %inside, label %outside
inside:
%masked = and i16 %x, 255 ;; add an redundant, explicit mask
%ctpop = call i16 @llvm.ctpop.i16(i16 %masked)
%res = icmp ule i16 %ctpop, 8
ret i1 %res
outside:
ret i1 true
}
```
`opt -O3` then finishes its job nicely (https://godbolt.org/z/1Pdz65sze):
```llvm ir
define noundef i1 @explicit_known_bits(i16 noundef %x) local_unnamed_addr #0 {
entry:
ret i1 true
}
```
Contributor guide
Research direction
Start with lvm/test/Transforms/CorrelatedValuePropagation/range.ll and run the ctpop_fold testcase through opt -O3 to reproduce the missed fold. Read the CorrelatedValuePropagation and SimplifyCFG interaction described in the issue, then verify that the testcase reaches the expected constant ret true result and remains covered by the regression test.
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
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 48/100