OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-old/] [gcc-4.2.2/] [gcc/] [value-prof.c] - Blame information for rev 816

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 38 julius
/* Transformations based on profile information for values.
2
   Copyright (C) 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
3
 
4
This file is part of GCC.
5
 
6
GCC is free software; you can redistribute it and/or modify it under
7
the terms of the GNU General Public License as published by the Free
8
Software Foundation; either version 3, or (at your option) any later
9
version.
10
 
11
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12
WARRANTY; without even the implied warranty of MERCHANTABILITY or
13
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14
for more details.
15
 
16
You should have received a copy of the GNU General Public License
17
along with GCC; see the file COPYING3.  If not see
18
<http://www.gnu.org/licenses/>.  */
19
 
20
#include "config.h"
21
#include "system.h"
22
#include "coretypes.h"
23
#include "tm.h"
24
#include "rtl.h"
25
#include "expr.h"
26
#include "hard-reg-set.h"
27
#include "basic-block.h"
28
#include "value-prof.h"
29
#include "output.h"
30
#include "flags.h"
31
#include "insn-config.h"
32
#include "recog.h"
33
#include "optabs.h"
34
#include "regs.h"
35
#include "ggc.h"
36
#include "tree-flow.h"
37
#include "tree-flow-inline.h"
38
#include "diagnostic.h"
39
#include "coverage.h"
40
#include "tree.h"
41
#include "gcov-io.h"
42
#include "timevar.h"
43
#include "tree-pass.h"
44
#include "toplev.h"
45
 
46
static struct value_prof_hooks *value_prof_hooks;
47
 
48
/* In this file value profile based optimizations are placed.  Currently the
49
   following optimizations are implemented (for more detailed descriptions
50
   see comments at value_profile_transformations):
51
 
52
   1) Division/modulo specialization.  Provided that we can determine that the
53
      operands of the division have some special properties, we may use it to
54
      produce more effective code.
55
   2) Speculative prefetching.  If we are able to determine that the difference
56
      between addresses accessed by a memory reference is usually constant, we
57
      may add the prefetch instructions.
58
      FIXME: This transformation was removed together with RTL based value
59
      profiling.
60
 
61
   Every such optimization should add its requirements for profiled values to
62
   insn_values_to_profile function.  This function is called from branch_prob
63
   in profile.c and the requested values are instrumented by it in the first
64
   compilation with -fprofile-arcs.  The optimization may then read the
65
   gathered data in the second compilation with -fbranch-probabilities.
66
 
67
   The measured data is pointed to from the histograms
68
   field of the statement annotation of the instrumented insns.  It is
69
   kept as a linked list of struct histogram_value_t's, which contain the
70
   same information as above.  */
71
 
72
 
73
static tree tree_divmod_fixed_value (tree, tree, tree, tree,
74
                                    tree, int, gcov_type, gcov_type);
75
static tree tree_mod_pow2 (tree, tree, tree, tree, int, gcov_type, gcov_type);
76
static tree tree_mod_subtract (tree, tree, tree, tree, int, int, int,
77
                                gcov_type, gcov_type, gcov_type);
78
static bool tree_divmod_fixed_value_transform (tree);
79
static bool tree_mod_pow2_value_transform (tree);
80
static bool tree_mod_subtract_transform (tree);
81
 
82
/* The overall number of invocations of the counter should match execution count
83
   of basic block.  Report it as error rather than internal error as it might
84
   mean that user has misused the profile somehow.  */
85
static bool
86
check_counter (tree stmt, const char * name, gcov_type all, gcov_type bb_count)
87
{
88
  if (all != bb_count)
89
    {
90
      location_t * locus;
91
      locus = (stmt != NULL && EXPR_HAS_LOCATION (stmt)
92
               ? EXPR_LOCUS (stmt)
93
               : &DECL_SOURCE_LOCATION (current_function_decl));
94
      error ("%HCorrupted value profile: %s profiler overall count (%d) does not match BB count (%d)",
95
             locus, name, (int)all, (int)bb_count);
96
      return true;
97
    }
98
  return false;
99
}
100
 
