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. > Conversely, > the number of distinct values that the control iv can represent is period + 1 > (naming of > the "period" variable is a bit missleading). agree. Thanks, - Tom