1/* Basic IPA optimizations based on profile.
2 Copyright (C) 2003-2017 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along 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 Similar histogram is also estimated by coverage runtime. This histogram
29 is not dependent on LTO, but it suffers from various defects; first
30 gcov runtime is not weighting individual basic block by estimated execution
31 time and second the merging of multiple runs makes assumption that the
32 histogram distribution did not change. Consequentely histogram constructed
33 here may be more precise.
34
35 The information is used to set hot/cold thresholds.
36 - Next speculative indirect call resolution is performed: the local
37 profile pass assigns profile-id to each function and provide us with a
38 histogram specifying the most common target. We look up the callgraph
39 node corresponding to the target and produce a speculative call.
40
41 This call may or may not survive through IPA optimization based on decision
42 of inliner.
43 - Finally we propagate the following flags: unlikely executed, executed
44 once, executed at startup and executed at exit. These flags are used to
45 control code size/performance threshold and code placement (by producing
46 .text.unlikely/.text.hot/.text.startup/.text.exit subsections). */
47#include "config.h"
48#include "system.h"
49#include "coretypes.h"
50#include "backend.h"
51#include "tree.h"
52#include "gimple.h"
53#include "predict.h"
54#include "alloc-pool.h"
55#include "tree-pass.h"
56#include "cgraph.h"
57#include "data-streamer.h"
58#include "gimple-iterator.h"
59#include "ipa-utils.h"
60#include "profile.h"
61#include "params.h"
62#include "value-prof.h"
63#include "tree-inline.h"
64#include "symbol-summary.h"
65#include "tree-vrp.h"
66#include "ipa-prop.h"
67#include "ipa-fnsummary.h"
68
69/* Entry in the histogram. */
70
71struct histogram_entry
72{
73 gcov_type count;
74 int time;
75 int size;
76};
77
78/* Histogram of profile values.
79 The histogram is represented as an ordered vector of entries allocated via
80 histogram_pool. During construction a separate hashtable is kept to lookup
81 duplicate entries. */
82
83vec<histogram_entry *> histogram;
84static object_allocator<histogram_entry> histogram_pool ("IPA histogram");
85
86/* Hashtable support for storing SSA names hashed by their SSA_NAME_VAR. */
87
88struct histogram_hash : nofree_ptr_hash <histogram_entry>
89{
90 static inline hashval_t hash (const histogram_entry *);
91 static inline int equal (const histogram_entry *, const histogram_entry *);
92};
93
94inline hashval_t
95histogram_hash::hash (const histogram_entry *val)
96{
97 return val->count;
98}
99
100inline int
101histogram_hash::equal (const histogram_entry *val, const histogram_entry *val2)
102{
103 return val->count == val2->count;
104}
105
106/* Account TIME and SIZE executed COUNT times into HISTOGRAM.
107 HASHTABLE is the on-side hash kept to avoid duplicates. */
108
109static void
110account_time_size (hash_table<histogram_hash> *hashtable,
111 vec<histogram_entry *> &histogram,
112 gcov_type count, int time, int size)
113{
114 histogram_entry key = {count, 0, 0};
115 histogram_entry **val = hashtable->find_slot (&key, INSERT);
116
117 if (!*val)
118 {
119 *val = histogram_pool.allocate ();
120 **val = key;
121 histogram.safe_push (*val);
122 }
123 (*val)->time += time;
124 (*val)->size += size;
125}
126
127int
128cmp_counts (const void *v1, const void *v2)
129{
130 const histogram_entry *h1 = *(const histogram_entry * const *)v1;
131 const histogram_entry *h2 = *(const histogram_entry * const *)v2;
132 if (h1->count < h2->count)
133 return 1;
134 if (h1->count > h2->count)
135 return -1;
136 return 0;
137}
138
139/* Dump HISTOGRAM to FILE. */
140
141static void
142dump_histogram (FILE *file, vec<histogram_entry *> histogram)
143{
144 unsigned int i;
145 gcov_type overall_time = 0, cumulated_time = 0, cumulated_size = 0, overall_size = 0;
146
147 fprintf (dump_file, "Histogram:\n");
148 for (i = 0; i < histogram.length (); i++)
149 {
150 overall_time += histogram[i]->count * histogram[i]->time;
151 overall_size += histogram[i]->size;
152 }
153 if (!overall_time)
154 overall_time = 1;
155 if (!overall_size)
156 overall_size = 1;
157 for (i = 0; i < histogram.length (); i++)
158 {
159 cumulated_time += histogram[i]->count * histogram[i]->time;
160 cumulated_size += histogram[i]->size;
161 fprintf (file, " %" PRId64": time:%i (%2.2f) size:%i (%2.2f)\n",
162 (int64_t) histogram[i]->count,
163 histogram[i]->time,
164 cumulated_time * 100.0 / overall_time,
165 histogram[i]->size,
166 cumulated_size * 100.0 / overall_size);
167 }
168}
169
170/* Collect histogram from CFG profiles. */
171
172static void
173ipa_profile_generate_summary (void)
174{
175 struct cgraph_node *node;
176 gimple_stmt_iterator gsi;
177 basic_block bb;
178
179 hash_table<histogram_hash> hashtable (10);
180
181 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
182 if (ENTRY_BLOCK_PTR_FOR_FN (DECL_STRUCT_FUNCTION (node->decl))->count.ipa_p ())
183 FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
184 {
185 int time = 0;
186 int size = 0;
187 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
188 {
189 gimple *stmt = gsi_stmt (gsi);
190 if (gimple_code (stmt) == GIMPLE_CALL
191 && !gimple_call_fndecl (stmt))
192 {
193 histogram_value h;
194 h = gimple_histogram_value_of_type
195 (DECL_STRUCT_FUNCTION (node->decl),
196 stmt, HIST_TYPE_INDIR_CALL);
197 /* No need to do sanity check: gimple_ic_transform already
198 takes away bad histograms. */
199 if (h)
200 {
201 /* counter 0 is target, counter 1 is number of execution we called target,
202 counter 2 is total number of executions. */
203 if (h->hvalue.counters[2])
204 {
205 struct cgraph_edge * e = node->get_edge (stmt);
206 if (e && !e->indirect_unknown_callee)
207 continue;
208 e->indirect_info->common_target_id
209 = h->hvalue.counters [0];
210 e->indirect_info->common_target_probability
211 = GCOV_COMPUTE_SCALE (h->hvalue.counters [1], h->hvalue.counters [2]);
212 if (e->indirect_info->common_target_probability > REG_BR_PROB_BASE)
213 {
214 if (dump_file)
215 fprintf (dump_file, "Probability capped to 1\n");
216 e->indirect_info->common_target_probability = REG_BR_PROB_BASE;
217 }
218 }
219 gimple_remove_histogram_value (DECL_STRUCT_FUNCTION (node->decl),
220 stmt, h);
221 }
222 }
223 time += estimate_num_insns (stmt, &eni_time_weights);
224 size += estimate_num_insns (stmt, &eni_size_weights);
225 }
226 if (bb->count.ipa_p () && bb->count.initialized_p ())
227 account_time_size (&hashtable, histogram, bb->count.ipa ().to_gcov_type (),
228 time, size);
229 }
230 histogram.qsort (cmp_counts);
231}
232
233/* Serialize the ipa info for lto. */
234
235static void
236ipa_profile_write_summary (void)
237{
238 struct lto_simple_output_block *ob
239 = lto_create_simple_output_block (LTO_section_ipa_profile);
240 unsigned int i;
241
242 streamer_write_uhwi_stream (ob->main_stream, histogram.length ());
243 for (i = 0; i < histogram.length (); i++)
244 {
245 streamer_write_gcov_count_stream (ob->main_stream, histogram[i]->count);
246 streamer_write_uhwi_stream (ob->main_stream, histogram[i]->time);
247 streamer_write_uhwi_stream (ob->main_stream, histogram[i]->size);
248 }
249 lto_destroy_simple_output_block (ob);
250}
251
252/* Deserialize the ipa info for lto. */
253
254static void
255ipa_profile_read_summary (void)
256{
257 struct lto_file_decl_data ** file_data_vec
258 = lto_get_file_decl_data ();
259 struct lto_file_decl_data * file_data;
260 int j = 0;
261
262 hash_table<histogram_hash> hashtable (10);
263
264 while ((file_data = file_data_vec[j++]))
265 {
266 const char *data;
267 size_t len;
268 struct lto_input_block *ib
269 = lto_create_simple_input_block (file_data,
270 LTO_section_ipa_profile,
271 &data, &len);
272 if (ib)
273 {
274 unsigned int num = streamer_read_uhwi (ib);
275 unsigned int n;
276 for (n = 0; n < num; n++)
277 {
278 gcov_type count = streamer_read_gcov_count (ib);
279 int time = streamer_read_uhwi (ib);
280 int size = streamer_read_uhwi (ib);
281 account_time_size (&hashtable, histogram,
282 count, time, size);
283 }
284 lto_destroy_simple_input_block (file_data,
285 LTO_section_ipa_profile,
286 ib, data, len);
287 }
288 }
289 histogram.qsort (cmp_counts);
290}
291
292/* Data used by ipa_propagate_frequency. */
293
294struct ipa_propagate_frequency_data
295{
296 cgraph_node *function_symbol;
297 bool maybe_unlikely_executed;
298 bool maybe_executed_once;
299 bool only_called_at_startup;
300 bool only_called_at_exit;
301};
302
303/* Worker for ipa_propagate_frequency_1. */
304
305static bool
306ipa_propagate_frequency_1 (struct cgraph_node *node, void *data)
307{
308 struct ipa_propagate_frequency_data *d;
309 struct cgraph_edge *edge;
310
311 d = (struct ipa_propagate_frequency_data *)data;
312 for (edge = node->callers;
313 edge && (d->maybe_unlikely_executed || d->maybe_executed_once
314 || d->only_called_at_startup || d->only_called_at_exit);
315 edge = edge->next_caller)
316 {
317 if (edge->caller != d->function_symbol)
318 {
319 d->only_called_at_startup &= edge->caller->only_called_at_startup;
320 /* It makes sense to put main() together with the static constructors.
321 It will be executed for sure, but rest of functions called from
322 main are definitely not at startup only. */
323 if (MAIN_NAME_P (DECL_NAME (edge->caller->decl)))
324 d->only_called_at_startup = 0;
325 d->only_called_at_exit &= edge->caller->only_called_at_exit;
326 }
327
328 /* When profile feedback is available, do not try to propagate too hard;
329 counts are already good guide on function frequencies and roundoff
330 errors can make us to push function into unlikely section even when
331 it is executed by the train run. Transfer the function only if all
332 callers are unlikely executed. */
333 if (profile_info
334 && edge->callee->count.initialized_p ()
335 /* Thunks are not profiled. This is more or less implementation
336 bug. */
337 && !d->function_symbol->thunk.thunk_p
338 && (edge->caller->frequency != NODE_FREQUENCY_UNLIKELY_EXECUTED
339 || (edge->caller->global.inlined_to
340 && edge->caller->global.inlined_to->frequency
341 != NODE_FREQUENCY_UNLIKELY_EXECUTED)))
342 d->maybe_unlikely_executed = false;
343 if (edge->count.initialized_p () && !edge->count.nonzero_p ())
344 continue;
345 switch (edge->caller->frequency)
346 {
347 case NODE_FREQUENCY_UNLIKELY_EXECUTED:
348 break;
349 case NODE_FREQUENCY_EXECUTED_ONCE:
350 if (dump_file && (dump_flags & TDF_DETAILS))
351 fprintf (dump_file, " Called by %s that is executed once\n",
352 edge->caller->name ());
353 d->maybe_unlikely_executed = false;
354 if (ipa_call_summaries->get (edge)->loop_depth)
355 {
356 d->maybe_executed_once = false;
357 if (dump_file && (dump_flags & TDF_DETAILS))
358 fprintf (dump_file, " Called in loop\n");
359 }
360 break;
361 case NODE_FREQUENCY_HOT:
362 case NODE_FREQUENCY_NORMAL:
363 if (dump_file && (dump_flags & TDF_DETAILS))
364 fprintf (dump_file, " Called by %s that is normal or hot\n",
365 edge->caller->name ());
366 d->maybe_unlikely_executed = false;
367 d->maybe_executed_once = false;
368 break;
369 }
370 }
371 return edge != NULL;
372}
373
374/* Return ture if NODE contains hot calls. */
375
376bool
377contains_hot_call_p (struct cgraph_node *node)
378{
379 struct cgraph_edge *e;
380 for (e = node->callees; e; e = e->next_callee)
381 if (e->maybe_hot_p ())
382 return true;
383 else if (!e->inline_failed
384 && contains_hot_call_p (e->callee))
385 return true;
386 for (e = node->indirect_calls; e; e = e->next_callee)
387 if (e->maybe_hot_p ())
388 return true;
389 return false;
390}
391
392/* See if the frequency of NODE can be updated based on frequencies of its
393 callers. */
394bool
395ipa_propagate_frequency (struct cgraph_node *node)
396{
397 struct ipa_propagate_frequency_data d = {node, true, true, true, true};
398 bool changed = false;
399
400 /* We can not propagate anything useful about externally visible functions
401 nor about virtuals. */
402 if (!node->local.local
403 || node->alias
404 || (opt_for_fn (node->decl, flag_devirtualize)
405 && DECL_VIRTUAL_P (node->decl)))
406 return false;
407 gcc_assert (node->analyzed);
408 if (dump_file && (dump_flags & TDF_DETAILS))
409 fprintf (dump_file, "Processing frequency %s\n", node->name ());
410
411 node->call_for_symbol_and_aliases (ipa_propagate_frequency_1, &d,
412 true);
413
414 if ((d.only_called_at_startup && !d.only_called_at_exit)
415 && !node->only_called_at_startup)
416 {
417 node->only_called_at_startup = true;
418 if (dump_file)
419 fprintf (dump_file, "Node %s promoted to only called at startup.\n",
420 node->name ());
421 changed = true;
422 }
423 if ((d.only_called_at_exit && !d.only_called_at_startup)
424 && !node->only_called_at_exit)
425 {
426 node->only_called_at_exit = true;
427 if (dump_file)
428 fprintf (dump_file, "Node %s promoted to only called at exit.\n",
429 node->name ());
430 changed = true;
431 }
432
433 /* With profile we can decide on hot/normal based on count. */
434 if (node->count. ipa().initialized_p ())
435 {
436 bool hot = false;
437 if (!(node->count. ipa() == profile_count::zero ())
438 && node->count. ipa() >= get_hot_bb_threshold ())
439 hot = true;
440 if (!hot)
441 hot |= contains_hot_call_p (node);
442 if (hot)
443 {
444 if (node->frequency != NODE_FREQUENCY_HOT)
445 {
446 if (dump_file)
447 fprintf (dump_file, "Node %s promoted to hot.\n",
448 node->name ());
449 node->frequency = NODE_FREQUENCY_HOT;
450 return true;
451 }
452 return false;
453 }
454 else if (node->frequency == NODE_FREQUENCY_HOT)
455 {
456 if (dump_file)
457 fprintf (dump_file, "Node %s reduced to normal.\n",
458 node->name ());
459 node->frequency = NODE_FREQUENCY_NORMAL;
460 changed = true;
461 }
462 }
463 /* These come either from profile or user hints; never update them. */
464 if (node->frequency == NODE_FREQUENCY_HOT
465 || node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
466 return changed;
467 if (d.maybe_unlikely_executed)
468 {
469 node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
470 if (dump_file)
471 fprintf (dump_file, "Node %s promoted to unlikely executed.\n",
472 node->name ());
473 changed = true;
474 }
475 else if (d.maybe_executed_once && node->frequency != NODE_FREQUENCY_EXECUTED_ONCE)
476 {
477 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
478 if (dump_file)
479 fprintf (dump_file, "Node %s promoted to executed once.\n",
480 node->name ());
481 changed = true;
482 }
483 return changed;
484}
485
486/* Simple ipa profile pass propagating frequencies across the callgraph. */
487
488static unsigned int
489ipa_profile (void)
490{
491 struct cgraph_node **order;
492 struct cgraph_edge *e;
493 int order_pos;
494 bool something_changed = false;
495 int i;
496 gcov_type overall_time = 0, cutoff = 0, cumulated = 0, overall_size = 0;
497 struct cgraph_node *n,*n2;
498 int nindirect = 0, ncommon = 0, nunknown = 0, nuseless = 0, nconverted = 0;
499 int nmismatch = 0, nimpossible = 0;
500 bool node_map_initialized = false;
501
502 if (dump_file)
503 dump_histogram (dump_file, histogram);
504 for (i = 0; i < (int)histogram.length (); i++)
505 {
506 overall_time += histogram[i]->count * histogram[i]->time;
507 overall_size += histogram[i]->size;
508 }
509 if (overall_time)
510 {
511 gcov_type threshold;
512
513 gcc_assert (overall_size);
514 if (dump_file)
515 {
516 gcov_type min, cumulated_time = 0, cumulated_size = 0;
517
518 fprintf (dump_file, "Overall time: %" PRId64"\n",
519 (int64_t)overall_time);
520 min = get_hot_bb_threshold ();
521 for (i = 0; i < (int)histogram.length () && histogram[i]->count >= min;
522 i++)
523 {
524 cumulated_time += histogram[i]->count * histogram[i]->time;
525 cumulated_size += histogram[i]->size;
526 }
527 fprintf (dump_file, "GCOV min count: %" PRId64
528 " Time:%3.2f%% Size:%3.2f%%\n",
529 (int64_t)min,
530 cumulated_time * 100.0 / overall_time,
531 cumulated_size * 100.0 / overall_size);
532 }
533 cutoff = (overall_time * PARAM_VALUE (HOT_BB_COUNT_WS_PERMILLE) + 500) / 1000;
534 threshold = 0;
535 for (i = 0; cumulated < cutoff; i++)
536 {
537 cumulated += histogram[i]->count * histogram[i]->time;
538 threshold = histogram[i]->count;
539 }
540 if (!threshold)
541 threshold = 1;
542 if (dump_file)
543 {
544 gcov_type cumulated_time = 0, cumulated_size = 0;
545
546 for (i = 0;
547 i < (int)histogram.length () && histogram[i]->count >= threshold;
548 i++)
549 {
550 cumulated_time += histogram[i]->count * histogram[i]->time;
551 cumulated_size += histogram[i]->size;
552 }
553 fprintf (dump_file, "Determined min count: %" PRId64
554 " Time:%3.2f%% Size:%3.2f%%\n",
555 (int64_t)threshold,
556 cumulated_time * 100.0 / overall_time,
557 cumulated_size * 100.0 / overall_size);
558 }
559 if (threshold > get_hot_bb_threshold ()
560 || in_lto_p)
561 {
562 if (dump_file)
563 fprintf (dump_file, "Threshold updated.\n");
564 set_hot_bb_threshold (threshold);
565 }
566 }
567 histogram.release ();
568 histogram_pool.release ();
569
570 /* Produce speculative calls: we saved common traget from porfiling into
571 e->common_target_id. Now, at link time, we can look up corresponding
572 function node and produce speculative call. */
573
574 FOR_EACH_DEFINED_FUNCTION (n)
575 {
576 bool update = false;
577
578 if (!opt_for_fn (n->decl, flag_ipa_profile))
579 continue;
580
581 for (e = n->indirect_calls; e; e = e->next_callee)
582 {
583 if (n->count.initialized_p ())
584 nindirect++;
585 if (e->indirect_info->common_target_id)
586 {
587 if (!node_map_initialized)
588 init_node_map (false);
589 node_map_initialized = true;
590 ncommon++;
591 n2 = find_func_by_profile_id (e->indirect_info->common_target_id);
592 if (n2)
593 {
594 if (dump_file)
595 {
596 fprintf (dump_file, "Indirect call -> direct call from"
597 " other module %s => %s, prob %3.2f\n",
598 n->dump_name (),
599 n2->dump_name (),
600 e->indirect_info->common_target_probability
601 / (float)REG_BR_PROB_BASE);
602 }
603 if (e->indirect_info->common_target_probability
604 < REG_BR_PROB_BASE / 2)
605 {
606 nuseless++;
607 if (dump_file)
608 fprintf (dump_file,
609 "Not speculating: probability is too low.\n");
610 }
611 else if (!e->maybe_hot_p ())
612 {
613 nuseless++;
614 if (dump_file)
615 fprintf (dump_file,
616 "Not speculating: call is cold.\n");
617 }
618 else if (n2->get_availability () <= AVAIL_INTERPOSABLE
619 && n2->can_be_discarded_p ())
620 {
621 nuseless++;
622 if (dump_file)
623 fprintf (dump_file,
624 "Not speculating: target is overwritable "
625 "and can be discarded.\n");
626 }
627 else if (ipa_node_params_sum && ipa_edge_args_sum
628 && (!vec_safe_is_empty
629 (IPA_NODE_REF (n2)->descriptors))
630 && ipa_get_param_count (IPA_NODE_REF (n2))
631 != ipa_get_cs_argument_count (IPA_EDGE_REF (e))
632 && (ipa_get_param_count (IPA_NODE_REF (n2))
633 >= ipa_get_cs_argument_count (IPA_EDGE_REF (e))
634 || !stdarg_p (TREE_TYPE (n2->decl))))
635 {
636 nmismatch++;
637 if (dump_file)
638 fprintf (dump_file,
639 "Not speculating: "
640 "parameter count mistmatch\n");
641 }
642 else if (e->indirect_info->polymorphic
643 && !opt_for_fn (n->decl, flag_devirtualize)
644 && !possible_polymorphic_call_target_p (e, n2))
645 {
646 nimpossible++;
647 if (dump_file)
648 fprintf (dump_file,
649 "Not speculating: "
650 "function is not in the polymorphic "
651 "call target list\n");
652 }
653 else
654 {
655 /* Target may be overwritable, but profile says that
656 control flow goes to this particular implementation
657 of N2. Speculate on the local alias to allow inlining.
658 */
659 if (!n2->can_be_discarded_p ())
660 {
661 cgraph_node *alias;
662 alias = dyn_cast<cgraph_node *> (n2->noninterposable_alias ());
663 if (alias)
664 n2 = alias;
665 }
666 nconverted++;
667 e->make_speculative
668 (n2,
669 e->count.apply_probability
670 (e->indirect_info->common_target_probability));
671 update = true;
672 }
673 }
674 else
675 {
676 if (dump_file)
677 fprintf (dump_file, "Function with profile-id %i not found.\n",
678 e->indirect_info->common_target_id);
679 nunknown++;
680 }
681 }
682 }
683 if (update)
684 ipa_update_overall_fn_summary (n);
685 }
686 if (node_map_initialized)
687 del_node_map ();
688 if (dump_file && nindirect)
689 fprintf (dump_file,
690 "%i indirect calls trained.\n"
691 "%i (%3.2f%%) have common target.\n"
692 "%i (%3.2f%%) targets was not found.\n"
693 "%i (%3.2f%%) targets had parameter count mismatch.\n"
694 "%i (%3.2f%%) targets was not in polymorphic call target list.\n"
695 "%i (%3.2f%%) speculations seems useless.\n"
696 "%i (%3.2f%%) speculations produced.\n",
697 nindirect,
698 ncommon, ncommon * 100.0 / nindirect,
699 nunknown, nunknown * 100.0 / nindirect,
700 nmismatch, nmismatch * 100.0 / nindirect,
701 nimpossible, nimpossible * 100.0 / nindirect,
702 nuseless, nuseless * 100.0 / nindirect,
703 nconverted, nconverted * 100.0 / nindirect);
704
705 order = XCNEWVEC (struct cgraph_node *, symtab->cgraph_count);
706 order_pos = ipa_reverse_postorder (order);
707 for (i = order_pos - 1; i >= 0; i--)
708 {
709 if (order[i]->local.local
710 && opt_for_fn (order[i]->decl, flag_ipa_profile)
711 && ipa_propagate_frequency (order[i]))
712 {
713 for (e = order[i]->callees; e; e = e->next_callee)
714 if (e->callee->local.local && !e->callee->aux)
715 {
716 something_changed = true;
717 e->callee->aux = (void *)1;
718 }
719 }
720 order[i]->aux = NULL;
721 }
722
723 while (something_changed)
724 {
725 something_changed = false;
726 for (i = order_pos - 1; i >= 0; i--)
727 {
728 if (order[i]->aux
729 && opt_for_fn (order[i]->decl, flag_ipa_profile)
730 && ipa_propagate_frequency (order[i]))
731 {
732 for (e = order[i]->callees; e; e = e->next_callee)
733 if (e->callee->local.local && !e->callee->aux)
734 {
735 something_changed = true;
736 e->callee->aux = (void *)1;
737 }
738 }
739 order[i]->aux = NULL;
740 }
741 }
742 free (order);
743 return 0;
744}
745
746namespace {
747
748const pass_data pass_data_ipa_profile =
749{
750 IPA_PASS, /* type */
751 "profile_estimate", /* name */
752 OPTGROUP_NONE, /* optinfo_flags */
753 TV_IPA_PROFILE, /* tv_id */
754 0, /* properties_required */
755 0, /* properties_provided */
756 0, /* properties_destroyed */
757 0, /* todo_flags_start */
758 0, /* todo_flags_finish */
759};
760
761class pass_ipa_profile : public ipa_opt_pass_d
762{
763public:
764 pass_ipa_profile (gcc::context *ctxt)
765 : ipa_opt_pass_d (pass_data_ipa_profile, ctxt,
766 ipa_profile_generate_summary, /* generate_summary */
767 ipa_profile_write_summary, /* write_summary */
768 ipa_profile_read_summary, /* read_summary */
769 NULL, /* write_optimization_summary */
770 NULL, /* read_optimization_summary */
771 NULL, /* stmt_fixup */
772 0, /* function_transform_todo_flags_start */
773 NULL, /* function_transform */
774 NULL) /* variable_transform */
775 {}
776
777 /* opt_pass methods: */
778 virtual bool gate (function *) { return flag_ipa_profile || in_lto_p; }
779 virtual unsigned int execute (function *) { return ipa_profile (); }
780
781}; // class pass_ipa_profile
782
783} // anon namespace
784
785ipa_opt_pass_d *
786make_pass_ipa_profile (gcc::context *ctxt)
787{
788 return new pass_ipa_profile (ctxt);
789}
790