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

   1 /**
   2  * @author Daniel Grund
   3  * @date 10.03.2005
   4  */
   5 #ifdef HAVE_CONFIG_H
   6 #include "config.h"
   7 #endif
   8
   9 #include <stdlib.h>
  10 #include <stdio.h>
  11 #define __USE_BSD
  12 #include <string.h>
  13
  14 #include "obst.h"
  15 #include "set.h"
  16 #include "pset.h"
  17 #include "list.h"
  18 #include "debug.h"
  19
  20 #include "irdom.h"
  21 #include "irouts.h"
  22 #include "bephicoalilp_t.h"
  23 #include "benumb_t.h"
  24 #include "bera_t.h"
  25 #include "belive_t.h"
  26 #include "bechordal_t.h"
  27
  28
  29 #define MAX_COLORS 32
  30
  31 /**
  32  * define get_weight to sth representing the _gain_ if node n and m
  33  * have the same color. Must return values MIN_WEIGHT <= . <= MAX_WEIGHT.
  34  */
  35 #define get_weight(n,m) 1
  36 #define MAX_WEIGHT 127
  37 #define MIN_WEIGHT 0
  38
  39 /** define this to sth which returns 0 iff c is NOT a possible color for node n */
  40 #define is_possible_color(n,c) 1
  41
  42 /** define this to sth which returns 1 iff not all colors can be assigned to node n */
  43 #define is_constrained(n) 0
  44
  45 #undef DUMP_MATRICES
  46 #define DUMP_MPS
  47 #undef DUMP_LPO
  48 #undef DUMP_LPP
  49 #define DO_SOLVE
  50 #define DELETE_FILES
  51 #undef USE_SOS
  52 #define SSH_USER_HOST "kb61@sp-smp.rz.uni-karlsruhe.de"
  53
  54 /* The overhead stuff */
  55 #define DEBUG_LVL SET_LEVEL_1
  56 #define SET_LIVING_INIT 32
  57 #define MAX_Q_INIT 0
  58 #define MIN_Q_INIT 0
  59
  60 static firm_dbg_module_t *dbgphi = NULL;
  61
  62 static INLINE FILE *ffopen(const char *base, const char *ext, const char *mode) {
  63         FILE *out;
  64         char buf[1024];
  65
  66         snprintf(buf, sizeof(buf), "%s.%s", base, ext);
  67         if (! (out = fopen(buf, mode))) {
  68                 fprintf(stderr, "Cannot open file %s in mode %s\n", buf, mode);
  69                 return NULL;
  70         }
  71         return out;
  72 }
  73
  74 /** A type storing names of the x variables in the form x[NUMBER]_[COLOR] */
  75 typedef struct _x_vec_t {
  76         int n, c;
  77 } x_vec_t;
  78
  79 /**
  80  * A type storing the unmodified '0-1 quadratic program' of the form
  81  * min f = xQx
  82  * udN:  Ax  = e
  83  *       Bx <= e
  84  *        x \in {0, 1}
  85  *
  86  * This problem is called the original problem
  87  */
  88 typedef struct _problem_instance_t {
  89         ir_graph* irg;
  90         const char *name;
  91         int x_dim, A_dim, B_dim;
  92         char *Q, *A, *B;
  93         x_vec_t *x;                             /**< stores the names of the x variables. Sorted first by node-num then by color. */
  94
  95         /* needed only for linearizations */
  96         int bigM, maxQij, minQij, correction;
  97
  98         /* overhead needed to build this */
  99         set *num2pos;
 100         struct obstack ob;
 101         int curr_col;
 102         int curr_row;
 103 } problem_instance_t;
 104
 105 /**
 106  * For each node taking part in the opt-problem its position in the
 107  * x-variable-vector is stored in a set. This set maps the node-nr (given by
 108  * benumb) to  the position in the vector.
 109  */
 110 typedef struct _num2pos_t {
 111         int num, pos;
 112 } num2pos_t;
 113
 114 /* Nodes have consecutive numbers so... */
 115 #define HASH_NUM(num) num
 116
 117 static int pi_num2pos_cmp(const void *x, const void *y, size_t size) {
 118         return ((num2pos_t *)x)->num != ((num2pos_t *)y)->num;
 119 }
 120
 121 /**
 122  * Sets the first position of node with number num to pos.
 123  * See x_vec_t *x in _problem_instance_t.
 124  */
 125 static INLINE void pi_set_first_pos(problem_instance_t *pi, int num, int pos) {
 126         num2pos_t find;
 127         find.num = num;
 128         find.pos = pos;
 129         set_insert(pi->num2pos, &find, sizeof(find), HASH_NUM(num));
 130 }
 131
 132 /**
 133  * Get position by number. (First possible color)
 134  * returns -1 if not found.
 135  */
 136 static INLINE int pi_get_first_pos(problem_instance_t *pi, int num) {
 137         num2pos_t find, *found;
 138         find.num = num;
 139         found = set_find(pi->num2pos, &find, sizeof(find), HASH_NUM(num));
 140         if (found) {
 141                 assert(pi->x[found->pos].n == num && (found->pos == 0 || pi->x[found->pos-1].n != num) && "pi->num2pos is broken!");
 142                 return found->pos;
 143         } else
 144                 return -1;
 145 }
 146
 147 /**
 148  * Get position by number and color.
 149  * returns -1 if not found.
 150  */
 151 static INLINE int pi_get_pos(problem_instance_t *pi, int num, int col) {
 152         num2pos_t find, *found;
 153         find.num = num;
 154         int pos;
 155         found = set_find(pi->num2pos, &find, sizeof(find), HASH_NUM(num));
 156         if (!found)
 157                 return -1;
 158         pos = found->pos;
 159         while (pos < pi->x_dim && pi->x[pos].n == num && pi->x[pos].c < col)
 160                 pos++;
 161
 162         if (pi->x[pos].n == num && pi->x[pos].c == col)
 163                 return pos;
 164         else
 165                 return -1;
 166 }
 167
 168 /**
 169  * Checks if all nodes in living are live_out in block block.
 170  */
 171 static INLINE int all_live_out(ir_node *block, pset *living) {
 172         ir_node *n;
 173         for (n = pset_first(living); n; n = pset_next(living))
 174                 if (!is_live_out(block, n)) {
 175                         pset_break(living);
 176                         return 0;
 177                 }
 178         return 1;
 179 }
 180
 181 /**
 182  * Finds all cliques in the interference graph, which are not conatained in
 183  * another one (or at least an approximation of that).
 184  * This is used for the matrix B.
 185  */
 186 static void pi_clique_finder(ir_node *block, void *env) {
 187         enum phase_t {growing, shrinking} phase = growing;
 188         problem_instance_t *pi = env;
 189         struct list_head *head = &get_ra_block_info(block)->border_head;
 190         border_t *b;
 191         pset *living = pset_new_ptr(SET_LIVING_INIT);
 192
 193         list_for_each_entry_reverse(border_t, b, head, list) {
 194                 const ir_node *irn = b->irn;
 195                 if (!is_possible_color(n, pi->curr_col))
 196                         continue;
 197
 198                 if (b->is_def) {
 199                         DBG((dbgphi, LEVEL_2, "Def %n\n", irn));
 200                         pset_insert_ptr(living, irn);
 201                         phase = growing;
 202                 } else { /* is_use */
 203                         DBG((dbgphi, LEVEL_2, "Use %n\n", irn));
 204
 205                         /* before shrinking the set store the current 'maximum' clique;
 206                          * do NOT if clique is a single node
 207                          * do NOT if all values are live_out */
 208                         if (phase == growing && pset_count(living) >= 2 && !all_live_out(block, living)) {
 209                                 ir_node *n;
 210                                 for (n = pset_first(living); n; n = pset_next(living)) {
 211                                         int pos = pi_get_pos(pi, get_irn_graph_nr(n), pi->curr_col);
 212                                         pi->B[pi->curr_row*pi->x_dim + pos] = 1;
 213                                         DBG((dbgphi, LEVEL_2, "B[%d, %d] := %d\n", pi->curr_row, pos, 1));
 214                                 }
 215                                 pi->curr_row++;
 216                         }
 217                         pset_remove_ptr(living, irn);
 218                         phase = shrinking;
 219                 }
 220         }
 221
 222         del_pset(living);
 223 }
 224
 225 #ifdef DUMP_MATRICES
 226 /**
 227  * Dump the raw matrices of the problem to a file for debugging.
 228  */
 229 static void pi_dump_matrices(problem_instance_t *pi) {
 230         int i, o;
 231         FILE *out = ffopen(pi->name, "matrix", "wt");
 232
 233         DBG((dbgphi, LEVEL_1, "Dumping raw...\n"));
 234         fprintf(out, "\n\nx-names =\n");
 235         for (i=0; i<pi->x_dim; ++i)
 236                 fprintf(out, "%5d %2d\n", pi->x[i].n, pi->x[i].c);
 237
 238         fprintf(out, "\n\n-Q =\n");
 239         for (i=0; i<pi->x_dim; ++i) {
 240                 for (o=0; o<pi->x_dim; ++o)
 241                         fprintf(out, "%d", -pi->Q[i*pi->x_dim + o]);
 242                 fprintf(out, "\n");
 243         }
 244
 245         fprintf(out, "\n\nA =\n");
 246         for (i=0; i<pi->A_dim; ++i) {
 247                 for (o=0; o<pi->x_dim; ++o)
 248                         fprintf(out, "%d", pi->A[i*pi->x_dim + o]);
 249                 fprintf(out, "\n");
 250         }
 251
 252         fprintf(out, "\n\nB =\n");
 253         for (i=0; i<pi->B_dim; ++i) {
 254                 for (o=0; o<pi->x_dim; ++o)
 255                         fprintf(out, "%d", pi->B[i*pi->x_dim + o]);
 256                 fprintf(out, "\n");
 257         }
 258         fclose(out);
 259 }
 260 #endif
 261
 262 #ifdef DUMP_MPS
 263 /**
 264  * Dumps an mps file representing the problem. This is NOT the old-style,
 265  * fixed-column format. Spaces are separators, MARKER-lines are used in
 266  * COLUMN section to define binaries.
 267  */
 268 static void pi_dump_mps(problem_instance_t *pi) {
 269         int i, o, max_abs_Qij;
 270         FILE *out = ffopen(pi->name, "mps", "wt");
 271
 272         DBG((dbgphi, LEVEL_1, "Dumping mps...\n"));
 273         max_abs_Qij = pi->maxQij;
 274         if (-pi->minQij > max_abs_Qij)
 275                 max_abs_Qij = -pi->minQij;
 276         pi->bigM = pi->A_dim * max_abs_Qij;
 277         DBG((dbgphi, LEVEL_2, "BigM = %d\n", pi->bigM));
 278
 279         fprintf(out, "NAME %s\n", pi->name);
 280
 281         fprintf(out, "ROWS\n");
 282         fprintf(out, " N obj\n");
 283         for (i=0; i<pi->x_dim; ++i)
 284                 fprintf(out, " E cQ%d\n", i);
 285         for (i=0; i<pi->A_dim; ++i)
 286                 fprintf(out, " E cA%d\n", i);
 287         for (i=0; i<pi->B_dim; ++i)
 288                 fprintf(out, " L cB%d\n", i);
 289         for (i=0; i<pi->x_dim; ++i)
 290                 fprintf(out, " L cy%d\n", i);
 291
 292         fprintf(out, "COLUMNS\n");
 293         /* the x vars come first */
 294         /* mark them as binaries */
 295         fprintf(out, "    MARKI0\t'MARKER'\t'INTORG'\n");
 296 #ifdef USE_SOS
 297         int sos_cnt = 0;
 298         fprintf(out, " S1 SOS_%d\t'MARKER'\t'SOSORG'\n", sos_cnt++);
 299 #endif
 300         for (i=0; i<pi->x_dim; ++i) {
 301 #ifdef USE_SOS
 302                 if (i>0 && pi->x[i].n != pi->x[i-1].n) {
 303                         fprintf(out, "    SOS_%d\t'MARKER'\t'SOSEND'\n", sos_cnt++);
 304                         fprintf(out, " S1 SOS_%d\t'MARKER'\t'SOSORG'\n", sos_cnt++);
 305                 }
 306 #endif
 307                 /* participation in objective */
 308                 fprintf(out, "    x%d_%d\tobj\t%d\n", pi->x[i].n, pi->x[i].c, -pi->bigM);
 309                 /* in Q */
 310                 for (o=0; o<pi->x_dim; ++o) {
 311                         int Qoi = pi->Q[o*pi->x_dim + i];
 312                         if (Qoi)
 313                                 fprintf(out, "    x%d_%d\tcQ%d\t%d\n", pi->x[i].n, pi->x[i].c, o, Qoi);
 314                 }
 315                 /* in A */
 316                 for (o=0; o<pi->A_dim; ++o) {
 317                         int Aoi = pi->A[o*pi->x_dim + i];
 318                         if (Aoi)
 319                                 fprintf(out, "    x%d_%d\tcA%d\t%d\n", pi->x[i].n, pi->x[i].c, o, Aoi);
 320                 }
 321                 /* in B */
 322                 for (o=0; o<pi->B_dim; ++o) {
 323                         int Boi = pi->B[o*pi->x_dim + i];
 324                         if (Boi)
 325                                 fprintf(out, "    x%d_%d\tcB%d\t%d\n", pi->x[i].n, pi->x[i].c, o, Boi);
 326                 }
 327                 /* in y */
 328                 fprintf(out, "    x%d_%d\tcy%d\t%d\n", pi->x[i].n, pi->x[i].c, i, 2*pi->bigM);
 329         }
 330 #ifdef USE_SOS
 331         fprintf(out, "    SOS_%d\t'MARKER'\t'SOSEND'\n", sos_cnt++);
 332 #endif
 333         fprintf(out, "    MARKI1\t'MARKER'\t'INTEND'\n"); /* end of marking */
 334
 335         /* next the s vars */
 336         for (i=0; i<pi->x_dim; ++i) {
 337                 /* participation in objective */
 338                 fprintf(out, "    s%d_%d\tobj\t%d\n", pi->x[i].n, pi->x[i].c, 1);
 339                 /* in Q */
 340                 fprintf(out, "    s%d_%d\tcQ%d\t%d\n", pi->x[i].n, pi->x[i].c, i, -1);
 341         }
 342
 343         /* next the y vars */
 344         for (i=0; i<pi->x_dim; ++i) {
 345                 /* in Q */
 346                 fprintf(out, "    y%d_%d\tcQ%d\t%d\n", pi->x[i].n, pi->x[i].c, i, -1);
 347                 /* in y */
 348                 fprintf(out, "    y%d_%d\tcy%d\t%d\n", pi->x[i].n, pi->x[i].c, i, 1);
 349         }
 350
 351         fprintf(out, "RHS\n");
 352         for (i=0; i<pi->x_dim; ++i)
 353                 fprintf(out, "    rhs\tcQ%d\t%d\n", i, -pi->bigM);
 354         for (i=0; i<pi->A_dim; ++i)
 355                 fprintf(out, "    rhs\tcA%d\t%d\n", i, 1);
 356         for (i=0; i<pi->B_dim; ++i)
 357                 fprintf(out, "    rhs\tcB%d\t%d\n", i, 1);
 358         for (i=0; i<pi->x_dim; ++i)
 359                 fprintf(out, "    rhs\tcy%d\t%d\n", i, 2*pi->bigM);
 360
 361         fprintf(out, "ENDATA\n");
 362         fclose(out);
 363
 364         out = ffopen(pi->name, "mst", "wt");
 365         fprintf(out, "NAME\n");
 366         for (i=0; i<pi->x_dim; ++i) {
 367                 int val, n, c;
 368                 n = pi->x[i].n;
 369                 c = pi->x[i].c;
 370                 if (get_irn_color(get_irn_for_graph_nr(pi->irg, n)) == c)
 371                         val = 1;
 372                 else
 373                         val = 0;
 374                 fprintf(out, "    x%d_%d\t%d\n", n, c, val);
 375         }
 376         fprintf(out, "ENDATA\n");
 377         fclose(out);
 378 }
 379 #endif
 380
 381 #if defined(DUMP_LPO) || defined(DUMP_LPP)
 382 /**
 383  * Dumps constraints used by both linearizations
 384  */
 385 static void pi_dump_lp_common_constraints(problem_instance_t *pi, FILE *out) {
 386         int i, o;
 387         /* knapsack constraints */
 388         for (i=0; i<pi->A_dim; ++i)     {
 389                 for (o=0; o<pi->x_dim; ++o)
 390                         if (pi->A[i*pi->x_dim + o])
 391                                 fprintf(out, "+x%d_%d ", pi->x[o].n, pi->x[o].c);
 392                 fprintf(out, " = 1;\n");
 393         }
 394         fprintf(out, "\n\n");
 395
 396         /* interference graph constraints */
 397         for (i=0; i<pi->B_dim; ++i)     {
 398                 for (o=0; o<pi->x_dim; ++o)
 399                         if (pi->B[i*pi->x_dim + o])
 400                                 fprintf(out, "+x%d_%d ", pi->x[o].n, pi->x[o].c);
 401                 fprintf(out, " <= 1;\n");
 402         }
 403         fprintf(out, "\n\n");
 404
 405         /* integer constraints */
 406         fprintf(out, "int x%d_%d", pi->x[0].n, pi->x[0].c);
 407         for (i=1; i<pi->x_dim; ++i)
 408                 fprintf(out, ", x%d_%d", pi->x[i].n, pi->x[i].c);
 409         fprintf(out, ";\n");
 410 }
 411 #endif
 412
 413 #ifdef DUMP_LPO
 414 /**
 415  * Dumps the problem instance as a MILP. The original problem is transformed into:
 416  * min f = es - Mex
 417  * udN:  Qx -y -s +Me = 0
 418  *       Ax  = e
 419  *       Bx <= e
 420  *        y <= 2M(e-x)
 421  *        x \in N   y, s >= 0
 422  *
 423  * with M >= max sum Q'ij * x_j
 424  *            i   j
 425  */
 426 static void pi_dump_lp_org(problem_instance_t *pi) {
 427         int i, o, max_abs_Qij;
 428         FILE *out = ffopen(pi->name, "lpo", "wt");
 429
 430         DBG((dbgphi, LEVEL_1, "Dumping lp_org...\n"));
 431         /* calc the big M for Q */
 432         max_abs_Qij = pi->maxQij;
 433         if (-pi->minQij > max_abs_Qij)
 434                 max_abs_Qij = -pi->minQij;
 435         pi->bigM = pi->A_dim * max_abs_Qij;
 436         DBG((dbgphi, LEVEL_2, "BigM = %d\n", pi->bigM));
 437
 438         /* generate objective function */
 439         fprintf(out, "min: ");
 440         for (i=0; i<pi->x_dim; ++i)
 441                 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);
 442         fprintf(out, ";\n\n");
 443
 444         /* constraints for former objective function */
 445         for (i=0; i<pi->x_dim; ++i)     {
 446                 for (o=0; o<pi->x_dim; ++o) {
 447                         int Qio = pi->Q[i*pi->x_dim + o];
 448                         if (Qio) {
 449                                 if (Qio == 1)
 450                                         fprintf(out, "+x%d_%d ", pi->x[o].n, pi->x[o].c);
 451                                 else if(Qio == -1)
 452                                         fprintf(out, "-x%d_%d ", pi->x[o].n, pi->x[o].c);
 453                                 else
 454                                         fprintf(out, "%+dx%d_%d ", Qio, pi->x[o].n, pi->x[o].c);
 455                         }
 456                 }
 457                 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);
 458         }
 459         fprintf(out, "\n\n");
 460
 461         /* constraints for (special) complementary condition */
 462         for (i=0; i<pi->x_dim; ++i)
 463                 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);
 464         fprintf(out, "\n\n");
 465
 466         pi_dump_lp_common_constraints(pi, out);
 467         fclose(out);
 468 }
 469 #endif
 470
 471 #ifdef DUMP_LPP
 472 /**
 473  * Dumps the problem instance as a MILP. The original problem is transformed into:
 474  * min f = es
 475  * udN:  Q'x -y -s = 0
 476  *       Ax  = e
 477  *       Bx <= e
 478  *        y <= M(e-x)
 479  *        x \in N   y, s >= 0
 480  *
 481  * with Q' = (q'_ij) := q_ij - minQij
 482  * and M >= max sum Q'ij * x_j
 483  *           i   j
 484  */
 485 static void pi_dump_lp_pos(problem_instance_t *pi) {
 486         int i, o;
 487         FILE *out = ffopen(pi->name, "lpp", "wt");
 488
 489         DBG((dbgphi, LEVEL_1, "Dumping lp_pos...\n"));
 490         /* Norm the Matrix: Qij >=0 and \exists i,j Qij=0 */
 491         for (i=0; i<pi->x_dim; ++i)
 492                 for (o=0; o<pi->x_dim; ++o)
 493                         pi->Q[i*pi->x_dim + o] -= pi->minQij;
 494         /* now Q' is stored in Q */
 495
 496         /* calc the big M for Q'
 497          * maxQ'ij = maxQij-minQij
 498          * #nodes = A_dim
 499          * So max sum Q'ij * x_j <= A_dim * maxQ'ij
 500          *     i   j
 501          */
 502         pi->bigM = pi->A_dim * (pi->maxQij - pi->minQij);
 503         DBG((dbgphi, LEVEL_2, "BigM = %d\n", pi->bigM));
 504
 505         /* clac the correction term for the obj func
 506          * xQx = xQ'x + minQij * k^2
 507          * where k, in general, is the knapsack size of wx = k.
 508          * Here w=1 and so 1x = #nodes = A_dim
 509          */
 510         pi->correction = pi->minQij * pi->A_dim * pi->A_dim;
 511         DBG((dbgphi, LEVEL_2, "Correction = %d\n", pi->correction));
 512
 513         /* generate objective function */
 514         fprintf(out, "min: ");
 515         for (i=0; i<pi->x_dim; ++i)
 516                 fprintf(out, "+s%d_%d ", pi->x[i].n, pi->x[i].c);
 517         fprintf(out, "+ correction\n");
 518         fprintf(out, "correction = %d ", pi->correction);
 519         fprintf(out, ";\n\n");
 520
 521         /* constraints for former objective function */
 522         for (i=0; i<pi->x_dim; ++i)     {
 523                 for (o=0; o<pi->x_dim; ++o) {
 524                         int Qio = pi->Q[i*pi->x_dim + o];
 525                         if (Qio) {
 526                                 if (Qio != 1)
 527                                         fprintf(out, "+%d", Qio);
 528                                 fprintf(out, "+x%d_%d ", pi->x[o].n, pi->x[o].c);
 529                         }
 530                 }
 531                 fprintf(out, "-y%d_%d -s%d_%d = 0;\n", pi->x[i].n, pi->x[i].c, pi->x[i].n, pi->x[i].c);
 532         }
 533         fprintf(out, "\n\n");
 534
 535         /* constraints for (special) complementary condition */
 536         for (i=0; i<pi->x_dim; ++i)
 537                 fprintf(out, "y%d_%d<=%d-%dx%d_%d;\n", pi->x[i].n, pi->x[i].c, pi->bigM, pi->bigM, pi->x[i].n, pi->x[i].c);
 538         fprintf(out, "\n\n");
 539
 540         pi_dump_lp_common_constraints(pi, out);
 541         fclose(out);
 542 }
 543 #endif
 544
 545 #ifdef DO_SOLVE
 546 /**
 547  * Invoke an external solver
 548  */
 549 static void pi_solve_ilp(problem_instance_t *pi) {
 550         FILE *out;
 551         char buf[1024];
 552
 553         /* write command file for CPLEX */
 554         out = ffopen(pi->name, "cmd", "wt");
 555         fprintf(out, "read %s.mps\n", pi->name);
 556         fprintf(out, "read %s.mst\n", pi->name);
 557         fprintf(out, "set mip strategy mipstart 1\n");
 558         fprintf(out, "optimize\n");
 559         fprintf(out, "set logfile %s.sol\n", pi->name);
 560         fprintf(out, "display solution variables 1-%d\n", pi->x_dim);
 561         fprintf(out, "set logfile cplex.log\n");
 562         fprintf(out, "quit\n");
 563         fclose(out);
 564
 565         snprintf(buf, sizeof(buf), "scp %s.mps %s.mst %s.cmd %s:", pi->name, pi->name, pi->name, SSH_USER_HOST);
 566         system(buf);
 567         snprintf(buf, sizeof(buf), "ssh %s \"./cplex90 < %s.cmd\"", SSH_USER_HOST, pi->name);
 568         system(buf);
 569         snprintf(buf, sizeof(buf), "scp %s:%s.sol .", SSH_USER_HOST, pi->name);
 570         system(buf);
 571 }
 572
 573 /**
 574  * Sets the colors of irns according to the values of variables found in the
 575  * output file of the solver.
 576  */
 577 static void pi_apply_solution(problem_instance_t *pi) {
 578         FILE *in = ffopen(pi->name, "sol", "rt");
 579
 580         DBG((dbgphi, LEVEL_1, "Applying solution...\n"));
 581         while (!feof(in)) {
 582                 char buf[1024];
 583                 int num = -1, col = -1, val = -1;
 584                 if (fscanf(in, "x%d_%d %d.%s\n", &num, &col, &val, buf) != 3) {
 585                         while(fscanf(in, "%1020s\n", buf) != 1);
 586                         continue;
 587                 }
 588                 if (val == 1) {
 589                         DBG((dbgphi, LEVEL_1, "x%d_%d = %d\n", num, col, val));
 590                         set_irn_color(get_irn_for_graph_nr(pi->irg, num), col);
 591                 }
 592         }
 593         fclose(in);
 594 }
 595 #endif /* DO_SOLVE */
 596
 597 #ifdef DELETE_FILES
 598 static void pi_delete_files(problem_instance_t *pi) {
 599         char buf[1024];
 600         int end = snprintf(buf, sizeof(buf), "%s", pi->name);
 601 #ifdef DUMP_MATRICES
 602         snprintf(buf+end, sizeof(buf)-end, ".matrix");
 603         remove(buf);
 604 #endif
 605 #ifdef DUMP_MPS
 606         snprintf(buf+end, sizeof(buf)-end, ".mps");
 607         remove(buf);
 608         snprintf(buf+end, sizeof(buf)-end, ".mst");
 609         remove(buf);
 610         snprintf(buf+end, sizeof(buf)-end, ".cmd");
 611         remove(buf);
 612 #endif
 613 #ifdef DUMP_LPO
 614         snprintf(buf+end, sizeof(buf)-end, ".lpo");
 615         remove(buf);
 616 #endif
 617 #ifdef DUMP_LPP
 618         snprintf(buf+end, sizeof(buf)-end, ".lpp");
 619         remove(buf);
 620 #endif
 621 }
 622 #endif
 623
 624 /**
 625  * Let N be minimal so that the copy-minimization-problem resticted to
 626  * N possible colors has the same result as the original copy-min-prob with
 627  * MAX_COLORS possible colors.
 628  * It is assumed (not proven) that this is true, if for each phi and phi-arg
 629  * an extra register would be available. Constrained registers count an additinal
 630  * register too.
 631  * TODO Prove the above.
 632  *
 633  * This function returns M in env, where N <= M <= MAX_COLROS
 634  */
 635 static void pi_colors_upper_bound(ir_node *block, void *env) {
 636         int *res = env;
 637         int i, max, max_pressure, special_cnt;
 638         if (*res == MAX_COLORS)
 639                 return;
 640
 641         /* get maximal register pressure */
 642         {
 643                 struct list_head *head = &get_ra_block_info(block)->border_head;
 644                 border_t *b;
 645                 max_pressure = 0;
 646                 list_for_each_entry(border_t, b, head, list)
 647                         if (b->pressure > max_pressure) {
 648                                 max_pressure = b->pressure;
 649                         }
 650         }
 651
 652         /* count special nodes */
 653         special_cnt = 0;
 654         for (i = 0, max = get_irn_n_outs(block); i < max; ++i) {
 655                 ir_node *n = get_irn_out(block, i);
 656                 if (get_nodes_block(n) != block)
 657                         continue;
 658                 if (is_Phi(n) || is_phi_operand(n) || is_constrained(n))
 659                         special_cnt++;
 660         }
 661
 662         /* new max? */
 663         if (*res < max_pressure + special_cnt)
 664                 *res = max_pressure + special_cnt;
 665         if (*res > MAX_COLORS)
 666                 *res = MAX_COLORS;
 667 }
 668
 669 /**
 670  * Generate the initial problem matrices and vectors.
 671  */
 672 static problem_instance_t *new_pi(ir_graph *irg, pset *all_phi_nodes) {
 673         int max_needed_cols;
 674         problem_instance_t *pi = calloc(1, sizeof(problem_instance_t));
 675         pi->irg = irg;
 676         pi->name =      get_entity_name(get_irg_entity(irg));
 677         pi->bigM = 1;
 678         pi->minQij = MIN_Q_INIT;
 679         pi->maxQij = MAX_Q_INIT;
 680         obstack_init(&pi->ob);
 681
 682         DBG((dbgphi, LEVEL_1, "Generating new instance...\n"));
 683         pi->num2pos = new_set(pi_num2pos_cmp, 128);
 684
 685         //TODO move pi_colors_upper_bound in "super-class" to fix issue with
 686         //invalid mst-values
 687         /* get max_needed_cols */
 688         max_needed_cols = 0;
 689         dom_tree_walk_irg(irg, pi_colors_upper_bound, NULL, &max_needed_cols);
 690         //TODO remove
 691         max_needed_cols = MAX_COLORS;
 692         DBG((dbgphi, LEVEL_1, "max_needed_cols: %d\n", max_needed_cols));
 693
 694         /* Vector x
 695          * one entry per node and possible color */
 696         {
 697                 x_vec_t xx;
 698                 for (xx.n=0; xx.n<get_graph_node_count(irg); ++xx.n) {
 699                         ir_node *irn = get_irn_for_graph_nr(irg, xx.n);
 700
 701                         if (!is_allocatable_irn(irn))
 702                                 continue;
 703                         DBG((dbgphi, LEVEL_2, "pi->num2pos %4d --> %4d\n", xx.n, pi->x_dim));
 704                         pi_set_first_pos(pi, xx.n, pi->x_dim);
 705
 706                         pi->A_dim++;                    /* one knapsack constraint for each node */
 707                         for (xx.c=0; xx.c<max_needed_cols; ++xx.c) {
 708                                 if (!is_possible_color(irn, xx.c))
 709                                         continue;
 710                                 DBG((dbgphi, LEVEL_2, "Adding %n %d\n", irn, xx.c));
 711                                 obstack_grow(&pi->ob, &xx, sizeof(xx));
 712                                 pi->x_dim++;            /* one x variable for each node and color */
 713                         }
 714                 }
 715                 pi->x = obstack_finish(&pi->ob);
 716         }
 717
 718         /* Matrix Q
 719          * weights for the 'same-color-optimization' target */
 720         {
 721                 ir_node *phi, *arg;
 722                 pi->Q = calloc(pi->x_dim*pi->x_dim, sizeof(pi->Q[0]));
 723                 for (phi = pset_first(all_phi_nodes); phi; phi = pset_next(all_phi_nodes)) {
 724                         unsigned phipos, argpos;
 725                         int phinr, argnr;
 726                         int i, max;
 727
 728                         for (i = 0, max = get_irn_arity(phi); i < max; ++i) {
 729                                 int weight;
 730                                 arg = get_irn_n(phi, i);
 731                                 if (phi_ops_interfere(phi, arg))
 732                                         continue;
 733                                 phinr = get_irn_graph_nr(phi);
 734                                 argnr = get_irn_graph_nr(arg);
 735                                 phipos = pi_get_first_pos(pi, phinr);
 736                                 argpos = pi_get_first_pos(pi, argnr);
 737                                 weight = -get_weight(phi, arg);
 738
 739                                 DBG((dbgphi, LEVEL_2, "Q[%n, %n] := %d\n", phi, arg, weight));
 740                                 /* for all colors phi and arg have in common, set the weight for
 741                                  * this pair in the objective function matrix Q */
 742                                 while (phipos < pi->x_dim && argpos < pi->x_dim &&
 743                                                 pi->x[phipos].n == phinr && pi->x[argpos].n == argnr) {
 744                                         if (pi->x[phipos].c < pi->x[argpos].c)
 745                                                 ++phipos;
 746                                         else if (pi->x[phipos].c > pi->x[argpos].c)
 747                                                 ++argpos;
 748                                         else {
 749                                                 pi->Q[(phipos++)*pi->x_dim + argpos++] = weight;
 750
 751                                                 if (weight < pi->minQij) {
 752                                                         DBG((dbgphi, LEVEL_2, "minQij = %d\n", weight));
 753                                                         pi->minQij = weight;
 754                                                 }
 755                                                 if (weight > pi->maxQij) {
 756                                                         DBG((dbgphi, LEVEL_2, "maxQij = %d\n", weight));
 757                                                         pi->maxQij = weight;
 758                                                 }
 759                                         }
 760                                 }
 761                         }
 762                 }
 763         }
 764
 765         /* Matrix A
 766          * knapsack constraint for each node */
 767         {
 768                 int row = 0, col = 0;
 769                 pi->A = calloc(pi->A_dim*pi->x_dim, sizeof(pi->A[0]));
 770                 while (col < pi->x_dim) {
 771                         int curr_n = pi->x[col].n;
 772                         while (col < pi->x_dim && pi->x[col].n == curr_n) {
 773                                 DBG((dbgphi, LEVEL_2, "A[%d, %d] := %d\n", row, col, 1));
 774                                 pi->A[row*pi->x_dim + col++] = 1;
 775                         }
 776                         ++row;
 777                 }
 778                 assert(row == pi->A_dim);
 779         }
 780
 781         /* Matrix B
 782          * interference constraints using exactly those cliques not contained in others. */
 783         {
 784                 int col;
 785                 pi->B_dim = set_count(be_ra_get_ifg(irg))*max_needed_cols;  /* this is an upper bound, see realloc below */
 786                 pi->B = calloc(pi->B_dim*pi->x_dim, sizeof(pi->B[0]));
 787
 788                 for (col = 0; col < max_needed_cols; ++col) {
 789                         pi->curr_col = col;
 790                         dom_tree_walk_irg(irg, pi_clique_finder, NULL, pi);
 791                 }
 792
 793                 pi->B_dim = pi->curr_row;
 794                 pi->B = realloc(pi->B, pi->B_dim*pi->x_dim*sizeof(pi->B[0]));
 795         }
 796
 797         return pi;
 798 }
 799
 800 /**
 801  * clean the problem instance
 802  */
 803 static void free_pi(problem_instance_t *pi) {
 804         free(pi->Q);
 805         free(pi->A);
 806         free(pi->B);
 807         del_set(pi->num2pos);
 808         obstack_free(&pi->ob, NULL);
 809         free(pi);
 810 }
 811
 812 void be_phi_coalesce_ilp(ir_graph *irg, pset *all_phi_nodes) {
 813         problem_instance_t *pi = new_pi(irg, all_phi_nodes);
 814
 815 #ifdef DUMP_MATRICES
 816         pi_dump_matrices(pi);
 817 #endif
 818
 819 #ifdef DUMP_MPS
 820         pi_dump_mps(pi);
 821 #endif
 822
 823 #ifdef DUMP_LPO
 824         pi_dump_lp_org(pi);
 825 #endif
 826
 827 #ifdef DUMP_LPP
 828         pi_dump_lp_pos(pi);
 829 #endif
 830
 831 #ifdef DO_SOLVE
 832         pi_solve_ilp(pi);
 833         pi_apply_solution(pi);
 834 #endif
 835
 836 #ifdef DELETE_FILES
 837         pi_delete_files(pi);
 838 #endif
 839
 840         free_pi(pi);
 841 }
 842
 843 void be_phi_coal_ilp_init(void) {
 844         dbgphi = firm_dbg_register("ir.be.phicoalilp");
 845         firm_dbg_set_mask(dbgphi, DEBUG_LVL);
 846 }