X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopyilp.c;h=20bdbc6ad5cb7382ae25061baf261087bad2f738;hb=f804d333c7b5459c3c1a6bfc188ecdc54346be73;hp=b4c0a25992be79232accf24f1754cf80ce5ac895;hpb=0f10ae87e00f6ba9bd58a849a98f23f74321ea0c;p=libfirm diff --git a/ir/be/becopyilp.c b/ir/be/becopyilp.c index b4c0a2599..20bdbc6ad 100644 --- a/ir/be/becopyilp.c +++ b/ir/be/becopyilp.c @@ -1,434 +1,261 @@ /** - * Minimizing copies with an exact algorithm using mixed integer programming (MIP). - * Problem statement as a 'quadratic 0-1 program with linear constraints' with - * n binary variables. Constraints are knapsack (enforce color for each node) and - * cliques of ifg (interference constraints). - * Transformation into a 'mixed integer program' with n binary variables and - * additional 2n real variables. Constraints are the above the transformed - * objective function and 'complementary conditions' for two var classes. - * @author Daniel Grund - * - * NOTE: Unfortunately no good solver is available locally (or even for linking) - * We use CPLEX 9.0 which runs on a machine residing at the Rechenzentrum. - * @date 12.04.2005 + * Author: Daniel Grund + * Date: 17.05.2005 + * Copyright: (c) Universitaet Karlsruhe + * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + * CVS-ID: $Id$ */ +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif +#ifdef HAVE_ALLOCA_H +#include +#endif +#ifdef HAVE_MALLOC_H +#include +#endif +#define PATH_CONSTRAINTS_FOR_CLASSES +#undef PRECOLOR_MAX_CLIQUE +#undef NO_NULL_COLORS +#undef NO_NULL_COLORS_EXTRA_CSTS +#undef NO_NULL_COLORS_WITH_COSTS +#if (defined(NO_NULL_COLORS_EXTRA_CSTS) || defined(NO_NULL_COLORS_WITH_COSTS)) && !defined(NO_NULL_COLORS) +#error Chose your weapon! +#endif + +#include "irprog.h" + +#include +#include +#include +#include +#include "xmalloc.h" +#include "pset.h" +#include "irdom_t.h" +#include "iredges_t.h" +#include "bechordal_t.h" #include "becopyopt.h" #include "becopystat.h" +#include "besched_t.h" +#include "phiclass.h" -#undef DUMP_MATRICES /**< dumps all matrices completely. only recommended for small problems */ -#define DUMP_MILP /**< dumps the problem as Mixed Integer Linear Programming in "CPLEX"-MPS format. NOT fixed-column-MPS. */ -#undef DO_SOLVE /**< solve the MPS output with CPLEX */ -#undef DELETE_FILES /**< deletes all dumped files after use */ - -/* CPLEX-account related stuff */ -#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 */ +#define LPP_HOST "i44pc52" +#define LPP_SOLVER "cplex" -#define DEBUG_LVL 0 //SET_LEVEL_1 +#undef DUMP_MPS static firm_dbg_module_t *dbg = NULL; -#define SLOTS_NUM2POS 256 +#define MAX(a,b) ((anum != ((num2pos_t *)y)->num; -} + const copy_opt_t *co; /** the copy_opt problem */ + /* problem size reduction removing simple nodes */ + struct list_head simplicials; /**< holds all simpl_t's in right order to color*/ + pset *removed; /**< holds all removed simplicial irns */ + /* lp problem */ + lpp_t *curr_lp; /**< points to the problem currently used */ + lpp_t *dilp; /**< problem formulation directly as milp */ +#ifdef NO_NULL_COLORS_EXTRA_CSTS + int first_nnc_cst_idx; /**< the first index of a constraint belonging to no-null-colors stuff*/ +#endif + int first_nnc_var_idx; /**< the first index of a constraint belonging to no-null-colors stuff*/ -/** - * Sets the first position of node with number num to pos. - * See x_name_t *x in _problem_instance_t. - */ -static INLINE void pi_set_first_pos(problem_instance_t *pi, int num, int pos) { - num2pos_t find; - find.num = num; - find.pos = pos; - set_insert(pi->num2pos, &find, sizeof(find), HASH_NUM(num)); -} + int cst_counter, first_x_var, last_x_var; + char buf[32]; + int all_simplicial; + pset *done; +} problem_instance_t; -/** - * Get position by number. (First possible color) - * returns -1 if not found. - */ -static INLINE int pi_get_first_pos(problem_instance_t *pi, int num) { - num2pos_t find, *found; - find.num = num; - found = set_find(pi->num2pos, &find, sizeof(find), HASH_NUM(num)); - if (found) { - assert(pi->x[found->pos].n == num && (found->pos == 0 || pi->x[found->pos-1].n != num) && "pi->num2pos is broken!"); - return found->pos; - } else - return -1; -} +#define is_removed(irn) pset_find_ptr(pi->removed, irn) -/** - * Get position by number and color. - * returns -1 if not found. - */ -static INLINE int pi_get_pos(problem_instance_t *pi, int num, int col) { - num2pos_t find, *found; - find.num = num; - int pos; - found = set_find(pi->num2pos, &find, sizeof(find), HASH_NUM(num)); - if (!found) - return -1; - pos = found->pos; - while (pos < pi->x_dim && pi->x[pos].n == num && pi->x[pos].c < col) - pos++; - - if (pi->x[pos].n == num && pi->x[pos].c == col) - return pos; - else - return -1; -} +#define is_color_possible(irn,color) arch_reg_is_allocatable(get_arch_env(pi->co), irn, -1, arch_register_for_index(pi->co->chordal_env->cls, color)) -#ifdef DUMP_MATRICES -/** - * Dump the raw matrices of the problem to a file for debugging. +/* + * Some stuff for variable name handling. */ -static void pi_dump_matrices(problem_instance_t *pi) { - int i; - FILE *out = ffopen(pi->co->name, "matrix", "wt"); - - DBG((dbg, LEVEL_1, "Dumping raw...\n")); - fprintf(out, "\n\nx-names =\n"); - for (i=0; ix_dim; ++i) - fprintf(out, "%5d %2d\n", pi->x[i].n, pi->x[i].c); - - fprintf(out, "\n\n-Q =\n"); - matrix_dump(pi->Q, out, -1); - - fprintf(out, "\n\nA =\n"); - matrix_dump(pi->A, out, 1); +#define mangle_cst(buf, prefix, nr) \ + snprintf((buf), sizeof(buf), "%c%d", (prefix), (nr)) - fprintf(out, "\n\nB =\n"); - matrix_dump(pi->B, out, 1); +#define mangle_var1(buf, prefix, color) \ + snprintf((buf), sizeof(buf), "%c%d", (prefix), (color)) - fclose(out); -} -#endif +#define mangle_var2(buf, prefix, node_nr, color) \ + snprintf((buf), sizeof(buf), "%c%d_%d", (prefix), (node_nr), (color)) -#ifdef DUMP_MILP -/** - * Dumps an mps file representing the problem. This is NOT the old-style, - * fixed-column format. Some white spaces are important, in general spaces - * are separators, MARKER-lines are used in COLUMN section to define binaries. - */ -//BETTER use last 2 fields in COLUMNS section. See MPS docu for details -static void pi_dump_milp(problem_instance_t *pi) { - int i, max_abs_Qij; - const matrix_elem_t *e; - FILE *out = ffopen(pi->co->name, "milp", "wt"); - - DBG((dbg, LEVEL_1, "Dumping milp...\n")); - max_abs_Qij = pi->maxQij; - if (-pi->minQij > max_abs_Qij) - max_abs_Qij = -pi->minQij; - pi->bigM = pi->A_dim * max_abs_Qij; - DBG((dbg, LEVEL_2, "BigM = %d\n", pi->bigM)); - - matrix_optimize(pi->Q); - bitset_t *good_row = bitset_alloca(pi->x_dim); - for (i=0; ix_dim; ++i) - if (matrix_row_first(pi->Q, i)) - bitset_set(good_row, i); - - fprintf(out, "NAME %s\n", pi->co->name); - - fprintf(out, "ROWS\n"); - fprintf(out, " N obj\n"); - for (i=0; ix_dim; ++i) - if (bitset_is_set(good_row, i)) - fprintf(out, " E cQ%d\n", i); - for (i=0; iA_dim; ++i) - fprintf(out, " E cA%d\n", i); - for (i=0; iB_dim; ++i) - fprintf(out, " L cB%d\n", i); - for (i=0; ix_dim; ++i) - if (bitset_is_set(good_row, i)) - fprintf(out, " L cy%d\n", i); - - fprintf(out, "COLUMNS\n"); - /* the x vars come first */ - /* mark them as binaries */ - fprintf(out, " MARKI0\t'MARKER'\t'INTORG'\n"); - for (i=0; ix_dim; ++i) { - /* participation in objective */ - if (bitset_is_set(good_row, i)) - fprintf(out, " x%d_%d\tobj\t%d\n", pi->x[i].n, pi->x[i].c, -pi->bigM); - /* in Q */ - matrix_foreach_in_col(pi->Q, i, e) - fprintf(out, " x%d_%d\tcQ%d\t%d\n", pi->x[i].n, pi->x[i].c, e->row, e->val); - /* in A */ - matrix_foreach_in_col(pi->A, i, e) - fprintf(out, " x%d_%d\tcA%d\t%d\n", pi->x[i].n, pi->x[i].c, e->row, e->val); - /* in B */ - matrix_foreach_in_col(pi->B, i, e) - fprintf(out, " x%d_%d\tcB%d\t%d\n", pi->x[i].n, pi->x[i].c, e->row, e->val); - /* in y */ - if (bitset_is_set(good_row, i)) - fprintf(out, " x%d_%d\tcy%d\t%d\n", pi->x[i].n, pi->x[i].c, i, 2*pi->bigM); - } +#define mangle_var3(buf, prefix, n1, n2, col) \ + snprintf((buf), sizeof(buf), "%c%d_%d_%d", (prefix), (n1), (n2), (col)) - fprintf(out, " MARKI1\t'MARKER'\t'INTEND'\n"); /* end of marking */ +#define mangle_var_irn(buf, prefix, irn, color) \ + mangle_var2((buf), (prefix), get_irn_graph_nr(irn), (color)) - /* next the s vars */ - for (i=0; ix_dim; ++i) - if (bitset_is_set(good_row, i)) { - /* participation in objective */ - fprintf(out, " s%d_%d\tobj\t%d\n", pi->x[i].n, pi->x[i].c, 1); - /* in Q */ - fprintf(out, " s%d_%d\tcQ%d\t%d\n", pi->x[i].n, pi->x[i].c, i, -1); - } +#define split_var(var, nnr, col) \ + sscanf(var, "x%d_%d", (nnr), (col)) - /* next the y vars */ - for (i=0; ix_dim; ++i) - if (bitset_is_set(good_row, i)) { - /* in Q */ - fprintf(out, " y%d_%d\tcQ%d\t%d\n", pi->x[i].n, pi->x[i].c, i, -1); - /* in y */ - fprintf(out, " y%d_%d\tcy%d\t%d\n", pi->x[i].n, pi->x[i].c, i, 1); - } - fprintf(out, "RHS\n"); - for (i=0; ix_dim; ++i) - if (bitset_is_set(good_row, i)) - fprintf(out, " rhs\tcQ%d\t%d\n", i, -pi->bigM); - for (i=0; iA_dim; ++i) - fprintf(out, " rhs\tcA%d\t%d\n", i, 1); - for (i=0; iB_dim; ++i) - fprintf(out, " rhs\tcB%d\t%d\n", i, 1); - for (i=0; ix_dim; ++i) - if (bitset_is_set(good_row, i)) - fprintf(out, " rhs\tcy%d\t%d\n", i, 2*pi->bigM); - - fprintf(out, "ENDATA\n"); - fclose(out); -} -#endif - -#ifdef DO_SOLVE /** - * Dumps the known solution to a file to make use of it - * as a starting solution respectively as a bound + * Checks if a node is simplicial in the graph + * heeding the already removed nodes. */ -static void pi_dump_start_sol(problem_instance_t *pi) { - int i; - FILE *out = ffopen(pi->co->name, "mst", "wt"); - fprintf(out, "NAME\n"); - for (i=0; ix_dim; ++i) { - int val, n, c; - n = pi->x[i].n; - c = pi->x[i].c; - if (get_irn_color(get_irn_for_graph_nr(pi->co->irg, n)) == c) - val = 1; - else - val = 0; - fprintf(out, " x%d_%d\t%d\n", n, c, val); - } - fprintf(out, "ENDATA\n"); - fclose(out); +static INLINE int pi_is_simplicial(problem_instance_t *pi, const ir_node *ifn) { + int i, o, size = 0; + ir_node **all, *curr; + be_ifg_t *ifg = pi->co->chordal_env->ifg; + void *iter = be_ifg_neighbours_iter_alloca(ifg); + + all = alloca(be_ifg_degree(ifg, ifn) * sizeof(*all)); + + /* get all non-removed neighbors */ + be_ifg_foreach_neighbour(ifg, iter, ifn, curr) + if (!is_removed(curr)) + all[size++] = curr; + + /* check if these form a clique */ + for (i=0; ico->name, "cmd", "wt"); - fprintf(out, "set logfile %s.sol\n", pi->co->name); -#ifdef DUMP_MILP - fprintf(out, "read %s.milp mps\n", pi->co->name); -#endif -#ifdef DUMP_MIQP - fprintf(out, "read %s.miqp mps\n", pi->co->name); -#endif - fprintf(out, "read %s.mst\n", pi->co->name); - fprintf(out, "set mip strategy mipstart 1\n"); - fprintf(out, "set mip emphasis 3\n"); - fprintf(out, "optimize\n"); - fprintf(out, "display solution variables 1-%d\n", pi->x_dim); - fprintf(out, "set logfile cplex.log\n"); - fprintf(out, "quit\n"); - fclose(out); - - /* write expect-file for copying problem to RZ */ - 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.miqp %s.milp %s.mst %s.cmd %s:\n", pi->co->name, pi->co->name, pi->co->name, pi->co->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, pi->co->name); /* solve */ - fprintf(out, "expect \"word:\"\nsend \"%s\\n\"\ninteract\n", passwd); - - fprintf(out, "spawn scp %s:%s.sol .\n", SSH_USER_HOST, pi->co->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); - - /* call the expect script */ - chmod(EXPECT_FILENAME ".exp", 0700); - system(EXPECT_FILENAME ".exp"); +static int irn_cmp(const void *a, const void *b, size_t n) +{ + return a != b; } /** - * Sets the colors of irns according to the values of variables found in the - * output file of the solver. + * Iterative finds and 'removes' from the graph all nodes which are + * simplicial AND not member of a equal-color-wish */ -static void pi_apply_solution(problem_instance_t *pi) { - FILE *in = ffopen(pi->co->name, "sol", "rt"); - - if (!in) - return; - DBG((dbg, LEVEL_1, "Applying solution...\n")); - while (!feof(in)) { - char buf[1024]; - int num = -1, col = -1, val = -1; - - fgets(buf, sizeof(buf), in); - DBG((dbg, LEVEL_3, "Line: %s", buf)); - - if (strcmp(buf, "No integer feasible solution exists.") == 0) - assert(0 && "CPLEX says: No integer feasible solution exists!"); - - if (strcmp(buf, "TODO Out of memory") == 0) {} - -#ifdef DO_STAT - { - /* solution time */ - float sol_time; - int iter; - if (sscanf(buf, "Solution time = %f sec. Iterations = %d", &sol_time, &iter) == 2) { - DBG((dbg, LEVEL_2, " Time: %f Iter: %d\n", sol_time, iter)); - curr_vals[I_ILP_TIME] += 10 * sol_time; - curr_vals[I_ILP_ITER] += iter; +static void pi_find_simplicials(problem_instance_t *pi) { + ir_node *irn; + int redo = 1; + int n_nodes = 0; + const be_ifg_t *ifg = pi->co->chordal_env->ifg; + void *iter = be_ifg_neighbours_iter_alloca(ifg); + + DBG((dbg, LEVEL_2, "Find simlicials...\n")); + + while (redo) { + arch_register_req_t req; + redo = 0; + be_ifg_foreach_node(ifg, iter, irn) { + if (!is_removed(irn) && !is_optimizable(get_arch_env(pi->co), irn, &req) && !is_optimizable_arg(pi->co, irn)) { + if (pi_is_simplicial(pi, irn)) { + simpl_t *s = xmalloc(sizeof(*s)); + s->irn = irn; + list_add(&s->chain, &pi->simplicials); + pset_insert_ptr(pi->removed, irn); + redo = 1; + DBG((dbg, LEVEL_2, " Removed %+F\n", irn)); + } } } -#endif + } - /* variable value */ - if (sscanf(buf, "x%d_%d %d", &num, &col, &val) == 3 && val == 1) { - DBG((dbg, LEVEL_2, " x%d_%d = %d\n", num, col, val)); - set_irn_color(get_irn_for_graph_nr(pi->co->irg, num), col); - } + /* TODO: Count inside the last look */ + be_ifg_foreach_node(ifg, iter, irn) { + n_nodes++; } - fclose(in); + + if (n_nodes == pset_count(pi->removed)) + pi->all_simplicial = 1; } -#endif /* DO_SOLVE */ - -#ifdef DELETE_FILES -static void pi_delete_files(problem_instance_t *pi) { - char buf[1024]; - int end = snprintf(buf, sizeof(buf), "%s", pi->co->name); - DBG((dbg, LEVEL_1, "Deleting files...\n")); -#ifdef DUMP_MATRICES - snprintf(buf+end, sizeof(buf)-end, ".matrix"); - remove(buf); + +#ifdef NO_NULL_COLORS +static void pi_add_constr_no_null_colors(problem_instance_t *pi) { + int cst_counter=0, col, var_idx, cst_idx; + int n_colors = pi->co->chordal_env->cls->n_regs; + char buf[40]; + + for (col = 0; col < n_colors; ++col) { + mangle_var1(buf, 'u', col); +#ifdef NO_NULL_COLORS_WITH_COSTS + var_idx = lpp_add_var(pi->curr_lp, buf, lpp_binary, 1.0 / (double) (1 << (col+1)) ); +#else + var_idx = lpp_add_var(pi->curr_lp, buf, lpp_binary, 1.0 / (2.0 * n_colors) ); #endif -#ifdef DUMP_MILP - 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); - remove(EXPECT_FILENAME ".exp"); + if (!pi->first_nnc_var_idx) + pi->first_nnc_var_idx = var_idx; + } + +#ifdef NO_NULL_COLORS_EXTRA_CSTS + for (col = 0; col < n_colors; ++col) { + mangle_cst(buf, 'U', cst_counter++); + cst_idx = lpp_add_cst(pi->curr_lp, buf, lpp_greater, 0); + if (!pi->first_nnc_cst_idx) + pi->first_nnc_cst_idx = cst_idx; + lpp_set_factor_fast(pi->curr_lp, cst_idx, pi->first_nnc_var_idx+col, -1); + } #endif -#ifdef DO_SOLVE - snprintf(buf+end, sizeof(buf)-end, ".sol"); - remove(buf); + +#ifndef NO_NULL_COLORS_WITH_COSTS + for (col = 0; col < n_colors - 1; ++col) { + mangle_cst(buf, 'U', cst_counter++); + cst_idx = lpp_add_cst(pi->curr_lp, buf, lpp_greater, 0); + lpp_set_factor_fast(pi->curr_lp, cst_idx, pi->first_nnc_var_idx+col , 1); + lpp_set_factor_fast(pi->curr_lp, cst_idx, pi->first_nnc_var_idx+col+1, -1); + } #endif + } #endif /** - * Collects all irns in currently processed register class + * Add coloring-force conditions + * Matrix A: knapsack constraint for each node */ -static void pi_collect_x_names(ir_node *block, void *env) { - problem_instance_t *pi = env; - struct list_head *head = &get_ra_block_info(block)->border_head; - border_t *curr; - bitset_t *pos_regs = bitset_alloca(pi->co->cls->n_regs); - - list_for_each_entry_reverse(border_t, curr, head, list) - if (curr->is_def && curr->is_real) { - x_name_t xx; - pi->A_dim++; /* one knapsack constraint for each node */ - - xx.n = get_irn_graph_nr(curr->irn); - pi_set_first_pos(pi, xx.n, pi->x_dim); - - // iterate over all possible colors in order - bitset_clear_all(pos_regs); - pi->co->isa->get_allocatable_regs(curr->irn, pi->co->cls, pos_regs); - bitset_foreach(pos_regs, xx.c) { - DBG((dbg, LEVEL_2, "Adding %n %d\n", curr->irn, xx.c)); - obstack_grow(&pi->ob, &xx, sizeof(xx)); - pi->x_dim++; /* one x variable for each node and color */ +static void pi_add_constr_A(problem_instance_t *pi) { + pmap_entry *pme; + + DBG((dbg, LEVEL_2, "Add A constraints...\n")); + /* iterate over all blocks */ + pmap_foreach(pi->co->chordal_env->border_heads, pme) { + struct list_head *head = pme->value; + border_t *curr; + bitset_t *pos_regs = bitset_alloca(pi->co->chordal_env->cls->n_regs); + + list_for_each_entry_reverse(border_t, curr, head, list) + if (curr->is_def && curr->is_real && !is_removed(curr->irn)) { + int cst_idx, nnr, col; + + nnr = get_irn_graph_nr(curr->irn); + mangle_cst(pi->buf, 'A', nnr); + cst_idx = lpp_add_cst(pi->curr_lp, pi->buf, lpp_equal, 1); + + /* iterate over all possible colors in order */ + bitset_clear_all(pos_regs); + arch_get_allocatable_regs(get_arch_env(pi->co), curr->irn, -1, pos_regs); + bitset_foreach(pos_regs, col) { + int var_idx; + mangle_var2(pi->buf, 'x', nnr, col); + var_idx = lpp_add_var(pi->curr_lp, pi->buf, lpp_binary, 0); + if (!pi->first_x_var) + pi->first_x_var = var_idx; + pi->last_x_var = var_idx; + lpp_set_factor_fast(pi->curr_lp, cst_idx, var_idx, 1); +#ifdef NO_NULL_COLORS_EXTRA_CSTS + lpp_set_factor_fast(pi->curr_lp, pi->first_nnc_cst_idx+col, var_idx, 1); +#endif + } } - } + } } /** - * Checks if all nodes in living are live_out in block block. + * Checks if all nodes in @p living are live in in block @p block. + * @return 1 if all are live in + * 0 else */ static INLINE int all_live_in(ir_node *block, pset *living) { ir_node *n; @@ -442,181 +269,743 @@ static INLINE int all_live_in(ir_node *block, pset *living) { /** * Finds cliques in the interference graph, considering only nodes - * for which the color pi->curr_color is possible. Finds only 'maximal-cliques', - * viz cliques which are not conatained in another one. - * This is used for the matrix B. + * for which the color @p color is possible. Finds only 'maximal-cliques', + * viz cliques which are not contained in another one. + * Matrix B: interference constraints using cliques */ -static void pi_clique_finder(ir_node *block, void *env) { - problem_instance_t *pi = env; +static void pi_add_constr_B(problem_instance_t *pi, int color) { enum phase_t {growing, shrinking} phase = growing; - struct list_head *head = &get_ra_block_info(block)->border_head; border_t *b; + pmap_entry *pme; pset *living = pset_new_ptr(SLOTS_LIVING); - list_for_each_entry_reverse(border_t, b, head, list) { - const ir_node *irn = b->irn; - - if (b->is_def) { - DBG((dbg, LEVEL_2, "Def %n\n", irn)); - pset_insert_ptr(living, irn); - phase = growing; - } else { /* is_use */ - DBG((dbg, LEVEL_2, "Use %n\n", irn)); - - /* before shrinking the set, store the current 'maximum' clique; - * do NOT if clique is a single node - * do NOT if all values are live_in (in this case they were contained in a live-out clique elsewhere) */ - if (phase == growing && pset_count(living) >= 2 && !all_live_in(block, living)) { - ir_node *n; - for (n = pset_first(living); n; n = pset_next(living)) { - int pos = pi_get_pos(pi, get_irn_graph_nr(n), pi->curr_color); - matrix_set(pi->B, pi->curr_row, pos, 1); - DBG((dbg, LEVEL_2, "B[%d, %d] := %d\n", pi->curr_row, pos, 1)); + DBG((dbg, LEVEL_2, "Add B constraints (col = %d)...\n", color)); + /* iterate over all blocks */ + pmap_foreach(pi->co->chordal_env->border_heads, pme) { + ir_node *block = pme->key; + struct list_head *head = pme->value; + + list_for_each_entry_reverse(border_t, b, head, list) { + const ir_node *irn = b->irn; + if (is_removed(irn) || !is_color_possible(irn, color)) + continue; + + if (b->is_def) { + DBG((dbg, LEVEL_2, "Def %n\n", irn)); + pset_insert_ptr(living, irn); + phase = growing; + } else { /* is_use */ + DBG((dbg, LEVEL_2, "Use %n\n", irn)); + + /* before shrinking the set, store the current 'maximum' clique; + * do NOT if clique is a single node + * do NOT if all values are live_in (in this case they were contained in a live-out clique elsewhere) */ + if (phase == growing && pset_count(living) >= 2 && !all_live_in(block, living)) { + int cst_idx; + ir_node *n; + mangle_cst(pi->buf, 'B', pi->cst_counter); +#ifdef NO_NULL_COLORS + cst_idx = lpp_add_cst(pi->curr_lp, pi->buf, lpp_less, 0); +#else + cst_idx = lpp_add_cst(pi->curr_lp, pi->buf, lpp_less, 1); +#endif + for (n = pset_first(living); n; n = pset_next(living)) { + int var_idx; + mangle_var_irn(pi->buf, 'x', n, color); + var_idx = lpp_get_var_idx(pi->curr_lp, pi->buf); + lpp_set_factor_fast(pi->curr_lp, cst_idx, var_idx, 1); + } +#ifdef NO_NULL_COLORS + lpp_set_factor_fast(pi->curr_lp, cst_idx, pi->first_nnc_var_idx+color, -1.0); +#endif + pi->cst_counter++; } - pi->curr_row++; + pset_remove_ptr(living, irn); + phase = shrinking; } - pset_remove_ptr(living, irn); - phase = shrinking; } } - + assert(0 == pset_count(living)); del_pset(living); } /** - * Generate the initial problem matrices and vectors. + * Generates constraints which interrelate x with y variables. + * x1 and x2 have the different colors ==> y_12 = 1 */ -static problem_instance_t *new_pi(const copy_opt_t *co) { - DBG((dbg, LEVEL_1, "Generating new instance...\n")); - problem_instance_t *pi = calloc(1, sizeof(*pi)); - pi->co = co; - pi->num2pos = new_set(set_cmp_num2pos, SLOTS_NUM2POS); - pi->bigM = 1; - - /* Vector x - * one entry per node and possible color */ - obstack_init(&pi->ob); - dom_tree_walk_irg(co->irg, pi_collect_x_names, NULL, pi); - pi->x = obstack_finish(&pi->ob); - - /* Matrix Q - * weights for the 'same-color-optimization' target */ - { - unit_t *curr; - pi->Q = new_matrix(pi->x_dim, pi->x_dim); - - list_for_each_entry(unit_t, curr, &co->units, units) { - const ir_node *root, *arg; - int rootnr, argnr; - unsigned rootpos, argpos; - int i; - - root = curr->nodes[0]; - rootnr = get_irn_graph_nr(root); - rootpos = pi_get_first_pos(pi, rootnr); - for (i = 1; i < curr->node_count; ++i) { - int weight = -get_weight(root, arg); - arg = curr->nodes[i]; - argnr = get_irn_graph_nr(arg); - argpos = pi_get_first_pos(pi, argnr); - - DBG((dbg, LEVEL_2, "Q[%n, %n] := %d\n", root, arg, weight)); - /* for all colors root and arg have in common, set the weight for - * this pair in the objective function matrix Q */ - while (rootpos < pi->x_dim && argpos < pi->x_dim && - pi->x[rootpos].n == rootnr && pi->x[argpos].n == argnr) { - if (pi->x[rootpos].c < pi->x[argpos].c) - ++rootpos; - else if (pi->x[rootpos].c > pi->x[argpos].c) - ++argpos; - else { - matrix_set(pi->Q, rootpos++, argpos++, weight); - - if (weight < pi->minQij) { - DBG((dbg, LEVEL_2, "minQij = %d\n", weight)); - pi->minQij = weight; - } - if (weight > pi->maxQij) { - DBG((dbg, LEVEL_2, "maxQij = %d\n", weight)); - pi->maxQij = weight; - } - } +static void pi_add_constr_E(problem_instance_t *pi) { + unit_t *curr; + bitset_t *root_regs, *arg_regs, *work_regs; + int cst_counter = 0; + unsigned nregs = pi->co->chordal_env->cls->n_regs; + root_regs = bitset_alloca(nregs); + arg_regs = bitset_alloca(nregs); + work_regs = bitset_alloca(nregs); + + DBG((dbg, LEVEL_2, "Add E constraints...\n")); + /* for all roots of optimization units */ + list_for_each_entry(unit_t, curr, &pi->co->units, units) { + ir_node *root, *arg; + int rootnr, argnr, color; + int y_idx, i; + char buf[32]; + + root = curr->nodes[0]; + rootnr = get_irn_graph_nr(root); + bitset_clear_all(root_regs); + arch_get_allocatable_regs(get_arch_env(pi->co), root, -1, root_regs); + + /* for all arguments of root */ + for (i = 1; i < curr->node_count; ++i) { + arg = curr->nodes[i]; + argnr = get_irn_graph_nr(arg); + bitset_clear_all(arg_regs); + arch_get_allocatable_regs(get_arch_env(pi->co), arg, -1, arg_regs); + + /* Introduce new variable and set factor in objective function */ + mangle_var2(buf, 'y', rootnr, argnr); + y_idx = lpp_add_var(pi->curr_lp, buf, lpp_binary, curr->costs[i]); + + /* set starting value */ + lpp_set_start_value(pi->curr_lp, y_idx, (get_irn_col(pi->co, root) != get_irn_col(pi->co, arg))); + + /* For all colors root and arg have in common, add 2 constraints to E */ + bitset_copy(work_regs, root_regs); + bitset_and(work_regs, arg_regs); + bitset_foreach(work_regs, color) { + int root_idx, arg_idx, cst_idx; + mangle_var2(buf, 'x', rootnr, color); + root_idx = lpp_get_var_idx(pi->curr_lp, buf); + mangle_var2(buf, 'x', argnr, color); + arg_idx = lpp_get_var_idx(pi->curr_lp, buf); + + /* add root-arg-y <= 0 */ + mangle_cst(buf, 'E', cst_counter++); + cst_idx = lpp_add_cst(pi->curr_lp, buf, lpp_less, 0); + lpp_set_factor_fast(pi->curr_lp, cst_idx, root_idx, 1); + lpp_set_factor_fast(pi->curr_lp, cst_idx, arg_idx, -1); + lpp_set_factor_fast(pi->curr_lp, cst_idx, y_idx, -1); + + /* add arg-root-y <= 0 */ + mangle_cst(buf, 'E', cst_counter++); + cst_idx = lpp_add_cst(pi->curr_lp, buf, lpp_less, 0); + lpp_set_factor_fast(pi->curr_lp, cst_idx, root_idx, -1); + lpp_set_factor_fast(pi->curr_lp, cst_idx, arg_idx, 1); + lpp_set_factor_fast(pi->curr_lp, cst_idx, y_idx, -1); + } + /* For all colors root and arg have "disjunct", add 1 constraints to E. + * If root gets a color the arg is not possible to get then they will + * definetly get different colors. So y has to be 1. + * Vice versa for arg. + */ + bitset_copy(work_regs, root_regs); + bitset_xor(work_regs, arg_regs); + bitset_foreach(work_regs, color) { + int root_idx, arg_idx, cst_idx; + mangle_var2(buf, 'x', rootnr, color); + root_idx = lpp_get_var_idx(pi->curr_lp, buf); + mangle_var2(buf, 'x', argnr, color); + arg_idx = lpp_get_var_idx(pi->curr_lp, buf); + + mangle_cst(buf, 'E', cst_counter++); + cst_idx = lpp_add_cst(pi->curr_lp, buf, lpp_less, 0); + if (bitset_is_set(root_regs, color)) { + /* add root-y <= 0 */ + lpp_set_factor_fast(pi->curr_lp, cst_idx, root_idx, 1); + lpp_set_factor_fast(pi->curr_lp, cst_idx, y_idx, -1); + } else { + assert(bitset_is_set(arg_regs, color) && "bitset_xor is buggy"); + /* add arg-y <= 0 */ + lpp_set_factor_fast(pi->curr_lp, cst_idx, arg_idx, 1); + lpp_set_factor_fast(pi->curr_lp, cst_idx, y_idx, -1); } } } } +} + +static INLINE int get_costs(problem_instance_t *pi, ir_node *phi, ir_node *irn) { + int i; + unit_t *curr; + /* search optimization unit for phi */ + list_for_each_entry(unit_t, curr, &pi->co->units, units) + if (curr->nodes[0] == phi) { + for (i=1; inode_count; ++i) + if (curr->nodes[i] == irn) + return curr->costs[i]; + assert(0 && "irn must occur in this ou"); + } + assert(0 && "phi must be found in a ou"); + return 0; +} + +static void clique_path_walker(ir_node *block, void *env) { + problem_instance_t *pi = env; + int count, arity, row, col, other_row, *costs; + ir_node **phis, *phi, *irn, **phi_matrix; + pset *done; + bitset_t *candidates; + + /* Count all phi nodes of this block */ + for (count=0, irn = sched_first(block); is_Phi(irn); irn = sched_next(irn)) + count++; + + /* We at least 2 phi nodes for this class of inequalities */ + if (count < 2) + return; - /* Matrix A - * knapsack constraint for each node */ - { - int row = 0, col = 0; - pi->A = new_matrix(pi->A_dim, pi->x_dim); - while (col < pi->x_dim) { - int curr_n = pi->x[col].n; - while (col < pi->x_dim && pi->x[col].n == curr_n) { - DBG((dbg, LEVEL_2, "A[%d, %d] := %d\n", row, col, 1)); - matrix_set(pi->A, row, col++, 1); + /* Build the \Phi-Matrix */ + arity = get_irn_arity(sched_first(block)); + phis = alloca(count * sizeof(*phis)); + costs = alloca(count * sizeof(costs)); + phi_matrix = alloca(count*arity * sizeof(*phi_matrix)); + candidates = bitset_alloca(count); + + phi = sched_first(block); + for (row=0; rowco->chordal_env, phi, arg)) { + phi_matrix[row*arity + col] = NULL; + } else + phi_matrix[row*arity + col] = arg; + } + phi = sched_next(phi); + } + + /* Now find the interesting patterns in the matrix: + * All nodes which are used at least twice in a column. */ + /* columnwise ... */ + for (col=0; colcurr_lp, buf, lpp_greater, minimal_unequal_count); + + /* for all phis */ + bitset_foreach(candidates, pos) { + root = phis[pos]; + rootnr = get_irn_graph_nr(root); + mangle_var2(buf, 'y', rootnr, irnnr); + y_idx = lpp_get_var_idx(pi->curr_lp, buf); + lpp_set_factor_fast(pi->curr_lp, cst_idx, y_idx, 1); + } + } + } + del_pset(done); /* clear set for next row */ + } /*next col*/ +} + +/** + * Matrix M: Multi-Arg-Use. Interrelates different \phi-functions + * in the same block, iff they use the same arg at the same pos. + * Only one of the phis can get the arg. + */ +static void pi_add_clique_path_cstr(problem_instance_t *pi) { + DBG((dbg, LEVEL_2, "Adding clique path constraints...\n")); + dom_tree_walk_irg(get_irg(pi->co), clique_path_walker, NULL, pi); +} + +#ifndef PATH_CONSTRAINTS_FOR_CLASSES +/** + * Matrix P: Path contraints. + * If 2 nodes interfere and there is a path of equal-color-edges + * connecting them, then at least one of those equal-color-edges + * will break and cause some costs. + */ +static void pi_add_path_cstr(problem_instance_t *pi) { + unit_t *curr; + int cst_counter = 0; + DBG((dbg, LEVEL_2, "Adding path constraints...\n")); + + /* for all optimization units (only phis) */ + list_for_each_entry(unit_t, curr, &pi->co->units, units) { + int i, o, rootnr; + + if (curr->min_nodes_costs == 0) + continue; + + rootnr = get_irn_graph_nr(curr->nodes[0]); + /* check all argument pairs for interference */ + for (i=1; inode_count; ++i) { + const ir_node *arg1 = curr->nodes[i]; + int arg1nr = get_irn_graph_nr(arg1); + for (o=i+1; onode_count; ++o) { + const ir_node *arg2 = curr->nodes[o]; + int arg2nr = get_irn_graph_nr(arg2); + if (nodes_interfere(pi->co->chordal_env, arg1, arg2)) { + int cst_idx, y_idx; + char buf[32]; + + mangle_cst(buf, 'P', cst_counter++); + cst_idx = lpp_add_cst(pi->curr_lp, buf, lpp_greater, 1); + + mangle_var2(buf, 'y', rootnr, arg1nr); + y_idx = lpp_get_var_idx(pi->curr_lp, buf); + lpp_set_factor_fast(pi->curr_lp, cst_idx, y_idx, 1); + + mangle_var2(buf, 'y', rootnr, arg2nr); + y_idx = lpp_get_var_idx(pi->curr_lp, buf); + lpp_set_factor_fast(pi->curr_lp, cst_idx, y_idx, 1); + } } - ++row; } - assert(row == pi->A_dim); } +} +#endif + +#ifdef PATH_CONSTRAINTS_FOR_CLASSES +static INLINE int get_y_var_idx(problem_instance_t *pi, int nnr1, int nnr2) { + int res; + char buf[30]; - /* Matrix B - * interference constraints using exactly those cliques not contained in others. */ - { - int color, expected_clipques = pi->A_dim/4 * pi->co->cls->n_regs; - pi->B = new_matrix(expected_clipques, pi->x_dim); - for (color = 0; color < pi->co->cls->n_regs; ++color) { - pi->curr_color = color; - dom_tree_walk_irg(pi->co->irg, pi_clique_finder, NULL, pi); + mangle_var2(buf, 'y', nnr1, nnr2); + if ((res = lpp_get_var_idx(pi->curr_lp, buf)) != -1) + return res; + + mangle_var2(buf, 'y', nnr2, nnr1); + if ((res = lpp_get_var_idx(pi->curr_lp, buf)) != -1) + return res; + + assert(0 && "One of them must work"); + return -1; +} + +static void check_ecc_and_add_cut(problem_instance_t *pi, ir_node **path, int length, pset *remain, ir_node *tgt) { + if (path[length-1] == tgt) { /* we found a path */ + int cst_idx, var_idx, i, nnr1, nnr2; + char buf[30]; + + /* add cut to ilp */ + mangle_cst(buf, 'Q', pi->cst_counter++); + cst_idx = lpp_add_cst(pi->curr_lp, buf, lpp_greater, 1); + + /* add all vars along the path */ + nnr2 = get_irn_graph_nr(path[0]); + for (i=1; icurr_lp, cst_idx, var_idx, 1); } - pi->B_dim = matrix_get_rowcount(pi->B); + } else { /* try to extend the path */ + be_chordal_env_t *cenv = pi->co->chordal_env; + const ir_edge_t *edge; + ir_node *end = path[length-1]; + ir_node **next = alloca(pset_count(remain) * sizeof(*next)); + int i, o, max, next_pos = 0; + pset *done = pset_new_ptr_default(); + + /* find all potential next nodes on path */ + /* args of phis */ + if (is_Phi(end)) + for(i=0, max=get_irn_arity(end); isrc; + if (is_Phi(user) && !pset_find_ptr(done, user) && pset_find_ptr(remain, user)) { + next[next_pos++] = user; + pset_insert_ptr(done, user); + } + } + del_pset(done); + + + /* delete all potential nodes with interferences to other nodes in the path */ + for (i=0; i 1) ? 1 : 0; + + for(; odone, class)) + return; + + pset_insert_ptr(pi->done, class); + + /* pset to array */ + max = pset_count(class); + cls = alloca(max * sizeof(*cls)); + for(i=0, m = pset_first(class); m; i++, m = pset_next(class)) { + DBG((dbg, LEVEL_1, " class member: %+F\n", m)); + cls[i] = m; + } + + cenv = pi->co->chordal_env; + for(i=0; icst_counter = 0; + pi->done = pset_new_ptr_default(); + irg_walk_graph(get_irg(pi->co), path_cstr_for_classes_walker, NULL, pi); + del_pset(pi->done); +} +#endif + +#ifdef PRECOLOR_MAX_CLIQUE +struct pre_col { + problem_instance_t *pi; + pset **clique; +}; + +#define has_reg_class(pi,irn) \ + (arch_get_irn_reg_class(pi->co->chordal_env->session_env->main_env->arch_env, \ + irn, -1) == pi->co->chordal_env->cls) + +static void preColoringWalker(ir_node *bl, void *env) { + struct pre_col *e = env; + pset **clique = e->clique; + pset *max_clique = clique ? *clique : NULL; + int max = max_clique ? pset_count(max_clique) : 0; + problem_instance_t *pi = e->pi; + + int i, n; + pset *live = pset_new_ptr_default(); + ir_node *irn; + irn_live_t *li; + + /* as always, bring the live end nodes to life here */ + live_foreach(bl, li) { + if(live_is_end(li) && has_reg_class(pi, li->irn)) { + pset_insert_ptr(live, irn); + } + } + + sched_foreach_reverse(bl, irn) { + int pres = pset_count(live); + + if(pres > max) { + max = pres; + if(max_clique) + del_pset(max_clique); + + max_clique = pset_new_ptr_default(); + pset_insert_pset_ptr(max_clique, live); + } + + + + if(has_reg_class(pi, irn)) + pset_remove_ptr(live, irn); + + for(i = 0, n = get_irn_arity(irn); i < n; ++i) { + ir_node *op = get_irn_n(irn, i); + if(has_reg_class(pi, op) && !is_Phi(irn)) + pset_insert_ptr(live, op); + } + } + + del_pset(live); + *clique = max_clique; +} + +static void pi_add_constr_preColoring(problem_instance_t *pi) { + ir_node *irn; + int cst_counter, color; + struct pre_col pre_col; + + pre_col.clique = NULL; + pre_col.pi = pi; + + dom_tree_walk_irg(get_irg(pi->co), preColoringWalker, NULL, &pre_col); + + color = 0; + for (irn = pset_first(*pre_col.clique); irn; irn = pset_next(*pre_col.clique)) { + int cst_idx, var_idx, nnr = get_irn_graph_nr(irn); + char buf[100]; + + mangle_cst(buf, 'K', cst_counter++); + cst_idx = lpp_add_cst(pi->curr_lp, buf, lpp_equal, 1); + + mangle_var2(buf, 'x', nnr, color++); + var_idx = lpp_get_var_idx(pi->curr_lp, buf); + lpp_set_factor_fast(pi->curr_lp, cst_idx, var_idx, 1); + } +} +#endif + +/** + * Generate the initial problem matrices and vectors. + */ +static problem_instance_t *new_pi(const copy_opt_t *co) { + problem_instance_t *pi; + int col; + + DBG((dbg, LEVEL_2, "Generating new instance...\n")); + pi = xcalloc(1, sizeof(*pi)); + pi->co = co; + pi->removed = pset_new_ptr_default(); + INIT_LIST_HEAD(&pi->simplicials); + pi->dilp = new_lpp(co->name, lpp_minimize); + + /* problem size reduction */ + pi_find_simplicials(pi); + if (pi->all_simplicial) + return pi; + + /* built objective and constraints */ + pi->curr_lp = pi->dilp; +#ifdef NO_NULL_COLORS + pi_add_constr_no_null_colors(pi); +#endif + pi_add_constr_A(pi); + for (col = 0; col < pi->co->chordal_env->cls->n_regs; ++col) + pi_add_constr_B(pi, col); + pi_add_constr_E(pi); + +#ifdef PATH_CONSTRAINTS_FOR_CLASSES + pi_add_path_cstr_for_classes(pi); +#else + pi_add_path_cstr(pi); +#endif + pi_add_clique_path_cstr(pi); +#ifdef PRECOLOR_MAX_CLIQUE + pi_add_constr_preColoring(pi); +#endif return pi; } /** - * clean the problem instance + * Clean the problem instance */ static void free_pi(problem_instance_t *pi) { - DBG((dbg, LEVEL_1, "Generating new instance...\n")); - del_matrix(pi->Q); - del_matrix(pi->A); - del_matrix(pi->B); - del_set(pi->num2pos); - obstack_free(&pi->ob, NULL); + simpl_t *simpl, *tmp; + + DBG((dbg, LEVEL_2, "Free instance...\n")); + free_lpp(pi->dilp); + list_for_each_entry_safe(simpl_t, simpl, tmp, &pi->simplicials, chain) + free(simpl); + del_pset(pi->removed); free(pi); } -void co_ilp_opt(copy_opt_t *co) { - dbg = firm_dbg_register("ir.be.copyoptilp"); - firm_dbg_set_mask(dbg, DEBUG_LVL); - if (!strcmp(co->name, DEBUG_IRG)) - firm_dbg_set_mask(dbg, -1); +/** + * Set starting values for the mip problem according + * to the current coloring of the graph. + */ +static void pi_set_start_sol(problem_instance_t *pi) { + int i; + char var_name[64]; + DBG((dbg, LEVEL_2, "Set start solution...\n")); + for (i=pi->first_x_var; i<=pi->last_x_var; ++i) { + int nnr, col; + double val; + /* get variable name */ + lpp_get_var_name(pi->curr_lp, i, var_name, sizeof(var_name)); + /* split into components */ + if (split_var(var_name, &nnr, &col) == 2) { + assert(get_irn_col(pi->co, get_irn_for_graph_nr(get_irg(pi->co), nnr)) != -1); + val = (get_irn_col(pi->co, get_irn_for_graph_nr(get_irg(pi->co), nnr)) == col) ? 1 : 0; + lpp_set_start_value(pi->curr_lp, i, val); + } else { + fprintf(stderr, "Variable name is: %s\n", var_name); + assert(0 && "x vars always look like this 'x123_45'"); + } + } +} - problem_instance_t *pi = new_pi(co); - DBG((dbg, 0, "\t\t\t %5d %5d %5d\n", pi->x_dim, pi->A_dim, pi->B_dim)); +/** + * Invoke a solver + */ +static void pi_solve_ilp(problem_instance_t *pi) { + double lower_bound; + + pi_set_start_sol(pi); + lower_bound = co_get_lower_bound(pi->co) - co_get_inevit_copy_costs(pi->co); + lpp_set_bound(pi->curr_lp, lower_bound); + lpp_solve_net(pi->curr_lp, LPP_HOST, LPP_SOLVER); +// lpp_solve_cplex(pi->curr_lp); + DBG((dbg, LEVEL_1, "Solution time: %.2f\n", pi->curr_lp->sol_time)); +} - if (pi->x_dim > 0) { -#ifdef DUMP_MATRICES - pi_dump_matrices(pi); -#endif +/** + * Set the color of all simplicial nodes removed form + * the graph before transforming it to an ilp. + */ +static void pi_set_simplicials(problem_instance_t *pi) { + simpl_t *simpl, *tmp; + be_ifg_t *ifg = pi->co->chordal_env->ifg; + bitset_t *used_cols = bitset_alloca(arch_register_class_n_regs(pi->co->chordal_env->cls)); + void *iter = be_ifg_neighbours_iter_alloca(ifg); + + DBG((dbg, LEVEL_2, "Set simplicials...\n")); + /* color the simplicial nodes in right order */ + list_for_each_entry_safe(simpl_t, simpl, tmp, &pi->simplicials, chain) { + int free_col; + ir_node *other, *irn; + + /* get free color by inspecting all neighbors */ + irn = simpl->irn; + bitset_clear_all(used_cols); + + be_ifg_foreach_neighbour(ifg, iter, irn, other) { + if (!is_removed(other)) /* only inspect nodes which are in graph right now */ + bitset_set(used_cols, get_irn_col(pi->co, other)); + } -#ifdef DUMP_MILP - pi_dump_milp(pi); -#endif + /* 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(pi->co, irn, free_col); + pset_remove_ptr(pi->removed, irn); /* irn is back in graph again */ + } +} + +/** + * Sets the colors of irns according to the values of variables + * provided by the solution of the solver. + */ +static int pi_apply_solution(problem_instance_t *pi) { + int res = 1, i; + double *sol; + lpp_sol_state_t state; + DBG((dbg, LEVEL_2, "Applying solution...\n")); -#ifdef DO_SOLVE - pi_dump_start_sol(pi); - pi_solve_ilp(pi); - pi_apply_solution(pi); +#ifdef DO_STAT + copystat_add_ilp_time((int)(1000.0*lpp_get_sol_time(pi->curr_lp))); //now we have ms + copystat_add_ilp_vars(lpp_get_var_count(pi->curr_lp)); + copystat_add_ilp_csts(lpp_get_cst_count(pi->curr_lp)); + copystat_add_ilp_iter(lpp_get_iter_cnt(pi->curr_lp)); #endif -#ifdef DELETE_FILES - pi_delete_files(pi); + sol = xmalloc((pi->last_x_var - pi->first_x_var + 1) * sizeof(*sol)); + state = lpp_get_solution(pi->curr_lp, sol, pi->first_x_var, pi->last_x_var); + if (state != lpp_optimal) { + printf("WARNING %s: Solution state is not 'optimal': %d\n", pi->co->name, state); + assert(state >= lpp_feasible && "The solution should at least be feasible!"); + res = 0; + } + for (i=0; ilast_x_var - pi->first_x_var + 1; ++i) { + int nnr, col; + char var_name[64]; + + if (sol[i] > 1-EPSILON) { /* split varibale name into components */ + lpp_get_var_name(pi->curr_lp, pi->first_x_var+i, var_name, sizeof(var_name)); + if (split_var(var_name, &nnr, &col) == 2) { + DBG((dbg, LEVEL_2, "Irn %n Idx %d Var %s Val %f\n", get_irn_for_graph_nr(get_irg(pi->co), nnr), i, var_name, sol[i])); + DBG((dbg, LEVEL_2, "x%d = %d\n", nnr, col)); + set_irn_col(pi->co, get_irn_for_graph_nr(get_irg(pi->co), nnr), col); + } else + assert(0 && "This should be a x-var"); + } + } + return res; +} + +int co_ilp_opt(copy_opt_t *co, double time_limit) { + int res = 1; + problem_instance_t *pi; + + dbg = firm_dbg_register("ir.be.copyoptilp"); + + pi = new_pi(co); + if (!pi->all_simplicial) { +#ifdef DUMP_MPS + char buf[512]; + snprintf(buf, sizeof(buf), "%s.mps", co->name); + lpp_dump(pi->curr_lp, buf); #endif + lpp_set_time_limit(pi->curr_lp, time_limit); + pi_solve_ilp(pi); + res = pi_apply_solution(pi); + pi_set_simplicials(pi); } free_pi(pi); + return res; }