match.pd: Combine pairs of vector reductions into single operations.
Optimizes vector reductions by combining two separate reductions into a single elementwise operation.
This optimization in match.pd combines two vector reductions that feed into the same scalar operation into a single reduction of an elementwise operation. This transformation, REDUC(a) op REDUC(b) -> REDUC(a op b), trades a potentially expensive lane-crossing reduction for a cheaper elementwise operation, significantly reducing instruction count for operations like MIN, MAX, AND, IOR, XOR, and floating-point sums.
In Details
This commit adds new simplification rules to match.pd for combining vector reductions. The pattern REDUC (a) op REDUC (b) is transformed into REDUC (a op b). This applies to associative and commutative reductions like MIN, MAX, AND, IOR, XOR, and floating-point SUM. For integer SUM, the reduction is performed in an unsigned type to handle wrap-around correctly, while floating-point SUM leverages reassociation. The rule requires the narrow operation (e.g., vaddvq_s32) to be available and considers the cost of lane-crossing reductions versus elementwise operations. It also preserves int…
- match.pd
- A file within GCC that defines pattern matching rules for the tree-SSA (Static Single Assignment) intermediate representation. These rules are used by optimization passes to simplify and transform code.
- vector reduction
- An operation that combines all elements of a vector into a single scalar value. Examples include summing all elements, finding the minimum or maximum element, or performing a bitwise AND across all elements.
- elementwise operation
- An operation that is applied independently to each corresponding element of two vectors.
- lane-crossing reduction
- A type of vector reduction that involves moving data between different lanes (elements) of a vector processor, often implemented using shuffle or transpose instructions, which can be relatively expensive.
- SIMD
- Single Instruction, Multiple Data. A class of parallel computers in Flynn's taxonomy that perform the same operation on multiple data points simultaneously.
- tree-SSA
- GCC's intermediate representation (IR) that combines features of abstract syntax trees (AST) and Static Single Assignment (SSA) form, used for performing optimizations.