diff options
Diffstat (limited to 'gcc-4.9/gcc/gcov-io.c')
-rw-r--r-- | gcc-4.9/gcc/gcov-io.c | 1008 |
1 files changed, 1008 insertions, 0 deletions
diff --git a/gcc-4.9/gcc/gcov-io.c b/gcc-4.9/gcc/gcov-io.c new file mode 100644 index 000000000..5ef82f683 --- /dev/null +++ b/gcc-4.9/gcc/gcov-io.c @@ -0,0 +1,1008 @@ +/* File format for coverage information + Copyright (C) 1996-2014 Free Software Foundation, Inc. + Contributed by Bob Manson <manson@cygnus.com>. + Completely remangled by Nathan Sidwell <nathan@codesourcery.com>. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +Under Section 7 of GPL version 3, you are granted additional +permissions described in the GCC Runtime Library Exception, version +3.1, as published by the Free Software Foundation. + +You should have received a copy of the GNU General Public License and +a copy of the GCC Runtime Library Exception along with this program; +see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +<http://www.gnu.org/licenses/>. */ + +/* Routines declared in gcov-io.h. This file should be #included by + another source file, after having #included gcov-io.h. */ + +#if !IN_GCOV +static void gcov_write_block (unsigned); +static gcov_unsigned_t *gcov_write_words (unsigned); +#endif +static const gcov_unsigned_t *gcov_read_words (unsigned); +#if !IN_LIBGCOV +static void gcov_allocate (unsigned); +#endif + +/* Optimum number of gcov_unsigned_t's read from or written to disk. */ +#define GCOV_BLOCK_SIZE (1 << 10) + +GCOV_LINKAGE struct gcov_var +{ + FILE *file; + gcov_position_t start; /* Position of first byte of block */ + unsigned offset; /* Read/write position within the block. */ + unsigned length; /* Read limit in the block. */ + unsigned overread; /* Number of words overread. */ + int error; /* < 0 overflow, > 0 disk error. */ + int mode; /* < 0 writing, > 0 reading */ +#if IN_LIBGCOV + /* Holds one block plus 4 bytes, thus all coverage reads & writes + fit within this buffer and we always can transfer GCOV_BLOCK_SIZE + to and from the disk. libgcov never backtracks and only writes 4 + or 8 byte objects. */ + gcov_unsigned_t buffer[GCOV_BLOCK_SIZE + 1]; +#else + int endian; /* Swap endianness. */ + /* Holds a variable length block, as the compiler can write + strings and needs to backtrack. */ + size_t alloc; + gcov_unsigned_t *buffer; +#endif +} gcov_var; + +/* Save the current position in the gcov file. */ +static inline gcov_position_t +gcov_position (void) +{ + gcc_assert (gcov_var.mode > 0); + return gcov_var.start + gcov_var.offset; +} + +/* Return nonzero if the error flag is set. */ +static inline int +gcov_is_error (void) +{ + return gcov_var.file ? gcov_var.error : 1; +} + +#if IN_LIBGCOV +/* Move to beginning of file and initialize for writing. */ +GCOV_LINKAGE inline void +gcov_rewrite (void) +{ + gcc_assert (gcov_var.mode > 0); + gcov_var.mode = -1; + gcov_var.start = 0; + gcov_var.offset = 0; + fseek (gcov_var.file, 0L, SEEK_SET); +} +#endif + +static inline gcov_unsigned_t from_file (gcov_unsigned_t value) +{ +#if !IN_LIBGCOV + if (gcov_var.endian) + { + value = (value >> 16) | (value << 16); + value = ((value & 0xff00ff) << 8) | ((value >> 8) & 0xff00ff); + } +#endif + return value; +} + +/* Open a gcov file. NAME is the name of the file to open and MODE + indicates whether a new file should be created, or an existing file + opened. If MODE is >= 0 an existing file will be opened, if + possible, and if MODE is <= 0, a new file will be created. Use + MODE=0 to attempt to reopen an existing file and then fall back on + creating a new one. If MODE < 0, the file will be opened in + read-only mode. Otherwise it will be opened for modification. + Return zero on failure, >0 on opening an existing file and <0 on + creating a new one. */ + +GCOV_LINKAGE int +#if IN_LIBGCOV +gcov_open (const char *name) +#else +gcov_open (const char *name, int mode) +#endif +{ +#if IN_LIBGCOV + const int mode = 0; +#endif +#if GCOV_LOCKED + struct flock s_flock; + int fd; + + s_flock.l_whence = SEEK_SET; + s_flock.l_start = 0; + s_flock.l_len = 0; /* Until EOF. */ + s_flock.l_pid = getpid (); +#endif + + gcc_assert (!gcov_var.file); + gcov_var.start = 0; + gcov_var.offset = gcov_var.length = 0; + gcov_var.overread = -1u; + gcov_var.error = 0; +#if !IN_LIBGCOV + gcov_var.endian = 0; +#endif +#if GCOV_LOCKED + if (mode > 0) + { + /* Read-only mode - acquire a read-lock. */ + s_flock.l_type = F_RDLCK; + /* pass mode (ignored) for compatibility */ + fd = open (name, O_RDONLY, S_IRUSR | S_IWUSR); + } + else if (mode < 0) + { + /* Write mode - acquire a write-lock. */ + s_flock.l_type = F_WRLCK; + fd = open (name, O_RDWR | O_CREAT | O_TRUNC, 0666); + } + else /* mode == 0 */ + { + /* Read-Write mode - acquire a write-lock. */ + s_flock.l_type = F_WRLCK; + fd = open (name, O_RDWR | O_CREAT, 0666); + } + if (fd < 0) + return 0; + + while (fcntl (fd, F_SETLKW, &s_flock) && errno == EINTR) + continue; + + gcov_var.file = fdopen (fd, (mode > 0) ? "rb" : "r+b"); + + if (!gcov_var.file) + { + close (fd); + return 0; + } + + if (mode > 0) + gcov_var.mode = 1; + else if (mode == 0) + { + struct stat st; + + if (fstat (fd, &st) < 0) + { + fclose (gcov_var.file); + gcov_var.file = 0; + return 0; + } + if (st.st_size != 0) + gcov_var.mode = 1; + else + gcov_var.mode = mode * 2 + 1; + } + else + gcov_var.mode = mode * 2 + 1; +#else + if (mode >= 0) + gcov_var.file = fopen (name, (mode > 0) ? "rb" : "r+b"); + + if (gcov_var.file) + gcov_var.mode = 1; + else if (mode <= 0) + { + gcov_var.file = fopen (name, "w+b"); + if (gcov_var.file) + gcov_var.mode = mode * 2 + 1; + } + if (!gcov_var.file) + return 0; +#endif + + setbuf (gcov_var.file, (char *)0); + + return 1; +} + +/* Close the current gcov file. Flushes data to disk. Returns nonzero + on failure or error flag set. */ + +GCOV_LINKAGE int +gcov_close (void) +{ + if (gcov_var.file) + { +#if !IN_GCOV + if (gcov_var.offset && gcov_var.mode < 0) + gcov_write_block (gcov_var.offset); +#endif + fclose (gcov_var.file); + gcov_var.file = 0; + gcov_var.length = 0; + } +#if !IN_LIBGCOV + free (gcov_var.buffer); + gcov_var.alloc = 0; + gcov_var.buffer = 0; +#endif + gcov_var.mode = 0; + return gcov_var.error; +} + +#if !IN_LIBGCOV +/* Check if MAGIC is EXPECTED. Use it to determine endianness of the + file. Returns +1 for same endian, -1 for other endian and zero for + not EXPECTED. */ + +GCOV_LINKAGE int +gcov_magic (gcov_unsigned_t magic, gcov_unsigned_t expected) +{ + if (magic == expected) + return 1; + magic = (magic >> 16) | (magic << 16); + magic = ((magic & 0xff00ff) << 8) | ((magic >> 8) & 0xff00ff); + if (magic == expected) + { + gcov_var.endian = 1; + return -1; + } + return 0; +} +#endif + +#if !IN_LIBGCOV +static void +gcov_allocate (unsigned length) +{ + size_t new_size = gcov_var.alloc; + + if (!new_size) + new_size = GCOV_BLOCK_SIZE; + new_size += length; + new_size *= 2; + + gcov_var.alloc = new_size; + gcov_var.buffer = XRESIZEVAR (gcov_unsigned_t, gcov_var.buffer, new_size << 2); +} +#endif + +#if !IN_GCOV +/* Write out the current block, if needs be. */ + +static void +gcov_write_block (unsigned size) +{ + if (fwrite (gcov_var.buffer, size << 2, 1, gcov_var.file) != 1) + gcov_var.error = 1; + gcov_var.start += size; + gcov_var.offset -= size; +} + +/* Allocate space to write BYTES bytes to the gcov file. Return a + pointer to those bytes, or NULL on failure. */ + +static gcov_unsigned_t * +gcov_write_words (unsigned words) +{ + gcov_unsigned_t *result; + + gcc_assert (gcov_var.mode < 0); +#if IN_LIBGCOV + if (gcov_var.offset >= GCOV_BLOCK_SIZE) + { + gcov_write_block (GCOV_BLOCK_SIZE); + if (gcov_var.offset) + { + gcc_assert (gcov_var.offset == 1); + memcpy (gcov_var.buffer, gcov_var.buffer + GCOV_BLOCK_SIZE, 4); + } + } +#else + if (gcov_var.offset + words > gcov_var.alloc) + gcov_allocate (gcov_var.offset + words); +#endif + result = &gcov_var.buffer[gcov_var.offset]; + gcov_var.offset += words; + + return result; +} + +/* Write unsigned VALUE to coverage file. Sets error flag + appropriately. */ + +GCOV_LINKAGE void +gcov_write_unsigned (gcov_unsigned_t value) +{ + gcov_unsigned_t *buffer = gcov_write_words (1); + + buffer[0] = value; +} + +/* Write counter VALUE to coverage file. Sets error flag + appropriately. */ + +#if IN_LIBGCOV +GCOV_LINKAGE void +gcov_write_counter (gcov_type value) +{ + gcov_unsigned_t *buffer = gcov_write_words (2); + + buffer[0] = (gcov_unsigned_t) value; + if (sizeof (value) > sizeof (gcov_unsigned_t)) + buffer[1] = (gcov_unsigned_t) (value >> 32); + else + buffer[1] = 0; +} +#endif /* IN_LIBGCOV */ + +#if !IN_LIBGCOV +/* Write STRING to coverage file. Sets error flag on file + error, overflow flag on overflow */ + +GCOV_LINKAGE void +gcov_write_string (const char *string) +{ + unsigned length = 0; + unsigned alloc = 0; + gcov_unsigned_t *buffer; + + if (string) + { + length = strlen (string); + alloc = (length + 4) >> 2; + } + + buffer = gcov_write_words (1 + alloc); + + buffer[0] = alloc; + buffer[alloc] = 0; + memcpy (&buffer[1], string, length); +} +#endif + +#if !IN_LIBGCOV +/* Write a tag TAG and reserve space for the record length. Return a + value to be used for gcov_write_length. */ + +GCOV_LINKAGE gcov_position_t +gcov_write_tag (gcov_unsigned_t tag) +{ + gcov_position_t result = gcov_var.start + gcov_var.offset; + gcov_unsigned_t *buffer = gcov_write_words (2); + + buffer[0] = tag; + buffer[1] = 0; + + return result; +} + +/* Write a record length using POSITION, which was returned by + gcov_write_tag. The current file position is the end of the + record, and is restored before returning. Returns nonzero on + overflow. */ + +GCOV_LINKAGE void +gcov_write_length (gcov_position_t position) +{ + unsigned offset; + gcov_unsigned_t length; + gcov_unsigned_t *buffer; + + gcc_assert (gcov_var.mode < 0); + gcc_assert (position + 2 <= gcov_var.start + gcov_var.offset); + gcc_assert (position >= gcov_var.start); + offset = position - gcov_var.start; + length = gcov_var.offset - offset - 2; + buffer = (gcov_unsigned_t *) &gcov_var.buffer[offset]; + buffer[1] = length; + if (gcov_var.offset >= GCOV_BLOCK_SIZE) + gcov_write_block (gcov_var.offset); +} + +#else /* IN_LIBGCOV */ + +/* Write a tag TAG and length LENGTH. */ + +GCOV_LINKAGE void +gcov_write_tag_length (gcov_unsigned_t tag, gcov_unsigned_t length) +{ + gcov_unsigned_t *buffer = gcov_write_words (2); + + buffer[0] = tag; + buffer[1] = length; +} + +/* Write a summary structure to the gcov file. Return nonzero on + overflow. */ + +GCOV_LINKAGE void +gcov_write_summary (gcov_unsigned_t tag, const struct gcov_summary *summary) +{ + unsigned ix, h_ix, bv_ix, h_cnt = 0; + const struct gcov_ctr_summary *csum; + unsigned histo_bitvector[GCOV_HISTOGRAM_BITVECTOR_SIZE]; + + /* Count number of non-zero histogram entries, and fill in a bit vector + of non-zero indices. The histogram is only currently computed for arc + counters. */ + for (bv_ix = 0; bv_ix < GCOV_HISTOGRAM_BITVECTOR_SIZE; bv_ix++) + histo_bitvector[bv_ix] = 0; + csum = &summary->ctrs[GCOV_COUNTER_ARCS]; + for (h_ix = 0; h_ix < GCOV_HISTOGRAM_SIZE; h_ix++) + { + if (csum->histogram[h_ix].num_counters > 0) + { + histo_bitvector[h_ix / 32] |= 1 << (h_ix % 32); + h_cnt++; + } + } + gcov_write_tag_length (tag, GCOV_TAG_SUMMARY_LENGTH (h_cnt)); + gcov_write_unsigned (summary->checksum); + for (csum = summary->ctrs, ix = GCOV_COUNTERS_SUMMABLE; ix--; csum++) + { + gcov_write_unsigned (csum->num); + gcov_write_unsigned (csum->runs); + gcov_write_counter (csum->sum_all); + gcov_write_counter (csum->run_max); + gcov_write_counter (csum->sum_max); + if (ix != GCOV_COUNTER_ARCS) + { + for (bv_ix = 0; bv_ix < GCOV_HISTOGRAM_BITVECTOR_SIZE; bv_ix++) + gcov_write_unsigned (0); + continue; + } + for (bv_ix = 0; bv_ix < GCOV_HISTOGRAM_BITVECTOR_SIZE; bv_ix++) + gcov_write_unsigned (histo_bitvector[bv_ix]); + for (h_ix = 0; h_ix < GCOV_HISTOGRAM_SIZE; h_ix++) + { + if (!csum->histogram[h_ix].num_counters) + continue; + gcov_write_unsigned (csum->histogram[h_ix].num_counters); + gcov_write_counter (csum->histogram[h_ix].min_value); + gcov_write_counter (csum->histogram[h_ix].cum_value); + } + } +} +#endif /* IN_LIBGCOV */ + +#endif /*!IN_GCOV */ + +/* Return a pointer to read BYTES bytes from the gcov file. Returns + NULL on failure (read past EOF). */ + +static const gcov_unsigned_t * +gcov_read_words (unsigned words) +{ + const gcov_unsigned_t *result; + unsigned excess = gcov_var.length - gcov_var.offset; + + gcc_assert (gcov_var.mode > 0); + if (excess < words) + { + gcov_var.start += gcov_var.offset; +#if IN_LIBGCOV + if (excess) + { + gcc_assert (excess == 1); + memcpy (gcov_var.buffer, gcov_var.buffer + gcov_var.offset, 4); + } +#else + memmove (gcov_var.buffer, gcov_var.buffer + gcov_var.offset, excess * 4); +#endif + gcov_var.offset = 0; + gcov_var.length = excess; +#if IN_LIBGCOV + gcc_assert (!gcov_var.length || gcov_var.length == 1); + excess = GCOV_BLOCK_SIZE; +#else + if (gcov_var.length + words > gcov_var.alloc) + gcov_allocate (gcov_var.length + words); + excess = gcov_var.alloc - gcov_var.length; +#endif + excess = fread (gcov_var.buffer + gcov_var.length, + 1, excess << 2, gcov_var.file) >> 2; + gcov_var.length += excess; + if (gcov_var.length < words) + { + gcov_var.overread += words - gcov_var.length; + gcov_var.length = 0; + return 0; + } + } + result = &gcov_var.buffer[gcov_var.offset]; + gcov_var.offset += words; + return result; +} + +/* Read unsigned value from a coverage file. Sets error flag on file + error, overflow flag on overflow */ + +GCOV_LINKAGE gcov_unsigned_t +gcov_read_unsigned (void) +{ + gcov_unsigned_t value; + const gcov_unsigned_t *buffer = gcov_read_words (1); + + if (!buffer) + return 0; + value = from_file (buffer[0]); + return value; +} + +/* Read counter value from a coverage file. Sets error flag on file + error, overflow flag on overflow */ + +GCOV_LINKAGE gcov_type +gcov_read_counter (void) +{ + gcov_type value; + const gcov_unsigned_t *buffer = gcov_read_words (2); + + if (!buffer) + return 0; + value = from_file (buffer[0]); + if (sizeof (value) > sizeof (gcov_unsigned_t)) + value |= ((gcov_type) from_file (buffer[1])) << 32; + else if (buffer[1]) + gcov_var.error = -1; + + return value; +} + +/* Read string from coverage file. Returns a pointer to a static + buffer, or NULL on empty string. You must copy the string before + calling another gcov function. */ + +#if !IN_LIBGCOV +GCOV_LINKAGE const char * +gcov_read_string (void) +{ + unsigned length = gcov_read_unsigned (); + + if (!length) + return 0; + + return (const char *) gcov_read_words (length); +} +#endif + +GCOV_LINKAGE void +gcov_read_summary (struct gcov_summary *summary) +{ + unsigned ix, h_ix, bv_ix, h_cnt = 0; + struct gcov_ctr_summary *csum; + unsigned histo_bitvector[GCOV_HISTOGRAM_BITVECTOR_SIZE]; + unsigned cur_bitvector; + + summary->checksum = gcov_read_unsigned (); + for (csum = summary->ctrs, ix = GCOV_COUNTERS_SUMMABLE; ix--; csum++) + { + csum->num = gcov_read_unsigned (); + csum->runs = gcov_read_unsigned (); + csum->sum_all = gcov_read_counter (); + csum->run_max = gcov_read_counter (); + csum->sum_max = gcov_read_counter (); + memset (csum->histogram, 0, + sizeof (gcov_bucket_type) * GCOV_HISTOGRAM_SIZE); + for (bv_ix = 0; bv_ix < GCOV_HISTOGRAM_BITVECTOR_SIZE; bv_ix++) + { + histo_bitvector[bv_ix] = gcov_read_unsigned (); +#if IN_LIBGCOV + /* When building libgcov we don't include system.h, which includes + hwint.h (where popcount_hwi is declared). However, libgcov.a + is built by the bootstrapped compiler and therefore the builtins + are always available. */ + h_cnt += __builtin_popcount (histo_bitvector[bv_ix]); +#else + h_cnt += popcount_hwi (histo_bitvector[bv_ix]); +#endif + } + bv_ix = 0; + h_ix = 0; + cur_bitvector = 0; + while (h_cnt--) + { + /* Find the index corresponding to the next entry we will read in. + First find the next non-zero bitvector and re-initialize + the histogram index accordingly, then right shift and increment + the index until we find a set bit. */ + while (!cur_bitvector) + { + h_ix = bv_ix * 32; + gcc_assert (bv_ix < GCOV_HISTOGRAM_BITVECTOR_SIZE); + cur_bitvector = histo_bitvector[bv_ix++]; + } + while (!(cur_bitvector & 0x1)) + { + h_ix++; + cur_bitvector >>= 1; + } + gcc_assert (h_ix < GCOV_HISTOGRAM_SIZE); + + csum->histogram[h_ix].num_counters = gcov_read_unsigned (); + csum->histogram[h_ix].min_value = gcov_read_counter (); + csum->histogram[h_ix].cum_value = gcov_read_counter (); + /* Shift off the index we are done with and increment to the + corresponding next histogram entry. */ + cur_bitvector >>= 1; + h_ix++; + } + } +} + +#if !IN_LIBGCOV +/* Reset to a known position. BASE should have been obtained from + gcov_position, LENGTH should be a record length. */ + +GCOV_LINKAGE void +gcov_sync (gcov_position_t base, gcov_unsigned_t length) +{ + gcc_assert (gcov_var.mode > 0); + base += length; + if (base - gcov_var.start <= gcov_var.length) + gcov_var.offset = base - gcov_var.start; + else + { + gcov_var.offset = gcov_var.length = 0; + fseek (gcov_var.file, base << 2, SEEK_SET); + gcov_var.start = ftell (gcov_var.file) >> 2; + } +} +#endif + +#if IN_LIBGCOV +/* Move to a given position in a gcov file. */ + +GCOV_LINKAGE void +gcov_seek (gcov_position_t base) +{ + gcc_assert (gcov_var.mode < 0); + if (gcov_var.offset) + gcov_write_block (gcov_var.offset); + fseek (gcov_var.file, base << 2, SEEK_SET); + gcov_var.start = ftell (gcov_var.file) >> 2; +} +#endif + +#if IN_GCOV > 0 +/* Return the modification time of the current gcov file. */ + +GCOV_LINKAGE time_t +gcov_time (void) +{ + struct stat status; + + if (fstat (fileno (gcov_var.file), &status)) + return 0; + else + return status.st_mtime; +} +#endif /* IN_GCOV */ + +#if !IN_GCOV +/* Determine the index into histogram for VALUE. */ + +#if IN_LIBGCOV +static unsigned +#else +GCOV_LINKAGE unsigned +#endif +gcov_histo_index (gcov_type value) +{ + gcov_type_unsigned v = (gcov_type_unsigned)value; + unsigned r = 0; + unsigned prev2bits = 0; + + /* Find index into log2 scale histogram, where each of the log2 + sized buckets is divided into 4 linear sub-buckets for better + focus in the higher buckets. */ + + /* Find the place of the most-significant bit set. */ + if (v > 0) + { +#if IN_LIBGCOV + /* When building libgcov we don't include system.h, which includes + hwint.h (where floor_log2 is declared). However, libgcov.a + is built by the bootstrapped compiler and therefore the builtins + are always available. */ + r = sizeof (long long) * __CHAR_BIT__ - 1 - __builtin_clzll (v); +#else + /* We use floor_log2 from hwint.c, which takes a HOST_WIDE_INT + that is either 32 or 64 bits, and gcov_type_unsigned may be 64 bits. + Need to check for the case where gcov_type_unsigned is 64 bits + and HOST_WIDE_INT is 32 bits and handle it specially. */ +#if HOST_BITS_PER_WIDEST_INT == HOST_BITS_PER_WIDE_INT + r = floor_log2 (v); +#elif HOST_BITS_PER_WIDEST_INT == 2 * HOST_BITS_PER_WIDE_INT + HOST_WIDE_INT hwi_v = v >> HOST_BITS_PER_WIDE_INT; + if (hwi_v) + r = floor_log2 (hwi_v) + HOST_BITS_PER_WIDE_INT; + else + r = floor_log2 ((HOST_WIDE_INT)v); +#else + gcc_unreachable (); +#endif +#endif + } + + /* If at most the 2 least significant bits are set (value is + 0 - 3) then that value is our index into the lowest set of + four buckets. */ + if (r < 2) + return (unsigned)value; + + gcc_assert (r < 64); + + /* Find the two next most significant bits to determine which + of the four linear sub-buckets to select. */ + prev2bits = (v >> (r - 2)) & 0x3; + /* Finally, compose the final bucket index from the log2 index and + the next 2 bits. The minimum r value at this point is 2 since we + returned above if r was 2 or more, so the minimum bucket at this + point is 4. */ + return (r - 1) * 4 + prev2bits; +} + +/* Merge SRC_HISTO into TGT_HISTO. The counters are assumed to be in + the same relative order in both histograms, and are matched up + and merged in reverse order. Each counter is assigned an equal portion of + its entry's original cumulative counter value when computing the + new merged cum_value. */ + +static void gcov_histogram_merge (gcov_bucket_type *tgt_histo, + gcov_bucket_type *src_histo) +{ + int src_i, tgt_i, tmp_i = 0; + unsigned src_num, tgt_num, merge_num; + gcov_type src_cum, tgt_cum, merge_src_cum, merge_tgt_cum, merge_cum; + gcov_type merge_min; + gcov_bucket_type tmp_histo[GCOV_HISTOGRAM_SIZE]; + int src_done = 0; + + memset (tmp_histo, 0, sizeof (gcov_bucket_type) * GCOV_HISTOGRAM_SIZE); + + /* Assume that the counters are in the same relative order in both + histograms. Walk the histograms from largest to smallest entry, + matching up and combining counters in order. */ + src_num = 0; + src_cum = 0; + src_i = GCOV_HISTOGRAM_SIZE - 1; + for (tgt_i = GCOV_HISTOGRAM_SIZE - 1; tgt_i >= 0 && !src_done; tgt_i--) + { + tgt_num = tgt_histo[tgt_i].num_counters; + tgt_cum = tgt_histo[tgt_i].cum_value; + /* Keep going until all of the target histogram's counters at this + position have been matched and merged with counters from the + source histogram. */ + while (tgt_num > 0 && !src_done) + { + /* If this is either the first time through this loop or we just + exhausted the previous non-zero source histogram entry, look + for the next non-zero source histogram entry. */ + if (!src_num) + { + /* Locate the next non-zero entry. */ + while (src_i >= 0 && !src_histo[src_i].num_counters) + src_i--; + /* If source histogram has fewer counters, then just copy over the + remaining target counters and quit. */ + if (src_i < 0) + { + tmp_histo[tgt_i].num_counters += tgt_num; + tmp_histo[tgt_i].cum_value += tgt_cum; + if (!tmp_histo[tgt_i].min_value || + tgt_histo[tgt_i].min_value < tmp_histo[tgt_i].min_value) + tmp_histo[tgt_i].min_value = tgt_histo[tgt_i].min_value; + while (--tgt_i >= 0) + { + tmp_histo[tgt_i].num_counters + += tgt_histo[tgt_i].num_counters; + tmp_histo[tgt_i].cum_value += tgt_histo[tgt_i].cum_value; + if (!tmp_histo[tgt_i].min_value || + tgt_histo[tgt_i].min_value + < tmp_histo[tgt_i].min_value) + tmp_histo[tgt_i].min_value = tgt_histo[tgt_i].min_value; + } + + src_done = 1; + break; + } + + src_num = src_histo[src_i].num_counters; + src_cum = src_histo[src_i].cum_value; + } + + /* The number of counters to merge on this pass is the minimum + of the remaining counters from the current target and source + histogram entries. */ + merge_num = tgt_num; + if (src_num < merge_num) + merge_num = src_num; + + /* The merged min_value is the sum of the min_values from target + and source. */ + merge_min = tgt_histo[tgt_i].min_value + src_histo[src_i].min_value; + + /* Compute the portion of source and target entries' cum_value + that will be apportioned to the counters being merged. + The total remaining cum_value from each entry is divided + equally among the counters from that histogram entry if we + are not merging all of them. */ + merge_src_cum = src_cum; + if (merge_num < src_num) + merge_src_cum = merge_num * src_cum / src_num; + merge_tgt_cum = tgt_cum; + if (merge_num < tgt_num) + merge_tgt_cum = merge_num * tgt_cum / tgt_num; + /* The merged cum_value is the sum of the source and target + components. */ + merge_cum = merge_src_cum + merge_tgt_cum; + + /* Update the remaining number of counters and cum_value left + to be merged from this source and target entry. */ + src_cum -= merge_src_cum; + tgt_cum -= merge_tgt_cum; + src_num -= merge_num; + tgt_num -= merge_num; + + /* The merged counters get placed in the new merged histogram + at the entry for the merged min_value. */ + tmp_i = gcov_histo_index (merge_min); + gcc_assert (tmp_i < GCOV_HISTOGRAM_SIZE); + tmp_histo[tmp_i].num_counters += merge_num; + tmp_histo[tmp_i].cum_value += merge_cum; + if (!tmp_histo[tmp_i].min_value || + merge_min < tmp_histo[tmp_i].min_value) + tmp_histo[tmp_i].min_value = merge_min; + + /* Ensure the search for the next non-zero src_histo entry starts + at the next smallest histogram bucket. */ + if (!src_num) + src_i--; + } + } + + gcc_assert (tgt_i < 0); + + /* In the case where there were more counters in the source histogram, + accumulate the remaining unmerged cumulative counter values. Add + those to the smallest non-zero target histogram entry. Otherwise, + the total cumulative counter values in the histogram will be smaller + than the sum_all stored in the summary, which will complicate + computing the working set information from the histogram later on. */ + if (src_num) + src_i--; + while (src_i >= 0) + { + src_cum += src_histo[src_i].cum_value; + src_i--; + } + /* At this point, tmp_i should be the smallest non-zero entry in the + tmp_histo. */ + gcc_assert (tmp_i >= 0 && tmp_i < GCOV_HISTOGRAM_SIZE + && tmp_histo[tmp_i].num_counters > 0); + tmp_histo[tmp_i].cum_value += src_cum; + + /* Finally, copy the merged histogram into tgt_histo. */ + memcpy (tgt_histo, tmp_histo, + sizeof (gcov_bucket_type) * GCOV_HISTOGRAM_SIZE); +} +#endif /* !IN_GCOV */ + +/* This is used by gcov-dump (IN_GCOV == -1) and in the compiler + (!IN_GCOV && !IN_LIBGCOV). */ +#if IN_GCOV <= 0 && !IN_LIBGCOV +/* Compute the working set information from the counter histogram in + the profile summary. This is an array of information corresponding to a + range of percentages of the total execution count (sum_all), and includes + the number of counters required to cover that working set percentage and + the minimum counter value in that working set. */ + +GCOV_LINKAGE void +compute_working_sets (const struct gcov_ctr_summary *summary, + gcov_working_set_t *gcov_working_sets) +{ + gcov_type working_set_cum_values[NUM_GCOV_WORKING_SETS]; + gcov_type ws_cum_hotness_incr; + gcov_type cum, tmp_cum; + const gcov_bucket_type *histo_bucket; + unsigned ws_ix, c_num, count; + int h_ix; + + /* Compute the amount of sum_all that the cumulative hotness grows + by in each successive working set entry, which depends on the + number of working set entries. */ + ws_cum_hotness_incr = summary->sum_all / NUM_GCOV_WORKING_SETS; + + /* Next fill in an array of the cumulative hotness values corresponding + to each working set summary entry we are going to compute below. + Skip 0% statistics, which can be extrapolated from the + rest of the summary data. */ + cum = ws_cum_hotness_incr; + for (ws_ix = 0; ws_ix < NUM_GCOV_WORKING_SETS; + ws_ix++, cum += ws_cum_hotness_incr) + working_set_cum_values[ws_ix] = cum; + /* The last summary entry is reserved for (roughly) 99.9% of the + working set. Divide by 1024 so it becomes a shift, which gives + almost exactly 99.9%. */ + working_set_cum_values[NUM_GCOV_WORKING_SETS-1] + = summary->sum_all - summary->sum_all/1024; + + /* Next, walk through the histogram in decending order of hotness + and compute the statistics for the working set summary array. + As histogram entries are accumulated, we check to see which + working set entries have had their expected cum_value reached + and fill them in, walking the working set entries in increasing + size of cum_value. */ + ws_ix = 0; /* The current entry into the working set array. */ + cum = 0; /* The current accumulated counter sum. */ + count = 0; /* The current accumulated count of block counters. */ + for (h_ix = GCOV_HISTOGRAM_SIZE - 1; + h_ix >= 0 && ws_ix < NUM_GCOV_WORKING_SETS; h_ix--) + { + histo_bucket = &summary->histogram[h_ix]; + + /* If we haven't reached the required cumulative counter value for + the current working set percentage, simply accumulate this histogram + entry into the running sums and continue to the next histogram + entry. */ + if (cum + histo_bucket->cum_value < working_set_cum_values[ws_ix]) + { + cum += histo_bucket->cum_value; + count += histo_bucket->num_counters; + continue; + } + + /* If adding the current histogram entry's cumulative counter value + causes us to exceed the current working set size, then estimate + how many of this histogram entry's counter values are required to + reach the working set size, and fill in working set entries + as we reach their expected cumulative value. */ + for (c_num = 0, tmp_cum = cum; + c_num < histo_bucket->num_counters && ws_ix < NUM_GCOV_WORKING_SETS; + c_num++) + { + count++; + /* If we haven't reached the last histogram entry counter, add + in the minimum value again. This will underestimate the + cumulative sum so far, because many of the counter values in this + entry may have been larger than the minimum. We could add in the + average value every time, but that would require an expensive + divide operation. */ + if (c_num + 1 < histo_bucket->num_counters) + tmp_cum += histo_bucket->min_value; + /* If we have reached the last histogram entry counter, then add + in the entire cumulative value. */ + else + tmp_cum = cum + histo_bucket->cum_value; + + /* Next walk through successive working set entries and fill in + the statistics for any whose size we have reached by accumulating + this histogram counter. */ + while (ws_ix < NUM_GCOV_WORKING_SETS + && tmp_cum >= working_set_cum_values[ws_ix]) + { + gcov_working_sets[ws_ix].num_counters = count; + gcov_working_sets[ws_ix].min_counter + = histo_bucket->min_value; + ws_ix++; + } + } + /* Finally, update the running cumulative value since we were + using a temporary above. */ + cum += histo_bucket->cum_value; + } + gcc_assert (ws_ix == NUM_GCOV_WORKING_SETS); +} +#endif /* IN_GCOV <= 0 && !IN_LIBGCOV */ |