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

   1 /**
   2  * Author:      Daniel Grund, Sebastian Hack
   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
  24 #include "belive_t.h"
  25 #include "besched_t.h"
  26 #include "bespill.h"
  27 #include "benode_t.h"
  28 #include "bechordal_t.h"
  29
  30 #undef REMAT
  31 /* This enables re-computation of values. Current state: Unfinished and buggy. */
  32 #undef BUGGY_REMAT
  33
  34 typedef struct _reloader_t reloader_t;
  35 typedef struct _spill_info_t spill_info_t;
  36
  37 struct _reloader_t {
  38         reloader_t *next;
  39         ir_node *reloader;
  40 };
  41
  42 struct _spill_info_t {
  43         ir_node *spilled_node;
  44         reloader_t *reloaders;
  45 };
  46
  47 typedef struct _spill_ctx_t {
  48         ir_node *spilled;  /**< The spilled node. */
  49         ir_node *user;     /**< The node this spill is for. */
  50         ir_node *spill;    /**< The spill itself. */
  51 } spill_ctx_t;
  52
  53 struct _spill_env_t {
  54         const arch_register_class_t *cls;
  55         const be_chordal_env_t *chordal_env;
  56         struct obstack obst;
  57         set *spill_ctxs;
  58         set *spills;                            /**< all spill_info_t's, which must be placed */
  59         pset *mem_phis;                         /**< set of all special spilled phis. allocated and freed separately */
  60         decide_irn_t is_mem_phi;        /**< callback func to decide if a phi needs special spilling */
  61         void *data;                                     /**< data passed to all callbacks */
  62         DEBUG_ONLY(firm_dbg_module_t *dbg;)
  63 };
  64
  65 static int cmp_spillctx(const void *a, const void *b, size_t n) {
  66         const spill_ctx_t *p = a;
  67         const spill_ctx_t *q = b;
  68         return !(p->user == q->user && p->spilled == q->spilled);
  69 }
  70
  71 static int cmp_spillinfo(const void *x, const void *y, size_t size) {
  72         const spill_info_t *xx = x;
  73         const spill_info_t *yy = y;
  74         return ! (xx->spilled_node == yy->spilled_node);
  75 }
  76
  77 DEBUG_ONLY(
  78 void be_set_spill_env_dbg_module(spill_env_t *env, firm_dbg_module_t *dbg) {
  79         env->dbg = dbg;
  80 }
  81 )
  82
  83 spill_env_t *be_new_spill_env(const be_chordal_env_t *chordal_env, decide_irn_t is_mem_phi, void *data) {
  84         spill_env_t *env = xmalloc(sizeof(env[0]));
  85         env->spill_ctxs  = new_set(cmp_spillctx, 1024);
  86         env->spills      = new_set(cmp_spillinfo, 1024);
  87         env->cls         = chordal_env->cls;
  88         env->is_mem_phi  = is_mem_phi;
  89         env->data        = data;
  90         env->chordal_env = chordal_env;
  91         obstack_init(&env->obst);
  92         return env;
  93 }
  94
  95 void be_delete_spill_env(spill_env_t *senv) {
  96         del_set(senv->spill_ctxs);
  97         del_set(senv->spills);
  98         obstack_free(&senv->obst, NULL);
  99         free(senv);
 100 }
 101
 102 static spill_ctx_t *be_get_spill_ctx(set *sc, ir_node *to_spill, ir_node *ctx_irn) {
 103         spill_ctx_t templ;
 104
 105         templ.spilled = to_spill;
 106         templ.user    = ctx_irn;
 107         templ.spill   = NULL;
 108
 109         return set_insert(sc, &templ, sizeof(templ), HASH_COMBINE(HASH_PTR(to_spill), HASH_PTR(ctx_irn)));
 110 }
 111
 112 static ir_node *be_spill_irn(spill_env_t *senv, ir_node *irn, ir_node *ctx_irn) {
 113         spill_ctx_t *ctx;
 114         DBG((senv->dbg, LEVEL_1, "%+F in ctx %+F\n", irn, ctx_irn));
 115
 116         ctx = be_get_spill_ctx(senv->spill_ctxs, irn, ctx_irn);
 117         if(!ctx->spill) {
 118                 const be_main_env_t *env = senv->chordal_env->birg->main_env;
 119                 ctx->spill = be_spill(env->arch_env, irn, ctx_irn);
 120         }
 121
 122         return ctx->spill;
 123 }
 124
 125 /**
 126  * If the first usage of a phi result would be out of memory
 127  * there is no sense in allocating a register for it.
 128  * Thus we spill it and all its operands to the same spill slot.
 129  * Therefore the phi/dataB becomes a phi/Memory
 130  */
 131 static ir_node *be_spill_phi(spill_env_t *senv, ir_node *phi, ir_node *ctx_irn) {
 132         int i, n = get_irn_arity(phi);
 133         ir_node **ins, *bl = get_nodes_block(phi);
 134         ir_graph *irg = senv->chordal_env->irg;
 135         spill_ctx_t *ctx;
 136
 137         assert(is_Phi(phi));
 138         DBG((senv->dbg, LEVEL_1, "%+F in ctx %+F\n", phi, ctx_irn));
 139
 140         /* search an existing spill for this context */
 141         ctx = be_get_spill_ctx(senv->spill_ctxs, phi, ctx_irn);
 142
 143         /* if not found spill the phi */
 144         if(!ctx->spill) {
 145                 /* build a new PhiM with dummy in-array */
 146                 NEW_ARR_A(ir_node *, ins, n);
 147                 for(i=0; i<n; ++i)
 148                         ins[i] = new_r_Unknown(irg, mode_M);
 149                 ctx->spill = new_r_Phi(senv->chordal_env->irg, bl, n, ins, mode_M);
 150
 151                 /* re-wire the phiM */
 152                 for(i=0; i<n; ++i) {
 153                         ir_node *arg = get_irn_n(phi, i);
 154                         ir_node *sub_res;
 155
 156                         if(is_Phi(arg) && pset_find_ptr(senv->mem_phis, arg))
 157                                 sub_res = be_spill_phi(senv, arg, ctx_irn);
 158                         else
 159                                 sub_res = be_spill_irn(senv, arg, ctx_irn);
 160
 161                         set_irn_n(ctx->spill, i, sub_res);
 162                 }
 163         }
 164         return ctx->spill;
 165 }
 166
 167 static ir_node *be_spill_node(spill_env_t *senv, ir_node *to_spill) {
 168         ir_node *res;
 169         if (pset_find_ptr(senv->mem_phis, to_spill))
 170                 res = be_spill_phi(senv, to_spill, to_spill);
 171         else
 172                 res = be_spill_irn(senv, to_spill, to_spill);
 173
 174         return res;
 175 }
 176
 177 static void phi_walker(ir_node *irn, void *env) {
 178         spill_env_t *senv = env;
 179         const arch_env_t *arch = senv->chordal_env->birg->main_env->arch_env;
 180
 181         if (is_Phi(irn) && arch_irn_has_reg_class(arch, irn, 0, senv->cls)
 182                         && senv->is_mem_phi(irn, senv->data)) {
 183                 DBG((senv->dbg, LEVEL_1, "  %+F\n", irn));
 184                 pset_insert_ptr(senv->mem_phis, irn);
 185         }
 186 }
 187
 188 #ifdef REMAT
 189
 190 #ifdef BUGGY_REMAT
 191
 192 static int check_remat_conditions(spill_env_t *senv, ir_node *spill, ir_node *spilled, ir_node *reloader) {
 193         int pos, max;
 194
 195         /* check for 'normal' spill and general remat condition */
 196         if (!be_is_Spill(spill) || !arch_irn_is(senv->chordal_env->birg->main_env->arch_env, spilled, rematerializable))
 197                 return 0;
 198
 199         /* check availability of original arguments */
 200         if (is_Block(reloader)) {
 201
 202                 /* we want to remat at the end of a block.
 203                  * thus all arguments must be alive at the end of the block
 204                  */
 205                 for (pos=0, max=get_irn_arity(spilled); pos<max; ++pos) {
 206                         ir_node *arg = get_irn_n(spilled, pos);
 207                         if (!is_live_end(reloader, arg))
 208                                 return 0;
 209                 }
 210
 211         } else {
 212
 213                 /* we want to remat before the insn reloader
 214                  * thus an arguments is alive if
 215                  *   - it interferes with the reloaders result
 216                  * or
 217                  *   - or it is (last-) used by reloader itself
 218                  */
 219                 for (pos=0, max=get_irn_arity(spilled); pos<max; ++pos) {
 220                         ir_node *arg = get_irn_n(spilled, pos);
 221                         int i, m;
 222
 223                         if (values_interfere(reloader, arg))
 224                                 goto is_alive;
 225
 226                         for (i=0, m=get_irn_arity(reloader); i<m; ++i) {
 227                                 ir_node *rel_arg = get_irn_n(reloader, i);
 228                                 if (rel_arg == arg)
 229                                         goto is_alive;
 230                         }
 231
 232                         /* arg is not alive before reloader */
 233                         return 0;
 234
 235 is_alive:       ;
 236
 237                 }
 238
 239         }
 240
 241         return 1;
 242 }
 243
 244 #else /* BUGGY_REMAT */
 245
 246 static int check_remat_conditions(spill_env_t *senv, ir_node *spill, ir_node *spilled, ir_node *reloader) {
 247         const arch_env_t *aenv = senv->chordal_env->birg->main_env->arch_env;
 248
 249         return get_irn_arity(spilled) == 0 &&
 250                    be_is_Spill(spill) &&
 251                    arch_irn_is(aenv, spilled, rematerializable);
 252 }
 253
 254 #endif /* BUGGY_REMAT */
 255
 256 static ir_node *do_remat(spill_env_t *senv, ir_node *spilled, ir_node *reloader) {
 257         ir_node *res;
 258         ir_node *bl = (is_Block(reloader)) ? reloader : get_nodes_block(reloader);
 259
 260         /* recompute the value */
 261         res = new_ir_node(get_irn_dbg_info(spilled), senv->chordal_env->irg, bl,
 262                 get_irn_op(spilled),
 263                 get_irn_mode(spilled),
 264                 get_irn_arity(spilled),
 265                 get_irn_in(spilled));
 266         copy_node_attr(spilled, res);
 267
 268         DBG((senv->dbg, LEVEL_1, "Insert remat %+F before reloader %+F\n", res, reloader));
 269
 270         /* insert in schedule */
 271         if (is_Block(reloader)) {
 272                 ir_node *insert = sched_skip(reloader, 0, sched_skip_cf_predicator, (void *) senv->chordal_env->birg->main_env->arch_env);
 273                 sched_add_after(insert, res);
 274         } else {
 275                 sched_add_before(reloader, res);
 276         }
 277
 278         return res;
 279 }
 280
 281 #endif
 282
 283 void be_insert_spills_reloads(spill_env_t *senv, pset *reload_set) {
 284         const arch_env_t *aenv = senv->chordal_env->birg->main_env->arch_env;
 285         ir_graph *irg          = senv->chordal_env->irg;
 286         ir_node *irn;
 287         spill_info_t *si;
 288
 289         /* get all special spilled phis */
 290         DBG((senv->dbg, LEVEL_1, "Mem-phis:\n"));
 291         senv->mem_phis = pset_new_ptr_default();
 292         irg_walk_graph(senv->chordal_env->irg, phi_walker, NULL, senv);
 293
 294         /* Add reloads for mem_phis */
 295         /* BETTER: These reloads (1) should only be inserted, if they are really needed */
 296         DBG((senv->dbg, LEVEL_1, "Reloads for mem-phis:\n"));
 297         for(irn = pset_first(senv->mem_phis); irn; irn = pset_next(senv->mem_phis)) {
 298                 const ir_edge_t *e;
 299                 DBG((senv->dbg, LEVEL_1, " Mem-phi %+F\n", irn));
 300                 foreach_out_edge(irn, e) {
 301                         ir_node *user = e->src;
 302                         if (is_Phi(user) && !pset_find_ptr(senv->mem_phis, user)) {
 303                                         ir_node *use_bl = get_nodes_block(user);
 304                                         DBG((senv->dbg, LEVEL_1, " non-mem-phi user %+F\n", user));
 305                                         be_add_reload_on_edge(senv, irn, use_bl, e->pos); /* (1) */
 306                         }
 307                 }
 308         }
 309
 310         /* process each spilled node */
 311         DBG((senv->dbg, LEVEL_1, "Insert spills and reloads:\n"));
 312         for(si = set_first(senv->spills); si; si = set_next(senv->spills)) {
 313                 reloader_t *rld;
 314                 ir_mode *mode = get_irn_mode(si->spilled_node);
 315                 pset *values = pset_new_ptr(16);
 316
 317                 /* go through all reloads for this spill */
 318                 for(rld = si->reloaders; rld; rld = rld->next) {
 319                         ir_node *new_val;
 320
 321                         /* the spill for this reloader */
 322                         ir_node *spill   = be_spill_node(senv, si->spilled_node);
 323
 324 #ifdef REMAT
 325                         if (check_remat_conditions(senv, spill, si->spilled_node, rld->reloader))
 326                                 new_val = do_remat(senv, si->spilled_node, rld->reloader);
 327                         else
 328 #endif
 329                                 /* do a reload */
 330                                 new_val = be_reload(aenv, senv->cls, rld->reloader, mode, spill);
 331
 332                         DBG((senv->dbg, LEVEL_1, " %+F of %+F before %+F\n", new_val, si->spilled_node, rld->reloader));
 333                         pset_insert_ptr(values, new_val);
 334                         if(reload_set)
 335                                 pset_insert_ptr(reload_set, new_val);
 336                 }
 337
 338                 /* introduce copies, rewire the uses */
 339                 assert(pset_count(values) > 0 && "???");
 340                 pset_insert_ptr(values, si->spilled_node);
 341                 be_ssa_constr_set_ignore(senv->chordal_env->dom_front, values, senv->mem_phis);
 342
 343                 del_pset(values);
 344         }
 345
 346         for(irn = pset_first(senv->mem_phis); irn; irn = pset_next(senv->mem_phis)) {
 347                 int i, n;
 348                 for(i = 0, n = get_irn_arity(irn); i < n; ++i)
 349                         set_irn_n(irn, i, new_r_Bad(senv->chordal_env->irg));
 350                 sched_remove(irn);
 351         }
 352
 353         del_pset(senv->mem_phis);
 354 }
 355
 356 void be_add_reload(spill_env_t *senv, ir_node *to_spill, ir_node *before) {
 357         spill_info_t templ, *res;
 358         reloader_t *rel;
 359
 360         templ.spilled_node = to_spill;
 361         templ.reloaders    = NULL;
 362         res = set_insert(senv->spills, &templ, sizeof(templ), HASH_PTR(to_spill));
 363
 364         rel           = obstack_alloc(&senv->obst, sizeof(rel[0]));
 365         rel->reloader = before;
 366         rel->next     = res->reloaders;
 367         res->reloaders = rel;
 368 }
 369
 370 void be_add_reload_on_edge(spill_env_t *senv, ir_node *to_spill, ir_node *bl, int pos) {
 371         ir_node *insert_bl = get_irn_arity(bl) == 1 ? sched_first(bl) : get_Block_cfgpred_block(bl, pos);
 372         be_add_reload(senv, to_spill, insert_bl);
 373 }
 374
 375
 376
 377 /****************************************
 378
 379         SPILL SLOT MANAGEMENT AND OPTS
 380
 381 ****************************************/
 382
 383 typedef struct _spill_slot_t {
 384         unsigned size;
 385         unsigned align;
 386         pset *members;
 387         ir_mode *largest_mode;  /* the mode of all members with largest size */
 388 } spill_slot_t;
 389
 390 typedef struct _ss_env_t {
 391         struct obstack ob;
 392         be_chordal_env_t *cenv;
 393         pmap *slots;            /* maps spill_contexts to spill_slots */
 394         pmap *types;    /* maps modes to types */
 395         DEBUG_ONLY(firm_dbg_module_t *dbg;)
 396 } ss_env_t;
 397
 398
 399 /**
 400  * Walker: compute the spill slots
 401  */
 402 static void compute_spill_slots_walker(ir_node *spill, void *env) {
 403         ss_env_t *ssenv = env;
 404         ir_node *ctx;
 405         pmap_entry *entry;
 406         spill_slot_t *ss;
 407
 408         if (!be_is_Spill(spill))
 409                 return;
 410
 411         /* check, if this spill is for a context already known */
 412         ctx = be_get_Spill_context(spill);
 413         entry = pmap_find(ssenv->slots, ctx);
 414
 415         if (!entry) {
 416                 struct _arch_env_t *arch_env     = ssenv->cenv->birg->main_env->arch_env;
 417                 const arch_register_class_t *cls = arch_get_irn_reg_class(arch_env, spill, be_pos_Spill_val);
 418                 ir_mode *largest_mode            = arch_register_class_mode(cls);
 419
 420                 /* this is a new spill context */
 421                 ss = obstack_alloc(&ssenv->ob, sizeof(*ss));
 422                 ss->members      = pset_new_ptr(8);
 423                 ss->largest_mode = largest_mode;
 424                 ss->size         = get_mode_size_bytes(ss->largest_mode);
 425                 ss->align        = arch_isa_get_reg_class_alignment(arch_env->isa, cls);
 426                 pmap_insert(ssenv->slots, ctx, ss);
 427         } else {
 428                 /* values with the same spill_ctx must go into the same spill slot */
 429                 ss = entry->value;
 430
 431 #ifndef NDEBUG
 432                 /* ugly mega assert :-) */
 433                 {
 434                         ir_node *irn;
 435                         struct _arch_env_t *arch_env     = ssenv->cenv->birg->main_env->arch_env;
 436                         const arch_register_class_t *cls = arch_get_irn_reg_class(arch_env, spill, be_pos_Spill_val);
 437                         int size = get_mode_size_bytes(arch_register_class_mode(cls));
 438                         assert(ss->size == size && "Different sizes for the same spill slot are not allowed.");
 439                         for (irn = pset_first(ss->members); irn; irn = pset_next(ss->members)) {
 440                                 /* use values_interfere here, because it uses the dominance check,
 441                                          which does work for values in memory */
 442                                 assert(!values_interfere(spill, irn) && "Spills for the same spill slot must not interfere!");
 443                         }
 444                 }
 445 #endif /* NDEBUG */
 446         }
 447
 448         pset_insert_ptr(ss->members, spill);
 449 }
 450
 451 /**
 452  * qsort compare function, sort spill slots by size.
 453  */
 454 static int ss_sorter(const void *v1, const void *v2) {
 455         const spill_slot_t *ss1 = v1;
 456         const spill_slot_t *ss2 = v2;
 457         return ((int) ss2->size) - ((int) ss1->size);
 458 }
 459
 460
 461 /**
 462  * This function should optimize the spill slots.
 463  *  - Coalescing of multiple slots
 464  *  - Ordering the slots
 465  *
 466  * Input slots are in @p ssenv->slots
 467  * @p size The count of initial spill slots in @p ssenv->slots
 468  *         This also is the size of the preallocated array @p ass
 469  *
 470  * @return An array of spill slots @p ass in specific order
 471  **/
 472 static void optimize_slots(ss_env_t *ssenv, int size, spill_slot_t **ass) {
 473         int i, o, used_slots;
 474         pmap_entry *entr;
 475
 476         i=0;
 477         pmap_foreach(ssenv->slots, entr)
 478                 ass[i++] = entr->value;
 479
 480         /* Sort the array to minimize fragmentation and cache footprint.
 481            Large slots come first */
 482         qsort(ass, size, sizeof(ass[0]), ss_sorter);
 483
 484         /* For each spill slot:
 485                 - assign a new offset to this slot
 486             - xor find another slot to coalesce with */
 487         used_slots = 0;
 488         for (i=0; i<size; ++i) { /* for each spill slot */
 489                 ir_node *n1;
 490                 int tgt_slot = -1;
 491
 492                 DBG((ssenv->dbg, LEVEL_1, "Spill slot %d members:\n", i));
 493                 for(n1 = pset_first(ass[i]->members); n1; n1 = pset_next(ass[i]->members))
 494                         DBG((ssenv->dbg, LEVEL_1, "  %+F\n", n1));
 495
 496
 497                 for (o=0; o < used_slots && tgt_slot == -1; ++o) { /* for each offset-assigned spill slot */
 498                         /* check inter-slot-pairs for interference */
 499                         ir_node *n2;
 500                         for(n1 = pset_first(ass[i]->members); n1; n1 = pset_next(ass[i]->members))
 501                                 for(n2 = pset_first(ass[o]->members); n2; n2 = pset_next(ass[o]->members))
 502                                         if(values_interfere(n1, n2)) {
 503                                                 pset_break(ass[i]->members);
 504                                                 pset_break(ass[o]->members);
 505                                                 DBG((ssenv->dbg, LEVEL_1, "    Interf %+F -- %+F\n", n1, n2));
 506                                                 goto interf_detected;
 507                                         }
 508
 509                         /* if we are here, there is no interference between ass[i] and ass[o] */
 510                         tgt_slot = o;
 511
 512 interf_detected: /*nothing*/ ;
 513                 }
 514
 515                 /* now the members of ass[i] join the members of ass[tgt_slot] */
 516
 517                 /* do we need a new slot? */
 518                 if (tgt_slot == -1) {
 519                         tgt_slot = used_slots;
 520                         used_slots++;
 521
 522                         /* init slot */
 523                         if (tgt_slot != i) {
 524                                 ass[tgt_slot]->size = ass[i]->size;
 525                                 del_pset(ass[tgt_slot]->members);
 526                                 ass[tgt_slot]->members = pset_new_ptr(8);
 527                         }
 528                 }
 529
 530                 /* copy the members to the target pset */
 531                 /* NOTE: If src and tgt pset are the same, inserting while iterating is not allowed */
 532                 if (tgt_slot != i)
 533                         for(n1 = pset_first(ass[i]->members); n1; n1 = pset_next(ass[i]->members))
 534                                         pset_insert_ptr(ass[tgt_slot]->members, n1);
 535         }
 536 }
 537
 538 #define ALIGN_SPILL_AREA 16
 539 #define pset_foreach(pset, elm)  for(elm=pset_first(pset); elm; elm=pset_next(pset))
 540
 541 /**
 542  * Returns a spill type for a mode. Keep them in a map to reduce
 543  * the number of types.
 544  *
 545  * @param types  a map containing all created types
 546  * @param ss     the spill slot
 547  *
 548  * Note that type types should are identical for every mode.
 549  * This rule might break if two different register classes return the same
 550  * mode but different alignments.
 551  */
 552 static ir_type *get_spill_type(pmap *types, spill_slot_t *ss) {
 553   pmap_entry *e = pmap_find(types, ss->largest_mode);
 554   ir_type *res;
 555
 556   if (! e) {
 557                 char buf[64];
 558     snprintf(buf, sizeof(buf), "spill_slot_type_%s", get_mode_name(ss->largest_mode));
 559     res = new_type_primitive(new_id_from_str(buf), ss->largest_mode);
 560                 set_type_alignment_bytes(res, ss->align);
 561     pmap_insert(types, ss->largest_mode, res);
 562   }
 563   else {
 564     res = e->value;
 565                 assert(get_type_alignment_bytes(res) == (int)ss->align);
 566         }
 567   return res;
 568 }
 569
 570 /**
 571  * Create spill slot entities on the frame type.
 572  *
 573  * @param ssenv   the spill environment
 574  * @param n       number of spill slots
 575  * @param ss      array of spill slots
 576  */
 577 static void assign_entities(ss_env_t *ssenv, int n_slots, spill_slot_t *ss[]) {
 578         int i, offset, frame_align;
 579         ir_type *frame = get_irg_frame_type(ssenv->cenv->irg);
 580
 581         /* aligning by increasing frame size */
 582         offset = get_type_size_bits(frame) / 8;
 583         offset = round_up2(offset, ALIGN_SPILL_AREA);
 584         set_type_size_bytes(frame, -1);
 585
 586         /* create entities and assign offsets according to size and alignment*/
 587         for (i = 0; i < n_slots; ++i) {
 588                 char buf[64];
 589                 ident *name;
 590                 entity *spill_ent;
 591                 ir_node *irn;
 592
 593                 /* build entity */
 594                 snprintf(buf, sizeof(buf), "spill_slot_%d", i);
 595                 name = new_id_from_str(buf);
 596
 597                 spill_ent = new_entity(frame, name, get_spill_type(ssenv->types, ss[i]));
 598
 599                 /* align */
 600                 offset = round_up2(offset, ss[i]->align);
 601                 /* set */
 602                 set_entity_offset_bytes(spill_ent, offset);
 603                 /* next possible offset */
 604                 offset += round_up2(ss[i]->size, ss[i]->align);
 605
 606                 pset_foreach(ss[i]->members, irn)
 607                         be_set_Spill_entity(irn, spill_ent);
 608         }
 609
 610         /* set final size of stack frame */
 611         frame_align = get_type_alignment_bytes(frame);
 612         set_type_size_bytes(frame, round_up2(offset, frame_align));
 613 }
 614
 615 void be_compute_spill_offsets(be_chordal_env_t *cenv) {
 616         ss_env_t ssenv;
 617         spill_slot_t **ss;
 618         int ss_size;
 619         pmap_entry *pme;
 620
 621         obstack_init(&ssenv.ob);
 622         ssenv.cenv  = cenv;
 623         ssenv.slots = pmap_create();
 624         ssenv.types = pmap_create();
 625         FIRM_DBG_REGISTER(ssenv.dbg, "ir.be.spillslots");
 626
 627         /* Get initial spill slots */
 628         irg_walk_graph(cenv->irg, NULL, compute_spill_slots_walker, &ssenv);
 629
 630         /* Build an empty array for optimized spill slots */
 631         ss_size = pmap_count(ssenv.slots);
 632         ss = obstack_alloc(&ssenv.ob, ss_size * sizeof(*ss));
 633         optimize_slots(&ssenv, ss_size, ss);
 634
 635         /* Integrate slots into the stack frame entity */
 636         assign_entities(&ssenv, ss_size, ss);
 637
 638         /* Clean up */
 639         pmap_foreach(ssenv.slots, pme)
 640         del_pset(((spill_slot_t *)pme->value)->members);
 641         pmap_destroy(ssenv.slots);
 642         pmap_destroy(ssenv.types);
 643         obstack_free(&ssenv.ob, NULL);
 644
 645         be_copy_entities_to_reloads(cenv->irg);
 646 }