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