X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopypbqp.c;h=16a50e61063a9bca5554552a71cfa802b29c0ec8;hb=e0e9e9ace61d3ec46e4d09c7ab2c6947b17b2778;hp=281619c7329d583fdb966f963746ace3bc00e351;hpb=f5f01800a415844019068fbde56855f33788dee9;p=libfirm diff --git a/ir/be/becopypbqp.c b/ir/be/becopypbqp.c index 281619c73..16a50e610 100644 --- a/ir/be/becopypbqp.c +++ b/ir/be/becopypbqp.c @@ -15,7 +15,7 @@ #include "vector.h" #include "matrix.h" #include "html_dumper.h" -#include "heuristical.h" +#include "heuristical_co.h" #include "pbqp_node_t.h" #include "becopyopt_t.h" @@ -62,15 +62,14 @@ static FILE *my_open(const be_chordal_env_t *env, const char *prefix, const char } #endif -static void insert_into_reverse_peo(ir_node *block, void *data) { - pqueue_t *queue = new_pqueue(); - pqueue_t *constatQueue = new_pqueue(); - pbqp_co_t *pbqp_co = data; +static void insert_into_reverse_peo(ir_node *block, void *data) +{ + pqueue_t *queue = new_pqueue(); + pqueue_t *restrictedNodesQueue = new_pqueue(); + pbqp_co_t *pbqp_co = data; ir_node *irn; sched_foreach(block, irn) { - pbqp_node *node; - if (get_irn_mode(irn) == mode_T) { const ir_edge_t *edge; @@ -79,12 +78,9 @@ static void insert_into_reverse_peo(ir_node *block, void *data) { if (!arch_irn_consider_in_reg_alloc(pbqp_co->cls, proj)) continue; - // get related pbqp_node and insert into reverse peo - assert(node && "No corresponding PBQP-Node found!"); - // insert proj node into priority queue (descending by their degree in ifg) if(bitset_is_set(pbqp_co->restricted_nodes, get_irn_idx(proj))) { - pqueue_put(constatQueue,proj, be_ifg_degree(pbqp_co->ifg,proj)); + pqueue_put(restrictedNodesQueue,proj, be_ifg_degree(pbqp_co->ifg,proj)); } else { pqueue_put(queue,proj, be_ifg_degree(pbqp_co->ifg,proj)); @@ -92,8 +88,8 @@ static void insert_into_reverse_peo(ir_node *block, void *data) { } /* first insert all restricted nodes */ - while(!pqueue_empty(constatQueue)) { - plist_insert_back(pbqp_co->rpeo, get_node(pbqp_co->pbqp, get_irn_idx(pqueue_pop_front(constatQueue)))); + while(!pqueue_empty(restrictedNodesQueue)) { + plist_insert_back(pbqp_co->rpeo, get_node(pbqp_co->pbqp, get_irn_idx(pqueue_pop_front(restrictedNodesQueue)))); } /* insert proj nodes into reverse perfect elimination order (descending by their degree in ifg) */ @@ -105,24 +101,24 @@ static void insert_into_reverse_peo(ir_node *block, void *data) { if (!arch_irn_consider_in_reg_alloc(pbqp_co->cls, irn)) continue; - /* get related pbqp_node and insert into reverse peo */ - assert(node && "No corresponding PBQP-Node found!"); + /* insert pbqp node into reverse peo */ plist_insert_back(pbqp_co->rpeo, get_node(pbqp_co->pbqp, get_irn_idx(irn))); } } /* free priority queues */ del_pqueue(queue); - del_pqueue(constatQueue); + del_pqueue(restrictedNodesQueue); } -static int co_solve_heuristic_pbqp(copy_opt_t *co) { +static int co_solve_heuristic_pbqp(copy_opt_t *co) +{ void *nodes_it = be_ifg_nodes_iter_alloca(co->cenv->ifg); void *neigh_it = be_ifg_neighbours_iter_alloca(co->cenv->ifg); unsigned number_registers = co->cls->n_regs; unsigned number_nodes = get_irg_last_idx(co->irg); - ir_timer_t *t_ra_copymin_pbqp_create = ir_timer_register("be_co_pbqp_create", "copy minimization pbqp create"); - ir_timer_t *t_ra_copymin_pbqp_solve = ir_timer_register("be_co_pbqp_solve", "copy minimization pbqp solve"); + ir_timer_t *t_ra_copymin_pbqp_create = ir_timer_new(); + ir_timer_t *t_ra_copymin_pbqp_solve = ir_timer_new(); ir_node *ifg_node; ir_node *if_neighb_node; pbqp_co_t pbqp_co; @@ -138,12 +134,14 @@ static int co_solve_heuristic_pbqp(copy_opt_t *co) { /* create and initialize data structure for pbqp copy minimization optimization */ pbqp_co.cls = co->cls; pbqp_co.rpeo = plist_new(); - pbqp_co.map = pmap_create_ex(number_nodes); pbqp_co.pbqp = alloc_pbqp(number_nodes); pbqp_co.ignore_reg = bitset_malloc(number_registers); pbqp_co.restricted_nodes = bitset_malloc(number_nodes); pbqp_co.ifg = co->cenv->ifg; + /* no node is restricted at the beginning */ + bitset_clear_all(pbqp_co.restricted_nodes); + /* get ignored registers */ be_put_ignore_regs(co->cenv->birg, co->cls, pbqp_co.ignore_reg); @@ -180,33 +178,17 @@ static int co_solve_heuristic_pbqp(copy_opt_t *co) { /* add costs vector to node */ add_node_costs(pbqp_co.pbqp, get_irn_idx(ifg_node), costs_vector); - /* insert ir_node and pbqp_node into map */ - pmap_insert(pbqp_co.map, ifg_node, get_node(pbqp_co.pbqp, get_irn_idx(ifg_node))); - if(cntFreeChoosableRegs <= 4) { /* node is restricted */ bitset_set(pbqp_co.restricted_nodes, get_irn_idx(ifg_node)); } - else - { - /* node is not restricted */ - bitset_clear(pbqp_co.restricted_nodes, get_irn_idx(ifg_node)); - } - } /* create costs matrix for interference edges */ struct pbqp_matrix *ife_matrix = pbqp_matrix_alloc(pbqp_co.pbqp, number_registers, number_registers); /* set costs */ for(row = 0; row < number_registers; row++) { - for(col = 0; col < number_registers; col++) { - if(row == col) { - pbqp_matrix_set(ife_matrix, row, col, INF_COSTS); - } - else { - pbqp_matrix_set(ife_matrix, row, col, 0); - } - } + pbqp_matrix_set(ife_matrix, row, row, INF_COSTS); } /* create costs matrix for affinity edges */ @@ -233,6 +215,7 @@ static int co_solve_heuristic_pbqp(copy_opt_t *co) { /* add costs matrix to interference edge */ add_edge_costs(pbqp_co.pbqp, get_irn_idx(ifg_node), get_irn_idx(if_neighb_node) , matrix); + } } @@ -242,9 +225,8 @@ static int co_solve_heuristic_pbqp(copy_opt_t *co) { if(aff_node != NULL) { co_gs_foreach_neighb(aff_node, aff_neighb_node) { /* ignore Unknowns */ - if(pmap_find(pbqp_co.map,aff_neighb_node->irn) == NULL) { + if(get_node(pbqp_co.pbqp, get_irn_idx(aff_neighb_node->irn)) == NULL) continue; - } if(get_edge(pbqp_co.pbqp, get_irn_idx(aff_node->irn), get_irn_idx(aff_neighb_node->irn)) == NULL) { /* copy matrix */ @@ -266,9 +248,8 @@ static int co_solve_heuristic_pbqp(copy_opt_t *co) { #if KAPS_DUMP // dump graph before solving pbqp - FILE *file_before = my_open(co->cenv, "", "-before.html"); - set_dumpfile(pbqp_co.pbqp, file_before); - pbqp_dump_input(pbqp_co.pbqp); + FILE *file = my_open(co->cenv, "", "-pbqp_copymin.html"); + set_dumpfile(pbqp_co.pbqp, file); #endif /* start timer */ @@ -292,20 +273,15 @@ static int co_solve_heuristic_pbqp(copy_opt_t *co) { #endif #if KAPS_TIMING - printf("%-20s: %8.3lf msec\n" , ir_timer_get_description(t_ra_copymin_pbqp_create), (double)ir_timer_elapsed_usec(t_ra_copymin_pbqp_create) / 1000.0); - printf("%-20s: %8.3lf msec\n" , ir_timer_get_description(t_ra_copymin_pbqp_solve), (double)ir_timer_elapsed_usec(t_ra_copymin_pbqp_solve) / 1000.0); + printf("%-20s: %8.3lf msec\n", "copy minimization pbqp create", + (double)ir_timer_elapsed_usec(t_ra_copymin_pbqp_create) / 1000.0); + printf("%-20s: %8.3lf msec\n" , "copy minimization pbqp solve", + (double)ir_timer_elapsed_usec(t_ra_copymin_pbqp_solve) / 1000.0); printf("==>> END PBQP TIMING on IRG %s (%s) <<==\n", get_entity_name(get_irg_entity(co->irg)), arch_register_class_name(co->cls)); #endif assert(solution != INF_COSTS && "No PBQP solution found"); - #if KAPS_DUMP - /* dump graph after solving pbqp */ - FILE *file_after = my_open(co->cenv, "", "-after.html"); - set_dumpfile(pbqp_co.pbqp, file_after); - pbqp_dump_input(pbqp_co.pbqp); - #endif - /* coloring ifg */ be_ifg_foreach_node(co->cenv->ifg, nodes_it, ifg_node) { num index = get_node_solution(pbqp_co.pbqp, get_irn_idx(ifg_node)); @@ -315,12 +291,10 @@ static int co_solve_heuristic_pbqp(copy_opt_t *co) { /* free allocated memory */ #if KAPS_DUMP - fclose(file_before); - fclose(file_after); + fclose(file); #endif bitset_free(pbqp_co.ignore_reg); bitset_free(pbqp_co.restricted_nodes); - pmap_destroy(pbqp_co.map); plist_free(pbqp_co.rpeo); free_pbqp(pbqp_co.pbqp);