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

Subversion Repositories openrisc

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

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 38 julius
/* Calculate branch probabilities, and basic block execution counts.
2
   Copyright (C) 1990, 1991, 1992, 1993, 1994, 1996, 1997, 1998, 1999,
3
   2000, 2001, 2002, 2003, 2004, 2005, 2007
4
   Free Software Foundation, Inc.
5
   Contributed by James E. Wilson, UC Berkeley/Cygnus Support;
6
   based on some ideas from Dain Samples of UC Berkeley.
7
   Further mangling by Bob Manson, Cygnus Support.
8
 
9
This file is part of GCC.
10
 
11
GCC is free software; you can redistribute it and/or modify it under
12
the terms of the GNU General Public License as published by the Free
13
Software Foundation; either version 3, or (at your option) any later
14
version.
15
 
16
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
17
WARRANTY; without even the implied warranty of MERCHANTABILITY or
18
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
19
for more details.
20
 
21
You should have received a copy of the GNU General Public License
22
along with GCC; see the file COPYING3.  If not see
23
<http://www.gnu.org/licenses/>.  */
24
 
25
/* Generate basic block profile instrumentation and auxiliary files.
26
   Profile generation is optimized, so that not all arcs in the basic
27
   block graph need instrumenting. First, the BB graph is closed with
28
   one entry (function start), and one exit (function exit).  Any
29
   ABNORMAL_EDGE cannot be instrumented (because there is no control
30
   path to place the code). We close the graph by inserting fake
31
   EDGE_FAKE edges to the EXIT_BLOCK, from the sources of abnormal
32
   edges that do not go to the exit_block. We ignore such abnormal
33
   edges.  Naturally these fake edges are never directly traversed,
34
   and so *cannot* be directly instrumented.  Some other graph
35
   massaging is done. To optimize the instrumentation we generate the
36
   BB minimal span tree, only edges that are not on the span tree
37
   (plus the entry point) need instrumenting. From that information
38
   all other edge counts can be deduced.  By construction all fake
39
   edges must be on the spanning tree. We also attempt to place
40
   EDGE_CRITICAL edges on the spanning tree.
41
 
42
   The auxiliary files generated are <dumpbase>.gcno (at compile time)
43
   and <dumpbase>.gcda (at run time).  The format is
44
   described in full in gcov-io.h.  */
45
 
46
/* ??? Register allocation should use basic block execution counts to
47
   give preference to the most commonly executed blocks.  */
48
 
49
/* ??? Should calculate branch probabilities before instrumenting code, since
50
   then we can use arc counts to help decide which arcs to instrument.  */
51
 
52
#include "config.h"
53
#include "system.h"
54
#include "coretypes.h"
55
#include "tm.h"
56
#include "rtl.h"
57
#include "flags.h"
58
#include "output.h"
59
#include "regs.h"
60
#include "expr.h"
61
#include "function.h"
62
#include "toplev.h"
63
#include "coverage.h"
64
#include "value-prof.h"
65
#include "tree.h"
66
#include "cfghooks.h"
67
#include "tree-flow.h"
68
#include "timevar.h"
69
#include "cfgloop.h"
70
#include "tree-pass.h"
71
 
72
/* Hooks for profiling.  */
73
static struct profile_hooks* profile_hooks;
74
 
75
/* Additional information about the edges we need.  */
76
struct edge_info {
77
  unsigned int count_valid : 1;
78
 
79
  /* Is on the spanning tree.  */
80
  unsigned int on_tree : 1;
81
 
82
  /* Pretend this edge does not exist (it is abnormal and we've
83
     inserted a fake to compensate).  */
84
  unsigned int ignore : 1;
85
};
86
 
87
struct bb_info {
88
  unsigned int count_valid : 1;
89
 
90
  /* Number of successor and predecessor edges.  */
91
  gcov_type succ_count;
92
  gcov_type pred_count;
93
};
94
 
95
#define EDGE_INFO(e)  ((struct edge_info *) (e)->aux)
96
#define BB_INFO(b)  ((struct bb_info *) (b)->aux)
97
 
98
/* Counter summary from the last set of coverage counts read.  */
99
 
100
const struct gcov_ctr_summary *profile_info;
101
 
102
/* Collect statistics on the performance of this pass for the entire source
103
   file.  */
104
 
105
static int total_num_blocks;
106
static int total_num_edges;
107
static int total_num_edges_ignored;
108
static int total_num_edges_instrumented;
109
static int total_num_blocks_created;
110
static int total_num_passes;
111
static int total_num_times_called;
112
static int total_hist_br_prob[20];
113
static int total_num_never_executed;
114
static int total_num_branches;
115
 
116
/* Forward declarations.  */
117
static void find_spanning_tree (struct edge_list *);
118
static unsigned instrument_edges (struct edge_list *);
119
static void instrument_values (histogram_values);
120
static void compute_branch_probabilities (void);
121
static void compute_value_histograms (histogram_values);
122
static gcov_type * get_exec_counts (void);
123
static basic_block find_group (basic_block);
124
static void union_groups (basic_block, basic_block);
125
 
126
 
127
/* Add edge instrumentation code to the entire insn chain.
128
 
129
   F is the first insn of the chain.
130
   NUM_BLOCKS is the number of basic blocks found in F.  */
131
 
