X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbeirgmod.c;h=444e69e0b7dc1d3cbb69f1e90602c3304c32b0a0;hb=d14c6378674f36728eacaf5dc7e4bb045ff9fbab;hp=c0bcf80e7cda4aee780fe2214383b8c7a38318aa;hpb=04d00146b0c97ce225c2a8e48ac99a2dcb95d3f4;p=libfirm

diff --git a/ir/be/beirgmod.c b/ir/be/beirgmod.c
index c0bcf80e7..444e69e0b 100644
--- a/ir/be/beirgmod.c
+++ b/ir/be/beirgmod.c
@@ -26,13 +26,17 @@
 #include "irdom_t.h"
 #include "iredges_t.h"
 #include "irgopt.h"
+#include "irprintf_t.h"
+#include "irgwalk.h"
 
 #include "be_t.h"
+#include "bechordal_t.h"
 #include "bearch.h"
 #include "besched_t.h"
 #include "belive_t.h"
 #include "benode_t.h"
 #include "beutil.h"
+#include "beinsn_t.h"
 
 #include "beirgmod.h"
 
@@ -53,7 +57,7 @@
 */
 
 
-struct _dom_front_info_t {
+struct _be_dom_front_info_t {
   pmap *df_map;
 };
 
@@ -107,9 +111,9 @@ static void compute_df(ir_node *n, pmap *df_map)
 
 }
 
-dom_front_info_t *be_compute_dominance_frontiers(ir_graph *irg)
+be_dom_front_info_t *be_compute_dominance_frontiers(ir_graph *irg)
 {
-  dom_front_info_t *info = xmalloc(sizeof(*info));
+  be_dom_front_info_t *info = xmalloc(sizeof(*info));
 
   edges_assure(irg);
   info->df_map = pmap_create();
@@ -119,7 +123,7 @@ dom_front_info_t *be_compute_dominance_frontiers(ir_graph *irg)
   return info;
 }
 
-void be_free_dominance_frontiers(dom_front_info_t *info)
+void be_free_dominance_frontiers(be_dom_front_info_t *info)
 {
   pmap_entry *ent;
 
@@ -130,48 +134,49 @@ void be_free_dominance_frontiers(dom_front_info_t *info)
   free(info);
 }
 
-pset *be_get_dominance_frontier(dom_front_info_t *info, ir_node *block)
+pset *be_get_dominance_frontier(be_dom_front_info_t *info, ir_node *block)
 {
   return pmap_get(info->df_map, block);
 }
 
