IVOPT improvement patch

[Zdenek Dvorak]

Hi,

> >> @@ -3811,6 +3841,9 @@ get_computation_cost_at (struct ivopts_d
> >> Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â &offset, depends_on));
> >> Â  Â  Â }
> >>
> >> + Â /* Loop invariant computation. Â */
> >> + Â cost.cost /= avg_loop_niter (data->current_loop);
> >> +
> >
> > This is wrong, at least some parts of the computation here are not loop invariant.
> 
> Which part is not loop invariant?

it depends on the actual form of the use.  But in the most general case, the
computation whose cost is determined here is ubase + ratio * (var - cbase), and
no part of this is loop invariant (except for the force_var_costs of ubase and cbase).

> >> @@ -4056,20 +4090,16 @@ may_eliminate_iv (struct ivopts_data *da
> >> Â  Â /* If not, and if this is the only possible exit of the loop, see whether
> >> Â  Â  Â  we can get a conservative estimate on the number of iterations of the
> >> Â  Â  Â  entire loop and compare against that instead. Â */
> >> - Â else if (loop_only_exit_p (loop, exit))
> >> + Â else
> >
> > This change is wrong, the test is necessary. Â See
> > http://gcc.gnu.org/ml/gcc-patches/2008-07/msg00146.html
> > and the following discussion.
> >
> 
> The original fix to the problem is too conservative -- if there is
> only one exit has the test to be replaced, it should be ok to do it,
> right?

Yes.  But I do not see your point -- your patch removes the loop_only_exit_p
test, which is necessary.

> >> Â  Â  Â {
> >> Â  Â  Â  Â double_int period_value, max_niter;
> >> Â  Â  Â  Â if (!estimated_loop_iterations (loop, true, &max_niter))
> >> Â  Â  Â  return false;
> >> Â  Â  Â  Â period_value = tree_to_double_int (period);
> >> - Â  Â  Â if (double_int_ucmp (max_niter, period_value) >= 0)
> >> + Â  Â  Â if (double_int_ucmp (max_niter, period_value) > 0)
> >> Â  Â  Â  return false;
> >> Â  Â  Â }
> >
> > This also seems wrong (or at least inconsistent with that is done for
> > the constant number of iterations).
> 
> This looks correct to me. 

I think you are right; but, then the preceding test for tree_int_cst_lt
should be changed as well (so that both conditions are the same).
It would also be nice to add testcases for the boundary values to the
testsuite, to make sure we are not making an off-by-one error.

Zdenek