X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;ds=sidebyside;f=ir%2Fbe%2Fbecopypbqp.c;h=92fdcfcf5a602366b07542ab0482bd732ee918ea;hb=75c3d36f124dbac5780d9c33cbfc4b30ae8e29a0;hp=0b633dddaa94ed6123be4812bfcfebbf7309a25e;hpb=532c2cd96f3e03ae22d05a36bb213510a274ec7b;p=libfirm diff --git a/ir/be/becopypbqp.c b/ir/be/becopypbqp.c index 0b633ddda..92fdcfcf5 100644 --- a/ir/be/becopypbqp.c +++ b/ir/be/becopypbqp.c @@ -8,6 +8,8 @@ #ifdef FIRM_KAPS +#include "becopypbqp.h" + #include "kaps.h" #include "pbqp_t.h" #include "vector.h" @@ -19,12 +21,22 @@ #include "becopyopt_t.h" #include "beifg.h" #include "beifg_t.h" +#include "bemodule.h" #include "irprintf_t.h" +#include "besched.h" +#include "bearch.h" +#include "irdom.h" +#include "iredges.h" +#include "timing.h" + #include "error.h" #include "bitset.h" #include "pmap.h" +#include "plist.h" +#include "pqueue.h" +#if KAPS_DUMP static FILE *my_open(const be_chordal_env_t *env, const char *prefix, const char *suffix) { FILE *result; @@ -48,45 +60,100 @@ static FILE *my_open(const be_chordal_env_t *env, const char *prefix, const char return result; } +#endif -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); - ir_node *ifg_node, *if_neighb_node; +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; - pbqp *pbqp_problem; - unsigned number_registers = co->cls->n_regs; - unsigned number_nodes = 0; - unsigned int nodeIdx = 0; + sched_foreach(block, irn) { + if (get_irn_mode(irn) == mode_T) { + const ir_edge_t *edge; - bitset_t *ignore_registers; - pmap *map; + foreach_out_edge(irn, edge) { + ir_node *proj = get_edge_src_irn(edge); + if (!arch_irn_consider_in_reg_alloc(pbqp_co->cls, proj)) + continue; - // count nodes in ifg - be_ifg_foreach_node(co->cenv->ifg, nodes_it, ifg_node) { - number_nodes++; - } + // 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(restrictedNodesQueue,proj, be_ifg_degree(pbqp_co->ifg,proj)); + } + else { + pqueue_put(queue,proj, be_ifg_degree(pbqp_co->ifg,proj)); + } + } - // create empty PBQP instance - pbqp_problem = alloc_pbqp(number_nodes); + /* first insert all restricted nodes */ + while(!pqueue_empty(restrictedNodesQueue)) { + plist_insert_back(pbqp_co->rpeo, get_node(pbqp_co->pbqp, get_irn_idx(pqueue_pop_front(restrictedNodesQueue)))); + } - // - ignore_registers = bitset_malloc(number_registers); - be_put_ignore_regs(co->cenv->birg, co->cls, ignore_registers); + /* insert proj nodes into reverse perfect elimination order (descending by their degree in ifg) */ + while(!pqueue_empty(queue)) { + plist_insert_back(pbqp_co->rpeo, get_node(pbqp_co->pbqp, get_irn_idx(pqueue_pop_front(queue)))); + } - // create map - map = pmap_create_ex(number_nodes); + } else { + if (!arch_irn_consider_in_reg_alloc(pbqp_co->cls, irn)) + continue; - // add costs vector to nodes - nodeIdx = 0; + /* 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(restrictedNodesQueue); +} + +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_node *ifg_node; + ir_node *if_neighb_node; + pbqp_co_t pbqp_co; + unsigned row, col; + + #if KAPS_TIMING + printf("==>> START PBQP TIMING on IRG %s (%s) <<==\n", get_entity_name(get_irg_entity(co->irg)), arch_register_class_name(co->cls)); + #endif + + /* start timer */ + ir_timer_reset_and_start(t_ra_copymin_pbqp_create); + + /* create and initialize data structure for pbqp copy minimization optimization */ + pbqp_co.cls = co->cls; + pbqp_co.rpeo = plist_new(); + 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); + + /* add costs vector to nodes */ be_ifg_foreach_node(co->cenv->ifg, nodes_it, ifg_node) { - // create costs vector - struct vector *costs_vector = vector_alloc(pbqp_problem, number_registers); + int cntFreeChoosableRegs = 0; + + /* create costs vector */ + struct vector *costs_vector = vector_alloc(pbqp_co.pbqp, number_registers); - // set costs + /* set costs */ unsigned int cnt; for(cnt = 0; cnt < costs_vector->len; cnt++) { - if (bitset_is_set(ignore_registers,cnt)) { + if (bitset_is_set(pbqp_co.ignore_reg,cnt)) { vector_set(costs_vector, cnt, INF_COSTS); } else { @@ -96,125 +163,149 @@ int co_solve_heuristic_pbqp(copy_opt_t *co) { } else { vector_set(costs_vector, cnt, 0); + cntFreeChoosableRegs++; } } - // add description + #if KAPS_ENABLE_VECTOR_NAMES + /* add description */ vector_set_description(costs_vector, cnt, arch_register_for_index(co->cls, cnt)->name); + #endif } - // add costs vector to node - add_node_costs(pbqp_problem, nodeIdx, costs_vector); + /* 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(map, ifg_node, get_node(pbqp_problem,nodeIdx)); + if(cntFreeChoosableRegs <= 4) { + /* node is restricted */ + bitset_set(pbqp_co.restricted_nodes, get_irn_idx(ifg_node)); + } + } - // increment nodeIndex - nodeIdx++; + /* 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++) { + pbqp_matrix_set(ife_matrix, row, row, INF_COSTS); } - be_ifg_foreach_node(co->cenv->ifg, nodes_it, ifg_node) { - pbqp_node *src_node = pmap_find(map,ifg_node)->value; - unsigned int srcNodeIdx = src_node->index; + /* create costs matrix for affinity edges */ + struct pbqp_matrix *afe_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(afe_matrix, row, col, 0); + } + else { + pbqp_matrix_set(afe_matrix, row, col, 2); + } + } + } - // add costs matrix between nodes (interference edge) + /* add pbqp edges and cost matrix */ + be_ifg_foreach_node(co->cenv->ifg, nodes_it, ifg_node) { + /* add costs matrix between nodes (interference edge) */ be_ifg_foreach_neighbour(co->cenv->ifg, neigh_it, ifg_node, if_neighb_node) { - pbqp_node *trg_node = pmap_find(map,if_neighb_node)->value; - if(get_edge(pbqp_problem, srcNodeIdx, trg_node->index) == NULL) { - // create costs matrix - struct pbqp_matrix *matrix = pbqp_matrix_alloc(pbqp_problem, number_registers, number_registers); - - // set costs - unsigned row, col; - for(row = 0; row < number_registers; row++) { - for(col = 0; col < number_registers; col++) { - if(row == col) { - pbqp_matrix_set(matrix, row, col, INF_COSTS); - } - else { - pbqp_matrix_set(matrix, row, col, 2); - } - } - } + if(get_edge(pbqp_co.pbqp,get_irn_idx(ifg_node), get_irn_idx(if_neighb_node)) == NULL) { + /* copy matrix */ + struct pbqp_matrix *matrix = pbqp_matrix_copy(pbqp_co.pbqp, ife_matrix); + + /* add costs matrix to interference edge */ + add_edge_costs(pbqp_co.pbqp, get_irn_idx(ifg_node), get_irn_idx(if_neighb_node) , matrix); - // add costs matrix to interference edge - add_edge_costs(pbqp_problem, srcNodeIdx, trg_node->index , matrix); } } - // add costs matrix between nodes (affinety edge) + /* add costs matrix between nodes (affinity edge) */ affinity_node_t *aff_node = get_affinity_info(co, ifg_node); neighb_t *aff_neighb_node; if(aff_node != NULL) { co_gs_foreach_neighb(aff_node, aff_neighb_node) { - pbqp_node *trg_node = pmap_find(map,aff_neighb_node->irn)->value; - if(get_edge(pbqp_problem, srcNodeIdx, trg_node->index) == NULL) { - // create costs matrix - struct pbqp_matrix *matrix = pbqp_matrix_alloc(pbqp_problem, number_registers, number_registers); - - // set costs - unsigned row, col; - for(row = 0; row < number_registers; row++) { - for(col = 0; col < number_registers; col++) { - if(row == col) { - pbqp_matrix_set(matrix, row, col, 0); - } - else { - pbqp_matrix_set(matrix, row, col, 2); - } - } - } - - // add costs matrix to interference edge - add_edge_costs(pbqp_problem, srcNodeIdx, trg_node->index , matrix); + /* ignore Unknowns */ + 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 */ + struct pbqp_matrix *matrix = pbqp_matrix_copy(pbqp_co.pbqp, afe_matrix); + + /* add costs matrix to affinity edge */ + add_edge_costs(pbqp_co.pbqp, get_irn_idx(aff_node->irn), get_irn_idx(aff_neighb_node->irn) , matrix); } } } } -#if KAPS_DUMP - // dump graph before solving pbqp - FILE *file_before = my_open(co->cenv, "", "-before.html"); - set_dumpfile(pbqp_problem, file_before); - pbqp_dump_input(pbqp_problem); -#endif + /* create reverse perfect elimination order */ + assure_doms(co->irg); + dom_tree_walk_irg(co->irg, insert_into_reverse_peo, NULL, &pbqp_co); + /* stop timer */ + ir_timer_stop(t_ra_copymin_pbqp_create); - // solve pbqp problem - solve_pbqp_heuristical(pbqp_problem); - //solve_pbqp_brute_force(pbqp_problem); - num solution = get_solution(pbqp_problem); + #if KAPS_DUMP + // dump graph before solving pbqp + FILE *file = my_open(co->cenv, "", "-pbqp_copymin.html"); + set_dumpfile(pbqp_co.pbqp, file); + #endif + + /* start timer */ + ir_timer_reset_and_start(t_ra_copymin_pbqp_solve); + + /* solve pbqp problem using a reverse perfect elimination order */ + solve_pbqp_heuristical_co(pbqp_co.pbqp, pbqp_co.rpeo); + num solution = get_solution(pbqp_co.pbqp); + + /* stop time */ + ir_timer_stop(t_ra_copymin_pbqp_solve); + + #if KAPS_STATISTIC + printf("==>> PBQP STATISTIC on IRG %s (%s) <<==\n", get_entity_name(get_irg_entity(co->irg)), arch_register_class_name(co->cls)); + printf("Number of Nodes: %d\n", number_nodes); + printf("Number of independent edges : %d\n", pbqp_co.pbqp->num_edges); + printf("Number of trivial solved nodes: %d\n", pbqp_co.pbqp->num_r0); + printf("Number of R1 reductions : %d\n", pbqp_co.pbqp->num_r1); + printf("Number of R2 reductions : %d\n", pbqp_co.pbqp->num_r2); + printf("Number of RN reductions : %d\n", pbqp_co.pbqp->num_rn); + #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("==>> 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"); - // printf("Solution (%s): %d\n",co->name, (int)solution); - - // coloring ifg + /* coloring ifg */ be_ifg_foreach_node(co->cenv->ifg, nodes_it, ifg_node) { - pbqp_node *node = pmap_find(map,ifg_node)->value; - num index = get_node_solution(pbqp_problem, node->index); + num index = get_node_solution(pbqp_co.pbqp, get_irn_idx(ifg_node)); const arch_register_t *reg = arch_register_for_index(co->cls, index); arch_set_irn_register(ifg_node, reg); } -#if KAPS_DUMP - // dump graph after solving pbqp - FILE *file_after = my_open(co->cenv, "", "-after.html"); - set_dumpfile(pbqp_problem, file_after); - pbqp_dump_input(pbqp_problem); -#endif + /* free allocated memory */ + #if KAPS_DUMP + fclose(file); + #endif + bitset_free(pbqp_co.ignore_reg); + bitset_free(pbqp_co.restricted_nodes); + plist_free(pbqp_co.rpeo); + free_pbqp(pbqp_co.pbqp); + return 0; +} - // free pbqp resources -#if KAPS_DUMP - fclose(file_before); - fclose(file_after); -#endif - bitset_free(ignore_registers); - pmap_destroy(map); - free_pbqp(pbqp_problem); +void be_init_copypbqp(void) +{ + static co_algo_info copyheur = { + co_solve_heuristic_pbqp, 0 + }; - return 0; + be_register_copyopt("pbqp", ©heur); } +BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copypbqp); + #endif