X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Fexecfreq.c;h=41909a6843cfb7df6314d753d021db1797ce71d5;hb=bb5c6d5ce2e35c4074900017f8c8e1a4935054d0;hp=ff9ef3eff28ca2d84112cb6fe2539a208ea74232;hpb=3244e5da5a8ba71d7b43958b5dad1f938b262265;p=libfirm

diff --git a/ir/ana/execfreq.c b/ir/ana/execfreq.c
index ff9ef3eff..41909a684 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.
  *
@@ -112,6 +112,7 @@ set_insert_freq(set * set, const ir_node * irn)
 
 	query.irn = irn;
 	query.freq = 0.0;
+	query.idx  = -1;
 	return set_insert(set, &query, sizeof(query), HASH_PTR(irn));
 }
 
@@ -162,10 +163,9 @@ solve_lgs(gs_matrix_t *mat, double *x, int size)
 
 #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();
@@ -212,8 +212,7 @@ 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));
@@ -231,6 +230,12 @@ void set_execfreq(ir_exec_freq *execfreq, const ir_node *block, double freq)
 	f->freq = freq;
 }
 
+static void collect_blocks(ir_node *bl, void *data)
+{
+	set *freqs = data;
+	set_insert_freq(freqs, bl);
+}
+
 ir_exec_freq *
 compute_execfreq(ir_graph * irg, double loop_weight)
 {
@@ -251,21 +256,23 @@ 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, 32);
+	freqs = ef->set = new_set(cmp_freq, dfs_get_n_nodes(dfs));
+
+	/*
+	 * Populate the exec freq set.
+	 * The DFS cannot be used alone, since the CFG might not be connected
+	 * due to unreachable code.
+	 */
+	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);
@@ -275,15 +282,17 @@ 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) {
 			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));
 		}
+		gs_matrix_set(mat, idx, idx, -1.0);
 	}
 
+	dfs_free(dfs);
+
 	/*
 	 * Add a loop from end to start.
 	 * The problem is then an eigenvalue problem:
@@ -291,7 +300,8 @@ compute_execfreq(ir_graph * irg, double loop_weight)
 	 */
 	s = set_find_freq(freqs, get_irg_start_block(irg));
 	e = set_find_freq(freqs, get_irg_end_block(irg));
-	gs_matrix_set(mat, s->idx, e->idx, 1.0);
+	if (e->idx >= 0)
+		gs_matrix_set(mat, s->idx, e->idx, 1.0);
 
 	/* solve the system and delete the matrix */
 	solve_lgs(mat, x, size);
@@ -301,16 +311,14 @@ compute_execfreq(ir_graph * irg, double loop_weight)
 	 * compute the normalization factor.
 	 * 1.0 / exec freq of start block.
 	 */
-	assert(x[s->idx] > 0.0);
-	norm = 1.0 / x[s->idx];
+	norm = x[s->idx] != 0.0 ? 1.0 / x[s->idx] : 1.0;
 
 	ef->max = 0.0;
 	set_foreach(freqs, freq) {
 		int idx = freq->idx;
 
-		/* freq->freq = UNDEF(x[idx]) ? EPSILON : x[idx]; */
-		/* TODO: Do we need the check for zero? */
-		freq->freq = x[idx] * norm;
+		/* take abs because it sometimes can be -0 in case of endless loops */
+		freq->freq = fabs(x[idx]) * norm;
 
 		/* get the maximum exec freq */
 		ef->max = MAX(ef->max, freq->freq);