From patchwork Fri Feb 17 04:01:36 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexandre Oliva X-Patchwork-Id: 141729 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 65039B6FCB for ; Fri, 17 Feb 2012 15:02:13 +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=1330056137; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Received: Received:Received:Received:From:To:Cc:Subject:References:Date: In-Reply-To:Message-ID:User-Agent:MIME-Version:Content-Type: Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:Sender:Delivered-To; bh=yr0+3vxx0pOXD06ULfJ+ oXpP+gY=; b=WHHObXvzOiREN5F4C5HYeWTx75qLlHuisUSIdRZ8wE9MaTsuKKfP P2pAS8GEky0rMvfuLbYbMROwxFgJlOnKLRtDCecpa+rxsUOhaH9a/if7ENPDgloZ FCLX0v5tHIvYyAEebIK6icrB4b2sHXzSdy4wqPcqOeicRuCkl1UM8Ic= 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:Received:Received:Received:Received:From:To:Cc:Subject:References:Date:In-Reply-To:Message-ID:User-Agent:MIME-Version:Content-Type:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=g9YqC0cMiLof84tJ1rKvYwFOiv/0K08kJblmW8vCBrjwSzkOiH21Ys65w45HOS j6JLv/L6N74hmaCmrIPa6kCHi47wv9j/9tVSqjmhCLvuJBbIBD0U+i71lAsOl8HN cPyrG+isADFd30ncZNIuhT3csTWvWP2cQ9ti7d/V4iDKQ=; Received: (qmail 18700 invoked by alias); 17 Feb 2012 04:02:08 -0000 Received: (qmail 18691 invoked by uid 22791); 17 Feb 2012 04:02:06 -0000 X-SWARE-Spam-Status: No, hits=-5.9 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_HI, SPF_HELO_PASS, T_RP_MATCHES_RCVD, T_TVD_MIME_NO_HEADERS X-Spam-Check-By: sourceware.org Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Fri, 17 Feb 2012 04:01:49 +0000 Received: from int-mx09.intmail.prod.int.phx2.redhat.com (int-mx09.intmail.prod.int.phx2.redhat.com [10.5.11.22]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id q1H41m7R007492 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Thu, 16 Feb 2012 23:01:49 -0500 Received: from freie.oliva.athome.lsd.ic.unicamp.br (ovpn01.gateway.prod.ext.phx2.redhat.com [10.5.9.1]) by int-mx09.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id q1H41kPJ003716 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Thu, 16 Feb 2012 23:01:48 -0500 Received: from livre.localdomain (livre-to-gw.oliva.athome.lsd.ic.unicamp.br [172.31.160.19]) by freie.oliva.athome.lsd.ic.unicamp.br (8.14.5/8.14.5) with ESMTP id q1H41c7p012847; Fri, 17 Feb 2012 02:01:38 -0200 Received: from livre.localdomain (aoliva@localhost.localdomain [127.0.0.1]) by livre.localdomain (8.14.3/8.14.3/Debian-5+lenny1) with ESMTP id q1H41bbG014445; Fri, 17 Feb 2012 02:01:37 -0200 Received: (from aoliva@localhost) by livre.localdomain (8.14.3/8.14.3/Submit) id q1H41apB014443; Fri, 17 Feb 2012 02:01:36 -0200 From: Alexandre Oliva To: gcc-patches@gcc.gnu.org Cc: jakub@redhat.com, rdsandiford@googlemail.com Subject: Re: [PR52001] too many cse reverse equiv exprs (take2) References: <87sjiejwmc.fsf@talisman.home> <87lio32a2l.fsf@talisman.home> Date: Fri, 17 Feb 2012 02:01:36 -0200 In-Reply-To: <87lio32a2l.fsf@talisman.home> (Richard Sandiford's message of "Wed, 15 Feb 2012 19:03:30 +0000") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.1 (gnu/linux) MIME-Version: 1.0 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 On Feb 15, 2012, Richard Sandiford wrote: > I'm fine with putting it in and seeing what breaks. But I'd really > prefer if we knew in theory. :-) Ok, I dove into the problem without a testcase, and I managed to trigger it on other platforms after tweaking get_addr a bit so as use loc lists form canonical values, and to avoid returning other VALUEs if other alternatives exist. > Like I say, my understanding before this patch series went in was that > cselib values weren't supposed to be cyclic. Now that they are, what > should consumers like memrefs_conflict_p do to avoid getting stuck? I'm now testing the following heuristic: only use an expr instead of a value if the expr doesn't reference any value whose uid is greater than that of the value. This worked for libgcc so far; regstrapping now. Here's the revised patch that addresses Jakub's and your comments, that regstrapped on x86_64-linux-gnu and i686-linux-gnu, followed by the patch I'm testing now on both platforms. for gcc/ChangeLog from Alexandre Oliva PR debug/52001 * alias.c (refs_newer_value_cb, refs_newer_value_p): New. (get_addr): Walk canonical value's locs. Avoid returning VALUEs and locs that reference values newer than the non-canonical value at hand. Return the canonical value as a worst case. (memrefs_conflict_p): Walk canonical value's locs. Index: gcc/alias.c =================================================================== --- gcc/alias.c.orig 2012-02-17 01:14:43.734347934 -0200 +++ gcc/alias.c 2012-02-17 01:47:33.506632170 -0200 @@ -1773,6 +1773,29 @@ base_alias_check (rtx x, rtx y, enum mac return 1; } +/* Callback for for_each_rtx, that returns 1 upon encountering a VALUE + whose UID is greater than the int uid that D points to. */ + +static int +refs_newer_value_cb (rtx *x, void *d) +{ + if (GET_CODE (*x) == VALUE && CSELIB_VAL_PTR (*x)->uid > *(int *)d) + return 1; + + return 0; +} + +/* Return TRUE if EXPR refers to a VALUE whose uid is greater than + that of V. */ + +static bool +refs_newer_value_p (rtx expr, rtx v) +{ + int minuid = CSELIB_VAL_PTR (v)->uid; + + return for_each_rtx (&expr, refs_newer_value_cb, &minuid); +} + /* Convert the address X into something we can use. This is done by returning it unchanged unless it is a value; in the latter case we call cselib to get a more useful rtx. */ @@ -1788,14 +1811,20 @@ get_addr (rtx x) v = CSELIB_VAL_PTR (x); if (v) { + v = canonical_cselib_val (v); for (l = v->locs; l; l = l->next) if (CONSTANT_P (l->loc)) return l->loc; for (l = v->locs; l; l = l->next) - if (!REG_P (l->loc) && !MEM_P (l->loc)) + if (!REG_P (l->loc) && !MEM_P (l->loc) && GET_CODE (l->loc) != VALUE + && !refs_newer_value_p (l->loc, x)) + return l->loc; + for (l = v->locs; l; l = l->next) + if (REG_P (l->loc) || (GET_CODE (l->loc) != VALUE + && !refs_newer_value_p (l->loc, x))) return l->loc; - if (v->locs) - return v->locs->loc; + /* Return the canonical value. */ + return v->val_rtx; } return x; } @@ -1873,7 +1902,8 @@ memrefs_conflict_p (int xsize, rtx x, in { struct elt_loc_list *l = NULL; if (CSELIB_VAL_PTR (x)) - for (l = CSELIB_VAL_PTR (x)->locs; l; l = l->next) + for (l = canonical_cselib_val (CSELIB_VAL_PTR (x))->locs; + l; l = l->next) if (REG_P (l->loc) && rtx_equal_for_memref_p (l->loc, y)) break; if (l) @@ -1891,7 +1921,8 @@ memrefs_conflict_p (int xsize, rtx x, in { struct elt_loc_list *l = NULL; if (CSELIB_VAL_PTR (y)) - for (l = CSELIB_VAL_PTR (y)->locs; l; l = l->next) + for (l = canonical_cselib_val (CSELIB_VAL_PTR (y))->locs; + l; l = l->next) if (REG_P (l->loc) && rtx_equal_for_memref_p (l->loc, x)) break; if (l)