execution_frequency.c 13.8 KB
Newer Older
1
/*
Michael Beck's avatar
Michael Beck committed
2
 * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
Matthias Braun's avatar
Matthias Braun committed
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
 */

/**
 * @file
 * @brief     Compute an estimate of basic block executions.
 * @author    Goetz Lindenmaier
 * @date      5.11.2004
 * @version   $Id$
26
 */
Michael Beck's avatar
Michael Beck committed
27
#include "config.h"
28
29
30
31
32

#include "execution_frequency.h"

#include "set.h"
#include "pdeq.h"
Michael Beck's avatar
Michael Beck committed
33
#include "hashptr.h"
34
#include "error.h"
35

Götz Lindenmaier's avatar
Götz Lindenmaier committed
36
37
#include "irprog_t.h"
#include "irgraph_t.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
38
#include "irnode_t.h"
39
#include "irloop.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
40
#include "irgwalk.h"
41
42
43

#include "interval_analysis.h"

Götz Lindenmaier's avatar
Götz Lindenmaier committed
44
45
void set_irp_exec_freq_state(exec_freq_state s);

46
47
48
49
50
51
52
53
/*------------------------------------------------------------------*/
/* A hashmap mapping the frequency to block and loop nodes.  Block
 * and loop nodes are regions.                                      */
/*------------------------------------------------------------------*/

typedef struct {
  void   *reg;
  double  freq;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
54
  int     prob;
55
56
57
58
59
} reg_exec_freq;

/* We use this set for all nodes in all irgraphs. */
static set *exec_freq_set = NULL;

60
61
static int exec_freq_cmp(const void *e1, const void *e2, size_t size)
{
62
63
  reg_exec_freq *ef1 = (reg_exec_freq *)e1;
  reg_exec_freq *ef2 = (reg_exec_freq *)e2;
Matthias Braun's avatar
Matthias Braun committed
64
65
  (void) size;

66
67
68
  return (ef1->reg != ef2->reg);
}

69
70
static inline unsigned int exec_freq_hash(reg_exec_freq *e)
{
Michael Beck's avatar
Michael Beck committed
71
  return HASH_PTR(e->reg);
72
73
}

74
75
static inline void set_region_exec_freq(void *reg, double freq)
{
76
77
78
79
80
81
  reg_exec_freq ef;
  ef.reg  = reg;
  ef.freq = freq;
  set_insert(exec_freq_set, &ef, sizeof(ef), exec_freq_hash(&ef));
}

82
83
double get_region_exec_freq(void *reg)
{
84
85
  reg_exec_freq ef, *found;
  ef.reg  = reg;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
86
  assert(exec_freq_set);
87

88
  found = (reg_exec_freq*) set_find(exec_freq_set, &ef, sizeof(ef), exec_freq_hash(&ef));
Götz Lindenmaier's avatar
Götz Lindenmaier committed
89
90
91
92
93
94

  /* Not found if information is invalid. */
  if (found)
    return found->freq;
  else
    return 0;
95
96
97
}

/* Returns the number of times the block is executed. */
98
99
double     get_Block_exec_freq(ir_node *b)
{
100
101
102
  return get_region_exec_freq((void *)b);
}

103
104
double get_irn_exec_freq(ir_node *n)
{
105
106
107
108
  if (!is_Block(n)) n = get_nodes_block(n);
  return get_Block_exec_freq(n);
}

109

Götz Lindenmaier's avatar
Götz Lindenmaier committed
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
/*------------------------------------------------------------------*/
/* A algorithm that precomputes whether Conds lead to an exception.
 * Computes a field for all Projs from Conds that says the following:
 *   - The Proj projs from a normal dual Cond with probability 50:50
 *   - This Proj of the Cond leads to an exception, i.e., a raise node.
 *     It is taken with exception probability.
 *   - The Proj of the Cond avoids an exception.  It is taken with
 *     1 - exception probability.                                   */
/*------------------------------------------------------------------*/

#include "irouts.h"

typedef enum {
  Cond_prob_none,
  Cond_prob_normal,
  Cond_prob_avoid_exception,
  Cond_prob_exception_taken,
  Cond_prob_was_exception_taken,
} Cond_prob;

static int just_passed_a_Raise = 0;
static ir_node *Cond_list = NULL;

