nsz Git - libfirm/blob - ir/be/becopyilp2.c

   1 /**
   2  * Author:      Daniel Grund
   3  * Date:                28.02.2006
   4  * Copyright:   (c) Universitaet Karlsruhe
   5  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
   6  *
   7  *
   8  * ILP formalization using G=(V, E, Q):
   9  *  - 2 class of variables: coloring vars x_ic   and   equal color vars y_ij
  10  *  - Path constraints
  11  *  - Clique-star constraints
  12  *
  13  *
  14  *      \min \sum_{ (i,j) \in Q }  w_ij y_ij
  15  *
  16  *              \sum_c x_nc                     =  1                    n \in N, c \in C
  17  *
  18  *              x_nc                            =  0                    n \in N, c \not\in C(n)
  19  *
  20  *              \sum x_nc                       <= 1                    x_nc \in Clique \in AllCliques,  c \in C
  21  *
  22  *              \sum_{e \in p} y_e      >= 1                    p \in P         path constraints
  23  *
  24  *              \sum_{e \in cs} y_e     >= |cs| - 1             cs \in CP       clique-star constraints
  25  *
  26  *              x_nc, y_ij \in N,   w_ij \in R^+
  27  */
  28
  29 #ifdef HAVE_CONFIG_H
  30 #include "config.h"
  31 #endif /* HAVE_CONFIG_H */
  32
  33 #ifdef WITH_ILP
  34
  35 #include "irtools.h"
  36 #include "irgwalk.h"
  37 #include "becopyilp_t.h"
  38 #include "beifg_t.h"
  39 #include "besched_t.h"
  40
  41 #define DEBUG_LVL 1
  42
  43 typedef struct _local_env_t {
  44         firm_dbg_module_t *dbg;
  45         double time_limit;
  46         int first_x_var, last_x_var;
  47         pmap *nr_2_irn;
  48 } local_env_t;
  49
  50 static void build_coloring_cstr(ilp_env_t *ienv) {
  51         be_ifg_t *ifg = ienv->co->cenv->ifg;
  52         void *iter = be_ifg_nodes_iter_alloca(ifg);
  53         bitset_t *colors;
  54         ir_node *irn;
  55         char buf[16];
  56
  57         colors = bitset_alloca(arch_register_class_n_regs(ienv->co->cls));
  58
  59         be_ifg_foreach_node(ifg, iter, irn)
  60                 if (!sr_is_removed(ienv->sr, irn)) {
  61                         int col, cst_idx;
  62                         arch_register_req_t req;
  63                         int curr_node_color = get_irn_col(ienv->co, irn);
  64                         int node_nr = (int)get_irn_node_nr(irn);
  65                         local_env_t *lenv = ienv->env;
  66
  67                         pmap_insert(lenv->nr_2_irn, INT_TO_PTR(node_nr), irn);
  68
  69                         arch_get_register_req(ienv->co->aenv, &req, irn, -1);
  70
  71                         /* get assignable colors */
  72                         if (arch_register_req_is(&req, limited))
  73                                 req.limited(req.limited_env, colors);
  74                         else
  75                                 arch_put_non_ignore_regs(ienv->co->aenv, req.cls, colors);
  76
  77                         /* add the coloring constraint */
  78                         cst_idx = lpp_add_cst(ienv->lp, NULL, lpp_equal, 1.0);
  79
  80                         bitset_foreach(colors, col) {
  81                                 int var_idx = lpp_add_var(ienv->lp, name_cdd(buf, 'x', node_nr, col), lpp_binary, 0.0);
  82                                 lpp_set_start_value(ienv->lp, var_idx, (col == curr_node_color) ? 1.0 : 0.0);
  83                                 lpp_set_factor_fast(ienv->lp, cst_idx, var_idx, 1);
  84
  85                                 lenv->last_x_var = var_idx;
  86                                 if (lenv->first_x_var == -1)
  87                                         lenv->first_x_var = var_idx;
  88                         }
  89
  90                         /* add register constraint constraints */
  91                         bitset_foreach_clear(colors, col) {
  92                                 int cst_idx = lpp_add_cst(ienv->lp, NULL, lpp_equal, 0.0);
  93                                 int var_idx = lpp_add_var(ienv->lp, name_cdd(buf, 'x', node_nr, col), lpp_binary, 0.0);
  94                                 lpp_set_start_value(ienv->lp, var_idx, 0.0);
  95                                 lpp_set_factor_fast(ienv->lp, cst_idx, var_idx, 1);
  96
  97                                 lenv->last_x_var = var_idx;
  98                         }
  99                 }
 100 }
 101
 102 static void build_interference_cstr(ilp_env_t *ienv) {
 103         lpp_t *lpp = ienv->lp;
 104         be_ifg_t *ifg = ienv->co->cenv->ifg;
 105         int n_colors = arch_register_class_n_regs(ienv->co->cls);
 106         int i, col;
 107
 108         void *iter = be_ifg_cliques_iter_alloca(ifg);
 109         ir_node **clique = alloca(sizeof(*clique) * n_colors);
 110         int size;
 111
 112         char buf[16];
 113
 114         /* for each maximal clique */
 115         be_ifg_foreach_clique(ifg, iter, clique, &size) {
 116
 117                 if (size < 2)
 118                         continue;
 119
 120                 /* for all colors */
 121                 for (col=0; col<n_colors; ++col) {
 122                         int cst_idx = lpp_add_cst(lpp, NULL, lpp_less, 1.0);
 123
 124                         /* for each member of this clique */
 125                         for (i=0; i<size; ++i) {
 126                                 ir_node *irn = clique[i];
 127
 128                                 if (!sr_is_removed(ienv->sr, irn)) {
 129                                         int var_idx = lpp_get_var_idx(lpp, name_cdd(buf, 'x', (int)get_irn_node_nr(irn), col));
 130                                         lpp_set_factor_fast(lpp, cst_idx, var_idx, 1);
 131                                 }
 132                         }
 133                 }
 134         }
 135 }
 136
 137 static void build_affinity_cstr(ilp_env_t *ienv) {
 138         unit_t *curr;
 139         int n_colors = arch_register_class_n_regs(ienv->co->cls);
 140
 141         /* for all optimization units */
 142         list_for_each_entry(unit_t, curr, &ienv->co->units, units) {
 143                 ir_node *root, *arg;
 144                 int root_nr, arg_nr, i, col, y_idx, root_idx, arg_idx;
 145                 char buf[16];
 146                 int root_col, arg_col;
 147
 148                 root = curr->nodes[0];
 149                 root_nr = (int) get_irn_node_nr(root);
 150                 root_col = get_irn_col(ienv->co, root);
 151
 152                 for (i = 1; i < curr->node_count; ++i) {
 153                         arg = curr->nodes[i];
 154                         arg_nr = (int) get_irn_node_nr(arg);
 155                         arg_col = get_irn_col(ienv->co, arg);
 156
 157                         /* add a new affinity variable */
 158                         y_idx = lpp_add_var(ienv->lp, name_cdd_sorted(buf, 'y', root_nr, arg_nr), lpp_binary, curr->costs[i]);
 159                         lpp_set_start_value(ienv->lp, y_idx, (root_col==arg_col) ? 0.0 : 1.0);
 160
 161                         /* add constraints relating the affinity var to the color vars */
 162                         for (col=0; col<n_colors; ++col) {
 163                                 int cst_idx = lpp_add_cst(ienv->lp, NULL, lpp_less, 0.0);
 164                                 root_idx = lpp_get_var_idx(ienv->lp, name_cdd(buf, 'x', root_nr, col));
 165                                 arg_idx  = lpp_get_var_idx(ienv->lp, name_cdd(buf, 'x', arg_nr,  col));
 166
 167                                 lpp_set_factor_fast(ienv->lp, cst_idx, root_idx,  1.0);
 168                                 lpp_set_factor_fast(ienv->lp, cst_idx, arg_idx,  -1.0);
 169                                 lpp_set_factor_fast(ienv->lp, cst_idx, root_idx, -1.0);
 170                         }
 171                 }
 172         }
 173 }
 174
 175 /**
 176  *
 177  */
 178 static void build_clique_star_cstr(ilp_env_t *ienv) {
 179
 180 }
 181
 182 /**
 183  *
 184  */
 185 static void build_path_cstr(ilp_env_t *ienv) {
 186
 187 }
 188
 189 static void ilp2_build(ilp_env_t *ienv) {
 190         local_env_t *lenv = ienv->env;
 191         int lower_bound;
 192
 193         ienv->lp = new_lpp(ienv->co->name, lpp_minimize);
 194         build_coloring_cstr(ienv);
 195         build_interference_cstr(ienv);
 196         build_affinity_cstr(ienv);
 197         build_clique_star_cstr(ienv);
 198         build_path_cstr(ienv);
 199
 200         lower_bound = co_get_lower_bound(ienv->co) - co_get_inevit_copy_costs(ienv->co);
 201         lpp_set_bound(ienv->lp, lower_bound);
 202         lpp_set_time_limit(ienv->lp, lenv->time_limit);
 203 }
 204
 205 static void ilp2_apply(ilp_env_t *ienv) {
 206         local_env_t *lenv = ienv->env;
 207         double *sol;
 208         lpp_sol_state_t state;
 209         int i, count;
 210
 211         count = lenv->last_x_var - lenv->first_x_var + 1;
 212         sol = xmalloc(count * sizeof(sol[0]));
 213         state = lpp_get_solution(ienv->lp, sol, lenv->first_x_var, lenv->last_x_var);
 214         if (state != lpp_optimal) {
 215                 printf("WARNING %s: Solution state is not 'optimal': %d\n", ienv->co->name, state);
 216                 assert(state >= lpp_feasible && "The solution should at least be feasible!");
 217         }
 218
 219         for (i=0; i<count; ++i) {
 220                 int nodenr, color;
 221                 char var_name[16];
 222
 223                 if (sol[i] > 1-EPSILON) { /* split variable name into components */
 224                         lpp_get_var_name(ienv->lp, lenv->first_x_var+i, var_name, sizeof(var_name));
 225
 226                         if (sscanf(var_name, "x_%d_%d", &nodenr, &color) == 2) {
 227                                 ir_node *irn = pmap_get(lenv->nr_2_irn, INT_TO_PTR(nodenr));
 228                                 assert(irn && "This node number must be present in the map");
 229
 230                                 set_irn_col(ienv->co, irn, color);
 231                         } else
 232                                 assert(0 && "This should be a x-var");
 233                 }
 234         }
 235
 236 #ifdef COPYOPT_STAT
 237         /* TODO adapt to multiple possible ILPs */
 238         copystat_add_ilp_time((int)(1000.0*lpp_get_sol_time(pi->curr_lp)));  //now we have ms
 239         copystat_add_ilp_vars(lpp_get_var_count(pi->curr_lp));
 240         copystat_add_ilp_csts(lpp_get_cst_count(pi->curr_lp));
 241         copystat_add_ilp_iter(lpp_get_iter_cnt(pi->curr_lp));
 242 #endif
 243 }
 244
 245 int co_solve_ilp2(copy_opt_t *co, double time_limit) {
 246         lpp_sol_state_t sol_state;
 247         ilp_env_t *ienv;
 248         local_env_t my;
 249
 250         my.time_limit  = time_limit;
 251         my.first_x_var = -1;
 252         my.last_x_var  = -1;
 253         my.nr_2_irn    = pmap_create();
 254         my.dbg         = firm_dbg_register("ir.be.coilp2");
 255         firm_dbg_set_mask(my.dbg, DEBUG_LVL);
 256
 257         ienv = new_ilp_env(co, ilp2_build, ilp2_apply, &my);
 258
 259         sol_state = ilp_go(ienv);
 260
 261         pmap_destroy(my.nr_2_irn);
 262         free_ilp_env(ienv);
 263
 264         return sol_state == lpp_optimal;
 265 }
 266
 267 #else /* WITH_ILP */
 268
 269 static void only_that_you_can_compile_without_WITH_ILP_defined(void) {
 270 }
 271
 272 #endif /* WITH_ILP */