1 /* Basic IPA optimizations based on profile.
2 Copyright (C) 2003-2014 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 Similar histogram is also estimated by coverage runtime. This histogram
29 is not dependent on LTO, but it suffers from various defects; first
30 gcov runtime is not weighting individual basic block by estimated execution
31 time and second the merging of multiple runs makes assumption that the
32 histogram distribution did not change. Consequentely histogram constructed
33 here may be more precise.
35 The information is used to set hot/cold thresholds.
36 - Next speculative indirect call resolution is performed: the local
37 profile pass assigns profile-id to each function and provide us with a
38 histogram specifying the most common target. We look up the callgraph
39 node corresponding to the target and produce a speculative call.
41 This call may or may not survive through IPA optimization based on decision
43 - Finally we propagate the following flags: unlikely executed, executed
44 once, executed at startup and executed at exit. These flags are used to
45 control code size/performance threshold and and code placement (by producing
46 .text.unlikely/.text.hot/.text.startup/.text.exit subsections). */
49 #include "coretypes.h"
53 #include "dominance.h"
55 #include "basic-block.h"
58 #include "plugin-api.h"
63 #include "hard-reg-set.h"
68 #include "tree-pass.h"
69 #include "tree-ssa-alias.h"
70 #include "internal-fn.h"
71 #include "gimple-expr.h"
73 #include "gimple-iterator.h"
76 #include "tree-iterator.h"
77 #include "ipa-utils.h"
80 #include "value-prof.h"
81 #include "alloc-pool.h"
82 #include "tree-inline.h"
83 #include "lto-streamer.h"
84 #include "data-streamer.h"
86 #include "ipa-inline.h"
88 /* Entry in the histogram. */
90 struct histogram_entry
97 /* Histogram of profile values.
98 The histogram is represented as an ordered vector of entries allocated via
99 histogram_pool. During construction a separate hashtable is kept to lookup
100 duplicate entries. */
102 vec
<histogram_entry
*> histogram
;
103 static alloc_pool histogram_pool
;
105 /* Hashtable support for storing SSA names hashed by their SSA_NAME_VAR. */
107 struct histogram_hash
: typed_noop_remove
<histogram_entry
>
109 typedef histogram_entry value_type
;
110 typedef histogram_entry compare_type
;
111 static inline hashval_t
hash (const value_type
*);
112 static inline int equal (const value_type
*, const compare_type
*);
116 histogram_hash::hash (const histogram_entry
*val
)
122 histogram_hash::equal (const histogram_entry
*val
, const histogram_entry
*val2
)
124 return val
->count
== val2
->count
;
127 /* Account TIME and SIZE executed COUNT times into HISTOGRAM.
128 HASHTABLE is the on-side hash kept to avoid duplicates. */
131 account_time_size (hash_table
<histogram_hash
> *hashtable
,
132 vec
<histogram_entry
*> &histogram
,
133 gcov_type count
, int time
, int size
)
135 histogram_entry key
= {count
, 0, 0};
136 histogram_entry
**val
= hashtable
->find_slot (&key
, INSERT
);
140 *val
= (histogram_entry
*) pool_alloc (histogram_pool
);
142 histogram
.safe_push (*val
);
144 (*val
)->time
+= time
;
145 (*val
)->size
+= size
;
149 cmp_counts (const void *v1
, const void *v2
)
151 const histogram_entry
*h1
= *(const histogram_entry
* const *)v1
;
152 const histogram_entry
*h2
= *(const histogram_entry
* const *)v2
;
153 if (h1
->count
< h2
->count
)
155 if (h1
->count
> h2
->count
)
160 /* Dump HISTOGRAM to FILE. */
163 dump_histogram (FILE *file
, vec
<histogram_entry
*> histogram
)
166 gcov_type overall_time
= 0, cumulated_time
= 0, cumulated_size
= 0, overall_size
= 0;
168 fprintf (dump_file
, "Histogram:\n");
169 for (i
= 0; i
< histogram
.length (); i
++)
171 overall_time
+= histogram
[i
]->count
* histogram
[i
]->time
;
172 overall_size
+= histogram
[i
]->size
;
178 for (i
= 0; i
< histogram
.length (); i
++)
180 cumulated_time
+= histogram
[i
]->count
* histogram
[i
]->time
;
181 cumulated_size
+= histogram
[i
]->size
;
182 fprintf (file
, " %"PRId64
": time:%i (%2.2f) size:%i (%2.2f)\n",
183 (int64_t) histogram
[i
]->count
,
185 cumulated_time
* 100.0 / overall_time
,
187 cumulated_size
* 100.0 / overall_size
);
191 /* Collect histogram from CFG profiles. */
194 ipa_profile_generate_summary (void)
196 struct cgraph_node
*node
;
197 gimple_stmt_iterator gsi
;
200 hash_table
<histogram_hash
> hashtable (10);
201 histogram_pool
= create_alloc_pool ("IPA histogram", sizeof (struct histogram_entry
),
204 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
205 FOR_EACH_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
209 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
211 gimple stmt
= gsi_stmt (gsi
);
212 if (gimple_code (stmt
) == GIMPLE_CALL
213 && !gimple_call_fndecl (stmt
))
216 h
= gimple_histogram_value_of_type
217 (DECL_STRUCT_FUNCTION (node
->decl
),
218 stmt
, HIST_TYPE_INDIR_CALL
);
219 /* No need to do sanity check: gimple_ic_transform already
220 takes away bad histograms. */
223 /* counter 0 is target, counter 1 is number of execution we called target,
224 counter 2 is total number of executions. */
225 if (h
->hvalue
.counters
[2])
227 struct cgraph_edge
* e
= node
->get_edge (stmt
);
228 if (e
&& !e
->indirect_unknown_callee
)
230 e
->indirect_info
->common_target_id
231 = h
->hvalue
.counters
[0];
232 e
->indirect_info
->common_target_probability
233 = GCOV_COMPUTE_SCALE (h
->hvalue
.counters
[1], h
->hvalue
.counters
[2]);
234 if (e
->indirect_info
->common_target_probability
> REG_BR_PROB_BASE
)
237 fprintf (dump_file
, "Probability capped to 1\n");
238 e
->indirect_info
->common_target_probability
= REG_BR_PROB_BASE
;
241 gimple_remove_histogram_value (DECL_STRUCT_FUNCTION (node
->decl
),
245 time
+= estimate_num_insns (stmt
, &eni_time_weights
);
246 size
+= estimate_num_insns (stmt
, &eni_size_weights
);
248 account_time_size (&hashtable
, histogram
, bb
->count
, time
, size
);
250 histogram
.qsort (cmp_counts
);
253 /* Serialize the ipa info for lto. */
256 ipa_profile_write_summary (void)
258 struct lto_simple_output_block
*ob
259 = lto_create_simple_output_block (LTO_section_ipa_profile
);
262 streamer_write_uhwi_stream (ob
->main_stream
, histogram
.length ());
263 for (i
= 0; i
< histogram
.length (); i
++)
265 streamer_write_gcov_count_stream (ob
->main_stream
, histogram
[i
]->count
);
266 streamer_write_uhwi_stream (ob
->main_stream
, histogram
[i
]->time
);
267 streamer_write_uhwi_stream (ob
->main_stream
, histogram
[i
]->size
);
269 lto_destroy_simple_output_block (ob
);
272 /* Deserialize the ipa info for lto. */
275 ipa_profile_read_summary (void)
277 struct lto_file_decl_data
** file_data_vec
278 = lto_get_file_decl_data ();
279 struct lto_file_decl_data
* file_data
;
282 hash_table
<histogram_hash
> hashtable (10);
283 histogram_pool
= create_alloc_pool ("IPA histogram", sizeof (struct histogram_entry
),
286 while ((file_data
= file_data_vec
[j
++]))
290 struct lto_input_block
*ib
291 = lto_create_simple_input_block (file_data
,
292 LTO_section_ipa_profile
,
296 unsigned int num
= streamer_read_uhwi (ib
);
298 for (n
= 0; n
< num
; n
++)
300 gcov_type count
= streamer_read_gcov_count (ib
);
301 int time
= streamer_read_uhwi (ib
);
302 int size
= streamer_read_uhwi (ib
);
303 account_time_size (&hashtable
, histogram
,
306 lto_destroy_simple_input_block (file_data
,
307 LTO_section_ipa_profile
,
311 histogram
.qsort (cmp_counts
);
314 /* Data used by ipa_propagate_frequency. */
316 struct ipa_propagate_frequency_data
318 bool maybe_unlikely_executed
;
319 bool maybe_executed_once
;
320 bool only_called_at_startup
;
321 bool only_called_at_exit
;
324 /* Worker for ipa_propagate_frequency_1. */
327 ipa_propagate_frequency_1 (struct cgraph_node
*node
, void *data
)
329 struct ipa_propagate_frequency_data
*d
;
330 struct cgraph_edge
*edge
;
332 d
= (struct ipa_propagate_frequency_data
*)data
;
333 for (edge
= node
->callers
;
334 edge
&& (d
->maybe_unlikely_executed
|| d
->maybe_executed_once
335 || d
->only_called_at_startup
|| d
->only_called_at_exit
);
336 edge
= edge
->next_caller
)
338 if (edge
->caller
!= node
)
340 d
->only_called_at_startup
&= edge
->caller
->only_called_at_startup
;
341 /* It makes sense to put main() together with the static constructors.
342 It will be executed for sure, but rest of functions called from
343 main are definitely not at startup only. */
344 if (MAIN_NAME_P (DECL_NAME (edge
->caller
->decl
)))
345 d
->only_called_at_startup
= 0;
346 d
->only_called_at_exit
&= edge
->caller
->only_called_at_exit
;
349 /* When profile feedback is available, do not try to propagate too hard;
350 counts are already good guide on function frequencies and roundoff
351 errors can make us to push function into unlikely section even when
352 it is executed by the train run. Transfer the function only if all
353 callers are unlikely executed. */
354 if (profile_info
&& flag_branch_probabilities
355 && (edge
->caller
->frequency
!= NODE_FREQUENCY_UNLIKELY_EXECUTED
356 || (edge
->caller
->global
.inlined_to
357 && edge
->caller
->global
.inlined_to
->frequency
358 != NODE_FREQUENCY_UNLIKELY_EXECUTED
)))
359 d
->maybe_unlikely_executed
= false;
360 if (!edge
->frequency
)
362 switch (edge
->caller
->frequency
)
364 case NODE_FREQUENCY_UNLIKELY_EXECUTED
:
366 case NODE_FREQUENCY_EXECUTED_ONCE
:
367 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
368 fprintf (dump_file
, " Called by %s that is executed once\n",
369 edge
->caller
->name ());
370 d
->maybe_unlikely_executed
= false;
371 if (inline_edge_summary (edge
)->loop_depth
)
373 d
->maybe_executed_once
= false;
374 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
375 fprintf (dump_file
, " Called in loop\n");
378 case NODE_FREQUENCY_HOT
:
379 case NODE_FREQUENCY_NORMAL
:
380 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
381 fprintf (dump_file
, " Called by %s that is normal or hot\n",
382 edge
->caller
->name ());
383 d
->maybe_unlikely_executed
= false;
384 d
->maybe_executed_once
= false;
391 /* Return ture if NODE contains hot calls. */
394 contains_hot_call_p (struct cgraph_node
*node
)
396 struct cgraph_edge
*e
;
397 for (e
= node
->callees
; e
; e
= e
->next_callee
)
398 if (e
->maybe_hot_p ())
400 else if (!e
->inline_failed
401 && contains_hot_call_p (e
->callee
))
403 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
404 if (e
->maybe_hot_p ())
409 /* See if the frequency of NODE can be updated based on frequencies of its
412 ipa_propagate_frequency (struct cgraph_node
*node
)
414 struct ipa_propagate_frequency_data d
= {true, true, true, true};
415 bool changed
= false;
417 /* We can not propagate anything useful about externally visible functions
418 nor about virtuals. */
419 if (!node
->local
.local
421 || (flag_devirtualize
&& DECL_VIRTUAL_P (node
->decl
)))
423 gcc_assert (node
->analyzed
);
424 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
425 fprintf (dump_file
, "Processing frequency %s\n", node
->name ());
427 node
->call_for_symbol_thunks_and_aliases (ipa_propagate_frequency_1
, &d
,
430 if ((d
.only_called_at_startup
&& !d
.only_called_at_exit
)
431 && !node
->only_called_at_startup
)
433 node
->only_called_at_startup
= true;
435 fprintf (dump_file
, "Node %s promoted to only called at startup.\n",
439 if ((d
.only_called_at_exit
&& !d
.only_called_at_startup
)
440 && !node
->only_called_at_exit
)
442 node
->only_called_at_exit
= true;
444 fprintf (dump_file
, "Node %s promoted to only called at exit.\n",
449 /* With profile we can decide on hot/normal based on count. */
453 if (node
->count
>= get_hot_bb_threshold ())
456 hot
|= contains_hot_call_p (node
);
459 if (node
->frequency
!= NODE_FREQUENCY_HOT
)
462 fprintf (dump_file
, "Node %s promoted to hot.\n",
464 node
->frequency
= NODE_FREQUENCY_HOT
;
469 else if (node
->frequency
== NODE_FREQUENCY_HOT
)
472 fprintf (dump_file
, "Node %s reduced to normal.\n",
474 node
->frequency
= NODE_FREQUENCY_NORMAL
;
478 /* These come either from profile or user hints; never update them. */
479 if (node
->frequency
== NODE_FREQUENCY_HOT
480 || node
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
)
482 if (d
.maybe_unlikely_executed
)
484 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
486 fprintf (dump_file
, "Node %s promoted to unlikely executed.\n",
490 else if (d
.maybe_executed_once
&& node
->frequency
!= NODE_FREQUENCY_EXECUTED_ONCE
)
492 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
494 fprintf (dump_file
, "Node %s promoted to executed once.\n",
501 /* Simple ipa profile pass propagating frequencies across the callgraph. */
506 struct cgraph_node
**order
;
507 struct cgraph_edge
*e
;
509 bool something_changed
= false;
511 gcov_type overall_time
= 0, cutoff
= 0, cumulated
= 0, overall_size
= 0;
512 struct cgraph_node
*n
,*n2
;
513 int nindirect
= 0, ncommon
= 0, nunknown
= 0, nuseless
= 0, nconverted
= 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
);
530 gcov_type min
, cumulated_time
= 0, cumulated_size
= 0;
532 fprintf (dump_file
, "Overall time: %"PRId64
"\n",
533 (int64_t)overall_time
);
534 min
= get_hot_bb_threshold ();
535 for (i
= 0; i
< (int)histogram
.length () && histogram
[i
]->count
>= min
;
538 cumulated_time
+= histogram
[i
]->count
* histogram
[i
]->time
;
539 cumulated_size
+= histogram
[i
]->size
;
541 fprintf (dump_file
, "GCOV min count: %"PRId64
542 " Time:%3.2f%% Size:%3.2f%%\n",
544 cumulated_time
* 100.0 / overall_time
,
545 cumulated_size
* 100.0 / overall_size
);
547 cutoff
= (overall_time
* PARAM_VALUE (HOT_BB_COUNT_WS_PERMILLE
) + 500) / 1000;
549 for (i
= 0; cumulated
< cutoff
; i
++)
551 cumulated
+= histogram
[i
]->count
* histogram
[i
]->time
;
552 threshold
= histogram
[i
]->count
;
558 gcov_type cumulated_time
= 0, cumulated_size
= 0;
561 i
< (int)histogram
.length () && histogram
[i
]->count
>= threshold
;
564 cumulated_time
+= histogram
[i
]->count
* histogram
[i
]->time
;
565 cumulated_size
+= histogram
[i
]->size
;
567 fprintf (dump_file
, "Determined min count: %"PRId64
568 " Time:%3.2f%% Size:%3.2f%%\n",
570 cumulated_time
* 100.0 / overall_time
,
571 cumulated_size
* 100.0 / overall_size
);
573 if (threshold
> get_hot_bb_threshold ()
577 fprintf (dump_file
, "Threshold updated.\n");
578 set_hot_bb_threshold (threshold
);
581 histogram
.release ();
582 free_alloc_pool (histogram_pool
);
584 /* Produce speculative calls: we saved common traget from porfiling into
585 e->common_target_id. Now, at link time, we can look up corresponding
586 function node and produce speculative call. */
588 FOR_EACH_DEFINED_FUNCTION (n
)
592 for (e
= n
->indirect_calls
; e
; e
= e
->next_callee
)
596 if (e
->indirect_info
->common_target_id
)
598 if (!node_map_initialized
)
599 init_node_map (false);
600 node_map_initialized
= true;
602 n2
= find_func_by_profile_id (e
->indirect_info
->common_target_id
);
607 fprintf (dump_file
, "Indirect call -> direct call from"
608 " other module %s/%i => %s/%i, prob %3.2f\n",
609 xstrdup (n
->name ()), n
->order
,
610 xstrdup (n2
->name ()), n2
->order
,
611 e
->indirect_info
->common_target_probability
612 / (float)REG_BR_PROB_BASE
);
614 if (e
->indirect_info
->common_target_probability
615 < REG_BR_PROB_BASE
/ 2)
620 "Not speculating: probability is too low.\n");
622 else if (!e
->maybe_hot_p ())
627 "Not speculating: call is cold.\n");
629 else if (n2
->get_availability () <= AVAIL_INTERPOSABLE
630 && n2
->can_be_discarded_p ())
635 "Not speculating: target is overwritable "
636 "and can be discarded.\n");
640 /* Target may be overwritable, but profile says that
641 control flow goes to this particular implementation
642 of N2. Speculate on the local alias to allow inlining.
644 if (!n2
->can_be_discarded_p ())
647 alias
= dyn_cast
<cgraph_node
*> (n2
->noninterposable_alias ());
654 apply_scale (e
->count
,
655 e
->indirect_info
->common_target_probability
),
656 apply_scale (e
->frequency
,
657 e
->indirect_info
->common_target_probability
));
664 fprintf (dump_file
, "Function with profile-id %i not found.\n",
665 e
->indirect_info
->common_target_id
);
671 inline_update_overall_summary (n
);
673 if (node_map_initialized
)
675 if (dump_file
&& nindirect
)
677 "%i indirect calls trained.\n"
678 "%i (%3.2f%%) have common target.\n"
679 "%i (%3.2f%%) targets was not found.\n"
680 "%i (%3.2f%%) speculations seems useless.\n"
681 "%i (%3.2f%%) speculations produced.\n",
683 ncommon
, ncommon
* 100.0 / nindirect
,
684 nunknown
, nunknown
* 100.0 / nindirect
,
685 nuseless
, nuseless
* 100.0 / nindirect
,
686 nconverted
, nconverted
* 100.0 / nindirect
);
688 order
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
689 order_pos
= ipa_reverse_postorder (order
);
690 for (i
= order_pos
- 1; i
>= 0; i
--)
692 if (order
[i
]->local
.local
&& ipa_propagate_frequency (order
[i
]))
694 for (e
= order
[i
]->callees
; e
; e
= e
->next_callee
)
695 if (e
->callee
->local
.local
&& !e
->callee
->aux
)
697 something_changed
= true;
698 e
->callee
->aux
= (void *)1;
701 order
[i
]->aux
= NULL
;
704 while (something_changed
)
706 something_changed
= false;
707 for (i
= order_pos
- 1; i
>= 0; i
--)
709 if (order
[i
]->aux
&& ipa_propagate_frequency (order
[i
]))
711 for (e
= order
[i
]->callees
; e
; e
= e
->next_callee
)
712 if (e
->callee
->local
.local
&& !e
->callee
->aux
)
714 something_changed
= true;
715 e
->callee
->aux
= (void *)1;
718 order
[i
]->aux
= NULL
;
727 const pass_data pass_data_ipa_profile
=
730 "profile_estimate", /* name */
731 OPTGROUP_NONE
, /* optinfo_flags */
732 TV_IPA_PROFILE
, /* tv_id */
733 0, /* properties_required */
734 0, /* properties_provided */
735 0, /* properties_destroyed */
736 0, /* todo_flags_start */
737 0, /* todo_flags_finish */
740 class pass_ipa_profile
: public ipa_opt_pass_d
743 pass_ipa_profile (gcc::context
*ctxt
)
744 : ipa_opt_pass_d (pass_data_ipa_profile
, ctxt
,
745 ipa_profile_generate_summary
, /* generate_summary */
746 ipa_profile_write_summary
, /* write_summary */
747 ipa_profile_read_summary
, /* read_summary */
748 NULL
, /* write_optimization_summary */
749 NULL
, /* read_optimization_summary */
750 NULL
, /* stmt_fixup */
751 0, /* function_transform_todo_flags_start */
752 NULL
, /* function_transform */
753 NULL
) /* variable_transform */
756 /* opt_pass methods: */
757 virtual bool gate (function
*) { return flag_ipa_profile
; }
758 virtual unsigned int execute (function
*) { return ipa_profile (); }
760 }; // class pass_ipa_profile
765 make_pass_ipa_profile (gcc::context
*ctxt
)
767 return new pass_ipa_profile (ctxt
);