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