gcc/graphds.c

   1 /* Graph representation and manipulation functions.
   2    Copyright (C) 2007-2019 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    Tarjan -- 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.
 285
 286    After running this function, v->component is the number of the strongly
 287    connected component for each vertex of G.  Returns the number of the
 288    sccs of G.  */
 289
 290 int
 291 graphds_scc (struct graph *g, bitmap subgraph,
 292              skip_edge_callback skip_edge_p)
 293 {
 294   int *queue = XNEWVEC (int, g->n_vertices);
 295   vec<int> postorder = vNULL;
 296   int nq, i, comp;
 297   unsigned v;
 298   bitmap_iterator bi;
 299
 300   if (subgraph)
 301     {
 302       nq = 0;
 303       EXECUTE_IF_SET_IN_BITMAP (subgraph, 0, v, bi)
 304         {
 305           queue[nq++] = v;
 306         }
 307     }
 308   else
 309     {
 310       for (i = 0; i < g->n_vertices; i++)
 311         queue[i] = i;
 312       nq = g->n_vertices;
 313     }
 314
 315   graphds_dfs (g, queue, nq, &postorder, false, subgraph, skip_edge_p);
 316   gcc_assert (postorder.length () == (unsigned) nq);
 317
 318   for (i = 0; i < nq; i++)
 319     queue[i] = postorder[nq - i - 1];
 320   comp = graphds_dfs (g, queue, nq, NULL, true, subgraph, skip_edge_p);
 321
 322   free (queue);
 323   postorder.release ();
 324
 325   return comp;
 326 }
 327
 328 /* Runs CALLBACK for all edges in G.  DATA is private data for CALLBACK.  */
 329
 330 void
 331 for_each_edge (struct graph *g, graphds_edge_callback callback, void *data)
 332 {
 333   struct graph_edge *e;
 334   int i;
 335
 336   for (i = 0; i < g->n_vertices; i++)
 337     for (e = g->vertices[i].succ; e; e = e->succ_next)
 338       callback (g, e, data);
 339 }
 340
 341 /* Releases the memory occupied by G.  */
 342
 343 void
 344 free_graph (struct graph *g)
 345 {
 346   obstack_free (&g->ob, NULL);
 347   free (g);
 348 }
 349
 350 /* Returns the nearest common ancestor of X and Y in tree whose parent
 351    links are given by PARENT.  MARKS is the array used to mark the
 352    vertices of the tree, and MARK is the number currently used as a mark.  */
 353
 354 static int
 355 tree_nca (int x, int y, int *parent, int *marks, int mark)
 356 {
 357   if (x == -1 || x == y)
 358     return y;
 359
 360   /* We climb with X and Y up the tree, marking the visited nodes.  When
 361      we first arrive to a marked node, it is the common ancestor.  */
 362   marks[x] = mark;
 363   marks[y] = mark;
 364
 365   while (1)
 366     {
 367       x = parent[x];
 368       if (x == -1)
 369         break;
 370       if (marks[x] == mark)
 371         return x;
 372       marks[x] = mark;
 373
 374       y = parent[y];
 375       if (y == -1)
 376         break;
 377       if (marks[y] == mark)
 378         return y;
 379       marks[y] = mark;
 380     }
 381
 382   /* If we reached the root with one of the vertices, continue
 383      with the other one till we reach the marked part of the
 384      tree.  */
 385   if (x == -1)
 386     {
 387       for (y = parent[y]; marks[y] != mark; y = parent[y])
 388         continue;
 389
 390       return y;
 391     }
 392   else
 393     {
 394       for (x = parent[x]; marks[x] != mark; x = parent[x])
 395         continue;
 396
 397       return x;
 398     }
 399 }
 400
 401 /* Determines the dominance tree of G (stored in the PARENT, SON and BROTHER
 402    arrays), where the entry node is ENTRY.  */
 403
 404 void
 405 graphds_domtree (struct graph *g, int entry,
 406                  int *parent, int *son, int *brother)
 407 {
 408   vec<int> postorder = vNULL;
 409   int *marks = XCNEWVEC (int, g->n_vertices);
 410   int mark = 1, i, v, idom;
 411   bool changed = true;
 412   struct graph_edge *e;
 413
 414   /* We use a slight modification of the standard iterative algorithm, as
 415      described in
 416
 417      K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance
 418         Algorithm
 419
 420      sort vertices in reverse postorder
 421      foreach v
 422        dom(v) = everything
 423      dom(entry) = entry;
 424
 425      while (anything changes)
 426        foreach v
 427          dom(v) = {v} union (intersection of dom(p) over all predecessors of v)
 428
 429      The sets dom(v) are represented by the parent links in the current version
 430      of the dominance tree.  */
 431
 432   for (i = 0; i < g->n_vertices; i++)
 433     {
 434       parent[i] = -1;
 435       son[i] = -1;
 436       brother[i] = -1;
 437     }
 438   graphds_dfs (g, &entry, 1, &postorder, true, NULL);
 439   gcc_assert (postorder.length () == (unsigned) g->n_vertices);
 440   gcc_assert (postorder[g->n_vertices - 1] == entry);
 441
 442   while (changed)
 443     {
 444       changed = false;
 445
 446       for (i = g->n_vertices - 2; i >= 0; i--)
 447         {
 448           v = postorder[i];
 449           idom = -1;
 450           for (e = g->vertices[v].pred; e; e = e->pred_next)
 451             {
 452               if (e->src != entry
 453                   && parent[e->src] == -1)
 454                 continue;
 455
 456               idom = tree_nca (idom, e->src, parent, marks, mark++);
 457             }
 458
 459           if (idom != parent[v])
 460             {
 461               parent[v] = idom;
 462               changed = true;
 463             }
 464         }
 465     }
 466
 467   free (marks);
 468   postorder.release ();
 469
 470   for (i = 0; i < g->n_vertices; i++)
 471     if (parent[i] != -1)
 472       {
 473         brother[i] = son[parent[i]];
 474         son[parent[i]] = i;
 475       }
 476 }