Missed dead branch elimination due to PHI analysis
- 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
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