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  * ILP formalization using G=(V, E, Q):
   8  *  - 1 class of variables: equal color vars
   9  *  - Path constraints
  10  *  - Clique path constraints
  11  *
  12  *
  13  *      \min \sum_{ (i,j) \in Q }  w_ij y_ij
  14  *
  15  *              y_ij                            =  1                    (i,j) \in E
  16  *
  17  *              \sum_c y_nc                     =  |C| - 1              n \in N, c \in C
  18  *
  19  *              y_nc                            =  1                    n \in N, c \not\in C(n)
  20  *
  21  *              \sum_{e \in p} y_e      >= 1                    p \in P         path constraints
  22  *
  23  *              \sum_{e \in cp} y_e     >= |cp| - 1             cp \in CP       clique-path constraints
  24  *
  25  *              y_ij \in N,   w_ij \in R^+
  26  */
  27
  28 #ifdef HAVE_CONFIG_H
  29 #include "config.h"
  30 #endif /* HAVE_CONFIG_H */
  31
  32 #ifdef WITH_ILP
  33
  34 #include "becopyilp_t.h"
  35 #include "beifg_t.h"
  36 #include "irtools.h"
  37
  38 #define DEBUG_LVL 1
  39
  40 typedef struct _local_env_t {
  41         firm_dbg_module_t *dbg;
  42         double time_limit;
  43         int first_x_var, last_x_var;
  44         pmap *nr_2_irn;
  45 } local_env_t;
  46
  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);
  50         bitset_t *colors;
  51         ir_node *irn;
  52         char buf[16];
  53
  54         colors = bitset_alloca(arch_register_class_n_regs(ienv->co->cls));
  55
  56         be_ifg_foreach_node(ifg, iter, irn)
  57                 if (!sr_is_removed(ienv->sr, irn)) {
  58                         int col, cst_idx;
  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;
  63
  64                         pmap_insert(lenv->nr_2_irn, INT_TO_PTR(node_nr), irn);
  65
  66                         arch_get_register_req(ienv->co->aenv, &req, irn, -1);
  67
  68                         /* get assignable colors */
  69                         if (arch_register_req_is(&req, limited))
  70                                 req.limited(req.limited_env, colors);
  71                         else
  72                                 arch_put_non_ignore_regs(ienv->co->aenv, req.cls, colors);
  73
  74                         /* add the coloring constraint */
  75                         cst_idx = lpp_add_cst(ienv->lp, NULL, lpp_equal, 1.0);
  76
  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);
  81
  82                                 lenv->last_x_var = var_idx;
  83                                 if (lenv->first_x_var == -1)
  84                                         lenv->first_x_var = var_idx;
  85                         }
  86
  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);
  93
  94                                 lenv->last_x_var = var_idx;
  95                         }
  96                 }
  97 }
  98
  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);
 103         int i, col;
 104
 105         void *iter = be_ifg_cliques_iter_alloca(ifg);
 106         ir_node **clique = alloca(sizeof(*clique) * n_colors);
 107         int size;
 108
 109         char buf[16];
 110
 111         /* for each maximal clique */
 112         be_ifg_foreach_clique(ifg, iter, clique, &size) {
 113
 114                 if (size < 2)
 115                         continue;
 116
 117                 /* for all colors */
 118                 for (col=0; col<n_colors; ++col) {
 119                         int cst_idx = lpp_add_cst(lpp, NULL, lpp_less, 1.0);
 120
 121                         /* for each member of this clique */
 122                         for (i=0; i<size; ++i) {
 123                                 ir_node *irn = clique[i];
 124
 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);
 128                                 }
 129                         }
 130                 }
 131         }
 132 }
 133
 134 static void build_affinity_cstr(ilp_env_t *ienv) {
 135         unit_t *curr;
 136         int n_colors = arch_register_class_n_regs(ienv->co->cls);
 137
 138         /* for all optimization units */
 139         list_for_each_entry(unit_t, curr, &ienv->co->units, units) {
 140                 ir_node *root, *arg;
 141                 int root_nr, arg_nr, i, col, y_idx, root_idx, arg_idx;
 142                 char buf[16];
 143                 int root_col, arg_col;
 144
 145                 root = curr->nodes[0];
 146                 root_nr = (int) get_irn_node_nr(root);
 147                 root_col = get_irn_col(ienv->co, root);
 148
 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);
 153
 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);
 157
 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));
 163
 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);
 167                         }
 168                 }
 169         }
 170 }
 171
 172 static void build_path_cstr(ilp_env_t *ienv) {
 173
 174 }
 175
 176 static void build_clique_path_cstr(ilp_env_t *ienv) {
 177
 178 }
 179
 180 static void ilp2_build(ilp_env_t *ienv) {
 181         local_env_t *lenv = ienv->env;
 182         int lower_bound;
 183
 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);
 190
 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);
 194 }
 195
 196 static void ilp2_apply(ilp_env_t *ienv) {
 197         local_env_t *lenv = ienv->env;
 198         double *sol;
 199         lpp_sol_state_t state;
 200         int i, count;
 201
 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!");
 208         }
 209
 210         for (i=0; i<count; ++i) {
 211                 int nodenr, color;
 212                 char var_name[16];
 213
 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));
 216
 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");
 220
 221                                 set_irn_col(ienv->co, irn, color);
 222                         } else
 223                                 assert(0 && "This should be a x-var");
 224                 }
 225         }
 226
 227 #ifdef COPYOPT_STAT
 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));
 233 #endif
 234 }
 235
 236 int co_solve_ilp2(copy_opt_t *co, double time_limit) {
 237         lpp_sol_state_t sol_state;
 238         ilp_env_t *ienv;
 239         local_env_t my;
 240
 241         my.time_limit  = time_limit;
 242         my.first_x_var = -1;
 243         my.last_x_var  = -1;
 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);
 247
 248         ienv = new_ilp_env(co, ilp2_build, ilp2_apply, &my);
 249
 250         sol_state = ilp_go(ienv);
 251
 252         pmap_destroy(my.nr_2_irn);
 253         free_ilp_env(ienv);
 254
 255         return sol_state == lpp_optimal;
 256 }
 257
 258 #else /* WITH_ILP */
 259
 260 static void only_that_you_can_compile_without_WITH_ILP_defined(void) {
 261 }
 262
 263 #endif /* WITH_ILP */