llvm / llvm/llvm-project

[InstCombine] Fold range-with-hole test to direct inequality checks

Open
#223,251 3 comments 0 reactions 0 assignees View on GitHub
llvm:instcombine missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

## Description

InstCombine appears to miss:

```text
(X - C) >u N || (X - C) == K
```

when the complement is a small constant set.

Example:

```llvm
define i1 @src(i8 %x) {
%v1 = add i8 %x, -8
%v3 = icmp ugt i8 %v1, 2
%v5 = icmp eq i8 %v1, 1
%r = or i1 %v3, %v5
ret i1 %r
}

define i1 @tgt(i8 %x) {
%a = icmp ne i8 %x, 8
%b = icmp ne i8 %x, 10
%r = and i1 %a, %b
ret i1 %r
}
```

Alive2: https://alive2.llvm.org/ce/z/Da85bf

The source is false only when:

```text
x - 8 ∈ {0, 2}
```

i.e. when:

```text
x ∈ {8, 10}
```

Therefore it is equivalent to:

```c
x != 8 && x != 10
```

This removes the arithmetic and exposes a simpler constant set-membership test.

Contributor guide

Open the contributing guide

Research direction

Start in InstCombine's integer comparison and arithmetic-folding handling, using the LLVM IR example in the issue as the entry point. Trace how the range-with-hole condition is represented and verify that the shown source is reduced to equivalent direct inequality checks for the stated constants.

Written by the indexing model from the issue text.

Assessment

Domain
compilers
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.