OSDN Git Service

245b2de1c2104eee1024f88fe766d493e6dc8f2b
[pf3gnuchains/gcc-fork.git] / gcc / dominance.c
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).
5
6    This file is part of GCC.
7
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.
12
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
16    License for more details.
17
18    You should have received a copy of the GNU General Public License
19    along with GCC; see the file COPYING3.  If not see
20    <http://www.gnu.org/licenses/>.  */
21
22 /* This file implements the well known algorithm from Lengauer and Tarjan
23    to compute the dominators in a control flow graph.  A basic block D is said
24    to dominate another block X, when all paths from the entry node of the CFG
25    to X go also over D.  The dominance relation is a transitive reflexive
26    relation and its minimal transitive reduction is a tree, called the
27    dominator tree.  So for each block X besides the entry block exists a
28    block I(X), called the immediate dominator of X, which is the parent of X
29    in the dominator tree.
30
31    The algorithm computes this dominator tree implicitly by computing for
32    each block its immediate dominator.  We use tree balancing and path
33    compression, so it's the O(e*a(e,v)) variant, where a(e,v) is the very
34    slowly growing functional inverse of the Ackerman function.  */
35
36 #include "config.h"
37 #include "system.h"
38 #include "coretypes.h"
39 #include "tm.h"
40 #include "rtl.h"
41 #include "hard-reg-set.h"
42 #include "obstack.h"
43 #include "basic-block.h"
44 #include "toplev.h"
45 #include "et-forest.h"
46 #include "timevar.h"
47 #include "vecprim.h"
48 #include "pointer-set.h"
49 #include "graphds.h"
50
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.  */
56
57 /* Type of Basic Block aka. TBB */
58 typedef unsigned int TBB;
59
60 /* We work in a poor-mans object oriented fashion, and carry an instance of
61    this structure through all our 'methods'.  It holds various arrays
62    reflecting the (sub)structure of the flowgraph.  Most of them are of type
63    TBB and are also indexed by TBB.  */
64
65 struct dom_info
66 {
67   /* The parent of a node in the DFS tree.  */
68   TBB *dfs_parent;
69   /* For a node x key[x] is roughly the node nearest to the root from which
70      exists a way to x only over nodes behind x.  Such a node is also called
71      semidominator.  */
72   TBB *key;
73   /* The value in path_min[x] is the node y on the path from x to the root of
74      the tree x is in with the smallest key[y].  */
75   TBB *path_min;
76   /* bucket[x] points to the first node of the set of nodes having x as key.  */
77   TBB *bucket;
78   /* And next_bucket[x] points to the next node.  */
79   TBB *next_bucket;
80   /* After the algorithm is done, dom[x] contains the immediate dominator
81      of x.  */
82   TBB *dom;
83
84   /* The following few fields implement the structures needed for disjoint
85      sets.  */
86   /* set_chain[x] is the next node on the path from x to the 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;
94
95   /* If b is the number of a basic block (BB->index), dfs_order[b] is the
96      number of that node in DFS order counted from 1.  This is an index
97      into most of the other arrays in this structure.  */
98   TBB *dfs_order;
99   /* If x is the DFS-index of a node which corresponds with a basic block,
100      dfs_to_bb[x] is that basic block.  Note, that in our structure there are
101      more nodes that basic blocks, so only dfs_to_bb[dfs_order[bb->index]]==bb
102      is true for every basic block bb, but not the opposite.  */
103   basic_block *dfs_to_bb;
104
105   /* This is the next free DFS number when creating the DFS tree.  */
106   unsigned int dfsnum;
107   /* The number of nodes in the DFS tree (==dfsnum-1).  */
108   unsigned int nodes;
109
110   /* Blocks with bits set here have a fake edge to EXIT.  These are used
111      to turn a DFS forest into a proper tree.  */
112   bitmap fake_exit_edge;
113 };
114
115 static void init_dom_info (struct dom_info *, enum cdi_direction);
116 static void free_dom_info (struct dom_info *);
117 static void calc_dfs_tree_nonrec (struct dom_info *, basic_block, 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);
125
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)
142
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.  */
145
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);
155
156   init_ar (di->bucket, TBB, num, 0);
157   init_ar (di->next_bucket, TBB, num, 0);
158
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);
162
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);
165
166   di->dfsnum = 1;
167   di->nodes = 0;
168
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 }
182
183 #undef init_ar
184
185 /* Map dominance calculation type to array index used for various
186    dominance information arrays.  This version is simple -- it will need
187    to be modified, obviously, if additional values are added to
188    cdi_direction.  */
189
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 }
196
197 /* Free all allocated memory in DI, but not DI itself.  */
198
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 }
215
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.  */
221
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;
236
237   stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
238   sp = 0;
239
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     }
253
254   /* When the stack is empty we break out of this loop.  */
255   while (1)
256     {
257       basic_block bn;
258
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);
264
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;
270
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             }
293
294           gcc_assert (bn != en_block);
295
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;
304
305           /* Save the current point in the CFG on the stack, and recurse.  */
306           stack[sp++] = ei;
307           ei = einext;
308         }
309
310       if (!sp)
311         break;
312       ei = stack[--sp];
313
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 }
327
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.  */
332
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++;
341
342   calc_dfs_tree_nonrec (di, begin, reverse);
343
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.
349
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.  */
355
356       basic_block b;
357       bool saw_unconnected = false;
358
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         }
374
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     }
390
391   di->nodes = di->dfsnum - 1;
392
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 }
396
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.  */
401
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 }
417
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.  */
421
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];
428
429   /* V itself is the root.  */
430   if (!rep)
431     return di->path_min[v];
432
433   /* Compress only if necessary.  */
434   if (di->set_chain[rep])
435     {
436       compress (di, v);
437       rep = di->set_chain[v];
438     }
439
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 }
445
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.  */
450
451 static void
452 link_roots (struct dom_info *di, TBB v, TBB w)
453 {
454   TBB s = w;
455
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     }
471
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     }
480
481   /* Merge all subtrees.  */
482   while (s)
483     {
484       di->set_chain[s] = v;
485       s = di->set_child[s];
486     }
487 }
488
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].  */
492
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;
499
500   if (reverse)
501     en_block = EXIT_BLOCK_PTR;
502   else
503     en_block = ENTRY_BLOCK_PTR;
504
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;
511
512       par = di->dfs_parent[v];
513       k = v;
514
515       ei = (reverse) ? ei_start (bb->succs) : ei_start (bb->preds);
516
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         }
527
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;
536
537           e = ei_edge (ei);
538           b = (reverse) ? e->dest : e->src;
539           einext = ei;
540           ei_next (&einext);
541
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];
549
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;
556
557           ei = einext;
558         }
559
560       di->key[v] = k;
561       link_roots (di, par, v);
562       di->next_bucket[v] = di->bucket[k];
563       di->bucket[k] = v;
564
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     }
578
579   /* Explicitly define the dominators.  */
580   di->dom[1] = 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 }
585
586 /* Assign dfs numbers starting from NUM to NODE and its sons.  */
587
588 static void
589 assign_dfs_numbers (struct et_node *node, int *num)
590 {
591   struct et_node *son;
592
593   node->dfs_num_in = (*num)++;
594
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     }
601
602   node->dfs_num_out = (*num)++;
603 }
604
605 /* Compute the data necessary for fast resolving of dominator queries in a
606    static dominator tree.  */
607
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);
614
615   gcc_assert (dom_info_available_p (dir));
616
617   if (dom_computed[dir_index] == DOM_OK)
618     return;
619
620   FOR_ALL_BB (bb)
621     {
622       if (!bb->dom[dir_index]->father)
623         assign_dfs_numbers (bb->dom[dir_index], &num);
624     }
625
626   dom_computed[dir_index] = DOM_OK;
627 }
628
629 /* The main entry point into this module.  DIR is set depending on whether
630    we want to compute dominators or postdominators.  */
631
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;
639
640   if (dom_computed[dir_index] == DOM_OK)
641     return;
642
643   timevar_push (TV_DOMINANCE);
644   if (!dom_info_available_p (dir))
645     {
646       gcc_assert (!n_bbs_in_dom_tree[dir_index]);
647
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;
653
654       init_dom_info (&di, dir);
655       calc_dfs_tree (&di, reverse);
656       calc_idoms (&di, reverse);
657
658       FOR_EACH_BB (b)
659         {
660           TBB d = di.dom[di.dfs_order[b->index]];
661
662           if (di.dfs_to_bb[d])
663             et_set_father (b->dom[dir_index], di.dfs_to_bb[d]->dom[dir_index]);
664         }
665
666       free_dom_info (&di);
667       dom_computed[dir_index] = DOM_NO_FAST_QUERY;
668     }
669
670   compute_dom_fast_query (dir);
671
672   timevar_pop (TV_DOMINANCE);
673 }
674
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);
681
682   if (!dom_info_available_p (dir))
683     return;
684
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 ();
691
692   n_bbs_in_dom_tree[dir_index] = 0;
693
694   dom_computed[dir_index] = DOM_NONE;
695 }
696
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];
703
704   gcc_assert (dom_computed[dir_index]);
705
706   if (!node->father)
707     return NULL;
708
709   return (basic_block) node->father->data;
710 }
711
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];
720
721   gcc_assert (dom_computed[dir_index]);
722
723   if (node->father)
724     {
725       if (node->father->data == dominated_by)
726         return;
727       et_split (node);
728     }
729
730   if (dominated_by)
731     et_set_father (node, dominated_by->dom[dir_index]);
732
733   if (dom_computed[dir_index] == DOM_OK)
734     dom_computed[dir_index] = DOM_NO_FAST_QUERY;
735 }
736
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;
745
746   gcc_assert (dom_computed[dir_index]);
747
748   if (!son)
749     return NULL;
750
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);
754
755   return bbs;
756 }
757
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.  */
761
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;
769
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;
780
781   return doms;
782 }
783
784 /* Returns the list of basic blocks including BB dominated by BB, in the
785    direction DIR.  The vector will be sorted in preorder.  */
786
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;
792
793   i = 0;
794   VEC_safe_push (basic_block, heap, bbs, bb);
795
796   do
797     {
798       basic_block son;
799
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));
807
808   return bbs;
809 }
810
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;
818
819   bb_node = bb->dom[dir_index];
820   to_node = to->dom[dir_index];
821
822   gcc_assert (dom_computed[dir_index]);
823
824   if (!bb_node->son)
825     return;
826
827   while (bb_node->son)
828     {
829       son = bb_node->son;
830
831       et_split (son);
832       et_set_father (son, to_node);
833     }
834
835   if (dom_computed[dir_index] == DOM_OK)
836     dom_computed[dir_index] = DOM_NO_FAST_QUERY;
837 }
838
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);
844
845   gcc_assert (dom_computed[dir_index]);
846
847   if (!bb1)
848     return bb2;
849   if (!bb2)
850     return bb1;
851
852   return (basic_block) et_nca (bb1->dom[dir_index], bb2->dom[dir_index])->data;
853 }
854
855
856 /* Find the nearest common dominator for the basic blocks in BLOCKS,
857    using dominance direction DIR.  */
858
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;
865
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));
871
872   return dom;
873 }
874
875 /*  Given a dominator tree, we can determine whether one thing
876     dominates another in constant time by using two DFS numbers:
877
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
880
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.
884
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:
888
889     1. Node A is above Node B (and thus, Node A dominates node B)
890
891      A
892      |
893      C
894     / \
895    B   D
896
897
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
902
903    2. Node A is below node B (and thus, node B dominates node A)
904
905
906      B
907      |
908      A
909     / \
910    C   D
911
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.
914
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
917
918    3. Node A and B are siblings (and thus, neither dominates the other)
919
920      C
921      |
922      D
923     / \
924    A   B
925
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.
935
936    Thus, it is sufficient to write
937
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    }
943
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    }  */
949
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];
956
957   gcc_assert (dom_computed[dir_index]);
958
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);
962
963   return et_below (n1, n2);
964 }
965
966 /* Returns the entry dfs number for basic block BB, in the direction DIR.  */
967
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];
973
974   gcc_assert (dom_computed[dir_index] == DOM_OK);
975   return n->dfs_num_in;
976 }
977
978 /* Returns the exit dfs number for basic block BB, in the direction DIR.  */
979
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];
985
986   gcc_assert (dom_computed[dir_index] == DOM_OK);
987   return n->dfs_num_out;
988 }
989
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;
998
999   gcc_assert (dom_info_available_p (dir));
1000
1001   init_dom_info (&di, dir);
1002   calc_dfs_tree (&di, reverse);
1003   calc_idoms (&di, reverse);
1004
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         }
1013
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     }
1022
1023   free_dom_info (&di);
1024   gcc_assert (!err);
1025 }
1026
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.  */
1031
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;
1039
1040   gcc_assert (dom_computed[dir_index]);
1041
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     }
1058
1059   return dom_bb;
1060 }
1061
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.  */
1068
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;
1078
1079   for (i = 0; VEC_iterate (basic_block, bbs, i, bb);)
1080     {
1081       if (bb == ENTRY_BLOCK_PTR)
1082         goto succeed;
1083
1084       if (single_pred_p (bb))
1085         {
1086           set_immediate_dominator (CDI_DOMINATORS, bb, single_pred (bb));
1087           goto succeed;
1088         }
1089
1090       if (!conservative)
1091         goto fail;
1092
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;
1099
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         }
1108
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         }
1116
1117 fail:
1118       i++;
1119       continue;
1120
1121 succeed:
1122       VEC_unordered_remove (basic_block, bbs, i);
1123     }
1124 }
1125
1126 /* Returns root of the dominance tree in the direction DIR that contains
1127    BB.  */
1128
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 }
1134
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.  */
1139
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;
1151
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);
1158
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     }
1168
1169   gprime = BITMAP_ALLOC (NULL);
1170   for (a = son[y]; a != -1; a = brother[a])
1171     bitmap_set_bit (gprime, a);
1172
1173   nc = graphds_scc (g, gprime);
1174   BITMAP_FREE (gprime);
1175
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);
1179
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;
1190
1191               dom = nearest_common_dominator (CDI_DOMINATORS, dom, e->src);
1192             }
1193         }
1194
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     }
1202
1203   for (i = 0; i < nc; i++)
1204     VEC_free (int, heap, sccs[i]);
1205   free (sccs);
1206
1207   for (a = son[y]; a != -1; a = brother[a])
1208     identify_vertices (g, y, a);
1209 }
1210
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.
1214
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.  */
1217
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);
1232
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]);
1242
1243   /* The algorithm we use takes inspiration from the following papers, although
1244      the details are quite different from any of them:
1245
1246      [1] G. Ramalingam, T. Reps, An Incremental Algorithm for Maintaining the
1247          Dominator Tree of a Reducible Flowgraph
1248      [2]  V. C. Sreedhar, G. R. Gao, Y.-F. Lee: Incremental computation of
1249           dominator trees
1250      [3]  K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance
1251           Algorithm
1252
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
1262
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 [3] to the algorithm of
1272      Lengauer and Tarjan, since the set BBS is usually small (rarely exceeding
1273      10 during gcc bootstrap), and [3] should perform better in this case.
1274
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.  */
1292
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     }
1302
1303   prune_bbs_to_update_dominators (bbs, conservative);
1304   n = VEC_length (basic_block, bbs);
1305
1306   if (n == 0)
1307     return;
1308
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     }
1316
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;
1327
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;
1338
1339           dom_i = (size_t) *pointer_map_contains (map, dom);
1340
1341           /* Do not include parallel edges to G.  */
1342           if (bitmap_bit_p ((bitmap) g->vertices[dom_i].data, i))
1343             continue;
1344
1345           bitmap_set_bit ((bitmap) g->vertices[dom_i].data, i);
1346           add_edge (g, dom_i, i);
1347         }
1348     }
1349   for (y = 0; y < g->n_vertices; y++)
1350     BITMAP_FREE (g->vertices[y].data);
1351   pointer_map_destroy (map);
1352
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);
1358
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);
1365
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     }
1375
1376   free (son);
1377   free (brother);
1378   free (parent);
1379
1380   free_graph (g);
1381 }
1382
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);
1387
1388   gcc_assert (dom_computed[dir_index]);
1389   gcc_assert (!bb->dom[dir_index]);
1390
1391   n_bbs_in_dom_tree[dir_index]++;
1392
1393   bb->dom[dir_index] = et_new_tree (bb);
1394
1395   if (dom_computed[dir_index] == DOM_OK)
1396     dom_computed[dir_index] = DOM_NO_FAST_QUERY;
1397 }
1398
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);
1403
1404   gcc_assert (dom_computed[dir_index]);
1405
1406   et_free_tree (bb->dom[dir_index]);
1407   bb->dom[dir_index] = NULL;
1408   n_bbs_in_dom_tree[dir_index]--;
1409
1410   if (dom_computed[dir_index] == DOM_OK)
1411     dom_computed[dir_index] = DOM_NO_FAST_QUERY;
1412 }
1413
1414 /* Returns the first son of BB in the dominator or postdominator tree
1415    as determined by DIR.  */
1416
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;
1422
1423   return (basic_block) (son ? son->data : NULL);
1424 }
1425
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.  */
1428
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;
1434
1435   return (basic_block) (next->father->son == next ? NULL : next->data);
1436 }
1437
1438 /* Return dominance availability for dominance info DIR.  */
1439
1440 enum dom_state
1441 dom_info_state (enum cdi_direction dir)
1442 {
1443   unsigned int dir_index = dom_convert_dir_to_idx (dir);
1444
1445   return dom_computed[dir_index];
1446 }
1447
1448 /* Set the dominance availability for dominance info DIR to NEW_STATE.  */
1449
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);
1454
1455   dom_computed[dir_index] = new_state;
1456 }
1457
1458 /* Returns true if dominance information for direction DIR is available.  */
1459
1460 bool
1461 dom_info_available_p (enum cdi_direction dir)
1462 {
1463   unsigned int dir_index = dom_convert_dir_to_idx (dir);
1464
1465   return dom_computed[dir_index] != DOM_NONE;
1466 }
1467
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 }
1476
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.  */
1480
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;
1488
1489   if (indent_first)
1490     for (i = 0; i < indent; i++)
1491       fprintf (stderr, "\t");
1492   fprintf (stderr, "%d\t", root->index);
1493
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     }
1501
1502   if (first)
1503     fprintf (stderr, "\n");
1504 }
1505
1506 /* Prints to stderr representation of the dominance tree (for direction DIR)
1507    rooted in ROOT.  */
1508
1509 void
1510 debug_dominance_tree (enum cdi_direction dir, basic_block root)
1511 {
1512   debug_dominance_tree_1 (dir, root, 0, false);
1513 }