4 * Copyright: (c) Universitaet Karlsruhe
5 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
8 * ILP formalization using:
9 * - 2 classes of vars: Nodes- and optimality variables.
10 * - Clique constraints
12 * - Clique path constraints
17 #endif /* HAVE_CONFIG_H */
21 #include "becopyilp_t.h"
30 #include "iredges_t.h"
32 #include "becopystat.h"
33 #include "besched_t.h"
38 #define PATH_CONSTRAINTS_FOR_CLASSES
40 typedef struct _problem_instance_t {
41 const copy_opt_t *co; /**< the copy opt problem */
42 size_red_t *sr; /**< problem size reduction. removes simple nodes */
43 lpp_t *lp; /**< the linear programming problem */
45 /* Helpers for maintaining indices and finding variables */
46 int first_nnc_var_idx; /**< the first index of a constraint belonging to no-null-colors stuff*/
47 int cst_counter, first_x_var, last_x_var;
52 #define is_color_possible(irn,color) arch_reg_is_allocatable(pi->co->aenv, irn, -1, arch_register_for_index(pi->co->cls, color))
55 * Some stuff for variable name handling.
57 #define mangle_cst(buf, prefix, nr) \
58 snprintf((buf), sizeof(buf), "%c%d", (prefix), (nr))
60 #define mangle_var1(buf, prefix, color) \
61 snprintf((buf), sizeof(buf), "%c%d", (prefix), (color))
63 #define mangle_var2(buf, prefix, node_nr, color) \
64 snprintf((buf), sizeof(buf), "%c%d_%d", (prefix), (node_nr), (color))
66 #define mangle_var3(buf, prefix, n1, n2, col) \
67 snprintf((buf), sizeof(buf), "%c%d_%d_%d", (prefix), (n1), (n2), (col))
69 #define mangle_var_irn(buf, prefix, irn, color) \
70 mangle_var2((buf), (prefix), get_irn_graph_nr(irn), (color))
72 #define split_var(var, nnr, col) \
73 sscanf(var, "x%d_%d", (nnr), (col))
76 #ifndef PATH_CONSTRAINTS_FOR_CLASSES
78 * Matrix P: Path contraints.
79 * If 2 nodes interfere and there is a path of equal-color-edges
80 * connecting them, then at least one of those equal-color-edges
81 * will break and cause some costs.
83 static void pi_add_path_cstr(problem_instance_t *pi) {
86 DBG((dbg, LEVEL_2, "Adding path constraints...\n"));
88 /* for all optimization units (only phis) */
89 list_for_each_entry(unit_t, curr, &pi->co->units, units) {
92 if (curr->min_nodes_costs == 0)
95 rootnr = get_irn_graph_nr(curr->nodes[0]);
96 /* check all argument pairs for interference */
97 for (i=1; i<curr->node_count; ++i) {
98 const ir_node *arg1 = curr->nodes[i];
99 int arg1nr = get_irn_graph_nr(arg1);
100 for (o=i+1; o<curr->node_count; ++o) {
101 const ir_node *arg2 = curr->nodes[o];
102 int arg2nr = get_irn_graph_nr(arg2);
103 if (nodes_interfere(pi->co->cenv, arg1, arg2)) {
107 mangle_cst(buf, 'P', cst_counter++);
108 cst_idx = lpp_add_cst(pi->curr_lp, buf, lpp_greater, 1);
110 mangle_var2(buf, 'y', rootnr, arg1nr);
111 y_idx = lpp_get_var_idx(pi->curr_lp, buf);
112 lpp_set_factor_fast(pi->curr_lp, cst_idx, y_idx, 1);
114 mangle_var2(buf, 'y', rootnr, arg2nr);
115 y_idx = lpp_get_var_idx(pi->curr_lp, buf);
116 lpp_set_factor_fast(pi->curr_lp, cst_idx, y_idx, 1);
124 #ifdef PATH_CONSTRAINTS_FOR_CLASSES
125 static INLINE int get_y_var_idx(problem_instance_t *pi, int nnr1, int nnr2) {
129 mangle_var2(buf, 'y', nnr1, nnr2);
130 if ((res = lpp_get_var_idx(pi->curr_lp, buf)) != -1)
133 mangle_var2(buf, 'y', nnr2, nnr1);
134 if ((res = lpp_get_var_idx(pi->curr_lp, buf)) != -1)
137 assert(0 && "One of them must work");
141 static void check_ecc_and_add_cut(problem_instance_t *pi, ir_node **path, int length, pset *remain, ir_node *tgt) {
142 if (path[length-1] == tgt) { /* we found a path */
143 int cst_idx, var_idx, i, nnr1, nnr2;
147 mangle_cst(buf, 'Q', pi->cst_counter++);
148 cst_idx = lpp_add_cst(pi->curr_lp, buf, lpp_greater, 1);
150 /* add all vars along the path */
151 nnr2 = get_irn_graph_nr(path[0]);
152 for (i=1; i<length; ++i) {
154 nnr2 = get_irn_graph_nr(path[i]);
155 var_idx = get_y_var_idx(pi, nnr1, nnr2);
156 lpp_set_factor_fast(pi->curr_lp, cst_idx, var_idx, 1);
158 } else { /* try to extend the path */
159 be_chordal_env_t *cenv = pi->co->cenv;
160 const ir_edge_t *edge;
161 ir_node *end = path[length-1];
162 ir_node **next = alloca(pset_count(remain) * sizeof(*next));
163 int i, o, max, next_pos = 0;
164 pset *done = pset_new_ptr_default();
166 /* find all potential next nodes on path */
169 for(i=0, max=get_irn_arity(end); i<max; ++i) {
170 ir_node *arg = get_irn_n(end, i);
171 if (!pset_find_ptr(done, arg) && pset_find_ptr(remain, arg)) {
172 next[next_pos++] = arg;
173 pset_insert_ptr(done, arg);
176 /* outs of phis and other nodes */
177 foreach_out_edge(end, edge) {
178 ir_node *user = edge->src;
179 if (is_Phi(user) && !pset_find_ptr(done, user) && pset_find_ptr(remain, user)) {
180 next[next_pos++] = user;
181 pset_insert_ptr(done, user);
187 /* delete all potential nodes with interferences to other nodes in the path */
188 for (i=0; i<next_pos; ++i) {
189 ir_node *nn = next[i];
191 /* if next is the tgt, it may interfere with path[0],
192 * so skip the first check */
193 o = (nn == tgt && length > 1) ? 1 : 0;
196 if (nodes_interfere(cenv, nn, path[o])) {
201 /* now we have all possible nodes in next; impossibles are NULL */
203 /* try to finish path with all possible nodes */
204 for (i=0; i<next_pos; ++i) {
205 if (!next[i]) /* this was an impossible node */
208 path[length] = next[i];
209 pset_remove_ptr(remain, next[i]);
210 check_ecc_and_add_cut(pi, path, length+1, remain, tgt);
211 pset_insert_ptr(remain, next[i]);
216 static void path_cstr_for_classes_walker(ir_node *irn, void *env) {
217 problem_instance_t *pi = env;
218 be_chordal_env_t *cenv;
221 pset *class = get_phi_class(irn);
222 if (!class || pset_find_ptr(pi->done, class))
225 pset_insert_ptr(pi->done, class);
228 max = pset_count(class);
229 cls = alloca(max * sizeof(*cls));
230 for(i=0, m = pset_first(class); m; i++, m = pset_next(class)) {
231 DBG((dbg, LEVEL_1, " class member: %+F\n", m));
236 for(i=0; i<max; ++i) {
237 ir_node **path = alloca(max * sizeof(*path));
238 pset *remain = pset_new_ptr(8);
239 pset_insert_pset_ptr(remain, class);
241 /* add cls[i] to path and remove it from remainder */
243 pset_remove_ptr(remain, cls[i]);
245 for(o=i+1; o<max; ++o)
246 if (nodes_interfere(cenv, cls[i], cls[o]))
247 check_ecc_and_add_cut(pi, path, 1, remain, cls[o]);
249 /* insert back into remainder */
250 pset_insert_ptr(remain, cls[i]);
256 * Matrix P: Path contraints.
257 * If 2 nodes interfere and there is a path of equal-color-edges
258 * connecting them, then at least one of those equal-color-edges
259 * will break and cause some costs.
261 static void pi_add_path_cstr_for_classes(problem_instance_t *pi) {
262 DBG((dbg, LEVEL_2, "Adding path constraints for phi classes...\n"));
264 pi->done = pset_new_ptr_default();
265 irg_walk_graph(pi->co->irg, path_cstr_for_classes_walker, NULL, pi);
270 static void pi_construct(problem_instance_t *pi) {
271 pi_add_path_cstr_for_classes(pi);
272 pi_add_path_cstr(pi);
273 pi_add_clique_path_cstr(pi);
277 #include "becopyilp_t.h"
281 typedef struct _my_env_t {
286 static void ilp1_build(ilp_env_t *ienv) {
287 ienv->lp = new_lpp(ienv->co->name, lpp_minimize);
291 static void ilp1_apply(ilp_env_t *ienv) {
295 int co_solve_ilp1(copy_opt_t *co, double time_limit) {
302 static void only_that_you_can_compile_without_WITH_ILP_defined(void) {
305 #endif /* WITH_ILP */