gcc/dominance.c

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