Branch data Line data Source code
1 : : /* Basic IPA optimizations based on profile.
2 : : Copyright (C) 2003-2024 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 : 34353 : histogram_hash::hash (const histogram_entry *val)
90 : : {
91 : 34353 : return val->count;
92 : : }
93 : :
94 : : inline int
95 : 17717 : histogram_hash::equal (const histogram_entry *val, const histogram_entry *val2)
96 : : {
97 : 17717 : 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 : 16771 : account_time_size (hash_table<histogram_hash> *hashtable,
105 : : vec<histogram_entry *> &histogram,
106 : : gcov_type count, int time, int size)
107 : : {
108 : 16771 : histogram_entry key = {count, 0, 0};
109 : 16771 : histogram_entry **val = hashtable->find_slot (&key, INSERT);
110 : :
111 : 16771 : if (!*val)
112 : : {
113 : 3611 : *val = histogram_pool.allocate ();
114 : 3611 : **val = key;
115 : 3611 : histogram.safe_push (*val);
116 : : }
117 : 16771 : (*val)->time += time;
118 : 16771 : (*val)->size += size;
119 : 16771 : }
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 : 28 : dump_histogram (FILE *file, vec<histogram_entry *> histogram)
137 : : {
138 : 28 : unsigned int i;
139 : 28 : gcov_type overall_time = 0, cumulated_time = 0, cumulated_size = 0,
140 : 28 : overall_size = 0;
141 : :
142 : 28 : fprintf (dump_file, "Histogram:\n");
143 : 98 : 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 : 28 : if (!overall_time)
149 : 24 : overall_time = 1;
150 : 28 : if (!overall_size)
151 : 24 : overall_size = 1;
152 : 70 : 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 : 28 : }
164 : :
165 : : /* Structure containing speculative target information from profile. */
166 : :
167 : : struct speculative_call_target
168 : : {
169 : 109 : speculative_call_target (unsigned int id = 0, int prob = 0)
170 : 48 : : 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 : 136953 : class speculative_call_summary
181 : : {
182 : : public:
183 : 136953 : 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 : 154502 : ipa_profile_call_summaries (symbol_table *table)
199 : 309004 : : 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 : 38 : speculative_call_summary::dump (FILE *f)
214 : : {
215 : 38 : cgraph_node *n2;
216 : :
217 : 38 : unsigned spec_count = speculative_call_targets.length ();
218 : 46 : 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 : 38 : }
232 : :
233 : : /* Duplicate info when an edge is cloned. */
234 : :
235 : : void
236 : 35 : ipa_profile_call_summaries::duplicate (cgraph_edge *, cgraph_edge *,
237 : : speculative_call_summary *old_sum,
238 : : speculative_call_summary *new_sum)
239 : : {
240 : 35 : if (!old_sum)
241 : : return;
242 : :
243 : 35 : unsigned old_count = old_sum->speculative_call_targets.length ();
244 : 35 : if (!old_count)
245 : : return;
246 : :
247 : 35 : new_sum->speculative_call_targets.reserve_exact (old_count);
248 : 35 : new_sum->speculative_call_targets.quick_grow_cleared (old_count);
249 : :
250 : 83 : for (unsigned i = 0; i < old_count; i++)
251 : : {
252 : 144 : new_sum->speculative_call_targets[i]
253 : 48 : = old_sum->speculative_call_targets[i];
254 : : }
255 : : }
256 : :
257 : : /* Collect histogram and speculative target summaries from CFG profiles. */
258 : :
259 : : static void
260 : 141628 : ipa_profile_generate_summary (void)
261 : : {
262 : 141628 : struct cgraph_node *node;
263 : 141628 : gimple_stmt_iterator gsi;
264 : 141628 : basic_block bb;
265 : :
266 : 141628 : hash_table<histogram_hash> hashtable (10);
267 : :
268 : 141628 : gcc_checking_assert (!call_sums);
269 : 141628 : call_sums = new ipa_profile_call_summaries (symtab);
270 : :
271 : 1372622 : FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
272 : 1230994 : if (ENTRY_BLOCK_PTR_FOR_FN
273 : 2461988 : (DECL_STRUCT_FUNCTION (node->decl))->count.ipa_p ())
274 : 25102 : FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
275 : : {
276 : 19230 : int time = 0;
277 : 19230 : int size = 0;
278 : 120588 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
279 : : {
280 : 82128 : gimple *stmt = gsi_stmt (gsi);
281 : 82128 : if (gimple_code (stmt) == GIMPLE_CALL
282 : 82128 : && !gimple_call_fndecl (stmt))
283 : : {
284 : 155 : histogram_value h;
285 : 155 : h = gimple_histogram_value_of_type
286 : 155 : (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 : 155 : 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 : 82128 : time += estimate_num_insns (stmt, &eni_time_weights);
328 : 82128 : size += estimate_num_insns (stmt, &eni_size_weights);
329 : : }
330 : 52374 : if (bb->count.ipa_p () && bb->count.initialized_p ())
331 : 16572 : account_time_size (&hashtable, histogram,
332 : 33144 : bb->count.ipa ().to_gcov_type (),
333 : : time, size);
334 : : }
335 : 141628 : histogram.qsort (cmp_counts);
336 : 141628 : }
337 : :
338 : : /* Serialize the speculative summary info for LTO. */
339 : :
340 : : static void
341 : 1732 : ipa_profile_write_edge_summary (lto_simple_output_block *ob,
342 : : speculative_call_summary *csum)
343 : : {
344 : 1732 : unsigned len = 0;
345 : :
346 : 1732 : len = csum->speculative_call_targets.length ();
347 : :
348 : 4 : gcc_assert (len <= GCOV_TOPN_MAXIMUM_TRACKED_VALUES);
349 : :
350 : 1732 : streamer_write_hwi_stream (ob->main_stream, len);
351 : :
352 : 1732 : 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 : 1732 : }
364 : :
365 : : /* Serialize the ipa info for lto. */
366 : :
367 : : static void
368 : 18467 : ipa_profile_write_summary (void)
369 : : {
370 : 18467 : struct lto_simple_output_block *ob
371 : 18467 : = lto_create_simple_output_block (LTO_section_ipa_profile);
372 : 18467 : unsigned int i;
373 : :
374 : 18467 : streamer_write_uhwi_stream (ob->main_stream, histogram.length ());
375 : 38057 : for (i = 0; i < histogram.length (); i++)
376 : : {
377 : 379 : streamer_write_gcov_count_stream (ob->main_stream, histogram[i]->count);
378 : 379 : streamer_write_uhwi_stream (ob->main_stream, histogram[i]->time);
379 : 379 : streamer_write_uhwi_stream (ob->main_stream, histogram[i]->size);
380 : : }
381 : :
382 : 18467 : if (!call_sums)
383 : 0 : return;
384 : :
385 : : /* Serialize speculative targets information. */
386 : 18467 : unsigned int count = 0;
387 : 18467 : lto_symtab_encoder_t encoder = ob->decl_state->symtab_node_encoder;
388 : 18467 : lto_symtab_encoder_iterator lsei;
389 : 18467 : cgraph_node *node;
390 : :
391 : 214838 : for (lsei = lsei_start_function_in_partition (encoder); !lsei_end_p (lsei);
392 : 89049 : lsei_next_function_in_partition (&lsei))
393 : : {
394 : 89049 : node = lsei_cgraph_node (lsei);
395 : 89048 : if (node->definition && node->has_gimple_body_p ()
396 : 177174 : && node->indirect_calls)
397 : 956 : count++;
398 : : }
399 : :
400 : 18467 : streamer_write_uhwi_stream (ob->main_stream, count);
401 : :
402 : : /* Process all of the functions. */
403 : 18467 : for (lsei = lsei_start_function_in_partition (encoder);
404 : 52260 : !lsei_end_p (lsei) && count; lsei_next_function_in_partition (&lsei))
405 : : {
406 : 7760 : cgraph_node *node = lsei_cgraph_node (lsei);
407 : 7760 : if (node->definition && node->has_gimple_body_p ()
408 : 15183 : && node->indirect_calls)
409 : : {
410 : 956 : int node_ref = lto_symtab_encoder_encode (encoder, node);
411 : 956 : streamer_write_uhwi_stream (ob->main_stream, node_ref);
412 : :
413 : 2688 : for (cgraph_edge *e = node->indirect_calls; e; e = e->next_callee)
414 : : {
415 : 1732 : speculative_call_summary *csum = call_sums->get_create (e);
416 : 1732 : ipa_profile_write_edge_summary (ob, csum);
417 : : }
418 : : }
419 : : }
420 : :
421 : 18467 : 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 : 28 : ipa_profile_dump_all_summaries (FILE *f)
428 : : {
429 : 28 : fprintf (dump_file,
430 : : "\n========== IPA-profile speculative targets: ==========\n");
431 : 28 : cgraph_node *node;
432 : 100 : FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
433 : : {
434 : 72 : fprintf (f, "\nSummary for node %s:\n", node->dump_name ());
435 : 110 : for (cgraph_edge *e = node->indirect_calls; e; e = e->next_callee)
436 : : {
437 : 38 : fprintf (f, " Summary for %s of indirect edge %d:\n",
438 : 38 : e->caller->dump_name (), e->lto_stmt_uid);
439 : 38 : speculative_call_summary *csum = call_sums->get_create (e);
440 : 38 : csum->dump (f);
441 : : }
442 : : }
443 : 28 : fprintf (f, "\n\n");
444 : 28 : }
445 : :
446 : : /* Read speculative targets information about edge for LTO WPA. */
447 : :
448 : : static void
449 : 1317 : ipa_profile_read_edge_summary (class lto_input_block *ib, cgraph_edge *edge)
450 : : {
451 : 1317 : unsigned i, len;
452 : :
453 : 1317 : len = streamer_read_hwi (ib);
454 : 1317 : gcc_assert (len <= GCOV_TOPN_MAXIMUM_TRACKED_VALUES);
455 : 1317 : speculative_call_summary *csum = call_sums->get_create (edge);
456 : :
457 : 1327 : 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 : 1317 : }
465 : :
466 : : /* Read profile speculative targets section information for LTO WPA. */
467 : :
468 : : static void
469 : 10006 : ipa_profile_read_summary_section (struct lto_file_decl_data *file_data,
470 : : class lto_input_block *ib)
471 : : {
472 : 10006 : if (!ib)
473 : : return;
474 : :
475 : 10006 : lto_symtab_encoder_t encoder = file_data->symtab_node_encoder;
476 : :
477 : 10006 : unsigned int count = streamer_read_uhwi (ib);
478 : :
479 : 10006 : unsigned int i;
480 : 10006 : unsigned int index;
481 : 10006 : cgraph_node * node;
482 : :
483 : 10626 : for (i = 0; i < count; i++)
484 : : {
485 : 620 : index = streamer_read_uhwi (ib);
486 : 620 : node
487 : 620 : = dyn_cast<cgraph_node *> (lto_symtab_encoder_deref (encoder, index));
488 : :
489 : 1937 : for (cgraph_edge *e = node->indirect_calls; e; e = e->next_callee)
490 : 1317 : 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 : 12874 : ipa_profile_read_summary (void)
499 : : {
500 : 12874 : struct lto_file_decl_data ** file_data_vec
501 : 12874 : = lto_get_file_decl_data ();
502 : 12874 : struct lto_file_decl_data * file_data;
503 : 12874 : int j = 0;
504 : :
505 : 12874 : hash_table<histogram_hash> hashtable (10);
506 : :
507 : 12874 : gcc_checking_assert (!call_sums);
508 : 12874 : call_sums = new ipa_profile_call_summaries (symtab);
509 : :
510 : 26751 : while ((file_data = file_data_vec[j++]))
511 : : {
512 : 13877 : const char *data;
513 : 13877 : size_t len;
514 : 13877 : class lto_input_block *ib
515 : 13877 : = lto_create_simple_input_block (file_data,
516 : : LTO_section_ipa_profile,
517 : : &data, &len);
518 : 13877 : if (ib)
519 : : {
520 : 10006 : unsigned int num = streamer_read_uhwi (ib);
521 : 10006 : unsigned int n;
522 : 10205 : for (n = 0; n < num; n++)
523 : : {
524 : 199 : gcov_type count = streamer_read_gcov_count (ib);
525 : 199 : int time = streamer_read_uhwi (ib);
526 : 199 : int size = streamer_read_uhwi (ib);
527 : 199 : account_time_size (&hashtable, histogram,
528 : : count, time, size);
529 : : }
530 : :
531 : 10006 : ipa_profile_read_summary_section (file_data, ib);
532 : :
533 : 10006 : lto_destroy_simple_input_block (file_data,
534 : : LTO_section_ipa_profile,
535 : : ib, data, len);
536 : : }
537 : : }
538 : 12874 : histogram.qsort (cmp_counts);
539 : 12874 : }
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 : 4099504 : ipa_propagate_frequency_1 (struct cgraph_node *node, void *data)
556 : : {
557 : 4099504 : struct ipa_propagate_frequency_data *d;
558 : 4099504 : struct cgraph_edge *edge;
559 : :
560 : 4099504 : d = (struct ipa_propagate_frequency_data *)data;
561 : 4099504 : for (edge = node->callers;
562 : 8298198 : edge && (d->maybe_unlikely_executed || d->maybe_executed_once
563 : 118673 : || d->only_called_at_startup || d->only_called_at_exit);
564 : 4198694 : edge = edge->next_caller)
565 : : {
566 : 4198694 : if (edge->caller != d->function_symbol)
567 : : {
568 : 4196474 : 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 : 4196474 : if (MAIN_NAME_P (DECL_NAME (edge->caller->decl)))
573 : 136725 : d->only_called_at_startup = 0;
574 : 4196474 : 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 : 4198694 : if (profile_info
583 : 4199183 : && !(edge->callee->count.ipa () == profile_count::zero ())
584 : 4199180 : && (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 : 486 : d->maybe_unlikely_executed = false;
589 : 4198694 : if (edge->count.ipa ().initialized_p ()
590 : 4198694 : && !edge->count.ipa ().nonzero_p ())
591 : 32804 : continue;
592 : 4165890 : switch (edge->caller->frequency)
593 : : {
594 : : case NODE_FREQUENCY_UNLIKELY_EXECUTED:
595 : : break;
596 : 276019 : case NODE_FREQUENCY_EXECUTED_ONCE:
597 : 276019 : {
598 : 276019 : if (dump_file && (dump_flags & TDF_DETAILS))
599 : 110 : fprintf (dump_file, " Called by %s that is executed once\n",
600 : : edge->caller->dump_name ());
601 : 276019 : d->maybe_unlikely_executed = false;
602 : 276019 : ipa_call_summary *s = ipa_call_summaries->get (edge);
603 : 276019 : if (s != NULL && s->loop_depth)
604 : : {
605 : 7572 : d->maybe_executed_once = false;
606 : 7572 : if (dump_file && (dump_flags & TDF_DETAILS))
607 : 6 : fprintf (dump_file, " Called in loop\n");
608 : : }
609 : : break;
610 : : }
611 : 3887910 : case NODE_FREQUENCY_HOT:
612 : 3887910 : case NODE_FREQUENCY_NORMAL:
613 : 3887910 : if (dump_file && (dump_flags & TDF_DETAILS))
614 : 151 : fprintf (dump_file, " Called by %s that is normal or hot\n",
615 : : edge->caller->dump_name ());
616 : 3887910 : d->maybe_unlikely_executed = false;
617 : 3887910 : d->maybe_executed_once = false;
618 : 3887910 : break;
619 : : }
620 : : }
621 : 4099504 : return edge != NULL;
622 : : }
623 : :
624 : : /* Return ture if NODE contains hot calls. */
625 : :
626 : : bool
627 : 32125 : contains_hot_call_p (struct cgraph_node *node)
628 : : {
629 : 32125 : struct cgraph_edge *e;
630 : 78866 : for (e = node->callees; e; e = e->next_callee)
631 : 46743 : if (e->maybe_hot_p ())
632 : : return true;
633 : 46741 : else if (!e->inline_failed
634 : 46741 : && contains_hot_call_p (e->callee))
635 : : return true;
636 : 32474 : for (e = node->indirect_calls; e; e = e->next_callee)
637 : 351 : 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 : 7358886 : ipa_propagate_frequency (struct cgraph_node *node)
646 : : {
647 : 7358886 : struct ipa_propagate_frequency_data d = {node, true, true, true, true};
648 : 7358886 : bool changed = false;
649 : :
650 : : /* We cannot propagate anything useful about externally visible functions
651 : : nor about virtuals. */
652 : 7358886 : if (!node->local
653 : 4144207 : || node->alias
654 : 11491836 : || (opt_for_fn (node->decl, flag_devirtualize)
655 : 4060061 : && DECL_VIRTUAL_P (node->decl)))
656 : : return false;
657 : 4089934 : gcc_assert (node->analyzed);
658 : 4089934 : if (dump_file && (dump_flags & TDF_DETAILS))
659 : 260 : fprintf (dump_file, "Processing frequency %s\n", node->dump_name ());
660 : :
661 : 4089934 : node->call_for_symbol_and_aliases (ipa_propagate_frequency_1, &d,
662 : : true);
663 : :
664 : 4089934 : if ((d.only_called_at_startup && !d.only_called_at_exit)
665 : 5642 : && !node->only_called_at_startup)
666 : : {
667 : 1608 : node->only_called_at_startup = true;
668 : 1608 : 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 : 4089934 : if ((d.only_called_at_exit && !d.only_called_at_startup)
674 : 52 : && !node->only_called_at_exit)
675 : : {
676 : 20 : node->only_called_at_exit = true;
677 : 20 : 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 : 4089934 : if (node->count. ipa().initialized_p ())
685 : : {
686 : 24300 : bool hot = false;
687 : 24300 : if (!(node->count. ipa() == profile_count::zero ())
688 : 163 : && node->count. ipa() >= get_hot_bb_threshold ())
689 : 158 : hot = true;
690 : 24300 : if (!hot)
691 : 24142 : hot |= contains_hot_call_p (node);
692 : 24300 : if (hot)
693 : : {
694 : 160 : if (node->frequency != NODE_FREQUENCY_HOT)
695 : : {
696 : 10 : if (dump_file)
697 : 0 : fprintf (dump_file, "Node %s promoted to hot.\n",
698 : : node->dump_name ());
699 : 10 : node->frequency = NODE_FREQUENCY_HOT;
700 : 10 : return true;
701 : : }
702 : : return false;
703 : : }
704 : 24140 : 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 : 4089774 : if (node->frequency == NODE_FREQUENCY_HOT
715 : 4089768 : || node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
716 : : return changed;
717 : 4067470 : if (d.maybe_unlikely_executed)
718 : : {
719 : 7342 : node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
720 : 7342 : if (dump_file)
721 : 0 : fprintf (dump_file, "Node %s promoted to unlikely executed.\n",
722 : : node->dump_name ());
723 : : changed = true;
724 : : }
725 : 4060128 : else if (d.maybe_executed_once && node->frequency != NODE_FREQUENCY_EXECUTED_ONCE)
726 : : {
727 : 77230 : node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
728 : 77230 : if (dump_file)
729 : 53 : 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 : 35 : check_argument_count (struct cgraph_node *n, struct cgraph_edge *e)
741 : : {
742 : 35 : if (!ipa_node_params_sum || !ipa_edge_args_sum)
743 : : return true;
744 : 35 : ipa_node_params *info = ipa_node_params_sum->get (n->function_symbol ());
745 : 35 : if (!info)
746 : : return true;
747 : 35 : ipa_edge_args *e_info = ipa_edge_args_sum->get (e);
748 : 35 : if (!e_info)
749 : : return true;
750 : 56 : if (ipa_get_param_count (info) != ipa_get_cs_argument_count (e_info)
751 : 35 : && (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 : 145916 : ipa_profile (void)
761 : : {
762 : 145916 : struct cgraph_node **order;
763 : 145916 : struct cgraph_edge *e;
764 : 145916 : int order_pos;
765 : 145916 : bool something_changed = false;
766 : 145916 : int i;
767 : 145916 : gcov_type overall_time = 0, cutoff = 0, cumulated = 0, overall_size = 0;
768 : 145916 : struct cgraph_node *n,*n2;
769 : 145916 : int nindirect = 0, ncommon = 0, nunknown = 0, nuseless = 0, nconverted = 0;
770 : 145916 : int nmismatch = 0, nimpossible = 0;
771 : 145916 : bool node_map_initialized = false;
772 : 145916 : gcov_type threshold;
773 : :
774 : 145916 : if (dump_file)
775 : 28 : dump_histogram (dump_file, histogram);
776 : 155787 : for (i = 0; i < (int)histogram.length (); i++)
777 : : {
778 : 3426 : overall_time += histogram[i]->count * histogram[i]->time;
779 : 3426 : overall_size += histogram[i]->size;
780 : : }
781 : 145916 : threshold = 0;
782 : 145916 : 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 : 145916 : histogram.release ();
820 : 145916 : 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 : 145916 : gcc_checking_assert (call_sums);
827 : :
828 : 145916 : if (dump_file)
829 : : {
830 : 28 : if (!node_map_initialized)
831 : 28 : init_node_map (false);
832 : 28 : node_map_initialized = true;
833 : :
834 : 28 : ipa_profile_dump_all_summaries (dump_file);
835 : : }
836 : :
837 : 1474633 : FOR_EACH_DEFINED_FUNCTION (n)
838 : : {
839 : 1328717 : bool update = false;
840 : :
841 : 1328717 : if (!opt_for_fn (n->decl, flag_ipa_profile))
842 : 11096 : continue;
843 : :
844 : 1453681 : for (e = n->indirect_calls; e; e = e->next_callee)
845 : : {
846 : 136060 : if (n->count.initialized_p ())
847 : 136055 : nindirect++;
848 : :
849 : 136060 : speculative_call_summary *csum = call_sums->get_create (e);
850 : 136099 : 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 (!e->maybe_hot_p ())
886 : : {
887 : 7 : nuseless++;
888 : 7 : if (dump_file)
889 : 0 : fprintf (dump_file,
890 : : "Not speculating: call is cold.\n");
891 : : }
892 : 35 : else if (n2->get_availability () <= AVAIL_INTERPOSABLE
893 : 35 : && n2->can_be_discarded_p ())
894 : : {
895 : 0 : nuseless++;
896 : 0 : if (dump_file)
897 : 0 : fprintf (dump_file,
898 : : "Not speculating: target is overwritable "
899 : : "and can be discarded.\n");
900 : : }
901 : 35 : else if (!check_argument_count (n2, e))
902 : : {
903 : 0 : nmismatch++;
904 : 0 : if (dump_file)
905 : 0 : fprintf (dump_file,
906 : : "Not speculating: "
907 : : "parameter count mismatch\n");
908 : : }
909 : 35 : else if (e->indirect_info->polymorphic
910 : 8 : && !opt_for_fn (n->decl, flag_devirtualize)
911 : 39 : && !possible_polymorphic_call_target_p (e, n2))
912 : : {
913 : 0 : nimpossible++;
914 : 0 : if (dump_file)
915 : 0 : fprintf (dump_file,
916 : : "Not speculating: "
917 : : "function is not in the polymorphic "
918 : : "call target list\n");
919 : : }
920 : : else
921 : : {
922 : : /* Target may be overwritable, but profile says that
923 : : control flow goes to this particular implementation
924 : : of N2. Speculate on the local alias to allow
925 : : inlining. */
926 : 35 : if (!n2->can_be_discarded_p ())
927 : : {
928 : 31 : cgraph_node *alias;
929 : 31 : alias = dyn_cast<cgraph_node *>
930 : 31 : (n2->noninterposable_alias ());
931 : : if (alias)
932 : 35 : n2 = alias;
933 : : }
934 : 35 : nconverted++;
935 : 35 : profile_probability prob
936 : : = profile_probability::from_reg_br_prob_base
937 : 35 : (item.target_probability).adjusted ();
938 : 35 : e->make_speculative (n2,
939 : : orig.apply_probability (prob),
940 : : speculative_id);
941 : 35 : update = true;
942 : 35 : speculative_id++;
943 : : }
944 : : }
945 : : else
946 : : {
947 : 1 : if (dump_file)
948 : 0 : fprintf (dump_file,
949 : : "Function with profile-id %i not found.\n",
950 : : item.target_id);
951 : 1 : nunknown++;
952 : : }
953 : : }
954 : : }
955 : : }
956 : 1317621 : if (update)
957 : 29 : ipa_update_overall_fn_summary (n);
958 : : }
959 : 145916 : if (node_map_initialized)
960 : 47 : del_node_map ();
961 : 145916 : if (dump_file && nindirect)
962 : 26 : fprintf (dump_file,
963 : : "%i indirect calls trained.\n"
964 : : "%i (%3.2f%%) have common target.\n"
965 : : "%i (%3.2f%%) targets was not found.\n"
966 : : "%i (%3.2f%%) targets had parameter count mismatch.\n"
967 : : "%i (%3.2f%%) targets was not in polymorphic call target list.\n"
968 : : "%i (%3.2f%%) speculations seems useless.\n"
969 : : "%i (%3.2f%%) speculations produced.\n",
970 : : nindirect,
971 : 26 : ncommon, ncommon * 100.0 / nindirect,
972 : 26 : nunknown, nunknown * 100.0 / nindirect,
973 : 26 : nmismatch, nmismatch * 100.0 / nindirect,
974 : 26 : nimpossible, nimpossible * 100.0 / nindirect,
975 : 26 : nuseless, nuseless * 100.0 / nindirect,
976 : 26 : nconverted, nconverted * 100.0 / nindirect);
977 : :
978 : 145916 : order = XCNEWVEC (struct cgraph_node *, symtab->cgraph_count);
979 : 145916 : order_pos = ipa_reverse_postorder (order);
980 : 2722576 : for (i = order_pos - 1; i >= 0; i--)
981 : : {
982 : 2576660 : if (order[i]->local
983 : 155226 : && opt_for_fn (order[i]->decl, flag_ipa_profile)
984 : 2726460 : && ipa_propagate_frequency (order[i]))
985 : : {
986 : 303358 : for (e = order[i]->callees; e; e = e->next_callee)
987 : 277529 : if (e->callee->local && !e->callee->aux)
988 : : {
989 : 9217 : something_changed = true;
990 : 9217 : e->callee->aux = (void *)1;
991 : : }
992 : : }
993 : 2576660 : order[i]->aux = NULL;
994 : : }
995 : :
996 : 154192 : while (something_changed)
997 : : {
998 : : something_changed = false;
999 : 108348 : for (i = order_pos - 1; i >= 0; i--)
1000 : : {
1001 : 100072 : if (order[i]->aux
1002 : 14862 : && opt_for_fn (order[i]->decl, flag_ipa_profile)
1003 : 114934 : && ipa_propagate_frequency (order[i]))
1004 : : {
1005 : 67113 : for (e = order[i]->callees; e; e = e->next_callee)
1006 : 53715 : if (e->callee->local && !e->callee->aux)
1007 : : {
1008 : 5649 : something_changed = true;
1009 : 5649 : e->callee->aux = (void *)1;
1010 : : }
1011 : : }
1012 : 100072 : order[i]->aux = NULL;
1013 : : }
1014 : : }
1015 : 145916 : free (order);
1016 : :
1017 : 145916 : if (dump_file && (dump_flags & TDF_DETAILS))
1018 : 0 : symtab->dump (dump_file);
1019 : :
1020 : 145916 : delete call_sums;
1021 : 145916 : call_sums = NULL;
1022 : :
1023 : 145916 : return 0;
1024 : : }
1025 : :
1026 : : namespace {
1027 : :
1028 : : const pass_data pass_data_ipa_profile =
1029 : : {
1030 : : IPA_PASS, /* type */
1031 : : "profile_estimate", /* name */
1032 : : OPTGROUP_NONE, /* optinfo_flags */
1033 : : TV_IPA_PROFILE, /* tv_id */
1034 : : 0, /* properties_required */
1035 : : 0, /* properties_provided */
1036 : : 0, /* properties_destroyed */
1037 : : 0, /* todo_flags_start */
1038 : : 0, /* todo_flags_finish */
1039 : : };
1040 : :
1041 : : class pass_ipa_profile : public ipa_opt_pass_d
1042 : : {
1043 : : public:
1044 : 285617 : pass_ipa_profile (gcc::context *ctxt)
1045 : : : ipa_opt_pass_d (pass_data_ipa_profile, ctxt,
1046 : : ipa_profile_generate_summary, /* generate_summary */
1047 : : ipa_profile_write_summary, /* write_summary */
1048 : : ipa_profile_read_summary, /* read_summary */
1049 : : NULL, /* write_optimization_summary */
1050 : : NULL, /* read_optimization_summary */
1051 : : NULL, /* stmt_fixup */
1052 : : 0, /* function_transform_todo_flags_start */
1053 : : NULL, /* function_transform */
1054 : 285617 : NULL) /* variable_transform */
1055 : 285617 : {}
1056 : :
1057 : : /* opt_pass methods: */
1058 : 586712 : bool gate (function *) final override { return flag_ipa_profile || in_lto_p; }
1059 : 145916 : unsigned int execute (function *) final override { return ipa_profile (); }
1060 : :
1061 : : }; // class pass_ipa_profile
1062 : :
1063 : : } // anon namespace
1064 : :
1065 : : ipa_opt_pass_d *
1066 : 285617 : make_pass_ipa_profile (gcc::context *ctxt)
1067 : : {
1068 : 285617 : return new pass_ipa_profile (ctxt);
1069 : : }
1070 : :
1071 : : /* Reset all state within ipa-profile.cc so that we can rerun the compiler
1072 : : within the same process. For use by toplev::finalize. */
1073 : :
1074 : : void
1075 : 257333 : ipa_profile_cc_finalize (void)
1076 : : {
1077 : 257333 : delete call_sums;
1078 : 257333 : call_sums = NULL;
1079 : 257333 : }
|