3 * File name: ir/ana/execution_frequency.c
4 * Purpose: Compute an estimate of basic block executions.
5 * Author: Goetz Lindenmaier
9 * Copyright: (c) 2004 Universität Karlsruhe
10 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
16 #include "execution_frequency.h"
18 #include "firm_common_t.h"
27 #include "interval_analysis.h"
29 /*------------------------------------------------------------------*/
30 /* A hashmap mapping the frequency to block and loop nodes. Block
31 * and loop nodes are regions. */
32 /*------------------------------------------------------------------*/
40 /* We use this set for all nodes in all irgraphs. */
41 static set *exec_freq_set = NULL;
43 static int exec_freq_cmp(const void *e1, const void *e2, size_t size) {
44 reg_exec_freq *ef1 = (reg_exec_freq *)e1;
45 reg_exec_freq *ef2 = (reg_exec_freq *)e2;
46 return (ef1->reg != ef2->reg);
49 static INLINE unsigned int exec_freq_hash(void *e) {
50 unsigned int v = (unsigned int) ((reg_exec_freq *)e)->reg;
54 static INLINE void set_region_exec_freq(void *reg, double freq) {
58 set_insert(exec_freq_set, &ef, sizeof(ef), exec_freq_hash(&ef));
61 INLINE double get_region_exec_freq(void *reg) {
62 reg_exec_freq ef, *found;
64 assert(exec_freq_set);
66 found = set_find(exec_freq_set, &ef, sizeof(ef), exec_freq_hash(&ef));
68 /* Not found if information is invalid. */
75 /* Returns the number of times the block is executed. */
76 double get_Block_exec_freq(ir_node *b) {
77 return get_region_exec_freq((void *)b);
80 double get_irn_exec_freq(ir_node *n) {
81 if (!is_Block(n)) n = get_nodes_block(n);
82 return get_Block_exec_freq(n);
86 /*------------------------------------------------------------------*/
87 /* A algorithm that precomputes whether Conds lead to an exception.
88 * Computes a field for all Projs from Conds that says the following:
89 * - The Proj projs from a normal dual Cond with probability 50:50
90 * - This Proj of the Cond leads to an exception, i.e., a raise node.
91 * It is taken with exception probability.
92 * - The Proj of the Cond avoids an exception. It is taken with
93 * 1 - exception probability. */
94 /*------------------------------------------------------------------*/
101 Cond_prob_avoid_exception,
102 Cond_prob_exception_taken,
103 Cond_prob_was_exception_taken,
106 static int just_passed_a_Raise = 0;
107 static ir_node *Cond_list = NULL;
109 /* We do not use an extra set, as Projs are not yet in the existing one. */
110 void set_ProjX_probability(ir_node *n, Cond_prob prob) {
114 set_insert(exec_freq_set, &ef, sizeof(ef), exec_freq_hash(&ef));
117 Cond_prob get_ProjX_probability(ir_node *n) {
118 reg_exec_freq ef, *found;
121 found = set_find(exec_freq_set, &ef, sizeof(ef), exec_freq_hash(&ef));
124 return (Cond_prob)found->prob;
126 return Cond_prob_none;
129 /* A walker that only visits the nodes we want to see. */
132 my_irg_walk_2_both(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void * env) {
134 set_irn_visited(node, current_ir_graph->visited);
138 if (node->op != op_Block) {
140 if (node->op == op_Proj)
141 pred = get_irn_n(node, 0);
143 pred = get_irn_n(node, -1);
144 if (pred->visited < current_ir_graph->visited)
145 my_irg_walk_2_both(pred, pre, post, env);
149 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
150 ir_node *pred = get_irn_n(node, i);
151 if (pred->visited < current_ir_graph->visited)
152 my_irg_walk_2_both(pred, pre, post, env);
156 if (node->op == op_End) {
157 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
158 ir_node *pred = get_irn_n(node, i);
159 if ((pred->op == op_Block) && (pred->visited < current_ir_graph->visited))
160 my_irg_walk_2_both(pred, pre, post, env);
166 static void my_irg_walk_current_graph(irg_walk_func *pre, irg_walk_func *post, void *env) {
167 inc_irg_visited(current_ir_graph);
168 my_irg_walk_2_both(get_irg_end(current_ir_graph), pre, post, env);
172 static void walk_pre(ir_node *n, void *env) {
174 if (get_irn_op(n) == op_Raise)
175 just_passed_a_Raise = 1;
177 if ( (get_irn_op(n) == op_Proj)
178 && (get_irn_op(get_Proj_pred(n)) == op_Cond)
179 && (just_passed_a_Raise)) {
180 ir_node *c = get_Proj_pred(n);
182 /* If we already visited the other Proj, and it also leads to a Raise,
183 we are in the middle of something. Continue searching. */
184 assert(get_irn_n_outs(c) == 2 && "encountered a switch cond");
185 ir_node *other_proj = get_irn_out(c, 0);
186 if (other_proj == n) other_proj = get_irn_out(c, 1);
187 if (get_ProjX_probability(other_proj) == Cond_prob_exception_taken) {
188 set_ProjX_probability(other_proj, Cond_prob_was_exception_taken);
189 /* Keep searching for the Proj, so keep just_passed_a_Raise. */
191 set_ProjX_probability(n, Cond_prob_exception_taken);
192 just_passed_a_Raise = 0;
196 if (get_irn_op(n) == op_Cond) {
197 set_irn_link(n, Cond_list);
202 static void walk_post(ir_node *n, void *env) {
204 if (get_irn_op(n) == op_Raise)
205 just_passed_a_Raise = 0;
207 if ( (get_irn_op(n) == op_Proj)
208 && (get_irn_op(get_Proj_pred(n)) == op_Cond)
209 && ((get_ProjX_probability(n) == Cond_prob_exception_taken) ||
210 (get_ProjX_probability(n) == Cond_prob_was_exception_taken) )) {
211 just_passed_a_Raise = 1;
215 /** Precompute which Conds test for an exception.
217 * Operates on current_ir_graph. */
218 void precompute_cond_evaluation(void) {
221 compute_outs(current_ir_graph);
223 just_passed_a_Raise = 0;
225 my_irg_walk_current_graph(walk_pre, walk_post, NULL);
227 for (c = Cond_list; c; c = get_irn_link(c)) {
228 assert(get_irn_n_outs(c) == 2 && "encountered a switch cond");
229 ir_node *p0 = get_irn_out(c, 0);
230 ir_node *p1 = get_irn_out(c, 1);
232 /* both are exceptions */
233 if ((get_ProjX_probability(p0) == Cond_prob_exception_taken) &&
234 (get_ProjX_probability(p1) == Cond_prob_exception_taken) ) {
235 assert(0 && "I tried to avoid these!");
237 set_ProjX_probability(p0, Cond_prob_normal);
238 set_ProjX_probability(p1, Cond_prob_normal);
241 /* p0 is exception */
242 else if (get_ProjX_probability(p0) == Cond_prob_exception_taken) {
243 set_ProjX_probability(p1, Cond_prob_avoid_exception);
246 /* p1 is exception */
247 else if (get_ProjX_probability(p1) == Cond_prob_exception_taken) {
248 set_ProjX_probability(p0, Cond_prob_avoid_exception);
251 /* none is exception */
253 set_ProjX_probability(p0, Cond_prob_normal);
254 set_ProjX_probability(p1, Cond_prob_normal);
259 int is_fragile_Proj(ir_node *n) {
260 return is_Proj(n) && (get_ProjX_probability(n) == Cond_prob_exception_taken);
263 /*------------------------------------------------------------------*/
264 /* The algorithm to compute the execution freqencies.
266 * Walk the control flow loop tree which we consider the interval
267 * tree. Compute the execution for the lowest loop, add inner loops
268 * to worklist. Consider the inner loops as simple nodes. Check that
269 * there is only one loop header in each loop. */
270 /*------------------------------------------------------------------*/
272 static double exception_prob = 0.001;
274 static INLINE int is_loop_head(ir_node *cond) {
278 /** Weight a single region in edge.
280 * Given all outs of the predecessor region, we can compute the weight of
281 * this single edge. */
282 static INLINE double get_weighted_region_exec_freq(void *reg, int pos) {
283 void *pred_reg = get_region_in(reg, pos);
284 double res, full_freq = get_region_exec_freq (pred_reg);
285 int n_outs = get_region_n_outs (pred_reg);
286 int n_exc_outs = get_region_n_exc_outs(pred_reg);
289 if (is_ir_node(reg)) {
290 cfop = get_Block_cfgpred((ir_node *)reg, pos);
291 if (is_Proj(cfop) && (get_irn_op(get_Proj_pred(cfop)) != op_Cond))
292 cfop = skip_Proj(cfop);
294 assert(is_ir_loop(reg));
295 cfop = get_loop_cfop(reg, pos);
298 if (is_fragile_op(cfop) || is_fragile_Proj(cfop)) {
299 res = full_freq * exception_prob;
302 /* Equally distribute the weight after exceptions to the left over outs. */
303 res = (full_freq *(1 - exception_prob * n_exc_outs)) / (n_outs - n_exc_outs);
309 static INLINE void compute_region_freqency(void *reg, double head_weight) {
310 int i, n_ins = get_region_n_ins(reg);
313 //printf("head weight %lf: ", head_weight); DDMR(reg);
315 for (i = 0; i < n_ins; ++i) {
316 void *pred_reg = get_region_in(reg, i);
318 my_freq += get_weighted_region_exec_freq(reg, i);
322 if (my_freq == 0.0) {
323 /* All preds are from outer loop. We are a head or so. */
324 my_freq = head_weight;
326 set_region_exec_freq(reg, my_freq);
329 static void check_proper_head(ir_loop *l, void *reg) {
330 int i, n_ins = get_region_n_ins(reg);
331 for (i = 0; i < n_ins; ++i) {
332 assert(!get_region_in(reg, i));
336 /* Compute the ex freq for current_ir_graph */
337 static void compute_frequency(int default_loop_weight) {
338 ir_loop *outermost_l = get_irg_loop(current_ir_graph);
339 pdeq *block_worklist = new_pdeq1(outermost_l);
341 /* Outermost start is considered a loop head. We will soon multiply
342 by default_loop_weight. */
343 set_region_exec_freq(outermost_l, 1.0/default_loop_weight);
345 while (!pdeq_empty(block_worklist)) {
346 ir_loop *l = (ir_loop *)pdeq_getl(block_worklist);
347 int i, n_elems = get_loop_n_elements(l);
349 /* The header is initialized with the freqency of the full loop times the iteration weight. */
350 check_proper_head(l, get_loop_element(l, 0).son);
352 for (i = 0; i < n_elems; ++i) {
353 loop_element e = get_loop_element(l, i);
354 if (is_ir_loop(e.son)) pdeq_putr(block_worklist, e.son);
355 compute_region_freqency(e.son, default_loop_weight * get_region_exec_freq(l));
358 del_pdeq(block_worklist);
361 /* Compute the execution frequency for all blocks in the given
364 * irg: The graph to be analyzed.
365 * default_loop_weight: The number of executions of a loop.
367 void compute_execution_frequency(ir_graph *irg, int default_loop_weight, double exception_probability) {
368 ir_graph *rem = current_ir_graph;
369 current_ir_graph = irg;
370 exception_prob = exception_probability;
371 if (!exec_freq_set) exec_freq_set = new_set(exec_freq_cmp, 256);
373 precompute_cond_evaluation();
374 construct_intervals(current_ir_graph);
375 compute_frequency(default_loop_weight);
378 dump_loop_tree (current_ir_graph, "-execfreq");
379 dump_ir_block_graph(current_ir_graph, "-execfreq");
380 dump_interval_graph(current_ir_graph, "-execfreq");
383 current_ir_graph = rem;
387 void compute_execution_frequencies(int default_loop_weight, double exception_probability) {
388 int i, n_irgs = get_irp_n_irgs();
390 for (i = 0; i < n_irgs; ++i) {
391 compute_execution_frequency(get_irp_irg(i), default_loop_weight, exception_probability);
395 /** free occupied memory, reset */
396 void free_execution_frequency(void) {
398 del_set(exec_freq_set);