Re-apply reverted niter change 1/4

Hi,
as discussed on IRC today, I would like to re-apply the patch to fix bogus
realistic bounds in niter.  As it turned out, we seem to rely on this bogus
estimate in few benchmarks and there is miscompilation with avx512. 

The performance regressions should be solved my planned patch to introduce
likely upper bounds - here we can track the assumption that there are no
trailing arrays in the structures. I plan to send it after some benchmarking.

Moreover we can get smarter about tracking trailing arrays.  We seem to get
wrong MEM_REFs (as noticed by Richard), we may disable the path for non-C
based languages (regresions are for Fortran testcases) and we can track object
sizes.

I plan to do that step-by-step so possible additional fallout is easier to
track.  This patch re-instantiate first fix included in the orignial
patch - ivopts should consider max_stmt-executions_int when giving an estimate
on number of iterations.

Bootstrapped/regtested x86_64-linux, comitted.

Honza

On Mon, Apr 18, 2016 at 6:24 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
> Hi,
> as discussed on IRC today, I would like to re-apply the patch to fix bogus
> realistic bounds in niter.  As it turned out, we seem to rely on this bogus
> estimate in few benchmarks and there is miscompilation with avx512.
>
> The performance regressions should be solved my planned patch to introduce
> likely upper bounds - here we can track the assumption that there are no
> trailing arrays in the structures. I plan to send it after some benchmarking.
>
> Moreover we can get smarter about tracking trailing arrays.  We seem to get
> wrong MEM_REFs (as noticed by Richard), we may disable the path for non-C
> based languages (regresions are for Fortran testcases) and we can track object
> sizes.
>
> I plan to do that step-by-step so possible additional fallout is easier to
> track.  This patch re-instantiate first fix included in the orignial
> patch - ivopts should consider max_stmt-executions_int when giving an estimate
> on number of iterations.
>
> Bootstrapped/regtested x86_64-linux, comitted.
>
> Honza
>
> Index: ChangeLog
> ===================================================================
> --- ChangeLog   (revision 235157)
> +++ ChangeLog   (working copy)
> @@ -1,3 +1,8 @@
> +2016-04-17  Jan Hubicka  <jh@suse.cz>
> +
> +       * tree-ssa-loop-ivopts.c (avg_loop_niter): Use also
> +       max_loop_iterations_int.
> +
>  2016-04-18  Richard Biener  <rguenther@suse.de>
>
>         PR tree-optimization/43434
> Index: tree-ssa-loop-ivopts.c
> ===================================================================
> --- tree-ssa-loop-ivopts.c      (revision 235064)
> +++ tree-ssa-loop-ivopts.c      (working copy)
> @@ -121,7 +121,11 @@ avg_loop_niter (struct loop *loop)
>  {
>    HOST_WIDE_INT niter = estimated_stmt_executions_int (loop);
>    if (niter == -1)
> -    return AVG_LOOP_NITER (loop);
> +    {
> +      niter = max_stmt_executions_int (loop);
> +      if (niter == -1 || niter > AVG_LOOP_NITER (loop))
> +        return AVG_LOOP_NITER (loop);
Any reason why AVG_LOOP_NITER is still used if niter gives larger number?

Thanks,
bin
> +    }
>
>    return niter;
>  }

> > Index: tree-ssa-loop-ivopts.c
> > ===================================================================
> > --- tree-ssa-loop-ivopts.c      (revision 235064)
> > +++ tree-ssa-loop-ivopts.c      (working copy)
> > @@ -121,7 +121,11 @@ avg_loop_niter (struct loop *loop)
> >  {
> >    HOST_WIDE_INT niter = estimated_stmt_executions_int (loop);
> >    if (niter == -1)
> > -    return AVG_LOOP_NITER (loop);
> > +    {
> > +      niter = max_stmt_executions_int (loop);
> > +      if (niter == -1 || niter > AVG_LOOP_NITER (loop))
> > +        return AVG_LOOP_NITER (loop);
> Any reason why AVG_LOOP_NITER is still used if niter gives larger number?

if you have a loop like this

int a[1000000];

for (i=0li<1000000;i++)
  if (a[i])
    break
max_stmt_executions_int will be 1000000 but that is just upper bound, not realistic
estimate and thus you can not assume that average number of iterations is 1000000.
It is anywhere between 0 and 1000000 and I assume the constant of 5 which AVG_LOOP_NITER
expands into was chosen to avoid ivopts to give resonable balance between setup cost
and iteration cost. For example, string manipulation loops tends to get large buffers
and terminate in very few iterations.

(I do not recall the data precisely, it has been a decade. The average number
of iterations of random loop can be measured from profile feedback, it is
somewhere between 3 adn 10 for SPEC or GCC).
This is why:
/* Loopback edge is taken.  */                                                  
DEF_PREDICTOR (PRED_LOOP_BRANCH, "loop branch", HITRATE (86),                   
               PRED_FLAG_FIRST_MATCH)                                           
                                                                                
/* Edge causing loop to terminate is probably not taken.  */                    
DEF_PREDICTOR (PRED_LOOP_EXIT, "loop exit", HITRATE (91),                       
               PRED_FLAG_FIRST_MATCH)                                           

is set accordingly.

Honza
> 
> Thanks,
> bin
> > +    }
> >
> >    return niter;
> >  }

On Tue, Apr 19, 2016 at 12:09 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> > Index: tree-ssa-loop-ivopts.c
>> > ===================================================================
>> > --- tree-ssa-loop-ivopts.c      (revision 235064)
>> > +++ tree-ssa-loop-ivopts.c      (working copy)
>> > @@ -121,7 +121,11 @@ avg_loop_niter (struct loop *loop)
>> >  {
>> >    HOST_WIDE_INT niter = estimated_stmt_executions_int (loop);
>> >    if (niter == -1)
>> > -    return AVG_LOOP_NITER (loop);
>> > +    {
>> > +      niter = max_stmt_executions_int (loop);
>> > +      if (niter == -1 || niter > AVG_LOOP_NITER (loop))
>> > +        return AVG_LOOP_NITER (loop);
>> Any reason why AVG_LOOP_NITER is still used if niter gives larger number?
>
> if you have a loop like this
>
> int a[1000000];
>
> for (i=0li<1000000;i++)
>   if (a[i])
>     break
> max_stmt_executions_int will be 1000000 but that is just upper bound, not realistic
> estimate and thus you can not assume that average number of iterations is 1000000.
> It is anywhere between 0 and 1000000 and I assume the constant of 5 which AVG_LOOP_NITER
> expands into was chosen to avoid ivopts to give resonable balance between setup cost
> and iteration cost. For example, string manipulation loops tends to get large buffers
> and terminate in very few iterations.
>
> (I do not recall the data precisely, it has been a decade. The average number
> of iterations of random loop can be measured from profile feedback, it is
> somewhere between 3 adn 10 for SPEC or GCC).
> This is why:
> /* Loopback edge is taken.  */
> DEF_PREDICTOR (PRED_LOOP_BRANCH, "loop branch", HITRATE (86),
>                PRED_FLAG_FIRST_MATCH)
>
> /* Edge causing loop to terminate is probably not taken.  */
> DEF_PREDICTOR (PRED_LOOP_EXIT, "loop exit", HITRATE (91),
>                PRED_FLAG_FIRST_MATCH)
>
> is set accordingly.
Thanks for explanation.

Thanks,
bin