132
static unsigned
133
instrument_edges (struct edge_list *el)
134
{
135
  unsigned num_instr_edges = 0;
136
  int num_edges = NUM_EDGES (el);
137
  basic_block bb;
138
 
139
  FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
140
    {
141
      edge e;
142
      edge_iterator ei;
143
 
144
      FOR_EACH_EDGE (e, ei, bb->succs)
145
        {
146
          struct edge_info *inf = EDGE_INFO (e);
147
 
148
          if (!inf->ignore && !inf->on_tree)
149
            {
150
              gcc_assert (!(e->flags & EDGE_ABNORMAL));
151
              if (dump_file)
152
                fprintf (dump_file, "Edge %d to %d instrumented%s\n",
153
                         e->src->index, e->dest->index,
154
                         EDGE_CRITICAL_P (e) ? " (and split)" : "");
155
              (profile_hooks->gen_edge_profiler) (num_instr_edges++, e);
156
            }
157
        }
158
    }
159
 
160
  total_num_blocks_created += num_edges;
161
  if (dump_file)
162
    fprintf (dump_file, "%d edges instrumented\n", num_instr_edges);
163
  return num_instr_edges;
164
}
165
 
166
/* Add code to measure histograms for values in list VALUES.  */
167
static void
168
instrument_values (histogram_values values)
169
{
170
  unsigned i, t;
171
 
172
  /* Emit code to generate the histograms before the insns.  */
173
 
174
  for (i = 0; i < VEC_length (histogram_value, values); i++)
175
    {
176
      histogram_value hist = VEC_index (histogram_value, values, i);
177
      switch (hist->type)
178
        {
179
        case HIST_TYPE_INTERVAL:
180
          t = GCOV_COUNTER_V_INTERVAL;
181
          break;
182
 
183
        case HIST_TYPE_POW2:
184
          t = GCOV_COUNTER_V_POW2;
185
          break;
186
 
187
        case HIST_TYPE_SINGLE_VALUE:
188
          t = GCOV_COUNTER_V_SINGLE;
189
          break;
190
 
191
        case HIST_TYPE_CONST_DELTA:
192
          t = GCOV_COUNTER_V_DELTA;
193
          break;
194
 
195
        default:
196
          gcc_unreachable ();
197
        }
198
      if (!coverage_counter_alloc (t, hist->n_counters))
199
        continue;
200
 
201
      switch (hist->type)
202
        {
203
        case HIST_TYPE_INTERVAL:
204
          (profile_hooks->gen_interval_profiler) (hist, t, 0);
205
          break;
206
 
207
        case HIST_TYPE_POW2:
208
          (profile_hooks->gen_pow2_profiler) (hist, t, 0);
209
          break;
210
 
211
        case HIST_TYPE_SINGLE_VALUE:
212
          (profile_hooks->gen_one_value_profiler) (hist, t, 0);
213
          break;
214
 
215
        case HIST_TYPE_CONST_DELTA:
216
          (profile_hooks->gen_const_delta_profiler) (hist, t, 0);
217
          break;
218
 
219
        default:
220
          gcc_unreachable ();
221
        }
222
    }
223
}
224
 
225
 
226
/* Computes hybrid profile for all matching entries in da_file.  */
227
 
228
static gcov_type *
229
get_exec_counts (void)
230
{
231
  unsigned num_edges = 0;
232
  basic_block bb;
233
  gcov_type *counts;
234
 
235
  /* Count the edges to be (possibly) instrumented.  */
236
  FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
237
    {
238
      edge e;
239
      edge_iterator ei;
240
 
241
      FOR_EACH_EDGE (e, ei, bb->succs)
242
        if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree)
243
          num_edges++;
244
    }
245
 
246
  counts = get_coverage_counts (GCOV_COUNTER_ARCS, num_edges, &profile_info);
247
  if (!counts)
248
    return NULL;
249
 
250
  if (dump_file && profile_info)
251
    fprintf(dump_file, "Merged %u profiles with maximal count %u.\n",
252
            profile_info->runs, (unsigned) profile_info->sum_max);
253
 
254
  return counts;
255
}
256
 
257
 
258
/* Compute the branch probabilities for the various branches.
259
   Annotate them accordingly.  */
260
 
261
static void
262
compute_branch_probabilities (void)
263
{
264
  basic_block bb;
265
  int i;
266
  int num_edges = 0;
267
  int changes;
268
  int passes;
269
  int hist_br_prob[20];
270
  int num_never_executed;
271
  int num_branches;
272
  gcov_type *exec_counts = get_exec_counts ();
273
  int exec_counts_pos = 0;
274
 
275
  /* Very simple sanity checks so we catch bugs in our profiling code.  */
276
  if (profile_info)
277
    {
278
      if (profile_info->run_max * profile_info->runs < profile_info->sum_max)
279
        {
280
          error ("corrupted profile info: run_max * runs < sum_max");
281
          exec_counts = NULL;
282
        }
283
 
284
      if (profile_info->sum_all < profile_info->sum_max)
285
        {
286
          error ("corrupted profile info: sum_all is smaller than sum_max");
287
          exec_counts = NULL;
288
        }
289
    }
290
 
291
  /* Attach extra info block to each bb.  */
292
 
293
  alloc_aux_for_blocks (sizeof (struct bb_info));
294
  FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
295
    {
296
      edge e;
297
      edge_iterator ei;
298
 
299
      FOR_EACH_EDGE (e, ei, bb->succs)
300
        if (!EDGE_INFO (e)->ignore)
301
          BB_INFO (bb)->succ_count++;
302
      FOR_EACH_EDGE (e, ei, bb->preds)
303
        if (!EDGE_INFO (e)->ignore)
304
          BB_INFO (bb)->pred_count++;
305
    }
306
 
307
  /* Avoid predicting entry on exit nodes.  */
308
  BB_INFO (EXIT_BLOCK_PTR)->succ_count = 2;
309
  BB_INFO (ENTRY_BLOCK_PTR)->pred_count = 2;
310
 
311
  /* For each edge not on the spanning tree, set its execution count from
312
     the .da file.  */
313
 
314
  /* The first count in the .da file is the number of times that the function
315
     was entered.  This is the exec_count for block zero.  */
316
 
317
  FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
318
    {
319
      edge e;
320
      edge_iterator ei;
321
 
322
      FOR_EACH_EDGE (e, ei, bb->succs)
323
        if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree)
324
          {
325
            num_edges++;
326
            if (exec_counts)
327
              {
328
                e->count = exec_counts[exec_counts_pos++];
329
                if (e->count > profile_info->sum_max)
330
                  {
331
                    error ("corrupted profile info: edge from %i to %i exceeds maximal count",
332
                           bb->index, e->dest->index);
333
                  }
334
              }
335
            else
336
              e->count = 0;
337
 
338
            EDGE_INFO (e)->count_valid = 1;
339
            BB_INFO (bb)->succ_count--;
340
            BB_INFO (e->dest)->pred_count--;
341
            if (dump_file)
342
              {
343
                fprintf (dump_file, "\nRead edge from %i to %i, count:",
344
                         bb->index, e->dest->index);
345
                fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
346
                         (HOST_WIDEST_INT) e->count);
347
              }
348
          }
