DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
+/* see comment in compute_liveness() */
+#define LV_COMPUTE_SORTED
#define LV_STD_SIZE 64
#define LV_USE_BINARY_SEARCH
#undef LV_INTESIVE_CHECKS
case iro_Block:
case iro_Bad:
case iro_End:
+ case iro_Anchor:
return 0;
default:;
}
if(n == 0)
return 0;
-#if 0
- if(idx < payload[0].u.node.idx)
- return 0;
-
- if(idx > payload[n - 1].u.node.idx)
- return n - 1;
-#endif
-
- /* start a binary search for the requested node. */
while(lo < hi) {
int md = lo + ((hi - lo) >> 1);
unsigned md_idx = payload[md].u.node.idx;
static void *lv_phase_data_init(ir_phase *phase, ir_node *irn, void *old)
{
struct _be_lv_info_t *info = phase_alloc(phase, LV_STD_SIZE * sizeof(info[0]));
+ (void) irn;
+ (void) old;
+
memset(info, 0, LV_STD_SIZE * sizeof(info[0]));
info[0].u.head.n_size = LV_STD_SIZE - 1;
return info;
}
+static void collect_nodes(ir_node *irn, void *data)
+{
+ struct obstack *obst = data;
+ if (is_liveness_node(irn))
+ obstack_ptr_grow(obst, irn);
+}
+
+static int node_idx_cmp(const void *a, const void *b)
+{
+ const ir_node *p = *(ir_node **) a;
+ const ir_node *q = *(ir_node **) b;
+ int ia = get_irn_idx(p);
+ int ib = get_irn_idx(q);
+ return ia - ib;
+}
+
static void compute_liveness(be_lv_t *lv)
{
+ struct obstack obst;
struct _lv_walker_t w;
+ ir_node **nodes;
+ int i, n;
+
+ obstack_init(&obst);
+ irg_walk_graph(lv->irg, collect_nodes, NULL, &obst);
+ n = obstack_object_size(&obst) / sizeof(nodes[0]);
+ nodes = obstack_finish(&obst);
+
+ /*
+ * inserting the variables sorted by their ID is probably
+ * more efficient since the binary sorted set insertion
+ * will not need to move arounf the data.
+ * However, if sorting the variables a priori pays off
+ * needs to be checked, hence the define.
+ */
+#ifdef LV_COMPUTE_SORTED
+ qsort(nodes, n, sizeof(nodes[0]), node_idx_cmp);
+#endif
+
w.lv = lv;
- w.data = bitset_malloc(get_irg_last_idx(lv->irg));
- irg_walk_graph(lv->irg, liveness_for_node, NULL, &w);
- bitset_free(w.data);
+ w.data = bitset_obstack_alloc(&obst, get_irg_last_idx(lv->irg));
+
+ for (i = 0; i < n; ++i)
+ liveness_for_node(nodes[i], &w);
+
+ obstack_free(&obst, NULL);
+ register_hook(hook_node_info, &lv->hook_info);
}
void be_liveness_assure_sets(be_lv_t *lv)
void be_liveness_assure_chk(be_lv_t *lv)
{
#ifndef USE_LIVE_CHK
- be_liveness_assure_sets(be_lv_t *lv);
+ be_liveness_assure_sets(lv);
+#else
+ (void) lv;
#endif
}
void be_liveness_invalidate(be_lv_t *lv)
{
if (lv && lv->nodes) {
+ unregister_hook(hook_node_info, &lv->hook_info);
phase_free(&lv->ph);
bitset_free(lv->nodes);
lv->nodes = NULL;
memset(lv, 0, sizeof(lv[0]));
lv->irg = irg;
+#ifdef USE_LIVE_CHK
lv->lvc = lv_chk_new(irg);
+#endif
lv->hook_info.context = lv;
lv->hook_info.hook._hook_node_info = lv_dump_block;
- register_hook(hook_node_info, &lv->hook_info);
return lv;
}
void be_liveness_free(be_lv_t *lv)
{
be_liveness_invalidate(lv);
- unregister_hook(hook_node_info, &lv->hook_info);
free(lv);
}
return !problem_found;
}
-pset *be_liveness_transfer(const arch_env_t *arch_env, const arch_register_class_t *cls, ir_node *irn, pset *live)
-{
- int i, n;
-
- /* You should better break out of your loop when hitting the first phi function. */
- assert(!is_Phi(irn) && "liveness_transfer produces invalid results for phi nodes");
-
- if(arch_irn_consider_in_reg_alloc(arch_env, cls, irn)) {
- ir_node *del = pset_remove_ptr(live, irn);
- (void) del;
- assert(irn == del);
- }
-
- for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
- ir_node *op = get_irn_n(irn, i);
-
- if(arch_irn_consider_in_reg_alloc(arch_env, cls, op))
- pset_insert_ptr(live, op);
- }
-
- return live;
-}
-
-void be_liveness_transfer_ir_nodeset(const arch_env_t *arch_env,
- const arch_register_class_t *cls,
- ir_node *node, ir_nodeset_t *nodeset)
+void be_liveness_transfer(const arch_env_t *arch_env,
+ const arch_register_class_t *cls,
+ ir_node *node, ir_nodeset_t *nodeset)
{
int i, arity;
* function. */
assert(!is_Phi(node) && "liveness_transfer produces invalid results for phi nodes");
- if(arch_irn_consider_in_reg_alloc(arch_env, cls, node)) {
+ 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);
+
+ if (arch_irn_consider_in_reg_alloc(arch_env, cls, proj)) {
+ ir_nodeset_remove(nodeset, proj);
+ }
+ }
+ }
+
+ if (arch_irn_consider_in_reg_alloc(arch_env, cls, node)) {
ir_nodeset_remove(nodeset, node);
}
arity = get_irn_arity(node);
- for(i = 0; i < arity; ++i) {
+ for (i = 0; i < arity; ++i) {
ir_node *op = get_irn_n(node, i);
- if(arch_irn_consider_in_reg_alloc(arch_env, cls, op))
+ if (arch_irn_consider_in_reg_alloc(arch_env, cls, op))
ir_nodeset_insert(nodeset, op);
}
}
-pset *be_liveness_end_of_block(const be_lv_t *lv, const arch_env_t *arch_env, const arch_register_class_t *cls, const ir_node *bl, pset *live)
-{
- int i;
- assert(lv->nodes && "live sets must be computed");
- be_lv_foreach(lv, bl, be_lv_state_end, i) {
- ir_node *irn = be_lv_get_irn(lv, bl, i);
- if(arch_irn_consider_in_reg_alloc(arch_env, cls, irn))
- pset_insert_ptr(live, irn);
- }
-
- return live;
-}
-
-void be_liveness_end_of_block_ir_nodeset(const be_lv_t *lv,
- const arch_env_t *arch_env,
- const arch_register_class_t *cls,
- const ir_node *block,
- ir_nodeset_t *live)
+void be_liveness_end_of_block(const be_lv_t *lv, const arch_env_t *arch_env,
+ const arch_register_class_t *cls,
+ const ir_node *block, ir_nodeset_t *live)
{
int i;
-pset *be_liveness_nodes_live_at(const be_lv_t *lv, const arch_env_t *arch_env, const arch_register_class_t *cls, const ir_node *pos, pset *live)
+void be_liveness_nodes_live_at(const be_lv_t *lv, const arch_env_t *arch_env,
+ const arch_register_class_t *cls,
+ const ir_node *pos, ir_nodeset_t *live)
{
const ir_node *bl = is_Block(pos) ? pos : get_nodes_block(pos);
ir_node *irn;
* exit immediately, so that this node is still live
*/
if(irn == pos)
- return live;
+ return;
be_liveness_transfer(arch_env, cls, irn, live);
}
-
- return live;
}
-pset *be_liveness_nodes_live_at_input(const be_lv_t *lv, const arch_env_t *arch_env, const arch_register_class_t *cls, const ir_node *pos, pset *live)
+void be_liveness_nodes_live_at_input(const be_lv_t *lv,
+ const arch_env_t *arch_env,
+ const arch_register_class_t *cls,
+ const ir_node *pos, ir_nodeset_t *live)
{
const ir_node *bl = is_Block(pos) ? pos : get_nodes_block(pos);
ir_node *irn;
sched_foreach_reverse(bl, irn) {
be_liveness_transfer(arch_env, cls, irn, live);
if(irn == pos)
- return live;
+ return;
}
-
- return live;
}
static void collect_node(ir_node *irn, void *data)
projects / libfirm / blobdiff