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

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