Branch data Line data Source code
1 : : /* Basic IPA optimizations based on profile.
2 : : Copyright (C) 2003-2025 Free Software Foundation, Inc.
3 : :
4 : : This file is part of GCC.
5 : :
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
9 : : version.
10 : :
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
14 : : for more details.
15 : :
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/>. */
19 : :
20 : : /* ipa-profile pass implements the following analysis propagating profille
21 : : inter-procedurally.
22 : :
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.
27 : :
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.
33 : :
34 : : This call may or may not survive through IPA optimization based on decision
35 : : of inliner.
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). */
40 : : #include "config.h"
41 : : #include "system.h"
42 : : #include "coretypes.h"
43 : : #include "backend.h"
44 : : #include "tree.h"
45 : : #include "gimple.h"
46 : : #include "predict.h"
47 : : #include "alloc-pool.h"
48 : : #include "tree-pass.h"
49 : : #include "cgraph.h"
50 : : #include "data-streamer.h"
51 : : #include "gimple-iterator.h"
52 : : #include "ipa-utils.h"
53 : : #include "profile.h"
54 : : #include "value-prof.h"
55 : : #include "tree-inline.h"
56 : : #include "symbol-summary.h"
57 : : #include "tree-vrp.h"
58 : : #include "sreal.h"
59 : : #include "ipa-cp.h"
60 : : #include "ipa-prop.h"
61 : : #include "ipa-fnsummary.h"
62 : :
63 : : /* Entry in the histogram. */
64 : :
65 : : struct histogram_entry
66 : : {
67 : : gcov_type count;
68 : : int time;
69 : : int size;
70 : : };
71 : :
72 : : /* Histogram of profile values.
73 : : The histogram is represented as an ordered vector of entries allocated via
74 : : histogram_pool. During construction a separate hashtable is kept to lookup
75 : : duplicate entries. */
76 : :
77 : : vec<histogram_entry *> histogram;
78 : : static object_allocator<histogram_entry> histogram_pool ("IPA histogram");
79 : :
80 : : /* Hashtable support for storing SSA names hashed by their SSA_NAME_VAR. */
81 : :
82 : : struct histogram_hash : nofree_ptr_hash <histogram_entry>
83 : : {
84 : : static inline hashval_t hash (const histogram_entry *);
85 : : static inline int equal (const histogram_entry *, const histogram_entry *);
86 : : };
87 : :
88 : : inline hashval_t
89 : 35905 : histogram_hash::hash (const histogram_entry *val)
90 : : {
91 : 35905 : return val->count;
92 : : }
93 : :
94 : : inline int
95 : 18411 : histogram_hash::equal (const histogram_entry *val, const histogram_entry *val2)
96 : : {
97 : 18411 : return val->count == val2->count;
98 : : }
99 : :
100 : : /* Account TIME and SIZE executed COUNT times into HISTOGRAM.
101 : : HASHTABLE is the on-side hash kept to avoid duplicates. */
102 : :
103 : : static void
104 : 17629 : account_time_size (hash_table<histogram_hash> *hashtable,
105 : : vec<histogram_entry *> &histogram,
106 : : gcov_type count, int time, int size)
107 : : {
108 : 17629 : histogram_entry key = {count, 0, 0};
109 : 17629 : histogram_entry **val = hashtable->find_slot (&key, INSERT);
110 : :
111 : 17629 : if (!*val)
112 : : {
113 : 3777 : *val = histogram_pool.allocate ();
114 : 3777 : **val = key;
115 : 3777 : histogram.safe_push (*val);
116 : : }
117 : 17629 : (*val)->time += time;
118 : 17629 : (*val)->size += size;
119 : 17629 : }
120 : :
121 : : int
122 : 4607 : cmp_counts (const void *v1, const void *v2)
123 : : {
124 : 4607 : const histogram_entry *h1 = *(const histogram_entry * const *)v1;
125 : 4607 : const histogram_entry *h2 = *(const histogram_entry * const *)v2;
126 : 4607 : if (h1->count < h2->count)
127 : : return 1;
128 : 2665 : if (h1->count > h2->count)
129 : 2665 : return -1;
130 : : return 0;
131 : : }
132 : :
133 : : /* Dump HISTOGRAM to FILE. */
134 : :
135 : : static void
136 : 27 : dump_histogram (FILE *file, vec<histogram_entry *> histogram)
137 : : {
138 : 27 : unsigned int i;
139 : 27 : gcov_type overall_time = 0, cumulated_time = 0, cumulated_size = 0,
140 : 27 : overall_size = 0;
141 : :
142 : 27 : fprintf (dump_file, "Histogram:\n");
143 : 73 : for (i = 0; i < histogram.length (); i++)
144 : : {
145 : 19 : overall_time += histogram[i]->count * histogram[i]->time;
146 : 19 : overall_size += histogram[i]->size;
147 : : }
148 : 27 : if (!overall_time)
149 : 23 : overall_time = 1;
150 : 27 : if (!overall_size)
151 : 23 : overall_size = 1;
152 : 46 : for (i = 0; i < histogram.length (); i++)
153 : : {
154 : 19 : cumulated_time += histogram[i]->count * histogram[i]->time;
155 : 19 : cumulated_size += histogram[i]->size;
156 : 19 : fprintf (file, " %" PRId64": time:%i (%2.2f) size:%i (%2.2f)\n",
157 : 19 : (int64_t) histogram[i]->count,
158 : 19 : histogram[i]->time,
159 : 19 : cumulated_time * 100.0 / overall_time,
160 : 19 : histogram[i]->size,
161 : 19 : cumulated_size * 100.0 / overall_size);
162 : : }
163 : 27 : }
164 : :
165 : : /* Structure containing speculative target information from profile. */
166 : :
167 : : struct speculative_call_target
168 : : {
169 : 116 : speculative_call_target (unsigned int id = 0, int prob = 0)
170 : 55 : : target_id (id), target_probability (prob)
171 : : {
172 : : }
173 : :
174 : : /* Profile_id of target obtained from profile. */
175 : : unsigned int target_id;
176 : : /* Probability that call will land in function with target_id. */
177 : : unsigned int target_probability;
178 : : };
179 : :
180 : 138876 : class speculative_call_summary
181 : : {
182 : : public:
183 : 138876 : speculative_call_summary () : speculative_call_targets ()
184 : : {}
185 : :
186 : : auto_vec<speculative_call_target> speculative_call_targets;
187 : :
188 : : void dump (FILE *f);
189 : :
190 : : };
191 : :
192 : : /* Class to manage call summaries. */
193 : :
194 : : class ipa_profile_call_summaries
195 : : : public call_summary<speculative_call_summary *>
196 : : {
197 : : public:
198 : 157738 : ipa_profile_call_summaries (symbol_table *table)
199 : 315476 : : call_summary<speculative_call_summary *> (table)
200 : : {}
201 : :
202 : : /* Duplicate info when an edge is cloned. */
203 : : void duplicate (cgraph_edge *, cgraph_edge *,
204 : : speculative_call_summary *old_sum,
205 : : speculative_call_summary *new_sum) final override;
206 : : };
207 : :
208 : : static ipa_profile_call_summaries *call_sums = NULL;
209 : :
210 : : /* Dump all information in speculative call summary to F. */
211 : :
212 : : void
213 : 34 : speculative_call_summary::dump (FILE *f)
214 : : {
215 : 34 : cgraph_node *n2;
216 : :
217 : 34 : unsigned spec_count = speculative_call_targets.length ();
218 : 42 : for (unsigned i = 0; i < spec_count; i++)
219 : : {
220 : 8 : speculative_call_target item = speculative_call_targets[i];
221 : 8 : n2 = find_func_by_profile_id (item.target_id);
222 : 8 : if (n2)
223 : 8 : fprintf (f, " The %i speculative target is %s with prob %3.2f\n", i,
224 : : n2->dump_name (),
225 : 8 : item.target_probability / (float) REG_BR_PROB_BASE);
226 : : else
227 : 0 : fprintf (f, " The %i speculative target is %u with prob %3.2f\n", i,
228 : : item.target_id,
229 : 0 : item.target_probability / (float) REG_BR_PROB_BASE);
230 : : }
231 : 34 : }
232 : :
233 : : /* Duplicate info when an edge is cloned. */
234 : :
235 : : void
236 : 42 : ipa_profile_call_summaries::duplicate (cgraph_edge *, cgraph_edge *,
237 : : speculative_call_summary *old_sum,
238 : : speculative_call_summary *new_sum)
239 : : {
240 : 42 : if (!old_sum)
241 : : return;
242 : :
243 : 42 : unsigned old_count = old_sum->speculative_call_targets.length ();
244 : 42 : if (!old_count)
245 : : return;
246 : :
247 : 42 : new_sum->speculative_call_targets.reserve_exact (old_count);
248 : 42 : new_sum->speculative_call_targets.quick_grow_cleared (old_count);
249 : :
250 : 97 : for (unsigned i = 0; i < old_count; i++)
251 : : {
252 : 165 : new_sum->speculative_call_targets[i]
253 : 55 : = old_sum->speculative_call_targets[i];
254 : : }
255 : : }
256 : :
257 : : /* Collect histogram and speculative target summaries from CFG profiles. */
258 : :
259 : : static void
260 : 144924 : ipa_profile_generate_summary (void)
261 : : {
262 : 144924 : struct cgraph_node *node;
263 : 144924 : gimple_stmt_iterator gsi;
264 : 144924 : basic_block bb;
265 : :
266 : 144924 : hash_table<histogram_hash> hashtable (10);
267 : :
268 : 144924 : gcc_checking_assert (!call_sums);
269 : 144924 : call_sums = new ipa_profile_call_summaries (symtab);
270 : :
271 : 1429125 : FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
272 : 1284201 : if (ENTRY_BLOCK_PTR_FOR_FN
273 : 2568402 : (DECL_STRUCT_FUNCTION (node->decl))->count.ipa_p ())
274 : 27386 : FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
275 : : {
276 : 20989 : int time = 0;
277 : 20989 : int size = 0;
278 : 128337 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
279 : : {
280 : 86359 : gimple *stmt = gsi_stmt (gsi);
281 : 86359 : if (gimple_code (stmt) == GIMPLE_CALL
282 : 86359 : && !gimple_call_fndecl (stmt))
283 : : {
284 : 154 : histogram_value h;
285 : 154 : h = gimple_histogram_value_of_type
286 : 154 : (DECL_STRUCT_FUNCTION (node->decl),
287 : : stmt, HIST_TYPE_INDIR_CALL);
288 : : /* No need to do sanity check: gimple_ic_transform already
289 : : takes away bad histograms. */
290 : 154 : if (h)
291 : : {
292 : 40 : gcov_type val, count, all;
293 : 40 : struct cgraph_edge *e = node->get_edge (stmt);
294 : 40 : if (e && !e->indirect_unknown_callee)
295 : 0 : continue;
296 : :
297 : 40 : speculative_call_summary *csum
298 : 40 : = call_sums->get_create (e);
299 : :
300 : 1320 : for (unsigned j = 0; j < GCOV_TOPN_MAXIMUM_TRACKED_VALUES;
301 : : j++)
302 : : {
303 : 1280 : if (!get_nth_most_common_value (NULL, "indirect call",
304 : : h, &val, &count, &all,
305 : : j))
306 : 1229 : continue;
307 : :
308 : 51 : if (val == 0 || count == 0)
309 : 0 : continue;
310 : :
311 : 51 : if (count > all)
312 : : {
313 : 0 : if (dump_file)
314 : 0 : fprintf (dump_file,
315 : : "Probability capped to 1\n");
316 : 0 : count = all;
317 : : }
318 : 51 : speculative_call_target item (
319 : 51 : val, GCOV_COMPUTE_SCALE (count, all));
320 : 51 : csum->speculative_call_targets.safe_push (item);
321 : : }
322 : :
323 : 40 : gimple_remove_histogram_value
324 : 40 : (DECL_STRUCT_FUNCTION (node->decl), stmt, h);
325 : : }
326 : : }
327 : 86359 : time += estimate_num_insns (stmt, &eni_time_weights);
328 : 86359 : size += estimate_num_insns (stmt, &eni_size_weights);
329 : : }
330 : 55787 : if (bb->count.ipa_p () && bb->count.initialized_p ())
331 : 17399 : account_time_size (&hashtable, histogram,
332 : 34798 : bb->count.ipa ().to_gcov_type (),
333 : : time, size);
334 : : }
335 : 144924 : histogram.qsort (cmp_counts);
336 : 144924 : }
337 : :
338 : : /* Serialize the speculative summary info for LTO. */
339 : :
340 : : static void
341 : 1761 : ipa_profile_write_edge_summary (lto_simple_output_block *ob,
342 : : speculative_call_summary *csum)
343 : : {
344 : 1761 : unsigned len = 0;
345 : :
346 : 1761 : len = csum->speculative_call_targets.length ();
347 : :
348 : 4 : gcc_assert (len <= GCOV_TOPN_MAXIMUM_TRACKED_VALUES);
349 : :
350 : 1761 : streamer_write_hwi_stream (ob->main_stream, len);
351 : :
352 : 1761 : if (len)
353 : : {
354 : 4 : unsigned spec_count = csum->speculative_call_targets.length ();
355 : 14 : for (unsigned i = 0; i < spec_count; i++)
356 : : {
357 : 10 : speculative_call_target item = csum->speculative_call_targets[i];
358 : 10 : gcc_assert (item.target_id);
359 : 10 : streamer_write_hwi_stream (ob->main_stream, item.target_id);
360 : 10 : streamer_write_hwi_stream (ob->main_stream, item.target_probability);
361 : : }
362 : : }
363 : 1761 : }
364 : :
365 : : /* Serialize the ipa info for lto. */
366 : :
367 : : static void
368 : 19145 : ipa_profile_write_summary (void)
369 : : {
370 : 19145 : struct lto_simple_output_block *ob
371 : 19145 : = lto_create_simple_output_block (LTO_section_ipa_profile);
372 : 19145 : unsigned int i;
373 : :
374 : 19145 : streamer_write_uhwi_stream (ob->main_stream, histogram.length ());
375 : 38702 : for (i = 0; i < histogram.length (); i++)
376 : : {
377 : 412 : streamer_write_gcov_count_stream (ob->main_stream, histogram[i]->count);
378 : 412 : streamer_write_uhwi_stream (ob->main_stream, histogram[i]->time);
379 : 412 : streamer_write_uhwi_stream (ob->main_stream, histogram[i]->size);
380 : : }
381 : :
382 : 19145 : if (!call_sums)
383 : 0 : return;
384 : :
385 : : /* Serialize speculative targets information. */
386 : 19145 : unsigned int count = 0;
387 : 19145 : lto_symtab_encoder_t encoder = ob->decl_state->symtab_node_encoder;
388 : 19145 : lto_symtab_encoder_iterator lsei;
389 : 19145 : cgraph_node *node;
390 : :
391 : 110060 : for (lsei = lsei_start_function_in_partition (encoder); !lsei_end_p (lsei);
392 : 90915 : lsei_next_function_in_partition (&lsei))
393 : : {
394 : 90915 : node = lsei_cgraph_node (lsei);
395 : 90915 : if (node->definition && node->has_gimple_body_p ()
396 : 180848 : && node->indirect_calls)
397 : 979 : count++;
398 : : }
399 : :
400 : 19145 : streamer_write_uhwi_stream (ob->main_stream, count);
401 : :
402 : : /* Process all of the functions. */
403 : 19145 : for (lsei = lsei_start_function_in_partition (encoder);
404 : 26988 : !lsei_end_p (lsei) && count; lsei_next_function_in_partition (&lsei))
405 : : {
406 : 7843 : cgraph_node *node = lsei_cgraph_node (lsei);
407 : 7843 : if (node->definition && node->has_gimple_body_p ()
408 : 15339 : && node->indirect_calls)
409 : : {
410 : 979 : int node_ref = lto_symtab_encoder_encode (encoder, node);
411 : 979 : streamer_write_uhwi_stream (ob->main_stream, node_ref);
412 : :
413 : 2740 : for (cgraph_edge *e = node->indirect_calls; e; e = e->next_callee)
414 : : {
415 : 1761 : speculative_call_summary *csum = call_sums->get_create (e);
416 : 1761 : ipa_profile_write_edge_summary (ob, csum);
417 : : }
418 : : }
419 : : }
420 : :
421 : 19145 : lto_destroy_simple_output_block (ob);
422 : : }
423 : :
424 : : /* Dump all profile summary data for all cgraph nodes and edges to file F. */
425 : :
426 : : static void
427 : 27 : ipa_profile_dump_all_summaries (FILE *f)
428 : : {
429 : 27 : fprintf (dump_file,
430 : : "\n========== IPA-profile speculative targets: ==========\n");
431 : 27 : cgraph_node *node;
432 : 98 : FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
433 : : {
434 : 71 : fprintf (f, "\nSummary for node %s:\n", node->dump_name ());
435 : 105 : for (cgraph_edge *e = node->indirect_calls; e; e = e->next_callee)
436 : : {
437 : 34 : fprintf (f, " Summary for %s of indirect edge %d:\n",
438 : 34 : e->caller->dump_name (), e->lto_stmt_uid);
439 : 34 : speculative_call_summary *csum = call_sums->get_create (e);
440 : 34 : csum->dump (f);
441 : : }
442 : : }
443 : 27 : fprintf (f, "\n\n");
444 : 27 : }
445 : :
446 : : /* Read speculative targets information about edge for LTO WPA. */
447 : :
448 : : static void
449 : 1352 : ipa_profile_read_edge_summary (class lto_input_block *ib, cgraph_edge *edge)
450 : : {
451 : 1352 : unsigned i, len;
452 : :
453 : 1352 : len = streamer_read_hwi (ib);
454 : 1352 : gcc_assert (len <= GCOV_TOPN_MAXIMUM_TRACKED_VALUES);
455 : 1352 : speculative_call_summary *csum = call_sums->get_create (edge);
456 : :
457 : 1362 : for (i = 0; i < len; i++)
458 : : {
459 : 10 : unsigned int target_id = streamer_read_hwi (ib);
460 : 10 : int target_probability = streamer_read_hwi (ib);
461 : 10 : speculative_call_target item (target_id, target_probability);
462 : 10 : csum->speculative_call_targets.safe_push (item);
463 : : }
464 : 1352 : }
465 : :
466 : : /* Read profile speculative targets section information for LTO WPA. */
467 : :
468 : : static void
469 : 10422 : ipa_profile_read_summary_section (struct lto_file_decl_data *file_data,
470 : : class lto_input_block *ib)
471 : : {
472 : 10422 : if (!ib)
473 : : return;
474 : :
475 : 10422 : lto_symtab_encoder_t encoder = file_data->symtab_node_encoder;
476 : :
477 : 10422 : unsigned int count = streamer_read_uhwi (ib);
478 : :
479 : 10422 : unsigned int i;
480 : 10422 : unsigned int index;
481 : 10422 : cgraph_node * node;
482 : :
483 : 11071 : for (i = 0; i < count; i++)
484 : : {
485 : 649 : index = streamer_read_uhwi (ib);
486 : 649 : node
487 : 649 : = dyn_cast<cgraph_node *> (lto_symtab_encoder_deref (encoder, index));
488 : :
489 : 2001 : for (cgraph_edge *e = node->indirect_calls; e; e = e->next_callee)
490 : 1352 : ipa_profile_read_edge_summary (ib, e);
491 : : }
492 : : }
493 : :
494 : : /* Deserialize the IPA histogram and speculative targets summary info for LTO.
495 : : */
496 : :
497 : : static void
498 : 12814 : ipa_profile_read_summary (void)
499 : : {
500 : 12814 : struct lto_file_decl_data ** file_data_vec
501 : 12814 : = lto_get_file_decl_data ();
502 : 12814 : struct lto_file_decl_data * file_data;
503 : 12814 : int j = 0;
504 : :
505 : 12814 : hash_table<histogram_hash> hashtable (10);
506 : :
507 : 12814 : gcc_checking_assert (!call_sums);
508 : 12814 : call_sums = new ipa_profile_call_summaries (symtab);
509 : :
510 : 26653 : while ((file_data = file_data_vec[j++]))
511 : : {
512 : 13839 : const char *data;
513 : 13839 : size_t len;
514 : 13839 : class lto_input_block *ib
515 : 13839 : = lto_create_simple_input_block (file_data,
516 : : LTO_section_ipa_profile,
517 : : &data, &len);
518 : 13839 : if (ib)
519 : : {
520 : 10422 : unsigned int num = streamer_read_uhwi (ib);
521 : 10422 : unsigned int n;
522 : 10652 : for (n = 0; n < num; n++)
523 : : {
524 : 230 : gcov_type count = streamer_read_gcov_count (ib);
525 : 230 : int time = streamer_read_uhwi (ib);
526 : 230 : int size = streamer_read_uhwi (ib);
527 : 230 : account_time_size (&hashtable, histogram,
528 : : count, time, size);
529 : : }
530 : :
531 : 10422 : ipa_profile_read_summary_section (file_data, ib);
532 : :
533 : 10422 : lto_destroy_simple_input_block (file_data,
534 : : LTO_section_ipa_profile,
535 : : ib, data, len);
536 : : }
537 : : }
538 : 12814 : histogram.qsort (cmp_counts);
539 : 12814 : }
540 : :
541 : : /* Data used by ipa_propagate_frequency. */
542 : :
543 : : struct ipa_propagate_frequency_data
544 : : {
545 : : cgraph_node *function_symbol;
546 : : bool maybe_unlikely_executed;
547 : : bool maybe_executed_once;
548 : : bool only_called_at_startup;
549 : : bool only_called_at_exit;
550 : : };
551 : :
552 : : /* Worker for ipa_propagate_frequency_1. */
553 : :
554 : : static bool
555 : 4617808 : ipa_propagate_frequency_1 (struct cgraph_node *node, void *data)
556 : : {
557 : 4617808 : struct ipa_propagate_frequency_data *d;
558 : 4617808 : struct cgraph_edge *edge;
559 : :
560 : 4617808 : d = (struct ipa_propagate_frequency_data *)data;
561 : 4617808 : for (edge = node->callers;
562 : 9339768 : edge && (d->maybe_unlikely_executed || d->maybe_executed_once
563 : 133732 : || d->only_called_at_startup || d->only_called_at_exit);
564 : 4721960 : edge = edge->next_caller)
565 : : {
566 : 4721960 : if (edge->caller != d->function_symbol)
567 : : {
568 : 4719818 : d->only_called_at_startup &= edge->caller->only_called_at_startup;
569 : : /* It makes sense to put main() together with the static constructors.
570 : : It will be executed for sure, but rest of functions called from
571 : : main are definitely not at startup only. */
572 : 4719818 : if (MAIN_NAME_P (DECL_NAME (edge->caller->decl)))
573 : 139969 : d->only_called_at_startup = 0;
574 : 4719818 : d->only_called_at_exit &= edge->caller->only_called_at_exit;
575 : : }
576 : :
577 : : /* When profile feedback is available, do not try to propagate too hard;
578 : : counts are already good guide on function frequencies and roundoff
579 : : errors can make us to push function into unlikely section even when
580 : : it is executed by the train run. Transfer the function only if all
581 : : callers are unlikely executed. */
582 : 4721960 : if (profile_info
583 : 4722458 : && !(edge->callee->count.ipa () == profile_count::zero ())
584 : 4722455 : && (edge->caller->frequency != NODE_FREQUENCY_UNLIKELY_EXECUTED
585 : 0 : || (edge->caller->inlined_to
586 : 0 : && edge->caller->inlined_to->frequency
587 : 0 : != NODE_FREQUENCY_UNLIKELY_EXECUTED)))
588 : 495 : d->maybe_unlikely_executed = false;
589 : 4721960 : if (edge->count.ipa ().initialized_p ()
590 : 4721960 : && !edge->count.ipa ().nonzero_p ())
591 : 37861 : continue;
592 : 4684099 : switch (edge->caller->frequency)
593 : : {
594 : : case NODE_FREQUENCY_UNLIKELY_EXECUTED:
595 : : break;
596 : 292277 : case NODE_FREQUENCY_EXECUTED_ONCE:
597 : 292277 : {
598 : 292277 : if (dump_file && (dump_flags & TDF_DETAILS))
599 : 89 : fprintf (dump_file, " Called by %s that is executed once\n",
600 : : edge->caller->dump_name ());
601 : 292277 : d->maybe_unlikely_executed = false;
602 : 292277 : ipa_call_summary *s = ipa_call_summaries->get (edge);
603 : 292277 : if (s != NULL && s->loop_depth)
604 : : {
605 : 7876 : d->maybe_executed_once = false;
606 : 7876 : if (dump_file && (dump_flags & TDF_DETAILS))
607 : 6 : fprintf (dump_file, " Called in loop\n");
608 : : }
609 : : break;
610 : : }
611 : 4389552 : case NODE_FREQUENCY_HOT:
612 : 4389552 : case NODE_FREQUENCY_NORMAL:
613 : 4389552 : if (dump_file && (dump_flags & TDF_DETAILS))
614 : 138 : fprintf (dump_file, " Called by %s that is normal or hot\n",
615 : : edge->caller->dump_name ());
616 : 4389552 : d->maybe_unlikely_executed = false;
617 : 4389552 : d->maybe_executed_once = false;
618 : 4389552 : break;
619 : : }
620 : : }
621 : 4617808 : return edge != NULL;
622 : : }
623 : :
624 : : /* Return ture if NODE contains hot calls. */
625 : :
626 : : bool
627 : 38660 : contains_hot_call_p (struct cgraph_node *node)
628 : : {
629 : 38660 : struct cgraph_edge *e;
630 : 94893 : for (e = node->callees; e; e = e->next_callee)
631 : 56235 : if (e->maybe_hot_p ())
632 : : return true;
633 : 56233 : else if (!e->inline_failed
634 : 56233 : && contains_hot_call_p (e->callee))
635 : : return true;
636 : 39029 : for (e = node->indirect_calls; e; e = e->next_callee)
637 : 371 : if (e->maybe_hot_p ())
638 : : return true;
639 : : return false;
640 : : }
641 : :
642 : : /* See if the frequency of NODE can be updated based on frequencies of its
643 : : callers. */
644 : : bool
645 : 8063288 : ipa_propagate_frequency (struct cgraph_node *node)
646 : : {
647 : 8063288 : struct ipa_propagate_frequency_data d = {node, true, true, true, true};
648 : 8063288 : bool changed = false;
649 : :
650 : : /* We cannot propagate anything useful about externally visible functions
651 : : nor about virtuals. */
652 : 8063288 : if (!node->local
653 : 4662588 : || node->alias
654 : 12714770 : || (opt_for_fn (node->decl, flag_devirtualize)
655 : 4571370 : && DECL_VIRTUAL_P (node->decl)))
656 : : return false;
657 : 4609048 : gcc_assert (node->analyzed);
658 : 4609048 : if (dump_file && (dump_flags & TDF_DETAILS))
659 : 226 : fprintf (dump_file, "Processing frequency %s\n", node->dump_name ());
660 : :
661 : 4609048 : node->call_for_symbol_and_aliases (ipa_propagate_frequency_1, &d,
662 : : true);
663 : :
664 : 4609048 : if ((d.only_called_at_startup && !d.only_called_at_exit)
665 : 6198 : && !node->only_called_at_startup)
666 : : {
667 : 1918 : node->only_called_at_startup = true;
668 : 1918 : if (dump_file)
669 : 0 : fprintf (dump_file, "Node %s promoted to only called at startup.\n",
670 : : node->dump_name ());
671 : : changed = true;
672 : : }
673 : 4609048 : if ((d.only_called_at_exit && !d.only_called_at_startup)
674 : 49 : && !node->only_called_at_exit)
675 : : {
676 : 19 : node->only_called_at_exit = true;
677 : 19 : if (dump_file)
678 : 0 : fprintf (dump_file, "Node %s promoted to only called at exit.\n",
679 : : node->dump_name ());
680 : : changed = true;
681 : : }
682 : :
683 : : /* With profile we can decide on hot/normal based on count. */
684 : 4609048 : if (node->count. ipa().initialized_p ())
685 : : {
686 : 28653 : bool hot = false;
687 : 28653 : if (!(node->count. ipa() == profile_count::zero ())
688 : 172 : && node->count. ipa() >= get_hot_bb_threshold ())
689 : 167 : hot = true;
690 : 28653 : if (!hot)
691 : 28486 : hot |= contains_hot_call_p (node);
692 : 28653 : if (hot)
693 : : {
694 : 169 : if (node->frequency != NODE_FREQUENCY_HOT)
695 : : {
696 : 12 : if (dump_file)
697 : 0 : fprintf (dump_file, "Node %s promoted to hot.\n",
698 : : node->dump_name ());
699 : 12 : node->frequency = NODE_FREQUENCY_HOT;
700 : 12 : return true;
701 : : }
702 : : return false;
703 : : }
704 : 28484 : else if (node->frequency == NODE_FREQUENCY_HOT)
705 : : {
706 : 4 : if (dump_file)
707 : 0 : fprintf (dump_file, "Node %s reduced to normal.\n",
708 : : node->dump_name ());
709 : 4 : node->frequency = NODE_FREQUENCY_NORMAL;
710 : 4 : changed = true;
711 : : }
712 : : }
713 : : /* These come either from profile or user hints; never update them. */
714 : 4608879 : if (node->frequency == NODE_FREQUENCY_HOT
715 : 4608873 : || node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
716 : : return changed;
717 : 4582612 : if (d.maybe_unlikely_executed)
718 : : {
719 : 9365 : node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
720 : 9365 : if (dump_file)
721 : 0 : fprintf (dump_file, "Node %s promoted to unlikely executed.\n",
722 : : node->dump_name ());
723 : : changed = true;
724 : : }
725 : 4573247 : else if (d.maybe_executed_once && node->frequency != NODE_FREQUENCY_EXECUTED_ONCE)
726 : : {
727 : 81690 : node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
728 : 81690 : if (dump_file)
729 : 45 : fprintf (dump_file, "Node %s promoted to executed once.\n",
730 : : node->dump_name ());
731 : : changed = true;
732 : : }
733 : : return changed;
734 : : }
735 : :
736 : : /* Check that number of arguments of N agrees with E.
737 : : Be conservative when summaries are not present. */
738 : :
739 : : static bool
740 : 42 : check_argument_count (struct cgraph_node *n, struct cgraph_edge *e)
741 : : {
742 : 42 : if (!ipa_node_params_sum || !ipa_edge_args_sum)
743 : : return true;
744 : 42 : ipa_node_params *info = ipa_node_params_sum->get (n->function_symbol ());
745 : 42 : if (!info)
746 : : return true;
747 : 42 : ipa_edge_args *e_info = ipa_edge_args_sum->get (e);
748 : 42 : if (!e_info)
749 : : return true;
750 : 66 : if (ipa_get_param_count (info) != ipa_get_cs_argument_count (e_info)
751 : 42 : && (ipa_get_param_count (info) >= ipa_get_cs_argument_count (e_info)
752 : 0 : || !stdarg_p (TREE_TYPE (n->decl))))
753 : 0 : return false;
754 : : return true;
755 : : }
756 : :
757 : : /* Simple ipa profile pass propagating frequencies across the callgraph. */
758 : :
759 : : static unsigned int
760 : 148877 : ipa_profile (void)
761 : : {
762 : 148877 : struct cgraph_node **order;
763 : 148877 : struct cgraph_edge *e;
764 : 148877 : int order_pos;
765 : 148877 : bool something_changed = false;
766 : 148877 : int i;
767 : 148877 : gcov_type overall_time = 0, cutoff = 0, cumulated = 0, overall_size = 0;
768 : 148877 : struct cgraph_node *n,*n2;
769 : 148877 : int nindirect = 0, ncommon = 0, nunknown = 0, nuseless = 0, nconverted = 0;
770 : 148877 : int nmismatch = 0, nimpossible = 0;
771 : 148877 : bool node_map_initialized = false;
772 : 148877 : gcov_type threshold;
773 : :
774 : 148877 : if (dump_file)
775 : 27 : dump_histogram (dump_file, histogram);
776 : 159195 : for (i = 0; i < (int)histogram.length (); i++)
777 : : {
778 : 3575 : overall_time += histogram[i]->count * histogram[i]->time;
779 : 3575 : overall_size += histogram[i]->size;
780 : : }
781 : 148877 : threshold = 0;
782 : 148877 : if (overall_time)
783 : : {
784 : 99 : gcc_assert (overall_size);
785 : :
786 : 99 : cutoff = (overall_time * param_hot_bb_count_ws_permille + 500) / 1000;
787 : 444 : for (i = 0; cumulated < cutoff; i++)
788 : : {
789 : 345 : cumulated += histogram[i]->count * histogram[i]->time;
790 : 345 : threshold = histogram[i]->count;
791 : : }
792 : 99 : if (!threshold)
793 : 0 : threshold = 1;
794 : 99 : if (dump_file)
795 : : {
796 : : gcov_type cumulated_time = 0, cumulated_size = 0;
797 : :
798 : 15 : for (i = 0;
799 : 19 : i < (int)histogram.length () && histogram[i]->count >= threshold;
800 : : i++)
801 : : {
802 : 15 : cumulated_time += histogram[i]->count * histogram[i]->time;
803 : 15 : cumulated_size += histogram[i]->size;
804 : : }
805 : 4 : fprintf (dump_file, "Determined min count: %" PRId64
806 : : " Time:%3.2f%% Size:%3.2f%%\n",
807 : : (int64_t)threshold,
808 : 4 : cumulated_time * 100.0 / overall_time,
809 : 4 : cumulated_size * 100.0 / overall_size);
810 : : }
811 : :
812 : 99 : if (in_lto_p)
813 : : {
814 : 4 : if (dump_file)
815 : 2 : fprintf (dump_file, "Setting hotness threshold in LTO mode.\n");
816 : 4 : set_hot_bb_threshold (threshold);
817 : : }
818 : : }
819 : 148877 : histogram.release ();
820 : 148877 : histogram_pool.release ();
821 : :
822 : : /* Produce speculative calls: we saved common target from profiling into
823 : : e->target_id. Now, at link time, we can look up corresponding
824 : : function node and produce speculative call. */
825 : :
826 : 148877 : gcc_checking_assert (call_sums);
827 : :
828 : 148877 : if (dump_file)
829 : : {
830 : 27 : if (!node_map_initialized)
831 : 27 : init_node_map (false);
832 : 27 : node_map_initialized = true;
833 : :
834 : 27 : ipa_profile_dump_all_summaries (dump_file);
835 : : }
836 : :
837 : 1536080 : FOR_EACH_DEFINED_FUNCTION (n)
838 : : {
839 : 1387203 : bool update = false;
840 : :
841 : 1387203 : if (!opt_for_fn (n->decl, flag_ipa_profile))
842 : 10746 : continue;
843 : :
844 : 1514419 : for (e = n->indirect_calls; e; e = e->next_callee)
845 : : {
846 : 137962 : if (n->count.initialized_p ())
847 : 137958 : nindirect++;
848 : :
849 : 137962 : speculative_call_summary *csum = call_sums->get_create (e);
850 : 138001 : unsigned spec_count = csum->speculative_call_targets.length ();
851 : 39 : if (spec_count)
852 : : {
853 : 39 : if (!node_map_initialized)
854 : 19 : init_node_map (false);
855 : 39 : node_map_initialized = true;
856 : 39 : ncommon++;
857 : :
858 : 39 : unsigned speculative_id = 0;
859 : 39 : profile_count orig = e->count;
860 : 90 : for (unsigned i = 0; i < spec_count; i++)
861 : : {
862 : 51 : speculative_call_target item
863 : 51 : = csum->speculative_call_targets[i];
864 : 51 : n2 = find_func_by_profile_id (item.target_id);
865 : 51 : if (n2)
866 : : {
867 : 50 : if (dump_file)
868 : : {
869 : 8 : fprintf (dump_file,
870 : : "Indirect call -> direct call from"
871 : : " other module %s => %s, prob %3.2f\n",
872 : : n->dump_name (),
873 : : n2->dump_name (),
874 : : item.target_probability
875 : 8 : / (float) REG_BR_PROB_BASE);
876 : : }
877 : 50 : if (item.target_probability < REG_BR_PROB_BASE / 2)
878 : : {
879 : 8 : nuseless++;
880 : 8 : if (dump_file)
881 : 1 : fprintf (dump_file,
882 : : "Not speculating: "
883 : : "probability is too low.\n");
884 : : }
885 : 42 : else if (n2->get_availability () <= AVAIL_INTERPOSABLE
886 : 42 : && n2->can_be_discarded_p ())
887 : : {
888 : 0 : nuseless++;
889 : 0 : if (dump_file)
890 : 0 : fprintf (dump_file,
891 : : "Not speculating: target is overwritable "
892 : : "and can be discarded.\n");
893 : : }
894 : 42 : else if (!check_argument_count (n2, e))
895 : : {
896 : 0 : nmismatch++;
897 : 0 : if (dump_file)
898 : 0 : fprintf (dump_file,
899 : : "Not speculating: "
900 : : "parameter count mismatch\n");
901 : : }
902 : 42 : else if (e->indirect_info->polymorphic
903 : 10 : && !opt_for_fn (n->decl, flag_devirtualize)
904 : 46 : && !possible_polymorphic_call_target_p (e, n2))
905 : : {
906 : 0 : nimpossible++;
907 : 0 : if (dump_file)
908 : 0 : fprintf (dump_file,
909 : : "Not speculating: "
910 : : "function is not in the polymorphic "
911 : : "call target list\n");
912 : : }
913 : : else
914 : : {
915 : : /* Target may be overwritable, but profile says that
916 : : control flow goes to this particular implementation
917 : : of N2. Speculate on the local alias to allow
918 : : inlining. */
919 : 42 : if (!n2->can_be_discarded_p ())
920 : : {
921 : 36 : cgraph_node *alias;
922 : 36 : alias = dyn_cast<cgraph_node *>
923 : 36 : (n2->noninterposable_alias ());
924 : : if (alias)
925 : 42 : n2 = alias;
926 : : }
927 : 42 : nconverted++;
928 : 42 : profile_probability prob
929 : : = profile_probability::from_reg_br_prob_base
930 : 42 : (item.target_probability).adjusted ();
931 : 42 : e->make_speculative (n2,
932 : : orig.apply_probability (prob),
933 : : speculative_id);
934 : 42 : update = true;
935 : 42 : speculative_id++;
936 : : }
937 : : }
938 : : else
939 : : {
940 : 1 : if (dump_file)
941 : 0 : fprintf (dump_file,
942 : : "Function with profile-id %i not found.\n",
943 : : item.target_id);
944 : 1 : nunknown++;
945 : : }
946 : : }
947 : : }
948 : : }
949 : 1376457 : if (update)
950 : 36 : ipa_update_overall_fn_summary (n);
951 : : }
952 : 148877 : if (node_map_initialized)
953 : 46 : del_node_map ();
954 : 148877 : if (dump_file && nindirect)
955 : 25 : fprintf (dump_file,
956 : : "%i indirect calls trained.\n"
957 : : "%i (%3.2f%%) have common target.\n"
958 : : "%i (%3.2f%%) targets was not found.\n"
959 : : "%i (%3.2f%%) targets had parameter count mismatch.\n"
960 : : "%i (%3.2f%%) targets was not in polymorphic call target list.\n"
961 : : "%i (%3.2f%%) speculations seems useless.\n"
962 : : "%i (%3.2f%%) speculations produced.\n",
963 : : nindirect,
964 : 25 : ncommon, ncommon * 100.0 / nindirect,
965 : 25 : nunknown, nunknown * 100.0 / nindirect,
966 : 25 : nmismatch, nmismatch * 100.0 / nindirect,
967 : 25 : nimpossible, nimpossible * 100.0 / nindirect,
968 : 25 : nuseless, nuseless * 100.0 / nindirect,
969 : 25 : nconverted, nconverted * 100.0 / nindirect);
970 : :
971 : 148877 : order = XCNEWVEC (struct cgraph_node *, symtab->cgraph_count);
972 : 148877 : order_pos = ipa_reverse_postorder (order);
973 : 2803335 : for (i = order_pos - 1; i >= 0; i--)
974 : : {
975 : 2654458 : if (order[i]->local
976 : 163103 : && opt_for_fn (order[i]->decl, flag_ipa_profile)
977 : 2812053 : && ipa_propagate_frequency (order[i]))
978 : : {
979 : 325569 : for (e = order[i]->callees; e; e = e->next_callee)
980 : 296842 : if (e->callee->local && !e->callee->aux)
981 : : {
982 : 10198 : something_changed = true;
983 : 10198 : e->callee->aux = (void *)1;
984 : : }
985 : : }
986 : 2654458 : order[i]->aux = NULL;
987 : : }
988 : :
989 : 157562 : while (something_changed)
990 : : {
991 : : something_changed = false;
992 : 117324 : for (i = order_pos - 1; i >= 0; i--)
993 : : {
994 : 108639 : if (order[i]->aux
995 : 16111 : && opt_for_fn (order[i]->decl, flag_ipa_profile)
996 : 124750 : && ipa_propagate_frequency (order[i]))
997 : : {
998 : 96591 : for (e = order[i]->callees; e; e = e->next_callee)
999 : 82064 : if (e->callee->local && !e->callee->aux)
1000 : : {
1001 : 5917 : something_changed = true;
1002 : 5917 : e->callee->aux = (void *)1;
1003 : : }
1004 : : }
1005 : 108639 : order[i]->aux = NULL;
1006 : : }
1007 : : }
1008 : 148877 : free (order);
1009 : :
1010 : 148877 : if (dump_file && (dump_flags & TDF_DETAILS))
1011 : 0 : symtab->dump (dump_file);
1012 : :
1013 : 148877 : delete call_sums;
1014 : 148877 : call_sums = NULL;
1015 : :
1016 : 148877 : return 0;
1017 : : }
1018 : :
1019 : : namespace {
1020 : :
1021 : : const pass_data pass_data_ipa_profile =
1022 : : {
1023 : : IPA_PASS, /* type */
1024 : : "profile_estimate", /* name */
1025 : : OPTGROUP_NONE, /* optinfo_flags */
1026 : : TV_IPA_PROFILE, /* tv_id */
1027 : : 0, /* properties_required */
1028 : : 0, /* properties_provided */
1029 : : 0, /* properties_destroyed */
1030 : : 0, /* todo_flags_start */
1031 : : 0, /* todo_flags_finish */
1032 : : };
1033 : :
1034 : : class pass_ipa_profile : public ipa_opt_pass_d
1035 : : {
1036 : : public:
1037 : 283157 : pass_ipa_profile (gcc::context *ctxt)
1038 : : : ipa_opt_pass_d (pass_data_ipa_profile, ctxt,
1039 : : ipa_profile_generate_summary, /* generate_summary */
1040 : : ipa_profile_write_summary, /* write_summary */
1041 : : ipa_profile_read_summary, /* read_summary */
1042 : : NULL, /* write_optimization_summary */
1043 : : NULL, /* read_optimization_summary */
1044 : : NULL, /* stmt_fixup */
1045 : : 0, /* function_transform_todo_flags_start */
1046 : : NULL, /* function_transform */
1047 : 283157 : NULL) /* variable_transform */
1048 : 283157 : {}
1049 : :
1050 : : /* opt_pass methods: */
1051 : 582577 : bool gate (function *) final override { return flag_ipa_profile || in_lto_p; }
1052 : 148877 : unsigned int execute (function *) final override { return ipa_profile (); }
1053 : :
1054 : : }; // class pass_ipa_profile
1055 : :
1056 : : } // anon namespace
1057 : :
1058 : : ipa_opt_pass_d *
1059 : 283157 : make_pass_ipa_profile (gcc::context *ctxt)
1060 : : {
1061 : 283157 : return new pass_ipa_profile (ctxt);
1062 : : }
1063 : :
1064 : : /* Reset all state within ipa-profile.cc so that we can rerun the compiler
1065 : : within the same process. For use by toplev::finalize. */
1066 : :
1067 : : void
1068 : 254814 : ipa_profile_cc_finalize (void)
1069 : : {
1070 : 254814 : delete call_sums;
1071 : 254814 : call_sums = NULL;
1072 : 254814 : }
|
