# SIMD Optimizations

HEIR includes a SIMD (Single Instruction, Multiple Data) optimizer which is designed to exploit the restricted SIMD parallelism most (Ring-LWE-based) FHE schemes support (also commonly known as “packing” or “batching”). Specifically, HEIR incorporates the “automated batching” optimizations (among many other things) from the HECO compiler. The following will assume basic familiarity with the FHE SIMD paradigm and the high-level goals of the optimization, and we refer to the associated HECO paper, slides, talk and additional resources on the Usenix'23 website for an introduction to the topic. This documentation will mostly focus on describing how the optimization is realized in HEIR (which differs somewhat from the original implementation) and how the optimization is intended to be used in an overall end-to-end compilation pipeline.

## Representing FHE SIMD Operations

Following the design principle of maintaining programs in standard MLIR dialects
as long as possible (cf. the design rationale behind the
Secret Dialect), HEIR uses the MLIR
`tensor`

dialect and
ElementwiseMappable
operations from the MLIR
`arith`

dialect to represent HE
SIMD operations.

We do introduce the HEIR-specific
`tensor_ext.rotate`

operation, which represents a cyclical left-rotation of a tensor. Note that, as
the current SIMD vectorizer only supports one-dimensional tensors, the semantics
of this operation on multi-dimensional tensors are not (currently) defined.

For example, the common “rotate-and-reduce” pattern which results in each element containing the sum/product/etc of the original vector can be expressed as:

```
%tensor = tensor.from_elements %i1, %i2, %i3, %i4, %i5, %i6, %i7, %i8 : tensor<8xi16>
%0 = tensor_ext.rotate %tensor, %c4 : tensor<8xi16>, index
%1 = arith.addi %tensor, %0 : tensor<8xi16>
%2 = tensor_ext.rotate %1, %c2 : tensor<8xi16>, index
%3 = arith.addi %1, %2 : tensor<8xi16>
%4 = tensor_ext.rotate %3, %c1 : tensor<8xi16>, index
%5 = arith.addi %3, %4 : tensor<8xi16>
```

The `%cN`

and `%iN`

, which are defined as `%cN = arith.constant N : index`

and
`%iN = arith.constant N : i16`

, respectively, have been omitted for readability.

## Intended Usage

The `-heir-simd-vectorizer`

pipeline transforms a program consisting of loops
and index-based accesses into tensors (e.g., `tensor.extract`

and
`tensor.insert`

) into one consisting of SIMD operations (including rotations) on
entire tensors. While its implementation does not depend on any FHE-specific
details or even the Secret dialect, this transformation is likely only useful
when lowering a high-level program to an arithmetic-circuit-based FHE scheme
(e.g., B/FV, BGV, or CKKS). The `-mlir-to-openfhe-bgv`

pipeline demonstrates the
intended flow: augmenting a high-level program with `secret`

annotations, then
applying the SIMD optimization (and any other high-level optimizations) before
lowering to BGV operations and then exiting to OpenFHE.

WarningThe current SIMD vectorizer pipeline supports only one-dimensional tensors. As a workaround, one could reshape all multi-dimensional tensors into one-dimensional tensors, but MLIR/HEIR currently do not provide a pass to automate this process.

Since the optimization is based on heuristics, the resulting program might not be optimal or could even be worse than a trivial realization that does not use ciphertext packing. However, well-structured programs generally lower to reasonable batched solutions, even if they do not achieve optimal batching layouts. For common operations such as matrix-vector or matrix-matrix multiplications, state-of-the-art approaches require advanced packing schemes that might map elements into the ciphertext vector in non-trivial ways (e.g., diagonal-major and/or replicated). The current SIMD vectorizer will never change the arrangement of elements inside an input tensor and therefore cannot produce the optimal approaches for these operations.

Note, that the SIMD batching optimization is different from, and significantly
more complex than, the Straight Line Vectorizer (`-straight-line-vectorize`

pass), which simply groups
ElementwiseMappable
operations that agree in operation name and operand/result types into
vectorized/tensorized versions.

## Implementation

