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 ? -1 : hwi_nit;
+}
+
+/* Sets NIT to an upper bound for the maximum number of executions of the
+ latch of the LOOP. If we have no reliable estimate, the function returns
+ false, otherwise returns true. */
+
+bool
+get_likely_max_loop_iterations (struct loop *loop, widest_int *nit)
+{
+ if (!loop->any_likely_upper_bound)
+ return false;
+
+ *nit = loop->nb_iterations_likely_upper_bound;
+ return true;
+}
+
+/* Similar to get_max_loop_iterations, but returns the estimate only
+ if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
+ on the number of iterations of LOOP could not be derived, returns -1. */
+
+HOST_WIDE_INT
+get_likely_max_loop_iterations_int (struct loop *loop)
+{
+ widest_int nit;
+ HOST_WIDE_INT hwi_nit;
+
+ if (!get_likely_max_loop_iterations (loop, &nit))
+ return -1;
+
+ if (!wi::fits_shwi_p (nit))
return -1;
hwi_nit = nit.to_shwi ();
Index: cfgloop.h
===================================================================
--- cfgloop.h (revision 236762)
+++ cfgloop.h (working copy)
@@ -160,6 +160,8 @@ struct GTY ((chain_next ("%h.next"))) lo
valid if any_upper_bound is true. */
widest_int nb_iterations_upper_bound;
+ widest_int nb_iterations_likely_upper_bound;
+
/* An integer giving an estimate on nb_iterations. Unlike
nb_iterations_upper_bound, there is no guarantee that it is at least
nb_iterations. */
@@ -167,6 +169,7 @@ struct GTY ((chain_next ("%h.next"))) lo
bool any_upper_bound;
bool any_estimate;
+ bool any_likely_upper_bound;
/* True if the loop can be parallel. */
bool can_be_parallel;
@@ -776,8 +779,10 @@ loop_outermost (struct loop *loop)
extern void record_niter_bound (struct loop *, const widest_int &, bool, bool);
extern HOST_WIDE_INT get_estimated_loop_iterations_int (struct loop *);
extern HOST_WIDE_INT get_max_loop_iterations_int (struct loop *);
+extern HOST_WIDE_INT get_likely_max_loop_iterations_int (struct loop *);
extern bool get_estimated_loop_iterations (struct loop *loop, widest_int *nit);
extern bool get_max_loop_iterations (struct loop *loop, widest_int *nit);
+extern bool get_likely_max_loop_iterations (struct loop *loop, widest_int
*nit);
extern int bb_loop_depth (const_basic_block);
/* Converts VAL to widest_int. */
Index: cfgloopmanip.c
===================================================================
--- cfgloopmanip.c (revision 236762)
+++ cfgloopmanip.c (working copy)
@@ -1016,6 +1016,9 @@ copy_loop_info (struct loop *loop, struc
gcc_checking_assert (!target->any_upper_bound && !target->any_estimate);
target->any_upper_bound = loop->any_upper_bound;
target->nb_iterations_upper_bound = loop->nb_iterations_upper_bound;
+ target->any_likely_upper_bound = loop->any_likely_upper_bound;
+ target->nb_iterations_likely_upper_bound
+ = loop->nb_iterations_likely_upper_bound;
target->any_estimate = loop->any_estimate;
target->nb_iterations_estimate = loop->nb_iterations_estimate;
target->estimate_state = loop->estimate_state;
Index: loop-unroll.c
===================================================================
--- loop-unroll.c (revision 236762)
+++ loop-unroll.c (working copy)
@@ -523,6 +523,11 @@ unroll_loop_constant_iterations (struct
loop->nb_iterations_estimate -= exit_mod;
else
loop->any_estimate = false;
+ if (loop->any_likely_upper_bound
+ && wi::leu_p (exit_mod, loop->nb_iterations_likely_upper_bound))
+ loop->nb_iterations_likely_upper_bound -= exit_mod;
+ else
+ loop->any_likely_upper_bound = false;
}
bitmap_set_bit (wont_exit, 1);
@@ -566,6 +571,11 @@ unroll_loop_constant_iterations (struct
loop->nb_iterations_estimate -= exit_mod + 1;
else
loop->any_estimate = false;
+ if (loop->any_likely_upper_bound
+ && wi::leu_p (exit_mod + 1,
loop->nb_iterations_likely_upper_bound))
+ loop->nb_iterations_likely_upper_bound -= exit_mod + 1;
+ else
+ loop->any_likely_upper_bound = false;
desc->noloop_assumptions = NULL_RTX;
bitmap_set_bit (wont_exit, 0);
@@ -619,6 +629,9 @@ unroll_loop_constant_iterations (struct
if (loop->any_estimate)
loop->nb_iterations_estimate
= wi::udiv_trunc (loop->nb_iterations_estimate, max_unroll + 1);
+ if (loop->any_likely_upper_bound)
+ loop->nb_iterations_likely_upper_bound
+ = wi::udiv_trunc (loop->nb_iterations_likely_upper_bound, max_unroll +
1);
desc->niter_expr = GEN_INT (desc->niter);
/* Remove the edges. */
@@ -1059,6 +1072,9 @@ unroll_loop_runtime_iterations (struct l
if (loop->any_estimate)
loop->nb_iterations_estimate
= wi::udiv_trunc (loop->nb_iterations_estimate, max_unroll + 1);
+ if (loop->any_likely_upper_bound)
+ loop->nb_iterations_likely_upper_bound
+ = wi::udiv_trunc (loop->nb_iterations_likely_upper_bound, max_unroll +
1);
if (exit_at_end)
{
desc->niter_expr =
@@ -1070,6 +1086,11 @@ unroll_loop_runtime_iterations (struct l
--loop->nb_iterations_estimate;
else
loop->any_estimate = false;
+ if (loop->any_likely_upper_bound
+ && loop->nb_iterations_likely_upper_bound != 0)
+ --loop->nb_iterations_likely_upper_bound;
+ else
+ loop->any_likely_upper_bound = false;
}
if (dump_file)
Index: lto-streamer-in.c
===================================================================
--- lto-streamer-in.c (revision 236762)
+++ lto-streamer-in.c (working copy)
@@ -835,6 +835,9 @@ input_cfg (struct lto_input_block *ib, s
loop->any_upper_bound = streamer_read_hwi (ib);
if (loop->any_upper_bound)
loop->nb_iterations_upper_bound = streamer_read_wi (ib);
+ loop->any_likely_upper_bound = streamer_read_hwi (ib);
+ if (loop->any_likely_upper_bound)
+ loop->nb_iterations_likely_upper_bound = streamer_read_wi (ib);
loop->any_estimate = streamer_read_hwi (ib);
if (loop->any_estimate)
loop->nb_iterations_estimate = streamer_read_wi (ib);
Index: lto-streamer-out.c
===================================================================
--- lto-streamer-out.c (revision 236762)
+++ lto-streamer-out.c (working copy)
@@ -1925,6 +1925,9 @@ output_cfg (struct output_block *ob, str
streamer_write_hwi (ob, loop->any_upper_bound);
if (loop->any_upper_bound)
streamer_write_wi (ob, loop->nb_iterations_upper_bound);
+ streamer_write_hwi (ob, loop->any_likely_upper_bound);
+ if (loop->any_likely_upper_bound)
+ streamer_write_wi (ob, loop->nb_iterations_likely_upper_bound);
streamer_write_hwi (ob, loop->any_estimate);
if (loop->any_estimate)
streamer_write_wi (ob, loop->nb_iterations_estimate);
Index: tree-ssa-loop-ivcanon.c
===================================================================
--- tree-ssa-loop-ivcanon.c (revision 236762)
+++ tree-ssa-loop-ivcanon.c (working copy)
@@ -1036,6 +1036,8 @@ try_peel_loop (struct loop *loop,
}
if (loop->any_upper_bound)
loop->nb_iterations_upper_bound -= npeel;
+ if (loop->any_likely_upper_bound)
+ loop->nb_iterations_likely_upper_bound -= npeel;
loop->nb_iterations_estimate = 0;
/* Make sure to mark loop cold so we do not try to peel it more. */
scale_loop_profile (loop, 1, 0);
@@ -1107,6 +1109,12 @@ canonicalize_loop_induction_variables (s
fprintf (dump_file, "Loop %d iterates at most %i times.\n", loop->num,
(int)maxiter);
}
+ if (dump_file && (dump_flags & TDF_DETAILS)
+ && likely_max_loop_iterations_int (loop) >= 0)
+ {
+ fprintf (dump_file, "Loop likely %d iterates at most %i times.\n",
loop->num,
+ (int)likely_max_loop_iterations_int (loop));
+ }
/* Remove exits that are known to be never taken based on loop bound.
Needs to be called after compilation of max_loop_iterations_int that
Index: tree-ssa-loop-niter.c
===================================================================
--- tree-ssa-loop-niter.c (revision 236762)
+++ tree-ssa-loop-niter.c (working copy)
@@ -2954,8 +2958,6 @@ record_estimate (struct loop *loop, tree
realistic = false;
else
gcc_checking_assert (i_bound == wi::to_widest (bound));
- if (!upper && !realistic)
- return;
/* If we have a guaranteed upper bound, record it in the appropriate
list, unless this is an !is_exit bound (i.e. undefined behavior in
@@ -2977,7 +2979,7 @@ record_estimate (struct loop *loop, tree
/* If statement is executed on every path to the loop latch, we can directly
infer the upper bound on the # of iterations of the loop. */
if (!dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (at_stmt)))
- return;
+ upper = false;
/* Update the number of iteration estimates according to the bound.
If at_stmt is an exit then the loop latch is executed at most BOUND times,
@@ -3850,6 +3852,37 @@ max_loop_iterations_int (struct loop *lo
return hwi_nit < 0 ? -1 : hwi_nit;
}
+bool
+likely_max_loop_iterations (struct loop *loop, widest_int *nit)
+{
+ /* When SCEV information is available, try to update loop iterations
+ estimate. Otherwise just return whatever we recorded earlier. */
+ if (scev_initialized_p ())
+ estimate_numbers_of_iterations_loop (loop);
+
+ return get_likely_max_loop_iterations (loop, nit);
+}
+
+/* Similar to max_loop_iterations, but returns the estimate only
+ if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
+ on the number of iterations of LOOP could not be derived, returns -1. */
+
+HOST_WIDE_INT
+likely_max_loop_iterations_int (struct loop *loop)
+{
+ widest_int nit;
+ HOST_WIDE_INT hwi_nit;
+
+ if (!likely_max_loop_iterations (loop, &nit))
+ return -1;
+
+ if (!wi::fits_shwi_p (nit))
+ return -1;
+ hwi_nit = nit.to_shwi ();
+
+ return hwi_nit < 0 ? -1 : hwi_nit;
+}
+
/* Returns an estimate for 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. */
@@ -3869,7 +3902,7 @@ estimated_stmt_executions_int (struct lo
return snit < 0 ? -1 : snit;
}
-/* Sets NIT to the estimated maximum number of executions of the latch of the
+/* Sets NIT to the maximum number of executions of the latch of the
LOOP, plus one. If we have no reliable estimate, the function returns
false, otherwise returns true. */
@@ -3882,6 +3915,25 @@ max_stmt_executions (struct loop *loop,
return false;
nit_minus_one = *nit;
+
+ *nit += 1;
+
+ return wi::gtu_p (*nit, nit_minus_one);
+}
+
+/* Sets NIT to the estimated maximum number of executions of the latch of the
+ LOOP, plus one. If we have no likely estimate, the function returns
+ false, otherwise returns true. */
+
+bool
+likely_max_stmt_executions (struct loop *loop, widest_int *nit)
+{
+ widest_int nit_minus_one;
+
+ if (!likely_max_loop_iterations (loop, nit))
+ return false;
+
+ nit_minus_one = *nit;
*nit += 1;
Index: tree-ssa-loop-niter.h
===================================================================
--- tree-ssa-loop-niter.h (revision 236762)
+++ tree-ssa-loop-niter.h (working copy)
@@ -35,9 +35,13 @@ extern bool estimated_loop_iterations (s
extern HOST_WIDE_INT estimated_loop_iterations_int (struct loop *);
extern bool max_loop_iterations (struct loop *, widest_int *);
extern HOST_WIDE_INT max_loop_iterations_int (struct loop *);
+extern bool likely_max_loop_iterations (struct loop *, widest_int *);
+extern HOST_WIDE_INT likely_max_loop_iterations_int (struct loop *);
extern HOST_WIDE_INT max_stmt_executions_int (struct loop *);
+extern HOST_WIDE_INT likely_max_stmt_executions_int (struct loop *);
extern HOST_WIDE_INT estimated_stmt_executions_int (struct loop *);
extern bool max_stmt_executions (struct loop *, widest_int *);
+extern bool likely_max_stmt_executions (struct loop *, widest_int *);
extern bool estimated_stmt_executions (struct loop *, widest_int *);
extern void estimate_numbers_of_iterations (void);
extern bool stmt_dominates_stmt_p (gimple *, gimple *);
