2 * Copyright (C) 1995-2008 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 dominance frontiers.
23 * @author Sebastian Hack, Daniel Grund
35 #include "iredges_t.h"
36 #include "irnodeset.h"
38 #include "bedomfront.h"
41 * The dominance frontier for a graph.
43 struct _be_dom_front_info_t {
44 pmap *df_map; /**< A map, mapping every block to a list of its dominance frontier blocks. */
45 struct obstack obst; /**< An obstack holding all the frontier data. */
49 * A wrapper for get_Block_idom.
50 * This function returns the block itself, if the block is the start
51 * block. Returning NULL would make any != comparison true which
52 * suggests, that the start block is dominated by some other node.
53 * @param bl The block.
54 * @return The immediate dominator of the block.
56 static inline ir_node *get_idom(ir_node *bl)
58 ir_node *idom = get_Block_idom(bl);
59 return idom == NULL ? bl : idom;
63 * Compute the dominance frontier for a given block.
65 * @param blk the block where the calculation starts
67 * @return the list of all blocks in the dominance frontier of blk
69 static ir_node **compute_df(ir_node *blk, be_dom_front_info_t *info)
72 const ir_edge_t *edge;
73 ir_node **df_list = NEW_ARR_F(ir_node *, 0);
77 /* Add local dominance frontiers */
78 foreach_block_succ(blk, edge) {
79 ir_node *y = get_edge_src_irn(edge);
81 if (get_idom(y) != blk) {
82 ARR_APP1(ir_node *, df_list, y);
87 * Go recursively down the dominance tree and add all blocks
88 * into the dominance frontiers of the children, which are not
89 * dominated by the given block.
91 for (c = get_Block_dominated_first(blk); c; c = get_Block_dominated_next(c)) {
93 ir_node **df_c_list = compute_df(c, info);
95 for (i = ARR_LEN(df_c_list) - 1; i >= 0; --i) {
96 ir_node *w = df_c_list[i];
97 if (get_idom(w) != blk)
98 ARR_APP1(ir_node *, df_list, w);
102 /* now copy the flexible array to the obstack */
103 len = ARR_LEN(df_list);
104 df = NEW_ARR_D(ir_node *, &info->obst, len);
105 memcpy(df, df_list, len * sizeof(df[0]));
108 pmap_insert(info->df_map, blk, df);
112 be_dom_front_info_t *be_compute_dominance_frontiers(ir_graph *irg)
114 be_dom_front_info_t *info = XMALLOC(be_dom_front_info_t);
117 obstack_init(&info->obst);
118 info->df_map = pmap_create();
120 (void)compute_df(get_irg_start_block(irg), info);
125 void be_free_dominance_frontiers(be_dom_front_info_t *info)
127 obstack_free(&info->obst, NULL);
128 pmap_destroy(info->df_map);
132 /* Get the dominance frontier of a block. */
133 ir_node **be_get_dominance_frontier(const be_dom_front_info_t *info,
136 return pmap_get(info->df_map, block);