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