Vectorization Plan

Abstract

The vectorization transformation can be rather complicated, involving several potential alternatives, especially for outer-loops [1] but also possibly for innermost loops. These alternatives may have significant performance impact, both positive and negative. A cost model is therefore employed to identify the best alternative, including the alternative of avoiding any transformation altogether.

The Vectorization Plan is an explicit model for describing vectorization candidates. It serves for both optimizing candidates including estimating their cost reliably, and for performing their final translation into IR. This facilitates dealing with multiple vectorization candidates.

High-level Design

Vectorization Workflow

VPlan-based vectorization involves three major steps, taking a “scenario-based approach” to vectorization planning:

1. Legal Step: check if a loop can be legally vectorized; encode constraints and artifacts if so.
2. Plan Step:
   1. Build initial VPlans following the constraints and decisions taken by Legal Step 1, and compute their cost.
   2. Apply optimizations to the VPlans, possibly forking additional VPlans. Prune sub-optimal VPlans having relatively high cost.
3. Execute Step: materialize the best VPlan. Note that this is the only step that modifies the IR.

Design Guidelines

In what follows, the term “input IR” refers to code that is fed into the vectorizer whereas the term “output IR” refers to code that is generated by the vectorizer. The output IR contains code that has been vectorized or “widened” according to a loop Vectorization Factor (VF), and/or loop unroll-and-jammed according to an Unroll Factor (UF). The design of VPlan follows several high-level guidelines:

1. Analysis-like: building and manipulating VPlans must not modify the input IR. In particular, if the best option is not to vectorize at all, the vectorization process terminates before reaching Step 3, and compilation should proceed as if VPlans had not been built.
2. Align Cost & Execute: each VPlan must support both estimating the cost and generating the output IR code, such that the cost estimation evaluates the to-be-generated code reliably.
3. Support vectorizing additional constructs:
   1. Outer-loop vectorization. In particular, VPlan must be able to model the control-flow of the output IR which may include multiple basic-blocks and nested loops.
   2. SLP vectorization.
   3. Combinations of the above, including nested vectorization: vectorizing both an inner loop and an outer-loop at the same time (each with its own VF and UF), mixed vectorization: vectorizing a loop with SLP patterns inside [4], (re)vectorizing input IR containing vector code.
   4. Function vectorization [2].
4. Support multiple candidates efficiently. In particular, similar candidates related to a range of possible VF’s and UF’s must be represented efficiently. Potential versioning needs to be supported efficiently.
5. Support vectorizing idioms, such as interleaved groups of strided loads or stores. This is achieved by modeling a sequence of output instructions using a “Recipe”, which is responsible for computing its cost and generating its code.
6. Encapsulate Single-Entry Single-Exit regions (SESE). During vectorization such regions may need to be, for example, predicated and linearized, or replicated VF*UF times to handle scalarized and predicated instructions. Innerloops are also modelled as SESE regions.

Low-level Design

The low-level design of VPlan comprises of the following classes.

LoopVectorizationPlanner:  A LoopVectorizationPlanner is designed to handle the vectorization of a loop or a loop nest. It can construct, optimize and discard one or more VPlans, each VPlan modelling a distinct way to vectorize the loop or the loop nest. Once the best VPlan is determined, including the best VF and UF, this VPlan drives the generation of output IR. VPlan:A model of a vectorized candidate for a given input IR loop or loop nest. This candidate is represented using a Hierarchical CFG. VPlan supports estimating the cost and driving the generation of the output IR code it represents. Hierarchical CFG:  A control-flow graph whose nodes are basic-blocks or Hierarchical CFG’s. The Hierarchical CFG data structure is similar to the Tile Tree [5], where cross-Tile edges are lifted to connect Tiles instead of the original basic-blocks as in Sharir [6], promoting the Tile encapsulation. The terms Region and Block are used rather than Tile [5] to avoid confusion with loop tiling. VPBlockBase:The building block of the Hierarchical CFG. A pure-virtual base-class of VPBasicBlock and VPRegionBlock, see below. VPBlockBase models the hierarchical control-flow relations with other VPBlocks. Note that in contrast to the IR BasicBlock, a VPBlockBase models its control-flow successors and predecessors directly, rather than through a Terminator branch or through predecessor branches that “use” the VPBlockBase. VPBasicBlock:VPBasicBlock is a subclass of VPBlockBase, and serves as the leaves of the Hierarchical CFG. It represents a sequence of output IR instructions that will appear consecutively in an output IR basic-block. The instructions of this basic-block originate from one or more VPBasicBlocks. VPBasicBlock holds a sequence of zero or more VPRecipes that model the cost and generation of the output IR instructions. VPRegionBlock:VPRegionBlock is a subclass of VPBlockBase. It models a collection of VPBasicBlocks and VPRegionBlocks which form a SESE subgraph of the output IR CFG. A VPRegionBlock may indicate that its contents are to be replicated a constant number of times when output IR is generated, effectively representing a loop with constant trip-count that will be completely unrolled. This is used to support scalarized and predicated instructions with a single model for multiple candidate VF’s and UF’s. VPRecipeBase:A pure-virtual base class modeling a sequence of one or more output IR instructions, possibly based on one or more input IR instructions. These input IR instructions are referred to as “Ingredients” of the Recipe. A Recipe may specify how its ingredients are to be transformed to produce the output IR instructions; e.g., cloned once, replicated multiple times or widened according to selected VF. VPTransformState:  Stores information used for generating output IR, passed from LoopVectorizationPlanner to its selected VPlan for execution, and used to pass additional information down to VPBlocks and VPRecipes.

Related LLVM components

1. SLP Vectorizer: one can compare the VPlan model with LLVM’s existing SLP tree, where TSLP [3] adds Plan Step 2.b.
2. RegionInfo: one can compare VPlan’s H-CFG with the Region Analysis as used by Polly [7].

References

[1]	“Outer-loop vectorization: revisited for short SIMD architectures”, Dorit Nuzman and Ayal Zaks, PACT 2008.

[2]	“Proposal for function vectorization and loop vectorization with function calls”, Xinmin Tian, [cfe-dev]., March 2, 2016. See also review.

[3]	“Throttling Automatic Vectorization: When Less is More”, Vasileios Porpodas and Tim Jones, PACT 2015 and LLVM Developers’ Meeting 2015.

[4]	“Exploiting mixed SIMD parallelism by reducing data reorganization overhead”, Hao Zhou and Jingling Xue, CGO 2016.

[5]	(1, 2) “Register Allocation via Hierarchical Graph Coloring”, David Callahan and Brian Koblenz, PLDI 1991

[6]	“Structural analysis: A new approach to flow analysis in optimizing compilers”, M. Sharir, Journal of Computer Languages, Jan. 1980

[7]	“Enabling Polyhedral Optimizations in LLVM”, Tobias Grosser, Diploma thesis, 2011.

[8]	“Introducing VPlan to the Loop Vectorizer”, Gil Rapaport and Ayal Zaks, European LLVM Developers’ Meeting 2017.