match: Fold sum of MIN/MAX pair into a single expression.
Optimizes expressions like (a + b) - MIN(a, b) to simplify to MAX(a, b).
This commit introduces a new simplification rule in match.pd that folds expressions of the form (x + y) - MIN(x, y) into MAX(x, y). This algebraic identity holds for both integers and floating-point numbers (under certain conditions like reassociation). The optimization simplifies code by reducing the number of operations required, as demonstrated by an example reducing four instructions to one on AArch64.
In Details
The change adds a new simplification rule to match.pd for the pattern (PLUS_EXPR (x) (y)) - (MIN_EXPR (x) (y)) which simplifies to (MAX_EXPR (x) (y)). This relies on the identity x + y = MIN(x, y) + MAX(x, y). The rule is applicable to integers and floating-point types when reassociation is enabled and specific constraints (no signed zero honoring, no traps) are met. The operands of PLUS_EXPR, MIN_EXPR, and MAX_EXPR are assumed to have a canonical order, so no explicit commutation is needed on the MIN/MAX expressions.
- match.pd
- A file within GCC that defines pattern matching rules for the tree-SSA intermediate representation. These rules are used by optimization passes to simplify and transform code.
- PLUS_EXPR
- GCC's internal representation for an addition operation in the tree-SSA IR.
- MIN_EXPR / MAX_EXPR
- GCC's internal representation for minimum and maximum operations, respectively, in the tree-SSA IR.
- 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.
- reassociation
- An optimization transformation that changes the grouping of operands in an expression without changing the mathematical result. For example,
(a + b) + cmight be reassociated toa + (b + c). This is particularly important for floating-point arithmetic where different groupings can yield slightly different results due to precision limitations.