X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopyilp.c;h=020ef9371ad4e51485135123a05c3033e775622a;hb=ab11945ab757f3f22a717a35d639be264b0f649c;hp=57fdab4ee999c1c4690b981aff507f832b0d1c30;hpb=1a3b7d363474ab544c13093a2f0b578718d37c7a;p=libfirm diff --git a/ir/be/becopyilp.c b/ir/be/becopyilp.c index 57fdab4ee..020ef9371 100644 --- a/ir/be/becopyilp.c +++ b/ir/be/becopyilp.c @@ -1,20 +1,6 @@ /* - * 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. + * Copyright (C) 2012 University of Karlsruhe. */ /** @@ -22,34 +8,35 @@ * @brief Common stuff used by all ILP formulations. * @author Daniel Grund * @date 28.02.2006 - * @version $Id$ */ #include "config.h" +#include + +#include "be_t.h" +#include "beintlive_t.h" +#include "beirg.h" #include "irtools.h" #include "irprintf.h" -#include "bestatevent.h" -#include "beirg.h" +#include "statev_t.h" #include "bemodule.h" #include "error.h" +#include "lpp.h" + #include "lc_opts.h" #include "lc_opts_enum.h" -#ifdef WITH_ILP - #define DUMP_ILP 1 -#define DUMP_SOL 2 static int time_limit = 60; static int solve_log = 0; static unsigned dump_flags = 0; static const lc_opt_enum_mask_items_t dump_items[] = { - { "ilp", DUMP_ILP }, - { "sol", DUMP_SOL }, - { NULL, 0 } + { "ilp", DUMP_ILP }, + { NULL, 0 } }; static lc_opt_enum_mask_var_t dump_var = { @@ -63,7 +50,7 @@ static const lc_opt_table_entry_t options[] = { LC_OPT_LAST }; -BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyilp); +BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyilp) void be_init_copyilp(void) { lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be"); @@ -89,111 +76,120 @@ void be_init_copyilp(void) *****************************************************************************/ -size_red_t *new_size_red(copy_opt_t *co) +/** + * Checks if a node is simplicial in the graph heeding the already removed nodes. + */ +static inline bool sr_is_simplicial(ilp_env_t *const ienv, ir_node const *const ifn) { - size_red_t *res = XMALLOC(size_red_t); + bool res = true; + ir_node **all = NEW_ARR_F(ir_node*, 0); + be_lv_t *const lv = be_get_irg_liveness(ienv->co->irg); + neighbours_iter_t iter; + be_ifg_foreach_neighbour(ienv->co->cenv->ifg, &iter, ifn, curr) { + /* Only consider non-removed neighbours. */ + if (sr_is_removed(ienv, curr)) + continue; + + /* Check whether the current node forms a clique with all previous nodes. */ + for (size_t i = ARR_LEN(all); i-- != 0;) { + if (!be_values_interfere(lv, curr, all[i])) { + res = false; + goto end; + } + } - res->co = co; - res->all_removed = pset_new_ptr_default(); - res->col_suff = NULL; - obstack_init(&res->ob); + ARR_APP1(ir_node*, all, curr); + } +end: + DEL_ARR_F(all); return res; } /** - * Checks if a node is simplicial in the graph heeding the already removed nodes. + * Virtually remove all nodes not related to the problem + * (simplicial AND not adjacent to a equal-color-edge) */ -static inline int sr_is_simplicial(size_red_t *sr, const ir_node *ifn) +static void sr_remove(ilp_env_t *const ienv) { - be_ifg_t *ifg = sr->co->cenv->ifg; - neighbours_iter_t iter; - ir_node **all = ALLOCAN(ir_node*, be_ifg_degree(ifg, ifn)); - ir_node *curr; - int size = 0; - int i; - int o; - - /* get all non-removed neighbors */ - be_ifg_foreach_neighbour(ifg, &iter, ifn, curr) - if (!sr_is_removed(sr, curr)) - all[size++] = curr; - - /* check if these form a clique */ - for (i=0; ico->cenv->ifg; - nodes_iter_t iter; + bool redo = true; + const be_ifg_t *ifg = ienv->co->cenv->ifg; while (redo) { - redo = 0; - be_ifg_foreach_node(ifg, &iter, irn) { - const arch_register_req_t *req = arch_get_register_req_out(irn); - - if (!arch_register_req_is(req, limited) && !sr_is_removed(sr, irn) && !co_gs_is_optimizable(sr->co, irn)) { - if (sr_is_simplicial(sr, irn)) { - coloring_suffix_t *cs = OALLOC(&sr->ob, coloring_suffix_t); - - cs->irn = irn; - cs->next = sr->col_suff; - sr->col_suff = cs; - - pset_insert_ptr(sr->all_removed, irn); - - redo = 1; - } - } + redo = false; + be_ifg_foreach_node(ifg, irn) { + const arch_register_req_t *req = arch_get_irn_register_req(irn); + if (arch_register_req_is(req, limited) || sr_is_removed(ienv, irn)) + continue; + if (co_gs_is_optimizable(ienv->co, irn)) + continue; + if (!sr_is_simplicial(ienv, irn)) + continue; + + ARR_APP1(ir_node*, ienv->col_suff, irn); + ir_nodeset_insert(&ienv->all_removed, irn); + + redo = true; } } } -void sr_reinsert(size_red_t *sr) +/** + * Virtually reinsert the nodes removed before and color them + */ +static void sr_reinsert(ilp_env_t *const ienv) { - coloring_suffix_t *cs; - be_ifg_t *ifg = sr->co->cenv->ifg; - bitset_t *used_cols = bitset_alloca(arch_register_class_n_regs(sr->co->cls)); + ir_graph *irg = ienv->co->irg; + be_ifg_t *ifg = ienv->co->cenv->ifg; + unsigned n_regs = arch_register_class_n_regs(ienv->co->cls); + + unsigned *const allocatable_cols = rbitset_alloca(n_regs); + be_set_allocatable_regs(irg, ienv->co->cls, allocatable_cols); + + unsigned *const possible_cols = rbitset_alloca(n_regs); neighbours_iter_t iter; /* color the removed nodes in right order */ - for (cs = sr->col_suff; cs; cs = cs->next) { - int free_col; - ir_node *other, *irn; + for (size_t i = ARR_LEN(ienv->col_suff); i-- != 0;) { + ir_node *const irn = ienv->col_suff[i]; - /* get free color by inspecting all neighbors */ - irn = cs->irn; - bitset_clear_all(used_cols); + rbitset_copy(possible_cols, allocatable_cols, n_regs); + /* get free color by inspecting all neighbors */ be_ifg_foreach_neighbour(ifg, &iter, irn, other) { - if (!sr_is_removed(sr, other)) /* only inspect nodes which are in graph right now */ - bitset_set(used_cols, get_irn_col(other)); + const arch_register_req_t *cur_req; + unsigned cur_col; + + /* only inspect nodes which are in graph right now */ + if (sr_is_removed(ienv, other)) + continue; + + cur_req = arch_get_irn_register_req(other); + cur_col = get_irn_col(other); + + /* Invalidate all single size register when it is a large one */ + do { + rbitset_clear(possible_cols, cur_col); + ++cur_col; + } while ((cur_col % cur_req->width) != 0); } /* now all bits not set are possible colors */ - free_col = bitset_next_clear(used_cols, 0); - assert(free_col != -1 && "No free color found. This can not be."); - set_irn_col(sr->co, irn, free_col); - pset_remove_ptr(sr->all_removed, irn); /* irn is back in graph again */ + /* take one that matches the alignment constraint */ + unsigned free_col; + assert(!rbitset_is_empty(possible_cols, n_regs) && "No free color found. This can not be."); + for (;;) { + free_col = (unsigned)rbitset_next(possible_cols, free_col, true); + if (free_col % arch_get_irn_register_req(irn)->width == 0) + break; + ++free_col; + assert(free_col < n_regs); + } + set_irn_col(ienv->co->cls, irn, free_col); + ir_nodeset_remove(&ienv->all_removed, irn); /* irn is back in graph again */ } } -void free_size_red(size_red_t *sr) -{ - del_pset(sr->all_removed); - obstack_free(&sr->ob, NULL); - free(sr); -} - /****************************************************************************** _____ _ _____ _ _____ / ____| (_) |_ _| | | __ \ @@ -214,35 +210,25 @@ ilp_env_t *new_ilp_env(copy_opt_t *co, ilp_callback build, ilp_callback apply, v res->build = build; res->apply = apply; res->env = env; - res->sr = new_size_red(co); + res->col_suff = NEW_ARR_F(ir_node*, 0); + ir_nodeset_init(&res->all_removed); return res; } lpp_sol_state_t ilp_go(ilp_env_t *ienv) { - be_options_t *options = be_get_irg_options(ienv->co->irg); + ir_graph *irg = ienv->co->irg; - sr_remove(ienv->sr); + sr_remove(ienv); ienv->build(ienv); - lpp_set_time_limit(ienv->lp, time_limit); - - if (solve_log) - lpp_set_log(ienv->lp, stdout); - - lpp_solve_net(ienv->lp, options->ilp_server, options->ilp_solver); - - //be_stat_ev_dbl("co_ilp_objval", ienv->lp->objval); - //be_stat_ev_dbl("co_ilp_best_bound", ienv->lp->best_bound); - be_stat_ev ("co_ilp_iter", lpp_get_iter_cnt(ienv->lp)); - be_stat_ev_dbl("co_ilp_sol_time", lpp_get_sol_time(ienv->lp)); if (dump_flags & DUMP_ILP) { char buf[128]; FILE *f; - ir_snprintf(buf, sizeof(buf), "%F_%s-co.ilp", ienv->co->cenv->irg, + ir_snprintf(buf, sizeof(buf), "%F_%s-co.ilp", irg, ienv->co->cenv->cls->name); f = fopen(buf, "wt"); if (f == NULL) { @@ -252,24 +238,28 @@ lpp_sol_state_t ilp_go(ilp_env_t *ienv) fclose(f); } + lpp_set_time_limit(ienv->lp, time_limit); + if (solve_log) + lpp_set_log(ienv->lp, stdout); + + lpp_solve(ienv->lp, be_options.ilp_server, be_options.ilp_solver); + + //stat_ev_dbl("co_ilp_objval", ienv->lp->objval); + //stat_ev_dbl("co_ilp_best_bound", ienv->lp->best_bound); + stat_ev_int("co_ilp_iter", lpp_get_iter_cnt(ienv->lp)); + stat_ev_dbl("co_ilp_sol_time", lpp_get_sol_time(ienv->lp)); + ienv->apply(ienv); - sr_reinsert(ienv->sr); + sr_reinsert(ienv); return lpp_get_sol_state(ienv->lp); } void free_ilp_env(ilp_env_t *ienv) { - free_size_red(ienv->sr); - free_lpp(ienv->lp); + ir_nodeset_destroy(&ienv->all_removed); + DEL_ARR_F(ienv->col_suff); + lpp_free(ienv->lp); free(ienv); } - -#else /* WITH_ILP */ - -static inline void only_that_you_can_compile_without_WITH_ILP_defined(void) -{ -} - -#endif /* WITH_ILP */