Deleted Added
sdiff udiff text old ( 96489 ) new ( 117395 )
full compact
dominance.c (96489) dominance.c (117395)
1/* Calculate (post)dominators in slightly super-linear time.
2 Copyright (C) 2000 Free Software Foundation, Inc.
3 Contributed by Michael Matz (matz@ifh.de).
1/* Calculate (post)dominators in slightly super-linear time.
2 Copyright (C) 2000 Free Software Foundation, Inc.
3 Contributed by Michael Matz (matz@ifh.de).
4
4
5 This file is part of GCC.
5 This file is part of GCC.
6
6
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
10 any later version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public

--- 18 unchanged lines hidden (view full) ---

33 compression, so its the O(e*a(e,v)) variant, where a(e,v) is the very
34 slowly growing functional inverse of the Ackerman function. */
35
36#include "config.h"
37#include "system.h"
38#include "rtl.h"
39#include "hard-reg-set.h"
40#include "basic-block.h"
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
10 any later version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public

--- 18 unchanged lines hidden (view full) ---

33 compression, so its the O(e*a(e,v)) variant, where a(e,v) is the very
34 slowly growing functional inverse of the Ackerman function. */
35
36#include "config.h"
37#include "system.h"
38#include "rtl.h"
39#include "hard-reg-set.h"
40#include "basic-block.h"
41#include "errors.h"
42#include "et-forest.h"
41
43
44struct dominance_info
45{
46 et_forest_t forest;
47 varray_type varray;
48};
42
49
50#define BB_NODE(info, bb) \
51 ((et_forest_node_t)VARRAY_GENERIC_PTR ((info)->varray, (bb)->index + 2))
52#define SET_BB_NODE(info, bb, node) \
53 (VARRAY_GENERIC_PTR ((info)->varray, (bb)->index + 2) = (node))
54
43/* We name our nodes with integers, beginning with 1. Zero is reserved for
44 'undefined' or 'end of list'. The name of each node is given by the dfs
45 number of the corresponding basic block. Please note, that we include the
46 artificial ENTRY_BLOCK (or EXIT_BLOCK in the post-dom case) in our lists to
47 support multiple entry points. As it has no real basic block index we use
55/* We name our nodes with integers, beginning with 1. Zero is reserved for
56 'undefined' or 'end of list'. The name of each node is given by the dfs
57 number of the corresponding basic block. Please note, that we include the
58 artificial ENTRY_BLOCK (or EXIT_BLOCK in the post-dom case) in our lists to
59 support multiple entry points. As it has no real basic block index we use
48 'n_basic_blocks' for that. Its dfs number is of course 1. */
60 'last_basic_block' for that. Its dfs number is of course 1. */
49
50/* Type of Basic Block aka. TBB */
51typedef unsigned int TBB;
52
53/* We work in a poor-mans object oriented fashion, and carry an instance of
54 this structure through all our 'methods'. It holds various arrays
55 reflecting the (sub)structure of the flowgraph. Most of them are of type
56 TBB and are also indexed by TBB. */

--- 27 unchanged lines hidden (view full) ---

84 /* set_child[x] is used for balancing the tree representing a set. It can
85 be understood as the next sibling of x. */
86 TBB *set_child;
87
88 /* If b is the number of a basic block (BB->index), dfs_order[b] is the
89 number of that node in DFS order counted from 1. This is an index
90 into most of the other arrays in this structure. */
91 TBB *dfs_order;
61
62/* Type of Basic Block aka. TBB */
63typedef unsigned int TBB;
64
65/* We work in a poor-mans object oriented fashion, and carry an instance of
66 this structure through all our 'methods'. It holds various arrays
67 reflecting the (sub)structure of the flowgraph. Most of them are of type
68 TBB and are also indexed by TBB. */

--- 27 unchanged lines hidden (view full) ---

