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