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