X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbechordal.c;h=2000c28f848ef6dfdf8499d63209a245e2ccde89;hb=9276447aec4972df060349e162f583c4898dfec8;hp=0f2b6a4fcedd6277db1c95569a9083a4e7e3a35d;hpb=bad0a6217eda4cd4120aa4ed08a048cc8ef4f057;p=libfirm diff --git a/ir/be/bechordal.c b/ir/be/bechordal.c index 0f2b6a4fc..2000c28f8 100644 --- a/ir/be/bechordal.c +++ b/ir/be/bechordal.c @@ -1,22 +1,31 @@ -/** - * Chordal register allocation. - * @author Sebastian Hack - * @date 8.12.2004 - * @cvs-id $Id$ +/* + * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved. + * + * This file is part of libFirm. + * + * This file may be distributed and/or modified under the terms of the + * GNU General Public License version 2 as published by the Free Software + * Foundation and appearing in the file LICENSE.GPL included in the + * packaging of this file. * - * Copyright (C) Universitaet Karlsruhe - * Released under the GPL + * Licensees holding valid libFirm Professional Edition licenses may use + * this file in accordance with the libFirm Commercial License. + * Agreement provided with the Software. + * + * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE + * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE. */ -#ifdef HAVE_CONFIG_H -#include -#endif -#ifdef HAVE_MALLOC_H -#include -#endif - -#ifdef HAVE_ALLOCA_H -#include +/** + * @file + * @brief Chordal register allocation. + * @author Sebastian Hack + * @date 08.12.2004 + * @version $Id$ + */ +#ifdef HAVE_CONFIG_H +#include "config.h" #endif #include @@ -37,31 +46,37 @@ #include "irdump.h" #include "irdom.h" #include "irtools.h" +#include "irbitset.h" #include "debug.h" #include "xmalloc.h" +#include "iredges.h" #include "beutil.h" #include "besched.h" #include "besched_t.h" #include "belive_t.h" #include "benode_t.h" -#include "bearch.h" +#include "bearch_t.h" #include "beirgmod.h" #include "beifg.h" #include "beinsn_t.h" #include "bestatevent.h" #include "beirg_t.h" - +#include "beintlive_t.h" +#include "bera.h" #include "bechordal_t.h" #include "bechordal_draw.h" +#include "bemodule.h" -#define DBG_LEVEL SET_LEVEL_0 -#define DBG_LEVEL_CHECK SET_LEVEL_0 +DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;) #define NO_COLOR (-1) #define DUMP_INTERVALS +/* new style assign routine without borders. */ +#undef NEW_STYLE_ASSIGN + typedef struct _be_chordal_alloc_env_t { be_chordal_env_t *chordal_env; @@ -71,7 +86,6 @@ typedef struct _be_chordal_alloc_env_t { bitset_t *colors; /**< The color mask. */ bitset_t *in_colors; /**< Colors used by live in values. */ int colors_n; /**< The number of colors. */ - DEBUG_ONLY(firm_dbg_module_t *constr_dbg;) /**< Debug output for the constraint handler. */ } be_chordal_alloc_env_t; #include "fourcc.h" @@ -119,10 +133,10 @@ static INLINE border_t *border_add(be_chordal_env_t *env, struct list_head *head if(!is_def) { border_t *def; - b = obstack_alloc(&env->obst, sizeof(*b)); + b = obstack_alloc(env->obst, sizeof(*b)); /* also allocate the def and tie it to the use. */ - def = obstack_alloc(&env->obst, sizeof(*def)); + def = obstack_alloc(env->obst, sizeof(*def)); memset(def, 0, sizeof(*def)); b->other_end = def; def->other_end = b; @@ -155,7 +169,7 @@ static INLINE border_t *border_add(be_chordal_env_t *env, struct list_head *head b->irn = irn; b->step = step; list_add_tail(&b->list, head); - DBG((env->dbg, LEVEL_5, "\t\t%s adding %+F, step: %d\n", is_def ? "def" : "use", irn, step)); + DBG((dbg, LEVEL_5, "\t\t%s adding %+F, step: %d\n", is_def ? "def" : "use", irn, step)); return b; @@ -169,8 +183,7 @@ 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->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); + return arch_irn_consider_in_reg_alloc(env->birg->main_env->arch_env, env->cls, irn); } #define has_limited_constr(req, irn) \ @@ -216,14 +229,15 @@ static be_insn_t *chordal_scan_insn(be_chordal_env_t *env, ir_node *irn) ie.ignore_colors = env->ignore_colors; ie.aenv = env->birg->main_env->arch_env; - ie.obst = &env->obst; + 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) { - const arch_env_t *aenv = env->birg->main_env->arch_env; + const be_irg_t *birg = env->birg; + const arch_env_t *aenv = birg->main_env->arch_env; bitset_t *tmp = bitset_alloca(env->cls->n_regs); bitset_t *def_constr = bitset_alloca(env->cls->n_regs); ir_node *bl = get_nodes_block(irn); @@ -260,7 +274,7 @@ static ir_node *prepare_constr_insn(be_chordal_env_t *env, ir_node *irn) 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)); + DBG((dbg, LEVEL_3, "inserting ignore arg copy %+F for %+F pos %d\n", copy, irn, i)); } insn = chordal_scan_insn(env, irn); @@ -287,7 +301,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, 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)); + DBG((dbg, LEVEL_3, "inserting multiple constr copy %+F for %+F pos %d\n", copy, insn->irn, a_op->pos)); } } @@ -316,7 +330,7 @@ static ir_node *prepare_constr_insn(be_chordal_env_t *env, ir_node *irn) 3) is constrained to a register occuring in out constraints. */ if(!op->has_constraints || - !values_interfere(lv, insn->irn, op->carrier) || + !values_interfere(birg, insn->irn, op->carrier) || bitset_popcnt(tmp) == 0) continue; @@ -333,12 +347,12 @@ 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)); + DBG((dbg, LEVEL_3, "inserting constr copy %+F for %+F pos %d\n", copy, insn->irn, op->pos)); be_liveness_update(lv, op->carrier); } end: - obstack_free(&env->obst, insn); + obstack_free(env->obst, insn); return insn->next_insn; } @@ -363,7 +377,6 @@ 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; @@ -383,7 +396,7 @@ static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, be_insn_t if (op->partner != NULL) continue; - if (values_interfere(lv, op->irn, op->carrier)) + if (values_interfere(env->birg, op->irn, op->carrier)) continue; bitset_clear_all(bs); @@ -414,7 +427,6 @@ static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env, be_insn_t *insn = *the_insn; ir_node *perm = NULL; bitset_t *out_constr = bitset_alloca(env->cls->n_regs); - be_lv_t *lv = env->birg->lv; const ir_edge_t *edge; int i; @@ -436,7 +448,7 @@ static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env, 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, lv, env->cls, env->birg->dom_front, sched_prev(insn->irn)); + perm = insert_Perm_after(env->birg, env->cls, sched_prev(insn->irn)); /* Registers are propagated by insert_Perm_after(). Clean them here! */ if(perm == NULL) @@ -454,7 +466,7 @@ static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env, the live sets may change. */ // be_liveness_recompute(lv); - obstack_free(&env->obst, insn); + obstack_free(env->obst, insn); *the_insn = insn = chordal_scan_insn(env, insn->irn); /* @@ -485,18 +497,17 @@ static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *i hungarian_problem_t *bp; int *assignment; pmap *partners; - DEBUG_ONLY(firm_dbg_module_t *dbg); int i, n_alloc; long col; const ir_edge_t *edge; ir_node *perm = NULL; int match_res, cost; be_chordal_env_t *env = alloc_env->chordal_env; - void *base = obstack_base(&env->obst); + 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; - be_lv_t *lv = env->birg->lv; + be_irg_t *birg = env->birg; if(insn->pre_colored) { int i; @@ -532,7 +543,6 @@ static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *i // bipartite_t *bp = bipartite_new(n_regs, n_regs); assignment = alloca(n_regs * sizeof(assignment[0])); partners = pmap_create(); - DEBUG_ONLY(dbg = alloc_env->constr_dbg;) /* prepare the constraint handling of this node. @@ -588,7 +598,7 @@ static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *i assert(is_Proj(proj)); - if(!values_interfere(lv, proj, irn) || pmap_contains(partners, proj)) + if(!values_interfere(birg, proj, irn) || pmap_contains(partners, proj)) continue; assert(n_alloc < n_regs); @@ -671,7 +681,7 @@ static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *i pmap_destroy(partners); end: - obstack_free(&env->obst, base); + obstack_free(env->obst, base); return res; } @@ -725,7 +735,6 @@ static void pressure(ir_node *block, void *env_ptr) 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; @@ -738,7 +747,7 @@ static void pressure(ir_node *block, void *env_ptr) bitset_clear_all(live); /* Set up the border list in the block info */ - head = obstack_alloc(&env->obst, sizeof(*head)); + head = obstack_alloc(env->obst, sizeof(*head)); INIT_LIST_HEAD(head); assert(pmap_get(env->border_heads, block) == NULL); pmap_insert(env->border_heads, block, head); @@ -831,7 +840,6 @@ static void assign(ir_node *block, void *env_ptr) const ir_node *irn; border_t *b; - DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;) bitset_clear_all(colors); bitset_clear_all(live); @@ -914,7 +922,11 @@ static void assign(ir_node *block, void *env_ptr) assert(reg && "Register must have been assigned"); col = arch_register_get_index(reg); - assert(bitset_is_set(live, nr) && "Cannot have a non live use"); +#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); @@ -924,15 +936,143 @@ static void assign(ir_node *block, void *env_ptr) del_pset(live_in); } +/** + * A new assign... + */ +static void assign_new(ir_node *block, be_chordal_alloc_env_t *alloc_env, bitset_t *live_end_dom) +{ + be_chordal_env_t *env = alloc_env->chordal_env; + bitset_t *colors = alloc_env->colors; + bitset_t *in_colors = alloc_env->in_colors; + bitset_t *live = bitset_irg_malloc(env->irg); + const arch_env_t *arch_env = env->birg->main_env->arch_env; + be_irg_t *birg = env->birg; + lv_chk_t *lv = be_get_birg_liveness_chk(birg); + + bitset_pos_t elm; + ir_node *irn; + + bitset_clear_all(colors); + bitset_clear_all(in_colors); + + /* + * All variables which are live in to this block are live out + * of the immediate dominator thanks to SSA properties. As we + * have already visited the immediate dominator, we know these + * variables. The only tjing left is to check wheather they are live + * in here (they also could be phi arguments to some ohi not + * in this block, hence we have to check). + */ + bitset_foreach (live_end_dom, elm) { + ir_node *irn = get_idx_irn(env->irg, elm); + if (lv_chk_bl_in(lv, block, irn)) { + const arch_register_t *reg = arch_get_irn_register(arch_env, irn); + int col; + + assert(be_is_live_in(env->birg->lv, block, irn)); + 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, elm); + } + + else { + assert(!be_is_live_in(env->birg->lv, block, irn)); + } + } + + /* + * Mind that the sequence of defs from back to front defines a perfect + * elimination order. So, coloring the definitions from first to last + * will work. + */ + sched_foreach (block, irn) { + int nr = get_irn_idx(irn); + int ignore = arch_irn_is(arch_env, irn, ignore); + + /* Clear the color upon a last use. */ + if(!is_Phi(irn)) { + int i; + for (i = get_irn_arity(irn) - 1; i >= 0; --i) { + ir_node *op = get_irn_n(irn, i); + + /* + * If the reg class matches and the operand is not live after + * the node, irn is a last use of op and the register can + * be freed. + */ + if (has_reg_class(env, op)) { + if (!be_lv_chk_after_irn(birg, op, irn)) { + const arch_register_t *reg = arch_get_irn_register(arch_env, op); + int col; + + assert(reg && "Register must have been assigned"); + col = arch_register_get_index(reg); + bitset_clear(colors, col); + bitset_clear(live, nr); + } + } + } + } + + if (has_reg_class(env, irn)) { + const arch_register_t *reg; + int col = NO_COLOR; + + /* + * Assign a color, if it is a local def. Global defs already have a + * color. + */ + if(ignore || pset_find_ptr(alloc_env->pre_colored, irn)) { + reg = arch_get_irn_register(arch_env, irn); + col = reg->index; + assert(!bitset_is_set(colors, col) && "pre-colored register must be free"); + } else { + col = get_next_free_reg(alloc_env, colors); + reg = arch_register_for_index(env->cls, col); + assert(arch_get_irn_register(arch_env, 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); + 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)); + + assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered"); + bitset_set(live, nr); + } + + } + + dominates_for_each (block, irn) { + assign_new(irn, alloc_env, live); + } + + bitset_free(live); +} + 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; + const arch_register_class_t *cls = chordal_env->cls; - int colors_n = arch_register_class_n_regs(chordal_env->cls); + int colors_n = arch_register_class_n_regs(cls); ir_graph *irg = chordal_env->irg; + int allocatable_regs = colors_n - be_put_ignore_regs(birg, cls, NULL); + /* some special classes contain only ignore regs, no work to be done */ + if(allocatable_regs == 0) + return; be_assure_dom_front(birg); be_assure_liveness(birg); @@ -944,8 +1084,6 @@ void be_ra_chordal_color(be_chordal_env_t *chordal_env) env.tmp_colors = bitset_alloca(colors_n); env.in_colors = bitset_alloca(colors_n); env.pre_colored = pset_new_ptr_default(); - FIRM_DBG_REGISTER(env.constr_dbg, "firm.be.chordal.constr"); - /* Handle register targeting constraints */ dom_tree_walk_irg(irg, constraints, NULL, &env); @@ -961,7 +1099,11 @@ void be_ra_chordal_color(be_chordal_env_t *chordal_env) dom_tree_walk_irg(irg, pressure, NULL, &env); /* Assign the colors */ +#ifdef NEW_STYLE_ASSIGN + assign_new(get_irg_start_block(irg), &env, env.live); +#else dom_tree_walk_irg(irg, assign, NULL, &env); +#endif if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) { plotter_t *plotter; @@ -974,3 +1116,10 @@ void be_ra_chordal_color(be_chordal_env_t *chordal_env) bitset_free(env.live); del_pset(env.pre_colored); } + +void be_init_chordal(void) +{ + FIRM_DBG_REGISTER(dbg, "firm.be.chordal"); +} + +BE_REGISTER_MODULE_CONSTRUCTOR(be_init_chordal);