96 /* set_child[x] is used for balancing the tree representing a set. It can
97 be understood as the next sibling of x. */
98 TBB *set_child;
99
100 /* If b is the number of a basic block (BB->index), dfs_order[b] is the
101 number of that node in DFS order counted from 1. This is an index
102 into most of the other arrays in this structure. */
103 TBB *dfs_order;
92 /* If x is the DFS-index of a node which corresponds with an basic block,
104 /* If x is the DFS-index of a node which corresponds with a basic block,
93 dfs_to_bb[x] is that basic block. Note, that in our structure there are
94 more nodes that basic blocks, so only dfs_to_bb[dfs_order[bb->index]]==bb
95 is true for every basic block bb, but not the opposite. */
96 basic_block *dfs_to_bb;
97
98 /* This is the next free DFS number when creating the DFS tree or forest. */
99 unsigned int dfsnum;
100 /* The number of nodes in the DFS tree (==dfsnum-1). */

--- 7 unchanged lines hidden (view full) ---

108 enum cdi_direction));
109static void calc_dfs_tree PARAMS ((struct dom_info *,
110 enum cdi_direction));
111static void compress PARAMS ((struct dom_info *, TBB));
112static TBB eval PARAMS ((struct dom_info *, TBB));
113static void link_roots PARAMS ((struct dom_info *, TBB, TBB));
114static void calc_idoms PARAMS ((struct dom_info *,
115 enum cdi_direction));
105 dfs_to_bb[x] is that basic block. Note, that in our structure there are
106 more nodes that basic blocks, so only dfs_to_bb[dfs_order[bb->index]]==bb
107 is true for every basic block bb, but not the opposite. */
108 basic_block *dfs_to_bb;
109
110 /* This is the next free DFS number when creating the DFS tree or forest. */
111 unsigned int dfsnum;
112 /* The number of nodes in the DFS tree (==dfsnum-1). */

--- 7 unchanged lines hidden (view full) ---

120 enum cdi_direction));
121static void calc_dfs_tree PARAMS ((struct dom_info *,
122 enum cdi_direction));
123static void compress PARAMS ((struct dom_info *, TBB));
124static TBB eval PARAMS ((struct dom_info *, TBB));
125static void link_roots PARAMS ((struct dom_info *, TBB, TBB));
126static void calc_idoms PARAMS ((struct dom_info *,
127 enum cdi_direction));
116static void idoms_to_doms PARAMS ((struct dom_info *,
117 sbitmap *));
128void debug_dominance_info PARAMS ((dominance_info));
118
119/* Helper macro for allocating and initializing an array,
120 for aesthetic reasons. */
121#define init_ar(var, type, num, content) \
129
130/* Helper macro for allocating and initializing an array,
131 for aesthetic reasons. */
132#define init_ar(var, type, num, content) \
122 do { \
123 unsigned int i = 1; /* Catch content == i. */ \
124 if (! (content)) \
125 (var) = (type *) xcalloc ((num), sizeof (type)); \
126 else \
127 { \
128 (var) = (type *) xmalloc ((num) * sizeof (type)); \
129 for (i = 0; i < num; i++) \
130 (var)[i] = (content); \
131 } \
132 } while (0)
133 do \
134 { \
135 unsigned int i = 1; /* Catch content == i. */ \
136 if (! (content)) \
137 (var) = (type *) xcalloc ((num), sizeof (type)); \
138 else \
139 { \
140 (var) = (type *) xmalloc ((num) * sizeof (type)); \
141 for (i = 0; i < num; i++) \
142 (var)[i] = (content); \
143 } \
144 } \
145 while (0)
133
134/* Allocate all needed memory in a pessimistic fashion (so we round up).
146
147/* Allocate all needed memory in a pessimistic fashion (so we round up).
135 This initialises the contents of DI, which already must be allocated. */
148 This initializes the contents of DI, which already must be allocated. */
136
137static void
138init_dom_info (di)
139 struct dom_info *di;
140{
141 /* We need memory for n_basic_blocks nodes and the ENTRY_BLOCK or
142 EXIT_BLOCK. */
143 unsigned int num = n_basic_blocks + 1 + 1;

--- 4 unchanged lines hidden (view full) ---

148
149 init_ar (di->bucket, TBB, num, 0);
150 init_ar (di->next_bucket, TBB, num, 0);
151
152 init_ar (di->set_chain, TBB, num, 0);
153 init_ar (di->set_size, unsigned int, num, 1);
154 init_ar (di->set_child, TBB, num, 0);
155
149
150static void
151init_dom_info (di)
152 struct dom_info *di;
153{
154 /* We need memory for n_basic_blocks nodes and the ENTRY_BLOCK or
155 EXIT_BLOCK. */
156 unsigned int num = n_basic_blocks + 1 + 1;

--- 4 unchanged lines hidden (view full) ---

161
162 init_ar (di->bucket, TBB, num, 0);
163 init_ar (di->next_bucket, TBB, num, 0);
164
165 init_ar (di->set_chain, TBB, num, 0);
166 init_ar (di->set_size, unsigned int, num, 1);
167 init_ar (di->set_child, TBB, num, 0);
168
156 init_ar (di->dfs_order, TBB, (unsigned int) n_basic_blocks + 1, 0);
169 init_ar (di->dfs_order, TBB, (unsigned int) last_basic_block + 1, 0);
157 init_ar (di->dfs_to_bb, basic_block, num, 0);
158
159 di->dfsnum = 1;
160 di->nodes = 0;
161}
162
163#undef init_ar
164

--- 99 unchanged lines hidden (view full) ---

264
265 if (bn == en_block)
266 abort ();
267
268 /* Fill the DFS tree info calculatable _before_ recursing. */
269 if (bb != en_block)
270 my_i = di->dfs_order[bb->index];
271 else
170 init_ar (di->dfs_to_bb, basic_block, num, 0);
171
172 di->dfsnum = 1;
173 di->nodes = 0;
174}
175
176#undef init_ar
177