349
    }
350
 
351
  if (dump_file)
352
    fprintf (dump_file, "\n%d edge counts read\n", num_edges);
353
 
354
  /* For every block in the file,
355
     - if every exit/entrance edge has a known count, then set the block count
356
     - if the block count is known, and every exit/entrance edge but one has
357
     a known execution count, then set the count of the remaining edge
358
 
359
     As edge counts are set, decrement the succ/pred count, but don't delete
360
     the edge, that way we can easily tell when all edges are known, or only
361
     one edge is unknown.  */
362
 
363
  /* The order that the basic blocks are iterated through is important.
364
     Since the code that finds spanning trees starts with block 0, low numbered
365
     edges are put on the spanning tree in preference to high numbered edges.
366
     Hence, most instrumented edges are at the end.  Graph solving works much
367
     faster if we propagate numbers from the end to the start.
368
 
369
     This takes an average of slightly more than 3 passes.  */
370
 
371
  changes = 1;
372
  passes = 0;
373
  while (changes)
374
    {
375
      passes++;
376
      changes = 0;
377
      FOR_BB_BETWEEN (bb, EXIT_BLOCK_PTR, NULL, prev_bb)
378
        {
379
          struct bb_info *bi = BB_INFO (bb);
380
          if (! bi->count_valid)
381
            {
382
              if (bi->succ_count == 0)
383
                {
384
                  edge e;
385
                  edge_iterator ei;
386
                  gcov_type total = 0;
387
 
388
                  FOR_EACH_EDGE (e, ei, bb->succs)
389
                    total += e->count;
390
                  bb->count = total;
391
                  bi->count_valid = 1;
392
                  changes = 1;
393
                }
394
              else if (bi->pred_count == 0)
395
                {
396
                  edge e;
397
                  edge_iterator ei;
398
                  gcov_type total = 0;
399
 
400
                  FOR_EACH_EDGE (e, ei, bb->preds)
401
                    total += e->count;
402
                  bb->count = total;
403
                  bi->count_valid = 1;
404
                  changes = 1;
405
                }
406
            }
407
          if (bi->count_valid)
408
            {
409
              if (bi->succ_count == 1)
410
                {
411
                  edge e;
412
                  edge_iterator ei;
413
                  gcov_type total = 0;
414
 
415
                  /* One of the counts will be invalid, but it is zero,
416
                     so adding it in also doesn't hurt.  */
417
                  FOR_EACH_EDGE (e, ei, bb->succs)
418
                    total += e->count;
419
 
420
                  /* Seedgeh for the invalid edge, and set its count.  */
421
                  FOR_EACH_EDGE (e, ei, bb->succs)
422
                    if (! EDGE_INFO (e)->count_valid && ! EDGE_INFO (e)->ignore)
423
                      break;
424
 
425
                  /* Calculate count for remaining edge by conservation.  */
426
                  total = bb->count - total;
427
 
428
                  gcc_assert (e);
429
                  EDGE_INFO (e)->count_valid = 1;
430
                  e->count = total;
431
                  bi->succ_count--;
432
 
433
                  BB_INFO (e->dest)->pred_count--;
434
                  changes = 1;
435
                }
436
              if (bi->pred_count == 1)
437
                {
438
                  edge e;
439
                  edge_iterator ei;
440
                  gcov_type total = 0;
441
 
442
                  /* One of the counts will be invalid, but it is zero,
443
                     so adding it in also doesn't hurt.  */
444
                  FOR_EACH_EDGE (e, ei, bb->preds)
445
                    total += e->count;
446
 
447
                  /* Search for the invalid edge, and set its count.  */
448
                  FOR_EACH_EDGE (e, ei, bb->preds)
449
                    if (!EDGE_INFO (e)->count_valid && !EDGE_INFO (e)->ignore)
450
                      break;
451
 
452
                  /* Calculate count for remaining edge by conservation.  */
453
                  total = bb->count - total + e->count;
454
 
455
                  gcc_assert (e);
456
                  EDGE_INFO (e)->count_valid = 1;
457
                  e->count = total;
458
                  bi->pred_count--;
459
 
460
                  BB_INFO (e->src)->succ_count--;
461
                  changes = 1;
462
                }
463
            }
464
        }
465
    }
466
  if (dump_file)
467
    dump_flow_info (dump_file, dump_flags);
468
 
469
  total_num_passes += passes;
470
  if (dump_file)
471
    fprintf (dump_file, "Graph solving took %d passes.\n\n", passes);
472
 
473
  /* If the graph has been correctly solved, every block will have a
474
     succ and pred count of zero.  */
