https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109233
Richard Biener <rguenth at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |hubicka at gcc dot gnu.org
--- Comment #12 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Andrew Macleod from comment #11)
> (In reply to Aldy Hernandez from comment #10)
> > (In reply to Jakub Jelinek from comment #8)
> >
> > > And on the ranger side why we have determined the [0, 5] range rather than
> > > [0, 4], whether it is related to inaccurate number of iterations
> > > estimation,
> > > or ranger using it incorrectly, ...
> >
> > The [0, 5] is actually coming from SCEV, which ranger is using to refine the
> > range. Presumably, ranger is doing worse than SCEV, because it doesn't
> > improve it.
> >
> > $ grep 'Loops range fo' a.c.*evrp
> > Loops range found for i_3: [irange] int [0, 5] NONZERO 0x7 and calculated
> > range :[irange] int [-2147483647, +INF]
> > Loops range found for i_3: [irange] int [0, 5] NONZERO 0x7 and calculated
> > range :[irange] int [0, 6] NONZERO 0x7
> >
> > Perhaps Andrew can pontificate on the recalculations / iterations / etc.
>
> Im not sure what to add.
>
>
> SCEV tells us its [0,5] .
>
> Statement MEM <struct T> [(struct S *)t_9(D)].f[i_3].y = 1;
> is executed at most 4 (bounded by 4) + 1 times in loop 1.
> Induction variable (int) 0 + 1 * iteration does not wrap in statement MEM
> <struct T> [(struct S *)t_9(D)].f[i_3].z = 2;
> in loop 1.
> Statement MEM <struct T> [(struct S *)t_9(D)].f[i_3].z = 2;
> is executed at most 4 (bounded by 4) + 1 times in loop 1.
> Induction variable (int) 0 + 1 * iteration does not wrap in statement MEM
> <struct T> [(struct S *)t_9(D)].f[i_3].x = 3;
> in loop 1.
> Statement MEM <struct T> [(struct S *)t_9(D)].f[i_3].x = 3;
> is executed at most 4 (bounded by 4) + 1 times in loop 1.
> Induction variable (int) 0 + 1 * iteration does not wrap in statement MEM
> <struct T> [(struct S *)t_9(D)].f[i_3].z = 2;
> in loop 1.
> Statement MEM <struct T> [(struct S *)t_9(D)].f[i_3].z = 2;
> is executed at most 4 (bounded by 4) + 1 times in loop 1.
> Trying to walk loop body to reduce the bound.
> Found better loop bound 5
>
>
> I see nothing else in the IL to help ranger make any other decision, so it
> defers to SCEV, and the transformtion to rewrite the array index to [5]
> seems spot on, its the only possible value that can be there... THe branch
> condition is:
> _1 = t_9(D)->h;
> i.0_2 = (unsigned int) i_3;
> if (_1 > i.0_2)
> goto <bb 3>;
>
> Ranger knows nothing of the value of _1, and with i_3 being [0,5] there is
> nothing that I can see that ranger could do
>
> Why does scev decide 5 is a better bound?
It's the first bound it finds, based on the access. The issue is that
the accesses are after the exit test and we're doing adjustments to
the estimates in discover_iteration_bound_by_body_walk like
/* Exit terminates loop at given iteration, while non-exits produce
undefined
effect on the next iteration. */
if (!elt->is_exit)
{
bound += 1;
but note we're always setting elt->is_exit to false for bounds discovered
from array refs (see record_estimate call from record_nonwrapping_iv from
idx_infer_loop_bounds). I think there's either some duplicate accounting
or confusion as to what is_exit means though. Since we record the number
of latch executions the estimate from blocks dominated by the exit test
should be directly usable as estimate while those before the exit test
would need adjustment in the other direction?
is_exit is documented as
/* True if, after executing the statement BOUND + 1 times, we will
leave the loop; that is, all the statements after it are executed at most
BOUND times. */
bool is_exit;
the "that is, all the statements after it are executed at most BOUND times"
really suggests this is about an actual exit statement and not about
position relative to the exit. In the function of the above loop we
translate the stmt execution bound to a bound on the number of latch
executions (so the last time an exit stmt is executed it will exit the
loop, so no +1).
Note this is a tricky area and we have many related bugreports, but
testsuite coverage should be quite good here.
Btw, the actual thing is that the IV as analyzed by SCEV can get the
value 5, the actual array references will not be executed but we must
exit the loop in that case. That's something not covered by niter
analysis / SCEV directly but if you use max_stmt_executions () on
blocks following the exit test you should be able to determine that
i != 5 is always true. So the fix is probably somewhere in ranger
determining that on the exit test edge remaining in the loop, the
bounds on other IVs can be adjusted by one (but only on that edge).
