From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 111663 invoked by alias); 22 Mar 2018 15:44:17 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 111648 invoked by uid 89); 22 Mar 2018 15:44:16 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-24.8 required=5.0 tests=AWL,BAYES_00,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,RCVD_IN_DNSWL_NONE,SPF_PASS,URIBL_RED autolearn=ham version=3.3.2 spammy= X-HELO: relay1.mentorg.com Received: from relay1.mentorg.com (HELO relay1.mentorg.com) (192.94.38.131) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Thu, 22 Mar 2018 15:44:14 +0000 Received: from nat-ies.mentorg.com ([192.94.31.2] helo=SVR-IES-MBX-04.mgc.mentorg.com) by relay1.mentorg.com with esmtps (TLSv1.2:ECDHE-RSA-AES256-SHA384:256) id 1ez2Nw-00047J-J3 from Tom_deVries@mentor.com ; Thu, 22 Mar 2018 08:44:12 -0700 Received: from [137.202.13.181] (137.202.0.87) by SVR-IES-MBX-04.mgc.mentorg.com (139.181.222.4) with Microsoft SMTP Server (TLS) id 15.0.1320.4; Thu, 22 Mar 2018 15:44:08 +0000 Subject: Re: [parloops, PR83126], Use cached affine_ivs canonicalize_loop_ivs To: Richard Biener CC: GCC Patches References: <72456add-0339-35cf-c9d6-6aade4af6050@mentor.com> <4b1d8bca-81b0-16e1-6df9-6bc76fa9d9a7@mentor.com> From: Tom de Vries Message-ID: <61cbd3b6-5d00-a35d-ca14-2cc11954f698@mentor.com> Date: Thu, 22 Mar 2018 15:48:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.6.0 MIME-Version: 1.0 In-Reply-To: Content-Type: multipart/mixed; boundary="------------467E9F79E204D55094D56ACD" X-ClientProxiedBy: svr-ies-mbx-01.mgc.mentorg.com (139.181.222.1) To SVR-IES-MBX-04.mgc.mentorg.com (139.181.222.4) X-SW-Source: 2018-03/txt/msg01202.txt.bz2 --------------467E9F79E204D55094D56ACD Content-Type: text/plain; charset="utf-8"; format=flowed Content-Transfer-Encoding: 7bit Content-length: 4263 On 03/21/2018 04:43 PM, Richard Biener wrote: > On Wed, 21 Mar 2018, Tom de Vries wrote: > >> On 03/12/2018 01:14 PM, Richard Biener wrote: >>> On Thu, 22 Feb 2018, Tom de Vries wrote: >>> >>>> Hi, >>>> >>>> this patch fixes an ICE in the parloops pass. >>>> >>>> The ICE (when compiling the test-case in attached patch) follows from the >>>> fact >>>> that here in gen_parallel_loop the call to canonicalize_loop_ivs fails to >>>> "base all the induction variables in LOOP on a single control one": >>>> ... >>>> /* Base all the induction variables in LOOP on a single control one.*/ >>>> canonicalize_loop_ivs (loop, &nit, true); >>>> ... >>>> >>>> This is caused by the fact that for one of the induction variables, >>>> simple_iv >>>> no longer returns true (as was the case at the start of >>>> gen_parallel_loop). >>>> This seems to be triggered by the fact that during loop_version we call >>>> scev_reset (although I'm not sure why when recalculating scev info we're >>>> not >>>> reaching the same conclusion as before). >>> I guess the real reason is that canonicalize_loop_ivs calls >>> create_iv first which in the parloop case with bump-in-latch true >>> and then incrementally re-writes PHIs, eventually wrecking other >>> PHIs SCEV. In this case the 2nd PHIs evolution depends on the >>> first one but the rewritten ones depend on the new IV already. >>> >>> So the better fix (maybe not 100% enough) would be to re-organize >>> canonicalize_loop_ivs to first do analysis of all PHIs and then >>> rewrite them all. >>> >> >> Focusing on the re-organize first, is this sort of what you had in mind? > > Yes, though not sure why you need to have a hash-map here, just pushing > to a vector of PHIs would work, no? Or alternatively a bitmap > of SSA versions so you have a way to match the gphi iterator with > the set of IVs. But the vector should be sorted in PHI order so > just traversing the PHIs looking for the "next" PHI in the vector > would work I guess. > > Does it help with the original issue btw? > Not as such. The original problem happens before canonicalize_loop_ivs. Perhaps the easiest way to demonstrate the problem is this patch: ... diff --git a/gcc/tree-parloops.c b/gcc/tree-parloops.c index 3a788cc..801fc46 100644 --- a/gcc/tree-parloops.c +++ b/gcc/tree-parloops.c @@ -2254,6 +2254,38 @@ num_phis (basic_block bb, bool count_virtual_p) return nr_phis; } +static unsigned +get_nr_simple_ivs (struct loop *loop) +{ + unsigned cnt = 0; + basic_block *bbs = get_loop_body_in_dom_order (loop); + + for (unsigned i = 0; i < loop->num_nodes; i++) + { + basic_block bb = bbs[i]; + if (bb->loop_father != loop) + continue; + + for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi); + gsi_next (&psi)) + { + gphi *phi = psi.phi (); + tree res = PHI_RESULT (phi); + if (virtual_operand_p (res)) + continue; + + affine_iv iv; + if (!simple_iv (loop, loop, res, &iv, true)) + continue; + cnt++; + } + } + + free (bbs); + + return cnt; +} + /* Generates code to execute the iterations of LOOP in N_THREADS threads in parallel, which can be 0 if that number is to be determined later. @@ -2378,11 +2410,15 @@ gen_parallel_loop (struct loop *loop, initialize_original_copy_tables (); /* We assume that the loop usually iterates a lot. */ + fprintf (stderr, "nr simple ivs: %u @ line %d\n", + get_nr_simple_ivs (loop), __LINE__); loop_version (loop, many_iterations_cond, NULL, profile_probability::likely (), profile_probability::unlikely (), profile_probability::likely (), profile_probability::unlikely (), true); + fprintf (stderr, "nr simple ivs: %u @ line %d\n", + get_nr_simple_ivs (loop), __LINE__); update_ssa (TODO_update_ssa); free_original_copy_tables (); } ... and this output for pr83126.c: ... nr simple ivs: 3 @ line 2414 nr simple ivs: 2 @ line 2421 ... I've written attached follow-up patch that works around that problem by analyzing the phis before calling loop_version. It works for the example, and bootstraps fine, but I'm not familiar enough with loop_version to known whether this is safe or not. Thanks, - Tom --------------467E9F79E204D55094D56ACD Content-Type: text/x-patch; name="0002-parloops-Fix-canonicalize_loop_ivs-in-gen_parallel_loop.patch" Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename*0="0002-parloops-Fix-canonicalize_loop_ivs-in-gen_parallel_loop"; filename*1=".patch" Content-length: 4040 [parloops] Fix canonicalize_loop_ivs in gen_parallel_loop 2018-03-21 Tom de Vries PR tree-optimization/83126 * tree-parloops.c (gen_parallel_loop): Inline canonicalize_loop_ivs. Assert that canonicalize_loop_ivs succeeds. * tree-ssa-loop-manip.c (get_all_phi_affine_ivs): Remove static. (struct phi_affine_iv): Move ... * tree-ssa-loop-manip.h (struct phi_affine_iv): ... here. (get_all_phi_affine_ivs, canonicalize_loop_ivs_1): Declare. --- gcc/tree-parloops.c | 27 ++++++--------------------- gcc/tree-ssa-loop-manip.c | 8 +------- gcc/tree-ssa-loop-manip.h | 10 ++++++++++ 3 files changed, 17 insertions(+), 28 deletions(-) diff --git a/gcc/tree-parloops.c b/gcc/tree-parloops.c index 3a788cc..9c2d19a 100644 --- a/gcc/tree-parloops.c +++ b/gcc/tree-parloops.c @@ -2339,6 +2339,9 @@ gen_parallel_loop (struct loop *loop, we should compute nit = n * m, not nit = n. Also may_be_zero handling would need to be adjusted. */ + auto_vec simple_ivs; + get_all_phi_affine_ivs (loop, &simple_ivs); + type = TREE_TYPE (niter->niter); nit = force_gimple_operand (unshare_expr (niter->niter), &stmts, true, NULL_TREE); @@ -2388,27 +2391,9 @@ gen_parallel_loop (struct loop *loop, } /* Base all the induction variables in LOOP on a single control one. */ - canonicalize_loop_ivs (loop, &nit, true); - if (num_phis (loop->header, false) != reduction_list->elements () + 1) - { - /* The call to canonicalize_loop_ivs above failed to "base all the - induction variables in LOOP on a single control one". Do damage - control. */ - basic_block preheader = loop_preheader_edge (loop)->src; - basic_block cond_bb = single_pred (preheader); - gcond *cond = as_a (gsi_stmt (gsi_last_bb (cond_bb))); - gimple_cond_make_true (cond); - update_stmt (cond); - /* We've gotten rid of the duplicate loop created by loop_version, but - we can't undo whatever canonicalize_loop_ivs has done. - TODO: Fix this properly by ensuring that the call to - canonicalize_loop_ivs succeeds. */ - if (dump_file - && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "canonicalize_loop_ivs failed for loop %d," - " aborting transformation\n", loop->num); - return; - } + canonicalize_loop_ivs_1 (loop, &nit, true, &simple_ivs); + gcc_assert (num_phis (loop->header, false) + == reduction_list->elements () + 1); /* Ensure that the exit condition is the first statement in the loop. The common case is that latch of the loop is empty (apart from the diff --git a/gcc/tree-ssa-loop-manip.c b/gcc/tree-ssa-loop-manip.c index ecda325..6014384 100644 --- a/gcc/tree-ssa-loop-manip.c +++ b/gcc/tree-ssa-loop-manip.c @@ -1453,15 +1453,9 @@ rewrite_phi_with_iv (gphi_iterator *psi, gsi_insert_before (gsi, stmt, GSI_SAME_STMT); } -struct phi_affine_iv -{ - gphi *phi; - affine_iv iv; -}; - /* Return map of phi node result to affine_iv, for all phis in LOOPS. */ -static void +void get_all_phi_affine_ivs (struct loop *loop, auto_vec *simple_ivs) { diff --git a/gcc/tree-ssa-loop-manip.h b/gcc/tree-ssa-loop-manip.h index 390ac6f..ef439be 100644 --- a/gcc/tree-ssa-loop-manip.h +++ b/gcc/tree-ssa-loop-manip.h @@ -19,6 +19,7 @@ along with GCC; see the file COPYING3. If not see #ifndef GCC_TREE_SSA_LOOP_MANIP_H #define GCC_TREE_SSA_LOOP_MANIP_H +#include "tree-ssa-loop.h" typedef void (*transform_callback)(struct loop *, void *); @@ -56,6 +57,15 @@ extern void tree_unroll_loop (struct loop *, unsigned, edge, struct tree_niter_desc *); extern tree canonicalize_loop_ivs (struct loop *, tree *, bool); +struct phi_affine_iv +{ + gphi *phi; + affine_iv iv; +}; +extern void get_all_phi_affine_ivs (struct loop *, + auto_vec *); +extern tree canonicalize_loop_ivs_1 (struct loop *, tree *, bool, + auto_vec *); #endif /* GCC_TREE_SSA_LOOP_MANIP_H */ --------------467E9F79E204D55094D56ACD--