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 : 35497 : histogram_hash::hash (const histogram_entry *val)
90 : : {
91 : 35497 : return val->count;
92 : : }
93 : :
94 : : inline int
95 : 18373 : histogram_hash::equal (const histogram_entry *val, const histogram_entry *val2)
96 : : {
97 : 18373 : 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 : 17264 : account_time_size (hash_table<histogram_hash> *hashtable,
105 : : vec<histogram_entry *> &histogram,
106 : : gcov_type count, int time, int size)
107 : : {
108 : 17264 : histogram_entry key = {count, 0, 0};
109 : 17264 : histogram_entry **val = hashtable->find_slot (&key, INSERT);
110 : :
111 : 17264 : if (!*val)
112 : : {
113 : 3487 : *val = histogram_pool.allocate ();
114 : 3487 : **val = key;
115 : 3487 : histogram.safe_push (*val);
116 : : }
117 : 17264 : (*val)->time += time;
118 : 17264 : (*val)->size += size;
119 : 17264 : }
120 : :
121 : : int
122 : 4660 : cmp_counts (const void *v1, const void *v2)
123 : : {
124 : 4660 : const histogram_entry *h1 = *(const histogram_entry * const *)v1;
125 : 4660 : const histogram_entry *h2 = *(const histogram_entry * const *)v2;
126 : 4660 : if (h1->count < h2->count)
127 : : return 1;
128 : 2699 : if (h1->count > h2->count)
129 : 2699 : 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 : 142954 : class speculative_call_summary
181 : : {
182 : : public:
183 : 142954 : 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 : 160731 : ipa_profile_call_summaries (symbol_table *table)
199 : 321462 : : 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 : 147472 : ipa_profile_generate_summary (void)
261 : : {
262 : 147472 : struct cgraph_node *node;
263 : 147472 : gimple_stmt_iterator gsi;
264 : 147472 : basic_block bb;
265 : :
266 : 147472 : hash_table<histogram_hash> hashtable (10);
267 : :
268 : 147472 : gcc_checking_assert (!call_sums);
269 : 147472 : call_sums = new ipa_profile_call_summaries (symtab);
270 : :
271 : 1488587 : FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
272 : 1341115 : if (ENTRY_BLOCK_PTR_FOR_FN
273 : 2682230 : (DECL_STRUCT_FUNCTION (node->decl))->count.ipa_p ())
274 : 27530 : FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
275 : : {
276 : 21251 : int time = 0;
277 : 21251 : int size = 0;
278 : 128882 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
279 : : {
280 : 86380 : gimple *stmt = gsi_stmt (gsi);
281 : 86380 : if (gimple_code (stmt) == GIMPLE_CALL
282 : 86380 : && !gimple_call_fndecl (stmt))
283 : : {
284 : 181 : histogram_value h;
285 : 181 : h = gimple_histogram_value_of_type
286 : 181 : (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 : 181 : 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 : : val,
320 : 51 : profile_count::from_gcov_type (count)
321 : : .probability_in
322 : 51 : (profile_count::from_gcov_type (all))
323 : 51 : .to_reg_br_prob_base ());
324 : 51 : csum->speculative_call_targets.safe_push (item);
325 : : }
326 : :
327 : 40 : gimple_remove_histogram_value
328 : 40 : (DECL_STRUCT_FUNCTION (node->decl), stmt, h);
329 : : }
330 : : }
331 : 86380 : time += estimate_num_insns (stmt, &eni_time_weights);
332 : 86380 : size += estimate_num_insns (stmt, &eni_size_weights);
333 : : }
334 : 55307 : if (bb->count.ipa_p () && bb->count.initialized_p ())
335 : 17028 : account_time_size (&hashtable, histogram,
336 : 34056 : bb->count.ipa ().to_gcov_type (),
337 : : time, size);
338 : : }
339 : 147472 : histogram.qsort (cmp_counts);
340 : 147472 : }
341 : :
342 : : /* Serialize the speculative summary info for LTO. */
343 : :
344 : : static void
345 : 1821 : ipa_profile_write_edge_summary (lto_simple_output_block *ob,
346 : : speculative_call_summary *csum)
347 : : {
348 : 1821 : unsigned len = 0;
349 : :
350 : 1821 : len = csum->speculative_call_targets.length ();
351 : :
352 : 4 : gcc_assert (len <= GCOV_TOPN_MAXIMUM_TRACKED_VALUES);
353 : :
354 : 1821 : streamer_write_hwi_stream (ob->main_stream, len);
355 : :
356 : 1821 : if (len)
357 : : {
358 : 4 : unsigned spec_count = csum->speculative_call_targets.length ();
359 : 14 : for (unsigned i = 0; i < spec_count; i++)
360 : : {
361 : 10 : speculative_call_target item = csum->speculative_call_targets[i];
362 : 10 : gcc_assert (item.target_id);
363 : 10 : streamer_write_hwi_stream (ob->main_stream, item.target_id);
364 : 10 : streamer_write_hwi_stream (ob->main_stream, item.target_probability);
365 : : }
366 : : }
367 : 1821 : }
368 : :
369 : : /* Serialize the ipa info for lto. */
370 : :
371 : : static void
372 : 19556 : ipa_profile_write_summary (void)
373 : : {
374 : 19556 : struct lto_simple_output_block *ob
375 : 19556 : = lto_create_simple_output_block (LTO_section_ipa_profile);
376 : 19556 : unsigned int i;
377 : :
378 : 19556 : streamer_write_uhwi_stream (ob->main_stream, histogram.length ());
379 : 39441 : for (i = 0; i < histogram.length (); i++)
380 : : {
381 : 329 : streamer_write_gcov_count_stream (ob->main_stream, histogram[i]->count);
382 : 329 : streamer_write_uhwi_stream (ob->main_stream, histogram[i]->time);
383 : 329 : streamer_write_uhwi_stream (ob->main_stream, histogram[i]->size);
384 : : }
385 : :
386 : 19556 : if (!call_sums)
387 : 0 : return;
388 : :
389 : : /* Serialize speculative targets information. */
390 : 19556 : unsigned int count = 0;
391 : 19556 : lto_symtab_encoder_t encoder = ob->decl_state->symtab_node_encoder;
392 : 19556 : lto_symtab_encoder_iterator lsei;
393 : 19556 : cgraph_node *node;
394 : :
395 : 112159 : for (lsei = lsei_start_function_in_partition (encoder); !lsei_end_p (lsei);
396 : 92603 : lsei_next_function_in_partition (&lsei))
397 : : {
398 : 92603 : node = lsei_cgraph_node (lsei);
399 : 92603 : if (node->definition && node->has_gimple_body_p ()
400 : 184231 : && node->indirect_calls)
401 : 1011 : count++;
402 : : }
403 : :
404 : 19556 : streamer_write_uhwi_stream (ob->main_stream, count);
405 : :
406 : : /* Process all of the functions. */
407 : 19556 : for (lsei = lsei_start_function_in_partition (encoder);
408 : 27530 : !lsei_end_p (lsei) && count; lsei_next_function_in_partition (&lsei))
409 : : {
410 : 7974 : cgraph_node *node = lsei_cgraph_node (lsei);
411 : 7974 : if (node->definition && node->has_gimple_body_p ()
412 : 15597 : && node->indirect_calls)
413 : : {
414 : 1011 : int node_ref = lto_symtab_encoder_encode (encoder, node);
415 : 1011 : streamer_write_uhwi_stream (ob->main_stream, node_ref);
416 : :
417 : 2832 : for (cgraph_edge *e = node->indirect_calls; e; e = e->next_callee)
418 : : {
419 : 1821 : speculative_call_summary *csum = call_sums->get_create (e);
420 : 1821 : ipa_profile_write_edge_summary (ob, csum);
421 : : }
422 : : }
423 : : }
424 : :
425 : 19556 : lto_destroy_simple_output_block (ob);
426 : : }
427 : :
428 : : /* Dump all profile summary data for all cgraph nodes and edges to file F. */
429 : :
430 : : static void
431 : 27 : ipa_profile_dump_all_summaries (FILE *f)
432 : : {
433 : 27 : fprintf (dump_file,
434 : : "\n========== IPA-profile speculative targets: ==========\n");
435 : 27 : cgraph_node *node;
436 : 98 : FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
437 : : {
438 : 71 : fprintf (f, "\nSummary for node %s:\n", node->dump_name ());
439 : 105 : for (cgraph_edge *e = node->indirect_calls; e; e = e->next_callee)
440 : : {
441 : 34 : fprintf (f, " Summary for %s of indirect edge %d:\n",
442 : 34 : e->caller->dump_name (), e->lto_stmt_uid);
443 : 34 : speculative_call_summary *csum = call_sums->get_create (e);
444 : 34 : csum->dump (f);
445 : : }
446 : : }
447 : 27 : fprintf (f, "\n\n");
448 : 27 : }
449 : :
450 : : /* Read speculative targets information about edge for LTO WPA. */
451 : :
452 : : static void
453 : 1401 : ipa_profile_read_edge_summary (class lto_input_block *ib, cgraph_edge *edge)
454 : : {
455 : 1401 : unsigned i, len;
456 : :
457 : 1401 : len = streamer_read_hwi (ib);
458 : 1401 : gcc_assert (len <= GCOV_TOPN_MAXIMUM_TRACKED_VALUES);
459 : 1401 : speculative_call_summary *csum = call_sums->get_create (edge);
460 : :
461 : 1411 : for (i = 0; i < len; i++)
462 : : {
463 : 10 : unsigned int target_id = streamer_read_hwi (ib);
464 : 10 : int target_probability = streamer_read_hwi (ib);
465 : 10 : speculative_call_target item (target_id, target_probability);
466 : 10 : csum->speculative_call_targets.safe_push (item);
467 : : }
468 : 1401 : }
469 : :
470 : : /* Read profile speculative targets section information for LTO WPA. */
471 : :
472 : : static void
473 : 10695 : ipa_profile_read_summary_section (struct lto_file_decl_data *file_data,
474 : : class lto_input_block *ib)
475 : : {
476 : 10695 : if (!ib)
477 : : return;
478 : :
479 : 10695 : lto_symtab_encoder_t encoder = file_data->symtab_node_encoder;
480 : :
481 : 10695 : unsigned int count = streamer_read_uhwi (ib);
482 : :
483 : 10695 : unsigned int i;
484 : 10695 : unsigned int index;
485 : 10695 : cgraph_node * node;
486 : :
487 : 11369 : for (i = 0; i < count; i++)
488 : : {
489 : 674 : index = streamer_read_uhwi (ib);
490 : 674 : node
491 : 674 : = dyn_cast<cgraph_node *> (lto_symtab_encoder_deref (encoder, index));
492 : :
493 : 2075 : for (cgraph_edge *e = node->indirect_calls; e; e = e->next_callee)
494 : 1401 : ipa_profile_read_edge_summary (ib, e);
495 : : }
496 : : }
497 : :
498 : : /* Deserialize the IPA histogram and speculative targets summary info for LTO.
499 : : */
500 : :
501 : : static void
502 : 13259 : ipa_profile_read_summary (void)
503 : : {
504 : 13259 : struct lto_file_decl_data ** file_data_vec
505 : 13259 : = lto_get_file_decl_data ();
506 : 13259 : struct lto_file_decl_data * file_data;
507 : 13259 : int j = 0;
508 : :
509 : 13259 : hash_table<histogram_hash> hashtable (10);
510 : :
511 : 13259 : gcc_checking_assert (!call_sums);
512 : 13259 : call_sums = new ipa_profile_call_summaries (symtab);
513 : :
514 : 27556 : while ((file_data = file_data_vec[j++]))
515 : : {
516 : 14297 : const char *data;
517 : 14297 : size_t len;
518 : 14297 : class lto_input_block *ib
519 : 14297 : = lto_create_simple_input_block (file_data,
520 : : LTO_section_ipa_profile,
521 : : &data, &len);
522 : 14297 : if (ib)
523 : : {
524 : 10695 : unsigned int num = streamer_read_uhwi (ib);
525 : 10695 : unsigned int n;
526 : 10931 : for (n = 0; n < num; n++)
527 : : {
528 : 236 : gcov_type count = streamer_read_gcov_count (ib);
529 : 236 : int time = streamer_read_uhwi (ib);
530 : 236 : int size = streamer_read_uhwi (ib);
531 : 236 : account_time_size (&hashtable, histogram,
532 : : count, time, size);
533 : : }
534 : :
535 : 10695 : ipa_profile_read_summary_section (file_data, ib);
536 : :
537 : 10695 : lto_destroy_simple_input_block (file_data,
538 : : LTO_section_ipa_profile,
539 : : ib, data, len);
540 : : }
541 : : }
542 : 13259 : histogram.qsort (cmp_counts);
543 : 13259 : }
544 : :
545 : : /* Data used by ipa_propagate_frequency. */
546 : :
547 : : struct ipa_propagate_frequency_data
548 : : {
549 : : cgraph_node *function_symbol;
550 : : bool maybe_unlikely_executed;
551 : : bool maybe_executed_once;
552 : : bool only_called_at_startup;
553 : : bool only_called_at_exit;
554 : : };
555 : :
556 : : /* Worker for ipa_propagate_frequency_1. */
557 : :
558 : : static bool
559 : 5255639 : ipa_propagate_frequency_1 (struct cgraph_node *node, void *data)
560 : : {
561 : 5255639 : struct ipa_propagate_frequency_data *d;
562 : 5255639 : struct cgraph_edge *edge;
563 : :
564 : 5255639 : d = (struct ipa_propagate_frequency_data *)data;
565 : 5255639 : for (edge = node->callers;
566 : 10614290 : edge && (d->maybe_unlikely_executed || d->maybe_executed_once
567 : 144520 : || d->only_called_at_startup || d->only_called_at_exit);
568 : 5358651 : edge = edge->next_caller)
569 : : {
570 : 5358651 : if (edge->caller != d->function_symbol)
571 : : {
572 : 5355857 : d->only_called_at_startup &= edge->caller->only_called_at_startup;
573 : : /* It makes sense to put main() together with the static constructors.
574 : : It will be executed for sure, but rest of functions called from
575 : : main are definitely not at startup only. */
576 : 5355857 : if (MAIN_NAME_P (DECL_NAME (edge->caller->decl)))
577 : 155029 : d->only_called_at_startup = 0;
578 : 5355857 : d->only_called_at_exit &= edge->caller->only_called_at_exit;
579 : : }
580 : :
581 : : /* When profile feedback is available, do not try to propagate too hard;
582 : : counts are already good guide on function frequencies and roundoff
583 : : errors can make us to push function into unlikely section even when
584 : : it is executed by the train run. Transfer the function only if all
585 : : callers are unlikely executed. */
586 : 5358651 : if (profile_info
587 : 5359184 : && !(edge->callee->count.ipa () == profile_count::zero ())
588 : 5359181 : && (edge->caller->frequency != NODE_FREQUENCY_UNLIKELY_EXECUTED
589 : 0 : || (edge->caller->inlined_to
590 : 0 : && edge->caller->inlined_to->frequency
591 : 0 : != NODE_FREQUENCY_UNLIKELY_EXECUTED)))
592 : 530 : d->maybe_unlikely_executed = false;
593 : 5358651 : if (edge->count.ipa ().initialized_p ()
594 : 5358651 : && !edge->count.ipa ().nonzero_p ())
595 : 40707 : continue;
596 : 5317944 : switch (edge->caller->frequency)
597 : : {
598 : : case NODE_FREQUENCY_UNLIKELY_EXECUTED:
599 : : break;
600 : 359444 : case NODE_FREQUENCY_EXECUTED_ONCE:
601 : 359444 : {
602 : 359444 : if (dump_file && (dump_flags & TDF_DETAILS))
603 : 90 : fprintf (dump_file, " Called by %s that is executed once\n",
604 : : edge->caller->dump_name ());
605 : 359444 : d->maybe_unlikely_executed = false;
606 : 359444 : ipa_call_summary *s = ipa_call_summaries->get (edge);
607 : 359444 : if (s != NULL && s->loop_depth)
608 : : {
609 : 8513 : d->maybe_executed_once = false;
610 : 8513 : if (dump_file && (dump_flags & TDF_DETAILS))
611 : 6 : fprintf (dump_file, " Called in loop\n");
612 : : }
613 : : break;
614 : : }
615 : 4955958 : case NODE_FREQUENCY_HOT:
616 : 4955958 : case NODE_FREQUENCY_NORMAL:
617 : 4955958 : if (dump_file && (dump_flags & TDF_DETAILS))
618 : 135 : fprintf (dump_file, " Called by %s that is normal or hot\n",
619 : : edge->caller->dump_name ());
620 : 4955958 : d->maybe_unlikely_executed = false;
621 : 4955958 : d->maybe_executed_once = false;
622 : 4955958 : break;
623 : : }
624 : : }
625 : 5255639 : return edge != NULL;
626 : : }
627 : :
628 : : /* Return true if NODE contains hot calls. */
629 : :
630 : : bool
631 : 41655 : contains_hot_call_p (struct cgraph_node *node)
632 : : {
633 : 41655 : struct cgraph_edge *e;
634 : 103190 : for (e = node->callees; e; e = e->next_callee)
635 : 61537 : if (e->maybe_hot_p ())
636 : : return true;
637 : 61535 : else if (!e->inline_failed
638 : 61535 : && contains_hot_call_p (e->callee))
639 : : return true;
640 : 42039 : for (e = node->indirect_calls; e; e = e->next_callee)
641 : 386 : if (e->maybe_hot_p ())
642 : : return true;
643 : : return false;
644 : : }
645 : :
646 : : /* See if the frequency of NODE can be updated based on frequencies of its
647 : : callers. */
648 : : bool
649 : 9100130 : ipa_propagate_frequency (struct cgraph_node *node)
650 : : {
651 : 9100130 : struct ipa_propagate_frequency_data d = {node, true, true, true, true};
652 : 9100130 : bool changed = false;
653 : :
654 : : /* We cannot propagate anything useful about externally visible functions
655 : : nor about virtuals. */
656 : 9100130 : if (!node->local
657 : 5346833 : || node->alias
658 : 14434937 : || (opt_for_fn (node->decl, flag_devirtualize)
659 : 5251201 : && DECL_VIRTUAL_P (node->decl)))
660 : : return false;
661 : 5246356 : gcc_assert (node->analyzed);
662 : 5246356 : if (dump_file && (dump_flags & TDF_DETAILS))
663 : 225 : fprintf (dump_file, "Processing frequency %s\n", node->dump_name ());
664 : :
665 : 5246356 : node->call_for_symbol_and_aliases (ipa_propagate_frequency_1, &d,
666 : : true);
667 : :
668 : 5246356 : if ((d.only_called_at_startup && !d.only_called_at_exit)
669 : 42718 : && !node->only_called_at_startup)
670 : : {
671 : 13914 : node->only_called_at_startup = true;
672 : 13914 : if (dump_file)
673 : 0 : fprintf (dump_file, "Node %s promoted to only called at startup.\n",
674 : : node->dump_name ());
675 : : changed = true;
676 : : }
677 : 5246356 : if ((d.only_called_at_exit && !d.only_called_at_startup)
678 : 49 : && !node->only_called_at_exit)
679 : : {
680 : 19 : node->only_called_at_exit = true;
681 : 19 : if (dump_file)
682 : 0 : fprintf (dump_file, "Node %s promoted to only called at exit.\n",
683 : : node->dump_name ());
684 : : changed = true;
685 : : }
686 : :
687 : : /* With profile we can decide on hot/normal based on count. */
688 : 5246356 : if (node->count. ipa().initialized_p ())
689 : : {
690 : 31567 : bool hot = false;
691 : 31567 : if (!(node->count. ipa() == profile_count::zero ())
692 : 207 : && node->count. ipa() >= get_hot_bb_threshold ())
693 : 202 : hot = true;
694 : 31567 : if (!hot)
695 : 31365 : hot |= contains_hot_call_p (node);
696 : 31567 : if (hot)
697 : : {
698 : 204 : if (node->frequency != NODE_FREQUENCY_HOT)
699 : : {
700 : 14 : if (dump_file)
701 : 0 : fprintf (dump_file, "Node %s promoted to hot.\n",
702 : : node->dump_name ());
703 : 14 : node->frequency = NODE_FREQUENCY_HOT;
704 : 14 : return true;
705 : : }
706 : : return false;
707 : : }
708 : 31363 : else if (node->frequency == NODE_FREQUENCY_HOT)
709 : : {
710 : 4 : if (dump_file)
711 : 0 : fprintf (dump_file, "Node %s reduced to normal.\n",
712 : : node->dump_name ());
713 : 4 : node->frequency = NODE_FREQUENCY_NORMAL;
714 : 4 : changed = true;
715 : : }
716 : : }
717 : : /* These come either from profile or user hints; never update them. */
718 : 5246152 : if (node->frequency == NODE_FREQUENCY_HOT
719 : 5246146 : || node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
720 : : return changed;
721 : 5221214 : if (d.maybe_unlikely_executed)
722 : : {
723 : 10352 : node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
724 : 10352 : if (dump_file)
725 : 0 : fprintf (dump_file, "Node %s promoted to unlikely executed.\n",
726 : : node->dump_name ());
727 : : changed = true;
728 : : }
729 : 5210862 : else if (d.maybe_executed_once && node->frequency != NODE_FREQUENCY_EXECUTED_ONCE)
730 : : {
731 : 112362 : node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
732 : 112362 : if (dump_file)
733 : 45 : fprintf (dump_file, "Node %s promoted to executed once.\n",
734 : : node->dump_name ());
735 : : changed = true;
736 : : }
737 : : return changed;
738 : : }
739 : :
740 : : /* Check that number of arguments of N agrees with E.
741 : : Be conservative when summaries are not present. */
742 : :
743 : : static bool
744 : 42 : check_argument_count (struct cgraph_node *n, struct cgraph_edge *e)
745 : : {
746 : 42 : if (!ipa_node_params_sum || !ipa_edge_args_sum)
747 : : return true;
748 : 42 : ipa_node_params *info = ipa_node_params_sum->get (n->function_symbol ());
749 : 42 : if (!info)
750 : : return true;
751 : 42 : ipa_edge_args *e_info = ipa_edge_args_sum->get (e);
752 : 42 : if (!e_info)
753 : : return true;
754 : 66 : if (ipa_get_param_count (info) != ipa_get_cs_argument_count (e_info)
755 : 42 : && (ipa_get_param_count (info) >= ipa_get_cs_argument_count (e_info)
756 : 0 : || !stdarg_p (TREE_TYPE (n->decl))))
757 : 0 : return false;
758 : : return true;
759 : : }
760 : :
761 : : /* Simple ipa profile pass propagating frequencies across the callgraph. */
762 : :
763 : : static unsigned int
764 : 151706 : ipa_profile (void)
765 : : {
766 : 151706 : struct cgraph_node **order;
767 : 151706 : struct cgraph_edge *e;
768 : 151706 : int order_pos;
769 : 151706 : bool something_changed = false;
770 : 151706 : int i;
771 : 151706 : widest_int overall_time = 0, cumulated = 0;
772 : 151706 : gcov_type overall_size = 0;
773 : 151706 : struct cgraph_node *n,*n2;
774 : 151706 : int nindirect = 0, ncommon = 0, nunknown = 0, nuseless = 0, nconverted = 0;
775 : 151706 : int nmismatch = 0, nimpossible = 0;
776 : 151706 : bool node_map_initialized = false;
777 : 151706 : gcov_type threshold;
778 : :
779 : 151706 : if (dump_file)
780 : : {
781 : 27 : if (profile_info)
782 : : {
783 : 4 : fprintf (dump_file,
784 : : "runs: %i sum_max: %" PRId64 " cutoff: %" PRId64"\n",
785 : : profile_info->runs, profile_info->sum_max, profile_info->cutoff);
786 : 4 : fprintf (dump_file, "hot bb threshold: %" PRId64 "\n",
787 : : get_hot_bb_threshold ());
788 : : }
789 : 27 : dump_histogram (dump_file, histogram);
790 : : }
791 : 161276 : for (i = 0; i < (int)histogram.length (); i++)
792 : : {
793 : 3328 : overall_time += ((widest_int)histogram[i]->count) * histogram[i]->time;
794 : : /* Watch for overflow. */
795 : 3328 : gcc_assert (overall_time >= 0);
796 : 3328 : overall_size += histogram[i]->size;
797 : : }
798 : 151706 : threshold = 0;
799 : 151706 : if (overall_time != 0)
800 : : {
801 : 101 : gcc_assert (overall_size);
802 : :
803 : 101 : widest_int cutoff = ((overall_time * param_hot_bb_count_ws_permille
804 : 202 : + 500) / 1000);
805 : : /* Watch for overflow. */
806 : 101 : gcc_assert (cutoff >= 0);
807 : 450 : for (i = 0; cumulated < cutoff; i++)
808 : : {
809 : 349 : cumulated += ((widest_int)histogram[i]->count) * histogram[i]->time;
810 : 349 : threshold = histogram[i]->count;
811 : : }
812 : 101 : if (!threshold)
813 : 0 : threshold = 1;
814 : 101 : if (dump_file)
815 : : {
816 : 4 : widest_int cumulated_time = 0;
817 : 4 : gcov_type cumulated_size = 0;
818 : :
819 : 4 : for (i = 0;
820 : 38 : i < (int)histogram.length () && histogram[i]->count >= threshold;
821 : : i++)
822 : : {
823 : 15 : cumulated_time += ((widest_int)histogram[i]->count)
824 : 30 : * histogram[i]->time;
825 : 15 : cumulated_size += histogram[i]->size;
826 : : }
827 : 4 : fprintf (dump_file, "Determined min count: %" PRId64
828 : : " Time:%3.2f%% Size:%3.2f%%\n",
829 : : (int64_t)threshold,
830 : 8 : (cumulated_time * 10000 / overall_time).to_shwi () / 100.0,
831 : 4 : cumulated_size * 100.0 / overall_size);
832 : 4 : }
833 : :
834 : 101 : if (in_lto_p)
835 : : {
836 : 4 : if (dump_file)
837 : 2 : fprintf (dump_file, "Setting hotness threshold in LTO mode.\n");
838 : 4 : set_hot_bb_threshold (threshold);
839 : : }
840 : 101 : }
841 : 151706 : histogram.release ();
842 : 151706 : histogram_pool.release ();
843 : :
844 : : /* Produce speculative calls: we saved common target from profiling into
845 : : e->target_id. Now, at link time, we can look up corresponding
846 : : function node and produce speculative call. */
847 : :
848 : 151706 : gcc_checking_assert (call_sums);
849 : :
850 : 151706 : if (dump_file)
851 : : {
852 : 27 : if (!node_map_initialized)
853 : 27 : init_node_map (false);
854 : 27 : node_map_initialized = true;
855 : :
856 : 27 : ipa_profile_dump_all_summaries (dump_file);
857 : : }
858 : :
859 : 1595378 : FOR_EACH_DEFINED_FUNCTION (n)
860 : : {
861 : 1443672 : bool update = false;
862 : :
863 : 1443672 : if (!opt_for_fn (n->decl, flag_ipa_profile))
864 : 11102 : continue;
865 : :
866 : 1574578 : for (e = n->indirect_calls; e; e = e->next_callee)
867 : : {
868 : 142008 : if (n->count.initialized_p ())
869 : 142004 : nindirect++;
870 : :
871 : 142008 : speculative_call_summary *csum = call_sums->get_create (e);
872 : 142047 : unsigned spec_count = csum->speculative_call_targets.length ();
873 : 39 : if (spec_count)
874 : : {
875 : 39 : if (!node_map_initialized)
876 : 19 : init_node_map (false);
877 : 39 : node_map_initialized = true;
878 : 39 : ncommon++;
879 : :
880 : 39 : unsigned speculative_id = 0;
881 : 39 : profile_count orig = e->count;
882 : 90 : for (unsigned i = 0; i < spec_count; i++)
883 : : {
884 : 51 : speculative_call_target item
885 : 51 : = csum->speculative_call_targets[i];
886 : 51 : n2 = find_func_by_profile_id (item.target_id);
887 : 51 : if (n2)
888 : : {
889 : 50 : if (dump_file)
890 : : {
891 : 8 : fprintf (dump_file,
892 : : "Indirect call -> direct call from"
893 : : " other module %s => %s, prob %3.2f\n",
894 : : n->dump_name (),
895 : : n2->dump_name (),
896 : : item.target_probability
897 : 8 : / (float) REG_BR_PROB_BASE);
898 : : }
899 : 50 : if (item.target_probability < REG_BR_PROB_BASE / 2)
900 : : {
901 : 8 : nuseless++;
902 : 8 : if (dump_file)
903 : 1 : fprintf (dump_file,
904 : : "Not speculating: "
905 : : "probability is too low.\n");
906 : : }
907 : 42 : else if (n2->get_availability () <= AVAIL_INTERPOSABLE
908 : 42 : && n2->can_be_discarded_p ())
909 : : {
910 : 0 : nuseless++;
911 : 0 : if (dump_file)
912 : 0 : fprintf (dump_file,
913 : : "Not speculating: target is overwritable "
914 : : "and can be discarded.\n");
915 : : }
916 : 42 : else if (!check_argument_count (n2, e))
917 : : {
918 : 0 : nmismatch++;
919 : 0 : if (dump_file)
920 : 0 : fprintf (dump_file,
921 : : "Not speculating: "
922 : : "parameter count mismatch\n");
923 : : }
924 : 42 : else if (e->indirect_info->polymorphic
925 : 10 : && !opt_for_fn (n->decl, flag_devirtualize)
926 : 46 : && !possible_polymorphic_call_target_p (e, n2))
927 : : {
928 : 0 : nimpossible++;
929 : 0 : if (dump_file)
930 : 0 : fprintf (dump_file,
931 : : "Not speculating: "
932 : : "function is not in the polymorphic "
933 : : "call target list\n");
934 : : }
935 : : else
936 : : {
937 : : /* Target may be overwritable, but profile says that
938 : : control flow goes to this particular implementation
939 : : of N2. Speculate on the local alias to allow
940 : : inlining. */
941 : 42 : if (!n2->can_be_discarded_p ())
942 : : {
943 : 36 : cgraph_node *alias;
944 : 36 : alias = dyn_cast<cgraph_node *>
945 : 36 : (n2->noninterposable_alias ());
946 : : if (alias)
947 : 42 : n2 = alias;
948 : : }
949 : 42 : nconverted++;
950 : 42 : profile_probability prob
951 : : = profile_probability::from_reg_br_prob_base
952 : 42 : (item.target_probability).adjusted ();
953 : 42 : e->make_speculative (n2,
954 : : orig.apply_probability (prob),
955 : : speculative_id);
956 : 42 : update = true;
957 : 42 : speculative_id++;
958 : : }
959 : : }
960 : : else
961 : : {
962 : 1 : if (dump_file)
963 : 0 : fprintf (dump_file,
964 : : "Function with profile-id %i not found.\n",
965 : : item.target_id);
966 : 1 : nunknown++;
967 : : }
968 : : }
969 : : }
970 : : }
971 : 1432570 : if (update)
972 : 36 : ipa_update_overall_fn_summary (n);
973 : : }
974 : 151706 : if (node_map_initialized)
975 : 46 : del_node_map ();
976 : 151706 : if (dump_file && nindirect)
977 : 25 : fprintf (dump_file,
978 : : "%i indirect calls trained.\n"
979 : : "%i (%3.2f%%) have common target.\n"
980 : : "%i (%3.2f%%) targets was not found.\n"
981 : : "%i (%3.2f%%) targets had parameter count mismatch.\n"
982 : : "%i (%3.2f%%) targets was not in polymorphic call target list.\n"
983 : : "%i (%3.2f%%) speculations seems useless.\n"
984 : : "%i (%3.2f%%) speculations produced.\n",
985 : : nindirect,
986 : 25 : ncommon, ncommon * 100.0 / nindirect,
987 : 25 : nunknown, nunknown * 100.0 / nindirect,
988 : 25 : nmismatch, nmismatch * 100.0 / nindirect,
989 : 25 : nimpossible, nimpossible * 100.0 / nindirect,
990 : 25 : nuseless, nuseless * 100.0 / nindirect,
991 : 25 : nconverted, nconverted * 100.0 / nindirect);
992 : :
993 : 151706 : order = XCNEWVEC (struct cgraph_node *, symtab->cgraph_count);
994 : 151706 : order_pos = ipa_reverse_postorder (order);
995 : 2873657 : for (i = order_pos - 1; i >= 0; i--)
996 : : {
997 : 2721951 : if (order[i]->local
998 : 170504 : && opt_for_fn (order[i]->decl, flag_ipa_profile)
999 : 2886962 : && ipa_propagate_frequency (order[i]))
1000 : : {
1001 : 325092 : for (e = order[i]->callees; e; e = e->next_callee)
1002 : 296426 : if (e->callee->local && !e->callee->aux)
1003 : : {
1004 : 10082 : something_changed = true;
1005 : 10082 : e->callee->aux = (void *)1;
1006 : : }
1007 : : }
1008 : 2721951 : order[i]->aux = NULL;
1009 : : }
1010 : :
1011 : 160348 : while (something_changed)
1012 : : {
1013 : : something_changed = false;
1014 : 115013 : for (i = order_pos - 1; i >= 0; i--)
1015 : : {
1016 : 106371 : if (order[i]->aux
1017 : 15999 : && opt_for_fn (order[i]->decl, flag_ipa_profile)
1018 : 122370 : && ipa_propagate_frequency (order[i]))
1019 : : {
1020 : 95459 : for (e = order[i]->callees; e; e = e->next_callee)
1021 : 81014 : if (e->callee->local && !e->callee->aux)
1022 : : {
1023 : 5921 : something_changed = true;
1024 : 5921 : e->callee->aux = (void *)1;
1025 : : }
1026 : : }
1027 : 106371 : order[i]->aux = NULL;
1028 : : }
1029 : : }
1030 : 151706 : free (order);
1031 : :
1032 : 151706 : if (dump_file && (dump_flags & TDF_DETAILS))
1033 : 0 : symtab->dump (dump_file);
1034 : :
1035 : 151706 : delete call_sums;
1036 : 151706 : call_sums = NULL;
1037 : :
1038 : 151706 : return 0;
1039 : 151706 : }
1040 : :
1041 : : namespace {
1042 : :
1043 : : const pass_data pass_data_ipa_profile =
1044 : : {
1045 : : IPA_PASS, /* type */
1046 : : "profile_estimate", /* name */
1047 : : OPTGROUP_NONE, /* optinfo_flags */
1048 : : TV_IPA_PROFILE, /* tv_id */
1049 : : 0, /* properties_required */
1050 : : 0, /* properties_provided */
1051 : : 0, /* properties_destroyed */
1052 : : 0, /* todo_flags_start */
1053 : : 0, /* todo_flags_finish */
1054 : : };
1055 : :
1056 : : class pass_ipa_profile : public ipa_opt_pass_d
1057 : : {
1058 : : public:
1059 : 289080 : pass_ipa_profile (gcc::context *ctxt)
1060 : : : ipa_opt_pass_d (pass_data_ipa_profile, ctxt,
1061 : : ipa_profile_generate_summary, /* generate_summary */
1062 : : ipa_profile_write_summary, /* write_summary */
1063 : : ipa_profile_read_summary, /* read_summary */
1064 : : NULL, /* write_optimization_summary */
1065 : : NULL, /* read_optimization_summary */
1066 : : NULL, /* stmt_fixup */
1067 : : 0, /* function_transform_todo_flags_start */
1068 : : NULL, /* function_transform */
1069 : 289080 : NULL) /* variable_transform */
1070 : 289080 : {}
1071 : :
1072 : : /* opt_pass methods: */
1073 : 593004 : bool gate (function *) final override { return flag_ipa_profile || in_lto_p; }
1074 : 151706 : unsigned int execute (function *) final override { return ipa_profile (); }
1075 : :
1076 : : }; // class pass_ipa_profile
1077 : :
1078 : : } // anon namespace
1079 : :
1080 : : ipa_opt_pass_d *
1081 : 289080 : make_pass_ipa_profile (gcc::context *ctxt)
1082 : : {
1083 : 289080 : return new pass_ipa_profile (ctxt);
1084 : : }
1085 : :
1086 : : /* Reset all state within ipa-profile.cc so that we can rerun the compiler
1087 : : within the same process. For use by toplev::finalize. */
1088 : :
1089 : : void
1090 : 260181 : ipa_profile_cc_finalize (void)
1091 : : {
1092 : 260181 : delete call_sums;
1093 : 260181 : call_sums = NULL;
1094 : 260181 : }
|
