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