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

   1 /**
   2  * Author:      Daniel Grund
   3  * Date:                17.05.2005
   4  * Copyright:   (c) Universitaet Karlsruhe
   5  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
   6  * CVS-ID:      $Id$
   7  *
   8  * ILP formalization using:
   9  *  - 2 classes of vars: Nodes- and optimality variables.
  10  *  - Clique constraints
  11  *  - Path constraints
  12  *  - Clique path constraints
  13  */
  14
  15 #ifdef HAVE_CONFIG_H
  16 #include "config.h"
  17 #endif /* HAVE_CONFIG_H */
  18
  19 #ifdef WITH_ILP
  20
  21 #include "becopyilp_t.h"
  22 #include "benumb_t.h"
  23 #include "belive_t.h"
  24 #include "irdom_t.h"
  25 #include "irgwalk.h"
  26 #include "xmalloc.h"
  27 #include "pset.h"
  28 #include "irprog.h"
  29 #include "irdom_t.h"
  30 #include "iredges_t.h"
  31
  32 #include "becopystat.h"
  33 #include "besched_t.h"
  34 #include "phiclass.h"
  35
  36 #if 0 //temporary
  37
  38 #define PATH_CONSTRAINTS_FOR_CLASSES
  39 #undef DUMP_MPS
  40
  41 static firm_dbg_module_t *dbg = NULL;
  42 #define SLOTS_LIVING 32
  43
  44 typedef struct _problem_instance_t {
  45         const copy_opt_t *co;                   /**< the copy opt problem */
  46         size_red_t *sr;                                 /**< problem size reduction. removes simple nodes */
  47         lpp_t *lp;                                              /**< the linear programming problem */
  48
  49         /* Helpers for maintaining indices and finding variables */
  50         int first_nnc_var_idx;                  /**< the first index of a constraint belonging to no-null-colors stuff*/
  51         int cst_counter, first_x_var, last_x_var;
  52         char buf[32];
  53         pset *done;
  54 } problem_instance_t;
  55
  56 #define is_color_possible(irn,color) arch_reg_is_allocatable(pi->co->aenv, irn, -1, arch_register_for_index(pi->co->cls, color))
  57
  58 /*
  59  * Some stuff for variable name handling.
  60  */
  61 #define mangle_cst(buf, prefix, nr) \
  62                         snprintf((buf), sizeof(buf), "%c%d", (prefix), (nr))
  63
  64 #define mangle_var1(buf, prefix, color) \
  65                         snprintf((buf), sizeof(buf), "%c%d", (prefix), (color))
  66
  67 #define mangle_var2(buf, prefix, node_nr, color) \
  68                         snprintf((buf), sizeof(buf), "%c%d_%d", (prefix), (node_nr), (color))
  69
  70 #define mangle_var3(buf, prefix, n1, n2, col) \
  71                         snprintf((buf), sizeof(buf), "%c%d_%d_%d", (prefix), (n1), (n2), (col))
  72
  73 #define mangle_var_irn(buf, prefix, irn, color) \
  74                         mangle_var2((buf), (prefix), get_irn_graph_nr(irn), (color))
  75
  76 #define split_var(var, nnr, col) \
  77                         sscanf(var, "x%d_%d", (nnr), (col))
  78
  79
  80 /**
  81  * Add coloring-force conditions
  82  * Matrix A: knapsack constraint for each node
  83  */
  84 static void pi_add_constr_A(problem_instance_t *pi) {
  85         pmap_entry *pme;
  86
  87         DBG((dbg, LEVEL_2, "Add A constraints...\n"));
  88         /* iterate over all blocks */
  89         pmap_foreach(pi->co->cenv->border_heads, pme) {
  90                 struct list_head *head = pme->value;
  91                 border_t *curr;
  92                 bitset_t *pos_regs = bitset_alloca(pi->co->cenv->cls->n_regs);
  93
  94                 list_for_each_entry_reverse(border_t, curr, head, list)
  95                         if (curr->is_def && curr->is_real && !sr_is_removed(pi->sr->curr->irn)) {
  96                                 int cst_idx, nnr, col;
  97
  98                                 nnr = get_irn_graph_nr(curr->irn);
  99                                 mangle_cst(pi->buf, 'A', nnr);
 100                                 cst_idx = lpp_add_cst(pi->curr_lp, pi->buf, lpp_equal, 1);
 101
 102                                 /* iterate over all possible colors in order */
 103                                 bitset_clear_all(pos_regs);
 104                                 arch_get_allocatable_regs(pi->co->aenv, curr->irn, -1, pos_regs);
 105                                 bitset_foreach(pos_regs, col) {
 106                                         int var_idx;
 107                                         mangle_var2(pi->buf, 'x', nnr, col);
 108                                         var_idx = lpp_add_var(pi->curr_lp, pi->buf, lpp_binary, 0);
 109                                         if (!pi->first_x_var)
 110                                                 pi->first_x_var = var_idx;
 111                                         pi->last_x_var = var_idx;
 112                                         lpp_set_factor_fast(pi->curr_lp, cst_idx, var_idx, 1);
 113                                 }
 114                         }
 115         }
 116 }
 117
 118 /**
 119  * Checks if all nodes in @p living are live in in block @p block.
 120  * @return 1 if all are live in
 121  *         0 else
 122  */
 123 static INLINE int all_live_in(ir_node *block, pset *living) {
 124         ir_node *n;
 125         for (n = pset_first(living); n; n = pset_next(living))
 126                 if (!is_live_in(block, n)) {
 127                         pset_break(living);
 128                         return 0;
 129                 }
 130         return 1;
 131 }
 132
 133 /**
 134  * Finds cliques in the interference graph, considering only nodes
 135  * for which the color @p color is possible. Finds only 'maximal-cliques',
 136  * viz cliques which are not contained in another one.
 137  * Matrix B: interference constraints using cliques
 138  */
 139 static void pi_add_constr_B(problem_instance_t *pi, int color) {
 140         enum phase_t {growing, shrinking} phase = growing;
 141         border_t *b;
 142         pmap_entry *pme;
 143         pset *living = pset_new_ptr(SLOTS_LIVING);
 144
 145         DBG((dbg, LEVEL_2, "Add B constraints (col = %d)...\n", color));
 146         /* iterate over all blocks */
 147         pmap_foreach(pi->co->cenv->border_heads, pme) {
 148                 ir_node *block = pme->key;
 149                 struct list_head *head = pme->value;
 150
 151                 list_for_each_entry_reverse(border_t, b, head, list) {
 152                         const ir_node *irn = b->irn;
 153                         if (is_removed(irn) || !is_color_possible(irn, color))
 154                                 continue;
 155
 156                         if (b->is_def) {
 157                                 DBG((dbg, LEVEL_2, "Def %n\n", irn));
 158                                 pset_insert_ptr(living, irn);
 159                                 phase = growing;
 160                         } else { /* is_use */
 161                                 DBG((dbg, LEVEL_2, "Use %n\n", irn));
 162
 163                                 /* before shrinking the set, store the current 'maximum' clique;
 164                                  * do NOT if clique is a single node
 165                                  * do NOT if all values are live_in (in this case they were contained in a live-out clique elsewhere) */
 166                                 if (phase == growing && pset_count(living) >= 2 && !all_live_in(block, living)) {
 167                                         int cst_idx;
 168                                         ir_node *n;
 169                                         mangle_cst(pi->buf, 'B', pi->cst_counter);
 170                                         cst_idx = lpp_add_cst(pi->curr_lp, pi->buf, lpp_less, 1);
 171                                         for (n = pset_first(living); n; n = pset_next(living)) {
 172                                                 int var_idx;
 173                                                 mangle_var_irn(pi->buf, 'x', n, color);
 174                                                 var_idx = lpp_get_var_idx(pi->curr_lp, pi->buf);
 175                                                 lpp_set_factor_fast(pi->curr_lp, cst_idx, var_idx, 1);
 176                                         }
 177                                         pi->cst_counter++;
 178                                 }
 179                                 pset_remove_ptr(living, irn);
 180                                 phase = shrinking;
 181                         }
 182                 }
 183         }
 184         assert(0 == pset_count(living));
 185         del_pset(living);
 186 }
 187
 188 /**
 189  * Generates constraints which interrelate x with y variables.
 190  * x1 and x2 have the different colors ==> y_12 = 1
 191  */
 192 static void pi_add_constr_E(problem_instance_t *pi) {
 193         unit_t *curr;
 194         bitset_t *root_regs, *arg_regs, *work_regs;
 195         int cst_counter = 0;
 196         unsigned nregs = pi->co->cenv->cls->n_regs;
 197         root_regs = bitset_alloca(nregs);
 198         arg_regs = bitset_alloca(nregs);
 199         work_regs = bitset_alloca(nregs);
 200
 201         DBG((dbg, LEVEL_2, "Add E constraints...\n"));
 202         /* for all roots of optimization units */
 203         list_for_each_entry(unit_t, curr, &pi->co->units, units) {
 204                 ir_node *root, *arg;
 205                 int rootnr, argnr, color;
 206                 int y_idx, i;
 207                 char buf[32];
 208
 209                 root = curr->nodes[0];
 210                 rootnr = get_irn_graph_nr(root);
 211                 bitset_clear_all(root_regs);
 212                 arch_get_allocatable_regs(pi->co->aenv, root, -1, root_regs);
 213
 214                 /* for all arguments of root */
 215                 for (i = 1; i < curr->node_count; ++i) {
 216                         arg = curr->nodes[i];
 217                         argnr = get_irn_graph_nr(arg);
 218                         bitset_clear_all(arg_regs);
 219                         arch_get_allocatable_regs(pi->co->aenv, arg, -1, arg_regs);
 220
 221                         /* Introduce new variable and set factor in objective function */
 222                         mangle_var2(buf, 'y', rootnr, argnr);
 223                         y_idx = lpp_add_var(pi->curr_lp, buf, lpp_binary, curr->costs[i]);
 224
 225                         /* set starting value */
 226                         lpp_set_start_value(pi->curr_lp, y_idx, (get_irn_col(pi->co, root) != get_irn_col(pi->co, arg)));
 227
 228                         /* For all colors root and arg have in common, add 2 constraints to E */
 229                         bitset_copy(work_regs, root_regs);
 230                         bitset_and(work_regs, arg_regs);
 231                         bitset_foreach(work_regs, color) {
 232                                 int root_idx, arg_idx, cst_idx;
 233                                 mangle_var2(buf, 'x', rootnr, color);
 234                                 root_idx = lpp_get_var_idx(pi->curr_lp, buf);
 235                                 mangle_var2(buf, 'x', argnr, color);
 236                                 arg_idx = lpp_get_var_idx(pi->curr_lp, buf);
 237
 238                                 /* add root-arg-y <= 0 */
 239                                 mangle_cst(buf, 'E', cst_counter++);
 240                                 cst_idx = lpp_add_cst(pi->curr_lp, buf, lpp_less, 0);
 241                                 lpp_set_factor_fast(pi->curr_lp, cst_idx, root_idx, 1);
 242                                 lpp_set_factor_fast(pi->curr_lp, cst_idx, arg_idx, -1);
 243                                 lpp_set_factor_fast(pi->curr_lp, cst_idx, y_idx, -1);
 244
 245                                 /* add arg-root-y <= 0 */
 246                                 mangle_cst(buf, 'E', cst_counter++);
 247                                 cst_idx = lpp_add_cst(pi->curr_lp, buf, lpp_less, 0);
 248                                 lpp_set_factor_fast(pi->curr_lp, cst_idx, root_idx, -1);
 249                                 lpp_set_factor_fast(pi->curr_lp, cst_idx, arg_idx, 1);
 250                                 lpp_set_factor_fast(pi->curr_lp, cst_idx, y_idx, -1);
 251                         }
 252                         /* For all colors root and arg have "disjunct", add 1 constraints to E.
 253                          * If root gets a color the arg is not possible to get then they will
 254                          * definetly get different colors. So y has to be 1.
 255                          * Vice versa for arg.
 256                          */
 257                         bitset_copy(work_regs, root_regs);
 258                         bitset_xor(work_regs, arg_regs);
 259                         bitset_foreach(work_regs, color) {
 260                                 int root_idx, arg_idx, cst_idx;
 261                                 mangle_var2(buf, 'x', rootnr, color);
 262                                 root_idx = lpp_get_var_idx(pi->curr_lp, buf);
 263                                 mangle_var2(buf, 'x', argnr, color);
 264                                 arg_idx = lpp_get_var_idx(pi->curr_lp, buf);
 265
 266                                 mangle_cst(buf, 'E', cst_counter++);
 267                                 cst_idx = lpp_add_cst(pi->curr_lp, buf, lpp_less, 0);
 268                                 if (bitset_is_set(root_regs, color)) {
 269                                         /* add root-y <= 0 */
 270                                         lpp_set_factor_fast(pi->curr_lp, cst_idx, root_idx, 1);
 271                                         lpp_set_factor_fast(pi->curr_lp, cst_idx, y_idx, -1);
 272                                 } else {
 273                                         assert(bitset_is_set(arg_regs, color) && "bitset_xor is buggy");
 274                                         /* add arg-y <= 0 */
 275                                         lpp_set_factor_fast(pi->curr_lp, cst_idx, arg_idx, 1);
 276                                         lpp_set_factor_fast(pi->curr_lp, cst_idx, y_idx, -1);
 277                                 }
 278                         }
 279                 }
 280         }
 281 }
 282
 283 static void clique_path_walker(ir_node *block, void *env) {
 284         problem_instance_t *pi = env;
 285         int count, arity, row, col, other_row, *costs;
 286         ir_node **phis, *phi, *irn, **phi_matrix;
 287         pset *done;
 288         bitset_t *candidates;
 289
 290         /* Count all phi nodes of this block */
 291         for (count=0, irn = sched_first(block); is_Phi(irn); irn = sched_next(irn))
 292                 count++;
 293
 294         /* We at least 2 phi nodes for this class of inequalities */
 295         if (count < 2)
 296                 return;
 297
 298         /* Build the \Phi-Matrix */
 299         arity = get_irn_arity(sched_first(block));
 300         phis = alloca(count * sizeof(*phis));
 301         costs = alloca(count * sizeof(costs));
 302         phi_matrix = alloca(count*arity * sizeof(*phi_matrix));
 303         candidates = bitset_alloca(count);
 304
 305         phi = sched_first(block);
 306         for (row=0; row<count; ++row) {
 307                 phis[row] = phi;
 308                 for (col=0; col<arity; ++col) {
 309                         ir_node *arg = get_irn_n(phi, col);
 310                         /* Sort out all arguments interfering with its phi */
 311                         if (nodes_interfere(pi->co->cenv, phi, arg)) {
 312                                 phi_matrix[row*arity + col] =  NULL;
 313                         } else
 314                                 phi_matrix[row*arity + col] =  arg;
 315                 }
 316                 phi = sched_next(phi);
 317         }
 318
 319         /* Now find the interesting patterns in the matrix:
 320          * All nodes which are used at least twice in a column. */
 321         /* columnwise ... */
 322         for (col=0; col<arity; ++col) {
 323                 done = pset_new_ptr_default();
 324                 for (row=0; row<count; ++row) {
 325                         irn = phi_matrix[row*arity + col];
 326                         /*
 327                          * is this an interfering arg (NULL)
 328                          * or has the irn already been processed in this col?
 329                          */
 330                         if (!irn || pset_find_ptr(done, irn))
 331                                 continue;
 332                         else
 333                                 pset_insert_ptr(done, irn);
 334
 335                         /* insert irn in candidates */
 336                         bitset_clear_all(candidates);
 337                         bitset_set(candidates, row);
 338                         /* search the irn in the rows below */
 339                         for (other_row = row+1; other_row<count; ++other_row)
 340                                 if (irn == phi_matrix[other_row*arity + col]) {
 341                                         /* found the irn in the same col in another row */
 342                                         bitset_set(candidates, other_row);
 343                                 }
 344
 345                         /* now we know all occurences of irn in this col */
 346                         if (bitset_popcnt(candidates) < 2)
 347                                 continue;
 348
 349                         /* generate an unequation finally.
 350                          * phis are indexed in the bitset,
 351                          * shared argument is irn
 352                          * rhs is phi_count - 1 */
 353                         {
 354                                 char buf[32];
 355                                 ir_node *root;
 356                                 int pos, irnnr, rootnr, cst_idx, y_idx, cst_counter = 0;
 357                                 int minimal_unequal_count = bitset_popcnt(candidates)-1;
 358
 359                                 irnnr = get_irn_graph_nr(irn);
 360                                 mangle_cst(buf, 'M', cst_counter++);
 361                                 cst_idx = lpp_add_cst(pi->curr_lp, buf, lpp_greater, minimal_unequal_count);
 362
 363                                 /* for all phis */
 364                                 bitset_foreach(candidates, pos) {
 365                                         root = phis[pos];
 366                                         rootnr = get_irn_graph_nr(root);
 367                                         mangle_var2(buf, 'y', rootnr, irnnr);
 368                                         y_idx = lpp_get_var_idx(pi->curr_lp, buf);
 369                                         lpp_set_factor_fast(pi->curr_lp, cst_idx, y_idx, 1);
 370                                 }
 371                         }
 372                 }
 373                 del_pset(done); /* clear set for next row */
 374         } /*next col*/
 375 }
 376
 377 /**
 378  * Matrix M: Multi-Arg-Use. Interrelates different \phi-functions
 379  * in the same block, iff they use the same arg at the same pos.
 380  * Only one of the phis can get the arg.
 381  */
 382 static void pi_add_clique_path_cstr(problem_instance_t *pi) {
 383         DBG((dbg, LEVEL_2, "Adding clique path constraints...\n"));
 384         dom_tree_walk_irg(pi->co->irg, clique_path_walker, NULL, pi);
 385 }
 386
 387 #ifndef PATH_CONSTRAINTS_FOR_CLASSES
 388 /**
 389  * Matrix P: Path contraints.
 390  * If 2 nodes interfere and there is a path of equal-color-edges
 391  * connecting them, then at least one of those equal-color-edges
 392  * will break and cause some costs.
 393  */
 394 static void pi_add_path_cstr(problem_instance_t *pi) {
 395         unit_t *curr;
 396         int cst_counter = 0;
 397         DBG((dbg, LEVEL_2, "Adding path constraints...\n"));
 398
 399         /* for all optimization units (only phis) */
 400         list_for_each_entry(unit_t, curr, &pi->co->units, units) {
 401                 int i, o, rootnr;
 402
 403                 if (curr->min_nodes_costs == 0)
 404                         continue;
 405
 406                 rootnr = get_irn_graph_nr(curr->nodes[0]);
 407                 /* check all argument pairs for interference */
 408                 for (i=1; i<curr->node_count; ++i) {
 409                         const ir_node *arg1 = curr->nodes[i];
 410                         int arg1nr = get_irn_graph_nr(arg1);
 411                         for (o=i+1; o<curr->node_count; ++o) {
 412                                 const ir_node *arg2 = curr->nodes[o];
 413                                 int arg2nr = get_irn_graph_nr(arg2);
 414                                 if (nodes_interfere(pi->co->cenv, arg1, arg2)) {
 415                                         int cst_idx, y_idx;
 416                                         char buf[32];
 417
 418                                         mangle_cst(buf, 'P', cst_counter++);
 419                                         cst_idx = lpp_add_cst(pi->curr_lp, buf, lpp_greater, 1);
 420
 421                                         mangle_var2(buf, 'y', rootnr, arg1nr);
 422                                         y_idx = lpp_get_var_idx(pi->curr_lp, buf);
 423                                         lpp_set_factor_fast(pi->curr_lp, cst_idx, y_idx, 1);
 424
 425                                         mangle_var2(buf, 'y', rootnr, arg2nr);
 426                                         y_idx = lpp_get_var_idx(pi->curr_lp, buf);
 427                                         lpp_set_factor_fast(pi->curr_lp, cst_idx, y_idx, 1);
 428                                 }
 429                         }
 430                 }
 431         }
 432 }
 433 #endif
 434
 435 #ifdef PATH_CONSTRAINTS_FOR_CLASSES
 436 static INLINE int get_y_var_idx(problem_instance_t *pi, int nnr1, int nnr2) {
 437         int res;
 438         char buf[30];
 439
 440         mangle_var2(buf, 'y', nnr1, nnr2);
 441         if ((res = lpp_get_var_idx(pi->curr_lp, buf)) != -1)
 442                 return res;
 443
 444         mangle_var2(buf, 'y', nnr2, nnr1);
 445         if ((res = lpp_get_var_idx(pi->curr_lp, buf)) != -1)
 446                 return res;
 447
 448         assert(0 && "One of them must work");
 449   return -1;
 450 }
 451
 452 static void check_ecc_and_add_cut(problem_instance_t *pi, ir_node **path, int length, pset *remain, ir_node *tgt) {
 453         if (path[length-1] == tgt) { /* we found a path */
 454                 int cst_idx, var_idx, i, nnr1, nnr2;
 455                 char buf[30];
 456
 457                 /* add cut to ilp */
 458                 mangle_cst(buf, 'Q', pi->cst_counter++);
 459                 cst_idx = lpp_add_cst(pi->curr_lp, buf, lpp_greater, 1);
 460
 461                 /* add all vars along the path */
 462                 nnr2 = get_irn_graph_nr(path[0]);
 463                 for (i=1; i<length; ++i) {
 464                         nnr1 = nnr2;
 465                         nnr2 = get_irn_graph_nr(path[i]);
 466                         var_idx = get_y_var_idx(pi, nnr1, nnr2);
 467                         lpp_set_factor_fast(pi->curr_lp, cst_idx, var_idx, 1);
 468                 }
 469         } else { /* try to extend the path */
 470                 be_chordal_env_t *cenv = pi->co->cenv;
 471                 const ir_edge_t *edge;
 472                 ir_node *end = path[length-1];
 473                 ir_node **next = alloca(pset_count(remain) * sizeof(*next));
 474                 int i, o, max, next_pos = 0;
 475                 pset *done = pset_new_ptr_default();
 476
 477                 /* find all potential next nodes on path */
 478                 /*  args of phis */
 479                 if (is_Phi(end))
 480                         for(i=0, max=get_irn_arity(end); i<max; ++i) {
 481                                 ir_node *arg = get_irn_n(end, i);
 482                                 if (!pset_find_ptr(done, arg) && pset_find_ptr(remain, arg)) {
 483                                         next[next_pos++] = arg;
 484                                         pset_insert_ptr(done, arg);
 485                                 }
 486                         }
 487                 /*  outs of phis and other nodes */
 488                 foreach_out_edge(end, edge) {
 489                         ir_node *user = edge->src;
 490                         if (is_Phi(user) && !pset_find_ptr(done, user) && pset_find_ptr(remain, user)) {
 491                                 next[next_pos++] = user;
 492                                 pset_insert_ptr(done, user);
 493                         }
 494                 }
 495                 del_pset(done);
 496
 497
 498                 /* delete all potential nodes with interferences to other nodes in the path */
 499                 for (i=0; i<next_pos; ++i) {
 500                         ir_node *nn = next[i];
 501
 502                         /* if next is the tgt, it may interfere with path[0],
 503                          * so skip the first check */
 504                         o = (nn == tgt && length > 1) ? 1 : 0;
 505
 506                         for(; o<length; ++o)
 507                                 if (nodes_interfere(cenv, nn, path[o])) {
 508                                         next[i] = NULL;
 509                                         break;
 510                                 }
 511                 }
 512                 /* now we have all possible nodes in next; impossibles are NULL */
 513
 514                 /* try to finish path with all possible nodes */
 515                 for (i=0; i<next_pos; ++i) {
 516                         if (!next[i]) /* this was an impossible node */
 517                                 continue;
 518
 519                         path[length] = next[i];
 520                         pset_remove_ptr(remain, next[i]);
 521                         check_ecc_and_add_cut(pi, path, length+1, remain, tgt);
 522                         pset_insert_ptr(remain, next[i]);
 523                 }
 524         }
 525 }
 526
 527 static void path_cstr_for_classes_walker(ir_node *irn, void *env) {
 528         problem_instance_t *pi = env;
 529         be_chordal_env_t *cenv;
 530         int i, o, max;
 531         ir_node *m, **cls;
 532         pset *class = get_phi_class(irn);
 533         if (!class || pset_find_ptr(pi->done, class))
 534                 return;
 535
 536         pset_insert_ptr(pi->done, class);
 537
 538         /* pset to array */
 539         max = pset_count(class);
 540         cls = alloca(max * sizeof(*cls));
 541         for(i=0, m = pset_first(class); m; i++, m = pset_next(class)) {
 542                 DBG((dbg, LEVEL_1, " class member: %+F\n", m));
 543                 cls[i] = m;
 544         }
 545
 546         cenv = pi->co->cenv;
 547         for(i=0; i<max; ++i) {
 548                 ir_node **path = alloca(max * sizeof(*path));
 549                 pset *remain = pset_new_ptr(8);
 550                 pset_insert_pset_ptr(remain, class);
 551
 552                 /* add cls[i] to path and remove it from remainder */
 553                 path[0] = cls[i];
 554                 pset_remove_ptr(remain, cls[i]);
 555
 556                 for(o=i+1; o<max; ++o)
 557                         if (nodes_interfere(cenv, cls[i], cls[o]))
 558                                 check_ecc_and_add_cut(pi, path, 1, remain, cls[o]);
 559
 560                 /* insert back into remainder */
 561                 pset_insert_ptr(remain, cls[i]);
 562         }
 563 }
 564
 565
 566 /**
 567  * Matrix P: Path contraints.
 568  * If 2 nodes interfere and there is a path of equal-color-edges
 569  * connecting them, then at least one of those equal-color-edges
 570  * will break and cause some costs.
 571  */
 572 static void pi_add_path_cstr_for_classes(problem_instance_t *pi) {
 573         DBG((dbg, LEVEL_2, "Adding path constraints for phi classes...\n"));
 574         pi->cst_counter = 0;
 575         pi->done = pset_new_ptr_default();
 576         irg_walk_graph(pi->co->irg, path_cstr_for_classes_walker, NULL, pi);
 577         del_pset(pi->done);
 578 }
 579 #endif
 580
 581
 582
 583 /**
 584  * Generate the initial problem matrices and vectors.
 585  */
 586 static problem_instance_t *new_pi(const copy_opt_t *co) {
 587         problem_instance_t *pi;
 588         int col;
 589
 590         DBG((dbg, LEVEL_2, "Generating new instance...\n"));
 591         pi = xcalloc(1, sizeof(*pi));
 592         pi->co  = co;
 593         pi->sr  = new_size_red(co);
 594         pi->lp  = new_lpp(co->name, lpp_minimize);
 595
 596         return pi;
 597 }
 598
 599 static void pi_construct(problem_instance_t *pi) {
 600         pi_add_constr_A(pi);
 601         for (col = 0; col < pi->co->cls->n_regs; ++col)
 602                 pi_add_constr_B(pi, col);
 603         pi_add_constr_E(pi);
 604
 605 #ifdef PATH_CONSTRAINTS_FOR_CLASSES
 606         pi_add_path_cstr_for_classes(pi);
 607 #else
 608         pi_add_path_cstr(pi);
 609 #endif
 610         pi_add_clique_path_cstr(pi);
 611 }
 612
 613 /**
 614  * Clean the problem instance
 615  */
 616 static void free_pi(problem_instance_t *pi) {
 617         simpl_t *simpl, *tmp;
 618
 619         DBG((dbg, LEVEL_2, "Free instance...\n"));
 620         free_lpp(pi->lp);
 621         free_size_red(pi->sr);
 622         free(pi);
 623 }
 624
 625
 626 /**
 627  * Set starting values for the mip problem according
 628  * to the current coloring of the graph.
 629  */
 630 static void pi_set_start_sol(problem_instance_t *pi) {
 631         int i;
 632         char var_name[64];
 633         DBG((dbg, LEVEL_2, "Set start solution...\n"));
 634         for (i=pi->first_x_var; i<=pi->last_x_var; ++i) {
 635                 int nnr, col;
 636                 double val;
 637                 /* get variable name */
 638                 lpp_get_var_name(pi->curr_lp, i, var_name, sizeof(var_name));
 639                 /* split into components */
 640                 if (split_var(var_name, &nnr, &col) == 2) {
 641                         assert(get_irn_col(pi->co, get_irn_for_graph_nr(pi->co->irg, nnr)) != -1);
 642                         val = (get_irn_col(pi->co, get_irn_for_graph_nr(pi->co->irg, nnr)) == col) ? 1 : 0;
 643                         lpp_set_start_value(pi->curr_lp, i, val);
 644                 } else {
 645                         fprintf(stderr, "Variable name is: %s\n", var_name);
 646                         assert(0 && "x vars always look like this 'x123_45'");
 647                 }
 648         }
 649 }
 650
 651
 652 /**
 653  * Invoke a solver
 654  */
 655 static void pi_solve_ilp(problem_instance_t *pi, double time_limit) {
 656         double lower_bound;
 657 #ifdef DUMP_MPS
 658         char buf[512];
 659         snprintf(buf, sizeof(buf), "%s.ilp1", co->name);
 660         lpp_dump(pi->lp, buf);
 661 #endif
 662
 663         pi_set_start_sol(pi);
 664
 665         lower_bound = co_get_lower_bound(pi->co) - co_get_inevit_copy_costs(pi->co);
 666         lpp_set_bound(pi->curr_lp, lower_bound);
 667
 668         lpp_set_time_limit(pi->curr_lp, time_limit);
 669
 670 #ifdef LPP_SOLVE_REMOTE
 671         lpp_solve_net(pi->curr_lp, LPP_HOST, LPP_SOLVER);
 672 #else
 673         lpp_solve_cplex(pi->curr_lp);
 674 #endif
 675         DBG((dbg, LEVEL_1, "Solution time: %.2f\n", pi->curr_lp->sol_time));
 676 }
 677
 678
 679 /**
 680  * Sets the colors of irns according to the values of variables
 681  * provided by the solution of the solver.
 682  */
 683 static int pi_apply_solution(problem_instance_t *pi) {
 684         int res = 1, i;
 685         double *sol;
 686         lpp_sol_state_t state;
 687         DBG((dbg, LEVEL_2, "Applying solution...\n"));
 688
 689 #ifdef DO_STAT
 690         copystat_add_ilp_time((int)(1000.0*lpp_get_sol_time(pi->curr_lp)));  //now we have ms
 691         copystat_add_ilp_vars(lpp_get_var_count(pi->curr_lp));
 692         copystat_add_ilp_csts(lpp_get_cst_count(pi->curr_lp));
 693         copystat_add_ilp_iter(lpp_get_iter_cnt(pi->curr_lp));
 694 #endif
 695
 696         sol = xmalloc((pi->last_x_var - pi->first_x_var + 1) * sizeof(*sol));
 697         state = lpp_get_solution(pi->curr_lp, sol, pi->first_x_var, pi->last_x_var);
 698         if (state != lpp_optimal) {
 699                 printf("WARNING %s: Solution state is not 'optimal': %d\n", pi->co->name, state);
 700                 assert(state >= lpp_feasible && "The solution should at least be feasible!");
 701                 res = 0;
 702         }
 703         for (i=0; i<pi->last_x_var - pi->first_x_var + 1; ++i) {
 704                 int nnr, col;
 705                 char var_name[64];
 706
 707                 if (sol[i] > 1-EPSILON) { /* split varibale name into components */
 708                         lpp_get_var_name(pi->curr_lp, pi->first_x_var+i, var_name, sizeof(var_name));
 709                         if (split_var(var_name, &nnr, &col) == 2) {
 710                                 DBG((dbg, LEVEL_2, "Irn %n  Idx %d  Var %s  Val %f\n", get_irn_for_graph_nr(pi->co->irg, nnr), i, var_name, sol[i]));
 711                                 DBG((dbg, LEVEL_2, "x%d = %d\n", nnr, col));
 712                                 set_irn_col(pi->co, get_irn_for_graph_nr(pi->co->irg, nnr), col);
 713                         } else
 714                                 assert(0 && "This should be a x-var");
 715                 }
 716         }
 717         return res;
 718 }
 719
 720
 721 int co_solve_ilp11(copy_opt_t *co, double time_limit) {
 722         int res = 1;
 723         problem_instance_t *pi;
 724
 725         dbg = firm_dbg_register("ir.be.copyoptilp1");
 726
 727         pi = new_pi(co);
 728
 729         sr_remove(pi->sr);                              /* problem size reduction */
 730         pi_construct(pi);                               /* set up the problem */
 731         pi_solve_ilp(pi, time_limit);   /* solve it */
 732         res = pi_apply_solution(pi);    /* apply solution */
 733         sr_reinsert(pi->sr);                    /* complete the partial solution */
 734
 735         free_pi(pi);
 736         return res;
 737 }
 738 #endif
 739
 740 #include "becopyilp_t.h"
 741
 742 #define DEBUG_LVL 1
 743
 744 typedef struct _my_env_t {
 745         int foo;
 746 } my_env_t;
 747
 748
 749 static void ilp2_build(ilp_env_t *ienv) {
 750         ienv->lp = new_lpp(ienv->co->name, lpp_minimize);
 751
 752 }
 753
 754 static void ilp2_apply(ilp_env_t *ienv) {
 755
 756 }
 757
 758 int co_solve_ilp1(copy_opt_t *co, double time_limit) {
 759         lpp_sol_state_t sol_state;
 760         ilp_env_t *ienv;
 761         my_env_t my;
 762         firm_dbg_module_t *dbg = firm_dbg_register("ir.be.coilp2");
 763
 764         firm_dbg_set_mask(dbg, DEBUG_LVL);
 765
 766         // my.bla = TODO
 767
 768         ienv = new_ilp_env(co, dbg, ilp2_build, ilp2_apply, &my);
 769
 770         sol_state = ilp_go(ienv, time_limit);
 771
 772         free_ilp_env(ienv);
 773
 774         return sol_state == lpp_optimal;
 775 }
 776
 777
 778 #else /* WITH_ILP */
 779
 780 static void only_that_you_can_compile_without_WITH_ILP_defined(void) {
 781 }
 782
 783 #endif /* WITH_ILP */