X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbechordal.c;h=d80281475501315092f1633d099a245bba72556f;hb=ff9b23893ba556b55fb18b0203a804179a4ea5d4;hp=d172253592997cdd6a3535dd4b4154f4e69844e6;hpb=1631f8aca0f030511c4078f346e9a2117c8279b6;p=libfirm diff --git a/ir/be/bechordal.c b/ir/be/bechordal.c index d17225359..d80281475 100644 --- a/ir/be/bechordal.c +++ b/ir/be/bechordal.c @@ -1,7 +1,8 @@ /** * Chordal register allocation. * @author Sebastian Hack - * @date 8.12.2004 + * @date 8.12.2004 + * @cvs-id $Id$ * * Copyright (C) Universitaet Karlsruhe * Released under the GPL @@ -34,6 +35,7 @@ #include "irgwalk.h" #include "irdump.h" #include "irdom.h" +#include "irtools.h" #include "debug.h" #include "xmalloc.h" @@ -56,9 +58,6 @@ #define NO_COLOR (-1) -#define MAX(x, y) ((x) > (y) ? (x) : (y)) -#define MIN(x, y) ((x) < (y) ? (x) : (y)) - #define DUMP_INTERVALS typedef struct _be_chordal_alloc_env_t { @@ -78,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; @@ -94,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 @@ -167,8 +167,8 @@ static INLINE border_t *border_add(be_chordal_env_t *env, struct list_head *head */ static INLINE int has_reg_class(const be_chordal_env_t *env, const ir_node *irn) { - // return arch_irn_has_reg_class(env->main_env->arch_env, irn, -1, env->cls); - return arch_irn_consider_in_reg_alloc(env->birg->main_env->arch_env, env->cls, irn); + return arch_irn_has_reg_class(env->birg->main_env->arch_env, irn, -1, env->cls); + // return arch_irn_consider_in_reg_alloc(env->birg->main_env->arch_env, env->cls, irn); } #define has_limited_constr(req, irn) \ @@ -208,26 +208,64 @@ static bitset_t *get_decisive_partner_regs(bitset_t *bs, const be_operand_t *o1, return res; } -static be_insn_t *chordal_scan_insn(be_chordal_alloc_env_t *env, ir_node *irn) +static be_insn_t *chordal_scan_insn(be_chordal_env_t *env, ir_node *irn) { be_insn_env_t ie; - ie.ignore_colors = env->chordal_env->ignore_colors; - ie.aenv = env->chordal_env->birg->main_env->arch_env; - ie.obst = &env->chordal_env->obst; - ie.cls = env->chordal_env->cls; + ie.ignore_colors = env->ignore_colors; + ie.aenv = env->birg->main_env->arch_env; + ie.obst = &env->obst; + ie.cls = env->cls; return be_scan_insn(&ie, 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 i; + + if(!insn->has_constraints) + goto end; + + 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); + } + } + +end: + obstack_free(&env->obst, insn); + return insn->next_insn; +} + +static void pre_spill_prepare_constr_walker(ir_node *bl, void *data) +{ + be_chordal_env_t *env = data; + ir_node *irn; + for(irn = sched_first(bl); !sched_is_end(irn);) { + irn = prepare_constr_insn(env, irn); + } +} + +void be_pre_spill_prepare_constr(be_chordal_env_t *cenv) { + irg_block_walk_graph(cenv->irg, pre_spill_prepare_constr_walker, NULL, (void *) cenv); +} + static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, be_insn_t *insn) { 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; @@ -235,42 +273,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(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); } @@ -306,9 +337,14 @@ 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]; - if(op->has_constraints && (values_interfere(op->carrier, insn->irn) || arch_irn_is(aenv, op->carrier, ignore))) { + 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); @@ -317,20 +353,22 @@ static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env, be_in 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); - insn->ops[i].carrier = copy; + 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 /* 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->cls, env->dom_front, sched_prev(insn->irn)); + perm = insert_Perm_after(aenv, env->lv, env->cls, env->dom_front, sched_prev(insn->irn)); /* Registers are propagated by insert_Perm_after(). Clean them here! */ if(perm) { @@ -346,9 +384,9 @@ 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(env->irg); + // be_liveness_recompute(env->lv); obstack_free(&env->obst, insn); - *the_insn = insn = chordal_scan_insn(alloc_env, insn->irn); + *the_insn = insn = chordal_scan_insn(env, insn->irn); /* Copy the input constraints of the insn to the Perm as output @@ -374,7 +412,7 @@ static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *i { be_chordal_env_t *env = alloc_env->chordal_env; void *base = obstack_base(&env->obst); - be_insn_t *insn = chordal_scan_insn(alloc_env, irn); + be_insn_t *insn = chordal_scan_insn(env, irn); ir_node *res = insn->next_insn; int be_silent = *silent; @@ -468,7 +506,7 @@ static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *i assert(is_Proj(proj)); - if(values_interfere(proj, irn) && !pmap_contains(partners, proj)) { + if(values_interfere(env->lv, proj, irn) && !pmap_contains(partners, proj)) { assert(n_alloc < n_regs); alloc_nodes[n_alloc] = proj; pmap_insert(partners, proj, NULL); @@ -541,6 +579,7 @@ static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *i } } + bipartite_free(bp); pmap_destroy(partners); } @@ -604,8 +643,8 @@ static void pressure(ir_node *block, void *env_ptr) unsigned step = 0; unsigned pressure = 0; struct list_head *head; - pset *live_in = put_live_in(block, pset_new_ptr_default()); - pset *live_end = put_live_end(block, pset_new_ptr_default()); + 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()); DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block)); bitset_clear_all(live); @@ -620,10 +659,10 @@ static void pressure(ir_node *block, void *env_ptr) * Make final uses of all values live out of the block. * They are necessary to build up real intervals. */ - for(irn = pset_first(live_end); irn; irn = pset_next(live_end)) { + foreach_pset(live_end, irn) { if(has_reg_class(env, irn)) { - DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_graph_nr(irn))); - bitset_set(live, get_irn_graph_nr(irn)); + DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_idx(irn))); + bitset_set(live, get_irn_idx(irn)); border_use(irn, step, 0); } } @@ -635,14 +674,14 @@ static void pressure(ir_node *block, void *env_ptr) */ sched_foreach_reverse(block, irn) { DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure)); - DBG((dbg, LEVEL_2, "\tlive: %b\n", live)); + DBG((dbg, LEVEL_2, "\tlive: %B\n", live)); /* * If the node defines some value, which can put into a * register of the current class, make a border for it. */ if(has_reg_class(env, irn)) { - int nr = get_irn_graph_nr(irn); + int nr = get_irn_idx(irn); bitset_clear(live, nr); border_def(irn, step, 1); @@ -656,14 +695,16 @@ static void pressure(ir_node *block, void *env_ptr) ir_node *op = get_irn_n(irn, i); if(has_reg_class(env, op)) { - int nr = get_irn_graph_nr(op); - - DBG((dbg, LEVEL_4, "\t\tpos: %d, use: %+F\n", i, op)); + int nr = get_irn_idx(op); + const char *msg = "-"; if(!bitset_is_set(live, nr)) { border_use(op, step, 1); bitset_set(live, nr); + msg = "X"; } + + DBG((dbg, LEVEL_4, "\t\t%s pos: %d, use: %+F\n", msg, i, op)); } } } @@ -673,20 +714,19 @@ static void pressure(ir_node *block, void *env_ptr) /* * Add initial defs for all values live in. */ - for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) { + foreach_pset(live_in, irn) { if(has_reg_class(env, irn)) { /* Mark the value live in. */ - bitset_set(live, get_irn_graph_nr(irn)); + bitset_set(live, get_irn_idx(irn)); /* Add the def */ border_def(irn, step, 0); } } - - del_pset(live_in); - del_pset(live_end); + del_pset(live_in); + del_pset(live_end); } static void assign(ir_node *block, void *env_ptr) @@ -697,12 +737,12 @@ static void assign(ir_node *block, void *env_ptr) bitset_t *colors = alloc_env->colors; bitset_t *in_colors = alloc_env->in_colors; const arch_env_t *arch_env = env->birg->main_env->arch_env; - DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;) + 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()); const ir_node *irn; border_t *b; - struct list_head *head = get_block_border_head(env, block); - pset *live_in = put_live_in(block, pset_new_ptr_default()); + DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;) bitset_clear_all(colors); bitset_clear_all(live); @@ -712,7 +752,7 @@ static void assign(ir_node *block, void *env_ptr) DBG((dbg, LEVEL_4, "\tusedef chain for block\n")); list_for_each_entry(border_t, b, head, list) { DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use", - b->irn, get_irn_graph_nr(b->irn))); + b->irn, get_irn_idx(b->irn))); } /* @@ -720,7 +760,7 @@ static void assign(ir_node *block, void *env_ptr) * Since their colors have already been assigned (The dominators were * allocated before), we have to mark their colors as used also. */ - for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) { + foreach_pset(live_in, irn) { if(has_reg_class(env, irn)) { const arch_register_t *reg = arch_get_irn_register(arch_env, irn); int col; @@ -728,12 +768,14 @@ static void assign(ir_node *block, void *env_ptr) assert(reg && "Node must have been assigned a register"); col = arch_register_get_index(reg); + DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name)); + /* Mark the color of the live in value as used. */ bitset_set(colors, col); bitset_set(in_colors, col); /* Mark the value live in. */ - bitset_set(live, get_irn_graph_nr(irn)); + bitset_set(live, get_irn_idx(irn)); } } @@ -745,17 +787,18 @@ static void assign(ir_node *block, void *env_ptr) */ list_for_each_entry_reverse(border_t, b, head, list) { ir_node *irn = b->irn; - int nr = get_irn_graph_nr(irn); + int nr = get_irn_idx(irn); + int ignore = arch_irn_is(arch_env, irn, ignore); /* * Assign a color, if it is a local def. Global defs already have a * color. */ - if(b->is_def && !is_live_in(block, irn)) { + if(b->is_def && !be_is_live_in(env->lv, block, irn)) { const arch_register_t *reg; int col = NO_COLOR; - if(pset_find_ptr(alloc_env->pre_colored, irn)) { + if(pset_find_ptr(alloc_env->pre_colored, irn) || ignore) { reg = arch_get_irn_register(arch_env, irn); col = reg->index; assert(!bitset_is_set(colors, col) && "pre-colored register must be free"); @@ -771,8 +814,7 @@ static void assign(ir_node *block, void *env_ptr) bitset_set(colors, col); arch_set_irn_register(arch_env, irn, reg); - DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", - arch_register_get_name(reg), col, irn)); + DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn)); assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered"); bitset_set(live, nr); @@ -805,8 +847,7 @@ void be_ra_chordal_color(be_chordal_env_t *chordal_env) ir_graph *irg = chordal_env->irg; - if(get_irg_dom_state(irg) != dom_consistent) - compute_doms(irg); + assure_doms(irg); env.chordal_env = chordal_env; env.colors_n = colors_n; @@ -826,7 +867,7 @@ void be_ra_chordal_color(be_chordal_env_t *chordal_env) } be_numbering(irg); - env.live = bitset_malloc(get_graph_node_count(chordal_env->irg)); + env.live = bitset_malloc(get_irg_last_idx(chordal_env->irg)); /* First, determine the pressure */ dom_tree_walk_irg(irg, pressure, NULL, &env); @@ -837,12 +878,13 @@ void be_ra_chordal_color(be_chordal_env_t *chordal_env) be_numbering_done(irg); if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) { - plotter_t *plotter; + plotter_t *plotter; ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg); - plotter = new_plotter_ps(buf); - draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter); - plotter_free(plotter); + plotter = new_plotter_ps(buf); + draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter); + plotter_free(plotter); } + bitset_free(env.live); del_pset(env.pre_colored); }