This patch adds a function graphds_wcc to find the weakly connected
components (WCCs) of a graph. It assigns a component index to each
vertex and can also output vertex indices grouped by component.
The new function will be used by the following vectorizer patch to
process the SLP graph one WCC at a time.
Bootstrapped and tested on aarch64-linux-gnu and x86_64-linux-gnu.
gcc/ChangeLog:
* graphds.cc (graphds_wcc): New function.
* graphds.h (graphds_wcc): Declare.
---
gcc/graphds.cc | 50 ++++++++++++++++++++++++++++++++++++++++++++++++++
gcc/graphds.h | 1 +
2 files changed, 51 insertions(+)
diff --git a/gcc/graphds.cc b/gcc/graphds.cc
index 717fa04cd278..17821694ace0 100644
--- a/gcc/graphds.cc
+++ b/gcc/graphds.cc
@@ -327,6 +327,56 @@ graphds_scc (struct graph *g, bitmap subgraph,
return comp;
}
+/* Determines the weakly connected components of G. If WCC_GROUPING is not
+ NULL, all nodes of a WCC are listed consecutively in it.
+
+ After running this function, v->component is the index of the weakly
+ connected component of G. Returns the number of WCCs in G. */
+
+int
+graphds_wcc (struct graph *g, vec<int> *wcc_grouping)
+{
+ int i, comp = 0;
+ auto_vec<int> worklist;
+
+ for (i = 0; i < g->n_vertices; i++)
+ g->vertices[i].component = -1;
+
+ for (i = 0; i < g->n_vertices; i++)
+ {
+ if (g->vertices[i].component != -1)
+ continue;
+
+ g->vertices[i].component = comp;
+ worklist.safe_push (i);
+ while (!worklist.is_empty ())
+ {
+ int curr = worklist.pop ();
+ if (wcc_grouping)
+ wcc_grouping->safe_push (curr);
+
+ /* Search both predecessors and successors of the current vertex,
+ since we are looking for weakly connected components. */
+ auto visit = [&](int next)
+ {
+ if (g->vertices[next].component == -1)
+ {
+ g->vertices[next].component = comp;
+ worklist.safe_push (next);
+ }
+ else
+ gcc_assert (g->vertices[next].component == comp);
+ };
+ for (graph_edge *e = g->vertices[curr].pred; e; e = e->pred_next)
+ visit (e->src);
+ for (graph_edge *e = g->vertices[curr].succ; e; e = e->succ_next)
+ visit (e->dest);
+ }
+ comp++;
+ }
+ return comp;
+}
+
/* Runs CALLBACK for all edges in G. DATA is private data for CALLBACK. */
void
diff --git a/gcc/graphds.h b/gcc/graphds.h
index fa17e20c2f2e..12e6dbdc1338 100644
--- a/gcc/graphds.h
+++ b/gcc/graphds.h
@@ -60,6 +60,7 @@ 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,
vec<int> * = NULL);
+int graphds_wcc (struct graph *, vec<int> * = NULL);
void graphds_domtree (struct graph *, int, int *, int *, int *);
typedef void (*graphds_edge_callback) (struct graph *,
struct graph_edge *, void *);
--
2.43.0
