Added clique walker

[libfirm] / ir / be / belive.c

diff --git a/ir/be/belive.c b/ir/be/belive.c
index ed6cd7f..ce7d6b8 100644 (file)
--- a/ir/be/belive.c
+++ b/ir/be/belive.c
@@ -8,7 +8,7 @@
 #endif
 
 #include "impl.h"
-#include "irouts.h"
+#include "iredges_t.h"
 #include "irgwalk.h"
 #include "irprintf_t.h"
 
@@ -34,7 +34,7 @@ static INLINE void mark_live_in(ir_node *block, const ir_node *irn)
 
 static INLINE void mark_live_out(ir_node *block, const ir_node *irn)
 {
-  _get_or_set_live(block, irn, live_state_out);
+  _get_or_set_live(block, irn, live_state_out | live_state_end);
 }
 
 static INLINE void mark_live_end(ir_node *block, const ir_node *irn)
@@ -73,7 +73,7 @@ static void live_end_at_block(ir_node *def, ir_node *block,
       mark_live_in(block, def);
 
       for(i = 0, n = get_irn_arity(block); i < n; ++i)
-        live_end_at_block(def, get_nodes_block(get_irn_n(block, i)), visited, 1);
+        live_end_at_block(def, get_Block_cfgpred_block(block, i), visited, 1);
     }
 
   }
@@ -88,7 +88,7 @@ static void live_end_at_block(ir_node *def, ir_node *block,
  */
 static void liveness_for_node(ir_node *irn, void *env)
 {
-  int i, n;
+  const ir_edge_t *edge;
   ir_node *def_block;
   pset *visited;
 
@@ -100,8 +100,8 @@ static void liveness_for_node(ir_node *irn, void *env)
   def_block = get_nodes_block(irn);
 
   /* Go over all uses of the value */
-  for(i = 0, n = get_irn_n_outs(irn); i < n; ++i) {
-    ir_node *use = get_irn_out(irn, i);
+  foreach_out_edge(irn, edge) {
+    ir_node *use = edge->src;
     ir_node *use_block;
 
     /*
@@ -120,17 +120,8 @@ static void liveness_for_node(ir_node *irn, void *env)
      * value as live out of that block.
      */
     if(is_Phi(use)) {
-      int i, n;
-
-      /* Mark the node as a phi operand, since a use by a phi was found. */
-      /* get_node_live_info(irn)->is_phi_op = 1; */
-
-      for(i = 0, n = get_irn_arity(use); i < n; ++i) {
-        if(get_irn_n(use, i) == irn) {
-          ir_node *pred_block = get_nodes_block(get_irn_n(use_block, i));
-          live_end_at_block(irn, pred_block, visited, 0);
-        }
-      }
+                       ir_node *pred_block = get_Block_cfgpred_block(use_block, edge->pos);
+                       live_end_at_block(irn, pred_block, visited, 0);
     }
 
     /*
@@ -160,9 +151,118 @@ static int cmp_irn_live(const void *a, const void *b, size_t size)
   return !(p->block == q->block && p->irn == q->irn);
 }
 
+static int (*old_dump_block_func)(ir_node *self, FILE *F, dump_reason_t reason) = NULL;
+
+static int dump_block_func(ir_node *self, FILE *F, dump_reason_t reason)
+{
+       switch(reason) {
+       case dump_node_opcode_txt:
+               fprintf(F, get_irn_opname(self));
+               break;
+       case dump_node_mode_txt:
+               fprintf(F, get_irn_modename(self));
+               break;
+       case dump_node_nodeattr_txt:
+               break;
+       case dump_node_info_txt:
+               if(!get_irg_live_info(get_irn_irg(self))->live)
+                       return 0;
+
+               fprintf(F, "liveness information:\n");
+               {
+                       irn_live_t *li;
+                       live_foreach(self, li) {
+                               ir_fprintf(F, "%+F", li->irn);
+                               if(live_is_in(li))
+                                       fprintf(F, " in");
+                               if(live_is_end(li))
+                                       fprintf(F, " end");
+                               if(live_is_out(li))
+                                       fprintf(F, " out");
+
+                               fprintf(F, "\n");
+                       }
+               }
+       }
+
+       return 0;
+}
+
 void be_liveness(ir_graph *irg)
 {
   irg_live_info_t *live_info = get_irg_live_info(irg);
+  if(live_info->live)
+    del_set(live_info->live);
+
   live_info->live = new_set(cmp_irn_live, 8192);
   irg_walk_graph(irg, liveness_for_node, NULL, NULL);
+
+  old_dump_block_func     = op_Block->ops.dump_node;
+  op_Block->ops.dump_node = dump_block_func;
+}
+
+static void dump_liveness_walker(ir_node *bl, void *data)
+{
+       FILE *f = data;
+       const irn_live_t *li;
+       char buf[64];
+
+       ir_fprintf(f, "%+F\n", bl);
+       live_foreach(bl, li) {
+               strcpy(buf, "");
+
+               if(live_is_in(li))
+                       strcat(buf, "in ");
+
+               if(live_is_end(li))
+                       strcat(buf, "end ");
+
+               if(live_is_out(li))
+                       strcat(buf, "out ");
+
+               ir_fprintf(f, "\t%+20F %s\n", li->irn, buf);
+       }
+}
+
+void be_liveness_dump(ir_graph *irg, FILE *f)
+{
+       irg_block_walk_graph(irg, dump_liveness_walker, NULL, f);
+}
+
+void be_liveness_dumpto(ir_graph *irg, const char *cls_name)
+{
+       FILE *f;
+       char buf[128];
+       ir_snprintf(buf, sizeof(buf), "%F_%s-live.txt", irg, cls_name);
+       if((f = fopen(buf, "wt")) != NULL) {
+               be_liveness_dump(irg, f);
+               fclose(f);
+       }
+}
+
+static void dom_check(ir_node *irn, void *data)
+{
+       if(!is_Block(irn) && irn != get_irg_end(get_irn_irg(irn))) {
+               int i, n;
+               ir_node *bl = get_nodes_block(irn);
+
+               for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
+                       ir_node *op     = get_irn_n(irn, i);
+                       ir_node *def_bl = get_nodes_block(op);
+                       ir_node *use_bl = bl;
+
+                       if(is_Phi(irn))
+                               use_bl = get_Block_cfgpred_block(bl, i);
+
+                       if(!block_dominates(def_bl, use_bl)) {
+                               ir_fprintf(stderr, "%+F in %+F must dominate %+F for user %+F\n", op, def_bl, use_bl, irn);
+                               assert(0);
+                       }
+               }
+       }
+}
+
+void be_check_dominance(ir_graph *irg)
+{
+       irg_walk_graph(irg, dom_check, NULL, NULL);
 }