llvm / llvm/llvm-project

[CVP] Missed ctpop range fold after SimplifyCFG converts branch to select

Open
#210,673 2 comments 0 reactions 0 assignees View on GitHub
llvm:transforms missed-optimization
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

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.