X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fir%2Firedges.c;h=1a2ee723e24bcaf0c20d99e8a5e560be154deeb0;hb=b78bdd4d94de46de4156272e6dbfe44e97933a5b;hp=0702244ea57dd2bd79870455068f02636b1607ca;hpb=0ba5c335437890db96a18c1a1b780d39c10bebf9;p=libfirm

diff --git a/ir/ir/iredges.c b/ir/ir/iredges.c
index 0702244ea..1a2ee723e 100644
--- a/ir/ir/iredges.c
+++ b/ir/ir/iredges.c
@@ -1,3 +1,15 @@
+/*
+ * Project:     libFIRM
+ * File name:   ir/ir/iredges.c
+ * Purpose:     Always available outs.
+ * Author:      Sebastian Hack
+ * Modified by: Michael Beck
+ * Created:     14.1.2005
+ * CVS-ID:      $Id$
+ * Copyright:   (c) 1998-2006 Universität Karlsruhe
+ * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
+ */
+
 /**
  * Always available outs.
  * @author Sebastian Hack
@@ -16,6 +28,7 @@
 #endif
 
 #include "irnode_t.h"
+#include "iropt_t.h"
 #include "iredges_t.h"
 #include "irgwalk.h"
 #include "irdump_t.h"
@@ -26,8 +39,6 @@
 
 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
 
-#if FIRM_EDGES_INPLACE
-
 /**
  * This flag is set to 1, if the edges get initialized for an irg.
  * Then register additional data is forbidden.
@@ -63,7 +74,7 @@ static int edge_cmp(const void *p1, const void *p2, size_t len)
 
 /**
  * Initialize the out information for a graph.
- * @note Dead node elim can call this on an already initialized graph.
+ * @note Dead node elimination can call this on an already initialized graph.
  */
 void edges_init_graph(ir_graph *irg)
 {
@@ -231,6 +242,7 @@ void edges_notify_edge(ir_node *src, int pos, ir_node *tgt, ir_node *old_tgt, ir
 			/* If the old target is not null, the edge is moved. */
 			if(old_tgt) {
 				msg = "redirecting";
+
 				list_move(&edge->list, head);
 
 				/* If the edge is a cf edge, move it from the successor list. */
@@ -258,8 +270,8 @@ void edges_notify_edge(ir_node *src, int pos, ir_node *tgt, ir_node *old_tgt, ir
 	}
 
 	/* If the target and the old target are equal, nothing is done. */
-	DBG((dbg, LEVEL_5, "announce out edge: %n[%p] %d-> %n[%p](%n[%p]): %s\n",
-				src, src, pos, tgt, tgt, old_tgt, old_tgt, msg));
+	DBG((dbg, LEVEL_5, "announce out edge: %+F %d-> %+F(%+F): %s\n",
+				src, pos, tgt, old_tgt, msg));
 }
 
 void edges_node_deleted(ir_node *old, ir_graph *irg)
@@ -268,33 +280,31 @@ void edges_node_deleted(ir_node *old, ir_graph *irg)
 		int not_a_block = !is_Block(old);
 		int i, n;
 
-		DBG((dbg, LEVEL_5, "node deleted: %n\n", old));
+		DBG((dbg, LEVEL_5, "node deleted: %+F\n", old));
 
 		/* Change to get_irn_n */
 		for(i = -not_a_block, n = get_irn_arity(old); i < n; ++i) {
 			ir_node *old_tgt = get_irn_n(old, i);
-			DBG((dbg, LEVEL_5, "\tdelete to old target %n\n", old_tgt));
+			DBG((dbg, LEVEL_5, "\tdelete to old target %+F\n", old_tgt));
 			edges_notify_edge(old, i, NULL, old_tgt, irg);
 		}
 
 	}
 }
 
