X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopyopt.c;h=d45ba4ca827ae0ac857b60c858924b521cec682a;hb=f804d333c7b5459c3c1a6bfc188ecdc54346be73;hp=e7193711868dc96969516bcc365e7f5fc57d78e3;hpb=e4a6094bd9204ada5d9d01d132478e1eb1663afe;p=libfirm diff --git a/ir/be/becopyopt.c b/ir/be/becopyopt.c index e71937118..d45ba4ca8 100644 --- a/ir/be/becopyopt.c +++ b/ir/be/becopyopt.c @@ -18,6 +18,7 @@ #include "irloop_t.h" #include "xmalloc.h" +#include "beutil.h" #include "bechordal_t.h" #include "becopyopt.h" #include "becopystat.h" @@ -26,7 +27,7 @@ static firm_dbg_module_t *dbg = NULL; #define is_curr_reg_class(irn) \ (arch_get_irn_reg_class(get_arch_env(co), \ - irn, arch_pos_make_out(0)) == co->chordal_env->cls) + irn, -1) == co->chordal_env->cls) #define MIN(a,b) ((a??? */ static int ou_max_ind_set_costs(unit_t *ou) { be_chordal_env_t *chordal_env = ou->co->chordal_env; @@ -74,84 +74,96 @@ static int ou_max_ind_set_costs(unit_t *ou) { } - - /* now brute force the best set out of the unsafe nodes*/ - curr = bitset_alloca(unsafe_count); - - bitset_set_all(curr); - while ((max = bitset_popcnt(curr)) != 0) { - /* check if curr is a stable set */ - for (i=bitset_next_set(curr, 0); i!=-1; i=bitset_next_set(curr, i+1)) - for (o=bitset_next_set(curr, i+1); o!=-1; o=bitset_next_set(curr, o+1)) /* !!!!! difference to qnode_max_ind_set(): NOT (curr, i) */ - if (nodes_interfere(chordal_env, unsafe[i], unsafe[o])) - goto no_stable_set; - - /* if we arrive here, we have a stable set */ - /* compute the weigth of the stable set*/ - curr_weight = 0; - bitset_foreach(curr, pos) - curr_weight += unsafe_costs[pos]; - - /* any better ? */ - if (curr_weight > best_weight) { - best_weight = curr_weight; + /* now compute the best set out of the unsafe nodes*/ + if (unsafe_count > MIS_HEUR_TRIGGER) { + bitset_t *best = bitset_alloca(unsafe_count); + /* Heuristik: Greedy trial and error form index 0 to unsafe_count-1 */ + for (i=0; i best_weight) { + best_weight = curr_weight; + } -no_stable_set: - bitset_minus1(curr); + no_stable_set: + bitset_minus1(curr); + } } return safe_costs+best_weight; } -/** - * Builds an optimization unit for a given optimizable irn (root). - * This opt-unit is inserted in the main structure co. - * If an arg of root itself is optimizable process this arg before with a - * recursive call. For handling this situation and loops co->root is used - * to remember all roots. - */ -static void co_append_unit(copy_opt_t *co, ir_node *root) { - int i, arity; +static void co_collect_units(ir_node *irn, void *env) { + copy_opt_t *co = env; unit_t *unit; - struct list_head *tmp; + arch_register_req_t req; - DBG((dbg, LEVEL_1, "\t Root: %n %N\n", root, root)); - /* check if we encountered this root earlier */ - if (pset_find_ptr(co->roots, root)) + if (!is_curr_reg_class(irn)) + return; + if (!is_optimizable(get_arch_env(co), irn, &req)) return; - pset_insert_ptr(co->roots, root); - - assert(is_curr_reg_class(root) && "node is in wrong register class!"); - /* init unit */ - arity = get_irn_arity(root); + /* Init a new unit */ unit = xcalloc(1, sizeof(*unit)); unit->co = co; - unit->nodes = xmalloc((arity+1) * sizeof(*unit->nodes)); - unit->costs = xmalloc((arity+1) * sizeof(*unit->costs)); unit->node_count = 1; - unit->nodes[0] = root; INIT_LIST_HEAD(&unit->queue); - /* check all args */ - if (is_Phi(root) && mode_is_datab(get_irn_mode(root))) { + /* Phi with some/all of its arguments */ + if (is_Reg_Phi(irn)) { + int i, arity; + + /* init */ + arity = get_irn_arity(irn); + unit->nodes = xmalloc((arity+1) * sizeof(*unit->nodes)); + unit->costs = xmalloc((arity+1) * sizeof(*unit->costs)); + unit->nodes[0] = irn; + + /* fill */ for (i=0; ichordal_env, root, arg)) { - unit->inevitable_costs += co->get_costs(root, arg, i); + if (nodes_interfere(co->chordal_env, irn, arg)) { + unit->inevitable_costs += co->get_costs(irn, arg, i); continue; } /* Else insert the argument of the phi to the members of this ou */ - DBG((dbg, LEVEL_1, "\t Member: %n %N\n", arg, arg)); + DBG((dbg, LEVEL_1, "\t Member: %+F\n", arg)); /* Check if arg has occurred at a prior position in the arg/list */ + arg_pos = 0; for (o=0; onode_count; ++o) if (unit->nodes[o] == arg) { arg_pos = o; @@ -161,58 +173,64 @@ static void co_append_unit(copy_opt_t *co, ir_node *root) { if (!arg_pos) { /* a new argument */ /* insert node, set costs */ unit->nodes[unit->node_count] = arg; - unit->costs[unit->node_count] = co->get_costs(root, arg, i); + unit->costs[unit->node_count] = co->get_costs(irn, arg, i); unit->node_count++; } else { /* arg has occured before in same phi */ /* increase costs for existing arg */ - unit->costs[arg_pos] += co->get_costs(root, arg, i); + unit->costs[arg_pos] += co->get_costs(irn, arg, i); } } unit->nodes = xrealloc(unit->nodes, unit->node_count * sizeof(*unit->nodes)); unit->costs = xrealloc(unit->costs, unit->node_count * sizeof(*unit->costs)); - } else if (is_Copy(get_arch_env(co), root)) { - assert(!nodes_interfere(co->chordal_env, root, get_Copy_src(root))); - unit->nodes[1] = get_Copy_src(root); - unit->costs[1] = co->get_costs(root, unit->nodes[1], -1); - unit->node_count = 2; - unit->nodes = xrealloc(unit->nodes, 2 * sizeof(*unit->nodes)); - unit->costs = xrealloc(unit->costs, 2 * sizeof(*unit->costs)); } else - assert(0 && "This is not an optimizable node!"); - /* TODO add ou's for 2-addr-code instructions */ - - /* Determine the maximum costs this unit can cause: all_nodes_cost */ - for(i=1; inode_count; ++i) { - unit->sort_key = MAX(unit->sort_key, unit->costs[i]); - unit->all_nodes_costs += unit->costs[i]; - } + /* Proj of a perm with corresponding arg */ + if (is_Perm_Proj(get_arch_env(co), irn)) { + assert(!nodes_interfere(co->chordal_env, irn, get_Copy_src(irn))); + unit->nodes = xmalloc(2 * sizeof(*unit->nodes)); + unit->costs = xmalloc(2 * sizeof(*unit->costs)); + unit->node_count = 2; + unit->nodes[0] = irn; + unit->nodes[1] = get_Copy_src(irn); + unit->costs[1] = co->get_costs(irn, unit->nodes[1], -1); + } else - /* Determine the minimal costs this unit will cause: min_nodes_costs */ - unit->min_nodes_costs += unit->all_nodes_costs - ou_max_ind_set_costs(unit); + /* Src == Tgt of a 2-addr-code instruction */ + if (is_2addr_code(get_arch_env(co), irn, &req)) { + ir_node *other = req.other; + if (!nodes_interfere(co->chordal_env, irn, other)) { + unit->nodes = xmalloc(2 * sizeof(*unit->nodes)); + unit->costs = xmalloc(2 * sizeof(*unit->costs)); + unit->node_count = 2; + unit->nodes[0] = irn; + unit->nodes[1] = other; + unit->costs[1] = co->get_costs(irn, other, -120480); + } + } else + assert(0 && "This is not an optimizable node!"); - /* Insert the new ou according to its sort_key */ - tmp = &co->units; - while (tmp->next != &co->units && list_entry_units(tmp->next)->sort_key > unit->sort_key) - tmp = tmp->next; - list_add(&unit->units, tmp); -} + /* Insert the new unit at a position according to its costs */ + if (unit->node_count > 1) { + int i; + struct list_head *tmp; -static void co_collect_in_block(ir_node *block, void *env) { - copy_opt_t *co = env; - struct list_head *head = get_block_border_head(co->chordal_env, block); - border_t *curr; + /* Determine the maximum costs this unit can cause: all_nodes_cost */ + for(i=1; inode_count; ++i) { + unit->sort_key = MAX(unit->sort_key, unit->costs[i]); + unit->all_nodes_costs += unit->costs[i]; + } - list_for_each_entry_reverse(border_t, curr, head, list) - if (curr->is_def && curr->is_real && is_optimizable(get_arch_env(co), curr->irn)) - co_append_unit(co, curr->irn); -} + /* Determine the minimal costs this unit will cause: min_nodes_costs */ + unit->min_nodes_costs += unit->all_nodes_costs - ou_max_ind_set_costs(unit); -static void co_collect_units(copy_opt_t *co) { - DBG((dbg, LEVEL_1, "\tCollecting optimization units\n")); - co->roots = pset_new_ptr(64); - dom_tree_walk_irg(get_irg(co), co_collect_in_block, NULL, co); - del_pset(co->roots); + /* Insert the new ou according to its sort_key */ + tmp = &co->units; + while (tmp->next != &co->units && list_entry_units(tmp->next)->sort_key > unit->sort_key) + tmp = tmp->next; + list_add(&unit->units, tmp); + } else { + free(unit); + } } copy_opt_t *new_copy_opt(be_chordal_env_t *chordal_env, int (*get_costs)(ir_node*, ir_node*, int)) { @@ -221,7 +239,6 @@ copy_opt_t *new_copy_opt(be_chordal_env_t *chordal_env, int (*get_costs)(ir_node copy_opt_t *co; dbg = firm_dbg_register("ir.be.copyopt"); - firm_dbg_set_mask(dbg, DEBUG_LVL_CO); co = xcalloc(1, sizeof(*co)); co->chordal_env = chordal_env; @@ -233,13 +250,10 @@ copy_opt_t *new_copy_opt(be_chordal_env_t *chordal_env, int (*get_costs)(ir_node len = strlen(s1) + strlen(s2) + strlen(s3) + 5; co->name = xmalloc(len); snprintf(co->name, len, "%s__%s__%s", s1, s2, s3); - if (!strcmp(co->name, DEBUG_IRG)) - firm_dbg_set_mask(dbg, DEBUG_IRG_LVL_CO); - else - firm_dbg_set_mask(dbg, DEBUG_LVL_CO); + DBG((dbg, LEVEL_1, "\tCollecting optimization units\n")); INIT_LIST_HEAD(&co->units); - co_collect_units(co); + irg_walk_graph(get_irg(co), co_collect_units, NULL, co); return co; } @@ -248,18 +262,28 @@ void free_copy_opt(copy_opt_t *co) { xfree(co->name); list_for_each_entry_safe(unit_t, curr, tmp, &co->units, units) { xfree(curr->nodes); + xfree(curr->costs); xfree(curr); } } int is_optimizable_arg(const copy_opt_t *co, ir_node *irn) { - int i, max; - for(i=0, max=get_irn_n_outs(irn); ichordal_env, irn, n))) - return 1; + arch_env_t *aenv = co->chordal_env->main_env->arch_env; + const ir_edge_t *edge; + + foreach_out_edge(irn, edge) { + ir_node *n = edge->src; + arch_register_req_t req; + + arch_get_register_req(aenv, &req, n, -1); + + if( ( (req.type == arch_register_req_type_should_be_same && req.other == irn) || + is_Reg_Phi(n) || + is_Perm(get_arch_env(co), n) + ) && (irn == n || !nodes_interfere(co->chordal_env, irn, n))) + return 1; } + return 0; } @@ -268,13 +292,12 @@ int get_costs_loop_depth(ir_node *root, ir_node* arg, int pos) { ir_loop *loop; ir_node *root_block = get_nodes_block(root); - assert(pos==-1 || is_Phi(root)); - if (pos == -1) { - /* a perm places the copy in the same block as it resides */ - loop = get_irn_loop(root_block); - } else { + if (is_Phi(root)) { /* for phis the copies are placed in the corresponding pred-block */ loop = get_irn_loop(get_Block_cfgpred_block(root_block, pos)); + } else { + /* a perm places the copy in the same block as it resides */ + loop = get_irn_loop(root_block); } if (loop) { int d = get_loop_depth(loop);