+typedef struct block_or_loop_t block_or_loop_t;
+struct block_or_loop_t {
+ union {
+ ir_node *block;
+ ir_loop *loop;
+ } v;
+ bool is_loop;
+};
+
+static block_or_loop_t *loop_blocks;
+static ir_loop *current_loop;
+
+static void find_blocks(ir_node *block);
+
+static void find_in_loop(ir_loop *loop, ir_node *entry)
+{
+ loop_info_t *loop_info = get_loop_info(loop);
+ block_or_loop_t block_or_loop;
+ loop_edge_t *edge;
+
+ /* simply mark 1 block in the loop to indicate that the loop was already
+ * processed */
+ ir_node *some_block = loop_info->entry_edges->block;
+ if (Block_block_visited(some_block))
+ return;
+
+ block_or_loop.v.loop = loop;
+ block_or_loop.is_loop = true;
+ ARR_APP1(block_or_loop_t, loop_blocks, block_or_loop);
+
+#ifndef NDEBUG
+ {
+ /* we should be 1 of the entry blocks */
+ loop_edge_t *edge = loop_info->entry_edges;
+ bool found = false;
+ for ( ; edge != NULL; edge = edge->next) {
+ if (edge->block == entry)
+ found = true;
+ }
+ assert(found);
+ }
+#endif
+ /* check all loop successors */
+ for (edge = loop_info->exit_edges; edge != NULL; edge = edge->next) {
+ ir_node *succ = edge->block;
+ ir_loop *succ_loop = get_irn_loop(succ);
+
+ if (succ_loop == current_loop) {
+ find_blocks(succ);
+ } else {
+ assert(get_loop_depth(succ_loop) < get_loop_depth(current_loop));
+ }
+ }
+}
+
+static void find_blocks(ir_node *block)
+{
+ const ir_edge_t *edge;
+ block_or_loop_t block_or_loop;
+
+ if (Block_block_visited(block))
+ return;
+
+ block_or_loop.v.block = block;
+ block_or_loop.is_loop = false;
+
+ ARR_APP1(block_or_loop_t, loop_blocks, block_or_loop);
+ mark_Block_block_visited(block);
+
+ foreach_block_succ(block, edge) {
+ ir_node *succ = get_edge_src_irn(edge);
+
+ /* is it part of the current loop? */
+ ir_loop *loop = get_irn_loop(succ);
+ if (loop != current_loop) {
+ /* a sub-loop? */
+ if (get_loop_depth(loop) > get_loop_depth(current_loop)) {
+ find_in_loop(loop, succ);
+ } else {
+ /* parent loop: we're not interested in the block */
+ }
+ } else {
+ find_blocks(succ);
+ }
+ }
+}
+
+/**
+ * append an entry to a worklist. WARNING: The entry must not already be in the
+ * worklist.
+ */
+static void worklist_append(worklist_t *worklist, ir_node *value,
+ ir_node *reload_point,
+ ir_loop *unused_livethrough_loop)
+{
+ worklist_entry_t *entry = obstack_alloc(&obst, sizeof(entry[0]));
+ memset(entry, 0, sizeof(entry[0]));
+
+ entry->value = value;
+ entry->reload_point = reload_point;
+ entry->unused_livethrough_loop = unused_livethrough_loop;
+ list_add_tail(&entry->head, &worklist->live_values);
+ ++worklist->n_live_values;
+ assert(worklist->n_live_values <= n_regs);
+}
+
+static void push_unused_livethrough(loop_info_t *loop_info, ir_node *value)
+{
+ /* add the value to all loop exit and entry blocks */
+ loop_edge_t *edge = loop_info->exit_edges;
+ for ( ; edge != NULL; edge = edge->next) {
+ ir_node *block
+ = get_Block_cfgpred_block(edge->block, edge->pos);
+ const block_info_t *info = get_block_info(block);
+ worklist_t *worklist = info->end_worklist;
+ /* TODO: we need a smarter mechanism here, that makes the reloader place
+ * reload nodes on all loop exits... */
+ ir_node *reload_point = NULL;
+
+ worklist_append(worklist, value, reload_point, loop_info->loop);
+ }
+ edge = loop_info->entry_edges;
+ for ( ; edge != NULL; edge = edge->next) {
+ ir_node *entry_block = edge->block;
+ const block_info_t *info = get_block_info(entry_block);
+ worklist_t *worklist = info->start_worklist;
+
+ ir_node *pred_block
+ = get_Block_cfgpred_block(entry_block, edge->pos);
+ ir_node *reload_point = be_get_end_of_block_insertion_point(pred_block);
+
+ worklist_append(worklist, value, reload_point, loop_info->loop);
+ }
+
+ set_irn_link(value, NULL);
+ ++loop_info->max_register_pressure;
+}
+
+static void push_unused_livethroughs(loop_info_t *loop_info)
+{
+ loop_edge_t *edge;
+
+ /* we can only push unused livethroughs if register pressure inside the loop
+ * was low enough */
+ if (loop_info->max_register_pressure >= n_regs)
+ return;
+
+ /* find unused livethroughs: register pressure in the loop was low enough
+ * which means that we had no spills which implies that at every point in
+ * the loop all*/
+ for (edge = loop_info->exit_edges; edge != NULL; edge = edge->next) {
+ ir_node *block = edge->block;
+ const block_info_t *info = get_block_info(block);
+ worklist_t *start_worklist = info->start_worklist;
+ ir_node *exit_block;
+ const block_info_t *exit_info;
+ worklist_t *end_worklist;
+ struct list_head *entry;
+
+ if (start_worklist == NULL)
+ continue;
+
+ exit_block = get_Block_cfgpred_block(edge->block, edge->pos);
+ exit_info = get_block_info(exit_block);
+ end_worklist = exit_info->end_worklist;
+
+ activate_worklist(end_worklist);
+ /* all values contained in the start_worklist, which are not available
+ * in the end_worklist, must be unused livethroughs */
+
+ list_for_each(entry, &start_worklist->live_values) {
+ worklist_entry_t *wl_entry
+ = list_entry(entry, worklist_entry_t, head);
+ ir_node *value = wl_entry->value;
+
+ if (!worklist_contains(value)) {
+ /* add it to all loop exits */
+ ir_fprintf(stderr, "Found unused livethrough: %+F (regpressure in loop %d)\n", value, loop_info->max_register_pressure);
+ push_unused_livethrough(loop_info, value);
+ mark_irn_visited(value);
+ }
+
+ if (loop_info->max_register_pressure >= n_regs)
+ break;
+ }
+ deactivate_worklist(end_worklist);
+ }
+}
+
+static void process_block_or_loop(const block_or_loop_t *block_or_loop)
+{
+ if (block_or_loop->is_loop) {
+ loop_info_t *loop_info = get_loop_info(block_or_loop->v.loop);
+
+ if (loop_info->max_register_pressure > max_register_pressure)
+ max_register_pressure = loop_info->max_register_pressure;
+
+ push_unused_livethroughs(loop_info);
+ return;
+ }
+ process_block(block_or_loop->v.block, NULL);
+}
+
+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);
+
+ fprintf(stderr, "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->is_loop) {
+ ir_fprintf(stderr, " L-%p", block_or_loop->v.loop);
+ } else {
+ ir_fprintf(stderr, " B-%+F", block_or_loop->v.block);
+ }
+ }
+ fprintf(stderr, "\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;
+ for (i = len-1; i >= 0; --i) {
+ process_block_or_loop(&loop_blocks[i]);
+ }
+
+ loop_info->max_register_pressure = max_register_pressure;
+ ir_fprintf(stderr, "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;
+ struct list_head *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);
+
+ list_for_each(entry, &start_worklist->live_values) {
+ worklist_entry_t *wl_entry
+ = list_entry(entry, worklist_entry_t, head);
+ ir_node *value = wl_entry->value;
+
+ 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(arch_env, cls, value))
+ continue;
+ }
+
+ if (worklist_contains(value))
+ continue;
+ if (wl_entry->unused_livethrough_loop != NULL && !is_loop_entry)
+ continue;
+
+ be_add_reload_on_edge(senv, value, block, i, cls, 1);
+ }
+
+ deactivate_worklist(end_worklist);
+ }
+}
+