2 * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Algorithms for computing normal and iterated dominance frontiers.
23 * @author Sebastian Hack, Daniel Grund
37 #include "iredges_t.h"
38 #include "irnodeset.h"
40 #include "bedomfront.h"
43 * The dominance frontier for a graph.
45 struct _be_dom_front_info_t {
46 pmap *df_map; /**< A map, mapping every block to a list of its dominance frontier blocks. */
47 struct obstack obst; /**< An obstack holding all the frontier data. */
51 * A wrapper for get_Block_idom.
52 * This function returns the block itself, if the block is the start
53 * block. Returning NULL would make any != comparison true which
54 * suggests, that the start block is dominated by some other node.
55 * @param bl The block.
56 * @return The immediate dominator of the block.
59 ir_node *get_idom(ir_node *bl)
61 ir_node *idom = get_Block_idom(bl);
62 return idom == NULL ? bl : idom;
66 * Compute the dominance frontier for a given block.
68 * @param blk the block where the calculation starts
70 * @return the list of all blocks in the dominance frontier of blk
73 ir_node **compute_df(ir_node *blk, be_dom_front_info_t *info)
76 const ir_edge_t *edge;
77 ir_node **df_list = NEW_ARR_F(ir_node *, 0);
81 /* Add local dominance frontiers */
82 foreach_block_succ(blk, edge) {
83 ir_node *y = get_edge_src_irn(edge);
85 if (get_idom(y) != blk) {
86 ARR_APP1(ir_node *, df_list, y);
91 * Go recursively down the dominance tree and add all blocks
92 * into the dominance frontiers of the children, which are not
93 * dominated by the given block.
95 for (c = get_Block_dominated_first(blk); c; c = get_Block_dominated_next(c)) {
97 ir_node **df_c_list = compute_df(c, info);
99 for (i = ARR_LEN(df_c_list) - 1; i >= 0; --i) {
100 ir_node *w = df_c_list[i];
101 if (get_idom(w) != blk)
102 ARR_APP1(ir_node *, df_list, w);
106 /* now copy the flexible array to the obstack */
107 len = ARR_LEN(df_list);
108 df = NEW_ARR_D(ir_node *, &info->obst, len);
109 memcpy(df, df_list, len * sizeof(df[0]));
112 pmap_insert(info->df_map, blk, df);
116 be_dom_front_info_t *be_compute_dominance_frontiers(ir_graph *irg)
118 be_dom_front_info_t *info = xmalloc(sizeof(*info));
121 obstack_init(&info->obst);
122 info->df_map = pmap_create();
124 (void)compute_df(get_irg_start_block(irg), info);
129 void be_free_dominance_frontiers(be_dom_front_info_t *info)
131 obstack_free(&info->obst, NULL);
132 pmap_destroy(info->df_map);
136 /* Get the dominance frontier of a block. */
137 ir_node **be_get_dominance_frontier(const be_dom_front_info_t *info,
140 return pmap_get(info->df_map, block);
144 * Calculates the iterated dominance frontier of a set of blocks.
145 * Also clears the link field of the returned blocks as a side effect
147 void be_get_iterated_dominance_frontiers(const be_dom_front_info_t *domfronts,
148 ir_nodeset_t *blocks)
151 ir_nodeset_iterator_t iter;
152 waitq *worklist = new_waitq();
154 foreach_ir_nodeset(blocks, block, iter) {
155 waitq_put(worklist, block);
158 while(! pdeq_empty(worklist)) {
160 ir_node *block = waitq_get(worklist);
161 ir_node **domfront = be_get_dominance_frontier(domfronts, block);
162 int domfront_len = ARR_LEN(domfront);
164 for (i = 0; i < domfront_len; ++i) {
165 ir_node *y = domfront[i];
166 if(!ir_nodeset_insert(blocks, y))
169 waitq_put(worklist, y);