X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbechordal.c;h=bd368226f43f73e1ce3ba39c2e15ed31e9cce9f7;hb=4ed245f5007168dab7850942a7ee6b6b29a19817;hp=914d17ec4f02e14062446d5aea44fcf0c50899ec;hpb=cb0c12e4aa9e238abd067ec1e9bc8a55115e29a4;p=libfirm diff --git a/ir/be/bechordal.c b/ir/be/bechordal.c index 914d17ec4..bd368226f 100644 --- a/ir/be/bechordal.c +++ b/ir/be/bechordal.c @@ -77,6 +77,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 +94,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 +221,72 @@ 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; + be_insn_t *insn = chordal_scan_insn(env, 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(insn->irn); + int i, j; 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 && 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); + + 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); + + 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]; + + 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(env->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(env->lv, op->carrier); + } } } @@ -263,11 +312,10 @@ 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])); int i, j; @@ -275,42 +323,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(env->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); } @@ -346,6 +387,10 @@ static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env, be_in Now, figure out which input operand must be copied since it has input constraints which are also output constraints. */ + (void) bl; + (void) copy; + (void) bs; + (void) dbg; #if 0 for(i = insn->use_start; i < insn->n_ops; ++i) { be_operand_t *op = &insn->ops[i];