X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbessaconstr.c;h=0cb6df97b72be080dd13fabc9004ae4f132ea45a;hb=ee5425ca1c172c4cf244de9864f8fd44ad2cb645;hp=26e39219d7f0f75d9aebe89b60abc2a62fd1a123;hpb=ce6161a7e42a48f7422b7babcc64d8ace18e2687;p=libfirm

diff --git a/ir/be/bessaconstr.c b/ir/be/bessaconstr.c
index 26e39219d..0cb6df97b 100644
--- a/ir/be/bessaconstr.c
+++ b/ir/be/bessaconstr.c
@@ -20,16 +20,16 @@
 /**
  * @file
  * @brief       SSA construction for a set of nodes
- * @author      Sebastian Hack, Daniel Grund, Matthias Braun, Christian Wuerdig
+ * @author      Sebastian Hack, Daniel Grund, Matthias Braun, Christian Wuerdig,
+ *              Sebastian Buchwald
  * @date        04.05.2005
- * @version     $Id$
  *
  * The problem: Given a value and a set of "copies" that are known to
  * represent the same abstract value, rewire all usages of the original value
  * to their closest copy while introducing phis as necessary.
  *
  * Algorithm: Mark all blocks in the iterated dominance frontiers of the value
- * and it's copies. Link the copies ordered by dominance to the blocks.  Then
+ * and its copies. Link the copies ordered by dominance to the blocks.  Then
  * we search for each use all definitions in the current block, if none is
  * found, then we search one in the immediate dominator. If we are in a block
  * of the dominance frontier, create a phi and do the same search for all
@@ -64,19 +64,133 @@
 #include "pdeq.h"
 #include "array.h"
 #include "irdom.h"
+#include "irnodeset.h"
 
 #include "ircons.h"
 #include "iredges_t.h"
 
 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
 
+static ir_node *search_def_end_of_block(be_ssa_construction_env_t *env,
+                                        ir_node *block);
+
+struct constr_info {
+	bool is_definition     : 1;
+	bool is_use            : 1;
+	bool already_processed : 1;
+	union {
+		/* Since we only consider scheduled nodes,
+		 * this points to the real definition (e.g. a Proj). */
+		ir_node *definition;
+
+		/* Last definition of a block. */
+		ir_node *last_definition;
+	};
+};
+
+typedef struct constr_info constr_info;
+
+/**
+ * @return Whether the block contains a definition.
+ */
+static bool has_definition(const ir_node *block)
+{
+	return irn_visited(block);
+}
+
+static constr_info *get_or_set_info(be_ssa_construction_env_t *env,
+                                    const ir_node *node)
+{
+	constr_info *info = ir_nodemap_get(&env->infos, node);
+	if (info == NULL) {
+		info = OALLOCZ(&env->obst, constr_info);
+		ir_nodemap_insert(&env->infos, node, info);
+	}
+	return info;
+}
+
+static constr_info *get_info(const be_ssa_construction_env_t *env,
+                             const ir_node *node)
+{
+	return (constr_info*)ir_nodemap_get(&env->infos, node);
+}
+
+/**
+ * @return Whether the block contains a use.
+ */
+static inline bool has_use(be_ssa_construction_env_t *env, ir_node *block)
+{
+	constr_info *info = get_or_set_info(env, block);
+	return info->is_use;
+}
+
+/**
+ * @return Whether the node is a definition.
+ */
+static bool is_definition(be_ssa_construction_env_t *env, ir_node *node)
+{
+	constr_info *info = get_info(env, node);
+	return info != NULL && info->is_definition;
+}
+
+/**
+ * @return Whether the node is a use.
+ */
+static bool is_use(const be_ssa_construction_env_t *env, ir_node *node)
+{
+	constr_info *info = get_info(env, node);
+	return info != NULL && info->is_use;
+}
+
+/**
+ * Introduces a definition at the corresponding block.
+ */
+static void introduce_definition(be_ssa_construction_env_t *env, ir_node *def)
+{
+	ir_node     *block      = get_nodes_block(def);
+	constr_info *def_info   = get_or_set_info(env, def);
+	ir_node     *skip       = skip_Proj(def);
+	constr_info *skip_info  = get_or_set_info(env, skip);
+	constr_info *block_info = get_or_set_info(env, block);
+
+	DBG((dbg, LEVEL_2, "\tintroducing definition %+F in %+F\n", def, block));
+
+	def_info->is_definition = true;
+
+	skip_info->is_definition = true;
+	skip_info->definition    = def;
+
+	// Set the last definition if we only introduce one definition for the block
+	if (has_definition(block)) {
+		assert(!block_info->already_processed);
+		block_info->last_definition = NULL;
+	} else {
+		mark_irn_visited(block);
+		block_info->last_definition = def;
+	}
+}
+
+static void introduce_use(be_ssa_construction_env_t *env, ir_node *use)
+{
+	ir_node     *block      = get_nodes_block(use);
+	constr_info *info       = get_or_set_info(env, use);
+	constr_info *block_info = get_or_set_info(env, block);
+
+	DBG((dbg, LEVEL_2, "\tintroducing use %+F in %+F\n", use, block));
+
+	info->is_use       = true;
+	block_info->is_use = true;
+
+	waitq_put(env->worklist, use);
+}
+
 /**
  * Calculates the iterated dominance frontier of a set of blocks. Marks the
  * blocks as visited. Sets the link fields of the blocks in the dominance
  * frontier to the block itself.
  */
 static void mark_iterated_dominance_frontiers(
-		const be_ssa_construction_env_t *env)
+                                           const be_ssa_construction_env_t *env)
 {
 	stat_ev_cnt_decl(blocks);
 	DBG((dbg, LEVEL_3, "Dominance Frontier:"));
@@ -107,11 +221,15 @@ static void mark_iterated_dominance_frontiers(
 	DBG((dbg, LEVEL_3, "\n"));
 }
 
-static ir_node *search_def_end_of_block(be_ssa_construction_env_t *env,
-                                        ir_node *block);
-
-static ir_node *create_phi(be_ssa_construction_env_t *env, ir_node *block,
-                           ir_node *link_with)
+/**
+ * Inserts a new phi at the given block.
+ *
+ * The constructed phi has only Dummy operands,
+ * but can be used as definition for other nodes.
+ *
+ * @see fix_phi_arguments
+ */
+static ir_node *insert_dummy_phi(be_ssa_construction_env_t *env, ir_node *block)
 {
 	int i, n_preds = get_Block_n_cfgpreds(block);
 	ir_graph *irg = get_Block_irg(block);
@@ -119,6 +237,8 @@ static ir_node *create_phi(be_ssa_construction_env_t *env, ir_node *block,
 	ir_node  *dummy;
 	ir_node  *phi;
 
+	DBG((dbg, LEVEL_3, "\t...create phi at block %+F\n", block));
+
 	assert(n_preds > 1);
 
 	dummy = new_r_Dummy(irg, env->mode);
@@ -126,120 +246,168 @@ static ir_node *create_phi(be_ssa_construction_env_t *env, ir_node *block,
 		ins[i] = dummy;
 	}
 	phi = be_new_Phi(block, n_preds, ins, env->mode, env->phi_cls);
-	if (env->new_phis != NULL) {
-		ARR_APP1(ir_node*, env->new_phis, phi);
-	}
-
-	if (env->mode != mode_M) {
-		sched_add_after(block, phi);
-	}
+	sched_add_after(block, phi);
+	ARR_APP1(ir_node*, env->new_phis, phi);
 
 	DBG((dbg, LEVEL_2, "\tcreating phi %+F in %+F\n", phi, block));
-	set_irn_link(link_with, phi);
-	mark_irn_visited(block);
-
-	for (i = 0; i < n_preds; ++i) {
-		ir_node *pred_block = get_Block_cfgpred_block(block, i);
-		ir_node *pred_def   = search_def_end_of_block(env, pred_block);
+	introduce_definition(env, phi);
 
-		set_irn_n(phi, i, pred_def);
-	}
+	waitq_put(env->worklist, phi);
 
 	return phi;
 }
 
+/**
+ * @return Last definition of the immediate dominator.
+ */
 static ir_node *get_def_at_idom(be_ssa_construction_env_t *env, ir_node *block)
 {
 	ir_node *dom = get_Block_idom(block);
 	assert(dom != NULL);
+	DBG((dbg, LEVEL_3, "\t...continue at idom %+F\n", dom));
 	return search_def_end_of_block(env, dom);
 }
 
-static ir_node *search_def_end_of_block(be_ssa_construction_env_t *env,
-                                        ir_node *block)
+/**
+ * Fixes all operands of a use.
+ *
+ * If an operand of the use is a (original) definition,
+ * it will be replaced by the given definition.
+ */
+static void set_operands(be_ssa_construction_env_t *env, ir_node *use, ir_node *def)
 {
-	if (irn_visited(block)) {
-		assert(get_irn_link(block) != NULL);
-		return (ir_node*)get_irn_link(block);
-	} else if (Block_block_visited(block)) {
-		return create_phi(env, block, block);
-	} else {
-		ir_node *def = get_def_at_idom(env, block);
-		mark_irn_visited(block);
-		set_irn_link(block, def);
-		return def;
+	constr_info *info  = get_info(env, use);
+	int          arity = get_irn_arity(use);
+	int          i;
+
+	for (i = 0; i < arity; ++i) {
+		ir_node *op = get_irn_n(use, i);
+
+		if (is_definition(env, op)) {
+			DBG((dbg, LEVEL_1, "\t...%+F(%d) -> %+F\n", use, i, def));
+			set_irn_n(use, i, def);
+		}
 	}
+
+	info->already_processed = true;
 }
 
-static ir_node *search_def(be_ssa_construction_env_t *env, ir_node *at)
+/**
+ * Fixes all uses of the given block.
+ */
+static void process_block(be_ssa_construction_env_t *env, ir_node *block)
 {
-	ir_node *block = get_nodes_block(at);
-	ir_node *node;
-	ir_node *def;
+	ir_node     *node;
+	ir_node     *def        = NULL;
+	constr_info *block_info = get_or_set_info(env, block);
 
-	DBG((dbg, LEVEL_3, "\t...searching def at %+F\n", at));
+	assert(has_definition(block));
+	assert(!block_info->already_processed && "Block already processed");
 
-	/* no defs in the current block we can do the normal searching */
-	if (!irn_visited(block) && !Block_block_visited(block)) {
-		DBG((dbg, LEVEL_3, "\t...continue at idom\n"));
-		return get_def_at_idom(env, block);
-	}
+	DBG((dbg, LEVEL_3, "\tprocessing block  %+F\n", block));
 
-	/* there are defs in the current block, walk the linked list to find
-	   the one immediately dominating us
-	 */
-	node = block;
-	def  = (ir_node*)get_irn_link(node);
-	while (def != NULL) {
-		if (!value_dominates(at, def)) {
-			DBG((dbg, LEVEL_3, "\t...found dominating def %+F\n", def));
-			return def;
-		}
+	sched_foreach(block, node) {
+		if (is_use(env, node) && !is_Phi(node)) {
+			DBG((dbg, LEVEL_3, "\t...found use %+F\n", node));
 
-		node = def;
-		def  = (ir_node*)get_irn_link(node);
-	}
+			if (def == NULL) {
+				/* Create a phi if the block is in the dominance frontier. */
+				if (Block_block_visited(block)) {
+					def = insert_dummy_phi(env, block);
+				}
+				else {
+					def = get_def_at_idom(env, block);
+				}
+			}
 
-	/* block in dominance frontier? create a phi then */
-	if (Block_block_visited(block)) {
-		DBG((dbg, LEVEL_3, "\t...create phi at block %+F\n", block));
-		assert(!is_Phi(node));
-		return create_phi(env, block, node);
+			set_operands(env, node, def);
+		}
+
+		if (is_definition(env, node)) {
+			constr_info *info = get_info(env, node);
+			def = info->definition;
+			DBG((dbg, LEVEL_3, "\t...found definition %+F\n", def));
+		}
 	}
 
-	DBG((dbg, LEVEL_3, "\t...continue at idom (after checking block)\n"));
-	return get_def_at_idom(env, block);
+	block_info->already_processed = true;
+	block_info->last_definition   = def;
 }
 
 /**
- * Adds a definition into the link field of the block. The definitions are
- * sorted by dominance. A non-visited block means no definition has been
- * inserted yet.
+ * @return Last definition of the given block.
  */
-static void introduce_def_at_block(ir_node *block, ir_node *def)
+static ir_node *search_def_end_of_block(be_ssa_construction_env_t *env,
+                                        ir_node *block)
 {
-	if (irn_visited_else_mark(block)) {
-		ir_node *node = block;
-		ir_node *current_def;
-
-		for (;;) {
-			current_def = (ir_node*)get_irn_link(node);
-			if (current_def == def) {
-				/* already in block */
-				return;
+	constr_info *block_info      = get_or_set_info(env, block);
+	ir_node     *last_definition = block_info->last_definition;
+
+	if (last_definition != NULL)
+		return last_definition;
+
+	if (has_definition(block)) {
+		if (has_use(env, block)) {
+			if (!block_info->already_processed) {
+				process_block(env, block);
 			}
-			if (current_def == NULL)
-				break;
-			if (value_dominates(current_def, def))
-				break;
-			node = current_def;
 		}
+		else {
+			ir_node *def = NULL;
+
+			/* Search the last definition of the block. */
+			sched_foreach_reverse(block, def) {
+				if (is_definition(env, def)) {
+					constr_info *info = get_info(env, def);
+					def = info->definition;
+					DBG((dbg, LEVEL_3, "\t...found definition %+F\n", def));
+
+					break;
+				}
+			}
+
+			assert(def && "No definition found");
+
+			block_info->last_definition = def;
+		}
+
+		return block_info->last_definition;
+	} else if (Block_block_visited(block)) {
+		ir_node *phi = insert_dummy_phi(env, block);
+
+		block_info->last_definition = phi;
 
-		set_irn_link(node, def);
-		set_irn_link(def, current_def);
+		return phi;
 	} else {
-		set_irn_link(block, def);
-		set_irn_link(def, NULL);
+		ir_node *def = get_def_at_idom(env, block);
+
+		block_info->last_definition = def;
+
+		return def;
+	}
+}
+
+/**
+ * Fixes all operands of the given use.
+ */
+static void search_def_at_block(be_ssa_construction_env_t *env, ir_node *use)
+{
+	ir_node     *block      = get_nodes_block(use);
+	constr_info *block_info = get_or_set_info(env, block);
+
+	if (block_info->already_processed)
+		return;
+
+	if (has_definition(block)) {
+		process_block(env, block);
+	} else if (Block_block_visited(block)) {
+		ir_node *phi = insert_dummy_phi(env, block);
+
+		set_operands(env, use, phi);
+	} else {
+		ir_node *def = get_def_at_idom(env, block);
+
+		set_operands(env, use, def);
 	}
 }
 
@@ -261,6 +429,8 @@ void be_ssa_construction_init(be_ssa_construction_env_t *env, ir_graph *irg)
 	env->domfronts = be_get_irg_dom_front(irg);
 	env->new_phis  = NEW_ARR_F(ir_node*, 0);
 	env->worklist  = new_waitq();
+	ir_nodemap_init(&env->infos, irg);
+	obstack_init(&env->obst);
 
 	ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED
 			| IR_RESOURCE_BLOCK_VISITED | IR_RESOURCE_IRN_LINK);
@@ -276,6 +446,8 @@ void be_ssa_construction_init(be_ssa_construction_env_t *env, ir_graph *irg)
 void be_ssa_construction_destroy(be_ssa_construction_env_t *env)
 {
 	stat_ev_int("bessaconstr_phis", ARR_LEN(env->new_phis));
+	obstack_free(&env->obst, NULL);
+	ir_nodemap_destroy(&env->infos);
 	del_waitq(env->worklist);
 	DEL_ARR_F(env->new_phis);
 
@@ -295,17 +467,17 @@ void be_ssa_construction_add_copy(be_ssa_construction_env_t *env,
 
 	if (env->mode == NULL) {
 		env->mode    = get_irn_mode(copy);
-		env->phi_cls = arch_get_irn_reg_class_out(copy);
+		env->phi_cls = arch_get_irn_reg_class(copy);
 	} else {
 		assert(env->mode == get_irn_mode(copy));
 	}
 
 	block = get_nodes_block(copy);
 
-	if (!irn_visited(block)) {
+	if (!has_definition(block)) {
 		waitq_put(env->worklist, block);
 	}
-	introduce_def_at_block(block, copy);
+	introduce_definition(env, copy);
 }
 
 void be_ssa_construction_add_copies(be_ssa_construction_env_t *env,
@@ -317,7 +489,7 @@ void be_ssa_construction_add_copies(be_ssa_construction_env_t *env,
 
 	if (env->mode == NULL) {
 		env->mode    = get_irn_mode(copies[0]);
-		env->phi_cls = arch_get_irn_reg_class_out(copies[0]);
+		env->phi_cls = arch_get_irn_reg_class(copies[0]);
 	}
 
 	for (i = 0; i < copies_len; ++i) {
@@ -325,10 +497,10 @@ void be_ssa_construction_add_copies(be_ssa_construction_env_t *env,
 		ir_node *block = get_nodes_block(copy);
 
 		assert(env->mode == get_irn_mode(copy));
-		if (!irn_visited(block)) {
+		if (!has_definition(block)) {
 			waitq_put(env->worklist, block);
 		}
-		introduce_def_at_block(block, copy);
+		introduce_definition(env, copy);
 	}
 }
 
@@ -343,10 +515,38 @@ ir_node **be_ssa_construction_get_new_phis(be_ssa_construction_env_t *env)
 	return env->new_phis;
 }
 
+/**
+ * Fixes all arguments of a newly constructed phi.
+ *
+ * @see insert_dummy_phi
+ */
+static void fix_phi_arguments(be_ssa_construction_env_t *env, ir_node *phi)
+{
+	constr_info *info    = get_info(env, phi);
+	ir_node     *block   = get_nodes_block(phi);
+	int          i;
+	int          n_preds = get_Block_n_cfgpreds(block);
+
+	DBG((dbg, LEVEL_3, "\tfixing phi arguments  %+F\n", phi));
+
+	for (i = 0; i < n_preds; ++i) {
+		ir_node *op = get_irn_n(phi, i);
+
+		if (is_definition(env, op) || is_Dummy(op)) {
+			ir_node *pred_block = get_Block_cfgpred_block(block, i);
+			ir_node *pred_def   = search_def_end_of_block(env, pred_block);
+
+			DBG((dbg, LEVEL_1, "\t...%+F(%d) -> %+F\n", phi, i, pred_def));
+			set_irn_n(phi, i, pred_def);
+		}
+	}
+
+	info->already_processed = true;
+}
+
 void be_ssa_construction_fix_users_array(be_ssa_construction_env_t *env,
                                          ir_node **nodes, size_t nodes_len)
 {
-	const ir_edge_t *edge, *next;
 	size_t i;
 	stat_ev_cnt_decl(uses);
 
@@ -357,42 +557,52 @@ void be_ssa_construction_fix_users_array(be_ssa_construction_env_t *env,
 		env->iterated_domfront_calculated = 1;
 	}
 
+	DBG((dbg, LEVEL_1, "\tfixing users array\n"));
+
+	assert(waitq_empty(env->worklist));
+
 	stat_ev_tim_push();
+
 	for (i = 0; i < nodes_len; ++i) {
+		const ir_edge_t *edge, *next;
 		ir_node *value = nodes[i];
+		DBG((dbg, LEVEL_3, "\tfixing users of %+F\n", value));
+		introduce_definition(env, value);
 
-		/*
-		 * Search the valid def for each use and set it.
-		 */
 		foreach_out_edge_safe(value, edge, next) {
-			ir_node *use = get_edge_src_irn(edge);
-			ir_node *at  = use;
-			int pos      = get_edge_src_pos(edge);
-			ir_node *def;
+			ir_node *use   = get_edge_src_irn(edge);
 
 			if (env->ignore_uses != NULL &&
-			   ir_nodeset_contains(env->ignore_uses, use))
+					ir_nodeset_contains(env->ignore_uses, use))
 				continue;
+
 			if (is_Anchor(use) || is_End(use))
 				continue;
 
-			if (is_Phi(use)) {
-				ir_node *block     = get_nodes_block(use);
-				ir_node *predblock = get_Block_cfgpred_block(block, pos);
-				at = sched_last(predblock);
-			}
+			introduce_use(env, use);
+		}
+	}
 
-			def = search_def(env, at);
+	assert(!waitq_empty(env->worklist));
 
-			if (def == NULL) {
-				panic("no definition found for %+F at position %d", use, pos);
-			}
+	while (!waitq_empty(env->worklist)) {
+		ir_node     *use  = (ir_node *)waitq_get(env->worklist);
+		constr_info *info = get_info(env, use);
 
-			DBG((dbg, LEVEL_2, "\t%+F(%d) -> %+F\n", use, pos, def));
-			set_irn_n(use, pos, def);
-			stat_ev_cnt_inc(uses);
+		if (info->already_processed)
+			continue;
+
+		if (is_Phi(use)) {
+			fix_phi_arguments(env, use);
+		}
+		else {
+			DBG((dbg, LEVEL_3, "\tsearching def for %+F at %+F\n", use, get_nodes_block(use)));
+			search_def_at_block(env, use);
 		}
+
+		stat_ev_cnt_inc(uses);
 	}
+
 	be_timer_pop(T_SSA_CONSTR);
 
 	stat_ev_tim_pop("bessaconstr_fix_time");
@@ -421,7 +631,7 @@ void be_ssa_construction_update_liveness_phis(be_ssa_construction_env_t *env,
 	be_timer_pop(T_SSA_CONSTR);
 }
 
-BE_REGISTER_MODULE_CONSTRUCTOR(be_init_ssaconstr);
+BE_REGISTER_MODULE_CONSTRUCTOR(be_init_ssaconstr)
 void be_init_ssaconstr(void)
 {
 	FIRM_DBG_REGISTER(dbg, "firm.be.ssaconstr");