X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fcode_placement.c;h=6c0053189fc8d6aef75182188ea4a4bb5ae7bdce;hb=a619ce99e40de4eb4481a590970a881e9f24627a;hp=1e220e20ca256bece357db4946983b6038a5b63c;hpb=73a92a0b4183c187c230353782e1535b388e07a1;p=libfirm

diff --git a/ir/opt/code_placement.c b/ir/opt/code_placement.c
index 1e220e20c..6c0053189 100644
--- a/ir/opt/code_placement.c
+++ b/ir/opt/code_placement.c
@@ -25,22 +25,22 @@
  *           Michael Beck
  * @version  $Id$
  */
-#ifdef HAVE_CONFIG_H
-# include "config.h"
-#endif
+#include "config.h"
 
+#include "iroptimize.h"
 #include "adt/pdeq.h"
 #include "irnode_t.h"
 #include "irouts.h"
 #include "irgopt.h"
+#include "irpass.h"
 
 /**
  * Returns non-zero, is a block is not reachable from Start.
  *
  * @param block  the block to test
  */
-static int
-is_Block_unreachable(ir_node *block) {
+static int is_Block_unreachable(ir_node *block)
+{
 	return is_Block_dead(block) || get_Block_dom_depth(block) < 0;
 }
 
@@ -63,12 +63,12 @@ is_Block_unreachable(ir_node *block) {
  * @param n         the node to be placed
  * @param worklist  a worklist, predecessors of non-floating nodes are placed here
  */
-static void
-place_floats_early(ir_node *n, waitq *worklist) {
+static void place_floats_early(ir_node *n, waitq *worklist)
+{
 	int i, irn_arity;
 
 	/* we must not run into an infinite loop */
-	assert(irn_not_visited(n));
+	assert(!irn_visited(n));
 	mark_irn_visited(n);
 
 	/* Place floating nodes. */
@@ -92,14 +92,15 @@ place_floats_early(ir_node *n, waitq *worklist) {
 			ir_node *pred = get_irn_n(n, i);
 			ir_node *pred_block;
 
-			if ((irn_not_visited(pred))
+			if (!irn_visited(pred)
 			    && (get_irn_pinned(pred) == op_pin_state_floats)) {
 
 				/*
 				 * If the current node is NOT in a dead block, but one of its
-				 * predecessors is, we must move the predecessor to a live block.
-				 * Such thing can happen, if global CSE chose a node from a dead block.
-				 * We move it simply to our block.
+				 * predecessors is, we must move the predecessor to a live
+				 * block.
+				 * Such thing can happen, if global CSE chose a node from a
+				 * dead block. We move it simply to our block.
 				 * Note that neither Phi nor End nodes are floating, so we don't
 				 * need to handle them here.
 				 */
@@ -118,16 +119,18 @@ place_floats_early(ir_node *n, waitq *worklist) {
 			if (in_dead_block)
 				continue;
 
-			/* Because all loops contain at least one op_pin_state_pinned node, now all
-			   our inputs are either op_pin_state_pinned or place_early() has already
-			   been finished on them.  We do not have any unfinished inputs!  */
+			/* Because all loops contain at least one op_pin_state_pinned node,
+			   now all our inputs are either op_pin_state_pinned or
+			   place_early() has already been finished on them.
+			   We do not have any unfinished inputs! */
 			pred_block = get_nodes_block(pred);
 			if ((!is_Block_dead(pred_block)) &&
 				(get_Block_dom_depth(pred_block) > depth)) {
 				b = pred_block;
 				depth = get_Block_dom_depth(pred_block);
 			}
-			/* Avoid that the node is placed in the Start block */
+			/* Avoid that the node is placed in the Start block if we are not
+			   in the backend phase. */
 			if (depth == 1 &&
 					get_Block_dom_depth(get_nodes_block(n)) > 1 &&
 					get_irg_phase_state(current_ir_graph) != phase_backend) {
@@ -142,7 +145,8 @@ place_floats_early(ir_node *n, waitq *worklist) {
 
 	/*
 	 * Add predecessors of non floating nodes and non-floating predecessors
-	 * of floating nodes to worklist and fix their blocks if the are in dead block.
+	 * of floating nodes to worklist and fix their blocks if the are in dead
+	 * block.
 	 */
 	irn_arity = get_irn_arity(n);
 
@@ -153,7 +157,7 @@ place_floats_early(ir_node *n, waitq *worklist) {
 		 */
 		for (i = -1; i < irn_arity; ++i) {
 			ir_node *pred = get_irn_n(n, i);
-			if (irn_not_visited(pred))
+			if (!irn_visited(pred))
 				waitq_put(worklist, pred);
 		}
 	} else if (is_Block(n)) {
@@ -163,7 +167,7 @@ place_floats_early(ir_node *n, waitq *worklist) {
 		 */
 		for (i = irn_arity - 1; i >= 0; --i) {
 			ir_node *pred = get_irn_n(n, i);
-			if (irn_not_visited(pred))
+			if (!irn_visited(pred))
 				waitq_put(worklist, pred);
 		}
 	} else if (is_Phi(n)) {
@@ -176,13 +180,13 @@ place_floats_early(ir_node *n, waitq *worklist) {
 		 * of the Phi-input if the Phi is not in a bad block.
 		 */
 		pred = get_nodes_block(n);
-		if (irn_not_visited(pred))
+		if (!irn_visited(pred))
 			waitq_put(worklist, pred);
 
 		for (i = irn_arity - 1; i >= 0; --i) {
 			ir_node *pred = get_irn_n(n, i);
 
-			if (irn_not_visited(pred)) {
+			if (!irn_visited(pred)) {
 				if (! in_dead_block &&
 					get_irn_pinned(pred) == op_pin_state_floats &&
 					is_Block_unreachable(get_nodes_block(pred))) {
@@ -200,13 +204,13 @@ place_floats_early(ir_node *n, waitq *worklist) {
 		 * All other nodes: move nodes from dead blocks into the same block.
 		 */
 		pred = get_nodes_block(n);
-		if (irn_not_visited(pred))
+		if (!irn_visited(pred))
 			waitq_put(worklist, pred);
 
 		for (i = irn_arity - 1; i >= 0; --i) {
 			ir_node *pred = get_irn_n(n, i);
 
-			if (irn_not_visited(pred)) {
+			if (!irn_visited(pred)) {
 				if (! in_dead_block &&
 					get_irn_pinned(pred) == op_pin_state_floats &&
 					is_Block_unreachable(get_nodes_block(pred))) {
@@ -220,13 +224,15 @@ place_floats_early(ir_node *n, waitq *worklist) {
 
 /**
  * Floating nodes form subgraphs that begin at nodes as Const, Load,
- * Start, Call and that end at op_pin_state_pinned nodes as Store, Call.  Place_early
- * places all floating nodes reachable from its argument through floating
- * nodes and adds all beginnings at op_pin_state_pinned nodes to the worklist.
+ * Start, Call and that end at op_pin_state_pinned nodes as Store, Call.
+ * Place_early places all floating nodes reachable from its argument through
+ * floating nodes and adds all beginnings at op_pin_state_pinned nodes to the
+ * worklist.
  *
  * @param worklist   a worklist, used for the algorithm, empty on in/output
  */
-static void place_early(waitq *worklist) {
+static void place_early(waitq *worklist)
+{
 	assert(worklist);
 	inc_irg_visited(current_ir_graph);
 
@@ -236,19 +242,24 @@ static void place_early(waitq *worklist) {
 	/* Work the content of the worklist. */
 	while (!waitq_empty(worklist)) {
 		ir_node *n = waitq_get(worklist);
-		if (irn_not_visited(n))
+		if (!irn_visited(n))
 			place_floats_early(n, worklist);
 	}
-
-	set_irg_outs_inconsistent(current_ir_graph);
 	set_irg_pinned(current_ir_graph, op_pin_state_pinned);
 }
 
 /**
- * Compute the deepest common ancestor of block and dca.
+ * Compute the deepest common dominator tree ancestor of block and dca.
+ *
+ * @param dca    the deepest common dominator tree ancestor so far,
+ *               might be NULL
+ * @param block  a block
+ *
+ * @return  the deepest common dominator tree ancestor of block and dca
  */
-static ir_node *calc_dca(ir_node *dca, ir_node *block) {
-	assert(block);
+static ir_node *calc_dom_dca(ir_node *dca, ir_node *block)
+{
+	assert(block != NULL);
 
 	/* we do not want to place nodes in dead blocks */
 	if (is_Block_dead(block))
@@ -268,11 +279,11 @@ static ir_node *calc_dca(ir_node *dca, ir_node *block) {
 	while (block != dca) {
 		block = get_Block_idom(block); dca = get_Block_idom(dca);
 	}
-
 	return dca;
 }
 
-/** Deepest common dominance ancestor of DCA and CONSUMER of PRODUCER.
+/**
+ * Deepest common dominance ancestor of DCA and CONSUMER of PRODUCER.
  * I.e., DCA is the block where we might place PRODUCER.
  * A data flow edge points from producer to consumer.
  */
@@ -292,20 +303,18 @@ static ir_node *consumer_dom_dca(ir_node *dca, ir_node *consumer, ir_node *produ
 				ir_node *new_block = get_Block_cfgpred_block(phi_block, i);
 
 				if (!is_Block_unreachable(new_block))
-					dca = calc_dca(dca, new_block);
+					dca = calc_dom_dca(dca, new_block);
 			}
 		}
 	} else {
-		dca = calc_dca(dca, get_nodes_block(consumer));
+		dca = calc_dom_dca(dca, get_nodes_block(consumer));
 	}
-
 	return dca;
 }
 
-/* FIXME: the name clashes here with the function from ana/field_temperature.c
- * please rename. */
-static INLINE int get_irn_loop_depth(ir_node *n) {
-	return get_loop_depth(get_irn_loop(n));
+static inline int get_block_loop_depth(ir_node *block)
+{
+	return get_loop_depth(get_irn_loop(block));
 }
 
 /**
@@ -315,7 +324,8 @@ static INLINE int get_irn_loop_depth(ir_node *n) {
  * @param n      the node that should be moved
  * @param early  the earliest block we can n move to
  */
-static void move_out_of_loops(ir_node *n, ir_node *early) {
+static void move_out_of_loops(ir_node *n, ir_node *early)
+{
 	ir_node *best, *dca;
 	assert(n && early);
 
@@ -329,24 +339,25 @@ static void move_out_of_loops(ir_node *n, ir_node *early) {
 	while (dca != early) {
 		dca = get_Block_idom(dca);
 		if (!dca || is_Bad(dca)) break; /* may be Bad if not reachable from Start */
-		if (get_irn_loop_depth(dca) < get_irn_loop_depth(best)) {
+		if (get_block_loop_depth(dca) < get_block_loop_depth(best)) {
 			best = dca;
 		}
 	}
-	if (best != get_nodes_block(n)) {
-		/* debug output
-		printf("Moving out of loop: "); DDMN(n);
-		printf(" Outermost block: "); DDMN(early);
-		printf(" Best block: "); DDMN(best);
-		printf(" Innermost block: "); DDMN(get_nodes_block(n));
-		*/
+	if (best != get_nodes_block(n))
 		set_nodes_block(n, best);
-	}
 }
 
-/* deepest common ancestor in the dominator tree of all nodes'
-   blocks depending on us; our final placement has to dominate DCA. */
-static ir_node *get_deepest_common_ancestor(ir_node *node, ir_node *dca)
+/**
+ * Calculate the deepest common ancestor in the dominator tree of all nodes'
+ * blocks depending on node; our final placement has to dominate DCA.
+ *
+ * @param node  the definition node
+ * @param dca   the deepest common ancestor block so far, initially
+ *              NULL
+ *
+ * @return the deepest common dominator ancestor of all blocks of node's users
+ */
+static ir_node *get_deepest_common_dom_ancestor(ir_node *node, ir_node *dca)
 {
 	int i;
 
@@ -362,7 +373,9 @@ static ir_node *get_deepest_common_ancestor(ir_node *node, ir_node *dca)
 		}
 
 		if (is_Proj(succ)) {
-			dca = get_deepest_common_ancestor(succ, dca);
+			/* Proj nodes are in the same block as node, so
+			 * the users of Proj are our users. */
+			dca = get_deepest_common_dom_ancestor(succ, dca);
 		} else {
 			/* ignore if succ is in dead code */
 			ir_node *succ_blk = get_nodes_block(succ);
@@ -371,7 +384,6 @@ static ir_node *get_deepest_common_ancestor(ir_node *node, ir_node *dca)
 			dca = consumer_dom_dca(dca, succ, node);
 		}
 	}
-
 	return dca;
 }
 
@@ -381,7 +393,8 @@ static ir_node *get_deepest_common_ancestor(ir_node *node, ir_node *dca)
  * @param node   the mode_T node
  * @param block  the block to put the Proj nodes to
  */
-static void set_projs_block(ir_node *node, ir_node *block) {
+static void set_projs_block(ir_node *node, ir_node *block)
+{
 	int i;
 
 	for (i = get_irn_n_outs(node) - 1; i >= 0; --i) {
@@ -408,11 +421,12 @@ static void set_projs_block(ir_node *node, ir_node *block) {
  * @param worklist  a worklist, all successors of non-floating nodes are
  *                  placed here
  */
-static void place_floats_late(ir_node *n, pdeq *worklist) {
+static void place_floats_late(ir_node *n, pdeq *worklist)
+{
 	int i, n_outs;
 	ir_node *early_blk;
 
-	assert(irn_not_visited(n)); /* no multiple placement */
+	assert(!irn_visited(n)); /* no multiple placement */
 
 	mark_irn_visited(n);
 
@@ -440,7 +454,7 @@ static void place_floats_late(ir_node *n, pdeq *worklist) {
 		    producer of one of their inputs in the same block anyway. */
 		for (i = get_irn_n_outs(n) - 1; i >= 0; --i) {
 			ir_node *succ = get_irn_out(n, i);
-			if (irn_not_visited(succ) && !is_Phi(succ))
+			if (!irn_visited(succ) && !is_Phi(succ))
 				place_floats_late(succ, worklist);
 		}
 
@@ -458,7 +472,7 @@ static void place_floats_late(ir_node *n, pdeq *worklist) {
 				/* deepest common ancestor in the dominator tree of all nodes'
 				   blocks depending on us; our final placement has to dominate
 				   DCA. */
-				ir_node *dca = get_deepest_common_ancestor(n, NULL);
+				ir_node *dca = get_deepest_common_dom_ancestor(n, NULL);
 				if (dca != NULL) {
 					set_nodes_block(n, dca);
 					move_out_of_loops(n, early_blk);
@@ -475,7 +489,7 @@ static void place_floats_late(ir_node *n, pdeq *worklist) {
 	n_outs = get_irn_n_outs(n);
 	for (i = 0; i < n_outs; i++) {
 		ir_node *succ = get_irn_out(n, i);
-		if (irn_not_visited(succ)) {
+		if (!irn_visited(succ)) {
 			pdeq_putr(worklist, succ);
 		}
 	}
@@ -487,7 +501,8 @@ static void place_floats_late(ir_node *n, pdeq *worklist) {
  *
  * @param worklist   the worklist containing the nodes to place
  */
-static void place_late(waitq *worklist) {
+static void place_late(waitq *worklist)
+{
 	assert(worklist);
 	inc_irg_visited(current_ir_graph);
 
@@ -497,20 +512,23 @@ static void place_late(waitq *worklist) {
 	/* And now empty the worklist again... */
 	while (!waitq_empty(worklist)) {
 		ir_node *n = waitq_get(worklist);
-		if (irn_not_visited(n))
+		if (!irn_visited(n))
 			place_floats_late(n, worklist);
 	}
 }
 
 /* Code Placement. */
-void place_code(ir_graph *irg) {
+void place_code(ir_graph *irg)
+{
 	waitq *worklist;
 	ir_graph *rem = current_ir_graph;
 
 	current_ir_graph = irg;
+	remove_critical_cf_edges(irg);
 
 	/* Handle graph state */
 	assert(get_irg_phase_state(irg) != phase_building);
+	assure_irg_outs(irg);
 	assure_doms(irg);
 
 	if (1 || get_irg_loopinfo_state(irg) != loopinfo_consistent) {
@@ -535,3 +553,19 @@ void place_code(ir_graph *irg) {
 	del_waitq(worklist);
 	current_ir_graph = rem;
 }
+
+/**
+ * Wrapper for place_code() inside the place_code pass.
+ */
+static void place_code_wrapper(ir_graph *irg)
+{
+	set_opt_global_cse(1);
+	optimize_graph_df(irg);
+	place_code(irg);
+	set_opt_global_cse(0);
+}
+
+ir_graph_pass_t *place_code_pass(const char *name)
+{
+	return def_graph_pass(name ? name : "place", place_code_wrapper);
+}