+static void belady(ir_node *block, void *env);
+
+/** Decides whether a specific node should be in the start workset or not
+ *
+ * @param env belady environment
+ * @param first
+ * @param node the node to test
+ * @param block the block of the node
+ * @param loop the loop of the node
+ */
+static loc_t to_take_or_not_to_take(belady_env_t *env, ir_node* first,
+ ir_node *node, ir_node *block,
+ ir_loop *loop)
+{
+ be_next_use_t next_use;
+ loc_t loc;
+ loc.time = USES_INFINITY;
+ loc.irn = node;
+
+ if (!arch_irn_consider_in_reg_alloc(env->arch, env->cls, node)) {
+ loc.time = USES_INFINITY;
+ return loc;
+ }
+
+ /* We have to keep nonspillable nodes in the workingset */
+ if(arch_irn_get_flags(env->arch, node) & arch_irn_flags_dont_spill) {
+ loc.time = 0;
+ DBG((dbg, DBG_START, " %+F taken (dontspill node)\n", node, loc.time));
+ return loc;
+ }
+
+ next_use = be_get_next_use(env->uses, first, 0, node, 0);
+ if(USES_IS_INFINITE(next_use.time)) {
+ // the nodes marked as live in shouldn't be dead, so it must be a phi
+ assert(is_Phi(node));
+ loc.time = USES_INFINITY;
+ DBG((dbg, DBG_START, " %+F not taken (dead)\n", node));
+ if(is_Phi(node)) {
+ be_spill_phi(env->senv, node);
+ }
+ return loc;
+ }
+
+ loc.time = next_use.time;
+
+ if(next_use.outermost_loop >= get_loop_depth(loop)) {
+ DBG((dbg, DBG_START, " %+F taken (%u, loop %d)\n", node, loc.time, next_use.outermost_loop));
+ } else {
+ loc.time = USES_PENDING;
+ DBG((dbg, DBG_START, " %+F delayed (outerloopdepth %d < loopdetph %d)\n", node, next_use.outermost_loop, get_loop_depth(loop)));
+ }
+ return loc;
+}
+
+/*
+ * Computes set of live-ins for each block with multiple predecessors
+ * and notifies spill algorithm which phis need to be spilled
+ */
+static void compute_live_ins(ir_node *block, void *data) {
+ belady_env_t *env = data;
+ ir_loop *loop = get_irn_loop(block);
+ const be_lv_t *lv = env->lv;
+ block_info_t *block_info;
+ ir_node *first, *irn;
+ loc_t loc, *starters, *delayed;
+ int i, len, ws_count;
+ int free_slots, free_pressure_slots;
+ unsigned pressure;
+
+ 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);
+ delayed = NEW_ARR_F(loc_t, 0);
+
+ DBG((dbg, DBG_START, "Living at start of %+F:\n", block));
+ first = sched_first(block);
+
+ /* check all Phis first */
+ sched_foreach(block, irn) {
+ if (! is_Phi(irn))
+ break;
+
+ loc = to_take_or_not_to_take(env, first, irn, block, loop);
+
+ if (! USES_IS_INFINITE(loc.time)) {
+ if (USES_IS_PENDING(loc.time))
+ ARR_APP1(loc_t, delayed, loc);
+ else
+ ARR_APP1(loc_t, starters, loc);
+ }
+ }
+
+ /* check all Live-Ins */
+ be_lv_foreach(lv, block, be_lv_state_in, i) {
+ ir_node *node = be_lv_get_irn(lv, block, i);
+
+ loc = to_take_or_not_to_take(env, first, node, block, loop);
+
+ if (! USES_IS_INFINITE(loc.time)) {
+ if (USES_IS_PENDING(loc.time))
+ ARR_APP1(loc_t, delayed, loc);
+ else
+ ARR_APP1(loc_t, starters, loc);
+ }
+ }
+
+ pressure = be_get_loop_pressure(env->loop_ana, env->cls, loop);
+ assert(ARR_LEN(delayed) <= pressure);
+ free_slots = env->n_regs - ARR_LEN(starters);
+ free_pressure_slots = env->n_regs - (pressure - ARR_LEN(delayed));
+ free_slots = MIN(free_slots, free_pressure_slots);
+ /* append nodes delayed due to loop structure until start set is full */
+ for (i = 0; i < ARR_LEN(delayed) && i < free_slots; ++i) {
+ DBG((dbg, DBG_START, " delayed %+F taken\n", delayed[i].irn));
+ ARR_APP1(loc_t, starters, delayed[i]);
+ delayed[i].irn = NULL;
+ }
+
+ /* spill all delayed phis which didn't make it into start workset */
+ for (i = ARR_LEN(delayed) - 1; i >= 0; --i) {
+ ir_node *irn = delayed[i].irn;
+ if (irn && is_Phi(irn)) {
+ DBG((dbg, DBG_START, " spilling delayed phi %+F\n", irn));
+ be_spill_phi(env->senv, irn);
+ }
+ }
+ DEL_ARR_F(delayed);
+
+ /* 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. */
+ len = ARR_LEN(starters);
+ for (i = ws_count; 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);
+}
+
+/**
+ * Collects all values live-in at block @p block and all phi results in this block.
+ * Then it adds the best values (at most n_regs) to the blocks start_workset.
+ * The phis among the remaining values get spilled: Introduce psudo-copies of
+ * their args to break interference and make it possible to spill them to the
+ * same spill slot.
+ */
+static block_info_t *compute_block_start_info(belady_env_t *env, ir_node *block) {
+ ir_node *pred_block;
+ block_info_t *res, *pred_info;
+
+ /* Have we seen this block before? */
+ res = get_block_info(block);
+ if (res)
+ return res;
+
+ /* Create the block info for this block. */
+ res = new_block_info(&env->ob);
+ set_block_info(block, res);
+
+ /* Use endset of predecessor block as startset */
+ assert(get_Block_n_cfgpreds(block) == 1 && block != get_irg_start_block(get_irn_irg(block)));
+ pred_block = get_Block_cfgpred_block(block, 0);
+ pred_info = get_block_info(pred_block);
+
+ /* if pred block has not been processed yet, do it now */
+ if (pred_info == NULL || pred_info->processed == 0) {
+ belady(pred_block, env);
+ pred_info = get_block_info(pred_block);
+ }
+
+ /* now we have an end_set of pred */
+ assert(pred_info->ws_end && "The recursive call (above) is supposed to compute an end_set");
+ res->ws_start = workset_clone(env, &env->ob, pred_info->ws_end);
+
+ return res;
+}
+
+