245b2de1c2104eee1024f88fe766d493e6dc8f2b
1 /* Calculate (post)dominators in slightly super-linear time.
2    Copyright (C) 2000, 2003, 2004, 2005, 2006, 2007, 2008 Free
3    Software Foundation, Inc.
4    Contributed by Michael Matz (matz@ifh.de).
6    This file is part of GCC.
8    GCC is free software; you can redistribute it and/or modify it
9    under the terms of the GNU General Public License as published by
10    the Free Software Foundation; either version 3, or (at your option)
11    any later version.
13    GCC is distributed in the hope that it will be useful, but WITHOUT
14    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
15    or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
18    You should have received a copy of the GNU General Public License
19    along with GCC; see the file COPYING3.  If not see
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.
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.  */
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 #include "timevar.h"
47 #include "vecprim.h"
48 #include "pointer-set.h"
49 #include "graphds.h"
51 /* We name our nodes with integers, beginning with 1.  Zero is reserved for
52    'undefined' or 'end of list'.  The name of each node is given by the dfs
53    number of the corresponding basic block.  Please note, that we include the
54    artificial ENTRY_BLOCK (or EXIT_BLOCK in the post-dom case) in our lists to
55    support multiple entry points.  Its dfs number is of course 1.  */
57 /* Type of Basic Block aka. TBB */
58 typedef unsigned int TBB;
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.  */
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;
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 representative
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;
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;
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;
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 };
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, bool);
118 static void calc_dfs_tree (struct dom_info *, bool);
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 *, bool);
123 void debug_dominance_info (enum cdi_direction);
124 void debug_dominance_tree (enum cdi_direction, basic_block);
126 /* Helper macro for allocating and initializing an array,
127    for aesthetic reasons.  */
128 #define init_ar(var, type, num, content)                        \
129   do                                                            \
130     {                                                           \
131       unsigned int i = 1;    /* Catch content == i.  */         \
132       if (! (content))                                          \
133         (var) = XCNEWVEC (type, num);                           \
134       else                                                      \
135         {                                                       \
136           (var) = XNEWVEC (type, (num));                        \
137           for (i = 0; i < num; i++)                             \
138             (var)[i] = (content);                               \
139         }                                                       \
140     }                                                           \
141   while (0)
143 /* Allocate all needed memory in a pessimistic fashion (so we round up).
144    This initializes the contents of DI, which already must be allocated.  */
146 static void
147 init_dom_info (struct dom_info *di, enum cdi_direction dir)
148 {
149   /* We need memory for n_basic_blocks nodes.  */
150   unsigned int num = n_basic_blocks;
151   init_ar (di->dfs_parent, TBB, num, 0);
152   init_ar (di->path_min, TBB, num, i);
153   init_ar (di->key, TBB, num, i);
154   init_ar (di->dom, TBB, num, 0);
156   init_ar (di->bucket, TBB, num, 0);
157   init_ar (di->next_bucket, TBB, num, 0);
159   init_ar (di->set_chain, TBB, num, 0);
160   init_ar (di->set_size, unsigned int, num, 1);
161   init_ar (di->set_child, TBB, num, 0);
163   init_ar (di->dfs_order, TBB, (unsigned int) last_basic_block + 1, 0);
164   init_ar (di->dfs_to_bb, basic_block, num, 0);
166   di->dfsnum = 1;
167   di->nodes = 0;
169   switch (dir)
170     {
171       case CDI_DOMINATORS:
172         di->fake_exit_edge = NULL;
173         break;
174       case CDI_POST_DOMINATORS:
175         di->fake_exit_edge = BITMAP_ALLOC (NULL);
176         break;
177       default:
178         gcc_unreachable ();
179         break;
180     }
181 }
183 #undef init_ar
185 /* Map dominance calculation type to array index used for various
186    dominance information arrays.  This version is simple -- it will need
188    cdi_direction.  */
190 static unsigned int
191 dom_convert_dir_to_idx (enum cdi_direction dir)
192 {
193   gcc_assert (dir == CDI_DOMINATORS || dir == CDI_POST_DOMINATORS);
194   return dir - 1;
195 }
197 /* Free all allocated memory in DI, but not DI itself.  */
199 static void
200 free_dom_info (struct dom_info *di)
201 {
202   free (di->dfs_parent);
203   free (di->path_min);
204   free (di->key);
205   free (di->dom);
206   free (di->bucket);
207   free (di->next_bucket);
208   free (di->set_chain);
209   free (di->set_size);
210   free (di->set_child);
211   free (di->dfs_order);
212   free (di->dfs_to_bb);
213   BITMAP_FREE (di->fake_exit_edge);
214 }
216 /* The nonrecursive variant of creating a DFS tree.  DI is our working
217    structure, BB the starting basic block for this tree and REVERSE
218    is true, if predecessors should be visited instead of successors of a
219    node.  After this is done all nodes reachable from BB were visited, have
220    assigned their dfs number and are linked together to form a tree.  */
222 static void
223 calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb, bool reverse)
224 {
225   /* We call this _only_ if bb is not already visited.  */
226   edge e;
227   TBB child_i, my_i = 0;
228   edge_iterator *stack;
229   edge_iterator ei, einext;
230   int sp;
231   /* Start block (ENTRY_BLOCK_PTR for forward problem, EXIT_BLOCK for backward
232      problem).  */
233   basic_block en_block;
234   /* Ending block.  */
235   basic_block ex_block;
237   stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
238   sp = 0;
240   /* Initialize our border blocks, and the first edge.  */
241   if (reverse)
242     {
243       ei = ei_start (bb->preds);
244       en_block = EXIT_BLOCK_PTR;
245       ex_block = ENTRY_BLOCK_PTR;
246     }
247   else
248     {
249       ei = ei_start (bb->succs);
250       en_block = ENTRY_BLOCK_PTR;
251       ex_block = EXIT_BLOCK_PTR;
252     }
254   /* When the stack is empty we break out of this loop.  */
255   while (1)
256     {
257       basic_block bn;
259       /* This loop traverses edges e in depth first manner, and fills the
260          stack.  */
261       while (!ei_end_p (ei))
262         {
263           e = ei_edge (ei);
265           /* Deduce from E the current and the next block (BB and BN), and the
266              next edge.  */
267           if (reverse)
268             {
269               bn = e->src;
271               /* If the next node BN is either already visited or a border
272                  block the current edge is useless, and simply overwritten
273                  with the next edge out of the current node.  */
274               if (bn == ex_block || di->dfs_order[bn->index])
275                 {
276                   ei_next (&ei);
277                   continue;
278                 }
279               bb = e->dest;
280               einext = ei_start (bn->preds);
281             }
282           else
283             {
284               bn = e->dest;
285               if (bn == ex_block || di->dfs_order[bn->index])
286                 {
287                   ei_next (&ei);
288                   continue;
289                 }
290               bb = e->src;
291               einext = ei_start (bn->succs);
292             }
294           gcc_assert (bn != en_block);
296           /* Fill the DFS tree info calculatable _before_ recursing.  */
297           if (bb != en_block)
298             my_i = di->dfs_order[bb->index];
299           else
300             my_i = di->dfs_order[last_basic_block];
301           child_i = di->dfs_order[bn->index] = di->dfsnum++;
302           di->dfs_to_bb[child_i] = bn;
303           di->dfs_parent[child_i] = my_i;
305           /* Save the current point in the CFG on the stack, and recurse.  */
306           stack[sp++] = ei;
307           ei = einext;
308         }
310       if (!sp)
311         break;
312       ei = stack[--sp];
314       /* OK.  The edge-list was exhausted, meaning normally we would
315          end the recursion.  After returning from the recursive call,
316          there were (may be) other statements which were run after a
317          child node was completely considered by DFS.  Here is the
318          point to do it in the non-recursive variant.
319          E.g. The block just completed is in e->dest for forward DFS,
320          the block not yet completed (the parent of the one above)
321          in e->src.  This could be used e.g. for computing the number of
322          descendants or the tree depth.  */
323       ei_next (&ei);
324     }
325   free (stack);
326 }
328 /* The main entry for calculating the DFS tree or forest.  DI is our working
329    structure and REVERSE is true, if we are interested in the reverse flow
330    graph.  In that case the result is not necessarily a tree but a forest,
331    because there may be nodes from which the EXIT_BLOCK is unreachable.  */
333 static void
334 calc_dfs_tree (struct dom_info *di, bool reverse)
335 {
336   /* The first block is the ENTRY_BLOCK (or EXIT_BLOCK if REVERSE).  */
337   basic_block begin = reverse ? EXIT_BLOCK_PTR : ENTRY_BLOCK_PTR;
338   di->dfs_order[last_basic_block] = di->dfsnum;
339   di->dfs_to_bb[di->dfsnum] = begin;
340   di->dfsnum++;
342   calc_dfs_tree_nonrec (di, begin, reverse);
344   if (reverse)
345     {
346       /* In the post-dom case we may have nodes without a path to EXIT_BLOCK.
347          They are reverse-unreachable.  In the dom-case we disallow such
348          nodes, but in post-dom we have to deal with them.
350          There are two situations in which this occurs.  First, noreturn
351          functions.  Second, infinite loops.  In the first case we need to
352          pretend that there is an edge to the exit block.  In the second
353          case, we wind up with a forest.  We need to process all noreturn
354          blocks before we know if we've got any infinite loops.  */
356       basic_block b;
357       bool saw_unconnected = false;
359       FOR_EACH_BB_REVERSE (b)
360         {
361           if (EDGE_COUNT (b->succs) > 0)
362             {
363               if (di->dfs_order[b->index] == 0)
364                 saw_unconnected = true;
365               continue;
366             }
367           bitmap_set_bit (di->fake_exit_edge, b->index);
368           di->dfs_order[b->index] = di->dfsnum;
369           di->dfs_to_bb[di->dfsnum] = b;
370           di->dfs_parent[di->dfsnum] = di->dfs_order[last_basic_block];
371           di->dfsnum++;
372           calc_dfs_tree_nonrec (di, b, reverse);
373         }
375       if (saw_unconnected)
376         {
377           FOR_EACH_BB_REVERSE (b)
378             {
379               if (di->dfs_order[b->index])
380                 continue;
381               bitmap_set_bit (di->fake_exit_edge, b->index);
382               di->dfs_order[b->index] = di->dfsnum;
383               di->dfs_to_bb[di->dfsnum] = b;
384               di->dfs_parent[di->dfsnum] = di->dfs_order[last_basic_block];
385               di->dfsnum++;
386               calc_dfs_tree_nonrec (di, b, reverse);
387             }
388         }
389     }
391   di->nodes = di->dfsnum - 1;
393   /* This aborts e.g. when there is _no_ path from ENTRY to EXIT at all.  */
394   gcc_assert (di->nodes == (unsigned int) n_basic_blocks - 1);
395 }
397 /* Compress the path from V to the root of its set and update path_min at the
398    same time.  After compress(di, V) set_chain[V] is the root of the set V is
399    in and path_min[V] is the node with the smallest key[] value on the path
400    from V to that root.  */
402 static void
403 compress (struct dom_info *di, TBB v)
404 {
405   /* Btw. It's not worth to unrecurse compress() as the depth is usually not
406      greater than 5 even for huge graphs (I've not seen call depth > 4).
407      Also performance wise compress() ranges _far_ behind eval().  */
408   TBB parent = di->set_chain[v];
409   if (di->set_chain[parent])
410     {
411       compress (di, parent);
412       if (di->key[di->path_min[parent]] < di->key[di->path_min[v]])
413         di->path_min[v] = di->path_min[parent];
414       di->set_chain[v] = di->set_chain[parent];
415     }
416 }
418 /* Compress the path from V to the set root of V if needed (when the root has
419    changed since the last call).  Returns the node with the smallest key[]
420    value on the path from V to the root.  */
422 static inline TBB
423 eval (struct dom_info *di, TBB v)
424 {
425   /* The representative of the set V is in, also called root (as the set
426      representation is a tree).  */
427   TBB rep = di->set_chain[v];
429   /* V itself is the root.  */
430   if (!rep)
431     return di->path_min[v];
433   /* Compress only if necessary.  */
434   if (di->set_chain[rep])
435     {
436       compress (di, v);
437       rep = di->set_chain[v];
438     }
440   if (di->key[di->path_min[rep]] >= di->key[di->path_min[v]])
441     return di->path_min[v];
442   else
443     return di->path_min[rep];
444 }
446 /* This essentially merges the two sets of V and W, giving a single set with
447    the new root V.  The internal representation of these disjoint sets is a
448    balanced tree.  Currently link(V,W) is only used with V being the parent
449    of W.  */
451 static void
452 link_roots (struct dom_info *di, TBB v, TBB w)
453 {
454   TBB s = w;
456   /* Rebalance the tree.  */
457   while (di->key[di->path_min[w]] < di->key[di->path_min[di->set_child[s]]])
458     {
459       if (di->set_size[s] + di->set_size[di->set_child[di->set_child[s]]]
460           >= 2 * di->set_size[di->set_child[s]])
461         {
462           di->set_chain[di->set_child[s]] = s;
463           di->set_child[s] = di->set_child[di->set_child[s]];
464         }
465       else
466         {
467           di->set_size[di->set_child[s]] = di->set_size[s];
468           s = di->set_chain[s] = di->set_child[s];
469         }
470     }
472   di->path_min[s] = di->path_min[w];
473   di->set_size[v] += di->set_size[w];
474   if (di->set_size[v] < 2 * di->set_size[w])
475     {
476       TBB tmp = s;
477       s = di->set_child[v];
478       di->set_child[v] = tmp;
479     }
481   /* Merge all subtrees.  */
482   while (s)
483     {
484       di->set_chain[s] = v;
485       s = di->set_child[s];
486     }
487 }
489 /* This calculates the immediate dominators (or post-dominators if REVERSE is
490    true).  DI is our working structure and should hold the DFS forest.
491    On return the immediate dominator to node V is in di->dom[V].  */
493 static void
494 calc_idoms (struct dom_info *di, bool reverse)
495 {
496   TBB v, w, k, par;
497   basic_block en_block;
498   edge_iterator ei, einext;
500   if (reverse)
501     en_block = EXIT_BLOCK_PTR;
502   else
503     en_block = ENTRY_BLOCK_PTR;
505   /* Go backwards in DFS order, to first look at the leafs.  */
506   v = di->nodes;
507   while (v > 1)
508     {
509       basic_block bb = di->dfs_to_bb[v];
510       edge e;
512       par = di->dfs_parent[v];
513       k = v;
515       ei = (reverse) ? ei_start (bb->succs) : ei_start (bb->preds);
517       if (reverse)
518         {
519           /* If this block has a fake edge to exit, process that first.  */
520           if (bitmap_bit_p (di->fake_exit_edge, bb->index))
521             {
522               einext = ei;
523               einext.index = 0;
524               goto do_fake_exit_edge;
525             }
526         }
528       /* Search all direct predecessors for the smallest node with a path
529          to them.  That way we have the smallest node with also a path to
530          us only over nodes behind us.  In effect we search for our
531          semidominator.  */
532       while (!ei_end_p (ei))
533         {
534           TBB k1;
535           basic_block b;
537           e = ei_edge (ei);
538           b = (reverse) ? e->dest : e->src;
539           einext = ei;
540           ei_next (&einext);
542           if (b == en_block)
543             {
544             do_fake_exit_edge:
545               k1 = di->dfs_order[last_basic_block];
546             }
547           else
548             k1 = di->dfs_order[b->index];
550           /* Call eval() only if really needed.  If k1 is above V in DFS tree,
551              then we know, that eval(k1) == k1 and key[k1] == k1.  */
552           if (k1 > v)
553             k1 = di->key[eval (di, k1)];
554           if (k1 < k)
555             k = k1;
557           ei = einext;
558         }
560       di->key[v] = k;
562       di->next_bucket[v] = di->bucket[k];
563       di->bucket[k] = v;
565       /* Transform semidominators into dominators.  */
566       for (w = di->bucket[par]; w; w = di->next_bucket[w])
567         {
568           k = eval (di, w);
569           if (di->key[k] < di->key[w])
570             di->dom[w] = k;
571           else
572             di->dom[w] = par;
573         }
574       /* We don't need to cleanup next_bucket[].  */
575       di->bucket[par] = 0;
576       v--;
577     }
579   /* Explicitly define the dominators.  */
580   di->dom = 0;
581   for (v = 2; v <= di->nodes; v++)
582     if (di->dom[v] != di->key[v])
583       di->dom[v] = di->dom[di->dom[v]];
584 }
586 /* Assign dfs numbers starting from NUM to NODE and its sons.  */
588 static void
589 assign_dfs_numbers (struct et_node *node, int *num)
590 {
591   struct et_node *son;
593   node->dfs_num_in = (*num)++;
595   if (node->son)
596     {
597       assign_dfs_numbers (node->son, num);
598       for (son = node->son->right; son != node->son; son = son->right)
599         assign_dfs_numbers (son, num);
600     }
602   node->dfs_num_out = (*num)++;
603 }
605 /* Compute the data necessary for fast resolving of dominator queries in a
606    static dominator tree.  */
608 static void
609 compute_dom_fast_query (enum cdi_direction dir)
610 {
611   int num = 0;
612   basic_block bb;
613   unsigned int dir_index = dom_convert_dir_to_idx (dir);
615   gcc_assert (dom_info_available_p (dir));
617   if (dom_computed[dir_index] == DOM_OK)
618     return;
620   FOR_ALL_BB (bb)
621     {
622       if (!bb->dom[dir_index]->father)
623         assign_dfs_numbers (bb->dom[dir_index], &num);
624     }
626   dom_computed[dir_index] = DOM_OK;
627 }
629 /* The main entry point into this module.  DIR is set depending on whether
630    we want to compute dominators or postdominators.  */
632 void
633 calculate_dominance_info (enum cdi_direction dir)
634 {
635   struct dom_info di;
636   basic_block b;
637   unsigned int dir_index = dom_convert_dir_to_idx (dir);
638   bool reverse = (dir == CDI_POST_DOMINATORS) ? true : false;
640   if (dom_computed[dir_index] == DOM_OK)
641     return;
643   timevar_push (TV_DOMINANCE);
644   if (!dom_info_available_p (dir))
645     {
646       gcc_assert (!n_bbs_in_dom_tree[dir_index]);
648       FOR_ALL_BB (b)
649         {
650           b->dom[dir_index] = et_new_tree (b);
651         }
652       n_bbs_in_dom_tree[dir_index] = n_basic_blocks;
654       init_dom_info (&di, dir);
655       calc_dfs_tree (&di, reverse);
656       calc_idoms (&di, reverse);
658       FOR_EACH_BB (b)
659         {
660           TBB d = di.dom[di.dfs_order[b->index]];
662           if (di.dfs_to_bb[d])
663             et_set_father (b->dom[dir_index], di.dfs_to_bb[d]->dom[dir_index]);
664         }
666       free_dom_info (&di);
667       dom_computed[dir_index] = DOM_NO_FAST_QUERY;
668     }
670   compute_dom_fast_query (dir);
672   timevar_pop (TV_DOMINANCE);
673 }
675 /* Free dominance information for direction DIR.  */
676 void
677 free_dominance_info (enum cdi_direction dir)
678 {
679   basic_block bb;
680   unsigned int dir_index = dom_convert_dir_to_idx (dir);
682   if (!dom_info_available_p (dir))
683     return;
685   FOR_ALL_BB (bb)
686     {
687       et_free_tree_force (bb->dom[dir_index]);
688       bb->dom[dir_index] = NULL;
689     }
690   et_free_pools ();
692   n_bbs_in_dom_tree[dir_index] = 0;
694   dom_computed[dir_index] = DOM_NONE;
695 }
697 /* Return the immediate dominator of basic block BB.  */
698 basic_block
699 get_immediate_dominator (enum cdi_direction dir, basic_block bb)
700 {
701   unsigned int dir_index = dom_convert_dir_to_idx (dir);
702   struct et_node *node = bb->dom[dir_index];
704   gcc_assert (dom_computed[dir_index]);
706   if (!node->father)
707     return NULL;
709   return (basic_block) node->father->data;
710 }
712 /* Set the immediate dominator of the block possibly removing
713    existing edge.  NULL can be used to remove any edge.  */
714 void
715 set_immediate_dominator (enum cdi_direction dir, basic_block bb,
716                          basic_block dominated_by)
717 {
718   unsigned int dir_index = dom_convert_dir_to_idx (dir);
719   struct et_node *node = bb->dom[dir_index];
721   gcc_assert (dom_computed[dir_index]);
723   if (node->father)
724     {
725       if (node->father->data == dominated_by)
726         return;
727       et_split (node);
728     }
730   if (dominated_by)
731     et_set_father (node, dominated_by->dom[dir_index]);
733   if (dom_computed[dir_index] == DOM_OK)
734     dom_computed[dir_index] = DOM_NO_FAST_QUERY;
735 }
737 /* Returns the list of basic blocks immediately dominated by BB, in the
738    direction DIR.  */
739 VEC (basic_block, heap) *
740 get_dominated_by (enum cdi_direction dir, basic_block bb)
741 {
742   unsigned int dir_index = dom_convert_dir_to_idx (dir);
743   struct et_node *node = bb->dom[dir_index], *son = node->son, *ason;
744   VEC (basic_block, heap) *bbs = NULL;
746   gcc_assert (dom_computed[dir_index]);
748   if (!son)
749     return NULL;
751   VEC_safe_push (basic_block, heap, bbs, (basic_block) son->data);
752   for (ason = son->right; ason != son; ason = ason->right)
753     VEC_safe_push (basic_block, heap, bbs, (basic_block) ason->data);
755   return bbs;
756 }
758 /* Returns the list of basic blocks that are immediately dominated (in
759    direction DIR) by some block between N_REGION ones stored in REGION,
760    except for blocks in the REGION itself.  */
762 VEC (basic_block, heap) *
763 get_dominated_by_region (enum cdi_direction dir, basic_block *region,
764                          unsigned n_region)
765 {
766   unsigned i;
767   basic_block dom;
768   VEC (basic_block, heap) *doms = NULL;
770   for (i = 0; i < n_region; i++)
771     region[i]->flags |= BB_DUPLICATED;
772   for (i = 0; i < n_region; i++)
773     for (dom = first_dom_son (dir, region[i]);
774          dom;
775          dom = next_dom_son (dir, dom))
776       if (!(dom->flags & BB_DUPLICATED))
777         VEC_safe_push (basic_block, heap, doms, dom);
778   for (i = 0; i < n_region; i++)
779     region[i]->flags &= ~BB_DUPLICATED;
781   return doms;
782 }
784 /* Returns the list of basic blocks including BB dominated by BB, in the
785    direction DIR.  The vector will be sorted in preorder.  */
787 VEC (basic_block, heap) *
788 get_all_dominated_blocks (enum cdi_direction dir, basic_block bb)
789 {
790   VEC(basic_block, heap) *bbs = NULL;
791   unsigned i;
793   i = 0;
794   VEC_safe_push (basic_block, heap, bbs, bb);
796   do
797     {
798       basic_block son;
800       bb = VEC_index (basic_block, bbs, i++);
801       for (son = first_dom_son (dir, bb);
802            son;
803            son = next_dom_son (dir, son))
804         VEC_safe_push (basic_block, heap, bbs, son);
805     }
806   while (i < VEC_length (basic_block, bbs));
808   return bbs;
809 }
811 /* Redirect all edges pointing to BB to TO.  */
812 void
813 redirect_immediate_dominators (enum cdi_direction dir, basic_block bb,
814                                basic_block to)
815 {
816   unsigned int dir_index = dom_convert_dir_to_idx (dir);
817   struct et_node *bb_node, *to_node, *son;
819   bb_node = bb->dom[dir_index];
820   to_node = to->dom[dir_index];
822   gcc_assert (dom_computed[dir_index]);
824   if (!bb_node->son)
825     return;
827   while (bb_node->son)
828     {
829       son = bb_node->son;
831       et_split (son);
832       et_set_father (son, to_node);
833     }
835   if (dom_computed[dir_index] == DOM_OK)
836     dom_computed[dir_index] = DOM_NO_FAST_QUERY;
837 }
839 /* Find first basic block in the tree dominating both BB1 and BB2.  */
840 basic_block
841 nearest_common_dominator (enum cdi_direction dir, basic_block bb1, basic_block bb2)
842 {
843   unsigned int dir_index = dom_convert_dir_to_idx (dir);
845   gcc_assert (dom_computed[dir_index]);
847   if (!bb1)
848     return bb2;
849   if (!bb2)
850     return bb1;
852   return (basic_block) et_nca (bb1->dom[dir_index], bb2->dom[dir_index])->data;
853 }
856 /* Find the nearest common dominator for the basic blocks in BLOCKS,
857    using dominance direction DIR.  */
859 basic_block
860 nearest_common_dominator_for_set (enum cdi_direction dir, bitmap blocks)
861 {
862   unsigned i, first;
863   bitmap_iterator bi;
864   basic_block dom;
866   first = bitmap_first_set_bit (blocks);
867   dom = BASIC_BLOCK (first);
868   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
869     if (dom != BASIC_BLOCK (i))
870       dom = nearest_common_dominator (dir, dom, BASIC_BLOCK (i));
872   return dom;
873 }
875 /*  Given a dominator tree, we can determine whether one thing
876     dominates another in constant time by using two DFS numbers:
878     1. The number for when we visit a node on the way down the tree
879     2. The number for when we visit a node on the way back up the tree
881     You can view these as bounds for the range of dfs numbers the
882     nodes in the subtree of the dominator tree rooted at that node
883     will contain.
885     The dominator tree is always a simple acyclic tree, so there are
886     only three possible relations two nodes in the dominator tree have
887     to each other:
889     1. Node A is above Node B (and thus, Node A dominates node B)
891      A
892      |
893      C
894     / \
895    B   D
898    In the above case, DFS_Number_In of A will be <= DFS_Number_In of
899    B, and DFS_Number_Out of A will be >= DFS_Number_Out of B.  This is
900    because we must hit A in the dominator tree *before* B on the walk
901    down, and we will hit A *after* B on the walk back up
903    2. Node A is below node B (and thus, node B dominates node A)
906      B
907      |
908      A
909     / \
910    C   D
912    In the above case, DFS_Number_In of A will be >= DFS_Number_In of
913    B, and DFS_Number_Out of A will be <= DFS_Number_Out of B.
915    This is because we must hit A in the dominator tree *after* B on
916    the walk down, and we will hit A *before* B on the walk back up
918    3. Node A and B are siblings (and thus, neither dominates the other)
920      C
921      |
922      D
923     / \
924    A   B
926    In the above case, DFS_Number_In of A will *always* be <=
927    DFS_Number_In of B, and DFS_Number_Out of A will *always* be <=
928    DFS_Number_Out of B.  This is because we will always finish the dfs
929    walk of one of the subtrees before the other, and thus, the dfs
930    numbers for one subtree can't intersect with the range of dfs
931    numbers for the other subtree.  If you swap A and B's position in
932    the dominator tree, the comparison changes direction, but the point
933    is that both comparisons will always go the same way if there is no
934    dominance relationship.
936    Thus, it is sufficient to write
938    A_Dominates_B (node A, node B)
939    {
940      return DFS_Number_In(A) <= DFS_Number_In(B)
941             && DFS_Number_Out (A) >= DFS_Number_Out(B);
942    }
944    A_Dominated_by_B (node A, node B)
945    {
946      return DFS_Number_In(A) >= DFS_Number_In(A)
947             && DFS_Number_Out (A) <= DFS_Number_Out(B);
948    }  */
950 /* Return TRUE in case BB1 is dominated by BB2.  */
951 bool
952 dominated_by_p (enum cdi_direction dir, const_basic_block bb1, const_basic_block bb2)
953 {
954   unsigned int dir_index = dom_convert_dir_to_idx (dir);
955   struct et_node *n1 = bb1->dom[dir_index], *n2 = bb2->dom[dir_index];
957   gcc_assert (dom_computed[dir_index]);
959   if (dom_computed[dir_index] == DOM_OK)
960     return (n1->dfs_num_in >= n2->dfs_num_in
961             && n1->dfs_num_out <= n2->dfs_num_out);
963   return et_below (n1, n2);
964 }
966 /* Returns the entry dfs number for basic block BB, in the direction DIR.  */
968 unsigned
969 bb_dom_dfs_in (enum cdi_direction dir, basic_block bb)
970 {
971   unsigned int dir_index = dom_convert_dir_to_idx (dir);
972   struct et_node *n = bb->dom[dir_index];
974   gcc_assert (dom_computed[dir_index] == DOM_OK);
975   return n->dfs_num_in;
976 }
978 /* Returns the exit dfs number for basic block BB, in the direction DIR.  */
980 unsigned
981 bb_dom_dfs_out (enum cdi_direction dir, basic_block bb)
982 {
983   unsigned int dir_index = dom_convert_dir_to_idx (dir);
984   struct et_node *n = bb->dom[dir_index];
986   gcc_assert (dom_computed[dir_index] == DOM_OK);
987   return n->dfs_num_out;
988 }
990 /* Verify invariants of dominator structure.  */
991 void
992 verify_dominators (enum cdi_direction dir)
993 {
994   int err = 0;
995   basic_block bb, imm_bb, imm_bb_correct;
996   struct dom_info di;
997   bool reverse = (dir == CDI_POST_DOMINATORS) ? true : false;
999   gcc_assert (dom_info_available_p (dir));
1001   init_dom_info (&di, dir);
1002   calc_dfs_tree (&di, reverse);
1003   calc_idoms (&di, reverse);
1005   FOR_EACH_BB (bb)
1006     {
1007       imm_bb = get_immediate_dominator (dir, bb);
1008       if (!imm_bb)
1009         {
1010           error ("dominator of %d status unknown", bb->index);
1011           err = 1;
1012         }
1014       imm_bb_correct = di.dfs_to_bb[di.dom[di.dfs_order[bb->index]]];
1015       if (imm_bb != imm_bb_correct)
1016         {
1017           error ("dominator of %d should be %d, not %d",
1018                  bb->index, imm_bb_correct->index, imm_bb->index);
1019           err = 1;
1020         }
1021     }
1023   free_dom_info (&di);
1024   gcc_assert (!err);
1025 }
1027 /* Determine immediate dominator (or postdominator, according to DIR) of BB,
1028    assuming that dominators of other blocks are correct.  We also use it to
1029    recompute the dominators in a restricted area, by iterating it until it
1030    reaches a fixed point.  */
1032 basic_block
1033 recompute_dominator (enum cdi_direction dir, basic_block bb)
1034 {
1035   unsigned int dir_index = dom_convert_dir_to_idx (dir);
1036   basic_block dom_bb = NULL;
1037   edge e;
1038   edge_iterator ei;
1040   gcc_assert (dom_computed[dir_index]);
1042   if (dir == CDI_DOMINATORS)
1043     {
1044       FOR_EACH_EDGE (e, ei, bb->preds)
1045         {
1046           if (!dominated_by_p (dir, e->src, bb))
1047             dom_bb = nearest_common_dominator (dir, dom_bb, e->src);
1048         }
1049     }
1050   else
1051     {
1052       FOR_EACH_EDGE (e, ei, bb->succs)
1053         {
1054           if (!dominated_by_p (dir, e->dest, bb))
1055             dom_bb = nearest_common_dominator (dir, dom_bb, e->dest);
1056         }
1057     }
1059   return dom_bb;
1060 }
1062 /* Use simple heuristics (see iterate_fix_dominators) to determine dominators
1063    of BBS.  We assume that all the immediate dominators except for those of the
1064    blocks in BBS are correct.  If CONSERVATIVE is true, we also assume that the
1065    currently recorded immediate dominators of blocks in BBS really dominate the
1066    blocks.  The basic blocks for that we determine the dominator are removed
1067    from BBS.  */
1069 static void
1070 prune_bbs_to_update_dominators (VEC (basic_block, heap) *bbs,
1071                                 bool conservative)
1072 {
1073   unsigned i;
1074   bool single;
1075   basic_block bb, dom = NULL;
1076   edge_iterator ei;
1077   edge e;
1079   for (i = 0; VEC_iterate (basic_block, bbs, i, bb);)
1080     {
1081       if (bb == ENTRY_BLOCK_PTR)
1082         goto succeed;
1084       if (single_pred_p (bb))
1085         {
1086           set_immediate_dominator (CDI_DOMINATORS, bb, single_pred (bb));
1087           goto succeed;
1088         }
1090       if (!conservative)
1091         goto fail;
1093       single = true;
1094       dom = NULL;
1095       FOR_EACH_EDGE (e, ei, bb->preds)
1096         {
1097           if (dominated_by_p (CDI_DOMINATORS, e->src, bb))
1098             continue;
1100           if (!dom)
1101             dom = e->src;
1102           else
1103             {
1104               single = false;
1105               dom = nearest_common_dominator (CDI_DOMINATORS, dom, e->src);
1106             }
1107         }
1109       gcc_assert (dom != NULL);
1110       if (single
1111           || find_edge (dom, bb))
1112         {
1113           set_immediate_dominator (CDI_DOMINATORS, bb, dom);
1114           goto succeed;
1115         }
1117 fail:
1118       i++;
1119       continue;
1121 succeed:
1122       VEC_unordered_remove (basic_block, bbs, i);
1123     }
1124 }
1126 /* Returns root of the dominance tree in the direction DIR that contains
1127    BB.  */
1129 static basic_block
1130 root_of_dom_tree (enum cdi_direction dir, basic_block bb)
1131 {
1132   return (basic_block) et_root (bb->dom[dom_convert_dir_to_idx (dir)])->data;
1133 }
1135 /* See the comment in iterate_fix_dominators.  Finds the immediate dominators
1136    for the sons of Y, found using the SON and BROTHER arrays representing
1137    the dominance tree of graph G.  BBS maps the vertices of G to the basic
1138    blocks.  */
1140 static void
1141 determine_dominators_for_sons (struct graph *g, VEC (basic_block, heap) *bbs,
1142                                int y, int *son, int *brother)
1143 {
1144   bitmap gprime;
1145   int i, a, nc;
1146   VEC (int, heap) **sccs;
1147   basic_block bb, dom, ybb;
1148   unsigned si;
1149   edge e;
1150   edge_iterator ei;
1152   if (son[y] == -1)
1153     return;
1154   if (y == (int) VEC_length (basic_block, bbs))
1155     ybb = ENTRY_BLOCK_PTR;
1156   else
1157     ybb = VEC_index (basic_block, bbs, y);
1159   if (brother[son[y]] == -1)
1160     {
1161       /* Handle the common case Y has just one son specially.  */
1162       bb = VEC_index (basic_block, bbs, son[y]);
1163       set_immediate_dominator (CDI_DOMINATORS, bb,
1164                                recompute_dominator (CDI_DOMINATORS, bb));
1165       identify_vertices (g, y, son[y]);
1166       return;
1167     }
1169   gprime = BITMAP_ALLOC (NULL);
1170   for (a = son[y]; a != -1; a = brother[a])
1171     bitmap_set_bit (gprime, a);
1173   nc = graphds_scc (g, gprime);
1174   BITMAP_FREE (gprime);
1176   sccs = XCNEWVEC (VEC (int, heap) *, nc);
1177   for (a = son[y]; a != -1; a = brother[a])
1178     VEC_safe_push (int, heap, sccs[g->vertices[a].component], a);
1180   for (i = nc - 1; i >= 0; i--)
1181     {
1182       dom = NULL;
1183       for (si = 0; VEC_iterate (int, sccs[i], si, a); si++)
1184         {
1185           bb = VEC_index (basic_block, bbs, a);
1186           FOR_EACH_EDGE (e, ei, bb->preds)
1187             {
1188               if (root_of_dom_tree (CDI_DOMINATORS, e->src) != ybb)
1189                 continue;
1191               dom = nearest_common_dominator (CDI_DOMINATORS, dom, e->src);
1192             }
1193         }
1195       gcc_assert (dom != NULL);
1196       for (si = 0; VEC_iterate (int, sccs[i], si, a); si++)
1197         {
1198           bb = VEC_index (basic_block, bbs, a);
1199           set_immediate_dominator (CDI_DOMINATORS, bb, dom);
1200         }
1201     }
1203   for (i = 0; i < nc; i++)
1204     VEC_free (int, heap, sccs[i]);
1205   free (sccs);
1207   for (a = son[y]; a != -1; a = brother[a])
1208     identify_vertices (g, y, a);
1209 }
1211 /* Recompute dominance information for basic blocks in the set BBS.  The
1212    function assumes that the immediate dominators of all the other blocks
1213    in CFG are correct, and that there are no unreachable blocks.
1215    If CONSERVATIVE is true, we additionally assume that all the ancestors of
1216    a block of BBS in the current dominance tree dominate it.  */
1218 void
1219 iterate_fix_dominators (enum cdi_direction dir, VEC (basic_block, heap) *bbs,
1220                         bool conservative)
1221 {
1222   unsigned i;
1223   basic_block bb, dom;
1224   struct graph *g;
1225   int n, y;
1226   size_t dom_i;
1227   edge e;
1228   edge_iterator ei;
1229   struct pointer_map_t *map;
1230   int *parent, *son, *brother;
1231   unsigned int dir_index = dom_convert_dir_to_idx (dir);
1233   /* We only support updating dominators.  There are some problems with
1234      updating postdominators (need to add fake edges from infinite loops
1235      and noreturn functions), and since we do not currently use
1236      iterate_fix_dominators for postdominators, any attempt to handle these
1237      problems would be unused, untested, and almost surely buggy.  We keep
1238      the DIR argument for consistency with the rest of the dominator analysis
1239      interface.  */
1240   gcc_assert (dir == CDI_DOMINATORS);
1241   gcc_assert (dom_computed[dir_index]);
1243   /* The algorithm we use takes inspiration from the following papers, although
1244      the details are quite different from any of them:
1246       G. Ramalingam, T. Reps, An Incremental Algorithm for Maintaining the
1247          Dominator Tree of a Reducible Flowgraph
1248        V. C. Sreedhar, G. R. Gao, Y.-F. Lee: Incremental computation of
1249           dominator trees
1250        K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance
1251           Algorithm
1253      First, we use the following heuristics to decrease the size of the BBS
1254      set:
1255        a) if BB has a single predecessor, then its immediate dominator is this
1256           predecessor
1257        additionally, if CONSERVATIVE is true:
1258        b) if all the predecessors of BB except for one (X) are dominated by BB,
1259           then X is the immediate dominator of BB
1260        c) if the nearest common ancestor of the predecessors of BB is X and
1261           X -> BB is an edge in CFG, then X is the immediate dominator of BB
1263      Then, we need to establish the dominance relation among the basic blocks
1264      in BBS.  We split the dominance tree by removing the immediate dominator
1265      edges from BBS, creating a forest F.  We form a graph G whose vertices
1266      are BBS and ENTRY and X -> Y is an edge of G if there exists an edge
1267      X' -> Y in CFG such that X' belongs to the tree of the dominance forest
1268      whose root is X.  We then determine dominance tree of G.  Note that
1269      for X, Y in BBS, X dominates Y in CFG if and only if X dominates Y in G.
1270      In this step, we can use arbitrary algorithm to determine dominators.
1271      We decided to prefer the algorithm  to the algorithm of
1272      Lengauer and Tarjan, since the set BBS is usually small (rarely exceeding
1273      10 during gcc bootstrap), and  should perform better in this case.
1275      Finally, we need to determine the immediate dominators for the basic
1276      blocks of BBS.  If the immediate dominator of X in G is Y, then
1277      the immediate dominator of X in CFG belongs to the tree of F rooted in
1278      Y.  We process the dominator tree T of G recursively, starting from leaves.
1279      Suppose that X_1, X_2, ..., X_k are the sons of Y in T, and that the
1280      subtrees of the dominance tree of CFG rooted in X_i are already correct.
1281      Let G' be the subgraph of G induced by {X_1, X_2, ..., X_k}.  We make
1282      the following observations:
1283        (i) the immediate dominator of all blocks in a strongly connected
1284            component of G' is the same
1285        (ii) if X has no predecessors in G', then the immediate dominator of X
1286             is the nearest common ancestor of the predecessors of X in the
1287             subtree of F rooted in Y
1288      Therefore, it suffices to find the topological ordering of G', and
1289      process the nodes X_i in this order using the rules (i) and (ii).
1290      Then, we contract all the nodes X_i with Y in G, so that the further
1291      steps work correctly.  */
1293   if (!conservative)
1294     {
1295       /* Split the tree now.  If the idoms of blocks in BBS are not
1296          conservatively correct, setting the dominators using the
1297          heuristics in prune_bbs_to_update_dominators could
1298          create cycles in the dominance "tree", and cause ICE.  */
1299       for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
1300         set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
1301     }
1303   prune_bbs_to_update_dominators (bbs, conservative);
1304   n = VEC_length (basic_block, bbs);
1306   if (n == 0)
1307     return;
1309   if (n == 1)
1310     {
1311       bb = VEC_index (basic_block, bbs, 0);
1312       set_immediate_dominator (CDI_DOMINATORS, bb,
1313                                recompute_dominator (CDI_DOMINATORS, bb));
1314       return;
1315     }
1317   /* Construct the graph G.  */
1318   map = pointer_map_create ();
1319   for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
1320     {
1321       /* If the dominance tree is conservatively correct, split it now.  */
1322       if (conservative)
1323         set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
1324       *pointer_map_insert (map, bb) = (void *) (size_t) i;
1325     }
1326   *pointer_map_insert (map, ENTRY_BLOCK_PTR) = (void *) (size_t) n;
1328   g = new_graph (n + 1);
1329   for (y = 0; y < g->n_vertices; y++)
1330     g->vertices[y].data = BITMAP_ALLOC (NULL);
1331   for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
1332     {
1333       FOR_EACH_EDGE (e, ei, bb->preds)
1334         {
1335           dom = root_of_dom_tree (CDI_DOMINATORS, e->src);
1336           if (dom == bb)
1337             continue;
1339           dom_i = (size_t) *pointer_map_contains (map, dom);
1341           /* Do not include parallel edges to G.  */
1342           if (bitmap_bit_p ((bitmap) g->vertices[dom_i].data, i))
1343             continue;
1345           bitmap_set_bit ((bitmap) g->vertices[dom_i].data, i);
1347         }
1348     }
1349   for (y = 0; y < g->n_vertices; y++)
1350     BITMAP_FREE (g->vertices[y].data);
1351   pointer_map_destroy (map);
1353   /* Find the dominator tree of G.  */
1354   son = XNEWVEC (int, n + 1);
1355   brother = XNEWVEC (int, n + 1);
1356   parent = XNEWVEC (int, n + 1);
1357   graphds_domtree (g, n, parent, son, brother);
1359   /* Finally, traverse the tree and find the immediate dominators.  */
1360   for (y = n; son[y] != -1; y = son[y])
1361     continue;
1362   while (y != -1)
1363     {
1364       determine_dominators_for_sons (g, bbs, y, son, brother);
1366       if (brother[y] != -1)
1367         {
1368           y = brother[y];
1369           while (son[y] != -1)
1370             y = son[y];
1371         }
1372       else
1373         y = parent[y];
1374     }
1376   free (son);
1377   free (brother);
1378   free (parent);
1380   free_graph (g);
1381 }
1383 void
1384 add_to_dominance_info (enum cdi_direction dir, basic_block bb)
1385 {
1386   unsigned int dir_index = dom_convert_dir_to_idx (dir);
1388   gcc_assert (dom_computed[dir_index]);
1389   gcc_assert (!bb->dom[dir_index]);
1391   n_bbs_in_dom_tree[dir_index]++;
1393   bb->dom[dir_index] = et_new_tree (bb);
1395   if (dom_computed[dir_index] == DOM_OK)
1396     dom_computed[dir_index] = DOM_NO_FAST_QUERY;
1397 }
1399 void
1400 delete_from_dominance_info (enum cdi_direction dir, basic_block bb)
1401 {
1402   unsigned int dir_index = dom_convert_dir_to_idx (dir);
1404   gcc_assert (dom_computed[dir_index]);
1406   et_free_tree (bb->dom[dir_index]);
1407   bb->dom[dir_index] = NULL;
1408   n_bbs_in_dom_tree[dir_index]--;
1410   if (dom_computed[dir_index] == DOM_OK)
1411     dom_computed[dir_index] = DOM_NO_FAST_QUERY;
1412 }
1414 /* Returns the first son of BB in the dominator or postdominator tree
1415    as determined by DIR.  */
1417 basic_block
1418 first_dom_son (enum cdi_direction dir, basic_block bb)
1419 {
1420   unsigned int dir_index = dom_convert_dir_to_idx (dir);
1421   struct et_node *son = bb->dom[dir_index]->son;
1423   return (basic_block) (son ? son->data : NULL);
1424 }
1426 /* Returns the next dominance son after BB in the dominator or postdominator
1427    tree as determined by DIR, or NULL if it was the last one.  */
1429 basic_block
1430 next_dom_son (enum cdi_direction dir, basic_block bb)
1431 {
1432   unsigned int dir_index = dom_convert_dir_to_idx (dir);
1433   struct et_node *next = bb->dom[dir_index]->right;
1435   return (basic_block) (next->father->son == next ? NULL : next->data);
1436 }
1438 /* Return dominance availability for dominance info DIR.  */
1440 enum dom_state
1441 dom_info_state (enum cdi_direction dir)
1442 {
1443   unsigned int dir_index = dom_convert_dir_to_idx (dir);
1445   return dom_computed[dir_index];
1446 }
1448 /* Set the dominance availability for dominance info DIR to NEW_STATE.  */
1450 void
1451 set_dom_info_availability (enum cdi_direction dir, enum dom_state new_state)
1452 {
1453   unsigned int dir_index = dom_convert_dir_to_idx (dir);
1455   dom_computed[dir_index] = new_state;
1456 }
1458 /* Returns true if dominance information for direction DIR is available.  */
1460 bool
1461 dom_info_available_p (enum cdi_direction dir)
1462 {
1463   unsigned int dir_index = dom_convert_dir_to_idx (dir);
1465   return dom_computed[dir_index] != DOM_NONE;
1466 }
1468 void
1469 debug_dominance_info (enum cdi_direction dir)
1470 {
1471   basic_block bb, bb2;
1472   FOR_EACH_BB (bb)
1473     if ((bb2 = get_immediate_dominator (dir, bb)))
1474       fprintf (stderr, "%i %i\n", bb->index, bb2->index);
1475 }
1477 /* Prints to stderr representation of the dominance tree (for direction DIR)
1478    rooted in ROOT, indented by INDENT tabulators.  If INDENT_FIRST is false,
1479    the first line of the output is not indented.  */
1481 static void
1482 debug_dominance_tree_1 (enum cdi_direction dir, basic_block root,
1483                         unsigned indent, bool indent_first)
1484 {
1485   basic_block son;
1486   unsigned i;
1487   bool first = true;
1489   if (indent_first)
1490     for (i = 0; i < indent; i++)
1491       fprintf (stderr, "\t");
1492   fprintf (stderr, "%d\t", root->index);
1494   for (son = first_dom_son (dir, root);
1495        son;
1496        son = next_dom_son (dir, son))
1497     {
1498       debug_dominance_tree_1 (dir, son, indent + 1, !first);
1499       first = false;
1500     }
1502   if (first)
1503     fprintf (stderr, "\n");
1504 }
1506 /* Prints to stderr representation of the dominance tree (for direction DIR)
1507    rooted in ROOT.  */
1509 void
1510 debug_dominance_tree (enum cdi_direction dir, basic_block root)
1511 {
1512   debug_dominance_tree_1 (dir, root, 0, false);
1513 }