From patchwork Mon Apr 9 05:50:02 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexandre Oliva X-Patchwork-Id: 151401 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 7779CB703B for ; Mon, 9 Apr 2012 15:50:37 +1000 (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=1334555438; 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=rUrlkwrD2TUwm6JCgquWvvoPnJk=; b=fXaWswdbMvU0zrn B4QJYus29ban1dx/Q59raMnYSn3HpTNOJtKVEv1lgzCfa8uw/OKz2ktI1ii3LIRB 4pODyZt6mQqIcweT41JmkFKmGj7har7UqiFVImQPFPWQnkwPWaeykCCuIbBTCE1k escIacP2ByAAO8SZ0u9RHfyuY5Y0= 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=oNbOBzED3HKaDRyUopBj3AJXd0ly72iUc8h0nLlNCWpz+i3t3ImoWvKnbWMT5m 7GxHeINtPM7JWGxDwHaNGpmW6x8of+vjAGHL7zCquhdqnF08PM5KWJIuAmpcTHHh xAMaU16ur9TFd9WDGlwN3u6t4QAnyHsYDa6l3ycH3Gu6U=; Received: (qmail 16142 invoked by alias); 9 Apr 2012 05:50:31 -0000 Received: (qmail 16132 invoked by uid 22791); 9 Apr 2012 05:50:29 -0000 X-SWARE-Spam-Status: No, hits=-5.4 required=5.0 tests=AWL, BAYES_00, KHOP_RCVD_UNTRUST, 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, 09 Apr 2012 05:50:10 +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 q395o8Uq021136 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK) for ; Mon, 9 Apr 2012 01:50:09 -0400 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 q395o6uC013142 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Mon, 9 Apr 2012 01:50:07 -0400 Received: from livre.localdomain (livre.oliva.athome.lsd.ic.unicamp.br [172.31.160.2]) by freie.oliva.athome.lsd.ic.unicamp.br (8.14.5/8.14.5) with ESMTP id q395o5qr025316; Mon, 9 Apr 2012 02:50:05 -0300 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 q395o56Y001737; Mon, 9 Apr 2012 02:50:05 -0300 Received: (from aoliva@localhost) by livre.localdomain (8.14.3/8.14.3/Submit) id q395o2uo001734; Mon, 9 Apr 2012 02:50:02 -0300 From: Alexandre Oliva To: gcc-patches@gcc.gnu.org Cc: jakub@redhat.com Subject: [PR51570] minimize ENTRY_VALUEs in debug location lists Date: Mon, 09 Apr 2012 02:50:02 -0300 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 gcc.dg/guality/pr45003-*.c have regressed with reordering of the exploration of the loc expansion space, in a way that didn't always privilege expansions without ENTRY_VALUEs over ones with it. This patch fixes it, by ensuring that we'll only ever use ENTRY_VALUEs if we can't help it given a maximum expression depth (complexity, actually), and, if we can't help it, we'll go for an option that uses the fewest ENTRY_VALUEs. Regstrap time is about the same, as expected, assuming the 2% lower regstrap time is not statistically significant. Regstrapped on trunk on x86_64-linux-gnu and i686-linux-gnu. It restored pr45003-[23].c to XPASS, without any regressions. pr45003-1.c is unchanged by this patch by itself, but in combination with another patch I'm posting soon that caused it to regress, this patch also avoids the regression. Ok to install? for gcc/ChangeLog from Alexandre Oliva PR debug/51570 * var-tracking.c (expand_depth): New type. (onepart_aux, expand_loc_callback_data): Change depth type to it. (loc_exp_dep_alloc): Adjust initializer. (update_depth): Use new type. Add entryvals. (vt_expand_var_loc_chain): Take note of expansions with ENTRY_VALUEs, but don't accept them right away. Run an optional second pass accepting the minimum ENTRY_VALUE count found in the first pass. (vt_expand_loc_callback, INIT_ELCD): Adjust. Index: gcc/var-tracking.c =================================================================== --- gcc/var-tracking.c.orig 2012-04-08 01:43:59.466998531 -0300 +++ gcc/var-tracking.c 2012-04-08 01:50:25.657377155 -0300 @@ -320,6 +320,19 @@ typedef struct loc_exp_dep_s DEF_VEC_O (loc_exp_dep); +/* This data structure holds information about the depth of a variable + expansion. */ +typedef struct expand_depth_struct +{ + /* This measures the complexity of the expanded expression. It + grows by one for each level of expansion that adds more than one + operand. */ + int complexity; + /* This counts the number of ENTRY_VALUE expressions in an + expansion. We want to minimize their use. */ + int entryvals; +} expand_depth; + /* This data structure is allocated for one-part variables at the time of emitting notes. */ struct onepart_aux @@ -338,7 +351,7 @@ struct onepart_aux a change notification from any of its active dependencies. */ rtx from; /* The depth of the cur_loc expression. */ - int depth; + expand_depth depth; /* Dependencies actively used when expand FROM into cur_loc. */ VEC (loc_exp_dep, none) deps; }; @@ -7491,7 +7504,7 @@ struct expand_loc_callback_data /* The maximum depth among the sub-expressions under expansion. Zero indicates no expansion so far. */ - int depth; + expand_depth depth; }; /* Allocate the one-part auxiliary data structure for VAR, with enough @@ -7536,7 +7549,8 @@ loc_exp_dep_alloc (variable var, int cou VAR_LOC_1PAUX (var) = XNEWVAR (struct onepart_aux, allocsize); *VAR_LOC_DEP_LSTP (var) = NULL; VAR_LOC_FROM (var) = NULL; - VAR_LOC_DEPTH (var) = 0; + VAR_LOC_DEPTH (var).complexity = 0; + VAR_LOC_DEPTH (var).entryvals = 0; } VEC_embedded_init (loc_exp_dep, VAR_LOC_DEP_VEC (var), count); } @@ -7691,21 +7705,26 @@ static rtx vt_expand_loc_callback (rtx x /* Return the combined depth, when one sub-expression evaluated to BEST_DEPTH and the previous known depth was SAVED_DEPTH. */ -static inline int -update_depth (int saved_depth, int best_depth) +static inline expand_depth +update_depth (expand_depth saved_depth, expand_depth best_depth) { /* If we didn't find anything, stick with what we had. */ - if (!best_depth) + if (!best_depth.complexity) return saved_depth; /* If we found hadn't found anything, use the depth of the current expression. Do NOT add one extra level, we want to compute the maximum depth among sub-expressions. We'll increment it later, if appropriate. */ - if (!saved_depth) + if (!saved_depth.complexity) return best_depth; - if (saved_depth < best_depth) + /* Combine the entryval count so that regardless of which one we + return, the entryval count is accurate. */ + best_depth.entryvals = saved_depth.entryvals + = best_depth.entryvals + saved_depth.entryvals; + + if (saved_depth.complexity < best_depth.complexity) return best_depth; else return saved_depth; @@ -7727,12 +7746,14 @@ vt_expand_var_loc_chain (variable var, b bool pending_recursion; rtx loc_from = NULL; struct elt_loc_list *cloc = NULL; - int depth = 0, saved_depth = elcd->depth; + expand_depth depth = { 0, 0 }, saved_depth = elcd->depth; + int wanted_entryvals, found_entryvals = 0; /* Clear all backlinks pointing at this, so that we're not notified while we're active. */ loc_exp_dep_clear (var); + retry: if (var->onepart == ONEPART_VALUE) { cselib_val *val = CSELIB_VAL_PTR (dv_as_value (var->dv)); @@ -7745,13 +7766,15 @@ vt_expand_var_loc_chain (variable var, b first_child = result_first_child = last_child = VEC_length (rtx, elcd->expanding); + wanted_entryvals = found_entryvals; + /* Attempt to expand each available location in turn. */ for (next = loc = var->n_var_parts ? var->var_part[0].loc_chain : NULL; loc || cloc; loc = next) { result_first_child = last_child; - if (!loc || (GET_CODE (loc->loc) == ENTRY_VALUE && cloc)) + if (!loc) { loc_from = cloc->loc; next = loc; @@ -7767,7 +7790,7 @@ vt_expand_var_loc_chain (variable var, b gcc_checking_assert (!unsuitable_loc (loc_from)); - elcd->depth = 0; + elcd->depth.complexity = elcd->depth.entryvals = 0; result = cselib_expand_value_rtx_cb (loc_from, regs, EXPR_DEPTH, vt_expand_loc_callback, data); last_child = VEC_length (rtx, elcd->expanding); @@ -7776,23 +7799,48 @@ vt_expand_var_loc_chain (variable var, b { depth = elcd->depth; - gcc_checking_assert (depth || result_first_child == last_child); + gcc_checking_assert (depth.complexity + || result_first_child == last_child); if (last_child - result_first_child != 1) - depth++; + { + if (!depth.complexity && GET_CODE (result) == ENTRY_VALUE) + depth.entryvals++; + depth.complexity++; + } - if (depth <= EXPR_USE_DEPTH) - break; + if (depth.complexity <= EXPR_USE_DEPTH) + { + if (depth.entryvals <= wanted_entryvals) + break; + else if (!found_entryvals || depth.entryvals < found_entryvals) + found_entryvals = depth.entryvals; + } result = NULL; } /* Set it up in case we leave the loop. */ - depth = 0; + depth.complexity = depth.entryvals = 0; loc_from = NULL; result_first_child = first_child; } + if (!loc_from && wanted_entryvals < found_entryvals) + { + /* We found entries with ENTRY_VALUEs and skipped them. Since + we could not find any expansions without ENTRY_VALUEs, but we + found at least one with them, go back and get an entry with + the minimum number ENTRY_VALUE count that we found. We could + avoid looping, but since each sub-loc is already resolved, + the re-expansion should be trivial. ??? Should we record all + attempted locs as dependencies, so that we retry the + expansion should any of them change, in the hope it can give + us a new entry without an ENTRY_VALUE? */ + VEC_truncate (rtx, elcd->expanding, first_child); + goto retry; + } + /* Register all encountered dependencies as active. */ pending_recursion = loc_exp_dep_set (var, result, VEC_address (rtx, elcd->expanding) + result_first_child, @@ -7805,7 +7853,7 @@ vt_expand_var_loc_chain (variable var, b VAR_LOC_FROM (var) = loc_from; VAR_LOC_DEPTH (var) = depth; - gcc_checking_assert (!depth == !result); + gcc_checking_assert (!depth.complexity == !result); elcd->depth = update_depth (saved_depth, depth); @@ -7893,7 +7941,7 @@ vt_expand_loc_callback (rtx x, bitmap re gcc_checking_assert (!NO_LOC_P (x)); gcc_checking_assert (var->var_part[0].cur_loc); gcc_checking_assert (VAR_LOC_1PAUX (var)); - gcc_checking_assert (VAR_LOC_1PAUX (var)->depth); + gcc_checking_assert (VAR_LOC_1PAUX (var)->depth.complexity); elcd->depth = update_depth (elcd->depth, VAR_LOC_1PAUX (var)->depth); @@ -7967,7 +8015,7 @@ resolve_expansions_pending_recursion (VE (d).vars = (v); \ (d).expanding = VEC_alloc (rtx, stack, 4); \ (d).pending = VEC_alloc (rtx, stack, 4); \ - (d).depth = 0; \ + (d).depth.complexity = (d).depth.entryvals = 0; \ } \ while (0) /* Finalize expand_loc_callback_data D, resolved to location L. */