1 /* Read and annotate call graph profile from the auto profile data file.
2 Copyright (C) 2014. Free Software Foundation, Inc.
3 Contributed by Dehao Chen (dehao@google.com)
5 This file is part of GCC.
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
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
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/>. */
28 #include "coretypes.h"
32 #include "basic-block.h"
33 #include "diagnostic-core.h"
37 #include "langhooks.h"
39 #include "tree-pass.h"
41 #include "tree-ssa-alias.h"
43 #include "tree-cfgcleanup.h"
44 #include "tree-ssa-operands.h"
45 #include "tree-into-ssa.h"
46 #include "internal-fn.h"
48 #include "gimple-expr.h"
51 #include "gimple-iterator.h"
52 #include "gimple-ssa.h"
54 #include "value-prof.h"
58 #include "ipa-utils.h"
59 #include "ipa-inline.h"
61 #include "dwarf2asm.h"
62 #include "tree-inline.h"
63 #include "auto-profile.h"
65 /* The following routines implements AutoFDO optimization.
67 This optimization uses sampling profiles to annotate basic block counts
68 and uses heuristics to estimate branch probabilities.
70 There are three phases in AutoFDO:
72 Phase 1: Read profile from the profile data file.
73 The following info is read from the profile datafile:
74 * string_table: a map between function name and its index.
75 * autofdo_source_profile: a map from function_instance name to
76 function_instance. This is represented as a forest of
78 * WorkingSet: a histogram of how many instructions are covered for a
79 given percentage of total cycles. This is describing the binary
80 level information (not source level). This info is used to help
81 decide if we want aggressive optimizations that could increase
82 code footprint (e.g. loop unroll etc.)
83 A function instance is an instance of function that could either be a
84 standalone symbol, or a clone of a function that is inlined into another
87 Phase 2: Early inline + valur profile transformation.
88 Early inline uses autofdo_source_profile to find if a callsite is:
89 * inlined in the profiled binary.
90 * callee body is hot in the profiling run.
91 If both condition satisfies, early inline will inline the callsite
92 regardless of the code growth.
93 Phase 2 is an iterative process. During each iteration, we also check
94 if an indirect callsite is promoted and inlined in the profiling run.
95 If yes, vpt will happen to force promote it and in the next iteration,
96 einline will inline the promoted callsite in the next iteration.
98 Phase 3: Annotate control flow graph.
99 AutoFDO uses a separate pass to:
100 * Annotate basic block count
101 * Estimate branch probability
103 After the above 3 phases, all profile is readily annotated on the GCC IR.
104 AutoFDO tries to reuse all FDO infrastructure as much as possible to make
105 use of the profile. E.g. it uses existing mechanism to calculate the basic
106 block/edge frequency, as well as the cgraph node/edge count.
109 #define DEFAULT_AUTO_PROFILE_FILE "fbdata.afdo"
114 /* Represent a source location: (function_decl, lineno). */
115 typedef std::pair
<tree
, unsigned> decl_lineno
;
117 /* Represent an inline stack. vector[0] is the leaf node. */
118 typedef auto_vec
<decl_lineno
> inline_stack
;
120 /* String array that stores function names. */
121 typedef auto_vec
<char *> string_vector
;
123 /* Map from function name's index in string_table to target's
125 typedef std::map
<unsigned, gcov_type
> icall_target_map
;
127 /* Set of gimple stmts. Used to track if the stmt has already been promoted
129 typedef std::set
<gimple
> stmt_set
;
131 /* Represent count info of an inline stack. */
134 /* Sampled count of the inline stack. */
137 /* Map from indirect call target to its sample count. */
138 icall_target_map targets
;
140 /* Whether this inline stack is already used in annotation.
142 Each inline stack should only be used to annotate IR once.
143 This will be enforced when instruction-level discriminator
148 /* operator< for "const char *". */
149 struct string_compare
151 bool operator()(const char *a
, const char *b
) const
153 return strcmp (a
, b
) < 0;
157 /* Store a string array, indexed by string position in the array. */
166 /* For a given string, returns its index. */
167 int get_index (const char *name
) const;
169 /* For a given decl, returns the index of the decl name. */
170 int get_index_by_decl (tree decl
) const;
172 /* For a given index, returns the string. */
173 const char *get_name (int index
) const;
175 /* Read profile, return TRUE on success. */
179 typedef std::map
<const char *, unsigned, string_compare
> string_index_map
;
180 string_vector vector_
;
181 string_index_map map_
;
184 /* Profile of a function instance:
185 1. total_count of the function.
186 2. head_count (entry basic block count) of the function (only valid when
187 function is a top-level function_instance, i.e. it is the original copy
188 instead of the inlined copy).
189 3. map from source location (decl_lineno) to profile (count_info).
190 4. map from callsite to callee function_instance. */
191 class function_instance
194 typedef auto_vec
<function_instance
*> function_instance_stack
;
196 /* Read the profile and return a function_instance with head count as
197 HEAD_COUNT. Recursively read callsites to create nested function_instances
198 too. STACK is used to track the recursive creation process. */
199 static function_instance
*
200 read_function_instance (function_instance_stack
*stack
,
201 gcov_type head_count
);
203 /* Recursively deallocate all callsites (nested function_instances). */
204 ~function_instance ();
223 /* Traverse callsites of the current function_instance to find one at the
224 location of LINENO. */
225 function_instance
*get_function_instance_by_decl (unsigned lineno
,
228 /* Store the profile info for LOC in INFO. Return TRUE if profile info
230 bool get_count_info (location_t loc
, count_info
*info
) const;
232 /* Read the inlined indirect call target profile for STMT and store it in
233 MAP, return the total count for all inlined indirect calls. */
234 gcov_type
find_icall_target_map (gimple stmt
, icall_target_map
*map
) const;
236 /* Sum of counts that is used during annotation. */
237 gcov_type
total_annotated_count () const;
239 /* Mark LOC as annotated. */
240 void mark_annotated (location_t loc
);
243 /* Callsite, represented as (decl_lineno, callee_function_name_index). */
244 typedef std::pair
<unsigned, unsigned> callsite
;
246 /* Map from callsite to callee function_instance. */
247 typedef std::map
<callsite
, function_instance
*> callsite_map
;
249 function_instance (unsigned name
, gcov_type head_count
)
250 : name_ (name
), total_count_ (0), head_count_ (head_count
)
254 /* Map from source location (decl_lineno) to profile (count_info). */
255 typedef std::map
<unsigned, count_info
> position_count_map
;
257 /* function_instance name index in the string_table. */
260 /* Total sample count. */
261 gcov_type total_count_
;
263 /* Entry BB's sample count. */
264 gcov_type head_count_
;
266 /* Map from callsite location to callee function_instance. */
267 callsite_map callsites
;
269 /* Map from source location to count_info. */
270 position_count_map pos_counts
;
273 /* Profile for all functions. */
274 class autofdo_source_profile
277 static autofdo_source_profile
*
280 autofdo_source_profile
*map
= new autofdo_source_profile ();
288 ~autofdo_source_profile ();
290 /* For a given DECL, returns the top-level function_instance. */
291 function_instance
*get_function_instance_by_decl (tree decl
) const;
293 /* Find count_info for a given gimple STMT. If found, store the count_info
294 in INFO and return true; otherwise return false. */
295 bool get_count_info (gimple stmt
, count_info
*info
) const;
297 /* Find total count of the callee of EDGE. */
298 gcov_type
get_callsite_total_count (struct cgraph_edge
*edge
) const;
300 /* Update value profile INFO for STMT from the inlined indirect callsite.
301 Return true if INFO is updated. */
302 bool update_inlined_ind_target (gimple stmt
, count_info
*info
);
304 /* Mark LOC as annotated. */
305 void mark_annotated (location_t loc
);
307 /* Writes the profile annotation status for each function in an elf
309 void write_annotated_count () const;
312 /* Map from function_instance name index (in string_table) to
313 function_instance. */
314 typedef std::map
<unsigned, function_instance
*> name_function_instance_map
;
316 autofdo_source_profile () {}
318 /* Read AutoFDO profile and returns TRUE on success. */
321 /* Return the function_instance in the profile that correspond to the
324 get_function_instance_by_inline_stack (const inline_stack
&stack
) const;
326 name_function_instance_map map_
;
329 /* Module profile. */
330 class autofdo_module_profile
{
332 static autofdo_module_profile
*create ()
334 autofdo_module_profile
*map
= new autofdo_module_profile ();
341 /* For a given module NAME, returns this module's gcov_module_info. */
342 gcov_module_info
*get_module(const char *name
) const
344 name_target_map::const_iterator iter
= map_
.find (name
);
345 return iter
== map_
.end() ? NULL
: iter
->second
.second
;
348 /* For a given module NAME, returns this module's aux-modules. */
349 const string_vector
*get_aux_modules(const char *name
) const
351 name_target_map::const_iterator iter
= map_
.find (name
);
352 return iter
== map_
.end() ? NULL
: &iter
->second
.first
;
356 autofdo_module_profile () {}
359 typedef std::pair
<string_vector
, gcov_module_info
*> AuxInfo
;
360 typedef std::map
<const char *, AuxInfo
, string_compare
> name_target_map
;
361 /* Map from module name to (aux_modules, gcov_module_info). */
362 name_target_map map_
;
366 /* Store the strings read from the profile data file. */
367 static string_table
*afdo_string_table
;
369 /* Store the AutoFDO source profile. */
370 static autofdo_source_profile
*afdo_source_profile
;
372 /* Store the AutoFDO module profile. */
373 static autofdo_module_profile
*afdo_module_profile
;
375 /* gcov_ctr_summary structure to store the profile_info. */
376 static struct gcov_ctr_summary
*afdo_profile_info
;
378 /* Helper functions. */
380 /* Return the original name of NAME: strip the suffix that starts
381 with '.' Caller is responsible for freeing RET. */
384 get_original_name (const char *name
)
386 char *ret
= xstrdup (name
);
387 char *find
= strchr (ret
, '.');
393 /* Return the combined location, which is a 32bit integer in which
394 higher 16 bits stores the line offset of LOC to the start lineno
395 of DECL, The lower 16 bits stores the discrimnator. */
398 get_combined_location (location_t loc
, tree decl
)
400 /* TODO: allow more bits for line and less bits for discriminator. */
401 return ((LOCATION_LINE (loc
) - DECL_SOURCE_LINE (decl
)) << 16)
402 | get_discriminator_from_locus (loc
);
405 /* Return the function decl of a given lexical BLOCK. */
408 get_function_decl_from_block (tree block
)
412 if (LOCATION_LOCUS (BLOCK_SOURCE_LOCATION (block
) == UNKNOWN_LOCATION
))
415 for (decl
= BLOCK_ABSTRACT_ORIGIN (block
);
416 decl
&& (TREE_CODE (decl
) == BLOCK
);
417 decl
= BLOCK_ABSTRACT_ORIGIN (decl
))
418 if (TREE_CODE (decl
) == FUNCTION_DECL
)
423 /* Store inline stack for STMT in STACK. */
426 get_inline_stack (location_t locus
, inline_stack
*stack
)
428 if (LOCATION_LOCUS (locus
) == UNKNOWN_LOCATION
)
431 tree block
= LOCATION_BLOCK (locus
);
432 if (block
&& TREE_CODE (block
) == BLOCK
)
435 for (block
= BLOCK_SUPERCONTEXT (block
);
436 block
&& (TREE_CODE (block
) == BLOCK
);
437 block
= BLOCK_SUPERCONTEXT (block
))
439 location_t tmp_locus
= BLOCK_SOURCE_LOCATION (block
);
440 if (LOCATION_LOCUS (tmp_locus
) == UNKNOWN_LOCATION
)
443 tree decl
= get_function_decl_from_block (block
);
445 std::make_pair (decl
, get_combined_location (locus
, decl
)));
451 std::make_pair (current_function_decl
,
452 get_combined_location (locus
, current_function_decl
)));
455 /* Return STMT's combined location, which is a 32bit integer in which
456 higher 16 bits stores the line offset of LOC to the start lineno
457 of DECL, The lower 16 bits stores the discrimnator. */
460 get_relative_location_for_stmt (gimple stmt
)
462 location_t locus
= gimple_location (stmt
);
463 if (LOCATION_LOCUS (locus
) == UNKNOWN_LOCATION
)
464 return UNKNOWN_LOCATION
;
466 for (tree block
= gimple_block (stmt
); block
&& (TREE_CODE (block
) == BLOCK
);
467 block
= BLOCK_SUPERCONTEXT (block
))
468 if (LOCATION_LOCUS (BLOCK_SOURCE_LOCATION (block
)) != UNKNOWN_LOCATION
)
469 return get_combined_location (locus
,
470 get_function_decl_from_block (block
));
471 return get_combined_location (locus
, current_function_decl
);
474 /* Return true if BB contains indirect call. */
477 has_indirect_call (basic_block bb
)
479 gimple_stmt_iterator gsi
;
481 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
483 gimple stmt
= gsi_stmt (gsi
);
484 if (gimple_code (stmt
) == GIMPLE_CALL
&& !gimple_call_internal_p (stmt
)
485 && (gimple_call_fn (stmt
) == NULL
486 || TREE_CODE (gimple_call_fn (stmt
)) != FUNCTION_DECL
))
492 /* Member functions for string_table. */
496 string_table::~string_table ()
498 for (unsigned i
= 0; i
< vector_
.length (); i
++)
503 /* Return the index of a given function NAME. Return -1 if NAME is not
504 found in string table. */
507 string_table::get_index (const char *name
) const
511 string_index_map::const_iterator iter
= map_
.find (name
);
512 if (iter
== map_
.end ())
518 /* Return the index of a given function DECL. Return -1 if DECL is not
519 found in string table. */
522 string_table::get_index_by_decl (tree decl
) const
525 = get_original_name (IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl
)));
526 int ret
= get_index (name
);
530 ret
= get_index (lang_hooks
.dwarf_name (decl
, 0));
533 if (DECL_ABSTRACT_ORIGIN (decl
))
534 return get_index_by_decl (DECL_ABSTRACT_ORIGIN (decl
));
539 /* Return the function name of a given INDEX. */
542 string_table::get_name (int index
) const
544 gcc_assert (index
> 0 && index
< (int)vector_
.length ());
545 return vector_
[index
];
548 /* Read the string table. Return TRUE if reading is successful. */
551 string_table::read ()
553 if (gcov_read_unsigned () != GCOV_TAG_AFDO_FILE_NAMES
)
555 /* Skip the length of the section. */
556 gcov_read_unsigned ();
557 /* Read in the file name table. */
558 unsigned string_num
= gcov_read_unsigned ();
559 for (unsigned i
= 0; i
< string_num
; i
++)
561 vector_
.safe_push (get_original_name (gcov_read_string ()));
562 map_
[vector_
.last ()] = i
;
567 /* Member functions for function_instance. */
569 function_instance::~function_instance ()
571 for (callsite_map::iterator iter
= callsites
.begin ();
572 iter
!= callsites
.end (); ++iter
)
576 /* Traverse callsites of the current function_instance to find one at the
577 location of LINENO and callee name represented in DECL. */
580 function_instance::get_function_instance_by_decl (unsigned lineno
,
583 int func_name_idx
= afdo_string_table
->get_index_by_decl (decl
);
584 if (func_name_idx
!= -1)
586 callsite_map::const_iterator ret
587 = callsites
.find (std::make_pair (lineno
, func_name_idx
));
588 if (ret
!= callsites
.end ())
592 = afdo_string_table
->get_index (lang_hooks
.dwarf_name (decl
, 0));
593 if (func_name_idx
!= -1)
595 callsite_map::const_iterator ret
596 = callsites
.find (std::make_pair (lineno
, func_name_idx
));
597 if (ret
!= callsites
.end ())
600 if (DECL_ABSTRACT_ORIGIN (decl
))
601 return get_function_instance_by_decl (lineno
, DECL_ABSTRACT_ORIGIN (decl
));
606 /* Store the profile info for LOC in INFO. Return TRUE if profile info
610 function_instance::get_count_info (location_t loc
, count_info
*info
) const
612 position_count_map::const_iterator iter
= pos_counts
.find (loc
);
613 if (iter
== pos_counts
.end ())
615 *info
= iter
->second
;
619 /* Mark LOC as annotated. */
622 function_instance::mark_annotated (location_t loc
)
624 position_count_map::iterator iter
= pos_counts
.find (loc
);
625 if (iter
== pos_counts
.end ())
627 iter
->second
.annotated
= true;
630 /* Read the inlinied indirect call target profile for STMT and store it in
631 MAP, return the total count for all inlined indirect calls. */
634 function_instance::find_icall_target_map (gimple stmt
,
635 icall_target_map
*map
) const
638 unsigned stmt_offset
= get_relative_location_for_stmt (stmt
);
640 for (callsite_map::const_iterator iter
= callsites
.begin ();
641 iter
!= callsites
.end (); ++iter
)
643 unsigned callee
= iter
->second
->name ();
644 /* Check if callsite location match the stmt. */
645 if (iter
->first
.first
!= stmt_offset
)
647 struct cgraph_node
*node
= find_func_by_global_id (
648 (unsigned long long) afdo_string_table
->get_name (callee
), true);
651 if (!check_ic_target (stmt
, node
))
653 if (!node
->definition
)
655 (*map
)[callee
] = iter
->second
->total_count ();
656 ret
+= iter
->second
->total_count ();
661 /* Read the profile and create a function_instance with head count as
662 HEAD_COUNT. Recursively read callsites to create nested function_instances
663 too. STACK is used to track the recursive creation process. */
665 /* function instance profile format:
669 NUM_POS_COUNTS: 4 bytes
670 NUM_CALLSITES: 4 byte
672 POS_1_OFFSET: 4 bytes
676 VALUE_PROFILE_TYPE: 4 bytes
686 CALLSITE_1_OFFSET: 4 bytes
687 FUNCTION_INSTANCE_PROFILE (nested)
693 function_instance::read_function_instance (function_instance_stack
*stack
,
694 gcov_type head_count
)
696 unsigned name
= gcov_read_unsigned ();
697 unsigned num_pos_counts
= gcov_read_unsigned ();
698 unsigned num_callsites
= gcov_read_unsigned ();
699 function_instance
*s
= new function_instance (name
, head_count
);
700 stack
->safe_push (s
);
702 for (unsigned i
= 0; i
< num_pos_counts
; i
++)
704 unsigned offset
= gcov_read_unsigned ();
705 unsigned num_targets
= gcov_read_unsigned ();
706 gcov_type count
= gcov_read_counter ();
707 s
->pos_counts
[offset
].count
= count
;
708 for (unsigned j
= 0; j
< stack
->length (); j
++)
709 (*stack
)[j
]->total_count_
+= count
;
710 for (unsigned j
= 0; j
< num_targets
; j
++)
712 /* Only indirect call target histogram is supported now. */
713 gcov_read_unsigned ();
714 gcov_type target_idx
= gcov_read_counter ();
715 s
->pos_counts
[offset
].targets
[target_idx
] = gcov_read_counter ();
718 for (unsigned i
= 0; i
< num_callsites
; i
++)
720 unsigned offset
= gcov_read_unsigned ();
721 function_instance
*callee_function_instance
722 = read_function_instance (stack
, 0);
723 s
->callsites
[std::make_pair (offset
, callee_function_instance
->name ())]
724 = callee_function_instance
;
730 /* Sum of counts that is used during annotation. */
733 function_instance::total_annotated_count () const
736 for (callsite_map::const_iterator iter
= callsites
.begin ();
737 iter
!= callsites
.end (); ++iter
)
738 ret
+= iter
->second
->total_annotated_count ();
739 for (position_count_map::const_iterator iter
= pos_counts
.begin ();
740 iter
!= pos_counts
.end (); ++iter
)
741 if (iter
->second
.annotated
)
742 ret
+= iter
->second
.count
;
747 autofdo_source_profile::write_annotated_count () const
749 /* We store the annotation info as a string in the format of:
751 function_name:total_count:annotated_count
753 Because different modules may output the annotation info for a same
754 function, we set the section as SECTION_MERGE so that we don't have
755 replicated info in the final binary. */
756 switch_to_section (get_section (
757 ".gnu.switches.text.annotation",
758 SECTION_DEBUG
| SECTION_MERGE
| SECTION_STRINGS
| (SECTION_ENTSIZE
& 1),
760 for (name_function_instance_map::const_iterator iter
= map_
.begin ();
761 iter
!= map_
.end (); ++iter
)
762 if (iter
->second
->total_count () > 0)
766 "%s:"HOST_WIDEST_INT_PRINT_DEC
":"HOST_WIDEST_INT_PRINT_DEC
,
767 afdo_string_table
->get_name (iter
->first
),
768 iter
->second
->total_count (),
769 iter
->second
->total_annotated_count ());
770 dw2_asm_output_nstring (buf
, (size_t)-1, NULL
);
775 /* Member functions for autofdo_source_profile. */
777 autofdo_source_profile::~autofdo_source_profile ()
779 for (name_function_instance_map::const_iterator iter
= map_
.begin ();
780 iter
!= map_
.end (); ++iter
)
784 /* For a given DECL, returns the top-level function_instance. */
787 autofdo_source_profile::get_function_instance_by_decl (tree decl
) const
789 int index
= afdo_string_table
->get_index_by_decl (decl
);
792 name_function_instance_map::const_iterator ret
= map_
.find (index
);
793 return ret
== map_
.end () ? NULL
: ret
->second
;
796 /* Find count_info for a given gimple STMT. If found, store the count_info
797 in INFO and return true; otherwise return false. */
800 autofdo_source_profile::get_count_info (gimple stmt
, count_info
*info
) const
802 if (LOCATION_LOCUS (gimple_location (stmt
)) == cfun
->function_end_locus
)
806 get_inline_stack (gimple_location (stmt
), &stack
);
807 if (stack
.length () == 0)
809 function_instance
*s
= get_function_instance_by_inline_stack (stack
);
812 return s
->get_count_info (stack
[0].second
, info
);
815 /* Mark LOC as annotated. */
818 autofdo_source_profile::mark_annotated (location_t loc
)
821 get_inline_stack (loc
, &stack
);
822 if (stack
.length () == 0)
824 function_instance
*s
= get_function_instance_by_inline_stack (stack
);
827 s
->mark_annotated (stack
[0].second
);
830 /* Update value profile INFO for STMT from the inlined indirect callsite.
831 Return true if INFO is updated. */
834 autofdo_source_profile::update_inlined_ind_target (gimple stmt
,
837 if (LOCATION_LOCUS (gimple_location (stmt
)) == cfun
->function_end_locus
)
841 get_count_info (stmt
, &old_info
);
843 for (icall_target_map::const_iterator iter
= old_info
.targets
.begin ();
844 iter
!= old_info
.targets
.end (); ++iter
)
845 total
+= iter
->second
;
847 /* Program behavior changed, original promoted (and inlined) target is not
848 hot any more. Will avoid promote the original target.
850 To check if original promoted target is still hot, we check the total
851 count of the unpromoted targets (stored in old_info). If it is no less
852 than half of the callsite count (stored in INFO), the original promoted
853 target is considered not hot any more. */
854 if (total
>= info
->count
/ 2)
858 get_inline_stack (gimple_location (stmt
), &stack
);
859 if (stack
.length () == 0)
861 function_instance
*s
= get_function_instance_by_inline_stack (stack
);
864 icall_target_map map
;
865 if (s
->find_icall_target_map (stmt
, &map
) == 0)
867 for (icall_target_map::const_iterator iter
= map
.begin ();
868 iter
!= map
.end (); ++iter
)
869 info
->targets
[iter
->first
] = iter
->second
;
873 /* Find total count of the callee of EDGE. */
876 autofdo_source_profile::get_callsite_total_count (
877 struct cgraph_edge
*edge
) const
880 stack
.safe_push (std::make_pair (edge
->callee
->decl
, 0));
881 get_inline_stack (gimple_location (edge
->call_stmt
), &stack
);
883 function_instance
*s
= get_function_instance_by_inline_stack (stack
);
887 return s
->total_count ();
890 /* Read AutoFDO profile and returns TRUE on success. */
892 /* source profile format:
894 GCOV_TAG_AFDO_FUNCTION: 4 bytes
896 NUM_FUNCTIONS: 4 bytes
900 FUNCTION_INSTANCE_N. */
903 autofdo_source_profile::read ()
905 if (gcov_read_unsigned () != GCOV_TAG_AFDO_FUNCTION
)
907 inform (0, "Not expected TAG.");
911 /* Skip the length of the section. */
912 gcov_read_unsigned ();
914 /* Read in the function/callsite profile, and store it in local
916 unsigned function_num
= gcov_read_unsigned ();
917 for (unsigned i
= 0; i
< function_num
; i
++)
919 function_instance::function_instance_stack stack
;
920 function_instance
*s
= function_instance::read_function_instance (
921 &stack
, gcov_read_counter ());
922 afdo_profile_info
->sum_all
+= s
->total_count ();
923 map_
[s
->name ()] = s
;
928 /* Return the function_instance in the profile that correspond to the
932 autofdo_source_profile::get_function_instance_by_inline_stack (
933 const inline_stack
&stack
) const
935 name_function_instance_map::const_iterator iter
= map_
.find (
936 afdo_string_table
->get_index_by_decl (stack
[stack
.length () - 1].first
));
937 if (iter
== map_
.end())
939 function_instance
*s
= iter
->second
;
940 for (unsigned i
= stack
.length() - 1; i
> 0; i
--)
942 s
= s
->get_function_instance_by_decl (
943 stack
[i
].second
, stack
[i
- 1].first
);
951 /* Member functions for autofdo_module_profile. */
954 autofdo_module_profile::read ()
956 /* Read in the module info. */
957 if (gcov_read_unsigned () != GCOV_TAG_AFDO_MODULE_GROUPING
)
959 inform (0, "Not expected TAG.");
962 /* Skip the length of the section. */
963 gcov_read_unsigned ();
965 /* Read in the file name table. */
966 unsigned total_module_num
= gcov_read_unsigned ();
967 for (unsigned i
= 0; i
< total_module_num
; i
++)
969 char *name
= xstrdup (gcov_read_string ());
970 unsigned total_num
= 0;
971 unsigned num_array
[7];
972 unsigned exported
= gcov_read_unsigned ();
973 unsigned lang
= gcov_read_unsigned ();
974 unsigned ggc_memory
= gcov_read_unsigned ();
975 for (unsigned j
= 0; j
< 7; j
++)
977 num_array
[j
] = gcov_read_unsigned ();
978 total_num
+= num_array
[j
];
980 gcov_module_info
*module
= XCNEWVAR (
982 sizeof (gcov_module_info
) + sizeof (char *) * total_num
);
984 std::pair
<name_target_map::iterator
, bool> ret
= map_
.insert(
985 name_target_map::value_type (name
, AuxInfo()));
986 gcc_assert (ret
.second
);
987 ret
.first
->second
.second
= module
;
988 module
->ident
= i
+ 1;
990 module
->ggc_memory
= ggc_memory
;
991 module
->num_quote_paths
= num_array
[1];
992 module
->num_bracket_paths
= num_array
[2];
993 module
->num_system_paths
= num_array
[3];
994 module
->num_cpp_defines
= num_array
[4];
995 module
->num_cpp_includes
= num_array
[5];
996 module
->num_cl_args
= num_array
[6];
997 module
->source_filename
= name
;
998 module
->is_primary
= strcmp (name
, in_fnames
[0]) == 0;
999 module
->flags
= module
->is_primary
? exported
: 1;
1000 for (unsigned j
= 0; j
< num_array
[0]; j
++)
1001 ret
.first
->second
.first
.safe_push (xstrdup (gcov_read_string ()));
1002 for (unsigned j
= 0; j
< total_num
- num_array
[0]; j
++)
1003 module
->string_array
[j
] = xstrdup (gcov_read_string ());
1008 /* Read data from profile data file. */
1013 if (gcov_open (auto_profile_file
, 1) == 0)
1014 error ("Cannot open profile file %s.", auto_profile_file
);
1016 if (gcov_read_unsigned () != GCOV_DATA_MAGIC
)
1017 error ("AutoFDO profile magic number does not mathch.");
1019 /* Skip the version number. */
1020 gcov_read_unsigned ();
1022 /* Skip the empty integer. */
1023 gcov_read_unsigned ();
1026 afdo_string_table
= new string_table ();
1027 if (!afdo_string_table
->read())
1028 error ("Cannot read string table from %s.", auto_profile_file
);
1030 /* autofdo_source_profile. */
1031 afdo_source_profile
= autofdo_source_profile::create ();
1032 if (afdo_source_profile
== NULL
)
1033 error ("Cannot read function profile from %s.", auto_profile_file
);
1035 /* autofdo_module_profile. */
1036 afdo_module_profile
= autofdo_module_profile::create ();
1037 if (afdo_module_profile
== NULL
)
1038 error ("Cannot read module profile from %s.", auto_profile_file
);
1040 /* Read in the working set. */
1041 if (gcov_read_unsigned () != GCOV_TAG_AFDO_WORKING_SET
)
1042 error ("Cannot read working set from %s.", auto_profile_file
);
1044 /* Skip the length of the section. */
1045 gcov_read_unsigned ();
1046 gcov_working_set_t set
[128];
1047 for (unsigned i
= 0; i
< 128; i
++)
1049 set
[i
].num_counters
= gcov_read_unsigned ();
1050 set
[i
].min_counter
= gcov_read_counter ();
1052 add_working_set (set
);
1055 /* Read in the auxiliary modules for the current primary module. */
1058 read_aux_modules (void)
1060 gcov_module_info
*module
= afdo_module_profile
->get_module (in_fnames
[0]);
1064 const string_vector
*aux_modules
=
1065 afdo_module_profile
->get_aux_modules (in_fnames
[0]);
1066 unsigned num_aux_modules
= aux_modules
? aux_modules
->length() : 0;
1068 module_infos
= XCNEWVEC (gcov_module_info
*, num_aux_modules
+ 1);
1069 module_infos
[0] = module
;
1070 primary_module_id
= module
->ident
;
1071 record_module_name (module
->ident
, lbasename (in_fnames
[0]));
1072 if (aux_modules
== NULL
)
1074 unsigned curr_module
= 1, max_group
= PARAM_VALUE (PARAM_MAX_LIPO_GROUP
);
1077 FOR_EACH_VEC_ELT (*aux_modules
, i
, str
)
1079 gcov_module_info
*aux_module
= afdo_module_profile
->get_module (str
);
1080 if (aux_module
== module
)
1082 if (aux_module
== NULL
)
1085 inform (0, "aux module %s cannot be found.", str
);
1088 if ((aux_module
->lang
& GCOV_MODULE_LANG_MASK
) !=
1089 (module
->lang
& GCOV_MODULE_LANG_MASK
))
1092 inform (0, "Not importing %s: source language"
1093 " different from primary module's source language", str
);
1096 if ((aux_module
->lang
& GCOV_MODULE_ASM_STMTS
)
1097 && flag_ripa_disallow_asm_modules
)
1100 inform (0, "Not importing %s: contains "
1101 "assembler statements", str
);
1104 if (max_group
!= 0 && curr_module
>= max_group
)
1107 inform (0, "Not importing %s: maximum group size reached", str
);
1110 if (incompatible_cl_args (module
, aux_module
))
1113 inform (0, "Not importing %s: command-line"
1114 " arguments not compatible with primary module", str
);
1117 module_infos
[curr_module
++] = aux_module
;
1118 add_input_filename (str
);
1119 record_module_name (aux_module
->ident
, lbasename (str
));
1123 /* From AutoFDO profiles, find values inside STMT for that we want to measure
1124 histograms for indirect-call optimization.
1126 This function is actually served for 2 purposes:
1127 Â Â * before annotation, we need to mark histogram, promote and inline
1128 Â Â * after annotation, we just need to mark, and let follow-up logic to
1129 Â Â Â decide if it needs to promote and inline. */
1132 afdo_indirect_call (gimple_stmt_iterator
*gsi
, const icall_target_map
&map
)
1134 gimple stmt
= gsi_stmt (*gsi
);
1137 if (map
.size () == 0 || gimple_code (stmt
) != GIMPLE_CALL
1138 || gimple_call_fndecl (stmt
) != NULL_TREE
)
1141 callee
= gimple_call_fn (stmt
);
1143 histogram_value hist
= gimple_alloc_histogram_value (
1144 cfun
, HIST_TYPE_INDIR_CALL_TOPN
, stmt
, callee
);
1145 hist
->n_counters
= (GCOV_ICALL_TOPN_VAL
<< 2) + 1;
1146 hist
->hvalue
.counters
= XNEWVEC (gcov_type
, hist
->n_counters
);
1147 gimple_add_histogram_value (cfun
, stmt
, hist
);
1149 gcov_type total
= 0;
1150 icall_target_map::const_iterator max_iter1
= map
.end ();
1151 icall_target_map::const_iterator max_iter2
= map
.end ();
1153 for (icall_target_map::const_iterator iter
= map
.begin ();
1154 iter
!= map
.end (); ++iter
)
1156 total
+= iter
->second
;
1157 if (max_iter1
== map
.end () || max_iter1
->second
< iter
->second
)
1159 max_iter2
= max_iter1
;
1162 else if (max_iter2
== map
.end () || max_iter2
->second
< iter
->second
)
1166 hist
->hvalue
.counters
[0] = total
;
1167 hist
->hvalue
.counters
[1] = (unsigned long long)
1168 afdo_string_table
->get_name (max_iter1
->first
);
1169 hist
->hvalue
.counters
[2] = max_iter1
->second
;
1170 if (max_iter2
!= map
.end())
1172 hist
->hvalue
.counters
[3] = (unsigned long long)
1173 afdo_string_table
->get_name (max_iter2
->first
);
1174 hist
->hvalue
.counters
[4] = max_iter2
->second
;
1178 hist
->hvalue
.counters
[3] = 0;
1179 hist
->hvalue
.counters
[4] = 0;
1183 /* From AutoFDO profiles, find values inside STMT for that we want to measure
1184 histograms and adds them to list VALUES. */
1187 afdo_vpt (gimple_stmt_iterator
*gsi
, const icall_target_map
&map
)
1189 afdo_indirect_call (gsi
, map
);
1192 typedef std::set
<basic_block
> bb_set
;
1193 typedef std::set
<edge
> edge_set
;
1196 is_bb_annotated (const basic_block bb
, const bb_set
&annotated
)
1198 return annotated
.find (bb
) != annotated
.end ();
1202 set_bb_annotated (basic_block bb
, bb_set
*annotated
)
1204 annotated
->insert (bb
);
1208 is_edge_annotated (const edge e
, const edge_set
&annotated
)
1210 return annotated
.find (e
) != annotated
.end ();
1214 set_edge_annotated (edge e
, edge_set
*annotated
)
1216 annotated
->insert (e
);
1219 /* For a given BB, set its execution count. Attach value profile if a stmt
1220 is not in PROMOTED, because we only want to promot an indirect call once.
1221 Return TRUE if BB is annotated. */
1224 afdo_set_bb_count (basic_block bb
, const stmt_set
&promoted
)
1226 gimple_stmt_iterator gsi
;
1229 gcov_type max_count
= 0;
1230 bool has_annotated
= false;
1232 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1235 gimple stmt
= gsi_stmt (gsi
);
1236 if (gimple_clobber_p (stmt
) || is_gimple_debug (stmt
))
1238 if (afdo_source_profile
->get_count_info (stmt
, &info
))
1242 if (info
.count
> max_count
)
1243 max_count
= info
.count
;
1244 has_annotated
= true;
1245 if (info
.targets
.size () > 0
1246 && promoted
.find (stmt
) == promoted
.end ())
1247 afdo_vpt (&gsi
, info
.targets
);
1254 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1255 afdo_source_profile
->mark_annotated (gimple_location (gsi_stmt (gsi
)));
1256 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1258 gimple phi
= gsi_stmt (gsi
);
1260 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1261 afdo_source_profile
->mark_annotated (gimple_phi_arg_location (phi
, i
));
1263 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1264 afdo_source_profile
->mark_annotated (e
->goto_locus
);
1266 bb
->count
= max_count
;
1270 /* BB1 and BB2 are in an equivalent class iff:
1271 1. BB1 dominates BB2.
1272 2. BB2 post-dominates BB1.
1273 3. BB1 and BB2 are in the same loop nest.
1274 This function finds the equivalent class for each basic block, and
1275 stores a pointer to the first BB in its equivalent class. Meanwhile,
1276 set bb counts for the same equivalent class to be idenical. Update
1277 ANNOTATED_BB for the first BB in its equivalent class. */
1280 afdo_find_equiv_class (bb_set
*annotated_bb
)
1284 FOR_ALL_BB_FN (bb
, cfun
)
1287 FOR_ALL_BB_FN (bb
, cfun
)
1289 vec
<basic_block
> dom_bbs
;
1293 if (bb
->aux
!= NULL
)
1296 dom_bbs
= get_all_dominated_blocks (CDI_DOMINATORS
, bb
);
1297 FOR_EACH_VEC_ELT (dom_bbs
, i
, bb1
)
1298 if (bb1
->aux
== NULL
&& dominated_by_p (CDI_POST_DOMINATORS
, bb
, bb1
)
1299 && bb1
->loop_father
== bb
->loop_father
)
1302 if (bb1
->count
> bb
->count
&& is_bb_annotated (bb1
, *annotated_bb
))
1304 bb
->count
= MAX (bb
->count
, bb1
->count
);
1305 set_bb_annotated (bb
, annotated_bb
);
1308 dom_bbs
= get_all_dominated_blocks (CDI_POST_DOMINATORS
, bb
);
1309 FOR_EACH_VEC_ELT (dom_bbs
, i
, bb1
)
1310 if (bb1
->aux
== NULL
&& dominated_by_p (CDI_DOMINATORS
, bb
, bb1
)
1311 && bb1
->loop_father
== bb
->loop_father
)
1314 if (bb1
->count
> bb
->count
&& is_bb_annotated (bb1
, *annotated_bb
))
1316 bb
->count
= MAX (bb
->count
, bb1
->count
);
1317 set_bb_annotated (bb
, annotated_bb
);
1323 /* If a basic block's count is known, and only one of its in/out edges' count
1324 is unknown, its count can be calculated. Meanwhile, if all of the in/out
1325 edges' counts are known, then the basic block's unknown count can also be
1327 IS_SUCC is true if out edges of a basic blocks are examined.
1328 Update ANNOTATED_BB and ANNOTATED_EDGE accordingly.
1329 Return TRUE if any basic block/edge count is changed. */
1332 afdo_propagate_edge (bool is_succ
, bb_set
*annotated_bb
,
1333 edge_set
*annotated_edge
)
1336 bool changed
= false;
1338 FOR_EACH_BB_FN (bb
, cfun
)
1340 edge e
, unknown_edge
= NULL
;
1342 int num_unknown_edge
= 0;
1343 gcov_type total_known_count
= 0;
1345 FOR_EACH_EDGE (e
, ei
, is_succ
? bb
->succs
: bb
->preds
)
1346 if (!is_edge_annotated (e
, *annotated_edge
))
1347 num_unknown_edge
++, unknown_edge
= e
;
1349 total_known_count
+= e
->count
;
1351 if (num_unknown_edge
== 0)
1353 if (total_known_count
> bb
->count
)
1355 bb
->count
= total_known_count
;
1358 if (!is_bb_annotated (bb
, *annotated_bb
))
1360 set_bb_annotated (bb
, annotated_bb
);
1364 else if (num_unknown_edge
== 1 && is_bb_annotated (bb
, *annotated_bb
))
1366 if (bb
->count
>= total_known_count
)
1367 unknown_edge
->count
= bb
->count
- total_known_count
;
1369 unknown_edge
->count
= 0;
1370 set_edge_annotated (unknown_edge
, annotated_edge
);
1377 /* Special propagation for circuit expressions. Because GCC translates
1378 control flow into data flow for circuit expressions. E.g.
1385 will be translated into:
1400 tmp = PHI (0 (BB1), 0 (BB.t1), 1 (BB.t2)
1406 In this case, we need to propagate through PHI to determine the edge
1407 count of BB1->BB.t1, BB.t1->BB.t2.
1408 Update ANNOTATED_EDGE accordingly. */
1411 afdo_propagate_circuit (const bb_set
&annotated_bb
, edge_set
*annotated_edge
)
1414 FOR_ALL_BB_FN (bb
, cfun
)
1417 tree cmp_rhs
, cmp_lhs
;
1418 gimple cmp_stmt
= last_stmt (bb
);
1422 if (!cmp_stmt
|| gimple_code (cmp_stmt
) != GIMPLE_COND
)
1424 cmp_rhs
= gimple_cond_rhs (cmp_stmt
);
1425 cmp_lhs
= gimple_cond_lhs (cmp_stmt
);
1426 if (!TREE_CONSTANT (cmp_rhs
)
1427 || !(integer_zerop (cmp_rhs
) || integer_onep (cmp_rhs
)))
1429 if (TREE_CODE (cmp_lhs
) != SSA_NAME
)
1431 if (!is_bb_annotated (bb
, annotated_bb
))
1433 phi_stmt
= SSA_NAME_DEF_STMT (cmp_lhs
);
1434 while (phi_stmt
&& gimple_code (phi_stmt
) == GIMPLE_ASSIGN
1435 && gimple_assign_single_p (phi_stmt
)
1436 && TREE_CODE (gimple_assign_rhs1 (phi_stmt
)) == SSA_NAME
)
1437 phi_stmt
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (phi_stmt
));
1438 if (!phi_stmt
|| gimple_code (phi_stmt
) != GIMPLE_PHI
)
1440 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1442 unsigned i
, total
= 0;
1444 bool check_value_one
= (((integer_onep (cmp_rhs
))
1445 ^ (gimple_cond_code (cmp_stmt
) == EQ_EXPR
))
1446 ^ ((e
->flags
& EDGE_TRUE_VALUE
) != 0));
1447 if (!is_edge_annotated (e
, *annotated_edge
))
1449 for (i
= 0; i
< gimple_phi_num_args (phi_stmt
); i
++)
1451 tree val
= gimple_phi_arg_def (phi_stmt
, i
);
1452 edge ep
= gimple_phi_arg_edge (phi_stmt
, i
);
1454 if (!TREE_CONSTANT (val
)
1455 || !(integer_zerop (val
) || integer_onep (val
)))
1457 if (check_value_one
^ integer_onep (val
))
1461 if (e
->probability
== 0 && !is_edge_annotated (ep
, *annotated_edge
))
1463 ep
->probability
= 0;
1465 set_edge_annotated (ep
, annotated_edge
);
1468 if (total
== 1 && !is_edge_annotated (only_one
, *annotated_edge
))
1470 only_one
->probability
= e
->probability
;
1471 only_one
->count
= e
->count
;
1472 set_edge_annotated (only_one
, annotated_edge
);
1478 /* Propagate the basic block count and edge count on the control flow
1479 graph. We do the propagation iteratively until stablize. */
1482 afdo_propagate (bb_set
*annotated_bb
, edge_set
*annotated_edge
)
1485 bool changed
= true;
1488 FOR_ALL_BB_FN (bb
, cfun
)
1490 bb
->count
= ((basic_block
)bb
->aux
)->count
;
1491 if (is_bb_annotated ((const basic_block
)bb
->aux
, *annotated_bb
))
1492 set_bb_annotated (bb
, annotated_bb
);
1495 while (changed
&& i
++ < PARAM_VALUE (PARAM_AUTOFDO_MAX_PROPAGATE_ITERATIONS
))
1499 if (afdo_propagate_edge (true, annotated_bb
, annotated_edge
))
1501 if (afdo_propagate_edge (false, annotated_bb
, annotated_edge
))
1503 afdo_propagate_circuit (*annotated_bb
, annotated_edge
);
1507 /* All information parsed from a location_t that will be stored into the ELF
1510 struct locus_information_t
{
1511 /* File name of the source file containing the branch. */
1512 const char *filename
;
1513 /* Line number of the branch location. */
1515 /* Hash value calculated from function name, function length, branch site
1516 offset and discriminator, used to uniquely identify a branch across
1517 different source versions. */
1521 /* Return true iff file and lineno are available for the provided locus.
1522 Fill all fields of li with information about locus. */
1525 get_locus_information (location_t locus
, locus_information_t
* li
) {
1526 if (locus
== UNKNOWN_LOCATION
|| !LOCATION_FILE (locus
))
1528 li
->filename
= LOCATION_FILE (locus
);
1529 li
->lineno
= LOCATION_LINE (locus
);
1533 get_inline_stack (locus
, &stack
);
1534 if (stack
.is_empty ())
1537 tree function_decl
= stack
[0].first
;
1539 if (!(function_decl
&& TREE_CODE (function_decl
) == FUNCTION_DECL
))
1542 /* Get function_length, branch_offset and discriminator to identify branches
1543 across different source versions. */
1544 unsigned function_lineno
=
1545 LOCATION_LINE (DECL_SOURCE_LOCATION (function_decl
));
1546 function
*f
= DECL_STRUCT_FUNCTION (function_decl
);
1547 unsigned function_length
= f
? LOCATION_LINE (f
->function_end_locus
) -
1548 function_lineno
: 0;
1549 unsigned branch_offset
= li
->lineno
- function_lineno
;
1550 int discriminator
= get_discriminator_from_locus (locus
);
1552 const char *fn_name
= fndecl_name (function_decl
);
1553 unsigned char md5_result
[16];
1557 md5_init_ctx (&ctx
);
1558 md5_process_bytes (fn_name
, strlen (fn_name
), &ctx
);
1559 md5_process_bytes (&function_length
, sizeof (function_length
), &ctx
);
1560 md5_process_bytes (&branch_offset
, sizeof (branch_offset
), &ctx
);
1561 md5_process_bytes (&discriminator
, sizeof (discriminator
), &ctx
);
1562 md5_finish_ctx (&ctx
, md5_result
);
1564 /* Convert MD5 to hexadecimal representation. */
1565 for (int i
= 0; i
< 16; ++i
)
1567 sprintf (li
->hash
+ i
*2, "%02x", md5_result
[i
]);
1573 /* Record branch prediction comparison for the given edge and actual
1576 record_branch_prediction_results (edge e
, int probability
) {
1577 basic_block bb
= e
->src
;
1579 if (bb
->succs
->length () == 2 &&
1580 maybe_hot_count_p (cfun
, bb
->count
) &&
1581 bb
->count
>= check_branch_annotation_threshold
)
1583 gimple_stmt_iterator gsi
;
1586 for (gsi
= gsi_last_nondebug_bb (bb
);
1588 gsi_prev_nondebug (&gsi
))
1590 last
= gsi_stmt (gsi
);
1592 if (gimple_has_location (last
))
1596 struct locus_information_t li
;
1599 if (e
->flags
& EDGE_PREDICTED_BY_EXPECT
)
1604 if (get_locus_information (e
->goto_locus
, &li
))
1605 ; /* Intentionally do nothing. */
1606 else if (get_locus_information (gimple_location (last
), &li
))
1607 ; /* Intentionally do nothing. */
1609 return; /* Can't get locus information, return. */
1611 switch_to_section (get_section (
1612 ".gnu.switches.text.branch.annotation",
1613 SECTION_DEBUG
| SECTION_MERGE
|
1614 SECTION_STRINGS
| (SECTION_ENTSIZE
& 1),
1617 snprintf (buf
, 1024, "%s;%u;"
1618 HOST_WIDEST_INT_PRINT_DEC
";%d;%d;%d;%s",
1619 li
.filename
, li
.lineno
, bb
->count
, annotated
?1:0,
1620 probability
, e
->probability
, li
.hash
);
1621 dw2_asm_output_nstring (buf
, (size_t)-1, NULL
);
1625 /* Propagate counts on control flow graph and calculate branch
1629 afdo_calculate_branch_prob (bb_set
*annotated_bb
, edge_set
*annotated_edge
)
1632 bool has_sample
= false;
1634 FOR_EACH_BB_FN (bb
, cfun
)
1641 calculate_dominance_info (CDI_POST_DOMINATORS
);
1642 calculate_dominance_info (CDI_DOMINATORS
);
1643 loop_optimizer_init (0);
1645 afdo_find_equiv_class (annotated_bb
);
1646 afdo_propagate (annotated_bb
, annotated_edge
);
1648 FOR_EACH_BB_FN (bb
, cfun
)
1652 int num_unknown_succ
= 0;
1653 gcov_type total_count
= 0;
1655 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1657 if (!is_edge_annotated (e
, *annotated_edge
))
1660 total_count
+= e
->count
;
1662 if (num_unknown_succ
== 0 && total_count
> 0)
1664 bool first_edge
= true;
1666 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1668 int probability
= (double) e
->count
* REG_BR_PROB_BASE
/ total_count
;
1670 if (first_edge
&& flag_check_branch_annotation
)
1672 record_branch_prediction_results (e
, probability
);
1675 e
->probability
= probability
;
1679 FOR_ALL_BB_FN (bb
, cfun
)
1684 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1686 e
->count
= (double)bb
->count
* e
->probability
/ REG_BR_PROB_BASE
;
1687 if (flag_check_branch_annotation
)
1689 e
->flags
&= ~EDGE_PREDICTED_BY_EXPECT
;
1695 loop_optimizer_finalize ();
1696 free_dominance_info (CDI_DOMINATORS
);
1697 free_dominance_info (CDI_POST_DOMINATORS
);
1700 /* Perform value profile transformation using AutoFDO profile. Add the
1701 promoted stmts to PROMOTED_STMTS. Return TRUE if there is any
1702 indirect call promoted. */
1705 afdo_vpt_for_early_inline (stmt_set
*promoted_stmts
)
1708 if (afdo_source_profile
->get_function_instance_by_decl (
1709 current_function_decl
) == NULL
)
1712 bool has_vpt
= false;
1713 FOR_EACH_BB_FN (bb
, cfun
)
1715 if (!has_indirect_call (bb
))
1717 gimple_stmt_iterator gsi
;
1719 gcov_type bb_count
= 0;
1720 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1723 gimple stmt
= gsi_stmt (gsi
);
1724 if (afdo_source_profile
->get_count_info (stmt
, &info
))
1725 bb_count
= MAX (bb_count
, info
.count
);
1728 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1730 gimple stmt
= gsi_stmt (gsi
);
1731 /* IC_promotion and early_inline_2 is done in multiple iterations.
1732 No need to promoted the stmt if its in promoted_stmts (means
1733 it is already been promoted in the previous iterations). */
1734 if (gimple_code (stmt
) != GIMPLE_CALL
|| gimple_call_fn (stmt
) == NULL
1735 || TREE_CODE (gimple_call_fn (stmt
)) == FUNCTION_DECL
1736 || promoted_stmts
->find (stmt
) != promoted_stmts
->end ())
1740 afdo_source_profile
->get_count_info (stmt
, &info
);
1741 info
.count
= bb_count
;
1742 if (afdo_source_profile
->update_inlined_ind_target (stmt
, &info
))
1744 /* Promote the indirect call and update the promoted_stmts. */
1745 promoted_stmts
->insert (stmt
);
1746 afdo_vpt (&gsi
, info
.targets
);
1751 if (has_vpt
&& gimple_value_profile_transformations ())
1753 free_dominance_info (CDI_DOMINATORS
);
1754 free_dominance_info (CDI_POST_DOMINATORS
);
1755 calculate_dominance_info (CDI_POST_DOMINATORS
);
1756 calculate_dominance_info (CDI_DOMINATORS
);
1757 update_ssa (TODO_update_ssa
);
1758 rebuild_cgraph_edges ();
1765 /* Annotate auto profile to the control flow graph. Do not annotate value
1766 profile for stmts in PROMOTED_STMTS. */
1769 afdo_annotate_cfg (const stmt_set
&promoted_stmts
)
1772 bb_set annotated_bb
;
1773 edge_set annotated_edge
;
1774 const function_instance
*s
1775 = afdo_source_profile
->get_function_instance_by_decl (
1776 current_function_decl
);
1780 cgraph_get_node (current_function_decl
)->count
= s
->head_count ();
1781 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
= s
->head_count ();
1782 gcov_type max_count
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
;
1784 FOR_EACH_BB_FN (bb
, cfun
)
1790 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1793 if (afdo_set_bb_count (bb
, promoted_stmts
))
1794 set_bb_annotated (bb
, &annotated_bb
);
1795 if (bb
->count
> max_count
)
1796 max_count
= bb
->count
;
1798 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
1799 > ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
->count
)
1801 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
->count
1802 = ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
;
1803 set_bb_annotated (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
, &annotated_bb
);
1805 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
1806 > EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
->count
)
1808 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
->count
1809 = ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
;
1810 set_bb_annotated (EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
, &annotated_bb
);
1812 afdo_source_profile
->mark_annotated (
1813 DECL_SOURCE_LOCATION (current_function_decl
));
1814 afdo_source_profile
->mark_annotated (cfun
->function_start_locus
);
1815 afdo_source_profile
->mark_annotated (cfun
->function_end_locus
);
1818 afdo_calculate_branch_prob (&annotated_bb
, &annotated_edge
);
1820 profile_status_for_fn (cfun
) = PROFILE_READ
;
1822 if (flag_value_profile_transformations
)
1824 gimple_value_profile_transformations ();
1825 free_dominance_info (CDI_DOMINATORS
);
1826 free_dominance_info (CDI_POST_DOMINATORS
);
1827 calculate_dominance_info (CDI_POST_DOMINATORS
);
1828 calculate_dominance_info (CDI_DOMINATORS
);
1829 update_ssa (TODO_update_ssa
);
1833 /* Wrapper function to invoke early inliner. */
1838 compute_inline_parameters (cgraph_get_node (current_function_decl
), true);
1839 unsigned todo
= early_inliner ();
1840 if (todo
& TODO_update_ssa_any
)
1841 update_ssa (TODO_update_ssa
);
1844 /* Use AutoFDO profile to annoate the control flow graph.
1845 Return the todo flag. */
1850 struct cgraph_node
*node
;
1852 if (cgraph_state
== CGRAPH_STATE_FINISHED
)
1855 if (!flag_auto_profile
)
1858 if (L_IPO_COMP_MODE
)
1859 lipo_link_and_fixup ();
1860 init_node_map (true);
1861 profile_info
= autofdo::afdo_profile_info
;
1863 FOR_EACH_FUNCTION (node
)
1865 if (!gimple_has_body_p (node
->decl
))
1868 /* Don't profile functions produced for builtin stuff. */
1869 if (DECL_SOURCE_LOCATION (node
->decl
) == BUILTINS_LOCATION
)
1872 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
1874 /* First do indirect call promotion and early inline to make the
1875 IR match the profiled binary before actual annotation.
1877 This is needed because an indirect call might have been promoted
1878 and inlined in the profiled binary. If we do not promote and
1879 inline these indirect calls before annotation, the profile for
1880 these promoted functions will be lost.
1882 e.g. foo() --indirect_call--> bar()
1883 In profiled binary, the callsite is promoted and inlined, making
1884 the profile look like:
1894 Before AutoFDO pass, loc_foo_2 is not promoted thus not inlined.
1895 If we perform annotation on it, the profile inside bar@loc_foo2
1898 To avoid this, we promote loc_foo_2 and inline the promoted bar
1899 function before annotation, so the profile inside bar@loc_foo2
1901 autofdo::stmt_set promoted_stmts
;
1902 for (int i
= 0; i
< PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS
); i
++)
1904 if (!flag_value_profile_transformations
1905 || !autofdo::afdo_vpt_for_early_inline (&promoted_stmts
))
1911 autofdo::afdo_annotate_cfg (promoted_stmts
);
1912 compute_function_frequency ();
1914 /* Local pure-const may imply need to fixup the cfg. */
1915 if (execute_fixup_cfg () & TODO_cleanup_cfg
)
1916 cleanup_tree_cfg ();
1918 free_dominance_info (CDI_DOMINATORS
);
1919 free_dominance_info (CDI_POST_DOMINATORS
);
1920 rebuild_cgraph_edges ();
1921 compute_inline_parameters (cgraph_get_node (current_function_decl
), true);
1925 if (flag_auto_profile_record_coverage_in_elf
)
1926 autofdo::afdo_source_profile
->write_annotated_count ();
1927 return TODO_rebuild_cgraph_edges
;
1929 } /* namespace autofdo. */
1931 /* Read the profile from the profile data file. */
1934 init_auto_profile (void)
1936 if (auto_profile_file
== NULL
)
1937 auto_profile_file
= DEFAULT_AUTO_PROFILE_FILE
;
1939 autofdo::afdo_profile_info
= (struct gcov_ctr_summary
*)xcalloc (
1940 1, sizeof (struct gcov_ctr_summary
));
1941 autofdo::afdo_profile_info
->runs
= 1;
1942 autofdo::afdo_profile_info
->sum_max
= 0;
1943 autofdo::afdo_profile_info
->sum_all
= 0;
1945 /* Read the profile from the profile file. */
1946 autofdo::read_profile ();
1949 autofdo::read_aux_modules ();
1952 /* Free the resources. */
1955 end_auto_profile (void)
1957 delete autofdo::afdo_source_profile
;
1958 delete autofdo::afdo_string_table
;
1959 delete autofdo::afdo_module_profile
;
1960 profile_info
= NULL
;
1963 /* Returns TRUE if EDGE is hot enough to be inlined early. */
1966 afdo_callsite_hot_enough_for_early_inline (struct cgraph_edge
*edge
)
1969 = autofdo::afdo_source_profile
->get_callsite_total_count (edge
);
1973 const struct gcov_ctr_summary
*saved_profile_info
= profile_info
;
1974 /* At earling inline stage, profile_info is not set yet. We need to
1975 temporarily set it to afdo_profile_info to calculate hotness. */
1976 profile_info
= autofdo::afdo_profile_info
;
1977 is_hot
= maybe_hot_count_p (NULL
, count
);
1978 profile_info
= saved_profile_info
;
1987 const pass_data pass_data_ipa_auto_profile
=
1991 OPTGROUP_NONE
, /* optinfo_flags */
1992 true, /* has_gate */
1993 true, /* has_execute */
1994 TV_IPA_AUTOFDO
, /* tv_id */
1995 0, /* properties_required */
1996 0, /* properties_provided */
1997 0, /* properties_destroyed */
1998 0, /* todo_flags_start */
1999 0, /* todo_flags_finish */
2002 class pass_ipa_auto_profile
: public simple_ipa_opt_pass
2005 pass_ipa_auto_profile(gcc::context
*ctxt
)
2006 : simple_ipa_opt_pass(pass_data_ipa_auto_profile
, ctxt
)
2009 /* opt_pass methods: */
2010 bool gate () { return flag_auto_profile
; }
2011 unsigned int execute () { return autofdo::auto_profile (); }
2013 }; // class pass_ipa_auto_profile
2017 simple_ipa_opt_pass
*
2018 make_pass_ipa_auto_profile (gcc::context
*ctxt
)
2020 return new pass_ipa_auto_profile (ctxt
);