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