475
  FOR_EACH_BB (bb)
476
    {
477
      gcc_assert (!BB_INFO (bb)->succ_count && !BB_INFO (bb)->pred_count);
478
    }
479
 
480
  /* For every edge, calculate its branch probability and add a reg_note
481
     to the branch insn to indicate this.  */
482
 
483
  for (i = 0; i < 20; i++)
484
    hist_br_prob[i] = 0;
485
  num_never_executed = 0;
486
  num_branches = 0;
487
 
488
  FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
489
    {
490
      edge e;
491
      edge_iterator ei;
492
 
493
      if (bb->count < 0)
494
        {
495
          error ("corrupted profile info: number of iterations for basic block %d thought to be %i",
496
                 bb->index, (int)bb->count);
497
          bb->count = 0;
498
        }
499
      FOR_EACH_EDGE (e, ei, bb->succs)
500
        {
501
          /* Function may return twice in the cased the called function is
502
             setjmp or calls fork, but we can't represent this by extra
503
             edge from the entry, since extra edge from the exit is
504
             already present.  We get negative frequency from the entry
505
             point.  */
506
          if ((e->count < 0
507
               && e->dest == EXIT_BLOCK_PTR)
508
              || (e->count > bb->count
509
                  && e->dest != EXIT_BLOCK_PTR))
510
            {
511
              if (block_ends_with_call_p (bb))
512
                e->count = e->count < 0 ? 0 : bb->count;
513
            }
514
          if (e->count < 0 || e->count > bb->count)
515
            {
516
              error ("corrupted profile info: number of executions for edge %d-%d thought to be %i",
517
                     e->src->index, e->dest->index,
518
                     (int)e->count);
519
              e->count = bb->count / 2;
520
            }
521
        }
522
      if (bb->count)
523
        {
524
          FOR_EACH_EDGE (e, ei, bb->succs)
525
            e->probability = (e->count * REG_BR_PROB_BASE + bb->count / 2) / bb->count;
526
          if (bb->index >= NUM_FIXED_BLOCKS
527
              && block_ends_with_condjump_p (bb)
528
              && EDGE_COUNT (bb->succs) >= 2)
529
            {
530
              int prob;
531
              edge e;
532
              int index;
533
 
534
              /* Find the branch edge.  It is possible that we do have fake
535
                 edges here.  */
536
              FOR_EACH_EDGE (e, ei, bb->succs)
537
                if (!(e->flags & (EDGE_FAKE | EDGE_FALLTHRU)))
538
                  break;
539
 
540
              prob = e->probability;
541
              index = prob * 20 / REG_BR_PROB_BASE;
542
 
543
              if (index == 20)
544
                index = 19;
545
              hist_br_prob[index]++;
546
 
547
              num_branches++;
548
            }
549
        }
550
      /* As a last resort, distribute the probabilities evenly.
551
         Use simple heuristics that if there are normal edges,
552
         give all abnormals frequency of 0, otherwise distribute the
553
         frequency over abnormals (this is the case of noreturn
554
         calls).  */
555
      else if (profile_status == PROFILE_ABSENT)
556
        {
557
          int total = 0;
558
 
559
          FOR_EACH_EDGE (e, ei, bb->succs)
560
            if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
561
              total ++;
562
          if (total)
563
            {
564
              FOR_EACH_EDGE (e, ei, bb->succs)
565
                if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
566
                  e->probability = REG_BR_PROB_BASE / total;
567
                else
568
                  e->probability = 0;
569
            }
570
          else
571
            {
572
              total += EDGE_COUNT (bb->succs);
573
              FOR_EACH_EDGE (e, ei, bb->succs)
574
                e->probability = REG_BR_PROB_BASE / total;
575
            }
576
          if (bb->index >= NUM_FIXED_BLOCKS
577
              && block_ends_with_condjump_p (bb)
578
              && EDGE_COUNT (bb->succs) >= 2)
579
            num_branches++, num_never_executed;
580
        }
581
    }
582
  counts_to_freqs ();
583
 
584
  if (dump_file)
585
    {
586
      fprintf (dump_file, "%d branches\n", num_branches);
587
      fprintf (dump_file, "%d branches never executed\n",
588
               num_never_executed);
589
      if (num_branches)
590
        for (i = 0; i < 10; i++)
591
          fprintf (dump_file, "%d%% branches in range %d-%d%%\n",
592
                   (hist_br_prob[i] + hist_br_prob[19-i]) * 100 / num_branches,
593
                   5 * i, 5 * i + 5);
594
 
595
      total_num_branches += num_branches;
596
      total_num_never_executed += num_never_executed;
597
      for (i = 0; i < 20; i++)
598
        total_hist_br_prob[i] += hist_br_prob[i];
599
 
600
      fputc ('\n', dump_file);
601
      fputc ('\n', dump_file);
602
    }
603
 
604
  free_aux_for_blocks ();
605
}
606
 
607
/* Load value histograms values whose description is stored in VALUES array
608
   from .gcda file.  */
609
 
610
static void
611
compute_value_histograms (histogram_values values)
612
{
613
  unsigned i, j, t, any;
614
  unsigned n_histogram_counters[GCOV_N_VALUE_COUNTERS];
615
  gcov_type *histogram_counts[GCOV_N_VALUE_COUNTERS];
616
  gcov_type *act_count[GCOV_N_VALUE_COUNTERS];
617
  gcov_type *aact_count;
618
 
619
  for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++)
620
    n_histogram_counters[t] = 0;
621
 
622
  for (i = 0; i < VEC_length (histogram_value, values); i++)
623
    {
624
      histogram_value hist = VEC_index (histogram_value, values, i);
625
      n_histogram_counters[(int) hist->type] += hist->n_counters;
626
    }
