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

   1 /**
   2  * Author:      Daniel Grund
   3  * Date:                12.04.2005
   4  * Copyright:   (c) Universitaet Karlsruhe
   5  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
   6
   7  * Minimizing copies with an exact algorithm using mixed integer programming (MIP).
   8  * Problem statement as a 'quadratic 0-1 program with linear constraints' with
   9  * n binary variables. Constraints are knapsack (enforce color for each node) and
  10  * cliques of ifg (interference constraints).
  11  * Transformation into a 'mixed integer program' with n binary variables and
  12  * additional 2n real variables. Constraints are the above the transformed
  13  * objective function and 'complementary conditions' for two var classes.
  14  * @author Daniel Grund
  15  *
  16  * NOTE:
  17  * MPS means NOT the old-style, fixed-column format. Some white spaces are
  18  * important. In general spaces are separators, MARKER-lines are used in COLUMN
  19  * section to define binaries. BETTER use last 2 fields in COLUMNS section.
  20  * See MPS docu for details
  21  *
  22  * Unfortunately no good solver is available locally (or even for linking)
  23  * We use CPLEX 9.0 which runs on a machine residing at the Rechenzentrum.
  24  */
  25 #ifdef HAVE_CONFIG_H
  26 #include "config.h"
  27 #endif
  28
  29 #ifdef HAVE_ALLOCA_H
  30 #include <alloca.h>
  31 #endif
  32 #ifdef HAVE_MALLOC_H
  33 #include <malloc.h>
  34 #endif
  35
  36 #include <sys/types.h>
  37 #include <sys/stat.h>
  38
  39 #include "xmalloc.h"
  40 #include "becopyopt.h"
  41 #include "becopystat.h"
  42
  43 #undef DUMP_MATRICES            /**< dumps all matrices completely. only recommended for small problems */
  44 #undef DUMP_Q2ILP                       /**< see function pi_dump_q2ilp */
  45 #define DUMP_DILP                       /**< see function pi_dump_dilp */
  46 #define DO_SOLVE                        /**< solve the MPS output with CPLEX */
  47 #undef DELETE_FILES             /**< deletes all dumped files after use */
  48
  49 /* CPLEX-account related stuff */
  50 #define SSH_USER_HOST "kb61@sp-smp.rz.uni-karlsruhe.de"
  51 #define SSH_PASSWD_FILE "/ben/daniel/.smppw"
  52 #define EXPECT_FILENAME "runme" /* name of the expect-script */
  53
  54 #define DEBUG_LVL SET_LEVEL_1
  55 static firm_dbg_module_t *dbg = NULL;
  56
  57 #define SLOTS_NUM2POS 256
  58 #define SLOTS_LIVING 32
  59
  60 /* get_weight represents the _gain_ if node n and m have the same color. */
  61 #define get_weight(n,m) 1
  62
  63 /**
  64  * A type storing names of the x variables in the form x[NUMBER]_[COLOR]
  65  */
  66 typedef struct _x_name_t {
  67         int n, c;
  68 } x_name_t;
  69
  70 /**
  71  * For each node taking part in the opt-problem its position in the
  72  * x-variable-vector is stored in a set. This set maps the node-nr (given by
  73  * benumb) to the position in the vector.
  74  */
  75 typedef struct _num2pos_t {
  76         int num, pos;
  77 } num2pos_t;
  78
  79 typedef struct _simpl_t {
  80         struct list_head chain;
  81         if_node_t *ifn;
  82 } simpl_t;
  83
  84 /**
  85  * A type storing the unmodified '0-1 quadratic program' of the form
  86  * min f = xQx
  87  * udN:  Ax  = e
  88  *       Bx <= e
  89  *        x \in {0, 1}
  90  *
  91  * This problem is called the original problem
  92  */
  93 typedef struct _problem_instance_t {
  94         const copy_opt_t *co;                   /** the original copy_opt problem */
  95         int x_dim, A_dim, B_dim, E_dim, c_dim;          /**< number of: x variables (equals Q_dim), rows in A, rows in B */
  96         sp_matrix_t *Q, *A, *B, *E, *c;         /**< the (sparse) matrices of this problem */
  97         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. */
  98         set *num2pos;                                   /**< maps node numbers to positions in x. */
  99
 100         /* problem size reduction removing simple nodes */
 101         struct list_head simplicials;   /**< holds all simpl_t's in right order to color*/
 102         pset *removed;                                  /**< holds all removed simplicial irns */
 103
 104         /* needed for linearization */
 105         int bigM, maxQij, minQij;
 106
 107         /* overhead needed to build this */
 108         struct obstack ob;
 109         int curr_color;
 110         int curr_row;
 111 } problem_instance_t;
 112
 113 #define is_removed(irn) pset_find_ptr(pi->removed, irn)
 114
 115 /* Nodes have consecutive numbers so this hash shoud be fine */
 116 #define HASH_NUM(num) num
 117
 118 static int set_cmp_num2pos(const void *x, const void *y, size_t size) {
 119         return ((num2pos_t *)x)->num != ((num2pos_t *)y)->num;
 120 }
 121
 122 /**
 123  * Sets the first position of node with number num to pos.
 124  * See x_name_t *x in _problem_instance_t.
 125  */
 126 static INLINE void pi_set_first_pos(problem_instance_t *pi, int num, int pos) {
 127         num2pos_t find;
 128         find.num = num;
 129         find.pos = pos;
 130         set_insert(pi->num2pos, &find, sizeof(find), HASH_NUM(num));
 131 }
 132
 133 /**
 134  * Get position by number. (First possible color)
 135  * returns -1 if not found.
 136  */
 137 static INLINE int pi_get_first_pos(problem_instance_t *pi, int num) {
 138         num2pos_t find, *found;
 139         find.num = num;
 140         found = set_find(pi->num2pos, &find, sizeof(find), HASH_NUM(num));
 141         if (found) {
 142                 assert(pi->x[found->pos].n == num && (found->pos == 0 || pi->x[found->pos-1].n != num) && "pi->num2pos is broken!");
 143                 return found->pos;
 144         } else
 145                 return -1;
 146 }
 147
 148 /**
 149  * Get position by number and color.
 150  * returns -1 if not found.
 151  */
 152 static INLINE int pi_get_pos(problem_instance_t *pi, int num, int col) {
 153         num2pos_t find, *found;
 154         int pos;
 155
 156         find.num = num;
 157         found = set_find(pi->num2pos, &find, sizeof(find), HASH_NUM(num));
 158         if (!found)
 159                 return -1;
 160         pos = found->pos;
 161         while (pos < pi->x_dim && pi->x[pos].n == num && pi->x[pos].c < col)
 162                 pos++;
 163
 164         if (pi->x[pos].n == num && pi->x[pos].c == col)
 165                 return pos;
 166         else
 167                 return -1;
 168 }
 169
 170 /**
 171  * Collects all irns in currently processed register class
 172  */
 173 static void pi_collect_x_names(ir_node *block, void *env) {
 174         problem_instance_t *pi = env;
 175         struct list_head *head = &get_ra_block_info(block)->border_head;
 176         border_t *curr;
 177         bitset_t *pos_regs = bitset_alloca(pi->co->cls->n_regs);
 178
 179         list_for_each_entry_reverse(border_t, curr, head, list)
 180                 if (curr->is_def && curr->is_real && !is_removed(curr->irn)) {
 181                         x_name_t xx;
 182                         pi->A_dim++;                    /* one knapsack constraint for each node */
 183
 184                         xx.n = get_irn_graph_nr(curr->irn);
 185                         pi_set_first_pos(pi, xx.n, pi->x_dim);
 186
 187                         // iterate over all possible colors in order
 188                         bitset_clear_all(pos_regs);
 189                         arch_get_allocatable_regs(pi->co->env, curr->irn, arch_pos_make_out(0), pi->co->cls, pos_regs);
 190                         bitset_foreach(pos_regs, xx.c) {
 191                                 DBG((dbg, LEVEL_2, "Adding %n %d\n", curr->irn, xx.c));
 192                                 obstack_grow(&pi->ob, &xx, sizeof(xx));
 193                                 pi->x_dim++;            /* one x variable for each node and color */
 194                         }
 195                 }
 196 }
 197
 198 /**
 199  * Checks if all nodes in living are live_out in block block.
 200  */
 201 static INLINE int all_live_in(ir_node *block, pset *living) {
 202         ir_node *n;
 203         for (n = pset_first(living); n; n = pset_next(living))
 204                 if (!is_live_in(block, n)) {
 205                         pset_break(living);
 206                         return 0;
 207                 }
 208         return 1;
 209 }
 210
 211 /**
 212  * Finds cliques in the interference graph, considering only nodes
 213  * for which the color pi->curr_color is possible. Finds only 'maximal-cliques',
 214  * viz cliques which are not conatained in another one.
 215  * This is used for the matrix B.
 216  */
 217 static void pi_clique_finder(ir_node *block, void *env) {
 218         problem_instance_t *pi = env;
 219         enum phase_t {growing, shrinking} phase = growing;
 220         struct list_head *head = &get_ra_block_info(block)->border_head;
 221         border_t *b;
 222         pset *living = pset_new_ptr(SLOTS_LIVING);
 223
 224         list_for_each_entry_reverse(border_t, b, head, list) {
 225                 const ir_node *irn = b->irn;
 226                 if (is_removed(irn))
 227                         continue;
 228
 229                 if (b->is_def) {
 230                         DBG((dbg, LEVEL_2, "Def %n\n", irn));
 231                         pset_insert_ptr(living, irn);
 232                         phase = growing;
 233                 } else { /* is_use */
 234                         DBG((dbg, LEVEL_2, "Use %n\n", irn));
 235
 236                         /* before shrinking the set, store the current 'maximum' clique;
 237                          * do NOT if clique is a single node
 238                          * do NOT if all values are live_in (in this case they were contained in a live-out clique elsewhere) */
 239                         if (phase == growing && pset_count(living) >= 2 && !all_live_in(block, living)) {
 240                                 ir_node *n;
 241                                 for (n = pset_first(living); n; n = pset_next(living)) {
 242                                         int pos = pi_get_pos(pi, get_irn_graph_nr(n), pi->curr_color);
 243                                         matrix_set(pi->B, pi->curr_row, pos, 1);
 244                                         DBG((dbg, LEVEL_2, "B[%d, %d] := %d\n", pi->curr_row, pos, 1));
 245                                 }
 246                                 pi->curr_row++;
 247                         }
 248                         pset_remove_ptr(living, irn);
 249                         phase = shrinking;
 250                 }
 251         }
 252
 253         del_pset(living);
 254 }
 255
 256 static INLINE int pi_is_simplicial(problem_instance_t *pi, const if_node_t *ifn) {
 257         int i, o, size = 0;
 258         if_node_t **all, *curr;
 259         all = alloca(ifn_get_degree(ifn) * sizeof(*all));
 260
 261         /* get all non-removed neighbors */
 262         foreach_neighb(ifn, curr)
 263                 if (!is_removed(curr))
 264                         all[size++] = curr;
 265
 266         /* check if these form a clique */
 267         for (i=0; i<size; ++i)
 268                 for (o=i+1; o<size; ++o)
 269                         if (!ifg_has_edge(pi->co->irg, all[i], all[o]))
 270                                 return 0;
 271
 272         /* all edges exist so this is a clique */
 273         return 1;
 274 }
 275
 276 static void pi_find_simplicials(problem_instance_t *pi) {
 277         set *if_nodes;
 278         if_node_t *ifn;
 279         int redo = 1;
 280
 281         if_nodes = be_ra_get_ifg_nodes(pi->co->irg);
 282         while (redo) {
 283                 redo = 0;
 284                 for (ifn = set_first(if_nodes); ifn; ifn = set_next(if_nodes)) {
 285                         ir_node *irn = get_irn_for_graph_nr(pi->co->irg, ifn->nnr);
 286                         if (!is_removed(irn) && !is_optimizable(irn) && !is_optimizable_arg(irn) && pi_is_simplicial(pi, ifn)) {
 287                                 simpl_t *s = xmalloc(sizeof(*s));
 288                                 s->ifn = ifn;
 289                                 list_add(&s->chain, &pi->simplicials);
 290                                 pset_insert_ptr(pi->removed, irn);
 291                                 redo = 1;
 292                                 DBG((dbg, LEVEL_1, " Removed %n\n", irn));
 293                         }
 294                 }
 295         }
 296 }
 297
 298 /**
 299  * Generate the initial problem matrices and vectors.
 300  */
 301 static problem_instance_t *new_pi(const copy_opt_t *co) {
 302         DBG((dbg, LEVEL_1, "Generating new instance...\n"));
 303         problem_instance_t *pi = xcalloc(1, sizeof(*pi));
 304         pi->co = co;
 305         pi->num2pos = new_set(set_cmp_num2pos, SLOTS_NUM2POS);
 306         pi->bigM = 1;
 307         pi->removed = pset_new_ptr_default();
 308         INIT_LIST_HEAD(&pi->simplicials);
 309
 310         /* problem size reduction */
 311         pi_find_simplicials(pi);
 312
 313         //TODO dump_ifg_wo_removed
 314
 315         /* Vector x
 316          * one entry per node and possible color */
 317         obstack_init(&pi->ob);
 318         dom_tree_walk_irg(co->irg, pi_collect_x_names, NULL, pi);
 319         pi->x = obstack_finish(&pi->ob);
 320
 321         /* Matrix Q and E
 322          * weights for the 'same-color-optimization' target */
 323         {
 324                 unit_t *curr;
 325                 pi->Q = new_matrix(pi->x_dim, pi->x_dim);
 326                 pi->E = new_matrix(pi->x_dim, pi->x_dim);
 327                 pi->c = new_matrix(1, pi->x_dim);
 328
 329                 list_for_each_entry(unit_t, curr, &co->units, units) {
 330                         const ir_node *root, *arg;
 331                         int rootnr, argnr;
 332                         unsigned save_rootpos, rootpos, argpos;
 333                         int i;
 334
 335                         root = curr->nodes[0];
 336                         rootnr = get_irn_graph_nr(root);
 337                         save_rootpos = pi_get_first_pos(pi, rootnr);
 338                         for (i = 1; i < curr->node_count; ++i) {
 339                                 int weight;
 340                                 rootpos = save_rootpos;
 341                                 arg = curr->nodes[i];
 342                                 argnr = get_irn_graph_nr(arg);
 343                                 argpos = pi_get_first_pos(pi, argnr);
 344                                 weight = -get_weight(root, arg);
 345
 346                                 DBG((dbg, LEVEL_2, "Q[%n, %n] := %d\n", root, arg, weight));
 347                                 /* for all colors root and arg have in common, set the weight for
 348                                  * this pair in the objective function matrix Q */
 349                                 while (rootpos < pi->x_dim && argpos < pi->x_dim &&
 350                                                 pi->x[rootpos].n == rootnr && pi->x[argpos].n == argnr) {
 351                                         if (pi->x[rootpos].c < pi->x[argpos].c)
 352                                                 ++rootpos;
 353                                         else if (pi->x[rootpos].c > pi->x[argpos].c)
 354                                                 ++argpos;
 355                                         else {
 356                                                 /* E */
 357                                                 matrix_set(pi->E, pi->E_dim, rootpos, +1);
 358                                                 matrix_set(pi->E, pi->E_dim, argpos,  -1);
 359                                                 matrix_set(pi->E, pi->E_dim, pi->x_dim + pi->c_dim, 1);
 360                                                 pi->E_dim++;
 361                                                 matrix_set(pi->E, pi->E_dim, rootpos, -1);
 362                                                 matrix_set(pi->E, pi->E_dim, argpos,  +1);
 363                                                 matrix_set(pi->E, pi->E_dim, pi->x_dim + pi->c_dim, 1);
 364                                                 pi->E_dim++;
 365
 366                                                 /* Q */
 367                                                 matrix_set(pi->Q, rootpos, argpos, weight + matrix_get(pi->Q, rootpos, argpos));
 368                                                 rootpos++;
 369                                                 argpos++;
 370                                                 if (weight < pi->minQij) {
 371                                                         DBG((dbg, LEVEL_2, "minQij = %d\n", weight));
 372                                                         pi->minQij = weight;
 373                                                 }
 374                                                 if (weight > pi->maxQij) {
 375                                                         DBG((dbg, LEVEL_2, "maxQij = %d\n", weight));
 376                                                         pi->maxQij = weight;
 377                                                 }
 378                                         }
 379                                 }
 380
 381                                 /* E */
 382                                 matrix_set(pi->c, 1, pi->c_dim++, -weight);
 383                         }
 384                 }
 385         }
 386
 387         /* Matrix A
 388          * knapsack constraint for each node */
 389         {
 390                 int row = 0, col = 0;
 391                 pi->A = new_matrix(pi->A_dim, pi->x_dim);
 392                 while (col < pi->x_dim) {
 393                         int curr_n = pi->x[col].n;
 394                         while (col < pi->x_dim && pi->x[col].n == curr_n) {
 395                                 DBG((dbg, LEVEL_2, "A[%d, %d] := %d\n", row, col, 1));
 396                                 matrix_set(pi->A, row, col++, 1);
 397                         }
 398                         ++row;
 399                 }
 400                 assert(row == pi->A_dim);
 401         }
 402
 403         /* Matrix B
 404          * interference constraints using exactly those cliques not contained in others. */
 405         {
 406                 int color, expected_clipques = pi->A_dim/4 * pi->co->cls->n_regs;
 407                 pi->B = new_matrix(expected_clipques, pi->x_dim);
 408                 for (color = 0; color < pi->co->cls->n_regs; ++color) {
 409                         pi->curr_color = color;
 410                         dom_tree_walk_irg(pi->co->irg, pi_clique_finder, NULL, pi);
 411                 }
 412                 pi->B_dim = matrix_get_rowcount(pi->B);
 413         }
 414
 415         return pi;
 416 }
 417
 418 /**
 419  * clean the problem instance
 420  */
 421 static void free_pi(problem_instance_t *pi) {
 422         DBG((dbg, LEVEL_1, "Free instance...\n"));
 423         del_matrix(pi->Q);
 424         del_matrix(pi->A);
 425         del_matrix(pi->B);
 426         del_matrix(pi->E);
 427         del_matrix(pi->c);
 428         del_set(pi->num2pos);
 429         del_pset(pi->removed);
 430         obstack_free(&pi->ob, NULL);
 431         free(pi);
 432 }
 433
 434 #ifdef DUMP_MATRICES
 435 /**
 436  * Dump the raw matrices of the problem to a file for debugging.
 437  */
 438 static void pi_dump_matrices(problem_instance_t *pi) {
 439         int i;
 440         FILE *out = ffopen(pi->co->name, "matrix", "wt");
 441
 442         DBG((dbg, LEVEL_1, "Dumping raw...\n"));
 443         fprintf(out, "\n\nx-names =\n");
 444         for (i=0; i<pi->x_dim; ++i)
 445                 fprintf(out, "%5d %2d\n", pi->x[i].n, pi->x[i].c);
 446
 447         fprintf(out, "\n\n-Q =\n");
 448         matrix_dump(pi->Q, out, -1);
 449
 450         fprintf(out, "\n\nA =\n");
 451         matrix_dump(pi->A, out, 1);
 452
 453         fprintf(out, "\n\nB =\n");
 454         matrix_dump(pi->B, out, 1);
 455
 456         fclose(out);
 457 }
 458 #endif
 459
 460 #ifdef DUMP_Q2ILP
 461 /**
 462  * Dumps an mps file representing the problem using a linearization of the
 463  * quadratic programming problem.
 464  */
 465 static void pi_dump_q2ilp(problem_instance_t *pi) {
 466         int i, max_abs_Qij;
 467         const matrix_elem_t *e;
 468         FILE *out;
 469         bitset_t *good_row;
 470         DBG((dbg, LEVEL_1, "Dumping q2ilp...\n"));
 471
 472         max_abs_Qij = pi->maxQij;
 473         if (-pi->minQij > max_abs_Qij)
 474                 max_abs_Qij = -pi->minQij;
 475         pi->bigM = pi->A_dim * max_abs_Qij;
 476         DBG((dbg, LEVEL_2, "BigM = %d\n", pi->bigM));
 477
 478         matrix_optimize(pi->Q);
 479         good_row = bitset_alloca(pi->x_dim);
 480         for (i=0; i<pi->x_dim; ++i)
 481                 if (matrix_row_first(pi->Q, i))
 482                         bitset_set(good_row, i);
 483
 484     out = ffopen(pi->co->name, "q2ilp", "wt");
 485         fprintf(out, "NAME %s\n", pi->co->name);
 486
 487         fprintf(out, "ROWS\n");
 488         fprintf(out, " N obj\n");
 489         for (i=0; i<pi->x_dim; ++i)
 490                 if (bitset_is_set(good_row, i))
 491                         fprintf(out, " E cQ%d\n", i);
 492         for (i=0; i<pi->A_dim; ++i)
 493                 fprintf(out, " E cA%d\n", i);
 494         for (i=0; i<pi->B_dim; ++i)
 495                 fprintf(out, " L cB%d\n", i);
 496         for (i=0; i<pi->x_dim; ++i)
 497                 if (bitset_is_set(good_row, i))
 498                         fprintf(out, " L cy%d\n", i);
 499
 500         fprintf(out, "COLUMNS\n");
 501         /* the x vars come first */
 502         /* mark them as binaries */
 503         fprintf(out, "    MARKI0\t'MARKER'\t'INTORG'\n");
 504         for (i=0; i<pi->x_dim; ++i) {
 505                 /* participation in objective */
 506                 if (bitset_is_set(good_row, i))
 507                         fprintf(out, "    x%d_%d\tobj\t%d\n", pi->x[i].n, pi->x[i].c, -pi->bigM);
 508                 /* in Q */
 509                 matrix_foreach_in_col(pi->Q, i, e)
 510                         fprintf(out, "    x%d_%d\tcQ%d\t%d\n", pi->x[i].n, pi->x[i].c, e->row, e->val);
 511                 /* in A */
 512                 matrix_foreach_in_col(pi->A, i, e)
 513                         fprintf(out, "    x%d_%d\tcA%d\t%d\n", pi->x[i].n, pi->x[i].c, e->row, e->val);
 514                 /* in B */
 515                 matrix_foreach_in_col(pi->B, i, e)
 516                         fprintf(out, "    x%d_%d\tcB%d\t%d\n", pi->x[i].n, pi->x[i].c, e->row, e->val);
 517                 /* in y */
 518                 if (bitset_is_set(good_row, i))
 519                         fprintf(out, "    x%d_%d\tcy%d\t%d\n", pi->x[i].n, pi->x[i].c, i, 2*pi->bigM);
 520         }
 521
 522         fprintf(out, "    MARKI1\t'MARKER'\t'INTEND'\n"); /* end of marking */
 523
 524         /* next the s vars */
 525         for (i=0; i<pi->x_dim; ++i)
 526                 if (bitset_is_set(good_row, i)) {
 527                         /* participation in objective */
 528                         fprintf(out, "    s%d_%d\tobj\t%d\n", pi->x[i].n, pi->x[i].c, 1);
 529                         /* in Q */
 530                         fprintf(out, "    s%d_%d\tcQ%d\t%d\n", pi->x[i].n, pi->x[i].c, i, -1);
 531                 }
 532
 533         /* next the y vars */
 534         for (i=0; i<pi->x_dim; ++i)
 535                 if (bitset_is_set(good_row, i)) {
 536                         /* in Q */
 537                         fprintf(out, "    y%d_%d\tcQ%d\t%d\n", pi->x[i].n, pi->x[i].c, i, -1);
 538                         /* in y */
 539                         fprintf(out, "    y%d_%d\tcy%d\t%d\n", pi->x[i].n, pi->x[i].c, i, 1);
 540                 }
 541
 542         fprintf(out, "RHS\n");
 543         for (i=0; i<pi->x_dim; ++i)
 544                 if (bitset_is_set(good_row, i))
 545                         fprintf(out, "    rhs\tcQ%d\t%d\n", i, -pi->bigM);
 546         for (i=0; i<pi->A_dim; ++i)
 547                 fprintf(out, "    rhs\tcA%d\t%d\n", i, 1);
 548         for (i=0; i<pi->B_dim; ++i)
 549                 fprintf(out, "    rhs\tcB%d\t%d\n", i, 1);
 550         for (i=0; i<pi->x_dim; ++i)
 551                 if (bitset_is_set(good_row, i))
 552                         fprintf(out, "    rhs\tcy%d\t%d\n", i, 2*pi->bigM);
 553
 554         fprintf(out, "ENDATA\n");
 555         fclose(out);
 556 }
 557 #endif
 558
 559 #ifdef DUMP_DILP
 560 /**
 561  * Dumps an mps file representing the problem using directly a formalization as ILP.
 562  */
 563 static void pi_dump_dilp(problem_instance_t *pi) {
 564         int i;
 565         const matrix_elem_t *e;
 566         FILE *out;
 567         DBG((dbg, LEVEL_1, "Dumping dilp...\n"));
 568
 569         out = ffopen(pi->co->name, "dilp", "wt");
 570         fprintf(out, "NAME %s\n", pi->co->name);
 571         fprintf(out, "OBJSENSE\n   MAX\n");
 572
 573         fprintf(out, "ROWS\n");
 574         fprintf(out, " N obj\n");
 575         for (i=0; i<pi->A_dim; ++i)
 576                 fprintf(out, " E cA%d\n", i);
 577         for (i=0; i<pi->B_dim; ++i)
 578                 fprintf(out, " L cB%d\n", i);
 579         for (i=0; i<pi->E_dim; ++i)
 580                 fprintf(out, " L cE%d\n", i);
 581
 582         fprintf(out, "COLUMNS\n");
 583         /* the x vars come first */
 584         /* mark them as binaries */
 585         fprintf(out, "    MARKI0\t'MARKER'\t'INTORG'\n");
 586         for (i=0; i<pi->x_dim; ++i) {
 587                 /* in A */
 588                 matrix_foreach_in_col(pi->A, i, e)
 589                         fprintf(out, "    x%d_%d\tcA%d\t%d\n", pi->x[i].n, pi->x[i].c, e->row, e->val);
 590                 /* in B */
 591                 matrix_foreach_in_col(pi->B, i, e)
 592                         fprintf(out, "    x%d_%d\tcB%d\t%d\n", pi->x[i].n, pi->x[i].c, e->row, e->val);
 593                 /* in E */
 594                 matrix_foreach_in_col(pi->E, i, e)
 595                         fprintf(out, "    x%d_%d\tcE%d\t%d\n", pi->x[i].n, pi->x[i].c, e->row, e->val);
 596         }
 597         fprintf(out, "    MARKI1\t'MARKER'\t'INTEND'\n"); /* end of marking */
 598
 599         /* next the y vars */
 600         for (i=0; i<pi->c_dim; ++i) {
 601                 /* in Objective */
 602                 fprintf(out, "    y%d\tobj\t%d\n", i, matrix_get(pi->c, 1, i));
 603                 /* in E */
 604                 matrix_foreach_in_col(pi->E, pi->x_dim+i, e)
 605                         fprintf(out, "    y%d\tcE%d\t%d\n", i, e->row, e->val);
 606         }
 607
 608         fprintf(out, "RHS\n");
 609         for (i=0; i<pi->A_dim; ++i)
 610                 fprintf(out, "    rhs\tcA%d\t%d\n", i, 1);
 611         for (i=0; i<pi->B_dim; ++i)
 612                 fprintf(out, "    rhs\tcB%d\t%d\n", i, 1);
 613         for (i=0; i<pi->E_dim; ++i)
 614                 fprintf(out, "    rhs\tcE%d\t%d\n", i, 1);
 615
 616         fprintf(out, "ENDATA\n");
 617         fclose(out);
 618 }
 619 #endif
 620
 621 #ifdef DO_SOLVE
 622 /**
 623  * Dumps the known solution to a file to make use of it
 624  * as a starting solution respectively as a bound
 625  */
 626 static void pi_dump_start_sol(problem_instance_t *pi) {
 627         int i;
 628         FILE *out = ffopen(pi->co->name, "mst", "wt");
 629         fprintf(out, "NAME\n");
 630         for (i=0; i<pi->x_dim; ++i) {
 631                 int val, n, c;
 632                 n = pi->x[i].n;
 633                 c = pi->x[i].c;
 634                 if (get_irn_col(pi->co, get_irn_for_graph_nr(pi->co->irg, n)) == c)
 635                         val = 1;
 636                 else
 637                         val = 0;
 638                 fprintf(out, "    x%d_%d\t%d\n", n, c, val);
 639         }
 640         fprintf(out, "ENDATA\n");
 641         fclose(out);
 642 }
 643
 644 /**
 645  * Invoke an external solver
 646  */
 647 static void pi_solve_ilp(problem_instance_t *pi) {
 648         FILE *out, *pwfile;
 649         char passwd[128];
 650
 651         DBG((dbg, LEVEL_1, "Solving with CPLEX@RZ...\n"));
 652         /* write command file for CPLEX */
 653         out = ffopen(pi->co->name, "cmd", "wt");
 654         fprintf(out, "set logfile %s.sol\n", pi->co->name);
 655 #ifdef DUMP_Q2ILP
 656         fprintf(out, "read %s.q2ilp mps\n", pi->co->name);
 657 #endif
 658 #ifdef DUMP_DILP
 659         fprintf(out, "read %s.dilp mps\n", pi->co->name);
 660 #endif
 661         fprintf(out, "read %s.mst\n", pi->co->name);
 662         fprintf(out, "set mip strategy mipstart 1\n");
 663         //fprintf(out, "set mip emphasis 3\n");
 664         fprintf(out, "optimize\n");
 665         fprintf(out, "display solution variables 1-%d\n", pi->x_dim);
 666         fprintf(out, "quit\n");
 667         fclose(out);
 668
 669         /* write expect-file for copying problem to RZ */
 670         pwfile = fopen(SSH_PASSWD_FILE, "rt");
 671         fgets(passwd, sizeof(passwd), pwfile);
 672         fclose(pwfile);
 673
 674         out = ffopen(EXPECT_FILENAME, "exp", "wt");
 675         fprintf(out, "#! /usr/bin/expect\n");
 676         fprintf(out, "spawn scp %s.dilp %s.q2ilp %s.mst %s.cmd %s:\n", pi->co->name, pi->co->name, pi->co->name, pi->co->name, SSH_USER_HOST); /* copy problem files */
 677         fprintf(out, "expect \"word:\"\nsend \"%s\\n\"\ninteract\n", passwd);
 678
 679         fprintf(out, "spawn ssh %s \"./cplex90 < %s.cmd\"\n", SSH_USER_HOST, pi->co->name); /* solve */
 680         fprintf(out, "expect \"word:\"\nsend \"%s\\n\"\ninteract\n", passwd);
 681
 682         fprintf(out, "spawn scp %s:%s.sol .\n", SSH_USER_HOST, pi->co->name); /*copy back solution */
 683         fprintf(out, "expect \"word:\"\nsend \"%s\\n\"\ninteract\n", passwd);
 684
 685         fprintf(out, "spawn ssh %s ./dell\n", SSH_USER_HOST); /* clean files on server */
 686         fprintf(out, "expect \"word:\"\nsend \"%s\\n\"\ninteract\n", passwd);
 687
 688         fclose(out);
 689
 690         /* call the expect script */
 691         chmod(EXPECT_FILENAME ".exp", 0700);
 692         system(EXPECT_FILENAME ".exp");
 693 }
 694
 695 static void pi_set_simplicials(problem_instance_t *pi) {
 696         simpl_t *simpl, *tmp;
 697         bitset_t *used_cols = bitset_alloca(arch_register_class_n_regs(pi->co->cls));
 698
 699         /* color the simplicial nodes in right order */
 700         list_for_each_entry_safe(simpl_t, simpl, tmp, &pi->simplicials, chain) {
 701                 int free_col;
 702                 ir_node *other_irn, *irn;
 703                 if_node_t *other, *ifn;
 704
 705                 /* get free color by inspecting all neighbors */
 706                 ifn = simpl->ifn;
 707                 irn = get_irn_for_graph_nr(pi->co->irg, ifn->nnr);
 708                 bitset_clear_all(used_cols);
 709                 foreach_neighb(ifn, other) {
 710                         other_irn = get_irn_for_graph_nr(pi->co->irg, other->nnr);
 711                         if (!is_removed(other_irn)) /* only inspect nodes which are in graph right now */
 712                                 bitset_set(used_cols, get_irn_col(pi->co, other_irn));
 713                 }
 714
 715                 /* now all bits not set are possible colors */
 716                 free_col = bitset_next_clear(used_cols, 0);
 717                 assert(free_col != -1 && "No free color found. This can not be.");
 718                 set_irn_col(pi->co, irn, free_col);
 719                 pset_remove_ptr(pi->removed, irn); /* irn is back in graph again */
 720                 free(simpl);
 721         }
 722 }
 723
 724 /**
 725  * Sets the colors of irns according to the values of variables found in the
 726  * output file of the solver.
 727  */
 728 static void pi_apply_solution(problem_instance_t *pi) {
 729         FILE *in ;
 730
 731         if (!(in = ffopen(pi->co->name, "sol", "rt")))
 732                 return;
 733         DBG((dbg, LEVEL_1, "Applying solution...\n"));
 734         while (!feof(in)) {
 735                 char buf[1024];
 736                 int num = -1, col = -1, val = -1;
 737
 738                 fgets(buf, sizeof(buf), in);
 739                 DBG((dbg, LEVEL_3, "Line: %s", buf));
 740
 741                 if (strcmp(buf, "No integer feasible solution exists.") == 0)
 742                         assert(0 && "CPLEX says: No integer feasible solution exists!");
 743
 744                 if (strcmp(buf, "TODO Out of memory") == 0) {}
 745
 746 #ifdef DO_STAT
 747                 {
 748                         /* solution time */
 749                         float sol_time;
 750                         int iter;
 751                         if (sscanf(buf, "Solution time = %f sec. Iterations = %d", &sol_time, &iter) == 2) {
 752                                 DBG((dbg, LEVEL_2, " Time: %f Iter: %d\n", sol_time, iter));
 753                                 curr_vals[I_ILP_TIME] += 10 * sol_time;
 754                                 curr_vals[I_ILP_ITER] += iter;
 755                         }
 756                 }
 757 #endif
 758
 759                 /* variable value */
 760                 if (sscanf(buf, "x%d_%d %d", &num, &col, &val) == 3 && val == 1) {
 761                         DBG((dbg, LEVEL_2, " x%d_%d = %d\n", num, col, val));
 762                         set_irn_col(pi->co, get_irn_for_graph_nr(pi->co->irg, num), col);
 763                 }
 764         }
 765         fclose(in);
 766         pi_set_simplicials(pi);
 767 }
 768 #endif /* DO_SOLVE */
 769
 770 #ifdef DELETE_FILES
 771 static void pi_delete_files(problem_instance_t *pi) {
 772         char buf[1024];
 773         int end = snprintf(buf, sizeof(buf), "%s", pi->co->name);
 774         DBG((dbg, LEVEL_1, "Deleting files...\n"));
 775 #ifdef DUMP_MATRICES
 776         snprintf(buf+end, sizeof(buf)-end, ".matrix");
 777         remove(buf);
 778 #endif
 779 #ifdef DUMP_Q2ILP
 780         snprintf(buf+end, sizeof(buf)-end, ".q2ilp");
 781         remove(buf);
 782 #endif
 783 #ifdef DUMP_DILP
 784         snprintf(buf+end, sizeof(buf)-end, ".dilp");
 785         remove(buf);
 786 #endif
 787 #ifdef DO_SOLVE
 788         snprintf(buf+end, sizeof(buf)-end, ".cmd");
 789         remove(buf);
 790         snprintf(buf+end, sizeof(buf)-end, ".mst");
 791         remove(buf);
 792         snprintf(buf+end, sizeof(buf)-end, ".sol");
 793         remove(buf);
 794         remove(EXPECT_FILENAME ".exp");
 795 #endif
 796 }
 797 #endif
 798
 799 void co_ilp_opt(copy_opt_t *co) {
 800         problem_instance_t *pi;
 801
 802         dbg = firm_dbg_register("ir.be.copyoptilp");
 803         firm_dbg_set_mask(dbg, DEBUG_LVL);
 804         if (!strcmp(co->name, DEBUG_IRG))
 805                 firm_dbg_set_mask(dbg, -1);
 806
 807         pi = new_pi(co);
 808         DBG((dbg, 0, "\t\t\t %5d %5d %5d\n", pi->x_dim, pi->A_dim, pi->B_dim));
 809
 810         if (pi->x_dim > 0) {
 811 #ifdef DUMP_MATRICES
 812         pi_dump_matrices(pi);
 813 #endif
 814
 815 #ifdef DUMP_Q2ILP
 816         pi_dump_q2ilp(pi);
 817 #endif
 818
 819 #ifdef DUMP_DILP
 820         pi_dump_dilp(pi);
 821 #endif
 822
 823 #ifdef DO_SOLVE
 824         pi_dump_start_sol(pi);
 825         pi_solve_ilp(pi);
 826         pi_apply_solution(pi);
 827 #endif
 828
 829 #ifdef DELETE_FILES
 830         pi_delete_files(pi);
 831 #endif
 832         }
 833         free_pi(pi);
 834 }