Targets: VMX (JS20, Cell PPE), SPE (Cell), BlueGene/L (Double Hummer)

The SIMD vectorization (a.k.a. simdization) is implemented in IBM's XL product compiler, and thus supports multiple programming languages (e.g., C, C++, and Fortran), and multiple target machines (e.g., SPU, VMX, and BG/L).

As shown below, successful simdization involves several tasks that closely interact with each other. First Single Instruction Multiple Data (SIMD) parallelism must be extracted from an application, which may involve extraction from a basic-block, a loop, or a combination of both. Once that parallelism is extracted, various additional SIMD hardware constraints must be satisfied, such as memory alignment requirements, physical vector length, and hardware instruction set.

Our approach uses a virtual vector representation [ICS05] as an initial model to successfully extract SIMD parallelism from multiple sources in the code. Virtual registers have no alignment constraint and have arbitrary lengths. The virtual vectors are then progressively lowered in level to the physical SIMD registers of the target machine in successive de-virtualization steps.

A summary of simdization features:

• Loop-level simdization
  • Loops with induction/reduction/local variables, invariant computation, stride-one array accesses
  • Loops with small constant trip count
  • Loops with mixed data types
• Basic-block level simdization
  • Unrolled loops
  • Computation on adjacent members of aggregates
  • Scalar packing
  • Quasi-isomorphic packing
  • Aggregate copy statement
• Alignment handling
  • Data realignment on the fly (only when data are relatively misaligned)
  • Minimizing data realignment overhead
  • Versioning for relative alignment (for BG/L)
  • SIMD prologue/epilogue for misaligned stores
  • Scalar prologue/epilogue for misaligned stores to avoid false sharing and for memory protection
• Other optimizations
  • Diagnostic information on whether loops are simdizable and reasons for not being simdized
  • Interprocedure alignment analysis
  • Idiom recognition to exploit special hardware instructions
  • Loop distribution to isolate simdizable statements
  • Array recovery for loops with pointer arithmetics
  • Runtime dependence analysis
• And a lot more to come ....

Examples of code extract handled by our frameork are found here.

Embedded in the Toronto Portable Optimizer (TPO) component of the XL compiler, the simdization optimization leverages a rich set of high-level optimizations such as interprocedure analysis and loop transformations. Here we focus on describing the new components that are introduced specifically for simdization purposes. There are 6 new phases. The first 3 phases are mainly concerned with extracting SIMD parallelism from various code structures, e.g., basic blocks or loops.

Phase 1: Basic-Block Level Aggregation. During this phase, we aggregate isomorphic statements that address consecutive memory locations into virtual vectors. This phase is particularly successful at extracting SIMD parallelism in unrolled loops and consecutive elements of structs, such as 3-dimensional coordinates found in multimedia applications. It also handles semi-isomorphic statements, for example statements that are nearly identical but for an add versus a subtract operation.

Phase 2: Short-Loop Aggregation. During this phase, we aggregate entire loops with small trip counts into virtual vectors. This approach is successful in eliminating short innermost loop and may thus enable further SIMD aggregation within the second innermost loop. Typical examples are FIR based algorithms.

Phase 3: Loop-Level Aggregation. During this phase, we aggregate instances of a statement in consecutive iterations of a loop. This phase is particularly successful at extracting SIMD parallelism in loops and recognizing special patterns such reductions and linear recurrences. The blocking factor is selected so that the length of each virtual vector is a multiple of the physical vector length: 16 bytes in the VMX/Cell/BGL architectures.

These first 3 phases proceed regardless of the alignments and lengths of the vectors, as if targeting an idealized SIMD machine. This simplifies the extraction phases greatly, especially in the presence of mixed data sizes. Each phase extracts SIMD parallelism, treating input scalar or virtual vectors (generated by a prior phase) in a similar fashion.

The next 3 phases deal with specific constraints of SIMD units, such alignment, physical vector length, and SIMD instruction sets.

Phase 4: Alignment Devirtualization. During this phase, we satisfy the alignment constraint which states that the data being logically operated on by a SIMD operation must reside in the same slot of their respective input and output SIMD registers. In other words, when adding a[i] and b[i+1] in SIMD fashion, we must ensure that both a[0] and b[1] values are in the same relative position in their respective register. Data realignment instructions are inserted only for relatively misaligned memory streams. We attempt to minimize the number of data realignment instructions, both in the presence of compile-time [PLDI04] and runtime [CGO05] misalignment.

More information on the impact of alignment and our approach to minimize the impact of misalignment is found here.

After the completion of this phase, all virtual vector accesses are to aligned data regardless of the compile time/runtime nature of their alignment. A virtual vector may still have a virtual length, i.e. a length that is too long with respect to the physical vector registers provided by the underlying architecture.

Phase 5: Length Devirtualization. During this phase, long vectors are chunked into physical length vector registers, or they may revert back to scalar statements. This phase also handles data size conversion [CGO05], e.g., generating twice as many instructions for 4-byte integer expressions that use results generated by 2-byte short integer expressions.

After this phase, all virtual vectors are aligned and have the physical vector length, namely they are compatible with the physical vector registers provided by the underlying SIMD architecture.

Phase 6: SIMD Code Generation. Up to this point, most SIMD instructions were generic operators such as "add," "mult," or primitive data reorganization instructions. During this phase, we generate SIMD instructions that are specific to the target SIMD units.

After this last phase, the simdization process is complete and the SIMD operations can be safely scheduled and register allocated.