2 * This file is part of libFirm.
3 * Copyright (C) 2012 University of Karlsruhe.
8 * @brief Spillslot coalescer.
9 * @author Matthias Braun
22 #include "unionfind.h"
28 #include "bespillslots.h"
29 #include "bechordal_t.h"
32 #include "beintlive_t.h"
35 #include "bespillutil.h"
37 #define DBG_COALESCING 1
38 #define DBG_INTERFERENCES 2
40 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
42 typedef struct spill_t {
44 const ir_mode *mode; /**< mode of the spilled value */
45 int alignment; /**< alignment for the spilled value */
49 typedef struct affinity_edge_t {
61 affinity_edge_t **affinity_edges;
63 set_frame_entity_func set_frame_entity;
64 bool at_begin; /**< frame entities should be allocate at
65 the beginning of the stackframe */
68 /** Compare 2 affinity edges (used in quicksort) */
69 static int cmp_affinity(const void *d1, const void *d2)
71 const affinity_edge_t * const *e1 = (const affinity_edge_t**)d1;
72 const affinity_edge_t * const *e2 = (const affinity_edge_t**)d2;
73 double aff1 = (*e1)->affinity;
74 double aff2 = (*e2)->affinity;
76 /* sort in descending order */
79 } else if (aff1 > aff2) {
82 int slot11 = (*e1)->slot1;
83 int slot21 = (*e2)->slot1;
84 if (slot11 < slot21) {
86 } else if (slot11 > slot21) {
89 int slot12 = (*e1)->slot2;
90 int slot22 = (*e2)->slot2;
91 return (slot12<slot22) - (slot12<slot22);
96 static spill_t *get_spill(be_fec_env_t *env, ir_node *node)
98 assert(rbitset_is_set(env->spills_set, get_irn_idx(node)));
99 return (spill_t*)get_irn_link(node);
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)
121 /* already in spill set? */
122 unsigned idx = get_irn_idx(node);
123 if (rbitset_is_set(env->spills_set, idx)) {
124 spill_t *spill = get_spill(env, node);
125 assert(spill->mode == mode);
126 assert(spill->alignment == align);
129 rbitset_set(env->spills_set, idx);
131 spill = OALLOC(&env->obst, spill_t);
132 /* insert into set of spills if not already there */
135 spill->alignment = align;
136 spill->spillslot = (int)ARR_LEN(env->spills);
137 ARR_APP1(spill_t*, env->spills, spill);
138 set_irn_link(node, spill);
139 DB((dbg, DBG_COALESCING, "Slot %d: %+F\n", spill->spillslot, node));
142 int arity = get_irn_arity(node);
144 for (i = 0; i < arity; ++i) {
145 affinity_edge_t *affinty_edge;
146 ir_node *arg = get_irn_n(node, i);
147 spill_t *arg_spill = collect_spill(env, arg, mode, align);
148 ir_node *block = get_nodes_block(arg);
150 /* add an affinity edge */
151 affinty_edge = OALLOC(&env->obst, affinity_edge_t);
152 affinty_edge->affinity = get_block_execfreq(block);
153 affinty_edge->slot1 = spill->spillslot;
154 affinty_edge->slot2 = arg_spill->spillslot;
155 ARR_APP1(affinity_edge_t*, env->affinity_edges, affinty_edge);
162 void be_node_needs_frame_entity(be_fec_env_t *env, ir_node *node,
163 const ir_mode *mode, int align)
165 ir_node *spillnode = get_memory_edge(node);
166 assert(spillnode != NULL);
168 /* walk upwards and collect all phis and spills on this way */
169 collect_spill(env, spillnode, mode, align);
171 ARR_APP1(ir_node *, env->reloads, node);
174 static int merge_interferences(be_fec_env_t *env, bitset_t** interferences,
175 int* spillslot_unionfind, int s1, int s2)
181 /* merge spillslots and interferences */
182 res = uf_union(spillslot_unionfind, s1, s2);
183 /* we assume that we always merge s2 to s1 so swap s1, s2 if necessary */
190 bitset_or(interferences[s1], interferences[s2]);
192 /* update other interferences */
193 spillcount = ARR_LEN(env->spills);
194 for (i = 0; i < spillcount; ++i) {
195 bitset_t *intfs = interferences[i];
196 if (bitset_is_set(intfs, s2))
197 bitset_set(intfs, s1);
203 static bool my_values_interfere2(ir_graph *const irg, ir_node const *a, ir_node const *b)
205 if (value_dominates(b, a)) {
206 /* Adjust a and b so, that a dominates b if
207 * a dominates b or vice versa. */
208 ir_node const *const t = a;
211 } else if (!value_dominates(a, b)) {
212 /* If there is no dominance relation, they do not interfere. */
216 ir_node *const bb = get_nodes_block(b);
218 /* If a is live end in b's block it is
219 * live at b's definition (a dominates b) */
220 be_lv_t *const lv = be_get_irg_liveness(irg);
221 if (be_is_live_end(lv, bb, a))
224 /* Look at all usages of a.
225 * If there's one usage of a in the block of b, then
226 * we check, if this use is dominated by b, if that's true
227 * a and b interfere. Note that b must strictly dominate the user,
228 * since if b is the last user of in the block, b and a do not
230 * Uses of a not in b's block can be disobeyed, because the
231 * check for a being live at the end of b's block is already
233 foreach_out_edge(a, edge) {
234 ir_node const *const user = get_edge_src_irn(edge);
236 foreach_out_edge(user, edge2) {
237 ir_node const *const user2 = get_edge_src_irn(edge2);
238 assert(!is_Sync(user2));
239 if (get_nodes_block(user2) == bb && !is_Phi(user2) &&
240 _value_strictly_dominates_intrablock(b, user2))
244 if (get_nodes_block(user) == bb && !is_Phi(user) &&
245 _value_strictly_dominates_intrablock(b, user))
254 * same as values_interfere but with special handling for Syncs
256 static int my_values_interfere(ir_graph *irg, ir_node *a, ir_node *b)
259 int i, arity = get_irn_arity(a);
260 for (i = 0; i < arity; ++i) {
261 ir_node *in = get_irn_n(a, i);
262 if (my_values_interfere(irg, in, b))
266 } else if (is_Sync(b)) {
267 int i, arity = get_irn_arity(b);
268 for (i = 0; i < arity; ++i) {
269 ir_node *in = get_irn_n(b, i);
270 /* a is not a sync, so no need for my_values_interfere */
271 if (my_values_interfere2(irg, a, in))
277 return my_values_interfere2(irg, a, b);
281 * A greedy coalescing algorithm for spillslots:
282 * 1. Sort the list of affinity edges
283 * 2. Try to merge slots with affinity edges (most expensive slots first)
284 * 3. Try to merge everything else that is possible
286 static void do_greedy_coalescing(be_fec_env_t *env)
288 spill_t **spills = env->spills;
289 size_t spillcount = ARR_LEN(spills);
291 size_t affinity_edge_count;
292 bitset_t **interferences;
293 int* spillslot_unionfind;
301 DB((dbg, DBG_COALESCING, "Coalescing %d spillslots\n", spillcount));
303 interferences = OALLOCN(&data, bitset_t*, spillcount);
304 spillslot_unionfind = OALLOCN(&data, int, spillcount);
306 uf_init(spillslot_unionfind, spillcount);
308 for (i = 0; i < spillcount; ++i) {
309 interferences[i] = bitset_obstack_alloc(&data, spillcount);
312 /* construct interferences */
313 for (i = 0; i < spillcount; ++i) {
315 ir_node *spill1 = spills[i]->spill;
316 if (is_NoMem(spill1))
319 for (i2 = i+1; i2 < spillcount; ++i2) {
320 ir_node *spill2 = spills[i2]->spill;
321 if (is_NoMem(spill2))
324 if (my_values_interfere(env->irg, spill1, spill2)) {
325 DB((dbg, DBG_INTERFERENCES,
326 "Slot %d and %d interfere\n", i, i2));
328 bitset_set(interferences[i], i2);
329 bitset_set(interferences[i2], i);
334 /* sort affinity edges */
335 affinity_edge_count = ARR_LEN(env->affinity_edges);
336 qsort(env->affinity_edges, affinity_edge_count,
337 sizeof(env->affinity_edges[0]), cmp_affinity);
339 /* try to merge affine nodes */
340 for (i = 0; i < affinity_edge_count; ++i) {
341 const affinity_edge_t *edge = env->affinity_edges[i];
342 int s1 = uf_find(spillslot_unionfind, edge->slot1);
343 int s2 = uf_find(spillslot_unionfind, edge->slot2);
345 /* test if values interfere */
346 if (bitset_is_set(interferences[s1], s2)) {
347 assert(bitset_is_set(interferences[s2], s1));
351 DB((dbg, DBG_COALESCING,
352 "Merging %d and %d because of affinity edge\n", s1, s2));
354 merge_interferences(env, interferences, spillslot_unionfind, s1, s2);
357 /* try to merge as much remaining spillslots as possible */
358 for (i = 0; i < spillcount; ++i) {
360 int s1 = uf_find(spillslot_unionfind, i);
364 for (i2 = i+1; i2 < spillcount; ++i2) {
365 int s2 = uf_find(spillslot_unionfind, i2);
369 /* test if values interfere
370 * we have to test n1-n2 and n2-n1, because only 1 side gets updated
371 * when node merging occurs
373 if (bitset_is_set(interferences[s1], s2)) {
374 assert(bitset_is_set(interferences[s2], s1));
378 DB((dbg, DBG_COALESCING,
379 "Merging %d and %d because it is possible\n", s1, s2));
381 if (merge_interferences(env, interferences, spillslot_unionfind, s1, s2) != 0) {
382 /* we can break the loop here, because s2 is the new supernode
383 * now and we'll test s2 again later anyway */
389 /* assign spillslots to spills */
390 for (i = 0; i < spillcount; ++i) {
391 spills[i]->spillslot = uf_find(spillslot_unionfind, i);
394 obstack_free(&data, 0);
397 typedef struct spill_slot_t {
403 typedef struct memperm_entry_t {
408 struct memperm_entry_t *next;
411 typedef struct memperm_t {
414 memperm_entry_t *entries;
417 static int cmp_memperm(const void* d1, const void* d2, size_t size)
419 const memperm_t* e1 = (const memperm_t*)d1;
420 const memperm_t* e2 = (const memperm_t*)d2;
423 return e1->block != e2->block;
426 static memperm_t *get_memperm(be_fec_env_t *env, ir_node *block)
428 memperm_t entry, *res;
432 hash = hash_irn(block);
434 res = set_find(memperm_t, env->memperms, &entry, sizeof(entry), hash);
437 entry.entrycount = 0;
438 entry.entries = NULL;
439 res = set_insert(memperm_t, env->memperms, &entry, sizeof(entry), hash);
445 static ir_entity* create_stack_entity(be_fec_env_t *env, spill_slot_t *slot)
447 ir_graph *irg = env->irg;
448 ir_type *frame = get_irg_frame_type(irg);
449 ir_entity *res = frame_alloc_area(frame, slot->size, slot->align,
457 * Enlarges a spillslot (if necessary) so that it can carry a value of size
458 * @p othersize and alignment @p otheralign.
460 static void enlarge_spillslot(spill_slot_t *slot, int otheralign, int othersize)
462 if (othersize > slot->size) {
463 slot->size = othersize;
465 if (otheralign > slot->align) {
466 if (otheralign % slot->align != 0)
467 slot->align *= otheralign;
469 slot->align = otheralign;
470 } else if (slot->align % otheralign != 0) {
471 slot->align *= otheralign;
475 static void assign_spill_entity(be_fec_env_t *env,
476 ir_node *node, ir_entity *entity)
483 arity = get_irn_arity(node);
484 for (i = 0; i < arity; ++i) {
485 ir_node *in = get_irn_n(node, i);
488 assign_spill_entity(env, in, entity);
493 /* beware: we might have Stores with Memory Proj's, ia32 fisttp for
495 node = skip_Proj(node);
496 assert(arch_get_frame_entity(node) == NULL);
497 env->set_frame_entity(node, entity);
501 * Create stack entities for the spillslots and assign them to the spill and
504 static void assign_spillslots(be_fec_env_t *env)
506 spill_t **spills = env->spills;
507 size_t spillcount = ARR_LEN(spills);
508 spill_slot_t *spillslots = ALLOCANZ(spill_slot_t, spillcount);
511 /* construct spillslots */
512 for (s = 0; s < spillcount; ++s) {
513 const spill_t *spill = spills[s];
514 int slotid = spill->spillslot;
515 const ir_mode *mode = spill->mode;
516 spill_slot_t *slot = & (spillslots[slotid]);
517 int size = get_mode_size_bytes(mode);
518 int align = spill->alignment;
520 if (slot->align == 0 && slot->size == 0) {
524 enlarge_spillslot(slot, align, size);
528 for (s = 0; s < spillcount; ++s) {
529 const spill_t *spill = spills[s];
530 ir_node *node = spill->spill;
531 int slotid = spill->spillslot;
532 spill_slot_t *slot = &spillslots[slotid];
534 if (slot->entity == NULL) {
535 create_stack_entity(env, slot);
539 int arity = get_irn_arity(node);
541 ir_node *block = get_nodes_block(node);
543 /* should be a PhiM */
544 assert(get_irn_mode(node) == mode_M);
546 for (i = 0; i < arity; ++i) {
547 ir_node *arg = get_irn_n(node, i);
548 ir_node *predblock = get_Block_cfgpred_block(block, i);
549 spill_t *argspill = get_spill(env, arg);
550 int argslotid = argspill->spillslot;
552 if (slotid != argslotid) {
554 memperm_entry_t *entry;
555 spill_slot_t *argslot = &spillslots[argslotid];
556 if (argslot->entity == NULL) {
557 create_stack_entity(env, argslot);
560 memperm = get_memperm(env, predblock);
562 entry = OALLOC(&env->obst, memperm_entry_t);
565 entry->in = argslot->entity;
566 entry->out = slot->entity;
567 entry->next = memperm->entries;
568 memperm->entrycount++;
569 memperm->entries = entry;
573 assign_spill_entity(env, node, slot->entity);
577 for (s = 0; s < ARR_LEN(env->reloads); ++s) {
578 ir_node *reload = env->reloads[s];
579 ir_node *spillnode = get_memory_edge(reload);
580 const spill_t *spill = get_spill(env, spillnode);
581 const spill_slot_t *slot = &spillslots[spill->spillslot];
583 assert(slot->entity != NULL);
585 env->set_frame_entity(reload, slot->entity);
589 static void create_memperms(be_fec_env_t *env)
591 foreach_set(env->memperms, memperm_t, memperm) {
592 ir_node **nodes = ALLOCAN(ir_node*, memperm->entrycount);
593 memperm_entry_t *entry;
594 ir_node *mempermnode;
597 assert(memperm->entrycount > 0);
599 for (entry = memperm->entries, i = 0; entry != NULL; entry = entry->next, ++i) {
600 ir_node* arg = get_irn_n(entry->node, entry->pos);
604 mempermnode = be_new_MemPerm(memperm->block, memperm->entrycount,
607 /* insert node into schedule */
608 ir_node *const blockend = be_get_end_of_block_insertion_point(memperm->block);
609 sched_add_before(blockend, mempermnode);
610 stat_ev_dbl("mem_perm", memperm->entrycount);
613 for (entry = memperm->entries; entry != NULL; entry = entry->next, ++i) {
615 ir_node* arg = get_irn_n(entry->node, entry->pos);
617 be_set_MemPerm_in_entity(mempermnode, i, entry->in);
618 be_set_MemPerm_out_entity(mempermnode, i, entry->out);
619 proj = new_r_Proj(mempermnode, get_irn_mode(arg), i);
621 set_irn_n(entry->node, entry->pos, proj);
626 static unsigned count_spillslots(const be_fec_env_t *env)
628 size_t spillcount = ARR_LEN(env->spills);
629 unsigned slotcount = 0;
632 unsigned *const counted = rbitset_alloca(spillcount);
633 for (s = 0; s < spillcount; ++s) {
634 spill_t *spill = env->spills[s];
635 int spillslot = spill->spillslot;
636 if (!rbitset_is_set(counted, spillslot)) {
638 rbitset_set(counted, spillslot);
645 be_fec_env_t *be_new_frame_entity_coalescer(ir_graph *irg)
647 be_fec_env_t *env = XMALLOCZ(be_fec_env_t);
649 be_assure_live_chk(irg);
651 obstack_init(&env->obst);
653 env->spills = NEW_ARR_F(spill_t*, 0);
654 env->spills_set = rbitset_malloc(get_irg_last_idx(irg));
655 env->reloads = NEW_ARR_F(ir_node*, 0);
656 env->affinity_edges = NEW_ARR_F(affinity_edge_t*, 0);
657 env->memperms = new_set(cmp_memperm, 10);
659 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
664 void be_free_frame_entity_coalescer(be_fec_env_t *env)
666 ir_free_resources(env->irg, IR_RESOURCE_IRN_LINK);
668 del_set(env->memperms);
669 DEL_ARR_F(env->reloads);
670 DEL_ARR_F(env->affinity_edges);
671 DEL_ARR_F(env->spills);
672 xfree(env->spills_set);
673 obstack_free(&env->obst, NULL);
678 void be_assign_entities(be_fec_env_t *env,
679 set_frame_entity_func set_frame_entity,
680 bool alloc_entities_at_begin)
682 env->set_frame_entity = set_frame_entity;
683 env->at_begin = alloc_entities_at_begin;
685 if (stat_ev_enabled) {
686 stat_ev_dbl("spillslots", ARR_LEN(env->spills));
689 if (be_coalesce_spill_slots) {
690 do_greedy_coalescing(env);
693 if (stat_ev_enabled) {
694 stat_ev_dbl("spillslots_after_coalescing", count_spillslots(env));
697 assign_spillslots(env);
699 create_memperms(env);
702 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_spillslots)
703 void be_init_spillslots(void)
705 FIRM_DBG_REGISTER(dbg, "firm.be.spillslots");