Re: Fix array bound niter estimate (PR middle-end/54937)

[Jan Hubicka <hubicka at ucw dot cz>]

> > +static void
> > +maybe_lower_iteration_bound (struct loop *loop)
> > +{
> > +  pointer_set_t *not_executed_last_iteration = pointer_set_create ();
> > +  pointer_set_t *visited;
> > +  struct nb_iter_bound *elt;
> > +  bool found = false;
> > +  VEC (basic_block, heap) *queue = NULL;
> > +
> > +  for (elt = loop->bounds; elt; elt = elt->next)
> > +    {
> > +      if (!elt->is_exit
> > +	  && elt->bound.ult (loop->nb_iterations_upper_bound))
> > +	{
> > +	  found = true;
> > +	  pointer_set_insert (not_executed_last_iteration, elt->stmt);
> > +	}
> > +    }
> 
> So you are looking for all stmts a bound was derived from.

Yes, with bound smaller than the current estimate.
> 
> > +  if (!found)
> > +    {
> > +      pointer_set_destroy (not_executed_last_iteration);
> 
> create this on-demand in the above loop?

Will do. 
> 
> > +      return;
> > +    }
> > +  visited = pointer_set_create ();
> > +  VEC_safe_push (basic_block, heap, queue, loop->header);
> > +  pointer_set_insert (visited, loop->header);
> 
> pointer-set for BB visited?  In most other places we use a
> [s]bitmap with block numbers.

Will switch to bitmap though I think it is mostly because this tradition was
invented before pointer-set. bitmap has liner walk in it, pointer-set should
scale better.
> 
> if we didn't find an exit we reduce count.  double_int_one looks magic
> here, but with the assertion that each queued 'stmt_found' upper
> bound was less than loop->nb_iterations_upper_bound, subtracting one
> is certainly conservative.  But why not use the maximum estimate from 
> all stmts_found?

Because it is always nb_iterations_upper_bound-1, see logic in record_estimate.
I plan to change this - basically we can change record_esitmate to record all
statements, not only those dominating exit and do Dijkstra's algorithm in this
walk looking for largest upper bound we can reach loopback with.

But as I wrote in the email, I would like to do this incrementally - fix the
bug first (possibly for 4.7, too - the bug is there I am not sure if it can
lead to wrong code) and change this next.  It means some further changes
thorough niter.c, but little challenge to implement Dijkstra with double-int
based queue.
> 
> Thus, please add some comments, use a bitmap for visited and
> rename variables to be more descriptive.

Will do, and need to analyze the bounds fortran failures :)

Thanks,
Honza