mklog: add subject line skeleton
[official-gcc.git] / gcc / auto-profile.c
blob43d6fa0b1f02c1f31650eaedd74ef5fd3407da03
1 /* Read and annotate call graph profile from the auto profile data file.
2 Copyright (C) 2014-2021 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
10 version.
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.
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/>. */
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 "ipa-prop.h"
46 #include "ipa-fnsummary.h"
47 #include "ipa-inline.h"
48 #include "tree-inline.h"
49 #include "auto-profile.h"
50 #include "tree-pretty-print.h"
51 #include "gimple-pretty-print.h"
53 /* The following routines implements AutoFDO optimization.
55 This optimization uses sampling profiles to annotate basic block counts
56 and uses heuristics to estimate branch probabilities.
58 There are three phases in AutoFDO:
60 Phase 1: Read profile from the profile data file.
61 The following info is read from the profile datafile:
62 * string_table: a map between function name and its index.
63 * autofdo_source_profile: a map from function_instance name to
64 function_instance. This is represented as a forest of
65 function_instances.
66 * WorkingSet: a histogram of how many instructions are covered for a
67 given percentage of total cycles. This is describing the binary
68 level information (not source level). This info is used to help
69 decide if we want aggressive optimizations that could increase
70 code footprint (e.g. loop unroll etc.)
71 A function instance is an instance of function that could either be a
72 standalone symbol, or a clone of a function that is inlined into another
73 function.
75 Phase 2: Early inline + value profile transformation.
76 Early inline uses autofdo_source_profile to find if a callsite is:
77 * inlined in the profiled binary.
78 * callee body is hot in the profiling run.
79 If both condition satisfies, early inline will inline the callsite
80 regardless of the code growth.
81 Phase 2 is an iterative process. During each iteration, we also check
82 if an indirect callsite is promoted and inlined in the profiling run.
83 If yes, vpt will happen to force promote it and in the next iteration,
84 einline will inline the promoted callsite in the next iteration.
86 Phase 3: Annotate control flow graph.
87 AutoFDO uses a separate pass to:
88 * Annotate basic block count
89 * Estimate branch probability
91 After the above 3 phases, all profile is readily annotated on the GCC IR.
92 AutoFDO tries to reuse all FDO infrastructure as much as possible to make
93 use of the profile. E.g. it uses existing mechanism to calculate the basic
94 block/edge frequency, as well as the cgraph node/edge count.
97 #define DEFAULT_AUTO_PROFILE_FILE "fbdata.afdo"
98 #define AUTO_PROFILE_VERSION 1
100 namespace autofdo
103 /* Intermediate edge info used when propagating AutoFDO profile information.
104 We can't edge->count() directly since it's computed from edge's probability
105 while probability is yet not decided during propagation. */
106 #define AFDO_EINFO(e) ((class edge_info *) e->aux)
107 class edge_info
109 public:
110 edge_info () : count_ (profile_count::zero ().afdo ()), annotated_ (false) {}
111 bool is_annotated () const { return annotated_; }
112 void set_annotated () { annotated_ = true; }
113 profile_count get_count () const { return count_; }
114 void set_count (profile_count count) { count_ = count; }
115 private:
116 profile_count count_;
117 bool annotated_;
120 /* Represent a source location: (function_decl, lineno). */
121 typedef std::pair<tree, unsigned> decl_lineno;
123 /* Represent an inline stack. vector[0] is the leaf node. */
124 typedef auto_vec<decl_lineno> inline_stack;
126 /* String array that stores function names. */
127 typedef auto_vec<char *> string_vector;
129 /* Map from function name's index in string_table to target's
130 execution count. */
131 typedef std::map<unsigned, gcov_type> icall_target_map;
133 /* Set of gimple stmts. Used to track if the stmt has already been promoted
134 to direct call. */
135 typedef std::set<gimple *> stmt_set;
137 /* Represent count info of an inline stack. */
138 class count_info
140 public:
141 /* Sampled count of the inline stack. */
142 gcov_type count;
144 /* Map from indirect call target to its sample count. */
145 icall_target_map targets;
147 /* Whether this inline stack is already used in annotation.
149 Each inline stack should only be used to annotate IR once.
150 This will be enforced when instruction-level discriminator
151 is supported. */
152 bool annotated;
155 /* operator< for "const char *". */
156 struct string_compare
158 bool operator()(const char *a, const char *b) const
160 return strcmp (a, b) < 0;
164 /* Store a string array, indexed by string position in the array. */
165 class string_table
167 public:
168 string_table ()
171 ~string_table ();
173 /* For a given string, returns its index. */
174 int get_index (const char *name) const;
176 /* For a given decl, returns the index of the decl name. */
177 int get_index_by_decl (tree decl) const;
179 /* For a given index, returns the string. */
180 const char *get_name (int index) const;
182 /* Read profile, return TRUE on success. */
183 bool read ();
185 private:
186 typedef std::map<const char *, unsigned, string_compare> string_index_map;
187 string_vector vector_;
188 string_index_map map_;
191 /* Profile of a function instance:
192 1. total_count of the function.
193 2. head_count (entry basic block count) of the function (only valid when
194 function is a top-level function_instance, i.e. it is the original copy
195 instead of the inlined copy).
196 3. map from source location (decl_lineno) to profile (count_info).
197 4. map from callsite to callee function_instance. */
198 class function_instance
200 public:
201 typedef auto_vec<function_instance *> function_instance_stack;
203 /* Read the profile and return a function_instance with head count as
204 HEAD_COUNT. Recursively read callsites to create nested function_instances
205 too. STACK is used to track the recursive creation process. */
206 static function_instance *
207 read_function_instance (function_instance_stack *stack,
208 gcov_type head_count);
210 /* Recursively deallocate all callsites (nested function_instances). */
211 ~function_instance ();
213 /* Accessors. */
215 name () const
217 return name_;
219 gcov_type
220 total_count () const
222 return total_count_;
224 gcov_type
225 head_count () const
227 return head_count_;
230 /* Traverse callsites of the current function_instance to find one at the
231 location of LINENO and callee name represented in DECL. */
232 function_instance *get_function_instance_by_decl (unsigned lineno,
233 tree decl) const;
235 /* Store the profile info for LOC in INFO. Return TRUE if profile info
236 is found. */
237 bool get_count_info (location_t loc, count_info *info) const;
239 /* Read the inlined indirect call target profile for STMT and store it in
240 MAP, return the total count for all inlined indirect calls. */
241 gcov_type find_icall_target_map (gcall *stmt, icall_target_map *map) const;
243 /* Sum of counts that is used during annotation. */
244 gcov_type total_annotated_count () const;
246 /* Mark LOC as annotated. */
247 void mark_annotated (location_t loc);
249 private:
250 /* Callsite, represented as (decl_lineno, callee_function_name_index). */
251 typedef std::pair<unsigned, unsigned> callsite;
253 /* Map from callsite to callee function_instance. */
254 typedef std::map<callsite, function_instance *> callsite_map;
256 function_instance (unsigned name, gcov_type head_count)
257 : name_ (name), total_count_ (0), head_count_ (head_count)
261 /* Map from source location (decl_lineno) to profile (count_info). */
262 typedef std::map<unsigned, count_info> position_count_map;
264 /* function_instance name index in the string_table. */
265 unsigned name_;
267 /* Total sample count. */
268 gcov_type total_count_;
270 /* Entry BB's sample count. */
271 gcov_type head_count_;
273 /* Map from callsite location to callee function_instance. */
274 callsite_map callsites;
276 /* Map from source location to count_info. */
277 position_count_map pos_counts;
280 /* Profile for all functions. */
281 class autofdo_source_profile
283 public:
284 static autofdo_source_profile *
285 create ()
287 autofdo_source_profile *map = new autofdo_source_profile ();
289 if (map->read ())
290 return map;
291 delete map;
292 return NULL;
295 ~autofdo_source_profile ();
297 /* For a given DECL, returns the top-level function_instance. */
298 function_instance *get_function_instance_by_decl (tree decl) const;
300 /* Find count_info for a given gimple STMT. If found, store the count_info
301 in INFO and return true; otherwise return false. */
302 bool get_count_info (gimple *stmt, count_info *info) const;
304 /* Find total count of the callee of EDGE. */
305 gcov_type get_callsite_total_count (struct cgraph_edge *edge) const;
307 /* Update value profile INFO for STMT from the inlined indirect callsite.
308 Return true if INFO is updated. */
309 bool update_inlined_ind_target (gcall *stmt, count_info *info);
311 /* Mark LOC as annotated. */
312 void mark_annotated (location_t loc);
314 private:
315 /* Map from function_instance name index (in string_table) to
316 function_instance. */
317 typedef std::map<unsigned, function_instance *> name_function_instance_map;
319 autofdo_source_profile () {}
321 /* Read AutoFDO profile and returns TRUE on success. */
322 bool read ();
324 /* Return the function_instance in the profile that correspond to the
325 inline STACK. */
326 function_instance *
327 get_function_instance_by_inline_stack (const inline_stack &stack) const;
329 name_function_instance_map map_;
332 /* Store the strings read from the profile data file. */
333 static string_table *afdo_string_table;
335 /* Store the AutoFDO source profile. */
336 static autofdo_source_profile *afdo_source_profile;
338 /* gcov_summary structure to store the profile_info. */
339 static gcov_summary *afdo_profile_info;
341 /* Helper functions. */
343 /* Return the original name of NAME: strip the suffix that starts
344 with '.' Caller is responsible for freeing RET. */
346 static char *
347 get_original_name (const char *name)
349 char *ret = xstrdup (name);
350 char *find = strchr (ret, '.');
351 if (find != NULL)
352 *find = 0;
353 return ret;
356 /* Return the combined location, which is a 32bit integer in which
357 higher 16 bits stores the line offset of LOC to the start lineno
358 of DECL, The lower 16 bits stores the discriminator. */
360 static unsigned
361 get_combined_location (location_t loc, tree decl)
363 /* TODO: allow more bits for line and less bits for discriminator. */
364 if (LOCATION_LINE (loc) - DECL_SOURCE_LINE (decl) >= (1<<16))
365 warning_at (loc, OPT_Woverflow, "offset exceeds 16 bytes");
366 return ((LOCATION_LINE (loc) - DECL_SOURCE_LINE (decl)) << 16);
369 /* Return the function decl of a given lexical BLOCK. */
371 static tree
372 get_function_decl_from_block (tree block)
374 if (!inlined_function_outer_scope_p (block))
375 return NULL_TREE;
377 return BLOCK_ABSTRACT_ORIGIN (block);
380 /* Store inline stack for STMT in STACK. */
382 static void
383 get_inline_stack (location_t locus, inline_stack *stack)
385 if (LOCATION_LOCUS (locus) == UNKNOWN_LOCATION)
386 return;
388 tree block = LOCATION_BLOCK (locus);
389 if (block && TREE_CODE (block) == BLOCK)
391 int level = 0;
392 for (block = BLOCK_SUPERCONTEXT (block);
393 block && (TREE_CODE (block) == BLOCK);
394 block = BLOCK_SUPERCONTEXT (block))
396 location_t tmp_locus = BLOCK_SOURCE_LOCATION (block);
397 if (LOCATION_LOCUS (tmp_locus) == UNKNOWN_LOCATION)
398 continue;
400 tree decl = get_function_decl_from_block (block);
401 stack->safe_push (
402 std::make_pair (decl, get_combined_location (locus, decl)));
403 locus = tmp_locus;
404 level++;
407 stack->safe_push (
408 std::make_pair (current_function_decl,
409 get_combined_location (locus, current_function_decl)));
412 /* Return STMT's combined location, which is a 32bit integer in which
413 higher 16 bits stores the line offset of LOC to the start lineno
414 of DECL, The lower 16 bits stores the discriminator. */
416 static unsigned
417 get_relative_location_for_stmt (gimple *stmt)
419 location_t locus = gimple_location (stmt);
420 if (LOCATION_LOCUS (locus) == UNKNOWN_LOCATION)
421 return UNKNOWN_LOCATION;
423 for (tree block = gimple_block (stmt); block && (TREE_CODE (block) == BLOCK);
424 block = BLOCK_SUPERCONTEXT (block))
425 if (LOCATION_LOCUS (BLOCK_SOURCE_LOCATION (block)) != UNKNOWN_LOCATION)
426 return get_combined_location (locus,
427 get_function_decl_from_block (block));
428 return get_combined_location (locus, current_function_decl);
431 /* Return true if BB contains indirect call. */
433 static bool
434 has_indirect_call (basic_block bb)
436 gimple_stmt_iterator gsi;
438 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
440 gimple *stmt = gsi_stmt (gsi);
441 if (gimple_code (stmt) == GIMPLE_CALL && !gimple_call_internal_p (stmt)
442 && (gimple_call_fn (stmt) == NULL
443 || TREE_CODE (gimple_call_fn (stmt)) != FUNCTION_DECL))
444 return true;
446 return false;
449 /* Member functions for string_table. */
451 /* Deconstructor. */
453 string_table::~string_table ()
455 for (unsigned i = 0; i < vector_.length (); i++)
456 free (vector_[i]);
460 /* Return the index of a given function NAME. Return -1 if NAME is not
461 found in string table. */
464 string_table::get_index (const char *name) const
466 if (name == NULL)
467 return -1;
468 string_index_map::const_iterator iter = map_.find (name);
469 if (iter == map_.end ())
470 return -1;
472 return iter->second;
475 /* Return the index of a given function DECL. Return -1 if DECL is not
476 found in string table. */
479 string_table::get_index_by_decl (tree decl) const
481 char *name
482 = get_original_name (IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl)));
483 int ret = get_index (name);
484 free (name);
485 if (ret != -1)
486 return ret;
487 ret = get_index (lang_hooks.dwarf_name (decl, 0));
488 if (ret != -1)
489 return ret;
490 if (DECL_FROM_INLINE (decl))
491 return get_index_by_decl (DECL_ABSTRACT_ORIGIN (decl));
493 return -1;
496 /* Return the function name of a given INDEX. */
498 const char *
499 string_table::get_name (int index) const
501 gcc_assert (index > 0 && index < (int)vector_.length ());
502 return vector_[index];
505 /* Read the string table. Return TRUE if reading is successful. */
507 bool
508 string_table::read ()
510 if (gcov_read_unsigned () != GCOV_TAG_AFDO_FILE_NAMES)
511 return false;
512 /* Skip the length of the section. */
513 gcov_read_unsigned ();
514 /* Read in the file name table. */
515 unsigned string_num = gcov_read_unsigned ();
516 for (unsigned i = 0; i < string_num; i++)
518 vector_.safe_push (get_original_name (gcov_read_string ()));
519 map_[vector_.last ()] = i;
521 return true;
524 /* Member functions for function_instance. */
526 function_instance::~function_instance ()
528 for (callsite_map::iterator iter = callsites.begin ();
529 iter != callsites.end (); ++iter)
530 delete iter->second;
533 /* Traverse callsites of the current function_instance to find one at the
534 location of LINENO and callee name represented in DECL. */
536 function_instance *
537 function_instance::get_function_instance_by_decl (unsigned lineno,
538 tree decl) const
540 int func_name_idx = afdo_string_table->get_index_by_decl (decl);
541 if (func_name_idx != -1)
543 callsite_map::const_iterator ret
544 = callsites.find (std::make_pair (lineno, func_name_idx));
545 if (ret != callsites.end ())
546 return ret->second;
548 func_name_idx
549 = afdo_string_table->get_index (lang_hooks.dwarf_name (decl, 0));
550 if (func_name_idx != -1)
552 callsite_map::const_iterator ret
553 = callsites.find (std::make_pair (lineno, func_name_idx));
554 if (ret != callsites.end ())
555 return ret->second;
557 if (DECL_FROM_INLINE (decl))
558 return get_function_instance_by_decl (lineno, DECL_ABSTRACT_ORIGIN (decl));
560 return NULL;
563 /* Store the profile info for LOC in INFO. Return TRUE if profile info
564 is found. */
566 bool
567 function_instance::get_count_info (location_t loc, count_info *info) const
569 position_count_map::const_iterator iter = pos_counts.find (loc);
570 if (iter == pos_counts.end ())
571 return false;
572 *info = iter->second;
573 return true;
576 /* Mark LOC as annotated. */
578 void
579 function_instance::mark_annotated (location_t loc)
581 position_count_map::iterator iter = pos_counts.find (loc);
582 if (iter == pos_counts.end ())
583 return;
584 iter->second.annotated = true;
587 /* Read the inlined indirect call target profile for STMT and store it in
588 MAP, return the total count for all inlined indirect calls. */
590 gcov_type
591 function_instance::find_icall_target_map (gcall *stmt,
592 icall_target_map *map) const
594 gcov_type ret = 0;
595 unsigned stmt_offset = get_relative_location_for_stmt (stmt);
597 for (callsite_map::const_iterator iter = callsites.begin ();
598 iter != callsites.end (); ++iter)
600 unsigned callee = iter->second->name ();
601 /* Check if callsite location match the stmt. */
602 if (iter->first.first != stmt_offset)
603 continue;
604 struct cgraph_node *node = cgraph_node::get_for_asmname (
605 get_identifier (afdo_string_table->get_name (callee)));
606 if (node == NULL)
607 continue;
608 (*map)[callee] = iter->second->total_count ();
609 ret += iter->second->total_count ();
611 return ret;
614 /* Read the profile and create a function_instance with head count as
615 HEAD_COUNT. Recursively read callsites to create nested function_instances
616 too. STACK is used to track the recursive creation process. */
618 /* function instance profile format:
620 ENTRY_COUNT: 8 bytes
621 NAME_INDEX: 4 bytes
622 NUM_POS_COUNTS: 4 bytes
623 NUM_CALLSITES: 4 byte
624 POS_COUNT_1:
625 POS_1_OFFSET: 4 bytes
626 NUM_TARGETS: 4 bytes
627 COUNT: 8 bytes
628 TARGET_1:
629 VALUE_PROFILE_TYPE: 4 bytes
630 TARGET_IDX: 8 bytes
631 COUNT: 8 bytes
632 TARGET_2
634 TARGET_n
635 POS_COUNT_2
637 POS_COUNT_N
638 CALLSITE_1:
639 CALLSITE_1_OFFSET: 4 bytes
640 FUNCTION_INSTANCE_PROFILE (nested)
641 CALLSITE_2
643 CALLSITE_n. */
645 function_instance *
646 function_instance::read_function_instance (function_instance_stack *stack,
647 gcov_type head_count)
649 unsigned name = gcov_read_unsigned ();
650 unsigned num_pos_counts = gcov_read_unsigned ();
651 unsigned num_callsites = gcov_read_unsigned ();
652 function_instance *s = new function_instance (name, head_count);
653 stack->safe_push (s);
655 for (unsigned i = 0; i < num_pos_counts; i++)
657 unsigned offset = gcov_read_unsigned () & 0xffff0000;
658 unsigned num_targets = gcov_read_unsigned ();
659 gcov_type count = gcov_read_counter ();
660 s->pos_counts[offset].count = count;
661 for (unsigned j = 0; j < stack->length (); j++)
662 (*stack)[j]->total_count_ += count;
663 for (unsigned j = 0; j < num_targets; j++)
665 /* Only indirect call target histogram is supported now. */
666 gcov_read_unsigned ();
667 gcov_type target_idx = gcov_read_counter ();
668 s->pos_counts[offset].targets[target_idx] = gcov_read_counter ();
671 for (unsigned i = 0; i < num_callsites; i++)
673 unsigned offset = gcov_read_unsigned ();
674 function_instance *callee_function_instance
675 = read_function_instance (stack, 0);
676 s->callsites[std::make_pair (offset, callee_function_instance->name ())]
677 = callee_function_instance;
679 stack->pop ();
680 return s;
683 /* Sum of counts that is used during annotation. */
685 gcov_type
686 function_instance::total_annotated_count () const
688 gcov_type ret = 0;
689 for (callsite_map::const_iterator iter = callsites.begin ();
690 iter != callsites.end (); ++iter)
691 ret += iter->second->total_annotated_count ();
692 for (position_count_map::const_iterator iter = pos_counts.begin ();
693 iter != pos_counts.end (); ++iter)
694 if (iter->second.annotated)
695 ret += iter->second.count;
696 return ret;
699 /* Member functions for autofdo_source_profile. */
701 autofdo_source_profile::~autofdo_source_profile ()
703 for (name_function_instance_map::const_iterator iter = map_.begin ();
704 iter != map_.end (); ++iter)
705 delete iter->second;
708 /* For a given DECL, returns the top-level function_instance. */
710 function_instance *
711 autofdo_source_profile::get_function_instance_by_decl (tree decl) const
713 int index = afdo_string_table->get_index_by_decl (decl);
714 if (index == -1)
715 return NULL;
716 name_function_instance_map::const_iterator ret = map_.find (index);
717 return ret == map_.end () ? NULL : ret->second;
720 /* Find count_info for a given gimple STMT. If found, store the count_info
721 in INFO and return true; otherwise return false. */
723 bool
724 autofdo_source_profile::get_count_info (gimple *stmt, count_info *info) const
726 if (LOCATION_LOCUS (gimple_location (stmt)) == cfun->function_end_locus)
727 return false;
729 inline_stack stack;
730 get_inline_stack (gimple_location (stmt), &stack);
731 if (stack.length () == 0)
732 return false;
733 function_instance *s = get_function_instance_by_inline_stack (stack);
734 if (s == NULL)
735 return false;
736 return s->get_count_info (stack[0].second, info);
739 /* Mark LOC as annotated. */
741 void
742 autofdo_source_profile::mark_annotated (location_t loc)
744 inline_stack stack;
745 get_inline_stack (loc, &stack);
746 if (stack.length () == 0)
747 return;
748 function_instance *s = get_function_instance_by_inline_stack (stack);
749 if (s == NULL)
750 return;
751 s->mark_annotated (stack[0].second);
754 /* Update value profile INFO for STMT from the inlined indirect callsite.
755 Return true if INFO is updated. */
757 bool
758 autofdo_source_profile::update_inlined_ind_target (gcall *stmt,
759 count_info *info)
761 if (dump_file)
763 fprintf (dump_file, "Checking indirect call -> direct call ");
764 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
767 if (LOCATION_LOCUS (gimple_location (stmt)) == cfun->function_end_locus)
769 if (dump_file)
770 fprintf (dump_file, " good locus\n");
771 return false;
774 count_info old_info;
775 get_count_info (stmt, &old_info);
776 gcov_type total = 0;
777 for (icall_target_map::const_iterator iter = old_info.targets.begin ();
778 iter != old_info.targets.end (); ++iter)
779 total += iter->second;
781 /* Program behavior changed, original promoted (and inlined) target is not
782 hot any more. Will avoid promote the original target.
784 To check if original promoted target is still hot, we check the total
785 count of the unpromoted targets (stored in TOTAL). If a callsite count
786 (stored in INFO) is smaller than half of the total count, the original
787 promoted target is considered not hot any more. */
788 if (info->count < total / 2)
790 if (dump_file)
791 fprintf (dump_file, " not hot anymore %ld < %ld",
792 (long)info->count,
793 (long)total /2);
794 return false;
797 inline_stack stack;
798 get_inline_stack (gimple_location (stmt), &stack);
799 if (stack.length () == 0)
801 if (dump_file)
802 fprintf (dump_file, " no inline stack\n");
803 return false;
805 function_instance *s = get_function_instance_by_inline_stack (stack);
806 if (s == NULL)
808 if (dump_file)
809 fprintf (dump_file, " function not found in inline stack\n");
810 return false;
812 icall_target_map map;
813 if (s->find_icall_target_map (stmt, &map) == 0)
815 if (dump_file)
816 fprintf (dump_file, " no target map\n");
817 return false;
819 for (icall_target_map::const_iterator iter = map.begin ();
820 iter != map.end (); ++iter)
821 info->targets[iter->first] = iter->second;
822 if (dump_file)
823 fprintf (dump_file, " looks good\n");
824 return true;
827 /* Find total count of the callee of EDGE. */
829 gcov_type
830 autofdo_source_profile::get_callsite_total_count (
831 struct cgraph_edge *edge) const
833 inline_stack stack;
834 stack.safe_push (std::make_pair (edge->callee->decl, 0));
835 get_inline_stack (gimple_location (edge->call_stmt), &stack);
837 function_instance *s = get_function_instance_by_inline_stack (stack);
838 if (s == NULL
839 || afdo_string_table->get_index (IDENTIFIER_POINTER (
840 DECL_ASSEMBLER_NAME (edge->callee->decl))) != s->name ())
841 return 0;
843 return s->total_count ();
846 /* Read AutoFDO profile and returns TRUE on success. */
848 /* source profile format:
850 GCOV_TAG_AFDO_FUNCTION: 4 bytes
851 LENGTH: 4 bytes
852 NUM_FUNCTIONS: 4 bytes
853 FUNCTION_INSTANCE_1
854 FUNCTION_INSTANCE_2
856 FUNCTION_INSTANCE_N. */
858 bool
859 autofdo_source_profile::read ()
861 if (gcov_read_unsigned () != GCOV_TAG_AFDO_FUNCTION)
863 inform (UNKNOWN_LOCATION, "Not expected TAG.");
864 return false;
867 /* Skip the length of the section. */
868 gcov_read_unsigned ();
870 /* Read in the function/callsite profile, and store it in local
871 data structure. */
872 unsigned function_num = gcov_read_unsigned ();
873 for (unsigned i = 0; i < function_num; i++)
875 function_instance::function_instance_stack stack;
876 function_instance *s = function_instance::read_function_instance (
877 &stack, gcov_read_counter ());
878 map_[s->name ()] = s;
880 return true;
883 /* Return the function_instance in the profile that correspond to the
884 inline STACK. */
886 function_instance *
887 autofdo_source_profile::get_function_instance_by_inline_stack (
888 const inline_stack &stack) const
890 name_function_instance_map::const_iterator iter = map_.find (
891 afdo_string_table->get_index_by_decl (stack[stack.length () - 1].first));
892 if (iter == map_.end())
893 return NULL;
894 function_instance *s = iter->second;
895 for (unsigned i = stack.length() - 1; i > 0; i--)
897 s = s->get_function_instance_by_decl (
898 stack[i].second, stack[i - 1].first);
899 if (s == NULL)
900 return NULL;
902 return s;
905 /* Module profile is only used by LIPO. Here we simply ignore it. */
907 static void
908 fake_read_autofdo_module_profile ()
910 /* Read in the module info. */
911 gcov_read_unsigned ();
913 /* Skip the length of the section. */
914 gcov_read_unsigned ();
916 /* Read in the file name table. */
917 unsigned total_module_num = gcov_read_unsigned ();
918 gcc_assert (total_module_num == 0);
921 /* Read data from profile data file. */
923 static void
924 read_profile (void)
926 if (gcov_open (auto_profile_file, 1) == 0)
928 error ("cannot open profile file %s", auto_profile_file);
929 return;
932 if (gcov_read_unsigned () != GCOV_DATA_MAGIC)
934 error ("AutoFDO profile magic number does not match");
935 return;
938 /* Skip the version number. */
939 unsigned version = gcov_read_unsigned ();
940 if (version != AUTO_PROFILE_VERSION)
942 error ("AutoFDO profile version %u does not match %u",
943 version, AUTO_PROFILE_VERSION);
944 return;
947 /* Skip the empty integer. */
948 gcov_read_unsigned ();
950 /* string_table. */
951 afdo_string_table = new string_table ();
952 if (!afdo_string_table->read())
954 error ("cannot read string table from %s", auto_profile_file);
955 return;
958 /* autofdo_source_profile. */
959 afdo_source_profile = autofdo_source_profile::create ();
960 if (afdo_source_profile == NULL)
962 error ("cannot read function profile from %s", auto_profile_file);
963 return;
966 /* autofdo_module_profile. */
967 fake_read_autofdo_module_profile ();
970 /* From AutoFDO profiles, find values inside STMT for that we want to measure
971 histograms for indirect-call optimization.
973 This function is actually served for 2 purposes:
974 * before annotation, we need to mark histogram, promote and inline
975 * after annotation, we just need to mark, and let follow-up logic to
976 decide if it needs to promote and inline. */
978 static void
979 afdo_indirect_call (gimple_stmt_iterator *gsi, const icall_target_map &map,
980 bool transform)
982 gimple *gs = gsi_stmt (*gsi);
983 tree callee;
985 if (map.size () == 0)
986 return;
987 gcall *stmt = dyn_cast <gcall *> (gs);
988 if (!stmt
989 || gimple_call_internal_p (stmt)
990 || gimple_call_fndecl (stmt) != NULL_TREE)
991 return;
993 gcov_type total = 0;
994 icall_target_map::const_iterator max_iter = map.end ();
996 for (icall_target_map::const_iterator iter = map.begin ();
997 iter != map.end (); ++iter)
999 total += iter->second;
1000 if (max_iter == map.end () || max_iter->second < iter->second)
1001 max_iter = iter;
1003 struct cgraph_node *direct_call = cgraph_node::get_for_asmname (
1004 get_identifier (afdo_string_table->get_name (max_iter->first)));
1005 if (direct_call == NULL || !direct_call->profile_id)
1006 return;
1008 callee = gimple_call_fn (stmt);
1010 histogram_value hist = gimple_alloc_histogram_value (
1011 cfun, HIST_TYPE_INDIR_CALL, stmt, callee);
1012 hist->n_counters = 3;
1013 hist->hvalue.counters = XNEWVEC (gcov_type, hist->n_counters);
1014 gimple_add_histogram_value (cfun, stmt, hist);
1016 hist->hvalue.counters[0] = direct_call->profile_id;
1017 hist->hvalue.counters[1] = max_iter->second;
1018 hist->hvalue.counters[2] = total;
1020 if (!transform)
1021 return;
1023 struct cgraph_edge *indirect_edge
1024 = cgraph_node::get (current_function_decl)->get_edge (stmt);
1026 if (dump_file)
1028 fprintf (dump_file, "Indirect call -> direct call ");
1029 print_generic_expr (dump_file, callee, TDF_SLIM);
1030 fprintf (dump_file, " => ");
1031 print_generic_expr (dump_file, direct_call->decl, TDF_SLIM);
1034 if (direct_call == NULL)
1036 if (dump_file)
1037 fprintf (dump_file, " not transforming\n");
1038 return;
1040 if (DECL_STRUCT_FUNCTION (direct_call->decl) == NULL)
1042 if (dump_file)
1043 fprintf (dump_file, " no declaration\n");
1044 return;
1047 if (dump_file)
1049 fprintf (dump_file, " transformation on insn ");
1050 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1051 fprintf (dump_file, "\n");
1054 /* FIXME: Count should be initialized. */
1055 struct cgraph_edge *new_edge
1056 = indirect_edge->make_speculative (direct_call,
1057 profile_count::uninitialized ());
1058 cgraph_edge::redirect_call_stmt_to_callee (new_edge);
1059 gimple_remove_histogram_value (cfun, stmt, hist);
1060 inline_call (new_edge, true, NULL, NULL, false);
1063 /* From AutoFDO profiles, find values inside STMT for that we want to measure
1064 histograms and adds them to list VALUES. */
1066 static void
1067 afdo_vpt (gimple_stmt_iterator *gsi, const icall_target_map &map,
1068 bool transform)
1070 afdo_indirect_call (gsi, map, transform);
1073 typedef std::set<basic_block> bb_set;
1074 typedef std::set<edge> edge_set;
1076 static bool
1077 is_bb_annotated (const basic_block bb, const bb_set &annotated)
1079 return annotated.find (bb) != annotated.end ();
1082 static void
1083 set_bb_annotated (basic_block bb, bb_set *annotated)
1085 annotated->insert (bb);
1088 /* For a given BB, set its execution count. Attach value profile if a stmt
1089 is not in PROMOTED, because we only want to promote an indirect call once.
1090 Return TRUE if BB is annotated. */
1092 static bool
1093 afdo_set_bb_count (basic_block bb, const stmt_set &promoted)
1095 gimple_stmt_iterator gsi;
1096 edge e;
1097 edge_iterator ei;
1098 gcov_type max_count = 0;
1099 bool has_annotated = false;
1101 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1103 count_info info;
1104 gimple *stmt = gsi_stmt (gsi);
1105 if (gimple_clobber_p (stmt) || is_gimple_debug (stmt))
1106 continue;
1107 if (afdo_source_profile->get_count_info (stmt, &info))
1109 if (info.count > max_count)
1110 max_count = info.count;
1111 has_annotated = true;
1112 if (info.targets.size () > 0
1113 && promoted.find (stmt) == promoted.end ())
1114 afdo_vpt (&gsi, info.targets, false);
1118 if (!has_annotated)
1119 return false;
1121 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1122 afdo_source_profile->mark_annotated (gimple_location (gsi_stmt (gsi)));
1123 for (gphi_iterator gpi = gsi_start_phis (bb);
1124 !gsi_end_p (gpi);
1125 gsi_next (&gpi))
1127 gphi *phi = gpi.phi ();
1128 size_t i;
1129 for (i = 0; i < gimple_phi_num_args (phi); i++)
1130 afdo_source_profile->mark_annotated (gimple_phi_arg_location (phi, i));
1132 FOR_EACH_EDGE (e, ei, bb->succs)
1133 afdo_source_profile->mark_annotated (e->goto_locus);
1135 bb->count = profile_count::from_gcov_type (max_count).afdo ();
1136 return true;
1139 /* BB1 and BB2 are in an equivalent class iff:
1140 1. BB1 dominates BB2.
1141 2. BB2 post-dominates BB1.
1142 3. BB1 and BB2 are in the same loop nest.
1143 This function finds the equivalent class for each basic block, and
1144 stores a pointer to the first BB in its equivalent class. Meanwhile,
1145 set bb counts for the same equivalent class to be idenical. Update
1146 ANNOTATED_BB for the first BB in its equivalent class. */
1148 static void
1149 afdo_find_equiv_class (bb_set *annotated_bb)
1151 basic_block bb;
1153 FOR_ALL_BB_FN (bb, cfun)
1154 bb->aux = NULL;
1156 FOR_ALL_BB_FN (bb, cfun)
1158 if (bb->aux != NULL)
1159 continue;
1160 bb->aux = bb;
1161 for (basic_block bb1 : get_dominated_by (CDI_DOMINATORS, bb))
1162 if (bb1->aux == NULL && dominated_by_p (CDI_POST_DOMINATORS, bb, bb1)
1163 && bb1->loop_father == bb->loop_father)
1165 bb1->aux = bb;
1166 if (bb1->count > bb->count && is_bb_annotated (bb1, *annotated_bb))
1168 bb->count = bb1->count;
1169 set_bb_annotated (bb, annotated_bb);
1173 for (basic_block bb1 : get_dominated_by (CDI_POST_DOMINATORS, bb))
1174 if (bb1->aux == NULL && dominated_by_p (CDI_DOMINATORS, bb, bb1)
1175 && bb1->loop_father == bb->loop_father)
1177 bb1->aux = bb;
1178 if (bb1->count > bb->count && is_bb_annotated (bb1, *annotated_bb))
1180 bb->count = bb1->count;
1181 set_bb_annotated (bb, annotated_bb);
1187 /* If a basic block's count is known, and only one of its in/out edges' count
1188 is unknown, its count can be calculated. Meanwhile, if all of the in/out
1189 edges' counts are known, then the basic block's unknown count can also be
1190 calculated.
1191 IS_SUCC is true if out edges of a basic blocks are examined.
1192 Update ANNOTATED_BB accordingly.
1193 Return TRUE if any basic block/edge count is changed. */
1195 static bool
1196 afdo_propagate_edge (bool is_succ, bb_set *annotated_bb)
1198 basic_block bb;
1199 bool changed = false;
1201 FOR_EACH_BB_FN (bb, cfun)
1203 edge e, unknown_edge = NULL;
1204 edge_iterator ei;
1205 int num_unknown_edge = 0;
1206 profile_count total_known_count = profile_count::zero ().afdo ();
1208 FOR_EACH_EDGE (e, ei, is_succ ? bb->succs : bb->preds)
1210 gcc_assert (AFDO_EINFO (e) != NULL);
1211 if (! AFDO_EINFO (e)->is_annotated ())
1212 num_unknown_edge++, unknown_edge = e;
1213 else
1214 total_known_count += AFDO_EINFO (e)->get_count ();
1217 /* Be careful not to annotate block with no successor in special cases. */
1218 if (num_unknown_edge == 0 && total_known_count > bb->count)
1220 bb->count = total_known_count;
1221 if (!is_bb_annotated (bb, *annotated_bb))
1222 set_bb_annotated (bb, annotated_bb);
1223 changed = true;
1225 else if (num_unknown_edge == 1 && is_bb_annotated (bb, *annotated_bb))
1227 if (bb->count > total_known_count)
1228 AFDO_EINFO (unknown_edge)->set_count (bb->count - total_known_count);
1229 else
1230 AFDO_EINFO (unknown_edge)->set_count (profile_count::zero().afdo ());
1231 AFDO_EINFO (unknown_edge)->set_annotated ();
1232 changed = true;
1235 return changed;
1238 /* Special propagation for circuit expressions. Because GCC translates
1239 control flow into data flow for circuit expressions. E.g.
1240 BB1:
1241 if (a && b)
1243 else
1246 will be translated into:
1248 BB1:
1249 if (a)
1250 goto BB.t1
1251 else
1252 goto BB.t3
1253 BB.t1:
1254 if (b)
1255 goto BB.t2
1256 else
1257 goto BB.t3
1258 BB.t2:
1259 goto BB.t3
1260 BB.t3:
1261 tmp = PHI (0 (BB1), 0 (BB.t1), 1 (BB.t2)
1262 if (tmp)
1263 goto BB2
1264 else
1265 goto BB3
1267 In this case, we need to propagate through PHI to determine the edge
1268 count of BB1->BB.t1, BB.t1->BB.t2. */
1270 static void
1271 afdo_propagate_circuit (const bb_set &annotated_bb)
1273 basic_block bb;
1274 FOR_ALL_BB_FN (bb, cfun)
1276 gimple *def_stmt;
1277 tree cmp_rhs, cmp_lhs;
1278 gimple *cmp_stmt = last_stmt (bb);
1279 edge e;
1280 edge_iterator ei;
1282 if (!cmp_stmt || gimple_code (cmp_stmt) != GIMPLE_COND)
1283 continue;
1284 cmp_rhs = gimple_cond_rhs (cmp_stmt);
1285 cmp_lhs = gimple_cond_lhs (cmp_stmt);
1286 if (!TREE_CONSTANT (cmp_rhs)
1287 || !(integer_zerop (cmp_rhs) || integer_onep (cmp_rhs)))
1288 continue;
1289 if (TREE_CODE (cmp_lhs) != SSA_NAME)
1290 continue;
1291 if (!is_bb_annotated (bb, annotated_bb))
1292 continue;
1293 def_stmt = SSA_NAME_DEF_STMT (cmp_lhs);
1294 while (def_stmt && gimple_code (def_stmt) == GIMPLE_ASSIGN
1295 && gimple_assign_single_p (def_stmt)
1296 && TREE_CODE (gimple_assign_rhs1 (def_stmt)) == SSA_NAME)
1297 def_stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (def_stmt));
1298 if (!def_stmt)
1299 continue;
1300 gphi *phi_stmt = dyn_cast <gphi *> (def_stmt);
1301 if (!phi_stmt)
1302 continue;
1303 FOR_EACH_EDGE (e, ei, bb->succs)
1305 unsigned i, total = 0;
1306 edge only_one;
1307 bool check_value_one = (((integer_onep (cmp_rhs))
1308 ^ (gimple_cond_code (cmp_stmt) == EQ_EXPR))
1309 ^ ((e->flags & EDGE_TRUE_VALUE) != 0));
1310 if (! AFDO_EINFO (e)->is_annotated ())
1311 continue;
1312 for (i = 0; i < gimple_phi_num_args (phi_stmt); i++)
1314 tree val = gimple_phi_arg_def (phi_stmt, i);
1315 edge ep = gimple_phi_arg_edge (phi_stmt, i);
1317 if (!TREE_CONSTANT (val)
1318 || !(integer_zerop (val) || integer_onep (val)))
1319 continue;
1320 if (check_value_one ^ integer_onep (val))
1321 continue;
1322 total++;
1323 only_one = ep;
1324 if (! (AFDO_EINFO (e)->get_count ()).nonzero_p ()
1325 && ! AFDO_EINFO (ep)->is_annotated ())
1327 AFDO_EINFO (ep)->set_count (profile_count::zero ().afdo ());
1328 AFDO_EINFO (ep)->set_annotated ();
1331 if (total == 1 && ! AFDO_EINFO (only_one)->is_annotated ())
1333 AFDO_EINFO (only_one)->set_count (AFDO_EINFO (e)->get_count ());
1334 AFDO_EINFO (only_one)->set_annotated ();
1340 /* Propagate the basic block count and edge count on the control flow
1341 graph. We do the propagation iteratively until stablize. */
1343 static void
1344 afdo_propagate (bb_set *annotated_bb)
1346 basic_block bb;
1347 bool changed = true;
1348 int i = 0;
1350 FOR_ALL_BB_FN (bb, cfun)
1352 bb->count = ((basic_block)bb->aux)->count;
1353 if (is_bb_annotated ((basic_block)bb->aux, *annotated_bb))
1354 set_bb_annotated (bb, annotated_bb);
1357 while (changed && i++ < 10)
1359 changed = false;
1361 if (afdo_propagate_edge (true, annotated_bb))
1362 changed = true;
1363 if (afdo_propagate_edge (false, annotated_bb))
1364 changed = true;
1365 afdo_propagate_circuit (*annotated_bb);
1369 /* Propagate counts on control flow graph and calculate branch
1370 probabilities. */
1372 static void
1373 afdo_calculate_branch_prob (bb_set *annotated_bb)
1375 edge e;
1376 edge_iterator ei;
1377 basic_block bb;
1379 calculate_dominance_info (CDI_POST_DOMINATORS);
1380 calculate_dominance_info (CDI_DOMINATORS);
1381 loop_optimizer_init (0);
1383 FOR_ALL_BB_FN (bb, cfun)
1385 gcc_assert (bb->aux == NULL);
1386 FOR_EACH_EDGE (e, ei, bb->succs)
1388 gcc_assert (e->aux == NULL);
1389 e->aux = new edge_info ();
1393 afdo_find_equiv_class (annotated_bb);
1394 afdo_propagate (annotated_bb);
1396 FOR_EACH_BB_FN (bb, cfun)
1398 int num_unknown_succ = 0;
1399 profile_count total_count = profile_count::zero ().afdo ();
1401 FOR_EACH_EDGE (e, ei, bb->succs)
1403 gcc_assert (AFDO_EINFO (e) != NULL);
1404 if (! AFDO_EINFO (e)->is_annotated ())
1405 num_unknown_succ++;
1406 else
1407 total_count += AFDO_EINFO (e)->get_count ();
1409 if (num_unknown_succ == 0 && total_count > profile_count::zero ())
1411 FOR_EACH_EDGE (e, ei, bb->succs)
1412 e->probability
1413 = AFDO_EINFO (e)->get_count ().probability_in (total_count);
1416 FOR_ALL_BB_FN (bb, cfun)
1418 bb->aux = NULL;
1419 FOR_EACH_EDGE (e, ei, bb->succs)
1420 if (AFDO_EINFO (e) != NULL)
1422 delete AFDO_EINFO (e);
1423 e->aux = NULL;
1427 loop_optimizer_finalize ();
1428 free_dominance_info (CDI_DOMINATORS);
1429 free_dominance_info (CDI_POST_DOMINATORS);
1432 /* Perform value profile transformation using AutoFDO profile. Add the
1433 promoted stmts to PROMOTED_STMTS. Return TRUE if there is any
1434 indirect call promoted. */
1436 static bool
1437 afdo_vpt_for_early_inline (stmt_set *promoted_stmts)
1439 basic_block bb;
1440 if (afdo_source_profile->get_function_instance_by_decl (
1441 current_function_decl) == NULL)
1442 return false;
1444 compute_fn_summary (cgraph_node::get (current_function_decl), true);
1446 bool has_vpt = false;
1447 FOR_EACH_BB_FN (bb, cfun)
1449 if (!has_indirect_call (bb))
1450 continue;
1451 gimple_stmt_iterator gsi;
1453 gcov_type bb_count = 0;
1454 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1456 count_info info;
1457 gimple *stmt = gsi_stmt (gsi);
1458 if (afdo_source_profile->get_count_info (stmt, &info))
1459 bb_count = MAX (bb_count, info.count);
1462 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1464 gcall *stmt = dyn_cast <gcall *> (gsi_stmt (gsi));
1465 /* IC_promotion and early_inline_2 is done in multiple iterations.
1466 No need to promoted the stmt if its in promoted_stmts (means
1467 it is already been promoted in the previous iterations). */
1468 if ((!stmt) || gimple_call_fn (stmt) == NULL
1469 || TREE_CODE (gimple_call_fn (stmt)) == FUNCTION_DECL
1470 || promoted_stmts->find (stmt) != promoted_stmts->end ())
1471 continue;
1473 count_info info;
1474 afdo_source_profile->get_count_info (stmt, &info);
1475 info.count = bb_count;
1476 if (afdo_source_profile->update_inlined_ind_target (stmt, &info))
1478 /* Promote the indirect call and update the promoted_stmts. */
1479 promoted_stmts->insert (stmt);
1480 afdo_vpt (&gsi, info.targets, true);
1481 has_vpt = true;
1486 if (has_vpt)
1488 unsigned todo = optimize_inline_calls (current_function_decl);
1489 if (todo & TODO_update_ssa_any)
1490 update_ssa (TODO_update_ssa);
1491 return true;
1494 return false;
1497 /* Annotate auto profile to the control flow graph. Do not annotate value
1498 profile for stmts in PROMOTED_STMTS. */
1500 static void
1501 afdo_annotate_cfg (const stmt_set &promoted_stmts)
1503 basic_block bb;
1504 bb_set annotated_bb;
1505 const function_instance *s
1506 = afdo_source_profile->get_function_instance_by_decl (
1507 current_function_decl);
1509 if (s == NULL)
1510 return;
1511 cgraph_node::get (current_function_decl)->count
1512 = profile_count::from_gcov_type (s->head_count ()).afdo ();
1513 ENTRY_BLOCK_PTR_FOR_FN (cfun)->count
1514 = profile_count::from_gcov_type (s->head_count ()).afdo ();
1515 EXIT_BLOCK_PTR_FOR_FN (cfun)->count = profile_count::zero ().afdo ();
1516 profile_count max_count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count;
1518 FOR_EACH_BB_FN (bb, cfun)
1520 /* As autoFDO uses sampling approach, we have to assume that all
1521 counters are zero when not seen by autoFDO. */
1522 bb->count = profile_count::zero ().afdo ();
1523 if (afdo_set_bb_count (bb, promoted_stmts))
1524 set_bb_annotated (bb, &annotated_bb);
1525 if (bb->count > max_count)
1526 max_count = bb->count;
1528 if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count
1529 > ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb->count)
1531 ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb->count
1532 = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count;
1533 set_bb_annotated (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, &annotated_bb);
1535 if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count
1536 > EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb->count)
1538 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb->count
1539 = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count;
1540 set_bb_annotated (EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb, &annotated_bb);
1542 afdo_source_profile->mark_annotated (
1543 DECL_SOURCE_LOCATION (current_function_decl));
1544 afdo_source_profile->mark_annotated (cfun->function_start_locus);
1545 afdo_source_profile->mark_annotated (cfun->function_end_locus);
1546 if (max_count > profile_count::zero ())
1548 /* Calculate, propagate count and probability information on CFG. */
1549 afdo_calculate_branch_prob (&annotated_bb);
1551 update_max_bb_count ();
1552 profile_status_for_fn (cfun) = PROFILE_READ;
1553 if (flag_value_profile_transformations)
1555 gimple_value_profile_transformations ();
1556 free_dominance_info (CDI_DOMINATORS);
1557 free_dominance_info (CDI_POST_DOMINATORS);
1558 update_ssa (TODO_update_ssa);
1562 /* Wrapper function to invoke early inliner. */
1564 static void
1565 early_inline ()
1567 compute_fn_summary (cgraph_node::get (current_function_decl), true);
1568 unsigned todo = early_inliner (cfun);
1569 if (todo & TODO_update_ssa_any)
1570 update_ssa (TODO_update_ssa);
1573 /* Use AutoFDO profile to annoate the control flow graph.
1574 Return the todo flag. */
1576 static unsigned int
1577 auto_profile (void)
1579 struct cgraph_node *node;
1581 if (symtab->state == FINISHED)
1582 return 0;
1584 init_node_map (true);
1585 profile_info = autofdo::afdo_profile_info;
1587 FOR_EACH_FUNCTION (node)
1589 if (!gimple_has_body_p (node->decl))
1590 continue;
1592 /* Don't profile functions produced for builtin stuff. */
1593 if (DECL_SOURCE_LOCATION (node->decl) == BUILTINS_LOCATION)
1594 continue;
1596 push_cfun (DECL_STRUCT_FUNCTION (node->decl));
1598 /* First do indirect call promotion and early inline to make the
1599 IR match the profiled binary before actual annotation.
1601 This is needed because an indirect call might have been promoted
1602 and inlined in the profiled binary. If we do not promote and
1603 inline these indirect calls before annotation, the profile for
1604 these promoted functions will be lost.
1606 e.g. foo() --indirect_call--> bar()
1607 In profiled binary, the callsite is promoted and inlined, making
1608 the profile look like:
1610 foo: {
1611 loc_foo_1: count_1
1612 bar@loc_foo_2: {
1613 loc_bar_1: count_2
1614 loc_bar_2: count_3
1618 Before AutoFDO pass, loc_foo_2 is not promoted thus not inlined.
1619 If we perform annotation on it, the profile inside bar@loc_foo2
1620 will be wasted.
1622 To avoid this, we promote loc_foo_2 and inline the promoted bar
1623 function before annotation, so the profile inside bar@loc_foo2
1624 will be useful. */
1625 autofdo::stmt_set promoted_stmts;
1626 for (int i = 0; i < opt_for_fn (node->decl,
1627 param_early_inliner_max_iterations); i++)
1629 if (!flag_value_profile_transformations
1630 || !autofdo::afdo_vpt_for_early_inline (&promoted_stmts))
1631 break;
1632 early_inline ();
1635 early_inline ();
1636 autofdo::afdo_annotate_cfg (promoted_stmts);
1637 compute_function_frequency ();
1639 /* Local pure-const may imply need to fixup the cfg. */
1640 if (execute_fixup_cfg () & TODO_cleanup_cfg)
1641 cleanup_tree_cfg ();
1643 free_dominance_info (CDI_DOMINATORS);
1644 free_dominance_info (CDI_POST_DOMINATORS);
1645 cgraph_edge::rebuild_edges ();
1646 compute_fn_summary (cgraph_node::get (current_function_decl), true);
1647 pop_cfun ();
1650 return TODO_rebuild_cgraph_edges;
1652 } /* namespace autofdo. */
1654 /* Read the profile from the profile data file. */
1656 void
1657 read_autofdo_file (void)
1659 if (auto_profile_file == NULL)
1660 auto_profile_file = DEFAULT_AUTO_PROFILE_FILE;
1662 autofdo::afdo_profile_info = XNEW (gcov_summary);
1663 autofdo::afdo_profile_info->runs = 1;
1664 autofdo::afdo_profile_info->sum_max = 0;
1666 /* Read the profile from the profile file. */
1667 autofdo::read_profile ();
1670 /* Free the resources. */
1672 void
1673 end_auto_profile (void)
1675 delete autofdo::afdo_source_profile;
1676 delete autofdo::afdo_string_table;
1677 profile_info = NULL;
1680 /* Returns TRUE if EDGE is hot enough to be inlined early. */
1682 bool
1683 afdo_callsite_hot_enough_for_early_inline (struct cgraph_edge *edge)
1685 gcov_type count
1686 = autofdo::afdo_source_profile->get_callsite_total_count (edge);
1688 if (count > 0)
1690 bool is_hot;
1691 profile_count pcount = profile_count::from_gcov_type (count).afdo ();
1692 gcov_summary *saved_profile_info = profile_info;
1693 /* At early inline stage, profile_info is not set yet. We need to
1694 temporarily set it to afdo_profile_info to calculate hotness. */
1695 profile_info = autofdo::afdo_profile_info;
1696 is_hot = maybe_hot_count_p (NULL, pcount);
1697 profile_info = saved_profile_info;
1698 return is_hot;
1701 return false;
1704 namespace
1707 const pass_data pass_data_ipa_auto_profile = {
1708 SIMPLE_IPA_PASS, "afdo", /* name */
1709 OPTGROUP_NONE, /* optinfo_flags */
1710 TV_IPA_AUTOFDO, /* tv_id */
1711 0, /* properties_required */
1712 0, /* properties_provided */
1713 0, /* properties_destroyed */
1714 0, /* todo_flags_start */
1715 0, /* todo_flags_finish */
1718 class pass_ipa_auto_profile : public simple_ipa_opt_pass
1720 public:
1721 pass_ipa_auto_profile (gcc::context *ctxt)
1722 : simple_ipa_opt_pass (pass_data_ipa_auto_profile, ctxt)
1726 /* opt_pass methods: */
1727 virtual bool
1728 gate (function *)
1730 return flag_auto_profile;
1732 virtual unsigned int
1733 execute (function *)
1735 return autofdo::auto_profile ();
1737 }; // class pass_ipa_auto_profile
1739 } // anon namespace
1741 simple_ipa_opt_pass *
1742 make_pass_ipa_auto_profile (gcc::context *ctxt)
1744 return new pass_ipa_auto_profile (ctxt);