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 "irnode_t.h"
  24 #include "irloop.h"
  25 #include "irgwalk.h"
  26
  27 #include "interval_analysis.h"
  28
  29 /*------------------------------------------------------------------*/
  30 /* A hashmap mapping the frequency to block and loop nodes.  Block
  31  * and loop nodes are regions.                                      */
  32 /*------------------------------------------------------------------*/
  33
  34 typedef struct {
  35   void   *reg;
  36   double  freq;
  37   int     prob;
  38 } reg_exec_freq;
  39
  40 /* We use this set for all nodes in all irgraphs. */
  41 static set *exec_freq_set = NULL;
  42
  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);
  47 }
  48
  49 static INLINE unsigned int exec_freq_hash(void *e) {
  50   unsigned int v = (unsigned int) ((reg_exec_freq *)e)->reg;
  51   return v ^ (v>>8);
  52 }
  53
  54 static INLINE void set_region_exec_freq(void *reg, double freq) {
  55   reg_exec_freq ef;
  56   ef.reg  = reg;
  57   ef.freq = freq;
  58   set_insert(exec_freq_set, &ef, sizeof(ef), exec_freq_hash(&ef));
  59 }
  60
  61 INLINE double get_region_exec_freq(void *reg) {
  62   reg_exec_freq ef, *found;
  63   ef.reg  = reg;
  64   assert(exec_freq_set);
  65
  66   found = set_find(exec_freq_set, &ef, sizeof(ef), exec_freq_hash(&ef));
  67
  68   /* Not found if information is invalid. */
  69   if (found)
  70     return found->freq;
  71   else
  72     return 0;
  73 }
  74
  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);
  78 }
  79
  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);
  83 }
  84
  85
  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 /*------------------------------------------------------------------*/
  95
  96 #include "irouts.h"
  97
  98 typedef enum {
  99   Cond_prob_none,
 100   Cond_prob_normal,
 101   Cond_prob_avoid_exception,
 102   Cond_prob_exception_taken,
 103   Cond_prob_was_exception_taken,
 104 } Cond_prob;
 105
 106 static int just_passed_a_Raise = 0;
 107 static ir_node *Cond_list = NULL;
 108
 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) {
 111   reg_exec_freq ef;
 112   ef.reg  = n;
 113   ef.prob = prob;
 114   set_insert(exec_freq_set, &ef, sizeof(ef), exec_freq_hash(&ef));
 115 }
 116
 117 Cond_prob get_ProjX_probability(ir_node *n) {
 118   reg_exec_freq ef, *found;
 119   ef.reg  = n;
 120
 121   found = set_find(exec_freq_set, &ef, sizeof(ef), exec_freq_hash(&ef));
 122
 123   if (found)
 124     return (Cond_prob)found->prob;
 125   else
 126     return Cond_prob_none;
 127 }
 128
 129 /* A walker that only visits the nodes we want to see. */
 130
 131 static void
 132 my_irg_walk_2_both(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void * env) {
 133   int i;
 134   set_irn_visited(node, current_ir_graph->visited);
 135
 136   pre(node, env);
 137
 138   if (node->op != op_Block) {
 139     ir_node *pred;
 140     if (node->op == op_Proj)
 141       pred = get_irn_n(node, 0);
 142     else
 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);
 146   }
 147
 148   else {  /* a Block */
 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);
 153     }
 154   }
 155
 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);
 161     }
 162   }
 163
 164   post(node, env);
 165 }
 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);
 169 }
 170
 171
 172 static void walk_pre(ir_node *n, void *env) {
 173
 174   if (get_irn_op(n) == op_Raise)
 175     just_passed_a_Raise = 1;
 176
 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 *other_proj;
 181     ir_node *c = get_Proj_pred(n);
 182
 183     /* If we already visited the other Proj, and it also leads to a Raise,
 184        we are in the middle of something. Continue searching. */
 185     assert(get_irn_n_outs(c) == 2 && "encountered a switch cond");
 186     other_proj = get_irn_out(c, 0);
 187     if (other_proj == n) other_proj = get_irn_out(c, 1);
 188     if (get_ProjX_probability(other_proj) == Cond_prob_exception_taken) {
 189       set_ProjX_probability(other_proj, Cond_prob_was_exception_taken);
 190       /* Keep searching for the Proj, so keep just_passed_a_Raise. */
 191     } else {
 192       set_ProjX_probability(n, Cond_prob_exception_taken);
 193       just_passed_a_Raise = 0;
 194     }
 195   }
 196
 197   if (get_irn_op(n) == op_Cond) {
 198     set_irn_link(n, Cond_list);
 199     Cond_list = n;
 200   }
 201 }
 202
 203 static void walk_post(ir_node *n, void *env) {
 204
 205   if (get_irn_op(n) == op_Raise)
 206     just_passed_a_Raise = 0;
 207
 208   if (   (get_irn_op(n) == op_Proj)
 209       && (get_irn_op(get_Proj_pred(n)) == op_Cond)
 210       && ((get_ProjX_probability(n) == Cond_prob_exception_taken)    ||
 211           (get_ProjX_probability(n) == Cond_prob_was_exception_taken)   )) {
 212     just_passed_a_Raise = 1;
 213   }
 214 }
 215
 216 /** Precompute which Conds test for an exception.
 217  *
 218  *  Operates on current_ir_graph. */
 219 void precompute_cond_evaluation(void) {
 220   ir_node *c;
 221
 222   compute_outs(current_ir_graph);
 223
 224   just_passed_a_Raise = 0;
 225   Cond_list = NULL;
 226   my_irg_walk_current_graph(walk_pre, walk_post, NULL);
 227
 228   for (c = Cond_list; c; c = get_irn_link(c)) {
 229     ir_node *p0, *p1;
 230
 231     assert(get_irn_n_outs(c) == 2 && "encountered a switch cond");
 232     p0 = get_irn_out(c, 0);
 233     p1 = get_irn_out(c, 1);
 234
 235     /* both are exceptions */
 236     if ((get_ProjX_probability(p0) == Cond_prob_exception_taken) &&
 237         (get_ProjX_probability(p1) == Cond_prob_exception_taken)   ) {
 238       assert(0 && "I tried to avoid these!");
 239       /* It's a */
 240       set_ProjX_probability(p0, Cond_prob_normal);
 241       set_ProjX_probability(p1, Cond_prob_normal);
 242     }
 243
 244     /* p0 is exception */
 245     else if (get_ProjX_probability(p0) == Cond_prob_exception_taken) {
 246       set_ProjX_probability(p1, Cond_prob_avoid_exception);
 247     }
 248
 249     /* p1 is exception */
 250     else if (get_ProjX_probability(p1) == Cond_prob_exception_taken) {
 251       set_ProjX_probability(p0, Cond_prob_avoid_exception);
 252     }
 253
 254     /* none is exception */
 255     else {
 256       set_ProjX_probability(p0, Cond_prob_normal);
 257       set_ProjX_probability(p1, Cond_prob_normal);
 258     }
 259   }
 260 }
 261
 262 int is_fragile_Proj(ir_node *n) {
 263   return is_Proj(n) && (get_ProjX_probability(n) == Cond_prob_exception_taken);
 264 }
 265
 266 /*------------------------------------------------------------------*/
 267 /* The algorithm to compute the execution frequencies.
 268  *
 269  * Walk the control flow loop tree which we consider the interval
 270  * tree.  Compute the execution for the lowest loop, add inner loops
 271  * to worklist.  Consider the inner loops as simple nodes.  Check that
 272  * there is only one loop header in each loop.                      */
 273 /*------------------------------------------------------------------*/
 274
 275 static double exception_prob = 0.001;
 276
 277 static INLINE int is_loop_head(ir_node *cond) {
 278   return false;
 279 }
 280
 281 /** Weight a single region in edge.
 282  *
 283  *  Given all outs of the predecessor region, we can compute the weight of
 284  *  this single edge. */
 285 static INLINE double get_weighted_region_exec_freq(void *reg, int pos) {
 286   void *pred_reg        = get_region_in(reg, pos);
 287   double res, full_freq = get_region_exec_freq (pred_reg);
 288   int n_outs            = get_region_n_outs    (pred_reg);
 289   int n_exc_outs        = get_region_n_exc_outs(pred_reg);
 290
 291   ir_node *cfop;
 292   if (is_ir_node(reg)) {
 293     cfop = get_Block_cfgpred((ir_node *)reg, pos);
 294     if (is_Proj(cfop) && (get_irn_op(get_Proj_pred(cfop)) != op_Cond))
 295       cfop = skip_Proj(cfop);
 296   } else {
 297     assert(is_ir_loop(reg));
 298     cfop = get_loop_cfop(reg, pos);
 299   }
 300
 301   if (is_fragile_op(cfop) || is_fragile_Proj(cfop)) {
 302     res = full_freq * exception_prob;
 303   } else {
 304
 305     /* Equally distribute the weight after exceptions to the left over outs. */
 306     res = (full_freq *(1 - exception_prob * n_exc_outs)) / (n_outs - n_exc_outs);
 307   }
 308
 309   return res;
 310 }
 311
 312 static INLINE void compute_region_freqency(void *reg, double head_weight) {
 313   int i, n_ins = get_region_n_ins(reg);
 314   double my_freq = 0;
 315
 316   //printf("head weight %lf: ", head_weight); DDMR(reg);
 317
 318   for (i = 0; i < n_ins; ++i) {
 319     void *pred_reg = get_region_in(reg, i);
 320     if (pred_reg) {
 321       my_freq += get_weighted_region_exec_freq(reg, i);
 322     }
 323   }
 324
 325   if (my_freq == 0.0) {
 326     /* All preds are from outer loop. We are a head or so. */
 327     my_freq = head_weight;
 328   }
 329   set_region_exec_freq(reg, my_freq);
 330 }
 331
 332 static void check_proper_head(ir_loop *l, void *reg) {
 333   int i, n_ins = get_region_n_ins(reg);
 334   for (i = 0; i < n_ins; ++i) {
 335     assert(!get_region_in(reg, i));
 336   }
 337 }
 338
 339 /* Compute the ex freq for current_ir_graph */
 340 static void compute_frequency(int default_loop_weight) {
 341   ir_loop *outermost_l = get_irg_loop(current_ir_graph);
 342   pdeq *block_worklist = new_pdeq1(outermost_l);
 343
 344   /* Outermost start is considered a loop head.  We will soon multiply
 345      by default_loop_weight. */
 346   set_region_exec_freq(outermost_l, 1.0/default_loop_weight);
 347
 348   while (!pdeq_empty(block_worklist)) {
 349     ir_loop *l = (ir_loop *)pdeq_getl(block_worklist);
 350     int i, n_elems = get_loop_n_elements(l);
 351
 352     /* The header is initialized with the frequency of the full loop times the iteration weight. */
 353     check_proper_head(l, get_loop_element(l, 0).son);
 354
 355     for (i = 0; i < n_elems; ++i) {
 356       loop_element e = get_loop_element(l, i);
 357       if (is_ir_loop(e.son)) pdeq_putr(block_worklist, e.son);
 358       compute_region_freqency(e.son, default_loop_weight * get_region_exec_freq(l));
 359     }
 360   }
 361   del_pdeq(block_worklist);
 362 }
 363
 364 /* Compute the execution frequency for all blocks in the given
 365  * graph.
 366  *
 367  * irg:                 The graph to be analyzed.
 368  * default_loop_weight: The number of executions of a loop.
 369  */
 370 void compute_execution_frequency(ir_graph *irg, int default_loop_weight, double exception_probability) {
 371   ir_graph *rem = current_ir_graph;
 372   current_ir_graph = irg;
 373   exception_prob = exception_probability;
 374   if (!exec_freq_set) exec_freq_set = new_set(exec_freq_cmp, 256);
 375
 376   precompute_cond_evaluation();
 377   construct_intervals(current_ir_graph);
 378   compute_frequency(default_loop_weight);
 379
 380   /*
 381     dump_loop_tree     (current_ir_graph, "-execfreq");
 382     dump_ir_block_graph(current_ir_graph, "-execfreq");
 383     dump_interval_graph(current_ir_graph, "-execfreq");
 384   */
 385
 386   current_ir_graph = rem;
 387 }
 388
 389
 390 void compute_execution_frequencies(int default_loop_weight, double exception_probability) {
 391   int i, n_irgs = get_irp_n_irgs();
 392   free_intervals();
 393   for (i = 0; i < n_irgs; ++i) {
 394     compute_execution_frequency(get_irp_irg(i), default_loop_weight, exception_probability);
 395   }
 396 }
 397
 398 /** free occupied memory, reset */
 399 void free_execution_frequency(void) {
 400   free_intervals();
 401   del_set(exec_freq_set);
 402 }