+ /* 3. Insert the new values into the workset */
+ for (i = 0; i < demand; ++i) {
+ ir_node *val = to_insert[i];
+
+ workset_insert(ws, val, spilled[i]);
+ }
+}
+
+enum {
+ AVAILABLE_EVERYWHERE,
+ AVAILABLE_NOWHERE,
+ AVAILABLE_PARTLY,
+ AVAILABLE_UNKNOWN
+};
+
+static unsigned available_in_all_preds(workset_t* const* pred_worksets,
+ size_t n_pred_worksets,
+ const ir_node *value, bool is_local_phi)
+{
+ size_t i;
+ bool avail_everywhere = true;
+ bool avail_nowhere = true;
+
+ assert(n_pred_worksets > 0);
+
+ /* value available in all preds? */
+ for (i = 0; i < n_pred_worksets; ++i) {
+ bool found = false;
+ const workset_t *p_workset = pred_worksets[i];
+ int p_len = workset_get_length(p_workset);
+ int p_i;
+ const ir_node *l_value;
+
+ if (is_local_phi) {
+ assert(is_Phi(value));
+ l_value = get_irn_n(value, i);
+ } else {
+ l_value = value;
+ }
+
+ for (p_i = 0; p_i < p_len; ++p_i) {
+ const loc_t *p_l = &p_workset->vals[p_i];
+ if (p_l->node != l_value)
+ continue;
+
+ found = true;
+ break;
+ }
+
+ if (found) {
+ avail_nowhere = false;
+ } else {
+ avail_everywhere = false;
+ }
+ }
+
+ if (avail_everywhere) {
+ assert(!avail_nowhere);
+ return AVAILABLE_EVERYWHERE;
+ } else if (avail_nowhere) {
+ return AVAILABLE_NOWHERE;
+ } else {
+ return AVAILABLE_PARTLY;
+ }
+}
+
+/** 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 loop the loop of the node
+ */
+static loc_t to_take_or_not_to_take(ir_node* first, ir_node *node,
+ ir_loop *loop, unsigned available)
+{
+ be_next_use_t next_use;
+ loc_t loc;
+
+ loc.time = USES_INFINITY;
+ loc.node = node;
+ loc.spilled = false;
+
+ if (!arch_irn_consider_in_reg_alloc(cls, node)) {
+ loc.time = USES_INFINITY;
+ return loc;
+ }
+
+ /* We have to keep nonspillable nodes in the workingset */
+ if (arch_irn_get_flags(node) & arch_irn_flags_dont_spill) {
+ loc.time = 0;
+ DB((dbg, DBG_START, " %+F taken (dontspill node)\n", node, loc.time));
+ return loc;
+ }
+
+ next_use = be_get_next_use(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;
+ DB((dbg, DBG_START, " %+F not taken (dead)\n", node));
+ return loc;
+ }
+
+ loc.time = next_use.time;
+
+ if (improve_known_preds) {
+ if (available == AVAILABLE_EVERYWHERE) {
+ DB((dbg, DBG_START, " %+F taken (%u, live in all preds)\n",
+ node, loc.time));
+ return loc;
+ } else if(available == AVAILABLE_NOWHERE) {
+ DB((dbg, DBG_START, " %+F not taken (%u, live in no pred)\n",
+ node, loc.time));
+ loc.time = USES_INFINITY;
+ return loc;
+ }
+ }
+
+ if (!respectloopdepth || next_use.outermost_loop >= get_loop_depth(loop)) {
+ DB((dbg, DBG_START, " %+F taken (%u, loop %d)\n", node, loc.time,
+ next_use.outermost_loop));
+ } else {
+ loc.time = USES_PENDING;
+ DB((dbg, DBG_START, " %+F delayed (outerdepth %d < loopdepth %d)\n",
+ node, next_use.outermost_loop, get_loop_depth(loop)));
+ }
+
+ return loc;
+}
+
+/**
+ * Computes the start-workset for a block with multiple predecessors. We assume
+ * that at least 1 of the predeccesors is a back-edge which means we're at the
+ * beginning of a loop. We try to reload as much values as possible now so they
+ * don't get reloaded inside the loop.
+ */
+static void decide_start_workset(const ir_node *block)
+{
+ ir_loop *loop = get_irn_loop(block);
+ ir_node *first;
+ ir_node *node;
+ loc_t loc;
+ loc_t *starters;
+ loc_t *delayed;
+ int i, len, ws_count;
+ int free_slots, free_pressure_slots;
+ unsigned pressure;
+ int arity;
+ workset_t **pred_worksets;
+ bool all_preds_known;
+
+ /* check predecessors */
+ arity = get_irn_arity(block);
+ pred_worksets = ALLOCAN(workset_t*, arity);
+ all_preds_known = true;
+ for(i = 0; i < arity; ++i) {
+ ir_node *pred_block = get_Block_cfgpred_block(block, i);
+ block_info_t *pred_info = get_block_info(pred_block);
+
+ if (pred_info == NULL) {
+ pred_worksets[i] = NULL;
+ all_preds_known = false;
+ } else {
+ pred_worksets[i] = pred_info->end_workset;
+ }
+ }
+
+ /* Collect all values living at start of block */
+ starters = NEW_ARR_F(loc_t, 0);
+ delayed = NEW_ARR_F(loc_t, 0);
+
+ DB((dbg, DBG_START, "Living at start of %+F:\n", block));
+ first = sched_first(block);
+
+ /* check all Phis first */
+ sched_foreach(block, node) {
+ unsigned available;
+
+ if (! is_Phi(node))
+ break;
+ if (!arch_irn_consider_in_reg_alloc(cls, node))
+ continue;
+
+ if (all_preds_known) {
+ available = available_in_all_preds(pred_worksets, arity, node, true);
+ } else {
+ available = AVAILABLE_UNKNOWN;
+ }
+
+ loc = to_take_or_not_to_take(first, node, loop, available);
+
+ 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);
+ } else {
+ be_spill_phi(senv, node);
+ }
+ }
+
+ /* check all Live-Ins */
+ be_lv_foreach(lv, block, be_lv_state_in, i) {
+ ir_node *node = be_lv_get_irn(lv, block, i);
+ unsigned available;
+
+ if (all_preds_known) {
+ available = available_in_all_preds(pred_worksets, arity, node, false);
+ } else {
+ available = AVAILABLE_UNKNOWN;
+ }
+
+ loc = to_take_or_not_to_take(first, node, loop, available);
+
+ 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(loop_ana, cls, loop);
+ assert(ARR_LEN(delayed) <= (signed)pressure);
+ free_slots = n_regs - ARR_LEN(starters);
+ free_pressure_slots = n_regs - (pressure - ARR_LEN(delayed));
+ free_slots = MIN(free_slots, free_pressure_slots);
+
+ /* so far we only put nodes into the starters list that are used inside
+ * the loop. If register pressure in the loop is low then we can take some
+ * values and let them live through the loop */
+ DB((dbg, DBG_START, "Loop pressure %d, taking %d delayed vals\n",
+ pressure, free_slots));
+ if (free_slots > 0) {
+ qsort(delayed, ARR_LEN(delayed), sizeof(delayed[0]), loc_compare);
+
+ for (i = 0; i < ARR_LEN(delayed) && free_slots > 0; ++i) {
+ int p, arity;
+ loc_t *loc = & delayed[i];
+
+ if (!is_Phi(loc->node)) {
+ /* don't use values which are dead in a known predecessors
+ * to not induce unnecessary reloads */
+ arity = get_irn_arity(block);
+ for (p = 0; p < arity; ++p) {
+ ir_node *pred_block = get_Block_cfgpred_block(block, p);
+ block_info_t *pred_info = get_block_info(pred_block);
+
+ if (pred_info == NULL)
+ continue;
+
+ if (!workset_contains(pred_info->end_workset, loc->node)) {
+ DB((dbg, DBG_START,
+ " delayed %+F not live at pred %+F\n", loc->node,
+ pred_block));
+ goto skip_delayed;
+ }
+ }
+ }
+
+ DB((dbg, DBG_START, " delayed %+F taken\n", loc->node));
+ ARR_APP1(loc_t, starters, *loc);
+ loc->node = NULL;
+ --free_slots;
+ skip_delayed:
+ ;
+ }
+ }
+
+ /* spill phis (the actual phis not just their values) that are in this block
+ * but not in the start workset */
+ for (i = ARR_LEN(delayed) - 1; i >= 0; --i) {
+ ir_node *node = delayed[i].node;
+ if (node == NULL || !is_Phi(node) || get_nodes_block(node) != block)
+ continue;
+
+ DB((dbg, DBG_START, " spilling delayed phi %+F\n", node));
+ be_spill_phi(senv, node);
+ }
+ 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), n_regs);
+ workset_clear(ws);
+ workset_bulk_fill(ws, ws_count, starters);
+
+ /* spill phis (the actual phis not just their values) that are in this block
+ * but not in the start workset */
+ len = ARR_LEN(starters);
+ for (i = ws_count; i < len; ++i) {
+ ir_node *node = starters[i].node;
+ if (! is_Phi(node) || get_nodes_block(node) != block)
+ continue;
+
+ DB((dbg, DBG_START, " spilling phi %+F\n", node));
+ be_spill_phi(senv, node);
+ }
+
+ DEL_ARR_F(starters);
+
+ /* determine spill status of the values: If there's 1 pred block (which
+ * is no backedge) where the value is spilled then we must set it to
+ * spilled here. */
+ for(i = 0; i < ws_count; ++i) {
+ loc_t *loc = &ws->vals[i];
+ ir_node *value = loc->node;
+ bool spilled;
+ int n;
+
+ /* phis from this block aren't spilled */
+ if (get_nodes_block(value) == block) {
+ assert(is_Phi(value));
+ loc->spilled = false;
+ continue;
+ }
+
+ /* determine if value was spilled on any predecessor */
+ spilled = false;
+ for(n = 0; n < arity; ++n) {
+ workset_t *pred_workset = pred_worksets[n];
+ int p_len;
+ int p;
+
+ if (pred_workset == NULL)
+ continue;
+
+ p_len = workset_get_length(pred_workset);
+ for(p = 0; p < p_len; ++p) {
+ loc_t *l = &pred_workset->vals[p];
+
+ if (l->node != value)
+ continue;
+
+ if (l->spilled) {
+ spilled = true;
+ }
+ break;
+ }
+ }
+
+ loc->spilled = spilled;
+ }