X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fifconv.c;h=84a93f7a435a62a393808bb3f73a5572a817ad0b;hb=43332529cf18bf9f2a0ecb384dc5dd0093eb3c8a;hp=63c70905311968229d53de9ef1372b9d4bf2e78a;hpb=0fbcef83aa6060534172bb13e71cdadb04428806;p=libfirm

diff --git a/ir/opt/ifconv.c b/ir/opt/ifconv.c
index 63c709053..84a93f7a4 100644
--- a/ir/opt/ifconv.c
+++ b/ir/opt/ifconv.c
@@ -27,32 +27,44 @@
 #include "config.h"
 
 #include <assert.h>
+#include <stdbool.h>
+
 #include "iroptimize.h"
 #include "obst.h"
 #include "irnode_t.h"
 #include "cdep.h"
 #include "ircons.h"
-#include "irdom.h"
 #include "irgmod.h"
 #include "irgopt.h"
 #include "irgwalk.h"
 #include "irtools.h"
 #include "array_t.h"
+#include "irpass_t.h"
 
 // debug
 #include "irdump.h"
 #include "debug.h"
 
+/**
+ * Environment for if-conversion.
+ */
+typedef struct walker_env {
+	const ir_settings_if_conv_t *params; /**< Conversion parameter. */
+	int                         changed; /**< Set if the graph was changed. */
+} walker_env;
+
 DEBUG_ONLY(static firm_dbg_module_t *dbg);
 
-/** allow every Mux to be created. */
-static int default_allow_ifconv(ir_node *sel, ir_node* phi_list, int i, int j)
+/**
+ * Default callback for Mux creation: don't allow any Mux nodes
+ */
+static int default_allow_ifconv(ir_node *sel, ir_node *mux_false,
+                                ir_node *mux_true)
 {
 	(void) sel;
-	(void) phi_list;
-	(void) i;
-	(void) j;
-	return 1;
+	(void) mux_false;
+	(void) mux_true;
+	return 0;
 }
 
 /**
@@ -65,12 +77,24 @@ static const ir_settings_if_conv_t default_info = {
 
 /**
  * Returns non-zero if a Block can be emptied.
+ *
+ * @param block  the block
  */
