X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fcfopt.c;h=765f57eba2af0a07edbfaa7b5b56de8d27bf3825;hb=b27ae245166bb695bc4e418ff416d91bc37d0f28;hp=d65e46e651a957700e418905edbeea9d23f21462;hpb=14b28714b5bb4bae1cf3b46aa7978ccf8e67d293;p=libfirm

diff --git a/ir/opt/cfopt.c b/ir/opt/cfopt.c
index d65e46e65..765f57eba 100644
--- a/ir/opt/cfopt.c
+++ b/ir/opt/cfopt.c
@@ -56,6 +56,7 @@
 #include "irflag_t.h"
 #include "firmstat.h"
 #include "irpass.h"
+#include "irphase_t.h"
 
 #include "iropt_dbg.h"
 
@@ -63,7 +64,6 @@
 typedef struct merge_env {
 	bool      changed;      /**< Set if the graph was changed. */
 	bool      phis_moved;   /**< Set if Phi nodes were moved. */
-	ir_node **switch_conds; /**< Helper list for all found Switch Conds. */
 } merge_env;
 
 static void set_Block_removable(ir_node *block, bool removable)
@@ -76,6 +76,11 @@ static bool is_Block_removable(ir_node *block)
 	return get_Block_mark(block);
 }
 
+static bool is_switch_Cond(ir_node *cond) {
+	ir_node *sel = get_Cond_selector(cond);
+	return get_irn_mode(sel) != mode_b;
+}
+
 static void clear_link(ir_node *node, void *ctx)
 {
 	(void) ctx;
@@ -93,7 +98,7 @@ static void clear_link(ir_node *node, void *ctx)
  */
 static void collect_nodes(ir_node *n, void *ctx)
 {
-	merge_env *env = (merge_env*)ctx;
+	ir_node ***switch_conds = (ir_node***)ctx;
 
 	if (is_Phi(n)) {
 		/* Collect Phi nodes to compact ins along with block's ins. */
@@ -113,12 +118,9 @@ static void collect_nodes(ir_node *n, void *ctx)
 			ir_node *pred = get_Proj_pred(n);
 			set_irn_link(n, get_irn_link(pred));
 			set_irn_link(pred, n);
-		} else if (is_Cond(n)) {
-			ir_node *sel = get_Cond_selector(n);
-			if (get_irn_mode(sel) != mode_b) {
-				/* found a switch-Cond, collect */
-				ARR_APP1(ir_node*, env->switch_conds, n);
-			}
+		} else if (is_Cond(n) && is_switch_Cond(n)) {
+			/* found a switch-Cond, collect */
+			ARR_APP1(ir_node*, *switch_conds, n);
 		}
 	}
 }
