match.pd, forwprop: Recognize long-multiply carries as 2-arg PHI
Improves long-multiply optimization by recognizing carry propagation in PHI nodes with specific base+pow2 patterns.
This commit enhances the forwprop (forward propagation) optimization pass to recognize and optimize long-multiply operations where the carry is expressed using a two-argument PHI node. This pattern, common in hand-written assembly, involves a PHI that conditionally adds a power of two. The pass now identifies these PHI structures and folds them into the long-multiply operation, improving the compiler’s ability to optimize these cases, particularly for the high part of the multiplication.
In Details
The forwprop pass gains new recognizers in match.pd for cond_carry_add and cond_carry_add_neg patterns. These recognize PHI nodes of the form PHI<base + pow2, base> guarded by an unsigned comparison, which often represent carry propagation in handwritten long-multiply code. When matched, the compiler can fold these into a 2N-bit multiply, specifically handling the HIGH_PART of the result. This addresses PR tree-optimization/107090 by improving the recognition of a specific carry-handling idiom.
- forwprop
- Forward propagation is an optimization pass in GCC that attempts to simplify expressions by replacing variables with their definitions as early as possible in the program flow. It's part of the SSA (Static Single Assignment) based optimization framework.
- match.pd
- A file within GCC that contains pattern-matching definitions for various intermediate code constructs, used by optimization passes to identify and transform specific code sequences.
- PHI node
- In Static Single Assignment (SSA) form, a PHI node is used at a join point of control flow to merge values from different predecessors. It indicates which version of a variable should be used based on the path taken through the control flow graph.
- long-multiply
- A multiplication operation where the result's bit-width is twice that of the operands (e.g., multiplying two 64-bit integers to produce a 128-bit result). Optimizing these operations is crucial for performance on platforms that may not have native hardware support for such wide multiplications.
- GIMPLE
- GCC's Internal Manipulation-code Generator and Evaluator. It is an intermediate representation (IR) used within GCC after the parsing and initial tree building, designed to be simpler and more amenable to optimization than the original AST.