From: Richard Sandiford <richard.sandiford@arm.com>
To: gcc-patches@gcc.gnu.org
Subject: [PATCH 3/6] Make graphds_scc pass the node order back to callers
Date: Thu, 25 Aug 2022 14:05:51 +0100 [thread overview]
Message-ID: <mptk06wiic0.fsf@arm.com> (raw)
In-Reply-To: <mptwnawiids.fsf@arm.com> (Richard Sandiford's message of "Thu, 25 Aug 2022 14:04:47 +0100")
As a side-effect, graphds_scc constructs a vector in which all
nodes in an SCC are listed consecutively. This can be useful
information, so that the patch adds an optional pass-back parameter
for it. The interface is similar to the one for graphds_dfs.
gcc/
* graphds.cc (graphds_scc): Add a pass-back parameter for the
final node order.
---
gcc/graphds.cc | 13 ++++++++++---
gcc/graphds.h | 3 ++-
2 files changed, 12 insertions(+), 4 deletions(-)
diff --git a/gcc/graphds.cc b/gcc/graphds.cc
index 91a2ca5c225..2a108fd475f 100644
--- a/gcc/graphds.cc
+++ b/gcc/graphds.cc
@@ -281,7 +281,14 @@ graphds_dfs (struct graph *g, int *qs, int nq, vec<int> *qt,
numbers assigned by the previous pass. If SUBGRAPH is not NULL, it
specifies the subgraph of G whose strongly connected components we want
to determine. If SKIP_EDGE_P is not NULL, it points to a callback function.
- Edge E will be skipped if callback function returns true.
+ Edge E will be skipped if callback function returns true. If SCC_GROUPING
+ is not null, the nodes will be added to it in the following order:
+
+ - If SCC A is a direct or indirect predecessor of SCC B in the SCC dag,
+ A's nodes come before B's nodes.
+
+ - All of an SCC's nodes are listed consecutively, although the order
+ of the nodes within an SCC is not really meaningful.
After running this function, v->component is the number of the strongly
connected component for each vertex of G. Returns the number of the
@@ -289,7 +296,7 @@ graphds_dfs (struct graph *g, int *qs, int nq, vec<int> *qt,
int
graphds_scc (struct graph *g, bitmap subgraph,
- skip_edge_callback skip_edge_p)
+ skip_edge_callback skip_edge_p, vec<int> *scc_grouping)
{
int *queue = XNEWVEC (int, g->n_vertices);
vec<int> postorder = vNULL;
@@ -317,7 +324,7 @@ graphds_scc (struct graph *g, bitmap subgraph,
for (i = 0; i < nq; i++)
queue[i] = postorder[nq - i - 1];
- comp = graphds_dfs (g, queue, nq, NULL, true, subgraph, skip_edge_p);
+ comp = graphds_dfs (g, queue, nq, scc_grouping, true, subgraph, skip_edge_p);
free (queue);
postorder.release ();
diff --git a/gcc/graphds.h b/gcc/graphds.h
index c54d8767fa7..e0e4d802cbb 100644
--- a/gcc/graphds.h
+++ b/gcc/graphds.h
@@ -58,7 +58,8 @@ void identify_vertices (struct graph *, int, int);
typedef bool (*skip_edge_callback) (struct graph_edge *);
int graphds_dfs (struct graph *, int *, int,
vec<int> *, bool, bitmap, skip_edge_callback = NULL);
-int graphds_scc (struct graph *, bitmap, skip_edge_callback = NULL);
+int graphds_scc (struct graph *, bitmap, skip_edge_callback = NULL,
+ vec<int> * = NULL);
void graphds_domtree (struct graph *, int, int *, int *, int *);
typedef void (*graphds_edge_callback) (struct graph *,
struct graph_edge *, void *);
--
2.25.1
next prev parent reply other threads:[~2022-08-25 13:05 UTC|newest]
Thread overview: 12+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-08-25 13:04 [PATCH 0/6] Optimise placement of SLP permutations Richard Sandiford
2022-08-25 13:05 ` [PATCH 1/6] Split code out of vectorizable_slp_permutation Richard Sandiford
2022-08-25 13:05 ` [PATCH 2/6] Split code out of vect_transform_slp_perm_load Richard Sandiford
2022-08-25 13:05 ` Richard Sandiford [this message]
2022-08-25 13:06 ` [PATCH 4/6] Rearrange unbounded_hashmap_traits Richard Sandiford
2022-08-25 13:06 ` [PATCH 5/6] Add base hash traits for vectors Richard Sandiford
2022-08-25 13:07 ` [PATCH 6/6] Extend SLP permutation optimisations Richard Sandiford
2022-08-26 16:26 ` Jeff Law
2022-08-30 14:50 ` Richard Sandiford
2022-08-30 14:50 ` Richard Sandiford
2022-08-31 14:38 ` Jeff Law
2022-08-26 9:25 ` [PATCH 0/6] Optimise placement of SLP permutations Richard Biener
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=mptk06wiic0.fsf@arm.com \
--to=richard.sandiford@arm.com \
--cc=gcc-patches@gcc.gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).