From patchwork Sat Jan 21 21:21:48 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andrew Pinski X-Patchwork-Id: 137209 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 27916B6FA0 for ; Sun, 22 Jan 2012 08:22:07 +1100 (EST) Comment: DKIM? See http://www.dkim.org DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=gcc.gnu.org; s=default; x=1327785728; h=Comment: DomainKey-Signature:Received:Received:Received:Received: MIME-Version:Received:Received:Date:Message-ID:Subject:From:To: Content-Type:Mailing-List:Precedence:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:Sender:Delivered-To; bh=l4obGsU AgOpg1wvwqX59SMiwxjw=; b=h7BfpaK/sL8lTavTGaWLO/4cIOA2qeSiSPDH0NX GSvPxIhvzLE+KIIDTXQ3ohT2O24eENGXjUjCZkzDra0mzTh50Nl6+wJjpPxN/vjq 09APavnUnJv4BAkG3QM96VnhcWJJQZkzADgB69rbQv3oS0jBYhG6KszgoSiEuqC5 zWn0= Comment: DomainKeys? See http://antispam.yahoo.com/domainkeys DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=default; d=gcc.gnu.org; h=Received:Received:X-SWARE-Spam-Status:X-Spam-Check-By:Received:Received:MIME-Version:Received:Received:Date:Message-ID:Subject:From:To:Content-Type:X-IsSubscribed:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=Vr+21ETqWtBXybLcb8l9F2CAugCYTk+6vdioGugIPtZWmv8ULYeBjgPr/EaRn/ EzQUZwCL0EebRvkZxG+5MqrXcgIX9ZTtTdxHnJTSjRxvej9RnNpomx6VMrJG5DJ+ 0n+xDKyYkniRzJpSEEY8ppV2Ah2GKtVPR9VEKBnzi+wVU=; Received: (qmail 539 invoked by alias); 21 Jan 2012 21:22:04 -0000 Received: (qmail 531 invoked by uid 22791); 21 Jan 2012 21:22:03 -0000 X-SWARE-Spam-Status: No, hits=-2.2 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, RCVD_IN_DNSWL_LOW, TW_CF, TW_TM X-Spam-Check-By: sourceware.org Received: from mail-we0-f175.google.com (HELO mail-we0-f175.google.com) (74.125.82.175) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Sat, 21 Jan 2012 21:21:49 +0000 Received: by werc1 with SMTP id c1so18972wer.20 for ; Sat, 21 Jan 2012 13:21:48 -0800 (PST) MIME-Version: 1.0 Received: by 10.216.131.78 with SMTP id l56mr1659221wei.56.1327180908317; Sat, 21 Jan 2012 13:21:48 -0800 (PST) Received: by 10.216.12.209 with HTTP; Sat, 21 Jan 2012 13:21:48 -0800 (PST) Date: Sat, 21 Jan 2012 13:21:48 -0800 Message-ID: Subject: [PATCH] Fix PR 50971 and PR 35629: Only one loop detected when there should be two From: Andrew Pinski To: GCC Patches X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org 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; }