X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbechordal.c;h=24126a1be6990ff6c89b1cfa9aa51d88d3c33d15;hb=5474a1c188c9d59eea2c915515980cd9cbab58d8;hp=d8fb8ed5902742eff56395f55cb8c1e31b2410d4;hpb=aec17f81a9d5186a8284d8589bff07a44be3aa8d;p=libfirm diff --git a/ir/be/bechordal.c b/ir/be/bechordal.c index d8fb8ed59..24126a1be 100644 --- a/ir/be/bechordal.c +++ b/ir/be/bechordal.c @@ -22,7 +22,6 @@ * @brief Chordal register allocation. * @author Sebastian Hack * @date 08.12.2004 - * @version $Id$ */ #include "config.h" @@ -44,7 +43,6 @@ #include "irdump.h" #include "irdom.h" #include "irtools.h" -#include "irbitset.h" #include "debug.h" #include "iredges.h" @@ -69,117 +67,26 @@ DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;) -#define NO_COLOR (-1) - #define DUMP_INTERVALS -typedef struct _be_chordal_alloc_env_t { +typedef struct be_chordal_alloc_env_t { be_chordal_env_t *chordal_env; pset *pre_colored; /**< Set of precolored nodes. */ - bitset_t *live; /**< A liveness bitset. */ + bitset_t *live; /**< A liveness bitset. */ bitset_t *tmp_colors; /**< An auxiliary bitset which is as long as the number of colors in the class. */ - bitset_t *colors; /**< The color mask. */ + bitset_t *colors; /**< The color mask. */ bitset_t *in_colors; /**< Colors used by live in values. */ int colors_n; /**< The number of colors. */ } be_chordal_alloc_env_t; -#if 0 -static void check_border_list(struct list_head *head) -{ - border_t *x; - list_for_each_entry(border_t, x, head, list) { - assert(x->magic == BORDER_FOURCC); - } -} - -static void check_heads(be_chordal_env_t *env) -{ - pmap_entry *ent; - for (ent = pmap_first(env->border_heads); ent; ent = pmap_next(env->border_heads)) { - /* ir_printf("checking border list of block %+F\n", ent->key); */ - check_border_list(ent->value); - } -} -#endif - -///** -// * Add an interval border to the list of a block's list -// * of interval border. -// * @note You always have to create the use before the def. -// * @param env The environment. -// * @param head The list head to enqueue the borders. -// * @param irn The node (value) the border belongs to. -// * @param pressure The pressure at this point in time. -// * @param step A time step for the border. -// * @param is_def Is the border a use or a def. -// * @return The created border. -// */ -//static inline border_t *border_add(be_chordal_env_t *env, struct list_head *head, -// ir_node *irn, unsigned step, unsigned pressure, -// unsigned is_def, unsigned is_real) -//{ -// border_t *b; -// -// if (!is_def) { -// border_t *def; -// -// b = OALLOC(env->obst, border_t); -// -// /* also allocate the def and tie it to the use. */ -// def = OALLOCZ(env->obst, border_t); -// b->other_end = def; -// def->other_end = b; -// -// /* -// * Set the link field of the irn to the def. -// * This strongly relies on the fact, that the use is always -// * made before the def. -// */ -// set_irn_link(irn, def); -// -// DEBUG_ONLY(b->magic = BORDER_FOURCC); -// DEBUG_ONLY(def->magic = BORDER_FOURCC); -// } else { -// /* -// * If the def is encountered, the use was made and so was the -// * the def node (see the code above). It was placed into the -// * link field of the irn, so we can get it there. -// */ -// b = get_irn_link(irn); -// -// DEBUG_ONLY(assert(b && b->magic == BORDER_FOURCC && "Illegal border encountered")); -// } -// -// b->pressure = pressure; -// b->is_def = is_def; -// b->is_real = is_real; -// b->irn = irn; -// b->step = step; -// list_add_tail(&b->list, head); -// DBG((dbg, LEVEL_5, "\t\t%s adding %+F, step: %d\n", is_def ? "def" : "use", irn, step)); -// -// -// return b; -//} - -///** -// * Check, if an irn is of the register class currently under processing. -// * @param env The chordal environment. -// * @param irn The node. -// * @return 1, if the node is of that register class, 0 if not. -// */ -//static inline int has_reg_class(const be_chordal_env_t *env, const ir_node *irn) -//{ -// return arch_irn_consider_in_reg_alloc(env->cls, irn); -//} - static int get_next_free_reg(const be_chordal_alloc_env_t *alloc_env, bitset_t *colors) { bitset_t *tmp = alloc_env->tmp_colors; bitset_copy(tmp, colors); - bitset_or(tmp, alloc_env->chordal_env->ignore_colors); - return bitset_next_clear(tmp, 0); + bitset_flip_all(tmp); + bitset_and(tmp, alloc_env->chordal_env->allocatable_regs); + return bitset_next_set(tmp, 0); } static bitset_t *get_decisive_partner_regs(bitset_t *bs, const be_operand_t *o1, const be_operand_t *o2) @@ -219,48 +126,48 @@ 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) { - int smallest = -1; - int smallest_n_regs = 2 * env->cls->n_regs + 1; - be_operand_t *out_op = &insn->ops[j]; + be_operand_t *smallest = NULL; + int smallest_n_regs = 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]; + int n_total; + be_operand_t *op = &insn->ops[i]; + be_lv_t *lv; if (op->partner != NULL) continue; - if (be_values_interfere(env->birg->lv, op->irn, op->carrier)) + lv = be_get_irg_liveness(env->irg); + if (be_values_interfere(lv, op->irn, op->carrier)) continue; - 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); + n_total = bitset_popcount(op->regs); if (!bitset_is_empty(bs) && n_total < smallest_n_regs) { - smallest = i; + smallest = op; smallest_n_regs = n_total; } } - if (smallest >= 0) { - be_operand_t *partner = &insn->ops[smallest]; + if (smallest != NULL) { for (i = insn->use_start; i < insn->n_ops; ++i) { - if (insn->ops[i].carrier == partner->carrier) + if (insn->ops[i].carrier == smallest->carrier) insn->ops[i].partner = out_op; } - out_op->partner = partner; - partner->partner = out_op; + out_op->partner = smallest; + smallest->partner = out_op; } } } static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, - ir_node *irn, int *silent) + ir_node *irn) { int n_regs; bitset_t *bs; @@ -269,7 +176,7 @@ static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, int *assignment; pmap *partners; int i, n_alloc; - bitset_pos_t col; + size_t col; const ir_edge_t *edge; ir_node *perm = NULL; //int match_res, cost; @@ -277,7 +184,6 @@ static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, void *base = obstack_base(env->obst); be_insn_t *insn = chordal_scan_insn(env, irn); ir_node *res = insn->next_insn; - int be_silent = *silent; bipartite_t *bp; if (insn->pre_colored) { @@ -286,19 +192,6 @@ static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier); } - /* - * If the current node is a barrier toggle the silent flag. - * If we are in the start block, we are ought to be silent at the beginning, - * so the toggling activates the constraint handling but skips the barrier. - * If we are in the end block we handle the in requirements of the barrier - * and set the rest to silent. - */ - if (be_is_Barrier(irn)) - *silent = !*silent; - - if (be_silent) - goto end; - /* * Perms inserted before the constraint handling phase are considered to be * correctly precolored. These Perms arise during the ABI handling phase. @@ -382,11 +275,12 @@ static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, foreach_out_edge(perm, edge) { int i; ir_node *proj = get_edge_src_irn(edge); + be_lv_t *lv = be_get_irg_liveness(env->irg); assert(is_Proj(proj)); - if (!be_values_interfere(env->birg->lv, proj, irn) - || pmap_contains(partners, proj)) + if (!be_values_interfere(lv, proj, irn) + || pmap_contains(partners, proj)) continue; /* don't insert a node twice */ @@ -404,10 +298,7 @@ static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, alloc_nodes[n_alloc] = proj; pmap_insert(partners, proj, NULL); - bitset_clear_all(bs); - arch_put_non_ignore_regs(env->cls, bs); - bitset_andnot(bs, env->ignore_colors); - bitset_foreach(bs, col) { + bitset_foreach(env->allocatable_regs, col) { //hungarian_add(bp, n_alloc, col, 1); bipartite_add(bp, n_alloc, col); } @@ -422,6 +313,7 @@ static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, match_res = hungarian_solve(bp, assignment, &cost, 1); assert(match_res == 0 && "matching failed"); #else + /*bipartite_dump_f(stderr, bp);*/ bipartite_matching(bp, assignment); #endif @@ -430,9 +322,8 @@ static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, const arch_register_t *reg; ir_node *irn; - assert(assignment[i] >= 0 && "there must have been a register assigned"); + assert(assignment[i] >= 0 && "there must have been a register assigned (node not register pressure faithful?)"); reg = arch_register_for_index(env->cls, assignment[i]); - assert(! (reg->type & arch_register_type_ignore)); irn = alloc_nodes[i]; if (irn != NULL) { @@ -441,7 +332,7 @@ static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", irn, reg->name)); } - irn = pmap_get(partners, alloc_nodes[i]); + irn = (ir_node*)pmap_get(partners, alloc_nodes[i]); if (irn != NULL) { arch_set_irn_register(irn, reg); (void) pset_hinsert_ptr(alloc_env->pre_colored, irn); @@ -498,33 +389,23 @@ end: */ static void constraints(ir_node *bl, void *data) { - /* - * Start silent in the start block. - * The silence remains until the first barrier is seen. - * Each other block is begun loud. - */ - int silent = bl == get_irg_start_block(get_irn_irg(bl)); - be_chordal_alloc_env_t *env = data; + be_chordal_alloc_env_t *env = (be_chordal_alloc_env_t*)data; ir_node *irn; - /* - * If the block is the start block search the barrier and - * start handling constraints from there. - */ for (irn = sched_first(bl); !sched_is_end(irn);) { - irn = handle_constraints(env, irn, &silent); + irn = handle_constraints(env, irn); } } static void assign(ir_node *block, void *env_ptr) { - be_chordal_alloc_env_t *alloc_env = env_ptr; + be_chordal_alloc_env_t *alloc_env = (be_chordal_alloc_env_t*)env_ptr; be_chordal_env_t *env = alloc_env->chordal_env; bitset_t *live = alloc_env->live; bitset_t *colors = alloc_env->colors; bitset_t *in_colors = alloc_env->in_colors; struct list_head *head = get_block_border_head(env, block); - be_lv_t *lv = env->birg->lv; + be_lv_t *lv = be_get_irg_liveness(env->irg); const ir_node *irn; border_t *b; @@ -582,7 +463,7 @@ static void assign(ir_node *block, void *env_ptr) */ if (b->is_def && !be_is_live_in(lv, block, irn)) { const arch_register_t *reg; - int col = NO_COLOR; + int col; if (ignore || pset_find_ptr(alloc_env->pre_colored, irn)) { reg = arch_get_irn_register(irn); @@ -592,7 +473,6 @@ static void assign(ir_node *block, void *env_ptr) col = get_next_free_reg(alloc_env, colors); reg = arch_register_for_index(env->cls, col); assert(arch_get_irn_register(irn) == NULL && "This node must not have been assigned a register yet"); - assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register"); } bitset_set(colors, col); @@ -610,11 +490,6 @@ static void assign(ir_node *block, void *env_ptr) assert(reg && "Register must have been assigned"); col = arch_register_get_index(reg); -#ifndef NDEBUG - if (!arch_register_type_is(reg, ignore)) { - assert(bitset_is_set(live, nr) && "Cannot have a non live use"); - } -#endif bitset_clear(colors, col); bitset_clear(live, nr); @@ -626,17 +501,12 @@ void be_ra_chordal_color(be_chordal_env_t *chordal_env) { be_chordal_alloc_env_t env; char buf[256]; - be_lv_t *lv; - be_irg_t *birg = chordal_env->birg; const arch_register_class_t *cls = chordal_env->cls; - int colors_n = arch_register_class_n_regs(cls); - ir_graph *irg = chordal_env->irg; - - lv = be_assure_liveness(birg); - be_liveness_assure_sets(lv); - be_liveness_assure_chk(lv); + int colors_n = arch_register_class_n_regs(cls); + ir_graph *irg = chordal_env->irg; + be_assure_live_sets(irg); assure_doms(irg); env.chordal_env = chordal_env; @@ -646,22 +516,22 @@ void be_ra_chordal_color(be_chordal_env_t *chordal_env) env.in_colors = bitset_alloca(colors_n); env.pre_colored = pset_new_ptr_default(); - BE_TIMER_PUSH(t_constr); + be_timer_push(T_CONSTR); /* Handle register targeting constraints */ dom_tree_walk_irg(irg, constraints, NULL, &env); if (chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) { - snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name); - be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched); + snprintf(buf, sizeof(buf), "%s-constr", chordal_env->cls->name); + dump_ir_graph(chordal_env->irg, buf); } - BE_TIMER_POP(t_constr); + be_timer_pop(T_CONSTR); env.live = bitset_malloc(get_irg_last_idx(chordal_env->irg)); /* First, determine the pressure */ - dom_tree_walk_irg(irg, pressure, NULL, env.chordal_env); + dom_tree_walk_irg(irg, create_borders, NULL, env.chordal_env); /* Assign the colors */ dom_tree_walk_irg(irg, assign, NULL, &env); @@ -678,15 +548,13 @@ void be_ra_chordal_color(be_chordal_env_t *chordal_env) del_pset(env.pre_colored); } +BE_REGISTER_MODULE_CONSTRUCTOR(be_init_chordal) void be_init_chordal(void) { - FIRM_DBG_REGISTER(dbg, "firm.be.chordal"); - static be_ra_chordal_coloring_t coloring = { be_ra_chordal_color }; + FIRM_DBG_REGISTER(dbg, "firm.be.chordal"); be_register_chordal_coloring("default", &coloring); } - -BE_REGISTER_MODULE_CONSTRUCTOR(be_init_chordal);