Fold remainder of a remainder by a multiple
GCC simplifies nested modulo operations where the inner modulus divides the outer one, reducing redundant calculations.
GCC can now simplify expressions of the form (x % C1) % C2 when C2 is a divisor of C1. This optimization, implemented in the match.pd system, replaces the nested remainder operations with a single remainder operation x % C2, effectively removing one division from the generated code. This is beneficial for performance, as division operations are typically more expensive than modulo operations.
In Details
The match.pd file has been updated with a new simplification rule for nested remainder operations. The rule targets expressions (X % C1) % C2 where C2 divides C1. Mathematically, (X % C1) % C2 is equivalent to X % C2 under this condition. The simplification (X % C1) % C2 -> X % C2 eliminates one division instruction, provided C1 and C2 are constants and the divisibility condition holds. Special handling is included for remainders by -1 to avoid potential traps or issues with sanitizers.
- remainder
- The amount left over after division. In programming, the modulo operator (%) typically computes the remainder.
- multiple
- A number that can be divided by another number without a remainder. For example, 12 is a multiple of 4.
- 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.
- truncating remainder
- A type of remainder operation where the sign of the result matches the sign of the dividend. This is the behavior of the % operator in C and C++ for negative dividends.