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

   1 /*
   2  * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /*
  21  * Author:      Matthias Braun
  22  * Date:                26.7.06
  23  * Copyright:   (c) Universitaet Karlsruhe
  24  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  25  */
  26 #ifdef HAVE_CONFIG_H
  27 #include "config.h"
  28 #endif
  29
  30 #include <stdlib.h>
  31
  32 #include "set.h"
  33
  34 #include "irgwalk.h"
  35 #include "ircons.h"
  36 #include "irprintf.h"
  37 #include "execfreq.h"
  38 #include "unionfind.h"
  39 #include "type.h"
  40 #include "irdump_t.h"
  41
  42 #include "benode_t.h"
  43 #include "besched.h"
  44 #include "bespillslots.h"
  45 #include "bechordal_t.h"
  46 #include "bejavacoal.h"
  47 #include "benodesets.h"
  48 #include "bestatevent.h"
  49 #include "bespilloptions.h"
  50 #include "bemodule.h"
  51
  52 #define DBG_COALESCING          1
  53 #define DBG_INTERFERENCES       2
  54
  55 DEBUG_ONLY(
  56 static firm_dbg_module_t *dbg = NULL;
  57 )
  58
  59 typedef struct _spill_t {
  60         ir_node *spill;
  61         /** mode of the spilled value */
  62         const ir_mode *mode;
  63         /** alignment for the spilled value */
  64         int alignment;
  65         /** index into spillslot_unionfind unionfind structure */
  66         int spillslot;
  67 } spill_t;
  68
  69 typedef struct _affinity_edge_t {
  70         double affinity;
  71         int slot1, slot2;
  72 } affinity_edge_t;
  73
  74 struct _be_fec_env_t {
  75         struct obstack obst;
  76         const arch_env_t *arch_env;
  77         be_irg_t *birg;
  78         set *spills;
  79         ir_node **reloads;
  80         affinity_edge_t **affinity_edges;
  81         set *memperms;
  82 };
  83
  84 /** Compare 2 affinity edges (used in quicksort) */
  85 static int cmp_affinity(const void *d1, const void *d2)
  86 {
  87         const affinity_edge_t * const *e1 = d1;
  88         const affinity_edge_t * const *e2 = d2;
  89
  90         // sort in descending order
  91         return (*e1)->affinity < (*e2)->affinity ? 1 : -1;
  92 }
  93
  94 static int cmp_spill(const void* d1, const void* d2, size_t size)
  95 {
  96         const spill_t* s1 = d1;
  97         const spill_t* s2 = d2;
  98         return s1->spill != s2->spill;
  99 }
 100
 101 static spill_t *get_spill(be_fec_env_t *env, ir_node *node)
 102 {
 103         spill_t spill, *res;
 104         int hash = nodeset_hash(node);
 105
 106         spill.spill = node;
 107         res = set_find(env->spills, &spill, sizeof(spill), hash);
 108
 109         return res;
 110 }
 111
 112 /*
 113  *   ____      _ _           _     ____        _ _ _
 114  *  / ___|___ | | | ___  ___| |_  / ___| _ __ (_) | |___
 115  * | |   / _ \| | |/ _ \/ __| __| \___ \| '_ \| | | / __|
 116  * | |__| (_) | | |  __/ (__| |_   ___) | |_) | | | \__ \
 117  *  \____\___/|_|_|\___|\___|\__| |____/| .__/|_|_|_|___/
 118  *                                      |_|
 119  */
 120
 121 static INLINE ir_node *get_memory_edge(const ir_node *node)
 122 {
 123         int i, arity;
 124
 125         arity = get_irn_arity(node);
 126         for(i = arity - 1; i >= 0; --i) {
 127                 ir_node *arg = get_irn_n(node, i);
 128                 if(get_irn_mode(arg) == mode_M)
 129                         return arg;
 130         }
 131
 132         return NULL;
 133 }
 134
 135 static spill_t *collect_spill(be_fec_env_t *env, ir_node *node,
 136                                       const ir_mode *mode, int align)
 137 {
 138         spill_t spill, *res;
 139         int hash = nodeset_hash(node);
 140
 141         /* insert into set of spills if not already there */
 142         spill.spill = node;
 143         res = set_find(env->spills, &spill, sizeof(spill), hash);
 144
 145         if(res == NULL) {
 146                 spill.spillslot = set_count(env->spills);
 147                 spill.mode = mode;
 148                 spill.alignment = align;
 149                 res = set_insert(env->spills, &spill, sizeof(spill), hash);
 150         } else {
 151                 assert(res->mode == mode);
 152                 assert(res->alignment == align);
 153         }
 154
 155         return res;
 156 }
 157
 158 static spill_t *collect_memphi(be_fec_env_t *env, ir_node *node,
 159                                const ir_mode *mode, int align)
 160 {
 161         int i, arity;
 162         spill_t spill, *res;
 163         int hash = nodeset_hash(node);
 164         const ir_exec_freq *exec_freq = be_get_birg_exec_freq(env->birg);
 165
 166         assert(is_Phi(node));
 167
 168         spill.spill = node;
 169         res = set_find(env->spills, &spill, sizeof(spill), hash);
 170         if(res != NULL) {
 171                 assert(res->mode == mode);
 172                 assert(res->alignment == align);
 173                 return res;
 174         }
 175
 176         spill.spillslot = set_count(env->spills);
 177         spill.mode = mode;
 178         spill.alignment = align;
 179         res = set_insert(env->spills, &spill, sizeof(spill), hash);
 180
 181         // collect attached spills and mem-phis
 182         arity = get_irn_arity(node);
 183         for(i = 0; i < arity; ++i) {
 184                 affinity_edge_t *affinty_edge;
 185                 ir_node *arg = get_irn_n(node, i);
 186                 spill_t *arg_spill;
 187
 188                 if(is_Phi(arg)) {
 189                         arg_spill = collect_memphi(env, arg, mode, align);
 190                 } else {
 191                         arg_spill = collect_spill(env, arg, mode, align);
 192                 }
 193
 194                 // add an affinity edge
 195                 affinty_edge = obstack_alloc(&env->obst, sizeof(affinty_edge[0]));
 196                 affinty_edge->affinity = get_block_execfreq(exec_freq, get_nodes_block(arg));
 197                 affinty_edge->slot1 = res->spillslot;
 198                 affinty_edge->slot2 = arg_spill->spillslot;
 199                 ARR_APP1(affinity_edge_t*, env->affinity_edges, affinty_edge);
 200         }
 201
 202         return res;
 203 }
 204
 205 void be_node_needs_frame_entity(be_fec_env_t *env, ir_node *node,
 206                                 const ir_mode *mode, int align)
 207 {
 208         ir_node *spillnode = get_memory_edge(node);
 209         spill_t *spill;
 210
 211         assert(spillnode != NULL);
 212
 213         if (is_Phi(spillnode)) {
 214                 spill = collect_memphi(env, spillnode, mode, align);
 215         } else {
 216                 spill = collect_spill(env, spillnode, mode, align);
 217         }
 218
 219         ARR_APP1(ir_node *, env->reloads, node);
 220 }
 221
 222 /*
 223  *   ____            _                      ____  _       _
 224  *  / ___|___   __ _| | ___  ___  ___ ___  / ___|| | ___ | |_ ___
 225  * | |   / _ \ / _` | |/ _ \/ __|/ __/ _ \ \___ \| |/ _ \| __/ __|
 226  * | |__| (_) | (_| | |  __/\__ \ (_|  __/  ___) | | (_) | |_\__ \
 227  *  \____\___/ \__,_|_|\___||___/\___\___| |____/|_|\___/ \__|___/
 228  */
 229
 230 static int merge_interferences(be_fec_env_t *env, bitset_t** interferences,
 231                                int* spillslot_unionfind, int s1, int s2)
 232 {
 233         int res;
 234         int i;
 235         int spillcount;
 236
 237         // merge spillslots and interferences
 238         res = uf_union(spillslot_unionfind, s1, s2);
 239         // we assume that we always merge s2 to s1 so swap s1, s2 if necessary
 240         if(res != 0) {
 241                 int t = s1;
 242                 s1 = s2;
 243                 s2 = t;
 244         }
 245
 246         bitset_or(interferences[s1], interferences[s2]);
 247
 248         // update other interferences
 249         spillcount = set_count(env->spills);
 250         for(i = 0; i < spillcount; ++i) {
 251                 bitset_t *intfs = interferences[i];
 252                 if(bitset_is_set(intfs, s2))
 253                         bitset_set(intfs, s1);
 254         }
 255
 256         return res;
 257 }
 258
 259 /**
 260  * A greedy coalescing algorithm for spillslots:
 261  *  1. Sort the list of affinity edges
 262  *  2. Try to merge slots with affinity edges (most expensive slots first)
 263  *  3. Try to merge everything else that is possible
 264  */
 265 static void do_greedy_coalescing(be_fec_env_t *env)
 266 {
 267         int spillcount;
 268         spill_t **spilllist;
 269         spill_t *spill;
 270         int i, i2;
 271         int affinity_edge_count;
 272         bitset_t **interferences;
 273         int* spillslot_unionfind;
 274         const be_lv_t *lv = be_get_birg_liveness(env->birg);
 275
 276         spillcount = set_count(env->spills);
 277         if(spillcount == 0)
 278                 return;
 279
 280         DBG((dbg, DBG_COALESCING, "Coalescing %d spillslots\n", spillcount));
 281
 282         interferences = alloca(spillcount * sizeof(interferences[0]));
 283         spillslot_unionfind = alloca(spillcount * sizeof(spillslot_unionfind[0]));
 284         spilllist = alloca(spillcount * sizeof(spilllist[0]));
 285
 286         uf_init(spillslot_unionfind, 0, spillcount);
 287
 288         DEBUG_ONLY(
 289                 memset(spilllist, 0, spillcount * sizeof(spilllist[0]));
 290         );
 291
 292         for(spill = set_first(env->spills), i = 0; spill != NULL; spill = set_next(env->spills), ++i) {
 293                 assert(spill->spillslot < spillcount);
 294                 spilllist[spill->spillslot] = spill;
 295         }
 296
 297         for(i = 0; i < spillcount; ++i) {
 298                 interferences[i] = bitset_alloca(spillcount);
 299         }
 300
 301         // construct interferences
 302         for(i = 0; i < spillcount; ++i) {
 303                 ir_node *spill1 = spilllist[i]->spill;
 304                 if(is_NoMem(spill1))
 305                         continue;
 306
 307                 for(i2 = i+1; i2 < spillcount; ++i2) {
 308                         ir_node *spill2 = spilllist[i2]->spill;
 309                         if(is_NoMem(spill2))
 310                                 continue;
 311
 312                         if(values_interfere(lv, spill1, spill2)) {
 313                                 DBG((dbg, DBG_INTERFERENCES, "Slot %d and %d interfere\n",
 314                                      i, i2));
 315                                 bitset_set(interferences[i], i2);
 316                                 bitset_set(interferences[i2], i);
 317                         }
 318                 }
 319         }
 320
 321         // sort affinity edges
 322         affinity_edge_count = ARR_LEN(env->affinity_edges);
 323         qsort(env->affinity_edges, affinity_edge_count, sizeof(env->affinity_edges[0]), cmp_affinity);
 324
 325         //dump_interference_graph(env, interferences, "before");
 326
 327         // try to merge affine nodes
 328         for(i = 0; i < affinity_edge_count; ++i) {
 329                 const affinity_edge_t *edge = env->affinity_edges[i];
 330                 int s1 = uf_find(spillslot_unionfind, edge->slot1);
 331                 int s2 = uf_find(spillslot_unionfind, edge->slot2);
 332
 333                 /* test if values interfere */
 334                 if(bitset_is_set(interferences[s1], s2)) {
 335                         assert(bitset_is_set(interferences[s2], s1));
 336                         continue;
 337                 }
 338
 339                 DBG((dbg, DBG_COALESCING, "Merging %d and %d because of affinity edge\n", s1, s2));
 340
 341                 merge_interferences(env, interferences, spillslot_unionfind, s1, s2);
 342         }
 343
 344         // try to merge as much remaining spillslots as possible
 345         for(i = 0; i < spillcount; ++i) {
 346                 int s1 = uf_find(spillslot_unionfind, i);
 347                 if(s1 != i)
 348                         continue;
 349
 350                 for(i2 = i+1; i2 < spillcount; ++i2) {
 351                         int s2 = uf_find(spillslot_unionfind, i2);
 352                         if(s2 != i2)
 353                                 continue;
 354
 355                         /* test if values interfere
 356                          * we have to test n1-n2 and n2-n1, because only 1 side gets updated
 357                          * when node merging occurs
 358                          */
 359                         if(bitset_is_set(interferences[s1], s2)) {
 360                                 assert(bitset_is_set(interferences[s2], s1));
 361                                 continue;
 362                         }
 363
 364                         DBG((dbg, DBG_COALESCING, "Merging %d and %d because it is possible\n", s1, s2));
 365
 366                         if(merge_interferences(env, interferences, spillslot_unionfind, s1, s2) != 0) {
 367                                 // we can break the loop here, because s2 is the new supernode now
 368                                 // and we'll test s2 again later anyway
 369                                 break;
 370                         }
 371                 }
 372         }
 373
 374         // assign spillslots to spills
 375         for(i = 0; i < spillcount; ++i) {
 376                 spill_t *spill = spilllist[i];
 377
 378                 spill->spillslot = uf_find(spillslot_unionfind, i);
 379         }
 380
 381         //dump_interference_graph(env, interferences, "after");
 382 }
 383
 384 /*
 385  *     _            _               _____       _   _ _   _
 386  *    / \   ___ ___(_) __ _ _ __   | ____|_ __ | |_(_) |_(_) ___  ___
 387  *   / _ \ / __/ __| |/ _` | '_ \  |  _| | '_ \| __| | __| |/ _ \/ __|
 388  *  / ___ \\__ \__ \ | (_| | | | | | |___| | | | |_| | |_| |  __/\__ \
 389  * /_/   \_\___/___/_|\__, |_| |_| |_____|_| |_|\__|_|\__|_|\___||___/
 390  *                    |___/
 391  */
 392
 393 typedef struct _spill_slot_t {
 394         int size;
 395         int align;
 396         ir_entity *entity;
 397 } spill_slot_t;
 398
 399 typedef struct _memperm_entry_t {
 400         ir_node* node;
 401         int pos;
 402         ir_entity *in;
 403         ir_entity *out;
 404         struct _memperm_entry_t *next;
 405 } memperm_entry_t;
 406
 407 typedef struct _memperm_t {
 408         ir_node *block;
 409         int entrycount;
 410         memperm_entry_t *entries;
 411 } memperm_t;
 412
 413 static int cmp_memperm(const void* d1, const void* d2, size_t size)
 414 {
 415         const memperm_t* e1 = d1;
 416         const memperm_t* e2 = d2;
 417         return e1->block != e2->block;
 418 }
 419
 420 static memperm_t *get_memperm(be_fec_env_t *env, ir_node *block)
 421 {
 422         memperm_t entry, *res;
 423         int hash;
 424
 425         entry.block = block;
 426         hash = nodeset_hash(block);
 427
 428         res = set_find(env->memperms, &entry, sizeof(entry), hash);
 429
 430         if(res == NULL) {
 431                 entry.entrycount = 0;
 432                 entry.entries = NULL;
 433                 res = set_insert(env->memperms, &entry, sizeof(entry), hash);
 434         }
 435
 436         return res;
 437 }
 438
 439 static ir_entity* create_stack_entity(be_fec_env_t *env, spill_slot_t *slot)
 440 {
 441         ir_graph *irg = be_get_birg_irg(env->birg);
 442         ir_type *frame = get_irg_frame_type(irg);
 443         ir_entity *res = frame_alloc_area(frame, slot->size, slot->align, 0);
 444
 445         // adjust size of the entity type...
 446         ir_type *enttype = get_entity_type(res);
 447         set_type_size_bytes(enttype, slot->size);
 448
 449         slot->entity = res;
 450
 451         return res;
 452 }
 453
 454 /**
 455  * Enlarges a spillslot (if necessary) so that it can carry a value of size
 456  * @p othersize and alignment @p otheralign.
 457  */
 458 static void enlarge_spillslot(spill_slot_t *slot, int otheralign, int othersize)
 459 {
 460         if(othersize > slot->size) {
 461                 slot->size = othersize;
 462         }
 463         if(otheralign > slot->align) {
 464                 if(otheralign % slot->align != 0)
 465                         slot->align *= otheralign;
 466                 else
 467                         slot->align = otheralign;
 468         } else if(slot->align % otheralign != 0) {
 469                 slot->align *= otheralign;
 470         }
 471 }
 472
 473 /**
 474  * Create stack entities for the spillslots and assign them to the spill and
 475  * reload nodes.
 476  */
 477 static void assign_spillslots(be_fec_env_t *env)
 478 {
 479         const arch_env_t *arch_env = env->arch_env;
 480         int i;
 481         int spillcount;
 482         spill_t *spill;
 483         spill_slot_t* spillslots;
 484
 485         spillcount = set_count(env->spills);
 486         spillslots = alloca(spillcount * sizeof(spillslots[0]));
 487
 488         memset(spillslots, 0, spillcount * sizeof(spillslots[0]));
 489
 490         // construct spillslots
 491         for(spill = set_first(env->spills); spill != NULL; spill = set_next(env->spills)) {
 492                 int slotid = spill->spillslot;
 493                 const ir_mode *mode = spill->mode;
 494                 spill_slot_t *slot = & (spillslots[slotid]);
 495                 int size = get_mode_size_bytes(mode);
 496                 int align = spill->alignment;
 497
 498                 if(slot->align == 0 && slot->size == 0) {
 499                         slot->align = align;
 500                         slot->size = size;
 501                 } else {
 502                         enlarge_spillslot(slot, align, size);
 503                 }
 504         }
 505
 506         for(spill = set_first(env->spills); spill != NULL; spill = set_next(env->spills)) {
 507                 spill_slot_t *slot;
 508                 ir_node *node = spill->spill;
 509                 int slotid = spill->spillslot;
 510
 511                 slot = &spillslots[slotid];
 512                 if(slot->entity == NULL) {
 513                         create_stack_entity(env, slot);
 514                 }
 515
 516                 if(is_Phi(node)) {
 517                         int i, arity;
 518                         ir_node *block = get_nodes_block(node);
 519
 520                         // should be a PhiM
 521                         assert(is_Phi(node));
 522
 523                         for(i = 0, arity = get_irn_arity(node); i < arity; ++i) {
 524                                 ir_node *arg = get_irn_n(node, i);
 525                                 ir_node *predblock = get_Block_cfgpred_block(block, i);
 526                                 spill_t *argspill;
 527                                 int argslotid;
 528
 529                                 argspill = get_spill(env, arg);
 530                                 assert(argspill != NULL);
 531
 532                                 argslotid = argspill->spillslot;
 533                                 if(slotid != argslotid) {
 534                                         memperm_t *memperm;
 535                                         memperm_entry_t *entry;
 536                                         spill_slot_t *argslot = &spillslots[argslotid];
 537                                         if(argslot->entity == NULL) {
 538                                                 create_stack_entity(env, argslot);
 539                                         }
 540
 541                                         memperm = get_memperm(env, predblock);
 542
 543                                         entry = obstack_alloc(&env->obst, sizeof(entry[0]));
 544                                         entry->node = node;
 545                                         entry->pos = i;
 546                                         entry->in = argslot->entity;
 547                                         entry->out = slot->entity;
 548                                         entry->next = memperm->entries;
 549                                         memperm->entrycount++;
 550                                         memperm->entries = entry;
 551                                 }
 552                         }
 553                 } else {
 554                         if(!is_NoMem(node))
 555                                 arch_set_frame_entity(arch_env, node, slot->entity);
 556                 }
 557         }
 558
 559         for(i = 0; i < ARR_LEN(env->reloads); ++i) {
 560                 ir_node* reload = env->reloads[i];
 561                 ir_node* spillnode = get_memory_edge(reload);
 562                 spill_t *spill = get_spill(env, spillnode);
 563                 const spill_slot_t *slot = & spillslots[spill->spillslot];
 564
 565                 assert(slot->entity != NULL);
 566
 567                 arch_set_frame_entity(arch_env, reload, slot->entity);
 568         }
 569 }
 570
 571 /**
 572  * Returns the last node in a block which is no control flow changing node
 573  */
 574 static ir_node *get_end_of_block_insertion_point(ir_node* block)
 575 {
 576         ir_node* ins = sched_last(block);
 577         while(is_Proj(ins) && get_irn_mode(ins) == mode_X) {
 578                 ins = sched_prev(ins);
 579                 assert(ins != NULL);
 580         }
 581
 582         if(is_cfop(ins)) {
 583                 while(1) {
 584                         ir_node *prev = sched_prev(ins);
 585                         if(!is_cfop(prev))
 586                                 break;
 587                         ins = prev;
 588                 }
 589         }
 590
 591         return ins;
 592 }
 593
 594 static void create_memperms(be_fec_env_t *env)
 595 {
 596         const arch_env_t *arch_env = env->arch_env;
 597         ir_graph *irg = be_get_birg_irg(env->birg);
 598         memperm_t *memperm;
 599
 600         for(memperm = set_first(env->memperms); memperm != NULL; memperm = set_next(env->memperms)) {
 601                 int i;
 602                 memperm_entry_t *entry;
 603                 ir_node *blockend;
 604                 ir_node** nodes = alloca(memperm->entrycount * sizeof(nodes[0]));
 605                 ir_node* mempermnode;
 606
 607                 assert(memperm->entrycount > 0);
 608
 609                 for(entry = memperm->entries, i = 0; entry != NULL; entry = entry->next, ++i) {
 610                         ir_node* arg = get_irn_n(entry->node, entry->pos);
 611                         nodes[i] = arg;
 612                 }
 613
 614                 mempermnode = be_new_MemPerm(arch_env, irg, memperm->block,
 615                                              memperm->entrycount, nodes);
 616
 617                 // insert node into schedule
 618                 blockend = get_end_of_block_insertion_point(memperm->block);
 619                 sched_add_before(blockend, mempermnode);
 620                 be_stat_ev("mem_perm", memperm->entrycount);
 621
 622                 i = 0;
 623                 for(entry = memperm->entries; entry != NULL; entry = entry->next, ++i) {
 624                         ir_node *proj;
 625                         ir_node* arg = get_irn_n(entry->node, entry->pos);
 626
 627                         be_set_MemPerm_in_entity(mempermnode, i, entry->in);
 628                         be_set_MemPerm_out_entity(mempermnode, i, entry->out);
 629                         set_irg_current_block(irg, memperm->block);
 630                         proj = new_Proj(mempermnode, get_irn_mode(arg), i);
 631                         sched_add_before(blockend, proj);
 632
 633                         set_irn_n(entry->node, entry->pos, proj);
 634                 }
 635         }
 636 }
 637
 638 static int count_spillslots(const be_fec_env_t *env)
 639 {
 640         const spill_t *spill;
 641         int spillcount = set_count(env->spills);
 642         bitset_t *counted = bitset_alloca(spillcount);
 643         int slotcount;
 644
 645         slotcount = 0;
 646         for(spill = set_first(env->spills); spill != NULL;
 647             spill = set_next(env->spills)) {
 648                 int spillslot = spill->spillslot;
 649                 if(!bitset_is_set(counted, spillslot)) {
 650                         slotcount++;
 651                         bitset_set(counted, spillslot);
 652                 }
 653         }
 654
 655         return slotcount;
 656 }
 657
 658 be_fec_env_t *be_new_frame_entity_coalescer(be_irg_t *birg)
 659 {
 660         const arch_env_t *arch_env = birg->main_env->arch_env;
 661
 662         be_fec_env_t *env = xmalloc(sizeof(env[0]));
 663
 664         be_assure_liveness(birg);
 665
 666         obstack_init(&env->obst);
 667         env->arch_env = arch_env;
 668         env->birg = birg;
 669         env->spills = new_set(cmp_spill, 10);
 670         env->reloads = NEW_ARR_F(ir_node*, 0);
 671         env->affinity_edges = NEW_ARR_F(affinity_edge_t*, 0);
 672         env->memperms = new_set(cmp_memperm, 10);
 673
 674         return env;
 675 }
 676
 677 void be_free_frame_entity_coalescer(be_fec_env_t *env)
 678 {
 679         del_set(env->memperms);
 680         DEL_ARR_F(env->reloads);
 681         DEL_ARR_F(env->affinity_edges);
 682         del_set(env->spills);
 683         obstack_free(&env->obst, NULL);
 684
 685         free(env);
 686 }
 687
 688 void be_assign_entities(be_fec_env_t *env)
 689 {
 690         if(be_stat_ev_is_active()) {
 691                 int count = set_count(env->spills);
 692                 be_stat_ev("spillslots", count);
 693         }
 694
 695         if(be_coalesce_spill_slots) {
 696                 do_greedy_coalescing(env);
 697         }
 698
 699         if(be_stat_ev_is_active()) {
 700                 int count = count_spillslots(env);
 701                 be_stat_ev("spillslots_after_coalescing", count);
 702         }
 703
 704         assign_spillslots(env);
 705
 706         create_memperms(env);
 707 }
 708
 709 /**
 710  * This walker function searches for reloads and collects all the spills
 711  * and memphis attached to them.
 712  */
 713 static void collect_spills_walker(ir_node *node, void *data)
 714 {
 715         be_fec_env_t *env = data;
 716         const arch_env_t *arch_env = env->arch_env;
 717         const ir_mode *mode;
 718         const arch_register_class_t *cls;
 719         int align;
 720
 721         /* classify returns classification of the irn the proj is attached to */
 722         if (is_Proj(node))
 723                 return;
 724
 725         if (!arch_irn_class_is(arch_env, node, reload))
 726                 return;
 727
 728         mode = get_irn_mode(node);
 729         cls = arch_get_irn_reg_class(arch_env, node, -1);
 730         align = arch_isa_get_reg_class_alignment(arch_env_get_isa(arch_env), cls);
 731
 732         be_node_needs_frame_entity(env, node, mode, align);
 733 }
 734
 735 void be_coalesce_spillslots(be_irg_t *birg)
 736 {
 737         be_fec_env_t *env = be_new_frame_entity_coalescer(birg);
 738
 739         /* collect reloads */
 740         irg_walk_graph(birg->irg, NULL, collect_spills_walker, env);
 741
 742         be_assign_entities(env);
 743
 744         be_free_frame_entity_coalescer(env);
 745 }
 746
 747 void be_init_spillslots(void)
 748 {
 749         FIRM_DBG_REGISTER(dbg, "firm.be.spillslots");
 750 }
 751
 752 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_spillslots);