4 * Copyright: (c) Universitaet Karlsruhe
5 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
7 * ILP formalization using G=(V, E, Q):
8 * - 1 class of variables: equal color vars
10 * - Clique path constraints
13 * \min \sum_{ (i,j) \in Q } w_ij y_ij
15 * y_ij = 1 (i,j) \in E
17 * \sum_c y_nc = |C| - 1 n \in N, c \in C
19 * y_nc = 1 n \in N, c \not\in C(n)
21 * \sum_{e \in p} y_e >= 1 p \in P path constraints
23 * \sum_{e \in cp} y_e >= |cp| - 1 cp \in CP clique-path constraints
25 * y_ij \in N, w_ij \in R^+
30 #endif /* HAVE_CONFIG_H */
34 #include "becopyilp_t.h"
40 typedef struct _local_env_t {
41 firm_dbg_module_t *dbg;
43 int first_x_var, last_x_var;
47 static void build_coloring_cstr(ilp_env_t *ienv) {
48 be_ifg_t *ifg = ienv->co->cenv->ifg;
49 void *iter = be_ifg_nodes_iter_alloca(ifg);
54 colors = bitset_alloca(arch_register_class_n_regs(ienv->co->cls));
56 be_ifg_foreach_node(ifg, iter, irn)
57 if (!sr_is_removed(ienv->sr, irn)) {
59 arch_register_req_t req;
60 int curr_node_color = get_irn_col(ienv->co, irn);
61 int node_nr = (int)get_irn_node_nr(irn);
62 local_env_t *lenv = ienv->env;
64 pmap_insert(lenv->nr_2_irn, INT_TO_PTR(node_nr), irn);
66 arch_get_register_req(ienv->co->aenv, &req, irn, -1);
68 /* get assignable colors */
69 if (arch_register_req_is(&req, limited))
70 req.limited(req.limited_env, colors);
72 arch_put_non_ignore_regs(ienv->co->aenv, req.cls, colors);
74 /* add the coloring constraint */
75 cst_idx = lpp_add_cst(ienv->lp, NULL, lpp_equal, 1.0);
77 bitset_foreach(colors, col) {
78 int var_idx = lpp_add_var(ienv->lp, name_cdd(buf, 'x', node_nr, col), lpp_binary, 0.0);
79 lpp_set_start_value(ienv->lp, var_idx, (col == curr_node_color) ? 1.0 : 0.0);
80 lpp_set_factor_fast(ienv->lp, cst_idx, var_idx, 1);
82 lenv->last_x_var = var_idx;
83 if (lenv->first_x_var == -1)
84 lenv->first_x_var = var_idx;
87 /* add register constraint constraints */
88 bitset_foreach_clear(colors, col) {
89 int cst_idx = lpp_add_cst(ienv->lp, NULL, lpp_equal, 0.0);
90 int var_idx = lpp_add_var(ienv->lp, name_cdd(buf, 'x', node_nr, col), lpp_binary, 0.0);
91 lpp_set_start_value(ienv->lp, var_idx, 0.0);
92 lpp_set_factor_fast(ienv->lp, cst_idx, var_idx, 1);
94 lenv->last_x_var = var_idx;
99 static void build_interference_cstr(ilp_env_t *ienv) {
100 lpp_t *lpp = ienv->lp;
101 be_ifg_t *ifg = ienv->co->cenv->ifg;
102 int n_colors = arch_register_class_n_regs(ienv->co->cls);
105 void *iter = be_ifg_cliques_iter_alloca(ifg);
106 ir_node **clique = alloca(sizeof(*clique) * n_colors);
111 /* for each maximal clique */
112 be_ifg_foreach_clique(ifg, iter, clique, &size) {
118 for (col=0; col<n_colors; ++col) {
119 int cst_idx = lpp_add_cst(lpp, NULL, lpp_less, 1.0);
121 /* for each member of this clique */
122 for (i=0; i<size; ++i) {
123 ir_node *irn = clique[i];
125 if (!sr_is_removed(ienv->sr, irn)) {
126 int var_idx = lpp_get_var_idx(lpp, name_cdd(buf, 'x', (int)get_irn_node_nr(irn), col));
127 lpp_set_factor_fast(lpp, cst_idx, var_idx, 1);
134 static void build_affinity_cstr(ilp_env_t *ienv) {
136 int n_colors = arch_register_class_n_regs(ienv->co->cls);
138 /* for all optimization units */
139 list_for_each_entry(unit_t, curr, &ienv->co->units, units) {
141 int root_nr, arg_nr, i, col, y_idx, root_idx, arg_idx;
143 int root_col, arg_col;
145 root = curr->nodes[0];
146 root_nr = (int) get_irn_node_nr(root);
147 root_col = get_irn_col(ienv->co, root);
149 for (i = 1; i < curr->node_count; ++i) {
150 arg = curr->nodes[i];
151 arg_nr = (int) get_irn_node_nr(arg);
152 arg_col = get_irn_col(ienv->co, arg);
154 /* add a new affinity variable */
155 y_idx = lpp_add_var(ienv->lp, name_cdd_sorted(buf, 'y', root_nr, arg_nr), lpp_binary, curr->costs[i]);
156 lpp_set_start_value(ienv->lp, y_idx, (root_col==arg_col) ? 0.0 : 1.0);
158 /* add constraints relating the affinity var to the color vars */
159 for (col=0; col<n_colors; ++col) {
160 int cst_idx = lpp_add_cst(ienv->lp, NULL, lpp_less, 0.0);
161 root_idx = lpp_get_var_idx(ienv->lp, name_cdd(buf, 'x', root_nr, col));
162 arg_idx = lpp_get_var_idx(ienv->lp, name_cdd(buf, 'x', arg_nr, col));
164 lpp_set_factor_fast(ienv->lp, cst_idx, root_idx, 1.0);
165 lpp_set_factor_fast(ienv->lp, cst_idx, arg_idx, -1.0);
166 lpp_set_factor_fast(ienv->lp, cst_idx, root_idx, -1.0);
172 static void build_path_cstr(ilp_env_t *ienv) {
176 static void build_clique_path_cstr(ilp_env_t *ienv) {
180 static void ilp2_build(ilp_env_t *ienv) {
181 local_env_t *lenv = ienv->env;
184 ienv->lp = new_lpp(ienv->co->name, lpp_minimize);
185 build_coloring_cstr(ienv);
186 build_interference_cstr(ienv);
187 build_affinity_cstr(ienv);
188 build_path_cstr(ienv);
189 build_clique_path_cstr(ienv);
191 lower_bound = co_get_lower_bound(ienv->co) - co_get_inevit_copy_costs(ienv->co);
192 lpp_set_bound(ienv->lp, lower_bound);
193 lpp_set_time_limit(ienv->lp, lenv->time_limit);
196 static void ilp2_apply(ilp_env_t *ienv) {
197 local_env_t *lenv = ienv->env;
199 lpp_sol_state_t state;
202 count = lenv->last_x_var - lenv->first_x_var + 1;
203 sol = xmalloc(count * sizeof(sol[0]));
204 state = lpp_get_solution(ienv->lp, sol, lenv->first_x_var, lenv->last_x_var);
205 if (state != lpp_optimal) {
206 printf("WARNING %s: Solution state is not 'optimal': %d\n", ienv->co->name, state);
207 assert(state >= lpp_feasible && "The solution should at least be feasible!");
210 for (i=0; i<count; ++i) {
214 if (sol[i] > 1-EPSILON) { /* split variable name into components */
215 lpp_get_var_name(ienv->lp, lenv->first_x_var+i, var_name, sizeof(var_name));
217 if (sscanf(var_name, "x_%d_%d", &nodenr, &color) == 2) {
218 ir_node *irn = pmap_get(lenv->nr_2_irn, INT_TO_PTR(nodenr));
219 assert(irn && "This node number must be present in the map");
221 set_irn_col(ienv->co, irn, color);
223 assert(0 && "This should be a x-var");
228 /* TODO adapt to multiple possible ILPs */
229 copystat_add_ilp_time((int)(1000.0*lpp_get_sol_time(pi->curr_lp))); //now we have ms
230 copystat_add_ilp_vars(lpp_get_var_count(pi->curr_lp));
231 copystat_add_ilp_csts(lpp_get_cst_count(pi->curr_lp));
232 copystat_add_ilp_iter(lpp_get_iter_cnt(pi->curr_lp));
236 int co_solve_ilp2(copy_opt_t *co, double time_limit) {
237 lpp_sol_state_t sol_state;
241 my.time_limit = time_limit;
244 my.nr_2_irn = pmap_create();
245 my.dbg = firm_dbg_register("ir.be.coilp2");
246 firm_dbg_set_mask(my.dbg, DEBUG_LVL);
248 ienv = new_ilp_env(co, ilp2_build, ilp2_apply, &my);
250 sol_state = ilp_go(ienv);
252 pmap_destroy(my.nr_2_irn);
255 return sol_state == lpp_optimal;
260 static void only_that_you_can_compile_without_WITH_ILP_defined(void) {
263 #endif /* WITH_ILP */