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