101
/* Tree based transformations. */
102
static bool
103
tree_value_profile_transformations (void)
104
{
105
  basic_block bb;
106
  block_stmt_iterator bsi;
107
  bool changed = false;
108
 
109
  FOR_EACH_BB (bb)
110
    {
111
      /* Ignore cold areas -- we are enlarging the code.  */
112
      if (!maybe_hot_bb_p (bb))
113
        continue;
114
 
115
      for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
116
        {
117
          tree stmt = bsi_stmt (bsi);
118
          stmt_ann_t ann = get_stmt_ann (stmt);
119
          histogram_value th = ann->histograms;
120
          if (!th)
121
            continue;
122
 
123
          if (dump_file)
124
            {
125
              fprintf (dump_file, "Trying transformations on insn ");
126
              print_generic_stmt (dump_file, stmt, TDF_SLIM);
127
            }
128
 
129
          /* Transformations:  */
130
          /* The order of things in this conditional controls which
131
             transformation is used when more than one is applicable.  */
132
          /* It is expected that any code added by the transformations
133
             will be added before the current statement, and that the
134
             current statement remain valid (although possibly
135
             modified) upon return.  */
136
          if (flag_value_profile_transformations
137
              && (tree_mod_subtract_transform (stmt)
138
                  || tree_divmod_fixed_value_transform (stmt)
139
                  || tree_mod_pow2_value_transform (stmt)))
140
            {
141
              changed = true;
142
              /* Original statement may no longer be in the same block. */
143
              if (bb != bb_for_stmt (stmt))
144
                {
145
                  bb = bb_for_stmt (stmt);
146
                  bsi = bsi_for_stmt (stmt);
147
                }
148
            }
149
 
150
          /* Free extra storage from compute_value_histograms.  */
151
          while (th)
152
            {
153
              free (th->hvalue.counters);
154
              th = th->hvalue.next;
155
            }
156
          ann->histograms = 0;
157
        }
158
    }
159
 
160
  if (changed)
161
    {
162
      counts_to_freqs ();
163
    }
164
 
165
  return changed;
166
}
167
 
168
/* Generate code for transformation 1 (with OPERATION, operands OP1
169
   and OP2, whose value is expected to be VALUE, parent modify-expr STMT and
170
   probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
171
   within roundoff error).  This generates the result into a temp and returns
172
   the temp; it does not replace or alter the original STMT.  */
173
static tree
174
tree_divmod_fixed_value (tree stmt, tree operation,
175
                         tree op1, tree op2, tree value, int prob, gcov_type count,
176
                         gcov_type all)
177
{
178
  tree stmt1, stmt2, stmt3;
179
  tree tmp1, tmp2, tmpv;
180
  tree label_decl1 = create_artificial_label ();
181
  tree label_decl2 = create_artificial_label ();
182
  tree label_decl3 = create_artificial_label ();
183
  tree label1, label2, label3;
184
  tree bb1end, bb2end, bb3end;
185
  basic_block bb, bb2, bb3, bb4;
186
  tree optype = TREE_TYPE (operation);
187
  edge e12, e13, e23, e24, e34;
188
  block_stmt_iterator bsi;
189
 
190
  bb = bb_for_stmt (stmt);
191
  bsi = bsi_for_stmt (stmt);
192
 
193
  tmpv = create_tmp_var (optype, "PROF");
194
  tmp1 = create_tmp_var (optype, "PROF");
195
  stmt1 = build2 (MODIFY_EXPR, optype, tmpv, fold_convert (optype, value));
196
  stmt2 = build2 (MODIFY_EXPR, optype, tmp1, op2);
197
  stmt3 = build3 (COND_EXPR, void_type_node,
198
            build2 (NE_EXPR, boolean_type_node, tmp1, tmpv),
199
            build1 (GOTO_EXPR, void_type_node, label_decl2),
200
            build1 (GOTO_EXPR, void_type_node, label_decl1));
201
  bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
202
  bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
203
  bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
204
  bb1end = stmt3;
205
 
206
  tmp2 = create_tmp_var (optype, "PROF");
207
  label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
208
  stmt1 = build2 (MODIFY_EXPR, optype, tmp2,
209
                  build2 (TREE_CODE (operation), optype, op1, tmpv));
210
  bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
211
  bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
212
  bb2end = stmt1;
213
 
214
  label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
215
  stmt1 = build2 (MODIFY_EXPR, optype, tmp2,
216
                  build2 (TREE_CODE (operation), optype, op1, op2));
217
  bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
218
  bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
219
  bb3end = stmt1;
220
 
221
  label3 = build1 (LABEL_EXPR, void_type_node, label_decl3);
222
  bsi_insert_before (&bsi, label3, BSI_SAME_STMT);
223
 
224
  /* Fix CFG. */
225
  /* Edge e23 connects bb2 to bb3, etc. */
226
  e12 = split_block (bb, bb1end);
227
  bb2 = e12->dest;
228
  bb2->count = count;
229
  e23 = split_block (bb2, bb2end);
230
  bb3 = e23->dest;
231
  bb3->count = all - count;
232
  e34 = split_block (bb3, bb3end);
233
  bb4 = e34->dest;
234
  bb4->count = all;
235
 
236
  e12->flags &= ~EDGE_FALLTHRU;
237
  e12->flags |= EDGE_FALSE_VALUE;
238
  e12->probability = prob;
239
  e12->count = count;
240
 
241
  e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
242
  e13->probability = REG_BR_PROB_BASE - prob;
243
  e13->count = all - count;
244
 
245
  remove_edge (e23);
246
 
247
  e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
248
  e24->probability = REG_BR_PROB_BASE;
249
  e24->count = count;
250
 
251
  e34->probability = REG_BR_PROB_BASE;
252
  e34->count = all - count;
253
 
254
  return tmp2;
255
}
256
 
