X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopyheur.c;h=be203051dcd66c03e0704aa840bc513f53e25a09;hb=7039e499eb395a6c98b66c38353025490604a256;hp=bd769bb2fc0013a5c3df3fb680eb10723de5cf49;hpb=c6571686bfbfb3c87ae24ae1dc568e685d6cd49a;p=libfirm diff --git a/ir/be/becopyheur.c b/ir/be/becopyheur.c index bd769bb2f..be203051d 100644 --- a/ir/be/becopyheur.c +++ b/ir/be/becopyheur.c @@ -1,20 +1,6 @@ /* - * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. - * * This file is part of libFirm. - * - * This file may be distributed and/or modified under the terms of the - * GNU General Public License version 2 as published by the Free Software - * Foundation and appearing in the file LICENSE.GPL included in the - * packaging of this file. - * - * Licensees holding valid libFirm Professional Edition licenses may use - * this file in accordance with the libFirm Commercial License. - * Agreement provided with the Software. - * - * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE - * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR - * PURPOSE. + * Copyright (C) 2012 University of Karlsruhe. */ /** @@ -71,8 +57,8 @@ typedef struct conflict_t { */ typedef struct node_stat_t { ir_node *irn; - int new_color; - int pinned_local :1; + int new_color; + unsigned pinned_local :1; } node_stat_t; /** @@ -80,7 +66,6 @@ typedef struct node_stat_t { */ typedef struct qnode_t { struct list_head queue; /**< chaining of unit_t->queue */ - const unit_t *ou; /**< the opt unit this node belongs to */ int color; /**< target color */ set *conflicts; /**< contains conflict_t's. All internal conflicts */ int mis_costs; /**< costs of nodes/copies in the mis. */ @@ -91,16 +76,6 @@ typedef struct qnode_t { static pset *pinned_global; /**< optimized nodes should not be altered any more */ -static inline int nodes_interfere(const be_chordal_env_t *env, const ir_node *a, const ir_node *b) -{ - if (env->ifg) - return be_ifg_connected(env->ifg, a, b); - else { - be_lv_t *lv = be_get_irg_liveness(env->irg); - return be_values_interfere(lv, a, b); - } -} - static int set_cmp_conflict_t(const void *x, const void *y, size_t size) { const conflict_t *xx = (const conflict_t*)x; @@ -126,7 +101,7 @@ static inline void qnode_add_conflict(const qnode_t *qn, const ir_node *n1, cons 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)); } /** @@ -136,8 +111,11 @@ static inline int qnode_are_conflicting(const qnode_t *qn, const ir_node *n1, co { conflict_t c; /* search for live range interference */ - if (n1!=n2 && nodes_interfere(qn->ou->co->cenv, 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 (get_irn_idx(n1) < get_irn_idx(n2)) { c.n1 = n1; @@ -146,7 +124,7 @@ static inline int qnode_are_conflicting(const qnode_t *qn, const ir_node *n1, co c.n1 = n2; c.n2 = n1; } - return set_find(qn->conflicts, &c, sizeof(c), HASH_CONFLICT(c)) != 0; + 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) @@ -162,7 +140,7 @@ static inline const node_stat_t *qnode_find_node(const qnode_t *qn, ir_node *irn { node_stat_t find; find.irn = irn; - return (const node_stat_t*)set_find(qn->changed_nodes, &find, sizeof(find), hash_irn(irn)); + return set_find(node_stat_t, qn->changed_nodes, &find, sizeof(find), hash_irn(irn)); } /** @@ -175,7 +153,7 @@ static inline node_stat_t *qnode_find_or_insert_node(const qnode_t *qn, ir_node find.irn = irn; find.new_color = NO_COLOR; find.pinned_local = 0; - return (node_stat_t*)set_insert(qn->changed_nodes, &find, sizeof(find), hash_irn(irn)); + return set_insert(node_stat_t, qn->changed_nodes, &find, sizeof(find), hash_irn(irn)); } /** @@ -251,16 +229,10 @@ static inline void qnode_pin_local(const qnode_t *qn, ir_node *irn) * Else the first conflicting ir_node encountered is returned. * */ -static ir_node *qnode_color_irn(const qnode_t *qn, ir_node *irn, int col, const ir_node *trigger) +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) { - copy_opt_t *co = qn->ou->co; - const be_chordal_env_t *chordal_env = co->cenv; - const arch_register_class_t *cls = co->cls; int irn_col = qnode_get_new_color(qn, irn); - ir_node *sub_res, *curr; - be_ifg_t *ifg = chordal_env->ifg; neighbours_iter_t iter; - const arch_register_req_t *req; DBG((dbg, LEVEL_3, "\t %+F \tcaused col(%+F) \t%2d --> %2d\n", trigger, irn, irn_col, col)); @@ -276,25 +248,22 @@ static ir_node *qnode_color_irn(const qnode_t *qn, ir_node *irn, int col, const return irn; } - req = arch_get_irn_register_req(irn); + 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); - ir_node *curr; int free_col; /* Get all possible colors */ - bitset_copy(free_cols, co->cenv->allocatable_regs); + bitset_copy(free_cols, allocatable_regs); /* Exclude colors not assignable to the irn */ - if (arch_register_req_is(req, limited)) { - bitset_t *limited = bitset_alloca(cls->n_regs); - rbitset_copy_to_bitset(req->limited, limited); - bitset_and(free_cols, limited); - } + 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); @@ -325,7 +294,7 @@ static ir_node *qnode_color_irn(const qnode_t *qn, ir_node *irn, int col, const 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) { - sub_res = qnode_color_irn(qn, curr, irn_col, irn); + 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; @@ -348,7 +317,7 @@ static ir_node *qnode_color_irn(const qnode_t *qn, ir_node *irn, int col, const * @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) { @@ -356,7 +325,7 @@ static int qnode_try_color(const qnode_t *qn) test_node = qn->mis[i]; DBG((dbg, LEVEL_3, "\t Testing %+F\n", test_node)); - confl_node = qnode_color_irn(qn, test_node, qn->color, 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")); @@ -368,7 +337,7 @@ 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 */ - if (confl_node == qn->ou->nodes[0]) { + 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 */ @@ -399,7 +368,6 @@ 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; - size_t pos; int next, curr_weight, best_weight = 0; /* assign the nodes into two groups. @@ -495,7 +463,6 @@ no_stable_set: static inline qnode_t *new_qnode(const unit_t *ou, int color) { qnode_t *qn = XMALLOC(qnode_t); - qn->ou = ou; qn->color = color; qn->mis = XMALLOCN(ir_node*, ou->node_count); qn->conflicts = new_set(set_cmp_conflict_t, SLOTS_CONFLICTS); @@ -548,30 +515,21 @@ static inline void ou_insert_qnode(unit_t *ou, qnode_t *qn) * 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) +static void ou_optimize(unit_t *ou, bitset_t const *const allocatable_regs, be_ifg_t *const ifg) { - qnode_t *curr = NULL; - qnode_t *tmp; - const arch_register_req_t *req; - bitset_t const* allocatable_regs; - unsigned n_regs; - unsigned idx; - int i; - DBG((dbg, LEVEL_1, "\tOptimizing unit:\n")); - for (i=0; inode_count; ++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); - req = arch_get_irn_register_req(ou->nodes[0]); - allocatable_regs = ou->co->cenv->allocatable_regs; - n_regs = req->cls->n_regs; + 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 (idx = 0; idx != n_regs; ++idx) { + for (unsigned idx = 0; idx != n_regs; ++idx) { if (!bitset_is_set(allocatable_regs, idx)) continue; if (!rbitset_is_set(limited, idx)) @@ -580,7 +538,7 @@ static void ou_optimize(unit_t *ou) ou_insert_qnode(ou, new_qnode(ou, idx)); } } else { - for (idx = 0; idx != n_regs; ++idx) { + for (unsigned idx = 0; idx != n_regs; ++idx) { if (!bitset_is_set(allocatable_regs, idx)) continue; @@ -589,6 +547,7 @@ static void ou_optimize(unit_t *ou) } /* search best */ + qnode_t *curr; for (;;) { assert(!list_empty(&ou->queue)); /* get head of queue */ @@ -597,7 +556,7 @@ static void ou_optimize(unit_t *ou) 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 */ @@ -608,12 +567,11 @@ static void ou_optimize(unit_t *ou) /* apply the best found qnode */ if (curr->mis_size >= 2) { - node_stat_t *ns; 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 == root_col) @@ -625,7 +583,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_1, "\t color(%+F) := %d\n", ns->irn, ns->new_color)); - set_irn_col(ou->co->cls, ns->irn, ns->new_color); + set_irn_col(req->cls, ns->irn, ns->new_color); } } } @@ -642,14 +600,15 @@ static void ou_optimize(unit_t *ou) */ int co_solve_heuristic(copy_opt_t *co) { - unit_t *curr; - 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;