gcc/graphds.cc

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