-#define DBG_MODULE firm_dbg_register("firm.be.irgmod")
-
-struct _dom_front_info_t {
- pmap *df_map;
-};
-
-/**
- * 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;
-}
-
-static void compute_df_local(ir_node *bl, void *data)
-{
- pmap *df_map = ((dom_front_info_t *) data)->df_map;
- ir_node *idom = get_Block_idom(bl);
- pset *df = pmap_get(df_map, bl);
- int i, n;
-
- /*
- * In the case that the immediate dominator is NULL, the
- * block is the start block and its immediate dominator
- * must be itself, else it is inserted into its own
- * dominance frontier.
- */
- if(idom == NULL)
- idom = bl;
-
- /*
- * Create a new dom frot set for this node,
- * if none exists.
- */
- if(!df)
- pmap_insert(df_map, bl, pset_new_ptr(16));
-
- for(i = 0, n = get_irn_arity(bl); i < n; ++i) {
-
- /* The predecessor block */
- ir_node *pred = get_nodes_block(get_irn_n(bl, i));
-
- /* The dominance frontier set of the predecessor. */
- pset *df = pmap_get(df_map, pred);
- if(!df) {
- df = pset_new_ptr(16);
- pmap_insert(df_map, pred, df);
- }
-
- assert(df && "dom front set must have been created for this node");
-
- if(pred != idom && bl)
- pset_insert_ptr(df, bl);
- }
-}
-
-static void compute_df_up(ir_node *bl, void *data)
-{
- pmap *df_map = ((dom_front_info_t *) data)->df_map;
- ir_node *y;
-
- for(y = get_Block_dominated_first(bl); y; y = get_Block_dominated_next(y)) {
- ir_node *w;
- pset *df = pmap_get(df_map, y);
-
- for(w = pset_first(df); w; w = pset_next(df))
- if(!block_dominates(bl, w) || bl == w)
- pset_insert_ptr(df, w);
- }
-}
-
-static void compute_df(ir_node *n, pmap *df_map)
-{
- ir_node *y, *c;
- const ir_edge_t *edge;
- pset *df = pset_new_ptr_default();
-
- /* Add local dominance frontiers */
- foreach_block_succ(n, edge) {
- ir_node *y = edge->src;
-
- if(get_idom(y) != n)
- pset_insert_ptr(df, y);
- }
-
- /*
- * Go recursively down the dominance tree and add all blocks
- * int the dominance frontiers of the children, which are not
- * dominated by the given block.
- */
- for(c = get_Block_dominated_first(n); c; c = get_Block_dominated_next(c)) {
- pset *df_c;
- ir_node *w;
-
- compute_df(c, df_map);
- df_c = pmap_get(df_map, c);
-
- for(w = pset_first(df_c); w; w = pset_next(df_c)) {
- if(!block_dominates(n, w))
- pset_insert_ptr(df, w);
- }
- }
-
- pmap_insert(df_map, n, df);
-
-}
-
-dom_front_info_t *be_compute_dominance_frontiers(ir_graph *irg)
-{
- dom_front_info_t *info = malloc(sizeof(*info));
-
- edges_assure(irg);
- info->df_map = pmap_create();
- compute_df(get_irg_start_block(irg), info->df_map);
-
-#if 0
- /*
- * This must be called as a post walker, since the dom front sets
- * of all predecessors must be created when a block is reached.
- */
- dom_tree_walk_irg(irg, NULL, compute_df_local, info);
- dom_tree_walk_irg(irg, NULL, compute_df_up, info);
-#endif
- return info;
-}
-
-void be_free_dominance_frontiers(dom_front_info_t *info)
-{
- pmap_entry *ent;