nsz Git - libfirm/blob - ir/ana/execution_frequency.c

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/ana/execution_frequency.c
   4  * Purpose:     Compute an estimate of basic block executions.
   5  * Author:      Goetz Lindenmaier
   6  * Modified by:
   7  * Created:     5.11.2004
   8  * CVS-ID:      $Id$
   9  * Copyright:   (c) 2004 Universität Karlsruhe
  10  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  11  */
  12 #ifdef HAVE_CONFIG_H
  13 #include "config.h"
  14 #endif
  15
  16 #include "execution_frequency.h"
  17
  18 #include "firm_common_t.h"
  19 #include "set.h"
  20 #include "pdeq.h"
  21
  22 #include "irprog.h"
  23 #include "irloop.h"
  24
  25 #include "interval_analysis.h"
  26
  27 /*------------------------------------------------------------------*/
  28 /* A hashmap mapping the frequency to block and loop nodes.  Block
  29  * and loop nodes are regions.                                      */
  30 /*------------------------------------------------------------------*/
  31
  32 typedef struct {
  33   void   *reg;
  34   double  freq;
  35 } reg_exec_freq;
  36
  37 /* We use this set for all nodes in all irgraphs. */
  38 static set *exec_freq_set = NULL;
  39
  40 static int exec_freq_cmp(const void *e1, const void *e2, size_t size) {
  41   reg_exec_freq *ef1 = (reg_exec_freq *)e1;
  42   reg_exec_freq *ef2 = (reg_exec_freq *)e2;
  43   return (ef1->reg != ef2->reg);
  44 }
  45
  46 static INLINE unsigned int exec_freq_hash(void *e) {
  47   unsigned int v = (unsigned int) ((reg_exec_freq *)e)->reg;
  48   return v ^ (v>>8);
  49 }
  50
  51 static INLINE void set_region_exec_freq(void *reg, double freq) {
  52   reg_exec_freq ef;
  53   ef.reg  = reg;
  54   ef.freq = freq;
  55   set_insert(exec_freq_set, &ef, sizeof(ef), exec_freq_hash(&ef));
  56 }
  57
  58 INLINE double get_region_exec_freq(void *reg) {
  59   reg_exec_freq ef, *found;
  60   ef.reg  = reg;
  61
  62   found = set_find(exec_freq_set, &ef, sizeof(ef), exec_freq_hash(&ef));
  63   assert(found);
  64   return found->freq;
  65 }
  66
  67 /* Returns the number of times the block is executed. */
  68 double     get_Block_exec_freq(ir_node *b) {
  69   return get_region_exec_freq((void *)b);
  70 }
  71
  72
  73 /*------------------------------------------------------------------*/
  74 /* The algorithm to compute the execution freqencies.
  75  *
  76  * Walk the control flow loop tree which we consider the interval
  77  * tree.  Compute the execution for the lowest loop, add inner loops
  78  * to worklist.  Consider the inner loops as simple nodes.  Check that
  79  * there is only one loop header in each loop.                      */
  80 /*------------------------------------------------------------------*/
  81
  82 static double exception_prob = 0.001;
  83
  84 static INLINE int is_loop_head(ir_node *cond) {
  85   return false;
  86 }
  87
  88 static INLINE double get_weighted_region_exec_freq(void *reg, int pos) {
  89   void *pred_reg = get_region_in(reg, pos);
  90   double res, full_freq = get_region_exec_freq(pred_reg);
  91   int n_outs     = get_region_n_outs    (pred_reg);
  92   int n_exc_outs = get_region_n_exc_outs(pred_reg);
  93
  94   ir_node *cfop;
  95   if (is_ir_node(reg)) {
  96     cfop = skip_Proj(get_Block_cfgpred((ir_node *)reg, pos));
  97   } else {
  98     assert(is_ir_loop(reg));
  99     cfop = get_loop_cfop(reg, pos);
 100   }
 101
 102   if (is_fragile_op(cfop)) {
 103     res = full_freq * exception_prob;
 104   } else {
 105
 106     /* Equally distribute the weight after exceptions to the left over outs. */
 107     res = (full_freq *(1 - exception_prob * n_exc_outs)) / (n_outs - n_exc_outs);
 108   }
 109
 110   return res;
 111 }
 112
 113 static INLINE void compute_region_freqency(void *reg, double head_weight) {
 114   int i, n_ins = get_region_n_ins(reg);
 115   double my_freq = 0;
 116
 117   //printf("head weight %lf: ", head_weight); DDMR(reg);
 118
 119   for (i = 0; i < n_ins; ++i) {
 120     void *pred_reg = get_region_in(reg, i);
 121     if (pred_reg) {
 122       if (is_ir_node(reg) && get_irn_node_nr((ir_node *)reg) == 50573)
 123         printf(" + %lf", get_weighted_region_exec_freq(reg, i));
 124       my_freq += get_weighted_region_exec_freq(reg, i);
 125     }
 126   }
 127   if (is_ir_node(reg) && get_irn_node_nr(reg) == 50573) {
 128     printf(" myfreq %lf", my_freq); DDMN((ir_node *)reg);
 129   }
 130
 131   if (my_freq == 0.0) {
 132     /* All preds are from outer loop. We are a head or so. */
 133     my_freq = head_weight;
 134   }
 135   set_region_exec_freq(reg, my_freq);
 136 }
 137
 138 static void check_proper_head(ir_loop *l, void *reg) {
 139   int i, n_ins = get_region_n_ins(reg);
 140   for (i = 0; i < n_ins; ++i) {
 141     assert(!get_region_in(reg, i));
 142   }
 143 }
 144
 145 /* Compute the ex freq for current_ir_graph */
 146 static void compute_frequency(int default_loop_weight) {
 147   ir_loop *outermost_l = get_irg_loop(current_ir_graph);
 148   pdeq *block_worklist = new_pdeq1(outermost_l);
 149
 150   set_region_exec_freq(outermost_l, 1.0/default_loop_weight);  /* outermost start is considered a loop head. */
 151
 152   while (!pdeq_empty(block_worklist)) {
 153     ir_loop *l = (ir_loop *)pdeq_getl(block_worklist);
 154     int i, n_elems = get_loop_n_elements(l);
 155
 156     /* The header is initialized with the freqency of the full loop times the iteration weight. */
 157     check_proper_head(l, get_loop_element(l, 0).son);
 158
 159     for (i = 0; i < n_elems; ++i) {
 160       loop_element e = get_loop_element(l, i);
 161       if (is_ir_loop(e.son)) pdeq_putr(block_worklist, e.son);
 162       compute_region_freqency(e.son, default_loop_weight * get_region_exec_freq(l));
 163     }
 164   }
 165   del_pdeq(block_worklist);
 166 }
 167
 168 /* Compute the execution frequency for all blocks in the given
 169  * graph.
 170  *
 171  * irg:                 The graph to be analyzed.
 172  * default_loop_weight: The number of executions of a loop.
 173  */
 174 void compute_execution_frequency(ir_graph *irg, int default_loop_weight, double exception_probability) {
 175   ir_graph *rem = current_ir_graph;
 176   current_ir_graph = irg;
 177   exception_prob = exception_probability;
 178   if (!exec_freq_set) exec_freq_set = new_set(exec_freq_cmp, 256);
 179
 180   construct_intervals(current_ir_graph);
 181   compute_frequency(default_loop_weight);
 182
 183   /*
 184   dump_loop_tree     (current_ir_graph, "-execfreq");
 185   dump_ir_block_graph(current_ir_graph, "-execfreq");
 186   dump_interval_graph(current_ir_graph, "-execfreq");
 187   */
 188
 189   current_ir_graph = rem;
 190 }
 191
 192
 193 void compute_execution_frequencies(int default_loop_weight, double exception_probability) {
 194   int i, n_irgs = get_irp_n_irgs();
 195   free_intervals();
 196   for (i = 0; i < n_irgs; ++i) {
 197     compute_execution_frequency(get_irp_irg(i), default_loop_weight, exception_probability);
 198   }
 199 }
 200
 201 /** free occupied memory, reset */
 202 void free_execution_frequency(void) {
 203   free_intervals();
 204   del_set(exec_freq_set);
 205 }