Ping? Rebootstrapped on x86_64-linux-gnu with no regressions. Thanks, Andrew Pinski
On Sat, Jan 21, 2012 at 1:21 PM, Andrew Pinski <pins...@gmail.com> wrote: > The problem with these two bug reports is that the cfgloop does not do > a good job for disambiguating some loops. This patch rewrites > find_subloop_latch_edge_by_ivs to be better. It is able to detect > much more loops and gets the ones which are referenced in PR 50971 and > PR 35629. It does make sure the loops it finds are really loops and > not ones where the continue would cause a loop not to be done. > > OK for 4.8 when stage 1 comes? Bootstrapped and tested on > x86_64-linux-gnu with no regressions. > > ChangeLog: > cfgloop.c (skip_to_exit): New function. > (find_subloop_latch_edge_by_ivs): Rewrite to better detect subloop latches by > IVs. Also look at the cfg for those IVs to check for a better choice. > > testsuite/ChangeLog: > * gcc.dg/tree-ssa/loop-25.c: Remove xfails and remove "Found latch > edge"/"Merged latch edges" tests. > * gcc.dg/tree-ssa/loop-38.c: New testcase.
Index: testsuite/gcc.dg/tree-ssa/loop-25.c =================================================================== --- testsuite/gcc.dg/tree-ssa/loop-25.c (revision 183364) +++ testsuite/gcc.dg/tree-ssa/loop-25.c (working copy) @@ -120,10 +120,8 @@ void test5 (void) /* { dg-final { scan-tree-dump-times "Disambiguating loop" 5 "profile_estimate" } } */ /* For the following xfail marks, see PR35629. */ -/* { dg-final { scan-tree-dump-times "Found latch edge" 5 "profile_estimate" { xfail *-*-* } } } */ -/* { dg-final { scan-tree-dump-times "Merged latch edges" 2 "profile_estimate" { xfail *-*-* } } } */ -/* { dg-final { scan-tree-dump-times "4 loops found" 2 "profile_estimate" { xfail *-*-* } } } */ -/* { dg-final { scan-tree-dump-times "3 loops found" 2 "profile_estimate" { xfail *-*-* } } } */ -/* { dg-final { scan-tree-dump-times "2 loops found" 1 "profile_estimate" { xfail *-*-* } } } */ +/* { dg-final { scan-tree-dump-times "4 loops found" 2 "profile_estimate" } } */ +/* { dg-final { scan-tree-dump-times "3 loops found" 2 "profile_estimate" } } */ +/* { dg-final { scan-tree-dump-times "2 loops found" 1 "profile_estimate" } } */ /* { dg-final { cleanup-tree-dump "profile_estimate" } } */ Index: testsuite/gcc.dg/tree-ssa/loop-38.c =================================================================== --- testsuite/gcc.dg/tree-ssa/loop-38.c (revision 0) +++ testsuite/gcc.dg/tree-ssa/loop-38.c (revision 0) @@ -0,0 +1,26 @@ +/* { dg-do compile } */ +/* { dg-options "-O1 -fdump-tree-ch" } */ + +typedef struct basket +{ + int *a; + int cost; + int abs_cost; +} BASKET; +BASKET *perm[50 +300 +1]; + + +int f(int a, int *b, int cut) +{ + do { + while (perm[a]->abs_cost > cut) + a++; + a++; + } while (b[a]); + return a; +} + +/* { dg-final { scan-tree-dump-times "Disambiguating loop" 1 "ch" } } */ +/* { dg-final { scan-tree-dump-times "3 loops found" 1 "ch" } } */ + +/* { dg-final { cleanup-tree-dump "ch" } } */ Index: cfgloop.c =================================================================== --- cfgloop.c (revision 183364) +++ cfgloop.c (working copy) @@ -548,63 +548,200 @@ find_subloop_latch_edge_by_profile (VEC return me; } +/* Return the basic block where we might be doing an exit from a loop + if we go back up the cfg starting at basic block B skipping other loops + on the way and join points too. */ +static basic_block +skip_to_exit (basic_block b, struct loop *loop, unsigned succ_edge_count) +{ + /* Skip to the begining of the loop if possible, we don't need to check + succ_edge count for loops. */ + if (b->loop_father != loop) + { + edge e; + edge_iterator ei; + edge preheader_e = NULL; + + struct loop *oloop = b->loop_father; + /* There are multiple latches, we can't figure out the preheader, + just return b. */ + if (oloop->latch == NULL) + return NULL; + FOR_EACH_EDGE (e, ei, oloop->header->preds) + if (e->src != oloop->latch && preheader_e == NULL) + preheader_e = e; + else if (e->src != oloop->latch && preheader_e != NULL) + { + preheader_e = NULL; + break; + } + /* Only one preheader edge. */ + if (preheader_e != NULL) + return skip_to_exit (preheader_e->src, loop, 1); + else + return NULL; + } + if (EDGE_COUNT (b->succs) != succ_edge_count) + return b; + /* Skip basic blocks where it is just a passthrough. */ + if (single_pred_p (b)) + return skip_to_exit (single_pred_edge (b)->src, loop, 1); + /* A join point, find the point where the join was from. */ + /* FIXME should handle the case where we have more than two + predicates. */ + if (EDGE_COUNT (b->preds) == 2) + { + basic_block c, d; + if (EDGE_PRED (b, 0)->flags & EDGE_ABNORMAL + || EDGE_PRED (b, 1)->flags & EDGE_ABNORMAL) + return NULL; + c = skip_to_exit (EDGE_PRED (b, 0)->src, loop, 1); + if (c == NULL) + return NULL; + d = skip_to_exit (EDGE_PRED (b, 1)->src, loop, 1); + if (c == NULL) + return NULL; + if (c != d) + return NULL; + return skip_to_exit (d, loop, 2); + } + return b; +} + /* Among LATCHES, guesses a latch edge of LOOP corresponding to subloop, based on the structure of induction variables. Returns this edge, or NULL if we do not find any. - We are quite conservative, and look just for an obvious simple innermost - loop (which is the case where we would lose the most performance by not - disambiguating the loop). More precisely, we look for the following - situation: The source of the chosen latch edge dominates sources of all - the other latch edges. Additionally, the header does not contain a phi node - such that the argument from the chosen edge is equal to the argument from - another edge. */ + We start by finding all the latches that might have an IV defined by them. + If there is only one of them chose that one. If there is more than one find + the one where the accessor of the latch is the header. If none match that + then find the one where the accessor of the latch is a different loop + but only do this if the header has only one successor. */ static edge find_subloop_latch_edge_by_ivs (struct loop *loop ATTRIBUTE_UNUSED, VEC (edge, heap) *latches) { - edge e, latch = VEC_index (edge, latches, 0); - unsigned i; + edge latch = NULL, e; + unsigned i, j; gimple phi; gimple_stmt_iterator psi; tree lop; basic_block bb; + VEC (edge, heap) *extra_latches = NULL; - /* Find the candidate for the latch edge. */ - for (i = 1; VEC_iterate (edge, latches, i, e); i++) - if (dominated_by_p (CDI_DOMINATORS, latch->src, e->src)) - latch = e; - - /* Verify that it dominates all the latch edges. */ - FOR_EACH_VEC_ELT (edge, latches, i, e) - if (!dominated_by_p (CDI_DOMINATORS, e->src, latch->src)) + if (VEC_length (edge, latches) != 1) + { + if (dump_file) + { + fprintf (dump_file, "trying latches:"); + FOR_EACH_VEC_ELT (edge, latches, i, e) + fprintf (dump_file, " %d", e->src->index); + fprintf (dump_file, " that might be a IV subloop.\n"); + } + } + + FOR_EACH_VEC_ELT (edge, latches, i, latch) + { + /* Check for a phi node that would deny that this is a latch edge of + a subloop. */ + for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi)) + { + phi = gsi_stmt (psi); + lop = PHI_ARG_DEF_FROM_EDGE (phi, latch); + + /* Ignore the values that are not changed inside the subloop. */ + if (TREE_CODE (lop) != SSA_NAME + || SSA_NAME_DEF_STMT (lop) == phi) + continue; + if (lop == PHI_RESULT (phi)) + continue; + bb = gimple_bb (SSA_NAME_DEF_STMT (lop)); + if (!bb || !flow_bb_inside_loop_p (loop, bb)) + continue; + /* Ignore virtual operands PHIs as they will always + be different. */ + if (!is_gimple_reg (lop)) + continue; + FOR_EACH_VEC_ELT (edge, latches, j, e) + if (e != latch + && PHI_ARG_DEF_FROM_EDGE (phi, e) == lop) + { + latch = NULL; + goto next_latch; + } + } + next_latch: + if (latch != NULL) + VEC_safe_push (edge, heap, extra_latches, latch); + } + if (VEC_empty (edge, extra_latches)) + { + if (dump_file) + fprintf (dump_file, "no latches for IV subloob.\n"); return NULL; + } - /* Check for a phi node that would deny that this is a latch edge of - a subloop. */ - for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi)) - { - phi = gsi_stmt (psi); - lop = PHI_ARG_DEF_FROM_EDGE (phi, latch); - - /* Ignore the values that are not changed inside the subloop. */ - if (TREE_CODE (lop) != SSA_NAME - || SSA_NAME_DEF_STMT (lop) == phi) - continue; - bb = gimple_bb (SSA_NAME_DEF_STMT (lop)); - if (!bb || !flow_bb_inside_loop_p (loop, bb)) - continue; - - FOR_EACH_VEC_ELT (edge, latches, i, e) - if (e != latch - && PHI_ARG_DEF_FROM_EDGE (phi, e) == lop) - return NULL; + if (VEC_length (edge, extra_latches) != 1) + { + if (dump_file) + { + fprintf (dump_file, "more one latches:"); + FOR_EACH_VEC_ELT (edge, extra_latches, i, e) + fprintf (dump_file, " %d", e->src->index); + fprintf (dump_file, " that might be a IV subloop.\n"); + } + /* Try to look for the subloop where the accessor of the latch is + the header. */ + FOR_EACH_VEC_ELT (edge, extra_latches, i, latch) + { + basic_block b = latch->src; + b = skip_to_exit (b, loop, 1); + if (b == NULL) + continue; + if (b == loop->header) + { + if (dump_file) + { + fprintf (dump_file, "Guessing %d as latch of the subloop.\n", + latch->src->index); + fprintf (dump_file, "Because its immediate accessor" + " is the header.\n"); + } + return latch; + } + } + /* Try to look for the subloop where the accessor of the latch + is a different loop but only do this if the header has only one + successor. */ + if (EDGE_COUNT (loop->header->succs) == 1) + FOR_EACH_VEC_ELT (edge, extra_latches, i, latch) + { + basic_block b = latch->src; + b = skip_to_exit (b, loop, 1); + if (b == NULL) + continue; + b = skip_to_exit (b, loop, 2); + if (b == loop->header) + { + if (dump_file) + { + fprintf (dump_file, "Guessing %d as latch of the subloop.\n", + latch->src->index); + fprintf (dump_file, "Because condition reaches the header.\n"); + } + return latch; + } + } + return NULL; } + latch = VEC_index (edge, extra_latches, 0); + if (dump_file) fprintf (dump_file, "Found latch edge %d -> %d using iv structure.\n", latch->src->index, latch->dest->index); + VEC_free (edge, heap, extra_latches); return latch; }