22 #include "bephicoalilp_t.h"
26 #include "bechordal_t.h"
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.
35 #define get_weight(n,m) 1
36 #define MAX_WEIGHT 127
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
42 /** define this to sth which returns 1 iff not all colors can be assigned to node n */
43 #define is_constrained(n) 0
52 #define SSH_USER_HOST "kb61@sp-smp.rz.uni-karlsruhe.de"
54 /* The overhead stuff */
55 #define DEBUG_LVL SET_LEVEL_1
56 #define SET_LIVING_INIT 32
60 static firm_dbg_module_t *dbgphi = NULL;
62 static INLINE FILE *ffopen(const char *base, const char *ext, const char *mode) {
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);
74 /** A type storing names of the x variables in the form x[NUMBER]_[COLOR] */
75 typedef struct _x_vec_t {
80 * A type storing the unmodified '0-1 quadratic program' of the form
86 * This problem is called the original problem
88 typedef struct _problem_instance_t {
91 int x_dim, A_dim, B_dim;
93 x_vec_t *x; /**< stores the names of the x variables. Sorted first by node-num then by color. */
95 /* needed only for linearizations */
96 int bigM, maxQij, minQij, correction;
98 /* overhead needed to build this */
103 } problem_instance_t;
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.
110 typedef struct _num2pos_t {
114 /* Nodes have consecutive numbers so... */
115 #define HASH_NUM(num) num
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;
122 * Sets the first position of node with number num to pos.
123 * See x_vec_t *x in _problem_instance_t.
125 static INLINE void pi_set_first_pos(problem_instance_t *pi, int num, int pos) {
129 set_insert(pi->num2pos, &find, sizeof(find), HASH_NUM(num));
133 * Get position by number. (First possible color)
134 * returns -1 if not found.
136 static INLINE int pi_get_first_pos(problem_instance_t *pi, int num) {
137 num2pos_t find, *found;
139 found = set_find(pi->num2pos, &find, sizeof(find), HASH_NUM(num));
141 assert(pi->x[found->pos].n == num && (found->pos == 0 || pi->x[found->pos-1].n != num) && "pi->num2pos is broken!");
148 * Get position by number and color.
149 * returns -1 if not found.
151 static INLINE int pi_get_pos(problem_instance_t *pi, int num, int col) {
152 num2pos_t find, *found;
155 found = set_find(pi->num2pos, &find, sizeof(find), HASH_NUM(num));
159 while (pos < pi->x_dim && pi->x[pos].n == num && pi->x[pos].c < col)
162 if (pi->x[pos].n == num && pi->x[pos].c == col)
169 * Checks if all nodes in living are live_out in block block.
171 static INLINE int all_live_out(ir_node *block, pset *living) {
173 for (n = pset_first(living); n; n = pset_next(living))
174 if (!is_live_out(block, n)) {
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.
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;
191 pset *living = pset_new_ptr(SET_LIVING_INIT);
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))
199 DBG((dbgphi, LEVEL_2, "Def %n\n", irn));
200 pset_insert_ptr(living, irn);
202 } else { /* is_use */
203 DBG((dbgphi, LEVEL_2, "Use %n\n", irn));
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)) {
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));
217 pset_remove_ptr(living, irn);
227 * Dump the raw matrices of the problem to a file for debugging.
229 static void pi_dump_matrices(problem_instance_t *pi) {
231 FILE *out = ffopen(pi->name, "matrix", "wt");
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);
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]);
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]);
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]);
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.
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");
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));
279 fprintf(out, "NAME %s\n", pi->name);
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);
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");
298 fprintf(out, " S1 SOS_%d\t'MARKER'\t'SOSORG'\n", sos_cnt++);
300 for (i=0; i<pi->x_dim; ++i) {
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++);
307 /* participation in objective */
308 fprintf(out, " x%d_%d\tobj\t%d\n", pi->x[i].n, pi->x[i].c, -pi->bigM);
310 for (o=0; o<pi->x_dim; ++o) {
311 int Qoi = pi->Q[o*pi->x_dim + i];
313 fprintf(out, " x%d_%d\tcQ%d\t%d\n", pi->x[i].n, pi->x[i].c, o, Qoi);
316 for (o=0; o<pi->A_dim; ++o) {
317 int Aoi = pi->A[o*pi->x_dim + i];
319 fprintf(out, " x%d_%d\tcA%d\t%d\n", pi->x[i].n, pi->x[i].c, o, Aoi);
322 for (o=0; o<pi->B_dim; ++o) {
323 int Boi = pi->B[o*pi->x_dim + i];
325 fprintf(out, " x%d_%d\tcB%d\t%d\n", pi->x[i].n, pi->x[i].c, o, Boi);
328 fprintf(out, " x%d_%d\tcy%d\t%d\n", pi->x[i].n, pi->x[i].c, i, 2*pi->bigM);
331 fprintf(out, " SOS_%d\t'MARKER'\t'SOSEND'\n", sos_cnt++);
333 fprintf(out, " MARKI1\t'MARKER'\t'INTEND'\n"); /* end of marking */
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);
340 fprintf(out, " s%d_%d\tcQ%d\t%d\n", pi->x[i].n, pi->x[i].c, i, -1);
343 /* next the y vars */
344 for (i=0; i<pi->x_dim; ++i) {
346 fprintf(out, " y%d_%d\tcQ%d\t%d\n", pi->x[i].n, pi->x[i].c, i, -1);
348 fprintf(out, " y%d_%d\tcy%d\t%d\n", pi->x[i].n, pi->x[i].c, i, 1);
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);
361 fprintf(out, "ENDATA\n");
364 out = ffopen(pi->name, "mst", "wt");
365 fprintf(out, "NAME\n");
366 for (i=0; i<pi->x_dim; ++i) {
370 if (get_irn_color(get_irn_for_graph_nr(pi->irg, n)) == c)
374 fprintf(out, " x%d_%d\t%d\n", n, c, val);
376 fprintf(out, "ENDATA\n");
381 #if defined(DUMP_LPO) || defined(DUMP_LPP)
383 * Dumps constraints used by both linearizations
385 static void pi_dump_lp_common_constraints(problem_instance_t *pi, FILE *out) {
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");
394 fprintf(out, "\n\n");
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");
403 fprintf(out, "\n\n");
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);
415 * Dumps the problem instance as a MILP. The original problem is transformed into:
417 * udN: Qx -y -s +Me = 0
423 * with M >= max sum Q'ij * x_j
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");
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));
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");
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];
450 fprintf(out, "+x%d_%d ", pi->x[o].n, pi->x[o].c);
452 fprintf(out, "-x%d_%d ", pi->x[o].n, pi->x[o].c);
454 fprintf(out, "%+dx%d_%d ", Qio, pi->x[o].n, pi->x[o].c);
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);
459 fprintf(out, "\n\n");
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");
466 pi_dump_lp_common_constraints(pi, out);
473 * Dumps the problem instance as a MILP. The original problem is transformed into:
481 * with Q' = (q'_ij) := q_ij - minQij
482 * and M >= max sum Q'ij * x_j
485 static void pi_dump_lp_pos(problem_instance_t *pi) {
487 FILE *out = ffopen(pi->name, "lpp", "wt");
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 */
496 /* calc the big M for Q'
497 * maxQ'ij = maxQij-minQij
499 * So max sum Q'ij * x_j <= A_dim * maxQ'ij
502 pi->bigM = pi->A_dim * (pi->maxQij - pi->minQij);
503 DBG((dbgphi, LEVEL_2, "BigM = %d\n", pi->bigM));
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
510 pi->correction = pi->minQij * pi->A_dim * pi->A_dim;
511 DBG((dbgphi, LEVEL_2, "Correction = %d\n", pi->correction));
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");
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];
527 fprintf(out, "+%d", Qio);
528 fprintf(out, "+x%d_%d ", pi->x[o].n, pi->x[o].c);
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);
533 fprintf(out, "\n\n");
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");
540 pi_dump_lp_common_constraints(pi, out);
547 * Invoke an external solver
549 static void pi_solve_ilp(problem_instance_t *pi) {
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");
565 snprintf(buf, sizeof(buf), "scp %s.mps %s.mst %s.cmd %s:", pi->name, pi->name, pi->name, SSH_USER_HOST);
567 snprintf(buf, sizeof(buf), "ssh %s \"./cplex90 < %s.cmd\"", SSH_USER_HOST, pi->name);
569 snprintf(buf, sizeof(buf), "scp %s:%s.sol .", SSH_USER_HOST, pi->name);
574 * Sets the colors of irns according to the values of variables found in the
575 * output file of the solver.
577 static void pi_apply_solution(problem_instance_t *pi) {
578 FILE *in = ffopen(pi->name, "sol", "rt");
580 DBG((dbgphi, LEVEL_1, "Applying solution...\n"));
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);
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);
595 #endif /* DO_SOLVE */
598 static void pi_delete_files(problem_instance_t *pi) {
600 int end = snprintf(buf, sizeof(buf), "%s", pi->name);
602 snprintf(buf+end, sizeof(buf)-end, ".matrix");
606 snprintf(buf+end, sizeof(buf)-end, ".mps");
608 snprintf(buf+end, sizeof(buf)-end, ".mst");
610 snprintf(buf+end, sizeof(buf)-end, ".cmd");
614 snprintf(buf+end, sizeof(buf)-end, ".lpo");
618 snprintf(buf+end, sizeof(buf)-end, ".lpp");
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
631 * TODO Prove the above.
633 * This function returns M in env, where N <= M <= MAX_COLROS
635 static void pi_colors_upper_bound(ir_node *block, void *env) {
637 int i, max, max_pressure, special_cnt;
638 if (*res == MAX_COLORS)
641 /* get maximal register pressure */
643 struct list_head *head = &get_ra_block_info(block)->border_head;
646 list_for_each_entry(border_t, b, head, list)
647 if (b->pressure > max_pressure) {
648 max_pressure = b->pressure;
652 /* count special nodes */
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)
658 if (is_Phi(n) || is_phi_operand(n) || is_constrained(n))
663 if (*res < max_pressure + special_cnt)
664 *res = max_pressure + special_cnt;
665 if (*res > MAX_COLORS)
670 * Generate the initial problem matrices and vectors.
672 static problem_instance_t *new_pi(ir_graph *irg, pset *all_phi_nodes) {
674 problem_instance_t *pi = calloc(1, sizeof(problem_instance_t));
676 pi->name = get_entity_name(get_irg_entity(irg));
678 pi->minQij = MIN_Q_INIT;
679 pi->maxQij = MAX_Q_INIT;
680 obstack_init(&pi->ob);
682 DBG((dbgphi, LEVEL_1, "Generating new instance...\n"));
683 pi->num2pos = new_set(pi_num2pos_cmp, 128);
685 //TODO move pi_colors_upper_bound in "super-class" to fix issue with
687 /* get max_needed_cols */
689 dom_tree_walk_irg(irg, pi_colors_upper_bound, NULL, &max_needed_cols);
691 max_needed_cols = MAX_COLORS;
692 DBG((dbgphi, LEVEL_1, "max_needed_cols: %d\n", max_needed_cols));
695 * one entry per node and possible color */
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);
701 if (!is_allocatable_irn(irn))
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);
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))
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 */
715 pi->x = obstack_finish(&pi->ob);
719 * weights for the 'same-color-optimization' target */
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;
728 for (i = 0, max = get_irn_arity(phi); i < max; ++i) {
730 arg = get_irn_n(phi, i);
731 if (phi_ops_interfere(phi, arg))
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);
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)
746 else if (pi->x[phipos].c > pi->x[argpos].c)
749 pi->Q[(phipos++)*pi->x_dim + argpos++] = weight;
751 if (weight < pi->minQij) {
752 DBG((dbgphi, LEVEL_2, "minQij = %d\n", weight));
755 if (weight > pi->maxQij) {
756 DBG((dbgphi, LEVEL_2, "maxQij = %d\n", weight));
766 * knapsack constraint for each node */
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;
778 assert(row == pi->A_dim);
782 * interference constraints using exactly those cliques not contained in others. */
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]));
788 for (col = 0; col < max_needed_cols; ++col) {
790 dom_tree_walk_irg(irg, pi_clique_finder, NULL, pi);
793 pi->B_dim = pi->curr_row;
794 pi->B = realloc(pi->B, pi->B_dim*pi->x_dim*sizeof(pi->B[0]));
801 * clean the problem instance
803 static void free_pi(problem_instance_t *pi) {
807 del_set(pi->num2pos);
808 obstack_free(&pi->ob, NULL);
812 void be_phi_coalesce_ilp(ir_graph *irg, pset *all_phi_nodes) {
813 problem_instance_t *pi = new_pi(irg, all_phi_nodes);
816 pi_dump_matrices(pi);
833 pi_apply_solution(pi);
843 void be_phi_coal_ilp_init(void) {
844 dbgphi = firm_dbg_register("ir.be.phicoalilp");
845 firm_dbg_set_mask(dbgphi, DEBUG_LVL);