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

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