* @version $Id$
*
* TODO:
- * - handle phis correctly, decide wether we should spill them
- * - merge multiple start worksets of blocks
+ * - handle phis correctly, decide wether we should spill them ~ok
+ * - merge multiple start worksets of blocks ~ok
* - how to and when to do the tentative phase...
*/
#ifdef HAVE_CONFIG_H
struct worklist_entry_t {
struct list_head head;
ir_node *value;
- unsigned timestep;
ir_node *reload_point;
+ worklist_entry_t *next_reload;
};
typedef struct worklist_t worklist_t;
struct worklist_t {
struct list_head live_values;
size_t n_live_values;
- unsigned current_timestep;
};
static const arch_env_t *arch_env;
static int tentative_mode;
static ir_exec_freq *exec_freq;
-static void init_worklist(worklist_t *worklist, unsigned timestep)
+static worklist_t *new_worklist(void)
{
+ worklist_t *worklist = obstack_alloc(&obst, sizeof(worklist[0]));
+
INIT_LIST_HEAD(&worklist->live_values);
worklist->n_live_values = 0;
- worklist->current_timestep = timestep;
+
+ return worklist;
}
static void mark_irn_not_visited(ir_node *node)
}
}
-static void activate_worklist(const worklist_t *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;
-
- assert(irn_not_visited(value));
- mark_irn_visited(value);
- set_irn_link(value, wl_entry);
- }
-}
-
-static worklist_t *duplicate_worklist(const worklist_t *worklist,
- ir_node *block,
- ir_node *succ_block, int succ_pos)
+/**
+ * duplicate a worklist and directly activates it
+ */
+static worklist_t *duplicate_activate_worklist(const worklist_t *worklist,
+ ir_node *block, ir_node *succ_block, int succ_pos)
{
- ir_node *reload_point = NULL;
+ ir_node *reload_point = NULL;
+ size_t n_live_values = 0;
+ worklist_t *new_worklist;
struct list_head *entry;
- worklist_t *new_worklist = obstack_alloc(&obst, sizeof(new_worklist[0]));
-
- INIT_LIST_HEAD(&new_worklist->live_values);
if(succ_block != NULL && get_Block_n_cfgpreds(succ_block) > 1) {
reload_point = be_get_end_of_block_insertion_point(block);
}
- new_worklist->current_timestep = worklist->current_timestep;
- new_worklist->n_live_values = worklist->n_live_values;
+ new_worklist = obstack_alloc(&obst, sizeof(new_worklist[0]));
+ INIT_LIST_HEAD(&new_worklist->live_values);
list_for_each(entry, &worklist->live_values) {
- worklist_entry_t *wl_entry
- = list_entry(entry, worklist_entry_t, head);
+ worklist_entry_t *wl_entry = list_entry(entry, worklist_entry_t, head);
+ ir_node *value = wl_entry->value;
worklist_entry_t *new_entry
= obstack_alloc(&obst, sizeof(new_entry[0]));
- ir_node *value = wl_entry->value;
if(is_Phi(value) && get_nodes_block(value) == succ_block) {
value = get_Phi_pred(value, succ_pos);
}
- new_entry->value = value;
- new_entry->timestep = wl_entry->timestep;
+ 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);
+ ++n_live_values;
- list_add_tail(&new_entry->head, &new_worklist->live_values);
+ mark_irn_visited(value);
+ set_irn_link(value, new_entry);
+ } else {
+ /* the only way we might visit a value again, is when we get it as
+ * phi predecessor */
+ assert(is_Phi(wl_entry->value));
+ }
}
+ new_worklist->n_live_values = n_live_values;
return new_worklist;
}
{
struct list_head *entry;
- DB((dbg, level, "%d values (TS %u): ", worklist->n_live_values,
- worklist->current_timestep));
+ DB((dbg, level, "%d values: ", worklist->n_live_values));
list_for_each(entry, &worklist->live_values) {
worklist_entry_t *wl_entry
= list_entry(entry, worklist_entry_t, head);
- //DB((dbg, level, "%+F(%+F) ", wl_entry->value,
- // wl_entry->reload_point));
DB((dbg, level, "%+F ", wl_entry->value));
}
}
{
if(tentative_mode)
return;
- DB((dbg, LEVEL_1, "reload of %+F before %+F", entry->value,
- entry->reload_point));
- be_add_reload(senv, entry->value, entry->reload_point, cls, 1);
+
+ /* 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);
}
-static void spill_non_live_nodes(const worklist_t *worklist)
+/**
+ * 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(irn_visited(value))
- continue;
-
- place_reload(wl_entry);
+ worklist_entry_t *wl_entry = list_entry(entry, worklist_entry_t, head);
+ ir_node *value = wl_entry->value;
+
+ if(!irn_visited(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;
+ }
}
}
mark_irn_visited(value);
}
- entry->timestep = worklist->current_timestep;
entry->reload_point = sched_point;
+ entry->next_reload = NULL;
list_add_tail(&entry->head, &worklist->live_values);
}
assert(worklist != NULL);
-#ifdef DEBUG_libfirm
- DB((dbg, LEVEL_1, "worklist at end of %+F:", block));
- print_worklist(worklist, LEVEL_1);
- DB((dbg, LEVEL_1, "\n"));
-#endif
-
sched_foreach_reverse(block, node) {
int i, arity;
size_t n_defs = 0;
if(!arch_irn_consider_in_reg_alloc(arch_env, cls, node2))
continue;
- be_spill_phi(senv, node2);
+ if(!tentative_mode)
+ be_spill_phi(senv, node2);
}
break;
}
* some */
make_room(worklist, 0);
- ++worklist->current_timestep;
-
#ifdef DEBUG_libfirm
print_worklist(worklist, LEVEL_2);
DB((dbg, LEVEL_2, "\n"));
}
}
if(worklist == NULL) {
- /* only the end-block has 0 successors */
- assert(block == get_irg_end_block(get_irn_irg(block)));
+ /* at least 1 successor block must have been processed unless it was
+ * the end block */
+ assert(tentative_mode || block == get_irg_end_block(get_irn_irg(block)));
- worklist = obstack_alloc(&obst, sizeof(worklist[0]));
- init_worklist(worklist, 0);
+ worklist = new_worklist();
+#ifdef DEBUG_libfirm
+ DB((dbg, LEVEL_1, "worklist at end of %+F:", block));
+ print_worklist(worklist, LEVEL_1);
+ DB((dbg, LEVEL_1, "\n"));
+#endif
} else {
- worklist = duplicate_worklist(worklist, block, best_succ_block,
- best_pos);
- activate_worklist(worklist);
+ worklist = duplicate_activate_worklist(worklist, block, best_succ_block,
+ best_pos);
/* 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.
- */
- if(!tentative_mode) {
- foreach_block_succ(block, edge) {
- ir_node *succ_block = get_edge_src_irn(edge);
- worklist_t *succ_worklist = get_irn_link(succ_block);
-
- spill_non_live_nodes(succ_worklist);
- }
+ * 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);
+ worklist_t *succ_worklist = get_irn_link(succ_block);
+
+ if(succ_block == best_succ_block)
+ continue;
+
+ process_non_active_worklist(succ_worklist, worklist);
}
+
+#ifdef DEBUG_libfirm
+ DB((dbg, LEVEL_1, "worklist at end of %+F:", block));
+ print_worklist(worklist, LEVEL_1);
+ DB((dbg, LEVEL_1, "\n"));
+#endif
}
do_spilling(block, worklist);
arch_env = be_get_birg_arch_env(birg);
exec_freq = be_get_birg_exec_freq(birg);
- tentative_mode = 0;
be_clear_links(irg);
set_using_irn_link(irg);
/* 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);
clear_using_irn_link(irg);
projects / libfirm / blobdiff