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: 67406 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:5915:0:0:0:0:0 with SMTP id v21csp876581wrd; Fri, 10 Mar 2023 05:39:47 -0800 (PST) X-Google-Smtp-Source: AK7set/NJQI5Y9vBAKzE6qC+p0rHgYj+cHamdx2kYf4PYk3qSRbYwNGSYX+cUWXIxLq/mKEkfi7T X-Received: by 2002:a17:906:1687:b0:8b1:2c2d:4658 with SMTP id s7-20020a170906168700b008b12c2d4658mr25688024ejd.33.1678455587653; Fri, 10 Mar 2023 05:39:47 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1678455587; cv=none; d=google.com; s=arc-20160816; b=yBqPPwJ9y/IWexT76GBKE47+ww5KMVbNPibZrZt6NQszIGumeIonmJQK3s0vfjGZ7g OJeE8215Mr+KeNMeKSiV6rjHYdS3DnJHKeoDOmtFaS7iG2/fcULO6dsxJxg9W8ai6raU l0IW9rQWSua4iAqImAJtboXD2IOSzRa/OfaHALVYxuND4GLYnNoZxxEUHMFaVnmzK/s6 NbQaTtgtXJVmKVC7jUgxPnyh/Ns65uDqT4Gsx4xJLCmzcBlSft8hZboTQdSmoLlDRASb ymzORFJ+rCq3BDPxs7JhJcam/gTBrpklCVepI77GqWyqmX2MyN1YBGgk5uBp56oAbxKE TSHw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:reply-to:from:list-subscribe:list-help:list-post :list-archive:list-unsubscribe:list-id:precedence:message-id :mime-version:subject:to:date:dmarc-filter:delivered-to :dkim-signature:dkim-filter; bh=f2FhPX0YVV9BsovmfrfR/FvYbCmDvr8C+OUe/Xe5UDM=; b=ICMOj8q9+dBiYPEbr4k0w/YZrGlJGKb2BxVK6+GJgfrIqECvZNU8yfpnoSwX1SifRH zaZmvs9AFFF/olkWbd5zXBo0TddkXCSmaclLwJKBWfJ9mVkqYcdgGuQK59QhpKzGMJ5Y 2a/TCQDnzYz5XCIZ6dO9VGsfikndTD64PERt8DmApzcVF5PDKTHMTrwnX2v9TJLtIvWW hMhVwlvx/RX3cPHltRlxRCXo5m9yx+kiNPiizErjRC+UUpB/duphoaMs/oDLe8IsFv00 NhFV5S/O5CnOr05m2uSB6KsEHiiR2Prz8rNczTChjG7JfjA1+X8lO9FV4B8C3W61wHAB ichA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=fuk3XVZS; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from sourceware.org (server2.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id hh15-20020a170906a94f00b008e66e454eb9si2293947ejb.1.2023.03.10.05.39.47 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 10 Mar 2023 05:39:47 -0800 (PST) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=fuk3XVZS; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id AC4C7385840F for ; Fri, 10 Mar 2023 13:39:46 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org AC4C7385840F DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1678455586; 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=fuk3XVZS4R7N5R9TBJ4YZ1FZTjVFUqD1m0NZGtYlpsL7YkBLT9L9i0P8HVq41tSzW CHxvgxHDUbQGMLjfuDI7iBmi9Z4uJcSJhmc5sXIM6xIsyhwr3EvzN0/euM+P4GbPBe PgYZEunqBbuXub34HwCSEY6zR66O+yJ4td42h2q0= 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+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1759988246253681155?= X-GMAIL-MSGID: =?utf-8?q?1759988246253681155?= 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);