-/**
- * Finds cliques in the interference graph, considering only nodes
- * for which the color @p color is possible. Finds only 'maximal-cliques',
- * viz cliques which are not contained in another one.
- * Matrix B: interference constraints using cliques
- */
-static void pi_add_constr_B(problem_instance_t *pi, int color) {
- enum phase_t {growing, shrinking} phase = growing;
- border_t *b;
- pmap_entry *pme;
- pset *living = pset_new_ptr(SLOTS_LIVING);
-
- DBG((dbg, LEVEL_2, "Add B constraints (col = %d)...\n", color));
- /* iterate over all blocks */
- pmap_foreach(pi->co->chordal_env->border_heads, pme) {
- ir_node *block = pme->key;
- struct list_head *head = pme->value;
-
- list_for_each_entry_reverse(border_t, b, head, list) {
- const ir_node *irn = b->irn;
- if (is_removed(irn) || !is_color_possible(irn, color))
- continue;
-
- if (b->is_def) {
- DBG((dbg, LEVEL_2, "Def %n\n", irn));
- pset_insert_ptr(living, irn);
- phase = growing;
- } else { /* is_use */
- DBG((dbg, LEVEL_2, "Use %n\n", irn));
-
- /* before shrinking the set, store the current 'maximum' clique;
- * do NOT if clique is a single node
- * do NOT if all values are live_in (in this case they were contained in a live-out clique elsewhere) */
- if (phase == growing && pset_count(living) >= 2 && !all_live_in(block, living)) {
- int cst_idx;
- ir_node *n;
- mangle_cst(pi->buf, 'B', pi->cst_counter);
- cst_idx = lpp_add_cst(pi->curr_lp, pi->buf, lpp_less, 1);
- for (n = pset_first(living); n; n = pset_next(living)) {
- int var_idx;
- mangle_var_irn(pi->buf, 'x', n, color);
- var_idx = lpp_get_var_idx(pi->curr_lp, pi->buf);
- lpp_set_factor_fast(pi->curr_lp, cst_idx, var_idx, 1);
- }
- pi->cst_counter++;
- }
- pset_remove_ptr(living, irn);
- phase = shrinking;
- }
- }
- }
- assert(0 == pset_count(living));
- del_pset(living);
-}
-/**
- * Generates constraints which interrelate x with y variables.
- * x1 and x2 have the different colors ==> y_12 = 1
- */
-static void pi_add_constr_E_new_reverse(problem_instance_t *pi) {
- unit_t *curr;
- bitset_t *root_regs, *arg_regs, *work_regs;
- int cst_counter = 0;
- unsigned nregs = pi->co->chordal_env->cls->n_regs;
- root_regs = bitset_alloca(nregs);
- arg_regs = bitset_alloca(nregs);
- work_regs = bitset_alloca(nregs);
-
- DBG((dbg, LEVEL_2, "Add E constraints...\n"));
- /* for all roots of optimization units */
- list_for_each_entry(unit_t, curr, &pi->co->units, units) {
- ir_node *root, *arg;
- int rootnr, argnr, color;
- int y_idx, i;
- char buf[32];
-
- root = curr->nodes[0];
- rootnr = get_irn_graph_nr(root);
- bitset_clear_all(root_regs);
- arch_get_allocatable_regs(get_arch_env(pi->co), root, arch_pos_make_out(0), pi->co->chordal_env->cls, root_regs);
-
- /* for all arguments of root */
- for (i = 1; i < curr->node_count; ++i) {
- int extra_cst_idx;
-
- arg = curr->nodes[i];
- argnr = get_irn_graph_nr(arg);
- bitset_clear_all(arg_regs);
- arch_get_allocatable_regs(get_arch_env(pi->co), arg, arch_pos_make_out(0), pi->co->chordal_env->cls, arg_regs);
-
- /* For all colors root and arg have in common, add 2 constraints to E */
- bitset_copy(work_regs, root_regs);
- bitset_and(work_regs, arg_regs);
-
- /* y_ij1 + y_ij2 + .... + y_ijk <= 1 */
- mangle_cst(buf, 'Z', cst_counter++);
- extra_cst_idx = lpp_add_cst(pi->curr_lp, buf, lpp_greater, bitset_popcnt(work_regs)-1);
-
- bitset_foreach(work_regs, color) {
- int root_idx, arg_idx, cst_idx;
-
- /* Introduce new variable and set factor in objective function */
- mangle_var3(buf, 'y', rootnr, argnr, color);
- y_idx = lpp_add_var(pi->curr_lp, buf, lpp_binary, curr->costs[i]);
-
- /* add new y var to the extra Z constraint */
- lpp_set_factor_fast(pi->curr_lp, extra_cst_idx, y_idx, 1);
-
- /* set starting value */
- lpp_set_start_value(pi->curr_lp, y_idx, (get_irn_col(pi->co, root)==color && get_irn_col(pi->co, arg)==color) );
-
- mangle_var(buf, 'x', rootnr, color);
- root_idx = lpp_get_var_idx(pi->curr_lp, buf);
- mangle_var(buf, 'x', argnr, color);
- arg_idx = lpp_get_var_idx(pi->curr_lp, buf);
-
- /* add root+y >= 1 */
- mangle_cst(buf, 'E', cst_counter++);
- cst_idx = lpp_add_cst(pi->curr_lp, buf, lpp_greater, 1);
- lpp_set_factor_fast(pi->curr_lp, cst_idx, root_idx, 1);
- lpp_set_factor_fast(pi->curr_lp, cst_idx, y_idx, 1);
-
- /* add arg+y >= 1 */
- mangle_cst(buf, 'E', cst_counter++);
- cst_idx = lpp_add_cst(pi->curr_lp, buf, lpp_greater, 1);
- lpp_set_factor_fast(pi->curr_lp, cst_idx, arg_idx, 1);
- lpp_set_factor_fast(pi->curr_lp, cst_idx, y_idx, 1);
- }
- }
- }
-}