+
+ be_liveness_add_missing(env->chordal_env->lv);
+}
+
+void be_add_reload_on_edge(spill_env_t *env, ir_node *to_spill, ir_node *block, int pos) {
+ ir_node *predblock, *last;
+
+ /* simply add the reload to the beginning of the block if we only have 1 predecessor
+ * (we don't need to check for phis as there can't be any in a block with only 1 pred)
+ */
+ if(get_Block_n_cfgpreds(block) == 1) {
+ assert(!is_Phi(sched_first(block)));
+ be_add_reload(env, to_spill, sched_first(block));
+ return;
+ }
+
+ /* We have to reload the value in pred-block */
+ predblock = get_Block_cfgpred_block(block, pos);
+ last = sched_last(predblock);
+
+ /* we might have projs and keepanys behind the jump... */
+ while(is_Proj(last) || be_is_Keep(last)) {
+ last = sched_prev(last);
+ assert(!sched_is_end(last));
+ }
+ assert(is_cfop(last));
+
+ // add the reload before the (cond-)jump
+ be_add_reload(env, to_spill, last);
+}
+
+/****************************************
+
+ SPILL SLOT MANAGEMENT AND OPTS
+
+****************************************/
+
+typedef struct _spill_slot_t {
+ unsigned size;
+ unsigned align;
+ pset *members;
+ ir_mode *largest_mode; /* the mode of all members with largest size */
+} spill_slot_t;
+
+typedef struct _ss_env_t {
+ struct obstack ob;
+ be_chordal_env_t *cenv;
+ pmap *slots; /* maps spill_contexts to spill_slots */
+ pmap *types; /* maps modes to types */
+ DEBUG_ONLY(firm_dbg_module_t *dbg;)
+} ss_env_t;
+
+
+/**
+ * Walker: compute the spill slots
+ */
+static void compute_spill_slots_walker(ir_node *spill, void *env) {
+ ss_env_t *ssenv = env;
+ arch_env_t *arch_env = ssenv->cenv->birg->main_env->arch_env;
+ ir_node *ctx;
+ pmap_entry *entry;
+ spill_slot_t *ss;
+ const arch_register_class_t *cls;
+
+ if (! be_is_Spill(spill))
+ return;
+
+ cls = arch_get_irn_reg_class(arch_env, spill, be_pos_Spill_val);
+
+ if (cls != ssenv->cenv->cls)
+ return;
+
+ /* check, if this spill is for a context already known */
+ ctx = be_get_Spill_context(spill);
+ entry = pmap_find(ssenv->slots, ctx);
+
+ if (! entry) {
+ ir_mode *largest_mode = arch_register_class_mode(cls);
+
+ /* this is a new spill context */
+ ss = obstack_alloc(&ssenv->ob, sizeof(*ss));
+ ss->members = pset_new_ptr(8);
+ ss->largest_mode = largest_mode;
+ ss->size = get_mode_size_bytes(ss->largest_mode);
+ ss->align = arch_isa_get_reg_class_alignment(arch_env->isa, cls);
+ pmap_insert(ssenv->slots, ctx, ss);
+ } else {
+ /* values with the same spill_ctx must go into the same spill slot */
+ ss = entry->value;
+
+#ifndef NDEBUG
+ /* ugly mega assert :-) */
+ {
+ ir_node *irn;
+ struct _arch_env_t *arch_env = ssenv->cenv->birg->main_env->arch_env;
+ const arch_register_class_t *cls = arch_get_irn_reg_class(arch_env, spill, be_pos_Spill_val);
+ int size = get_mode_size_bytes(arch_register_class_mode(cls));
+ assert((int) ss->size == size && "Different sizes for the same spill slot are not allowed.");
+ for (irn = pset_first(ss->members); irn; irn = pset_next(ss->members)) {
+ /* use values_interfere here, because it uses the dominance check,
+ which does work for values in memory */
+ assert(!values_interfere(ssenv->cenv->lv, spill, irn) && "Spills for the same spill slot must not interfere!");
+ }
+ }
+#endif /* NDEBUG */
+ }
+
+ pset_insert_ptr(ss->members, spill);
+}
+
+/**
+ * qsort compare function, sort spill slots by size.
+ */
+static int ss_sorter(const void *v1, const void *v2) {
+ const spill_slot_t **ss1 = (const spill_slot_t **)v1;
+ const spill_slot_t **ss2 = (const spill_slot_t **)v2;
+ return ((int) (*ss2)->size) - ((int) (*ss1)->size);
+}
+
+
+/**
+ * This function should optimize the spill slots.
+ * - Coalescing of multiple slots
+ * - Ordering the slots
+ *
+ * Input slots are in @p ssenv->slots
+ * @p size The count of initial spill slots in @p ssenv->slots
+ * This also is the size of the preallocated array @p ass
+ *
+ * @return An array of spill slots @p ass in specific order
+ **/
+static void optimize_slots(ss_env_t *ssenv, int size, spill_slot_t *ass[]) {
+ int i, o, used_slots;
+ pmap_entry *entr;
+
+ i=0;
+ pmap_foreach(ssenv->slots, entr)
+ ass[i++] = entr->value;
+
+ /* Sort the array to minimize fragmentation and cache footprint.
+ Large slots come first */
+ qsort(ass, size, sizeof(ass[0]), ss_sorter);
+
+ /* For each spill slot:
+ - assign a new offset to this slot
+ - xor find another slot to coalesce with */
+ used_slots = 0;
+ for (i=0; i<size; ++i) {
+ /* for each spill slot */
+ ir_node *n1;
+ int tgt_slot = -1;
+
+ DBG((ssenv->dbg, LEVEL_1, "Spill slot %d members:\n", i));
+ for(n1 = pset_first(ass[i]->members); n1; n1 = pset_next(ass[i]->members))
+ DBG((ssenv->dbg, LEVEL_1, " %+F\n", n1));
+
+
+ for (o=0; o < used_slots && tgt_slot == -1; ++o) { /* for each offset-assigned spill slot */
+ /* check inter-slot-pairs for interference */
+ ir_node *n2;
+ for(n1 = pset_first(ass[i]->members); n1; n1 = pset_next(ass[i]->members))
+ for(n2 = pset_first(ass[o]->members); n2; n2 = pset_next(ass[o]->members))
+ if(values_interfere(ssenv->cenv->lv, n1, n2)) {
+ pset_break(ass[i]->members);
+ pset_break(ass[o]->members);
+ DBG((ssenv->dbg, LEVEL_1, " Interf %+F -- %+F\n", n1, n2));
+ goto interf_detected;
+ }
+
+ /* if we are here, there is no interference between ass[i] and ass[o] */
+ tgt_slot = o;
+
+interf_detected: /*nothing*/ ;
+ }
+
+ /* now the members of ass[i] join the members of ass[tgt_slot] */
+
+ /* do we need a new slot? */
+ if (tgt_slot == -1) {
+ tgt_slot = used_slots;
+ used_slots++;
+
+ /* init slot */
+ if (tgt_slot != i) {
+ ass[tgt_slot]->size = ass[i]->size;
+ del_pset(ass[tgt_slot]->members);
+ ass[tgt_slot]->members = pset_new_ptr(8);
+ }
+ }
+
+ /* copy the members to the target pset */
+ /* NOTE: If src and tgt pset are the same, inserting while iterating is not allowed */
+ if (tgt_slot != i)
+ for(n1 = pset_first(ass[i]->members); n1; n1 = pset_next(ass[i]->members))
+ pset_insert_ptr(ass[tgt_slot]->members, n1);
+ }
+}
+
+#define ALIGN_SPILL_AREA 16
+#define pset_foreach(pset, elm) for(elm=pset_first(pset); elm; elm=pset_next(pset))
+
+/**
+ * Returns a spill type for a mode. Keep them in a map to reduce
+ * the number of types.
+ *
+ * @param types a map containing all created types
+ * @param ss the spill slot
+ *
+ * Note that type types should are identical for every mode.
+ * This rule might break if two different register classes return the same
+ * mode but different alignments.
+ */
+static ir_type *get_spill_type(pmap *types, spill_slot_t *ss) {
+ pmap_entry *e = pmap_find(types, ss->largest_mode);
+ ir_type *res;
+
+ if (! e) {
+ char buf[64];
+ snprintf(buf, sizeof(buf), "spill_slot_type_%s", get_mode_name(ss->largest_mode));
+ buf[sizeof(buf) - 1] = '\0';
+ res = new_type_primitive(new_id_from_str(buf), ss->largest_mode);
+ set_type_alignment_bytes(res, ss->align);
+ pmap_insert(types, ss->largest_mode, res);
+ } else {
+ res = e->value;
+ assert(get_type_alignment_bytes(res) == (int)ss->align);
+ }
+
+ return res;
+}
+
+/**
+ * Create spill slot entities on the frame type.
+ *
+ * @param ssenv the spill environment
+ * @param n number of spill slots
+ * @param ss array of spill slots
+ */
+static void assign_entities(ss_env_t *ssenv, int n_slots, spill_slot_t *ss[]) {
+ int i, offset, frame_align;
+ ir_type *frame;
+
+ /* do not align the frame if no spill slots are needed */
+ if (n_slots <= 0)
+ return;
+
+ frame = get_irg_frame_type(ssenv->cenv->irg);
+
+ /* aligning by increasing frame size */
+ offset = get_type_size_bytes(frame);
+ offset = round_up2(offset, ALIGN_SPILL_AREA);
+
+ /* create entities and assign offsets according to size and alignment*/
+ for (i = 0; i < n_slots; ++i) {
+ char buf[64];
+ ident *name;
+ entity *spill_ent;
+ ir_node *irn;
+
+ /* build entity */
+ snprintf(buf, sizeof(buf), "spill_slot_%d", i);
+ buf[sizeof(buf) - 1] = '\0';
+ name = new_id_from_str(buf);
+
+ spill_ent = new_entity(frame, name, get_spill_type(ssenv->types, ss[i]));
+
+ /* align */
+ offset = round_up2(offset, ss[i]->align);
+ /* set */
+ set_entity_offset_bytes(spill_ent, offset);
+ /* next possible offset */
+ offset += round_up2(ss[i]->size, ss[i]->align);
+
+ pset_foreach(ss[i]->members, irn)
+ be_set_Spill_entity(irn, spill_ent);
+ }
+
+
+ /* set final size of stack frame */
+ frame_align = get_type_alignment_bytes(frame);
+ set_type_size_bytes(frame, round_up2(offset, frame_align));