* - merge multiple start worksets of blocks ~ok
* - how to and when to do the tentative phase...
*/
-#ifdef HAVE_CONFIG_H
#include "config.h"
-#endif
#include <stdbool.h>
#include "bemodule.h"
#include "bespill.h"
#include "beutil.h"
-#include "bespilloptions.h"
-#include "besched_t.h"
+#include "bespillutil.h"
+#include "besched.h"
#include "be_t.h"
+#ifndef NDEBUG
#define EXPENSIVE_CHECKS
+#endif
DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
ir_loop *unused_livethrough_loop;
};
+#define foreach_worklist(entry, wl) list_for_each_entry(worklist_entry_t, entry, &(wl)->live_values, head)
+
typedef struct worklist_t worklist_t;
struct worklist_t {
struct list_head live_values;
size_t n_live_values;
- unsigned long visited;
+ ir_visited_t visited;
};
typedef struct block_info_t block_info_t;
worklist_t *end_worklist;
};
-static const arch_env_t *arch_env;
+/** The register class we currently run on. */
static const arch_register_class_t *cls;
static struct obstack obst;
static spill_env_t *senv;
static size_t n_regs;
static size_t max_register_pressure;
static bool tentative_mode;
-static bool should_have_reached_fixpoint;
static bool do_push_unused_livethroughs;
+/** Execution frequency for the current graph. */
static ir_exec_freq *exec_freq;
-static unsigned long worklist_visited;
+static ir_visited_t worklist_visited;
+#ifdef DEBUG_libfirm
+static bool should_have_reached_fixpoint;
+#endif
static worklist_t *new_worklist(void)
{
- worklist_t *worklist = obstack_alloc(&obst, sizeof(worklist[0]));
- memset(worklist, 0, sizeof(worklist[0]));
+ worklist_t *worklist = OALLOCZ(&obst, worklist_t);
INIT_LIST_HEAD(&worklist->live_values);
worklist->n_live_values = 0;
if (info != NULL)
return info;
- info = obstack_alloc(&obst, sizeof(info[0]));
- memset(info, 0, sizeof(info[0]));
+ info = OALLOCZ(&obst, block_info_t);
set_irn_link(block, info);
return info;
}
static void deactivate_worklist(const worklist_t *worklist)
{
- struct list_head *entry;
+ worklist_entry_t *entry;
- list_for_each(entry, &worklist->live_values) {
- worklist_entry_t *wl_entry
- = list_entry(entry, worklist_entry_t, head);
- assert(worklist_contains(wl_entry->value));
- mark_irn_not_visited(wl_entry->value);
- set_irn_link(wl_entry->value, NULL);
+ foreach_worklist(entry, worklist) {
+ assert(worklist_contains(entry->value));
+ mark_irn_not_visited(entry->value);
+ set_irn_link(entry->value, NULL);
}
}
static void activate_worklist(const worklist_t *worklist)
{
- struct list_head *entry;
+ worklist_entry_t *entry;
- list_for_each(entry, &worklist->live_values) {
- worklist_entry_t *wl_entry
- = list_entry(entry, worklist_entry_t, head);
- assert(!worklist_contains(wl_entry->value));
- mark_irn_visited(wl_entry->value);
- set_irn_link(wl_entry->value, wl_entry);
+ foreach_worklist(entry, worklist) {
+ assert(!worklist_contains(entry->value));
+ mark_irn_visited(entry->value);
+ set_irn_link(entry->value, entry);
}
}
{
ir_node *reload_point = NULL;
size_t n_live_values = 0;
- struct list_head *entry;
+ worklist_entry_t *entry;
if (succ_block != NULL &&
(get_Block_n_cfgpreds(succ_block) > 1
reload_point = be_get_end_of_block_insertion_point(block);
}
- 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;
+ foreach_worklist(entry, worklist) {
+ ir_node *value = entry->value;
worklist_entry_t *new_entry;
if (new_worklist->n_live_values >= n_regs)
value = get_Phi_pred(value, succ_pos);
/* can happen for unknown phi preds */
- if (!arch_irn_consider_in_reg_alloc(arch_env, cls, value))
+ if (!arch_irn_consider_in_reg_alloc(cls, value))
continue;
}
- if (irn_visited(value))
+ if (irn_visited_else_mark(value))
continue;
- new_entry = obstack_alloc(&obst, sizeof(new_entry[0]));
- memset(new_entry, 0, sizeof(new_entry[0]));
+ new_entry = OALLOCZ(&obst, worklist_entry_t);
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->reload_point = entry->reload_point;
}
list_add_tail(&new_entry->head, &new_worklist->live_values);
++n_live_values;
- mark_irn_visited(value);
set_irn_link(value, new_entry);
new_worklist->n_live_values++;
}
worklist_t *new_worklist;
struct list_head *entry;
- new_worklist = obstack_alloc(&obst, sizeof(new_worklist[0]));
- memset(new_worklist, 0, sizeof(new_worklist[0]));
+ new_worklist = OALLOCZ(&obst, worklist_t);
INIT_LIST_HEAD(&new_worklist->live_values);
new_worklist->n_live_values = worklist->n_live_values;
list_for_each(entry, &worklist->live_values) {
worklist_entry_t *wl_entry = list_entry(entry, worklist_entry_t, head);
- worklist_entry_t *new_entry
- = obstack_alloc(&obst, sizeof(new_entry[0]));
+ worklist_entry_t *new_entry = OALLOC(&obst, worklist_entry_t);
memcpy(new_entry, wl_entry, sizeof(new_entry[0]));
list_add_tail(&new_entry->head, &new_worklist->live_values);
#endif
-
+/**
+ * Clear the link fields of a loop and all
+ * its child loops.
+ *
+ * @param loop the root loop
+ */
static void clear_loop_info(ir_loop *loop)
{
int n_elements = get_loop_n_elements(loop);
if (info != NULL)
return info;
- info = obstack_alloc(&obst, sizeof(info[0]));
- memset(info, 0, sizeof(info[0]));
+ info = OALLOCZ(&obst, loop_info_t);
info->loop = loop;
loop->link = info;
return info;
do {
loop_info_t *l_info = get_loop_info(l);
- edge = obstack_alloc(&obst, sizeof(edge[0]));
- memset(edge, 0, sizeof(edge[0]));
+ edge = OALLOCZ(&obst, loop_edge_t);
edge->block = block;
edge->pos = i;
assert(get_loop_depth(cfgpred_loop) < get_loop_depth(l));
}
l = get_loop_outer_loop(l);
- } while(l != goal);
+ } while (l != goal);
}
}
/* 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));
+ assert(arch_irn_consider_in_reg_alloc(cls, value));
if (worklist_contains(value)) {
assert(entry != NULL);
list_del(&entry->head);
} else {
if (entry == NULL) {
- entry = obstack_alloc(&obst, sizeof(entry[0]));
- memset(entry, 0, sizeof(entry[0]));
-
+ entry = OALLOCZ(&obst, worklist_entry_t);
entry->value = value;
set_irn_link(value, entry);
}
if (worklist_contains(node2))
continue;
- if (!arch_irn_consider_in_reg_alloc(arch_env, cls, node2))
+ if (!arch_irn_consider_in_reg_alloc(cls, node2))
continue;
if (!tentative_mode)
foreach_out_edge(node, edge) {
ir_node *proj = get_edge_src_irn(edge);
- if (!arch_irn_consider_in_reg_alloc(arch_env, cls, proj))
+ if (!arch_irn_consider_in_reg_alloc(cls, proj))
continue;
if (worklist_contains(proj)) {
worklist_remove(worklist, proj);
++n_defs;
}
}
- } else if (arch_irn_consider_in_reg_alloc(arch_env, cls, node)) {
+ } else if (arch_irn_consider_in_reg_alloc(cls, node)) {
if (worklist_contains(node)) {
worklist_remove(worklist, node);
} else {
for(i = 0; i < arity; ++i) {
ir_node *use = get_irn_n(node, i);
- if (!arch_irn_consider_in_reg_alloc(arch_env, cls, use))
+ if (!arch_irn_consider_in_reg_alloc(cls, use))
continue;
val_used(worklist, use, node);
double best_execfreq = -1;
worklist_t *best_worklist = NULL;
ir_node *best_succ_block = NULL;
- int best_pos;
+ int best_pos = -1;
const ir_edge_t *edge;
/* construct worklist */
//assert(n_preds != 0 || worklist->n_live_values == 0);
}
-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;
+typedef union block_or_loop_t block_or_loop_t;
+union block_or_loop_t {
+ ir_node *block;
+ ir_loop *loop;
};
static block_or_loop_t *loop_blocks;
if (Block_block_visited(some_block))
return;
- block_or_loop.v.loop = loop;
- block_or_loop.is_loop = true;
+ block_or_loop.loop = loop;
ARR_APP1(block_or_loop_t, loop_blocks, block_or_loop);
#ifndef NDEBUG
loop_edge_t *edge = loop_info->entry_edges;
bool found = false;
for ( ; edge != NULL; edge = edge->next) {
- if (edge->block == entry)
+ if (edge->block == entry) {
found = true;
+ break;
+ }
}
assert(found);
}
+#else
+ (void) entry;
#endif
+
/* check all loop successors */
for (edge = loop_info->exit_edges; edge != NULL; edge = edge->next) {
ir_node *succ = edge->block;
if (Block_block_visited(block))
return;
- block_or_loop.v.block = block;
- block_or_loop.is_loop = false;
+ block_or_loop.block = block;
ARR_APP1(block_or_loop_t, loop_blocks, block_or_loop);
mark_Block_block_visited(block);
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]));
+ worklist_entry_t *entry;
#ifdef EXPENSIVE_CHECKS
- {
- struct list_head *entry;
- list_for_each(entry, &worklist->live_values) {
- worklist_entry_t *wl_entry
- = list_entry(entry, worklist_entry_t, head);
- assert(wl_entry->value != value);
- }
+ foreach_worklist(entry, worklist) {
+ assert(entry->value != value);
}
#endif
+ entry = OALLOCZ(&obst, worklist_entry_t);
entry->value = value;
entry->reload_point = reload_point;
entry->unused_livethrough_loop = unused_livethrough_loop;
}
}
-static void process_block_or_loop(const block_or_loop_t *block_or_loop)
+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 (block_or_loop.loop->kind == k_ir_loop) {
+ loop_info_t *loop_info = get_loop_info(block_or_loop.loop);
if (do_push_unused_livethroughs)
push_unused_livethroughs(loop_info);
return;
}
- process_block(block_or_loop->v.block, NULL);
+ process_block(block_or_loop.block, NULL);
}
static void process_loop(ir_loop *loop)
some_block = get_irg_start_block(current_ir_graph);
}
- loop_blocks = NEW_ARR_F(block_or_loop_t,0);
+ loop_blocks = NEW_ARR_F(block_or_loop_t, 0);
current_loop = loop;
ir_reserve_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->is_loop) {
- DB((dbg, LEVEL_3, " L-%p", block_or_loop->v.loop));
+ 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->v.block));
+ DB((dbg, LEVEL_3, " B-%+F", block_or_loop.block));
}
}
DB((dbg, LEVEL_3, "\n"));
/* run1: tentative phase */
tentative_mode = true;
for (i = len-1; i >= 0; --i) {
- process_block_or_loop(&loop_blocks[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]);
+ process_block_or_loop(loop_blocks[i]);
}
#ifndef NDEBUG
tentative_mode = true;
should_have_reached_fixpoint = true;
for (i = len-1; i >= 0; --i) {
- process_block_or_loop(&loop_blocks[i]);
+ process_block_or_loop(loop_blocks[i]);
}
should_have_reached_fixpoint = false;
#endif
tentative_mode = false;
do_push_unused_livethroughs = true;
for (i = len-1; i >= 0; --i) {
- process_block_or_loop(&loop_blocks[i]);
+ process_block_or_loop(loop_blocks[i]);
}
do_push_unused_livethroughs = false;
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;
+ worklist_entry_t *entry;
assert(end_worklist != NULL);
/* 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;
+ 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(arch_env, cls, value))
+ if (!arch_irn_consider_in_reg_alloc(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);
}
}
}
+/**
+ * Run the spill algorithm.
+ *
+ * @param birg the graph to run on
+ * @param ncls the register class to run on
+ */
static void be_spill_belady3(be_irg_t *birg, const arch_register_class_t *ncls)
{
ir_graph *irg = be_get_birg_irg(birg);
return;
worklist_visited = 0;
- arch_env = be_get_birg_arch_env(birg);
exec_freq = be_get_birg_exec_freq(birg);
be_clear_links(irg);
clear_loop_info(get_irg_loop(irg));
irg_block_walk_graph(irg, construct_loop_edges, NULL, NULL);
- process_loop(get_irg_loop(current_ir_graph));
+ process_loop(get_irg_loop(irg));
irg_block_walk_graph(irg, fix_block_borders, NULL, NULL);
projects / libfirm / blobdiff