From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1130) id 168F3382F09A; Tue, 30 Aug 2022 14:44:22 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 168F3382F09A DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1661870662; bh=jC+4HsepHCCx5ET+zgGWdhBHfekACPLJgJkhh2qFEtk=; h=From:To:Subject:Date:From; b=VWL35oahRPk7CzQQJii70mh1CEEC1up/6wsB1DwKxSKYNefLj7x5aOkuhX2zXmjMD LFOmsSWNZvzUIVOmgu+znCVPGRvUnyWloQ14+yY1v+BtV2BCrp1GGGg75+fiTVGgo7 qW+S5qCM1PRDh/DnwXiVcj/FsBI40BdfeYF2slOg= MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Richard Sandiford To: gcc-cvs@gcc.gnu.org Subject: [gcc r13-2285] Make graphds_scc pass the node order back to callers X-Act-Checkin: gcc X-Git-Author: Richard Sandiford X-Git-Refname: refs/heads/trunk X-Git-Oldrev: 5551501e84dd51b569801c0e52b24f9e30124166 X-Git-Newrev: 2bac880a19633b96608548b412739379df1c10dc Message-Id: <20220830144422.168F3382F09A@sourceware.org> Date: Tue, 30 Aug 2022 14:44:22 +0000 (GMT) List-Id: https://gcc.gnu.org/g:2bac880a19633b96608548b412739379df1c10dc commit r13-2285-g2bac880a19633b96608548b412739379df1c10dc Author: Richard Sandiford Date: Tue Aug 30 15:43:46 2022 +0100 Make graphds_scc pass the node order back to callers 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. * graphds.h (graphds_scc): Update prototype accordingly. Diff: --- 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 *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 *qt, int graphds_scc (struct graph *g, bitmap subgraph, - skip_edge_callback skip_edge_p) + skip_edge_callback skip_edge_p, vec *scc_grouping) { int *queue = XNEWVEC (int, g->n_vertices); vec 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 *, 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 * = NULL); void graphds_domtree (struct graph *, int, int *, int *, int *); typedef void (*graphds_edge_callback) (struct graph *, struct graph_edge *, void *);