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