llvm / llvm/llvm-project

`opt -O3` fails to optimize branch instruction after #209615

Open
#213,782 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

llvm:optimizations missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

Repro (notice how the branch to `fail` isn't optimized out): https://godbolt.org/z/xa5K7zYoW

(not copy/pasting the repro IR here as there's already a lot of IR in this bug)

In the `-O3` optimization pipeline, `opt` produces the following IR right before `ConstraintElimination`:

```llvm
br i1 %need_grow, label %grow, label %join

grow: ; preds = %entry
%0 = tail call i64 @llvm.umax.i64(i64 %len, i64 5)
%new_cap = add nuw i64 %0, 3
store i64 %new_cap, ptr %v, align 8
%sub1 = sub i64 %new_cap, %len
%cmp1 = icmp ugt i64 %sub1, 2
br label %join

join: ; preds = %grow, %entry
%phi = phi i1 [ true, %entry ], [ %cmp1, %grow ]
tail call void @llvm.assume(i1 %phi)
%loaded_cap = load i64, ptr %v, align 8
%sub2 = sub i64 %loaded_cap, %len
%cmp2 = icmp ult i64 %sub2, 3
br i1 %cmp2, label %fail, label %exit

fail: ; preds = %join
tail call void @do_reserve_and_handle()
br label %exit
```

Before #209615, `ConstraintElimination` does not recognize that `%cmp1` is tautologically true:

```llvm
grow: ; preds = %entry
%0 = tail call i64 @llvm.umax.i64(i64 %len, i64 5)
%new_cap = add nuw i64 %0, 3
store i64 %new_cap, ptr %v, align 8
%sub1 = sub i64 %new_cap, %len
%cmp1 = icmp ugt i64 %sub1, 2
br label %join

join: ; preds = %grow, %entry
%phi = phi i1 [ true, %entry ], [ %cmp1, %grow ]
tail call void @llvm.assume(i1 %phi)
```

while after, that pass *does* recognize it as true:

```llvm
grow: ; preds = %entry
%0 = tail call i64 @llvm.umax.i64(i64 %len, i64 5)
%new_cap = add nuw i64 %0, 3
store i64 %new_cap, ptr %v, align 8
%sub1 = sub i64 %new_cap, %len
br label %join

join: ; preds = %grow, %entry
%phi = phi i1 [ true, %entry ], [ true, %grow ] ; <---- %cmp1 is optimized to true here
tail call void @llvm.assume(i1 %phi)
```

Because `%phi` is always `%true`, `tail call void @llvm.assume(i1 %phi)` later gets optimized away. This causes issues right before (one of the many invocations of) `SimplifyCFG`.

Before that commit, the IR before `SimplifyCFG` is

```llvm
join: ; preds = %entry
%0 = tail call i64 @llvm.umax.i64(i64 %len, i64 5)
%new_cap = add nuw i64 %0, 3
store i64 %new_cap, ptr %v, align 8
%sub1 = sub i64 %new_cap, %len
%cmp1 = icmp ugt i64 %sub1, 2
%1 = icmp ult i64 %sub1, 3
tail call void @llvm.assume(i1 %cmp1)
br i1 %1, label %fail, label %exit

fail: ; preds = %join
tail call void @do_reserve_and_handle()
br label %exit
```

Because we preserved the call to `@llvm.assume(...)`, we know that `%1` is always false (`%cmp1` being true asserts that `%sub1 > 2`, so `%1` which is `%sub1 < 3` has to be false). `SimplifyCFG` therefore recognizes that the `fail` basic block will never execute and therefore optimizes it away.

However, after the commit, we have

```llvm
join: ; preds = %entry
%0 = tail call i64 @llvm.umax.i64(i64 %len, i64 5)
%new_cap = add nuw i64 %0, 3
store i64 %new_cap, ptr %v, align 8
%.pre = sub i64 %new_cap, %len
%1 = icmp ult i64 %.pre, 3
br i1 %1, label %fail, label %exit

fail: ; preds = %join
tail call void @do_reserve_and_handle()
br label %exit
```

`SimplifyCFG` therefore fails to eliminate the `fail` basic block because 1) we optimized the call to `@llvm.assume(...)` and 2)`ConstraintElimination` is not run a second time before this `SimplifyCFG` run to prove that ` %.pre = sub i64 %new_cap, %len` is `>2`.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with the linked Compiler Explorer reproducer and inspect the -O3 pipeline around ConstraintElimination and SimplifyCFG. Trace how the llvm.assume is removed before SimplifyCFG and compare the IR before and after #209615. Done means the fail block is eliminated again for the reported reproducer without regressing the relevant optimization behavior.

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
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.