Re: [PATCH PR45098, 7/10] Nowrap limits iterations
Hi Zdenek, On 05/31/2011 10:04 AM, Zdenek Dvorak wrote: Hi, As far as I can tell, what is current calculated in i_bound (and assigned to nb_iterations_upper_bound), is the maximum amount of times any statement in the loop is executed, where any includes exit tests. Differently put, the maximum amount of times the loop header is executed. hmm... this is rather confusing, I don't really recall why I gave nb_iterations_upper_bound a different semantics from any other instance of what # of iterations of a loop means. This is confirmed by this comment in tree-vrp.c: /* Try to use estimated number of iterations for the loop to constrain the final value in the evolution. We are interested in the number of executions of the latch, while nb_iterations_upper_bound includes the last execution of the exit test. */ I modified the patch to improved the comment. I think a better fix would be to make the nb_iterations_upper_bound semantics consistent with that of nb_iterations. Let me try to do it, hopefully this should be mostly mechanical, This patch changes the semantics of nb_iterations_upper_bound and nb_iterations_estimate, to mean: the amount of latch executions. That change is countered at all use sites, except for tree-ssa-loop-ivopts.c:may_eliminate_iv. Passed x86_64 bootstrapping and reg-testing. OK for trunk? 2011-06-10 Zdenek Dvorak o...@ucw.cz Tom de Vries t...@codesourcery.com PR target/45098 * cfgloop.h (nb_iterations_upper_bound, nb_iterations_estimate): Document changed semantics. (max_stmt_executions, max_stmt_executions_int): Declare. * tree-data-ref.c (estimated_loop_iterations) (estimated_loop_iterations_int): Move functions... * tree-ssa-loop-niter.c (estimated_loop_iterations) (estimated_loop_iterations_int): here. (record_estimate): Change nb_iterations_upper_bound and nb_iterations_estimate semantics. (max_stmt_executions, max_stmt_executions_int): New function. * tree-data-ref.c (estimated_loop_iterations_tree): Rename to ... (max_stmt_executions_tree): this. (analyze_miv_subscript): Use max_stmt_executions_tree instead of estimated_loop_iterations_tree. tree-ssa-loop-ivopts.c (avg_loop_niter): Use max_stmt_executions_int instead of estimated_loop_iterations_int. * predict.c (predict_loops): Idem. * tree-parloops.c (parallelize_loops): Idem. * tree-data-ref.c (analyze_siv_subscript_cst_affine) (compute_overlap_steps_for_affine_1_2, analyze_subscript_affine_affine) (init_omega_for_ddr_1): Idem. * tree-ssa-loop-prefetch.c (determine_loop_nest_reuse) (loop_prefetch_arrays): Idem * graphite-sese-to-poly.c (build_loop_iteration_domains): Use max_stmt_executions instead of estimated_loop_iterations. * tree-data-ref.c (estimated_loop_iterations_tree): Idem. * tree-vrp.c (adjust_range_with_scev): Use estimated_loop_iterations instead of nb_iterations_upper_bound. Index: gcc/tree-vrp.c === --- gcc/tree-vrp.c (revision 174810) +++ gcc/tree-vrp.c (working copy) @@ -3403,44 +3403,42 @@ adjust_range_with_scev (value_range_t *v tmax = TYPE_MAX_VALUE (type); /* Try to use estimated number of iterations for the loop to constrain the - final value in the evolution. - We are interested in the number of executions of the latch, while - nb_iterations_upper_bound includes the last execution of the exit test. */ + final value in the evolution. */ if (TREE_CODE (step) == INTEGER_CST - loop-any_upper_bound - !double_int_zero_p (loop-nb_iterations_upper_bound) is_gimple_val (init) (TREE_CODE (init) != SSA_NAME || get_value_range (init)-type == VR_RANGE)) { - value_range_t maxvr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }; - double_int dtmp; - bool unsigned_p = TYPE_UNSIGNED (TREE_TYPE (step)); - int overflow = 0; + double_int nit; - dtmp = double_int_mul_with_sign (tree_to_double_int (step), - double_int_sub ( - loop-nb_iterations_upper_bound, - double_int_one), - unsigned_p, overflow); - /* If the multiplication overflowed we can't do a meaningful - adjustment. Likewise if the result doesn't fit in the type - of the induction variable. For a signed type we have to - check whether the result has the expected signedness which - is that of the step as nb_iterations_upper_bound is unsigned. */ - if (!overflow - double_int_fits_to_tree_p (TREE_TYPE (init), dtmp) - (unsigned_p - || ((dtmp.high ^ TREE_INT_CST_HIGH (step)) = 0))) + if (estimated_loop_iterations (loop,
Re: [PATCH PR45098, 7/10] Nowrap limits iterations
On 05/30/2011 02:38 PM, Zdenek Dvorak wrote: Hi, 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: this is a bit strange, it looks like the # of iterations estimation is setting nb_iterations_upper_bound too conservatively (or I gave nb_iterations_upper_bound a different semantics than I remember -- but both my memory and the comment in cfgloop.h suggest that nb_iterations_upper_bound = nb_iterations, i.e., that it should be 10 in your example), The actual values of nb_iterations_upper_bound are determined by this code fragment in record_estimate. /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT is true if the loop is exited immediately after STMT, and this exit is taken at last when the STMT is executed BOUND + 1 times. REALISTIC is true if BOUND is expected to be close to the real number of iterations. UPPER is true if we are sure the loop iterates at most BOUND times. I_BOUND is an unsigned double_int upper estimate on BOUND. */ static void record_estimate (struct loop *loop, tree bound, double_int i_bound, gimple at_stmt, bool is_exit, bool realistic, bool upper) { ... /* Update the number of iteration estimates according to the bound. If at_stmt is an exit, then every statement in the loop is executed at most BOUND + 1 times. If it is not an exit, then some of the statements before it could be executed BOUND + 2 times, if an exit of LOOP is before stmt. */ exit = single_exit (loop); if (is_exit || (exit != NULL dominated_by_p (CDI_DOMINATORS, exit-src, gimple_bb (at_stmt delta = double_int_one; else delta = double_int_two; i_bound = double_int_add (i_bound, delta); As far as I can tell, what is current calculated in i_bound (and assigned to nb_iterations_upper_bound), is the maximum amount of times any statement in the loop is executed, where any includes exit tests. Differently put, the maximum amount of times the loop header is executed. This is confirmed by this comment in tree-vrp.c: /* Try to use estimated number of iterations for the loop to constrain the final value in the evolution. We are interested in the number of executions of the latch, while nb_iterations_upper_bound includes the last execution of the exit test. */ I modified the patch to improved the comment. Ok for trunk? Thanks, - Tom 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,14 @@ 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) + /* (a) loop-nb_iterations_upper_bound (assigned to max_niter) + includes the last execution of the exit test. + (b) The number of distinct values of the cand is + period_value + 1. + So, the transformation is allowed if + max_niter = period_value + 1. */ + period_value = double_int_add (period_value, double_int_one); + if (double_int_ucmp (max_niter, period_value) 0) return false; } else
Re: [PATCH PR45098, 7/10] Nowrap limits iterations
Hi, As far as I can tell, what is current calculated in i_bound (and assigned to nb_iterations_upper_bound), is the maximum amount of times any statement in the loop is executed, where any includes exit tests. Differently put, the maximum amount of times the loop header is executed. hmm... this is rather confusing, I don't really recall why I gave nb_iterations_upper_bound a different semantics from any other instance of what # of iterations of a loop means. This is confirmed by this comment in tree-vrp.c: /* Try to use estimated number of iterations for the loop to constrain the final value in the evolution. We are interested in the number of executions of the latch, while nb_iterations_upper_bound includes the last execution of the exit test. */ I modified the patch to improved the comment. I think a better fix would be to make the nb_iterations_upper_bound semantics consistent with that of nb_iterations. Let me try to do it, hopefully this should be mostly mechanical, Zdenek
Re: [PATCH PR45098, 7/10] Nowrap limits iterations
Hi, 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: this is a bit strange, it looks like the # of iterations estimation is setting nb_iterations_upper_bound too conservatively (or I gave nb_iterations_upper_bound a different semantics than I remember -- but both my memory and the comment in cfgloop.h suggest that nb_iterations_upper_bound = nb_iterations, i.e., that it should be 10 in your example), Zdenek
Re: [PATCH PR45098, 7/10] Nowrap limits iterations
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
Re: [PATCH PR45098, 7/10] Nowrap limits iterations
Hi, Would it be possible to add the handling of these cases to estimate_numbers_of_iterations, rather than doing it just for ivopts? Yes, I did that now. Thanks, - Tom 2011-05-05 Tom de Vries t...@codesourcery.com PR target/45098 * tree-ssa-loop-niter.c (infer_loop_bounds_from_pointer_arith): New function. (infer_loop_bounds_from_undefined): Use new function. this is OK. * 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. Therefore, the control induction variable of the loop will (at the exit statement) achieve at most max_niter + 1 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). Thus, the correct test is # of available values = # of required values, equivalently period + 1 = max_niter + 1, equivalently period = max_niter, i.e., the current test. Zdenek
Re: [PATCH PR45098, 7/10] Nowrap limits iterations
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