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

diff --git a/ir/be/bessaconstr.c b/ir/be/bessaconstr.c
index 26e39219d..2e30a140d 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,125 @@
 #include "pdeq.h"
 #include "array.h"
 #include "irdom.h"
+#include "irnodeset.h"
 
 #include "ircons.h"
 #include "iredges_t.h"
+#include "statev_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;
+	} u;
+};
+
+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(constr_info, &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 ir_nodemap_get(constr_info, &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;
+}
+
+/**
+ * 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->u.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->u.last_definition = NULL;
+	} else {
+		mark_irn_visited(block);
+		block_info->u.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:"));
@@ -84,7 +190,7 @@ static void mark_iterated_dominance_frontiers(
 	while (!waitq_empty(env->worklist)) {
 		int i;
 		ir_node  *block    = (ir_node*)waitq_get(env->worklist);
-		ir_node **domfront = be_get_dominance_frontier(env->domfronts, block);
+		ir_node **domfront = ir_get_dominance_frontier(block);
 		int domfront_len = ARR_LEN(domfront);
 
 		for (i = 0; i < domfront_len; ++i) {
@@ -107,11 +213,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,127 +229,163 @@ 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);
 	for (i = 0; i < n_preds; ++i) {
 		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);
-	}
+	phi = be_new_Phi(block, n_preds, ins, env->mode, env->phi_req);
+	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);
+	introduce_definition(env, phi);
 
-	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);
-
-		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)
+static ir_node *get_def_from_preds(be_ssa_construction_env_t *const env, ir_node *const block)
 {
-	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);
+	/* Create a phi if the block is in the dominance frontier. */
+	if (Block_block_visited(block)) {
+		return insert_dummy_phi(env, block);
 	} else {
-		ir_node *def = get_def_at_idom(env, block);
-		mark_irn_visited(block);
-		set_irn_link(block, def);
-		return def;
+		return get_def_at_idom(env, 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, constr_info *const use_info)
+{
+	int arity = get_irn_arity(use);
+	for (int 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);
+		}
 	}
+
+	use_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     *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) {
+		constr_info *const info = get_info(env, node);
+		if (!info)
+			continue;
 
-		node = def;
-		def  = (ir_node*)get_irn_link(node);
-	}
+		if (info->is_use && !is_Phi(node)) {
+			DBG((dbg, LEVEL_3, "\t...found use %+F\n", node));
 
-	/* 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);
+			if (def == NULL) {
+				/* Create a phi if the block is in the dominance frontier. */
+				def = get_def_from_preds(env, block);
+			}
+
+			set_operands(env, node, def, info);
+		}
+
+		if (info->is_definition) {
+			def = info->u.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->u.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->u.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);
+			}
+		}
+		else {
+			/* Search the last definition of the block. */
+			sched_foreach_reverse(block, def) {
+				constr_info const *const info = get_info(env, def);
+				if (info && info->is_definition) {
+					DBG((dbg, LEVEL_3, "\t...found definition %+F\n", info->u.definition));
+					block_info->u.last_definition = info->u.definition;
+					break;
+				}
 			}
-			if (current_def == NULL)
-				break;
-			if (value_dominates(current_def, def))
-				break;
-			node = current_def;
+
+			assert(block_info->u.last_definition && "No definition found");
 		}
 
-		set_irn_link(node, def);
-		set_irn_link(def, current_def);
+		return block_info->u.last_definition;
 	} else {
-		set_irn_link(block, def);
-		set_irn_link(def, NULL);
+		ir_node *const def = get_def_from_preds(env, block);
+		block_info->u.last_definition = def;
+		return def;
+	}
+}
+
+/**
+ * Fixes all operands of the given use.
+ */
+static void search_def_at_block(be_ssa_construction_env_t *const env, ir_node *const use, constr_info *const info)
+{
+	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 {
+		ir_node *const def = get_def_from_preds(env, block);
+		set_operands(env, use, def, info);
 	}
 }
 
@@ -248,19 +394,22 @@ void be_ssa_construction_init(be_ssa_construction_env_t *env, ir_graph *irg)
 	ir_node *sb   = get_irg_start_block(irg);
 	int n_blocks  = get_Block_dom_max_subtree_pre_num(sb);
 
