gcc/graphds.cc

   1 /* Graph representation and manipulation functions.
   2    Copyright (C) 2007-2024 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 3, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #include "config.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "bitmap.h"
  24 #include "graphds.h"
  25
  26 /* Dumps graph G into F.  */
  27
  28 void
  29 dump_graph (FILE *f, struct graph *g)
  30 {
  31   int i;
  32   struct graph_edge *e;
  33
  34   fprintf (f, "digraph {\n");
  35   for (i = 0; i < g->n_vertices; i++)
  36     {
  37       fprintf (f, "\"%d\" [label=\"%d (%d): %p\"];\n",
  38                i, i, g->vertices[i].component, g->vertices[i].data);
  39       for (e = g->vertices[i].pred; e; e = e->pred_next)
  40         fprintf (f, "\"%d\" -> \"%d\" [label=\"%p\"];\n", e->src, e->dest, e->data);
  41       for (e = g->vertices[i].succ; e; e = e->succ_next)
  42         fprintf (f, "\"%d\" -> \"%d\";\n", e->src, e->dest);
  43     }
  44   fprintf (f, "}\n");
  45 }
  46
  47 /* Creates a new graph with N_VERTICES vertices.  */
  48
  49 struct graph *
  50 new_graph (int n_vertices)
  51 {
  52   struct graph *g = XNEW (struct graph);
  53
  54   gcc_obstack_init (&g->ob);
  55   g->n_vertices = n_vertices;
  56   g->vertices = XOBNEWVEC (&g->ob, struct vertex, n_vertices);
  57   memset (g->vertices, 0, sizeof (struct vertex) * n_vertices);
  58
  59   return g;
  60 }
  61
  62 /* Adds an edge from F to T to graph G.  The new edge is returned.  */
  63
  64 struct graph_edge *
  65 add_edge (struct graph *g, int f, int t)
  66 {
  67   struct graph_edge *e = XOBNEW (&g->ob, struct graph_edge);
  68   struct vertex *vf = &g->vertices[f], *vt = &g->vertices[t];
  69
  70   e->src = f;
  71   e->dest = t;
  72
  73   e->pred_next = vt->pred;
  74   vt->pred = e;
  75
  76   e->succ_next = vf->succ;
  77   vf->succ = e;
  78
  79   e->data = NULL;
  80   return e;
  81 }
  82
  83 /* Moves all the edges incident with U to V.  */
  84
  85 void
  86 identify_vertices (struct graph *g, int v, int u)
  87 {
  88   struct vertex *vv = &g->vertices[v];
  89   struct vertex *uu = &g->vertices[u];
  90   struct graph_edge *e, *next;
  91
  92   for (e = uu->succ; e; e = next)
  93     {
  94       next = e->succ_next;
  95
  96       e->src = v;
  97       e->succ_next = vv->succ;
  98       vv->succ = e;
  99     }
 100   uu->succ = NULL;
 101
 102   for (e = uu->pred; e; e = next)
 103     {
 104       next = e->pred_next;
 105
 106       e->dest = v;
 107       e->pred_next = vv->pred;
 108       vv->pred = e;
 109     }
 110   uu->pred = NULL;
 111 }
 112
 113 /* Helper function for graphds_dfs.  Returns the source vertex of E, in the
 114    direction given by FORWARD.  */
 115
 116 static inline int
 117 dfs_edge_src (struct graph_edge *e, bool forward)
 118 {
 119   return forward ? e->src : e->dest;
 120 }
 121
 122 /* Helper function for graphds_dfs.  Returns the destination vertex of E, in
 123    the direction given by FORWARD.  */
 124
 125 static inline int
 126 dfs_edge_dest (struct graph_edge *e, bool forward)
 127 {
 128   return forward ? e->dest : e->src;
 129 }
 130
 131 /* Helper function for graphds_dfs.  Returns the first edge after E (including
 132    E), in the graph direction given by FORWARD, that belongs to SUBGRAPH.  If
 133    SKIP_EDGE_P is not NULL, it points to a callback function.  Edge E will be
 134    skipped if callback function returns true.  */
 135
 136 static inline struct graph_edge *
 137 foll_in_subgraph (struct graph_edge *e, bool forward, bitmap subgraph,
 138                   skip_edge_callback skip_edge_p)
 139 {
 140   int d;
 141
 142   if (!e)
 143     return e;
 144
 145   if (!subgraph && (!skip_edge_p || !skip_edge_p (e)))
 146     return e;
 147
 148   while (e)
 149     {
 150       d = dfs_edge_dest (e, forward);
 151       /* Return edge if it belongs to subgraph and shouldn't be skipped.  */
 152       if ((!subgraph || bitmap_bit_p (subgraph, d))
 153           && (!skip_edge_p || !skip_edge_p (e)))
 154         return e;
 155
 156       e = forward ? e->succ_next : e->pred_next;
 157     }
 158
 159   return e;
 160 }
 161
 162 /* Helper function for graphds_dfs.  Select the first edge from V in G, in the
 163    direction given by FORWARD, that belongs to SUBGRAPH.  If SKIP_EDGE_P is not
 164    NULL, it points to a callback function.  Edge E will be skipped if callback
 165    function returns true.  */
 166
 167 static inline struct graph_edge *
 168 dfs_fst_edge (struct graph *g, int v, bool forward, bitmap subgraph,
 169               skip_edge_callback skip_edge_p)
 170 {
 171   struct graph_edge *e;
 172
 173   e = (forward ? g->vertices[v].succ : g->vertices[v].pred);
 174   return foll_in_subgraph (e, forward, subgraph, skip_edge_p);
 175 }
 176
 177 /* Helper function for graphds_dfs.  Returns the next edge after E, in the
 178    graph direction given by FORWARD, that belongs to SUBGRAPH.  If SKIP_EDGE_P
 179    is not NULL, it points to a callback function.  Edge E will be skipped if
 180    callback function returns true.  */
 181
 182 static inline struct graph_edge *
 183 dfs_next_edge (struct graph_edge *e, bool forward, bitmap subgraph,
 184                skip_edge_callback skip_edge_p)
 185 {
 186   return foll_in_subgraph (forward ? e->succ_next : e->pred_next,
 187                            forward, subgraph, skip_edge_p);
 188 }
 189
 190 /* Runs dfs search over vertices of G, from NQ vertices in queue QS.
 191    The vertices in postorder are stored into QT.  If FORWARD is false,
 192    backward dfs is run.  If SUBGRAPH is not NULL, it specifies the
 193    subgraph of G to run DFS on.  Returns the number of the components
 194    of the graph (number of the restarts of DFS).  If SKIP_EDGE_P is not
 195    NULL, it points to a callback function.  Edge E will be skipped if
 196    callback function returns true.  */
 197
 198 int
 199 graphds_dfs (struct graph *g, int *qs, int nq, vec<int> *qt,
 200              bool forward, bitmap subgraph,
 201              skip_edge_callback skip_edge_p)
 202 {
 203   int i, tick = 0, v, comp = 0, top;
 204   struct graph_edge *e;
 205   struct graph_edge **stack = XNEWVEC (struct graph_edge *, g->n_vertices);
 206   bitmap_iterator bi;
 207   unsigned av;
 208
 209   if (subgraph)
 210     {
 211       EXECUTE_IF_SET_IN_BITMAP (subgraph, 0, av, bi)
 212         {
 213           g->vertices[av].component = -1;
 214           g->vertices[av].post = -1;
 215         }
 216     }
 217   else
 218     {
 219       for (i = 0; i < g->n_vertices; i++)
 220         {
 221           g->vertices[i].component = -1;
 222           g->vertices[i].post = -1;
 223         }
 224     }
 225
 226   for (i = 0; i < nq; i++)
 227     {
 228       v = qs[i];
 229       if (g->vertices[v].post != -1)
 230         continue;
 231
 232       g->vertices[v].component = comp++;
 233       e = dfs_fst_edge (g, v, forward, subgraph, skip_edge_p);
 234       top = 0;
 235
 236       while (1)
 237         {
 238           while (e)
 239             {
 240               if (g->vertices[dfs_edge_dest (e, forward)].component
 241                   == -1)
 242                 break;
 243               e = dfs_next_edge (e, forward, subgraph, skip_edge_p);
 244             }
 245
 246           if (!e)
 247             {
 248               if (qt)
 249                 qt->safe_push (v);
 250               g->vertices[v].post = tick++;
 251
 252               if (!top)
 253                 break;
 254
 255               e = stack[--top];
 256               v = dfs_edge_src (e, forward);
 257               e = dfs_next_edge (e, forward, subgraph, skip_edge_p);
 258               continue;
 259             }
 260
 261           stack[top++] = e;
 262           v = dfs_edge_dest (e, forward);
 263           e = dfs_fst_edge (g, v, forward, subgraph, skip_edge_p);
 264           g->vertices[v].component = comp - 1;
 265         }
 266     }
 267
 268   free (stack);
 269
 270   return comp;
 271 }
 272
 273 /* Determines the strongly connected components of G, using the algorithm of
 274    Kosaraju -- first determine the postorder dfs numbering in reversed graph,
 275    then run the dfs on the original graph in the order given by decreasing
 276    numbers assigned by the previous pass.  If SUBGRAPH is not NULL, it
 277    specifies the subgraph of G whose strongly connected components we want
 278    to determine.  If SKIP_EDGE_P is not NULL, it points to a callback function.
 279    Edge E will be skipped if callback function returns true.  If SCC_GROUPING
 280    is not null, the nodes will be added to it in the following order:
 281
 282    - If SCC A is a direct or indirect predecessor of SCC B in the SCC dag,
 283      A's nodes come before B's nodes.
 284
 285    - All of an SCC's nodes are listed consecutively, although the order
 286      of the nodes within an SCC is not really meaningful.
 287
 288    After running this function, v->component is the number of the strongly
 289    connected component for each vertex of G.  Returns the number of the
 290    sccs of G.  */
 291
 292 int
 293 graphds_scc (struct graph *g, bitmap subgraph,
 294              skip_edge_callback skip_edge_p, vec<int> *scc_grouping)
 295 {
 296   int *queue = XNEWVEC (int, g->n_vertices);
 297   vec<int> postorder = vNULL;
 298   int nq, i, comp;
 299   unsigned v;
 300   bitmap_iterator bi;
 301
 302   if (subgraph)
 303     {
 304       nq = 0;
 305       EXECUTE_IF_SET_IN_BITMAP (subgraph, 0, v, bi)
 306         {
 307           queue[nq++] = v;
 308         }
 309     }
 310   else
 311     {
 312       for (i = 0; i < g->n_vertices; i++)
 313         queue[i] = i;
 314       nq = g->n_vertices;
 315     }
 316
 317   graphds_dfs (g, queue, nq, &postorder, false, subgraph, skip_edge_p);
 318   gcc_assert (postorder.length () == (unsigned) nq);
 319
 320   for (i = 0; i < nq; i++)
 321     queue[i] = postorder[nq - i - 1];
 322   comp = graphds_dfs (g, queue, nq, scc_grouping, true, subgraph, skip_edge_p);
 323
 324   free (queue);
 325   postorder.release ();
 326
 327   return comp;
 328 }
 329
 330 /* Runs CALLBACK for all edges in G.  DATA is private data for CALLBACK.  */
 331
 332 void
 333 for_each_edge (struct graph *g, graphds_edge_callback callback, void *data)
 334 {
 335   struct graph_edge *e;
 336   int i;
 337
 338   for (i = 0; i < g->n_vertices; i++)
 339     for (e = g->vertices[i].succ; e; e = e->succ_next)
 340       callback (g, e, data);
 341 }
 342
 343 /* Releases the memory occupied by G.  */
 344
 345 void
 346 free_graph (struct graph *g)
 347 {
 348   obstack_free (&g->ob, NULL);
 349   free (g);
 350 }
 351
 352 /* Returns the nearest common ancestor of X and Y in tree whose parent
 353    links are given by PARENT.  MARKS is the array used to mark the
 354    vertices of the tree, and MARK is the number currently used as a mark.  */
 355
 356 static int
 357 tree_nca (int x, int y, int *parent, int *marks, int mark)
 358 {
 359   if (x == -1 || x == y)
 360     return y;
 361
 362   /* We climb with X and Y up the tree, marking the visited nodes.  When
 363      we first arrive to a marked node, it is the common ancestor.  */
 364   marks[x] = mark;
 365   marks[y] = mark;
 366
 367   while (1)
 368     {
 369       x = parent[x];
 370       if (x == -1)
 371         break;
 372       if (marks[x] == mark)
 373         return x;
 374       marks[x] = mark;
 375
 376       y = parent[y];
 377       if (y == -1)
 378         break;
 379       if (marks[y] == mark)
 380         return y;
 381       marks[y] = mark;
 382     }
 383
 384   /* If we reached the root with one of the vertices, continue
 385      with the other one till we reach the marked part of the
 386      tree.  */
 387   if (x == -1)
 388     {
 389       for (y = parent[y]; marks[y] != mark; y = parent[y])
 390         continue;
 391
 392       return y;
 393     }
 394   else
 395     {
 396       for (x = parent[x]; marks[x] != mark; x = parent[x])
 397         continue;
 398
 399       return x;
 400     }
 401 }
 402
 403 /* Determines the dominance tree of G (stored in the PARENT, SON and BROTHER
 404    arrays), where the entry node is ENTRY.  */
 405
 406 void
 407 graphds_domtree (struct graph *g, int entry,
 408                  int *parent, int *son, int *brother)
 409 {
 410   vec<int> postorder = vNULL;
 411   int *marks = XCNEWVEC (int, g->n_vertices);
 412   int mark = 1, i, v, idom;
 413   bool changed = true;
 414   struct graph_edge *e;
 415
 416   /* We use a slight modification of the standard iterative algorithm, as
 417      described in
 418
 419      K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance
 420         Algorithm
 421
 422      sort vertices in reverse postorder
 423      foreach v
 424        dom(v) = everything
 425      dom(entry) = entry;
 426
 427      while (anything changes)
 428        foreach v
 429          dom(v) = {v} union (intersection of dom(p) over all predecessors of v)
 430
 431      The sets dom(v) are represented by the parent links in the current version
 432      of the dominance tree.  */
 433
 434   for (i = 0; i < g->n_vertices; i++)
 435     {
 436       parent[i] = -1;
 437       son[i] = -1;
 438       brother[i] = -1;
 439     }
 440   graphds_dfs (g, &entry, 1, &postorder, true, NULL);
 441   gcc_assert (postorder.length () == (unsigned) g->n_vertices);
 442   gcc_assert (postorder[g->n_vertices - 1] == entry);
 443
 444   while (changed)
 445     {
 446       changed = false;
 447
 448       for (i = g->n_vertices - 2; i >= 0; i--)
 449         {
 450           v = postorder[i];
 451           idom = -1;
 452           for (e = g->vertices[v].pred; e; e = e->pred_next)
 453             {
 454               if (e->src != entry
 455                   && parent[e->src] == -1)
 456                 continue;
 457
 458               idom = tree_nca (idom, e->src, parent, marks, mark++);
 459             }
 460
 461           if (idom != parent[v])
 462             {
 463               parent[v] = idom;
 464               changed = true;
 465             }
 466         }
 467     }
 468
 469   free (marks);
 470   postorder.release ();
 471
 472   for (i = 0; i < g->n_vertices; i++)
 473     if (parent[i] != -1)
 474       {
 475         brother[i] = son[parent[i]];
 476         son[parent[i]] = i;
 477       }
 478 }