X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;ds=sidebyside;f=ir%2Fana%2Fexecfreq.c;h=a655a76e20ef3a06526a27e620026e7d1c80f15e;hb=6f068af98daa4725d60e5d23a8f98ec2841cfa44;hp=1bcf3e6fe8d8d82afb5de1419df5b15b710f3b03;hpb=9e32d446edc895d0a6a8033352376bfc20002790;p=libfirm

diff --git a/ir/ana/execfreq.c b/ir/ana/execfreq.c
index 1bcf3e6fe..a655a76e2 100644
--- a/ir/ana/execfreq.c
+++ b/ir/ana/execfreq.c
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
+ * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
  *
  * This file is part of libFirm.
  *
@@ -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,22 +61,22 @@
 #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,type,i) for ((i)=(type)set_first((s)); (i); (i)=(type)set_next((s)))
 
-typedef struct _freq_t {
+typedef struct freq_t {
 	const ir_node    *irn;
 	int               idx;
 	double            freq;
 } freq_t;
 
 struct ir_exec_freq {
-	set *set;
+	set *freqs;
 	hook_entry_t hook;
 	double max;
 	double min_non_zero;
@@ -86,41 +84,36 @@ 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;
+	const freq_t *p = (const freq_t*) a;
+	const freq_t *q = (const freq_t*) b;
 	(void) 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 *freqs, const ir_node *irn)
 {
-	freq_t     query;
-
+	freq_t query;
 	query.irn = irn;
-	return set_find(set, &query, sizeof(query), HASH_PTR(irn));
+	return (freq_t*) set_find(freqs, &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 *freqs, const ir_node *irn)
 {
 	freq_t query;
 
 	query.irn = irn;
 	query.freq = 0.0;
 	query.idx  = -1;
-	return set_insert(set, &query, sizeof(query), HASH_PTR(irn));
+	return (freq_t*) set_insert(freqs, &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) {
-		set *freqs = ef->set;
+	if (!ef->infeasible) {
+		set *freqs = ef->freqs;
 		freq_t *freq;
 		assert(is_Block(irn));
 		freq = set_find_freq(freqs, irn);
@@ -141,8 +134,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;
@@ -152,22 +144,20 @@ solve_lgs(gs_matrix_t *mat, double *x, int size)
 	for (i = 0; i < size; ++i)
 		x[i] = init;
 
-	gs_matrix_dump(mat, size, size, stderr);
 	stat_ev_dbl("execfreq_matrix_size", size);
 	stat_ev_tim_push();
 	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();
@@ -182,23 +172,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;
+
+	if (is_Bad(pred))
+		return 0;
 
-	cur = get_loop_depth(get_irn_loop(bb)) < get_loop_depth(get_irn_loop(pred)) ? 1.0 : loop_weight;
+	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;
@@ -206,19 +217,23 @@ 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)) {
-		ir_exec_freq *ef = ctx;
-		fprintf(f, "execution frequency: %g/%lu\n", get_block_execfreq(ef, irn), get_block_execfreq_ulong(ef, irn));
-	}
+	ir_exec_freq *ef = (ir_exec_freq*) ctx;
+	if (!is_Block(irn))
+		return;
+
+	fprintf(f, "execution frequency: %g/%lu\n", get_block_execfreq(ef, irn), get_block_execfreq_ulong(ef, irn));
 }
 
 ir_exec_freq *create_execfreq(ir_graph *irg)
 {
-	ir_exec_freq *execfreq = xmalloc(sizeof(execfreq[0]));
-	memset(execfreq, 0, sizeof(execfreq[0]));
-	execfreq->set = new_set(cmp_freq, 32);
+	ir_exec_freq *execfreq = XMALLOCZ(ir_exec_freq);
+	execfreq->freqs = 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);
@@ -229,24 +244,25 @@ ir_exec_freq *create_execfreq(ir_graph *irg)
 
 void set_execfreq(ir_exec_freq *execfreq, const ir_node *block, double freq)
 {
-	freq_t *f = set_insert_freq(execfreq->set, block);
+	freq_t *f = set_insert_freq(execfreq->freqs, block);
 	f->freq = freq;
 }
 
 static void collect_blocks(ir_node *bl, void *data)
 {
-	set *freqs = data;
+	set *freqs = (set*) 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;
@@ -259,10 +275,9 @@ 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));
+	freqs = ef->freqs = new_set(cmp_freq, dfs_get_n_nodes(dfs));
 
 	/*
 	 * Populate the exec freq set.
@@ -272,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);
@@ -290,25 +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);
@@ -320,7 +353,7 @@ compute_execfreq(ir_graph * irg, double loop_weight)
 	norm = x[s->idx] != 0.0 ? 1.0 / x[s->idx] : 1.0;
 
 	ef->max = 0.0;
-	set_foreach(freqs, freq) {
+	set_foreach(freqs, freq_t*, freq) {
 		int idx = freq->idx;
 
 		/* take abs because it sometimes can be -0 in case of endless loops */
@@ -330,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);
 	}
 
@@ -343,24 +376,24 @@ compute_execfreq(ir_graph * irg, double loop_weight)
 		double l1 = 1.0;
 		double h1 = MAX_INT_FREQ;
 
-		double *fs = malloc(set_count(freqs) * sizeof(fs[0]));
+		double *fs = (double*) malloc(set_count(freqs) * sizeof(fs[0]));
 		int i, j, n = 0;
 
-		set_foreach(freqs, freq)
+		set_foreach(freqs, freq_t*, freq)
 			fs[n++] = freq->freq;
 
 		/*
 		 * 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);
 			}
 		}
@@ -375,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;
 		}
@@ -393,10 +426,9 @@ 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);
+	del_set(ef->freqs);
 	unregister_hook(hook_node_info, &ef->hook);
 	free(ef);
 }