X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopypbqp.c;h=7b41d4f4f9a047f96fbc23d805996a3ed4207a63;hb=85536ec36b4d2b20dad0767c3d25e3c41ce8c4d5;hp=c222bbe558ffa168cb67d914fb62ccb0a975990d;hpb=e0b1dd8b1dea38693eed0fb18d1149d76b17ff2c;p=libfirm diff --git a/ir/be/becopypbqp.c b/ir/be/becopypbqp.c index c222bbe55..7b41d4f4f 100644 --- a/ir/be/becopypbqp.c +++ b/ir/be/becopypbqp.c @@ -4,6 +4,11 @@ * Created on: Aug 28, 2009 * Author: bersch */ +#include "config.h" + +#ifdef FIRM_KAPS + +#include "becopypbqp.h" #include "kaps.h" #include "pbqp_t.h" @@ -16,12 +21,21 @@ #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 "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; @@ -45,45 +59,81 @@ 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(); + 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) { + pbqp_node *node; - bitset_t *ignore_registers; - pmap *map; + if (get_irn_mode(irn) == mode_T) { + const ir_edge_t *edge; - // count nodes in ifg - be_ifg_foreach_node(co->cenv->ifg, nodes_it, ifg_node) { - number_nodes++; + 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; + + // 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) + pqueue_put(queue,proj, be_ifg_degree(pbqp_co->ifg,proj)); + } + + /* 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)))); + } + } else { + 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!"); + plist_insert_back(pbqp_co->rpeo, get_node(pbqp_co->pbqp, get_irn_idx(irn))); + } } - // create empty PBQP instance - pbqp_problem = alloc_pbqp(number_nodes); + /* free priority queue */ + del_pqueue(queue); +} + +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); + ir_node *ifg_node; + ir_node *if_neighb_node; + + pbqp_co_t pbqp_co; + + unsigned number_registers = co->cls->n_regs; + unsigned number_nodes = get_irg_last_idx(co->irg); - // - ignore_registers = bitset_malloc(number_registers); - be_put_ignore_regs(co->cenv->birg, co->cls, ignore_registers); + /* 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.ifg = co->cenv->ifg; - // create map - map = pmap_create_ex(number_nodes); + /* get ignored registers */ + be_put_ignore_regs(co->cenv->birg, co->cls, pbqp_co.ignore_reg); - // add costs vector to nodes - nodeIdx = 0; + /* 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); + /* 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 { @@ -95,33 +145,28 @@ int co_solve_heuristic_pbqp(copy_opt_t *co) { vector_set(costs_vector, cnt, 0); } } - - // 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); - - // insert ir_node and pbqp_node into map - pmap_insert(map, ifg_node, get_node(pbqp_problem,nodeIdx)); + /* add costs vector to node */ + add_node_costs(pbqp_co.pbqp, get_irn_idx(ifg_node), costs_vector); - // increment nodeIndex - nodeIdx++; + /* 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))); } + /* add pbqp edges and cost matrix */ 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; - - // add costs matrix between nodes (interference edge) + /* 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); + if(get_edge(pbqp_co.pbqp,get_irn_idx(ifg_node), get_irn_idx(if_neighb_node)) == NULL) { + /* create costs matrix */ + struct pbqp_matrix *matrix = pbqp_matrix_alloc(pbqp_co.pbqp, number_registers, number_registers); - // set costs + /* set costs */ unsigned row, col; for(row = 0; row < number_registers; row++) { for(col = 0; col < number_registers; col++) { @@ -129,27 +174,33 @@ int co_solve_heuristic_pbqp(copy_opt_t *co) { pbqp_matrix_set(matrix, row, col, INF_COSTS); } else { - pbqp_matrix_set(matrix, row, col, 2); + pbqp_matrix_set(matrix, row, col, 0); } } } - // add costs matrix to interference edge - add_edge_costs(pbqp_problem, srcNodeIdx, trg_node->index , 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 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); + pmap_entry *ptr_pbqp_node = pmap_find(pbqp_co.map,aff_neighb_node->irn); + + /* ignore Unknowns */ + if(ptr_pbqp_node == NULL) { + continue; + } - // set costs + if(get_edge(pbqp_co.pbqp, get_irn_idx(aff_node->irn), get_irn_idx(aff_neighb_node->irn)) == NULL) { + /* create costs matrix */ + struct pbqp_matrix *matrix = pbqp_matrix_alloc(pbqp_co.pbqp, number_registers, number_registers); + + /* set costs */ unsigned row, col; for(row = 0; row < number_registers; row++) { for(col = 0; col < number_registers; col++) { @@ -162,54 +213,68 @@ int co_solve_heuristic_pbqp(copy_opt_t *co) { } } - // add costs matrix to interference edge - add_edge_costs(pbqp_problem, srcNodeIdx, trg_node->index , 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); } } } } + /* create reverse perfect elimination order */ + assure_doms(co->irg); + dom_tree_walk_irg(co->irg, insert_into_reverse_peo, NULL, &pbqp_co); + #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); + set_dumpfile(pbqp_co.pbqp, file_before); + pbqp_dump_input(pbqp_co.pbqp); #endif - // solve pbqp problem - solve_pbqp_heuristical(pbqp_problem); - //solve_pbqp_brute_force(pbqp_problem); - num solution = get_solution(pbqp_problem); - - assert(solution != INF_COSTS && "No PBQP solution found"); + /* 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); - // printf("Solution (%s): %d\n",co->name, (int)solution); + assert(solution != INF_COSTS && "No PBQP solution found"); - // 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); - 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 + /* 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); + 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)); + const arch_register_t *reg = arch_register_for_index(co->cls, index); + arch_set_irn_register(ifg_node, reg); + } - // free pbqp resources + /* free pbqp resources */ #if KAPS_DUMP fclose(file_before); fclose(file_after); #endif - bitset_free(ignore_registers); - pmap_destroy(map); - free_pbqp(pbqp_problem); + bitset_free(pbqp_co.ignore_reg); + pmap_destroy(pbqp_co.map); + plist_free(pbqp_co.rpeo); + free_pbqp(pbqp_co.pbqp); return 0; } + +void be_init_copypbqp(void) +{ + static co_algo_info copyheur = { + co_solve_heuristic_pbqp, 0 + }; + + be_register_copyopt("pbqp", ©heur); +} + +BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copypbqp); + +#endif