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