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