3 * @author Sebastian Hack, Daniel Grund
6 * Copyright: (c) Universitaet Karlsruhe
7 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
13 #include "bedomfront.h"
21 #include "iredges_t.h"
24 * The dominance frontier for a graph.
26 struct _be_dom_front_info_t {
27 pmap *df_map; /**< A map, mapping every block to a list of its dominance frontier blocks. */
28 struct obstack obst; /**< An obstack holding all the frontier data. */
32 * A wrapper for get_Block_idom.
33 * This function returns the block itself, if the block is the start
34 * block. Returning NULL would make any != comparison true which
35 * suggests, that the start block is dominated by some other node.
36 * @param bl The block.
37 * @return The immediate dominator of the block.
40 ir_node *get_idom(ir_node *bl)
42 ir_node *idom = get_Block_idom(bl);
43 return idom == NULL ? bl : idom;
47 * Compute the dominance frontier for a given block.
49 * @param blk the block where the calculation starts
51 * @return the list of all blocks in the dominance frontier of blk
54 ir_node **compute_df(ir_node *blk, be_dom_front_info_t *info)
57 const ir_edge_t *edge;
58 ir_node **df_list = NEW_ARR_F(ir_node *, 0);
62 /* Add local dominance frontiers */
63 foreach_block_succ(blk, edge) {
64 ir_node *y = get_edge_src_irn(edge);
66 if (get_idom(y) != blk) {
67 ARR_APP1(ir_node *, df_list, y);
72 * Go recursively down the dominance tree and add all blocks
73 * into the dominance frontiers of the children, which are not
74 * dominated by the given block.
76 for (c = get_Block_dominated_first(blk); c; c = get_Block_dominated_next(c)) {
78 ir_node **df_c_list = compute_df(c, info);
80 for (i = ARR_LEN(df_c_list) - 1; i >= 0; --i) {
81 ir_node *w = df_c_list[i];
82 if (get_idom(w) != blk)
83 ARR_APP1(ir_node *, df_list, w);
87 /* now copy the flexible array to the obstack */
88 len = ARR_LEN(df_list);
89 df = NEW_ARR_D(ir_node *, &info->obst, len);
90 memcpy(df, df_list, len * sizeof(df[0]));
93 pmap_insert(info->df_map, blk, df);
97 be_dom_front_info_t *be_compute_dominance_frontiers(ir_graph *irg)
99 be_dom_front_info_t *info = xmalloc(sizeof(*info));
102 obstack_init(&info->obst);
103 info->df_map = pmap_create();
105 (void)compute_df(get_irg_start_block(irg), info);
110 void be_free_dominance_frontiers(be_dom_front_info_t *info)
112 obstack_free(&info->obst, NULL);
113 pmap_destroy(info->df_map);
117 /* Get the dominance frontier of a block. */
118 ir_node **be_get_dominance_frontier(const be_dom_front_info_t *info,
121 return pmap_get(info->df_map, block);
125 * Calculates the iterated dominance frontier of a set of blocks.
126 * Also clears the link field of the returned blocks as a side effect
128 void be_get_iterated_dominance_frontiers(const be_dom_front_info_t *domfronts,
129 ir_nodeset_t *blocks)
132 ir_nodeset_iterator_t iter;
133 waitq *worklist = new_waitq();
135 foreach_ir_nodeset(blocks, block, iter) {
136 waitq_put(worklist, block);
139 while(!pdeq_empty(worklist)) {
141 ir_node *block = waitq_get(worklist);
142 ir_node **domfront = be_get_dominance_frontier(domfronts, block);
143 int domfront_len = ARR_LEN(domfront);
145 for (i = 0; i < domfront_len; ++i) {
146 ir_node *y = domfront[i];
147 if(!ir_nodeset_insert(blocks, y))
150 waitq_put(worklist, y);