X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopyheur.c;h=be203051dcd66c03e0704aa840bc513f53e25a09;hb=7039e499eb395a6c98b66c38353025490604a256;hp=55092fea213dee9618b368d99b4605179e57bb94;hpb=9b24fe0ec0f4412c790ee4a7c6fc022fd28064a1;p=libfirm diff --git a/ir/be/becopyheur.c b/ir/be/becopyheur.c index 55092fea2..be203051d 100644 --- a/ir/be/becopyheur.c +++ b/ir/be/becopyheur.c @@ -1,47 +1,53 @@ -/** - * Author: Daniel Grund - * Date: 12.04.2005 - * Copyright: (c) Universitaet Karlsruhe - * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. +/* + * This file is part of libFirm. + * Copyright (C) 2012 University of Karlsruhe. + */ +/** + * @file + * @brief First simple copy minimization heuristics. + * @author Daniel Grund + * @date 12.04.2005 + * * 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'. 'Conflict graph' = "Interference graph' + 'conflict edges' - * A 'max indep set' is determined form these. We try to color this mis using a + * A 'max indep set' is determined from 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" -#endif - -#ifdef HAVE_ALLOCA_H -#include -#endif -#ifdef HAVE_MALLOC_H -#include -#endif +#include "debug.h" +#include "bitset.h" +#include "raw_bitset.h" #include "xmalloc.h" -#include "becopyopt.h" + +#include "becopyopt_t.h" #include "becopystat.h" +#include "beintlive_t.h" +#include "beirg.h" +#include "bemodule.h" + +DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;) + +/** Defines an invalid register index. */ +#define NO_COLOR (-1) -#define DEBUG_LVL 0 //SET_LEVEL_1 -static firm_dbg_module_t *dbg = NULL; +#define SEARCH_FREE_COLORS -#define SLOTS_PINNED_GLOBAL 256 +#define SLOTS_PINNED_GLOBAL 64 #define SLOTS_CONFLICTS 8 #define SLOTS_CHANGED_NODES 32 -#define MIN(a,b) ((aqueue */ - const unit_t *ou; /**< the opt unit this qnode belongs to */ - int color; /**< target color */ - set *conflicts; /**< contains conflict_t's. All internal conflicts */ - int mis_size; /**< number of nodes in the mis. */ - ir_node **mis; /**< the nodes of unit_t->nodes[] being part of the max independent set */ - set *changed_nodes; /**< contains node_stat_t's. */ +typedef struct qnode_t { + struct list_head queue; /**< chaining of unit_t->queue */ + int color; /**< target color */ + set *conflicts; /**< contains conflict_t's. All internal conflicts */ + 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; -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; - const conflict_t *yy = y; - return ! (xx->n1 == yy->n1 && xx->n2 == yy->n2); +static int set_cmp_conflict_t(const void *x, const void *y, size_t size) +{ + const conflict_t *xx = (const conflict_t*)x; + const conflict_t *yy = (const conflict_t*)y; + (void) size; + + return xx->n1 != yy->n1 || xx->n2 != yy->n2; } /** * If a local pinned conflict occurs, a new edge in the conflict graph is added. * The next maximum independent set build, will regard it. */ -static INLINE void qnode_add_conflict(const qnode_t *qn, const ir_node *n1, const ir_node *n2) { +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) { + if (get_irn_idx(n1) < get_irn_idx(n2)) { c.n1 = n1; c.n2 = n2; } else { c.n1 = n2; c.n2 = n1; } - set_insert(qn->conflicts, &c, sizeof(c), HASH_CONFLICT(c)); + (void)set_insert(conflict_t, qn->conflicts, &c, sizeof(c), HASH_CONFLICT(c)); } /** * Checks if two nodes are in a conflict. */ -static INLINE int qnode_are_conflicting(const qnode_t *qn, const ir_node *n1, const ir_node *n2) { +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 && nodes_interfere(qn->ou->co->chordal_env, n1, n2)) - return 1; + if (n1 != n2) { + be_lv_t *const lv = be_get_irg_liveness(get_irn_irg(n1)); + if (be_values_interfere(lv, n1, n2)) + return 1; + } /* search for recoloring conflicts */ - if ((int)n1 < (int)n2) { + if (get_irn_idx(n1) < get_irn_idx(n2)) { c.n1 = n1; c.n2 = n2; } else { c.n1 = n2; c.n2 = n1; } - return (int) set_find(qn->conflicts, &c, sizeof(c), HASH_CONFLICT(c)); + return set_find(conflict_t, qn->conflicts, &c, sizeof(c), HASH_CONFLICT(c)) != 0; } -static int set_cmp_node_stat_t(const void *x, const void *y, size_t size) { - return ((node_stat_t *)x)->irn != ((node_stat_t *)y)->irn; +static int set_cmp_node_stat_t(const void *x, const void *y, size_t size) +{ + (void) size; + return ((const node_stat_t*)x)->irn != ((const node_stat_t*)y)->irn; } /** * 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, ir_node *irn) { +static inline const 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)); + return set_find(node_stat_t, qn->changed_nodes, &find, sizeof(find), hash_irn(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, 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; find.pinned_local = 0; - return set_insert(qn->changed_nodes, &find, sizeof(find), HASH_PTR(irn)); + return set_insert(node_stat_t, qn->changed_nodes, &find, sizeof(find), hash_irn(irn)); } /** * 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, ir_node *irn) { - node_stat_t *found = qnode_find_node(qn, irn); +static inline int qnode_get_new_color(const qnode_t *qn, ir_node *irn) +{ + const node_stat_t *found = qnode_find_node(qn, irn); if (found) return found->new_color; else - return get_irn_col(qn->ou->co, irn); + return get_irn_col(irn); } /** * Sets the virtual color of a node. */ -static INLINE void qnode_set_new_color(const qnode_t *qn, 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; + DBG((dbg, LEVEL_3, "\t col(%+F) := %d\n", irn, color)); } /** @@ -162,8 +183,9 @@ static INLINE void qnode_set_new_color(const qnode_t *qn, ir_node *irn, int colo * 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, ir_node *irn) { - node_stat_t *found = qnode_find_node(qn, irn); +static inline int qnode_is_pinned_local(const qnode_t *qn, ir_node *irn) +{ + const node_stat_t *found = qnode_find_node(qn, irn); if (found) return found->pinned_local; else @@ -174,170 +196,136 @@ static INLINE int qnode_is_pinned_local(const qnode_t *qn, 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, 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; + if (found->new_color == NO_COLOR) + found->new_color = get_irn_col(irn); } + /** * Possible return values of qnode_color_irn() */ #define CHANGE_SAVE NULL #define CHANGE_IMPOSSIBLE (ir_node *)1 -#define is_conflicting_node(n) (((int)n) > 1) /** * Performs virtual re-coloring of node @p n to color @p col. Virtual colors of * other nodes are changed too, as required to preserve correctness. Function is * aware of local and global pinning. Recursive. - * @param irn The node to set the color for - * @param col The color to set + * + * If irn == trigger the color @p col must be used. (the first recoloring) + * If irn != trigger an arbitrary free color may be used. If no color is free, @p col is used. + * + * @param irn The node to set the color for + * @param col The color to set * @param trigger The irn that caused the wish to change the color of the irn + * External callers must call with trigger = irn + * * @return CHANGE_SAVE iff setting the color is possible, with all transitive effects. * CHANGE_IMPOSSIBLE iff conflicts with reg-constraintsis occured. * Else the first conflicting ir_node encountered is returned. * - * ASSUMPTION: Assumes that a life range of a single value can't be split into - * several smaller intervals where other values can live in between. - * This should be true in SSA. */ -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); - irn_col = qnode_get_new_color(qn, irn); - - if (irn_col == col) - goto ret_save; +static ir_node *qnode_color_irn(qnode_t const *const qn, ir_node *const irn, int const col, ir_node const *const trigger, bitset_t const *const allocatable_regs, be_ifg_t *const ifg) +{ + int irn_col = qnode_get_new_color(qn, irn); + neighbours_iter_t iter; + + DBG((dbg, LEVEL_3, "\t %+F \tcaused col(%+F) \t%2d --> %2d\n", trigger, irn, irn_col, col)); + + /* If the target color is already set do nothing */ + if (irn_col == col) { + DBG((dbg, LEVEL_3, "\t %+F same color\n", irn)); + return CHANGE_SAVE; + } + + /* If the irn is pinned, changing color is impossible */ if (pset_find_ptr(pinned_global, irn) || qnode_is_pinned_local(qn, irn)) { - res = irn; - goto ret_confl; + DBG((dbg, LEVEL_3, "\t %+F conflicting\n", irn)); + return irn; } - 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 */ - { - struct obstack q; - int in, out; - ir_node *irn_bl; - - irn_bl = get_nodes_block(irn); - - /* first check for a conflicting node which is 'living in' the irns block */ - { - 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)) { - - 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. */ - obstack_init(&q); - obstack_ptr_grow(&q, irn_bl); - in = 1; - out = 0; - - /* process the queue. The code below checks for every block dominated - * by the irns one, and in which the irn is live, if there are - * conflicting nodes */ - while (out < in) { - ir_node *curr_bl, *sub_bl; - int i, max; - - curr_bl = ((ir_node **)obstack_base(&q))[out++]; - - /* Add to the result all nodes in the block, which have - * 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); - } - } + arch_register_req_t const *const req = arch_get_irn_register_req(irn); + arch_register_class_t const *const cls = req->cls; +#ifdef SEARCH_FREE_COLORS + /* If we resolve conflicts (recursive calls) we can use any unused color. + * In case of the first call @p col must be used. + */ + if (irn != trigger) { + bitset_t *free_cols = bitset_alloca(cls->n_regs); + int free_col; - /* If irn lives out check i-dominated blocks where the irn lives in */ - /* Fill the queue */ - if (is_live_out(curr_bl, irn)) { - dominates_for_each(curr_bl, sub_bl) - if (is_live_in(sub_bl, irn)) { - obstack_ptr_grow(&q, sub_bl); - in++; - } - } + /* Get all possible colors */ + bitset_copy(free_cols, allocatable_regs); + + /* Exclude colors not assignable to the irn */ + if (arch_register_req_is(req, limited)) + rbitset_and(free_cols->data, req->limited, free_cols->size); + + /* Exclude the color of the irn, because it must _change_ its color */ + bitset_clear(free_cols, irn_col); + + /* Exclude all colors used by adjacent nodes */ + be_ifg_foreach_neighbour(ifg, &iter, irn, curr) + bitset_clear(free_cols, qnode_get_new_color(qn, curr)); + + free_col = bitset_next_set(free_cols, 0); + + if (free_col != -1) { + qnode_set_new_color(qn, irn, free_col); + return CHANGE_SAVE; } - obstack_free(&q, NULL); - obstack_ptr_grow(&confl_ob, NULL); - confl = (ir_node **) obstack_finish(&confl_ob); } +#endif /* SEARCH_FREE_COLORS */ - /* process all nodes which would conflict with this change */ - for (i = 0, cn = confl[0]; cn; cn = confl[++i]) { - ir_node *sub_res; + /* If target color is not allocatable changing color is impossible */ + if (!arch_reg_is_allocatable(req, arch_register_for_index(cls, col))) { + DBG((dbg, LEVEL_3, "\t %+F impossible\n", irn)); + return CHANGE_IMPOSSIBLE; + } - /* try to color the conflicting node cn with the color of the irn itself */ - sub_res = qnode_color_irn(qn, cn, irn_col, irn); - if (sub_res != CHANGE_SAVE) { - res = sub_res; - goto ret_confl; + /* + * If we arrive here changing color may be possible, but there may be conflicts. + * Try to color all conflicting nodes 'curr' with the color of the irn itself. + */ + be_ifg_foreach_neighbour(ifg, &iter, irn, curr) { + DBG((dbg, LEVEL_3, "\t Confl %+F(%d)\n", curr, qnode_get_new_color(qn, curr))); + if (qnode_get_new_color(qn, curr) == col && curr != trigger) { + ir_node *const sub_res = qnode_color_irn(qn, curr, irn_col, irn, allocatable_regs, ifg); + if (sub_res != CHANGE_SAVE) { + be_ifg_neighbours_break(&iter); + return sub_res; + } } } - /* 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)); - obstack_free(&confl_ob, NULL); + /* + * If we arrive here, all conflicts were resolved. + * So it is save to change this irn + */ qnode_set_new_color(qn, irn, col); return CHANGE_SAVE; - -ret_imposs: - DBG((dbg, LEVEL_3, "\t %n impossible\n", irn)); - obstack_free(&confl_ob, NULL); - return CHANGE_IMPOSSIBLE; - -ret_confl: - DBG((dbg, LEVEL_3, "\t %n conflicting\n", irn)); - obstack_free(&confl_ob, NULL); - return res; } + /** * Tries to set the colors for all members of this queue node; * to the target color qn->color * @returns 1 iff all members colors could be set * 0 else */ -static int qnode_try_color(const qnode_t *qn) { +static int qnode_try_color(qnode_t const *const qn, bitset_t const *const allocatable_regs, be_ifg_t *const ifg) +{ int i; for (i=0; imis_size; ++i) { ir_node *test_node, *confl_node; test_node = qn->mis[i]; - DBG((dbg, LEVEL_3, "\t Testing %n\n", test_node)); - confl_node = qnode_color_irn(qn, test_node, qn->color, test_node); + DBG((dbg, LEVEL_3, "\t Testing %+F\n", test_node)); + confl_node = qnode_color_irn(qn, test_node, qn->color, test_node, allocatable_regs, ifg); if (confl_node == CHANGE_SAVE) { DBG((dbg, LEVEL_3, "\t Save --> pin local\n")); @@ -345,102 +333,139 @@ static int qnode_try_color(const qnode_t *qn) { } else if (confl_node == CHANGE_IMPOSSIBLE) { DBG((dbg, LEVEL_3, "\t Impossible --> remove from qnode\n")); qnode_add_conflict(qn, test_node, test_node); + return 0; } 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->mis[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 */ DBG((dbg, LEVEL_3, "\t Conflicting global --> remove from qnode\n")); qnode_add_conflict(qn, test_node, test_node); } - } - - if (confl_node != CHANGE_SAVE) return 0; + } } return 1; } /** - * 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; - ir_node **curr, **all = alloca(ou->node_count * sizeof(*all)); - - /* all contains all nodes not removed in this qn */ - all_size = 0; - 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; +static inline void qnode_max_ind_set(qnode_t *qn, const unit_t *ou) +{ + ir_node **safe, **unsafe; + int i, o, safe_count, safe_costs, unsafe_count, *unsafe_costs; + bitset_t *curr, *best; + int next, curr_weight, best_weight = 0; + + /* assign the nodes into two groups. + * safe: node has no interference, hence it is in every max stable set. + * unsafe: node has an interference + */ + safe = ALLOCAN(ir_node*, ou->node_count - 1); + safe_costs = 0; + safe_count = 0; + unsafe = ALLOCAN(ir_node*, ou->node_count - 1); + unsafe_costs = ALLOCAN(int, ou->node_count - 1); + 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]; + } + } -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; - } + + + /* now compute the best set out of the unsafe nodes*/ + best = bitset_alloca(unsafe_count); + + if (unsafe_count > MIS_HEUR_TRIGGER) { + /* Heuristic: Greedy trial and error form index 0 to unsafe_count-1 */ + for (i=0; i best_weight) { + best_weight = curr_weight; + bitset_copy(best, curr); } + +no_stable_set: + bitset_minus1(curr); } } + + /* transfer the best set into the qn */ + qn->mis_size = 1+safe_count+bitset_popcount(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++] = unsafe[pos]; } /** * Creates a new qnode */ -static INLINE qnode_t *new_qnode(const unit_t *ou, int color) { - qnode_t *qn = xmalloc(sizeof(*qn)); - qn->ou = ou; - qn->color = color; - qn->mis = malloc(ou->node_count * sizeof(*qn->mis)); - qn->conflicts = new_set(set_cmp_conflict_t, SLOTS_CONFLICTS); +static inline qnode_t *new_qnode(const unit_t *ou, int color) +{ + qnode_t *qn = XMALLOC(qnode_t); + qn->color = color; + qn->mis = XMALLOCN(ir_node*, ou->node_count); + qn->conflicts = new_set(set_cmp_conflict_t, SLOTS_CONFLICTS); qn->changed_nodes = new_set(set_cmp_node_stat_t, SLOTS_CHANGED_NODES); return qn; } @@ -448,7 +473,8 @@ static INLINE qnode_t *new_qnode(const unit_t *ou, int color) { /** * Frees space used by a queue node */ -static INLINE void free_qnode(qnode_t *qn) { +static inline void free_qnode(qnode_t *qn) +{ del_set(qn->conflicts); del_set(qn->changed_nodes); xfree(qn->mis); @@ -459,7 +485,8 @@ static INLINE void free_qnode(qnode_t *qn) { * Inserts a qnode in the sorted queue of the optimization unit. Queue is * ordered by field 'size' (the size of the mis) in decreasing order. */ -static INLINE void ou_insert_qnode(unit_t *ou, qnode_t *qn) { +static inline void ou_insert_qnode(unit_t *ou, qnode_t *qn) +{ struct list_head *lh; if (qnode_are_conflicting(qn, ou->nodes[0], ou->nodes[0])) { @@ -470,11 +497,11 @@ static INLINE void ou_insert_qnode(unit_t *ou, qnode_t *qn) { qnode_max_ind_set(qn, ou); /* 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; } @@ -482,37 +509,56 @@ 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->chordal_env->cls->n_regs); - +static void ou_optimize(unit_t *ou, bitset_t const *const allocatable_regs, be_ifg_t *const ifg) +{ DBG((dbg, LEVEL_1, "\tOptimizing unit:\n")); - for (i=0; inode_count; ++i) - DBG((dbg, LEVEL_1, "\t %n\n", ou->nodes[i])); + for (int i = 0; i < ou->node_count; ++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); - bitset_foreach(pos_regs, i) - ou_insert_qnode(ou, new_qnode(ou, i)); + + arch_register_req_t const *const req = arch_get_irn_register_req(ou->nodes[0]); + unsigned const n_regs = req->cls->n_regs; + if (arch_register_req_is(req, limited)) { + unsigned const* limited = req->limited; + + for (unsigned idx = 0; idx != n_regs; ++idx) { + if (!bitset_is_set(allocatable_regs, idx)) + continue; + if (!rbitset_is_set(limited, idx)) + continue; + + ou_insert_qnode(ou, new_qnode(ou, idx)); + } + } else { + for (unsigned idx = 0; idx != n_regs; ++idx) { + if (!bitset_is_set(allocatable_regs, idx)) + continue; + + ou_insert_qnode(ou, new_qnode(ou, idx)); + } + } /* search best */ - while (!list_empty(&ou->queue)) { + qnode_t *curr; + for (;;) { + assert(!list_empty(&ou->queue)); /* 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)) + if (qnode_try_color(curr, allocatable_regs, ifg)) break; + /* no success, so re-insert */ del_set(curr->changed_nodes); curr->changed_nodes = new_set(set_cmp_node_stat_t, SLOTS_CHANGED_NODES); @@ -521,24 +567,23 @@ 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 Copies: %d/%d\n", curr->color, ou->interf+ou->node_count-curr->mis_size, ou->interf+ou->node_count-1)); - /* globally pin root and eventually others */ + int root_col = qnode_get_new_color(curr, ou->nodes[0]); + 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) { + for (int i = 1; i < ou->node_count; ++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])) + if (nc != NO_COLOR && nc == root_col) pset_insert_ptr(pinned_global, irn); } /* set color of all changed nodes */ - for (ns = set_first(curr->changed_nodes); ns; ns = set_next(curr->changed_nodes)) { + foreach_set(curr->changed_nodes, node_stat_t, ns) { /* 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_col(ou->co, ns->irn, ns->new_color); + DBG((dbg, LEVEL_1, "\t color(%+F) := %d\n", ns->irn, ns->new_color)); + set_irn_col(req->cls, ns->irn, ns->new_color); } } } @@ -549,19 +594,33 @@ static void ou_optimize(unit_t *ou) { free_qnode(curr); } -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); - else - firm_dbg_set_mask(dbg, DEBUG_LVL); +/** + * Solves the problem using a heuristic approach + * Uses the OU data structure + */ +int co_solve_heuristic(copy_opt_t *co) +{ + ASSERT_OU_AVAIL(co); pinned_global = pset_new_ptr(SLOTS_PINNED_GLOBAL); - list_for_each_entry(unit_t, curr, &co->units, units) + bitset_t const *const allocatable_regs = co->cenv->allocatable_regs; + be_ifg_t *const ifg = co->cenv->ifg; + list_for_each_entry(unit_t, curr, &co->units, units) { if (curr->node_count > 1) - ou_optimize(curr); + ou_optimize(curr, allocatable_regs, ifg); + } del_pset(pinned_global); + return 0; +} + +BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur) +void be_init_copyheur(void) +{ + static co_algo_info copyheur = { + co_solve_heuristic, 0 + }; + + be_register_copyopt("heur1", ©heur); + FIRM_DBG_REGISTER(dbg, "ir.be.copyoptheur"); }