X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fberaextern.c;h=182138c5ab9cb1073ee9adc0102ff092ddc33ddb;hb=e6ad8ee4680a88db8652483c2c6f3124f3d9a888;hp=9f2e6281a4465750a8371c489456fa6567c9fd32;hpb=9ca9386adeacf03a4698a15ef45035b8fb6870f2;p=libfirm diff --git a/ir/be/beraextern.c b/ir/be/beraextern.c index 9f2e6281a..182138c5a 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 ')' . -regcount, node-nr ::= int32 . -spill-costs ::= uint32 . + +weight, regcount, node-nr ::= int32 . +spill-costs ::= int32 . // negative spill costs indicate unspillable The output file format ----------------------- @@ -161,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) + /****************************************************************************** _____ _ _____ _ / ____| | | / ____| (_) @@ -452,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); + } } @@ -505,14 +526,14 @@ static INLINE void dump_constraint(be_raext_env_t *raenv, ir_node *irn, int pos) } } -static INLINE unsigned int get_spill_costs(be_raext_env_t *raenv, var_info_t *vi) { +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)) { pset_break(vi->values); - return UINT_MAX; + return -1; } if (is_Phi(irn)) { @@ -520,14 +541,14 @@ static INLINE unsigned int get_spill_costs(be_raext_env_t *raenv, var_info_t *vi 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) { @@ -542,12 +563,13 @@ static void dump_nodes(be_raext_env_t *raenv) { if (vi->var_nr == SET_REMOVED) continue; - fprintf(f, "%d %u", vi->var_nr, get_spill_costs(raenv, 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); } @@ -577,27 +599,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, 0); - fprintf(raenv->f, "(%d, %d)\n", vi1->var_nr, vi2->var_nr); + 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)); + } } @@ -605,10 +635,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)); } } } @@ -666,6 +696,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."); } /****************************************************************************** @@ -685,6 +716,7 @@ 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; + 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 */ @@ -720,6 +752,8 @@ 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, 0)); + /* insert reloads and wire them arbitrary*/ pset_foreach(vi->values, irn) foreach_out_edge_safe(irn, edge, ne) { @@ -729,7 +763,8 @@ static INLINE void var_add_spills_and_reloads(be_raext_env_t *raenv, int var_nr) /* 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, edge->pos, get_irn_mode(get_irn_n(spill, 0)), spill); + 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); @@ -759,14 +794,17 @@ 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, 1); + assert(get_irn_node_nr(spilled) != 1089); 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); @@ -802,7 +840,6 @@ static int read_and_apply_results(be_raext_env_t *raenv, char *filename) { int var_nr; while (fscanf(f, " %d ", &var_nr) == 1) var_add_spills_and_reloads(raenv, var_nr); - be_liveness(raenv->irg); } else /* or do we allocate */ @@ -829,6 +866,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"); + } + } + } +} + /****************************************************************************** __ __ _ | \/ | (_) @@ -842,7 +906,7 @@ 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] = "\"E:/user/kimohoff/ipd-registerallocator/win32/register allocator\""; +static char callee[128] = "\"E:/user/kimohoff/public/register allocator\""; //static char callee[128] = "/ben/kimohoff/ipd-registerallocator/register_allocator"; @@ -859,7 +923,7 @@ 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; @@ -884,7 +948,7 @@ static void be_ra_extern_main(const be_irg_t *bi) { phi_class_compute(irg); be_clear_links(irg); irg_walk_graph(irg, values_to_vars, NULL, &raenv); - be_liveness(irg); + /* For all register classes */ for(clsnr = 0, clss = arch_isa_get_n_reg_class(raenv.aenv->isa); clsnr < clss; ++clsnr) { @@ -899,6 +963,8 @@ static void be_ra_extern_main(const be_irg_t *bi) { 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); @@ -909,6 +975,8 @@ static void be_ra_extern_main(const be_irg_t *bi) { round++; } while (!done); + check_allocation(&raenv); + free(raenv.cls_vars); }