On Thu, 11 Oct 2012, Jan Hubicka wrote:
> Hi,
> while looking into RTL loop peeling micopmilation I found that we now do a
> lot of
> RTL loop peeling for loops of the form
>
> int a[2];
> test(int c)
> {
> int i;
> for (i=0;i<c;i++)
> a[i]=5;
> }
> this is because tree-ssa-loop-niter is able to prove that the loop iterates at
> most twice. This is better to be done on gimple level because destroying the
> loop enables more propagation.
>
> This patch started as simple attempt to make try_unroll_loop_completely
> to use max_loop_iterations_int. I had to track several issues
>
> 1) try_unroll_loop_completely handles only inner loops. I am fine with not
> peeling loops with subloops, but if the loop is known to iterate 0 times,
> we should turn it into non-loop.
> 2) try_unroll_loop_completely now handles removal of the loop by making
> exit edge conditional to be true and relying on cleanup_cfg to do
> the job. This does not work for all the cases we can handle
> by max_loop_iterations_int. When loop has multiple possible exits
> we don't really know what exit will be taken (we know it will be one
> of them).
>
> I added logic handling simple case where loop has single exit and
> in generic case I unloop it by adding __builtin_unreachable on the
> loopback path. While this seems bit involved it works well.
> 3) The last iteration has parts that are provably unreachable and should
> be optimized out later. VRP however tends to report array bound warnings
> that breaks -O3 bootstrap.
> I sent separate fix for that. Still I need to add 3 initializations
> to avoid maybe used uninitialized warning to get -O3 bootstrap working
> with this patch.
>
> The patch got quite a lot of snowballing effect, so I decided to not include:
>
> 1) the cost model is skewed for last iteration. It is often just duplicated
> loop header - i.e. all code dominated by the optmized out exit test should
> not be accounted. This would make cunroll-4.c testcase bellow to be
> unlooped
> during cunrolli rather than during complette unroling.
> 2) profile updating is broken for any loop containing non-trivial control
> flow.
> We need to teach loop duplication code to update sanely the profile when
> wont_exit is true and we need to update profile
> 3) we probably want to do less unrolling when result is not a single basic
> block. Current limit of 400 isnsns seems bit too large; making one basic
> block is important win. Making sequence of basic blocks with exits is
> less so.
Nice - this was on my TODO list as well, btw ;)
> * gcc.dg/tree-ssa/cunroll-1.c: New testcase.
> * gcc.dg/tree-ssa/cunroll-2.c: New testcase.
> * gcc.dg/tree-ssa/cunroll-3.c: New testcase.
> * gcc.dg/tree-ssa/cunroll-4.c: New testcase.
> * gcc.dg/tree-ssa/cunroll-5.c: New testcase.
>
> * cfgloopmanip.c (unloop): Export.
> * tree-ssa-loop-ivcanon.c (tree_estimate_loop_size): Estimate
> also with unknown exit conditoinal.
> (try_unroll_loop_completely): Use max_loop_iterations_int to unroll
> also loops with low upper bound; handle unlooping of the last loop
> even when exit conditional is not known; unloop loop that do not loop
> even if they are not innermost.
> (canonicalize_loop_induction_variables): Record niter bounds known;
> try unrolling even if number of iterations is not known;
> (canonicalize_induction_variables): Be ready for loops disappearing.
> (tree_unroll_loops_completely): Likewise.
> * cfgloop.h (unloop): Declare.
>
> * f95-lang.c (gfc_init_builtin_functions): Build __builtin_unreachable.
I wonder if other languages need similar adjustment?
+ /* Now destroy the loop. First try to do so by cancelling the
+ patch from exit conditional if we identified good candidate.
+
you mean 'path' here, right? Similar in other places.
+ /* Unloop destroys the latch edge. */
+ unloop (loop, &irred_invalidated);
+ if (irred_invalidated)
+ mark_irreducible_loops ();
this makes the whole thing quadratic in the number of loops.
Please pass down a flag and handle this in the place we
update SSA form (thus, once per function / unroll iteration).
Or provide a more optimial implementation that only considers
parent loops of 'loop' (even that is excessive though, quadratic
in the loop depth).
- FOR_EACH_LOOP (li, loop, 0)
+ for (fel_init (&li, &next, LI_ONLY_INNERMOST); next;)
FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
but I'm sure that IV canonicalization should happen for all loops.
So, why do you need this change? Esp. we should get rid of
single-iteration outer loops here, too.
- FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
+ for (fel_init (&li, &next, 0); next;)
see above - FOR_EACH_LOOP (li, loop, 0)
Otherwise looks ok. Please update and re-post.
Thanks,
Richard.
> Index: testsuite/gcc.dg/tree-ssa/cunroll-1.c
> ===================================================================
> --- testsuite/gcc.dg/tree-ssa/cunroll-1.c (revision 0)
> +++ testsuite/gcc.dg/tree-ssa/cunroll-1.c (revision 0)
> @@ -0,0 +1,12 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O3 -fdump-tree-cunroll-details" } */
> +int a[2];
> +test(int c)
> +{
> + int i;
> + for (i=0;i<c;i++)
> + a[i]=5;
> +}
> +/* Array bounds says the loop will not roll much. */
> +/* { dg-final { scan-tree-dump-not "Unrolled loop 1 completely (duplicated 1
> times). Last iteration exit edge was proved true." "cunroll"} } */
> +/* { dg-final { cleanup-tree-dump "cunroll" } } */
> Index: testsuite/gcc.dg/tree-ssa/cunroll-2.c
> ===================================================================
> --- testsuite/gcc.dg/tree-ssa/cunroll-2.c (revision 0)
> +++ testsuite/gcc.dg/tree-ssa/cunroll-2.c (revision 0)
> @@ -0,0 +1,16 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O3 -fdump-tree-cunroll-details" } */
> +int a[2];
> +test(int c)
> +{
> + int i;
> + for (i=0;i<c;i++)
> + {
> + a[i]=5;
> + if (test2())
> + return;
> + }
> +}
> +/* We are not able to get rid of the final conditional because the loop has
> two exits. */
> +/* { dg-final { scan-tree-dump-not "Unrolled loop 1 completely (duplicated 2
> times)." "cunroll"} } */
> +/* { dg-final { cleanup-tree-dump "cunroll" } } */
> Index: testsuite/gcc.dg/tree-ssa/cunroll-3.c
> ===================================================================
> --- testsuite/gcc.dg/tree-ssa/cunroll-3.c (revision 0)
> +++ testsuite/gcc.dg/tree-ssa/cunroll-3.c (revision 0)
> @@ -0,0 +1,15 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-cunrolli-details" } */
> +int a[1];
> +test(int c)
> +{
> + int i;
> + for (i=0;i<c;i++)
> + {
> + a[i]=5;
> + }
> +}
> +/* If we start duplicating headers prior curoll, this loop will have 0
> iterations. */
> +
> +/* { dg-final { scan-tree-dump-not "Unrolled loop 1 completely (duplicated 1
> times)." "cunrolli"} } */
> +/* { dg-final { cleanup-tree-dump "cunrolli" } } */
> Index: testsuite/gcc.dg/tree-ssa/cunroll-4.c
> ===================================================================
> --- testsuite/gcc.dg/tree-ssa/cunroll-4.c (revision 0)
> +++ testsuite/gcc.dg/tree-ssa/cunroll-4.c (revision 0)
> @@ -0,0 +1,20 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O3 -fdump-tree-cunroll-details" } */
> +int a[1];
> +test(int c)
> +{
> + int i=0,j;
> + for (i=0;i<c;i++)
> + {
> + for (j=0;j<c;j++)
> + {
> + a[i]=5;
> + test2();
> + }
> + }
> +}
> +
> +/* We should do this as part of cunrolli, but our cost model do not take
> into account early exit
> + from the last iteration. */
> +/* { dg-final { scan-tree-dump-not "Turned loop 1 to non-loop; it never
> loops. Last iteration exit edge was proved true." "cunrolli"} } */
> +/* { dg-final { cleanup-tree-dump "cunroll" } } */
> Index: testsuite/gcc.dg/tree-ssa/cunroll-5.c
> ===================================================================
> --- testsuite/gcc.dg/tree-ssa/cunroll-5.c (revision 0)
> +++ testsuite/gcc.dg/tree-ssa/cunroll-5.c (revision 0)
> @@ -0,0 +1,12 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O3 -fdump-tree-cunroll-details" } */
> +int *a;
> +test(int c)
> +{
> + int i;
> + for (i=0;i<6;i++)
> + a[i]=5;
> +}
> +/* Basic testcase for complette unrolling. */
> +/* { dg-final { scan-tree-dump-not "Unrolled loop 1 completely (duplicated 5
> times). Exit condition of peeled iterations was eliminated. Last iteration
> exit edge was proved true." "cunroll"} } */
> +/* { dg-final { cleanup-tree-dump "cunroll" } } */
> Index: cfgloopmanip.c
> ===================================================================
> --- cfgloopmanip.c (revision 192360)
> +++ cfgloopmanip.c (working copy)
> @@ -37,7 +37,6 @@ static int find_path (edge, basic_block
> static void fix_loop_placements (struct loop *, bool *);
> static bool fix_bb_placement (basic_block);
> static void fix_bb_placements (basic_block, bool *);
> -static void unloop (struct loop *, bool *);
>
> /* Checks whether basic block BB is dominated by DATA. */
> static bool
> @@ -895,7 +894,7 @@ loopify (edge latch_edge, edge header_ed
> If this may cause the information about irreducible regions to become
> invalid, IRRED_INVALIDATED is set to true. */
>
> -static void
> +void
> unloop (struct loop *loop, bool *irred_invalidated)
> {
> basic_block *body;
> Index: tree-ssa-loop-ivcanon.c
> ===================================================================
> --- tree-ssa-loop-ivcanon.c (revision 192360)
> +++ tree-ssa-loop-ivcanon.c (working copy)
> @@ -231,7 +231,7 @@ tree_estimate_loop_size (struct loop *lo
> /* Look for reasons why we might optimize this stmt away. */
>
> /* Exit conditional. */
> - if (body[i] == exit->src && stmt == last_stmt (exit->src))
> + if (exit && body[i] == exit->src && stmt == last_stmt (exit->src))
> {
> if (dump_file && (dump_flags & TDF_DETAILS))
> fprintf (dump_file, " Exit condition will be eliminated.\n");
> @@ -326,13 +326,43 @@ try_unroll_loop_completely (struct loop
> unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll, unr_insns;
> gimple cond;
> struct loop_size size;
> + bool n_unroll_found = false;
> + HOST_WIDE_INT maxiter;
> + basic_block latch;
> + edge latch_edge;
> + location_t locus;
> + int flags;
> + bool irred_invalidated = false;
> + gimple stmt;
> + gimple_stmt_iterator gsi;
> + edge other_edge = NULL, last_exit;
> + int num = loop->num;
> + bool last_iteration_updated = false;
> +
> + /* See if we proved number of iterations to be low constant. */
> + if (host_integerp (niter, 1))
> + {
> + n_unroll = tree_low_cst (niter, 1);
> + n_unroll_found = true;
> + }
>
> - if (loop->inner)
> + /* See if we can improve our estimate by using recorded loop bounds. */
> + maxiter = max_loop_iterations_int (loop);
> + if (maxiter >= 0
> + && (!n_unroll_found || (unsigned HOST_WIDE_INT)maxiter < n_unroll))
> + {
> + n_unroll = maxiter;
> + n_unroll_found = true;
> + }
> +
> + if (!n_unroll_found)
> return false;
>
> - if (!host_integerp (niter, 1))
> + /* We unroll only inner loops, because we do not consider it profitable
> + otheriwse. We still can cancel loopback edge of not rolling loop;
> + this is always a good idea. */
> + if (loop->inner && n_unroll)
> return false;
> - n_unroll = tree_low_cst (niter, 1);
>
> max_unroll = PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES);
> if (n_unroll > max_unroll)
> @@ -340,6 +370,10 @@ try_unroll_loop_completely (struct loop
>
> if (n_unroll)
> {
> + sbitmap wont_exit;
> + edge e;
> + unsigned i;
> + VEC (edge, heap) *to_remove = NULL;
> if (ul == UL_SINGLE_ITER)
> return false;
>
> @@ -372,14 +408,6 @@ try_unroll_loop_completely (struct loop
> fprintf (dump_file, "Not unrolling loop %d.\n", loop->num);
> return false;
> }
> - }
> -
> - if (n_unroll)
> - {
> - sbitmap wont_exit;
> - edge e;
> - unsigned i;
> - VEC (edge, heap) *to_remove = NULL;
>
> initialize_original_copy_tables ();
> wont_exit = sbitmap_alloc (n_unroll + 1);
> @@ -408,24 +436,143 @@ try_unroll_loop_completely (struct loop
> free_original_copy_tables ();
> }
>
> - cond = last_stmt (exit->src);
> - if (exit->flags & EDGE_TRUE_VALUE)
> - gimple_cond_make_true (cond);
> - else
> - gimple_cond_make_false (cond);
> - update_stmt (cond);
> + /* After complette unrolling we still may get rid of the conditional
> + on exit in the last copy even if we have no idea what it does.
> + This is quite common case for loops of form
> +
> + int a[5];
> + for (i=0;i<b;i++)
> + a[i]=0;
> +
> + Here we prove the loop to iterate 5 times but we do not know
> + it from induction variable.
> +
> + We want to make the conditional of exit true, so we can only
> + consider exits that are not part of the inner (irreducible) loops
> + so we know that the conditional is tested at most once per iteration.
> +
> + Situation is more complicated withloops with multiple exists:
> +
> + int a[5];
> + for (i=0;i<b;i++)
> + {
> + if (blah)
> + break;
> + a[i]=0;
> + }
> +
> + Here we could cancel the conditional of if "(blah)". And:
> +
> + int a[5];
> + for (i=0;i<b;i++)
> + {
> + a[i]=0;
> + if (blah)
> + break;
> + }
> +
> + Here we can cancel the last i<b test.
> +
> + To handle these we need to track all statements containing code that
> + can not execute on last iteration (in tree-ssa-loop-niter).
> + Then we can use control dependnecy (not computed here) to cancel all
> + the paths leading to them unless they are part of the inner loops.
> + This however seems bit like an overkill so we handle only the
> + simple case of single exit until interesting testcases appears. */
> + last_exit = exit;
> + if (!last_exit)
> + {
> + last_exit = single_exit (loop);
> + if (!last_exit || last_exit->src->loop_father != loop
> + || !(last_exit->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
> + last_exit = NULL;
> + else
> + {
> + if (last_exit->src->flags & BB_IRREDUCIBLE_LOOP)
> + last_exit = NULL;
> + }
> + }
> +
> + /* If loop has only one exit edge, we can remove the conditional from
> + the last copy of the loop.
> + TODO: We should account this update into cost model. */
> + if (last_exit)
> + {
> + cond = last_stmt (last_exit->src);
> + if (last_exit->flags & EDGE_TRUE_VALUE)
> + gimple_cond_make_true (cond);
> + else
> + gimple_cond_make_false (cond);
> + update_stmt (cond);
> + other_edge = EDGE_SUCC (last_exit->src, 0);
> + if (other_edge == last_exit)
> + other_edge = EDGE_SUCC (last_exit->src, 1);
> + last_iteration_updated = true;
> + }
> +
> + /* Now destroy the loop. First try to do so by cancelling the
> + patch from exit conditional if we identified good candidate.
> +
> + TODO: We should update the loop profile for the fact that
> + the last iteration no longer executes. */
> + if (!other_edge || !remove_path (other_edge))
> + {
> + /* We did not manage to cancel the loop by removing the patch.
> + The loop latch remains reachable even if it will never be reached
> + at runtime. We must redirect it to somewhere, so create basic
> + block containg __builtin_unreachable call for this reason. */
> + latch = loop->latch;
> + latch_edge = loop_latch_edge (loop);
> + flags = latch_edge->flags;
> + locus = latch_edge->goto_locus;
> +
> + /* Unloop destroys the latch edge. */
> + unloop (loop, &irred_invalidated);
> + if (irred_invalidated)
> + mark_irreducible_loops ();
> +
> + /* Create new basic block for the latch edge destination and wire
> + it in. */
> + stmt = gimple_build_call (builtin_decl_implicit
> (BUILT_IN_UNREACHABLE), 0);
> + latch_edge = make_edge (latch, create_basic_block (NULL, NULL, latch),
> flags);
> + gsi = gsi_start_bb (latch_edge->dest);
> + gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
> + latch_edge->dest->loop_father = current_loops->tree_root;
> + set_immediate_dominator (CDI_DOMINATORS, latch_edge->dest,
> latch_edge->src);
> + latch_edge->probability = 0;
> + latch_edge->count = 0;
> + latch_edge->flags |= flags;
> + latch_edge->goto_locus = locus;
> + }
>
> if (dump_file && (dump_flags & TDF_DETAILS))
> - fprintf (dump_file, "Unrolled loop %d completely.\n", loop->num);
> + {
> + if (!n_unroll)
> + fprintf (dump_file, "Turned loop %d to non-loop; it never
> loops.%s\n", num,
> + last_iteration_updated
> + ? " Last iteration exit edge was proved true." : "");
> + else
> + {
> + fprintf (dump_file, "Unrolled loop %d completely "
> + "(duplicated %i times).%s%s\n", num, (int)n_unroll,
> + exit
> + ? " Exit condition of peeled iterations was eliminated." :
> "",
> + last_iteration_updated
> + ? " Last iteration exit edge was proved true." : "");
> + }
> + }
>
> - return true;
> + return true;
> }
>
> /* Adds a canonical induction variable to LOOP if suitable.
> CREATE_IV is true if we may create a new iv. UL determines
> which loops we are allowed to completely unroll. If TRY_EVAL is true, we
> try
> to determine the number of iterations of a loop by direct evaluation.
> - Returns true if cfg is changed. */
> + Returns true if cfg is changed.
> +
> + IRREDUCIBLE_LOOPS_FOUND is used to bookkeep if we discovered irreducible
> + loops. This is used in a special case of the exit condition analysis. */
>
> static bool
> canonicalize_loop_induction_variables (struct loop *loop,
> @@ -455,22 +602,34 @@ canonicalize_loop_induction_variables (s
> || TREE_CODE (niter) != INTEGER_CST))
> niter = find_loop_niter_by_eval (loop, &exit);
>
> - if (chrec_contains_undetermined (niter)
> - || TREE_CODE (niter) != INTEGER_CST)
> - return false;
> + if (TREE_CODE (niter) != INTEGER_CST)
> + exit = NULL;
> }
>
> - if (dump_file && (dump_flags & TDF_DETAILS))
> + /* We work exceptionally hard here to estimate the bound
> + by find_loop_niter_by_eval. Be sure to keep it for future. */
> + if (niter && TREE_CODE (niter) == INTEGER_CST)
> + record_niter_bound (loop, tree_to_double_int (niter), false, true);
> +
> + if (dump_file && (dump_flags & TDF_DETAILS)
> + && TREE_CODE (niter) == INTEGER_CST)
> {
> fprintf (dump_file, "Loop %d iterates ", loop->num);
> print_generic_expr (dump_file, niter, TDF_SLIM);
> fprintf (dump_file, " times.\n");
> }
> + if (dump_file && (dump_flags & TDF_DETAILS)
> + && max_loop_iterations_int (loop) >= 0)
> + {
> + fprintf (dump_file, "Loop %d iterates at most %i times.\n", loop->num,
> + (int)max_loop_iterations_int (loop));
> + }
>
> if (try_unroll_loop_completely (loop, exit, niter, ul))
> return true;
>
> - if (create_iv)
> + if (create_iv
> + && niter && !chrec_contains_undetermined (niter))
> create_canonical_iv (loop, exit, niter);
>
> return false;
> @@ -483,11 +642,14 @@ unsigned int
> canonicalize_induction_variables (void)
> {
> loop_iterator li;
> - struct loop *loop;
> + struct loop *loop, *next;
> bool changed = false;
>
> - FOR_EACH_LOOP (li, loop, 0)
> + for (fel_init (&li, &next, LI_ONLY_INNERMOST); next;)
> {
> + loop = next;
> + fel_next (&li, &next);
> +
> changed |= canonicalize_loop_induction_variables (loop,
> true, UL_SINGLE_ITER,
> true);
> @@ -591,14 +753,18 @@ tree_unroll_loops_completely (bool may_i
> bool changed;
> enum unroll_level ul;
> int iteration = 0;
> + struct loop *next;
>
> do
> {
> changed = false;
>
> - FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
> + for (fel_init (&li, &next, 0); next;)
> {
> - struct loop *loop_father = loop_outer (loop);
> + struct loop *loop_father = loop_outer (next);
> +
> + loop = next;
> + fel_next (&li, &next);
>
> if (may_increase_size && optimize_loop_for_speed_p (loop)
> /* Unroll outermost loops only if asked to do so or they do
> Index: fortran/f95-lang.c
> ===================================================================
> --- fortran/f95-lang.c (revision 192360)
> +++ fortran/f95-lang.c (working copy)
> @@ -908,6 +908,11 @@ gfc_init_builtin_functions (void)
> gfc_define_builtin ("__builtin_expect", ftype, BUILT_IN_EXPECT,
> "__builtin_expect", ATTR_CONST_NOTHROW_LEAF_LIST);
>
> + ftype = build_function_type_list (void_type_node, NULL_TREE);
> +
> + gfc_define_builtin ("__builtin_unreachable", ftype, BUILT_IN_EXPECT,
> + "__builtin_unreachable", ATTR_NORETURN_NOTHROW_LEAF_LIST);
> +
> ftype = build_function_type_list (void_type_node,
> pvoid_type_node, NULL_TREE);
> gfc_define_builtin ("__builtin_free", ftype, BUILT_IN_FREE,
> Index: cfgloop.h
> ===================================================================
> --- cfgloop.h (revision 192360)
> +++ cfgloop.h (working copy)
> @@ -319,7 +319,8 @@ extern struct loop *loopify (edge, edge,
> struct loop * loop_version (struct loop *, void *,
> basic_block *, unsigned, unsigned, unsigned, bool);
> extern bool remove_path (edge);
> -void scale_loop_frequencies (struct loop *, int, int);
> +extern void scale_loop_frequencies (struct loop *, int, int);
> +extern void unloop (struct loop *, bool *);
>
> /* Induction variable analysis. */
>
>
>
--
Richard Biener <rguent...@suse.de>
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend
