X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbelive.c;h=ce7d6b8bd70b2bf336bbf99f1d10c3247a95c17c;hb=1b8713c0eca7389d9db2a74302e206d718edc902;hp=d54028ce42bd078088f0a9632170c81db3414e71;hpb=d26125ca5720072a4975d37c0a17f7ad6c18de2d;p=libfirm

diff --git a/ir/be/belive.c b/ir/be/belive.c
index d54028ce4..ce7d6b8bd 100644
--- a/ir/be/belive.c
+++ b/ir/be/belive.c
@@ -3,42 +3,43 @@
  * @author Sebastian Hack
  * @date 6.12.2004
  */
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
 
-#include "irouts.h"
+#include "impl.h"
+#include "iredges_t.h"
 #include "irgwalk.h"
-#include "irprintf.h"
+#include "irprintf_t.h"
 
 #include "beutil.h"
 #include "belive_t.h"
 
+FIRM_IMPL2(is_live_in, int, const ir_node *, const ir_node *)
+FIRM_IMPL2(is_live_out, int, const ir_node *, const ir_node *)
+FIRM_IMPL2(is_live_end, int, const ir_node *, const ir_node *)
+
 /** The offset of the liveness information in a firm node. */
-size_t live_irn_data_offset = 0;
+size_t live_irg_data_offset = 0;
 
 void be_liveness_init(void)
 {
-	live_irn_data_offset = register_additional_node_data(sizeof(live_info_t));
+  live_irg_data_offset = register_additional_graph_data(sizeof(irn_live_t));
 }
 
-int (is_live_in)(const ir_node *block, const ir_node *irn)
-{
-	return _is_live_in(block, irn);
-}
-
-int (is_live_out)(const ir_node *block, const ir_node *irn)
+static INLINE void mark_live_in(ir_node *block, const ir_node *irn)
 {
-	return _is_live_in(block, irn);
+  _get_or_set_live(block, irn, live_state_in);
 }
 
-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)
 {
-	block_live_info_t *info = get_block_live_info(block);
-	pset_insert_ptr(info->in, irn);
+  _get_or_set_live(block, irn, live_state_out | live_state_end);
 }
 
-static INLINE void mark_live_out(ir_node *block, const ir_node *irn)
+static INLINE void mark_live_end(ir_node *block, const ir_node *irn)
 {
-	block_live_info_t *info = get_block_live_info(block);
-	pset_insert_ptr(info->out, irn);
+  _get_or_set_live(block, irn, live_state_end);
 }
 
 /**
@@ -48,27 +49,34 @@ static INLINE void mark_live_out(ir_node *block, const ir_node *irn)
  * @param def The node (value).
  * @param block The block to mark the value live out of.
  * @param visited A set were all visited blocks are recorded.
+ * @param is_true_out Is the node real out there or only live at the end
+ * of the block.
  */
