dominance.c revision 90075
1/* Calculate (post)dominators in slightly super-linear time. 2 Copyright (C) 2000 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, 59 Temple Place - Suite 330, Boston, MA 20 02111-1307, 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 its 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 "rtl.h" 39#include "hard-reg-set.h" 40#include "basic-block.h" 41 42 43/* We name our nodes with integers, beginning with 1. Zero is reserved for 44 'undefined' or 'end of list'. The name of each node is given by the dfs 45 number of the corresponding basic block. Please note, that we include the 46 artificial ENTRY_BLOCK (or EXIT_BLOCK in the post-dom case) in our lists to 47 support multiple entry points. As it has no real basic block index we use 48 'n_basic_blocks' for that. Its dfs number is of course 1. */ 49 50/* Type of Basic Block aka. TBB */ 51typedef unsigned int TBB; 52 53/* We work in a poor-mans object oriented fashion, and carry an instance of 54 this structure through all our 'methods'. It holds various arrays 55 reflecting the (sub)structure of the flowgraph. Most of them are of type 56 TBB and are also indexed by TBB. */ 57 58struct dom_info 59{ 60 /* The parent of a node in the DFS tree. */ 61 TBB *dfs_parent; 62 /* For a node x key[x] is roughly the node nearest to the root from which 63 exists a way to x only over nodes behind x. Such a node is also called 64 semidominator. */ 65 TBB *key; 66 /* The value in path_min[x] is the node y on the path from x to the root of 67 the tree x is in with the smallest key[y]. */ 68 TBB *path_min; 69 /* bucket[x] points to the first node of the set of nodes having x as key. */ 70 TBB *bucket; 71 /* And next_bucket[x] points to the next node. */ 72 TBB *next_bucket; 73 /* After the algorithm is done, dom[x] contains the immediate dominator 74 of x. */ 75 TBB *dom; 76 77 /* The following few fields implement the structures needed for disjoint 78 sets. */ 79 /* set_chain[x] is the next node on the path from x to the representant 80 of the set containing x. If set_chain[x]==0 then x is a root. */ 81 TBB *set_chain; 82 /* set_size[x] is the number of elements in the set named by x. */ 83 unsigned int *set_size; 84 /* set_child[x] is used for balancing the tree representing a set. It can 85 be understood as the next sibling of x. */ 86 TBB *set_child; 87 88 /* If b is the number of a basic block (BB->index), dfs_order[b] is the 89 number of that node in DFS order counted from 1. This is an index 90 into most of the other arrays in this structure. */ 91 TBB *dfs_order; 92 /* If x is the DFS-index of a node which corresponds with an basic block, 93 dfs_to_bb[x] is that basic block. Note, that in our structure there are 94 more nodes that basic blocks, so only dfs_to_bb[dfs_order[bb->index]]==bb 95 is true for every basic block bb, but not the opposite. */ 96 basic_block *dfs_to_bb; 97 98 /* This is the next free DFS number when creating the DFS tree or forest. */ 99 unsigned int dfsnum; 100 /* The number of nodes in the DFS tree (==dfsnum-1). */ 101 unsigned int nodes; 102}; 103 104static void init_dom_info PARAMS ((struct dom_info *)); 105static void free_dom_info PARAMS ((struct dom_info *)); 106static void calc_dfs_tree_nonrec PARAMS ((struct dom_info *, 107 basic_block, 108 enum cdi_direction)); 109static void calc_dfs_tree PARAMS ((struct dom_info *, 110 enum cdi_direction)); 111static void compress PARAMS ((struct dom_info *, TBB)); 112static TBB eval PARAMS ((struct dom_info *, TBB)); 113static void link_roots PARAMS ((struct dom_info *, TBB, TBB)); 114static void calc_idoms PARAMS ((struct dom_info *, 115 enum cdi_direction)); 116static void idoms_to_doms PARAMS ((struct dom_info *, 117 sbitmap *)); 118 119/* Helper macro for allocating and initializing an array, 120 for aesthetic reasons. */ 121#define init_ar(var, type, num, content) \ 122 do { \ 123 unsigned int i = 1; /* Catch content == i. */ \ 124 if (! (content)) \ 125 (var) = (type *) xcalloc ((num), sizeof (type)); \ 126 else \ 127 { \ 128 (var) = (type *) xmalloc ((num) * sizeof (type)); \ 129 for (i = 0; i < num; i++) \ 130 (var)[i] = (content); \ 131 } \ 132 } while (0) 133 134/* Allocate all needed memory in a pessimistic fashion (so we round up). 135 This initialises the contents of DI, which already must be allocated. */ 136 137static void 138init_dom_info (di) 139 struct dom_info *di; 140{ 141 /* We need memory for n_basic_blocks nodes and the ENTRY_BLOCK or 142 EXIT_BLOCK. */ 143 unsigned int num = n_basic_blocks + 1 + 1; 144 init_ar (di->dfs_parent, TBB, num, 0); 145 init_ar (di->path_min, TBB, num, i); 146 init_ar (di->key, TBB, num, i); 147 init_ar (di->dom, TBB, num, 0); 148 149 init_ar (di->bucket, TBB, num, 0); 150 init_ar (di->next_bucket, TBB, num, 0); 151 152 init_ar (di->set_chain, TBB, num, 0); 153 init_ar (di->set_size, unsigned int, num, 1); 154 init_ar (di->set_child, TBB, num, 0); 155 156 init_ar (di->dfs_order, TBB, (unsigned int) n_basic_blocks + 1, 0); 157 init_ar (di->dfs_to_bb, basic_block, num, 0); 158 159 di->dfsnum = 1; 160 di->nodes = 0; 161} 162 163#undef init_ar 164 165/* Free all allocated memory in DI, but not DI itself. */ 166 167static void 168free_dom_info (di) 169 struct dom_info *di; 170{ 171 free (di->dfs_parent); 172 free (di->path_min); 173 free (di->key); 174 free (di->dom); 175 free (di->bucket); 176 free (di->next_bucket); 177 free (di->set_chain); 178 free (di->set_size); 179 free (di->set_child); 180 free (di->dfs_order); 181 free (di->dfs_to_bb); 182} 183 184/* The nonrecursive variant of creating a DFS tree. DI is our working 185 structure, BB the starting basic block for this tree and REVERSE 186 is true, if predecessors should be visited instead of successors of a 187 node. After this is done all nodes reachable from BB were visited, have 188 assigned their dfs number and are linked together to form a tree. */ 189 190static void 191calc_dfs_tree_nonrec (di, bb, reverse) 192 struct dom_info *di; 193 basic_block bb; 194 enum cdi_direction reverse; 195{ 196 /* We never call this with bb==EXIT_BLOCK_PTR (ENTRY_BLOCK_PTR if REVERSE). */ 197 /* We call this _only_ if bb is not already visited. */ 198 edge e; 199 TBB child_i, my_i = 0; 200 edge *stack; 201 int sp; 202 /* Start block (ENTRY_BLOCK_PTR for forward problem, EXIT_BLOCK for backward 203 problem). */ 204 basic_block en_block; 205 /* Ending block. */ 206 basic_block ex_block; 207 208 stack = (edge *) xmalloc ((n_basic_blocks + 3) * sizeof (edge)); 209 sp = 0; 210 211 /* Initialize our border blocks, and the first edge. */ 212 if (reverse) 213 { 214 e = bb->pred; 215 en_block = EXIT_BLOCK_PTR; 216 ex_block = ENTRY_BLOCK_PTR; 217 } 218 else 219 { 220 e = bb->succ; 221 en_block = ENTRY_BLOCK_PTR; 222 ex_block = EXIT_BLOCK_PTR; 223 } 224 225 /* When the stack is empty we break out of this loop. */ 226 while (1) 227 { 228 basic_block bn; 229 230 /* This loop traverses edges e in depth first manner, and fills the 231 stack. */ 232 while (e) 233 { 234 edge e_next; 235 236 /* Deduce from E the current and the next block (BB and BN), and the 237 next edge. */ 238 if (reverse) 239 { 240 bn = e->src; 241 242 /* If the next node BN is either already visited or a border 243 block the current edge is useless, and simply overwritten 244 with the next edge out of the current node. */ 245 if (bn == ex_block || di->dfs_order[bn->index]) 246 { 247 e = e->pred_next; 248 continue; 249 } 250 bb = e->dest; 251 e_next = bn->pred; 252 } 253 else 254 { 255 bn = e->dest; 256 if (bn == ex_block || di->dfs_order[bn->index]) 257 { 258 e = e->succ_next; 259 continue; 260 } 261 bb = e->src; 262 e_next = bn->succ; 263 } 264 265 if (bn == en_block) 266 abort (); 267 268 /* Fill the DFS tree info calculatable _before_ recursing. */ 269 if (bb != en_block) 270 my_i = di->dfs_order[bb->index]; 271 else 272 my_i = di->dfs_order[n_basic_blocks]; 273 child_i = di->dfs_order[bn->index] = di->dfsnum++; 274 di->dfs_to_bb[child_i] = bn; 275 di->dfs_parent[child_i] = my_i; 276 277 /* Save the current point in the CFG on the stack, and recurse. */ 278 stack[sp++] = e; 279 e = e_next; 280 } 281 282 if (!sp) 283 break; 284 e = stack[--sp]; 285 286 /* OK. The edge-list was exhausted, meaning normally we would 287 end the recursion. After returning from the recursive call, 288 there were (may be) other statements which were run after a 289 child node was completely considered by DFS. Here is the 290 point to do it in the non-recursive variant. 291 E.g. The block just completed is in e->dest for forward DFS, 292 the block not yet completed (the parent of the one above) 293 in e->src. This could be used e.g. for computing the number of 294 descendants or the tree depth. */ 295 if (reverse) 296 e = e->pred_next; 297 else 298 e = e->succ_next; 299 } 300 free (stack); 301} 302 303/* The main entry for calculating the DFS tree or forest. DI is our working 304 structure and REVERSE is true, if we are interested in the reverse flow 305 graph. In that case the result is not necessarily a tree but a forest, 306 because there may be nodes from which the EXIT_BLOCK is unreachable. */ 307 308static void 309calc_dfs_tree (di, reverse) 310 struct dom_info *di; 311 enum cdi_direction reverse; 312{ 313 /* The first block is the ENTRY_BLOCK (or EXIT_BLOCK if REVERSE). */ 314 basic_block begin = reverse ? EXIT_BLOCK_PTR : ENTRY_BLOCK_PTR; 315 di->dfs_order[n_basic_blocks] = di->dfsnum; 316 di->dfs_to_bb[di->dfsnum] = begin; 317 di->dfsnum++; 318 319 calc_dfs_tree_nonrec (di, begin, reverse); 320 321 if (reverse) 322 { 323 /* In the post-dom case we may have nodes without a path to EXIT_BLOCK. 324 They are reverse-unreachable. In the dom-case we disallow such 325 nodes, but in post-dom we have to deal with them, so we simply 326 include them in the DFS tree which actually becomes a forest. */ 327 int i; 328 for (i = n_basic_blocks - 1; i >= 0; i--) 329 { 330 basic_block b = BASIC_BLOCK (i); 331 if (di->dfs_order[b->index]) 332 continue; 333 di->dfs_order[b->index] = di->dfsnum; 334 di->dfs_to_bb[di->dfsnum] = b; 335 di->dfsnum++; 336 calc_dfs_tree_nonrec (di, b, reverse); 337 } 338 } 339 340 di->nodes = di->dfsnum - 1; 341 342 /* This aborts e.g. when there is _no_ path from ENTRY to EXIT at all. */ 343 if (di->nodes != (unsigned int) n_basic_blocks + 1) 344 abort (); 345} 346 347/* Compress the path from V to the root of its set and update path_min at the 348 same time. After compress(di, V) set_chain[V] is the root of the set V is 349 in and path_min[V] is the node with the smallest key[] value on the path 350 from V to that root. */ 351 352static void 353compress (di, v) 354 struct dom_info *di; 355 TBB v; 356{ 357 /* Btw. It's not worth to unrecurse compress() as the depth is usually not 358 greater than 5 even for huge graphs (I've not seen call depth > 4). 359 Also performance wise compress() ranges _far_ behind eval(). */ 360 TBB parent = di->set_chain[v]; 361 if (di->set_chain[parent]) 362 { 363 compress (di, parent); 364 if (di->key[di->path_min[parent]] < di->key[di->path_min[v]]) 365 di->path_min[v] = di->path_min[parent]; 366 di->set_chain[v] = di->set_chain[parent]; 367 } 368} 369 370/* Compress the path from V to the set root of V if needed (when the root has 371 changed since the last call). Returns the node with the smallest key[] 372 value on the path from V to the root. */ 373 374static inline TBB 375eval (di, v) 376 struct dom_info *di; 377 TBB v; 378{ 379 /* The representant of the set V is in, also called root (as the set 380 representation is a tree). */ 381 TBB rep = di->set_chain[v]; 382 383 /* V itself is the root. */ 384 if (!rep) 385 return di->path_min[v]; 386 387 /* Compress only if necessary. */ 388 if (di->set_chain[rep]) 389 { 390 compress (di, v); 391 rep = di->set_chain[v]; 392 } 393 394 if (di->key[di->path_min[rep]] >= di->key[di->path_min[v]]) 395 return di->path_min[v]; 396 else 397 return di->path_min[rep]; 398} 399 400/* This essentially merges the two sets of V and W, giving a single set with 401 the new root V. The internal representation of these disjoint sets is a 402 balanced tree. Currently link(V,W) is only used with V being the parent 403 of W. */ 404 405static void 406link_roots (di, v, w) 407 struct dom_info *di; 408 TBB v, w; 409{ 410 TBB s = w; 411 412 /* Rebalance the tree. */ 413 while (di->key[di->path_min[w]] < di->key[di->path_min[di->set_child[s]]]) 414 { 415 if (di->set_size[s] + di->set_size[di->set_child[di->set_child[s]]] 416 >= 2 * di->set_size[di->set_child[s]]) 417 { 418 di->set_chain[di->set_child[s]] = s; 419 di->set_child[s] = di->set_child[di->set_child[s]]; 420 } 421 else 422 { 423 di->set_size[di->set_child[s]] = di->set_size[s]; 424 s = di->set_chain[s] = di->set_child[s]; 425 } 426 } 427 428 di->path_min[s] = di->path_min[w]; 429 di->set_size[v] += di->set_size[w]; 430 if (di->set_size[v] < 2 * di->set_size[w]) 431 { 432 TBB tmp = s; 433 s = di->set_child[v]; 434 di->set_child[v] = tmp; 435 } 436 437 /* Merge all subtrees. */ 438 while (s) 439 { 440 di->set_chain[s] = v; 441 s = di->set_child[s]; 442 } 443} 444 445/* This calculates the immediate dominators (or post-dominators if REVERSE is 446 true). DI is our working structure and should hold the DFS forest. 447 On return the immediate dominator to node V is in di->dom[V]. */ 448 449static void 450calc_idoms (di, reverse) 451 struct dom_info *di; 452 enum cdi_direction reverse; 453{ 454 TBB v, w, k, par; 455 basic_block en_block; 456 if (reverse) 457 en_block = EXIT_BLOCK_PTR; 458 else 459 en_block = ENTRY_BLOCK_PTR; 460 461 /* Go backwards in DFS order, to first look at the leafs. */ 462 v = di->nodes; 463 while (v > 1) 464 { 465 basic_block bb = di->dfs_to_bb[v]; 466 edge e, e_next; 467 468 par = di->dfs_parent[v]; 469 k = v; 470 if (reverse) 471 e = bb->succ; 472 else 473 e = bb->pred; 474 475 /* Search all direct predecessors for the smallest node with a path 476 to them. That way we have the smallest node with also a path to 477 us only over nodes behind us. In effect we search for our 478 semidominator. */ 479 for (; e; e = e_next) 480 { 481 TBB k1; 482 basic_block b; 483 484 if (reverse) 485 { 486 b = e->dest; 487 e_next = e->succ_next; 488 } 489 else 490 { 491 b = e->src; 492 e_next = e->pred_next; 493 } 494 if (b == en_block) 495 k1 = di->dfs_order[n_basic_blocks]; 496 else 497 k1 = di->dfs_order[b->index]; 498 499 /* Call eval() only if really needed. If k1 is above V in DFS tree, 500 then we know, that eval(k1) == k1 and key[k1] == k1. */ 501 if (k1 > v) 502 k1 = di->key[eval (di, k1)]; 503 if (k1 < k) 504 k = k1; 505 } 506 507 di->key[v] = k; 508 link_roots (di, par, v); 509 di->next_bucket[v] = di->bucket[k]; 510 di->bucket[k] = v; 511 512 /* Transform semidominators into dominators. */ 513 for (w = di->bucket[par]; w; w = di->next_bucket[w]) 514 { 515 k = eval (di, w); 516 if (di->key[k] < di->key[w]) 517 di->dom[w] = k; 518 else 519 di->dom[w] = par; 520 } 521 /* We don't need to cleanup next_bucket[]. */ 522 di->bucket[par] = 0; 523 v--; 524 } 525 526 /* Explicitly define the dominators. */ 527 di->dom[1] = 0; 528 for (v = 2; v <= di->nodes; v++) 529 if (di->dom[v] != di->key[v]) 530 di->dom[v] = di->dom[di->dom[v]]; 531} 532 533/* Convert the information about immediate dominators (in DI) to sets of all 534 dominators (in DOMINATORS). */ 535 536static void 537idoms_to_doms (di, dominators) 538 struct dom_info *di; 539 sbitmap *dominators; 540{ 541 TBB i, e_index; 542 int bb, bb_idom; 543 sbitmap_vector_zero (dominators, n_basic_blocks); 544 /* We have to be careful, to not include the ENTRY_BLOCK or EXIT_BLOCK 545 in the list of (post)-doms, so remember that in e_index. */ 546 e_index = di->dfs_order[n_basic_blocks]; 547 548 for (i = 1; i <= di->nodes; i++) 549 { 550 if (i == e_index) 551 continue; 552 bb = di->dfs_to_bb[i]->index; 553 554 if (di->dom[i] && (di->dom[i] != e_index)) 555 { 556 bb_idom = di->dfs_to_bb[di->dom[i]]->index; 557 sbitmap_copy (dominators[bb], dominators[bb_idom]); 558 } 559 else 560 { 561 /* It has no immediate dom or only ENTRY_BLOCK or EXIT_BLOCK. 562 If it is a child of ENTRY_BLOCK that's OK, and it's only 563 dominated by itself; if it's _not_ a child of ENTRY_BLOCK, it 564 means, it is unreachable. That case has been disallowed in the 565 building of the DFS tree, so we are save here. For the reverse 566 flow graph it means, it has no children, so, to be compatible 567 with the old code, we set the post_dominators to all one. */ 568 if (!di->dom[i]) 569 { 570 sbitmap_ones (dominators[bb]); 571 } 572 } 573 SET_BIT (dominators[bb], bb); 574 } 575} 576 577/* The main entry point into this module. IDOM is an integer array with room 578 for n_basic_blocks integers, DOMS is a preallocated sbitmap array having 579 room for n_basic_blocks^2 bits, and POST is true if the caller wants to 580 know post-dominators. 581 582 On return IDOM[i] will be the BB->index of the immediate (post) dominator 583 of basic block i, and DOMS[i] will have set bit j if basic block j is a 584 (post)dominator for block i. 585 586 Either IDOM or DOMS may be NULL (meaning the caller is not interested in 587 immediate resp. all dominators). */ 588 589void 590calculate_dominance_info (idom, doms, reverse) 591 int *idom; 592 sbitmap *doms; 593 enum cdi_direction reverse; 594{ 595 struct dom_info di; 596 597 if (!doms && !idom) 598 return; 599 init_dom_info (&di); 600 calc_dfs_tree (&di, reverse); 601 calc_idoms (&di, reverse); 602 603 if (idom) 604 { 605 int i; 606 for (i = 0; i < n_basic_blocks; i++) 607 { 608 basic_block b = BASIC_BLOCK (i); 609 TBB d = di.dom[di.dfs_order[b->index]]; 610 611 /* The old code didn't modify array elements of nodes having only 612 itself as dominator (d==0) or only ENTRY_BLOCK (resp. EXIT_BLOCK) 613 (d==1). */ 614 if (d > 1) 615 idom[i] = di.dfs_to_bb[d]->index; 616 } 617 } 618 if (doms) 619 idoms_to_doms (&di, doms); 620 621 free_dom_info (&di); 622} 623