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

   1 /*
   2  * Author:      Daniel Grund, Sebastian Hack, Matthias Braun
   3  * Date:                29.09.2005
   4  * Copyright:   (c) Universitaet Karlsruhe
   5  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
   6  * CVS-Id:      $Id$
   7  */
   8 #ifdef HAVE_CONFIG_H
   9 #include "config.h"
  10 #endif
  11
  12 #include <stdlib.h>
  13
  14 #include "pset.h"
  15 #include "irnode_t.h"
  16 #include "ircons_t.h"
  17 #include "iredges_t.h"
  18 #include "irbackedge_t.h"
  19 #include "irprintf.h"
  20 #include "ident_t.h"
  21 #include "type_t.h"
  22 #include "entity_t.h"
  23 #include "debug.h"
  24 #include "irgwalk.h"
  25 #include "array.h"
  26 #include "pdeq.h"
  27 #include "unionfind.h"
  28 #include "execfreq.h"
  29
  30 #include "belive_t.h"
  31 #include "besched_t.h"
  32 #include "bespill.h"
  33 #include "belive_t.h"
  34 #include "benode_t.h"
  35 #include "bechordal_t.h"
  36 #include "bejavacoal.h"
  37 #include "benodesets.h"
  38 #include "bespilloptions.h"
  39 #include "bestatevent.h"
  40
  41 // only rematerialise when costs are less than REMAT_COST_LIMIT
  42 // TODO determine a good value here...
  43 #define REMAT_COST_LIMIT        10
  44
  45 typedef struct _reloader_t reloader_t;
  46
  47 struct _reloader_t {
  48         reloader_t *next;
  49         ir_node    *reloader;
  50         ir_node    *rematted_node;
  51         int        allow_remat;     /**< the node may be rematted instead of reloaded if global remat option is on */
  52 };
  53
  54 typedef struct _spill_info_t {
  55         /** the value that should get spilled */
  56         ir_node *spilled_node;
  57         /** list of places where the value should get reloaded */
  58         reloader_t *reloaders;
  59
  60         /** the spill node, or a PhiM node */
  61         ir_node *spill;
  62         /** if we had the value of a phi spilled before but not the phi itself then
  63          * this field contains the spill for the phi value */
  64         ir_node *old_spill;
  65
  66         /** the register class in which the reload should be placed */
  67         const arch_register_class_t *reload_cls;
  68 } spill_info_t;
  69
  70 struct _spill_env_t {
  71         const arch_env_t *arch_env;
  72         ir_graph *irg;
  73         struct obstack obst;
  74         be_irg_t *birg;
  75         int spill_cost;     /**< the cost of a single spill node */
  76         int reload_cost;    /**< the cost of a reload node */
  77         set *spills;        /**< all spill_info_t's, which must be placed */
  78         pset *mem_phis;     /**< set of all special spilled phis. allocated and freed separately */
  79
  80         DEBUG_ONLY(firm_dbg_module_t *dbg;)
  81 };
  82
  83 /**
  84  * Compare two spill infos.
  85  */
  86 static int cmp_spillinfo(const void *x, const void *y, size_t size) {
  87         const spill_info_t *xx = x;
  88         const spill_info_t *yy = y;
  89         return xx->spilled_node != yy->spilled_node;
  90 }
  91
  92 /**
  93  * Returns spill info for a specific value (returns NULL if the info doesn't
  94  * exist yet)
  95  */
  96 static spill_info_t *find_spillinfo(const spill_env_t *env, ir_node *value) {
  97         spill_info_t info;
  98         int hash = nodeset_hash(value);
  99
 100         info.spilled_node = value;
 101
 102         return set_find(env->spills, &info, sizeof(info), hash);
 103 }
 104
 105 /**
 106  * Returns spill info for a specific value (the value that is to be spilled)
 107  */
 108 static spill_info_t *get_spillinfo(const spill_env_t *env, ir_node *value) {
 109         spill_info_t info, *res;
 110         int hash = nodeset_hash(value);
 111
 112         info.spilled_node = value;
 113         res = set_find(env->spills, &info, sizeof(info), hash);
 114
 115         if (res == NULL) {
 116                 info.reloaders = NULL;
 117                 info.spill = NULL;
 118                 info.old_spill = NULL;
 119                 info.reload_cls = NULL;
 120                 res = set_insert(env->spills, &info, sizeof(info), hash);
 121         }
 122
 123         return res;
 124 }
 125
 126 DEBUG_ONLY(
 127 /* Sets the debug module of a spill environment. */
 128 void be_set_spill_env_dbg_module(spill_env_t *env, firm_dbg_module_t *dbg) {
 129         env->dbg = dbg;
 130 }
 131 )
 132
 133 /* Creates a new spill environment. */
 134 spill_env_t *be_new_spill_env(be_irg_t *birg) {
 135         spill_env_t *env        = xmalloc(sizeof(env[0]));
 136         env->spills                     = new_set(cmp_spillinfo, 1024);
 137         env->irg            = be_get_birg_irg(birg);
 138         env->birg           = birg;
 139         env->arch_env       = birg->main_env->arch_env;
 140         env->mem_phis           = pset_new_ptr_default();
 141         // TODO, ask backend about costs..., or even ask backend whether we should
 142         // rematerialize...
 143         env->spill_cost     = 8;
 144         env->reload_cost    = 5;
 145         obstack_init(&env->obst);
 146         return env;
 147 }
 148
 149 /* Deletes a spill environment. */
 150 void be_delete_spill_env(spill_env_t *env) {
 151         del_set(env->spills);
 152         del_pset(env->mem_phis);
 153         obstack_free(&env->obst, NULL);
 154         free(env);
 155 }
 156
 157 /*
 158  *  ____  _                  ____      _                 _
 159  * |  _ \| | __ _  ___ ___  |  _ \ ___| | ___   __ _  __| |___
 160  * | |_) | |/ _` |/ __/ _ \ | |_) / _ \ |/ _ \ / _` |/ _` / __|
 161  * |  __/| | (_| | (_|  __/ |  _ <  __/ | (_) | (_| | (_| \__ \
 162  * |_|   |_|\__,_|\___\___| |_| \_\___|_|\___/ \__,_|\__,_|___/
 163  *
 164  */
 165
 166 void be_add_remat(spill_env_t *env, ir_node *to_spill, ir_node *before, ir_node *rematted_node) {
 167         spill_info_t *spill_info;
 168         reloader_t *reloader;
 169
 170         spill_info = get_spillinfo(env, to_spill);
 171
 172         /* add the remat information */
 173         reloader                = obstack_alloc(&env->obst, sizeof(reloader[0]));
 174         reloader->next          = spill_info->reloaders;
 175         reloader->reloader      = before;
 176         reloader->rematted_node = rematted_node;
 177         reloader->allow_remat   = 1;
 178
 179         spill_info->reloaders  = reloader;
 180
 181         DBG((env->dbg, LEVEL_1, "creating spillinfo for %+F, will be rematerialized before %+F\n",
 182                 to_spill, before));
 183 }
 184
 185 void be_add_reload(spill_env_t *env, ir_node *to_spill, ir_node *before,
 186                 const arch_register_class_t *reload_cls, int allow_remat)
 187 {
 188         spill_info_t *info;
 189         reloader_t *rel;
 190
 191         info = get_spillinfo(env, to_spill);
 192
 193         if (is_Phi(to_spill)) {
 194                 int i, arity;
 195
 196                 /* create spillinfos for the phi arguments */
 197                 for (i = 0, arity = get_irn_arity(to_spill); i < arity; ++i) {
 198                         ir_node *arg = get_irn_n(to_spill, i);
 199                         get_spillinfo(env, arg);
 200                 }
 201
 202 #if 1
 203                 // hackery... sometimes the morgan algo spilled the value of a phi,
 204                 // the belady algo decides later to spill the whole phi, then sees the
 205                 // spill node and adds a reload for that spill node, problem is the
 206                 // reload gets attach to that same spill (and is totally unnecessary)
 207                 if (info->old_spill != NULL &&
 208                         (before == info->old_spill || value_dominates(before, info->old_spill)))
 209                 {
 210                         printf("spilledphi hack was needed...\n");
 211                         before = sched_next(info->old_spill);
 212                 }
 213 #endif
 214         }
 215
 216         /* put reload into list */
 217         rel                = obstack_alloc(&env->obst, sizeof(rel[0]));
 218         rel->next          = info->reloaders;
 219         rel->reloader      = before;
 220         rel->rematted_node = NULL;
 221         rel->allow_remat   = allow_remat;
 222
 223         info->reloaders  = rel;
 224         assert(info->reload_cls == NULL || info->reload_cls == reload_cls);
 225         info->reload_cls = reload_cls;
 226
 227         DBG((env->dbg, LEVEL_1, "creating spillinfo for %+F, will be reloaded before %+F, may%s be rematerialized\n",
 228                 to_spill, before, allow_remat ? "" : " not"));
 229 }
 230
 231 static ir_node *get_reload_insertion_point(ir_node *block, int pos) {
 232         ir_node *predblock, *last;
 233
 234         /* simply add the reload to the beginning of the block if we only have 1 predecessor
 235          * (we don't need to check for phis as there can't be any in a block with only 1 pred)
 236          */
 237         if(get_Block_n_cfgpreds(block) == 1) {
 238                 assert(!is_Phi(sched_first(block)));
 239                 return sched_first(block);
 240         }
 241
 242         /* We have to reload the value in pred-block */
 243         predblock = get_Block_cfgpred_block(block, pos);
 244         last = sched_last(predblock);
 245
 246         /* we might have projs and keepanys behind the jump... */
 247         while(is_Proj(last) || be_is_Keep(last)) {
 248                 last = sched_prev(last);
 249                 assert(!sched_is_end(last));
 250         }
 251
 252         if(!is_cfop(last)) {
 253                 last = sched_next(last);
 254                 // last node must be a cfop, only exception is the start block
 255                 assert(last     == get_irg_start_block(get_irn_irg(block)));
 256         }
 257
 258         // add the reload before the (cond-)jump
 259         return last;
 260 }
 261
 262 void be_add_reload_on_edge(spill_env_t *env, ir_node *to_spill, ir_node *block, int pos,
 263                 const arch_register_class_t *reload_cls, int allow_remat)
 264 {
 265         ir_node *before = get_reload_insertion_point(block, pos);
 266         be_add_reload(env, to_spill, before, reload_cls, allow_remat);
 267 }
 268
 269 void be_spill_phi(spill_env_t *env, ir_node *node) {
 270         spill_info_t* spill;
 271         int i, arity;
 272
 273         assert(is_Phi(node));
 274
 275         pset_insert_ptr(env->mem_phis, node);
 276
 277         // create spillinfos for the phi arguments
 278         spill = get_spillinfo(env, node);
 279         for(i = 0, arity = get_irn_arity(node); i < arity; ++i) {
 280                 ir_node *arg = get_irn_n(node, i);
 281                 get_spillinfo(env, arg);
 282         }
 283
 284         // if we had a spill for the phi value before, then remove this spill from
 285         // schedule, as we will remove it in the insert spill/reload phase
 286         if(spill->spill != NULL && !is_Phi(spill->spill)) {
 287                 assert(spill->old_spill == NULL);
 288                 spill->old_spill = spill->spill;
 289                 spill->spill = NULL;
 290         }
 291 }
 292
 293 /*
 294  *   ____                _         ____        _ _ _
 295  *  / ___|_ __ ___  __ _| |_ ___  / ___| _ __ (_) | |___
 296  * | |   | '__/ _ \/ _` | __/ _ \ \___ \| '_ \| | | / __|
 297  * | |___| | |  __/ (_| | ||  __/  ___) | |_) | | | \__ \
 298  *  \____|_|  \___|\__,_|\__\___| |____/| .__/|_|_|_|___/
 299  *                                      |_|
 300  */
 301
 302 /**
 303  * Schedules a node after an instruction. (That is the place after all projs and phis
 304  * that are scheduled after the instruction)
 305  * This function also skips phi nodes at the beginning of a block
 306  */
 307 static void sched_add_after_insn(ir_node *sched_after, ir_node *node) {
 308         ir_node *next = sched_next(sched_after);
 309         while(is_Proj(next) || is_Phi(next)) {
 310                 next = sched_next(next);
 311         }
 312         assert(next != NULL);
 313
 314         if(sched_is_end(next)) {
 315                 sched_add_after(sched_last(get_nodes_block(sched_after)), node);
 316         } else {
 317                 sched_add_before(next, node);
 318         }
 319 }
 320
 321 /**
 322  * Creates a spill.
 323  *
 324  * @param senv      the spill environment
 325  * @param irn       the node that should be spilled
 326  * @param ctx_irn   an user of the spilled node
 327  *
 328  * @return a be_Spill node
 329  */
 330 static void spill_irn(spill_env_t *env, spill_info_t *spillinfo) {
 331         optimization_state_t opt;
 332         ir_node              *to_spill = spillinfo->spilled_node;
 333
 334         DBG((env->dbg, LEVEL_1, "spilling %+F ... ", to_spill));
 335
 336         /* Trying to spill an already spilled value, no need for a new spill
 337          * node then, we can simply connect to the same one for this reload
 338          *
 339          * (although rematerialization code should handle most of these cases
 340          * this can still happen when spilling Phis)
 341          */
 342         if (be_is_Reload(to_spill)) {
 343                 spillinfo->spill = get_irn_n(to_spill, be_pos_Reload_mem);
 344                 DB((env->dbg, LEVEL_1, "skip reload, using existing spill %+F\n", spillinfo->spill));
 345                 return;
 346         }
 347
 348         if (arch_irn_is(env->arch_env, to_spill, dont_spill)) {
 349                 assert(0 && "Attempt to spill a node marked 'dont_spill'");
 350         }
 351
 352         /*
 353                 We switch on optimizations here to get CSE. This is needed as some backends
 354                 have some extra spill phases and we want to make use of those spills instead
 355                 of creating new ones.
 356         */
 357         save_optimization_state(&opt);
 358         set_optimize(1);
 359         spillinfo->spill = be_spill(env->arch_env, to_spill);
 360         restore_optimization_state(&opt);
 361         if (! sched_is_scheduled(spillinfo->spill)) {
 362                 DB((env->dbg, LEVEL_1, "add spill %+F after %+F\n", spillinfo->spill, to_spill));
 363                 sched_add_after_insn(to_spill, spillinfo->spill);
 364         }
 365         else {
 366                 DB((env->dbg, LEVEL_1, "re-using spill %+F after %+F\n", spillinfo->spill, to_spill));
 367         }
 368 }
 369
 370 static void spill_node(spill_env_t *env, spill_info_t *spillinfo);
 371
 372 /**
 373  * If the first usage of a Phi result would be out of memory
 374  * there is no sense in allocating a register for it.
 375  * Thus we spill it and all its operands to the same spill slot.
 376  * Therefore the phi/dataB becomes a phi/Memory
 377  *
 378  * @param senv      the spill environment
 379  * @param phi       the Phi node that should be spilled
 380  * @param ctx_irn   an user of the spilled node
 381  */
 382 static void spill_phi(spill_env_t *env, spill_info_t *spillinfo) {
 383         ir_node *phi = spillinfo->spilled_node;
 384         int i;
 385         int arity = get_irn_arity(phi);
 386         ir_node     *block    = get_nodes_block(phi);
 387         ir_node     **ins;
 388
 389         assert(is_Phi(phi));
 390
 391         DBG((env->dbg, LEVEL_1, "spilling Phi %+F:\n", phi));
 392         /* build a new PhiM */
 393         ins = alloca(sizeof(ir_node*) * arity);
 394         for(i = 0; i < arity; ++i) {
 395                 ins[i] = get_irg_bad(env->irg);
 396         }
 397         spillinfo->spill = new_r_Phi(env->irg, block, arity, ins, mode_M);
 398
 399         for(i = 0; i < arity; ++i) {
 400                 ir_node *arg = get_irn_n(phi, i);
 401                 spill_info_t *arg_info = get_spillinfo(env, arg);
 402
 403                 spill_node(env, arg_info);
 404
 405                 set_irn_n(spillinfo->spill, i, arg_info->spill);
 406         }
 407         DBG((env->dbg, LEVEL_1, "... done spilling Phi %+F\n", phi));
 408
 409         // rewire reloads from old_spill to phi
 410         if (spillinfo->old_spill != NULL) {
 411                 const ir_edge_t *edge, *next;
 412                 ir_node *old_spill = spillinfo->old_spill;
 413
 414                 DBG((env->dbg, LEVEL_1, "old spill found, rewiring reloads:\n"));
 415
 416                 foreach_out_edge_safe(old_spill, edge, next) {
 417                         ir_node *reload = get_edge_src_irn(edge);
 418                         int     pos     = get_edge_src_pos(edge);
 419
 420                         DBG((env->dbg, LEVEL_1, "\tset input %d of %+F to %+F\n", pos, reload, spillinfo->spill));
 421
 422                         assert(be_is_Reload(reload) || is_Phi(reload));
 423                         set_irn_n(reload, pos, spillinfo->spill);
 424                 }
 425                 DBG((env->dbg, LEVEL_1, "\tset input of %+F to BAD\n", old_spill));
 426                 set_irn_n(old_spill, be_pos_Spill_val, new_Bad());
 427                 //sched_remove(old_spill);
 428                 spillinfo->old_spill = NULL;
 429         }
 430 }
 431
 432 /**
 433  * Spill a node.
 434  *
 435  * @param senv      the spill environment
 436  * @param to_spill  the node that should be spilled
 437  */
 438 static void spill_node(spill_env_t *env, spill_info_t *spillinfo) {
 439         ir_node *to_spill;
 440
 441         // the node should be tagged for spilling already...
 442         if(spillinfo->spill != NULL)
 443                 return;
 444
 445         to_spill = spillinfo->spilled_node;
 446         assert(sched_is_scheduled(to_spill) && "Node to be spilled must be scheduled!");
 447         if (is_Phi(to_spill) && pset_find_ptr(env->mem_phis, spillinfo->spilled_node)) {
 448                 spill_phi(env, spillinfo);
 449         } else {
 450                 spill_irn(env, spillinfo);
 451         }
 452 }
 453
 454 /*
 455  *
 456  *  ____                      _            _       _ _
 457  * |  _ \ ___ _ __ ___   __ _| |_ ___ _ __(_) __ _| (_)_______
 458  * | |_) / _ \ '_ ` _ \ / _` | __/ _ \ '__| |/ _` | | |_  / _ \
 459  * |  _ <  __/ | | | | | (_| | ||  __/ |  | | (_| | | |/ /  __/
 460  * |_| \_\___|_| |_| |_|\__,_|\__\___|_|  |_|\__,_|_|_/___\___|
 461  *
 462  */
 463
 464 /**
 465  * Tests whether value @p arg is available before node @p reloader
 466  * @returns 1 if value is available, 0 otherwise
 467  */
 468 static int is_value_available(spill_env_t *env, ir_node *arg, ir_node *reloader) {
 469         if(is_Unknown(arg) || arg == new_NoMem())
 470                 return 1;
 471
 472         if(be_is_Spill(arg))
 473                 return 1;
 474
 475         if(arg == get_irg_frame(env->irg))
 476                 return 1;
 477
 478         // hack for now (happens when command should be inserted at end of block)
 479         if(is_Block(reloader)) {
 480                 return 0;
 481         }
 482
 483         /*
 484          * Ignore registers are always available
 485          */
 486         if(arch_irn_is(env->arch_env, arg, ignore)) {
 487                 return 1;
 488         }
 489
 490 #if 0
 491         /* the following test does not work while spilling,
 492          * because the liveness info is not adapted yet to the effects of the
 493          * additional spills/reloads.
 494          */
 495
 496         /* we want to remat before the insn reloader
 497          * thus an arguments is alive if
 498          *   - it interferes with the reloaders result
 499          *   - or it is (last-) used by reloader itself
 500          */
 501         if (values_interfere(env->birg->lv, reloader, arg)) {
 502                 return 1;
 503         }
 504
 505         arity = get_irn_arity(reloader);
 506         for (i = 0; i < arity; ++i) {
 507                 ir_node *rel_arg = get_irn_n(reloader, i);
 508                 if (rel_arg == arg)
 509                         return 1;
 510         }
 511 #endif
 512
 513         return 0;
 514 }
 515
 516 /**
 517  * Checks whether the node can principally be rematerialized
 518  */
 519 static int is_remat_node(spill_env_t *env, ir_node *node) {
 520         const arch_env_t *arch_env = env->arch_env;
 521
 522         assert(!be_is_Spill(node));
 523
 524         if(arch_irn_is(arch_env, node, rematerializable)) {
 525                 return 1;
 526         }
 527
 528         if(be_is_StackParam(node))
 529                 return 1;
 530
 531         return 0;
 532 }
 533
 534 /**
 535  * Check if a node is rematerializable. This tests for the following conditions:
 536  *
 537  * - The node itself is rematerializable
 538  * - All arguments of the node are available or also rematerialisable
 539  * - The costs for the rematerialisation operation is less or equal a limit
 540  *
 541  * Returns the costs needed for rematerialisation or something
 542  * > REMAT_COST_LIMIT if remat is not possible.
 543  */
 544 static int check_remat_conditions_costs(spill_env_t *env, ir_node *spilled, ir_node *reloader, int parentcosts) {
 545         int i, arity;
 546         int argremats;
 547         int costs = 0;
 548
 549         if(!is_remat_node(env, spilled))
 550                 return REMAT_COST_LIMIT;
 551
 552         if(be_is_Reload(spilled)) {
 553                 costs += 2;
 554         } else {
 555                 costs += arch_get_op_estimated_cost(env->arch_env, spilled);
 556         }
 557         if(parentcosts + costs >= REMAT_COST_LIMIT) {
 558                 return REMAT_COST_LIMIT;
 559         }
 560
 561         argremats = 0;
 562         for(i = 0, arity = get_irn_arity(spilled); i < arity; ++i) {
 563                 ir_node *arg = get_irn_n(spilled, i);
 564
 565                 if(is_value_available(env, arg, reloader))
 566                         continue;
 567
 568                 // we have to rematerialize the argument as well...
 569                 if(argremats >= 1) {
 570                         /* we only support rematerializing 1 argument at the moment,
 571                          * so that we don't have to care about register pressure
 572                          */
 573                         return REMAT_COST_LIMIT;
 574                 }
 575                 argremats++;
 576
 577                 costs += check_remat_conditions_costs(env, arg, reloader, parentcosts + costs);
 578                 if(parentcosts + costs >= REMAT_COST_LIMIT)
 579                         return REMAT_COST_LIMIT;
 580         }
 581
 582         return costs;
 583 }
 584
 585 static int check_remat_conditions(spill_env_t *env, ir_node *spilled, ir_node *reloader) {
 586         int costs = check_remat_conditions_costs(env, spilled, reloader, 0);
 587
 588         return costs < REMAT_COST_LIMIT;
 589 }
 590
 591 /**
 592  * Re-materialize a node.
 593  *
 594  * @param senv      the spill environment
 595  * @param spilled   the node that was spilled
 596  * @param reloader  a irn that requires a reload
 597  */
 598 static ir_node *do_remat(spill_env_t *env, ir_node *spilled, ir_node *reloader) {
 599         int i, arity;
 600         ir_node *res;
 601         ir_node *bl;
 602         ir_node **ins;
 603
 604         if(is_Block(reloader)) {
 605                 bl = reloader;
 606         } else {
 607                 bl = get_nodes_block(reloader);
 608         }
 609
 610         ins = alloca(get_irn_arity(spilled) * sizeof(ins[0]));
 611         for(i = 0, arity = get_irn_arity(spilled); i < arity; ++i) {
 612                 ir_node *arg = get_irn_n(spilled, i);
 613
 614                 if(is_value_available(env, arg, reloader)) {
 615                         ins[i] = arg;
 616                 } else {
 617                         ins[i] = do_remat(env, arg, reloader);
 618                 }
 619         }
 620
 621         /* create a copy of the node */
 622         res = new_ir_node(get_irn_dbg_info(spilled), env->irg, bl,
 623                 get_irn_op(spilled),
 624                 get_irn_mode(spilled),
 625                 get_irn_arity(spilled),
 626                 ins);
 627         copy_node_attr(spilled, res);
 628         new_backedge_info(res);
 629         sched_reset(res);
 630
 631         DBG((env->dbg, LEVEL_1, "Insert remat %+F of %+F before reloader %+F\n", res, spilled, reloader));
 632
 633         /* insert in schedule */
 634         sched_add_before(reloader, res);
 635
 636         return res;
 637 }
 638
 639 int be_get_reload_costs(spill_env_t *env, ir_node *to_spill, ir_node *before) {
 640         spill_info_t *spill_info;
 641
 642         if(be_do_remats) {
 643                 // is the node rematerializable?
 644                 int costs = check_remat_conditions_costs(env, to_spill, before, 0);
 645                 if(costs < REMAT_COST_LIMIT)
 646                         return costs;
 647         }
 648
 649         // do we already have a spill?
 650         spill_info = find_spillinfo(env, to_spill);
 651         if(spill_info != NULL && spill_info->spill != NULL)
 652                 return env->reload_cost;
 653
 654         return env->spill_cost + env->reload_cost;
 655 }
 656
 657 int be_get_reload_costs_on_edge(spill_env_t *env, ir_node *to_spill, ir_node *block, int pos) {
 658         ir_node *before = get_reload_insertion_point(block, pos);
 659         return be_get_reload_costs(env, to_spill, before);
 660 }
 661
 662 /*
 663  *  ___                     _     ____      _                 _
 664  * |_ _|_ __  ___  ___ _ __| |_  |  _ \ ___| | ___   __ _  __| |___
 665  *  | || '_ \/ __|/ _ \ '__| __| | |_) / _ \ |/ _ \ / _` |/ _` / __|
 666  *  | || | | \__ \  __/ |  | |_  |  _ <  __/ | (_) | (_| | (_| \__ \
 667  * |___|_| |_|___/\___|_|   \__| |_| \_\___|_|\___/ \__,_|\__,_|___/
 668  *
 669  */
 670
 671 void be_insert_spills_reloads(spill_env_t *env) {
 672         const arch_env_t *arch_env = env->arch_env;
 673         int              remats    = 0;
 674         int              reloads   = 0;
 675         int              spills    = 0;
 676         spill_info_t     *si;
 677
 678         /* process each spilled node */
 679         for (si = set_first(env->spills); si; si = set_next(env->spills)) {
 680                 reloader_t *rld;
 681                 ir_mode    *mode   = get_irn_mode(si->spilled_node);
 682                 pset       *values = pset_new_ptr(16);
 683
 684                 DBG((env->dbg, LEVEL_1, "\nhandling all reloaders of %+F:\n", si->spilled_node));
 685
 686                 /* go through all reloads for this spill */
 687                 for (rld = si->reloaders; rld; rld = rld->next) {
 688                         ir_node *new_val;
 689
 690                         if (rld->rematted_node != NULL) {
 691                                 new_val = rld->rematted_node;
 692                                 remats++;
 693                                 sched_add_before(rld->reloader, new_val);
 694                         }
 695                         else if (be_do_remats && rld->allow_remat && check_remat_conditions(env, si->spilled_node, rld->reloader)) {
 696                                 new_val = do_remat(env, si->spilled_node, rld->reloader);
 697                                 remats++;
 698                         }
 699                         else {
 700                                 /* make sure we have a spill */
 701                                 if (si->spill == NULL) {
 702                                         spill_node(env, si);
 703                                         spills++;
 704                                 }
 705
 706                                 /* create a reload */
 707                                 new_val = be_reload(arch_env, si->reload_cls, rld->reloader, mode, si->spill);
 708                                 reloads++;
 709                         }
 710
 711                         DBG((env->dbg, LEVEL_1, " %+F of %+F before %+F\n", new_val, si->spilled_node, rld->reloader));
 712                         pset_insert_ptr(values, new_val);
 713                 }
 714
 715                 if (pset_count(values) > 0) {
 716                         /* introduce copies, rewire the uses */
 717                         pset_insert_ptr(values, si->spilled_node);
 718                         be_ssa_constr_set_ignore(env->birg->dom_front, env->birg->lv, values, env->mem_phis);
 719                 }
 720
 721                 del_pset(values);
 722
 723                 si->reloaders = NULL;
 724         }
 725
 726 #ifdef FIRM_STATISTICS
 727         if (be_stat_ev_is_active()) {
 728                 be_stat_ev("spill_spills", spills);
 729                 be_stat_ev("spill_reloads", reloads);
 730                 be_stat_ev("spill_remats", remats);
 731         }
 732 #endif /* FIRM_STATISTICS */
 733
 734         be_remove_dead_nodes_from_schedule(env->irg);
 735         //be_liveness_recompute(env->birg->lv);
 736         be_invalidate_liveness(env->birg);
 737 }