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

   1 /**
   2  * @file   bespillilp.c
   3  * @date   15.07.2005
   4  * @author Sebastian Hack
   5  *
   6  * ILP based spilling
   7  *
   8  * Copyright (C) 2005 Universitaet Karlsruhe
   9  * Released under the GPL
  10  */
  11 #include <math.h>
  12
  13 #include "hashptr.h"
  14 #include "debug.h"
  15 #include "obst.h"
  16 #include "set.h"
  17 #include "list.h"
  18 #include "pmap.h"
  19
  20 #include "irprintf.h"
  21 #include "irgwalk.h"
  22 #include "irnode_t.h"
  23 #include "ircons_t.h"
  24 #include "irloop_t.h"
  25
  26 #include <lpp/lpp.h>
  27 #include <lpp/lpp_net.h>
  28 #include <lpp/lpp_cplex.h>
  29
  30 #include "be_t.h"
  31 #include "belive_t.h"
  32 #include "besched_t.h"
  33 #include "beirgmod.h"
  34 #include "bearch.h"
  35 #include "benode_t.h"
  36 #include "beutil.h"
  37 #include "bespillilp.h"
  38
  39 #define BIGM 100000.0
  40
  41 #define MAX(a,b) ((a) > (b) ? (a) : (b))
  42
  43 #define DBG_LEVEL SET_LEVEL_0 // 3
  44
  45 #define DUMP_SOLUTION
  46 #define DUMP_ILP
  47 #define DUMP_STATS
  48
  49 #undef  SOLVE_LOCAL
  50 #define LPP_SERVER "i44pc52"
  51 #define LPP_SOLVER "cplex"
  52
  53 #define COST_LOAD      10
  54 #define COST_STORE     50
  55 #define COST_REMAT     (-9)
  56
  57 #define is_end_of_block_use(lr) (is_Block((lr)->user))
  58
  59 /**
  60  * Reloads on edges.
  61  */
  62 typedef struct _edge_reload_t {
  63         ir_node *irn;
  64         ir_node *bl;
  65         int pos;
  66         int in_mem_var;
  67         struct _edge_reload_t *next;
  68 } edge_reload_t;
  69
  70 typedef struct _spill_stat_t {
  71         int n_spills;
  72         int n_reloads;
  73         int n_remat;
  74 } spill_stat_t;
  75
  76 typedef struct _spill_ilp_t {
  77         spill_stat_t stats;
  78         const arch_register_class_t *cls;
  79         const be_main_session_env_t *session;
  80         firm_dbg_module_t *dbg;
  81         lpp_t *lpp;
  82         set *irn_use_heads;
  83         set *live_ranges;
  84         set *first_uses;
  85         spill_env_t *senv;
  86         edge_reload_t *edges;
  87         struct obstack *obst;
  88         int enable_store : 1;
  89         int enable_remat : 1;
  90 } spill_ilp_t;
  91
  92 typedef struct _live_range_t live_range_t;
  93
  94 typedef struct _irn_use_head_t {
  95         struct list_head head;
  96         ir_node *irn;
  97         int spill_var;
  98         int n_uses;
  99         live_range_t *closest_use;
 100 } irn_use_head_t;
 101
 102 struct _live_range_t {
 103         struct list_head list;
 104         irn_use_head_t *use_head;
 105         ir_node *user;
 106         ir_node *irn;
 107         int pos;
 108         int in_mem_var;
 109         int is_remat_var;
 110 };
 111
 112 /*
 113  * Associates the first use of a live-in in a block
 114  * with its live range.
 115  */
 116 typedef struct _first_use_t {
 117         ir_node *bl;
 118         ir_node *irn;       /**< A value live in at bl. */
 119         live_range_t *lr;   /**< The live range for the first use of irn in bl. */
 120 } first_use_t;
 121
 122
 123 /**
 124  * Get weight for spill/reload costs
 125  * Actually computed with loop depth.
 126  * @param irn The location where to check for the weights.
 127  * @return The weights at this points.
 128  */
 129 static double get_weight(const ir_node *irn)
 130 {
 131         ir_loop *loop = get_irn_loop((ir_node *) irn);
 132         int res = 1.0;
 133
 134         if(loop) {
 135                 int depth = get_loop_depth(loop);
 136                 res += depth * depth;
 137
 138                 // ir_printf("%+F has loop depth %d\n", irn, depth);
 139         }
 140
 141         return res;
 142 }
 143
 144
 145 static INLINE int has_reg_class(const spill_ilp_t *si, const ir_node *irn)
 146 {
 147   return arch_irn_has_reg_class(si->session->main_env->arch_env,
 148       irn, arch_pos_make_out(0), si->cls);
 149 }
 150
 151 static int cmp_live_range(const void *a, const void *b, size_t n)
 152 {
 153   const live_range_t *p = a;
 154   const live_range_t *q = b;
 155
 156   return !(p->user == q->user && p->irn == q->irn && p->pos == q->pos);
 157 }
 158
 159 static int cmp_irn_use_head(const void *a, const void *b, size_t n)
 160 {
 161   const irn_use_head_t *p = a;
 162   const irn_use_head_t *q = b;
 163
 164         return !(p->irn == q->irn);
 165 }
 166
 167 static irn_use_head_t *get_use_head(spill_ilp_t *si, const ir_node *irn)
 168 {
 169         irn_use_head_t templ;
 170         templ.irn = (ir_node *) irn;
 171         return set_find(si->irn_use_heads, &templ, sizeof(templ), HASH_PTR(irn));
 172 }
 173
 174 static int cmp_first_use(const void *a, const void *b, size_t n)
 175 {
 176   const first_use_t *p = a;
 177   const first_use_t *q = b;
 178
 179   return !(p->irn == q->irn && p->bl == q->bl);
 180 }
 181
 182 static void add_first_use(spill_ilp_t *si, ir_node *bl, ir_node *irn, live_range_t *lr)
 183 {
 184         first_use_t templ;
 185         templ.bl    = bl;
 186         templ.irn   = irn;
 187         templ.lr    = lr;
 188
 189         set_insert(si->first_uses, &templ, sizeof(templ),
 190                         HASH_COMBINE(HASH_PTR(bl), HASH_PTR(irn)));
 191 }
 192
 193 static live_range_t *get_first_use_lr(spill_ilp_t *si, ir_node *bl, ir_node *irn)
 194 {
 195         first_use_t *res;
 196         first_use_t templ;
 197         templ.bl    = bl;
 198         templ.irn   = irn;
 199
 200         res = set_find(si->first_uses, &templ, sizeof(templ),
 201                         HASH_COMBINE(HASH_PTR(bl), HASH_PTR(irn)));
 202
 203         return res ? res->lr : NULL;
 204 }
 205
 206 /**
 207  * Checks, if a vertain node can be recomputed at a certain position.
 208  * @param si    The spill ILP environment.
 209  * @param irn   The node to recompute.
 210  * @param live  The nodes live at the place where @p irn shall be
 211  *              recomputed.
 212  * @return      1, if irn can be recomputed, 0 if not.
 213  */
 214 static INLINE int can_remat(const spill_ilp_t *si, const ir_node *irn, pset *live)
 215 {
 216         int i, n;
 217   const arch_env_t *arch_env    = si->session->main_env->arch_env;
 218         int remat = (arch_irn_get_flags(arch_env, irn) & arch_irn_flags_rematerializable) != 0;
 219
 220         for(i = 0, n = get_irn_arity(irn); i < n && remat; ++i) {
 221                 ir_node *op = get_irn_n(irn, i);
 222                 remat &= !has_reg_class(si, op) || pset_find_ptr(live, op);
 223         }
 224
 225         return remat;
 226 }
 227
 228 static live_range_t *get_live_range(spill_ilp_t *si, ir_node *irn, ir_node *user, int pos)
 229 {
 230         live_range_t lr, *res;
 231         irn_use_head_t iuh, *head;
 232         int is_new;
 233         unsigned hash = HASH_COMBINE(HASH_PTR(irn), HASH_PTR(user));
 234
 235         lr.user         = user;
 236         lr.irn          = irn;
 237         lr.pos          = pos;
 238         lr.in_mem_var   = -1;
 239         lr.is_remat_var = -1;
 240
 241         res = set_insert(si->live_ranges, &lr, sizeof(lr), hash);
 242         is_new = res->in_mem_var == -1;
 243
 244         if(is_new) {
 245                 char buf[128];
 246                 double cost = 0.0;
 247
 248                 if(pos >= 0)
 249                         cost = get_weight(user) * COST_LOAD;
 250
 251                 ir_snprintf(buf, sizeof(buf), "m_%s%N_%N_%d",
 252                                         is_Phi(irn) ? "phi_" : "", irn, user, MAX(pos, 0));
 253                 res->in_mem_var = lpp_add_var(si->lpp, buf, lpp_binary, cost);
 254         }
 255
 256         memset(&iuh, 0, sizeof(iuh));
 257         iuh.irn = irn;
 258         iuh.n_uses = -1;
 259         head = set_insert(si->irn_use_heads, &iuh, sizeof(iuh), HASH_PTR(irn));
 260         if(head->n_uses == -1) {
 261                 head->n_uses = 0;
 262                 INIT_LIST_HEAD(&head->head);
 263         }
 264
 265         if(is_new) {
 266                 list_add_tail(&res->list, &head->head);
 267                 head->n_uses++;
 268         }
 269
 270         res->use_head = head;
 271
 272         return res;
 273 }
 274
 275 static void print_live_set(spill_ilp_t *si, pset *s) {
 276         ir_node *n;
 277         for(n=pset_first(s); n; n=pset_next(s))
 278                 DBG((si->dbg, LEVEL_3, "    %+F\n", n));
 279 }
 280
 281 static void process_block(ir_node *bl, void *data)
 282 {
 283         char buf[128];
 284         int i, n, skipped=0;
 285         spill_ilp_t *si  = data;
 286         int step         = 0;
 287         int n_regs       = arch_register_class_n_regs(si->cls);
 288         int n_preds      = get_irn_arity(bl);
 289         pset *live       = pset_new_ptr_default();
 290         irn_live_t *li;
 291         ir_node *irn;
 292
 293         DBG((si->dbg, LEVEL_3, "\n"));
 294         DBG((si->dbg, LEVEL_3, "Processing %+F\n", bl));
 295
 296         /*
 297          * Get all live-end values of this block
 298          */
 299         live_foreach(bl, li) {
 300                 if(live_is_end(li) && has_reg_class(si, li->irn)) {
 301                         ir_node *irn = (ir_node *) li->irn;
 302                         pset_insert_ptr(live, irn);
 303
 304                         /*The "user" of the live range to the end of a block
 305                          * is the block itself. This is quite arbitrary. */
 306                         set_irn_link(irn, get_live_range(si, irn, bl, -1));
 307                 }
 308         }
 309         DBG((si->dbg, LEVEL_3, "Live-End:\n"));
 310         print_live_set(si, live);
 311
 312         /*
 313          * Walk through the schedule of this block from end to begin.
 314          * Phis are handled togther with live ins after this loop.
 315          */
 316         for(irn = sched_last(bl); !sched_is_begin(irn) && !is_Phi(irn); irn = sched_prev(irn)) {
 317                 ir_node *l;
 318                 int cst;
 319                 int relevant_args, results;
 320                 int demand;
 321                 int n_cand;
 322                 int must_be_in_mem;
 323                 pset *cand;
 324
 325                 /*
 326                  * Determine the number of results
 327                  */
 328                 /* Special handling of Projs */
 329                 if(is_Proj(irn)) {
 330                         if(has_reg_class(si, irn)) {
 331                                 assert(pset_find_ptr(live, irn) && "node must be live");
 332                                 pset_remove_ptr(live, irn);
 333                                 skipped++;
 334                         }
 335
 336                         DBG((si->dbg, LEVEL_2, "Skipped %+F\n", irn));
 337                         continue;
 338                 }
 339
 340                 DBG((si->dbg, LEVEL_1, "Irn %+F\n", irn));
 341                 if(skipped > 0) {
 342                         /* ModeT node */
 343                         assert(get_irn_mode(irn) == mode_T && "node before projs must be tuple");
 344                         results = skipped;
 345                         skipped = 0;
 346                 } else {
 347                         /* Normal node */
 348                         if(has_reg_class(si, irn)) {
 349                                 assert(get_irn_mode(irn) != mode_T && "node must not be a tuple");
 350                                 assert(pset_find_ptr(live, irn) && "node must be live");
 351                                 pset_remove_ptr(live, irn);
 352                                 results = 1;
 353                         } else {
 354                                 results = 0;
 355                         }
 356                 }
 357
 358                 /* cand holds the irns which may be spilled */
 359                 cand = pset_new_ptr(8);
 360                 for(l=pset_first(live); l; l=pset_next(live))
 361                         pset_insert_ptr(cand, l);
 362
 363                 /*
 364                  * Determine number of arguments
 365                  */
 366                 relevant_args = 0;
 367                 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
 368                         ir_node *op = get_irn_n(irn, i);
 369                         if(has_reg_class(si, op)) {
 370                                 DBG((si->dbg, LEVEL_2, "  arg %+F\n", op));
 371                                 relevant_args++;
 372
 373                                 /* arguments must not be spilled */
 374                                 if(pset_find_ptr(cand, op))
 375                                         pset_remove_ptr(cand, op);
 376                         }
 377                 }
 378
 379                 /*
 380                  * Determine, how many values must be in memory.
 381                  * We have 'n_regs' registers.
 382                  * The instr. needs 'demand'.
 383                  * So (R:= n_regs - demand) registers can be used for candidates 'cand'.
 384                  * The rest (M:= n_cand - R) must reside in memory.
 385                  */
 386                 demand = MAX(results, relevant_args);
 387                 n_cand = pset_count(cand);
 388                 must_be_in_mem = n_cand - (n_regs - demand);
 389
 390                 DBG((si->dbg, LEVEL_1, "  Demand: %d, Cands: %d, InMem: %d\n", demand, n_cand, must_be_in_mem));
 391                 DBG((si->dbg, LEVEL_3, "  Cand-Set:\n"));
 392                 print_live_set(si, cand);
 393
 394                 /*
 395                  * Generate the corresponding constraint spilling
 396                  * enough candidates at this label.
 397                  */
 398                 if(must_be_in_mem > 0) {
 399                         ir_snprintf(buf, sizeof(buf), "cp_%N_%N_%d", bl, irn, step);
 400                         cst = lpp_add_cst(si->lpp, buf, lpp_greater, must_be_in_mem);
 401
 402                         for(l = pset_first(cand); l; l = pset_next(cand)) {
 403                                 live_range_t *lr = get_irn_link(l);
 404                                 lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, 1.0);
 405                         }
 406                 }
 407
 408                 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
 409                         ir_node *op = get_irn_n(irn, i);
 410
 411                         if(has_reg_class(si, op)) {
 412                                 live_range_t *op_lr = get_live_range(si, op, irn, i);
 413                                 set_irn_link(op, op_lr);
 414
 415 #if 0
 416                                 /*
 417                                  * The operand is reloaded at its usage, so it must not occur
 418                                  * in the constraint which determines which values live at the
 419                                  * instruction must reside in memory.
 420                                  */
 421                                 if(must_be_in_mem > 0) {
 422                                         DBG((si->dbg, LEVEL_3, " Resetting %+F to 0:\n", op));
 423                                         lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, 0.0);
 424                                 }
 425 #endif
 426
 427                                 /*
 428                                  * Check, if the node is a rematerializable node and
 429                                  * if its operands are live here.
 430                                  */
 431                                 if(si->enable_remat && can_remat(si, op, live)) {
 432                                         int cst;
 433                                         int j, n;
 434                                         int n_operands = 0;
 435
 436                                         for(j = 0, n = get_irn_arity(op); j < n; ++j)
 437                                                 n_operands += has_reg_class(si, get_irn_n(op, j));
 438
 439                                         /* Make the remat constraint for this operand */
 440                                         ir_snprintf(buf, sizeof(buf), "ce1_%N_%N_%d", op, irn, i);
 441                                         cst = lpp_add_cst(si->lpp, buf, lpp_less, n_operands);
 442
 443                                         /* Make the rematerialize variable for the operand */
 444                                         ir_snprintf(buf, sizeof(buf), "e_%N_%N_%d", op, irn, i);
 445                                         op_lr->is_remat_var = lpp_add_var(si->lpp, buf, lpp_binary, COST_REMAT);
 446                                         lpp_set_factor_fast(si->lpp, cst, op_lr->is_remat_var, n_operands);
 447
 448                                         for(j = 0, n = get_irn_arity(op); j < n; ++j) {
 449                                                 ir_node *oop = get_irn_n(op, j);
 450                                                 if(has_reg_class(si, oop)) {
 451                                                         live_range_t *lr = get_irn_link(oop);
 452                                                         lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, 1.0);
 453                                                 }
 454                                         }
 455
 456                                         ir_snprintf(buf, sizeof(buf), "ce2_%N_%N_%d", op, irn, i);
 457                                         cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0);
 458                                         lpp_set_factor_fast(si->lpp, cst, op_lr->is_remat_var, 1.0);
 459                                         lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, -1.0);
 460                                 }
 461                         }
 462                 }
 463
 464                 /*
 465                  * Insert arguments of current instr into the live set
 466                  */
 467                 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
 468                         ir_node *op = get_irn_n(irn, i);
 469                         if(has_reg_class(si, op))
 470                                 pset_insert_ptr(live, op);
 471                 }
 472
 473                 del_pset(cand);
 474                 step++;
 475         }
 476
 477         if(bl == get_irg_start_block(get_irn_irg(bl)))
 478                 goto end;
 479
 480         /*
 481          * Here, the live set contains
 482          * - phis of the block
 483          * - live-in values of the block
 484          *
 485          * TODO: comment is wrong
 486          * If a value is live in, it must be in a register in all predecessor
 487          * blocks or in memory at the end of all predecessor blocks. Also, the
 488          * closest use in the current block must then be from register or
 489          * memory, respectively.
 490          */
 491         for(irn = pset_first(live); irn; irn = pset_next(live)) {
 492                 live_range_t *lr = get_irn_link(irn);
 493                 int is_phi = is_Phi(irn) && get_nodes_block(irn) == bl;
 494                 int cst;
 495
 496                 assert(has_reg_class(si, irn));
 497                 assert(is_Phi(irn) || is_live_in(bl, irn));
 498
 499                 /* Deprecated: Can be done with the first uses map */
 500                 if(is_phi)
 501                         lr->use_head->closest_use = lr;
 502
 503                 /*
 504                  * Remind the liverange of the first use of a live (or phi) in the
 505                  * current block.
 506                  */
 507                 add_first_use(si, bl, irn, lr);
 508
 509                 for(i = 0; i < n_preds; ++i) {
 510                         ir_node *pred_bl     = get_Block_cfgpred_block(bl, i);
 511                         ir_node *end_node    = is_phi ? get_irn_n(irn, i) : irn;
 512                         live_range_t *op_lr  = get_live_range(si, end_node, pred_bl, -1);
 513                         edge_reload_t *edge  = obstack_alloc(si->obst, sizeof(edge[0]));
 514
 515                         ir_snprintf(buf, sizeof(buf), "edge_b%N_p%N_i%N", bl, pred_bl, end_node);
 516                         edge->in_mem_var = lpp_add_var(si->lpp, buf, lpp_binary, get_weight(pred_bl) * COST_LOAD);
 517                         edge->bl         = bl;
 518                         edge->irn        = end_node;
 519                         edge->pos        = i;
 520                         edge->next       = si->edges;
 521                         si->edges        = edge;
 522
 523                         ir_snprintf(buf, sizeof(buf), "cedge_b%N_p%N_i%N", bl, pred_bl, end_node);
 524                         cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0);
 525                         lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, 1.0);
 526                         lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, -1.0);
 527                         lpp_set_factor_fast(si->lpp, cst, edge->in_mem_var, -1.0);
 528                 }
 529         }
 530
 531 end:
 532         del_pset(live);
 533 }
 534
 535 /**
 536  * Add the costs for a store.
 537  *
 538  * If one of the uses is from memory, add additional costs for the
 539  * spill.
 540  *
 541  * m_1 + ... + m_n - M * s <= 0
 542  *
 543  * @param si The ILP spilling environment.
 544  */
 545 static void add_store_costs(spill_ilp_t *si)
 546 {
 547         if(si->enable_store) {
 548                 char buf[64];
 549                 irn_use_head_t *uh;
 550
 551                 for(uh = set_first(si->irn_use_heads); uh; uh = set_next(si->irn_use_heads)) {
 552                         int cst;
 553                         live_range_t *lr;
 554
 555                         ir_snprintf(buf, sizeof(buf), "cs_%N", uh->irn);
 556                         cst = lpp_add_cst(si->lpp, buf, lpp_less, 0);
 557
 558                         ir_snprintf(buf, sizeof(buf), "s_%N", uh->irn);
 559                         uh->spill_var = lpp_add_var(si->lpp, buf, lpp_binary,
 560                                         get_weight(uh->irn) * COST_STORE);
 561                         lpp_set_factor_fast(si->lpp, cst, uh->spill_var, -BIGM);
 562
 563                         list_for_each_entry(live_range_t, lr, &uh->head, list)
 564                                 lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, 1.0);
 565                 }
 566         }
 567 }
 568
 569 static INLINE int is_zero(double x)
 570 {
 571   return fabs(x) < 0.00001;
 572 }
 573
 574 static int is_spilled(const spill_ilp_t *si, const live_range_t *lr)
 575 {
 576         return !is_zero(lpp_get_var_sol(si->lpp, lr->in_mem_var));
 577 }
 578
 579 static int is_mem_phi(const ir_node *phi, void *data)
 580 {
 581         spill_ilp_t *si = data;
 582         return is_spilled(si, get_use_head(si, phi)->closest_use);
 583 }
 584
 585 static void writeback_results(spill_ilp_t *si)
 586 {
 587         irn_use_head_t *uh;
 588         edge_reload_t *edge;
 589
 590         /* Look at each node and examine the usages. */
 591         for(uh = set_first(si->irn_use_heads); uh; uh = set_next(si->irn_use_heads)) {
 592                 live_range_t *lr;
 593
 594                 si->stats.n_spills += !is_zero(lpp_get_var_sol(si->lpp, uh->spill_var));
 595
 596                 /* Go through all live ranges of the node. */
 597                 list_for_each_entry(live_range_t, lr, &uh->head, list) {
 598                         if(is_spilled(si, lr) && !is_end_of_block_use(lr)) {
 599                                 DBG((si->dbg, LEVEL_2, "%+F: inserting reload at user %+F\n",
 600                                                         lr->irn, lr->user));
 601                                 be_add_reload(si->senv, lr->irn, lr->user);
 602                                 si->stats.n_reloads += 1;
 603                         }
 604                 }
 605         }
 606
 607         for(edge = si->edges; edge; edge = edge->next) {
 608                 if(!is_zero(lpp_get_var_sol(si->lpp, edge->in_mem_var))) {
 609                         DBG((si->dbg, LEVEL_2, "%+F: insert reload on edge %d from %+F\n",
 610                                                 edge->irn, edge->pos, edge->bl));
 611                         be_add_reload_on_edge(si->senv, edge->irn, edge->bl, edge->pos);
 612                         si->stats.n_reloads += 1;
 613                 }
 614         }
 615
 616         be_insert_spills_reloads(si->senv, NULL);
 617 }
 618
 619 void be_spill_ilp(const be_main_session_env_t *session_env,
 620     const arch_register_class_t *cls)
 621 {
 622         char problem_name[256];
 623         struct obstack obst;
 624         spill_ilp_t si;
 625
 626         ir_snprintf(problem_name, sizeof(problem_name), "%F_%s", session_env->irg, cls->name);
 627
 628         obstack_init(&obst);
 629         memset(&si.stats, 0, sizeof(si.stats));
 630         si.session         = session_env;
 631         si.obst            = &obst;
 632         si.dbg             = firm_dbg_register("be.ra.spillilp");
 633         si.senv            = be_new_spill_env(si.dbg, session_env, cls, is_mem_phi, &si);
 634         si.cls             = cls;
 635         si.lpp             = new_lpp(problem_name, lpp_minimize);
 636         si.irn_use_heads   = new_set(cmp_irn_use_head, 4096);
 637         si.live_ranges     = new_set(cmp_live_range, 16384);
 638         si.first_uses      = new_set(cmp_first_use, 4096);
 639         si.edges           = NULL;
 640         si.enable_remat    = 0;
 641         si.enable_store    = 1;
 642
 643         firm_dbg_set_mask(si.dbg, DBG_LEVEL);
 644         irg_block_walk_graph(session_env->irg, process_block, NULL, &si);
 645         if(si.enable_store)
 646                 add_store_costs(&si);
 647
 648 #ifdef DUMP_ILP
 649         {
 650                 FILE *f;
 651                 char buf[256];
 652
 653                 ir_snprintf(buf, sizeof(buf), "%s-spill.ilp", problem_name);
 654                 if((f = fopen(buf, "wt")) != NULL) {
 655                         lpp_dump_plain(si.lpp, f);
 656                         fclose(f);
 657                 }
 658         }
 659 #endif
 660
 661         DBG((si.dbg, LEVEL_1, "%F\n", session_env->irg));
 662 #ifdef SOLVE_LOCAL
 663         lpp_solve_cplex(si.lpp);
 664 #else
 665         lpp_solve_net(si.lpp, LPP_SERVER, LPP_SOLVER);
 666 #endif
 667         assert(lpp_is_sol_valid(si.lpp) && "solution of ILP must be valid");
 668
 669         DBG((si.dbg, LEVEL_1, "\tnodes: %d, vars: %d, csts: %d\n",
 670                                 set_count(si.irn_use_heads), si.lpp->var_next, si.lpp->cst_next));
 671         DBG((si.dbg, LEVEL_1, "\titerations: %d, solution time: %g\n",
 672                                 si.lpp->iterations, si.lpp->sol_time));
 673
 674 #ifdef DUMP_SOLUTION
 675         {
 676                 FILE *f;
 677                 char buf[256];
 678
 679                 ir_snprintf(buf, sizeof(buf), "%s-spill.sol", problem_name);
 680                 if((f = fopen(buf, "wt")) != NULL) {
 681                         int i;
 682                         for(i = 0; i < si.lpp->var_next; ++i) {
 683                                 lpp_name_t *name = si.lpp->vars[i];
 684                                 fprintf(f, "%20s %4d %10f\n", name->name, name->nr, name->value);
 685                         }
 686                         fclose(f);
 687                 }
 688         }
 689 #endif
 690
 691         writeback_results(&si);
 692
 693 #ifdef DUMP_STATS
 694         {
 695                 char buf[256];
 696                 FILE *f;
 697
 698                 ir_snprintf(buf, sizeof(buf), "%s-spill.stat", problem_name);
 699                 if((f = fopen(buf, "wt")) != NULL) {
 700                         fprintf(f, "%20s: %d\n", "nodes", set_count(si.irn_use_heads));
 701                         fprintf(f, "%20s: %d\n", "vars", si.lpp->var_next);
 702                         fprintf(f, "%20s: %d\n", "csts", si.lpp->cst_next);
 703                         fprintf(f, "%20s: %f\n", "sol time", si.lpp->sol_time);
 704                         fprintf(f, "%20s: %d\n", "spills", si.stats.n_spills);
 705                         fprintf(f, "%20s: %d\n", "reloads", si.stats.n_reloads);
 706                         fprintf(f, "%20s: %d\n", "remats", si.stats.n_remat);
 707                         fclose(f);
 708                 }
 709         }
 710 #endif
 711
 712         del_set(si.irn_use_heads);
 713         del_set(si.live_ranges);
 714         free_lpp(si.lpp);
 715         obstack_free(&obst, NULL);
 716 }