* Copyright: (c) Universitaet Karlsruhe
* Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
*
+ *
* ILP formalization using G=(V, E, Q):
- * - 1 class of variables: equal color vars
+ * - 2 class of variables: coloring vars x_ic and equal color vars y_ij
* - Path constraints
- * - Clique path constraints
+ * - Clique-star constraints
*
*
* \min \sum_{ (i,j) \in Q } w_ij y_ij
*
- * y_ij = 1 (i,j) \in E
+ * \sum_c x_nc = 1 n \in N, c \in C
*
- * \sum_c y_nc = |C| - 1 n \in N, c \in C
+ * x_nc = 0 n \in N, c \not\in C(n)
*
- * y_nc = 1 n \in N, c \not\in C(n)
+ * \sum x_nc <= 1 x_nc \in Clique \in AllCliques, c \in C
*
* \sum_{e \in p} y_e >= 1 p \in P path constraints
*
- * \sum_{e \in cp} y_e >= |cp| - 1 cp \in CP clique-path constraints
+ * \sum_{e \in cs} y_e >= |cs| - 1 cs \in CP clique-star constraints
*
- * y_ij \in N, w_ij \in R^+
+ * x_nc, y_ij \in N, w_ij \in R^+
*/
#ifdef HAVE_CONFIG_H
#ifdef WITH_ILP
+#include "irtools.h"
+#include "irgwalk.h"
#include "becopyilp_t.h"
#include "beifg_t.h"
-#include "irtools.h"
+#include "besched_t.h"
#define DEBUG_LVL 1
int i, col;
void *iter = be_ifg_cliques_iter_alloca(ifg);
- ir_node *clique = alloca(sizeof(*clique) * n_colors);
+ ir_node **clique = alloca(sizeof(*clique) * n_colors);
int size;
char buf[16];
/* for each maximal clique */
- be_ifg_foreach_clique(ifg, iter, &clique, &size) {
+ be_ifg_foreach_clique(ifg, iter, clique, &size) {
if (size < 2)
continue;
int cst_idx = lpp_add_cst(lpp, NULL, lpp_less, 1.0);
/* for each member of this clique */
- for (i=0; i<size, ++i) {
+ for (i=0; i<size; ++i) {
ir_node *irn = clique[i];
if (!sr_is_removed(ienv->sr, irn)) {
}
}
-static void build_path_cstr(ilp_env_t *ienv) {
+/**
+ *
+ */
+static void build_clique_star_cstr(ilp_env_t *ienv) {
}
-static void build_clique_path_cstr(ilp_env_t *ienv) {
+/**
+ *
+ */
+static void build_path_cstr(ilp_env_t *ienv) {
}
build_coloring_cstr(ienv);
build_interference_cstr(ienv);
build_affinity_cstr(ienv);
+ build_clique_star_cstr(ienv);
build_path_cstr(ienv);
- build_clique_path_cstr(ienv);
lower_bound = co_get_lower_bound(ienv->co) - co_get_inevit_copy_costs(ienv->co);
lpp_set_bound(ienv->lp, lower_bound);
static void ilp2_apply(ilp_env_t *ienv) {
local_env_t *lenv = ienv->env;
- double sol[];
+ double *sol;
lpp_sol_state_t state;
- int count;
+ int i, count;
count = lenv->last_x_var - lenv->first_x_var + 1;
sol = xmalloc(count * sizeof(sol[0]));
}
for (i=0; i<count; ++i) {
- char c;
int nodenr, color;
char var_name[16];