Line data Source code
1 : /* Calculate branch probabilities, and basic block execution counts.
2 : Copyright (C) 1990-2026 Free Software Foundation, Inc.
3 : Contributed by James E. Wilson, UC Berkeley/Cygnus Support;
4 : based on some ideas from Dain Samples of UC Berkeley.
5 : Further mangling by Bob Manson, Cygnus Support.
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 : You should have received a copy of the GNU General Public License
20 : along with GCC; see the file COPYING3. If not see
21 : <http://www.gnu.org/licenses/>. */
22 :
23 : /* Generate basic block profile instrumentation and auxiliary files.
24 : Profile generation is optimized, so that not all arcs in the basic
25 : block graph need instrumenting. First, the BB graph is closed with
26 : one entry (function start), and one exit (function exit). Any
27 : ABNORMAL_EDGE cannot be instrumented (because there is no control
28 : path to place the code). We close the graph by inserting fake
29 : EDGE_FAKE edges to the EXIT_BLOCK, from the sources of abnormal
30 : edges that do not go to the exit_block. We ignore such abnormal
31 : edges. Naturally these fake edges are never directly traversed,
32 : and so *cannot* be directly instrumented. Some other graph
33 : massaging is done. To optimize the instrumentation we generate the
34 : BB minimal span tree, only edges that are not on the span tree
35 : (plus the entry point) need instrumenting. From that information
36 : all other edge counts can be deduced. By construction all fake
37 : edges must be on the spanning tree. We also attempt to place
38 : EDGE_CRITICAL edges on the spanning tree.
39 :
40 : The auxiliary files generated are <dumpbase>.gcno (at compile time)
41 : and <dumpbase>.gcda (at run time). The format is
42 : described in full in gcov-io.h. */
43 :
44 : /* ??? Register allocation should use basic block execution counts to
45 : give preference to the most commonly executed blocks. */
46 :
47 : /* ??? Should calculate branch probabilities before instrumenting code, since
48 : then we can use arc counts to help decide which arcs to instrument. */
49 :
50 : #include "config.h"
51 : #include "system.h"
52 : #include "coretypes.h"
53 : #include "backend.h"
54 : #include "rtl.h"
55 : #include "tree.h"
56 : #include "gimple.h"
57 : #include "cfghooks.h"
58 : #include "cgraph.h"
59 : #include "coverage.h"
60 : #include "diagnostic-core.h"
61 : #include "cfganal.h"
62 : #include "value-prof.h"
63 : #include "gimple-iterator.h"
64 : #include "tree-cfg.h"
65 : #include "dumpfile.h"
66 : #include "cfgloop.h"
67 : #include "sreal.h"
68 : #include "file-prefix-map.h"
69 : #include "stringpool.h"
70 : #include "attribs.h"
71 :
72 : #include "profile.h"
73 : #include "auto-profile.h"
74 :
75 : struct condcov;
76 : struct condcov *find_conditions (struct function*);
77 : size_t cov_length (const struct condcov*);
78 : array_slice<basic_block> cov_blocks (struct condcov*, size_t);
79 : array_slice<uint64_t> cov_masks (struct condcov*, size_t);
80 : array_slice<sbitmap> cov_maps (struct condcov* cov, size_t n);
81 : void cov_free (struct condcov*);
82 : size_t instrument_decisions (array_slice<basic_block>, size_t,
83 : array_slice<sbitmap>,
84 : array_slice<gcov_type_unsigned>);
85 :
86 : /* Map from BBs/edges to gcov counters. */
87 : vec<gcov_type> bb_gcov_counts;
88 : hash_map<edge,gcov_type> *edge_gcov_counts;
89 :
90 : struct bb_profile_info {
91 : unsigned int count_valid : 1;
92 :
93 : /* Number of successor and predecessor edges. */
94 : gcov_type succ_count;
95 : gcov_type pred_count;
96 : };
97 :
98 : #define BB_INFO(b) ((struct bb_profile_info *) (b)->aux)
99 :
100 :
101 : /* Counter summary from the last set of coverage counts read. */
102 :
103 : gcov_summary *profile_info, *gcov_profile_info;
104 :
105 : /* Collect statistics on the performance of this pass for the entire source
106 : file. */
107 :
108 : static int total_num_blocks;
109 : static int total_num_edges;
110 : static int total_num_edges_ignored;
111 : static int total_num_edges_instrumented;
112 : static int total_num_blocks_created;
113 : static int total_num_passes;
114 : static int total_num_times_called;
115 : static int total_hist_br_prob[20];
116 : static int total_num_branches;
117 : static int total_num_conds;
118 :
119 : /* Map between auto-fdo and fdo counts used to compare quality
120 : of the profiles. */
121 : struct afdo_fdo_record
122 : {
123 : cgraph_node *node;
124 : struct bb_record
125 : {
126 : /* Index of the basic block. */
127 : int index;
128 : profile_count afdo;
129 : profile_count fdo;
130 :
131 : /* Successors and predecessors in CFG. */
132 : vec <int> preds;
133 : vec <int> succs;
134 : };
135 : vec <bb_record> bbs;
136 : };
137 :
138 : static vec <afdo_fdo_record> afdo_fdo_records;
139 :
140 : /* Forward declarations. */
141 : static void find_spanning_tree (struct edge_list *);
142 :
143 : /* Add edge instrumentation code to the entire insn chain.
144 :
145 : F is the first insn of the chain.
146 : NUM_BLOCKS is the number of basic blocks found in F. */
147 :
148 : static unsigned
149 2140 : instrument_edges (struct edge_list *el)
150 : {
151 2140 : unsigned num_instr_edges = 0;
152 2140 : int num_edges = NUM_EDGES (el);
153 2140 : basic_block bb;
154 :
155 18293 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
156 : {
157 16153 : edge e;
158 16153 : edge_iterator ei;
159 :
160 32673 : FOR_EACH_EDGE (e, ei, bb->succs)
161 : {
162 16520 : struct edge_profile_info *inf = EDGE_INFO (e);
163 :
164 16520 : if (!inf->ignore && !inf->on_tree)
165 : {
166 8582 : gcc_assert (!(e->flags & EDGE_ABNORMAL));
167 8582 : if (dump_file)
168 696 : fprintf (dump_file, "Edge %d to %d instrumented%s\n",
169 232 : e->src->index, e->dest->index,
170 462 : EDGE_CRITICAL_P (e) ? " (and split)" : "");
171 8582 : gimple_gen_edge_profiler (num_instr_edges++, e);
172 : }
173 : }
174 : }
175 :
176 2140 : total_num_blocks_created += num_edges;
177 2140 : if (dump_file)
178 90 : fprintf (dump_file, "%d edges instrumented\n", num_instr_edges);
179 2140 : return num_instr_edges;
180 : }
181 :
182 : /* Add code to measure histograms for values in list VALUES. */
183 : static void
184 589 : instrument_values (histogram_values values)
185 : {
186 589 : unsigned i;
187 :
188 : /* Emit code to generate the histograms before the insns. */
189 :
190 1373 : for (i = 0; i < values.length (); i++)
191 : {
192 784 : histogram_value hist = values[i];
193 784 : unsigned t = COUNTER_FOR_HIST_TYPE (hist->type);
194 :
195 784 : if (!coverage_counter_alloc (t, hist->n_counters))
196 0 : continue;
197 :
198 784 : switch (hist->type)
199 : {
200 5 : case HIST_TYPE_INTERVAL:
201 5 : gimple_gen_interval_profiler (hist, t);
202 5 : break;
203 :
204 5 : case HIST_TYPE_POW2:
205 5 : gimple_gen_pow2_profiler (hist, t);
206 5 : break;
207 :
208 54 : case HIST_TYPE_TOPN_VALUES:
209 54 : gimple_gen_topn_values_profiler (hist, t);
210 54 : break;
211 :
212 49 : case HIST_TYPE_INDIR_CALL:
213 49 : gimple_gen_ic_profiler (hist, t);
214 49 : break;
215 :
216 41 : case HIST_TYPE_AVERAGE:
217 41 : gimple_gen_average_profiler (hist, t);
218 41 : break;
219 :
220 41 : case HIST_TYPE_IOR:
221 41 : gimple_gen_ior_profiler (hist, t);
222 41 : break;
223 :
224 589 : case HIST_TYPE_TIME_PROFILE:
225 589 : gimple_gen_time_profiler (t);
226 589 : break;
227 :
228 0 : default:
229 0 : gcc_unreachable ();
230 : }
231 : }
232 589 : }
233 :
234 :
235 : /* Computes hybrid profile for all matching entries in da_file.
236 :
237 : CFG_CHECKSUM is the precomputed checksum for the CFG. */
238 :
239 : static gcov_type *
240 581 : get_exec_counts (unsigned cfg_checksum, unsigned lineno_checksum)
241 : {
242 581 : unsigned num_edges = 0;
243 581 : basic_block bb;
244 581 : gcov_type *counts;
245 :
246 : /* Count the edges to be (possibly) instrumented. */
247 4613 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
248 : {
249 4032 : edge e;
250 4032 : edge_iterator ei;
251 :
252 8993 : FOR_EACH_EDGE (e, ei, bb->succs)
253 4961 : if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree)
254 2074 : num_edges++;
255 : }
256 :
257 581 : counts = get_coverage_counts (GCOV_COUNTER_ARCS, cfg_checksum,
258 : lineno_checksum, num_edges);
259 581 : if (!counts)
260 : return NULL;
261 :
262 : return counts;
263 : }
264 :
265 : static bool
266 4998 : is_edge_inconsistent (vec<edge, va_gc> *edges)
267 : {
268 4998 : edge e;
269 4998 : edge_iterator ei;
270 12007 : FOR_EACH_EDGE (e, ei, edges)
271 : {
272 7009 : if (!EDGE_INFO (e)->ignore)
273 : {
274 6977 : if (edge_gcov_count (e) < 0
275 6977 : && (!(e->flags & EDGE_FAKE)
276 1 : || !block_ends_with_call_p (e->src)))
277 : {
278 0 : if (dump_file)
279 : {
280 0 : fprintf (dump_file,
281 : "Edge %i->%i is inconsistent, count%" PRId64,
282 0 : e->src->index, e->dest->index, edge_gcov_count (e));
283 0 : dump_bb (dump_file, e->src, 0, TDF_DETAILS);
284 0 : dump_bb (dump_file, e->dest, 0, TDF_DETAILS);
285 : }
286 : return true;
287 : }
288 : }
289 : }
290 : return false;
291 : }
292 :
293 : static void
294 0 : correct_negative_edge_counts (void)
295 : {
296 0 : basic_block bb;
297 0 : edge e;
298 0 : edge_iterator ei;
299 :
300 0 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
301 : {
302 0 : FOR_EACH_EDGE (e, ei, bb->succs)
303 : {
304 0 : if (edge_gcov_count (e) < 0)
305 0 : edge_gcov_count (e) = 0;
306 : }
307 : }
308 0 : }
309 :
310 : /* Check consistency.
311 : Return true if inconsistency is found. */
312 : static bool
313 499 : is_inconsistent (void)
314 : {
315 499 : basic_block bb;
316 499 : bool inconsistent = false;
317 2998 : FOR_EACH_BB_FN (bb, cfun)
318 : {
319 2499 : inconsistent |= is_edge_inconsistent (bb->preds);
320 2499 : if (!dump_file && inconsistent)
321 : return true;
322 2499 : inconsistent |= is_edge_inconsistent (bb->succs);
323 2499 : if (!dump_file && inconsistent)
324 : return true;
325 2499 : if (bb_gcov_count (bb) < 0)
326 : {
327 0 : if (dump_file)
328 : {
329 0 : fprintf (dump_file, "BB %i count is negative "
330 : "%" PRId64,
331 : bb->index,
332 0 : bb_gcov_count (bb));
333 0 : dump_bb (dump_file, bb, 0, TDF_DETAILS);
334 : }
335 : inconsistent = true;
336 : }
337 2499 : if (bb_gcov_count (bb) != sum_edge_counts (bb->preds))
338 : {
339 0 : if (dump_file)
340 : {
341 0 : fprintf (dump_file, "BB %i count does not match sum of incoming edges "
342 : "%" PRId64" should be %" PRId64,
343 : bb->index,
344 0 : bb_gcov_count (bb),
345 : sum_edge_counts (bb->preds));
346 0 : dump_bb (dump_file, bb, 0, TDF_DETAILS);
347 : }
348 : inconsistent = true;
349 : }
350 2499 : if (bb_gcov_count (bb) != sum_edge_counts (bb->succs) &&
351 0 : ! (find_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun)) != NULL
352 0 : && block_ends_with_call_p (bb)))
353 : {
354 0 : if (dump_file)
355 : {
356 0 : fprintf (dump_file, "BB %i count does not match sum of outgoing edges "
357 : "%" PRId64" should be %" PRId64,
358 : bb->index,
359 0 : bb_gcov_count (bb),
360 : sum_edge_counts (bb->succs));
361 0 : dump_bb (dump_file, bb, 0, TDF_DETAILS);
362 : }
363 : inconsistent = true;
364 : }
365 2499 : if (!dump_file && inconsistent)
366 : return true;
367 : }
368 :
369 : return inconsistent;
370 : }
371 :
372 : /* Set each basic block count to the sum of its outgoing edge counts */
373 : static void
374 0 : set_bb_counts (void)
375 : {
376 0 : basic_block bb;
377 0 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
378 : {
379 0 : bb_gcov_count (bb) = sum_edge_counts (bb->succs);
380 0 : gcc_assert (bb_gcov_count (bb) >= 0);
381 : }
382 0 : }
383 :
384 : /* Reads profile data and returns total number of edge counts read */
385 : static int
386 499 : read_profile_edge_counts (gcov_type *exec_counts)
387 : {
388 499 : basic_block bb;
389 499 : int num_edges = 0;
390 499 : int exec_counts_pos = 0;
391 : /* For each edge not on the spanning tree, set its execution count from
392 : the .da file. */
393 : /* The first count in the .da file is the number of times that the function
394 : was entered. This is the exec_count for block zero. */
395 :
396 3996 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
397 : {
398 3497 : edge e;
399 3497 : edge_iterator ei;
400 :
401 7798 : FOR_EACH_EDGE (e, ei, bb->succs)
402 4301 : if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree)
403 : {
404 1785 : num_edges++;
405 1785 : if (exec_counts)
406 1778 : edge_gcov_count (e) = exec_counts[exec_counts_pos++];
407 : else
408 7 : edge_gcov_count (e) = 0;
409 :
410 1785 : EDGE_INFO (e)->count_valid = 1;
411 1785 : BB_INFO (bb)->succ_count--;
412 1785 : BB_INFO (e->dest)->pred_count--;
413 1785 : if (dump_file)
414 : {
415 234 : fprintf (dump_file, "\nRead edge from %i to %i, count:",
416 : bb->index, e->dest->index);
417 234 : fprintf (dump_file, "%" PRId64,
418 234 : (int64_t) edge_gcov_count (e));
419 : }
420 : }
421 : }
422 :
423 499 : return num_edges;
424 : }
425 :
426 : /* BB statistics comparing guessed frequency of BB with feedback. */
427 :
428 : struct bb_stats
429 : {
430 : basic_block bb;
431 : double guessed, feedback;
432 : int64_t count;
433 : };
434 :
435 : /* Compare limit_tuple intervals by first item in descending order. */
436 :
437 : static int
438 857 : cmp_stats (const void *ptr1, const void *ptr2)
439 : {
440 857 : const bb_stats *p1 = (const bb_stats *)ptr1;
441 857 : const bb_stats *p2 = (const bb_stats *)ptr2;
442 :
443 857 : if (p1->feedback < p2->feedback)
444 : return 1;
445 625 : else if (p1->feedback > p2->feedback)
446 277 : return -1;
447 : return 0;
448 : }
449 :
450 :
451 : /* Compute the branch probabilities for the various branches.
452 : Annotate them accordingly.
453 :
454 : CFG_CHECKSUM is the precomputed checksum for the CFG. */
455 :
456 : static void
457 581 : compute_branch_probabilities (unsigned cfg_checksum, unsigned lineno_checksum)
458 : {
459 581 : basic_block bb;
460 581 : int i;
461 581 : int num_edges = 0;
462 581 : int changes;
463 581 : int passes;
464 581 : int hist_br_prob[20];
465 581 : int num_branches;
466 581 : gcov_type *exec_counts = get_exec_counts (cfg_checksum, lineno_checksum);
467 581 : int inconsistent = 0;
468 :
469 : /* Very simple sanity checks so we catch bugs in our profiling code. */
470 581 : if (!profile_info)
471 : {
472 82 : if (dump_file)
473 0 : fprintf (dump_file, "Profile info is missing; giving up\n");
474 82 : return;
475 : }
476 :
477 499 : bb_gcov_counts.safe_grow_cleared (last_basic_block_for_fn (cfun), true);
478 499 : edge_gcov_counts = new hash_map<edge,gcov_type>;
479 :
480 : /* Attach extra info block to each bb. */
481 499 : alloc_aux_for_blocks (sizeof (struct bb_profile_info));
482 3996 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
483 : {
484 3497 : edge e;
485 3497 : edge_iterator ei;
486 :
487 7798 : FOR_EACH_EDGE (e, ei, bb->succs)
488 4301 : if (!EDGE_INFO (e)->ignore)
489 4284 : BB_INFO (bb)->succ_count++;
490 7798 : FOR_EACH_EDGE (e, ei, bb->preds)
491 4301 : if (!EDGE_INFO (e)->ignore)
492 4284 : BB_INFO (bb)->pred_count++;
493 : }
494 :
495 : /* Avoid predicting entry on exit nodes. */
496 499 : BB_INFO (EXIT_BLOCK_PTR_FOR_FN (cfun))->succ_count = 2;
497 499 : BB_INFO (ENTRY_BLOCK_PTR_FOR_FN (cfun))->pred_count = 2;
498 :
499 499 : afdo_fdo_record record = {cgraph_node::get (current_function_decl), vNULL};;
500 499 : if (dump_file && flag_auto_profile)
501 : {
502 0 : FOR_ALL_BB_FN (bb, cfun)
503 : {
504 0 : record.bbs.safe_push ({bb->index, bb->count.ipa (),
505 0 : profile_count::uninitialized (), vNULL, vNULL});
506 0 : record.bbs.last ().preds.reserve (EDGE_COUNT (bb->preds));
507 0 : for (auto &e : bb->preds)
508 0 : record.bbs.last ().preds.safe_push (e->src->index);
509 0 : record.bbs.last ().succs.reserve (EDGE_COUNT (bb->succs));
510 0 : for (auto &e : bb->succs)
511 0 : record.bbs.last ().succs.safe_push (e->dest->index);
512 : }
513 : }
514 :
515 499 : num_edges = read_profile_edge_counts (exec_counts);
516 :
517 499 : if (dump_file)
518 91 : fprintf (dump_file, "\n%d edge counts read\n", num_edges);
519 :
520 : /* For every block in the file,
521 : - if every exit/entrance edge has a known count, then set the block count
522 : - if the block count is known, and every exit/entrance edge but one has
523 : a known execution count, then set the count of the remaining edge
524 :
525 : As edge counts are set, decrement the succ/pred count, but don't delete
526 : the edge, that way we can easily tell when all edges are known, or only
527 : one edge is unknown. */
528 :
529 : /* The order that the basic blocks are iterated through is important.
530 : Since the code that finds spanning trees starts with block 0, low numbered
531 : edges are put on the spanning tree in preference to high numbered edges.
532 : Hence, most instrumented edges are at the end. Graph solving works much
533 : faster if we propagate numbers from the end to the start.
534 :
535 : This takes an average of slightly more than 3 passes. */
536 :
537 499 : changes = 1;
538 499 : passes = 0;
539 2574 : while (changes)
540 : {
541 2075 : passes++;
542 2075 : changes = 0;
543 19573 : FOR_BB_BETWEEN (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), NULL, prev_bb)
544 : {
545 17498 : struct bb_profile_info *bi = BB_INFO (bb);
546 17498 : if (! bi->count_valid)
547 : {
548 6201 : if (bi->succ_count == 0)
549 : {
550 827 : edge e;
551 827 : edge_iterator ei;
552 827 : gcov_type total = 0;
553 :
554 1885 : FOR_EACH_EDGE (e, ei, bb->succs)
555 1058 : total += edge_gcov_count (e);
556 827 : bb_gcov_count (bb) = total;
557 827 : bi->count_valid = 1;
558 827 : changes = 1;
559 : }
560 5374 : else if (bi->pred_count == 0)
561 : {
562 2670 : edge e;
563 2670 : edge_iterator ei;
564 2670 : gcov_type total = 0;
565 :
566 6513 : FOR_EACH_EDGE (e, ei, bb->preds)
567 3843 : total += edge_gcov_count (e);
568 2670 : bb_gcov_count (bb) = total;
569 2670 : bi->count_valid = 1;
570 2670 : changes = 1;
571 : }
572 : }
573 17498 : if (bi->count_valid)
574 : {
575 14794 : if (bi->succ_count == 1)
576 : {
577 2171 : edge e;
578 2171 : edge_iterator ei;
579 2171 : gcov_type total = 0;
580 :
581 : /* One of the counts will be invalid, but it is zero,
582 : so adding it in also doesn't hurt. */
583 5414 : FOR_EACH_EDGE (e, ei, bb->succs)
584 3243 : total += edge_gcov_count (e);
585 :
586 : /* Search for the invalid edge, and set its count. */
587 3077 : FOR_EACH_EDGE (e, ei, bb->succs)
588 3077 : if (! EDGE_INFO (e)->count_valid && ! EDGE_INFO (e)->ignore)
589 : break;
590 :
591 : /* Calculate count for remaining edge by conservation. */
592 2171 : total = bb_gcov_count (bb) - total;
593 :
594 2171 : gcc_assert (e);
595 2171 : EDGE_INFO (e)->count_valid = 1;
596 2171 : edge_gcov_count (e) = total;
597 2171 : bi->succ_count--;
598 :
599 2171 : BB_INFO (e->dest)->pred_count--;
600 2171 : changes = 1;
601 : }
602 14794 : if (bi->pred_count == 1)
603 : {
604 328 : edge e;
605 328 : edge_iterator ei;
606 328 : gcov_type total = 0;
607 :
608 : /* One of the counts will be invalid, but it is zero,
609 : so adding it in also doesn't hurt. */
610 786 : FOR_EACH_EDGE (e, ei, bb->preds)
611 458 : total += edge_gcov_count (e);
612 :
613 : /* Search for the invalid edge, and set its count. */
614 386 : FOR_EACH_EDGE (e, ei, bb->preds)
615 386 : if (!EDGE_INFO (e)->count_valid && !EDGE_INFO (e)->ignore)
616 : break;
617 :
618 : /* Calculate count for remaining edge by conservation. */
619 328 : total = bb_gcov_count (bb) - total + edge_gcov_count (e);
620 :
621 328 : gcc_assert (e);
622 328 : EDGE_INFO (e)->count_valid = 1;
623 328 : edge_gcov_count (e) = total;
624 328 : bi->pred_count--;
625 :
626 328 : BB_INFO (e->src)->succ_count--;
627 328 : changes = 1;
628 : }
629 : }
630 : }
631 : }
632 :
633 499 : total_num_passes += passes;
634 499 : if (dump_file)
635 91 : fprintf (dump_file, "Graph solving took %d passes.\n\n", passes);
636 :
637 : /* If the graph has been correctly solved, every block will have a
638 : succ and pred count of zero. */
639 2998 : FOR_EACH_BB_FN (bb, cfun)
640 : {
641 2499 : gcc_assert (!BB_INFO (bb)->succ_count && !BB_INFO (bb)->pred_count);
642 : }
643 :
644 : /* Check for inconsistent basic block counts */
645 499 : inconsistent = is_inconsistent ();
646 :
647 499 : if (inconsistent)
648 : {
649 0 : if (flag_profile_correction)
650 : {
651 : /* Inconsistency detected. Make it flow-consistent. */
652 0 : static int informed = 0;
653 0 : if (dump_enabled_p () && informed == 0)
654 : {
655 0 : informed = 1;
656 0 : dump_printf_loc (MSG_NOTE,
657 0 : dump_user_location_t::from_location_t (input_location),
658 : "correcting inconsistent profile data\n");
659 : }
660 0 : correct_negative_edge_counts ();
661 : /* Set bb counts to the sum of the outgoing edge counts */
662 0 : set_bb_counts ();
663 0 : if (dump_file)
664 0 : fprintf (dump_file, "\nCalling mcf_smooth_cfg\n");
665 0 : mcf_smooth_cfg ();
666 : }
667 : else
668 0 : error ("corrupted profile info: profile data is not flow-consistent");
669 : }
670 :
671 : /* For every edge, calculate its branch probability and add a reg_note
672 : to the branch insn to indicate this. */
673 :
674 10479 : for (i = 0; i < 20; i++)
675 9980 : hist_br_prob[i] = 0;
676 499 : num_branches = 0;
677 :
678 3996 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
679 : {
680 3497 : edge e;
681 3497 : edge_iterator ei;
682 :
683 3497 : if (bb_gcov_count (bb) < 0)
684 : {
685 0 : error ("corrupted profile info: number of iterations for basic block %d thought to be %i",
686 0 : bb->index, (int)bb_gcov_count (bb));
687 0 : bb_gcov_count (bb) = 0;
688 : }
689 7798 : FOR_EACH_EDGE (e, ei, bb->succs)
690 : {
691 : /* Function may return twice in the cased the called function is
692 : setjmp or calls fork, but we can't represent this by extra
693 : edge from the entry, since extra edge from the exit is
694 : already present. We get negative frequency from the entry
695 : point. */
696 4301 : if ((edge_gcov_count (e) < 0
697 1 : && e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
698 4301 : || (edge_gcov_count (e) > bb_gcov_count (bb)
699 1 : && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)))
700 : {
701 2 : if (block_ends_with_call_p (bb))
702 4 : edge_gcov_count (e) = edge_gcov_count (e) < 0
703 3 : ? 0 : bb_gcov_count (bb);
704 : }
705 4301 : if (edge_gcov_count (e) < 0
706 4301 : || edge_gcov_count (e) > bb_gcov_count (bb))
707 : {
708 0 : error ("corrupted profile info: number of executions for edge %d-%d thought to be %i",
709 0 : e->src->index, e->dest->index,
710 0 : (int)edge_gcov_count (e));
711 0 : edge_gcov_count (e) = bb_gcov_count (bb) / 2;
712 : }
713 : }
714 3497 : if (bb_gcov_count (bb))
715 : {
716 2508 : bool set_to_guessed = false;
717 5680 : FOR_EACH_EDGE (e, ei, bb->succs)
718 : {
719 3172 : bool prev_never = e->probability == profile_probability::never ();
720 3172 : e->probability = profile_probability::probability_in_gcov_type
721 3172 : (edge_gcov_count (e), bb_gcov_count (bb));
722 3890 : if (e->probability == profile_probability::never ()
723 718 : && !prev_never
724 3750 : && flag_profile_partial_training)
725 0 : set_to_guessed = true;
726 : }
727 2508 : if (set_to_guessed)
728 0 : FOR_EACH_EDGE (e, ei, bb->succs)
729 0 : e->probability = e->probability.guessed ();
730 2508 : if (bb->index >= NUM_FIXED_BLOCKS
731 1780 : && block_ends_with_condjump_p (bb)
732 2990 : && EDGE_COUNT (bb->succs) >= 2)
733 : {
734 482 : int prob;
735 482 : edge e;
736 482 : int index;
737 :
738 : /* Find the branch edge. It is possible that we do have fake
739 : edges here. */
740 482 : FOR_EACH_EDGE (e, ei, bb->succs)
741 482 : if (!(e->flags & (EDGE_FAKE | EDGE_FALLTHRU)))
742 : break;
743 :
744 482 : prob = e->probability.to_reg_br_prob_base ();
745 482 : index = prob * 20 / REG_BR_PROB_BASE;
746 :
747 482 : if (index == 20)
748 56 : index = 19;
749 482 : hist_br_prob[index]++;
750 :
751 482 : num_branches++;
752 : }
753 : }
754 : /* As a last resort, distribute the probabilities evenly.
755 : Use simple heuristics that if there are normal edges,
756 : give all abnormals frequency of 0, otherwise distribute the
757 : frequency over abnormals (this is the case of noreturn
758 : calls). */
759 989 : else if (profile_status_for_fn (cfun) == PROFILE_ABSENT)
760 : {
761 16 : int total = 0;
762 :
763 34 : FOR_EACH_EDGE (e, ei, bb->succs)
764 18 : if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
765 11 : total ++;
766 16 : if (total)
767 : {
768 22 : FOR_EACH_EDGE (e, ei, bb->succs)
769 11 : if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
770 11 : e->probability
771 11 : = profile_probability::guessed_always () / total;
772 : else
773 0 : e->probability = profile_probability::never ();
774 : }
775 : else
776 : {
777 5 : total += EDGE_COUNT (bb->succs);
778 12 : FOR_EACH_EDGE (e, ei, bb->succs)
779 7 : e->probability = profile_probability::guessed_always () / total;
780 : }
781 16 : if (bb->index >= NUM_FIXED_BLOCKS
782 16 : && block_ends_with_condjump_p (bb)
783 3513 : && EDGE_COUNT (bb->succs) >= 2)
784 0 : num_branches++;
785 : }
786 : }
787 :
788 499 : if (exec_counts
789 499 : && (bb_gcov_count (ENTRY_BLOCK_PTR_FOR_FN (cfun))
790 133 : || !flag_profile_partial_training))
791 497 : profile_status_for_fn (cfun) = PROFILE_READ;
792 :
793 : /* If we have real data, use them! */
794 499 : if (bb_gcov_count (ENTRY_BLOCK_PTR_FOR_FN (cfun))
795 499 : || !flag_guess_branch_prob)
796 : {
797 364 : profile_count old_entry_cnt = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count;
798 364 : auto_vec <bb_stats> stats;
799 364 : double sum1 = 0, sum2 = 0;
800 :
801 3101 : FOR_ALL_BB_FN (bb, cfun)
802 : {
803 2737 : profile_count cnt = bb->count;
804 2737 : if (bb_gcov_count (bb) || !flag_profile_partial_training)
805 2737 : bb->count = profile_count::from_gcov_type (bb_gcov_count (bb));
806 : else
807 0 : bb->count = profile_count::guessed_zero ();
808 :
809 2737 : if (dump_file && (dump_flags & TDF_DETAILS) && bb->index >= 0)
810 : {
811 85 : double freq1 = cnt.to_sreal_scale (old_entry_cnt).to_double ();
812 85 : double freq2 = bb->count.to_sreal_scale
813 85 : (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count).
814 85 : to_double ();
815 85 : bb_stats stat = {bb, freq1, freq2,
816 85 : (int64_t) bb_gcov_count (bb)};
817 85 : stats.safe_push (stat);
818 85 : sum1 += freq1;
819 85 : sum2 += freq2;
820 : }
821 : }
822 364 : if (dump_file && (dump_flags & TDF_DETAILS))
823 : {
824 12 : double nsum1 = 0, nsum2 = 0;
825 12 : stats.qsort (cmp_stats);
826 121 : for (auto stat : stats)
827 : {
828 85 : nsum1 += stat.guessed;
829 85 : nsum2 += stat.feedback;
830 85 : fprintf (dump_file,
831 : " Basic block %4i guessed freq: %12.3f"
832 : " cumulative:%6.2f%% "
833 : " feedback freq: %12.3f cumulative:%7.2f%%"
834 : " cnt: 10%" PRId64 "\n", stat.bb->index,
835 : stat.guessed,
836 85 : nsum1 * 100 / sum1,
837 : stat.feedback,
838 85 : nsum2 * 100 / sum2,
839 : stat.count);
840 : }
841 : }
842 364 : }
843 : /* If function was not trained, preserve local estimates including statically
844 : determined zero counts. */
845 135 : else if (profile_status_for_fn (cfun) == PROFILE_READ
846 133 : && !flag_profile_partial_training)
847 882 : FOR_ALL_BB_FN (bb, cfun)
848 756 : if (!(bb->count == profile_count::zero ()))
849 742 : bb->count = bb->count.global0 ();
850 :
851 499 : bb_gcov_counts.release ();
852 998 : delete edge_gcov_counts;
853 499 : edge_gcov_counts = NULL;
854 :
855 499 : if (dump_file && flag_auto_profile)
856 : {
857 0 : int i = 0;
858 0 : FOR_ALL_BB_FN (bb, cfun)
859 : {
860 0 : gcc_checking_assert (record.bbs[i].index == bb->index);
861 0 : record.bbs[i].fdo = bb->count.ipa ();
862 0 : i++;
863 : }
864 0 : afdo_fdo_records.safe_push (record);
865 : }
866 :
867 499 : update_max_bb_count ();
868 :
869 499 : if (dump_file)
870 : {
871 91 : fprintf (dump_file, " Profile feedback for function");
872 93 : fprintf (dump_file, ((profile_status_for_fn (cfun) == PROFILE_READ)
873 : ? " is available \n"
874 : : " is not available \n"));
875 :
876 91 : fprintf (dump_file, "%d branches\n", num_branches);
877 91 : if (num_branches)
878 286 : for (i = 0; i < 10; i++)
879 260 : fprintf (dump_file, "%d%% branches in range %d-%d%%\n",
880 260 : (hist_br_prob[i] + hist_br_prob[19-i]) * 100 / num_branches,
881 260 : 5 * i, 5 * i + 5);
882 :
883 91 : total_num_branches += num_branches;
884 1911 : for (i = 0; i < 20; i++)
885 1820 : total_hist_br_prob[i] += hist_br_prob[i];
886 :
887 91 : fputc ('\n', dump_file);
888 91 : fputc ('\n', dump_file);
889 :
890 91 : gimple_dump_cfg (dump_file, TDF_BLOCKS);
891 : }
892 :
893 499 : free_aux_for_blocks ();
894 : }
895 :
896 : /* Sort the histogram value and count for TOPN and INDIR_CALL type. */
897 :
898 : static void
899 83 : sort_hist_values (histogram_value hist)
900 : {
901 83 : gcc_assert (hist->type == HIST_TYPE_TOPN_VALUES
902 : || hist->type == HIST_TYPE_INDIR_CALL);
903 :
904 83 : int counters = hist->hvalue.counters[1];
905 125 : for (int i = 0; i < counters - 1; i++)
906 : /* Hist value is organized as:
907 : [total_executions, N, value1, counter1, ..., valueN, counterN]
908 : Use decrease bubble sort to rearrange it. The sort starts from <value1,
909 : counter1> and compares counter first. If counter is same, compares the
910 : value, exchange it if small to keep stable. */
911 :
912 : {
913 : bool swapped = false;
914 611 : for (int j = 0; j < counters - 1 - i; j++)
915 : {
916 543 : gcov_type *p = &hist->hvalue.counters[2 * j + 2];
917 543 : if (p[1] < p[3] || (p[1] == p[3] && p[0] < p[2]))
918 : {
919 483 : std::swap (p[0], p[2]);
920 483 : std::swap (p[1], p[3]);
921 483 : swapped = true;
922 : }
923 : }
924 68 : if (!swapped)
925 : break;
926 : }
927 83 : }
928 : /* Load value histograms values whose description is stored in VALUES array
929 : from .gcda file.
930 :
931 : CFG_CHECKSUM is the precomputed checksum for the CFG. */
932 :
933 : static void
934 435 : compute_value_histograms (histogram_values values, unsigned cfg_checksum,
935 : unsigned lineno_checksum)
936 : {
937 435 : unsigned i, j, t, any;
938 435 : unsigned n_histogram_counters[GCOV_N_VALUE_COUNTERS];
939 435 : gcov_type *histogram_counts[GCOV_N_VALUE_COUNTERS];
940 435 : gcov_type *act_count[GCOV_N_VALUE_COUNTERS];
941 435 : gcov_type *aact_count;
942 435 : struct cgraph_node *node;
943 :
944 4350 : for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++)
945 3915 : n_histogram_counters[t] = 0;
946 :
947 2136 : for (i = 0; i < values.length (); i++)
948 : {
949 633 : histogram_value hist = values[i];
950 633 : n_histogram_counters[(int) hist->type] += hist->n_counters;
951 : }
952 :
953 : any = 0;
954 4350 : for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++)
955 : {
956 3915 : if (!n_histogram_counters[t])
957 : {
958 3295 : histogram_counts[t] = NULL;
959 3295 : continue;
960 : }
961 :
962 620 : histogram_counts[t] = get_coverage_counts (COUNTER_FOR_HIST_TYPE (t),
963 : cfg_checksum,
964 : lineno_checksum,
965 : n_histogram_counters[t]);
966 620 : if (histogram_counts[t])
967 492 : any = 1;
968 620 : act_count[t] = histogram_counts[t];
969 : }
970 435 : if (!any)
971 98 : return;
972 :
973 1666 : for (i = 0; i < values.length (); i++)
974 : {
975 496 : histogram_value hist = values[i];
976 496 : gimple *stmt = hist->hvalue.stmt;
977 :
978 496 : t = (int) hist->type;
979 496 : bool topn_p = (hist->type == HIST_TYPE_TOPN_VALUES
980 496 : || hist->type == HIST_TYPE_INDIR_CALL);
981 :
982 : /* TOP N counter uses variable number of counters. */
983 496 : if (topn_p)
984 : {
985 83 : unsigned total_size;
986 83 : if (act_count[t])
987 83 : total_size = 2 + 2 * act_count[t][1];
988 : else
989 : total_size = 2;
990 83 : gimple_add_histogram_value (cfun, stmt, hist);
991 83 : hist->n_counters = total_size;
992 83 : hist->hvalue.counters = XNEWVEC (gcov_type, hist->n_counters);
993 539 : for (j = 0; j < hist->n_counters; j++)
994 456 : if (act_count[t])
995 456 : hist->hvalue.counters[j] = act_count[t][j];
996 : else
997 0 : hist->hvalue.counters[j] = 0;
998 83 : act_count[t] += hist->n_counters;
999 83 : sort_hist_values (hist);
1000 : }
1001 : else
1002 : {
1003 413 : aact_count = act_count[t];
1004 :
1005 413 : if (act_count[t])
1006 413 : act_count[t] += hist->n_counters;
1007 :
1008 413 : gimple_add_histogram_value (cfun, stmt, hist);
1009 413 : hist->hvalue.counters = XNEWVEC (gcov_type, hist->n_counters);
1010 879 : for (j = 0; j < hist->n_counters; j++)
1011 466 : if (aact_count)
1012 466 : hist->hvalue.counters[j] = aact_count[j];
1013 : else
1014 0 : hist->hvalue.counters[j] = 0;
1015 : }
1016 :
1017 : /* Time profiler counter is not related to any statement,
1018 : so that we have to read the counter and set the value to
1019 : the corresponding call graph node. */
1020 496 : if (hist->type == HIST_TYPE_TIME_PROFILE)
1021 : {
1022 337 : node = cgraph_node::get (hist->fun->decl);
1023 337 : if (hist->hvalue.counters[0] >= 0
1024 337 : && hist->hvalue.counters[0] < INT_MAX / 2)
1025 337 : node->tp_first_run = hist->hvalue.counters[0];
1026 : else
1027 : {
1028 0 : if (flag_profile_correction)
1029 0 : error ("corrupted profile info: invalid time profile");
1030 0 : node->tp_first_run = 0;
1031 : }
1032 :
1033 : /* Drop profile for -fprofile-reproducible=multithreaded. */
1034 337 : bool drop
1035 337 : = (flag_profile_reproducible == PROFILE_REPRODUCIBILITY_MULTITHREADED);
1036 337 : if (drop)
1037 0 : node->tp_first_run = 0;
1038 :
1039 337 : if (dump_file)
1040 178 : fprintf (dump_file, "Read tp_first_run: %d%s\n", node->tp_first_run,
1041 : drop ? "; ignored because profile reproducibility is "
1042 : "multi-threaded" : "");
1043 : }
1044 : }
1045 :
1046 3370 : for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++)
1047 3033 : free (histogram_counts[t]);
1048 : }
1049 :
1050 : /* Location triplet which records a location. */
1051 : struct location_triplet
1052 : {
1053 : const char *filename;
1054 : int lineno;
1055 : int bb_index;
1056 : };
1057 :
1058 : /* Traits class for streamed_locations hash set below. */
1059 :
1060 : struct location_triplet_hash : typed_noop_remove <location_triplet>
1061 : {
1062 : typedef location_triplet value_type;
1063 : typedef location_triplet compare_type;
1064 :
1065 : static hashval_t
1066 87096 : hash (const location_triplet &ref)
1067 : {
1068 87096 : inchash::hash hstate (0);
1069 87096 : if (ref.filename)
1070 84995 : hstate.add_int (strlen (ref.filename));
1071 87096 : hstate.add_int (ref.lineno);
1072 87096 : hstate.add_int (ref.bb_index);
1073 87096 : return hstate.end ();
1074 : }
1075 :
1076 : static bool
1077 75895 : equal (const location_triplet &ref1, const location_triplet &ref2)
1078 : {
1079 75895 : return ref1.lineno == ref2.lineno
1080 10211 : && ref1.bb_index == ref2.bb_index
1081 5083 : && ref1.filename != NULL
1082 5083 : && ref2.filename != NULL
1083 80978 : && strcmp (ref1.filename, ref2.filename) == 0;
1084 : }
1085 :
1086 : static void
1087 : mark_deleted (location_triplet &ref)
1088 : {
1089 : ref.lineno = -1;
1090 : }
1091 :
1092 : static const bool empty_zero_p = false;
1093 :
1094 : static void
1095 59115 : mark_empty (location_triplet &ref)
1096 : {
1097 59115 : ref.lineno = -2;
1098 : }
1099 :
1100 : static bool
1101 100472 : is_deleted (const location_triplet &ref)
1102 : {
1103 100472 : return ref.lineno == -1;
1104 : }
1105 :
1106 : static bool
1107 448590 : is_empty (const location_triplet &ref)
1108 : {
1109 434739 : return ref.lineno == -2;
1110 : }
1111 : };
1112 :
1113 :
1114 :
1115 :
1116 : /* When passed NULL as file_name, initialize.
1117 : When passed something else, output the necessary commands to change
1118 : line to LINE and offset to FILE_NAME. */
1119 : static void
1120 18930 : output_location (hash_set<location_triplet_hash> *streamed_locations,
1121 : char const *file_name, int line,
1122 : gcov_position_t *offset, basic_block bb)
1123 : {
1124 18930 : static char const *prev_file_name;
1125 18930 : static int prev_line;
1126 18930 : bool name_differs, line_differs;
1127 :
1128 18930 : if (file_name != NULL)
1129 17433 : file_name = remap_profile_filename (file_name);
1130 :
1131 18930 : location_triplet triplet;
1132 18930 : triplet.filename = file_name;
1133 18930 : triplet.lineno = line;
1134 18930 : triplet.bb_index = bb ? bb->index : 0;
1135 :
1136 18930 : if (streamed_locations->add (triplet))
1137 6576 : return;
1138 :
1139 13851 : if (!file_name)
1140 : {
1141 1497 : prev_file_name = NULL;
1142 1497 : prev_line = -1;
1143 1497 : return;
1144 : }
1145 :
1146 12354 : name_differs = !prev_file_name || filename_cmp (file_name, prev_file_name);
1147 12354 : line_differs = prev_line != line;
1148 :
1149 12354 : if (!*offset)
1150 : {
1151 9572 : *offset = gcov_write_tag (GCOV_TAG_LINES);
1152 9572 : gcov_write_unsigned (bb->index);
1153 9572 : name_differs = line_differs = true;
1154 : }
1155 :
1156 : /* If this is a new source file, then output the
1157 : file's name to the .bb file. */
1158 12354 : if (name_differs)
1159 : {
1160 9657 : prev_file_name = file_name;
1161 9657 : gcov_write_unsigned (0);
1162 9657 : gcov_write_filename (prev_file_name);
1163 : }
1164 12354 : if (line_differs)
1165 : {
1166 12351 : gcov_write_unsigned (line);
1167 12351 : prev_line = line;
1168 : }
1169 : }
1170 :
1171 : /* Helper for qsort so edges get sorted from highest frequency to smallest.
1172 : This controls the weight for minimal spanning tree algorithm */
1173 : static int
1174 601249 : compare_freqs (const void *p1, const void *p2)
1175 : {
1176 601249 : const_edge e1 = *(const const_edge *)p1;
1177 601249 : const_edge e2 = *(const const_edge *)p2;
1178 :
1179 : /* Critical edges needs to be split which introduce extra control flow.
1180 : Make them more heavy. */
1181 601249 : int m1 = EDGE_CRITICAL_P (e1) ? 2 : 1;
1182 601249 : int m2 = EDGE_CRITICAL_P (e2) ? 2 : 1;
1183 :
1184 601249 : if (EDGE_FREQUENCY (e1) * m1 + m1 != EDGE_FREQUENCY (e2) * m2 + m2)
1185 206786 : return EDGE_FREQUENCY (e2) * m2 + m2 - EDGE_FREQUENCY (e1) * m1 - m1;
1186 : /* Stabilize sort. */
1187 394463 : if (e1->src->index != e2->src->index)
1188 360282 : return e2->src->index - e1->src->index;
1189 34181 : return e2->dest->index - e1->dest->index;
1190 : }
1191 :
1192 : /* Only read execution count for thunks. */
1193 :
1194 : void
1195 7 : read_thunk_profile (struct cgraph_node *node)
1196 : {
1197 7 : tree old = current_function_decl;
1198 7 : current_function_decl = node->decl;
1199 7 : gcov_type *counts = get_coverage_counts (GCOV_COUNTER_ARCS, 0, 0, 1);
1200 7 : if (counts)
1201 : {
1202 14 : node->callees->count = node->count
1203 7 : = profile_count::from_gcov_type (counts[0]);
1204 7 : free (counts);
1205 : }
1206 7 : current_function_decl = old;
1207 7 : return;
1208 : }
1209 :
1210 : /* Disable coverage for BB. This is used for #pragma GCC suppress_coverage. */
1211 : void
1212 2309 : suppress_coverage (basic_block bb)
1213 : {
1214 2309 : bb->flags |= BB_COVERAGE_SUPPRESSED;
1215 2309 : }
1216 :
1217 : /* Unset the flag set by suppress_coverage. This is only useful when merging
1218 : blocks. */
1219 : void
1220 23 : suppress_coverage_unset (basic_block bb)
1221 : {
1222 23 : bb->flags &= ~BB_COVERAGE_SUPPRESSED;
1223 23 : }
1224 :
1225 : /* Check if BB has coverage disabled by #pragma GCC suppress_coverage. */
1226 : bool
1227 212444357 : coverage_suppressed_p (basic_block bb)
1228 : {
1229 212444357 : return bb->flags & BB_COVERAGE_SUPPRESSED;
1230 : }
1231 :
1232 : /* Check if any blocks are disabled by #pragma suppress_coverage in the current
1233 : function. */
1234 : static bool
1235 1465 : any_block_coverage_suppressed_p ()
1236 : {
1237 1465 : basic_block bb;
1238 9769 : FOR_EACH_BB_FN (bb, cfun)
1239 8557 : if (coverage_suppressed_p (bb))
1240 : return true;
1241 : return false;
1242 : }
1243 :
1244 : /* The source locations of #pragma GCC suppress_coverage begin/end. For each
1245 : entry, the source_range m_finish/m_end should be the (expanded) source
1246 : location of the begin/end. If there is no end, m_finish will be
1247 : UNKNOWN_LOCATION. */
1248 : static vec<source_range> suppress_coverage_ranges;
1249 :
1250 : /* Try to add LOC as the beginning of a new range. If a range was started
1251 : already, this is a no-op. Returns true if a new range was created. */
1252 : bool
1253 349 : suppress_coverage_begin (location_t loc)
1254 : {
1255 685 : if (!suppress_coverage_ranges.is_empty ()
1256 336 : && suppress_coverage_ranges.last ().m_finish == UNKNOWN_LOCATION)
1257 : return false;
1258 :
1259 348 : loc = get_pure_location (expansion_point_location (loc));
1260 348 : source_range range = source_range::from_locations (loc, UNKNOWN_LOCATION);
1261 348 : suppress_coverage_ranges.safe_push (range);
1262 348 : return true;
1263 : }
1264 :
1265 : /* Try to close the last range created by suppress_coverage_begin at LOC. If
1266 : the range has been closed already (or not opened), this is a no-op. Returns
1267 : true if a range was closed. */
1268 : bool
1269 348 : suppress_coverage_end (location_t loc)
1270 : {
1271 695 : if (suppress_coverage_ranges.is_empty ()
1272 347 : || suppress_coverage_ranges.last ().m_finish != UNKNOWN_LOCATION)
1273 : return false;
1274 347 : loc = get_pure_location (expansion_point_location (loc));
1275 347 : suppress_coverage_ranges.last ().m_finish = loc;
1276 347 : return true;
1277 : }
1278 :
1279 : /* Check if STMT is anchored to a line of code in a range disabled by #pragma
1280 : GCC suppress_coverage begin/end. This function always returns false if
1281 : coverage is disabled as it is the faster check, and nothing should be
1282 : suppressed anyway.
1283 :
1284 : If STMT is at an UNKNOWN_LOCATION or ADHOC_LOC, this function returns PREV.
1285 : This is probably a compiler-generated statement that should inherit the
1286 : disabled state of the previous statement since it is really tied to it, and
1287 : there is no opportunity for a #pragma in-between. */
1288 : bool
1289 96692736 : in_pragma_suppress_coverage_p (gimple* stmt, bool prev)
1290 : {
1291 96692736 : if (!coverage_instrumentation_p ())
1292 : return false;
1293 :
1294 53087 : location_t loc = expansion_point_location (gimple_location (stmt));
1295 53087 : if (loc == UNKNOWN_LOCATION || IS_ADHOC_LOC (loc))
1296 : return prev;
1297 :
1298 39621 : return location_in_pragma_suppress_coverage_p (loc);
1299 : }
1300 :
1301 : /* Check if LOC is within a #pragma GCC suppress_coverage block. */
1302 : bool
1303 3066708 : location_in_pragma_suppress_coverage_p (location_t loc)
1304 : {
1305 3066708 : loc = get_pure_location (expansion_point_location (loc));
1306 3323107 : for (const source_range& dl : suppress_coverage_ranges)
1307 245995 : if (linemap_location_before_p (line_table, dl.m_start, loc)
1308 245995 : && (linemap_location_before_p (line_table, loc, dl.m_finish)
1309 147783 : || dl.m_finish == UNKNOWN_LOCATION))
1310 : return true;
1311 : return false;
1312 : }
1313 :
1314 : /* Check if FN is fully between #pragma GCC suppress_coverage begin/end. In
1315 : that case we can disable the whole function rather than every block, and
1316 : omit MC/DC (-fcondition-coverage) and prime path coverage (-fpath-coverage)
1317 : instrumentation. */
1318 : static bool
1319 3012 : fn_in_pragma_suppress_coverage_p (function *fn)
1320 : {
1321 3012 : if (!coverage_instrumentation_p ())
1322 : return false;
1323 :
1324 2420 : if (lookup_attribute ("gnu", "suppress_coverage",
1325 2420 : DECL_ATTRIBUTES (fn->decl)))
1326 : return true;
1327 :
1328 2393 : const location_t start = fn->function_start_locus;
1329 2393 : const location_t end = fn->function_end_locus;
1330 :
1331 19507 : for (const source_range& dl : suppress_coverage_ranges)
1332 16361 : if (linemap_location_before_p (line_table, dl.m_start, start)
1333 16361 : && (linemap_location_before_p (line_table, end, dl.m_finish)
1334 7394 : || dl.m_finish == UNKNOWN_LOCATION))
1335 : return true;
1336 : return false;
1337 : }
1338 :
1339 : /* Instrument and/or analyze program behavior based on program the CFG.
1340 :
1341 : This function creates a representation of the control flow graph (of
1342 : the function being compiled) that is suitable for the instrumentation
1343 : of edges and/or converting measured edge counts to counts on the
1344 : complete CFG.
1345 :
1346 : When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in
1347 : the flow graph that are needed to reconstruct the dynamic behavior of the
1348 : flow graph. This data is written to the gcno file for gcov.
1349 :
1350 : When FLAG_PROFILE_CONDITIONS is nonzero, this functions instruments the
1351 : edges in the control flow graph to track what conditions are evaluated to in
1352 : order to determine what conditions are covered and have an independent
1353 : effect on the outcome (modified condition/decision coverage). This data is
1354 : written to the gcno file for gcov.
1355 :
1356 : When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
1357 : information from the gcda file containing edge count information from
1358 : previous executions of the function being compiled. In this case, the
1359 : control flow graph is annotated with actual execution counts by
1360 : compute_branch_probabilities().
1361 :
1362 : Main entry point of this file. */
1363 :
1364 : void
1365 3012 : branch_prob (bool thunk)
1366 : {
1367 3012 : basic_block bb;
1368 3012 : unsigned i;
1369 3012 : unsigned num_edges, ignored_edges;
1370 3012 : unsigned num_instrumented;
1371 3012 : struct edge_list *el;
1372 3012 : histogram_values values = histogram_values ();
1373 3012 : unsigned cfg_checksum, lineno_checksum;
1374 3012 : bool output_to_file;
1375 :
1376 3012 : total_num_times_called++;
1377 :
1378 3012 : flow_call_edges_add (NULL);
1379 3012 : add_noreturn_fake_exit_edges ();
1380 :
1381 3012 : hash_set <location_triplet_hash> streamed_locations;
1382 :
1383 3012 : if (!thunk)
1384 : {
1385 : /* We can't handle cyclic regions constructed using abnormal edges.
1386 : To avoid these we replace every source of abnormal edge by a fake
1387 : edge from entry node and every destination by fake edge to exit.
1388 : This keeps graph acyclic and our calculation exact for all normal
1389 : edges except for exit and entrance ones.
1390 :
1391 : We also add fake exit edges for each call and asm statement in the
1392 : basic, since it may not return. */
1393 :
1394 20428 : FOR_EACH_BB_FN (bb, cfun)
1395 : {
1396 17423 : int need_exit_edge = 0, need_entry_edge = 0;
1397 17423 : int have_exit_edge = 0, have_entry_edge = 0;
1398 17423 : edge e;
1399 17423 : edge_iterator ei;
1400 :
1401 : /* Functions returning multiple times are not handled by extra edges.
1402 : Instead we simply allow negative counts on edges from exit to the
1403 : block past call and corresponding probabilities. We can't go
1404 : with the extra edges because that would result in flowgraph that
1405 : needs to have fake edges outside the spanning tree. */
1406 :
1407 44640 : FOR_EACH_EDGE (e, ei, bb->succs)
1408 : {
1409 27217 : gimple_stmt_iterator gsi;
1410 27217 : gimple *last = NULL;
1411 :
1412 : /* It may happen that there are compiler generated statements
1413 : without a locus at all. Go through the basic block from the
1414 : last to the first statement looking for a locus. */
1415 27217 : for (gsi = gsi_last_nondebug_bb (bb);
1416 30439 : !gsi_end_p (gsi);
1417 3222 : gsi_prev_nondebug (&gsi))
1418 : {
1419 27736 : last = gsi_stmt (gsi);
1420 27736 : if (!RESERVED_LOCATION_P (gimple_location (last)))
1421 : break;
1422 : }
1423 :
1424 : /* Edge with goto locus might get wrong coverage info unless
1425 : it is the only edge out of BB.
1426 : Don't do that when the locuses match, so
1427 : if (blah) goto something;
1428 : is not computed twice. */
1429 27217 : if (last
1430 26323 : && gimple_has_location (last)
1431 24583 : && !RESERVED_LOCATION_P (e->goto_locus)
1432 4970 : && !single_succ_p (bb)
1433 27500 : && (LOCATION_FILE (e->goto_locus)
1434 283 : != LOCATION_FILE (gimple_location (last))
1435 279 : || (LOCATION_LINE (e->goto_locus)
1436 27217 : != LOCATION_LINE (gimple_location (last)))))
1437 : {
1438 125 : basic_block new_bb = split_edge (e);
1439 125 : edge ne = single_succ_edge (new_bb);
1440 125 : ne->goto_locus = e->goto_locus;
1441 : }
1442 27217 : if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
1443 182 : && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1444 27217 : need_exit_edge = 1;
1445 27217 : if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1446 8149 : have_exit_edge = 1;
1447 : }
1448 39498 : FOR_EACH_EDGE (e, ei, bb->preds)
1449 : {
1450 22075 : if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
1451 182 : && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
1452 22075 : need_entry_edge = 1;
1453 22075 : if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1454 3005 : have_entry_edge = 1;
1455 : }
1456 :
1457 17423 : if (need_exit_edge && !have_exit_edge)
1458 : {
1459 29 : if (dump_file)
1460 0 : fprintf (dump_file, "Adding fake exit edge to bb %i\n",
1461 : bb->index);
1462 29 : make_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), EDGE_FAKE);
1463 : }
1464 17423 : if (need_entry_edge && !have_entry_edge)
1465 : {
1466 115 : if (dump_file)
1467 0 : fprintf (dump_file, "Adding fake entry edge to bb %i\n",
1468 : bb->index);
1469 115 : make_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), bb, EDGE_FAKE);
1470 : /* Avoid bbs that have both fake entry edge and also some
1471 : exit edge. One of those edges wouldn't be added to the
1472 : spanning tree, but we can't instrument any of them. */
1473 115 : if (have_exit_edge || need_exit_edge)
1474 : {
1475 80 : gimple_stmt_iterator gsi;
1476 80 : gimple *first;
1477 :
1478 80 : gsi = gsi_start_nondebug_after_labels_bb (bb);
1479 80 : gcc_checking_assert (!gsi_end_p (gsi));
1480 80 : first = gsi_stmt (gsi);
1481 : /* Don't split the bbs containing __builtin_setjmp_receiver
1482 : or ABNORMAL_DISPATCHER calls. These are very
1483 : special and don't expect anything to be inserted before
1484 : them. */
1485 80 : if (is_gimple_call (first)
1486 80 : && (gimple_call_builtin_p (first, BUILT_IN_SETJMP_RECEIVER)
1487 76 : || (gimple_call_flags (first) & ECF_RETURNS_TWICE)
1488 39 : || (gimple_call_internal_p (first)
1489 39 : && (gimple_call_internal_fn (first)
1490 : == IFN_ABNORMAL_DISPATCHER))))
1491 76 : continue;
1492 :
1493 4 : if (dump_file)
1494 0 : fprintf (dump_file, "Splitting bb %i after labels\n",
1495 : bb->index);
1496 4 : split_block_after_labels (bb);
1497 : }
1498 : }
1499 : }
1500 : }
1501 :
1502 3012 : el = create_edge_list ();
1503 3012 : num_edges = NUM_EDGES (el);
1504 3012 : qsort (el->index_to_edge, num_edges, sizeof (edge), compare_freqs);
1505 3012 : alloc_aux_for_edges (sizeof (struct edge_profile_info));
1506 :
1507 : /* The basic blocks are expected to be numbered sequentially. */
1508 3012 : compact_blocks ();
1509 :
1510 3012 : ignored_edges = 0;
1511 36416 : for (i = 0 ; i < num_edges ; i++)
1512 : {
1513 30392 : edge e = INDEX_EDGE (el, i);
1514 :
1515 : /* Mark edges we've replaced by fake edges above as ignored. */
1516 30392 : if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
1517 182 : && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1518 182 : && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1519 : {
1520 182 : EDGE_INFO (e)->ignore = 1;
1521 182 : ignored_edges++;
1522 : }
1523 : /* Ignore edges after musttail calls. */
1524 30392 : if (cfun->has_musttail
1525 160 : && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
1526 : {
1527 140 : gimple_stmt_iterator gsi = gsi_last_nondebug_bb (e->src);
1528 140 : gimple *stmt = gsi_stmt (gsi);
1529 140 : if (stmt
1530 140 : && is_gimple_call (stmt)
1531 220 : && gimple_call_must_tail_p (as_a <const gcall *> (stmt)))
1532 : {
1533 48 : EDGE_INFO (e)->ignore = 1;
1534 48 : ignored_edges++;
1535 : }
1536 : }
1537 : }
1538 :
1539 : /* Create spanning tree from basic block graph, mark each edge that is
1540 : on the spanning tree. We insert as many abnormal and critical edges
1541 : as possible to minimize number of edge splits necessary. */
1542 :
1543 3012 : if (!thunk)
1544 3005 : find_spanning_tree (el);
1545 : else
1546 : {
1547 7 : edge e;
1548 7 : edge_iterator ei;
1549 : /* Keep only edge from entry block to be instrumented. */
1550 21 : FOR_EACH_BB_FN (bb, cfun)
1551 35 : FOR_EACH_EDGE (e, ei, bb->succs)
1552 21 : EDGE_INFO (e)->ignore = true;
1553 : }
1554 :
1555 :
1556 : /* Fake edges that are not on the tree will not be instrumented, so
1557 : mark them ignored. */
1558 33404 : for (num_instrumented = i = 0; i < num_edges; i++)
1559 : {
1560 30392 : edge e = INDEX_EDGE (el, i);
1561 30392 : struct edge_profile_info *inf = EDGE_INFO (e);
1562 :
1563 30392 : if (inf->ignore || inf->on_tree)
1564 : /*NOP*/;
1565 12718 : else if (e->flags & EDGE_FAKE)
1566 : {
1567 76 : inf->ignore = 1;
1568 76 : ignored_edges++;
1569 : }
1570 : else
1571 12642 : num_instrumented++;
1572 : }
1573 :
1574 3012 : total_num_blocks += n_basic_blocks_for_fn (cfun);
1575 3012 : if (dump_file)
1576 181 : fprintf (dump_file, "%d basic blocks\n", n_basic_blocks_for_fn (cfun));
1577 :
1578 3012 : total_num_edges += num_edges;
1579 3012 : if (dump_file)
1580 181 : fprintf (dump_file, "%d edges\n", num_edges);
1581 :
1582 3012 : total_num_edges_ignored += ignored_edges;
1583 3012 : if (dump_file)
1584 181 : fprintf (dump_file, "%d ignored edges\n", ignored_edges);
1585 :
1586 3012 : total_num_edges_instrumented += num_instrumented;
1587 3012 : if (dump_file)
1588 181 : fprintf (dump_file, "%d instrumentation edges\n", num_instrumented);
1589 :
1590 : /* Dump function body before it's instrumented.
1591 : It helps to debug gcov tool. */
1592 3012 : if (dump_file && (dump_flags & TDF_DETAILS))
1593 24 : dump_function_to_file (cfun->decl, dump_file, dump_flags);
1594 :
1595 : /* Compute two different checksums. Note that we want to compute
1596 : the checksum in only once place, since it depends on the shape
1597 : of the control flow which can change during
1598 : various transformations. */
1599 3012 : if (thunk)
1600 : {
1601 : /* At stream in time we do not have CFG, so we cannot do checksums. */
1602 : cfg_checksum = 0;
1603 : lineno_checksum = 0;
1604 : }
1605 : else
1606 : {
1607 3005 : cfg_checksum = coverage_compute_cfg_checksum (cfun);
1608 3005 : lineno_checksum = coverage_compute_lineno_checksum ();
1609 : }
1610 :
1611 3012 : const bool fn_coverage_suppressed_p = fn_in_pragma_suppress_coverage_p (cfun);
1612 :
1613 : /* Write the data from which gcov can reconstruct the basic block
1614 : graph and function line numbers (the gcno file). */
1615 3012 : output_to_file = false;
1616 3012 : if (coverage_begin_function (lineno_checksum, cfg_checksum))
1617 : {
1618 1497 : gcov_position_t offset;
1619 :
1620 : /* The condition coverage needs a deeper analysis to identify expressions
1621 : of conditions, which means it is not yet ready to write to the gcno
1622 : file. It will write its entries later, but needs to know if it do it
1623 : in the first place, which is controlled by the return value of
1624 : coverage_begin_function. */
1625 1497 : output_to_file = true;
1626 :
1627 : /* Basic block flags */
1628 1497 : offset = gcov_write_tag (GCOV_TAG_BLOCKS);
1629 1497 : gcov_write_unsigned (n_basic_blocks_for_fn (cfun));
1630 1497 : gcov_write_length (offset);
1631 :
1632 : /* Arcs */
1633 13148 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
1634 : EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
1635 : {
1636 11651 : edge e;
1637 11651 : edge_iterator ei;
1638 :
1639 11651 : offset = gcov_write_tag (GCOV_TAG_ARCS);
1640 11651 : gcov_write_unsigned (bb->index);
1641 :
1642 29407 : FOR_EACH_EDGE (e, ei, bb->succs)
1643 : {
1644 17756 : struct edge_profile_info *i = EDGE_INFO (e);
1645 17756 : if (!i->ignore)
1646 : {
1647 17539 : unsigned flag_bits = 0;
1648 :
1649 17539 : if (i->on_tree)
1650 10154 : flag_bits |= GCOV_ARC_ON_TREE;
1651 17539 : if (e->flags & EDGE_FAKE)
1652 3284 : flag_bits |= GCOV_ARC_FAKE;
1653 17539 : if (e->flags & EDGE_FALLTHRU)
1654 7905 : flag_bits |= GCOV_ARC_FALLTHROUGH;
1655 17539 : if (e->flags & EDGE_TRUE_VALUE)
1656 1798 : flag_bits |= GCOV_ARC_TRUE;
1657 17539 : if (e->flags & EDGE_FALSE_VALUE)
1658 1798 : flag_bits |= GCOV_ARC_FALSE;
1659 : /* On trees we don't have fallthru flags, but we can
1660 : recompute them from CFG shape. */
1661 17539 : if (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)
1662 3596 : && e->src->next_bb == e->dest)
1663 1781 : flag_bits |= GCOV_ARC_FALLTHROUGH;
1664 :
1665 17539 : gcov_write_unsigned (e->dest->index);
1666 17539 : gcov_write_unsigned (flag_bits);
1667 : }
1668 : }
1669 :
1670 11651 : gcov_write_length (offset);
1671 : }
1672 :
1673 : /* Disabled blocks or function. Lines, arcs, path segments through
1674 : ignored blocks should not count towards coverage. Ignoring coverage
1675 : is a matter of interpretation and does not change the instrumentation;
1676 : gcov sorts it out. If the whole function is disabled (by the
1677 : attribute on the function, not the statements), the entry block is
1678 : recorded as ignored. */
1679 1497 : if (fn_coverage_suppressed_p)
1680 : {
1681 32 : offset = gcov_write_tag (GCOV_TAG_SUPPRESS);
1682 32 : gcov_write_unsigned (ENTRY_BLOCK);
1683 32 : gcov_write_length (offset);
1684 : }
1685 1465 : else if (any_block_coverage_suppressed_p ())
1686 : {
1687 253 : offset = gcov_write_tag (GCOV_TAG_SUPPRESS);
1688 2488 : FOR_EACH_BB_FN (bb, cfun)
1689 2235 : if (coverage_suppressed_p (bb))
1690 825 : gcov_write_unsigned (bb->index);
1691 253 : gcov_write_length (offset);
1692 : }
1693 :
1694 : /* Line numbers. */
1695 : /* Initialize the output. */
1696 1497 : output_location (&streamed_locations, NULL, 0, NULL, NULL);
1697 :
1698 1497 : hash_set<location_hash> seen_locations;
1699 :
1700 11651 : FOR_EACH_BB_FN (bb, cfun)
1701 : {
1702 10154 : gimple_stmt_iterator gsi;
1703 10154 : gcov_position_t offset = 0;
1704 :
1705 10154 : if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb)
1706 : {
1707 1497 : location_t loc = DECL_SOURCE_LOCATION (current_function_decl);
1708 1497 : if (!RESERVED_LOCATION_P (loc))
1709 : {
1710 1497 : seen_locations.add (get_pure_location (loc));
1711 1497 : expanded_location curr_location = expand_location (loc);
1712 1497 : output_location (&streamed_locations, curr_location.file,
1713 1497 : MAX (1, curr_location.line), &offset, bb);
1714 : }
1715 : }
1716 :
1717 37301 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1718 : {
1719 16993 : gimple *stmt = gsi_stmt (gsi);
1720 16993 : location_t loc = gimple_location (stmt);
1721 16993 : if (!RESERVED_LOCATION_P (loc))
1722 : {
1723 14646 : seen_locations.add (get_pure_location (loc));
1724 29292 : output_location (&streamed_locations, gimple_filename (stmt),
1725 29292 : MAX (1, gimple_lineno (stmt)), &offset, bb);
1726 : }
1727 : }
1728 :
1729 : /* Notice GOTO expressions eliminated while constructing the CFG.
1730 : It's hard to distinguish such expression, but goto_locus should
1731 : not be any of already seen location. */
1732 10154 : location_t loc;
1733 10154 : if (single_succ_p (bb)
1734 5253 : && (loc = single_succ_edge (bb)->goto_locus)
1735 3607 : && !RESERVED_LOCATION_P (loc)
1736 15407 : && !seen_locations.contains (get_pure_location (loc)))
1737 : {
1738 1290 : expanded_location curr_location = expand_location (loc);
1739 1290 : output_location (&streamed_locations, curr_location.file,
1740 1290 : MAX (1, curr_location.line), &offset, bb);
1741 : }
1742 :
1743 10154 : if (offset)
1744 : {
1745 : /* A file of NULL indicates the end of run. */
1746 9572 : gcov_write_unsigned (0);
1747 9572 : gcov_write_string (NULL);
1748 9572 : gcov_write_length (offset);
1749 : }
1750 : }
1751 1497 : }
1752 :
1753 3012 : if (flag_profile_values)
1754 1023 : gimple_find_values_to_profile (&values);
1755 :
1756 3012 : if (flag_branch_probabilities)
1757 : {
1758 581 : compute_branch_probabilities (cfg_checksum, lineno_checksum);
1759 581 : if (flag_profile_values)
1760 435 : compute_value_histograms (values, cfg_checksum, lineno_checksum);
1761 : }
1762 :
1763 3012 : remove_fake_edges ();
1764 :
1765 3012 : if (condition_coverage_flag || path_coverage_flag || profile_arc_flag)
1766 2420 : gimple_init_gcov_profiler ();
1767 :
1768 3012 : if (condition_coverage_flag && !fn_coverage_suppressed_p)
1769 : {
1770 166 : struct condcov *cov = find_conditions (cfun);
1771 166 : gcc_assert (cov);
1772 166 : const size_t nconds = cov_length (cov);
1773 166 : total_num_conds += nconds;
1774 :
1775 166 : if (coverage_counter_alloc (GCOV_COUNTER_CONDS, 2 * nconds))
1776 : {
1777 166 : gcov_position_t offset {};
1778 166 : if (output_to_file)
1779 166 : offset = gcov_write_tag (GCOV_TAG_CONDS);
1780 :
1781 463 : for (size_t i = 0; i != nconds; ++i)
1782 : {
1783 297 : array_slice<basic_block> expr = cov_blocks (cov, i);
1784 297 : array_slice<uint64_t> masks = cov_masks (cov, i);
1785 297 : array_slice<sbitmap> maps = cov_maps (cov, i);
1786 297 : gcc_assert (expr.is_valid ());
1787 297 : gcc_assert (masks.is_valid ());
1788 297 : gcc_assert (maps.is_valid ());
1789 :
1790 297 : size_t terms = instrument_decisions (expr, i, maps, masks);
1791 297 : if (output_to_file)
1792 : {
1793 297 : gcov_write_unsigned (expr.front ()->index);
1794 297 : gcov_write_unsigned (terms);
1795 : }
1796 : }
1797 166 : if (output_to_file)
1798 166 : gcov_write_length (offset);
1799 : }
1800 166 : cov_free (cov);
1801 : }
1802 :
1803 : /* For each edge not on the spanning tree, add counting code. */
1804 3012 : if (profile_arc_flag
1805 3012 : && coverage_counter_alloc (GCOV_COUNTER_ARCS, num_instrumented))
1806 : {
1807 2140 : unsigned n_instrumented;
1808 :
1809 2140 : n_instrumented = instrument_edges (el);
1810 :
1811 2140 : gcc_assert (n_instrumented == num_instrumented);
1812 :
1813 2140 : if (flag_profile_values)
1814 589 : instrument_values (values);
1815 : }
1816 :
1817 3012 : unsigned instrument_prime_paths (struct function*);
1818 3012 : if (path_coverage_flag && !fn_coverage_suppressed_p)
1819 : {
1820 298 : const unsigned npaths = instrument_prime_paths (cfun);
1821 298 : if (output_to_file)
1822 : {
1823 298 : gcov_position_t offset = gcov_write_tag (GCOV_TAG_PATHS);
1824 298 : gcov_write_unsigned (npaths);
1825 298 : gcov_write_length (offset);
1826 : }
1827 : }
1828 :
1829 3012 : free_aux_for_edges ();
1830 :
1831 3012 : values.release ();
1832 3012 : free_edge_list (el);
1833 : /* Commit changes done by instrumentation. */
1834 3012 : gsi_commit_edge_inserts ();
1835 :
1836 3012 : coverage_end_function (lineno_checksum, cfg_checksum);
1837 3012 : if (flag_branch_probabilities
1838 581 : && (profile_status_for_fn (cfun) == PROFILE_READ))
1839 : {
1840 497 : if (dump_file && (dump_flags & TDF_DETAILS))
1841 12 : report_predictor_hitrates ();
1842 497 : sreal nit;
1843 497 : bool reliable;
1844 :
1845 : /* At this moment we have precise loop iteration count estimates.
1846 : Record them to loop structure before the profile gets out of date. */
1847 1695 : for (auto loop : loops_list (cfun, 0))
1848 233 : if (loop->header->count.ipa ().nonzero_p ()
1849 175 : && expected_loop_iterations_by_profile (loop, &nit, &reliable)
1850 175 : && reliable)
1851 : {
1852 175 : widest_int bound = nit.to_nearest_int ();
1853 175 : loop->any_estimate = false;
1854 175 : record_niter_bound (loop, bound, true, false);
1855 175 : }
1856 497 : compute_function_frequency ();
1857 : }
1858 3012 : }
1859 :
1860 : /* Union find algorithm implementation for the basic blocks using
1861 : aux fields. */
1862 :
1863 : static basic_block
1864 97226 : find_group (basic_block bb)
1865 : {
1866 97226 : basic_block group = bb, bb1;
1867 :
1868 158372 : while ((basic_block) group->aux != group)
1869 : group = (basic_block) group->aux;
1870 :
1871 : /* Compress path. */
1872 123693 : while ((basic_block) bb->aux != group)
1873 : {
1874 6039 : bb1 = (basic_block) bb->aux;
1875 6039 : bb->aux = (void *) group;
1876 6039 : bb = bb1;
1877 : }
1878 97226 : return group;
1879 : }
1880 :
1881 : static void
1882 20428 : union_groups (basic_block bb1, basic_block bb2)
1883 : {
1884 20428 : basic_block bb1g = find_group (bb1);
1885 35442 : basic_block bb2g = find_group (bb2);
1886 :
1887 : /* ??? I don't have a place for the rank field. OK. Lets go w/o it,
1888 : this code is unlikely going to be performance problem anyway. */
1889 20428 : gcc_assert (bb1g != bb2g);
1890 :
1891 20428 : bb1g->aux = bb2g;
1892 20428 : }
1893 :
1894 : /* This function searches all of the edges in the program flow graph, and puts
1895 : as many bad edges as possible onto the spanning tree. Bad edges include
1896 : abnormals edges, which can't be instrumented at the moment. Since it is
1897 : possible for fake edges to form a cycle, we will have to develop some
1898 : better way in the future. Also put critical edges to the tree, since they
1899 : are more expensive to instrument. */
1900 :
1901 : static void
1902 3005 : find_spanning_tree (struct edge_list *el)
1903 : {
1904 3005 : int i;
1905 3005 : int num_edges = NUM_EDGES (el);
1906 3005 : basic_block bb;
1907 :
1908 : /* We use aux field for standard union-find algorithm. */
1909 26438 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
1910 23433 : bb->aux = bb;
1911 :
1912 : /* Add fake edge exit to entry we can't instrument. */
1913 3005 : union_groups (EXIT_BLOCK_PTR_FOR_FN (cfun), ENTRY_BLOCK_PTR_FOR_FN (cfun));
1914 :
1915 : /* First add all abnormal edges to the tree unless they form a cycle. Also
1916 : add all edges to the exit block to avoid inserting profiling code behind
1917 : setting return value from function. */
1918 36374 : for (i = 0; i < num_edges; i++)
1919 : {
1920 30364 : edge e = INDEX_EDGE (el, i);
1921 30364 : if (((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_FAKE))
1922 24803 : || e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1923 8471 : && !EDGE_INFO (e)->ignore
1924 55159 : && (find_group (e->src) != find_group (e->dest)))
1925 : {
1926 8189 : if (dump_file)
1927 330 : fprintf (dump_file, "Abnormal edge %d to %d put to tree\n",
1928 : e->src->index, e->dest->index);
1929 8189 : EDGE_INFO (e)->on_tree = 1;
1930 8189 : union_groups (e->src, e->dest);
1931 : }
1932 : }
1933 :
1934 : /* And now the rest. Edge list is sorted according to frequencies and
1935 : thus we will produce minimal spanning tree. */
1936 33369 : for (i = 0; i < num_edges; i++)
1937 : {
1938 30364 : edge e = INDEX_EDGE (el, i);
1939 30364 : if (!EDGE_INFO (e)->ignore
1940 90632 : && find_group (e->src) != find_group (e->dest))
1941 : {
1942 9234 : if (dump_file)
1943 302 : fprintf (dump_file, "Normal edge %d to %d put to tree\n",
1944 : e->src->index, e->dest->index);
1945 9234 : EDGE_INFO (e)->on_tree = 1;
1946 9234 : union_groups (e->src, e->dest);
1947 : }
1948 : }
1949 :
1950 3005 : clear_aux_for_blocks ();
1951 3005 : }
1952 :
1953 : /* Perform file-level initialization for branch-prob processing. */
1954 :
1955 : void
1956 0 : init_branch_prob (void)
1957 : {
1958 0 : int i;
1959 :
1960 0 : total_num_blocks = 0;
1961 0 : total_num_edges = 0;
1962 0 : total_num_edges_ignored = 0;
1963 0 : total_num_edges_instrumented = 0;
1964 0 : total_num_blocks_created = 0;
1965 0 : total_num_passes = 0;
1966 0 : total_num_times_called = 0;
1967 0 : total_num_branches = 0;
1968 0 : total_num_conds = 0;
1969 0 : for (i = 0; i < 20; i++)
1970 0 : total_hist_br_prob[i] = 0;
1971 0 : }
1972 :
1973 : /* Performs file-level cleanup after branch-prob processing
1974 : is completed. */
1975 :
1976 : void
1977 630 : end_branch_prob (void)
1978 : {
1979 630 : if (dump_file)
1980 : {
1981 48 : fprintf (dump_file, "\n");
1982 48 : fprintf (dump_file, "Total number of blocks: %d\n",
1983 : total_num_blocks);
1984 48 : fprintf (dump_file, "Total number of edges: %d\n", total_num_edges);
1985 48 : fprintf (dump_file, "Total number of ignored edges: %d\n",
1986 : total_num_edges_ignored);
1987 48 : fprintf (dump_file, "Total number of instrumented edges: %d\n",
1988 : total_num_edges_instrumented);
1989 48 : fprintf (dump_file, "Total number of blocks created: %d\n",
1990 : total_num_blocks_created);
1991 48 : fprintf (dump_file, "Total number of graph solution passes: %d\n",
1992 : total_num_passes);
1993 48 : if (total_num_times_called != 0)
1994 48 : fprintf (dump_file, "Average number of graph solution passes: %d\n",
1995 48 : (total_num_passes + (total_num_times_called >> 1))
1996 : / total_num_times_called);
1997 48 : fprintf (dump_file, "Total number of branches: %d\n",
1998 : total_num_branches);
1999 48 : if (total_num_branches)
2000 : {
2001 : int i;
2002 :
2003 220 : for (i = 0; i < 10; i++)
2004 200 : fprintf (dump_file, "%d%% branches in range %d-%d%%\n",
2005 200 : (total_hist_br_prob[i] + total_hist_br_prob[19-i]) * 100
2006 200 : / total_num_branches, 5*i, 5*i+5);
2007 : }
2008 48 : fprintf (dump_file, "Total number of conditions: %d\n",
2009 : total_num_conds);
2010 48 : if (afdo_fdo_records.length ())
2011 : {
2012 0 : profile_count fdo_sum = profile_count::zero ();
2013 0 : profile_count afdo_sum = profile_count::zero ();
2014 0 : for (const auto &r : afdo_fdo_records)
2015 0 : for (const auto &b : r.bbs)
2016 0 : if (b.fdo.initialized_p () && b.afdo.initialized_p ())
2017 : {
2018 0 : fdo_sum += b.fdo;
2019 0 : afdo_sum += b.afdo;
2020 : }
2021 0 : for (auto &r : afdo_fdo_records)
2022 : {
2023 0 : for (auto &b : r.bbs)
2024 0 : if (b.fdo.initialized_p () && b.afdo.initialized_p ())
2025 : {
2026 0 : fprintf (dump_file, "%s bb %i fdo %" PRIu64 " (%s) afdo ",
2027 0 : r.node->dump_name (), b.index,
2028 0 : (int64_t)b.fdo.to_gcov_type (),
2029 : maybe_hot_count_p
2030 0 : (NULL, b.fdo.apply_scale (1, 1000))
2031 : ? "very hot"
2032 0 : : maybe_hot_count_p (NULL, b.fdo)
2033 0 : ? "hot" : "cold");
2034 0 : b.afdo.dump (dump_file);
2035 0 : fprintf (dump_file, " (%s) ",
2036 : maybe_hot_afdo_count_p
2037 0 : (b.afdo.apply_scale (1, 1000))
2038 : ? "very hot"
2039 0 : : maybe_hot_afdo_count_p (b.afdo)
2040 0 : ? "hot" : "cold");
2041 0 : if (afdo_sum.nonzero_p ())
2042 : {
2043 0 : profile_count scaled
2044 0 : = b.afdo.apply_scale (fdo_sum, afdo_sum);
2045 0 : fprintf (dump_file, "scaled %" PRIu64,
2046 : scaled.to_gcov_type ());
2047 0 : if (b.fdo.to_gcov_type ())
2048 0 : fprintf (dump_file, " diff %" PRId64 ", %+2.2f%%",
2049 : scaled.to_gcov_type ()
2050 : - b.fdo.to_gcov_type (),
2051 0 : (scaled.to_gcov_type ()
2052 0 : - b.fdo.to_gcov_type ()) * 100.0
2053 : / b.fdo.to_gcov_type ());
2054 : }
2055 0 : fprintf (dump_file, "\n preds");
2056 0 : for (int val : b.preds)
2057 0 : fprintf (dump_file, " %i", val);
2058 0 : b.preds.release ();
2059 0 : fprintf (dump_file, "\n succs");
2060 0 : for (int val : b.succs)
2061 0 : fprintf (dump_file, " %i", val);
2062 0 : b.succs.release ();
2063 0 : fprintf (dump_file, "\n");
2064 : }
2065 0 : r.bbs.release ();
2066 : }
2067 : }
2068 48 : afdo_fdo_records.release ();
2069 : }
2070 630 : }
2071 :
2072 : /* Return true if any cfg coverage/profiling is enabled; -fprofile-arcs
2073 : -fcondition-coverage -fpath-coverage. */
2074 101342403 : bool coverage_instrumentation_p ()
2075 : {
2076 101342403 : return profile_arc_flag || condition_coverage_flag || path_coverage_flag;
2077 : }
|
