Simplifies division and modulo by powers of two in PHI nodes.
New forward propagation pass simplifies DIV/MOD by powers of two into RSHIFT/BIT_AND within PHI nodes.
A new forward propagation pass, simplify_phi_result_movdiv, is introduced to simplify division and modulo operations where the divisor is a power of two within PHI nodes. It transforms DIV into RSHIFT and MOD into BIT_AND, provided certain conditions on the operands are met. This change resolves most use cases for PR101179 by enabling these simplifications for positive power-of-two divisors and specific conditions on the PHI node’s arguments.
In Details
This commit adds a new forward propagation step, simplify_phi_result_movdiv, to tree-ssa-forwprop.cc. It targets PHI nodes where an operand is a MOD or DIV operation whose divisor is a power of two. Under specific conditions (e.g., known positive divisor, or specific operand usage), it replaces MOD with BIT_AND and DIV with RSHIFT. This is a specialization of Richi's suggestion to push such simplifications out of match.pd and targets PR101179.
- forwprop
- Abbreviation for forward propagation, a compiler optimization technique that replaces variables with their definitions whenever possible to simplify subsequent computations.
- PHI node
- In SSA (Static Single Assignment) form, a PHI node is an instruction that merges values from different control flow paths. It represents a variable that may have different values depending on which path the program execution took.
- RSHIFT
- Right bit shift operation. Shifts the bits of a number to the right, effectively dividing by powers of two.
- BIT_AND
- Bitwise AND operation. Performs a logical AND operation on each pair of corresponding bits. Used here to replace modulo by powers of two.
- TRUNC_DIV
- Truncating division, where the result of a division is truncated towards zero.
- FLOOR_DIV
- Floor division, where the result of a division is rounded down to the nearest integer.
- TRUNC_MOD
- Truncating modulo operation, where the remainder of a division is taken, truncated towards zero.
- FLOOR_MOD
- Floor modulo operation, where the remainder of a division is taken, rounded down.