gcc/gcov-io.c

   1 /* File format for coverage information
   2    Copyright (C) 1996, 1997, 1998, 2000, 2002, 2003, 2004, 2005, 2007,
   3    2008  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           h_cnt += __builtin_popcountll (histo_bitvector[bv_ix]);
 542         }
 543       bv_ix = 0;
 544       h_ix = 0;
 545       cur_bitvector = 0;
 546       while (h_cnt--)
 547         {
 548           /* Find the index corresponding to the next entry we will read in.
 549              First find the next non-zero bitvector and re-initialize
 550              the histogram index accordingly, then right shift and increment
 551              the index until we find a set bit.  */
 552           while (!cur_bitvector)
 553             {
 554               h_ix = bv_ix * 32;
 555               gcc_assert(bv_ix < GCOV_HISTOGRAM_BITVECTOR_SIZE);
 556               cur_bitvector = histo_bitvector[bv_ix++];
 557             }
 558           while (!(cur_bitvector & 0x1))
 559             {
 560               h_ix++;
 561               cur_bitvector >>= 1;
 562             }
 563           gcc_assert(h_ix < GCOV_HISTOGRAM_SIZE);
 564
 565           csum->histogram[h_ix].num_counters = gcov_read_unsigned ();
 566           csum->histogram[h_ix].min_value = gcov_read_counter ();
 567           csum->histogram[h_ix].cum_value = gcov_read_counter ();
 568           /* Shift off the index we are done with and increment to the
 569              corresponding next histogram entry.  */
 570           cur_bitvector >>= 1;
 571           h_ix++;
 572         }
 573     }
 574 }
 575
 576 #if !IN_LIBGCOV
 577 /* Reset to a known position.  BASE should have been obtained from
 578    gcov_position, LENGTH should be a record length.  */
 579
 580 GCOV_LINKAGE void
 581 gcov_sync (gcov_position_t base, gcov_unsigned_t length)
 582 {
 583   gcc_assert (gcov_var.mode > 0);
 584   base += length;
 585   if (base - gcov_var.start <= gcov_var.length)
 586     gcov_var.offset = base - gcov_var.start;
 587   else
 588     {
 589       gcov_var.offset = gcov_var.length = 0;
 590       fseek (gcov_var.file, base << 2, SEEK_SET);
 591       gcov_var.start = ftell (gcov_var.file) >> 2;
 592     }
 593 }
 594 #endif
 595
 596 #if IN_LIBGCOV
 597 /* Move to a given position in a gcov file.  */
 598
 599 GCOV_LINKAGE void
 600 gcov_seek (gcov_position_t base)
 601 {
 602   gcc_assert (gcov_var.mode < 0);
 603   if (gcov_var.offset)
 604     gcov_write_block (gcov_var.offset);
 605   fseek (gcov_var.file, base << 2, SEEK_SET);
 606   gcov_var.start = ftell (gcov_var.file) >> 2;
 607 }
 608 #endif
 609
 610 #if IN_GCOV > 0
 611 /* Return the modification time of the current gcov file.  */
 612
 613 GCOV_LINKAGE time_t
 614 gcov_time (void)
 615 {
 616   struct stat status;
 617
 618   if (fstat (fileno (gcov_var.file), &status))
 619     return 0;
 620   else
 621     return status.st_mtime;
 622 }
 623 #endif /* IN_GCOV */
 624
 625 #if IN_LIBGCOV || !IN_GCOV
 626 /* Determine the index into histogram for VALUE. */
 627
 628 static unsigned
 629 gcov_histo_index(gcov_type value)
 630 {
 631   gcov_type_unsigned v = (gcov_type_unsigned)value;
 632   unsigned r = 0;
 633   unsigned prev2bits = 0;
 634
 635   /* Find index into log2 scale histogram, where each of the log2
 636      sized buckets is divided into 4 linear sub-buckets for better
 637      focus in the higher buckets.  */
 638
 639   /* Find the place of the most-significant bit set.  */
 640   if (v > 0)
 641     r = 63 - __builtin_clzll (v);
 642
 643   /* If at most the 2 least significant bits are set (value is
 644      0 - 3) then that value is our index into the lowest set of
 645      four buckets.  */
 646   if (r < 2)
 647     return (unsigned)value;
 648
 649   gcc_assert (r < 64);
 650
 651   /* Find the two next most significant bits to determine which
 652      of the four linear sub-buckets to select.  */
 653   prev2bits = (v >> (r - 2)) & 0x3;
 654   /* Finally, compose the final bucket index from the log2 index and
 655      the next 2 bits. The minimum r value at this point is 2 since we
 656      returned above if r was 2 or more, so the minimum bucket at this
 657      point is 4.  */
 658   return (r - 1) * 4 + prev2bits;
 659 }
 660
 661 /* Merge SRC_HISTO into TGT_HISTO. The counters are assumed to be in
 662    the same relative order in both histograms, and are matched up
 663    and merged in reverse order. Each counter is assigned an equal portion of
 664    its entry's original cumulative counter value when computing the
 665    new merged cum_value.  */
 666
 667 static void gcov_histogram_merge(gcov_bucket_type *tgt_histo,
 668                                  gcov_bucket_type *src_histo)
 669 {
 670   int src_i, tgt_i, tmp_i = 0;
 671   unsigned src_num, tgt_num, merge_num;
 672   gcov_type src_cum, tgt_cum, merge_src_cum, merge_tgt_cum, merge_cum;
 673   gcov_type merge_min;
 674   gcov_bucket_type tmp_histo[GCOV_HISTOGRAM_SIZE];
 675   int src_done = 0;
 676
 677   memset(tmp_histo, 0, sizeof (gcov_bucket_type) * GCOV_HISTOGRAM_SIZE);
 678
 679   /* Assume that the counters are in the same relative order in both
 680      histograms. Walk the histograms from largest to smallest entry,
 681      matching up and combining counters in order.  */
 682   src_num = 0;
 683   src_cum = 0;
 684   src_i = GCOV_HISTOGRAM_SIZE - 1;
 685   for (tgt_i = GCOV_HISTOGRAM_SIZE - 1; tgt_i >= 0 && !src_done; tgt_i--)
 686     {
 687       tgt_num = tgt_histo[tgt_i].num_counters;
 688       tgt_cum = tgt_histo[tgt_i].cum_value;
 689       /* Keep going until all of the target histogram's counters at this
 690          position have been matched and merged with counters from the
 691          source histogram.  */
 692       while (tgt_num > 0 && !src_done)
 693         {
 694           /* If this is either the first time through this loop or we just
 695              exhausted the previous non-zero source histogram entry, look
 696              for the next non-zero source histogram entry.  */
 697           if (!src_num)
 698             {
 699               /* Locate the next non-zero entry.  */
 700               while (src_i >= 0 && !src_histo[src_i].num_counters)
 701                 src_i--;
 702               /* If source histogram has fewer counters, then just copy over the
 703                  remaining target counters and quit.  */
 704               if (src_i < 0)
 705                 {
 706                   tmp_histo[tgt_i].num_counters += tgt_num;
 707                   tmp_histo[tgt_i].cum_value += tgt_cum;
 708                   if (!tmp_histo[tgt_i].min_value ||
 709                       tgt_histo[tgt_i].min_value < tmp_histo[tgt_i].min_value)
 710                     tmp_histo[tgt_i].min_value = tgt_histo[tgt_i].min_value;
 711                   while (--tgt_i >= 0)
 712                     {
 713                       tmp_histo[tgt_i].num_counters
 714                           += tgt_histo[tgt_i].num_counters;
 715                       tmp_histo[tgt_i].cum_value += tgt_histo[tgt_i].cum_value;
 716                       if (!tmp_histo[tgt_i].min_value ||
 717                           tgt_histo[tgt_i].min_value
 718                           < tmp_histo[tgt_i].min_value)
 719                         tmp_histo[tgt_i].min_value = tgt_histo[tgt_i].min_value;
 720                     }
 721
 722                   src_done = 1;
 723                   break;
 724                 }
 725
 726               src_num = src_histo[src_i].num_counters;
 727               src_cum = src_histo[src_i].cum_value;
 728             }
 729
 730           /* The number of counters to merge on this pass is the minimum
 731              of the remaining counters from the current target and source
 732              histogram entries.  */
 733           merge_num = tgt_num;
 734           if (src_num < merge_num)
 735             merge_num = src_num;
 736
 737           /* The merged min_value is the sum of the min_values from target
 738              and source.  */
 739           merge_min = tgt_histo[tgt_i].min_value + src_histo[src_i].min_value;
 740
 741           /* Compute the portion of source and target entries' cum_value
 742              that will be apportioned to the counters being merged.
 743              The total remaining cum_value from each entry is divided
 744              equally among the counters from that histogram entry if we
 745              are not merging all of them.  */
 746           merge_src_cum = src_cum;
 747           if (merge_num < src_num)
 748             merge_src_cum = merge_num * src_cum / src_num;
 749           merge_tgt_cum = tgt_cum;
 750           if (merge_num < tgt_num)
 751             merge_tgt_cum = merge_num * tgt_cum / tgt_num;
 752           /* The merged cum_value is the sum of the source and target
 753              components.  */
 754           merge_cum = merge_src_cum + merge_tgt_cum;
 755
 756           /* Update the remaining number of counters and cum_value left
 757              to be merged from this source and target entry.  */
 758           src_cum -= merge_src_cum;
 759           tgt_cum -= merge_tgt_cum;
 760           src_num -= merge_num;
 761           tgt_num -= merge_num;
 762
 763           /* The merged counters get placed in the new merged histogram
 764              at the entry for the merged min_value.  */
 765           tmp_i = gcov_histo_index(merge_min);
 766           gcc_assert (tmp_i < GCOV_HISTOGRAM_SIZE);
 767           tmp_histo[tmp_i].num_counters += merge_num;
 768           tmp_histo[tmp_i].cum_value += merge_cum;
 769           if (!tmp_histo[tmp_i].min_value ||
 770               merge_min < tmp_histo[tmp_i].min_value)
 771             tmp_histo[tmp_i].min_value = merge_min;
 772
 773           /* Ensure the search for the next non-zero src_histo entry starts
 774              at the next smallest histogram bucket.  */
 775           if (!src_num)
 776             src_i--;
 777         }
 778     }
 779
 780   gcc_assert (tgt_i < 0);
 781
 782   /* In the case where there were more counters in the source histogram,
 783      accumulate the remaining unmerged cumulative counter values. Add
 784      those to the smallest non-zero target histogram entry. Otherwise,
 785      the total cumulative counter values in the histogram will be smaller
 786      than the sum_all stored in the summary, which will complicate
 787      computing the working set information from the histogram later on.  */
 788   if (src_num)
 789     src_i--;
 790   while (src_i >= 0)
 791     {
 792       src_cum += src_histo[src_i].cum_value;
 793       src_i--;
 794     }
 795   /* At this point, tmp_i should be the smallest non-zero entry in the
 796      tmp_histo.  */
 797   gcc_assert(tmp_i >= 0 && tmp_i < GCOV_HISTOGRAM_SIZE
 798              && tmp_histo[tmp_i].num_counters > 0);
 799   tmp_histo[tmp_i].cum_value += src_cum;
 800
 801   /* Finally, copy the merged histogram into tgt_histo.  */
 802   memcpy(tgt_histo, tmp_histo, sizeof (gcov_bucket_type) * GCOV_HISTOGRAM_SIZE);
 803 }
 804 #endif /* IN_LIBGCOV || !IN_GCOV */