+static void process_loop(ir_loop *loop)
+{
+ int n_elements = get_loop_n_elements(loop);
+ int i, len;
+ loop_info_t *loop_info;
+ loop_edge_t *edge;
+ ir_node *some_block;
+
+ /* first handle all sub-loops */
+ for (i = 0; i < n_elements; ++i) {
+ loop_element element = get_loop_element(loop, i);
+ if (*element.kind != k_ir_loop)
+ continue;
+
+ process_loop(element.son);
+ }
+
+ /* create a postorder of the blocks */
+ loop_info = get_loop_info(loop);
+ edge = loop_info->entry_edges;
+ if (edge != NULL) {
+ some_block = edge->block;
+ } else {
+ assert(loop == get_irg_loop(current_ir_graph));
+ some_block = get_irg_start_block(current_ir_graph);
+ }
+
+ loop_blocks = NEW_ARR_F(block_or_loop_t, 0);
+ current_loop = loop;
+
+ ir_reserve_resources(current_ir_graph, IR_RESOURCE_BLOCK_VISITED);
+ inc_irg_block_visited(current_ir_graph);
+ find_blocks(some_block);
+ /* for endless loops the end-block might be unreachable */
+ if (loop == get_irg_loop(current_ir_graph)) {
+ find_blocks(get_irg_end_block(current_ir_graph));
+ }
+ ir_free_resources(current_ir_graph, IR_RESOURCE_BLOCK_VISITED);
+
+ DB((dbg, LEVEL_3, "Block List for loop %p\n", loop));
+ len = ARR_LEN(loop_blocks);
+ for (i = 0; i < len; ++i) {
+ block_or_loop_t block_or_loop = loop_blocks[i];
+ if (block_or_loop.loop->kind == k_ir_loop) {
+ DB((dbg, LEVEL_3, " L-%p", block_or_loop.loop));
+ } else {
+ DB((dbg, LEVEL_3, " B-%+F", block_or_loop.block));
+ }
+ }
+ DB((dbg, LEVEL_3, "\n"));
+
+ max_register_pressure = 0;
+
+ /* run1: tentative phase */
+ tentative_mode = true;
+ for (i = len-1; i >= 0; --i) {
+ process_block_or_loop(loop_blocks[i]);
+ }
+
+ /* run2: tentative phase - should reach fixpoint */
+ tentative_mode = true;
+ for (i = len-1; i >= 0; --i) {
+ process_block_or_loop(loop_blocks[i]);
+ }
+
+#ifndef NDEBUG
+ /* run3: tentative phase - check fixpoint */
+ tentative_mode = true;
+ should_have_reached_fixpoint = true;
+ for (i = len-1; i >= 0; --i) {
+ process_block_or_loop(loop_blocks[i]);
+ }
+ should_have_reached_fixpoint = false;
+#endif
+
+ /* run4: add spills/reloads */
+ tentative_mode = false;
+ do_push_unused_livethroughs = true;
+ for (i = len-1; i >= 0; --i) {
+ process_block_or_loop(loop_blocks[i]);
+ }
+ do_push_unused_livethroughs = false;
+
+ loop_info->max_register_pressure = max_register_pressure;
+ DB((dbg, LEVEL_2, "Regpressure in loop %p: %u\n", loop,
+ (unsigned) max_register_pressure));
+
+ DEL_ARR_F(loop_blocks);
+}
+
+static void fix_block_borders(ir_node *block, void *data)
+{
+ block_info_t *block_info = get_block_info(block);
+ worklist_t *start_worklist = block_info->start_worklist;
+ int n_cfgpreds = get_Block_n_cfgpreds(block);
+ ir_loop *loop = get_irn_loop(block);
+ int i;
+
+ (void) data;
+ assert(start_worklist != NULL);
+
+ for (i = 0; i < n_cfgpreds; ++i) {
+ ir_node *pred_block = get_Block_cfgpred_block(block, i);
+ block_info_t *pred_block_info = get_block_info(pred_block);
+ worklist_t *end_worklist = pred_block_info->end_worklist;
+ ir_loop *pred_loop = get_irn_loop(pred_block);
+ bool is_loop_entry = false;
+ worklist_entry_t *entry;
+
+ assert(end_worklist != NULL);
+
+ if (get_loop_depth(pred_loop) < get_loop_depth(loop)) {
+ is_loop_entry = true;
+ }
+
+ /* reload missing values */
+ activate_worklist(end_worklist);
+
+ foreach_worklist(entry, start_worklist) {
+ ir_node *value = entry->value;
+
+ if (!is_loop_entry && entry->unused_livethrough_loop != NULL)
+ continue;
+
+ if (is_Phi(value) && get_nodes_block(value) == block) {
+ value = get_irn_n(value, i);
+
+ /* we might have unknowns as argument for the phi */
+ if (!arch_irn_consider_in_reg_alloc(cls, value))
+ continue;
+ }
+ if (worklist_contains(value))
+ continue;
+ be_add_reload_on_edge(senv, value, block, i, cls, 1);
+ }
+
+ deactivate_worklist(end_worklist);
+ }
+}
+
+/**
+ * Run the spill algorithm.
+ *
+ * @param birg the graph to run on
+ * @param ncls the register class to run on
+ */