X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fberaextern.c;h=be4323977e6da262ede19332659ebde6e7d58d92;hb=23b71abac8014aa6bfee3b47648fdb8fe8687b8f;hp=debef727ff47f10ac1b6b3bc24d0610c4596ab9a;hpb=7522048d810ba9515423b9f5bd94274296aa01ae;p=libfirm diff --git a/ir/be/beraextern.c b/ir/be/beraextern.c index debef727f..be4323977 100644 --- a/ir/be/beraextern.c +++ b/ir/be/beraextern.c @@ -6,61 +6,53 @@ * * Implementation of the RA-Interface for an external, (non-SSA) register allocator. * - * 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 + * The external register allocator is a program: + * PROG -i INPUTFILE -o OUTPUTFILE + * + * 1) Input file defines the interference graph + * 2) Output file contains the instructions to perform * The input file format ---------------------- -inputfile ::= regs cfg . +inputfile ::= regs nodes interf affinities . regs ::= 'regs' regcount . // Anzahl der register (0..regcount-1), die zur Verfuegung stehen -cfg ::= 'cfg' ident '{' block* edge* '}' . // Steuerflussgraph der Prozedur - -block ::= 'block' block-nr '{' insn* '}' . // Grundblock im cfg versehen mit einer nummer - -edge ::= 'cf-edge' block-nr block-nr . // Steuerflusskante src-->tgt +nodes ::= 'nodes' '{' node* '}' . // All nodes in the graph -insn ::= gen-insn // Befehl in einem block - | copy-insn . +node ::= node-info + | node-info '<' reg-nr '>' . // Reg-nr is present in case of constraints -gen-insn ::= 'insn' insn-nr '{' uses defs '}' . -copy-insn ::= 'copy' insn-nr '{' uses defs '}' . +node-info ::= node-nr spill-costs . -defs ::= 'def' var-list . // Liste der definierten/verwendeten Variablen -uses ::= 'use' var-list . +interf ::= 'interferences' '{' i-edge* '}' . // Interference edges of the graph -var-list ::= var-ref - | var-ref var-list . +i-edge ::= '(' node-nr ',' node-nr ')' . -var-ref ::= var-nr - | var-nr '<' reg-nr '>' . // reg-nr gibt register constraint an. +affinities ::= 'affinities' '{' a-edge* '}' . // Affinity edges of the graph +a-edge ::= '(' node-nr ',' node-nr ',' weight ')' . -ident ::= non-whitespace-char* . -regcount, block-nr, insn-nr, reg-nr, var-nr ::= integer . +weight, regcount, node-nr ::= int32 . +spill-costs ::= int32 . // negative spill costs indicate unspillable The output file format ----------------------- -outputfile ::= action* . +outputfile ::= spills | allocs . -action ::= 'spill' loc var-nr // insert a spill spill(var-nr); - | 'reload' loc var-nr var-nr // insert a reload var-nr[1] := reload(var-nr[2]); - | 'copy' loc var-nr var-nr // insert a copy var-nr[1] := var-nr[2]; - | 'assign' var-nr reg-nr . // assign var-nr the register reg-nr +spills ::= 'spills' node-nr+ . -loc ::= 'before' insn-nr - | 'after' insn-nr . +allocs ::= 'allocs' alloc* . + +alloc ::= node-nr reg-nr . -TODO - * - * End of file format docu */ + +******** End of file format docu ********/ #ifdef HAVE_CONFIG_H #include "config.h" @@ -74,91 +66,54 @@ TODO #include #include +#include #ifdef WITH_LIBCORE #include #include #endif -#include "pmap.h" +#include "set.h" #include "pset.h" +#include "pmap.h" #include "bitset.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 "benode_t.h" +#include "beirgmod.h" #include "besched.h" #include "beutil.h" +#include "belive_t.h" + +#define DBG_LEVEL 2 + +typedef struct _var_info_t var_info_t; /** * Environment with all the needed stuff */ typedef struct _be_raext_env_t { + firm_dbg_module_t *dbg; arch_env_t *aenv; const arch_register_class_t *cls; ir_graph *irg; + dom_front_info_t *dom_info; - FILE *f; /**< file handle used for out- and input file */ - pmap *vars; /**< maps variable numbers (int) to the corresponding SSA-values (pset of irns) */ - pmap *blocks; /**< maps block numbers (int) to the block (ir_node*) having that node_nr */ + FILE *f; /**< file handle used for out- and input file */ + set *vars; /**< contains all var_info_t */ + int n_cls_vars; /**< length of the array cls_vars */ + var_info_t **cls_vars; /**< only the var_infos for current cls. needed for double iterating */ } be_raext_env_t; -/****************************************************************************** - ____ _ _ - / __ \ | | (_) - | | | |_ __ | |_ _ ___ _ __ ___ - | | | | '_ \| __| |/ _ \| '_ \/ __| - | |__| | |_) | |_| | (_) | | | \__ \ - \____/| .__/ \__|_|\___/|_| |_|___/ - | | - |_| - *****************************************************************************/ - - -static void ssa_destr_simple(be_raext_env_t *); -static void ssa_destr_rastello(be_raext_env_t *); -static void be_ra_extern_main(const be_main_env_t *env, ir_graph *irg); - -static void (*ssa_destr)(be_raext_env_t*) = ssa_destr_simple; -static char callee[128] = "echo"; - -#ifdef WITH_LIBCORE - -static const lc_opt_enum_const_ptr_items_t ssa_destr_items[] = { - { "simple", ssa_destr_simple }, - { "rastello", ssa_destr_rastello }, - { NULL, NULL } -}; -static lc_opt_enum_const_ptr_var_t ssa_destr_var = { - (const void **) &ssa_destr, ssa_destr_items -}; - -static const lc_opt_table_entry_t be_ra_extern_options[] = { - LC_OPT_ENT_ENUM_FUNC_PTR("ssa_destr", "SSA destruction flavor", &ssa_destr_var), - LC_OPT_ENT_STR("callee", "The external program to call", callee, sizeof(callee)), - { NULL } -}; - -static void be_ra_extern_register_options(lc_opt_entry_t *root) { - lc_opt_entry_t *grp = lc_opt_get_grp(root, "ext"); - - lc_opt_add_table(grp, be_ra_extern_options); -} - -#endif /* WITH_LIBCORE */ - -const be_ra_t be_ra_external_allocator = { -#ifdef WITH_LIBCORE - be_ra_extern_register_options, -#endif - be_ra_extern_main -}; /****************************************************************************** _ _ _ @@ -171,14 +126,9 @@ const be_ra_t be_ra_external_allocator = { |_| *****************************************************************************/ -#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) - -#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 set_var_nr(irn, nr) set_irn_link(irn, INT_TO_PTR(nr)) -#define get_var_nr(irn) PTR_TO_INT(get_irn_link(irn)) +#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 @@ -187,33 +137,105 @@ const be_ra_t be_ra_external_allocator = { */ #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 && "There must be a non-phi-irn in this"); + return NULL; +} + +static INLINE ir_node *get_first_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 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)); + + if (loop) { + int d = get_loop_depth(loop); + cost = d*d; + } + return cost+1; +} + +#define get_const_weight(irn) (1) + +#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) + +/****************************************************************************** + _____ _ _____ _ + / ____| | | / ____| (_) + | | ___ _ __ ___| |_ _ __ | | ___ _ __ _ ___ ___ + | | / _ \| '_ \/ __| __| '__| | | / _ \| '_ \| |/ _ \/ __| + | |___| (_) | | | \__ \ |_| | | |___| (_) | |_) | | __/\__ \ + \_____\___/|_| |_|___/\__|_| \_____\___/| .__/|_|\___||___/ + | | + |_| + *****************************************************************************/ + +static void handle_constraints_walker(ir_node *irn, void *env) { + be_raext_env_t *raenv = env; + arch_register_req_t req; + int pos, max; + + /* handle output constraints + * user -> irn becomes user -> cpy -> irn + */ + arch_get_register_req(raenv->aenv, &req, irn, -1); + if (arch_register_req_is(&req, limited)) { + ir_node *cpy = be_new_Copy(req.cls, raenv->irg, get_nodes_block(irn), irn); + const ir_edge_t *edge; + + /* all users of the irn use the copy instead */ + sched_add_after(irn, cpy); + foreach_out_edge(irn, edge) + set_irn_n(edge->src, edge->pos, cpy); + } + + + /* handle input constraints by converting them into output constraints + * of copies of the former argument + * irn -> arg becomes irn -> copy -> arg + */ + for (pos = 0, max = get_irn_arity(irn); posaenv, &req, irn, pos); + if (arch_register_req_is(&req, limited)) { + ir_node *arg = get_irn_n(irn, pos); + ir_node *cpy = be_new_Copy(req.cls, raenv->irg, get_nodes_block(irn), arg); + + /* use the copy instead */ + sched_add_before(irn, cpy); + set_irn_n(irn, pos, cpy); + + /* set an out constraint for the copy */ + be_set_constr_limited(cpy, -1, &req); + } } +} - assert(0 && "Where did you come from???"); +static void handle_constraints(be_raext_env_t *raenv) { + irg_block_walk_graph(raenv->irg, NULL, handle_constraints_walker, raenv); } + /****************************************************************************** _____ _____ _____ _ / ____/ ____| /\ | __ \ | | @@ -224,6 +246,8 @@ static INLINE int is_sth_in_reg_class(be_raext_env_t *raenv, const ir_node *irn) *****************************************************************************/ +#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) /** * Insert a copy for the argument of @p start_phi found at position @p pos. @@ -335,10 +359,92 @@ static void ssa_destr_simple(be_raext_env_t *raenv) { static void ssa_destr_rastello(be_raext_env_t *raenv) { + assert(0 && "NYI"); + exit(0xDeadBeef); + /* phi_class_compute(raenv->irg); - //TODO irg_block_walk_graph(irg, ssa_destr_rastello, NULL, &raenv); + irg_block_walk_graph(irg, ssa_destr_rastello, NULL, &raenv); + */ } +/****************************************************************************** + __ __ _ ___ __ __ + \ \ / / | | |__ \ \ \ / / + \ \ / /_ _| |___ ) | \ \ / /_ _ _ __ ___ + \ \/ / _` | / __| / / \ \/ / _` | '__/ __| + \ / (_| | \__ \ / /_ \ / (_| | | \__ \ + \/ \__,_|_|___/ |____| \/ \__,_|_| |___/ + *****************************************************************************/ + +/** + * This struct maps a variable (nr) to the values belonging to this variable + */ +struct _var_info_t { + int var_nr; /* the key */ + pset *values; /* the ssa-values belonging to this variable */ +}; + +#define SET_REMOVED -1 + +/** + * 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)) + +#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; + + if (v1->var_nr == SET_REMOVED || v2->var_nr == SET_REMOVED) + return 1; + + 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; + + found = set_insert(vars, &vi, sizeof(vi), HASH_VAR_NR(var_nr)); + + if (!found->values) + found->values = pset_new_ptr(1); + + 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; +} + +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 exist"); + return vi->values; +} /** * Define variables (numbers) for all SSA-values. @@ -347,28 +453,29 @@ static void ssa_destr_rastello(be_raext_env_t *raenv) { */ static void values_to_vars(ir_node *irn, void *env) { be_raext_env_t *raenv = env; - ir_node *n; int nr; pset *vals; + if(arch_get_irn_reg_class(raenv->aenv, irn, -1) == NULL) + return; + vals = get_phi_class(irn); - if (!vals) { + if (vals) { + nr = get_irn_node_nr(get_first_phi(vals)); + } else { /* not a phi class member, value == var */ + nr = get_irn_node_nr(irn); vals = pset_new_ptr(1); pset_insert_ptr(vals, irn); } - /* value to var mapping */ - n = pset_first(vals); - nr = get_irn_node_nr(n); - for (; n; n=pset_next(vals)) - set_var_nr(irn, nr); - - /* var to values mapping */ - pmap_insert_sth(raenv->vars, nr, vals); + /* values <--> var mapping */ + pset_foreach(vals, irn) + var_add_value(raenv, nr, irn); } + /****************************************************************************** _____ | __ \ @@ -380,6 +487,25 @@ static void values_to_vars(ir_node *irn, void *env) { |_| *****************************************************************************/ + +static void extract_vars_of_cls(be_raext_env_t *raenv) { + int count = 0; + var_info_t *vi; + + raenv->cls_vars = malloc(set_count(raenv->vars) * sizeof(*raenv->cls_vars)); + assert(raenv->cls_vars); + + 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); + + raenv->n_cls_vars = count; +} + + /** * Check if node irn has a limited-constraint at position pos. * If yes, dump it to FILE raenv->f @@ -391,96 +517,133 @@ static INLINE void dump_constraint(be_raext_env_t *raenv, ir_node *irn, int pos) arch_get_register_req(raenv->aenv, &req, irn, pos); if (arch_register_req_is(&req, limited)) { int reg_nr; - req.limited(irn, pos, bs); + req.limited(req.limited_env, bs); reg_nr = bitset_next_set(bs, 0); - fprintf(raenv->f, " <%d>", reg_nr); + 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"); } } - -/** - * Dump all blocks and instructions in that block - */ -static void dump_blocks(ir_node *blk, void *env) { - be_raext_env_t *raenv = env; +static INLINE unsigned int get_spill_costs(be_raext_env_t *raenv, var_info_t *vi) { ir_node *irn; + int c_spills=0, c_reloads=0; + + pset_foreach(vi->values, irn) { + if (arch_irn_is_ignore(raenv->aenv, irn)) { + pset_break(vi->values); + return -1; + } + + 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; - int nr = get_irn_node_nr(blk); + int i; - pmap_insert_sth(raenv->blocks, nr, blk); + fprintf(f, "\nnodes {\n"); - /* begin block scope */ - fprintf(f, "\n"); - fprintf(f, " block %d {\n", nr); + for (i=0; in_cls_vars; ++i) { + var_info_t *vi = raenv->cls_vars[i]; - /* for each instruction */ - for(irn=sched_first(blk); !sched_is_end(irn); irn=sched_next(irn)) { - int max, i; - if (is_Phi(irn) || !is_sth_in_reg_class(raenv, irn)) + if (vi->var_nr == SET_REMOVED) continue; - fprintf(f, " insn %ld {\n", get_irn_node_nr(irn)); - - /* - * print all uses - */ - fprintf(f, " use"); - for (i=0, max=get_irn_arity(irn); iaenv, arg, -1, raenv->cls)) { - fprintf(f, " %d", get_var_nr(arg)); - dump_constraint(raenv, irn, i); - } - } - fprintf(f,"\n"); - - /* - * print all defs - */ - fprintf(f, " def"); - /* special handling of projs */ - if (get_irn_mode(irn) == mode_T) { - for (irn = sched_next(irn); is_Proj(irn); irn = sched_next(irn)) - if (arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls)) { - fprintf(f, " %d", get_var_nr(irn)); - dump_constraint(raenv, irn, -1); - } - irn = sched_prev(irn); /* for outer loop */ - } else { - if (arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls)) { - fprintf(f, " %d", get_var_nr(irn)); - dump_constraint(raenv, irn, -1); - } - } - fprintf(f,"\n"); - - fprintf(f, " }\n"); + fprintf(f, "%d %u", vi->var_nr, get_spill_costs(raenv, vi)); + dump_constraint(raenv, get_first_non_phi(vi->values), -1); + fprintf(f, "\n"); } - /* end the block scope */ - fprintf(f, " }\n"); + fprintf(f, "}\n"); } -/** - * Dump all control flow edges of this irg - */ -static void dump_edges(ir_node *blk, void *env) { +static void dump_interferences(be_raext_env_t *raenv) { + int i,o; + var_info_t *vi1, *vi2; + ir_node *irn1, *irn2; + FILE *f = raenv->f; + + 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)) { + pset_break(vi1->values); + pset_break(vi2->values); + fprintf(f, "(%d, %d)\n", vi1->var_nr, vi2->var_nr); + } + } + } + fprintf(f, "}\n"); +} + +static void dump_affinities_walker(ir_node *irn, void *env) { be_raext_env_t *raenv = env; - int i, max; + arch_register_req_t req; + int pos, max; + var_info_t *vi1, *vi2; - if (get_irg_start_block(get_irn_irg(blk)) == blk) + if (arch_get_irn_reg_class(raenv->aenv, irn, -1) == NULL || arch_irn_is_ignore(raenv->aenv, irn)) return; - /* dump cf edges in the flow-order "pred succ" */ - for (i=0, max=get_irn_arity(blk); if, " cf_edge %ld %ld\n", get_irn_node_nr(pred), get_irn_node_nr(blk)); + vi1 = get_var_info(irn); + + /* copies have affinities */ + if (arch_irn_classify(raenv->aenv, irn) == arch_irn_class_copy) { + ir_node *other = get_irn_n(irn, 0); + + if (! arch_irn_is_ignore(raenv->aenv, other)) { + vi2 = get_var_info(other); + + 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, &req, irn, pos); + + if (arch_register_req_is(&req, should_be_same) && arch_irn_is_ignore(raenv->aenv, req.other_same)) { + vi2 = get_var_info(req.other_same); + + 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, "\naffinities {\n"); + irg_walk_graph(raenv->irg, NULL, dump_affinities_walker, raenv); + fprintf(raenv->f, "}\n"); +} + /** * Dump all information needed by the external * register allocator to a single file. @@ -490,22 +653,22 @@ 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; + /* dump register info */ fprintf(f, "regs %d\n", arch_register_class_n_regs(raenv->cls)); - fprintf(f, "cfg %s {\n", filename); - irg_block_walk_graph(raenv->irg, NULL, dump_blocks, raenv); - irg_block_walk_graph(raenv->irg, NULL, dump_edges, raenv); - - fprintf(f, "}\n"); + /* dump the interference graph */ + dump_nodes(raenv); + dump_interferences(raenv); + dump_affinities(raenv); fclose(f); } - /****************************************************************************** ______ _ | ____| | | @@ -519,11 +682,11 @@ static void dump_to_file(be_raext_env_t *raenv, char *filename) { * Execute the external register allocator specified in the * firm-option firm.be.ra.ext.callee */ -static void execute(char *out_file, char *result_file) { +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", callee, out_file, result_file); + snprintf(cmd_line, sizeof(cmd_line), "%s -i %s -o %s", prog_to_call, out_file, result_file); ret_status = system(cmd_line); assert(ret_status != -1 && "Invokation of external register allocator failed"); @@ -540,22 +703,184 @@ static void execute(char *out_file, char *result_file) { |_| |_| |___/ *****************************************************************************/ +/** + * 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) { + var_info_t *vi = 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 */ + 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"); + + /* 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; + } + + /* all ordinary nodes must be spilled */ + DBG((raenv->dbg, LEVEL_2, " spilling %+F\n", irn)); + spill = be_spill(raenv->aenv, irn, ctx); + + /* 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, 0)); + + /* 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(raenv->dom_info, spills); + + + /****** 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, 0); + raenv->cls_vars[raenv->n_cls_vars++] = var_add_value(raenv, get_irn_node_nr(spilled), spilled); + } + } + + /* add new variables for all reloads */ + pset_foreach(reloads, irn) + raenv->cls_vars[raenv->n_cls_vars++] = var_add_value(raenv, 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-> + * Apply these transformations to the irg. + * @return 1 if an allocation was read in. 0 otherwise. */ -static void read_and_apply_results(be_raext_env_t *raenv, char *filename) { +static int read_and_apply_results(be_raext_env_t *raenv, char *filename) { FILE *f; + 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; - //TODO: free pmap entries (the psets) pmap_foreach(raenv.vars, pme) del_pset(pme->value); + /* read the action */ + if (fscanf(f, BUFCONV, buf) != 1) + INVALID_FILE_FORMAT; + + /* 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 + + /* or do we allocate */ + if (!strcmp(buf, "allocs")) { + int var_nr, reg_nr; + + is_allocation = 1; + while (fscanf(f, " %d %d ", &var_nr, ®_nr) == 2) { + ir_node *irn; + pset *vals = get_var_values(raenv, var_nr); + + 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; + + if (!feof(f)) + INVALID_FILE_FORMAT; fclose(f); + + return is_allocation; +} + +static void check_allocation(be_raext_env_t *raenv) { + int i, o; + + for (i=0; in_cls_vars; ++i) { + var_info_t *vi1 = raenv->cls_vars[i]; + + if (vi1->var_nr == SET_REMOVED) + continue; + + for (o=0; ocls_vars[o]; + ir_node *irn1, *irn2; + + if (vi2->var_nr == SET_REMOVED) + continue; + + pset_foreach(vi1->values, irn1) + pset_foreach(vi2->values, irn2) + if (values_interfere(irn1, irn2)) { + dump_ir_block_graph_sched(raenv->irg, "ERROR"); + ir_fprintf(stdout, "SSA values %+F and %+F interfere. They belong to varible %d and %d respectively.\n", irn1, irn2, vi1->var_nr, vi2->var_nr); + assert(0 && "ERROR graph dumped"); + } + } + } } /****************************************************************************** @@ -567,6 +892,14 @@ static void 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] = "\"E:/user/kimohoff/ipd-registerallocator/win32/register allocator\""; +//static char callee[128] = "/ben/kimohoff/ipd-registerallocator/register_allocator"; + + /** * Allocate registers with an external program using a text-file interface. * @@ -576,40 +909,117 @@ static void read_and_apply_results(be_raext_env_t *raenv, char *filename) { * Read in results and apply them * */ -static void be_ra_extern_main(const be_main_env_t *env, ir_graph *irg) { +static void be_ra_extern_main(const be_irg_t *bi) { + be_main_env_t *env = bi->main_env; + ir_graph *irg = bi->irg; + be_raext_env_t raenv; int clsnr, clss; + var_info_t *vi; + + compute_doms(irg); + + raenv.irg = irg; + raenv.aenv = env->arch_env; + raenv.dom_info = be_compute_dominance_frontiers(irg); + raenv.vars = new_set(compare_var_infos, 64); + raenv.dbg = firm_dbg_register("ir.be.raextern"); + firm_dbg_set_mask(raenv.dbg, DBG_LEVEL); - raenv.irg = irg; - raenv.aenv = env->arch_env; - raenv.vars = pmap_create(); - raenv.blocks = pmap_create(); + /* Insert copies for constraints */ + handle_constraints(&raenv); + dump_ir_block_graph_sched(irg, "-extern-constr"); - /* SSA destruction */ + /* SSA destruction respectively transformation into "Conventional SSA" */ ssa_destr(&raenv); + dump_ir_block_graph_sched(irg, "-extern-ssadestr"); - be_clear_links(irg); + /* Mapping of SSA-Values <--> Variables */ phi_class_compute(irg); + be_clear_links(irg); irg_walk_graph(irg, values_to_vars, NULL, &raenv); - 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, 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); - dump_to_file(&raenv, out); + extract_vars_of_cls(&raenv); + + 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); - execute(out, in); + dump_to_file(&raenv, out); + execute(callee, out, in); + done = read_and_apply_results(&raenv, in); - read_and_apply_results(&raenv, in); + ir_snprintf(in, sizeof(in), "-extern-%s-round-%d", raenv.cls->name, round); + dump_ir_block_graph_sched(irg, in); + + round++; + } while (!done); + + check_allocation(&raenv); + + free(raenv.cls_vars); } + dump_ir_block_graph_sched(irg, "-extern-alloc"); + /* Clean up */ - pmap_destroy(raenv.blocks); - pmap_destroy(raenv.vars); + set_foreach(raenv.vars, vi) + del_pset(vi->values); + del_set(raenv.vars); + be_free_dominance_frontiers(raenv.dom_info); } + +/****************************************************************************** + ____ _ _ + / __ \ | | (_) + | | | |_ __ | |_ _ ___ _ __ ___ + | | | | '_ \| __| |/ _ \| '_ \/ __| + | |__| | |_) | |_| | (_) | | | \__ \ + \____/| .__/ \__|_|\___/|_| |_|___/ + | | + |_| + *****************************************************************************/ + +#ifdef WITH_LIBCORE + + +static const lc_opt_enum_func_ptr_items_t ssa_destr_items[] = { + { "simple", (int (*)()) ssa_destr_simple }, /* TODO make (void*) casts nicer */ + { "rastello", (int (*)()) ssa_destr_rastello }, + { NULL, NULL } +}; + +static lc_opt_enum_func_ptr_var_t ssa_destr_var = { + (int (**)()) &ssa_destr, ssa_destr_items +}; + +static const lc_opt_table_entry_t be_ra_extern_options[] = { + LC_OPT_ENT_ENUM_FUNC_PTR("ssa_destr", "SSA destruction flavor", &ssa_destr_var), + LC_OPT_ENT_STR("callee", "The external program to call", callee, sizeof(callee)), + { NULL } +}; + +static void be_ra_extern_register_options(lc_opt_entry_t *root) { + lc_opt_entry_t *grp = lc_opt_get_grp(root, "ext"); + + lc_opt_add_table(grp, be_ra_extern_options); +} + +#endif /* WITH_LIBCORE */ + +const be_ra_t be_ra_external_allocator = { +#ifdef WITH_LIBCORE + be_ra_extern_register_options, +#endif + be_ra_extern_main +};