X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fifconv.c;h=ab1703e3ad5a08b2bd70e59911f9b699c89906c0;hb=3958bfcd6866194c5dc191e0486b1886230afcba;hp=aa38e6239f48b75759c80a8ed450638be3fcb5a6;hpb=978ee2acb6ef64acdf50d0c446bf7e6ddb88a2d5;p=libfirm

diff --git a/ir/opt/ifconv.c b/ir/opt/ifconv.c
index aa38e6239..ab1703e3a 100644
--- a/ir/opt/ifconv.c
+++ b/ir/opt/ifconv.c
@@ -1,3 +1,22 @@
+/*
+ * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
+ *
+ * This file is part of libFirm.
+ *
+ * This file may be distributed and/or modified under the terms of the
+ * GNU General Public License version 2 as published by the Free Software
+ * Foundation and appearing in the file LICENSE.GPL included in the
+ * packaging of this file.
+ *
+ * Licensees holding valid libFirm Professional Edition licenses may use
+ * this file in accordance with the libFirm Commercial License.
+ * Agreement provided with the Software.
+ *
+ * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
+ * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE.
+ */
+
 /*
  * Project:     libFIRM
  * File name:   ir/opt/ifconv.c
@@ -6,7 +25,6 @@
  * Created:
  * CVS-ID:      $Id$
  * Copyright:   (c) 1998-2005 Universität Karlsruhe
- * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  */
 
 #if 1
@@ -14,12 +32,6 @@
 #ifdef HAVE_CONFIG_H
 #include "config.h"
 #endif
-#ifdef HAVE_MALLOC_H
-#include <malloc.h>
-#endif
-#ifdef HAVE_ALLOCA_H
-#include <alloca.h>
-#endif
 
 #include <assert.h>
 
@@ -35,6 +47,7 @@
 #include "irtools.h"
 #include "return.h"
 #include "array.h"
+#include "xmalloc.h"
 
 // debug
 #include "irdump.h"
@@ -42,25 +55,20 @@
 
 DEBUG_ONLY(firm_dbg_module_t *dbg);
 
-static ir_node* walk_to_projx(ir_node* start)
+/** allow every Psi to be created. */
+static int default_allow_ifconv(ir_node *sel, ir_node* phi_list, int i, int j)
 {
-	ir_node* pred;
-
-	pred = get_nodes_block(start);
-
-	/* if there are multiple control flow predecessors nothing sensible can be
-	 * done */
-	if (get_irn_arity(pred) > 1) return NULL;
-
-	pred = get_irn_n(pred, 0);
-	if (get_irn_op(pred) == op_Proj) {
-		assert(get_irn_mode(pred) == mode_X);
-		return pred;
-	} else {
-		return NULL;
-	}
+	return 1;
 }
 
+/**
+ * Default options.
+ */
+static const opt_if_conv_info_t default_info = {
+	0,    /* doesn't matter for Psi */
+	default_allow_ifconv
+};
+
 /**
  * Additional block info.
  */
@@ -80,6 +88,42 @@ static int can_empty_block(ir_node *block)
 }
 
 
