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

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