llvm / llvm/llvm-project

Failure to reassociate uniform vector transformations with variable shuffles

Open
#167,260 0 comments 0 reactions 0 assignees View on GitHub
llvm:optimizations missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

Since shuffles only change the arrangement of elements within a vector, it should be legal to reassociate operations that transform all lanes in the same manner to occur before/after they are shuffled even if the shuffle pattern isn't known at compile time.

This optimization isn't performed when the indexes are variable. For example, `shuffle(POW_OF_2_LUT, idx) + 1` is implemented naively rather then offsetting the table:

```asm
powOf2P1LUT_clang:
pand xmm0, xmmword ptr [rip + .LCPI0_0]
movdqa xmm1, xmmword ptr [rip + .LCPI0_1]
pshufb xmm1, xmm0
pcmpeqd xmm0, xmm0
psubb xmm1, xmm0
movdqa xmm0, xmm1
ret
```

https://godbolt.org/z/Y78Ws6Tdv

Note that this isn't legal for shuffles that can set lanes to specific constants, or that select between two vectors if only one is transformed.

Contributor guide

Open the contributing guide

Research direction

Start by reproducing the variable-index example from the issue using the linked Godbolt case and inspect the generated assembly. Trace the compiler's shuffle reassociation handling and add coverage for uniformly transformed lanes, while preserving the stated exclusions for constant-setting and selectively transformed shuffles. Done means the example no longer emits the naive post-shuffle transformation.

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
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.