-void edges_invalidate(ir_node *irn, ir_graph *irg)
-{
+void edges_invalidate(ir_node *irn, ir_graph *irg) {
 	edges_node_deleted(irn, irg);
 }
 
 /**
  * Post-Walker: notify all edges
  */
-static void build_edges_walker(ir_node *irn, void *data)
-{
+static void build_edges_walker(ir_node *irn, void *data) {
 	ir_graph *irg = data;
 	int not_a_block = !is_Block(irn);
 	int i, n;
 
-	for(i = -not_a_block, n = get_irn_arity(irn); i < n; ++i)
+	for (i = -not_a_block, n = get_irn_arity(irn); i < n; ++i)
 		edges_notify_edge(irn, i, get_irn_n(irn, i), NULL, irg);
 }
 
@@ -302,14 +312,46 @@ static void build_edges_walker(ir_node *irn, void *data)
  * Pre-Walker: initializes the list-heads and set the out-count
  * of all nodes to 0.
  */
-static void init_lh_walker(ir_node *irn, void *data)
-{
+static void init_lh_walker(ir_node *irn, void *data) {
 	INIT_LIST_HEAD(_get_irn_outs_head(irn));
-	if(is_Block(irn))
+	if (is_Block(irn))
 		INIT_LIST_HEAD(_get_block_succ_head(irn));
 	_get_irn_edge_info(irn)->out_count = 0;
 }
 
+/**
+ * Visitor: initializes the list-heads and set the out-count
+ * of all nodes to 0 of nodes that are not seen so far.
+ */
+static void visitor(ir_node *irn, void *data) {
+	if (irn_not_visited(irn)) {
+		mark_irn_visited(irn);
+		init_lh_walker(irn, data);
+	}
+}
+
+/*
+ * Build the initial edge set.
+ * Beware, this is not a simple task because it suffers from two
+ * difficulties:
+ * - the anchor set allows access to Nodes that may not be reachable from
+ *   the End node
+ * - the identities add nodes to the "root set" that are not yet reachable
+ *   from End. However, after some transformations, the CSE may revival these
+ *   nodes
+ *
+ * These problems can be fixed using different strategies:
+ * - Add an age flag to every node. Whenever the edge of a node is older
+ *   then the current edge, invalidate the edges of this node.
+ *   While this would help for revivaled nodes, it increases memory and runtime.
+ * - Delete the identities set.
+ *   Solves the revival problem, but may increase the memory consumption, as
+ *   nodes cannot be revivaled at all.
+ * - Manually iterate over the identities root set. This did not consume more memory
+ *   but increase the computation time because the |identies| >= |V|
+ *
+ * Currently, we use the last option.
+ */
 void edges_activate(ir_graph *irg)
 {
 	irg_edge_info_t *info = _get_irg_edge_info(irg);
@@ -317,6 +359,8 @@ void edges_activate(ir_graph *irg)
 	info->activated = 1;
 	edges_init_graph(irg);
 	irg_walk_graph(irg, init_lh_walker, build_edges_walker, irg);
+	irg_walk_anchors(irg, init_lh_walker, NULL, irg);
+	visit_all_identities(irg, visitor, irg);
 }
 
 void edges_deactivate(ir_graph *irg)
@@ -324,10 +368,10 @@ void edges_deactivate(ir_graph *irg)
 	irg_edge_info_t *info = _get_irg_edge_info(irg);
 
 	info->activated = 0;
-	if(info->edges) {
+	if (info->edges) {
 		del_set(info->edges);
-    info->edges = NULL;
-  }
+		info->edges = NULL;
+	}
 }
 
 int (edges_activated)(const ir_graph *irg)
@@ -348,7 +392,7 @@ void edges_reroute(ir_node *from, ir_node *to, ir_graph *irg)
 		struct list_head *head = _get_irn_outs_head(from);
 
 		DBG((dbg, LEVEL_5,
-					"reroute from %n to %n\n", from, to));
+					"reroute from %+F to %+F\n", from, to));
 
 		while(head != head->next) {
 			ir_edge_t *edge = list_entry(head->next, ir_edge_t, list);
@@ -379,7 +423,7 @@ static void verify_set_presence(ir_node *irn, void *data)
 		if(e != NULL)
 			e->present = 1;
 		else
-			DBG((dbg, LEVEL_DEFAULT, "edge %n,%d is missing\n", irn, templ->pos));
+			DBG((dbg, LEVEL_DEFAULT, "edge %+F,%d is missing\n", irn, templ->pos));
 	}
 }
 
@@ -390,7 +434,7 @@ static void verify_list_presence(ir_node *irn, void *data)
 	foreach_out_edge(irn, e) {
 		ir_node *tgt = get_irn_n(e->src, e->pos);
 		if(irn != tgt)
-			DBG((dbg, LEVEL_DEFAULT, "edge %n,%d is no out edge of %n but of %n\n",
+			DBG((dbg, LEVEL_DEFAULT, "edge %+F,%d is no out edge of %+F but of %+F\n",
 					e->src, e->pos, irn, tgt));
 	}
 
@@ -414,7 +458,7 @@ void edges_verify(ir_graph *irg)
 	 */
 	for(e = set_first(edges); e; e = set_next(edges)) {
 		if(!e->invalid && !e->present)
-			DBG((dbg, LEVEL_DEFAULT, "edge %n,%d is superfluous\n", e->src, e->pos));
+			DBG((dbg, LEVEL_DEFAULT, "edge %+F,%d is superfluous\n", e->src, e->pos));
 	}
 }
 
@@ -449,6 +493,3 @@ int (get_irn_n_edges)(const ir_node *irn)
 {
 	return _get_irn_n_edges(irn);
 }
-
-
-#endif /* FIRM_EDGES_INPLACE */