llvm / llvm/llvm-project

Missed control-flow aware PHI folding: (%0 == %1) implies PHI(%0, %1) ==> %1

Open
#191,179 1 comment 0 reactions 0 assignees View on GitHub
llvm:optimizations
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/devsisters/libquic/blob/89547/boringssl/crypto/x509v3/v3_utl.c#L694

Godbolt: https://godbolt.org/z/v8Yr5sz8W
alive2 proof: https://alive2.llvm.org/ce/z/zXomxA

In the following code, `%.04 = phi i64 [ %0, %skip_prefix.exit ], [ %1, %3 ]` can be simplified to `%.04 = phi i64 [ %1, %skip_prefix.exit ], [ %1, %3 ]`, since `%0 == %1` along the `%skip_prefix.exit` path.

```llvm
define noundef i32 @equal_case(i64 %0, i64 %1, i1 %2) local_unnamed_addr {
br i1 %2, label %skip_prefix.exit.thread, label %skip_prefix.exit

skip_prefix.exit: ; preds = %3
%.not = icmp eq i64 %0, %1
br i1 %.not, label %skip_prefix.exit.thread, label %5

skip_prefix.exit.thread: ; preds = %skip_prefix.exit, %3
%.04 = phi i64 [ %0, %skip_prefix.exit ], [ %1, %3 ]
%4 = tail call i32 @memcmp(i64 %.04)
br label %5

5: ; preds = %skip_prefix.exit.thread, %skip_prefix.exit
ret i32 0
}
```

expected:
```llvm
define noundef i32 @tgt(i64 %0, i64 %1, i1 %2) local_unnamed_addr {
%.not = icmp eq i64 %0, %1
%or.cond = select i1 %2, i1 true, i1 %.not
br i1 %or.cond, label %skip_prefix.exit.thread, label %5

skip_prefix.exit.thread: ; preds = %3
%4 = tail call i32 @memcmp(i64 %1)
br label %5

5: ; preds = %3, %skip_prefix.exit.thread
ret i32 0
}
```

Contributor guide

Open the contributing guide

Research direction

Start by reproducing the reduced LLVM IR in the linked Godbolt example and checking the Alive2 proof. Trace the control-flow-aware PHI simplification responsible for this case; done means the PHI argument is folded to %1 and the resulting IR matches the expected transformation shown in the issue.

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.