llvm / llvm/llvm-project

SimplifyCFG could make better decision before converting a phi to a select.

Open
#222,923 0 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

Consider https://godbolt.org/z/hxz9aK866

For the code:

```c
if( newarc[cmp-1].flow < newarc[cmp].flow )
cmp++;
```

llvm at O2 generates (as can be seen in compiler explorer):

```asm
cmp x11, x10
cinc x0, x0, lt
b .LBB0_1
```
which is a branchless form (uses cinc to do the cmp++ increment).

When select-optimize is enabled (right-most panel in compiler-explorer), it generates:

```asm
cmp x11, x10
b.ge .LBB0_1
orr x0, x0, #0x1
b .LBB0_1
```

On an aarch64 machine, the latter version is found to be 6-7% more efficient than the former.

The problem with the former is that, the IR started with branches, then an instance of simplifycfg decided locally (in function validateAndCostRequiredSelects) that the cost of converting this branch to a select is 1 (which is less than the budget of 2) and converts it. A later instcombine pass sees this and converts it roughly to:

```llvm
%21 = icmp slt i64 %18, %20, !dbg !91
%22 = zext i1 %21 to i64, !dbg !92
%23 = or disjoint i64 %13, %22, !dbg !92
br label %24, !dbg !92
```

which eventually ends up as a cinc (if selectoptimize is not enabled).

When selectoptimize is enabled and run, it operates over the select group (function SelectOptimizeImpl::findProfitableSIGroupsInnerLoops) and identifies that branches would be cheaper than predicates and converts it back.

Wouldn't it make sense for simplifycfg to make the right decision first time instead of undoing it later?

Rationale: While we do get an optimal codegen when selectoptimize is run, it is only enabled at O3. At O2, we get the sub-optimal version. Having simplifycfg make the right decision wouldn't affect code size or be as 'aggressive' as running an O3-only pass at O2 for the whole program.

This code snippet is extracted from mcf in SPEC2017 benchmark suite.

Contributor guide

Open the contributing guide

Research direction

Start by reading SimplifyCFG's validateAndCostRequiredSelects decision and SelectOptimizeImpl::findProfitableSIGroupsInnerLoops, then reproduce the Godbolt example at O2 and with select optimization enabled. Compare the resulting AArch64 code and determine whether SimplifyCFG's cost decision can account for this case without broadening the O2 pass pipeline; done means the reproducer's O2 output is validated against the intended tradeoff.

Written by the indexing model from the issue text.

Assessment

Tech stack
c
Domain
compilers, performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
48/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.