Add a test for x + x + x + ...

[libfirm] / ir / be / belive.c

diff --git a/ir/be/belive.c b/ir/be/belive.c
index 0becbab..62e9d91 100644 (file)
--- a/ir/be/belive.c
+++ b/ir/be/belive.c
@@ -36,6 +36,10 @@
 #include "irdump_t.h"
 #include "irnodeset.h"
 
+#include "dfs_t.h"
+#include "absgraph.h"
+#include "statev.h"
+
 #include "beutil.h"
 #include "belive_t.h"
 #include "beirg_t.h"
@@ -50,12 +54,15 @@ DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
 #define LV_USE_BINARY_SEARCH
 #undef  LV_INTESIVE_CHECKS
 
+void be_live_chk_compare(be_lv_t *lv, lv_chk_t *lvc);
+
 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:
                return 0;
        default:;
        }
@@ -102,15 +109,6 @@ static INLINE unsigned _be_liveness_bsearch(struct _be_lv_info_t *arr, unsigned
        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;
@@ -162,8 +160,11 @@ static INLINE unsigned _be_liveness_bsearch(struct _be_lv_info_t *arr, unsigned
 
 struct _be_lv_info_node_t *be_lv_get(const struct _be_lv_t *li, const ir_node *bl, const ir_node *irn)
 {
-       struct _be_lv_info_t *irn_live = phase_get_irn_data(&li->ph, bl);
+       struct _be_lv_info_t *irn_live;
+       struct _be_lv_info_node_t *res = NULL;
 
+       stat_ev_tim_push();
+       irn_live = phase_get_irn_data(&li->ph, bl);
        if(irn_live) {
                unsigned idx = get_irn_idx(irn);
 
@@ -171,14 +172,15 @@ struct _be_lv_info_node_t *be_lv_get(const struct _be_lv_t *li, const ir_node *b
                int pos = _be_liveness_bsearch(irn_live, idx);
 
                /* Get the record in question. 1 must be added, since the first record contains information about the array and must be skipped. */
-               struct _be_lv_info_node_t *res = &irn_live[pos + 1].u.node;
+               struct _be_lv_info_node_t *rec = &irn_live[pos + 1].u.node;
 
                /* Check, if the irn is in deed in the array. */
-               if(res->idx == idx)
-                       return res;
+               if(rec->idx == idx)
+                       res = rec;
        }
+       stat_ev_tim_pop("be_lv_get");
 
-       return NULL;
+       return res;
 }
 
 static struct _be_lv_info_node_t *be_lv_get_or_set(struct _be_lv_t *li, ir_node *bl, ir_node *irn)
@@ -391,6 +393,9 @@ static void liveness_for_node(ir_node *irn, void *data)
                ir_node *use = edge->src;
                ir_node *use_block;
 
+               DBG((dbg, LEVEL_4, "%+F: use at %+F, pos %d in %+F\n", irn, use, edge->pos, get_block(use)));
+               assert(get_irn_n(use, edge->pos) == irn);
+
                /*
                 * If the usage is no data node, skip this use, since it does not
                 * affect the liveness of the node.
@@ -505,6 +510,7 @@ static void compute_liveness(be_lv_t *lv)
        ir_node **nodes;
        int i, n;
 
+       stat_ev_tim_push();
        obstack_init(&obst);
        irg_walk_graph(lv->irg, collect_nodes, NULL, &obst);
        n      = obstack_object_size(&obst) / sizeof(nodes[0]);
@@ -529,6 +535,7 @@ static void compute_liveness(be_lv_t *lv)
 
        obstack_free(&obst, NULL);
        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)
@@ -537,6 +544,7 @@ void be_liveness_assure_sets(be_lv_t *lv)
                lv->nodes = bitset_malloc(2 * get_irg_last_idx(lv->irg));
                phase_init(&lv->ph, "liveness", lv->irg, PHASE_DEFAULT_GROWTH, lv_phase_data_init, NULL);
                compute_liveness(lv);
+               /* be_live_chk_compare(lv, lv->lvc); */
        }
 }
 
@@ -560,14 +568,16 @@ void be_liveness_invalidate(be_lv_t *lv)
 }
 
 /* Compute the inter block liveness for a graph. */
-be_lv_t *be_liveness(ir_graph *irg)
+be_lv_t *be_liveness(const be_irg_t *birg)
 {
        be_lv_t *lv = xmalloc(sizeof(lv[0]));
 
        memset(lv, 0, sizeof(lv[0]));
-       lv->irg = irg;
+       lv->irg  = be_get_birg_irg(birg);
+       lv->birg = birg;
 #ifdef USE_LIVE_CHK
-       lv->lvc = lv_chk_new(irg);
+       lv->dfs  = dfs_new(&absgraph_irg_cfg_succ, lv->irg);
+       lv->lvc  = lv_chk_new(lv->irg, lv->dfs);
 #endif
        lv->hook_info.context = lv;
        lv->hook_info.hook._hook_node_info = lv_dump_block;
@@ -679,7 +689,7 @@ static void lv_check_walker(ir_node *bl, void *data)
 void be_liveness_check(be_lv_t *lv)
 {
        struct _lv_walker_t w;
-       be_lv_t *fresh = be_liveness(lv->irg);
+       be_lv_t *fresh = be_liveness(lv->birg);
 
        w.lv   = lv;
        w.data = fresh;
@@ -769,8 +779,6 @@ void be_liveness_transfer(const arch_env_t *arch_env,
         * function. */
        assert(!is_Phi(node) && "liveness_transfer produces invalid results for phi nodes");
 
-#ifndef SCHEDULE_PROJS
-       /* kill all Proj's if a node is killed */
        if (get_irn_mode(node) == mode_T) {
                const ir_edge_t *edge;
 
@@ -782,7 +790,6 @@ void be_liveness_transfer(const arch_env_t *arch_env,
                        }
                }
        }
-#endif
 
        if (arch_irn_consider_in_reg_alloc(arch_env, cls, node)) {
                ir_nodeset_remove(nodeset, node);
@@ -879,11 +886,12 @@ void be_live_chk_compare(be_lv_t *lv, lv_chk_t *lvc)
        obstack_ptr_grow(&obst, NULL);
        nodes = obstack_finish(&obst);
 
-       for (i = 0; blocks[i]; ++i) {
-               ir_node *bl = blocks[i];
+       stat_ev_ctx_push("be_lv_chk_compare");
+       for (j = 0; nodes[j]; ++j) {
+               ir_node *irn = nodes[j];
+               for (i = 0; blocks[i]; ++i) {
+                       ir_node *bl = blocks[i];
 
-               for (j = 0; nodes[j]; ++j) {
-                       ir_node *irn = nodes[j];
                        if (!is_Block(irn)) {
                                int lvr_in  = be_is_live_in (lv, bl, irn);
                                int lvr_out = be_is_live_out(lv, bl, irn);
@@ -904,7 +912,7 @@ void be_live_chk_compare(be_lv_t *lv, lv_chk_t *lvc)
                        }
                }
        }
-
+       stat_ev_ctx_pop("be_lv_chk_compare");
 
        obstack_free(&obst, NULL);
 }