-#define DBG_MODULE "firm.be.irgmod"
-#define DBG_LEVEL SET_LEVEL_0
-
-/*
- ____ _
- | _ \ ___ _ __ ___ (_)_ __ __ _ _ __ ___ ___
- | | | |/ _ \| '_ ` _ \| | '_ \ / _` | '_ \ / __/ _ \
- | |_| | (_) | | | | | | | | | | (_| | | | | (_| __/
- |____/ \___/|_| |_| |_|_|_| |_|\__,_|_| |_|\___\___|
- | ___| __ ___ _ __ | |_(_) ___ _ __ ___
- | |_ | '__/ _ \| '_ \| __| |/ _ \ '__/ __|
- | _|| | | (_) | | | | |_| | __/ | \__ \
- |_| |_| \___/|_| |_|\__|_|\___|_| |___/
-
-*/
-
-/**
- * The dominance frontier for a graph.
- */
-struct _be_dom_front_info_t {
- pmap *df_map; /**< A map, mapping every block to a list of its dominance frontier blocks. */
- struct obstack obst; /**< An obstack holding all the frontier data. */
-};
-
-/**
- * A wrapper for get_Block_idom.
- * This function returns the block itself, if the block is the start
- * block. Returning NULL would make any != comparison true which
- * suggests, that the start block is dominated by some other node.
- * @param bl The block.
- * @return The immediate dominator of the block.
- */
-static INLINE ir_node *get_idom(ir_node *bl)
-{
- ir_node *idom = get_Block_idom(bl);
- return idom == NULL ? bl : idom;
-}
-
-/**
- * Compute the dominance frontier for a given block.
- *
- * @param blk the block where the calculation starts
- *
- * @return the list of all blocks in the dominance frontier of blk
- */
-static ir_node **compute_df(ir_node *blk, be_dom_front_info_t *info)
-{
- ir_node *c;
- const ir_edge_t *edge;
- ir_node **df_list = NEW_ARR_F(ir_node *, 0);
- ir_node **df;
- int len;
-
- /* Add local dominance frontiers */
- foreach_block_succ(blk, edge) {
- ir_node *y = edge->src;
-
- if (get_idom(y) != blk) {
- ARR_APP1(ir_node *, df_list, y);
- }
- }
-
- /*
- * Go recursively down the dominance tree and add all blocks
- * into the dominance frontiers of the children, which are not
- * dominated by the given block.
- */
- for (c = get_Block_dominated_first(blk); c; c = get_Block_dominated_next(c)) {
- int i;
- ir_node **df_c_list = compute_df(c, info);
-
- for (i = ARR_LEN(df_c_list) - 1; i >= 0; --i) {
- ir_node *w = df_c_list[i];
- if (get_idom(w) != blk)
- ARR_APP1(ir_node *, df_list, w);
- }
- }
-
- /* now copy the flexible array to the obstack */
- len = ARR_LEN(df_list);
- df = NEW_ARR_D(ir_node *, &info->obst, len);
- memcpy(df, df_list, len * sizeof(df[0]));
- DEL_ARR_F(df_list);
-
- pmap_insert(info->df_map, blk, df);
- return df;
-}
-
-be_dom_front_info_t *be_compute_dominance_frontiers(ir_graph *irg)
-{
- be_dom_front_info_t *info = xmalloc(sizeof(*info));
-
- edges_assure(irg);
- obstack_init(&info->obst);
- info->df_map = pmap_create();
- assure_doms(irg);
- (void)compute_df(get_irg_start_block(irg), info);
-
- return info;
-}
-
-void be_free_dominance_frontiers(be_dom_front_info_t *info)
-{
- obstack_free(&info->obst, NULL);
- pmap_destroy(info->df_map);
- free(info);
-}
-
-/* Get the dominance frontier of a block. */
-ir_node **be_get_dominance_frontier(be_dom_front_info_t *info, ir_node *block)
-{
- return pmap_get(info->df_map, block);
-}