gcc/gcov-io.c

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