nsz Git - libfirm/blob - ir/be/becopyilp1.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  * CVS-ID:      $Id$
   7  *
   8  * ILP formalization using:
   9  *  - 2 classes of vars: Nodes- and optimality variables.
  10  *  - Clique constraints
  11  *  - Path constraints
  12  *  - Clique path constraints
  13  */
  14
  15 #ifdef HAVE_CONFIG_H
  16 #include "config.h"
  17 #endif /* HAVE_CONFIG_H */
  18
  19 #ifdef WITH_ILP
  20
  21 #include "becopyilp_t.h"
  22 #include "benumb_t.h"
  23 #include "belive_t.h"
  24 #include "irdom_t.h"
  25 #include "irgwalk.h"
  26 #include "xmalloc.h"
  27 #include "pset.h"
  28 #include "irprog.h"
  29 #include "irdom_t.h"
  30 #include "iredges_t.h"
  31
  32 #include "becopystat.h"
  33 #include "besched_t.h"
  34 #include "phiclass.h"
  35
  36 #if 0 //temporary
  37
  38 #define PATH_CONSTRAINTS_FOR_CLASSES
  39
  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 */
  44
  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;
  48         char buf[32];
  49         pset *done;
  50 } problem_instance_t;
  51
  52 #define is_color_possible(irn,color) arch_reg_is_allocatable(pi->co->aenv, irn, -1, arch_register_for_index(pi->co->cls, color))
  53
  54 /*
  55  * Some stuff for variable name handling.
  56  */
  57 #define mangle_cst(buf, prefix, nr) \
  58                         snprintf((buf), sizeof(buf), "%c%d", (prefix), (nr))
  59
  60 #define mangle_var1(buf, prefix, color) \
  61                         snprintf((buf), sizeof(buf), "%c%d", (prefix), (color))
  62
  63 #define mangle_var2(buf, prefix, node_nr, color) \
  64                         snprintf((buf), sizeof(buf), "%c%d_%d", (prefix), (node_nr), (color))
  65
  66 #define mangle_var3(buf, prefix, n1, n2, col) \
  67                         snprintf((buf), sizeof(buf), "%c%d_%d_%d", (prefix), (n1), (n2), (col))
  68
  69 #define mangle_var_irn(buf, prefix, irn, color) \
  70                         mangle_var2((buf), (prefix), get_irn_graph_nr(irn), (color))
  71
  72 #define split_var(var, nnr, col) \
  73                         sscanf(var, "x%d_%d", (nnr), (col))
  74
  75
  76 #ifndef PATH_CONSTRAINTS_FOR_CLASSES
  77 /**
  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.
  82  */
  83 static void pi_add_path_cstr(problem_instance_t *pi) {
  84         unit_t *curr;
  85         int cst_counter = 0;
  86         DBG((dbg, LEVEL_2, "Adding path constraints...\n"));
  87
  88         /* for all optimization units (only phis) */
  89         list_for_each_entry(unit_t, curr, &pi->co->units, units) {
  90                 int i, o, rootnr;
  91
  92                 if (curr->min_nodes_costs == 0)
  93                         continue;
  94
  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)) {
 104                                         int cst_idx, y_idx;
 105                                         char buf[32];
 106
 107                                         mangle_cst(buf, 'P', cst_counter++);
 108                                         cst_idx = lpp_add_cst(pi->curr_lp, buf, lpp_greater, 1);
 109
 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);
 113
 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);
 117                                 }
 118                         }
 119                 }
 120         }
 121 }
 122 #endif
 123
 124 #ifdef PATH_CONSTRAINTS_FOR_CLASSES
 125 static INLINE int get_y_var_idx(problem_instance_t *pi, int nnr1, int nnr2) {
 126         int res;
 127         char buf[30];
 128
 129         mangle_var2(buf, 'y', nnr1, nnr2);
 130         if ((res = lpp_get_var_idx(pi->curr_lp, buf)) != -1)
 131                 return res;
 132
 133         mangle_var2(buf, 'y', nnr2, nnr1);
 134         if ((res = lpp_get_var_idx(pi->curr_lp, buf)) != -1)
 135                 return res;
 136
 137         assert(0 && "One of them must work");
 138   return -1;
 139 }
 140
 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;
 144                 char buf[30];
 145
 146                 /* add cut to ilp */
 147                 mangle_cst(buf, 'Q', pi->cst_counter++);
 148                 cst_idx = lpp_add_cst(pi->curr_lp, buf, lpp_greater, 1);
 149
 150                 /* add all vars along the path */
 151                 nnr2 = get_irn_graph_nr(path[0]);
 152                 for (i=1; i<length; ++i) {
 153                         nnr1 = nnr2;
 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);
 157                 }
 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();
 165
 166                 /* find all potential next nodes on path */
 167                 /*  args of phis */
 168                 if (is_Phi(end))
 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);
 174                                 }
 175                         }
 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);
 182                         }
 183                 }
 184                 del_pset(done);
 185
 186
 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];
 190
 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;
 194
 195                         for(; o<length; ++o)
 196                                 if (nodes_interfere(cenv, nn, path[o])) {
 197                                         next[i] = NULL;
 198                                         break;
 199                                 }
 200                 }
 201                 /* now we have all possible nodes in next; impossibles are NULL */
 202
 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 */
 206                                 continue;
 207
 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]);
 212                 }
 213         }
 214 }
 215
 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;
 219         int i, o, max;
 220         ir_node *m, **cls;
 221         pset *class = get_phi_class(irn);
 222         if (!class || pset_find_ptr(pi->done, class))
 223                 return;
 224
 225         pset_insert_ptr(pi->done, class);
 226
 227         /* pset to array */
 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));
 232                 cls[i] = m;
 233         }
 234
 235         cenv = pi->co->cenv;
 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);
 240
 241                 /* add cls[i] to path and remove it from remainder */
 242                 path[0] = cls[i];
 243                 pset_remove_ptr(remain, cls[i]);
 244
 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]);
 248
 249                 /* insert back into remainder */
 250                 pset_insert_ptr(remain, cls[i]);
 251         }
 252 }
 253
 254
 255 /**
 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.
 260  */
 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"));
 263         pi->cst_counter = 0;
 264         pi->done = pset_new_ptr_default();
 265         irg_walk_graph(pi->co->irg, path_cstr_for_classes_walker, NULL, pi);
 266         del_pset(pi->done);
 267 }
 268 #endif
 269
 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);
 274 }
 275 #endif
 276
 277 #include "becopyilp_t.h"
 278
 279 #define DEBUG_LVL 1
 280
 281 typedef struct _my_env_t {
 282         int foo;
 283 } my_env_t;
 284
 285
 286 static void ilp1_build(ilp_env_t *ienv) {
 287         ienv->lp = new_lpp(ienv->co->name, lpp_minimize);
 288
 289 }
 290
 291 static void ilp1_apply(ilp_env_t *ienv) {
 292
 293 }
 294
 295 int co_solve_ilp1(copy_opt_t *co, double time_limit) {
 296         return 1;
 297 }
 298
 299
 300 #else /* WITH_ILP */
 301
 302 static void only_that_you_can_compile_without_WITH_ILP_defined(void) {
 303 }
 304
 305 #endif /* WITH_ILP */