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
  25 #include <lpp/lpp.h>
  26 #include <lpp/lpp_net.h>
  27
  28 #include "be_t.h"
  29 #include "belive_t.h"
  30 #include "besched_t.h"
  31 #include "beirgmod.h"
  32 #include "bearch.h"
  33 #include "benode_t.h"
  34 #include "beutil.h"
  35
  36 #define BIGM 1000.0
  37
  38 #define MAX(a,b) ((a) > (b) ? (a) : (b))
  39
  40 #define DBG_LEVEL SET_LEVEL_3
  41
  42 #define DUMP_SOLUTION
  43 #define DUMP_ILP
  44
  45 #define LPP_SERVER "i44pc52"
  46 #define LPP_SOLVER "cplex"
  47
  48 #define COST_LOAD      10
  49 #define COST_STORE     50
  50 #define COST_REMAT     (-9)
  51
  52 #define is_end_of_block_use(lr) (is_Block((lr)->user))
  53
  54 typedef struct _spill_ilp_t {
  55   const be_main_session_env_t *session_env;
  56   const arch_register_class_t *cls;
  57         firm_dbg_module_t *dbg;
  58   lpp_t *lpp;
  59         set *irn_use_heads;
  60   set *live_ranges;
  61         set *spill_ctx;
  62         pset *remove_phis;
  63   struct obstack *obst;
  64         int enable_store : 1;
  65         int enable_remat : 1;
  66 } spill_ilp_t;
  67
  68 typedef struct _live_range_t live_range_t;
  69
  70 typedef struct _irn_use_head_t {
  71         struct list_head head;
  72         ir_node *irn;
  73         int spill_var;
  74         int n_uses;
  75         live_range_t *closest_use;
  76 } irn_use_head_t;
  77
  78 struct _live_range_t {
  79   struct list_head list;
  80         irn_use_head_t *use_head;
  81   ir_node *user;
  82   ir_node *irn;
  83         int pos;
  84   int in_mem_var;
  85   int is_remat_var;
  86 };
  87
  88 typedef struct _spill_ctx_t {
  89         ir_node *spilled;  /**< The spilled node. */
  90         ir_node *user;     /**< The node this spill is for. */
  91         ir_node *spill;    /**< The spill itself. */
  92 } spill_ctx_t;
  93
  94 static int has_reg_class(const spill_ilp_t *si, const ir_node *irn)
  95 {
  96   return arch_irn_has_reg_class(si->session_env->main_env->arch_env,
  97       irn, arch_pos_make_out(0), si->cls);
  98 }
  99
 100 static int register_demand(spill_ilp_t *si, const ir_node *irn)
 101 {
 102         const arch_env_t *arch_env = si->session_env->main_env->arch_env;
 103         int n_in = arch_get_n_operands(arch_env, irn, 0);
 104         int n_out = arch_get_n_operands(arch_env, irn, -1);
 105
 106         return MAX(n_in, n_out);
 107 }
 108
 109 static int cmp_spill_ctx(const void *a, const void *b, size_t n)
 110 {
 111         const spill_ctx_t *p = a;
 112         const spill_ctx_t *q = b;
 113   return !(p->user == q->user && p->spilled == q->spilled);
 114 }
 115
 116 static int cmp_live_range(const void *a, const void *b, size_t n)
 117 {
 118   const live_range_t *p = a;
 119   const live_range_t *q = b;
 120
 121   return !(p->user == q->user && p->irn == q->irn && p->pos == q->pos);
 122 }
 123
 124 static int cmp_irn_use_head(const void *a, const void *b, size_t n)
 125 {
 126   const irn_use_head_t *p = a;
 127   const irn_use_head_t *q = b;
 128
 129         return !(p->irn == q->irn);
 130 }
 131
 132 /**
 133  * Checks, if a vertain node can be recomputed at a certain position.
 134  * @param si    The spill ILP environment.
 135  * @param irn   The node to recompute.
 136  * @param live  The nodes live at the place where @p irn shall be
 137  *              recomputed.
 138  * @return      1, if irn can be recomputed, 0 if not.
 139  */
 140 static INLINE int can_remat(const spill_ilp_t *si, const ir_node *irn, pset *live)
 141 {
 142         int i, n;
 143   const arch_env_t *arch_env    = si->session_env->main_env->arch_env;
 144         int remat = (arch_irn_get_flags(arch_env, irn) & arch_irn_flags_rematerializable) != 0;
 145
 146         for(i = 0, n = get_irn_arity(irn); i < n && remat; ++i) {
 147                 ir_node *op = get_irn_n(irn, i);
 148                 remat &= !has_reg_class(si, op) || pset_find_ptr(live, op);
 149         }
 150
 151         return remat;
 152 }
 153
 154 static spill_ctx_t *get_spill_ctx(spill_ilp_t *si, ir_node *spilled, ir_node *ctx_irn)
 155 {
 156         spill_ctx_t templ, *res;
 157
 158         templ.spilled = spilled;
 159         templ.user    = ctx_irn;
 160         templ.spill   = NULL;
 161
 162         res = set_insert(si->spill_ctx, &templ, sizeof(templ),
 163                         HASH_COMBINE(HASH_PTR(spilled), HASH_PTR(ctx_irn)));
 164
 165         return res;
 166 }
 167
 168 static live_range_t *get_live_range(spill_ilp_t *si, ir_node *irn, ir_node *user, int pos)
 169 {
 170   live_range_t lr, *res;
 171         irn_use_head_t iuh, *head;
 172         int is_new;
 173   unsigned hash = HASH_COMBINE(HASH_PTR(irn), HASH_PTR(user));
 174
 175   lr.user    = user;
 176   lr.irn     = irn;
 177   lr.pos     = pos;
 178   lr.in_mem_var = -1;
 179         lr.is_remat_var = -1;
 180
 181   res = set_insert(si->live_ranges, &lr, sizeof(lr), hash);
 182         is_new = res->in_mem_var == -1;
 183
 184   if(is_new) {
 185     char buf[128];
 186     ir_snprintf(buf, sizeof(buf), "m_%s%N_%N_%d",
 187                                 is_Phi(irn) ? "phi_" : "", irn, user, MAX(pos, 0));
 188     res->in_mem_var = lpp_add_var(si->lpp, buf, lpp_binary, pos >= 0 ? COST_LOAD : 0.0);
 189   }
 190
 191         memset(&iuh, 0, sizeof(iuh));
 192         iuh.irn = irn;
 193         iuh.n_uses = -1;
 194         head = set_insert(si->irn_use_heads, &iuh, sizeof(iuh), HASH_PTR(irn));
 195         if(head->n_uses == -1) {
 196                 head->n_uses = 0;
 197                 INIT_LIST_HEAD(&head->head);
 198         }
 199
 200         if(is_new) {
 201                 list_add_tail(&res->list, &head->head);
 202                 head->n_uses++;
 203         }
 204
 205         res->use_head = head;
 206
 207   return res;
 208 }
 209
 210 static live_range_t *lookup_live_range(const spill_ilp_t *si, ir_node *irn,
 211                 ir_node *user, int pos)
 212 {
 213   live_range_t lr;
 214   unsigned hash = HASH_COMBINE(HASH_PTR(irn), HASH_PTR(user));
 215
 216   lr.user    = user;
 217   lr.irn     = irn;
 218   lr.pos     = pos;
 219   lr.in_mem_var = -1;
 220
 221   return set_find(si->live_ranges, &lr, sizeof(lr), hash);
 222 }
 223
 224 static void create_block_live_range_sets(ir_node *bl, void *data)
 225 {
 226         assert(is_Block(bl));
 227         set_irn_link(bl, pset_new_ptr_default());
 228 }
 229
 230 static void delete_block_live_range_sets(ir_node *bl, void *data)
 231 {
 232         assert(is_Block(bl));
 233
 234         del_pset(get_irn_link(bl));
 235         set_irn_link(bl, NULL);
 236 }
 237
 238 #if 0
 239 static void annotate_live_ranges(ir_node *irn, void *data)
 240 {
 241         const ir_edge_t *edge;
 242
 243         foreach_out_edge(irn, edge) {
 244                 pset *lr_set;
 245
 246                 ir_node *user = edge->use;
 247                 int pos       = edge->pos;
 248                 ir_node *bl   = get_nodes_block(user);
 249
 250                 if(is_Phi(user))
 251                         bl = get_Block_cfgpred_block(bl, pos);
 252
 253                 lr_set = get_irn_link(bl);
 254
 255         }
 256 }
 257 #endif
 258
 259
 260 static void process_block(ir_node *bl, void *data)
 261 {
 262         char buf[128];
 263         int i, n;
 264   spill_ilp_t *si  = data;
 265   int step         = 0;
 266   int n_regs       = arch_register_class_n_regs(si->cls);
 267         int n_preds      = get_irn_arity(bl);
 268   pset *live       = pset_new_ptr_default();
 269   irn_live_t *li;
 270   ir_node *irn;
 271
 272   /* as always, bring the live end nodes to life here */
 273   live_foreach(bl, li) {
 274     if(live_is_end(li) && has_reg_class(si, li->irn)) {
 275       ir_node *irn = (ir_node *) li->irn;
 276       pset_insert_ptr(live, irn);
 277
 278       /*
 279        * The "user" of the live range to the end of a block
 280        * is the block itself. This is quite arbitrary.
 281        */
 282       set_irn_link(irn, get_live_range(si, irn, bl, -1));
 283     }
 284   }
 285
 286         sched_foreach_reverse(bl, irn) {
 287                 ir_node *l;
 288                 int cst;
 289                 int demand;
 290                 int n_live;
 291                 int must_be_in_mem;
 292
 293                 /* We handle phi togther with live ins after this loop (see below). */
 294                 if(is_Phi(irn))
 295                         break;
 296
 297                 if(has_reg_class(si, irn))
 298                         pset_remove_ptr(live, irn);
 299
 300                 demand = register_demand(si, irn);
 301                 n_live = pset_count(live);
 302
 303                 /*
 304                  * Determine, how many values (which are not used at the label)
 305                  * must be in memory.
 306                  * demand means the number of registers, the operation will consume.
 307                  * So there are n_regs - demand registers available to store values
 308                  * which are not used at this label. The rest must reside in memory.
 309                  */
 310                 must_be_in_mem = MAX(n_live - (n_regs - demand), 0);
 311
 312                 if(must_be_in_mem > 0) {
 313
 314                         /*
 315                          * The constraint limiting the pressure at this label to
 316                          * the number of free registers.
 317                          */
 318                         ir_snprintf(buf, sizeof(buf), "cp_%N_%d", bl, step);
 319                         cst = lpp_add_cst(si->lpp, buf, lpp_greater, must_be_in_mem);
 320
 321                         for(l = pset_first(live); l; l = pset_next(live)) {
 322                                 live_range_t *lr = get_irn_link(l);
 323                                 lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, 1.0);
 324                         }
 325                 }
 326
 327                 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
 328                         ir_node *op = get_irn_n(irn, i);
 329
 330                         if(has_reg_class(si, op)) {
 331                                 live_range_t *op_lr = get_live_range(si, op, irn, i);
 332
 333                                 set_irn_link(op, op_lr);
 334
 335                                 /*
 336                                  * The operand is reloaded at its usage, so it must not occur
 337                                  * in the constraint which determines which values live at the
 338                                  * instruction must reside in memory.
 339                                  */
 340                                 if(must_be_in_mem > 0) {
 341                                         lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, 0.0);
 342                                 }
 343
 344                                 /*
 345                                  * Check, if the node is a rematerializable node and
 346                                  * if its operands are live here.
 347                                  */
 348                                 if(si->enable_remat && can_remat(si, op, live)) {
 349                                         int cst;
 350                                         int j, n;
 351                                         int n_operands = 0;
 352
 353                                         for(j = 0, n = get_irn_arity(op); j < n; ++j)
 354                                                 n_operands += has_reg_class(si, get_irn_n(op, j));
 355
 356                                         /* Make the remat constraint for this operand */
 357                                         ir_snprintf(buf, sizeof(buf), "ce1_%N_%N_%d", op, irn, i);
 358                                         cst = lpp_add_cst(si->lpp, buf, lpp_less, n_operands);
 359
 360                                         /* Make the rematerialize variable for the operand */
 361                                         ir_snprintf(buf, sizeof(buf), "e_%N_%N_%d", op, irn, i);
 362                                         op_lr->is_remat_var = lpp_add_var(si->lpp, buf, lpp_binary, COST_REMAT);
 363                                         lpp_set_factor_fast(si->lpp, cst, op_lr->is_remat_var, n_operands);
 364
 365                                         for(j = 0, n = get_irn_arity(op); j < n; ++j) {
 366                                                 ir_node *oop = get_irn_n(op, j);
 367                                                 if(has_reg_class(si, oop)) {
 368                                                         live_range_t *lr = get_irn_link(oop);
 369                                                         lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, 1.0);
 370                                                 }
 371                                         }
 372
 373                                         ir_snprintf(buf, sizeof(buf), "ce2_%N_%N_%d", op, irn, i);
 374                                         cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0);
 375                                         lpp_set_factor_fast(si->lpp, cst, op_lr->is_remat_var, 1.0);
 376                                         lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, -1.0);
 377                                 }
 378                         }
 379                 }
 380
 381                         for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
 382                                 ir_node *op = get_irn_n(irn, i);
 383                                 if(has_reg_class(si, op) && !is_Phi(irn))
 384                                         pset_insert_ptr(live, op);
 385                         }
 386
 387                 step++;
 388         }
 389
 390         if(bl == get_irg_start_block(get_irn_irg(bl)))
 391                 goto end;
 392
 393         /*
 394          * Here, only the phis in the block and the values live in are in the
 395          * live set.
 396          *
 397          * If a value is live in, it must be in a register in all predecessor
 398          * blocks or in memory at the end of all predecessor blocks. Also, the
 399          * closest use in the current block must then be from register or
 400          * memory, respectively.
 401          */
 402         for(irn = pset_first(live); irn; irn = pset_next(live)) {
 403                 live_range_t *lr = get_irn_link(irn);
 404                 int is_phi = is_Phi(irn) && get_nodes_block(irn) == bl;
 405                 int cst;
 406
 407                 if(is_phi)
 408                         lr->use_head->closest_use = lr;
 409
 410                 assert(has_reg_class(si, irn));
 411                 assert(is_Phi(irn) || is_live_in(bl, irn));
 412
 413 #if 0
 414                 ir_snprintf(buf, sizeof(buf), "c%s_%N_%N", (is_phi ? "phi" : "li"), irn, bl);
 415                 cst = lpp_add_cst(si->lpp, buf, lpp_equal, 0.0);
 416                 lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, -n_preds);
 417
 418                 for(i = 0; i < n_preds; ++i) {
 419                         ir_node *pred_bl     = get_Block_cfgpred_block(bl, i);
 420                         ir_node *end_node    = is_phi ? get_irn_n(irn, i) : irn;
 421                         live_range_t *op_lr  = get_live_range(si, end_node, pred_bl, -1);
 422
 423                         lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, 1.0);
 424                 }
 425 #endif
 426
 427                 for(i = 0; i < n_preds; ++i) {
 428                         ir_node *pred_bl     = get_Block_cfgpred_block(bl, i);
 429                         ir_node *end_node    = is_phi ? get_irn_n(irn, i) : irn;
 430                         live_range_t *op_lr  = get_live_range(si, end_node, pred_bl, -1);
 431
 432                         ir_snprintf(buf, sizeof(buf), "cpred_%N_%N_%d", lr->irn, bl, i);
 433                         cst = lpp_add_cst(si->lpp, buf, lpp_equal, 0.0);
 434                         lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, 1.0);
 435                         lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, -1.0);
 436                 }
 437         }
 438
 439 end:
 440
 441   del_pset(live);
 442 }
 443
 444 /**
 445  * Add the costs for a store.
 446  *
 447  * If one of the uses is from memory, add additional costs for the
 448  * spill.
 449  *
 450  * m_1 + ... + m_n - M * s <= 0
 451  *
 452  * @param si The ILP spilling environment.
 453  */
 454 static void add_store_costs(spill_ilp_t *si)
 455 {
 456         char buf[64];
 457         irn_use_head_t *uh;
 458         double costs = si->enable_store ? COST_STORE : 0.0;
 459
 460         for(uh = set_first(si->irn_use_heads); uh; uh = set_next(si->irn_use_heads)) {
 461                 int cst;
 462                 live_range_t *lr;
 463
 464                 ir_snprintf(buf, sizeof(buf), "cs_%N", uh->irn);
 465                 cst = lpp_add_cst(si->lpp, buf, lpp_less, 0);
 466
 467                 ir_snprintf(buf, sizeof(buf), "s_%N", uh->irn);
 468                 uh->spill_var = lpp_add_var(si->lpp, buf, lpp_binary, costs);
 469                 lpp_set_factor_fast(si->lpp, cst, uh->spill_var, -BIGM);
 470
 471     list_for_each_entry(live_range_t, lr, &uh->head, list)
 472                         lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, 1.0);
 473         }
 474 }
 475
 476 static INLINE int is_zero(double x)
 477 {
 478   return fabs(x) < 0.00001;
 479 }
 480
 481 static int is_spilled(const spill_ilp_t *si, const live_range_t *lr)
 482 {
 483         return !is_zero(lpp_get_var_sol(si->lpp, lr->in_mem_var));
 484 }
 485
 486 static ir_node *spill_irn(spill_ilp_t *si, ir_node *irn, ir_node *ctx_irn)
 487 {
 488   const be_node_factory_t *fact = si->session_env->main_env->node_factory;
 489   const arch_env_t *arch_env    = si->session_env->main_env->arch_env;
 490         spill_ctx_t *ctx;
 491
 492         ctx = get_spill_ctx(si, irn, ctx_irn);
 493         if(ctx->spill)
 494                 return ctx->spill;
 495
 496         ctx->spill = be_spill(fact, arch_env, irn);
 497         return ctx->spill;
 498 }
 499
 500 static ir_node *spill_phi(spill_ilp_t *si, ir_node *phi, ir_node *ctx_irn, pset *rem_phis)
 501 {
 502         int i, n;
 503         ir_mode *mode = get_irn_mode(phi);
 504         ir_node **ins;
 505         ir_node *bl = get_nodes_block(phi);
 506         ir_graph *irg = get_irn_irg(bl);
 507         spill_ctx_t *ctx;
 508
 509         assert(is_Phi(phi));
 510
 511         ctx = get_spill_ctx(si, phi, ctx_irn);
 512         if(ctx->spill)
 513                 return ctx->spill;
 514
 515         n    = get_irn_arity(phi);
 516         ins  = malloc(n * sizeof(ins[0]));
 517
 518         for(i = 0; i < n; ++i)
 519                 ins[i]  = new_r_Unknown(irg, mode_M);
 520
 521         ctx->spill = new_r_Phi(irg, bl, n, ins, mode_M);
 522         free(ins);
 523
 524         for(i = 0; i < n; ++i) {
 525                 ir_node *arg = get_irn_n(phi, i);
 526                 ir_node *res;
 527
 528                 if(is_Phi(arg))
 529                         res = spill_phi(si, arg, ctx_irn, rem_phis);
 530                 else
 531                         res = spill_irn(si, arg, ctx_irn);
 532
 533                 set_irn_n(ctx->spill, i, res);
 534         }
 535
 536         return ctx->spill;
 537 }
 538
 539 static ir_node *spill_live_range(spill_ilp_t *si, live_range_t *lr, pset *rem_phis)
 540 {
 541         const live_range_t *closest = lr->use_head->closest_use;
 542
 543         if(is_Phi(lr->irn) && closest && is_spilled(si, closest))
 544                 return spill_phi(si, lr->irn, lr->irn, rem_phis);
 545         else
 546                 return spill_irn(si, lr->irn, lr->irn);
 547 }
 548
 549
 550 static void writeback_results(spill_ilp_t *si)
 551 {
 552   const be_node_factory_t *fact = si->session_env->main_env->node_factory;
 553   const arch_env_t *arch_env    = si->session_env->main_env->arch_env;
 554         ir_node *irn;
 555         irn_use_head_t *uh;
 556         pset *rem_phis = pset_new_ptr_default();
 557
 558         for(uh = set_first(si->irn_use_heads); uh; uh = set_next(si->irn_use_heads)) {
 559                 if(is_Phi(uh->irn) && is_spilled(si, uh->closest_use))
 560                         pset_insert_ptr(rem_phis, uh->irn);
 561         }
 562
 563         /* Look at each node and examine the usages. */
 564         for(uh = set_first(si->irn_use_heads); uh; uh = set_next(si->irn_use_heads)) {
 565     live_range_t *lr;
 566     ir_node **reloads;
 567
 568     int n_reloads           = 0;
 569     ir_node *irn            = uh->irn;
 570                 ir_mode *mode           = get_irn_mode(irn);
 571
 572                 /* Go through all live ranges of the node. */
 573     list_for_each_entry(live_range_t, lr, &uh->head, list) {
 574       int spilled = is_spilled(si, lr);
 575                         // int rematd  = !is_zero(lpp_get_var_sol(si->lpp, lr->is_remat_var));
 576
 577                         if(spilled && !is_end_of_block_use(lr)) {
 578                                 ir_node *bl      = get_nodes_block(lr->user);
 579                                 ir_node *spill   = spill_live_range(si, lr, rem_phis);
 580                                 ir_node *reload  = new_Reload(fact, si->cls,
 581                                                 si->session_env->irg, bl, mode, spill);
 582
 583                                 obstack_ptr_grow(si->obst, reload);
 584                                 n_reloads++;
 585
 586                                 sched_add_before(lr->user, reload);
 587                         }
 588
 589     }
 590
 591                 if(n_reloads > 0) {
 592                         reloads = obstack_finish(si->obst);
 593                         be_introduce_copies_ignore(si->session_env->dom_front, irn,
 594                                         n_reloads, reloads, rem_phis);
 595                         obstack_free(si->obst, reloads);
 596                 }
 597   }
 598
 599         for(irn = pset_first(rem_phis); irn; irn = pset_next(rem_phis)) {
 600                 int i, n;
 601
 602                 for(i = 0, n = get_irn_arity(irn); i < n; ++i)
 603                         set_irn_n(irn, i, new_r_Bad(si->session_env->irg));
 604                 sched_remove(irn);
 605         }
 606 }
 607
 608 void be_spill_ilp(const be_main_session_env_t *session_env,
 609     const arch_register_class_t *cls)
 610 {
 611         char buf[256];
 612         char problem_name[256];
 613   struct obstack obst;
 614   spill_ilp_t si;
 615
 616         ir_snprintf(problem_name, sizeof(problem_name), "%F_%s", session_env->irg, cls->name);
 617
 618   obstack_init(&obst);
 619   si.obst           = &obst;
 620         si.dbg            = firm_dbg_register("be.ra.spillilp");
 621   si.session_env    = session_env;
 622   si.cls            = cls;
 623   si.lpp            = new_lpp(problem_name, lpp_minimize);
 624   si.irn_use_heads  = new_set(cmp_irn_use_head, 4096);
 625   si.live_ranges    = new_set(cmp_live_range, 16384);
 626   si.spill_ctx      = new_set(cmp_spill_ctx, 4096);
 627         si.enable_remat   = 1;
 628         si.enable_store   = 0;
 629
 630         firm_dbg_set_mask(si.dbg, DBG_LEVEL);
 631         irg_block_walk_graph(session_env->irg, process_block, NULL, &si);
 632         if(si.enable_store)
 633                 add_store_costs(&si);
 634
 635 #ifdef DUMP_ILP
 636         {
 637                 FILE *f;
 638
 639                 ir_snprintf(buf, sizeof(buf), "spill-%s.ilp", problem_name);
 640                 if((f = fopen(buf, "wt")) != NULL) {
 641                         lpp_dump_plain(si.lpp, f);
 642                         fclose(f);
 643                 }
 644         }
 645 #endif
 646
 647         DBG((si.dbg, LEVEL_1, "%F\n", session_env->irg));
 648         lpp_solve_net(si.lpp, LPP_SERVER, LPP_SOLVER);
 649         assert(lpp_is_sol_valid(si.lpp) && "ILP not feasible");
 650
 651         assert(lpp_is_sol_valid(si.lpp) && "solution of ILP must be valid");
 652
 653         DBG((si.dbg, LEVEL_1, "\tnodes: %d, vars: %d, csts: %d\n",
 654                                 set_count(si.irn_use_heads), si.lpp->var_next, si.lpp->cst_next));
 655         DBG((si.dbg, LEVEL_1, "\titerations: %d, solution time: %g\n",
 656                                 si.lpp->iterations, si.lpp->sol_time));
 657
 658 #ifdef DUMP_SOLUTION
 659         {
 660                 FILE *f;
 661
 662                 ir_snprintf(buf, sizeof(buf), "spill-%s.sol", problem_name);
 663                 if((f = fopen(buf, "wt")) != NULL) {
 664                         int i;
 665                         for(i = 0; i < si.lpp->var_next; ++i) {
 666                                 lpp_name_t *name = si.lpp->vars[i];
 667                                 fprintf(f, "%10s %4d %10f\n", name->name, name->nr, name->value);
 668                         }
 669                         fclose(f);
 670                 }
 671         }
 672 #endif
 673   writeback_results(&si);
 674
 675   del_set(si.irn_use_heads);
 676   del_set(si.live_ranges);
 677   free_lpp(si.lpp);
 678   obstack_free(&obst, NULL);
 679 }