gcc/dominance.c

   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 #include "errors.h"
  42 #include "et-forest.h"
  43
  44 struct dominance_info
  45 {
  46   et_forest_t forest;
  47   varray_type varray;
  48 };
  49
  50 #define BB_NODE(info, bb) \
  51   ((et_forest_node_t)VARRAY_GENERIC_PTR ((info)->varray, (bb)->index + 2))
  52 #define SET_BB_NODE(info, bb, node) \
  53   (VARRAY_GENERIC_PTR ((info)->varray, (bb)->index + 2) = (node))
  54
  55 /* We name our nodes with integers, beginning with 1.  Zero is reserved for
  56    'undefined' or 'end of list'.  The name of each node is given by the dfs
  57    number of the corresponding basic block.  Please note, that we include the
  58    artificial ENTRY_BLOCK (or EXIT_BLOCK in the post-dom case) in our lists to
  59    support multiple entry points.  As it has no real basic block index we use
  60    'last_basic_block' for that.  Its dfs number is of course 1.  */
  61
  62 /* Type of Basic Block aka. TBB */
  63 typedef unsigned int TBB;
  64
  65 /* We work in a poor-mans object oriented fashion, and carry an instance of
  66    this structure through all our 'methods'.  It holds various arrays
  67    reflecting the (sub)structure of the flowgraph.  Most of them are of type
  68    TBB and are also indexed by TBB.  */
  69
  70 struct dom_info
  71 {
  72   /* The parent of a node in the DFS tree.  */
  73   TBB *dfs_parent;
  74   /* For a node x key[x] is roughly the node nearest to the root from which
  75      exists a way to x only over nodes behind x.  Such a node is also called
  76      semidominator.  */
  77   TBB *key;
  78   /* The value in path_min[x] is the node y on the path from x to the root of
  79      the tree x is in with the smallest key[y].  */
  80   TBB *path_min;
  81   /* bucket[x] points to the first node of the set of nodes having x as key.  */
  82   TBB *bucket;
  83   /* And next_bucket[x] points to the next node.  */
  84   TBB *next_bucket;
  85   /* After the algorithm is done, dom[x] contains the immediate dominator
  86      of x.  */
  87   TBB *dom;
  88
  89   /* The following few fields implement the structures needed for disjoint
  90      sets.  */
  91   /* set_chain[x] is the next node on the path from x to the representant
  92      of the set containing x.  If set_chain[x]==0 then x is a root.  */
  93   TBB *set_chain;
  94   /* set_size[x] is the number of elements in the set named by x.  */
  95   unsigned int *set_size;
  96   /* set_child[x] is used for balancing the tree representing a set.  It can
  97      be understood as the next sibling of x.  */
  98   TBB *set_child;
  99
 100   /* If b is the number of a basic block (BB->index), dfs_order[b] is the
 101      number of that node in DFS order counted from 1.  This is an index
 102      into most of the other arrays in this structure.  */
 103   TBB *dfs_order;
 104   /* If x is the DFS-index of a node which corresponds with an basic block,
 105      dfs_to_bb[x] is that basic block.  Note, that in our structure there are
 106      more nodes that basic blocks, so only dfs_to_bb[dfs_order[bb->index]]==bb
 107      is true for every basic block bb, but not the opposite.  */
 108   basic_block *dfs_to_bb;
 109
 110   /* This is the next free DFS number when creating the DFS tree or forest.  */
 111   unsigned int dfsnum;
 112   /* The number of nodes in the DFS tree (==dfsnum-1).  */
 113   unsigned int nodes;
 114 };
 115
 116 static void init_dom_info               PARAMS ((struct dom_info *));
 117 static void free_dom_info               PARAMS ((struct dom_info *));
 118 static void calc_dfs_tree_nonrec        PARAMS ((struct dom_info *,
 119                                                  basic_block,
 120                                                  enum cdi_direction));
 121 static void calc_dfs_tree               PARAMS ((struct dom_info *,
 122                                                  enum cdi_direction));
 123 static void compress                    PARAMS ((struct dom_info *, TBB));
 124 static TBB eval                         PARAMS ((struct dom_info *, TBB));
 125 static void link_roots                  PARAMS ((struct dom_info *, TBB, TBB));
 126 static void calc_idoms                  PARAMS ((struct dom_info *,
 127                                                  enum cdi_direction));
 128 void debug_dominance_info               PARAMS ((dominance_info));
 129
 130 /* Helper macro for allocating and initializing an array,
 131    for aesthetic reasons.  */
 132 #define init_ar(var, type, num, content)                        \
 133   do                                                            \
 134     {                                                           \
 135       unsigned int i = 1;    /* Catch content == i.  */         \
 136       if (! (content))                                          \
 137         (var) = (type *) xcalloc ((num), sizeof (type));        \
 138       else                                                      \
 139         {                                                       \
 140           (var) = (type *) xmalloc ((num) * sizeof (type));     \
 141           for (i = 0; i < num; i++)                             \
 142             (var)[i] = (content);                               \
 143         }                                                       \
 144     }                                                           \
 145   while (0)
 146
 147 /* Allocate all needed memory in a pessimistic fashion (so we round up).
 148    This initialises the contents of DI, which already must be allocated.  */
 149
 150 static void
 151 init_dom_info (di)
 152      struct dom_info *di;
 153 {
 154   /* We need memory for n_basic_blocks nodes and the ENTRY_BLOCK or
 155      EXIT_BLOCK.  */
 156   unsigned int num = n_basic_blocks + 1 + 1;
 157   init_ar (di->dfs_parent, TBB, num, 0);
 158   init_ar (di->path_min, TBB, num, i);
 159   init_ar (di->key, TBB, num, i);
 160   init_ar (di->dom, TBB, num, 0);
 161
 162   init_ar (di->bucket, TBB, num, 0);
 163   init_ar (di->next_bucket, TBB, num, 0);
 164
 165   init_ar (di->set_chain, TBB, num, 0);
 166   init_ar (di->set_size, unsigned int, num, 1);
 167   init_ar (di->set_child, TBB, num, 0);
 168
 169   init_ar (di->dfs_order, TBB, (unsigned int) last_basic_block + 1, 0);
 170   init_ar (di->dfs_to_bb, basic_block, num, 0);
 171
 172   di->dfsnum = 1;
 173   di->nodes = 0;
 174 }
 175
 176 #undef init_ar
 177
 178 /* Free all allocated memory in DI, but not DI itself.  */
 179
 180 static void
 181 free_dom_info (di)
 182      struct dom_info *di;
 183 {
 184   free (di->dfs_parent);
 185   free (di->path_min);
 186   free (di->key);
 187   free (di->dom);
 188   free (di->bucket);
 189   free (di->next_bucket);
 190   free (di->set_chain);
 191   free (di->set_size);
 192   free (di->set_child);
 193   free (di->dfs_order);
 194   free (di->dfs_to_bb);
 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
 203 static void
 204 calc_dfs_tree_nonrec (di, bb, reverse)
 205      struct dom_info *di;
 206      basic_block bb;
 207      enum cdi_direction reverse;
 208 {
 209   /* We never call this with bb==EXIT_BLOCK_PTR (ENTRY_BLOCK_PTR if REVERSE).  */
 210   /* We call this _only_ if bb is not already visited.  */
 211   edge e;
 212   TBB child_i, my_i = 0;
 213   edge *stack;
 214   int sp;
 215   /* Start block (ENTRY_BLOCK_PTR for forward problem, EXIT_BLOCK for backward
 216      problem).  */
 217   basic_block en_block;
 218   /* Ending block.  */
 219   basic_block ex_block;
 220
 221   stack = (edge *) xmalloc ((n_basic_blocks + 3) * sizeof (edge));
 222   sp = 0;
 223
 224   /* Initialize our border blocks, and the first edge.  */
 225   if (reverse)
 226     {
 227       e = bb->pred;
 228       en_block = EXIT_BLOCK_PTR;
 229       ex_block = ENTRY_BLOCK_PTR;
 230     }
 231   else
 232     {
 233       e = bb->succ;
 234       en_block = ENTRY_BLOCK_PTR;
 235       ex_block = EXIT_BLOCK_PTR;
 236     }
 237
 238   /* When the stack is empty we break out of this loop.  */
 239   while (1)
 240     {
 241       basic_block bn;
 242
 243       /* This loop traverses edges e in depth first manner, and fills the
 244          stack.  */
 245       while (e)
 246         {
 247           edge e_next;
 248
 249           /* Deduce from E the current and the next block (BB and BN), and the
 250              next edge.  */
 251           if (reverse)
 252             {
 253               bn = e->src;
 254
 255               /* If the next node BN is either already visited or a border
 256                  block the current edge is useless, and simply overwritten
 257                  with the next edge out of the current node.  */
 258               if (bn == ex_block || di->dfs_order[bn->index])
 259                 {
 260                   e = e->pred_next;
 261                   continue;
 262                 }
 263               bb = e->dest;
 264               e_next = bn->pred;
 265             }
 266           else
 267             {
 268               bn = e->dest;
 269               if (bn == ex_block || di->dfs_order[bn->index])
 270                 {
 271                   e = e->succ_next;
 272                   continue;
 273                 }
 274               bb = e->src;
 275               e_next = bn->succ;
 276             }
 277
 278           if (bn == en_block)
 279             abort ();
 280
 281           /* Fill the DFS tree info calculatable _before_ recursing.  */
 282           if (bb != en_block)
 283             my_i = di->dfs_order[bb->index];
 284           else
 285             my_i = di->dfs_order[last_basic_block];
 286           child_i = di->dfs_order[bn->index] = di->dfsnum++;
 287           di->dfs_to_bb[child_i] = bn;
 288           di->dfs_parent[child_i] = my_i;
 289
 290           /* Save the current point in the CFG on the stack, and recurse.  */
 291           stack[sp++] = e;
 292           e = e_next;
 293         }
 294
 295       if (!sp)
 296         break;
 297       e = stack[--sp];
 298
 299       /* OK.  The edge-list was exhausted, meaning normally we would
 300          end the recursion.  After returning from the recursive call,
 301          there were (may be) other statements which were run after a
 302          child node was completely considered by DFS.  Here is the
 303          point to do it in the non-recursive variant.
 304          E.g. The block just completed is in e->dest for forward DFS,
 305          the block not yet completed (the parent of the one above)
 306          in e->src.  This could be used e.g. for computing the number of
 307          descendants or the tree depth.  */
 308       if (reverse)
 309         e = e->pred_next;
 310       else
 311         e = e->succ_next;
 312     }
 313   free (stack);
 314 }
 315
 316 /* The main entry for calculating the DFS tree or forest.  DI is our working
 317    structure and REVERSE is true, if we are interested in the reverse flow
 318    graph.  In that case the result is not necessarily a tree but a forest,
 319    because there may be nodes from which the EXIT_BLOCK is unreachable.  */
 320
 321 static void
 322 calc_dfs_tree (di, reverse)
 323      struct dom_info *di;
 324      enum cdi_direction reverse;
 325 {
 326   /* The first block is the ENTRY_BLOCK (or EXIT_BLOCK if REVERSE).  */
 327   basic_block begin = reverse ? EXIT_BLOCK_PTR : ENTRY_BLOCK_PTR;
 328   di->dfs_order[last_basic_block] = di->dfsnum;
 329   di->dfs_to_bb[di->dfsnum] = begin;
 330   di->dfsnum++;
 331
 332   calc_dfs_tree_nonrec (di, begin, reverse);
 333
 334   if (reverse)
 335     {
 336       /* In the post-dom case we may have nodes without a path to EXIT_BLOCK.
 337          They are reverse-unreachable.  In the dom-case we disallow such
 338          nodes, but in post-dom we have to deal with them, so we simply
 339          include them in the DFS tree which actually becomes a forest.  */
 340       basic_block b;
 341       FOR_EACH_BB_REVERSE (b)
 342         {
 343           if (di->dfs_order[b->index])
 344             continue;
 345           di->dfs_order[b->index] = di->dfsnum;
 346           di->dfs_to_bb[di->dfsnum] = b;
 347           di->dfsnum++;
 348           calc_dfs_tree_nonrec (di, b, reverse);
 349         }
 350     }
 351
 352   di->nodes = di->dfsnum - 1;
 353
 354   /* This aborts e.g. when there is _no_ path from ENTRY to EXIT at all.  */
 355   if (di->nodes != (unsigned int) n_basic_blocks + 1)
 356     abort ();
 357 }
 358
 359 /* Compress the path from V to the root of its set and update path_min at the
 360    same time.  After compress(di, V) set_chain[V] is the root of the set V is
 361    in and path_min[V] is the node with the smallest key[] value on the path
 362    from V to that root.  */
 363
 364 static void
 365 compress (di, v)
 366      struct dom_info *di;
 367      TBB v;
 368 {
 369   /* Btw. It's not worth to unrecurse compress() as the depth is usually not
 370      greater than 5 even for huge graphs (I've not seen call depth > 4).
 371      Also performance wise compress() ranges _far_ behind eval().  */
 372   TBB parent = di->set_chain[v];
 373   if (di->set_chain[parent])
 374     {
 375       compress (di, parent);
 376       if (di->key[di->path_min[parent]] < di->key[di->path_min[v]])
 377         di->path_min[v] = di->path_min[parent];
 378       di->set_chain[v] = di->set_chain[parent];
 379     }
 380 }
 381
 382 /* Compress the path from V to the set root of V if needed (when the root has
 383    changed since the last call).  Returns the node with the smallest key[]
 384    value on the path from V to the root.  */
 385
 386 static inline TBB
 387 eval (di, v)
 388      struct dom_info *di;
 389      TBB v;
 390 {
 391   /* The representant of the set V is in, also called root (as the set
 392      representation is a tree).  */
 393   TBB rep = di->set_chain[v];
 394
 395   /* V itself is the root.  */
 396   if (!rep)
 397     return di->path_min[v];
 398
 399   /* Compress only if necessary.  */
 400   if (di->set_chain[rep])
 401     {
 402       compress (di, v);
 403       rep = di->set_chain[v];
 404     }
 405
 406   if (di->key[di->path_min[rep]] >= di->key[di->path_min[v]])
 407     return di->path_min[v];
 408   else
 409     return di->path_min[rep];
 410 }
 411
 412 /* This essentially merges the two sets of V and W, giving a single set with
 413    the new root V.  The internal representation of these disjoint sets is a
 414    balanced tree.  Currently link(V,W) is only used with V being the parent
 415    of W.  */
 416
 417 static void
 418 link_roots (di, v, w)
 419      struct dom_info *di;
 420      TBB v, w;
 421 {
 422   TBB s = w;
 423
 424   /* Rebalance the tree.  */
 425   while (di->key[di->path_min[w]] < di->key[di->path_min[di->set_child[s]]])
 426     {
 427       if (di->set_size[s] + di->set_size[di->set_child[di->set_child[s]]]
 428           >= 2 * di->set_size[di->set_child[s]])
 429         {
 430           di->set_chain[di->set_child[s]] = s;
 431           di->set_child[s] = di->set_child[di->set_child[s]];
 432         }
 433       else
 434         {
 435           di->set_size[di->set_child[s]] = di->set_size[s];
 436           s = di->set_chain[s] = di->set_child[s];
 437         }
 438     }
 439
 440   di->path_min[s] = di->path_min[w];
 441   di->set_size[v] += di->set_size[w];
 442   if (di->set_size[v] < 2 * di->set_size[w])
 443     {
 444       TBB tmp = s;
 445       s = di->set_child[v];
 446       di->set_child[v] = tmp;
 447     }
 448
 449   /* Merge all subtrees.  */
 450   while (s)
 451     {
 452       di->set_chain[s] = v;
 453       s = di->set_child[s];
 454     }
 455 }
 456
 457 /* This calculates the immediate dominators (or post-dominators if REVERSE is
 458    true).  DI is our working structure and should hold the DFS forest.
 459    On return the immediate dominator to node V is in di->dom[V].  */
 460
 461 static void
 462 calc_idoms (di, reverse)
 463      struct dom_info *di;
 464      enum cdi_direction reverse;
 465 {
 466   TBB v, w, k, par;
 467   basic_block en_block;
 468   if (reverse)
 469     en_block = EXIT_BLOCK_PTR;
 470   else
 471     en_block = ENTRY_BLOCK_PTR;
 472
 473   /* Go backwards in DFS order, to first look at the leafs.  */
 474   v = di->nodes;
 475   while (v > 1)
 476     {
 477       basic_block bb = di->dfs_to_bb[v];
 478       edge e, e_next;
 479
 480       par = di->dfs_parent[v];
 481       k = v;
 482       if (reverse)
 483         e = bb->succ;
 484       else
 485         e = bb->pred;
 486
 487       /* Search all direct predecessors for the smallest node with a path
 488          to them.  That way we have the smallest node with also a path to
 489          us only over nodes behind us.  In effect we search for our
 490          semidominator.  */
 491       for (; e; e = e_next)
 492         {
 493           TBB k1;
 494           basic_block b;
 495
 496           if (reverse)
 497             {
 498               b = e->dest;
 499               e_next = e->succ_next;
 500             }
 501           else
 502             {
 503               b = e->src;
 504               e_next = e->pred_next;
 505             }
 506           if (b == en_block)
 507             k1 = di->dfs_order[last_basic_block];
 508           else
 509             k1 = di->dfs_order[b->index];
 510
 511           /* Call eval() only if really needed.  If k1 is above V in DFS tree,
 512              then we know, that eval(k1) == k1 and key[k1] == k1.  */
 513           if (k1 > v)
 514             k1 = di->key[eval (di, k1)];
 515           if (k1 < k)
 516             k = k1;
 517         }
 518
 519       di->key[v] = k;
 520       link_roots (di, par, v);
 521       di->next_bucket[v] = di->bucket[k];
 522       di->bucket[k] = v;
 523
 524       /* Transform semidominators into dominators.  */
 525       for (w = di->bucket[par]; w; w = di->next_bucket[w])
 526         {
 527           k = eval (di, w);
 528           if (di->key[k] < di->key[w])
 529             di->dom[w] = k;
 530           else
 531             di->dom[w] = par;
 532         }
 533       /* We don't need to cleanup next_bucket[].  */
 534       di->bucket[par] = 0;
 535       v--;
 536     }
 537
 538   /* Explicitly define the dominators.  */
 539   di->dom[1] = 0;
 540   for (v = 2; v <= di->nodes; v++)
 541     if (di->dom[v] != di->key[v])
 542       di->dom[v] = di->dom[di->dom[v]];
 543 }
 544
 545 /* The main entry point into this module.  IDOM is an integer array with room
 546    for last_basic_block integers, DOMS is a preallocated sbitmap array having
 547    room for last_basic_block^2 bits, and POST is true if the caller wants to
 548    know post-dominators.
 549
 550    On return IDOM[i] will be the BB->index of the immediate (post) dominator
 551    of basic block i, and DOMS[i] will have set bit j if basic block j is a
 552    (post)dominator for block i.
 553
 554    Either IDOM or DOMS may be NULL (meaning the caller is not interested in
 555    immediate resp. all dominators).  */
 556
 557 dominance_info
 558 calculate_dominance_info (reverse)
 559      enum cdi_direction reverse;
 560 {
 561   struct dom_info di;
 562   dominance_info info;
 563   basic_block b;
 564
 565   /* allocate structure for dominance information.  */
 566   info = xmalloc (sizeof (struct dominance_info));
 567   info->forest = et_forest_create ();
 568   VARRAY_GENERIC_PTR_INIT (info->varray, last_basic_block + 3, "dominance info");
 569
 570   /* Add the two well-known basic blocks.  */
 571   SET_BB_NODE (info, ENTRY_BLOCK_PTR, et_forest_add_node (info->forest,
 572                                                           ENTRY_BLOCK_PTR));
 573   SET_BB_NODE (info, EXIT_BLOCK_PTR, et_forest_add_node (info->forest,
 574                                                          EXIT_BLOCK_PTR));
 575   FOR_EACH_BB (b)
 576     SET_BB_NODE (info, b, et_forest_add_node (info->forest, b));
 577
 578   init_dom_info (&di);
 579   calc_dfs_tree (&di, reverse);
 580   calc_idoms (&di, reverse);
 581
 582
 583   FOR_EACH_BB (b)
 584     {
 585       TBB d = di.dom[di.dfs_order[b->index]];
 586
 587       if (di.dfs_to_bb[d])
 588         et_forest_add_edge (info->forest, BB_NODE (info, di.dfs_to_bb[d]), BB_NODE (info, b));
 589     }
 590
 591   free_dom_info (&di);
 592   return info;
 593 }
 594
 595 /* Free dominance information.  */
 596 void
 597 free_dominance_info (info)
 598      dominance_info info;
 599 {
 600   basic_block bb;
 601
 602   /* Allow users to create new basic block without setting up the dominance
 603      information for them.  */
 604   FOR_EACH_BB (bb)
 605     if (bb->index < (int)(info->varray->num_elements - 2)
 606         && BB_NODE (info, bb))
 607       delete_from_dominance_info (info, bb);
 608   delete_from_dominance_info (info, ENTRY_BLOCK_PTR);
 609   delete_from_dominance_info (info, EXIT_BLOCK_PTR);
 610   et_forest_delete (info->forest);
 611   VARRAY_GROW (info->varray, 0);
 612   free (info);
 613 }
 614
 615 /* Return the immediate dominator of basic block BB.  */
 616 basic_block
 617 get_immediate_dominator (dom, bb)
 618      dominance_info dom;
 619      basic_block bb;
 620 {
 621   return et_forest_node_value (dom->forest,
 622                                et_forest_parent (dom->forest,
 623                                                  BB_NODE (dom, bb)));
 624 }
 625
 626 /* Set the immediate dominator of the block possibly removing
 627    existing edge.  NULL can be used to remove any edge.  */
 628 inline void
 629 set_immediate_dominator (dom, bb, dominated_by)
 630      dominance_info dom;
 631      basic_block bb, dominated_by;
 632 {
 633   void *aux_bb_node;
 634   et_forest_node_t bb_node = BB_NODE (dom, bb);
 635
 636   aux_bb_node = et_forest_parent (dom->forest, bb_node);
 637   if (aux_bb_node)
 638     et_forest_remove_edge (dom->forest, aux_bb_node, bb_node);
 639   if (dominated_by != NULL)
 640     {
 641       if (bb == dominated_by)
 642         abort ();
 643       if (!et_forest_add_edge (dom->forest, BB_NODE (dom, dominated_by), bb_node))
 644         abort ();
 645     }
 646 }
 647
 648 /* Store all basic blocks dominated by BB into BBS and return their number.  */
 649 int
 650 get_dominated_by (dom, bb, bbs)
 651      dominance_info dom;
 652      basic_block bb;
 653      basic_block **bbs;
 654 {
 655   int n, i;
 656
 657   *bbs = xmalloc (n_basic_blocks * sizeof (basic_block));
 658   n = et_forest_enumerate_sons (dom->forest, BB_NODE (dom, bb), (et_forest_node_t *)*bbs);
 659   for (i = 0; i < n; i++)
 660    (*bbs)[i] = et_forest_node_value (dom->forest, (et_forest_node_t)(*bbs)[i]);
 661   return n;
 662 }
 663
 664 /* Redirect all edges pointing to BB to TO.  */
 665 void
 666 redirect_immediate_dominators (dom, bb, to)
 667      dominance_info dom;
 668      basic_block bb;
 669      basic_block to;
 670 {
 671   et_forest_node_t *bbs = xmalloc (n_basic_blocks * sizeof (basic_block));
 672   et_forest_node_t node = BB_NODE (dom, bb);
 673   et_forest_node_t node2 = BB_NODE (dom, to);
 674   int n = et_forest_enumerate_sons (dom->forest, node, bbs);
 675   int i;
 676
 677   for (i = 0; i < n; i++)
 678     {
 679       et_forest_remove_edge (dom->forest, node, bbs[i]);
 680       et_forest_add_edge (dom->forest, node2, bbs[i]);
 681     }
 682   free (bbs);
 683 }
 684
 685 /* Find first basic block in the tree dominating both BB1 and BB2.  */
 686 basic_block
 687 nearest_common_dominator (dom, bb1, bb2)
 688      dominance_info dom;
 689      basic_block bb1;
 690      basic_block bb2;
 691 {
 692   if (!bb1)
 693     return bb2;
 694   if (!bb2)
 695     return bb1;
 696   return et_forest_node_value (dom->forest,
 697                                et_forest_common_ancestor (dom->forest,
 698                                                           BB_NODE (dom, bb1),
 699                                                           BB_NODE (dom,
 700                                                                    bb2)));
 701 }
 702
 703 /* Return TRUE in case BB1 is dominated by BB2.  */
 704 bool
 705 dominated_by_p (dom, bb1, bb2)
 706      dominance_info dom;
 707      basic_block bb1;
 708      basic_block bb2;
 709 {
 710   return nearest_common_dominator (dom, bb1, bb2) == bb2;
 711 }
 712
 713 /* Verify invariants of dominator structure.  */
 714 void
 715 verify_dominators (dom)
 716      dominance_info dom;
 717 {
 718   int err = 0;
 719   basic_block bb;
 720
 721   FOR_EACH_BB (bb)
 722     {
 723       basic_block dom_bb;
 724
 725       dom_bb = recount_dominator (dom, bb);
 726       if (dom_bb != get_immediate_dominator (dom, bb))
 727         {
 728           error ("dominator of %d should be %d, not %d",
 729            bb->index, dom_bb->index, get_immediate_dominator(dom, bb)->index);
 730           err = 1;
 731         }
 732     }
 733   if (err)
 734     abort ();
 735 }
 736
 737 /* Recount dominator of BB.  */
 738 basic_block
 739 recount_dominator (dom, bb)
 740      dominance_info dom;
 741      basic_block bb;
 742 {
 743    basic_block dom_bb = NULL;
 744    edge e;
 745
 746    for (e = bb->pred; e; e = e->pred_next)
 747      {
 748        if (!dominated_by_p (dom, e->src, bb))
 749          dom_bb = nearest_common_dominator (dom, dom_bb, e->src);
 750      }
 751
 752    return dom_bb;
 753 }
 754
 755 /* Iteratively recount dominators of BBS. The change is supposed to be local
 756    and not to grow further.  */
 757 void
 758 iterate_fix_dominators (dom, bbs, n)
 759      dominance_info dom;
 760      basic_block *bbs;
 761      int n;
 762 {
 763   int i, changed = 1;
 764   basic_block old_dom, new_dom;
 765
 766   while (changed)
 767     {
 768       changed = 0;
 769       for (i = 0; i < n; i++)
 770         {
 771           old_dom = get_immediate_dominator (dom, bbs[i]);
 772           new_dom = recount_dominator (dom, bbs[i]);
 773           if (old_dom != new_dom)
 774             {
 775               changed = 1;
 776               set_immediate_dominator (dom, bbs[i], new_dom);
 777             }
 778         }
 779     }
 780 }
 781
 782 void
 783 add_to_dominance_info (dom, bb)
 784      dominance_info dom;
 785      basic_block bb;
 786 {
 787   VARRAY_GROW (dom->varray, last_basic_block + 3);
 788 #ifdef ENABLE_CHECKING
 789   if (BB_NODE (dom, bb))
 790     abort ();
 791 #endif
 792   SET_BB_NODE (dom, bb, et_forest_add_node (dom->forest, bb));
 793 }
 794
 795 void
 796 delete_from_dominance_info (dom, bb)
 797      dominance_info dom;
 798      basic_block bb;
 799 {
 800   et_forest_remove_node (dom->forest, BB_NODE (dom, bb));
 801   SET_BB_NODE (dom, bb, NULL);
 802 }
 803
 804 void
 805 debug_dominance_info (dom)
 806   dominance_info dom;
 807 {
 808   basic_block bb, bb2;
 809   FOR_EACH_BB (bb)
 810     if ((bb2 = get_immediate_dominator (dom, bb)))
 811       fprintf (stderr, "%i %i\n", bb->index, bb2->index);
 812 }