257
/* Do transform 1) on INSN if applicable.  */
258
static bool
259
tree_divmod_fixed_value_transform (tree stmt)
260
{
261
  stmt_ann_t ann = get_stmt_ann (stmt);
262
  histogram_value histogram;
263
  enum tree_code code;
264
  gcov_type val, count, all;
265
  tree modify, op, op1, op2, result, value, tree_val;
266
  int prob;
267
 
268
  modify = stmt;
269
  if (TREE_CODE (stmt) == RETURN_EXPR
270
      && TREE_OPERAND (stmt, 0)
271
      && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR)
272
    modify = TREE_OPERAND (stmt, 0);
273
  if (TREE_CODE (modify) != MODIFY_EXPR)
274
    return false;
275
  op = TREE_OPERAND (modify, 1);
276
  if (!INTEGRAL_TYPE_P (TREE_TYPE (op)))
277
    return false;
278
  code = TREE_CODE (op);
279
 
280
  if (code != TRUNC_DIV_EXPR && code != TRUNC_MOD_EXPR)
281
    return false;
282
 
283
  op1 = TREE_OPERAND (op, 0);
284
  op2 = TREE_OPERAND (op, 1);
285
  if (!ann->histograms)
286
    return false;
287
 
288
  for (histogram = ann->histograms; histogram; histogram = histogram->hvalue.next)
289
    if (histogram->type == HIST_TYPE_SINGLE_VALUE)
290
      break;
291
 
292
  if (!histogram)
293
    return false;
294
 
295
  value = histogram->hvalue.value;
296
  val = histogram->hvalue.counters[0];
297
  count = histogram->hvalue.counters[1];
298
  all = histogram->hvalue.counters[2];
299
 
300
  /* We require that count is at least half of all; this means
301
     that for the transformation to fire the value must be constant
302
     at least 50% of time (and 75% gives the guarantee of usage).  */
303
  if (simple_cst_equal (op2, value) != 1 || 2 * count < all)
304
    return false;
305
 
306
  if (check_counter (stmt, "value", all, bb_for_stmt (stmt)->count))
307
    return false;
308
 
309
  /* Compute probability of taking the optimal path.  */
310
  prob = (count * REG_BR_PROB_BASE + all / 2) / all;
311
 
312
  tree_val = build_int_cst_wide (get_gcov_type (),
313
                                 (unsigned HOST_WIDE_INT) val,
314
                                 val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1);
315
  result = tree_divmod_fixed_value (stmt, op, op1, op2, tree_val, prob, count, all);
316
 
317
  if (dump_file)
318
    {
319
      fprintf (dump_file, "Div/mod by constant ");
320
      print_generic_expr (dump_file, value, TDF_SLIM);
321
      fprintf (dump_file, "=");
322
      print_generic_expr (dump_file, tree_val, TDF_SLIM);
323
      fprintf (dump_file, " transformation on insn ");
324
      print_generic_stmt (dump_file, stmt, TDF_SLIM);
325
    }
326
 
327
  TREE_OPERAND (modify, 1) = result;
328
 
329
  return true;
330
}
331
 
