gcc/graphds.c

   1 /* Graph representation and manipulation functions.
   2    Copyright (C) 2007, 2012
   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 "graphds.h"
  28
  29 /* Dumps graph G into F.  */
  30
  31 void
  32 dump_graph (FILE *f, struct graph *g)
  33 {
  34   int i;
  35   struct graph_edge *e;
  36
  37   for (i = 0; i < g->n_vertices; i++)
  38     {
  39       if (!g->vertices[i].pred
  40           && !g->vertices[i].succ)
  41         continue;
  42
  43       fprintf (f, "%d (%d)\t<-", i, g->vertices[i].component);
  44       for (e = g->vertices[i].pred; e; e = e->pred_next)
  45         fprintf (f, " %d", e->src);
  46       fprintf (f, "\n");
  47
  48       fprintf (f, "\t->");
  49       for (e = g->vertices[i].succ; e; e = e->succ_next)
  50         fprintf (f, " %d", e->dest);
  51       fprintf (f, "\n");
  52     }
  53 }
  54
  55 /* Creates a new graph with N_VERTICES vertices.  */
  56
  57 struct graph *
  58 new_graph (int n_vertices)
  59 {
  60   struct graph *g = XNEW (struct graph);
  61
  62   g->n_vertices = n_vertices;
  63   g->vertices = XCNEWVEC (struct vertex, n_vertices);
  64
  65   return g;
  66 }
  67
  68 /* Adds an edge from F to T to graph G.  The new edge is returned.  */
  69
  70 struct graph_edge *
  71 add_edge (struct graph *g, int f, int t)
  72 {
  73   struct graph_edge *e = XNEW (struct graph_edge);
  74   struct vertex *vf = &g->vertices[f], *vt = &g->vertices[t];
  75
  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   struct graph_edge *e, *n;
 329   struct vertex *v;
 330   int i;
 331
 332   for (i = 0; i < g->n_vertices; i++)
 333     {
 334       v = &g->vertices[i];
 335       for (e = v->succ; e; e = n)
 336         {
 337           n = e->succ_next;
 338           free (e);
 339         }
 340     }
 341   free (g->vertices);
 342   free (g);
 343 }
 344
 345 /* Returns the nearest common ancestor of X and Y in tree whose parent
 346    links are given by PARENT.  MARKS is the array used to mark the
 347    vertices of the tree, and MARK is the number currently used as a mark.  */
 348
 349 static int
 350 tree_nca (int x, int y, int *parent, int *marks, int mark)
 351 {
 352   if (x == -1 || x == y)
 353     return y;
 354
 355   /* We climb with X and Y up the tree, marking the visited nodes.  When
 356      we first arrive to a marked node, it is the common ancestor.  */
 357   marks[x] = mark;
 358   marks[y] = mark;
 359
 360   while (1)
 361     {
 362       x = parent[x];
 363       if (x == -1)
 364         break;
 365       if (marks[x] == mark)
 366         return x;
 367       marks[x] = mark;
 368
 369       y = parent[y];
 370       if (y == -1)
 371         break;
 372       if (marks[y] == mark)
 373         return y;
 374       marks[y] = mark;
 375     }
 376
 377   /* If we reached the root with one of the vertices, continue
 378      with the other one till we reach the marked part of the
 379      tree.  */
 380   if (x == -1)
 381     {
 382       for (y = parent[y]; marks[y] != mark; y = parent[y])
 383         continue;
 384
 385       return y;
 386     }
 387   else
 388     {
 389       for (x = parent[x]; marks[x] != mark; x = parent[x])
 390         continue;
 391
 392       return x;
 393     }
 394 }
 395
 396 /* Determines the dominance tree of G (stored in the PARENT, SON and BROTHER
 397    arrays), where the entry node is ENTRY.  */
 398
 399 void
 400 graphds_domtree (struct graph *g, int entry,
 401                  int *parent, int *son, int *brother)
 402 {
 403   vec<int> postorder = vNULL;
 404   int *marks = XCNEWVEC (int, g->n_vertices);
 405   int mark = 1, i, v, idom;
 406   bool changed = true;
 407   struct graph_edge *e;
 408
 409   /* We use a slight modification of the standard iterative algorithm, as
 410      described in
 411
 412      K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance
 413         Algorithm
 414
 415      sort vertices in reverse postorder
 416      foreach v
 417        dom(v) = everything
 418      dom(entry) = entry;
 419
 420      while (anything changes)
 421        foreach v
 422          dom(v) = {v} union (intersection of dom(p) over all predecessors of v)
 423
 424      The sets dom(v) are represented by the parent links in the current version
 425      of the dominance tree.  */
 426
 427   for (i = 0; i < g->n_vertices; i++)
 428     {
 429       parent[i] = -1;
 430       son[i] = -1;
 431       brother[i] = -1;
 432     }
 433   graphds_dfs (g, &entry, 1, &postorder, true, NULL);
 434   gcc_assert (postorder.length () == (unsigned) g->n_vertices);
 435   gcc_assert (postorder[g->n_vertices - 1] == entry);
 436
 437   while (changed)
 438     {
 439       changed = false;
 440
 441       for (i = g->n_vertices - 2; i >= 0; i--)
 442         {
 443           v = postorder[i];
 444           idom = -1;
 445           for (e = g->vertices[v].pred; e; e = e->pred_next)
 446             {
 447               if (e->src != entry
 448                   && parent[e->src] == -1)
 449                 continue;
 450
 451               idom = tree_nca (idom, e->src, parent, marks, mark++);
 452             }
 453
 454           if (idom != parent[v])
 455             {
 456               parent[v] = idom;
 457               changed = true;
 458             }
 459         }
 460     }
 461
 462   free (marks);
 463   postorder.release ();
 464
 465   for (i = 0; i < g->n_vertices; i++)
 466     if (parent[i] != -1)
 467       {
 468         brother[i] = son[parent[i]];
 469         son[parent[i]] = i;
 470       }
 471 }