gcc/dominance.c

   1 /* Calculate (post)dominators in slightly super-linear time.
   2    Copyright (C) 2000 Free Software Foundation, Inc.
   3    Contributed by Michael Matz (matz@ifh.de).
   4
   5    This file is part of GNU CC.
   6
   7    GNU CC is free software; you can redistribute it and/or modify
   8    it 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    GNU CC is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with GNU CC; see the file COPYING.  If not, write to
  19    the Free Software Foundation, 59 Temple Place - Suite 330,
  20    Boston, MA 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 implicitely 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 "rtl.h"
  39 #include "hard-reg-set.h"
  40 #include "basic-block.h"
  41
  42
  43 /* We name our nodes with integers, beginning with 1.  Zero is reserved for
  44    'undefined' or 'end of list'.  The name of each node is given by the dfs
  45    number of the corresponding basic block.  Please note, that we include the
  46    artificial ENTRY_BLOCK (or EXIT_BLOCK in the post-dom case) in our lists to
  47    support multiple entry points.  As it has no real basic block index we use
  48    'n_basic_blocks' for that.  Its dfs number is of course 1.  */
  49
  50 /* Type of Basic Block aka. TBB */
  51 typedef unsigned int TBB;
  52
  53 /* We work in a poor-mans object oriented fashion, and carry an instance of
  54    this structure through all our 'methods'.  It holds various arrays
  55    reflecting the (sub)structure of the flowgraph.  Most of them are of type
  56    TBB and are also indexed by TBB.  */
  57
  58 struct dom_info
  59 {
  60   /* The parent of a node in the DFS tree.  */
  61   TBB *dfs_parent;
  62   /* For a node x key[x] is roughly the node nearest to the root from which
  63      exists a way to x only over nodes behind x.  Such a node is also called
  64      semidominator.  */
  65   TBB *key;
  66   /* The value in path_min[x] is the node y on the path from x to the root of
  67      the tree x is in with the smallest key[y].  */
  68   TBB *path_min;
  69   /* bucket[x] points to the first node of the set of nodes having x as key.  */
  70   TBB *bucket;
  71   /* And next_bucket[x] points to the next node.  */
  72   TBB *next_bucket;
  73   /* After the algorithm is done, dom[x] contains the immediate dominator
  74      of x.  */
  75   TBB *dom;
  76
  77   /* The following few fields implement the structures needed for disjoint
  78      sets.  */
  79   /* set_chain[x] is the next node on the path from x to the representant
  80      of the set containing x.  If set_chain[x]==0 then x is a root.  */
  81   TBB *set_chain;
  82   /* set_size[x] is the number of elements in the set named by x.  */
  83   unsigned int *set_size;
  84   /* set_child[x] is used for balancing the tree representing a set.  It can
  85      be understood as the next sibling of x.  */
  86   TBB *set_child;
  87
  88   /* If b is the number of a basic block (BB->index), dfs_order[b] is the
  89      number of that node in DFS order counted from 1.  This is an index
  90      into most of the other arrays in this structure.  */
  91   TBB *dfs_order;
  92   /* If x is the DFS-index of a node which correspondends with an basic block,
  93      dfs_to_bb[x] is that basic block.  Note, that in our structure there are
  94      more nodes that basic blocks, so only dfs_to_bb[dfs_order[bb->index]]==bb
  95      is true for every basic block bb, but not the opposite.  */
  96   basic_block *dfs_to_bb;
  97
  98   /* This is the next free DFS number when creating the DFS tree or forest. */
  99   unsigned int dfsnum;
 100   /* The number of nodes in the DFS tree (==dfsnum-1).  */
 101   unsigned int nodes;
 102 };
 103
 104 static void init_dom_info               PARAMS ((struct dom_info *));
 105 static void free_dom_info               PARAMS ((struct dom_info *));
 106 static void calc_dfs_tree_nonrec        PARAMS ((struct dom_info *,
 107                                                  basic_block,
 108                                                  enum cdi_direction));
 109 static void calc_dfs_tree               PARAMS ((struct dom_info *,
 110                                                  enum cdi_direction));
 111 static void compress                    PARAMS ((struct dom_info *, TBB));
 112 static TBB eval                         PARAMS ((struct dom_info *, TBB));
 113 static void link_roots                  PARAMS ((struct dom_info *, TBB, TBB));
 114 static void calc_idoms                  PARAMS ((struct dom_info *,
 115                                                  enum cdi_direction));
 116 static void idoms_to_doms               PARAMS ((struct dom_info *,
 117                                                  sbitmap *));
 118
 119 /* Helper macro for allocating and initializing an array,
 120    for aesthetic reasons.  */
 121 #define init_ar(var, type, num, content)                        \
 122   do {                                                          \
 123     unsigned int i = 1;    /* Catch content == i.  */           \
 124     if (! (content))                                            \
 125       (var) = (type *) xcalloc ((num), sizeof (type));          \
 126     else                                                        \
 127       {                                                         \
 128         (var) = (type *) xmalloc ((num) * sizeof (type));       \
 129         for (i = 0; i < num; i++)                               \
 130           (var)[i] = (content);                                 \
 131       }                                                         \
 132   } while (0)
 133
 134 /* Allocate all needed memory in a pessimistic fashion (so we round up).
 135    This initialises the contents of DI, which already must be allocated.  */
 136
 137 static void
 138 init_dom_info (di)
 139      struct dom_info *di;
 140 {
 141   /* We need memory for n_basic_blocks nodes and the ENTRY_BLOCK or
 142      EXIT_BLOCK.  */
 143   unsigned int num = n_basic_blocks + 1 + 1;
 144   init_ar (di->dfs_parent, TBB, num, 0);
 145   init_ar (di->path_min, TBB, num, i);
 146   init_ar (di->key, TBB, num, i);
 147   init_ar (di->dom, TBB, num, 0);
 148
 149   init_ar (di->bucket, TBB, num, 0);
 150   init_ar (di->next_bucket, TBB, num, 0);
 151
 152   init_ar (di->set_chain, TBB, num, 0);
 153   init_ar (di->set_size, unsigned int, num, 1);
 154   init_ar (di->set_child, TBB, num, 0);
 155
 156   init_ar (di->dfs_order, TBB, (unsigned int) n_basic_blocks + 1, 0);
 157   init_ar (di->dfs_to_bb, basic_block, num, 0);
 158
 159   di->dfsnum = 1;
 160   di->nodes = 0;
 161 }
 162
 163 #undef init_ar
 164
 165 /* Free all allocated memory in DI, but not DI itself.  */
 166
 167 static void
 168 free_dom_info (di)
 169      struct dom_info *di;
 170 {
 171   free (di->dfs_parent);
 172   free (di->path_min);
 173   free (di->key);
 174   free (di->dom);
 175   free (di->bucket);
 176   free (di->next_bucket);
 177   free (di->set_chain);
 178   free (di->set_size);
 179   free (di->set_child);
 180   free (di->dfs_order);
 181   free (di->dfs_to_bb);
 182 }
 183
 184 /* The nonrecursive variant of creating a DFS tree.  DI is our working
 185    structure, BB the starting basic block for this tree and REVERSE
 186    is true, if predecessors should be visited instead of successors of a
 187    node.  After this is done all nodes reachable from BB were visited, have
 188    assigned their dfs number and are linked together to form a tree.  */
 189
 190 static void
 191 calc_dfs_tree_nonrec (di, bb, reverse)
 192      struct dom_info *di;
 193      basic_block bb;
 194      enum cdi_direction reverse;
 195 {
 196   /* We never call this with bb==EXIT_BLOCK_PTR (ENTRY_BLOCK_PTR if REVERSE). */
 197   /* We call this _only_ if bb is not already visited.  */
 198   edge e;
 199   TBB child_i, my_i = 0;
 200   edge *stack;
 201   int sp;
 202   /* Start block (ENTRY_BLOCK_PTR for forward problem, EXIT_BLOCK for backward
 203      problem).  */
 204   basic_block en_block;
 205   /* Ending block.  */
 206   basic_block ex_block;
 207
 208   stack = (edge *) xmalloc ((n_basic_blocks + 3) * sizeof (edge));
 209   sp = 0;
 210
 211   /* Initialize our border blocks, and the first edge.  */
 212   if (reverse)
 213     {
 214       e = bb->pred;
 215       en_block = EXIT_BLOCK_PTR;
 216       ex_block = ENTRY_BLOCK_PTR;
 217     }
 218   else
 219     {
 220       e = bb->succ;
 221       en_block = ENTRY_BLOCK_PTR;
 222       ex_block = EXIT_BLOCK_PTR;
 223     }
 224
 225   /* When the stack is empty we break out of this loop.  */
 226   while (1)
 227     {
 228       basic_block bn;
 229
 230       /* This loop traverses edges e in depth first manner, and fills the
 231          stack.  */
 232       while (e)
 233         {
 234           edge e_next;
 235
 236           /* Deduce from E the current and the next block (BB and BN), and the
 237              next edge.  */
 238           if (reverse)
 239             {
 240               bn = e->src;
 241
 242               /* If the next node BN is either already visited or a border
 243                  block the current edge is useless, and simply overwritten
 244                  with the next edge out of the current node.  */
 245               if (di->dfs_order[bn->index] || bn == ex_block)
 246                 {
 247                   e = e->pred_next;
 248                   continue;
 249                 }
 250               bb = e->dest;
 251               e_next = bn->pred;
 252             }
 253           else
 254             {
 255               bn = e->dest;
 256               if (di->dfs_order[bn->index] || bn == ex_block)
 257                 {
 258                   e = e->succ_next;
 259                   continue;
 260                 }
 261               bb = e->src;
 262               e_next = bn->succ;
 263             }
 264
 265           if (bn == en_block)
 266             abort ();
 267
 268           /* Fill the DFS tree info calculatable _before_ recursing.  */
 269           if (bb != en_block)
 270             my_i = di->dfs_order[bb->index];
 271           else
 272             my_i = di->dfs_order[n_basic_blocks];
 273           child_i = di->dfs_order[bn->index] = di->dfsnum++;
 274           di->dfs_to_bb[child_i] = bn;
 275           di->dfs_parent[child_i] = my_i;
 276
 277           /* Save the current point in the CFG on the stack, and recurse.  */
 278           stack[sp++] = e;
 279           e = e_next;
 280         }
 281
 282       if (!sp)
 283         break;
 284       e = stack[--sp];
 285
 286       /* OK.  The edge-list was exhausted, meaning normally we would
 287          end the recursion.  After returning from the recursive call,
 288          there were (may be) other statements which were run after a
 289          child node was completely considered by DFS.  Here is the
 290          point to do it in the non-recursive variant.
 291          E.g. The block just completed is in e->dest for forward DFS,
 292          the block not yet completed (the parent of the one above)
 293          in e->src.  This could be used e.g. for computing the number of
 294          descendants or the tree depth.  */
 295       if (reverse)
 296         e = e->pred_next;
 297       else
 298         e = e->succ_next;
 299     }
 300   free (stack);
 301 }
 302
 303 /* The main entry for calculating the DFS tree or forest.  DI is our working
 304    structure and REVERSE is true, if we are interested in the reverse flow
 305    graph.  In that case the result is not necessarily a tree but a forest,
 306    because there may be nodes from which the EXIT_BLOCK is unreachable.  */
 307
 308 static void
 309 calc_dfs_tree (di, reverse)
 310      struct dom_info *di;
 311      enum cdi_direction reverse;
 312 {
 313   /* The first block is the ENTRY_BLOCK (or EXIT_BLOCK if REVERSE).  */
 314   basic_block begin = reverse ? EXIT_BLOCK_PTR : ENTRY_BLOCK_PTR;
 315   di->dfs_order[n_basic_blocks] = di->dfsnum;
 316   di->dfs_to_bb[di->dfsnum] = begin;
 317   di->dfsnum++;
 318
 319   calc_dfs_tree_nonrec (di, begin, reverse);
 320
 321   if (reverse)
 322     {
 323       /* In the post-dom case we may have nodes without a path to EXIT_BLOCK.
 324          They are reverse-unreachable.  In the dom-case we disallow such
 325          nodes, but in post-dom we have to deal with them, so we simply
 326          include them in the DFS tree which actually becomes a forest.  */
 327       int i;
 328       for (i = n_basic_blocks - 1; i >= 0; i--)
 329         {
 330           basic_block b = BASIC_BLOCK (i);
 331           if (di->dfs_order[b->index])
 332             continue;
 333           di->dfs_order[b->index] = di->dfsnum;
 334           di->dfs_to_bb[di->dfsnum] = b;
 335           di->dfsnum++;
 336           calc_dfs_tree_nonrec (di, b, reverse);
 337         }
 338     }
 339
 340   di->nodes = di->dfsnum - 1;
 341
 342   /* This aborts e.g. when there is _no_ path from ENTRY to EXIT at all.  */
 343   if (di->nodes != (unsigned int) n_basic_blocks + 1)
 344     abort ();
 345 }
 346
 347 /* Compress the path from V to the root of its set and update path_min at the
 348    same time.  After compress(di, V) set_chain[V] is the root of the set V is
 349    in and path_min[V] is the node with the smallest key[] value on the path
 350    from V to that root.  */
 351
 352 static void
 353 compress (di, v)
 354      struct dom_info *di;
 355      TBB v;
 356 {
 357   /* Btw. It's not worth to unrecurse compress() as the depth is usually not
 358      greater than 5 even for huge graphs (I've not seen call depth > 4).
 359      Also performance wise compress() ranges _far_ behind eval().  */
 360   TBB parent = di->set_chain[v];
 361   if (di->set_chain[parent])
 362     {
 363       compress (di, parent);
 364       if (di->key[di->path_min[parent]] < di->key[di->path_min[v]])
 365         di->path_min[v] = di->path_min[parent];
 366       di->set_chain[v] = di->set_chain[parent];
 367     }
 368 }
 369
 370 /* Compress the path from V to the set root of V if needed (when the root has
 371    changed since the last call).  Returns the node with the smallest key[]
 372    value on the path from V to the root.  */
 373
 374 static inline TBB
 375 eval (di, v)
 376      struct dom_info *di;
 377      TBB v;
 378 {
 379   /* The representant of the set V is in, also called root (as the set
 380      representation is a tree).  */
 381   TBB rep = di->set_chain[v];
 382
 383   /* V itself is the root.  */
 384   if (!rep)
 385     return di->path_min[v];
 386
 387   /* Compress only if necessary.  */
 388   if (di->set_chain[rep])
 389     {
 390       compress (di, v);
 391       rep = di->set_chain[v];
 392     }
 393
 394   if (di->key[di->path_min[rep]] >= di->key[di->path_min[v]])
 395     return di->path_min[v];
 396   else
 397     return di->path_min[rep];
 398 }
 399
 400 /* This essentially merges the two sets of V and W, giving a single set with
 401    the new root V.  The internal representation of these disjoint sets is a
 402    balanced tree.  Currently link(V,W) is only used with V being the parent
 403    of W.  */
 404
 405 static void
 406 link_roots (di, v, w)
 407      struct dom_info *di;
 408      TBB v, w;
 409 {
 410   TBB s = w;
 411
 412   /* Rebalance the tree.  */
 413   while (di->key[di->path_min[w]] < di->key[di->path_min[di->set_child[s]]])
 414     {
 415       if (di->set_size[s] + di->set_size[di->set_child[di->set_child[s]]]
 416           >= 2 * di->set_size[di->set_child[s]])
 417         {
 418           di->set_chain[di->set_child[s]] = s;
 419           di->set_child[s] = di->set_child[di->set_child[s]];
 420         }
 421       else
 422         {
 423           di->set_size[di->set_child[s]] = di->set_size[s];
 424           s = di->set_chain[s] = di->set_child[s];
 425         }
 426     }
 427
 428   di->path_min[s] = di->path_min[w];
 429   di->set_size[v] += di->set_size[w];
 430   if (di->set_size[v] < 2 * di->set_size[w])
 431     {
 432       TBB tmp = s;
 433       s = di->set_child[v];
 434       di->set_child[v] = tmp;
 435     }
 436
 437   /* Merge all subtrees.  */
 438   while (s)
 439     {
 440       di->set_chain[s] = v;
 441       s = di->set_child[s];
 442     }
 443 }
 444
 445 /* This calculates the immediate dominators (or post-dominators if REVERSE is
 446    true).  DI is our working structure and should hold the DFS forest.
 447    On return the immediate dominator to node V is in di->dom[V].  */
 448
 449 static void
 450 calc_idoms (di, reverse)
 451      struct dom_info *di;
 452      enum cdi_direction reverse;
 453 {
 454   TBB v, w, k, par;
 455   basic_block en_block;
 456   if (reverse)
 457     en_block = EXIT_BLOCK_PTR;
 458   else
 459     en_block = ENTRY_BLOCK_PTR;
 460
 461   /* Go backwards in DFS order, to first look at the leafs.  */
 462   v = di->nodes;
 463   while (v > 1)
 464     {
 465       basic_block bb = di->dfs_to_bb[v];
 466       edge e, e_next;
 467
 468       par = di->dfs_parent[v];
 469       k = v;
 470       if (reverse)
 471         e = bb->succ;
 472       else
 473         e = bb->pred;
 474
 475       /* Search all direct predecessors for the smallest node with a path
 476          to them.  That way we have the smallest node with also a path to
 477          us only over nodes behind us.  In effect we search for our
 478          semidominator.  */
 479       for (; e; e = e_next)
 480         {
 481           TBB k1;
 482           basic_block b;
 483
 484           if (reverse)
 485             {
 486               b = e->dest;
 487               e_next = e->succ_next;
 488             }
 489           else
 490             {
 491               b = e->src;
 492               e_next = e->pred_next;
 493             }
 494           if (b == en_block)
 495             k1 = di->dfs_order[n_basic_blocks];
 496           else
 497             k1 = di->dfs_order[b->index];
 498
 499           /* Call eval() only if really needed.  If k1 is above V in DFS tree,
 500              then we know, that eval(k1) == k1 and key[k1] == k1.  */
 501           if (k1 > v)
 502             k1 = di->key[eval (di, k1)];
 503           if (k1 < k)
 504             k = k1;
 505         }
 506
 507       di->key[v] = k;
 508       link_roots (di, par, v);
 509       di->next_bucket[v] = di->bucket[k];
 510       di->bucket[k] = v;
 511
 512       /* Transform semidominators into dominators.  */
 513       for (w = di->bucket[par]; w; w = di->next_bucket[w])
 514         {
 515           k = eval (di, w);
 516           if (di->key[k] < di->key[w])
 517             di->dom[w] = k;
 518           else
 519             di->dom[w] = par;
 520         }
 521       /* We don't need to cleanup next_bucket[].  */
 522       di->bucket[par] = 0;
 523       v--;
 524     }
 525
 526   /* Explicitely define the dominators.  */
 527   di->dom[1] = 0;
 528   for (v = 2; v <= di->nodes; v++)
 529     if (di->dom[v] != di->key[v])
 530       di->dom[v] = di->dom[di->dom[v]];
 531 }
 532
 533 /* Convert the information about immediate dominators (in DI) to sets of all
 534    dominators (in DOMINATORS).  */
 535
 536 static void
 537 idoms_to_doms (di, dominators)
 538      struct dom_info *di;
 539      sbitmap *dominators;
 540 {
 541   TBB i, e_index;
 542   int bb, bb_idom;
 543   sbitmap_vector_zero (dominators, n_basic_blocks);
 544   /* We have to be careful, to not include the ENTRY_BLOCK or EXIT_BLOCK
 545      in the list of (post)-doms, so remember that in e_index.  */
 546   e_index = di->dfs_order[n_basic_blocks];
 547
 548   for (i = 1; i <= di->nodes; i++)
 549     {
 550       if (i == e_index)
 551         continue;
 552       bb = di->dfs_to_bb[i]->index;
 553
 554       if (di->dom[i] && (di->dom[i] != e_index))
 555         {
 556           bb_idom = di->dfs_to_bb[di->dom[i]]->index;
 557           sbitmap_copy (dominators[bb], dominators[bb_idom]);
 558         }
 559       else
 560         {
 561           /* It has no immediate dom or only ENTRY_BLOCK or EXIT_BLOCK.
 562              If it is a child of ENTRY_BLOCK that's OK, and it's only
 563              dominated by itself; if it's _not_ a child of ENTRY_BLOCK, it
 564              means, it is unreachable.  That case has been disallowed in the
 565              building of the DFS tree, so we are save here.  For the reverse
 566              flow graph it means, it has no children, so, to be compatible
 567              with the old code, we set the post_dominators to all one.  */
 568           if (!di->dom[i])
 569             {
 570               sbitmap_ones (dominators[bb]);
 571             }
 572         }
 573       SET_BIT (dominators[bb], bb);
 574     }
 575 }
 576
 577 /* The main entry point into this module.  IDOM is an integer array with room
 578    for n_basic_blocks integers, DOMS is a preallocated sbitmap array having
 579    room for n_basic_blocks^2 bits, and POST is true if the caller wants to
 580    know post-dominators.
 581
 582    On return IDOM[i] will be the BB->index of the immediate (post) dominator
 583    of basic block i, and DOMS[i] will have set bit j if basic block j is a
 584    (post)dominator for block i.
 585
 586    Either IDOM or DOMS may be NULL (meaning the caller is not interested in
 587    immediate resp. all dominators).  */
 588
 589 void
 590 calculate_dominance_info (idom, doms, reverse)
 591      int *idom;
 592      sbitmap *doms;
 593      enum cdi_direction reverse;
 594 {
 595   struct dom_info di;
 596
 597   if (!doms && !idom)
 598     return;
 599   init_dom_info (&di);
 600   calc_dfs_tree (&di, reverse);
 601   calc_idoms (&di, reverse);
 602
 603   if (idom)
 604     {
 605       int i;
 606       for (i = 0; i < n_basic_blocks; i++)
 607         {
 608           basic_block b = BASIC_BLOCK (i);
 609           TBB d = di.dom[di.dfs_order[b->index]];
 610
 611           /* The old code didn't modify array elements of nodes having only
 612              itself as dominator (d==0) or only ENTRY_BLOCK (resp. EXIT_BLOCK)
 613              (d==1).  */
 614           if (d > 1)
 615             idom[i] = di.dfs_to_bb[d]->index;
 616         }
 617     }
 618   if (doms)
 619     idoms_to_doms (&di, doms);
 620
 621   free_dom_info (&di);
 622 }