332
/* Generate code for transformation 2 (with OPERATION, operands OP1
333
   and OP2, parent modify-expr STMT and probability of taking the optimal
334
   path PROB, which is equivalent to COUNT/ALL within roundoff error).
335
   This generates the result into a temp and returns
336
   the temp; it does not replace or alter the original STMT.  */
337
static tree
338
tree_mod_pow2 (tree stmt, tree operation, tree op1, tree op2, int prob,
339
               gcov_type count, gcov_type all)
340
{
341
  tree stmt1, stmt2, stmt3, stmt4;
342
  tree tmp2, tmp3;
343
  tree label_decl1 = create_artificial_label ();
344
  tree label_decl2 = create_artificial_label ();
345
  tree label_decl3 = create_artificial_label ();
346
  tree label1, label2, label3;
347
  tree bb1end, bb2end, bb3end;
348
  basic_block bb, bb2, bb3, bb4;
349
  tree optype = TREE_TYPE (operation);
350
  edge e12, e13, e23, e24, e34;
351
  block_stmt_iterator bsi;
352
  tree result = create_tmp_var (optype, "PROF");
353
 
354
  bb = bb_for_stmt (stmt);
355
  bsi = bsi_for_stmt (stmt);
356
 
357
  tmp2 = create_tmp_var (optype, "PROF");
358
  tmp3 = create_tmp_var (optype, "PROF");
359
  stmt2 = build2 (MODIFY_EXPR, optype, tmp2,
360
                  build2 (PLUS_EXPR, optype, op2, build_int_cst (optype, -1)));
361
  stmt3 = build2 (MODIFY_EXPR, optype, tmp3,
362
                  build2 (BIT_AND_EXPR, optype, tmp2, op2));
363
  stmt4 = build3 (COND_EXPR, void_type_node,
364
                  build2 (NE_EXPR, boolean_type_node,
365
                          tmp3, build_int_cst (optype, 0)),
366
                  build1 (GOTO_EXPR, void_type_node, label_decl2),
367
                  build1 (GOTO_EXPR, void_type_node, label_decl1));
368
  bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
369
  bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
370
  bsi_insert_before (&bsi, stmt4, BSI_SAME_STMT);
371
  bb1end = stmt4;
372
 
373
  /* tmp2 == op2-1 inherited from previous block */
374
  label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
375
  stmt1 = build2 (MODIFY_EXPR, optype, result,
376
                  build2 (BIT_AND_EXPR, optype, op1, tmp2));
377
  bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
378
  bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
379
  bb2end = stmt1;
380
 
381
  label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
382
  stmt1 = build2 (MODIFY_EXPR, optype, result,
383
                  build2 (TREE_CODE (operation), optype, op1, op2));
384
  bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
385
  bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
386
  bb3end = stmt1;
387
 
388
  label3 = build1 (LABEL_EXPR, void_type_node, label_decl3);
389
  bsi_insert_before (&bsi, label3, BSI_SAME_STMT);
390
 
391
  /* Fix CFG. */
392
  /* Edge e23 connects bb2 to bb3, etc. */
393
  e12 = split_block (bb, bb1end);
394
  bb2 = e12->dest;
395
  bb2->count = count;
396
  e23 = split_block (bb2, bb2end);
397
  bb3 = e23->dest;
398
  bb3->count = all - count;
399
  e34 = split_block (bb3, bb3end);
400
  bb4 = e34->dest;
401
  bb4->count = all;
402
 
403
  e12->flags &= ~EDGE_FALLTHRU;
404
  e12->flags |= EDGE_FALSE_VALUE;
405
  e12->probability = prob;
406
  e12->count = count;
407
 
408
  e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
409
  e13->probability = REG_BR_PROB_BASE - prob;
410
  e13->count = all - count;
411
 
412
  remove_edge (e23);
413
 
414
  e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
415
  e24->probability = REG_BR_PROB_BASE;
416
  e24->count = count;
417
 
418
  e34->probability = REG_BR_PROB_BASE;
419
  e34->count = all - count;
420
 
421
  return result;
422
}
423
 
