X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbeirgmod.c;h=773343f7a5de9183e42ed25f77a5157d6cbc18c5;hb=4d7a9507baf1737297cd4f7fc91eab209fd5d398;hp=60845b9f6707a0d4fa64d2cf61ee603c95bd9c5f;hpb=3283f1d16a40c2484322f52314ce65de91f72775;p=libfirm diff --git a/ir/be/beirgmod.c b/ir/be/beirgmod.c index 60845b9f6..773343f7a 100644 --- a/ir/be/beirgmod.c +++ b/ir/be/beirgmod.c @@ -98,6 +98,7 @@ dom_front_info_t *be_compute_dominance_frontiers(ir_graph *irg) edges_assure(irg); info->df_map = pmap_create(); + compute_doms(irg); compute_df(get_irg_start_block(irg), info->df_map); return info; @@ -119,52 +120,48 @@ pset *be_get_dominance_frontier(dom_front_info_t *info, ir_node *block) return pmap_get(info->df_map, block); } -static void determine_phi_blocks(ir_node *orig, pset *copies, - pset *copy_blocks, pset *phi_blocks, dom_front_info_t *df_info) +static void determine_phi_blocks(pset *copies, pset* copy_blocks, pset *phi_blocks, dom_front_info_t *df_info) { ir_node *bl; - ir_node *orig_block = get_nodes_block(orig); - pdeq *worklist = new_pdeq(); - firm_dbg_module_t *dbg = DBG_MODULE; - - /* - * Fill the worklist queue and the rest of the orig blocks array. - */ - for(bl = pset_first(copy_blocks); bl; bl = pset_next(copy_blocks)) { - assert(block_dominates(orig_block, bl) - && "The block of the copy must be dominated by the block of the value"); + pdeq *worklist = new_pdeq(); + firm_dbg_module_t *dbg = DBG_MODULE; + + /* + * Fill the worklist queue and the rest of the orig blocks array. + */ + for(bl = pset_first(copy_blocks); bl; bl = pset_next(copy_blocks)) { + pdeq_putr(worklist, bl); + } - pdeq_putr(worklist, bl); - } + while(!pdeq_empty(worklist)) { + ir_node *bl = pdeq_getl(worklist); + pset *df = be_get_dominance_frontier(df_info, bl); - while(!pdeq_empty(worklist)) { - ir_node *bl = pdeq_getl(worklist); - ir_node *y; - pset *df = be_get_dominance_frontier(df_info, bl); + ir_node *y; - DBG((dbg, LEVEL_3, "dom front of %+F\n", bl)); - for(y = pset_first(df); y; y = pset_next(df)) - DBG((dbg, LEVEL_3, "\t%+F\n", y)); + DBG((dbg, LEVEL_3, "dom front of %+F\n", bl)); + for(y = pset_first(df); y; y = pset_next(df)) + DBG((dbg, LEVEL_3, "\t%+F\n", y)); - for(y = pset_first(df); y; y = pset_next(df)) { - if(!pset_find_ptr(phi_blocks, y)) { - pset_insert_ptr(phi_blocks, y); + for(y = pset_first(df); y; y = pset_next(df)) { + if(!pset_find_ptr(phi_blocks, y)) { + pset_insert_ptr(phi_blocks, y); /* - * Clear the link field of a possible phi block, since - * the possibly created phi will be stored there. See, - * search_def() - */ + * Clear the link field of a possible phi block, since + * the possibly created phi will be stored there. See, + * search_def() + */ set_irn_link(y, NULL); if(!pset_find_ptr(copy_blocks, y)) pdeq_putr(worklist, y); - } - } - } + } + } + } - del_pdeq(worklist); + del_pdeq(worklist); } /** @@ -178,58 +175,56 @@ static void determine_phi_blocks(ir_node *orig, pset *copies, * traversing from the predecessor block which corresponds to the phi * usage. * - * @param usage The node which uses the original node. - * @param pos The number of the argument which corresponds to the - * original node. - * @param copy_blocks A set containing all basic block in which copies - * of the original node are located. - * @param copies A set containing all node which are copies from the - * original node. - * @return The valid copy for usage. + * @param usage The node which uses the original node. + * @param pos The position of the argument which corresponds to the original node. + * @param copies A set containing all node which are copies from the original node. + * @param copy_blocks A set containing all basic block in which copies of the original node are located. + * @param phis A set where all created phis are recorded. + * @param phi_blocks A set of all blocks where Phis shall be inserted (iterated dominance frontier). + * @param mode The mode for the Phi if one has to be created. + * @return The valid copy for usage. */ -static ir_node *search_def(ir_node *usage, int pos, pset *copies, - pset *copy_blocks, pset *phi_blocks, ir_mode *mode) +static ir_node *search_def(ir_node *usage, int pos, pset *copies, pset *copy_blocks, pset *phis, pset *phi_blocks, ir_mode *mode) { - ir_node *curr_bl; - ir_node *start_irn; - firm_dbg_module_t *dbg = DBG_MODULE; - - curr_bl = get_nodes_block(usage); + ir_node *curr_bl; + ir_node *start_irn; + firm_dbg_module_t *dbg = DBG_MODULE; + + curr_bl = get_nodes_block(usage); + + DBG((dbg, LEVEL_1, "Searching valid def for use %+F at pos %d\n", usage, pos)); + /* + * If the usage is in a phi node, search the copy in the + * predecessor denoted by pos. + */ + if(is_Phi(usage)) { + curr_bl = get_Block_cfgpred_block(curr_bl, pos); + start_irn = sched_last(curr_bl); + } else { + start_irn = sched_prev(usage); + } + /* + * Traverse the dominance tree upwards from the + * predecessor block of the usage. + */ + while(curr_bl != NULL) { - DBG((dbg, LEVEL_1, "Searching valid def for use %+F at pos %d\n", usage, pos)); - /* - * If the usage is in a phi node, search the copy in the - * predecessor denoted by pos. - */ - if(is_Phi(usage)) { - curr_bl = get_Block_cfgpred_block(curr_bl, pos); - start_irn = sched_last(curr_bl); - } else { - start_irn = sched_prev(usage); - } + /* + * If this block contains a copy, search the block + * instruction by instruction. + */ + if(pset_find_ptr(copy_blocks, curr_bl)) { + ir_node *irn; - /* - * Traverse the dominance tree upwards from the - * predecessor block of the usage. - */ - while(curr_bl != NULL) { - - /* - * If this block contains a copy, search the block - * instruction by instruction. - */ - if(pset_find_ptr(copy_blocks, curr_bl)) { - ir_node *irn; - - /* Look at each instruction from last to first. */ + /* Look at each instruction from last to first. */ sched_foreach_reverse_from(start_irn, irn) { - /* Take the first copy we find. */ - if(pset_find_ptr(copies, irn)) - return irn; - } - } + /* Take the first copy we find. */ + if(pset_find_ptr(copies, irn)) + return irn; + } + } if(pset_find_ptr(phi_blocks, curr_bl)) { ir_node *phi = get_irn_link(curr_bl); @@ -237,7 +232,7 @@ static ir_node *search_def(ir_node *usage, int pos, pset *copies, if(!phi) { int i, n_preds = get_irn_arity(curr_bl); ir_graph *irg = get_irn_irg(curr_bl); - ir_node **ins = malloc(n_preds * sizeof(ins[0])); + ir_node **ins = xmalloc(n_preds * sizeof(ins[0])); for(i = 0; i < n_preds; ++i) ins[i] = new_r_Unknown(irg, mode); @@ -250,77 +245,84 @@ static ir_node *search_def(ir_node *usage, int pos, pset *copies, free(ins); for(i = 0; i < n_preds; ++i) { - ir_node *arg = search_def(phi, i, copies, copy_blocks, phi_blocks, mode); + ir_node *arg = search_def(phi, i, copies, copy_blocks, phis, phi_blocks, mode); DBG((dbg, LEVEL_2, "\t\t%+F(%d) -> %+F\n", phi, i, arg)); set_irn_n(phi, i, arg); } + + if(phis) + pset_insert_ptr(phis, phi); } return phi; } - /* If were not done yet, look in the immediate dominator */ - curr_bl = get_Block_idom(curr_bl); - if(curr_bl) - start_irn = sched_last(curr_bl); - } + /* If were not done yet, look in the immediate dominator */ + curr_bl = get_Block_idom(curr_bl); + if(curr_bl) + start_irn = sched_last(curr_bl); + } - return NULL; + return NULL; } -static void fix_usages(ir_node *orig, pset *copies, pset *copy_blocks, - pset *phi_blocks, pset *ignore_uses) +static void fix_usages(pset *copies, pset *copy_blocks, pset *phi_blocks, pset *phis, pset *ignore_uses) { - int i = 0; - int n_outs = 0; - const ir_edge_t *edge; - ir_mode *mode = get_irn_mode(orig); - - firm_dbg_module_t *dbg = DBG_MODULE; - - struct { - ir_node *irn; - int pos; - } *outs; - - /* Count the number of outs. */ - foreach_out_edge(orig, edge) - n_outs += !pset_find_ptr(ignore_uses, get_edge_src_irn(edge)); - - /* - * Put all outs into an array. - * This is neccessary, since the outs would be modified while - * interating on them what could bring the outs module in trouble. - */ - outs = malloc(n_outs * sizeof(outs[0])); - foreach_out_edge(orig, edge) { - if(!pset_find_ptr(ignore_uses, get_edge_src_irn(edge))) { - outs[i].irn = get_edge_src_irn(edge); - outs[i].pos = get_edge_src_pos(edge); - i += 1; + firm_dbg_module_t *dbg = DBG_MODULE; + int n_outs = 0; + + struct obstack obst; + ir_node *irn; + int i; + + struct out { + ir_node *irn; + int pos; + } *outs; + + obstack_init(&obst); + + /* + * Put all outs into an array. + * This is necessary, since the outs would be modified while + * iterating on them what could bring the outs module in trouble. + */ + for(irn = pset_first(copies); irn; irn = pset_next(copies)) { + const ir_edge_t *edge; + foreach_out_edge(irn, edge) { + if(!pset_find_ptr(ignore_uses, get_edge_src_irn(edge))) { + struct out tmp; + tmp.irn = get_edge_src_irn(edge); + tmp.pos = get_edge_src_pos(edge); + obstack_grow(&obst, &tmp, sizeof(tmp)); + n_outs++; + } } - } + } + outs = obstack_finish(&obst); - /* - * Search the valid def for each out and set it. - */ - for(i = 0; i < n_outs; ++i) { - ir_node *def; - ir_node *irn = outs[i].irn; - int pos = outs[i].pos; + /* + * Search the valid def for each out and set it. + */ + for(i = 0; i < n_outs; ++i) { + ir_node *irn = outs[i].irn; + int pos = outs[i].pos; + ir_mode *mode = get_irn_mode(get_irn_n(irn, pos)); - def = search_def(irn, pos, copies, copy_blocks, phi_blocks, mode); - DBG((dbg, LEVEL_2, "\t%+F(%d) -> %+F\n", irn, pos, def)); + ir_node *def; - if(def != NULL) - set_irn_n(irn, pos, def); - } + def = search_def(irn, pos, copies, copy_blocks, phis, phi_blocks, mode); + DBG((dbg, LEVEL_2, "\t%+F(%d) -> %+F\n", irn, pos, def)); + + if(def != NULL) + set_irn_n(irn, pos, def); + } - free(outs); + obstack_free(&obst, NULL); } /** - * Remove phis which are not neccesary. + * Remove phis which are not necessary. * During place_phi_functions() phi functions are put on the dominance * frontiers blindly. However some of them will never be used (these * have at least one predecessor which is NULL, see search_def() for @@ -352,103 +354,88 @@ static void remove_odd_phis(pset *copies, pset *unused_copies) } } -void be_introduce_copies_ignore(dom_front_info_t *info, ir_node *orig, - int n, ir_node *copy_nodes[], pset *ignore_uses) +void be_ssa_constr_phis_ignore(dom_front_info_t *info, int n, ir_node *nodes[], pset *phis, pset *ignore_uses) { - pset *copies = pset_new_ptr(2 * n); - pset *copy_blocks = pset_new_ptr(2 * n); - pset *phi_blocks = pset_new_ptr(2 * n); - int save_optimize = get_optimize(); - int save_normalize = get_opt_normalize(); - firm_dbg_module_t *dbg = DBG_MODULE; - int i; - -#if 0 - { - static int ser = 0; - char buf[128]; - - snprintf(buf, sizeof(buf), "-post-%d", ser++); - dump_ir_block_graph_sched(get_irn_irg(orig), buf); - } -#endif + pset *irns = pset_new_ptr(n); + int i; - firm_dbg_set_mask(dbg, DBG_LEVEL); - DBG((dbg, LEVEL_1, "Introducing following copies of %+F\n", orig)); + for(i = 0; i < n; ++i) + pset_insert_ptr(irns, nodes[i]); + be_ssa_constr_set_phis_ignore(info, irns, phis, ignore_uses); + del_pset(irns); +} - /* Fill the sets. */ - pset_insert_ptr(copies, orig); - pset_insert_ptr(copy_blocks, get_nodes_block(orig)); +void be_ssa_constr_ignore(dom_front_info_t *info, int n, ir_node *nodes[], pset *ignore_uses) +{ + be_ssa_constr_phis_ignore(info, n, nodes, NULL, ignore_uses); +} - /* - * All phis using the original value are also copies of it - * and must be present in the copies set. - */ - for(i = 0; i < n; ++i) { - DBG((dbg, LEVEL_1, - " %+F in block %+F\n", copy_nodes[i], get_nodes_block(copy_nodes[i]))); - pset_insert_ptr(copies, copy_nodes[i]); - pset_insert_ptr(copy_blocks, get_nodes_block(copy_nodes[i])); - } +void be_ssa_constr(dom_front_info_t *info, int n, ir_node *nodes[]) +{ + pset *empty_set = be_empty_set(); + assert(pset_count(empty_set) == 0); + be_ssa_constr_ignore(info, n, nodes, empty_set); +} - /* - * Disable optimization so that the phi functions do not - * disappear. - */ - set_optimize(0); - set_opt_normalize(0); +void be_ssa_constr_set_phis_ignore(dom_front_info_t *df, pset *nodes, pset *phis, pset *ignore_uses) +{ + int n = pset_count(nodes); + pset *blocks = pset_new_ptr(n); + pset *phi_blocks = pset_new_ptr(n); + int save_optimize = get_optimize(); + int save_normalize = get_opt_normalize(); + firm_dbg_module_t *dbg = DBG_MODULE; + + ir_node *irn; + + firm_dbg_set_mask(dbg, DBG_LEVEL); + DBG((dbg, LEVEL_1, "Introducing following copies for:\n")); + + /* Fill the sets. */ + for(irn = pset_first(nodes); irn; irn = pset_next(nodes)) { + ir_node *bl = get_nodes_block(irn); + pset_insert_ptr(blocks, bl); + DBG((dbg, LEVEL_1, "\t%+F in %+F\n", irn, bl)); + } - /* - * Place the phi functions and reroute the usages. - */ - determine_phi_blocks(orig, copies, copy_blocks, phi_blocks, info); - fix_usages(orig, copies, copy_blocks, phi_blocks, ignore_uses); + /* + * Disable optimization so that the phi functions do not + * disappear. + */ + set_optimize(0); + set_opt_normalize(0); - /* reset the optimizations */ - set_optimize(save_optimize); - set_opt_normalize(save_normalize); + /* + * Place the phi functions and reroute the usages. + */ + determine_phi_blocks(nodes, blocks, phi_blocks, df); + fix_usages(nodes, blocks, phi_blocks, phis, ignore_uses); - del_pset(copies); - del_pset(phi_blocks); - del_pset(copy_blocks); + /* reset the optimizations */ + set_optimize(save_optimize); + set_opt_normalize(save_normalize); + del_pset(phi_blocks); + del_pset(blocks); } -void be_introduce_copies(dom_front_info_t *info, ir_node *orig, int n, ir_node *copy_nodes[]) +void be_ssa_constr_set_phis(dom_front_info_t *df, pset *nodes, pset *phis) { - static pset *empty_set = NULL; - - if(!empty_set) - empty_set = pset_new_ptr_default(); + pset *empty_set = be_empty_set(); + assert(pset_count(empty_set) == 0); - be_introduce_copies_ignore(info, orig, n, copy_nodes, empty_set); + be_ssa_constr_set_phis_ignore(df, nodes,phis, empty_set); } -void be_introduce_copies_for_set(dom_front_info_t *info, pset *origs, pset *copies) { - /* TODO */ - assert(0 && "NYI); - exit(0xDeadBeef); +void be_ssa_constr_set_ignore(dom_front_info_t *df, pset *nodes, pset *ignore_uses) +{ + be_ssa_constr_set_phis_ignore(df, nodes, NULL, ignore_uses); } - -void be_introduce_copies_pset(dom_front_info_t *info, pset *nodes) { - int i, n = pset_count(nodes); - ir_node *orig, *irn, **copy_nodes; - static pset *empty_set = NULL; - - if (n<2) - return; - - copy_nodes = alloca((n-1)*sizeof(*copy_nodes)); - irn = pset_first(nodes); - orig = irn; - for (i=0, irn = pset_next(nodes); irn; irn=pset_next(nodes)) - copy_nodes[i++] = irn; - - - if(!empty_set) - empty_set = pset_new_ptr_default(); - - be_introduce_copies_ignore(info, orig, n-1, copy_nodes, empty_set); +void be_ssa_constr_set(dom_front_info_t *info, pset *nodes) +{ + pset *empty_set = be_empty_set(); + assert(pset_count(empty_set) == 0); + be_ssa_constr_set_ignore(info, nodes, empty_set); }