X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbechordal.c;h=725e8d2f524da53f71ffdea505cd60291848ba9b;hb=80a6158fdd766f42ee6c508a773bc114ff1b61f3;hp=ec0b43d4a0d6e1f08a55111b938a45543599723c;hpb=8d3747b480395d0097ef78e4a764c86f69cfcc7b;p=libfirm diff --git a/ir/be/bechordal.c b/ir/be/bechordal.c index ec0b43d4a..725e8d2f5 100644 --- a/ir/be/bechordal.c +++ b/ir/be/bechordal.c @@ -28,6 +28,7 @@ #include "bitset.h" #include "iterator.h" #include "bipartite.h" +#include "hungarian.h" #include "irmode_t.h" #include "irgraph_t.h" @@ -41,7 +42,6 @@ #include "beutil.h" #include "besched.h" -#include "benumb_t.h" #include "besched_t.h" #include "belive_t.h" #include "benode_t.h" @@ -50,6 +50,7 @@ #include "beifg.h" #include "beinsn_t.h" #include "bestatevent.h" +#include "beirg_t.h" #include "bechordal_t.h" #include "bechordal_draw.h" @@ -226,30 +227,35 @@ static ir_node *prepare_constr_insn(be_chordal_env_t *env, ir_node *irn) bitset_t *def_constr = bitset_alloca(env->cls->n_regs); bitset_t *tmp = bitset_alloca(env->cls->n_regs); ir_node *bl = get_nodes_block(irn); + be_lv_t *lv = env->birg->lv; be_insn_t *insn; int i, j; - for(i = get_irn_arity(irn) - 1; i >= 0; --i) { + for (i = get_irn_arity(irn) - 1; i >= 0; --i) { ir_node *op = get_irn_n(irn, i); const arch_register_t *reg; arch_register_req_t req; - reg = arch_get_irn_register(aenv, op); + if (arch_get_irn_reg_class(aenv, irn, i) == env->cls) { + reg = arch_get_irn_register(aenv, op); - if(reg && arch_register_type_is(reg, ignore)) { - arch_get_register_req(aenv, &req, irn, i); - if(arch_register_req_is(&req, limited)) { - bitset_clear_all(tmp); - req.limited(req.limited_env, tmp); - if(!bitset_is_set(tmp, reg->index)) { - ir_node *copy = be_new_Copy(env->cls, env->irg, bl, op); - be_stat_ev("constr_copy", 1); + if (reg && arch_register_type_is(reg, ignore)) { + arch_get_register_req(aenv, &req, irn, i); + + if (arch_register_req_is(&req, limited)) { + bitset_clear_all(tmp); + req.limited(req.limited_env, tmp); + + if (! bitset_is_set(tmp, reg->index)) { + ir_node *copy = be_new_Copy(env->cls, env->irg, bl, op); + be_stat_ev("constr_copy", 1); - sched_add_before(irn, copy); - set_irn_n(irn, i, copy); - DBG((env->dbg, LEVEL_3, "inserting ignore arg copy %+F for %+F pos %d\n", copy, irn, i)); + sched_add_before(irn, copy); + set_irn_n(irn, i, copy); + DBG((env->dbg, LEVEL_3, "inserting ignore arg copy %+F for %+F pos %d\n", copy, irn, i)); + } } } } @@ -303,7 +309,7 @@ static ir_node *prepare_constr_insn(be_chordal_env_t *env, ir_node *irn) 2) lives through the node. 3) is constrained to a register occuring in out constraints. */ - if(op->has_constraints && values_interfere(env->lv, insn->irn, op->carrier) && bitset_popcnt(tmp) > 0) { + if(op->has_constraints && values_interfere(lv, insn->irn, op->carrier) && bitset_popcnt(tmp) > 0) { /* only create the copy if the operand is no copy. this is necessary since the assure constraints phase inserts @@ -316,7 +322,7 @@ static ir_node *prepare_constr_insn(be_chordal_env_t *env, ir_node *irn) sched_add_before(insn->irn, copy); set_irn_n(insn->irn, op->pos, copy); DBG((env->dbg, LEVEL_3, "inserting constr copy %+F for %+F pos %d\n", copy, insn->irn, op->pos)); - be_liveness_update(env->lv, op->carrier); + be_liveness_update(lv, op->carrier); } } } @@ -347,6 +353,7 @@ static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, be_insn_t int n_defs = be_insn_n_defs(insn); bitset_t *bs = bitset_alloca(env->cls->n_regs); int *pairing = alloca(MAX(n_defs, n_uses) * sizeof(pairing[0])); + be_lv_t *lv = env->birg->lv; int i, j; @@ -364,7 +371,7 @@ static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, be_insn_t int n_total; const be_operand_t *op = &insn->ops[i]; - if (! values_interfere(env->lv, op->irn, op->carrier) && ! op->partner) { + if (! values_interfere(lv, op->irn, op->carrier) && ! op->partner) { bitset_clear_all(bs); bitset_copy(bs, op->regs); bitset_and(bs, out_op->regs); @@ -396,6 +403,7 @@ static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env, be_in ir_node *perm = NULL; bitset_t *out_constr = bitset_alloca(env->cls->n_regs); bitset_t *bs = bitset_alloca(env->cls->n_regs); + be_lv_t *lv = env->birg->lv; DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;) int i; @@ -423,7 +431,7 @@ static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env, be_in Make the Perm, recompute liveness and re-scan the insn since the in operands are now the Projs of the Perm. */ - perm = insert_Perm_after(aenv, env->lv, env->cls, env->dom_front, sched_prev(insn->irn)); + perm = insert_Perm_after(aenv, lv, env->cls, env->birg->dom_front, sched_prev(insn->irn)); /* Registers are propagated by insert_Perm_after(). Clean them here! */ if(perm) { @@ -440,7 +448,7 @@ static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env, be_in the Perm. Recomputing liveness is also a good idea if a Perm is inserted, since the live sets may change. */ - // be_liveness_recompute(env->lv); + // be_liveness_recompute(lv); obstack_free(&env->obst, insn); *the_insn = insn = chordal_scan_insn(env, insn->irn); @@ -471,6 +479,7 @@ static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *i be_insn_t *insn = chordal_scan_insn(env, irn); ir_node *res = insn->next_insn; int be_silent = *silent; + be_lv_t *lv = env->birg->lv; if(insn->pre_colored) { int i; @@ -500,7 +509,8 @@ static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *i int n_regs = env->cls->n_regs; bitset_t *bs = bitset_alloca(n_regs); ir_node **alloc_nodes = alloca(n_regs * sizeof(alloc_nodes[0])); - bipartite_t *bp = bipartite_new(n_regs, n_regs); + hungarian_problem_t *bp= hungarian_new(n_regs, n_regs, 2, HUNGARIAN_MATCH_PERFECT); +// bipartite_t *bp = bipartite_new(n_regs, n_regs); int *assignment = alloca(n_regs * sizeof(assignment[0])); pmap *partners = pmap_create(); DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;) @@ -509,6 +519,7 @@ static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *i long col; const ir_edge_t *edge; ir_node *perm = NULL; + int match_res, cost; /* prepare the constraint handling of this node. @@ -546,7 +557,8 @@ static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *i DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier, bs)); bitset_foreach(bs, col) - bipartite_add(bp, n_alloc, col); + hungarian_add(bp, n_alloc, col, 1); +// bipartite_add(bp, n_alloc, col); n_alloc++; } @@ -562,7 +574,7 @@ static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *i assert(is_Proj(proj)); - if(values_interfere(env->lv, proj, irn) && !pmap_contains(partners, proj)) { + if(values_interfere(lv, proj, irn) && !pmap_contains(partners, proj)) { assert(n_alloc < n_regs); alloc_nodes[n_alloc] = proj; pmap_insert(partners, proj, NULL); @@ -571,7 +583,8 @@ static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *i arch_put_non_ignore_regs(aenv, env->cls, bs); bitset_andnot(bs, env->ignore_colors); bitset_foreach(bs, col) - bipartite_add(bp, n_alloc, col); + hungarian_add(bp, n_alloc, col, 1); +// bipartite_add(bp, n_alloc, col); n_alloc++; } @@ -579,7 +592,10 @@ static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *i } /* Compute a valid register allocation. */ - bipartite_matching(bp, assignment); + hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL); + match_res = hungarian_solve(bp, assignment, &cost, 1); + assert(match_res == 0 && "matching failed"); + //bipartite_matching(bp, assignment); /* Assign colors obtained from the matching. */ for(i = 0; i < n_alloc; ++i) { @@ -598,7 +614,7 @@ static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *i continue; arch_set_irn_register(aenv, nodes[j], reg); - pset_hinsert_ptr(alloc_env->pre_colored, nodes[j]); + (void) pset_hinsert_ptr(alloc_env->pre_colored, nodes[j]); DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", nodes[j], reg->name)); } } @@ -636,7 +652,8 @@ static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *i } } - bipartite_free(bp); + //bipartite_free(bp); + hungarian_free(bp); pmap_destroy(partners); } @@ -694,14 +711,15 @@ static void pressure(ir_node *block, void *env_ptr) be_chordal_env_t *env = alloc_env->chordal_env; bitset_t *live = alloc_env->live; ir_node *irn; + be_lv_t *lv = env->birg->lv; DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;) int i, n; unsigned step = 0; unsigned pressure = 0; struct list_head *head; - pset *live_in = be_lv_pset_put_in(env->lv, block, pset_new_ptr_default()); - pset *live_end = be_lv_pset_put_end(env->lv, block, pset_new_ptr_default()); + pset *live_in = be_lv_pset_put_in(lv, block, pset_new_ptr_default()); + pset *live_end = be_lv_pset_put_end(lv, block, pset_new_ptr_default()); DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block)); bitset_clear_all(live); @@ -795,7 +813,8 @@ static void assign(ir_node *block, void *env_ptr) bitset_t *in_colors = alloc_env->in_colors; const arch_env_t *arch_env = env->birg->main_env->arch_env; struct list_head *head = get_block_border_head(env, block); - pset *live_in = be_lv_pset_put_in(env->lv, block, pset_new_ptr_default()); + be_lv_t *lv = env->birg->lv; + pset *live_in = be_lv_pset_put_in(lv, block, pset_new_ptr_default()); const ir_node *irn; border_t *b; @@ -851,7 +870,7 @@ static void assign(ir_node *block, void *env_ptr) * Assign a color, if it is a local def. Global defs already have a * color. */ - if(b->is_def && !be_is_live_in(env->lv, block, irn)) { + if(b->is_def && !be_is_live_in(lv, block, irn)) { const arch_register_t *reg; int col = NO_COLOR; @@ -899,11 +918,14 @@ void be_ra_chordal_color(be_chordal_env_t *chordal_env) { be_chordal_alloc_env_t env; char buf[256]; + be_irg_t *birg = chordal_env->birg; int colors_n = arch_register_class_n_regs(chordal_env->cls); ir_graph *irg = chordal_env->irg; + be_assure_dom_front(birg); + be_assure_liveness(birg); assure_doms(irg); env.chordal_env = chordal_env; @@ -931,8 +953,6 @@ void be_ra_chordal_color(be_chordal_env_t *chordal_env) /* Assign the colors */ dom_tree_walk_irg(irg, assign, NULL, &env); - be_numbering_done(irg); - if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) { plotter_t *plotter; ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);