X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbechordal.c;h=725e8d2f524da53f71ffdea505cd60291848ba9b;hb=80a6158fdd766f42ee6c508a773bc114ff1b61f3;hp=914d17ec4f02e14062446d5aea44fcf0c50899ec;hpb=cb0c12e4aa9e238abd067ec1e9bc8a55115e29a4;p=libfirm diff --git a/ir/be/bechordal.c b/ir/be/bechordal.c index 914d17ec4..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" @@ -49,6 +49,8 @@ #include "beirgmod.h" #include "beifg.h" #include "beinsn_t.h" +#include "bestatevent.h" +#include "beirg_t.h" #include "bechordal_t.h" #include "bechordal_draw.h" @@ -77,6 +79,7 @@ typedef struct _be_chordal_alloc_env_t { /* Make a fourcc for border checking. */ #define BORDER_FOURCC FOURCC('B', 'O', 'R', 'D') +#if 0 static void check_border_list(struct list_head *head) { border_t *x; @@ -93,7 +96,7 @@ static void check_heads(be_chordal_env_t *env) check_border_list(ent->value); } } - +#endif /** * Add an interval border to the list of a block's list @@ -220,24 +223,107 @@ static be_insn_t *chordal_scan_insn(be_chordal_env_t *env, ir_node *irn) static ir_node *prepare_constr_insn(be_chordal_env_t *env, ir_node *irn) { - be_insn_t *insn = chordal_scan_insn(env, irn); - int n_uses = be_insn_n_uses(insn); - int n_defs = be_insn_n_defs(insn); - int i; + const arch_env_t *aenv = env->birg->main_env->arch_env; + 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) { + ir_node *op = get_irn_n(irn, i); + + const arch_register_t *reg; + arch_register_req_t req; + + 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); + + 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)); + } + } + } + } + } + + insn = chordal_scan_insn(env, irn); if(!insn->has_constraints) goto end; + /* insert copies for nodes that occur constrained more than once. */ + for(i = insn->use_start; i < insn->n_ops; ++i) { + be_operand_t *op = &insn->ops[i]; + + if(op->has_constraints) { + for(j = i + 1; j < insn->n_ops; ++j) { + be_operand_t *a_op = &insn->ops[j]; + + if(a_op->carrier == op->carrier && a_op->has_constraints) { + ir_node *copy = be_new_Copy(env->cls, env->irg, bl, op->carrier); + be_stat_ev("constr_copy", 1); + + sched_add_before(insn->irn, copy); + set_irn_n(insn->irn, a_op->pos, copy); + DBG((env->dbg, LEVEL_3, "inserting multiple constr copy %+F for %+F pos %d\n", copy, insn->irn, a_op->pos)); + } + } + } + } + + /* collect all registers occuring in out constraints. */ + for(i = 0; i < insn->use_start; ++i) { + be_operand_t *op = &insn->ops[i]; + if(op->has_constraints) + bitset_or(def_constr, op->regs); + } + + /* + insert copies for all constrained arguments living through the node + and being constrained to a register which also occurs in out constraints. + */ for(i = insn->use_start; i < insn->n_ops; ++i) { be_operand_t *op = &insn->ops[i]; - if(op->has_constraints && values_interfere(env->lv, insn->irn, op->carrier)) { - ir_node *bl = get_nodes_block(insn->irn); - ir_node *copy = be_new_Copy(env->cls, env->irg, bl, op->carrier); - - 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); + + bitset_copy(tmp, op->regs); + bitset_and(tmp, def_constr); + + /* + Check, if + 1) the operand is constrained. + 2) lives through the node. + 3) is constrained to a register occuring in out constraints. + */ + 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 + Copies and Keeps for operands which must be different from the results. + Additional copies here would destroy this. + */ + if(!be_is_Copy(op->carrier)) { + ir_node *copy = be_new_Copy(env->cls, env->irg, bl, op->carrier); + + 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(lv, op->carrier); + } } } @@ -263,11 +349,11 @@ static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, be_insn_t { const be_chordal_env_t *env = alloc_env->chordal_env; - int n_uses = be_insn_n_uses(insn); - int n_defs = be_insn_n_defs(insn); - bitset_t *bs = bitset_alloca(env->cls->n_regs); - bipartite_t *bp = bipartite_new(n_defs, n_uses); - int *pairing = alloca(MAX(n_defs, n_uses) * sizeof(pairing[0])); + int n_uses = be_insn_n_uses(insn); + 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; @@ -275,42 +361,35 @@ static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, be_insn_t For each out operand, try to find an in operand which can be assigned the same register as the out operand. */ - for(j = 0; j < insn->use_start; ++j) { + for (j = 0; j < insn->use_start; ++j) { + int smallest = -1; + int smallest_n_regs = 2 * env->cls->n_regs + 1; be_operand_t *out_op = &insn->ops[j]; /* Try to find an in operand which has ... */ for(i = insn->use_start; i < insn->n_ops; ++i) { + int n_total; const be_operand_t *op = &insn->ops[i]; - /* - The in operand can only be paired with a def, if the node defining the - operand's value does not interfere with the instruction itself. That - would mean, that it is live at the instruction, so no result of the instruction - can have the same register as the operand. - - Furthermore, tow operands can be paired, if the admissible registers - of one are a subset of the other's. We record the operand whose constraints - count in the decisive array. - */ - if(!values_interfere(env->lv, op->irn, op->carrier)) { - if(get_decisive_partner_regs(bs, out_op, op)) - bipartite_add(bp, j, i - insn->use_start); + 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); + n_total = bitset_popcnt(op->regs) + bitset_popcnt(out_op->regs); + + if (bitset_popcnt(bs) > 0 && n_total < smallest_n_regs) { + smallest = i; + smallest_n_regs = n_total; + } } } - } - - /* Compute the pairing. */ - bipartite_matching(bp, pairing); - for(i = 0; i < insn->use_start; ++i) { - int p = pairing[i] + insn->use_start; - if(p >= insn->use_start) { - insn->ops[i].partner = &insn->ops[p]; - insn->ops[p].partner = &insn->ops[i]; + if (smallest >= 0) { + be_operand_t *partner = &insn->ops[smallest]; + out_op->partner = partner; + partner->partner = out_op; } } - - bipartite_free(bp); } @@ -324,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; @@ -342,43 +422,22 @@ static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env, be_in bitset_or(out_constr, op->regs); } - /* - Now, figure out which input operand must be copied since it has input - constraints which are also output constraints. - */ -#if 0 - for(i = insn->use_start; i < insn->n_ops; ++i) { - be_operand_t *op = &insn->ops[i]; - if(op->has_constraints && (values_interfere(env->lv, op->carrier, insn->irn) || arch_irn_is(aenv, op->carrier, ignore))) { - bitset_copy(bs, op->regs); - bitset_and(bs, out_constr); - - /* - The operand (interfering with the node) has input constraints - which also occur as output constraints, so insert a copy. - */ - if(bitset_popcnt(bs) > 0) { - copy = be_new_Copy(op->req.cls, env->irg, bl, op->carrier); - op->carrier = copy; - sched_add_before(insn->irn, copy); - set_irn_n(insn->irn, op->pos, op->carrier); - - DBG((dbg, LEVEL_2, "adding copy for interfering and constrained op %+F\n", op->carrier)); - } - } - } -#endif + (void) bl; + (void) copy; + (void) bs; + DEBUG_ONLY((void) dbg;) /* 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) { const ir_edge_t *edge; + be_stat_ev("constr_perm", get_irn_arity(perm)); foreach_out_edge(perm, edge) { ir_node *proj = get_edge_src_irn(edge); arch_set_irn_register(aenv, proj, NULL); @@ -389,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); @@ -420,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; @@ -449,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;) @@ -458,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. @@ -495,14 +557,15 @@ 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++; } } /* - Put all nodes which live by the constrained instruction also to the + Put all nodes which live through the constrained instruction also to the allocation bipartite graph. They are considered unconstrained. */ if(perm) { @@ -511,15 +574,17 @@ 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); bitset_clear_all(bs); 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++; } @@ -527,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) { @@ -546,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)); } } @@ -584,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); } @@ -642,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); @@ -743,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; @@ -799,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; @@ -847,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; @@ -871,7 +945,6 @@ void be_ra_chordal_color(be_chordal_env_t *chordal_env) be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched); } - be_numbering(irg); env.live = bitset_malloc(get_irg_last_idx(chordal_env->irg)); /* First, determine the pressure */ @@ -880,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);