--- 99 unchanged lines hidden (view full) ---

277
278 if (bn == en_block)
279 abort ();
280
281 /* Fill the DFS tree info calculatable _before_ recursing. */
282 if (bb != en_block)
283 my_i = di->dfs_order[bb->index];
284 else
272 my_i = di->dfs_order[n_basic_blocks];
285 my_i = di->dfs_order[last_basic_block];
273 child_i = di->dfs_order[bn->index] = di->dfsnum++;
274 di->dfs_to_bb[child_i] = bn;
275 di->dfs_parent[child_i] = my_i;
276
277 /* Save the current point in the CFG on the stack, and recurse. */
278 stack[sp++] = e;
279 e = e_next;
280 }

--- 26 unchanged lines hidden (view full) ---

307
308static void
309calc_dfs_tree (di, reverse)
310 struct dom_info *di;
311 enum cdi_direction reverse;
312{
313 /* The first block is the ENTRY_BLOCK (or EXIT_BLOCK if REVERSE). */
314 basic_block begin = reverse ? EXIT_BLOCK_PTR : ENTRY_BLOCK_PTR;
286 child_i = di->dfs_order[bn->index] = di->dfsnum++;
287 di->dfs_to_bb[child_i] = bn;
288 di->dfs_parent[child_i] = my_i;
289
290 /* Save the current point in the CFG on the stack, and recurse. */
291 stack[sp++] = e;
292 e = e_next;
293 }

--- 26 unchanged lines hidden (view full) ---

