X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbepbqpcoloring.c;h=f9de569e8a10d3c23189449d05acff5265266151;hb=df2faee01a5832057bb3ca0ba5f67e979c916e19;hp=ac5dec844685f2f7871521fe21b8966edbab488d;hpb=3a47171668b40b487a2a3d3c4e5fa3e3e76301c6;p=libfirm diff --git a/ir/be/bepbqpcoloring.c b/ir/be/bepbqpcoloring.c index ac5dec844..f9de569e8 100644 --- a/ir/be/bepbqpcoloring.c +++ b/ir/be/bepbqpcoloring.c @@ -22,14 +22,11 @@ * @brief PBQP based register allocation. * @author Thomas Bersch * @date 27.11.2009 - * @version $Id: bechordal.c 26750 2009-11-27 09:37:43Z bersch $ */ -/* miscellaneous includes */ +/* miscellaneous includes */ #include "config.h" -#ifdef FIRM_KAPS - #include "debug.h" #include "error.h" @@ -38,9 +35,9 @@ #include "iredges_t.h" #include "irprintf.h" #include "irgwalk.h" +#include "irtools.h" #include "time.h" - -/* libfirm/ir/adt includes */ +#include "execfreq_t.h" #include "bipartite.h" /* libfirm/ir/be includes */ @@ -82,17 +79,18 @@ static int use_exec_freq = true; static int use_late_decision = false; -typedef struct _be_pbqp_alloc_env_t { - pbqp *pbqp_inst; /**< PBQP instance for register allocation */ - ir_graph *irg; /**< The graph under examination. */ - const arch_register_class_t *cls; /**< Current processed register class */ +typedef struct be_pbqp_alloc_env_t { + pbqp_t *pbqp_inst; /**< PBQP instance for register allocation */ + ir_graph *irg; /**< The graph under examination. */ + const arch_register_class_t *cls; /**< Current processed register class */ be_lv_t *lv; - bitset_t *ignored_regs; - pbqp_matrix *ife_matrix_template; - pbqp_matrix *aff_matrix_template; + bitset_t *allocatable_regs; + pbqp_matrix_t *ife_matrix_template; + pbqp_matrix_t *aff_matrix_template; plist_t *rpeo; unsigned *restr_nodes; unsigned *ife_edge_num; + ir_execfreq_int_factors execfreq_factors; be_chordal_env_t *env; } be_pbqp_alloc_env_t; @@ -103,11 +101,6 @@ typedef struct _be_pbqp_alloc_env_t { #define insert_edge(pbqp, src_node, trg_node, template_matrix) (add_edge_costs(pbqp, get_irn_idx(src_node), get_irn_idx(trg_node), pbqp_matrix_copy(pbqp, template_matrix))) #define get_free_regs(restr_nodes, cls, irn) (arch_register_class_n_regs(cls) - restr_nodes[get_irn_idx(irn)]) -static inline int is_2addr_code(const arch_register_req_t *req) -{ - return (req->type & arch_register_req_type_should_be_same) != 0; -} - static const lc_opt_table_entry_t options[] = { LC_OPT_ENT_BOOL("exec_freq", "use exec_freq", &use_exec_freq), LC_OPT_ENT_BOOL("late_decision", "use late decision for register allocation", &use_late_decision), @@ -146,18 +139,21 @@ static FILE *my_open(const be_chordal_env_t *env, const char *prefix, const char static void create_pbqp_node(be_pbqp_alloc_env_t *pbqp_alloc_env, ir_node *irn) { const arch_register_class_t *cls = pbqp_alloc_env->cls; - pbqp *pbqp_inst = pbqp_alloc_env->pbqp_inst; - bitset_t *ignored_regs = pbqp_alloc_env->ignored_regs; + pbqp_t *pbqp_inst = pbqp_alloc_env->pbqp_inst; + bitset_t *allocatable_regs = pbqp_alloc_env->allocatable_regs; unsigned colors_n = arch_register_class_n_regs(cls); unsigned cntConstrains = 0; /* create costs vector depending on register constrains */ - struct vector *costs_vector = vector_alloc(pbqp_inst, colors_n); + vector_t *costs_vector = vector_alloc(pbqp_inst, colors_n); /* set costs depending on register constrains */ unsigned idx; for (idx = 0; idx < colors_n; idx++) { - if (bitset_is_set(ignored_regs, idx) || !arch_reg_out_is_allocatable(irn, arch_register_for_index(cls, idx))) { + const arch_register_req_t *req = arch_get_irn_register_req(irn); + const arch_register_t *reg = arch_register_for_index(cls, idx); + if (!bitset_is_set(allocatable_regs, idx) + || !arch_reg_is_allocatable(req, reg)) { /* constrained */ vector_set(costs_vector, idx, INF_COSTS); cntConstrains++; @@ -171,9 +167,9 @@ static void create_pbqp_node(be_pbqp_alloc_env_t *pbqp_alloc_env, ir_node *irn) static void insert_ife_edge(be_pbqp_alloc_env_t *pbqp_alloc_env, ir_node *src_node, ir_node *trg_node) { - pbqp *pbqp = pbqp_alloc_env->pbqp_inst; + pbqp_t *pbqp = pbqp_alloc_env->pbqp_inst; const arch_register_class_t *cls = pbqp_alloc_env->cls; - pbqp_matrix *ife_matrix_template = pbqp_alloc_env->ife_matrix_template; + pbqp_matrix_t *ife_matrix_template = pbqp_alloc_env->ife_matrix_template; unsigned *restr_nodes = pbqp_alloc_env->restr_nodes; if (get_edge(pbqp, get_irn_idx(src_node), get_irn_idx(trg_node)) == NULL) { @@ -209,19 +205,18 @@ static void insert_ife_edge(be_pbqp_alloc_env_t *pbqp_alloc_env, ir_node *src_no static void insert_afe_edge(be_pbqp_alloc_env_t *pbqp_alloc_env, ir_node *src_node, ir_node *trg_node, int pos) { - pbqp *pbqp = pbqp_alloc_env->pbqp_inst; + pbqp_t *pbqp = pbqp_alloc_env->pbqp_inst; const arch_register_class_t *cls = pbqp_alloc_env->cls; unsigned *restr_nodes = pbqp_alloc_env->restr_nodes; - pbqp_matrix *afe_matrix = pbqp_matrix_alloc(pbqp, arch_register_class_n_regs(cls), arch_register_class_n_regs(cls)); + pbqp_matrix_t *afe_matrix = pbqp_matrix_alloc(pbqp, arch_register_class_n_regs(cls), arch_register_class_n_regs(cls)); unsigned colors_n = arch_register_class_n_regs(cls); if (get_edge(pbqp, get_irn_idx(src_node), get_irn_idx(trg_node)) == NULL) { if (use_exec_freq) { /* get exec_freq for copy_block */ - ir_node *root_bl = get_nodes_block(src_node); - ir_node *copy_bl = is_Phi(src_node) ? get_Block_cfgpred_block(root_bl, pos) : root_bl; - ir_exec_freq *exec_freq = be_get_irg_exec_freq(pbqp_alloc_env->irg); - unsigned long res = get_block_execfreq_ulong(exec_freq, copy_bl); + ir_node *root_bl = get_nodes_block(src_node); + ir_node *copy_bl = is_Phi(src_node) ? get_Block_cfgpred_block(root_bl, pos) : root_bl; + int res = get_block_execfreq_int(&pbqp_alloc_env->execfreq_factors, copy_bl); /* create afe-matrix */ unsigned row, col; @@ -259,9 +254,9 @@ static void insert_afe_edge(be_pbqp_alloc_env_t *pbqp_alloc_env, ir_node *src_no static void create_affinity_edges(ir_node *irn, void *env) { - be_pbqp_alloc_env_t *pbqp_alloc_env = env; + be_pbqp_alloc_env_t *pbqp_alloc_env = (be_pbqp_alloc_env_t*)env; const arch_register_class_t *cls = pbqp_alloc_env->cls; - const arch_register_req_t *req = arch_get_register_req_out(irn); + const arch_register_req_t *req = arch_get_irn_register_req(irn); unsigned pos; unsigned max; @@ -286,25 +281,22 @@ static void create_affinity_edges(ir_node *irn, void *env) return; insert_afe_edge(pbqp_alloc_env, irn, arg, -1); - } - else { /* 2-address code */ - if (is_2addr_code(req)) { - const unsigned other = req->other_same; - int i; - - for (i = 0; 1U << i <= other; ++i) { - if (other & (1U << i)) { - ir_node *other = get_irn_n(skip_Proj(irn), i); - if (!arch_irn_consider_in_reg_alloc(cls, other)) - continue; - - /* no edges to itself */ - if (irn == other) { - continue; - } + } else if (arch_register_req_is(req, should_be_same)) { + const unsigned other = req->other_same; + int i; + + for (i = 0; 1U << i <= other; ++i) { + if (other & (1U << i)) { + ir_node *other = get_irn_n(skip_Proj(irn), i); + if (!arch_irn_consider_in_reg_alloc(cls, other)) + continue; - insert_afe_edge(pbqp_alloc_env, irn, other, i); + /* no edges to itself */ + if (irn == other) { + continue; } + + insert_afe_edge(pbqp_alloc_env, irn, other, i); } } } @@ -312,22 +304,21 @@ static void create_affinity_edges(ir_node *irn, void *env) static void create_pbqp_coloring_instance(ir_node *block, void *data) { - be_pbqp_alloc_env_t *pbqp_alloc_env = data; - be_lv_t *lv = pbqp_alloc_env->lv; - const arch_register_class_t *cls = pbqp_alloc_env->cls; + be_pbqp_alloc_env_t *pbqp_alloc_env = (be_pbqp_alloc_env_t*)data; + be_lv_t *lv = pbqp_alloc_env->lv; + const arch_register_class_t *cls = pbqp_alloc_env->cls; plist_t *rpeo = pbqp_alloc_env->rpeo; - pbqp *pbqp_inst = pbqp_alloc_env->pbqp_inst; + pbqp_t *pbqp_inst = pbqp_alloc_env->pbqp_inst; plist_t *temp_list = plist_new(); plist_element_t *el; - ir_node *irn; ir_nodeset_t live_nodes; #if USE_BIPARTIT_MATCHING int *assignment = ALLOCAN(int, cls->n_regs); #else unsigned *restr_nodes = pbqp_alloc_env->restr_nodes; - pqueue_t *restr_nodes_queue = new_pqueue(); - pqueue_t *queue = new_pqueue(); - plist_t *sorted_list = plist_new(); + pqueue_t *restr_nodes_queue = new_pqueue(); + pqueue_t *queue = new_pqueue(); + plist_t *sorted_list = plist_new(); ir_node *last_element = NULL; #endif @@ -341,61 +332,27 @@ static void create_pbqp_coloring_instance(ir_node *block, void *data) /* create pbqp nodes, interference edges and reverse perfect elimination order */ sched_foreach_reverse(block, irn) { - ir_node *live; - ir_nodeset_iterator_t iter; + be_foreach_value(irn, value, + if (!arch_irn_consider_in_reg_alloc(cls, value)) + continue; - if (get_irn_mode(irn) == mode_T) { - const ir_edge_t *edge; - foreach_out_edge(irn, edge) { - ir_node *proj = get_edge_src_irn(edge); - if (!arch_irn_consider_in_reg_alloc(cls, proj)) - continue; + /* create pbqp source node if it dosn't exist */ + if (!get_node(pbqp_inst, get_irn_idx(value))) + create_pbqp_node(pbqp_alloc_env, value); + /* create nodes and interference edges */ + foreach_ir_nodeset(&live_nodes, live, iter) { /* create pbqp source node if it dosn't exist */ - if (get_node(pbqp_inst, get_irn_idx(proj)) == NULL) { - create_pbqp_node(pbqp_alloc_env, proj); - } + if (!get_node(pbqp_inst, get_irn_idx(live))) + create_pbqp_node(pbqp_alloc_env, live); - /* create nodes and interference edges */ - foreach_ir_nodeset(&live_nodes, live, iter) { - /* create pbqp source node if it dosn't exist */ - if (get_node(pbqp_inst, get_irn_idx(live)) == NULL) { - create_pbqp_node(pbqp_alloc_env, live); - } - - /* no edges to itself */ - if (proj == live) { - continue; - } - - insert_ife_edge(pbqp_alloc_env, proj, live); - } - } - } - else { - if (arch_irn_consider_in_reg_alloc(cls, irn)) { - /* create pbqp source node if it dosn't exist */ - if (get_node(pbqp_inst, get_irn_idx(irn)) == NULL) { - create_pbqp_node(pbqp_alloc_env, irn); - } - - /* create nodes and interference edges */ - foreach_ir_nodeset(&live_nodes, live, iter) { - /* create pbqp source node if it dosn't exist */ - if (get_node(pbqp_inst, get_irn_idx(live)) == NULL) { - create_pbqp_node(pbqp_alloc_env, live); - } - - /* no edges to itself */ - if (irn == live) { - continue; - } + /* no edges to itself */ + if (value == live) + continue; - /* insert interference edge */ - insert_ife_edge(pbqp_alloc_env, irn, live); - } + insert_ife_edge(pbqp_alloc_env, value, live); } - } + ); /* get living nodes for next step */ if (!is_Phi(irn)) { @@ -410,7 +367,6 @@ static void create_pbqp_coloring_instance(ir_node *block, void *data) bipartite_t *bp = bipartite_new(cls->n_regs, cls->n_regs); /* add all proj after a perm to clique */ - const ir_edge_t *edge; foreach_out_edge(irn, edge) { ir_node *proj = get_edge_src_irn(edge); @@ -510,9 +466,7 @@ static void create_pbqp_coloring_instance(ir_node *block, void *data) #else /* order nodes for perfect elimination order */ if (get_irn_mode(irn) == mode_T) { - bool allHaveIFEdges = true; - const ir_edge_t *edge; - + bool allHaveIFEdges = true; foreach_out_edge(irn, edge) { ir_node *proj = get_edge_src_irn(edge); if (!arch_irn_consider_in_reg_alloc(cls, proj)) @@ -549,12 +503,14 @@ static void create_pbqp_coloring_instance(ir_node *block, void *data) /* first insert all restricted proj nodes */ while (!pqueue_empty(restr_nodes_queue)) { - plist_insert_front(sorted_list, get_node(pbqp_inst, get_irn_idx(pqueue_pop_front(restr_nodes_queue)))); + ir_node *node = (ir_node*)pqueue_pop_front(restr_nodes_queue); + plist_insert_front(sorted_list, get_node(pbqp_inst, get_irn_idx(node))); } /* insert proj nodes descending by their number of interference edges */ while (!pqueue_empty(queue)) { - plist_insert_front(sorted_list, get_node(pbqp_inst, get_irn_idx(pqueue_pop_front(queue)))); + ir_node *node = (ir_node*)pqueue_pop_front(queue); + plist_insert_front(sorted_list, get_node(pbqp_inst, get_irn_idx(node))); } /* invert sorted list */ @@ -597,34 +553,16 @@ static void create_pbqp_coloring_instance(ir_node *block, void *data) static void insert_perms(ir_node *block, void *data) { - /* - * Start silent in the start block. - * The silence remains until the first barrier is seen. - * Each other block is begun loud. - */ - be_chordal_env_t *env = data; + be_chordal_env_t *env = (be_chordal_env_t*)data; ir_node *irn; - int silent = block == get_irg_start_block(get_irn_irg(block)); - /* - * If the block is the start block search the barrier and - * start handling constraints from there. - */ for (irn = sched_first(block); !sched_is_end(irn);) { - int silent_old = silent; /* store old silent value */ - if (be_is_Barrier(irn)) - silent = !silent; /* toggle silent flag */ - - be_insn_t *insn = chordal_scan_insn(env, irn); - irn = insn->next_insn; + ir_node *const next = sched_next(irn); + be_insn_t * insn = be_scan_insn(env, irn); + if (insn) + pre_process_constraints(env, &insn); - if (silent_old) - continue; - - if (!insn->has_constraints) - continue; - - pre_process_constraints(env, &insn); + irn = next; } } @@ -638,7 +576,11 @@ static void be_pbqp_coloring(be_chordal_env_t *env) be_pbqp_alloc_env_t pbqp_alloc_env; unsigned col; unsigned row; - + pbqp_matrix_t *ife_matrix; + num solution; +#if KAPS_DUMP + FILE *file_before; +#endif #if TIMER ir_timer_t *t_ra_pbqp_alloc_create = ir_timer_new(); ir_timer_t *t_ra_pbqp_alloc_solve = ir_timer_new(); @@ -646,9 +588,8 @@ static void be_pbqp_coloring(be_chordal_env_t *env) printf("#### ----- === Allocating registers of %s (%s) ===\n", cls->name, get_entity_name(get_irg_entity(irg))); #endif - lv = be_assure_liveness(irg); - be_liveness_assure_sets(lv); - be_liveness_assure_chk(lv); + be_assure_live_sets(irg); + lv = be_get_irg_liveness(irg); /* insert perms */ assure_doms(irg); @@ -661,22 +602,23 @@ static void be_pbqp_coloring(be_chordal_env_t *env) dump_ir_graph(irg, buf); } + ir_calculate_execfreq_int_factors(&pbqp_alloc_env.execfreq_factors, irg); /* initialize pbqp allocation data structure */ - pbqp_alloc_env.pbqp_inst = alloc_pbqp(get_irg_last_idx(irg)); /* initialize pbqp instance */ - pbqp_alloc_env.cls = cls; - pbqp_alloc_env.irg = irg; - pbqp_alloc_env.lv = lv; - pbqp_alloc_env.ignored_regs = bitset_malloc(colors_n); - pbqp_alloc_env.rpeo = plist_new(); - pbqp_alloc_env.restr_nodes = XMALLOCNZ(unsigned, get_irg_last_idx(irg)); - pbqp_alloc_env.ife_edge_num = XMALLOCNZ(unsigned, get_irg_last_idx(irg)); - pbqp_alloc_env.env = env; - be_put_ignore_regs(irg, cls, pbqp_alloc_env.ignored_regs); /* get ignored registers */ + pbqp_alloc_env.pbqp_inst = alloc_pbqp(get_irg_last_idx(irg)); /* initialize pbqp instance */ + pbqp_alloc_env.cls = cls; + pbqp_alloc_env.irg = irg; + pbqp_alloc_env.lv = lv; + pbqp_alloc_env.allocatable_regs = bitset_malloc(colors_n); + pbqp_alloc_env.rpeo = plist_new(); + pbqp_alloc_env.restr_nodes = XMALLOCNZ(unsigned, get_irg_last_idx(irg)); + pbqp_alloc_env.ife_edge_num = XMALLOCNZ(unsigned, get_irg_last_idx(irg)); + pbqp_alloc_env.env = env; + be_put_allocatable_regs(irg, cls, pbqp_alloc_env.allocatable_regs); /* create costs matrix template for interference edges */ - struct pbqp_matrix *ife_matrix = pbqp_matrix_alloc(pbqp_alloc_env.pbqp_inst, colors_n, colors_n); + ife_matrix = pbqp_matrix_alloc(pbqp_alloc_env.pbqp_inst, colors_n, colors_n); /* set costs */ for (row = 0, col = 0; row < colors_n; row++, col++) pbqp_matrix_set(ife_matrix, row, col, INF_COSTS); @@ -686,7 +628,7 @@ static void be_pbqp_coloring(be_chordal_env_t *env) if (!use_exec_freq) { /* create costs matrix template for affinity edges */ - struct pbqp_matrix *afe_matrix = pbqp_matrix_alloc(pbqp_alloc_env.pbqp_inst, colors_n, colors_n); + pbqp_matrix_t *afe_matrix = pbqp_matrix_alloc(pbqp_alloc_env.pbqp_inst, colors_n, colors_n); /* set costs */ for (row = 0; row < colors_n; row++) { for (col = 0; col < colors_n; col++) { @@ -714,8 +656,8 @@ static void be_pbqp_coloring(be_chordal_env_t *env) ir_timer_reset_and_start(t_ra_pbqp_alloc_create_aff); #endif foreach_plist(pbqp_alloc_env.rpeo, element) { - pbqp_node *node = element->data; - ir_node *irn = get_idx_irn(irg, node->index); + pbqp_node_t *node = (pbqp_node_t*)element->data; + ir_node *irn = get_idx_irn(irg, node->index); create_affinity_edges(irn, &pbqp_alloc_env); } @@ -726,18 +668,20 @@ static void be_pbqp_coloring(be_chordal_env_t *env) #if KAPS_DUMP // dump graph before solving pbqp - FILE *file_before = my_open(env, "", "-pbqp_coloring.html"); + file_before = my_open(env, "", "-pbqp_coloring.html"); set_dumpfile(pbqp_alloc_env.pbqp_inst, file_before); #endif - /* print out reverse perfect eleminiation order */ + /* print out reverse perfect elimination order */ #if PRINT_RPEO - plist_element_t *elements; - foreach_plist(pbqp_alloc_env.rpeo, elements) { - pbqp_node *node = elements->data; - printf(" %d(%lu);", node->index, get_idx_irn(irg, node->index)->node_nr); + { + plist_element_t *elements; + foreach_plist(pbqp_alloc_env.rpeo, elements) { + pbqp_node_t *node = elements->data; + printf(" %d(%ld);", node->index, get_idx_irn(irg, node->index)->node_nr); + } + printf("\n"); } - printf("\n"); #endif /* solve pbqp instance */ @@ -755,14 +699,14 @@ static void be_pbqp_coloring(be_chordal_env_t *env) #endif - num solution = get_solution(pbqp_alloc_env.pbqp_inst); + solution = get_solution(pbqp_alloc_env.pbqp_inst); if (solution == INF_COSTS) panic("No PBQP solution found"); /* assign colors */ foreach_plist(pbqp_alloc_env.rpeo, element) { - pbqp_node *node = element->data; + pbqp_node_t *node = (pbqp_node_t*)element->data; ir_node *irn = get_idx_irn(irg, node->index); num color = get_node_solution(pbqp_alloc_env.pbqp_inst, node->index); const arch_register_t *reg = arch_register_for_index(cls, color); @@ -785,7 +729,7 @@ static void be_pbqp_coloring(be_chordal_env_t *env) #if KAPS_DUMP fclose(file_before); #endif - bitset_free(pbqp_alloc_env.ignored_regs); + bitset_free(pbqp_alloc_env.allocatable_regs); free_pbqp(pbqp_alloc_env.pbqp_inst); plist_free(pbqp_alloc_env.rpeo); xfree(pbqp_alloc_env.restr_nodes); @@ -796,7 +740,7 @@ static void be_pbqp_coloring(be_chordal_env_t *env) /** * Initializes this module. */ -BE_REGISTER_MODULE_CONSTRUCTOR(be_init_pbqp_coloring); +BE_REGISTER_MODULE_CONSTRUCTOR(be_init_pbqp_coloring) void be_init_pbqp_coloring(void) { lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be"); @@ -812,5 +756,3 @@ void be_init_pbqp_coloring(void) lc_opt_add_table(pbqp_grp, options); be_register_chordal_coloring("pbqp", &coloring); } - -#endif