From patchwork Thu Mar 6 07:05:51 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexandre Oliva X-Patchwork-Id: 327324 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.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 78ED72C0086 for ; Thu, 6 Mar 2014 18:07:16 +1100 (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:subject:references:date:in-reply-to:message-id:mime-version :content-type; q=dns; s=default; b=gxQUEik5N0OnniHn8go/Xe07qiQ5g a0xWMyypeswj0YW4TAxQ1GxCxG+BDBQRvSmypaVlMTQ9v0AV6i39lyi7nIkeupHz MbxDQiPRZ3CHj56SZS/0YwPxpFI1ix0w2buO186YIyAY9NQhBoLRBbDbo5oVqy3Z 09ZHnRlB9nlEv4= 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:subject:references:date:in-reply-to:message-id:mime-version :content-type; s=default; bh=Y177CDXAi42ZaUOv36l5i+Bs71w=; b=J5l dKA2Hsz6IW1mKVPl0F8uoYzluplFieaJyPPf6Vb0B25jrp8/7RBEABL2v4MO7FLG PXQjGl+6wyl/0fsQBIpKJ/ejke0oFwHA1lS7kj5+B3eLLE5qinwuVQN3Q6YFrs2e v0EpFrJwpBteCOoERJhcRjVe0FGjFY/xHpfaSH1M= Received: (qmail 8597 invoked by alias); 6 Mar 2014 07:07:09 -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 8587 invoked by uid 89); 6 Mar 2014 07:07:08 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-3.1 required=5.0 tests=AWL, BAYES_00, SPF_HELO_PASS, SPF_PASS, T_RP_MATCHES_RCVD, T_TVD_MIME_NO_HEADERS autolearn=ham version=3.3.2 X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Thu, 06 Mar 2014 07:07:06 +0000 Received: from int-mx02.intmail.prod.int.phx2.redhat.com (int-mx02.intmail.prod.int.phx2.redhat.com [10.5.11.12]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id s26774d8003492 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK) for ; Thu, 6 Mar 2014 02:07:04 -0500 Received: from freie.home (ovpn01.gateway.prod.ext.phx2.redhat.com [10.5.9.1]) by int-mx02.intmail.prod.int.phx2.redhat.com (8.13.8/8.13.8) with ESMTP id s26770ut013805 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Thu, 6 Mar 2014 02:07:03 -0500 Received: from livre.home (livre.home [172.31.160.2]) by freie.home (8.14.8/8.14.7) with ESMTP id s2675qtn009816; Thu, 6 Mar 2014 04:05:53 -0300 From: Alexandre Oliva To: gcc-patches@gcc.gnu.org Subject: Re: [PR debug/59992 #1/2] avoid quadratic behavior for the removal of useless values References: Date: Thu, 06 Mar 2014 04:05:51 -0300 In-Reply-To: (Alexandre Oliva's message of "Thu, 27 Feb 2014 02:54:46 -0300") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.2 (gnu/linux) MIME-Version: 1.0 On Feb 27, 2014, Alexandre Oliva wrote: > I wasn't entirely sure this wouldn't invalidate assumptions made in > callers of cselib_preserve_only_values (the function called at the end > of each extended basic block), but some analysis, plus comparing before > and after assembly output ;-), made sure it didn't ;-) For some values of didn't ;-) PR60381 proved otherwise. On PA, FP args may be passed by reference with incoming-rtl (mem (plus (reg) (const_int))), and we don't preserve the VALUE for the REG in this case. There may be other such cases, so I decided to not try to fix just this one. Fortunately, the second patch of this series, that moves permanent entries to an alternate table, brings about by itself nearly all of the benefit of the two together. I'm checking this in. Revert r208220. From: Alexandre Oliva for gcc/ChangeLog PR debug/60381 Revert: 2014-02-28 Alexandre Oliva PR debug/59992 * cselib.c (remove_useless_values): Skip to avoid quadratic behavior if the condition moved from... (cselib_process_insn): ... here holds. --- gcc/cselib.c | 16 +++++++--------- 1 file changed, 7 insertions(+), 9 deletions(-) diff --git a/gcc/cselib.c b/gcc/cselib.c index 0fcfe28..4dfc557 100644 --- a/gcc/cselib.c +++ b/gcc/cselib.c @@ -681,14 +681,6 @@ remove_useless_values (void) { cselib_val **p, *v; - if (n_useless_values <= MAX_USELESS_VALUES - /* remove_useless_values is linear in the hash table size. Avoid - quadratic behavior for very large hashtables with very few - useless elements. */ - || ((unsigned int)n_useless_values - <= (cselib_hash_table.elements () - n_debug_values) / 4)) - return; - /* First pass: eliminate locations that reference the value. That in turn can make more values useless. */ do @@ -2720,7 +2712,13 @@ cselib_process_insn (rtx insn) cselib_current_insn = NULL_RTX; - remove_useless_values (); + if (n_useless_values > MAX_USELESS_VALUES + /* remove_useless_values is linear in the hash table size. Avoid + quadratic behavior for very large hashtables with very few + useless elements. */ + && ((unsigned int)n_useless_values + > (cselib_hash_table.elements () - n_debug_values) / 4)) + remove_useless_values (); } /* Initialize cselib for one pass. The caller must also call