320
321static void
322calc_dfs_tree (di, reverse)
323 struct dom_info *di;
324 enum cdi_direction reverse;
325{
326 /* The first block is the ENTRY_BLOCK (or EXIT_BLOCK if REVERSE). */
327 basic_block begin = reverse ? EXIT_BLOCK_PTR : ENTRY_BLOCK_PTR;
315 di->dfs_order[n_basic_blocks] = di->dfsnum;
328 di->dfs_order[last_basic_block] = di->dfsnum;
316 di->dfs_to_bb[di->dfsnum] = begin;
317 di->dfsnum++;
318
319 calc_dfs_tree_nonrec (di, begin, reverse);
320
321 if (reverse)
322 {
323 /* In the post-dom case we may have nodes without a path to EXIT_BLOCK.
324 They are reverse-unreachable. In the dom-case we disallow such
325 nodes, but in post-dom we have to deal with them, so we simply
326 include them in the DFS tree which actually becomes a forest. */
329 di->dfs_to_bb[di->dfsnum] = begin;
330 di->dfsnum++;
331
332 calc_dfs_tree_nonrec (di, begin, reverse);
333
334 if (reverse)
335 {
336 /* In the post-dom case we may have nodes without a path to EXIT_BLOCK.
337 They are reverse-unreachable. In the dom-case we disallow such
338 nodes, but in post-dom we have to deal with them, so we simply
339 include them in the DFS tree which actually becomes a forest. */
327 int i;
328 for (i = n_basic_blocks - 1; i >= 0; i--)
340 basic_block b;
341 FOR_EACH_BB_REVERSE (b)
329 {
342 {
330 basic_block b = BASIC_BLOCK (i);
331 if (di->dfs_order[b->index])
332 continue;
333 di->dfs_order[b->index] = di->dfsnum;
334 di->dfs_to_bb[di->dfsnum] = b;
335 di->dfsnum++;
336 calc_dfs_tree_nonrec (di, b, reverse);
337 }
338 }

--- 148 unchanged lines hidden (view full) ---

487 e_next = e->succ_next;
488 }
489 else
490 {
491 b = e->src;
492 e_next = e->pred_next;
493 }
494 if (b == en_block)
343 if (di->dfs_order[b->index])
344 continue;
345 di->dfs_order[b->index] = di->dfsnum;
346 di->dfs_to_bb[di->dfsnum] = b;
347 di->dfsnum++;
348 calc_dfs_tree_nonrec (di, b, reverse);
349 }
350 }

--- 148 unchanged lines hidden (view full) ---

499 e_next = e->succ_next;
500 }
501 else
502 {
503 b = e->src;
504 e_next = e->pred_next;
505 }
506 if (b == en_block)
495 k1 = di->dfs_order[n_basic_blocks];
507 k1 = di->dfs_order[last_basic_block];
496 else
497 k1 = di->dfs_order[b->index];
498
499 /* Call eval() only if really needed. If k1 is above V in DFS tree,
500 then we know, that eval(k1) == k1 and key[k1] == k1. */
501 if (k1 > v)
502 k1 = di->key[eval (di, k1)];
503 if (k1 < k)

--- 21 unchanged lines hidden (view full) ---

525
526 /* Explicitly define the dominators. */
527 di->dom[1] = 0;
528 for (v = 2; v <= di->nodes; v++)
529 if (di->dom[v] != di->key[v])
530 di->dom[v] = di->dom[di->dom[v]];
531}
532
508 else
509 k1 = di->dfs_order[b->index];
510
511 /* Call eval() only if really needed. If k1 is above V in DFS tree,
512 then we know, that eval(k1) == k1 and key[k1] == k1. */
513 if (k1 > v)
514 k1 = di->key[eval (di, k1)];
515 if (k1 < k)

--- 21 unchanged lines hidden (view full) ---

