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

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   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.
  10  *
  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.
  14  *
  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
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief     Compute an estimate of basic block executions.
  23  * @author    Goetz Lindenmaier
  24  * @date      5.11.2004
  25  * @version   $Id$
  26  */
  27 #include "config.h"
  28
  29 #include "execution_frequency.h"
  30
  31 #include "set.h"
  32 #include "pdeq.h"
  33 #include "hashptr.h"
  34
  35 #include "irprog_t.h"
  36 #include "irgraph_t.h"
  37 #include "irnode_t.h"
  38 #include "irloop.h"
  39 #include "irgwalk.h"
  40
  41 #include "interval_analysis.h"
  42
  43 void set_irp_exec_freq_state(exec_freq_state s);
  44
  45 /*------------------------------------------------------------------*/
  46 /* A hashmap mapping the frequency to block and loop nodes.  Block
  47  * and loop nodes are regions.                                      */
  48 /*------------------------------------------------------------------*/
  49
  50 typedef struct {
  51   void   *reg;
  52   double  freq;
  53   int     prob;
  54 } reg_exec_freq;
  55
  56 /* We use this set for all nodes in all irgraphs. */
  57 static set *exec_freq_set = NULL;
  58
  59 static int exec_freq_cmp(const void *e1, const void *e2, size_t size)
  60 {
  61   reg_exec_freq *ef1 = (reg_exec_freq *)e1;
  62   reg_exec_freq *ef2 = (reg_exec_freq *)e2;
  63   (void) size;
  64
  65   return (ef1->reg != ef2->reg);
  66 }
  67
  68 static inline unsigned int exec_freq_hash(reg_exec_freq *e)
  69 {
  70   return HASH_PTR(e->reg);
  71 }
  72
  73 static inline void set_region_exec_freq(void *reg, double freq)
  74 {
  75   reg_exec_freq ef;
  76   ef.reg  = reg;
  77   ef.freq = freq;
  78   set_insert(exec_freq_set, &ef, sizeof(ef), exec_freq_hash(&ef));
  79 }
  80
  81 double get_region_exec_freq(void *reg)
  82 {
  83   reg_exec_freq ef, *found;
  84   ef.reg  = reg;
  85   assert(exec_freq_set);
  86
  87   found = set_find(exec_freq_set, &ef, sizeof(ef), exec_freq_hash(&ef));
  88
  89   /* Not found if information is invalid. */
  90   if (found)
  91     return found->freq;
  92   else
  93     return 0;
  94 }
  95
  96 /* Returns the number of times the block is executed. */
  97 double     get_Block_exec_freq(ir_node *b)
  98 {
  99   return get_region_exec_freq((void *)b);
 100 }
 101
 102 double get_irn_exec_freq(ir_node *n)
 103 {
 104   if (!is_Block(n)) n = get_nodes_block(n);
 105   return get_Block_exec_freq(n);
 106 }
 107
 108
 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 /*------------------------------------------------------------------*/
 118
 119 #include "irouts.h"
 120
 121 typedef enum {
 122   Cond_prob_none,
 123   Cond_prob_normal,
 124   Cond_prob_avoid_exception,
 125   Cond_prob_exception_taken,
 126   Cond_prob_was_exception_taken,
 127 } Cond_prob;
 128
 129 static int just_passed_a_Raise = 0;
 130 static ir_node *Cond_list = NULL;
 131
 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)
 134 {
 135   reg_exec_freq ef;
 136   ef.reg  = n;
 137   ef.prob = prob;
 138   set_insert(exec_freq_set, &ef, sizeof(ef), exec_freq_hash(&ef));
 139 }
 140
 141 Cond_prob get_ProjX_probability(ir_node *n)
 142 {
 143   reg_exec_freq ef, *found;
 144   ef.reg  = n;
 145
 146   found = set_find(exec_freq_set, &ef, sizeof(ef), exec_freq_hash(&ef));
 147
 148   if (found)
 149     return (Cond_prob)found->prob;
 150   else
 151     return Cond_prob_none;
 152 }
 153
 154 /* A walker that only visits the nodes we want to see. */
 155
 156 static void my_irg_walk_2_both(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void * env)
 157 {
 158   int i;
 159   set_irn_visited(node, current_ir_graph->visited);
 160
 161   pre(node, env);
 162
 163   if (node->op != op_Block) {
 164     ir_node *pred;
 165     if (node->op == op_Proj)
 166       pred = get_irn_n(node, 0);
 167     else
 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);
 171   }
 172
 173   else {  /* a Block */
 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);
 178     }
 179   }
 180
 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);
 186     }
 187   }
 188
 189   post(node, env);
 190 }
 191 static void my_irg_walk_current_graph(irg_walk_func *pre, irg_walk_func *post, void *env)
 192 {
 193   inc_irg_visited(current_ir_graph);
 194   my_irg_walk_2_both(get_irg_end(current_ir_graph), pre, post, env);
 195 }
 196
 197
 198 static void walk_pre(ir_node *n, void *env)
 199 {
 200   (void) env;
 201   if (is_Raise(n))
 202     just_passed_a_Raise = 1;
 203
 204   if (get_irn_op(n) == op_Proj  &&
 205       is_Cond(get_Proj_pred(n)) &&
 206       just_passed_a_Raise) {
 207     ir_node *other_proj;
 208     ir_node *c = get_Proj_pred(n);
 209
 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. */
 218     } else {
 219       set_ProjX_probability(n, Cond_prob_exception_taken);
 220       just_passed_a_Raise = 0;
 221     }
 222   }
 223
 224   if (is_Cond(n)) {
 225     set_irn_link(n, Cond_list);
 226     Cond_list = n;
 227   }
 228 }
 229
 230 static void walk_post(ir_node *n, void *env)
 231 {
 232   (void) env;
 233   if (is_Raise(n))
 234     just_passed_a_Raise = 0;
 235
 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
 240       )) {
 241     just_passed_a_Raise = 1;
 242   }
 243 }
 244
 245 /** Precompute which Conds test for an exception.
 246  *
 247  *  Operates on current_ir_graph. */
 248 void precompute_cond_evaluation(void)
 249 {
 250   ir_node *c;
 251
 252   compute_irg_outs(current_ir_graph);
 253
 254   just_passed_a_Raise = 0;
 255   Cond_list = NULL;
 256   my_irg_walk_current_graph(walk_pre, walk_post, NULL);
 257
 258   for (c = Cond_list; c; c = get_irn_link(c)) {
 259     ir_node *p0, *p1;
 260
 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);
 264
 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!");
 269       /* It's a */
 270       set_ProjX_probability(p0, Cond_prob_normal);
 271       set_ProjX_probability(p1, Cond_prob_normal);
 272     }
 273
 274     /* p0 is exception */
 275     else if (get_ProjX_probability(p0) == Cond_prob_exception_taken) {
 276       set_ProjX_probability(p1, Cond_prob_avoid_exception);
 277     }
 278
 279     /* p1 is exception */
 280     else if (get_ProjX_probability(p1) == Cond_prob_exception_taken) {
 281       set_ProjX_probability(p0, Cond_prob_avoid_exception);
 282     }
 283
 284     /* none is exception */
 285     else {
 286       set_ProjX_probability(p0, Cond_prob_normal);
 287       set_ProjX_probability(p1, Cond_prob_normal);
 288     }
 289   }
 290 }
 291
 292 int is_fragile_Proj(ir_node *n)
 293 {
 294   return is_Proj(n) && (get_ProjX_probability(n) == Cond_prob_exception_taken);
 295 }
 296
 297 /*------------------------------------------------------------------*/
 298 /* The algorithm to compute the execution frequencies.
 299  *
 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 /*------------------------------------------------------------------*/
 305
 306 static double exception_prob = 0.001;
 307
 308 static inline int is_loop_head(ir_node *cond)
 309 {
 310   (void) cond;
 311   return 0;
 312 }
 313
 314 /** Weight a single region in edge.
 315  *
 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)
 319 {
 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);
 324
 325   ir_node *cfop;
 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);
 330   } else {
 331     assert(is_ir_loop(reg));
 332     cfop = get_loop_cfop(reg, pos);
 333   }
 334
 335   if (is_fragile_op(cfop) || is_fragile_Proj(cfop)) {
 336     res = full_freq * exception_prob;
 337   } else {
 338
 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);
 341   }
 342
 343   return res;
 344 }
 345
 346 static inline void compute_region_freqency(void *reg, double head_weight)
 347 {
 348   int i, n_ins = get_region_n_ins(reg);
 349   double my_freq = 0;
 350
 351   //printf("head weight %lf: ", head_weight); DDMR(reg);
 352
 353   for (i = 0; i < n_ins; ++i) {
 354     void *pred_reg = get_region_in(reg, i);
 355     if (pred_reg) {
 356       my_freq += get_weighted_region_exec_freq(reg, i);
 357     }
 358   }
 359
 360   if (my_freq == 0.0) {
 361     /* All preds are from outer loop. We are a head or so. */
 362     my_freq = head_weight;
 363   }
 364   set_region_exec_freq(reg, my_freq);
 365 }
 366
 367 static void check_proper_head(ir_loop *l, void *reg)
 368 {
 369   int i, n_ins = get_region_n_ins(reg);
 370   (void) l;
 371   for (i = 0; i < n_ins; ++i) {
 372     assert(!get_region_in(reg, i));
 373   }
 374 }
 375
 376 /* Compute the ex freq for current_ir_graph */
 377 static void compute_frequency(int default_loop_weight)
 378 {
 379   ir_loop *outermost_l = get_irg_loop(current_ir_graph);
 380   pdeq *block_worklist = new_pdeq1(outermost_l);
 381
 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);
 385
 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);
 389
 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);
 392
 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));
 397     }
 398   }
 399   del_pdeq(block_worklist);
 400 }
 401
 402 /* Compute the execution frequency for all blocks in the given
 403  * graph.
 404  *
 405  * irg:                 The graph to be analyzed.
 406  * default_loop_weight: The number of executions of a loop.
 407  */
 408 void compute_execution_frequency(ir_graph *irg, int default_loop_weight, double exception_probability)
 409 {
 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);
 414
 415   precompute_cond_evaluation();
 416   construct_intervals(current_ir_graph);
 417   compute_frequency(default_loop_weight);
 418
 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);
 422
 423   /*
 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");
 427   */
 428
 429   current_ir_graph = rem;
 430 }
 431
 432
 433 void compute_execution_frequencies(int default_loop_weight, double exception_probability)
 434 {
 435   int i, n_irgs = get_irp_n_irgs();
 436   free_intervals();
 437   for (i = 0; i < n_irgs; ++i) {
 438     compute_execution_frequency(get_irp_irg(i), default_loop_weight, exception_probability);
 439   }
 440   set_irp_exec_freq_state(exec_freq_consistent);
 441 }
 442
 443 /** free occupied memory, reset */
 444 void free_execution_frequency(void)
 445 {
 446   int i, n_irgs = get_irp_n_irgs();
 447   free_intervals();
 448   del_set(exec_freq_set);
 449
 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);
 453 }
 454
 455 exec_freq_state get_irg_exec_freq_state(ir_graph *irg)
 456 {
 457   return irg->execfreq_state;
 458 }
 459 void            set_irg_exec_freq_state(ir_graph *irg, exec_freq_state s)
 460 {
 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;
 465 }
 466
 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)
 469 {
 470   if (get_irg_exec_freq_state(irg) == exec_freq_consistent)
 471     set_irg_exec_freq_state(irg, exec_freq_inconsistent);
 472 }
 473
 474 void set_irp_exec_freq_state(exec_freq_state s)
 475 {
 476   irp->execfreq_state = s;
 477 }
 478
 479 exec_freq_state get_irp_exec_freq_state(void)
 480 {
 481   return irp->execfreq_state;
 482 }
 483
 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)
 486 {
 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;
 494     }
 495   }
 496 }