@@ -222,8 +224,8 @@ non_dispensable:
 }
 
 /**
- * This method removed Bad cf predecessors from Blocks and Phis, and removes
- * empty blocks.  A block is empty if it only contains Phi and Jmp nodes.
+ * This method removes empty blocks.  A block is empty if it only contains Phi
+ * and Jmp nodes.
  *
  * We first adapt Phi nodes, then Block nodes, as we need the old ins
  * of the Block to adapt the Phi nodes.  We do this by computing new
@@ -371,7 +373,7 @@ static void optimize_blocks(ir_node *b, void *ctx)
 						pred = get_Block_cfgpred_block(b, i);
 
 						if (is_Bad(pred)) {
-							/* Do nothing */
+							in[q_preds++] = pred;
 						} else if (is_Block_removable(pred) && !Block_block_visited(pred)) {
 							/* It's an empty block and not yet visited. */
 							for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
@@ -386,8 +388,7 @@ static void optimize_blocks(ir_node *b, void *ctx)
 					/* now we are at k, copy the phi predecessors */
 					pred = get_nodes_block(get_Block_cfgpred(b, k));
 					for (i = 0; i < get_Phi_n_preds(phi); i++) {
-						if (! is_Bad(get_Block_cfgpred(pred, i)))
-							in[q_preds++] = get_Phi_pred(phi, i);
+						in[q_preds++] = get_Phi_pred(phi, i);
 					}
 
 					/* and now all the rest */
@@ -395,7 +396,9 @@ static void optimize_blocks(ir_node *b, void *ctx)
 						pred = get_Block_cfgpred_block(b, i);
 
 						if (is_Bad(pred)) {
-							/* Do nothing */
+							ir_graph *irg  = get_irn_irg(b);
+							ir_mode  *mode = get_irn_mode(phi);
+							in[q_preds++] = new_r_Bad(irg, mode);
 						} else if (is_Block_removable(pred) && !Block_block_visited(pred)) {
 							/* It's an empty block and not yet visited. */
 							for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
@@ -428,7 +431,7 @@ static void optimize_blocks(ir_node *b, void *ctx)
 		ir_node *predb = get_nodes_block(pred);
 		ir_graph *irg  = get_irn_irg(pred);
 
-		/* case 1: Do nothing */
+		/* case 1: Bad predecessor */
 		if (is_Bad(pred)) {
 			in[n_preds++] = new_r_Bad(irg, mode_X);
 			continue;
@@ -463,21 +466,6 @@ static void optimize_blocks(ir_node *b, void *ctx)
 	xfree(in);
 }
 
-/**
- * Block walker: optimize all blocks using the default optimizations.
- * This removes Blocks with only a Jmp predecessor.
- */
-static void remove_simple_blocks(ir_node *block, void *ctx)
-{
-	merge_env *env = (merge_env*)ctx;
-	ir_node   *new_blk = equivalent_node(block);
-
-	if (new_blk != block) {
-		exchange(block, new_blk);
-		env->changed = true;
-	}
-}
-
 /**
  * Optimize table-switch Conds.
  *
@@ -549,21 +537,172 @@ static bool handle_switch_cond(ir_node *cond)
 	return false;
 }
 
-/* Optimizations of the control flow that also require changes of Phi nodes.
- *
- * This optimization performs two passes over the graph.
- *
- * The first pass collects all Phi nodes in a link list in the block
- * nodes.  Further it performs simple control flow optimizations.
- * Finally it marks all blocks that do not contain useful
- * computations, i.e., these blocks might be removed.
- *
- * The second pass performs the optimizations intended by this algorithm.
- * It walks only over block nodes and adapts these and the Phi nodes in these
- * blocks, which it finds in a linked list computed by the first pass.
+static bool get_phase_flag(ir_phase *block_info, ir_node *block, int offset) {
+	return ((int)phase_get_irn_data(block_info, block)) & (1<<offset);
+}
+static void set_phase_flag(ir_phase *block_info, ir_node *block, int offset) {
+	int data = (int)phase_get_irn_data(block_info, block);
+	data |= (1<<offset);
+	phase_set_irn_data(block_info, block, (void*)data);
+}
+
+static bool has_operations(ir_phase *block_info, ir_node *block) {
+	return get_phase_flag(block_info, block, 1);
+}
+static void set_has_operations(ir_phase *block_info, ir_node *block) {
+	set_phase_flag(block_info, block, 1);
+}
+
+static bool has_phis(ir_phase *block_info, ir_node *block) {
+	return get_phase_flag(block_info, block, 2);
+}
+static void set_has_phis(ir_phase *block_info, ir_node *block) {
+	set_phase_flag(block_info, block, 2);
+}
+
+static bool is_unknown_jump_target(ir_phase *block_info, ir_node *block) {
+	return get_phase_flag(block_info, block, 3);
+}
+static void set_is_unknown_jump_target(ir_phase *block_info, ir_node *block) {
+	set_phase_flag(block_info, block, 3);
+}
+
+/**
+ * Optimize Conds, where true and false jump to the same block into a Jmp
  *
- * We use the mark flag to mark removable blocks in the first phase.
+ *        Cond
+ *       /    \
+ *  projA      projB   =>   Jmp     Bad
+ *       \    /                \   /
+ *       block                 block
  */
+static bool optimize_pred_cond(ir_node *block, int i, int j)
+{
+	ir_node *projA, *projB, *cond, *pred_block, *jmp, *bad;
+	assert(i != j);
+
+	projA = get_Block_cfgpred(block, i);
+	if (!is_Proj(projA)) return false;
+	projB = get_Block_cfgpred(block, j);
+	if (!is_Proj(projB)) return false;
+	cond  = get_Proj_pred(projA);
+	if (!is_Cond(cond))  return false;
+
+	if (cond != get_Proj_pred(projB)) return false;
+	if (is_switch_Cond(cond)) return false;
+
+	/* cond should actually be a Jmp */
+	pred_block = get_nodes_block(cond);
+	jmp = new_r_Jmp(pred_block);
+	bad = new_r_Bad(get_irn_irg(block), mode_X);
+
+	assert(projA != projB);
+	exchange(projA, jmp);
+	exchange(projB, bad);
+	return true;
+}
+
+static void compute_block_info(ir_node *n, void *x)
+{
+	ir_phase *block_info = (ir_phase *)x;
+
+	if (is_Block(n)) {
+		int i, max = get_Block_n_cfgpreds(n);
+		for (i=0; i<max; i++) {
+			ir_node *pred = get_Block_cfgpred(n,i);
+			if (is_unknown_jump(pred)) {
+				set_is_unknown_jump_target(block_info, n);
+			}
+		}
+	} else if (is_Phi(n)) {
+		ir_node *block = get_nodes_block(n);
+		set_has_phis(block_info, block);
+	} else if (is_Jmp(n) || is_Cond(n) || is_Cmp(n) || is_Proj(n)) {
+		/* ignore */
+	} else {
+		ir_node *block = get_nodes_block(n);
+		set_has_operations(block_info, block);
+	}
+}
+
+typedef struct skip_env {
+	bool changed;
+	ir_phase *phase;
+} skip_env;
+
+static void optimize_conds(ir_node *b, void *x)
+{
+	skip_env *env = (skip_env*)x;
+	int i, j;
+	int n_preds = get_Block_n_cfgpreds(b);
+
+	if (has_phis(env->phase,b)) return;
+
+	/* optimize Cond predecessors (might produce Bad predecessors) */
+	for (i = 0; i < n_preds; i++) {
+		for (j = i+1; j < n_preds; j++) {
+			optimize_pred_cond(b, i, j);
+		}
+	}
+}
+
+static void remove_empty_blocks(ir_node *b, void *x)
+{
+	skip_env *env = (skip_env*)x;
+	int i;
+	int n_preds = get_Block_n_cfgpreds(b);
+
+	for (i = 0; i < n_preds; ++i) {
+		ir_node *jmp, *jmp_block, *pred, *pred_block;
+
+		jmp = get_Block_cfgpred(b, i);
+		if (!is_Jmp(jmp)) continue;
+		if (is_unknown_jump(jmp)) continue;
+		jmp_block = get_nodes_block(jmp);
+		if (is_unknown_jump_target(env->phase, jmp_block)) continue;
+		if (has_operations(env->phase,jmp_block)) continue;
+		/* jmp_block is an empty block! */
+
+		if (get_Block_n_cfgpreds(jmp_block) != 1) continue;
+		pred = get_Block_cfgpred(jmp_block, 0);
+		exchange(jmp, pred);
+		env->changed = true;
+
+		/* cleanup: jmp_block might have a Keep edge! */
+		pred_block = get_nodes_block(pred);
+		exchange(jmp_block, pred_block);
+	}
+}
+
+/*
+ * Some cfg optimizations, which do not touch Phi nodes */
+static void cfgopt_ignoring_phis(ir_graph *irg) {
+	ir_phase *block_info = new_phase(irg, NULL);
+	skip_env env = { false, block_info };
+
+	irg_walk_graph(irg, compute_block_info, NULL, block_info);
+
+	for(;;) {
+		env.changed = false;
+
+		/* Conds => Jmp optimization; might produce empty blocks */
+		irg_block_walk_graph(irg, optimize_conds, NULL, &env);
+
+		/* Remove empty blocks */
+		irg_block_walk_graph(irg, remove_empty_blocks, NULL, &env);
+		if (env.changed) {
+			set_irg_doms_inconsistent(irg);
+			/* Removing blocks might enable more Cond optimizations */
+			continue;
+		} else {
+			break;
+		}
+	}
+
+	phase_free(block_info);
+}
+
+/* Optimizations of the control flow that also require changes of Phi nodes.  */
 void optimize_cf(ir_graph *irg)
 {
 	int i, j, n;
@@ -582,41 +721,55 @@ void optimize_cf(ir_graph *irg)
 	 * here. Fix the edges! */
 	edges_deactivate(irg);
 
+	cfgopt_ignoring_phis(irg);
+
 	/* we use the mark flag to mark removable blocks */
 	ir_reserve_resources(irg, IR_RESOURCE_BLOCK_MARK | IR_RESOURCE_IRN_LINK);
-restart:
-	env.changed    = false;
-	env.phis_moved = false;
 
-	assure_doms(irg);
+	/* The switch Cond optimization might expose unreachable code, so we loop */
+	for (;;) {
+		int length;
+		ir_node **switch_conds = NULL;
+		env.changed    = false;
+		env.phis_moved = false;
 
-	env.switch_conds = NEW_ARR_F(ir_node*, 0);
-	irg_walk(end, clear_link, collect_nodes, &env);
+		assure_doms(irg);
 
-	/* handle all collected switch-Conds */
-	n = ARR_LEN(env.switch_conds);
-	for (i = 0; i < n; ++i) {
-		ir_node *cond = env.switch_conds[i];
-		env.changed |= handle_switch_cond(cond);
-	}
-	DEL_ARR_F(env.switch_conds);
+		/*
+		 * This pass collects all Phi nodes in a link list in the block
+		 * nodes.  Further it performs simple control flow optimizations.
+		 * Finally it marks all blocks that do not contain useful
+		 * computations, i.e., these blocks might be removed.
+		 */
+		switch_conds = NEW_ARR_F(ir_node*, 0);
+		irg_walk(end, clear_link, collect_nodes, &switch_conds);
+
+		/* handle all collected switch-Conds */
+		length = ARR_LEN(switch_conds);
+		for (i = 0; i < length; ++i) {
+			ir_node *cond = switch_conds[i];
+			env.changed |= handle_switch_cond(cond);
+		}
+		DEL_ARR_F(switch_conds);
+
+		if (!env.changed) break;
 
-	if (env.changed) {
-		/* Handle graph state if was changed. */
-		set_irg_outs_inconsistent(irg);
 		set_irg_doms_inconsistent(irg);
 		set_irg_extblk_inconsistent(irg);
-		set_irg_loopinfo_inconsistent(irg);
 		set_irg_entity_usage_state(irg, ir_entity_usage_not_computed);
-
-		/* The Cond optimization might generate unreachable code, so restart if
-		   it happens. */
-		goto restart;
 	}
 
-	/* Optimize the standard code. */
+	/* assert due to collect_nodes:
+	 * 1. removable blocks are now marked as such
+	 * 2. phi lists are up to date
+	 */
+
+	/* Optimize the standard code.
+	 * It walks only over block nodes and adapts these and the Phi nodes in these
+	 * blocks, which it finds in a linked list computed before.
+	 * */
 	assure_doms(irg);
-	irg_block_walk_graph(irg, optimize_blocks, remove_simple_blocks, &env);
+	irg_block_walk_graph(irg, optimize_blocks, NULL, &env);
 
 	new_end = optimize_in_place(end);
 	if (new_end != end) {
@@ -635,10 +788,6 @@ restart:
 		n = get_End_n_keepalives(end);
 		if (n > 0) {
 			NEW_ARR_A(ir_node *, in, n);
-			if (env.changed) {
-				/* Handle graph state if was changed. */
-				set_irg_outs_inconsistent(irg);
-			}
 			assure_irg_outs(irg);
 
 			for (i = j = 0; i < n; ++i) {
@@ -669,10 +818,8 @@ restart:
 
 	if (env.changed) {
 		/* Handle graph state if was changed. */
-		set_irg_outs_inconsistent(irg);
 		set_irg_doms_inconsistent(irg);
 		set_irg_extblk_inconsistent(irg);
-		set_irg_loopinfo_inconsistent(irg);
 		set_irg_entity_usage_state(irg, ir_entity_usage_not_computed);
 	}
 }