]>
Commit | Line | Data |
---|---|---|
3b22db66 | 1 | /* Interprocedural constant propagation |
3aea1f79 | 2 | Copyright (C) 2005-2014 Free Software Foundation, Inc. |
821d0e0f | 3 | |
4 | Contributed by Razya Ladelsky <RAZYA@il.ibm.com> and Martin Jambor | |
5 | <mjambor@suse.cz> | |
48e1416a | 6 | |
3b22db66 | 7 | This file is part of GCC. |
48e1416a | 8 | |
3b22db66 | 9 | GCC is free software; you can redistribute it and/or modify it under |
10 | the terms of the GNU General Public License as published by the Free | |
8c4c00c1 | 11 | Software Foundation; either version 3, or (at your option) any later |
3b22db66 | 12 | version. |
48e1416a | 13 | |
3b22db66 | 14 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY |
15 | WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
16 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
17 | for more details. | |
48e1416a | 18 | |
3b22db66 | 19 | You should have received a copy of the GNU General Public License |
8c4c00c1 | 20 | along with GCC; see the file COPYING3. If not see |
21 | <http://www.gnu.org/licenses/>. */ | |
3b22db66 | 22 | |
821d0e0f | 23 | /* Interprocedural constant propagation (IPA-CP). |
48e1416a | 24 | |
821d0e0f | 25 | The goal of this transformation is to |
d60eadfa | 26 | |
821d0e0f | 27 | 1) discover functions which are always invoked with some arguments with the |
28 | same known constant values and modify the functions so that the | |
29 | subsequent optimizations can take advantage of the knowledge, and | |
d60eadfa | 30 | |
821d0e0f | 31 | 2) partial specialization - create specialized versions of functions |
32 | transformed in this way if some parameters are known constants only in | |
33 | certain contexts but the estimated tradeoff between speedup and cost size | |
34 | is deemed good. | |
48e1416a | 35 | |
821d0e0f | 36 | The algorithm also propagates types and attempts to perform type based |
37 | devirtualization. Types are propagated much like constants. | |
48e1416a | 38 | |
821d0e0f | 39 | The algorithm basically consists of three stages. In the first, functions |
40 | are analyzed one at a time and jump functions are constructed for all known | |
41 | call-sites. In the second phase, the pass propagates information from the | |
42 | jump functions across the call to reveal what values are available at what | |
43 | call sites, performs estimations of effects of known values on functions and | |
44 | their callees, and finally decides what specialized extra versions should be | |
45 | created. In the third, the special versions materialize and appropriate | |
46 | calls are redirected. | |
d60eadfa | 47 | |
821d0e0f | 48 | The algorithm used is to a certain extent based on "Interprocedural Constant |
49 | Propagation", by David Callahan, Keith D Cooper, Ken Kennedy, Linda Torczon, | |
50 | Comp86, pg 152-161 and "A Methodology for Procedure Cloning" by Keith D | |
51 | Cooper, Mary W. Hall, and Ken Kennedy. | |
48e1416a | 52 | |
3b22db66 | 53 | |
54 | First stage - intraprocedural analysis | |
55 | ======================================= | |
821d0e0f | 56 | |
d60eadfa | 57 | This phase computes jump_function and modification flags. |
48e1416a | 58 | |
821d0e0f | 59 | A jump function for a call-site represents the values passed as an actual |
60 | arguments of a given call-site. In principle, there are three types of | |
61 | values: | |
62 | ||
63 | Pass through - the caller's formal parameter is passed as an actual | |
64 | argument, plus an operation on it can be performed. | |
85694bac | 65 | Constant - a constant is passed as an actual argument. |
3b22db66 | 66 | Unknown - neither of the above. |
48e1416a | 67 | |
821d0e0f | 68 | All jump function types are described in detail in ipa-prop.h, together with |
69 | the data structures that represent them and methods of accessing them. | |
48e1416a | 70 | |
821d0e0f | 71 | ipcp_generate_summary() is the main function of the first stage. |
3b22db66 | 72 | |
73 | Second stage - interprocedural analysis | |
74 | ======================================== | |
48e1416a | 75 | |
821d0e0f | 76 | This stage is itself divided into two phases. In the first, we propagate |
77 | known values over the call graph, in the second, we make cloning decisions. | |
78 | It uses a different algorithm than the original Callahan's paper. | |
48e1416a | 79 | |
821d0e0f | 80 | First, we traverse the functions topologically from callers to callees and, |
81 | for each strongly connected component (SCC), we propagate constants | |
82 | according to previously computed jump functions. We also record what known | |
83 | values depend on other known values and estimate local effects. Finally, we | |
9d75589a | 84 | propagate cumulative information about these effects from dependent values |
821d0e0f | 85 | to those on which they depend. |
3b22db66 | 86 | |
821d0e0f | 87 | Second, we again traverse the call graph in the same topological order and |
88 | make clones for functions which we know are called with the same values in | |
89 | all contexts and decide about extra specialized clones of functions just for | |
90 | some contexts - these decisions are based on both local estimates and | |
91 | cumulative estimates propagated from callees. | |
3b22db66 | 92 | |
821d0e0f | 93 | ipcp_propagate_stage() and ipcp_decision_stage() together constitute the |
94 | third stage. | |
95 | ||
96 | Third phase - materialization of clones, call statement updates. | |
3b22db66 | 97 | ============================================ |
821d0e0f | 98 | |
99 | This stage is currently performed by call graph code (mainly in cgraphunit.c | |
100 | and tree-inline.c) according to instructions inserted to the call graph by | |
101 | the second stage. */ | |
3b22db66 | 102 | |
103 | #include "config.h" | |
104 | #include "system.h" | |
105 | #include "coretypes.h" | |
106 | #include "tree.h" | |
bc61cadb | 107 | #include "gimple-fold.h" |
108 | #include "gimple-expr.h" | |
3b22db66 | 109 | #include "target.h" |
3b22db66 | 110 | #include "ipa-prop.h" |
073c1fd5 | 111 | #include "bitmap.h" |
3b22db66 | 112 | #include "tree-pass.h" |
113 | #include "flags.h" | |
3b22db66 | 114 | #include "diagnostic.h" |
ce084dfc | 115 | #include "tree-pretty-print.h" |
8624b7fc | 116 | #include "tree-inline.h" |
2a15795f | 117 | #include "params.h" |
c7b2cc59 | 118 | #include "ipa-inline.h" |
821d0e0f | 119 | #include "ipa-utils.h" |
3b22db66 | 120 | |
821d0e0f | 121 | struct ipcp_value; |
11b73810 | 122 | |
821d0e0f | 123 | /* Describes a particular source for an IPA-CP value. */ |
11b73810 | 124 | |
821d0e0f | 125 | struct ipcp_value_source |
126 | { | |
803a7988 | 127 | /* Aggregate offset of the source, negative if the source is scalar value of |
128 | the argument itself. */ | |
129 | HOST_WIDE_INT offset; | |
821d0e0f | 130 | /* The incoming edge that brought the value. */ |
131 | struct cgraph_edge *cs; | |
132 | /* If the jump function that resulted into his value was a pass-through or an | |
133 | ancestor, this is the ipcp_value of the caller from which the described | |
134 | value has been derived. Otherwise it is NULL. */ | |
135 | struct ipcp_value *val; | |
136 | /* Next pointer in a linked list of sources of a value. */ | |
137 | struct ipcp_value_source *next; | |
138 | /* If the jump function that resulted into his value was a pass-through or an | |
139 | ancestor, this is the index of the parameter of the caller the jump | |
140 | function references. */ | |
141 | int index; | |
142 | }; | |
11b73810 | 143 | |
821d0e0f | 144 | /* Describes one particular value stored in struct ipcp_lattice. */ |
11b73810 | 145 | |
821d0e0f | 146 | struct ipcp_value |
3b22db66 | 147 | { |
821d0e0f | 148 | /* The actual value for the given parameter. This is either an IPA invariant |
149 | or a TREE_BINFO describing a type that can be used for | |
150 | devirtualization. */ | |
151 | tree value; | |
152 | /* The list of sources from which this value originates. */ | |
153 | struct ipcp_value_source *sources; | |
154 | /* Next pointers in a linked list of all values in a lattice. */ | |
155 | struct ipcp_value *next; | |
156 | /* Next pointers in a linked list of values in a strongly connected component | |
157 | of values. */ | |
158 | struct ipcp_value *scc_next; | |
159 | /* Next pointers in a linked list of SCCs of values sorted topologically | |
160 | according their sources. */ | |
161 | struct ipcp_value *topo_next; | |
162 | /* A specialized node created for this value, NULL if none has been (so far) | |
163 | created. */ | |
164 | struct cgraph_node *spec_node; | |
165 | /* Depth first search number and low link for topological sorting of | |
166 | values. */ | |
167 | int dfs, low_link; | |
168 | /* Time benefit and size cost that specializing the function for this value | |
169 | would bring about in this function alone. */ | |
170 | int local_time_benefit, local_size_cost; | |
171 | /* Time benefit and size cost that specializing the function for this value | |
172 | can bring about in it's callees (transitively). */ | |
173 | int prop_time_benefit, prop_size_cost; | |
174 | /* True if this valye is currently on the topo-sort stack. */ | |
175 | bool on_stack; | |
176 | }; | |
3b22db66 | 177 | |
803a7988 | 178 | /* Lattice describing potential values of a formal parameter of a function, or |
179 | a part of an aggreagate. TOP is represented by a lattice with zero values | |
180 | and with contains_variable and bottom flags cleared. BOTTOM is represented | |
181 | by a lattice with the bottom flag set. In that case, values and | |
821d0e0f | 182 | contains_variable flag should be disregarded. */ |
183 | ||
184 | struct ipcp_lattice | |
3b22db66 | 185 | { |
821d0e0f | 186 | /* The list of known values and types in this lattice. Note that values are |
187 | not deallocated if a lattice is set to bottom because there may be value | |
188 | sources referencing them. */ | |
189 | struct ipcp_value *values; | |
190 | /* Number of known values and types in this lattice. */ | |
191 | int values_count; | |
803a7988 | 192 | /* The lattice contains a variable component (in addition to values). */ |
821d0e0f | 193 | bool contains_variable; |
194 | /* The value of the lattice is bottom (i.e. variable and unusable for any | |
195 | propagation). */ | |
196 | bool bottom; | |
803a7988 | 197 | }; |
198 | ||
199 | /* Lattice with an offset to describe a part of an aggregate. */ | |
200 | ||
201 | struct ipcp_agg_lattice : public ipcp_lattice | |
202 | { | |
203 | /* Offset that is being described by this lattice. */ | |
204 | HOST_WIDE_INT offset; | |
205 | /* Size so that we don't have to re-compute it every time we traverse the | |
206 | list. Must correspond to TYPE_SIZE of all lat values. */ | |
207 | HOST_WIDE_INT size; | |
208 | /* Next element of the linked list. */ | |
209 | struct ipcp_agg_lattice *next; | |
210 | }; | |
211 | ||
212 | /* Structure containing lattices for a parameter itself and for pieces of | |
213 | aggregates that are passed in the parameter or by a reference in a parameter | |
214 | plus some other useful flags. */ | |
215 | ||
216 | struct ipcp_param_lattices | |
217 | { | |
218 | /* Lattice describing the value of the parameter itself. */ | |
219 | struct ipcp_lattice itself; | |
220 | /* Lattices describing aggregate parts. */ | |
221 | struct ipcp_agg_lattice *aggs; | |
222 | /* Number of aggregate lattices */ | |
223 | int aggs_count; | |
224 | /* True if aggregate data were passed by reference (as opposed to by | |
225 | value). */ | |
226 | bool aggs_by_ref; | |
227 | /* All aggregate lattices contain a variable component (in addition to | |
228 | values). */ | |
229 | bool aggs_contain_variable; | |
230 | /* The value of all aggregate lattices is bottom (i.e. variable and unusable | |
231 | for any propagation). */ | |
232 | bool aggs_bottom; | |
233 | ||
821d0e0f | 234 | /* There is a virtual call based on this parameter. */ |
235 | bool virt_call; | |
236 | }; | |
3b22db66 | 237 | |
803a7988 | 238 | /* Allocation pools for values and their sources in ipa-cp. */ |
239 | ||
240 | alloc_pool ipcp_values_pool; | |
241 | alloc_pool ipcp_sources_pool; | |
242 | alloc_pool ipcp_agg_lattice_pool; | |
243 | ||
821d0e0f | 244 | /* Maximal count found in program. */ |
245 | ||
246 | static gcov_type max_count; | |
247 | ||
248 | /* Original overall size of the program. */ | |
249 | ||
250 | static long overall_size, max_new_size; | |
251 | ||
252 | /* Head of the linked list of topologically sorted values. */ | |
253 | ||
254 | static struct ipcp_value *values_topo; | |
255 | ||
803a7988 | 256 | /* Return the param lattices structure corresponding to the Ith formal |
257 | parameter of the function described by INFO. */ | |
258 | static inline struct ipcp_param_lattices * | |
259 | ipa_get_parm_lattices (struct ipa_node_params *info, int i) | |
3b22db66 | 260 | { |
03f99d3c | 261 | gcc_assert (i >= 0 && i < ipa_get_param_count (info)); |
821d0e0f | 262 | gcc_checking_assert (!info->ipcp_orig_node); |
263 | gcc_checking_assert (info->lattices); | |
264 | return &(info->lattices[i]); | |
3b22db66 | 265 | } |
266 | ||
803a7988 | 267 | /* Return the lattice corresponding to the scalar value of the Ith formal |
268 | parameter of the function described by INFO. */ | |
269 | static inline struct ipcp_lattice * | |
270 | ipa_get_scalar_lat (struct ipa_node_params *info, int i) | |
271 | { | |
272 | struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); | |
273 | return &plats->itself; | |
274 | } | |
275 | ||
821d0e0f | 276 | /* Return whether LAT is a lattice with a single constant and without an |
277 | undefined value. */ | |
278 | ||
d60eadfa | 279 | static inline bool |
821d0e0f | 280 | ipa_lat_is_single_const (struct ipcp_lattice *lat) |
3b22db66 | 281 | { |
821d0e0f | 282 | if (lat->bottom |
283 | || lat->contains_variable | |
284 | || lat->values_count != 1) | |
3b22db66 | 285 | return false; |
821d0e0f | 286 | else |
287 | return true; | |
3b22db66 | 288 | } |
289 | ||
821d0e0f | 290 | /* Print V which is extracted from a value in a lattice to F. */ |
291 | ||
3b22db66 | 292 | static void |
821d0e0f | 293 | print_ipcp_constant_value (FILE * f, tree v) |
3b22db66 | 294 | { |
821d0e0f | 295 | if (TREE_CODE (v) == TREE_BINFO) |
3b22db66 | 296 | { |
821d0e0f | 297 | fprintf (f, "BINFO "); |
298 | print_generic_expr (f, BINFO_TYPE (v), 0); | |
3b22db66 | 299 | } |
821d0e0f | 300 | else if (TREE_CODE (v) == ADDR_EXPR |
301 | && TREE_CODE (TREE_OPERAND (v, 0)) == CONST_DECL) | |
3b22db66 | 302 | { |
821d0e0f | 303 | fprintf (f, "& "); |
304 | print_generic_expr (f, DECL_INITIAL (TREE_OPERAND (v, 0)), 0); | |
3b22db66 | 305 | } |
821d0e0f | 306 | else |
307 | print_generic_expr (f, v, 0); | |
3b22db66 | 308 | } |
309 | ||
803a7988 | 310 | /* Print a lattice LAT to F. */ |
311 | ||
312 | static void | |
313 | print_lattice (FILE * f, struct ipcp_lattice *lat, | |
314 | bool dump_sources, bool dump_benefits) | |
315 | { | |
316 | struct ipcp_value *val; | |
317 | bool prev = false; | |
318 | ||
319 | if (lat->bottom) | |
320 | { | |
321 | fprintf (f, "BOTTOM\n"); | |
322 | return; | |
323 | } | |
324 | ||
325 | if (!lat->values_count && !lat->contains_variable) | |
326 | { | |
327 | fprintf (f, "TOP\n"); | |
328 | return; | |
329 | } | |
330 | ||
331 | if (lat->contains_variable) | |
332 | { | |
333 | fprintf (f, "VARIABLE"); | |
334 | prev = true; | |
335 | if (dump_benefits) | |
336 | fprintf (f, "\n"); | |
337 | } | |
338 | ||
339 | for (val = lat->values; val; val = val->next) | |
340 | { | |
341 | if (dump_benefits && prev) | |
342 | fprintf (f, " "); | |
343 | else if (!dump_benefits && prev) | |
344 | fprintf (f, ", "); | |
345 | else | |
346 | prev = true; | |
347 | ||
348 | print_ipcp_constant_value (f, val->value); | |
349 | ||
350 | if (dump_sources) | |
351 | { | |
352 | struct ipcp_value_source *s; | |
353 | ||
354 | fprintf (f, " [from:"); | |
355 | for (s = val->sources; s; s = s->next) | |
02774f2d | 356 | fprintf (f, " %i(%i)", s->cs->caller->order, |
15c999e3 | 357 | s->cs->frequency); |
803a7988 | 358 | fprintf (f, "]"); |
359 | } | |
360 | ||
361 | if (dump_benefits) | |
362 | fprintf (f, " [loc_time: %i, loc_size: %i, " | |
363 | "prop_time: %i, prop_size: %i]\n", | |
364 | val->local_time_benefit, val->local_size_cost, | |
365 | val->prop_time_benefit, val->prop_size_cost); | |
366 | } | |
367 | if (!dump_benefits) | |
368 | fprintf (f, "\n"); | |
369 | } | |
370 | ||
d60eadfa | 371 | /* Print all ipcp_lattices of all functions to F. */ |
821d0e0f | 372 | |
3b22db66 | 373 | static void |
821d0e0f | 374 | print_all_lattices (FILE * f, bool dump_sources, bool dump_benefits) |
3b22db66 | 375 | { |
376 | struct cgraph_node *node; | |
377 | int i, count; | |
8624b7fc | 378 | |
821d0e0f | 379 | fprintf (f, "\nLattices:\n"); |
380 | FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node) | |
3b22db66 | 381 | { |
86c96e3a | 382 | struct ipa_node_params *info; |
383 | ||
86c96e3a | 384 | info = IPA_NODE_REF (node); |
f1c8b4d7 | 385 | fprintf (f, " Node: %s/%i:\n", node->name (), |
02774f2d | 386 | node->order); |
d60eadfa | 387 | count = ipa_get_param_count (info); |
3b22db66 | 388 | for (i = 0; i < count; i++) |
389 | { | |
803a7988 | 390 | struct ipcp_agg_lattice *aglat; |
391 | struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); | |
11b73810 | 392 | fprintf (f, " param [%d]: ", i); |
803a7988 | 393 | print_lattice (f, &plats->itself, dump_sources, dump_benefits); |
821d0e0f | 394 | |
803a7988 | 395 | if (plats->virt_call) |
396 | fprintf (f, " virt_call flag set\n"); | |
397 | ||
398 | if (plats->aggs_bottom) | |
821d0e0f | 399 | { |
803a7988 | 400 | fprintf (f, " AGGS BOTTOM\n"); |
821d0e0f | 401 | continue; |
402 | } | |
803a7988 | 403 | if (plats->aggs_contain_variable) |
404 | fprintf (f, " AGGS VARIABLE\n"); | |
405 | for (aglat = plats->aggs; aglat; aglat = aglat->next) | |
821d0e0f | 406 | { |
803a7988 | 407 | fprintf (f, " %soffset " HOST_WIDE_INT_PRINT_DEC ": ", |
408 | plats->aggs_by_ref ? "ref " : "", aglat->offset); | |
409 | print_lattice (f, aglat, dump_sources, dump_benefits); | |
821d0e0f | 410 | } |
3b22db66 | 411 | } |
412 | } | |
413 | } | |
414 | ||
821d0e0f | 415 | /* Determine whether it is at all technically possible to create clones of NODE |
416 | and store this information in the ipa_node_params structure associated | |
417 | with NODE. */ | |
d747fdfb | 418 | |
821d0e0f | 419 | static void |
420 | determine_versionability (struct cgraph_node *node) | |
d747fdfb | 421 | { |
821d0e0f | 422 | const char *reason = NULL; |
eae7682a | 423 | |
77b05e95 | 424 | /* There are a number of generic reasons functions cannot be versioned. We |
425 | also cannot remove parameters if there are type attributes such as fnspec | |
426 | present. */ | |
02774f2d | 427 | if (node->alias || node->thunk.thunk_p) |
821d0e0f | 428 | reason = "alias or thunk"; |
c8d92fc1 | 429 | else if (!node->local.versionable) |
03f99d3c | 430 | reason = "not a tree_versionable_function"; |
821d0e0f | 431 | else if (cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE) |
432 | reason = "insufficient body availability"; | |
83167671 | 433 | else if (!opt_for_fn (node->decl, optimize) |
434 | || !opt_for_fn (node->decl, flag_ipa_cp)) | |
435 | reason = "non-optimized function"; | |
d09768a4 | 436 | else if (lookup_attribute ("omp declare simd", DECL_ATTRIBUTES (node->decl))) |
437 | { | |
438 | /* Ideally we should clone the SIMD clones themselves and create | |
439 | vector copies of them, so IPA-cp and SIMD clones can happily | |
440 | coexist, but that may not be worth the effort. */ | |
441 | reason = "function has SIMD clones"; | |
442 | } | |
468088ac | 443 | /* Don't clone decls local to a comdat group; it breaks and for C++ |
444 | decloned constructors, inlining is always better anyway. */ | |
445 | else if (symtab_comdat_local_p (node)) | |
446 | reason = "comdat-local function"; | |
d747fdfb | 447 | |
02774f2d | 448 | if (reason && dump_file && !node->alias && !node->thunk.thunk_p) |
821d0e0f | 449 | fprintf (dump_file, "Function %s/%i is not versionable, reason: %s.\n", |
f1c8b4d7 | 450 | node->name (), node->order, reason); |
d747fdfb | 451 | |
c8d92fc1 | 452 | node->local.versionable = (reason == NULL); |
d747fdfb | 453 | } |
454 | ||
821d0e0f | 455 | /* Return true if it is at all technically possible to create clones of a |
456 | NODE. */ | |
457 | ||
11b73810 | 458 | static bool |
821d0e0f | 459 | ipcp_versionable_function_p (struct cgraph_node *node) |
11b73810 | 460 | { |
c8d92fc1 | 461 | return node->local.versionable; |
821d0e0f | 462 | } |
11b73810 | 463 | |
821d0e0f | 464 | /* Structure holding accumulated information about callers of a node. */ |
4855a75d | 465 | |
821d0e0f | 466 | struct caller_statistics |
467 | { | |
468 | gcov_type count_sum; | |
469 | int n_calls, n_hot_calls, freq_sum; | |
470 | }; | |
11b73810 | 471 | |
821d0e0f | 472 | /* Initialize fields of STAT to zeroes. */ |
7f74ac6b | 473 | |
821d0e0f | 474 | static inline void |
475 | init_caller_stats (struct caller_statistics *stats) | |
476 | { | |
477 | stats->count_sum = 0; | |
478 | stats->n_calls = 0; | |
479 | stats->n_hot_calls = 0; | |
480 | stats->freq_sum = 0; | |
481 | } | |
482 | ||
483 | /* Worker callback of cgraph_for_node_and_aliases accumulating statistics of | |
484 | non-thunk incoming edges to NODE. */ | |
485 | ||
486 | static bool | |
487 | gather_caller_stats (struct cgraph_node *node, void *data) | |
488 | { | |
489 | struct caller_statistics *stats = (struct caller_statistics *) data; | |
490 | struct cgraph_edge *cs; | |
491 | ||
492 | for (cs = node->callers; cs; cs = cs->next_caller) | |
493 | if (cs->caller->thunk.thunk_p) | |
494 | cgraph_for_node_and_aliases (cs->caller, gather_caller_stats, | |
495 | stats, false); | |
496 | else | |
497 | { | |
498 | stats->count_sum += cs->count; | |
499 | stats->freq_sum += cs->frequency; | |
500 | stats->n_calls++; | |
501 | if (cgraph_maybe_hot_edge_p (cs)) | |
502 | stats->n_hot_calls ++; | |
503 | } | |
504 | return false; | |
505 | ||
506 | } | |
507 | ||
508 | /* Return true if this NODE is viable candidate for cloning. */ | |
509 | ||
510 | static bool | |
511 | ipcp_cloning_candidate_p (struct cgraph_node *node) | |
512 | { | |
513 | struct caller_statistics stats; | |
514 | ||
515 | gcc_checking_assert (cgraph_function_with_gimple_body_p (node)); | |
48e1416a | 516 | |
821d0e0f | 517 | if (!flag_ipa_cp_clone) |
11b73810 | 518 | { |
519 | if (dump_file) | |
821d0e0f | 520 | fprintf (dump_file, "Not considering %s for cloning; " |
521 | "-fipa-cp-clone disabled.\n", | |
f1c8b4d7 | 522 | node->name ()); |
11b73810 | 523 | return false; |
524 | } | |
11b73810 | 525 | |
02774f2d | 526 | if (!optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node->decl))) |
11b73810 | 527 | { |
528 | if (dump_file) | |
821d0e0f | 529 | fprintf (dump_file, "Not considering %s for cloning; " |
530 | "optimizing it for size.\n", | |
f1c8b4d7 | 531 | node->name ()); |
11b73810 | 532 | return false; |
533 | } | |
534 | ||
821d0e0f | 535 | init_caller_stats (&stats); |
536 | cgraph_for_node_and_aliases (node, gather_caller_stats, &stats, false); | |
537 | ||
538 | if (inline_summary (node)->self_size < stats.n_calls) | |
11b73810 | 539 | { |
540 | if (dump_file) | |
821d0e0f | 541 | fprintf (dump_file, "Considering %s for cloning; code might shrink.\n", |
f1c8b4d7 | 542 | node->name ()); |
821d0e0f | 543 | return true; |
11b73810 | 544 | } |
545 | ||
546 | /* When profile is available and function is hot, propagate into it even if | |
547 | calls seems cold; constant propagation can improve function's speed | |
0a10fd82 | 548 | significantly. */ |
11b73810 | 549 | if (max_count) |
550 | { | |
821d0e0f | 551 | if (stats.count_sum > node->count * 90 / 100) |
11b73810 | 552 | { |
553 | if (dump_file) | |
821d0e0f | 554 | fprintf (dump_file, "Considering %s for cloning; " |
555 | "usually called directly.\n", | |
f1c8b4d7 | 556 | node->name ()); |
11b73810 | 557 | return true; |
558 | } | |
559 | } | |
821d0e0f | 560 | if (!stats.n_hot_calls) |
11b73810 | 561 | { |
562 | if (dump_file) | |
563 | fprintf (dump_file, "Not considering %s for cloning; no hot calls.\n", | |
f1c8b4d7 | 564 | node->name ()); |
a111083a | 565 | return false; |
11b73810 | 566 | } |
567 | if (dump_file) | |
568 | fprintf (dump_file, "Considering %s for cloning.\n", | |
f1c8b4d7 | 569 | node->name ()); |
11b73810 | 570 | return true; |
571 | } | |
572 | ||
821d0e0f | 573 | /* Arrays representing a topological ordering of call graph nodes and a stack |
574 | of noes used during constant propagation. */ | |
1caef38b | 575 | |
821d0e0f | 576 | struct topo_info |
1caef38b | 577 | { |
821d0e0f | 578 | struct cgraph_node **order; |
579 | struct cgraph_node **stack; | |
580 | int nnodes, stack_top; | |
581 | }; | |
582 | ||
583 | /* Allocate the arrays in TOPO and topologically sort the nodes into order. */ | |
584 | ||
585 | static void | |
586 | build_toporder_info (struct topo_info *topo) | |
587 | { | |
588 | topo->order = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes); | |
589 | topo->stack = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes); | |
590 | topo->stack_top = 0; | |
591 | topo->nnodes = ipa_reduced_postorder (topo->order, true, true, NULL); | |
1caef38b | 592 | } |
593 | ||
821d0e0f | 594 | /* Free information about strongly connected components and the arrays in |
595 | TOPO. */ | |
596 | ||
3b22db66 | 597 | static void |
821d0e0f | 598 | free_toporder_info (struct topo_info *topo) |
599 | { | |
600 | ipa_free_postorder_info (); | |
601 | free (topo->order); | |
602 | free (topo->stack); | |
603 | } | |
604 | ||
605 | /* Add NODE to the stack in TOPO, unless it is already there. */ | |
606 | ||
607 | static inline void | |
608 | push_node_to_stack (struct topo_info *topo, struct cgraph_node *node) | |
3b22db66 | 609 | { |
d60eadfa | 610 | struct ipa_node_params *info = IPA_NODE_REF (node); |
821d0e0f | 611 | if (info->node_enqueued) |
612 | return; | |
613 | info->node_enqueued = 1; | |
614 | topo->stack[topo->stack_top++] = node; | |
615 | } | |
3b22db66 | 616 | |
821d0e0f | 617 | /* Pop a node from the stack in TOPO and return it or return NULL if the stack |
618 | is empty. */ | |
11b73810 | 619 | |
821d0e0f | 620 | static struct cgraph_node * |
621 | pop_node_from_stack (struct topo_info *topo) | |
622 | { | |
623 | if (topo->stack_top) | |
1caef38b | 624 | { |
821d0e0f | 625 | struct cgraph_node *node; |
626 | topo->stack_top--; | |
627 | node = topo->stack[topo->stack_top]; | |
628 | IPA_NODE_REF (node)->node_enqueued = 0; | |
629 | return node; | |
1caef38b | 630 | } |
821d0e0f | 631 | else |
632 | return NULL; | |
3b22db66 | 633 | } |
634 | ||
821d0e0f | 635 | /* Set lattice LAT to bottom and return true if it previously was not set as |
636 | such. */ | |
637 | ||
638 | static inline bool | |
639 | set_lattice_to_bottom (struct ipcp_lattice *lat) | |
3b22db66 | 640 | { |
821d0e0f | 641 | bool ret = !lat->bottom; |
642 | lat->bottom = true; | |
643 | return ret; | |
644 | } | |
3b22db66 | 645 | |
821d0e0f | 646 | /* Mark lattice as containing an unknown value and return true if it previously |
647 | was not marked as such. */ | |
50828ed8 | 648 | |
821d0e0f | 649 | static inline bool |
650 | set_lattice_contains_variable (struct ipcp_lattice *lat) | |
651 | { | |
652 | bool ret = !lat->contains_variable; | |
653 | lat->contains_variable = true; | |
654 | return ret; | |
3b22db66 | 655 | } |
656 | ||
803a7988 | 657 | /* Set all aggegate lattices in PLATS to bottom and return true if they were |
658 | not previously set as such. */ | |
659 | ||
660 | static inline bool | |
661 | set_agg_lats_to_bottom (struct ipcp_param_lattices *plats) | |
662 | { | |
663 | bool ret = !plats->aggs_bottom; | |
664 | plats->aggs_bottom = true; | |
665 | return ret; | |
666 | } | |
667 | ||
668 | /* Mark all aggegate lattices in PLATS as containing an unknown value and | |
669 | return true if they were not previously marked as such. */ | |
670 | ||
671 | static inline bool | |
672 | set_agg_lats_contain_variable (struct ipcp_param_lattices *plats) | |
673 | { | |
674 | bool ret = !plats->aggs_contain_variable; | |
675 | plats->aggs_contain_variable = true; | |
676 | return ret; | |
677 | } | |
678 | ||
679 | /* Mark bot aggregate and scalar lattices as containing an unknown variable, | |
680 | return true is any of them has not been marked as such so far. */ | |
681 | ||
682 | static inline bool | |
683 | set_all_contains_variable (struct ipcp_param_lattices *plats) | |
684 | { | |
685 | bool ret = !plats->itself.contains_variable || !plats->aggs_contain_variable; | |
686 | plats->itself.contains_variable = true; | |
687 | plats->aggs_contain_variable = true; | |
688 | return ret; | |
689 | } | |
690 | ||
821d0e0f | 691 | /* Initialize ipcp_lattices. */ |
5fce5299 | 692 | |
3b22db66 | 693 | static void |
821d0e0f | 694 | initialize_node_lattices (struct cgraph_node *node) |
3b22db66 | 695 | { |
821d0e0f | 696 | struct ipa_node_params *info = IPA_NODE_REF (node); |
697 | struct cgraph_edge *ie; | |
698 | bool disable = false, variable = false; | |
699 | int i; | |
3b22db66 | 700 | |
821d0e0f | 701 | gcc_checking_assert (cgraph_function_with_gimple_body_p (node)); |
03f99d3c | 702 | if (!node->local.local) |
821d0e0f | 703 | { |
704 | /* When cloning is allowed, we can assume that externally visible | |
705 | functions are not called. We will compensate this by cloning | |
706 | later. */ | |
707 | if (ipcp_versionable_function_p (node) | |
708 | && ipcp_cloning_candidate_p (node)) | |
709 | variable = true; | |
710 | else | |
711 | disable = true; | |
712 | } | |
3b22db66 | 713 | |
821d0e0f | 714 | if (disable || variable) |
715 | { | |
716 | for (i = 0; i < ipa_get_param_count (info) ; i++) | |
717 | { | |
803a7988 | 718 | struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); |
821d0e0f | 719 | if (disable) |
803a7988 | 720 | { |
721 | set_lattice_to_bottom (&plats->itself); | |
722 | set_agg_lats_to_bottom (plats); | |
723 | } | |
821d0e0f | 724 | else |
803a7988 | 725 | set_all_contains_variable (plats); |
821d0e0f | 726 | } |
727 | if (dump_file && (dump_flags & TDF_DETAILS) | |
02774f2d | 728 | && !node->alias && !node->thunk.thunk_p) |
821d0e0f | 729 | fprintf (dump_file, "Marking all lattices of %s/%i as %s\n", |
f1c8b4d7 | 730 | node->name (), node->order, |
821d0e0f | 731 | disable ? "BOTTOM" : "VARIABLE"); |
732 | } | |
3b22db66 | 733 | |
821d0e0f | 734 | for (ie = node->indirect_calls; ie; ie = ie->next_callee) |
f5e35fed | 735 | if (ie->indirect_info->polymorphic |
736 | && ie->indirect_info->param_index >= 0) | |
eae7682a | 737 | { |
821d0e0f | 738 | gcc_checking_assert (ie->indirect_info->param_index >= 0); |
803a7988 | 739 | ipa_get_parm_lattices (info, |
740 | ie->indirect_info->param_index)->virt_call = 1; | |
eae7682a | 741 | } |
3b22db66 | 742 | } |
743 | ||
821d0e0f | 744 | /* Return the result of a (possibly arithmetic) pass through jump function |
745 | JFUNC on the constant value INPUT. Return NULL_TREE if that cannot be | |
ad4a8b28 | 746 | determined or be considered an interprocedural invariant. */ |
1caef38b | 747 | |
821d0e0f | 748 | static tree |
749 | ipa_get_jf_pass_through_result (struct ipa_jump_func *jfunc, tree input) | |
1caef38b | 750 | { |
821d0e0f | 751 | tree restype, res; |
1caef38b | 752 | |
ad4a8b28 | 753 | if (TREE_CODE (input) == TREE_BINFO) |
754 | { | |
755 | if (ipa_get_jf_pass_through_type_preserved (jfunc)) | |
756 | { | |
757 | gcc_checking_assert (ipa_get_jf_pass_through_operation (jfunc) | |
758 | == NOP_EXPR); | |
759 | return input; | |
760 | } | |
761 | return NULL_TREE; | |
762 | } | |
763 | ||
4fa83f96 | 764 | if (ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR) |
821d0e0f | 765 | return input; |
1caef38b | 766 | |
4fa83f96 | 767 | gcc_checking_assert (is_gimple_ip_invariant (input)); |
768 | if (TREE_CODE_CLASS (ipa_get_jf_pass_through_operation (jfunc)) | |
821d0e0f | 769 | == tcc_comparison) |
770 | restype = boolean_type_node; | |
771 | else | |
772 | restype = TREE_TYPE (input); | |
4fa83f96 | 773 | res = fold_binary (ipa_get_jf_pass_through_operation (jfunc), restype, |
774 | input, ipa_get_jf_pass_through_operand (jfunc)); | |
1caef38b | 775 | |
821d0e0f | 776 | if (res && !is_gimple_ip_invariant (res)) |
777 | return NULL_TREE; | |
1caef38b | 778 | |
821d0e0f | 779 | return res; |
1caef38b | 780 | } |
781 | ||
821d0e0f | 782 | /* Return the result of an ancestor jump function JFUNC on the constant value |
783 | INPUT. Return NULL_TREE if that cannot be determined. */ | |
1caef38b | 784 | |
821d0e0f | 785 | static tree |
786 | ipa_get_jf_ancestor_result (struct ipa_jump_func *jfunc, tree input) | |
1caef38b | 787 | { |
4fa83f96 | 788 | if (TREE_CODE (input) == TREE_BINFO) |
ad4a8b28 | 789 | { |
790 | if (!ipa_get_jf_ancestor_type_preserved (jfunc)) | |
791 | return NULL; | |
792 | return get_binfo_at_offset (input, | |
793 | ipa_get_jf_ancestor_offset (jfunc), | |
794 | ipa_get_jf_ancestor_type (jfunc)); | |
795 | } | |
4fa83f96 | 796 | else if (TREE_CODE (input) == ADDR_EXPR) |
1caef38b | 797 | { |
821d0e0f | 798 | tree t = TREE_OPERAND (input, 0); |
799 | t = build_ref_for_offset (EXPR_LOCATION (t), t, | |
4fa83f96 | 800 | ipa_get_jf_ancestor_offset (jfunc), |
0daac096 | 801 | ipa_get_jf_ancestor_type (jfunc) |
802 | ? ipa_get_jf_ancestor_type (jfunc) | |
803 | : ptr_type_node, NULL, false); | |
821d0e0f | 804 | return build_fold_addr_expr (t); |
1caef38b | 805 | } |
806 | else | |
821d0e0f | 807 | return NULL_TREE; |
808 | } | |
1caef38b | 809 | |
821d0e0f | 810 | /* Determine whether JFUNC evaluates to a known value (that is either a |
811 | constant or a binfo) and if so, return it. Otherwise return NULL. INFO | |
812 | describes the caller node so that pass-through jump functions can be | |
813 | evaluated. */ | |
814 | ||
20da2013 | 815 | tree |
821d0e0f | 816 | ipa_value_from_jfunc (struct ipa_node_params *info, struct ipa_jump_func *jfunc) |
817 | { | |
818 | if (jfunc->type == IPA_JF_CONST) | |
4fa83f96 | 819 | return ipa_get_jf_constant (jfunc); |
821d0e0f | 820 | else if (jfunc->type == IPA_JF_KNOWN_TYPE) |
bee52153 | 821 | return ipa_binfo_from_known_type_jfunc (jfunc); |
821d0e0f | 822 | else if (jfunc->type == IPA_JF_PASS_THROUGH |
823 | || jfunc->type == IPA_JF_ANCESTOR) | |
1caef38b | 824 | { |
821d0e0f | 825 | tree input; |
826 | int idx; | |
1caef38b | 827 | |
821d0e0f | 828 | if (jfunc->type == IPA_JF_PASS_THROUGH) |
4fa83f96 | 829 | idx = ipa_get_jf_pass_through_formal_id (jfunc); |
821d0e0f | 830 | else |
4fa83f96 | 831 | idx = ipa_get_jf_ancestor_formal_id (jfunc); |
1caef38b | 832 | |
821d0e0f | 833 | if (info->ipcp_orig_node) |
f1f41a6c | 834 | input = info->known_vals[idx]; |
821d0e0f | 835 | else |
1caef38b | 836 | { |
821d0e0f | 837 | struct ipcp_lattice *lat; |
838 | ||
839 | if (!info->lattices) | |
1caef38b | 840 | { |
821d0e0f | 841 | gcc_checking_assert (!flag_ipa_cp); |
842 | return NULL_TREE; | |
1caef38b | 843 | } |
803a7988 | 844 | lat = ipa_get_scalar_lat (info, idx); |
821d0e0f | 845 | if (!ipa_lat_is_single_const (lat)) |
846 | return NULL_TREE; | |
847 | input = lat->values->value; | |
848 | } | |
849 | ||
850 | if (!input) | |
851 | return NULL_TREE; | |
852 | ||
853 | if (jfunc->type == IPA_JF_PASS_THROUGH) | |
4fa83f96 | 854 | return ipa_get_jf_pass_through_result (jfunc, input); |
821d0e0f | 855 | else |
4fa83f96 | 856 | return ipa_get_jf_ancestor_result (jfunc, input); |
1caef38b | 857 | } |
821d0e0f | 858 | else |
859 | return NULL_TREE; | |
1caef38b | 860 | } |
861 | ||
1caef38b | 862 | |
821d0e0f | 863 | /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not |
864 | bottom, not containing a variable component and without any known value at | |
865 | the same time. */ | |
1caef38b | 866 | |
821d0e0f | 867 | DEBUG_FUNCTION void |
868 | ipcp_verify_propagated_values (void) | |
3b22db66 | 869 | { |
821d0e0f | 870 | struct cgraph_node *node; |
11b73810 | 871 | |
821d0e0f | 872 | FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node) |
3b22db66 | 873 | { |
d60eadfa | 874 | struct ipa_node_params *info = IPA_NODE_REF (node); |
821d0e0f | 875 | int i, count = ipa_get_param_count (info); |
d60eadfa | 876 | |
821d0e0f | 877 | for (i = 0; i < count; i++) |
3b22db66 | 878 | { |
803a7988 | 879 | struct ipcp_lattice *lat = ipa_get_scalar_lat (info, i); |
d60eadfa | 880 | |
821d0e0f | 881 | if (!lat->bottom |
882 | && !lat->contains_variable | |
883 | && lat->values_count == 0) | |
3b22db66 | 884 | { |
821d0e0f | 885 | if (dump_file) |
3b22db66 | 886 | { |
3083a0b3 | 887 | dump_symtab (dump_file); |
821d0e0f | 888 | fprintf (dump_file, "\nIPA lattices after constant " |
3083a0b3 | 889 | "propagation, before gcc_unreachable:\n"); |
821d0e0f | 890 | print_all_lattices (dump_file, true, false); |
3b22db66 | 891 | } |
1caef38b | 892 | |
821d0e0f | 893 | gcc_unreachable (); |
3b22db66 | 894 | } |
895 | } | |
896 | } | |
897 | } | |
898 | ||
821d0e0f | 899 | /* Return true iff X and Y should be considered equal values by IPA-CP. */ |
900 | ||
901 | static bool | |
902 | values_equal_for_ipcp_p (tree x, tree y) | |
903 | { | |
904 | gcc_checking_assert (x != NULL_TREE && y != NULL_TREE); | |
905 | ||
906 | if (x == y) | |
907 | return true; | |
908 | ||
909 | if (TREE_CODE (x) == TREE_BINFO || TREE_CODE (y) == TREE_BINFO) | |
910 | return false; | |
911 | ||
912 | if (TREE_CODE (x) == ADDR_EXPR | |
913 | && TREE_CODE (y) == ADDR_EXPR | |
914 | && TREE_CODE (TREE_OPERAND (x, 0)) == CONST_DECL | |
915 | && TREE_CODE (TREE_OPERAND (y, 0)) == CONST_DECL) | |
916 | return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x, 0)), | |
917 | DECL_INITIAL (TREE_OPERAND (y, 0)), 0); | |
918 | else | |
919 | return operand_equal_p (x, y, 0); | |
920 | } | |
921 | ||
922 | /* Add a new value source to VAL, marking that a value comes from edge CS and | |
923 | (if the underlying jump function is a pass-through or an ancestor one) from | |
803a7988 | 924 | a caller value SRC_VAL of a caller parameter described by SRC_INDEX. OFFSET |
925 | is negative if the source was the scalar value of the parameter itself or | |
926 | the offset within an aggregate. */ | |
821d0e0f | 927 | |
3b22db66 | 928 | static void |
821d0e0f | 929 | add_value_source (struct ipcp_value *val, struct cgraph_edge *cs, |
803a7988 | 930 | struct ipcp_value *src_val, int src_idx, HOST_WIDE_INT offset) |
3b22db66 | 931 | { |
821d0e0f | 932 | struct ipcp_value_source *src; |
11b73810 | 933 | |
821d0e0f | 934 | src = (struct ipcp_value_source *) pool_alloc (ipcp_sources_pool); |
803a7988 | 935 | src->offset = offset; |
821d0e0f | 936 | src->cs = cs; |
937 | src->val = src_val; | |
938 | src->index = src_idx; | |
8867b500 | 939 | |
821d0e0f | 940 | src->next = val->sources; |
941 | val->sources = src; | |
942 | } | |
943 | ||
821d0e0f | 944 | /* Try to add NEWVAL to LAT, potentially creating a new struct ipcp_value for |
803a7988 | 945 | it. CS, SRC_VAL SRC_INDEX and OFFSET are meant for add_value_source and |
946 | have the same meaning. */ | |
821d0e0f | 947 | |
948 | static bool | |
949 | add_value_to_lattice (struct ipcp_lattice *lat, tree newval, | |
950 | struct cgraph_edge *cs, struct ipcp_value *src_val, | |
803a7988 | 951 | int src_idx, HOST_WIDE_INT offset) |
821d0e0f | 952 | { |
953 | struct ipcp_value *val; | |
954 | ||
955 | if (lat->bottom) | |
956 | return false; | |
957 | ||
821d0e0f | 958 | for (val = lat->values; val; val = val->next) |
959 | if (values_equal_for_ipcp_p (val->value, newval)) | |
960 | { | |
a0255a70 | 961 | if (ipa_edge_within_scc (cs)) |
821d0e0f | 962 | { |
963 | struct ipcp_value_source *s; | |
964 | for (s = val->sources; s ; s = s->next) | |
965 | if (s->cs == cs) | |
966 | break; | |
967 | if (s) | |
968 | return false; | |
969 | } | |
970 | ||
803a7988 | 971 | add_value_source (val, cs, src_val, src_idx, offset); |
821d0e0f | 972 | return false; |
973 | } | |
974 | ||
975 | if (lat->values_count == PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE)) | |
976 | { | |
977 | /* We can only free sources, not the values themselves, because sources | |
978 | of other values in this this SCC might point to them. */ | |
979 | for (val = lat->values; val; val = val->next) | |
980 | { | |
981 | while (val->sources) | |
982 | { | |
983 | struct ipcp_value_source *src = val->sources; | |
984 | val->sources = src->next; | |
985 | pool_free (ipcp_sources_pool, src); | |
986 | } | |
987 | } | |
988 | ||
989 | lat->values = NULL; | |
990 | return set_lattice_to_bottom (lat); | |
991 | } | |
992 | ||
993 | lat->values_count++; | |
994 | val = (struct ipcp_value *) pool_alloc (ipcp_values_pool); | |
995 | memset (val, 0, sizeof (*val)); | |
996 | ||
803a7988 | 997 | add_value_source (val, cs, src_val, src_idx, offset); |
821d0e0f | 998 | val->value = newval; |
999 | val->next = lat->values; | |
1000 | lat->values = val; | |
1001 | return true; | |
1002 | } | |
8867b500 | 1003 | |
803a7988 | 1004 | /* Like above but passes a special value of offset to distinguish that the |
1005 | origin is the scalar value of the parameter rather than a part of an | |
1006 | aggregate. */ | |
1007 | ||
1008 | static inline bool | |
1009 | add_scalar_value_to_lattice (struct ipcp_lattice *lat, tree newval, | |
1010 | struct cgraph_edge *cs, | |
1011 | struct ipcp_value *src_val, int src_idx) | |
1012 | { | |
1013 | return add_value_to_lattice (lat, newval, cs, src_val, src_idx, -1); | |
1014 | } | |
1015 | ||
821d0e0f | 1016 | /* Propagate values through a pass-through jump function JFUNC associated with |
1017 | edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX | |
1018 | is the index of the source parameter. */ | |
1019 | ||
1020 | static bool | |
1021 | propagate_vals_accross_pass_through (struct cgraph_edge *cs, | |
1022 | struct ipa_jump_func *jfunc, | |
1023 | struct ipcp_lattice *src_lat, | |
1024 | struct ipcp_lattice *dest_lat, | |
1025 | int src_idx) | |
1026 | { | |
1027 | struct ipcp_value *src_val; | |
1028 | bool ret = false; | |
1029 | ||
821d0e0f | 1030 | /* Do not create new values when propagating within an SCC because if there |
4fa83f96 | 1031 | are arithmetic functions with circular dependencies, there is infinite |
1032 | number of them and we would just make lattices bottom. */ | |
ad4a8b28 | 1033 | if ((ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR) |
a0255a70 | 1034 | && ipa_edge_within_scc (cs)) |
821d0e0f | 1035 | ret = set_lattice_contains_variable (dest_lat); |
1036 | else | |
1037 | for (src_val = src_lat->values; src_val; src_val = src_val->next) | |
eae7682a | 1038 | { |
ad4a8b28 | 1039 | tree cstval = ipa_get_jf_pass_through_result (jfunc, src_val->value); |
821d0e0f | 1040 | |
1041 | if (cstval) | |
803a7988 | 1042 | ret |= add_scalar_value_to_lattice (dest_lat, cstval, cs, src_val, |
1043 | src_idx); | |
821d0e0f | 1044 | else |
1045 | ret |= set_lattice_contains_variable (dest_lat); | |
eae7682a | 1046 | } |
821d0e0f | 1047 | |
1048 | return ret; | |
1049 | } | |
1050 | ||
1051 | /* Propagate values through an ancestor jump function JFUNC associated with | |
1052 | edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX | |
1053 | is the index of the source parameter. */ | |
1054 | ||
1055 | static bool | |
1056 | propagate_vals_accross_ancestor (struct cgraph_edge *cs, | |
1057 | struct ipa_jump_func *jfunc, | |
1058 | struct ipcp_lattice *src_lat, | |
1059 | struct ipcp_lattice *dest_lat, | |
1060 | int src_idx) | |
1061 | { | |
1062 | struct ipcp_value *src_val; | |
1063 | bool ret = false; | |
1064 | ||
a0255a70 | 1065 | if (ipa_edge_within_scc (cs)) |
821d0e0f | 1066 | return set_lattice_contains_variable (dest_lat); |
1067 | ||
1068 | for (src_val = src_lat->values; src_val; src_val = src_val->next) | |
1069 | { | |
4fa83f96 | 1070 | tree t = ipa_get_jf_ancestor_result (jfunc, src_val->value); |
821d0e0f | 1071 | |
1072 | if (t) | |
803a7988 | 1073 | ret |= add_scalar_value_to_lattice (dest_lat, t, cs, src_val, src_idx); |
821d0e0f | 1074 | else |
1075 | ret |= set_lattice_contains_variable (dest_lat); | |
1076 | } | |
1077 | ||
1078 | return ret; | |
1079 | } | |
1080 | ||
803a7988 | 1081 | /* Propagate scalar values across jump function JFUNC that is associated with |
1082 | edge CS and put the values into DEST_LAT. */ | |
821d0e0f | 1083 | |
1084 | static bool | |
803a7988 | 1085 | propagate_scalar_accross_jump_function (struct cgraph_edge *cs, |
1086 | struct ipa_jump_func *jfunc, | |
1087 | struct ipcp_lattice *dest_lat) | |
821d0e0f | 1088 | { |
1089 | if (dest_lat->bottom) | |
1090 | return false; | |
1091 | ||
1092 | if (jfunc->type == IPA_JF_CONST | |
1093 | || jfunc->type == IPA_JF_KNOWN_TYPE) | |
1094 | { | |
1095 | tree val; | |
1096 | ||
1097 | if (jfunc->type == IPA_JF_KNOWN_TYPE) | |
ee4fcf24 | 1098 | { |
bee52153 | 1099 | val = ipa_binfo_from_known_type_jfunc (jfunc); |
ee4fcf24 | 1100 | if (!val) |
1101 | return set_lattice_contains_variable (dest_lat); | |
1102 | } | |
821d0e0f | 1103 | else |
4fa83f96 | 1104 | val = ipa_get_jf_constant (jfunc); |
803a7988 | 1105 | return add_scalar_value_to_lattice (dest_lat, val, cs, NULL, 0); |
821d0e0f | 1106 | } |
1107 | else if (jfunc->type == IPA_JF_PASS_THROUGH | |
1108 | || jfunc->type == IPA_JF_ANCESTOR) | |
1109 | { | |
1110 | struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller); | |
1111 | struct ipcp_lattice *src_lat; | |
1112 | int src_idx; | |
1113 | bool ret; | |
1114 | ||
1115 | if (jfunc->type == IPA_JF_PASS_THROUGH) | |
4fa83f96 | 1116 | src_idx = ipa_get_jf_pass_through_formal_id (jfunc); |
821d0e0f | 1117 | else |
4fa83f96 | 1118 | src_idx = ipa_get_jf_ancestor_formal_id (jfunc); |
821d0e0f | 1119 | |
803a7988 | 1120 | src_lat = ipa_get_scalar_lat (caller_info, src_idx); |
821d0e0f | 1121 | if (src_lat->bottom) |
1122 | return set_lattice_contains_variable (dest_lat); | |
1123 | ||
1124 | /* If we would need to clone the caller and cannot, do not propagate. */ | |
1125 | if (!ipcp_versionable_function_p (cs->caller) | |
1126 | && (src_lat->contains_variable | |
1127 | || (src_lat->values_count > 1))) | |
1128 | return set_lattice_contains_variable (dest_lat); | |
1129 | ||
1130 | if (jfunc->type == IPA_JF_PASS_THROUGH) | |
1131 | ret = propagate_vals_accross_pass_through (cs, jfunc, src_lat, | |
1132 | dest_lat, src_idx); | |
1133 | else | |
1134 | ret = propagate_vals_accross_ancestor (cs, jfunc, src_lat, dest_lat, | |
1135 | src_idx); | |
1136 | ||
1137 | if (src_lat->contains_variable) | |
1138 | ret |= set_lattice_contains_variable (dest_lat); | |
1139 | ||
1140 | return ret; | |
1141 | } | |
1142 | ||
1143 | /* TODO: We currently do not handle member method pointers in IPA-CP (we only | |
1144 | use it for indirect inlining), we should propagate them too. */ | |
1145 | return set_lattice_contains_variable (dest_lat); | |
1146 | } | |
1147 | ||
803a7988 | 1148 | /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches |
1149 | NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all | |
1150 | other cases, return false). If there are no aggregate items, set | |
1151 | aggs_by_ref to NEW_AGGS_BY_REF. */ | |
1152 | ||
1153 | static bool | |
1154 | set_check_aggs_by_ref (struct ipcp_param_lattices *dest_plats, | |
1155 | bool new_aggs_by_ref) | |
1156 | { | |
1157 | if (dest_plats->aggs) | |
1158 | { | |
1159 | if (dest_plats->aggs_by_ref != new_aggs_by_ref) | |
1160 | { | |
1161 | set_agg_lats_to_bottom (dest_plats); | |
1162 | return true; | |
1163 | } | |
1164 | } | |
1165 | else | |
1166 | dest_plats->aggs_by_ref = new_aggs_by_ref; | |
1167 | return false; | |
1168 | } | |
1169 | ||
1170 | /* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an | |
1171 | already existing lattice for the given OFFSET and SIZE, marking all skipped | |
1172 | lattices as containing variable and checking for overlaps. If there is no | |
1173 | already existing lattice for the OFFSET and VAL_SIZE, create one, initialize | |
1174 | it with offset, size and contains_variable to PRE_EXISTING, and return true, | |
1175 | unless there are too many already. If there are two many, return false. If | |
1176 | there are overlaps turn whole DEST_PLATS to bottom and return false. If any | |
1177 | skipped lattices were newly marked as containing variable, set *CHANGE to | |
1178 | true. */ | |
1179 | ||
1180 | static bool | |
1181 | merge_agg_lats_step (struct ipcp_param_lattices *dest_plats, | |
1182 | HOST_WIDE_INT offset, HOST_WIDE_INT val_size, | |
1183 | struct ipcp_agg_lattice ***aglat, | |
1184 | bool pre_existing, bool *change) | |
1185 | { | |
1186 | gcc_checking_assert (offset >= 0); | |
1187 | ||
1188 | while (**aglat && (**aglat)->offset < offset) | |
1189 | { | |
1190 | if ((**aglat)->offset + (**aglat)->size > offset) | |
1191 | { | |
1192 | set_agg_lats_to_bottom (dest_plats); | |
1193 | return false; | |
1194 | } | |
1195 | *change |= set_lattice_contains_variable (**aglat); | |
1196 | *aglat = &(**aglat)->next; | |
1197 | } | |
1198 | ||
1199 | if (**aglat && (**aglat)->offset == offset) | |
1200 | { | |
1201 | if ((**aglat)->size != val_size | |
1202 | || ((**aglat)->next | |
1203 | && (**aglat)->next->offset < offset + val_size)) | |
1204 | { | |
1205 | set_agg_lats_to_bottom (dest_plats); | |
1206 | return false; | |
1207 | } | |
1208 | gcc_checking_assert (!(**aglat)->next | |
1209 | || (**aglat)->next->offset >= offset + val_size); | |
1210 | return true; | |
1211 | } | |
1212 | else | |
1213 | { | |
1214 | struct ipcp_agg_lattice *new_al; | |
1215 | ||
1216 | if (**aglat && (**aglat)->offset < offset + val_size) | |
1217 | { | |
1218 | set_agg_lats_to_bottom (dest_plats); | |
1219 | return false; | |
1220 | } | |
1221 | if (dest_plats->aggs_count == PARAM_VALUE (PARAM_IPA_MAX_AGG_ITEMS)) | |
1222 | return false; | |
1223 | dest_plats->aggs_count++; | |
1224 | new_al = (struct ipcp_agg_lattice *) pool_alloc (ipcp_agg_lattice_pool); | |
1225 | memset (new_al, 0, sizeof (*new_al)); | |
1226 | ||
1227 | new_al->offset = offset; | |
1228 | new_al->size = val_size; | |
1229 | new_al->contains_variable = pre_existing; | |
1230 | ||
1231 | new_al->next = **aglat; | |
1232 | **aglat = new_al; | |
1233 | return true; | |
1234 | } | |
1235 | } | |
1236 | ||
1237 | /* Set all AGLAT and all other aggregate lattices reachable by next pointers as | |
1238 | containing an unknown value. */ | |
1239 | ||
1240 | static bool | |
1241 | set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice *aglat) | |
1242 | { | |
1243 | bool ret = false; | |
1244 | while (aglat) | |
1245 | { | |
1246 | ret |= set_lattice_contains_variable (aglat); | |
1247 | aglat = aglat->next; | |
1248 | } | |
1249 | return ret; | |
1250 | } | |
1251 | ||
1252 | /* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting | |
1253 | DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source | |
1254 | parameter used for lattice value sources. Return true if DEST_PLATS changed | |
1255 | in any way. */ | |
1256 | ||
1257 | static bool | |
1258 | merge_aggregate_lattices (struct cgraph_edge *cs, | |
1259 | struct ipcp_param_lattices *dest_plats, | |
1260 | struct ipcp_param_lattices *src_plats, | |
1261 | int src_idx, HOST_WIDE_INT offset_delta) | |
1262 | { | |
1263 | bool pre_existing = dest_plats->aggs != NULL; | |
1264 | struct ipcp_agg_lattice **dst_aglat; | |
1265 | bool ret = false; | |
1266 | ||
1267 | if (set_check_aggs_by_ref (dest_plats, src_plats->aggs_by_ref)) | |
1268 | return true; | |
1269 | if (src_plats->aggs_bottom) | |
1270 | return set_agg_lats_contain_variable (dest_plats); | |
36bcc547 | 1271 | if (src_plats->aggs_contain_variable) |
1272 | ret |= set_agg_lats_contain_variable (dest_plats); | |
803a7988 | 1273 | dst_aglat = &dest_plats->aggs; |
1274 | ||
1275 | for (struct ipcp_agg_lattice *src_aglat = src_plats->aggs; | |
1276 | src_aglat; | |
1277 | src_aglat = src_aglat->next) | |
1278 | { | |
1279 | HOST_WIDE_INT new_offset = src_aglat->offset - offset_delta; | |
1280 | ||
1281 | if (new_offset < 0) | |
1282 | continue; | |
1283 | if (merge_agg_lats_step (dest_plats, new_offset, src_aglat->size, | |
1284 | &dst_aglat, pre_existing, &ret)) | |
1285 | { | |
1286 | struct ipcp_agg_lattice *new_al = *dst_aglat; | |
1287 | ||
1288 | dst_aglat = &(*dst_aglat)->next; | |
1289 | if (src_aglat->bottom) | |
1290 | { | |
1291 | ret |= set_lattice_contains_variable (new_al); | |
1292 | continue; | |
1293 | } | |
1294 | if (src_aglat->contains_variable) | |
1295 | ret |= set_lattice_contains_variable (new_al); | |
1296 | for (struct ipcp_value *val = src_aglat->values; | |
1297 | val; | |
1298 | val = val->next) | |
1299 | ret |= add_value_to_lattice (new_al, val->value, cs, val, src_idx, | |
1300 | src_aglat->offset); | |
1301 | } | |
1302 | else if (dest_plats->aggs_bottom) | |
1303 | return true; | |
1304 | } | |
1305 | ret |= set_chain_of_aglats_contains_variable (*dst_aglat); | |
1306 | return ret; | |
1307 | } | |
1308 | ||
e3f929ed | 1309 | /* Determine whether there is anything to propagate FROM SRC_PLATS through a |
1310 | pass-through JFUNC and if so, whether it has conform and conforms to the | |
1311 | rules about propagating values passed by reference. */ | |
1312 | ||
1313 | static bool | |
1314 | agg_pass_through_permissible_p (struct ipcp_param_lattices *src_plats, | |
1315 | struct ipa_jump_func *jfunc) | |
1316 | { | |
1317 | return src_plats->aggs | |
1318 | && (!src_plats->aggs_by_ref | |
1319 | || ipa_get_jf_pass_through_agg_preserved (jfunc)); | |
1320 | } | |
1321 | ||
803a7988 | 1322 | /* Propagate scalar values across jump function JFUNC that is associated with |
1323 | edge CS and put the values into DEST_LAT. */ | |
1324 | ||
1325 | static bool | |
1326 | propagate_aggs_accross_jump_function (struct cgraph_edge *cs, | |
1327 | struct ipa_jump_func *jfunc, | |
1328 | struct ipcp_param_lattices *dest_plats) | |
1329 | { | |
1330 | bool ret = false; | |
1331 | ||
1332 | if (dest_plats->aggs_bottom) | |
1333 | return false; | |
1334 | ||
1335 | if (jfunc->type == IPA_JF_PASS_THROUGH | |
1336 | && ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR) | |
1337 | { | |
1338 | struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller); | |
1339 | int src_idx = ipa_get_jf_pass_through_formal_id (jfunc); | |
1340 | struct ipcp_param_lattices *src_plats; | |
1341 | ||
1342 | src_plats = ipa_get_parm_lattices (caller_info, src_idx); | |
e3f929ed | 1343 | if (agg_pass_through_permissible_p (src_plats, jfunc)) |
803a7988 | 1344 | { |
1345 | /* Currently we do not produce clobber aggregate jump | |
1346 | functions, replace with merging when we do. */ | |
1347 | gcc_assert (!jfunc->agg.items); | |
1348 | ret |= merge_aggregate_lattices (cs, dest_plats, src_plats, | |
1349 | src_idx, 0); | |
1350 | } | |
1351 | else | |
1352 | ret |= set_agg_lats_contain_variable (dest_plats); | |
1353 | } | |
1354 | else if (jfunc->type == IPA_JF_ANCESTOR | |
1355 | && ipa_get_jf_ancestor_agg_preserved (jfunc)) | |
1356 | { | |
1357 | struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller); | |
1358 | int src_idx = ipa_get_jf_ancestor_formal_id (jfunc); | |
1359 | struct ipcp_param_lattices *src_plats; | |
1360 | ||
1361 | src_plats = ipa_get_parm_lattices (caller_info, src_idx); | |
1362 | if (src_plats->aggs && src_plats->aggs_by_ref) | |
1363 | { | |
1364 | /* Currently we do not produce clobber aggregate jump | |
1365 | functions, replace with merging when we do. */ | |
1366 | gcc_assert (!jfunc->agg.items); | |
1367 | ret |= merge_aggregate_lattices (cs, dest_plats, src_plats, src_idx, | |
1368 | ipa_get_jf_ancestor_offset (jfunc)); | |
1369 | } | |
1370 | else if (!src_plats->aggs_by_ref) | |
1371 | ret |= set_agg_lats_to_bottom (dest_plats); | |
1372 | else | |
1373 | ret |= set_agg_lats_contain_variable (dest_plats); | |
1374 | } | |
1375 | else if (jfunc->agg.items) | |
1376 | { | |
1377 | bool pre_existing = dest_plats->aggs != NULL; | |
1378 | struct ipcp_agg_lattice **aglat = &dest_plats->aggs; | |
1379 | struct ipa_agg_jf_item *item; | |
1380 | int i; | |
1381 | ||
1382 | if (set_check_aggs_by_ref (dest_plats, jfunc->agg.by_ref)) | |
1383 | return true; | |
1384 | ||
f1f41a6c | 1385 | FOR_EACH_VEC_ELT (*jfunc->agg.items, i, item) |
803a7988 | 1386 | { |
1387 | HOST_WIDE_INT val_size; | |
1388 | ||
1389 | if (item->offset < 0) | |
1390 | continue; | |
1391 | gcc_checking_assert (is_gimple_ip_invariant (item->value)); | |
6a0712d4 | 1392 | val_size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (item->value))); |
803a7988 | 1393 | |
1394 | if (merge_agg_lats_step (dest_plats, item->offset, val_size, | |
1395 | &aglat, pre_existing, &ret)) | |
1396 | { | |
1397 | ret |= add_value_to_lattice (*aglat, item->value, cs, NULL, 0, 0); | |
1398 | aglat = &(*aglat)->next; | |
1399 | } | |
1400 | else if (dest_plats->aggs_bottom) | |
1401 | return true; | |
1402 | } | |
1403 | ||
1404 | ret |= set_chain_of_aglats_contains_variable (*aglat); | |
1405 | } | |
1406 | else | |
1407 | ret |= set_agg_lats_contain_variable (dest_plats); | |
1408 | ||
1409 | return ret; | |
1410 | } | |
1411 | ||
821d0e0f | 1412 | /* Propagate constants from the caller to the callee of CS. INFO describes the |
1413 | caller. */ | |
1414 | ||
1415 | static bool | |
1416 | propagate_constants_accross_call (struct cgraph_edge *cs) | |
1417 | { | |
1418 | struct ipa_node_params *callee_info; | |
1419 | enum availability availability; | |
1420 | struct cgraph_node *callee, *alias_or_thunk; | |
1421 | struct ipa_edge_args *args; | |
1422 | bool ret = false; | |
03f99d3c | 1423 | int i, args_count, parms_count; |
821d0e0f | 1424 | |
1425 | callee = cgraph_function_node (cs->callee, &availability); | |
02774f2d | 1426 | if (!callee->definition) |
821d0e0f | 1427 | return false; |
1428 | gcc_checking_assert (cgraph_function_with_gimple_body_p (callee)); | |
1429 | callee_info = IPA_NODE_REF (callee); | |
821d0e0f | 1430 | |
1431 | args = IPA_EDGE_REF (cs); | |
03f99d3c | 1432 | args_count = ipa_get_cs_argument_count (args); |
1433 | parms_count = ipa_get_param_count (callee_info); | |
019885b0 | 1434 | if (parms_count == 0) |
1435 | return false; | |
821d0e0f | 1436 | |
1437 | /* If this call goes through a thunk we must not propagate to the first (0th) | |
1438 | parameter. However, we might need to uncover a thunk from below a series | |
1439 | of aliases first. */ | |
1440 | alias_or_thunk = cs->callee; | |
02774f2d | 1441 | while (alias_or_thunk->alias) |
15ca8f90 | 1442 | alias_or_thunk = cgraph_alias_target (alias_or_thunk); |
821d0e0f | 1443 | if (alias_or_thunk->thunk.thunk_p) |
1444 | { | |
803a7988 | 1445 | ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info, |
1446 | 0)); | |
821d0e0f | 1447 | i = 1; |
1448 | } | |
1449 | else | |
1450 | i = 0; | |
1451 | ||
03f99d3c | 1452 | for (; (i < args_count) && (i < parms_count); i++) |
821d0e0f | 1453 | { |
1454 | struct ipa_jump_func *jump_func = ipa_get_ith_jump_func (args, i); | |
803a7988 | 1455 | struct ipcp_param_lattices *dest_plats; |
821d0e0f | 1456 | |
803a7988 | 1457 | dest_plats = ipa_get_parm_lattices (callee_info, i); |
821d0e0f | 1458 | if (availability == AVAIL_OVERWRITABLE) |
803a7988 | 1459 | ret |= set_all_contains_variable (dest_plats); |
821d0e0f | 1460 | else |
803a7988 | 1461 | { |
1462 | ret |= propagate_scalar_accross_jump_function (cs, jump_func, | |
1463 | &dest_plats->itself); | |
1464 | ret |= propagate_aggs_accross_jump_function (cs, jump_func, | |
1465 | dest_plats); | |
1466 | } | |
821d0e0f | 1467 | } |
03f99d3c | 1468 | for (; i < parms_count; i++) |
803a7988 | 1469 | ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info, i)); |
03f99d3c | 1470 | |
821d0e0f | 1471 | return ret; |
1472 | } | |
1473 | ||
1474 | /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS | |
265c4eb2 | 1475 | (which can contain both constants and binfos), KNOWN_BINFOS, KNOWN_AGGS or |
1476 | AGG_REPS return the destination. The latter three can be NULL. If AGG_REPS | |
1477 | is not NULL, KNOWN_AGGS is ignored. */ | |
821d0e0f | 1478 | |
265c4eb2 | 1479 | static tree |
1480 | ipa_get_indirect_edge_target_1 (struct cgraph_edge *ie, | |
1481 | vec<tree> known_vals, | |
1482 | vec<tree> known_binfos, | |
1483 | vec<ipa_agg_jump_function_p> known_aggs, | |
1484 | struct ipa_agg_replacement_value *agg_reps) | |
821d0e0f | 1485 | { |
1486 | int param_index = ie->indirect_info->param_index; | |
1487 | HOST_WIDE_INT token, anc_offset; | |
1488 | tree otr_type; | |
1489 | tree t; | |
02636da3 | 1490 | tree target = NULL; |
821d0e0f | 1491 | |
fd8b458b | 1492 | if (param_index == -1 |
1493 | || known_vals.length () <= (unsigned int) param_index) | |
821d0e0f | 1494 | return NULL_TREE; |
1495 | ||
1496 | if (!ie->indirect_info->polymorphic) | |
1497 | { | |
a4f60e55 | 1498 | tree t; |
1499 | ||
1500 | if (ie->indirect_info->agg_contents) | |
1501 | { | |
265c4eb2 | 1502 | if (agg_reps) |
1503 | { | |
1504 | t = NULL; | |
1505 | while (agg_reps) | |
1506 | { | |
1507 | if (agg_reps->index == param_index | |
c42e4f2e | 1508 | && agg_reps->offset == ie->indirect_info->offset |
1509 | && agg_reps->by_ref == ie->indirect_info->by_ref) | |
265c4eb2 | 1510 | { |
1511 | t = agg_reps->value; | |
1512 | break; | |
1513 | } | |
1514 | agg_reps = agg_reps->next; | |
1515 | } | |
1516 | } | |
1517 | else if (known_aggs.length () > (unsigned int) param_index) | |
a4f60e55 | 1518 | { |
1519 | struct ipa_agg_jump_function *agg; | |
f1f41a6c | 1520 | agg = known_aggs[param_index]; |
a4f60e55 | 1521 | t = ipa_find_agg_cst_for_param (agg, ie->indirect_info->offset, |
1522 | ie->indirect_info->by_ref); | |
1523 | } | |
1524 | else | |
1525 | t = NULL; | |
1526 | } | |
1527 | else | |
fd8b458b | 1528 | t = known_vals[param_index]; |
a4f60e55 | 1529 | |
821d0e0f | 1530 | if (t && |
1531 | TREE_CODE (t) == ADDR_EXPR | |
1532 | && TREE_CODE (TREE_OPERAND (t, 0)) == FUNCTION_DECL) | |
d4e80e2b | 1533 | return TREE_OPERAND (t, 0); |
821d0e0f | 1534 | else |
1535 | return NULL_TREE; | |
1536 | } | |
1537 | ||
02636da3 | 1538 | if (!flag_devirtualize) |
1539 | return NULL_TREE; | |
1540 | ||
a4f60e55 | 1541 | gcc_assert (!ie->indirect_info->agg_contents); |
821d0e0f | 1542 | token = ie->indirect_info->otr_token; |
0d491188 | 1543 | anc_offset = ie->indirect_info->offset; |
821d0e0f | 1544 | otr_type = ie->indirect_info->otr_type; |
1545 | ||
02636da3 | 1546 | t = NULL; |
1547 | ||
1548 | /* Try to work out value of virtual table pointer value in replacemnets. */ | |
1549 | if (!t && agg_reps && !ie->indirect_info->by_ref) | |
1550 | { | |
1551 | while (agg_reps) | |
1552 | { | |
1553 | if (agg_reps->index == param_index | |
1554 | && agg_reps->offset == ie->indirect_info->offset | |
1555 | && agg_reps->by_ref) | |
1556 | { | |
1557 | t = agg_reps->value; | |
1558 | break; | |
1559 | } | |
1560 | agg_reps = agg_reps->next; | |
1561 | } | |
1562 | } | |
1563 | ||
1564 | /* Try to work out value of virtual table pointer value in known | |
1565 | aggregate values. */ | |
1566 | if (!t && known_aggs.length () > (unsigned int) param_index | |
1567 | && !ie->indirect_info->by_ref) | |
1568 | { | |
1569 | struct ipa_agg_jump_function *agg; | |
1570 | agg = known_aggs[param_index]; | |
1571 | t = ipa_find_agg_cst_for_param (agg, ie->indirect_info->offset, | |
1572 | true); | |
1573 | } | |
1574 | ||
6750de5f | 1575 | /* If we found the virtual table pointer, lookup the target. */ |
02636da3 | 1576 | if (t) |
6750de5f | 1577 | { |
1578 | tree vtable; | |
1579 | unsigned HOST_WIDE_INT offset; | |
1580 | if (vtable_pointer_value_to_vtable (t, &vtable, &offset)) | |
1581 | { | |
1582 | target = gimple_get_virt_method_for_vtable (ie->indirect_info->otr_token, | |
1583 | vtable, offset); | |
bc58d800 | 1584 | if (target) |
6750de5f | 1585 | { |
bc58d800 | 1586 | if ((TREE_CODE (TREE_TYPE (target)) == FUNCTION_TYPE |
1587 | && DECL_FUNCTION_CODE (target) == BUILT_IN_UNREACHABLE) | |
1588 | || !possible_polymorphic_call_target_p | |
1589 | (ie, cgraph_get_node (target))) | |
1590 | { | |
1591 | if (dump_file) | |
1592 | fprintf (dump_file, | |
1593 | "Type inconsident devirtualization: %s/%i->%s\n", | |
1594 | ie->caller->name (), ie->caller->order, | |
1595 | IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (target))); | |
1596 | target = builtin_decl_implicit (BUILT_IN_UNREACHABLE); | |
1597 | cgraph_get_create_node (target); | |
1598 | } | |
1599 | return target; | |
6750de5f | 1600 | } |
6750de5f | 1601 | } |
1602 | } | |
02636da3 | 1603 | |
1604 | /* Did we work out BINFO via type propagation? */ | |
f1f41a6c | 1605 | if (!t && known_binfos.length () > (unsigned int) param_index) |
1606 | t = known_binfos[param_index]; | |
02636da3 | 1607 | /* Or do we know the constant value of pointer? */ |
1608 | if (!t) | |
1609 | t = known_vals[param_index]; | |
821d0e0f | 1610 | if (!t) |
1611 | return NULL_TREE; | |
1612 | ||
1613 | if (TREE_CODE (t) != TREE_BINFO) | |
1614 | { | |
54176a57 | 1615 | ipa_polymorphic_call_context context; |
1616 | vec <cgraph_node *>targets; | |
1617 | bool final; | |
1618 | ||
1619 | if (!get_polymorphic_call_info_from_invariant | |
1620 | (&context, t, ie->indirect_info->otr_type, | |
1621 | anc_offset)) | |
821d0e0f | 1622 | return NULL_TREE; |
54176a57 | 1623 | targets = possible_polymorphic_call_targets |
1624 | (ie->indirect_info->otr_type, | |
1625 | ie->indirect_info->otr_token, | |
1626 | context, &final); | |
1627 | if (!final || targets.length () > 1) | |
821d0e0f | 1628 | return NULL_TREE; |
54176a57 | 1629 | if (targets.length () == 1) |
1630 | target = targets[0]->decl; | |
1631 | else | |
1632 | target = builtin_decl_implicit (BUILT_IN_UNREACHABLE); | |
821d0e0f | 1633 | } |
1634 | else | |
1635 | { | |
1636 | tree binfo; | |
1637 | ||
1638 | binfo = get_binfo_at_offset (t, anc_offset, otr_type); | |
1639 | if (!binfo) | |
1640 | return NULL_TREE; | |
10fba9c0 | 1641 | target = gimple_get_virt_method_for_binfo (token, binfo); |
821d0e0f | 1642 | } |
9a225e5a | 1643 | |
1644 | if (target && !possible_polymorphic_call_target_p (ie, | |
1645 | cgraph_get_node (target))) | |
1646 | { | |
1647 | if (dump_file) | |
1648 | fprintf (dump_file, | |
1649 | "Type inconsident devirtualization: %s/%i->%s\n", | |
1650 | ie->caller->name (), ie->caller->order, | |
1651 | IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (target))); | |
1652 | target = builtin_decl_implicit (BUILT_IN_UNREACHABLE); | |
1653 | cgraph_get_create_node (target); | |
1654 | } | |
10fba9c0 | 1655 | |
1656 | return target; | |
821d0e0f | 1657 | } |
1658 | ||
265c4eb2 | 1659 | |
1660 | /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS | |
1661 | (which can contain both constants and binfos), KNOWN_BINFOS (which can be | |
1662 | NULL) or KNOWN_AGGS (which also can be NULL) return the destination. */ | |
1663 | ||
1664 | tree | |
1665 | ipa_get_indirect_edge_target (struct cgraph_edge *ie, | |
1666 | vec<tree> known_vals, | |
1667 | vec<tree> known_binfos, | |
1668 | vec<ipa_agg_jump_function_p> known_aggs) | |
1669 | { | |
1670 | return ipa_get_indirect_edge_target_1 (ie, known_vals, known_binfos, | |
1671 | known_aggs, NULL); | |
1672 | } | |
1673 | ||
821d0e0f | 1674 | /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS |
1675 | and KNOWN_BINFOS. */ | |
1676 | ||
1677 | static int | |
1678 | devirtualization_time_bonus (struct cgraph_node *node, | |
f1f41a6c | 1679 | vec<tree> known_csts, |
265c4eb2 | 1680 | vec<tree> known_binfos, |
1681 | vec<ipa_agg_jump_function_p> known_aggs) | |
821d0e0f | 1682 | { |
1683 | struct cgraph_edge *ie; | |
1684 | int res = 0; | |
1685 | ||
1686 | for (ie = node->indirect_calls; ie; ie = ie->next_callee) | |
1687 | { | |
1688 | struct cgraph_node *callee; | |
1689 | struct inline_summary *isummary; | |
d4e80e2b | 1690 | tree target; |
821d0e0f | 1691 | |
a4f60e55 | 1692 | target = ipa_get_indirect_edge_target (ie, known_csts, known_binfos, |
265c4eb2 | 1693 | known_aggs); |
821d0e0f | 1694 | if (!target) |
1695 | continue; | |
1696 | ||
1697 | /* Only bare minimum benefit for clearly un-inlineable targets. */ | |
1698 | res += 1; | |
1699 | callee = cgraph_get_node (target); | |
02774f2d | 1700 | if (!callee || !callee->definition) |
821d0e0f | 1701 | continue; |
1702 | isummary = inline_summary (callee); | |
1703 | if (!isummary->inlinable) | |
1704 | continue; | |
1705 | ||
1706 | /* FIXME: The values below need re-considering and perhaps also | |
1707 | integrating into the cost metrics, at lest in some very basic way. */ | |
1708 | if (isummary->size <= MAX_INLINE_INSNS_AUTO / 4) | |
1709 | res += 31; | |
1710 | else if (isummary->size <= MAX_INLINE_INSNS_AUTO / 2) | |
1711 | res += 15; | |
1712 | else if (isummary->size <= MAX_INLINE_INSNS_AUTO | |
02774f2d | 1713 | || DECL_DECLARED_INLINE_P (callee->decl)) |
821d0e0f | 1714 | res += 7; |
1715 | } | |
1716 | ||
1717 | return res; | |
1718 | } | |
1719 | ||
803a7988 | 1720 | /* Return time bonus incurred because of HINTS. */ |
1721 | ||
1722 | static int | |
1723 | hint_time_bonus (inline_hints hints) | |
1724 | { | |
3a1cb879 | 1725 | int result = 0; |
803a7988 | 1726 | if (hints & (INLINE_HINT_loop_iterations | INLINE_HINT_loop_stride)) |
3a1cb879 | 1727 | result += PARAM_VALUE (PARAM_IPA_CP_LOOP_HINT_BONUS); |
1728 | if (hints & INLINE_HINT_array_index) | |
1729 | result += PARAM_VALUE (PARAM_IPA_CP_ARRAY_INDEX_HINT_BONUS); | |
1730 | return result; | |
803a7988 | 1731 | } |
1732 | ||
821d0e0f | 1733 | /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT |
1734 | and SIZE_COST and with the sum of frequencies of incoming edges to the | |
1735 | potential new clone in FREQUENCIES. */ | |
1736 | ||
1737 | static bool | |
1738 | good_cloning_opportunity_p (struct cgraph_node *node, int time_benefit, | |
1739 | int freq_sum, gcov_type count_sum, int size_cost) | |
1740 | { | |
1741 | if (time_benefit == 0 | |
1742 | || !flag_ipa_cp_clone | |
02774f2d | 1743 | || !optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node->decl))) |
821d0e0f | 1744 | return false; |
1745 | ||
29bb06c7 | 1746 | gcc_assert (size_cost > 0); |
821d0e0f | 1747 | |
821d0e0f | 1748 | if (max_count) |
1749 | { | |
29bb06c7 | 1750 | int factor = (count_sum * 1000) / max_count; |
1751 | HOST_WIDEST_INT evaluation = (((HOST_WIDEST_INT) time_benefit * factor) | |
1752 | / size_cost); | |
821d0e0f | 1753 | |
1754 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1755 | fprintf (dump_file, " good_cloning_opportunity_p (time: %i, " | |
1756 | "size: %i, count_sum: " HOST_WIDE_INT_PRINT_DEC | |
29bb06c7 | 1757 | ") -> evaluation: " HOST_WIDEST_INT_PRINT_DEC |
1758 | ", threshold: %i\n", | |
821d0e0f | 1759 | time_benefit, size_cost, (HOST_WIDE_INT) count_sum, |
cfb368a3 | 1760 | evaluation, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD)); |
821d0e0f | 1761 | |
1762 | return evaluation >= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD); | |
1763 | } | |
1764 | else | |
1765 | { | |
29bb06c7 | 1766 | HOST_WIDEST_INT evaluation = (((HOST_WIDEST_INT) time_benefit * freq_sum) |
1767 | / size_cost); | |
821d0e0f | 1768 | |
1769 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1770 | fprintf (dump_file, " good_cloning_opportunity_p (time: %i, " | |
29bb06c7 | 1771 | "size: %i, freq_sum: %i) -> evaluation: " |
1772 | HOST_WIDEST_INT_PRINT_DEC ", threshold: %i\n", | |
821d0e0f | 1773 | time_benefit, size_cost, freq_sum, evaluation, |
cfb368a3 | 1774 | PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD)); |
821d0e0f | 1775 | |
1776 | return evaluation >= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD); | |
1777 | } | |
1778 | } | |
1779 | ||
803a7988 | 1780 | /* Return all context independent values from aggregate lattices in PLATS in a |
1781 | vector. Return NULL if there are none. */ | |
1782 | ||
b3e7c666 | 1783 | static vec<ipa_agg_jf_item, va_gc> * |
803a7988 | 1784 | context_independent_aggregate_values (struct ipcp_param_lattices *plats) |
1785 | { | |
b3e7c666 | 1786 | vec<ipa_agg_jf_item, va_gc> *res = NULL; |
803a7988 | 1787 | |
1788 | if (plats->aggs_bottom | |
1789 | || plats->aggs_contain_variable | |
1790 | || plats->aggs_count == 0) | |
1791 | return NULL; | |
1792 | ||
1793 | for (struct ipcp_agg_lattice *aglat = plats->aggs; | |
1794 | aglat; | |
1795 | aglat = aglat->next) | |
1796 | if (ipa_lat_is_single_const (aglat)) | |
1797 | { | |
1798 | struct ipa_agg_jf_item item; | |
1799 | item.offset = aglat->offset; | |
1800 | item.value = aglat->values->value; | |
f1f41a6c | 1801 | vec_safe_push (res, item); |
803a7988 | 1802 | } |
1803 | return res; | |
1804 | } | |
821d0e0f | 1805 | |
803a7988 | 1806 | /* Allocate KNOWN_CSTS, KNOWN_BINFOS and, if non-NULL, KNOWN_AGGS and populate |
1807 | them with values of parameters that are known independent of the context. | |
1808 | INFO describes the function. If REMOVABLE_PARAMS_COST is non-NULL, the | |
1809 | movement cost of all removable parameters will be stored in it. */ | |
821d0e0f | 1810 | |
1811 | static bool | |
1812 | gather_context_independent_values (struct ipa_node_params *info, | |
f1f41a6c | 1813 | vec<tree> *known_csts, |
1814 | vec<tree> *known_binfos, | |
b3e7c666 | 1815 | vec<ipa_agg_jump_function> *known_aggs, |
803a7988 | 1816 | int *removable_params_cost) |
821d0e0f | 1817 | { |
1818 | int i, count = ipa_get_param_count (info); | |
1819 | bool ret = false; | |
1820 | ||
f1f41a6c | 1821 | known_csts->create (0); |
1822 | known_binfos->create (0); | |
1823 | known_csts->safe_grow_cleared (count); | |
1824 | known_binfos->safe_grow_cleared (count); | |
803a7988 | 1825 | if (known_aggs) |
1826 | { | |
f1f41a6c | 1827 | known_aggs->create (0); |
1828 | known_aggs->safe_grow_cleared (count); | |
803a7988 | 1829 | } |
821d0e0f | 1830 | |
1831 | if (removable_params_cost) | |
1832 | *removable_params_cost = 0; | |
1833 | ||
1834 | for (i = 0; i < count ; i++) | |
1835 | { | |
803a7988 | 1836 | struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); |
1837 | struct ipcp_lattice *lat = &plats->itself; | |
821d0e0f | 1838 | |
1839 | if (ipa_lat_is_single_const (lat)) | |
1840 | { | |
1841 | struct ipcp_value *val = lat->values; | |
1842 | if (TREE_CODE (val->value) != TREE_BINFO) | |
1843 | { | |
f1f41a6c | 1844 | (*known_csts)[i] = val->value; |
821d0e0f | 1845 | if (removable_params_cost) |
1846 | *removable_params_cost | |
1847 | += estimate_move_cost (TREE_TYPE (val->value)); | |
1848 | ret = true; | |
1849 | } | |
803a7988 | 1850 | else if (plats->virt_call) |
821d0e0f | 1851 | { |
f1f41a6c | 1852 | (*known_binfos)[i] = val->value; |
821d0e0f | 1853 | ret = true; |
1854 | } | |
1855 | else if (removable_params_cost | |
1856 | && !ipa_is_param_used (info, i)) | |
09ab6335 | 1857 | *removable_params_cost += ipa_get_param_move_cost (info, i); |
821d0e0f | 1858 | } |
1859 | else if (removable_params_cost | |
1860 | && !ipa_is_param_used (info, i)) | |
1861 | *removable_params_cost | |
09ab6335 | 1862 | += ipa_get_param_move_cost (info, i); |
803a7988 | 1863 | |
1864 | if (known_aggs) | |
1865 | { | |
b3e7c666 | 1866 | vec<ipa_agg_jf_item, va_gc> *agg_items; |
803a7988 | 1867 | struct ipa_agg_jump_function *ajf; |
1868 | ||
1869 | agg_items = context_independent_aggregate_values (plats); | |
f1f41a6c | 1870 | ajf = &(*known_aggs)[i]; |
803a7988 | 1871 | ajf->items = agg_items; |
1872 | ajf->by_ref = plats->aggs_by_ref; | |
1873 | ret |= agg_items != NULL; | |
1874 | } | |
821d0e0f | 1875 | } |
1876 | ||
1877 | return ret; | |
1878 | } | |
1879 | ||
803a7988 | 1880 | /* The current interface in ipa-inline-analysis requires a pointer vector. |
1881 | Create it. | |
1882 | ||
1883 | FIXME: That interface should be re-worked, this is slightly silly. Still, | |
1884 | I'd like to discuss how to change it first and this demonstrates the | |
1885 | issue. */ | |
1886 | ||
f1f41a6c | 1887 | static vec<ipa_agg_jump_function_p> |
b3e7c666 | 1888 | agg_jmp_p_vec_for_t_vec (vec<ipa_agg_jump_function> known_aggs) |
803a7988 | 1889 | { |
f1f41a6c | 1890 | vec<ipa_agg_jump_function_p> ret; |
803a7988 | 1891 | struct ipa_agg_jump_function *ajf; |
1892 | int i; | |
1893 | ||
f1f41a6c | 1894 | ret.create (known_aggs.length ()); |
1895 | FOR_EACH_VEC_ELT (known_aggs, i, ajf) | |
1896 | ret.quick_push (ajf); | |
803a7988 | 1897 | return ret; |
1898 | } | |
1899 | ||
821d0e0f | 1900 | /* Iterate over known values of parameters of NODE and estimate the local |
1901 | effects in terms of time and size they have. */ | |
1902 | ||
1903 | static void | |
1904 | estimate_local_effects (struct cgraph_node *node) | |
1905 | { | |
1906 | struct ipa_node_params *info = IPA_NODE_REF (node); | |
1907 | int i, count = ipa_get_param_count (info); | |
f1f41a6c | 1908 | vec<tree> known_csts, known_binfos; |
b3e7c666 | 1909 | vec<ipa_agg_jump_function> known_aggs; |
f1f41a6c | 1910 | vec<ipa_agg_jump_function_p> known_aggs_ptrs; |
821d0e0f | 1911 | bool always_const; |
1912 | int base_time = inline_summary (node)->time; | |
1913 | int removable_params_cost; | |
1914 | ||
1915 | if (!count || !ipcp_versionable_function_p (node)) | |
1916 | return; | |
1917 | ||
11b73810 | 1918 | if (dump_file && (dump_flags & TDF_DETAILS)) |
821d0e0f | 1919 | fprintf (dump_file, "\nEstimating effects for %s/%i, base_time: %i.\n", |
f1c8b4d7 | 1920 | node->name (), node->order, base_time); |
821d0e0f | 1921 | |
1922 | always_const = gather_context_independent_values (info, &known_csts, | |
803a7988 | 1923 | &known_binfos, &known_aggs, |
821d0e0f | 1924 | &removable_params_cost); |
803a7988 | 1925 | known_aggs_ptrs = agg_jmp_p_vec_for_t_vec (known_aggs); |
821d0e0f | 1926 | if (always_const) |
11b73810 | 1927 | { |
821d0e0f | 1928 | struct caller_statistics stats; |
803a7988 | 1929 | inline_hints hints; |
821d0e0f | 1930 | int time, size; |
1931 | ||
1932 | init_caller_stats (&stats); | |
1933 | cgraph_for_node_and_aliases (node, gather_caller_stats, &stats, false); | |
20da2013 | 1934 | estimate_ipcp_clone_size_and_time (node, known_csts, known_binfos, |
803a7988 | 1935 | known_aggs_ptrs, &size, &time, &hints); |
265c4eb2 | 1936 | time -= devirtualization_time_bonus (node, known_csts, known_binfos, |
1937 | known_aggs_ptrs); | |
803a7988 | 1938 | time -= hint_time_bonus (hints); |
821d0e0f | 1939 | time -= removable_params_cost; |
1940 | size -= stats.n_calls * removable_params_cost; | |
1941 | ||
1942 | if (dump_file) | |
1943 | fprintf (dump_file, " - context independent values, size: %i, " | |
1944 | "time_benefit: %i\n", size, base_time - time); | |
1945 | ||
1946 | if (size <= 0 | |
1947 | || cgraph_will_be_removed_from_program_if_no_direct_calls (node)) | |
1948 | { | |
87228246 | 1949 | info->do_clone_for_all_contexts = true; |
821d0e0f | 1950 | base_time = time; |
1951 | ||
1952 | if (dump_file) | |
1953 | fprintf (dump_file, " Decided to specialize for all " | |
1954 | "known contexts, code not going to grow.\n"); | |
1955 | } | |
1956 | else if (good_cloning_opportunity_p (node, base_time - time, | |
1957 | stats.freq_sum, stats.count_sum, | |
1958 | size)) | |
1959 | { | |
1960 | if (size + overall_size <= max_new_size) | |
1961 | { | |
87228246 | 1962 | info->do_clone_for_all_contexts = true; |
821d0e0f | 1963 | base_time = time; |
1964 | overall_size += size; | |
1965 | ||
1966 | if (dump_file) | |
1967 | fprintf (dump_file, " Decided to specialize for all " | |
1968 | "known contexts, growth deemed beneficial.\n"); | |
1969 | } | |
1970 | else if (dump_file && (dump_flags & TDF_DETAILS)) | |
1971 | fprintf (dump_file, " Not cloning for all contexts because " | |
1972 | "max_new_size would be reached with %li.\n", | |
1973 | size + overall_size); | |
1974 | } | |
11b73810 | 1975 | } |
1976 | ||
821d0e0f | 1977 | for (i = 0; i < count ; i++) |
11b73810 | 1978 | { |
803a7988 | 1979 | struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); |
1980 | struct ipcp_lattice *lat = &plats->itself; | |
821d0e0f | 1981 | struct ipcp_value *val; |
1982 | int emc; | |
1983 | ||
1984 | if (lat->bottom | |
1985 | || !lat->values | |
f1f41a6c | 1986 | || known_csts[i] |
1987 | || known_binfos[i]) | |
821d0e0f | 1988 | continue; |
1989 | ||
1990 | for (val = lat->values; val; val = val->next) | |
1991 | { | |
1992 | int time, size, time_benefit; | |
803a7988 | 1993 | inline_hints hints; |
821d0e0f | 1994 | |
1995 | if (TREE_CODE (val->value) != TREE_BINFO) | |
1996 | { | |
f1f41a6c | 1997 | known_csts[i] = val->value; |
1998 | known_binfos[i] = NULL_TREE; | |
821d0e0f | 1999 | emc = estimate_move_cost (TREE_TYPE (val->value)); |
2000 | } | |
803a7988 | 2001 | else if (plats->virt_call) |
821d0e0f | 2002 | { |
f1f41a6c | 2003 | known_csts[i] = NULL_TREE; |
2004 | known_binfos[i] = val->value; | |
821d0e0f | 2005 | emc = 0; |
2006 | } | |
2007 | else | |
2008 | continue; | |
2009 | ||
20da2013 | 2010 | estimate_ipcp_clone_size_and_time (node, known_csts, known_binfos, |
803a7988 | 2011 | known_aggs_ptrs, &size, &time, |
2012 | &hints); | |
821d0e0f | 2013 | time_benefit = base_time - time |
265c4eb2 | 2014 | + devirtualization_time_bonus (node, known_csts, known_binfos, |
2015 | known_aggs_ptrs) | |
803a7988 | 2016 | + hint_time_bonus (hints) |
821d0e0f | 2017 | + removable_params_cost + emc; |
2018 | ||
ae56707d | 2019 | gcc_checking_assert (size >=0); |
2020 | /* The inliner-heuristics based estimates may think that in certain | |
2021 | contexts some functions do not have any size at all but we want | |
2022 | all specializations to have at least a tiny cost, not least not to | |
2023 | divide by zero. */ | |
2024 | if (size == 0) | |
2025 | size = 1; | |
2026 | ||
821d0e0f | 2027 | if (dump_file && (dump_flags & TDF_DETAILS)) |
2028 | { | |
2029 | fprintf (dump_file, " - estimates for value "); | |
2030 | print_ipcp_constant_value (dump_file, val->value); | |
09ab6335 | 2031 | fprintf (dump_file, " for "); |
2032 | ipa_dump_param (dump_file, info, i); | |
821d0e0f | 2033 | fprintf (dump_file, ": time_benefit: %i, size: %i\n", |
2034 | time_benefit, size); | |
2035 | } | |
2036 | ||
2037 | val->local_time_benefit = time_benefit; | |
2038 | val->local_size_cost = size; | |
2039 | } | |
f1f41a6c | 2040 | known_binfos[i] = NULL_TREE; |
2041 | known_csts[i] = NULL_TREE; | |
803a7988 | 2042 | } |
2043 | ||
2044 | for (i = 0; i < count ; i++) | |
2045 | { | |
2046 | struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); | |
2047 | struct ipa_agg_jump_function *ajf; | |
2048 | struct ipcp_agg_lattice *aglat; | |
2049 | ||
2050 | if (plats->aggs_bottom || !plats->aggs) | |
2051 | continue; | |
2052 | ||
f1f41a6c | 2053 | ajf = &known_aggs[i]; |
803a7988 | 2054 | for (aglat = plats->aggs; aglat; aglat = aglat->next) |
2055 | { | |
2056 | struct ipcp_value *val; | |
2057 | if (aglat->bottom || !aglat->values | |
2058 | /* If the following is true, the one value is in known_aggs. */ | |
2059 | || (!plats->aggs_contain_variable | |
2060 | && ipa_lat_is_single_const (aglat))) | |
2061 | continue; | |
2062 | ||
2063 | for (val = aglat->values; val; val = val->next) | |
2064 | { | |
2065 | int time, size, time_benefit; | |
2066 | struct ipa_agg_jf_item item; | |
2067 | inline_hints hints; | |
2068 | ||
2069 | item.offset = aglat->offset; | |
2070 | item.value = val->value; | |
f1f41a6c | 2071 | vec_safe_push (ajf->items, item); |
803a7988 | 2072 | |
2073 | estimate_ipcp_clone_size_and_time (node, known_csts, known_binfos, | |
2074 | known_aggs_ptrs, &size, &time, | |
2075 | &hints); | |
2076 | time_benefit = base_time - time | |
265c4eb2 | 2077 | + devirtualization_time_bonus (node, known_csts, known_binfos, |
2078 | known_aggs_ptrs) | |
803a7988 | 2079 | + hint_time_bonus (hints); |
2080 | gcc_checking_assert (size >=0); | |
2081 | if (size == 0) | |
2082 | size = 1; | |
2083 | ||
2084 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2085 | { | |
2086 | fprintf (dump_file, " - estimates for value "); | |
2087 | print_ipcp_constant_value (dump_file, val->value); | |
09ab6335 | 2088 | fprintf (dump_file, " for "); |
2089 | ipa_dump_param (dump_file, info, i); | |
803a7988 | 2090 | fprintf (dump_file, "[%soffset: " HOST_WIDE_INT_PRINT_DEC |
2091 | "]: time_benefit: %i, size: %i\n", | |
2092 | plats->aggs_by_ref ? "ref " : "", | |
2093 | aglat->offset, time_benefit, size); | |
2094 | } | |
2095 | ||
2096 | val->local_time_benefit = time_benefit; | |
2097 | val->local_size_cost = size; | |
f1f41a6c | 2098 | ajf->items->pop (); |
803a7988 | 2099 | } |
2100 | } | |
2101 | } | |
2102 | ||
2103 | for (i = 0; i < count ; i++) | |
f1f41a6c | 2104 | vec_free (known_aggs[i].items); |
821d0e0f | 2105 | |
f1f41a6c | 2106 | known_csts.release (); |
2107 | known_binfos.release (); | |
2108 | known_aggs.release (); | |
2109 | known_aggs_ptrs.release (); | |
821d0e0f | 2110 | } |
2111 | ||
2112 | ||
2113 | /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the | |
2114 | topological sort of values. */ | |
2115 | ||
2116 | static void | |
2117 | add_val_to_toposort (struct ipcp_value *cur_val) | |
2118 | { | |
2119 | static int dfs_counter = 0; | |
2120 | static struct ipcp_value *stack; | |
2121 | struct ipcp_value_source *src; | |
2122 | ||
2123 | if (cur_val->dfs) | |
2124 | return; | |
2125 | ||
2126 | dfs_counter++; | |
2127 | cur_val->dfs = dfs_counter; | |
2128 | cur_val->low_link = dfs_counter; | |
2129 | ||
2130 | cur_val->topo_next = stack; | |
2131 | stack = cur_val; | |
2132 | cur_val->on_stack = true; | |
2133 | ||
2134 | for (src = cur_val->sources; src; src = src->next) | |
2135 | if (src->val) | |
2136 | { | |
2137 | if (src->val->dfs == 0) | |
2138 | { | |
2139 | add_val_to_toposort (src->val); | |
2140 | if (src->val->low_link < cur_val->low_link) | |
2141 | cur_val->low_link = src->val->low_link; | |
2142 | } | |
2143 | else if (src->val->on_stack | |
2144 | && src->val->dfs < cur_val->low_link) | |
2145 | cur_val->low_link = src->val->dfs; | |
2146 | } | |
2147 | ||
2148 | if (cur_val->dfs == cur_val->low_link) | |
11b73810 | 2149 | { |
821d0e0f | 2150 | struct ipcp_value *v, *scc_list = NULL; |
2151 | ||
2152 | do | |
2153 | { | |
2154 | v = stack; | |
2155 | stack = v->topo_next; | |
2156 | v->on_stack = false; | |
2157 | ||
2158 | v->scc_next = scc_list; | |
2159 | scc_list = v; | |
2160 | } | |
2161 | while (v != cur_val); | |
2162 | ||
2163 | cur_val->topo_next = values_topo; | |
2164 | values_topo = cur_val; | |
11b73810 | 2165 | } |
3b22db66 | 2166 | } |
2167 | ||
821d0e0f | 2168 | /* Add all values in lattices associated with NODE to the topological sort if |
2169 | they are not there yet. */ | |
2170 | ||
2171 | static void | |
2172 | add_all_node_vals_to_toposort (struct cgraph_node *node) | |
3b22db66 | 2173 | { |
821d0e0f | 2174 | struct ipa_node_params *info = IPA_NODE_REF (node); |
2175 | int i, count = ipa_get_param_count (info); | |
2176 | ||
2177 | for (i = 0; i < count ; i++) | |
2178 | { | |
803a7988 | 2179 | struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); |
2180 | struct ipcp_lattice *lat = &plats->itself; | |
2181 | struct ipcp_agg_lattice *aglat; | |
821d0e0f | 2182 | struct ipcp_value *val; |
2183 | ||
803a7988 | 2184 | if (!lat->bottom) |
2185 | for (val = lat->values; val; val = val->next) | |
2186 | add_val_to_toposort (val); | |
2187 | ||
2188 | if (!plats->aggs_bottom) | |
2189 | for (aglat = plats->aggs; aglat; aglat = aglat->next) | |
2190 | if (!aglat->bottom) | |
2191 | for (val = aglat->values; val; val = val->next) | |
2192 | add_val_to_toposort (val); | |
821d0e0f | 2193 | } |
3b22db66 | 2194 | } |
2195 | ||
821d0e0f | 2196 | /* One pass of constants propagation along the call graph edges, from callers |
2197 | to callees (requires topological ordering in TOPO), iterate over strongly | |
2198 | connected components. */ | |
2199 | ||
3b22db66 | 2200 | static void |
821d0e0f | 2201 | propagate_constants_topo (struct topo_info *topo) |
3b22db66 | 2202 | { |
821d0e0f | 2203 | int i; |
3b22db66 | 2204 | |
821d0e0f | 2205 | for (i = topo->nnodes - 1; i >= 0; i--) |
3b22db66 | 2206 | { |
3ffe0ea9 | 2207 | unsigned j; |
821d0e0f | 2208 | struct cgraph_node *v, *node = topo->order[i]; |
3ffe0ea9 | 2209 | vec<cgraph_node_ptr> cycle_nodes = ipa_get_nodes_in_cycle (node); |
821d0e0f | 2210 | |
821d0e0f | 2211 | /* First, iteratively propagate within the strongly connected component |
2212 | until all lattices stabilize. */ | |
3ffe0ea9 | 2213 | FOR_EACH_VEC_ELT (cycle_nodes, j, v) |
2214 | if (cgraph_function_with_gimple_body_p (v)) | |
821d0e0f | 2215 | push_node_to_stack (topo, v); |
821d0e0f | 2216 | |
3ffe0ea9 | 2217 | v = pop_node_from_stack (topo); |
821d0e0f | 2218 | while (v) |
2219 | { | |
2220 | struct cgraph_edge *cs; | |
2221 | ||
2222 | for (cs = v->callees; cs; cs = cs->next_callee) | |
a0255a70 | 2223 | if (ipa_edge_within_scc (cs) |
821d0e0f | 2224 | && propagate_constants_accross_call (cs)) |
2225 | push_node_to_stack (topo, cs->callee); | |
2226 | v = pop_node_from_stack (topo); | |
2227 | } | |
2228 | ||
2229 | /* Afterwards, propagate along edges leading out of the SCC, calculates | |
2230 | the local effects of the discovered constants and all valid values to | |
2231 | their topological sort. */ | |
3ffe0ea9 | 2232 | FOR_EACH_VEC_ELT (cycle_nodes, j, v) |
2233 | if (cgraph_function_with_gimple_body_p (v)) | |
2234 | { | |
2235 | struct cgraph_edge *cs; | |
821d0e0f | 2236 | |
3ffe0ea9 | 2237 | estimate_local_effects (v); |
2238 | add_all_node_vals_to_toposort (v); | |
2239 | for (cs = v->callees; cs; cs = cs->next_callee) | |
a0255a70 | 2240 | if (!ipa_edge_within_scc (cs)) |
3ffe0ea9 | 2241 | propagate_constants_accross_call (cs); |
2242 | } | |
2243 | cycle_nodes.release (); | |
3b22db66 | 2244 | } |
2245 | } | |
2246 | ||
29bb06c7 | 2247 | |
2248 | /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return | |
2249 | the bigger one if otherwise. */ | |
2250 | ||
2251 | static int | |
2252 | safe_add (int a, int b) | |
2253 | { | |
2254 | if (a > INT_MAX/2 || b > INT_MAX/2) | |
2255 | return a > b ? a : b; | |
2256 | else | |
2257 | return a + b; | |
2258 | } | |
2259 | ||
2260 | ||
821d0e0f | 2261 | /* Propagate the estimated effects of individual values along the topological |
9d75589a | 2262 | from the dependent values to those they depend on. */ |
821d0e0f | 2263 | |
3b22db66 | 2264 | static void |
821d0e0f | 2265 | propagate_effects (void) |
3b22db66 | 2266 | { |
821d0e0f | 2267 | struct ipcp_value *base; |
3b22db66 | 2268 | |
821d0e0f | 2269 | for (base = values_topo; base; base = base->topo_next) |
3b22db66 | 2270 | { |
821d0e0f | 2271 | struct ipcp_value_source *src; |
2272 | struct ipcp_value *val; | |
2273 | int time = 0, size = 0; | |
2274 | ||
2275 | for (val = base; val; val = val->scc_next) | |
2276 | { | |
29bb06c7 | 2277 | time = safe_add (time, |
2278 | val->local_time_benefit + val->prop_time_benefit); | |
2279 | size = safe_add (size, val->local_size_cost + val->prop_size_cost); | |
821d0e0f | 2280 | } |
2281 | ||
2282 | for (val = base; val; val = val->scc_next) | |
2283 | for (src = val->sources; src; src = src->next) | |
2284 | if (src->val | |
2285 | && cgraph_maybe_hot_edge_p (src->cs)) | |
2286 | { | |
29bb06c7 | 2287 | src->val->prop_time_benefit = safe_add (time, |
2288 | src->val->prop_time_benefit); | |
2289 | src->val->prop_size_cost = safe_add (size, | |
2290 | src->val->prop_size_cost); | |
821d0e0f | 2291 | } |
3b22db66 | 2292 | } |
2293 | } | |
2294 | ||
821d0e0f | 2295 | |
2296 | /* Propagate constants, binfos and their effects from the summaries | |
2297 | interprocedurally. */ | |
2298 | ||
3b22db66 | 2299 | static void |
821d0e0f | 2300 | ipcp_propagate_stage (struct topo_info *topo) |
3b22db66 | 2301 | { |
2302 | struct cgraph_node *node; | |
3b22db66 | 2303 | |
821d0e0f | 2304 | if (dump_file) |
2305 | fprintf (dump_file, "\n Propagating constants:\n\n"); | |
2306 | ||
2307 | if (in_lto_p) | |
2308 | ipa_update_after_lto_read (); | |
2309 | ||
2310 | ||
2311 | FOR_EACH_DEFINED_FUNCTION (node) | |
2312 | { | |
2313 | struct ipa_node_params *info = IPA_NODE_REF (node); | |
2314 | ||
2315 | determine_versionability (node); | |
2316 | if (cgraph_function_with_gimple_body_p (node)) | |
2317 | { | |
803a7988 | 2318 | info->lattices = XCNEWVEC (struct ipcp_param_lattices, |
821d0e0f | 2319 | ipa_get_param_count (info)); |
2320 | initialize_node_lattices (node); | |
2321 | } | |
02774f2d | 2322 | if (node->definition && !node->alias) |
15ca8f90 | 2323 | overall_size += inline_summary (node)->self_size; |
821d0e0f | 2324 | if (node->count > max_count) |
2325 | max_count = node->count; | |
821d0e0f | 2326 | } |
2327 | ||
2328 | max_new_size = overall_size; | |
2329 | if (max_new_size < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS)) | |
2330 | max_new_size = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS); | |
2331 | max_new_size += max_new_size * PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH) / 100 + 1; | |
2332 | ||
2333 | if (dump_file) | |
2334 | fprintf (dump_file, "\noverall_size: %li, max_new_size: %li\n", | |
2335 | overall_size, max_new_size); | |
2336 | ||
2337 | propagate_constants_topo (topo); | |
2338 | #ifdef ENABLE_CHECKING | |
2339 | ipcp_verify_propagated_values (); | |
2340 | #endif | |
2341 | propagate_effects (); | |
2342 | ||
2343 | if (dump_file) | |
2344 | { | |
2345 | fprintf (dump_file, "\nIPA lattices after all propagation:\n"); | |
2346 | print_all_lattices (dump_file, (dump_flags & TDF_DETAILS), true); | |
2347 | } | |
2348 | } | |
2349 | ||
2350 | /* Discover newly direct outgoing edges from NODE which is a new clone with | |
2351 | known KNOWN_VALS and make them direct. */ | |
2352 | ||
2353 | static void | |
2354 | ipcp_discover_new_direct_edges (struct cgraph_node *node, | |
265c4eb2 | 2355 | vec<tree> known_vals, |
2356 | struct ipa_agg_replacement_value *aggvals) | |
821d0e0f | 2357 | { |
2358 | struct cgraph_edge *ie, *next_ie; | |
18b64b34 | 2359 | bool found = false; |
821d0e0f | 2360 | |
2361 | for (ie = node->indirect_calls; ie; ie = next_ie) | |
2362 | { | |
d4e80e2b | 2363 | tree target; |
821d0e0f | 2364 | |
2365 | next_ie = ie->next_callee; | |
265c4eb2 | 2366 | target = ipa_get_indirect_edge_target_1 (ie, known_vals, vNULL, vNULL, |
2367 | aggvals); | |
821d0e0f | 2368 | if (target) |
18b64b34 | 2369 | { |
4d044066 | 2370 | bool agg_contents = ie->indirect_info->agg_contents; |
2371 | bool polymorphic = ie->indirect_info->polymorphic; | |
436b29f7 | 2372 | int param_index = ie->indirect_info->param_index; |
096295f6 | 2373 | struct cgraph_edge *cs = ipa_make_edge_direct_to_target (ie, target); |
18b64b34 | 2374 | found = true; |
096295f6 | 2375 | |
4d044066 | 2376 | if (cs && !agg_contents && !polymorphic) |
096295f6 | 2377 | { |
2378 | struct ipa_node_params *info = IPA_NODE_REF (node); | |
096295f6 | 2379 | int c = ipa_get_controlled_uses (info, param_index); |
2380 | if (c != IPA_UNDESCRIBED_USE) | |
2381 | { | |
2382 | struct ipa_ref *to_del; | |
2383 | ||
2384 | c--; | |
2385 | ipa_set_controlled_uses (info, param_index, c); | |
2386 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2387 | fprintf (dump_file, " controlled uses count of param " | |
2388 | "%i bumped down to %i\n", param_index, c); | |
2389 | if (c == 0 | |
02774f2d | 2390 | && (to_del = ipa_find_reference (node, |
2391 | cs->callee, | |
4d044066 | 2392 | NULL, 0))) |
096295f6 | 2393 | { |
2394 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2395 | fprintf (dump_file, " and even removing its " | |
2396 | "cloning-created reference\n"); | |
2397 | ipa_remove_reference (to_del); | |
2398 | } | |
2399 | } | |
2400 | } | |
18b64b34 | 2401 | } |
821d0e0f | 2402 | } |
18b64b34 | 2403 | /* Turning calls to direct calls will improve overall summary. */ |
2404 | if (found) | |
2405 | inline_update_overall_summary (node); | |
821d0e0f | 2406 | } |
2407 | ||
2408 | /* Vector of pointers which for linked lists of clones of an original crgaph | |
2409 | edge. */ | |
2410 | ||
f1f41a6c | 2411 | static vec<cgraph_edge_p> next_edge_clone; |
948ccfa6 | 2412 | static vec<cgraph_edge_p> prev_edge_clone; |
821d0e0f | 2413 | |
2414 | static inline void | |
948ccfa6 | 2415 | grow_edge_clone_vectors (void) |
821d0e0f | 2416 | { |
f1f41a6c | 2417 | if (next_edge_clone.length () |
821d0e0f | 2418 | <= (unsigned) cgraph_edge_max_uid) |
f1f41a6c | 2419 | next_edge_clone.safe_grow_cleared (cgraph_edge_max_uid + 1); |
948ccfa6 | 2420 | if (prev_edge_clone.length () |
2421 | <= (unsigned) cgraph_edge_max_uid) | |
2422 | prev_edge_clone.safe_grow_cleared (cgraph_edge_max_uid + 1); | |
821d0e0f | 2423 | } |
2424 | ||
2425 | /* Edge duplication hook to grow the appropriate linked list in | |
2426 | next_edge_clone. */ | |
2427 | ||
2428 | static void | |
2429 | ipcp_edge_duplication_hook (struct cgraph_edge *src, struct cgraph_edge *dst, | |
948ccfa6 | 2430 | void *) |
821d0e0f | 2431 | { |
948ccfa6 | 2432 | grow_edge_clone_vectors (); |
2433 | ||
2434 | struct cgraph_edge *old_next = next_edge_clone[src->uid]; | |
2435 | if (old_next) | |
2436 | prev_edge_clone[old_next->uid] = dst; | |
2437 | prev_edge_clone[dst->uid] = src; | |
2438 | ||
2439 | next_edge_clone[dst->uid] = old_next; | |
f1f41a6c | 2440 | next_edge_clone[src->uid] = dst; |
821d0e0f | 2441 | } |
2442 | ||
948ccfa6 | 2443 | /* Hook that is called by cgraph.c when an edge is removed. */ |
2444 | ||
2445 | static void | |
2446 | ipcp_edge_removal_hook (struct cgraph_edge *cs, void *) | |
2447 | { | |
2448 | grow_edge_clone_vectors (); | |
2449 | ||
2450 | struct cgraph_edge *prev = prev_edge_clone[cs->uid]; | |
2451 | struct cgraph_edge *next = next_edge_clone[cs->uid]; | |
2452 | if (prev) | |
2453 | next_edge_clone[prev->uid] = next; | |
2454 | if (next) | |
2455 | prev_edge_clone[next->uid] = prev; | |
2456 | } | |
2457 | ||
803a7988 | 2458 | /* See if NODE is a clone with a known aggregate value at a given OFFSET of a |
2459 | parameter with the given INDEX. */ | |
821d0e0f | 2460 | |
803a7988 | 2461 | static tree |
2462 | get_clone_agg_value (struct cgraph_node *node, HOST_WIDEST_INT offset, | |
2463 | int index) | |
821d0e0f | 2464 | { |
803a7988 | 2465 | struct ipa_agg_replacement_value *aggval; |
2466 | ||
2467 | aggval = ipa_get_agg_replacements_for_node (node); | |
2468 | while (aggval) | |
2469 | { | |
2470 | if (aggval->offset == offset | |
2471 | && aggval->index == index) | |
2472 | return aggval->value; | |
2473 | aggval = aggval->next; | |
2474 | } | |
2475 | return NULL_TREE; | |
821d0e0f | 2476 | } |
2477 | ||
2478 | /* Return true if edge CS does bring about the value described by SRC. */ | |
2479 | ||
2480 | static bool | |
2481 | cgraph_edge_brings_value_p (struct cgraph_edge *cs, | |
2482 | struct ipcp_value_source *src) | |
2483 | { | |
2484 | struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller); | |
87228246 | 2485 | struct ipa_node_params *dst_info = IPA_NODE_REF (cs->callee); |
821d0e0f | 2486 | |
87228246 | 2487 | if ((dst_info->ipcp_orig_node && !dst_info->is_all_contexts_clone) |
821d0e0f | 2488 | || caller_info->node_dead) |
2489 | return false; | |
2490 | if (!src->val) | |
2491 | return true; | |
2492 | ||
2493 | if (caller_info->ipcp_orig_node) | |
2494 | { | |
803a7988 | 2495 | tree t; |
2496 | if (src->offset == -1) | |
f1f41a6c | 2497 | t = caller_info->known_vals[src->index]; |
803a7988 | 2498 | else |
2499 | t = get_clone_agg_value (cs->caller, src->offset, src->index); | |
821d0e0f | 2500 | return (t != NULL_TREE |
2501 | && values_equal_for_ipcp_p (src->val->value, t)); | |
2502 | } | |
2503 | else | |
3b22db66 | 2504 | { |
803a7988 | 2505 | struct ipcp_agg_lattice *aglat; |
2506 | struct ipcp_param_lattices *plats = ipa_get_parm_lattices (caller_info, | |
2507 | src->index); | |
2508 | if (src->offset == -1) | |
2509 | return (ipa_lat_is_single_const (&plats->itself) | |
2510 | && values_equal_for_ipcp_p (src->val->value, | |
2511 | plats->itself.values->value)); | |
821d0e0f | 2512 | else |
803a7988 | 2513 | { |
2514 | if (plats->aggs_bottom || plats->aggs_contain_variable) | |
2515 | return false; | |
2516 | for (aglat = plats->aggs; aglat; aglat = aglat->next) | |
2517 | if (aglat->offset == src->offset) | |
2518 | return (ipa_lat_is_single_const (aglat) | |
2519 | && values_equal_for_ipcp_p (src->val->value, | |
2520 | aglat->values->value)); | |
2521 | } | |
2522 | return false; | |
821d0e0f | 2523 | } |
2524 | } | |
2525 | ||
803a7988 | 2526 | /* Get the next clone in the linked list of clones of an edge. */ |
2527 | ||
2528 | static inline struct cgraph_edge * | |
2529 | get_next_cgraph_edge_clone (struct cgraph_edge *cs) | |
2530 | { | |
f1f41a6c | 2531 | return next_edge_clone[cs->uid]; |
803a7988 | 2532 | } |
2533 | ||
821d0e0f | 2534 | /* Given VAL, iterate over all its sources and if they still hold, add their |
2535 | edge frequency and their number into *FREQUENCY and *CALLER_COUNT | |
2536 | respectively. */ | |
2537 | ||
2538 | static bool | |
2539 | get_info_about_necessary_edges (struct ipcp_value *val, int *freq_sum, | |
2540 | gcov_type *count_sum, int *caller_count) | |
2541 | { | |
2542 | struct ipcp_value_source *src; | |
2543 | int freq = 0, count = 0; | |
2544 | gcov_type cnt = 0; | |
2545 | bool hot = false; | |
2546 | ||
2547 | for (src = val->sources; src; src = src->next) | |
2548 | { | |
2549 | struct cgraph_edge *cs = src->cs; | |
2550 | while (cs) | |
3b22db66 | 2551 | { |
821d0e0f | 2552 | if (cgraph_edge_brings_value_p (cs, src)) |
2553 | { | |
2554 | count++; | |
2555 | freq += cs->frequency; | |
2556 | cnt += cs->count; | |
2557 | hot |= cgraph_maybe_hot_edge_p (cs); | |
2558 | } | |
2559 | cs = get_next_cgraph_edge_clone (cs); | |
3b22db66 | 2560 | } |
2561 | } | |
821d0e0f | 2562 | |
2563 | *freq_sum = freq; | |
2564 | *count_sum = cnt; | |
2565 | *caller_count = count; | |
2566 | return hot; | |
3b22db66 | 2567 | } |
2568 | ||
821d0e0f | 2569 | /* Return a vector of incoming edges that do bring value VAL. It is assumed |
2570 | their number is known and equal to CALLER_COUNT. */ | |
2571 | ||
f1f41a6c | 2572 | static vec<cgraph_edge_p> |
821d0e0f | 2573 | gather_edges_for_value (struct ipcp_value *val, int caller_count) |
3b22db66 | 2574 | { |
821d0e0f | 2575 | struct ipcp_value_source *src; |
f1f41a6c | 2576 | vec<cgraph_edge_p> ret; |
821d0e0f | 2577 | |
f1f41a6c | 2578 | ret.create (caller_count); |
821d0e0f | 2579 | for (src = val->sources; src; src = src->next) |
2580 | { | |
2581 | struct cgraph_edge *cs = src->cs; | |
2582 | while (cs) | |
2583 | { | |
2584 | if (cgraph_edge_brings_value_p (cs, src)) | |
f1f41a6c | 2585 | ret.quick_push (cs); |
821d0e0f | 2586 | cs = get_next_cgraph_edge_clone (cs); |
2587 | } | |
2588 | } | |
2589 | ||
2590 | return ret; | |
3b22db66 | 2591 | } |
2592 | ||
821d0e0f | 2593 | /* Construct a replacement map for a know VALUE for a formal parameter PARAM. |
2594 | Return it or NULL if for some reason it cannot be created. */ | |
2595 | ||
3b22db66 | 2596 | static struct ipa_replace_map * |
09ab6335 | 2597 | get_replacement_map (struct ipa_node_params *info, tree value, int parm_num) |
3b22db66 | 2598 | { |
2599 | struct ipa_replace_map *replace_map; | |
3b22db66 | 2600 | |
821d0e0f | 2601 | |
25a27413 | 2602 | replace_map = ggc_alloc<ipa_replace_map> (); |
5afe38fe | 2603 | if (dump_file) |
2604 | { | |
09ab6335 | 2605 | fprintf (dump_file, " replacing "); |
2606 | ipa_dump_param (dump_file, info, parm_num); | |
2607 | ||
5afe38fe | 2608 | fprintf (dump_file, " with const "); |
821d0e0f | 2609 | print_generic_expr (dump_file, value, 0); |
5afe38fe | 2610 | fprintf (dump_file, "\n"); |
2611 | } | |
79e830ee | 2612 | replace_map->old_tree = NULL; |
2613 | replace_map->parm_num = parm_num; | |
821d0e0f | 2614 | replace_map->new_tree = value; |
13e50f08 | 2615 | replace_map->replace_p = true; |
2616 | replace_map->ref_p = false; | |
3b22db66 | 2617 | |
2618 | return replace_map; | |
2619 | } | |
2620 | ||
821d0e0f | 2621 | /* Dump new profiling counts */ |
3b22db66 | 2622 | |
3b22db66 | 2623 | static void |
821d0e0f | 2624 | dump_profile_updates (struct cgraph_node *orig_node, |
2625 | struct cgraph_node *new_node) | |
3b22db66 | 2626 | { |
821d0e0f | 2627 | struct cgraph_edge *cs; |
3b22db66 | 2628 | |
821d0e0f | 2629 | fprintf (dump_file, " setting count of the specialized node to " |
2630 | HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) new_node->count); | |
2631 | for (cs = new_node->callees; cs ; cs = cs->next_callee) | |
2632 | fprintf (dump_file, " edge to %s has count " | |
2633 | HOST_WIDE_INT_PRINT_DEC "\n", | |
f1c8b4d7 | 2634 | cs->callee->name (), (HOST_WIDE_INT) cs->count); |
821d0e0f | 2635 | |
2636 | fprintf (dump_file, " setting count of the original node to " | |
2637 | HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) orig_node->count); | |
2638 | for (cs = orig_node->callees; cs ; cs = cs->next_callee) | |
2639 | fprintf (dump_file, " edge to %s is left with " | |
2640 | HOST_WIDE_INT_PRINT_DEC "\n", | |
f1c8b4d7 | 2641 | cs->callee->name (), (HOST_WIDE_INT) cs->count); |
821d0e0f | 2642 | } |
5afe38fe | 2643 | |
821d0e0f | 2644 | /* After a specialized NEW_NODE version of ORIG_NODE has been created, update |
2645 | their profile information to reflect this. */ | |
3b22db66 | 2646 | |
3b22db66 | 2647 | static void |
821d0e0f | 2648 | update_profiling_info (struct cgraph_node *orig_node, |
2649 | struct cgraph_node *new_node) | |
3b22db66 | 2650 | { |
3b22db66 | 2651 | struct cgraph_edge *cs; |
821d0e0f | 2652 | struct caller_statistics stats; |
2653 | gcov_type new_sum, orig_sum; | |
2654 | gcov_type remainder, orig_node_count = orig_node->count; | |
2655 | ||
2656 | if (orig_node_count == 0) | |
2657 | return; | |
3b22db66 | 2658 | |
821d0e0f | 2659 | init_caller_stats (&stats); |
2660 | cgraph_for_node_and_aliases (orig_node, gather_caller_stats, &stats, false); | |
2661 | orig_sum = stats.count_sum; | |
2662 | init_caller_stats (&stats); | |
2663 | cgraph_for_node_and_aliases (new_node, gather_caller_stats, &stats, false); | |
2664 | new_sum = stats.count_sum; | |
2665 | ||
2666 | if (orig_node_count < orig_sum + new_sum) | |
3b22db66 | 2667 | { |
821d0e0f | 2668 | if (dump_file) |
2669 | fprintf (dump_file, " Problem: node %s/%i has too low count " | |
2670 | HOST_WIDE_INT_PRINT_DEC " while the sum of incoming " | |
2671 | "counts is " HOST_WIDE_INT_PRINT_DEC "\n", | |
f1c8b4d7 | 2672 | orig_node->name (), orig_node->order, |
821d0e0f | 2673 | (HOST_WIDE_INT) orig_node_count, |
2674 | (HOST_WIDE_INT) (orig_sum + new_sum)); | |
2675 | ||
2676 | orig_node_count = (orig_sum + new_sum) * 12 / 10; | |
2677 | if (dump_file) | |
2678 | fprintf (dump_file, " proceeding by pretending it was " | |
2679 | HOST_WIDE_INT_PRINT_DEC "\n", | |
2680 | (HOST_WIDE_INT) orig_node_count); | |
3b22db66 | 2681 | } |
821d0e0f | 2682 | |
2683 | new_node->count = new_sum; | |
2684 | remainder = orig_node_count - new_sum; | |
2685 | orig_node->count = remainder; | |
2686 | ||
2687 | for (cs = new_node->callees; cs ; cs = cs->next_callee) | |
2688 | if (cs->frequency) | |
f9d4b7f4 | 2689 | cs->count = apply_probability (cs->count, |
2690 | GCOV_COMPUTE_SCALE (new_sum, | |
2691 | orig_node_count)); | |
821d0e0f | 2692 | else |
2693 | cs->count = 0; | |
2694 | ||
2695 | for (cs = orig_node->callees; cs ; cs = cs->next_callee) | |
f9d4b7f4 | 2696 | cs->count = apply_probability (cs->count, |
2697 | GCOV_COMPUTE_SCALE (remainder, | |
2698 | orig_node_count)); | |
821d0e0f | 2699 | |
2700 | if (dump_file) | |
2701 | dump_profile_updates (orig_node, new_node); | |
3b22db66 | 2702 | } |
2703 | ||
821d0e0f | 2704 | /* Update the respective profile of specialized NEW_NODE and the original |
2705 | ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM | |
2706 | have been redirected to the specialized version. */ | |
2707 | ||
2708 | static void | |
2709 | update_specialized_profile (struct cgraph_node *new_node, | |
2710 | struct cgraph_node *orig_node, | |
2711 | gcov_type redirected_sum) | |
2a15795f | 2712 | { |
614b82b2 | 2713 | struct cgraph_edge *cs; |
821d0e0f | 2714 | gcov_type new_node_count, orig_node_count = orig_node->count; |
2a15795f | 2715 | |
821d0e0f | 2716 | if (dump_file) |
2717 | fprintf (dump_file, " the sum of counts of redirected edges is " | |
2718 | HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) redirected_sum); | |
2719 | if (orig_node_count == 0) | |
2720 | return; | |
614b82b2 | 2721 | |
821d0e0f | 2722 | gcc_assert (orig_node_count >= redirected_sum); |
2a15795f | 2723 | |
821d0e0f | 2724 | new_node_count = new_node->count; |
2725 | new_node->count += redirected_sum; | |
2726 | orig_node->count -= redirected_sum; | |
614b82b2 | 2727 | |
821d0e0f | 2728 | for (cs = new_node->callees; cs ; cs = cs->next_callee) |
2729 | if (cs->frequency) | |
f9d4b7f4 | 2730 | cs->count += apply_probability (cs->count, |
2731 | GCOV_COMPUTE_SCALE (redirected_sum, | |
2732 | new_node_count)); | |
821d0e0f | 2733 | else |
2734 | cs->count = 0; | |
614b82b2 | 2735 | |
821d0e0f | 2736 | for (cs = orig_node->callees; cs ; cs = cs->next_callee) |
2737 | { | |
f9d4b7f4 | 2738 | gcov_type dec = apply_probability (cs->count, |
2739 | GCOV_COMPUTE_SCALE (redirected_sum, | |
2740 | orig_node_count)); | |
821d0e0f | 2741 | if (dec < cs->count) |
2742 | cs->count -= dec; | |
2743 | else | |
2744 | cs->count = 0; | |
2745 | } | |
614b82b2 | 2746 | |
821d0e0f | 2747 | if (dump_file) |
2748 | dump_profile_updates (orig_node, new_node); | |
2a15795f | 2749 | } |
2750 | ||
821d0e0f | 2751 | /* Create a specialized version of NODE with known constants and types of |
2752 | parameters in KNOWN_VALS and redirect all edges in CALLERS to it. */ | |
614b82b2 | 2753 | |
821d0e0f | 2754 | static struct cgraph_node * |
2755 | create_specialized_node (struct cgraph_node *node, | |
f1f41a6c | 2756 | vec<tree> known_vals, |
803a7988 | 2757 | struct ipa_agg_replacement_value *aggvals, |
f1f41a6c | 2758 | vec<cgraph_edge_p> callers) |
2a15795f | 2759 | { |
821d0e0f | 2760 | struct ipa_node_params *new_info, *info = IPA_NODE_REF (node); |
f1f41a6c | 2761 | vec<ipa_replace_map_p, va_gc> *replace_trees = NULL; |
3c0fe71b | 2762 | struct ipa_agg_replacement_value *av; |
821d0e0f | 2763 | struct cgraph_node *new_node; |
2764 | int i, count = ipa_get_param_count (info); | |
2765 | bitmap args_to_skip; | |
2a15795f | 2766 | |
821d0e0f | 2767 | gcc_assert (!info->ipcp_orig_node); |
2768 | ||
2769 | if (node->local.can_change_signature) | |
2a15795f | 2770 | { |
821d0e0f | 2771 | args_to_skip = BITMAP_GGC_ALLOC (); |
2772 | for (i = 0; i < count; i++) | |
2773 | { | |
f1f41a6c | 2774 | tree t = known_vals[i]; |
821d0e0f | 2775 | |
2776 | if ((t && TREE_CODE (t) != TREE_BINFO) | |
2777 | || !ipa_is_param_used (info, i)) | |
2778 | bitmap_set_bit (args_to_skip, i); | |
2779 | } | |
2780 | } | |
2781 | else | |
03f99d3c | 2782 | { |
2783 | args_to_skip = NULL; | |
2784 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2785 | fprintf (dump_file, " cannot change function signature\n"); | |
2786 | } | |
821d0e0f | 2787 | |
2788 | for (i = 0; i < count ; i++) | |
2789 | { | |
f1f41a6c | 2790 | tree t = known_vals[i]; |
821d0e0f | 2791 | if (t && TREE_CODE (t) != TREE_BINFO) |
2792 | { | |
2793 | struct ipa_replace_map *replace_map; | |
2794 | ||
09ab6335 | 2795 | replace_map = get_replacement_map (info, t, i); |
821d0e0f | 2796 | if (replace_map) |
f1f41a6c | 2797 | vec_safe_push (replace_trees, replace_map); |
821d0e0f | 2798 | } |
2a15795f | 2799 | } |
2800 | ||
821d0e0f | 2801 | new_node = cgraph_create_virtual_clone (node, callers, replace_trees, |
2802 | args_to_skip, "constprop"); | |
803a7988 | 2803 | ipa_set_node_agg_value_chain (new_node, aggvals); |
3c0fe71b | 2804 | for (av = aggvals; av; av = av->next) |
02774f2d | 2805 | ipa_maybe_record_reference (new_node, av->value, |
3c0fe71b | 2806 | IPA_REF_ADDR, NULL); |
2807 | ||
821d0e0f | 2808 | if (dump_file && (dump_flags & TDF_DETAILS)) |
803a7988 | 2809 | { |
2810 | fprintf (dump_file, " the new node is %s/%i.\n", | |
f1c8b4d7 | 2811 | new_node->name (), new_node->order); |
803a7988 | 2812 | if (aggvals) |
2813 | ipa_dump_agg_replacement_values (dump_file, aggvals); | |
2814 | } | |
5a7ad253 | 2815 | ipa_check_create_node_params (); |
821d0e0f | 2816 | update_profiling_info (node, new_node); |
2817 | new_info = IPA_NODE_REF (new_node); | |
2818 | new_info->ipcp_orig_node = node; | |
2819 | new_info->known_vals = known_vals; | |
2a15795f | 2820 | |
265c4eb2 | 2821 | ipcp_discover_new_direct_edges (new_node, known_vals, aggvals); |
821d0e0f | 2822 | |
f1f41a6c | 2823 | callers.release (); |
821d0e0f | 2824 | return new_node; |
2a15795f | 2825 | } |
2826 | ||
821d0e0f | 2827 | /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in |
2828 | KNOWN_VALS with constants and types that are also known for all of the | |
2829 | CALLERS. */ | |
1caef38b | 2830 | |
2831 | static void | |
803a7988 | 2832 | find_more_scalar_values_for_callers_subset (struct cgraph_node *node, |
f1f41a6c | 2833 | vec<tree> known_vals, |
2834 | vec<cgraph_edge_p> callers) | |
1caef38b | 2835 | { |
2836 | struct ipa_node_params *info = IPA_NODE_REF (node); | |
821d0e0f | 2837 | int i, count = ipa_get_param_count (info); |
1caef38b | 2838 | |
821d0e0f | 2839 | for (i = 0; i < count ; i++) |
1caef38b | 2840 | { |
821d0e0f | 2841 | struct cgraph_edge *cs; |
2842 | tree newval = NULL_TREE; | |
2843 | int j; | |
1caef38b | 2844 | |
f1f41a6c | 2845 | if (ipa_get_scalar_lat (info, i)->bottom || known_vals[i]) |
1caef38b | 2846 | continue; |
2847 | ||
f1f41a6c | 2848 | FOR_EACH_VEC_ELT (callers, j, cs) |
3658fd1d | 2849 | { |
821d0e0f | 2850 | struct ipa_jump_func *jump_func; |
2851 | tree t; | |
09a2b4db | 2852 | |
c8fc6b84 | 2853 | if (i >= ipa_get_cs_argument_count (IPA_EDGE_REF (cs))) |
2854 | { | |
2855 | newval = NULL_TREE; | |
2856 | break; | |
2857 | } | |
821d0e0f | 2858 | jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i); |
821d0e0f | 2859 | t = ipa_value_from_jfunc (IPA_NODE_REF (cs->caller), jump_func); |
2860 | if (!t | |
2861 | || (newval | |
2862 | && !values_equal_for_ipcp_p (t, newval))) | |
1caef38b | 2863 | { |
821d0e0f | 2864 | newval = NULL_TREE; |
2865 | break; | |
1caef38b | 2866 | } |
821d0e0f | 2867 | else |
2868 | newval = t; | |
1caef38b | 2869 | } |
2870 | ||
821d0e0f | 2871 | if (newval) |
2872 | { | |
2873 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2874 | { | |
803a7988 | 2875 | fprintf (dump_file, " adding an extra known scalar value "); |
821d0e0f | 2876 | print_ipcp_constant_value (dump_file, newval); |
09ab6335 | 2877 | fprintf (dump_file, " for "); |
2878 | ipa_dump_param (dump_file, info, i); | |
821d0e0f | 2879 | fprintf (dump_file, "\n"); |
2880 | } | |
2a15795f | 2881 | |
f1f41a6c | 2882 | known_vals[i] = newval; |
821d0e0f | 2883 | } |
2a15795f | 2884 | } |
2a15795f | 2885 | } |
2886 | ||
803a7988 | 2887 | /* Go through PLATS and create a vector of values consisting of values and |
2888 | offsets (minus OFFSET) of lattices that contain only a single value. */ | |
2889 | ||
b3e7c666 | 2890 | static vec<ipa_agg_jf_item> |
803a7988 | 2891 | copy_plats_to_inter (struct ipcp_param_lattices *plats, HOST_WIDE_INT offset) |
2892 | { | |
b3e7c666 | 2893 | vec<ipa_agg_jf_item> res = vNULL; |
803a7988 | 2894 | |
2895 | if (!plats->aggs || plats->aggs_contain_variable || plats->aggs_bottom) | |
1e094109 | 2896 | return vNULL; |
803a7988 | 2897 | |
2898 | for (struct ipcp_agg_lattice *aglat = plats->aggs; aglat; aglat = aglat->next) | |
2899 | if (ipa_lat_is_single_const (aglat)) | |
2900 | { | |
2901 | struct ipa_agg_jf_item ti; | |
2902 | ti.offset = aglat->offset - offset; | |
2903 | ti.value = aglat->values->value; | |
f1f41a6c | 2904 | res.safe_push (ti); |
803a7988 | 2905 | } |
2906 | return res; | |
2907 | } | |
2908 | ||
2909 | /* Intersect all values in INTER with single value lattices in PLATS (while | |
2910 | subtracting OFFSET). */ | |
2911 | ||
2912 | static void | |
2913 | intersect_with_plats (struct ipcp_param_lattices *plats, | |
b3e7c666 | 2914 | vec<ipa_agg_jf_item> *inter, |
803a7988 | 2915 | HOST_WIDE_INT offset) |
2916 | { | |
2917 | struct ipcp_agg_lattice *aglat; | |
2918 | struct ipa_agg_jf_item *item; | |
2919 | int k; | |
2920 | ||
2921 | if (!plats->aggs || plats->aggs_contain_variable || plats->aggs_bottom) | |
2922 | { | |
f1f41a6c | 2923 | inter->release (); |
803a7988 | 2924 | return; |
2925 | } | |
2926 | ||
2927 | aglat = plats->aggs; | |
f1f41a6c | 2928 | FOR_EACH_VEC_ELT (*inter, k, item) |
803a7988 | 2929 | { |
2930 | bool found = false; | |
2931 | if (!item->value) | |
2932 | continue; | |
2933 | while (aglat) | |
2934 | { | |
2935 | if (aglat->offset - offset > item->offset) | |
2936 | break; | |
2937 | if (aglat->offset - offset == item->offset) | |
2938 | { | |
2939 | gcc_checking_assert (item->value); | |
2940 | if (values_equal_for_ipcp_p (item->value, aglat->values->value)) | |
2941 | found = true; | |
2942 | break; | |
2943 | } | |
2944 | aglat = aglat->next; | |
2945 | } | |
2946 | if (!found) | |
2947 | item->value = NULL_TREE; | |
2948 | } | |
2949 | } | |
2950 | ||
2951 | /* Copy agggregate replacement values of NODE (which is an IPA-CP clone) to the | |
2952 | vector result while subtracting OFFSET from the individual value offsets. */ | |
2953 | ||
b3e7c666 | 2954 | static vec<ipa_agg_jf_item> |
9bd3a517 | 2955 | agg_replacements_to_vector (struct cgraph_node *node, int index, |
2956 | HOST_WIDE_INT offset) | |
803a7988 | 2957 | { |
2958 | struct ipa_agg_replacement_value *av; | |
b3e7c666 | 2959 | vec<ipa_agg_jf_item> res = vNULL; |
803a7988 | 2960 | |
2961 | for (av = ipa_get_agg_replacements_for_node (node); av; av = av->next) | |
9bd3a517 | 2962 | if (av->index == index |
2963 | && (av->offset - offset) >= 0) | |
803a7988 | 2964 | { |
2965 | struct ipa_agg_jf_item item; | |
2966 | gcc_checking_assert (av->value); | |
2967 | item.offset = av->offset - offset; | |
2968 | item.value = av->value; | |
f1f41a6c | 2969 | res.safe_push (item); |
803a7988 | 2970 | } |
2971 | ||
2972 | return res; | |
2973 | } | |
2974 | ||
2975 | /* Intersect all values in INTER with those that we have already scheduled to | |
2976 | be replaced in parameter number INDEX of NODE, which is an IPA-CP clone | |
2977 | (while subtracting OFFSET). */ | |
2978 | ||
2979 | static void | |
2980 | intersect_with_agg_replacements (struct cgraph_node *node, int index, | |
b3e7c666 | 2981 | vec<ipa_agg_jf_item> *inter, |
803a7988 | 2982 | HOST_WIDE_INT offset) |
2983 | { | |
2984 | struct ipa_agg_replacement_value *srcvals; | |
2985 | struct ipa_agg_jf_item *item; | |
2986 | int i; | |
2987 | ||
2988 | srcvals = ipa_get_agg_replacements_for_node (node); | |
2989 | if (!srcvals) | |
2990 | { | |
f1f41a6c | 2991 | inter->release (); |
803a7988 | 2992 | return; |
2993 | } | |
2994 | ||
f1f41a6c | 2995 | FOR_EACH_VEC_ELT (*inter, i, item) |
803a7988 | 2996 | { |
2997 | struct ipa_agg_replacement_value *av; | |
2998 | bool found = false; | |
2999 | if (!item->value) | |
3000 | continue; | |
3001 | for (av = srcvals; av; av = av->next) | |
3002 | { | |
3003 | gcc_checking_assert (av->value); | |
3004 | if (av->index == index | |
3005 | && av->offset - offset == item->offset) | |
3006 | { | |
3007 | if (values_equal_for_ipcp_p (item->value, av->value)) | |
3008 | found = true; | |
3009 | break; | |
3010 | } | |
3011 | } | |
3012 | if (!found) | |
3013 | item->value = NULL_TREE; | |
3014 | } | |
3015 | } | |
3016 | ||
7e8091c8 | 3017 | /* Intersect values in INTER with aggregate values that come along edge CS to |
3018 | parameter number INDEX and return it. If INTER does not actually exist yet, | |
3019 | copy all incoming values to it. If we determine we ended up with no values | |
3020 | whatsoever, return a released vector. */ | |
3021 | ||
b3e7c666 | 3022 | static vec<ipa_agg_jf_item> |
7e8091c8 | 3023 | intersect_aggregates_with_edge (struct cgraph_edge *cs, int index, |
b3e7c666 | 3024 | vec<ipa_agg_jf_item> inter) |
7e8091c8 | 3025 | { |
3026 | struct ipa_jump_func *jfunc; | |
3027 | jfunc = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), index); | |
3028 | if (jfunc->type == IPA_JF_PASS_THROUGH | |
3029 | && ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR) | |
3030 | { | |
3031 | struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller); | |
3032 | int src_idx = ipa_get_jf_pass_through_formal_id (jfunc); | |
3033 | ||
3034 | if (caller_info->ipcp_orig_node) | |
3035 | { | |
3036 | struct cgraph_node *orig_node = caller_info->ipcp_orig_node; | |
3037 | struct ipcp_param_lattices *orig_plats; | |
3038 | orig_plats = ipa_get_parm_lattices (IPA_NODE_REF (orig_node), | |
3039 | src_idx); | |
3040 | if (agg_pass_through_permissible_p (orig_plats, jfunc)) | |
3041 | { | |
3042 | if (!inter.exists ()) | |
9bd3a517 | 3043 | inter = agg_replacements_to_vector (cs->caller, src_idx, 0); |
7e8091c8 | 3044 | else |
3045 | intersect_with_agg_replacements (cs->caller, src_idx, | |
3046 | &inter, 0); | |
3047 | } | |
3048 | } | |
3049 | else | |
3050 | { | |
3051 | struct ipcp_param_lattices *src_plats; | |
3052 | src_plats = ipa_get_parm_lattices (caller_info, src_idx); | |
3053 | if (agg_pass_through_permissible_p (src_plats, jfunc)) | |
3054 | { | |
3055 | /* Currently we do not produce clobber aggregate jump | |
3056 | functions, adjust when we do. */ | |
3057 | gcc_checking_assert (!jfunc->agg.items); | |
3058 | if (!inter.exists ()) | |
3059 | inter = copy_plats_to_inter (src_plats, 0); | |
3060 | else | |
3061 | intersect_with_plats (src_plats, &inter, 0); | |
3062 | } | |
3063 | } | |
3064 | } | |
3065 | else if (jfunc->type == IPA_JF_ANCESTOR | |
3066 | && ipa_get_jf_ancestor_agg_preserved (jfunc)) | |
3067 | { | |
3068 | struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller); | |
3069 | int src_idx = ipa_get_jf_ancestor_formal_id (jfunc); | |
3070 | struct ipcp_param_lattices *src_plats; | |
3071 | HOST_WIDE_INT delta = ipa_get_jf_ancestor_offset (jfunc); | |
3072 | ||
3073 | if (caller_info->ipcp_orig_node) | |
3074 | { | |
3075 | if (!inter.exists ()) | |
9bd3a517 | 3076 | inter = agg_replacements_to_vector (cs->caller, src_idx, delta); |
7e8091c8 | 3077 | else |
9bd3a517 | 3078 | intersect_with_agg_replacements (cs->caller, src_idx, &inter, |
7e8091c8 | 3079 | delta); |
3080 | } | |
3081 | else | |
3082 | { | |
3083 | src_plats = ipa_get_parm_lattices (caller_info, src_idx);; | |
3084 | /* Currently we do not produce clobber aggregate jump | |
3085 | functions, adjust when we do. */ | |
3086 | gcc_checking_assert (!src_plats->aggs || !jfunc->agg.items); | |
3087 | if (!inter.exists ()) | |
3088 | inter = copy_plats_to_inter (src_plats, delta); | |
3089 | else | |
3090 | intersect_with_plats (src_plats, &inter, delta); | |
3091 | } | |
3092 | } | |
3093 | else if (jfunc->agg.items) | |
3094 | { | |
3095 | struct ipa_agg_jf_item *item; | |
3096 | int k; | |
3097 | ||
3098 | if (!inter.exists ()) | |
3099 | for (unsigned i = 0; i < jfunc->agg.items->length (); i++) | |
3100 | inter.safe_push ((*jfunc->agg.items)[i]); | |
3101 | else | |
3102 | FOR_EACH_VEC_ELT (inter, k, item) | |
3103 | { | |
3104 | int l = 0; | |
3105 | bool found = false;; | |
3106 | ||
3107 | if (!item->value) | |
3108 | continue; | |
3109 | ||
3110 | while ((unsigned) l < jfunc->agg.items->length ()) | |
3111 | { | |
3112 | struct ipa_agg_jf_item *ti; | |
3113 | ti = &(*jfunc->agg.items)[l]; | |
3114 | if (ti->offset > item->offset) | |
3115 | break; | |
3116 | if (ti->offset == item->offset) | |
3117 | { | |
3118 | gcc_checking_assert (ti->value); | |
3119 | if (values_equal_for_ipcp_p (item->value, | |
3120 | ti->value)) | |
3121 | found = true; | |
3122 | break; | |
3123 | } | |
3124 | l++; | |
3125 | } | |
3126 | if (!found) | |
3127 | item->value = NULL; | |
3128 | } | |
3129 | } | |
3130 | else | |
3131 | { | |
9af5ce0c | 3132 | inter.release (); |
b3e7c666 | 3133 | return vec<ipa_agg_jf_item>(); |
7e8091c8 | 3134 | } |
3135 | return inter; | |
3136 | } | |
3137 | ||
803a7988 | 3138 | /* Look at edges in CALLERS and collect all known aggregate values that arrive |
3139 | from all of them. */ | |
3140 | ||
3141 | static struct ipa_agg_replacement_value * | |
3142 | find_aggregate_values_for_callers_subset (struct cgraph_node *node, | |
f1f41a6c | 3143 | vec<cgraph_edge_p> callers) |
803a7988 | 3144 | { |
91af92ef | 3145 | struct ipa_node_params *dest_info = IPA_NODE_REF (node); |
803a7988 | 3146 | struct ipa_agg_replacement_value *res = NULL; |
3147 | struct cgraph_edge *cs; | |
91af92ef | 3148 | int i, j, count = ipa_get_param_count (dest_info); |
803a7988 | 3149 | |
f1f41a6c | 3150 | FOR_EACH_VEC_ELT (callers, j, cs) |
803a7988 | 3151 | { |
3152 | int c = ipa_get_cs_argument_count (IPA_EDGE_REF (cs)); | |
3153 | if (c < count) | |
3154 | count = c; | |
3155 | } | |
3156 | ||
3157 | for (i = 0; i < count ; i++) | |
3158 | { | |
3159 | struct cgraph_edge *cs; | |
b3e7c666 | 3160 | vec<ipa_agg_jf_item> inter = vNULL; |
803a7988 | 3161 | struct ipa_agg_jf_item *item; |
c42e4f2e | 3162 | struct ipcp_param_lattices *plats = ipa_get_parm_lattices (dest_info, i); |
803a7988 | 3163 | int j; |
3164 | ||
3165 | /* Among other things, the following check should deal with all by_ref | |
3166 | mismatches. */ | |
c42e4f2e | 3167 | if (plats->aggs_bottom) |
803a7988 | 3168 | continue; |
3169 | ||
f1f41a6c | 3170 | FOR_EACH_VEC_ELT (callers, j, cs) |
803a7988 | 3171 | { |
7e8091c8 | 3172 | inter = intersect_aggregates_with_edge (cs, i, inter); |
803a7988 | 3173 | |
f1f41a6c | 3174 | if (!inter.exists ()) |
803a7988 | 3175 | goto next_param; |
3176 | } | |
3177 | ||
f1f41a6c | 3178 | FOR_EACH_VEC_ELT (inter, j, item) |
803a7988 | 3179 | { |
3180 | struct ipa_agg_replacement_value *v; | |
3181 | ||
3182 | if (!item->value) | |
3183 | continue; | |
3184 | ||
25a27413 | 3185 | v = ggc_alloc<ipa_agg_replacement_value> (); |
803a7988 | 3186 | v->index = i; |
3187 | v->offset = item->offset; | |
3188 | v->value = item->value; | |
c42e4f2e | 3189 | v->by_ref = plats->aggs_by_ref; |
803a7988 | 3190 | v->next = res; |
3191 | res = v; | |
3192 | } | |
3193 | ||
3194 | next_param: | |
f1f41a6c | 3195 | if (inter.exists ()) |
3196 | inter.release (); | |
803a7988 | 3197 | } |
3198 | return res; | |
3199 | } | |
3200 | ||
3201 | /* Turn KNOWN_AGGS into a list of aggreate replacement values. */ | |
3202 | ||
3203 | static struct ipa_agg_replacement_value * | |
b3e7c666 | 3204 | known_aggs_to_agg_replacement_list (vec<ipa_agg_jump_function> known_aggs) |
803a7988 | 3205 | { |
3206 | struct ipa_agg_replacement_value *res = NULL; | |
3207 | struct ipa_agg_jump_function *aggjf; | |
3208 | struct ipa_agg_jf_item *item; | |
3209 | int i, j; | |
3210 | ||
f1f41a6c | 3211 | FOR_EACH_VEC_ELT (known_aggs, i, aggjf) |
3212 | FOR_EACH_VEC_SAFE_ELT (aggjf->items, j, item) | |
803a7988 | 3213 | { |
3214 | struct ipa_agg_replacement_value *v; | |
25a27413 | 3215 | v = ggc_alloc<ipa_agg_replacement_value> (); |
803a7988 | 3216 | v->index = i; |
3217 | v->offset = item->offset; | |
3218 | v->value = item->value; | |
c42e4f2e | 3219 | v->by_ref = aggjf->by_ref; |
803a7988 | 3220 | v->next = res; |
3221 | res = v; | |
3222 | } | |
3223 | return res; | |
3224 | } | |
3225 | ||
3226 | /* Determine whether CS also brings all scalar values that the NODE is | |
3227 | specialized for. */ | |
3228 | ||
3229 | static bool | |
3230 | cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge *cs, | |
3231 | struct cgraph_node *node) | |
3232 | { | |
3233 | struct ipa_node_params *dest_info = IPA_NODE_REF (node); | |
3234 | int count = ipa_get_param_count (dest_info); | |
3235 | struct ipa_node_params *caller_info; | |
3236 | struct ipa_edge_args *args; | |
3237 | int i; | |
3238 | ||
3239 | caller_info = IPA_NODE_REF (cs->caller); | |
3240 | args = IPA_EDGE_REF (cs); | |
3241 | for (i = 0; i < count; i++) | |
3242 | { | |
3243 | struct ipa_jump_func *jump_func; | |
3244 | tree val, t; | |
3245 | ||
f1f41a6c | 3246 | val = dest_info->known_vals[i]; |
803a7988 | 3247 | if (!val) |
3248 | continue; | |
3249 | ||
3250 | if (i >= ipa_get_cs_argument_count (args)) | |
3251 | return false; | |
3252 | jump_func = ipa_get_ith_jump_func (args, i); | |
3253 | t = ipa_value_from_jfunc (caller_info, jump_func); | |
3254 | if (!t || !values_equal_for_ipcp_p (val, t)) | |
3255 | return false; | |
3256 | } | |
3257 | return true; | |
3258 | } | |
3259 | ||
3260 | /* Determine whether CS also brings all aggregate values that NODE is | |
3261 | specialized for. */ | |
3262 | static bool | |
3263 | cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge *cs, | |
3264 | struct cgraph_node *node) | |
3265 | { | |
7e8091c8 | 3266 | struct ipa_node_params *orig_caller_info = IPA_NODE_REF (cs->caller); |
fc635e81 | 3267 | struct ipa_node_params *orig_node_info; |
803a7988 | 3268 | struct ipa_agg_replacement_value *aggval; |
7e8091c8 | 3269 | int i, ec, count; |
803a7988 | 3270 | |
3271 | aggval = ipa_get_agg_replacements_for_node (node); | |
7e8091c8 | 3272 | if (!aggval) |
3273 | return true; | |
3274 | ||
3275 | count = ipa_get_param_count (IPA_NODE_REF (node)); | |
3276 | ec = ipa_get_cs_argument_count (IPA_EDGE_REF (cs)); | |
3277 | if (ec < count) | |
3278 | for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next) | |
3279 | if (aggval->index >= ec) | |
3280 | return false; | |
3281 | ||
fc635e81 | 3282 | orig_node_info = IPA_NODE_REF (IPA_NODE_REF (node)->ipcp_orig_node); |
7e8091c8 | 3283 | if (orig_caller_info->ipcp_orig_node) |
3284 | orig_caller_info = IPA_NODE_REF (orig_caller_info->ipcp_orig_node); | |
3285 | ||
3286 | for (i = 0; i < count; i++) | |
803a7988 | 3287 | { |
b3e7c666 | 3288 | static vec<ipa_agg_jf_item> values = vec<ipa_agg_jf_item>(); |
803a7988 | 3289 | struct ipcp_param_lattices *plats; |
7e8091c8 | 3290 | bool interesting = false; |
3291 | for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next) | |
3292 | if (aggval->index == i) | |
3293 | { | |
3294 | interesting = true; | |
3295 | break; | |
3296 | } | |
3297 | if (!interesting) | |
3298 | continue; | |
3299 | ||
fc635e81 | 3300 | plats = ipa_get_parm_lattices (orig_node_info, aggval->index); |
7e8091c8 | 3301 | if (plats->aggs_bottom) |
803a7988 | 3302 | return false; |
803a7988 | 3303 | |
7e8091c8 | 3304 | values = intersect_aggregates_with_edge (cs, i, values); |
9af5ce0c | 3305 | if (!values.exists ()) |
803a7988 | 3306 | return false; |
3307 | ||
7e8091c8 | 3308 | for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next) |
3309 | if (aggval->index == i) | |
3310 | { | |
3311 | struct ipa_agg_jf_item *item; | |
3312 | int j; | |
3313 | bool found = false; | |
3314 | FOR_EACH_VEC_ELT (values, j, item) | |
3315 | if (item->value | |
3316 | && item->offset == av->offset | |
3317 | && values_equal_for_ipcp_p (item->value, av->value)) | |
9ea71c42 | 3318 | { |
3319 | found = true; | |
3320 | break; | |
3321 | } | |
7e8091c8 | 3322 | if (!found) |
3323 | { | |
9af5ce0c | 3324 | values.release (); |
7e8091c8 | 3325 | return false; |
3326 | } | |
3327 | } | |
803a7988 | 3328 | } |
3329 | return true; | |
3330 | } | |
3331 | ||
821d0e0f | 3332 | /* Given an original NODE and a VAL for which we have already created a |
3333 | specialized clone, look whether there are incoming edges that still lead | |
3334 | into the old node but now also bring the requested value and also conform to | |
3335 | all other criteria such that they can be redirected the the special node. | |
3336 | This function can therefore redirect the final edge in a SCC. */ | |
7428ee1f | 3337 | |
3338 | static void | |
821d0e0f | 3339 | perhaps_add_new_callers (struct cgraph_node *node, struct ipcp_value *val) |
7428ee1f | 3340 | { |
821d0e0f | 3341 | struct ipcp_value_source *src; |
821d0e0f | 3342 | gcov_type redirected_sum = 0; |
7428ee1f | 3343 | |
821d0e0f | 3344 | for (src = val->sources; src; src = src->next) |
7428ee1f | 3345 | { |
821d0e0f | 3346 | struct cgraph_edge *cs = src->cs; |
3347 | while (cs) | |
3348 | { | |
3349 | enum availability availability; | |
87228246 | 3350 | struct cgraph_node *dst = cgraph_function_node (cs->callee, |
3351 | &availability); | |
3352 | if ((dst == node || IPA_NODE_REF (dst)->is_all_contexts_clone) | |
821d0e0f | 3353 | && availability > AVAIL_OVERWRITABLE |
3354 | && cgraph_edge_brings_value_p (cs, src)) | |
3355 | { | |
803a7988 | 3356 | if (cgraph_edge_brings_all_scalars_for_node (cs, val->spec_node) |
3357 | && cgraph_edge_brings_all_agg_vals_for_node (cs, | |
3358 | val->spec_node)) | |
821d0e0f | 3359 | { |
3360 | if (dump_file) | |
3361 | fprintf (dump_file, " - adding an extra caller %s/%i" | |
3362 | " of %s/%i\n", | |
f1c8b4d7 | 3363 | xstrdup (cs->caller->name ()), |
02774f2d | 3364 | cs->caller->order, |
f1c8b4d7 | 3365 | xstrdup (val->spec_node->name ()), |
02774f2d | 3366 | val->spec_node->order); |
821d0e0f | 3367 | |
3368 | cgraph_redirect_edge_callee (cs, val->spec_node); | |
3369 | redirected_sum += cs->count; | |
3370 | } | |
3371 | } | |
3372 | cs = get_next_cgraph_edge_clone (cs); | |
3373 | } | |
7428ee1f | 3374 | } |
821d0e0f | 3375 | |
3376 | if (redirected_sum) | |
3377 | update_specialized_profile (val->spec_node, node, redirected_sum); | |
7428ee1f | 3378 | } |
3379 | ||
3380 | ||
821d0e0f | 3381 | /* Copy KNOWN_BINFOS to KNOWN_VALS. */ |
3382 | ||
3b22db66 | 3383 | static void |
f1f41a6c | 3384 | move_binfos_to_values (vec<tree> known_vals, |
3385 | vec<tree> known_binfos) | |
3b22db66 | 3386 | { |
821d0e0f | 3387 | tree t; |
2a15795f | 3388 | int i; |
3b22db66 | 3389 | |
f1f41a6c | 3390 | for (i = 0; known_binfos.iterate (i, &t); i++) |
821d0e0f | 3391 | if (t) |
f1f41a6c | 3392 | known_vals[i] = t; |
821d0e0f | 3393 | } |
2a15795f | 3394 | |
803a7988 | 3395 | /* Return true if there is a replacement equivalent to VALUE, INDEX and OFFSET |
3396 | among those in the AGGVALS list. */ | |
3397 | ||
3398 | DEBUG_FUNCTION bool | |
3399 | ipcp_val_in_agg_replacements_p (struct ipa_agg_replacement_value *aggvals, | |
3400 | int index, HOST_WIDE_INT offset, tree value) | |
3401 | { | |
3402 | while (aggvals) | |
3403 | { | |
3404 | if (aggvals->index == index | |
3405 | && aggvals->offset == offset | |
3406 | && values_equal_for_ipcp_p (aggvals->value, value)) | |
3407 | return true; | |
3408 | aggvals = aggvals->next; | |
3409 | } | |
3410 | return false; | |
3411 | } | |
3412 | ||
3413 | /* Decide wheter to create a special version of NODE for value VAL of parameter | |
3414 | at the given INDEX. If OFFSET is -1, the value is for the parameter itself, | |
3415 | otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS, | |
3416 | KNOWN_BINFOS and KNOWN_AGGS describe the other already known values. */ | |
3417 | ||
3418 | static bool | |
3419 | decide_about_value (struct cgraph_node *node, int index, HOST_WIDE_INT offset, | |
f1f41a6c | 3420 | struct ipcp_value *val, vec<tree> known_csts, |
3421 | vec<tree> known_binfos) | |
803a7988 | 3422 | { |
3423 | struct ipa_agg_replacement_value *aggvals; | |
3424 | int freq_sum, caller_count; | |
3425 | gcov_type count_sum; | |
f1f41a6c | 3426 | vec<cgraph_edge_p> callers; |
3427 | vec<tree> kv; | |
803a7988 | 3428 | |
3429 | if (val->spec_node) | |
3430 | { | |
3431 | perhaps_add_new_callers (node, val); | |
3432 | return false; | |
3433 | } | |
3434 | else if (val->local_size_cost + overall_size > max_new_size) | |
3435 | { | |
3436 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
3437 | fprintf (dump_file, " Ignoring candidate value because " | |
3438 | "max_new_size would be reached with %li.\n", | |
3439 | val->local_size_cost + overall_size); | |
3440 | return false; | |
3441 | } | |
3442 | else if (!get_info_about_necessary_edges (val, &freq_sum, &count_sum, | |
3443 | &caller_count)) | |
3444 | return false; | |
3445 | ||
3446 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
3447 | { | |
3448 | fprintf (dump_file, " - considering value "); | |
3449 | print_ipcp_constant_value (dump_file, val->value); | |
09ab6335 | 3450 | fprintf (dump_file, " for "); |
3451 | ipa_dump_param (dump_file, IPA_NODE_REF (node), index); | |
803a7988 | 3452 | if (offset != -1) |
3453 | fprintf (dump_file, ", offset: " HOST_WIDE_INT_PRINT_DEC, offset); | |
3454 | fprintf (dump_file, " (caller_count: %i)\n", caller_count); | |
3455 | } | |
3456 | ||
3457 | if (!good_cloning_opportunity_p (node, val->local_time_benefit, | |
3458 | freq_sum, count_sum, | |
3459 | val->local_size_cost) | |
3460 | && !good_cloning_opportunity_p (node, | |
3461 | val->local_time_benefit | |
3462 | + val->prop_time_benefit, | |
3463 | freq_sum, count_sum, | |
3464 | val->local_size_cost | |
3465 | + val->prop_size_cost)) | |
3466 | return false; | |
3467 | ||
3468 | if (dump_file) | |
3469 | fprintf (dump_file, " Creating a specialized node of %s/%i.\n", | |
f1c8b4d7 | 3470 | node->name (), node->order); |
803a7988 | 3471 | |
3472 | callers = gather_edges_for_value (val, caller_count); | |
f1f41a6c | 3473 | kv = known_csts.copy (); |
803a7988 | 3474 | move_binfos_to_values (kv, known_binfos); |
3475 | if (offset == -1) | |
f1f41a6c | 3476 | kv[index] = val->value; |
803a7988 | 3477 | find_more_scalar_values_for_callers_subset (node, kv, callers); |
3478 | aggvals = find_aggregate_values_for_callers_subset (node, callers); | |
3479 | gcc_checking_assert (offset == -1 | |
3480 | || ipcp_val_in_agg_replacements_p (aggvals, index, | |
3481 | offset, val->value)); | |
3482 | val->spec_node = create_specialized_node (node, kv, aggvals, callers); | |
3483 | overall_size += val->local_size_cost; | |
3484 | ||
3485 | /* TODO: If for some lattice there is only one other known value | |
3486 | left, make a special node for it too. */ | |
3487 | ||
3488 | return true; | |
3489 | } | |
2a15795f | 3490 | |
821d0e0f | 3491 | /* Decide whether and what specialized clones of NODE should be created. */ |
2a15795f | 3492 | |
821d0e0f | 3493 | static bool |
3494 | decide_whether_version_node (struct cgraph_node *node) | |
3495 | { | |
3496 | struct ipa_node_params *info = IPA_NODE_REF (node); | |
3497 | int i, count = ipa_get_param_count (info); | |
f1f41a6c | 3498 | vec<tree> known_csts, known_binfos; |
b3e7c666 | 3499 | vec<ipa_agg_jump_function> known_aggs = vNULL; |
821d0e0f | 3500 | bool ret = false; |
2a15795f | 3501 | |
821d0e0f | 3502 | if (count == 0) |
3503 | return false; | |
2a15795f | 3504 | |
821d0e0f | 3505 | if (dump_file && (dump_flags & TDF_DETAILS)) |
3506 | fprintf (dump_file, "\nEvaluating opportunities for %s/%i.\n", | |
f1c8b4d7 | 3507 | node->name (), node->order); |
2a15795f | 3508 | |
821d0e0f | 3509 | gather_context_independent_values (info, &known_csts, &known_binfos, |
87228246 | 3510 | info->do_clone_for_all_contexts ? &known_aggs |
3511 | : NULL, NULL); | |
2a15795f | 3512 | |
803a7988 | 3513 | for (i = 0; i < count ;i++) |
821d0e0f | 3514 | { |
803a7988 | 3515 | struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); |
3516 | struct ipcp_lattice *lat = &plats->itself; | |
821d0e0f | 3517 | struct ipcp_value *val; |
2a15795f | 3518 | |
803a7988 | 3519 | if (!lat->bottom |
f1f41a6c | 3520 | && !known_csts[i] |
3521 | && !known_binfos[i]) | |
803a7988 | 3522 | for (val = lat->values; val; val = val->next) |
3523 | ret |= decide_about_value (node, i, -1, val, known_csts, | |
3524 | known_binfos); | |
3c97c75d | 3525 | |
87228246 | 3526 | if (!plats->aggs_bottom) |
3b22db66 | 3527 | { |
803a7988 | 3528 | struct ipcp_agg_lattice *aglat; |
3529 | struct ipcp_value *val; | |
3530 | for (aglat = plats->aggs; aglat; aglat = aglat->next) | |
3531 | if (!aglat->bottom && aglat->values | |
3532 | /* If the following is false, the one value is in | |
3533 | known_aggs. */ | |
3534 | && (plats->aggs_contain_variable | |
3535 | || !ipa_lat_is_single_const (aglat))) | |
3536 | for (val = aglat->values; val; val = val->next) | |
3537 | ret |= decide_about_value (node, i, aglat->offset, val, | |
3538 | known_csts, known_binfos); | |
f9e9b574 | 3539 | } |
803a7988 | 3540 | info = IPA_NODE_REF (node); |
821d0e0f | 3541 | } |
f9e9b574 | 3542 | |
87228246 | 3543 | if (info->do_clone_for_all_contexts) |
821d0e0f | 3544 | { |
87228246 | 3545 | struct cgraph_node *clone; |
f1f41a6c | 3546 | vec<cgraph_edge_p> callers; |
f9e9b574 | 3547 | |
821d0e0f | 3548 | if (dump_file) |
3549 | fprintf (dump_file, " - Creating a specialized node of %s/%i " | |
f1c8b4d7 | 3550 | "for all known contexts.\n", node->name (), |
02774f2d | 3551 | node->order); |
2a15795f | 3552 | |
821d0e0f | 3553 | callers = collect_callers_of_node (node); |
3554 | move_binfos_to_values (known_csts, known_binfos); | |
87228246 | 3555 | clone = create_specialized_node (node, known_csts, |
803a7988 | 3556 | known_aggs_to_agg_replacement_list (known_aggs), |
3557 | callers); | |
821d0e0f | 3558 | info = IPA_NODE_REF (node); |
87228246 | 3559 | info->do_clone_for_all_contexts = false; |
3560 | IPA_NODE_REF (clone)->is_all_contexts_clone = true; | |
e4898110 | 3561 | for (i = 0; i < count ; i++) |
3562 | vec_free (known_aggs[i].items); | |
3563 | known_aggs.release (); | |
821d0e0f | 3564 | ret = true; |
3565 | } | |
3566 | else | |
f1f41a6c | 3567 | known_csts.release (); |
2a15795f | 3568 | |
f1f41a6c | 3569 | known_binfos.release (); |
821d0e0f | 3570 | return ret; |
3571 | } | |
ccf4ab6b | 3572 | |
821d0e0f | 3573 | /* Transitively mark all callees of NODE within the same SCC as not dead. */ |
1caef38b | 3574 | |
821d0e0f | 3575 | static void |
3576 | spread_undeadness (struct cgraph_node *node) | |
3577 | { | |
3578 | struct cgraph_edge *cs; | |
2a15795f | 3579 | |
821d0e0f | 3580 | for (cs = node->callees; cs; cs = cs->next_callee) |
a0255a70 | 3581 | if (ipa_edge_within_scc (cs)) |
821d0e0f | 3582 | { |
3583 | struct cgraph_node *callee; | |
3584 | struct ipa_node_params *info; | |
50828ed8 | 3585 | |
821d0e0f | 3586 | callee = cgraph_function_node (cs->callee, NULL); |
3587 | info = IPA_NODE_REF (callee); | |
2a15795f | 3588 | |
821d0e0f | 3589 | if (info->node_dead) |
3590 | { | |
3591 | info->node_dead = 0; | |
3592 | spread_undeadness (callee); | |
3593 | } | |
3594 | } | |
3595 | } | |
3596 | ||
3597 | /* Return true if NODE has a caller from outside of its SCC that is not | |
3598 | dead. Worker callback for cgraph_for_node_and_aliases. */ | |
3599 | ||
3600 | static bool | |
3601 | has_undead_caller_from_outside_scc_p (struct cgraph_node *node, | |
3602 | void *data ATTRIBUTE_UNUSED) | |
3603 | { | |
3604 | struct cgraph_edge *cs; | |
3605 | ||
3606 | for (cs = node->callers; cs; cs = cs->next_caller) | |
3607 | if (cs->caller->thunk.thunk_p | |
3608 | && cgraph_for_node_and_aliases (cs->caller, | |
3609 | has_undead_caller_from_outside_scc_p, | |
3610 | NULL, true)) | |
3611 | return true; | |
a0255a70 | 3612 | else if (!ipa_edge_within_scc (cs) |
821d0e0f | 3613 | && !IPA_NODE_REF (cs->caller)->node_dead) |
3614 | return true; | |
3615 | return false; | |
3616 | } | |
3617 | ||
3618 | ||
3619 | /* Identify nodes within the same SCC as NODE which are no longer needed | |
3620 | because of new clones and will be removed as unreachable. */ | |
3621 | ||
3622 | static void | |
3623 | identify_dead_nodes (struct cgraph_node *node) | |
3624 | { | |
3625 | struct cgraph_node *v; | |
02774f2d | 3626 | for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle) |
821d0e0f | 3627 | if (cgraph_will_be_removed_from_program_if_no_direct_calls (v) |
3628 | && !cgraph_for_node_and_aliases (v, | |
3629 | has_undead_caller_from_outside_scc_p, | |
3630 | NULL, true)) | |
3631 | IPA_NODE_REF (v)->node_dead = 1; | |
3632 | ||
02774f2d | 3633 | for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle) |
821d0e0f | 3634 | if (!IPA_NODE_REF (v)->node_dead) |
3635 | spread_undeadness (v); | |
3636 | ||
3637 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
3638 | { | |
02774f2d | 3639 | for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle) |
821d0e0f | 3640 | if (IPA_NODE_REF (v)->node_dead) |
3641 | fprintf (dump_file, " Marking node as dead: %s/%i.\n", | |
f1c8b4d7 | 3642 | v->name (), v->order); |
2a15795f | 3643 | } |
821d0e0f | 3644 | } |
3645 | ||
3646 | /* The decision stage. Iterate over the topological order of call graph nodes | |
3647 | TOPO and make specialized clones if deemed beneficial. */ | |
3648 | ||
3649 | static void | |
3650 | ipcp_decision_stage (struct topo_info *topo) | |
3651 | { | |
3652 | int i; | |
3653 | ||
3654 | if (dump_file) | |
3655 | fprintf (dump_file, "\nIPA decision stage:\n\n"); | |
2a15795f | 3656 | |
821d0e0f | 3657 | for (i = topo->nnodes - 1; i >= 0; i--) |
2a15795f | 3658 | { |
821d0e0f | 3659 | struct cgraph_node *node = topo->order[i]; |
3660 | bool change = false, iterate = true; | |
3661 | ||
3662 | while (iterate) | |
3663 | { | |
3664 | struct cgraph_node *v; | |
3665 | iterate = false; | |
02774f2d | 3666 | for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle) |
821d0e0f | 3667 | if (cgraph_function_with_gimple_body_p (v) |
3668 | && ipcp_versionable_function_p (v)) | |
3669 | iterate |= decide_whether_version_node (v); | |
3670 | ||
3671 | change |= iterate; | |
3672 | } | |
3673 | if (change) | |
3674 | identify_dead_nodes (node); | |
3b22db66 | 3675 | } |
3b22db66 | 3676 | } |
3677 | ||
3678 | /* The IPCP driver. */ | |
821d0e0f | 3679 | |
8624b7fc | 3680 | static unsigned int |
3b22db66 | 3681 | ipcp_driver (void) |
3682 | { | |
821d0e0f | 3683 | struct cgraph_2edge_hook_list *edge_duplication_hook_holder; |
948ccfa6 | 3684 | struct cgraph_edge_hook_list *edge_removal_hook_holder; |
821d0e0f | 3685 | struct topo_info topo; |
3686 | ||
821d0e0f | 3687 | ipa_check_create_node_params (); |
3688 | ipa_check_create_edge_args (); | |
948ccfa6 | 3689 | grow_edge_clone_vectors (); |
821d0e0f | 3690 | edge_duplication_hook_holder = |
3691 | cgraph_add_edge_duplication_hook (&ipcp_edge_duplication_hook, NULL); | |
948ccfa6 | 3692 | edge_removal_hook_holder = |
3693 | cgraph_add_edge_removal_hook (&ipcp_edge_removal_hook, NULL); | |
3694 | ||
821d0e0f | 3695 | ipcp_values_pool = create_alloc_pool ("IPA-CP values", |
3696 | sizeof (struct ipcp_value), 32); | |
3697 | ipcp_sources_pool = create_alloc_pool ("IPA-CP value sources", | |
3698 | sizeof (struct ipcp_value_source), 64); | |
803a7988 | 3699 | ipcp_agg_lattice_pool = create_alloc_pool ("IPA_CP aggregate lattices", |
3700 | sizeof (struct ipcp_agg_lattice), | |
3701 | 32); | |
3b22db66 | 3702 | if (dump_file) |
3703 | { | |
11b73810 | 3704 | fprintf (dump_file, "\nIPA structures before propagation:\n"); |
3705 | if (dump_flags & TDF_DETAILS) | |
3706 | ipa_print_all_params (dump_file); | |
3707 | ipa_print_all_jump_functions (dump_file); | |
3b22db66 | 3708 | } |
821d0e0f | 3709 | |
3710 | /* Topological sort. */ | |
3711 | build_toporder_info (&topo); | |
3712 | /* Do the interprocedural propagation. */ | |
3713 | ipcp_propagate_stage (&topo); | |
3714 | /* Decide what constant propagation and cloning should be performed. */ | |
3715 | ipcp_decision_stage (&topo); | |
3716 | ||
3b22db66 | 3717 | /* Free all IPCP structures. */ |
821d0e0f | 3718 | free_toporder_info (&topo); |
f1f41a6c | 3719 | next_edge_clone.release (); |
948ccfa6 | 3720 | cgraph_remove_edge_removal_hook (edge_removal_hook_holder); |
821d0e0f | 3721 | cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder); |
799c8711 | 3722 | ipa_free_all_structures_after_ipa_cp (); |
3b22db66 | 3723 | if (dump_file) |
3724 | fprintf (dump_file, "\nIPA constant propagation end\n"); | |
2a1990e9 | 3725 | return 0; |
3b22db66 | 3726 | } |
3727 | ||
1caef38b | 3728 | /* Initialization and computation of IPCP data structures. This is the initial |
3729 | intraprocedural analysis of functions, which gathers information to be | |
3730 | propagated later on. */ | |
3731 | ||
50828ed8 | 3732 | static void |
3733 | ipcp_generate_summary (void) | |
3734 | { | |
1caef38b | 3735 | struct cgraph_node *node; |
3736 | ||
50828ed8 | 3737 | if (dump_file) |
3738 | fprintf (dump_file, "\nIPA constant propagation start:\n"); | |
50828ed8 | 3739 | ipa_register_cgraph_hooks (); |
1caef38b | 3740 | |
91bf9d9a | 3741 | FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node) |
1caef38b | 3742 | { |
7d0d0ce1 | 3743 | node->local.versionable |
02774f2d | 3744 | = tree_versionable_function_p (node->decl); |
1caef38b | 3745 | ipa_analyze_node (node); |
3746 | } | |
50828ed8 | 3747 | } |
3748 | ||
8867b500 | 3749 | /* Write ipcp summary for nodes in SET. */ |
821d0e0f | 3750 | |
8867b500 | 3751 | static void |
eab36a5a | 3752 | ipcp_write_summary (void) |
8867b500 | 3753 | { |
eab36a5a | 3754 | ipa_prop_write_jump_functions (); |
8867b500 | 3755 | } |
3756 | ||
3757 | /* Read ipcp summary. */ | |
821d0e0f | 3758 | |
8867b500 | 3759 | static void |
3760 | ipcp_read_summary (void) | |
3761 | { | |
3762 | ipa_prop_read_jump_functions (); | |
3763 | } | |
3764 | ||
cbe8bda8 | 3765 | namespace { |
3766 | ||
3767 | const pass_data pass_data_ipa_cp = | |
3768 | { | |
3769 | IPA_PASS, /* type */ | |
3770 | "cp", /* name */ | |
3771 | OPTGROUP_NONE, /* optinfo_flags */ | |
cbe8bda8 | 3772 | true, /* has_execute */ |
3773 | TV_IPA_CONSTANT_PROP, /* tv_id */ | |
3774 | 0, /* properties_required */ | |
3775 | 0, /* properties_provided */ | |
3776 | 0, /* properties_destroyed */ | |
3777 | 0, /* todo_flags_start */ | |
3778 | ( TODO_dump_symtab | TODO_remove_functions ), /* todo_flags_finish */ | |
3b22db66 | 3779 | }; |
cbe8bda8 | 3780 | |
3781 | class pass_ipa_cp : public ipa_opt_pass_d | |
3782 | { | |
3783 | public: | |
9af5ce0c | 3784 | pass_ipa_cp (gcc::context *ctxt) |
3785 | : ipa_opt_pass_d (pass_data_ipa_cp, ctxt, | |
3786 | ipcp_generate_summary, /* generate_summary */ | |
3787 | ipcp_write_summary, /* write_summary */ | |
3788 | ipcp_read_summary, /* read_summary */ | |
3789 | ipa_prop_write_all_agg_replacement, /* | |
3790 | write_optimization_summary */ | |
3791 | ipa_prop_read_all_agg_replacement, /* | |
3792 | read_optimization_summary */ | |
3793 | NULL, /* stmt_fixup */ | |
3794 | 0, /* function_transform_todo_flags_start */ | |
3795 | ipcp_transform_function, /* function_transform */ | |
3796 | NULL) /* variable_transform */ | |
cbe8bda8 | 3797 | {} |
3798 | ||
3799 | /* opt_pass methods: */ | |
31315c24 | 3800 | virtual bool gate (function *) |
3801 | { | |
3802 | /* FIXME: We should remove the optimize check after we ensure we never run | |
3803 | IPA passes when not optimizing. */ | |
3804 | return flag_ipa_cp && optimize; | |
3805 | } | |
3806 | ||
65b0537f | 3807 | virtual unsigned int execute (function *) { return ipcp_driver (); } |
cbe8bda8 | 3808 | |
3809 | }; // class pass_ipa_cp | |
3810 | ||
3811 | } // anon namespace | |
3812 | ||
3813 | ipa_opt_pass_d * | |
3814 | make_pass_ipa_cp (gcc::context *ctxt) | |
3815 | { | |
3816 | return new pass_ipa_cp (ctxt); | |
3817 | } |