From patchwork Thu Jun 10 17:07:38 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexandre Oliva X-Patchwork-Id: 55239 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 9B84A1007D1 for ; Fri, 11 Jun 2010 03:08:02 +1000 (EST) Received: (qmail 27261 invoked by alias); 10 Jun 2010 17:07:59 -0000 Received: (qmail 27112 invoked by uid 22791); 10 Jun 2010 17:07:56 -0000 X-SWARE-Spam-Status: No, hits=-4.8 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; Thu, 10 Jun 2010 17:07:47 +0000 Received: from int-mx04.intmail.prod.int.phx2.redhat.com (int-mx04.intmail.prod.int.phx2.redhat.com [10.5.11.17]) by mx1.redhat.com (8.13.8/8.13.8) with ESMTP id o5AH7hS3009226 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Thu, 10 Jun 2010 13:07:43 -0400 Received: from localhost.localdomain (ovpn01.gateway.prod.ext.phx2.redhat.com [10.5.9.1]) by int-mx04.intmail.prod.int.phx2.redhat.com (8.13.8/8.13.8) with ESMTP id o5AH7etB012608 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Thu, 10 Jun 2010 13:07:42 -0400 Received: from livre.localdomain (livre.oliva.athome.lsd.ic.unicamp.br [172.31.160.2]) by localhost.localdomain (8.14.3/8.14.3) with ESMTP id o5AH7ePV007232; Thu, 10 Jun 2010 14:07:40 -0300 Received: from livre.localdomain (aoliva@localhost [127.0.0.1]) by livre.localdomain (8.14.3/8.14.3/Debian-5+lenny1) with ESMTP id o5AH7dAL002094; Thu, 10 Jun 2010 14:07:39 -0300 Received: (from aoliva@localhost) by livre.localdomain (8.14.3/8.14.3/Submit) id o5AH7cj5002091; Thu, 10 Jun 2010 14:07:38 -0300 From: Alexandre Oliva To: Richard Guenther Cc: Jakub Jelinek , gcc-patches@gcc.gnu.org Subject: Re: [PATCH] Speed up find_loc_in_1pdv (PR debug/41371) References: <20100604131521.GK10293@tyan-ft48-01.lab.bos.redhat.com> Date: Thu, 10 Jun 2010 14:07:38 -0300 In-Reply-To: (Richard Guenther's message of "Thu, 10 Jun 2010 12:29:58 +0200 (CEST)") 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 Jun 10, 2010, Richard Guenther wrote: > There's some odd spacing here: > + dv = dv_from_value (node->loc); > + rvar = (variable) htab_find_with_hash (vars, dv, > dv_htab_hash (dv)); Thanks, fixed. > Ok for trunk and the branch. Here's the patch I installed, with an additional comment. > Do you have updated timings for the testcases in the PR? No, I haven't measured the timing difference. for gcc/ChangeLog from Alexandre Oliva PR debug/41371 * var-tracking.c (find_loc_in_1pdv): Remove recursion, only tail-recurse into canonical node. Fast-forward over non-canonical VALUEs. Index: gcc/var-tracking.c =================================================================== --- gcc/var-tracking.c.orig 2010-06-10 08:15:13.000000000 -0300 +++ gcc/var-tracking.c 2010-06-10 09:26:18.000000000 -0300 @@ -2479,125 +2479,81 @@ dv_changed_p (decl_or_value dv) /* Return a location list node whose loc is rtx_equal to LOC, in the location list of a one-part variable or value VAR, or in that of - any values recursively mentioned in the location lists. */ + any values recursively mentioned in the location lists. VARS must + be in star-canonical form. */ static location_chain find_loc_in_1pdv (rtx loc, variable var, htab_t vars) { location_chain node; enum rtx_code loc_code; - location_chain ret = NULL; - int unmark_self = 0; -#ifdef ENABLE_CHECKING - static int mark_count; -#endif if (!var) - return ret; + return NULL; #ifdef ENABLE_CHECKING gcc_assert (dv_onepart_p (var->dv)); #endif if (!var->n_var_parts) - return ret; + return NULL; #ifdef ENABLE_CHECKING gcc_assert (var->var_part[0].offset == 0); + gcc_assert (loc != dv_as_opaque (var->dv)); #endif loc_code = GET_CODE (loc); for (node = var->var_part[0].loc_chain; node; node = node->next) { + decl_or_value dv; + variable rvar; + if (GET_CODE (node->loc) != loc_code) { if (GET_CODE (node->loc) != VALUE) continue; } else if (loc == node->loc) - { - ret = node; - break; - } + return node; else if (loc_code != VALUE) { if (rtx_equal_p (loc, node->loc)) - { - ret = node; - break; - } + return node; continue; } - if (!VALUE_RECURSED_INTO (node->loc)) - { - decl_or_value dv = dv_from_value (node->loc); - variable rvar = (variable) - htab_find_with_hash (vars, dv, dv_htab_hash (dv)); - if (rvar) + /* Since we're in star-canonical form, we don't need to visit + non-canonical nodes: one-part variables and non-canonical + values would only point back to the canonical node. */ + if (dv_is_value_p (var->dv) + && !canon_value_cmp (node->loc, dv_as_value (var->dv))) + { + /* Skip all subsequent VALUEs. */ + while (node->next && GET_CODE (node->next->loc) == VALUE) { - location_chain where; - - if (!unmark_self) - { - if (dv_is_value_p (var->dv) - && !VALUE_RECURSED_INTO (dv_as_value (var->dv))) - { - unmark_self = 1; + node = node->next; #ifdef ENABLE_CHECKING - mark_count++; -#endif - VALUE_RECURSED_INTO (dv_as_value (var->dv)) = true; - } - else - unmark_self = -1; - } - -#ifdef ENABLE_CHECKING - mark_count++; - /* The recursion count is bounded because we're - searching in a star-canonicalized set, i.e., each - equivalence set of values is arranged so that the - canonical value has all locations and equivalent - values, whereas equivalent values only point back to - the canonical. So, if we start at the canonical - value, we'll recurse at most into each sibling, so - the recurse limit will be 2. If we start at a - non-canonical value, we'll recurse into the - canonical, and from there to other siblings, so - recurse limit will be 3. If we start at a one-part - variable, we add one level of recursion, but we don't - count it. */ - gcc_assert (mark_count <= 3); -#endif - VALUE_RECURSED_INTO (node->loc) = true; - if ((where = find_loc_in_1pdv (loc, rvar, vars))) - { -#ifdef ENABLE_CHECKING - mark_count--; -#endif - VALUE_RECURSED_INTO (node->loc) = false; - ret = where; - break; - } - VALUE_RECURSED_INTO (node->loc) = false; -#ifdef ENABLE_CHECKING - mark_count--; + gcc_assert (!canon_value_cmp (node->loc, + dv_as_value (var->dv))); #endif + if (loc == node->loc) + return node; } + continue; } - } - if (unmark_self > 0) - { - VALUE_RECURSED_INTO (dv_as_value (var->dv)) = false; #ifdef ENABLE_CHECKING - mark_count--; - gcc_assert (mark_count == 0); + gcc_assert (node == var->var_part[0].loc_chain); + gcc_assert (!node->next); #endif + + dv = dv_from_value (node->loc); + rvar = (variable) htab_find_with_hash (vars, dv, dv_htab_hash (dv)); + return find_loc_in_1pdv (loc, rvar, vars); } - return ret; + return NULL; } /* Hash table iteration argument passed to variable_merge. */ @@ -4031,6 +3987,12 @@ variable_post_merge_perm_vals (void **ps var = shared_hash_find (set->vars, dv); if (var) { + /* Although variable_post_merge_new_vals may have made decls + non-star-canonical, values that pre-existed in canonical form + remain canonical, and newly-created values reference a single + REG, so they are canonical as well. Since VAR has the + location list for a VALUE, using find_loc_in_1pdv for it is + fine, since VALUEs don't map back to DECLs. */ if (find_loc_in_1pdv (pnode->loc, var, shared_hash_htab (set->vars))) return 1; val_reset (set, dv);