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