From 93e10ae9191c0247b78772c2611b753decedb917 Mon Sep 17 00:00:00 2001 From: Sebastian Hack Date: Fri, 13 Jan 2006 15:00:29 +0000 Subject: [PATCH] Third fix --- ir/be/bechordal.c | 130 ++++++++++++++++++++++--------------------- ir/be/beconstrperm.c | 103 +++++++++++++++++++--------------- 2 files changed, 124 insertions(+), 109 deletions(-) diff --git a/ir/be/bechordal.c b/ir/be/bechordal.c index e7950b646..adcf8d9d3 100644 --- a/ir/be/bechordal.c +++ b/ir/be/bechordal.c @@ -165,6 +165,35 @@ static INLINE int has_reg_class(const be_chordal_env_t *env, const ir_node *irn) #define has_limited_constr(req, irn) \ (arch_get_register_req(arch_env, (req), irn, -1) && (req)->type == arch_register_req_type_limited) +static int try_pre_color(be_chordal_env_t *env, ir_node *irn, + pset *pre_colored, bitset_t *colors_used) +{ + arch_register_req_t req; + + if(arch_get_register_req(env->main_env->arch_env, &req, irn, -1) + && req.type == arch_register_req_type_limited) { + + bitset_t *bs = bitset_alloca(env->cls->n_regs); + const arch_register_t *reg; + int col; + + req.data.limited(irn, -1, bs); + col = bitset_next_set(bs, 0); + reg = arch_register_for_index(env->cls, col); + + pset_insert_ptr(pre_colored, irn); + arch_set_irn_register(env->main_env->arch_env, irn, reg); + + bitset_set(colors_used, col); + + DBG((env->dbg, LEVEL_2, "pre coloring %+F with %s\n", irn, reg->name)); + + return 1; + } + + return 0; +} + /** * Handle register targeting constraints signaled by a Perm. * @param alloc_env Private data for the allocation phase. @@ -232,13 +261,10 @@ static ir_node *handle_constraints_at_perm(be_chordal_alloc_env_t *alloc_env, ir const arch_env_t *arch_env = env->main_env->arch_env; pset *leftover = pset_new_ptr(8); - bitset_t *bs = bitset_alloca(env->cls->n_regs); + pset *pre_colored = pset_new_ptr(8); bitset_t *colors_used = bitset_alloca(env->cls->n_regs); - ir_node *irn, *cnstr; + ir_node *irn, *cnstr, *last; int has_cnstr = 0; - int col; - arch_register_req_t req; - const arch_register_t *reg, *cnstr_reg = NULL; assert(be_is_Perm(perm)); @@ -247,82 +273,58 @@ static ir_node *handle_constraints_at_perm(be_chordal_alloc_env_t *alloc_env, ir /* * Color constrained Projs first. */ - for(irn = sched_next(perm); is_Proj(irn); irn = sched_next(irn)) { - arch_register_req_t req; - - if(has_limited_constr(&req, irn)) { - bitset_clear_all(bs); - req.data.limited(irn, -1, bs); - col = bitset_next_set(bs, 0); - reg = arch_register_for_index(env->cls, col); - - pset_insert_ptr(alloc_env->pre_colored, irn); - arch_set_irn_register(arch_env, irn, reg); - bitset_set(colors_used, col); - - DBG((dbg, LEVEL_2, "\tPerm Proj with constraints: %+F set to %s\n", irn, reg->name)); - } - - else + for(irn = sched_next(perm); is_Proj(irn); irn = sched_next(irn)) + if(!try_pre_color(env, irn, pre_colored, colors_used)) pset_insert_ptr(leftover, irn); - } cnstr = irn; + last = irn; - if(has_limited_constr(&req, cnstr)) { - bitset_clear_all(bs); - req.data.limited(cnstr, -1, bs); - col = bitset_next_set(colors_used, 0); - reg = arch_register_for_index(env->cls, col); - - arch_set_irn_register(arch_env, cnstr, reg); - pset_insert_ptr(alloc_env->pre_colored, cnstr); + if(get_irn_mode(cnstr) == mode_T) { + for(irn = sched_next(cnstr); is_Proj(irn); irn = sched_next(irn)) + if(!try_pre_color(env, irn, pre_colored, colors_used)) + pset_insert_ptr(leftover, irn); - DBG((dbg, LEVEL_2, "\tConstrained node: %+F set to %s\n", irn, reg->name)); + last = sched_prev(irn); + } - /* - * The color of the constrained node must not be used! - * The Proj which has been assigned that color might - * interfere with the constrained node which leads - * to an invalid register allocation. - */ - assert(!bitset_is_set(colors_used, reg->index)); + else + try_pre_color(env, cnstr, pre_colored, colors_used); - /* - * Look for a Proj not interfering with the constrained node. - * This Proj can be safely set to the constrafined nodes - * color. - */ - for(irn = pset_first(leftover); irn; irn = pset_next(leftover)) { - if(!values_interfere(irn, cnstr)) { + for(irn = pset_first(leftover); irn; irn = pset_next(leftover)) { + const arch_register_t *reg; + ir_node *precol; + int colored = 0; - DBG((dbg, LEVEL_2, "\tFound Proj not interfering with contr node %+F set to %s\n", irn, reg->name)); - pset_insert_ptr(alloc_env->pre_colored, irn); + for(precol = pset_first(pre_colored); precol; precol = pset_next(pre_colored)) { + if(!values_interfere(irn, precol)) { + reg = arch_get_irn_register(arch_env, irn); arch_set_irn_register(arch_env, irn, reg); - bitset_set(colors_used, reg->index); - pset_remove_ptr(leftover, irn); - pset_break(leftover); + pset_break(pre_colored); + colored = 1; break; } } - } - /* - * Color the leftover Projs with the leftover colors. - */ - for(irn = pset_first(leftover); irn; irn = pset_next(leftover)) { - col = bitset_next_clear(colors_used, 0); - reg = arch_register_for_index(env->cls, col); + if(!colored) { + int col = bitset_next_clear(colors_used, 0); - arch_set_irn_register(arch_env, irn, reg); - pset_insert_ptr(alloc_env->pre_colored, irn); - bitset_set(colors_used, col); + assert(col >=0 && "There must be a register left"); + reg = arch_register_for_index(env->cls, col); + arch_set_irn_register(arch_env, irn, reg); + bitset_set(colors_used, reg->index); + pset_insert_ptr(alloc_env->pre_colored, irn); - DBG((dbg, LEVEL_2, "\tLeft over %+F set to %s\n", irn, reg->name)); + DBG((dbg, LEVEL_2, "coloring leftover %+F with %s\n", irn, reg->name)); + } } + pset_insert_pset_ptr(alloc_env->pre_colored, pre_colored); + del_pset(leftover); - return cnstr; + del_pset(pre_colored); + + return last; } /** @@ -339,7 +341,7 @@ static void constraints(ir_node *bl, void *data) ir_node *irn; for(irn = sched_first(bl); !sched_is_end(irn); irn = sched_next(irn)) { - if(be_is_Perm(irn)) + if(be_is_Perm(irn) && arch_irn_has_reg_class(arch_env, irn, 0, env->chordal_env->cls)) irn = handle_constraints_at_perm(env, irn); } } diff --git a/ir/be/beconstrperm.c b/ir/be/beconstrperm.c index 92311a265..d6d982124 100644 --- a/ir/be/beconstrperm.c +++ b/ir/be/beconstrperm.c @@ -1,5 +1,5 @@ /** - * Author: Daniel Grund + * Author: Daniel Grund, Sebastian Hack * Date: 15.12.2005 * Copyright: (c) Universitaet Karlsruhe * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. @@ -19,62 +19,75 @@ #include "besched_t.h" #include "beconstrperm.h" -static void walker_insert_constr_perms(ir_node *bl, void *env) { - ir_node *irn; - int pos, max, cnt = 0; - arch_register_req_t req; - ir_graph *irg = get_irn_irg(bl); - be_chordal_env_t *cenv = env; +static void check_constraints(const be_chordal_env_t *cenv, ir_node *base, ir_node *irn, ir_node **perm) +{ + const arch_env_t *aenv = cenv->main_env->arch_env; const be_main_env_t *menv = cenv->main_env; - const arch_env_t *aenv = menv->arch_env; + arch_register_req_t req; + int pos, n; - sched_foreach(bl, irn) { - ir_node *perm = NULL; + assert(is_Proj(irn) || (base == irn)); - /* check for a restriction of the result (-1) or one of the operands (0..n) */ - max = get_irn_arity(irn); - for(pos=-1; poscls == arch_get_irn_reg_class(aenv, irn, pos) && req.type == arch_register_req_type_limited) { + if(arch_irn_has_reg_class(aenv, irn, pos, cenv->cls) && req.type == arch_register_req_type_limited) { - /* - * If we inserted a perm, - * we have to recompute liveness analysis since inserting - * a Perm changes the liveness situation at the end - * of the block. - * (its needed by successive calls to insert_Perm_after) - * Perhaps thinking about an online liveness analysis - * would help. - */ - if(!perm) { - perm = insert_Perm_after(menv, cenv->cls, cenv->dom_front, sched_prev(irn)); - be_liveness(irg); - } + /* + * If we inserted a perm, + * we have to recompute liveness analysis since inserting + * a Perm changes the liveness situation at the end + * of the block. + * (its needed by successive calls to insert_Perm_after) + * Perhaps thinking about an online liveness analysis + * would help. + */ + if(*perm == NULL) { + *perm = insert_Perm_after(menv, cenv->cls, cenv->dom_front, sched_prev(base)); + be_liveness(cenv->irg); + } + + /* + * Turn an input constraint into an output constraint: + * The Proj of the Perm which corresponds to the input + * constraint will have the input constraint of the node + * as an output constraint + */ + if(pos >= 0) { + ir_node *op = get_irn_n(irn, pos); /* - * Turn an input constraint into an output constraint: - * The Proj of the Perm which corresponds to the input - * constraint will have the input constraint of the node - * as an output constraint - */ - if(pos >= 0) { - ir_node *op = get_irn_n(irn, pos); - - /* - * The operand must be a proj now, since a perm cut - * all live ranges. - */ - assert(is_Proj(op)); - be_set_Perm_out_req(perm, get_Proj_proj(op), &req); - } + * The operand must be a proj now, since a perm cut + * all live ranges. + */ + assert(is_Proj(op)); + be_set_Perm_out_req(*perm, get_Proj_proj(op), &req); } } } } +static void walker_insert_constr_perms(ir_node *bl, void *env) { + be_chordal_env_t *cenv = env; + ir_node *irn; + + for(irn = sched_first(bl); !sched_is_end(irn); irn = sched_next(irn)) { + ir_node *perm = NULL; + + if(get_irn_mode(irn) == mode_T) { + ir_node *proj; + + for(proj = sched_next(irn); is_Proj(proj); proj = sched_next(proj)) + check_constraints(cenv, irn, proj, &perm); + + irn = sched_prev(proj); + } + + else + check_constraints(cenv, irn, irn, &perm); + } +} + void be_insert_constr_perms(be_chordal_env_t *cenv) { irg_block_walk_graph(cenv->irg, walker_insert_constr_perms, NULL, cenv); } -- 2.20.1