1 /* Calculate (post)dominators in slightly super-linear time. 2 Copyright (C) 2000-2018 Free Software Foundation, Inc. 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" 38 #include "backend.h" 39 #include "timevar.h" 40 #include "diagnostic-core.h" 41 #include "cfganal.h" 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 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. */ 58 59 class dom_info 60 { 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 76 /* The parent of a node in the DFS tree. */ 77 TBB *m_dfs_parent; 78 /* For a node x m_key[x] is roughly the node nearest to the root from which 79 exists a way to x only over nodes behind x. Such a node is also called 80 semidominator. */ 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 91 of x. */ 92 TBB *m_dom; 93 94 /* The following few fields implement the structures needed for disjoint 95 sets. */ 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 102 be understood as the next sibling of x. */ 103 TBB *m_set_child; 104 105 /* If b is the number of a basic block (BB->index), m_dfs_order[b] is the 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. */ 108 TBB *m_dfs_order; 109 /* Points to last element in m_dfs_order array. */ 110 TBB *m_dfs_last; 111 /* If x is the DFS-index of a node which corresponds with a basic block, 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; 117 118 /* This is the next free DFS number when creating the DFS tree. */ 119 unsigned int m_dfsnum; 120 /* The number of nodes in the DFS tree (==m_dfsnum-1). */ 121 unsigned int m_nodes; 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. */ 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; 138 }; 139 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); 167 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 } 176 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); 182 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). */ 190 191 dom_info::dom_info (function *fn, cdi_direction dir) 192 { 193 m_n_basic_blocks = n_basic_blocks_for_fn (fn); 194 195 dom_init (); 196 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]; 200 201 switch (dir) 202 { 203 case CDI_DOMINATORS: 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); 208 break; 209 case CDI_POST_DOMINATORS: 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); 214 break; 215 default: 216 gcc_unreachable (); 217 } 218 } 219 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 } 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 270 static inline unsigned int 271 dom_convert_dir_to_idx (cdi_direction dir) 272 { 273 gcc_checking_assert (dir == CDI_DOMINATORS || dir == CDI_POST_DOMINATORS); 274 return dir - 1; 275 } 276 277 /* Free all allocated memory in dom_info. */ 278 279 dom_info::~dom_info () 280 { 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); 293 } 294 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. */ 300 301 void 302 dom_info::calc_dfs_tree_nonrec (basic_block bb) 303 { 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); 308 309 /* Initialize the first edge. */ 310 edge_iterator ei = m_reverse ? ei_start (bb->preds) 311 : ei_start (bb->succs); 312 313 /* When the stack is empty we break out of this loop. */ 314 while (1) 315 { 316 basic_block bn; 317 edge_iterator einext; 318 319 /* This loop traverses edges e in depth first manner, and fills the 320 stack. */ 321 while (!ei_end_p (ei)) 322 { 323 edge e = ei_edge (ei); 324 325 /* Deduce from E the current and the next block (BB and BN), and the 326 next edge. */ 327 if (m_reverse) 328 { 329 bn = e->src; 330 331 /* If the next node BN is either already visited or a border 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]) 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; 346 if (bn == m_end_block || bn->dom[d_i] == NULL 347 || m_dfs_order[bn->index]) 348 { 349 ei_next (&ei); 350 continue; 351 } 352 bb = e->src; 353 einext = ei_start (bn->succs); 354 } 355 356 gcc_assert (bn != m_start_block); 357 358 /* Fill the DFS tree info calculatable _before_ recursing. */ 359 TBB my_i; 360 if (bb != m_start_block) 361 my_i = m_dfs_order[bb->index]; 362 else 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; 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 } 388 delete[] stack; 389 } 390 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. */ 395 396 void 397 dom_info::calc_dfs_tree () 398 { 399 *m_dfs_last = m_dfsnum; 400 m_dfs_to_bb[m_dfsnum] = m_start_block; 401 m_dfsnum++; 402 403 calc_dfs_tree_nonrec (m_start_block); 404 405 if (m_fake_exit_edge) 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 420 FOR_BB_BETWEEN (b, m_start_block->prev_bb, m_end_block, prev_bb) 421 { 422 if (EDGE_COUNT (b->succs) > 0) 423 { 424 if (m_dfs_order[b->index] == 0) 425 saw_unconnected = true; 426 continue; 427 } 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); 434 } 435 436 if (saw_unconnected) 437 { 438 FOR_BB_BETWEEN (b, m_start_block->prev_bb, m_end_block, prev_bb) 439 { 440 if (m_dfs_order[b->index]) 441 continue; 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]); 451 } 452 } 453 } 454 455 m_nodes = m_dfsnum - 1; 456 457 /* This aborts e.g. when there is _no_ path from ENTRY to EXIT at all. */ 458 gcc_assert (m_nodes == (unsigned int) m_n_basic_blocks - 1); 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 466 void 467 dom_info::compress (TBB v) 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(). */ 472 TBB parent = m_set_chain[v]; 473 if (m_set_chain[parent]) 474 { 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]; 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 486 inline TBB 487 dom_info::eval (TBB v) 488 { 489 /* The representative of the set V is in, also called root (as the set 490 representation is a tree). */ 491 TBB rep = m_set_chain[v]; 492 493 /* V itself is the root. */ 494 if (!rep) 495 return m_path_min[v]; 496 497 /* Compress only if necessary. */ 498 if (m_set_chain[rep]) 499 { 500 compress (v); 501 rep = m_set_chain[v]; 502 } 503 504 if (m_key[m_path_min[rep]] >= m_key[m_path_min[v]]) 505 return m_path_min[v]; 506 else 507 return m_path_min[rep]; 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 515 void 516 dom_info::link_roots (TBB v, TBB w) 517 { 518 TBB s = w; 519 520 /* Rebalance the tree. */ 521 while (m_key[m_path_min[w]] < m_key[m_path_min[m_set_child[s]]]) 522 { 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]]) 525 { 526 m_set_chain[m_set_child[s]] = s; 527 m_set_child[s] = m_set_child[m_set_child[s]]; 528 } 529 else 530 { 531 m_set_size[m_set_child[s]] = m_set_size[s]; 532 s = m_set_chain[s] = m_set_child[s]; 533 } 534 } 535 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); 540 541 /* Merge all subtrees. */ 542 while (s) 543 { 544 m_set_chain[s] = v; 545 s = m_set_child[s]; 546 } 547 } 548 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]. */ 552 553 void 554 dom_info::calc_idoms () 555 { 556 /* Go backwards in DFS order, to first look at the leafs. */ 557 for (TBB v = m_nodes; v > 1; v--) 558 { 559 basic_block bb = m_dfs_to_bb[v]; 560 edge e; 561 562 TBB par = m_dfs_parent[v]; 563 TBB k = v; 564 565 edge_iterator ei = m_reverse ? ei_start (bb->succs) 566 : ei_start (bb->preds); 567 edge_iterator einext; 568 569 if (m_fake_exit_edge) 570 { 571 /* If this block has a fake edge to exit, process that first. */ 572 if (bitmap_bit_p (m_fake_exit_edge, bb->index)) 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 { 586 basic_block b; 587 TBB k1; 588 589 e = ei_edge (ei); 590 b = m_reverse ? e->dest : e->src; 591 einext = ei; 592 ei_next (&einext); 593 594 if (b == m_start_block) 595 { 596 do_fake_exit_edge: 597 k1 = *m_dfs_last; 598 } 599 else 600 k1 = m_dfs_order[b->index]; 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) 605 k1 = m_key[eval (k1)]; 606 if (k1 < k) 607 k = k1; 608 609 ei = einext; 610 } 611 612 m_key[v] = k; 613 link_roots (par, v); 614 m_next_bucket[v] = m_bucket[k]; 615 m_bucket[k] = v; 616 617 /* Transform semidominators into dominators. */ 618 for (TBB w = m_bucket[par]; w; w = m_next_bucket[w]) 619 { 620 k = eval (w); 621 if (m_key[k] < m_key[w]) 622 m_dom[w] = k; 623 else 624 m_dom[w] = par; 625 } 626 /* We don't need to cleanup next_bucket[]. */ 627 m_bucket[par] = 0; 628 } 629 630 /* Explicitly define the dominators. */ 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]]; 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 666 gcc_checking_assert (dom_info_available_p (dir)); 667 668 if (dom_computed[dir_index] == DOM_OK) 669 return; 670 671 FOR_ALL_BB_FN (bb, cfun) 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 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 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 711 calculate_dominance_info (cdi_direction dir) 712 { 713 unsigned int dir_index = dom_convert_dir_to_idx (dir); 714 715 if (dom_computed[dir_index] == DOM_OK) 716 { 717 checking_verify_dominators (dir); 718 return; 719 } 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 726 basic_block b; 727 FOR_ALL_BB_FN (b, cfun) 728 { 729 b->dom[dir_index] = et_new_tree (b); 730 } 731 n_bbs_in_dom_tree[dir_index] = n_basic_blocks_for_fn (cfun); 732 733 dom_info di (cfun, dir); 734 di.calc_dfs_tree (); 735 di.calc_idoms (); 736 737 FOR_EACH_BB_FN (b, cfun) 738 { 739 if (basic_block d = di.get_idom (b)) 740 et_set_father (b->dom[dir_index], d->dom[dir_index]); 741 } 742 743 dom_computed[dir_index] = DOM_NO_FAST_QUERY; 744 } 745 else 746 checking_verify_dominators (dir); 747 748 compute_dom_fast_query (dir); 749 750 timevar_pop (TV_DOMINANCE); 751 } 752 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 790 /* Free dominance information for direction DIR. */ 791 void 792 free_dominance_info (function *fn, enum cdi_direction dir) 793 { 794 basic_block bb; 795 unsigned int dir_index = dom_convert_dir_to_idx (dir); 796 797 if (!dom_info_available_p (fn, dir)) 798 return; 799 800 FOR_ALL_BB_FN (bb, fn) 801 { 802 et_free_tree_force (bb->dom[dir_index]); 803 bb->dom[dir_index] = NULL; 804 } 805 et_free_pools (); 806 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. */ 819 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; 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 851 gcc_checking_assert (dom_computed[dir_index]); 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. */ 861 void 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]; 867 868 gcc_checking_assert (dom_computed[dir_index]); 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. */ 886 vec<basic_block> 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; 891 vec<basic_block> bbs = vNULL; 892 893 gcc_checking_assert (dom_computed[dir_index]); 894 895 if (!son) 896 return vNULL; 897 898 bbs.safe_push ((basic_block) son->data); 899 for (ason = son->right; ason != son; ason = ason->right) 900 bbs.safe_push ((basic_block) ason->data); 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. */ 908 909 vec<basic_block> 910 get_dominated_by_region (enum cdi_direction dir, basic_block *region, 911 unsigned n_region) 912 { 913 unsigned i; 914 basic_block dom; 915 vec<basic_block> doms = vNULL; 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)) 924 doms.safe_push (dom); 925 for (i = 0; i < n_region; i++) 926 region[i]->flags &= ~BB_DUPLICATED; 927 928 return doms; 929 } 930 931 /* Returns the list of basic blocks including BB dominated by BB, in the 932 direction DIR up to DEPTH in the dominator tree. The DEPTH of zero will 933 produce a vector containing all dominated blocks. The vector will be sorted 934 in preorder. */ 935 936 vec<basic_block> 937 get_dominated_to_depth (enum cdi_direction dir, basic_block bb, int depth) 938 { 939 vec<basic_block> bbs = vNULL; 940 unsigned i; 941 unsigned next_level_start; 942 943 i = 0; 944 bbs.safe_push (bb); 945 next_level_start = 1; /* = bbs.length (); */ 946 947 do 948 { 949 basic_block son; 950 951 bb = bbs[i++]; 952 for (son = first_dom_son (dir, bb); 953 son; 954 son = next_dom_son (dir, son)) 955 bbs.safe_push (son); 956 957 if (i == next_level_start && --depth) 958 next_level_start = bbs.length (); 959 } 960 while (i < next_level_start); 961 962 return bbs; 963 } 964 965 /* Returns the list of basic blocks including BB dominated by BB, in the 966 direction DIR. The vector will be sorted in preorder. */ 967 968 vec<basic_block> 969 get_all_dominated_blocks (enum cdi_direction dir, basic_block bb) 970 { 971 return get_dominated_to_depth (dir, bb, 0); 972 } 973 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; 981 982 bb_node = bb->dom[dir_index]; 983 to_node = to->dom[dir_index]; 984 985 gcc_checking_assert (dom_computed[dir_index]); 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 1008 gcc_checking_assert (dom_computed[dir_index]); 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; 1028 1029 first = bitmap_first_set_bit (blocks); 1030 dom = BASIC_BLOCK_FOR_FN (cfun, first); 1031 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi) 1032 if (dom != BASIC_BLOCK_FOR_FN (cfun, i)) 1033 dom = nearest_common_dominator (dir, dom, BASIC_BLOCK_FOR_FN (cfun, i)); 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. 1047 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: 1051 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 1065 1066 2. Node A is below node B (and thus, node B dominates node A) 1067 1068 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. 1077 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 1080 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 { 1103 return DFS_Number_In(A) <= DFS_Number_In(B) 1104 && DFS_Number_Out (A) >= DFS_Number_Out(B); 1105 } 1106 1107 A_Dominated_by_B (node A, node B) 1108 { 1109 return DFS_Number_In(A) >= DFS_Number_In(B) 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) 1116 { 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]; 1119 1120 gcc_checking_assert (dom_computed[dir_index]); 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 1137 gcc_checking_assert (dom_computed[dir_index] == DOM_OK); 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 1149 gcc_checking_assert (dom_computed[dir_index] == DOM_OK); 1150 return n->dfs_num_out; 1151 } 1152 1153 /* Verify invariants of dominator structure. */ 1154 DEBUG_FUNCTION void 1155 verify_dominators (cdi_direction dir) 1156 { 1157 gcc_assert (dom_info_available_p (dir)); 1158 1159 dom_info di (cfun, dir); 1160 di.calc_dfs_tree (); 1161 di.calc_idoms (); 1162 1163 bool err = false; 1164 basic_block bb; 1165 FOR_EACH_BB_FN (bb, cfun) 1166 { 1167 basic_block imm_bb = get_immediate_dominator (dir, bb); 1168 if (!imm_bb) 1169 { 1170 error ("dominator of %d status unknown", bb->index); 1171 err = true; 1172 continue; 1173 } 1174 1175 basic_block imm_bb_correct = di.get_idom (bb); 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); 1180 err = true; 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 1200 gcc_checking_assert (dom_computed[dir_index]); 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 1230 prune_bbs_to_update_dominators (vec<basic_block> bbs, 1231 bool conservative) 1232 { 1233 unsigned i; 1234 bool single; 1235 basic_block bb, dom = NULL; 1236 edge_iterator ei; 1237 edge e; 1238 1239 for (i = 0; bbs.iterate (i, &bb);) 1240 { 1241 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)) 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: 1282 bbs.unordered_remove (i); 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 1301 determine_dominators_for_sons (struct graph *g, vec<basic_block> bbs, 1302 int y, int *son, int *brother) 1303 { 1304 bitmap gprime; 1305 int i, a, nc; 1306 vec<int> *sccs; 1307 basic_block bb, dom, ybb; 1308 unsigned si; 1309 edge e; 1310 edge_iterator ei; 1311 1312 if (son[y] == -1) 1313 return; 1314 if (y == (int) bbs.length ()) 1315 ybb = ENTRY_BLOCK_PTR_FOR_FN (cfun); 1316 else 1317 ybb = bbs[y]; 1318 1319 if (brother[son[y]] == -1) 1320 { 1321 /* Handle the common case Y has just one son specially. */ 1322 bb = bbs[son[y]]; 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 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); 1340 for (a = son[y]; a != -1; a = brother[a]) 1341 sccs[g->vertices[a].component].safe_push (a); 1342 1343 for (i = nc - 1; i >= 0; i--) 1344 { 1345 dom = NULL; 1346 FOR_EACH_VEC_ELT (sccs[i], si, a) 1347 { 1348 bb = bbs[a]; 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); 1359 FOR_EACH_VEC_ELT (sccs[i], si, a) 1360 { 1361 bb = bbs[a]; 1362 set_immediate_dominator (CDI_DOMINATORS, bb, dom); 1363 } 1364 } 1365 1366 for (i = 0; i < nc; i++) 1367 sccs[i].release (); 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 1382 iterate_fix_dominators (enum cdi_direction dir, vec<basic_block> bbs, 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. */ 1402 gcc_checking_assert (dir == CDI_DOMINATORS && dom_computed[dir_index]); 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. */ 1460 FOR_EACH_VEC_ELT (bbs, i, bb) 1461 set_immediate_dominator (CDI_DOMINATORS, bb, NULL); 1462 } 1463 1464 prune_bbs_to_update_dominators (bbs, conservative); 1465 n = bbs.length (); 1466 1467 if (n == 0) 1468 return; 1469 1470 if (n == 1) 1471 { 1472 bb = bbs[0]; 1473 set_immediate_dominator (CDI_DOMINATORS, bb, 1474 recompute_dominator (CDI_DOMINATORS, bb)); 1475 return; 1476 } 1477 1478 /* Construct the graph G. */ 1479 hash_map<basic_block, int> map (251); 1480 FOR_EACH_VEC_ELT (bbs, i, bb) 1481 { 1482 /* If the dominance tree is conservatively correct, split it now. */ 1483 if (conservative) 1484 set_immediate_dominator (CDI_DOMINATORS, bb, NULL); 1485 map.put (bb, i); 1486 } 1487 map.put (ENTRY_BLOCK_PTR_FOR_FN (cfun), n); 1488 1489 g = new_graph (n + 1); 1490 for (y = 0; y < g->n_vertices; y++) 1491 g->vertices[y].data = BITMAP_ALLOC (NULL); 1492 FOR_EACH_VEC_ELT (bbs, i, bb) 1493 { 1494 FOR_EACH_EDGE (e, ei, bb->preds) 1495 { 1496 dom = root_of_dom_tree (CDI_DOMINATORS, e->src); 1497 if (dom == bb) 1498 continue; 1499 1500 dom_i = *map.get (dom); 1501 1502 /* Do not include parallel edges to G. */ 1503 if (!bitmap_set_bit ((bitmap) g->vertices[dom_i].data, i)) 1504 continue; 1505 1506 add_edge (g, dom_i, i); 1507 } 1508 } 1509 for (y = 0; y < g->n_vertices; y++) 1510 BITMAP_FREE (g->vertices[y].data); 1511 1512 /* Find the dominator tree of G. */ 1513 son = XNEWVEC (int, n + 1); 1514 brother = XNEWVEC (int, n + 1); 1515 parent = XNEWVEC (int, n + 1); 1516 graphds_domtree (g, n, parent, son, brother); 1517 1518 /* Finally, traverse the tree and find the immediate dominators. */ 1519 for (y = n; son[y] != -1; y = son[y]) 1520 continue; 1521 while (y != -1) 1522 { 1523 determine_dominators_for_sons (g, bbs, y, son, brother); 1524 1525 if (brother[y] != -1) 1526 { 1527 y = brother[y]; 1528 while (son[y] != -1) 1529 y = son[y]; 1530 } 1531 else 1532 y = parent[y]; 1533 } 1534 1535 free (son); 1536 free (brother); 1537 free (parent); 1538 1539 free_graph (g); 1540 } 1541 1542 void 1543 add_to_dominance_info (enum cdi_direction dir, basic_block bb) 1544 { 1545 unsigned int dir_index = dom_convert_dir_to_idx (dir); 1546 1547 gcc_checking_assert (dom_computed[dir_index] && !bb->dom[dir_index]); 1548 1549 n_bbs_in_dom_tree[dir_index]++; 1550 1551 bb->dom[dir_index] = et_new_tree (bb); 1552 1553 if (dom_computed[dir_index] == DOM_OK) 1554 dom_computed[dir_index] = DOM_NO_FAST_QUERY; 1555 } 1556 1557 void 1558 delete_from_dominance_info (enum cdi_direction dir, basic_block bb) 1559 { 1560 unsigned int dir_index = dom_convert_dir_to_idx (dir); 1561 1562 gcc_checking_assert (dom_computed[dir_index]); 1563 1564 et_free_tree (bb->dom[dir_index]); 1565 bb->dom[dir_index] = NULL; 1566 n_bbs_in_dom_tree[dir_index]--; 1567 1568 if (dom_computed[dir_index] == DOM_OK) 1569 dom_computed[dir_index] = DOM_NO_FAST_QUERY; 1570 } 1571 1572 /* Returns the first son of BB in the dominator or postdominator tree 1573 as determined by DIR. */ 1574 1575 basic_block 1576 first_dom_son (enum cdi_direction dir, basic_block bb) 1577 { 1578 unsigned int dir_index = dom_convert_dir_to_idx (dir); 1579 struct et_node *son = bb->dom[dir_index]->son; 1580 1581 return (basic_block) (son ? son->data : NULL); 1582 } 1583 1584 /* Returns the next dominance son after BB in the dominator or postdominator 1585 tree as determined by DIR, or NULL if it was the last one. */ 1586 1587 basic_block 1588 next_dom_son (enum cdi_direction dir, basic_block bb) 1589 { 1590 unsigned int dir_index = dom_convert_dir_to_idx (dir); 1591 struct et_node *next = bb->dom[dir_index]->right; 1592 1593 return (basic_block) (next->father->son == next ? NULL : next->data); 1594 } 1595 1596 /* Return dominance availability for dominance info DIR. */ 1597 1598 enum dom_state 1599 dom_info_state (function *fn, enum cdi_direction dir) 1600 { 1601 if (!fn->cfg) 1602 return DOM_NONE; 1603 1604 unsigned int dir_index = dom_convert_dir_to_idx (dir); 1605 return fn->cfg->x_dom_computed[dir_index]; 1606 } 1607 1608 enum dom_state 1609 dom_info_state (enum cdi_direction dir) 1610 { 1611 return dom_info_state (cfun, dir); 1612 } 1613 1614 /* Set the dominance availability for dominance info DIR to NEW_STATE. */ 1615 1616 void 1617 set_dom_info_availability (enum cdi_direction dir, enum dom_state new_state) 1618 { 1619 unsigned int dir_index = dom_convert_dir_to_idx (dir); 1620 1621 dom_computed[dir_index] = new_state; 1622 } 1623 1624 /* Returns true if dominance information for direction DIR is available. */ 1625 1626 bool 1627 dom_info_available_p (function *fn, enum cdi_direction dir) 1628 { 1629 return dom_info_state (fn, dir) != DOM_NONE; 1630 } 1631 1632 bool 1633 dom_info_available_p (enum cdi_direction dir) 1634 { 1635 return dom_info_available_p (cfun, dir); 1636 } 1637 1638 DEBUG_FUNCTION void 1639 debug_dominance_info (enum cdi_direction dir) 1640 { 1641 basic_block bb, bb2; 1642 FOR_EACH_BB_FN (bb, cfun) 1643 if ((bb2 = get_immediate_dominator (dir, bb))) 1644 fprintf (stderr, "%i %i\n", bb->index, bb2->index); 1645 } 1646 1647 /* Prints to stderr representation of the dominance tree (for direction DIR) 1648 rooted in ROOT, indented by INDENT tabulators. If INDENT_FIRST is false, 1649 the first line of the output is not indented. */ 1650 1651 static void 1652 debug_dominance_tree_1 (enum cdi_direction dir, basic_block root, 1653 unsigned indent, bool indent_first) 1654 { 1655 basic_block son; 1656 unsigned i; 1657 bool first = true; 1658 1659 if (indent_first) 1660 for (i = 0; i < indent; i++) 1661 fprintf (stderr, "\t"); 1662 fprintf (stderr, "%d\t", root->index); 1663 1664 for (son = first_dom_son (dir, root); 1665 son; 1666 son = next_dom_son (dir, son)) 1667 { 1668 debug_dominance_tree_1 (dir, son, indent + 1, !first); 1669 first = false; 1670 } 1671 1672 if (first) 1673 fprintf (stderr, "\n"); 1674 } 1675 1676 /* Prints to stderr representation of the dominance tree (for direction DIR) 1677 rooted in ROOT. */ 1678 1679 DEBUG_FUNCTION void 1680 debug_dominance_tree (enum cdi_direction dir, basic_block root) 1681 { 1682 debug_dominance_tree_1 (dir, root, 0, false); 1683 } 1684