2 * Author: Matthias Braun
4 * Copyright: (c) Universitaet Karlsruhe
5 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
19 #include "unionfind.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"
33 #define DBG_COALESCING 1
34 #define DBG_INTERFERENCES 2
37 static firm_dbg_module_t *dbg = NULL;
40 typedef struct _spill_t {
42 /** mode of the spilled value */
44 /** alignment for the spilled value */
46 /** index into spillslot_unionfind unionfind structure */
50 typedef struct _affinity_edge_t {
55 struct _be_fec_env_t {
57 const arch_env_t *arch_env;
61 affinity_edge_t **affinity_edges;
65 /** Compare 2 affinity edges (used in quicksort) */
66 static int cmp_affinity(const void *d1, const void *d2)
68 const affinity_edge_t * const *e1 = d1;
69 const affinity_edge_t * const *e2 = d2;
71 // sort in descending order
72 return (*e1)->affinity < (*e2)->affinity ? 1 : -1;
75 static int cmp_spill(const void* d1, const void* d2, size_t size)
77 const spill_t* s1 = d1;
78 const spill_t* s2 = d2;
79 return s1->spill != s2->spill;
82 static spill_t *get_spill(be_fec_env_t *env, ir_node *node)
85 int hash = nodeset_hash(node);
88 res = set_find(env->spills, &spill, sizeof(spill), hash);
94 * ____ _ _ _ ____ _ _ _
95 * / ___|___ | | | ___ ___| |_ / ___| _ __ (_) | |___
96 * | | / _ \| | |/ _ \/ __| __| \___ \| '_ \| | | / __|
97 * | |__| (_) | | | __/ (__| |_ ___) | |_) | | | \__ \
98 * \____\___/|_|_|\___|\___|\__| |____/| .__/|_|_|_|___/
102 static INLINE ir_node *get_memory_edge(const ir_node *node)
106 arity = get_irn_arity(node);
107 for(i = arity - 1; i >= 0; --i) {
108 ir_node *arg = get_irn_n(node, i);
109 if(get_irn_mode(arg) == mode_M)
116 static spill_t *collect_spill(be_fec_env_t *env, ir_node *node,
117 const ir_mode *mode, int align)
120 int hash = nodeset_hash(node);
122 /* insert into set of spills if not already there */
124 res = set_find(env->spills, &spill, sizeof(spill), hash);
127 spill.spillslot = set_count(env->spills);
129 spill.alignment = align;
130 res = set_insert(env->spills, &spill, sizeof(spill), hash);
132 assert(res->mode == mode);
133 assert(res->alignment == align);
139 static spill_t *collect_memphi(be_fec_env_t *env, ir_node *node,
140 const ir_mode *mode, int align)
144 int hash = nodeset_hash(node);
145 const ir_exec_freq *exec_freq = be_get_birg_exec_freq(env->birg);
147 assert(is_Phi(node));
150 res = set_find(env->spills, &spill, sizeof(spill), hash);
152 assert(res->mode == mode);
153 assert(res->alignment == align);
157 spill.spillslot = set_count(env->spills);
159 spill.alignment = align;
160 res = set_insert(env->spills, &spill, sizeof(spill), hash);
162 // collect attached spills and mem-phis
163 arity = get_irn_arity(node);
164 for(i = 0; i < arity; ++i) {
165 affinity_edge_t *affinty_edge;
166 ir_node *arg = get_irn_n(node, i);
170 arg_spill = collect_memphi(env, arg, mode, align);
172 arg_spill = collect_spill(env, arg, mode, align);
175 // add an affinity edge
176 affinty_edge = obstack_alloc(&env->obst, sizeof(affinty_edge[0]));
177 affinty_edge->affinity = get_block_execfreq(exec_freq, get_nodes_block(arg));
178 affinty_edge->slot1 = res->spillslot;
179 affinty_edge->slot2 = arg_spill->spillslot;
180 ARR_APP1(affinity_edge_t*, env->affinity_edges, affinty_edge);
186 void be_node_needs_frame_entity(be_fec_env_t *env, ir_node *node,
187 const ir_mode *mode, int align)
189 ir_node *spillnode = get_memory_edge(node);
192 assert(spillnode != NULL);
194 if (is_Phi(spillnode)) {
195 spill = collect_memphi(env, spillnode, mode, align);
197 spill = collect_spill(env, spillnode, mode, align);
200 ARR_APP1(ir_node *, env->reloads, node);
205 * / ___|___ __ _| | ___ ___ ___ ___ / ___|| | ___ | |_ ___
206 * | | / _ \ / _` | |/ _ \/ __|/ __/ _ \ \___ \| |/ _ \| __/ __|
207 * | |__| (_) | (_| | | __/\__ \ (_| __/ ___) | | (_) | |_\__ \
208 * \____\___/ \__,_|_|\___||___/\___\___| |____/|_|\___/ \__|___/
211 static int merge_interferences(be_fec_env_t *env, bitset_t** interferences,
212 int* spillslot_unionfind, int s1, int s2)
218 // merge spillslots and interferences
219 res = uf_union(spillslot_unionfind, s1, s2);
220 // we assume that we always merge s2 to s1 so swap s1, s2 if necessary
227 bitset_or(interferences[s1], interferences[s2]);
229 // update other interferences
230 spillcount = set_count(env->spills);
231 for(i = 0; i < spillcount; ++i) {
232 bitset_t *intfs = interferences[i];
233 if(bitset_is_set(intfs, s2))
234 bitset_set(intfs, s1);
241 * A greedy coalescing algorithm for spillslots:
242 * 1. Sort the list of affinity edges
243 * 2. Try to merge slots with affinity edges (most expensive slots first)
244 * 3. Try to merge everything else that is possible
246 static void do_greedy_coalescing(be_fec_env_t *env)
252 int affinity_edge_count;
253 bitset_t **interferences;
254 int* spillslot_unionfind;
255 const be_lv_t *lv = be_get_birg_liveness(env->birg);
257 spillcount = set_count(env->spills);
261 DBG((dbg, DBG_COALESCING, "Coalescing %d spillslots\n", spillcount));
263 interferences = alloca(spillcount * sizeof(interferences[0]));
264 spillslot_unionfind = alloca(spillcount * sizeof(spillslot_unionfind[0]));
265 spilllist = alloca(spillcount * sizeof(spilllist[0]));
267 uf_init(spillslot_unionfind, 0, spillcount);
270 memset(spilllist, 0, spillcount * sizeof(spilllist[0]));
273 for(spill = set_first(env->spills), i = 0; spill != NULL; spill = set_next(env->spills), ++i) {
274 assert(spill->spillslot < spillcount);
275 spilllist[spill->spillslot] = spill;
278 for(i = 0; i < spillcount; ++i) {
279 interferences[i] = bitset_alloca(spillcount);
282 // construct interferences
283 for(i = 0; i < spillcount; ++i) {
284 for(i2 = i+1; i2 < spillcount; ++i2) {
285 if(values_interfere(lv, spilllist[i]->spill, spilllist[i2]->spill)) {
286 DBG((dbg, DBG_INTERFERENCES, "Slot %d and %d interfere\n", i, i2));
287 bitset_set(interferences[i], i2);
288 bitset_set(interferences[i2], i);
293 // sort affinity edges
294 affinity_edge_count = ARR_LEN(env->affinity_edges);
295 qsort(env->affinity_edges, affinity_edge_count, sizeof(env->affinity_edges[0]), cmp_affinity);
297 //dump_interference_graph(env, interferences, "before");
299 // try to merge affine nodes
300 for(i = 0; i < affinity_edge_count; ++i) {
301 const affinity_edge_t *edge = env->affinity_edges[i];
302 int s1 = uf_find(spillslot_unionfind, edge->slot1);
303 int s2 = uf_find(spillslot_unionfind, edge->slot2);
305 /* test if values interfere */
306 if(bitset_is_set(interferences[s1], s2)) {
307 assert(bitset_is_set(interferences[s2], s1));
311 DBG((dbg, DBG_COALESCING, "Merging %d and %d because of affinity edge\n", s1, s2));
313 merge_interferences(env, interferences, spillslot_unionfind, s1, s2);
316 // try to merge as much remaining spillslots as possible
317 for(i = 0; i < spillcount; ++i) {
318 int s1 = uf_find(spillslot_unionfind, i);
322 for(i2 = i+1; i2 < spillcount; ++i2) {
323 int s2 = uf_find(spillslot_unionfind, i2);
327 /* test if values interfere
328 * we have to test n1-n2 and n2-n1, because only 1 side gets updated
329 * when node merging occurs
331 if(bitset_is_set(interferences[s1], s2)) {
332 assert(bitset_is_set(interferences[s2], s1));
336 DBG((dbg, DBG_COALESCING, "Merging %d and %d because it is possible\n", s1, s2));
338 if(merge_interferences(env, interferences, spillslot_unionfind, s1, s2) != 0) {
339 // we can break the loop here, because s2 is the new supernode now
340 // and we'll test s2 again later anyway
346 // assign spillslots to spills
347 for(i = 0; i < spillcount; ++i) {
348 spill_t *spill = spilllist[i];
350 spill->spillslot = uf_find(spillslot_unionfind, i);
353 //dump_interference_graph(env, interferences, "after");
358 * / \ ___ ___(_) __ _ _ __ | ____|_ __ | |_(_) |_(_) ___ ___
359 * / _ \ / __/ __| |/ _` | '_ \ | _| | '_ \| __| | __| |/ _ \/ __|
360 * / ___ \\__ \__ \ | (_| | | | | | |___| | | | |_| | |_| | __/\__ \
361 * /_/ \_\___/___/_|\__, |_| |_| |_____|_| |_|\__|_|\__|_|\___||___/
365 typedef struct _spill_slot_t {
371 typedef struct _memperm_entry_t {
376 struct _memperm_entry_t *next;
379 typedef struct _memperm_t {
382 memperm_entry_t *entries;
385 static int cmp_memperm(const void* d1, const void* d2, size_t size)
387 const memperm_t* e1 = d1;
388 const memperm_t* e2 = d2;
389 return e1->block != e2->block;
392 static memperm_t *get_memperm(be_fec_env_t *env, ir_node *block)
394 memperm_t entry, *res;
398 hash = nodeset_hash(block);
400 res = set_find(env->memperms, &entry, sizeof(entry), hash);
403 entry.entrycount = 0;
404 entry.entries = NULL;
405 res = set_insert(env->memperms, &entry, sizeof(entry), hash);
411 static ir_entity* create_stack_entity(be_fec_env_t *env, spill_slot_t *slot)
413 ir_graph *irg = be_get_birg_irg(env->birg);
414 ir_type *frame = get_irg_frame_type(irg);
415 ir_entity *res = frame_alloc_area(frame, slot->size, slot->align, 0);
417 // adjust size of the entity type...
418 ir_type *enttype = get_entity_type(res);
419 set_type_size_bytes(enttype, slot->size);
427 * Enlarges a spillslot (if necessary) so that it can carry a value of size
428 * @p othersize and alignment @p otheralign.
430 static void enlarge_spillslot(spill_slot_t *slot, int otheralign, int othersize)
432 if(othersize > slot->size) {
433 slot->size = othersize;
435 if(otheralign > slot->align) {
436 if(otheralign % slot->align != 0)
437 slot->align *= otheralign;
439 slot->align = otheralign;
440 } else if(slot->align % otheralign != 0) {
441 slot->align *= otheralign;
446 * Create stack entities for the spillslots and assign them to the spill and
449 static void assign_spillslots(be_fec_env_t *env)
451 const arch_env_t *arch_env = env->arch_env;
455 spill_slot_t* spillslots;
457 spillcount = set_count(env->spills);
458 spillslots = alloca(spillcount * sizeof(spillslots[0]));
460 memset(spillslots, 0, spillcount * sizeof(spillslots[0]));
462 // construct spillslots
463 for(spill = set_first(env->spills); spill != NULL; spill = set_next(env->spills)) {
464 int slotid = spill->spillslot;
465 const ir_mode *mode = spill->mode;
466 spill_slot_t *slot = & (spillslots[slotid]);
467 int size = get_mode_size_bytes(mode);
468 int align = spill->alignment;
470 if(slot->align == 0 && slot->size == 0) {
474 enlarge_spillslot(slot, align, size);
478 for(spill = set_first(env->spills); spill != NULL; spill = set_next(env->spills)) {
480 ir_node *node = spill->spill;
481 int slotid = spill->spillslot;
483 slot = &spillslots[slotid];
484 if(slot->entity == NULL) {
485 create_stack_entity(env, slot);
490 ir_node *block = get_nodes_block(node);
493 assert(is_Phi(node));
495 for(i = 0, arity = get_irn_arity(node); i < arity; ++i) {
496 ir_node *arg = get_irn_n(node, i);
497 ir_node *predblock = get_Block_cfgpred_block(block, i);
501 argspill = get_spill(env, arg);
502 assert(argspill != NULL);
504 argslotid = argspill->spillslot;
505 if(slotid != argslotid) {
507 memperm_entry_t *entry;
508 spill_slot_t *argslot = &spillslots[argslotid];
509 if(argslot->entity == NULL) {
510 create_stack_entity(env, argslot);
513 memperm = get_memperm(env, predblock);
515 entry = obstack_alloc(&env->obst, sizeof(entry[0]));
518 entry->in = argslot->entity;
519 entry->out = slot->entity;
520 entry->next = memperm->entries;
521 memperm->entrycount++;
522 memperm->entries = entry;
526 arch_set_frame_entity(arch_env, node, slot->entity);
530 for(i = 0; i < ARR_LEN(env->reloads); ++i) {
531 ir_node* reload = env->reloads[i];
532 ir_node* spillnode = get_memory_edge(reload);
533 spill_t *spill = get_spill(env, spillnode);
534 const spill_slot_t *slot = & spillslots[spill->spillslot];
536 assert(slot->entity != NULL);
538 arch_set_frame_entity(arch_env, reload, slot->entity);
543 * Returns the last node in a block which is no control flow changing node
545 static ir_node *get_end_of_block_insertion_point(ir_node* block)
547 ir_node* ins = sched_last(block);
548 while(is_Proj(ins) && get_irn_mode(ins) == mode_X) {
549 ins = sched_prev(ins);
555 ir_node *prev = sched_prev(ins);
565 static void create_memperms(be_fec_env_t *env)
567 const arch_env_t *arch_env = env->arch_env;
568 ir_graph *irg = be_get_birg_irg(env->birg);
571 for(memperm = set_first(env->memperms); memperm != NULL; memperm = set_next(env->memperms)) {
573 memperm_entry_t *entry;
575 ir_node** nodes = alloca(memperm->entrycount * sizeof(nodes[0]));
576 ir_node* mempermnode;
578 assert(memperm->entrycount > 0);
580 for(entry = memperm->entries, i = 0; entry != NULL; entry = entry->next, ++i) {
581 ir_node* arg = get_irn_n(entry->node, entry->pos);
585 mempermnode = be_new_MemPerm(arch_env, irg, memperm->block,
586 memperm->entrycount, nodes);
588 // insert node into schedule
589 blockend = get_end_of_block_insertion_point(memperm->block);
590 sched_add_before(blockend, mempermnode);
591 be_stat_ev("mem_perm", memperm->entrycount);
594 for(entry = memperm->entries; entry != NULL; entry = entry->next, ++i) {
596 ir_node* arg = get_irn_n(entry->node, entry->pos);
598 be_set_MemPerm_in_entity(mempermnode, i, entry->in);
599 be_set_MemPerm_out_entity(mempermnode, i, entry->out);
600 set_irg_current_block(irg, memperm->block);
601 proj = new_Proj(mempermnode, get_irn_mode(arg), i);
602 sched_add_before(blockend, proj);
604 set_irn_n(entry->node, entry->pos, proj);
609 static int count_spillslots(const be_fec_env_t *env)
611 const spill_t *spill;
612 int spillcount = set_count(env->spills);
613 bitset_t *counted = bitset_alloca(spillcount);
617 for(spill = set_first(env->spills); spill != NULL;
618 spill = set_next(env->spills)) {
619 int spillslot = spill->spillslot;
620 if(!bitset_is_set(counted, spillslot)) {
622 bitset_set(counted, spillslot);
629 be_fec_env_t *be_new_frame_entity_coalescer(be_irg_t *birg)
631 const arch_env_t *arch_env = birg->main_env->arch_env;
633 be_fec_env_t *env = xmalloc(sizeof(env[0]));
635 be_assure_liveness(birg);
637 obstack_init(&env->obst);
638 env->arch_env = arch_env;
640 env->spills = new_set(cmp_spill, 10);
641 env->reloads = NEW_ARR_F(ir_node*, 0);
642 env->affinity_edges = NEW_ARR_F(affinity_edge_t*, 0);
643 env->memperms = new_set(cmp_memperm, 10);
648 void be_free_frame_entity_coalescer(be_fec_env_t *env)
650 del_set(env->memperms);
651 DEL_ARR_F(env->reloads);
652 DEL_ARR_F(env->affinity_edges);
653 del_set(env->spills);
654 obstack_free(&env->obst, NULL);
659 void be_assign_entities(be_fec_env_t *env)
661 if(be_stat_ev_is_active()) {
662 int count = set_count(env->spills);
663 be_stat_ev("spillslots", count);
666 if(be_coalesce_spill_slots) {
667 do_greedy_coalescing(env);
670 if(be_stat_ev_is_active()) {
671 int count = count_spillslots(env);
672 be_stat_ev("spillslots_after_coalescing", count);
675 assign_spillslots(env);
677 create_memperms(env);
681 * This walker function searches for reloads and collects all the spills
682 * and memphis attached to them.
684 static void collect_spills_walker(ir_node *node, void *data)
686 be_fec_env_t *env = data;
687 const arch_env_t *arch_env = env->arch_env;
689 const arch_register_class_t *cls;
692 /* classify returns classification of the irn the proj is attached to */
696 if (!arch_irn_class_is(arch_env, node, reload))
699 mode = get_irn_mode(node);
700 cls = arch_get_irn_reg_class(arch_env, node, -1);
701 align = arch_isa_get_reg_class_alignment(arch_env_get_isa(arch_env), cls);
703 be_node_needs_frame_entity(env, node, mode, align);
706 void be_coalesce_spillslots(be_irg_t *birg)
708 be_fec_env_t *env = be_new_frame_entity_coalescer(birg);
710 /* collect reloads */
711 irg_walk_graph(birg->irg, NULL, collect_spills_walker, env);
713 be_assign_entities(env);
715 be_free_frame_entity_coalescer(env);
718 void be_init_spillslots(void)
720 FIRM_DBG_REGISTER(dbg, "firm.be.spillslots");
723 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_spillslots);