Hi Zdenek, On 05/21/2011 07:59 PM, Tom de Vries wrote: > On 05/21/2011 02:24 PM, Zdenek Dvorak wrote: >>> * tree-ssa-loop-ivopts.c (may_eliminate_iv): Fix >>> estimated_loop_iterations comparison. >> >> I don't think this part is correct, though: >> >>> Index: gcc/tree-ssa-loop-ivopts.c >>> =================================================================== >>> --- gcc/tree-ssa-loop-ivopts.c (revision 173734) >>> +++ gcc/tree-ssa-loop-ivopts.c (working copy) >>> @@ -4391,8 +4391,13 @@ may_eliminate_iv (struct ivopts_data *da >>> { >>> if (!estimated_loop_iterations (loop, true, &max_niter)) >>> return false; >>> - /* The loop bound is already adjusted by adding 1. */ >>> - if (double_int_ucmp (max_niter, period_value) > 0) >>> + /* The max iterations applies also to the number of times >>> the loop >>> + exit condition is executed. The number of distinct >>> values of >>> + the cand is period_value + 1. So, test for >>> + 'period_value + 1 >= max_iterations'. >>> + */ >>> + period_value = double_int_add (period_value, double_int_one); >>> + if (double_int_ucmp (max_niter, period_value) > 0) >>> return false; >>> } >>> else >> > >> max_niter is the upper bound on the number of iterations of the loop, i.e., >> the number >> of executions of its latch edge. > > max_niter is set from estimated_loop_iterations, meaning from > loop->nb_iterations_upper_bound. > > consider: > ... > void f(int *a) > { > int i; > > for (i = 0; i < 10; ++i) > a[i] = 0; > } > ... > > at ivopts, it looks like this (compiled with -Os -fno-tree-vrp > -fno-tree-dominator-opts -fno-tree-loop-ivcanon, to get a source-like > representation) > ... > f (int * a) > { > int i; > int * D.2009; > unsigned int D.2008; > unsigned int i.0; > > <bb 2>: > goto <bb 4>; > > <bb 3>: > i.0_3 = (unsigned int) i_1; > D.2008_4 = i.0_3 * 4; > D.2009_6 = a_5(D) + D.2008_4; > *D.2009_6 = 0; > i_7 = i_1 + 1; > > <bb 4>: > # i_1 = PHI <0(2), i_7(3)> > if (i_1 <= 9) > goto <bb 3>; > else > goto <bb 5>; > > <bb 5>: > return; > > } > ... > > > The header block of the loop is bb 4, the latch block is bb 3: > ... > (gdb) p loop.header.index > $4 = 4 > (gdb) p loop.latch.index > $5 = 3 > ... > > The number of times the latch edge is executed, is 10. > > But loop->nb_iterations_upper_bound, or max_niter is 11: > ... > (gdb) p *loop > $1 = {num = 1, ninsns = 0, header = 0xf7dc2440, latch = 0xf7dc2400, > lpt_decision > = {decision = LPT_NONE, times = 0}, av_ninsns = 0, num_nodes = 2, superloops = > 0xf7db6ee8, inner = 0x0, next = 0x0, > aux = 0x0, nb_iterations = 0xf7d3d540, nb_iterations_upper_bound = {low = > 11, > high = 0}, nb_iterations_estimate = {low = 11, high = 0}, any_upper_bound = 1 > '\001', any_estimate = 1 '\001', > can_be_parallel = 0 '\000', estimate_state = EST_AVAILABLE, bounds = > 0xf7d3da2c, exits = 0xf7dc3d70} > ... > >> Therefore, the control induction variable of the loop >> will (at the exit statement) achieve at most max_niter + 1 different values. > > Based on what I observe, I'd say the control induction variable of the loop > will > achieve at most max_niter different values. >
Any thoughts on my observations above? Thanks, - Tom