nsz Git - libfirm/blob - ir/be/becopyilp.c

   1 /**
   2  * Minimizing copies with an exact algorithm using mixed integer programming (MIP).
   3  * Problem statement as a 'quadratic 0-1 program with linear constraints' with
   4  * n binary variables. Constraints are knapsack (enforce color for each node) and
   5  * cliques of ifg (interference constraints).
   6  * Transformation into a 'mixed integer program' with n binary variables and
   7  * additional 2n real variables. Constraints are the above the transformed
   8  * objective function and 'complementary conditions' for two var classes.
   9  * @author Daniel Grund
  10  *
  11  * NOTE: Unfortunately no good solver is available locally (or even for linking)
  12  *       We use CPLEX 9.0 which runs on a machine residing at the Rechenzentrum.
  13  * @date 12.04.2005
  14  */
  15
  16 #include "becopyopt.h"
  17 #include "becopystat.h"
  18
  19 #define DUMP_MPS                        /**< dumps the problem in "CPLEX"-MPS format. NOT fixed-column-MPS. */
  20 #undef USE_SOS                          /**< uses Special Ordered Sets when using MPS */
  21 #define DO_SOLVE                        /**< solve the MPS output with CPLEX */
  22 #undef DUMP_MATRICES            /**< dumps all matrices completely. only recommended for small problems */
  23 #undef DUMP_LP                          /**< dumps the problem in LP format. 'human-readable' equations etc... */
  24 #define DELETE_FILES            /**< deletes all dumped files after use */
  25
  26 /* CPLEX-account related stuff */
  27 #define SSH_USER_HOST "kb61@sp-smp.rz.uni-karlsruhe.de"
  28 #define SSH_PASSWD "!cplex90"
  29 #define EXPECT_FILENAME "runme" /** name of the expect-script */
  30
  31 #define DEBUG_LVL SET_LEVEL_1
  32 static firm_dbg_module_t *dbg = NULL;
  33
  34 #define SLOTS_NUM2POS 256
  35 #define SLOTS_LIVING 32
  36
  37 /**
  38  * A type storing names of the x variables in the form x[NUMBER]_[COLOR]
  39  */
  40 typedef struct _x_name_t {
  41         int n, c;
  42 } x_name_t;
  43
  44 /**
  45  * For each node taking part in the opt-problem its position in the
  46  * x-variable-vector is stored in a set. This set maps the node-nr (given by
  47  * benumb) to the position in the vector.
  48  */
  49 typedef struct _num2pos_t {
  50         int num, pos;
  51 } num2pos_t;
  52
  53 /**
  54  * A type storing the unmodified '0-1 quadratic program' of the form
  55  * min f = xQx
  56  * udN:  Ax  = e
  57  *       Bx <= e
  58  *        x \in {0, 1}
  59  *
  60  * This problem is called the original problem
  61  */
  62 typedef struct _problem_instance_t {
  63         ir_graph* irg;
  64         const char *name;
  65         int x_dim, A_dim, B_dim;        /**< number of: x variables, rows in A, rows in B */
  66         x_name_t *x;                            /**< stores the names of the x variables. all possible colors for a node are ordered and occupy consecutive entries. lives in obstack ob. */
  67         set *num2pos;                           /**< maps node numbers to positions in x. */
  68         sp_matrix_t *Q, *A, *B;         /**< the (sparse) matrices of this problem */
  69
  70         /* needed only for linearizations */
  71         int bigM, maxQij, minQij;
  72
  73         /* overhead needed to build this */
  74         struct obstack ob;
  75         int curr_color;
  76         int curr_row;
  77 } problem_instance_t;
  78
  79 /* Nodes have consecutive numbers so this hash shoud be fine */
  80 #define HASH_NUM(num) num
  81
  82 static int set_cmp_num2pos(const void *x, const void *y, size_t size) {
  83         return ((num2pos_t *)x)->num != ((num2pos_t *)y)->num;
  84 }
  85
  86 /**
  87  * Sets the first position of node with number num to pos.
  88  * See x_name_t *x in _problem_instance_t.
  89  */
  90 static INLINE void pi_set_first_pos(problem_instance_t *pi, int num, int pos) {
  91         num2pos_t find;
  92         find.num = num;
  93         find.pos = pos;
  94         set_insert(pi->num2pos, &find, sizeof(find), HASH_NUM(num));
  95 }
  96
  97 /**
  98  * Get position by number. (First possible color)
  99  * returns -1 if not found.
 100  */
 101 static INLINE int pi_get_first_pos(problem_instance_t *pi, int num) {
 102         num2pos_t find, *found;
 103         find.num = num;
 104         found = set_find(pi->num2pos, &find, sizeof(find), HASH_NUM(num));
 105         if (found) {
 106                 assert(pi->x[found->pos].n == num && (found->pos == 0 || pi->x[found->pos-1].n != num) && "pi->num2pos is broken!");
 107                 return found->pos;
 108         } else
 109                 return -1;
 110 }
 111
 112 /**
 113  * Get position by number and color.
 114  * returns -1 if not found.
 115  */
 116 static INLINE int pi_get_pos(problem_instance_t *pi, int num, int col) {
 117         num2pos_t find, *found;
 118         find.num = num;
 119         int pos;
 120         found = set_find(pi->num2pos, &find, sizeof(find), HASH_NUM(num));
 121         if (!found)
 122                 return -1;
 123         pos = found->pos;
 124         while (pos < pi->x_dim && pi->x[pos].n == num && pi->x[pos].c < col)
 125                 pos++;
 126
 127         if (pi->x[pos].n == num && pi->x[pos].c == col)
 128                 return pos;
 129         else
 130                 return -1;
 131 }
 132
 133 #ifdef DUMP_MATRICES
 134 /**
 135  * Dump the raw matrices of the problem to a file for debugging.
 136  */
 137 static void pi_dump_matrices(problem_instance_t *pi) {
 138         int i;
 139         FILE *out = ffopen(pi->name, "matrix", "wt");
 140
 141         DBG((dbg, LEVEL_1, "Dumping raw...\n"));
 142         fprintf(out, "\n\nx-names =\n");
 143         for (i=0; i<pi->x_dim; ++i)
 144                 fprintf(out, "%5d %2d\n", pi->x[i].n, pi->x[i].c);
 145
 146         fprintf(out, "\n\n-Q =\n");
 147         matrix_dump(pi->Q, out, -1);
 148
 149         fprintf(out, "\n\nA =\n");
 150         matrix_dump(pi->A, out, 1);
 151
 152         fprintf(out, "\n\nB =\n");
 153         matrix_dump(pi->B, out, 1);
 154
 155         fclose(out);
 156 }
 157 #endif
 158
 159 #ifdef DUMP_LP
 160 /**
 161  * Dumps the problem instance as a MILP. The original problem is transformed into:
 162  * min f = es - Mex
 163  * udN:  Qx -y -s +Me = 0
 164  *       Ax  = e
 165  *       Bx <= e
 166  *        y <= 2M(e-x)
 167  *        x \in N   y, s >= 0
 168  *
 169  * with M >= max sum Q'ij * x_j
 170  *            i   j
 171  */
 172 static void pi_dump_lp(problem_instance_t *pi) {
 173         int i, max_abs_Qij;
 174         matrix_elem_t *e;
 175         FILE *out = ffopen(pi->name, "lpo", "wt");
 176
 177         DBG((dbg, LEVEL_1, "Dumping lp...\n"));
 178         /* calc the big M for Q */
 179         max_abs_Qij = pi->maxQij;
 180         if (-pi->minQij > max_abs_Qij)
 181                 max_abs_Qij = -pi->minQij;
 182         pi->bigM = pi->A_dim * max_abs_Qij;
 183         DBG((dbg, LEVEL_2, "BigM = %d\n", pi->bigM));
 184
 185         /* generate objective function */
 186         fprintf(out, "min: ");
 187         for (i=0; i<pi->x_dim; ++i)
 188                 fprintf(out, "+s%d_%d -%dx%d_%d ", pi->x[i].n, pi->x[i].c, pi->bigM, pi->x[i].n, pi->x[i].c);
 189         fprintf(out, ";\n\n");
 190
 191         /* constraints for former objective function */
 192         for (i=0; i<pi->x_dim; ++i)     {
 193                 matrix_foreach_in_row(pi->Q, i, e) {
 194                         int Qio = e->val;
 195                                 if (Qio == 1)
 196                                         fprintf(out, "+x%d_%d ", pi->x[e->col].n, pi->x[e->col].c);
 197                                 else if(Qio == -1)
 198                                         fprintf(out, "-x%d_%d ", pi->x[e->col].n, pi->x[e->col].c);
 199                                 else
 200                                         fprintf(out, "%+dx%d_%d ", Qio, pi->x[e->col].n, pi->x[e->col].c);
 201                 }
 202                 fprintf(out, "-y%d_%d -s%d_%d +%d= 0;\n", pi->x[i].n, pi->x[i].c, pi->x[i].n, pi->x[i].c, pi->bigM);
 203         }
 204         fprintf(out, "\n\n");
 205
 206         /* constraints for (special) complementary condition */
 207         for (i=0; i<pi->x_dim; ++i)
 208                 fprintf(out, "y%d_%d <= %d - %dx%d_%d;\n", pi->x[i].n, pi->x[i].c, 2*pi->bigM, 2*pi->bigM, pi->x[i].n, pi->x[i].c);
 209         fprintf(out, "\n\n");
 210
 211         /* knapsack constraints */
 212         for (i=0; i<pi->A_dim; ++i)     {
 213                 matrix_foreach_in_row(pi->Q, i, e)
 214                         fprintf(out, "+x%d_%d ", pi->x[e->col].n, pi->x[e->col].c);
 215                 fprintf(out, " = 1;\n");
 216         }
 217         fprintf(out, "\n\n");
 218
 219         /* interference graph constraints */
 220         for (i=0; i<pi->B_dim; ++i)     {
 221                 matrix_foreach_in_row(pi->Q, i, e)
 222                         fprintf(out, "+x%d_%d ", pi->x[e->col].n, pi->x[e->col].c);
 223                 fprintf(out, " <= 1;\n");
 224         }
 225         fprintf(out, "\n\n");
 226
 227         /* integer constraints */
 228         fprintf(out, "int x%d_%d", pi->x[0].n, pi->x[0].c);
 229         for (i=1; i<pi->x_dim; ++i)
 230                 fprintf(out, ", x%d_%d", pi->x[i].n, pi->x[i].c);
 231         fprintf(out, ";\n");
 232
 233         fclose(out);
 234 }
 235 #endif
 236
 237 #ifdef DUMP_MPS
 238 /**
 239  * Dumps an mps file representing the problem. This is NOT the old-style,
 240  * fixed-column format. Some white spaces are important, in general spaces
 241  * are separators, MARKER-lines are used in COLUMN section to define binaries.
 242  */
 243 //BETTER use last 2 fields in COLUMNS section
 244 static void pi_dump_mps(problem_instance_t *pi) {
 245         int i, max_abs_Qij;
 246         matrix_elem_t *e;
 247         FILE *out = ffopen(pi->name, "mps", "wt");
 248
 249         DBG((dbg, LEVEL_1, "Dumping mps...\n"));
 250         max_abs_Qij = pi->maxQij;
 251         if (-pi->minQij > max_abs_Qij)
 252                 max_abs_Qij = -pi->minQij;
 253         pi->bigM = pi->A_dim * max_abs_Qij;
 254         DBG((dbg, LEVEL_2, "BigM = %d\n", pi->bigM));
 255
 256         fprintf(out, "NAME %s\n", pi->name);
 257
 258         fprintf(out, "ROWS\n");
 259         fprintf(out, " N obj\n");
 260         for (i=0; i<pi->x_dim; ++i)
 261                 fprintf(out, " E cQ%d\n", i);
 262         for (i=0; i<pi->A_dim; ++i)
 263                 fprintf(out, " E cA%d\n", i);
 264         for (i=0; i<pi->B_dim; ++i)
 265                 fprintf(out, " L cB%d\n", i);
 266         for (i=0; i<pi->x_dim; ++i)
 267                 fprintf(out, " L cy%d\n", i);
 268
 269         fprintf(out, "COLUMNS\n");
 270         /* the x vars come first */
 271         /* mark them as binaries */
 272         fprintf(out, "    MARKI0\t'MARKER'\t'INTORG'\n");
 273 #ifdef USE_SOS
 274         int sos_cnt = 0;
 275         fprintf(out, " S1 SOS_%d\t'MARKER'\t'SOSORG'\n", sos_cnt++);
 276 #endif
 277         for (i=0; i<pi->x_dim; ++i) {
 278 #ifdef USE_SOS
 279                 if (i>0 && pi->x[i].n != pi->x[i-1].n) {
 280                         fprintf(out, "    SOS_%d\t'MARKER'\t'SOSEND'\n", sos_cnt++);
 281                         fprintf(out, " S1 SOS_%d\t'MARKER'\t'SOSORG'\n", sos_cnt++);
 282                 }
 283 #endif
 284                 /* participation in objective */
 285                 fprintf(out, "    x%d_%d\tobj\t%d\n", pi->x[i].n, pi->x[i].c, -pi->bigM);
 286                 /* in Q */
 287                 matrix_foreach_in_col(pi->Q, i, e)
 288                         fprintf(out, "    x%d_%d\tcQ%d\t%d\n", pi->x[i].n, pi->x[i].c, e->row, e->val);
 289                 /* in A */
 290                 matrix_foreach_in_col(pi->A, i, e)
 291                         fprintf(out, "    x%d_%d\tcA%d\t%d\n", pi->x[i].n, pi->x[i].c, e->row, e->val);
 292                 /* in B */
 293                 matrix_foreach_in_col(pi->B, i, e)
 294                         fprintf(out, "    x%d_%d\tcB%d\t%d\n", pi->x[i].n, pi->x[i].c, e->row, e->val);
 295                 /* in y */
 296                 fprintf(out, "    x%d_%d\tcy%d\t%d\n", pi->x[i].n, pi->x[i].c, i, 2*pi->bigM);
 297         }
 298
 299 #ifdef USE_SOS
 300         fprintf(out, "    SOS_%d\t'MARKER'\t'SOSEND'\n", sos_cnt++);
 301 #endif
 302         fprintf(out, "    MARKI1\t'MARKER'\t'INTEND'\n"); /* end of marking */
 303
 304         /* next the s vars */
 305         for (i=0; i<pi->x_dim; ++i) {
 306                 /* participation in objective */
 307                 fprintf(out, "    s%d_%d\tobj\t%d\n", pi->x[i].n, pi->x[i].c, 1);
 308                 /* in Q */
 309                 fprintf(out, "    s%d_%d\tcQ%d\t%d\n", pi->x[i].n, pi->x[i].c, i, -1);
 310         }
 311
 312         /* next the y vars */
 313         for (i=0; i<pi->x_dim; ++i) {
 314                 /* in Q */
 315                 fprintf(out, "    y%d_%d\tcQ%d\t%d\n", pi->x[i].n, pi->x[i].c, i, -1);
 316                 /* in y */
 317                 fprintf(out, "    y%d_%d\tcy%d\t%d\n", pi->x[i].n, pi->x[i].c, i, 1);
 318         }
 319
 320         fprintf(out, "RHS\n");
 321         for (i=0; i<pi->x_dim; ++i)
 322                 fprintf(out, "    rhs\tcQ%d\t%d\n", i, -pi->bigM);
 323         for (i=0; i<pi->A_dim; ++i)
 324                 fprintf(out, "    rhs\tcA%d\t%d\n", i, 1);
 325         for (i=0; i<pi->B_dim; ++i)
 326                 fprintf(out, "    rhs\tcB%d\t%d\n", i, 1);
 327         for (i=0; i<pi->x_dim; ++i)
 328                 fprintf(out, "    rhs\tcy%d\t%d\n", i, 2*pi->bigM);
 329
 330         fprintf(out, "ENDATA\n");
 331         fclose(out);
 332
 333         out = ffopen(pi->name, "mst", "wt");
 334         fprintf(out, "NAME\n");
 335         for (i=0; i<pi->x_dim; ++i) {
 336                 int val, n, c;
 337                 n = pi->x[i].n;
 338                 c = pi->x[i].c;
 339                 if (get_irn_color(get_irn_for_graph_nr(pi->irg, n)) == c)
 340                         val = 1;
 341                 else
 342                         val = 0;
 343                 fprintf(out, "    x%d_%d\t%d\n", n, c, val);
 344         }
 345         fprintf(out, "ENDATA\n");
 346         fclose(out);
 347 }
 348 #endif
 349
 350 #ifdef DO_SOLVE
 351 /**
 352  * Invoke an external solver
 353  */
 354 static void pi_solve_ilp(problem_instance_t *pi) {
 355         FILE *out;
 356
 357         DBG((dbg, LEVEL_1, "Solving with CPLEX@RZ...\n"));
 358         /* write command file for CPLEX */
 359         out = ffopen(pi->name, "cmd", "wt");
 360         fprintf(out, "read %s.mps\n", pi->name);
 361         fprintf(out, "read %s.mst\n", pi->name);
 362         fprintf(out, "set mip strategy mipstart 1\n");
 363         fprintf(out, "set logfile %s.sol\n", pi->name);
 364         fprintf(out, "optimize\n");
 365         fprintf(out, "display solution variables 1-%d\n", pi->x_dim);
 366         fprintf(out, "set logfile cplex.log\n");
 367         fprintf(out, "quit\n");
 368         fclose(out);
 369
 370         /* write expect-file for copying problem to RZ */
 371         out = ffopen(EXPECT_FILENAME, "exp", "wt");
 372         fprintf(out, "#! /usr/bin/expect\n");
 373         fprintf(out, "spawn scp %s.mps %s.mst %s.cmd %s:\n", pi->name, pi->name, pi->name, SSH_USER_HOST); /* copy problem files */
 374         fprintf(out, "expect \":\"\nsend \"%s\\n\"\ninteract\n", SSH_PASSWD);
 375
 376         fprintf(out, "spawn ssh %s \"./cplex90 < %s.cmd\"\n", SSH_USER_HOST, pi->name); /* solve */
 377         fprintf(out, "expect \":\"\nsend \"%s\\n\"\ninteract\n", SSH_PASSWD);
 378
 379         fprintf(out, "spawn scp %s:%s.sol .\n", SSH_USER_HOST, pi->name); /*copy back solution */
 380         fprintf(out, "expect \":\"\nsend \"%s\\n\"\ninteract\n", SSH_PASSWD);
 381
 382         fprintf(out, "spawn ssh %s ./dell\n", SSH_USER_HOST); /* clean files on server */
 383         fprintf(out, "expect \":\"\nsend \"%s\\n\"\ninteract\n", SSH_PASSWD);
 384         fclose(out);
 385
 386         /* call the expect script */
 387         chmod(EXPECT_FILENAME ".exp", 0700);
 388         system(EXPECT_FILENAME ".exp");
 389 }
 390
 391 /**
 392  * Sets the colors of irns according to the values of variables found in the
 393  * output file of the solver.
 394  */
 395 static void pi_apply_solution(problem_instance_t *pi) {
 396         FILE *in = ffopen(pi->name, "sol", "rt");
 397
 398         if (!in)
 399                 return;
 400         DBG((dbg, LEVEL_1, "Applying solution...\n"));
 401         while (!feof(in)) {
 402                 char buf[1024];
 403                 int num = -1, col = -1, val = -1;
 404
 405                 //TODO No integer feasible solution exists.
 406
 407                 if (fscanf(in, "x%d_%d %d.%s\n", &num, &col, &val, buf) != 3) {
 408                         while(fscanf(in, "%1020s\n", buf) != 1);
 409                         continue;
 410                 }
 411                 if (val == 1) {
 412                         DBG((dbg, LEVEL_1, "x%d_%d = %d\n", num, col, val));
 413                         set_irn_color(get_irn_for_graph_nr(pi->irg, num), col);
 414                 }
 415         }
 416         fclose(in);
 417 }
 418 #endif /* DO_SOLVE */
 419
 420 #ifdef DELETE_FILES
 421 static void pi_delete_files(problem_instance_t *pi) {
 422         char buf[1024];
 423         int end = snprintf(buf, sizeof(buf), "%s", pi->name);
 424         DBG((dbg, LEVEL_1, "Deleting files...\n"));
 425 #ifdef DUMP_MATRICES
 426         snprintf(buf+end, sizeof(buf)-end, ".matrix");
 427         remove(buf);
 428 #endif
 429 #ifdef DUMP_MPS
 430         snprintf(buf+end, sizeof(buf)-end, ".mps");
 431         remove(buf);
 432         snprintf(buf+end, sizeof(buf)-end, ".mst");
 433         remove(buf);
 434         snprintf(buf+end, sizeof(buf)-end, ".cmd");
 435         remove(buf);
 436         remove(EXPECT_FILENAME ".exp");
 437 #endif
 438 #ifdef DUMP_LP
 439         snprintf(buf+end, sizeof(buf)-end, ".lp");
 440         remove(buf);
 441 #endif
 442 }
 443 #endif
 444
 445 /**
 446  * Collects all irns in currently processed register class
 447  */
 448 static void pi_collect_x_names(ir_node *block, void *env) {
 449         problem_instance_t *pi = env;
 450         struct list_head *head = &get_ra_block_info(block)->border_head;
 451         border_t *curr;
 452
 453         list_for_each_entry_reverse(border_t, curr, head, list)
 454                 if (curr->is_def && curr->is_real) {
 455                         x_name_t xx;
 456                         pi->A_dim++;                    /* one knapsack constraint for each node */
 457
 458                         xx.n = get_irn_graph_nr(curr->irn);
 459                         pi_set_first_pos(pi, xx.n, pi->x_dim);
 460                         //TODO iterate over all possible colors !!MUST BE IN ORDER!!
 461                         for (xx.c=0; xx.c<MAX_COLORS; ++xx.c) {
 462                                 if (!is_possible_color(irn, xx.c))
 463                                         continue;
 464                                 DBG((dbg, LEVEL_2, "Adding %n %d\n", curr->irn, xx.c));
 465                                 obstack_grow(&pi->ob, &xx, sizeof(xx));
 466                                 pi->x_dim++;            /* one x variable for each node and color */
 467                         }
 468                 }
 469 }
 470
 471 /**
 472  * Checks if all nodes in living are live_out in block block.
 473  */
 474 static INLINE int all_live_in(ir_node *block, pset *living) {
 475         ir_node *n;
 476         for (n = pset_first(living); n; n = pset_next(living))
 477                 if (!is_live_in(block, n)) {
 478                         pset_break(living);
 479                         return 0;
 480                 }
 481         return 1;
 482 }
 483
 484 /**
 485  * Finds cliques in the interference graph, considering only nodes
 486  * for which the color pi->curr_color is possible. Finds only 'maximal-cliques',
 487  * viz cliques which are not conatained in another one.
 488  * This is used for the matrix B.
 489  */
 490 static void pi_clique_finder(ir_node *block, void *env) {
 491         problem_instance_t *pi = env;
 492         enum phase_t {growing, shrinking} phase = growing;
 493         struct list_head *head = &get_ra_block_info(block)->border_head;
 494         border_t *b;
 495         pset *living = pset_new_ptr(SLOTS_LIVING);
 496
 497         list_for_each_entry_reverse(border_t, b, head, list) {
 498                 const ir_node *irn = b->irn;
 499                 if (!is_possible_color(n, pi->curr_col))
 500                         continue;
 501
 502                 if (b->is_def) {
 503                         DBG((dbg, LEVEL_2, "Def %n\n", irn));
 504                         pset_insert_ptr(living, irn);
 505                         phase = growing;
 506                 } else { /* is_use */
 507                         DBG((dbg, LEVEL_2, "Use %n\n", irn));
 508
 509                         /* before shrinking the set, store the current 'maximum' clique;
 510                          * do NOT if clique is a single node
 511                          * do NOT if all values are live_in (in this case they were contained in a live-out clique elsewhere) */
 512                         if (phase == growing && pset_count(living) >= 2 && !all_live_in(block, living)) {
 513                                 ir_node *n;
 514                                 for (n = pset_first(living); n; n = pset_next(living)) {
 515                                         int pos = pi_get_pos(pi, get_irn_graph_nr(n), pi->curr_color);
 516                                         matrix_set(pi->B, pi->curr_row, pos, 1);
 517                                         DBG((dbg, LEVEL_2, "B[%d, %d] := %d\n", pi->curr_row, pos, 1));
 518                                 }
 519                                 pi->curr_row++;
 520                         }
 521                         pset_remove_ptr(living, irn);
 522                         phase = shrinking;
 523                 }
 524         }
 525
 526         del_pset(living);
 527 }
 528
 529 /**
 530  * Generate the initial problem matrices and vectors.
 531  */
 532 static problem_instance_t *new_pi(const copy_opt_t *co) {
 533         DBG((dbg, LEVEL_1, "Generating new instance...\n"));
 534         problem_instance_t *pi = calloc(1, sizeof(*pi));
 535         pi->irg = co->irg;
 536         pi->name =      get_entity_name(get_irg_entity(co->irg));
 537         pi->num2pos = new_set(set_cmp_num2pos, SLOTS_NUM2POS);
 538         pi->bigM = 1;
 539
 540         /* Vector x
 541          * one entry per node and possible color */
 542         obstack_init(&pi->ob);
 543         dom_tree_walk_irg(co->irg, pi_collect_x_names, NULL, pi);
 544         pi->x = obstack_finish(&pi->ob);
 545
 546         /* Matrix Q
 547          * weights for the 'same-color-optimization' target */
 548         {
 549                 unit_t *curr;
 550                 pi->Q = new_matrix(pi->x_dim, pi->x_dim);
 551
 552                 list_for_each_entry(unit_t, curr, &co->units, units) {
 553                         const ir_node *root, *arg;
 554                         int rootnr, argnr;
 555                         unsigned rootpos, argpos;
 556                         int i;
 557
 558                         root = curr->nodes[0];
 559                         rootnr = get_irn_graph_nr(root);
 560                         rootpos = pi_get_first_pos(pi, rootnr);
 561                         for (i = 1; i < curr->node_count; ++i) {
 562                                 int weight = -get_weight(root, arg);
 563                                 arg = curr->nodes[i];
 564                                 argnr = get_irn_graph_nr(arg);
 565                                 argpos = pi_get_first_pos(pi, argnr);
 566
 567                                 DBG((dbg, LEVEL_2, "Q[%n, %n] := %d\n", root, arg, weight));
 568                                 /* for all colors root and arg have in common, set the weight for
 569                                  * this pair in the objective function matrix Q */
 570                                 while (rootpos < pi->x_dim && argpos < pi->x_dim &&
 571                                                 pi->x[rootpos].n == rootnr && pi->x[argpos].n == argnr) {
 572                                         if (pi->x[rootpos].c < pi->x[argpos].c)
 573                                                 ++rootpos;
 574                                         else if (pi->x[rootpos].c > pi->x[argpos].c)
 575                                                 ++argpos;
 576                                         else {
 577                                                 matrix_set(pi->Q, rootpos++, argpos++, weight);
 578
 579                                                 if (weight < pi->minQij) {
 580                                                         DBG((dbg, LEVEL_2, "minQij = %d\n", weight));
 581                                                         pi->minQij = weight;
 582                                                 }
 583                                                 if (weight > pi->maxQij) {
 584                                                         DBG((dbg, LEVEL_2, "maxQij = %d\n", weight));
 585                                                         pi->maxQij = weight;
 586                                                 }
 587                                         }
 588                                 }
 589                         }
 590                 }
 591         }
 592
 593         /* Matrix A
 594          * knapsack constraint for each node */
 595         {
 596                 int row = 0, col = 0;
 597                 pi->A = new_matrix(pi->A_dim, pi->x_dim);
 598                 while (col < pi->x_dim) {
 599                         int curr_n = pi->x[col].n;
 600                         while (col < pi->x_dim && pi->x[col].n == curr_n) {
 601                                 DBG((dbg, LEVEL_2, "A[%d, %d] := %d\n", row, col, 1));
 602                                 matrix_set(pi->A, row, col++, 1);
 603                         }
 604                         ++row;
 605                 }
 606                 assert(row == pi->A_dim);
 607         }
 608
 609         /* Matrix B
 610          * interference constraints using exactly those cliques not contained in others. */
 611         {
 612                 int color, expected_clipques = pi->A_dim/3 * MAX_COLORS;
 613                 pi->B = new_matrix(expected_clipques, pi->x_dim);
 614                 for (color = 0; color < MAX_COLORS; ++color) {
 615                         pi->curr_color = color;
 616                         dom_tree_walk_irg(pi->irg, pi_clique_finder, NULL, pi);
 617                 }
 618                 pi->B_dim = matrix_get_rowcount(pi->B);
 619         }
 620
 621         return pi;
 622 }
 623
 624 /**
 625  * clean the problem instance
 626  */
 627 static void free_pi(problem_instance_t *pi) {
 628         del_matrix(pi->Q);
 629         del_matrix(pi->A);
 630         del_matrix(pi->B);
 631         del_set(pi->num2pos);
 632         obstack_free(&pi->ob, NULL);
 633         free(pi);
 634 }
 635
 636 void co_ilp_opt(copy_opt_t *co) {
 637         dbg = firm_dbg_register("ir.be.copyoptilp");
 638         firm_dbg_set_mask(dbg, DEBUG_LVL);
 639
 640         problem_instance_t *pi = new_pi(co);
 641
 642 #ifdef DUMP_MATRICES
 643         pi_dump_matrices(pi);
 644 #endif
 645
 646 #ifdef DUMP_LP
 647         pi_dump_lp(pi);
 648 #endif
 649
 650 #ifdef DUMP_MPS
 651         pi_dump_mps(pi);
 652 #endif
 653
 654 #ifdef DO_SOLVE
 655         pi_solve_ilp(pi);
 656         pi_apply_solution(pi);
 657 #endif
 658
 659 #ifdef DELETE_FILES
 660         pi_delete_files(pi);
 661 #endif
 662
 663         free_pi(pi);
 664 }