190075Sobrien/* Calculate (post)dominators in slightly super-linear time. 2169689Skan Copyright (C) 2000, 2003, 2004, 2005 Free Software Foundation, Inc. 390075Sobrien Contributed by Michael Matz (matz@ifh.de). 4117395Skan 590075Sobrien This file is part of GCC. 6117395Skan 790075Sobrien GCC is free software; you can redistribute it and/or modify it 890075Sobrien under the terms of the GNU General Public License as published by 990075Sobrien the Free Software Foundation; either version 2, or (at your option) 1090075Sobrien any later version. 1190075Sobrien 1290075Sobrien GCC is distributed in the hope that it will be useful, but WITHOUT 1390075Sobrien ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 1490075Sobrien or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public 1590075Sobrien License for more details. 1690075Sobrien 1790075Sobrien You should have received a copy of the GNU General Public License 1890075Sobrien along with GCC; see the file COPYING. If not, write to the Free 19169689Skan Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20169689Skan 02110-1301, USA. */ 2190075Sobrien 2290075Sobrien/* This file implements the well known algorithm from Lengauer and Tarjan 2390075Sobrien to compute the dominators in a control flow graph. A basic block D is said 2490075Sobrien to dominate another block X, when all paths from the entry node of the CFG 2590075Sobrien to X go also over D. The dominance relation is a transitive reflexive 2690075Sobrien relation and its minimal transitive reduction is a tree, called the 2790075Sobrien dominator tree. So for each block X besides the entry block exists a 2890075Sobrien block I(X), called the immediate dominator of X, which is the parent of X 2990075Sobrien in the dominator tree. 3090075Sobrien 3190075Sobrien The algorithm computes this dominator tree implicitly by computing for 3290075Sobrien each block its immediate dominator. We use tree balancing and path 33169689Skan compression, so it's the O(e*a(e,v)) variant, where a(e,v) is the very 3490075Sobrien slowly growing functional inverse of the Ackerman function. */ 3590075Sobrien 3690075Sobrien#include "config.h" 3790075Sobrien#include "system.h" 38132718Skan#include "coretypes.h" 39132718Skan#include "tm.h" 4090075Sobrien#include "rtl.h" 4190075Sobrien#include "hard-reg-set.h" 42169689Skan#include "obstack.h" 4390075Sobrien#include "basic-block.h" 44169689Skan#include "toplev.h" 45117395Skan#include "et-forest.h" 46169689Skan#include "timevar.h" 4790075Sobrien 48132718Skan/* Whether the dominators and the postdominators are available. */ 49132718Skanenum dom_state dom_computed[2]; 5090075Sobrien 5190075Sobrien/* We name our nodes with integers, beginning with 1. Zero is reserved for 5290075Sobrien 'undefined' or 'end of list'. The name of each node is given by the dfs 5390075Sobrien number of the corresponding basic block. Please note, that we include the 5490075Sobrien artificial ENTRY_BLOCK (or EXIT_BLOCK in the post-dom case) in our lists to 55169689Skan support multiple entry points. Its dfs number is of course 1. */ 5690075Sobrien 5790075Sobrien/* Type of Basic Block aka. TBB */ 5890075Sobrientypedef unsigned int TBB; 5990075Sobrien 6090075Sobrien/* We work in a poor-mans object oriented fashion, and carry an instance of 6190075Sobrien this structure through all our 'methods'. It holds various arrays 6290075Sobrien reflecting the (sub)structure of the flowgraph. Most of them are of type 6390075Sobrien TBB and are also indexed by TBB. */ 6490075Sobrien 6590075Sobrienstruct dom_info 6690075Sobrien{ 6790075Sobrien /* The parent of a node in the DFS tree. */ 6890075Sobrien TBB *dfs_parent; 6990075Sobrien /* For a node x key[x] is roughly the node nearest to the root from which 7090075Sobrien exists a way to x only over nodes behind x. Such a node is also called 7190075Sobrien semidominator. */ 7290075Sobrien TBB *key; 7390075Sobrien /* The value in path_min[x] is the node y on the path from x to the root of 7490075Sobrien the tree x is in with the smallest key[y]. */ 7590075Sobrien TBB *path_min; 7690075Sobrien /* bucket[x] points to the first node of the set of nodes having x as key. */ 7790075Sobrien TBB *bucket; 7890075Sobrien /* And next_bucket[x] points to the next node. */ 7990075Sobrien TBB *next_bucket; 8090075Sobrien /* After the algorithm is done, dom[x] contains the immediate dominator 8190075Sobrien of x. */ 8290075Sobrien TBB *dom; 8390075Sobrien 8490075Sobrien /* The following few fields implement the structures needed for disjoint 8590075Sobrien sets. */ 8690075Sobrien /* set_chain[x] is the next node on the path from x to the representant 8790075Sobrien of the set containing x. If set_chain[x]==0 then x is a root. */ 8890075Sobrien TBB *set_chain; 8990075Sobrien /* set_size[x] is the number of elements in the set named by x. */ 9090075Sobrien unsigned int *set_size; 9190075Sobrien /* set_child[x] is used for balancing the tree representing a set. It can 9290075Sobrien be understood as the next sibling of x. */ 9390075Sobrien TBB *set_child; 9490075Sobrien 9590075Sobrien /* If b is the number of a basic block (BB->index), dfs_order[b] is the 9690075Sobrien number of that node in DFS order counted from 1. This is an index 9790075Sobrien into most of the other arrays in this structure. */ 9890075Sobrien TBB *dfs_order; 99117395Skan /* If x is the DFS-index of a node which corresponds with a basic block, 10090075Sobrien dfs_to_bb[x] is that basic block. Note, that in our structure there are 10190075Sobrien more nodes that basic blocks, so only dfs_to_bb[dfs_order[bb->index]]==bb 10290075Sobrien is true for every basic block bb, but not the opposite. */ 10390075Sobrien basic_block *dfs_to_bb; 10490075Sobrien 105169689Skan /* This is the next free DFS number when creating the DFS tree. */ 10690075Sobrien unsigned int dfsnum; 10790075Sobrien /* The number of nodes in the DFS tree (==dfsnum-1). */ 10890075Sobrien unsigned int nodes; 109169689Skan 110169689Skan /* Blocks with bits set here have a fake edge to EXIT. These are used 111169689Skan to turn a DFS forest into a proper tree. */ 112169689Skan bitmap fake_exit_edge; 11390075Sobrien}; 11490075Sobrien 115169689Skanstatic void init_dom_info (struct dom_info *, enum cdi_direction); 116132718Skanstatic void free_dom_info (struct dom_info *); 117132718Skanstatic void calc_dfs_tree_nonrec (struct dom_info *, basic_block, 118132718Skan enum cdi_direction); 119132718Skanstatic void calc_dfs_tree (struct dom_info *, enum cdi_direction); 120132718Skanstatic void compress (struct dom_info *, TBB); 121132718Skanstatic TBB eval (struct dom_info *, TBB); 122132718Skanstatic void link_roots (struct dom_info *, TBB, TBB); 123132718Skanstatic void calc_idoms (struct dom_info *, enum cdi_direction); 124132718Skanvoid debug_dominance_info (enum cdi_direction); 12590075Sobrien 126169689Skan/* Keeps track of the*/ 127169689Skanstatic unsigned n_bbs_in_dom_tree[2]; 128169689Skan 12990075Sobrien/* Helper macro for allocating and initializing an array, 13090075Sobrien for aesthetic reasons. */ 13190075Sobrien#define init_ar(var, type, num, content) \ 132117395Skan do \ 133117395Skan { \ 134117395Skan unsigned int i = 1; /* Catch content == i. */ \ 135117395Skan if (! (content)) \ 136169689Skan (var) = XCNEWVEC (type, num); \ 137117395Skan else \ 138117395Skan { \ 139169689Skan (var) = XNEWVEC (type, (num)); \ 140117395Skan for (i = 0; i < num; i++) \ 141117395Skan (var)[i] = (content); \ 142117395Skan } \ 143117395Skan } \ 144117395Skan while (0) 14590075Sobrien 14690075Sobrien/* Allocate all needed memory in a pessimistic fashion (so we round up). 147117395Skan This initializes the contents of DI, which already must be allocated. */ 14890075Sobrien 14990075Sobrienstatic void 150169689Skaninit_dom_info (struct dom_info *di, enum cdi_direction dir) 15190075Sobrien{ 152169689Skan unsigned int num = n_basic_blocks; 15390075Sobrien init_ar (di->dfs_parent, TBB, num, 0); 15490075Sobrien init_ar (di->path_min, TBB, num, i); 15590075Sobrien init_ar (di->key, TBB, num, i); 15690075Sobrien init_ar (di->dom, TBB, num, 0); 15790075Sobrien 15890075Sobrien init_ar (di->bucket, TBB, num, 0); 15990075Sobrien init_ar (di->next_bucket, TBB, num, 0); 16090075Sobrien 16190075Sobrien init_ar (di->set_chain, TBB, num, 0); 16290075Sobrien init_ar (di->set_size, unsigned int, num, 1); 16390075Sobrien init_ar (di->set_child, TBB, num, 0); 16490075Sobrien 165117395Skan init_ar (di->dfs_order, TBB, (unsigned int) last_basic_block + 1, 0); 16690075Sobrien init_ar (di->dfs_to_bb, basic_block, num, 0); 16790075Sobrien 16890075Sobrien di->dfsnum = 1; 16990075Sobrien di->nodes = 0; 170169689Skan 171169689Skan di->fake_exit_edge = dir ? BITMAP_ALLOC (NULL) : NULL; 17290075Sobrien} 17390075Sobrien 17490075Sobrien#undef init_ar 17590075Sobrien 17690075Sobrien/* Free all allocated memory in DI, but not DI itself. */ 17790075Sobrien 17890075Sobrienstatic void 179132718Skanfree_dom_info (struct dom_info *di) 18090075Sobrien{ 18190075Sobrien free (di->dfs_parent); 18290075Sobrien free (di->path_min); 18390075Sobrien free (di->key); 18490075Sobrien free (di->dom); 18590075Sobrien free (di->bucket); 18690075Sobrien free (di->next_bucket); 18790075Sobrien free (di->set_chain); 18890075Sobrien free (di->set_size); 18990075Sobrien free (di->set_child); 19090075Sobrien free (di->dfs_order); 19190075Sobrien free (di->dfs_to_bb); 192169689Skan BITMAP_FREE (di->fake_exit_edge); 19390075Sobrien} 19490075Sobrien 19590075Sobrien/* The nonrecursive variant of creating a DFS tree. DI is our working 19690075Sobrien structure, BB the starting basic block for this tree and REVERSE 19790075Sobrien is true, if predecessors should be visited instead of successors of a 19890075Sobrien node. After this is done all nodes reachable from BB were visited, have 19990075Sobrien assigned their dfs number and are linked together to form a tree. */ 20090075Sobrien 20190075Sobrienstatic void 202169689Skancalc_dfs_tree_nonrec (struct dom_info *di, basic_block bb, 203169689Skan enum cdi_direction reverse) 20490075Sobrien{ 20590075Sobrien /* We call this _only_ if bb is not already visited. */ 20690075Sobrien edge e; 20790075Sobrien TBB child_i, my_i = 0; 208169689Skan edge_iterator *stack; 209169689Skan edge_iterator ei, einext; 21090075Sobrien int sp; 21190075Sobrien /* Start block (ENTRY_BLOCK_PTR for forward problem, EXIT_BLOCK for backward 21290075Sobrien problem). */ 21390075Sobrien basic_block en_block; 21490075Sobrien /* Ending block. */ 21590075Sobrien basic_block ex_block; 21690075Sobrien 217169689Skan stack = XNEWVEC (edge_iterator, n_basic_blocks + 1); 21890075Sobrien sp = 0; 21990075Sobrien 22090075Sobrien /* Initialize our border blocks, and the first edge. */ 22190075Sobrien if (reverse) 22290075Sobrien { 223169689Skan ei = ei_start (bb->preds); 22490075Sobrien en_block = EXIT_BLOCK_PTR; 22590075Sobrien ex_block = ENTRY_BLOCK_PTR; 22690075Sobrien } 22790075Sobrien else 22890075Sobrien { 229169689Skan ei = ei_start (bb->succs); 23090075Sobrien en_block = ENTRY_BLOCK_PTR; 23190075Sobrien ex_block = EXIT_BLOCK_PTR; 23290075Sobrien } 23390075Sobrien 23490075Sobrien /* When the stack is empty we break out of this loop. */ 23590075Sobrien while (1) 23690075Sobrien { 23790075Sobrien basic_block bn; 23890075Sobrien 23990075Sobrien /* This loop traverses edges e in depth first manner, and fills the 24090075Sobrien stack. */ 241169689Skan while (!ei_end_p (ei)) 24290075Sobrien { 243169689Skan e = ei_edge (ei); 24490075Sobrien 24590075Sobrien /* Deduce from E the current and the next block (BB and BN), and the 24690075Sobrien next edge. */ 24790075Sobrien if (reverse) 24890075Sobrien { 24990075Sobrien bn = e->src; 25090075Sobrien 25190075Sobrien /* If the next node BN is either already visited or a border 25290075Sobrien block the current edge is useless, and simply overwritten 25390075Sobrien with the next edge out of the current node. */ 25490075Sobrien if (bn == ex_block || di->dfs_order[bn->index]) 25590075Sobrien { 256169689Skan ei_next (&ei); 25790075Sobrien continue; 25890075Sobrien } 25990075Sobrien bb = e->dest; 260169689Skan einext = ei_start (bn->preds); 26190075Sobrien } 26290075Sobrien else 26390075Sobrien { 26490075Sobrien bn = e->dest; 26590075Sobrien if (bn == ex_block || di->dfs_order[bn->index]) 26690075Sobrien { 267169689Skan ei_next (&ei); 26890075Sobrien continue; 26990075Sobrien } 27090075Sobrien bb = e->src; 271169689Skan einext = ei_start (bn->succs); 27290075Sobrien } 27390075Sobrien 274169689Skan gcc_assert (bn != en_block); 27590075Sobrien 27690075Sobrien /* Fill the DFS tree info calculatable _before_ recursing. */ 27790075Sobrien if (bb != en_block) 27890075Sobrien my_i = di->dfs_order[bb->index]; 27990075Sobrien else 280117395Skan my_i = di->dfs_order[last_basic_block]; 28190075Sobrien child_i = di->dfs_order[bn->index] = di->dfsnum++; 28290075Sobrien di->dfs_to_bb[child_i] = bn; 28390075Sobrien di->dfs_parent[child_i] = my_i; 28490075Sobrien 28590075Sobrien /* Save the current point in the CFG on the stack, and recurse. */ 286169689Skan stack[sp++] = ei; 287169689Skan ei = einext; 28890075Sobrien } 28990075Sobrien 29090075Sobrien if (!sp) 29190075Sobrien break; 292169689Skan ei = stack[--sp]; 29390075Sobrien 29490075Sobrien /* OK. The edge-list was exhausted, meaning normally we would 29590075Sobrien end the recursion. After returning from the recursive call, 29690075Sobrien there were (may be) other statements which were run after a 29790075Sobrien child node was completely considered by DFS. Here is the 29890075Sobrien point to do it in the non-recursive variant. 29990075Sobrien E.g. The block just completed is in e->dest for forward DFS, 30090075Sobrien the block not yet completed (the parent of the one above) 30190075Sobrien in e->src. This could be used e.g. for computing the number of 30290075Sobrien descendants or the tree depth. */ 303169689Skan ei_next (&ei); 30490075Sobrien } 30590075Sobrien free (stack); 30690075Sobrien} 30790075Sobrien 30890075Sobrien/* The main entry for calculating the DFS tree or forest. DI is our working 30990075Sobrien structure and REVERSE is true, if we are interested in the reverse flow 31090075Sobrien graph. In that case the result is not necessarily a tree but a forest, 31190075Sobrien because there may be nodes from which the EXIT_BLOCK is unreachable. */ 31290075Sobrien 31390075Sobrienstatic void 314132718Skancalc_dfs_tree (struct dom_info *di, enum cdi_direction reverse) 31590075Sobrien{ 31690075Sobrien /* The first block is the ENTRY_BLOCK (or EXIT_BLOCK if REVERSE). */ 31790075Sobrien basic_block begin = reverse ? EXIT_BLOCK_PTR : ENTRY_BLOCK_PTR; 318117395Skan di->dfs_order[last_basic_block] = di->dfsnum; 31990075Sobrien di->dfs_to_bb[di->dfsnum] = begin; 32090075Sobrien di->dfsnum++; 32190075Sobrien 32290075Sobrien calc_dfs_tree_nonrec (di, begin, reverse); 32390075Sobrien 32490075Sobrien if (reverse) 32590075Sobrien { 32690075Sobrien /* In the post-dom case we may have nodes without a path to EXIT_BLOCK. 32790075Sobrien They are reverse-unreachable. In the dom-case we disallow such 328169689Skan nodes, but in post-dom we have to deal with them. 329169689Skan 330169689Skan There are two situations in which this occurs. First, noreturn 331169689Skan functions. Second, infinite loops. In the first case we need to 332169689Skan pretend that there is an edge to the exit block. In the second 333169689Skan case, we wind up with a forest. We need to process all noreturn 334169689Skan blocks before we know if we've got any infinite loops. */ 335169689Skan 336117395Skan basic_block b; 337169689Skan bool saw_unconnected = false; 338169689Skan 339117395Skan FOR_EACH_BB_REVERSE (b) 34090075Sobrien { 341169689Skan if (EDGE_COUNT (b->succs) > 0) 342169689Skan { 343169689Skan if (di->dfs_order[b->index] == 0) 344169689Skan saw_unconnected = true; 345169689Skan continue; 346169689Skan } 347169689Skan bitmap_set_bit (di->fake_exit_edge, b->index); 34890075Sobrien di->dfs_order[b->index] = di->dfsnum; 34990075Sobrien di->dfs_to_bb[di->dfsnum] = b; 350169689Skan di->dfs_parent[di->dfsnum] = di->dfs_order[last_basic_block]; 35190075Sobrien di->dfsnum++; 35290075Sobrien calc_dfs_tree_nonrec (di, b, reverse); 35390075Sobrien } 354169689Skan 355169689Skan if (saw_unconnected) 356169689Skan { 357169689Skan FOR_EACH_BB_REVERSE (b) 358169689Skan { 359169689Skan if (di->dfs_order[b->index]) 360169689Skan continue; 361169689Skan bitmap_set_bit (di->fake_exit_edge, b->index); 362169689Skan di->dfs_order[b->index] = di->dfsnum; 363169689Skan di->dfs_to_bb[di->dfsnum] = b; 364169689Skan di->dfs_parent[di->dfsnum] = di->dfs_order[last_basic_block]; 365169689Skan di->dfsnum++; 366169689Skan calc_dfs_tree_nonrec (di, b, reverse); 367169689Skan } 368169689Skan } 36990075Sobrien } 37090075Sobrien 37190075Sobrien di->nodes = di->dfsnum - 1; 37290075Sobrien 37390075Sobrien /* This aborts e.g. when there is _no_ path from ENTRY to EXIT at all. */ 374169689Skan gcc_assert (di->nodes == (unsigned int) n_basic_blocks - 1); 37590075Sobrien} 37690075Sobrien 37790075Sobrien/* Compress the path from V to the root of its set and update path_min at the 37890075Sobrien same time. After compress(di, V) set_chain[V] is the root of the set V is 37990075Sobrien in and path_min[V] is the node with the smallest key[] value on the path 38090075Sobrien from V to that root. */ 38190075Sobrien 38290075Sobrienstatic void 383132718Skancompress (struct dom_info *di, TBB v) 38490075Sobrien{ 38590075Sobrien /* Btw. It's not worth to unrecurse compress() as the depth is usually not 38690075Sobrien greater than 5 even for huge graphs (I've not seen call depth > 4). 38790075Sobrien Also performance wise compress() ranges _far_ behind eval(). */ 38890075Sobrien TBB parent = di->set_chain[v]; 38990075Sobrien if (di->set_chain[parent]) 39090075Sobrien { 39190075Sobrien compress (di, parent); 39290075Sobrien if (di->key[di->path_min[parent]] < di->key[di->path_min[v]]) 39390075Sobrien di->path_min[v] = di->path_min[parent]; 39490075Sobrien di->set_chain[v] = di->set_chain[parent]; 39590075Sobrien } 39690075Sobrien} 39790075Sobrien 39890075Sobrien/* Compress the path from V to the set root of V if needed (when the root has 39990075Sobrien changed since the last call). Returns the node with the smallest key[] 40090075Sobrien value on the path from V to the root. */ 40190075Sobrien 40290075Sobrienstatic inline TBB 403132718Skaneval (struct dom_info *di, TBB v) 40490075Sobrien{ 40590075Sobrien /* The representant of the set V is in, also called root (as the set 40690075Sobrien representation is a tree). */ 40790075Sobrien TBB rep = di->set_chain[v]; 40890075Sobrien 40990075Sobrien /* V itself is the root. */ 41090075Sobrien if (!rep) 41190075Sobrien return di->path_min[v]; 41290075Sobrien 41390075Sobrien /* Compress only if necessary. */ 41490075Sobrien if (di->set_chain[rep]) 41590075Sobrien { 41690075Sobrien compress (di, v); 41790075Sobrien rep = di->set_chain[v]; 41890075Sobrien } 41990075Sobrien 42090075Sobrien if (di->key[di->path_min[rep]] >= di->key[di->path_min[v]]) 42190075Sobrien return di->path_min[v]; 42290075Sobrien else 42390075Sobrien return di->path_min[rep]; 42490075Sobrien} 42590075Sobrien 42690075Sobrien/* This essentially merges the two sets of V and W, giving a single set with 42790075Sobrien the new root V. The internal representation of these disjoint sets is a 42890075Sobrien balanced tree. Currently link(V,W) is only used with V being the parent 42990075Sobrien of W. */ 43090075Sobrien 43190075Sobrienstatic void 432132718Skanlink_roots (struct dom_info *di, TBB v, TBB w) 43390075Sobrien{ 43490075Sobrien TBB s = w; 43590075Sobrien 43690075Sobrien /* Rebalance the tree. */ 43790075Sobrien while (di->key[di->path_min[w]] < di->key[di->path_min[di->set_child[s]]]) 43890075Sobrien { 43990075Sobrien if (di->set_size[s] + di->set_size[di->set_child[di->set_child[s]]] 44090075Sobrien >= 2 * di->set_size[di->set_child[s]]) 44190075Sobrien { 44290075Sobrien di->set_chain[di->set_child[s]] = s; 44390075Sobrien di->set_child[s] = di->set_child[di->set_child[s]]; 44490075Sobrien } 44590075Sobrien else 44690075Sobrien { 44790075Sobrien di->set_size[di->set_child[s]] = di->set_size[s]; 44890075Sobrien s = di->set_chain[s] = di->set_child[s]; 44990075Sobrien } 45090075Sobrien } 45190075Sobrien 45290075Sobrien di->path_min[s] = di->path_min[w]; 45390075Sobrien di->set_size[v] += di->set_size[w]; 45490075Sobrien if (di->set_size[v] < 2 * di->set_size[w]) 45590075Sobrien { 45690075Sobrien TBB tmp = s; 45790075Sobrien s = di->set_child[v]; 45890075Sobrien di->set_child[v] = tmp; 45990075Sobrien } 46090075Sobrien 46190075Sobrien /* Merge all subtrees. */ 46290075Sobrien while (s) 46390075Sobrien { 46490075Sobrien di->set_chain[s] = v; 46590075Sobrien s = di->set_child[s]; 46690075Sobrien } 46790075Sobrien} 46890075Sobrien 46990075Sobrien/* This calculates the immediate dominators (or post-dominators if REVERSE is 47090075Sobrien true). DI is our working structure and should hold the DFS forest. 47190075Sobrien On return the immediate dominator to node V is in di->dom[V]. */ 47290075Sobrien 47390075Sobrienstatic void 474132718Skancalc_idoms (struct dom_info *di, enum cdi_direction reverse) 47590075Sobrien{ 47690075Sobrien TBB v, w, k, par; 47790075Sobrien basic_block en_block; 478169689Skan edge_iterator ei, einext; 479169689Skan 48090075Sobrien if (reverse) 48190075Sobrien en_block = EXIT_BLOCK_PTR; 48290075Sobrien else 48390075Sobrien en_block = ENTRY_BLOCK_PTR; 48490075Sobrien 48590075Sobrien /* Go backwards in DFS order, to first look at the leafs. */ 48690075Sobrien v = di->nodes; 48790075Sobrien while (v > 1) 48890075Sobrien { 48990075Sobrien basic_block bb = di->dfs_to_bb[v]; 490169689Skan edge e; 49190075Sobrien 49290075Sobrien par = di->dfs_parent[v]; 49390075Sobrien k = v; 494169689Skan 495169689Skan ei = (reverse) ? ei_start (bb->succs) : ei_start (bb->preds); 496169689Skan 49790075Sobrien if (reverse) 498169689Skan { 499169689Skan /* If this block has a fake edge to exit, process that first. */ 500169689Skan if (bitmap_bit_p (di->fake_exit_edge, bb->index)) 501169689Skan { 502169689Skan einext = ei; 503169689Skan einext.index = 0; 504169689Skan goto do_fake_exit_edge; 505169689Skan } 506169689Skan } 50790075Sobrien 50890075Sobrien /* Search all direct predecessors for the smallest node with a path 50990075Sobrien to them. That way we have the smallest node with also a path to 51090075Sobrien us only over nodes behind us. In effect we search for our 51190075Sobrien semidominator. */ 512169689Skan while (!ei_end_p (ei)) 51390075Sobrien { 51490075Sobrien TBB k1; 51590075Sobrien basic_block b; 51690075Sobrien 517169689Skan e = ei_edge (ei); 518169689Skan b = (reverse) ? e->dest : e->src; 519169689Skan einext = ei; 520169689Skan ei_next (&einext); 521169689Skan 522169689Skan if (b == en_block) 52390075Sobrien { 524169689Skan do_fake_exit_edge: 525169689Skan k1 = di->dfs_order[last_basic_block]; 52690075Sobrien } 52790075Sobrien else 52890075Sobrien k1 = di->dfs_order[b->index]; 52990075Sobrien 53090075Sobrien /* Call eval() only if really needed. If k1 is above V in DFS tree, 53190075Sobrien then we know, that eval(k1) == k1 and key[k1] == k1. */ 53290075Sobrien if (k1 > v) 53390075Sobrien k1 = di->key[eval (di, k1)]; 53490075Sobrien if (k1 < k) 53590075Sobrien k = k1; 536169689Skan 537169689Skan ei = einext; 53890075Sobrien } 53990075Sobrien 54090075Sobrien di->key[v] = k; 54190075Sobrien link_roots (di, par, v); 54290075Sobrien di->next_bucket[v] = di->bucket[k]; 54390075Sobrien di->bucket[k] = v; 54490075Sobrien 54590075Sobrien /* Transform semidominators into dominators. */ 54690075Sobrien for (w = di->bucket[par]; w; w = di->next_bucket[w]) 54790075Sobrien { 54890075Sobrien k = eval (di, w); 54990075Sobrien if (di->key[k] < di->key[w]) 55090075Sobrien di->dom[w] = k; 55190075Sobrien else 55290075Sobrien di->dom[w] = par; 55390075Sobrien } 55490075Sobrien /* We don't need to cleanup next_bucket[]. */ 55590075Sobrien di->bucket[par] = 0; 55690075Sobrien v--; 55790075Sobrien } 55890075Sobrien 55990075Sobrien /* Explicitly define the dominators. */ 56090075Sobrien di->dom[1] = 0; 56190075Sobrien for (v = 2; v <= di->nodes; v++) 56290075Sobrien if (di->dom[v] != di->key[v]) 56390075Sobrien di->dom[v] = di->dom[di->dom[v]]; 56490075Sobrien} 56590075Sobrien 566132718Skan/* Assign dfs numbers starting from NUM to NODE and its sons. */ 56790075Sobrien 568132718Skanstatic void 569132718Skanassign_dfs_numbers (struct et_node *node, int *num) 570132718Skan{ 571132718Skan struct et_node *son; 57290075Sobrien 573132718Skan node->dfs_num_in = (*num)++; 57490075Sobrien 575132718Skan if (node->son) 576132718Skan { 577132718Skan assign_dfs_numbers (node->son, num); 578132718Skan for (son = node->son->right; son != node->son; son = son->right) 579169689Skan assign_dfs_numbers (son, num); 580132718Skan } 581132718Skan 582132718Skan node->dfs_num_out = (*num)++; 583132718Skan} 584132718Skan 585132718Skan/* Compute the data necessary for fast resolving of dominator queries in a 586132718Skan static dominator tree. */ 587132718Skan 588132718Skanstatic void 589132718Skancompute_dom_fast_query (enum cdi_direction dir) 59090075Sobrien{ 591132718Skan int num = 0; 592132718Skan basic_block bb; 593132718Skan 594169689Skan gcc_assert (dom_info_available_p (dir)); 595132718Skan 596132718Skan if (dom_computed[dir] == DOM_OK) 597132718Skan return; 598132718Skan 599132718Skan FOR_ALL_BB (bb) 600132718Skan { 601132718Skan if (!bb->dom[dir]->father) 602169689Skan assign_dfs_numbers (bb->dom[dir], &num); 603132718Skan } 604132718Skan 605132718Skan dom_computed[dir] = DOM_OK; 606132718Skan} 607132718Skan 608132718Skan/* The main entry point into this module. DIR is set depending on whether 609132718Skan we want to compute dominators or postdominators. */ 610132718Skan 611132718Skanvoid 612132718Skancalculate_dominance_info (enum cdi_direction dir) 613132718Skan{ 61490075Sobrien struct dom_info di; 615117395Skan basic_block b; 61690075Sobrien 617132718Skan if (dom_computed[dir] == DOM_OK) 618132718Skan return; 619117395Skan 620169689Skan timevar_push (TV_DOMINANCE); 621169689Skan if (!dom_info_available_p (dir)) 622132718Skan { 623169689Skan gcc_assert (!n_bbs_in_dom_tree[dir]); 624117395Skan 625132718Skan FOR_ALL_BB (b) 626132718Skan { 627132718Skan b->dom[dir] = et_new_tree (b); 628132718Skan } 629169689Skan n_bbs_in_dom_tree[dir] = n_basic_blocks; 63090075Sobrien 631169689Skan init_dom_info (&di, dir); 632132718Skan calc_dfs_tree (&di, dir); 633132718Skan calc_idoms (&di, dir); 634117395Skan 635132718Skan FOR_EACH_BB (b) 636132718Skan { 637132718Skan TBB d = di.dom[di.dfs_order[b->index]]; 638117395Skan 639132718Skan if (di.dfs_to_bb[d]) 640132718Skan et_set_father (b->dom[dir], di.dfs_to_bb[d]->dom[dir]); 641132718Skan } 642132718Skan 643132718Skan free_dom_info (&di); 644132718Skan dom_computed[dir] = DOM_NO_FAST_QUERY; 645117395Skan } 646117395Skan 647132718Skan compute_dom_fast_query (dir); 648169689Skan 649169689Skan timevar_pop (TV_DOMINANCE); 650117395Skan} 651117395Skan 652132718Skan/* Free dominance information for direction DIR. */ 653117395Skanvoid 654132718Skanfree_dominance_info (enum cdi_direction dir) 655117395Skan{ 656117395Skan basic_block bb; 657117395Skan 658169689Skan if (!dom_info_available_p (dir)) 659132718Skan return; 660132718Skan 661132718Skan FOR_ALL_BB (bb) 662132718Skan { 663169689Skan et_free_tree_force (bb->dom[dir]); 664169689Skan bb->dom[dir] = NULL; 665132718Skan } 666169689Skan et_free_pools (); 667132718Skan 668169689Skan n_bbs_in_dom_tree[dir] = 0; 669169689Skan 670132718Skan dom_computed[dir] = DOM_NONE; 671117395Skan} 672117395Skan 673117395Skan/* Return the immediate dominator of basic block BB. */ 674117395Skanbasic_block 675132718Skanget_immediate_dominator (enum cdi_direction dir, basic_block bb) 676117395Skan{ 677132718Skan struct et_node *node = bb->dom[dir]; 678132718Skan 679169689Skan gcc_assert (dom_computed[dir]); 680132718Skan 681132718Skan if (!node->father) 682132718Skan return NULL; 683132718Skan 684169689Skan return node->father->data; 685117395Skan} 686117395Skan 687117395Skan/* Set the immediate dominator of the block possibly removing 688117395Skan existing edge. NULL can be used to remove any edge. */ 689117395Skaninline void 690132718Skanset_immediate_dominator (enum cdi_direction dir, basic_block bb, 691132718Skan basic_block dominated_by) 692117395Skan{ 693132718Skan struct et_node *node = bb->dom[dir]; 694117395Skan 695169689Skan gcc_assert (dom_computed[dir]); 696132718Skan 697132718Skan if (node->father) 698117395Skan { 699132718Skan if (node->father->data == dominated_by) 700169689Skan return; 701132718Skan et_split (node); 702117395Skan } 703132718Skan 704132718Skan if (dominated_by) 705132718Skan et_set_father (node, dominated_by->dom[dir]); 706132718Skan 707132718Skan if (dom_computed[dir] == DOM_OK) 708132718Skan dom_computed[dir] = DOM_NO_FAST_QUERY; 709117395Skan} 710117395Skan 711132718Skan/* Store all basic blocks immediately dominated by BB into BBS and return 712132718Skan their number. */ 713117395Skanint 714132718Skanget_dominated_by (enum cdi_direction dir, basic_block bb, basic_block **bbs) 715117395Skan{ 716132718Skan int n; 717132718Skan struct et_node *node = bb->dom[dir], *son = node->son, *ason; 718117395Skan 719169689Skan gcc_assert (dom_computed[dir]); 720132718Skan 721132718Skan if (!son) 722132718Skan { 723132718Skan *bbs = NULL; 724132718Skan return 0; 725132718Skan } 726132718Skan 727132718Skan for (ason = son->right, n = 1; ason != son; ason = ason->right) 728132718Skan n++; 729132718Skan 730169689Skan *bbs = XNEWVEC (basic_block, n); 731132718Skan (*bbs)[0] = son->data; 732132718Skan for (ason = son->right, n = 1; ason != son; ason = ason->right) 733132718Skan (*bbs)[n++] = ason->data; 734132718Skan 735117395Skan return n; 736117395Skan} 737117395Skan 738169689Skan/* Find all basic blocks that are immediately dominated (in direction DIR) 739169689Skan by some block between N_REGION ones stored in REGION, except for blocks 740169689Skan in the REGION itself. The found blocks are stored to DOMS and their number 741169689Skan is returned. */ 742169689Skan 743169689Skanunsigned 744169689Skanget_dominated_by_region (enum cdi_direction dir, basic_block *region, 745169689Skan unsigned n_region, basic_block *doms) 746169689Skan{ 747169689Skan unsigned n_doms = 0, i; 748169689Skan basic_block dom; 749169689Skan 750169689Skan for (i = 0; i < n_region; i++) 751169689Skan region[i]->flags |= BB_DUPLICATED; 752169689Skan for (i = 0; i < n_region; i++) 753169689Skan for (dom = first_dom_son (dir, region[i]); 754169689Skan dom; 755169689Skan dom = next_dom_son (dir, dom)) 756169689Skan if (!(dom->flags & BB_DUPLICATED)) 757169689Skan doms[n_doms++] = dom; 758169689Skan for (i = 0; i < n_region; i++) 759169689Skan region[i]->flags &= ~BB_DUPLICATED; 760169689Skan 761169689Skan return n_doms; 762169689Skan} 763169689Skan 764117395Skan/* Redirect all edges pointing to BB to TO. */ 765117395Skanvoid 766132718Skanredirect_immediate_dominators (enum cdi_direction dir, basic_block bb, 767132718Skan basic_block to) 768117395Skan{ 769132718Skan struct et_node *bb_node = bb->dom[dir], *to_node = to->dom[dir], *son; 770117395Skan 771169689Skan gcc_assert (dom_computed[dir]); 772132718Skan 773132718Skan if (!bb_node->son) 774132718Skan return; 775132718Skan 776132718Skan while (bb_node->son) 777117395Skan { 778132718Skan son = bb_node->son; 779132718Skan 780132718Skan et_split (son); 781132718Skan et_set_father (son, to_node); 782117395Skan } 783132718Skan 784132718Skan if (dom_computed[dir] == DOM_OK) 785132718Skan dom_computed[dir] = DOM_NO_FAST_QUERY; 786117395Skan} 787117395Skan 788117395Skan/* Find first basic block in the tree dominating both BB1 and BB2. */ 789117395Skanbasic_block 790132718Skannearest_common_dominator (enum cdi_direction dir, basic_block bb1, basic_block bb2) 791117395Skan{ 792169689Skan gcc_assert (dom_computed[dir]); 793132718Skan 794117395Skan if (!bb1) 795117395Skan return bb2; 796117395Skan if (!bb2) 797117395Skan return bb1; 798132718Skan 799132718Skan return et_nca (bb1->dom[dir], bb2->dom[dir])->data; 800117395Skan} 801117395Skan 802169689Skan 803169689Skan/* Find the nearest common dominator for the basic blocks in BLOCKS, 804169689Skan using dominance direction DIR. */ 805169689Skan 806169689Skanbasic_block 807169689Skannearest_common_dominator_for_set (enum cdi_direction dir, bitmap blocks) 808169689Skan{ 809169689Skan unsigned i, first; 810169689Skan bitmap_iterator bi; 811169689Skan basic_block dom; 812169689Skan 813169689Skan first = bitmap_first_set_bit (blocks); 814169689Skan dom = BASIC_BLOCK (first); 815169689Skan EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi) 816169689Skan if (dom != BASIC_BLOCK (i)) 817169689Skan dom = nearest_common_dominator (dir, dom, BASIC_BLOCK (i)); 818169689Skan 819169689Skan return dom; 820169689Skan} 821169689Skan 822169689Skan/* Given a dominator tree, we can determine whether one thing 823169689Skan dominates another in constant time by using two DFS numbers: 824169689Skan 825169689Skan 1. The number for when we visit a node on the way down the tree 826169689Skan 2. The number for when we visit a node on the way back up the tree 827169689Skan 828169689Skan You can view these as bounds for the range of dfs numbers the 829169689Skan nodes in the subtree of the dominator tree rooted at that node 830169689Skan will contain. 831169689Skan 832169689Skan The dominator tree is always a simple acyclic tree, so there are 833169689Skan only three possible relations two nodes in the dominator tree have 834169689Skan to each other: 835169689Skan 836169689Skan 1. Node A is above Node B (and thus, Node A dominates node B) 837169689Skan 838169689Skan A 839169689Skan | 840169689Skan C 841169689Skan / \ 842169689Skan B D 843169689Skan 844169689Skan 845169689Skan In the above case, DFS_Number_In of A will be <= DFS_Number_In of 846169689Skan B, and DFS_Number_Out of A will be >= DFS_Number_Out of B. This is 847169689Skan because we must hit A in the dominator tree *before* B on the walk 848169689Skan down, and we will hit A *after* B on the walk back up 849169689Skan 850169689Skan 2. Node A is below node B (and thus, node B dominates node A) 851169689Skan 852169689Skan 853169689Skan B 854169689Skan | 855169689Skan A 856169689Skan / \ 857169689Skan C D 858169689Skan 859169689Skan In the above case, DFS_Number_In of A will be >= DFS_Number_In of 860169689Skan B, and DFS_Number_Out of A will be <= DFS_Number_Out of B. 861169689Skan 862169689Skan This is because we must hit A in the dominator tree *after* B on 863169689Skan the walk down, and we will hit A *before* B on the walk back up 864169689Skan 865169689Skan 3. Node A and B are siblings (and thus, neither dominates the other) 866169689Skan 867169689Skan C 868169689Skan | 869169689Skan D 870169689Skan / \ 871169689Skan A B 872169689Skan 873169689Skan In the above case, DFS_Number_In of A will *always* be <= 874169689Skan DFS_Number_In of B, and DFS_Number_Out of A will *always* be <= 875169689Skan DFS_Number_Out of B. This is because we will always finish the dfs 876169689Skan walk of one of the subtrees before the other, and thus, the dfs 877169689Skan numbers for one subtree can't intersect with the range of dfs 878169689Skan numbers for the other subtree. If you swap A and B's position in 879169689Skan the dominator tree, the comparison changes direction, but the point 880169689Skan is that both comparisons will always go the same way if there is no 881169689Skan dominance relationship. 882169689Skan 883169689Skan Thus, it is sufficient to write 884169689Skan 885169689Skan A_Dominates_B (node A, node B) 886169689Skan { 887169689Skan return DFS_Number_In(A) <= DFS_Number_In(B) 888169689Skan && DFS_Number_Out (A) >= DFS_Number_Out(B); 889169689Skan } 890169689Skan 891169689Skan A_Dominated_by_B (node A, node B) 892169689Skan { 893169689Skan return DFS_Number_In(A) >= DFS_Number_In(A) 894169689Skan && DFS_Number_Out (A) <= DFS_Number_Out(B); 895169689Skan } */ 896169689Skan 897117395Skan/* Return TRUE in case BB1 is dominated by BB2. */ 898117395Skanbool 899132718Skandominated_by_p (enum cdi_direction dir, basic_block bb1, basic_block bb2) 900169689Skan{ 901132718Skan struct et_node *n1 = bb1->dom[dir], *n2 = bb2->dom[dir]; 902132718Skan 903169689Skan gcc_assert (dom_computed[dir]); 904132718Skan 905132718Skan if (dom_computed[dir] == DOM_OK) 906132718Skan return (n1->dfs_num_in >= n2->dfs_num_in 907169689Skan && n1->dfs_num_out <= n2->dfs_num_out); 908132718Skan 909132718Skan return et_below (n1, n2); 910117395Skan} 911117395Skan 912169689Skan/* Returns the entry dfs number for basic block BB, in the direction DIR. */ 913169689Skan 914169689Skanunsigned 915169689Skanbb_dom_dfs_in (enum cdi_direction dir, basic_block bb) 916169689Skan{ 917169689Skan struct et_node *n = bb->dom[dir]; 918169689Skan 919169689Skan gcc_assert (dom_computed[dir] == DOM_OK); 920169689Skan return n->dfs_num_in; 921169689Skan} 922169689Skan 923169689Skan/* Returns the exit dfs number for basic block BB, in the direction DIR. */ 924169689Skan 925169689Skanunsigned 926169689Skanbb_dom_dfs_out (enum cdi_direction dir, basic_block bb) 927169689Skan{ 928169689Skan struct et_node *n = bb->dom[dir]; 929169689Skan 930169689Skan gcc_assert (dom_computed[dir] == DOM_OK); 931169689Skan return n->dfs_num_out; 932169689Skan} 933169689Skan 934117395Skan/* Verify invariants of dominator structure. */ 935117395Skanvoid 936132718Skanverify_dominators (enum cdi_direction dir) 937117395Skan{ 938117395Skan int err = 0; 939117395Skan basic_block bb; 940117395Skan 941169689Skan gcc_assert (dom_info_available_p (dir)); 942132718Skan 943117395Skan FOR_EACH_BB (bb) 944117395Skan { 945117395Skan basic_block dom_bb; 946169689Skan basic_block imm_bb; 947117395Skan 948132718Skan dom_bb = recount_dominator (dir, bb); 949169689Skan imm_bb = get_immediate_dominator (dir, bb); 950169689Skan if (dom_bb != imm_bb) 95190075Sobrien { 952169689Skan if ((dom_bb == NULL) || (imm_bb == NULL)) 953169689Skan error ("dominator of %d status unknown", bb->index); 954169689Skan else 955169689Skan error ("dominator of %d should be %d, not %d", 956169689Skan bb->index, dom_bb->index, imm_bb->index); 957117395Skan err = 1; 958117395Skan } 959117395Skan } 960169689Skan 961169689Skan if (dir == CDI_DOMINATORS) 962169689Skan { 963169689Skan FOR_EACH_BB (bb) 964169689Skan { 965169689Skan if (!dominated_by_p (dir, bb, ENTRY_BLOCK_PTR)) 966169689Skan { 967169689Skan error ("ENTRY does not dominate bb %d", bb->index); 968169689Skan err = 1; 969169689Skan } 970169689Skan } 971169689Skan } 972169689Skan 973169689Skan gcc_assert (!err); 974117395Skan} 97590075Sobrien 976169689Skan/* Determine immediate dominator (or postdominator, according to DIR) of BB, 977169689Skan assuming that dominators of other blocks are correct. We also use it to 978169689Skan recompute the dominators in a restricted area, by iterating it until it 979169689Skan reaches a fixed point. */ 980169689Skan 981117395Skanbasic_block 982132718Skanrecount_dominator (enum cdi_direction dir, basic_block bb) 983117395Skan{ 984169689Skan basic_block dom_bb = NULL; 985169689Skan edge e; 986169689Skan edge_iterator ei; 987117395Skan 988169689Skan gcc_assert (dom_computed[dir]); 989132718Skan 990169689Skan if (dir == CDI_DOMINATORS) 991169689Skan { 992169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 993169689Skan { 994169689Skan /* Ignore the predecessors that either are not reachable from 995169689Skan the entry block, or whose dominator was not determined yet. */ 996169689Skan if (!dominated_by_p (dir, e->src, ENTRY_BLOCK_PTR)) 997169689Skan continue; 998117395Skan 999169689Skan if (!dominated_by_p (dir, e->src, bb)) 1000169689Skan dom_bb = nearest_common_dominator (dir, dom_bb, e->src); 1001169689Skan } 1002169689Skan } 1003169689Skan else 1004169689Skan { 1005169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 1006169689Skan { 1007169689Skan if (!dominated_by_p (dir, e->dest, bb)) 1008169689Skan dom_bb = nearest_common_dominator (dir, dom_bb, e->dest); 1009169689Skan } 1010169689Skan } 1011169689Skan 1012169689Skan return dom_bb; 1013117395Skan} 1014117395Skan 1015117395Skan/* Iteratively recount dominators of BBS. The change is supposed to be local 1016117395Skan and not to grow further. */ 1017117395Skanvoid 1018132718Skaniterate_fix_dominators (enum cdi_direction dir, basic_block *bbs, int n) 1019117395Skan{ 1020117395Skan int i, changed = 1; 1021117395Skan basic_block old_dom, new_dom; 1022117395Skan 1023169689Skan gcc_assert (dom_computed[dir]); 1024132718Skan 1025169689Skan for (i = 0; i < n; i++) 1026169689Skan set_immediate_dominator (dir, bbs[i], NULL); 1027169689Skan 1028117395Skan while (changed) 1029117395Skan { 1030117395Skan changed = 0; 1031117395Skan for (i = 0; i < n; i++) 1032117395Skan { 1033132718Skan old_dom = get_immediate_dominator (dir, bbs[i]); 1034132718Skan new_dom = recount_dominator (dir, bbs[i]); 1035117395Skan if (old_dom != new_dom) 1036117395Skan { 1037117395Skan changed = 1; 1038132718Skan set_immediate_dominator (dir, bbs[i], new_dom); 1039117395Skan } 104090075Sobrien } 104190075Sobrien } 1042169689Skan 1043169689Skan for (i = 0; i < n; i++) 1044169689Skan gcc_assert (get_immediate_dominator (dir, bbs[i])); 1045117395Skan} 104690075Sobrien 1047117395Skanvoid 1048132718Skanadd_to_dominance_info (enum cdi_direction dir, basic_block bb) 1049117395Skan{ 1050169689Skan gcc_assert (dom_computed[dir]); 1051169689Skan gcc_assert (!bb->dom[dir]); 1052132718Skan 1053169689Skan n_bbs_in_dom_tree[dir]++; 1054169689Skan 1055132718Skan bb->dom[dir] = et_new_tree (bb); 1056132718Skan 1057132718Skan if (dom_computed[dir] == DOM_OK) 1058132718Skan dom_computed[dir] = DOM_NO_FAST_QUERY; 105990075Sobrien} 1060117395Skan 1061117395Skanvoid 1062132718Skandelete_from_dominance_info (enum cdi_direction dir, basic_block bb) 1063117395Skan{ 1064169689Skan gcc_assert (dom_computed[dir]); 1065132718Skan 1066132718Skan et_free_tree (bb->dom[dir]); 1067132718Skan bb->dom[dir] = NULL; 1068169689Skan n_bbs_in_dom_tree[dir]--; 1069132718Skan 1070132718Skan if (dom_computed[dir] == DOM_OK) 1071132718Skan dom_computed[dir] = DOM_NO_FAST_QUERY; 1072117395Skan} 1073117395Skan 1074132718Skan/* Returns the first son of BB in the dominator or postdominator tree 1075132718Skan as determined by DIR. */ 1076132718Skan 1077132718Skanbasic_block 1078132718Skanfirst_dom_son (enum cdi_direction dir, basic_block bb) 1079132718Skan{ 1080132718Skan struct et_node *son = bb->dom[dir]->son; 1081132718Skan 1082132718Skan return son ? son->data : NULL; 1083132718Skan} 1084132718Skan 1085132718Skan/* Returns the next dominance son after BB in the dominator or postdominator 1086132718Skan tree as determined by DIR, or NULL if it was the last one. */ 1087132718Skan 1088132718Skanbasic_block 1089132718Skannext_dom_son (enum cdi_direction dir, basic_block bb) 1090132718Skan{ 1091132718Skan struct et_node *next = bb->dom[dir]->right; 1092132718Skan 1093132718Skan return next->father->son == next ? NULL : next->data; 1094132718Skan} 1095132718Skan 1096169689Skan/* Returns true if dominance information for direction DIR is available. */ 1097169689Skan 1098169689Skanbool 1099169689Skandom_info_available_p (enum cdi_direction dir) 1100169689Skan{ 1101169689Skan return dom_computed[dir] != DOM_NONE; 1102169689Skan} 1103169689Skan 1104117395Skanvoid 1105132718Skandebug_dominance_info (enum cdi_direction dir) 1106117395Skan{ 1107117395Skan basic_block bb, bb2; 1108117395Skan FOR_EACH_BB (bb) 1109132718Skan if ((bb2 = get_immediate_dominator (dir, bb))) 1110117395Skan fprintf (stderr, "%i %i\n", bb->index, bb2->index); 1111117395Skan} 1112