From patchwork Fri Mar 10 13:38:57 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 66209 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 710083858C27 for ; Fri, 10 Mar 2023 13:39:31 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 710083858C27 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1678455571; bh=f2FhPX0YVV9BsovmfrfR/FvYbCmDvr8C+OUe/Xe5UDM=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=njpV1WMtRC6I7J+Nqiy+eypNvLzVl+iwa9vMqyk8p14sn1PQYcGPRzT16zJbQRXNI oZpF5VtiEj5PBRJ/Lg7PzA2BGc3fPyP807NRfm2MUrvm0GLpBkEURvnXBe5YeVouh/ qBpkvTa8m6E1Z9nUX1llDfS6navq4VM13Y8rVpNA= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out2.suse.de (smtp-out2.suse.de [195.135.220.29]) by sourceware.org (Postfix) with ESMTPS id A95CA3858D1E for ; Fri, 10 Mar 2023 13:38:59 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org A95CA3858D1E Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by smtp-out2.suse.de (Postfix) with ESMTPS id 8A10C20653 for ; Fri, 10 Mar 2023 13:38:58 +0000 (UTC) Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by imap2.suse-dmz.suse.de (Postfix) with ESMTPS id 76465134F7 for ; Fri, 10 Mar 2023 13:38:58 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id +8TLG/IyC2R2RgAAMHmgww (envelope-from ) for ; Fri, 10 Mar 2023 13:38:58 +0000 Date: Fri, 10 Mar 2023 14:38:57 +0100 (CET) To: gcc-patches@gcc.gnu.org Subject: [PATCH] Speedup PTA solving for call constraint sets MIME-Version: 1.0 Message-Id: <20230310133858.76465134F7@imap2.suse-dmz.suse.de> X-Spam-Status: No, score=-11.8 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Richard Biener via Gcc-patches From: Richard Biener Reply-To: Richard Biener Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" With calls we now often get contraints like callarg = *callarg + UNKNOWN or similar cases. The important thing to note is that this complex constraint changes the node solution itself, so when solving the node is marked as changed immediately again. When that happens it's profitable to iterate that self-cycle immediately so we maximize cache reuse and build up the successor graph quickly to get better topological ordering and reduce the number of iterations of the solving. For a testcase derived from ceph this reduces the time spent in PTA solving from 453s to 92s which is quite significant. Bootstrap and regtest running on x86_64-unknown-linux-gnu. For the testcase I verified we create identical points-to solutions before and after the change. There are regression bugs complaining about high PTA time (often only as part of overall slow compile), I did not verify if this improves any of those but consider the change a regression fix. * tree-ssa-structalias.cc (solve_graph): Immediately iterate self-cycles. --- gcc/tree-ssa-structalias.cc | 15 +++++++++++---- 1 file changed, 11 insertions(+), 4 deletions(-) diff --git a/gcc/tree-ssa-structalias.cc b/gcc/tree-ssa-structalias.cc index fd7450b9477..fa3a2e4e1f9 100644 --- a/gcc/tree-ssa-structalias.cc +++ b/gcc/tree-ssa-structalias.cc @@ -2775,8 +2775,15 @@ solve_graph (constraint_graph_t graph) continue; /* If the node has changed, we need to process the - complex constraints and outgoing edges again. */ - if (bitmap_clear_bit (changed, i)) + complex constraints and outgoing edges again. For complex + constraints that modify i itself, like the common group of + callarg = callarg + UNKNOWN; + callarg = *callarg + UNKNOWN; + *callarg = callescape; + make sure to iterate immediately because that maximizes + cache reuse and expands the graph quickest, leading to + better visitation order in the next iteration. */ + while (bitmap_clear_bit (changed, i)) { unsigned int j; constraint_t c; @@ -2794,7 +2801,7 @@ solve_graph (constraint_graph_t graph) ??? But we shouldn't ended up with "changed" set ... */ if (vi->oldsolution && bitmap_bit_p (vi->oldsolution, anything_id)) - continue; + break; bitmap_copy (pts, get_varinfo (find (anything_id))->solution); } else if (vi->oldsolution) @@ -2803,7 +2810,7 @@ solve_graph (constraint_graph_t graph) bitmap_copy (pts, vi->solution); if (bitmap_empty_p (pts)) - continue; + break; if (vi->oldsolution) bitmap_ior_into (vi->oldsolution, pts);