- size_t size;
- double *matrix;
- double *rhs;
- int i;
- freq_t *freq;
- walkerdata_t wd;
- exec_freq_t *ef;
- set *freqs;
-#ifdef USE_GSL
- gsl_vector *x;
-#else
- double *x;
-#endif
-
- ef = xmalloc(sizeof(ef[0]));
- memset(ef, 0, sizeof(ef[0]));
- ef->min_non_zero = 1e50; /* initialize with a reasonable large number. */
- freqs = ef->set = new_set(cmp_freq, 32);
-
- construct_cf_backedges(irg);
-
- wd.idx = 0;
- wd.set = freqs;
-
- irg_block_walk_graph(irg, block_walker, NULL, &wd);
-
- size = set_count(freqs);
- matrix = xmalloc(size*size*sizeof(*matrix));
- memset(matrix, 0, size*size*sizeof(*matrix));
- rhs = xmalloc(size*sizeof(*rhs));
- memset(rhs, 0, size*sizeof(*rhs));
-
- set_foreach(freqs, freq) {
- ir_node *bb = (ir_node *)freq->irn;
- size_t idx = (int)get_irn_link(bb);
-
- matrix[idx * (size + 1)] = -1.0;
-
- if (bb == get_irg_start_block(irg)) {
- rhs[(int)get_irn_link(bb)] = -1.0;
- continue;
- }
-
- for(i = get_Block_n_cfgpreds(bb) - 1; i >= 0; --i) {
- ir_node *pred = get_Block_cfgpred_block(bb, i);
- size_t pred_idx = (int)get_irn_link(pred);
-
-// matrix[pred_idx + idx*size] += 1.0/(double)get_Block_n_cfg_outs(pred);
- matrix[pred_idx + idx * size] += get_cf_probability(bb, i, loop_weight);
- }
- }
-
- x = solve_lgs(matrix, rhs, size);
- if(x == NULL) {
- ef->infeasible = 1;
- return ef;
- }
-
- ef->max = MAX_INT_FREQ;
- set_foreach(freqs, freq) {
- const ir_node *bb = freq->irn;
- size_t idx = PTR_TO_INT(get_irn_link(bb));
-
-#ifdef USE_GSL
- freq->freq = ZERO(gsl_vector_get(x, idx)) ? 0.0 : gsl_vector_get(x, idx);
-#else
- freq->freq = ZERO(x[idx]) ? 0.0 : x[idx];
-#endif
-
- /* get the maximum exec freq */
- ef->max = MAX(ef->max, freq->freq);
-
- /* Get the minimum non-zero execution frequency. */
- if(freq->freq > 0.0)
- ef->min_non_zero = MIN(ef->min_non_zero, freq->freq);
- }
-
- /* compute m and b of the transformation used to convert the doubles into scaled ints */
- {
- /* double l1 = 1; */
- double h1 = MAX_INT_FREQ;
- double l2 = ef->min_non_zero;
- double h2 = ef->max;
-
- ef->m = (h1 /* - l1 */) / (h2 - l2);
- ef->b = (/* l1 * */ h2 - l2 * h1) / (h2 - l2);
- }
-
-#ifdef USE_GSL
- gsl_vector_free(x);
-#endif
- free(matrix);
-
- memset(&ef->hook, 0, sizeof(ef->hook));
- ef->hook.context = ef;
- ef->hook.hook._hook_node_info = exec_freq_node_info;
- register_hook(hook_node_info, &ef->hook);
-
- return ef;
-}
+ double loop_weight = 10.0;
+
+ assure_irg_properties(irg,
+ IR_GRAPH_PROPERTY_CONSISTENT_OUT_EDGES
+ | IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO
+ | IR_GRAPH_PROPERTY_NO_UNREACHABLE_CODE);
+
+ /* compute a DFS.
+ * using a toposort on the CFG (without back edges) will propagate
+ * the values better for the gauss/seidel iteration.
+ * => they can "flow" from start to end.
+ */
+ dfs_t *dfs = dfs_new(&absgraph_irg_cfg_succ, irg);
+
+ int size = dfs_get_n_nodes(dfs);
+ gs_matrix_t *mat = gs_new_matrix(size, size);
+
+ ir_node *end_block = get_irg_end_block(irg);
+
+ for (int idx = size - 1; idx >= 0; --idx) {
+ const ir_node *bb = (ir_node*)dfs_get_post_num_node(dfs, size-idx-1);
+
+ /* Sum of (execution frequency of predecessor * probability of cf edge) ... */
+ for (int i = get_Block_n_cfgpreds(bb) - 1; i >= 0; --i) {
+ const ir_node *pred = get_Block_cfgpred_block(bb, i);
+ int pred_idx = size - dfs_get_post_num(dfs, pred)-1;
+ double cf_probability = get_cf_probability(bb, i, loop_weight);
+ gs_matrix_set(mat, idx, pred_idx, cf_probability);
+ }
+ /* ... equals my execution frequency */
+ gs_matrix_set(mat, idx, idx, -1.0);
+
+ /* Add an edge from end to start.
+ * The problem is then an eigenvalue problem:
+ * Solve A*x = 1*x => (A-I)x = 0
+ */
+ if (bb == end_block) {
+ const ir_node *start_block = get_irg_start_block(irg);
+ int s_idx = size - dfs_get_post_num(dfs, start_block)-1;
+ gs_matrix_set(mat, s_idx, idx, 1.0);
+ }
+ }