X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbespill.c;h=7dd59cd999f95f7f2aade6b37eceaee5ee4e852a;hb=3c3425a50a1d721b74a015c6812257e32feeac85;hp=00d0dc340726d35257d41386120065bdbc1295f6;hpb=6165d2a9406fcc89959cc52a312eaff7bfd99c1b;p=libfirm diff --git a/ir/be/bespill.c b/ir/be/bespill.c index 00d0dc340..7dd59cd99 100644 --- a/ir/be/bespill.c +++ b/ir/be/bespill.c @@ -1,113 +1,281 @@ +/* + * 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. + */ + /** - * Author: Daniel Grund - * Date: 29.09.2005 - * Copyright: (c) Universitaet Karlsruhe - * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + * @file + * @brief Spill module selection; Preparation steps + * @author Matthias Braun + * @date 29.09.2005 */ +#include "config.h" -#include "pset.h" -#include "irnode_t.h" -#include "ircons_t.h" +#include "irtools.h" +#include "debug.h" +#include "iredges_t.h" +#include "raw_bitset.h" +#include "statev.h" +#include "irgwalk.h" -#include "besched.h" #include "bespill.h" -#include "benode_t.h" - -typedef struct _spill_ctx_t { - ir_node *spilled; /**< The spilled node. */ - ir_node *user; /**< The node this spill is for. */ - ir_node *spill; /**< The spill itself. */ -} spill_ctx_t; - -int be_set_cmp_spillctx(const void *a, const void *b, size_t n) { - const spill_ctx_t *p = a; - const spill_ctx_t *q = b; - return !(p->user == q->user && p->spilled == q->spilled); -} +#include "bemodule.h" +#include "be.h" +#include "belive_t.h" +#include "beirg.h" +#include "bearch.h" +#include "benode.h" +#include "besched.h" +#include "bera.h" +#include "beintlive_t.h" -static spill_ctx_t *be_get_spill_ctx(set *sc, ir_node *to_spill, ir_node *ctx_irn) { - spill_ctx_t templ; +#include "lc_opts.h" +#include "lc_opts_enum.h" - templ.spilled = to_spill; - templ.user = ctx_irn; - templ.spill = NULL; +DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;) - return set_insert(sc, &templ, sizeof(templ), HASH_COMBINE(HASH_PTR(to_spill), HASH_PTR(ctx_irn))); -} +typedef struct be_pre_spill_env_t { + ir_graph *irg; + const arch_register_class_t *cls; +} be_pre_spill_env_t; + +static void prepare_constr_insn(be_pre_spill_env_t *env, ir_node *node) +{ + const arch_register_class_t *cls = env->cls; + ir_node *block = get_nodes_block(node); + const ir_graph *irg = env->irg; + be_irg_t *birg = be_birg_from_irg(irg); + be_lv_t *lv = be_get_irg_liveness(irg); + unsigned *tmp = NULL; + unsigned *def_constr = NULL; + int arity = get_irn_arity(node); + ir_node *def; -static ir_node *be_spill_irn(spill_env_t *senv, ir_node *irn, ir_node *ctx_irn) { - spill_ctx_t *ctx; -// DBG((dbg, DBG_SPILL, "spill_irn %+F\n", irn)); + int i, i2; - ctx = be_get_spill_ctx(senv->spill_ctxs, irn, ctx_irn); - if(!ctx->spill) { - const be_main_env_t *env = senv->session->main_env; - ctx->spill = be_spill(env->node_factory, env->arch_env, irn); + /* Insert a copy for constraint inputs attached to a value which can't + * fulfill the constraint + * (typical example: stack pointer as input to copyb) + * TODO: This really just checks precolored registers at the moment and + * ignores the general case of not matching in/out constraints + */ + for (i = 0; i < arity; ++i) { + ir_node *op = get_irn_n(node, i); + const arch_register_req_t *req = arch_get_irn_register_req_in(node, i); + const arch_register_t *reg; + ir_node *copy; + + if (req->cls != cls) + continue; + reg = arch_get_irn_register(op); + if (reg == NULL) + continue; + + /* precolored with an ignore register (which is not a joker like + unknown/noreg) */ + if ((reg->type & arch_register_type_joker) || + rbitset_is_set(birg->allocatable_regs, reg->global_index)) + continue; + + if (! (req->type & arch_register_req_type_limited)) + continue; + if (rbitset_is_set(req->limited, reg->index)) + continue; + + copy = be_new_Copy(block, op); + stat_ev_int("constr_copy", 1); + sched_add_before(node, copy); + set_irn_n(node, i, copy); + DBG((dbg, LEVEL_3, "inserting ignore arg copy %+F for %+F pos %d\n", + copy, node, i)); } - return ctx->spill; -} + /* insert copies for nodes that occur constrained more than once. */ + for (i = 0; i < arity; ++i) { + ir_node *in; + ir_node *copy; + const arch_register_req_t *req; -/** - * If the first usage of a phi result would be out of memory - * there is no sense in allocating a register for it. - * Thus we spill it and all its operands to the same spill slot. - * Therefore the phi/dataB becomes a phi/Memory - */ -static ir_node *be_spill_phi(spill_env_t *senv, ir_node *phi, ir_node *ctx_irn) { - int i, n = get_irn_arity(phi); - ir_node **ins, *bl = get_nodes_block(phi); - ir_graph *irg = get_irn_irg(bl); - spill_ctx_t *ctx; - - assert(is_Phi(phi)); -// DBG((dbg, DBG_SPILL, "spill_phi %+F\n", phi)); - - /* search an existing spill for this context */ - ctx = be_get_spill_ctx(senv->spill_ctxs, phi, ctx_irn); - - /* if not found spill the phi */ - if(!ctx->spill) { - /* build a new PhiM with dummy in-array */ - ins = malloc(n * sizeof(ins[0])); - for(i=0; ispill = new_r_Phi(senv->session->irg, bl, n, ins, mode_M); - free(ins); - - /* re-wire the phiM */ - for(i=0; imem_phis, arg)) - sub_res = be_spill_phi(senv, arg, ctx_irn); - else - sub_res = be_spill_irn(senv, arg, ctx_irn); - - set_irn_n(ctx->spill, i, sub_res); + req = arch_get_irn_register_req_in(node, i); + if (req->cls != cls) + continue; + + if (! (req->type & arch_register_req_type_limited)) + continue; + + in = get_irn_n(node, i); + if (!arch_irn_consider_in_reg_alloc(cls, in)) + continue; + + for (i2 = i + 1; i2 < arity; ++i2) { + ir_node *in2; + const arch_register_req_t *req2; + + req2 = arch_get_irn_register_req_in(node, i2); + if (req2->cls != cls) + continue; + if (! (req2->type & arch_register_req_type_limited)) + continue; + + in2 = get_irn_n(node, i2); + if (in2 != in) + continue; + + /* if the constraint is the same, no copy is necessary + * TODO generalise unequal but overlapping constraints */ + if (rbitsets_equal(req->limited, req2->limited, cls->n_regs)) + continue; + + copy = be_new_Copy(block, in); + stat_ev_int("constr_copy", 1); + + sched_add_before(node, copy); + set_irn_n(node, i2, copy); + DBG((dbg, LEVEL_3, + "inserting multiple constr copy %+F for %+F pos %d\n", + copy, node, i2)); } } - return ctx->spill; -} -ir_node *be_spill_node(spill_env_t *senv, ir_node *to_spill) { - ir_node *res; - if (pset_find_ptr(senv->mem_phis, to_spill)) - res = be_spill_phi(senv, to_spill, to_spill); - else - res = be_spill_irn(senv, to_spill, to_spill); + /* collect all registers occurring in out constraints. */ + be_foreach_definition(node, cls, def, + if (! (req_->type & arch_register_req_type_limited)) + continue; + if (def_constr == NULL) { + rbitset_alloca(def_constr, cls->n_regs); + } + rbitset_or(def_constr, req_->limited, cls->n_regs); + ); + + /* no output constraints => we're good */ + if (def_constr == NULL) { + return; + } - return res; + /* + * insert copies for all constrained arguments living through the node + * and being constrained to a register which also occurs in out constraints. + */ + rbitset_alloca(tmp, cls->n_regs); + for (i = 0; i < arity; ++i) { + const arch_register_req_t *req; + ir_node *in; + ir_node *copy; + + /* + * Check, if + * 1) the operand is constrained. + * 2) lives through the node. + * 3) is constrained to a register occurring in out constraints. + */ + req = arch_get_irn_register_req_in(node, i); + if (req->cls != cls) + continue; + if (!(req->type & arch_register_req_type_limited)) + continue; + + in = get_irn_n(node, i); + if (!arch_irn_consider_in_reg_alloc(cls, in)) + continue; + if (!be_values_interfere(lv, node, in)) + continue; + + rbitset_copy(tmp, req->limited, cls->n_regs); + rbitset_and(tmp, def_constr, cls->n_regs); + + if (rbitset_is_empty(tmp, cls->n_regs)) + continue; + + /* + * only create the copy if the operand is no copy. + * this is necessary since the assure constraints phase inserts + * Copies and Keeps for operands which must be different from the + * results. Additional copies here would destroy this. + */ + if (be_is_Copy(in)) + continue; + + copy = be_new_Copy(block, in); + sched_add_before(node, copy); + set_irn_n(node, i, copy); + DBG((dbg, LEVEL_3, "inserting constr copy %+F for %+F pos %d\n", + copy, node, i)); + be_liveness_update(lv, in); + } } -void be_remove_spilled_phis(spill_env_t *senv) { - ir_node *irn; - /* remove all special phis form the irg and the schedule */ - for(irn = pset_first(senv->mem_phis); irn; irn = pset_next(senv->mem_phis)) { - int i, n; - for(i = 0, n = get_irn_arity(irn); i < n; ++i) - set_irn_n(irn, i, new_r_Bad(senv->session->irg)); - sched_remove(irn); +static void pre_spill_prepare_constr_walker(ir_node *block, void *data) +{ + be_pre_spill_env_t *env = (be_pre_spill_env_t*)data; + sched_foreach(block, node) { + prepare_constr_insn(env, node); } } + +void be_pre_spill_prepare_constr(ir_graph *irg, + const arch_register_class_t *cls) +{ + be_pre_spill_env_t env; + memset(&env, 0, sizeof(env)); + env.irg = irg; + env.cls = cls; + + be_assure_live_sets(irg); + + irg_block_walk_graph(irg, pre_spill_prepare_constr_walker, NULL, &env); +} + + + +int be_coalesce_spill_slots = 1; +int be_do_remats = 1; + +static const lc_opt_table_entry_t be_spill_options[] = { + LC_OPT_ENT_BOOL ("coalesce_slots", "coalesce the spill slots", &be_coalesce_spill_slots), + LC_OPT_ENT_BOOL ("remat", "try to rematerialize values instead of reloading", &be_do_remats), + LC_OPT_LAST +}; + +static be_module_list_entry_t *spillers = NULL; +static const be_spiller_t *selected_spiller = NULL; + +void be_register_spiller(const char *name, be_spiller_t *spiller) +{ + if (selected_spiller == NULL) + selected_spiller = spiller; + be_add_module_to_list(&spillers, name, spiller); +} + +void be_do_spill(ir_graph *irg, const arch_register_class_t *cls) +{ + assert(selected_spiller != NULL); + + selected_spiller->spill(irg, cls); +} + +BE_REGISTER_MODULE_CONSTRUCTOR(be_init_spilloptions) +void be_init_spilloptions(void) +{ + lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be"); + lc_opt_entry_t *spill_grp = lc_opt_get_grp(be_grp, "spill"); + + lc_opt_add_table(spill_grp, be_spill_options); + be_add_module_list_opt(be_grp, "spiller", "spill algorithm", + &spillers, (void**) &selected_spiller); + + FIRM_DBG_REGISTER(dbg, "firm.be.spillprepare"); +}