X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopyheur.c;h=34e2e83def76e9980207fcc799596d2dd9d9fe70;hb=5c1057c78bd79c19bb1b93015ef3963c43700bf2;hp=a3ae35b792fccac5862d580eabc1abe33f2028bb;hpb=c2b1cfa6ad7c6bafcdce6a8c9d8d4fd3f94ce4a7;p=libfirm diff --git a/ir/be/becopyheur.c b/ir/be/becopyheur.c index a3ae35b79..34e2e83de 100644 --- a/ir/be/becopyheur.c +++ b/ir/be/becopyheur.c @@ -1,12 +1,16 @@ /** + * Author: Daniel Grund + * Date: 12.04.2005 + * Copyright: (c) Universitaet Karlsruhe + * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + * Heuristic for minimizing copies using a queue which holds 'qnodes' not yet * examined. A qnode has a 'target color', nodes out of the opt unit and - * a 'conflict graph'. A 'max indep set' is determined form these. We try to - * color this mis using a color-exchanging mechanism. Occuring conflicts are - * modeled with 'conflict edges' and the qnode is reinserted in the queue. The - * first qnode colored without conflicts is the best one. - * @author Daniel Grund - * @date 12.04.2005 + * a 'conflict graph'. 'Conflict graph' = "Interference graph' + 'conflict edges' + * A 'max indep set' is determined form these. We try to color this mis using a + * color-exchanging mechanism. Occuring conflicts are modeled with 'conflict edges' + * and the qnode is reinserted in the queue. The first qnode colored without + * conflicts is the best one. */ #ifdef HAVE_CONFIG_H #include "config.h" @@ -22,6 +26,7 @@ #include "xmalloc.h" #include "becopyopt.h" #include "becopystat.h" +#include "bitset.h" #define DEBUG_LVL 0 //SET_LEVEL_1 static firm_dbg_module_t *dbg = NULL; @@ -30,7 +35,7 @@ static firm_dbg_module_t *dbg = NULL; #define SLOTS_CONFLICTS 8 #define SLOTS_CHANGED_NODES 32 -#define MIN(a,b) ((anodes[] being part of the max independent set */ + int mis_costs; /**< costs of nodes/copies in the mis. */ + int mis_size; /**< size of the array below */ + ir_node **mis; /**< the nodes of unit_t->nodes[] being part of the max independent set */ set *changed_nodes; /**< contains node_stat_t's. */ } qnode_t; @@ -96,7 +102,7 @@ static INLINE void qnode_add_conflict(const qnode_t *qn, const ir_node *n1, cons static INLINE int qnode_are_conflicting(const qnode_t *qn, const ir_node *n1, const ir_node *n2) { conflict_t c; /* search for live range interference */ - if (n1!=n2 && values_interfere(n1, n2)) + if (n1!=n2 && nodes_interfere(qn->ou->co->chordal_env, n1, n2)) return 1; /* search for recoloring conflicts */ if ((int)n1 < (int)n2) { @@ -116,7 +122,7 @@ static int set_cmp_node_stat_t(const void *x, const void *y, size_t size) { /** * Finds a node status entry of a node if existent. Otherwise return NULL */ -static INLINE node_stat_t *qnode_find_node(const qnode_t *qn, const ir_node *irn) { +static INLINE node_stat_t *qnode_find_node(const qnode_t *qn, ir_node *irn) { node_stat_t find; find.irn = irn; return set_find(qn->changed_nodes, &find, sizeof(find), HASH_PTR(irn)); @@ -126,7 +132,7 @@ static INLINE node_stat_t *qnode_find_node(const qnode_t *qn, const ir_node *irn * Finds a node status entry of a node if existent. Otherwise it will return * an initialized new entry for this node. */ -static INLINE node_stat_t *qnode_find_or_insert_node(const qnode_t *qn, const ir_node *irn) { +static INLINE node_stat_t *qnode_find_or_insert_node(const qnode_t *qn, ir_node *irn) { node_stat_t find; find.irn = irn; find.new_color = NO_COLOR; @@ -137,18 +143,18 @@ static INLINE node_stat_t *qnode_find_or_insert_node(const qnode_t *qn, const ir /** * Returns the virtual color of a node if set before, else returns the real color. */ -static INLINE int qnode_get_new_color(const qnode_t *qn, const ir_node *irn) { +static INLINE int qnode_get_new_color(const qnode_t *qn, ir_node *irn) { node_stat_t *found = qnode_find_node(qn, irn); if (found) return found->new_color; else - return get_irn_color(irn); + return get_irn_col(qn->ou->co, irn); } /** * Sets the virtual color of a node. */ -static INLINE void qnode_set_new_color(const qnode_t *qn, const ir_node *irn, int color) { +static INLINE void qnode_set_new_color(const qnode_t *qn, ir_node *irn, int color) { node_stat_t *found = qnode_find_or_insert_node(qn, irn); found->new_color = color; } @@ -158,7 +164,7 @@ static INLINE void qnode_set_new_color(const qnode_t *qn, const ir_node *irn, in * to the same optimization unit and has been optimized before the current * processed node. */ -static INLINE int qnode_is_pinned_local(const qnode_t *qn, const ir_node *irn) { +static INLINE int qnode_is_pinned_local(const qnode_t *qn, ir_node *irn) { node_stat_t *found = qnode_find_node(qn, irn); if (found) return found->pinned_local; @@ -170,7 +176,7 @@ static INLINE int qnode_is_pinned_local(const qnode_t *qn, const ir_node *irn) { * Local-pins a node, so optimizations of further nodes of the same opt unit * can handle situations in which a color change would undo prior optimizations. */ -static INLINE void qnode_pin_local(const qnode_t *qn, const ir_node *irn) { +static INLINE void qnode_pin_local(const qnode_t *qn, ir_node *irn) { node_stat_t *found = qnode_find_or_insert_node(qn, irn); found->pinned_local = 1; } @@ -197,11 +203,14 @@ static INLINE void qnode_pin_local(const qnode_t *qn, const ir_node *irn) { * several smaller intervals where other values can live in between. * This should be true in SSA. */ -static const ir_node *qnode_color_irn(const qnode_t *qn, const ir_node *irn, int col, const ir_node *trigger) { - const ir_node *res; +static ir_node *qnode_color_irn(const qnode_t *qn, ir_node *irn, int col, const ir_node *trigger) { + ir_node *res; struct obstack confl_ob; 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_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)); obstack_init(&confl_ob); @@ -213,7 +222,10 @@ static const ir_node *qnode_color_irn(const qnode_t *qn, const ir_node *irn, int res = irn; goto ret_confl; } - if (!qn->ou->co->isa->is_reg_allocatable(irn, arch_register_for_index(qn->ou->co->cls, col))) + if (!arch_reg_is_allocatable(arch_env, + irn, + arch_pos_make_out(0), + arch_register_for_index(cls, col))) goto ret_imposs; /* get all nodes which would conflict with this change */ @@ -227,14 +239,18 @@ static const ir_node *qnode_color_irn(const qnode_t *qn, const ir_node *irn, int /* first check for a conflicting node which is 'living in' the irns block */ { ir_node *n; - pset *live_ins = get_live_in(irn_bl); + 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 (is_allocatable_irn(n) && n != trigger && qnode_get_new_color(qn, n) == col && values_interfere(irn, n)) { + 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); pset_break(live_ins); break; - } + } + del_pset(live_ins); } /* setup the queue of blocks. */ @@ -256,7 +272,10 @@ static const ir_node *qnode_color_irn(const qnode_t *qn, const ir_node *irn, int * 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 (is_allocatable_irn(n) && n != trigger && qnode_get_new_color(qn, n) == col && values_interfere(irn, n)) { + 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); } @@ -279,7 +298,7 @@ static const ir_node *qnode_color_irn(const qnode_t *qn, const ir_node *irn, int /* process all nodes which would conflict with this change */ for (i = 0, cn = confl[0]; cn; cn = confl[++i]) { - const ir_node *sub_res; + ir_node *sub_res; /* try to color the conflicting node cn with the color of the irn itself */ sub_res = qnode_color_irn(qn, cn, irn_col, irn); @@ -316,7 +335,7 @@ ret_confl: static int qnode_try_color(const qnode_t *qn) { int i; for (i=0; imis_size; ++i) { - const ir_node *test_node, *confl_node; + ir_node *test_node, *confl_node; test_node = qn->mis[i]; DBG((dbg, LEVEL_3, "\t Testing %n\n", test_node)); @@ -331,8 +350,16 @@ static int qnode_try_color(const qnode_t *qn) { } else { if (qnode_is_pinned_local(qn, confl_node)) { /* changing test_node would change back a node of current ou */ - DBG((dbg, LEVEL_3, "\t Conflicting local --> add conflict\n")); - qnode_add_conflict(qn, confl_node, test_node); + if (confl_node == qn->ou->nodes[0]) { + /* Adding a conflict edge between testnode and conflnode + * would introduce a root -- arg interference. + * So remove the arg of the qn */ + DBG((dbg, LEVEL_3, "\t Conflicting local with phi --> remove from qnode\n")); + qnode_add_conflict(qn, test_node, test_node); + } else { + DBG((dbg, LEVEL_3, "\t Conflicting local --> add conflict\n")); + qnode_add_conflict(qn, confl_node, test_node); + } } if (pset_find_ptr(pinned_global, confl_node)) { /* changing test_node would change back a node of a prior ou */ @@ -348,71 +375,59 @@ static int qnode_try_color(const qnode_t *qn) { } /** - * Determines a maximum independent set with respect to the interference and - * conflict edges of all nodes in a qnode. + * 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) { - int all_size, curr_size, i, o; - int *which; - const ir_node **curr, **all = alloca(ou->node_count * sizeof(*all)); + ir_node **irns; + 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; ++i) - if (!qnode_are_conflicting(qn, ou->nodes[i], ou->nodes[i])) - all[all_size++] = ou->nodes[i]; - - /* which[i] says which element to take out of all[] and put into curr[i] */ - which = alloca(all_size*sizeof(*which)); - for (curr_size=0; curr_sizemis_size = curr_size; - for (i=0; imis[i] = curr[i]; - return; + if (is_stable_set) { + /* calc current weigth */ + curr_weight = 0; + bitset_foreach(curr, pos) + curr_weight += ou->costs[1+pos]; -conflict_found: - /* We had a conflict. Generate next set */ - if (which[all_size-curr_size+1] == all_size-curr_size+1) { - curr_size--; - for (i=0; i=which[i+1]) { - redo = 1; - break; - } + /* any better ? */ + if (curr_weight > best_weight) { + best_weight = curr_weight; + bitset_copy(best, curr); } } + + bitset_minus1(curr); } + + /* transfer the best set into the qn */ + qn->mis_size = bitset_popcnt(best); + qn->mis_costs = best_weight; + next = 0; + bitset_foreach(best, pos) + qn->mis[next++] = ou->nodes[1+pos]; } /** @@ -452,17 +467,12 @@ static INLINE void ou_insert_qnode(unit_t *ou, qnode_t *qn) { } qnode_max_ind_set(qn, ou); - - /* set ou->mis_size for lower bound compution */ - if (ou->mis_size < qn->mis_size) - ou->mis_size = qn->mis_size; - /* do the insertion */ - DBG((dbg, LEVEL_4, "\t Insert qnode color %d with size %d\n", qn->color, qn->mis_size)); + DBG((dbg, LEVEL_4, "\t Insert qnode color %d with cost %d\n", qn->color, qn->mis_costs)); lh = &ou->queue; while (lh->next != &ou->queue) { qnode_t *curr = list_entry_queue(lh->next); - if (curr->mis_size <= qn->mis_size) + if (curr->mis_costs <= qn->mis_costs) break; lh = lh->next; } @@ -470,16 +480,16 @@ static INLINE void ou_insert_qnode(unit_t *ou, qnode_t *qn) { } /** - * Tries to re-allocate colors of nodes in this opt unit, to achieve a lower - * number of copy instructions placed during SSA-destruction and lowering. + * Tries to re-allocate colors of nodes in this opt unit, to achieve lower + * costs of copy instructions placed during SSA-destruction and lowering. * Works only for opt units with exactly 1 root node, which is the - * case for approximately 80% of all phi classes and all register constrained + * case for approximately 80% of all phi classes and 100% of register constrained * nodes. (All other phi classes are reduced to this case.) */ static void ou_optimize(unit_t *ou) { int i; qnode_t *curr, *tmp; - bitset_t *pos_regs = bitset_alloca(ou->co->cls->n_regs); + 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) @@ -487,7 +497,7 @@ static void ou_optimize(unit_t *ou) { /* init queue */ INIT_LIST_HEAD(&ou->queue); - ou->co->isa->get_allocatable_regs(ou->nodes[0], ou->co->cls, pos_regs); + 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); bitset_foreach(pos_regs, i) ou_insert_qnode(ou, new_qnode(ou, i)); @@ -496,7 +506,7 @@ static void ou_optimize(unit_t *ou) { /* get head of queue */ curr = list_entry_queue(ou->queue.next); list_del(&curr->queue); - DBG((dbg, LEVEL_2, "\t Examine qnode color %d with size %d\n", curr->color, curr->mis_size)); + DBG((dbg, LEVEL_2, "\t Examine qnode color %d with cost %d\n", curr->color, curr->mis_costs)); /* try */ if (qnode_try_color(curr)) @@ -511,11 +521,11 @@ static void ou_optimize(unit_t *ou) { if (curr->mis_size >= 2) { node_stat_t *ns; - DBG((dbg, LEVEL_1, "\t Best color: %d Copies: %d/%d\n", curr->color, ou->interf+ou->node_count-curr->mis_size, ou->interf+ou->node_count-1)); + 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 */ pset_insert_ptr(pinned_global, ou->nodes[0]); for (i=1; inode_count; ++i) { - const ir_node *irn = ou->nodes[i]; + ir_node *irn = ou->nodes[i]; int nc = qnode_get_new_color(curr, irn); if (nc != NO_COLOR && nc == qnode_get_new_color(curr, ou->nodes[0])) pset_insert_ptr(pinned_global, irn); @@ -526,7 +536,7 @@ static void ou_optimize(unit_t *ou) { /* 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)); - set_irn_color(ns->irn, ns->new_color); + set_irn_col(ou->co, ns->irn, ns->new_color); } } } @@ -542,7 +552,9 @@ void co_heur_opt(copy_opt_t *co) { 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, -1); + firm_dbg_set_mask(dbg, DEBUG_LVL_HEUR); + else + firm_dbg_set_mask(dbg, DEBUG_LVL); pinned_global = pset_new_ptr(SLOTS_PINNED_GLOBAL); list_for_each_entry(unit_t, curr, &co->units, units)