gcc/dominance.c

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