llvm / llvm/llvm-project

[InstCombine] Fold `((~0 << X) ^ ~0) & X` to `X`

Open
#216,446 2 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

InstCombine appears to miss the following general identity:

https://alive2.llvm.org/ce/z/w4PLp-

The identity can be viewed as:

```text
((~0 << X) ^ ~0) & X
```

where:

```text
(~0 << X) ^ ~0
```

constructs a mask containing the low `X` bits:

```text
(1 << X) - 1
```

For every defined shift, `X` is less than the integer bit width. For positive `X`, the number of bits required to represent `X` is at most `X`, so all set bits of `X` are contained within the low-`X`-bit mask. `X == 0` is also trivially valid.

Therefore:

```text
X & ((1 << X) - 1) == X
```

for all defined executions of the source expression.

For out-of-range shift amounts the source `shl` is poison, so replacing the expression with `%x` is still a valid refinement, as confirmed by Alive2.

I originally encountered this in a more restricted form where `%x` came from a `zext i1`, but the simplification generalizes to the full-width shift operand as shown above.

A possible canonical fold would therefore be roughly:

```text
and (xor (shl -1, X), -1), X
-> X
```

with analogous forms if existing InstCombine canonicalization represents the low-bit mask differently.

Assisted by gpt-5.6-sol

Contributor guide

Open the contributing guide

Research direction

Start at the InstCombine entry points handling shl, xor, and, since the issue names no specific file or test. Check related canonicalization patterns and validate that the proposed expression folds to X for defined shifts; done means the missed identity is recognized with regression coverage.

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.