X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Flpp%2Flpp.c;h=9ac76f4cf4f3c42eba24a56d5e00c4bb6af8817f;hb=b59e22a229aa1227ef992c184c79fdafe34908cf;hp=7ef0eba3b4dac24a2ac66cce9710531a6d3a3375;hpb=73807220b633b9a02e9a9561a089141e38be2fdb;p=libfirm diff --git a/ir/lpp/lpp.c b/ir/lpp/lpp.c index 7ef0eba3b..9ac76f4cf 100644 --- a/ir/lpp/lpp.c +++ b/ir/lpp/lpp.c @@ -1,17 +1,28 @@ -/** - * Author: Daniel Grund - * Date: Fri 13.05.2005 - * Copyright: (c) Universitaet Karlsruhe - * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. - * CVS-Id: $Id: lpp.c 27353 2010-04-07 13:33:16Z matze $ +/* + * Copyright (C) 2005-2011 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 + * @author Daniel Grund + */ #include "config.h" -#ifdef HAVE_IO_H -#include -#endif - #include #include #include @@ -21,50 +32,55 @@ #include "hashptr.h" #include "debug.h" #include "set.h" +#include "debug.h" #include "sp_matrix.h" #include "mps.h" #include "lpp_t.h" #include "lpp_comm.h" #include "lpp_solvers.h" +#include "lpp_net.h" -#define HASH_NAME_T(n) HASH_STR((n)->name, strlen((n)->name)) +#define HASH_NAME_T(n) hash_str((n)->name) -static firm_dbg_module_t *dbg = NULL; +DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;) -static inline char *obst_xstrdup(struct obstack *obst, const char *str) { - return obstack_copy0(obst, str, strlen(str)); +static inline char *obst_xstrdup(struct obstack *obst, const char *str) +{ + return (char*)obstack_copy0(obst, str, strlen(str)); } -static int cmp_name_t(const void *x, const void *y, size_t size) { - const lpp_name_t *n = x; - const lpp_name_t *m = y; - (void)size; /* stop warnings */ +static int cmp_name_t(const void *x, const void *y, size_t size) +{ + const lpp_name_t *n = (const lpp_name_t*)x; + const lpp_name_t *m = (const lpp_name_t*)y; + (void)size; return strcmp(n->name, m->name); } /** * Update statistic information about matrix usage. */ -static void update_stats(lpp_t *lpp) { +static void update_stats(lpp_t *lpp) +{ lpp->n_elems = matrix_get_entries(lpp->m); lpp->matrix_mem = lpp->n_elems * matrix_get_elem_size(); lpp->density = (double)lpp->n_elems / (double)(lpp->cst_next * lpp->var_next) * 100.0; } -#define INITIAL_SIZE 64 - -lpp_t *new_lpp(const char *name, lpp_opt_t opt_type) { - return new_lpp_userdef(name, opt_type, INITIAL_SIZE, INITIAL_SIZE, 2.0); +lpp_t *lpp_new(const char *name, lpp_opt_t opt_type) +{ + return lpp_new_userdef(name, opt_type, 64, 64, 2.0); } -lpp_t *new_lpp_userdef(const char *name, lpp_opt_t opt_type, - int estimated_vars, int estimated_csts, double grow_factor) +lpp_t *lpp_new_userdef(const char *name, lpp_opt_t opt_type, + int estimated_vars, int estimated_csts, + double grow_factor) { lpp_t *lpp; int idx; - dbg = firm_dbg_register("lpp"); + DEBUG_ONLY(dbg = firm_dbg_register("lpp");) lpp = XMALLOCZ(lpp_t); obstack_init(&lpp->obst); @@ -87,12 +103,14 @@ lpp_t *new_lpp_userdef(const char *name, lpp_opt_t opt_type, return lpp; } -void free_lpp_matrix(lpp_t *lpp) { +void lpp_free_matrix(lpp_t *lpp) +{ del_matrix(lpp->m); lpp->m = NULL; } -void free_lpp(lpp_t *lpp) { +void lpp_free(lpp_t *lpp) +{ obstack_free(&lpp->obst, NULL); del_set(lpp->cst2nr); @@ -108,31 +126,43 @@ void free_lpp(lpp_t *lpp) { free(lpp); } -double lpp_get_fix_costs(lpp_t *lpp) { +double lpp_get_fix_costs(lpp_t *lpp) +{ return matrix_get(lpp->m, 0, 0); } -void lpp_set_fix_costs(lpp_t *lpp, double value) { +void lpp_set_fix_costs(lpp_t *lpp, double value) +{ matrix_set(lpp->m, 0, 0, value); } -static inline int name2nr(set *where, const char *name) { +static int name2nr(set *where, const char *name) +{ lpp_name_t find, *found; find.name = name; - found = set_find(where, &find, sizeof(find), HASH_NAME_T(&find)); + found = set_find(lpp_name_t, where, &find, sizeof(find), HASH_NAME_T(&find)); return (found ? found->nr : -1); } -#define cst_nr(lpp, name) name2nr(lpp->cst2nr, name) -#define var_nr(lpp, name) name2nr(lpp->var2nr, name) +static int cst_nr(const lpp_t *lpp, const char *name) +{ + return name2nr(lpp->cst2nr, name); +} + +static int var_nr(const lpp_t *lpp, const char *name) +{ + return name2nr(lpp->var2nr, name); +} -static inline char *get_next_name(lpp_t *lpp) { - char *res = obstack_alloc(&lpp->obst, 12); - snprintf(res, 12, "_%d", lpp->next_name_number++); +static inline char *get_next_name(lpp_t *lpp) +{ + char *res = OALLOCN(&lpp->obst, char, 12); + snprintf(res, 12, "_%u", lpp->next_name_number++); return res; } -int lpp_add_cst(lpp_t *lpp, const char *cst_name, lpp_cst_t cst_type, double rhs) { +int lpp_add_cst(lpp_t *lpp, const char *cst_name, lpp_cst_t cst_type, double rhs) +{ lpp_name_t n, *inner; DBG((dbg, LEVEL_2, "%s %d %g\n", cst_name, cst_type, rhs)); @@ -146,7 +176,7 @@ int lpp_add_cst(lpp_t *lpp, const char *cst_name, lpp_cst_t cst_type, double rhs n.name = get_next_name(lpp); n.nr = -1; - inner = set_insert(lpp->cst2nr, &n, sizeof(n), HASH_NAME_T(&n)); + inner = set_insert(lpp_name_t, lpp->cst2nr, &n, sizeof(n), HASH_NAME_T(&n)); assert(inner); if (inner->nr == -1) { @@ -169,29 +199,33 @@ int lpp_add_cst(lpp_t *lpp, const char *cst_name, lpp_cst_t cst_type, double rhs return inner->nr; } -int lpp_add_cst_uniq(lpp_t *lpp, const char *cst_name, lpp_cst_t cst_type, double rhs) { +int lpp_add_cst_uniq(lpp_t *lpp, const char *cst_name, lpp_cst_t cst_type, double rhs) +{ if (cst_name) { lpp_name_t n; n.name = cst_name; n.nr = -1; - assert(!set_find(lpp->cst2nr, &n, sizeof(n), HASH_NAME_T(&n)) && + assert(!set_find(lpp_name_t, lpp->cst2nr, &n, sizeof(n), HASH_NAME_T(&n)) && "constraint already exists"); } return lpp_add_cst(lpp, cst_name, cst_type, rhs); } -int lpp_get_cst_idx(lpp_t *lpp, const char *cst_name) { +int lpp_get_cst_idx(lpp_t *lpp, const char *cst_name) +{ DBG((dbg, LEVEL_2, "%s --> %d\n", cst_name, cst_nr(lpp, cst_name))); return cst_nr(lpp, cst_name); } -void lpp_get_cst_name(lpp_t *lpp, int index, char *buf, size_t buf_size) { +void lpp_get_cst_name(lpp_t *lpp, int index, char *buf, size_t buf_size) +{ DBG((dbg, LEVEL_2, "%d --> %s\n", index, lpp->csts[index]->name)); strncpy(buf, lpp->csts[index]->name, buf_size); } -int lpp_add_var_default(lpp_t *lpp, const char *var_name, lpp_var_t var_type, double obj, double startval) { +int lpp_add_var_default(lpp_t *lpp, const char *var_name, lpp_var_t var_type, double obj, double startval) +{ int val; val = lpp_add_var(lpp, var_name, var_type, obj); @@ -200,7 +234,8 @@ int lpp_add_var_default(lpp_t *lpp, const char *var_name, lpp_var_t var_type, do return val; } -int lpp_add_var(lpp_t *lpp, const char *var_name, lpp_var_t var_type, double obj) { +int lpp_add_var(lpp_t *lpp, const char *var_name, lpp_var_t var_type, double obj) +{ lpp_name_t n, *inner; DBG((dbg, LEVEL_2, "%s %d %g\n", var_name, var_type, obj)); @@ -216,12 +251,12 @@ int lpp_add_var(lpp_t *lpp, const char *var_name, lpp_var_t var_type, double obj n.name = get_next_name(lpp); n.nr = -1; - inner = set_insert(lpp->var2nr, &n, sizeof(n), HASH_NAME_T(&n)); + inner = set_insert(lpp_name_t, lpp->var2nr, &n, sizeof(n), HASH_NAME_T(&n)); assert(inner); if (inner->nr == -1) { inner->nr = lpp->var_next; - inner->value_kind = 0; + inner->value_kind = lpp_none; inner->value = 0; inner->type.var_type = var_type; @@ -239,17 +274,20 @@ int lpp_add_var(lpp_t *lpp, const char *var_name, lpp_var_t var_type, double obj return inner->nr; } -int lpp_get_var_idx(lpp_t *lpp, const char *var_name) { +int lpp_get_var_idx(lpp_t *lpp, const char *var_name) +{ DBG((dbg, LEVEL_2, "%s --> %d\n", var_name, var_nr(lpp, var_name))); return var_nr(lpp, var_name); } -void lpp_get_var_name(lpp_t *lpp, int index, char *buf, size_t buf_size) { +void lpp_get_var_name(lpp_t *lpp, int index, char *buf, size_t buf_size) +{ DBG((dbg, LEVEL_2, "%d --> %s\n", index, lpp->vars[index]->name)); strncpy(buf, lpp->vars[index]->name, buf_size); } -int lpp_set_factor(lpp_t *lpp, const char *cst_name, const char *var_name, double value) { +int lpp_set_factor(lpp_t *lpp, const char *cst_name, const char *var_name, double value) +{ int cst, var; cst = cst_nr(lpp, cst_name); @@ -261,7 +299,8 @@ int lpp_set_factor(lpp_t *lpp, const char *cst_name, const char *var_name, doubl return 0; } -int lpp_set_factor_fast(lpp_t *lpp, int cst_idx, int var_idx, double value) { +int lpp_set_factor_fast(lpp_t *lpp, int cst_idx, int var_idx, double value) +{ assert(cst_idx >= 0 && var_idx >= 0); assert(cst_idx < lpp->cst_next && var_idx < lpp->var_next); DBG((dbg, LEVEL_2, "%s[%d] %s[%d] %g\n", lpp->csts[cst_idx]->name, cst_idx, lpp->vars[var_idx]->name, var_idx, value)); @@ -270,7 +309,8 @@ int lpp_set_factor_fast(lpp_t *lpp, int cst_idx, int var_idx, double value) { return 0; } -int lpp_set_factor_fast_bulk(lpp_t *lpp, int cst_idx, int *var_idx, int num_vars, double value) { +int lpp_set_factor_fast_bulk(lpp_t *lpp, int cst_idx, int *var_idx, int num_vars, double value) +{ assert(cst_idx >= 0 && cst_idx < lpp->cst_next); assert(num_vars < lpp->var_next); DBG((dbg, LEVEL_2, "row %s[%d] %d vars %g\n", lpp->csts[cst_idx]->name, cst_idx, num_vars, value)); @@ -279,14 +319,16 @@ int lpp_set_factor_fast_bulk(lpp_t *lpp, int cst_idx, int *var_idx, int num_vars return 0; } -void lpp_set_start_value(lpp_t *lpp, int var_idx, double value) { +void lpp_set_start_value(lpp_t *lpp, int var_idx, double value) +{ assert(var_idx > 0 && var_idx < lpp->var_next); DBG((dbg, LEVEL_2, "%d %s %g\n", var_idx, lpp->vars[var_idx]->name, value)); lpp->vars[var_idx]->value = value; lpp->vars[var_idx]->value_kind = lpp_value_start; } -lpp_sol_state_t lpp_get_solution(lpp_t *lpp, double *values, int begin, int end) { +lpp_sol_state_t lpp_get_solution(lpp_t *lpp, double *values, int begin, int end) +{ int i; if (lpp->sol_state < lpp_feasible) @@ -299,7 +341,8 @@ lpp_sol_state_t lpp_get_solution(lpp_t *lpp, double *values, int begin, int end) return lpp->sol_state; } -void lpp_check_startvals(lpp_t *lpp) { +void lpp_check_startvals(lpp_t *lpp) +{ int cst_idx; for (cst_idx = 1; cst_idx < lpp->cst_next; ++cst_idx) { @@ -321,14 +364,14 @@ void lpp_check_startvals(lpp_t *lpp) { fprintf(stderr, "constraint %s unsatisfied: %g != %g\n", cst->name, sum, cst_val); } break; - case lpp_less: + case lpp_less_equal: if(sum > cst_val) { - fprintf(stderr, "constraint %s unsatisfied: %g > %g\n", cst->name, sum, cst_val); + fprintf(stderr, "constraint %s unsatisfied: %g >= %g\n", cst->name, sum, cst_val); } break; - case lpp_greater: + case lpp_greater_equal: if(sum < cst_val) { - fprintf(stderr, "constraint %s unsatisfied: %g < %g\n", cst->name, sum, cst_val); + fprintf(stderr, "constraint %s unsatisfied: %g <= %g\n", cst->name, sum, cst_val); } break; default: @@ -338,7 +381,8 @@ next: ; } } -void lpp_dump(lpp_t *lpp, const char *filename) { +void lpp_dump(lpp_t *lpp, const char *filename) +{ FILE *out = fopen(filename, "wt"); mps_write_mps(lpp, s_mps_fixed, out); fclose(out); @@ -352,37 +396,51 @@ void lpp_set_log(lpp_t *lpp, FILE *log) static const char *lpp_cst_op_to_str(lpp_cst_t cst) { - switch(cst) { - case lpp_equal: - return "="; - case lpp_less: - return "<="; - case lpp_greater: - return ">="; + switch(cst) { + case lpp_equal: + return "="; + case lpp_less_equal: + return "<="; + case lpp_greater_equal: + return ">="; default: - return ""; - } + return ""; + } } void lpp_dump_plain(lpp_t *lpp, FILE *f) { - int i; + int i; + + fprintf(f, lpp->opt_type == lpp_minimize ? "Minimize\n" : "Maximize\n"); + for(i = 0; i < lpp->cst_next; ++i) { + lpp_name_t *cst = lpp->csts[i]; + + + fprintf(f, "%16s: ", cst->name); + matrix_foreach_in_row(lpp->m, cst->nr, elm) { + lpp_name_t *var = lpp->vars[elm->col]; + /* TODO Perhaps better a define LPP_COL_RHS */ + if(elm->col > 0) + fprintf(f, "%+4.1f %-16s ", elm->val, var->name); + } - for(i = 0; i < lpp->cst_next; ++i) { - const matrix_elem_t *elm; - lpp_name_t *cst = lpp->csts[i]; + if (i == 0) { + fprintf(f, "\nSubject To\n"); + continue; + } - fprintf(f, "%16s: ", cst->name); - matrix_foreach_in_row(lpp->m, cst->nr, elm) { - lpp_name_t *var = lpp->vars[elm->col]; - /* TODO Perhaps better a define LPP_COL_RHS */ - if(elm->col > 0) - fprintf(f, "%+4.1f*%-16s ", elm->val, var->name); - } + fprintf(f, "%3s %+4.1f\n", + lpp_cst_op_to_str(cst->type.cst_type), matrix_get(lpp->m, cst->nr, 0)); + } - fprintf(f, "%3s %+4.1f\n", - lpp_cst_op_to_str(cst->type.cst_type), matrix_get(lpp->m, cst->nr, 0)); - } + fprintf(f, "Binary\n"); + for(i = 0; i < lpp->var_next; ++i) { + lpp_name_t *var = lpp->vars[i]; + if (var->type.var_type == lpp_binary) + fprintf(f, "%16s\n", var->name); + } + fprintf(f, "End\n"); } /** @@ -404,7 +462,7 @@ void lpp_serialize(lpp_comm_t *comm, const lpp_t *lpp, int with_names) lpp_writel(comm, lpp->set_bound); lpp_writed(comm, lpp->bound); lpp_writed(comm, lpp->time_limit_secs); - lpp_writed(comm, lpp->emphasis); + lpp_writel(comm, lpp->emphasis); for(i = 0; i < lpp->cst_next; ++i) { lpp_name_t *name = lpp->csts[i]; @@ -426,25 +484,19 @@ void lpp_serialize(lpp_comm_t *comm, const lpp_t *lpp, int with_names) lpp_writes(comm, name->name); } - { - const matrix_elem_t *elm; - n = 0; + n = 0; + matrix_foreach(lpp->m, elm) + n++; - matrix_foreach(lpp->m, elm) - n++; - - assert(n == matrix_get_entries(lpp->m)); - lpp_writel(comm, n); - matrix_foreach(lpp->m, elm) { - lpp_writel(comm, elm->row); - lpp_writel(comm, elm->col); - lpp_writed(comm, elm->val); - } + assert(n == matrix_get_entries(lpp->m)); + lpp_writel(comm, n); + matrix_foreach(lpp->m, elm) { + lpp_writel(comm, elm->row); + lpp_writel(comm, elm->col); + lpp_writed(comm, elm->val); } } -#define NAMELEN 64 - /** * Deserialize an lpp from a file descriptor. * @param comm The file descriptor. @@ -461,14 +513,14 @@ lpp_t *lpp_deserialize(lpp_comm_t *comm) with_names = lpp_readl(comm); lpp->cst_next = lpp_readl(comm); lpp->var_next = lpp_readl(comm); - lpp->opt_type = lpp_readl(comm); + lpp->opt_type = (lpp_opt_t)lpp_readl(comm); lpp->name = lpp_reads(comm); /* read options */ lpp->set_bound = lpp_readl(comm); lpp->bound = lpp_readd(comm); lpp->time_limit_secs = lpp_readd(comm); - lpp->emphasis = lpp_readd(comm); + lpp->emphasis = (lpp_emphasis_t)lpp_readl(comm); lpp->cst_size = lpp->cst_next; lpp->var_size = lpp->var_next; @@ -484,18 +536,18 @@ lpp_t *lpp_deserialize(lpp_comm_t *comm) lpp_name_t name, *res; name.nr = lpp_readl(comm); - name.value_kind = lpp_readl(comm); - name.type.cst_type = lpp_readl(comm); - - if(with_names) - name.name = lpp_reads(comm); - else { - char* buf = XMALLOCN(char, NAMELEN); - snprintf(buf, NAMELEN, "c%d\n", name.nr); + name.value_kind = (lpp_value_kind_t)lpp_readl(comm); + name.type.cst_type = (lpp_cst_t)lpp_readl(comm); + + if(with_names) { + name.name = lpp_reads(comm); + } else { + char* buf = XMALLOCN(char, 32); + snprintf(buf, 32, "c%d\n", name.nr); name.name = buf; } - res = set_insert(lpp->cst2nr, &name, sizeof(name), HASH_NAME_T(&name)); + res = set_insert(lpp_name_t, lpp->cst2nr, &name, sizeof(name), HASH_NAME_T(&name)); lpp->csts[name.nr] = res; } @@ -503,18 +555,18 @@ lpp_t *lpp_deserialize(lpp_comm_t *comm) lpp_name_t name, *res; name.nr = lpp_readl(comm); - name.value_kind = lpp_readl(comm); - name.type.var_type = lpp_readl(comm); - - if(with_names) - name.name = lpp_reads(comm); - else { - char* buf = XMALLOCN(char, NAMELEN); - snprintf(buf, NAMELEN, "v%d\n", name.nr); + name.value_kind = (lpp_value_kind_t)lpp_readl(comm); + name.type.var_type = (lpp_var_t)lpp_readl(comm); + + if(with_names) { + name.name = lpp_reads(comm); + } else { + char* buf = XMALLOCN(char, 32); + snprintf(buf, 32, "v%d\n", name.nr); name.name = buf; } - res = set_insert(lpp->var2nr, &name, sizeof(name), HASH_NAME_T(&name)); + res = set_insert(lpp_name_t, lpp->var2nr, &name, sizeof(name), HASH_NAME_T(&name)); lpp->vars[name.nr] = res; } @@ -532,38 +584,38 @@ lpp_t *lpp_deserialize(lpp_comm_t *comm) void lpp_serialize_values(lpp_comm_t *comm, const lpp_t *lpp, lpp_value_kind_t value_kind) { - int i, n; + int i, n; - for(i = 0, n = 0; i < lpp->var_next; ++i) - n += lpp->vars[i]->value_kind == value_kind; + for(i = 0, n = 0; i < lpp->var_next; ++i) + n += lpp->vars[i]->value_kind == value_kind; - /* Write the number of values to expect */ - lpp_writel(comm, n); + /* Write the number of values to expect */ + lpp_writel(comm, n); - /* send the values */ - for(i = 0, n = lpp->var_next; i < n; ++i) { - const lpp_name_t *name = lpp->vars[i]; - if(name->value_kind == value_kind) { - lpp_writel(comm, name->nr); - lpp_writed(comm, name->value); - } - } + /* send the values */ + for(i = 0, n = lpp->var_next; i < n; ++i) { + const lpp_name_t *name = lpp->vars[i]; + if(name->value_kind == value_kind) { + lpp_writel(comm, name->nr); + lpp_writed(comm, name->value); + } + } } void lpp_deserialize_values(lpp_comm_t *comm, lpp_t *lpp, lpp_value_kind_t value_kind) { - int i, n; + int i, n; - /* Get the number of values to read */ - n = lpp_readl(comm); + /* Get the number of values to read */ + n = lpp_readl(comm); - for(i = 0; i < n; ++i) { - int nr = lpp_readl(comm); - lpp_name_t *name = lpp->vars[nr]; + for(i = 0; i < n; ++i) { + int nr = lpp_readl(comm); + lpp_name_t *name = lpp->vars[nr]; - name->value_kind = value_kind; - name->value = lpp_readd(comm); - } + name->value_kind = value_kind; + name->value = lpp_readd(comm); + } } void lpp_serialize_stats(lpp_comm_t *comm, const lpp_t *lpp) @@ -577,7 +629,7 @@ void lpp_serialize_stats(lpp_comm_t *comm, const lpp_t *lpp) void lpp_deserialize_stats(lpp_comm_t *comm, lpp_t *lpp) { - lpp->sol_state = lpp_readl(comm); + lpp->sol_state = (lpp_sol_state_t)lpp_readl(comm); lpp->iterations = lpp_readl(comm); lpp->sol_time = lpp_readd(comm); lpp->objval = lpp_readd(comm); @@ -590,9 +642,7 @@ void lpp_solve(lpp_t *lpp, const char* host, const char* solver) lpp_solver_func_t* f = lpp_find_solver(solver); if (f != NULL) f(lpp); - } - - else { + } else { lpp_solve_net(lpp, host, solver); } }