X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopyilp2.c;h=acecf27034ee2099e2d3c592fa540620c505b0ad;hb=36e688467f3e9fed2b96e2d7f323edffa4268b53;hp=06cb43e6105fc500498d78c4367e81fdc2f9ec76;hpb=be2960bc9ccda691eba3a031ec3a37d480c07f01;p=libfirm diff --git a/ir/be/becopyilp2.c b/ir/be/becopyilp2.c index 06cb43e61..acecf2703 100644 --- a/ir/be/becopyilp2.c +++ b/ir/be/becopyilp2.c @@ -30,37 +30,36 @@ * - Clique-star constraints * * - * \min \sum_{ (i,j) \in Q } w_ij y_ij + * \min \sum_{ (i,j) \in Q } w_ij y_ij * - * \sum_c x_nc = 1 n \in N, c \in C + * \sum_c x_nc = 1 n \in N, c \in C * - * x_nc = 0 n \in N, c \not\in C(n) + * x_nc = 0 n \in N, c \not\in C(n) * - * \sum x_nc <= 1 x_nc \in Clique \in AllCliques, c \in C + * \sum x_nc <= 1 x_nc \in Clique \in AllCliques, c \in C * - * \sum_{e \in p} y_e >= 1 p \in P path constraints + * \sum_{e \in p} y_e >= 1 p \in P path constraints * - * \sum_{e \in cs} y_e >= |cs| - 1 cs \in CP clique-star constraints + * \sum_{e \in cs} y_e >= |cs| - 1 cs \in CP clique-star constraints * - * x_nc, y_ij \in N, w_ij \in R^+ + * x_nc, y_ij \in N, w_ij \in R^+ */ #include "config.h" -#ifdef WITH_ILP - #include "bitset.h" #include "raw_bitset.h" #include "pdeq.h" -#include "irtools.h" +#include "util.h" #include "irgwalk.h" #include "becopyilp_t.h" -#include "beifg_t.h" -#include "besched_t.h" +#include "beifg.h" +#include "besched.h" +#include "bemodule.h" #define DEBUG_LVL 1 -typedef struct _local_env_t { +typedef struct local_env_t { double time_limit; int first_x_var, last_x_var; int n_colors; @@ -69,18 +68,19 @@ typedef struct _local_env_t { DEBUG_ONLY(firm_dbg_module_t *dbg;) } local_env_t; -static void build_coloring_cstr(ilp_env_t *ienv) { +static void build_coloring_cstr(ilp_env_t *ienv) +{ be_ifg_t *ifg = ienv->co->cenv->ifg; - void *iter = be_ifg_nodes_iter_alloca(ifg); + nodes_iter_t iter; bitset_t *colors; ir_node *irn; char buf[16]; colors = bitset_alloca(arch_register_class_n_regs(ienv->co->cls)); - be_ifg_foreach_node(ifg, iter, irn) + be_ifg_foreach_node(ifg, &iter, irn) if (!sr_is_removed(ienv->sr, irn)) { - bitset_pos_t col; + size_t col; int cst_idx; const arch_register_req_t *req; int curr_node_color = get_irn_col(irn); @@ -89,7 +89,7 @@ static void build_coloring_cstr(ilp_env_t *ienv) { pmap_insert(lenv->nr_2_irn, INT_TO_PTR(node_nr), irn); - req = arch_get_register_req(irn, -1); + req = arch_get_irn_register_req(irn); bitset_clear_all(colors); @@ -104,7 +104,7 @@ static void build_coloring_cstr(ilp_env_t *ienv) { cst_idx = lpp_add_cst(ienv->lp, NULL, lpp_equal, 1.0); bitset_foreach(colors, col) { - int var_idx = lpp_add_var(ienv->lp, name_cdd(buf, 'x', node_nr, col), lpp_binary, 0.0); + int var_idx = lpp_add_var(ienv->lp, name_cdd(buf, 'x', node_nr, (int)col), lpp_binary, 0.0); lpp_set_start_value(ienv->lp, var_idx, (col == (unsigned) curr_node_color) ? 1.0 : 0.0); lpp_set_factor_fast(ienv->lp, cst_idx, var_idx, 1); @@ -116,7 +116,7 @@ static void build_coloring_cstr(ilp_env_t *ienv) { /* add register constraint constraints */ bitset_foreach_clear(colors, col) { int cst_idx = lpp_add_cst(ienv->lp, NULL, lpp_equal, 0.0); - int var_idx = lpp_add_var(ienv->lp, name_cdd(buf, 'x', node_nr, col), lpp_binary, 0.0); + int var_idx = lpp_add_var(ienv->lp, name_cdd(buf, 'x', node_nr, (int)col), lpp_binary, 0.0); lpp_set_start_value(ienv->lp, var_idx, 0.0); lpp_set_factor_fast(ienv->lp, cst_idx, var_idx, 1); @@ -125,21 +125,22 @@ static void build_coloring_cstr(ilp_env_t *ienv) { } } -static void build_interference_cstr(ilp_env_t *ienv) { - lpp_t *lpp = ienv->lp; - local_env_t *lenv = ienv->env; - be_ifg_t *ifg = ienv->co->cenv->ifg; - int n_colors = lenv->n_colors; - int i, col; - - void *iter = be_ifg_cliques_iter_alloca(ifg); - ir_node **clique = alloca(sizeof(*clique) * n_colors); - int size; +static void build_interference_cstr(ilp_env_t *ienv) +{ + lpp_t *lpp = ienv->lp; + local_env_t *lenv = ienv->env; + be_ifg_t *ifg = ienv->co->cenv->ifg; + int n_colors = lenv->n_colors; + cliques_iter_t iter; + ir_node **clique = ALLOCAN(ir_node*, n_colors); + int size; + int col; + int i; char buf[16]; /* for each maximal clique */ - be_ifg_foreach_clique(ifg, iter, clique, &size) { + be_ifg_foreach_clique(ifg, &iter, clique, &size) { int realsize = 0; for (i=0; ienv; int n_colors = lenv->n_colors; unit_t *curr; @@ -199,7 +201,7 @@ static void build_affinity_cstr(ilp_env_t *ienv) { /* add constraints relating the affinity var to the color vars */ for (col=0; collp, NULL, lpp_less, 0.0); + int cst_idx = lpp_add_cst(ienv->lp, NULL, lpp_less_equal, 0.0); root_idx = lpp_get_var_idx(ienv->lp, name_cdd(buf, 'x', root_nr, col)); arg_idx = lpp_get_var_idx(ienv->lp, name_cdd(buf, 'x', arg_nr, col)); @@ -214,11 +216,12 @@ static void build_affinity_cstr(ilp_env_t *ienv) { /** * Helping stuff for build_clique_star_cstr */ -typedef struct _edge_t { +typedef struct edge_t { ir_node *n1, *n2; } edge_t; -static int compare_edge_t(const void *k1, const void *k2, size_t size) { +static int compare_edge_t(const void *k1, const void *k2, size_t size) +{ const edge_t *e1 = k1; const edge_t *e2 = k2; (void) size; @@ -228,7 +231,8 @@ static int compare_edge_t(const void *k1, const void *k2, size_t size) { #define HASH_EDGE(e) (hash_irn((e)->n1) ^ hash_irn((e)->n2)) -static INLINE edge_t *add_edge(set *edges, ir_node *n1, ir_node *n2, int *counter) { +static inline edge_t *add_edge(set *edges, ir_node *n1, ir_node *n2, int *counter) +{ edge_t new_edge; if (PTR_TO_INT(n1) < PTR_TO_INT(n2)) { @@ -242,7 +246,8 @@ static INLINE edge_t *add_edge(set *edges, ir_node *n1, ir_node *n2, int *counte return set_insert(edges, &new_edge, sizeof(new_edge), HASH_EDGE(&new_edge)); } -static INLINE edge_t *find_edge(set *edges, ir_node *n1, ir_node *n2) { +static inline edge_t *find_edge(set *edges, ir_node *n1, ir_node *n2) +{ edge_t new_edge; if (PTR_TO_INT(n1) < PTR_TO_INT(n2)) { @@ -255,7 +260,8 @@ static INLINE edge_t *find_edge(set *edges, ir_node *n1, ir_node *n2) { return set_find(edges, &new_edge, sizeof(new_edge), HASH_EDGE(&new_edge)); } -static INLINE void remove_edge(set *edges, ir_node *n1, ir_node *n2, int *counter) { +static inline void remove_edge(set *edges, ir_node *n1, ir_node *n2, int *counter) +{ edge_t new_edge, *e; if (PTR_TO_INT(n1) < PTR_TO_INT(n2)) { @@ -273,14 +279,15 @@ static INLINE void remove_edge(set *edges, ir_node *n1, ir_node *n2, int *counte } } -#define pset_foreach(pset, irn) for(irn=pset_first(pset); irn; irn=pset_next(pset)) +#define pset_foreach(pset, irn) for (irn=pset_first(pset); irn; irn=pset_next(pset)) /** * Search for an interference clique and an external node * with affinity edges to all nodes of the clique. * At most 1 node of the clique can be colored equally with the external node. */ -static void build_clique_star_cstr(ilp_env_t *ienv) { +static void build_clique_star_cstr(ilp_env_t *ienv) +{ affinity_node_t *aff; /* for each node with affinity edges */ @@ -292,7 +299,7 @@ static void build_clique_star_cstr(ilp_env_t *ienv) { set *edges; int i, o, n_nodes, n_edges; - if (arch_irn_is(aff->irn, ignore)) + if (arch_irn_is_ignore(aff->irn)) continue; obstack_init(&ob); @@ -301,7 +308,7 @@ static void build_clique_star_cstr(ilp_env_t *ienv) { /* get all affinity neighbours */ n_nodes = 0; co_gs_foreach_neighb(aff, nbr) { - if (!arch_irn_is(nbr->irn, ignore)) { + if (!arch_irn_is_ignore(nbr->irn)) { obstack_ptr_grow(&ob, nbr->irn); ++n_nodes; } @@ -322,8 +329,8 @@ static void build_clique_star_cstr(ilp_env_t *ienv) { int growed; /* get 2 starting nodes to form a clique */ - for (e=set_first(edges); !e->n1; e=set_next(edges)) - /*nothing*/ ; + for (e=set_first(edges); !e->n1; e=set_next(edges)) { + } /* we could be stepped out of the loop before the set iterated to the end */ set_break(edges); @@ -375,7 +382,7 @@ static void build_clique_star_cstr(ilp_env_t *ienv) { int var_idx, cst_idx, center_nr, member_nr; char buf[16]; - cst_idx = lpp_add_cst(ienv->lp, NULL, lpp_greater, pset_count(clique)-1); + cst_idx = lpp_add_cst(ienv->lp, NULL, lpp_greater_equal, pset_count(clique)-1); center_nr = get_irn_idx(center); pset_foreach(clique, member) { @@ -394,7 +401,8 @@ static void build_clique_star_cstr(ilp_env_t *ienv) { } -static void extend_path(ilp_env_t *ienv, pdeq *path, const ir_node *irn) { +static void extend_path(ilp_env_t *ienv, pdeq *path, const ir_node *irn) +{ be_ifg_t *ifg = ienv->co->cenv->ifg; int i, len; ir_node **curr_path; @@ -405,7 +413,7 @@ static void extend_path(ilp_env_t *ienv, pdeq *path, const ir_node *irn) { if (pdeq_contains(path, irn)) return; - if (arch_irn_is(irn, ignore)) + if (arch_irn_is_ignore(irn)) return; /* insert the new irn */ @@ -414,8 +422,8 @@ static void extend_path(ilp_env_t *ienv, pdeq *path, const ir_node *irn) { /* check for forbidden interferences */ - len = pdeq_len(path); - curr_path = alloca(len * sizeof(*curr_path)); + len = pdeq_len(path); + curr_path = ALLOCAN(ir_node*, len); pdeq_copyl(path, (const void **)curr_path); for (i=1; i 2) { /* finally build the constraint */ - int cst_idx = lpp_add_cst(ienv->lp, NULL, lpp_greater, 1.0); + int cst_idx = lpp_add_cst(ienv->lp, NULL, lpp_greater_equal, 1.0); for (i=1; ienv; int lower_bound; - ienv->lp = new_lpp(ienv->co->name, lpp_minimize); + ienv->lp = lpp_new(ienv->co->name, lpp_minimize); build_coloring_cstr(ienv); build_interference_cstr(ienv); build_affinity_cstr(ienv); @@ -494,7 +504,8 @@ static void ilp2_build(ilp_env_t *ienv) { lpp_set_time_limit(ienv->lp, lenv->time_limit); } -static void ilp2_apply(ilp_env_t *ienv) { +static void ilp2_apply(ilp_env_t *ienv) +{ local_env_t *lenv = ienv->env; int i; @@ -505,7 +516,7 @@ static void ilp2_apply(ilp_env_t *ienv) { lpp_sol_state_t state = lpp_get_solution(ienv->lp, sol, lenv->first_x_var, lenv->last_x_var); if (state != lpp_optimal) { - printf("WARNING %s: Solution state is not 'optimal': %d\n", ienv->co->name, state); + printf("WARNING %s: Solution state is not 'optimal': %d\n", ienv->co->name, (int)state); assert(state >= lpp_feasible && "The solution should at least be feasible!"); } @@ -538,7 +549,18 @@ static void ilp2_apply(ilp_env_t *ienv) { #endif } -int co_solve_ilp2(copy_opt_t *co) { +BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyilp2) +void be_init_copyilp2(void) +{ + static co_algo_info copyheur = { + co_solve_ilp2, 1 + }; + + be_register_copyopt("ilp", ©heur); +} + +int co_solve_ilp2(copy_opt_t *co) +{ lpp_sol_state_t sol_state; ilp_env_t *ienv; local_env_t my; @@ -554,8 +576,8 @@ int co_solve_ilp2(copy_opt_t *co) { my.normal_colors = bitset_alloca(arch_register_class_n_regs(co->cls)); bitset_clear_all(my.normal_colors); - arch_put_non_ignore_regs(co->cls, my.normal_colors); - my.n_colors = bitset_popcnt(my.normal_colors); + be_put_allocatable_regs(co->irg, co->cls, my.normal_colors); + my.n_colors = bitset_popcount(my.normal_colors); ienv = new_ilp_env(co, ilp2_build, ilp2_apply, &my); @@ -566,10 +588,3 @@ int co_solve_ilp2(copy_opt_t *co) { return sol_state == lpp_optimal; } - -#else /* WITH_ILP */ - -static INLINE void only_that_you_can_compile_without_WITH_ILP_defined(void) { -} - -#endif /* WITH_ILP */