/* 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
{
Götz Lindenmaier's avatar
Götz Lindenmaier committed
136
137
138
139
140
141
  reg_exec_freq ef;
  ef.reg  = n;
  ef.prob = prob;
  set_insert(exec_freq_set, &ef, sizeof(ef), exec_freq_hash(&ef));
}

142
static Cond_prob get_ProjX_probability(ir_node *n)
143
{
Götz Lindenmaier's avatar
Götz Lindenmaier committed
144
145
146
  reg_exec_freq ef, *found;
  ef.reg  = n;

147
  found = (reg_exec_freq*) set_find(exec_freq_set, &ef, sizeof(ef), exec_freq_hash(&ef));
Götz Lindenmaier's avatar
Götz Lindenmaier committed
148
149
150
151
152
153
154
155
156

  if (found)
    return (Cond_prob)found->prob;
  else
    return Cond_prob_none;
}

/* A walker that only visits the nodes we want to see. */

157
static void my_irg_walk_2_both(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void * env)
158
{
Götz Lindenmaier's avatar
Götz Lindenmaier committed
159
160
161
162
163
  int i;
  set_irn_visited(node, current_ir_graph->visited);

  pre(node, env);

164
  if (!is_Block(node)) {
Götz Lindenmaier's avatar
Götz Lindenmaier committed
165
    ir_node *pred;
166
    if (is_Proj(node))
Götz Lindenmaier's avatar
Götz Lindenmaier committed
167
168
      pred = get_irn_n(node, 0);
    else
169
      pred = get_irn_n(node, -1);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
170
171
172
173
174
175
176
177
    if (pred->visited < current_ir_graph->visited)
      my_irg_walk_2_both(pred, pre, post, env);
  }

  else {  /* a Block */
    for (i = get_irn_arity(node) - 1; i >= 0; --i) {
      ir_node *pred = get_irn_n(node, i);
      if (pred->visited < current_ir_graph->visited)
Michael Beck's avatar
Michael Beck committed
178
        my_irg_walk_2_both(pred, pre, post, env);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
179
180
181
    }
  }

182
  if (is_End(node)) {
Götz Lindenmaier's avatar
Götz Lindenmaier committed
183
184
185
    for (i = get_irn_arity(node) - 1; i >= 0; --i) {
      ir_node *pred = get_irn_n(node, i);
      if ((pred->op == op_Block) && (pred->visited < current_ir_graph->visited))
Michael Beck's avatar
Michael Beck committed
186
        my_irg_walk_2_both(pred, pre, post, env);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
187
188
189
190
191
    }
  }

  post(node, env);
}
192
193
static void my_irg_walk_current_graph(irg_walk_func *pre, irg_walk_func *post, void *env)
{
Götz Lindenmaier's avatar
Götz Lindenmaier committed
194
195
196
197
198
  inc_irg_visited(current_ir_graph);
  my_irg_walk_2_both(get_irg_end(current_ir_graph), pre, post, env);
}


Matthias Braun's avatar
Matthias Braun committed
199
200
201
static void walk_pre(ir_node *n, void *env)
{
  (void) env;
202
  if (is_Raise(n))
Götz Lindenmaier's avatar
Götz Lindenmaier committed
203
204
    just_passed_a_Raise = 1;

205
206
207
  if (get_irn_op(n) == op_Proj  &&
      is_Cond(get_Proj_pred(n)) &&
      just_passed_a_Raise) {
Michael Beck's avatar
Michael Beck committed
208
    ir_node *other_proj;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
209
210
211
212
213
    ir_node *c = get_Proj_pred(n);

    /* If we already visited the other Proj, and it also leads to a Raise,
       we are in the middle of something. Continue searching. */
    assert(get_irn_n_outs(c) == 2 && "encountered a switch cond");
Michael Beck's avatar
Michael Beck committed
214
    other_proj = get_irn_out(c, 0);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
215
216
217
218
219
220
221
222
223
224
    if (other_proj == n) other_proj = get_irn_out(c, 1);
    if (get_ProjX_probability(other_proj) == Cond_prob_exception_taken) {
      set_ProjX_probability(other_proj, Cond_prob_was_exception_taken);
      /* Keep searching for the Proj, so keep just_passed_a_Raise. */
    } else {
      set_ProjX_probability(n, Cond_prob_exception_taken);
      just_passed_a_Raise = 0;
    }
  }

225
  if (is_Cond(n)) {
Götz Lindenmaier's avatar
Götz Lindenmaier committed
226
227
228
229
230
    set_irn_link(n, Cond_list);
    Cond_list = n;
  }
}

