llvm / llvm/llvm-project

[InstCombine] Fold null-check over pointer umax select

Open
#199,402 3 comments 0 reactions 1 assignee Claimed by @ParkHanbum View on GitHub
llvm:instcombine missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

InstCombine currently misses a simplification for null checks over a pointer `umax` select.

Given IR like:

```llvm
%isnull = icmp eq ptr %x, null
%cmp = icmp ugt ptr %x, %y
%max = select i1 %cmp, ptr %x, ptr %y
%maxnull = icmp eq ptr %max, null
%r = select i1 %isnull, i1 true, i1 %maxnull
```
This can be folded to:

```llvm
%r = icmp eq ptr %x, null
```

For address spaces where the null pointer representation is zero, if %x != null, then umax(%x, %y) cannot be null:

```text
if %y == null, unsigned max selects %x
if %y != null, the selected value is also non-null
```

So:
```c
x == null ? true : umax(x, y) == null
```
is equivalent to:

```c
x == null
```
This pattern appears in real optimized IR, for example:

```llvm
%66 = load ptr, ptr %65, align 8
%.not.i.not.i.i = icmp eq ptr %66, null
%68 = load ptr, ptr %67, align 8
%69 = icmp ugt ptr %66, %68
%.08.i.i.i = select i1 %69, ptr %66, ptr %68
%.not5.i.i = icmp eq ptr %.08.i.i.i, null
%.not.i.i38 = select i1 %.not.i.not.i.i, i1 true, i1 %.not5.i.i
```
which can reduce the final condition to:

```llvm
%.not.i.i38 = icmp eq ptr %66, null
```

AliveProof : https://alive2.llvm.org/ce/z/nNjyRU
Compiler-Explorer & Perf : https://compiler-explorer.com/z/vbjjoj9TY
RealWorld Usage : https://github.com/dtcxzyw/llvm-opt-benchmark-nightly/pull/359/changes#diff-1a8713a2b431eaa7ff2b500a2fa2585ffe362cf8c9dd65fa54ca5dfcf51a58d1

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.