Submitter | Tom de Vries |
---|---|

Date | May 20, 2011, 9:56 a.m. |

Message ID | <4DD63AE1.7070600@codesourcery.com> |

Download | mbox | patch |

Permalink | /patch/96577/ |

State | New |

Headers | show |

## Comments

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 <tom@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

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

On Sat, May 21, 2011 at 5:24 AM, Zdenek Dvorak <rakdver@kam.mff.cuni.cz> wrote: > 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 <tom@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. > This caused: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49124 H.J.

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

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

## Patch

Index: gcc/tree-ssa-loop-niter.c =================================================================== --- gcc/tree-ssa-loop-niter.c (revision 173734) +++ gcc/tree-ssa-loop-niter.c (working copy) @@ -2835,6 +2835,54 @@ infer_loop_bounds_from_array (struct loo that signed arithmetics in STMT does not overflow. */ static void +infer_loop_bounds_from_pointer_arith (struct loop *loop, gimple stmt) +{ + tree def, base, step, scev, type, low, high; + tree var, ptr; + + if (!is_gimple_assign (stmt) + || gimple_assign_rhs_code (stmt) != POINTER_PLUS_EXPR) + return; + + def = gimple_assign_lhs (stmt); + if (TREE_CODE (def) != SSA_NAME) + return; + + type = TREE_TYPE (def); + if (!nowrap_type_p (type)) + return; + + ptr = gimple_assign_rhs1 (stmt); + if (!expr_invariant_in_loop_p (loop, ptr)) + return; + + var = gimple_assign_rhs2 (stmt); + if (TYPE_PRECISION (type) != TYPE_PRECISION (TREE_TYPE (var))) + return; + + scev = instantiate_parameters (loop, analyze_scalar_evolution (loop, def)); + if (chrec_contains_undetermined (scev)) + return; + + base = initial_condition_in_loop_num (scev, loop->num); + step = evolution_part_in_loop_num (scev, loop->num); + + if (!base || !step + || TREE_CODE (step) != INTEGER_CST + || tree_contains_chrecs (base, NULL) + || chrec_contains_symbols_defined_in_loop (base, loop->num)) + return; + + low = lower_bound_in_type (type, type); + high = upper_bound_in_type (type, type); + + record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true); +} + +/* Determine information about number of iterations of a LOOP from the fact + that signed arithmetics in STMT does not overflow. */ + +static void infer_loop_bounds_from_signedness (struct loop *loop, gimple stmt) { tree def, base, step, scev, type, low, high; @@ -2907,7 +2955,10 @@ infer_loop_bounds_from_undefined (struct infer_loop_bounds_from_array (loop, stmt, reliable); if (reliable) - infer_loop_bounds_from_signedness (loop, stmt); + { + infer_loop_bounds_from_signedness (loop, stmt); + infer_loop_bounds_from_pointer_arith (loop, stmt); + } } } 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