From patchwork Fri Nov 7 23:00:22 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jeff Law X-Patchwork-Id: 408317 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 1C8481400A6 for ; Sat, 8 Nov 2014 10:00:46 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :message-id:date:from:mime-version:to:subject:content-type; q= dns; s=default; b=LffP0pZfCDG4Z3FAUZCdpxipZXyw8SHGa6fluTR4RHlTqd GfmDMDSajnJg5v688j7EGL7asYwEhI4Y24gcgZH5rK1Ylihldpv1cnVl83s5c51X 1L4IbKx898DRPG1qGHMUvYbwObx7f3tMymNwbOi6Bu42cGs82kC/3yE07HeKI= 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 :message-id:date:from:mime-version:to:subject:content-type; s= default; bh=LpJXQlOIlFLGe0kjo9QEOOZA79Q=; b=xAu+WbZlR9n94A8RT6U8 vBRIzcPgJHO0tMsO2Cm4F/+IecxR/WOJu90TNT1fTTlGSXc2ZfEJAz+FZlb41U3w s7fuvP6NQakX9cIGjDOnxaXndRvwJ+prRyDE8K+lwTPygMr9PjDPGi29TcmDbQ1W ED7ZNVD/JFbVJXJJBouAAUQ= Received: (qmail 901 invoked by alias); 7 Nov 2014 23:00:38 -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 890 invoked by uid 89); 7 Nov 2014 23:00:37 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.1 required=5.0 tests=AWL, BAYES_00, RP_MATCHES_RCVD, SPF_HELO_PASS, SPF_PASS 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 (AES256-GCM-SHA384 encrypted) ESMTPS; Fri, 07 Nov 2014 23:00:27 +0000 Received: from int-mx11.intmail.prod.int.phx2.redhat.com (int-mx11.intmail.prod.int.phx2.redhat.com [10.5.11.24]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id sA7N0P0n013192 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=FAIL) for ; Fri, 7 Nov 2014 18:00:25 -0500 Received: from [10.3.113.31] (ovpn-113-31.phx2.redhat.com [10.3.113.31]) by int-mx11.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id sA7N0Osc028586 for ; Fri, 7 Nov 2014 18:00:24 -0500 Message-ID: <545D4F06.60207@redhat.com> Date: Fri, 07 Nov 2014 16:00:22 -0700 From: Jeff Law User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.2.0 MIME-Version: 1.0 To: gcc-patches@gcc.gnu.org Subject: [PR tree-optimization/61515] Fix poor compile-time behaviour in tree-ssa-threadedge.c X-IsSubscribed: yes When we thread across a backedge, we have to do invalidations of equivalences. This changes the method by which we identify which objects need invalidation. Previously we'd walk all the SSA_NAMEs and see if any had a current value that needed invalidation. That is obviously expensive if we have a lot of SSA_NAMEs. This patch implements an idea from Richi, basically walk the equivalency unwinder stack, which has equivalences from both DOM and the threader. Check the current value of each object in that stack and see if it needs invalidation. Even pathlogical cases this ought to be considerably faster than walking all the SSA_NAMEs. For the reduced testcase, compilation time in the relevant parts of GCC go from 40 seconds to less than a second. Bootstrapped and regression tested on x86_64-unknown-linux-gnu. Installed on the trunk. diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 966c0b4..0c8eb79 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,9 @@ +2014-11-07 Jeff Law + + PR tree-optimization/61515 + * tree-ssa-threadedge.c (invalidate_equivalences): Walk the unwinding + stack rather than looking at every SSA_NAME's value. + 2014-11-07 Richard Biener PR tree-optimization/63605 diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c index de3c819..d5b9696 100644 --- a/gcc/tree-ssa-threadedge.c +++ b/gcc/tree-ssa-threadedge.c @@ -290,15 +290,40 @@ fold_assignment_stmt (gimple stmt) } /* A new value has been assigned to LHS. If necessary, invalidate any - equivalences that are no longer valid. */ + equivalences that are no longer valid. This includes invaliding + LHS and any objects that are currently equivalent to LHS. + + Finding the objects that are currently marked as equivalent to LHS + is a bit tricky. We could walk the ssa names and see if any have + SSA_NAME_VALUE that is the same as LHS. That's expensive. + + However, it's far more efficient to look at the unwinding stack as + that will have all context sensitive equivalences which are the only + ones that we really have to worry about here. */ static void invalidate_equivalences (tree lhs, vec *stack) { - for (unsigned int i = 1; i < num_ssa_names; i++) - if (ssa_name (i) && SSA_NAME_VALUE (ssa_name (i)) == lhs) - record_temporary_equivalence (ssa_name (i), NULL_TREE, stack); + /* The stack is an unwinding stack. If the current element is NULL + then it's a "stop unwinding" marker. Else the current marker is + the SSA_NAME with an equivalence and the prior entry in the stack + is what the current element is equivalent to. */ + for (int i = stack->length() - 1; i >= 0; i--) + { + /* Ignore the stop unwinding markers. */ + if ((*stack)[i] == NULL) + continue; + + /* We want to check the current value of stack[i] to see if + it matches LHS. If so, then invalidate. */ + if (SSA_NAME_VALUE ((*stack)[i]) == lhs) + record_temporary_equivalence ((*stack)[i], NULL_TREE, stack); + + /* Remember, we're dealing with two elements in this case. */ + i--; + } + /* And invalidate any known value for LHS itself. */ if (SSA_NAME_VALUE (lhs)) record_temporary_equivalence (lhs, NULL_TREE, stack); }