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