X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fberaextern.c;h=74a2b54a8e3101310760642456b8defe269eae10;hb=89dc24503c04139bb05504059b291d6d89f99661;hp=873350e36b04edb142179ff30847bd886e4b88b3;hpb=bf4a6b5554030d8c898440235ec716c0a340b5eb;p=libfirm diff --git a/ir/be/beraextern.c b/ir/be/beraextern.c index 873350e36..74a2b54a8 100644 --- a/ir/be/beraextern.c +++ b/ir/be/beraextern.c @@ -1,14 +1,34 @@ +/* + * 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: 17.01.2006 - * Copyright: (c) Universitaet Karlsruhe - * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + * @file + * @brief Implementation of the RA-Interface for an external, (non-SSA) register allocator. + * @author Daniel Grund + * @date 17.01.2006 + * @version $Id$ * - * Implementation of the RA-Interface for an external, (non-SSA) register allocator. + * The external register allocator is a program: + * PROG -i INPUTFILE -o OUTPUTFILE * - * The external register allocator is a program taking 2 arguments: - * 1) An input file in which the cfg is defined - * 2) An output file containing the essential actions performed during allocation + * 1) Input file defines the interference graph + * 2) Output file contains the instructions to perform * @@ -21,81 +41,74 @@ regs ::= 'regs' regcount . // Anzahl der register (0..regcount-1), die zur nodes ::= 'nodes' '{' node* '}' . // All nodes in the graph -interf ::= 'interferences' '{' edge* '}' . // Interference edges of the graph +node ::= node-info + | node-info '<' reg-nr '>' . // Reg-nr is present in case of constraints -affinities ::= 'affinities' '{' edge* '}' . // Affinity edges of the graph +node-info ::= node-nr spill-costs . -node ::= node-nr - | node-nr '<' reg-nr '>' . // Reg-nr is present in case of constraints +interf ::= 'interferences' '{' i-edge* '}' . // Interference edges of the graph -edge ::= '(' node-nr node-nr ')' . +i-edge ::= '(' node-nr ',' node-nr ')' . +affinities ::= 'affinities' '{' a-edge* '}' . // Affinity edges of the graph -regcount, node-nr ::= integer . +a-edge ::= '(' node-nr ',' node-nr ',' weight ')' . +weight, regcount, node-nr ::= int32 . +spill-costs ::= int32 . // negative spill costs indicate unspillable + The output file format ----------------------- outputfile ::= spills | allocs . -spills ::= 'spills' '{' node-nr+ '}' . +spills ::= 'spills' node-nr+ . -allocs ::= 'allocs' '{' alloc* '}' . +allocs ::= 'allocs' alloc* . alloc ::= node-nr reg-nr . - -Constraints for output file ---------------------------- -1) The returned actions must result in a non-ssa-program - equivalent to the former input. -2) All names (numbers) must be defined before their first use. - Numbers already occuring in the input file are implicitly defined in the output file. -3) All spills of a variable must precede the first reload of this variable -4) Each reload must define a new variable name - - - -******** End of file format docu ********/ - +*/ +#ifdef NOT_PORTED #ifdef HAVE_CONFIG_H #include "config.h" #endif -#ifdef WIN32 -#include -#else -#include -#endif - #include #include -#ifdef WITH_LIBCORE -#include -#include -#endif +#include +#include "lc_opts.h" +#include "lc_opts_enum.h" #include "set.h" #include "pset.h" #include "pmap.h" #include "bitset.h" +#include "raw_bitset.h" +#include "xmalloc.h" #include "irprintf_t.h" #include "irnode_t.h" #include "irgraph_t.h" #include "irgwalk.h" +#include "iredges_t.h" #include "irdom_t.h" #include "phiclass.h" -#include "beraextern.h" -#include "bearch.h" +#include "bemodule.h" +#include "beabi.h" +#include "bearch_t.h" #include "benode_t.h" #include "beirgmod.h" -#include "besched.h" +#include "besched_t.h" #include "beutil.h" +#include "belive_t.h" +#include "beinsn_t.h" -typedef struct _var_info_t var_info_t; +#include "bessadestrsimple.h" + +#define DBG_LEVEL 2 /** * Environment with all the needed stuff @@ -103,15 +116,14 @@ typedef struct _var_info_t var_info_t; typedef struct _be_raext_env_t { arch_env_t *aenv; const arch_register_class_t *cls; + be_irg_t *birg; ir_graph *irg; - dom_front_info_t *dom_info; FILE *f; /**< file handle used for out- and input file */ - set *vars; /**< contains all var_info_t */ - int n_cls_vars; - var_info_t **cls_vars; /**< only the var_infos for current cls. needed for double iterating */ - set *edges; /**< interference and affinity edges */ - pmap *nodes; /**< maps nodes numbers (int) to the node (ir_node*) having that node_nr */ + set *vars; /**< contains all be_var_info_t */ + int n_cls_vars; /**< length of the array cls_vars */ + be_var_info_t **cls_vars; /**< only the var_infos for current cls. needed for double iterating */ + DEBUG_ONLY(firm_dbg_module_t *dbg;) } be_raext_env_t; @@ -131,7 +143,6 @@ typedef struct _be_raext_env_t { #define pset_foreach(pset, irn) for(irn=pset_first(pset); irn; irn=pset_next(pset)) #define set_foreach(set, e) for(e=set_first(set); e; e=set_next(set)) - /** * Checks if _the_ result of the irn belongs to the * current register class (raenv->cls) @@ -139,344 +150,122 @@ typedef struct _be_raext_env_t { */ #define is_res_in_reg_class(irn) arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls) +static INLINE ir_node *get_first_non_phi(pset *s) { + ir_node *irn; -/** - * Checks if the irn uses or defines values of the - * current register class (raenv->cls) - */ -static INLINE int is_sth_in_reg_class(be_raext_env_t *raenv, const ir_node *irn) { - int max, i; - - /* check arguments */ - for (i=0, max=get_irn_arity(irn); iaenv, get_irn_n(irn, i), -1, raenv->cls)) - return 1; - - /* check result(s) */ - if (get_irn_mode(irn) == mode_T) { - ir_node *proj; - for (proj = sched_next(irn); is_Proj(proj); proj = sched_next(proj)) - if (arch_irn_has_reg_class(raenv->aenv, proj, -1, raenv->cls)) - return 1; - return 0; - } else { - return arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls); - } + pset_foreach(s, irn) + if (!is_Phi(irn)) { + pset_break(s); + return irn; + } - assert(0 && "Where did you come from???"); + assert(0 && "There must be a non-phi-irn in this"); + return NULL; } -/****************************************************************************** - _____ _____ _____ _ - / ____/ ____| /\ | __ \ | | - | (___| (___ / \ ______| | | | ___ ___| |_ _ __ - \___ \\___ \ / /\ \______| | | |/ _ \/ __| __| '__| - ____) |___) / ____ \ | |__| | __/\__ \ |_| | - |_____/_____/_/ \_\ |_____/ \___||___/\__|_| - - *****************************************************************************/ - -#define mark_as_done(irn, pos) set_irn_link(irn, INT_TO_PTR(pos+1)) -#define has_been_done(irn, pos) (PTR_TO_INT(get_irn_link(irn)) > pos) +static INLINE ir_node *get_first_phi(pset *s) { + ir_node *irn; -/** - * Insert a copy for the argument of @p start_phi found at position @p pos. - * Also searches a phi-loop of arbitrary length to detect and resolve - * the class of phi-swap-problems. To search for a loop recursion is used. - * - * 1) Simplest case (phi with a non-phi arg): - * A single copy is inserted. - * - * 2) Phi chain (phi (with phi-arg)* with non=phi arg): - * Several copies are placed, each after returning from recursion. - * - * 3) Phi-loop: - * On detection a loop breaker is inserted, which is a copy of the start_phi. - * This copy then pretends beeing the argumnent of the last phi. - * Now case 2) can be used. - * - * The values of @p start_phi and @p pos never change during recursion. - * - * @p raenv Environment with all the stuff needed - * @p start_phi Phi node to process - * @p pos Argument position to insert copy/copies for - * @p curr_phi Phi node currently processed during recursion. Equals start_phi on initial call - * - * @return NULL If no copy is necessary - * NULL If the phi has already been processed at this pos - * Link field is used to keep track of processed positions - * In all other cases the ir_node *copy which was placed is returned. - */ -static ir_node *insert_copies(be_raext_env_t *raenv, ir_node *start_phi, int pos, ir_node *curr_phi) { - ir_node *arg = get_irn_n(curr_phi, pos); - ir_node *arg_blk = get_nodes_block(arg); - ir_node *pred_blk = get_Block_cfgpred_block(get_nodes_block(curr_phi), pos); - ir_node *curr_cpy, *last_cpy; - - assert(is_Phi(start_phi) && is_Phi(curr_phi)); - - if (has_been_done(start_phi, pos)) - return NULL; - - /* In case this is a 'normal' phi we insert into - * the schedule before the pred_blk irn */ - last_cpy = pred_blk; - - /* If we detect a loop stop recursion. */ - if (arg == start_phi) { - ir_node *loop_breaker; - if (start_phi == curr_phi) { - /* Phi directly uses itself. No copy necessary */ - return NULL; + pset_foreach(s, irn) + if (is_Phi(irn)) { + pset_break(s); + return irn; } - /* At least 2 phis are involved */ - /* Insert a loop breaking copy (an additional variable T) */ - loop_breaker = be_new_Copy(raenv->cls, raenv->irg, pred_blk, start_phi); - sched_add_before(pred_blk, loop_breaker); - - arg = loop_breaker; - } - - /* If arg is a phi in the same block we have to continue search */ - if (is_Phi(arg) && arg_blk == get_nodes_block(start_phi)) - last_cpy = insert_copies(raenv, start_phi, pos, arg); - - /* Insert copy of argument (may be the loop-breaker) */ - curr_cpy = be_new_Copy(raenv->cls, raenv->irg, pred_blk, arg); - set_irn_n(curr_phi, pos, curr_cpy); - mark_as_done(curr_phi, pos); - sched_add_before(last_cpy, curr_cpy); - return curr_cpy; + assert(0 && "There must be a phi in this"); + return NULL; } +static int get_loop_weight(ir_node *irn) { + int cost = 0; + ir_loop *loop = get_irn_loop(get_nodes_block(irn)); -/** - * Perform simple SSA-destruction with copies. - * The order of processing _must_ be - * for all positions { - * for all phis { - * doit - * } - * } - * else the magic to keep track of processed phi-positions will fail in - * function 'insert_copies' - */ -static void ssa_destr_simple_walker(ir_node *blk, void *env) { - be_raext_env_t *raenv = env; - int pos, max; - ir_node *phi; - - /* for all argument positions of the phis */ - for (pos=0, max=get_irn_arity(blk); poscls = arch_get_irn_reg_class(raenv->aenv, phi, -1); - insert_copies(raenv, phi, pos, phi); - } + if (loop) { + int d = get_loop_depth(loop); + cost = d*d; } + return cost+1; } +#define get_const_weight(irn) (1) -static void ssa_destr_simple(be_raext_env_t *raenv) { - be_clear_links(raenv->irg); - irg_block_walk_graph(raenv->irg, ssa_destr_simple_walker, NULL, raenv); -} - - -static void ssa_destr_rastello(be_raext_env_t *raenv) { - assert(0 && "NYI"); - /* TODO - phi_class_compute(raenv->irg); - irg_block_walk_graph(irg, ssa_destr_rastello, NULL, &raenv); - */ -} +#define get_spill_weight(irn) get_loop_weight(irn) +#define get_reload_weight(irn) get_loop_weight(irn) +#define get_affinity_weight(irn) get_loop_weight(irn) /****************************************************************************** - __ __ _ ___ __ __ - \ \ / / | | |__ \ \ \ / / - \ \ / /_ _| |___ ) | \ \ / /_ _ _ __ ___ - \ \/ / _` | / __| / / \ \/ / _` | '__/ __| - \ / (_| | \__ \ / /_ \ / (_| | | \__ \ - \/ \__,_|_|___/ |____| \/ \__,_|_| |___/ + _____ _ _____ _ + / ____| | | / ____| (_) + | | ___ _ __ ___| |_ _ __ | | ___ _ __ _ ___ ___ + | | / _ \| '_ \/ __| __| '__| | | / _ \| '_ \| |/ _ \/ __| + | |___| (_) | | | \__ \ |_| | | |___| (_) | |_) | | __/\__ \ + \_____\___/|_| |_|___/\__|_| \_____\___/| .__/|_|\___||___/ + | | + |_| *****************************************************************************/ -/** - * This struct maps a variable (nr) to - * 1) the values belonging to this variable - * 2) the spills of this variable - */ -struct _var_info_t { - int var_nr; /* the key for comparesion */ - pset *values; /* the ssa-values belonging to this variable */ - pset *spills; /* the spills of this variable */ - pset *reloads; /* the relaods of this variable */ - unsigned reload_phase:1; /* 0 initially, 1 if a reload of this var has been inserted */ -}; - -/** - * The link field of an irn points to the var_info struct - * representing the corresponding variable. - */ -#define set_var_info(irn, vi) set_irn_link(irn, vi) -#define get_var_info(irn) ((var_info_t *)get_irn_link(irn)) - -/* TODO insn-nr handling if ext defines new ones */ -#define pmap_insert_sth(pmap, key, val) pmap_insert(pmap, (void *)key, (void *)val) -#define pmap_get_sth(pmap, key) pmap_get(pmap, (void *)key) - - -#define HASH_VAR_NR(var_nr) var_nr - - - -static int compare_var_infos(const void *e1, const void *e2, size_t size) { - const var_info_t *v1 = e1; - const var_info_t *v2 = e2; - - return v1->var_nr != v2->var_nr; -} - -static INLINE var_info_t *var_find(set *vars, int var_nr) { - var_info_t vi; - vi.var_nr = var_nr; - - return set_find(vars, &vi, sizeof(vi), HASH_VAR_NR(var_nr)); -} - -static INLINE var_info_t *var_find_or_insert(set *vars, int var_nr) { - var_info_t vi, *found; - memset(&vi, 0, sizeof(vi)); - vi.var_nr = var_nr; +static void handle_constraints_insn(be_raext_env_t *env, be_insn_t *insn) +{ + ir_node *bl = get_nodes_block(insn->irn); + int i; - found = set_insert(vars, &vi, sizeof(vi), HASH_VAR_NR(var_nr)); + for(i = 0; i < insn->use_start; ++i) { + be_operand_t *op = &insn->ops[i]; - if (!found->values) { - found->values = pset_new_ptr(1); - found->spills = pset_new_ptr(1); - found->reloads = pset_new_ptr(1); + if(op->has_constraints) { + ir_node *cpy = be_new_Copy(op->req->cls, env->irg, bl, op->carrier); + sched_add_before(insn->next_insn, cpy); + edges_reroute(op->carrier, cpy, env->irg); + } } - return found; -} - -/** - * Adds a value to a variable. Sets all pointers accordingly. - */ -static INLINE var_info_t *var_add_value(be_raext_env_t *raenv, int var_nr, ir_node *irn) { - var_info_t *vi = var_find_or_insert(raenv->vars, var_nr); - - /* var 2 value mapping */ - pset_insert_ptr(vi->values, irn); - - /* value 2 var mapping */ - set_var_info(irn, vi); - - return vi; -} - -/** - * Adds a spill to a variable. Sets all pointers accordingly. - */ -static INLINE var_info_t *var_add_spill(be_raext_env_t *raenv, int var_to_spill, ir_node *before) { - var_info_t *vi = var_find_or_insert(raenv->vars, var_to_spill); - ir_node *blk, *tospill, *spill; - - assert(pset_count(vi->values) && "There are no values associated to this variable"); - assert(!vi->reload_phase && "I have already seen a reload for this variable, so you cant spill anymore!"); - - /* add spill to graph and schedule */ - blk = get_nodes_block(before); - tospill = dom_up_search(vi->values, before); /* which value gets spilled */ - spill = be_new_Spill(raenv->cls, raenv->irg, blk, tospill, tospill); /* the corresponding spill node */ - - sched_add_before(before, spill); + for(i = insn->use_start; i < insn->n_ops; ++i) { + be_operand_t *op = &insn->ops[i]; - /* the spill also points to the var_info of the spilled node */ - set_var_info(spill, vi); - - /* remember the spill */ - pset_insert_ptr(vi->spills, spill); - - return vi; + if(op->has_constraints) { + ir_node *cpy = be_new_Copy(op->req->cls, env->irg, bl, op->carrier); + sched_add_before(insn->irn, cpy); + set_irn_n(insn->irn, op->pos, cpy); + be_set_constr_limited(cpy, BE_OUT_POS(0), op->req); + } + } } -/** - * Adds a reload to a variable. Sets all pointers accordingly. - */ -static INLINE var_info_t *var_add_reload(be_raext_env_t *raenv, int var_to_reload, int var_nr_for_reload, ir_node *before) { - var_info_t *vi = var_find_or_insert(raenv->vars, var_to_reload); - ir_node *blk, *spill, *reload; - - assert(pset_count(vi->spills) && "There are no spills associated to this variable"); - /* now we enter the reload phase, so no more spills are allowed */ - vi->reload_phase = 1; +static void handle_constraints_block(ir_node *bl, void *data) +{ + be_raext_env_t *raenv = data; + int active = bl != get_irg_start_block(raenv->irg); - /* add reload to graph and schedule */ - blk = get_nodes_block(before); - spill = pset_first(vi->spills); /* For now use an arbitrary spill node. This is corrected later in fix_reloads */ - pset_break(vi->spills); - reload = be_new_Reload(raenv->cls, raenv->irg, blk, get_irn_mode(get_irn_n(spill, 0)), spill); + ir_node *irn; + be_insn_env_t ie; + struct obstack obst; - sched_add_before(before, reload); + ie.cls = raenv->cls; + ie.aenv = raenv->aenv; + ie.obst = &obst; + ie.ignore_colors = NULL; + obstack_init(&obst); - /* create a new variable for the result of the reload */ - assert(!var_find(raenv->vars, var_nr_for_reload) && "Each reload must define a new variable"); - var_add_value(raenv, var_nr_for_reload, reload); + irn = sched_first(bl); + while(!sched_is_end(irn)) { + be_insn_t *insn = be_scan_insn(&ie, irn); - /* remember the reload */ - pset_insert_ptr(vi->reloads, reload); + if(insn->has_constraints) + handle_constraints_insn(raenv, insn); - return vi; -} + if(be_is_Barrier(irn)) + active = !active; -static INLINE pset *get_var_values(be_raext_env_t *raenv, int var_nr) { - var_info_t *vi = var_find(raenv->vars, var_nr); - assert(vi && "Variable does not (yet?) exist"); - return vi->values; + irn = insn->next_insn; + obstack_free(&obst, insn); + } } -static INLINE pset *get_var_spills(be_raext_env_t *raenv, int var_nr) { - var_info_t *vi = var_find(raenv->vars, var_nr); - assert(vi && "Variable does not (yet?) exist"); - return vi->spills; +static void handle_constraints(be_raext_env_t *raenv) { + irg_block_walk_graph(raenv->irg, NULL, handle_constraints_block, raenv); } -static INLINE pset *get_var_reloads(be_raext_env_t *raenv, int var_nr) { - var_info_t *vi = var_find(raenv->vars, var_nr); - assert(vi && "Variable does not (yet?) exist"); - return vi->reloads; -} -/** - * Define variables (numbers) for all SSA-values. - * All values in a phi class get assigned the same variable name. - * The link field maps values to the var-name - */ -static void values_to_vars(ir_node *irn, void *env) { - be_raext_env_t *raenv = env; - ir_node *n; - int nr; - pset *vals; - - vals = get_phi_class(irn); - - if (!vals) { - /* not a phi class member, value == var */ - vals = pset_new_ptr(1); - pset_insert_ptr(vals, irn); - } - - /* values <--> var mapping */ - n = pset_first(vals); - nr = get_irn_node_nr(n); - for (; n; n=pset_next(vals)) - var_add_value(raenv, nr, n); -} /****************************************************************************** @@ -491,32 +280,16 @@ static void values_to_vars(ir_node *irn, void *env) { *****************************************************************************/ -static INLINE ir_node *get_first_non_phi(pset *s) { - ir_node *irn; - - pset_foreach(s, irn) - if (!is_Phi(irn)) { - pset_break(s); - return irn; - } - - assert(0 && "There must be a non-phi-irn in this"); - return NULL; -} - static void extract_vars_of_cls(be_raext_env_t *raenv) { int count = 0; - set_entry *e; + be_var_info_t *vi; - raenv->cls_vars = malloc(set_count(raenv->vars) * sizeof(*raenv->cls_vars)); + raenv->cls_vars = xmalloc(set_count(raenv->vars) * sizeof(*raenv->cls_vars)); assert(raenv->cls_vars); - set_foreach(raenv->vars, e) { - var_info_t *vi = (var_info_t *)e->dptr; - + set_foreach(raenv->vars, vi) if (is_res_in_reg_class(get_first_non_phi(vi->values))) raenv->cls_vars[count++] = vi; - } raenv->cls_vars = realloc(raenv->cls_vars, count * sizeof(*raenv->cls_vars)); assert(raenv->cls_vars); @@ -530,19 +303,45 @@ static void extract_vars_of_cls(be_raext_env_t *raenv) { * If yes, dump it to FILE raenv->f */ static INLINE void dump_constraint(be_raext_env_t *raenv, ir_node *irn, int pos) { - bitset_t *bs = bitset_alloca(raenv->cls->n_regs); - arch_register_req_t req; - - arch_get_register_req(raenv->aenv, &req, irn, pos); - if (arch_register_req_is(&req, limited)) { - int reg_nr; - req.limited(req.limited_env, bs); - reg_nr = bitset_next_set(bs, 0); + const arch_register_req_t *req; + + req = arch_get_register_req(raenv->aenv, irn, pos); + if (arch_register_req_is(req, limited)) { + unsigned reg_nr; + + reg_nr = rbitset_next(req->limited, 0, 1); fprintf(raenv->f, "<%d>", reg_nr); - assert(-1 == bitset_next_set(bs, reg_nr+1) && "Constraints with more than 1 possible register are not supported"); + assert(rbitset_popcnt(req->limited, raenv->cls->n_regs) <= 1 + && "Constraints with more than 1 possible register are not supported"); } } +#define UNSPILLABLE -1 + +static INLINE int get_spill_costs(be_raext_env_t *raenv, be_var_info_t *vi) { + ir_node *irn; + int c_spills=0, c_reloads=0; + + pset_foreach(vi->values, irn) { + if (arch_irn_is(raenv->aenv, irn, ignore) || be_is_Reload(irn)) { + pset_break(vi->values); + return UNSPILLABLE; + } + + if (is_Phi(irn)) { + /* number of reloads is the number of non-phi uses of all values of this var */ + const ir_edge_t *edge; + foreach_out_edge(irn, edge) + if (!is_Phi(edge->src)) + c_reloads += get_reload_weight(edge->src); + } else { + /* number of spills is the number of non-phi values for this var */ + c_spills += get_spill_weight(irn); + } + } + + return c_spills + c_reloads; +} static void dump_nodes(be_raext_env_t *raenv) { FILE *f = raenv->f; @@ -551,57 +350,103 @@ static void dump_nodes(be_raext_env_t *raenv) { fprintf(f, "\nnodes {\n"); for (i=0; in_cls_vars; ++i) { - fprintf(f, "%d", raenv->cls_vars[i]->var_nr); - dump_constraint(raenv, get_first_non_phi(raenv->cls_vars[i]->values), -1); + be_var_info_t *vi = raenv->cls_vars[i]; + + if (vi->var_nr == SET_REMOVED) + continue; + + fprintf(f, "%d %d", vi->var_nr, get_spill_costs(raenv, vi)); + dump_constraint(raenv, get_first_non_phi(vi->values), -1); fprintf(f, "\n"); } fprintf(f, "}\n"); + fflush(f); } static void dump_interferences(be_raext_env_t *raenv) { int i,o; - var_info_t *vi1, *vi2; + be_var_info_t *vi1, *vi2; ir_node *irn1, *irn2; FILE *f = raenv->f; + be_lv_t *lv = raenv->birg->lv; fprintf(f, "\ninterferences {\n"); for (i=0; in_cls_vars; ++i) { vi1 = raenv->cls_vars[i]; + if (vi1->var_nr == SET_REMOVED) + continue; + for (o=i+1; on_cls_vars; ++o) { vi2 = raenv->cls_vars[o]; + if (vi2->var_nr == SET_REMOVED) + continue; + pset_foreach(vi1->values, irn1) pset_foreach(vi2->values, irn2) - if (values_interfere(irn1, irn2)) { + if (values_interfere(lv, irn1, irn2)) { pset_break(vi1->values); pset_break(vi2->values); - fprintf(f, "(%d %d)\n", vi1->var_nr, vi2->var_nr); + fprintf(f, "(%d, %d)\n", vi1->var_nr, vi2->var_nr); + goto NextVar; } + +NextVar: ; } } fprintf(f, "}\n"); } - static void dump_affinities_walker(ir_node *irn, void *env) { be_raext_env_t *raenv = env; + const arch_register_req_t *req; + int pos, max; + be_var_info_t *vi1, *vi2; + + if (arch_get_irn_reg_class(raenv->aenv, irn, -1) != raenv->cls || arch_irn_is(raenv->aenv, irn, ignore)) + return; + + vi1 = be_get_var_info(irn); + + /* copies have affinities */ + if (arch_irn_class_is(raenv->aenv, irn, copy)) { + ir_node *other = be_get_Copy_op(irn); - if (arch_irn_classify(raenv->aenv, irn) == arch_irn_class_copy) { - ir_node *src = get_irn_n(irn, 0); - var_info_t *vi1 = get_irn_link(irn); - var_info_t *vi2 = get_irn_link(src); + if (! arch_irn_is(raenv->aenv, other, ignore)) { + vi2 = be_get_var_info(other); - fprintf(raenv->f, "(%d %d)\n", vi1->var_nr, vi2->var_nr); + fprintf(raenv->f, "(%d, %d, %d)\n", vi1->var_nr, vi2->var_nr, get_affinity_weight(irn)); + } + } + + + /* should_be_equal constraints are affinites */ + for (pos = 0, max = get_irn_arity(irn); posaenv, irn, pos); + if (arch_register_req_is(req, should_be_same)) { + const int* i; + for (i = req->other_same; i != ENDOF(req->other_same); ++i) { + ir_node *other; + + if (*i == -1) break; + + other = get_irn_n(skip_Proj(irn), *i); + if(arch_irn_is(raenv->aenv, other, ignore)) { + vi2 = be_get_var_info(other); + fprintf(raenv->f, "(%d, %d, %d)\n", vi1->var_nr, vi2->var_nr, get_affinity_weight(irn)); + } + } + } } } static void dump_affinities(be_raext_env_t *raenv) { - fprintf(raenv->f, "\ninterferences {\n"); + fprintf(raenv->f, "\naffinities {\n"); irg_walk_graph(raenv->irg, NULL, dump_affinities_walker, raenv); fprintf(raenv->f, "}\n"); } @@ -615,6 +460,7 @@ static void dump_to_file(be_raext_env_t *raenv, char *filename) { if (!(f = fopen(filename, "wt"))) { fprintf(stderr, "Could not open file %s for writing\n", filename); + assert(0); exit(0xdeadbeef); } raenv->f = f; @@ -647,10 +493,12 @@ static void execute(char *prog_to_call, char *out_file, char *result_file) { char cmd_line[1024]; int ret_status; - snprintf(cmd_line, sizeof(cmd_line), "%s %s %s", prog_to_call, out_file, result_file); + snprintf(cmd_line, sizeof(cmd_line), "%s -i %s -o %s", prog_to_call, out_file, result_file); + cmd_line[sizeof(cmd_line) - 1] = '\0'; ret_status = system(cmd_line); assert(ret_status != -1 && "Invokation of external register allocator failed"); + assert(ret_status == 0 && "External register allocator is unhappy with sth."); } /****************************************************************************** @@ -664,23 +512,112 @@ static void execute(char *prog_to_call, char *out_file, char *result_file) { |_| |_| |___/ *****************************************************************************/ -#define INVALID_FILE_FORMAT assert(0 && "Invalid file format.") +/** + * Spill a variable and add reloads before all uses. + */ +static INLINE void var_add_spills_and_reloads(be_raext_env_t *raenv, int var_nr) { + be_var_info_t *vi = be_var_find(raenv->vars, var_nr); + ir_node *spill=NULL, *ctx, *irn; + ir_mode *mode; + const ir_edge_t *edge, *ne; + pset *spills = pset_new_ptr(4); /* the spills of this variable */ + pset *reloads = pset_new_ptr(4); /* the reloads of this variable */ + be_lv_t *lv = raenv->birg->lv; + be_dom_front_info_t *dom_front = raenv->birg->dom_front; + int new_size, n_spills, n_reloads; + + assert(vi && "Variable nr does not exist!"); + assert(pset_count(vi->values) && "There are no values associated to this variable"); -static INLINE int is_before(const char *s, size_t len) { - if (!strncmp(s, "before", len)) - return 1; - if (!strncmp(s, "after", len)) - return 0; - INVALID_FILE_FORMAT; - return -1; -} + /* the spill context is set to an arbitrary node of the phi-class, + * or the node itself if it is not member of a phi class + */ + if (pset_count(vi->values) == 1) + ctx = get_first_non_phi(vi->values); + else + ctx = get_first_phi(vi->values); + + DBG((raenv->dbg, LEVEL_2, "Spill context: %+F\n", ctx)); + + /* for each value of this variable insert the spills */ + pset_foreach(vi->values, irn) { + if (is_Phi(irn)) { + sched_remove(irn); + continue; + } -static void fix_reloads(be_raext_env_t *raenv) { - var_info_t *vi; - set_foreach(raenv->vars, vi) - be_introduce_copies_pset(raenv->dom_info, vi->spills); + /* all ordinary nodes must be spilled */ + DBG((raenv->dbg, LEVEL_2, " spilling %+F\n", irn)); + spill = be_spill(raenv->aenv, irn); + + /* remember the spill */ + pset_insert_ptr(spills, spill); + } + + assert(spill && "There must be at least one non-phi-node"); + + mode = get_irn_mode(get_irn_n(spill, be_pos_Spill_val)); + + /* insert reloads and wire them arbitrary*/ + pset_foreach(vi->values, irn) { + foreach_out_edge_safe(irn, edge, ne) { + ir_node *reload, *src = edge->src; + if (is_Phi(src) || be_is_Spill(src)) + continue; + + /* all real uses must be reloaded */ + DBG((raenv->dbg, LEVEL_2, " reloading before %+F\n", src)); + reload = be_reload(raenv->aenv, raenv->cls, edge->src, mode, spill); + set_irn_n(edge->src, edge->pos, reload); + + /* remember the reload */ + pset_insert_ptr(reloads, reload); + } + } + + /* correct the reload->spill pointers... */ + be_ssa_constr_set_ignore(dom_front, lv, spills, NULL); + + + /****** correct the variable <--> values mapping: ****** + * + * - if we had a phi class it gets split into several new variables + * - all reloads are new variables + */ + n_spills = pset_count(spills); + n_reloads = pset_count(reloads); + + /* first make room for new pointers in the cls_var array */ + new_size = raenv->n_cls_vars + n_reloads + ((n_spills>1) ? n_spills : 0); + raenv->cls_vars = realloc(raenv->cls_vars, (new_size) * sizeof(*raenv->cls_vars)); + assert(raenv->cls_vars && "Out of mem!?"); + + /* if we had a real phi-class, we must... */ + if (pset_count(spills) > 1) { + /* ...remove the old variable corresponding to the phi class */ + vi->var_nr = SET_REMOVED; + + /* ...add new vars for each non-phi-member */ + pset_foreach(spills, irn) { + ir_node *spilled = get_irn_n(irn, be_pos_Spill_val); + raenv->cls_vars[raenv->n_cls_vars++] = be_var_add_value(raenv->vars, get_irn_node_nr(spilled), spilled); + } + } + + /* add new variables for all reloads */ + pset_foreach(reloads, irn) { + assert(get_irn_node_nr(irn) != 1089); + raenv->cls_vars[raenv->n_cls_vars++] = be_var_add_value(raenv->vars, get_irn_node_nr(irn), irn); + } + + del_pset(spills); + del_pset(reloads); } +#define INVALID_FILE_FORMAT assert(0 && "Invalid file format.") +#define BUFLEN 32 +#define BUFCONV " %32s " + /** * Read in the actions performed by the external allocator. * Apply these transformations to the irg. @@ -688,97 +625,76 @@ static void fix_reloads(be_raext_env_t *raenv) { */ static int read_and_apply_results(be_raext_env_t *raenv, char *filename) { FILE *f; - var_info_t *vi; - int phase=0; + char buf[BUFLEN]; + int is_allocation = 0; if (!(f = fopen(filename, "rt"))) { fprintf(stderr, "Could not open file %s for reading\n", filename); + assert(0); exit(0xdeadbeef); } raenv->f = f; - /* parse the file */ - while (phase == 0) { - int loc, var_use_ident, var_def_ident, pos; - char where[16]; - - /* handle a spill */ - if (fscanf(f, " spill %6s %d %d ", &where, &loc, &var_use_ident) == 3) { - - /* determine the node to insert the spill before */ - ir_node *anchor = pmap_get_sth(raenv->nodes, loc); - assert(anchor && "insn-nr does not exist"); - if (!is_before(where, sizeof(where))) - anchor = sched_next(anchor); + /* read the action */ + if (fscanf(f, BUFCONV, buf) != 1) + INVALID_FILE_FORMAT; - var_add_spill(raenv, var_use_ident, anchor); - } + /* do we spill */ + if (!strcmp(buf, "spills")) { + int var_nr; + while (fscanf(f, " %d ", &var_nr) == 1) + var_add_spills_and_reloads(raenv, var_nr); + } else - /* handle a reload */ - else if (fscanf(f, " reload %s %d %d %d ", &where, &loc, &var_def_ident, &var_use_ident) == 4) { + /* or do we allocate */ + if (!strcmp(buf, "allocs")) { + int var_nr, reg_nr; - /* determine the node to insert the spill before */ - ir_node *anchor = pmap_get_sth(raenv->nodes, loc); - assert(anchor && "insn-nr does not exist"); - if (!is_before(where, sizeof(where))) - anchor = sched_next(anchor); + is_allocation = 1; + while (fscanf(f, " %d %d ", &var_nr, ®_nr) == 2) { + ir_node *irn; + pset *vals = be_get_var_values(raenv->vars, var_nr); - var_add_reload(raenv, var_use_ident, var_def_ident, anchor); + assert(vals && "Variable nr does not exist!"); + pset_foreach(vals, irn) + arch_set_irn_register(raenv->aenv, irn, arch_register_for_index(raenv->cls, reg_nr)); } + } else + INVALID_FILE_FORMAT; - /* handle a set_irn_n */ - else if (fscanf(f, " setarg %d %d %d ", &loc, &pos, &var_use_ident) == 3) { - ir_node *to_change, *new_arg; - var_info_t *vi = var_find(raenv->vars, var_use_ident); - assert(vi && vi->values && "New argument does not exist"); + if (!feof(f)) + INVALID_FILE_FORMAT; - to_change = pmap_get_sth(raenv->nodes, loc); - assert(to_change && "insn-nr does not exist"); + fclose(f); - new_arg = dom_up_search(vi->values, to_change); - set_irn_n(to_change, pos, new_arg); - } + return is_allocation; +} - /* handle a copy insertion */ - else if (fscanf(f, " copy %s %d %d %d ", &where, &loc, &var_def_ident, &var_use_ident) == 4) { - /* TODO - Ziel der Kopie ist Variable die bereits existiert - Ziel der Kopie ist eine neue Variable - */ - } +static void check_allocation(be_raext_env_t *raenv) { + int i, o; + be_lv_t *lv = raenv->birg->lv; - else - phase++; - } + for (i=0; in_cls_vars; ++i) { + be_var_info_t *vi1 = raenv->cls_vars[i]; - fix_reloads(raenv); + if (vi1->var_nr == SET_REMOVED) + continue; - while (phase == 1) { - int var_use_ident, reg_nr; + for (o=0; ocls_vars[o]; + ir_node *irn1, *irn2; - /* assign register */ - if (fscanf(f, " assign %d %d ", &var_use_ident, ®_nr) == 2) { - pset *vals = get_var_values(raenv, var_use_ident); - ir_node *irn; + if (vi2->var_nr == SET_REMOVED) + continue; - assert(vals && "Variable does not (yet?) exist!"); - pset_foreach(vals, irn) - arch_set_irn_register(raenv->aenv, irn, arch_register_for_index(raenv->cls, var_use_ident)); + pset_foreach(vi1->values, irn1) + pset_foreach(vi2->values, irn2) + if (values_interfere(lv, irn1, irn2) && arch_get_irn_register(raenv->aenv, irn1) == arch_get_irn_register(raenv->aenv, irn2)) { + dump_ir_block_graph_sched(raenv->irg, "ERROR"); + ir_fprintf(stdout, "SSA values %+F and %+F interfere. They belong to variable %d and %d respectively.\n", irn1, irn2, vi1->var_nr, vi2->var_nr); + assert(0 && "ERROR graph dumped"); + } } - else - phase++; - } - - if (!feof(f)) - INVALID_FILE_FORMAT; - - fclose(f); - - /* Free the psets held in the variable-infos */ - set_foreach(raenv->vars, vi) { - del_pset(vi->values); - del_pset(vi->spills); - del_pset(vi->reloads); } } @@ -794,8 +710,8 @@ static int read_and_apply_results(be_raext_env_t *raenv, char *filename) { /** * Default values for options */ -static void (*ssa_destr)(be_raext_env_t*) = ssa_destr_simple; -static char callee[128] = "echo"; +static char callee[128] = "\"E:/user/kimohoff/public/register allocator\""; +//static char callee[128] = "/ben/kimohoff/ipd-registerallocator/register_allocator"; /** @@ -807,57 +723,72 @@ static char callee[128] = "echo"; * Read in results and apply them * */ -static void be_ra_extern_main(const be_main_env_t *env, ir_graph *irg) { - be_raext_env_t raenv; +static void be_ra_extern_main(be_irg_t *birg) { + be_main_env_t *env = birg->main_env; + ir_graph *irg = birg->irg; + + be_raext_env_t raenv; int clsnr, clss; - compute_doms(irg); + be_assure_dom_front(birg); + be_assure_liveness(birg); + edges_assure(irg); raenv.irg = irg; + raenv.birg = birg; raenv.aenv = env->arch_env; - raenv.dom_info = be_compute_dominance_frontiers(irg); - raenv.vars = new_set(compare_var_infos, 64); - raenv.nodes = pmap_create(); + FIRM_DBG_REGISTER(raenv.dbg, "firm.be.raextern"); - /* Insert copies */ - - //TODO + /* Insert copies for constraints */ + for(clsnr = 0, clss = arch_isa_get_n_reg_class(raenv.aenv->isa); clsnr < clss; ++clsnr) { + raenv.cls = arch_isa_get_reg_class(raenv.aenv->isa, clsnr); + handle_constraints(&raenv); + } - /* SSA destruction */ - ssa_destr(&raenv); + be_dump(irg, "-extern-constr", dump_ir_block_graph_sched); - /* Mapping of SSA-Values <--> Variables */ - phi_class_compute(irg); - be_clear_links(irg); - irg_walk_graph(irg, values_to_vars, NULL, &raenv); + /* SSA destruction respectively transformation into "Conventional SSA" */ + raenv.vars = be_ssa_destr_simple(irg, env->arch_env); + be_dump(irg, "-extern-ssadestr", dump_ir_block_graph_sched); - dump_ir_block_graph_sched(irg, "-extern-ssadestr"); /* For all register classes */ for(clsnr = 0, clss = arch_isa_get_n_reg_class(raenv.aenv->isa); clsnr < clss; ++clsnr) { - int done = 0; + int done, round = 1; char out[256], in[256]; raenv.cls = arch_isa_get_reg_class(raenv.aenv->isa, clsnr); - ir_snprintf(out, sizeof(out), "%F-%s.ra", irg, raenv.cls->name); - ir_snprintf(in, sizeof(in), "%F-%s.ra.res", irg, raenv.cls->name); extract_vars_of_cls(&raenv); - while (!done) { + do { + ir_snprintf(out, sizeof(out), "%F-%s-%d.ra", irg, raenv.cls->name, round); + ir_snprintf(in, sizeof(in), "%F-%s-%d.ra.res", irg, raenv.cls->name, round); + + be_liveness(irg); + dump_to_file(&raenv, out); execute(callee, out, in); done = read_and_apply_results(&raenv, in); - } + be_abi_fix_stack_nodes(birg->abi); + + ir_snprintf(in, sizeof(in), "-extern-%s-round-%d", raenv.cls->name, round); + be_dump(irg, in, dump_ir_block_graph_sched); + + round++; + } while (!done); + + check_allocation(&raenv); free(raenv.cls_vars); } + be_dump(irg, "-extern-alloc", dump_ir_block_graph_sched); + /* Clean up */ - pmap_destroy(raenv.nodes); - del_set(raenv.vars); - be_free_dominance_frontiers(raenv.dom_info); + free_ssa_destr_simple(raenv.vars); + be_liveness_invalidate(be_get_birg_liveness(birg)); } /****************************************************************************** @@ -871,16 +802,15 @@ static void be_ra_extern_main(const be_main_env_t *env, ir_graph *irg) { |_| *****************************************************************************/ -#ifdef WITH_LIBCORE - -static const lc_opt_enum_const_ptr_items_t ssa_destr_items[] = { - { "simple", ssa_destr_simple }, - { "rastello", ssa_destr_rastello }, +static const lc_opt_enum_func_ptr_items_t ssa_destr_items[] = { + { "simple", (int (*)(void)) be_ssa_destr_simple }, /* TODO make (void*) casts nicer */ { NULL, NULL } }; -static lc_opt_enum_const_ptr_var_t ssa_destr_var = { - (const void **) &ssa_destr, ssa_destr_items +static set* (*ssa_destr)(ir_graph*,const arch_env_t*) = be_ssa_destr_simple; + +static lc_opt_enum_func_ptr_var_t ssa_destr_var = { + (int (**)(void)) &ssa_destr, ssa_destr_items }; static const lc_opt_table_entry_t be_ra_extern_options[] = { @@ -889,17 +819,19 @@ static const lc_opt_table_entry_t be_ra_extern_options[] = { { NULL } }; -static void be_ra_extern_register_options(lc_opt_entry_t *root) { - lc_opt_entry_t *grp = lc_opt_get_grp(root, "ext"); +static be_ra_t be_ra_external_allocator = { + be_ra_extern_main +}; + +void be_init_raextern(void) { + lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be"); + lc_opt_entry_t *blocksched_grp = lc_opt_get_grp(be_grp, "ra"); + lc_opt_entry_t *ext_grp = lc_opt_get_grp(blocksched_grp, "ext"); - lc_opt_add_table(grp, be_ra_extern_options); -} + lc_opt_add_table(ext_grp, be_ra_extern_options); -#endif /* WITH_LIBCORE */ + be_register_allocator("ext", &be_ra_external_allocator); +} +BE_REGISTER_MODULE_CONSTRUCTOR(be_init_raextern); -const be_ra_t be_ra_external_allocator = { -#ifdef WITH_LIBCORE - be_ra_extern_register_options, -#endif - be_ra_extern_main -}; +#endif /* NOT_PORTED */