#include "irdump_t.h"
#include "irnodeset.h"
-#include "dfs_t.h"
#include "absgraph.h"
-#include "statev.h"
+#include "statev_t.h"
#include "beutil.h"
#include "belive_t.h"
#define LV_STD_SIZE 64
-/* if defined, use binary search for already live nodes, else linear */
-#define LV_USE_BINARY_SEARCH
-#undef LV_INTESIVE_CHECKS
-
-void be_live_chk_compare(be_lv_t *lv, lv_chk_t *lvc);
-
/**
* Filter out some nodes for which we never need liveness.
*
return _be_is_live_xxx(lv, block, irn, be_lv_state_end);
}
-
-#ifdef LV_USE_BINARY_SEARCH
static inline unsigned _be_liveness_bsearch(be_lv_info_t *arr, unsigned idx)
{
be_lv_info_t *payload = arr + 1;
res = lo;
} while (lo < hi);
-#ifdef LV_INTESIVE_CHECKS
- {
- unsigned i;
- for (i = res; i < n; ++i)
- assert(payload[i].node.idx >= idx);
-
- for (i = 0; i < res; ++i)
- assert(payload[i].node.idx < idx);
- }
-#endif
-
return res;
}
-#else
-
-/**
- * This function searches linearly for the node in the array.
- */
-static inline unsigned _be_liveness_bsearch(be_lv_info_t *arr, unsigned idx)
-{
- unsigned n = arr[0].head.n_members;
- unsigned i;
-
- for (i = 0; i < n; ++i) {
- if (arr[i + 1].node.idx == idx)
- return i;
- }
-
- return i;
-}
-#endif
-
be_lv_info_node_t *be_lv_get(const be_lv_t *li, const ir_node *bl,
const ir_node *irn)
{
be_lv_info_node_t *res = NULL;
stat_ev_tim_push();
- irn_live = (be_lv_info_t*)ir_nodehashmap_get(&li->map, bl);
+ irn_live = ir_nodehashmap_get(be_lv_info_t, &li->map, bl);
if (irn_live != NULL) {
unsigned idx = get_irn_idx(irn);
static be_lv_info_node_t *be_lv_get_or_set(be_lv_t *li, ir_node *bl,
ir_node *irn)
{
- be_lv_info_t *irn_live = (be_lv_info_t*)ir_nodehashmap_get(&li->map, bl);
+ be_lv_info_t *irn_live = ir_nodehashmap_get(be_lv_info_t, &li->map, bl);
if (irn_live == NULL) {
irn_live = OALLOCNZ(&li->obst, be_lv_info_t, LV_STD_SIZE);
irn_live[0].head.n_size = LV_STD_SIZE-1;
res->flags = 0;
}
-#ifdef LV_INTESIVE_CHECKS
- {
- unsigned i;
- unsigned n = irn_live[0].head.n_members;
- unsigned last = 0;
- be_lv_info_t *payload = &irn_live[1];
-
- for (i = 0; i < n; ++i) {
- assert(payload[i].node.idx >= last);
- last = payload[i].node.idx;
- }
- }
-#endif
-
return res;
}
static int be_lv_remove(be_lv_t *li, const ir_node *bl,
const ir_node *irn)
{
- be_lv_info_t *irn_live = (be_lv_info_t*)ir_nodehashmap_get(&li->map, bl);
+ be_lv_info_t *irn_live = ir_nodehashmap_get(be_lv_info_t, &li->map, bl);
if (irn_live != NULL) {
unsigned n = irn_live[0].head.n_members;
return 0;
}
-static void register_node(be_lv_t *lv, const ir_node *irn)
-{
- unsigned idx = get_irn_idx(irn);
- if (idx >= bitset_size(lv->nodes)) {
- bitset_t *nw = bitset_malloc(2 * idx);
- bitset_copy_into(nw, lv->nodes);
- bitset_free(lv->nodes);
- lv->nodes = nw;
- }
-
- bitset_set(lv->nodes, idx);
-}
-
/**
* Mark a node as live-in in a block.
*/
be_lv_info_node_t *n = be_lv_get_or_set(lv, block, irn);
DBG((dbg, LEVEL_2, "marking %+F live in at %+F\n", irn, block));
n->flags |= be_lv_state_in;
- register_node(lv, irn);
}
/**
be_lv_info_node_t *n = be_lv_get_or_set(lv, block, irn);
DBG((dbg, LEVEL_2, "marking %+F live out at %+F\n", irn, block));
n->flags |= be_lv_state_out | be_lv_state_end;
- register_node(lv, irn);
}
/**
be_lv_info_node_t *n = be_lv_get_or_set(lv, block, irn);
DBG((dbg, LEVEL_2, "marking %+F live end at %+F\n", irn, block));
n->flags |= be_lv_state_end;
- register_node(lv, irn);
}
static struct {
*/
static void liveness_for_node(ir_node *irn)
{
- const ir_edge_t *edge;
ir_node *def_block;
bitset_clear_all(re.visited);
nodes[get_irn_idx(irn)] = irn;
}
-static void compute_liveness(be_lv_t *lv)
+void be_liveness_compute_sets(be_lv_t *lv)
{
ir_node **nodes;
- int i, n;
+ int i;
+ int n;
+
+ if (lv->sets_valid)
+ return;
+
+ be_timer_push(T_LIVE);
+ ir_nodehashmap_init(&lv->map);
+ obstack_init(&lv->obst);
- stat_ev_tim_push();
n = get_irg_last_idx(lv->irg);
nodes = NEW_ARR_F(ir_node *, n);
memset(nodes, 0, sizeof(nodes[0]) * n);
- /*
- * inserting the variables sorted by their ID is probably
+ /* inserting the variables sorted by their ID is probably
* more efficient since the binary sorted set insertion
- * will not need to move around the data.
- */
+ * will not need to move around the data. */
irg_walk_graph(lv->irg, NULL, collect_liveness_nodes, nodes);
re.lv = lv;
DEL_ARR_F(nodes);
free(re.visited);
register_hook(hook_node_info, &lv->hook_info);
- stat_ev_tim_pop("be_lv_sets_cons");
-}
-void be_liveness_assure_sets(be_lv_t *lv)
-{
- if (!lv->nodes) {
- be_timer_push(T_LIVE);
+ be_timer_pop(T_LIVE);
- lv->nodes = bitset_malloc(2 * get_irg_last_idx(lv->irg));
- ir_nodehashmap_init(&lv->map);
- obstack_init(&lv->obst);
- compute_liveness(lv);
- /* be_live_chk_compare(lv, lv->lvc); */
+ lv->sets_valid = true;
+}
- be_timer_pop(T_LIVE);
- }
+void be_liveness_compute_chk(be_lv_t *lv)
+{
+ if (lv->lvc != NULL)
+ return;
+ lv->lvc = lv_chk_new(lv->irg);
}
-void be_liveness_assure_chk(be_lv_t *lv)
+void be_liveness_invalidate_sets(be_lv_t *lv)
{
-#ifndef USE_LIVE_CHK
- be_timer_push(t_verify);
- be_liveness_assure_sets(lv);
- be_timer_pop(t_verify);
-#else
- (void) lv;
-#endif
+ if (!lv->sets_valid)
+ return;
+ unregister_hook(hook_node_info, &lv->hook_info);
+ obstack_free(&lv->obst, NULL);
+ ir_nodehashmap_destroy(&lv->map);
+ lv->sets_valid = false;
}
-void be_liveness_invalidate(be_lv_t *lv)
+void be_liveness_invalidate_chk(be_lv_t *lv)
{
- if (lv && lv->nodes) {
- unregister_hook(hook_node_info, &lv->hook_info);
- obstack_free(&lv->obst, NULL);
- ir_nodehashmap_destroy(&lv->map);
- bitset_free(lv->nodes);
- lv->nodes = NULL;
- }
+ be_liveness_invalidate_sets(lv);
+
+ if (lv->lvc == NULL)
+ return;
+ lv_chk_free(lv->lvc);
+ lv->lvc = NULL;
}
-/* Compute the inter block liveness for a graph. */
-be_lv_t *be_liveness(ir_graph *irg)
+be_lv_t *be_liveness_new(ir_graph *irg)
{
be_lv_t *lv = XMALLOCZ(be_lv_t);
- lv->irg = irg;
-#ifdef USE_LIVE_CHK
- lv->dfs = dfs_new(&absgraph_irg_cfg_succ, irg);
- lv->lvc = lv_chk_new(lv->irg, lv->dfs);
-#endif
+ lv->irg = irg;
lv->hook_info.context = lv;
lv->hook_info.hook._hook_node_info = be_dump_liveness_block;
return lv;
}
-void be_liveness_recompute(be_lv_t *lv)
-{
- unsigned last_idx;
-
- be_timer_push(T_LIVE);
- last_idx = get_irg_last_idx(lv->irg);
- if (last_idx >= bitset_size(lv->nodes)) {
- bitset_free(lv->nodes);
- lv->nodes = bitset_malloc(last_idx * 2);
- } else
- bitset_clear_all(lv->nodes);
-
- ir_nodehashmap_destroy(&lv->map);
- obstack_free(&lv->obst, NULL);
-
- ir_nodehashmap_init(&lv->map);
- obstack_init(&lv->obst);
- compute_liveness(lv);
-
- be_timer_pop(T_LIVE);
-}
-
-
void be_liveness_free(be_lv_t *lv)
{
- be_liveness_invalidate(lv);
-#ifdef USE_LIVE_CHK
- lv_chk_free(lv->lvc);
- dfs_free(lv->dfs);
-#endif
+ be_liveness_invalidate_sets(lv);
+ be_liveness_invalidate_chk(lv);
+
xfree(lv);
}
void be_liveness_remove(be_lv_t *lv, const ir_node *irn)
{
- if (lv->nodes) {
- unsigned idx = get_irn_idx(irn);
+ if (lv->sets_valid) {
lv_remove_walker_t w;
/*
w.lv = lv;
w.irn = irn;
dom_tree_walk(get_nodes_block(irn), lv_remove_irn_walker, NULL, &w);
- if (idx < bitset_size(lv->nodes))
- bitset_clear(lv->nodes, idx);
}
}
void be_liveness_introduce(be_lv_t *lv, ir_node *irn)
{
/* Don't compute liveness information for non-data nodes. */
- if (lv->nodes && is_liveness_node(irn)) {
+ if (lv->sets_valid && is_liveness_node(irn)) {
re.lv = lv;
re.visited = bitset_malloc(get_irg_last_idx(lv->irg));
liveness_for_node(irn);
void be_liveness_transfer(const arch_register_class_t *cls,
ir_node *node, ir_nodeset_t *nodeset)
{
- int i, arity;
-
/* You should better break out of your loop when hitting the first phi
* function. */
assert(!is_Phi(node) && "liveness_transfer produces invalid results for phi nodes");
- if (get_irn_mode(node) == mode_T) {
- const ir_edge_t *edge;
-
- foreach_out_edge(node, edge) {
- ir_node *proj = get_edge_src_irn(edge);
+ ir_node *value;
+ be_foreach_definition(node, cls, value,
+ ir_nodeset_remove(nodeset, value);
+ );
- if (arch_irn_consider_in_reg_alloc(cls, proj)) {
- ir_nodeset_remove(nodeset, proj);
- }
- }
- } else if (arch_irn_consider_in_reg_alloc(cls, node)) {
- ir_nodeset_remove(nodeset, node);
- }
-
- arity = get_irn_arity(node);
- for (i = 0; i < arity; ++i) {
+ int arity = get_irn_arity(node);
+ for (int i = 0; i < arity; ++i) {
ir_node *op = get_irn_n(node, i);
-
- if (arch_irn_consider_in_reg_alloc(cls, op))
- ir_nodeset_insert(nodeset, op);
+ if (!arch_irn_consider_in_reg_alloc(cls, op))
+ continue;
+ ir_nodeset_insert(nodeset, op);
}
}
const arch_register_class_t *cls,
const ir_node *block, ir_nodeset_t *live)
{
- int i;
-
- assert(lv->nodes && "live sets must be computed");
- be_lv_foreach(lv, block, be_lv_state_end, i) {
- ir_node *node = be_lv_get_irn(lv, block, i);
+ assert(lv->sets_valid && "live sets must be computed");
+ be_lv_foreach(lv, block, be_lv_state_end, node) {
if (!arch_irn_consider_in_reg_alloc(cls, node))
continue;
const ir_node *pos, ir_nodeset_t *live)
{
const ir_node *bl = is_Block(pos) ? pos : get_nodes_block(pos);
- ir_node *irn;
be_liveness_end_of_block(lv, cls, bl, live);
sched_foreach_reverse(bl, irn) {
obstack_ptr_grow(obst, irn);
}
-void be_live_chk_compare(be_lv_t *lv, lv_chk_t *lvc)
+static void be_live_chk_compare(be_lv_t *lv, lv_chk_t *lvc)
{
ir_graph *irg = lv->irg;
BE_REGISTER_MODULE_CONSTRUCTOR(be_init_live)
void be_init_live(void)
{
+ (void)be_live_chk_compare;
FIRM_DBG_REGISTER(dbg, "firm.be.liveness");
}
projects / libfirm / blobdiff