2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Compute an estimate of basic block executions.
23 * @author Goetz Lindenmaier
29 #include "execution_frequency.h"
36 #include "irgraph_t.h"
41 #include "interval_analysis.h"
43 void set_irp_exec_freq_state(exec_freq_state s);
45 /*------------------------------------------------------------------*/
46 /* A hashmap mapping the frequency to block and loop nodes. Block
47 * and loop nodes are regions. */
48 /*------------------------------------------------------------------*/
56 /* We use this set for all nodes in all irgraphs. */
57 static set *exec_freq_set = NULL;
59 static int exec_freq_cmp(const void *e1, const void *e2, size_t size)
61 reg_exec_freq *ef1 = (reg_exec_freq *)e1;
62 reg_exec_freq *ef2 = (reg_exec_freq *)e2;
65 return (ef1->reg != ef2->reg);
68 static inline unsigned int exec_freq_hash(reg_exec_freq *e)
70 return HASH_PTR(e->reg);
73 static inline void set_region_exec_freq(void *reg, double freq)
78 set_insert(exec_freq_set, &ef, sizeof(ef), exec_freq_hash(&ef));
81 double get_region_exec_freq(void *reg)
83 reg_exec_freq ef, *found;
85 assert(exec_freq_set);
87 found = set_find(exec_freq_set, &ef, sizeof(ef), exec_freq_hash(&ef));
89 /* Not found if information is invalid. */
96 /* Returns the number of times the block is executed. */
97 double get_Block_exec_freq(ir_node *b)
99 return get_region_exec_freq((void *)b);
102 double get_irn_exec_freq(ir_node *n)
104 if (!is_Block(n)) n = get_nodes_block(n);
105 return get_Block_exec_freq(n);
109 /*------------------------------------------------------------------*/
110 /* A algorithm that precomputes whether Conds lead to an exception.
111 * Computes a field for all Projs from Conds that says the following:
112 * - The Proj projs from a normal dual Cond with probability 50:50
113 * - This Proj of the Cond leads to an exception, i.e., a raise node.
114 * It is taken with exception probability.
115 * - The Proj of the Cond avoids an exception. It is taken with
116 * 1 - exception probability. */
117 /*------------------------------------------------------------------*/
124 Cond_prob_avoid_exception,
125 Cond_prob_exception_taken,
126 Cond_prob_was_exception_taken,
129 static int just_passed_a_Raise = 0;
130 static ir_node *Cond_list = NULL;
132 /* We do not use an extra set, as Projs are not yet in the existing one. */
133 void set_ProjX_probability(ir_node *n, Cond_prob prob)
138 set_insert(exec_freq_set, &ef, sizeof(ef), exec_freq_hash(&ef));
141 Cond_prob get_ProjX_probability(ir_node *n)
143 reg_exec_freq ef, *found;
146 found = set_find(exec_freq_set, &ef, sizeof(ef), exec_freq_hash(&ef));
149 return (Cond_prob)found->prob;
151 return Cond_prob_none;
154 /* A walker that only visits the nodes we want to see. */
156 static void my_irg_walk_2_both(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void * env)
159 set_irn_visited(node, current_ir_graph->visited);
163 if (node->op != op_Block) {
165 if (node->op == op_Proj)
166 pred = get_irn_n(node, 0);
168 pred = get_irn_n(node, -1);
169 if (pred->visited < current_ir_graph->visited)
170 my_irg_walk_2_both(pred, pre, post, env);
174 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
175 ir_node *pred = get_irn_n(node, i);
176 if (pred->visited < current_ir_graph->visited)
177 my_irg_walk_2_both(pred, pre, post, env);
181 if (node->op == op_End) {
182 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
183 ir_node *pred = get_irn_n(node, i);
184 if ((pred->op == op_Block) && (pred->visited < current_ir_graph->visited))
185 my_irg_walk_2_both(pred, pre, post, env);
191 static void my_irg_walk_current_graph(irg_walk_func *pre, irg_walk_func *post, void *env)
193 inc_irg_visited(current_ir_graph);
194 my_irg_walk_2_both(get_irg_end(current_ir_graph), pre, post, env);
198 static void walk_pre(ir_node *n, void *env)
202 just_passed_a_Raise = 1;
204 if (get_irn_op(n) == op_Proj &&
205 is_Cond(get_Proj_pred(n)) &&
206 just_passed_a_Raise) {
208 ir_node *c = get_Proj_pred(n);
210 /* If we already visited the other Proj, and it also leads to a Raise,
211 we are in the middle of something. Continue searching. */
212 assert(get_irn_n_outs(c) == 2 && "encountered a switch cond");
213 other_proj = get_irn_out(c, 0);
214 if (other_proj == n) other_proj = get_irn_out(c, 1);
215 if (get_ProjX_probability(other_proj) == Cond_prob_exception_taken) {
216 set_ProjX_probability(other_proj, Cond_prob_was_exception_taken);
217 /* Keep searching for the Proj, so keep just_passed_a_Raise. */
219 set_ProjX_probability(n, Cond_prob_exception_taken);
220 just_passed_a_Raise = 0;
225 set_irn_link(n, Cond_list);
230 static void walk_post(ir_node *n, void *env)
234 just_passed_a_Raise = 0;
236 if (get_irn_op(n) == op_Proj &&
237 is_Cond(get_Proj_pred(n)) && (
238 get_ProjX_probability(n) == Cond_prob_exception_taken ||
239 get_ProjX_probability(n) == Cond_prob_was_exception_taken
241 just_passed_a_Raise = 1;
245 /** Precompute which Conds test for an exception.
247 * Operates on current_ir_graph. */
248 void precompute_cond_evaluation(void)
252 compute_irg_outs(current_ir_graph);
254 just_passed_a_Raise = 0;
256 my_irg_walk_current_graph(walk_pre, walk_post, NULL);
258 for (c = Cond_list; c; c = get_irn_link(c)) {
261 assert(get_irn_n_outs(c) == 2 && "encountered a switch cond");
262 p0 = get_irn_out(c, 0);
263 p1 = get_irn_out(c, 1);
265 /* both are exceptions */
266 if ((get_ProjX_probability(p0) == Cond_prob_exception_taken) &&
267 (get_ProjX_probability(p1) == Cond_prob_exception_taken) ) {
268 assert(0 && "I tried to avoid these!");
270 set_ProjX_probability(p0, Cond_prob_normal);
271 set_ProjX_probability(p1, Cond_prob_normal);
274 /* p0 is exception */
275 else if (get_ProjX_probability(p0) == Cond_prob_exception_taken) {
276 set_ProjX_probability(p1, Cond_prob_avoid_exception);
279 /* p1 is exception */
280 else if (get_ProjX_probability(p1) == Cond_prob_exception_taken) {
281 set_ProjX_probability(p0, Cond_prob_avoid_exception);
284 /* none is exception */
286 set_ProjX_probability(p0, Cond_prob_normal);
287 set_ProjX_probability(p1, Cond_prob_normal);
292 int is_fragile_Proj(ir_node *n)
294 return is_Proj(n) && (get_ProjX_probability(n) == Cond_prob_exception_taken);
297 /*------------------------------------------------------------------*/
298 /* The algorithm to compute the execution frequencies.
300 * Walk the control flow loop tree which we consider the interval
301 * tree. Compute the execution for the lowest loop, add inner loops
302 * to worklist. Consider the inner loops as simple nodes. Check that
303 * there is only one loop header in each loop. */
304 /*------------------------------------------------------------------*/
306 static double exception_prob = 0.001;
308 static inline int is_loop_head(ir_node *cond)
314 /** Weight a single region in edge.
316 * Given all outs of the predecessor region, we can compute the weight of
317 * this single edge. */
318 static inline double get_weighted_region_exec_freq(void *reg, int pos)
320 void *pred_reg = get_region_in(reg, pos);
321 double res, full_freq = get_region_exec_freq (pred_reg);
322 int n_outs = get_region_n_outs (pred_reg);
323 int n_exc_outs = get_region_n_exc_outs(pred_reg);
326 if (is_ir_node(reg)) {
327 cfop = get_Block_cfgpred((ir_node *)reg, pos);
328 if (is_Proj(cfop) && !is_Cond(get_Proj_pred(cfop)))
329 cfop = skip_Proj(cfop);
331 assert(is_ir_loop(reg));
332 cfop = get_loop_cfop(reg, pos);
335 if (is_fragile_op(cfop) || is_fragile_Proj(cfop)) {
336 res = full_freq * exception_prob;
339 /* Equally distribute the weight after exceptions to the left over outs. */
340 res = (full_freq *(1 - exception_prob * n_exc_outs)) / (n_outs - n_exc_outs);
346 static inline void compute_region_freqency(void *reg, double head_weight)
348 int i, n_ins = get_region_n_ins(reg);
351 //printf("head weight %lf: ", head_weight); DDMR(reg);
353 for (i = 0; i < n_ins; ++i) {
354 void *pred_reg = get_region_in(reg, i);
356 my_freq += get_weighted_region_exec_freq(reg, i);
360 if (my_freq == 0.0) {
361 /* All preds are from outer loop. We are a head or so. */
362 my_freq = head_weight;
364 set_region_exec_freq(reg, my_freq);
367 static void check_proper_head(ir_loop *l, void *reg)
369 int i, n_ins = get_region_n_ins(reg);
371 for (i = 0; i < n_ins; ++i) {
372 assert(!get_region_in(reg, i));
376 /* Compute the ex freq for current_ir_graph */
377 static void compute_frequency(int default_loop_weight)
379 ir_loop *outermost_l = get_irg_loop(current_ir_graph);
380 pdeq *block_worklist = new_pdeq1(outermost_l);
382 /* Outermost start is considered a loop head. We will soon multiply
383 by default_loop_weight. */
384 set_region_exec_freq(outermost_l, 1.0/default_loop_weight);
386 while (!pdeq_empty(block_worklist)) {
387 ir_loop *l = (ir_loop *)pdeq_getl(block_worklist);
388 int i, n_elems = get_loop_n_elements(l);
390 /* The header is initialized with the frequency of the full loop times the iteration weight. */
391 check_proper_head(l, get_loop_element(l, 0).son);
393 for (i = 0; i < n_elems; ++i) {
394 loop_element e = get_loop_element(l, i);
395 if (is_ir_loop(e.son)) pdeq_putr(block_worklist, e.son);
396 compute_region_freqency(e.son, default_loop_weight * get_region_exec_freq(l));
399 del_pdeq(block_worklist);
402 /* Compute the execution frequency for all blocks in the given
405 * irg: The graph to be analyzed.
406 * default_loop_weight: The number of executions of a loop.
408 void compute_execution_frequency(ir_graph *irg, int default_loop_weight, double exception_probability)
410 ir_graph *rem = current_ir_graph;
411 current_ir_graph = irg;
412 exception_prob = exception_probability;
413 if (!exec_freq_set) exec_freq_set = new_set(exec_freq_cmp, 256);
415 precompute_cond_evaluation();
416 construct_intervals(current_ir_graph);
417 compute_frequency(default_loop_weight);
419 set_irg_exec_freq_state(irg, exec_freq_consistent);
420 if (get_irp_exec_freq_state() == exec_freq_none)
421 set_irp_exec_freq_state(exec_freq_inconsistent);
424 dump_loop_tree (current_ir_graph, "-execfreq");
425 dump_ir_block_graph(current_ir_graph, "-execfreq");
426 dump_interval_graph(current_ir_graph, "-execfreq");
429 current_ir_graph = rem;
433 void compute_execution_frequencies(int default_loop_weight, double exception_probability)
435 int i, n_irgs = get_irp_n_irgs();
437 for (i = 0; i < n_irgs; ++i) {
438 compute_execution_frequency(get_irp_irg(i), default_loop_weight, exception_probability);
440 set_irp_exec_freq_state(exec_freq_consistent);
443 /** free occupied memory, reset */
444 void free_execution_frequency(void)
446 int i, n_irgs = get_irp_n_irgs();
448 del_set(exec_freq_set);
450 for (i = 0; i < n_irgs; ++i)
451 set_irg_exec_freq_state(get_irp_irg(i), exec_freq_none);
452 set_irp_exec_freq_state(exec_freq_none);
455 exec_freq_state get_irg_exec_freq_state(ir_graph *irg)
457 return irg->execfreq_state;
459 void set_irg_exec_freq_state(ir_graph *irg, exec_freq_state s)
461 if ((get_irp_exec_freq_state() == exec_freq_consistent && s != exec_freq_consistent) ||
462 (get_irp_exec_freq_state() == exec_freq_none && s != exec_freq_none))
463 irp->execfreq_state = exec_freq_inconsistent;
464 irg->execfreq_state = s;
467 /* Sets irg and irp exec freq state to inconsistent if it is set to consistent. */
468 void set_irg_exec_freq_state_inconsistent(ir_graph *irg)
470 if (get_irg_exec_freq_state(irg) == exec_freq_consistent)
471 set_irg_exec_freq_state(irg, exec_freq_inconsistent);
474 void set_irp_exec_freq_state(exec_freq_state s)
476 irp->execfreq_state = s;
479 exec_freq_state get_irp_exec_freq_state(void)
481 return irp->execfreq_state;
484 /* Sets irp and all irg exec freq states to inconsistent if it is set to consistent. */
485 void set_irp_exec_freq_state_inconsistent(void)
487 if (get_irp_exec_freq_state() != exec_freq_none) {
488 int i, n_irgs = get_irp_n_irgs();
489 set_irp_exec_freq_state(exec_freq_inconsistent);
490 for (i = 0; i < n_irgs; ++i) {
491 ir_graph *irg = get_irp_irg(i);
492 if (get_irg_exec_freq_state(irg) != exec_freq_none)
493 irg->execfreq_state = exec_freq_inconsistent;