Below, we give a brief overview over the implementation, with the goal of both improving maintainability/extensibility of the SIMD vectorizer and allowing advanced users to better understand why a certain program is transformed in the way it is.

### Components

The `-heir-simd-vectorizer`

pipeline uses a combination of standard MLIR passes
(`-canonicalize`

,
`-cse`

,
`-sccp`

) and custom HEIR passes.
Some of these
(`-apply-folders`

,
`-full-loop-unroll`

)
might have applications outside the SIMD optimization, while others
(`-insert-rotate`

,
`-collapse-insertion-chains`

and
`-rotate-and-reduce`

)
are very specific to the FHE SIMD optimization. In addition, the passes make use
of the `RotationAnalysis`

and `TargetSlotAnalysis`

analyses.

### High-Level Flow

**Loop Unrolling**(`-full-loop-unroll`

): The implementation currently begins by unrolling all loops in the program to simplify the later passes. See #589 for a discussion on how this could be avoided.**Canonicalization**(`-apply-folders -canonicalize`

): As the rotation-specific passes are very strict about the structure of the IR they operate on, we must first simplify away things such as tensors of constant values. For performance reasons (c.f. comments in the`heirSIMDVectorizerPipelineBuilder`

function in`heir-opt.cpp`

), this must be done by first applying folds before applying the full canonicalization.**Main SIMD Rewrite**(`-insert-rotate -cse -canonicalize -cse`

): This pass rewrites arithmetic operations over`tensor.extract`

-ed operands into SIMD operations over the entire tensor, rotating the (full-tensor) operands so that the correct elements interact. For example, it will rewrite the following snippet (which computes`t2[4] = t0[3] + t1[5]`

)`%0 = tensor.extract %t0[%c3] : tensor<32xi16> %1 = tensor.extract %t1[%c5] : tensor<32xi16> %2 = arith.addi %0, %1 : i16 %3 = tensor.insert %2 into %t2[%c4] : tensor<32xi16>`

to

`%0 = tensor_ext.rotate %t0, %c31 : tensor<32xi16>, index %1 = tensor_ext.rotate %t1, %c1 : tensor<32xi16>, index %2 = arith.addi %0, %1 : tensor<32xi16>`

i.e., rotating

`t0`

down by one (31 = -1 (mod 32)) and`t1`

up by one to bring the elements at index 3 and 5, respectively, to the “target” index 4. The pass uses the`TargetSlotAnalysis`

to identify the appropriate target index (or ciphertext “slot” in FHE-speak). See Insert Rotate Pass below for more details. This pass is roughly equivalent to the`-batching`

pass in the original HECO implementation.Doing this rewrite by itself does not represent an optimization, but if we consider what happens to the corresponding code for other indices (e.g.,

`t2[5] = t0[4] + t1[6]`

), we see that the pass transforms expressions with the same relative index offsets into the exact same set of rotations/SIMD operations, so the following Common Subexpression Elimination (CSE) will remove redundant computations. We apply CSE twice, once directly (which creates new opportunities for canonicalization and folding) and then again after that canonicalization. See TensorExt Canonicalization for a description of the rotation-specific canonocalization patterns).**Cleanup of Redundant Insert/Extract**(`-collapse-insertion-chains -sccp -canonicalize -cse`

): Because the`-insert-rotate`

pass maintains the consistency of the IR, it emits a`tensor.extract`

operation after the SIMD operation and uses that to replace the original operation (which is valid, as both produce the desired scalar result). As a consequence, the generated code for the snippet above is actually trailed by a (redundant) extract/insert:`%extracted = tensor.extract %2[%c4] : tensor<32xi16> %inserted = tensor.insert %extracted into %t2[%c4] : tensor<32xi16>`

In real code, this might generate a long series of such extraction/insertion operations, all extracting from the same (due to CSE) tensor and inserting into the same output tensor. Therefore, the

`-collapse-insertion-chains`

pass searches for such chains over entire tensors and collapses them. It supports not just chains where the indices match perfectly, but any chain where the relative offset is consistent across the tensor, issuing a rotation to realize the offset (if the offset is zero, the canonicalization will remove the redundant rotation). Note, that in HECO, insertion/extraction is handled differently, as HECO features a`combine`

