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