Matthias Braun's avatar
Matthias Braun committed
231
232
233
static void walk_post(ir_node *n, void *env)
{
  (void) env;
234
  if (is_Raise(n))
Götz Lindenmaier's avatar
Götz Lindenmaier committed
235
236
    just_passed_a_Raise = 0;

237
238
239
240
241
  if (get_irn_op(n) == op_Proj  &&
      is_Cond(get_Proj_pred(n)) && (
        get_ProjX_probability(n) == Cond_prob_exception_taken ||
        get_ProjX_probability(n) == Cond_prob_was_exception_taken
      )) {
Götz Lindenmaier's avatar
Götz Lindenmaier committed
242
243
244
245
246
247
248
    just_passed_a_Raise = 1;
  }
}

/** Precompute which Conds test for an exception.
 *
 *  Operates on current_ir_graph. */
249
static void precompute_cond_evaluation(void)
250
{
Götz Lindenmaier's avatar
Götz Lindenmaier committed
251
252
  ir_node *c;

Götz Lindenmaier's avatar
Götz Lindenmaier committed
253
  compute_irg_outs(current_ir_graph);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
254
255
256
257
258

  just_passed_a_Raise = 0;
  Cond_list = NULL;
  my_irg_walk_current_graph(walk_pre, walk_post, NULL);

259
  for (c = Cond_list; c; c = (ir_node*)get_irn_link(c)) {
Michael Beck's avatar
Michael Beck committed
260
261
    ir_node *p0, *p1;

Götz Lindenmaier's avatar
Götz Lindenmaier committed
262
    assert(get_irn_n_outs(c) == 2 && "encountered a switch cond");
Michael Beck's avatar
Michael Beck committed
263
264
    p0 = get_irn_out(c, 0);
    p1 = get_irn_out(c, 1);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
265
266
267

    /* both are exceptions */
    if ((get_ProjX_probability(p0) == Cond_prob_exception_taken) &&
Michael Beck's avatar
Michael Beck committed
268
        (get_ProjX_probability(p1) == Cond_prob_exception_taken)   ) {
269
270
      panic("I tried to avoid these!");
#if 0
Götz Lindenmaier's avatar
Götz Lindenmaier committed
271
272
273
      /* It's a */
      set_ProjX_probability(p0, Cond_prob_normal);
      set_ProjX_probability(p1, Cond_prob_normal);
274
#endif
Götz Lindenmaier's avatar
Götz Lindenmaier committed
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
    }

    /* p0 is exception */
    else if (get_ProjX_probability(p0) == Cond_prob_exception_taken) {
      set_ProjX_probability(p1, Cond_prob_avoid_exception);
    }

    /* p1 is exception */
    else if (get_ProjX_probability(p1) == Cond_prob_exception_taken) {
      set_ProjX_probability(p0, Cond_prob_avoid_exception);
    }

    /* none is exception */
    else {
      set_ProjX_probability(p0, Cond_prob_normal);
      set_ProjX_probability(p1, Cond_prob_normal);
    }
  }
}

295
296
int is_fragile_Proj(ir_node *n)
{
Götz Lindenmaier's avatar
Götz Lindenmaier committed
297
298
299
  return is_Proj(n) && (get_ProjX_probability(n) == Cond_prob_exception_taken);
}

300
/*------------------------------------------------------------------*/
Michael Beck's avatar
Michael Beck committed
301
/* The algorithm to compute the execution frequencies.
302
303
304
305
306
307
308
309
310
 *
 * Walk the control flow loop tree which we consider the interval
 * tree.  Compute the execution for the lowest loop, add inner loops
 * to worklist.  Consider the inner loops as simple nodes.  Check that
 * there is only one loop header in each loop.                      */
/*------------------------------------------------------------------*/

static double exception_prob = 0.001;

311
static inline int is_loop_head(ir_node *cond)
Matthias Braun's avatar
Matthias Braun committed
312
313
{
  (void) cond;
314
  return 0;
315
316
}

