X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fberaextern.c;h=ac38070626659e9d7c2bb78876cb0978931b7ed4;hb=6e78e108572e6c3fd33abe6557945092646b4cd9;hp=5b9748622fa80507caf9f06426df69ae1ee6470c;hpb=06cf13e40f34e97ab54f16a88e1897780093ac98;p=libfirm diff --git a/ir/be/beraextern.c b/ir/be/beraextern.c index 5b9748622..ac3807062 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) { @@ -498,24 +524,29 @@ 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) { +static INLINE unsigned 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 -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)) - 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,7 +561,7 @@ 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 %u", vi->var_nr, get_spill_costs(raenv, vi)); dump_constraint(raenv, get_first_non_phi(vi->values), -1); fprintf(f, "\n"); } @@ -571,21 +602,26 @@ static void dump_interferences(be_raext_env_t *raenv) { 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)); + } } @@ -593,10 +629,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 +653,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; @@ -672,7 +709,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; - const ir_edge_t *edge; + 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 +717,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); @@ -700,14 +746,14 @@ static INLINE void var_add_spills_and_reloads(be_raext_env_t *raenv, int var_nr) /* 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, edge->pos, get_irn_mode(get_irn_n(spill, 0)), spill); /* remember the reload */ pset_insert_ptr(reloads, reload); @@ -716,6 +762,7 @@ static INLINE void var_add_spills_and_reloads(be_raext_env_t *raenv, int var_nr) /* 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 @@ -765,6 +812,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; @@ -804,6 +852,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)) { + 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"); + } + } + } +} + /****************************************************************************** __ __ _ | \/ | (_) @@ -817,7 +892,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/ipd-registerallocator/win32/register allocator\""; +//static char callee[128] = "/ben/kimohoff/ipd-registerallocator/register_allocator"; /** @@ -838,12 +914,13 @@ static void be_ra_extern_main(const be_irg_t *bi) { 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); @@ -853,28 +930,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); }