gcc/graphds.c

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