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 2150 : instrument_edges (struct edge_list *el)
150 : {
151 2150 : unsigned num_instr_edges = 0;
152 2150 : int num_edges = NUM_EDGES (el);
153 2150 : basic_block bb;
154 :
155 18395 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
156 : {
157 16245 : edge e;
158 16245 : edge_iterator ei;
159 :
160 32859 : FOR_EACH_EDGE (e, ei, bb->succs)
161 : {
162 16614 : struct edge_profile_info *inf = EDGE_INFO (e);
163 :
164 16614 : if (!inf->ignore && !inf->on_tree)
165 : {
166 8634 : gcc_assert (!(e->flags & EDGE_ABNORMAL));
167 8634 : if (dump_file)
168 699 : fprintf (dump_file, "Edge %d to %d instrumented%s\n",
169 233 : e->src->index, e->dest->index,
170 464 : EDGE_CRITICAL_P (e) ? " (and split)" : "");
171 8634 : gimple_gen_edge_profiler (num_instr_edges++, e);
172 : }
173 : }
174 : }
175 :
176 2150 : total_num_blocks_created += num_edges;
177 2150 : if (dump_file)
178 90 : fprintf (dump_file, "%d edges instrumented\n", num_instr_edges);
179 2150 : return num_instr_edges;
180 : }
181 :
182 : /* Add code to measure histograms for values in list VALUES. */
183 : static void
184 592 : instrument_values (histogram_values values)
185 : {
186 592 : unsigned i;
187 :
188 : /* Emit code to generate the histograms before the insns. */
189 :
190 1380 : for (i = 0; i < values.length (); i++)
191 : {
192 788 : histogram_value hist = values[i];
193 788 : unsigned t = COUNTER_FOR_HIST_TYPE (hist->type);
194 :
195 788 : if (!coverage_counter_alloc (t, hist->n_counters))
196 0 : continue;
197 :
198 788 : 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 50 : case HIST_TYPE_INDIR_CALL:
213 50 : gimple_gen_ic_profiler (hist, t);
214 50 : 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 592 : case HIST_TYPE_TIME_PROFILE:
225 592 : gimple_gen_time_profiler (t);
226 592 : break;
227 :
228 0 : default:
229 0 : gcc_unreachable ();
230 : }
231 : }
232 592 : }
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 579 : get_exec_counts (unsigned cfg_checksum, unsigned lineno_checksum)
241 : {
242 579 : unsigned num_edges = 0;
243 579 : basic_block bb;
244 579 : gcov_type *counts;
245 :
246 : /* Count the edges to be (possibly) instrumented. */
247 4610 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
248 : {
249 4031 : edge e;
250 4031 : edge_iterator ei;
251 :
252 8996 : FOR_EACH_EDGE (e, ei, bb->succs)
253 4965 : if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree)
254 2075 : num_edges++;
255 : }
256 :
257 579 : counts = get_coverage_counts (GCOV_COUNTER_ARCS, cfg_checksum,
258 : lineno_checksum, num_edges);
259 579 : if (!counts)
260 : return NULL;
261 :
262 : return counts;
263 : }
264 :
265 : static bool
266 5012 : is_edge_inconsistent (vec<edge, va_gc> *edges)
267 : {
268 5012 : edge e;
269 5012 : edge_iterator ei;
270 12039 : FOR_EACH_EDGE (e, ei, edges)
271 : {
272 7027 : if (!EDGE_INFO (e)->ignore)
273 : {
274 6995 : if (edge_gcov_count (e) < 0
275 6995 : && (!(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 501 : is_inconsistent (void)
314 : {
315 501 : basic_block bb;
316 501 : bool inconsistent = false;
317 3007 : FOR_EACH_BB_FN (bb, cfun)
318 : {
319 2506 : inconsistent |= is_edge_inconsistent (bb->preds);
320 2506 : if (!dump_file && inconsistent)
321 : return true;
322 2506 : inconsistent |= is_edge_inconsistent (bb->succs);
323 2506 : if (!dump_file && inconsistent)
324 : return true;
325 2506 : 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 2506 : 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 2506 : 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 2506 : 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 501 : read_profile_edge_counts (gcov_type *exec_counts)
387 : {
388 501 : basic_block bb;
389 501 : int num_edges = 0;
390 501 : 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 4009 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
397 : {
398 3508 : edge e;
399 3508 : edge_iterator ei;
400 :
401 7821 : FOR_EACH_EDGE (e, ei, bb->succs)
402 4313 : if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree)
403 : {
404 1790 : num_edges++;
405 1790 : if (exec_counts)
406 1783 : edge_gcov_count (e) = exec_counts[exec_counts_pos++];
407 : else
408 7 : edge_gcov_count (e) = 0;
409 :
410 1790 : EDGE_INFO (e)->count_valid = 1;
411 1790 : BB_INFO (bb)->succ_count--;
412 1790 : BB_INFO (e->dest)->pred_count--;
413 1790 : if (dump_file)
414 : {
415 235 : fprintf (dump_file, "\nRead edge from %i to %i, count:",
416 : bb->index, e->dest->index);
417 235 : fprintf (dump_file, "%" PRId64,
418 235 : (int64_t) edge_gcov_count (e));
419 : }
420 : }
421 : }
422 :
423 501 : 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 579 : compute_branch_probabilities (unsigned cfg_checksum, unsigned lineno_checksum)
458 : {
459 579 : basic_block bb;
460 579 : int i;
461 579 : int num_edges = 0;
462 579 : int changes;
463 579 : int passes;
464 579 : int hist_br_prob[20];
465 579 : int num_branches;
466 579 : gcov_type *exec_counts = get_exec_counts (cfg_checksum, lineno_checksum);
467 579 : int inconsistent = 0;
468 :
469 : /* Very simple sanity checks so we catch bugs in our profiling code. */
470 579 : if (!profile_info)
471 : {
472 78 : if (dump_file)
473 0 : fprintf (dump_file, "Profile info is missing; giving up\n");
474 78 : return;
475 : }
476 :
477 501 : bb_gcov_counts.safe_grow_cleared (last_basic_block_for_fn (cfun), true);
478 501 : edge_gcov_counts = new hash_map<edge,gcov_type>;
479 :
480 : /* Attach extra info block to each bb. */
481 501 : alloc_aux_for_blocks (sizeof (struct bb_profile_info));
482 4009 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
483 : {
484 3508 : edge e;
485 3508 : edge_iterator ei;
486 :
487 7821 : FOR_EACH_EDGE (e, ei, bb->succs)
488 4313 : if (!EDGE_INFO (e)->ignore)
489 4296 : BB_INFO (bb)->succ_count++;
490 7821 : FOR_EACH_EDGE (e, ei, bb->preds)
491 4313 : if (!EDGE_INFO (e)->ignore)
492 4296 : BB_INFO (bb)->pred_count++;
493 : }
494 :
495 : /* Avoid predicting entry on exit nodes. */
496 501 : BB_INFO (EXIT_BLOCK_PTR_FOR_FN (cfun))->succ_count = 2;
497 501 : BB_INFO (ENTRY_BLOCK_PTR_FOR_FN (cfun))->pred_count = 2;
498 :
499 501 : afdo_fdo_record record = {cgraph_node::get (current_function_decl), vNULL};;
500 501 : 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 501 : num_edges = read_profile_edge_counts (exec_counts);
516 :
517 501 : 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 501 : changes = 1;
538 501 : passes = 0;
539 2584 : while (changes)
540 : {
541 2083 : passes++;
542 2083 : changes = 0;
543 19629 : FOR_BB_BETWEEN (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), NULL, prev_bb)
544 : {
545 17546 : struct bb_profile_info *bi = BB_INFO (bb);
546 17546 : if (! bi->count_valid)
547 : {
548 6219 : if (bi->succ_count == 0)
549 : {
550 830 : edge e;
551 830 : edge_iterator ei;
552 830 : gcov_type total = 0;
553 :
554 1892 : FOR_EACH_EDGE (e, ei, bb->succs)
555 1062 : total += edge_gcov_count (e);
556 830 : bb_gcov_count (bb) = total;
557 830 : bi->count_valid = 1;
558 830 : changes = 1;
559 : }
560 5389 : else if (bi->pred_count == 0)
561 : {
562 2678 : edge e;
563 2678 : edge_iterator ei;
564 2678 : gcov_type total = 0;
565 :
566 6532 : FOR_EACH_EDGE (e, ei, bb->preds)
567 3854 : total += edge_gcov_count (e);
568 2678 : bb_gcov_count (bb) = total;
569 2678 : bi->count_valid = 1;
570 2678 : changes = 1;
571 : }
572 : }
573 17546 : if (bi->count_valid)
574 : {
575 14835 : if (bi->succ_count == 1)
576 : {
577 2177 : edge e;
578 2177 : edge_iterator ei;
579 2177 : 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 5428 : FOR_EACH_EDGE (e, ei, bb->succs)
584 3251 : total += edge_gcov_count (e);
585 :
586 : /* Search for the invalid edge, and set its count. */
587 3085 : FOR_EACH_EDGE (e, ei, bb->succs)
588 3085 : if (! EDGE_INFO (e)->count_valid && ! EDGE_INFO (e)->ignore)
589 : break;
590 :
591 : /* Calculate count for remaining edge by conservation. */
592 2177 : total = bb_gcov_count (bb) - total;
593 :
594 2177 : gcc_assert (e);
595 2177 : EDGE_INFO (e)->count_valid = 1;
596 2177 : edge_gcov_count (e) = total;
597 2177 : bi->succ_count--;
598 :
599 2177 : BB_INFO (e->dest)->pred_count--;
600 2177 : changes = 1;
601 : }
602 14835 : if (bi->pred_count == 1)
603 : {
604 329 : edge e;
605 329 : edge_iterator ei;
606 329 : 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 788 : FOR_EACH_EDGE (e, ei, bb->preds)
611 459 : total += edge_gcov_count (e);
612 :
613 : /* Search for the invalid edge, and set its count. */
614 387 : FOR_EACH_EDGE (e, ei, bb->preds)
615 387 : if (!EDGE_INFO (e)->count_valid && !EDGE_INFO (e)->ignore)
616 : break;
617 :
618 : /* Calculate count for remaining edge by conservation. */
619 329 : total = bb_gcov_count (bb) - total + edge_gcov_count (e);
620 :
621 329 : gcc_assert (e);
622 329 : EDGE_INFO (e)->count_valid = 1;
623 329 : edge_gcov_count (e) = total;
624 329 : bi->pred_count--;
625 :
626 329 : BB_INFO (e->src)->succ_count--;
627 329 : changes = 1;
628 : }
629 : }
630 : }
631 : }
632 :
633 501 : total_num_passes += passes;
634 501 : 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 3007 : FOR_EACH_BB_FN (bb, cfun)
640 : {
641 2506 : gcc_assert (!BB_INFO (bb)->succ_count && !BB_INFO (bb)->pred_count);
642 : }
643 :
644 : /* Check for inconsistent basic block counts */
645 501 : inconsistent = is_inconsistent ();
646 :
647 501 : 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 10521 : for (i = 0; i < 20; i++)
675 10020 : hist_br_prob[i] = 0;
676 501 : num_branches = 0;
677 :
678 4009 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
679 : {
680 3508 : edge e;
681 3508 : edge_iterator ei;
682 :
683 3508 : 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 7821 : 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 4313 : if ((edge_gcov_count (e) < 0
697 1 : && e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
698 4313 : || (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 4313 : if (edge_gcov_count (e) < 0
706 4313 : || 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 3508 : if (bb_gcov_count (bb))
715 : {
716 2525 : bool set_to_guessed = false;
717 5713 : FOR_EACH_EDGE (e, ei, bb->succs)
718 : {
719 3188 : bool prev_never = e->probability == profile_probability::never ();
720 3188 : e->probability = profile_probability::probability_in_gcov_type
721 3188 : (edge_gcov_count (e), bb_gcov_count (bb));
722 3908 : if (e->probability == profile_probability::never ()
723 720 : && !prev_never
724 3768 : && flag_profile_partial_training)
725 0 : set_to_guessed = true;
726 : }
727 2525 : if (set_to_guessed)
728 0 : FOR_EACH_EDGE (e, ei, bb->succs)
729 0 : e->probability = e->probability.guessed ();
730 2525 : if (bb->index >= NUM_FIXED_BLOCKS
731 1789 : && block_ends_with_condjump_p (bb)
732 3008 : && EDGE_COUNT (bb->succs) >= 2)
733 : {
734 483 : int prob;
735 483 : edge e;
736 483 : int index;
737 :
738 : /* Find the branch edge. It is possible that we do have fake
739 : edges here. */
740 483 : FOR_EACH_EDGE (e, ei, bb->succs)
741 483 : if (!(e->flags & (EDGE_FAKE | EDGE_FALLTHRU)))
742 : break;
743 :
744 483 : prob = e->probability.to_reg_br_prob_base ();
745 483 : index = prob * 20 / REG_BR_PROB_BASE;
746 :
747 483 : if (index == 20)
748 56 : index = 19;
749 483 : hist_br_prob[index]++;
750 :
751 483 : 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 983 : 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 3524 : && EDGE_COUNT (bb->succs) >= 2)
784 0 : num_branches++;
785 : }
786 : }
787 :
788 501 : if (exec_counts
789 501 : && (bb_gcov_count (ENTRY_BLOCK_PTR_FOR_FN (cfun))
790 131 : || !flag_profile_partial_training))
791 499 : profile_status_for_fn (cfun) = PROFILE_READ;
792 :
793 : /* If we have real data, use them! */
794 501 : if (bb_gcov_count (ENTRY_BLOCK_PTR_FOR_FN (cfun))
795 501 : || !flag_guess_branch_prob)
796 : {
797 368 : profile_count old_entry_cnt = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count;
798 368 : auto_vec <bb_stats> stats;
799 368 : double sum1 = 0, sum2 = 0;
800 :
801 3122 : FOR_ALL_BB_FN (bb, cfun)
802 : {
803 2754 : profile_count cnt = bb->count;
804 2754 : if (bb_gcov_count (bb) || !flag_profile_partial_training)
805 2754 : bb->count = profile_count::from_gcov_type (bb_gcov_count (bb));
806 : else
807 0 : bb->count = profile_count::guessed_zero ();
808 :
809 2754 : 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 368 : 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 368 : }
843 : /* If function was not trained, preserve local estimates including statically
844 : determined zero counts. */
845 133 : else if (profile_status_for_fn (cfun) == PROFILE_READ
846 131 : && !flag_profile_partial_training)
847 874 : FOR_ALL_BB_FN (bb, cfun)
848 750 : if (!(bb->count == profile_count::zero ()))
849 736 : bb->count = bb->count.global0 ();
850 :
851 501 : bb_gcov_counts.release ();
852 1002 : delete edge_gcov_counts;
853 501 : edge_gcov_counts = NULL;
854 :
855 501 : 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 501 : update_max_bb_count ();
868 :
869 501 : 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 501 : free_aux_for_blocks ();
894 : }
895 :
896 : /* Sort the histogram value and count for TOPN and INDIR_CALL type. */
897 :
898 : static void
899 84 : sort_hist_values (histogram_value hist)
900 : {
901 84 : gcc_assert (hist->type == HIST_TYPE_TOPN_VALUES
902 : || hist->type == HIST_TYPE_INDIR_CALL);
903 :
904 84 : int counters = hist->hvalue.counters[1];
905 127 : 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 615 : for (int j = 0; j < counters - 1 - i; j++)
915 : {
916 545 : gcov_type *p = &hist->hvalue.counters[2 * j + 2];
917 545 : if (p[1] < p[3] || (p[1] == p[3] && p[0] < p[2]))
918 : {
919 484 : std::swap (p[0], p[2]);
920 484 : std::swap (p[1], p[3]);
921 484 : swapped = true;
922 : }
923 : }
924 70 : if (!swapped)
925 : break;
926 : }
927 84 : }
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 433 : compute_value_histograms (histogram_values values, unsigned cfg_checksum,
935 : unsigned lineno_checksum)
936 : {
937 433 : unsigned i, j, t, any;
938 433 : unsigned n_histogram_counters[GCOV_N_VALUE_COUNTERS];
939 433 : gcov_type *histogram_counts[GCOV_N_VALUE_COUNTERS];
940 433 : gcov_type *act_count[GCOV_N_VALUE_COUNTERS];
941 433 : gcov_type *aact_count;
942 433 : struct cgraph_node *node;
943 :
944 4330 : for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++)
945 3897 : n_histogram_counters[t] = 0;
946 :
947 2130 : for (i = 0; i < values.length (); i++)
948 : {
949 632 : histogram_value hist = values[i];
950 632 : n_histogram_counters[(int) hist->type] += hist->n_counters;
951 : }
952 :
953 : any = 0;
954 4330 : for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++)
955 : {
956 3897 : if (!n_histogram_counters[t])
957 : {
958 3278 : histogram_counts[t] = NULL;
959 3278 : continue;
960 : }
961 :
962 619 : histogram_counts[t] = get_coverage_counts (COUNTER_FOR_HIST_TYPE (t),
963 : cfg_checksum,
964 : lineno_checksum,
965 : n_histogram_counters[t]);
966 619 : if (histogram_counts[t])
967 495 : any = 1;
968 619 : act_count[t] = histogram_counts[t];
969 : }
970 433 : if (!any)
971 94 : return;
972 :
973 1676 : for (i = 0; i < values.length (); i++)
974 : {
975 499 : histogram_value hist = values[i];
976 499 : gimple *stmt = hist->hvalue.stmt;
977 :
978 499 : t = (int) hist->type;
979 499 : bool topn_p = (hist->type == HIST_TYPE_TOPN_VALUES
980 499 : || hist->type == HIST_TYPE_INDIR_CALL);
981 :
982 : /* TOP N counter uses variable number of counters. */
983 499 : if (topn_p)
984 : {
985 84 : unsigned total_size;
986 84 : if (act_count[t])
987 84 : total_size = 2 + 2 * act_count[t][1];
988 : else
989 : total_size = 2;
990 84 : gimple_add_histogram_value (cfun, stmt, hist);
991 84 : hist->n_counters = total_size;
992 84 : hist->hvalue.counters = XNEWVEC (gcov_type, hist->n_counters);
993 548 : for (j = 0; j < hist->n_counters; j++)
994 464 : if (act_count[t])
995 464 : hist->hvalue.counters[j] = act_count[t][j];
996 : else
997 0 : hist->hvalue.counters[j] = 0;
998 84 : act_count[t] += hist->n_counters;
999 84 : sort_hist_values (hist);
1000 : }
1001 : else
1002 : {
1003 415 : aact_count = act_count[t];
1004 :
1005 415 : if (act_count[t])
1006 415 : act_count[t] += hist->n_counters;
1007 :
1008 415 : gimple_add_histogram_value (cfun, stmt, hist);
1009 415 : hist->hvalue.counters = XNEWVEC (gcov_type, hist->n_counters);
1010 883 : for (j = 0; j < hist->n_counters; j++)
1011 468 : if (aact_count)
1012 468 : 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 499 : if (hist->type == HIST_TYPE_TIME_PROFILE)
1021 : {
1022 339 : node = cgraph_node::get (hist->fun->decl);
1023 339 : if (hist->hvalue.counters[0] >= 0
1024 339 : && hist->hvalue.counters[0] < INT_MAX / 2)
1025 339 : 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 339 : bool drop
1035 339 : = (flag_profile_reproducible == PROFILE_REPRODUCIBILITY_MULTITHREADED);
1036 339 : if (drop)
1037 0 : node->tp_first_run = 0;
1038 :
1039 339 : 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 3390 : for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++)
1047 3051 : 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 87531 : hash (const location_triplet &ref)
1067 : {
1068 87531 : inchash::hash hstate (0);
1069 87531 : if (ref.filename)
1070 85353 : hstate.add_int (strlen (ref.filename));
1071 87531 : hstate.add_int (ref.lineno);
1072 87531 : hstate.add_int (ref.bb_index);
1073 87531 : return hstate.end ();
1074 : }
1075 :
1076 : static bool
1077 76186 : equal (const location_triplet &ref1, const location_triplet &ref2)
1078 : {
1079 76186 : return ref1.lineno == ref2.lineno
1080 10204 : && ref1.bb_index == ref2.bb_index
1081 5090 : && ref1.filename != NULL
1082 5090 : && ref2.filename != NULL
1083 81276 : && 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 59302 : mark_empty (location_triplet &ref)
1096 : {
1097 59302 : ref.lineno = -2;
1098 : }
1099 :
1100 : static bool
1101 100888 : is_deleted (const location_triplet &ref)
1102 : {
1103 100888 : return ref.lineno == -1;
1104 : }
1105 :
1106 : static bool
1107 450318 : is_empty (const location_triplet &ref)
1108 : {
1109 436397 : 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 19007 : 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 19007 : static char const *prev_file_name;
1125 19007 : static int prev_line;
1126 19007 : bool name_differs, line_differs;
1127 :
1128 19007 : if (file_name != NULL)
1129 17500 : file_name = remap_profile_filename (file_name);
1130 :
1131 19007 : location_triplet triplet;
1132 19007 : triplet.filename = file_name;
1133 19007 : triplet.lineno = line;
1134 19007 : triplet.bb_index = bb ? bb->index : 0;
1135 :
1136 19007 : if (streamed_locations->add (triplet))
1137 6593 : return;
1138 :
1139 13921 : if (!file_name)
1140 : {
1141 1507 : prev_file_name = NULL;
1142 1507 : prev_line = -1;
1143 1507 : return;
1144 : }
1145 :
1146 12414 : name_differs = !prev_file_name || filename_cmp (file_name, prev_file_name);
1147 12414 : line_differs = prev_line != line;
1148 :
1149 12414 : if (!*offset)
1150 : {
1151 9620 : *offset = gcov_write_tag (GCOV_TAG_LINES);
1152 9620 : gcov_write_unsigned (bb->index);
1153 9620 : 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 12414 : if (name_differs)
1159 : {
1160 9705 : prev_file_name = file_name;
1161 9705 : gcov_write_unsigned (0);
1162 9705 : gcov_write_filename (prev_file_name);
1163 : }
1164 12414 : if (line_differs)
1165 : {
1166 12411 : gcov_write_unsigned (line);
1167 12411 : 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 603726 : compare_freqs (const void *p1, const void *p2)
1175 : {
1176 603726 : const_edge e1 = *(const const_edge *)p1;
1177 603726 : 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 603726 : int m1 = EDGE_CRITICAL_P (e1) ? 2 : 1;
1182 603726 : int m2 = EDGE_CRITICAL_P (e2) ? 2 : 1;
1183 :
1184 603726 : if (EDGE_FREQUENCY (e1) * m1 + m1 != EDGE_FREQUENCY (e2) * m2 + m2)
1185 207697 : return EDGE_FREQUENCY (e2) * m2 + m2 - EDGE_FREQUENCY (e1) * m1 - m1;
1186 : /* Stabilize sort. */
1187 396029 : if (e1->src->index != e2->src->index)
1188 361752 : return e2->src->index - e1->src->index;
1189 34277 : 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 2330 : suppress_coverage (basic_block bb)
1213 : {
1214 2330 : bb->flags |= BB_COVERAGE_SUPPRESSED;
1215 2330 : }
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 213320454 : coverage_suppressed_p (basic_block bb)
1228 : {
1229 213320454 : 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 1475 : any_block_coverage_suppressed_p ()
1236 : {
1237 1475 : basic_block bb;
1238 9820 : FOR_EACH_BB_FN (bb, cfun)
1239 8600 : 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. A new range is always
1251 : created, even if the previous one was left open. */
1252 : void
1253 357 : suppress_coverage_begin (location_t loc)
1254 : {
1255 357 : loc = get_pure_location (expansion_point_location (loc));
1256 357 : source_range range = source_range::from_locations (loc, UNKNOWN_LOCATION);
1257 357 : suppress_coverage_ranges.safe_push (range);
1258 357 : }
1259 :
1260 : /* Try to close the last open range created by suppress_coverage_begin at LOC.
1261 : If all ranges have been closed already (or never opened), this is a no-op.
1262 : Returns true if a range was closed. */
1263 : bool
1264 359 : suppress_coverage_end (location_t loc)
1265 : {
1266 359 : if (suppress_coverage_ranges.is_empty ())
1267 : return false;
1268 :
1269 358 : source_range *current = nullptr;
1270 720 : for (int i = suppress_coverage_ranges.length () - 1; !current && i >= 0; i--)
1271 362 : if (suppress_coverage_ranges[i].m_finish == UNKNOWN_LOCATION)
1272 357 : current = &suppress_coverage_ranges[i];
1273 :
1274 358 : if (!current)
1275 : return false;
1276 :
1277 357 : loc = get_pure_location (expansion_point_location (loc));
1278 357 : current->m_finish = loc;
1279 357 : return true;
1280 : }
1281 :
1282 : /* Check if STMT is anchored to a line of code in a range disabled by #pragma
1283 : GCC suppress_coverage begin/end. This function always returns false if
1284 : coverage is disabled as it is the faster check, and nothing should be
1285 : suppressed anyway.
1286 :
1287 : If STMT is at an UNKNOWN_LOCATION or ADHOC_LOC, this function returns PREV.
1288 : This is probably a compiler-generated statement that should inherit the
1289 : disabled state of the previous statement since it is really tied to it, and
1290 : there is no opportunity for a #pragma in-between. */
1291 : bool
1292 97104368 : in_pragma_suppress_coverage_p (gimple* stmt, bool prev)
1293 : {
1294 97104368 : if (!coverage_instrumentation_p ())
1295 : return false;
1296 :
1297 53293 : location_t loc = expansion_point_location (gimple_location (stmt));
1298 53293 : if (loc == UNKNOWN_LOCATION || IS_ADHOC_LOC (loc))
1299 : return prev;
1300 :
1301 39755 : return location_in_pragma_suppress_coverage_p (loc);
1302 : }
1303 :
1304 : /* Check if LOC is within a #pragma GCC suppress_coverage block. */
1305 : bool
1306 3049908 : location_in_pragma_suppress_coverage_p (location_t loc)
1307 : {
1308 3049908 : loc = get_pure_location (expansion_point_location (loc));
1309 3307122 : for (const source_range& dl : suppress_coverage_ranges)
1310 246670 : if (linemap_location_before_p (line_table, dl.m_start, loc)
1311 246670 : && (linemap_location_before_p (line_table, loc, dl.m_finish)
1312 148116 : || dl.m_finish == UNKNOWN_LOCATION))
1313 : return true;
1314 : return false;
1315 : }
1316 :
1317 : /* Check if FN is fully between #pragma GCC suppress_coverage begin/end. In
1318 : that case we can disable the whole function rather than every block, and
1319 : omit MC/DC (-fcondition-coverage) and prime path coverage (-fpath-coverage)
1320 : instrumentation. */
1321 : static bool
1322 3024 : fn_in_pragma_suppress_coverage_p (function *fn)
1323 : {
1324 3024 : if (!coverage_instrumentation_p ())
1325 : return false;
1326 :
1327 2434 : if (lookup_attribute ("gnu", "suppress_coverage",
1328 2434 : DECL_ATTRIBUTES (fn->decl)))
1329 : return true;
1330 :
1331 2407 : const location_t start = fn->function_start_locus;
1332 2407 : const location_t end = fn->function_end_locus;
1333 :
1334 19600 : for (const source_range& dl : suppress_coverage_ranges)
1335 16426 : if (linemap_location_before_p (line_table, dl.m_start, start)
1336 16426 : && (linemap_location_before_p (line_table, end, dl.m_finish)
1337 7417 : || dl.m_finish == UNKNOWN_LOCATION))
1338 : return true;
1339 : return false;
1340 : }
1341 :
1342 : /* Instrument and/or analyze program behavior based on program the CFG.
1343 :
1344 : This function creates a representation of the control flow graph (of
1345 : the function being compiled) that is suitable for the instrumentation
1346 : of edges and/or converting measured edge counts to counts on the
1347 : complete CFG.
1348 :
1349 : When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in
1350 : the flow graph that are needed to reconstruct the dynamic behavior of the
1351 : flow graph. This data is written to the gcno file for gcov.
1352 :
1353 : When FLAG_PROFILE_CONDITIONS is nonzero, this functions instruments the
1354 : edges in the control flow graph to track what conditions are evaluated to in
1355 : order to determine what conditions are covered and have an independent
1356 : effect on the outcome (modified condition/decision coverage). This data is
1357 : written to the gcno file for gcov.
1358 :
1359 : When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
1360 : information from the gcda file containing edge count information from
1361 : previous executions of the function being compiled. In this case, the
1362 : control flow graph is annotated with actual execution counts by
1363 : compute_branch_probabilities().
1364 :
1365 : Main entry point of this file. */
1366 :
1367 : void
1368 3024 : branch_prob (bool thunk)
1369 : {
1370 3024 : basic_block bb;
1371 3024 : unsigned i;
1372 3024 : unsigned num_edges, ignored_edges;
1373 3024 : unsigned num_instrumented;
1374 3024 : struct edge_list *el;
1375 3024 : histogram_values values = histogram_values ();
1376 3024 : unsigned cfg_checksum, lineno_checksum;
1377 3024 : bool output_to_file;
1378 :
1379 3024 : total_num_times_called++;
1380 :
1381 3024 : flow_call_edges_add (NULL);
1382 3024 : add_noreturn_fake_exit_edges ();
1383 :
1384 3024 : hash_set <location_triplet_hash> streamed_locations;
1385 :
1386 3024 : if (!thunk)
1387 : {
1388 : /* We can't handle cyclic regions constructed using abnormal edges.
1389 : To avoid these we replace every source of abnormal edge by a fake
1390 : edge from entry node and every destination by fake edge to exit.
1391 : This keeps graph acyclic and our calculation exact for all normal
1392 : edges except for exit and entrance ones.
1393 :
1394 : We also add fake exit edges for each call and asm statement in the
1395 : basic, since it may not return. */
1396 :
1397 20537 : FOR_EACH_BB_FN (bb, cfun)
1398 : {
1399 17520 : int need_exit_edge = 0, need_entry_edge = 0;
1400 17520 : int have_exit_edge = 0, have_entry_edge = 0;
1401 17520 : edge e;
1402 17520 : edge_iterator ei;
1403 :
1404 : /* Functions returning multiple times are not handled by extra edges.
1405 : Instead we simply allow negative counts on edges from exit to the
1406 : block past call and corresponding probabilities. We can't go
1407 : with the extra edges because that would result in flowgraph that
1408 : needs to have fake edges outside the spanning tree. */
1409 :
1410 44888 : FOR_EACH_EDGE (e, ei, bb->succs)
1411 : {
1412 27368 : gimple_stmt_iterator gsi;
1413 27368 : gimple *last = NULL;
1414 :
1415 : /* It may happen that there are compiler generated statements
1416 : without a locus at all. Go through the basic block from the
1417 : last to the first statement looking for a locus. */
1418 27368 : for (gsi = gsi_last_nondebug_bb (bb);
1419 30616 : !gsi_end_p (gsi);
1420 3248 : gsi_prev_nondebug (&gsi))
1421 : {
1422 27889 : last = gsi_stmt (gsi);
1423 27889 : if (!RESERVED_LOCATION_P (gimple_location (last)))
1424 : break;
1425 : }
1426 :
1427 : /* Edge with goto locus might get wrong coverage info unless
1428 : it is the only edge out of BB.
1429 : Don't do that when the locuses match, so
1430 : if (blah) goto something;
1431 : is not computed twice. */
1432 27368 : if (last
1433 26468 : && gimple_has_location (last)
1434 24711 : && !RESERVED_LOCATION_P (e->goto_locus)
1435 4985 : && !single_succ_p (bb)
1436 27652 : && (LOCATION_FILE (e->goto_locus)
1437 284 : != LOCATION_FILE (gimple_location (last))
1438 280 : || (LOCATION_LINE (e->goto_locus)
1439 27368 : != LOCATION_LINE (gimple_location (last)))))
1440 : {
1441 125 : basic_block new_bb = split_edge (e);
1442 125 : edge ne = single_succ_edge (new_bb);
1443 125 : ne->goto_locus = e->goto_locus;
1444 : }
1445 27368 : if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
1446 182 : && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1447 27368 : need_exit_edge = 1;
1448 27368 : if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1449 8198 : have_exit_edge = 1;
1450 : }
1451 39709 : FOR_EACH_EDGE (e, ei, bb->preds)
1452 : {
1453 22189 : if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
1454 182 : && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
1455 22189 : need_entry_edge = 1;
1456 22189 : if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1457 3017 : have_entry_edge = 1;
1458 : }
1459 :
1460 17520 : if (need_exit_edge && !have_exit_edge)
1461 : {
1462 29 : if (dump_file)
1463 0 : fprintf (dump_file, "Adding fake exit edge to bb %i\n",
1464 : bb->index);
1465 29 : make_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), EDGE_FAKE);
1466 : }
1467 17520 : if (need_entry_edge && !have_entry_edge)
1468 : {
1469 115 : if (dump_file)
1470 0 : fprintf (dump_file, "Adding fake entry edge to bb %i\n",
1471 : bb->index);
1472 115 : make_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), bb, EDGE_FAKE);
1473 : /* Avoid bbs that have both fake entry edge and also some
1474 : exit edge. One of those edges wouldn't be added to the
1475 : spanning tree, but we can't instrument any of them. */
1476 115 : if (have_exit_edge || need_exit_edge)
1477 : {
1478 80 : gimple_stmt_iterator gsi;
1479 80 : gimple *first;
1480 :
1481 80 : gsi = gsi_start_nondebug_after_labels_bb (bb);
1482 80 : gcc_checking_assert (!gsi_end_p (gsi));
1483 80 : first = gsi_stmt (gsi);
1484 : /* Don't split the bbs containing __builtin_setjmp_receiver
1485 : or ABNORMAL_DISPATCHER calls. These are very
1486 : special and don't expect anything to be inserted before
1487 : them. */
1488 80 : if (is_gimple_call (first)
1489 80 : && (gimple_call_builtin_p (first, BUILT_IN_SETJMP_RECEIVER)
1490 76 : || (gimple_call_flags (first) & ECF_RETURNS_TWICE)
1491 39 : || (gimple_call_internal_p (first)
1492 39 : && (gimple_call_internal_fn (first)
1493 : == IFN_ABNORMAL_DISPATCHER))))
1494 76 : continue;
1495 :
1496 4 : if (dump_file)
1497 0 : fprintf (dump_file, "Splitting bb %i after labels\n",
1498 : bb->index);
1499 4 : split_block_after_labels (bb);
1500 : }
1501 : }
1502 : }
1503 : }
1504 :
1505 3024 : el = create_edge_list ();
1506 3024 : num_edges = NUM_EDGES (el);
1507 3024 : qsort (el->index_to_edge, num_edges, sizeof (edge), compare_freqs);
1508 3024 : alloc_aux_for_edges (sizeof (struct edge_profile_info));
1509 :
1510 : /* The basic blocks are expected to be numbered sequentially. */
1511 3024 : compact_blocks ();
1512 :
1513 3024 : ignored_edges = 0;
1514 36603 : for (i = 0 ; i < num_edges ; i++)
1515 : {
1516 30555 : edge e = INDEX_EDGE (el, i);
1517 :
1518 : /* Mark edges we've replaced by fake edges above as ignored. */
1519 30555 : if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
1520 182 : && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1521 182 : && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1522 : {
1523 182 : EDGE_INFO (e)->ignore = 1;
1524 182 : ignored_edges++;
1525 : }
1526 : /* Ignore edges after musttail calls. */
1527 30555 : if (cfun->has_musttail
1528 160 : && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
1529 : {
1530 140 : gimple_stmt_iterator gsi = gsi_last_nondebug_bb (e->src);
1531 140 : gimple *stmt = gsi_stmt (gsi);
1532 140 : if (stmt
1533 140 : && is_gimple_call (stmt)
1534 220 : && gimple_call_must_tail_p (as_a <const gcall *> (stmt)))
1535 : {
1536 48 : EDGE_INFO (e)->ignore = 1;
1537 48 : ignored_edges++;
1538 : }
1539 : }
1540 : }
1541 :
1542 : /* Create spanning tree from basic block graph, mark each edge that is
1543 : on the spanning tree. We insert as many abnormal and critical edges
1544 : as possible to minimize number of edge splits necessary. */
1545 :
1546 3024 : if (!thunk)
1547 3017 : find_spanning_tree (el);
1548 : else
1549 : {
1550 7 : edge e;
1551 7 : edge_iterator ei;
1552 : /* Keep only edge from entry block to be instrumented. */
1553 21 : FOR_EACH_BB_FN (bb, cfun)
1554 35 : FOR_EACH_EDGE (e, ei, bb->succs)
1555 21 : EDGE_INFO (e)->ignore = true;
1556 : }
1557 :
1558 :
1559 : /* Fake edges that are not on the tree will not be instrumented, so
1560 : mark them ignored. */
1561 33579 : for (num_instrumented = i = 0; i < num_edges; i++)
1562 : {
1563 30555 : edge e = INDEX_EDGE (el, i);
1564 30555 : struct edge_profile_info *inf = EDGE_INFO (e);
1565 :
1566 30555 : if (inf->ignore || inf->on_tree)
1567 : /*NOP*/;
1568 12784 : else if (e->flags & EDGE_FAKE)
1569 : {
1570 76 : inf->ignore = 1;
1571 76 : ignored_edges++;
1572 : }
1573 : else
1574 12708 : num_instrumented++;
1575 : }
1576 :
1577 3024 : total_num_blocks += n_basic_blocks_for_fn (cfun);
1578 3024 : if (dump_file)
1579 181 : fprintf (dump_file, "%d basic blocks\n", n_basic_blocks_for_fn (cfun));
1580 :
1581 3024 : total_num_edges += num_edges;
1582 3024 : if (dump_file)
1583 181 : fprintf (dump_file, "%d edges\n", num_edges);
1584 :
1585 3024 : total_num_edges_ignored += ignored_edges;
1586 3024 : if (dump_file)
1587 181 : fprintf (dump_file, "%d ignored edges\n", ignored_edges);
1588 :
1589 3024 : total_num_edges_instrumented += num_instrumented;
1590 3024 : if (dump_file)
1591 181 : fprintf (dump_file, "%d instrumentation edges\n", num_instrumented);
1592 :
1593 : /* Dump function body before it's instrumented.
1594 : It helps to debug gcov tool. */
1595 3024 : if (dump_file && (dump_flags & TDF_DETAILS))
1596 24 : dump_function_to_file (cfun->decl, dump_file, dump_flags);
1597 :
1598 : /* Compute two different checksums. Note that we want to compute
1599 : the checksum in only once place, since it depends on the shape
1600 : of the control flow which can change during
1601 : various transformations. */
1602 3024 : if (thunk)
1603 : {
1604 : /* At stream in time we do not have CFG, so we cannot do checksums. */
1605 : cfg_checksum = 0;
1606 : lineno_checksum = 0;
1607 : }
1608 : else
1609 : {
1610 3017 : cfg_checksum = coverage_compute_cfg_checksum (cfun);
1611 3017 : lineno_checksum = coverage_compute_lineno_checksum ();
1612 : }
1613 :
1614 3024 : const bool fn_coverage_suppressed_p = fn_in_pragma_suppress_coverage_p (cfun);
1615 :
1616 : /* Write the data from which gcov can reconstruct the basic block
1617 : graph and function line numbers (the gcno file). */
1618 3024 : output_to_file = false;
1619 3024 : if (coverage_begin_function (lineno_checksum, cfg_checksum))
1620 : {
1621 1507 : gcov_position_t offset;
1622 :
1623 : /* The condition coverage needs a deeper analysis to identify expressions
1624 : of conditions, which means it is not yet ready to write to the gcno
1625 : file. It will write its entries later, but needs to know if it do it
1626 : in the first place, which is controlled by the return value of
1627 : coverage_begin_function. */
1628 1507 : output_to_file = true;
1629 :
1630 : /* Basic block flags */
1631 1507 : offset = gcov_write_tag (GCOV_TAG_BLOCKS);
1632 1507 : gcov_write_unsigned (n_basic_blocks_for_fn (cfun));
1633 1507 : gcov_write_length (offset);
1634 :
1635 : /* Arcs */
1636 13222 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
1637 : EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
1638 : {
1639 11715 : edge e;
1640 11715 : edge_iterator ei;
1641 :
1642 11715 : offset = gcov_write_tag (GCOV_TAG_ARCS);
1643 11715 : gcov_write_unsigned (bb->index);
1644 :
1645 29560 : FOR_EACH_EDGE (e, ei, bb->succs)
1646 : {
1647 17845 : struct edge_profile_info *i = EDGE_INFO (e);
1648 17845 : if (!i->ignore)
1649 : {
1650 17628 : unsigned flag_bits = 0;
1651 :
1652 17628 : if (i->on_tree)
1653 10208 : flag_bits |= GCOV_ARC_ON_TREE;
1654 17628 : if (e->flags & EDGE_FAKE)
1655 3298 : flag_bits |= GCOV_ARC_FAKE;
1656 17628 : if (e->flags & EDGE_FALLTHRU)
1657 7946 : flag_bits |= GCOV_ARC_FALLTHROUGH;
1658 17628 : if (e->flags & EDGE_TRUE_VALUE)
1659 1810 : flag_bits |= GCOV_ARC_TRUE;
1660 17628 : if (e->flags & EDGE_FALSE_VALUE)
1661 1810 : flag_bits |= GCOV_ARC_FALSE;
1662 : /* On trees we don't have fallthru flags, but we can
1663 : recompute them from CFG shape. */
1664 17628 : if (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)
1665 3620 : && e->src->next_bb == e->dest)
1666 1793 : flag_bits |= GCOV_ARC_FALLTHROUGH;
1667 :
1668 17628 : gcov_write_unsigned (e->dest->index);
1669 17628 : gcov_write_unsigned (flag_bits);
1670 : }
1671 : }
1672 :
1673 11715 : gcov_write_length (offset);
1674 : }
1675 :
1676 : /* Disabled blocks or function. Lines, arcs, path segments through
1677 : ignored blocks should not count towards coverage. Ignoring coverage
1678 : is a matter of interpretation and does not change the instrumentation;
1679 : gcov sorts it out. If the whole function is disabled (by the
1680 : attribute on the function, not the statements), the entry block is
1681 : recorded as ignored. */
1682 1507 : if (fn_coverage_suppressed_p)
1683 : {
1684 32 : offset = gcov_write_tag (GCOV_TAG_SUPPRESS);
1685 32 : gcov_write_unsigned (ENTRY_BLOCK);
1686 32 : gcov_write_length (offset);
1687 : }
1688 1475 : else if (any_block_coverage_suppressed_p ())
1689 : {
1690 255 : offset = gcov_write_tag (GCOV_TAG_SUPPRESS);
1691 2505 : FOR_EACH_BB_FN (bb, cfun)
1692 2250 : if (coverage_suppressed_p (bb))
1693 832 : gcov_write_unsigned (bb->index);
1694 255 : gcov_write_length (offset);
1695 : }
1696 :
1697 : /* Line numbers. */
1698 : /* Initialize the output. */
1699 1507 : output_location (&streamed_locations, NULL, 0, NULL, NULL);
1700 :
1701 1507 : hash_set<location_hash> seen_locations;
1702 :
1703 11715 : FOR_EACH_BB_FN (bb, cfun)
1704 : {
1705 10208 : gimple_stmt_iterator gsi;
1706 10208 : gcov_position_t offset = 0;
1707 :
1708 10208 : if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb)
1709 : {
1710 1507 : location_t loc = DECL_SOURCE_LOCATION (current_function_decl);
1711 1507 : if (!RESERVED_LOCATION_P (loc))
1712 : {
1713 1507 : seen_locations.add (get_pure_location (loc));
1714 1507 : expanded_location curr_location = expand_location (loc);
1715 1507 : output_location (&streamed_locations, curr_location.file,
1716 1507 : MAX (1, curr_location.line), &offset, bb);
1717 : }
1718 : }
1719 :
1720 37478 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1721 : {
1722 17062 : gimple *stmt = gsi_stmt (gsi);
1723 17062 : location_t loc = gimple_location (stmt);
1724 17062 : if (!RESERVED_LOCATION_P (loc))
1725 : {
1726 14702 : seen_locations.add (get_pure_location (loc));
1727 29404 : output_location (&streamed_locations, gimple_filename (stmt),
1728 29404 : MAX (1, gimple_lineno (stmt)), &offset, bb);
1729 : }
1730 : }
1731 :
1732 : /* Notice GOTO expressions eliminated while constructing the CFG.
1733 : It's hard to distinguish such expression, but goto_locus should
1734 : not be any of already seen location. */
1735 10208 : location_t loc;
1736 10208 : if (single_succ_p (bb)
1737 5282 : && (loc = single_succ_edge (bb)->goto_locus)
1738 3625 : && !RESERVED_LOCATION_P (loc)
1739 15490 : && !seen_locations.contains (get_pure_location (loc)))
1740 : {
1741 1291 : expanded_location curr_location = expand_location (loc);
1742 1291 : output_location (&streamed_locations, curr_location.file,
1743 1291 : MAX (1, curr_location.line), &offset, bb);
1744 : }
1745 :
1746 10208 : if (offset)
1747 : {
1748 : /* A file of NULL indicates the end of run. */
1749 9620 : gcov_write_unsigned (0);
1750 9620 : gcov_write_string (NULL);
1751 9620 : gcov_write_length (offset);
1752 : }
1753 : }
1754 1507 : }
1755 :
1756 3024 : if (flag_profile_values)
1757 1024 : gimple_find_values_to_profile (&values);
1758 :
1759 3024 : if (flag_branch_probabilities)
1760 : {
1761 579 : compute_branch_probabilities (cfg_checksum, lineno_checksum);
1762 579 : if (flag_profile_values)
1763 433 : compute_value_histograms (values, cfg_checksum, lineno_checksum);
1764 : }
1765 :
1766 3024 : remove_fake_edges ();
1767 :
1768 3024 : if (condition_coverage_flag || path_coverage_flag || profile_arc_flag)
1769 2434 : gimple_init_gcov_profiler ();
1770 :
1771 3024 : if (condition_coverage_flag && !fn_coverage_suppressed_p)
1772 : {
1773 171 : struct condcov *cov = find_conditions (cfun);
1774 171 : gcc_assert (cov);
1775 171 : const size_t nconds = cov_length (cov);
1776 171 : total_num_conds += nconds;
1777 :
1778 171 : if (coverage_counter_alloc (GCOV_COUNTER_CONDS, 2 * nconds))
1779 : {
1780 171 : gcov_position_t offset {};
1781 171 : if (output_to_file)
1782 171 : offset = gcov_write_tag (GCOV_TAG_CONDS);
1783 :
1784 472 : for (size_t i = 0; i != nconds; ++i)
1785 : {
1786 301 : array_slice<basic_block> expr = cov_blocks (cov, i);
1787 301 : array_slice<uint64_t> masks = cov_masks (cov, i);
1788 301 : array_slice<sbitmap> maps = cov_maps (cov, i);
1789 301 : gcc_assert (expr.is_valid ());
1790 301 : gcc_assert (masks.is_valid ());
1791 301 : gcc_assert (maps.is_valid ());
1792 :
1793 301 : size_t terms = instrument_decisions (expr, i, maps, masks);
1794 301 : if (output_to_file)
1795 : {
1796 301 : gcov_write_unsigned (expr.front ()->index);
1797 301 : gcov_write_unsigned (terms);
1798 : }
1799 : }
1800 171 : if (output_to_file)
1801 171 : gcov_write_length (offset);
1802 : }
1803 171 : cov_free (cov);
1804 : }
1805 :
1806 : /* For each edge not on the spanning tree, add counting code. */
1807 3024 : if (profile_arc_flag
1808 3024 : && coverage_counter_alloc (GCOV_COUNTER_ARCS, num_instrumented))
1809 : {
1810 2150 : unsigned n_instrumented;
1811 :
1812 2150 : n_instrumented = instrument_edges (el);
1813 :
1814 2150 : gcc_assert (n_instrumented == num_instrumented);
1815 :
1816 2150 : if (flag_profile_values)
1817 592 : instrument_values (values);
1818 : }
1819 :
1820 3024 : unsigned instrument_prime_paths (struct function*);
1821 3024 : if (path_coverage_flag && !fn_coverage_suppressed_p)
1822 : {
1823 308 : const unsigned npaths = instrument_prime_paths (cfun);
1824 308 : if (output_to_file)
1825 : {
1826 308 : gcov_position_t offset = gcov_write_tag (GCOV_TAG_PATHS);
1827 308 : gcov_write_unsigned (npaths);
1828 308 : gcov_write_length (offset);
1829 : }
1830 : }
1831 :
1832 3024 : free_aux_for_edges ();
1833 :
1834 3024 : values.release ();
1835 3024 : free_edge_list (el);
1836 : /* Commit changes done by instrumentation. */
1837 3024 : gsi_commit_edge_inserts ();
1838 :
1839 3024 : coverage_end_function (lineno_checksum, cfg_checksum);
1840 3024 : if (flag_branch_probabilities
1841 579 : && (profile_status_for_fn (cfun) == PROFILE_READ))
1842 : {
1843 499 : if (dump_file && (dump_flags & TDF_DETAILS))
1844 12 : report_predictor_hitrates ();
1845 499 : sreal nit;
1846 499 : bool reliable;
1847 :
1848 : /* At this moment we have precise loop iteration count estimates.
1849 : Record them to loop structure before the profile gets out of date. */
1850 1702 : for (auto loop : loops_list (cfun, 0))
1851 234 : if (loop->header->count.ipa ().nonzero_p ()
1852 176 : && expected_loop_iterations_by_profile (loop, &nit, &reliable)
1853 176 : && reliable)
1854 : {
1855 176 : widest_int bound = nit.to_nearest_int ();
1856 176 : loop->any_estimate = false;
1857 176 : record_niter_bound (loop, bound, true, false);
1858 176 : }
1859 499 : compute_function_frequency ();
1860 : }
1861 3024 : }
1862 :
1863 : /* Union find algorithm implementation for the basic blocks using
1864 : aux fields. */
1865 :
1866 : static basic_block
1867 97759 : find_group (basic_block bb)
1868 : {
1869 97759 : basic_block group = bb, bb1;
1870 :
1871 159243 : while ((basic_block) group->aux != group)
1872 : group = (basic_block) group->aux;
1873 :
1874 : /* Compress path. */
1875 124353 : while ((basic_block) bb->aux != group)
1876 : {
1877 6057 : bb1 = (basic_block) bb->aux;
1878 6057 : bb->aux = (void *) group;
1879 6057 : bb = bb1;
1880 : }
1881 97759 : return group;
1882 : }
1883 :
1884 : static void
1885 20537 : union_groups (basic_block bb1, basic_block bb2)
1886 : {
1887 20537 : basic_block bb1g = find_group (bb1);
1888 35639 : basic_block bb2g = find_group (bb2);
1889 :
1890 : /* ??? I don't have a place for the rank field. OK. Lets go w/o it,
1891 : this code is unlikely going to be performance problem anyway. */
1892 20537 : gcc_assert (bb1g != bb2g);
1893 :
1894 20537 : bb1g->aux = bb2g;
1895 20537 : }
1896 :
1897 : /* This function searches all of the edges in the program flow graph, and puts
1898 : as many bad edges as possible onto the spanning tree. Bad edges include
1899 : abnormals edges, which can't be instrumented at the moment. Since it is
1900 : possible for fake edges to form a cycle, we will have to develop some
1901 : better way in the future. Also put critical edges to the tree, since they
1902 : are more expensive to instrument. */
1903 :
1904 : static void
1905 3017 : find_spanning_tree (struct edge_list *el)
1906 : {
1907 3017 : int i;
1908 3017 : int num_edges = NUM_EDGES (el);
1909 3017 : basic_block bb;
1910 :
1911 : /* We use aux field for standard union-find algorithm. */
1912 26571 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
1913 23554 : bb->aux = bb;
1914 :
1915 : /* Add fake edge exit to entry we can't instrument. */
1916 3017 : union_groups (EXIT_BLOCK_PTR_FOR_FN (cfun), ENTRY_BLOCK_PTR_FOR_FN (cfun));
1917 :
1918 : /* First add all abnormal edges to the tree unless they form a cycle. Also
1919 : add all edges to the exit block to avoid inserting profiling code behind
1920 : setting return value from function. */
1921 36561 : for (i = 0; i < num_edges; i++)
1922 : {
1923 30527 : edge e = INDEX_EDGE (el, i);
1924 30527 : if (((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_FAKE))
1925 24929 : || e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1926 8520 : && !EDGE_INFO (e)->ignore
1927 55469 : && (find_group (e->src) != find_group (e->dest)))
1928 : {
1929 8238 : if (dump_file)
1930 332 : fprintf (dump_file, "Abnormal edge %d to %d put to tree\n",
1931 : e->src->index, e->dest->index);
1932 8238 : EDGE_INFO (e)->on_tree = 1;
1933 8238 : union_groups (e->src, e->dest);
1934 : }
1935 : }
1936 :
1937 : /* And now the rest. Edge list is sorted according to frequencies and
1938 : thus we will produce minimal spanning tree. */
1939 33544 : for (i = 0; i < num_edges; i++)
1940 : {
1941 30527 : edge e = INDEX_EDGE (el, i);
1942 30527 : if (!EDGE_INFO (e)->ignore
1943 91121 : && find_group (e->src) != find_group (e->dest))
1944 : {
1945 9282 : if (dump_file)
1946 302 : fprintf (dump_file, "Normal edge %d to %d put to tree\n",
1947 : e->src->index, e->dest->index);
1948 9282 : EDGE_INFO (e)->on_tree = 1;
1949 9282 : union_groups (e->src, e->dest);
1950 : }
1951 : }
1952 :
1953 3017 : clear_aux_for_blocks ();
1954 3017 : }
1955 :
1956 : /* Perform file-level initialization for branch-prob processing. */
1957 :
1958 : void
1959 0 : init_branch_prob (void)
1960 : {
1961 0 : int i;
1962 :
1963 0 : total_num_blocks = 0;
1964 0 : total_num_edges = 0;
1965 0 : total_num_edges_ignored = 0;
1966 0 : total_num_edges_instrumented = 0;
1967 0 : total_num_blocks_created = 0;
1968 0 : total_num_passes = 0;
1969 0 : total_num_times_called = 0;
1970 0 : total_num_branches = 0;
1971 0 : total_num_conds = 0;
1972 0 : for (i = 0; i < 20; i++)
1973 0 : total_hist_br_prob[i] = 0;
1974 0 : }
1975 :
1976 : /* Performs file-level cleanup after branch-prob processing
1977 : is completed. */
1978 :
1979 : void
1980 632 : end_branch_prob (void)
1981 : {
1982 632 : if (dump_file)
1983 : {
1984 48 : fprintf (dump_file, "\n");
1985 48 : fprintf (dump_file, "Total number of blocks: %d\n",
1986 : total_num_blocks);
1987 48 : fprintf (dump_file, "Total number of edges: %d\n", total_num_edges);
1988 48 : fprintf (dump_file, "Total number of ignored edges: %d\n",
1989 : total_num_edges_ignored);
1990 48 : fprintf (dump_file, "Total number of instrumented edges: %d\n",
1991 : total_num_edges_instrumented);
1992 48 : fprintf (dump_file, "Total number of blocks created: %d\n",
1993 : total_num_blocks_created);
1994 48 : fprintf (dump_file, "Total number of graph solution passes: %d\n",
1995 : total_num_passes);
1996 48 : if (total_num_times_called != 0)
1997 48 : fprintf (dump_file, "Average number of graph solution passes: %d\n",
1998 48 : (total_num_passes + (total_num_times_called >> 1))
1999 : / total_num_times_called);
2000 48 : fprintf (dump_file, "Total number of branches: %d\n",
2001 : total_num_branches);
2002 48 : if (total_num_branches)
2003 : {
2004 : int i;
2005 :
2006 220 : for (i = 0; i < 10; i++)
2007 200 : fprintf (dump_file, "%d%% branches in range %d-%d%%\n",
2008 200 : (total_hist_br_prob[i] + total_hist_br_prob[19-i]) * 100
2009 200 : / total_num_branches, 5*i, 5*i+5);
2010 : }
2011 48 : fprintf (dump_file, "Total number of conditions: %d\n",
2012 : total_num_conds);
2013 48 : if (afdo_fdo_records.length ())
2014 : {
2015 0 : profile_count fdo_sum = profile_count::zero ();
2016 0 : profile_count afdo_sum = profile_count::zero ();
2017 0 : for (const auto &r : afdo_fdo_records)
2018 0 : for (const auto &b : r.bbs)
2019 0 : if (b.fdo.initialized_p () && b.afdo.initialized_p ())
2020 : {
2021 0 : fdo_sum += b.fdo;
2022 0 : afdo_sum += b.afdo;
2023 : }
2024 0 : for (auto &r : afdo_fdo_records)
2025 : {
2026 0 : for (auto &b : r.bbs)
2027 0 : if (b.fdo.initialized_p () && b.afdo.initialized_p ())
2028 : {
2029 0 : fprintf (dump_file, "%s bb %i fdo %" PRIu64 " (%s) afdo ",
2030 0 : r.node->dump_name (), b.index,
2031 0 : (int64_t)b.fdo.to_gcov_type (),
2032 : maybe_hot_count_p
2033 0 : (NULL, b.fdo.apply_scale (1, 1000))
2034 : ? "very hot"
2035 0 : : maybe_hot_count_p (NULL, b.fdo)
2036 0 : ? "hot" : "cold");
2037 0 : b.afdo.dump (dump_file);
2038 0 : fprintf (dump_file, " (%s) ",
2039 : maybe_hot_afdo_count_p
2040 0 : (b.afdo.apply_scale (1, 1000))
2041 : ? "very hot"
2042 0 : : maybe_hot_afdo_count_p (b.afdo)
2043 0 : ? "hot" : "cold");
2044 0 : if (afdo_sum.nonzero_p ())
2045 : {
2046 0 : profile_count scaled
2047 0 : = b.afdo.apply_scale (fdo_sum, afdo_sum);
2048 0 : fprintf (dump_file, "scaled %" PRIu64,
2049 : scaled.to_gcov_type ());
2050 0 : if (b.fdo.to_gcov_type ())
2051 0 : fprintf (dump_file, " diff %" PRId64 ", %+2.2f%%",
2052 : scaled.to_gcov_type ()
2053 : - b.fdo.to_gcov_type (),
2054 0 : (scaled.to_gcov_type ()
2055 0 : - b.fdo.to_gcov_type ()) * 100.0
2056 : / b.fdo.to_gcov_type ());
2057 : }
2058 0 : fprintf (dump_file, "\n preds");
2059 0 : for (int val : b.preds)
2060 0 : fprintf (dump_file, " %i", val);
2061 0 : b.preds.release ();
2062 0 : fprintf (dump_file, "\n succs");
2063 0 : for (int val : b.succs)
2064 0 : fprintf (dump_file, " %i", val);
2065 0 : b.succs.release ();
2066 0 : fprintf (dump_file, "\n");
2067 : }
2068 0 : r.bbs.release ();
2069 : }
2070 : }
2071 48 : afdo_fdo_records.release ();
2072 : }
2073 632 : }
2074 :
2075 : /* Return true if any cfg coverage/profiling is enabled; -fprofile-arcs
2076 : -fcondition-coverage -fpath-coverage. */
2077 : bool
2078 101775347 : coverage_instrumentation_p ()
2079 : {
2080 101775347 : return profile_arc_flag || condition_coverage_flag || path_coverage_flag;
2081 : }
|