From patchwork Mon Feb 13 14:27:35 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexandre Oliva X-Patchwork-Id: 140910 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 CDC661007D1 for ; Tue, 14 Feb 2012 01:28:09 +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=1329748091; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Received: Received:Received:Received:From:To:Cc:Subject:Date: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=a5fasIquE7WLQI5uC59AuPmMmcU=; b=iEpOo4xxtDsdou+ UInR8tn+80WBox8UBVZ7FRdR/nhKag37OsIK8dzXgS/iByGIV1aSsRGlKnBLctnx SmVoRhdKXkVsak0io5FDQ9W0gGL9WvTGmCvnHdmmjrmfzSMhh0hoQ6GwwqbixVuA MN++4I52UpvIvHx8CvozfCMkIFqE= 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:Date: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=HbWfYT5yvy3Eyh6CxuzvsoiUhgUVHR/XNump/qZCuMAvAXtLUbcBjcPMWtUg9a X63WGLnxZkQNIy5LL1ocO1JcAAbkrv4wlVcfIiIkkTFAb5/bij7B5kOLbfkwJAst YehtL+aAGCxNsiFji1A5wtfmfkuHli7Kr/38wXKooCOVo=; Received: (qmail 2859 invoked by alias); 13 Feb 2012 14:28:05 -0000 Received: (qmail 2844 invoked by uid 22791); 13 Feb 2012 14:28:04 -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; Mon, 13 Feb 2012 14:27:47 +0000 Received: from int-mx12.intmail.prod.int.phx2.redhat.com (int-mx12.intmail.prod.int.phx2.redhat.com [10.5.11.25]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id q1DERkRE003630 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Mon, 13 Feb 2012 09:27:46 -0500 Received: from freie.oliva.athome.lsd.ic.unicamp.br (ovpn01.gateway.prod.ext.phx2.redhat.com [10.5.9.1]) by int-mx12.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id q1DERiGt012759 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Mon, 13 Feb 2012 09:27:46 -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 q1DERb8F020050; Mon, 13 Feb 2012 12:27:37 -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 q1DERav1004299; Mon, 13 Feb 2012 12:27:36 -0200 Received: (from aoliva@localhost) by livre.localdomain (8.14.3/8.14.3/Submit) id q1DERZn1004297; Mon, 13 Feb 2012 12:27:35 -0200 From: Alexandre Oliva To: gcc-patches@gcc.gnu.org Cc: jakub@redhat.com, rdsandiford@googlemail.com Subject: [PR52001] too many cse reverse equiv exprs (take2) Date: Mon, 13 Feb 2012 12:27:35 -0200 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 Jakub asked to have a closer look at the problem, and I found we could do somewhat better. The first thing I noticed was that the problem was that, in each block that computed a (base+const), we created a new VALUE for the expression (with the same const and global base), and a new reverse operation. This was wrong. Clearly we should reuse the same expression. I had to arrange for the expression to be retained across basic blocks, for it was function invariant. I split out the code to detect invariants from the function that removes entries from the cselib hash table across blocks, and made it recursive so that a VALUE equivalent to (plus (value) (const_int)) will be retained, if the base value fits (maybe recursively) the definition of invariant. An earlier attempt to address this issue remained in cselib: using the canonical value to build the reverse expression. I believe it has a potential of avoiding the creation of redundant reverse expressions, for expressions involving equivalent but different VALUEs will evaluate to different hashes. I haven't observed effects WRT the given testcase, before or after the change that actually fixed the problem, because we now find the same base expression and thus reuse the reverse_op as well, but I figured I'd keep it in for it is very cheap and possibly useful. Regstrapped on x86_64-linux-gnu and i686-pc-linux-gnu. Ok to install? for gcc/ChangeLog from Alexandre Oliva PR debug/52001 * cselib.c (invariant_p): Split out of... (preserve_only_constants): ... this. Preserve plus expressions of invariant values and constants. * var-tracking.c (reverse_op): Don't drop equivs of constants. Use canonical value to build reverse operation. Index: gcc/cselib.c =================================================================== --- gcc/cselib.c.orig 2012-02-12 06:13:40.676385499 -0200 +++ gcc/cselib.c 2012-02-12 09:07:00.653579375 -0200 @@ -383,22 +383,29 @@ cselib_clear_table (void) cselib_reset_table (1); } -/* Remove from hash table all VALUEs except constants - and function invariants. */ +/* Return TRUE if V is a constant or a function invariant, FALSE + otherwise. */ -static int -preserve_only_constants (void **x, void *info ATTRIBUTE_UNUSED) +static bool +invariant_p (cselib_val *v) { - cselib_val *v = (cselib_val *)*x; struct elt_loc_list *l; + if (v == cfa_base_preserved_val) + return true; + + /* Keep VALUE equivalences around. */ + for (l = v->locs; l; l = l->next) + if (GET_CODE (l->loc) == VALUE) + return true; + if (v->locs != NULL && v->locs->next == NULL) { if (CONSTANT_P (v->locs->loc) && (GET_CODE (v->locs->loc) != CONST || !references_value_p (v->locs->loc, 0))) - return 1; + return true; /* Although a debug expr may be bound to different expressions, we can preserve it as if it was constant, to get unification and proper merging within var-tracking. */ @@ -406,24 +413,29 @@ preserve_only_constants (void **x, void || GET_CODE (v->locs->loc) == DEBUG_IMPLICIT_PTR || GET_CODE (v->locs->loc) == ENTRY_VALUE || GET_CODE (v->locs->loc) == DEBUG_PARAMETER_REF) - return 1; - if (cfa_base_preserved_val) - { - if (v == cfa_base_preserved_val) - return 1; - if (GET_CODE (v->locs->loc) == PLUS - && CONST_INT_P (XEXP (v->locs->loc, 1)) - && XEXP (v->locs->loc, 0) == cfa_base_preserved_val->val_rtx) - return 1; - } + return true; + + /* (plus (value V) (const_int C)) is invariant iff V is invariant. */ + if (GET_CODE (v->locs->loc) == PLUS + && CONST_INT_P (XEXP (v->locs->loc, 1)) + && GET_CODE (XEXP (v->locs->loc, 0)) == VALUE + && invariant_p (CSELIB_VAL_PTR (XEXP (v->locs->loc, 0)))) + return true; } - /* Keep VALUE equivalences around. */ - for (l = v->locs; l; l = l->next) - if (GET_CODE (l->loc) == VALUE) - return 1; + return false; +} + +/* Remove from hash table all VALUEs except constants + and function invariants. */ + +static int +preserve_only_constants (void **x, void *info ATTRIBUTE_UNUSED) +{ + cselib_val *v = (cselib_val *)*x; - htab_clear_slot (cselib_hash_table, x); + if (!invariant_p (v)) + htab_clear_slot (cselib_hash_table, x); return 1; } Index: gcc/var-tracking.c =================================================================== --- gcc/var-tracking.c.orig 2012-02-12 06:13:38.633412886 -0200 +++ gcc/var-tracking.c 2012-02-12 10:09:49.000000000 -0200 @@ -5298,7 +5298,6 @@ reverse_op (rtx val, const_rtx expr, rtx { rtx src, arg, ret; cselib_val *v; - struct elt_loc_list *l; enum rtx_code code; if (GET_CODE (expr) != SET) @@ -5334,13 +5333,9 @@ reverse_op (rtx val, const_rtx expr, rtx if (!v || !cselib_preserved_value_p (v)) return; - /* Adding a reverse op isn't useful if V already has an always valid - location. Ignore ENTRY_VALUE, while it is always constant, we should - prefer non-ENTRY_VALUE locations whenever possible. */ - for (l = v->locs; l; l = l->next) - if (CONSTANT_P (l->loc) - && (GET_CODE (l->loc) != CONST || !references_value_p (l->loc, 0))) - return; + /* Use canonical V to avoid creating multiple redundant expressions + for different VALUES equivalent to V. */ + v = canonical_cselib_val (v); switch (GET_CODE (src)) {