X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbechordal.c;h=0bfd1ca474698a8a9425e3a03b11d6b0b8cd12bf;hb=e03dd955762d16d38fdec0e2d7c24bf36d0ecc2e;hp=a033515b68c593a8ca7ab7f8aea2d147ccea8bf4;hpb=fffce24ca3bd902557240873edd936588b3cd265;p=libfirm

diff --git a/ir/be/bechordal.c b/ir/be/bechordal.c
index a033515b6..0bfd1ca47 100644
--- a/ir/be/bechordal.c
+++ b/ir/be/bechordal.c
@@ -38,6 +38,7 @@
 #include "bechordal_t.h"
 #include "bechordal_draw.h"
 
+#define DBG_LEVEL SET_LEVEL_0
 #define NO_COLOR (-1)
 
 #undef DUMP_INTERVALS
@@ -49,19 +50,16 @@
 #endif
 
 
-#ifdef DEBUG_libfirm
 #include "fourcc.h"
 
 /* Make a fourcc for border checking. */
 #define BORDER_FOURCC				FOURCC('B', 'O', 'R', 'D')
 
-#endif /* DEBUG_libfirm */
-
 static firm_dbg_module_t *dbg;
 
 #ifdef BUILD_GRAPH
 
-#define IF_EDGE_HASH(e) ((e)->src)
+#define IF_EDGE_HASH(e) ((e)->src ^ (e)->tgt)
 #define IF_NODE_HASH(n) ((n)->nnr)
 
 static int if_edge_cmp(const void *p1, const void *p2, size_t size)
@@ -177,6 +175,23 @@ static void dump_ifg(const be_chordal_env_t *env)
 
 #endif /* BUILD_GRAPH */
 
+static void check_border_list(struct list_head *head)
+{
+  border_t *x;
+  list_for_each_entry(border_t, x, head, list) {
+    assert(x->magic == BORDER_FOURCC);
+  }
+}
+
+static void check_heads(be_chordal_env_t *env)
+{
+  pmap_entry *ent;
+  for(ent = pmap_first(env->border_heads); ent; ent = pmap_next(env->border_heads)) {
+    /* ir_printf("checking border list of block %+F\n", ent->key); */
+    check_border_list(ent->value);
+  }
+}
+
 
 /**
  * Add an interval border to the list of a block's list
@@ -203,6 +218,7 @@ static INLINE border_t *border_add(be_chordal_env_t *env, struct list_head *head
 
 		/* also allocate the def and tie it to the use. */
 		def = obstack_alloc(&env->obst, sizeof(*def));
+    memset(def, 0, sizeof(*def));
 		b->other_end = def;
 		def->other_end = b;
 
@@ -213,10 +229,8 @@ static INLINE border_t *border_add(be_chordal_env_t *env, struct list_head *head
 		 */
 		set_irn_link(irn, def);
 
-#ifdef DEBUG_libfirm
 		b->magic = BORDER_FOURCC;
 		def->magic = BORDER_FOURCC;
-#endif
 	}
 
 	/*
@@ -227,9 +241,7 @@ static INLINE border_t *border_add(be_chordal_env_t *env, struct list_head *head
 	else {
 		b = get_irn_link(irn);
 
-#ifdef DEBUG_libfirm
 		assert(b && b->magic == BORDER_FOURCC && "Illegal border encountered");
-#endif
 	}
 
 	b->pressure = pressure;
@@ -241,9 +253,16 @@ static INLINE border_t *border_add(be_chordal_env_t *env, struct list_head *head
 	DBG((dbg, LEVEL_5, "\t\t%s adding %+F, step: %d\n",
 				is_def ? "def" : "use", irn, step));
 
+
 	return b;
 }
 
+static INLINE int has_reg_class(const be_chordal_env_t *env, const ir_node *irn)
+{
+  return arch_irn_has_reg_class(env->session_env->main_env->arch_env,
+			irn, arch_pos_make_out(0), env->cls);
+}
+
 /**
  * Annotate the register pressure to the nodes and compute
  * the liveness intervals.
@@ -270,7 +289,6 @@ static void pressure(ir_node *block, void *env_ptr)
 	struct list_head *head;
 	pset *live_in = put_live_in(block, pset_new_ptr_default());
 	pset *live_end = put_live_end(block, pset_new_ptr_default());
-	const arch_register_class_t *cls = env->cls;
 
 	DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
 	bitset_clear_all(live);
@@ -278,6 +296,7 @@ static void pressure(ir_node *block, void *env_ptr)
 	/* Set up the border list in the block info */
 	head = obstack_alloc(&env->obst, sizeof(*head));
 	INIT_LIST_HEAD(head);
