gcc/graphds.c

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