gcc/gcov-io.c

   1 /* File format for coverage information
   2    Copyright (C) 1996-2014 Free Software Foundation, Inc.
   3    Contributed by Bob Manson <manson@cygnus.com>.
   4    Completely remangled by Nathan Sidwell <nathan@codesourcery.com>.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 Under Section 7 of GPL version 3, you are granted additional
  19 permissions described in the GCC Runtime Library Exception, version
  20 3.1, as published by the Free Software Foundation.
  21
  22 You should have received a copy of the GNU General Public License and
  23 a copy of the GCC Runtime Library Exception along with this program;
  24 see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  25 <http://www.gnu.org/licenses/>.  */
  26
  27 /* Routines declared in gcov-io.h.  This file should be #included by
  28    another source file, after having #included gcov-io.h.  */
  29
  30 #if !IN_GCOV
  31 static void gcov_write_block (unsigned);
  32 static gcov_unsigned_t *gcov_write_words (unsigned);
  33 #endif
  34 static const gcov_unsigned_t *gcov_read_words (unsigned);
  35 #if !IN_LIBGCOV
  36 static void gcov_allocate (unsigned);
  37 #endif
  38
  39 /* Optimum number of gcov_unsigned_t's read from or written to disk.  */
  40 #define GCOV_BLOCK_SIZE (1 << 10)
  41
  42 GCOV_LINKAGE struct gcov_var
  43 {
  44   FILE *file;
  45   gcov_position_t start;        /* Position of first byte of block */
  46   unsigned offset;              /* Read/write position within the block.  */
  47   unsigned length;              /* Read limit in the block.  */
  48   unsigned overread;            /* Number of words overread.  */
  49   int error;                    /* < 0 overflow, > 0 disk error.  */
  50   int mode;                     /* < 0 writing, > 0 reading */
  51 #if IN_LIBGCOV
  52   /* Holds one block plus 4 bytes, thus all coverage reads & writes
  53      fit within this buffer and we always can transfer GCOV_BLOCK_SIZE
  54      to and from the disk. libgcov never backtracks and only writes 4
  55      or 8 byte objects.  */
  56   gcov_unsigned_t buffer[GCOV_BLOCK_SIZE + 1];
  57 #else
  58   int endian;                   /* Swap endianness.  */
  59   /* Holds a variable length block, as the compiler can write
  60      strings and needs to backtrack.  */
  61   size_t alloc;
  62   gcov_unsigned_t *buffer;
  63 #endif
  64 } gcov_var;
  65
  66 /* Save the current position in the gcov file.  */
  67 static inline gcov_position_t
  68 gcov_position (void)
  69 {
  70   gcc_assert (gcov_var.mode > 0);
  71   return gcov_var.start + gcov_var.offset;
  72 }
  73
  74 /* Return nonzero if the error flag is set.  */
  75 static inline int
  76 gcov_is_error (void)
  77 {
  78   return gcov_var.file ? gcov_var.error : 1;
  79 }
  80
  81 #if IN_LIBGCOV
  82 /* Move to beginning of file and initialize for writing.  */
  83 GCOV_LINKAGE inline void
  84 gcov_rewrite (void)
  85 {
  86   gcc_assert (gcov_var.mode > 0);
  87   gcov_var.mode = -1;
  88   gcov_var.start = 0;
  89   gcov_var.offset = 0;
  90   fseek (gcov_var.file, 0L, SEEK_SET);
  91 }
  92 #endif
  93
  94 static inline gcov_unsigned_t from_file (gcov_unsigned_t value)
  95 {
  96 #if !IN_LIBGCOV
  97   if (gcov_var.endian)
  98     {
  99       value = (value >> 16) | (value << 16);
 100       value = ((value & 0xff00ff) << 8) | ((value >> 8) & 0xff00ff);
 101     }
 102 #endif
 103   return value;
 104 }
 105
 106 /* Open a gcov file. NAME is the name of the file to open and MODE
 107    indicates whether a new file should be created, or an existing file
 108    opened. If MODE is >= 0 an existing file will be opened, if
 109    possible, and if MODE is <= 0, a new file will be created. Use
 110    MODE=0 to attempt to reopen an existing file and then fall back on
 111    creating a new one.  If MODE < 0, the file will be opened in
 112    read-only mode.  Otherwise it will be opened for modification.
 113    Return zero on failure, >0 on opening an existing file and <0 on
 114    creating a new one.  */
 115
 116 GCOV_LINKAGE int
 117 #if IN_LIBGCOV
 118 gcov_open (const char *name)
 119 #else
 120 gcov_open (const char *name, int mode)
 121 #endif
 122 {
 123 #if IN_LIBGCOV
 124   const int mode = 0;
 125 #endif
 126 #if GCOV_LOCKED
 127   struct flock s_flock;
 128   int fd;
 129
 130   s_flock.l_whence = SEEK_SET;
 131   s_flock.l_start = 0;
 132   s_flock.l_len = 0; /* Until EOF.  */
 133   s_flock.l_pid = getpid ();
 134 #endif
 135
 136   gcc_assert (!gcov_var.file);
 137   gcov_var.start = 0;
 138   gcov_var.offset = gcov_var.length = 0;
 139   gcov_var.overread = -1u;
 140   gcov_var.error = 0;
 141 #if !IN_LIBGCOV
 142   gcov_var.endian = 0;
 143 #endif
 144 #if GCOV_LOCKED
 145   if (mode > 0)
 146     {
 147       /* Read-only mode - acquire a read-lock.  */
 148       s_flock.l_type = F_RDLCK;
 149       /* pass mode (ignored) for compatibility */
 150       fd = open (name, O_RDONLY, S_IRUSR | S_IWUSR);
 151     }
 152   else
 153     {
 154       /* Write mode - acquire a write-lock.  */
 155       s_flock.l_type = F_WRLCK;
 156       fd = open (name, O_RDWR | O_CREAT, 0666);
 157     }
 158   if (fd < 0)
 159     return 0;
 160
 161   while (fcntl (fd, F_SETLKW, &s_flock) && errno == EINTR)
 162     continue;
 163
 164   gcov_var.file = fdopen (fd, (mode > 0) ? "rb" : "r+b");
 165
 166   if (!gcov_var.file)
 167     {
 168       close (fd);
 169       return 0;
 170     }
 171
 172   if (mode > 0)
 173     gcov_var.mode = 1;
 174   else if (mode == 0)
 175     {
 176       struct stat st;
 177
 178       if (fstat (fd, &st) < 0)
 179         {
 180           fclose (gcov_var.file);
 181           gcov_var.file = 0;
 182           return 0;
 183         }
 184       if (st.st_size != 0)
 185         gcov_var.mode = 1;
 186       else
 187         gcov_var.mode = mode * 2 + 1;
 188     }
 189   else
 190     gcov_var.mode = mode * 2 + 1;
 191 #else
 192   if (mode >= 0)
 193     gcov_var.file = fopen (name, (mode > 0) ? "rb" : "r+b");
 194
 195   if (gcov_var.file)
 196     gcov_var.mode = 1;
 197   else if (mode <= 0)
 198     {
 199       gcov_var.file = fopen (name, "w+b");
 200       if (gcov_var.file)
 201         gcov_var.mode = mode * 2 + 1;
 202     }
 203   if (!gcov_var.file)
 204     return 0;
 205 #endif
 206
 207   setbuf (gcov_var.file, (char *)0);
 208
 209   return 1;
 210 }
 211
 212 /* Close the current gcov file. Flushes data to disk. Returns nonzero
 213    on failure or error flag set.  */
 214
 215 GCOV_LINKAGE int
 216 gcov_close (void)
 217 {
 218   if (gcov_var.file)
 219     {
 220 #if !IN_GCOV
 221       if (gcov_var.offset && gcov_var.mode < 0)
 222         gcov_write_block (gcov_var.offset);
 223 #endif
 224       fclose (gcov_var.file);
 225       gcov_var.file = 0;
 226       gcov_var.length = 0;
 227     }
 228 #if !IN_LIBGCOV
 229   free (gcov_var.buffer);
 230   gcov_var.alloc = 0;
 231   gcov_var.buffer = 0;
 232 #endif
 233   gcov_var.mode = 0;
 234   return gcov_var.error;
 235 }
 236
 237 #if !IN_LIBGCOV
 238 /* Check if MAGIC is EXPECTED. Use it to determine endianness of the
 239    file. Returns +1 for same endian, -1 for other endian and zero for
 240    not EXPECTED.  */
 241
 242 GCOV_LINKAGE int
 243 gcov_magic (gcov_unsigned_t magic, gcov_unsigned_t expected)
 244 {
 245   if (magic == expected)
 246     return 1;
 247   magic = (magic >> 16) | (magic << 16);
 248   magic = ((magic & 0xff00ff) << 8) | ((magic >> 8) & 0xff00ff);
 249   if (magic == expected)
 250     {
 251       gcov_var.endian = 1;
 252       return -1;
 253     }
 254   return 0;
 255 }
 256 #endif
 257
 258 #if !IN_LIBGCOV
 259 static void
 260 gcov_allocate (unsigned length)
 261 {
 262   size_t new_size = gcov_var.alloc;
 263
 264   if (!new_size)
 265     new_size = GCOV_BLOCK_SIZE;
 266   new_size += length;
 267   new_size *= 2;
 268
 269   gcov_var.alloc = new_size;
 270   gcov_var.buffer = XRESIZEVAR (gcov_unsigned_t, gcov_var.buffer, new_size << 2);
 271 }
 272 #endif
 273
 274 #if !IN_GCOV
 275 /* Write out the current block, if needs be.  */
 276
 277 static void
 278 gcov_write_block (unsigned size)
 279 {
 280   if (fwrite (gcov_var.buffer, size << 2, 1, gcov_var.file) != 1)
 281     gcov_var.error = 1;
 282   gcov_var.start += size;
 283   gcov_var.offset -= size;
 284 }
 285
 286 /* Allocate space to write BYTES bytes to the gcov file. Return a
 287    pointer to those bytes, or NULL on failure.  */
 288
 289 static gcov_unsigned_t *
 290 gcov_write_words (unsigned words)
 291 {
 292   gcov_unsigned_t *result;
 293
 294   gcc_assert (gcov_var.mode < 0);
 295 #if IN_LIBGCOV
 296   if (gcov_var.offset >= GCOV_BLOCK_SIZE)
 297     {
 298       gcov_write_block (GCOV_BLOCK_SIZE);
 299       if (gcov_var.offset)
 300         {
 301           gcc_assert (gcov_var.offset == 1);
 302           memcpy (gcov_var.buffer, gcov_var.buffer + GCOV_BLOCK_SIZE, 4);
 303         }
 304     }
 305 #else
 306   if (gcov_var.offset + words > gcov_var.alloc)
 307     gcov_allocate (gcov_var.offset + words);
 308 #endif
 309   result = &gcov_var.buffer[gcov_var.offset];
 310   gcov_var.offset += words;
 311
 312   return result;
 313 }
 314
 315 /* Write unsigned VALUE to coverage file.  Sets error flag
 316    appropriately.  */
 317
 318 GCOV_LINKAGE void
 319 gcov_write_unsigned (gcov_unsigned_t value)
 320 {
 321   gcov_unsigned_t *buffer = gcov_write_words (1);
 322
 323   buffer[0] = value;
 324 }
 325
 326 /* Write counter VALUE to coverage file.  Sets error flag
 327    appropriately.  */
 328
 329 #if IN_LIBGCOV
 330 GCOV_LINKAGE void
 331 gcov_write_counter (gcov_type value)
 332 {
 333   gcov_unsigned_t *buffer = gcov_write_words (2);
 334
 335   buffer[0] = (gcov_unsigned_t) value;
 336   if (sizeof (value) > sizeof (gcov_unsigned_t))
 337     buffer[1] = (gcov_unsigned_t) (value >> 32);
 338   else
 339     buffer[1] = 0;
 340 }
 341 #endif /* IN_LIBGCOV */
 342
 343 #if !IN_LIBGCOV
 344 /* Write STRING to coverage file.  Sets error flag on file
 345    error, overflow flag on overflow */
 346
 347 GCOV_LINKAGE void
 348 gcov_write_string (const char *string)
 349 {
 350   unsigned length = 0;
 351   unsigned alloc = 0;
 352   gcov_unsigned_t *buffer;
 353
 354   if (string)
 355     {
 356       length = strlen (string);
 357       alloc = (length + 4) >> 2;
 358     }
 359
 360   buffer = gcov_write_words (1 + alloc);
 361
 362   buffer[0] = alloc;
 363   buffer[alloc] = 0;
 364   memcpy (&buffer[1], string, length);
 365 }
 366 #endif
 367
 368 #if !IN_LIBGCOV
 369 /* Write a tag TAG and reserve space for the record length. Return a
 370    value to be used for gcov_write_length.  */
 371
 372 GCOV_LINKAGE gcov_position_t
 373 gcov_write_tag (gcov_unsigned_t tag)
 374 {
 375   gcov_position_t result = gcov_var.start + gcov_var.offset;
 376   gcov_unsigned_t *buffer = gcov_write_words (2);
 377
 378   buffer[0] = tag;
 379   buffer[1] = 0;
 380
 381   return result;
 382 }
 383
 384 /* Write a record length using POSITION, which was returned by
 385    gcov_write_tag.  The current file position is the end of the
 386    record, and is restored before returning.  Returns nonzero on
 387    overflow.  */
 388
 389 GCOV_LINKAGE void
 390 gcov_write_length (gcov_position_t position)
 391 {
 392   unsigned offset;
 393   gcov_unsigned_t length;
 394   gcov_unsigned_t *buffer;
 395
 396   gcc_assert (gcov_var.mode < 0);
 397   gcc_assert (position + 2 <= gcov_var.start + gcov_var.offset);
 398   gcc_assert (position >= gcov_var.start);
 399   offset = position - gcov_var.start;
 400   length = gcov_var.offset - offset - 2;
 401   buffer = (gcov_unsigned_t *) &gcov_var.buffer[offset];
 402   buffer[1] = length;
 403   if (gcov_var.offset >= GCOV_BLOCK_SIZE)
 404     gcov_write_block (gcov_var.offset);
 405 }
 406
 407 #else /* IN_LIBGCOV */
 408
 409 /* Write a tag TAG and length LENGTH.  */
 410
 411 GCOV_LINKAGE void
 412 gcov_write_tag_length (gcov_unsigned_t tag, gcov_unsigned_t length)
 413 {
 414   gcov_unsigned_t *buffer = gcov_write_words (2);
 415
 416   buffer[0] = tag;
 417   buffer[1] = length;
 418 }
 419
 420 /* Write a summary structure to the gcov file.  Return nonzero on
 421    overflow.  */
 422
 423 GCOV_LINKAGE void
 424 gcov_write_summary (gcov_unsigned_t tag, const struct gcov_summary *summary)
 425 {
 426   unsigned ix, h_ix, bv_ix, h_cnt = 0;
 427   const struct gcov_ctr_summary *csum;
 428   unsigned histo_bitvector[GCOV_HISTOGRAM_BITVECTOR_SIZE];
 429
 430   /* Count number of non-zero histogram entries, and fill in a bit vector
 431      of non-zero indices. The histogram is only currently computed for arc
 432      counters.  */
 433   for (bv_ix = 0; bv_ix < GCOV_HISTOGRAM_BITVECTOR_SIZE; bv_ix++)
 434     histo_bitvector[bv_ix] = 0;
 435   csum = &summary->ctrs[GCOV_COUNTER_ARCS];
 436   for (h_ix = 0; h_ix < GCOV_HISTOGRAM_SIZE; h_ix++)
 437     {
 438       if (csum->histogram[h_ix].num_counters > 0)
 439         {
 440           histo_bitvector[h_ix / 32] |= 1 << (h_ix % 32);
 441           h_cnt++;
 442         }
 443     }
 444   gcov_write_tag_length (tag, GCOV_TAG_SUMMARY_LENGTH (h_cnt));
 445   gcov_write_unsigned (summary->checksum);
 446   for (csum = summary->ctrs, ix = GCOV_COUNTERS_SUMMABLE; ix--; csum++)
 447     {
 448       gcov_write_unsigned (csum->num);
 449       gcov_write_unsigned (csum->runs);
 450       gcov_write_counter (csum->sum_all);
 451       gcov_write_counter (csum->run_max);
 452       gcov_write_counter (csum->sum_max);
 453       if (ix != GCOV_COUNTER_ARCS)
 454         {
 455           for (bv_ix = 0; bv_ix < GCOV_HISTOGRAM_BITVECTOR_SIZE; bv_ix++)
 456             gcov_write_unsigned (0);
 457           continue;
 458         }
 459       for (bv_ix = 0; bv_ix < GCOV_HISTOGRAM_BITVECTOR_SIZE; bv_ix++)
 460         gcov_write_unsigned (histo_bitvector[bv_ix]);
 461       for (h_ix = 0; h_ix < GCOV_HISTOGRAM_SIZE; h_ix++)
 462         {
 463           if (!csum->histogram[h_ix].num_counters)
 464             continue;
 465           gcov_write_unsigned (csum->histogram[h_ix].num_counters);
 466           gcov_write_counter (csum->histogram[h_ix].min_value);
 467           gcov_write_counter (csum->histogram[h_ix].cum_value);
 468         }
 469     }
 470 }
 471 #endif /* IN_LIBGCOV */
 472
 473 #endif /*!IN_GCOV */
 474
 475 /* Return a pointer to read BYTES bytes from the gcov file. Returns
 476    NULL on failure (read past EOF).  */
 477
 478 static const gcov_unsigned_t *
 479 gcov_read_words (unsigned words)
 480 {
 481   const gcov_unsigned_t *result;
 482   unsigned excess = gcov_var.length - gcov_var.offset;
 483
 484   gcc_assert (gcov_var.mode > 0);
 485   if (excess < words)
 486     {
 487       gcov_var.start += gcov_var.offset;
 488 #if IN_LIBGCOV
 489       if (excess)
 490         {
 491           gcc_assert (excess == 1);
 492           memcpy (gcov_var.buffer, gcov_var.buffer + gcov_var.offset, 4);
 493         }
 494 #else
 495       memmove (gcov_var.buffer, gcov_var.buffer + gcov_var.offset, excess * 4);
 496 #endif
 497       gcov_var.offset = 0;
 498       gcov_var.length = excess;
 499 #if IN_LIBGCOV
 500       gcc_assert (!gcov_var.length || gcov_var.length == 1);
 501       excess = GCOV_BLOCK_SIZE;
 502 #else
 503       if (gcov_var.length + words > gcov_var.alloc)
 504         gcov_allocate (gcov_var.length + words);
 505       excess = gcov_var.alloc - gcov_var.length;
 506 #endif
 507       excess = fread (gcov_var.buffer + gcov_var.length,
 508                       1, excess << 2, gcov_var.file) >> 2;
 509       gcov_var.length += excess;
 510       if (gcov_var.length < words)
 511         {
 512           gcov_var.overread += words - gcov_var.length;
 513           gcov_var.length = 0;
 514           return 0;
 515         }
 516     }
 517   result = &gcov_var.buffer[gcov_var.offset];
 518   gcov_var.offset += words;
 519   return result;
 520 }
 521
 522 /* Read unsigned value from a coverage file. Sets error flag on file
 523    error, overflow flag on overflow */
 524
 525 GCOV_LINKAGE gcov_unsigned_t
 526 gcov_read_unsigned (void)
 527 {
 528   gcov_unsigned_t value;
 529   const gcov_unsigned_t *buffer = gcov_read_words (1);
 530
 531   if (!buffer)
 532     return 0;
 533   value = from_file (buffer[0]);
 534   return value;
 535 }
 536
 537 /* Read counter value from a coverage file. Sets error flag on file
 538    error, overflow flag on overflow */
 539
 540 GCOV_LINKAGE gcov_type
 541 gcov_read_counter (void)
 542 {
 543   gcov_type value;
 544   const gcov_unsigned_t *buffer = gcov_read_words (2);
 545
 546   if (!buffer)
 547     return 0;
 548   value = from_file (buffer[0]);
 549   if (sizeof (value) > sizeof (gcov_unsigned_t))
 550     value |= ((gcov_type) from_file (buffer[1])) << 32;
 551   else if (buffer[1])
 552     gcov_var.error = -1;
 553
 554   return value;
 555 }
 556
 557 /* Read string from coverage file. Returns a pointer to a static
 558    buffer, or NULL on empty string. You must copy the string before
 559    calling another gcov function.  */
 560
 561 #if !IN_LIBGCOV
 562 GCOV_LINKAGE const char *
 563 gcov_read_string (void)
 564 {
 565   unsigned length = gcov_read_unsigned ();
 566
 567   if (!length)
 568     return 0;
 569
 570   return (const char *) gcov_read_words (length);
 571 }
 572 #endif
 573
 574 GCOV_LINKAGE void
 575 gcov_read_summary (struct gcov_summary *summary)
 576 {
 577   unsigned ix, h_ix, bv_ix, h_cnt = 0;
 578   struct gcov_ctr_summary *csum;
 579   unsigned histo_bitvector[GCOV_HISTOGRAM_BITVECTOR_SIZE];
 580   unsigned cur_bitvector;
 581
 582   summary->checksum = gcov_read_unsigned ();
 583   for (csum = summary->ctrs, ix = GCOV_COUNTERS_SUMMABLE; ix--; csum++)
 584     {
 585       csum->num = gcov_read_unsigned ();
 586       csum->runs = gcov_read_unsigned ();
 587       csum->sum_all = gcov_read_counter ();
 588       csum->run_max = gcov_read_counter ();
 589       csum->sum_max = gcov_read_counter ();
 590       memset (csum->histogram, 0,
 591               sizeof (gcov_bucket_type) * GCOV_HISTOGRAM_SIZE);
 592       for (bv_ix = 0; bv_ix < GCOV_HISTOGRAM_BITVECTOR_SIZE; bv_ix++)
 593         {
 594           histo_bitvector[bv_ix] = gcov_read_unsigned ();
 595 #if IN_LIBGCOV
 596           /* When building libgcov we don't include system.h, which includes
 597              hwint.h (where popcount_hwi is declared). However, libgcov.a
 598              is built by the bootstrapped compiler and therefore the builtins
 599              are always available.  */
 600           h_cnt += __builtin_popcount (histo_bitvector[bv_ix]);
 601 #else
 602           h_cnt += popcount_hwi (histo_bitvector[bv_ix]);
 603 #endif
 604         }
 605       bv_ix = 0;
 606       h_ix = 0;
 607       cur_bitvector = 0;
 608       while (h_cnt--)
 609         {
 610           /* Find the index corresponding to the next entry we will read in.
 611              First find the next non-zero bitvector and re-initialize
 612              the histogram index accordingly, then right shift and increment
 613              the index until we find a set bit.  */
 614           while (!cur_bitvector)
 615             {
 616               h_ix = bv_ix * 32;
 617               gcc_assert (bv_ix < GCOV_HISTOGRAM_BITVECTOR_SIZE);
 618               cur_bitvector = histo_bitvector[bv_ix++];
 619             }
 620           while (!(cur_bitvector & 0x1))
 621             {
 622               h_ix++;
 623               cur_bitvector >>= 1;
 624             }
 625           gcc_assert (h_ix < GCOV_HISTOGRAM_SIZE);
 626
 627           csum->histogram[h_ix].num_counters = gcov_read_unsigned ();
 628           csum->histogram[h_ix].min_value = gcov_read_counter ();
 629           csum->histogram[h_ix].cum_value = gcov_read_counter ();
 630           /* Shift off the index we are done with and increment to the
 631              corresponding next histogram entry.  */
 632           cur_bitvector >>= 1;
 633           h_ix++;
 634         }
 635     }
 636 }
 637
 638 #if !IN_LIBGCOV
 639 /* Reset to a known position.  BASE should have been obtained from
 640    gcov_position, LENGTH should be a record length.  */
 641
 642 GCOV_LINKAGE void
 643 gcov_sync (gcov_position_t base, gcov_unsigned_t length)
 644 {
 645   gcc_assert (gcov_var.mode > 0);
 646   base += length;
 647   if (base - gcov_var.start <= gcov_var.length)
 648     gcov_var.offset = base - gcov_var.start;
 649   else
 650     {
 651       gcov_var.offset = gcov_var.length = 0;
 652       fseek (gcov_var.file, base << 2, SEEK_SET);
 653       gcov_var.start = ftell (gcov_var.file) >> 2;
 654     }
 655 }
 656 #endif
 657
 658 #if IN_LIBGCOV
 659 /* Move to a given position in a gcov file.  */
 660
 661 GCOV_LINKAGE void
 662 gcov_seek (gcov_position_t base)
 663 {
 664   gcc_assert (gcov_var.mode < 0);
 665   if (gcov_var.offset)
 666     gcov_write_block (gcov_var.offset);
 667   fseek (gcov_var.file, base << 2, SEEK_SET);
 668   gcov_var.start = ftell (gcov_var.file) >> 2;
 669 }
 670 #endif
 671
 672 #if IN_GCOV > 0
 673 /* Return the modification time of the current gcov file.  */
 674
 675 GCOV_LINKAGE time_t
 676 gcov_time (void)
 677 {
 678   struct stat status;
 679
 680   if (fstat (fileno (gcov_var.file), &status))
 681     return 0;
 682   else
 683     return status.st_mtime;
 684 }
 685 #endif /* IN_GCOV */
 686
 687 #if !IN_GCOV
 688 /* Determine the index into histogram for VALUE. */
 689
 690 #if IN_LIBGCOV
 691 static unsigned
 692 #else
 693 GCOV_LINKAGE unsigned
 694 #endif
 695 gcov_histo_index (gcov_type value)
 696 {
 697   gcov_type_unsigned v = (gcov_type_unsigned)value;
 698   unsigned r = 0;
 699   unsigned prev2bits = 0;
 700
 701   /* Find index into log2 scale histogram, where each of the log2
 702      sized buckets is divided into 4 linear sub-buckets for better
 703      focus in the higher buckets.  */
 704
 705   /* Find the place of the most-significant bit set.  */
 706   if (v > 0)
 707     {
 708 #if IN_LIBGCOV
 709       /* When building libgcov we don't include system.h, which includes
 710          hwint.h (where floor_log2 is declared). However, libgcov.a
 711          is built by the bootstrapped compiler and therefore the builtins
 712          are always available.  */
 713       r = sizeof (long long) * __CHAR_BIT__ - 1 - __builtin_clzll (v);
 714 #else
 715       /* We use floor_log2 from hwint.c, which takes a HOST_WIDE_INT
 716          that is either 32 or 64 bits, and gcov_type_unsigned may be 64 bits.
 717          Need to check for the case where gcov_type_unsigned is 64 bits
 718          and HOST_WIDE_INT is 32 bits and handle it specially.  */
 719 #if HOST_BITS_PER_WIDEST_INT == HOST_BITS_PER_WIDE_INT
 720       r = floor_log2 (v);
 721 #elif HOST_BITS_PER_WIDEST_INT == 2 * HOST_BITS_PER_WIDE_INT
 722       HOST_WIDE_INT hwi_v = v >> HOST_BITS_PER_WIDE_INT;
 723       if (hwi_v)
 724         r = floor_log2 (hwi_v) + HOST_BITS_PER_WIDE_INT;
 725       else
 726         r = floor_log2 ((HOST_WIDE_INT)v);
 727 #else
 728       gcc_unreachable ();
 729 #endif
 730 #endif
 731     }
 732
 733   /* If at most the 2 least significant bits are set (value is
 734      0 - 3) then that value is our index into the lowest set of
 735      four buckets.  */
 736   if (r < 2)
 737     return (unsigned)value;
 738
 739   gcc_assert (r < 64);
 740
 741   /* Find the two next most significant bits to determine which
 742      of the four linear sub-buckets to select.  */
 743   prev2bits = (v >> (r - 2)) & 0x3;
 744   /* Finally, compose the final bucket index from the log2 index and
 745      the next 2 bits. The minimum r value at this point is 2 since we
 746      returned above if r was 2 or more, so the minimum bucket at this
 747      point is 4.  */
 748   return (r - 1) * 4 + prev2bits;
 749 }
 750
 751 /* Merge SRC_HISTO into TGT_HISTO. The counters are assumed to be in
 752    the same relative order in both histograms, and are matched up
 753    and merged in reverse order. Each counter is assigned an equal portion of
 754    its entry's original cumulative counter value when computing the
 755    new merged cum_value.  */
 756
 757 static void gcov_histogram_merge (gcov_bucket_type *tgt_histo,
 758                                   gcov_bucket_type *src_histo)
 759 {
 760   int src_i, tgt_i, tmp_i = 0;
 761   unsigned src_num, tgt_num, merge_num;
 762   gcov_type src_cum, tgt_cum, merge_src_cum, merge_tgt_cum, merge_cum;
 763   gcov_type merge_min;
 764   gcov_bucket_type tmp_histo[GCOV_HISTOGRAM_SIZE];
 765   int src_done = 0;
 766
 767   memset (tmp_histo, 0, sizeof (gcov_bucket_type) * GCOV_HISTOGRAM_SIZE);
 768
 769   /* Assume that the counters are in the same relative order in both
 770      histograms. Walk the histograms from largest to smallest entry,
 771      matching up and combining counters in order.  */
 772   src_num = 0;
 773   src_cum = 0;
 774   src_i = GCOV_HISTOGRAM_SIZE - 1;
 775   for (tgt_i = GCOV_HISTOGRAM_SIZE - 1; tgt_i >= 0 && !src_done; tgt_i--)
 776     {
 777       tgt_num = tgt_histo[tgt_i].num_counters;
 778       tgt_cum = tgt_histo[tgt_i].cum_value;
 779       /* Keep going until all of the target histogram's counters at this
 780          position have been matched and merged with counters from the
 781          source histogram.  */
 782       while (tgt_num > 0 && !src_done)
 783         {
 784           /* If this is either the first time through this loop or we just
 785              exhausted the previous non-zero source histogram entry, look
 786              for the next non-zero source histogram entry.  */
 787           if (!src_num)
 788             {
 789               /* Locate the next non-zero entry.  */
 790               while (src_i >= 0 && !src_histo[src_i].num_counters)
 791                 src_i--;
 792               /* If source histogram has fewer counters, then just copy over the
 793                  remaining target counters and quit.  */
 794               if (src_i < 0)
 795                 {
 796                   tmp_histo[tgt_i].num_counters += tgt_num;
 797                   tmp_histo[tgt_i].cum_value += tgt_cum;
 798                   if (!tmp_histo[tgt_i].min_value ||
 799                       tgt_histo[tgt_i].min_value < tmp_histo[tgt_i].min_value)
 800                     tmp_histo[tgt_i].min_value = tgt_histo[tgt_i].min_value;
 801                   while (--tgt_i >= 0)
 802                     {
 803                       tmp_histo[tgt_i].num_counters
 804                           += tgt_histo[tgt_i].num_counters;
 805                       tmp_histo[tgt_i].cum_value += tgt_histo[tgt_i].cum_value;
 806                       if (!tmp_histo[tgt_i].min_value ||
 807                           tgt_histo[tgt_i].min_value
 808                           < tmp_histo[tgt_i].min_value)
 809                         tmp_histo[tgt_i].min_value = tgt_histo[tgt_i].min_value;
 810                     }
 811
 812                   src_done = 1;
 813                   break;
 814                 }
 815
 816               src_num = src_histo[src_i].num_counters;
 817               src_cum = src_histo[src_i].cum_value;
 818             }
 819
 820           /* The number of counters to merge on this pass is the minimum
 821              of the remaining counters from the current target and source
 822              histogram entries.  */
 823           merge_num = tgt_num;
 824           if (src_num < merge_num)
 825             merge_num = src_num;
 826
 827           /* The merged min_value is the sum of the min_values from target
 828              and source.  */
 829           merge_min = tgt_histo[tgt_i].min_value + src_histo[src_i].min_value;
 830
 831           /* Compute the portion of source and target entries' cum_value
 832              that will be apportioned to the counters being merged.
 833              The total remaining cum_value from each entry is divided
 834              equally among the counters from that histogram entry if we
 835              are not merging all of them.  */
 836           merge_src_cum = src_cum;
 837           if (merge_num < src_num)
 838             merge_src_cum = merge_num * src_cum / src_num;
 839           merge_tgt_cum = tgt_cum;
 840           if (merge_num < tgt_num)
 841             merge_tgt_cum = merge_num * tgt_cum / tgt_num;
 842           /* The merged cum_value is the sum of the source and target
 843              components.  */
 844           merge_cum = merge_src_cum + merge_tgt_cum;
 845
 846           /* Update the remaining number of counters and cum_value left
 847              to be merged from this source and target entry.  */
 848           src_cum -= merge_src_cum;
 849           tgt_cum -= merge_tgt_cum;
 850           src_num -= merge_num;
 851           tgt_num -= merge_num;
 852
 853           /* The merged counters get placed in the new merged histogram
 854              at the entry for the merged min_value.  */
 855           tmp_i = gcov_histo_index (merge_min);
 856           gcc_assert (tmp_i < GCOV_HISTOGRAM_SIZE);
 857           tmp_histo[tmp_i].num_counters += merge_num;
 858           tmp_histo[tmp_i].cum_value += merge_cum;
 859           if (!tmp_histo[tmp_i].min_value ||
 860               merge_min < tmp_histo[tmp_i].min_value)
 861             tmp_histo[tmp_i].min_value = merge_min;
 862
 863           /* Ensure the search for the next non-zero src_histo entry starts
 864              at the next smallest histogram bucket.  */
 865           if (!src_num)
 866             src_i--;
 867         }
 868     }
 869
 870   gcc_assert (tgt_i < 0);
 871
 872   /* In the case where there were more counters in the source histogram,
 873      accumulate the remaining unmerged cumulative counter values. Add
 874      those to the smallest non-zero target histogram entry. Otherwise,
 875      the total cumulative counter values in the histogram will be smaller
 876      than the sum_all stored in the summary, which will complicate
 877      computing the working set information from the histogram later on.  */
 878   if (src_num)
 879     src_i--;
 880   while (src_i >= 0)
 881     {
 882       src_cum += src_histo[src_i].cum_value;
 883       src_i--;
 884     }
 885   /* At this point, tmp_i should be the smallest non-zero entry in the
 886      tmp_histo.  */
 887   gcc_assert (tmp_i >= 0 && tmp_i < GCOV_HISTOGRAM_SIZE
 888               && tmp_histo[tmp_i].num_counters > 0);
 889   tmp_histo[tmp_i].cum_value += src_cum;
 890
 891   /* Finally, copy the merged histogram into tgt_histo.  */
 892   memcpy (tgt_histo, tmp_histo,
 893           sizeof (gcov_bucket_type) * GCOV_HISTOGRAM_SIZE);
 894 }
 895 #endif /* !IN_GCOV */
 896
 897 /* This is used by gcov-dump (IN_GCOV == -1) and in the compiler
 898    (!IN_GCOV && !IN_LIBGCOV).  */
 899 #if IN_GCOV <= 0 && !IN_LIBGCOV
 900 /* Compute the working set information from the counter histogram in
 901    the profile summary. This is an array of information corresponding to a
 902    range of percentages of the total execution count (sum_all), and includes
 903    the number of counters required to cover that working set percentage and
 904    the minimum counter value in that working set.  */
 905
 906 GCOV_LINKAGE void
 907 compute_working_sets (const struct gcov_ctr_summary *summary,
 908                       gcov_working_set_t *gcov_working_sets)
 909 {
 910   gcov_type working_set_cum_values[NUM_GCOV_WORKING_SETS];
 911   gcov_type ws_cum_hotness_incr;
 912   gcov_type cum, tmp_cum;
 913   const gcov_bucket_type *histo_bucket;
 914   unsigned ws_ix, c_num, count;
 915   int h_ix;
 916
 917   /* Compute the amount of sum_all that the cumulative hotness grows
 918      by in each successive working set entry, which depends on the
 919      number of working set entries.  */
 920   ws_cum_hotness_incr = summary->sum_all / NUM_GCOV_WORKING_SETS;
 921
 922   /* Next fill in an array of the cumulative hotness values corresponding
 923      to each working set summary entry we are going to compute below.
 924      Skip 0% statistics, which can be extrapolated from the
 925      rest of the summary data.  */
 926   cum = ws_cum_hotness_incr;
 927   for (ws_ix = 0; ws_ix < NUM_GCOV_WORKING_SETS;
 928        ws_ix++, cum += ws_cum_hotness_incr)
 929     working_set_cum_values[ws_ix] = cum;
 930   /* The last summary entry is reserved for (roughly) 99.9% of the
 931      working set. Divide by 1024 so it becomes a shift, which gives
 932      almost exactly 99.9%.  */
 933   working_set_cum_values[NUM_GCOV_WORKING_SETS-1]
 934       = summary->sum_all - summary->sum_all/1024;
 935
 936   /* Next, walk through the histogram in decending order of hotness
 937      and compute the statistics for the working set summary array.
 938      As histogram entries are accumulated, we check to see which
 939      working set entries have had their expected cum_value reached
 940      and fill them in, walking the working set entries in increasing
 941      size of cum_value.  */
 942   ws_ix = 0; /* The current entry into the working set array.  */
 943   cum = 0; /* The current accumulated counter sum.  */
 944   count = 0; /* The current accumulated count of block counters.  */
 945   for (h_ix = GCOV_HISTOGRAM_SIZE - 1;
 946        h_ix >= 0 && ws_ix < NUM_GCOV_WORKING_SETS; h_ix--)
 947     {
 948       histo_bucket = &summary->histogram[h_ix];
 949
 950       /* If we haven't reached the required cumulative counter value for
 951          the current working set percentage, simply accumulate this histogram
 952          entry into the running sums and continue to the next histogram
 953          entry.  */
 954       if (cum + histo_bucket->cum_value < working_set_cum_values[ws_ix])
 955         {
 956           cum += histo_bucket->cum_value;
 957           count += histo_bucket->num_counters;
 958           continue;
 959         }
 960
 961       /* If adding the current histogram entry's cumulative counter value
 962          causes us to exceed the current working set size, then estimate
 963          how many of this histogram entry's counter values are required to
 964          reach the working set size, and fill in working set entries
 965          as we reach their expected cumulative value.  */
 966       for (c_num = 0, tmp_cum = cum;
 967            c_num < histo_bucket->num_counters && ws_ix < NUM_GCOV_WORKING_SETS;
 968            c_num++)
 969         {
 970           count++;
 971           /* If we haven't reached the last histogram entry counter, add
 972              in the minimum value again. This will underestimate the
 973              cumulative sum so far, because many of the counter values in this
 974              entry may have been larger than the minimum. We could add in the
 975              average value every time, but that would require an expensive
 976              divide operation.  */
 977           if (c_num + 1 < histo_bucket->num_counters)
 978             tmp_cum += histo_bucket->min_value;
 979           /* If we have reached the last histogram entry counter, then add
 980              in the entire cumulative value.  */
 981           else
 982             tmp_cum = cum + histo_bucket->cum_value;
 983
 984           /* Next walk through successive working set entries and fill in
 985              the statistics for any whose size we have reached by accumulating
 986              this histogram counter.  */
 987           while (ws_ix < NUM_GCOV_WORKING_SETS
 988                  && tmp_cum >= working_set_cum_values[ws_ix])
 989             {
 990               gcov_working_sets[ws_ix].num_counters = count;
 991               gcov_working_sets[ws_ix].min_counter
 992                   = histo_bucket->min_value;
 993               ws_ix++;
 994             }
 995         }
 996       /* Finally, update the running cumulative value since we were
 997          using a temporary above.  */
 998       cum += histo_bucket->cum_value;
 999     }
1000   gcc_assert (ws_ix == NUM_GCOV_WORKING_SETS);
1001 }
1002 #endif /* IN_GCOV <= 0 && !IN_LIBGCOV */