gcc/graphds.c

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