tree-optimization: Recognize CLZ loop for signed non-negative values.
Compiler now recognizes CLZ (count leading zeros) optimization for loops involving signed non-negative values.
The compiler’s loop iteration counting has been improved to recognize Count Leading Zeros (CLZ) optimizations for loops that use signed arithmetic right shifts on non-negative values. Previously, a strict unsigned type check prevented this optimization. The change modifies the is_rshift_by_1 function and adds non-negativity checks to loop iteration counting, enabling more efficient code generation for these cases.
In Details
The tree-ssa-loop-niter.cc pass, specifically number_of_iterations_cltz and number_of_iterations_cltz_complement, now correctly identifies opportunities for CLZ optimization when signed arithmetic right shifts operate on non-negative values. This is achieved by relaxing the TYPE_UNSIGNED restriction in is_rshift_by_1 and introducing range analysis (range_on_edge) to verify the non-negativity of the loop's preheader input. This fixes PR tree-optimization/125734.
- CLZ
- Count Leading Zeros. An instruction that counts the number of zero bits from the most significant bit to the first set bit.
- arithmetic right shift
- A right bit shift operation that preserves the sign bit of the value. For non-negative numbers, it is equivalent to a logical right shift.
- GENERIC
- GCC's first intermediate representation, a tree-based representation of the program.
- SSA
- Static Single Assignment form. An intermediate representation where every variable is assigned exactly once, simplifying many analyses and optimizations.