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