+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;
+ double norm;
+
+ /*
+ * 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 = dfs_new(&absgraph_irg_cfg_succ, irg);
+ ef = XMALLOCZ(ir_exec_freq);
+ ef->min_non_zero = HUGE_VAL; /* initialize with a reasonable large number. */
+ freqs = ef->freqs = 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);
+ edges_assure(irg);
+
+ size = dfs_get_n_nodes(dfs);
+ mat = gs_new_matrix(size, size);
+ 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);
+ int i;
+
+ freq = set_insert_freq(freqs, bb);
+ freq->idx = idx;
+
+ /* 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);
+ }