X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopyilp2.c;h=36dad10952f69deb93bc2dacd12ed038dba7a0cb;hb=b151d11c50d89b9dffadfb63f7ccfd81ea8db44f;hp=b323464e583a203689bea22c8bfcdd1957c02b20;hpb=94b02881010e09aabe313564771b2e99273c4196;p=libfirm diff --git a/ir/be/becopyilp2.c b/ir/be/becopyilp2.c index b323464e5..36dad1095 100644 --- a/ir/be/becopyilp2.c +++ b/ir/be/becopyilp2.c @@ -1,9 +1,28 @@ -/** - * Author: Daniel Grund - * Date: 28.02.2006 - * Copyright: (c) Universitaet Karlsruhe - * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. +/* + * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. + * + * This file is part of libFirm. + * + * This file may be distributed and/or modified under the terms of the + * GNU General Public License version 2 as published by the Free Software + * Foundation and appearing in the file LICENSE.GPL included in the + * packaging of this file. * + * Licensees holding valid libFirm Professional Edition licenses may use + * this file in accordance with the libFirm Commercial License. + * Agreement provided with the Software. + * + * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE + * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE. + */ + +/** + * @file + * @brief ILP based copy minimization. + * @author Daniel Grund + * @date 28.02.2006 + * @version $Id$ * * ILP formalization using G=(V, E, Q): * - 2 class of variables: coloring vars x_ic and equal color vars y_ij @@ -11,75 +30,84 @@ * - 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^+ */ - -#ifdef HAVE_CONFIG_H #include "config.h" -#endif /* HAVE_CONFIG_H */ #ifdef WITH_ILP +#include "bitset.h" +#include "raw_bitset.h" +#include "pdeq.h" + #include "irtools.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 { - firm_dbg_module_t *dbg; +typedef struct local_env_t { double time_limit; int first_x_var, last_x_var; + int n_colors; + bitset_t *normal_colors; pmap *nr_2_irn; + DEBUG_ONLY(firm_dbg_module_t *dbg;) } local_env_t; -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); +static void build_coloring_cstr(ilp_env_t *ienv) +{ + be_ifg_t *ifg = ienv->co->cenv->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)) { - int col, cst_idx; - arch_register_req_t req; - int curr_node_color = get_irn_col(ienv->co, irn); - int node_nr = (int)get_irn_node_nr(irn); + size_t col; + int cst_idx; + const arch_register_req_t *req; + int curr_node_color = get_irn_col(irn); + int node_nr = (int)get_irn_idx(irn); local_env_t *lenv = ienv->env; pmap_insert(lenv->nr_2_irn, INT_TO_PTR(node_nr), irn); - arch_get_register_req(ienv->co->aenv, &req, irn, -1); + req = arch_get_register_req_out(irn); + + bitset_clear_all(colors); /* get assignable colors */ - if (arch_register_req_is(&req, limited)) - req.limited(req.limited_env, colors); - else - arch_put_non_ignore_regs(ienv->co->aenv, req.cls, colors); + if (arch_register_req_is(req, limited)) { + rbitset_copy_to_bitset(req->limited, colors); + } else { + bitset_copy(colors, lenv->normal_colors); + } /* add the coloring constraint */ 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); - lpp_set_start_value(ienv->lp, var_idx, (col == curr_node_color) ? 1.0 : 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); lenv->last_x_var = var_idx; @@ -99,22 +127,29 @@ static void build_coloring_cstr(ilp_env_t *ienv) { } } -static void build_interference_cstr(ilp_env_t *ienv) { - lpp_t *lpp = ienv->lp; - be_ifg_t *ifg = ienv->co->cenv->ifg; - int n_colors = arch_register_class_n_regs(ienv->co->cls); - 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; isr, clique[i])) + ++realsize; - if (size < 2) + if (realsize < 2) continue; /* for all colors */ @@ -126,7 +161,7 @@ static void build_interference_cstr(ilp_env_t *ienv) { ir_node *irn = clique[i]; if (!sr_is_removed(ienv->sr, irn)) { - int var_idx = lpp_get_var_idx(lpp, name_cdd(buf, 'x', (int)get_irn_node_nr(irn), col)); + int var_idx = lpp_get_var_idx(lpp, name_cdd(buf, 'x', (int)get_irn_idx(irn), col)); lpp_set_factor_fast(lpp, cst_idx, var_idx, 1); } } @@ -134,9 +169,17 @@ static void build_interference_cstr(ilp_env_t *ienv) { } } -static void build_affinity_cstr(ilp_env_t *ienv) { + +/** + * TODO: Remove the dependency of the opt-units data structure + * by walking over all affinity edges. Graph structure + * does not provide this walker, yet. + */ +static void build_affinity_cstr(ilp_env_t *ienv) +{ + local_env_t *lenv = ienv->env; + int n_colors = lenv->n_colors; unit_t *curr; - int n_colors = arch_register_class_n_regs(ienv->co->cls); /* for all optimization units */ list_for_each_entry(unit_t, curr, &ienv->co->units, units) { @@ -146,13 +189,13 @@ static void build_affinity_cstr(ilp_env_t *ienv) { int root_col, arg_col; root = curr->nodes[0]; - root_nr = (int) get_irn_node_nr(root); - root_col = get_irn_col(ienv->co, root); + root_nr = (int) get_irn_idx(root); + root_col = get_irn_col(root); for (i = 1; i < curr->node_count; ++i) { arg = curr->nodes[i]; - arg_nr = (int) get_irn_node_nr(arg); - arg_col = get_irn_col(ienv->co, arg); + arg_nr = (int) get_irn_idx(arg); + arg_col = get_irn_col(arg); /* add a new affinity variable */ y_idx = lpp_add_var(ienv->lp, name_cdd_sorted(buf, 'y', root_nr, arg_nr), lpp_binary, curr->costs[i]); @@ -166,7 +209,7 @@ static void build_affinity_cstr(ilp_env_t *ienv) { lpp_set_factor_fast(ienv->lp, cst_idx, root_idx, 1.0); lpp_set_factor_fast(ienv->lp, cst_idx, arg_idx, -1.0); - lpp_set_factor_fast(ienv->lp, cst_idx, root_idx, -1.0); + lpp_set_factor_fast(ienv->lp, cst_idx, y_idx, -1.0); } } } @@ -175,20 +218,23 @@ 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; return ! (e1->n1 == e2->n1 && e1->n2 == e2->n2); } -#define HASH_EDGE(e) (HASH_PTR((e)->n1) ^ HASH_PTR((e)->n2)) +#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)) { @@ -198,11 +244,12 @@ static INLINE edge_t *add_edge(set *edges, ir_node *n1, ir_node *n2, int *counte new_edge.n1 = n2; new_edge.n2 = n1; } - *counter++; + (*counter)++; 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)) { @@ -215,7 +262,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)) { @@ -229,37 +277,43 @@ static INLINE void remove_edge(set *edges, ir_node *n1, ir_node *n2, int *counte if (e) { e->n1 = NULL; e->n2 = NULL; - *counter--; + (*counter)--; } } -#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) { - node_t *node; +static void build_clique_star_cstr(ilp_env_t *ienv) +{ + affinity_node_t *aff; /* for each node with affinity edges */ - co_gs_foreach_node(ienv->co, node) { + co_gs_foreach_aff_node(ienv->co, aff) { struct obstack ob; neighb_t *nbr; - ir_node *center = node->irn; + const ir_node *center = aff->irn; ir_node **nodes; set *edges; int i, o, n_nodes, n_edges; + if (arch_irn_is_ignore(aff->irn)) + continue; + obstack_init(&ob); edges = new_set(compare_edge_t, 8); /* get all affinity neighbours */ n_nodes = 0; - co_gs_foreach_neighb(node, nbr) { - obstack_ptr_grow(&ob, nbr->irn); - ++n_nodes; + co_gs_foreach_neighb(aff, nbr) { + if (!arch_irn_is_ignore(nbr->irn)) { + obstack_ptr_grow(&ob, nbr->irn); + ++n_nodes; + } } nodes = obstack_finish(&ob); @@ -280,9 +334,12 @@ static void build_clique_star_cstr(ilp_env_t *ienv) { for (e=set_first(edges); !e->n1; e=set_next(edges)) /*nothing*/ ; - remove_edge(edges, e->n1, e->n2, &n_edges); + /* we could be stepped out of the loop before the set iterated to the end */ + set_break(edges); + pset_insert_ptr(clique, e->n1); pset_insert_ptr(clique, e->n2); + remove_edge(edges, e->n1, e->n2, &n_edges); /* while the clique is growing */ do { @@ -328,10 +385,10 @@ static void build_clique_star_cstr(ilp_env_t *ienv) { char buf[16]; cst_idx = lpp_add_cst(ienv->lp, NULL, lpp_greater, pset_count(clique)-1); - center_nr = get_irn_node_nr(center); + center_nr = get_irn_idx(center); pset_foreach(clique, member) { - member_nr = get_irn_node_nr(member); + member_nr = get_irn_idx(member); var_idx = lpp_get_var_idx(ienv->lp, name_cdd_sorted(buf, 'y', center_nr, member_nr)); lpp_set_factor_fast(ienv->lp, cst_idx, var_idx, 1.0); } @@ -345,14 +402,95 @@ static void build_clique_star_cstr(ilp_env_t *ienv) { } } + +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; + affinity_node_t *aff; + neighb_t *nbr; + + /* do not walk backwards or in circles */ + if (pdeq_contains(path, irn)) + return; + + if (arch_irn_is_ignore(irn)) + return; + + /* insert the new irn */ + pdeq_putr(path, irn); + + + + /* check for forbidden interferences */ + 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); + for (i=1; ilp, name_cdd_sorted(buf, 'y', nr_1, nr_2)); + lpp_set_factor_fast(ienv->lp, cst_idx, var_idx, 1.0); + } + } + + /* this path cannot be extended anymore */ + goto end; + } + + + + /* recursively extend the path */ + aff = get_affinity_info(ienv->co, irn); + co_gs_foreach_neighb(aff, nbr) + extend_path(ienv, path, nbr->irn); + + +end: + /* remove the irn */ + pdeq_getr(path); + +} + /** - * + * Search a path of affinity edges, whose ends are connected + * by an interference edge and there are no other interference + * edges in between. + * Then at least one of these affinity edges must break. */ -static void build_path_cstr(ilp_env_t *ienv) { +static void build_path_cstr(ilp_env_t *ienv) +{ + affinity_node_t *aff_info; + + /* for each node with affinity edges */ + co_gs_foreach_aff_node(ienv->co, aff_info) { + pdeq *path = new_pdeq(); + + extend_path(ienv, path, aff_info->irn); + del_pdeq(path); + } } -static void ilp2_build(ilp_env_t *ienv) { +static void ilp2_build(ilp_env_t *ienv) +{ local_env_t *lenv = ienv->env; int lower_bound; @@ -368,35 +506,40 @@ 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; - double *sol; - lpp_sol_state_t state; - int i, count; - - count = lenv->last_x_var - lenv->first_x_var + 1; - sol = xmalloc(count * sizeof(sol[0])); - 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); - assert(state >= lpp_feasible && "The solution should at least be feasible!"); - } + int i; + + /* first check if there was sth. to optimize */ + if (lenv->first_x_var >= 0) { + int count = lenv->last_x_var - lenv->first_x_var + 1; + double *sol = XMALLOCN(double, count); + 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); + assert(state >= lpp_feasible && "The solution should at least be feasible!"); + } - for (i=0; i 1-EPSILON) { /* split variable name into components */ - lpp_get_var_name(ienv->lp, lenv->first_x_var+i, var_name, sizeof(var_name)); + if (sol[i] > 1-EPSILON) { /* split variable name into components */ + lpp_get_var_name(ienv->lp, lenv->first_x_var+i, var_name, sizeof(var_name)); - if (sscanf(var_name, "x_%d_%d", &nodenr, &color) == 2) { - ir_node *irn = pmap_get(lenv->nr_2_irn, INT_TO_PTR(nodenr)); - assert(irn && "This node number must be present in the map"); + if (sscanf(var_name, "x_%d_%d", &nodenr, &color) == 2) { + ir_node *irn = pmap_get(lenv->nr_2_irn, INT_TO_PTR(nodenr)); + assert(irn && "This node number must be present in the map"); - set_irn_col(ienv->co, irn, color); - } else - assert(0 && "This should be a x-var"); + set_irn_col(ienv->co, irn, color); + } else + assert(0 && "This should be a x-var"); + } } + + xfree(sol); } #ifdef COPYOPT_STAT @@ -408,17 +551,35 @@ static void ilp2_apply(ilp_env_t *ienv) { #endif } -int co_solve_ilp2(copy_opt_t *co, double time_limit) { +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; - my.time_limit = time_limit; + ASSERT_OU_AVAIL(co); //See build_clique_st + ASSERT_GS_AVAIL(co); + + my.time_limit = 0; my.first_x_var = -1; my.last_x_var = -1; my.nr_2_irn = pmap_create(); - my.dbg = firm_dbg_register("ir.be.coilp2"); - firm_dbg_set_mask(my.dbg, DEBUG_LVL); + FIRM_DBG_REGISTER(my.dbg, "firm.be.coilp2"); + + my.normal_colors = bitset_alloca(arch_register_class_n_regs(co->cls)); + bitset_clear_all(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); @@ -432,7 +593,8 @@ int co_solve_ilp2(copy_opt_t *co, double time_limit) { #else /* WITH_ILP */ -static void only_that_you_can_compile_without_WITH_ILP_defined(void) { +static inline void only_that_you_can_compile_without_WITH_ILP_defined(void) +{ } #endif /* WITH_ILP */