Message ID | 20100625115114.GJ12443@tyan-ft48-01.lab.bos.redhat.com |
---|---|
State | New |
Headers | show |
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 > >
--- 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" } }