X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fberaextern.c;h=922235e05ed7448f5963f75df4fda55ed94abbc5;hb=4d7a9507baf1737297cd4f7fc91eab209fd5d398;hp=52d14c2f498dfd7df5b0b6b9327d0417caa582a9;hpb=ff80e609f5567d665e221fbab0e30c2a004c172c;p=libfirm diff --git a/ir/be/beraextern.c b/ir/be/beraextern.c index 52d14c2f4..922235e05 100644 --- a/ir/be/beraextern.c +++ b/ir/be/beraextern.c @@ -28,15 +28,17 @@ node ::= node-info node-info ::= node-nr spill-costs . -interf ::= 'interferences' '{' edge* '}' . // Interference edges of the graph +interf ::= 'interferences' '{' i-edge* '}' . // Interference edges of the graph -affinities ::= 'affinities' '{' edge* '}' . // Affinity edges of the graph +i-edge ::= '(' node-nr ',' node-nr ')' . -edge ::= '(' node-nr ',' node-nr ')' . +affinities ::= 'affinities' '{' a-edge* '}' . // Affinity edges of the graph +a-edge ::= '(' node-nr ',' node-nr ',' weight ')' . -spill-costs, regcount, node-nr ::= integer . +weight, regcount, node-nr ::= int32 . +spill-costs ::= int32 . // negative spill costs indicate unspillable The output file format ----------------------- @@ -64,6 +66,7 @@ alloc ::= node-nr reg-nr . #include #include +#include #ifdef WITH_LIBCORE #include #include @@ -90,12 +93,15 @@ alloc ::= node-nr reg-nr . #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; @@ -157,6 +163,23 @@ static INLINE ir_node *get_first_phi(pset *s) { 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) + /****************************************************************************** _____ _ _____ _ / ____| | | / ____| (_) @@ -433,6 +456,9 @@ static void values_to_vars(ir_node *irn, void *env) { int nr; pset *vals; + if(arch_get_irn_reg_class(raenv->aenv, irn, -1) == NULL) + return; + vals = get_phi_class(irn); if (vals) { @@ -445,8 +471,10 @@ static void values_to_vars(ir_node *irn, void *env) { } /* values <--> var mapping */ - pset_foreach(vals, irn) + pset_foreach(vals, irn) { + DBG((raenv->dbg, 0, "Var %d contains %+F\n", nr, irn)); var_add_value(raenv, nr, irn); + } } @@ -498,24 +526,31 @@ static INLINE void dump_constraint(be_raext_env_t *raenv, ir_node *irn, int pos) } } -static INLINE int get_spill_costs(var_info_t *vi) { +#define UNSPILLABLE -1 + +static INLINE int get_spill_costs(be_raext_env_t *raenv, var_info_t *vi) { ir_node *irn; - int n_spills=0, n_reloads=0; + int c_spills=0, c_reloads=0; pset_foreach(vi->values, irn) { + if (arch_irn_is_ignore(raenv->aenv, irn) || 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)) - n_reloads++; + c_reloads += get_reload_weight(edge->src); } else { /* number of spills is the number of non-phi values for this var */ - n_spills++; + c_spills += get_spill_weight(irn); } } - return n_spills + n_reloads; + return c_spills + c_reloads; } static void dump_nodes(be_raext_env_t *raenv) { @@ -530,12 +565,13 @@ static void dump_nodes(be_raext_env_t *raenv) { if (vi->var_nr == SET_REMOVED) continue; - fprintf(f, "%d %d", vi->var_nr, get_spill_costs(vi)); + 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); } @@ -565,27 +601,35 @@ static void dump_interferences(be_raext_env_t *raenv) { pset_break(vi1->values); pset_break(vi2->values); 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; arch_register_req_t req; int pos, max; var_info_t *vi1, *vi2; + if (arch_get_irn_reg_class(raenv->aenv, irn, -1) == NULL || arch_irn_is_ignore(raenv->aenv, irn)) + return; + vi1 = get_var_info(irn); /* copies have affinities */ - /* TODO? remove this case by adding should_be_equal requirements */ if (arch_irn_classify(raenv->aenv, irn) == arch_irn_class_copy) { - vi2 = get_var_info(get_irn_n(irn, 0)); + ir_node *other = get_irn_n(irn, be_pos_Copy_orig); + + if (! arch_irn_is_ignore(raenv->aenv, other)) { + vi2 = 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)); + } } @@ -593,10 +637,10 @@ static void dump_affinities_walker(ir_node *irn, void *env) { for (pos = 0, max = get_irn_arity(irn); posaenv, &req, irn, pos); - if (arch_register_req_is(&req, should_be_same)) { + 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)\n", vi1->var_nr, vi2->var_nr); + fprintf(raenv->f, "(%d, %d, %d)\n", vi1->var_nr, vi2->var_nr, get_affinity_weight(irn)); } } } @@ -617,6 +661,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; @@ -653,6 +698,7 @@ static void execute(char *prog_to_call, char *out_file, char *result_file) { 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."); } /****************************************************************************** @@ -672,7 +718,8 @@ static void execute(char *prog_to_call, char *out_file, char *result_file) { 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; - const ir_edge_t *edge; + 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; @@ -680,17 +727,26 @@ static INLINE void var_add_spills_and_reloads(be_raext_env_t *raenv, int var_nr) 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 */ - ctx = get_first_phi(vi->values); + /* 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)) + if (is_Phi(irn)) { + sched_remove(irn); continue; + } /* all ordinary nodes must be spilled */ - spill = be_new_Spill(raenv->cls, raenv->irg, get_nodes_block(irn), irn, ctx); - sched_add_after(irn, spill); + DBG((raenv->dbg, LEVEL_2, " spilling %+F\n", irn)); + spill = be_spill(raenv->aenv, irn, ctx); /* remember the spill */ pset_insert_ptr(spills, spill); @@ -698,23 +754,26 @@ static INLINE void var_add_spills_and_reloads(be_raext_env_t *raenv, int var_nr) 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(irn, edge) { + foreach_out_edge_safe(irn, edge, ne) { ir_node *reload, *src = edge->src; - if (is_Phi(src)) + if (is_Phi(src) || be_is_Spill(src)) continue; /* all real uses must be reloaded */ - reload = be_new_Reload(raenv->cls, raenv->irg, get_nodes_block(src), get_irn_mode(get_irn_n(spill, 0)), spill); - sched_add_before(src, reload); + 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_sets(raenv->dom_info, spills, reloads); + be_ssa_constr_set(raenv->dom_info, spills); /****** correct the variable <--> values mapping: ****** @@ -737,16 +796,16 @@ static INLINE void var_add_spills_and_reloads(be_raext_env_t *raenv, int var_nr) /* ...add new vars for each non-phi-member */ pset_foreach(spills, irn) { - ir_node *spilled = get_irn_n(irn, 0); + ir_node *spilled = get_irn_n(irn, be_pos_Spill_val); 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) + pset_foreach(reloads, irn) { + assert(get_irn_node_nr(irn) != 1089); raenv->cls_vars[raenv->n_cls_vars++] = var_add_value(raenv, get_irn_node_nr(irn), irn); - - + } del_pset(spills); del_pset(reloads); @@ -768,6 +827,7 @@ static int read_and_apply_results(be_raext_env_t *raenv, char *filename) { if (!(f = fopen(filename, "rt"))) { fprintf(stderr, "Could not open file %s for reading\n", filename); + assert(0); exit(0xdeadbeef); } raenv->f = f; @@ -807,6 +867,33 @@ static int read_and_apply_results(be_raext_env_t *raenv, char *filename) { 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) && 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 varible %d and %d respectively.\n", irn1, irn2, vi1->var_nr, vi2->var_nr); + assert(0 && "ERROR graph dumped"); + } + } + } +} + /****************************************************************************** __ __ _ | \/ | (_) @@ -820,7 +907,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] = "/ben/kimohoff/ipd-registerallocator/register_allocator"; +static char callee[128] = "\"E:/user/kimohoff/public/register allocator\""; +//static char callee[128] = "/ben/kimohoff/ipd-registerallocator/register_allocator"; /** @@ -836,17 +924,18 @@ 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; + be_raext_env_t raenv; int clsnr, clss; var_info_t *vi; compute_doms(irg); - be_liveness(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); /* Insert copies for constraints */ handle_constraints(&raenv); @@ -856,28 +945,38 @@ static void be_ra_extern_main(const be_irg_t *bi) { ssa_destr(&raenv); dump_ir_block_graph_sched(irg, "-extern-ssadestr"); - /* Mapping of SSA-Values <--> Variables */ phi_class_compute(irg); be_clear_links(irg); irg_walk_graph(irg, values_to_vars, NULL, &raenv); + /* 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); - } + + 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); }