Mercurial > hg > CbC > CbC_gcc
annotate gcc/graphds.c @ 158:494b0b89df80 default tip
...
| author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Mon, 25 May 2020 18:13:55 +0900 |
| parents | 1830386684a0 |
| children |
| rev | line source |
|---|---|
| 0 | 1 /* Graph representation and manipulation functions. |
| 145 | 2 Copyright (C) 2007-2020 Free Software Foundation, Inc. |
| 0 | 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 | |
| 111 | 59 gcc_obstack_init (&g->ob); |
| 0 | 60 g->n_vertices = n_vertices; |
| 111 | 61 g->vertices = XOBNEWVEC (&g->ob, struct vertex, n_vertices); |
| 62 memset (g->vertices, 0, sizeof (struct vertex) * n_vertices); | |
| 0 | 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 { | |
| 111 | 72 struct graph_edge *e = XOBNEW (&g->ob, struct graph_edge); |
| 0 | 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 | |
| 111 | 84 e->data = NULL; |
| 0 | 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 | |
| 111 | 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. */ | |
| 0 | 140 |
| 141 static inline struct graph_edge * | |
| 111 | 142 foll_in_subgraph (struct graph_edge *e, bool forward, bitmap subgraph, |
| 143 skip_edge_callback skip_edge_p) | |
| 0 | 144 { |
| 145 int d; | |
| 146 | |
| 111 | 147 if (!e) |
| 148 return e; | |
| 149 | |
| 150 if (!subgraph && (!skip_edge_p || !skip_edge_p (e))) | |
| 0 | 151 return e; |
| 152 | |
| 153 while (e) | |
| 154 { | |
| 155 d = dfs_edge_dest (e, forward); | |
| 111 | 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))) | |
| 0 | 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 | |
| 111 | 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. */ | |
| 0 | 171 |
| 172 static inline struct graph_edge * | |
| 111 | 173 dfs_fst_edge (struct graph *g, int v, bool forward, bitmap subgraph, |
| 174 skip_edge_callback skip_edge_p) | |
| 0 | 175 { |
| 176 struct graph_edge *e; | |
| 177 | |
| 178 e = (forward ? g->vertices[v].succ : g->vertices[v].pred); | |
| 111 | 179 return foll_in_subgraph (e, forward, subgraph, skip_edge_p); |
| 0 | 180 } |
| 181 | |
| 182 /* Helper function for graphds_dfs. Returns the next edge after E, in the | |
| 111 | 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. */ | |
| 0 | 186 |
| 187 static inline struct graph_edge * | |
| 111 | 188 dfs_next_edge (struct graph_edge *e, bool forward, bitmap subgraph, |
| 189 skip_edge_callback skip_edge_p) | |
| 0 | 190 { |
| 191 return foll_in_subgraph (forward ? e->succ_next : e->pred_next, | |
| 111 | 192 forward, subgraph, skip_edge_p); |
| 0 | 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 | |
| 111 | 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. */ | |
| 0 | 202 |
| 203 int | |
| 111 | 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) | |
| 0 | 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++; | |
| 111 | 238 e = dfs_fst_edge (g, v, forward, subgraph, skip_edge_p); |
| 0 | 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; | |
| 111 | 248 e = dfs_next_edge (e, forward, subgraph, skip_edge_p); |
| 0 | 249 } |
| 250 | |
| 251 if (!e) | |
| 252 { | |
| 253 if (qt) | |
| 111 | 254 qt->safe_push (v); |
| 0 | 255 g->vertices[v].post = tick++; |
| 256 | |
| 257 if (!top) | |
| 258 break; | |
| 259 | |
| 260 e = stack[--top]; | |
| 261 v = dfs_edge_src (e, forward); | |
| 111 | 262 e = dfs_next_edge (e, forward, subgraph, skip_edge_p); |
| 0 | 263 continue; |
| 264 } | |
| 265 | |
| 266 stack[top++] = e; | |
| 267 v = dfs_edge_dest (e, forward); | |
| 111 | 268 e = dfs_fst_edge (g, v, forward, subgraph, skip_edge_p); |
| 0 | 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 | |
| 111 | 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. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
285 |
| 0 | 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 | |
| 111 | 291 graphds_scc (struct graph *g, bitmap subgraph, |
| 292 skip_edge_callback skip_edge_p) | |
| 0 | 293 { |
| 294 int *queue = XNEWVEC (int, g->n_vertices); | |
| 111 | 295 vec<int> postorder = vNULL; |
| 0 | 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 | |
| 111 | 315 graphds_dfs (g, queue, nq, &postorder, false, subgraph, skip_edge_p); |
| 316 gcc_assert (postorder.length () == (unsigned) nq); | |
| 0 | 317 |
| 318 for (i = 0; i < nq; i++) | |
| 111 | 319 queue[i] = postorder[nq - i - 1]; |
| 320 comp = graphds_dfs (g, queue, nq, NULL, true, subgraph, skip_edge_p); | |
| 0 | 321 |
| 322 free (queue); | |
| 111 | 323 postorder.release (); |
| 0 | 324 |
| 325 return comp; | |
| 326 } | |
| 327 | |
| 111 | 328 /* Runs CALLBACK for all edges in G. DATA is private data for CALLBACK. */ |
| 0 | 329 |
| 330 void | |
| 111 | 331 for_each_edge (struct graph *g, graphds_edge_callback callback, void *data) |
| 0 | 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) | |
| 111 | 338 callback (g, e, data); |
| 0 | 339 } |
| 340 | |
| 341 /* Releases the memory occupied by G. */ | |
| 342 | |
| 343 void | |
| 344 free_graph (struct graph *g) | |
| 345 { | |
| 111 | 346 obstack_free (&g->ob, NULL); |
| 0 | 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 { | |
| 111 | 408 vec<int> postorder = vNULL; |
| 0 | 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 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
416 |
| 0 | 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); | |
| 111 | 439 gcc_assert (postorder.length () == (unsigned) g->n_vertices); |
| 440 gcc_assert (postorder[g->n_vertices - 1] == entry); | |
| 0 | 441 |
| 442 while (changed) | |
| 443 { | |
| 444 changed = false; | |
| 445 | |
| 446 for (i = g->n_vertices - 2; i >= 0; i--) | |
| 447 { | |
| 111 | 448 v = postorder[i]; |
| 0 | 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); | |
| 111 | 468 postorder.release (); |
| 0 | 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 } |