llvm / llvm/llvm-project

[InstCombine] Canonicalize vector select of conditional OR mask

Open
#201,086 1 comment 0 reactions 1 assignee Claimed by @gremh97 View on GitHub
llvm:instcombine
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

I found a missed vector canonicalization pattern that appears in ASCII case-conversion code.
A reduced example is:

```llvm
define <8 x i8> @src_ascii_tolower_vec(<8 x i8> %x) {
%sub = add <8 x i8> %x, splat (i8 -65)
%is_upper = icmp ult <8 x i8> %sub, splat (i8 26)
%lower = or <8 x i8> %x, splat (i8 32)
%r = select <8 x i1> %is_upper, <8 x i8> %lower, <8 x i8> %x
ret <8 x i8> %r
}

define <8 x i8> @tgt_ascii_tolower_vec(<8 x i8> %x) {
%sub = add <8 x i8> %x, splat (i8 -65)
%is_upper = icmp ult <8 x i8> %sub, splat (i8 26)
%mask = select <8 x i1> %is_upper, <8 x i8> splat (i8 32), <8 x i8> zeroinitializer
%r = or <8 x i8> %x, %mask
ret <8 x i8> %r
}
```
This is based on the following identity:
```text
select C, (X | K), X
=>
X | select C, K, 0
```
The swapped form is also valid:
```text
select C, X, (X | K)
=>
X | select C, 0, K
```
This pattern is useful for vectorized ASCII uppercase-to-lowercase code:
```text
C = (x - 'A') < 26
C ? (x | 32) : x
```
can be represented as:
```text
x | (C ? 32 : 0)
```
The transformed form exposes the operation as a conditional bit-set mask followed by an OR. On vector targets this can be more codegen-friendly than selecting between x and x | K.

This is not necessarily profitable for scalar code because the instruction count is usually unchanged and the backend may already lower the original form well. So it may be better to restrict the fold to vector integer types.

One implementation detail to be careful about: if the source OR has the disjoint flag, the transformed final OR should only preserve disjoint when it is safe to do so. A conservative first implementation can simply create a plain or.

Suggested fold:
```llvm
%or = or %x, C
%r = select %cond, %or, %x
```
to:
```llvm
%mask = select %cond, C, zeroinitializer
%r = or %x, %mask
```
and the symmetric false-arm form as well.

AliveProof : https://alive2.llvm.org/ce/z/NqKR6w
Compiler-explorer sample & perf : https://compiler-explorer.com/z/Yv83McbGv
RealWorld Usage : https://github.com/dtcxzyw/llvm-opt-benchmark-nightly/pull/417/changes

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.