gcc/dominance.c

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