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