627
 
628
  any = 0;
629
  for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++)
630
    {
631
      if (!n_histogram_counters[t])
632
        {
633
          histogram_counts[t] = NULL;
634
          continue;
635
        }
636
 
637
      histogram_counts[t] =
638
        get_coverage_counts (COUNTER_FOR_HIST_TYPE (t),
639
                             n_histogram_counters[t], NULL);
640
      if (histogram_counts[t])
641
        any = 1;
642
      act_count[t] = histogram_counts[t];
643
    }
644
  if (!any)
645
    return;
646
 
647
  for (i = 0; i < VEC_length (histogram_value, values); i++)
648
    {
649
      histogram_value hist = VEC_index (histogram_value, values, i);
650
      tree stmt = hist->hvalue.stmt;
651
      stmt_ann_t ann = get_stmt_ann (stmt);
652
 
653
      t = (int) hist->type;
654
 
655
      aact_count = act_count[t];
656
      act_count[t] += hist->n_counters;
657
 
658
      hist->hvalue.next = ann->histograms;
659
      ann->histograms = hist;
660
      hist->hvalue.counters =  XNEWVEC (gcov_type, hist->n_counters);
661
      for (j = 0; j < hist->n_counters; j++)
662
        hist->hvalue.counters[j] = aact_count[j];
663
    }
664
 
665
  for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++)
666
    if (histogram_counts[t])
667
      free (histogram_counts[t]);
668
}
669
 
670
/* The entry basic block will be moved around so that it has index=1,
671
   there is nothing at index 0 and the exit is at n_basic_block.  */
672
#define BB_TO_GCOV_INDEX(bb)  ((bb)->index - 1)
673
/* When passed NULL as file_name, initialize.
674
   When passed something else, output the necessary commands to change
675
   line to LINE and offset to FILE_NAME.  */
676
static void
677
output_location (char const *file_name, int line,
678
                 gcov_position_t *offset, basic_block bb)
679
{
680
  static char const *prev_file_name;
681
  static int prev_line;
682
  bool name_differs, line_differs;
683
 
684
  if (!file_name)
685
    {
686
      prev_file_name = NULL;
687
      prev_line = -1;
688
      return;
689
    }
690
 
691
  name_differs = !prev_file_name || strcmp (file_name, prev_file_name);
692
  line_differs = prev_line != line;
693
 
694
  if (name_differs || line_differs)
695
    {
696
      if (!*offset)
697
        {
698
          *offset = gcov_write_tag (GCOV_TAG_LINES);
699
          gcov_write_unsigned (BB_TO_GCOV_INDEX (bb));
700
          name_differs = line_differs=true;
701
        }
702
 
703
      /* If this is a new source file, then output the
704
         file's name to the .bb file.  */
705
      if (name_differs)
706
        {
707
          prev_file_name = file_name;
708
          gcov_write_unsigned (0);
709
          gcov_write_string (prev_file_name);
710
        }
711
      if (line_differs)
712
        {
713
          gcov_write_unsigned (line);
714
          prev_line = line;
715
        }
716
     }
717
}
718
 
719
/* Instrument and/or analyze program behavior based on program flow graph.
720
   In either case, this function builds a flow graph for the function being
721
   compiled.  The flow graph is stored in BB_GRAPH.
722
 
723
   When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in
724
   the flow graph that are needed to reconstruct the dynamic behavior of the
725
   flow graph.
726
 
727
   When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
728
   information from a data file containing edge count information from previous
729
   executions of the function being compiled.  In this case, the flow graph is
730
   annotated with actual execution counts, which are later propagated into the
731
   rtl for optimization purposes.
732
 
733
   Main entry point of this file.  */
734
 
735
void
736
branch_prob (void)
737
{
738
  basic_block bb;
739
  unsigned i;
740
  unsigned num_edges, ignored_edges;
741
  unsigned num_instrumented;
742
  struct edge_list *el;
743
  histogram_values values = NULL;
744
 
745
  total_num_times_called++;
746
 
747
  flow_call_edges_add (NULL);
748
  add_noreturn_fake_exit_edges ();
749
 
750
  /* We can't handle cyclic regions constructed using abnormal edges.
751
     To avoid these we replace every source of abnormal edge by a fake
752
     edge from entry node and every destination by fake edge to exit.
753
     This keeps graph acyclic and our calculation exact for all normal
754
     edges except for exit and entrance ones.
755
 
756
     We also add fake exit edges for each call and asm statement in the
757
     basic, since it may not return.  */
758
 
759
  FOR_EACH_BB (bb)
760
    {
761
      int need_exit_edge = 0, need_entry_edge = 0;
762
      int have_exit_edge = 0, have_entry_edge = 0;
763
      edge e;
764
      edge_iterator ei;
765
 
766
      /* Functions returning multiple times are not handled by extra edges.
767
         Instead we simply allow negative counts on edges from exit to the
768
         block past call and corresponding probabilities.  We can't go
769
         with the extra edges because that would result in flowgraph that
770
         needs to have fake edges outside the spanning tree.  */
771
 
772
      FOR_EACH_EDGE (e, ei, bb->succs)
773
        {
774
          block_stmt_iterator bsi;
775
          tree last = NULL;
776
 
777
          /* It may happen that there are compiler generated statements
778
             without a locus at all.  Go through the basic block from the
779
             last to the first statement looking for a locus.  */
780
          for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
781
            {
782
              last = bsi_stmt (bsi);
783
              if (EXPR_LOCUS (last))
784
                break;
785
            }
786
 
787
          /* Edge with goto locus might get wrong coverage info unless
788
             it is the only edge out of BB.
789
             Don't do that when the locuses match, so
790
             if (blah) goto something;
791
             is not computed twice.  */
792
          if (last && EXPR_LOCUS (last)
793
              && e->goto_locus
794
              && !single_succ_p (bb)
795
#ifdef USE_MAPPED_LOCATION
796
              && (LOCATION_FILE (e->goto_locus)
797
                  != LOCATION_FILE (EXPR_LOCATION  (last))
798
                  || (LOCATION_LINE (e->goto_locus)
799
                      != LOCATION_LINE (EXPR_LOCATION  (last)))))
800
#else
801
              && (e->goto_locus->file != EXPR_LOCUS (last)->file
802
                  || (e->goto_locus->line != EXPR_LOCUS (last)->line)))
803
#endif
804
            {
805
              basic_block new = split_edge (e);
806
              single_succ_edge (new)->goto_locus = e->goto_locus;
807
            }
808
          if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
809
               && e->dest != EXIT_BLOCK_PTR)
810
            need_exit_edge = 1;
811
          if (e->dest == EXIT_BLOCK_PTR)
812
            have_exit_edge = 1;
813
        }
