+ 3. Insert the new values into the workset
+ */
+ for (i = 0; i < demand; ++i)
+ workset_insert(env, env->ws, to_insert[i]);
+}
+
+static void belady(ir_node *blk, void *env);
+
+/*
+ * Computes set of live-ins for each block with multiple predecessors
+ * and notifies spill algorithm which phis need to be spilled
+ */
+static void spill_phi_walker(ir_node *block, void *data) {
+ belady_env_t *env = data;
+ block_info_t *block_info;
+ ir_node *first, *irn;
+ loc_t loc, *starters;
+ int i, len, ws_count;
+
+ if(get_Block_n_cfgpreds(block) == 1 && get_irg_start_block(get_irn_irg(block)) != block)
+ return;
+
+ block_info = new_block_info(&env->ob);
+ set_block_info(block, block_info);
+
+ /* Collect all values living at start of block */
+ starters = NEW_ARR_F(loc_t, 0);
+
+ /* rebuild schedule time information, because it seems to be broken */
+ sched_renumber(block);
+
+ DBG((dbg, DBG_START, "Living at start of %+F:\n", block));
+ first = sched_first(block);
+ sched_foreach(block, irn) {
+ if(!is_Phi(irn))
+ break;
+ if(!arch_irn_consider_in_reg_alloc(env->arch, env->cls, irn))
+ continue;
+
+ loc.irn = irn;
+ loc.time = get_distance(env, first, 0, irn, 0);
+ ARR_APP1(loc_t, starters, loc);
+ DBG((dbg, DBG_START, " %+F:\n", irn));
+ }
+
+ be_lv_foreach(env->cenv->lv, block, be_lv_state_in, i) {
+ ir_node *irn = be_lv_get_irn(env->cenv->lv, block, i);
+ if (!arch_irn_consider_in_reg_alloc(env->arch, env->cls, irn))
+ continue;
+
+ loc.irn = irn;
+ loc.time = get_distance(env, first, 0, irn, 0);
+ ARR_APP1(loc_t, starters, loc);
+ DBG((dbg, DBG_START, " %+F:\n", irn));
+ }
+
+ // Sort start values by first use
+ qsort(starters, ARR_LEN(starters), sizeof(starters[0]), loc_compare);
+
+ /* Copy the best ones from starters to start workset */
+ ws_count = MIN(ARR_LEN(starters), env->n_regs);
+ block_info->ws_start = new_workset(env, &env->ob);
+ workset_bulk_fill(block_info->ws_start, ws_count, starters);
+
+ /* The phis of this block which are not in the start set have to be spilled later. */
+ for (i = ws_count, len = ARR_LEN(starters); i < len; ++i) {
+ irn = starters[i].irn;
+ if (!is_Phi(irn) || get_nodes_block(irn) != block)
+ continue;
+
+ be_spill_phi(env->senv, irn);
+ }
+
+ DEL_ARR_F(starters);