X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopyilp.c;h=20bdbc6ad5cb7382ae25061baf261087bad2f738;hb=f804d333c7b5459c3c1a6bfc188ecdc54346be73;hp=3ff18daf72050342f0c262a74e81ba139598a076;hpb=606235a7824fadb03f38504dd190542164a2977b;p=libfirm diff --git a/ir/be/becopyilp.c b/ir/be/becopyilp.c index 3ff18daf7..20bdbc6ad 100644 --- a/ir/be/becopyilp.c +++ b/ir/be/becopyilp.c @@ -3,6 +3,7 @@ * Date: 17.05.2005 * Copyright: (c) Universitaet Karlsruhe * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + * CVS-ID: $Id$ */ #ifdef HAVE_CONFIG_H #include "config.h" @@ -14,22 +15,20 @@ #include #endif +#define PATH_CONSTRAINTS_FOR_CLASSES +#undef PRECOLOR_MAX_CLIQUE #undef NO_NULL_COLORS #undef NO_NULL_COLORS_EXTRA_CSTS #undef NO_NULL_COLORS_WITH_COSTS - #if (defined(NO_NULL_COLORS_EXTRA_CSTS) || defined(NO_NULL_COLORS_WITH_COSTS)) && !defined(NO_NULL_COLORS) #error Chose your weapon! #endif -#undef PRECOLOR_MAX_CLIQUE -#define PATH_CONSTRAINTS_FOR_CLASSES - #include "irprog.h" #include #include -//#include +#include #include #include "xmalloc.h" #include "pset.h" @@ -54,7 +53,7 @@ static firm_dbg_module_t *dbg = NULL; typedef struct _simpl_t { struct list_head chain; - if_node_t *ifn; + ir_node *irn; } simpl_t; typedef struct _problem_instance_t { @@ -78,7 +77,7 @@ typedef struct _problem_instance_t { #define is_removed(irn) pset_find_ptr(pi->removed, irn) -#define is_color_possible(irn,color) arch_reg_is_allocatable(get_arch_env(pi->co), irn, arch_pos_make_out(0), arch_register_for_index(pi->co->chordal_env->cls, color)) +#define is_color_possible(irn,color) arch_reg_is_allocatable(get_arch_env(pi->co), irn, -1, arch_register_for_index(pi->co->chordal_env->cls, color)) /* * Some stuff for variable name handling. @@ -106,55 +105,70 @@ typedef struct _problem_instance_t { * Checks if a node is simplicial in the graph * heeding the already removed nodes. */ -static INLINE int pi_is_simplicial(problem_instance_t *pi, const if_node_t *ifn) { +static INLINE int pi_is_simplicial(problem_instance_t *pi, const ir_node *ifn) { int i, o, size = 0; - if_node_t **all, *curr; - all = alloca(ifn_get_degree(ifn) * sizeof(*all)); + ir_node **all, *curr; + be_ifg_t *ifg = pi->co->chordal_env->ifg; + void *iter = be_ifg_neighbours_iter_alloca(ifg); + + all = alloca(be_ifg_degree(ifg, ifn) * sizeof(*all)); /* get all non-removed neighbors */ - foreach_neighb(ifn, curr) + be_ifg_foreach_neighbour(ifg, iter, ifn, curr) if (!is_removed(curr)) all[size++] = curr; /* check if these form a clique */ for (i=0; ico->chordal_env, all[i], all[o])) + if (!be_ifg_connected(ifg, all[i], all[o])) return 0; /* all edges exist so this is a clique */ return 1; } +static int irn_cmp(const void *a, const void *b, size_t n) +{ + return a != b; +} + /** * Iterative finds and 'removes' from the graph all nodes which are * simplicial AND not member of a equal-color-wish */ static void pi_find_simplicials(problem_instance_t *pi) { - set *if_nodes; - if_node_t *ifn; + ir_node *irn; int redo = 1; + int n_nodes = 0; + const be_ifg_t *ifg = pi->co->chordal_env->ifg; + void *iter = be_ifg_neighbours_iter_alloca(ifg); DBG((dbg, LEVEL_2, "Find simlicials...\n")); - if_nodes = be_ra_get_ifg_nodes(pi->co->chordal_env); while (redo) { + arch_register_req_t req; redo = 0; - for (ifn = set_first(if_nodes); ifn; ifn = set_next(if_nodes)) { - ir_node *irn = get_irn_for_graph_nr(get_irg(pi->co), ifn->nnr); - if (!is_removed(irn) && !is_optimizable(get_arch_env(pi->co), irn) && !is_optimizable_arg(pi->co, irn)) { - if (pi_is_simplicial(pi, ifn)) { + be_ifg_foreach_node(ifg, iter, irn) { + if (!is_removed(irn) && !is_optimizable(get_arch_env(pi->co), irn, &req) && !is_optimizable_arg(pi->co, irn)) { + if (pi_is_simplicial(pi, irn)) { simpl_t *s = xmalloc(sizeof(*s)); - s->ifn = ifn; + s->irn = irn; list_add(&s->chain, &pi->simplicials); pset_insert_ptr(pi->removed, irn); redo = 1; - DBG((dbg, LEVEL_2, " Removed %n %d\n", irn, get_irn_graph_nr(irn))); + DBG((dbg, LEVEL_2, " Removed %+F\n", irn)); } } } } - if (set_count(be_ra_get_ifg_nodes(pi->co->chordal_env)) == pset_count(pi->removed)) + + /* TODO: Count inside the last look */ + be_ifg_foreach_node(ifg, iter, irn) { + n_nodes++; + } + + if (n_nodes == pset_count(pi->removed)) pi->all_simplicial = 1; } @@ -221,7 +235,7 @@ static void pi_add_constr_A(problem_instance_t *pi) { /* iterate over all possible colors in order */ bitset_clear_all(pos_regs); - arch_get_allocatable_regs(get_arch_env(pi->co), curr->irn, arch_pos_make_out(0), pi->co->chordal_env->cls, pos_regs); + arch_get_allocatable_regs(get_arch_env(pi->co), curr->irn, -1, pos_regs); bitset_foreach(pos_regs, col) { int var_idx; mangle_var2(pi->buf, 'x', nnr, col); @@ -339,14 +353,14 @@ static void pi_add_constr_E(problem_instance_t *pi) { root = curr->nodes[0]; rootnr = get_irn_graph_nr(root); bitset_clear_all(root_regs); - arch_get_allocatable_regs(get_arch_env(pi->co), root, arch_pos_make_out(0), pi->co->chordal_env->cls, root_regs); + arch_get_allocatable_regs(get_arch_env(pi->co), root, -1, root_regs); /* for all arguments of root */ for (i = 1; i < curr->node_count; ++i) { arg = curr->nodes[i]; argnr = get_irn_graph_nr(arg); bitset_clear_all(arg_regs); - arch_get_allocatable_regs(get_arch_env(pi->co), arg, arch_pos_make_out(0), pi->co->chordal_env->cls, arg_regs); + arch_get_allocatable_regs(get_arch_env(pi->co), arg, -1, arg_regs); /* Introduce new variable and set factor in objective function */ mangle_var2(buf, 'y', rootnr, argnr); @@ -591,6 +605,7 @@ static INLINE int get_y_var_idx(problem_instance_t *pi, int nnr1, int nnr2) { return res; assert(0 && "One of them must work"); + return -1; } static void check_ecc_and_add_cut(problem_instance_t *pi, ir_node **path, int length, pset *remain, ir_node *tgt) { @@ -672,7 +687,7 @@ static void path_cstr_for_classes_walker(ir_node *irn, void *env) { problem_instance_t *pi = env; be_chordal_env_t *cenv; int i, o, max; - ir_node *m; + ir_node *m, **cls; pset *class = get_phi_class(irn); if (!class || pset_find_ptr(pi->done, class)) return; @@ -681,7 +696,7 @@ static void path_cstr_for_classes_walker(ir_node *irn, void *env) { /* pset to array */ max = pset_count(class); - ir_node **cls = alloca(max * sizeof(*cls)); + cls = alloca(max * sizeof(*cls)); for(i=0, m = pset_first(class); m; i++, m = pset_next(class)) { DBG((dbg, LEVEL_1, " class member: %+F\n", m)); cls[i] = m; @@ -730,7 +745,7 @@ struct pre_col { #define has_reg_class(pi,irn) \ (arch_get_irn_reg_class(pi->co->chordal_env->session_env->main_env->arch_env, \ - irn, arch_pos_make_out(0)) == pi->co->chordal_env->cls) + irn, -1) == pi->co->chordal_env->cls) static void preColoringWalker(ir_node *bl, void *env) { struct pre_col *e = env; @@ -889,7 +904,11 @@ static void pi_set_start_sol(problem_instance_t *pi) { * Invoke a solver */ static void pi_solve_ilp(problem_instance_t *pi) { + double lower_bound; + pi_set_start_sol(pi); + lower_bound = co_get_lower_bound(pi->co) - co_get_inevit_copy_costs(pi->co); + lpp_set_bound(pi->curr_lp, lower_bound); lpp_solve_net(pi->curr_lp, LPP_HOST, LPP_SOLVER); // lpp_solve_cplex(pi->curr_lp); DBG((dbg, LEVEL_1, "Solution time: %.2f\n", pi->curr_lp->sol_time)); @@ -901,23 +920,23 @@ static void pi_solve_ilp(problem_instance_t *pi) { */ static void pi_set_simplicials(problem_instance_t *pi) { simpl_t *simpl, *tmp; - bitset_t *used_cols = bitset_alloca(arch_register_class_n_regs(pi->co->chordal_env->cls)); + be_ifg_t *ifg = pi->co->chordal_env->ifg; + bitset_t *used_cols = bitset_alloca(arch_register_class_n_regs(pi->co->chordal_env->cls)); + void *iter = be_ifg_neighbours_iter_alloca(ifg); DBG((dbg, LEVEL_2, "Set simplicials...\n")); /* color the simplicial nodes in right order */ list_for_each_entry_safe(simpl_t, simpl, tmp, &pi->simplicials, chain) { int free_col; - ir_node *other_irn, *irn; - if_node_t *other, *ifn; + ir_node *other, *irn; /* get free color by inspecting all neighbors */ - ifn = simpl->ifn; - irn = get_irn_for_graph_nr(get_irg(pi->co), ifn->nnr); + irn = simpl->irn; bitset_clear_all(used_cols); - foreach_neighb(ifn, other) { - other_irn = get_irn_for_graph_nr(get_irg(pi->co), other->nnr); - if (!is_removed(other_irn)) /* only inspect nodes which are in graph right now */ - bitset_set(used_cols, get_irn_col(pi->co, other_irn)); + + be_ifg_foreach_neighbour(ifg, iter, irn, other) { + if (!is_removed(other)) /* only inspect nodes which are in graph right now */ + bitset_set(used_cols, get_irn_col(pi->co, other)); } /* now all bits not set are possible colors */ @@ -932,8 +951,8 @@ static void pi_set_simplicials(problem_instance_t *pi) { * Sets the colors of irns according to the values of variables * provided by the solution of the solver. */ -static void pi_apply_solution(problem_instance_t *pi) { - int i; +static int pi_apply_solution(problem_instance_t *pi) { + int res = 1, i; double *sol; lpp_sol_state_t state; DBG((dbg, LEVEL_2, "Applying solution...\n")); @@ -948,8 +967,9 @@ static void pi_apply_solution(problem_instance_t *pi) { sol = xmalloc((pi->last_x_var - pi->first_x_var + 1) * sizeof(*sol)); state = lpp_get_solution(pi->curr_lp, sol, pi->first_x_var, pi->last_x_var); if (state != lpp_optimal) { - printf("Solution state is not 'optimal': %d\n", state); + printf("WARNING %s: Solution state is not 'optimal': %d\n", pi->co->name, state); assert(state >= lpp_feasible && "The solution should at least be feasible!"); + res = 0; } for (i=0; ilast_x_var - pi->first_x_var + 1; ++i) { int nnr, col; @@ -965,16 +985,14 @@ static void pi_apply_solution(problem_instance_t *pi) { assert(0 && "This should be a x-var"); } } + return res; } -void co_ilp_opt(copy_opt_t *co) { +int co_ilp_opt(copy_opt_t *co, double time_limit) { + int res = 1; problem_instance_t *pi; dbg = firm_dbg_register("ir.be.copyoptilp"); - if (!strcmp(co->name, DEBUG_IRG)) - firm_dbg_set_mask(dbg, DEBUG_IRG_LVL_ILP); - else - firm_dbg_set_mask(dbg, DEBUG_LVL_ILP); pi = new_pi(co); if (!pi->all_simplicial) { @@ -983,9 +1001,11 @@ void co_ilp_opt(copy_opt_t *co) { snprintf(buf, sizeof(buf), "%s.mps", co->name); lpp_dump(pi->curr_lp, buf); #endif + lpp_set_time_limit(pi->curr_lp, time_limit); pi_solve_ilp(pi); - pi_apply_solution(pi); + res = pi_apply_solution(pi); pi_set_simplicials(pi); } free_pi(pi); + return res; }