-	stat_ev_ctx_push_fobj("bessaconstr", irg);
+	stat_ev_ctx_push_fmt("bessaconstr", "%+F", irg);
 	stat_ev_tim_push();
 
 	(void) n_blocks;
 	stat_ev_dbl("bessaconstr_n_blocks", n_blocks);
 
 	memset(env, 0, sizeof(env[0]));
-	be_assure_dom_front(irg);
 
 	env->irg       = 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);
+
+	assure_irg_properties(env->irg,
+	                      IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE_FRONTIERS);
 
 	ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED
 			| IR_RESOURCE_BLOCK_VISITED | IR_RESOURCE_IRN_LINK);
@@ -276,6 +425,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);
 
@@ -286,6 +437,24 @@ void be_ssa_construction_destroy(be_ssa_construction_env_t *env)
 	stat_ev_ctx_pop("bessaconstr");
 }
 
+static void determine_phi_req(be_ssa_construction_env_t *env, ir_node *value)
+{
+	const arch_register_req_t *req   = arch_get_irn_register_req(value);
+	env->mode = get_irn_mode(value);
+	if (req->width == 1) {
+		env->phi_req = req->cls->class_req;
+	} else {
+		/* construct a new register req... */
+		ir_graph            *irg     = get_irn_irg(value);
+		struct obstack      *obst    = be_get_be_obst(irg);
+		arch_register_req_t *new_req = OALLOCZ(obst, arch_register_req_t);
+		new_req->cls   = req->cls;
+		new_req->type  = req->type & arch_register_req_type_aligned;
+		new_req->width = req->width;
+		env->phi_req = new_req;
+	}
+}
+
 void be_ssa_construction_add_copy(be_ssa_construction_env_t *env,
                                   ir_node *copy)
 {
@@ -294,18 +463,17 @@ void be_ssa_construction_add_copy(be_ssa_construction_env_t *env,
 	assert(env->iterated_domfront_calculated == 0);
 
 	if (env->mode == NULL) {
-		env->mode    = get_irn_mode(copy);
-		env->phi_cls = arch_get_irn_reg_class_out(copy);
+		determine_phi_req(env, 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,
@@ -316,8 +484,7 @@ void be_ssa_construction_add_copies(be_ssa_construction_env_t *env,
 	assert(env->iterated_domfront_calculated == 0);
 
 	if (env->mode == NULL) {
-		env->mode    = get_irn_mode(copies[0]);
-		env->phi_cls = arch_get_irn_reg_class_out(copies[0]);
+		determine_phi_req(env, copies[0]);
 	}
 
 	for (i = 0; i < copies_len; ++i) {
@@ -325,28 +492,48 @@ 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);
 	}
 }
 
-void be_ssa_construction_set_ignore_uses(be_ssa_construction_env_t *env,
-                                         const ir_nodeset_t *ignore_uses)
+ir_node **be_ssa_construction_get_new_phis(be_ssa_construction_env_t *env)
 {
-	env->ignore_uses = ignore_uses;
+	return env->new_phis;
 }
 
-ir_node **be_ssa_construction_get_new_phis(be_ssa_construction_env_t *env)
+/**
+ * Fixes all arguments of a newly constructed phi.
+ *
+ * @see insert_dummy_phi
+ */
+static void fix_phi_arguments(be_ssa_construction_env_t *const env, ir_node *const phi, constr_info *const info)
 {
-	return env->new_phis;
+	ir_node *block   = get_nodes_block(phi);
+	int      n_preds = get_Block_n_cfgpreds(block);
+
+	DBG((dbg, LEVEL_3, "\tfixing phi arguments  %+F\n", phi));
+
+	for (int 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 +544,46 @@ 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) {
 		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;
-
-			if (env->ignore_uses != NULL &&
-			   ir_nodeset_contains(env->ignore_uses, use))
-				continue;
+		foreach_out_edge_safe(value, edge) {
+			ir_node *const use = get_edge_src_irn(edge);
 			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, info);
+		}
+		else {
+			DBG((dbg, LEVEL_3, "\tsearching def for %+F at %+F\n", use, get_nodes_block(use)));
+			search_def_at_block(env, use, info);
 		}
+
+		stat_ev_cnt_inc(uses);
 	}
+
 	be_timer_pop(T_SSA_CONSTR);
 
 	stat_ev_tim_pop("bessaconstr_fix_time");
@@ -421,7 +612,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");