wiki:ShufflePatternLibrary

Version 1 (modified by cameron, 4 years ago) (diff)

--

Towards a Library of Shufflevector Patterns

The LLVM IR contains a very powerful vector operation called shufflevector. Unless the target architecture supports a similarly powerful operation directly, good code generation for shufflevector instructions with arbitrary shuffle patterns is very difficult.

However, there are many shufflevector patterns that map to simpler operations, both at the LLVM IR level and at the target architecture level. This document introduces a library of patterns as well as a systematic approach to code generation for shufflevector operations.

Pattern Recognition

With a potentially large library of shuffle vector patterns and corresponding implementations, how do we systematically search for patterns without incurring high pattern matching costs for brute-force sequential search? One answer is to abstract the patterns and to define quick, parallel methods of pattern recognition.

The Rotate Pattern

The double vector rotate pattern is recognized as follows. Form the first-order difference vector of the shuffle index vector

d[i] = sv[(i+1) mod 2^k^] - sv[i]

The Shift Left Pattern

The Shift Right Logical Pattern

The Shift Right Arithmetic Pattern

The Zero-Extend Pattern

The Merge Pattern

The Pack Pattern

The Parallel Extract Pattern

The Parallel Deposit Pattern