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