Fold overflow-free average idiom to fewer operations
GCC now simplifies a common overflow-safe integer average calculation into a more efficient form.
GCC’s pattern matching system (match.pd) has gained a new rule to simplify a common, overflow-free way of calculating the average of two integers. The idiom ((x >> 1) + (y >> 1)) + (x & y & 1) is now transformed into the mathematically equivalent but more efficient (x & y) + ((x ^ y) >> 1). This optimization reduces the number of operations, leading to performance improvements on various architectures, including aarch64, and is also beneficial for vectorization.
In Details
The match.pd file, which defines patterns for tree-ssa simplifications, now includes a rule to recognize and fold the ((x >> 1) + (y >> 1)) + (x & y & 1) average idiom. This form is known to be exact and overflow-free for signed and unsigned integers. The new pattern rewrites it to (x & y) + ((x ^ y) >> 1), which uses fewer operations (4 vs 6). This optimization is particularly relevant for vectorizers that might generate the six-operation form when a target lacks a specific halving-add instruction.
- match.pd
- A file within GCC that defines pattern matching rules for simplifying intermediate code representations. It allows the compiler to recognize common code sequences and replace them with more efficient equivalents.
- idiom
- A common and characteristic way of expressing something in programming. In this context, it refers to a specific pattern of arithmetic operations used to calculate an average.
- overflow-free
- An operation that is guaranteed not to exceed the maximum representable value or go below the minimum representable value for its data type.
- vectorizer
- A compiler component that transforms code to use SIMD (Single Instruction, Multiple Data) instructions, allowing a single operation to be applied to multiple data elements simultaneously.
- aarch64
- The 64-bit ARM architecture, commonly used in mobile devices and increasingly in servers and laptops.