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