814
      FOR_EACH_EDGE (e, ei, bb->preds)
815
        {
816
          if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
817
               && e->src != ENTRY_BLOCK_PTR)
818
            need_entry_edge = 1;
819
          if (e->src == ENTRY_BLOCK_PTR)
820
            have_entry_edge = 1;
821
        }
822
 
823
      if (need_exit_edge && !have_exit_edge)
824
        {
825
          if (dump_file)
826
            fprintf (dump_file, "Adding fake exit edge to bb %i\n",
827
                     bb->index);
828
          make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
829
        }
830
      if (need_entry_edge && !have_entry_edge)
831
        {
832
          if (dump_file)
833
            fprintf (dump_file, "Adding fake entry edge to bb %i\n",
834
                     bb->index);
835
          make_edge (ENTRY_BLOCK_PTR, bb, EDGE_FAKE);
836
        }
837
    }
838
 
839
  el = create_edge_list ();
840
  num_edges = NUM_EDGES (el);
841
  alloc_aux_for_edges (sizeof (struct edge_info));
842
 
843
  /* The basic blocks are expected to be numbered sequentially.  */
844
  compact_blocks ();
845
 
846
  ignored_edges = 0;
847
  for (i = 0 ; i < num_edges ; i++)
848
    {
849
      edge e = INDEX_EDGE (el, i);
850
      e->count = 0;
851
 
852
      /* Mark edges we've replaced by fake edges above as ignored.  */
853
      if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
854
          && e->src != ENTRY_BLOCK_PTR && e->dest != EXIT_BLOCK_PTR)
855
        {
856
          EDGE_INFO (e)->ignore = 1;
857
          ignored_edges++;
858
        }
859
    }
860
 
861
  /* Create spanning tree from basic block graph, mark each edge that is
862
     on the spanning tree.  We insert as many abnormal and critical edges
863
     as possible to minimize number of edge splits necessary.  */
864
 
865
  find_spanning_tree (el);
866
 
867
  /* Fake edges that are not on the tree will not be instrumented, so
868
     mark them ignored.  */
869
  for (num_instrumented = i = 0; i < num_edges; i++)
870
    {
871
      edge e = INDEX_EDGE (el, i);
872
      struct edge_info *inf = EDGE_INFO (e);
873
 
874
      if (inf->ignore || inf->on_tree)
875
        /*NOP*/;
876
      else if (e->flags & EDGE_FAKE)
877
        {
878
          inf->ignore = 1;
879
          ignored_edges++;
880
        }
881
      else
882
        num_instrumented++;
883
    }
884
 
885
  total_num_blocks += n_basic_blocks;
886
  if (dump_file)
887
    fprintf (dump_file, "%d basic blocks\n", n_basic_blocks);
888
 
889
  total_num_edges += num_edges;
890
  if (dump_file)
891
    fprintf (dump_file, "%d edges\n", num_edges);
892
 
893
  total_num_edges_ignored += ignored_edges;
894
  if (dump_file)
895
    fprintf (dump_file, "%d ignored edges\n", ignored_edges);
896
 
897
  /* Write the data from which gcov can reconstruct the basic block
898
     graph.  */
899
 
900
  /* Basic block flags */
901
  if (coverage_begin_output ())
902
    {
903
      gcov_position_t offset;
904
 
905
      offset = gcov_write_tag (GCOV_TAG_BLOCKS);
906
      for (i = 0; i != (unsigned) (n_basic_blocks); i++)
907
        gcov_write_unsigned (0);
908
      gcov_write_length (offset);
909
    }
910
 
911
   /* Keep all basic block indexes nonnegative in the gcov output.
912
      Index 0 is used for entry block, last index is for exit block.
913
      */
914
  ENTRY_BLOCK_PTR->index = 1;
915
  EXIT_BLOCK_PTR->index = last_basic_block;
916
 
917
  /* Arcs */
918
  if (coverage_begin_output ())
919
    {
920
      gcov_position_t offset;
921
 
922
      FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
923
        {
924
          edge e;
925
          edge_iterator ei;
926
 
927
          offset = gcov_write_tag (GCOV_TAG_ARCS);
928
          gcov_write_unsigned (BB_TO_GCOV_INDEX (bb));
929
 
930
          FOR_EACH_EDGE (e, ei, bb->succs)
931
            {
932
              struct edge_info *i = EDGE_INFO (e);
933
              if (!i->ignore)
934
                {
935
                  unsigned flag_bits = 0;
936
 
937
                  if (i->on_tree)
938
                    flag_bits |= GCOV_ARC_ON_TREE;
939
                  if (e->flags & EDGE_FAKE)
940
                    flag_bits |= GCOV_ARC_FAKE;
941
                  if (e->flags & EDGE_FALLTHRU)
942
                    flag_bits |= GCOV_ARC_FALLTHROUGH;
943
                  /* On trees we don't have fallthru flags, but we can
944
                     recompute them from CFG shape.  */
945
                  if (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)
946
                      && e->src->next_bb == e->dest)
947
                    flag_bits |= GCOV_ARC_FALLTHROUGH;
948
 
949
                  gcov_write_unsigned (BB_TO_GCOV_INDEX (e->dest));
950
                  gcov_write_unsigned (flag_bits);
951
                }
952
            }
953
 
954
          gcov_write_length (offset);
955
        }
