X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopyilp2.c;h=8054f48ece682bcafa1c1a5cb227a5822d2d6936;hb=dfc341ac6f54b4b0922d605e28333be76f487c68;hp=f1703fb7d555a024832140b89913209f3834d314;hpb=87d3e7eba011a02e25e216fc299dd41f82d6e30d;p=libfirm diff --git a/ir/be/becopyilp2.c b/ir/be/becopyilp2.c index f1703fb7d..8054f48ec 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-2007 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 @@ -25,14 +44,14 @@ * * 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 +#include "bitset.h" +#include "raw_bitset.h" #include "pdeq.h" #include "irtools.h" @@ -40,14 +59,15 @@ #include "becopyilp_t.h" #include "beifg_t.h" #include "besched_t.h" +#include "benodesets.h" #define DEBUG_LVL 1 typedef struct _local_env_t { - firm_dbg_module_t *dbg; double time_limit; int first_x_var, last_x_var; pmap *nr_2_irn; + DEBUG_ONLY(firm_dbg_module_t *dbg;) } local_env_t; static void build_coloring_cstr(ilp_env_t *ienv) { @@ -62,20 +82,22 @@ static void build_coloring_cstr(ilp_env_t *ienv) { be_ifg_foreach_node(ifg, iter, irn) if (!sr_is_removed(ienv->sr, irn)) { int col, cst_idx; - arch_register_req_t req; + const arch_register_req_t *req; int curr_node_color = get_irn_col(ienv->co, irn); int node_nr = (int)get_irn_node_nr(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(ienv->co->aenv, irn, -1); /* 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 { + arch_register_class_put(req->cls, colors); + // bitset_andnot(colors, ienv->co->cenv->ignore_colors); + } /* add the coloring constraint */ cst_idx = lpp_add_cst(ienv->lp, NULL, lpp_equal, 1.0); @@ -142,6 +164,12 @@ static void build_interference_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) { unit_t *curr; int n_colors = arch_register_class_n_regs(ienv->co->cls); @@ -194,7 +222,7 @@ static int compare_edge_t(const void *k1, const void *k2, size_t 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) (nodeset_hash((e)->n1) ^ nodeset_hash((e)->n2)) static INLINE edge_t *add_edge(set *edges, ir_node *n1, ir_node *n2, int *counter) { edge_t new_edge; @@ -249,7 +277,7 @@ static INLINE void remove_edge(set *edges, ir_node *n1, ir_node *n2, int *counte * 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) { - affinity_t *aff; + affinity_node_t *aff; /* for each node with affinity edges */ co_gs_foreach_aff_node(ienv->co, aff) { @@ -288,6 +316,9 @@ static void build_clique_star_cstr(ilp_env_t *ienv) { for (e=set_first(edges); !e->n1; e=set_next(edges)) /*nothing*/ ; + /* 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); @@ -358,7 +389,7 @@ static void extend_path(ilp_env_t *ienv, pdeq *path, ir_node *irn) { be_ifg_t *ifg = ienv->co->cenv->ifg; int i, len; ir_node **curr_path; - affinity_t *aff; + affinity_node_t *aff; neighb_t *nbr; /* do not walk backwards or in circles */ @@ -373,7 +404,7 @@ static void extend_path(ilp_env_t *ienv, pdeq *path, ir_node *irn) { /* check for forbidden interferences */ len = pdeq_len(path); curr_path = alloca(len * sizeof(*curr_path)); - pdeq_copyl(path, curr_path); + pdeq_copyl(path, (const void **)curr_path); for (i=1; ico, aff_info) { @@ -495,17 +526,19 @@ static void ilp2_apply(ilp_env_t *ienv) { #endif } -int co_solve_ilp2(copy_opt_t *co, double time_limit) { +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"); ienv = new_ilp_env(co, ilp2_build, ilp2_apply, &my); @@ -519,7 +552,7 @@ 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 */