1 /* Basic IPA optimizations based on profile.
2 Copyright (C) 2003-2020 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* ipa-profile pass implements the following analysis propagating profille
23 - Count histogram construction. This is a histogram analyzing how much
24 time is spent executing statements with a given execution count read
25 from profile feedback. This histogram is complete only with LTO,
26 otherwise it contains information only about the current unit.
28 The information is used to set hot/cold thresholds.
29 - Next speculative indirect call resolution is performed: the local
30 profile pass assigns profile-id to each function and provide us with a
31 histogram specifying the most common target. We look up the callgraph
32 node corresponding to the target and produce a speculative call.
34 This call may or may not survive through IPA optimization based on decision
36 - Finally we propagate the following flags: unlikely executed, executed
37 once, executed at startup and executed at exit. These flags are used to
38 control code size/performance threshold and code placement (by producing
39 .text.unlikely/.text.hot/.text.startup/.text.exit subsections). */
42 #include "coretypes.h"
47 #include "alloc-pool.h"
48 #include "tree-pass.h"
50 #include "data-streamer.h"
51 #include "gimple-iterator.h"
52 #include "ipa-utils.h"
54 #include "value-prof.h"
55 #include "tree-inline.h"
56 #include "symbol-summary.h"
59 #include "ipa-fnsummary.h"
61 /* Entry in the histogram. */
63 struct histogram_entry
70 /* Histogram of profile values.
71 The histogram is represented as an ordered vector of entries allocated via
72 histogram_pool. During construction a separate hashtable is kept to lookup
75 vec
<histogram_entry
*> histogram
;
76 static object_allocator
<histogram_entry
> histogram_pool ("IPA histogram");
78 /* Hashtable support for storing SSA names hashed by their SSA_NAME_VAR. */
80 struct histogram_hash
: nofree_ptr_hash
<histogram_entry
>
82 static inline hashval_t
hash (const histogram_entry
*);
83 static inline int equal (const histogram_entry
*, const histogram_entry
*);
87 histogram_hash::hash (const histogram_entry
*val
)
93 histogram_hash::equal (const histogram_entry
*val
, const histogram_entry
*val2
)
95 return val
->count
== val2
->count
;
98 /* Account TIME and SIZE executed COUNT times into HISTOGRAM.
99 HASHTABLE is the on-side hash kept to avoid duplicates. */
102 account_time_size (hash_table
<histogram_hash
> *hashtable
,
103 vec
<histogram_entry
*> &histogram
,
104 gcov_type count
, int time
, int size
)
106 histogram_entry key
= {count
, 0, 0};
107 histogram_entry
**val
= hashtable
->find_slot (&key
, INSERT
);
111 *val
= histogram_pool
.allocate ();
113 histogram
.safe_push (*val
);
115 (*val
)->time
+= time
;
116 (*val
)->size
+= size
;
120 cmp_counts (const void *v1
, const void *v2
)
122 const histogram_entry
*h1
= *(const histogram_entry
* const *)v1
;
123 const histogram_entry
*h2
= *(const histogram_entry
* const *)v2
;
124 if (h1
->count
< h2
->count
)
126 if (h1
->count
> h2
->count
)
131 /* Dump HISTOGRAM to FILE. */
134 dump_histogram (FILE *file
, vec
<histogram_entry
*> histogram
)
137 gcov_type overall_time
= 0, cumulated_time
= 0, cumulated_size
= 0, overall_size
= 0;
139 fprintf (dump_file
, "Histogram:\n");
140 for (i
= 0; i
< histogram
.length (); i
++)
142 overall_time
+= histogram
[i
]->count
* histogram
[i
]->time
;
143 overall_size
+= histogram
[i
]->size
;
149 for (i
= 0; i
< histogram
.length (); i
++)
151 cumulated_time
+= histogram
[i
]->count
* histogram
[i
]->time
;
152 cumulated_size
+= histogram
[i
]->size
;
153 fprintf (file
, " %" PRId64
": time:%i (%2.2f) size:%i (%2.2f)\n",
154 (int64_t) histogram
[i
]->count
,
156 cumulated_time
* 100.0 / overall_time
,
158 cumulated_size
* 100.0 / overall_size
);
162 /* Collect histogram from CFG profiles. */
165 ipa_profile_generate_summary (void)
167 struct cgraph_node
*node
;
168 gimple_stmt_iterator gsi
;
171 hash_table
<histogram_hash
> hashtable (10);
173 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
174 if (ENTRY_BLOCK_PTR_FOR_FN (DECL_STRUCT_FUNCTION (node
->decl
))->count
.ipa_p ())
175 FOR_EACH_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
179 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
181 gimple
*stmt
= gsi_stmt (gsi
);
182 if (gimple_code (stmt
) == GIMPLE_CALL
183 && !gimple_call_fndecl (stmt
))
186 h
= gimple_histogram_value_of_type
187 (DECL_STRUCT_FUNCTION (node
->decl
),
188 stmt
, HIST_TYPE_INDIR_CALL
);
189 /* No need to do sanity check: gimple_ic_transform already
190 takes away bad histograms. */
193 gcov_type val
, count
, all
;
194 if (get_nth_most_common_value (NULL
, "indirect call", h
,
197 struct cgraph_edge
* e
= node
->get_edge (stmt
);
198 if (e
&& !e
->indirect_unknown_callee
)
201 e
->indirect_info
->common_target_id
= val
;
202 e
->indirect_info
->common_target_probability
203 = GCOV_COMPUTE_SCALE (count
, all
);
204 if (e
->indirect_info
->common_target_probability
> REG_BR_PROB_BASE
)
207 fprintf (dump_file
, "Probability capped to 1\n");
208 e
->indirect_info
->common_target_probability
= REG_BR_PROB_BASE
;
211 gimple_remove_histogram_value (DECL_STRUCT_FUNCTION (node
->decl
),
215 time
+= estimate_num_insns (stmt
, &eni_time_weights
);
216 size
+= estimate_num_insns (stmt
, &eni_size_weights
);
218 if (bb
->count
.ipa_p () && bb
->count
.initialized_p ())
219 account_time_size (&hashtable
, histogram
, bb
->count
.ipa ().to_gcov_type (),
222 histogram
.qsort (cmp_counts
);
225 /* Serialize the ipa info for lto. */
228 ipa_profile_write_summary (void)
230 struct lto_simple_output_block
*ob
231 = lto_create_simple_output_block (LTO_section_ipa_profile
);
234 streamer_write_uhwi_stream (ob
->main_stream
, histogram
.length ());
235 for (i
= 0; i
< histogram
.length (); i
++)
237 streamer_write_gcov_count_stream (ob
->main_stream
, histogram
[i
]->count
);
238 streamer_write_uhwi_stream (ob
->main_stream
, histogram
[i
]->time
);
239 streamer_write_uhwi_stream (ob
->main_stream
, histogram
[i
]->size
);
241 lto_destroy_simple_output_block (ob
);
244 /* Deserialize the ipa info for lto. */
247 ipa_profile_read_summary (void)
249 struct lto_file_decl_data
** file_data_vec
250 = lto_get_file_decl_data ();
251 struct lto_file_decl_data
* file_data
;
254 hash_table
<histogram_hash
> hashtable (10);
256 while ((file_data
= file_data_vec
[j
++]))
260 class lto_input_block
*ib
261 = lto_create_simple_input_block (file_data
,
262 LTO_section_ipa_profile
,
266 unsigned int num
= streamer_read_uhwi (ib
);
268 for (n
= 0; n
< num
; n
++)
270 gcov_type count
= streamer_read_gcov_count (ib
);
271 int time
= streamer_read_uhwi (ib
);
272 int size
= streamer_read_uhwi (ib
);
273 account_time_size (&hashtable
, histogram
,
276 lto_destroy_simple_input_block (file_data
,
277 LTO_section_ipa_profile
,
281 histogram
.qsort (cmp_counts
);
284 /* Data used by ipa_propagate_frequency. */
286 struct ipa_propagate_frequency_data
288 cgraph_node
*function_symbol
;
289 bool maybe_unlikely_executed
;
290 bool maybe_executed_once
;
291 bool only_called_at_startup
;
292 bool only_called_at_exit
;
295 /* Worker for ipa_propagate_frequency_1. */
298 ipa_propagate_frequency_1 (struct cgraph_node
*node
, void *data
)
300 struct ipa_propagate_frequency_data
*d
;
301 struct cgraph_edge
*edge
;
303 d
= (struct ipa_propagate_frequency_data
*)data
;
304 for (edge
= node
->callers
;
305 edge
&& (d
->maybe_unlikely_executed
|| d
->maybe_executed_once
306 || d
->only_called_at_startup
|| d
->only_called_at_exit
);
307 edge
= edge
->next_caller
)
309 if (edge
->caller
!= d
->function_symbol
)
311 d
->only_called_at_startup
&= edge
->caller
->only_called_at_startup
;
312 /* It makes sense to put main() together with the static constructors.
313 It will be executed for sure, but rest of functions called from
314 main are definitely not at startup only. */
315 if (MAIN_NAME_P (DECL_NAME (edge
->caller
->decl
)))
316 d
->only_called_at_startup
= 0;
317 d
->only_called_at_exit
&= edge
->caller
->only_called_at_exit
;
320 /* When profile feedback is available, do not try to propagate too hard;
321 counts are already good guide on function frequencies and roundoff
322 errors can make us to push function into unlikely section even when
323 it is executed by the train run. Transfer the function only if all
324 callers are unlikely executed. */
326 && !(edge
->callee
->count
.ipa () == profile_count::zero ())
327 && (edge
->caller
->frequency
!= NODE_FREQUENCY_UNLIKELY_EXECUTED
328 || (edge
->caller
->inlined_to
329 && edge
->caller
->inlined_to
->frequency
330 != NODE_FREQUENCY_UNLIKELY_EXECUTED
)))
331 d
->maybe_unlikely_executed
= false;
332 if (edge
->count
.ipa ().initialized_p ()
333 && !edge
->count
.ipa ().nonzero_p ())
335 switch (edge
->caller
->frequency
)
337 case NODE_FREQUENCY_UNLIKELY_EXECUTED
:
339 case NODE_FREQUENCY_EXECUTED_ONCE
:
341 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
342 fprintf (dump_file
, " Called by %s that is executed once\n",
343 edge
->caller
->name ());
344 d
->maybe_unlikely_executed
= false;
345 ipa_call_summary
*s
= ipa_call_summaries
->get (edge
);
346 if (s
!= NULL
&& s
->loop_depth
)
348 d
->maybe_executed_once
= false;
349 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
350 fprintf (dump_file
, " Called in loop\n");
354 case NODE_FREQUENCY_HOT
:
355 case NODE_FREQUENCY_NORMAL
:
356 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
357 fprintf (dump_file
, " Called by %s that is normal or hot\n",
358 edge
->caller
->name ());
359 d
->maybe_unlikely_executed
= false;
360 d
->maybe_executed_once
= false;
367 /* Return ture if NODE contains hot calls. */
370 contains_hot_call_p (struct cgraph_node
*node
)
372 struct cgraph_edge
*e
;
373 for (e
= node
->callees
; e
; e
= e
->next_callee
)
374 if (e
->maybe_hot_p ())
376 else if (!e
->inline_failed
377 && contains_hot_call_p (e
->callee
))
379 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
380 if (e
->maybe_hot_p ())
385 /* See if the frequency of NODE can be updated based on frequencies of its
388 ipa_propagate_frequency (struct cgraph_node
*node
)
390 struct ipa_propagate_frequency_data d
= {node
, true, true, true, true};
391 bool changed
= false;
393 /* We cannot propagate anything useful about externally visible functions
394 nor about virtuals. */
397 || (opt_for_fn (node
->decl
, flag_devirtualize
)
398 && DECL_VIRTUAL_P (node
->decl
)))
400 gcc_assert (node
->analyzed
);
401 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
402 fprintf (dump_file
, "Processing frequency %s\n", node
->name ());
404 node
->call_for_symbol_and_aliases (ipa_propagate_frequency_1
, &d
,
407 if ((d
.only_called_at_startup
&& !d
.only_called_at_exit
)
408 && !node
->only_called_at_startup
)
410 node
->only_called_at_startup
= true;
412 fprintf (dump_file
, "Node %s promoted to only called at startup.\n",
416 if ((d
.only_called_at_exit
&& !d
.only_called_at_startup
)
417 && !node
->only_called_at_exit
)
419 node
->only_called_at_exit
= true;
421 fprintf (dump_file
, "Node %s promoted to only called at exit.\n",
426 /* With profile we can decide on hot/normal based on count. */
427 if (node
->count
. ipa().initialized_p ())
430 if (!(node
->count
. ipa() == profile_count::zero ())
431 && node
->count
. ipa() >= get_hot_bb_threshold ())
434 hot
|= contains_hot_call_p (node
);
437 if (node
->frequency
!= NODE_FREQUENCY_HOT
)
440 fprintf (dump_file
, "Node %s promoted to hot.\n",
442 node
->frequency
= NODE_FREQUENCY_HOT
;
447 else if (node
->frequency
== NODE_FREQUENCY_HOT
)
450 fprintf (dump_file
, "Node %s reduced to normal.\n",
452 node
->frequency
= NODE_FREQUENCY_NORMAL
;
456 /* These come either from profile or user hints; never update them. */
457 if (node
->frequency
== NODE_FREQUENCY_HOT
458 || node
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
)
460 if (d
.maybe_unlikely_executed
)
462 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
464 fprintf (dump_file
, "Node %s promoted to unlikely executed.\n",
468 else if (d
.maybe_executed_once
&& node
->frequency
!= NODE_FREQUENCY_EXECUTED_ONCE
)
470 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
472 fprintf (dump_file
, "Node %s promoted to executed once.\n",
479 /* Check that number of arguments of N agrees with E.
480 Be conservative when summaries are not present. */
483 check_argument_count (struct cgraph_node
*n
, struct cgraph_edge
*e
)
485 if (!ipa_node_params_sum
|| !ipa_edge_args_sum
)
487 class ipa_node_params
*info
= IPA_NODE_REF (n
->function_symbol ());
490 ipa_edge_args
*e_info
= IPA_EDGE_REF (e
);
493 if (ipa_get_param_count (info
) != ipa_get_cs_argument_count (e_info
)
494 && (ipa_get_param_count (info
) >= ipa_get_cs_argument_count (e_info
)
495 || !stdarg_p (TREE_TYPE (n
->decl
))))
500 /* Simple ipa profile pass propagating frequencies across the callgraph. */
505 struct cgraph_node
**order
;
506 struct cgraph_edge
*e
;
508 bool something_changed
= false;
510 gcov_type overall_time
= 0, cutoff
= 0, cumulated
= 0, overall_size
= 0;
511 struct cgraph_node
*n
,*n2
;
512 int nindirect
= 0, ncommon
= 0, nunknown
= 0, nuseless
= 0, nconverted
= 0;
513 int nmismatch
= 0, nimpossible
= 0;
514 bool node_map_initialized
= false;
517 dump_histogram (dump_file
, histogram
);
518 for (i
= 0; i
< (int)histogram
.length (); i
++)
520 overall_time
+= histogram
[i
]->count
* histogram
[i
]->time
;
521 overall_size
+= histogram
[i
]->size
;
527 gcc_assert (overall_size
);
529 cutoff
= (overall_time
* param_hot_bb_count_ws_permille
+ 500) / 1000;
531 for (i
= 0; cumulated
< cutoff
; i
++)
533 cumulated
+= histogram
[i
]->count
* histogram
[i
]->time
;
534 threshold
= histogram
[i
]->count
;
540 gcov_type cumulated_time
= 0, cumulated_size
= 0;
543 i
< (int)histogram
.length () && histogram
[i
]->count
>= threshold
;
546 cumulated_time
+= histogram
[i
]->count
* histogram
[i
]->time
;
547 cumulated_size
+= histogram
[i
]->size
;
549 fprintf (dump_file
, "Determined min count: %" PRId64
550 " Time:%3.2f%% Size:%3.2f%%\n",
552 cumulated_time
* 100.0 / overall_time
,
553 cumulated_size
* 100.0 / overall_size
);
559 fprintf (dump_file
, "Setting hotness threshold in LTO mode.\n");
560 set_hot_bb_threshold (threshold
);
563 histogram
.release ();
564 histogram_pool
.release ();
566 /* Produce speculative calls: we saved common target from porfiling into
567 e->common_target_id. Now, at link time, we can look up corresponding
568 function node and produce speculative call. */
570 FOR_EACH_DEFINED_FUNCTION (n
)
574 if (!opt_for_fn (n
->decl
, flag_ipa_profile
))
577 for (e
= n
->indirect_calls
; e
; e
= e
->next_callee
)
579 if (n
->count
.initialized_p ())
581 if (e
->indirect_info
->common_target_id
)
583 if (!node_map_initialized
)
584 init_node_map (false);
585 node_map_initialized
= true;
587 n2
= find_func_by_profile_id (e
->indirect_info
->common_target_id
);
592 fprintf (dump_file
, "Indirect call -> direct call from"
593 " other module %s => %s, prob %3.2f\n",
596 e
->indirect_info
->common_target_probability
597 / (float)REG_BR_PROB_BASE
);
599 if (e
->indirect_info
->common_target_probability
600 < REG_BR_PROB_BASE
/ 2)
605 "Not speculating: probability is too low.\n");
607 else if (!e
->maybe_hot_p ())
612 "Not speculating: call is cold.\n");
614 else if (n2
->get_availability () <= AVAIL_INTERPOSABLE
615 && n2
->can_be_discarded_p ())
620 "Not speculating: target is overwritable "
621 "and can be discarded.\n");
623 else if (!check_argument_count (n2
, e
))
629 "parameter count mismatch\n");
631 else if (e
->indirect_info
->polymorphic
632 && !opt_for_fn (n
->decl
, flag_devirtualize
)
633 && !possible_polymorphic_call_target_p (e
, n2
))
639 "function is not in the polymorphic "
640 "call target list\n");
644 /* Target may be overwritable, but profile says that
645 control flow goes to this particular implementation
646 of N2. Speculate on the local alias to allow inlining.
648 if (!n2
->can_be_discarded_p ())
651 alias
= dyn_cast
<cgraph_node
*> (n2
->noninterposable_alias ());
658 e
->count
.apply_probability
659 (e
->indirect_info
->common_target_probability
));
666 fprintf (dump_file
, "Function with profile-id %i not found.\n",
667 e
->indirect_info
->common_target_id
);
673 ipa_update_overall_fn_summary (n
);
675 if (node_map_initialized
)
677 if (dump_file
&& nindirect
)
679 "%i indirect calls trained.\n"
680 "%i (%3.2f%%) have common target.\n"
681 "%i (%3.2f%%) targets was not found.\n"
682 "%i (%3.2f%%) targets had parameter count mismatch.\n"
683 "%i (%3.2f%%) targets was not in polymorphic call target list.\n"
684 "%i (%3.2f%%) speculations seems useless.\n"
685 "%i (%3.2f%%) speculations produced.\n",
687 ncommon
, ncommon
* 100.0 / nindirect
,
688 nunknown
, nunknown
* 100.0 / nindirect
,
689 nmismatch
, nmismatch
* 100.0 / nindirect
,
690 nimpossible
, nimpossible
* 100.0 / nindirect
,
691 nuseless
, nuseless
* 100.0 / nindirect
,
692 nconverted
, nconverted
* 100.0 / nindirect
);
694 order
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
695 order_pos
= ipa_reverse_postorder (order
);
696 for (i
= order_pos
- 1; i
>= 0; i
--)
699 && opt_for_fn (order
[i
]->decl
, flag_ipa_profile
)
700 && ipa_propagate_frequency (order
[i
]))
702 for (e
= order
[i
]->callees
; e
; e
= e
->next_callee
)
703 if (e
->callee
->local
&& !e
->callee
->aux
)
705 something_changed
= true;
706 e
->callee
->aux
= (void *)1;
709 order
[i
]->aux
= NULL
;
712 while (something_changed
)
714 something_changed
= false;
715 for (i
= order_pos
- 1; i
>= 0; i
--)
718 && opt_for_fn (order
[i
]->decl
, flag_ipa_profile
)
719 && ipa_propagate_frequency (order
[i
]))
721 for (e
= order
[i
]->callees
; e
; e
= e
->next_callee
)
722 if (e
->callee
->local
&& !e
->callee
->aux
)
724 something_changed
= true;
725 e
->callee
->aux
= (void *)1;
728 order
[i
]->aux
= NULL
;
737 const pass_data pass_data_ipa_profile
=
740 "profile_estimate", /* name */
741 OPTGROUP_NONE
, /* optinfo_flags */
742 TV_IPA_PROFILE
, /* tv_id */
743 0, /* properties_required */
744 0, /* properties_provided */
745 0, /* properties_destroyed */
746 0, /* todo_flags_start */
747 0, /* todo_flags_finish */
750 class pass_ipa_profile
: public ipa_opt_pass_d
753 pass_ipa_profile (gcc::context
*ctxt
)
754 : ipa_opt_pass_d (pass_data_ipa_profile
, ctxt
,
755 ipa_profile_generate_summary
, /* generate_summary */
756 ipa_profile_write_summary
, /* write_summary */
757 ipa_profile_read_summary
, /* read_summary */
758 NULL
, /* write_optimization_summary */
759 NULL
, /* read_optimization_summary */
760 NULL
, /* stmt_fixup */
761 0, /* function_transform_todo_flags_start */
762 NULL
, /* function_transform */
763 NULL
) /* variable_transform */
766 /* opt_pass methods: */
767 virtual bool gate (function
*) { return flag_ipa_profile
|| in_lto_p
; }
768 virtual unsigned int execute (function
*) { return ipa_profile (); }
770 }; // class pass_ipa_profile
775 make_pass_ipa_profile (gcc::context
*ctxt
)
777 return new pass_ipa_profile (ctxt
);