956
    }
957
 
958
  /* Line numbers.  */
959
  if (coverage_begin_output ())
960
    {
961
      gcov_position_t offset;
962
 
963
      /* Initialize the output.  */
964
      output_location (NULL, 0, NULL, NULL);
965
 
966
      FOR_EACH_BB (bb)
967
        {
968
          block_stmt_iterator bsi;
969
 
970
          offset = 0;
971
 
972
          if (bb == ENTRY_BLOCK_PTR->next_bb)
973
            {
974
              expanded_location curr_location =
975
                expand_location (DECL_SOURCE_LOCATION (current_function_decl));
976
              output_location (curr_location.file, curr_location.line,
977
                               &offset, bb);
978
            }
979
 
980
          for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
981
            {
982
              tree stmt = bsi_stmt (bsi);
983
              if (EXPR_HAS_LOCATION (stmt))
984
                output_location (EXPR_FILENAME (stmt), EXPR_LINENO (stmt),
985
                                 &offset, bb);
986
            }
987
 
988
          /* Notice GOTO expressions we eliminated while constructing the
989
             CFG.  */
990
          if (single_succ_p (bb) && single_succ_edge (bb)->goto_locus)
991
            {
992
              /* ??? source_locus type is marked deprecated in input.h.  */
993
              source_locus curr_location = single_succ_edge (bb)->goto_locus;
994
              /* ??? The FILE/LINE API is inconsistent for these cases.  */
995
#ifdef USE_MAPPED_LOCATION 
996
              output_location (LOCATION_FILE (curr_location),
997
                               LOCATION_LINE (curr_location), &offset, bb);
998
#else
999
              output_location (curr_location->file, curr_location->line,
1000
                               &offset, bb);
1001
#endif
1002
            }
1003
 
1004
          if (offset)
1005
            {
1006
              /* A file of NULL indicates the end of run.  */
1007
              gcov_write_unsigned (0);
1008
              gcov_write_string (NULL);
1009
              gcov_write_length (offset);
1010
            }
1011
        }
1012
    }
1013
 
1014
  ENTRY_BLOCK_PTR->index = ENTRY_BLOCK;
1015
  EXIT_BLOCK_PTR->index = EXIT_BLOCK;
1016
#undef BB_TO_GCOV_INDEX
1017
 
1018
  if (flag_profile_values)
1019
    find_values_to_profile (&values);
1020
 
1021
  if (flag_branch_probabilities)
1022
    {
1023
      compute_branch_probabilities ();
1024
      if (flag_profile_values)
1025
        compute_value_histograms (values);
1026
    }
1027
 
1028
  remove_fake_edges ();
1029
 
1030
  /* For each edge not on the spanning tree, add counting code.  */
1031
  if (profile_arc_flag
1032
      && coverage_counter_alloc (GCOV_COUNTER_ARCS, num_instrumented))
1033
    {
1034
      unsigned n_instrumented;
1035
 
1036
      profile_hooks->init_edge_profiler ();
1037
 
1038
      n_instrumented = instrument_edges (el);
1039
 
1040
      gcc_assert (n_instrumented == num_instrumented);
1041
 
1042
      if (flag_profile_values)
1043
        instrument_values (values);
1044
 
1045
      /* Commit changes done by instrumentation.  */
1046
      bsi_commit_edge_inserts ();
1047
    }
1048
 
1049
  free_aux_for_edges ();
1050
 
1051
  VEC_free (histogram_value, heap, values);
1052
  free_edge_list (el);
1053
  if (flag_branch_probabilities)
1054
    profile_status = PROFILE_READ;
1055
  coverage_end_function ();
1056
}
1057
 
1058
/* Union find algorithm implementation for the basic blocks using
1059
   aux fields.  */
1060
 
1061
static basic_block
1062
find_group (basic_block bb)
1063
{
1064
  basic_block group = bb, bb1;
1065
 
1066
  while ((basic_block) group->aux != group)
1067
    group = (basic_block) group->aux;
1068
 
1069
  /* Compress path.  */
1070
  while ((basic_block) bb->aux != group)
1071
    {
1072
      bb1 = (basic_block) bb->aux;
1073
      bb->aux = (void *) group;
1074
      bb = bb1;
1075
    }
1076
  return group;
1077
}
1078
 
1079
static void
1080
union_groups (basic_block bb1, basic_block bb2)
1081
{
1082
  basic_block bb1g = find_group (bb1);
1083
  basic_block bb2g = find_group (bb2);
1084
 
1085
  /* ??? I don't have a place for the rank field.  OK.  Lets go w/o it,
1086
     this code is unlikely going to be performance problem anyway.  */
1087
  gcc_assert (bb1g != bb2g);
1088
 
1089
  bb1g->aux = bb2g;
1090
}
1091
 
1092
/* This function searches all of the edges in the program flow graph, and puts
1093
   as many bad edges as possible onto the spanning tree.  Bad edges include
1094
   abnormals edges, which can't be instrumented at the moment.  Since it is
1095
   possible for fake edges to form a cycle, we will have to develop some
1096
   better way in the future.  Also put critical edges to the tree, since they
1097
   are more expensive to instrument.  */
