Re: Record likely upper bounds for loops

[Bernhard Reutner-Fischer]

On May 27, 2016 1:14:09 PM GMT+02:00, Jan Hubicka  wrote:

>+  fprintf (dump_file, "Loop likely %d iterates at most %i
>times.\n", loop->num,
>+ (int)likely_max_loop_iterations_int (loop));

s/Loop likely %d/Loop %d likely/
please.
thanks,

Re: Record likely upper bounds for loops

[Jan Hubicka]

> Hi,
> 
> On Fri, 27 May 2016, Jan Hubicka wrote:
> > Thanks, updatted and comitted.
> 
> This checkin seems to regress gcc.c-torture/execute/20050826-2.c at -Os:
> 
> gcc/xgcc -Bgcc/ ../gcc/gcc/testsuite/gcc.c-torture/execute/20050826-2.c -Os \
>   -o ./20050826-2.exe  
> 
> ./20050826-2.exe
> Aborted
> 
> (the previous revision is fine)
Sorry,
I amanged to accidentally commit the following change:

Index: tree-ssa-loop-niter.c
===
--- tree-ssa-loop-niter.c   (revision 236816)
+++ tree-ssa-loop-niter.c   (working copy)
@@ -2289,11 +2289,7 @@ number_of_iterations_exit (struct loop *
 
   /* If NITER has simplified into a constant, update MAX.  */
   if (TREE_CODE (niter->niter) == INTEGER_CST)
-{
-  niter->max = wi::to_widest (niter->niter);
-  record_niter_bound (loop, niter->max, loop_only_exit_p (loop, exit),
- true);
-}
+niter->max = wi::to_widest (niter->niter);
 
   if (integer_onep (niter->assumptions))
 return true;

I will revert it after re-testing.
Honza

Re: Record likely upper bounds for loops

[Paolo Carlini]

Hi,

On 27/05/2016 19:20, Alexander Monakov wrote:

Hi,

On Fri, 27 May 2016, Jan Hubicka wrote:

Thanks, updatted and comitted.

This checkin seems to regress gcc.c-torture/execute/20050826-2.c at -Os:

gcc/xgcc -Bgcc/ ../gcc/gcc/testsuite/gcc.c-torture/execute/20050826-2.c -Os \
   -o ./20050826-2.exe

./20050826-2.exe
Aborted

(the previous revision is fine)

I suspect (should double check) this one too in libstdc++-v3:

FAIL: 25_algorithms/is_sorted/1.cc execution test

Paolo.

Re: Record likely upper bounds for loops

[Alexander Monakov]

Hi,

On Fri, 27 May 2016, Jan Hubicka wrote:
> Thanks, updatted and comitted.

This checkin seems to regress gcc.c-torture/execute/20050826-2.c at -Os:

gcc/xgcc -Bgcc/ ../gcc/gcc/testsuite/gcc.c-torture/execute/20050826-2.c -Os \
  -o ./20050826-2.exe  

./20050826-2.exe
Aborted

(the previous revision is fine)

Alexander

Re: Record likely upper bounds for loops

[Jan Hubicka]

> likely_max_loop_iterations misses a function comment.

Thanks, updatted and comitted.

> 
> Ugh, one more widest_int in struct loop ... (oh well).  Given
> that (on x86_64) sizeof(widest_int) == 40 and sizeof(tree_int_cst) == 24
> (ok, that's cheating, it's with just one HWI for the number) it looks
> appealing to change the storage of these to 'tree' ... (as a followup,
> using uint128_type_node or so or whatever largest integer type a
> target supports).  Another option is to add a GCed wide_int that we
> can "allocate" - you can do this already by having a GTY HWI array
> and length and using wi::from_buffer ().  That way you'd avoid defining
> any tree type.

I am not big firend of using TREEs to represent things that are not exactly
part of IL. (and even in IL I would preffer seeing fewer of them).  For likely
upper bound we can also cap and consider only those bounds that fits in 64bit
type. Others are not useful anyway: loop will very likely not iterate more
than 2^64 times ;)

Honza

Re: Record likely upper bounds for loops

[Richard Biener]

On Fri, 27 May 2016, Jan Hubicka wrote:

> Hi,
> this patch adds infrastructure to tree-ssa-loop-niter to record likely upper 
> bounds.
> The basic idea is that it is easier to get likely bounds that 100% safe 
> bounds or
> realistic estimates and the bound can be effectively used to trim down 
> optimizations
> that are good idea only for large trip counts. This patch only updates the
> infrastructure. I have two followup patches. First turns current optimizers to
> use the bound (and adds testcase) and second enables loop peeling at -O3 and 
> makes
> us to peel in cases where we would fully unroll if the loop bound was safe.
> This improves some benchmarks, like John the ripper.
> 
> Currently likely upper bounds are derived in two cases
>  1) for arrays we can't prove to be non-trailing
>  2) for array accesses in conditional.  I.e.
> int a[3];
> for (int i = 0; t(); i++)
>   if (q())
>   a[i]++;
> It is easy to add more cases, for example when the only unbounded loopback 
> path contains
> unlikely edge.
> 
> Bootstrapped/regtested x86_64-linux, OK?

