> > > What about the conservative variant of simply
> > >
> > > else
> > > delta = double_int_one;
> >
> > I think it would be bad idea: it makes us to completely unroll one
> > interation
> > too many that bloats code for no benefit. No optimization cancels the path
> > in
> > CFG because of undefined effect and thus the code will be output (unless
> > someone
> > smarter, like VRP, cleans up later, but it is more an exception than rule.)
>
> OK, on deper tought I guess I can add double_int_one always at that spot and
> once we are done with everything I can walk nb_iter_bound for all statements
> known to not be executed on last iteration and record them to pointer set.
>
> Finally I can walk from header in DFS stopping on loop exits, side effects and
> those stateemnts. If I visit no loop exit or side effect I know I can lower
> iteration count by 1 (in estimate_numbers_of_iterations_loop).
>
> This will give accurate answer and requires just little extra bookkeeping.
>
> I will give this a try.
Here is updated patch. It solves the testcase and gives better estimates than
before.
Here is obvious improvements: record_estimate can put all statements to the
list not only
those that dominates loop latch and maybe_lower_iteration_bound can track
lowest estimate
it finds on its walk. This will need bit more work and I am thus sending the
bugfix
separately, because I think it should go to 4.7, too.
Honza
* tree-ssa-loop-niter.c (record_estimate): Remove confused
dominators check.
(maybe_lower_iteration_bound): New function.
(estimate_numbers_of_iterations_loop): Use it.
Index: tree-ssa-loop-niter.c
===================================================================
--- tree-ssa-loop-niter.c (revision 192537)
+++ tree-ssa-loop-niter.c (working copy)
@@ -2535,7 +2541,6 @@ record_estimate (struct loop *loop, tree
gimple at_stmt, bool is_exit, bool realistic, bool upper)
{
double_int delta;
- edge exit;
if (dump_file && (dump_flags & TDF_DETAILS))
{
@@ -2570,14 +2577,10 @@ record_estimate (struct loop *loop, tree
}
/* Update the number of iteration estimates according to the bound.
- If at_stmt is an exit or dominates the single exit from the loop,
- then the loop latch is executed at most BOUND times, otherwise
- it can be executed BOUND + 1 times. */
- exit = single_exit (loop);
- if (is_exit
- || (exit != NULL
- && dominated_by_p (CDI_DOMINATORS,
- exit->src, gimple_bb (at_stmt))))
+ If at_stmt is an exit then the loop latch is executed at most BOUND times,
+ otherwise it can be executed BOUND + 1 times. We will lower the estimate
+ later if such statement must be executed on last iteration */
+ if (is_exit)
delta = double_int_zero;
else
delta = double_int_one;
@@ -2953,6 +2956,87 @@ gcov_type_to_double_int (gcov_type val)
return ret;
}
+/* See if every path cross the loop goes through a statement that is known
+ to not execute at the last iteration. In that case we can decrese iteration
+ count by 1. */
+
+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);
+ }
+ }
+ if (!found)
+ {
+ pointer_set_destroy (not_executed_last_iteration);
+ return;
+ }
+ visited = pointer_set_create ();
+ VEC_safe_push (basic_block, heap, queue, loop->header);
+ pointer_set_insert (visited, loop->header);
+ found = false;
+
+ while (VEC_length (basic_block, queue) && !found)
+ {
+ basic_block bb = VEC_pop (basic_block, queue);
+ gimple_stmt_iterator gsi;
+ bool stmt_found = false;
+
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gimple stmt = gsi_stmt (gsi);
+ if (pointer_set_contains (not_executed_last_iteration, stmt))
+ {
+ stmt_found = true;
+ break;
+ }
+ if (gimple_has_side_effects (stmt))
+ {
+ found = true;
+ break;
+ }
+ }
+ if (!stmt_found && !found)
+ {
+ edge e;
+ edge_iterator ei;
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ if (loop_exit_edge_p (loop, e))
+ {
+ found = true;
+ break;
+ }
+ if (!pointer_set_insert (visited, e->dest))
+ VEC_safe_push (basic_block, heap, queue, e->dest);
+ }
+ }
+ }
+ if (!found)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Reducing loop iteration estimate by 1; "
+ "undefined statement must be executed at last iteration.");
+ record_niter_bound (loop, loop->nb_iterations_upper_bound -
double_int_one,
+ false, true);
+ }
+ pointer_set_destroy (visited);
+ VEC_free (basic_block, heap, queue);
+}
+
/* Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P
is true also use estimates derived from undefined behavior. */
@@ -2996,6 +3080,9 @@ estimate_numbers_of_iterations_loop (str
infer_loop_bounds_from_undefined (loop);
+ if (loop->any_upper_bound)
+ maybe_lower_iteration_bound (loop);
+
/* If we have a measured profile, use it to estimate the number of
iterations. */
if (loop->header->count != 0)