+  assert(pmap_get(env->border_heads, block) == NULL);
 	pmap_insert(env->border_heads, block, head);
 
 	/*
@@ -285,10 +304,11 @@ static void pressure(ir_node *block, void *env_ptr)
 	 * They are necessary to build up real intervals.
 	 */
 	for(irn = pset_first(live_end); irn; irn = pset_next(live_end)) {
-		DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_graph_nr(irn)));
-		bitset_set(live, get_irn_graph_nr(irn));
-		if(arch_irn_has_reg_class(env->arch_env, irn, 0, cls))
+		if(has_reg_class(env, irn)) {
+			DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_graph_nr(irn)));
+			bitset_set(live, get_irn_graph_nr(irn));
 			border_use(irn, step, 0);
+		}
 	}
 	++step;
 
@@ -304,7 +324,7 @@ static void pressure(ir_node *block, void *env_ptr)
 	     * If the node defines some value, which can put into a
 	     * register of the current class, make a border for it.
 	     */
-		if(arch_irn_has_reg_class(env->arch_env, irn, 0, cls)) {
+		if(has_reg_class(env, irn)) {
 			bitset_pos_t elm;
 			int nr = get_irn_graph_nr(irn);
 
@@ -313,7 +333,7 @@ static void pressure(ir_node *block, void *env_ptr)
 
 #ifdef BUILD_GRAPH
 			bitset_foreach(live, elm)
-			add_if(env, nr, (int) elm);
+				add_if(env, nr, (int) elm);
 #endif
 		}
 
@@ -324,7 +344,7 @@ static void pressure(ir_node *block, void *env_ptr)
 			for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
 				ir_node *op = get_irn_n(irn, i);
 
-				if(arch_irn_has_reg_class(env->arch_env, op, 0, cls)) {
+				if(has_reg_class(env, op)) {
 					int nr = get_irn_graph_nr(op);
 
 					DBG((dbg, LEVEL_4, "\t\tpos: %d, use: %+F\n", i, op));
@@ -343,7 +363,7 @@ static void pressure(ir_node *block, void *env_ptr)
 	 * Add initial defs for all values live in.
 	 */
 	for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
-		if(arch_irn_has_reg_class(env->arch_env, irn, 0, cls)) {
+		if(has_reg_class(env, irn)) {
 
 			/* Mark the value live in. */
 			bitset_set(live, get_irn_graph_nr(irn));
@@ -353,22 +373,18 @@ static void pressure(ir_node *block, void *env_ptr)
 		}
 	}
 
-    del_pset(live_in);
-    del_pset(live_end);
+
+  del_pset(live_in);
+  del_pset(live_end);
 }
 
 static void assign(ir_node *block, void *env_ptr)
 {
 	be_chordal_env_t *env = env_ptr;
-	struct obstack *obst = &env->obst;
 	bitset_t *live = env->live;
 	bitset_t *colors = env->colors;
 	bitset_t *in_colors = env->in_colors;
-	const arch_register_class_t *cls = env->cls;
-
-	/* Mark the obstack level and allocate the temporary tmp_colors */
-	void *obstack_level = obstack_base(obst);
-	/*bitset_t *tmp_colors = bitset_obstack_alloc(obst, env->colors_n);*/
+	const arch_env_t *arch_env = env->session_env->main_env->arch_env;
 
 	const ir_node *irn;
 	border_t *b;
@@ -392,11 +408,11 @@ static void assign(ir_node *block, void *env_ptr)
 	 * allocated before), we have to mark their colors as used also.
 	 */
 	for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
-		if(arch_irn_has_reg_class(env->arch_env, irn, 0, cls)) {
-      const arch_register_t *reg = arch_get_irn_register(env->arch_env, irn, 0);
-      int col;
+		if(has_reg_class(env, irn)) {
+			const arch_register_t *reg = arch_get_irn_register(arch_env, irn, 0);
+			int col;
 
-      assert(reg && "Node must have been assigned a register");
+			assert(reg && "Node must have been assigned a register");
 			col = arch_register_get_index(reg);
 
 			/* Mark the color of the live in value as used. */
@@ -422,34 +438,33 @@ static void assign(ir_node *block, void *env_ptr)
 		 * color.
 		 */
 		if(b->is_def && !is_live_in(block, irn)) {
-      const arch_register_t *reg;
+			const arch_register_t *reg;
 			int col = NO_COLOR;
 
 			DBG((dbg, LEVEL_4, "\tcolors in use: %b\n", colors));
 
-      col = bitset_next_clear(colors, 0);
-      reg = arch_register_for_index(env->cls, col);
+			col = bitset_next_clear(colors, 0);
+			reg = arch_register_for_index(env->cls, col);
 
-      assert(arch_get_irn_register(env->arch_env, irn, 0) == NULL
-          && "This node must not have been assigned a register yet");
+			assert(arch_get_irn_register(arch_env, irn, 0) == NULL && "This node must not have been assigned a register yet");
 			assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
 
 			bitset_set(colors, col);
 			bitset_set(live, nr);
 
-			arch_set_irn_register(env->arch_env, irn, 0, reg);
+			arch_set_irn_register(arch_env, irn, 0, reg);
 			DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n",
             arch_register_get_name(reg), col, irn));
 		}
 
 		/* Clear the color upon a use. */
 		else if(!b->is_def) {
-      const arch_register_t *reg = arch_get_irn_register(env->arch_env, irn, 0);
+			const arch_register_t *reg = arch_get_irn_register(arch_env, irn, 0);
 			int col;
 
-      assert(reg && "Register must have been assigned");
+			assert(reg && "Register must have been assigned");
 
-      col = arch_register_get_index(reg);
+			col = arch_register_get_index(reg);
 			assert(bitset_is_set(live, nr) && "Cannot have a non live use");
 
 			bitset_clear(colors, col);
@@ -457,22 +472,20 @@ static void assign(ir_node *block, void *env_ptr)
 		}
 	}
 
-	/* Free the auxillary data on the obstack. */
-	obstack_free(obst, obstack_level);
-
-  del_pset(live_in);
+	del_pset(live_in);
 }
 
 void be_ra_chordal_init(void)
 {
 	dbg = firm_dbg_register(DBG_CHORDAL);
-	firm_dbg_set_mask(dbg, 0);
+	firm_dbg_set_mask(dbg, DBG_LEVEL);
 }
 
