llvm / llvm/llvm-project

Missed dead branch elimination due to PHI analysis

Open
#188,452 3 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

The following reduced IR is derived from https://github.com/darktable-org/darktable/blob/db70f8981b98587057e9ee328c4e0804b3cbe30d/src/iop/Permutohedral.h#L710

Godbolt: https://godbolt.org/z/oWxPE37sT

In the following reduced IR, `Block 6` is a dead branch.
Although `%.not` has two incoming values (`%3` and `true`), when it takes the value `%3` (from `%1`), the corresponding PHI value `%.06` is `0`, making `%exitcond.not` evaluate to `false`, and thus control cannot reach block 4. Therefore, block 4 is only reachable via `%._crit_edge`, along which `%.not` is always `true`. As a result, the branch `br i1 %.not` in block 4 is effectively unconditional, and the successor label %6 is a dead branch.

```llvm
define void @PermutohedralLattice<3, 2>::blur() const(i32 %0) local_unnamed_addr {
%2 = tail call ptr @HashTablePermutohedral<3, 2>::getValues() const()
%3 = icmp eq ptr %2, null
br label %.preheader

.preheader:
%.06 = phi i32 [ 0, %1 ], [ %0, %._crit_edge ]
%.not = phi i1 [ %3, %1 ], [ true, %._crit_edge ]
br label %.lr.ph

4:
br i1 %.not, label %common.ret, label %6

._crit_edge:
%exitcond.not = icmp eq i32 %.06, 1
br i1 %exitcond.not, label %4, label %.preheader

.lr.ph:
%5 = tail call i64 @HashTablePermutohedral<3, 2>::size() const()
%.not7 = icmp eq i64 %5, 0
br i1 %.not7, label %._crit_edge, label %.lr.ph

common.ret:
ret void

6:
%7 = tail call i64 @HashTablePermutohedral<3, 2>::size() const()
br label %common.ret
}
```

Contributor guide

Open the contributing guide

Research direction

Start by reproducing the reduced LLVM IR in the linked Godbolt example and compare the optimizer's output with the reachability reasoning in the issue. Read the referenced Permutohedral.h code around line 710 for context; done means the dead branch in block 6 is eliminated without changing the valid control flow.

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.