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