#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)
{
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;
}
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;
+ unsigned last_idx;
+
+ if (lv->sets_valid)
+ return;
+
+ 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_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->lvc = lv_chk_new(lv->irg);
-#endif
+ lv->irg = irg;
lv->hook_info.context = lv;
lv->hook_info.hook._hook_node_info = be_dump_liveness_block;
+ lv->nodes = bitset_malloc(2 * get_irg_last_idx(lv->irg));
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);
-#endif
+ be_liveness_invalidate_sets(lv);
+ be_liveness_invalidate_chk(lv);
+
+ bitset_free(lv->nodes);
xfree(lv);
}
void be_liveness_remove(be_lv_t *lv, const ir_node *irn)
{
- if (lv->nodes) {
+ if (lv->sets_valid) {
unsigned idx = get_irn_idx(irn);
lv_remove_walker_t w;
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);
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");
}