From patchwork Sun Apr 14 07:46:14 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eric Botcazou X-Patchwork-Id: 236410 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 633662C00A2 for ; Sun, 14 Apr 2013 17:48:04 +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=kHJ7+NSdeqLNH/5orrC76Odv+ok2lL1dAuvqvWCQjtfJ2sTg92Hql sT+K+VSRsPG2Rjo7msiQ7qwSOZ0xtgaHLYCj/9NJ0TMyNJ3CPo3UHRWHlfkB6e2B eNBPZAmY1/Cwpj9EZe+w+Rd+rXrD3ifiqoOPPL59TPP3V3Ru8GRxVo= 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=4WVRMBGmwfq3IZ/YH1YLwbQ6zHM=; b=wTdczf0V9G1dXUt/P5KTkpaDi8U/ ym9+H5XY0vy1VhchS1E917Y+f0mhDBXZ//6xaGtkSBn8p6Hbu7xHBG7NkGKp0t0S zwsrKUZuz+/KCnGPrSULn6XkuzG0Eb9difyNV8H8wRparZJ/oSwAeZ9C2Abp7ADM oLhLHtovlvmniaQ= Received: (qmail 19269 invoked by alias); 14 Apr 2013 07:47:56 -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 19244 invoked by uid 89); 14 Apr 2013 07:47:55 -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; Sun, 14 Apr 2013 07:47:53 +0000 Received: from localhost (localhost [127.0.0.1]) by filtered-smtp.eu.adacore.com (Postfix) with ESMTP id 92544290016; Sun, 14 Apr 2013 09:47:50 +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 D0pPgSYtroeC; Sun, 14 Apr 2013 09:47:50 +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 2DE2129000E; Sun, 14 Apr 2013 09:47:50 +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: Sun, 14 Apr 2013 09:46:14 +0200 Message-ID: <2102577.TzgSJTV924@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> MIME-Version: 1.0 X-Virus-Found: No > This is a quadratic algorithm and as such not ok. We already have > aliasing_component_refs_p in tree-ssa-alias.c which is supposed to be > the non-quadratic replacement. It's not used via decl_refs_may_alias_p, > so that may be the thing to fix. aliasing_component_refs_p isn't powerful enough, it eliminates the quadratic aspect by assuming that all offsets are constants, so it misses cases like (*p)[i].f1 vs a[j].f2. Moreover it assumes TBAA and we don't need it here. I can rewrite nonoverlapping_component_refs_of_decl_p to make it non-quadratic and catch the same cases I think, patch attached (without the vect testsuite adjustments, but they are still needed). > nonoverlapping_component_refs_of_decl_p on RTL should go - in fact > we do call the tree oracle from all its callers so we only ever do redundant > work (after your proposed patch even more so). Not clear if the tree oracle can catch the above case with *p and a, but, yes, nonoverlapping_component_refs_p should go in the long term. * alias.c (nonoverlapping_component_refs_p): Protect again LTO quirk. * 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: 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)) return !(DECL_BIT_FIELD (fieldx) && DECL_BIT_FIELD (fieldy)); /* The comparison on the current field failed. If we're accessing Index: tree-ssa-alias.c =================================================================== --- tree-ssa-alias.c (revision 197926) +++ tree-ssa-alias.c (working copy) @@ -719,14 +719,110 @@ 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 you cannot reference several fields + at a time (unlike for arrays with slices), unless you're in a union, + in which case the return value will be false in any case. */ + 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; + + /* ??? Pointer inequality is too fragile in the LTO compiler. */ + if (field1 != field2 && DECL_NAME (field1) != DECL_NAME (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 +833,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 +1192,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,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); } }