gcc/dominance.c

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