-static int can_empty_block(ir_node *block) {
+static bool can_empty_block(ir_node *block)
+{
 	return get_Block_mark(block) == 0;
 }
 
-
+/**
+ * Find the ProjX node leading from block dependency to block start.
+ *
+ * @param start       a block that is control depended on dependency
+ * @param dependency  the block that decides whether start is executed
+ *
+ * @return a ProjX node that represent the decision control flow or
+ *         NULL is start is not dependent at all or a block on the way
+ *         cannot be emptied
+ */
 static ir_node* walk_to_projx(ir_node* start, const ir_node* dependency)
 {
 	int arity;
@@ -83,18 +107,21 @@ static ir_node* walk_to_projx(ir_node* start, const ir_node* dependency)
 	arity = get_irn_arity(start);
 	for (i = 0; i < arity; ++i) {
 		ir_node* pred = get_irn_n(start, i);
-		ir_node* pred_block = get_nodes_block(pred);
+		ir_node* pred_block = get_nodes_block(skip_Proj(pred));
 
 		if (pred_block == dependency) {
 			if (is_Proj(pred)) {
 				assert(get_irn_mode(pred) == mode_X);
+				/* we found it */
 				return pred;
 			}
+			/* Not a Proj? Should not happen. */
 			return NULL;
 		}
 
 		if (is_Proj(pred)) {
 			assert(get_irn_mode(pred) == mode_X);
+			/* another Proj but not from the control block */
 			return NULL;
 		}
 
@@ -107,22 +134,37 @@ static ir_node* walk_to_projx(ir_node* start, const ir_node* dependency)
 
 
 /**
- * Copies the DAG starting at node to the ith predecessor block of src_block
- * -if the node isn't in the src_block, this is a nop and the node is returned
- * -if the node is a phi in the src_block, the ith predecessor of the phi is
- *   returned
- * otherwise returns the copy of the passed node
+ * Recursively copies the DAG starting at node to the i-th predecessor
+ * block of src_block
+ * - if node isn't in the src_block, recursion ends and node is returned
+ * - if node is a Phi in the src_block, the i-th predecessor of this Phi is
+ *   returned and recursion ends
+ * otherwise returns a copy of the passed node created in the i-th predecessor of
+ * src_block.
+ *
+ * @param node       a root of a DAG
+ * @param src_block  the block of the DAG
+ * @param i          the position of the predecessor the DAG
+ *                   is moved to
+ *
+ * @return  the root of the copied DAG
  */
 static ir_node* copy_to(ir_node* node, ir_node* src_block, int i)
 {
 	ir_node* dst_block;
 	ir_node* copy;
-	int arity;
 	int j;
 
-	if (get_nodes_block(node) != src_block) return node;
-	if (get_irn_op(node) == op_Phi) return get_irn_n(node, i);
+	if (get_nodes_block(node) != src_block) {
+		/* already outside src_block, do not copy */
+		return node;
+	}
+	if (is_Phi(node)) {
+		/* move through the Phi to the i-th predecessor */
+		return get_irn_n(node, i);
+	}
 
+	/* else really need a copy */
 	copy = exact_copy(node);
 	dst_block = get_nodes_block(get_irn_n(src_block, i));
 	set_nodes_block(copy, dst_block);
@@ -130,8 +172,8 @@ static ir_node* copy_to(ir_node* node, ir_node* src_block, int i)
 	DB((dbg, LEVEL_1, "Copying node %+F to block %+F, copy is %+F\n",
 		node, dst_block, copy));
 
-	arity = get_irn_arity(node);
-	for (j = 0; j < arity; ++j) {
+	/* move recursively all predecessors */
+	for (j = get_irn_arity(node) - 1; j >= 0; --j) {
 		set_irn_n(copy, j, copy_to(get_irn_n(node, j), src_block, i));
 		DB((dbg, LEVEL_2, "-- pred %d is %+F\n", j, get_irn_n(copy, j)));
 	}
@@ -140,7 +182,13 @@ static ir_node* copy_to(ir_node* node, ir_node* src_block, int i)
 
 
 /**
- * Remove predecessors i and j from node and add predecessor new_pred
+ * Remove predecessors i and j (i < j) from a node and
+ * add an additional predecessor new_pred.
+ *
+ * @param node      the node whose inputs are changed
+ * @param i         the first index to remove
+ * @param j         the second index to remove
+ * @param new_pred  a node that is added as a new input to node
  */
 static void rewire(ir_node* node, int i, int j, ir_node* new_pred)
 {
@@ -162,7 +210,7 @@ static void rewire(ir_node* node, int i, int j, ir_node* new_pred)
 
 
 /**
- * Remove the jth predecessors from the ith predecessor of block and add it to block
+ * Remove the j-th predecessors from the i-th predecessor of block and add it to block
  */
 static void split_block(ir_node* block, int i, int j)
 {
@@ -242,10 +290,12 @@ static void prepare_path(ir_node* block, int i, const ir_node* dependency)
 	}
 }
 
-
-static void if_conv_walker(ir_node* block, void* env)
+/**
+ * Block walker: Search for diamonds and do the if conversion.
+ */
+static void if_conv_walker(ir_node *block, void *ctx)
 {
-	ir_settings_if_conv_t* opt_info = env;
+	walker_env *env = ctx;
 	int arity;
 	int i;
 
@@ -279,7 +329,10 @@ restart:
 				ir_node* sel;
 				ir_node* mux_block;
 				ir_node* phi;
+				ir_node* p;
 				ir_node* pred1;
+				bool     supported;
+				bool     negated;
 				dbg_info* cond_dbg;
 
 				pred1 = get_Block_cfgpred_block(block, j);
@@ -290,19 +343,37 @@ restart:
 
 				if (projx1 == NULL) continue;
 
+				sel = get_Cond_selector(cond);
 				phi = get_Block_phis(block);
-				if (!opt_info->allow_ifconv(get_Cond_selector(cond), phi, i, j)) continue;
+				supported = true;
+				negated   = get_Proj_proj(projx0) == pn_Cond_false;
+				for (p = phi; p != NULL; p = get_Phi_next(p)) {
+					ir_node *mux_false;
+					ir_node *mux_true;
+					if (negated) {
+						mux_true  = get_Phi_pred(p, j);
+						mux_false = get_Phi_pred(p, i);
+					} else {
+						mux_true  = get_Phi_pred(p, i);
+						mux_false = get_Phi_pred(p, j);
+					}
+					if (!env->params->allow_ifconv(sel, mux_false, mux_true)) {
+						supported = false;
+						break;
+					}
+				}
+				if (!supported)
+					continue;
 
 				DB((dbg, LEVEL_1, "Found Cond %+F with proj %+F and %+F\n",
 					cond, projx0, projx1
 				));
 
+				env->changed = 1;
 				prepare_path(block, i, dependency);
 				prepare_path(block, j, dependency);
 				arity = get_irn_arity(block);
 
-				sel = get_Cond_selector(cond);
-
 				mux_block = get_nodes_block(cond);
 				cond_dbg = get_irn_dbg_info(cond);
 				do {
@@ -321,15 +392,15 @@ restart:
 						 * one block, but not at the same memory node
 						 */
 						assert(get_irn_mode(phi) != mode_M);
-						if (get_Proj_proj(projx0) == pn_Cond_true) {
-							t = val_i;
-							f = val_j;
-						} else {
+						if (negated) {
 							t = val_j;
 							f = val_i;
+						} else {
+							t = val_i;
+							f = val_j;
 						}
 
-						mux = new_rd_Mux(cond_dbg, current_ir_graph, mux_block, sel, f, t, get_irn_mode(phi));
+						mux = new_rd_Mux(cond_dbg, mux_block, sel, f, t, get_irn_mode(phi));
 						DB((dbg, LEVEL_2, "Generating %+F for %+F\n", mux, phi));
 					}
 
@@ -340,7 +411,6 @@ restart:
 					} else {
 						rewire(phi, i, j, mux);
 					}
-
 					phi = next_phi;
 				} while (phi != NULL);
 
@@ -369,7 +439,7 @@ restart:
 #endif
 					return;
 				} else {
-					rewire(block, i, j, new_r_Jmp(current_ir_graph, mux_block));
+					rewire(block, i, j, new_r_Jmp(mux_block));
 					goto restart;
 				}
 			}
@@ -378,7 +448,7 @@ restart:
 }
 
 /**
- * Block walker: clear block mark and Phi list
+ * Block walker: clear block marks and Phi lists.
  */
 static void init_block_link(ir_node *block, void *env)
 {
@@ -389,10 +459,11 @@ static void init_block_link(ir_node *block, void *env)
 
 
 /**
- * Daisy-chain all phis in a block
+ * Daisy-chain all Phis in a block.
  * If a non-movable node is encountered set the has_pinned flag in its block.
  */
-static void collect_phis(ir_node *node, void *env) {
+static void collect_phis(ir_node *node, void *env)
+{
 	(void) env;
 
 	if (is_Phi(node)) {
@@ -402,10 +473,9 @@ static void collect_phis(ir_node *node, void *env) {
 	} else {
 		if (is_no_Block(node) && get_irn_pinned(node) == op_pin_state_pinned) {
 			/*
-			 * Ignore control flow nodes, these will be removed.
-			 * This ignores Raise. That is surely bad. FIXME.
+			 * Ignore control flow nodes (except Raise), these will be removed.
 			 */
-			if (!is_cfop(node)) {
+			if (!is_cfop(node) && !is_Raise(node)) {
 				ir_node *block = get_nodes_block(node);
 
 				DB((dbg, LEVEL_2, "Node %+F in block %+F is unmovable\n", node, block));
@@ -415,115 +485,13 @@ static void collect_phis(ir_node *node, void *env) {
 	}
 }
 
-static void optimise_muxs_0(ir_node* mux, void* env)
-{
-	ir_node* t;
-	ir_node* f;
-
-	(void) env;
-
-	if (!is_Mux(mux)) return;
-
-	t = get_Mux_true(mux);
-	f = get_Mux_false(mux);
-
-	DB((dbg, LEVEL_3, "Simplify %+F T=%+F F=%+F\n", mux, t, f));
-
-	if (is_Unknown(t)) {
-		DB((dbg, LEVEL_3, "Replace Mux with unknown operand by %+F\n", f));
-		exchange(mux, f);
-		return;
-	}
-	if (is_Unknown(f)) {
-		DB((dbg, LEVEL_3, "Replace Mux with unknown operand by %+F\n", t));
-		exchange(mux, t);
-		return;
-	}
-
-	if (is_Mux(t)) {
-		ir_graph* irg   = current_ir_graph;
-		ir_node*  block = get_nodes_block(mux);
-		ir_mode*  mode  = get_irn_mode(mux);
-		ir_node*  c0    = get_Mux_sel(mux);
-		ir_node*  c1    = get_Mux_sel(t);
-		ir_node*  t1    = get_Mux_true(t);
-		ir_node*  f1    = get_Mux_false(t);
-		if (f == f1) {
-			/* Mux(c0, Mux(c1, x, y), y) -> typical if (c0 && c1) x else y */
-			ir_node* and_    = new_r_And(irg, block, c0, c1, mode_b);
-			ir_node* new_mux = new_r_Mux(irg, block, and_, f1, t1, mode);
-			exchange(mux, new_mux);
-		} else if (f == t1) {
-			/* Mux(c0, Mux(c1, x, y), x) */
-			ir_node* not_c1 = new_r_Not(irg, block, c1, mode_b);
-			ir_node* and_   = new_r_And(irg, block, c0, not_c1, mode_b);
-			ir_node* new_mux = new_r_Mux(irg, block, and_, t1, f1, mode);
-			exchange(mux, new_mux);
-		}
-	} else if (is_Mux(f)) {
-		ir_graph* irg   = current_ir_graph;
-		ir_node*  block = get_nodes_block(mux);
-		ir_mode*  mode  = get_irn_mode(mux);
-		ir_node*  c0    = get_Mux_sel(mux);
-		ir_node*  c1    = get_Mux_sel(f);
-		ir_node*  t1    = get_Mux_true(f);
-		ir_node*  f1    = get_Mux_false(f);
-		if (t == t1) {
-			/* Mux(c0, x, Mux(c1, x, y)) -> typical if (c0 || c1) x else y */
-			ir_node* or_     = new_r_Or(irg, block, c0, c1, mode_b);
-			ir_node* new_mux = new_r_Mux(irg, block, or_, f1, t1, mode);
-			exchange(mux, new_mux);
-		} else if (t == f1) {
-			/* Mux(c0, x, Mux(c1, y, x)) */
-			ir_node* not_c1  = new_r_Not(irg, block, c1, mode_b);
-			ir_node* or_     = new_r_Or(irg, block, c0, not_c1, mode_b);
-			ir_node* new_mux = new_r_Mux(irg, block, or_, t1, f1, mode);
-			exchange(mux, new_mux);
-		}
-	}
-}
-
-
-static void optimise_muxs_1(ir_node* mux, void* env)
-{
-	ir_node* t;
-	ir_node* f;
-	ir_mode* mode;
-
-	(void) env;
-
-	if (!is_Mux(mux)) return;
-
-	t = get_Mux_true(mux);
-	f = get_Mux_false(mux);
-
-	DB((dbg, LEVEL_3, "Simplify %+F T=%+F F=%+F\n", mux, t, f));
-
-	mode = get_irn_mode(mux);
-
-	if (is_Const(t) && is_Const(f) && (mode_is_int(mode))) {
-		ir_node* block = get_nodes_block(mux);
-		ir_node* c     = get_Mux_sel(mux);
-		tarval* tv_t = get_Const_tarval(t);
-		tarval* tv_f = get_Const_tarval(f);
-		if (tarval_is_one(tv_t) && tarval_is_null(tv_f)) {
-			ir_node* conv  = new_r_Conv(current_ir_graph, block, c, mode);
-			exchange(mux, conv);
-		} else if (tarval_is_null(tv_t) && tarval_is_one(tv_f)) {
-			ir_node* not_  = new_r_Not(current_ir_graph, block, c, mode_b);
-			ir_node* conv  = new_r_Conv(current_ir_graph, block, not_, mode);
-			exchange(mux, conv);
-		}
-	}
-}
-
-
 void opt_if_conv(ir_graph *irg, const ir_settings_if_conv_t *params)
 {
-	ir_settings_if_conv_t p;
+	walker_env env;
 
 	/* get the parameters */
-	p = (params != NULL ? *params : default_info);
+	env.params  = (params != NULL ? params : &default_info);
+	env.changed = 0;
 
 	FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
 
@@ -533,28 +501,49 @@ void opt_if_conv(ir_graph *irg, const ir_settings_if_conv_t *params)
 	remove_critical_cf_edges(irg);
 
 	compute_cdep(irg);
-	assure_doms(irg);
 
-	ir_reserve_resources(irg, IR_RESOURCE_BLOCK_MARK);
+	ir_reserve_resources(irg, IR_RESOURCE_BLOCK_MARK | IR_RESOURCE_PHI_LIST);
 
 	irg_block_walk_graph(irg, init_block_link, NULL, NULL);
 	irg_walk_graph(irg, collect_phis, NULL, NULL);
-	irg_block_walk_graph(irg, NULL, if_conv_walker, &p);
+	irg_block_walk_graph(irg, NULL, if_conv_walker, &env);
 
-	ir_free_resources(irg, IR_RESOURCE_BLOCK_MARK);
+	ir_free_resources(irg, IR_RESOURCE_BLOCK_MARK | IR_RESOURCE_PHI_LIST);
 
-	local_optimize_graph(irg);
+	if (env.changed) {
+		local_optimize_graph(irg);
 
-	irg_walk_graph(irg, NULL, optimise_muxs_0, NULL);
-#if 1
-	irg_walk_graph(irg, NULL, optimise_muxs_1, NULL);
-#endif
-
-	/* TODO: graph might be changed, handle more graceful */
-	set_irg_outs_inconsistent(irg);
-	set_irg_extblk_inconsistent(irg);
-	set_irg_loopinfo_inconsistent(irg);
-	free_dom(irg);
+		/* graph has changed, invalidate analysis info */
+		set_irg_outs_inconsistent(irg);
+		set_irg_extblk_inconsistent(irg);
+		set_irg_loopinfo_inconsistent(irg);
+		set_irg_doms_inconsistent(irg);
+	}
 
 	free_cdep(irg);
 }
+
+struct pass_t {
+	ir_graph_pass_t             pass;
+	const ir_settings_if_conv_t *params;
+};
+
+/**
+ * Wrapper for running opt_if_conv() as an ir_graph pass.
+ */
+static int pass_wrapper(ir_graph *irg, void *context)
+{
+	struct pass_t *pass = context;
+	opt_if_conv(irg, pass->params);
+	return 0;
+}
+
+ir_graph_pass_t *opt_if_conv_pass(const char *name,
+                                  const ir_settings_if_conv_t *params)
+{
+	struct pass_t *pass = XMALLOCZ(struct pass_t);
+	pass->params = params;
+
+	return def_graph_pass_constructor(
+		&pass->pass, name ? name : "ifconv", pass_wrapper);
+}