From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 115678 invoked by alias); 15 Jan 2016 13:58:55 -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 115667 invoked by uid 89); 15 Jan 2016 13:58:54 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.0 required=5.0 tests=AWL,BAYES_00,RP_MATCHES_RCVD,SPF_PASS autolearn=ham version=3.3.2 spammy=3317, manages, 331,7, HX-detected-operating-system:Windows X-HELO: fencepost.gnu.org Received: from fencepost.gnu.org (HELO fencepost.gnu.org) (208.118.235.10) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Fri, 15 Jan 2016 13:58:52 +0000 Received: from eggs.gnu.org ([2001:4830:134:3::10]:48913) by fencepost.gnu.org with esmtps (TLS1.0:RSA_AES_256_CBC_SHA1:256) (Exim 4.82) (envelope-from ) id 1aK4tu-00037v-8y for gcc-patches@gnu.org; Fri, 15 Jan 2016 08:58:50 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1aK4tq-0002YB-L6 for gcc-patches@gnu.org; Fri, 15 Jan 2016 08:58:49 -0500 Received: from relay1.mentorg.com ([192.94.38.131]:40572) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1aK4tq-0002Xy-Ba for gcc-patches@gnu.org; Fri, 15 Jan 2016 08:58:46 -0500 Received: from nat-ies.mentorg.com ([192.94.31.2] helo=SVR-IES-FEM-01.mgc.mentorg.com) by relay1.mentorg.com with esmtp id 1aK4tn-0003QB-UQ from Tom_deVries@mentor.com ; Fri, 15 Jan 2016 05:58:44 -0800 Received: from [127.0.0.1] (137.202.0.76) by SVR-IES-FEM-01.mgc.mentorg.com (137.202.0.104) with Microsoft SMTP Server id 14.3.224.2; Fri, 15 Jan 2016 13:58:42 +0000 To: Sebastian Pop , CC: "gcc-patches@gnu.org" From: Tom de Vries Subject: [PATCH, PR68976] Use reaching def phi arg in sese_add_exit_phis_edge Message-ID: <5698FB0F.3090908@mentor.com> Date: Fri, 15 Jan 2016 13:58:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.4.0 MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------------040400020609010303020409" X-detected-operating-system: by eggs.gnu.org: Windows NT kernel [generic] [fuzzy] X-Received-From: 192.94.38.131 X-SW-Source: 2016-01/txt/msg01067.txt.bz2 --------------040400020609010303020409 Content-Type: text/plain; charset="utf-8"; format=flowed Content-Transfer-Encoding: 8bit Content-length: 4313 Hi, Consider testcase test.c: ... int kw = -1, hv = -1, ju; int mc[1]; void foo (void) { for (; kw; ++kw) for (; hv; ++hv) for (ju = 0; ju < 2; ++ju) mc[kw+1] = mc[0]; } ... When compiled with -O2 -fgraphite-identity, we run into an ICE: ... test.c: In function ‘foo’: test.c:5:1: internal compiler error: Segmentation fault foo (void) ^~~ 0xefb0cc crash_signal src/gcc/toplev.c:334 0xf62761 ssa_default_def(function*, tree_node*) src/gcc/tree-dfa.c:305 0xf62b08 get_or_create_ssa_default_def(function*, tree_node*) src/gcc/tree-dfa.c:357 0xfa9a21 get_reaching_def src/gcc/tree-into-ssa.c:1168 0xfab8b4 rewrite_update_phi_arguments src/gcc/tree-into-ssa.c:2017 0xfabd49 rewrite_update_dom_walker::before_dom_children(basic_block_def*) src/gcc/tree-into-ssa.c:2137 0x1c3a9a0 dom_walker::walk(basic_block_def*) src/gcc/domwalk.c:265 0xfabe35 rewrite_blocks src/gcc/tree-into-ssa.c:2194 0xfaeb45 update_ssa(unsigned int) src/gcc/tree-into-ssa.c:3356 0x1c75308 graphite_regenerate_ast_isl(scop*) src/gcc/graphite-isl-ast-to-gimple.c:3319 0x1c6c572 graphite_transform_loops() src/gcc/graphite.c:329 0x1c6c5f6 graphite_transforms src/gcc/graphite.c:356 0x1c6c719 execute src/gcc/graphite.c:433 Please submit a full bug report, with preprocessed source if appropriate. Please include the complete backtrace with any bug report. See for instructions. ... The scenario leading up to the ICE is as follows: Before scop detection, we have bb 16, jumping to either bb 17 or bb 18, in which _6 and _24 are defined: ... : ... if (hv_lsm.8_23 != 0) goto ; else goto ; : _6 = kw.0_30 + 1; goto ; : _24 = kw.0_30 + 1; goto ; ... And bb 8, were we join _6 and _24 in a phi: ... : # prephitmp_7 = PHI <_24(7), _6(17)> ... ... BB 18 is a preheader block for a loop with exit edge bb 7 -> bb 8. During scop detection/canonicalize_loop_closed_ssa_form, an exit phi is introduced in the loop for _24: ... : # _58 = PHI <_24(22)> ... Note that _24 is not defined in the loop, but before it. AFAIU the header comment of canonicalize_loop_closed_ssa_form, this phi is not needed. That might be the root cause of the bug, but I'm not sure, so I proceed here assuming that's not the case. After the introduction of the exit phi, the join phi looks like: ... : # prephitmp_7 = PHI <_58(21), _6(17)> ... After scop detection, we enter graphite_regenerate_ast_isl with region: ... (gdb) p region.region.entry.src.index $2 = 18 (gdb) p region.region.entry.dest.index $3 = 4 (gdb) p region.region.exit.src.index $4 = 21 (gdb) p region.region.exit.dest.index $5 = 8 ... In other words, the loop with header block 4 + loop exit block 21. In graphite_regenerate_ast_isl, we move the region into a condition: ... if (1) A; /* generate graphite code here. */ else REGION; ... Consequently, the def _58 (defined in the region) no longer dominates the use in the join phi. An empty condition join block is introduced: ... : ... And in sese_insert_phis_for_liveouts, we introduce a new phi, to join the values of both side of the condition: ... : # _22 = PHI <_58(28), _58(21)> ... An ssa rename mapping is introduced from _58 to _22, such that once we do update_ssa, the join phi in bb 8 will use _22 instead of _58. For the new phi in bb 25, the phi edge coming from region has the def in the region dominating the use in the phi. For the other edge (coming from A), that's not the case. That does not necessary result in an ICE. Usually, there's a region rename (with corresponding rename in the ssa name mapping) registered that gives the corresponding value in A, and update_ssa manages to fill in the correct values. In the case of this PR, there's no such rename, we run into the ICE. The patch fixes the PR detecting the case that there's no rename scheduled, and walking single-arg phis until we find a def that dominates the use in the phi (in the case of this test-case it's the def of _24). [ I'm not sure this the right fix in the right place though. ] Bootstrapped and reg-tested on x86_64. OK for trunk? Thanks, - Tom --------------040400020609010303020409 Content-Type: text/x-patch; name="0001-Use-reaching-def-phi-arg-in-sese_add_exit_phis_edge.patch" Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename*0="0001-Use-reaching-def-phi-arg-in-sese_add_exit_phis_edge.pat"; filename*1="ch" Content-length: 2947 Use reaching def phi arg in sese_add_exit_phis_edge 2016-01-15 Tom de Vries PR tree-optimization/68976 * sese.c (sese_add_exit_phis_edge): Find phi arg for true_edge with reaching def, if not renamed. (sese_insert_phis_for_liveouts): Call sese_add_exit_phis_edge with extra arg. --- gcc/sese.c | 34 +++++++++++++++++++++++++++++---- gcc/testsuite/gcc.dg/graphite/pr68976.c | 13 +++++++++++++ 2 files changed, 43 insertions(+), 4 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/graphite/pr68976.c diff --git a/gcc/sese.c b/gcc/sese.c index 59d2770..27287e9 100644 --- a/gcc/sese.c +++ b/gcc/sese.c @@ -270,15 +270,41 @@ free_sese_info (sese_info_p region) XDELETE (region); } -/* Add exit phis for USE on EXIT. */ +/* Add exit phis for USE on EXIT in REGION. */ static void -sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e) +sese_add_exit_phis_edge (sese_info_p region, basic_block exit, tree use, + edge false_e, edge true_e) { gphi *phi = create_phi_node (NULL_TREE, exit); create_new_def_for (use, phi, gimple_phi_result_ptr (phi)); add_phi_arg (phi, use, false_e, UNKNOWN_LOCATION); - add_phi_arg (phi, use, true_e, UNKNOWN_LOCATION); + + vec *renames = region->rename_map->get (use); + bool use_renamed = renames && !renames->is_empty (); + + if (use_renamed) + add_phi_arg (phi, use, true_e, UNKNOWN_LOCATION); + else + { + /* Handle the case that use is defined by a PHI, which is just a copy, and + the src of the copy can be used as argument for true_e. */ + tree arg = use; + while (true) + { + if (TREE_CODE (arg) != SSA_NAME) + break; + if (dominated_by_p (CDI_DOMINATORS, true_e->src, + gimple_bb (SSA_NAME_DEF_STMT (arg)))) + break; + gcc_assert (gimple_code (SSA_NAME_DEF_STMT (arg)) == GIMPLE_PHI); + gphi *use_def = as_a (SSA_NAME_DEF_STMT (arg)); + gcc_assert (gimple_phi_num_args (use_def) == 1); + arg = gimple_phi_arg_def (use_def, 0); + } + add_phi_arg (phi, arg, true_e, UNKNOWN_LOCATION); + } + update_stmt (phi); } @@ -305,7 +331,7 @@ sese_insert_phis_for_liveouts (sese_info_p region, basic_block bb, EXECUTE_IF_SET_IN_BITMAP (liveouts, 0, i, bi) if (!virtual_operand_p (ssa_name (i))) - sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e); + sese_add_exit_phis_edge (region, bb, ssa_name (i), false_e, true_e); BITMAP_FREE (liveouts); } diff --git a/gcc/testsuite/gcc.dg/graphite/pr68976.c b/gcc/testsuite/gcc.dg/graphite/pr68976.c new file mode 100644 index 0000000..165a740 --- /dev/null +++ b/gcc/testsuite/gcc.dg/graphite/pr68976.c @@ -0,0 +1,13 @@ +/* { dg-options "-O2 -fgraphite-identity" } */ + +int kw = -1, hv = -1, ju; +int mc[1]; + +void +foo (void) +{ + for (; kw; ++kw) + for (; hv; ++hv) + for (ju = 0; ju < 2; ++ju) + mc[kw+1] = mc[0]; +} -- 1.9.1 --------------040400020609010303020409--