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