From patchwork Wed May 31 11:26:26 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 101371 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:994d:0:b0:3d9:f83d:47d9 with SMTP id k13csp2804028vqr; Wed, 31 May 2023 04:27:25 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ6Y1uX0MA3/099UdcFcTAdWMcqAJ3mPWvocTJdj1LlScIF7j63VVEeI30YiaLpInExU8Kd/ X-Received: by 2002:ac2:4859:0:b0:4f3:9930:5b8c with SMTP id 25-20020ac24859000000b004f399305b8cmr2368266lfy.25.1685532445284; Wed, 31 May 2023 04:27:25 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1685532445; cv=none; d=google.com; s=arc-20160816; b=QokpN9Zh0Elqb5q9obzPFosqoC4plhj3UFRXzNF22i4j4PSOYrN5JsRHiIPAiweWQ0 fWf2n6U43lgOyyBCtV6JB+m0d8ZxGrPvY6hDxmkZQzTxiFFzcSsBKNqAwHAUhnvp8qp+ BNpX621O5ywxuHfHtnSZp8Liy0iX6zP7d8uaUDCqHh/Q+KlJ0j7wtEUVMHqoSIWVkk1B NVWpN3Bavolmrxk114VM9cM/YNpNyGhq7XGsLYSd8wnF1x4vZuthbpfXh12ersceL37o 4IwAX44WwUSel3glsTgnykpfeFAv9Af1mCn3cMK9iqjyLTP+GsTomzLglALd/ofd3Ev5 +u1w== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=message-id:sender:errors-to:reply-to:from:list-subscribe:list-help :list-post:list-archive:list-unsubscribe:list-id:precedence :mime-version:user-agent:subject:to:date:dmarc-filter:delivered-to :dkim-signature:dkim-filter; bh=GN8rWwOmcddugPQ/c7+7r98UxMuSETUjvyTWdfksHls=; b=YiN4+J7jNA1PUCCauZFSAUY9eD8ZEOY1wRlTKZFsA6LJ+r1++nVy7RzcPeU4PFvKGq tTPP/Q8Ix3tZbAZVX1aaBAnL7loZ/UGETrar0BtxjaYLDCj0c85bfLOeVBmsd9UumaPZ l6NdPsgIyQ9PTweaMQ+iCINLAi9JtQOIE3+aNgvSbarw5TB4yWdAIAM0Yv64SIUuHVOA 83NUAgzVakooL7w8d0K+a4lJ5WEKCcKUf3bo/P99+yhKqF0cAlVcmK0lb2Lx4fEh/fMt D5ItdSEQepqjV4mwQ2iWlH6JxATz5U65V0JkOUhZ72qnpcY02XuhZ8N65RD65BWueuVl Pl/g== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=lTnVh+OK; 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 (ip-8-43-85-97.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id q25-20020aa7da99000000b00514b3d55fe0si1802106eds.289.2023.05.31.04.27.24 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 31 May 2023 04:27:25 -0700 (PDT) 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=lTnVh+OK; 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 777EF3858296 for ; Wed, 31 May 2023 11:27:11 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 777EF3858296 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1685532431; bh=GN8rWwOmcddugPQ/c7+7r98UxMuSETUjvyTWdfksHls=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=lTnVh+OKSvTUaAM1ofN249wKT8w2AQ42IW+C82tmCd//Fkw+gcKxYD/I1847DYBZq 20oxHDea9+pKEbJ5c/ydsM2NV/2mWuTjhDI+CUQslrSf622frER/wnf42rbi6mEHva ruLKMzhLtGam6dGrJnS82wUWby9rSn4eqfzDT5vE= 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 6D1C938582BE for ; Wed, 31 May 2023 11:26:27 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 6D1C938582BE Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id A02671F8C0 for ; Wed, 31 May 2023 11:26:26 +0000 (UTC) Received: from wotan.suse.de (wotan.suse.de [10.160.0.1]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by relay2.suse.de (Postfix) with ESMTPS id 954A42C141 for ; Wed, 31 May 2023 11:26:26 +0000 (UTC) Date: Wed, 31 May 2023 11:26:26 +0000 (UTC) To: gcc-patches@gcc.gnu.org Subject: [PATCH] ipa/109983 - (IPA) PTA speedup User-Agent: Alpine 2.22 (LSU 394 2020-01-19) MIME-Version: 1.0 X-Spam-Status: No, score=-10.6 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, MISSING_MID, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE 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" Message-Id: <20230531112711.777EF3858296@sourceware.org> X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1767408869343934106?= X-GMAIL-MSGID: =?utf-8?q?1767408869343934106?= This improves the edge avoidance heuristic by re-ordering the topological sort of the graph to make sure the component with the ESCAPED node is processed first. This improves the number of created edges which directly correlates with the number of bitmap_ior_into calls from 141447426 to 239596 and the compile-time from 1083s to 3s. It also improves the compile-time for the related PR109143 from 81s to 27s. I've modernized the topological sorting API on the way as well. Bootstrapped and tested on x86_64-unknown-linux-gnu, pushed. PR ipa/109983 PR tree-optimization/109143 * tree-ssa-structalias.cc (struct topo_info): Remove. (init_topo_info): Likewise. (free_topo_info): Likewise. (compute_topo_order): Simplify API, put the component with ESCAPED last so it's processed first. (topo_visit): Adjust. (solve_graph): Likewise. --- gcc/tree-ssa-structalias.cc | 118 ++++++++++++++---------------------- 1 file changed, 46 insertions(+), 72 deletions(-) diff --git a/gcc/tree-ssa-structalias.cc b/gcc/tree-ssa-structalias.cc index 9ded34c1dd1..8db99a42565 100644 --- a/gcc/tree-ssa-structalias.cc +++ b/gcc/tree-ssa-structalias.cc @@ -1585,65 +1585,6 @@ unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from, bitmap_clear_bit (graph->succs[to], to); } -/* Information needed to compute the topological ordering of a graph. */ - -struct topo_info -{ - /* sbitmap of visited nodes. */ - sbitmap visited; - /* Array that stores the topological order of the graph, *in - reverse*. */ - vec topo_order; -}; - - -/* Initialize and return a topological info structure. */ - -static struct topo_info * -init_topo_info (void) -{ - size_t size = graph->size; - struct topo_info *ti = XNEW (struct topo_info); - ti->visited = sbitmap_alloc (size); - bitmap_clear (ti->visited); - ti->topo_order.create (1); - return ti; -} - - -/* Free the topological sort info pointed to by TI. */ - -static void -free_topo_info (struct topo_info *ti) -{ - sbitmap_free (ti->visited); - ti->topo_order.release (); - free (ti); -} - -/* Visit the graph in topological order, and store the order in the - topo_info structure. */ - -static void -topo_visit (constraint_graph_t graph, struct topo_info *ti, - unsigned int n) -{ - bitmap_iterator bi; - unsigned int j; - - bitmap_set_bit (ti->visited, n); - - if (graph->succs[n]) - EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi) - { - unsigned k = find (j); - if (!bitmap_bit_p (ti->visited, k)) - topo_visit (graph, ti, k); - } - - ti->topo_order.safe_push (n); -} - /* Add a copy edge FROM -> TO, optimizing special cases. Returns TRUE if the solution of TO changed. */ @@ -1925,19 +1866,56 @@ find_indirect_cycles (constraint_graph_t graph) scc_visit (graph, &si, i); } -/* Compute a topological ordering for GRAPH, and store the result in the - topo_info structure TI. */ +/* Visit the graph in topological order starting at node N, and store the + order in TOPO_ORDER using VISITED to indicate visited nodes. */ static void -compute_topo_order (constraint_graph_t graph, - struct topo_info *ti) +topo_visit (constraint_graph_t graph, vec &topo_order, + sbitmap visited, unsigned int n) +{ + bitmap_iterator bi; + unsigned int j; + + bitmap_set_bit (visited, n); + + if (graph->succs[n]) + EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi) + { + unsigned k = find (j); + if (!bitmap_bit_p (visited, k)) + topo_visit (graph, topo_order, visited, k); + } + + topo_order.quick_push (n); +} + +/* Compute a topological ordering for GRAPH, and return the result. */ + +static auto_vec +compute_topo_order (constraint_graph_t graph) { unsigned int i; unsigned int size = graph->size; + auto_sbitmap visited (size); + bitmap_clear (visited); + + /* For the heuristic in add_graph_edge to work optimally make sure to + first visit the connected component of the graph containing + ESCAPED. Do this by extracting the connected component + with ESCAPED and append that to all other components as solve_graph + pops from the order. */ + auto_vec tail (size); + topo_visit (graph, tail, visited, find (escaped_id)); + + auto_vec topo_order (size); + for (i = 0; i != size; ++i) - if (!bitmap_bit_p (ti->visited, i) && find (i) == i) - topo_visit (graph, ti, i); + if (!bitmap_bit_p (visited, i) && find (i) == i) + topo_visit (graph, topo_order, visited, i); + + topo_order.splice (tail); + return topo_order; } /* Structure used to for hash value numbering of pointer equivalence @@ -2765,17 +2743,14 @@ solve_graph (constraint_graph_t graph) while (!bitmap_empty_p (changed)) { unsigned int i; - struct topo_info *ti = init_topo_info (); stats.iterations++; bitmap_obstack_initialize (&iteration_obstack); - compute_topo_order (graph, ti); - - while (ti->topo_order.length () != 0) + auto_vec topo_order = compute_topo_order (graph); + while (topo_order.length () != 0) { - - i = ti->topo_order.pop (); + i = topo_order.pop (); /* If this variable is not a representative, skip it. */ if (find (i) != i) @@ -2910,7 +2885,6 @@ solve_graph (constraint_graph_t graph) } } } - free_topo_info (ti); bitmap_obstack_release (&iteration_obstack); }