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.
13 #include "execution_frequency.h"
15 #include "firm_common_t.h"
22 #include "interval_analysis.h"
24 /*------------------------------------------------------------------*/
25 /* A hashmap mapping the frequency to block and loop nodes. Block
26 * and loop nodes are regions. */
27 /*------------------------------------------------------------------*/
34 /* We use this set for all nodes in all irgraphs. */
35 static set *exec_freq_set = NULL;
37 static int exec_freq_cmp(const void *e1, const void *e2, size_t size) {
38 reg_exec_freq *ef1 = (reg_exec_freq *)e1;
39 reg_exec_freq *ef2 = (reg_exec_freq *)e2;
40 return (ef1->reg != ef2->reg);
43 static INLINE unsigned int exec_freq_hash(void *e) {
44 unsigned int v = (unsigned int) ((reg_exec_freq *)e)->reg;
48 static INLINE void set_region_exec_freq(void *reg, double freq) {
52 set_insert(exec_freq_set, &ef, sizeof(ef), exec_freq_hash(&ef));
55 INLINE double get_region_exec_freq(void *reg) {
56 reg_exec_freq ef, *found;
59 found = set_find(exec_freq_set, &ef, sizeof(ef), exec_freq_hash(&ef));
64 /* Returns the number of times the block is executed. */
65 double get_Block_exec_freq(ir_node *b) {
66 return get_region_exec_freq((void *)b);
70 /*------------------------------------------------------------------*/
71 /* The algorithm to compute the execution freqencies.
73 * Walk the control flow loop tree which we consider the interval
74 * tree. Compute the execution for the lowest loop, add inner loops
75 * to worklist. Consider the inner loops as simple nodes. Check that
76 * there is only one loop header in each loop. */
77 /*------------------------------------------------------------------*/
79 static double exception_prob = 0.001;
81 static INLINE int is_loop_head(ir_node *cond) {
85 static INLINE double get_weighted_region_exec_freq(void *reg, int pos) {
86 void *pred_reg = get_region_in(reg, pos);
87 double res, full_freq = get_region_exec_freq(pred_reg);
88 int n_outs = get_region_n_outs (pred_reg);
89 int n_exc_outs = get_region_n_exc_outs(pred_reg);
92 if (is_ir_node(reg)) {
93 cfop = skip_Proj(get_Block_cfgpred((ir_node *)reg, pos));
95 assert(is_ir_loop(reg));
96 cfop = get_loop_cfop(reg, pos);
99 if (is_fragile_op(cfop)) {
100 res = full_freq * exception_prob;
103 /* Equally distribute the weight after exceptions to the left over outs. */
104 res = (full_freq *(1 - exception_prob * n_exc_outs)) / (n_outs - n_exc_outs);
110 static INLINE void compute_region_freqency(void *reg, double head_weight) {
111 int i, n_ins = get_region_n_ins(reg);
114 //printf("head weight %lf: ", head_weight); DDMR(reg);
116 for (i = 0; i < n_ins; ++i) {
117 void *pred_reg = get_region_in(reg, i);
119 if (is_ir_node(reg) && get_irn_node_nr((ir_node *)reg) == 50573)
120 printf(" + %lf", get_weighted_region_exec_freq(reg, i));
121 my_freq += get_weighted_region_exec_freq(reg, i);
124 if (is_ir_node(reg) && get_irn_node_nr(reg) == 50573) {
125 printf(" myfreq %lf", my_freq); DDMN((ir_node *)reg);
128 if (my_freq == 0.0) {
129 /* All preds are from outer loop. We are a head or so. */
130 my_freq = head_weight;
132 set_region_exec_freq(reg, my_freq);
135 static void check_proper_head(ir_loop *l, void *reg) {
136 int i, n_ins = get_region_n_ins(reg);
137 for (i = 0; i < n_ins; ++i) {
138 assert(!get_region_in(reg, i));
142 /* Compute the ex freq for current_ir_graph */
143 static void compute_frequency(int default_loop_weight) {
144 ir_loop *outermost_l = get_irg_loop(current_ir_graph);
145 pdeq *block_worklist = new_pdeq1(outermost_l);
147 set_region_exec_freq(outermost_l, 1.0/default_loop_weight); /* outermost start is considered a loop head. */
149 while (!pdeq_empty(block_worklist)) {
150 ir_loop *l = (ir_loop *)pdeq_getl(block_worklist);
151 int i, n_elems = get_loop_n_elements(l);
153 /* The header is initialized with the freqency of the full loop times the iteration weight. */
154 check_proper_head(l, get_loop_element(l, 0).son);
156 for (i = 0; i < n_elems; ++i) {
157 loop_element e = get_loop_element(l, i);
158 if (is_ir_loop(e.son)) pdeq_putr(block_worklist, e.son);
159 compute_region_freqency(e.son, default_loop_weight * get_region_exec_freq(l));
162 del_pdeq(block_worklist);
165 /* Compute the execution frequency for all blocks in the given
168 * irg: The graph to be analyzed.
169 * default_loop_weight: The number of executions of a loop.
171 void compute_execution_frequency(ir_graph *irg, int default_loop_weight, double exception_probability) {
172 ir_graph *rem = current_ir_graph;
173 current_ir_graph = irg;
174 exception_prob = exception_probability;
175 if (!exec_freq_set) exec_freq_set = new_set(exec_freq_cmp, 256);
177 construct_intervals(current_ir_graph);
178 compute_frequency(default_loop_weight);
181 dump_loop_tree (current_ir_graph, "-execfreq");
182 dump_ir_block_graph(current_ir_graph, "-execfreq");
183 dump_interval_graph(current_ir_graph, "-execfreq");
186 current_ir_graph = rem;
190 void compute_execution_frequencies(int default_loop_weight, double exception_probability) {
191 int i, n_irgs = get_irp_n_irgs();
193 for (i = 0; i < n_irgs; ++i) {
194 compute_execution_frequency(get_irp_irg(i), default_loop_weight, exception_probability);
198 /** free occupied memory, reset */
199 void free_execution_frequency(void) {
201 del_set(exec_freq_set);