gcc/graphds.c

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