X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Finterval_analysis.c;h=db3a3cfa308261f2d75fe48e9b854903e8a0e8fe;hb=3da5ed2598245b896255bc444aaa1768f6098cfe;hp=be7ba1e70db55607a75dd1232d3c9b2ae1557af6;hpb=381452140f095c2fdadece5d506ae5a574da1f61;p=libfirm

diff --git a/ir/ana/interval_analysis.c b/ir/ana/interval_analysis.c
index be7ba1e70..db3a3cfa3 100644
--- a/ir/ana/interval_analysis.c
+++ b/ir/ana/interval_analysis.c
@@ -29,7 +29,6 @@
 #include "debug.h"
 #include "interval_analysis.h"
 #include "execution_frequency.h"
-#include "firm_common_t.h"
 #include "set.h"
 #include "array.h"
 
@@ -49,28 +48,43 @@ DEBUG_ONLY(static firm_dbg_module_t *dbg);
 /* block is not in blocks loop. */
 /*------------------------------------------------------------------*/
 
+/** The attributes of a region. */
 typedef struct {
-	void *reg;
-	void **in_array;
-	void **op_array;
-	int n_outs;
-	int n_exc_outs;
+	void *reg;        /**< The region: A block or a loop. */
+	void **in_array;  /**< New in-array for this region, may contain NULL (to be synchronized with block inputs). */
+	void **op_array;  /**< If reg is a loop, the control flow operations leading to this loop. */
+	int n_outs;       /**< The number of out edges of this region. */
+	int n_exc_outs;   /**< The number of exception out edges of this region. */
 } region_attr;
 
+/** A Hashset containing the region attributes. */
 static set *region_attr_set = NULL;
 