537
538 /* Explicitly define the dominators. */
539 di->dom[1] = 0;
540 for (v = 2; v <= di->nodes; v++)
541 if (di->dom[v] != di->key[v])
542 di->dom[v] = di->dom[di->dom[v]];
543}
544
533/* Convert the information about immediate dominators (in DI) to sets of all
534 dominators (in DOMINATORS). */
535
536static void
537idoms_to_doms (di, dominators)
538 struct dom_info *di;
539 sbitmap *dominators;
540{
541 TBB i, e_index;
542 int bb, bb_idom;
543 sbitmap_vector_zero (dominators, n_basic_blocks);
544 /* We have to be careful, to not include the ENTRY_BLOCK or EXIT_BLOCK
545 in the list of (post)-doms, so remember that in e_index. */
546 e_index = di->dfs_order[n_basic_blocks];
547
548 for (i = 1; i <= di->nodes; i++)
549 {
550 if (i == e_index)
551 continue;
552 bb = di->dfs_to_bb[i]->index;
553
554 if (di->dom[i] && (di->dom[i] != e_index))
555 {
556 bb_idom = di->dfs_to_bb[di->dom[i]]->index;
557 sbitmap_copy (dominators[bb], dominators[bb_idom]);
558 }
559 else
560 {
561 /* It has no immediate dom or only ENTRY_BLOCK or EXIT_BLOCK.
562 If it is a child of ENTRY_BLOCK that's OK, and it's only
563 dominated by itself; if it's _not_ a child of ENTRY_BLOCK, it
564 means, it is unreachable. That case has been disallowed in the
565 building of the DFS tree, so we are save here. For the reverse
566 flow graph it means, it has no children, so, to be compatible
567 with the old code, we set the post_dominators to all one. */
568 if (!di->dom[i])
569 {
570 sbitmap_ones (dominators[bb]);
571 }
572 }
573 SET_BIT (dominators[bb], bb);
574 }
575}
576
577/* The main entry point into this module. IDOM is an integer array with room
545/* The main entry point into this module. IDOM is an integer array with room
578 for n_basic_blocks integers, DOMS is a preallocated sbitmap array having
579 room for n_basic_blocks^2 bits, and POST is true if the caller wants to
546 for last_basic_block integers, DOMS is a preallocated sbitmap array having
547 room for last_basic_block^2 bits, and POST is true if the caller wants to
580 know post-dominators.
581
582 On return IDOM[i] will be the BB->index of the immediate (post) dominator
583 of basic block i, and DOMS[i] will have set bit j if basic block j is a
584 (post)dominator for block i.
585
586 Either IDOM or DOMS may be NULL (meaning the caller is not interested in
587 immediate resp. all dominators). */
588
548 know post-dominators.
549
550 On return IDOM[i] will be the BB->index of the immediate (post) dominator
551 of basic block i, and DOMS[i] will have set bit j if basic block j is a
552 (post)dominator for block i.
553
554 Either IDOM or DOMS may be NULL (meaning the caller is not interested in
555 immediate resp. all dominators). */
556
589void
590calculate_dominance_info (idom, doms, reverse)
591 int *idom;
592 sbitmap *doms;
557dominance_info
558calculate_dominance_info (reverse)
593 enum cdi_direction reverse;
594{
595 struct dom_info di;
559 enum cdi_direction reverse;
560{
561 struct dom_info di;
562 dominance_info info;
563 basic_block b;
596
564
597 if (!doms && !idom)
598 return;
565 /* allocate structure for dominance information. */
566 info = xmalloc (sizeof (struct dominance_info));
567 info->forest = et_forest_create ();
568 VARRAY_GENERIC_PTR_INIT (info->varray, last_basic_block + 3, "dominance info");
569
570 /* Add the two well-known basic blocks. */
571 SET_BB_NODE (info, ENTRY_BLOCK_PTR, et_forest_add_node (info->forest,
572 ENTRY_BLOCK_PTR));
573 SET_BB_NODE (info, EXIT_BLOCK_PTR, et_forest_add_node (info->forest,
574 EXIT_BLOCK_PTR));
575 FOR_EACH_BB (b)
576 SET_BB_NODE (info, b, et_forest_add_node (info->forest, b));
577
599 init_dom_info (&di);
600 calc_dfs_tree (&di, reverse);
601 calc_idoms (&di, reverse);
602
578 init_dom_info (&di);
579 calc_dfs_tree (&di, reverse);
580 calc_idoms (&di, reverse);
581
603 if (idom)
582
583 FOR_EACH_BB (b)
604 {
584 {
605 int i;
606 for (i = 0; i < n_basic_blocks; i++)
585 TBB d = di.dom[di.dfs_order[b->index]];
586
587 if (di.dfs_to_bb[d])
588 et_forest_add_edge (info->forest, BB_NODE (info, di.dfs_to_bb[d]), BB_NODE (info, b));
589 }
590
591 free_dom_info (&di);
592 return info;
593}
594
595/* Free dominance information. */
596void
597free_dominance_info (info)
598 dominance_info info;
599{
600 basic_block bb;
601
602 /* Allow users to create new basic block without setting up the dominance
603 information for them. */
604 FOR_EACH_BB (bb)
605 if (bb->index < (int)(info->varray->num_elements - 2)
606 && BB_NODE (info, bb))
607 delete_from_dominance_info (info, bb);
608 delete_from_dominance_info (info, ENTRY_BLOCK_PTR);
609 delete_from_dominance_info (info, EXIT_BLOCK_PTR);
610 et_forest_delete (info->forest);
611 VARRAY_GROW (info->varray, 0);
612 free (info);
613}
614
615/* Return the immediate dominator of basic block BB. */
616basic_block
617get_immediate_dominator (dom, bb)
618 dominance_info dom;
619 basic_block bb;
620{
621 return et_forest_node_value (dom->forest,
622 et_forest_parent (dom->forest,
623 BB_NODE (dom, bb)));
624}
625
626/* Set the immediate dominator of the block possibly removing
627 existing edge. NULL can be used to remove any edge. */
628inline void
629set_immediate_dominator (dom, bb, dominated_by)
630 dominance_info dom;
631 basic_block bb, dominated_by;
632{
633 void *aux_bb_node;
634 et_forest_node_t bb_node = BB_NODE (dom, bb);
635
636 aux_bb_node = et_forest_parent (dom->forest, bb_node);
637 if (aux_bb_node)
638 et_forest_remove_edge (dom->forest, aux_bb_node, bb_node);
639 if (dominated_by != NULL)
640 {
641 if (bb == dominated_by)
642 abort ();
643 if (!et_forest_add_edge (dom->forest, BB_NODE (dom, dominated_by), bb_node))
644 abort ();
645 }
646}
647
648/* Store all basic blocks dominated by BB into BBS and return their number. */
649int
650get_dominated_by (dom, bb, bbs)
651 dominance_info dom;
652 basic_block bb;
653 basic_block **bbs;
654{
655 int n, i;
656
657 *bbs = xmalloc (n_basic_blocks * sizeof (basic_block));
658 n = et_forest_enumerate_sons (dom->forest, BB_NODE (dom, bb), (et_forest_node_t *)*bbs);
659 for (i = 0; i < n; i++)
660 (*bbs)[i] = et_forest_node_value (dom->forest, (et_forest_node_t)(*bbs)[i]);
661 return n;
662}
663
664/* Redirect all edges pointing to BB to TO. */
665void
666redirect_immediate_dominators (dom, bb, to)
667 dominance_info dom;
668 basic_block bb;
669 basic_block to;
670{
671 et_forest_node_t *bbs = xmalloc (n_basic_blocks * sizeof (basic_block));
672 et_forest_node_t node = BB_NODE (dom, bb);
673 et_forest_node_t node2 = BB_NODE (dom, to);
674 int n = et_forest_enumerate_sons (dom->forest, node, bbs);
675 int i;
676
677 for (i = 0; i < n; i++)
678 {
679 et_forest_remove_edge (dom->forest, node, bbs[i]);
680 et_forest_add_edge (dom->forest, node2, bbs[i]);
681 }
682 free (bbs);
683}
684
685/* Find first basic block in the tree dominating both BB1 and BB2. */
686basic_block
687nearest_common_dominator (dom, bb1, bb2)
688 dominance_info dom;
689 basic_block bb1;
690 basic_block bb2;
691{
692 if (!bb1)
693 return bb2;
694 if (!bb2)
695 return bb1;
696 return et_forest_node_value (dom->forest,
697 et_forest_common_ancestor (dom->forest,
698 BB_NODE (dom, bb1),
699 BB_NODE (dom,
700 bb2)));
701}
702
703/* Return TRUE in case BB1 is dominated by BB2. */
704bool
705dominated_by_p (dom, bb1, bb2)
706 dominance_info dom;
707 basic_block bb1;
708 basic_block bb2;
709{
710 return nearest_common_dominator (dom, bb1, bb2) == bb2;
711}
712
713/* Verify invariants of dominator structure. */
714void
715verify_dominators (dom)
716 dominance_info dom;
717{
718 int err = 0;
719 basic_block bb;
720
721 FOR_EACH_BB (bb)
722 {
723 basic_block dom_bb;
724
725 dom_bb = recount_dominator (dom, bb);
726 if (dom_bb != get_immediate_dominator (dom, bb))
607 {
727 {
608 basic_block b = BASIC_BLOCK (i);
609 TBB d = di.dom[di.dfs_order[b->index]];
728 error ("dominator of %d should be %d, not %d",
729 bb->index, dom_bb->index, get_immediate_dominator(dom, bb)->index);
730 err = 1;
731 }
732 }
733 if (err)
734 abort ();
735}
610
736
611 /* The old code didn't modify array elements of nodes having only
612 itself as dominator (d==0) or only ENTRY_BLOCK (resp. EXIT_BLOCK)
613 (d==1). */
614 if (d > 1)
615 idom[i] = di.dfs_to_bb[d]->index;
737/* Recount dominator of BB. */
738basic_block
739recount_dominator (dom, bb)
740 dominance_info dom;
741 basic_block bb;
742{
743 basic_block dom_bb = NULL;
744 edge e;
745
746 for (e = bb->pred; e; e = e->pred_next)
747 {
748 if (!dominated_by_p (dom, e->src, bb))
749 dom_bb = nearest_common_dominator (dom, dom_bb, e->src);
750 }
751
752 return dom_bb;
753}
754
755/* Iteratively recount dominators of BBS. The change is supposed to be local
756 and not to grow further. */
757void
758iterate_fix_dominators (dom, bbs, n)
759 dominance_info dom;
760 basic_block *bbs;
761 int n;
762{
763 int i, changed = 1;
764 basic_block old_dom, new_dom;
765
766 while (changed)
767 {
768 changed = 0;
769 for (i = 0; i < n; i++)
770 {
771 old_dom = get_immediate_dominator (dom, bbs[i]);
772 new_dom = recount_dominator (dom, bbs[i]);
773 if (old_dom != new_dom)
774 {
775 changed = 1;
776 set_immediate_dominator (dom, bbs[i], new_dom);
777 }
616 }
617 }
778 }
779 }
618 if (doms)
619 idoms_to_doms (&di, doms);
780}
620
781
621 free_dom_info (&di);
782void
783add_to_dominance_info (dom, bb)
784 dominance_info dom;
785 basic_block bb;
786{
787 VARRAY_GROW (dom->varray, last_basic_block + 3);
788#ifdef ENABLE_CHECKING
789 if (BB_NODE (dom, bb))
790 abort ();
791#endif
792 SET_BB_NODE (dom, bb, et_forest_add_node (dom->forest, bb));
622}
793}
794
795void
796delete_from_dominance_info (dom, bb)
797 dominance_info dom;
798 basic_block bb;
799{
800 et_forest_remove_node (dom->forest, BB_NODE (dom, bb));
801 SET_BB_NODE (dom, bb, NULL);
802}
803
804void
805debug_dominance_info (dom)
806 dominance_info dom;
807{
808 basic_block bb, bb2;
809 FOR_EACH_BB (bb)
810 if ((bb2 = get_immediate_dominator (dom, bb)))
811 fprintf (stderr, "%i %i\n", bb->index, bb2->index);
812}