+static ir_node* walk_to_projx(ir_node* start, const ir_node* dependency)
+{
+	int arity;
+	int i;
+
+	/* No need to find the conditional block if this block cannot be emptied and
+	 * therefore not moved
+	 */
+	if (!can_empty_block(start)) return NULL;
+
+	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);
+
+		if (pred_block == dependency) {
+			if (is_Proj(pred)) {
+				assert(get_irn_mode(pred) == mode_X);
+				return pred;
+			}
+			return NULL;
+		}
+
+		if (is_Proj(pred)) {
+			assert(get_irn_mode(pred) == mode_X);
+			return NULL;
+		}
+
+		if (is_cdep_on(pred_block, dependency)) {
+			return walk_to_projx(pred_block, dependency);
+		}
+	}
+	return NULL;
+}
+
+
 /**
  * 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
@@ -113,65 +157,6 @@ static ir_node* copy_to(ir_node* node, ir_node* src_block, int i)
 }
 
 
-/**
- * Duplicate and move the contents of ith block predecessor into its
- * predecessors if the block has multiple control dependencies and only one
- * successor.
- * Also bail out if the block contains non-movable nodes, because later
- * if-conversion would be pointless.
- */
-static int fission_block(ir_node* block, int i)
-{
-	ir_node* pred = get_irn_n(block, i);
-	ir_node* pred_block;
-	block_info* info;
-	ir_node* phi;
-	int pred_arity;
-	int arity;
-	ir_node** ins;
-	int j;
-
-	if (get_irn_op(pred) != op_Jmp) return 0;
-	pred_block = get_nodes_block(pred);
-
-	if (!has_multiple_cdep(pred_block)) return 0;
-	if (!can_empty_block(pred_block)) return 0;
-
-	DB((dbg, LEVEL_1, "Fissioning block %+F\n", pred_block));
-
-	pred_arity = get_irn_arity(pred_block);
-	arity = get_irn_arity(block);
-	info = get_block_blockinfo(block);
-	NEW_ARR_A(ir_node *, ins, arity + pred_arity - 1);
-	for (phi = info->phi; phi != NULL; phi = get_irn_link(phi)) {
-		for (j = 0; j < i; ++j) ins[j] = get_irn_n(phi, j);
-		for (j = 0; j < pred_arity; ++j) {
-			ins[i + j] = copy_to(get_irn_n(phi, i), pred_block, j);
-		}
-		for (j = i + 1; j < arity; ++j) {
-			ins[pred_arity - 1 + j] = get_irn_n(phi, j);
-		}
-		set_irn_in(phi, arity + pred_arity - 1, ins);
-	}
-	for (j = 0; j < i; ++j) ins[j] = get_irn_n(block, j);
-	for (j = 0; j < pred_arity; ++j) ins[i + j] = get_irn_n(pred_block, j);
-	for (j = i + 1; j < arity; ++j) ins[pred_arity - 1 + j] = get_irn_n(block, j);
-	set_irn_in(block, arity + pred_arity - 1, ins);
-
-	/* Kill all Phis in the fissioned block
-	 * This is to make sure they're not kept alive
-	 */
-	info = get_block_blockinfo(pred_block);
-	phi = info->phi;
-	while (phi != NULL) {
-		ir_node* next = get_irn_link(phi);
-		exchange(phi, new_Bad());
-		phi = next;
-	}
-	return 1;
-}
-
-
 /**
  * Remove predecessors i and j from node and add predecessor new_pred
  */
@@ -194,110 +179,206 @@ static void rewire(ir_node* node, int i, int j, ir_node* new_pred)
 }
 
 
