+/**
+ * analyzes how to best spill a node and determine costs for that
+ */
+static void determine_spill_costs(spill_env_t *env, spill_info_t *spillinfo)
+{
+ ir_node *to_spill = spillinfo->to_spill;
+ ir_node *spill_block;
+ spill_t *spill;
+ double spill_execfreq;
+
+ /* already calculated? */
+ if(spillinfo->spill_costs >= 0)
+ return;
+
+ assert(!arch_irn_is(to_spill, dont_spill));
+ assert(!be_is_Reload(to_spill));
+
+ /* some backends have virtual noreg/unknown nodes that are not scheduled
+ * and simply always available.
+ * TODO: this is kinda hairy, the NoMem is correct for an Unknown as Phi
+ * predecessor (of a PhiM) but this test might match other things too...
+ */
+ if(!sched_is_scheduled(to_spill)) {
+ /* override spillinfos or create a new one */
+ spill_t *spill = obstack_alloc(&env->obst, sizeof(spill[0]));
+ spill->after = NULL;
+ spill->next = NULL;
+ spill->spill = new_NoMem();
+
+ spillinfo->spills = spill;
+ spillinfo->spill_costs = 0;
+
+ DB((dbg, LEVEL_1, "don't spill %+F use NoMem\n", to_spill));
+ return;
+ }
+
+ spill_block = get_nodes_block(to_spill);
+ spill_execfreq = get_block_execfreq(env->exec_freq, spill_block);
+
+ if (is_Phi(to_spill) && ir_nodeset_contains(&env->mem_phis, to_spill)) {
+ /* TODO calculate correct costs...
+ * (though we can't remat this node anyway so no big problem) */
+ spillinfo->spill_costs = env->spill_cost * spill_execfreq;
+ return;
+ }
+
+ if(spillinfo->spills != NULL) {
+ spill_t *s;
+ double spills_execfreq;
+
+ /* calculate sum of execution frequencies of individual spills */
+ spills_execfreq = 0;
+ s = spillinfo->spills;
+ for( ; s != NULL; s = s->next) {
+ ir_node *spill_block = get_block(s->after);
+ double freq = get_block_execfreq(env->exec_freq, spill_block);
+
+ spills_execfreq += freq;
+ }
+
+ DB((dbg, LEVEL_1, "%+F: latespillcosts %f after def: %f\n", to_spill,
+ spills_execfreq * env->spill_cost,
+ spill_execfreq * env->spill_cost));
+
+ /* multi-/latespill is advantageous -> return*/
+ if(spills_execfreq < spill_execfreq) {
+ DB((dbg, LEVEL_1, "use latespills for %+F\n", to_spill));
+ spillinfo->spill_costs = spills_execfreq * env->spill_cost;
+ return;
+ }
+ }
+
+ /* override spillinfos or create a new one */
+ spill = obstack_alloc(&env->obst, sizeof(spill[0]));
+ spill->after = skip_keeps_phis(to_spill);
+ spill->next = NULL;
+ spill->spill = NULL;
+
+ spillinfo->spills = spill;
+ spillinfo->spill_costs = spill_execfreq * env->spill_cost;
+ DB((dbg, LEVEL_1, "spill %+F after definition\n", to_spill));
+}
+
+void make_spill_locations_dominate_irn(spill_env_t *env, ir_node *irn)
+{
+ const spill_info_t *si = get_spillinfo(env, irn);
+ ir_node *start_block = get_irg_start_block(get_irn_irg(irn));
+ int n_blocks = get_Block_dom_max_subtree_pre_num(start_block);
+ bitset_t *reloads = bitset_alloca(n_blocks);
+ reloader_t *r;
+ spill_t *s;
+
+ if (si == NULL)
+ return;
+
+ /* Fill the bitset with the dominance pre-order numbers
+ * of the blocks the reloads are located in. */
+ for (r = si->reloaders; r != NULL; r = r->next) {
+ ir_node *bl = get_nodes_block(r->reloader);
+ bitset_set(reloads, get_Block_dom_tree_pre_num(bl));
+ }
+
+ /* Now, cancel out all the blocks that are dominated by each spill.
+ * If the bitset is not empty after that, we have reloads that are
+ * not dominated by any spill. */
+ for (s = si->spills; s != NULL; s = s->next) {
+ ir_node *bl = get_nodes_block(s->after);
+ int start = get_Block_dom_tree_pre_num(bl);
+ int end = get_Block_dom_max_subtree_pre_num(bl);
+
+ bitset_clear_range(reloads, start, end);
+ }
+
+ if (!bitset_is_empty(reloads))
+ be_add_spill(env, si->to_spill, si->to_spill);
+}
+
+void be_insert_spills_reloads(spill_env_t *env)
+{
+ const ir_exec_freq *exec_freq = env->exec_freq;
+ spill_info_t *si;
+ ir_nodeset_iterator_t iter;
+ ir_node *node;
+
+ BE_TIMER_PUSH(t_ra_spill_apply);
+
+ /* create all phi-ms first, this is needed so, that phis, hanging on
+ spilled phis work correctly */
+ foreach_ir_nodeset(&env->mem_phis, node, iter) {
+ spill_info_t *info = get_spillinfo(env, node);
+ spill_node(env, info);
+ }