-be_chordal_env_t *be_ra_chordal(ir_graph *irg,
-    const arch_env_t *arch_env,
+be_chordal_env_t *be_ra_chordal(
+    const be_main_session_env_t *session,
     const arch_register_class_t *cls)
 {
+  ir_graph *irg = session->irg;
 	int node_count = get_graph_node_count(irg);
 	int colors_n = arch_register_class_n_regs(cls);
 	be_chordal_env_t *env = malloc(sizeof(*env));
@@ -487,13 +500,12 @@ be_chordal_env_t *be_ra_chordal(ir_graph *irg,
 	env->nodes = new_set(if_node_cmp, node_count);
 #endif
 
+  env->session_env = session;
 	env->live = bitset_obstack_alloc(&env->obst, node_count);
 	env->colors = bitset_obstack_alloc(&env->obst, colors_n);
 	env->in_colors = bitset_obstack_alloc(&env->obst, colors_n);
 	env->colors_n = colors_n;
 	env->cls = cls;
-	env->arch_env = arch_env;
-	env->irg = irg;
 	env->border_heads = pmap_create();
 
 	/* First, determine the pressure */
@@ -517,7 +529,7 @@ be_chordal_env_t *be_ra_chordal(ir_graph *irg,
 		ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", cls->name, irg);
     	plotter = new_plotter_ps(buf);
 
-    	draw_interval_tree(&draw_chordal_def_opts, env, plotter, arch_env, cls);
+    	draw_interval_tree(&draw_chordal_def_opts, env, plotter, env->session_env->main_env->arch_env, cls);
     	plotter_free(plotter);
 	}
 #endif
@@ -525,14 +537,12 @@ be_chordal_env_t *be_ra_chordal(ir_graph *irg,
 }
 
 void be_ra_chordal_check(be_chordal_env_t *chordal_env) {
-	const arch_env_t *arch_env;
+	const arch_env_t *arch_env = chordal_env->session_env->main_env->arch_env;
 	struct obstack ob;
 	pmap_entry *pme;
 	ir_node **nodes, *n1, *n2;
 	int i, o;
 
-	arch_env = chordal_env->arch_env;
-
 	/* Collect all irns */
 	obstack_init(&ob);
 	pmap_foreach(chordal_env->border_heads, pme) {
@@ -551,17 +561,22 @@ void be_ra_chordal_check(be_chordal_env_t *chordal_env) {
 		const arch_register_t *n1_reg, *n2_reg;
 
 		n1_reg = arch_get_irn_register(arch_env, n1, 0);
-		assert(arch_reg_is_allocatable(arch_env, n1, arch_pos_make_out(0), n1_reg) && "Register constraint does not hold");
-
+		if (!arch_reg_is_allocatable(arch_env, n1, arch_pos_make_out(0), n1_reg)) {
+			DBG((dbg, 0, "Register assigned to %+F is not allowed\n", n1));
+			assert(0 && "Register constraint does not hold");
+		}
 		for (o = i+1, n2 = nodes[o]; n2; n2 = nodes[++o]) {
 			n2_reg = arch_get_irn_register(arch_env, n2, 0);
-			assert(!(nodes_interfere(chordal_env, n1, n2) && n1_reg == n2_reg) && "Interfering values have the same color!");
+			if (nodes_interfere(chordal_env, n1, n2) && n1_reg == n2_reg) {
+				DBG((dbg, 0, "Values %+F and %+F interfere and have the same register assigned\n", n1, n2));
+				assert(0 && "Interfering values have the same color!");
+			}
 		}
 	}
 	obstack_free(&ob, NULL);
 }
 
-/* TODO #ifdef BUILD_GRAPH --> faster version of checker with edges */
+/* BETTER #ifdef BUILD_GRAPH --> faster version of checker with edges */
 
 void be_ra_chordal_done(be_chordal_env_t *env)
 {
@@ -580,6 +595,8 @@ void be_ra_chordal_done(be_chordal_env_t *env)
 	free(env);
 }
 
+
+
 int nodes_interfere(const be_chordal_env_t *env, const ir_node *a, const ir_node *b)
 {
 #ifdef BUILD_GRAPH
@@ -600,3 +617,63 @@ set *be_ra_get_ifg_nodes(const be_chordal_env_t *env) {
 }
 
 #endif
+
+typedef struct {
+	const be_main_session_env_t *env;
+	const arch_register_class_t *cls;
+} check_pressure_info_t;
+
+
+static int check_pressure_has_class(const check_pressure_info_t *i, const ir_node *irn)
+{
+  return arch_irn_has_reg_class(i->env->main_env->arch_env,
+      irn, arch_pos_make_out(0), i->cls);
+}
+
+static void check_pressure_walker(ir_node *bl, void *data)
+{
+	check_pressure_info_t *info = data;
+	int n_regs = arch_register_class_n_regs(info->cls);
+
+	pset *live = pset_new_ptr_default();
+	int step = 0;
+	ir_node *irn;
+  irn_live_t *li;
+
+  live_foreach(bl, li) {
+    if(live_is_end(li) && check_pressure_has_class(info, li->irn)) {
+      ir_node *irn = (ir_node *) li->irn;
+      pset_insert_ptr(live, irn);
+    }
+  }
+
+	sched_foreach_reverse(bl, irn) {
+		int i, n;
+		int pressure = pset_count(live);
+
+		if(pressure > n_regs) {
+			ir_node *x;
+			ir_printf("%+10F@%+10F: pressure to high: %d\n", bl, irn, pressure);
+			for(x = pset_first(live); x; x = pset_next(live))
+				ir_printf("\t%+10F\n", x);
+		}
+
+		if(check_pressure_has_class(info, irn))
+			pset_remove_ptr(live, irn);
+
+		for(i = 0, n = get_irn_arity(irn); i < n; i++) {
+			ir_node *op = get_irn_n(irn, i);
+			if(check_pressure_has_class(info, op) && !is_Phi(irn))
+				pset_insert_ptr(live, op);
+		}
+		step++;
+	}
+}
+
+void be_check_pressure(const be_main_session_env_t *env, const arch_register_class_t *cls)
+{
+	check_pressure_info_t i;
+	i.env = env;
+	i.cls = cls;
+	irg_block_walk_graph(env->irg, check_pressure_walker, NULL, &i);
+}