belive: Avoid duplicate map lookups when calculating the liveness of a node in a...
[libfirm] / ir / be / belive.c
index bcc28f5..12749a7 100644 (file)
 #include "belive_t.h"
 #include "besched.h"
 #include "bemodule.h"
-#include "bedump.h"
 
 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
 
 #define LV_STD_SIZE             64
 
-/**
- * Filter out some nodes for which we never need liveness.
- *
- * @param irn  the node t check
- * @return 0 if no liveness info is needed, 1 else
- */
-static inline int is_liveness_node(const ir_node *irn)
-{
-       switch (get_irn_opcode(irn)) {
-       case iro_Block:
-       case iro_Bad:
-       case iro_End:
-       case iro_Anchor:
-       case iro_NoMem:
-               return 0;
-       default:
-               return 1;
-       }
-}
-
 int (be_is_live_in)(const be_lv_t *lv, const ir_node *block, const ir_node *irn)
 {
        return _be_is_live_xxx(lv, block, irn, be_lv_state_in);
@@ -83,7 +62,7 @@ int (be_is_live_end)(const be_lv_t *lv, const ir_node *block, const ir_node *irn
        return _be_is_live_xxx(lv, block, irn, be_lv_state_end);
 }
 
-static inline unsigned _be_liveness_bsearch(be_lv_info_t *arr, unsigned idx)
+static inline unsigned _be_liveness_bsearch(be_lv_info_t *arr, const ir_node *node)
 {
        be_lv_info_t *payload = arr + 1;
 
@@ -96,16 +75,15 @@ static inline unsigned _be_liveness_bsearch(be_lv_info_t *arr, unsigned idx)
                return 0;
 
        do {
-               int md          = lo + ((hi - lo) >> 1);
-               unsigned md_idx = payload[md].node.idx;
+               int md           = lo + ((hi - lo) >> 1);
+               ir_node *md_node = payload[md].node.node;
 
-               if (idx > md_idx)
+               if (node > md_node)
                        lo = md + 1;
-               else if (idx < md_idx)
+               else if (node < md_node)
                        hi = md;
                else {
                        res = md;
-                       assert(payload[res].node.idx == idx);
                        break;
                }
 
@@ -124,16 +102,14 @@ be_lv_info_node_t *be_lv_get(const be_lv_t *li, const ir_node *bl,
        stat_ev_tim_push();
        irn_live = ir_nodehashmap_get(be_lv_info_t, &li->map, bl);
        if (irn_live != NULL) {
-               unsigned idx = get_irn_idx(irn);
-
                /* Get the position of the index in the array. */
-               int pos = _be_liveness_bsearch(irn_live, idx);
+               int pos = _be_liveness_bsearch(irn_live, irn);
 
                /* Get the record in question. 1 must be added, since the first record contains information about the array and must be skipped. */
                be_lv_info_node_t *rec = &irn_live[pos + 1].node;
 
                /* Check, if the irn is in deed in the array. */
-               if (rec->idx == idx)
+               if (rec->node == irn)
                        res = rec;
        }
        stat_ev_tim_pop("be_lv_get");
@@ -151,16 +127,14 @@ static be_lv_info_node_t *be_lv_get_or_set(be_lv_t *li, ir_node *bl,
                ir_nodehashmap_insert(&li->map, bl, irn_live);
        }
 
-       unsigned idx = get_irn_idx(irn);
-
        /* Get the position of the index in the array. */
-       unsigned pos = _be_liveness_bsearch(irn_live, idx);
+       unsigned pos = _be_liveness_bsearch(irn_live, irn);
 
        /* Get the record in question. 1 must be added, since the first record contains information about the array and must be skipped. */
        be_lv_info_node_t *res = &irn_live[pos + 1].node;
 
        /* Check, if the irn is in deed in the array. */
-       if (res->idx != idx) {
+       if (res->node != irn) {
                be_lv_info_t *payload;
                unsigned n_members = irn_live[0].head.n_members;
                unsigned n_size    = irn_live[0].head.n_size;
@@ -188,9 +162,9 @@ static be_lv_info_node_t *be_lv_get_or_set(be_lv_t *li, ir_node *bl,
 
                ++irn_live[0].head.n_members;
 
-               res = &payload[pos].node;
-               res->idx    = idx;
-               res->flags  = 0;
+               res        = &payload[pos].node;
+               res->node  = irn;
+               res->flags = 0;
        }
 
        return res;
@@ -207,19 +181,18 @@ static int be_lv_remove(be_lv_t *li, const ir_node *bl,
 
        if (irn_live != NULL) {
                unsigned n   = irn_live[0].head.n_members;
-               unsigned idx = get_irn_idx(irn);
-               unsigned pos = _be_liveness_bsearch(irn_live, idx);
+               unsigned pos = _be_liveness_bsearch(irn_live, irn);
                be_lv_info_t *payload  = irn_live + 1;
                be_lv_info_node_t *res = &payload[pos].node;
 
                /* The node is in deed in the block's array. Let's remove it. */
-               if (res->idx == idx) {
+               if (res->node == irn) {
                        unsigned i;
 
                        for (i = pos + 1; i < n; ++i)
                                payload[i - 1] = payload[i];
 
-                       payload[n - 1].node.idx   = 0;
+                       payload[n - 1].node.node  = NULL;
                        payload[n - 1].node.flags = 0;
 
                        --irn_live[0].head.n_members;
@@ -231,36 +204,6 @@ static int be_lv_remove(be_lv_t *li, const ir_node *bl,
        return 0;
 }
 
-/**
- * Mark a node as live-in in a block.
- */
-static inline void mark_live_in(be_lv_t *lv, ir_node *block, ir_node *irn)
-{
-       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;
-}
-
-/**
- * Mark a node as live-out in a block.
- */
-static inline void mark_live_out(be_lv_t *lv, ir_node *block, ir_node *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;
-}
-
-/**
- * Mark a node as live-end in a block.
- */
-static inline void mark_live_end(be_lv_t *lv, ir_node *block, ir_node *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;
-}
-
 static struct {
        be_lv_t  *lv;         /**< The liveness object. */
        ir_node  *def;        /**< The node (value). */
@@ -278,15 +221,12 @@ static struct {
  */
 static void live_end_at_block(ir_node *block, int is_true_out)
 {
-       be_lv_t *lv  = re.lv;
-       ir_node *def = re.def;
-       bitset_t *visited;
+       be_lv_info_node_t *const n = be_lv_get_or_set(re.lv, block, re.def);
 
-       mark_live_end(lv, block, def);
-       if (is_true_out)
-               mark_live_out(lv, block, def);
+       DBG((dbg, LEVEL_2, "marking %+F live %s at %+F\n", re.def, is_true_out ? "end+out" : "end", block));
+       n->flags |= is_true_out ? be_lv_state_out | be_lv_state_end : be_lv_state_out;
 
-       visited = re.visited;
+       bitset_t *const visited = re.visited;
        if (!bitset_is_set(visited, get_irn_idx(block))) {
                bitset_set(visited, get_irn_idx(block));
 
@@ -297,7 +237,8 @@ static void live_end_at_block(ir_node *block, int is_true_out)
                if (re.def_block != block) {
                        int i;
 
-                       mark_live_in(lv, block, def);
+                       DBG((dbg, LEVEL_2, "marking %+F live in at %+F\n", re.def, block));
+                       n->flags |= be_lv_state_in;
 
                        for (i = get_Block_n_cfgpreds(block) - 1; i >= 0; --i)
                                live_end_at_block(get_Block_cfgpred_block(block, i), 1);
@@ -361,7 +302,9 @@ static void liveness_for_node(ir_node *irn)
                else if (def_block != use_block) {
                        int i;
 
-                       mark_live_in(re.lv, use_block, irn);
+                       be_lv_info_node_t *const n = be_lv_get_or_set(re.lv, use_block, irn);
+                       DBG((dbg, LEVEL_2, "marking %+F live in at %+F\n", irn, use_block));
+                       n->flags |= be_lv_state_in;
 
                        for (i = get_Block_n_cfgpreds(use_block) - 1; i >= 0; --i) {
                                ir_node *pred_block = get_Block_cfgpred_block(use_block, i);
@@ -390,7 +333,6 @@ static void collect_liveness_nodes(ir_node *irn, void *data)
 
 void be_liveness_compute_sets(be_lv_t *lv)
 {
-       ir_node **nodes;
        int       i;
        int       n;
 
@@ -402,8 +344,7 @@ void be_liveness_compute_sets(be_lv_t *lv)
        obstack_init(&lv->obst);
 
        n = get_irg_last_idx(lv->irg);
-       nodes = NEW_ARR_F(ir_node *, n);
-       memset(nodes, 0, sizeof(nodes[0]) * n);
+       ir_node **const nodes = NEW_ARR_FZ(ir_node*, n);
 
        /* inserting the variables sorted by their ID is probably
         * more efficient since the binary sorted set insertion
@@ -420,7 +361,6 @@ void be_liveness_compute_sets(be_lv_t *lv)
 
        DEL_ARR_F(nodes);
        free(re.visited);
-       register_hook(hook_node_info, &lv->hook_info);
 
        be_timer_pop(T_LIVE);
 
@@ -438,7 +378,6 @@ void be_liveness_invalidate_sets(be_lv_t *lv)
 {
        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;
@@ -459,8 +398,6 @@ be_lv_t *be_liveness_new(ir_graph *irg)
        be_lv_t *lv = XMALLOCZ(be_lv_t);
 
        lv->irg = irg;
-       lv->hook_info.context = lv;
-       lv->hook_info.hook._hook_node_info = be_dump_liveness_block;
 
        return lv;
 }
@@ -513,17 +450,13 @@ void be_liveness_transfer(const arch_register_class_t *cls,
         * function. */
        assert(!is_Phi(node) && "liveness_transfer produces invalid results for phi nodes");
 
-       be_foreach_definition(node, cls, value,
+       be_foreach_definition(node, cls, value, req,
                ir_nodeset_remove(nodeset, value);
        );
 
-       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))
-                       continue;
+       be_foreach_use(node, cls, in_req, op, op_req,
                ir_nodeset_insert(nodeset, op);
-       }
+       );
 }
 
 
@@ -533,10 +466,7 @@ void be_liveness_end_of_block(const be_lv_t *lv,
                               const ir_node *block, ir_nodeset_t *live)
 {
        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;
-
+       be_lv_foreach_cls(lv, block, be_lv_state_end, cls, node) {
                ir_nodeset_insert(live, node);
        }
 }