-int region_attr_cmp(const void *e1, const void *e2, size_t size) {
+/**
+ * Compare two region attributes for identical regions.
+ */
+static int region_attr_cmp(const void *e1, const void *e2, size_t size)
+{
 	region_attr *ra1 = (region_attr *)e1;
 	region_attr *ra2 = (region_attr *)e2;
 	(void) size;
 	return (ra1->reg != ra2->reg);
 }
 
-static inline int attr_set_hash(region_attr *a) {
+/** Hash a region attribute (the region only). */
+static inline int attr_set_hash(region_attr *a)
+{
 	return HASH_PTR(a->reg);
 }
 
-static inline region_attr *get_region_attr(void *region) {
+/**
+ * Return the region attribute for a given region.
+ * Allocate one if not exists.
+ *
+ * @param region  the region
+ */
+static inline region_attr *get_region_attr(void *region)
+{
 	region_attr r_attr, *res;
 	r_attr.reg = region;
 
@@ -90,44 +104,61 @@ static inline region_attr *get_region_attr(void *region) {
 	return res;
 }
 
-int get_region_n_ins(void *region) {
+int get_region_n_ins(void *region)
+{
 	return ARR_LEN(get_region_attr(region)->in_array);
 }
 
-void *get_region_in(void *region, int pos) {
+void *get_region_in(void *region, int pos)
+{
 	assert(0 <= pos && pos < get_region_n_ins(region));
 	return ((get_region_attr(region)->in_array)[pos]);
 }
 
-void add_region_in(void *region, void *in) {
+void add_region_in(void *region, void *in)
+{
 	ARR_APP1(void *, get_region_attr(region)->in_array, in);
 	get_region_attr(in)->n_outs++;
 }
 
-int get_region_n_outs(void *region) {
+int get_region_n_outs(void *region)
+{
 	return get_region_attr(region)->n_outs;
 }
 
-int get_region_n_exc_outs(void *region) {
+int get_region_n_exc_outs(void *region)
+{
 	return get_region_attr(region)->n_exc_outs;
 }
 
-void inc_region_n_exc_outs(void *region) {
+static void inc_region_n_exc_outs(void *region)
+{
 	(get_region_attr(region)->n_exc_outs)++;
 }
 
-void *get_loop_cfop(void *region, int pos) {
+void *get_loop_cfop(void *region, int pos)
+{
 	assert(0 <= pos && pos < get_region_n_ins(region));
 	return ((get_region_attr(region)->op_array)[pos]);
 }
 
-static inline void add_loop_cfop(void *region, void *cfop) {
+/** Add a control flow op to a loop region. */
+static inline void add_loop_cfop(void *region, void *cfop)
+{
 	assert(cfop);
 	ARR_APP1(void *, get_region_attr(region)->op_array, cfop);
 }
 
-static inline void exc_outs(void *reg, ir_node *cfop) {
-	if (is_fragile_op(cfop) || (is_fragile_Proj(cfop)))
+/**
+ * Increase the number of exception outputs if a control flow
+ * operation (that is inside the given region) is a fragile operation.
+ *
+ * @param reg   a region
+ * @param cfop  a control flow operation leaving this region
+ */
+static inline void exc_outs(void *reg, ir_node *cfop)
+{
+	if (is_fragile_op(cfop) || is_fragile_Proj(cfop))
 		inc_region_n_exc_outs(reg);
 }
 
@@ -136,12 +167,23 @@ static inline void exc_outs(void *reg, ir_node *cfop) {
 /* Walk a loop and add all edges.  Walk inner loops by recursion. */
 /*------------------------------------------------------------------*/
 
-/* return non-zero if outer can be reached from inner via the outer loop relation */
-static int find_outer_loop(ir_loop *inner, ir_loop *outer, ir_node *b, ir_node *cfop) {
+/**
+ * Check if the loop of a given block is the outer loop of the current one.
+ * If yes, add an edge from the block to the region of the current loop.
+ *
+ * @param inner  the current (possible inner) loop
+ * @param outer  the loop of blk
+ * @param blk    a block
+ * @param cfop   the control flow op leaving blk
+ *
+ * @return  non-zero if outer can be reached from inner via the outer loop relation
+ */
+static int find_outer_loop(ir_loop *inner, ir_loop *outer, ir_node *blk, ir_node *cfop)
+{
 	if (get_loop_outer_loop(inner) == outer) {
-		add_region_in(inner, b);
+		add_region_in(inner, blk);
 		add_loop_cfop(inner, cfop);
-		exc_outs(b, cfop);
+		exc_outs(blk, cfop);
 		return 1;
 	}
 	return 0;
@@ -154,7 +196,8 @@ static int find_outer_loop(ir_loop *inner, ir_loop *outer, ir_node *b, ir_node *
  * @param blk   a block
  * @param loop  a loop
  */
-static int test_loop_nest(ir_node *blk, ir_loop *loop) {
+static int test_loop_nest(ir_node *blk, ir_loop *loop)
+{
 	int i, n_elems = get_loop_n_elements(loop);
 
 	for (i = 0; i < n_elems; ++i) {
@@ -176,12 +219,18 @@ static int test_loop_nest(ir_node *blk, ir_loop *loop) {
 }
 
 /**
+ * Check if pred is a block from an inner loop jumping via cfop to the block blk.
+ * If yes, add an edge from pred's loop to the region blk.
+
  * @param blk   a block
  * @param l     the loop of blk
  * @param pred  a predecessor block of blk
  * @param cfop  the control flow op from pred to blk
+ *
+ * @return non-zero if pred is from an inner loop
  */
-static int find_inner_loop(ir_node *blk, ir_loop *l, ir_node *pred, ir_node *cfop) {
+static int find_inner_loop(ir_node *blk, ir_loop *l, ir_node *pred, ir_node *cfop)
+{
 	int i, n_elems = get_loop_n_elements(l);
 	int found = 0;
 
@@ -189,15 +238,17 @@ static int find_inner_loop(ir_node *blk, ir_loop *l, ir_node *pred, ir_node *cfo
 		loop_element e = get_loop_element(l, i);
 		switch (*e.kind) {
 		case k_ir_node:
-			if (e.node == blk)
+			if (e.node == blk) {
+				/* stop the search if we reach blk, pred cannot be found
+				   later in the loop */
 				return 0;
+			}
 			break;
 		case k_ir_loop:
 			found = test_loop_nest(pred, e.son);
 			if (found) {
 				add_region_in(blk, e.son);
 				exc_outs(e.son, cfop);
-				//if (is_fragile_op(cfop)) inc_region_n_exc_outs(b);
 				return found;
 			}
 			break;
@@ -208,7 +259,18 @@ static int find_inner_loop(ir_node *blk, ir_loop *l, ir_node *pred, ir_node *cfo
 	return found;
 }
 
-
+/**
+ * Check if a predecessor block pred_b is from a previous loop of the
+ * block b.
+ *
+ * @param l       the loop of the block b
+ * @param pred_l  the loop of the block pred_b
+ * @param b       the block
+ * @param pred_b  the predecessor block
+ * @param cfop    the control flow node leaving pred_b for b
+ *
+ * @return non-zero if pred is from an previous loop
+ */
 static int find_previous_loop(ir_loop *l, ir_loop *pred_l, ir_node *b,
                               ir_node *pred_b, ir_node *cfop)
 {
@@ -225,9 +287,9 @@ static int find_previous_loop(ir_loop *l, ir_loop *pred_l, ir_node *b,
 			found = test_loop_nest(pred_b, k);
 			if (found) {
 				add_region_in(l, k);
-				//if (is_fragile_op(cfop)) inc_region_n_exc_outs(k);
 				exc_outs(k, cfop);
 				add_loop_cfop(l, cfop);
+				/* placeholder: the edge is in the loop region */
 				add_region_in(b, NULL);
 			}
 		}
@@ -253,7 +315,8 @@ static int find_previous_loop(ir_loop *l, ir_loop *pred_l, ir_node *b,
  *   branches directly from loop k to loop l.  Add an edge l->k.  Watch it: k must
  *   not be a direct predecessor of l in the loop tree!
  */
-static void construct_interval_block(ir_node *blk, ir_loop *l) {
+static void construct_interval_block(ir_node *blk, ir_loop *l)
+{
 	int i, n_cfgpreds;
 
 	if (blk == get_irg_start_block(current_ir_graph))
@@ -278,8 +341,15 @@ static void construct_interval_block(ir_node *blk, ir_loop *l) {
 
 		cfop = get_Block_cfgpred(blk, i);
 		if (is_Proj(cfop)) {
-			if (!is_Cond(get_Proj_pred(cfop))) {
-				cfop = skip_Proj(cfop);
+			ir_node *op = skip_Proj(cfop);
+			if (is_fragile_op(op) && get_Proj_proj(cfop) == pn_Generic_X_except) {
+				/*
+				 * Skip the Proj for the exception flow only, leave the
+				 * not exception flow Proj's intact.
+				 * If the old semantic is used (only one exception Proj) this
+				 * should lead to the same representation as before.
+				 */
+				cfop = op;
 			} else {
 				assert(get_nodes_block(cfop) == get_nodes_block(skip_Proj(cfop)));
 			}
@@ -290,34 +360,38 @@ static void construct_interval_block(ir_node *blk, ir_loop *l) {
 		assert(!is_Bad(pred) && !is_Bad(skip_Proj(get_Block_cfgpred(blk, i))));
 		pred_l = get_irn_loop(pred);
 		if (pred_l == l) {
+			/* first case: both blocks are in the same loop */
 			add_region_in(blk, pred);
-			//if (is_fragile_op(cfop)) inc_region_n_exc_outs(blk);
 			exc_outs(pred, cfop);
 		} else {
+			/* check for the second case: pred is from an inner loop */
 			int found = find_inner_loop(blk, l, pred, cfop);
 			if (!found) {
 				if (blk != get_loop_element(l, 0).node) {
 					DB((dbg, LEVEL_1, "Loop entry not at loop position 0. %+F\n", blk));
 				}
+				/* check for the third case: pred is in an outer loop */
 				found = find_outer_loop(l, pred_l, pred, cfop);
-				if (found)
-					add_region_in(blk, NULL);  /* placeholder */
-			}
-			if (!found) {
-				found = find_previous_loop(l, pred_l, blk, pred, cfop);
-			}
-			if (!found) {
-				assert(is_backedge(blk, i));
-				assert(found && "backedge from inner loop");
+				if (found) {
+					  /* placeholder: the edge is added to the loop region */
+					add_region_in(blk, NULL);
+				} else {
+					/* fourth case: pred is from the previous loop */
+					found = find_previous_loop(l, pred_l, blk, pred, cfop);
+
+					assert(found && "decomposition failed");
+				}
 			}
 		}
 
+#ifdef DEBUG_libfirm
 		if (blk != get_loop_element(l, 0).node) {
-			/* Check for improper region */
+			/* Check for improper region. But these can happen, so what? */
 			if (has_backedges(blk)) {
-				ir_fprintf(stderr, "Improper Region!!!!!! %+F\n", blk);
+				DB((dbg, LEVEL_1, "Improper Region %+F\n", blk));
 			}
 		}
+#endif
 	}
 }
 
@@ -326,7 +400,8 @@ static void construct_interval_block(ir_node *blk, ir_loop *l) {
  *
  * @param l  the cf loop
  */
-static void construct_interval_edges(ir_loop *l) {
+static void construct_interval_edges(ir_loop *l)
+{
 	int i, n_elems = get_loop_n_elements(l);
 	for (i = 0; i < n_elems; ++i) {
 		loop_element e = get_loop_element(l, i);
@@ -343,35 +418,42 @@ static void construct_interval_edges(ir_loop *l) {
 	}
 }
 
-void construct_intervals(ir_graph *irg) {
-	ir_loop *l;
+void construct_intervals(ir_graph *irg)
+{
+	ir_loop  *l;
 	ir_graph *rem = current_ir_graph;
+
 	current_ir_graph = irg;
 
 	FIRM_DBG_REGISTER(dbg, "firm.ana.interval");
 
-	if (!region_attr_set)
+	if (region_attr_set == NULL)
 		region_attr_set = new_set(region_attr_cmp, 256);
 
-	construct_cf_backedges(current_ir_graph);
+	construct_cf_backedges(irg);
 
-	l = get_irg_loop(current_ir_graph);
+	l = get_irg_loop(irg);
 
 	construct_interval_edges(l);
 
 	current_ir_graph = rem;
 }
 
-void free_intervals(void) {
-	//void **ins;
-	if (!region_attr_set) return;
-	/* @@@ mem leak
-	for (ins = (void **)pmap_first(region_in_map);
-		ins;
-		ins = (void **)pmap_next(region_in_map)) {
-		DEL_ARR_F(ins);
+void free_intervals(void)
+{
+	region_attr *res;
+
+	if (region_attr_set == NULL)
+		return;
+
+	for (res = set_first(region_attr_set);
+	     res != NULL;
+	     res = set_next(region_attr_set)) {
+		DEL_ARR_F(res->in_array);
+		if (res->op_array != NULL)
+			DEL_ARR_F(res->op_array);
 	}
-	*/
+
 	del_set(region_attr_set);
 	region_attr_set = NULL;
 }
@@ -381,19 +463,23 @@ void free_intervals(void) {
 /*                                                                  */
 /*------------------------------------------------------------------*/
 
-void dump_region_edges(FILE *F, void *reg) {
+static void dump_region_edges(FILE *F, void *reg)
+{
 	int i, n_ins = get_region_n_ins(reg);
 
-	if (is_ir_node(reg) && get_Block_n_cfgpreds((ir_node *)reg) > get_region_n_ins(reg)) {
-		for (i = n_ins; i < get_Block_n_cfgpreds((ir_node *)reg); ++i) {
-			if (is_backedge((ir_node *)reg, i))
-				fprintf (F, "backedge: { sourcename: \"");
-			else
-				fprintf (F, "edge: { sourcename: \"");
-			PRINT_NODEID(((ir_node *)reg));
-			fprintf (F, "\" targetname: \"");
-			PRINT_NODEID(get_nodes_block(skip_Proj(get_Block_cfgpred((ir_node *)reg, i))));
-			fprintf (F, "\" " BLOCK_EDGE_ATTR "}\n");
+	if (is_ir_node(reg)) {
+		ir_node *irn = reg;
+		if (get_Block_n_cfgpreds(irn) > get_region_n_ins(reg)) {
+			for (i = n_ins; i < get_Block_n_cfgpreds(irn); ++i) {
+				if (is_backedge(irn, i))
+					fprintf(F, "backedge: { sourcename: \"");
+				else
+					fprintf(F, "edge: { sourcename: \"");
+				PRINT_NODEID(irn);
+				fprintf(F, "\" targetname: \"");
+				PRINT_NODEID(get_nodes_block(skip_Proj(get_Block_cfgpred(irn, i))));
+				fprintf(F, "\" " BLOCK_EDGE_ATTR "}\n");
+			}
 		}
 	}
 
@@ -401,62 +487,64 @@ void dump_region_edges(FILE *F, void *reg) {
 		void *target = get_region_in(reg, i);
 
 		if (is_ir_node(reg)) {
-			if (get_Block_n_cfgpreds((ir_node *)reg) != get_region_n_ins(reg)) {
-				ir_printf("n_cfgpreds = %d, n_ins = %d\n %+F\n", get_Block_n_cfgpreds((ir_node *)reg), get_region_n_ins(reg), (ir_node*) reg);
+			ir_node *irn = reg;
+			if (get_Block_n_cfgpreds(irn) != get_region_n_ins(reg)) {
+				ir_printf("n_cfgpreds = %d, n_ins = %d\n %+F\n", get_Block_n_cfgpreds(irn), get_region_n_ins(reg), irn);
 			}
 		}
 
 		if ((!target || (is_ir_node(reg) && !is_ir_node(target))) && i < get_Block_n_cfgpreds((ir_node *)reg)) {
 			assert(is_ir_node(reg));
 			if (is_backedge((ir_node *)reg, i))
-				fprintf (F, "backedge: { sourcename: \"");
+				fprintf(F, "backedge: { sourcename: \"");
 			else
-				fprintf (F, "edge: { sourcename: \"");
+				fprintf(F, "edge: { sourcename: \"");
 			PRINT_NODEID(((ir_node *)reg));
-			fprintf (F, "\" targetname: \"");
+			fprintf(F, "\" targetname: \"");
 			PRINT_NODEID(get_nodes_block(skip_Proj(get_Block_cfgpred((ir_node *)reg, i))));
-			fprintf (F, "\" " BLOCK_EDGE_ATTR "}\n");
+			fprintf(F, "\" " BLOCK_EDGE_ATTR "}\n");
 
 			if (!target) continue;
 		}
 
-		fprintf (F, "edge: { sourcename: \"");
+		fprintf(F, "edge: { sourcename: \"");
 		if (is_ir_node(reg)) {
 			PRINT_NODEID(((ir_node *)reg));
 		} else {
 			PRINT_LOOPID(((ir_loop *)reg));
 		}
-		fprintf (F, "\" targetname: \"");
+		fprintf(F, "\" targetname: \"");
 		if (is_ir_node(target)) {
 			PRINT_NODEID(((ir_node *)target));
 		} else {
 			PRINT_LOOPID(((ir_loop *)target));
 		}
-		fprintf (F, "\"");
+		fprintf(F, "\"");
 		if (is_ir_node(reg) && is_fragile_op(skip_Proj(get_Block_cfgpred(reg, i))))
 			fprintf(F, EXC_CF_EDGE_ATTR);
-		fprintf (F, "}\n");
+		fprintf(F, "}\n");
 	}
 }
 
 #include "execution_frequency.h"
 
-static void dump_interval_block(FILE *F, ir_node *block) {
+static void dump_interval_block(FILE *F, ir_node *block)
+{
 	int i, fl;
 	/* This is a block. Dump a node for the block. */
-	fprintf (F, "node: {title: \""); PRINT_NODEID(block);
-	fprintf (F, "\" label: \"");
+	fprintf(F, "node: {title: \""); PRINT_NODEID(block);
+	fprintf(F, "\" label: \"");
 	if (block == get_irg_start_block(get_irn_irg(block)))
 		fprintf(F, "Start ");
 	if (block == get_irg_end_block(get_irn_irg(block)))
 		fprintf(F, "End ");
 
-	fprintf (F, "%s ", get_op_name(get_irn_op(block)));
+	fprintf(F, "%s ", get_op_name(get_irn_op(block)));
 	PRINT_NODEID(block);
 	fprintf(F, " freq: %9.4lf", get_region_exec_freq(block));
 	fprintf(F, " n_outs: %d", get_region_n_outs(block));
 	fprintf(F, " n_exc_outs: %d", get_region_n_exc_outs(block));
-	fprintf (F, "\" ");
+	fprintf(F, "\" ");
 	fprintf(F, "info1:\"");
 	if (dump_dominator_information_flag)
 		fprintf(F, "dom depth %d\n", get_Block_dom_depth(block));
@@ -475,7 +563,7 @@ static void dump_interval_block(FILE *F, ir_node *block) {
 	if (fl)
 		fprintf(F, "\n");
 
-	fprintf (F, "\"");  /* closing quote of info */
+	fprintf(F, "\"");  /* closing quote of info */
 
 	if ((block == get_irg_start_block(get_irn_irg(block))) ||
 		(block == get_irg_end_block(get_irn_irg(block)))     )
@@ -483,10 +571,11 @@ static void dump_interval_block(FILE *F, ir_node *block) {
 	else if (fl)
 		fprintf(F, " color:yellow ");
 
-	fprintf (F, "}\n");
+	fprintf(F, "}\n");
 }
 
-static void dump_interval_loop(FILE *F, ir_loop *l) {
+static void dump_interval_loop(FILE *F, ir_loop *l)
+{
 	int i, n_elems = get_loop_n_elements(l);
 
 	fprintf(F, "graph: { title: \"");
@@ -516,8 +605,10 @@ static void dump_interval_loop(FILE *F, ir_loop *l) {
 }
 
 
-void dump_interval_graph(ir_graph *irg, const char *suffix) {
-	FILE *f;
+void dump_interval_graph(ir_graph *irg, const char *suffix)
+{
+	FILE     *f;
+	ir_graph *rem;
 
 	if (!is_filtered_dump_name(get_entity_ident(get_irg_entity(irg))))
 		return;
@@ -525,10 +616,13 @@ void dump_interval_graph(ir_graph *irg, const char *suffix) {
 	f = vcg_open(irg, suffix, "-intervals");
 	dump_vcg_header(f, get_irg_dump_name(irg), NULL, NULL);
 
+	rem              = current_ir_graph;
 	current_ir_graph = irg;
 
-	dump_interval_loop(f, get_irg_loop(current_ir_graph));
+	dump_interval_loop(f, get_irg_loop(irg));
 
 	dump_vcg_footer(f);
 	fclose(f);
+
+	current_ir_graph = rem;
 }