X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopyheur.c;h=bf75e77f5f8a28c361ce19e3a6d9b36e415349d7;hb=f48209ee1e8d81959bd3bd15f456afa4355f8303;hp=34e2e83def76e9980207fcc799596d2dd9d9fe70;hpb=757e9691e224edc699466891995898e806ca4b25;p=libfirm diff --git a/ir/be/becopyheur.c b/ir/be/becopyheur.c index 34e2e83de..bf75e77f5 100644 --- a/ir/be/becopyheur.c +++ b/ir/be/becopyheur.c @@ -28,7 +28,6 @@ #include "becopystat.h" #include "bitset.h" -#define DEBUG_LVL 0 //SET_LEVEL_1 static firm_dbg_module_t *dbg = NULL; #define SLOTS_PINNED_GLOBAL 256 @@ -70,7 +69,7 @@ typedef struct _qnode_t { set *changed_nodes; /**< contains node_stat_t's. */ } qnode_t; -pset *pinned_global; /**< optimized nodes should not be altered any more */ +static pset *pinned_global; /**< optimized nodes should not be altered any more */ static int set_cmp_conflict_t(const void *x, const void *y, size_t size) { const conflict_t *xx = x; @@ -84,7 +83,7 @@ static int set_cmp_conflict_t(const void *x, const void *y, size_t size) { */ static INLINE void qnode_add_conflict(const qnode_t *qn, const ir_node *n1, const ir_node *n2) { conflict_t c; - DBG((dbg, LEVEL_4, "\t %n -- %n\n", n1, n2)); + DBG((dbg, LEVEL_4, "\t %+F -- %+F\n", n1, n2)); if ((int)n1 < (int)n2) { c.n1 = n1; @@ -209,22 +208,24 @@ static ir_node *qnode_color_irn(const qnode_t *qn, ir_node *irn, int col, const ir_node **confl, *cn; int i, irn_col; const be_chordal_env_t *chordal_env = qn->ou->co->chordal_env; - const arch_env_t *arch_env = chordal_env->arch_env; + const arch_env_t *arch_env = get_arch_env(qn->ou->co); const arch_register_class_t *cls = chordal_env->cls; - DBG((dbg, LEVEL_3, "\t %n \tcaused col(%n) \t%2d --> %2d\n", trigger, irn, qnode_get_new_color(qn, irn), col)); + DBG((dbg, LEVEL_3, "\t %+F \tcaused col(%+F) \t%2d --> %2d\n", trigger, irn, qnode_get_new_color(qn, irn), col)); obstack_init(&confl_ob); irn_col = qnode_get_new_color(qn, irn); - if (irn_col == col) + if (irn_col == col) { + DBG((dbg, LEVEL_4, "\t Already same color.\n")); goto ret_save; + } if (pset_find_ptr(pinned_global, irn) || qnode_is_pinned_local(qn, irn)) { res = irn; goto ret_confl; } if (!arch_reg_is_allocatable(arch_env, irn, - arch_pos_make_out(0), + -1, arch_register_for_index(cls, col))) goto ret_imposs; @@ -240,15 +241,17 @@ static ir_node *qnode_color_irn(const qnode_t *qn, ir_node *irn, int col, const { ir_node *n; pset *live_ins = put_live_in(irn_bl, pset_new_ptr_default()); - for (n = pset_first(live_ins); n; n = pset_next(live_ins)) - if (arch_irn_has_reg_class(arch_env, n, arch_pos_make_out(0), cls) - && n != trigger && qnode_get_new_color(qn, n) == col - && nodes_interfere(chordal_env, irn, n)) { + for (n = pset_first(live_ins); n; n = pset_next(live_ins)) { + DBG((dbg, LEVEL_4, "Checking %+F which is live-in at the block\n", n)); + if (arch_irn_has_reg_class(arch_env, n, -1, cls) + && n != trigger && qnode_get_new_color(qn, n) == col + && nodes_interfere(chordal_env, irn, n)) { - DBG((dbg, LEVEL_4, "\t %n\ttroubles\n", n)); + DBG((dbg, LEVEL_4, "\t %+F\ttroubles\n", n)); obstack_ptr_grow(&confl_ob, n); pset_break(live_ins); break; + } } del_pset(live_ins); } @@ -272,12 +275,12 @@ static ir_node *qnode_color_irn(const qnode_t *qn, ir_node *irn, int col, const * the target color and interfere with the irn */ for (i = 0, max = get_irn_n_outs(curr_bl); i < max; ++i) { ir_node *n = get_irn_out(curr_bl, i); - if (arch_irn_has_reg_class(arch_env, n, arch_pos_make_out(0), cls) - && n != trigger && qnode_get_new_color(qn, n) == col - && nodes_interfere(chordal_env, irn, n)) { - - DBG((dbg, LEVEL_4, "\t %n\ttroubles\n", n)); - obstack_ptr_grow(&confl_ob, n); + DBG((dbg, LEVEL_4, "Checking %+F defined in same block\n", n)); + if (arch_irn_has_reg_class(arch_env, n, -1, cls) + && n != trigger && qnode_get_new_color(qn, n) == col + && nodes_interfere(chordal_env, irn, n)) { + DBG((dbg, LEVEL_4, "\t %+F\ttroubles\n", n)); + obstack_ptr_grow(&confl_ob, n); } } @@ -310,18 +313,18 @@ static ir_node *qnode_color_irn(const qnode_t *qn, ir_node *irn, int col, const /* if we arrive here all sub changes can be applied, so it's save to change this irn */ ret_save: - DBG((dbg, LEVEL_3, "\t %n save\n", irn)); + DBG((dbg, LEVEL_3, "\t %+F save\n", irn)); obstack_free(&confl_ob, NULL); qnode_set_new_color(qn, irn, col); return CHANGE_SAVE; ret_imposs: - DBG((dbg, LEVEL_3, "\t %n impossible\n", irn)); + DBG((dbg, LEVEL_3, "\t %+F impossible\n", irn)); obstack_free(&confl_ob, NULL); return CHANGE_IMPOSSIBLE; ret_confl: - DBG((dbg, LEVEL_3, "\t %n conflicting\n", irn)); + DBG((dbg, LEVEL_3, "\t %+F conflicting\n", irn)); obstack_free(&confl_ob, NULL); return res; } @@ -338,7 +341,7 @@ static int qnode_try_color(const qnode_t *qn) { ir_node *test_node, *confl_node; test_node = qn->mis[i]; - DBG((dbg, LEVEL_3, "\t Testing %n\n", test_node)); + DBG((dbg, LEVEL_3, "\t Testing %+F\n", test_node)); confl_node = qnode_color_irn(qn, test_node, qn->color, test_node); if (confl_node == CHANGE_SAVE) { @@ -374,60 +377,116 @@ static int qnode_try_color(const qnode_t *qn) { return 1; } +typedef int(*confl_f)(const ir_node *a, const ir_node *b, void *data); + +/** + * @param result Gets filled with the computed maximum independent set. + * @param count The size of input arrays / the number of nodes + * @param nodes A set of nodes to copmute the max. ind. set for + * @param weights Weights associated to the nodes in @p nodes + * @param confl Callback function to decide if two values interfere + * @param data Passed into all callbacks + * @return The size of the computed set + */ +//int max_ind_set(ir_node **result, int count, ir_node **nodes, int *weights, confl_f confl, void *data) { +// +//} + /** * Determines a maximum weighted independent set with respect to * the interference and conflict edges of all nodes in a qnode. */ static INLINE void qnode_max_ind_set(qnode_t *qn, const unit_t *ou) { - ir_node **irns; + ir_node **safe, **unsafe; + int i, o, safe_count, safe_costs, unsafe_count, *unsafe_costs; + bitset_t *curr, *best; int max, next, pos, curr_weight, best_weight = 0; - bitset_t *best, *curr; - - irns = alloca((ou->node_count-1) * sizeof(*irns)); - best = bitset_alloca(ou->node_count-1); - curr = bitset_alloca(ou->node_count-1); - - /* brute force the best set */ - bitset_set_all(curr); - while ((max = bitset_popcnt(curr)) != 0) { - /* check if curr is a stable set */ - int i, o, is_stable_set = 1; - - /* copy the irns */ - i = 0; - bitset_foreach(curr, pos) - irns[i++] = ou->nodes[1+pos]; - assert(i==max); - - for(i=0; inode_count-1) * sizeof(*safe)); + safe_costs = 0; + safe_count = 0; + unsafe = alloca((ou->node_count-1) * sizeof(*unsafe)); + unsafe_costs = alloca((ou->node_count-1) * sizeof(*unsafe_costs)); + unsafe_count = 0; + for(i=1; inode_count; ++i) { + int is_safe = 1; + for(o=1; onode_count; ++o) { + if (qnode_are_conflicting(qn, ou->nodes[i], ou->nodes[o])) { + if (i!=o) { + unsafe_costs[unsafe_count] = ou->costs[i]; + unsafe[unsafe_count] = ou->nodes[i]; + ++unsafe_count; } + is_safe = 0; + break; + } + } + if (is_safe) { + safe_costs += ou->costs[i]; + safe[safe_count++] = ou->nodes[i]; + } + } + + + + /* now compute the best set out of the unsafe nodes*/ + best = bitset_alloca(unsafe_count); - if (is_stable_set) { - /* calc current weigth */ + if (unsafe_count > MIS_HEUR_TRIGGER) { + /* Heuristik: Greedy trial and error form index 0 to unsafe_count-1 */ + for (i=0; icosts[1+pos]; + curr_weight += unsafe_costs[pos]; /* any better ? */ if (curr_weight > best_weight) { best_weight = curr_weight; bitset_copy(best, curr); } - } - bitset_minus1(curr); +no_stable_set: + bitset_minus1(curr); + } } /* transfer the best set into the qn */ - qn->mis_size = bitset_popcnt(best); - qn->mis_costs = best_weight; - next = 0; + qn->mis_size = 1+safe_count+bitset_popcnt(best); + qn->mis_costs = safe_costs+best_weight; + qn->mis[0] = ou->nodes[0]; /* the root is always in a max stable set */ + next = 1; + for (i=0; imis[next++] = safe[i]; bitset_foreach(best, pos) - qn->mis[next++] = ou->nodes[1+pos]; + qn->mis[next++] = unsafe[pos]; } /** @@ -488,16 +547,16 @@ static INLINE void ou_insert_qnode(unit_t *ou, qnode_t *qn) { */ static void ou_optimize(unit_t *ou) { int i; - qnode_t *curr, *tmp; + qnode_t *curr = NULL, *tmp; bitset_t *pos_regs = bitset_alloca(ou->co->chordal_env->cls->n_regs); DBG((dbg, LEVEL_1, "\tOptimizing unit:\n")); for (i=0; inode_count; ++i) - DBG((dbg, LEVEL_1, "\t %n\n", ou->nodes[i])); + DBG((dbg, LEVEL_1, "\t %+F\n", ou->nodes[i])); /* init queue */ INIT_LIST_HEAD(&ou->queue); - arch_get_allocatable_regs(ou->co->chordal_env->arch_env, ou->nodes[0], arch_pos_make_out(0), ou->co->chordal_env->cls, pos_regs); + arch_get_allocatable_regs(get_arch_env(ou->co), ou->nodes[0], -1, ou->co->chordal_env->cls, pos_regs); bitset_foreach(pos_regs, i) ou_insert_qnode(ou, new_qnode(ou, i)); @@ -520,9 +579,8 @@ static void ou_optimize(unit_t *ou) { /* apply the best found qnode */ if (curr->mis_size >= 2) { node_stat_t *ns; - - DBG((dbg, LEVEL_1, "\t Best color: %d Costs: %d/%d\n", curr->color, ou->complete_costs - curr->mis_costs, ou->complete_costs)); - /* globally pin root and eventually others */ + DBG((dbg, LEVEL_1, "\t Best color: %d Costs: %d << %d << %d\n", curr->color, ou->min_nodes_costs, ou->all_nodes_costs - curr->mis_costs, ou->all_nodes_costs)); + /* globally pin root and all args which have the same color */ pset_insert_ptr(pinned_global, ou->nodes[0]); for (i=1; inode_count; ++i) { ir_node *irn = ou->nodes[i]; @@ -535,10 +593,14 @@ static void ou_optimize(unit_t *ou) { for (ns = set_first(curr->changed_nodes); ns; ns = set_next(curr->changed_nodes)) { /* NO_COLOR is possible, if we had an undo */ if (ns->new_color != NO_COLOR) { - DBG((dbg, LEVEL_2, "\t color(%n) := %d\n", ns->irn, ns->new_color)); + DBG((dbg, LEVEL_1, "\t color(%+F) := %d\n", ns->irn, ns->new_color)); set_irn_col(ou->co, ns->irn, ns->new_color); } } + /* + * Enable for checking register allocation after each ou + * be_ra_chordal_check(ou->co->chordal_env); + */ } /* free best qnode (curr) and queue */ @@ -550,11 +612,10 @@ static void ou_optimize(unit_t *ou) { void co_heur_opt(copy_opt_t *co) { unit_t *curr; dbg = firm_dbg_register("ir.be.copyoptheur"); - firm_dbg_set_mask(dbg, DEBUG_LVL); if (!strcmp(co->name, DEBUG_IRG)) - firm_dbg_set_mask(dbg, DEBUG_LVL_HEUR); + firm_dbg_set_mask(dbg, DEBUG_IRG_LVL_HEUR); else - firm_dbg_set_mask(dbg, DEBUG_LVL); + firm_dbg_set_mask(dbg, DEBUG_LVL_HEUR); pinned_global = pset_new_ptr(SLOTS_PINNED_GLOBAL); list_for_each_entry(unit_t, curr, &co->units, units)