424
/* Do transform 2) on INSN if applicable.  */
425
static bool
426
tree_mod_pow2_value_transform (tree stmt)
427
{
428
  stmt_ann_t ann = get_stmt_ann (stmt);
429
  histogram_value histogram;
430
  enum tree_code code;
431
  gcov_type count, wrong_values, all;
432
  tree modify, op, op1, op2, result, value;
433
  int prob;
434
 
435
  modify = stmt;
436
  if (TREE_CODE (stmt) == RETURN_EXPR
437
      && TREE_OPERAND (stmt, 0)
438
      && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR)
439
    modify = TREE_OPERAND (stmt, 0);
440
  if (TREE_CODE (modify) != MODIFY_EXPR)
441
    return false;
442
  op = TREE_OPERAND (modify, 1);
443
  if (!INTEGRAL_TYPE_P (TREE_TYPE (op)))
444
    return false;
445
  code = TREE_CODE (op);
446
 
447
  if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (TREE_TYPE (op)))
448
    return false;
449
 
450
  op1 = TREE_OPERAND (op, 0);
451
  op2 = TREE_OPERAND (op, 1);
452
  if (!ann->histograms)
453
    return false;
454
 
455
  for (histogram = ann->histograms; histogram; histogram = histogram->hvalue.next)
456
    if (histogram->type == HIST_TYPE_POW2)
457
      break;
458
 
459
  if (!histogram)
460
    return false;
461
 
462
  value = histogram->hvalue.value;
463
  wrong_values = histogram->hvalue.counters[0];
464
  count = histogram->hvalue.counters[1];
465
 
466
  /* We require that we hit a power of 2 at least half of all evaluations.  */
467
  if (simple_cst_equal (op2, value) != 1 || count < wrong_values)
468
    return false;
469
 
470
  if (dump_file)
471
    {
472
      fprintf (dump_file, "Mod power of 2 transformation on insn ");
473
      print_generic_stmt (dump_file, stmt, TDF_SLIM);
474
    }
475
 
476
  /* Compute probability of taking the optimal path.  */
477
  all = count + wrong_values;
478
  if (check_counter (stmt, "pow2", all, bb_for_stmt (stmt)->count))
479
    return false;
480
 
481
  prob = (count * REG_BR_PROB_BASE + all / 2) / all;
482
 
483
  result = tree_mod_pow2 (stmt, op, op1, op2, prob, count, all);
484
 
485
  TREE_OPERAND (modify, 1) = result;
486
 
487
  return true;
488
}
489
 
490
/* Generate code for transformations 3 and 4 (with OPERATION, operands OP1
491
   and OP2, parent modify-expr STMT, and NCOUNTS the number of cases to
492
   support.  Currently only NCOUNTS==0 or 1 is supported and this is
493
   built into this interface.  The probabilities of taking the optimal
494
   paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
495
   COUNT2/ALL respectively within roundoff error).  This generates the
496
   result into a temp and returns the temp; it does not replace or alter
497
   the original STMT.  */
498
/* FIXME: Generalize the interface to handle NCOUNTS > 1.  */
499
 
500
static tree
501
tree_mod_subtract (tree stmt, tree operation, tree op1, tree op2,
502
                    int prob1, int prob2, int ncounts,
503
                    gcov_type count1, gcov_type count2, gcov_type all)
