X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Fexecfreq.c;h=83c9e4c5020d6cff6b77b7294f7525c08a79794f;hb=a1e9069afa4fa1e16e2d176bcd7905d6a1ed4677;hp=fbf0033ec3c58c809ac69d39fd1c27237da40570;hpb=c060c37d0085bdec05f35bf50a51dcb3767342eb;p=libfirm

diff --git a/ir/ana/execfreq.c b/ir/ana/execfreq.c
index fbf0033ec..83c9e4c50 100644
--- a/ir/ana/execfreq.c
+++ b/ir/ana/execfreq.c
@@ -24,9 +24,7 @@
  * @date        28.05.2006
  * @version     $Id$
  */
-#ifdef HAVE_CONFIG_H
 #include "config.h"
-#endif
 
 #include <stdio.h>
 #include <string.h>
@@ -35,7 +33,6 @@
 
 #include "gaussseidel.h"
 
-#include "firm_common_t.h"
 #include "set.h"
 #include "hashptr.h"
 #include "debug.h"
@@ -49,6 +46,7 @@
 #include "irloop.h"
 #include "irgwalk.h"
 #include "iredges.h"
+#include "irouts.h"
 #include "irprintf.h"
 #include "irtools.h"
 #include "irhooks.h"
@@ -63,15 +61,15 @@
 #endif
 
 
-#define EPSILON		     1e-5
+#define EPSILON          1e-5
 #define UNDEF(x)         (fabs(x) < EPSILON)
 #define SEIDEL_TOLERANCE 1e-7
 
 #define MAX_INT_FREQ 1000000
 
-#define set_foreach(s,i) for((i)=set_first((s)); (i); (i)=set_next((s)))
+#define set_foreach(s,i) for ((i)=set_first((s)); (i); (i)=set_next((s)))
 
