match.pd: Optimize power-of-two round-up calculations
Optimizes power-of-two round-up calculations by folding an identity, reducing instruction count on AArch64.
This commit optimizes power-of-two round-up calculations by applying an algebraic identity that reduces the number of instructions required. The optimization targets expressions of the form ((x - 1) | C) + 1, where C is a power-of-two minus one. The new form, (x + C) & -(C + 1), is more efficient, especially for wrapping arithmetic. This change reduces the instruction count for such operations on scalar and vector integral types, demonstrated by a reduction from three to two instructions on AArch64.
In Details
A new simplification rule has been added to match.pd for the pattern (((X - 1) | C) + 1), where C is a constant representing 2^k - 1. This pattern is folded into (X + C) & -(C + 1) (or (X + C) & -(2^k)). This transformation is applied to scalar and vector integral types. The use of :s on the inclusive-or expression ensures that the fold does not introduce unnecessary work if the intermediate value remains live. This optimization is particularly effective for constant powers of two and benefits code that frequently performs power-of-two rounding.
- match.pd
- A file within GCC that contains pattern matching rules used for optimizing code. These rules describe how to transform certain code structures into more efficient equivalents.
- Round up
- An arithmetic operation that increases a number to the nearest multiple of a specified value (e.g., rounding up to the nearest 10). In the context of power-of-two rounding, it finds the smallest power of two that is greater than or equal to the input number.
- AArch64
- The 64-bit ARM architecture. GCC supports generating code for this architecture.
- SIMD
- Single Instruction, Multiple Data. A class of parallel computers in Flynn's taxonomy. SIMD machines exploit data-level parallelism by performing the same operation on multiple data points simultaneously using specialized instructions.
- Inclusive OR
- A bitwise operation where the result has a bit set to 1 if that bit is set in either of the operands. Also known as the bitwise OR operator.