-static void determine_phi_blocks(pset *copies, pset* copy_blocks, pset *phi_blocks, dom_front_info_t *df_info)
+static void determine_phi_blocks(pset *copies, pset *copy_blocks, pset *phi_blocks, be_dom_front_info_t *df_info)
 {
 	ir_node *bl;
 	pdeq *worklist = new_pdeq();
 	FIRM_DBG_REGISTER(firm_dbg_module_t *dbg, DBG_MODULE);
 
 	/*
-	* Fill the worklist queue and the rest of the orig blocks array.
-	*/
+	 * Fill the worklist queue and the rest of the orig blocks array.
+	 */
 	for(bl = pset_first(copy_blocks); bl; bl = pset_next(copy_blocks)) {
 		pdeq_putr(worklist, bl);
 	}
 
-	while(!pdeq_empty(worklist)) {
+	while (!pdeq_empty(worklist)) {
 		ir_node *bl = pdeq_getl(worklist);
 		pset *df    = be_get_dominance_frontier(df_info, bl);
 
 		ir_node *y;
 
 		DBG((dbg, LEVEL_3, "dom front of %+F\n", bl));
-		for(y = pset_first(df); y; y = pset_next(df))
-			DBG((dbg, LEVEL_3, "\t%+F\n", y));
+		DEBUG_ONLY(
+			for (y = pset_first(df); y; y = pset_next(df))
+				DBG((dbg, LEVEL_3, "\t%+F\n", y))
+		);
 
 		for(y = pset_first(df); y; y = pset_next(df)) {
 			if(!pset_find_ptr(phi_blocks, y)) {
 				pset_insert_ptr(phi_blocks, y);
 
 				/*
-				* Clear the link field of a possible phi block, since
-				* the possibly created phi will be stored there. See,
-				* search_def()
-				*/
+				 * Clear the link field of a possible phi block, since
+				 * the possibly created phi will be stored there. See,
+				 * search_def()
+				 */
 				set_irn_link(y, NULL);
 
 				if(!pset_find_ptr(copy_blocks, y))
 					pdeq_putr(worklist, y);
-
 			}
 		}
 	}
@@ -199,7 +204,7 @@ static void determine_phi_blocks(pset *copies, pset* copy_blocks, pset *phi_bloc
  *
  * The usage is given as a node and a position. Initially, the given operand
  * points to a node for which copies were introduced. We have to find
- * the valid copy for this usage. This is done by travering the
+ * the valid copy for this usage. This is done by traversing the
  * dominance tree upwards. If the usage is a phi function, we start
  * traversing from the predecessor block which corresponds to the phi
  * usage.
@@ -223,9 +228,9 @@ static ir_node *search_def(ir_node *usage, int pos, pset *copies, pset *copy_blo
 
 	DBG((dbg, LEVEL_1, "Searching valid def for use %+F at pos %d\n", usage, pos));
 	/*
-	* If the usage is in a phi node, search the copy in the
-	* predecessor denoted by pos.
-	*/
+	 * If the usage is in a phi node, search the copy in the
+	 * predecessor denoted by pos.
+	 */
 	if(is_Phi(usage)) {
 		curr_bl = get_Block_cfgpred_block(curr_bl, pos);
 		start_irn = sched_last(curr_bl);
@@ -238,10 +243,12 @@ static ir_node *search_def(ir_node *usage, int pos, pset *copies, pset *copy_blo
 	 * predecessor block of the usage.
   	 */
 	while(curr_bl != NULL) {
+		ir_node *phim;
 
 	    /*
 		 * If this block contains a copy, search the block
-		 * instruction by instruction.
+		 * instruction by instruction. If nothing is found
+		 * search for a not scheduled PhiM.
 		 */
 		if(pset_find_ptr(copy_blocks, curr_bl)) {
 			ir_node *irn;
@@ -253,15 +260,25 @@ static ir_node *search_def(ir_node *usage, int pos, pset *copies, pset *copy_blo
 				if(pset_find_ptr(copies, irn))
 					return irn;
 			}
+
+			for(phim = pset_first(copies); phim; phim = pset_next(copies)) {
+				if(!is_Phi(phim) || !(get_irn_mode(phim) == mode_M))
+					continue;
+
+				if(get_nodes_block(phim) == curr_bl) {
+					pset_break(copies);
+					return phim;
+				}
+			}
 		}
 
 		if(pset_find_ptr(phi_blocks, curr_bl)) {
 			ir_node *phi = get_irn_link(curr_bl);
 
-			if(!phi) {
+			if(phi == NULL) {
 				int i, n_preds = get_irn_arity(curr_bl);
 				ir_graph *irg = get_irn_irg(curr_bl);
-				ir_node **ins = xmalloc(n_preds * sizeof(ins[0]));
+				ir_node **ins = alloca(n_preds * sizeof(ins[0]));
 
 				for(i = 0; i < n_preds; ++i)
 					ins[i] = new_r_Bad(irg);
@@ -270,16 +287,26 @@ static ir_node *search_def(ir_node *usage, int pos, pset *copies, pset *copy_blo
 				DBG((dbg, LEVEL_2, "\tcreating phi %+F in %+F\n", phi, curr_bl));
 
 				set_irn_link(curr_bl, phi);
-				sched_add_after(curr_bl, phi);
-				free(ins);
+				if(mode != mode_M)
+					sched_add_after(curr_bl, phi);
 
 				for(i = 0; i < n_preds; ++i) {
 					ir_node *arg = search_def(phi, i, copies, copy_blocks, phis, phi_blocks, mode);
+					if(arg == NULL) {
+						ir_node *irn;
+
+						ir_fprintf(stderr, "no definition found for %+F at position %d\nCopies: ", phi, i);
+						for(irn = pset_first(copies); irn; irn = pset_next(copies)) {
+							ir_fprintf(stderr, "%+F ", irn);
+						}
+						ir_fprintf(stderr, "\n\n");
+						assert(arg && "no definition found");
+					}
 					DBG((dbg, LEVEL_2, "\t\t%+F(%d) -> %+F\n", phi, i, arg));
 					set_irn_n(phi, i, arg);
 				}
 
-				if(phis)
+				if(phis != NULL)
 					pset_insert_ptr(phis, phi);
 			}
 
@@ -298,28 +325,27 @@ static ir_node *search_def(ir_node *usage, int pos, pset *copies, pset *copy_blo
 static void fix_usages(pset *copies, pset *copy_blocks, pset *phi_blocks, pset *phis, pset *ignore_uses)
 {
 	int n_outs = 0;
-	FIRM_DBG_REGISTER(firm_dbg_module_t *dbg, DBG_MODULE);
-
 	struct obstack obst;
 	ir_node *irn;
 	int i;
-
 	struct out {
 		ir_node *irn;
 		int pos;
 	} *outs;
 
+	FIRM_DBG_REGISTER(firm_dbg_module_t *dbg, DBG_MODULE);
+
 	obstack_init(&obst);
 
 	/*
- 	* Put all outs into an array.
- 	* This is necessary, since the outs would be modified while
- 	* iterating on them what could bring the outs module in trouble.
-	*/
-	for(irn = pset_first(copies); irn; irn = pset_next(copies)) {
+ 	 * Put all outs into an array.
+ 	 * This is necessary, since the outs would be modified while
+ 	 * iterating on them what could bring the outs module in trouble.
+	 */
+	for (irn = pset_first(copies); irn; irn = pset_next(copies)) {
 		const ir_edge_t *edge;
 		foreach_out_edge(irn, edge) {
-			if(!pset_find_ptr(ignore_uses, get_edge_src_irn(edge))) {
+			if (!pset_find_ptr(ignore_uses, get_edge_src_irn(edge))) {
 				struct out tmp;
 				tmp.irn = get_edge_src_irn(edge);
 				tmp.pos = get_edge_src_pos(edge);
@@ -343,13 +369,21 @@ static void fix_usages(pset *copies, pset *copy_blocks, pset *phi_blocks, pset *
 		def = search_def(irn, pos, copies, copy_blocks, phis, phi_blocks, mode);
 		DBG((dbg, LEVEL_2, "\t%+F(%d) -> %+F\n", irn, pos, def));
 
-		if(def != NULL)
-			set_irn_n(irn, pos, def);
+		if(def == NULL) {
+			ir_fprintf(stderr, "no definition found for %+F at position %d\nCopies: ", irn, pos);
+			for(irn = pset_first(copies); irn; irn = pset_next(copies)) {
+				ir_fprintf(stderr, "%+F ", irn);
+			}
+			ir_fprintf(stderr, "\n\n");
+			assert(def && "no definition found");
+		}
+		set_irn_n(irn, pos, def);
 	}
 
 	obstack_free(&obst, NULL);
 }
 
+#if 0
 /**
  * Remove phis which are not necessary.
  * During place_phi_functions() phi functions are put on the dominance
@@ -362,61 +396,73 @@ static void fix_usages(pset *copies, pset *copy_blocks, pset *phi_blocks, pset *
  */
 static void remove_odd_phis(pset *copies, pset *unused_copies)
 {
-  ir_node *irn;
-
-  for(irn = pset_first(copies); irn; irn = pset_next(copies)) {
-    if(is_Phi(irn)) {
-      int i, n;
-      int illegal = 0;
-
-      assert(sched_is_scheduled(irn) && "phi must be scheduled");
-      for(i = 0, n = get_irn_arity(irn); i < n && !illegal; ++i)
-        illegal = get_irn_n(irn, i) == NULL;
+	ir_node *irn;
 
-      if(illegal)
-        sched_remove(irn);
-    }
-  }
+	for(irn = pset_first(copies); irn; irn = pset_next(copies)) {
+		if(is_Phi(irn)) {
+			int i, n;
+			int illegal = 0;
+
+			assert(sched_is_scheduled(irn) && "phi must be scheduled");
+			for(i = 0, n = get_irn_arity(irn); i < n && !illegal; ++i)
+				illegal = get_irn_n(irn, i) == NULL;
+
+			if(illegal) {
+				for(i = 0, n = get_irn_arity(irn); i < n; ++i)
+					set_irn_n(irn, i, new_Bad());
+				sched_remove(irn);
+			}
+		}
+	}
 
-  for(irn = pset_first(unused_copies); irn; irn = pset_next(unused_copies)) {
+	for(irn = pset_first(unused_copies); irn; irn = pset_next(unused_copies)) {
+		for(i = 0, n = get_irn_arity(irn); i < n; ++i)
+			set_irn_n(irn, i, new_Bad());
 		sched_remove(irn);
 	}
 }
+#endif
 
-void be_ssa_constr_phis_ignore(dom_front_info_t *info, int n, ir_node *nodes[], pset *phis, pset *ignore_uses)
+void be_ssa_constr_phis_ignore(be_dom_front_info_t *info, be_lv_t *lv, int n, ir_node *nodes[], pset *phis, pset *ignore_uses)
 {
 	pset *irns = pset_new_ptr(n);
 	int i;
 
 	for(i = 0; i < n; ++i)
 		pset_insert_ptr(irns, nodes[i]);
-	be_ssa_constr_set_phis_ignore(info, irns, phis, ignore_uses);
+	be_ssa_constr_set_phis_ignore(info, lv, irns, phis, ignore_uses);
 	del_pset(irns);
 }
 
-void be_ssa_constr_ignore(dom_front_info_t *info, int n, ir_node *nodes[], pset *ignore_uses)
+void be_ssa_constr_ignore(be_dom_front_info_t *info, be_lv_t *lv, int n, ir_node *nodes[], pset *ignore_uses)
 {
-	be_ssa_constr_phis_ignore(info, n, nodes, NULL, ignore_uses);
+	be_ssa_constr_phis_ignore(info, lv, n, nodes, NULL, ignore_uses);
 }
 
-void be_ssa_constr(dom_front_info_t *info, int n, ir_node *nodes[])
+void be_ssa_constr(be_dom_front_info_t *info, be_lv_t *lv, int n, ir_node *nodes[])
 {
 	pset *empty_set = be_empty_set();
-	assert(pset_count(empty_set) == 0);
-	be_ssa_constr_ignore(info, n, nodes, empty_set);
+	be_ssa_constr_ignore(info, lv, n, nodes, empty_set);
 }
 
-void be_ssa_constr_set_phis_ignore(dom_front_info_t *df, pset *nodes, pset *phis, pset *ignore_uses)
+void be_ssa_constr_set_phis_ignore(be_dom_front_info_t *df, be_lv_t *lv, pset *nodes, pset *phis, pset *ignore_uses)
 {
 	int n                  = pset_count(nodes);
 	pset *blocks           = pset_new_ptr(n);
 	pset *phi_blocks       = pset_new_ptr(n);
 	int save_optimize      = get_optimize();
 	int save_normalize     = get_opt_normalize();
+	int phis_set_created   = 0;
 	FIRM_DBG_REGISTER(firm_dbg_module_t *dbg, DBG_MODULE);
 
 	ir_node *irn;
 
+	/* We need to collect the phi functions to compute their liveness. */
+	if(lv && !phis) {
+		phis_set_created = 1;
+		phis = pset_new_ptr_default();
+	}
+
 	DBG((dbg, LEVEL_1, "Introducing following copies for:\n"));
 
 	/* Fill the sets. */
@@ -427,15 +473,15 @@ void be_ssa_constr_set_phis_ignore(dom_front_info_t *df, pset *nodes, pset *phis
 	}
 
 	/*
-	* Disable optimization so that the phi functions do not
-	* disappear.
-	*/
+	 * Disable optimization so that the phi functions do not
+	 * disappear.
+	 */
 	set_optimize(0);
 	set_opt_normalize(0);
 
 	/*
-	* Place the phi functions and reroute the usages.
-	*/
+	 * Place the phi functions and reroute the usages.
+	 */
 	determine_phi_blocks(nodes, blocks, phi_blocks, df);
 	fix_usages(nodes, blocks, phi_blocks, phis, ignore_uses);
 
@@ -446,26 +492,40 @@ void be_ssa_constr_set_phis_ignore(dom_front_info_t *df, pset *nodes, pset *phis
 	del_pset(phi_blocks);
 	del_pset(blocks);
 
+	/* Recompute the liveness (if wanted) of the original nodes, the copies and the inserted phis. */
+	if(lv) {
+#if 1
+		foreach_pset(nodes, irn)
+			be_liveness_update(lv, irn);
+
+		foreach_pset(phis, irn)
+			be_liveness_introduce(lv, irn);
+#else
+		be_liveness_recompute(lv);
+#endif
+	}
+
+	/* Free the phi set of we created it. */
+	if(phis_set_created)
+		del_pset(phis);
+
 }
 
-void be_ssa_constr_set_phis(dom_front_info_t *df, pset *nodes, pset *phis)
+void be_ssa_constr_set_phis(be_dom_front_info_t *df, be_lv_t *lv, pset *nodes, pset *phis)
 {
 	pset *empty_set = be_empty_set();
-	assert(pset_count(empty_set) == 0);
-
-	be_ssa_constr_set_phis_ignore(df, nodes,phis, empty_set);
+	be_ssa_constr_set_phis_ignore(df, lv, nodes, phis, empty_set);
 }
 
-void be_ssa_constr_set_ignore(dom_front_info_t *df, pset *nodes, pset *ignore_uses)
+void be_ssa_constr_set_ignore(be_dom_front_info_t *df, be_lv_t *lv, pset *nodes, pset *ignore_uses)
 {
-	be_ssa_constr_set_phis_ignore(df, nodes, NULL, ignore_uses);
+	be_ssa_constr_set_phis_ignore(df, lv, nodes, NULL, ignore_uses);
 }
 
-void be_ssa_constr_set(dom_front_info_t *info, pset *nodes)
+void be_ssa_constr_set(be_dom_front_info_t *info, be_lv_t *lv, pset *nodes)
 {
 	pset *empty_set = be_empty_set();
-	assert(pset_count(empty_set) == 0);
-	be_ssa_constr_set_ignore(info, nodes, empty_set);
+	be_ssa_constr_set_ignore(info, lv, nodes, empty_set);
 }
 
 /*
@@ -478,13 +538,14 @@ void be_ssa_constr_set(dom_front_info_t *info, pset *nodes)
 */
 
 ir_node *insert_Perm_after(const arch_env_t *arch_env,
+						   be_lv_t *lv,
 						   const arch_register_class_t *cls,
-						   dom_front_info_t *dom_front,
+						   be_dom_front_info_t *dom_front,
 						   ir_node *pos)
 {
-	ir_node *bl                 = is_Block(pos) ? pos : get_nodes_block(pos);
-	ir_graph *irg               = get_irn_irg(bl);
-	pset *live                  = pset_new_ptr_default();
+	ir_node *bl     = is_Block(pos) ? pos : get_nodes_block(pos);
+	ir_graph *irg   = get_irn_irg(bl);
+	pset *live      = pset_new_ptr_default();
 	FIRM_DBG_REGISTER(firm_dbg_module_t *dbg, "be.node");
 
 	ir_node *curr, *irn, *perm, **nodes;
@@ -492,7 +553,7 @@ ir_node *insert_Perm_after(const arch_env_t *arch_env,
 
 	DBG((dbg, LEVEL_1, "Insert Perm after: %+F\n", pos));
 
-	if(!be_liveness_nodes_live_at(arch_env, cls, pos, live));
+	be_liveness_nodes_live_at(lv, arch_env, cls, pos, live);
 
 	n = pset_count(live);
 
@@ -529,7 +590,95 @@ ir_node *insert_Perm_after(const arch_env_t *arch_env,
 
 		copies[0] = perm_op;
 		copies[1] = proj;
-		be_ssa_constr(dom_front, 2, copies);
+
+		be_ssa_constr(dom_front, lv, 2, copies);
 	}
+
 	return perm;
 }
+
+struct _elr_closure_t {
+	struct obstack obst;
+	const be_chordal_env_t *cenv;
+};
+
+static void elr_split_walker(ir_node *bl, void *data)
+{
+	struct _elr_closure_t *c     = data;
+	const be_chordal_env_t *cenv = c->cenv;
+	const arch_env_t *aenv       = cenv->birg->main_env->arch_env;
+	be_lv_t *lv                  = cenv->birg->lv;
+	be_dom_front_info_t *dom_front = cenv->birg->dom_front;
+	be_insn_t *insn;
+	be_insn_env_t ie;
+
+	be_insn_env_init(&ie, cenv->birg, cenv->cls, &c->obst);
+
+	for(insn = be_scan_insn(&ie, sched_first(bl)); !is_Block(insn->irn); insn = be_scan_insn(&ie, insn->next_insn)) {
+		ir_node *pred = sched_prev(insn->irn);
+		if(!is_Block(pred) && !is_Phi(insn->irn))
+			insert_Perm_after(aenv, lv, cenv->cls, dom_front, insn->irn);
+	}
+}
+
+void extreme_liverange_splitting(struct _be_chordal_env_t *cenv)
+{
+	struct _elr_closure_t c;
+	be_lv_t *lv = cenv->birg->lv;
+
+	c.cenv = cenv;
+	obstack_init(&c.obst);
+	be_liveness_recompute(lv);
+	irg_block_walk_graph(cenv->irg, elr_split_walker, NULL, &c);
+	be_liveness_recompute(lv);
+	obstack_free(&c.obst, NULL);
+}
+
+static void remove_empty_block(ir_node *block, void *data) {
+	ir_graph *irg;
+	const ir_edge_t *edge, *next;
+	ir_node *node;
+	ir_node *jump = NULL;
+
+	assert(is_Block(block));
+
+	if (get_Block_n_cfgpreds(block) != 1)
+		return;
+
+	sched_foreach(block, node) {
+		if (! is_Jmp(node))
+			return;
+		if (jump != NULL) {
+			/* we should never have 2 jumps in a block */
+			assert(0 && "We should never have 2 jumps in a block");
+			return;
+		}
+		jump = node;
+	}
+
+	if (jump == NULL)
+		return;
+
+	node = get_Block_cfgpred(block, 0);
+	foreach_out_edge_safe(jump, edge, next) {
+		ir_node *block = get_edge_src_irn(edge);
+		int     pos    = get_edge_src_pos(edge);
+
+		set_irn_n(block, pos, node);
+	}
+
+	set_Block_cfgpred(block, 0, new_Bad());
+	sched_remove(jump);
+
+	irg = get_irn_irg(block);
+	set_irg_doms_inconsistent(irg);
+	set_irg_extblk_inconsistent(irg);
+	set_irg_outs_inconsistent(irg);
+}
+
+/**
+ * removes basic blocks that just contain a jump instruction
+ */
+void be_remove_empty_blocks(ir_graph *irg) {
+	irg_block_walk_graph(irg, remove_empty_block, NULL, NULL);
+}