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
  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
 141         assert(is_Phi(node));
 142
 143         spill.spill = node;
 144         res = set_find(env->spills, &spill, sizeof(spill), hash);
 145         if(res != NULL) {
 146                 return res;
 147         }
 148
 149         spill.spillslot = set_count(env->spills);
 150         spill.cls = NULL;
 151         res = set_insert(env->spills, &spill, sizeof(spill), hash);
 152
 153         // is 1 of the arguments a spill?
 154         for(i = 0, arity = get_irn_arity(node); i < arity; ++i) {
 155                 affinity_edge_t *affinty_edge;
 156                 ir_node* arg = get_irn_n(node, i);
 157                 spill_t* arg_spill;
 158
 159                 if(be_is_Spill(arg)) {
 160                         arg_spill = collect_spill(env, arg);
 161                 } else {
 162                         // if it wasn't a spill then it must be a Mem-Phi
 163                         assert(is_Phi(arg));
 164                         arg_spill = collect_memphi(env, arg);
 165                 }
 166
 167                 if(res->cls == NULL) {
 168                         res->cls = arg_spill->cls;
 169                 } else {
 170                         assert(arg_spill->cls == NULL || res->cls == arg_spill->cls);
 171                 }
 172
 173                 // add an affinity edge
 174                 affinty_edge = obstack_alloc(&env->obst, sizeof(affinty_edge[0]));
 175                 affinty_edge->affinity = get_block_execfreq(env->chordal_env->exec_freq, get_nodes_block(arg));
 176                 affinty_edge->slot1 = res->spillslot;
 177                 affinty_edge->slot2 = arg_spill->spillslot;
 178                 ARR_APP1(affinity_edge_t*, env->affinity_edges, affinty_edge);
 179         }
 180
 181         return res;
 182 }
 183
 184 /**
 185  * This walker function searches for reloads and collects all the spills
 186  * and memphis attached to them.
 187  */
 188 static void collect_spills_walker(ir_node *node, void *data) {
 189         ss_env_t *env = data;
 190         const arch_env_t *arch_env = env->arch_env;
 191
 192         // @@@ ia32 classify returns classification of the irn the proj is attached
 193         // too, why oh why?...
 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                 } else {
 206                         spill = collect_spill(env, spillnode);
 207                 }
 208
 209                 assert(!be_is_Reload(node) || spill->cls == arch_get_irn_reg_class(arch_env, node, -1));
 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
 335         spillcount = set_count(env->spills);
 336         if(spillcount == 0)
 337                 return;
 338
 339         DBG((dbg, DBG_COALESCING, "Coalescing %d spillslots\n", spillcount));
 340
 341         interferences = alloca(spillcount * sizeof(interferences[0]));
 342         spillslot_unionfind = alloca(spillcount * sizeof(spillslot_unionfind[0]));
 343         spilllist = alloca(spillcount * sizeof(spilllist[0]));
 344
 345         uf_init(spillslot_unionfind, 0, spillcount);
 346
 347         DEBUG_ONLY(
 348                 memset(spilllist, 0, spillcount * sizeof(spilllist[0]));
 349         );
 350
 351         for(spill = set_first(env->spills), i = 0; spill != NULL; spill = set_next(env->spills), ++i) {
 352                 assert(spill->spillslot < spillcount);
 353                 spilllist[spill->spillslot] = spill;
 354         }
 355
 356         for(i = 0; i < spillcount; ++i) {
 357                 interferences[i] = bitset_alloca(spillcount);
 358         }
 359
 360         // construct interferences
 361         for(i = 0; i < spillcount; ++i) {
 362                 for(i2 = i+1; i2 < spillcount; ++i2) {
 363                         if(values_interfere(env->chordal_env->lv, spilllist[i]->spill, spilllist[i2]->spill)) {
 364                                 DBG((dbg, DBG_INTERFERENCES, "Slot %d and %d interfere\n", i, i2));
 365                                 bitset_set(interferences[i], i2);
 366                                 bitset_set(interferences[i2], i);
 367                         }
 368                 }
 369         }
 370
 371         // sort affinity edges
 372         affinity_edge_count = ARR_LEN(env->affinity_edges);
 373         qsort(env->affinity_edges, affinity_edge_count, sizeof(env->affinity_edges[0]), cmp_affinity);
 374
 375         //dump_interference_graph(env, interferences, "before");
 376
 377         // try to merge affine nodes
 378         for(i = 0; i < affinity_edge_count; ++i) {
 379                 const affinity_edge_t *edge = env->affinity_edges[i];
 380                 int s1 = uf_find(spillslot_unionfind, edge->slot1);
 381                 int s2 = uf_find(spillslot_unionfind, edge->slot2);
 382
 383                 /* test if values interfere */
 384                 if(bitset_is_set(interferences[s1], s2)) {
 385                         assert(bitset_is_set(interferences[s2], s1));
 386                         continue;
 387                 }
 388
 389                 DBG((dbg, DBG_COALESCING, "Merging %d and %d because of affinity edge\n", s1, s2));
 390
 391                 merge_interferences(env, interferences, spillslot_unionfind, s1, s2);
 392         }
 393
 394         // try to merge as much remaining spillslots as possible
 395         for(i = 0; i < spillcount; ++i) {
 396                 int s1 = uf_find(spillslot_unionfind, i);
 397                 if(s1 != i)
 398                         continue;
 399
 400                 for(i2 = i+1; i2 < spillcount; ++i2) {
 401                         int s2 = uf_find(spillslot_unionfind, i2);
 402                         if(s2 != i2)
 403                                 continue;
 404
 405                         /* test if values interfere
 406                          * we have to test n1-n2 and n2-n1, because only 1 side gets updated
 407                          * when node merging occurs
 408                          */
 409                         if(bitset_is_set(interferences[s1], s2)) {
 410                                 assert(bitset_is_set(interferences[s2], s1));
 411                                 continue;
 412                         }
 413
 414                         DBG((dbg, DBG_COALESCING, "Merging %d and %d because it is possible\n", s1, s2));
 415
 416                         if(merge_interferences(env, interferences, spillslot_unionfind, s1, s2) != 0) {
 417                                 // we can break the loop here, because s2 is the new supernode now
 418                                 // and we'll test s2 again later anyway
 419                                 break;
 420                         }
 421                 }
 422         }
 423
 424         // assign spillslots to spills
 425         for(i = 0; i < spillcount; ++i) {
 426                 spill_t *spill = spilllist[i];
 427
 428                 spill->spillslot = uf_find(spillslot_unionfind, i);
 429         }
 430
 431         //dump_interference_graph(env, interferences, "after");
 432 }
 433
 434 #if 0
 435 static void do_java_coalescing(ss_env_t *env)
 436 {
 437         int spillcount;
 438         spill_t **spilllist;
 439         spill_t *spill;
 440         int i, i2;
 441         be_java_coal_t *coal;
 442
 443         spillcount = set_count(env->spills);
 444         if(spillcount == 0)
 445                 return;
 446
 447         spilllist = alloca(spillcount * sizeof(spilllist[0]));
 448
 449         DEBUG_ONLY(
 450                 memset(spilllist, 0, spillcount * sizeof(spilllist[0]));
 451         );
 452
 453         coal = be_java_coal_init("spillslot coalescing", spillcount, spillcount, 1);
 454
 455         for(spill = set_first(env->spills), i = 0; spill != NULL; spill = set_next(env->spills), ++i) {
 456                 assert(spill->spillslot < spillcount);
 457                 DEBUG_ONLY(assert(spilllist[spill->spillslot] == NULL));
 458                 spilllist[spill->spillslot] = spill;
 459
 460                 be_java_coal_set_color(coal, spill->spillslot, spill->spillslot);
 461         }
 462
 463         // construct interferences
 464         for(i = 0; i < spillcount; ++i) {
 465                 for(i2 = i+1; i2 < spillcount; ++i2) {
 466                         if(values_interfere(env->chordal_env->lv, spilllist[i]->spill, spilllist[i2]->spill)) {
 467                                 be_java_coal_add_int_edge(coal, i, i2);
 468                         }
 469                 }
 470         }
 471
 472         for(i = 0; i < ARR_LEN(env->affinity_edges); ++i) {
 473                 const affinity_edge_t *edge = env->affinity_edges[i];
 474                 int n = edge->slot1;
 475                 int m = edge->slot2;
 476                 int costs = (int) (edge->affinity * 10000);
 477                 be_java_coal_add_aff_edge(coal, n, m, costs);
 478         }
 479
 480         be_java_coal_coalesce(coal);
 481
 482         // construct spillslots
 483         for(i = 0; i < spillcount; ++i) {
 484                 spill_t *spill = spilllist[i];
 485                 spill->spillslot = be_java_coal_get_color(coal, i);
 486         }
 487         be_java_coal_destroy(coal);
 488 }
 489 #endif
 490
 491 /*
 492  *     _            _               _____       _   _ _   _
 493  *    / \   ___ ___(_) __ _ _ __   | ____|_ __ | |_(_) |_(_) ___  ___
 494  *   / _ \ / __/ __| |/ _` | '_ \  |  _| | '_ \| __| | __| |/ _ \/ __|
 495  *  / ___ \\__ \__ \ | (_| | | | | | |___| | | | |_| | |_| |  __/\__ \
 496  * /_/   \_\___/___/_|\__, |_| |_| |_____|_| |_|\__|_|\__|_|\___||___/
 497  *                    |___/
 498  */
 499
 500 typedef struct _spill_slot_t {
 501         int size;
 502         int align;
 503         entity   *entity;
 504 } spill_slot_t;
 505
 506 typedef struct _memperm_entry_t {
 507         ir_node* node;
 508         int pos;
 509         entity *in;
 510         entity *out;
 511         struct _memperm_entry_t *next;
 512 } memperm_entry_t;
 513
 514 typedef struct _memperm_t {
 515         ir_node *block;
 516         int entrycount;
 517         memperm_entry_t *entries;
 518 } memperm_t;
 519
 520 static int cmp_memperm(const void* d1, const void* d2, size_t size) {
 521         const memperm_t* e1 = d1;
 522         const memperm_t* e2 = d2;
 523         return e1->block != e2->block;
 524 }
 525
 526 static memperm_t *get_memperm(ss_env_t *env, ir_node *block) {
 527         memperm_t entry, *res;
 528         int hash;
 529
 530         entry.block = block;
 531         hash = nodeset_hash(block);
 532
 533         res = set_find(env->memperms, &entry, sizeof(entry), hash);
 534
 535         if(res == NULL) {
 536                 entry.entrycount = 0;
 537                 entry.entries = NULL;
 538                 res = set_insert(env->memperms, &entry, sizeof(entry), hash);
 539         }
 540
 541         return res;
 542 }
 543
 544 static entity* create_stack_entity(ss_env_t *env, spill_slot_t *slot) {
 545         ir_type* frame = get_irg_frame_type(env->chordal_env->irg);
 546         entity* res = frame_alloc_area(frame, slot->size, slot->align, 0);
 547
 548         // adjust size of the entity type...
 549         ir_type *enttype = get_entity_type(res);
 550         set_type_size_bytes(enttype, slot->size);
 551
 552         slot->entity = res;
 553
 554         return res;
 555 }
 556
 557 static int get_spillslotsize_for_spill(ss_env_t *env, spill_t *spill) {
 558         const ir_mode *mode = arch_register_class_mode(spill->cls);
 559
 560         return get_mode_size_bytes(mode);
 561 }
 562
 563 static int get_spillslotalign_for_spill(ss_env_t *env, spill_t *spill) {
 564         const arch_isa_t *isa = env->chordal_env->birg->main_env->arch_env->isa;
 565
 566         return arch_isa_get_reg_class_alignment(isa, spill->cls);
 567 }
 568
 569 /**
 570  * Enlarges a spillslot (if necessary) so that it can carry a value of size
 571  * @p othersize and alignment @p otheralign.
 572  */
 573 static void enlarge_spillslot(spill_slot_t *slot, int otheralign, int othersize) {
 574         if(othersize > slot->size) {
 575                 slot->size = othersize;
 576         }
 577         if(otheralign > slot->align) {
 578                 if(otheralign % slot->align != 0)
 579                         slot->align *= otheralign;
 580                 else
 581                         slot->align = otheralign;
 582         } else if(slot->align % otheralign != 0) {
 583                 slot->align *= otheralign;
 584         }
 585 }
 586
 587 /**
 588  * Create stack entities for the spillslots and assign them to the spill and
 589  * reload nodes.
 590  */
 591 static void assign_spillslots(ss_env_t *env) {
 592         const arch_env_t *arch_env = env->arch_env;
 593         int i;
 594         int spillcount;
 595         spill_t *spill;
 596         spill_slot_t* spillslots;
 597
 598         spillcount = set_count(env->spills);
 599         spillslots = alloca(spillcount * sizeof(spillslots[0]));
 600
 601         memset(spillslots, 0, spillcount * sizeof(spillslots[0]));
 602
 603         // construct spillslots
 604         for(spill = set_first(env->spills); spill != NULL; spill = set_next(env->spills)) {
 605                 int slotid = spill->spillslot;
 606                 spill_slot_t *slot = & (spillslots[slotid]);
 607                 int align = get_spillslotalign_for_spill(env, spill);
 608                 int size = get_spillslotsize_for_spill(env, spill);
 609
 610                 if(slot->align == 0 && slot->size == 0) {
 611                         slot->align = align;
 612                         slot->size = size;
 613                 } else {
 614                         enlarge_spillslot(slot, align, size);
 615                 }
 616         }
 617
 618         for(spill = set_first(env->spills); spill != NULL; spill = set_next(env->spills)) {
 619                 spill_slot_t *slot;
 620                 ir_node *node = spill->spill;
 621                 int slotid = spill->spillslot;
 622
 623                 slot = &spillslots[slotid];
 624                 if(slot->entity == NULL) {
 625                         create_stack_entity(env, slot);
 626                 }
 627
 628                 if(is_Phi(node)) {
 629                         int i, arity;
 630                         ir_node *block = get_nodes_block(node);
 631
 632                         // should be a PhiM
 633                         assert(is_Phi(node));
 634
 635                         for(i = 0, arity = get_irn_arity(node); i < arity; ++i) {
 636                                 ir_node *arg = get_irn_n(node, i);
 637                                 ir_node *predblock = get_Block_cfgpred_block(block, i);
 638                                 spill_t *argspill;
 639                                 int argslotid;
 640
 641                                 argspill = get_spill(env, arg);
 642                                 assert(argspill != NULL);
 643
 644                                 argslotid = argspill->spillslot;
 645                                 if(slotid != argslotid) {
 646                                         memperm_t *memperm;
 647                                         memperm_entry_t *entry;
 648                                         spill_slot_t *argslot = &spillslots[argslotid];
 649                                         if(argslot->entity == NULL) {
 650                                                 create_stack_entity(env, argslot);
 651                                         }
 652
 653                                         memperm = get_memperm(env, predblock);
 654
 655                                         entry = obstack_alloc(&env->obst, sizeof(entry[0]));
 656                                         entry->node = node;
 657                                         entry->pos = i;
 658                                         entry->in = argslot->entity;
 659                                         entry->out = slot->entity;
 660                                         entry->next = memperm->entries;
 661                                         memperm->entrycount++;
 662                                         memperm->entries = entry;
 663                                 }
 664                         }
 665                 } else {
 666                         assert(arch_irn_class_is(arch_env, node, spill));
 667                         arch_set_frame_entity(arch_env, node, slot->entity);
 668                 }
 669         }
 670
 671         for(i = 0; i < ARR_LEN(env->reloads); ++i) {
 672                 ir_node* reload = env->reloads[i];
 673                 ir_node* spillnode = get_memory_edge(reload);
 674                 spill_t *spill = get_spill(env, spillnode);
 675                 const spill_slot_t *slot = & spillslots[spill->spillslot];
 676
 677                 assert(slot->entity != NULL);
 678
 679                 arch_set_frame_entity(arch_env, reload, slot->entity);
 680         }
 681 }
 682
 683 /**
 684  * Returns the last node in a block which is no control flow changing node
 685  */
 686 static ir_node *get_end_of_block_insertion_point(ir_node* block)
 687 {
 688         ir_node* ins = sched_last(block);
 689         while(is_Proj(ins) && get_irn_mode(ins) == mode_X) {
 690                 ins = sched_prev(ins);
 691                 assert(ins != NULL);
 692         }
 693
 694         if(is_cfop(ins)) {
 695                 while(1) {
 696                         ir_node *prev = sched_prev(ins);
 697                         if(!is_cfop(prev))
 698                                 break;
 699                         ins = prev;
 700                 }
 701         }
 702
 703         return ins;
 704 }
 705
 706 static void create_memperms(ss_env_t *env) {
 707         memperm_t *memperm;
 708
 709         for(memperm = set_first(env->memperms); memperm != NULL; memperm = set_next(env->memperms)) {
 710                 int i;
 711                 memperm_entry_t *entry;
 712                 ir_node *blockend;
 713                 ir_node** nodes = alloca(memperm->entrycount * sizeof(nodes[0]));
 714                 ir_node* mempermnode;
 715
 716                 assert(memperm->entrycount > 0);
 717
 718                 for(entry = memperm->entries, i = 0; entry != NULL; entry = entry->next, ++i) {
 719                         ir_node* arg = get_irn_n(entry->node, entry->pos);
 720                         nodes[i] = arg;
 721                 }
 722
 723                 mempermnode = be_new_MemPerm(env->chordal_env->birg->main_env->arch_env, env->chordal_env->irg, memperm->block,
 724                         memperm->entrycount, nodes);
 725
 726                 // insert node into schedule
 727                 blockend = get_end_of_block_insertion_point(memperm->block);
 728                 sched_add_before(blockend, mempermnode);
 729                 be_stat_ev("mem_perm", memperm->entrycount);
 730
 731                 for(entry = memperm->entries, i = 0; entry != NULL; entry = entry->next, ++i) {
 732                         ir_node *proj;
 733                         ir_node* arg = get_irn_n(entry->node, entry->pos);
 734
 735                         be_set_MemPerm_in_entity(mempermnode, i, entry->in);
 736                         be_set_MemPerm_out_entity(mempermnode, i, entry->out);
 737                         set_irg_current_block(env->chordal_env->irg, memperm->block);
 738                         proj = new_Proj(mempermnode, get_irn_mode(arg), i);
 739                         sched_add_before(blockend, proj);
 740
 741                         set_irn_n(entry->node, entry->pos, proj);
 742                 }
 743         }
 744 }
 745
 746 void be_coalesce_spillslots(const be_chordal_env_t *chordal_env, int coalesce_spillslots) {
 747         ss_env_t env;
 748
 749         obstack_init(&env.obst);
 750         env.arch_env = chordal_env->birg->main_env->arch_env;
 751         env.chordal_env = chordal_env;
 752         env.spills = new_set(cmp_spill, 10);
 753         env.reloads = NEW_ARR_F(ir_node*, 0);
 754         env.affinity_edges = NEW_ARR_F(affinity_edge_t*, 0);
 755         env.memperms = new_set(cmp_memperm, 10);
 756         FIRM_DBG_REGISTER(dbg, "firm.be.spillslots");
 757         //firm_dbg_set_mask(dbg, DBG_COALESCING);
 758
 759         /* Get initial spill slots */
 760         irg_walk_graph(chordal_env->irg, NULL, collect_spills_walker, &env);
 761
 762         if(coalesce_spillslots)
 763                 do_greedy_coalescing(&env);
 764
 765         assign_spillslots(&env);
 766
 767         create_memperms(&env);
 768
 769         //show_stats(&env);
 770
 771         del_set(env.memperms);
 772         DEL_ARR_F(env.reloads);
 773         DEL_ARR_F(env.affinity_edges);
 774         del_set(env.spills);
 775         obstack_free(&env.obst, NULL);
 776 }