1/* Graph representation and manipulation functions. 2 Copyright (C) 2007-2015 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify it under 7the terms of the GNU General Public License as published by the Free 8Software Foundation; either version 3, or (at your option) any later 9version. 10 11GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12WARRANTY; without even the implied warranty of MERCHANTABILITY or 13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14for more details. 15 16You should have received a copy of the GNU General Public License 17along 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 30void 31dump_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 56struct graph * 57new_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 71struct graph_edge * 72add_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 91void 92identify_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 122static inline int 123dfs_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 131static inline int 132dfs_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 140static inline struct graph_edge * 141foll_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 163static inline struct graph_edge * 164dfs_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 175static inline struct graph_edge * 176dfs_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 188int 189graphds_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 273int 274graphds_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 312void 313for_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 325void 326free_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 336static int 337tree_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 386void 387graphds_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} 459