gcc/dominance.c

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