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