-static void live_out_at_block(ir_node *def, ir_node *block, pset *visited)
+static void live_end_at_block(ir_node *def, ir_node *block,
+    pset *visited, int is_true_out)
 {
-	if(pset_find_ptr(visited, block))
-		return;
+  mark_live_end(block, def);
+  if(is_true_out)
+    mark_live_out(block, def);
 
-	pset_insert_ptr(visited, block);
-	mark_live_out(block, def);
+  if(!pset_find_ptr(visited, block)) {
 
-	/*
-	 * If this block is not the definition block, we have to go up
-	 * further.
-	 */
-	if(get_nodes_block(def) != block) {
-		int i, n;
+    pset_insert_ptr(visited, block);
 
-		mark_live_in(block, def);
+    /*
+     * If this block is not the definition block, we have to go up
+     * further.
+     */
+    if(get_nodes_block(def) != block) {
+      int i, n;
 
-		for(i = 0, n = get_irn_arity(block); i < n; ++i)
-			live_out_at_block(def, get_nodes_block(get_irn_n(block, i)), visited);
-	}
+      mark_live_in(block, def);
+
+      for(i = 0, n = get_irn_arity(block); i < n; ++i)
+        live_end_at_block(def, get_Block_cfgpred_block(block, i), visited, 1);
+    }
+
+  }
 }
 
 /**
@@ -80,102 +88,181 @@ static void live_out_at_block(ir_node *def, ir_node *block, pset *visited)
  */
 static void liveness_for_node(ir_node *irn, void *env)
 {
-	int i, n;
-	ir_node *def_block;
-	pset *visited;
-
-	/* Don't compute liveness information fornon-data nodes. */
-	if(!is_data_node(irn))
-		return;
-
-	visited = pset_new_ptr(512);
-	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);
-		ir_node *use_block;
-
-		/*
-		 * If the usage is no data node, skip this use, since it does not
-		 * affect the liveness of the node.
-		 */
-		if(!is_data_node(use))
-			continue;
-
-		/* Get the block where the usage is in. */
-		use_block = get_nodes_block(use);
-
-		/*
-		 * If the block of the definition equals the use block, we can skip
-		 * the following computations, since this use is local to a block.
-		 */
-		if(def_block == use_block)
-			continue;
-
-		/*
-		 * If the use is a phi function, determine the corresponding block
-		 * through which the value reaches the phi function and mark the
-		 * value as live out of that block.
-		 */
-		if(is_Phi(use)) {
-			int i, n;
-
-			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_out_at_block(irn, pred_block, visited);
-				}
-			}
-		}
+  const ir_edge_t *edge;
+  ir_node *def_block;
+  pset *visited;
+
+  /* Don't compute liveness information for non-data nodes. */
+  if(!is_data_node(irn))
+    return;
+
+  visited = pset_new_ptr(512);
+  def_block = get_nodes_block(irn);
+
+  /* Go over all uses of the value */
+  foreach_out_edge(irn, edge) {
+    ir_node *use = edge->src;
+    ir_node *use_block;
+
+    /*
+     * If the usage is no data node, skip this use, since it does not
+     * affect the liveness of the node.
+     */
+    if(!is_data_node(use))
+      continue;
+
+    /* Get the block where the usage is in. */
+    use_block = get_nodes_block(use);
+
+    /*
+     * If the use is a phi function, determine the corresponding block
+     * through which the value reaches the phi function and mark the
+     * value as live out of that block.
+     */
+    if(is_Phi(use)) {
+			ir_node *pred_block = get_Block_cfgpred_block(use_block, edge->pos);
+			live_end_at_block(irn, pred_block, visited, 0);
+    }
+
+    /*
+     * Else, the value is live in at this block. Mark it and call live
+     * out on the predecessors.
+     */
+    else if(def_block != use_block) {
+      int i, n;
+
+      mark_live_in(use_block, irn);
+
+      for(i = 0, n = get_irn_arity(use_block); i < n; ++i) {
+        ir_node *pred_block = get_nodes_block(get_irn_n(use_block, i));
+        live_end_at_block(irn, pred_block, visited, 1);
+      }
+    }
+  }
+
+  del_pset(visited);
+}
 
-		/*
-		 * Else, the value is live in at this block. Mark it and call live
-		 * out on the predecessors.
-		 */
-		else {
-			int i, n;
+static int cmp_irn_live(const void *a, const void *b, size_t size)
+{
+  const irn_live_t *p = a;
+  const irn_live_t *q = b;
+
+  return !(p->block == q->block && p->irn == q->irn);
+}
 
-			mark_live_in(use_block, irn);
+static int (*old_dump_block_func)(ir_node *self, FILE *F, dump_reason_t reason) = NULL;
 
-			for(i = 0, n = get_irn_arity(use_block); i < n; ++i) {
-				ir_node *pred_block = get_nodes_block(get_irn_n(use_block, i));
-				live_out_at_block(irn, pred_block, visited);
+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");
 			}
 		}
 	}
 
-	del_pset(visited);
+	return 0;
 }
 
-static void create_sets(ir_node *block, void *env)
+void be_liveness(ir_graph *irg)
 {
-	block_live_info_t *info = get_block_live_info(block);
+  irg_live_info_t *live_info = get_irg_live_info(irg);
+  if(live_info->live)
+    del_set(live_info->live);
 
-	info->in = pset_new_ptr(128);
-	info->out = pset_new_ptr(128);
+  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;
 }
 
-void be_liveness(ir_graph *irg)
+static void dump_liveness_walker(ir_node *bl, void *data)
 {
-	irg_block_walk_graph(irg, create_sets, NULL, NULL);
-	irg_walk_graph(irg, liveness_for_node, NULL, NULL);
+	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);
+}
 
-static void liveness_dump(ir_node *block, void *env)
+void be_liveness_dumpto(ir_graph *irg, const char *cls_name)
 {
-	FILE *f = env;
-	block_live_info_t *info = get_block_live_info(block);
+	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);
 
-	assert(is_Block(block) && "Need a block here");
+		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;
 
-	ir_fprintf(f, "liveness at block %n\n", block);
-	ir_fprintf(f, "\tlive  in: %*n\n", pset_iterator, info->in);
-	ir_fprintf(f, "\tlive out: %*n\n", pset_iterator, info->out);
+			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_liveness_dump(FILE *f, ir_graph *irg)
+void be_check_dominance(ir_graph *irg)
 {
-	irg_block_walk_graph(irg, liveness_dump, NULL, f);
+	irg_walk_graph(irg, dom_check, NULL, NULL);
 }