|
111
|
1 /* Basic IPA optimizations based on profile.
|
|
|
2 Copyright (C) 2003-2017 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 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
|
|
|
71 struct 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
|
|
|
83 vec<histogram_entry *> histogram;
|
|
|
84 static object_allocator<histogram_entry> histogram_pool ("IPA histogram");
|
|
|
85
|
|
|
86 /* Hashtable support for storing SSA names hashed by their SSA_NAME_VAR. */
|
|
|
87
|
|
|
88 struct 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
|
|
|
94 inline hashval_t
|
|
|
95 histogram_hash::hash (const histogram_entry *val)
|
|
|
96 {
|
|
|
97 return val->count;
|
|
|
98 }
|
|
|
99
|
|
|
100 inline int
|
|
|
101 histogram_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
|
|
|
109 static void
|
|
|
110 account_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
|
|
|
127 int
|
|
|
128 cmp_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
|
|
|
141 static void
|
|
|
142 dump_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
|
|
|
172 static void
|
|
|
173 ipa_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 FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
|
|
|
183 {
|
|
|
184 int time = 0;
|
|
|
185 int size = 0;
|
|
|
186 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
187 {
|
|
|
188 gimple *stmt = gsi_stmt (gsi);
|
|
|
189 if (gimple_code (stmt) == GIMPLE_CALL
|
|
|
190 && !gimple_call_fndecl (stmt))
|
|
|
191 {
|
|
|
192 histogram_value h;
|
|
|
193 h = gimple_histogram_value_of_type
|
|
|
194 (DECL_STRUCT_FUNCTION (node->decl),
|
|
|
195 stmt, HIST_TYPE_INDIR_CALL);
|
|
|
196 /* No need to do sanity check: gimple_ic_transform already
|
|
|
197 takes away bad histograms. */
|
|
|
198 if (h)
|
|
|
199 {
|
|
|
200 /* counter 0 is target, counter 1 is number of execution we called target,
|
|
|
201 counter 2 is total number of executions. */
|
|
|
202 if (h->hvalue.counters[2])
|
|
|
203 {
|
|
|
204 struct cgraph_edge * e = node->get_edge (stmt);
|
|
|
205 if (e && !e->indirect_unknown_callee)
|
|
|
206 continue;
|
|
|
207 e->indirect_info->common_target_id
|
|
|
208 = h->hvalue.counters [0];
|
|
|
209 e->indirect_info->common_target_probability
|
|
|
210 = GCOV_COMPUTE_SCALE (h->hvalue.counters [1], h->hvalue.counters [2]);
|
|
|
211 if (e->indirect_info->common_target_probability > REG_BR_PROB_BASE)
|
|
|
212 {
|
|
|
213 if (dump_file)
|
|
|
214 fprintf (dump_file, "Probability capped to 1\n");
|
|
|
215 e->indirect_info->common_target_probability = REG_BR_PROB_BASE;
|
|
|
216 }
|
|
|
217 }
|
|
|
218 gimple_remove_histogram_value (DECL_STRUCT_FUNCTION (node->decl),
|
|
|
219 stmt, h);
|
|
|
220 }
|
|
|
221 }
|
|
|
222 time += estimate_num_insns (stmt, &eni_time_weights);
|
|
|
223 size += estimate_num_insns (stmt, &eni_size_weights);
|
|
|
224 }
|
|
|
225 if (bb->count.initialized_p ())
|
|
|
226 account_time_size (&hashtable, histogram, bb->count.to_gcov_type (),
|
|
|
227 time, size);
|
|
|
228 }
|
|
|
229 histogram.qsort (cmp_counts);
|
|
|
230 }
|
|
|
231
|
|
|
232 /* Serialize the ipa info for lto. */
|
|
|
233
|
|
|
234 static void
|
|
|
235 ipa_profile_write_summary (void)
|
|
|
236 {
|
|
|
237 struct lto_simple_output_block *ob
|
|
|
238 = lto_create_simple_output_block (LTO_section_ipa_profile);
|
|
|
239 unsigned int i;
|
|
|
240
|
|
|
241 streamer_write_uhwi_stream (ob->main_stream, histogram.length ());
|
|
|
242 for (i = 0; i < histogram.length (); i++)
|
|
|
243 {
|
|
|
244 streamer_write_gcov_count_stream (ob->main_stream, histogram[i]->count);
|
|
|
245 streamer_write_uhwi_stream (ob->main_stream, histogram[i]->time);
|
|
|
246 streamer_write_uhwi_stream (ob->main_stream, histogram[i]->size);
|
|
|
247 }
|
|
|
248 lto_destroy_simple_output_block (ob);
|
|
|
249 }
|
|
|
250
|
|
|
251 /* Deserialize the ipa info for lto. */
|
|
|
252
|
|
|
253 static void
|
|
|
254 ipa_profile_read_summary (void)
|
|
|
255 {
|
|
|
256 struct lto_file_decl_data ** file_data_vec
|
|
|
257 = lto_get_file_decl_data ();
|
|
|
258 struct lto_file_decl_data * file_data;
|
|
|
259 int j = 0;
|
|
|
260
|
|
|
261 hash_table<histogram_hash> hashtable (10);
|
|
|
262
|
|
|
263 while ((file_data = file_data_vec[j++]))
|
|
|
264 {
|
|
|
265 const char *data;
|
|
|
266 size_t len;
|
|
|
267 struct lto_input_block *ib
|
|
|
268 = lto_create_simple_input_block (file_data,
|
|
|
269 LTO_section_ipa_profile,
|
|
|
270 &data, &len);
|
|
|
271 if (ib)
|
|
|
272 {
|
|
|
273 unsigned int num = streamer_read_uhwi (ib);
|
|
|
274 unsigned int n;
|
|
|
275 for (n = 0; n < num; n++)
|
|
|
276 {
|
|
|
277 gcov_type count = streamer_read_gcov_count (ib);
|
|
|
278 int time = streamer_read_uhwi (ib);
|
|
|
279 int size = streamer_read_uhwi (ib);
|
|
|
280 account_time_size (&hashtable, histogram,
|
|
|
281 count, time, size);
|
|
|
282 }
|
|
|
283 lto_destroy_simple_input_block (file_data,
|
|
|
284 LTO_section_ipa_profile,
|
|
|
285 ib, data, len);
|
|
|
286 }
|
|
|
287 }
|
|
|
288 histogram.qsort (cmp_counts);
|
|
|
289 }
|
|
|
290
|
|
|
291 /* Data used by ipa_propagate_frequency. */
|
|
|
292
|
|
|
293 struct ipa_propagate_frequency_data
|
|
|
294 {
|
|
|
295 cgraph_node *function_symbol;
|
|
|
296 bool maybe_unlikely_executed;
|
|
|
297 bool maybe_executed_once;
|
|
|
298 bool only_called_at_startup;
|
|
|
299 bool only_called_at_exit;
|
|
|
300 };
|
|
|
301
|
|
|
302 /* Worker for ipa_propagate_frequency_1. */
|
|
|
303
|
|
|
304 static bool
|
|
|
305 ipa_propagate_frequency_1 (struct cgraph_node *node, void *data)
|
|
|
306 {
|
|
|
307 struct ipa_propagate_frequency_data *d;
|
|
|
308 struct cgraph_edge *edge;
|
|
|
309
|
|
|
310 d = (struct ipa_propagate_frequency_data *)data;
|
|
|
311 for (edge = node->callers;
|
|
|
312 edge && (d->maybe_unlikely_executed || d->maybe_executed_once
|
|
|
313 || d->only_called_at_startup || d->only_called_at_exit);
|
|
|
314 edge = edge->next_caller)
|
|
|
315 {
|
|
|
316 if (edge->caller != d->function_symbol)
|
|
|
317 {
|
|
|
318 d->only_called_at_startup &= edge->caller->only_called_at_startup;
|
|
|
319 /* It makes sense to put main() together with the static constructors.
|
|
|
320 It will be executed for sure, but rest of functions called from
|
|
|
321 main are definitely not at startup only. */
|
|
|
322 if (MAIN_NAME_P (DECL_NAME (edge->caller->decl)))
|
|
|
323 d->only_called_at_startup = 0;
|
|
|
324 d->only_called_at_exit &= edge->caller->only_called_at_exit;
|
|
|
325 }
|
|
|
326
|
|
|
327 /* When profile feedback is available, do not try to propagate too hard;
|
|
|
328 counts are already good guide on function frequencies and roundoff
|
|
|
329 errors can make us to push function into unlikely section even when
|
|
|
330 it is executed by the train run. Transfer the function only if all
|
|
|
331 callers are unlikely executed. */
|
|
|
332 if (profile_info
|
|
|
333 && edge->callee->count.initialized_p ()
|
|
|
334 /* Thunks are not profiled. This is more or less implementation
|
|
|
335 bug. */
|
|
|
336 && !d->function_symbol->thunk.thunk_p
|
|
|
337 && (edge->caller->frequency != NODE_FREQUENCY_UNLIKELY_EXECUTED
|
|
|
338 || (edge->caller->global.inlined_to
|
|
|
339 && edge->caller->global.inlined_to->frequency
|
|
|
340 != NODE_FREQUENCY_UNLIKELY_EXECUTED)))
|
|
|
341 d->maybe_unlikely_executed = false;
|
|
|
342 if (!edge->frequency)
|
|
|
343 continue;
|
|
|
344 switch (edge->caller->frequency)
|
|
|
345 {
|
|
|
346 case NODE_FREQUENCY_UNLIKELY_EXECUTED:
|
|
|
347 break;
|
|
|
348 case NODE_FREQUENCY_EXECUTED_ONCE:
|
|
|
349 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
350 fprintf (dump_file, " Called by %s that is executed once\n",
|
|
|
351 edge->caller->name ());
|
|
|
352 d->maybe_unlikely_executed = false;
|
|
|
353 if (ipa_call_summaries->get (edge)->loop_depth)
|
|
|
354 {
|
|
|
355 d->maybe_executed_once = false;
|
|
|
356 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
357 fprintf (dump_file, " Called in loop\n");
|
|
|
358 }
|
|
|
359 break;
|
|
|
360 case NODE_FREQUENCY_HOT:
|
|
|
361 case NODE_FREQUENCY_NORMAL:
|
|
|
362 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
363 fprintf (dump_file, " Called by %s that is normal or hot\n",
|
|
|
364 edge->caller->name ());
|
|
|
365 d->maybe_unlikely_executed = false;
|
|
|
366 d->maybe_executed_once = false;
|
|
|
367 break;
|
|
|
368 }
|
|
|
369 }
|
|
|
370 return edge != NULL;
|
|
|
371 }
|
|
|
372
|
|
|
373 /* Return ture if NODE contains hot calls. */
|
|
|
374
|
|
|
375 bool
|
|
|
376 contains_hot_call_p (struct cgraph_node *node)
|
|
|
377 {
|
|
|
378 struct cgraph_edge *e;
|
|
|
379 for (e = node->callees; e; e = e->next_callee)
|
|
|
380 if (e->maybe_hot_p ())
|
|
|
381 return true;
|
|
|
382 else if (!e->inline_failed
|
|
|
383 && contains_hot_call_p (e->callee))
|
|
|
384 return true;
|
|
|
385 for (e = node->indirect_calls; e; e = e->next_callee)
|
|
|
386 if (e->maybe_hot_p ())
|
|
|
387 return true;
|
|
|
388 return false;
|
|
|
389 }
|
|
|
390
|
|
|
391 /* See if the frequency of NODE can be updated based on frequencies of its
|
|
|
392 callers. */
|
|
|
393 bool
|
|
|
394 ipa_propagate_frequency (struct cgraph_node *node)
|
|
|
395 {
|
|
|
396 struct ipa_propagate_frequency_data d = {node, true, true, true, true};
|
|
|
397 bool changed = false;
|
|
|
398
|
|
|
399 /* We can not propagate anything useful about externally visible functions
|
|
|
400 nor about virtuals. */
|
|
|
401 if (!node->local.local
|
|
|
402 || node->alias
|
|
|
403 || (opt_for_fn (node->decl, flag_devirtualize)
|
|
|
404 && DECL_VIRTUAL_P (node->decl)))
|
|
|
405 return false;
|
|
|
406 gcc_assert (node->analyzed);
|
|
|
407 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
408 fprintf (dump_file, "Processing frequency %s\n", node->name ());
|
|
|
409
|
|
|
410 node->call_for_symbol_and_aliases (ipa_propagate_frequency_1, &d,
|
|
|
411 true);
|
|
|
412
|
|
|
413 if ((d.only_called_at_startup && !d.only_called_at_exit)
|
|
|
414 && !node->only_called_at_startup)
|
|
|
415 {
|
|
|
416 node->only_called_at_startup = true;
|
|
|
417 if (dump_file)
|
|
|
418 fprintf (dump_file, "Node %s promoted to only called at startup.\n",
|
|
|
419 node->name ());
|
|
|
420 changed = true;
|
|
|
421 }
|
|
|
422 if ((d.only_called_at_exit && !d.only_called_at_startup)
|
|
|
423 && !node->only_called_at_exit)
|
|
|
424 {
|
|
|
425 node->only_called_at_exit = true;
|
|
|
426 if (dump_file)
|
|
|
427 fprintf (dump_file, "Node %s promoted to only called at exit.\n",
|
|
|
428 node->name ());
|
|
|
429 changed = true;
|
|
|
430 }
|
|
|
431
|
|
|
432 /* With profile we can decide on hot/normal based on count. */
|
|
|
433 if (node->count.initialized_p ())
|
|
|
434 {
|
|
|
435 bool hot = false;
|
|
|
436 if (!(node->count == profile_count::zero ())
|
|
|
437 && node->count >= get_hot_bb_threshold ())
|
|
|
438 hot = true;
|
|
|
439 if (!hot)
|
|
|
440 hot |= contains_hot_call_p (node);
|
|
|
441 if (hot)
|
|
|
442 {
|
|
|
443 if (node->frequency != NODE_FREQUENCY_HOT)
|
|
|
444 {
|
|
|
445 if (dump_file)
|
|
|
446 fprintf (dump_file, "Node %s promoted to hot.\n",
|
|
|
447 node->name ());
|
|
|
448 node->frequency = NODE_FREQUENCY_HOT;
|
|
|
449 return true;
|
|
|
450 }
|
|
|
451 return false;
|
|
|
452 }
|
|
|
453 else if (node->frequency == NODE_FREQUENCY_HOT)
|
|
|
454 {
|
|
|
455 if (dump_file)
|
|
|
456 fprintf (dump_file, "Node %s reduced to normal.\n",
|
|
|
457 node->name ());
|
|
|
458 node->frequency = NODE_FREQUENCY_NORMAL;
|
|
|
459 changed = true;
|
|
|
460 }
|
|
|
461 }
|
|
|
462 /* These come either from profile or user hints; never update them. */
|
|
|
463 if (node->frequency == NODE_FREQUENCY_HOT
|
|
|
464 || node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
|
|
|
465 return changed;
|
|
|
466 if (d.maybe_unlikely_executed)
|
|
|
467 {
|
|
|
468 node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
|
|
|
469 if (dump_file)
|
|
|
470 fprintf (dump_file, "Node %s promoted to unlikely executed.\n",
|
|
|
471 node->name ());
|
|
|
472 changed = true;
|
|
|
473 }
|
|
|
474 else if (d.maybe_executed_once && node->frequency != NODE_FREQUENCY_EXECUTED_ONCE)
|
|
|
475 {
|
|
|
476 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
|
|
|
477 if (dump_file)
|
|
|
478 fprintf (dump_file, "Node %s promoted to executed once.\n",
|
|
|
479 node->name ());
|
|
|
480 changed = true;
|
|
|
481 }
|
|
|
482 return changed;
|
|
|
483 }
|
|
|
484
|
|
|
485 /* Simple ipa profile pass propagating frequencies across the callgraph. */
|
|
|
486
|
|
|
487 static unsigned int
|
|
|
488 ipa_profile (void)
|
|
|
489 {
|
|
|
490 struct cgraph_node **order;
|
|
|
491 struct cgraph_edge *e;
|
|
|
492 int order_pos;
|
|
|
493 bool something_changed = false;
|
|
|
494 int i;
|
|
|
495 gcov_type overall_time = 0, cutoff = 0, cumulated = 0, overall_size = 0;
|
|
|
496 struct cgraph_node *n,*n2;
|
|
|
497 int nindirect = 0, ncommon = 0, nunknown = 0, nuseless = 0, nconverted = 0;
|
|
|
498 int nmismatch = 0, nimpossible = 0;
|
|
|
499 bool node_map_initialized = false;
|
|
|
500
|
|
|
501 if (dump_file)
|
|
|
502 dump_histogram (dump_file, histogram);
|
|
|
503 for (i = 0; i < (int)histogram.length (); i++)
|
|
|
504 {
|
|
|
505 overall_time += histogram[i]->count * histogram[i]->time;
|
|
|
506 overall_size += histogram[i]->size;
|
|
|
507 }
|
|
|
508 if (overall_time)
|
|
|
509 {
|
|
|
510 gcov_type threshold;
|
|
|
511
|
|
|
512 gcc_assert (overall_size);
|
|
|
513 if (dump_file)
|
|
|
514 {
|
|
|
515 gcov_type min, cumulated_time = 0, cumulated_size = 0;
|
|
|
516
|
|
|
517 fprintf (dump_file, "Overall time: %" PRId64"\n",
|
|
|
518 (int64_t)overall_time);
|
|
|
519 min = get_hot_bb_threshold ();
|
|
|
520 for (i = 0; i < (int)histogram.length () && histogram[i]->count >= min;
|
|
|
521 i++)
|
|
|
522 {
|
|
|
523 cumulated_time += histogram[i]->count * histogram[i]->time;
|
|
|
524 cumulated_size += histogram[i]->size;
|
|
|
525 }
|
|
|
526 fprintf (dump_file, "GCOV min count: %" PRId64
|
|
|
527 " Time:%3.2f%% Size:%3.2f%%\n",
|
|
|
528 (int64_t)min,
|
|
|
529 cumulated_time * 100.0 / overall_time,
|
|
|
530 cumulated_size * 100.0 / overall_size);
|
|
|
531 }
|
|
|
532 cutoff = (overall_time * PARAM_VALUE (HOT_BB_COUNT_WS_PERMILLE) + 500) / 1000;
|
|
|
533 threshold = 0;
|
|
|
534 for (i = 0; cumulated < cutoff; i++)
|
|
|
535 {
|
|
|
536 cumulated += histogram[i]->count * histogram[i]->time;
|
|
|
537 threshold = histogram[i]->count;
|
|
|
538 }
|
|
|
539 if (!threshold)
|
|
|
540 threshold = 1;
|
|
|
541 if (dump_file)
|
|
|
542 {
|
|
|
543 gcov_type cumulated_time = 0, cumulated_size = 0;
|
|
|
544
|
|
|
545 for (i = 0;
|
|
|
546 i < (int)histogram.length () && histogram[i]->count >= threshold;
|
|
|
547 i++)
|
|
|
548 {
|
|
|
549 cumulated_time += histogram[i]->count * histogram[i]->time;
|
|
|
550 cumulated_size += histogram[i]->size;
|
|
|
551 }
|
|
|
552 fprintf (dump_file, "Determined min count: %" PRId64
|
|
|
553 " Time:%3.2f%% Size:%3.2f%%\n",
|
|
|
554 (int64_t)threshold,
|
|
|
555 cumulated_time * 100.0 / overall_time,
|
|
|
556 cumulated_size * 100.0 / overall_size);
|
|
|
557 }
|
|
|
558 if (threshold > get_hot_bb_threshold ()
|
|
|
559 || in_lto_p)
|
|
|
560 {
|
|
|
561 if (dump_file)
|
|
|
562 fprintf (dump_file, "Threshold updated.\n");
|
|
|
563 set_hot_bb_threshold (threshold);
|
|
|
564 }
|
|
|
565 }
|
|
|
566 histogram.release ();
|
|
|
567 histogram_pool.release ();
|
|
|
568
|
|
|
569 /* Produce speculative calls: we saved common traget from porfiling into
|
|
|
570 e->common_target_id. Now, at link time, we can look up corresponding
|
|
|
571 function node and produce speculative call. */
|
|
|
572
|
|
|
573 FOR_EACH_DEFINED_FUNCTION (n)
|
|
|
574 {
|
|
|
575 bool update = false;
|
|
|
576
|
|
|
577 if (!opt_for_fn (n->decl, flag_ipa_profile))
|
|
|
578 continue;
|
|
|
579
|
|
|
580 for (e = n->indirect_calls; e; e = e->next_callee)
|
|
|
581 {
|
|
|
582 if (n->count.initialized_p ())
|
|
|
583 nindirect++;
|
|
|
584 if (e->indirect_info->common_target_id)
|
|
|
585 {
|
|
|
586 if (!node_map_initialized)
|
|
|
587 init_node_map (false);
|
|
|
588 node_map_initialized = true;
|
|
|
589 ncommon++;
|
|
|
590 n2 = find_func_by_profile_id (e->indirect_info->common_target_id);
|
|
|
591 if (n2)
|
|
|
592 {
|
|
|
593 if (dump_file)
|
|
|
594 {
|
|
|
595 fprintf (dump_file, "Indirect call -> direct call from"
|
|
|
596 " other module %s => %s, prob %3.2f\n",
|
|
|
597 n->dump_name (),
|
|
|
598 n2->dump_name (),
|
|
|
599 e->indirect_info->common_target_probability
|
|
|
600 / (float)REG_BR_PROB_BASE);
|
|
|
601 }
|
|
|
602 if (e->indirect_info->common_target_probability
|
|
|
603 < REG_BR_PROB_BASE / 2)
|
|
|
604 {
|
|
|
605 nuseless++;
|
|
|
606 if (dump_file)
|
|
|
607 fprintf (dump_file,
|
|
|
608 "Not speculating: probability is too low.\n");
|
|
|
609 }
|
|
|
610 else if (!e->maybe_hot_p ())
|
|
|
611 {
|
|
|
612 nuseless++;
|
|
|
613 if (dump_file)
|
|
|
614 fprintf (dump_file,
|
|
|
615 "Not speculating: call is cold.\n");
|
|
|
616 }
|
|
|
617 else if (n2->get_availability () <= AVAIL_INTERPOSABLE
|
|
|
618 && n2->can_be_discarded_p ())
|
|
|
619 {
|
|
|
620 nuseless++;
|
|
|
621 if (dump_file)
|
|
|
622 fprintf (dump_file,
|
|
|
623 "Not speculating: target is overwritable "
|
|
|
624 "and can be discarded.\n");
|
|
|
625 }
|
|
|
626 else if (ipa_node_params_sum && ipa_edge_args_sum
|
|
|
627 && (!vec_safe_is_empty
|
|
|
628 (IPA_NODE_REF (n2)->descriptors))
|
|
|
629 && ipa_get_param_count (IPA_NODE_REF (n2))
|
|
|
630 != ipa_get_cs_argument_count (IPA_EDGE_REF (e))
|
|
|
631 && (ipa_get_param_count (IPA_NODE_REF (n2))
|
|
|
632 >= ipa_get_cs_argument_count (IPA_EDGE_REF (e))
|
|
|
633 || !stdarg_p (TREE_TYPE (n2->decl))))
|
|
|
634 {
|
|
|
635 nmismatch++;
|
|
|
636 if (dump_file)
|
|
|
637 fprintf (dump_file,
|
|
|
638 "Not speculating: "
|
|
|
639 "parameter count mistmatch\n");
|
|
|
640 }
|
|
|
641 else if (e->indirect_info->polymorphic
|
|
|
642 && !opt_for_fn (n->decl, flag_devirtualize)
|
|
|
643 && !possible_polymorphic_call_target_p (e, n2))
|
|
|
644 {
|
|
|
645 nimpossible++;
|
|
|
646 if (dump_file)
|
|
|
647 fprintf (dump_file,
|
|
|
648 "Not speculating: "
|
|
|
649 "function is not in the polymorphic "
|
|
|
650 "call target list\n");
|
|
|
651 }
|
|
|
652 else
|
|
|
653 {
|
|
|
654 /* Target may be overwritable, but profile says that
|
|
|
655 control flow goes to this particular implementation
|
|
|
656 of N2. Speculate on the local alias to allow inlining.
|
|
|
657 */
|
|
|
658 if (!n2->can_be_discarded_p ())
|
|
|
659 {
|
|
|
660 cgraph_node *alias;
|
|
|
661 alias = dyn_cast<cgraph_node *> (n2->noninterposable_alias ());
|
|
|
662 if (alias)
|
|
|
663 n2 = alias;
|
|
|
664 }
|
|
|
665 nconverted++;
|
|
|
666 e->make_speculative
|
|
|
667 (n2,
|
|
|
668 e->count.apply_probability
|
|
|
669 (e->indirect_info->common_target_probability),
|
|
|
670 apply_scale (e->frequency,
|
|
|
671 e->indirect_info->common_target_probability));
|
|
|
672 update = true;
|
|
|
673 }
|
|
|
674 }
|
|
|
675 else
|
|
|
676 {
|
|
|
677 if (dump_file)
|
|
|
678 fprintf (dump_file, "Function with profile-id %i not found.\n",
|
|
|
679 e->indirect_info->common_target_id);
|
|
|
680 nunknown++;
|
|
|
681 }
|
|
|
682 }
|
|
|
683 }
|
|
|
684 if (update)
|
|
|
685 ipa_update_overall_fn_summary (n);
|
|
|
686 }
|
|
|
687 if (node_map_initialized)
|
|
|
688 del_node_map ();
|
|
|
689 if (dump_file && nindirect)
|
|
|
690 fprintf (dump_file,
|
|
|
691 "%i indirect calls trained.\n"
|
|
|
692 "%i (%3.2f%%) have common target.\n"
|
|
|
693 "%i (%3.2f%%) targets was not found.\n"
|
|
|
694 "%i (%3.2f%%) targets had parameter count mismatch.\n"
|
|
|
695 "%i (%3.2f%%) targets was not in polymorphic call target list.\n"
|
|
|
696 "%i (%3.2f%%) speculations seems useless.\n"
|
|
|
697 "%i (%3.2f%%) speculations produced.\n",
|
|
|
698 nindirect,
|
|
|
699 ncommon, ncommon * 100.0 / nindirect,
|
|
|
700 nunknown, nunknown * 100.0 / nindirect,
|
|
|
701 nmismatch, nmismatch * 100.0 / nindirect,
|
|
|
702 nimpossible, nimpossible * 100.0 / nindirect,
|
|
|
703 nuseless, nuseless * 100.0 / nindirect,
|
|
|
704 nconverted, nconverted * 100.0 / nindirect);
|
|
|
705
|
|
|
706 order = XCNEWVEC (struct cgraph_node *, symtab->cgraph_count);
|
|
|
707 order_pos = ipa_reverse_postorder (order);
|
|
|
708 for (i = order_pos - 1; i >= 0; i--)
|
|
|
709 {
|
|
|
710 if (order[i]->local.local
|
|
|
711 && opt_for_fn (order[i]->decl, flag_ipa_profile)
|
|
|
712 && ipa_propagate_frequency (order[i]))
|
|
|
713 {
|
|
|
714 for (e = order[i]->callees; e; e = e->next_callee)
|
|
|
715 if (e->callee->local.local && !e->callee->aux)
|
|
|
716 {
|
|
|
717 something_changed = true;
|
|
|
718 e->callee->aux = (void *)1;
|
|
|
719 }
|
|
|
720 }
|
|
|
721 order[i]->aux = NULL;
|
|
|
722 }
|
|
|
723
|
|
|
724 while (something_changed)
|
|
|
725 {
|
|
|
726 something_changed = false;
|
|
|
727 for (i = order_pos - 1; i >= 0; i--)
|
|
|
728 {
|
|
|
729 if (order[i]->aux
|
|
|
730 && opt_for_fn (order[i]->decl, flag_ipa_profile)
|
|
|
731 && ipa_propagate_frequency (order[i]))
|
|
|
732 {
|
|
|
733 for (e = order[i]->callees; e; e = e->next_callee)
|
|
|
734 if (e->callee->local.local && !e->callee->aux)
|
|
|
735 {
|
|
|
736 something_changed = true;
|
|
|
737 e->callee->aux = (void *)1;
|
|
|
738 }
|
|
|
739 }
|
|
|
740 order[i]->aux = NULL;
|
|
|
741 }
|
|
|
742 }
|
|
|
743 free (order);
|
|
|
744 return 0;
|
|
|
745 }
|
|
|
746
|
|
|
747 namespace {
|
|
|
748
|
|
|
749 const pass_data pass_data_ipa_profile =
|
|
|
750 {
|
|
|
751 IPA_PASS, /* type */
|
|
|
752 "profile_estimate", /* name */
|
|
|
753 OPTGROUP_NONE, /* optinfo_flags */
|
|
|
754 TV_IPA_PROFILE, /* tv_id */
|
|
|
755 0, /* properties_required */
|
|
|
756 0, /* properties_provided */
|
|
|
757 0, /* properties_destroyed */
|
|
|
758 0, /* todo_flags_start */
|
|
|
759 0, /* todo_flags_finish */
|
|
|
760 };
|
|
|
761
|
|
|
762 class pass_ipa_profile : public ipa_opt_pass_d
|
|
|
763 {
|
|
|
764 public:
|
|
|
765 pass_ipa_profile (gcc::context *ctxt)
|
|
|
766 : ipa_opt_pass_d (pass_data_ipa_profile, ctxt,
|
|
|
767 ipa_profile_generate_summary, /* generate_summary */
|
|
|
768 ipa_profile_write_summary, /* write_summary */
|
|
|
769 ipa_profile_read_summary, /* read_summary */
|
|
|
770 NULL, /* write_optimization_summary */
|
|
|
771 NULL, /* read_optimization_summary */
|
|
|
772 NULL, /* stmt_fixup */
|
|
|
773 0, /* function_transform_todo_flags_start */
|
|
|
774 NULL, /* function_transform */
|
|
|
775 NULL) /* variable_transform */
|
|
|
776 {}
|
|
|
777
|
|
|
778 /* opt_pass methods: */
|
|
|
779 virtual bool gate (function *) { return flag_ipa_profile || in_lto_p; }
|
|
|
780 virtual unsigned int execute (function *) { return ipa_profile (); }
|
|
|
781
|
|
|
782 }; // class pass_ipa_profile
|
|
|
783
|
|
|
784 } // anon namespace
|
|
|
785
|
|
|
786 ipa_opt_pass_d *
|
|
|
787 make_pass_ipa_profile (gcc::context *ctxt)
|
|
|
788 {
|
|
|
789 return new pass_ipa_profile (ctxt);
|
|
|
790 }
|