504
{
505
  tree stmt1, stmt2, stmt3;
506
  tree tmp1;
507
  tree label_decl1 = create_artificial_label ();
508
  tree label_decl2 = create_artificial_label ();
509
  tree label_decl3 = create_artificial_label ();
510
  tree label1, label2, label3;
511
  tree bb1end, bb2end = NULL_TREE, bb3end;
512
  basic_block bb, bb2, bb3, bb4;
513
  tree optype = TREE_TYPE (operation);
514
  edge e12, e23 = 0, e24, e34, e14;
515
  block_stmt_iterator bsi;
516
  tree result = create_tmp_var (optype, "PROF");
517
 
518
  bb = bb_for_stmt (stmt);
519
  bsi = bsi_for_stmt (stmt);
520
 
521
  tmp1 = create_tmp_var (optype, "PROF");
522
  stmt1 = build2 (MODIFY_EXPR, optype, result, op1);
523
  stmt2 = build2 (MODIFY_EXPR, optype, tmp1, op2);
524
  stmt3 = build3 (COND_EXPR, void_type_node,
525
            build2 (LT_EXPR, boolean_type_node, result, tmp1),
526
            build1 (GOTO_EXPR, void_type_node, label_decl3),
527
            build1 (GOTO_EXPR, void_type_node,
528
                    ncounts ? label_decl1 : label_decl2));
529
  bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
530
  bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
531
  bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
532
  bb1end = stmt3;
533
 
534
  if (ncounts)  /* Assumed to be 0 or 1 */
535
    {
536
      label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
537
      stmt1 = build2 (MODIFY_EXPR, optype, result,
538
                      build2 (MINUS_EXPR, optype, result, tmp1));
539
      stmt2 = build3 (COND_EXPR, void_type_node,
540
                build2 (LT_EXPR, boolean_type_node, result, tmp1),
541
                build1 (GOTO_EXPR, void_type_node, label_decl3),
542
                build1 (GOTO_EXPR, void_type_node, label_decl2));
543
      bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
544
      bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
545
      bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
546
      bb2end = stmt2;
547
    }
548
 
549
  /* Fallback case. */
550
  label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
551
  stmt1 = build2 (MODIFY_EXPR, optype, result,
552
                    build2 (TREE_CODE (operation), optype, result, tmp1));
553
  bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
554
  bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
555
  bb3end = stmt1;
556
 
557
  label3 = build1 (LABEL_EXPR, void_type_node, label_decl3);
558
  bsi_insert_before (&bsi, label3, BSI_SAME_STMT);
559
 
560
  /* Fix CFG. */
561
  /* Edge e23 connects bb2 to bb3, etc. */
562
  /* However block 3 is optional; if it is not there, references
563
     to 3 really refer to block 2. */
564
  e12 = split_block (bb, bb1end);
565
  bb2 = e12->dest;
566
  bb2->count = all - count1;
567
 
568
  if (ncounts)  /* Assumed to be 0 or 1.  */
569
    {
570
      e23 = split_block (bb2, bb2end);
571
      bb3 = e23->dest;
572
      bb3->count = all - count1 - count2;
573
    }
574
 
575
  e34 = split_block (ncounts ? bb3 : bb2, bb3end);
576
  bb4 = e34->dest;
577
  bb4->count = all;
578
 
579
  e12->flags &= ~EDGE_FALLTHRU;
580
  e12->flags |= EDGE_FALSE_VALUE;
581
  e12->probability = REG_BR_PROB_BASE - prob1;
582
  e12->count = all - count1;
583
 
584
  e14 = make_edge (bb, bb4, EDGE_TRUE_VALUE);
585
  e14->probability = prob1;
586
  e14->count = count1;
587
 
588
  if (ncounts)  /* Assumed to be 0 or 1.  */
589
    {
590
      e23->flags &= ~EDGE_FALLTHRU;
591
      e23->flags |= EDGE_FALSE_VALUE;
592
      e23->count = all - count1 - count2;
593
      e23->probability = REG_BR_PROB_BASE - prob2;
594
 
595
      e24 = make_edge (bb2, bb4, EDGE_TRUE_VALUE);
596
      e24->probability = prob2;
597
      e24->count = count2;
598
    }
599
 
600
  e34->probability = REG_BR_PROB_BASE;
601
  e34->count = all - count1 - count2;
602
 
603
  return result;
604
}
605
 
606
/* Do transforms 3) and 4) on INSN if applicable.  */
607
static bool
608
tree_mod_subtract_transform (tree stmt)
609
{
610
  stmt_ann_t ann = get_stmt_ann (stmt);
611
  histogram_value histogram;
612
  enum tree_code code;
613
  gcov_type count, wrong_values, all;
614
  tree modify, op, op1, op2, result, value;
615
  int prob1, prob2;
616
  unsigned int i;
617
 
618
  modify = stmt;
619
  if (TREE_CODE (stmt) == RETURN_EXPR
620
      && TREE_OPERAND (stmt, 0)
621
      && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR)
622
    modify = TREE_OPERAND (stmt, 0);
623
  if (TREE_CODE (modify) != MODIFY_EXPR)
624
    return false;
625
  op = TREE_OPERAND (modify, 1);
626
  if (!INTEGRAL_TYPE_P (TREE_TYPE (op)))
627
    return false;
628
  code = TREE_CODE (op);
629
 
630
  if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (TREE_TYPE (op)))
631
    return false;
632
 
633
  op1 = TREE_OPERAND (op, 0);
634
  op2 = TREE_OPERAND (op, 1);
