From patchwork Tue Apr 16 09:55:28 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eric Botcazou X-Patchwork-Id: 236895 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]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client CN "localhost", Issuer "www.qmailtoaster.com" (not verified)) by ozlabs.org (Postfix) with ESMTPS id 1A1D62C00EC for ; Tue, 16 Apr 2013 19:57:42 +1000 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-type:content-transfer-encoding; q=dns; s= default; b=XXmAeMhIwDiPJScKBHpUxTm/SLzo4n4OTnuMv9otHuYyS4Qv8cFXv TtXk84BqGTRaqZskzKhC4IGPXc/A3sW6tGbHmWTRVTQ1J9IJsTq/MeKnp84JG0kw NS2tFhU3sHfAXwk4+K63Q/xn5saSs9r6Wi3DtkdPa51flRiN67UObU= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-type:content-transfer-encoding; s=default; bh=PMaCdU36lIgGswxnfBi5zXScxcU=; b=Ogipokf1nVDhDxYTGEeob8NLcAM5 raoBaKqlIhuwagBKkpqkNGmNyAo6zoasQaN/ii/UePkbxONiltnTdV834foyE/Ex LSMGERRy4BLs4FPiVnuAQYpD1V0HTF2liMoNkZ8uGx7s1M4MlodwckPBYLZ4gavR OqFgqnUg5PfGc6Q= Received: (qmail 2355 invoked by alias); 16 Apr 2013 09:57:36 -0000 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 Received: (qmail 2345 invoked by uid 89); 16 Apr 2013 09:57:36 -0000 X-Spam-SWARE-Status: No, score=-3.0 required=5.0 tests=AWL, BAYES_00, KHOP_THREADED autolearn=ham version=3.3.1 Received: from mel.act-europe.fr (HELO mel.act-europe.fr) (194.98.77.210) by sourceware.org (qpsmtpd/0.84/v0.84-167-ge50287c) with ESMTP; Tue, 16 Apr 2013 09:57:35 +0000 Received: from localhost (localhost [127.0.0.1]) by filtered-smtp.eu.adacore.com (Postfix) with ESMTP id 596A0290110; Tue, 16 Apr 2013 11:57:31 +0200 (CEST) Received: from mel.act-europe.fr ([127.0.0.1]) by localhost (smtp.eu.adacore.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id IEAMLH-UYQz1; Tue, 16 Apr 2013 11:57:31 +0200 (CEST) Received: from polaris.localnet (bon31-6-88-161-99-133.fbx.proxad.net [88.161.99.133]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by mel.act-europe.fr (Postfix) with ESMTP id CC12329004F; Tue, 16 Apr 2013 11:57:30 +0200 (CEST) From: Eric Botcazou To: Richard Biener Cc: gcc-patches@gcc.gnu.org Subject: Re: [patch] Fix ICE during RTL expansion at -O1 Date: Tue, 16 Apr 2013 11:55:28 +0200 Message-ID: <13944748.gGd7vrWRPJ@polaris> User-Agent: KMail/4.7.2 (Linux/3.1.10-1.19-desktop; KDE/4.7.2; x86_64; ; ) In-Reply-To: References: <13643527.5fuA5OUxPv@polaris> <2102577.TzgSJTV924@polaris> MIME-Version: 1.0 X-Virus-Found: No > Note that looking at the access path _is_ assuming TBAA constraints as > soon as the base objects are not the same (in the above case '*p' and 'a' > are not the same and p could alias a in a way that all f1 and f2 overlap). Right, but here I'm assuming (and asserting) that the base objects are the same. > Index: alias.c > =================================================================== > --- alias.c (revision 197926) > +++ alias.c (working copy) > @@ -2232,8 +2232,11 @@ nonoverlapping_component_refs_p (const_r > > found: > /* If we're left with accessing different fields of a structure, then > no - possible overlap, unless they are both bitfields. */ > - if (TREE_CODE (typex) == RECORD_TYPE && fieldx != fieldy) > + possible overlap, unless they are both bitfields. > + ??? Pointer inequality is too fragile in the LTO compiler. */ > + if (TREE_CODE (typex) == RECORD_TYPE > + && fieldx != fieldy > + && DECL_NAME (fieldx) != DECL_NAME (fieldy)) > > this, if at all, should go in with a separate patch and a testcase. > And I think it should _not_ go in. OK, I can remove the LTO related bits. > Otoh... > > + /* ??? We cannot simply use the type of operand #0 of the refs here > + as the Fortran compiler smuggles type punning into COMPONENT_REFs > + for common blocks instead of using unions like everyone else. */ > + tree type1 = TYPE_MAIN_VARIANT (DECL_CONTEXT (field1)); > + tree type2 = TYPE_MAIN_VARIANT (DECL_CONTEXT (field2)); > + > + if (type1 != type2 || TREE_CODE (type1) != RECORD_TYPE) > + goto may_overlap; > + > + /* ??? Pointer inequality is too fragile in the LTO compiler. */ > + if (field1 != field2 && DECL_NAME (field1) != DECL_NAME (field2)) > > this suggests you are seeing multiple FIELD_DECLs for the same field > in the _same_ FIELD_DECL chain ...?! Are you sure this happens with > GCC 4.8? There were some fixes in that area in the LTO type merging code. No, let's drop the LTO related bits for mainline. But the Fortran related bits are necessary, it's the verification you talked about earlier: for a COMPONENT_REF TYPE_MAIN_VARIANT (TREE_TYPE (TREE_OPERAND (t, 0))) = TYPE_MAIN_VARIANT (DECL_CONTEXT (TREE_OPERAND (t, 1))) is expected to be always true (but isn't checked as you pointed out). But the Fortran compiler violates it (4.9, gfortran.dg/aliasing_array_result_1.f90) as it implements a common block by defining 2 RECORD_TYPEs with 1 field, one for each variables, and does an implicit type conversion of TREE_OPERAND (t, 0). > Index: tree-streamer.c > =================================================================== > --- tree-streamer.c (revision 197926) > +++ tree-streamer.c (working copy) > @@ -267,10 +267,9 @@ record_common_node (struct streamer_tree > /* The FIELD_DECLs of structures should be shared, so that every > COMPONENT_REF uses the same tree node when referencing a field. > Pointer equality between FIELD_DECLs is used by the alias > - machinery to compute overlapping memory references (See > - nonoverlapping_component_refs_p). */ > - tree f; > - for (f = TYPE_FIELDS (node); f; f = TREE_CHAIN (f)) > + machinery to compute overlapping component references (see > + nonoverlapping_component_refs_of_decl_p). */ > + for (tree f = TYPE_FIELDS (node); f; f = TREE_CHAIN (f)) > record_common_node (cache, f); > } > } > > without actually removing nonoverlapping_component_refs_p it still applies > to both... Will adjust. > Can you port the non-quadratic algorithm to the RTL > nonoverlapping_component_refs_p first? The core code should exactly > be the same ... (and shared, and only called once from the RTL oracle). No, it cannot be ported, the non-quadratic aspect is a consequence of the same base object assumption. It you don't have it, you need to be quadratic to be able to deal with variable offsets in this way. > I don't understand the "reference several fields" comment. Because I > can clearly have aggregate copies of RECORD_TYPE. Can you try > do elaborate more on why the algorithm should be sufficient to catch > all cases? I can, but you need to keep in mind that the base objects are the same. > You could enhance it to not require > > + /* We must have the same base DECL. */ > + gcc_assert (ref1 == ref2); > > for MEM_REF bases under the same conditions like aliasing_component_refs_p, > that is if the MEM_REF isn't view-converting. The code already handles MEM_REF though (and checks that the offset is zero). I'm not sure that we need more (but ready to be proved wrong here). > That said, if the bases are the same DECLs then indeed you do not > rely on TBAA. The RTL nonoverlapping_component_refs_p does not > disable itself properly for pointer based accesses that might be > view-converted / aliased accesses (a simple testcase with ref-all > pointers properly offsetted to alias two adjacent fields may be enough to > show that). > > Also with your patch enhanced like I suggest we should be able to > remove aliasing_component_refs_p as well, no? My revised patch is only a safe, non-quadratic, non-TBAA based disambiguation for references based on the same DECL, so it's a full replacement neither for aliasing_component_refs_p nor for nonoverlapping_component_refs_p. Thanks for the review. Updated patch attached. * tree-ssa-alias.c (nonoverlapping_component_refs_of_decl_p): New. (decl_refs_may_alias_p): Add REF1 and REF2 parameters. Use nonoverlapping_component_refs_of_decl_p to disambiguate component references. (refs_may_alias_p_1): Adjust call to decl_refs_may_alias_p. * tree-streamer.c (record_common_node): Adjust reference in comment. Index: tree-ssa-alias.c =================================================================== --- tree-ssa-alias.c (revision 197926) +++ tree-ssa-alias.c (working copy) @@ -719,14 +719,112 @@ aliasing_component_refs_p (tree ref1, return false; } +/* Return true if we can determine that component references REF1 and REF2, + that are within a common DECL, cannot overlap. */ + +static bool +nonoverlapping_component_refs_of_decl_p (tree ref1, tree ref2) +{ + vec component_refs1; + vec component_refs2; + + vec_stack_alloc (tree, component_refs1, 16); + vec_stack_alloc (tree, component_refs2, 16); + + /* Create the stack of handled components for REF1. */ + while (handled_component_p (ref1)) + { + component_refs1.safe_push (ref1); + ref1 = TREE_OPERAND (ref1, 0); + } + if (TREE_CODE (ref1) == MEM_REF) + { + if (!integer_zerop (TREE_OPERAND (ref1, 1))) + goto may_overlap; + ref1 = TREE_OPERAND (TREE_OPERAND (ref1, 0), 0); + } + + /* Create the stack of handled components for REF2. */ + while (handled_component_p (ref2)) + { + component_refs2.safe_push (ref2); + ref2 = TREE_OPERAND (ref2, 0); + } + if (TREE_CODE (ref2) == MEM_REF) + { + if (!integer_zerop (TREE_OPERAND (ref2, 1))) + goto may_overlap; + ref2 = TREE_OPERAND (TREE_OPERAND (ref2, 0), 0); + } + + /* We must have the same base DECL. */ + gcc_assert (ref1 == ref2); + + /* Pop the stacks in parallel and examine the COMPONENT_REFs of the same + rank. This is sufficient because we start from the same DECL and you + cannot reference several fields at a time with COMPONENT_REFs (unlike + with ARRAY_RANGE_REFs for arrays) so you always need the same number + of them to access a sub-component, unless you're in a union, in which + case the return value will precisely be false. */ + while (true) + { + do + { + if (component_refs1.is_empty ()) + goto may_overlap; + ref1 = component_refs1.pop (); + } + while (!RECORD_OR_UNION_TYPE_P (TREE_TYPE (TREE_OPERAND (ref1, 0)))); + + do + { + if (component_refs2.is_empty ()) + goto may_overlap; + ref2 = component_refs2.pop (); + } + while (!RECORD_OR_UNION_TYPE_P (TREE_TYPE (TREE_OPERAND (ref2, 0)))); + + /* Beware of BIT_FIELD_REF. */ + if (TREE_CODE (ref1) != COMPONENT_REF + || TREE_CODE (ref2) != COMPONENT_REF) + goto may_overlap; + + tree field1 = TREE_OPERAND (ref1, 1); + tree field2 = TREE_OPERAND (ref2, 1); + + /* ??? We cannot simply use the type of operand #0 of the refs here + as the Fortran compiler smuggles type punning into COMPONENT_REFs + for common blocks instead of using unions like everyone else. */ + tree type1 = TYPE_MAIN_VARIANT (DECL_CONTEXT (field1)); + tree type2 = TYPE_MAIN_VARIANT (DECL_CONTEXT (field2)); + + if (type1 != type2 || TREE_CODE (type1) != RECORD_TYPE) + goto may_overlap; + + /* Different fields of the same RECORD_TYPE cannot overlap. */ + if (field1 != field2) + { + component_refs1.release (); + component_refs2.release (); + return true; + } + } + +may_overlap: + component_refs1.release (); + component_refs2.release (); + return false; +} + /* Return true if two memory references based on the variables BASE1 and BASE2 constrained to [OFFSET1, OFFSET1 + MAX_SIZE1) and - [OFFSET2, OFFSET2 + MAX_SIZE2) may alias. */ + [OFFSET2, OFFSET2 + MAX_SIZE2) may alias. REF1 and REF2 + if non-NULL are the complete memory reference trees. */ static bool -decl_refs_may_alias_p (tree base1, +decl_refs_may_alias_p (tree ref1, tree base1, HOST_WIDE_INT offset1, HOST_WIDE_INT max_size1, - tree base2, + tree ref2, tree base2, HOST_WIDE_INT offset2, HOST_WIDE_INT max_size2) { gcc_checking_assert (DECL_P (base1) && DECL_P (base2)); @@ -737,7 +835,17 @@ decl_refs_may_alias_p (tree base1, /* If both references are based on the same variable, they cannot alias if the accesses do not overlap. */ - return ranges_overlap_p (offset1, max_size1, offset2, max_size2); + if (!ranges_overlap_p (offset1, max_size1, offset2, max_size2)) + return false; + + /* For components with variable position, the above test isn't sufficient, + so we disambiguate component references manually. */ + if (ref1 && ref2 + && handled_component_p (ref1) && handled_component_p (ref2) + && nonoverlapping_component_refs_of_decl_p (ref1, ref2)) + return false; + + return true; } /* Return true if an indirect reference based on *PTR1 constrained @@ -1086,8 +1194,8 @@ refs_may_alias_p_1 (ao_ref *ref1, ao_ref var1_p = DECL_P (base1); var2_p = DECL_P (base2); if (var1_p && var2_p) - return decl_refs_may_alias_p (base1, offset1, max_size1, - base2, offset2, max_size2); + return decl_refs_may_alias_p (ref1->ref, base1, offset1, max_size1, + ref2->ref, base2, offset2, max_size2); ind1_p = (TREE_CODE (base1) == MEM_REF || TREE_CODE (base1) == TARGET_MEM_REF); Index: tree-streamer.c =================================================================== --- tree-streamer.c (revision 197926) +++ tree-streamer.c (working copy) @@ -267,10 +267,10 @@ record_common_node (struct streamer_tree /* The FIELD_DECLs of structures should be shared, so that every COMPONENT_REF uses the same tree node when referencing a field. Pointer equality between FIELD_DECLs is used by the alias - machinery to compute overlapping memory references (See - nonoverlapping_component_refs_p). */ - tree f; - for (f = TYPE_FIELDS (node); f; f = TREE_CHAIN (f)) + machinery to compute overlapping component references (see + nonoverlapping_component_refs_p and + nonoverlapping_component_refs_of_decl_p). */ + for (tree f = TYPE_FIELDS (node); f; f = TREE_CHAIN (f)) record_common_node (cache, f); } }