-typedef struct _freq_t {
+typedef struct freq_t {
 	const ir_node    *irn;
 	int               idx;
 	double            freq;
@@ -86,8 +84,7 @@ struct ir_exec_freq {
 	unsigned infeasible : 1;
 };
 
-static int
-cmp_freq(const void *a, const void *b, size_t size)
+static int cmp_freq(const void *a, const void *b, size_t size)
 {
 	const freq_t *p = a;
 	const freq_t *q = b;
@@ -96,8 +93,7 @@ cmp_freq(const void *a, const void *b, size_t size)
 	return !(p->irn == q->irn);
 }
 
-static freq_t *
-set_find_freq(set * set, const ir_node * irn)
+static freq_t *set_find_freq(set *set, const ir_node *irn)
 {
 	freq_t     query;
 
@@ -105,8 +101,7 @@ set_find_freq(set * set, const ir_node * irn)
 	return set_find(set, &query, sizeof(query), HASH_PTR(irn));
 }
 
-static freq_t *
-set_insert_freq(set * set, const ir_node * irn)
+static freq_t *set_insert_freq(set *set, const ir_node *irn)
 {
 	freq_t query;
 
@@ -116,10 +111,9 @@ set_insert_freq(set * set, const ir_node * irn)
 	return set_insert(set, &query, sizeof(query), HASH_PTR(irn));
 }
 
-double
-get_block_execfreq(const ir_exec_freq *ef, const ir_node * irn)
+double get_block_execfreq(const ir_exec_freq *ef, const ir_node *irn)
 {
-	if(!ef->infeasible) {
+	if (!ef->infeasible) {
 		set *freqs = ef->set;
 		freq_t *freq;
 		assert(is_Block(irn));
@@ -141,8 +135,7 @@ get_block_execfreq_ulong(const ir_exec_freq *ef, const ir_node *bb)
 	return res;
 }
 
-static double *
-solve_lgs(gs_matrix_t *mat, double *x, int size)
+static double *solve_lgs(gs_matrix_t *mat, double *x, int size)
 {
 	double init = 1.0 / size;
 	double dev;
@@ -157,16 +150,15 @@ solve_lgs(gs_matrix_t *mat, double *x, int size)
 	do {
 		++iter;
 		dev = gs_matrix_gauss_seidel(mat, x, size);
-	} while(fabs(dev) > SEIDEL_TOLERANCE);
+	} while (fabs(dev) > SEIDEL_TOLERANCE);
 	stat_ev_tim_pop("execfreq_seidel_time");
 	stat_ev_dbl("execfreq_seidel_iter", iter);
 
 #ifdef COMPARE_AGAINST_GAUSSJORDAN
 	{
-		double *nw = xmalloc(size * size * sizeof(*nw));
-		double *nx = xmalloc(size * sizeof(*nx));
+		double *nw = XMALLOCN(double, size * size);
+		double *nx = XMALLOCNZ(double, size);
 
-		memset(nx, 0, size * sizeof(*nx));
 		gs_matrix_export(mat, nw, size);
 
 		stat_ev_tim_push();
@@ -181,23 +173,44 @@ solve_lgs(gs_matrix_t *mat, double *x, int size)
 	return x;
 }
 
-static double
-get_cf_probability(ir_node *bb, int pos, double loop_weight)
+/*
+ * Determine probability that predecessor pos takes this cf edge.
+ */
+static double get_cf_probability(ir_node *bb, int pos, double loop_weight)
 {
-	double  sum = 0.0;
-	double  cur = 0.0;
-	const ir_node *pred = get_Block_cfgpred_block(bb, pos);
-	const ir_loop *pred_loop = get_irn_loop(pred);
-	int pred_depth = get_loop_depth(pred_loop);
+	double           sum = 0.0;
+	double           cur = 1.0;
+	double           inv_loop_weight = 1./loop_weight;
+	const ir_node   *pred = get_Block_cfgpred_block(bb, pos);
+	const ir_loop   *pred_loop;
+	int              pred_depth;
 	const ir_edge_t *edge;
+	const ir_loop   *loop;
+	int              depth;
+	int              d;
 
-	cur = get_loop_depth(get_irn_loop(bb)) < get_loop_depth(get_irn_loop(pred)) ? 1.0 : loop_weight;
+	if (is_Bad(pred))
+		return 0;
+
+	loop       = get_irn_loop(bb);
+	depth      = get_loop_depth(loop);
+	pred_loop  = get_irn_loop(pred);
+	pred_depth = get_loop_depth(pred_loop);
+
+	for (d = depth; d < pred_depth; ++d) {
+		cur *= inv_loop_weight;
+	}
 
 	foreach_block_succ(pred, edge) {
-		const ir_node *block = get_edge_src_irn(edge);
-		const ir_loop *loop = get_irn_loop(block);
-		int depth = get_loop_depth(loop);
-		sum += depth < pred_depth ? 1.0 : loop_weight;
+		const ir_node *succ       = get_edge_src_irn(edge);
+		const ir_loop *succ_loop  = get_irn_loop(succ);
+		int            succ_depth = get_loop_depth(succ_loop);
+
+		double         fac = 1.0;
+		for (d = succ_depth; d < pred_depth; ++d) {
+			fac *= inv_loop_weight;
+		}
+		sum += fac;
 	}
 
 	return cur/sum;
@@ -205,7 +218,7 @@ get_cf_probability(ir_node *bb, int pos, double loop_weight)
 
 static void exec_freq_node_info(void *ctx, FILE *f, const ir_node *irn)
 {
-	if(is_Block(irn)) {
+	if (is_Block(irn)) {
 		ir_exec_freq *ef = ctx;
 		fprintf(f, "execution frequency: %g/%lu\n", get_block_execfreq(ef, irn), get_block_execfreq_ulong(ef, irn));
 	}
@@ -213,11 +226,14 @@ static void exec_freq_node_info(void *ctx, FILE *f, const ir_node *irn)
 
 ir_exec_freq *create_execfreq(ir_graph *irg)
 {
-	ir_exec_freq *execfreq = xmalloc(sizeof(execfreq[0]));
-	memset(execfreq, 0, sizeof(execfreq[0]));
+	ir_exec_freq *execfreq = XMALLOCZ(ir_exec_freq);
 	execfreq->set = new_set(cmp_freq, 32);
 
 	memset(&execfreq->hook, 0, sizeof(execfreq->hook));
+
+	// set reasonable values to convert double execfreq to ulong execfreq
+	execfreq->m = 1.0;
+
 	execfreq->hook.context = execfreq;
 	execfreq->hook.hook._hook_node_info = exec_freq_node_info;
 	register_hook(hook_node_info, &execfreq->hook);
@@ -238,14 +254,15 @@ static void collect_blocks(ir_node *bl, void *data)
 	set_insert_freq(freqs, bl);
 }
 
-ir_exec_freq *
-compute_execfreq(ir_graph * irg, double loop_weight)
+ir_exec_freq *compute_execfreq(ir_graph *irg, double loop_weight)
 {
 	gs_matrix_t  *mat;
 	int           size;
+	int           n_keepalives;
 	int           idx;
 	freq_t       *freq, *s, *e;
 	ir_exec_freq *ef;
+	ir_node      *end = get_irg_end(irg);
 	set          *freqs;
 	dfs_t        *dfs;
 	double       *x;
@@ -258,8 +275,7 @@ compute_execfreq(ir_graph * irg, double loop_weight)
 	 * => they can "flow" from start to end.
 	 */
 	dfs = dfs_new(&absgraph_irg_cfg_succ, irg);
-	ef = xmalloc(sizeof(ef[0]));
-	memset(ef, 0, sizeof(ef[0]));
+	ef = XMALLOCZ(ir_exec_freq);
 	ef->min_non_zero = HUGE_VAL; /* initialize with a reasonable large number. */
 	freqs = ef->set = new_set(cmp_freq, dfs_get_n_nodes(dfs));
 
@@ -271,15 +287,11 @@ compute_execfreq(ir_graph * irg, double loop_weight)
 	irg_block_walk_graph(irg, collect_blocks, NULL, freqs);
 
 	construct_cf_backedges(irg);
-	/* TODO: edges are corrupt for EDGE_KIND_BLOCK after the local optimize
-		 graph phase merges blocks in the x86 backend */
-	edges_deactivate(irg);
-	edges_activate(irg);
-	/* edges_assure(irg); */
+	edges_assure(irg);
 
 	size = dfs_get_n_nodes(dfs);
 	mat  = gs_new_matrix(size, size);
-	x    = xmalloc(size*sizeof(*x));
+	x    = XMALLOCN(double, size);
 
 	for (idx = dfs_get_n_nodes(dfs) - 1; idx >= 0; --idx) {
 		ir_node *bb = (ir_node *) dfs_get_post_num_node(dfs, size - idx - 1);
@@ -289,27 +301,47 @@ compute_execfreq(ir_graph * irg, double loop_weight)
 		freq = set_insert_freq(freqs, bb);
 		freq->idx = idx;
 
-		gs_matrix_set(mat, idx, idx, -1.0);
-		for(i = get_Block_n_cfgpreds(bb) - 1; i >= 0; --i) {
+		/* Sum of (execution frequency of predecessor * probability of cf edge) ... */
+		for (i = get_Block_n_cfgpreds(bb) - 1; i >= 0; --i) {
 			ir_node *pred = get_Block_cfgpred_block(bb, i);
 			int pred_idx  = size - dfs_get_post_num(dfs, pred) - 1;
 
 			gs_matrix_set(mat, idx, pred_idx, get_cf_probability(bb, i, loop_weight));
 		}
+		/* ... equals my execution frequency */
+		gs_matrix_set(mat, idx, idx, -1.0);
 	}
 
 	dfs_free(dfs);
 
 	/*
-	 * Add a loop from end to start.
+	 * Add an edge from end to start.
 	 * The problem is then an eigenvalue problem:
 	 * Solve A*x = 1*x => (A-I)x = 0
 	 */
 	s = set_find_freq(freqs, get_irg_start_block(irg));
+
 	e = set_find_freq(freqs, get_irg_end_block(irg));
 	if (e->idx >= 0)
 		gs_matrix_set(mat, s->idx, e->idx, 1.0);
 
+	/*
+	 * Also add an edge for each kept block to start.
+	 *
+	 * This avoid strange results for e.g. an irg containing a exit()-call
+	 * which block has no cfg successor.
+	 */
+	n_keepalives = get_End_n_keepalives(end);
+	for (idx = n_keepalives - 1; idx >= 0; --idx) {
+		ir_node *keep = get_End_keepalive(end, idx);
+
+		if (is_Block(keep) && get_Block_n_cfg_outs(keep) == 0) {
+			freq_t *k = set_find_freq(freqs, keep);
+			if (k->idx >= 0)
+				gs_matrix_set(mat, s->idx, k->idx, 1.0);
+		}
+	}
+
 	/* solve the system and delete the matrix */
 	solve_lgs(mat, x, size);
 	gs_delete_matrix(mat);
@@ -331,7 +363,7 @@ compute_execfreq(ir_graph * irg, double loop_weight)
 		ef->max = MAX(ef->max, freq->freq);
 
 		/* Get the minimum non-zero execution frequency. */
-		if(freq->freq > 0.0)
+		if (freq->freq > 0.0)
 			ef->min_non_zero = MIN(ef->min_non_zero, freq->freq);
 	}
 
@@ -354,14 +386,14 @@ compute_execfreq(ir_graph * irg, double loop_weight)
 		 * find the smallest difference of the execution frequencies
 		 * we try to ressolve it with 1 integer.
 		 */
-		for(i = 0; i < n; ++i) {
-			if(fs[i] <= 0.0)
+		for (i = 0; i < n; ++i) {
+			if (fs[i] <= 0.0)
 				continue;
 
-			for(j = i + 1; j < n; ++j) {
+			for (j = i + 1; j < n; ++j) {
 				double diff = fabs(fs[i] - fs[j]);
 
-				if(!UNDEF(diff))
+				if (!UNDEF(diff))
 					smallest_diff = MIN(diff, smallest_diff);
 			}
 		}
@@ -376,7 +408,7 @@ compute_execfreq(ir_graph * irg, double loop_weight)
 		 * if the slope is so high that the largest integer would be larger than MAX_INT_FREQ
 		 * set the largest int freq to that upper limit and recompute the translation function
 		 */
-		if(ef->m * h2 + ef->b > MAX_INT_FREQ) {
+		if (ef->m * h2 + ef->b > MAX_INT_FREQ) {
 			ef->m = (h1 - l1) / (h2 - l2);
 			ef->b = l1 - ef->m * l2;
 		}
@@ -394,8 +426,7 @@ compute_execfreq(ir_graph * irg, double loop_weight)
 	return ef;
 }
 
-void
-free_execfreq(ir_exec_freq *ef)
+void free_execfreq(ir_exec_freq *ef)
 {
 	del_set(ef->set);
 	unregister_hook(hook_node_info, &ef->hook);