635
  if (!ann->histograms)
636
    return false;
637
 
638
  for (histogram = ann->histograms; histogram; histogram = histogram->hvalue.next)
639
    if (histogram->type == HIST_TYPE_INTERVAL)
640
      break;
641
 
642
  if (!histogram)
643
    return false;
644
 
645
  value = histogram->hvalue.value;
646
  all = 0;
647
  wrong_values = 0;
648
  for (i = 0; i < histogram->hdata.intvl.steps; i++)
649
    all += histogram->hvalue.counters[i];
650
 
651
  wrong_values += histogram->hvalue.counters[i];
652
  wrong_values += histogram->hvalue.counters[i+1];
653
  all += wrong_values;
654
 
655
  /* Compute probability of taking the optimal path.  */
656
  if (check_counter (stmt, "interval", all, bb_for_stmt (stmt)->count))
657
    return false;
658
 
659
  /* We require that we use just subtractions in at least 50% of all
660
     evaluations.  */
661
  count = 0;
662
  for (i = 0; i < histogram->hdata.intvl.steps; i++)
663
    {
664
      count += histogram->hvalue.counters[i];
665
      if (count * 2 >= all)
666
        break;
667
    }
668
  if (i == histogram->hdata.intvl.steps)
669
    return false;
670
 
671
  if (dump_file)
672
    {
673
      fprintf (dump_file, "Mod subtract transformation on insn ");
674
      print_generic_stmt (dump_file, stmt, TDF_SLIM);
675
    }
676
 
677
  /* Compute probability of taking the optimal path(s).  */
678
  prob1 = (histogram->hvalue.counters[0] * REG_BR_PROB_BASE + all / 2) / all;
679
  prob2 = (histogram->hvalue.counters[1] * REG_BR_PROB_BASE + all / 2) / all;
680
 
681
  /* In practice, "steps" is always 2.  This interface reflects this,
682
     and will need to be changed if "steps" can change.  */
683
  result = tree_mod_subtract (stmt, op, op1, op2, prob1, prob2, i,
684
                            histogram->hvalue.counters[0],
685
                            histogram->hvalue.counters[1], all);
686
 
687
  TREE_OPERAND (modify, 1) = result;
688
 
689
  return true;
690
}
691
 
692
struct value_prof_hooks {
693
  /* Find list of values for which we want to measure histograms.  */
694
  void (*find_values_to_profile) (histogram_values *);
695
 
696
  /* Identify and exploit properties of values that are hard to analyze
697
     statically.  See value-prof.c for more detail.  */
698
  bool (*value_profile_transformations) (void);
699
};
700
 
701
/* Find values inside STMT for that we want to measure histograms for
702
   division/modulo optimization.  */
703
static void
704
tree_divmod_values_to_profile (tree stmt, histogram_values *values)
705
{
706
  tree assign, lhs, rhs, divisor, op0, type;
707
  histogram_value hist;
708
 
709
  if (TREE_CODE (stmt) == RETURN_EXPR)
710
    assign = TREE_OPERAND (stmt, 0);
711
  else
712
    assign = stmt;
713
 
714
  if (!assign
715
      || TREE_CODE (assign) != MODIFY_EXPR)
716
    return;
717
  lhs = TREE_OPERAND (assign, 0);
718
  type = TREE_TYPE (lhs);
719
  if (!INTEGRAL_TYPE_P (type))
720
    return;
721
 
722
  rhs = TREE_OPERAND (assign, 1);
723
  switch (TREE_CODE (rhs))
724
    {
725
    case TRUNC_DIV_EXPR:
726
    case TRUNC_MOD_EXPR:
727
      divisor = TREE_OPERAND (rhs, 1);
728
      op0 = TREE_OPERAND (rhs, 0);
729
 
730
      VEC_reserve (histogram_value, heap, *values, 3);
731
 
732
      if (is_gimple_reg (divisor))
733
        {
734
          /* Check for the case where the divisor is the same value most
735
             of the time.  */
736
          hist = ggc_alloc (sizeof (*hist));
737
          hist->hvalue.value = divisor;
738
          hist->hvalue.stmt = stmt;
739
          hist->type = HIST_TYPE_SINGLE_VALUE;
740
          VEC_quick_push (histogram_value, *values, hist);
741
        }
742
 
743
      /* For mod, check whether it is not often a noop (or replaceable by
744
         a few subtractions).  */
745
      if (TREE_CODE (rhs) == TRUNC_MOD_EXPR
746
          && TYPE_UNSIGNED (type))
747
        {
748
          /* Check for a special case where the divisor is power of 2.  */
749
          hist = ggc_alloc (sizeof (*hist));
750
          hist->hvalue.value = divisor;
751
          hist->hvalue.stmt = stmt;
752
          hist->type = HIST_TYPE_POW2;
753
          VEC_quick_push (histogram_value, *values, hist);
754
 
755
          hist = ggc_alloc (sizeof (*hist));
756
          hist->hvalue.stmt = stmt;
757
          hist->hvalue.value
758
                  = build2 (TRUNC_DIV_EXPR, type, op0, divisor);
759
          hist->type = HIST_TYPE_INTERVAL;
760
          hist->hdata.intvl.int_start = 0;
761
          hist->hdata.intvl.steps = 2;
762
          VEC_quick_push (histogram_value, *values, hist);
763
        }
764
      return;
765
 
766
    default:
767
      return;
768
    }
769
}
770
 