operation modelling not just simple insertions (`combine(%t0#j, %t1)`

) but also more complex operations over slices of tensors (`combine(%t0#[i,j], %t1)`

). As a result, the equivalent pass in HECO (`-combine-simplify`

) instead joins different`combine`

operations, and a later fold removes`combines`

that replace the entire target tensor. See issue #512 for a discussion on why the`combine`

operation is a more powerful framework and what would be necessary to port it to HEIR.**Applying Rotate-and-Reduce Patterns**(`-rotate-and-reduce -sccp -canonicalize -cse`

): The rotate and reduce pattern (see Representing FHE SIMD Operations for an example) is an important aspect of accelerating SIMD-style operations in FHE, but it does not follow automatically from the batching rewrites applied so far. As a result, the`-rotate-and-reduce`

pass needs to search for sequences of arithmetic operations that correspond to the full folding of a tensor, i.e., patterns such as`t[0]+(t[1]+(t[2]+t[3]+(...)))`

, which currently uses a backwards search through the IR, but could be achieved more efficiently through a data flow analysis (c.f. issue #532). In HECO, rotate-and-reduce is handled differently, by identifying sequences of compatible operations prior to batching and rewriting them to “n-ary” operations. However, this approach requires non-standard arithmetic operations and is therefore not suitable for use in HEIR. However, there is likely still an opportunity to make the patterns in HEIR more robust/general (e.g., support constant scalar operands in the fold, or support non-full-tensor folds). See issue #522 for ideas on how to make the HEIR pattern more robust/more general.

### Insert Rotate Pass

TODO(#721): Write a detailed description of the rotation insertion pass and the associated target slot analysis.

### TensorExt Canonicalization

The
TensorExt (`tensor_ext`

) Dialect
includes a series of canonicalization rules that are essential to making
automatically generated rotation code efficient:

Rotation by zero:

`rotate %t, 0`

folds away to`%t`

Cyclical wraparound:

`rotate %t, k`

for $k > t.size$ can be simplified to`rotate %t, (k mod t.size)`

Sequential rotation:

`%0 = rotate %t, k`

followed by`%1 = rotate %0, l`

is simplified to`rotate %t (k+l)`

Extraction:

`%0 = rotate %t, k`

followed by`%1 = tensor.extract %0[l]`

is simplified to`tensor.extract %t[k+l]`

Binary Arithmetic Ops: where both operands to a binary

`arith`

operation are rotations by the same amount, the rotation can be performed only once, on the result. For Example,`%0 = rotate %t1, k %1 = rotate %t2, k %2 = arith.add %0, %1`

can be simplified to

`%0 = arith.add %t1, %t2 %1 = rotate %0, k`

*Sandwiched*Binary Arithmetic Ops: If a rotation follows a binary`arith`

operation which has rotation as its operands, the post-arith operation can be moved forward. For example,`%0 = rotate %t1, x %1 = rotate %t2, y %2 = arith.add %0, %1 %3 = rotate %2, z`

can be simplified to

`%0 = rotate %t1, x + z %1 = rotate %t2, y + z %2 = arith.add %0, %1`

Single-Use Arithmetic Ops: Finally, there is a pair of rules that do not eliminate rotations, but move rotations up in the IR, which can help in exposing further canonicalization and/or CSE opportunities. These only apply to

`arith`

operations with a single use, as they might otherwise increase the total number of rotations. For example,`%0 = rotate %t1, k %2 = arith.add %0, %t2 %1 = rotate %2, l`

can be equivalently rewritten as

`%0 = rotate %t1, (k+l) %1 = rotate %t2, l %2 = arith.add %0, %1`

and a similar pattern exists for situations where the rotation is the rhs operand of the arithmetic operation.

Note that the index computations in the patterns above (e.g., `k+l`

,
`k mod t.size`

are realized via emitting `arith`

operations. However, for
constant/compile-time-known indices, these will be subsequently constant-folded
away by the canonicalization pass.