Mercurial > hg > CbC > CbC_gcc
annotate gcc/dominance.c @ 67:f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
| author | nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Tue, 22 Mar 2011 17:18:12 +0900 |
| parents | b7f97abdc517 |
| children | 04ced10e8804 |
| rev | line source |
|---|---|
| 0 | 1 /* Calculate (post)dominators in slightly super-linear time. |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
2 Copyright (C) 2000, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
3 Free Software Foundation, Inc. |
| 0 | 4 Contributed by Michael Matz (matz@ifh.de). |
| 5 | |
| 6 This file is part of GCC. | |
| 7 | |
| 8 GCC is free software; you can redistribute it and/or modify it | |
| 9 under the terms of the GNU General Public License as published by | |
| 10 the Free Software Foundation; either version 3, or (at your option) | |
| 11 any later version. | |
| 12 | |
| 13 GCC is distributed in the hope that it will be useful, but WITHOUT | |
| 14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY | |
| 15 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public | |
| 16 License for more details. | |
| 17 | |
| 18 You should have received a copy of the GNU General Public License | |
| 19 along with GCC; see the file COPYING3. If not see | |
| 20 <http://www.gnu.org/licenses/>. */ | |
| 21 | |
| 22 /* This file implements the well known algorithm from Lengauer and Tarjan | |
| 23 to compute the dominators in a control flow graph. A basic block D is said | |
| 24 to dominate another block X, when all paths from the entry node of the CFG | |
| 25 to X go also over D. The dominance relation is a transitive reflexive | |
| 26 relation and its minimal transitive reduction is a tree, called the | |
| 27 dominator tree. So for each block X besides the entry block exists a | |
| 28 block I(X), called the immediate dominator of X, which is the parent of X | |
| 29 in the dominator tree. | |
| 30 | |
| 31 The algorithm computes this dominator tree implicitly by computing for | |
| 32 each block its immediate dominator. We use tree balancing and path | |
| 33 compression, so it's the O(e*a(e,v)) variant, where a(e,v) is the very | |
| 34 slowly growing functional inverse of the Ackerman function. */ | |
| 35 | |
| 36 #include "config.h" | |
| 37 #include "system.h" | |
| 38 #include "coretypes.h" | |
| 39 #include "tm.h" | |
| 40 #include "rtl.h" | |
| 41 #include "hard-reg-set.h" | |
| 42 #include "obstack.h" | |
| 43 #include "basic-block.h" | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
44 #include "diagnostic-core.h" |
| 0 | 45 #include "et-forest.h" |
| 46 #include "timevar.h" | |
| 47 #include "vecprim.h" | |
| 48 #include "pointer-set.h" | |
| 49 #include "graphds.h" | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
50 #include "bitmap.h" |
| 0 | 51 |
| 52 /* We name our nodes with integers, beginning with 1. Zero is reserved for | |
| 53 'undefined' or 'end of list'. The name of each node is given by the dfs | |
| 54 number of the corresponding basic block. Please note, that we include the | |
| 55 artificial ENTRY_BLOCK (or EXIT_BLOCK in the post-dom case) in our lists to | |
| 56 support multiple entry points. Its dfs number is of course 1. */ | |
| 57 | |
| 58 /* Type of Basic Block aka. TBB */ | |
| 59 typedef unsigned int TBB; | |
| 60 | |
| 61 /* We work in a poor-mans object oriented fashion, and carry an instance of | |
| 62 this structure through all our 'methods'. It holds various arrays | |
| 63 reflecting the (sub)structure of the flowgraph. Most of them are of type | |
| 64 TBB and are also indexed by TBB. */ | |
| 65 | |
| 66 struct dom_info | |
| 67 { | |
| 68 /* The parent of a node in the DFS tree. */ | |
| 69 TBB *dfs_parent; | |
| 70 /* For a node x key[x] is roughly the node nearest to the root from which | |
| 71 exists a way to x only over nodes behind x. Such a node is also called | |
| 72 semidominator. */ | |
| 73 TBB *key; | |
| 74 /* The value in path_min[x] is the node y on the path from x to the root of | |
| 75 the tree x is in with the smallest key[y]. */ | |
| 76 TBB *path_min; | |
| 77 /* bucket[x] points to the first node of the set of nodes having x as key. */ | |
| 78 TBB *bucket; | |
| 79 /* And next_bucket[x] points to the next node. */ | |
| 80 TBB *next_bucket; | |
| 81 /* After the algorithm is done, dom[x] contains the immediate dominator | |
| 82 of x. */ | |
| 83 TBB *dom; | |
| 84 | |
| 85 /* The following few fields implement the structures needed for disjoint | |
| 86 sets. */ | |
| 87 /* set_chain[x] is the next node on the path from x to the representative | |
| 88 of the set containing x. If set_chain[x]==0 then x is a root. */ | |
| 89 TBB *set_chain; | |
| 90 /* set_size[x] is the number of elements in the set named by x. */ | |
| 91 unsigned int *set_size; | |
| 92 /* set_child[x] is used for balancing the tree representing a set. It can | |
| 93 be understood as the next sibling of x. */ | |
| 94 TBB *set_child; | |
| 95 | |
| 96 /* If b is the number of a basic block (BB->index), dfs_order[b] is the | |
| 97 number of that node in DFS order counted from 1. This is an index | |
| 98 into most of the other arrays in this structure. */ | |
| 99 TBB *dfs_order; | |
| 100 /* If x is the DFS-index of a node which corresponds with a basic block, | |
| 101 dfs_to_bb[x] is that basic block. Note, that in our structure there are | |
| 102 more nodes that basic blocks, so only dfs_to_bb[dfs_order[bb->index]]==bb | |
| 103 is true for every basic block bb, but not the opposite. */ | |
| 104 basic_block *dfs_to_bb; | |
| 105 | |
| 106 /* This is the next free DFS number when creating the DFS tree. */ | |
| 107 unsigned int dfsnum; | |
| 108 /* The number of nodes in the DFS tree (==dfsnum-1). */ | |
| 109 unsigned int nodes; | |
| 110 | |
| 111 /* Blocks with bits set here have a fake edge to EXIT. These are used | |
| 112 to turn a DFS forest into a proper tree. */ | |
| 113 bitmap fake_exit_edge; | |
| 114 }; | |
| 115 | |
| 116 static void init_dom_info (struct dom_info *, enum cdi_direction); | |
| 117 static void free_dom_info (struct dom_info *); | |
| 118 static void calc_dfs_tree_nonrec (struct dom_info *, basic_block, bool); | |
| 119 static void calc_dfs_tree (struct dom_info *, bool); | |
| 120 static void compress (struct dom_info *, TBB); | |
| 121 static TBB eval (struct dom_info *, TBB); | |
| 122 static void link_roots (struct dom_info *, TBB, TBB); | |
| 123 static void calc_idoms (struct dom_info *, bool); | |
| 124 void debug_dominance_info (enum cdi_direction); | |
| 125 void debug_dominance_tree (enum cdi_direction, basic_block); | |
| 126 | |
| 127 /* Helper macro for allocating and initializing an array, | |
| 128 for aesthetic reasons. */ | |
| 129 #define init_ar(var, type, num, content) \ | |
| 130 do \ | |
| 131 { \ | |
| 132 unsigned int i = 1; /* Catch content == i. */ \ | |
| 133 if (! (content)) \ | |
| 134 (var) = XCNEWVEC (type, num); \ | |
| 135 else \ | |
| 136 { \ | |
| 137 (var) = XNEWVEC (type, (num)); \ | |
| 138 for (i = 0; i < num; i++) \ | |
| 139 (var)[i] = (content); \ | |
| 140 } \ | |
| 141 } \ | |
| 142 while (0) | |
| 143 | |
| 144 /* Allocate all needed memory in a pessimistic fashion (so we round up). | |
| 145 This initializes the contents of DI, which already must be allocated. */ | |
| 146 | |
| 147 static void | |
| 148 init_dom_info (struct dom_info *di, enum cdi_direction dir) | |
| 149 { | |
| 150 /* We need memory for n_basic_blocks nodes. */ | |
| 151 unsigned int num = n_basic_blocks; | |
| 152 init_ar (di->dfs_parent, TBB, num, 0); | |
| 153 init_ar (di->path_min, TBB, num, i); | |
| 154 init_ar (di->key, TBB, num, i); | |
| 155 init_ar (di->dom, TBB, num, 0); | |
| 156 | |
| 157 init_ar (di->bucket, TBB, num, 0); | |
| 158 init_ar (di->next_bucket, TBB, num, 0); | |
| 159 | |
| 160 init_ar (di->set_chain, TBB, num, 0); | |
| 161 init_ar (di->set_size, unsigned int, num, 1); | |
| 162 init_ar (di->set_child, TBB, num, 0); | |
| 163 | |
| 164 init_ar (di->dfs_order, TBB, (unsigned int) last_basic_block + 1, 0); | |
| 165 init_ar (di->dfs_to_bb, basic_block, num, 0); | |
| 166 | |
| 167 di->dfsnum = 1; | |
| 168 di->nodes = 0; | |
| 169 | |
| 170 switch (dir) | |
| 171 { | |
| 172 case CDI_DOMINATORS: | |
| 173 di->fake_exit_edge = NULL; | |
| 174 break; | |
| 175 case CDI_POST_DOMINATORS: | |
| 176 di->fake_exit_edge = BITMAP_ALLOC (NULL); | |
| 177 break; | |
| 178 default: | |
| 179 gcc_unreachable (); | |
| 180 break; | |
| 181 } | |
| 182 } | |
| 183 | |
| 184 #undef init_ar | |
| 185 | |
| 186 /* Map dominance calculation type to array index used for various | |
| 187 dominance information arrays. This version is simple -- it will need | |
| 188 to be modified, obviously, if additional values are added to | |
| 189 cdi_direction. */ | |
| 190 | |
| 191 static unsigned int | |
| 192 dom_convert_dir_to_idx (enum cdi_direction dir) | |
| 193 { | |
| 194 gcc_assert (dir == CDI_DOMINATORS || dir == CDI_POST_DOMINATORS); | |
| 195 return dir - 1; | |
| 196 } | |
| 197 | |
| 198 /* Free all allocated memory in DI, but not DI itself. */ | |
| 199 | |
| 200 static void | |
| 201 free_dom_info (struct dom_info *di) | |
| 202 { | |
| 203 free (di->dfs_parent); | |
| 204 free (di->path_min); | |
| 205 free (di->key); | |
| 206 free (di->dom); | |
| 207 free (di->bucket); | |
| 208 free (di->next_bucket); | |
| 209 free (di->set_chain); | |
| 210 free (di->set_size); | |
| 211 free (di->set_child); | |
| 212 free (di->dfs_order); | |
| 213 free (di->dfs_to_bb); | |
| 214 BITMAP_FREE (di->fake_exit_edge); | |
| 215 } | |
| 216 | |
| 217 /* The nonrecursive variant of creating a DFS tree. DI is our working | |
| 218 structure, BB the starting basic block for this tree and REVERSE | |
| 219 is true, if predecessors should be visited instead of successors of a | |
| 220 node. After this is done all nodes reachable from BB were visited, have | |
| 221 assigned their dfs number and are linked together to form a tree. */ | |
| 222 | |
| 223 static void | |
| 224 calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb, bool reverse) | |
| 225 { | |
| 226 /* We call this _only_ if bb is not already visited. */ | |
| 227 edge e; | |
| 228 TBB child_i, my_i = 0; | |
| 229 edge_iterator *stack; | |
| 230 edge_iterator ei, einext; | |
| 231 int sp; | |
| 232 /* Start block (ENTRY_BLOCK_PTR for forward problem, EXIT_BLOCK for backward | |
| 233 problem). */ | |
| 234 basic_block en_block; | |
| 235 /* Ending block. */ | |
| 236 basic_block ex_block; | |
| 237 | |
| 238 stack = XNEWVEC (edge_iterator, n_basic_blocks + 1); | |
| 239 sp = 0; | |
| 240 | |
| 241 /* Initialize our border blocks, and the first edge. */ | |
| 242 if (reverse) | |
| 243 { | |
| 244 ei = ei_start (bb->preds); | |
| 245 en_block = EXIT_BLOCK_PTR; | |
| 246 ex_block = ENTRY_BLOCK_PTR; | |
| 247 } | |
| 248 else | |
| 249 { | |
| 250 ei = ei_start (bb->succs); | |
| 251 en_block = ENTRY_BLOCK_PTR; | |
| 252 ex_block = EXIT_BLOCK_PTR; | |
| 253 } | |
| 254 | |
| 255 /* When the stack is empty we break out of this loop. */ | |
| 256 while (1) | |
| 257 { | |
| 258 basic_block bn; | |
| 259 | |
| 260 /* This loop traverses edges e in depth first manner, and fills the | |
| 261 stack. */ | |
| 262 while (!ei_end_p (ei)) | |
| 263 { | |
| 264 e = ei_edge (ei); | |
| 265 | |
| 266 /* Deduce from E the current and the next block (BB and BN), and the | |
| 267 next edge. */ | |
| 268 if (reverse) | |
| 269 { | |
| 270 bn = e->src; | |
| 271 | |
| 272 /* If the next node BN is either already visited or a border | |
| 273 block the current edge is useless, and simply overwritten | |
| 274 with the next edge out of the current node. */ | |
| 275 if (bn == ex_block || di->dfs_order[bn->index]) | |
| 276 { | |
| 277 ei_next (&ei); | |
| 278 continue; | |
| 279 } | |
| 280 bb = e->dest; | |
| 281 einext = ei_start (bn->preds); | |
| 282 } | |
| 283 else | |
| 284 { | |
| 285 bn = e->dest; | |
| 286 if (bn == ex_block || di->dfs_order[bn->index]) | |
| 287 { | |
| 288 ei_next (&ei); | |
| 289 continue; | |
| 290 } | |
| 291 bb = e->src; | |
| 292 einext = ei_start (bn->succs); | |
| 293 } | |
| 294 | |
| 295 gcc_assert (bn != en_block); | |
| 296 | |
| 297 /* Fill the DFS tree info calculatable _before_ recursing. */ | |
| 298 if (bb != en_block) | |
| 299 my_i = di->dfs_order[bb->index]; | |
| 300 else | |
| 301 my_i = di->dfs_order[last_basic_block]; | |
| 302 child_i = di->dfs_order[bn->index] = di->dfsnum++; | |
| 303 di->dfs_to_bb[child_i] = bn; | |
| 304 di->dfs_parent[child_i] = my_i; | |
| 305 | |
| 306 /* Save the current point in the CFG on the stack, and recurse. */ | |
| 307 stack[sp++] = ei; | |
| 308 ei = einext; | |
| 309 } | |
| 310 | |
| 311 if (!sp) | |
| 312 break; | |
| 313 ei = stack[--sp]; | |
| 314 | |
| 315 /* OK. The edge-list was exhausted, meaning normally we would | |
| 316 end the recursion. After returning from the recursive call, | |
| 317 there were (may be) other statements which were run after a | |
| 318 child node was completely considered by DFS. Here is the | |
| 319 point to do it in the non-recursive variant. | |
| 320 E.g. The block just completed is in e->dest for forward DFS, | |
| 321 the block not yet completed (the parent of the one above) | |
| 322 in e->src. This could be used e.g. for computing the number of | |
| 323 descendants or the tree depth. */ | |
| 324 ei_next (&ei); | |
| 325 } | |
| 326 free (stack); | |
| 327 } | |
| 328 | |
| 329 /* The main entry for calculating the DFS tree or forest. DI is our working | |
| 330 structure and REVERSE is true, if we are interested in the reverse flow | |
| 331 graph. In that case the result is not necessarily a tree but a forest, | |
| 332 because there may be nodes from which the EXIT_BLOCK is unreachable. */ | |
| 333 | |
| 334 static void | |
| 335 calc_dfs_tree (struct dom_info *di, bool reverse) | |
| 336 { | |
| 337 /* The first block is the ENTRY_BLOCK (or EXIT_BLOCK if REVERSE). */ | |
| 338 basic_block begin = reverse ? EXIT_BLOCK_PTR : ENTRY_BLOCK_PTR; | |
| 339 di->dfs_order[last_basic_block] = di->dfsnum; | |
| 340 di->dfs_to_bb[di->dfsnum] = begin; | |
| 341 di->dfsnum++; | |
| 342 | |
| 343 calc_dfs_tree_nonrec (di, begin, reverse); | |
| 344 | |
| 345 if (reverse) | |
| 346 { | |
| 347 /* In the post-dom case we may have nodes without a path to EXIT_BLOCK. | |
| 348 They are reverse-unreachable. In the dom-case we disallow such | |
| 349 nodes, but in post-dom we have to deal with them. | |
| 350 | |
| 351 There are two situations in which this occurs. First, noreturn | |
| 352 functions. Second, infinite loops. In the first case we need to | |
| 353 pretend that there is an edge to the exit block. In the second | |
| 354 case, we wind up with a forest. We need to process all noreturn | |
| 355 blocks before we know if we've got any infinite loops. */ | |
| 356 | |
| 357 basic_block b; | |
| 358 bool saw_unconnected = false; | |
| 359 | |
| 360 FOR_EACH_BB_REVERSE (b) | |
| 361 { | |
| 362 if (EDGE_COUNT (b->succs) > 0) | |
| 363 { | |
| 364 if (di->dfs_order[b->index] == 0) | |
| 365 saw_unconnected = true; | |
| 366 continue; | |
| 367 } | |
| 368 bitmap_set_bit (di->fake_exit_edge, b->index); | |
| 369 di->dfs_order[b->index] = di->dfsnum; | |
| 370 di->dfs_to_bb[di->dfsnum] = b; | |
| 371 di->dfs_parent[di->dfsnum] = di->dfs_order[last_basic_block]; | |
| 372 di->dfsnum++; | |
| 373 calc_dfs_tree_nonrec (di, b, reverse); | |
| 374 } | |
| 375 | |
| 376 if (saw_unconnected) | |
| 377 { | |
| 378 FOR_EACH_BB_REVERSE (b) | |
| 379 { | |
| 380 if (di->dfs_order[b->index]) | |
| 381 continue; | |
| 382 bitmap_set_bit (di->fake_exit_edge, b->index); | |
| 383 di->dfs_order[b->index] = di->dfsnum; | |
| 384 di->dfs_to_bb[di->dfsnum] = b; | |
| 385 di->dfs_parent[di->dfsnum] = di->dfs_order[last_basic_block]; | |
| 386 di->dfsnum++; | |
| 387 calc_dfs_tree_nonrec (di, b, reverse); | |
| 388 } | |
| 389 } | |
| 390 } | |
| 391 | |
| 392 di->nodes = di->dfsnum - 1; | |
| 393 | |
| 394 /* This aborts e.g. when there is _no_ path from ENTRY to EXIT at all. */ | |
| 395 gcc_assert (di->nodes == (unsigned int) n_basic_blocks - 1); | |
| 396 } | |
| 397 | |
| 398 /* Compress the path from V to the root of its set and update path_min at the | |
| 399 same time. After compress(di, V) set_chain[V] is the root of the set V is | |
| 400 in and path_min[V] is the node with the smallest key[] value on the path | |
| 401 from V to that root. */ | |
| 402 | |
| 403 static void | |
| 404 compress (struct dom_info *di, TBB v) | |
| 405 { | |
| 406 /* Btw. It's not worth to unrecurse compress() as the depth is usually not | |
| 407 greater than 5 even for huge graphs (I've not seen call depth > 4). | |
| 408 Also performance wise compress() ranges _far_ behind eval(). */ | |
| 409 TBB parent = di->set_chain[v]; | |
| 410 if (di->set_chain[parent]) | |
| 411 { | |
| 412 compress (di, parent); | |
| 413 if (di->key[di->path_min[parent]] < di->key[di->path_min[v]]) | |
| 414 di->path_min[v] = di->path_min[parent]; | |
| 415 di->set_chain[v] = di->set_chain[parent]; | |
| 416 } | |
| 417 } | |
| 418 | |
| 419 /* Compress the path from V to the set root of V if needed (when the root has | |
| 420 changed since the last call). Returns the node with the smallest key[] | |
| 421 value on the path from V to the root. */ | |
| 422 | |
| 423 static inline TBB | |
| 424 eval (struct dom_info *di, TBB v) | |
| 425 { | |
| 426 /* The representative of the set V is in, also called root (as the set | |
| 427 representation is a tree). */ | |
| 428 TBB rep = di->set_chain[v]; | |
| 429 | |
| 430 /* V itself is the root. */ | |
| 431 if (!rep) | |
| 432 return di->path_min[v]; | |
| 433 | |
| 434 /* Compress only if necessary. */ | |
| 435 if (di->set_chain[rep]) | |
| 436 { | |
| 437 compress (di, v); | |
| 438 rep = di->set_chain[v]; | |
| 439 } | |
| 440 | |
| 441 if (di->key[di->path_min[rep]] >= di->key[di->path_min[v]]) | |
| 442 return di->path_min[v]; | |
| 443 else | |
| 444 return di->path_min[rep]; | |
| 445 } | |
| 446 | |
| 447 /* This essentially merges the two sets of V and W, giving a single set with | |
| 448 the new root V. The internal representation of these disjoint sets is a | |
| 449 balanced tree. Currently link(V,W) is only used with V being the parent | |
| 450 of W. */ | |
| 451 | |
| 452 static void | |
| 453 link_roots (struct dom_info *di, TBB v, TBB w) | |
| 454 { | |
| 455 TBB s = w; | |
| 456 | |
| 457 /* Rebalance the tree. */ | |
| 458 while (di->key[di->path_min[w]] < di->key[di->path_min[di->set_child[s]]]) | |
| 459 { | |
| 460 if (di->set_size[s] + di->set_size[di->set_child[di->set_child[s]]] | |
| 461 >= 2 * di->set_size[di->set_child[s]]) | |
| 462 { | |
| 463 di->set_chain[di->set_child[s]] = s; | |
| 464 di->set_child[s] = di->set_child[di->set_child[s]]; | |
| 465 } | |
| 466 else | |
| 467 { | |
| 468 di->set_size[di->set_child[s]] = di->set_size[s]; | |
| 469 s = di->set_chain[s] = di->set_child[s]; | |
| 470 } | |
| 471 } | |
| 472 | |
| 473 di->path_min[s] = di->path_min[w]; | |
| 474 di->set_size[v] += di->set_size[w]; | |
| 475 if (di->set_size[v] < 2 * di->set_size[w]) | |
| 476 { | |
| 477 TBB tmp = s; | |
| 478 s = di->set_child[v]; | |
| 479 di->set_child[v] = tmp; | |
| 480 } | |
| 481 | |
| 482 /* Merge all subtrees. */ | |
| 483 while (s) | |
| 484 { | |
| 485 di->set_chain[s] = v; | |
| 486 s = di->set_child[s]; | |
| 487 } | |
| 488 } | |
| 489 | |
| 490 /* This calculates the immediate dominators (or post-dominators if REVERSE is | |
| 491 true). DI is our working structure and should hold the DFS forest. | |
| 492 On return the immediate dominator to node V is in di->dom[V]. */ | |
| 493 | |
| 494 static void | |
| 495 calc_idoms (struct dom_info *di, bool reverse) | |
| 496 { | |
| 497 TBB v, w, k, par; | |
| 498 basic_block en_block; | |
| 499 edge_iterator ei, einext; | |
| 500 | |
| 501 if (reverse) | |
| 502 en_block = EXIT_BLOCK_PTR; | |
| 503 else | |
| 504 en_block = ENTRY_BLOCK_PTR; | |
| 505 | |
| 506 /* Go backwards in DFS order, to first look at the leafs. */ | |
| 507 v = di->nodes; | |
| 508 while (v > 1) | |
| 509 { | |
| 510 basic_block bb = di->dfs_to_bb[v]; | |
| 511 edge e; | |
| 512 | |
| 513 par = di->dfs_parent[v]; | |
| 514 k = v; | |
| 515 | |
| 516 ei = (reverse) ? ei_start (bb->succs) : ei_start (bb->preds); | |
| 517 | |
| 518 if (reverse) | |
| 519 { | |
| 520 /* If this block has a fake edge to exit, process that first. */ | |
| 521 if (bitmap_bit_p (di->fake_exit_edge, bb->index)) | |
| 522 { | |
| 523 einext = ei; | |
| 524 einext.index = 0; | |
| 525 goto do_fake_exit_edge; | |
| 526 } | |
| 527 } | |
| 528 | |
| 529 /* Search all direct predecessors for the smallest node with a path | |
| 530 to them. That way we have the smallest node with also a path to | |
| 531 us only over nodes behind us. In effect we search for our | |
| 532 semidominator. */ | |
| 533 while (!ei_end_p (ei)) | |
| 534 { | |
| 535 TBB k1; | |
| 536 basic_block b; | |
| 537 | |
| 538 e = ei_edge (ei); | |
| 539 b = (reverse) ? e->dest : e->src; | |
| 540 einext = ei; | |
| 541 ei_next (&einext); | |
| 542 | |
| 543 if (b == en_block) | |
| 544 { | |
| 545 do_fake_exit_edge: | |
| 546 k1 = di->dfs_order[last_basic_block]; | |
| 547 } | |
| 548 else | |
| 549 k1 = di->dfs_order[b->index]; | |
| 550 | |
| 551 /* Call eval() only if really needed. If k1 is above V in DFS tree, | |
| 552 then we know, that eval(k1) == k1 and key[k1] == k1. */ | |
| 553 if (k1 > v) | |
| 554 k1 = di->key[eval (di, k1)]; | |
| 555 if (k1 < k) | |
| 556 k = k1; | |
| 557 | |
| 558 ei = einext; | |
| 559 } | |
| 560 | |
| 561 di->key[v] = k; | |
| 562 link_roots (di, par, v); | |
| 563 di->next_bucket[v] = di->bucket[k]; | |
| 564 di->bucket[k] = v; | |
| 565 | |
| 566 /* Transform semidominators into dominators. */ | |
| 567 for (w = di->bucket[par]; w; w = di->next_bucket[w]) | |
| 568 { | |
| 569 k = eval (di, w); | |
| 570 if (di->key[k] < di->key[w]) | |
| 571 di->dom[w] = k; | |
| 572 else | |
| 573 di->dom[w] = par; | |
| 574 } | |
| 575 /* We don't need to cleanup next_bucket[]. */ | |
| 576 di->bucket[par] = 0; | |
| 577 v--; | |
| 578 } | |
| 579 | |
| 580 /* Explicitly define the dominators. */ | |
| 581 di->dom[1] = 0; | |
| 582 for (v = 2; v <= di->nodes; v++) | |
| 583 if (di->dom[v] != di->key[v]) | |
| 584 di->dom[v] = di->dom[di->dom[v]]; | |
| 585 } | |
| 586 | |
| 587 /* Assign dfs numbers starting from NUM to NODE and its sons. */ | |
| 588 | |
| 589 static void | |
| 590 assign_dfs_numbers (struct et_node *node, int *num) | |
| 591 { | |
| 592 struct et_node *son; | |
| 593 | |
| 594 node->dfs_num_in = (*num)++; | |
| 595 | |
| 596 if (node->son) | |
| 597 { | |
| 598 assign_dfs_numbers (node->son, num); | |
| 599 for (son = node->son->right; son != node->son; son = son->right) | |
| 600 assign_dfs_numbers (son, num); | |
| 601 } | |
| 602 | |
| 603 node->dfs_num_out = (*num)++; | |
| 604 } | |
| 605 | |
| 606 /* Compute the data necessary for fast resolving of dominator queries in a | |
| 607 static dominator tree. */ | |
| 608 | |
| 609 static void | |
| 610 compute_dom_fast_query (enum cdi_direction dir) | |
| 611 { | |
| 612 int num = 0; | |
| 613 basic_block bb; | |
| 614 unsigned int dir_index = dom_convert_dir_to_idx (dir); | |
| 615 | |
| 616 gcc_assert (dom_info_available_p (dir)); | |
| 617 | |
| 618 if (dom_computed[dir_index] == DOM_OK) | |
| 619 return; | |
| 620 | |
| 621 FOR_ALL_BB (bb) | |
| 622 { | |
| 623 if (!bb->dom[dir_index]->father) | |
| 624 assign_dfs_numbers (bb->dom[dir_index], &num); | |
| 625 } | |
| 626 | |
| 627 dom_computed[dir_index] = DOM_OK; | |
| 628 } | |
| 629 | |
| 630 /* The main entry point into this module. DIR is set depending on whether | |
| 631 we want to compute dominators or postdominators. */ | |
| 632 | |
| 633 void | |
| 634 calculate_dominance_info (enum cdi_direction dir) | |
| 635 { | |
| 636 struct dom_info di; | |
| 637 basic_block b; | |
| 638 unsigned int dir_index = dom_convert_dir_to_idx (dir); | |
| 639 bool reverse = (dir == CDI_POST_DOMINATORS) ? true : false; | |
| 640 | |
| 641 if (dom_computed[dir_index] == DOM_OK) | |
| 642 return; | |
| 643 | |
| 644 timevar_push (TV_DOMINANCE); | |
| 645 if (!dom_info_available_p (dir)) | |
| 646 { | |
| 647 gcc_assert (!n_bbs_in_dom_tree[dir_index]); | |
| 648 | |
| 649 FOR_ALL_BB (b) | |
| 650 { | |
| 651 b->dom[dir_index] = et_new_tree (b); | |
| 652 } | |
| 653 n_bbs_in_dom_tree[dir_index] = n_basic_blocks; | |
| 654 | |
| 655 init_dom_info (&di, dir); | |
| 656 calc_dfs_tree (&di, reverse); | |
| 657 calc_idoms (&di, reverse); | |
| 658 | |
| 659 FOR_EACH_BB (b) | |
| 660 { | |
| 661 TBB d = di.dom[di.dfs_order[b->index]]; | |
| 662 | |
| 663 if (di.dfs_to_bb[d]) | |
| 664 et_set_father (b->dom[dir_index], di.dfs_to_bb[d]->dom[dir_index]); | |
| 665 } | |
| 666 | |
| 667 free_dom_info (&di); | |
| 668 dom_computed[dir_index] = DOM_NO_FAST_QUERY; | |
| 669 } | |
| 670 | |
| 671 compute_dom_fast_query (dir); | |
| 672 | |
| 673 timevar_pop (TV_DOMINANCE); | |
| 674 } | |
| 675 | |
| 676 /* Free dominance information for direction DIR. */ | |
| 677 void | |
| 678 free_dominance_info (enum cdi_direction dir) | |
| 679 { | |
| 680 basic_block bb; | |
| 681 unsigned int dir_index = dom_convert_dir_to_idx (dir); | |
| 682 | |
| 683 if (!dom_info_available_p (dir)) | |
| 684 return; | |
| 685 | |
| 686 FOR_ALL_BB (bb) | |
| 687 { | |
| 688 et_free_tree_force (bb->dom[dir_index]); | |
| 689 bb->dom[dir_index] = NULL; | |
| 690 } | |
| 691 et_free_pools (); | |
| 692 | |
| 693 n_bbs_in_dom_tree[dir_index] = 0; | |
| 694 | |
| 695 dom_computed[dir_index] = DOM_NONE; | |
| 696 } | |
| 697 | |
| 698 /* Return the immediate dominator of basic block BB. */ | |
| 699 basic_block | |
| 700 get_immediate_dominator (enum cdi_direction dir, basic_block bb) | |
| 701 { | |
| 702 unsigned int dir_index = dom_convert_dir_to_idx (dir); | |
| 703 struct et_node *node = bb->dom[dir_index]; | |
| 704 | |
| 705 gcc_assert (dom_computed[dir_index]); | |
| 706 | |
| 707 if (!node->father) | |
| 708 return NULL; | |
| 709 | |
| 710 return (basic_block) node->father->data; | |
| 711 } | |
| 712 | |
| 713 /* Set the immediate dominator of the block possibly removing | |
| 714 existing edge. NULL can be used to remove any edge. */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
715 void |
| 0 | 716 set_immediate_dominator (enum cdi_direction dir, basic_block bb, |
| 717 basic_block dominated_by) | |
| 718 { | |
| 719 unsigned int dir_index = dom_convert_dir_to_idx (dir); | |
| 720 struct et_node *node = bb->dom[dir_index]; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
721 |
| 0 | 722 gcc_assert (dom_computed[dir_index]); |
| 723 | |
| 724 if (node->father) | |
| 725 { | |
| 726 if (node->father->data == dominated_by) | |
| 727 return; | |
| 728 et_split (node); | |
| 729 } | |
| 730 | |
| 731 if (dominated_by) | |
| 732 et_set_father (node, dominated_by->dom[dir_index]); | |
| 733 | |
| 734 if (dom_computed[dir_index] == DOM_OK) | |
| 735 dom_computed[dir_index] = DOM_NO_FAST_QUERY; | |
| 736 } | |
| 737 | |
| 738 /* Returns the list of basic blocks immediately dominated by BB, in the | |
| 739 direction DIR. */ | |
| 740 VEC (basic_block, heap) * | |
| 741 get_dominated_by (enum cdi_direction dir, basic_block bb) | |
| 742 { | |
| 743 unsigned int dir_index = dom_convert_dir_to_idx (dir); | |
| 744 struct et_node *node = bb->dom[dir_index], *son = node->son, *ason; | |
| 745 VEC (basic_block, heap) *bbs = NULL; | |
| 746 | |
| 747 gcc_assert (dom_computed[dir_index]); | |
| 748 | |
| 749 if (!son) | |
| 750 return NULL; | |
| 751 | |
| 752 VEC_safe_push (basic_block, heap, bbs, (basic_block) son->data); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
753 for (ason = son->right; ason != son; ason = ason->right) |
| 0 | 754 VEC_safe_push (basic_block, heap, bbs, (basic_block) ason->data); |
| 755 | |
| 756 return bbs; | |
| 757 } | |
| 758 | |
| 759 /* Returns the list of basic blocks that are immediately dominated (in | |
| 760 direction DIR) by some block between N_REGION ones stored in REGION, | |
| 761 except for blocks in the REGION itself. */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
762 |
| 0 | 763 VEC (basic_block, heap) * |
| 764 get_dominated_by_region (enum cdi_direction dir, basic_block *region, | |
| 765 unsigned n_region) | |
| 766 { | |
| 767 unsigned i; | |
| 768 basic_block dom; | |
| 769 VEC (basic_block, heap) *doms = NULL; | |
| 770 | |
| 771 for (i = 0; i < n_region; i++) | |
| 772 region[i]->flags |= BB_DUPLICATED; | |
| 773 for (i = 0; i < n_region; i++) | |
| 774 for (dom = first_dom_son (dir, region[i]); | |
| 775 dom; | |
| 776 dom = next_dom_son (dir, dom)) | |
| 777 if (!(dom->flags & BB_DUPLICATED)) | |
| 778 VEC_safe_push (basic_block, heap, doms, dom); | |
| 779 for (i = 0; i < n_region; i++) | |
| 780 region[i]->flags &= ~BB_DUPLICATED; | |
| 781 | |
| 782 return doms; | |
| 783 } | |
| 784 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
785 /* Returns the list of basic blocks including BB dominated by BB, in the |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
786 direction DIR up to DEPTH in the dominator tree. The DEPTH of zero will |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
787 produce a vector containing all dominated blocks. The vector will be sorted |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
788 in preorder. */ |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
789 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
790 VEC (basic_block, heap) * |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
791 get_dominated_to_depth (enum cdi_direction dir, basic_block bb, int depth) |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
792 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
793 VEC(basic_block, heap) *bbs = NULL; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
794 unsigned i; |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
795 unsigned next_level_start; |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
796 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
797 i = 0; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
798 VEC_safe_push (basic_block, heap, bbs, bb); |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
799 next_level_start = 1; /* = VEC_length (basic_block, bbs); */ |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
800 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
801 do |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
802 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
803 basic_block son; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
804 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
805 bb = VEC_index (basic_block, bbs, i++); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
806 for (son = first_dom_son (dir, bb); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
807 son; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
808 son = next_dom_son (dir, son)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
809 VEC_safe_push (basic_block, heap, bbs, son); |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
810 |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
811 if (i == next_level_start && --depth) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
812 next_level_start = VEC_length (basic_block, bbs); |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
813 } |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
814 while (i < next_level_start); |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
815 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
816 return bbs; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
817 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
818 |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
819 /* Returns the list of basic blocks including BB dominated by BB, in the |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
820 direction DIR. The vector will be sorted in preorder. */ |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
821 |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
822 VEC (basic_block, heap) * |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
823 get_all_dominated_blocks (enum cdi_direction dir, basic_block bb) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
824 { |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
825 return get_dominated_to_depth (dir, bb, 0); |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
826 } |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
827 |
| 0 | 828 /* Redirect all edges pointing to BB to TO. */ |
| 829 void | |
| 830 redirect_immediate_dominators (enum cdi_direction dir, basic_block bb, | |
| 831 basic_block to) | |
| 832 { | |
| 833 unsigned int dir_index = dom_convert_dir_to_idx (dir); | |
| 834 struct et_node *bb_node, *to_node, *son; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
835 |
| 0 | 836 bb_node = bb->dom[dir_index]; |
| 837 to_node = to->dom[dir_index]; | |
| 838 | |
| 839 gcc_assert (dom_computed[dir_index]); | |
| 840 | |
| 841 if (!bb_node->son) | |
| 842 return; | |
| 843 | |
| 844 while (bb_node->son) | |
| 845 { | |
| 846 son = bb_node->son; | |
| 847 | |
| 848 et_split (son); | |
| 849 et_set_father (son, to_node); | |
| 850 } | |
| 851 | |
| 852 if (dom_computed[dir_index] == DOM_OK) | |
| 853 dom_computed[dir_index] = DOM_NO_FAST_QUERY; | |
| 854 } | |
| 855 | |
| 856 /* Find first basic block in the tree dominating both BB1 and BB2. */ | |
| 857 basic_block | |
| 858 nearest_common_dominator (enum cdi_direction dir, basic_block bb1, basic_block bb2) | |
| 859 { | |
| 860 unsigned int dir_index = dom_convert_dir_to_idx (dir); | |
| 861 | |
| 862 gcc_assert (dom_computed[dir_index]); | |
| 863 | |
| 864 if (!bb1) | |
| 865 return bb2; | |
| 866 if (!bb2) | |
| 867 return bb1; | |
| 868 | |
| 869 return (basic_block) et_nca (bb1->dom[dir_index], bb2->dom[dir_index])->data; | |
| 870 } | |
| 871 | |
| 872 | |
| 873 /* Find the nearest common dominator for the basic blocks in BLOCKS, | |
| 874 using dominance direction DIR. */ | |
| 875 | |
| 876 basic_block | |
| 877 nearest_common_dominator_for_set (enum cdi_direction dir, bitmap blocks) | |
| 878 { | |
| 879 unsigned i, first; | |
| 880 bitmap_iterator bi; | |
| 881 basic_block dom; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
882 |
| 0 | 883 first = bitmap_first_set_bit (blocks); |
| 884 dom = BASIC_BLOCK (first); | |
| 885 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi) | |
| 886 if (dom != BASIC_BLOCK (i)) | |
| 887 dom = nearest_common_dominator (dir, dom, BASIC_BLOCK (i)); | |
| 888 | |
| 889 return dom; | |
| 890 } | |
| 891 | |
| 892 /* Given a dominator tree, we can determine whether one thing | |
| 893 dominates another in constant time by using two DFS numbers: | |
| 894 | |
| 895 1. The number for when we visit a node on the way down the tree | |
| 896 2. The number for when we visit a node on the way back up the tree | |
| 897 | |
| 898 You can view these as bounds for the range of dfs numbers the | |
| 899 nodes in the subtree of the dominator tree rooted at that node | |
| 900 will contain. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
901 |
| 0 | 902 The dominator tree is always a simple acyclic tree, so there are |
| 903 only three possible relations two nodes in the dominator tree have | |
| 904 to each other: | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
905 |
| 0 | 906 1. Node A is above Node B (and thus, Node A dominates node B) |
| 907 | |
| 908 A | |
| 909 | | |
| 910 C | |
| 911 / \ | |
| 912 B D | |
| 913 | |
| 914 | |
| 915 In the above case, DFS_Number_In of A will be <= DFS_Number_In of | |
| 916 B, and DFS_Number_Out of A will be >= DFS_Number_Out of B. This is | |
| 917 because we must hit A in the dominator tree *before* B on the walk | |
| 918 down, and we will hit A *after* B on the walk back up | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
919 |
| 0 | 920 2. Node A is below node B (and thus, node B dominates node A) |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
921 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
922 |
| 0 | 923 B |
| 924 | | |
| 925 A | |
| 926 / \ | |
| 927 C D | |
| 928 | |
| 929 In the above case, DFS_Number_In of A will be >= DFS_Number_In of | |
| 930 B, and DFS_Number_Out of A will be <= DFS_Number_Out of B. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
931 |
| 0 | 932 This is because we must hit A in the dominator tree *after* B on |
| 933 the walk down, and we will hit A *before* B on the walk back up | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
934 |
| 0 | 935 3. Node A and B are siblings (and thus, neither dominates the other) |
| 936 | |
| 937 C | |
| 938 | | |
| 939 D | |
| 940 / \ | |
| 941 A B | |
| 942 | |
| 943 In the above case, DFS_Number_In of A will *always* be <= | |
| 944 DFS_Number_In of B, and DFS_Number_Out of A will *always* be <= | |
| 945 DFS_Number_Out of B. This is because we will always finish the dfs | |
| 946 walk of one of the subtrees before the other, and thus, the dfs | |
| 947 numbers for one subtree can't intersect with the range of dfs | |
| 948 numbers for the other subtree. If you swap A and B's position in | |
| 949 the dominator tree, the comparison changes direction, but the point | |
| 950 is that both comparisons will always go the same way if there is no | |
| 951 dominance relationship. | |
| 952 | |
| 953 Thus, it is sufficient to write | |
| 954 | |
| 955 A_Dominates_B (node A, node B) | |
| 956 { | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
957 return DFS_Number_In(A) <= DFS_Number_In(B) |
| 0 | 958 && DFS_Number_Out (A) >= DFS_Number_Out(B); |
| 959 } | |
| 960 | |
| 961 A_Dominated_by_B (node A, node B) | |
| 962 { | |
| 963 return DFS_Number_In(A) >= DFS_Number_In(A) | |
| 964 && DFS_Number_Out (A) <= DFS_Number_Out(B); | |
| 965 } */ | |
| 966 | |
| 967 /* Return TRUE in case BB1 is dominated by BB2. */ | |
| 968 bool | |
| 969 dominated_by_p (enum cdi_direction dir, const_basic_block bb1, const_basic_block bb2) | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
970 { |
| 0 | 971 unsigned int dir_index = dom_convert_dir_to_idx (dir); |
| 972 struct et_node *n1 = bb1->dom[dir_index], *n2 = bb2->dom[dir_index]; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
973 |
| 0 | 974 gcc_assert (dom_computed[dir_index]); |
| 975 | |
| 976 if (dom_computed[dir_index] == DOM_OK) | |
| 977 return (n1->dfs_num_in >= n2->dfs_num_in | |
| 978 && n1->dfs_num_out <= n2->dfs_num_out); | |
| 979 | |
| 980 return et_below (n1, n2); | |
| 981 } | |
| 982 | |
| 983 /* Returns the entry dfs number for basic block BB, in the direction DIR. */ | |
| 984 | |
| 985 unsigned | |
| 986 bb_dom_dfs_in (enum cdi_direction dir, basic_block bb) | |
| 987 { | |
| 988 unsigned int dir_index = dom_convert_dir_to_idx (dir); | |
| 989 struct et_node *n = bb->dom[dir_index]; | |
| 990 | |
| 991 gcc_assert (dom_computed[dir_index] == DOM_OK); | |
| 992 return n->dfs_num_in; | |
| 993 } | |
| 994 | |
| 995 /* Returns the exit dfs number for basic block BB, in the direction DIR. */ | |
| 996 | |
| 997 unsigned | |
| 998 bb_dom_dfs_out (enum cdi_direction dir, basic_block bb) | |
| 999 { | |
| 1000 unsigned int dir_index = dom_convert_dir_to_idx (dir); | |
| 1001 struct et_node *n = bb->dom[dir_index]; | |
| 1002 | |
| 1003 gcc_assert (dom_computed[dir_index] == DOM_OK); | |
| 1004 return n->dfs_num_out; | |
| 1005 } | |
| 1006 | |
| 1007 /* Verify invariants of dominator structure. */ | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1008 DEBUG_FUNCTION void |
| 0 | 1009 verify_dominators (enum cdi_direction dir) |
| 1010 { | |
| 1011 int err = 0; | |
| 1012 basic_block bb, imm_bb, imm_bb_correct; | |
| 1013 struct dom_info di; | |
| 1014 bool reverse = (dir == CDI_POST_DOMINATORS) ? true : false; | |
| 1015 | |
| 1016 gcc_assert (dom_info_available_p (dir)); | |
| 1017 | |
| 1018 init_dom_info (&di, dir); | |
| 1019 calc_dfs_tree (&di, reverse); | |
| 1020 calc_idoms (&di, reverse); | |
| 1021 | |
| 1022 FOR_EACH_BB (bb) | |
| 1023 { | |
| 1024 imm_bb = get_immediate_dominator (dir, bb); | |
| 1025 if (!imm_bb) | |
| 1026 { | |
| 1027 error ("dominator of %d status unknown", bb->index); | |
| 1028 err = 1; | |
| 1029 } | |
| 1030 | |
| 1031 imm_bb_correct = di.dfs_to_bb[di.dom[di.dfs_order[bb->index]]]; | |
| 1032 if (imm_bb != imm_bb_correct) | |
| 1033 { | |
| 1034 error ("dominator of %d should be %d, not %d", | |
| 1035 bb->index, imm_bb_correct->index, imm_bb->index); | |
| 1036 err = 1; | |
| 1037 } | |
| 1038 } | |
| 1039 | |
| 1040 free_dom_info (&di); | |
| 1041 gcc_assert (!err); | |
| 1042 } | |
| 1043 | |
| 1044 /* Determine immediate dominator (or postdominator, according to DIR) of BB, | |
| 1045 assuming that dominators of other blocks are correct. We also use it to | |
| 1046 recompute the dominators in a restricted area, by iterating it until it | |
| 1047 reaches a fixed point. */ | |
| 1048 | |
| 1049 basic_block | |
| 1050 recompute_dominator (enum cdi_direction dir, basic_block bb) | |
| 1051 { | |
| 1052 unsigned int dir_index = dom_convert_dir_to_idx (dir); | |
| 1053 basic_block dom_bb = NULL; | |
| 1054 edge e; | |
| 1055 edge_iterator ei; | |
| 1056 | |
| 1057 gcc_assert (dom_computed[dir_index]); | |
| 1058 | |
| 1059 if (dir == CDI_DOMINATORS) | |
| 1060 { | |
| 1061 FOR_EACH_EDGE (e, ei, bb->preds) | |
| 1062 { | |
| 1063 if (!dominated_by_p (dir, e->src, bb)) | |
| 1064 dom_bb = nearest_common_dominator (dir, dom_bb, e->src); | |
| 1065 } | |
| 1066 } | |
| 1067 else | |
| 1068 { | |
| 1069 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 1070 { | |
| 1071 if (!dominated_by_p (dir, e->dest, bb)) | |
| 1072 dom_bb = nearest_common_dominator (dir, dom_bb, e->dest); | |
| 1073 } | |
| 1074 } | |
| 1075 | |
| 1076 return dom_bb; | |
| 1077 } | |
| 1078 | |
| 1079 /* Use simple heuristics (see iterate_fix_dominators) to determine dominators | |
| 1080 of BBS. We assume that all the immediate dominators except for those of the | |
| 1081 blocks in BBS are correct. If CONSERVATIVE is true, we also assume that the | |
| 1082 currently recorded immediate dominators of blocks in BBS really dominate the | |
| 1083 blocks. The basic blocks for that we determine the dominator are removed | |
| 1084 from BBS. */ | |
| 1085 | |
| 1086 static void | |
| 1087 prune_bbs_to_update_dominators (VEC (basic_block, heap) *bbs, | |
| 1088 bool conservative) | |
| 1089 { | |
| 1090 unsigned i; | |
| 1091 bool single; | |
| 1092 basic_block bb, dom = NULL; | |
| 1093 edge_iterator ei; | |
| 1094 edge e; | |
| 1095 | |
| 1096 for (i = 0; VEC_iterate (basic_block, bbs, i, bb);) | |
| 1097 { | |
| 1098 if (bb == ENTRY_BLOCK_PTR) | |
| 1099 goto succeed; | |
| 1100 | |
| 1101 if (single_pred_p (bb)) | |
| 1102 { | |
| 1103 set_immediate_dominator (CDI_DOMINATORS, bb, single_pred (bb)); | |
| 1104 goto succeed; | |
| 1105 } | |
| 1106 | |
| 1107 if (!conservative) | |
| 1108 goto fail; | |
| 1109 | |
| 1110 single = true; | |
| 1111 dom = NULL; | |
| 1112 FOR_EACH_EDGE (e, ei, bb->preds) | |
| 1113 { | |
| 1114 if (dominated_by_p (CDI_DOMINATORS, e->src, bb)) | |
| 1115 continue; | |
| 1116 | |
| 1117 if (!dom) | |
| 1118 dom = e->src; | |
| 1119 else | |
| 1120 { | |
| 1121 single = false; | |
| 1122 dom = nearest_common_dominator (CDI_DOMINATORS, dom, e->src); | |
| 1123 } | |
| 1124 } | |
| 1125 | |
| 1126 gcc_assert (dom != NULL); | |
| 1127 if (single | |
| 1128 || find_edge (dom, bb)) | |
| 1129 { | |
| 1130 set_immediate_dominator (CDI_DOMINATORS, bb, dom); | |
| 1131 goto succeed; | |
| 1132 } | |
| 1133 | |
| 1134 fail: | |
| 1135 i++; | |
| 1136 continue; | |
| 1137 | |
| 1138 succeed: | |
| 1139 VEC_unordered_remove (basic_block, bbs, i); | |
| 1140 } | |
| 1141 } | |
| 1142 | |
| 1143 /* Returns root of the dominance tree in the direction DIR that contains | |
| 1144 BB. */ | |
| 1145 | |
| 1146 static basic_block | |
| 1147 root_of_dom_tree (enum cdi_direction dir, basic_block bb) | |
| 1148 { | |
| 1149 return (basic_block) et_root (bb->dom[dom_convert_dir_to_idx (dir)])->data; | |
| 1150 } | |
| 1151 | |
| 1152 /* See the comment in iterate_fix_dominators. Finds the immediate dominators | |
| 1153 for the sons of Y, found using the SON and BROTHER arrays representing | |
| 1154 the dominance tree of graph G. BBS maps the vertices of G to the basic | |
| 1155 blocks. */ | |
| 1156 | |
| 1157 static void | |
| 1158 determine_dominators_for_sons (struct graph *g, VEC (basic_block, heap) *bbs, | |
| 1159 int y, int *son, int *brother) | |
| 1160 { | |
| 1161 bitmap gprime; | |
| 1162 int i, a, nc; | |
| 1163 VEC (int, heap) **sccs; | |
| 1164 basic_block bb, dom, ybb; | |
| 1165 unsigned si; | |
| 1166 edge e; | |
| 1167 edge_iterator ei; | |
| 1168 | |
| 1169 if (son[y] == -1) | |
| 1170 return; | |
| 1171 if (y == (int) VEC_length (basic_block, bbs)) | |
| 1172 ybb = ENTRY_BLOCK_PTR; | |
| 1173 else | |
| 1174 ybb = VEC_index (basic_block, bbs, y); | |
| 1175 | |
| 1176 if (brother[son[y]] == -1) | |
| 1177 { | |
| 1178 /* Handle the common case Y has just one son specially. */ | |
| 1179 bb = VEC_index (basic_block, bbs, son[y]); | |
| 1180 set_immediate_dominator (CDI_DOMINATORS, bb, | |
| 1181 recompute_dominator (CDI_DOMINATORS, bb)); | |
| 1182 identify_vertices (g, y, son[y]); | |
| 1183 return; | |
| 1184 } | |
| 1185 | |
| 1186 gprime = BITMAP_ALLOC (NULL); | |
| 1187 for (a = son[y]; a != -1; a = brother[a]) | |
| 1188 bitmap_set_bit (gprime, a); | |
| 1189 | |
| 1190 nc = graphds_scc (g, gprime); | |
| 1191 BITMAP_FREE (gprime); | |
| 1192 | |
| 1193 sccs = XCNEWVEC (VEC (int, heap) *, nc); | |
| 1194 for (a = son[y]; a != -1; a = brother[a]) | |
| 1195 VEC_safe_push (int, heap, sccs[g->vertices[a].component], a); | |
| 1196 | |
| 1197 for (i = nc - 1; i >= 0; i--) | |
| 1198 { | |
| 1199 dom = NULL; | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1200 FOR_EACH_VEC_ELT (int, sccs[i], si, a) |
| 0 | 1201 { |
| 1202 bb = VEC_index (basic_block, bbs, a); | |
| 1203 FOR_EACH_EDGE (e, ei, bb->preds) | |
| 1204 { | |
| 1205 if (root_of_dom_tree (CDI_DOMINATORS, e->src) != ybb) | |
| 1206 continue; | |
| 1207 | |
| 1208 dom = nearest_common_dominator (CDI_DOMINATORS, dom, e->src); | |
| 1209 } | |
| 1210 } | |
| 1211 | |
| 1212 gcc_assert (dom != NULL); | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1213 FOR_EACH_VEC_ELT (int, sccs[i], si, a) |
| 0 | 1214 { |
| 1215 bb = VEC_index (basic_block, bbs, a); | |
| 1216 set_immediate_dominator (CDI_DOMINATORS, bb, dom); | |
| 1217 } | |
| 1218 } | |
| 1219 | |
| 1220 for (i = 0; i < nc; i++) | |
| 1221 VEC_free (int, heap, sccs[i]); | |
| 1222 free (sccs); | |
| 1223 | |
| 1224 for (a = son[y]; a != -1; a = brother[a]) | |
| 1225 identify_vertices (g, y, a); | |
| 1226 } | |
| 1227 | |
| 1228 /* Recompute dominance information for basic blocks in the set BBS. The | |
| 1229 function assumes that the immediate dominators of all the other blocks | |
| 1230 in CFG are correct, and that there are no unreachable blocks. | |
| 1231 | |
| 1232 If CONSERVATIVE is true, we additionally assume that all the ancestors of | |
| 1233 a block of BBS in the current dominance tree dominate it. */ | |
| 1234 | |
| 1235 void | |
| 1236 iterate_fix_dominators (enum cdi_direction dir, VEC (basic_block, heap) *bbs, | |
| 1237 bool conservative) | |
| 1238 { | |
| 1239 unsigned i; | |
| 1240 basic_block bb, dom; | |
| 1241 struct graph *g; | |
| 1242 int n, y; | |
| 1243 size_t dom_i; | |
| 1244 edge e; | |
| 1245 edge_iterator ei; | |
| 1246 struct pointer_map_t *map; | |
| 1247 int *parent, *son, *brother; | |
| 1248 unsigned int dir_index = dom_convert_dir_to_idx (dir); | |
| 1249 | |
| 1250 /* We only support updating dominators. There are some problems with | |
| 1251 updating postdominators (need to add fake edges from infinite loops | |
| 1252 and noreturn functions), and since we do not currently use | |
| 1253 iterate_fix_dominators for postdominators, any attempt to handle these | |
| 1254 problems would be unused, untested, and almost surely buggy. We keep | |
| 1255 the DIR argument for consistency with the rest of the dominator analysis | |
| 1256 interface. */ | |
| 1257 gcc_assert (dir == CDI_DOMINATORS); | |
| 1258 gcc_assert (dom_computed[dir_index]); | |
| 1259 | |
| 1260 /* The algorithm we use takes inspiration from the following papers, although | |
| 1261 the details are quite different from any of them: | |
| 1262 | |
| 1263 [1] G. Ramalingam, T. Reps, An Incremental Algorithm for Maintaining the | |
| 1264 Dominator Tree of a Reducible Flowgraph | |
| 1265 [2] V. C. Sreedhar, G. R. Gao, Y.-F. Lee: Incremental computation of | |
| 1266 dominator trees | |
| 1267 [3] K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance | |
| 1268 Algorithm | |
| 1269 | |
| 1270 First, we use the following heuristics to decrease the size of the BBS | |
| 1271 set: | |
| 1272 a) if BB has a single predecessor, then its immediate dominator is this | |
| 1273 predecessor | |
| 1274 additionally, if CONSERVATIVE is true: | |
| 1275 b) if all the predecessors of BB except for one (X) are dominated by BB, | |
| 1276 then X is the immediate dominator of BB | |
| 1277 c) if the nearest common ancestor of the predecessors of BB is X and | |
| 1278 X -> BB is an edge in CFG, then X is the immediate dominator of BB | |
| 1279 | |
| 1280 Then, we need to establish the dominance relation among the basic blocks | |
| 1281 in BBS. We split the dominance tree by removing the immediate dominator | |
| 1282 edges from BBS, creating a forest F. We form a graph G whose vertices | |
| 1283 are BBS and ENTRY and X -> Y is an edge of G if there exists an edge | |
| 1284 X' -> Y in CFG such that X' belongs to the tree of the dominance forest | |
| 1285 whose root is X. We then determine dominance tree of G. Note that | |
| 1286 for X, Y in BBS, X dominates Y in CFG if and only if X dominates Y in G. | |
| 1287 In this step, we can use arbitrary algorithm to determine dominators. | |
| 1288 We decided to prefer the algorithm [3] to the algorithm of | |
| 1289 Lengauer and Tarjan, since the set BBS is usually small (rarely exceeding | |
| 1290 10 during gcc bootstrap), and [3] should perform better in this case. | |
| 1291 | |
| 1292 Finally, we need to determine the immediate dominators for the basic | |
| 1293 blocks of BBS. If the immediate dominator of X in G is Y, then | |
| 1294 the immediate dominator of X in CFG belongs to the tree of F rooted in | |
| 1295 Y. We process the dominator tree T of G recursively, starting from leaves. | |
| 1296 Suppose that X_1, X_2, ..., X_k are the sons of Y in T, and that the | |
| 1297 subtrees of the dominance tree of CFG rooted in X_i are already correct. | |
| 1298 Let G' be the subgraph of G induced by {X_1, X_2, ..., X_k}. We make | |
| 1299 the following observations: | |
| 1300 (i) the immediate dominator of all blocks in a strongly connected | |
| 1301 component of G' is the same | |
| 1302 (ii) if X has no predecessors in G', then the immediate dominator of X | |
| 1303 is the nearest common ancestor of the predecessors of X in the | |
| 1304 subtree of F rooted in Y | |
| 1305 Therefore, it suffices to find the topological ordering of G', and | |
| 1306 process the nodes X_i in this order using the rules (i) and (ii). | |
| 1307 Then, we contract all the nodes X_i with Y in G, so that the further | |
| 1308 steps work correctly. */ | |
| 1309 | |
| 1310 if (!conservative) | |
| 1311 { | |
| 1312 /* Split the tree now. If the idoms of blocks in BBS are not | |
| 1313 conservatively correct, setting the dominators using the | |
| 1314 heuristics in prune_bbs_to_update_dominators could | |
| 1315 create cycles in the dominance "tree", and cause ICE. */ | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1316 FOR_EACH_VEC_ELT (basic_block, bbs, i, bb) |
| 0 | 1317 set_immediate_dominator (CDI_DOMINATORS, bb, NULL); |
| 1318 } | |
| 1319 | |
| 1320 prune_bbs_to_update_dominators (bbs, conservative); | |
| 1321 n = VEC_length (basic_block, bbs); | |
| 1322 | |
| 1323 if (n == 0) | |
| 1324 return; | |
| 1325 | |
| 1326 if (n == 1) | |
| 1327 { | |
| 1328 bb = VEC_index (basic_block, bbs, 0); | |
| 1329 set_immediate_dominator (CDI_DOMINATORS, bb, | |
| 1330 recompute_dominator (CDI_DOMINATORS, bb)); | |
| 1331 return; | |
| 1332 } | |
| 1333 | |
| 1334 /* Construct the graph G. */ | |
| 1335 map = pointer_map_create (); | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1336 FOR_EACH_VEC_ELT (basic_block, bbs, i, bb) |
| 0 | 1337 { |
| 1338 /* If the dominance tree is conservatively correct, split it now. */ | |
| 1339 if (conservative) | |
| 1340 set_immediate_dominator (CDI_DOMINATORS, bb, NULL); | |
| 1341 *pointer_map_insert (map, bb) = (void *) (size_t) i; | |
| 1342 } | |
| 1343 *pointer_map_insert (map, ENTRY_BLOCK_PTR) = (void *) (size_t) n; | |
| 1344 | |
| 1345 g = new_graph (n + 1); | |
| 1346 for (y = 0; y < g->n_vertices; y++) | |
| 1347 g->vertices[y].data = BITMAP_ALLOC (NULL); | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1348 FOR_EACH_VEC_ELT (basic_block, bbs, i, bb) |
| 0 | 1349 { |
| 1350 FOR_EACH_EDGE (e, ei, bb->preds) | |
| 1351 { | |
| 1352 dom = root_of_dom_tree (CDI_DOMINATORS, e->src); | |
| 1353 if (dom == bb) | |
| 1354 continue; | |
| 1355 | |
| 1356 dom_i = (size_t) *pointer_map_contains (map, dom); | |
| 1357 | |
| 1358 /* Do not include parallel edges to G. */ | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1359 if (!bitmap_set_bit ((bitmap) g->vertices[dom_i].data, i)) |
| 0 | 1360 continue; |
| 1361 | |
| 1362 add_edge (g, dom_i, i); | |
| 1363 } | |
| 1364 } | |
| 1365 for (y = 0; y < g->n_vertices; y++) | |
| 1366 BITMAP_FREE (g->vertices[y].data); | |
| 1367 pointer_map_destroy (map); | |
| 1368 | |
| 1369 /* Find the dominator tree of G. */ | |
| 1370 son = XNEWVEC (int, n + 1); | |
| 1371 brother = XNEWVEC (int, n + 1); | |
| 1372 parent = XNEWVEC (int, n + 1); | |
| 1373 graphds_domtree (g, n, parent, son, brother); | |
| 1374 | |
| 1375 /* Finally, traverse the tree and find the immediate dominators. */ | |
| 1376 for (y = n; son[y] != -1; y = son[y]) | |
| 1377 continue; | |
| 1378 while (y != -1) | |
| 1379 { | |
| 1380 determine_dominators_for_sons (g, bbs, y, son, brother); | |
| 1381 | |
| 1382 if (brother[y] != -1) | |
| 1383 { | |
| 1384 y = brother[y]; | |
| 1385 while (son[y] != -1) | |
| 1386 y = son[y]; | |
| 1387 } | |
| 1388 else | |
| 1389 y = parent[y]; | |
| 1390 } | |
| 1391 | |
| 1392 free (son); | |
| 1393 free (brother); | |
| 1394 free (parent); | |
| 1395 | |
| 1396 free_graph (g); | |
| 1397 } | |
| 1398 | |
| 1399 void | |
| 1400 add_to_dominance_info (enum cdi_direction dir, basic_block bb) | |
| 1401 { | |
| 1402 unsigned int dir_index = dom_convert_dir_to_idx (dir); | |
| 1403 | |
| 1404 gcc_assert (dom_computed[dir_index]); | |
| 1405 gcc_assert (!bb->dom[dir_index]); | |
| 1406 | |
| 1407 n_bbs_in_dom_tree[dir_index]++; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1408 |
| 0 | 1409 bb->dom[dir_index] = et_new_tree (bb); |
| 1410 | |
| 1411 if (dom_computed[dir_index] == DOM_OK) | |
| 1412 dom_computed[dir_index] = DOM_NO_FAST_QUERY; | |
| 1413 } | |
| 1414 | |
| 1415 void | |
| 1416 delete_from_dominance_info (enum cdi_direction dir, basic_block bb) | |
| 1417 { | |
| 1418 unsigned int dir_index = dom_convert_dir_to_idx (dir); | |
| 1419 | |
| 1420 gcc_assert (dom_computed[dir_index]); | |
| 1421 | |
| 1422 et_free_tree (bb->dom[dir_index]); | |
| 1423 bb->dom[dir_index] = NULL; | |
| 1424 n_bbs_in_dom_tree[dir_index]--; | |
| 1425 | |
| 1426 if (dom_computed[dir_index] == DOM_OK) | |
| 1427 dom_computed[dir_index] = DOM_NO_FAST_QUERY; | |
| 1428 } | |
| 1429 | |
| 1430 /* Returns the first son of BB in the dominator or postdominator tree | |
| 1431 as determined by DIR. */ | |
| 1432 | |
| 1433 basic_block | |
| 1434 first_dom_son (enum cdi_direction dir, basic_block bb) | |
| 1435 { | |
| 1436 unsigned int dir_index = dom_convert_dir_to_idx (dir); | |
| 1437 struct et_node *son = bb->dom[dir_index]->son; | |
| 1438 | |
| 1439 return (basic_block) (son ? son->data : NULL); | |
| 1440 } | |
| 1441 | |
| 1442 /* Returns the next dominance son after BB in the dominator or postdominator | |
| 1443 tree as determined by DIR, or NULL if it was the last one. */ | |
| 1444 | |
| 1445 basic_block | |
| 1446 next_dom_son (enum cdi_direction dir, basic_block bb) | |
| 1447 { | |
| 1448 unsigned int dir_index = dom_convert_dir_to_idx (dir); | |
| 1449 struct et_node *next = bb->dom[dir_index]->right; | |
| 1450 | |
| 1451 return (basic_block) (next->father->son == next ? NULL : next->data); | |
| 1452 } | |
| 1453 | |
| 1454 /* Return dominance availability for dominance info DIR. */ | |
| 1455 | |
| 1456 enum dom_state | |
| 1457 dom_info_state (enum cdi_direction dir) | |
| 1458 { | |
| 1459 unsigned int dir_index = dom_convert_dir_to_idx (dir); | |
| 1460 | |
| 1461 return dom_computed[dir_index]; | |
| 1462 } | |
| 1463 | |
| 1464 /* Set the dominance availability for dominance info DIR to NEW_STATE. */ | |
| 1465 | |
| 1466 void | |
| 1467 set_dom_info_availability (enum cdi_direction dir, enum dom_state new_state) | |
| 1468 { | |
| 1469 unsigned int dir_index = dom_convert_dir_to_idx (dir); | |
| 1470 | |
| 1471 dom_computed[dir_index] = new_state; | |
| 1472 } | |
| 1473 | |
| 1474 /* Returns true if dominance information for direction DIR is available. */ | |
| 1475 | |
| 1476 bool | |
| 1477 dom_info_available_p (enum cdi_direction dir) | |
| 1478 { | |
| 1479 unsigned int dir_index = dom_convert_dir_to_idx (dir); | |
| 1480 | |
| 1481 return dom_computed[dir_index] != DOM_NONE; | |
| 1482 } | |
| 1483 | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1484 DEBUG_FUNCTION void |
| 0 | 1485 debug_dominance_info (enum cdi_direction dir) |
| 1486 { | |
| 1487 basic_block bb, bb2; | |
| 1488 FOR_EACH_BB (bb) | |
| 1489 if ((bb2 = get_immediate_dominator (dir, bb))) | |
| 1490 fprintf (stderr, "%i %i\n", bb->index, bb2->index); | |
| 1491 } | |
| 1492 | |
| 1493 /* Prints to stderr representation of the dominance tree (for direction DIR) | |
| 1494 rooted in ROOT, indented by INDENT tabulators. If INDENT_FIRST is false, | |
| 1495 the first line of the output is not indented. */ | |
| 1496 | |
| 1497 static void | |
| 1498 debug_dominance_tree_1 (enum cdi_direction dir, basic_block root, | |
| 1499 unsigned indent, bool indent_first) | |
| 1500 { | |
| 1501 basic_block son; | |
| 1502 unsigned i; | |
| 1503 bool first = true; | |
| 1504 | |
| 1505 if (indent_first) | |
| 1506 for (i = 0; i < indent; i++) | |
| 1507 fprintf (stderr, "\t"); | |
| 1508 fprintf (stderr, "%d\t", root->index); | |
| 1509 | |
| 1510 for (son = first_dom_son (dir, root); | |
| 1511 son; | |
| 1512 son = next_dom_son (dir, son)) | |
| 1513 { | |
| 1514 debug_dominance_tree_1 (dir, son, indent + 1, !first); | |
| 1515 first = false; | |
| 1516 } | |
| 1517 | |
| 1518 if (first) | |
| 1519 fprintf (stderr, "\n"); | |
| 1520 } | |
| 1521 | |
| 1522 /* Prints to stderr representation of the dominance tree (for direction DIR) | |
| 1523 rooted in ROOT. */ | |
| 1524 | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1525 DEBUG_FUNCTION void |
| 0 | 1526 debug_dominance_tree (enum cdi_direction dir, basic_block root) |
| 1527 { | |
| 1528 debug_dominance_tree_1 (dir, root, 0, false); | |
| 1529 } |