From patchwork Fri Jun 25 11:51:14 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: Unswitching fixes (PR middle-end/43866) From: Jakub Jelinek X-Patchwork-Id: 56904 Message-Id: <20100625115114.GJ12443@tyan-ft48-01.lab.bos.redhat.com> To: Richard Guenther , Zdenek Dvorak Cc: gcc-patches@gcc.gnu.org Date: Fri, 25 Jun 2010 13:51:14 +0200 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? 2010-06-25 Jakub Jelinek 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. Jakub --- 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" } }