likely_max_loop_iterations misses a function comment.

Ugh, one more widest_int in struct loop ... (oh well).  Given
that (on x86_64) sizeof(widest_int) == 40 and sizeof(tree_int_cst) == 24
(ok, that's cheating, it's with just one HWI for the number) it looks
appealing to change the storage of these to 'tree' ... (as a followup,
using uint128_type_node or so or whatever largest integer type a
target supports).  Another option is to add a GCed wide_int that we
can "allocate" - you can do this already by having a GTY HWI array
and length and using wi::from_buffer ().  That way you'd avoid defining
any tree type.

Ok with the comment added.

Thanks,
Richard.

> Honza
> 
>   * cfgloop.c (record_niter_bound): Record likely upper bounds.
>   (likely_max_stmt_executions_int, get_likely_max_loop_iterations,
>   get_likely_max_loop_iterations_int): New.
>   * cfgloop.h (struct loop): Add nb_iterations_likely_upper_bound,
>   any_likely_upper_bound.
>   (get_likely_max_loop_iterations_int, get_likely_max_loop_iterations):
>   Declare.
>   * cfgloopmanip.c (copy_loop_info): Copy likely upper bounds.
>   * loop-unroll.c (unroll_loop_constant_iterations): Update likely
>   upper bound.
>   (unroll_loop_constant_iterations): Likewise.
>   (unroll_loop_runtime_iterations): Likewise.
>   * lto-streamer-in.c (input_cfg): Stream likely upper bounds.
>   * lto-streamer-out.c (output_cfg): Likewise.
>   * tree-ssa-loop-ivcanon.c (try_peel_loop): Update likely upper
>   bounds.
>   (canonicalize_loop_induction_variables): Dump likely upper bounds.
>   * tree-ssa-loop-niter.c (record_estimate): Record likely upper bounds.
>   (likely_max_loop_iterations): New.
>   (likely_max_loop_iterations_int): New.
>   (likely_max_stmt_executions): New.
>   * tree-ssa-loop-niter.h (likely_max_loop_iterations,
>   likely_max_loop_iterations_int, likely_max_stmt_executions_int,
>   likely_max_stmt_executions): Declare.
> Index: cfgloop.c
> ===
> --- cfgloop.c (revision 236762)
> +++ cfgloop.c (working copy)
> @@ -1790,6 +1790,11 @@ record_niter_bound (struct loop *loop, c
>  {
>loop->any_upper_bound = true;
>loop->nb_iterations_upper_bound = i_bound;
> +  if (!loop->any_likely_upper_bound)
> + {
> +   loop->any_likely_upper_bound = true;
> +   loop->nb_iterations_likely_upper_bound = i_bound;
> + }
>  }
>if (realistic
>&& (!loop->any_estimate
> @@ -1798,6 +1803,13 @@ record_niter_bound (struct loop *loop, c
>loop->any_estimate = true;
>loop->nb_iterations_estimate = i_bound;
>  }
> +  if (!realistic
> +  && (!loop->any_likely_upper_bound
> +  || wi::ltu_p (i_bound, loop->nb_iterations_likely_upper_bound)))
> +{
> +  loop->any_likely_upper_bound = true;
> +  loop->nb_iterations_likely_upper_bound = i_bound;
> +}
>  
>/* If an upper bound is smaller than the realistic estimate of the
>   number of iterations, use the upper bound instead.  */
> @@ -1806,6 +1818,11 @@ record_niter_bound (struct loop *loop, c
>&& wi::ltu_p (loop->nb_iterations_upper_bound,
>   loop->nb_iterations_estimate))
>  loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
> +  if (loop->any_upper_bound
> +  && loop->any_likely_upper_bound
> +  && wi::ltu_p (loop->nb_iterations_upper_bound,
> + loop->nb_iterations_likely_upper_bound))
> +loop->nb_iterations_likely_upper_bound = loop->nb_iterations_upper_bound;
>  }
>  
>  /* Similar to get_estimated_loop_iterations, but returns the estimate only
> @@ -1847,6 +1864,25 @@ max_stmt_executions_int (struct loop *lo
>return snit < 0 ? -1 : snit;
>  }
>  
> +/* Returns an likely upper bound on the number of executions of 

Record likely upper bounds for loops

[Jan Hubicka]

Hi,
this patch adds infrastructure to tree-ssa-loop-niter to record likely upper 
bounds.
The basic idea is that it is easier to get likely bounds that 100% safe bounds 
or
realistic estimates and the bound can be effectively used to trim down 
optimizations
that are good idea only for large trip counts. This patch only updates the
infrastructure. I have two followup patches. First turns current optimizers to
use the bound (and adds testcase) and second enables loop peeling at -O3 and 
makes
us to peel in cases where we would fully unroll if the loop bound was safe.
This improves some benchmarks, like John the ripper.

Currently likely upper bounds are derived in two cases
 1) for arrays we can't prove to be non-trailing
 2) for array accesses in conditional.  I.e.
int a[3];
for (int i = 0; t(); i++)
  if (q())
a[i]++;
It is easy to add more cases, for example when the only unbounded loopback path 
contains
unlikely edge.

Bootstrapped/regtested x86_64-linux, OK?

Honza

* cfgloop.c (record_niter_bound): Record likely upper bounds.
(likely_max_stmt_executions_int, get_likely_max_loop_iterations,
get_likely_max_loop_iterations_int): New.
* cfgloop.h (struct loop): Add nb_iterations_likely_upper_bound,
any_likely_upper_bound.
(get_likely_max_loop_iterations_int, get_likely_max_loop_iterations):
Declare.
* cfgloopmanip.c (copy_loop_info): Copy likely upper bounds.
* loop-unroll.c (unroll_loop_constant_iterations): Update likely
upper bound.
(unroll_loop_constant_iterations): Likewise.
(unroll_loop_runtime_iterations): Likewise.
* lto-streamer-in.c (input_cfg): Stream likely upper bounds.
* lto-streamer-out.c (output_cfg): Likewise.
* tree-ssa-loop-ivcanon.c (try_peel_loop): Update likely upper
bounds.
(canonicalize_loop_induction_variables): Dump likely upper bounds.
* tree-ssa-loop-niter.c (record_estimate): Record likely upper bounds.
(likely_max_loop_iterations): New.
(likely_max_loop_iterations_int): New.
(likely_max_stmt_executions): New.
* tree-ssa-loop-niter.h (likely_max_loop_iterations,
likely_max_loop_iterations_int, likely_max_stmt_executions_int,
likely_max_stmt_executions): Declare.
Index: cfgloop.c
===
--- cfgloop.c   (revision 236762)
+++ cfgloop.c   (working copy)
@@ -1790,6 +1790,11 @@ record_niter_bound (struct loop *loop, c
 {
   loop->any_upper_bound = true;
   loop->nb_iterations_upper_bound = i_bound;
+  if (!loop->any_likely_upper_bound)
+   {
+ loop->any_likely_upper_bound = true;
+ loop->nb_iterations_likely_upper_bound = i_bound;
+   }
 }
   if (realistic
   && (!loop->any_estimate
@@ -1798,6 +1803,13 @@ record_niter_bound (struct loop *loop, c
   loop->any_estimate = true;
   loop->nb_iterations_estimate = i_bound;
 }
+  if (!realistic
+  && (!loop->any_likely_upper_bound
+  || wi::ltu_p (i_bound, loop->nb_iterations_likely_upper_bound)))
+{
+  loop->any_likely_upper_bound = true;
+  loop->nb_iterations_likely_upper_bound = i_bound;
+}
 
   /* If an upper bound is smaller than the realistic estimate of the
  number of iterations, use the upper bound instead.  */
@@ -1806,6 +1818,11 @@ record_niter_bound (struct loop *loop, c
   && wi::ltu_p (loop->nb_iterations_upper_bound,
loop->nb_iterations_estimate))
 loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
+  if (loop->any_upper_bound
+  && loop->any_likely_upper_bound
+  && wi::ltu_p (loop->nb_iterations_upper_bound,
+   loop->nb_iterations_likely_upper_bound))
+loop->nb_iterations_likely_upper_bound = loop->nb_iterations_upper_bound;
 }
 
 /* Similar to get_estimated_loop_iterations, but returns the estimate only
@@ -1847,6 +1864,25 @@ max_stmt_executions_int (struct loop *lo
   return snit < 0 ? -1 : snit;
 }
 
+/* Returns an likely upper bound on the number of executions of statements
+   in the LOOP.  For statements before the loop exit, this exceeds
+   the number of execution of the latch by one.  */
+
+HOST_WIDE_INT
+likely_max_stmt_executions_int (struct loop *loop)
+{
+  HOST_WIDE_INT nit = get_likely_max_loop_iterations_int (loop);
+  HOST_WIDE_INT snit;
+
+  if (nit == -1)
+return -1;
+
+  snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1);
+
+  /* If the computation overflows, return -1.  */
+  return snit < 0 ? -1 : snit;
+}
+
 /* Sets NIT to the estimated number of executions of the latch of the
LOOP.  If we have no reliable estimate, the function returns false, 
otherwise
returns true.  */
@@ -1899,6 +1935,40 @@ get_max_loop_iterations_int (struct loop
 return -1;
 
   if (!wi::fits_shwi_p (nit))
+return -1;
+  hwi_nit = nit.to_shwi ();
+
+  return hwi_nit < 0 ?