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