-static void if_conv_walker(ir_node* block, void* env)
+/**
+ * Remove the jth predecessors from the ith predecessor of block and add it to block
+ */
+static void split_block(ir_node* block, int i, int j)
 {
+	ir_node* pred_block = get_nodes_block(get_irn_n(block, i));
+	int arity = get_irn_arity(block);
+	int new_pred_arity;
 	ir_node* phi;
+	ir_node **ins;
+	ir_node **pred_ins;
+	int k;
+
+	DB((dbg, LEVEL_1, "Splitting predecessor %d of predecessor %d of %+F\n", j, i, block));
+
+	NEW_ARR_A(ir_node*, ins, arity + 1);
+
+	for (phi = get_block_blockinfo(block)->phi; phi != NULL; phi = get_irn_link(phi)) {
+		ir_node* copy = copy_to(get_irn_n(phi, i), pred_block, j);
+
+		for (k = 0; k < i; ++k) ins[k] = get_irn_n(phi, k);
+		ins[k++] = copy;
+		for (; k < arity; ++k) ins[k] = get_irn_n(phi, k);
+		ins[k] = get_irn_n(phi, i);
+		assert(k == arity);
+		set_irn_in(phi, arity + 1, ins);
+	}
+
+	for (k = 0; k < i; ++k) ins[k] = get_irn_n(block, k);
+	ins[k++] = get_irn_n(pred_block, j);
+	for (; k < arity; ++k) ins[k] = get_irn_n(block, k);
+	ins[k] = get_irn_n(block, i);
+	assert(k == arity);
+	set_irn_in(block, arity + 1, ins);
+
+	new_pred_arity = get_irn_arity(pred_block) - 1;
+	NEW_ARR_A(ir_node*, pred_ins, new_pred_arity);
+
+	for (phi = get_block_blockinfo(pred_block)->phi; phi != NULL; phi = get_irn_link(phi)) {
+		for (k = 0; k < j; ++k) pred_ins[k] = get_irn_n(phi, k);
+		for (; k < new_pred_arity; ++k) pred_ins[k] = get_irn_n(phi, k + 1);
+		assert(k == new_pred_arity);
+		if (new_pred_arity > 1) {
+			set_irn_in(phi, new_pred_arity, pred_ins);
+		} else {
+			exchange(phi, pred_ins[0]);
+		}
+	}
+
+	for (k = 0; k < j; ++k) pred_ins[k] = get_irn_n(pred_block, k);
+	for (; k < new_pred_arity; ++k) pred_ins[k] = get_irn_n(pred_block, k + 1);
+	assert(k == new_pred_arity);
+	if (new_pred_arity > 1) {
+		set_irn_in(pred_block, new_pred_arity, pred_ins);
+	} else {
+		exchange(pred_block, get_nodes_block(pred_ins[0]));
+	}
+}
+
+
+static void prepare_path(ir_node* block, int i, const ir_node* dependency)
+{
+	ir_node* pred = get_nodes_block(get_irn_n(block, i));
+	int pred_arity;
+	int j;
+
+	DB((dbg, LEVEL_1, "Preparing predecessor %d of %+F\n", i, block));
+
+	pred_arity = get_irn_arity(pred);
+	for (j = 0; j < pred_arity; ++j) {
+		ir_node* pred_pred = get_nodes_block(get_irn_n(pred, j));
+
+		if (is_cdep_on(pred_pred, dependency)) {
+			prepare_path(pred, j, dependency);
+			split_block(block, i, j);
+			break;
+		}
+	}
+}
+
+
+static void if_conv_walker(ir_node* block, void* env)
+{
 	int arity;
 	int i;
+	opt_if_conv_info_t *opt_info = env;
 
 	/* Bail out, if there are no Phis at all */
 	if (get_block_blockinfo(block)->phi == NULL) return;
 
 restart:
-	arity = get_irn_arity(block);
-	for (i = 0; i < arity; ++i) {
-		if (fission_block(block, i)) goto restart;
-	}
-	//return;
-
 	arity = get_irn_arity(block);
 	for (i = 0; i < arity; ++i) {
 		ir_node* pred;
-		ir_node* cond;
-		ir_node* projx0;
-		int j;
-
-		projx0 = walk_to_projx(get_irn_n(block, i));
-		if (projx0 == NULL) return;
-		pred = get_Proj_pred(projx0);
-		if (get_irn_op(pred) != op_Cond || get_irn_mode(get_Cond_selector(pred)) != mode_b) continue;
-		cond = pred;
-
-		if (!can_empty_block(get_nodes_block(get_irn_n(block, i)))) {
-			DB((dbg, LEVEL_1, "Cannot empty block %+F\n",
-				get_nodes_block(get_irn_n(block, i))
-			));
-			continue;
-		}
+		cdep* cdep;
 
-		for (j = i + 1; j < arity; ++j) {
-			ir_node* projx1;
-			ir_node* psi_block;
-			ir_node* conds[1];
-			ir_node* vals[2];
-			ir_node* psi;
-
-			projx1 = walk_to_projx(get_irn_n(block, j));
-			if (projx1 == NULL) continue;
-			pred = get_Proj_pred(projx1);
-			if (get_irn_op(pred) != op_Cond || get_irn_mode(get_Cond_selector(pred)) != mode_b) continue;
-			if (pred != cond) continue;
-			DB((dbg, LEVEL_1, "Found Cond %+F with proj %+F and %+F\n", cond, projx0, projx1));
-
-			if (!can_empty_block(get_nodes_block(get_irn_n(block, j)))) {
-				DB((dbg, LEVEL_1, "Cannot empty %+F\n",	get_nodes_block(get_irn_n(block, j))));
-				continue;
-			}
+		pred = get_nodes_block(get_irn_n(block, i));
+		for (cdep = find_cdep(pred); cdep != NULL; cdep = cdep->next) {
+			const ir_node* dependency = cdep->node;
+			ir_node* projx0 = walk_to_projx(pred, dependency);
+			ir_node* cond;
+			int j;
 
-			conds[0] = get_Cond_selector(cond);
+			if (projx0 == NULL) continue;
 
-			psi_block = get_nodes_block(cond);
-			phi = get_block_blockinfo(block)->phi;
-			do {
-				ir_node* val_i = get_irn_n(phi, i);
-				ir_node* val_j = get_irn_n(phi, j);
+			cond = get_Proj_pred(projx0);
+			if (get_irn_op(cond) != op_Cond) continue;
 
-				if (val_i == val_j) {
-					psi = val_i;
-					DB((dbg, LEVEL_2,  "Generating no psi, because both values are equal\n"));
-				} else {
-					/* Something is very fishy if two predecessors of a PhiM point into
-					 * one block, but not at the same memory node
-					 */
-					assert(get_irn_mode(phi) != mode_M);
-					if (get_Proj_proj(projx0) == pn_Cond_true) {
-						vals[0] = val_i;
-						vals[1] = val_j;
+			/* We only handle boolean decisions, no switches */
+			if (get_irn_mode(get_Cond_selector(cond)) != mode_b) continue;
+
+			for (j = i + 1; j < arity; ++j) {
+				ir_node* projx1;
+				ir_node* conds[1];
+				ir_node* vals[2];
+				ir_node* psi = NULL;
+				ir_node* psi_block;
+				ir_node* phi;
+
+				pred = get_nodes_block(get_irn_n(block, j));
+
+				if (!is_cdep_on(pred, dependency)) continue;
+
+				projx1 = walk_to_projx(pred, dependency);
+
+				if (projx1 == NULL) continue;
+
+				phi = get_block_blockinfo(block)->phi;
+				if (!opt_info->allow_ifconv(get_Cond_selector(cond), phi, i, j)) continue;
+
+				DB((dbg, LEVEL_1, "Found Cond %+F with proj %+F and %+F\n",
+					cond, projx0, projx1
+				));
+
+				prepare_path(block, i, dependency);
+				prepare_path(block, j, dependency);
+				arity = get_irn_arity(block);
+
+				conds[0] = get_Cond_selector(cond);
+
+				psi_block = get_nodes_block(cond);
+				do {
+					ir_node* val_i = get_irn_n(phi, i);
+					ir_node* val_j = get_irn_n(phi, j);
+
+					if (val_i == val_j) {
+						psi = val_i;
+						DB((dbg, LEVEL_2,  "Generating no psi, because both values are equal\n"));
 					} else {
-						vals[0] = val_j;
-						vals[1] = val_i;
+						/* Something is very fishy if two predecessors of a PhiM point into
+						 * one block, but not at the same memory node
+						 */
+						assert(get_irn_mode(phi) != mode_M);
+						if (get_Proj_proj(projx0) == pn_Cond_true) {
+							vals[0] = val_i;
+							vals[1] = val_j;
+						} else {
+							vals[0] = val_j;
+							vals[1] = val_i;
+						}
+
+						psi = new_r_Psi(
+							current_ir_graph, psi_block, 1, conds, vals, get_irn_mode(phi)
+						);
+						DB((dbg, LEVEL_2, "Generating %+F for %+F\n", psi, phi));
 					}
-					psi = new_r_Psi(
-						current_ir_graph, psi_block, 1, conds, vals, get_irn_mode(phi)
-					);
-					DB((dbg, LEVEL_2, "Generating %+F for %+F\n", psi, phi));
-				}
 
-				if (arity == 2) {
-					exchange(phi, psi);
-				} else {
-					rewire(phi, i, j, psi);
-				}
+					/* only exchange if we have a Psi */
+					if (arity == 2) {
+						exchange(phi, psi);
+					} else {
+						rewire(phi, i, j, psi);
+					}
 
-				phi = get_irn_link(phi);
-			} while (phi != NULL);
+					phi = get_irn_link(phi);
+				} while (phi != NULL);
 
-			exchange(get_nodes_block(get_irn_n(block, i)), psi_block);
-			exchange(get_nodes_block(get_irn_n(block, j)), psi_block);
+				exchange(get_nodes_block(get_irn_n(block, i)), psi_block);
+				exchange(get_nodes_block(get_irn_n(block, j)), psi_block);
 
-			if (arity == 2) {
-				DB((dbg, LEVEL_1,  "Welding block %+F to %+F\n", block, psi_block));
-				get_block_blockinfo(psi_block)->has_pinned |=	get_block_blockinfo(block)->has_pinned;
-				exchange(block, psi_block);
-				return;
-			} else {
-				rewire(block, i, j, new_r_Jmp(current_ir_graph, psi_block));
-				goto restart;
+				if (arity == 2) {
+#if 1
+					DB((dbg, LEVEL_1,  "Welding block %+F and %+F\n", block, psi_block));
+					/* copy the block-info from the Psi-block to the block before merging */
+					get_block_blockinfo(psi_block)->has_pinned |= get_block_blockinfo(block)->has_pinned;
+					set_irn_link(block, get_irn_link(psi_block));
+
+					set_irn_in(block, get_irn_arity(psi_block), get_irn_in(psi_block) + 1);
+					exchange_cdep(psi_block, block);
+					exchange(psi_block, block);
+#else
+					DB((dbg, LEVEL_1,  "Welding block %+F to %+F\n", block, psi_block));
+					get_block_blockinfo(psi_block)->has_pinned |=	get_block_blockinfo(block)->has_pinned;
+					exchange(block, psi_block);
+#endif
+					return;
+				} else {
+					rewire(block, i, j, new_r_Jmp(current_ir_graph, psi_block));
+					goto restart;
+				}
 			}
 		}
 	}
@@ -555,36 +636,36 @@ static void optimise_psis(ir_node* node, void* env)
 void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
 {
 	struct obstack obst;
+	opt_if_conv_info_t p;
 
-	if (!get_opt_if_conversion())
+	if (! get_opt_if_conversion())
 		return;
 
+	/* get the parameters */
+	if (params)
+		memcpy(&p, params, sizeof(p));
+	else
+		memcpy(&p, &default_info, sizeof(p));
+
 	FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
 
 	DB((dbg, LEVEL_1, "Running if-conversion on %+F\n", irg));
 
-	dump_ir_block_graph(irg, "_00_pre");
-
 	normalize_one_return(irg);
 	remove_critical_cf_edges(irg);
 
-	dump_ir_block_graph(irg, "_01_normal");
-
 	compute_cdep(irg);
 	assure_doms(irg);
 
 	obstack_init(&obst);
 	irg_block_walk_graph(irg, init_block_link, NULL, &obst);
 	irg_walk_graph(irg, collect_phis, NULL, NULL);
-	irg_block_walk_graph(irg, NULL, if_conv_walker, NULL);
+	irg_block_walk_graph(irg, NULL, if_conv_walker, &p);
 
 	local_optimize_graph(irg);
-	dump_ir_block_graph(irg, "_02_ifconv");
 
 	irg_walk_graph(irg, NULL, optimise_psis, NULL);
 
-	dump_ir_block_graph(irg, "_03_postifconv");
-
 	obstack_free(&obst, NULL);
 
 	free_dom(irg);
@@ -1576,8 +1657,6 @@ void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
   DBG((dbg, LEVEL_1, "muxes made: %d\n", muxes_made));
 
   obstack_free(&obst, NULL);
-
-	dump_ir_block_graph(irg, "_ifconv_hack");
 }
 
 #endif