This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH] Unswitching fixes (PR middle-end/43866)
- From: Richard Guenther <rguenther at suse dot de>
- To: Jakub Jelinek <jakub at redhat dot com>
- Cc: Zdenek Dvorak <ook at ucw dot cz>, gcc-patches at gcc dot gnu dot org
- Date: Fri, 25 Jun 2010 13:53:30 +0200 (CEST)
- Subject: Re: [PATCH] Unswitching fixes (PR middle-end/43866)
- References: <20100625115114.GJ12443@tyan-ft48-01.lab.bos.redhat.com>
On Fri, 25 Jun 2010, Jakub Jelinek wrote:
> Hi!
>
> This patch fixes a couple of problems in tree-ssa-loop-unswitch.c.
>
> The first problem is in tree_may_unswitch_on - a tuplification error.
> Result of build2 (cond_code, ...) is never integer_zerop nor
> integer_nonzerop. While we could fold, we can just test for the canonical
> true/false conditions using gimple_cond* predicates.
>
> Another problem is that when hitting --param max-unswitch-level nesting
> level we wouldn't adjust the conditions. Some further pass probably would
> do so, but when we already have the code to handle it, it is IMHO better to
> do it right away. When hitting the max level we just won't consider any new
> conditions for unswitching.
>
> The last issue is that there is no cfg cleanup in between the unswitching
> levels, which means we often choose conditions that are never tested
> in any reachable bb in the loop. Instead of doing cfg cleanup and updating
> everything, this patch just does a quick discovery of reachable bbs in the
> loop (which takes into account the modified conditions) and doesn't consider
> conditions that aren't reachable.
>
> Bootstrapped/regtested on x86_64-linux and i686-linux. Ok for trunk?
Ok.
Thanks,
Richard.
> 2010-06-25 Jakub Jelinek <jakub@redhat.com>
>
> PR middle-end/43866
> * tree-ssa-loop-unswitch.c (tree_may_unswitch_on): If stmt is always
> true or always false, return NULL_TREE.
> (tree_unswitch_single_loop): Optimize conditions even when reaching
> max-unswitch-level parameter. If num > 0, optimize first all conditions
> using entry checks, then do still reachable block discovery and consider
> only conditions in still reachable basic blocks in the loop.
>
> * gfortran.dg/pr43866.f90: New test.
>
> --- gcc/tree-ssa-loop-unswitch.c.jj 2010-06-07 11:25:05.000000000 +0200
> +++ gcc/tree-ssa-loop-unswitch.c 2010-06-24 17:25:09.000000000 +0200
> @@ -129,6 +129,12 @@ tree_may_unswitch_on (basic_block bb, st
> if (!stmt || gimple_code (stmt) != GIMPLE_COND)
> return NULL_TREE;
>
> + /* To keep the things simple, we do not directly remove the conditions,
> + but just replace tests with 0 != 0 resp. 1 != 0. Prevent the infinite
> + loop where we would unswitch again on such a condition. */
> + if (gimple_cond_true_p (stmt) || gimple_cond_false_p (stmt))
> + return NULL_TREE;
> +
> /* Condition must be invariant. */
> FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
> {
> @@ -142,12 +148,6 @@ tree_may_unswitch_on (basic_block bb, st
> cond = build2 (gimple_cond_code (stmt), boolean_type_node,
> gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
>
> - /* To keep the things simple, we do not directly remove the conditions,
> - but just replace tests with 0/1. Prevent the infinite loop where we
> - would unswitch again on such a condition. */
> - if (integer_zerop (cond) || integer_nonzerop (cond))
> - return NULL_TREE;
> -
> return cond;
> }
>
> @@ -193,21 +193,14 @@ tree_unswitch_single_loop (struct loop *
> {
> basic_block *bbs;
> struct loop *nloop;
> - unsigned i;
> + unsigned i, found;
> tree cond = NULL_TREE;
> gimple stmt;
> bool changed = false;
>
> - /* Do not unswitch too much. */
> - if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
> - {
> - if (dump_file && (dump_flags & TDF_DETAILS))
> - fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
> - return false;
> - }
> -
> i = 0;
> bbs = get_loop_body (loop);
> + found = loop->num_nodes;
>
> while (1)
> {
> @@ -218,8 +211,17 @@ tree_unswitch_single_loop (struct loop *
>
> if (i == loop->num_nodes)
> {
> - free (bbs);
> - return changed;
> + if (dump_file
> + && num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL)
> + && (dump_flags & TDF_DETAILS))
> + fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
> +
> + if (found == loop->num_nodes)
> + {
> + free (bbs);
> + return changed;
> + }
> + break;
> }
>
> cond = simplify_using_entry_checks (loop, cond);
> @@ -236,19 +238,107 @@ tree_unswitch_single_loop (struct loop *
> gimple_cond_set_condition_from_tree (stmt, boolean_false_node);
> changed = true;
> }
> + /* Do not unswitch too much. */
> + else if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
> + {
> + i++;
> + continue;
> + }
> + /* In nested tree_unswitch_single_loop first optimize all conditions
> + using entry checks, then discover still reachable blocks in the
> + loop and find the condition only among those still reachable bbs. */
> + else if (num != 0)
> + {
> + if (found == loop->num_nodes)
> + found = i;
> + i++;
> + continue;
> + }
> else
> - break;
> + {
> + found = i;
> + break;
> + }
>
> update_stmt (stmt);
> i++;
> }
>
> + if (num != 0)
> + {
> + basic_block *tos, *worklist;
> +
> + /* When called recursively, first do a quick discovery
> + of reachable bbs after the above changes and only
> + consider conditions in still reachable bbs. */
> + tos = worklist = XNEWVEC (basic_block, loop->num_nodes);
> +
> + for (i = 0; i < loop->num_nodes; i++)
> + bbs[i]->flags &= ~BB_REACHABLE;
> +
> + /* Start with marking header. */
> + *tos++ = bbs[0];
> + bbs[0]->flags |= BB_REACHABLE;
> +
> + /* Iterate: find everything reachable from what we've already seen
> + within the same innermost loop. Don't look through false edges
> + if condition is always true or true edges if condition is
> + always false. */
> + while (tos != worklist)
> + {
> + basic_block b = *--tos;
> + edge e;
> + edge_iterator ei;
> + int flags = 0;
> +
> + if (EDGE_COUNT (b->succs) == 2)
> + {
> + gimple stmt = last_stmt (b);
> + if (stmt
> + && gimple_code (stmt) == GIMPLE_COND)
> + {
> + if (gimple_cond_true_p (stmt))
> + flags = EDGE_FALSE_VALUE;
> + else if (gimple_cond_false_p (stmt))
> + flags = EDGE_TRUE_VALUE;
> + }
> + }
> +
> + FOR_EACH_EDGE (e, ei, b->succs)
> + {
> + basic_block dest = e->dest;
> +
> + if (dest->loop_father == loop
> + && !(dest->flags & BB_REACHABLE)
> + && !(e->flags & flags))
> + {
> + *tos++ = dest;
> + dest->flags |= BB_REACHABLE;
> + }
> + }
> + }
> +
> + free (worklist);
> +
> + /* Find a bb to unswitch on. */
> + for (; found < loop->num_nodes; found++)
> + if ((bbs[found]->flags & BB_REACHABLE)
> + && (cond = tree_may_unswitch_on (bbs[found], loop)))
> + break;
> +
> + if (found == loop->num_nodes)
> + {
> + free (bbs);
> + return changed;
> + }
> + }
> +
> if (dump_file && (dump_flags & TDF_DETAILS))
> fprintf (dump_file, ";; Unswitching loop\n");
>
> initialize_original_copy_tables ();
> /* Unswitch the loop on this condition. */
> - nloop = tree_unswitch_loop (loop, bbs[i], cond);
> + nloop = tree_unswitch_loop (loop, bbs[found], cond);
> if (!nloop)
> {
> free_original_copy_tables ();
> --- gcc/testsuite/gfortran.dg/pr43866.f90.jj 2010-06-25 09:51:40.000000000 +0200
> +++ gcc/testsuite/gfortran.dg/pr43866.f90 2010-06-25 09:53:29.000000000 +0200
> @@ -0,0 +1,43 @@
> +! PR middle-end/43866
> +! { dg-do run }
> +! { dg-options "-funswitch-loops -fbounds-check" }
> +
> +MODULE PR43866
> + IMPLICIT NONE
> + TYPE TT
> + REAL(KIND=4), DIMENSION(:,:), POINTER :: A
> + REAL(KIND=8), DIMENSION(:,:), POINTER :: B
> + END TYPE
> +CONTAINS
> + SUBROUTINE FOO(M,X,Y,T)
> + TYPE(TT), POINTER :: M
> + INTEGER, INTENT(IN) :: Y, X
> + INTEGER :: C, D
> + LOGICAL :: T
> + REAL(KIND = 4), DIMENSION(:,:), POINTER :: P
> + REAL(KIND = 8), DIMENSION(:,:), POINTER :: Q
> +
> + Q => M%B
> + P => M%A
> + DO C=1,X
> + DO D=C+1,Y
> + IF (T) THEN
> + P(D,C)=P(C,D)
> + ELSE
> + Q(D,C)=Q(C,D)
> + ENDIF
> + ENDDO
> + ENDDO
> + END SUBROUTINE FOO
> +END MODULE PR43866
> +
> + USE PR43866
> + TYPE(TT), POINTER :: Q
> + INTEGER, PARAMETER :: N=17
> + ALLOCATE (Q)
> + ALLOCATE (Q%B(N,N))
> + Q%B=0
> + CALL FOO (Q,N,N,.FALSE.)
> +END
> +
> +! { dg-final { cleanup-modules "pr43866" } }
>
> Jakub
>
>
--
Richard Guenther <rguenther@suse.de>
Novell / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746 - GF: Markus Rex