Merge branch 'vendor/OPENSSL'
[dragonfly.git] / contrib / binutils-2.24 / gprof / basic_blocks.c
1 /* basic_blocks.c  -  Basic-block level related code: reading/writing
2    of basic-block info to/from gmon.out; computing and formatting of
3    basic-block related statistics.
4
5    Copyright 1999, 2000, 2001, 2002, 2004, 2005, 2007
6    Free Software Foundation, Inc.
7
8    This file is part of GNU Binutils.
9
10    This program is free software; you can redistribute it and/or modify
11    it under the terms of the GNU General Public License as published by
12    the Free Software Foundation; either version 3 of the License, or
13    (at your option) any later version.
14
15    This program is distributed in the hope that it will be useful,
16    but WITHOUT ANY WARRANTY; without even the implied warranty of
17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
18    GNU General Public License for more details.
19
20    You should have received a copy of the GNU General Public License
21    along with this program; if not, write to the Free Software
22    Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA
23    02110-1301, USA.  */
24 \f
25 #include "gprof.h"
26 #include "libiberty.h"
27 #include "filenames.h"
28 #include "basic_blocks.h"
29 #include "corefile.h"
30 #include "gmon_io.h"
31 #include "gmon_out.h"
32 #include "search_list.h"
33 #include "source.h"
34 #include "symtab.h"
35 #include "sym_ids.h"
36
37 static int cmp_bb (const PTR, const PTR);
38 static int cmp_ncalls (const PTR, const PTR);
39 static void fskip_string (FILE *);
40 static void annotate_with_count (char *, unsigned int, int, PTR);
41
42 /* Default option values:  */
43 bfd_boolean bb_annotate_all_lines = FALSE;
44 unsigned long bb_min_calls = 1;
45 int bb_table_length = 10;
46
47 /* Variables used to compute annotated source listing stats:  */
48 static long num_executable_lines;
49 static long num_lines_executed;
50
51
52 /* Helper for sorting.  Compares two symbols and returns result
53    such that sorting will be increasing according to filename, line
54    number, and address (in that order).  */
55
56 static int
57 cmp_bb (const PTR lp, const PTR rp)
58 {
59   int r;
60   const Sym *left = *(const Sym **) lp;
61   const Sym *right = *(const Sym **) rp;
62
63   if (left->file && right->file)
64     {
65       r = filename_cmp (left->file->name, right->file->name);
66
67       if (r)
68         return r;
69
70       if (left->line_num != right->line_num)
71         return left->line_num - right->line_num;
72     }
73
74   if (left->addr < right->addr)
75     return -1;
76   else if (left->addr > right->addr)
77     return 1;
78   else
79     return 0;
80 }
81
82
83 /* Helper for sorting.  Order basic blocks in decreasing number of
84    calls, ties are broken in increasing order of line numbers.  */
85 static int
86 cmp_ncalls (const PTR lp, const PTR rp)
87 {
88   const Sym *left = *(const Sym **) lp;
89   const Sym *right = *(const Sym **) rp;
90
91   if (!left)
92     return 1;
93   else if (!right)
94     return -1;
95
96   if (left->ncalls < right->ncalls)
97     return 1;
98   else if (left->ncalls > right->ncalls)
99     return -1;
100
101   return left->line_num - right->line_num;
102 }
103
104 /* Skip over variable length string.  */
105 static void
106 fskip_string (FILE *fp)
107 {
108   int ch;
109
110   while ((ch = fgetc (fp)) != EOF)
111     {
112       if (ch == '\0')
113         break;
114     }
115 }
116
117 /* Read a basic-block record from file IFP.  FILENAME is the name
118    of file IFP and is provided for formatting error-messages only.  */
119
120 void
121 bb_read_rec (FILE *ifp, const char *filename)
122 {
123   unsigned int nblocks, b;
124   bfd_vma addr, ncalls;
125   Sym *sym;
126
127   if (gmon_io_read_32 (ifp, &nblocks))
128     {
129       fprintf (stderr, _("%s: %s: unexpected end of file\n"),
130                whoami, filename);
131       done (1);
132     }
133
134   nblocks = bfd_get_32 (core_bfd, (bfd_byte *) & nblocks);
135   if (gmon_file_version == 0)
136     fskip_string (ifp);
137
138   for (b = 0; b < nblocks; ++b)
139     {
140       if (gmon_file_version == 0)
141         {
142           int line_num;
143
144           /* Version 0 had lots of extra stuff that we don't
145              care about anymore.  */
146           if ((fread (&ncalls, sizeof (ncalls), 1, ifp) != 1)
147               || (fread (&addr, sizeof (addr), 1, ifp) != 1)
148               || (fskip_string (ifp), FALSE)
149               || (fskip_string (ifp), FALSE)
150               || (fread (&line_num, sizeof (line_num), 1, ifp) != 1))
151             {
152               perror (filename);
153               done (1);
154             }
155         }
156       else if (gmon_io_read_vma (ifp, &addr)
157                || gmon_io_read_vma (ifp, &ncalls))
158         {
159           perror (filename);
160           done (1);
161         }
162
163       /* Basic-block execution counts are meaningful only if we're
164          profiling at the line-by-line level:  */
165       if (line_granularity)
166         {
167           sym = sym_lookup (&symtab, addr);
168
169           if (sym)
170             {
171               int i;
172
173               DBG (BBDEBUG,
174                    printf ("[bb_read_rec] 0x%lx->0x%lx (%s:%d) cnt=%lu\n",
175                            (unsigned long) addr, (unsigned long) sym->addr,
176                            sym->name, sym->line_num, (unsigned long) ncalls));
177
178               for (i = 0; i < NBBS; i++)
179                 {
180                   if (! sym->bb_addr[i] || sym->bb_addr[i] == addr)
181                     {
182                       sym->bb_addr[i] = addr;
183                       sym->bb_calls[i] += ncalls;
184                       break;
185                     }
186                 }
187             }
188         }
189       else
190         {
191           static bfd_boolean user_warned = FALSE;
192
193           if (!user_warned)
194             {
195               user_warned = TRUE;
196               fprintf (stderr,
197   _("%s: warning: ignoring basic-block exec counts (use -l or --line)\n"),
198                        whoami);
199             }
200         }
201     }
202   return;
203 }
204
205 /* Write all basic-blocks with non-zero counts to file OFP.  FILENAME
206    is the name of OFP and is provided for producing error-messages
207    only.  */
208 void
209 bb_write_blocks (FILE *ofp, const char *filename)
210 {
211   unsigned int nblocks = 0;
212   Sym *sym;
213   int i;
214
215   /* Count how many non-zero blocks with have:  */
216   for (sym = symtab.base; sym < symtab.limit; ++sym)
217     {
218       for (i = 0; i < NBBS && sym->bb_addr[i]; i++)
219         ;
220       nblocks += i;
221     }
222
223   /* Write header:  */
224   if (gmon_io_write_8 (ofp, GMON_TAG_BB_COUNT)
225       || gmon_io_write_32 (ofp, nblocks))
226     {
227       perror (filename);
228       done (1);
229     }
230
231   /* Write counts:  */
232   for (sym = symtab.base; sym < symtab.limit; ++sym)
233     {
234       for (i = 0; i < NBBS && sym->bb_addr[i]; i++)
235         {
236           if (gmon_io_write_vma (ofp, sym->bb_addr[i])
237               || gmon_io_write_vma (ofp, (bfd_vma) sym->bb_calls[i]))
238             {
239               perror (filename);
240               done (1);
241             }
242         }
243     }
244 }
245
246 /* Output basic-block statistics in a format that is easily parseable.
247    Current the format is:
248
249         <filename>:<line-number>: (<function-name>:<bb-addr): <ncalls>  */
250
251 void
252 print_exec_counts ()
253 {
254   Sym **sorted_bbs, *sym;
255   unsigned int i, j, len;
256
257   if (first_output)
258     first_output = FALSE;
259   else
260     printf ("\f\n");
261
262   /* Sort basic-blocks according to function name and line number:  */
263   sorted_bbs = (Sym **) xmalloc (symtab.len * sizeof (sorted_bbs[0]));
264   len = 0;
265
266   for (sym = symtab.base; sym < symtab.limit; ++sym)
267     {
268       /* Accept symbol if it's in the INCL_EXEC table
269          or there is no INCL_EXEC table
270          and it does not appear in the EXCL_EXEC table.  */
271       if (sym_lookup (&syms[INCL_EXEC], sym->addr)
272           || (syms[INCL_EXEC].len == 0
273               && !sym_lookup (&syms[EXCL_EXEC], sym->addr)))
274         {
275           sorted_bbs[len++] = sym;
276         }
277     }
278
279   qsort (sorted_bbs, len, sizeof (sorted_bbs[0]), cmp_bb);
280
281   /* Output basic-blocks:  */
282
283   for (i = 0; i < len; ++i)
284     {
285       sym = sorted_bbs [i];
286       
287       if (sym->ncalls > 0 || ! ignore_zeros)
288         {
289           /* FIXME: This only works if bfd_vma is unsigned long.  */
290           printf (_("%s:%d: (%s:0x%lx) %lu executions\n"),
291                   sym->file ? sym->file->name : _("<unknown>"), sym->line_num,
292                   sym->name, (unsigned long) sym->addr, sym->ncalls);
293         }
294
295       for (j = 0; j < NBBS && sym->bb_addr[j]; j ++)
296         {
297           if (sym->bb_calls[j] > 0 || ! ignore_zeros)
298             {
299               /* FIXME: This only works if bfd_vma is unsigned long.  */
300               printf (_("%s:%d: (%s:0x%lx) %lu executions\n"),
301                       sym->file ? sym->file->name : _("<unknown>"), sym->line_num,
302                       sym->name, (unsigned long) sym->bb_addr[j],
303                       sym->bb_calls[j]);
304             }
305         }
306     }
307   free (sorted_bbs);
308 }
309
310 /* Helper for bb_annotated_source: format annotation containing
311    number of line executions.  Depends on being called on each
312    line of a file in sequential order.
313
314    Global variable bb_annotate_all_lines enables execution count
315    compression (counts are supressed if identical to the last one)
316    and prints counts on all executed lines.  Otherwise, print
317    all basic-block execution counts exactly once on the line
318    that starts the basic-block.  */
319
320 static void
321 annotate_with_count (char *buf, unsigned int width, int line_num, PTR arg)
322 {
323   Source_File *sf = (Source_File *) arg;
324   Sym *b;
325   unsigned int i;
326   static unsigned long last_count;
327   unsigned long last_print = (unsigned long) -1;
328
329   b = NULL;
330
331   if (line_num <= sf->num_lines)
332     b = (Sym *) sf->line[line_num - 1];
333
334   if (!b)
335     {
336       for (i = 0; i < width; i++)
337         buf[i] = ' ';
338       buf[width] = '\0';
339     }
340   else
341     {
342       char tmpbuf[NBBS * 30];
343       char *p;
344       unsigned long ncalls;
345       int ncalls_set;
346       unsigned int len;
347
348       ++num_executable_lines;
349
350       p = tmpbuf;
351       *p = '\0';
352
353       ncalls = 0;
354       ncalls_set = 0;
355
356       /* If this is a function entry point, label the line no matter what.
357          Otherwise, we're in the middle of a function, so check to see
358          if the first basic-block address is larger than the starting
359          address of the line.  If so, then this line begins with a
360          a portion of the previous basic-block, so print that prior
361          execution count (if bb_annotate_all_lines is set).  */
362       if (b->is_func)
363         {
364           sprintf (p, "%lu", b->ncalls);
365           p += strlen (p);
366           last_count = b->ncalls;
367           last_print = last_count;
368           ncalls = b->ncalls;
369           ncalls_set = 1;
370         }
371       else if (bb_annotate_all_lines
372                && b->bb_addr[0] && b->bb_addr[0] > b->addr)
373         {
374           sprintf (p, "%lu", last_count);
375           p += strlen (p);
376           last_print = last_count;
377           ncalls = last_count;
378           ncalls_set = 1;
379         }
380
381       /* Loop through all of this line's basic-blocks.  For each one,
382          update last_count, then compress sequential identical counts
383          (if bb_annotate_all_lines) and print the execution count.  */
384
385       for (i = 0; i < NBBS && b->bb_addr[i]; i++)
386         {
387           last_count = b->bb_calls[i];
388           if (! ncalls_set)
389             {
390               ncalls = 0;
391               ncalls_set = 1;
392             }
393           ncalls += last_count;
394
395           if (bb_annotate_all_lines && last_count == last_print)
396             continue;
397
398           if (p > tmpbuf)
399             *p++ = ',';
400           sprintf (p, "%lu", last_count);
401           p += strlen (p);
402
403           last_print = last_count;
404         }
405
406       /* We're done.  If nothing has been printed on this line,
407          print the last execution count (bb_annotate_all_lines),
408          which could be from either a previous line (if there were
409          no BBs on this line), or from this line (if all our BB
410          counts were compressed out because they were identical).  */
411
412       if (bb_annotate_all_lines && p == tmpbuf)
413         {
414           sprintf (p, "%lu", last_count);
415           p += strlen (p);
416           ncalls = last_count;
417           ncalls_set = 1;
418         }
419
420       if (! ncalls_set)
421         {
422           unsigned int c;
423
424           for (c = 0; c < width; c++)
425             buf[c] = ' ';
426           buf[width] = '\0';
427           return;
428         }
429
430       ++num_lines_executed;
431
432       if (ncalls < bb_min_calls)
433         {
434           strcpy (tmpbuf, "#####");
435           p = tmpbuf + 5;
436         }
437
438       strcpy (p, " -> ");
439       p += 4;
440
441       len = p - tmpbuf;
442       if (len >= width)
443         {
444           strncpy (buf, tmpbuf, width);
445           buf[width] = '\0';
446         }
447       else
448         {
449           unsigned int c;
450
451           strcpy (buf + width - len, tmpbuf);
452           for (c = 0; c < width - len; ++c)
453             buf[c] = ' ';
454         }
455     }
456 }
457
458 /* Annotate the files named in SOURCE_FILES with basic-block statistics
459    (execution counts).  After each source files, a few statistics
460    regarding that source file are printed.  */
461
462 void
463 print_annotated_source ()
464 {
465   Sym *sym, *line_stats, *new_line;
466   Source_File *sf;
467   int i, table_len;
468   FILE *ofp;
469
470   /* Find maximum line number for each source file that user is
471      interested in:  */
472   for (sym = symtab.base; sym < symtab.limit; ++sym)
473     {
474       /* Accept symbol if it's file is known, its line number is
475          bigger than anything we have seen for that file so far and
476          if it's in the INCL_ANNO table or there is no INCL_ANNO
477          table and it does not appear in the EXCL_ANNO table.  */
478       if (sym->file && sym->line_num > sym->file->num_lines
479           && (sym_lookup (&syms[INCL_ANNO], sym->addr)
480               || (syms[INCL_ANNO].len == 0
481                   && !sym_lookup (&syms[EXCL_ANNO], sym->addr))))
482         {
483           sym->file->num_lines = sym->line_num;
484         }
485     }
486
487   /* Allocate line descriptors:  */
488   for (sf = first_src_file; sf; sf = sf->next)
489     {
490       if (sf->num_lines > 0)
491         {
492           sf->line = (void **) xmalloc (sf->num_lines * sizeof (sf->line[0]));
493           memset (sf->line, 0, sf->num_lines * sizeof (sf->line[0]));
494         }
495     }
496
497   /* Count executions per line:  */
498   for (sym = symtab.base; sym < symtab.limit; ++sym)
499     {
500       if (sym->file && sym->file->num_lines
501           && (sym_lookup (&syms[INCL_ANNO], sym->addr)
502               || (syms[INCL_ANNO].len == 0
503                   && !sym_lookup (&syms[EXCL_ANNO], sym->addr))))
504         {
505           sym->file->ncalls += sym->ncalls;
506           line_stats = (Sym *) sym->file->line[sym->line_num - 1];
507
508           if (!line_stats)
509             {
510               /* Common case has at most one basic-block per source line:  */
511               sym->file->line[sym->line_num - 1] = sym;
512             }
513           else if (!line_stats->addr)
514             {
515               /* sym is the 3rd .. nth basic block for this line:  */
516               line_stats->ncalls += sym->ncalls;
517             }
518           else
519             {
520               /* sym is the second basic block for this line.  */
521               new_line = (Sym *) xmalloc (sizeof (*new_line));
522               *new_line = *line_stats;
523               new_line->addr = 0;
524               new_line->ncalls += sym->ncalls;
525               sym->file->line[sym->line_num - 1] = new_line;
526             }
527         }
528     }
529
530   /* Plod over source files, annotating them:  */
531   for (sf = first_src_file; sf; sf = sf->next)
532     {
533       if (!sf->num_lines || (ignore_zeros && sf->ncalls == 0))
534         continue;
535
536       num_executable_lines = num_lines_executed = 0;
537
538       ofp = annotate_source (sf, 16, annotate_with_count, sf);
539       if (!ofp)
540         continue;
541
542       if (bb_table_length > 0)
543         {
544           fprintf (ofp, _("\n\nTop %d Lines:\n\n     Line      Count\n\n"),
545                    bb_table_length);
546
547           /* Abuse line arrays---it's not needed anymore:  */
548           qsort (sf->line, sf->num_lines, sizeof (sf->line[0]), cmp_ncalls);
549           table_len = bb_table_length;
550
551           if (table_len > sf->num_lines)
552             table_len = sf->num_lines;
553
554           for (i = 0; i < table_len; ++i)
555             {
556               sym = (Sym *) sf->line[i];
557
558               if (!sym || sym->ncalls == 0)
559                   break;
560
561               fprintf (ofp, "%9d %10lu\n", sym->line_num, sym->ncalls);
562             }
563         }
564
565       free (sf->line);
566       sf->line = 0;
567
568       fprintf (ofp, _("\nExecution Summary:\n\n"));
569       fprintf (ofp, _("%9ld   Executable lines in this file\n"),
570                num_executable_lines);
571       fprintf (ofp, _("%9ld   Lines executed\n"), num_lines_executed);
572       fprintf (ofp, _("%9.2f   Percent of the file executed\n"),
573                num_executable_lines
574                ? 100.0 * num_lines_executed / (double) num_executable_lines
575                : 100.0);
576       fprintf (ofp, _("\n%9lu   Total number of line executions\n"),
577                sf->ncalls);
578       fprintf (ofp, _("%9.2f   Average executions per line\n"),
579                num_executable_lines
580                ? (double) sf->ncalls / (double) num_executable_lines
581                : 0.0);
582
583       if (ofp != stdout)
584         fclose (ofp);
585     }
586 }