Fold inequality spelling of divisibility
Extends divisibility optimization to handle inequality conditions.
GCC now optimizes divisibility checks involving inequalities, similar to how it handles equalities. Previously, an expression like x / y * y == x could be simplified to x % y == 0. This change extends that optimization to also cover x / y * y != x, which simplifies to x % y != 0. This optimization can lead to more efficient code generation, as demonstrated by an example on AArch64.
In Details
The pattern matching in match.pd has been extended to recognize and fold expressions involving the inequality spelling of divisibility. The existing fold x / y * y == x => x % y == 0 is now complemented by x / y * y != x => x % y != 0. This allows the compiler to replace division and multiplication sequences with a modulo operation when checking for non-divisibility, potentially enabling simpler and faster code generation, especially on architectures where modulo operations are more efficient than the division-multiplication sequence.
- match.pd
- A file within GCC that defines patterns for matching and transforming intermediate representation (IR) code during optimization. It's part of the pattern-based optimization framework.
- fold
- An optimization technique where the compiler replaces an expression with a simpler, equivalent one, often by pre-calculating values or using algebraic identities.
- divisibility
- The property of one integer being perfectly divisible by another, meaning the remainder of the division is zero.
- IR
- Intermediate Representation. A low-level code representation used internally by compilers between the parsing of source code and the generation of machine code. GCC uses several IRs, including GENERIC and GIMPLE.