1/* Calculate (post)dominators in slightly super-linear time. 2 Copyright (C) 2000, 2003, 2004, 2005 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 2, 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 COPYING. If not, write to the Free 19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20 02110-1301, USA. */ 21 22/* This file implements the well known algorithm from Lengauer and Tarjan 23 to compute the dominators in a control flow graph. A basic block D is said 24 to dominate another block X, when all paths from the entry node of the CFG 25 to X go also over D. The dominance relation is a transitive reflexive 26 relation and its minimal transitive reduction is a tree, called the 27 dominator tree. So for each block X besides the entry block exists a 28 block I(X), called the immediate dominator of X, which is the parent of X 29 in the dominator tree. 30 31 The algorithm computes this dominator tree implicitly by computing for 32 each block its immediate dominator. We use tree balancing and path 33 compression, so it's the O(e*a(e,v)) variant, where a(e,v) is the very 34 slowly growing functional inverse of the Ackerman function. */ 35 36#include "config.h" 37#include "system.h" 38#include "coretypes.h" 39#include "tm.h" 40#include "rtl.h" 41#include "hard-reg-set.h" 42#include "obstack.h" 43#include "basic-block.h" 44#include "toplev.h" 45#include "et-forest.h" 46 47/* Whether the dominators and the postdominators are available. */ 48enum dom_state dom_computed[2]; 49 50/* We name our nodes with integers, beginning with 1. Zero is reserved for 51 'undefined' or 'end of list'. The name of each node is given by the dfs 52 number of the corresponding basic block. Please note, that we include the 53 artificial ENTRY_BLOCK (or EXIT_BLOCK in the post-dom case) in our lists to 54 support multiple entry points. As it has no real basic block index we use 55 'last_basic_block' for that. Its dfs number is of course 1. */ 56 57/* Type of Basic Block aka. TBB */ 58typedef unsigned int TBB; 59 60/* We work in a poor-mans object oriented fashion, and carry an instance of 61 this structure through all our 'methods'. It holds various arrays 62 reflecting the (sub)structure of the flowgraph. Most of them are of type 63 TBB and are also indexed by TBB. */ 64 65struct dom_info 66{ 67 /* The parent of a node in the DFS tree. */ 68 TBB *dfs_parent; 69 /* For a node x key[x] is roughly the node nearest to the root from which 70 exists a way to x only over nodes behind x. Such a node is also called 71 semidominator. */ 72 TBB *key; 73 /* The value in path_min[x] is the node y on the path from x to the root of 74 the tree x is in with the smallest key[y]. */ 75 TBB *path_min; 76 /* bucket[x] points to the first node of the set of nodes having x as key. */ 77 TBB *bucket; 78 /* And next_bucket[x] points to the next node. */ 79 TBB *next_bucket; 80 /* After the algorithm is done, dom[x] contains the immediate dominator 81 of x. */ 82 TBB *dom; 83 84 /* The following few fields implement the structures needed for disjoint 85 sets. */ 86 /* set_chain[x] is the next node on the path from x to the representant 87 of the set containing x. If set_chain[x]==0 then x is a root. */ 88 TBB *set_chain; 89 /* set_size[x] is the number of elements in the set named by x. */ 90 unsigned int *set_size; 91 /* set_child[x] is used for balancing the tree representing a set. It can 92 be understood as the next sibling of x. */ 93 TBB *set_child; 94 95 /* If b is the number of a basic block (BB->index), dfs_order[b] is the 96 number of that node in DFS order counted from 1. This is an index 97 into most of the other arrays in this structure. */ 98 TBB *dfs_order; 99 /* If x is the DFS-index of a node which corresponds with a basic block, 100 dfs_to_bb[x] is that basic block. Note, that in our structure there are 101 more nodes that basic blocks, so only dfs_to_bb[dfs_order[bb->index]]==bb 102 is true for every basic block bb, but not the opposite. */ 103 basic_block *dfs_to_bb; 104 105 /* This is the next free DFS number when creating the DFS tree. */ 106 unsigned int dfsnum; 107 /* The number of nodes in the DFS tree (==dfsnum-1). */ 108 unsigned int nodes; 109 110 /* Blocks with bits set here have a fake edge to EXIT. These are used 111 to turn a DFS forest into a proper tree. */ 112 bitmap fake_exit_edge; 113}; 114 115static void init_dom_info (struct dom_info *, enum cdi_direction); 116static void free_dom_info (struct dom_info *); 117static void calc_dfs_tree_nonrec (struct dom_info *, basic_block, 118 enum cdi_direction); 119static void calc_dfs_tree (struct dom_info *, enum cdi_direction); 120static void compress (struct dom_info *, TBB); 121static TBB eval (struct dom_info *, TBB); 122static void link_roots (struct dom_info *, TBB, TBB); 123static void calc_idoms (struct dom_info *, enum cdi_direction); 124void debug_dominance_info (enum cdi_direction); 125 126/* Keeps track of the*/ 127static unsigned n_bbs_in_dom_tree[2]; 128 129/* Helper macro for allocating and initializing an array, 130 for aesthetic reasons. */ 131#define init_ar(var, type, num, content) \ 132 do \ 133 { \ 134 unsigned int i = 1; /* Catch content == i. */ \ 135 if (! (content)) \ 136 (var) = xcalloc ((num), sizeof (type)); \ 137 else \ 138 { \ 139 (var) = xmalloc ((num) * sizeof (type)); \ 140 for (i = 0; i < num; i++) \ 141 (var)[i] = (content); \ 142 } \ 143 } \ 144 while (0) 145 146/* Allocate all needed memory in a pessimistic fashion (so we round up). 147 This initializes the contents of DI, which already must be allocated. */ 148 149static void 150init_dom_info (struct dom_info *di, enum cdi_direction dir) 151{ 152 /* We need memory for n_basic_blocks nodes and the ENTRY_BLOCK or 153 EXIT_BLOCK. */ 154 unsigned int num = n_basic_blocks + 1 + 1; 155 init_ar (di->dfs_parent, TBB, num, 0); 156 init_ar (di->path_min, TBB, num, i); 157 init_ar (di->key, TBB, num, i); 158 init_ar (di->dom, TBB, num, 0); 159 160 init_ar (di->bucket, TBB, num, 0); 161 init_ar (di->next_bucket, TBB, num, 0); 162 163 init_ar (di->set_chain, TBB, num, 0); 164 init_ar (di->set_size, unsigned int, num, 1); 165 init_ar (di->set_child, TBB, num, 0); 166 167 init_ar (di->dfs_order, TBB, (unsigned int) last_basic_block + 1, 0); 168 init_ar (di->dfs_to_bb, basic_block, num, 0); 169 170 di->dfsnum = 1; 171 di->nodes = 0; 172 173 di->fake_exit_edge = dir ? BITMAP_ALLOC (NULL) : NULL; 174} 175 176#undef init_ar 177 178/* Free all allocated memory in DI, but not DI itself. */ 179 180static void 181free_dom_info (struct dom_info *di) 182{ 183 free (di->dfs_parent); 184 free (di->path_min); 185 free (di->key); 186 free (di->dom); 187 free (di->bucket); 188 free (di->next_bucket); 189 free (di->set_chain); 190 free (di->set_size); 191 free (di->set_child); 192 free (di->dfs_order); 193 free (di->dfs_to_bb); 194 BITMAP_FREE (di->fake_exit_edge); 195} 196 197/* The nonrecursive variant of creating a DFS tree. DI is our working 198 structure, BB the starting basic block for this tree and REVERSE 199 is true, if predecessors should be visited instead of successors of a 200 node. After this is done all nodes reachable from BB were visited, have 201 assigned their dfs number and are linked together to form a tree. */ 202 203static void 204calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb, 205 enum cdi_direction reverse) 206{ 207 /* We call this _only_ if bb is not already visited. */ 208 edge e; 209 TBB child_i, my_i = 0; 210 edge_iterator *stack; 211 edge_iterator ei, einext; 212 int sp; 213 /* Start block (ENTRY_BLOCK_PTR for forward problem, EXIT_BLOCK for backward 214 problem). */ 215 basic_block en_block; 216 /* Ending block. */ 217 basic_block ex_block; 218 219 stack = xmalloc ((n_basic_blocks + 3) * sizeof (edge_iterator)); 220 sp = 0; 221 222 /* Initialize our border blocks, and the first edge. */ 223 if (reverse) 224 { 225 ei = ei_start (bb->preds); 226 en_block = EXIT_BLOCK_PTR; 227 ex_block = ENTRY_BLOCK_PTR; 228 } 229 else 230 { 231 ei = ei_start (bb->succs); 232 en_block = ENTRY_BLOCK_PTR; 233 ex_block = EXIT_BLOCK_PTR; 234 } 235 236 /* When the stack is empty we break out of this loop. */ 237 while (1) 238 { 239 basic_block bn; 240 241 /* This loop traverses edges e in depth first manner, and fills the 242 stack. */ 243 while (!ei_end_p (ei)) 244 { 245 e = ei_edge (ei); 246 247 /* Deduce from E the current and the next block (BB and BN), and the 248 next edge. */ 249 if (reverse) 250 { 251 bn = e->src; 252 253 /* If the next node BN is either already visited or a border 254 block the current edge is useless, and simply overwritten 255 with the next edge out of the current node. */ 256 if (bn == ex_block || di->dfs_order[bn->index]) 257 { 258 ei_next (&ei); 259 continue; 260 } 261 bb = e->dest; 262 einext = ei_start (bn->preds); 263 } 264 else 265 { 266 bn = e->dest; 267 if (bn == ex_block || di->dfs_order[bn->index]) 268 { 269 ei_next (&ei); 270 continue; 271 } 272 bb = e->src; 273 einext = ei_start (bn->succs); 274 } 275 276 gcc_assert (bn != en_block); 277 278 /* Fill the DFS tree info calculatable _before_ recursing. */ 279 if (bb != en_block) 280 my_i = di->dfs_order[bb->index]; 281 else 282 my_i = di->dfs_order[last_basic_block]; 283 child_i = di->dfs_order[bn->index] = di->dfsnum++; 284 di->dfs_to_bb[child_i] = bn; 285 di->dfs_parent[child_i] = my_i; 286 287 /* Save the current point in the CFG on the stack, and recurse. */ 288 stack[sp++] = ei; 289 ei = einext; 290 } 291 292 if (!sp) 293 break; 294 ei = stack[--sp]; 295 296 /* OK. The edge-list was exhausted, meaning normally we would 297 end the recursion. After returning from the recursive call, 298 there were (may be) other statements which were run after a 299 child node was completely considered by DFS. Here is the 300 point to do it in the non-recursive variant. 301 E.g. The block just completed is in e->dest for forward DFS, 302 the block not yet completed (the parent of the one above) 303 in e->src. This could be used e.g. for computing the number of 304 descendants or the tree depth. */ 305 ei_next (&ei); 306 } 307 free (stack); 308} 309 310/* The main entry for calculating the DFS tree or forest. DI is our working 311 structure and REVERSE is true, if we are interested in the reverse flow 312 graph. In that case the result is not necessarily a tree but a forest, 313 because there may be nodes from which the EXIT_BLOCK is unreachable. */ 314 315static void 316calc_dfs_tree (struct dom_info *di, enum cdi_direction reverse) 317{ 318 /* The first block is the ENTRY_BLOCK (or EXIT_BLOCK if REVERSE). */ 319 basic_block begin = reverse ? EXIT_BLOCK_PTR : ENTRY_BLOCK_PTR; 320 di->dfs_order[last_basic_block] = di->dfsnum; 321 di->dfs_to_bb[di->dfsnum] = begin; 322 di->dfsnum++; 323 324 calc_dfs_tree_nonrec (di, begin, reverse); 325 326 if (reverse) 327 { 328 /* In the post-dom case we may have nodes without a path to EXIT_BLOCK. 329 They are reverse-unreachable. In the dom-case we disallow such 330 nodes, but in post-dom we have to deal with them. 331 332 There are two situations in which this occurs. First, noreturn 333 functions. Second, infinite loops. In the first case we need to 334 pretend that there is an edge to the exit block. In the second 335 case, we wind up with a forest. We need to process all noreturn 336 blocks before we know if we've got any infinite loops. */ 337 338 basic_block b; 339 bool saw_unconnected = false; 340 341 FOR_EACH_BB_REVERSE (b) 342 { 343 if (EDGE_COUNT (b->succs) > 0) 344 { 345 if (di->dfs_order[b->index] == 0) 346 saw_unconnected = true; 347 continue; 348 } 349 bitmap_set_bit (di->fake_exit_edge, b->index); 350 di->dfs_order[b->index] = di->dfsnum; 351 di->dfs_to_bb[di->dfsnum] = b; 352 di->dfs_parent[di->dfsnum] = di->dfs_order[last_basic_block]; 353 di->dfsnum++; 354 calc_dfs_tree_nonrec (di, b, reverse); 355 } 356 357 if (saw_unconnected) 358 { 359 FOR_EACH_BB_REVERSE (b) 360 { 361 if (di->dfs_order[b->index]) 362 continue; 363 bitmap_set_bit (di->fake_exit_edge, b->index); 364 di->dfs_order[b->index] = di->dfsnum; 365 di->dfs_to_bb[di->dfsnum] = b; 366 di->dfs_parent[di->dfsnum] = di->dfs_order[last_basic_block]; 367 di->dfsnum++; 368 calc_dfs_tree_nonrec (di, b, reverse); 369 } 370 } 371 } 372 373 di->nodes = di->dfsnum - 1; 374 375 /* Make sure there is a path from ENTRY to EXIT at all. */ 376 gcc_assert (di->nodes == (unsigned int) n_basic_blocks + 1); 377} 378 379/* Compress the path from V to the root of its set and update path_min at the 380 same time. After compress(di, V) set_chain[V] is the root of the set V is 381 in and path_min[V] is the node with the smallest key[] value on the path 382 from V to that root. */ 383 384static void 385compress (struct dom_info *di, TBB v) 386{ 387 /* Btw. It's not worth to unrecurse compress() as the depth is usually not 388 greater than 5 even for huge graphs (I've not seen call depth > 4). 389 Also performance wise compress() ranges _far_ behind eval(). */ 390 TBB parent = di->set_chain[v]; 391 if (di->set_chain[parent]) 392 { 393 compress (di, parent); 394 if (di->key[di->path_min[parent]] < di->key[di->path_min[v]]) 395 di->path_min[v] = di->path_min[parent]; 396 di->set_chain[v] = di->set_chain[parent]; 397 } 398} 399 400/* Compress the path from V to the set root of V if needed (when the root has 401 changed since the last call). Returns the node with the smallest key[] 402 value on the path from V to the root. */ 403 404static inline TBB 405eval (struct dom_info *di, TBB v) 406{ 407 /* The representant of the set V is in, also called root (as the set 408 representation is a tree). */ 409 TBB rep = di->set_chain[v]; 410 411 /* V itself is the root. */ 412 if (!rep) 413 return di->path_min[v]; 414 415 /* Compress only if necessary. */ 416 if (di->set_chain[rep]) 417 { 418 compress (di, v); 419 rep = di->set_chain[v]; 420 } 421 422 if (di->key[di->path_min[rep]] >= di->key[di->path_min[v]]) 423 return di->path_min[v]; 424 else 425 return di->path_min[rep]; 426} 427 428/* This essentially merges the two sets of V and W, giving a single set with 429 the new root V. The internal representation of these disjoint sets is a 430 balanced tree. Currently link(V,W) is only used with V being the parent 431 of W. */ 432 433static void 434link_roots (struct dom_info *di, TBB v, TBB w) 435{ 436 TBB s = w; 437 438 /* Rebalance the tree. */ 439 while (di->key[di->path_min[w]] < di->key[di->path_min[di->set_child[s]]]) 440 { 441 if (di->set_size[s] + di->set_size[di->set_child[di->set_child[s]]] 442 >= 2 * di->set_size[di->set_child[s]]) 443 { 444 di->set_chain[di->set_child[s]] = s; 445 di->set_child[s] = di->set_child[di->set_child[s]]; 446 } 447 else 448 { 449 di->set_size[di->set_child[s]] = di->set_size[s]; 450 s = di->set_chain[s] = di->set_child[s]; 451 } 452 } 453 454 di->path_min[s] = di->path_min[w]; 455 di->set_size[v] += di->set_size[w]; 456 if (di->set_size[v] < 2 * di->set_size[w]) 457 { 458 TBB tmp = s; 459 s = di->set_child[v]; 460 di->set_child[v] = tmp; 461 } 462 463 /* Merge all subtrees. */ 464 while (s) 465 { 466 di->set_chain[s] = v; 467 s = di->set_child[s]; 468 } 469} 470 471/* This calculates the immediate dominators (or post-dominators if REVERSE is 472 true). DI is our working structure and should hold the DFS forest. 473 On return the immediate dominator to node V is in di->dom[V]. */ 474 475static void 476calc_idoms (struct dom_info *di, enum cdi_direction reverse) 477{ 478 TBB v, w, k, par; 479 basic_block en_block; 480 edge_iterator ei, einext; 481 482 if (reverse) 483 en_block = EXIT_BLOCK_PTR; 484 else 485 en_block = ENTRY_BLOCK_PTR; 486 487 /* Go backwards in DFS order, to first look at the leafs. */ 488 v = di->nodes; 489 while (v > 1) 490 { 491 basic_block bb = di->dfs_to_bb[v]; 492 edge e; 493 494 par = di->dfs_parent[v]; 495 k = v; 496 497 ei = (reverse) ? ei_start (bb->succs) : ei_start (bb->preds); 498 499 if (reverse) 500 { 501 /* If this block has a fake edge to exit, process that first. */ 502 if (bitmap_bit_p (di->fake_exit_edge, bb->index)) 503 { 504 einext = ei; 505 einext.index = 0; 506 goto do_fake_exit_edge; 507 } 508 } 509 510 /* Search all direct predecessors for the smallest node with a path 511 to them. That way we have the smallest node with also a path to 512 us only over nodes behind us. In effect we search for our 513 semidominator. */ 514 while (!ei_end_p (ei)) 515 { 516 TBB k1; 517 basic_block b; 518 519 e = ei_edge (ei); 520 b = (reverse) ? e->dest : e->src; 521 einext = ei; 522 ei_next (&einext); 523 524 if (b == en_block) 525 { 526 do_fake_exit_edge: 527 k1 = di->dfs_order[last_basic_block]; 528 } 529 else 530 k1 = di->dfs_order[b->index]; 531 532 /* Call eval() only if really needed. If k1 is above V in DFS tree, 533 then we know, that eval(k1) == k1 and key[k1] == k1. */ 534 if (k1 > v) 535 k1 = di->key[eval (di, k1)]; 536 if (k1 < k) 537 k = k1; 538 539 ei = einext; 540 } 541 542 di->key[v] = k; 543 link_roots (di, par, v); 544 di->next_bucket[v] = di->bucket[k]; 545 di->bucket[k] = v; 546 547 /* Transform semidominators into dominators. */ 548 for (w = di->bucket[par]; w; w = di->next_bucket[w]) 549 { 550 k = eval (di, w); 551 if (di->key[k] < di->key[w]) 552 di->dom[w] = k; 553 else 554 di->dom[w] = par; 555 } 556 /* We don't need to cleanup next_bucket[]. */ 557 di->bucket[par] = 0; 558 v--; 559 } 560 561 /* Explicitly define the dominators. */ 562 di->dom[1] = 0; 563 for (v = 2; v <= di->nodes; v++) 564 if (di->dom[v] != di->key[v]) 565 di->dom[v] = di->dom[di->dom[v]]; 566} 567 568/* Assign dfs numbers starting from NUM to NODE and its sons. */ 569 570static void 571assign_dfs_numbers (struct et_node *node, int *num) 572{ 573 struct et_node *son; 574 575 node->dfs_num_in = (*num)++; 576 577 if (node->son) 578 { 579 assign_dfs_numbers (node->son, num); 580 for (son = node->son->right; son != node->son; son = son->right) 581 assign_dfs_numbers (son, num); 582 } 583 584 node->dfs_num_out = (*num)++; 585} 586 587/* Compute the data necessary for fast resolving of dominator queries in a 588 static dominator tree. */ 589 590static void 591compute_dom_fast_query (enum cdi_direction dir) 592{ 593 int num = 0; 594 basic_block bb; 595 596 gcc_assert (dom_info_available_p (dir)); 597 598 if (dom_computed[dir] == DOM_OK) 599 return; 600 601 FOR_ALL_BB (bb) 602 { 603 if (!bb->dom[dir]->father) 604 assign_dfs_numbers (bb->dom[dir], &num); 605 } 606 607 dom_computed[dir] = DOM_OK; 608} 609 610/* The main entry point into this module. DIR is set depending on whether 611 we want to compute dominators or postdominators. */ 612 613void 614calculate_dominance_info (enum cdi_direction dir) 615{ 616 struct dom_info di; 617 basic_block b; 618 619 if (dom_computed[dir] == DOM_OK) 620 return; 621 622 if (!dom_info_available_p (dir)) 623 { 624 gcc_assert (!n_bbs_in_dom_tree[dir]); 625 626 FOR_ALL_BB (b) 627 { 628 b->dom[dir] = et_new_tree (b); 629 } 630 n_bbs_in_dom_tree[dir] = n_basic_blocks + 2; 631 632 init_dom_info (&di, dir); 633 calc_dfs_tree (&di, dir); 634 calc_idoms (&di, dir); 635 636 FOR_EACH_BB (b) 637 { 638 TBB d = di.dom[di.dfs_order[b->index]]; 639 640 if (di.dfs_to_bb[d]) 641 et_set_father (b->dom[dir], di.dfs_to_bb[d]->dom[dir]); 642 } 643 644 free_dom_info (&di); 645 dom_computed[dir] = DOM_NO_FAST_QUERY; 646 } 647 648 compute_dom_fast_query (dir); 649} 650 651/* Free dominance information for direction DIR. */ 652void 653free_dominance_info (enum cdi_direction dir) 654{ 655 basic_block bb; 656 657 if (!dom_info_available_p (dir)) 658 return; 659 660 FOR_ALL_BB (bb) 661 { 662 et_free_tree_force (bb->dom[dir]); 663 bb->dom[dir] = NULL; 664 } 665 666 n_bbs_in_dom_tree[dir] = 0; 667 668 dom_computed[dir] = DOM_NONE; 669} 670 671/* Return the immediate dominator of basic block BB. */ 672basic_block 673get_immediate_dominator (enum cdi_direction dir, basic_block bb) 674{ 675 struct et_node *node = bb->dom[dir]; 676 677 gcc_assert (dom_computed[dir]); 678 679 if (!node->father) 680 return NULL; 681 682 return node->father->data; 683} 684 685/* Set the immediate dominator of the block possibly removing 686 existing edge. NULL can be used to remove any edge. */ 687inline void 688set_immediate_dominator (enum cdi_direction dir, basic_block bb, 689 basic_block dominated_by) 690{ 691 struct et_node *node = bb->dom[dir]; 692 693 gcc_assert (dom_computed[dir]); 694 695 if (node->father) 696 { 697 if (node->father->data == dominated_by) 698 return; 699 et_split (node); 700 } 701 702 if (dominated_by) 703 et_set_father (node, dominated_by->dom[dir]); 704 705 if (dom_computed[dir] == DOM_OK) 706 dom_computed[dir] = DOM_NO_FAST_QUERY; 707} 708 709/* Store all basic blocks immediately dominated by BB into BBS and return 710 their number. */ 711int 712get_dominated_by (enum cdi_direction dir, basic_block bb, basic_block **bbs) 713{ 714 int n; 715 struct et_node *node = bb->dom[dir], *son = node->son, *ason; 716 717 gcc_assert (dom_computed[dir]); 718 719 if (!son) 720 { 721 *bbs = NULL; 722 return 0; 723 } 724 725 for (ason = son->right, n = 1; ason != son; ason = ason->right) 726 n++; 727 728 *bbs = xmalloc (n * sizeof (basic_block)); 729 (*bbs)[0] = son->data; 730 for (ason = son->right, n = 1; ason != son; ason = ason->right) 731 (*bbs)[n++] = ason->data; 732 733 return n; 734} 735 736/* Find all basic blocks that are immediately dominated (in direction DIR) 737 by some block between N_REGION ones stored in REGION, except for blocks 738 in the REGION itself. The found blocks are stored to DOMS and their number 739 is returned. */ 740 741unsigned 742get_dominated_by_region (enum cdi_direction dir, basic_block *region, 743 unsigned n_region, basic_block *doms) 744{ 745 unsigned n_doms = 0, i; 746 basic_block dom; 747 748 for (i = 0; i < n_region; i++) 749 region[i]->flags |= BB_DUPLICATED; 750 for (i = 0; i < n_region; i++) 751 for (dom = first_dom_son (dir, region[i]); 752 dom; 753 dom = next_dom_son (dir, dom)) 754 if (!(dom->flags & BB_DUPLICATED)) 755 doms[n_doms++] = dom; 756 for (i = 0; i < n_region; i++) 757 region[i]->flags &= ~BB_DUPLICATED; 758 759 return n_doms; 760} 761 762/* Redirect all edges pointing to BB to TO. */ 763void 764redirect_immediate_dominators (enum cdi_direction dir, basic_block bb, 765 basic_block to) 766{ 767 struct et_node *bb_node = bb->dom[dir], *to_node = to->dom[dir], *son; 768 769 gcc_assert (dom_computed[dir]); 770 771 if (!bb_node->son) 772 return; 773 774 while (bb_node->son) 775 { 776 son = bb_node->son; 777 778 et_split (son); 779 et_set_father (son, to_node); 780 } 781 782 if (dom_computed[dir] == DOM_OK) 783 dom_computed[dir] = DOM_NO_FAST_QUERY; 784} 785 786/* Find first basic block in the tree dominating both BB1 and BB2. */ 787basic_block 788nearest_common_dominator (enum cdi_direction dir, basic_block bb1, basic_block bb2) 789{ 790 gcc_assert (dom_computed[dir]); 791 792 if (!bb1) 793 return bb2; 794 if (!bb2) 795 return bb1; 796 797 return et_nca (bb1->dom[dir], bb2->dom[dir])->data; 798} 799 800 801/* Find the nearest common dominator for the basic blocks in BLOCKS, 802 using dominance direction DIR. */ 803 804basic_block 805nearest_common_dominator_for_set (enum cdi_direction dir, bitmap blocks) 806{ 807 unsigned i, first; 808 bitmap_iterator bi; 809 basic_block dom; 810 811 first = bitmap_first_set_bit (blocks); 812 dom = BASIC_BLOCK (first); 813 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi) 814 if (dom != BASIC_BLOCK (i)) 815 dom = nearest_common_dominator (dir, dom, BASIC_BLOCK (i)); 816 817 return dom; 818} 819 820 821/* Return TRUE in case BB1 is dominated by BB2. */ 822bool 823dominated_by_p (enum cdi_direction dir, basic_block bb1, basic_block bb2) 824{ 825 struct et_node *n1 = bb1->dom[dir], *n2 = bb2->dom[dir]; 826 827 gcc_assert (dom_computed[dir]); 828 829 if (dom_computed[dir] == DOM_OK) 830 return (n1->dfs_num_in >= n2->dfs_num_in 831 && n1->dfs_num_out <= n2->dfs_num_out); 832 833 return et_below (n1, n2); 834} 835 836/* Verify invariants of dominator structure. */ 837void 838verify_dominators (enum cdi_direction dir) 839{ 840 int err = 0; 841 basic_block bb; 842 843 gcc_assert (dom_info_available_p (dir)); 844 845 FOR_EACH_BB (bb) 846 { 847 basic_block dom_bb; 848 basic_block imm_bb; 849 850 dom_bb = recount_dominator (dir, bb); 851 imm_bb = get_immediate_dominator (dir, bb); 852 if (dom_bb != imm_bb) 853 { 854 if ((dom_bb == NULL) || (imm_bb == NULL)) 855 error ("dominator of %d status unknown", bb->index); 856 else 857 error ("dominator of %d should be %d, not %d", 858 bb->index, dom_bb->index, imm_bb->index); 859 err = 1; 860 } 861 } 862 863 if (dir == CDI_DOMINATORS) 864 { 865 FOR_EACH_BB (bb) 866 { 867 if (!dominated_by_p (dir, bb, ENTRY_BLOCK_PTR)) 868 { 869 error ("ENTRY does not dominate bb %d", bb->index); 870 err = 1; 871 } 872 } 873 } 874 875 gcc_assert (!err); 876} 877 878/* Determine immediate dominator (or postdominator, according to DIR) of BB, 879 assuming that dominators of other blocks are correct. We also use it to 880 recompute the dominators in a restricted area, by iterating it until it 881 reaches a fixed point. */ 882 883basic_block 884recount_dominator (enum cdi_direction dir, basic_block bb) 885{ 886 basic_block dom_bb = NULL; 887 edge e; 888 edge_iterator ei; 889 890 gcc_assert (dom_computed[dir]); 891 892 if (dir == CDI_DOMINATORS) 893 { 894 FOR_EACH_EDGE (e, ei, bb->preds) 895 { 896 /* Ignore the predecessors that either are not reachable from 897 the entry block, or whose dominator was not determined yet. */ 898 if (!dominated_by_p (dir, e->src, ENTRY_BLOCK_PTR)) 899 continue; 900 901 if (!dominated_by_p (dir, e->src, bb)) 902 dom_bb = nearest_common_dominator (dir, dom_bb, e->src); 903 } 904 } 905 else 906 { 907 FOR_EACH_EDGE (e, ei, bb->succs) 908 { 909 if (!dominated_by_p (dir, e->dest, bb)) 910 dom_bb = nearest_common_dominator (dir, dom_bb, e->dest); 911 } 912 } 913 914 return dom_bb; 915} 916 917/* Iteratively recount dominators of BBS. The change is supposed to be local 918 and not to grow further. */ 919void 920iterate_fix_dominators (enum cdi_direction dir, basic_block *bbs, int n) 921{ 922 int i, changed = 1; 923 basic_block old_dom, new_dom; 924 925 gcc_assert (dom_computed[dir]); 926 927 for (i = 0; i < n; i++) 928 set_immediate_dominator (dir, bbs[i], NULL); 929 930 while (changed) 931 { 932 changed = 0; 933 for (i = 0; i < n; i++) 934 { 935 old_dom = get_immediate_dominator (dir, bbs[i]); 936 new_dom = recount_dominator (dir, bbs[i]); 937 if (old_dom != new_dom) 938 { 939 changed = 1; 940 set_immediate_dominator (dir, bbs[i], new_dom); 941 } 942 } 943 } 944 945 for (i = 0; i < n; i++) 946 gcc_assert (get_immediate_dominator (dir, bbs[i])); 947} 948 949void 950add_to_dominance_info (enum cdi_direction dir, basic_block bb) 951{ 952 gcc_assert (dom_computed[dir]); 953 gcc_assert (!bb->dom[dir]); 954 955 n_bbs_in_dom_tree[dir]++; 956 957 bb->dom[dir] = et_new_tree (bb); 958 959 if (dom_computed[dir] == DOM_OK) 960 dom_computed[dir] = DOM_NO_FAST_QUERY; 961} 962 963void 964delete_from_dominance_info (enum cdi_direction dir, basic_block bb) 965{ 966 gcc_assert (dom_computed[dir]); 967 968 et_free_tree (bb->dom[dir]); 969 bb->dom[dir] = NULL; 970 n_bbs_in_dom_tree[dir]--; 971 972 if (dom_computed[dir] == DOM_OK) 973 dom_computed[dir] = DOM_NO_FAST_QUERY; 974} 975 976/* Returns the first son of BB in the dominator or postdominator tree 977 as determined by DIR. */ 978 979basic_block 980first_dom_son (enum cdi_direction dir, basic_block bb) 981{ 982 struct et_node *son = bb->dom[dir]->son; 983 984 return son ? son->data : NULL; 985} 986 987/* Returns the next dominance son after BB in the dominator or postdominator 988 tree as determined by DIR, or NULL if it was the last one. */ 989 990basic_block 991next_dom_son (enum cdi_direction dir, basic_block bb) 992{ 993 struct et_node *next = bb->dom[dir]->right; 994 995 return next->father->son == next ? NULL : next->data; 996} 997 998/* Returns true if dominance information for direction DIR is available. */ 999 1000bool 1001dom_info_available_p (enum cdi_direction dir) 1002{ 1003 return dom_computed[dir] != DOM_NONE; 1004} 1005 1006void 1007debug_dominance_info (enum cdi_direction dir) 1008{ 1009 basic_block bb, bb2; 1010 FOR_EACH_BB (bb) 1011 if ((bb2 = get_immediate_dominator (dir, bb))) 1012 fprintf (stderr, "%i %i\n", bb->index, bb2->index); 1013} 1014