Götz Lindenmaier's avatar
Götz Lindenmaier committed
317
318
319
320
/** Weight a single region in edge.
 *
 *  Given all outs of the predecessor region, we can compute the weight of
 *  this single edge. */
321
322
static inline double get_weighted_region_exec_freq(void *reg, int pos)
{
Götz Lindenmaier's avatar
Götz Lindenmaier committed
323
324
325
326
  void *pred_reg        = get_region_in(reg, pos);
  double res, full_freq = get_region_exec_freq (pred_reg);
  int n_outs            = get_region_n_outs    (pred_reg);
  int n_exc_outs        = get_region_n_exc_outs(pred_reg);
327
328
329

  ir_node *cfop;
  if (is_ir_node(reg)) {
Götz Lindenmaier's avatar
Götz Lindenmaier committed
330
    cfop = get_Block_cfgpred((ir_node *)reg, pos);
331
    if (is_Proj(cfop) && !is_Cond(get_Proj_pred(cfop)))
Götz Lindenmaier's avatar
Götz Lindenmaier committed
332
      cfop = skip_Proj(cfop);
333
334
  } else {
    assert(is_ir_loop(reg));
335
    cfop = (ir_node*)get_loop_cfop(reg, pos);
336
337
  }

Götz Lindenmaier's avatar
Götz Lindenmaier committed
338
  if (is_fragile_op(cfop) || is_fragile_Proj(cfop)) {
339
340
341
342
343
344
345
346
347
348
    res = full_freq * exception_prob;
  } else {

    /* Equally distribute the weight after exceptions to the left over outs. */
    res = (full_freq *(1 - exception_prob * n_exc_outs)) / (n_outs - n_exc_outs);
  }

  return res;
}

349
350
static inline void compute_region_freqency(void *reg, double head_weight)
{
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
  int i, n_ins = get_region_n_ins(reg);
  double my_freq = 0;

  for (i = 0; i < n_ins; ++i) {
    void *pred_reg = get_region_in(reg, i);
    if (pred_reg) {
      my_freq += get_weighted_region_exec_freq(reg, i);
    }
  }

  if (my_freq == 0.0) {
    /* All preds are from outer loop. We are a head or so. */
    my_freq = head_weight;
  }
  set_region_exec_freq(reg, my_freq);
}

Matthias Braun's avatar
Matthias Braun committed
368
369
static void check_proper_head(ir_loop *l, void *reg)
{
370
  int i, n_ins = get_region_n_ins(reg);
Matthias Braun's avatar
Matthias Braun committed
371
  (void) l;
372
373
374
375
376
377
  for (i = 0; i < n_ins; ++i) {
    assert(!get_region_in(reg, i));
  }
}

/* Compute the ex freq for current_ir_graph */
378
379
static void compute_frequency(int default_loop_weight)
{
380
381
382
  ir_loop *outermost_l = get_irg_loop(current_ir_graph);
  pdeq *block_worklist = new_pdeq1(outermost_l);

383
384
385
  /* Outermost start is considered a loop head.  We will soon multiply
     by default_loop_weight. */
  set_region_exec_freq(outermost_l, 1.0/default_loop_weight);
386
387
388

  while (!pdeq_empty(block_worklist)) {
    ir_loop *l = (ir_loop *)pdeq_getl(block_worklist);
Michael Beck's avatar
Michael Beck committed
389
    size_t i, n_elems = get_loop_n_elements(l);
390

Michael Beck's avatar
Michael Beck committed
391
    /* The header is initialized with the frequency of the full loop times the iteration weight. */
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
    check_proper_head(l, get_loop_element(l, 0).son);

    for (i = 0; i < n_elems; ++i) {
      loop_element e = get_loop_element(l, i);
      if (is_ir_loop(e.son)) pdeq_putr(block_worklist, e.son);
      compute_region_freqency(e.son, default_loop_weight * get_region_exec_freq(l));
    }
  }
  del_pdeq(block_worklist);
}

/* Compute the execution frequency for all blocks in the given
 * graph.
 *
 * irg:                 The graph to be analyzed.
 * default_loop_weight: The number of executions of a loop.
 */
