+ 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);
+ }
+ }
+
+ /*
+ * 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.
+ */
+ ir_node *start_block = get_irg_start_block(irg);
+ int s_idx = size - dfs_get_post_num(dfs, start_block)-1;
+ const ir_node *end = get_irg_end(irg);
+ int n_keepalives = get_End_n_keepalives(end);
+ for (int idx = n_keepalives - 1; idx >= 0; --idx) {
+ ir_node *keep = get_End_keepalive(end, idx);
+ if (!is_Block(keep) || get_irn_n_edges_kind(keep, EDGE_KIND_BLOCK) > 0)
+ continue;
+
+ int k_idx = size-dfs_get_post_num(dfs, keep)-1;
+ if (k_idx > 0)
+ gs_matrix_set(mat, s_idx, k_idx, 1.0);
+ }
+
+ /* solve the system and delete the matrix */
+ double *x = XMALLOCN(double, size);
+ solve_lgs(mat, x, size);
+ gs_delete_matrix(mat);
+
+ /* compute the normalization factor.
+ * 1.0 / exec freq of start block.
+ * (note: start_idx is != 0 in strange cases involving endless loops,
+ * probably a misfeature/bug)
+ */
+ int start_idx = size-dfs_get_post_num(dfs, get_irg_start_block(irg))-1;
+ double start_freq = x[start_idx];
+ double norm = start_freq != 0.0 ? 1.0 / start_freq : 1.0;
+
+ for (int idx = size - 1; idx >= 0; --idx) {
+ ir_node *bb = (ir_node *) dfs_get_post_num_node(dfs, size - idx - 1);
+
+ /* take abs because it sometimes can be -0 in case of endless loops */
+ double freq = fabs(x[idx]) * norm;
+ set_block_execfreq(bb, freq);
+ }
+
+ dfs_free(dfs);
+
+ xfree(x);