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 "ident_t.h"
  18 #include "type_t.h"
  19 #include "entity_t.h"
  20 #include "debug.h"
  21 #include "irgwalk.h"
  22 #include "array.h"
  23 #include "pdeq.h"
  24 #include "unionfind.h"
  25 #include "execfreq.h"
  26
  27 #include "belive_t.h"
  28 #include "besched_t.h"
  29 #include "bespill.h"
  30 #include "belive_t.h"
  31 #include "benode_t.h"
  32 #include "bechordal_t.h"
  33 #include "bejavacoal.h"
  34
  35 /* This enables re-computation of values. Current state: Unfinished and buggy. */
  36 #undef BUGGY_REMAT
  37
  38 typedef struct _reloader_t reloader_t;
  39
  40 struct _reloader_t {
  41         reloader_t *next;
  42         ir_node *reloader;
  43 };
  44
  45 typedef struct _spill_info_t {
  46         ir_node *spilled_node;
  47         reloader_t *reloaders;
  48
  49         ir_node *spill;
  50 } spill_info_t;
  51
  52 struct _spill_env_t {
  53         const arch_register_class_t *cls;
  54         const be_chordal_env_t *chordal_env;
  55         struct obstack obst;
  56         set *spills;                            /**< all spill_info_t's, which must be placed */
  57         pset *mem_phis;                         /**< set of all special spilled phis. allocated and freed separately */
  58
  59         DEBUG_ONLY(firm_dbg_module_t *dbg;)
  60 };
  61
  62 /**
  63  * Compare two spill infos.
  64  */
  65 static int cmp_spillinfo(const void *x, const void *y, size_t size) {
  66         const spill_info_t *xx = x;
  67         const spill_info_t *yy = y;
  68         return xx->spilled_node != yy->spilled_node;
  69 }
  70
  71 /**
  72  * Returns spill info for a specific value (the value that is to be spilled)
  73  */
  74 static spill_info_t *get_spillinfo(const spill_env_t *env, ir_node *value) {
  75         spill_info_t info, *res;
  76         int hash = HASH_PTR(value);
  77
  78         info.spilled_node = value;
  79         res = set_find(env->spills, &info, sizeof(info), hash);
  80
  81         if (res == NULL) {
  82                 info.reloaders = NULL;
  83                 info.spill = NULL;
  84                 res = set_insert(env->spills, &info, sizeof(info), hash);
  85         }
  86
  87         return res;
  88 }
  89
  90 DEBUG_ONLY(
  91 /* Sets the debug module of a spill environment. */
  92 void be_set_spill_env_dbg_module(spill_env_t *env, firm_dbg_module_t *dbg) {
  93         env->dbg = dbg;
  94 }
  95 )
  96
  97 /* Creates a new spill environment. */
  98 spill_env_t *be_new_spill_env(const be_chordal_env_t *chordal_env) {
  99         spill_env_t *env        = xmalloc(sizeof(env[0]));
 100         env->spills                     = new_set(cmp_spillinfo, 1024);
 101         env->cls                        = chordal_env->cls;
 102         env->chordal_env        = chordal_env;
 103         env->mem_phis           = pset_new_ptr_default();
 104         obstack_init(&env->obst);
 105         return env;
 106 }
 107
 108 /* Deletes a spill environment. */
 109 void be_delete_spill_env(spill_env_t *env) {
 110         del_set(env->spills);
 111         del_pset(env->mem_phis);
 112         obstack_free(&env->obst, NULL);
 113         free(env);
 114 }
 115
 116 /**
 117  * Schedules a node after an instruction. (That is the place after all projs and phis
 118  * that are scheduled after the instruction)
 119  */
 120 static void sched_add_after_insn(ir_node *sched_after, ir_node *node) {
 121         ir_node *next = sched_next(sched_after);
 122         while(!sched_is_end(next)) {
 123                 if(!is_Proj(next) && !is_Phi(next))
 124                         break;
 125                 next = sched_next(next);
 126         }
 127
 128         if(sched_is_end(next)) {
 129                 next = sched_last(get_nodes_block(sched_after));
 130                 sched_add_after(next, node);
 131         } else {
 132                 sched_add_before(next, node);
 133         }
 134 }
 135
 136 /**
 137  * Creates a spill.
 138  *
 139  * @param senv      the spill environment
 140  * @param irn       the node that should be spilled
 141  * @param ctx_irn   an user of the spilled node
 142  *
 143  * @return a be_Spill node
 144  */
 145 static void spill_irn(spill_env_t *env, spill_info_t *spillinfo) {
 146         const be_main_env_t *mainenv = env->chordal_env->birg->main_env;
 147         ir_node *to_spill = spillinfo->spilled_node;
 148
 149         DBG((env->dbg, LEVEL_1, "%+F\n", to_spill));
 150
 151         /* Trying to spill an already spilled value, no need for a new spill
 152          * node then, we can simply connect to the same one for this reload
 153          */
 154         if(be_is_Reload(to_spill)) {
 155                 spillinfo->spill = get_irn_n(to_spill, be_pos_Reload_mem);
 156                 return;
 157         }
 158
 159         spillinfo->spill = be_spill(mainenv->arch_env, to_spill);
 160         sched_add_after_insn(to_spill, spillinfo->spill);
 161 }
 162
 163 static void spill_node(spill_env_t *env, spill_info_t *spillinfo);
 164
 165 /**
 166  * If the first usage of a Phi result would be out of memory
 167  * there is no sense in allocating a register for it.
 168  * Thus we spill it and all its operands to the same spill slot.
 169  * Therefore the phi/dataB becomes a phi/Memory
 170  *
 171  * @param senv      the spill environment
 172  * @param phi       the Phi node that should be spilled
 173  * @param ctx_irn   an user of the spilled node
 174  */
 175 static void spill_phi(spill_env_t *env, spill_info_t *spillinfo) {
 176         ir_node *phi = spillinfo->spilled_node;
 177         int i;
 178         int arity = get_irn_arity(phi);
 179         ir_node     *block    = get_nodes_block(phi);
 180         ir_node     **ins;
 181
 182         assert(is_Phi(phi));
 183
 184         /* build a new PhiM */
 185         ins = alloca(sizeof(ir_node*) * arity);
 186         for(i = 0; i < arity; ++i) {
 187                 ins[i] = get_irg_bad(env->chordal_env->irg);
 188         }
 189         spillinfo->spill = new_r_Phi(env->chordal_env->irg, block, arity, ins, mode_M);
 190
 191         for(i = 0; i < arity; ++i) {
 192                 ir_node *arg = get_irn_n(phi, i);
 193                 spill_info_t *arg_info = get_spillinfo(env, arg);
 194
 195                 spill_node(env, arg_info);
 196
 197                 set_irn_n(spillinfo->spill, i, arg_info->spill);
 198         }
 199 }
 200
 201 /**
 202  * Spill a node.
 203  *
 204  * @param senv      the spill environment
 205  * @param to_spill  the node that should be spilled
 206  */
 207 static void spill_node(spill_env_t *env, spill_info_t *spillinfo) {
 208         ir_node *to_spill;
 209
 210         // the node should be tagged for spilling already...
 211         if(spillinfo->spill != NULL)
 212                 return;
 213
 214         to_spill = spillinfo->spilled_node;
 215         if (is_Phi(to_spill) && pset_find_ptr(env->mem_phis, spillinfo->spilled_node)) {
 216                 spill_phi(env, spillinfo);
 217         } else {
 218                 spill_irn(env, spillinfo);
 219         }
 220 }
 221
 222 static INLINE ir_node *skip_projs(ir_node *node) {
 223         while(is_Proj(node)) {
 224                 node = sched_next(node);
 225                 assert(!sched_is_end(node));
 226         }
 227
 228         return node;
 229 }
 230
 231 #if 0
 232 /**
 233  * Searchs the schedule backwards until we reach the first use or def of a
 234  * value or a phi.
 235  * Returns the node after this node (so that you can do sched_add_before)
 236  */
 237 static ir_node *find_last_use_def(spill_env_t *env, ir_node *block, ir_node *value) {
 238         ir_node *node, *last;
 239
 240         last = NULL;
 241         sched_foreach_reverse(block, node) {
 242                 int i, arity;
 243
 244                 if(is_Phi(node)) {
 245                         return last;
 246                 }
 247                 if(value == node) {
 248                         return skip_projs(last);
 249                 }
 250                 for(i = 0, arity = get_irn_arity(node); i < arity; ++i) {
 251                         ir_node *arg = get_irn_n(node, i);
 252                         if(arg == value) {
 253                                 return skip_projs(last);
 254                         }
 255                 }
 256                 last = node;
 257         }
 258
 259         // simply return first node if no def or use found
 260         return sched_first(block);
 261 }
 262 #endif
 263
 264 #ifdef BUGGY_REMAT
 265
 266 /**
 267  * Check if a spilled node could be rematerialized.
 268  *
 269  * @param senv      the spill environment
 270  * @param spill     the Spill node
 271  * @param spilled   the node that was spilled
 272  * @param reloader  a irn that requires a reload
 273  */
 274 static int check_remat_conditions(spill_env_t *senv, ir_node *spilled, ir_node *reloader) {
 275         int pos, max;
 276
 277         /* check for 'normal' spill and general remat condition */
 278         if (!arch_irn_is(senv->chordal_env->birg->main_env->arch_env, spilled, rematerializable))
 279                 return 0;
 280
 281         /* check availability of original arguments */
 282         if (is_Block(reloader)) {
 283
 284                 /* we want to remat at the end of a block.
 285                  * thus all arguments must be alive at the end of the block
 286                  */
 287                 for (pos=0, max=get_irn_arity(spilled); pos<max; ++pos) {
 288                         ir_node *arg = get_irn_n(spilled, pos);
 289                         if (!is_live_end(reloader, arg))
 290                                 return 0;
 291                 }
 292
 293         } else {
 294
 295                 /* we want to remat before the insn reloader
 296                  * thus an arguments is alive if
 297                  *   - it interferes with the reloaders result
 298                  * or
 299                  *   - or it is (last-) used by reloader itself
 300                  */
 301                 for (pos=0, max=get_irn_arity(spilled); pos<max; ++pos) {
 302                         ir_node *arg = get_irn_n(spilled, pos);
 303                         int i, m;
 304
 305                         if (values_interfere(reloader, arg))
 306                                 goto is_alive;
 307
 308                         for (i=0, m=get_irn_arity(reloader); i<m; ++i) {
 309                                 ir_node *rel_arg = get_irn_n(reloader, i);
 310                                 if (rel_arg == arg)
 311                                         goto is_alive;
 312                         }
 313
 314                         /* arg is not alive before reloader */
 315                         return 0;
 316
 317 is_alive:       ;
 318
 319                 }
 320
 321         }
 322
 323         return 1;
 324 }
 325
 326 #else /* BUGGY_REMAT */
 327
 328 /**
 329  * A very simple rematerialization checker.
 330  *
 331  * @param senv      the spill environment
 332  * @param spill     the Spill node
 333  * @param spilled   the node that was spilled
 334  * @param reloader  a irn that requires a reload
 335  */
 336 static int check_remat_conditions(spill_env_t *senv, ir_node *spilled, ir_node *reloader) {
 337         const arch_env_t *aenv = senv->chordal_env->birg->main_env->arch_env;
 338
 339         return get_irn_arity(spilled) == 0 &&
 340                    arch_irn_is(aenv, spilled, rematerializable);
 341 }
 342
 343 #endif /* BUGGY_REMAT */
 344
 345 /**
 346  * Re-materialize a node.
 347  *
 348  * @param senv      the spill environment
 349  * @param spilled   the node that was spilled
 350  * @param reloader  a irn that requires a reload
 351  */
 352 static ir_node *do_remat(spill_env_t *senv, ir_node *spilled, ir_node *reloader) {
 353         ir_node *res;
 354         ir_node *bl = (is_Block(reloader)) ? reloader : get_nodes_block(reloader);
 355
 356         /* recompute the value */
 357         res = new_ir_node(get_irn_dbg_info(spilled), senv->chordal_env->irg, bl,
 358                 get_irn_op(spilled),
 359                 get_irn_mode(spilled),
 360                 get_irn_arity(spilled),
 361                 get_irn_in(spilled) + 1);
 362         copy_node_attr(spilled, res);
 363
 364         DBG((senv->dbg, LEVEL_1, "Insert remat %+F before reloader %+F\n", res, reloader));
 365
 366         /* insert in schedule */
 367         if (is_Block(reloader)) {
 368                 ir_node *insert = sched_skip(reloader, 0, sched_skip_cf_predicator, (void *) senv->chordal_env->birg->main_env->arch_env);
 369                 sched_add_after(insert, res);
 370         } else {
 371                 sched_add_before(reloader, res);
 372         }
 373
 374         return res;
 375 }
 376
 377 void be_spill_phi(spill_env_t *env, ir_node *node) {
 378         int i, arity;
 379
 380         assert(is_Phi(node));
 381
 382         pset_insert_ptr(env->mem_phis, node);
 383
 384         // create spillinfos for the phi arguments
 385         get_spillinfo(env, node);
 386         for(i = 0, arity = get_irn_arity(node); i < arity; ++i) {
 387                 ir_node *arg = get_irn_n(node, i);
 388                 get_spillinfo(env, arg);
 389         }
 390 }
 391
 392 void be_insert_spills_reloads(spill_env_t *env) {
 393         const arch_env_t *arch_env = env->chordal_env->birg->main_env->arch_env;
 394         spill_info_t *si;
 395
 396         /* process each spilled node */
 397         DBG((env->dbg, LEVEL_1, "Insert spills and reloads:\n"));
 398         for(si = set_first(env->spills); si; si = set_next(env->spills)) {
 399                 reloader_t *rld;
 400                 ir_mode *mode = get_irn_mode(si->spilled_node);
 401                 pset *values = pset_new_ptr(16);
 402
 403                 /* go through all reloads for this spill */
 404                 for(rld = si->reloaders; rld; rld = rld->next) {
 405                         ir_node *new_val;
 406
 407                         if (check_remat_conditions(env, si->spilled_node, rld->reloader)) {
 408                                 new_val = do_remat(env, si->spilled_node, rld->reloader);
 409                         } else {
 410                                 /* make sure we have a spill */
 411                                 spill_node(env, si);
 412
 413                                 /* do a reload */
 414                                 new_val = be_reload(arch_env, env->cls, rld->reloader, mode, si->spill);
 415                         }
 416
 417                         DBG((env->dbg, LEVEL_1, " %+F of %+F before %+F\n", new_val, si->spilled_node, rld->reloader));
 418                         pset_insert_ptr(values, new_val);
 419                 }
 420
 421                 if(pset_count(values) > 0) {
 422                         /* introduce copies, rewire the uses */
 423                         pset_insert_ptr(values, si->spilled_node);
 424                         be_ssa_constr_set_ignore(env->chordal_env->dom_front, env->chordal_env->lv, values, env->mem_phis);
 425                 }
 426
 427                 del_pset(values);
 428         }
 429
 430         // reloads are placed now, but we might reuse the spill environment for further spilling decisions
 431         del_set(env->spills);
 432         env->spills = new_set(cmp_spillinfo, 1024);
 433 }
 434
 435 void be_add_reload(spill_env_t *env, ir_node *to_spill, ir_node *before) {
 436         spill_info_t *info;
 437         reloader_t *rel;
 438
 439         assert(sched_is_scheduled(before));
 440         assert(arch_irn_consider_in_reg_alloc(env->chordal_env->birg->main_env->arch_env, env->cls, to_spill));
 441
 442         info = get_spillinfo(env, to_spill);
 443
 444         if(is_Phi(to_spill)) {
 445                 int i, arity;
 446                 // create spillinfos for the phi arguments
 447                 for(i = 0, arity = get_irn_arity(to_spill); i < arity; ++i) {
 448                         ir_node *arg = get_irn_n(to_spill, i);
 449                         get_spillinfo(env, arg);
 450                 }
 451         }
 452
 453         rel           = obstack_alloc(&env->obst, sizeof(rel[0]));
 454         rel->reloader = before;
 455         rel->next     = info->reloaders;
 456         info->reloaders = rel;
 457         be_liveness_add_missing(env->chordal_env->lv);
 458 }
 459
 460 void be_add_reload_on_edge(spill_env_t *env, ir_node *to_spill, ir_node *block, int pos) {
 461         ir_node *predblock, *last;
 462
 463         /* simply add the reload to the beginning of the block if we only have 1 predecessor
 464          * (we don't need to check for phis as there can't be any in a block with only 1 pred)
 465          */
 466         if(get_Block_n_cfgpreds(block) == 1) {
 467                 assert(!is_Phi(sched_first(block)));
 468                 be_add_reload(env, to_spill, sched_first(block));
 469                 return;
 470         }
 471
 472         /* We have to reload the value in pred-block */
 473         predblock = get_Block_cfgpred_block(block, pos);
 474         last = sched_last(predblock);
 475
 476         /* we might have projs and keepanys behind the jump... */
 477         while(is_Proj(last) || be_is_Keep(last)) {
 478                 last = sched_prev(last);
 479                 assert(!sched_is_end(last));
 480         }
 481         assert(is_cfop(last));
 482
 483         // add the reload before the (cond-)jump
 484         be_add_reload(env, to_spill, last);
 485 }