From a74dd232f3a548725906e992f06f6e44e83969f4 Mon Sep 17 00:00:00 2001 From: Sebastian Hack Date: Tue, 26 Jul 2005 12:07:09 +0000 Subject: [PATCH] Moved to new lpp library Moved to new libcore --- ir/be/Makefile.in | 2 +- ir/be/bearch.c | 2 +- ir/be/bearch.h | 10 +- ir/be/bearch_firm.c | 2 +- ir/be/bemain.c | 15 +- ir/be/lpp.c | 213 -------------------- ir/be/lpp.h | 156 --------------- ir/be/lpp_local.c | 207 -------------------- ir/be/lpp_local.h | 15 -- ir/be/lpp_remote.c | 174 ----------------- ir/be/lpp_remote.h | 15 -- ir/be/mps.c | 164 ---------------- ir/be/mps.h | 35 ---- ir/be/sp_matrix.c | 462 -------------------------------------------- ir/be/sp_matrix.h | 129 ------------- 15 files changed, 21 insertions(+), 1580 deletions(-) delete mode 100644 ir/be/lpp.c delete mode 100644 ir/be/lpp.h delete mode 100644 ir/be/lpp_local.c delete mode 100644 ir/be/lpp_local.h delete mode 100644 ir/be/lpp_remote.c delete mode 100644 ir/be/lpp_remote.h delete mode 100644 ir/be/mps.c delete mode 100644 ir/be/mps.h delete mode 100644 ir/be/sp_matrix.c delete mode 100644 ir/be/sp_matrix.h diff --git a/ir/be/Makefile.in b/ir/be/Makefile.in index 5da008ef4..e225b88e8 100644 --- a/ir/be/Makefile.in +++ b/ir/be/Makefile.in @@ -26,7 +26,7 @@ SOURCES += Makefile.in besched.h belistsched.h belistsched.c \ becopyoptmain.c becopyopt.c becopyheur.c \ becopyilp.c becopystat.c bearch_firm.c bearch.c bechordal_draw.c \ bechordal_draw.h beirgmod.c beirgmod.h benode.c benode_t.h \ - bessadestr.c beifg.c bedupl.c bedupl.h + bessadestr.c beifg.c bedupl.c include $(topdir)/MakeRules diff --git a/ir/be/bearch.c b/ir/be/bearch.c index 137f852e0..bd53bd8c9 100644 --- a/ir/be/bearch.c +++ b/ir/be/bearch.c @@ -43,7 +43,7 @@ arch_env_t *arch_env_add_irn_handler(arch_env_t *env, static const arch_irn_ops_t *fallback_irn_ops = NULL; -int arch_register_class_put(const arch_register_class_t *cls, struct _bitset_t *bs) +int arch_register_class_put(const arch_register_class_t *cls, bitset_t *bs) { if(bs) { int i, n; diff --git a/ir/be/bearch.h b/ir/be/bearch.h index a6e5845b6..0d32c18a3 100644 --- a/ir/be/bearch.h +++ b/ir/be/bearch.h @@ -7,14 +7,13 @@ #include "irnode.h" #include "irmode.h" +#include "bitset.h" #include "hashptr.h" #include "fourcc.h" #include "set.h" #include "list.h" #include "ident.h" -struct _bitset_t; - typedef struct _arch_register_class_t arch_register_class_t; typedef struct _arch_register_t arch_register_t; typedef struct _arch_enum_t arch_enum_t; @@ -81,8 +80,7 @@ struct _arch_register_class_t { * @param bs The bitset. May be NULL. * @return The number of registers in the class. */ -extern int arch_register_class_put(const arch_register_class_t *cls, - struct _bitset_t *bs); +extern int arch_register_class_put(const arch_register_class_t *cls, bitset_t *bs); static INLINE const arch_register_t * _arch_register_for_index(const arch_register_class_t *cls, int idx) @@ -170,7 +168,7 @@ typedef struct _arch_register_req_t { const arch_register_class_t *cls; /** The register class this constraint belongs to. */ union { - int (*limited)(const ir_node *irn, int pos, struct _bitset_t *bs); + int (*limited)(const ir_node *irn, int pos, bitset_t *bs); /** In case of the 'limited' constraint, this function must put all allowable @@ -348,7 +346,7 @@ extern int arch_is_register_operand(const arch_env_t *env, * @return The amount of registers allocatable for that operand. */ extern int arch_get_allocatable_regs(const arch_env_t *env, const ir_node *irn, - int pos, const arch_register_class_t *cls, struct _bitset_t *bs); + int pos, const arch_register_class_t *cls, bitset_t *bs); /** * Check, if a register is assignable to an operand of a node. diff --git a/ir/be/bearch_firm.c b/ir/be/bearch_firm.c index 1aacdc186..678806fcd 100644 --- a/ir/be/bearch_firm.c +++ b/ir/be/bearch_firm.c @@ -13,7 +13,7 @@ #include "irreflect.h" -#define N_REGS 64 +#define N_REGS 4 static arch_register_t datab_regs[N_REGS]; diff --git a/ir/be/bemain.c b/ir/be/bemain.c index 6d874d639..05e8fae8b 100644 --- a/ir/be/bemain.c +++ b/ir/be/bemain.c @@ -153,9 +153,21 @@ static void be_main_loop(void) be_liveness(irg); dump_ir_block_graph_sched(irg, "-sched"); + copystat_reset(); copystat_collect_irg(irg, env.arch_env); + /* + * Spilling changed the liveness information. + * Recompute it now. + */ + be_liveness(irg); + + /* + * Verifying the schedule once again cannot hurt. + */ + sched_verify_irg(irg); + /* Perform the following for each register class. */ for(j = 0, m = isa->get_n_reg_class(); j < m; ++j) { be_chordal_env_t *chordal_env; @@ -176,8 +188,9 @@ static void be_main_loop(void) be_ra_chordal_done(chordal_env); } + copystat_dump_pretty(irg); - be_numbering_done(irg); + be_numbering_done(irg); } } diff --git a/ir/be/lpp.c b/ir/be/lpp.c deleted file mode 100644 index da1857c8e..000000000 --- a/ir/be/lpp.c +++ /dev/null @@ -1,213 +0,0 @@ -/** - * Author: Daniel Grund - * Date: Fri 13.05.2005 - * Copyright: (c) Universitaet Karlsruhe - * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. - */ - -#ifdef HAVE_CONFIG_H -#include "config.h" -#endif - -#ifdef HAVE_IO_H -#include -#endif - -#include -#include -#include - -#include "xmalloc.h" -#include "debug.h" -#include "assert.h" -#include "hashptr.h" -#include "mps.h" -#include "lpp.h" - -#define DEBUG_LVL SET_LEVEL_1 -static firm_dbg_module_t *dbg = NULL; - -#define HASH_NAME_T(n) HASH_STR((n)->name, strlen((n)->name)) - -static int cmp_name_t(const void *x, const void *y, size_t size) { - const name_t *n = x; - const name_t *m = y; - return strcmp(n->name, m->name); -} - -#define INITIAL_SIZE 64 - -lpp_t *new_lpp(const char *name, opt_t opt_type) { - lpp_t *lpp; - - dbg = firm_dbg_register("ir.be.lpp"); - firm_dbg_set_mask(dbg, DEBUG_LVL); - - lpp = xcalloc(1, sizeof(*lpp)); - lpp->name = xstrdup(name); - lpp->opt_type = opt_type; - lpp->cst2nr = new_set(cmp_name_t, INITIAL_SIZE); - lpp->var2nr = new_set(cmp_name_t, INITIAL_SIZE); - lpp->cst_size = INITIAL_SIZE; - lpp->var_size = INITIAL_SIZE; - lpp->csts = xcalloc(INITIAL_SIZE, sizeof(*lpp->csts)); - lpp->vars = xcalloc(INITIAL_SIZE, sizeof(*lpp->vars)); - lpp->m = new_matrix(INITIAL_SIZE, INITIAL_SIZE); - lpp_add_cst(lpp, "obj", objective, 0); - lpp_add_var(lpp, "rhs", rhs, 0); - return lpp; -} - -void free_lpp(lpp_t *lpp) { - int i; - for(i=0;icst_next;++i) - free(lpp->csts[i]->name); - for(i=0;ivar_next;++i) - free(lpp->vars[i]->name); - del_set(lpp->cst2nr); - del_set(lpp->var2nr); - del_matrix(lpp->m); - free(lpp->name); - free(lpp->csts); - free(lpp->vars); - if (lpp->error) - free(lpp->error); - free(lpp); -} - -static INLINE int name2nr(set *where, char *name) { - name_t find, *found; - find.name = name; - found = set_find(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 INLINE char *get_next_name(lpp_t *lpp) { - char *res = xmalloc(12); - snprintf(res, 12, "_%d", lpp->next_name_number++); - return res; -} - -int lpp_add_cst(lpp_t *lpp, char *cst_name, cst_t cst_type, double rhs) { - name_t n, *inner; - DBG((dbg, LEVEL_2, "%s %d %g\n", cst_name, cst_type, rhs)); - if (cst_name && cst_name[0] == '_') - return ERR_NAME_NOT_ALLOWED; - if (cst_name) - n.name = xstrdup(cst_name); - else - n.name = get_next_name(lpp); - n.nr = -1; - inner = set_insert(lpp->cst2nr, &n, sizeof(n), HASH_NAME_T(&n)); - assert(inner); - - if (inner->nr == -1) { - inner->nr = lpp->cst_next; - inner->type.cst_type = cst_type; - if (lpp->cst_next == lpp->cst_size) { - lpp->cst_size *= 2; - lpp->csts = xrealloc(lpp->csts, lpp->cst_size * sizeof(*lpp->csts)); - } - lpp->csts[lpp->cst_next] = inner; - lpp->cst_next++; - matrix_set(lpp->m, inner->nr, 0, rhs); - } - - return inner->nr; -} - -int lpp_get_cst_idx(lpp_t *lpp, 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) { - DBG((dbg, LEVEL_2, "%d --> %s\n", index, lpp->csts[index]->name)); - strncpy(buf, lpp->csts[index]->name, buf_size); -} - -int lpp_add_var(lpp_t *lpp, char *var_name, var_t var_type, double obj) { - name_t n, *inner; - DBG((dbg, LEVEL_2, "%s %d %g\n", var_name, var_type, obj)); - assert(var_type != invalid && "invalid is for internal use only"); - if (var_name && var_name[0] == '_') - return ERR_NAME_NOT_ALLOWED; - if (var_name) - n.name = xstrdup(var_name); - else - n.name = get_next_name(lpp); - n.nr = -1; - inner = set_insert(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 = 0; - inner->type.var_type = var_type; - if (lpp->var_next == lpp->var_size) { - lpp->var_size *= 2; - lpp->vars = xrealloc(lpp->vars, lpp->var_size * sizeof(*lpp->vars)); - } - lpp->vars[lpp->var_next] = inner; - lpp->var_next++; - matrix_set(lpp->m, 0, inner->nr, obj); - } - - return inner->nr; -} - -int lpp_get_var_idx(lpp_t *lpp, 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) { - 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, char *cst_name, char *var_name, double value) { - int cst, var; - - cst = cst_nr(lpp, cst_name); - var = var_nr(lpp, var_name); - assert(cst != -1 && var != -1); - DBG((dbg, LEVEL_2, "%s[%d] %s[%d] %g\n", cst_name, cst, var_name, var, value)); - matrix_set(lpp->m, cst, var, value); - return 0; -} - -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)); - matrix_set(lpp->m, cst_idx, var_idx, value); - return 0; -} - -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 = value_start; -} - -sol_state_t lpp_get_solution(lpp_t *lpp, double *values, int begin, int end) { - int i; - if (lpp->sol_state < feasible) - return lpp->sol_state; - /* here we are feasible or optimal */ - for (i=0; ivars[begin+i]->value; - return lpp->sol_state; -} - -void lpp_dump(lpp_t *lpp, const char *filename) { - FILE *out = fopen(filename, "wt"); - mps_write_mps(lpp, s_mps_fixed, out); - fclose(out); -} diff --git a/ir/be/lpp.h b/ir/be/lpp.h deleted file mode 100644 index 87b013c27..000000000 --- a/ir/be/lpp.h +++ /dev/null @@ -1,156 +0,0 @@ -/** - * Author: Daniel Grund - * Date: 16.05.2005 - * Copyright: (c) Universitaet Karlsruhe - * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. - * - * Interface for specifying an milp. Does not define a solution method. - */ -#ifndef _LPP_H -#define _LPP_H - -#include -#include "set.h" -#include "sp_matrix.h" - -typedef enum _opt_t {minimize, maximize} opt_t; -typedef enum _cst_t {objective=0, equal=1, less=2, greater=3} cst_t; -typedef enum _var_t {invalid=0, rhs=1, continous=2, binary=3} var_t; -typedef enum _sol_state_t {unknown=0, infeasible=1, inforunb=2, unbounded=3, feasible=4, optimal=5} sol_state_t; -typedef enum _value_kind_t {none=0, value_start, value_solution} value_kind_t; - -typedef struct _name_t name_t; -struct _name_t { - char *name; /**< the name of the var/constraint supplied by user */ - int nr; /**< the col/row number in the matrix */ - value_kind_t value_kind; - double value; - union _type { - var_t var_type; - cst_t cst_type; - } type; -}; - -typedef struct _lpp_t { - /* The problem data */ - char *name; /**< A textual name for this problem */ - opt_t opt_type; /**< Optimization direction */ - sp_matrix_t *m; /**< The matrix holding objective, constraints and rhs */ - - /* Cst/Var to Nr mapping */ - set *cst2nr; /**< Holds name_t's for constraints */ - set *var2nr; /**< Holds name_t's for variables */ - - /* Nr to Cst/Var mapping */ - int cst_size, var_size; /**< Size of the csts/vars-arrays below */ - int cst_next, var_next; /**< Next free position in arrays below */ - name_t **csts; /**< Pointers to the elements in the cst2nr set */ - name_t **vars; /**< Pointers to the elements in the var2nr set */ - - /* Solution stuff */ - sol_state_t sol_state; - double sol_time; /**< Time in seconds */ - unsigned iterations; - - char *error; - unsigned next_name_number; -} lpp_t; - -#define ERR_NAME_NOT_ALLOWED -2 - -/** - * Creates a new problem. Optimization type is minimize or maximize. - * Implicit row with name "obj" is inserted. - * Implicit col with name "rhs" is inserted. - */ -lpp_t *new_lpp(const char *name, opt_t opt_type); - -void free_lpp(lpp_t *lpp); - -/** - * Adds a constraint to a problem. If a constraint with the same name already - * exists nothing is altered, and the index of the existing entry is returned. - * @param cst_name The name of the constraint (1st char only alpha-numeric!). If NULL, a default name will be used. - * @param cst_type The type of constraint: objective, equality, less-or-equal, greater-or-equal - * @param rhs The right hand side value to set for this constraint. - * @return The (new or existing) index of the constraint - */ -int lpp_add_cst(lpp_t *lpp, char *cst_name, cst_t cst_type, double rhs); - -/** - * Returns the internal index of a constraint. - * @param cst_name The name of the constraint - * @return The internal index of constraint @p cst_name or -1 if it does not exist. - */ -int lpp_get_cst_idx(lpp_t *lpp, char *cst_name); - -/** - * Returns the name of a constraint. - * @param index The internal index of a constraint. - * @param buf A buffer to hold the name of the constraint - * @param buf_size Size of the buffer - */ -void lpp_get_cst_name(lpp_t *lpp, int index, char *buf, size_t buf_size); - -/** - * Adds a variable to a problem. If a variable with the same name already - * exists nothing is altered, and the index of the existing entry is returned. - * @param var_name The name of the constraint (1st char only alpha-numeric!). If NULL, a default name will be used. - * @param var_type The type of variable: real, binary - * @param obj The objactive value coefficient for this variable. - * @return The (new or existing) index of the variable - * - * NOTE: common integer or semi-continous vars are not (yet) implemented - */ -int lpp_add_var(lpp_t *lpp, char *var_name, var_t var_type, double obj); - -/** - * Returns the internal index of a variable. - * @param cst_name The name of the variable - * @return The internal index of variable @p var_name or -1 if it does not exist. - */ -int lpp_get_var_idx(lpp_t *lpp, char *var_name); - -/** - * Returns the name of a variable. - * @param index The internal index of a variable. - * @param buf A buffer to hold the name of the variable - * @param buf_size Size of the buffer - */ -void lpp_get_var_name(lpp_t *lpp, int index, char *buf, size_t buf_size); - -/** - * Sets the factor of the variable @p var_name in constraint @p cst_name to @p value. - * @return -1 if constraint or variable name does not exist. - * 0 otherwise - */ -int lpp_set_factor(lpp_t *lpp, char *cst_name, char *var_name, double value); - -/** - * Same as lpp_set_factor but uses the internal indices instead of names. - * @return -1 if an index was invalid - * 0 otherwise - */ -int lpp_set_factor_fast(lpp_t *lpp, int cst_idx, int var_idx, double value); - -/** - * Set a starting value for a var. - * @param var_idx The index of the variable to set the value for. - * @param value The value to set. - */ -void lpp_set_start_value(lpp_t *lpp, int var_idx, double value); - -/** - * @return The solution values of the variables from index begin to index end. - */ -sol_state_t lpp_get_solution(lpp_t *lpp, double *values, int begin, int end); - -/** - * Dumps the lpp into a file with name @p filename in MPS-format - */ -void lpp_dump(lpp_t *lpp, const char *filename); - -#define lpp_get_iter_cnt(lpp) ((lpp)->iterations) -#define lpp_get_sol_time(lpp) ((lpp)->sol_time) - -#endif diff --git a/ir/be/lpp_local.c b/ir/be/lpp_local.c deleted file mode 100644 index 362be3ee0..000000000 --- a/ir/be/lpp_local.c +++ /dev/null @@ -1,207 +0,0 @@ -/** - * Author: Daniel Grund - * Date: 02.06.2005 - * Copyright: (c) Universitaet Karlsruhe - * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. - */ -#undef HAVE_CPLEX - -#ifdef HAVE_CONFIG_H -#include "config.h" -#endif -#include "lpp_local.h" -#include - -#ifdef HAVE_CPLEX -#include -#include - -#include "xmalloc.h" -#include "assert.h" -#include "sp_matrix.h" -#include "ilcplex/cplex.h" - -#undef LOGFILE //stdout -#define TIME_LIMIT 5*60 /* in sec. 0 for none */ - -static char cpx_cst_encoding[4] = {'?', 'E', 'L', 'G'}; -static char cpx_var_encoding[4] = {'?', '?', 'C', 'B'}; - -typedef struct _cpx_t { - lpp_t *lpp; - CPXENVptr env; - CPXLPptr prob; - int status; - char buf[1024]; -} cpx_t; - -static INLINE void chk_cpx_err(cpx_t *cpx) { - if (cpx->status) { - if (CPXgeterrorstring(cpx->env, cpx->status, cpx->buf)) - printf(cpx->buf); - else - printf("Unknown CPLEX error\n"); - assert(0); - } -} - -static cpx_t *new_cpx(lpp_t *lpp) { - cpx_t *cpx = xcalloc(1, sizeof(*cpx)); - cpx->lpp = lpp; - cpx->env = CPXopenCPLEX(&cpx->status); - chk_cpx_err(cpx); - cpx->prob = CPXcreateprob(cpx->env, &cpx->status, lpp->name); - chk_cpx_err(cpx); - CPXchgobjsen(cpx->env, cpx->prob, (lpp->opt_type == minimize)?1:-1); - chk_cpx_err(cpx); -#ifdef LOGFILE - if (CPXsetlogfile(cpx->env, LOGFILE)) - assert(0 && "Could not set logfile"); -#endif - return cpx; -} - -static void free_cpx(cpx_t *cpx) { - CPXfreeprob(cpx->env, &cpx->prob); - CPXcloseCPLEX(&cpx->env); - free(cpx); -} - -static void cpx_construct(cpx_t *cpx) { - const matrix_elem_t *elem; - int i, o, sv_cnt, numcols, numrows, numentries, objsen, *matbeg, *matcnt, *matind, *indices; - double *obj, *rhs, *matval, *lb, *ub, *startv; - char *sense, *vartype, **colname; - lpp_t *lpp = cpx->lpp; - - numcols = lpp->var_next-1; - numrows = lpp->cst_next-1; - numentries = matrix_get_entries(lpp->m); - objsen = lpp->opt_type == minimize ? 1 : -1; - - obj = alloca(numcols * sizeof(*obj)); - lb = alloca(numcols * sizeof(*lb)); - ub = alloca(numcols * sizeof(*ub)); - colname = alloca(numcols * sizeof(*colname)); - vartype = alloca(numcols * sizeof(*vartype)); - indices = alloca(numcols * sizeof(*indices)); - startv = alloca(numcols * sizeof(*startv)); - matbeg = alloca(numcols * sizeof(*matbeg)); - matcnt = alloca(numcols * sizeof(*matcnt)); - matind = alloca(numentries * sizeof(*matind)); - matval = alloca(numentries * sizeof(*matval)); - rhs = alloca(numrows * sizeof(*rhs)); - sense = alloca(numrows * sizeof(*sense)); - - o = 0; - sv_cnt = 0; - for(i=0; ivars[1+i]; - obj[i] = matrix_get(lpp->m, 0, 1+i); - lb[i] = 0.0; - ub[i] = CPX_INFBOUND; - colname[i] = curr_var->name; - vartype[i] = cpx_var_encoding[curr_var->type.var_type]; - if(curr_var->value_kind == value_start) { - indices[sv_cnt] = i; - startv[sv_cnt++] = curr_var->value; - } - matbeg[i] = o; - matcnt[i] = 0; - matrix_foreach_in_col(lpp->m, 1+i, elem) { - if (elem->row == 0) - continue; - matind[o] = elem->row-1; - matval[o] = elem->val; - matcnt[i]++; - o++; - } - } - - for(i=0; im, 1+i, 0); - sense[i] = cpx_cst_encoding[lpp->csts[1+i]->type.cst_type]; - } - - cpx->status = CPXcopylpwnames(cpx->env, cpx->prob, - numcols, numrows, objsen, - obj, rhs, sense, - matbeg, matcnt, matind, matval, - lb, ub, NULL, - colname, NULL); - chk_cpx_err(cpx); - cpx->status = CPXcopyctype(cpx->env, cpx->prob, vartype); - chk_cpx_err(cpx); - cpx->status = CPXcopymipstart(cpx->env, cpx->prob, sv_cnt, indices, startv); - chk_cpx_err(cpx); -} - -static void cpx_solve(cpx_t *cpx) { - int i, CPX_state, numcols; - double *values; - struct timeval tvb, tva; - - lpp_t *lpp = cpx->lpp; - numcols = CPXgetnumcols(cpx->env, cpx->prob); - chk_cpx_err(cpx); - - /* set performance parameters */ - CPXsetintparam(cpx->env, CPX_PARAM_MIPSTART, CPX_ON); - CPXsetintparam(cpx->env, CPX_PARAM_MIPEMPHASIS, CPX_MIPEMPHASIS_BESTBOUND); - CPXsetintparam(cpx->env, CPX_PARAM_VARSEL, CPX_VARSEL_STRONG); - if (TIME_LIMIT) - CPXsetdblparam(cpx->env, CPX_PARAM_TILIM, TIME_LIMIT); - - /* solve */ - gettimeofday(&tvb, NULL); - cpx->status = CPXmipopt(cpx->env, cpx->prob); - gettimeofday(&tva, NULL); - chk_cpx_err(cpx); - - /* get solution status */ - CPX_state = CPXgetstat(cpx->env, cpx->prob); - switch (CPX_state) { - case CPXMIP_INFEASIBLE: - case CPX_STAT_INFEASIBLE: lpp->sol_state = infeasible; break; - case CPXMIP_INForUNBD: - case CPX_STAT_INForUNBD: lpp->sol_state = inforunb; break; - case CPXMIP_UNBOUNDED: - case CPX_STAT_UNBOUNDED: lpp->sol_state = unbounded; break; - case CPXMIP_ABORT_FEAS: - case CPXMIP_FAIL_FEAS: - case CPXMIP_MEM_LIM_FEAS: - case CPXMIP_NODE_LIM_FEAS: - case CPXMIP_TIME_LIM_FEAS: lpp->sol_state = feasible; break; - case CPXMIP_OPTIMAL: - case CPX_STAT_OPTIMAL: lpp->sol_state = optimal; break; - default: lpp->sol_state = unknown; - } - assert(lpp->sol_state == optimal || lpp->sol_state == feasible); - - /* get variable solution values */ - values = alloca(numcols * sizeof(*values)); - CPXgetmipx(cpx->env, cpx->prob, values, 0, numcols-1); - chk_cpx_err(cpx); - for(i=0; ivars[1+i]->value = values[i]; - lpp->vars[1+i]->value_kind = value_solution; - } - - /* get some statistics */ - lpp->sol_time = tva.tv_sec - tvb.tv_sec; - lpp->iterations = CPXgetmipitcnt(cpx->env, cpx->prob); -} - -void lpp_solve_local(lpp_t *lpp) { - cpx_t *cpx = new_cpx(lpp); - cpx_construct(cpx); - cpx_solve(cpx); - free_cpx(cpx); -} - -#else - -void lpp_solve_local(lpp_t *lpp) { - fprintf(stderr, "CPLEX not available!\n"); -} -#endif diff --git a/ir/be/lpp_local.h b/ir/be/lpp_local.h deleted file mode 100644 index 0bdc5107d..000000000 --- a/ir/be/lpp_local.h +++ /dev/null @@ -1,15 +0,0 @@ -/** - * Author: Daniel Grund - * Date: 02.06.2005 - * Copyright: (c) Universitaet Karlsruhe - * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. - */ - -#ifndef _LPP_LOCAL_H_ -#define _LPP_LOCAL_H_ - -#include "lpp.h" - -void lpp_solve_local(lpp_t *lpp); - -#endif /*_LPP_LOCAL_H_*/ diff --git a/ir/be/lpp_remote.c b/ir/be/lpp_remote.c deleted file mode 100644 index 63583b8c7..000000000 --- a/ir/be/lpp_remote.c +++ /dev/null @@ -1,174 +0,0 @@ -/** - * Author: Daniel Grund - * Date: 02.06.2005 - * Copyright: (c) Universitaet Karlsruhe - * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. - */ -#ifdef HAVE_CONFIG_H -#include "config.h" -#endif - -#include -#include -#include -#include -#include - -#include "lpp_remote.h" -#include "xmalloc.h" -#include "assert.h" -#include "mps.h" - -/* CPLEX-account related stuff */ -#define DELETE_FILES /**< deletes all dumped files after use. Files on server are always deleted. */ -#define SSH_USER_HOST "kb61@sp-smp.rz.uni-karlsruhe.de" -#define SSH_PASSWD_FILE "/ben/daniel/.smppw" -#define EXPECT_FILENAME "runme" /* name of the expect-script */ - -static INLINE FILE *ffopen(const char *base, const char *ext, const char *mode) { - FILE *out; - char buf[1024]; - - snprintf(buf, sizeof(buf), "%s.%s", base, ext); - if (! (out = fopen(buf, mode))) { - fprintf(stderr, "Cannot open file %s in mode %s\n", buf, mode); - return NULL; - } - return out; -} - -static void lpp_write_cmd(lpp_t *lpp) { - FILE *out = ffopen(lpp->name, "cmd", "wt"); - fprintf(out, "set logfile %s.sol\n", lpp->name); - fprintf(out, "set mip strategy mipstart 1\n"); - fprintf(out, "set mip emphasis 3\n"); /* moving best bound */ - fprintf(out, "set mip strategy variableselect 3\n"); /* strong branching */ - fprintf(out, "read %s.mps\n", lpp->name); - fprintf(out, "read %s.mst\n", lpp->name); - fprintf(out, "optimize\n"); - fprintf(out, "display solution variables -\n"); - fprintf(out, "quit\n"); - fclose(out); -} - -static void lpp_write_exp(lpp_t *lpp) { - FILE *pwfile, *out; - char passwd[128]; - - pwfile = fopen(SSH_PASSWD_FILE, "rt"); - fgets(passwd, sizeof(passwd), pwfile); - fclose(pwfile); - - out = ffopen(EXPECT_FILENAME, "exp", "wt"); - fprintf(out, "#! /usr/bin/expect\n"); - fprintf(out, "spawn scp %s.mps %s.mst %s.cmd %s:\n", lpp->name, lpp->name, lpp->name, SSH_USER_HOST); /* copy problem files */ - fprintf(out, "expect \"word:\"\nsend \"%s\\n\"\ninteract\n", passwd); - - fprintf(out, "spawn ssh %s \"./cplex90 < %s.cmd\"\n", SSH_USER_HOST, lpp->name); /* solve */ - fprintf(out, "expect \"word:\"\nsend \"%s\\n\"\ninteract\n", passwd); - - fprintf(out, "spawn scp %s:%s.sol .\n", SSH_USER_HOST, lpp->name); /*copy back solution */ - fprintf(out, "expect \"word:\"\nsend \"%s\\n\"\ninteract\n", passwd); - - fprintf(out, "spawn ssh %s ./dell\n", SSH_USER_HOST); /* clean files on server */ - fprintf(out, "expect \"word:\"\nsend \"%s\\n\"\ninteract\n", passwd); - fclose(out); -} - -static void lpp_read_solution(lpp_t *lpp) { - FILE *in; - double sol_time; - unsigned iter; - int vars_section = 0; - char var_name[128]; - double var_value; - - if (!(in = ffopen(lpp->name, "sol", "rt"))) { - lpp->sol_state = unknown; - return; - } - while (!feof(in)) { - char buf[1024]; - fgets(buf, sizeof(buf), in); - - /* error and solution state */ - if (!strncmp(buf, "CPLEX Error", 11)) - lpp->error = xstrdup(buf); - else if (!strncmp(buf, "Warning:", 8)) - lpp->error = xstrdup(buf); - else if (!strncmp(buf, "Integer optimal solution:", 25)) - lpp->sol_state = optimal; - else if (!strcmp(buf, "No integer feasible solution exists.")) - lpp->sol_state = infeasible; - else if (!strcmp(buf, "Error termination, integer feasible:")) - lpp->sol_state = feasible; - /* stats */ - else if (sscanf(buf, "Solution time = %lg sec. Iterations = %u", &sol_time, &iter) == 2) { - lpp->sol_time = sol_time; - lpp->iterations = iter; - } - /* variable values */ - else if(!strcmp(buf, "Variable Name Solution Value")) { - int i; - vars_section = 1; - for(i=0; ivar_next; ++i) { - name_t *var = lpp->vars[i]; - var->value = 0; - var->value_kind = value_solution; - } - } - else if(!strncmp(buf, "All other var", 13)) - vars_section = 0; - else if (vars_section) { - if (sscanf(buf, "%s %lg", var_name, &var_value) == 2) - lpp->vars[lpp_get_var_idx(lpp, var_name)]->value = var_value; - else - assert(0 && "There should be variables to read in!"); - } - } - fclose(in); - if (lpp->error) { - printf("\n%s\n", lpp->error); - assert(0); - } -} - -#ifdef DELETE_FILES -static void lpp_delete_files(lpp_t *lpp) { - char buf[1024]; - int end = snprintf(buf, sizeof(buf), "%s", lpp->name); - - snprintf(buf+end, sizeof(buf)-end, ".mps"); - remove(buf); - snprintf(buf+end, sizeof(buf)-end, ".mst"); - remove(buf); - snprintf(buf+end, sizeof(buf)-end, ".cmd"); - remove(buf); - snprintf(buf+end, sizeof(buf)-end, ".sol"); - remove(buf); - remove(EXPECT_FILENAME ".exp"); -} -#endif - -void lpp_solve_remote(lpp_t *lpp) { - FILE *out; - out = ffopen(lpp->name, "mps", "wt"); - mps_write_mps(lpp, s_mps_free, out); - fclose(out); - - out = ffopen(lpp->name, "mst", "wt"); - mps_write_mst(lpp, s_mps_free, out); - fclose(out); - - lpp_write_cmd(lpp); - lpp_write_exp(lpp); - - /* call the expect script */ - chmod(EXPECT_FILENAME ".exp", 0700); - system(EXPECT_FILENAME ".exp"); - - lpp_read_solution(lpp); -#ifdef DELETE_FILES - lpp_delete_files(lpp); -#endif -} diff --git a/ir/be/lpp_remote.h b/ir/be/lpp_remote.h deleted file mode 100644 index 4bde4045c..000000000 --- a/ir/be/lpp_remote.h +++ /dev/null @@ -1,15 +0,0 @@ -/** - * Author: Daniel Grund - * Date: 02.06.2005 - * Copyright: (c) Universitaet Karlsruhe - * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. - */ - -#ifndef _LPP_REMOTE_H_ -#define _LPP_REMOTE_H_ - -#include "lpp.h" - -void lpp_solve_remote(lpp_t *lpp); - -#endif /*_LPP_REMOTE_H_*/ diff --git a/ir/be/mps.c b/ir/be/mps.c deleted file mode 100644 index ddc2ee974..000000000 --- a/ir/be/mps.c +++ /dev/null @@ -1,164 +0,0 @@ -/** - * Author: Daniel Grund - * Date: 02.06.2005 - * Copyright: (c) Universitaet Karlsruhe - * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. - */ - -#ifdef HAVE_CONFIG_H -#include "config.h" -#endif -#include -#include -#include "mps.h" - -/** - * These must comply to the enum cst_t in lpp.h - */ -static char *mps_cst_encoding[4] = {"N", "E", "L", "G"}; - -/** - * Diffferent line styles which can be used in a mps file - */ -typedef enum _mps_line_t {l_raw, - l_ind_name, l_ind_objs, l_ind_rows, l_ind_cols, l_ind_rhs, l_ind_end, - l_data_row, l_data_col1, l_data_col2, l_data_mst, l_marker} mps_line_t; - -static void mps_write_line(FILE *out, style_t style, mps_line_t line_type, ...) { - va_list args; - char *fmt = ""; - - assert(style == s_mps_fixed || style == s_mps_free); - va_start(args, line_type); - - if (style == s_mps_fixed) { - /* white spaces are important! */ - switch (line_type) { - case l_raw: fmt = "%s\n"; break; - case l_ind_name: fmt = "NAME %s\n"; break; - case l_ind_objs: fmt = "OBJSENSE\n"; break; - case l_ind_rows: fmt = "ROWS\n"; break; - case l_ind_cols: fmt = "COLUMNS\n"; break; - case l_ind_rhs: fmt = "RHS\n"; break; - case l_ind_end: fmt = "ENDATA\n"; break; - case l_data_row: fmt = " %-2s %-8s\n"; break; /* Field 1-2 */ - case l_data_col1: fmt = " %-8s %-8s %12g\n"; break; /* Field 2-4 */ - case l_data_col2: fmt = " %-8s %-8s %12g %-8s %12g\n"; break; /* Field 2-6 */ - case l_data_mst: fmt = " %-8s %12g\n"; break; /* Field 3-4 */ - case l_marker: fmt = " M%-7d 'MARKER' '%s'\n"; break; /* Field 2,3,5 */ - default: assert(0); - } - } else { - switch (line_type) { - case l_raw: fmt = "%s\n"; break; - case l_ind_name: fmt = "NAME %s\n"; break; - case l_ind_objs: fmt = "OBJSENSE\n"; break; - case l_ind_rows: fmt = "ROWS\n"; break; - case l_ind_cols: fmt = "COLUMNS\n"; break; - case l_ind_rhs: fmt = "RHS\n"; break; - case l_ind_end: fmt = "ENDATA\n"; break; - case l_data_row: fmt = " %s\t%s\n"; break; - case l_data_col1: fmt = " %s\t%s\t%g\n"; break; - case l_data_col2: fmt = " %s\t%s\t%g\t%s\t%g\n"; break; - case l_data_mst: fmt = " %s\t%g\n"; break; - case l_marker: fmt = " M%d\t'MARKER'\t'%s'\n"; break; - default: assert(0); - } - } - - vfprintf(out, fmt, args); - va_end(args); -} - -static INLINE int mps_insert_markers(FILE *out, style_t style, var_t curr, var_t last, int marker_nr) { - assert(style == s_mps_fixed || style == s_mps_free); - if (last != curr) { - /* print end-marker for last */ - if (last == binary) - mps_write_line(out, style, l_marker, marker_nr++, "INTEND"); - - /* print begin-marker for curr */ - if (curr == binary) - mps_write_line(out, style, l_marker, marker_nr++, "INTORG"); - } - return marker_nr; -} - -void mps_write_mps(lpp_t *lpp, style_t style, FILE *out) { - int i, count, marker_nr = 0; - const name_t *curr; - const matrix_elem_t *elem, *before = NULL; - var_t last_type; - assert(style == s_mps_fixed || style == s_mps_free); - - /* NAME */ - mps_write_line(out, style, l_ind_name, lpp->name); - - /* OBJSENSE */ - if (lpp->opt_type == maximize) { - mps_write_line(out, style, l_ind_objs); - mps_write_line(out, style, l_raw, " MAX"); - } - - /* ROWS */ - mps_write_line(out, style, l_ind_rows); - for(i=0; icst_next; ++i) { - curr = lpp->csts[i]; - mps_write_line(out, style, l_data_row, mps_cst_encoding[curr->type.cst_type], curr->name); - } - - /* COLUMNS */ - mps_write_line(out, style, l_ind_cols); - last_type = invalid; - for(i=1; ivar_next; ++i) { /* column 0 is rhs */ - curr = lpp->vars[i]; - - /* markers */ - marker_nr = mps_insert_markers(out, style, curr->type.var_type, last_type, marker_nr); - last_type = curr->type.var_type; - - /* participation in constraints */ - count = 0; - matrix_foreach_in_col(lpp->m, curr->nr, elem) { - if (count == 0) { - before = elem; - count = 1; - } else { - mps_write_line(out, style, l_data_col2, curr->name, lpp->csts[before->row]->name, (double)before->val, lpp->csts[elem->row]->name, (double)elem->val); - count = 0; - } - } - if (count == 1) - mps_write_line(out, style, l_data_col1, curr->name, lpp->csts[before->row]->name, (double)before->val); - } - mps_insert_markers(out, style, invalid, last_type, marker_nr); /* potential end-marker */ - - /* RHS */ - mps_write_line(out, style, l_ind_rhs); - count = 0; - matrix_foreach_in_col(lpp->m, 0, elem) { - if (count == 0) { - before = elem; - count = 1; - } else { - mps_write_line(out, style, l_data_col2, "rhs", lpp->csts[before->row]->name, (double)before->val, lpp->csts[elem->row]->name, (double)elem->val); - count = 0; - } - } - if (count == 1) - mps_write_line(out, style, l_data_col1, "rhs", lpp->csts[before->row]->name, (double)before->val); - - /* ENDATA */ - mps_write_line(out, style, l_ind_end); -} - -void mps_write_mst(lpp_t *lpp, style_t style, FILE *out) { - int i; - mps_write_line(out, style, l_ind_name, ""); - for (i=0; ivar_next; ++i) { - const name_t *var = lpp->vars[i]; - if (var->value_kind == value_start) - mps_write_line(out, style, l_data_mst, var->name, (double)var->value); - } - mps_write_line(out, style, l_ind_end); -} diff --git a/ir/be/mps.h b/ir/be/mps.h deleted file mode 100644 index ffeae3a45..000000000 --- a/ir/be/mps.h +++ /dev/null @@ -1,35 +0,0 @@ -/** - * Author: Daniel Grund - * Date: 02.06.2005 - * Copyright: (c) Universitaet Karlsruhe - * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. - */ - -#ifndef _MPS_H_ -#define _MPS_H_ - -#include -#include "lpp.h" - -/** - * Two styles of mps files - * - * s_mps_fixed: mps where spaces are allowed in identifiers - * and all things have a fixed column... :-0 - * s_mps_free: mps where whitespace is a seperator :-) - */ -typedef enum _style_t {s_mps_fixed, s_mps_free} style_t; - -/** - * Writes the description of a lp problem object (lpp) - * to the stream out, using the specified style. - */ -void mps_write_mps(lpp_t *lpp, style_t style, FILE *out); - -/** - * Writes the start values of a lp problem object (lpp) - * to the stream out, using the specified style. - */ -void mps_write_mst(lpp_t *lpp, style_t style, FILE *out); - -#endif /*_MPS_H_*/ diff --git a/ir/be/sp_matrix.c b/ir/be/sp_matrix.c deleted file mode 100644 index d62e216df..000000000 --- a/ir/be/sp_matrix.c +++ /dev/null @@ -1,462 +0,0 @@ -/** - * Author: Daniel Grund - * Date: 07.04.2005 - * Copyright: (c) Universitaet Karlsruhe - * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. - - * Sparse matrix storage with linked lists for rows and cols. - */ - -#ifdef HAVE_CONFIG_H -#include "config.h" -#endif - -#ifdef HAVE_ALLOCA_H -#include -#endif -#ifdef HAVE_MALLOC_H -#include -#endif - -#include -#include -#include -#include "sp_matrix.h" -#include "list.h" -#include "bitset.h" - -#define MAX(a,b) ((a= maxrow and colc >= maxcol hold. */ - int rowc, colc; - /* number of entries */ - int entries; - /* arrays of list_head* as entry-points to rows and cols */ - struct list_head **rows, **cols; - /* for iteration: first is to remember start-point; - * last was returned just before - * next is used in case last was removed from list */ - iter_direction_t dir; - struct list_head *first, *last, *next; - int iter_row; /* used for iteration over all elements */ -}; - -#define _offsetof(type,member) ((char *) &(((type *) 0)->member) - (char *) 0) -#define _container_of(ptr,type,member) ((type *) ((char *) (ptr) - _offsetof(type, member))) -#define is_empty_row(row) (row>m->maxrow || list_empty(m->rows[row])) -#define is_empty_col(col) (col>m->maxcol || list_empty(m->cols[col])) -#define list_entry_by_col(h) (&list_entry(h, entry_t, col_chain)->e) -#define list_entry_by_row(h) (&list_entry(h, entry_t, row_chain)->e) - -/** - * Returns the new size for an array of size old_size, - * which must at least store an entry at position min. - */ -static INLINE int _m_new_size(int old_size, int min) { - int bits = 0; - assert(min>=old_size); - while (min>0) { - min >>= 1; - bits++; - } - assert(bits < sizeof(min)*8-1); - return 1 << bits; -} - -/** - * Allocates space for @p count entries in the rows array and - * inititializes all entries from @p start to the end. - */ -static INLINE void _m_alloc_row(sp_matrix_t *m, int start, int count) { - int p; - m->rowc = count; - m->rows = realloc(m->rows, m->rowc * sizeof(*m->rows)); - assert(m->rows); - for (p=start; prowc; ++p) { - m->rows[p] = malloc(sizeof(*m->rows[p])); - assert(m->rows[p]); - INIT_LIST_HEAD(m->rows[p]); - } -} - -/** - * Allocates space for @p count entries in the cols array and - * inititializes all entries from @p start to the end. - */ -static INLINE void _m_alloc_col(sp_matrix_t *m, int start, int count) { - int p; - m->colc = count; - m->cols = realloc(m->cols, m->colc * sizeof(*m->cols)); - assert(m->cols); - for (p=start; pcolc; ++p) { - m->cols[p] = malloc(sizeof(*m->cols[p])); - assert(m->cols[p]); - INIT_LIST_HEAD(m->cols[p]); - } -} - -/** - * Searches in row @p row for the matrix element m[row, col]. - * @return If the element exists: Element m[row, col] and @p prev points to the list_head in the entry_t holding the element. - * Else: NULL and @p prev points to the list_head after which the element would be inserted. - */ -static INLINE matrix_elem_t *_m_search_in_row(const sp_matrix_t *m, int row, int col, struct list_head **prev) { - struct list_head *start; - start = *prev = m->rows[row]; - while ((*prev)->next != start && list_entry_by_row((*prev)->next)->col <= col) - *prev = (*prev)->next; - if (*prev != start) { - matrix_elem_t *me = list_entry_by_row(*prev); - if (me->row == row && me->col == col) - return me; - } - return NULL; -} - -/** - * Searches in col @p col for the matrix element m[row, col]. - * @return If the element exists: Element m[row, col] and @p prev points to the list_head in the entry_t holding the element. - * Else: NULL and @p prev points to the list_head after which the element would be inserted. - */ -static INLINE matrix_elem_t *_m_search_in_col(const sp_matrix_t *m, int row, int col, struct list_head **prev) { - struct list_head *start; - start = *prev = m->cols[col]; - while ((*prev)->next != start && list_entry_by_col((*prev)->next)->row <= row) - *prev = (*prev)->next; - if (*prev != start) { - matrix_elem_t *me = list_entry_by_col(*prev); - if (me->row == row && me->col == col) - return me; - } - return NULL; -} - -sp_matrix_t *new_matrix(int row_init, int col_init) { - sp_matrix_t *res = calloc(1, sizeof(*res)); - res->maxrow = -1; - res->maxcol = -1; - _m_alloc_row(res, 0, MAX(0, row_init)); - _m_alloc_col(res, 0, MAX(0, col_init)); - return res; -} - -void del_matrix(sp_matrix_t *m) { - int i; - entry_t *e, *tmp; - - for (i=0; irowc; ++i) { - list_for_each_entry_safe(entry_t, e, tmp, m->rows[i], row_chain) - free(e); - free(m->rows[i]); - } - for (i=0; icolc; ++i) - free(m->cols[i]); - free(m->rows); - free(m->cols); - free(m); -} - -void matrix_set(sp_matrix_t *m, int row, int col, matrix_type val) { - matrix_elem_t *me = NULL; - entry_t *entr; - struct list_head *leftof, *above; - - /* if necessary enlarge the matrix */ - if (row>m->maxrow) { - m->maxrow = row; - if (row>=m->rowc) - _m_alloc_row(m, m->rowc, _m_new_size(m->rowc, row)); - } - if (col>m->maxcol) { - m->maxcol = col; - if (col>=m->colc) - _m_alloc_col(m, m->colc, _m_new_size(m->colc, col)); - } - - /* search for existing entry */ - if (m->maxrow < m->maxcol) - me = _m_search_in_col(m, row, col, &above); - else - me = _m_search_in_row(m, row, col, &leftof); - - /* if it exists, set the value and return */ - if (me) { - if (val != 0) { - me->val = val; - } else { - entr = _container_of(me, entry_t, e); - list_del(&entr->row_chain); - list_del(&entr->col_chain); - free(entr); - m->entries--; - } - return; - } - - /* if it does not exist and 0 should be set just quit */ - if (val == 0) - return; - - /* if it does not exist and val != 0 search the other direction */ - if (m->maxrow >= m->maxcol) - _m_search_in_col(m, row, col, &above); - else - _m_search_in_row(m, row, col, &leftof); - /* now leftof and above are the entry_t's prior the new one in each direction */ - - /* insert new entry */ - entr = malloc(sizeof(*entr)); - entr->e.row = row; - entr->e.col = col; - entr->e.val = val; - list_add(&entr->row_chain, leftof); - list_add(&entr->col_chain, above); - m->entries++; -} - -matrix_type matrix_get(const sp_matrix_t *m, int row, int col) { - struct list_head *dummy; - matrix_elem_t *me; - - if (is_empty_row(row) || is_empty_col(col)) - return 0; - - if (m->maxrow < m->maxcol) - me = _m_search_in_col(m, row, col, &dummy); - else - me = _m_search_in_row(m, row, col, &dummy); - - if (me) - assert(me->col == col && me->row == row); - - return me?me->val:0; -} - -int matrix_get_entries(const sp_matrix_t *m) { - return m->entries; -} - -int matrix_get_rowcount(const sp_matrix_t *m) { - return m->maxrow+1; -} - -int matrix_get_colcount(const sp_matrix_t *m) { - return m->maxcol+1; -} - -const matrix_elem_t *matrix_row_first(sp_matrix_t *m, int row) { - if (is_empty_row(row)) - return NULL; - m->dir = right; - m->first = m->rows[row]; - m->last = m->first->next; - m->next = m->last->next; - assert (list_entry_by_row(m->last)->row == row); - return list_entry_by_row(m->last); -} - -const matrix_elem_t *matrix_col_first(sp_matrix_t *m, int col) { - if (is_empty_col(col)) - return NULL; - m->dir = down; - m->first = m->cols[col]; - m->last = m->first->next; - m->next = m->last->next; - assert (list_entry_by_col(m->last)->col == col); - return list_entry_by_col(m->last); -} - -static INLINE const matrix_elem_t *matrix_first_from(sp_matrix_t *m, int startrow) { - const matrix_elem_t *res; - int i; - for (i=startrow; i<=m->maxrow; ++i) - if ((res = matrix_row_first(m, i))) { - m->iter_row = i; - m->dir = all; - return res; - } - return NULL; -} - -const matrix_elem_t *matrix_first(sp_matrix_t *m) { - return matrix_first_from(m, 0); -} - -const matrix_elem_t *matrix_next(sp_matrix_t *m) { - assert(m->last && "Start iteration with matrix_???_first, before calling me!"); - if (!m->last->next) - ; - if (m->next == m->first) { - if (m->dir == all) - return matrix_first_from(m, ++m->iter_row); - else - return NULL; - } - m->last = m->next; - m->next = m->next->next; - if (m->dir == down) - return list_entry_by_col(m->last); - else /* right or all */ - return list_entry_by_row(m->last); -} - -static int cmp_count(const void *e1, const void *e2) { - return (int *)e2 - (int *)e1; -} - -static INLINE void matrix_fill_row(sp_matrix_t *m, int row, bitset_t *fullrow) { - const matrix_elem_t *e; - bitset_set(fullrow, row); - matrix_foreach_in_col(m, row, e) - if (!bitset_is_set(fullrow, e->row)) { - assert(0 == matrix_get(m, e->col, e->row)); - matrix_set(m, e->col, e->row, e->val); - matrix_set(m, e->row, e->col, 0); - } -} - -void matrix_optimize(sp_matrix_t *m) { - int i, size, redo; - int *c; - const matrix_elem_t *e; - bitset_t *fullrow; - - size = MAX(m->maxcol, m->maxrow)+1; - - /* kill all double-entries (Mij and Mji are set) */ - matrix_foreach(m, e) { - int t_val; - - assert(e->row != e->col && "Root has itself as arg. Ok. But the arg (=root) will alwazs have the same color as root"); - t_val = matrix_get(m, e->col, e->row); - if (t_val) { - matrix_set(m, e->col, e->row, 0); - matrix_set(m, e->row, e->col, e->val + t_val); - } - } - - c = alloca(size * sizeof(*c)); - redo = 1; - fullrow = bitset_alloca(size); - /* kill 'all' rows containing only 1 entry */ - while (redo) { - redo = 0; - /* count elements in rows */ - memset(c, 0, size * sizeof(*c)); - matrix_foreach(m, e) - c[e->row]++; - for (i=0; icol] > 0) - matrix_fill_row(m, e->col, fullrow); - else - matrix_fill_row(m, e->row, fullrow); - } - } - } - - - memset(c, 0, size * sizeof(*c)); - matrix_foreach(m, e) - c[e->row]++; - qsort(c, size, sizeof(*c), cmp_count); - - - for (i=0; imaxrow; ++i) { - last_idx = -1; - matrix_foreach_in_row(m, i, e) { - for (o=last_idx+1; ocol; ++o) - fprintf(out, "0"); - fprintf(out, "%f", factor*e->val); - last_idx = e->col; - } - for (o=last_idx+1; o<=m->maxcol; ++o) - fprintf(out, "0"); - fprintf(out, "\n"); - } -} - -void matrix_self_test(int d) { - int i, o; - const matrix_elem_t *e; - sp_matrix_t *m = new_matrix(10, 10); - - for (i=0; ival == i); - i++; - } - assert(!matrix_next(m)); /*iter must finish */ - - i = 0; - matrix_foreach_in_col(m,d-1,e) { - assert(e->val == i); - i += d-1; - } - assert(!matrix_next(m)); - del_matrix(m); - m = new_matrix(16,16); - matrix_set(m, 1,1,9); - matrix_set(m, 1,2,8); - matrix_set(m, 1,3,7); - - matrix_set(m, 1,3,6); - matrix_set(m, 1,2,5); - matrix_set(m, 1,1,4); - i = 1; - matrix_foreach_in_row(m, 1, e) { - assert(e->row == 1 && e->col == i && e->val == i+3); - i++; - } - assert(i == 4); - del_matrix(m); - - m = new_matrix(5,5); - matrix_set(m, 1,1,1); - matrix_set(m, 2,2,2); - matrix_set(m, 3,3,3); - matrix_set(m, 3,5,4); - matrix_set(m, 4,4,5); - matrix_set(m, 5,5,6); - for (i=1, e = matrix_first(m); e; ++i, e=matrix_next(m)) - assert(e->val == i); - assert(i == 7); - matrix_set(m, 1,1,0); - assert(5 == matrix_get_entries(m)); - del_matrix(m); -} diff --git a/ir/be/sp_matrix.h b/ir/be/sp_matrix.h deleted file mode 100644 index d04056d19..000000000 --- a/ir/be/sp_matrix.h +++ /dev/null @@ -1,129 +0,0 @@ -/** - * Author: Daniel Grund - * Date: 07.04.2005 - * Copyright: (c) Universitaet Karlsruhe - * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. - - * Sparse matrix storage with linked lists for rows and cols. - */ - -#ifndef _SP_MATRIX_H -#define _SP_MATRIX_H - -#include - -typedef double matrix_type; - -typedef struct _matrix_elem_t { - int row, col; - matrix_type val; -} matrix_elem_t; - -typedef struct _sp_matrix_t sp_matrix_t; - -/** - * Allocate a new matrix and init internal data for a matrix of size - * row_init X col_init. Matrix cannot grow beyond these init values. - * All elements are initially (implicit) set to 0. - */ -sp_matrix_t *new_matrix(int rows, int cols); - -/** - * Free space used by matrix m - */ -void del_matrix(sp_matrix_t *m); - -/** - * Sets m[row, col] to val - */ -void matrix_set(sp_matrix_t *m, int row, int col, matrix_type val); - -/** - * Returns the value stored in m[row, col]. - */ -matrix_type matrix_get(const sp_matrix_t *m, int row, int col); - -/** - * Returns the number of (not-0-)entries. - */ -int matrix_get_entries(const sp_matrix_t *m); - -/** - * Returns the number of rows in this matrix; the height; the first dimension - */ -int matrix_get_rowcount(const sp_matrix_t *m); - -/** - * Returns the number of cols in this matrix; the width; the second dimension - */ -int matrix_get_rowcount(const sp_matrix_t *m); - -/** - * Start iteration over all matrix elements. Row by row, from top to bottom. - * @return NULL if the matrix is empty, else the first element. - */ -const matrix_elem_t *matrix_first(sp_matrix_t *m); - -/** - * Start iteratation over a row. Elements are returned from left to right. - * @return NULL if row is empty, else the first element. - */ -const matrix_elem_t *matrix_row_first(sp_matrix_t *m, int row); - -/** - * Start iteratation over a column. Elements are returned from top to bottom. - * @return NULL if column is empty, else the first element. - */ -const matrix_elem_t *matrix_col_first(sp_matrix_t *m, int row); - -/** - * @return the next element in iteration order or NULL if iteration is done. - */ -const matrix_elem_t *matrix_next(sp_matrix_t *m); - -/** - * m The matrix - * curr The variable to assign all elements to during iteration - * Save against removal of curr - */ -#define matrix_foreach(m,curr) \ - for (curr = matrix_first(m); curr; curr = matrix_next(m)) - -/** - * m The matrix - * r The row - * curr The variable to assign all elements to during iteration - * Save against removal of curr - */ -#define matrix_foreach_in_row(m,r,curr) \ - for (curr = matrix_row_first(m, r); curr; curr = matrix_next(m)) - -/** - * m The matrix - * c The col - * curr The variable to assign all elements to during iteration - * Save against removal of curr - */ -#define matrix_foreach_in_col(m,c,curr) \ - for (curr = matrix_col_first(m, c); curr; curr = matrix_next(m)) - -/** - * Changes the matrix into an equivalent one with maximal number zero-rows. - * The only equivalence transformation is: - * Adding a constant to Qij and substracting it from Qji - */ -void matrix_optimize(sp_matrix_t *m); - -/** - * Dumps the matrix factor*m to the stream @p out. - * Remark: I dont need spaces between the elements. So feel free to add - * char *seperator to the arguments. - */ -void matrix_dump(sp_matrix_t *m, FILE *out, int factor); - -/** - * Perform a self test with a sqare matrix of dimensions d. - */ -void matrix_self_test(int d); - -#endif -- 2.20.1