X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;ds=sidebyside;f=ir%2Fbe%2Fbechordal_common.c;h=a179117e56f9d117c01f3ba3a3900fb0a040d0a7;hb=552fbc58ec9d3f1623cee651661061c59f367b05;hp=62a5956ba30283824e150b582e4041b643415f90;hpb=6c3146b96bc65d9de18f3f2b59faf33b8b9935d6;p=libfirm diff --git a/ir/be/bechordal_common.c b/ir/be/bechordal_common.c index 62a5956ba..a179117e5 100644 --- a/ir/be/bechordal_common.c +++ b/ir/be/bechordal_common.c @@ -1,20 +1,6 @@ /* - * Copyright (C) 1995-2008 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. - * - * 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. + * Copyright (C) 2012 University of Karlsruhe. */ /** @@ -22,7 +8,6 @@ * @brief Common functions for chordal register allocation. * @author Sebastian Hack * @date 08.12.2004 - * @version $Id: bechordal.c 26750 2009-11-27 09:37:43Z bersch $ */ #include "config.h" @@ -35,10 +20,11 @@ #include "bechordal.h" #include "bechordal_t.h" +#include "beirg.h" #include "beirgmod.h" #include "beinsn_t.h" #include "besched.h" -#include "bestatevent.h" +#include "statev_t.h" #include "benode.h" #include "bemodule.h" #include "belive.h" @@ -50,11 +36,6 @@ DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;) /* Make a fourcc for border checking. */ #define BORDER_FOURCC FOURCC('B', 'O', 'R', 'D') -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 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) @@ -64,10 +45,10 @@ static inline border_t *border_add(be_chordal_env_t *env, struct list_head *head if (!is_def) { border_t *def; - b = OALLOC(env->obst, border_t); + b = OALLOC(&env->obst, border_t); /* also allocate the def and tie it to the use. */ - def = OALLOCZ(env->obst, border_t); + def = OALLOCZ(&env->obst, border_t); b->other_end = def; def->other_end = b; @@ -78,17 +59,17 @@ static inline border_t *border_add(be_chordal_env_t *env, struct list_head *head */ set_irn_link(irn, def); - DEBUG_ONLY(b->magic = BORDER_FOURCC); - DEBUG_ONLY(def->magic = BORDER_FOURCC); + 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); + b = (border_t*)get_irn_link(irn); - DEBUG_ONLY(assert(b && b->magic == BORDER_FOURCC && "Illegal border encountered")); + DEBUG_ONLY(assert(b && b->magic == BORDER_FOURCC && "Illegal border encountered");) } b->pressure = pressure; @@ -113,36 +94,31 @@ void create_borders(ir_node *block, void *env_ptr) #define border_use(irn, step, real) \ border_add(env, head, irn, step, ++pressure, 0, real) - be_chordal_env_t *env = env_ptr; - bitset_t *live = bitset_malloc(get_irg_last_idx(env->irg)); - ir_node *irn; - be_lv_t *lv = be_get_irg_liveness(env->irg); + be_chordal_env_t *const env = (be_chordal_env_t*)env_ptr; - int i, n; - unsigned elm; unsigned step = 0; unsigned pressure = 0; struct list_head *head; - bitset_clear_all(live); - /* Set up the border list in the block info */ - head = OALLOC(env->obst, struct list_head); + head = OALLOC(&env->obst, struct list_head); INIT_LIST_HEAD(head); - assert(pmap_get(env->border_heads, block) == NULL); + assert(pmap_get(struct list_head, env->border_heads, block) == NULL); pmap_insert(env->border_heads, block, head); + ir_nodeset_t live; + ir_nodeset_init(&live); + + be_lv_t *const lv = be_get_irg_liveness(env->irg); + /* * Make final uses of all values live out of the block. * They are necessary to build up real intervals. */ - be_lv_foreach(lv, block, be_lv_state_end, i) { - ir_node *irn = be_lv_get_irn(lv, block, i); - if (has_reg_class(env, 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); - } + be_lv_foreach_cls(lv, block, be_lv_state_end, env->cls, irn) { + DB((dbg, LEVEL_3, "\tMaking live: %+F\n", irn)); + ir_nodeset_insert(&live, irn); + border_use(irn, step, 0); } ++step; @@ -151,149 +127,89 @@ void create_borders(ir_node *block, void *env_ptr) * relevant for the interval borders. */ sched_foreach_reverse(block, irn) { - DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure)); - DBG((dbg, LEVEL_2, "\tlive: %B\n", live)); - - if (get_irn_mode(irn) == mode_T) { - const ir_edge_t *edge; - - foreach_out_edge(irn, edge) { - ir_node *proj = get_edge_src_irn(edge); + DB((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure)); - /* - * 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, proj)) { - int nr = get_irn_idx(proj); - - bitset_clear(live, nr); - border_def(proj, step, 1); - } - } - } else { + be_foreach_definition(irn, env->cls, def, req, /* * 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_idx(irn); - - bitset_clear(live, nr); - border_def(irn, step, 1); - } - } + ir_nodeset_remove(&live, def); + border_def(def, step, 1); + ); /* * If the node is no phi node we can examine the uses. */ if (!is_Phi(irn)) { - for (i = 0, n = get_irn_arity(irn); i < n; ++i) { - ir_node *op = get_irn_n(irn, i); + be_foreach_use(irn, env->cls, in_req_, op, op_req_, + const char *msg = "-"; - if (has_reg_class(env, 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)); + if (ir_nodeset_insert(&live, op)) { + border_use(op, step, 1); + msg = "X"; } - } + + DB((dbg, LEVEL_4, "\t\t%s pos: %d, use: %+F\n", msg, i_, op)); + ); } ++step; } - bitset_foreach(live, elm) { - ir_node *irn = get_idx_irn(env->irg, elm); - if (be_is_live_in(lv, block, irn)) - border_def(irn, step, 0); + foreach_ir_nodeset(&live, irn, iter) { + assert(be_is_live_in(lv, block, irn)); + border_def(irn, step, 0); } - bitset_free(live); -} - - -be_insn_t *chordal_scan_insn(be_chordal_env_t *env, ir_node *irn) -{ - be_insn_env_t ie; - - ie.allocatable_regs = env->allocatable_regs; - ie.obst = env->obst; - ie.cls = env->cls; - return be_scan_insn(&ie, irn); + ir_nodeset_destroy(&live); } ir_node *pre_process_constraints(be_chordal_env_t *env, be_insn_t **the_insn) { - be_insn_t *insn = *the_insn; - ir_node *perm = NULL; - bitset_t *out_constr = bitset_alloca(env->cls->n_regs); - const ir_edge_t *edge; - int i; - - assert(insn->has_constraints && "only do this for constrained nodes"); - - /* - * Collect all registers that occur in output constraints. - * This is necessary, since if the insn has one of these as an input constraint - * and the corresponding operand interferes with the insn, the operand must - * be copied. - */ - for (i = 0; i < insn->use_start; ++i) { - be_operand_t *op = &insn->ops[i]; - if (op->has_constraints) - bitset_or(out_constr, op->regs); - } + be_insn_t *insn = *the_insn; /* * 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(env->irg, env->cls, sched_prev(insn->irn)); + ir_node *const irn = insn->irn; + ir_node *const perm = insert_Perm_before(env->irg, env->cls, irn); - /* Registers are propagated by insert_Perm_after(). Clean them here! */ + /* Registers are propagated by insert_Perm_before(). Clean them here! */ if (perm == NULL) return NULL; - be_stat_ev("constr_perm", get_irn_arity(perm)); - foreach_out_edge(perm, edge) { - ir_node *proj = get_edge_src_irn(edge); - arch_set_irn_register(proj, NULL); - } + stat_ev_int("constr_perm", get_irn_arity(perm)); /* * We also have to re-build the insn since the input operands are now the Projs of * the Perm. Recomputing liveness is also a good idea if a Perm is inserted, since * the live sets may change. */ - obstack_free(env->obst, insn); - *the_insn = insn = chordal_scan_insn(env, insn->irn); - - /* - * Copy the input constraints of the insn to the Perm as output - * constraints. Succeeding phases (coalescing) will need that. - */ - for (i = insn->use_start; i < insn->n_ops; ++i) { - be_operand_t *op = &insn->ops[i]; - ir_node *proj = op->carrier; - /* - * Note that the predecessor must not be a Proj of the Perm, - * since ignore-nodes are not Perm'ed. - */ - if (op->has_constraints && is_Proj(proj) && get_Proj_pred(proj) == perm) { - be_set_constr_out(perm, get_Proj_proj(proj), op->req); - } + obstack_free(&env->obst, insn); + *the_insn = insn = be_scan_insn(env, irn); + + /* Copy the input constraints of the irn to the Perm as output + * constraints. Succeeding phases (coalescing) will need that. */ + for (int i = 0, n = get_irn_arity(irn); i != n; ++i) { + ir_node *const proj = get_irn_n(irn, i); + /* Note that the predecessor is not necessarily a Proj of the Perm, + * since ignore-nodes are not Perm'ed. */ + if (!is_Proj(proj) || get_Proj_pred(proj) != perm) + continue; + /* FIXME: Only setting the constraints, when the register requirement is + * limited, is a hack. It will break when multiple differently constrained + * inputs use the same value. */ + arch_register_req_t const *const req = arch_get_irn_register_req_in(irn, i); + if (!arch_register_req_is(req, limited)) + continue; + be_set_constr_out(perm, get_Proj_proj(proj), req); } return perm; } -BE_REGISTER_MODULE_CONSTRUCTOR(be_init_chordal_common); +BE_REGISTER_MODULE_CONSTRUCTOR(be_init_chordal_common) void be_init_chordal_common(void) { FIRM_DBG_REGISTER(dbg, "firm.be.chordal_common");