re PR c++/58516 (ICE with __transaction_atomic)
[official-gcc.git] / gcc / gcov-io.c
blob441aad92833dbc353ffab137d54e53f3ce263d80
1 /* File format for coverage information
2 Copyright (C) 1996-2013 Free Software Foundation, Inc.
3 Contributed by Bob Manson <manson@cygnus.com>.
4 Completely remangled by Nathan Sidwell <nathan@codesourcery.com>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 for more details.
18 Under Section 7 of GPL version 3, you are granted additional
19 permissions described in the GCC Runtime Library Exception, version
20 3.1, as published by the Free Software Foundation.
22 You should have received a copy of the GNU General Public License and
23 a copy of the GCC Runtime Library Exception along with this program;
24 see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
25 <http://www.gnu.org/licenses/>. */
27 /* Routines declared in gcov-io.h. This file should be #included by
28 another source file, after having #included gcov-io.h. */
30 #if !IN_GCOV
31 static void gcov_write_block (unsigned);
32 static gcov_unsigned_t *gcov_write_words (unsigned);
33 #endif
34 static const gcov_unsigned_t *gcov_read_words (unsigned);
35 #if !IN_LIBGCOV
36 static void gcov_allocate (unsigned);
37 #endif
39 static inline gcov_unsigned_t from_file (gcov_unsigned_t value)
41 #if !IN_LIBGCOV
42 if (gcov_var.endian)
44 value = (value >> 16) | (value << 16);
45 value = ((value & 0xff00ff) << 8) | ((value >> 8) & 0xff00ff);
47 #endif
48 return value;
51 /* Open a gcov file. NAME is the name of the file to open and MODE
52 indicates whether a new file should be created, or an existing file
53 opened. If MODE is >= 0 an existing file will be opened, if
54 possible, and if MODE is <= 0, a new file will be created. Use
55 MODE=0 to attempt to reopen an existing file and then fall back on
56 creating a new one. If MODE < 0, the file will be opened in
57 read-only mode. Otherwise it will be opened for modification.
58 Return zero on failure, >0 on opening an existing file and <0 on
59 creating a new one. */
61 GCOV_LINKAGE int
62 #if IN_LIBGCOV
63 gcov_open (const char *name)
64 #else
65 gcov_open (const char *name, int mode)
66 #endif
68 #if IN_LIBGCOV
69 const int mode = 0;
70 #endif
71 #if GCOV_LOCKED
72 struct flock s_flock;
73 int fd;
75 s_flock.l_whence = SEEK_SET;
76 s_flock.l_start = 0;
77 s_flock.l_len = 0; /* Until EOF. */
78 s_flock.l_pid = getpid ();
79 #endif
81 gcc_assert (!gcov_var.file);
82 gcov_var.start = 0;
83 gcov_var.offset = gcov_var.length = 0;
84 gcov_var.overread = -1u;
85 gcov_var.error = 0;
86 #if !IN_LIBGCOV
87 gcov_var.endian = 0;
88 #endif
89 #if GCOV_LOCKED
90 if (mode > 0)
92 /* Read-only mode - acquire a read-lock. */
93 s_flock.l_type = F_RDLCK;
94 /* pass mode (ignored) for compatibility */
95 fd = open (name, O_RDONLY, S_IRUSR | S_IWUSR);
97 else
99 /* Write mode - acquire a write-lock. */
100 s_flock.l_type = F_WRLCK;
101 fd = open (name, O_RDWR | O_CREAT, 0666);
103 if (fd < 0)
104 return 0;
106 while (fcntl (fd, F_SETLKW, &s_flock) && errno == EINTR)
107 continue;
109 gcov_var.file = fdopen (fd, (mode > 0) ? "rb" : "r+b");
111 if (!gcov_var.file)
113 close (fd);
114 return 0;
117 if (mode > 0)
118 gcov_var.mode = 1;
119 else if (mode == 0)
121 struct stat st;
123 if (fstat (fd, &st) < 0)
125 fclose (gcov_var.file);
126 gcov_var.file = 0;
127 return 0;
129 if (st.st_size != 0)
130 gcov_var.mode = 1;
131 else
132 gcov_var.mode = mode * 2 + 1;
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");
140 if (gcov_var.file)
141 gcov_var.mode = 1;
142 else if (mode <= 0)
144 gcov_var.file = fopen (name, "w+b");
145 if (gcov_var.file)
146 gcov_var.mode = mode * 2 + 1;
148 if (!gcov_var.file)
149 return 0;
150 #endif
152 setbuf (gcov_var.file, (char *)0);
154 return 1;
157 /* Close the current gcov file. Flushes data to disk. Returns nonzero
158 on failure or error flag set. */
160 GCOV_LINKAGE int
161 gcov_close (void)
163 if (gcov_var.file)
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;
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;
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. */
187 GCOV_LINKAGE int
188 gcov_magic (gcov_unsigned_t magic, gcov_unsigned_t expected)
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)
196 gcov_var.endian = 1;
197 return -1;
199 return 0;
201 #endif
203 #if !IN_LIBGCOV
204 static void
205 gcov_allocate (unsigned length)
207 size_t new_size = gcov_var.alloc;
209 if (!new_size)
210 new_size = GCOV_BLOCK_SIZE;
211 new_size += length;
212 new_size *= 2;
214 gcov_var.alloc = new_size;
215 gcov_var.buffer = XRESIZEVAR (gcov_unsigned_t, gcov_var.buffer, new_size << 2);
217 #endif
219 #if !IN_GCOV
220 /* Write out the current block, if needs be. */
222 static void
223 gcov_write_block (unsigned size)
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;
231 /* Allocate space to write BYTES bytes to the gcov file. Return a
232 pointer to those bytes, or NULL on failure. */
234 static gcov_unsigned_t *
235 gcov_write_words (unsigned words)
237 gcov_unsigned_t *result;
239 gcc_assert (gcov_var.mode < 0);
240 #if IN_LIBGCOV
241 if (gcov_var.offset >= GCOV_BLOCK_SIZE)
243 gcov_write_block (GCOV_BLOCK_SIZE);
244 if (gcov_var.offset)
246 gcc_assert (gcov_var.offset == 1);
247 memcpy (gcov_var.buffer, gcov_var.buffer + GCOV_BLOCK_SIZE, 4);
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;
257 return result;
260 /* Write unsigned VALUE to coverage file. Sets error flag
261 appropriately. */
263 GCOV_LINKAGE void
264 gcov_write_unsigned (gcov_unsigned_t value)
266 gcov_unsigned_t *buffer = gcov_write_words (1);
268 buffer[0] = value;
271 /* Write counter VALUE to coverage file. Sets error flag
272 appropriately. */
274 #if IN_LIBGCOV
275 GCOV_LINKAGE void
276 gcov_write_counter (gcov_type value)
278 gcov_unsigned_t *buffer = gcov_write_words (2);
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;
286 #endif /* IN_LIBGCOV */
288 #if !IN_LIBGCOV
289 /* Write STRING to coverage file. Sets error flag on file
290 error, overflow flag on overflow */
292 GCOV_LINKAGE void
293 gcov_write_string (const char *string)
295 unsigned length = 0;
296 unsigned alloc = 0;
297 gcov_unsigned_t *buffer;
299 if (string)
301 length = strlen (string);
302 alloc = (length + 4) >> 2;
305 buffer = gcov_write_words (1 + alloc);
307 buffer[0] = alloc;
308 buffer[alloc] = 0;
309 memcpy (&buffer[1], string, length);
311 #endif
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. */
317 GCOV_LINKAGE gcov_position_t
318 gcov_write_tag (gcov_unsigned_t tag)
320 gcov_position_t result = gcov_var.start + gcov_var.offset;
321 gcov_unsigned_t *buffer = gcov_write_words (2);
323 buffer[0] = tag;
324 buffer[1] = 0;
326 return result;
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. */
334 GCOV_LINKAGE void
335 gcov_write_length (gcov_position_t position)
337 unsigned offset;
338 gcov_unsigned_t length;
339 gcov_unsigned_t *buffer;
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);
352 #else /* IN_LIBGCOV */
354 /* Write a tag TAG and length LENGTH. */
356 GCOV_LINKAGE void
357 gcov_write_tag_length (gcov_unsigned_t tag, gcov_unsigned_t length)
359 gcov_unsigned_t *buffer = gcov_write_words (2);
361 buffer[0] = tag;
362 buffer[1] = length;
365 /* Write a summary structure to the gcov file. Return nonzero on
366 overflow. */
368 GCOV_LINKAGE void
369 gcov_write_summary (gcov_unsigned_t tag, const struct gcov_summary *summary)
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];
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++)
383 if (csum->histogram[h_ix].num_counters > 0)
385 histo_bitvector[h_ix / 32] |= 1 << (h_ix % 32);
386 h_cnt++;
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++)
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)
400 for (bv_ix = 0; bv_ix < GCOV_HISTOGRAM_BITVECTOR_SIZE; bv_ix++)
401 gcov_write_unsigned (0);
402 continue;
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++)
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);
416 #endif /* IN_LIBGCOV */
418 #endif /*!IN_GCOV */
420 /* Return a pointer to read BYTES bytes from the gcov file. Returns
421 NULL on failure (read past EOF). */
423 static const gcov_unsigned_t *
424 gcov_read_words (unsigned words)
426 const gcov_unsigned_t *result;
427 unsigned excess = gcov_var.length - gcov_var.offset;
429 gcc_assert (gcov_var.mode > 0);
430 if (excess < words)
432 gcov_var.start += gcov_var.offset;
433 #if IN_LIBGCOV
434 if (excess)
436 gcc_assert (excess == 1);
437 memcpy (gcov_var.buffer, gcov_var.buffer + gcov_var.offset, 4);
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)
457 gcov_var.overread += words - gcov_var.length;
458 gcov_var.length = 0;
459 return 0;
462 result = &gcov_var.buffer[gcov_var.offset];
463 gcov_var.offset += words;
464 return result;
467 /* Read unsigned value from a coverage file. Sets error flag on file
468 error, overflow flag on overflow */
470 GCOV_LINKAGE gcov_unsigned_t
471 gcov_read_unsigned (void)
473 gcov_unsigned_t value;
474 const gcov_unsigned_t *buffer = gcov_read_words (1);
476 if (!buffer)
477 return 0;
478 value = from_file (buffer[0]);
479 return value;
482 /* Read counter value from a coverage file. Sets error flag on file
483 error, overflow flag on overflow */
485 GCOV_LINKAGE gcov_type
486 gcov_read_counter (void)
488 gcov_type value;
489 const gcov_unsigned_t *buffer = gcov_read_words (2);
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;
499 return value;
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. */
506 #if !IN_LIBGCOV
507 GCOV_LINKAGE const char *
508 gcov_read_string (void)
510 unsigned length = gcov_read_unsigned ();
512 if (!length)
513 return 0;
515 return (const char *) gcov_read_words (length);
517 #endif
519 GCOV_LINKAGE void
520 gcov_read_summary (struct gcov_summary *summary)
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;
527 summary->checksum = gcov_read_unsigned ();
528 for (csum = summary->ctrs, ix = GCOV_COUNTERS_SUMMABLE; ix--; csum++)
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++)
539 histo_bitvector[bv_ix] = gcov_read_unsigned ();
540 #if IN_LIBGCOV
541 /* When building libgcov we don't include system.h, which includes
542 hwint.h (where popcount_hwi is declared). However, libgcov.a
543 is built by the bootstrapped compiler and therefore the builtins
544 are always available. */
545 h_cnt += __builtin_popcount (histo_bitvector[bv_ix]);
546 #else
547 h_cnt += popcount_hwi (histo_bitvector[bv_ix]);
548 #endif
550 bv_ix = 0;
551 h_ix = 0;
552 cur_bitvector = 0;
553 while (h_cnt--)
555 /* Find the index corresponding to the next entry we will read in.
556 First find the next non-zero bitvector and re-initialize
557 the histogram index accordingly, then right shift and increment
558 the index until we find a set bit. */
559 while (!cur_bitvector)
561 h_ix = bv_ix * 32;
562 gcc_assert(bv_ix < GCOV_HISTOGRAM_BITVECTOR_SIZE);
563 cur_bitvector = histo_bitvector[bv_ix++];
565 while (!(cur_bitvector & 0x1))
567 h_ix++;
568 cur_bitvector >>= 1;
570 gcc_assert(h_ix < GCOV_HISTOGRAM_SIZE);
572 csum->histogram[h_ix].num_counters = gcov_read_unsigned ();
573 csum->histogram[h_ix].min_value = gcov_read_counter ();
574 csum->histogram[h_ix].cum_value = gcov_read_counter ();
575 /* Shift off the index we are done with and increment to the
576 corresponding next histogram entry. */
577 cur_bitvector >>= 1;
578 h_ix++;
583 #if !IN_LIBGCOV
584 /* Reset to a known position. BASE should have been obtained from
585 gcov_position, LENGTH should be a record length. */
587 GCOV_LINKAGE void
588 gcov_sync (gcov_position_t base, gcov_unsigned_t length)
590 gcc_assert (gcov_var.mode > 0);
591 base += length;
592 if (base - gcov_var.start <= gcov_var.length)
593 gcov_var.offset = base - gcov_var.start;
594 else
596 gcov_var.offset = gcov_var.length = 0;
597 fseek (gcov_var.file, base << 2, SEEK_SET);
598 gcov_var.start = ftell (gcov_var.file) >> 2;
601 #endif
603 #if IN_LIBGCOV
604 /* Move to a given position in a gcov file. */
606 GCOV_LINKAGE void
607 gcov_seek (gcov_position_t base)
609 gcc_assert (gcov_var.mode < 0);
610 if (gcov_var.offset)
611 gcov_write_block (gcov_var.offset);
612 fseek (gcov_var.file, base << 2, SEEK_SET);
613 gcov_var.start = ftell (gcov_var.file) >> 2;
615 #endif
617 #if IN_GCOV > 0
618 /* Return the modification time of the current gcov file. */
620 GCOV_LINKAGE time_t
621 gcov_time (void)
623 struct stat status;
625 if (fstat (fileno (gcov_var.file), &status))
626 return 0;
627 else
628 return status.st_mtime;
630 #endif /* IN_GCOV */
632 #if !IN_GCOV
633 /* Determine the index into histogram for VALUE. */
635 #if IN_LIBGCOV
636 static unsigned
637 #else
638 GCOV_LINKAGE unsigned
639 #endif
640 gcov_histo_index (gcov_type value)
642 gcov_type_unsigned v = (gcov_type_unsigned)value;
643 unsigned r = 0;
644 unsigned prev2bits = 0;
646 /* Find index into log2 scale histogram, where each of the log2
647 sized buckets is divided into 4 linear sub-buckets for better
648 focus in the higher buckets. */
650 /* Find the place of the most-significant bit set. */
651 if (v > 0)
653 #if IN_LIBGCOV
654 /* When building libgcov we don't include system.h, which includes
655 hwint.h (where floor_log2 is declared). However, libgcov.a
656 is built by the bootstrapped compiler and therefore the builtins
657 are always available. */
658 r = sizeof (long long) * __CHAR_BIT__ - 1 - __builtin_clzll (v);
659 #else
660 /* We use floor_log2 from hwint.c, which takes a HOST_WIDE_INT
661 that is either 32 or 64 bits, and gcov_type_unsigned may be 64 bits.
662 Need to check for the case where gcov_type_unsigned is 64 bits
663 and HOST_WIDE_INT is 32 bits and handle it specially. */
664 #if HOST_BITS_PER_WIDEST_INT == HOST_BITS_PER_WIDE_INT
665 r = floor_log2 (v);
666 #elif HOST_BITS_PER_WIDEST_INT == 2 * HOST_BITS_PER_WIDE_INT
667 HOST_WIDE_INT hwi_v = v >> HOST_BITS_PER_WIDE_INT;
668 if (hwi_v)
669 r = floor_log2 (hwi_v) + HOST_BITS_PER_WIDE_INT;
670 else
671 r = floor_log2 ((HOST_WIDE_INT)v);
672 #else
673 gcc_unreachable ();
674 #endif
675 #endif
678 /* If at most the 2 least significant bits are set (value is
679 0 - 3) then that value is our index into the lowest set of
680 four buckets. */
681 if (r < 2)
682 return (unsigned)value;
684 gcc_assert (r < 64);
686 /* Find the two next most significant bits to determine which
687 of the four linear sub-buckets to select. */
688 prev2bits = (v >> (r - 2)) & 0x3;
689 /* Finally, compose the final bucket index from the log2 index and
690 the next 2 bits. The minimum r value at this point is 2 since we
691 returned above if r was 2 or more, so the minimum bucket at this
692 point is 4. */
693 return (r - 1) * 4 + prev2bits;
696 /* Merge SRC_HISTO into TGT_HISTO. The counters are assumed to be in
697 the same relative order in both histograms, and are matched up
698 and merged in reverse order. Each counter is assigned an equal portion of
699 its entry's original cumulative counter value when computing the
700 new merged cum_value. */
702 static void gcov_histogram_merge (gcov_bucket_type *tgt_histo,
703 gcov_bucket_type *src_histo)
705 int src_i, tgt_i, tmp_i = 0;
706 unsigned src_num, tgt_num, merge_num;
707 gcov_type src_cum, tgt_cum, merge_src_cum, merge_tgt_cum, merge_cum;
708 gcov_type merge_min;
709 gcov_bucket_type tmp_histo[GCOV_HISTOGRAM_SIZE];
710 int src_done = 0;
712 memset(tmp_histo, 0, sizeof (gcov_bucket_type) * GCOV_HISTOGRAM_SIZE);
714 /* Assume that the counters are in the same relative order in both
715 histograms. Walk the histograms from largest to smallest entry,
716 matching up and combining counters in order. */
717 src_num = 0;
718 src_cum = 0;
719 src_i = GCOV_HISTOGRAM_SIZE - 1;
720 for (tgt_i = GCOV_HISTOGRAM_SIZE - 1; tgt_i >= 0 && !src_done; tgt_i--)
722 tgt_num = tgt_histo[tgt_i].num_counters;
723 tgt_cum = tgt_histo[tgt_i].cum_value;
724 /* Keep going until all of the target histogram's counters at this
725 position have been matched and merged with counters from the
726 source histogram. */
727 while (tgt_num > 0 && !src_done)
729 /* If this is either the first time through this loop or we just
730 exhausted the previous non-zero source histogram entry, look
731 for the next non-zero source histogram entry. */
732 if (!src_num)
734 /* Locate the next non-zero entry. */
735 while (src_i >= 0 && !src_histo[src_i].num_counters)
736 src_i--;
737 /* If source histogram has fewer counters, then just copy over the
738 remaining target counters and quit. */
739 if (src_i < 0)
741 tmp_histo[tgt_i].num_counters += tgt_num;
742 tmp_histo[tgt_i].cum_value += tgt_cum;
743 if (!tmp_histo[tgt_i].min_value ||
744 tgt_histo[tgt_i].min_value < tmp_histo[tgt_i].min_value)
745 tmp_histo[tgt_i].min_value = tgt_histo[tgt_i].min_value;
746 while (--tgt_i >= 0)
748 tmp_histo[tgt_i].num_counters
749 += tgt_histo[tgt_i].num_counters;
750 tmp_histo[tgt_i].cum_value += tgt_histo[tgt_i].cum_value;
751 if (!tmp_histo[tgt_i].min_value ||
752 tgt_histo[tgt_i].min_value
753 < tmp_histo[tgt_i].min_value)
754 tmp_histo[tgt_i].min_value = tgt_histo[tgt_i].min_value;
757 src_done = 1;
758 break;
761 src_num = src_histo[src_i].num_counters;
762 src_cum = src_histo[src_i].cum_value;
765 /* The number of counters to merge on this pass is the minimum
766 of the remaining counters from the current target and source
767 histogram entries. */
768 merge_num = tgt_num;
769 if (src_num < merge_num)
770 merge_num = src_num;
772 /* The merged min_value is the sum of the min_values from target
773 and source. */
774 merge_min = tgt_histo[tgt_i].min_value + src_histo[src_i].min_value;
776 /* Compute the portion of source and target entries' cum_value
777 that will be apportioned to the counters being merged.
778 The total remaining cum_value from each entry is divided
779 equally among the counters from that histogram entry if we
780 are not merging all of them. */
781 merge_src_cum = src_cum;
782 if (merge_num < src_num)
783 merge_src_cum = merge_num * src_cum / src_num;
784 merge_tgt_cum = tgt_cum;
785 if (merge_num < tgt_num)
786 merge_tgt_cum = merge_num * tgt_cum / tgt_num;
787 /* The merged cum_value is the sum of the source and target
788 components. */
789 merge_cum = merge_src_cum + merge_tgt_cum;
791 /* Update the remaining number of counters and cum_value left
792 to be merged from this source and target entry. */
793 src_cum -= merge_src_cum;
794 tgt_cum -= merge_tgt_cum;
795 src_num -= merge_num;
796 tgt_num -= merge_num;
798 /* The merged counters get placed in the new merged histogram
799 at the entry for the merged min_value. */
800 tmp_i = gcov_histo_index(merge_min);
801 gcc_assert (tmp_i < GCOV_HISTOGRAM_SIZE);
802 tmp_histo[tmp_i].num_counters += merge_num;
803 tmp_histo[tmp_i].cum_value += merge_cum;
804 if (!tmp_histo[tmp_i].min_value ||
805 merge_min < tmp_histo[tmp_i].min_value)
806 tmp_histo[tmp_i].min_value = merge_min;
808 /* Ensure the search for the next non-zero src_histo entry starts
809 at the next smallest histogram bucket. */
810 if (!src_num)
811 src_i--;
815 gcc_assert (tgt_i < 0);
817 /* In the case where there were more counters in the source histogram,
818 accumulate the remaining unmerged cumulative counter values. Add
819 those to the smallest non-zero target histogram entry. Otherwise,
820 the total cumulative counter values in the histogram will be smaller
821 than the sum_all stored in the summary, which will complicate
822 computing the working set information from the histogram later on. */
823 if (src_num)
824 src_i--;
825 while (src_i >= 0)
827 src_cum += src_histo[src_i].cum_value;
828 src_i--;
830 /* At this point, tmp_i should be the smallest non-zero entry in the
831 tmp_histo. */
832 gcc_assert(tmp_i >= 0 && tmp_i < GCOV_HISTOGRAM_SIZE
833 && tmp_histo[tmp_i].num_counters > 0);
834 tmp_histo[tmp_i].cum_value += src_cum;
836 /* Finally, copy the merged histogram into tgt_histo. */
837 memcpy(tgt_histo, tmp_histo, sizeof (gcov_bucket_type) * GCOV_HISTOGRAM_SIZE);
839 #endif /* !IN_GCOV */
841 /* This is used by gcov-dump (IN_GCOV == -1) and in the compiler
842 (!IN_GCOV && !IN_LIBGCOV). */
843 #if IN_GCOV <= 0 && !IN_LIBGCOV
844 /* Compute the working set information from the counter histogram in
845 the profile summary. This is an array of information corresponding to a
846 range of percentages of the total execution count (sum_all), and includes
847 the number of counters required to cover that working set percentage and
848 the minimum counter value in that working set. */
850 GCOV_LINKAGE void
851 compute_working_sets (const struct gcov_ctr_summary *summary,
852 gcov_working_set_t *gcov_working_sets)
854 gcov_type working_set_cum_values[NUM_GCOV_WORKING_SETS];
855 gcov_type ws_cum_hotness_incr;
856 gcov_type cum, tmp_cum;
857 const gcov_bucket_type *histo_bucket;
858 unsigned ws_ix, c_num, count;
859 int h_ix;
861 /* Compute the amount of sum_all that the cumulative hotness grows
862 by in each successive working set entry, which depends on the
863 number of working set entries. */
864 ws_cum_hotness_incr = summary->sum_all / NUM_GCOV_WORKING_SETS;
866 /* Next fill in an array of the cumulative hotness values corresponding
867 to each working set summary entry we are going to compute below.
868 Skip 0% statistics, which can be extrapolated from the
869 rest of the summary data. */
870 cum = ws_cum_hotness_incr;
871 for (ws_ix = 0; ws_ix < NUM_GCOV_WORKING_SETS;
872 ws_ix++, cum += ws_cum_hotness_incr)
873 working_set_cum_values[ws_ix] = cum;
874 /* The last summary entry is reserved for (roughly) 99.9% of the
875 working set. Divide by 1024 so it becomes a shift, which gives
876 almost exactly 99.9%. */
877 working_set_cum_values[NUM_GCOV_WORKING_SETS-1]
878 = summary->sum_all - summary->sum_all/1024;
880 /* Next, walk through the histogram in decending order of hotness
881 and compute the statistics for the working set summary array.
882 As histogram entries are accumulated, we check to see which
883 working set entries have had their expected cum_value reached
884 and fill them in, walking the working set entries in increasing
885 size of cum_value. */
886 ws_ix = 0; /* The current entry into the working set array. */
887 cum = 0; /* The current accumulated counter sum. */
888 count = 0; /* The current accumulated count of block counters. */
889 for (h_ix = GCOV_HISTOGRAM_SIZE - 1;
890 h_ix >= 0 && ws_ix < NUM_GCOV_WORKING_SETS; h_ix--)
892 histo_bucket = &summary->histogram[h_ix];
894 /* If we haven't reached the required cumulative counter value for
895 the current working set percentage, simply accumulate this histogram
896 entry into the running sums and continue to the next histogram
897 entry. */
898 if (cum + histo_bucket->cum_value < working_set_cum_values[ws_ix])
900 cum += histo_bucket->cum_value;
901 count += histo_bucket->num_counters;
902 continue;
905 /* If adding the current histogram entry's cumulative counter value
906 causes us to exceed the current working set size, then estimate
907 how many of this histogram entry's counter values are required to
908 reach the working set size, and fill in working set entries
909 as we reach their expected cumulative value. */
910 for (c_num = 0, tmp_cum = cum;
911 c_num < histo_bucket->num_counters && ws_ix < NUM_GCOV_WORKING_SETS;
912 c_num++)
914 count++;
915 /* If we haven't reached the last histogram entry counter, add
916 in the minimum value again. This will underestimate the
917 cumulative sum so far, because many of the counter values in this
918 entry may have been larger than the minimum. We could add in the
919 average value every time, but that would require an expensive
920 divide operation. */
921 if (c_num + 1 < histo_bucket->num_counters)
922 tmp_cum += histo_bucket->min_value;
923 /* If we have reached the last histogram entry counter, then add
924 in the entire cumulative value. */
925 else
926 tmp_cum = cum + histo_bucket->cum_value;
928 /* Next walk through successive working set entries and fill in
929 the statistics for any whose size we have reached by accumulating
930 this histogram counter. */
931 while (ws_ix < NUM_GCOV_WORKING_SETS
932 && tmp_cum >= working_set_cum_values[ws_ix])
934 gcov_working_sets[ws_ix].num_counters = count;
935 gcov_working_sets[ws_ix].min_counter
936 = histo_bucket->min_value;
937 ws_ix++;
940 /* Finally, update the running cumulative value since we were
941 using a temporary above. */
942 cum += histo_bucket->cum_value;
944 gcc_assert (ws_ix == NUM_GCOV_WORKING_SETS);
946 #endif /* IN_GCOV <= 0 && !IN_LIBGCOV */