409
410
void compute_execution_frequency(ir_graph *irg, int default_loop_weight, double exception_probability)
{
411
412
413
414
415
  ir_graph *rem = current_ir_graph;
  current_ir_graph = irg;
  exception_prob = exception_probability;
  if (!exec_freq_set) exec_freq_set = new_set(exec_freq_cmp, 256);

Götz Lindenmaier's avatar
Götz Lindenmaier committed
416
  precompute_cond_evaluation();
417
418
419
  construct_intervals(current_ir_graph);
  compute_frequency(default_loop_weight);

Götz Lindenmaier's avatar
Götz Lindenmaier committed
420
421
422
423
  set_irg_exec_freq_state(irg, exec_freq_consistent);
  if (get_irp_exec_freq_state() == exec_freq_none)
    set_irp_exec_freq_state(exec_freq_inconsistent);

424
  /*
425
426
427
    dump_loop_tree     (current_ir_graph, "-execfreq");
    dump_ir_block_graph(current_ir_graph, "-execfreq");
    dump_interval_graph(current_ir_graph, "-execfreq");
428
429
430
431
432
433
  */

  current_ir_graph = rem;
}


434
435
void compute_execution_frequencies(int default_loop_weight, double exception_probability)
{
Michael Beck's avatar
Michael Beck committed
436
  size_t i, n_irgs = get_irp_n_irgs();
437
438
439
440
  free_intervals();
  for (i = 0; i < n_irgs; ++i) {
    compute_execution_frequency(get_irp_irg(i), default_loop_weight, exception_probability);
  }
Götz Lindenmaier's avatar
Götz Lindenmaier committed
441
  set_irp_exec_freq_state(exec_freq_consistent);
442
443
444
}

/** free occupied memory, reset */
445
446
void free_execution_frequency(void)
{
Michael Beck's avatar
Michael Beck committed
447
  size_t i, n_irgs = get_irp_n_irgs();
448
449
  free_intervals();
  del_set(exec_freq_set);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
450
451
452
453
454
455

  for (i = 0; i < n_irgs; ++i)
    set_irg_exec_freq_state(get_irp_irg(i), exec_freq_none);
  set_irp_exec_freq_state(exec_freq_none);
}

456
457
exec_freq_state get_irg_exec_freq_state(ir_graph *irg)
{
Götz Lindenmaier's avatar
Götz Lindenmaier committed
458
459
  return irg->execfreq_state;
}
460
461
void            set_irg_exec_freq_state(ir_graph *irg, exec_freq_state s)
{
Götz Lindenmaier's avatar
Götz Lindenmaier committed
462
463
464
465
466
467
468
  if ((get_irp_exec_freq_state() == exec_freq_consistent && s != exec_freq_consistent) ||
      (get_irp_exec_freq_state() == exec_freq_none       && s != exec_freq_none))
    irp->execfreq_state = exec_freq_inconsistent;
  irg->execfreq_state = s;
}

/* Sets irg and irp exec freq state to inconsistent if it is set to consistent. */
469
470
void            set_irg_exec_freq_state_inconsistent(ir_graph *irg)
{
Götz Lindenmaier's avatar
Götz Lindenmaier committed
471
472
473
474
  if (get_irg_exec_freq_state(irg) == exec_freq_consistent)
    set_irg_exec_freq_state(irg, exec_freq_inconsistent);
}

475
476
void set_irp_exec_freq_state(exec_freq_state s)
{
Götz Lindenmaier's avatar
Götz Lindenmaier committed
477
478
479
  irp->execfreq_state = s;
}

480
481
exec_freq_state get_irp_exec_freq_state(void)
{
Götz Lindenmaier's avatar
Götz Lindenmaier committed
482
483
484
485
  return irp->execfreq_state;
}

/* Sets irp and all irg exec freq states to inconsistent if it is set to consistent. */
486
487
void            set_irp_exec_freq_state_inconsistent(void)
{
Michael Beck's avatar
Michael Beck committed
488
489
490
491
492
493
494
495
496
	if (get_irp_exec_freq_state() != exec_freq_none) {
		size_t i, n_irgs = get_irp_n_irgs();
		set_irp_exec_freq_state(exec_freq_inconsistent);
		for (i = 0; i < n_irgs; ++i) {
			ir_graph *irg = get_irp_irg(i);
			if (get_irg_exec_freq_state(irg) != exec_freq_none)
				irg->execfreq_state = exec_freq_inconsistent;
		}
	}
497
}