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 ir_node *spill1 = spilllist[i]->spill;
288 for(i2 = i+1; i2 < spillcount; ++i2) {
289 ir_node *spill2 = spilllist[i2]->spill;
293 if(values_interfere(lv, spill1, spill2)) {
294 DBG((dbg, DBG_INTERFERENCES, "Slot %d and %d interfere\n",
296 bitset_set(interferences[i], i2);
297 bitset_set(interferences[i2], i);
302 // sort affinity edges
303 affinity_edge_count = ARR_LEN(env->affinity_edges);
304 qsort(env->affinity_edges, affinity_edge_count, sizeof(env->affinity_edges[0]), cmp_affinity);
306 //dump_interference_graph(env, interferences, "before");
308 // try to merge affine nodes
309 for(i = 0; i < affinity_edge_count; ++i) {
310 const affinity_edge_t *edge = env->affinity_edges[i];
311 int s1 = uf_find(spillslot_unionfind, edge->slot1);
312 int s2 = uf_find(spillslot_unionfind, edge->slot2);
314 /* test if values interfere */
315 if(bitset_is_set(interferences[s1], s2)) {
316 assert(bitset_is_set(interferences[s2], s1));
320 DBG((dbg, DBG_COALESCING, "Merging %d and %d because of affinity edge\n", s1, s2));
322 merge_interferences(env, interferences, spillslot_unionfind, s1, s2);
325 // try to merge as much remaining spillslots as possible
326 for(i = 0; i < spillcount; ++i) {
327 int s1 = uf_find(spillslot_unionfind, i);
331 for(i2 = i+1; i2 < spillcount; ++i2) {
332 int s2 = uf_find(spillslot_unionfind, i2);
336 /* test if values interfere
337 * we have to test n1-n2 and n2-n1, because only 1 side gets updated
338 * when node merging occurs
340 if(bitset_is_set(interferences[s1], s2)) {
341 assert(bitset_is_set(interferences[s2], s1));
345 DBG((dbg, DBG_COALESCING, "Merging %d and %d because it is possible\n", s1, s2));
347 if(merge_interferences(env, interferences, spillslot_unionfind, s1, s2) != 0) {
348 // we can break the loop here, because s2 is the new supernode now
349 // and we'll test s2 again later anyway
355 // assign spillslots to spills
356 for(i = 0; i < spillcount; ++i) {
357 spill_t *spill = spilllist[i];
359 spill->spillslot = uf_find(spillslot_unionfind, i);
362 //dump_interference_graph(env, interferences, "after");
367 * / \ ___ ___(_) __ _ _ __ | ____|_ __ | |_(_) |_(_) ___ ___
368 * / _ \ / __/ __| |/ _` | '_ \ | _| | '_ \| __| | __| |/ _ \/ __|
369 * / ___ \\__ \__ \ | (_| | | | | | |___| | | | |_| | |_| | __/\__ \
370 * /_/ \_\___/___/_|\__, |_| |_| |_____|_| |_|\__|_|\__|_|\___||___/
374 typedef struct _spill_slot_t {
380 typedef struct _memperm_entry_t {
385 struct _memperm_entry_t *next;
388 typedef struct _memperm_t {
391 memperm_entry_t *entries;
394 static int cmp_memperm(const void* d1, const void* d2, size_t size)
396 const memperm_t* e1 = d1;
397 const memperm_t* e2 = d2;
398 return e1->block != e2->block;
401 static memperm_t *get_memperm(be_fec_env_t *env, ir_node *block)
403 memperm_t entry, *res;
407 hash = nodeset_hash(block);
409 res = set_find(env->memperms, &entry, sizeof(entry), hash);
412 entry.entrycount = 0;
413 entry.entries = NULL;
414 res = set_insert(env->memperms, &entry, sizeof(entry), hash);
420 static ir_entity* create_stack_entity(be_fec_env_t *env, spill_slot_t *slot)
422 ir_graph *irg = be_get_birg_irg(env->birg);
423 ir_type *frame = get_irg_frame_type(irg);
424 ir_entity *res = frame_alloc_area(frame, slot->size, slot->align, 0);
426 // adjust size of the entity type...
427 ir_type *enttype = get_entity_type(res);
428 set_type_size_bytes(enttype, slot->size);
436 * Enlarges a spillslot (if necessary) so that it can carry a value of size
437 * @p othersize and alignment @p otheralign.
439 static void enlarge_spillslot(spill_slot_t *slot, int otheralign, int othersize)
441 if(othersize > slot->size) {
442 slot->size = othersize;
444 if(otheralign > slot->align) {
445 if(otheralign % slot->align != 0)
446 slot->align *= otheralign;
448 slot->align = otheralign;
449 } else if(slot->align % otheralign != 0) {
450 slot->align *= otheralign;
455 * Create stack entities for the spillslots and assign them to the spill and
458 static void assign_spillslots(be_fec_env_t *env)
460 const arch_env_t *arch_env = env->arch_env;
464 spill_slot_t* spillslots;
466 spillcount = set_count(env->spills);
467 spillslots = alloca(spillcount * sizeof(spillslots[0]));
469 memset(spillslots, 0, spillcount * sizeof(spillslots[0]));
471 // construct spillslots
472 for(spill = set_first(env->spills); spill != NULL; spill = set_next(env->spills)) {
473 int slotid = spill->spillslot;
474 const ir_mode *mode = spill->mode;
475 spill_slot_t *slot = & (spillslots[slotid]);
476 int size = get_mode_size_bytes(mode);
477 int align = spill->alignment;
479 if(slot->align == 0 && slot->size == 0) {
483 enlarge_spillslot(slot, align, size);
487 for(spill = set_first(env->spills); spill != NULL; spill = set_next(env->spills)) {
489 ir_node *node = spill->spill;
490 int slotid = spill->spillslot;
492 slot = &spillslots[slotid];
493 if(slot->entity == NULL) {
494 create_stack_entity(env, slot);
499 ir_node *block = get_nodes_block(node);
502 assert(is_Phi(node));
504 for(i = 0, arity = get_irn_arity(node); i < arity; ++i) {
505 ir_node *arg = get_irn_n(node, i);
506 ir_node *predblock = get_Block_cfgpred_block(block, i);
510 argspill = get_spill(env, arg);
511 assert(argspill != NULL);
513 argslotid = argspill->spillslot;
514 if(slotid != argslotid) {
516 memperm_entry_t *entry;
517 spill_slot_t *argslot = &spillslots[argslotid];
518 if(argslot->entity == NULL) {
519 create_stack_entity(env, argslot);
522 memperm = get_memperm(env, predblock);
524 entry = obstack_alloc(&env->obst, sizeof(entry[0]));
527 entry->in = argslot->entity;
528 entry->out = slot->entity;
529 entry->next = memperm->entries;
530 memperm->entrycount++;
531 memperm->entries = entry;
536 arch_set_frame_entity(arch_env, node, slot->entity);
540 for(i = 0; i < ARR_LEN(env->reloads); ++i) {
541 ir_node* reload = env->reloads[i];
542 ir_node* spillnode = get_memory_edge(reload);
543 spill_t *spill = get_spill(env, spillnode);
544 const spill_slot_t *slot = & spillslots[spill->spillslot];
546 assert(slot->entity != NULL);
548 arch_set_frame_entity(arch_env, reload, slot->entity);
553 * Returns the last node in a block which is no control flow changing node
555 static ir_node *get_end_of_block_insertion_point(ir_node* block)
557 ir_node* ins = sched_last(block);
558 while(is_Proj(ins) && get_irn_mode(ins) == mode_X) {
559 ins = sched_prev(ins);
565 ir_node *prev = sched_prev(ins);
575 static void create_memperms(be_fec_env_t *env)
577 const arch_env_t *arch_env = env->arch_env;
578 ir_graph *irg = be_get_birg_irg(env->birg);
581 for(memperm = set_first(env->memperms); memperm != NULL; memperm = set_next(env->memperms)) {
583 memperm_entry_t *entry;
585 ir_node** nodes = alloca(memperm->entrycount * sizeof(nodes[0]));
586 ir_node* mempermnode;
588 assert(memperm->entrycount > 0);
590 for(entry = memperm->entries, i = 0; entry != NULL; entry = entry->next, ++i) {
591 ir_node* arg = get_irn_n(entry->node, entry->pos);
595 mempermnode = be_new_MemPerm(arch_env, irg, memperm->block,
596 memperm->entrycount, nodes);
598 // insert node into schedule
599 blockend = get_end_of_block_insertion_point(memperm->block);
600 sched_add_before(blockend, mempermnode);
601 be_stat_ev("mem_perm", memperm->entrycount);
604 for(entry = memperm->entries; entry != NULL; entry = entry->next, ++i) {
606 ir_node* arg = get_irn_n(entry->node, entry->pos);
608 be_set_MemPerm_in_entity(mempermnode, i, entry->in);
609 be_set_MemPerm_out_entity(mempermnode, i, entry->out);
610 set_irg_current_block(irg, memperm->block);
611 proj = new_Proj(mempermnode, get_irn_mode(arg), i);
612 sched_add_before(blockend, proj);
614 set_irn_n(entry->node, entry->pos, proj);
619 static int count_spillslots(const be_fec_env_t *env)
621 const spill_t *spill;
622 int spillcount = set_count(env->spills);
623 bitset_t *counted = bitset_alloca(spillcount);
627 for(spill = set_first(env->spills); spill != NULL;
628 spill = set_next(env->spills)) {
629 int spillslot = spill->spillslot;
630 if(!bitset_is_set(counted, spillslot)) {
632 bitset_set(counted, spillslot);
639 be_fec_env_t *be_new_frame_entity_coalescer(be_irg_t *birg)
641 const arch_env_t *arch_env = birg->main_env->arch_env;
643 be_fec_env_t *env = xmalloc(sizeof(env[0]));
645 be_assure_liveness(birg);
647 obstack_init(&env->obst);
648 env->arch_env = arch_env;
650 env->spills = new_set(cmp_spill, 10);
651 env->reloads = NEW_ARR_F(ir_node*, 0);
652 env->affinity_edges = NEW_ARR_F(affinity_edge_t*, 0);
653 env->memperms = new_set(cmp_memperm, 10);
658 void be_free_frame_entity_coalescer(be_fec_env_t *env)
660 del_set(env->memperms);
661 DEL_ARR_F(env->reloads);
662 DEL_ARR_F(env->affinity_edges);
663 del_set(env->spills);
664 obstack_free(&env->obst, NULL);
669 void be_assign_entities(be_fec_env_t *env)
671 if(be_stat_ev_is_active()) {
672 int count = set_count(env->spills);
673 be_stat_ev("spillslots", count);
676 if(be_coalesce_spill_slots) {
677 do_greedy_coalescing(env);
680 if(be_stat_ev_is_active()) {
681 int count = count_spillslots(env);
682 be_stat_ev("spillslots_after_coalescing", count);
685 assign_spillslots(env);
687 create_memperms(env);
691 * This walker function searches for reloads and collects all the spills
692 * and memphis attached to them.
694 static void collect_spills_walker(ir_node *node, void *data)
696 be_fec_env_t *env = data;
697 const arch_env_t *arch_env = env->arch_env;
699 const arch_register_class_t *cls;
702 /* classify returns classification of the irn the proj is attached to */
706 if (!arch_irn_class_is(arch_env, node, reload))
709 mode = get_irn_mode(node);
710 cls = arch_get_irn_reg_class(arch_env, node, -1);
711 align = arch_isa_get_reg_class_alignment(arch_env_get_isa(arch_env), cls);
713 be_node_needs_frame_entity(env, node, mode, align);
716 void be_coalesce_spillslots(be_irg_t *birg)
718 be_fec_env_t *env = be_new_frame_entity_coalescer(birg);
720 /* collect reloads */
721 irg_walk_graph(birg->irg, NULL, collect_spills_walker, env);
723 be_assign_entities(env);
725 be_free_frame_entity_coalescer(env);
728 void be_init_spillslots(void)
730 FIRM_DBG_REGISTER(dbg, "firm.be.spillslots");
733 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_spillslots);