771
/* Find values inside STMT for that we want to measure histograms and adds
772
   them to list VALUES.  */
773
 
774
static void
775
tree_values_to_profile (tree stmt, histogram_values *values)
776
{
777
  if (flag_value_profile_transformations)
778
    tree_divmod_values_to_profile (stmt, values);
779
}
780
 
781
static void
782
tree_find_values_to_profile (histogram_values *values)
783
{
784
  basic_block bb;
785
  block_stmt_iterator bsi;
786
  unsigned i;
787
  histogram_value hist;
788
 
789
  *values = NULL;
790
  FOR_EACH_BB (bb)
791
    for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
792
      tree_values_to_profile (bsi_stmt (bsi), values);
793
 
794
  for (i = 0; VEC_iterate (histogram_value, *values, i, hist); i++)
795
    {
796
      switch (hist->type)
797
        {
798
        case HIST_TYPE_INTERVAL:
799
          if (dump_file)
800
            {
801
              fprintf (dump_file, "Interval counter for tree ");
802
              print_generic_expr (dump_file, hist->hvalue.stmt,
803
                                  TDF_SLIM);
804
              fprintf (dump_file, ", range %d -- %d.\n",
805
                     hist->hdata.intvl.int_start,
806
                     (hist->hdata.intvl.int_start
807
                      + hist->hdata.intvl.steps - 1));
808
            }
809
          hist->n_counters = hist->hdata.intvl.steps + 2;
810
          break;
811
 
812
        case HIST_TYPE_POW2:
813
          if (dump_file)
814
            {
815
              fprintf (dump_file, "Pow2 counter for tree ");
816
              print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM);
817
              fprintf (dump_file, ".\n");
818
            }
819
          hist->n_counters = 2;
820
          break;
821
 
822
        case HIST_TYPE_SINGLE_VALUE:
823
          if (dump_file)
824
            {
825
              fprintf (dump_file, "Single value counter for tree ");
826
              print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM);
827
              fprintf (dump_file, ".\n");
828
            }
829
          hist->n_counters = 3;
830
          break;
831
 
832
        case HIST_TYPE_CONST_DELTA:
833
          if (dump_file)
834
            {
835
              fprintf (dump_file, "Constant delta counter for tree ");
836
              print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM);
837
              fprintf (dump_file, ".\n");
838
            }
839
          hist->n_counters = 4;
840
          break;
841
 
842
        default:
843
          gcc_unreachable ();
844
        }
845
    }
846
}
847
 
848
static struct value_prof_hooks tree_value_prof_hooks = {
849
  tree_find_values_to_profile,
850
  tree_value_profile_transformations
851
};
852
 
853
void
854
tree_register_value_prof_hooks (void)
855
{
856
  value_prof_hooks = &tree_value_prof_hooks;
857
  gcc_assert (ir_type ());
858
}
859
 
860
/* IR-independent entry points.  */
861
void
862
find_values_to_profile (histogram_values *values)
863
{
864
  (value_prof_hooks->find_values_to_profile) (values);
865
}
866
 
867
bool
868
value_profile_transformations (void)
869
{
870
  return (value_prof_hooks->value_profile_transformations) ();
871
}
872
 
873
 

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.