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