1	/* Read and annotate call graph profile from the auto profile data file.
2	Copyright (C) 2014-2024 Free Software Foundation, Inc.
3	Contributed by Dehao Chen (dehao@google.com)
4
5	This file is part of GCC.
6
7	GCC is free software; you can redistribute it and/or modify it under
8	the terms of the GNU General Public License as published by the Free
9	Software Foundation; either version 3, or (at your option) any later
10	version.
11
12	GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13	WARRANTY; without even the implied warranty of MERCHANTABILITY or
14	FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15	for more details.
16
17	You should have received a copy of the GNU General Public License
18	along with GCC; see the file COPYING3. If not see
19	<http://www.gnu.org/licenses/>. */
20
21	#include "config.h"
22	#define INCLUDE_MAP
23	#define INCLUDE_SET
24	#include "system.h"
25	#include "coretypes.h"
26	#include "backend.h"
27	#include "tree.h"
28	#include "gimple.h"
29	#include "predict.h"
30	#include "alloc-pool.h"
31	#include "tree-pass.h"
32	#include "ssa.h"
33	#include "cgraph.h"
34	#include "gcov-io.h"
35	#include "diagnostic-core.h"
36	#include "profile.h"
37	#include "langhooks.h"
38	#include "cfgloop.h"
39	#include "tree-cfg.h"
40	#include "tree-cfgcleanup.h"
41	#include "tree-into-ssa.h"
42	#include "gimple-iterator.h"
43	#include "value-prof.h"
44	#include "symbol-summary.h"
45	#include "sreal.h"
46	#include "ipa-cp.h"
47	#include "ipa-prop.h"
48	#include "ipa-fnsummary.h"
49	#include "ipa-inline.h"
50	#include "tree-inline.h"
51	#include "auto-profile.h"
52	#include "tree-pretty-print.h"
53	#include "gimple-pretty-print.h"
54
55	/* The following routines implements AutoFDO optimization.
56
57	This optimization uses sampling profiles to annotate basic block counts
58	and uses heuristics to estimate branch probabilities.
59
60	There are three phases in AutoFDO:
61
62	Phase 1: Read profile from the profile data file.
63	The following info is read from the profile datafile:
64	* string_table: a map between function name and its index.
65	* autofdo_source_profile: a map from function_instance name to
66	function_instance. This is represented as a forest of
67	function_instances.
68	* WorkingSet: a histogram of how many instructions are covered for a
69	given percentage of total cycles. This is describing the binary
70	level information (not source level). This info is used to help
71	decide if we want aggressive optimizations that could increase
72	code footprint (e.g. loop unroll etc.)
73	A function instance is an instance of function that could either be a
74	standalone symbol, or a clone of a function that is inlined into another
75	function.
76
77	Phase 2: Early inline + value profile transformation.
78	Early inline uses autofdo_source_profile to find if a callsite is:
79	* inlined in the profiled binary.
80	* callee body is hot in the profiling run.
81	If both condition satisfies, early inline will inline the callsite
82	regardless of the code growth.
83	Phase 2 is an iterative process. During each iteration, we also check
84	if an indirect callsite is promoted and inlined in the profiling run.
85	If yes, vpt will happen to force promote it and in the next iteration,
86	einline will inline the promoted callsite in the next iteration.
87
88	Phase 3: Annotate control flow graph.
89	AutoFDO uses a separate pass to:
90	* Annotate basic block count
91	* Estimate branch probability
92
93	After the above 3 phases, all profile is readily annotated on the GCC IR.
94	AutoFDO tries to reuse all FDO infrastructure as much as possible to make
95	use of the profile. E.g. it uses existing mechanism to calculate the basic
96	block/edge frequency, as well as the cgraph node/edge count.
97	*/
98
99	#define DEFAULT_AUTO_PROFILE_FILE "fbdata.afdo"
100	#define AUTO_PROFILE_VERSION 2
101
102	namespace autofdo
103	{
104
105	/* Intermediate edge info used when propagating AutoFDO profile information.
106	We can't edge->count() directly since it's computed from edge's probability
107	while probability is yet not decided during propagation. */
108	#define AFDO_EINFO(e) ((class edge_info *) e->aux)
109	class edge_info
110	{
111	public:
112	edge_info () : count_ (profile_count::zero ().afdo ()), annotated_ (false) {}
113	bool is_annotated () const { return annotated_; }
114	void set_annotated () { annotated_ = true; }
115	profile_count get_count () const { return count_; }
116	void set_count (profile_count count) { count_ = count; }
117	private:
118	profile_count count_;
119	bool annotated_;
120	};
121
122	/* Represent a source location: (function_decl, lineno). */
123	typedef std::pair<tree, unsigned> decl_lineno;
124
125	/* Represent an inline stack. vector[0] is the leaf node. */
126	typedef auto_vec<decl_lineno> inline_stack;
127
128	/* String array that stores function names. */
129	typedef auto_vec<char *> string_vector;
130
131	/* Map from function name's index in string_table to target's
132	execution count. */
133	typedef std::map<unsigned, gcov_type> icall_target_map;
134
135	/* Set of gimple stmts. Used to track if the stmt has already been promoted
136	to direct call. */
137	typedef std::set<gimple *> stmt_set;
138
139	/* Represent count info of an inline stack. */
140	class count_info
141	{
142	public:
143	/* Sampled count of the inline stack. */
144	gcov_type count;
145
146	/* Map from indirect call target to its sample count. */
147	icall_target_map targets;
148
149	/* Whether this inline stack is already used in annotation.
150
151	Each inline stack should only be used to annotate IR once.
152	This will be enforced when instruction-level discriminator
153	is supported. */
154	bool annotated;
155	};
156
157	/* operator< for "const char *". */
158	struct string_compare
159	{
160	bool operator()(const char *a, const char *b) const
161	{
162	return strcmp (s1: a, s2: b) < 0;
163	}
164	};
165
166	/* Store a string array, indexed by string position in the array. */
167	class string_table
168	{
169	public:
170	string_table ()
171	{}
172
173	~string_table ();
174
175	/* For a given string, returns its index. */
176	int get_index (const char *name) const;
177
178	/* For a given decl, returns the index of the decl name. */
179	int get_index_by_decl (tree decl) const;
180
181	/* For a given index, returns the string. */
182	const char *get_name (int index) const;
183
184	/* Read profile, return TRUE on success. */
185	bool read ();
186
187	private:
188	typedef std::map<const char *, unsigned, string_compare> string_index_map;
189	string_vector vector_;
190	string_index_map map_;
191	};
192
193	/* Profile of a function instance:
194	1. total_count of the function.
195	2. head_count (entry basic block count) of the function (only valid when
196	function is a top-level function_instance, i.e. it is the original copy
197	instead of the inlined copy).
198	3. map from source location (decl_lineno) to profile (count_info).
199	4. map from callsite to callee function_instance. */
200	class function_instance
201	{
202	public:
203	typedef auto_vec<function_instance *> function_instance_stack;
204
205	/* Read the profile and return a function_instance with head count as
206	HEAD_COUNT. Recursively read callsites to create nested function_instances
207	too. STACK is used to track the recursive creation process. */
208	static function_instance *
209	read_function_instance (function_instance_stack *stack,
210	gcov_type head_count);
211
212	/* Recursively deallocate all callsites (nested function_instances). */
213	~function_instance ();
214
215	/* Accessors. */
216	int
217	name () const
218	{
219	return name_;
220	}
221	gcov_type
222	total_count () const
223	{
224	return total_count_;
225	}
226	gcov_type
227	head_count () const
228	{
229	return head_count_;
230	}
231
232	/* Traverse callsites of the current function_instance to find one at the
233	location of LINENO and callee name represented in DECL. */
234	function_instance *get_function_instance_by_decl (unsigned lineno,
235	tree decl) const;
236
237	/* Store the profile info for LOC in INFO. Return TRUE if profile info
238	is found. */
239	bool get_count_info (location_t loc, count_info *info) const;
240
241	/* Read the inlined indirect call target profile for STMT and store it in
242	MAP, return the total count for all inlined indirect calls. */
243	gcov_type find_icall_target_map (gcall *stmt, icall_target_map *map) const;
244
245	/* Sum of counts that is used during annotation. */
246	gcov_type total_annotated_count () const;
247
248	/* Mark LOC as annotated. */
249	void mark_annotated (location_t loc);
250
251	private:
252	/* Callsite, represented as (decl_lineno, callee_function_name_index). */
253	typedef std::pair<unsigned, unsigned> callsite;
254
255	/* Map from callsite to callee function_instance. */
256	typedef std::map<callsite, function_instance *> callsite_map;
257
258	function_instance (unsigned name, gcov_type head_count)
259	: name_ (name), total_count_ (0), head_count_ (head_count)
260	{
261	}
262
263	/* Map from source location (decl_lineno) to profile (count_info). */
264	typedef std::map<unsigned, count_info> position_count_map;
265
266	/* function_instance name index in the string_table. */
267	unsigned name_;
268
269	/* Total sample count. */
270	gcov_type total_count_;
271
272	/* Entry BB's sample count. */
273	gcov_type head_count_;
274
275	/* Map from callsite location to callee function_instance. */
276	callsite_map callsites;
277
278	/* Map from source location to count_info. */
279	position_count_map pos_counts;
280	};
281
282	/* Profile for all functions. */
283	class autofdo_source_profile
284	{
285	public:
286	static autofdo_source_profile *
287	create ()
288	{
289	autofdo_source_profile *map = new autofdo_source_profile ();
290
291	if (map->read ())
292	return map;
293	delete map;
294	return NULL;
295	}
296
297	~autofdo_source_profile ();
298
299	/* For a given DECL, returns the top-level function_instance. */
300	function_instance *get_function_instance_by_decl (tree decl) const;
301
302	/* Find count_info for a given gimple STMT. If found, store the count_info
303	in INFO and return true; otherwise return false. */
304	bool get_count_info (gimple *stmt, count_info *info) const;
305
306	/* Find total count of the callee of EDGE. */
307	gcov_type get_callsite_total_count (struct cgraph_edge *edge) const;
308
309	/* Update value profile INFO for STMT from the inlined indirect callsite.
310	Return true if INFO is updated. */
311	bool update_inlined_ind_target (gcall *stmt, count_info *info);
312
313	/* Mark LOC as annotated. */
314	void mark_annotated (location_t loc);
315
316	private:
317	/* Map from function_instance name index (in string_table) to
318	function_instance. */
319	typedef std::map<unsigned, function_instance *> name_function_instance_map;
320
321	autofdo_source_profile () {}
322
323	/* Read AutoFDO profile and returns TRUE on success. */
324	bool read ();
325
326	/* Return the function_instance in the profile that correspond to the
327	inline STACK. */
328	function_instance *
329	get_function_instance_by_inline_stack (const inline_stack &stack) const;
330
331	name_function_instance_map map_;
332	};
333
334	/* Store the strings read from the profile data file. */
335	static string_table *afdo_string_table;
336
337	/* Store the AutoFDO source profile. */
338	static autofdo_source_profile *afdo_source_profile;
339
340	/* gcov_summary structure to store the profile_info. */
341	static gcov_summary *afdo_profile_info;
342
343	/* Helper functions. */
344
345	/* Return the original name of NAME: strip the suffix that starts
346	with '.' Caller is responsible for freeing RET. */
347
348	static char *
349	get_original_name (const char *name)
350	{
351	char *ret = xstrdup (name);
352	char *find = strchr (s: ret, c: '.');
353	if (find != NULL)
354	*find = 0;
355	return ret;
356	}
357
358	/* Return the combined location, which is a 32bit integer in which
359	higher 16 bits stores the line offset of LOC to the start lineno
360	of DECL, The lower 16 bits stores the discriminator. */
361
362	static unsigned
363	get_combined_location (location_t loc, tree decl)
364	{
365	/* TODO: allow more bits for line and less bits for discriminator. */
366	if (LOCATION_LINE (loc) - DECL_SOURCE_LINE (decl) >= (1<<16))
367	warning_at (loc, OPT_Woverflow, "offset exceeds 16 bytes");
368	return ((LOCATION_LINE (loc) - DECL_SOURCE_LINE (decl)) << 16)
369	| get_discriminator_from_loc (loc);
370	}
371
372	/* Return the function decl of a given lexical BLOCK. */
373
374	static tree
375	get_function_decl_from_block (tree block)
376	{
377	if (!inlined_function_outer_scope_p (block))
378	return NULL_TREE;
379
380	return BLOCK_ABSTRACT_ORIGIN (block);
381	}
382
383	/* Store inline stack for STMT in STACK. */
384
385	static void
386	get_inline_stack (location_t locus, inline_stack *stack)
387	{
388	if (LOCATION_LOCUS (locus) == UNKNOWN_LOCATION)
389	return;
390
391	tree block = LOCATION_BLOCK (locus);
392	if (block && TREE_CODE (block) == BLOCK)
393	{
394	for (block = BLOCK_SUPERCONTEXT (block);
395	block && (TREE_CODE (block) == BLOCK);
396	block = BLOCK_SUPERCONTEXT (block))
397	{
398	location_t tmp_locus = BLOCK_SOURCE_LOCATION (block);
399	if (LOCATION_LOCUS (tmp_locus) == UNKNOWN_LOCATION)
400	continue;
401
402	tree decl = get_function_decl_from_block (block);
403	stack->safe_push (
404	obj: std::make_pair (x&: decl, y: get_combined_location (loc: locus, decl)));
405	locus = tmp_locus;
406	}
407	}
408	stack->safe_push (
409	obj: std::make_pair (x&: current_function_decl,
410	y: get_combined_location (loc: locus, decl: current_function_decl)));
411	}
412
413	/* Return STMT's combined location, which is a 32bit integer in which
414	higher 16 bits stores the line offset of LOC to the start lineno
415	of DECL, The lower 16 bits stores the discriminator. */
416
417	static unsigned
418	get_relative_location_for_stmt (gimple *stmt)
419	{
420	location_t locus = gimple_location (g: stmt);
421	if (LOCATION_LOCUS (locus) == UNKNOWN_LOCATION)
422	return UNKNOWN_LOCATION;
423
424	for (tree block = gimple_block (g: stmt); block && (TREE_CODE (block) == BLOCK);
425	block = BLOCK_SUPERCONTEXT (block))
426	if (LOCATION_LOCUS (BLOCK_SOURCE_LOCATION (block)) != UNKNOWN_LOCATION)
427	return get_combined_location (loc: locus,
428	decl: get_function_decl_from_block (block));
429	return get_combined_location (loc: locus, decl: current_function_decl);
430	}
431
432	/* Return true if BB contains indirect call. */
433
434	static bool
435	has_indirect_call (basic_block bb)
436	{
437	gimple_stmt_iterator gsi;
438
439	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
440	{
441	gimple *stmt = gsi_stmt (i: gsi);
442	if (gimple_code (g: stmt) == GIMPLE_CALL && !gimple_call_internal_p (gs: stmt)
443	&& (gimple_call_fn (gs: stmt) == NULL
444	|| TREE_CODE (gimple_call_fn (stmt)) != FUNCTION_DECL))
445	return true;
446	}
447	return false;
448	}
449
450	/* Member functions for string_table. */
451
452	/* Deconstructor. */
453
454	string_table::~string_table ()
455	{
456	for (unsigned i = 0; i < vector_.length (); i++)
457	free (ptr: vector_[i]);
458	}
459
460
461	/* Return the index of a given function NAME. Return -1 if NAME is not
462	found in string table. */
463
464	int
465	string_table::get_index (const char *name) const
466	{
467	if (name == NULL)
468	return -1;
469	string_index_map::const_iterator iter = map_.find (x: name);
470	if (iter == map_.end ())
471	return -1;
472
473	return iter->second;
474	}
475
476	/* Return the index of a given function DECL. Return -1 if DECL is not
477	found in string table. */
478
479	int
480	string_table::get_index_by_decl (tree decl) const
481	{
482	char *name
483	= get_original_name (IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl)));
484	int ret = get_index (name);
485	free (ptr: name);
486	if (ret != -1)
487	return ret;
488	ret = get_index (name: lang_hooks.dwarf_name (decl, 0));
489	if (ret != -1)
490	return ret;
491	if (DECL_FROM_INLINE (decl))
492	return get_index_by_decl (DECL_ABSTRACT_ORIGIN (decl));
493
494	return -1;
495	}
496
497	/* Return the function name of a given INDEX. */
498
499	const char *
500	string_table::get_name (int index) const
501	{
502	gcc_assert (index > 0 && index < (int)vector_.length ());
503	return vector_[index];
504	}
505
506	/* Read the string table. Return TRUE if reading is successful. */
507
508	bool
509	string_table::read ()
510	{
511	if (gcov_read_unsigned () != GCOV_TAG_AFDO_FILE_NAMES)
512	return false;
513	/* Skip the length of the section. */
514	gcov_read_unsigned ();
515	/* Read in the file name table. */
516	unsigned string_num = gcov_read_unsigned ();
517	for (unsigned i = 0; i < string_num; i++)
518	{
519	vector_.safe_push (obj: get_original_name (name: gcov_read_string ()));
520	map_[vector_.last ()] = i;
521	}
522	return true;
523	}
524
525	/* Member functions for function_instance. */
526
527	function_instance::~function_instance ()
528	{
529	for (callsite_map::iterator iter = callsites.begin ();
530	iter != callsites.end (); ++iter)
531	delete iter->second;
532	}
533
534	/* Traverse callsites of the current function_instance to find one at the
535	location of LINENO and callee name represented in DECL. */
536
537	function_instance *
538	function_instance::get_function_instance_by_decl (unsigned lineno,
539	tree decl) const
540	{
541	int func_name_idx = afdo_string_table->get_index_by_decl (decl);
542	if (func_name_idx != -1)
543	{
544	callsite_map::const_iterator ret
545	= callsites.find (x: std::make_pair (x&: lineno, y&: func_name_idx));
546	if (ret != callsites.end ())
547	return ret->second;
548	}
549	func_name_idx
550	= afdo_string_table->get_index (name: lang_hooks.dwarf_name (decl, 0));
551	if (func_name_idx != -1)
552	{
553	callsite_map::const_iterator ret
554	= callsites.find (x: std::make_pair (x&: lineno, y&: func_name_idx));
555	if (ret != callsites.end ())
556	return ret->second;
557	}
558	if (DECL_FROM_INLINE (decl))
559	return get_function_instance_by_decl (lineno, DECL_ABSTRACT_ORIGIN (decl));
560
561	return NULL;
562	}
563
564	/* Store the profile info for LOC in INFO. Return TRUE if profile info
565	is found. */
566
567	bool
568	function_instance::get_count_info (location_t loc, count_info *info) const
569	{
570	position_count_map::const_iterator iter = pos_counts.find (x: loc);
571	if (iter == pos_counts.end ())
572	return false;
573	*info = iter->second;
574	return true;
575	}
576
577	/* Mark LOC as annotated. */
578
579	void
580	function_instance::mark_annotated (location_t loc)
581	{
582	position_count_map::iterator iter = pos_counts.find (x: loc);
583	if (iter == pos_counts.end ())
584	return;
585	iter->second.annotated = true;
586	}
587
588	/* Read the inlined indirect call target profile for STMT and store it in
589	MAP, return the total count for all inlined indirect calls. */
590
591	gcov_type
592	function_instance::find_icall_target_map (gcall *stmt,
593	icall_target_map *map) const
594	{
595	gcov_type ret = 0;
596	unsigned stmt_offset = get_relative_location_for_stmt (stmt);
597
598	for (callsite_map::const_iterator iter = callsites.begin ();
599	iter != callsites.end (); ++iter)
600	{
601	unsigned callee = iter->second->name ();
602	/* Check if callsite location match the stmt. */
603	if (iter->first.first != stmt_offset)
604	continue;
605	struct cgraph_node *node = cgraph_node::get_for_asmname (
606	get_identifier (afdo_string_table->get_name (callee)));
607	if (node == NULL)
608	continue;
609	(*map)[callee] = iter->second->total_count ();
610	ret += iter->second->total_count ();
611	}
612	return ret;
613	}
614
615	/* Read the profile and create a function_instance with head count as
616	HEAD_COUNT. Recursively read callsites to create nested function_instances
617	too. STACK is used to track the recursive creation process. */
618
619	/* function instance profile format:
620
621	ENTRY_COUNT: 8 bytes
622	NAME_INDEX: 4 bytes
623	NUM_POS_COUNTS: 4 bytes
624	NUM_CALLSITES: 4 byte
625	POS_COUNT_1:
626	POS_1_OFFSET: 4 bytes
627	NUM_TARGETS: 4 bytes
628	COUNT: 8 bytes
629	TARGET_1:
630	VALUE_PROFILE_TYPE: 4 bytes
631	TARGET_IDX: 8 bytes
632	COUNT: 8 bytes
633	TARGET_2
634	...
635	TARGET_n
636	POS_COUNT_2
637	...
638	POS_COUNT_N
639	CALLSITE_1:
640	CALLSITE_1_OFFSET: 4 bytes
641	FUNCTION_INSTANCE_PROFILE (nested)
642	CALLSITE_2
643	...
644	CALLSITE_n. */
645
646	function_instance *
647	function_instance::read_function_instance (function_instance_stack *stack,
648	gcov_type head_count)
649	{
650	unsigned name = gcov_read_unsigned ();
651	unsigned num_pos_counts = gcov_read_unsigned ();
652	unsigned num_callsites = gcov_read_unsigned ();
653	function_instance *s = new function_instance (name, head_count);
654	stack->safe_push (obj: s);
655
656	for (unsigned i = 0; i < num_pos_counts; i++)
657	{
658	unsigned offset = gcov_read_unsigned ();
659	unsigned num_targets = gcov_read_unsigned ();
660	gcov_type count = gcov_read_counter ();
661	s->pos_counts[offset].count = count;
662	for (unsigned j = 0; j < stack->length (); j++)
663	(*stack)[j]->total_count_ += count;
664	for (unsigned j = 0; j < num_targets; j++)
665	{
666	/* Only indirect call target histogram is supported now. */
667	gcov_read_unsigned ();
668	gcov_type target_idx = gcov_read_counter ();
669	s->pos_counts[offset].targets[target_idx] = gcov_read_counter ();
670	}
671	}
672	for (unsigned i = 0; i < num_callsites; i++)
673	{
674	unsigned offset = gcov_read_unsigned ();
675	function_instance *callee_function_instance
676	= read_function_instance (stack, head_count: 0);
677	s->callsites[std::make_pair (x&: offset, y: callee_function_instance->name ())]
678	= callee_function_instance;
679	}
680	stack->pop ();
681	return s;
682	}
683
684	/* Sum of counts that is used during annotation. */
685
686	gcov_type
687	function_instance::total_annotated_count () const
688	{
689	gcov_type ret = 0;
690	for (callsite_map::const_iterator iter = callsites.begin ();
691	iter != callsites.end (); ++iter)
692	ret += iter->second->total_annotated_count ();
693	for (position_count_map::const_iterator iter = pos_counts.begin ();
694	iter != pos_counts.end (); ++iter)
695	if (iter->second.annotated)
696	ret += iter->second.count;
697	return ret;
698	}
699
700	/* Member functions for autofdo_source_profile. */
701
702	autofdo_source_profile::~autofdo_source_profile ()
703	{
704	for (name_function_instance_map::const_iterator iter = map_.begin ();
705	iter != map_.end (); ++iter)
706	delete iter->second;
707	}
708
709	/* For a given DECL, returns the top-level function_instance. */
710
711	function_instance *
712	autofdo_source_profile::get_function_instance_by_decl (tree decl) const
713	{
714	int index = afdo_string_table->get_index_by_decl (decl);
715	if (index == -1)
716	return NULL;
717	name_function_instance_map::const_iterator ret = map_.find (x: index);
718	return ret == map_.end () ? NULL : ret->second;
719	}
720
721	/* Find count_info for a given gimple STMT. If found, store the count_info
722	in INFO and return true; otherwise return false. */
723
724	bool
725	autofdo_source_profile::get_count_info (gimple *stmt, count_info *info) const
726	{
727	if (LOCATION_LOCUS (gimple_location (stmt)) == cfun->function_end_locus)
728	return false;
729
730	inline_stack stack;
731	get_inline_stack (locus: gimple_location (g: stmt), stack: &stack);
732	if (stack.length () == 0)
733	return false;
734	function_instance *s = get_function_instance_by_inline_stack (stack);
735	if (s == NULL)
736	return false;
737	return s->get_count_info (loc: stack[0].second, info);
738	}
739
740	/* Mark LOC as annotated. */
741
742	void
743	autofdo_source_profile::mark_annotated (location_t loc)
744	{
745	inline_stack stack;
746	get_inline_stack (locus: loc, stack: &stack);
747	if (stack.length () == 0)
748	return;
749	function_instance *s = get_function_instance_by_inline_stack (stack);
750	if (s == NULL)
751	return;
752	s->mark_annotated (loc: stack[0].second);
753	}
754
755	/* Update value profile INFO for STMT from the inlined indirect callsite.
756	Return true if INFO is updated. */
757
758	bool
759	autofdo_source_profile::update_inlined_ind_target (gcall *stmt,
760	count_info *info)
761	{
762	if (dump_file)
763	{
764	fprintf (stream: dump_file, format: "Checking indirect call -> direct call ");
765	print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
766	}
767
768	if (LOCATION_LOCUS (gimple_location (stmt)) == cfun->function_end_locus)
769	{
770	if (dump_file)
771	fprintf (stream: dump_file, format: " good locus\n");
772	return false;
773	}
774
775	count_info old_info;
776	get_count_info (stmt, info: &old_info);
777	gcov_type total = 0;
778	for (icall_target_map::const_iterator iter = old_info.targets.begin ();
779	iter != old_info.targets.end (); ++iter)
780	total += iter->second;
781
782	/* Program behavior changed, original promoted (and inlined) target is not
783	hot any more. Will avoid promote the original target.
784
785	To check if original promoted target is still hot, we check the total
786	count of the unpromoted targets (stored in TOTAL). If a callsite count
787	(stored in INFO) is smaller than half of the total count, the original
788	promoted target is considered not hot any more. */
789	if (info->count < total / 2)
790	{
791	if (dump_file)
792	fprintf (stream: dump_file, format: " not hot anymore %ld < %ld",
793	(long)info->count,
794	(long)total /2);
795	return false;
796	}
797
798	inline_stack stack;
799	get_inline_stack (locus: gimple_location (g: stmt), stack: &stack);
800	if (stack.length () == 0)
801	{
802	if (dump_file)
803	fprintf (stream: dump_file, format: " no inline stack\n");
804	return false;
805	}
806	function_instance *s = get_function_instance_by_inline_stack (stack);
807	if (s == NULL)
808	{
809	if (dump_file)
810	fprintf (stream: dump_file, format: " function not found in inline stack\n");
811	return false;
812	}
813	icall_target_map map;
814	if (s->find_icall_target_map (stmt, map: &map) == 0)
815	{
816	if (dump_file)
817	fprintf (stream: dump_file, format: " no target map\n");
818	return false;
819	}
820	for (icall_target_map::const_iterator iter = map.begin ();
821	iter != map.end (); ++iter)
822	info->targets[iter->first] = iter->second;
823	if (dump_file)
824	fprintf (stream: dump_file, format: " looks good\n");
825	return true;
826	}
827
828	/* Find total count of the callee of EDGE. */
829
830	gcov_type
831	autofdo_source_profile::get_callsite_total_count (
832	struct cgraph_edge *edge) const
833	{
834	inline_stack stack;
835	stack.safe_push (obj: std::make_pair (x&: edge->callee->decl, y: 0));
836	get_inline_stack (locus: gimple_location (g: edge->call_stmt), stack: &stack);
837
838	function_instance *s = get_function_instance_by_inline_stack (stack);
839	if (s == NULL
840	|| afdo_string_table->get_index (IDENTIFIER_POINTER (
841	DECL_ASSEMBLER_NAME (edge->callee->decl))) != s->name ())
842	return 0;
843
844	return s->total_count ();
845	}
846
847	/* Read AutoFDO profile and returns TRUE on success. */
848
849	/* source profile format:
850
851	GCOV_TAG_AFDO_FUNCTION: 4 bytes
852	LENGTH: 4 bytes
853	NUM_FUNCTIONS: 4 bytes
854	FUNCTION_INSTANCE_1
855	FUNCTION_INSTANCE_2
856	...
857	FUNCTION_INSTANCE_N. */
858
859	bool
860	autofdo_source_profile::read ()
861	{
862	if (gcov_read_unsigned () != GCOV_TAG_AFDO_FUNCTION)
863	{
864	inform (UNKNOWN_LOCATION, "Not expected TAG.");
865	return false;
866	}
867
868	/* Skip the length of the section. */
869	gcov_read_unsigned ();
870
871	/* Read in the function/callsite profile, and store it in local
872	data structure. */
873	unsigned function_num = gcov_read_unsigned ();
874	for (unsigned i = 0; i < function_num; i++)
875	{
876	function_instance::function_instance_stack stack;
877	function_instance *s = function_instance::read_function_instance (
878	stack: &stack, head_count: gcov_read_counter ());
879	map_[s->name ()] = s;
880	}
881	return true;
882	}
883
884	/* Return the function_instance in the profile that correspond to the
885	inline STACK. */
886
887	function_instance *
888	autofdo_source_profile::get_function_instance_by_inline_stack (
889	const inline_stack &stack) const
890	{
891	name_function_instance_map::const_iterator iter = map_.find (
892	x: afdo_string_table->get_index_by_decl (decl: stack[stack.length () - 1].first));
893	if (iter == map_.end())
894	return NULL;
895	function_instance *s = iter->second;
896	for (unsigned i = stack.length() - 1; i > 0; i--)
897	{
898	s = s->get_function_instance_by_decl (
899	lineno: stack[i].second, decl: stack[i - 1].first);
900	if (s == NULL)
901	return NULL;
902	}
903	return s;
904	}
905
906	/* Module profile is only used by LIPO. Here we simply ignore it. */
907
908	static void
909	fake_read_autofdo_module_profile ()
910	{
911	/* Read in the module info. */
912	gcov_read_unsigned ();
913
914	/* Skip the length of the section. */
915	gcov_read_unsigned ();
916
917	/* Read in the file name table. */
918	unsigned total_module_num = gcov_read_unsigned ();
919	gcc_assert (total_module_num == 0);
920	}
921
922	/* Read data from profile data file. */
923
924	static void
925	read_profile (void)
926	{
927	if (gcov_open (auto_profile_file, 1) == 0)
928	{
929	error ("cannot open profile file %s", auto_profile_file);
930	return;
931	}
932
933	if (gcov_read_unsigned () != GCOV_DATA_MAGIC)
934	{
935	error ("AutoFDO profile magic number does not match");
936	return;
937	}
938
939	/* Skip the version number. */
940	unsigned version = gcov_read_unsigned ();
941	if (version != AUTO_PROFILE_VERSION)
942	{
943	error ("AutoFDO profile version %u does not match %u",
944	version, AUTO_PROFILE_VERSION);
945	return;
946	}
947
948	/* Skip the empty integer. */
949	gcov_read_unsigned ();
950
951	/* string_table. */
952	afdo_string_table = new string_table ();
953	if (!afdo_string_table->read())
954	{
955	error ("cannot read string table from %s", auto_profile_file);
956	return;
957	}
958
959	/* autofdo_source_profile. */
960	afdo_source_profile = autofdo_source_profile::create ();
961	if (afdo_source_profile == NULL)
962	{
963	error ("cannot read function profile from %s", auto_profile_file);
964	return;
965	}
966
967	/* autofdo_module_profile. */
968	fake_read_autofdo_module_profile ();
969	}
970
971	/* From AutoFDO profiles, find values inside STMT for that we want to measure
972	histograms for indirect-call optimization.
973
974	This function is actually served for 2 purposes:
975	* before annotation, we need to mark histogram, promote and inline
976	* after annotation, we just need to mark, and let follow-up logic to
977	decide if it needs to promote and inline. */
978
979	static bool
980	afdo_indirect_call (gimple_stmt_iterator *gsi, const icall_target_map &map,
981	bool transform)
982	{
983	gimple *gs = gsi_stmt (i: *gsi);
984	tree callee;
985
986	if (map.size () == 0)
987	return false;
988	gcall *stmt = dyn_cast <gcall *> (p: gs);
989	if (!stmt
990	|| gimple_call_internal_p (gs: stmt)
991	|| gimple_call_fndecl (gs: stmt) != NULL_TREE)
992	return false;
993
994	gcov_type total = 0;
995	icall_target_map::const_iterator max_iter = map.end ();
996
997	for (icall_target_map::const_iterator iter = map.begin ();
998	iter != map.end (); ++iter)
999	{
1000	total += iter->second;
1001	if (max_iter == map.end () || max_iter->second < iter->second)
1002	max_iter = iter;
1003	}
1004	struct cgraph_node *direct_call = cgraph_node::get_for_asmname (
1005	get_identifier (afdo_string_table->get_name (max_iter->first)));
1006	if (direct_call == NULL || !direct_call->profile_id)
1007	return false;
1008
1009	callee = gimple_call_fn (gs: stmt);
1010
1011	histogram_value hist = gimple_alloc_histogram_value (
1012	cfun, HIST_TYPE_INDIR_CALL, stmt, value: callee);
1013	hist->n_counters = 4;
1014	hist->hvalue.counters = XNEWVEC (gcov_type, hist->n_counters);
1015	gimple_add_histogram_value (cfun, stmt, hist);
1016
1017	/* Total counter */
1018	hist->hvalue.counters[0] = total;
1019	/* Number of value/counter pairs */
1020	hist->hvalue.counters[1] = 1;
1021	/* Value */
1022	hist->hvalue.counters[2] = direct_call->profile_id;
1023	/* Counter */
1024	hist->hvalue.counters[3] = max_iter->second;
1025
1026	if (!transform)
1027	return false;
1028
1029	cgraph_node* current_function_node = cgraph_node::get (decl: current_function_decl);
1030
1031	/* If the direct call is a recursive call, don't promote it since
1032	we are not set up to inline recursive calls at this stage. */
1033	if (direct_call == current_function_node)
1034	return false;
1035
1036	struct cgraph_edge *indirect_edge
1037	= current_function_node->get_edge (call_stmt: stmt);
1038
1039	if (dump_file)
1040	{
1041	fprintf (stream: dump_file, format: "Indirect call -> direct call ");
1042	print_generic_expr (dump_file, callee, TDF_SLIM);
1043	fprintf (stream: dump_file, format: " => ");
1044	print_generic_expr (dump_file, direct_call->decl, TDF_SLIM);
1045	}
1046
1047	if (direct_call == NULL)
1048	{
1049	if (dump_file)
1050	fprintf (stream: dump_file, format: " not transforming\n");
1051	return false;
1052	}
1053	if (DECL_STRUCT_FUNCTION (direct_call->decl) == NULL)
1054	{
1055	if (dump_file)
1056	fprintf (stream: dump_file, format: " no declaration\n");
1057	return false;
1058	}
1059
1060	if (dump_file)
1061	{
1062	fprintf (stream: dump_file, format: " transformation on insn ");
1063	print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1064	fprintf (stream: dump_file, format: "\n");
1065	}
1066
1067	/* FIXME: Count should be initialized. */
1068	struct cgraph_edge *new_edge
1069	= indirect_edge->make_speculative (n2: direct_call,
1070	direct_count: profile_count::uninitialized ());
1071	cgraph_edge::redirect_call_stmt_to_callee (e: new_edge);
1072	gimple_remove_histogram_value (cfun, stmt, hist);
1073	inline_call (new_edge, true, NULL, NULL, false);
1074	return true;
1075	}
1076
1077	/* From AutoFDO profiles, find values inside STMT for that we want to measure
1078	histograms and adds them to list VALUES. */
1079
1080	static bool
1081	afdo_vpt (gimple_stmt_iterator *gsi, const icall_target_map &map,
1082	bool transform)
1083	{
1084	return afdo_indirect_call (gsi, map, transform);
1085	}
1086
1087	typedef std::set<basic_block> bb_set;
1088	typedef std::set<edge> edge_set;
1089
1090	static bool
1091	is_bb_annotated (const basic_block bb, const bb_set &annotated)
1092	{
1093	return annotated.find (x: bb) != annotated.end ();
1094	}
1095
1096	static void
1097	set_bb_annotated (basic_block bb, bb_set *annotated)
1098	{
1099	annotated->insert (x: bb);
1100	}
1101
1102	/* For a given BB, set its execution count. Attach value profile if a stmt
1103	is not in PROMOTED, because we only want to promote an indirect call once.
1104	Return TRUE if BB is annotated. */
1105
1106	static bool
1107	afdo_set_bb_count (basic_block bb, const stmt_set &promoted)
1108	{
1109	gimple_stmt_iterator gsi;
1110	edge e;
1111	edge_iterator ei;
1112	gcov_type max_count = 0;
1113	bool has_annotated = false;
1114
1115	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
1116	{
1117	count_info info;
1118	gimple *stmt = gsi_stmt (i: gsi);
1119	if (gimple_clobber_p (s: stmt) || is_gimple_debug (gs: stmt))
1120	continue;
1121	if (afdo_source_profile->get_count_info (stmt, info: &info))
1122	{
1123	if (info.count > max_count)
1124	max_count = info.count;
1125	has_annotated = true;
1126	if (info.targets.size () > 0
1127	&& promoted.find (x: stmt) == promoted.end ())
1128	afdo_vpt (gsi: &gsi, map: info.targets, transform: false);
1129	}
1130	}
1131
1132	if (!has_annotated)
1133	return false;
1134
1135	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
1136	afdo_source_profile->mark_annotated (loc: gimple_location (g: gsi_stmt (i: gsi)));
1137	for (gphi_iterator gpi = gsi_start_phis (bb);
1138	!gsi_end_p (i: gpi);
1139	gsi_next (i: &gpi))
1140	{
1141	gphi *phi = gpi.phi ();
1142	size_t i;
1143	for (i = 0; i < gimple_phi_num_args (gs: phi); i++)
1144	afdo_source_profile->mark_annotated (loc: gimple_phi_arg_location (phi, i));
1145	}
1146	FOR_EACH_EDGE (e, ei, bb->succs)
1147	afdo_source_profile->mark_annotated (loc: e->goto_locus);
1148
1149	bb->count = profile_count::from_gcov_type (v: max_count).afdo ();
1150	return true;
1151	}
1152
1153	/* BB1 and BB2 are in an equivalent class iff:
1154	1. BB1 dominates BB2.
1155	2. BB2 post-dominates BB1.
1156	3. BB1 and BB2 are in the same loop nest.
1157	This function finds the equivalent class for each basic block, and
1158	stores a pointer to the first BB in its equivalent class. Meanwhile,
1159	set bb counts for the same equivalent class to be idenical. Update
1160	ANNOTATED_BB for the first BB in its equivalent class. */
1161
1162	static void
1163	afdo_find_equiv_class (bb_set *annotated_bb)
1164	{
1165	basic_block bb;
1166
1167	FOR_ALL_BB_FN (bb, cfun)
1168	bb->aux = NULL;
1169
1170	FOR_ALL_BB_FN (bb, cfun)
1171	{
1172	if (bb->aux != NULL)
1173	continue;
1174	bb->aux = bb;
1175	for (basic_block bb1 : get_dominated_by (CDI_DOMINATORS, bb))
1176	if (bb1->aux == NULL && dominated_by_p (CDI_POST_DOMINATORS, bb, bb1)
1177	&& bb1->loop_father == bb->loop_father)
1178	{
1179	bb1->aux = bb;
1180	if (bb1->count > bb->count && is_bb_annotated (bb: bb1, annotated: *annotated_bb))
1181	{
1182	bb->count = bb1->count;
1183	set_bb_annotated (bb, annotated: annotated_bb);
1184	}
1185	}
1186
1187	for (basic_block bb1 : get_dominated_by (CDI_POST_DOMINATORS, bb))
1188	if (bb1->aux == NULL && dominated_by_p (CDI_DOMINATORS, bb, bb1)
1189	&& bb1->loop_father == bb->loop_father)
1190	{
1191	bb1->aux = bb;
1192	if (bb1->count > bb->count && is_bb_annotated (bb: bb1, annotated: *annotated_bb))
1193	{
1194	bb->count = bb1->count;
1195	set_bb_annotated (bb, annotated: annotated_bb);
1196	}
1197	}
1198	}
1199	}
1200
1201	/* If a basic block's count is known, and only one of its in/out edges' count
1202	is unknown, its count can be calculated. Meanwhile, if all of the in/out
1203	edges' counts are known, then the basic block's unknown count can also be
1204	calculated. Also, if a block has a single predecessor or successor, the block's
1205	count can be propagated to that predecessor or successor.
1206	IS_SUCC is true if out edges of a basic blocks are examined.
1207	Update ANNOTATED_BB accordingly.
1208	Return TRUE if any basic block/edge count is changed. */
1209
1210	static bool
1211	afdo_propagate_edge (bool is_succ, bb_set *annotated_bb)
1212	{
1213	basic_block bb;
1214	bool changed = false;
1215
1216	FOR_EACH_BB_FN (bb, cfun)
1217	{
1218	edge e, unknown_edge = NULL;
1219	edge_iterator ei;
1220	int num_unknown_edge = 0;
1221	int num_edge = 0;
1222	profile_count total_known_count = profile_count::zero ().afdo ();
1223
1224	FOR_EACH_EDGE (e, ei, is_succ ? bb->succs : bb->preds)
1225	{
1226	gcc_assert (AFDO_EINFO (e) != NULL);
1227	if (! AFDO_EINFO (e)->is_annotated ())
1228	num_unknown_edge++, unknown_edge = e;
1229	else
1230	total_known_count += AFDO_EINFO (e)->get_count ();
1231	num_edge++;
1232	}
1233
1234	/* Be careful not to annotate block with no successor in special cases. */
1235	if (num_unknown_edge == 0 && total_known_count > bb->count)
1236	{
1237	bb->count = total_known_count;
1238	if (!is_bb_annotated (bb, annotated: *annotated_bb))
1239	set_bb_annotated (bb, annotated: annotated_bb);
1240	changed = true;
1241	}
1242	else if (num_unknown_edge == 1 && is_bb_annotated (bb, annotated: *annotated_bb))
1243	{
1244	if (bb->count > total_known_count)
1245	{
1246	profile_count new_count = bb->count - total_known_count;
1247	AFDO_EINFO(unknown_edge)->set_count(new_count);
1248	if (num_edge == 1)
1249	{
1250	basic_block succ_or_pred_bb = is_succ ? unknown_edge->dest : unknown_edge->src;
1251	if (new_count > succ_or_pred_bb->count)
1252	{
1253	succ_or_pred_bb->count = new_count;
1254	if (!is_bb_annotated (bb: succ_or_pred_bb, annotated: *annotated_bb))
1255	set_bb_annotated (bb: succ_or_pred_bb, annotated: annotated_bb);
1256	}
1257	}
1258	}
1259	else
1260	AFDO_EINFO (unknown_edge)->set_count (profile_count::zero().afdo ());
1261	AFDO_EINFO (unknown_edge)->set_annotated ();
1262	changed = true;
1263	}
1264	}
1265	return changed;
1266	}
1267
1268	/* Special propagation for circuit expressions. Because GCC translates
1269	control flow into data flow for circuit expressions. E.g.
1270	BB1:
1271	if (a && b)
1272	BB2
1273	else
1274	BB3
1275
1276	will be translated into:
1277
1278	BB1:
1279	if (a)
1280	goto BB.t1
1281	else
1282	goto BB.t3
1283	BB.t1:
1284	if (b)
1285	goto BB.t2
1286	else
1287	goto BB.t3
1288	BB.t2:
1289	goto BB.t3
1290	BB.t3:
1291	tmp = PHI (0 (BB1), 0 (BB.t1), 1 (BB.t2)
1292	if (tmp)
1293	goto BB2
1294	else
1295	goto BB3
1296
1297	In this case, we need to propagate through PHI to determine the edge
1298	count of BB1->BB.t1, BB.t1->BB.t2. */
1299
1300	static void
1301	afdo_propagate_circuit (const bb_set &annotated_bb)
1302	{
1303	basic_block bb;
1304	FOR_ALL_BB_FN (bb, cfun)
1305	{
1306	gimple *def_stmt;
1307	tree cmp_rhs, cmp_lhs;
1308	gimple *cmp_stmt = last_nondebug_stmt (bb);
1309	edge e;
1310	edge_iterator ei;
1311
1312	if (!cmp_stmt || gimple_code (g: cmp_stmt) != GIMPLE_COND)
1313	continue;
1314	cmp_rhs = gimple_cond_rhs (gs: cmp_stmt);
1315	cmp_lhs = gimple_cond_lhs (gs: cmp_stmt);
1316	if (!TREE_CONSTANT (cmp_rhs)
1317	|| !(integer_zerop (cmp_rhs) || integer_onep (cmp_rhs)))
1318	continue;
1319	if (TREE_CODE (cmp_lhs) != SSA_NAME)
1320	continue;
1321	if (!is_bb_annotated (bb, annotated: annotated_bb))
1322	continue;
1323	def_stmt = SSA_NAME_DEF_STMT (cmp_lhs);
1324	while (def_stmt && gimple_code (g: def_stmt) == GIMPLE_ASSIGN
1325	&& gimple_assign_single_p (gs: def_stmt)
1326	&& TREE_CODE (gimple_assign_rhs1 (def_stmt)) == SSA_NAME)
1327	def_stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (def_stmt));
1328	if (!def_stmt)
1329	continue;
1330	gphi *phi_stmt = dyn_cast <gphi *> (p: def_stmt);
1331	if (!phi_stmt)
1332	continue;
1333	FOR_EACH_EDGE (e, ei, bb->succs)
1334	{
1335	unsigned i, total = 0;
1336	edge only_one;
1337	bool check_value_one = (((integer_onep (cmp_rhs))
1338	^ (gimple_cond_code (gs: cmp_stmt) == EQ_EXPR))
1339	^ ((e->flags & EDGE_TRUE_VALUE) != 0));
1340	if (! AFDO_EINFO (e)->is_annotated ())
1341	continue;
1342	for (i = 0; i < gimple_phi_num_args (gs: phi_stmt); i++)
1343	{
1344	tree val = gimple_phi_arg_def (gs: phi_stmt, index: i);
1345	edge ep = gimple_phi_arg_edge (phi: phi_stmt, i);
1346
1347	if (!TREE_CONSTANT (val)
1348	|| !(integer_zerop (val) || integer_onep (val)))
1349	continue;
1350	if (check_value_one ^ integer_onep (val))
1351	continue;
1352	total++;
1353	only_one = ep;
1354	if (! (AFDO_EINFO (e)->get_count ()).nonzero_p ()
1355	&& ! AFDO_EINFO (ep)->is_annotated ())
1356	{
1357	AFDO_EINFO (ep)->set_count (profile_count::zero ().afdo ());
1358	AFDO_EINFO (ep)->set_annotated ();
1359	}
1360	}
1361	if (total == 1 && ! AFDO_EINFO (only_one)->is_annotated ())
1362	{
1363	AFDO_EINFO (only_one)->set_count (AFDO_EINFO (e)->get_count ());
1364	AFDO_EINFO (only_one)->set_annotated ();
1365	}
1366	}
1367	}
1368	}
1369
1370	/* Propagate the basic block count and edge count on the control flow
1371	graph. We do the propagation iteratively until stablize. */
1372
1373	static void
1374	afdo_propagate (bb_set *annotated_bb)
1375	{
1376	basic_block bb;
1377	bool changed = true;
1378	int i = 0;
1379
1380	FOR_ALL_BB_FN (bb, cfun)
1381	{
1382	bb->count = ((basic_block)bb->aux)->count;
1383	if (is_bb_annotated (bb: (basic_block)bb->aux, annotated: *annotated_bb))
1384	set_bb_annotated (bb, annotated: annotated_bb);
1385	}
1386
1387	while (changed && i++ < 10)
1388	{
1389	changed = false;
1390
1391	if (afdo_propagate_edge (is_succ: true, annotated_bb))
1392	changed = true;
1393	if (afdo_propagate_edge (is_succ: false, annotated_bb))
1394	changed = true;
1395	afdo_propagate_circuit (annotated_bb: *annotated_bb);
1396	}
1397	}
1398
1399	/* Propagate counts on control flow graph and calculate branch
1400	probabilities. */
1401
1402	static void
1403	afdo_calculate_branch_prob (bb_set *annotated_bb)
1404	{
1405	edge e;
1406	edge_iterator ei;
1407	basic_block bb;
1408
1409	calculate_dominance_info (CDI_POST_DOMINATORS);
1410	calculate_dominance_info (CDI_DOMINATORS);
1411	loop_optimizer_init (0);
1412
1413	FOR_ALL_BB_FN (bb, cfun)
1414	{
1415	gcc_assert (bb->aux == NULL);
1416	FOR_EACH_EDGE (e, ei, bb->succs)
1417	{
1418	gcc_assert (e->aux == NULL);
1419	e->aux = new edge_info ();
1420	}
1421	}
1422
1423	afdo_find_equiv_class (annotated_bb);
1424	afdo_propagate (annotated_bb);
1425
1426	FOR_EACH_BB_FN (bb, cfun)
1427	{
1428	int num_unknown_succ = 0;
1429	profile_count total_count = profile_count::zero ().afdo ();
1430
1431	FOR_EACH_EDGE (e, ei, bb->succs)
1432	{
1433	gcc_assert (AFDO_EINFO (e) != NULL);
1434	if (! AFDO_EINFO (e)->is_annotated ())
1435	num_unknown_succ++;
1436	else
1437	total_count += AFDO_EINFO (e)->get_count ();
1438	}
1439	if (num_unknown_succ == 0 && total_count.nonzero_p())
1440	{
1441	FOR_EACH_EDGE (e, ei, bb->succs)
1442	e->probability
1443	= AFDO_EINFO (e)->get_count ().probability_in (overall: total_count);
1444	}
1445	}
1446	FOR_ALL_BB_FN (bb, cfun)
1447	{
1448	bb->aux = NULL;
1449	FOR_EACH_EDGE (e, ei, bb->succs)
1450	if (AFDO_EINFO (e) != NULL)
1451	{
1452	delete AFDO_EINFO (e);
1453	e->aux = NULL;
1454	}
1455	}
1456
1457	loop_optimizer_finalize ();
1458	free_dominance_info (CDI_DOMINATORS);
1459	free_dominance_info (CDI_POST_DOMINATORS);
1460	}
1461
1462	/* Perform value profile transformation using AutoFDO profile. Add the
1463	promoted stmts to PROMOTED_STMTS. Return TRUE if there is any
1464	indirect call promoted. */
1465
1466	static bool
1467	afdo_vpt_for_early_inline (stmt_set *promoted_stmts)
1468	{
1469	basic_block bb;
1470	if (afdo_source_profile->get_function_instance_by_decl (
1471	decl: current_function_decl) == NULL)
1472	return false;
1473
1474	compute_fn_summary (cgraph_node::get (decl: current_function_decl), true);
1475
1476	bool has_vpt = false;
1477	FOR_EACH_BB_FN (bb, cfun)
1478	{
1479	if (!has_indirect_call (bb))
1480	continue;
1481	gimple_stmt_iterator gsi;
1482
1483	gcov_type bb_count = 0;
1484	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
1485	{
1486	count_info info;
1487	gimple *stmt = gsi_stmt (i: gsi);
1488	if (afdo_source_profile->get_count_info (stmt, info: &info))
1489	bb_count = MAX (bb_count, info.count);
1490	}
1491
1492	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
1493	{
1494	gcall *stmt = dyn_cast <gcall *> (p: gsi_stmt (i: gsi));
1495	/* IC_promotion and early_inline_2 is done in multiple iterations.
1496	No need to promoted the stmt if its in promoted_stmts (means
1497	it is already been promoted in the previous iterations). */
1498	if ((!stmt) || gimple_call_fn (gs: stmt) == NULL
1499	|| TREE_CODE (gimple_call_fn (stmt)) == FUNCTION_DECL
1500	|| promoted_stmts->find (x: stmt) != promoted_stmts->end ())
1501	continue;
1502
1503	count_info info;
1504	afdo_source_profile->get_count_info (stmt, info: &info);
1505	info.count = bb_count;
1506	if (afdo_source_profile->update_inlined_ind_target (stmt, info: &info))
1507	{
1508	/* Promote the indirect call and update the promoted_stmts. */
1509	promoted_stmts->insert (x: stmt);
1510	if (afdo_vpt (gsi: &gsi, map: info.targets, transform: true))
1511	has_vpt = true;
1512	}
1513	}
1514	}
1515
1516	if (has_vpt)
1517	{
1518	unsigned todo = optimize_inline_calls (current_function_decl);
1519	if (todo & TODO_update_ssa_any)
1520	update_ssa (TODO_update_ssa);
1521	return true;
1522	}
1523
1524	return false;
1525	}
1526
1527	/* Annotate auto profile to the control flow graph. Do not annotate value
1528	profile for stmts in PROMOTED_STMTS. */
1529
1530	static void
1531	afdo_annotate_cfg (const stmt_set &promoted_stmts)
1532	{
1533	basic_block bb;
1534	bb_set annotated_bb;
1535	const function_instance *s
1536	= afdo_source_profile->get_function_instance_by_decl (
1537	decl: current_function_decl);
1538
1539	if (s == NULL)
1540	return;
1541	cgraph_node::get (decl: current_function_decl)->count
1542	= profile_count::from_gcov_type (v: s->head_count ()).afdo ();
1543	ENTRY_BLOCK_PTR_FOR_FN (cfun)->count
1544	= profile_count::from_gcov_type (v: s->head_count ()).afdo ();
1545	EXIT_BLOCK_PTR_FOR_FN (cfun)->count = profile_count::zero ().afdo ();
1546	profile_count max_count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count;
1547
1548	FOR_EACH_BB_FN (bb, cfun)
1549	{
1550	/* As autoFDO uses sampling approach, we have to assume that all
1551	counters are zero when not seen by autoFDO. */
1552	bb->count = profile_count::zero ().afdo ();
1553	if (afdo_set_bb_count (bb, promoted: promoted_stmts))
1554	set_bb_annotated (bb, annotated: &annotated_bb);
1555	if (bb->count > max_count)
1556	max_count = bb->count;
1557	}
1558	if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count
1559	> ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb->count)
1560	{
1561	ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb->count
1562	= ENTRY_BLOCK_PTR_FOR_FN (cfun)->count;
1563	set_bb_annotated (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, annotated: &annotated_bb);
1564	}
1565	if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count
1566	> EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb->count)
1567	{
1568	EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb->count
1569	= ENTRY_BLOCK_PTR_FOR_FN (cfun)->count;
1570	set_bb_annotated (EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb, annotated: &annotated_bb);
1571	}
1572	afdo_source_profile->mark_annotated (
1573	DECL_SOURCE_LOCATION (current_function_decl));
1574	afdo_source_profile->mark_annotated (cfun->function_start_locus);
1575	afdo_source_profile->mark_annotated (cfun->function_end_locus);
1576	if (max_count.nonzero_p())
1577	{
1578	/* Calculate, propagate count and probability information on CFG. */
1579	afdo_calculate_branch_prob (annotated_bb: &annotated_bb);
1580	}
1581	update_max_bb_count ();
1582	profile_status_for_fn (cfun) = PROFILE_READ;
1583	if (flag_value_profile_transformations)
1584	{
1585	gimple_value_profile_transformations ();
1586	free_dominance_info (CDI_DOMINATORS);
1587	free_dominance_info (CDI_POST_DOMINATORS);
1588	update_ssa (TODO_update_ssa);
1589	}
1590	}
1591
1592	/* Wrapper function to invoke early inliner. */
1593
1594	static unsigned int
1595	early_inline ()
1596	{
1597	compute_fn_summary (cgraph_node::get (decl: current_function_decl), true);
1598	unsigned int todo = early_inliner (cfun);
1599	if (todo & TODO_update_ssa_any)
1600	update_ssa (TODO_update_ssa);
1601	return todo;
1602	}
1603
1604	/* Use AutoFDO profile to annoate the control flow graph.
1605	Return the todo flag. */
1606
1607	static unsigned int
1608	auto_profile (void)
1609	{
1610	struct cgraph_node *node;
1611
1612	if (symtab->state == FINISHED)
1613	return 0;
1614
1615	init_node_map (true);
1616	profile_info = autofdo::afdo_profile_info;
1617
1618	FOR_EACH_FUNCTION (node)
1619	{
1620	if (!gimple_has_body_p (node->decl))
1621	continue;
1622
1623	/* Don't profile functions produced for builtin stuff. */
1624	if (DECL_SOURCE_LOCATION (node->decl) == BUILTINS_LOCATION)
1625	continue;
1626
1627	push_cfun (DECL_STRUCT_FUNCTION (node->decl));
1628
1629	/* First do indirect call promotion and early inline to make the
1630	IR match the profiled binary before actual annotation.
1631
1632	This is needed because an indirect call might have been promoted
1633	and inlined in the profiled binary. If we do not promote and
1634	inline these indirect calls before annotation, the profile for
1635	these promoted functions will be lost.
1636
1637	e.g. foo() --indirect_call--> bar()
1638	In profiled binary, the callsite is promoted and inlined, making
1639	the profile look like:
1640
1641	foo: {
1642	loc_foo_1: count_1
1643	bar@loc_foo_2: {
1644	loc_bar_1: count_2
1645	loc_bar_2: count_3
1646	}
1647	}
1648
1649	Before AutoFDO pass, loc_foo_2 is not promoted thus not inlined.
1650	If we perform annotation on it, the profile inside bar@loc_foo2
1651	will be wasted.
1652
1653	To avoid this, we promote loc_foo_2 and inline the promoted bar
1654	function before annotation, so the profile inside bar@loc_foo2
1655	will be useful. */
1656	autofdo::stmt_set promoted_stmts;
1657	unsigned int todo = 0;
1658	for (int i = 0; i < 10; i++)
1659	{
1660	if (!flag_value_profile_transformations
1661	|| !autofdo::afdo_vpt_for_early_inline (promoted_stmts: &promoted_stmts))
1662	break;
1663	todo |= early_inline ();
1664	}
1665
1666	todo |= early_inline ();
1667	autofdo::afdo_annotate_cfg (promoted_stmts);
1668	compute_function_frequency ();
1669
1670	/* Local pure-const may imply need to fixup the cfg. */
1671	todo |= execute_fixup_cfg ();
1672	if (todo & TODO_cleanup_cfg)
1673	cleanup_tree_cfg ();
1674
1675	free_dominance_info (CDI_DOMINATORS);
1676	free_dominance_info (CDI_POST_DOMINATORS);
1677	cgraph_edge::rebuild_edges ();
1678	compute_fn_summary (cgraph_node::get (decl: current_function_decl), true);
1679	pop_cfun ();
1680	}
1681
1682	return 0;
1683	}
1684	} /* namespace autofdo. */
1685
1686	/* Read the profile from the profile data file. */
1687
1688	void
1689	read_autofdo_file (void)
1690	{
1691	if (auto_profile_file == NULL)
1692	auto_profile_file = DEFAULT_AUTO_PROFILE_FILE;
1693
1694	autofdo::afdo_profile_info = XNEW (gcov_summary);
1695	autofdo::afdo_profile_info->runs = 1;
1696	autofdo::afdo_profile_info->sum_max = 0;
1697
1698	/* Read the profile from the profile file. */
1699	autofdo::read_profile ();
1700	}
1701
1702	/* Free the resources. */
1703
1704	void
1705	end_auto_profile (void)
1706	{
1707	delete autofdo::afdo_source_profile;
1708	delete autofdo::afdo_string_table;
1709	profile_info = NULL;
1710	}
1711
1712	/* Returns TRUE if EDGE is hot enough to be inlined early. */
1713
1714	bool
1715	afdo_callsite_hot_enough_for_early_inline (struct cgraph_edge *edge)
1716	{
1717	gcov_type count
1718	= autofdo::afdo_source_profile->get_callsite_total_count (edge);
1719
1720	if (count > 0)
1721	{
1722	bool is_hot;
1723	profile_count pcount = profile_count::from_gcov_type (v: count).afdo ();
1724	gcov_summary *saved_profile_info = profile_info;
1725	/* At early inline stage, profile_info is not set yet. We need to
1726	temporarily set it to afdo_profile_info to calculate hotness. */
1727	profile_info = autofdo::afdo_profile_info;
1728	is_hot = maybe_hot_count_p (NULL, pcount);
1729	profile_info = saved_profile_info;
1730	return is_hot;
1731	}
1732
1733	return false;
1734	}
1735
1736	namespace
1737	{
1738
1739	const pass_data pass_data_ipa_auto_profile = {
1740	.type: SIMPLE_IPA_PASS, .name: "afdo", /* name */
1741	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
1742	.tv_id: TV_IPA_AUTOFDO, /* tv_id */
1743	.properties_required: 0, /* properties_required */
1744	.properties_provided: 0, /* properties_provided */
1745	.properties_destroyed: 0, /* properties_destroyed */
1746	.todo_flags_start: 0, /* todo_flags_start */
1747	.todo_flags_finish: 0, /* todo_flags_finish */
1748	};
1749
1750	class pass_ipa_auto_profile : public simple_ipa_opt_pass
1751	{
1752	public:
1753	pass_ipa_auto_profile (gcc::context *ctxt)
1754	: simple_ipa_opt_pass (pass_data_ipa_auto_profile, ctxt)
1755	{
1756	}
1757
1758	/* opt_pass methods: */
1759	bool
1760	gate (function *) final override
1761	{
1762	return flag_auto_profile;
1763	}
1764	unsigned int
1765	execute (function *) final override
1766	{
1767	return autofdo::auto_profile ();
1768	}
1769	}; // class pass_ipa_auto_profile
1770
1771	} // anon namespace
1772
1773	simple_ipa_opt_pass *
1774	make_pass_ipa_auto_profile (gcc::context *ctxt)
1775	{
1776	return new pass_ipa_auto_profile (ctxt);
1777	}
1778