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

   1 /**
   2  * Author:      Daniel Grund
   3  * Date:                17.05.2005
   4  * Copyright:   (c) Universitaet Karlsruhe
   5  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
   6  */
   7 #ifdef HAVE_CONFIG_H
   8 #include "config.h"
   9 #endif
  10
  11 #ifdef HAVE_ALLOCA_H
  12 #include <alloca.h>
  13 #endif
  14 #ifdef HAVE_MALLOC_H
  15 #include <malloc.h>
  16 #endif
  17
  18 #include "lpp.h"
  19 #include "xmalloc.h"
  20 #include "becopyopt.h"
  21 #include "becopystat.h"
  22
  23 #define DEBUG_LVL SET_LEVEL_1
  24 static firm_dbg_module_t *dbg = NULL;
  25
  26 #define SLOTS_LIVING 32
  27
  28 /**
  29  * Represents the _costs_ if node n and m have different colors.
  30  * Must be >=0.
  31  **/
  32 #define get_weight(n,m) 1
  33
  34 typedef struct _simpl_t {
  35         struct list_head chain;
  36         if_node_t *ifn;
  37 } simpl_t;
  38
  39 typedef struct _problem_instance_t {
  40         const copy_opt_t *co;                   /** the original copy_opt problem */
  41         /* problem size reduction removing simple nodes */
  42         struct list_head simplicials;   /**< holds all simpl_t's in right order to color*/
  43         pset *removed;                                  /**< holds all removed simplicial irns */
  44         /* lp problem */
  45         lpp_t *dilp;                                    /**< problem formulation directly as milp */
  46         /* overhead stuff */
  47         lpp_t *curr_lp;                                 /**< points to the problem currently used */
  48         int curr_color, cst_counter, last_x_var;
  49         char buf[32];
  50 } problem_instance_t;
  51
  52 #define is_removed(irn) pset_find_ptr(pi->removed, irn)
  53 /*
  54  * Some stuff for variable name handling.
  55  */
  56 #define mangle_cst(buf, prefix, nr) \
  57                         snprintf((buf), sizeof(buf), "%c%d", (prefix), (nr))
  58
  59 #define mangle_var(buf, prefix, node_nr, color) \
  60                         snprintf((buf), sizeof(buf), "%c%d_%d", (prefix), (node_nr), (color))
  61
  62 #define mangle_var_irn(buf, prefix, irn, color) \
  63                         mangle_var((buf), (prefix), get_irn_graph_nr(irn), (color))
  64
  65 #define split_var(var, nnr, col) \
  66                         sscanf(var, "x%d_%d", (nnr), (col))
  67
  68
  69 /**
  70  * Checks if a node is simplicial in the graph
  71  * heeding the already removed nodes.
  72  */
  73 static INLINE int pi_is_simplicial(problem_instance_t *pi, const if_node_t *ifn) {
  74         int i, o, size = 0;
  75         if_node_t **all, *curr;
  76         all = alloca(ifn_get_degree(ifn) * sizeof(*all));
  77
  78         /* get all non-removed neighbors */
  79         foreach_neighb(ifn, curr)
  80                 if (!is_removed(curr))
  81                         all[size++] = curr;
  82
  83         /* check if these form a clique */
  84         for (i=0; i<size; ++i)
  85                 for (o=i+1; o<size; ++o)
  86                         if (!ifg_has_edge(pi->co->chordal_env, all[i], all[o]))
  87                                 return 0;
  88
  89         /* all edges exist so this is a clique */
  90         return 1;
  91 }
  92
  93 /**
  94  * Iterative finds and 'removes' from the graph all nodes which are
  95  * simplicial AND not member of a equal-color-wish
  96  */
  97 static void pi_find_simplicials(problem_instance_t *pi) {
  98         set *if_nodes;
  99         if_node_t *ifn;
 100         int redo = 1;
 101
 102         if_nodes = be_ra_get_ifg_nodes(pi->co->chordal_env);
 103         while (redo) {
 104                 redo = 0;
 105                 for (ifn = set_first(if_nodes); ifn; ifn = set_next(if_nodes)) {
 106                         ir_node *irn = get_irn_for_graph_nr(pi->co->irg, ifn->nnr);
 107                         if (!is_removed(irn) && !is_optimizable(irn) &&
 108           !is_optimizable_arg(pi->co, irn) && pi_is_simplicial(pi, ifn)) {
 109                                 simpl_t *s = xmalloc(sizeof(*s));
 110                                 s->ifn = ifn;
 111                                 list_add(&s->chain, &pi->simplicials);
 112                                 pset_insert_ptr(pi->removed, irn);
 113                                 redo = 1;
 114                                 DBG((dbg, LEVEL_2, " Removed %n\n", irn));
 115                         }
 116                 }
 117         }
 118 }
 119
 120 /**
 121  * Add coloring-force conditions
 122  */
 123 static void pi_add_constr_A(ir_node *block, void *env) {
 124         problem_instance_t *pi = env;
 125         struct list_head *head = get_block_border_head(pi->co->chordal_env, block);
 126         border_t *curr;
 127         bitset_t *pos_regs = bitset_alloca(pi->co->cls->n_regs);
 128
 129         list_for_each_entry_reverse(border_t, curr, head, list)
 130                 if (curr->is_def && curr->is_real && !is_removed(curr->irn)) {
 131                         int cst_idx, nnr, col;
 132
 133                         nnr = get_irn_graph_nr(curr->irn);
 134                         mangle_cst(pi->buf, 'A', nnr);
 135                         cst_idx = lpp_add_cst(pi->curr_lp, pi->buf, equal, 1);
 136
 137                         // iterate over all possible colors in order
 138                         bitset_clear_all(pos_regs);
 139                         arch_get_allocatable_regs(pi->co->env, curr->irn, arch_pos_make_out(0), pi->co->cls, pos_regs);
 140                         bitset_foreach(pos_regs, col) {
 141                                 int var_idx;
 142                                 mangle_var(pi->buf, 'x', nnr, col);
 143                                 var_idx = lpp_add_var(pi->curr_lp, pi->buf, binary, 0);
 144                                 pi->last_x_var = var_idx;
 145                                 lpp_set_factor_fast(pi->curr_lp, cst_idx, var_idx, 1);
 146                         }
 147                 }
 148 }
 149
 150 /**
 151  * Checks if all nodes in @p living are live in in block @p block.
 152  * @return 1 if all are live in
 153  *         0 else
 154  */
 155 static INLINE int all_live_in(ir_node *block, pset *living) {
 156         ir_node *n;
 157         for (n = pset_first(living); n; n = pset_next(living))
 158                 if (!is_live_in(block, n)) {
 159                         pset_break(living);
 160                         return 0;
 161                 }
 162         return 1;
 163 }
 164
 165 /**
 166  * Finds cliques in the interference graph, considering only nodes
 167  * for which the color pi->curr_color is possible. Finds only 'maximal-cliques',
 168  * viz cliques which are not contained in another one.
 169  * This is used for the matrix B.
 170  * TODO check color
 171  */
 172 static void pi_add_constr_B(ir_node *block, void *env) {
 173         problem_instance_t *pi = env;
 174         enum phase_t {growing, shrinking} phase = growing;
 175         struct list_head *head = get_block_border_head(pi->co->chordal_env, block);
 176         border_t *b;
 177         pset *living = pset_new_ptr(SLOTS_LIVING);
 178
 179         list_for_each_entry_reverse(border_t, b, head, list) {
 180                 const ir_node *irn = b->irn;
 181                 if (is_removed(irn))
 182                         continue;
 183
 184                 if (b->is_def) {
 185                         DBG((dbg, LEVEL_2, "Def %n\n", irn));
 186                         pset_insert_ptr(living, irn);
 187                         phase = growing;
 188                 } else { /* is_use */
 189                         DBG((dbg, LEVEL_2, "Use %n\n", irn));
 190
 191                         /* before shrinking the set, store the current 'maximum' clique;
 192                          * do NOT if clique is a single node
 193                          * do NOT if all values are live_in (in this case they were contained in a live-out clique elsewhere) */
 194                         if (phase == growing && pset_count(living) >= 2 && !all_live_in(block, living)) {
 195                                 int cst_idx;
 196                                 ir_node *n;
 197                                 mangle_cst(pi->buf, 'B', pi->cst_counter);
 198                                 cst_idx = lpp_add_cst(pi->curr_lp, pi->buf, less, 1);
 199                                 for (n = pset_first(living); n; n = pset_next(living)) {
 200                                         int var_idx;
 201                                         mangle_var_irn(pi->buf, 'x', n, pi->curr_color);
 202                                         var_idx = lpp_get_var_idx(pi->curr_lp, pi->buf);
 203                                         assert(var_idx>=1);
 204                                         lpp_set_factor_fast(pi->curr_lp, cst_idx, var_idx, 1);
 205                                 }
 206                                 pi->cst_counter++;
 207                         }
 208                         pset_remove_ptr(living, irn);
 209                         phase = shrinking;
 210                 }
 211         }
 212
 213         del_pset(living);
 214 }
 215
 216 static void pi_add_constr_E(problem_instance_t *pi) {
 217         unit_t *curr;
 218         bitset_t *root_regs, *arg_regs;
 219         root_regs = bitset_alloca(pi->co->cls->n_regs);
 220         arg_regs = bitset_alloca(pi->co->cls->n_regs);
 221
 222         /* for all roots of optimization units */
 223         list_for_each_entry(unit_t, curr, &pi->co->units, units) {
 224                 const ir_node *root, *arg;
 225                 int rootnr, argnr, color;
 226                 int y_idx, i, cst_counter = 0;
 227                 char buf[32];
 228
 229                 root = curr->nodes[0];
 230                 rootnr = get_irn_graph_nr(root);
 231                 bitset_clear_all(root_regs);
 232                 arch_get_allocatable_regs(pi->co->env, root, arch_pos_make_out(0), pi->co->cls, root_regs);
 233
 234                 /* for all arguments of root */
 235                 for (i = 1; i < curr->node_count; ++i) {
 236                         arg = curr->nodes[i];
 237                         argnr = get_irn_graph_nr(arg);
 238                         bitset_clear_all(arg_regs);
 239                         arch_get_allocatable_regs(pi->co->env, arg, arch_pos_make_out(0), pi->co->cls, arg_regs);
 240
 241                         /* Introduce new variable and set factor in objective function */
 242                         y_idx = lpp_add_var(pi->curr_lp, NULL, real, get_weight(root, arg));
 243
 244                         /* For all colors root and arg have in common, add 2 constraints to E */
 245                         bitset_and(arg_regs, root_regs);
 246                         bitset_foreach(arg_regs, color) {
 247                                 int root_idx, arg_idx, cst_idx;
 248                                 mangle_var(buf, 'x', rootnr, color);
 249                                 root_idx = lpp_get_var_idx(pi->curr_lp, buf);
 250                                 mangle_var(buf, 'x', argnr, color);
 251                                 arg_idx = lpp_get_var_idx(pi->curr_lp, buf);
 252
 253                                 /* add root-arg+y <= 1 */
 254                                 mangle_cst(buf, 'E', cst_counter++);
 255                                 cst_idx = lpp_add_cst(pi->curr_lp, buf, less, 0);
 256                                 lpp_set_factor_fast(pi->curr_lp, cst_idx, root_idx, 1);
 257                                 lpp_set_factor_fast(pi->curr_lp, cst_idx, arg_idx, -1);
 258                                 lpp_set_factor_fast(pi->curr_lp, cst_idx, y_idx, -1);
 259
 260                                 /* add arg-root+y <= 1 */
 261                                 mangle_cst(buf, 'E', cst_counter++);
 262                                 cst_idx = lpp_add_cst(pi->curr_lp, buf, less, 0);
 263                                 lpp_set_factor_fast(pi->curr_lp, cst_idx, root_idx, -1);
 264                                 lpp_set_factor_fast(pi->curr_lp, cst_idx, arg_idx, 1);
 265                                 lpp_set_factor_fast(pi->curr_lp, cst_idx, y_idx, -1);
 266                         }
 267                 }
 268         }
 269 }
 270
 271 /**
 272  * Generate the initial problem matrices and vectors.
 273  */
 274 static problem_instance_t *new_pi(const copy_opt_t *co) {
 275         problem_instance_t *pi;
 276
 277         DBG((dbg, LEVEL_1, "Generating new instance...\n"));
 278         pi = xcalloc(1, sizeof(*pi));
 279         pi->co = co;
 280         pi->removed = pset_new_ptr_default();
 281         INIT_LIST_HEAD(&pi->simplicials);
 282         pi->dilp = new_lpp(co->name, minimize);
 283
 284         /* problem size reduction */
 285         pi_find_simplicials(pi);
 286         //TODO dump_ifg_w/o_removed
 287
 288         pi->curr_lp = pi->dilp;
 289
 290         /* Matrix A: knapsack constraint for each node */
 291         dom_tree_walk_irg(co->irg, pi_add_constr_A, NULL, pi);
 292         /* Matrix B: interference constraints using cliques */
 293         for (pi->curr_color = 0; pi->curr_color < pi->co->cls->n_regs; ++pi->curr_color)
 294                 dom_tree_walk_irg(co->irg, pi_add_constr_B, NULL, pi);
 295         /* Matrix E weights for the 'same-color-optimization' target */
 296         pi_add_constr_E(pi);
 297         return pi;
 298 }
 299
 300 /**
 301  * Clean the problem instance
 302  */
 303 static void free_pi(problem_instance_t *pi) {
 304         DBG((dbg, LEVEL_1, "Free instance...\n"));
 305         /* pi->simplicials get freed during apply_solution */
 306         free_lpp(pi->dilp);
 307         del_pset(pi->removed);
 308         free(pi);
 309 }
 310
 311 /**
 312  * Set starting values for the mip problem according
 313  * to the current coloring of the graph.
 314  */
 315 static void pi_set_start_sol(problem_instance_t *pi) {
 316         int i;
 317         for (i=1; i<=pi->last_x_var; ++i) {
 318                 int nnr, col;
 319                 double val;
 320                 /* get variable name */
 321                 const char *var_name = lpp_get_var_name(pi->curr_lp, i);
 322                 /* split into components */
 323                 if (split_var(var_name, &nnr, &col) == 2) {
 324                         assert(get_irn_col(pi->co, get_irn_for_graph_nr(pi->co->irg, nnr)) != -1);
 325                         val = (get_irn_col(pi->co, get_irn_for_graph_nr(pi->co->irg, nnr)) == col) ? 1 : 0;
 326                         lpp_set_start_value(pi->curr_lp, i, val);
 327                 } else
 328                         assert(0 && "x vars always look like this 'x123_45'");
 329         }
 330 }
 331
 332 /**
 333  * Invoke a solver
 334  */
 335 static void pi_solve_ilp(problem_instance_t *pi) {
 336         pi_set_start_sol(pi);
 337         lpp_solve(pi->curr_lp, 1);
 338 }
 339
 340 /**
 341  * Set the color of all simplicial nodes removed form
 342  * the graph before transforming it to an ilp.
 343  */
 344 static void pi_set_simplicials(problem_instance_t *pi) {
 345         simpl_t *simpl, *tmp;
 346         bitset_t *used_cols = bitset_alloca(arch_register_class_n_regs(pi->co->cls));
 347
 348         /* color the simplicial nodes in right order */
 349         list_for_each_entry_safe(simpl_t, simpl, tmp, &pi->simplicials, chain) {
 350                 int free_col;
 351                 ir_node *other_irn, *irn;
 352                 if_node_t *other, *ifn;
 353
 354                 /* get free color by inspecting all neighbors */
 355                 ifn = simpl->ifn;
 356                 irn = get_irn_for_graph_nr(pi->co->irg, ifn->nnr);
 357                 bitset_clear_all(used_cols);
 358                 foreach_neighb(ifn, other) {
 359                         other_irn = get_irn_for_graph_nr(pi->co->irg, other->nnr);
 360                         if (!is_removed(other_irn)) /* only inspect nodes which are in graph right now */
 361                                 bitset_set(used_cols, get_irn_col(pi->co, other_irn));
 362                 }
 363
 364                 /* now all bits not set are possible colors */
 365                 free_col = bitset_next_clear(used_cols, 0);
 366                 assert(free_col != -1 && "No free color found. This can not be.");
 367                 set_irn_col(pi->co, irn, free_col);
 368                 pset_remove_ptr(pi->removed, irn); /* irn is back in graph again */
 369                 free(simpl);
 370         }
 371 }
 372
 373 /**
 374  * Sets the colors of irns according to the values of variables
 375  * provided by the solution of the solver.
 376  */
 377 static void pi_apply_solution(problem_instance_t *pi) {
 378 //              else if (vars_section && sscanf(buf, "x%d_%d %d", &num, &col, &val) == 3 && val == 1) {
 379 //                      set_irn_col(lpp, get_irn_for_graph_nr(lpp->irg, num), col);
 380         int i;
 381         double *sol;
 382         DBG((dbg, LEVEL_1, "Applying solution...\n"));
 383
 384 #ifdef DO_STAT
 385         //TODO
 386 #endif
 387
 388         sol = xmalloc(pi->last_x_var * sizeof(*sol));
 389         lpp_get_solution(pi->curr_lp, sol, 1, pi->last_x_var);
 390         for (i=0; i<pi->last_x_var; ++i)
 391                 if (sol[i] == 1) { /* split varibale name into components */
 392                         int nnr, col;
 393                         const char *var_name = lpp_get_var_name(pi->curr_lp, 1+i);
 394                         if (split_var(var_name, &nnr, &col) == 2) {
 395                                 DBG((dbg, LEVEL_2, " x%d = %d\n", nnr, col));
 396                                 set_irn_col(pi->co, get_irn_for_graph_nr(pi->co->irg, nnr), col);
 397                         } else
 398                                 assert(0 && "this should be a x-var");
 399         }
 400         pi_set_simplicials(pi);
 401 }
 402
 403 void co_ilp_opt(copy_opt_t *co) {
 404         problem_instance_t *pi;
 405         dbg = firm_dbg_register("ir.be.copyoptilp");
 406         if (!strcmp(co->name, DEBUG_IRG))
 407                 firm_dbg_set_mask(dbg, -1);
 408         else
 409                 firm_dbg_set_mask(dbg, DEBUG_LVL);
 410
 411         pi = new_pi(co);
 412         pi_solve_ilp(pi);
 413         pi_apply_solution(pi);
 414         free_pi(pi);
 415 }