contrib/gcc-5.0/gcc/gcov-io.c

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