`opt -O3` fails to optimize branch instruction after #209615
Nobody has claimed this yet.
- 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
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- 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