* @version $Id$
*
* TODO:
- * - handle phis correctly, decide wether we should spill them ~ok
+ * - handle phis correctly, decide whether we should spill them ~ok
* - merge multiple start worksets of blocks ~ok
* - how to and when to do the tentative phase...
*/
typedef struct loop_info_t loop_info_t;
struct loop_info_t {
+ ir_loop *loop;
loop_edge_t *entry_edges;
loop_edge_t *exit_edges;
size_t max_register_pressure;
struct list_head head;
ir_node *value;
ir_node *reload_point;
- worklist_entry_t *next_reload;
+ ir_loop *unused_livethrough_loop;
};
typedef struct worklist_t worklist_t;
static worklist_t *new_worklist(void)
{
worklist_t *worklist = obstack_alloc(&obst, sizeof(worklist[0]));
+ memset(worklist, 0, sizeof(worklist[0]));
INIT_LIST_HEAD(&worklist->live_values);
worklist->n_live_values = 0;
list_for_each(entry, &worklist->live_values) {
worklist_entry_t *wl_entry = list_entry(entry, worklist_entry_t, head);
ir_node *value = wl_entry->value;
+ worklist_entry_t *new_entry;
if (is_Phi(value) && get_nodes_block(value) == succ_block) {
value = get_Phi_pred(value, succ_pos);
continue;
}
- worklist_entry_t *new_entry
- = obstack_alloc(&obst, sizeof(new_entry[0]));
+ new_entry = obstack_alloc(&obst, sizeof(new_entry[0]));
+ memset(new_entry, 0, sizeof(new_entry[0]));
+
new_entry->value = value;
if (reload_point != NULL) {
new_entry->reload_point = reload_point;
} else {
new_entry->reload_point = wl_entry->reload_point;
}
- new_entry->next_reload = NULL;
if (irn_not_visited(value)) {
list_add_tail(&new_entry->head, &new_worklist->live_values);
mark_irn_visited(value);
set_irn_link(value, new_entry);
}
-#if 0
- else {
- /* the only way we might visit a value again, is when we get it as
- * phi predecessor */
- assert(is_Phi(wl_entry->value)
- && get_nodes_block(wl_entry->value) == succ_block);
- }
-#endif
}
new_worklist->n_live_values = n_live_values;
info = obstack_alloc(&obst, sizeof(info[0]));
memset(info, 0, sizeof(info[0]));
+ info->loop = loop;
loop->link = info;
return info;
}
ir_node *cfgpred_block = get_Block_cfgpred_block(block, i);
ir_loop *cfgpred_loop = get_irn_loop(cfgpred_block);
loop_edge_t *edge;
+ bool is_exit_edge;
+ ir_loop *l, *goal;
if (cfgpred_loop == loop)
continue;
assert(get_loop_depth(cfgpred_loop) != get_loop_depth(loop));
/* edge out of loop */
- bool is_exit_edge;
- ir_loop *l, *goal;
if (get_loop_depth(cfgpred_loop) > get_loop_depth(loop)) {
is_exit_edge = true;
l = cfgpred_loop;
if (tentative_mode)
return;
- /* walk list of reload points */
- do {
- DB((dbg, LEVEL_1, "reload of %+F before %+F\n", entry->value,
- entry->reload_point));
- assert(entry->reload_point != NULL);
- be_add_reload(senv, entry->value, entry->reload_point, cls, 1);
- entry->reload_point = NULL;
-
- entry = entry->next_reload;
- } while(entry != NULL);
-}
-
-#if 0
-/**
- * does stuff required for non-active worklists: spills all values not live
- * in the active worklist; links live values to the current worklist
- */
-static void process_non_active_worklist(const worklist_t *worklist,
- worklist_t *current_worklist)
-{
- struct list_head *entry;
-
- list_for_each(entry, &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)) {
- /* if we still have room in the worklist, then we can simply take
- * the value */
- if (current_worklist->n_live_values < n_regs) {
- worklist_entry_t *new_entry
- = obstack_alloc(&obst, sizeof(new_entry[0]));
-
- new_entry->value = value;
- new_entry->reload_point = wl_entry->reload_point;
- new_entry->next_reload = wl_entry->next_reload;
- set_irn_link(value, new_entry);
- mark_irn_visited(value);
- list_add(&new_entry->head, ¤t_worklist->live_values);
- ++current_worklist->n_live_values;
- } else {
- /* value is not in current worklist, place reloads */
- place_reload(wl_entry);
- }
- } else {
- /* value is in current worklist, link it with the reload point
- * from this path */
- worklist_entry_t *active_entry = get_irn_link(value);
- wl_entry->next_reload = active_entry->next_reload;
- active_entry->next_reload = wl_entry;
- }
- }
+ DB((dbg, LEVEL_1, "reload of %+F before %+F\n", entry->value,
+ entry->reload_point));
+ assert(entry->reload_point != NULL);
+ be_add_reload(senv, entry->value, entry->reload_point, cls, 1);
+ entry->reload_point = NULL;
}
-#endif
/**
* makes sure the worklist contains not more than n_regs - room_needed entries
*/
static void val_used(worklist_t *worklist, ir_node *value, ir_node *sched_point)
{
- assert(arch_irn_consider_in_reg_alloc(arch_env, cls, value));
-
/* already in the worklist? move around, otherwise add at back */
worklist_entry_t *entry = get_irn_link(value);
+
+ assert(arch_irn_consider_in_reg_alloc(arch_env, cls, value));
+
if (worklist_contains(value)) {
assert(entry != NULL);
} else {
if (entry == NULL) {
entry = obstack_alloc(&obst, sizeof(entry[0]));
+ memset(entry, 0, sizeof(entry[0]));
+
entry->value = value;
set_irn_link(value, entry);
}
}
entry->reload_point = sched_point;
- entry->next_reload = NULL;
list_add_tail(&entry->head, &worklist->live_values);
}
static void worklist_remove(worklist_t *worklist, ir_node *value)
{
worklist_entry_t *entry = get_irn_link(value);
+ ir_fprintf(stderr, "removing %+F\n", value);
assert(entry != NULL);
list_del(&entry->head);
--worklist->n_live_values;
} else {
worklist = duplicate_activate_worklist(worklist, block, best_succ_block,
best_pos);
-
- /* handle this in fix_blocks later... */
-#if 0
- /* now we could have live values in the succ worklists that are not
- * live anymore in the worklist we picked. We need reloads for them. */
- foreach_block_succ(block, edge) {
- ir_node *succ_block = get_edge_src_irn(edge);
- block_info_t *block_info = get_block_info(succ_block);
- worklist_t *succ_worklist = block_info->start_worklist;
-
- if (succ_block == best_succ_block)
- continue;
-
- process_non_active_worklist(succ_worklist, worklist);
- }
-#endif
}
block_info = get_block_info(block);
static void find_in_loop(ir_loop *loop, ir_node *entry)
{
- loop_info_t *loop_info = get_loop_info(loop);
+ 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 */
if (Block_block_visited(some_block))
return;
- block_or_loop_t block_or_loop;
block_or_loop.v.loop = loop;
block_or_loop.is_loop = true;
ARR_APP1(block_or_loop_t, loop_blocks, block_or_loop);
}
#endif
/* check all loop successors */
- loop_edge_t *edge = loop_info->exit_edges;
- for ( ; edge != NULL; edge = edge->next) {
- ir_node *succ = edge->block;
- ir_loop *succ_loop = get_irn_loop(succ);
+ 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);
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_t block_or_loop;
block_or_loop.v.block = block;
block_or_loop.is_loop = false;
}
}
+/**
+ * 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) {
if (loop_info->max_register_pressure > max_register_pressure)
max_register_pressure = loop_info->max_register_pressure;
- /* TODO: push unused livethroughs... */
+ push_unused_livethroughs(loop_info);
return;
}
process_block(block_or_loop->v.block, NULL);
static void process_loop(ir_loop *loop)
{
- /* first handle all sub-loops */
- int n_elements = get_loop_n_elements(loop);
- int i;
+ 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)
}
/* create a postorder of the blocks */
- loop_info_t *loop_info = get_loop_info(loop);
- loop_edge_t *edge = loop_info->entry_edges;
- ir_node *some_block;
+ loop_info = get_loop_info(loop);
+ edge = loop_info->entry_edges;
if (edge != NULL) {
some_block = edge->block;
} else {
ir_free_resources(current_ir_graph, IR_RESOURCE_BLOCK_VISITED);
fprintf(stderr, "Block List for loop %p\n", loop);
- int len = ARR_LEN(loop_blocks);
+ 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) {
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;
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);
- /* reload missing values */
- struct list_head *entry;
+ 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) {
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);
}
process_loop(get_irg_loop(current_ir_graph));
-#if 0
- /* do a post-order walk over the CFG to make sure we have a maximum number
- * of preds processed before entering a block */
- tentative_mode = 1;
- irg_block_edges_walk(get_irg_start_block(irg), NULL, process_block, NULL);
-
- tentative_mode = 1;
- irg_block_edges_walk(get_irg_start_block(irg), NULL, process_block, NULL);
-
- tentative_mode = 0;
- irg_block_edges_walk(get_irg_start_block(irg), NULL, process_block, NULL);
-#endif
-
irg_block_walk_graph(irg, fix_block_borders, NULL, NULL);
ir_free_resources(irg, IR_RESOURCE_IRN_VISITED | IR_RESOURCE_IRN_LINK
projects / libfirm / blobdiff