ivopts: Fix loop bound calculation for eliminated IVs
Corrects loop bound logic when eliminating induction variables with less-than comparisons to prevent incorrect pointer arithmetic and out-of-bounds access.
This patch fixes a bug in the induction variable (IV) elimination optimization when the loop exit condition involves a less-than comparison. The previous implementation could unsoundly compute loop bounds, leading to incorrect pointer arithmetic or even out-of-bounds memory access, particularly when loops execute zero times or when offsets are large and wrap around the address space. The fix recomputes the bound more robustly and enforces conditions for safe unsigned comparisons.
In Details
The iv_elimination_compare_lt pass, which transforms loops like for (i=a; i<b; ++i) to for (p < p_0 - a + b) where p = base + i, has been corrected. It now recomputes the bound base + step * b - step * a by converting a and b to the offset type separately, ensuring value preservation. It also adds checks for non-negative, non-overflowing scaled offsets and requires an unsigned comparison for may_be_zero cases to prevent incorrect loop termination or runaway memory access.
- ivopts
- A GCC optimization pass focused on induction variables, which are variables whose values change in a regular, arithmetic progression with each iteration of a loop. Optimizations often involve eliminating or simplifying these variables.
- induction variable (IV)
- A variable within a loop whose value is updated arithmetically in each iteration, typically used as a loop counter or to access array elements.
- loop bound
- The condition that determines when a loop should terminate. In this context, it refers to the calculated value that the induction variable or related pointer must not exceed.
- pointer arithmetic
- Performing arithmetic operations (addition, subtraction) on memory addresses stored in pointers. The result is a new address, adjusted by the size of the data type the pointer points to.
- address space
- The range of all possible memory addresses that a processor can access. Operations that exceed these bounds can lead to segmentation faults or undefined behavior.