gprof/hist.c

   1 /* hist.c  -  Histogram related operations.
   2
   3    Copyright 2000, 2001 Free Software Foundation, Inc.
   4
   5    This file is part of GNU Binutils.
   6
   7    This program is free software; you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 2 of the License, or
  10    (at your option) any later version.
  11
  12    This program is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with this program; if not, write to the Free Software
  19    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  20    02111-1307, USA.  */
  21 \f
  22 #include "libiberty.h"
  23 #include "gprof.h"
  24 #include "search_list.h"
  25 #include "source.h"
  26 #include "symtab.h"
  27 #include "corefile.h"
  28 #include "gmon_io.h"
  29 #include "gmon_out.h"
  30 #include "hist.h"
  31 #include "sym_ids.h"
  32 #include "utils.h"
  33
  34 #define UNITS_TO_CODE (offset_to_code / sizeof(UNIT))
  35
  36 static void scale_and_align_entries PARAMS ((void));
  37
  38 /* Declarations of automatically generated functions to output blurbs.  */
  39 extern void flat_blurb PARAMS ((FILE * fp));
  40
  41 bfd_vma s_lowpc;                /* Lowest address in .text.  */
  42 bfd_vma s_highpc = 0;           /* Highest address in .text.  */
  43 bfd_vma lowpc, highpc;          /* Same, but expressed in UNITs.  */
  44 int hist_num_bins = 0;          /* Number of histogram samples.  */
  45 int *hist_sample = 0;           /* Histogram samples (shorts in the file!).  */
  46 double hist_scale;
  47 char hist_dimension[16] = "seconds";
  48 char hist_dimension_abbrev = 's';
  49
  50 static double accum_time;       /* Accumulated time so far for print_line(). */
  51 static double total_time;       /* Total time for all routines.  */
  52
  53 /* Table of SI prefixes for powers of 10 (used to automatically
  54    scale some of the values in the flat profile).  */
  55 const struct
  56   {
  57     char prefix;
  58     double scale;
  59   }
  60 SItab[] =
  61 {
  62   { 'T', 1e-12 },                               /* tera */
  63   { 'G', 1e-09 },                               /* giga */
  64   { 'M', 1e-06 },                               /* mega */
  65   { 'K', 1e-03 },                               /* kilo */
  66   { ' ', 1e-00 },
  67   { 'm', 1e+03 },                               /* milli */
  68   { 'u', 1e+06 },                               /* micro */
  69   { 'n', 1e+09 },                               /* nano */
  70   { 'p', 1e+12 },                               /* pico */
  71   { 'f', 1e+15 },                               /* femto */
  72   { 'a', 1e+18 }                                /* ato */
  73 };
  74
  75
  76 /* Read the histogram from file IFP.  FILENAME is the name of IFP and
  77    is provided for formatting error messages only.  */
  78
  79 void
  80 DEFUN (hist_read_rec, (ifp, filename), FILE * ifp AND const char *filename)
  81 {
  82   bfd_vma n_lowpc, n_highpc;
  83   int i, ncnt, profrate;
  84   UNIT count;
  85
  86   if (gmon_io_read_vma (ifp, &n_lowpc)
  87       || gmon_io_read_vma (ifp, &n_highpc)
  88       || gmon_io_read_32 (ifp, &ncnt)
  89       || gmon_io_read_32 (ifp, &profrate)
  90       || gmon_io_read (ifp, hist_dimension, 15)
  91       || gmon_io_read (ifp, &hist_dimension_abbrev, 1))
  92     {
  93       fprintf (stderr, _("%s: %s: unexpected end of file\n"),
  94                whoami, filename);
  95
  96       done (1);
  97     }
  98
  99   if (!s_highpc)
 100     {
 101       /* This is the first histogram record.  */
 102       s_lowpc = n_lowpc;
 103       s_highpc = n_highpc;
 104       lowpc = (bfd_vma) n_lowpc / sizeof (UNIT);
 105       highpc = (bfd_vma) n_highpc / sizeof (UNIT);
 106       hist_num_bins = ncnt;
 107       hz = profrate;
 108     }
 109
 110   DBG (SAMPLEDEBUG,
 111        printf ("[hist_read_rec] n_lowpc 0x%lx n_highpc 0x%lx ncnt %d\n",
 112                (unsigned long) n_lowpc, (unsigned long) n_highpc, ncnt);
 113        printf ("[hist_read_rec] s_lowpc 0x%lx s_highpc 0x%lx nsamples %d\n",
 114                (unsigned long) s_lowpc, (unsigned long) s_highpc,
 115                hist_num_bins);
 116        printf ("[hist_read_rec]   lowpc 0x%lx   highpc 0x%lx\n",
 117                (unsigned long) lowpc, (unsigned long) highpc));
 118
 119   if (n_lowpc != s_lowpc || n_highpc != s_highpc
 120       || ncnt != hist_num_bins || hz != profrate)
 121     {
 122       fprintf (stderr, _("%s: `%s' is incompatible with first gmon file\n"),
 123                whoami, filename);
 124       done (1);
 125     }
 126
 127   if (!hist_sample)
 128     {
 129       hist_sample = (int *) xmalloc (hist_num_bins * sizeof (hist_sample[0]));
 130       memset (hist_sample, 0, hist_num_bins * sizeof (hist_sample[0]));
 131     }
 132
 133   for (i = 0; i < hist_num_bins; ++i)
 134     {
 135       if (fread (&count[0], sizeof (count), 1, ifp) != 1)
 136         {
 137           fprintf (stderr,
 138                   _("%s: %s: unexpected EOF after reading %d of %d samples\n"),
 139                    whoami, filename, i, hist_num_bins);
 140           done (1);
 141         }
 142       hist_sample[i] += bfd_get_16 (core_bfd, (bfd_byte *) & count[0]);
 143       DBG (SAMPLEDEBUG,
 144            printf ("[hist_read_rec] 0x%lx: %u\n",
 145                    (unsigned long) (n_lowpc + i * (n_highpc - n_lowpc) / ncnt),
 146                    hist_sample[i]));
 147     }
 148 }
 149
 150
 151 /* Write execution histogram to file OFP.  FILENAME is the name
 152    of OFP and is provided for formatting error-messages only.  */
 153
 154 void
 155 DEFUN (hist_write_hist, (ofp, filename), FILE * ofp AND const char *filename)
 156 {
 157   UNIT count;
 158   int i;
 159
 160   /* Write header.  */
 161
 162   if (gmon_io_write_8 (ofp, GMON_TAG_TIME_HIST)
 163       || gmon_io_write_vma (ofp, s_lowpc)
 164       || gmon_io_write_vma (ofp, s_highpc)
 165       || gmon_io_write_32 (ofp, hist_num_bins)
 166       || gmon_io_write_32 (ofp, hz)
 167       || gmon_io_write (ofp, hist_dimension, 15)
 168       || gmon_io_write (ofp, &hist_dimension_abbrev, 1))
 169     {
 170       perror (filename);
 171       done (1);
 172     }
 173
 174   for (i = 0; i < hist_num_bins; ++i)
 175     {
 176       bfd_put_16 (core_bfd, hist_sample[i], (bfd_byte *) & count[0]);
 177
 178       if (fwrite (&count[0], sizeof (count), 1, ofp) != 1)
 179         {
 180           perror (filename);
 181           done (1);
 182         }
 183     }
 184 }
 185
 186
 187 /* Calculate scaled entry point addresses (to save time in
 188    hist_assign_samples), and, on architectures that have procedure
 189    entry masks at the start of a function, possibly push the scaled
 190    entry points over the procedure entry mask, if it turns out that
 191    the entry point is in one bin and the code for a routine is in the
 192    next bin.  */
 193
 194 static void
 195 scale_and_align_entries ()
 196 {
 197   Sym *sym;
 198   bfd_vma bin_of_entry;
 199   bfd_vma bin_of_code;
 200
 201   for (sym = symtab.base; sym < symtab.limit; sym++)
 202     {
 203       sym->hist.scaled_addr = sym->addr / sizeof (UNIT);
 204       bin_of_entry = (sym->hist.scaled_addr - lowpc) / hist_scale;
 205       bin_of_code = ((sym->hist.scaled_addr + UNITS_TO_CODE - lowpc)
 206                      / hist_scale);
 207       if (bin_of_entry < bin_of_code)
 208         {
 209           DBG (SAMPLEDEBUG,
 210                printf ("[scale_and_align_entries] pushing 0x%lx to 0x%lx\n",
 211                        (unsigned long) sym->hist.scaled_addr,
 212                        (unsigned long) (sym->hist.scaled_addr
 213                                         + UNITS_TO_CODE)));
 214           sym->hist.scaled_addr += UNITS_TO_CODE;
 215         }
 216     }
 217 }
 218
 219
 220 /* Assign samples to the symbol to which they belong.
 221
 222    Histogram bin I covers some address range [BIN_LOWPC,BIN_HIGH_PC)
 223    which may overlap one more symbol address ranges.  If a symbol
 224    overlaps with the bin's address range by O percent, then O percent
 225    of the bin's count is credited to that symbol.
 226
 227    There are three cases as to where BIN_LOW_PC and BIN_HIGH_PC can be
 228    with respect to the symbol's address range [SYM_LOW_PC,
 229    SYM_HIGH_PC) as shown in the following diagram.  OVERLAP computes
 230    the distance (in UNITs) between the arrows, the fraction of the
 231    sample that is to be credited to the symbol which starts at
 232    SYM_LOW_PC.
 233
 234           sym_low_pc                                      sym_high_pc
 235                |                                               |
 236                v                                               v
 237
 238                +-----------------------------------------------+
 239                |                                               |
 240           |  ->|    |<-         ->|         |<-         ->|    |<-  |
 241           |         |             |         |             |         |
 242           +---------+             +---------+             +---------+
 243
 244           ^         ^             ^         ^             ^         ^
 245           |         |             |         |             |         |
 246      bin_low_pc bin_high_pc  bin_low_pc bin_high_pc  bin_low_pc bin_high_pc
 247
 248    For the VAX we assert that samples will never fall in the first two
 249    bytes of any routine, since that is the entry mask, thus we call
 250    scale_and_align_entries() to adjust the entry points if the entry
 251    mask falls in one bin but the code for the routine doesn't start
 252    until the next bin.  In conjunction with the alignment of routine
 253    addresses, this should allow us to have only one sample for every
 254    four bytes of text space and never have any overlap (the two end
 255    cases, above).  */
 256
 257 void
 258 DEFUN_VOID (hist_assign_samples)
 259 {
 260   bfd_vma bin_low_pc, bin_high_pc;
 261   bfd_vma sym_low_pc, sym_high_pc;
 262   bfd_vma overlap, addr;
 263   int bin_count, i;
 264   unsigned int j;
 265   double time, credit;
 266
 267   /* Read samples and assign to symbols.  */
 268   hist_scale = highpc - lowpc;
 269   hist_scale /= hist_num_bins;
 270   scale_and_align_entries ();
 271
 272   /* Iterate over all sample bins.  */
 273   for (i = 0, j = 1; i < hist_num_bins; ++i)
 274     {
 275       bin_count = hist_sample[i];
 276       if (! bin_count)
 277         continue;
 278
 279       bin_low_pc = lowpc + (bfd_vma) (hist_scale * i);
 280       bin_high_pc = lowpc + (bfd_vma) (hist_scale * (i + 1));
 281       time = bin_count;
 282
 283       DBG (SAMPLEDEBUG,
 284            printf (
 285       "[assign_samples] bin_low_pc=0x%lx, bin_high_pc=0x%lx, bin_count=%d\n",
 286                     (unsigned long) (sizeof (UNIT) * bin_low_pc),
 287                     (unsigned long) (sizeof (UNIT) * bin_high_pc),
 288                     bin_count));
 289       total_time += time;
 290
 291       /* Credit all symbols that are covered by bin I.  */
 292       for (j = j - 1; j < symtab.len; ++j)
 293         {
 294           sym_low_pc = symtab.base[j].hist.scaled_addr;
 295           sym_high_pc = symtab.base[j + 1].hist.scaled_addr;
 296
 297           /* If high end of bin is below entry address,
 298              go for next bin.  */
 299           if (bin_high_pc < sym_low_pc)
 300             break;
 301
 302           /* If low end of bin is above high end of symbol,
 303              go for next symbol.  */
 304           if (bin_low_pc >= sym_high_pc)
 305             continue;
 306
 307           overlap =
 308             MIN (bin_high_pc, sym_high_pc) - MAX (bin_low_pc, sym_low_pc);
 309           if (overlap > 0)
 310             {
 311               DBG (SAMPLEDEBUG,
 312                    printf (
 313                "[assign_samples] [0x%lx,0x%lx) %s gets %f ticks %ld overlap\n",
 314                            (unsigned long) symtab.base[j].addr,
 315                            (unsigned long) (sizeof (UNIT) * sym_high_pc),
 316                            symtab.base[j].name, overlap * time / hist_scale,
 317                            (long) overlap));
 318
 319               addr = symtab.base[j].addr;
 320               credit = overlap * time / hist_scale;
 321
 322               /* Credit symbol if it appears in INCL_FLAT or that
 323                  table is empty and it does not appear it in
 324                  EXCL_FLAT.  */
 325               if (sym_lookup (&syms[INCL_FLAT], addr)
 326                   || (syms[INCL_FLAT].len == 0
 327                       && !sym_lookup (&syms[EXCL_FLAT], addr)))
 328                 {
 329                   symtab.base[j].hist.time += credit;
 330                 }
 331               else
 332                 {
 333                   total_time -= credit;
 334                 }
 335             }
 336         }
 337     }
 338
 339   DBG (SAMPLEDEBUG, printf ("[assign_samples] total_time %f\n",
 340                             total_time));
 341 }
 342
 343
 344 /* Print header for flag histogram profile.  */
 345
 346 static void
 347 DEFUN (print_header, (prefix), const char prefix)
 348 {
 349   char unit[64];
 350
 351   sprintf (unit, _("%c%c/call"), prefix, hist_dimension_abbrev);
 352
 353   if (bsd_style_output)
 354     {
 355       printf (_("\ngranularity: each sample hit covers %ld byte(s)"),
 356               (long) hist_scale * sizeof (UNIT));
 357       if (total_time > 0.0)
 358         {
 359           printf (_(" for %.2f%% of %.2f %s\n\n"),
 360                   100.0 / total_time, total_time / hz, hist_dimension);
 361         }
 362     }
 363   else
 364     {
 365       printf (_("\nEach sample counts as %g %s.\n"), 1.0 / hz, hist_dimension);
 366     }
 367
 368   if (total_time <= 0.0)
 369     {
 370       printf (_(" no time accumulated\n\n"));
 371
 372       /* This doesn't hurt since all the numerators will be zero.  */
 373       total_time = 1.0;
 374     }
 375
 376   printf ("%5.5s %10.10s %8.8s %8.8s %8.8s %8.8s  %-8.8s\n",
 377           "%  ", _("cumulative"), _("self  "), "", _("self  "), _("total "),
 378           "");
 379   printf ("%5.5s %9.9s  %8.8s %8.8s %8.8s %8.8s  %-8.8s\n",
 380           _("time"), hist_dimension, hist_dimension, _("calls"), unit, unit,
 381           _("name"));
 382 }
 383
 384
 385 static void
 386 DEFUN (print_line, (sym, scale), Sym * sym AND double scale)
 387 {
 388   if (ignore_zeros && sym->ncalls == 0 && sym->hist.time == 0)
 389     return;
 390
 391   accum_time += sym->hist.time;
 392
 393   if (bsd_style_output)
 394     printf ("%5.1f %10.2f %8.2f",
 395             total_time > 0.0 ? 100 * sym->hist.time / total_time : 0.0,
 396             accum_time / hz, sym->hist.time / hz);
 397   else
 398     printf ("%6.2f %9.2f %8.2f",
 399             total_time > 0.0 ? 100 * sym->hist.time / total_time : 0.0,
 400             accum_time / hz, sym->hist.time / hz);
 401
 402   if (sym->ncalls != 0)
 403     printf (" %8lu %8.2f %8.2f  ",
 404             sym->ncalls, scale * sym->hist.time / hz / sym->ncalls,
 405             scale * (sym->hist.time + sym->cg.child_time) / hz / sym->ncalls);
 406   else
 407     printf (" %8.8s %8.8s %8.8s  ", "", "", "");
 408
 409   if (bsd_style_output)
 410     print_name (sym);
 411   else
 412     print_name_only (sym);
 413
 414   printf ("\n");
 415 }
 416
 417
 418 /* Compare LP and RP.  The primary comparison key is execution time,
 419    the secondary is number of invocation, and the tertiary is the
 420    lexicographic order of the function names.  */
 421
 422 static int
 423 DEFUN (cmp_time, (lp, rp), const PTR lp AND const PTR rp)
 424 {
 425   const Sym *left = *(const Sym **) lp;
 426   const Sym *right = *(const Sym **) rp;
 427   double time_diff;
 428
 429   time_diff = right->hist.time - left->hist.time;
 430
 431   if (time_diff > 0.0)
 432     return 1;
 433
 434   if (time_diff < 0.0)
 435     return -1;
 436
 437   if (right->ncalls > left->ncalls)
 438     return 1;
 439
 440   if (right->ncalls < left->ncalls)
 441     return -1;
 442
 443   return strcmp (left->name, right->name);
 444 }
 445
 446
 447 /* Print the flat histogram profile.  */
 448
 449 void
 450 DEFUN_VOID (hist_print)
 451 {
 452   Sym **time_sorted_syms, *top_dog, *sym;
 453   unsigned int index;
 454   int log_scale;
 455   double top_time, time;
 456   bfd_vma addr;
 457
 458   if (first_output)
 459     first_output = FALSE;
 460   else
 461     printf ("\f\n");
 462
 463   accum_time = 0.0;
 464
 465   if (bsd_style_output)
 466     {
 467       if (print_descriptions)
 468         {
 469           printf (_("\n\n\nflat profile:\n"));
 470           flat_blurb (stdout);
 471         }
 472     }
 473   else
 474     {
 475       printf (_("Flat profile:\n"));
 476     }
 477
 478   /* Sort the symbol table by time (call-count and name as secondary
 479      and tertiary keys).  */
 480   time_sorted_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *));
 481
 482   for (index = 0; index < symtab.len; ++index)
 483     time_sorted_syms[index] = &symtab.base[index];
 484
 485   qsort (time_sorted_syms, symtab.len, sizeof (Sym *), cmp_time);
 486
 487   if (bsd_style_output)
 488     {
 489       log_scale = 5;            /* Milli-seconds is BSD-default.  */
 490     }
 491   else
 492     {
 493       /* Search for symbol with highest per-call
 494          execution time and scale accordingly.  */
 495       log_scale = 0;
 496       top_dog = 0;
 497       top_time = 0.0;
 498
 499       for (index = 0; index < symtab.len; ++index)
 500         {
 501           sym = time_sorted_syms[index];
 502
 503           if (sym->ncalls != 0)
 504             {
 505               time = (sym->hist.time + sym->cg.child_time) / sym->ncalls;
 506
 507               if (time > top_time)
 508                 {
 509                   top_dog = sym;
 510                   top_time = time;
 511                 }
 512             }
 513         }
 514
 515       if (top_dog && top_dog->ncalls != 0 && top_time > 0.0)
 516         {
 517           top_time /= hz;
 518
 519           while (SItab[log_scale].scale * top_time < 1000.0
 520                  && ((size_t) log_scale
 521                      < sizeof (SItab) / sizeof (SItab[0]) - 1))
 522             {
 523               ++log_scale;
 524             }
 525         }
 526     }
 527
 528   /* For now, the dimension is always seconds.  In the future, we
 529      may also want to support other (pseudo-)dimensions (such as
 530      I-cache misses etc.).  */
 531   print_header (SItab[log_scale].prefix);
 532
 533   for (index = 0; index < symtab.len; ++index)
 534     {
 535       addr = time_sorted_syms[index]->addr;
 536
 537       /* Print symbol if its in INCL_FLAT table or that table
 538         is empty and the symbol is not in EXCL_FLAT.  */
 539       if (sym_lookup (&syms[INCL_FLAT], addr)
 540           || (syms[INCL_FLAT].len == 0
 541               && !sym_lookup (&syms[EXCL_FLAT], addr)))
 542         print_line (time_sorted_syms[index], SItab[log_scale].scale);
 543     }
 544
 545   free (time_sorted_syms);
 546
 547   if (print_descriptions && !bsd_style_output)
 548     flat_blurb (stdout);
 549 }