gcc/gcov-io.c

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