From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1666) id 77818385841E; Fri, 23 Jun 2023 10:29:55 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 77818385841E DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1687516195; bh=b5/UQpox5r+uat7sk554S6jWtBRHwnvU1RsqFqZnjaM=; h=From:To:Subject:Date:From; b=pTh/sxzKtp3c0s4nEEUhVQ9RoXNDgwhAg9LrSuTEdhNpdqxbzuSW4gudfRZEV575M +qMCh1k/ZYdEuTCZacyc/0cH9HsqL8F4sODaZOJ3kg36J9F8Ft+2eA2LLbB2K7Or2Y 9RwvWfy4vQHNZsxawjvZNK7Qq29FeyTY7vj3mLuE= MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Richard Biener To: gcc-cvs@gcc.gnu.org Subject: [gcc r13-7466] ipa/109983 - (IPA) PTA speedup X-Act-Checkin: gcc X-Git-Author: Richard Biener X-Git-Refname: refs/heads/releases/gcc-13 X-Git-Oldrev: fd8fc2c2ef69013043d0484b93054fb39b37664e X-Git-Newrev: a737da4885b7038fdd7d6646deaa1644efff2257 Message-Id: <20230623102955.77818385841E@sourceware.org> Date: Fri, 23 Jun 2023 10:29:55 +0000 (GMT) List-Id: https://gcc.gnu.org/g:a737da4885b7038fdd7d6646deaa1644efff2257 commit r13-7466-ga737da4885b7038fdd7d6646deaa1644efff2257 Author: Richard Biener Date: Wed May 31 12:07:42 2023 +0200 ipa/109983 - (IPA) PTA speedup 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. 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. (cherry picked from commit 95e5c38a98cc64a797b1d766a20f8c0d0c807a74) Diff: --- gcc/tree-ssa-structalias.cc | 117 +++++++++++++++++--------------------------- 1 file changed, 46 insertions(+), 71 deletions(-) diff --git a/gcc/tree-ssa-structalias.cc b/gcc/tree-ssa-structalias.cc index c3c5bce42df..1fed5190561 100644 --- a/gcc/tree-ssa-structalias.cc +++ b/gcc/tree-ssa-structalias.cc @@ -1581,64 +1581,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) - { - if (!bitmap_bit_p (ti->visited, j)) - topo_visit (graph, ti, j); - } - - ti->topo_order.safe_push (n); -} - /* Process a constraint C that represents x = *(y + off), using DELTA as the starting solution for y. */ @@ -1913,19 +1855,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 @@ -2753,17 +2732,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) @@ -2895,7 +2871,6 @@ solve_graph (constraint_graph_t graph) } } } - free_topo_info (ti); bitmap_obstack_release (&iteration_obstack); }