1098
 
1099
static void
1100
find_spanning_tree (struct edge_list *el)
1101
{
1102
  int i;
1103
  int num_edges = NUM_EDGES (el);
1104
  basic_block bb;
1105
 
1106
  /* We use aux field for standard union-find algorithm.  */
1107
  FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1108
    bb->aux = bb;
1109
 
1110
  /* Add fake edge exit to entry we can't instrument.  */
1111
  union_groups (EXIT_BLOCK_PTR, ENTRY_BLOCK_PTR);
1112
 
1113
  /* First add all abnormal edges to the tree unless they form a cycle. Also
1114
     add all edges to EXIT_BLOCK_PTR to avoid inserting profiling code behind
1115
     setting return value from function.  */
1116
  for (i = 0; i < num_edges; i++)
1117
    {
1118
      edge e = INDEX_EDGE (el, i);
1119
      if (((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_FAKE))
1120
           || e->dest == EXIT_BLOCK_PTR)
1121
          && !EDGE_INFO (e)->ignore
1122
          && (find_group (e->src) != find_group (e->dest)))
1123
        {
1124
          if (dump_file)
1125
            fprintf (dump_file, "Abnormal edge %d to %d put to tree\n",
1126
                     e->src->index, e->dest->index);
1127
          EDGE_INFO (e)->on_tree = 1;
1128
          union_groups (e->src, e->dest);
1129
        }
1130
    }
1131
 
1132
  /* Now insert all critical edges to the tree unless they form a cycle.  */
1133
  for (i = 0; i < num_edges; i++)
1134
    {
1135
      edge e = INDEX_EDGE (el, i);
1136
      if (EDGE_CRITICAL_P (e) && !EDGE_INFO (e)->ignore
1137
          && find_group (e->src) != find_group (e->dest))
1138
        {
1139
          if (dump_file)
1140
            fprintf (dump_file, "Critical edge %d to %d put to tree\n",
1141
                     e->src->index, e->dest->index);
1142
          EDGE_INFO (e)->on_tree = 1;
1143
          union_groups (e->src, e->dest);
1144
        }
1145
    }
1146
 
1147
  /* And now the rest.  */
1148
  for (i = 0; i < num_edges; i++)
1149
    {
1150
      edge e = INDEX_EDGE (el, i);
1151
      if (!EDGE_INFO (e)->ignore
1152
          && find_group (e->src) != find_group (e->dest))
1153
        {
1154
          if (dump_file)
1155
            fprintf (dump_file, "Normal edge %d to %d put to tree\n",
1156
                     e->src->index, e->dest->index);
1157
          EDGE_INFO (e)->on_tree = 1;
1158
          union_groups (e->src, e->dest);
1159
        }
1160
    }
1161
 
1162
  FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1163
    bb->aux = NULL;
1164
}
1165
 
1166
/* Perform file-level initialization for branch-prob processing.  */
1167
 
1168
void
1169
init_branch_prob (void)
1170
{
1171
  int i;
1172
 
1173
  total_num_blocks = 0;
1174
  total_num_edges = 0;
1175
  total_num_edges_ignored = 0;
1176
  total_num_edges_instrumented = 0;
1177
  total_num_blocks_created = 0;
1178
  total_num_passes = 0;
1179
  total_num_times_called = 0;
1180
  total_num_branches = 0;
1181
  total_num_never_executed = 0;
1182
  for (i = 0; i < 20; i++)
1183
    total_hist_br_prob[i] = 0;
1184
}
1185
 
1186
/* Performs file-level cleanup after branch-prob processing
1187
   is completed.  */
1188
 
1189
void
1190
end_branch_prob (void)
1191
{
1192
  if (dump_file)
1193
    {
1194
      fprintf (dump_file, "\n");
1195
      fprintf (dump_file, "Total number of blocks: %d\n",
1196
               total_num_blocks);
1197
      fprintf (dump_file, "Total number of edges: %d\n", total_num_edges);
1198
      fprintf (dump_file, "Total number of ignored edges: %d\n",
1199
               total_num_edges_ignored);
1200
      fprintf (dump_file, "Total number of instrumented edges: %d\n",
1201
               total_num_edges_instrumented);
1202
      fprintf (dump_file, "Total number of blocks created: %d\n",
1203
               total_num_blocks_created);
1204
      fprintf (dump_file, "Total number of graph solution passes: %d\n",
1205
               total_num_passes);
1206
      if (total_num_times_called != 0)
1207
        fprintf (dump_file, "Average number of graph solution passes: %d\n",
1208
                 (total_num_passes + (total_num_times_called  >> 1))
1209
                 / total_num_times_called);
1210
      fprintf (dump_file, "Total number of branches: %d\n",
1211
               total_num_branches);
1212
      fprintf (dump_file, "Total number of branches never executed: %d\n",
1213
               total_num_never_executed);
1214
      if (total_num_branches)
1215
        {
1216
          int i;
1217
 
1218
          for (i = 0; i < 10; i++)
1219
            fprintf (dump_file, "%d%% branches in range %d-%d%%\n",
1220
                     (total_hist_br_prob[i] + total_hist_br_prob[19-i]) * 100
1221
                     / total_num_branches, 5*i, 5*i+5);
1222
        }
1223
    }
1224
}
1225
 
1226
/* Set up hooks to enable tree-based profiling.  */
1227
 
1228
void
1229
tree_register_profile_hooks (void)
1230
{
1231
  gcc_assert (ir_type ());
1232
  profile_hooks = &tree_profile_hooks;
1233
}
1234
 

powered by: WebSVN 2.1.0

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