X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopyopt.c;h=8b0f6d000282c7e20bb6fb22fce923370fe61552;hb=8544304305897e5f2b5752fc243fd45c4f95a38c;hp=0118ae9b79e5bdd663cc8abbd80b5c5a9ecbac06;hpb=72b961b5b05ac239435b379ef340154c64134e25;p=libfirm diff --git a/ir/be/becopyopt.c b/ir/be/becopyopt.c index 0118ae9b7..8b0f6d000 100644 --- a/ir/be/becopyopt.c +++ b/ir/be/becopyopt.c @@ -14,31 +14,157 @@ #include #endif +#include "xmalloc.h" +#include "debug.h" +#include "pmap.h" +#include "irgraph.h" +#include "irgwalk.h" #include "irprog.h" #include "irloop_t.h" +#include "iredges_t.h" +#include "phiclass.h" -#include "xmalloc.h" -#include "bechordal_t.h" -#include "becopyopt.h" +#include "bearch.h" +#include "beutil.h" +#include "beifg_t.h" +#include "becopyopt_t.h" #include "becopystat.h" -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) +#undef QUICK_AND_DIRTY_HACK -#define MIN(a,b) ((acenv = chordal_env; + co->aenv = chordal_env->birg->main_env->arch_env; + co->irg = chordal_env->irg; + co->cls = chordal_env->cls; + co->get_costs = get_costs; + + s1 = get_irp_prog_name(); + s2 = get_entity_name(get_irg_entity(co->irg)); + s3 = chordal_env->cls->name; + len = strlen(s1) + strlen(s2) + strlen(s3) + 5; + co->name = xmalloc(len); + snprintf(co->name, len, "%s__%s__%s", s1, s2, s3); + + return co; +} + +void free_copy_opt(copy_opt_t *co) { + xfree(co->name); + free(co); +} + +int co_is_optimizable_root(const copy_opt_t *co, ir_node *irn) { + arch_register_req_t req; + const arch_register_t *reg; + + if (arch_irn_is(co->aenv, irn, ignore)) + return 0; + + reg = arch_get_irn_register(co->aenv, irn); + if (arch_register_type_is(reg, ignore)) + return 0; + + if (is_Reg_Phi(irn) || is_Perm_Proj(co->aenv, irn) || is_2addr_code(co->aenv, irn, &req)) + return 1; + + return 0; +} + +int co_is_optimizable_arg(const copy_opt_t *co, ir_node *irn) { + const ir_edge_t *edge; + const arch_register_t *reg; + + assert(0 && "Is buggy and obsolete. Do not use"); + + if (arch_irn_is(co->aenv, irn, ignore)) + return 0; + + reg = arch_get_irn_register(co->aenv, irn); + if (arch_register_type_is(reg, ignore)) + return 0; + + foreach_out_edge(irn, edge) { + ir_node *n = edge->src; + + if (!nodes_interfere(co->cenv, irn, n) || irn == n) { + arch_register_req_t req; + arch_get_register_req(co->aenv, &req, n, -1); + + if(is_Reg_Phi(n) || + is_Perm(co->aenv, n) || + (arch_register_req_is(&req, should_be_same) && req.other_same == irn) + ) + return 1; + } + } + + return 0; +} + +int co_get_costs_loop_depth(ir_node *root, ir_node* arg, int pos) { + int cost = 0; + ir_loop *loop; + ir_node *root_block = get_nodes_block(root); + + 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); + cost = d*d; + } + return cost+1; +} + +int co_get_costs_all_one(ir_node *root, ir_node* arg, int pos) { + return 1; +} + +/****************************************************************************** + ____ _ _ _ _ _ _____ _ + / __ \ | | | | | | (_) | / ____| | + | | | |_ __ | |_| | | |_ __ _| |_ ___ | (___ | |_ ___ _ __ __ _ __ _ ___ + | | | | '_ \| __| | | | '_ \| | __/ __| \___ \| __/ _ \| '__/ _` |/ _` |/ _ \ + | |__| | |_) | |_| |__| | | | | | |_\__ \ ____) | || (_) | | | (_| | (_| | __/ + \____/| .__/ \__|\____/|_| |_|_|\__|___/ |_____/ \__\___/|_| \__,_|\__, |\___| + | | __/ | + |_| |___/ + ******************************************************************************/ /** * Determines a maximum weighted independent set with respect to * the interference and conflict edges of all nodes in a qnode. - * TODO: This runs in n! in worst case. Use a heuristic iff n>??? */ static int ou_max_ind_set_costs(unit_t *ou) { - be_chordal_env_t *chordal_env = ou->co->chordal_env; + be_chordal_env_t *chordal_env = ou->co->cenv; ir_node **safe, **unsafe; int i, o, safe_count, safe_costs, unsafe_count, *unsafe_costs; bitset_t *curr; @@ -74,84 +200,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(co, irn)) + return; + if (!co_is_optimizable_root(co, irn)) 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->cenv, 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,136 +299,176 @@ 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); + } else + + /* Proj of a perm with corresponding arg */ + if (is_Perm_Proj(co->aenv, irn)) { + assert(!nodes_interfere(co->cenv, irn, get_Perm_src(irn))); + unit->nodes = xmalloc(2 * sizeof(*unit->nodes)); + unit->costs = xmalloc(2 * sizeof(*unit->costs)); unit->node_count = 2; - unit->nodes = xrealloc(unit->nodes, 2 * sizeof(*unit->nodes)); - unit->costs = xrealloc(unit->costs, 2 * sizeof(*unit->costs)); + unit->nodes[0] = irn; + unit->nodes[1] = get_Perm_src(irn); + unit->costs[1] = co->get_costs(irn, unit->nodes[1], -1); + } else + + /* Src == Tgt of a 2-addr-code instruction */ + if (is_2addr_code(co->aenv, irn, &req)) { + ir_node *other = req.other_same; + if (!nodes_interfere(co->cenv, 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, -1); + } } else assert(0 && "This is not an optimizable node!"); - /* TODO add ou's for 2-addr-code instructions */ + /* Insert the new unit at a position according to its costs */ + if (unit->node_count > 1) { + int i; + struct list_head *tmp; - /* 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]; + /* 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]; + } + + /* 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); + /* 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); } +} - /* 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); +#ifdef QUICK_AND_DIRTY_HACK + +static int compare_ous(const void *k1, const void *k2) { + const unit_t *u1 = *((const unit_t **) k1); + const unit_t *u2 = *((const unit_t **) k2); + int i, o, u1_has_constr, u2_has_constr; + arch_register_req_t req; + const arch_env_t *aenv = u1->co->aenv; + + /* Units with constraints come first */ + u1_has_constr = 0; + for (i=0; inode_count; ++i) { + arch_get_register_req(aenv, &req, u1->nodes[i], -1); + if (arch_register_req_is(&req, limited)) { + u1_has_constr = 1; + break; + } + } - /* 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); -} + u2_has_constr = 0; + for (i=0; inode_count; ++i) { + arch_get_register_req(aenv, &req, u2->nodes[i], -1); + if (arch_register_req_is(&req, limited)) { + u2_has_constr = 1; + break; + } + } -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; + if (u1_has_constr != u2_has_constr) + return u2_has_constr - u1_has_constr; - 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); -} + /* Now check, whether the two units are connected */ +#if 0 + for (i=0; inode_count; ++i) + for (o=0; onode_count; ++o) + if (u1->nodes[i] == u2->nodes[o]) + return 0; +#endif + + /* After all, the sort key decides. Greater keys come first. */ + return u2->sort_key - u1->sort_key; -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); } -copy_opt_t *new_copy_opt(be_chordal_env_t *chordal_env, int (*get_costs)(ir_node*, ir_node*, int)) { - const char *s1, *s2, *s3; - int len; - copy_opt_t *co; +/** + * Sort the ou's according to constraints and their sort_key + */ +static void co_sort_units(copy_opt_t *co) { + int i, count = 0, costs; + unit_t *ou, **ous; - dbg = firm_dbg_register("ir.be.copyopt"); - firm_dbg_set_mask(dbg, DEBUG_LVL_CO); + /* get the number of ous, remove them form the list and fill the array */ + list_for_each_entry(unit_t, ou, &co->units, units) + count++; + ous = alloca(count * sizeof(*ous)); - co = xcalloc(1, sizeof(*co)); - co->chordal_env = chordal_env; - co->get_costs = get_costs; + costs = co_get_max_copy_costs(co); - s1 = get_irp_prog_name(); - s2 = get_entity_name(get_irg_entity(get_irg(co))); - s3 = chordal_env->cls->name; - 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); + i = 0; + list_for_each_entry(unit_t, ou, &co->units, units) + ous[i++] = ou; INIT_LIST_HEAD(&co->units); - co_collect_units(co); - return co; + + assert(count == i && list_empty(&co->units)); + + for (i=0; inodes[0]); + + qsort(ous, count, sizeof(*ous), compare_ous); + + ir_printf("\n\n"); + for (i=0; inodes[0]); + + /* reinsert into list in correct order */ + for (i=0; iunits, &co->units); + + assert(costs == co_get_max_copy_costs(co)); } +#endif -void free_copy_opt(copy_opt_t *co) { +void co_build_ou_structure(copy_opt_t *co) { + DBG((dbg, LEVEL_1, "\tCollecting optimization units\n")); + INIT_LIST_HEAD(&co->units); + irg_walk_graph(co->irg, co_collect_units, NULL, co); +#ifdef QUICK_AND_DIRTY_HACK + co_sort_units(co); +#endif +} + +void co_free_ou_structure(copy_opt_t *co) { unit_t *curr, *tmp; - xfree(co->name); + ASSERT_OU_AVAIL(co); list_for_each_entry_safe(unit_t, curr, tmp, &co->units, units) { xfree(curr->nodes); + xfree(curr->costs); xfree(curr); } + co->units.next = NULL; } -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; - } - return 0; -} - -int get_costs_loop_depth(ir_node *root, ir_node* arg, int pos) { - int cost = 0; - 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 { - /* for phis the copies are placed in the corresponding pred-block */ - loop = get_irn_loop(get_Block_cfgpred_block(root_block, pos)); - } - if (loop) { - int d = get_loop_depth(loop); - cost = d*d; - } - return cost+1; -} - -int get_costs_all_one(ir_node *root, ir_node* arg, int pos) { - return 1; -} +/* co_solve_heuristic() is implemented in becopyheur.c */ int co_get_max_copy_costs(const copy_opt_t *co) { int i, res = 0; unit_t *curr; + ASSERT_OU_AVAIL(co); + list_for_each_entry(unit_t, curr, &co->units, units) { res += curr->inevitable_costs; for (i=1; inode_count; ++i) @@ -303,6 +481,8 @@ int co_get_inevit_copy_costs(const copy_opt_t *co) { int res = 0; unit_t *curr; + ASSERT_OU_AVAIL(co); + list_for_each_entry(unit_t, curr, &co->units, units) res += curr->inevitable_costs; return res; @@ -312,6 +492,8 @@ int co_get_copy_costs(const copy_opt_t *co) { int i, res = 0; unit_t *curr; + ASSERT_OU_AVAIL(co); + list_for_each_entry(unit_t, curr, &co->units, units) { int root_col = get_irn_col(co, curr->nodes[0]); DBG((dbg, LEVEL_1, " %3d costs for root %+F color %d\n", curr->inevitable_costs, curr->nodes[0], root_col)); @@ -330,7 +512,128 @@ int co_get_copy_costs(const copy_opt_t *co) { int co_get_lower_bound(const copy_opt_t *co) { int res = 0; unit_t *curr; + + ASSERT_OU_AVAIL(co); + list_for_each_entry(unit_t, curr, &co->units, units) res += curr->inevitable_costs + curr->min_nodes_costs; return res; } + +/****************************************************************************** + _____ _ _____ _ + / ____| | | / ____| | + | | __ _ __ __ _ _ __ | |__ | (___ | |_ ___ _ __ __ _ __ _ ___ + | | |_ | '__/ _` | '_ \| '_ \ \___ \| __/ _ \| '__/ _` |/ _` |/ _ \ + | |__| | | | (_| | |_) | | | | ____) | || (_) | | | (_| | (_| | __/ + \_____|_| \__,_| .__/|_| |_| |_____/ \__\___/|_| \__,_|\__, |\___| + | | __/ | + |_| |___/ + ******************************************************************************/ + +static int compare_affinity_node_t(const void *k1, const void *k2, size_t size) { + const affinity_node_t *n1 = k1; + const affinity_node_t *n2 = k2; + + return (n1->irn != n2->irn); +} + +static void add_edge(copy_opt_t *co, ir_node *n1, ir_node *n2, int costs) { + affinity_node_t new_node, *node; + neighb_t new_nbr, *nbr; + int allocnew; + + new_node.irn = n1; + new_node.degree = 0; + new_node.neighbours = NULL; + node = set_insert(co->nodes, &new_node, sizeof(new_node), HASH_PTR(new_node.irn)); + + allocnew = 1; + for (nbr = node->neighbours; nbr; nbr = nbr->next) + if (nbr->irn == n2) { + allocnew = 0; + break; + } + + /* if we did not find n2 in n1's neighbourhood insert it */ + if (allocnew) { + obstack_grow(&co->obst, &new_nbr, sizeof(new_nbr)); + nbr = obstack_finish(&co->obst); + nbr->irn = n2; + nbr->costs = 0; + nbr->next = node->neighbours; + node->neighbours = nbr; + node->degree++; + } + + /* now nbr points to n1's neighbour-entry of n2 */ + nbr->costs += costs; +} + +static INLINE void add_edges(copy_opt_t *co, ir_node *n1, ir_node *n2, int costs) { + if (! be_ifg_connected(co->cenv->ifg, n1, n2)) { + add_edge(co, n1, n2, costs); + add_edge(co, n2, n1, costs); + } +} + +static void build_graph_walker(ir_node *irn, void *env) { + copy_opt_t *co = env; + int pos, max; + arch_register_req_t req; + const arch_register_t *reg; + + if (!is_curr_reg_class(co, irn) || arch_irn_is(co->aenv, irn, ignore)) + return; + + reg = arch_get_irn_register(co->aenv, irn); + if (arch_register_type_is(reg, ignore)) + return; + + /* Phis */ + if (is_Reg_Phi(irn)) + for (pos=0, max=get_irn_arity(irn); posget_costs(irn, arg, pos)); + } + + /* Perms */ + else if (is_Perm_Proj(co->aenv, irn)) { + ir_node *arg = get_Perm_src(irn); + add_edges(co, irn, arg, co->get_costs(irn, arg, 0)); + } + + /* 2-address code */ + else if (is_2addr_code(co->aenv, irn, &req)) + add_edges(co, irn, req.other_same, co->get_costs(irn, req.other_same, 0)); +} + +void co_build_graph_structure(copy_opt_t *co) { + obstack_init(&co->obst); + co->nodes = new_set(compare_affinity_node_t, 32); + + irg_walk_graph(co->irg, build_graph_walker, NULL, co); +} + +void co_free_graph_structure(copy_opt_t *co) { + ASSERT_GS_AVAIL(co); + + del_set(co->nodes); + obstack_free(&co->obst, NULL); + co->nodes = NULL; +} + +/* co_solve_ilp1() co_solve_ilp2() are implemented in becopyilpX.c */ + +int co_gs_is_optimizable(copy_opt_t *co, ir_node *irn) { + affinity_node_t new_node, *n; + + ASSERT_GS_AVAIL(co); + + new_node.irn = irn; + n = set_find(co->nodes, &new_node, sizeof(new_node), HASH_PTR(new_node.irn)); + if (n) { + return (n->degree > 0); + } else + return 0; +}