libgomp: Use pthread mutexes in the nvptx plugin.
[official-gcc.git] / gcc / ipa-cp.c
blob44f16bf86f29d691f2ee9c27ae52cc07be01d2ae
1 /* Interprocedural constant propagation
2 Copyright (C) 2005-2015 Free Software Foundation, Inc.
4 Contributed by Razya Ladelsky <RAZYA@il.ibm.com> and Martin Jambor
5 <mjambor@suse.cz>
7 This file is part of GCC.
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
11 Software Foundation; either version 3, or (at your option) any later
12 version.
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.
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
23 /* Interprocedural constant propagation (IPA-CP).
25 The goal of this transformation is to
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
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.
36 The algorithm also propagates types and attempts to perform type based
37 devirtualization. Types are propagated much like constants.
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.
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.
54 First stage - intraprocedural analysis
55 =======================================
57 This phase computes jump_function and modification flags.
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:
63 Pass through - the caller's formal parameter is passed as an actual
64 argument, plus an operation on it can be performed.
65 Constant - a constant is passed as an actual argument.
66 Unknown - neither of the above.
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.
71 ipcp_generate_summary() is the main function of the first stage.
73 Second stage - interprocedural analysis
74 ========================================
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.
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
84 propagate cumulative information about these effects from dependent values
85 to those on which they depend.
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.
93 ipcp_propagate_stage() and ipcp_decision_stage() together constitute the
94 third stage.
96 Third phase - materialization of clones, call statement updates.
97 ============================================
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. */
103 #include "config.h"
104 #include "system.h"
105 #include "coretypes.h"
106 #include "hash-set.h"
107 #include "machmode.h"
108 #include "vec.h"
109 #include "hash-map.h"
110 #include "double-int.h"
111 #include "input.h"
112 #include "alias.h"
113 #include "symtab.h"
114 #include "options.h"
115 #include "wide-int.h"
116 #include "inchash.h"
117 #include "tree.h"
118 #include "fold-const.h"
119 #include "gimple-fold.h"
120 #include "gimple-expr.h"
121 #include "target.h"
122 #include "predict.h"
123 #include "basic-block.h"
124 #include "is-a.h"
125 #include "plugin-api.h"
126 #include "tm.h"
127 #include "hard-reg-set.h"
128 #include "input.h"
129 #include "function.h"
130 #include "ipa-ref.h"
131 #include "cgraph.h"
132 #include "alloc-pool.h"
133 #include "symbol-summary.h"
134 #include "ipa-prop.h"
135 #include "bitmap.h"
136 #include "tree-pass.h"
137 #include "flags.h"
138 #include "diagnostic.h"
139 #include "tree-pretty-print.h"
140 #include "tree-inline.h"
141 #include "params.h"
142 #include "ipa-inline.h"
143 #include "ipa-utils.h"
145 template <typename valtype> class ipcp_value;
147 /* Describes a particular source for an IPA-CP value. */
149 template <typename valtype>
150 class ipcp_value_source
152 public:
153 /* Aggregate offset of the source, negative if the source is scalar value of
154 the argument itself. */
155 HOST_WIDE_INT offset;
156 /* The incoming edge that brought the value. */
157 cgraph_edge *cs;
158 /* If the jump function that resulted into his value was a pass-through or an
159 ancestor, this is the ipcp_value of the caller from which the described
160 value has been derived. Otherwise it is NULL. */
161 ipcp_value<valtype> *val;
162 /* Next pointer in a linked list of sources of a value. */
163 ipcp_value_source *next;
164 /* If the jump function that resulted into his value was a pass-through or an
165 ancestor, this is the index of the parameter of the caller the jump
166 function references. */
167 int index;
170 /* Common ancestor for all ipcp_value instantiations. */
172 class ipcp_value_base
174 public:
175 /* Time benefit and size cost that specializing the function for this value
176 would bring about in this function alone. */
177 int local_time_benefit, local_size_cost;
178 /* Time benefit and size cost that specializing the function for this value
179 can bring about in it's callees (transitively). */
180 int prop_time_benefit, prop_size_cost;
183 /* Describes one particular value stored in struct ipcp_lattice. */
185 template <typename valtype>
186 class ipcp_value : public ipcp_value_base
188 public:
189 /* The actual value for the given parameter. */
190 valtype value;
191 /* The list of sources from which this value originates. */
192 ipcp_value_source <valtype> *sources;
193 /* Next pointers in a linked list of all values in a lattice. */
194 ipcp_value *next;
195 /* Next pointers in a linked list of values in a strongly connected component
196 of values. */
197 ipcp_value *scc_next;
198 /* Next pointers in a linked list of SCCs of values sorted topologically
199 according their sources. */
200 ipcp_value *topo_next;
201 /* A specialized node created for this value, NULL if none has been (so far)
202 created. */
203 cgraph_node *spec_node;
204 /* Depth first search number and low link for topological sorting of
205 values. */
206 int dfs, low_link;
207 /* True if this valye is currently on the topo-sort stack. */
208 bool on_stack;
210 void add_source (cgraph_edge *cs, ipcp_value *src_val, int src_idx,
211 HOST_WIDE_INT offset);
214 /* Lattice describing potential values of a formal parameter of a function, or
215 a part of an aggreagate. TOP is represented by a lattice with zero values
216 and with contains_variable and bottom flags cleared. BOTTOM is represented
217 by a lattice with the bottom flag set. In that case, values and
218 contains_variable flag should be disregarded. */
220 template <typename valtype>
221 class ipcp_lattice
223 public:
224 /* The list of known values and types in this lattice. Note that values are
225 not deallocated if a lattice is set to bottom because there may be value
226 sources referencing them. */
227 ipcp_value<valtype> *values;
228 /* Number of known values and types in this lattice. */
229 int values_count;
230 /* The lattice contains a variable component (in addition to values). */
231 bool contains_variable;
232 /* The value of the lattice is bottom (i.e. variable and unusable for any
233 propagation). */
234 bool bottom;
236 inline bool is_single_const ();
237 inline bool set_to_bottom ();
238 inline bool set_contains_variable ();
239 bool add_value (valtype newval, cgraph_edge *cs,
240 ipcp_value<valtype> *src_val = NULL,
241 int src_idx = 0, HOST_WIDE_INT offset = -1);
242 void print (FILE * f, bool dump_sources, bool dump_benefits);
245 /* Lattice of tree values with an offset to describe a part of an
246 aggregate. */
248 class ipcp_agg_lattice : public ipcp_lattice<tree>
250 public:
251 /* Offset that is being described by this lattice. */
252 HOST_WIDE_INT offset;
253 /* Size so that we don't have to re-compute it every time we traverse the
254 list. Must correspond to TYPE_SIZE of all lat values. */
255 HOST_WIDE_INT size;
256 /* Next element of the linked list. */
257 struct ipcp_agg_lattice *next;
260 /* Structure containing lattices for a parameter itself and for pieces of
261 aggregates that are passed in the parameter or by a reference in a parameter
262 plus some other useful flags. */
264 class ipcp_param_lattices
266 public:
267 /* Lattice describing the value of the parameter itself. */
268 ipcp_lattice<tree> itself;
269 /* Lattice describing the the polymorphic contexts of a parameter. */
270 ipcp_lattice<ipa_polymorphic_call_context> ctxlat;
271 /* Lattices describing aggregate parts. */
272 ipcp_agg_lattice *aggs;
273 /* Alignment information. Very basic one value lattice where !known means
274 TOP and zero alignment bottom. */
275 ipa_alignment alignment;
276 /* Number of aggregate lattices */
277 int aggs_count;
278 /* True if aggregate data were passed by reference (as opposed to by
279 value). */
280 bool aggs_by_ref;
281 /* All aggregate lattices contain a variable component (in addition to
282 values). */
283 bool aggs_contain_variable;
284 /* The value of all aggregate lattices is bottom (i.e. variable and unusable
285 for any propagation). */
286 bool aggs_bottom;
288 /* There is a virtual call based on this parameter. */
289 bool virt_call;
292 /* Allocation pools for values and their sources in ipa-cp. */
294 alloc_pool ipcp_cst_values_pool;
295 alloc_pool ipcp_poly_ctx_values_pool;
296 alloc_pool ipcp_sources_pool;
297 alloc_pool ipcp_agg_lattice_pool;
299 /* Maximal count found in program. */
301 static gcov_type max_count;
303 /* Original overall size of the program. */
305 static long overall_size, max_new_size;
307 /* Return the param lattices structure corresponding to the Ith formal
308 parameter of the function described by INFO. */
309 static inline struct ipcp_param_lattices *
310 ipa_get_parm_lattices (struct ipa_node_params *info, int i)
312 gcc_assert (i >= 0 && i < ipa_get_param_count (info));
313 gcc_checking_assert (!info->ipcp_orig_node);
314 gcc_checking_assert (info->lattices);
315 return &(info->lattices[i]);
318 /* Return the lattice corresponding to the scalar value of the Ith formal
319 parameter of the function described by INFO. */
320 static inline ipcp_lattice<tree> *
321 ipa_get_scalar_lat (struct ipa_node_params *info, int i)
323 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
324 return &plats->itself;
327 /* Return the lattice corresponding to the scalar value of the Ith formal
328 parameter of the function described by INFO. */
329 static inline ipcp_lattice<ipa_polymorphic_call_context> *
330 ipa_get_poly_ctx_lat (struct ipa_node_params *info, int i)
332 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
333 return &plats->ctxlat;
336 /* Return whether LAT is a lattice with a single constant and without an
337 undefined value. */
339 template <typename valtype>
340 inline bool
341 ipcp_lattice<valtype>::is_single_const ()
343 if (bottom || contains_variable || values_count != 1)
344 return false;
345 else
346 return true;
349 /* Print V which is extracted from a value in a lattice to F. */
351 static void
352 print_ipcp_constant_value (FILE * f, tree v)
354 if (TREE_CODE (v) == ADDR_EXPR
355 && TREE_CODE (TREE_OPERAND (v, 0)) == CONST_DECL)
357 fprintf (f, "& ");
358 print_generic_expr (f, DECL_INITIAL (TREE_OPERAND (v, 0)), 0);
360 else
361 print_generic_expr (f, v, 0);
364 /* Print V which is extracted from a value in a lattice to F. */
366 static void
367 print_ipcp_constant_value (FILE * f, ipa_polymorphic_call_context v)
369 v.dump(f, false);
372 /* Print a lattice LAT to F. */
374 template <typename valtype>
375 void
376 ipcp_lattice<valtype>::print (FILE * f, bool dump_sources, bool dump_benefits)
378 ipcp_value<valtype> *val;
379 bool prev = false;
381 if (bottom)
383 fprintf (f, "BOTTOM\n");
384 return;
387 if (!values_count && !contains_variable)
389 fprintf (f, "TOP\n");
390 return;
393 if (contains_variable)
395 fprintf (f, "VARIABLE");
396 prev = true;
397 if (dump_benefits)
398 fprintf (f, "\n");
401 for (val = values; val; val = val->next)
403 if (dump_benefits && prev)
404 fprintf (f, " ");
405 else if (!dump_benefits && prev)
406 fprintf (f, ", ");
407 else
408 prev = true;
410 print_ipcp_constant_value (f, val->value);
412 if (dump_sources)
414 ipcp_value_source<valtype> *s;
416 fprintf (f, " [from:");
417 for (s = val->sources; s; s = s->next)
418 fprintf (f, " %i(%i)", s->cs->caller->order,
419 s->cs->frequency);
420 fprintf (f, "]");
423 if (dump_benefits)
424 fprintf (f, " [loc_time: %i, loc_size: %i, "
425 "prop_time: %i, prop_size: %i]\n",
426 val->local_time_benefit, val->local_size_cost,
427 val->prop_time_benefit, val->prop_size_cost);
429 if (!dump_benefits)
430 fprintf (f, "\n");
433 /* Print all ipcp_lattices of all functions to F. */
435 static void
436 print_all_lattices (FILE * f, bool dump_sources, bool dump_benefits)
438 struct cgraph_node *node;
439 int i, count;
441 fprintf (f, "\nLattices:\n");
442 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
444 struct ipa_node_params *info;
446 info = IPA_NODE_REF (node);
447 fprintf (f, " Node: %s/%i:\n", node->name (),
448 node->order);
449 count = ipa_get_param_count (info);
450 for (i = 0; i < count; i++)
452 struct ipcp_agg_lattice *aglat;
453 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
454 fprintf (f, " param [%d]: ", i);
455 plats->itself.print (f, dump_sources, dump_benefits);
456 fprintf (f, " ctxs: ");
457 plats->ctxlat.print (f, dump_sources, dump_benefits);
458 if (plats->alignment.known && plats->alignment.align > 0)
459 fprintf (f, " Alignment %u, misalignment %u\n",
460 plats->alignment.align, plats->alignment.misalign);
461 else if (plats->alignment.known)
462 fprintf (f, " Alignment unusable\n");
463 else
464 fprintf (f, " Alignment unknown\n");
465 if (plats->virt_call)
466 fprintf (f, " virt_call flag set\n");
468 if (plats->aggs_bottom)
470 fprintf (f, " AGGS BOTTOM\n");
471 continue;
473 if (plats->aggs_contain_variable)
474 fprintf (f, " AGGS VARIABLE\n");
475 for (aglat = plats->aggs; aglat; aglat = aglat->next)
477 fprintf (f, " %soffset " HOST_WIDE_INT_PRINT_DEC ": ",
478 plats->aggs_by_ref ? "ref " : "", aglat->offset);
479 aglat->print (f, dump_sources, dump_benefits);
485 /* Determine whether it is at all technically possible to create clones of NODE
486 and store this information in the ipa_node_params structure associated
487 with NODE. */
489 static void
490 determine_versionability (struct cgraph_node *node)
492 const char *reason = NULL;
494 /* There are a number of generic reasons functions cannot be versioned. We
495 also cannot remove parameters if there are type attributes such as fnspec
496 present. */
497 if (node->alias || node->thunk.thunk_p)
498 reason = "alias or thunk";
499 else if (!node->local.versionable)
500 reason = "not a tree_versionable_function";
501 else if (node->get_availability () <= AVAIL_INTERPOSABLE)
502 reason = "insufficient body availability";
503 else if (!opt_for_fn (node->decl, optimize)
504 || !opt_for_fn (node->decl, flag_ipa_cp))
505 reason = "non-optimized function";
506 else if (lookup_attribute ("omp declare simd", DECL_ATTRIBUTES (node->decl)))
508 /* Ideally we should clone the SIMD clones themselves and create
509 vector copies of them, so IPA-cp and SIMD clones can happily
510 coexist, but that may not be worth the effort. */
511 reason = "function has SIMD clones";
513 /* Don't clone decls local to a comdat group; it breaks and for C++
514 decloned constructors, inlining is always better anyway. */
515 else if (node->comdat_local_p ())
516 reason = "comdat-local function";
518 if (reason && dump_file && !node->alias && !node->thunk.thunk_p)
519 fprintf (dump_file, "Function %s/%i is not versionable, reason: %s.\n",
520 node->name (), node->order, reason);
522 node->local.versionable = (reason == NULL);
525 /* Return true if it is at all technically possible to create clones of a
526 NODE. */
528 static bool
529 ipcp_versionable_function_p (struct cgraph_node *node)
531 return node->local.versionable;
534 /* Structure holding accumulated information about callers of a node. */
536 struct caller_statistics
538 gcov_type count_sum;
539 int n_calls, n_hot_calls, freq_sum;
542 /* Initialize fields of STAT to zeroes. */
544 static inline void
545 init_caller_stats (struct caller_statistics *stats)
547 stats->count_sum = 0;
548 stats->n_calls = 0;
549 stats->n_hot_calls = 0;
550 stats->freq_sum = 0;
553 /* Worker callback of cgraph_for_node_and_aliases accumulating statistics of
554 non-thunk incoming edges to NODE. */
556 static bool
557 gather_caller_stats (struct cgraph_node *node, void *data)
559 struct caller_statistics *stats = (struct caller_statistics *) data;
560 struct cgraph_edge *cs;
562 for (cs = node->callers; cs; cs = cs->next_caller)
563 if (cs->caller->thunk.thunk_p)
564 cs->caller->call_for_symbol_thunks_and_aliases (gather_caller_stats,
565 stats, false);
566 else
568 stats->count_sum += cs->count;
569 stats->freq_sum += cs->frequency;
570 stats->n_calls++;
571 if (cs->maybe_hot_p ())
572 stats->n_hot_calls ++;
574 return false;
578 /* Return true if this NODE is viable candidate for cloning. */
580 static bool
581 ipcp_cloning_candidate_p (struct cgraph_node *node)
583 struct caller_statistics stats;
585 gcc_checking_assert (node->has_gimple_body_p ());
587 if (!opt_for_fn (node->decl, flag_ipa_cp_clone))
589 if (dump_file)
590 fprintf (dump_file, "Not considering %s for cloning; "
591 "-fipa-cp-clone disabled.\n",
592 node->name ());
593 return false;
596 if (!optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node->decl)))
598 if (dump_file)
599 fprintf (dump_file, "Not considering %s for cloning; "
600 "optimizing it for size.\n",
601 node->name ());
602 return false;
605 init_caller_stats (&stats);
606 node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats, false);
608 if (inline_summaries->get (node)->self_size < stats.n_calls)
610 if (dump_file)
611 fprintf (dump_file, "Considering %s for cloning; code might shrink.\n",
612 node->name ());
613 return true;
616 /* When profile is available and function is hot, propagate into it even if
617 calls seems cold; constant propagation can improve function's speed
618 significantly. */
619 if (max_count)
621 if (stats.count_sum > node->count * 90 / 100)
623 if (dump_file)
624 fprintf (dump_file, "Considering %s for cloning; "
625 "usually called directly.\n",
626 node->name ());
627 return true;
630 if (!stats.n_hot_calls)
632 if (dump_file)
633 fprintf (dump_file, "Not considering %s for cloning; no hot calls.\n",
634 node->name ());
635 return false;
637 if (dump_file)
638 fprintf (dump_file, "Considering %s for cloning.\n",
639 node->name ());
640 return true;
643 template <typename valtype>
644 class value_topo_info
646 public:
647 /* Head of the linked list of topologically sorted values. */
648 ipcp_value<valtype> *values_topo;
649 /* Stack for creating SCCs, represented by a linked list too. */
650 ipcp_value<valtype> *stack;
651 /* Counter driving the algorithm in add_val_to_toposort. */
652 int dfs_counter;
654 value_topo_info () : values_topo (NULL), stack (NULL), dfs_counter (0)
656 void add_val (ipcp_value<valtype> *cur_val);
657 void propagate_effects ();
660 /* Arrays representing a topological ordering of call graph nodes and a stack
661 of nodes used during constant propagation and also data required to perform
662 topological sort of values and propagation of benefits in the determined
663 order. */
665 class ipa_topo_info
667 public:
668 /* Array with obtained topological order of cgraph nodes. */
669 struct cgraph_node **order;
670 /* Stack of cgraph nodes used during propagation within SCC until all values
671 in the SCC stabilize. */
672 struct cgraph_node **stack;
673 int nnodes, stack_top;
675 value_topo_info<tree> constants;
676 value_topo_info<ipa_polymorphic_call_context> contexts;
678 ipa_topo_info () : order(NULL), stack(NULL), nnodes(0), stack_top(0),
679 constants ()
683 /* Allocate the arrays in TOPO and topologically sort the nodes into order. */
685 static void
686 build_toporder_info (struct ipa_topo_info *topo)
688 topo->order = XCNEWVEC (struct cgraph_node *, symtab->cgraph_count);
689 topo->stack = XCNEWVEC (struct cgraph_node *, symtab->cgraph_count);
691 gcc_checking_assert (topo->stack_top == 0);
692 topo->nnodes = ipa_reduced_postorder (topo->order, true, true, NULL);
695 /* Free information about strongly connected components and the arrays in
696 TOPO. */
698 static void
699 free_toporder_info (struct ipa_topo_info *topo)
701 ipa_free_postorder_info ();
702 free (topo->order);
703 free (topo->stack);
706 /* Add NODE to the stack in TOPO, unless it is already there. */
708 static inline void
709 push_node_to_stack (struct ipa_topo_info *topo, struct cgraph_node *node)
711 struct ipa_node_params *info = IPA_NODE_REF (node);
712 if (info->node_enqueued)
713 return;
714 info->node_enqueued = 1;
715 topo->stack[topo->stack_top++] = node;
718 /* Pop a node from the stack in TOPO and return it or return NULL if the stack
719 is empty. */
721 static struct cgraph_node *
722 pop_node_from_stack (struct ipa_topo_info *topo)
724 if (topo->stack_top)
726 struct cgraph_node *node;
727 topo->stack_top--;
728 node = topo->stack[topo->stack_top];
729 IPA_NODE_REF (node)->node_enqueued = 0;
730 return node;
732 else
733 return NULL;
736 /* Set lattice LAT to bottom and return true if it previously was not set as
737 such. */
739 template <typename valtype>
740 inline bool
741 ipcp_lattice<valtype>::set_to_bottom ()
743 bool ret = !bottom;
744 bottom = true;
745 return ret;
748 /* Mark lattice as containing an unknown value and return true if it previously
749 was not marked as such. */
751 template <typename valtype>
752 inline bool
753 ipcp_lattice<valtype>::set_contains_variable ()
755 bool ret = !contains_variable;
756 contains_variable = true;
757 return ret;
760 /* Set all aggegate lattices in PLATS to bottom and return true if they were
761 not previously set as such. */
763 static inline bool
764 set_agg_lats_to_bottom (struct ipcp_param_lattices *plats)
766 bool ret = !plats->aggs_bottom;
767 plats->aggs_bottom = true;
768 return ret;
771 /* Mark all aggegate lattices in PLATS as containing an unknown value and
772 return true if they were not previously marked as such. */
774 static inline bool
775 set_agg_lats_contain_variable (struct ipcp_param_lattices *plats)
777 bool ret = !plats->aggs_contain_variable;
778 plats->aggs_contain_variable = true;
779 return ret;
782 /* Return true if alignment information in PLATS is known to be unusable. */
784 static inline bool
785 alignment_bottom_p (ipcp_param_lattices *plats)
787 return plats->alignment.known && (plats->alignment.align == 0);
790 /* Set alignment information in PLATS to unusable. Return true if it
791 previously was usable or unknown. */
793 static inline bool
794 set_alignment_to_bottom (ipcp_param_lattices *plats)
796 if (alignment_bottom_p (plats))
797 return false;
798 plats->alignment.known = true;
799 plats->alignment.align = 0;
800 return true;
803 /* Mark bot aggregate and scalar lattices as containing an unknown variable,
804 return true is any of them has not been marked as such so far. */
806 static inline bool
807 set_all_contains_variable (struct ipcp_param_lattices *plats)
809 bool ret;
810 ret = plats->itself.set_contains_variable ();
811 ret |= plats->ctxlat.set_contains_variable ();
812 ret |= set_agg_lats_contain_variable (plats);
813 ret |= set_alignment_to_bottom (plats);
814 return ret;
817 /* Initialize ipcp_lattices. */
819 static void
820 initialize_node_lattices (struct cgraph_node *node)
822 struct ipa_node_params *info = IPA_NODE_REF (node);
823 struct cgraph_edge *ie;
824 bool disable = false, variable = false;
825 int i;
827 gcc_checking_assert (node->has_gimple_body_p ());
828 if (!cgraph_local_p (node))
830 /* When cloning is allowed, we can assume that externally visible
831 functions are not called. We will compensate this by cloning
832 later. */
833 if (ipcp_versionable_function_p (node)
834 && ipcp_cloning_candidate_p (node))
835 variable = true;
836 else
837 disable = true;
840 if (disable || variable)
842 for (i = 0; i < ipa_get_param_count (info) ; i++)
844 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
845 if (disable)
847 plats->itself.set_to_bottom ();
848 plats->ctxlat.set_to_bottom ();
849 set_agg_lats_to_bottom (plats);
850 set_alignment_to_bottom (plats);
852 else
853 set_all_contains_variable (plats);
855 if (dump_file && (dump_flags & TDF_DETAILS)
856 && !node->alias && !node->thunk.thunk_p)
857 fprintf (dump_file, "Marking all lattices of %s/%i as %s\n",
858 node->name (), node->order,
859 disable ? "BOTTOM" : "VARIABLE");
862 for (ie = node->indirect_calls; ie; ie = ie->next_callee)
863 if (ie->indirect_info->polymorphic
864 && ie->indirect_info->param_index >= 0)
866 gcc_checking_assert (ie->indirect_info->param_index >= 0);
867 ipa_get_parm_lattices (info,
868 ie->indirect_info->param_index)->virt_call = 1;
872 /* Return the result of a (possibly arithmetic) pass through jump function
873 JFUNC on the constant value INPUT. Return NULL_TREE if that cannot be
874 determined or be considered an interprocedural invariant. */
876 static tree
877 ipa_get_jf_pass_through_result (struct ipa_jump_func *jfunc, tree input)
879 tree restype, res;
881 gcc_checking_assert (is_gimple_ip_invariant (input));
882 if (ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
883 return input;
885 if (TREE_CODE_CLASS (ipa_get_jf_pass_through_operation (jfunc))
886 == tcc_comparison)
887 restype = boolean_type_node;
888 else
889 restype = TREE_TYPE (input);
890 res = fold_binary (ipa_get_jf_pass_through_operation (jfunc), restype,
891 input, ipa_get_jf_pass_through_operand (jfunc));
893 if (res && !is_gimple_ip_invariant (res))
894 return NULL_TREE;
896 return res;
899 /* Return the result of an ancestor jump function JFUNC on the constant value
900 INPUT. Return NULL_TREE if that cannot be determined. */
902 static tree
903 ipa_get_jf_ancestor_result (struct ipa_jump_func *jfunc, tree input)
905 gcc_checking_assert (TREE_CODE (input) != TREE_BINFO);
906 if (TREE_CODE (input) == ADDR_EXPR)
908 tree t = TREE_OPERAND (input, 0);
909 t = build_ref_for_offset (EXPR_LOCATION (t), t,
910 ipa_get_jf_ancestor_offset (jfunc),
911 ptr_type_node, NULL, false);
912 return build_fold_addr_expr (t);
914 else
915 return NULL_TREE;
918 /* Determine whether JFUNC evaluates to a single known constant value and if
919 so, return it. Otherwise return NULL. INFO describes the caller node or
920 the one it is inlined to, so that pass-through jump functions can be
921 evaluated. */
923 tree
924 ipa_value_from_jfunc (struct ipa_node_params *info, struct ipa_jump_func *jfunc)
926 if (jfunc->type == IPA_JF_CONST)
927 return ipa_get_jf_constant (jfunc);
928 else if (jfunc->type == IPA_JF_PASS_THROUGH
929 || jfunc->type == IPA_JF_ANCESTOR)
931 tree input;
932 int idx;
934 if (jfunc->type == IPA_JF_PASS_THROUGH)
935 idx = ipa_get_jf_pass_through_formal_id (jfunc);
936 else
937 idx = ipa_get_jf_ancestor_formal_id (jfunc);
939 if (info->ipcp_orig_node)
940 input = info->known_csts[idx];
941 else
943 ipcp_lattice<tree> *lat;
945 if (!info->lattices)
946 return NULL_TREE;
947 lat = ipa_get_scalar_lat (info, idx);
948 if (!lat->is_single_const ())
949 return NULL_TREE;
950 input = lat->values->value;
953 if (!input)
954 return NULL_TREE;
956 if (jfunc->type == IPA_JF_PASS_THROUGH)
957 return ipa_get_jf_pass_through_result (jfunc, input);
958 else
959 return ipa_get_jf_ancestor_result (jfunc, input);
961 else
962 return NULL_TREE;
965 /* Determie whether JFUNC evaluates to single known polymorphic context, given
966 that INFO describes the caller node or the one it is inlined to, CS is the
967 call graph edge corresponding to JFUNC and CSIDX index of the described
968 parameter. */
970 ipa_polymorphic_call_context
971 ipa_context_from_jfunc (ipa_node_params *info, cgraph_edge *cs, int csidx,
972 ipa_jump_func *jfunc)
974 ipa_edge_args *args = IPA_EDGE_REF (cs);
975 ipa_polymorphic_call_context ctx;
976 ipa_polymorphic_call_context *edge_ctx
977 = cs ? ipa_get_ith_polymorhic_call_context (args, csidx) : NULL;
979 if (edge_ctx && !edge_ctx->useless_p ())
980 ctx = *edge_ctx;
982 if (jfunc->type == IPA_JF_PASS_THROUGH
983 || jfunc->type == IPA_JF_ANCESTOR)
985 ipa_polymorphic_call_context srcctx;
986 int srcidx;
987 bool type_preserved = true;
988 if (jfunc->type == IPA_JF_PASS_THROUGH)
990 if (ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR)
991 return ctx;
992 type_preserved = ipa_get_jf_pass_through_type_preserved (jfunc);
993 srcidx = ipa_get_jf_pass_through_formal_id (jfunc);
995 else
997 type_preserved = ipa_get_jf_ancestor_type_preserved (jfunc);
998 srcidx = ipa_get_jf_ancestor_formal_id (jfunc);
1000 if (info->ipcp_orig_node)
1002 if (info->known_contexts.exists ())
1003 srcctx = info->known_contexts[srcidx];
1005 else
1007 if (!info->lattices)
1008 return ctx;
1009 ipcp_lattice<ipa_polymorphic_call_context> *lat;
1010 lat = ipa_get_poly_ctx_lat (info, srcidx);
1011 if (!lat->is_single_const ())
1012 return ctx;
1013 srcctx = lat->values->value;
1015 if (srcctx.useless_p ())
1016 return ctx;
1017 if (jfunc->type == IPA_JF_ANCESTOR)
1018 srcctx.offset_by (ipa_get_jf_ancestor_offset (jfunc));
1019 if (!type_preserved)
1020 srcctx.possible_dynamic_type_change (cs->in_polymorphic_cdtor);
1021 srcctx.combine_with (ctx);
1022 return srcctx;
1025 return ctx;
1028 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
1029 bottom, not containing a variable component and without any known value at
1030 the same time. */
1032 DEBUG_FUNCTION void
1033 ipcp_verify_propagated_values (void)
1035 struct cgraph_node *node;
1037 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
1039 struct ipa_node_params *info = IPA_NODE_REF (node);
1040 int i, count = ipa_get_param_count (info);
1042 for (i = 0; i < count; i++)
1044 ipcp_lattice<tree> *lat = ipa_get_scalar_lat (info, i);
1046 if (!lat->bottom
1047 && !lat->contains_variable
1048 && lat->values_count == 0)
1050 if (dump_file)
1052 symtab_node::dump_table (dump_file);
1053 fprintf (dump_file, "\nIPA lattices after constant "
1054 "propagation, before gcc_unreachable:\n");
1055 print_all_lattices (dump_file, true, false);
1058 gcc_unreachable ();
1064 /* Return true iff X and Y should be considered equal values by IPA-CP. */
1066 static bool
1067 values_equal_for_ipcp_p (tree x, tree y)
1069 gcc_checking_assert (x != NULL_TREE && y != NULL_TREE);
1071 if (x == y)
1072 return true;
1074 if (TREE_CODE (x) == ADDR_EXPR
1075 && TREE_CODE (y) == ADDR_EXPR
1076 && TREE_CODE (TREE_OPERAND (x, 0)) == CONST_DECL
1077 && TREE_CODE (TREE_OPERAND (y, 0)) == CONST_DECL)
1078 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x, 0)),
1079 DECL_INITIAL (TREE_OPERAND (y, 0)), 0);
1080 else
1081 return operand_equal_p (x, y, 0);
1084 /* Return true iff X and Y should be considered equal contexts by IPA-CP. */
1086 static bool
1087 values_equal_for_ipcp_p (ipa_polymorphic_call_context x,
1088 ipa_polymorphic_call_context y)
1090 return x.equal_to (y);
1094 /* Add a new value source to the value represented by THIS, marking that a
1095 value comes from edge CS and (if the underlying jump function is a
1096 pass-through or an ancestor one) from a caller value SRC_VAL of a caller
1097 parameter described by SRC_INDEX. OFFSET is negative if the source was the
1098 scalar value of the parameter itself or the offset within an aggregate. */
1100 template <typename valtype>
1101 void
1102 ipcp_value<valtype>::add_source (cgraph_edge *cs, ipcp_value *src_val,
1103 int src_idx, HOST_WIDE_INT offset)
1105 ipcp_value_source<valtype> *src;
1107 src = new (pool_alloc (ipcp_sources_pool)) ipcp_value_source<valtype>;
1108 src->offset = offset;
1109 src->cs = cs;
1110 src->val = src_val;
1111 src->index = src_idx;
1113 src->next = sources;
1114 sources = src;
1117 /* Allocate a new ipcp_value holding a tree constant, initialize its value to
1118 SOURCE and clear all other fields. */
1120 static ipcp_value<tree> *
1121 allocate_and_init_ipcp_value (tree source)
1123 ipcp_value<tree> *val;
1125 val = new (pool_alloc (ipcp_cst_values_pool)) ipcp_value<tree>;
1126 memset (val, 0, sizeof (*val));
1127 val->value = source;
1128 return val;
1131 /* Allocate a new ipcp_value holding a polymorphic context, initialize its
1132 value to SOURCE and clear all other fields. */
1134 static ipcp_value<ipa_polymorphic_call_context> *
1135 allocate_and_init_ipcp_value (ipa_polymorphic_call_context source)
1137 ipcp_value<ipa_polymorphic_call_context> *val;
1139 val = new (pool_alloc (ipcp_poly_ctx_values_pool))
1140 ipcp_value<ipa_polymorphic_call_context>;
1141 memset (val, 0, sizeof (*val));
1142 val->value = source;
1143 return val;
1146 /* Try to add NEWVAL to LAT, potentially creating a new ipcp_value for it. CS,
1147 SRC_VAL SRC_INDEX and OFFSET are meant for add_source and have the same
1148 meaning. OFFSET -1 means the source is scalar and not a part of an
1149 aggregate. */
1151 template <typename valtype>
1152 bool
1153 ipcp_lattice<valtype>::add_value (valtype newval, cgraph_edge *cs,
1154 ipcp_value<valtype> *src_val,
1155 int src_idx, HOST_WIDE_INT offset)
1157 ipcp_value<valtype> *val;
1159 if (bottom)
1160 return false;
1162 for (val = values; val; val = val->next)
1163 if (values_equal_for_ipcp_p (val->value, newval))
1165 if (ipa_edge_within_scc (cs))
1167 ipcp_value_source<valtype> *s;
1168 for (s = val->sources; s ; s = s->next)
1169 if (s->cs == cs)
1170 break;
1171 if (s)
1172 return false;
1175 val->add_source (cs, src_val, src_idx, offset);
1176 return false;
1179 if (values_count == PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE))
1181 /* We can only free sources, not the values themselves, because sources
1182 of other values in this this SCC might point to them. */
1183 for (val = values; val; val = val->next)
1185 while (val->sources)
1187 ipcp_value_source<valtype> *src = val->sources;
1188 val->sources = src->next;
1189 pool_free (ipcp_sources_pool, src);
1193 values = NULL;
1194 return set_to_bottom ();
1197 values_count++;
1198 val = allocate_and_init_ipcp_value (newval);
1199 val->add_source (cs, src_val, src_idx, offset);
1200 val->next = values;
1201 values = val;
1202 return true;
1205 /* Propagate values through a pass-through jump function JFUNC associated with
1206 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1207 is the index of the source parameter. */
1209 static bool
1210 propagate_vals_accross_pass_through (cgraph_edge *cs,
1211 ipa_jump_func *jfunc,
1212 ipcp_lattice<tree> *src_lat,
1213 ipcp_lattice<tree> *dest_lat,
1214 int src_idx)
1216 ipcp_value<tree> *src_val;
1217 bool ret = false;
1219 /* Do not create new values when propagating within an SCC because if there
1220 are arithmetic functions with circular dependencies, there is infinite
1221 number of them and we would just make lattices bottom. */
1222 if ((ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR)
1223 && ipa_edge_within_scc (cs))
1224 ret = dest_lat->set_contains_variable ();
1225 else
1226 for (src_val = src_lat->values; src_val; src_val = src_val->next)
1228 tree cstval = ipa_get_jf_pass_through_result (jfunc, src_val->value);
1230 if (cstval)
1231 ret |= dest_lat->add_value (cstval, cs, src_val, src_idx);
1232 else
1233 ret |= dest_lat->set_contains_variable ();
1236 return ret;
1239 /* Propagate values through an ancestor jump function JFUNC associated with
1240 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1241 is the index of the source parameter. */
1243 static bool
1244 propagate_vals_accross_ancestor (struct cgraph_edge *cs,
1245 struct ipa_jump_func *jfunc,
1246 ipcp_lattice<tree> *src_lat,
1247 ipcp_lattice<tree> *dest_lat,
1248 int src_idx)
1250 ipcp_value<tree> *src_val;
1251 bool ret = false;
1253 if (ipa_edge_within_scc (cs))
1254 return dest_lat->set_contains_variable ();
1256 for (src_val = src_lat->values; src_val; src_val = src_val->next)
1258 tree t = ipa_get_jf_ancestor_result (jfunc, src_val->value);
1260 if (t)
1261 ret |= dest_lat->add_value (t, cs, src_val, src_idx);
1262 else
1263 ret |= dest_lat->set_contains_variable ();
1266 return ret;
1269 /* Propagate scalar values across jump function JFUNC that is associated with
1270 edge CS and put the values into DEST_LAT. */
1272 static bool
1273 propagate_scalar_accross_jump_function (struct cgraph_edge *cs,
1274 struct ipa_jump_func *jfunc,
1275 ipcp_lattice<tree> *dest_lat)
1277 if (dest_lat->bottom)
1278 return false;
1280 if (jfunc->type == IPA_JF_CONST)
1282 tree val = ipa_get_jf_constant (jfunc);
1283 return dest_lat->add_value (val, cs, NULL, 0);
1285 else if (jfunc->type == IPA_JF_PASS_THROUGH
1286 || jfunc->type == IPA_JF_ANCESTOR)
1288 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1289 ipcp_lattice<tree> *src_lat;
1290 int src_idx;
1291 bool ret;
1293 if (jfunc->type == IPA_JF_PASS_THROUGH)
1294 src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
1295 else
1296 src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
1298 src_lat = ipa_get_scalar_lat (caller_info, src_idx);
1299 if (src_lat->bottom)
1300 return dest_lat->set_contains_variable ();
1302 /* If we would need to clone the caller and cannot, do not propagate. */
1303 if (!ipcp_versionable_function_p (cs->caller)
1304 && (src_lat->contains_variable
1305 || (src_lat->values_count > 1)))
1306 return dest_lat->set_contains_variable ();
1308 if (jfunc->type == IPA_JF_PASS_THROUGH)
1309 ret = propagate_vals_accross_pass_through (cs, jfunc, src_lat,
1310 dest_lat, src_idx);
1311 else
1312 ret = propagate_vals_accross_ancestor (cs, jfunc, src_lat, dest_lat,
1313 src_idx);
1315 if (src_lat->contains_variable)
1316 ret |= dest_lat->set_contains_variable ();
1318 return ret;
1321 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1322 use it for indirect inlining), we should propagate them too. */
1323 return dest_lat->set_contains_variable ();
1326 /* Propagate scalar values across jump function JFUNC that is associated with
1327 edge CS and describes argument IDX and put the values into DEST_LAT. */
1329 static bool
1330 propagate_context_accross_jump_function (cgraph_edge *cs,
1331 ipa_jump_func *jfunc, int idx,
1332 ipcp_lattice<ipa_polymorphic_call_context> *dest_lat)
1334 ipa_edge_args *args = IPA_EDGE_REF (cs);
1335 if (dest_lat->bottom)
1336 return false;
1337 bool ret = false;
1338 bool added_sth = false;
1339 bool type_preserved = true;
1341 ipa_polymorphic_call_context edge_ctx, *edge_ctx_ptr
1342 = ipa_get_ith_polymorhic_call_context (args, idx);
1344 if (edge_ctx_ptr)
1345 edge_ctx = *edge_ctx_ptr;
1347 if (jfunc->type == IPA_JF_PASS_THROUGH
1348 || jfunc->type == IPA_JF_ANCESTOR)
1350 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1351 int src_idx;
1352 ipcp_lattice<ipa_polymorphic_call_context> *src_lat;
1354 /* TODO: Once we figure out how to propagate speculations, it will
1355 probably be a good idea to switch to speculation if type_preserved is
1356 not set instead of punting. */
1357 if (jfunc->type == IPA_JF_PASS_THROUGH)
1359 if (ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR)
1360 goto prop_fail;
1361 type_preserved = ipa_get_jf_pass_through_type_preserved (jfunc);
1362 src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
1364 else
1366 type_preserved = ipa_get_jf_ancestor_type_preserved (jfunc);
1367 src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
1370 src_lat = ipa_get_poly_ctx_lat (caller_info, src_idx);
1371 /* If we would need to clone the caller and cannot, do not propagate. */
1372 if (!ipcp_versionable_function_p (cs->caller)
1373 && (src_lat->contains_variable
1374 || (src_lat->values_count > 1)))
1375 goto prop_fail;
1377 ipcp_value<ipa_polymorphic_call_context> *src_val;
1378 for (src_val = src_lat->values; src_val; src_val = src_val->next)
1380 ipa_polymorphic_call_context cur = src_val->value;
1382 if (!type_preserved)
1383 cur.possible_dynamic_type_change (cs->in_polymorphic_cdtor);
1384 if (jfunc->type == IPA_JF_ANCESTOR)
1385 cur.offset_by (ipa_get_jf_ancestor_offset (jfunc));
1386 /* TODO: In cases we know how the context is going to be used,
1387 we can improve the result by passing proper OTR_TYPE. */
1388 cur.combine_with (edge_ctx);
1389 if (!cur.useless_p ())
1391 if (src_lat->contains_variable
1392 && !edge_ctx.equal_to (cur))
1393 ret |= dest_lat->set_contains_variable ();
1394 ret |= dest_lat->add_value (cur, cs, src_val, src_idx);
1395 added_sth = true;
1401 prop_fail:
1402 if (!added_sth)
1404 if (!edge_ctx.useless_p ())
1405 ret |= dest_lat->add_value (edge_ctx, cs);
1406 else
1407 ret |= dest_lat->set_contains_variable ();
1410 return ret;
1413 /* Propagate alignments across jump function JFUNC that is associated with
1414 edge CS and update DEST_LAT accordingly. */
1416 static bool
1417 propagate_alignment_accross_jump_function (struct cgraph_edge *cs,
1418 struct ipa_jump_func *jfunc,
1419 struct ipcp_param_lattices *dest_lat)
1421 if (alignment_bottom_p (dest_lat))
1422 return false;
1424 ipa_alignment cur;
1425 cur.known = false;
1426 if (jfunc->alignment.known)
1427 cur = jfunc->alignment;
1428 else if (jfunc->type == IPA_JF_PASS_THROUGH
1429 || jfunc->type == IPA_JF_ANCESTOR)
1431 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1432 struct ipcp_param_lattices *src_lats;
1433 HOST_WIDE_INT offset = 0;
1434 int src_idx;
1436 if (jfunc->type == IPA_JF_PASS_THROUGH)
1438 enum tree_code op = ipa_get_jf_pass_through_operation (jfunc);
1439 if (op != NOP_EXPR)
1441 if (op != POINTER_PLUS_EXPR
1442 && op != PLUS_EXPR
1443 && op != MINUS_EXPR)
1444 goto prop_fail;
1445 tree operand = ipa_get_jf_pass_through_operand (jfunc);
1446 if (!tree_fits_shwi_p (operand))
1447 goto prop_fail;
1448 offset = tree_to_shwi (operand);
1450 src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
1452 else
1454 src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
1455 offset = ipa_get_jf_ancestor_offset (jfunc);
1458 src_lats = ipa_get_parm_lattices (caller_info, src_idx);
1459 if (!src_lats->alignment.known
1460 || alignment_bottom_p (src_lats))
1461 goto prop_fail;
1463 cur = src_lats->alignment;
1464 cur.misalign = (cur.misalign + offset) % cur.align;
1467 if (cur.known)
1469 if (!dest_lat->alignment.known)
1471 dest_lat->alignment = cur;
1472 return true;
1474 else if (dest_lat->alignment.align == cur.align
1475 && dest_lat->alignment.misalign == cur.misalign)
1476 return false;
1479 prop_fail:
1480 set_alignment_to_bottom (dest_lat);
1481 return true;
1484 /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
1485 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
1486 other cases, return false). If there are no aggregate items, set
1487 aggs_by_ref to NEW_AGGS_BY_REF. */
1489 static bool
1490 set_check_aggs_by_ref (struct ipcp_param_lattices *dest_plats,
1491 bool new_aggs_by_ref)
1493 if (dest_plats->aggs)
1495 if (dest_plats->aggs_by_ref != new_aggs_by_ref)
1497 set_agg_lats_to_bottom (dest_plats);
1498 return true;
1501 else
1502 dest_plats->aggs_by_ref = new_aggs_by_ref;
1503 return false;
1506 /* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
1507 already existing lattice for the given OFFSET and SIZE, marking all skipped
1508 lattices as containing variable and checking for overlaps. If there is no
1509 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
1510 it with offset, size and contains_variable to PRE_EXISTING, and return true,
1511 unless there are too many already. If there are two many, return false. If
1512 there are overlaps turn whole DEST_PLATS to bottom and return false. If any
1513 skipped lattices were newly marked as containing variable, set *CHANGE to
1514 true. */
1516 static bool
1517 merge_agg_lats_step (struct ipcp_param_lattices *dest_plats,
1518 HOST_WIDE_INT offset, HOST_WIDE_INT val_size,
1519 struct ipcp_agg_lattice ***aglat,
1520 bool pre_existing, bool *change)
1522 gcc_checking_assert (offset >= 0);
1524 while (**aglat && (**aglat)->offset < offset)
1526 if ((**aglat)->offset + (**aglat)->size > offset)
1528 set_agg_lats_to_bottom (dest_plats);
1529 return false;
1531 *change |= (**aglat)->set_contains_variable ();
1532 *aglat = &(**aglat)->next;
1535 if (**aglat && (**aglat)->offset == offset)
1537 if ((**aglat)->size != val_size
1538 || ((**aglat)->next
1539 && (**aglat)->next->offset < offset + val_size))
1541 set_agg_lats_to_bottom (dest_plats);
1542 return false;
1544 gcc_checking_assert (!(**aglat)->next
1545 || (**aglat)->next->offset >= offset + val_size);
1546 return true;
1548 else
1550 struct ipcp_agg_lattice *new_al;
1552 if (**aglat && (**aglat)->offset < offset + val_size)
1554 set_agg_lats_to_bottom (dest_plats);
1555 return false;
1557 if (dest_plats->aggs_count == PARAM_VALUE (PARAM_IPA_MAX_AGG_ITEMS))
1558 return false;
1559 dest_plats->aggs_count++;
1560 new_al = (struct ipcp_agg_lattice *) pool_alloc (ipcp_agg_lattice_pool);
1561 memset (new_al, 0, sizeof (*new_al));
1563 new_al->offset = offset;
1564 new_al->size = val_size;
1565 new_al->contains_variable = pre_existing;
1567 new_al->next = **aglat;
1568 **aglat = new_al;
1569 return true;
1573 /* Set all AGLAT and all other aggregate lattices reachable by next pointers as
1574 containing an unknown value. */
1576 static bool
1577 set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice *aglat)
1579 bool ret = false;
1580 while (aglat)
1582 ret |= aglat->set_contains_variable ();
1583 aglat = aglat->next;
1585 return ret;
1588 /* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
1589 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source
1590 parameter used for lattice value sources. Return true if DEST_PLATS changed
1591 in any way. */
1593 static bool
1594 merge_aggregate_lattices (struct cgraph_edge *cs,
1595 struct ipcp_param_lattices *dest_plats,
1596 struct ipcp_param_lattices *src_plats,
1597 int src_idx, HOST_WIDE_INT offset_delta)
1599 bool pre_existing = dest_plats->aggs != NULL;
1600 struct ipcp_agg_lattice **dst_aglat;
1601 bool ret = false;
1603 if (set_check_aggs_by_ref (dest_plats, src_plats->aggs_by_ref))
1604 return true;
1605 if (src_plats->aggs_bottom)
1606 return set_agg_lats_contain_variable (dest_plats);
1607 if (src_plats->aggs_contain_variable)
1608 ret |= set_agg_lats_contain_variable (dest_plats);
1609 dst_aglat = &dest_plats->aggs;
1611 for (struct ipcp_agg_lattice *src_aglat = src_plats->aggs;
1612 src_aglat;
1613 src_aglat = src_aglat->next)
1615 HOST_WIDE_INT new_offset = src_aglat->offset - offset_delta;
1617 if (new_offset < 0)
1618 continue;
1619 if (merge_agg_lats_step (dest_plats, new_offset, src_aglat->size,
1620 &dst_aglat, pre_existing, &ret))
1622 struct ipcp_agg_lattice *new_al = *dst_aglat;
1624 dst_aglat = &(*dst_aglat)->next;
1625 if (src_aglat->bottom)
1627 ret |= new_al->set_contains_variable ();
1628 continue;
1630 if (src_aglat->contains_variable)
1631 ret |= new_al->set_contains_variable ();
1632 for (ipcp_value<tree> *val = src_aglat->values;
1633 val;
1634 val = val->next)
1635 ret |= new_al->add_value (val->value, cs, val, src_idx,
1636 src_aglat->offset);
1638 else if (dest_plats->aggs_bottom)
1639 return true;
1641 ret |= set_chain_of_aglats_contains_variable (*dst_aglat);
1642 return ret;
1645 /* Determine whether there is anything to propagate FROM SRC_PLATS through a
1646 pass-through JFUNC and if so, whether it has conform and conforms to the
1647 rules about propagating values passed by reference. */
1649 static bool
1650 agg_pass_through_permissible_p (struct ipcp_param_lattices *src_plats,
1651 struct ipa_jump_func *jfunc)
1653 return src_plats->aggs
1654 && (!src_plats->aggs_by_ref
1655 || ipa_get_jf_pass_through_agg_preserved (jfunc));
1658 /* Propagate scalar values across jump function JFUNC that is associated with
1659 edge CS and put the values into DEST_LAT. */
1661 static bool
1662 propagate_aggs_accross_jump_function (struct cgraph_edge *cs,
1663 struct ipa_jump_func *jfunc,
1664 struct ipcp_param_lattices *dest_plats)
1666 bool ret = false;
1668 if (dest_plats->aggs_bottom)
1669 return false;
1671 if (jfunc->type == IPA_JF_PASS_THROUGH
1672 && ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
1674 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1675 int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
1676 struct ipcp_param_lattices *src_plats;
1678 src_plats = ipa_get_parm_lattices (caller_info, src_idx);
1679 if (agg_pass_through_permissible_p (src_plats, jfunc))
1681 /* Currently we do not produce clobber aggregate jump
1682 functions, replace with merging when we do. */
1683 gcc_assert (!jfunc->agg.items);
1684 ret |= merge_aggregate_lattices (cs, dest_plats, src_plats,
1685 src_idx, 0);
1687 else
1688 ret |= set_agg_lats_contain_variable (dest_plats);
1690 else if (jfunc->type == IPA_JF_ANCESTOR
1691 && ipa_get_jf_ancestor_agg_preserved (jfunc))
1693 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1694 int src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
1695 struct ipcp_param_lattices *src_plats;
1697 src_plats = ipa_get_parm_lattices (caller_info, src_idx);
1698 if (src_plats->aggs && src_plats->aggs_by_ref)
1700 /* Currently we do not produce clobber aggregate jump
1701 functions, replace with merging when we do. */
1702 gcc_assert (!jfunc->agg.items);
1703 ret |= merge_aggregate_lattices (cs, dest_plats, src_plats, src_idx,
1704 ipa_get_jf_ancestor_offset (jfunc));
1706 else if (!src_plats->aggs_by_ref)
1707 ret |= set_agg_lats_to_bottom (dest_plats);
1708 else
1709 ret |= set_agg_lats_contain_variable (dest_plats);
1711 else if (jfunc->agg.items)
1713 bool pre_existing = dest_plats->aggs != NULL;
1714 struct ipcp_agg_lattice **aglat = &dest_plats->aggs;
1715 struct ipa_agg_jf_item *item;
1716 int i;
1718 if (set_check_aggs_by_ref (dest_plats, jfunc->agg.by_ref))
1719 return true;
1721 FOR_EACH_VEC_ELT (*jfunc->agg.items, i, item)
1723 HOST_WIDE_INT val_size;
1725 if (item->offset < 0)
1726 continue;
1727 gcc_checking_assert (is_gimple_ip_invariant (item->value));
1728 val_size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (item->value)));
1730 if (merge_agg_lats_step (dest_plats, item->offset, val_size,
1731 &aglat, pre_existing, &ret))
1733 ret |= (*aglat)->add_value (item->value, cs, NULL, 0, 0);
1734 aglat = &(*aglat)->next;
1736 else if (dest_plats->aggs_bottom)
1737 return true;
1740 ret |= set_chain_of_aglats_contains_variable (*aglat);
1742 else
1743 ret |= set_agg_lats_contain_variable (dest_plats);
1745 return ret;
1748 /* Propagate constants from the caller to the callee of CS. INFO describes the
1749 caller. */
1751 static bool
1752 propagate_constants_accross_call (struct cgraph_edge *cs)
1754 struct ipa_node_params *callee_info;
1755 enum availability availability;
1756 struct cgraph_node *callee, *alias_or_thunk;
1757 struct ipa_edge_args *args;
1758 bool ret = false;
1759 int i, args_count, parms_count;
1761 callee = cs->callee->function_symbol (&availability);
1762 if (!callee->definition)
1763 return false;
1764 gcc_checking_assert (callee->has_gimple_body_p ());
1765 callee_info = IPA_NODE_REF (callee);
1767 args = IPA_EDGE_REF (cs);
1768 args_count = ipa_get_cs_argument_count (args);
1769 parms_count = ipa_get_param_count (callee_info);
1770 if (parms_count == 0)
1771 return false;
1773 /* No propagation through instrumentation thunks is available yet.
1774 It should be possible with proper mapping of call args and
1775 instrumented callee params in the propagation loop below. But
1776 this case mostly occurs when legacy code calls instrumented code
1777 and it is not a primary target for optimizations.
1778 We detect instrumentation thunks in aliases and thunks chain by
1779 checking instrumentation_clone flag for chain source and target.
1780 Going through instrumentation thunks we always have it changed
1781 from 0 to 1 and all other nodes do not change it. */
1782 if (!cs->callee->instrumentation_clone
1783 && callee->instrumentation_clone)
1785 for (i = 0; i < parms_count; i++)
1786 ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info,
1787 i));
1788 return ret;
1791 /* If this call goes through a thunk we must not propagate to the first (0th)
1792 parameter. However, we might need to uncover a thunk from below a series
1793 of aliases first. */
1794 alias_or_thunk = cs->callee;
1795 while (alias_or_thunk->alias)
1796 alias_or_thunk = alias_or_thunk->get_alias_target ();
1797 if (alias_or_thunk->thunk.thunk_p)
1799 ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info,
1800 0));
1801 i = 1;
1803 else
1804 i = 0;
1806 for (; (i < args_count) && (i < parms_count); i++)
1808 struct ipa_jump_func *jump_func = ipa_get_ith_jump_func (args, i);
1809 struct ipcp_param_lattices *dest_plats;
1811 dest_plats = ipa_get_parm_lattices (callee_info, i);
1812 if (availability == AVAIL_INTERPOSABLE)
1813 ret |= set_all_contains_variable (dest_plats);
1814 else
1816 ret |= propagate_scalar_accross_jump_function (cs, jump_func,
1817 &dest_plats->itself);
1818 ret |= propagate_context_accross_jump_function (cs, jump_func, i,
1819 &dest_plats->ctxlat);
1820 ret |= propagate_alignment_accross_jump_function (cs, jump_func,
1821 dest_plats);
1822 ret |= propagate_aggs_accross_jump_function (cs, jump_func,
1823 dest_plats);
1826 for (; i < parms_count; i++)
1827 ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info, i));
1829 return ret;
1832 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
1833 KNOWN_CONTEXTS, KNOWN_AGGS or AGG_REPS return the destination. The latter
1834 three can be NULL. If AGG_REPS is not NULL, KNOWN_AGGS is ignored. */
1836 static tree
1837 ipa_get_indirect_edge_target_1 (struct cgraph_edge *ie,
1838 vec<tree> known_csts,
1839 vec<ipa_polymorphic_call_context> known_contexts,
1840 vec<ipa_agg_jump_function_p> known_aggs,
1841 struct ipa_agg_replacement_value *agg_reps,
1842 bool *speculative)
1844 int param_index = ie->indirect_info->param_index;
1845 HOST_WIDE_INT anc_offset;
1846 tree t;
1847 tree target = NULL;
1849 *speculative = false;
1851 if (param_index == -1
1852 || known_csts.length () <= (unsigned int) param_index)
1853 return NULL_TREE;
1855 if (!ie->indirect_info->polymorphic)
1857 tree t;
1859 if (ie->indirect_info->agg_contents)
1861 if (agg_reps)
1863 t = NULL;
1864 while (agg_reps)
1866 if (agg_reps->index == param_index
1867 && agg_reps->offset == ie->indirect_info->offset
1868 && agg_reps->by_ref == ie->indirect_info->by_ref)
1870 t = agg_reps->value;
1871 break;
1873 agg_reps = agg_reps->next;
1876 else if (known_aggs.length () > (unsigned int) param_index)
1878 struct ipa_agg_jump_function *agg;
1879 agg = known_aggs[param_index];
1880 t = ipa_find_agg_cst_for_param (agg, ie->indirect_info->offset,
1881 ie->indirect_info->by_ref);
1883 else
1884 t = NULL;
1886 else
1887 t = known_csts[param_index];
1889 if (t &&
1890 TREE_CODE (t) == ADDR_EXPR
1891 && TREE_CODE (TREE_OPERAND (t, 0)) == FUNCTION_DECL)
1892 return TREE_OPERAND (t, 0);
1893 else
1894 return NULL_TREE;
1897 if (!opt_for_fn (ie->caller->decl, flag_devirtualize))
1898 return NULL_TREE;
1900 gcc_assert (!ie->indirect_info->agg_contents);
1901 anc_offset = ie->indirect_info->offset;
1903 t = NULL;
1905 /* Try to work out value of virtual table pointer value in replacemnets. */
1906 if (!t && agg_reps && !ie->indirect_info->by_ref)
1908 while (agg_reps)
1910 if (agg_reps->index == param_index
1911 && agg_reps->offset == ie->indirect_info->offset
1912 && agg_reps->by_ref)
1914 t = agg_reps->value;
1915 break;
1917 agg_reps = agg_reps->next;
1921 /* Try to work out value of virtual table pointer value in known
1922 aggregate values. */
1923 if (!t && known_aggs.length () > (unsigned int) param_index
1924 && !ie->indirect_info->by_ref)
1926 struct ipa_agg_jump_function *agg;
1927 agg = known_aggs[param_index];
1928 t = ipa_find_agg_cst_for_param (agg, ie->indirect_info->offset,
1929 true);
1932 /* If we found the virtual table pointer, lookup the target. */
1933 if (t)
1935 tree vtable;
1936 unsigned HOST_WIDE_INT offset;
1937 if (vtable_pointer_value_to_vtable (t, &vtable, &offset))
1939 target = gimple_get_virt_method_for_vtable (ie->indirect_info->otr_token,
1940 vtable, offset);
1941 if (target)
1943 if ((TREE_CODE (TREE_TYPE (target)) == FUNCTION_TYPE
1944 && DECL_FUNCTION_CODE (target) == BUILT_IN_UNREACHABLE)
1945 || !possible_polymorphic_call_target_p
1946 (ie, cgraph_node::get (target)))
1947 target = ipa_impossible_devirt_target (ie, target);
1948 *speculative = ie->indirect_info->vptr_changed;
1949 if (!*speculative)
1950 return target;
1955 /* Do we know the constant value of pointer? */
1956 if (!t)
1957 t = known_csts[param_index];
1959 gcc_checking_assert (!t || TREE_CODE (t) != TREE_BINFO);
1961 ipa_polymorphic_call_context context;
1962 if (known_contexts.length () > (unsigned int) param_index)
1964 context = known_contexts[param_index];
1965 context.offset_by (anc_offset);
1966 if (ie->indirect_info->vptr_changed)
1967 context.possible_dynamic_type_change (ie->in_polymorphic_cdtor,
1968 ie->indirect_info->otr_type);
1969 if (t)
1971 ipa_polymorphic_call_context ctx2 = ipa_polymorphic_call_context
1972 (t, ie->indirect_info->otr_type, anc_offset);
1973 if (!ctx2.useless_p ())
1974 context.combine_with (ctx2, ie->indirect_info->otr_type);
1977 else if (t)
1978 context = ipa_polymorphic_call_context (t, ie->indirect_info->otr_type,
1979 anc_offset);
1980 else
1981 return NULL_TREE;
1983 vec <cgraph_node *>targets;
1984 bool final;
1986 targets = possible_polymorphic_call_targets
1987 (ie->indirect_info->otr_type,
1988 ie->indirect_info->otr_token,
1989 context, &final);
1990 if (!final || targets.length () > 1)
1992 struct cgraph_node *node;
1993 if (*speculative)
1994 return target;
1995 if (!opt_for_fn (ie->caller->decl, flag_devirtualize_speculatively)
1996 || ie->speculative || !ie->maybe_hot_p ())
1997 return NULL;
1998 node = try_speculative_devirtualization (ie->indirect_info->otr_type,
1999 ie->indirect_info->otr_token,
2000 context);
2001 if (node)
2003 *speculative = true;
2004 target = node->decl;
2006 else
2007 return NULL;
2009 else
2011 *speculative = false;
2012 if (targets.length () == 1)
2013 target = targets[0]->decl;
2014 else
2015 target = ipa_impossible_devirt_target (ie, NULL_TREE);
2018 if (target && !possible_polymorphic_call_target_p (ie,
2019 cgraph_node::get (target)))
2020 target = ipa_impossible_devirt_target (ie, target);
2022 return target;
2026 /* If an indirect edge IE can be turned into a direct one based on KNOWN_CSTS,
2027 KNOWN_CONTEXTS (which can be vNULL) or KNOWN_AGGS (which also can be vNULL)
2028 return the destination. */
2030 tree
2031 ipa_get_indirect_edge_target (struct cgraph_edge *ie,
2032 vec<tree> known_csts,
2033 vec<ipa_polymorphic_call_context> known_contexts,
2034 vec<ipa_agg_jump_function_p> known_aggs,
2035 bool *speculative)
2037 return ipa_get_indirect_edge_target_1 (ie, known_csts, known_contexts,
2038 known_aggs, NULL, speculative);
2041 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
2042 and KNOWN_CONTEXTS. */
2044 static int
2045 devirtualization_time_bonus (struct cgraph_node *node,
2046 vec<tree> known_csts,
2047 vec<ipa_polymorphic_call_context> known_contexts,
2048 vec<ipa_agg_jump_function_p> known_aggs)
2050 struct cgraph_edge *ie;
2051 int res = 0;
2053 for (ie = node->indirect_calls; ie; ie = ie->next_callee)
2055 struct cgraph_node *callee;
2056 struct inline_summary *isummary;
2057 enum availability avail;
2058 tree target;
2059 bool speculative;
2061 target = ipa_get_indirect_edge_target (ie, known_csts, known_contexts,
2062 known_aggs, &speculative);
2063 if (!target)
2064 continue;
2066 /* Only bare minimum benefit for clearly un-inlineable targets. */
2067 res += 1;
2068 callee = cgraph_node::get (target);
2069 if (!callee || !callee->definition)
2070 continue;
2071 callee = callee->function_symbol (&avail);
2072 if (avail < AVAIL_AVAILABLE)
2073 continue;
2074 isummary = inline_summaries->get (callee);
2075 if (!isummary->inlinable)
2076 continue;
2078 /* FIXME: The values below need re-considering and perhaps also
2079 integrating into the cost metrics, at lest in some very basic way. */
2080 if (isummary->size <= MAX_INLINE_INSNS_AUTO / 4)
2081 res += 31 / ((int)speculative + 1);
2082 else if (isummary->size <= MAX_INLINE_INSNS_AUTO / 2)
2083 res += 15 / ((int)speculative + 1);
2084 else if (isummary->size <= MAX_INLINE_INSNS_AUTO
2085 || DECL_DECLARED_INLINE_P (callee->decl))
2086 res += 7 / ((int)speculative + 1);
2089 return res;
2092 /* Return time bonus incurred because of HINTS. */
2094 static int
2095 hint_time_bonus (inline_hints hints)
2097 int result = 0;
2098 if (hints & (INLINE_HINT_loop_iterations | INLINE_HINT_loop_stride))
2099 result += PARAM_VALUE (PARAM_IPA_CP_LOOP_HINT_BONUS);
2100 if (hints & INLINE_HINT_array_index)
2101 result += PARAM_VALUE (PARAM_IPA_CP_ARRAY_INDEX_HINT_BONUS);
2102 return result;
2105 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
2106 and SIZE_COST and with the sum of frequencies of incoming edges to the
2107 potential new clone in FREQUENCIES. */
2109 static bool
2110 good_cloning_opportunity_p (struct cgraph_node *node, int time_benefit,
2111 int freq_sum, gcov_type count_sum, int size_cost)
2113 if (time_benefit == 0
2114 || !opt_for_fn (node->decl, flag_ipa_cp_clone)
2115 || !optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node->decl)))
2116 return false;
2118 gcc_assert (size_cost > 0);
2120 if (max_count)
2122 int factor = (count_sum * 1000) / max_count;
2123 int64_t evaluation = (((int64_t) time_benefit * factor)
2124 / size_cost);
2126 if (dump_file && (dump_flags & TDF_DETAILS))
2127 fprintf (dump_file, " good_cloning_opportunity_p (time: %i, "
2128 "size: %i, count_sum: " HOST_WIDE_INT_PRINT_DEC
2129 ") -> evaluation: " "%"PRId64
2130 ", threshold: %i\n",
2131 time_benefit, size_cost, (HOST_WIDE_INT) count_sum,
2132 evaluation, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD));
2134 return evaluation >= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD);
2136 else
2138 int64_t evaluation = (((int64_t) time_benefit * freq_sum)
2139 / size_cost);
2141 if (dump_file && (dump_flags & TDF_DETAILS))
2142 fprintf (dump_file, " good_cloning_opportunity_p (time: %i, "
2143 "size: %i, freq_sum: %i) -> evaluation: "
2144 "%"PRId64 ", threshold: %i\n",
2145 time_benefit, size_cost, freq_sum, evaluation,
2146 PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD));
2148 return evaluation >= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD);
2152 /* Return all context independent values from aggregate lattices in PLATS in a
2153 vector. Return NULL if there are none. */
2155 static vec<ipa_agg_jf_item, va_gc> *
2156 context_independent_aggregate_values (struct ipcp_param_lattices *plats)
2158 vec<ipa_agg_jf_item, va_gc> *res = NULL;
2160 if (plats->aggs_bottom
2161 || plats->aggs_contain_variable
2162 || plats->aggs_count == 0)
2163 return NULL;
2165 for (struct ipcp_agg_lattice *aglat = plats->aggs;
2166 aglat;
2167 aglat = aglat->next)
2168 if (aglat->is_single_const ())
2170 struct ipa_agg_jf_item item;
2171 item.offset = aglat->offset;
2172 item.value = aglat->values->value;
2173 vec_safe_push (res, item);
2175 return res;
2178 /* Allocate KNOWN_CSTS, KNOWN_CONTEXTS and, if non-NULL, KNOWN_AGGS and
2179 populate them with values of parameters that are known independent of the
2180 context. INFO describes the function. If REMOVABLE_PARAMS_COST is
2181 non-NULL, the movement cost of all removable parameters will be stored in
2182 it. */
2184 static bool
2185 gather_context_independent_values (struct ipa_node_params *info,
2186 vec<tree> *known_csts,
2187 vec<ipa_polymorphic_call_context>
2188 *known_contexts,
2189 vec<ipa_agg_jump_function> *known_aggs,
2190 int *removable_params_cost)
2192 int i, count = ipa_get_param_count (info);
2193 bool ret = false;
2195 known_csts->create (0);
2196 known_contexts->create (0);
2197 known_csts->safe_grow_cleared (count);
2198 known_contexts->safe_grow_cleared (count);
2199 if (known_aggs)
2201 known_aggs->create (0);
2202 known_aggs->safe_grow_cleared (count);
2205 if (removable_params_cost)
2206 *removable_params_cost = 0;
2208 for (i = 0; i < count ; i++)
2210 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
2211 ipcp_lattice<tree> *lat = &plats->itself;
2213 if (lat->is_single_const ())
2215 ipcp_value<tree> *val = lat->values;
2216 gcc_checking_assert (TREE_CODE (val->value) != TREE_BINFO);
2217 (*known_csts)[i] = val->value;
2218 if (removable_params_cost)
2219 *removable_params_cost
2220 += estimate_move_cost (TREE_TYPE (val->value), false);
2221 ret = true;
2223 else if (removable_params_cost
2224 && !ipa_is_param_used (info, i))
2225 *removable_params_cost
2226 += ipa_get_param_move_cost (info, i);
2228 ipcp_lattice<ipa_polymorphic_call_context> *ctxlat = &plats->ctxlat;
2229 if (ctxlat->is_single_const ())
2231 (*known_contexts)[i] = ctxlat->values->value;
2232 ret = true;
2235 if (known_aggs)
2237 vec<ipa_agg_jf_item, va_gc> *agg_items;
2238 struct ipa_agg_jump_function *ajf;
2240 agg_items = context_independent_aggregate_values (plats);
2241 ajf = &(*known_aggs)[i];
2242 ajf->items = agg_items;
2243 ajf->by_ref = plats->aggs_by_ref;
2244 ret |= agg_items != NULL;
2248 return ret;
2251 /* The current interface in ipa-inline-analysis requires a pointer vector.
2252 Create it.
2254 FIXME: That interface should be re-worked, this is slightly silly. Still,
2255 I'd like to discuss how to change it first and this demonstrates the
2256 issue. */
2258 static vec<ipa_agg_jump_function_p>
2259 agg_jmp_p_vec_for_t_vec (vec<ipa_agg_jump_function> known_aggs)
2261 vec<ipa_agg_jump_function_p> ret;
2262 struct ipa_agg_jump_function *ajf;
2263 int i;
2265 ret.create (known_aggs.length ());
2266 FOR_EACH_VEC_ELT (known_aggs, i, ajf)
2267 ret.quick_push (ajf);
2268 return ret;
2271 /* Perform time and size measurement of NODE with the context given in
2272 KNOWN_CSTS, KNOWN_CONTEXTS and KNOWN_AGGS, calculate the benefit and cost
2273 given BASE_TIME of the node without specialization, REMOVABLE_PARAMS_COST of
2274 all context-independent removable parameters and EST_MOVE_COST of estimated
2275 movement of the considered parameter and store it into VAL. */
2277 static void
2278 perform_estimation_of_a_value (cgraph_node *node, vec<tree> known_csts,
2279 vec<ipa_polymorphic_call_context> known_contexts,
2280 vec<ipa_agg_jump_function_p> known_aggs_ptrs,
2281 int base_time, int removable_params_cost,
2282 int est_move_cost, ipcp_value_base *val)
2284 int time, size, time_benefit;
2285 inline_hints hints;
2287 estimate_ipcp_clone_size_and_time (node, known_csts, known_contexts,
2288 known_aggs_ptrs, &size, &time,
2289 &hints);
2290 time_benefit = base_time - time
2291 + devirtualization_time_bonus (node, known_csts, known_contexts,
2292 known_aggs_ptrs)
2293 + hint_time_bonus (hints)
2294 + removable_params_cost + est_move_cost;
2296 gcc_checking_assert (size >=0);
2297 /* The inliner-heuristics based estimates may think that in certain
2298 contexts some functions do not have any size at all but we want
2299 all specializations to have at least a tiny cost, not least not to
2300 divide by zero. */
2301 if (size == 0)
2302 size = 1;
2304 val->local_time_benefit = time_benefit;
2305 val->local_size_cost = size;
2308 /* Iterate over known values of parameters of NODE and estimate the local
2309 effects in terms of time and size they have. */
2311 static void
2312 estimate_local_effects (struct cgraph_node *node)
2314 struct ipa_node_params *info = IPA_NODE_REF (node);
2315 int i, count = ipa_get_param_count (info);
2316 vec<tree> known_csts;
2317 vec<ipa_polymorphic_call_context> known_contexts;
2318 vec<ipa_agg_jump_function> known_aggs;
2319 vec<ipa_agg_jump_function_p> known_aggs_ptrs;
2320 bool always_const;
2321 int base_time = inline_summaries->get (node)->time;
2322 int removable_params_cost;
2324 if (!count || !ipcp_versionable_function_p (node))
2325 return;
2327 if (dump_file && (dump_flags & TDF_DETAILS))
2328 fprintf (dump_file, "\nEstimating effects for %s/%i, base_time: %i.\n",
2329 node->name (), node->order, base_time);
2331 always_const = gather_context_independent_values (info, &known_csts,
2332 &known_contexts, &known_aggs,
2333 &removable_params_cost);
2334 known_aggs_ptrs = agg_jmp_p_vec_for_t_vec (known_aggs);
2335 if (always_const)
2337 struct caller_statistics stats;
2338 inline_hints hints;
2339 int time, size;
2341 init_caller_stats (&stats);
2342 node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats,
2343 false);
2344 estimate_ipcp_clone_size_and_time (node, known_csts, known_contexts,
2345 known_aggs_ptrs, &size, &time, &hints);
2346 time -= devirtualization_time_bonus (node, known_csts, known_contexts,
2347 known_aggs_ptrs);
2348 time -= hint_time_bonus (hints);
2349 time -= removable_params_cost;
2350 size -= stats.n_calls * removable_params_cost;
2352 if (dump_file)
2353 fprintf (dump_file, " - context independent values, size: %i, "
2354 "time_benefit: %i\n", size, base_time - time);
2356 if (size <= 0
2357 || node->will_be_removed_from_program_if_no_direct_calls_p ())
2359 info->do_clone_for_all_contexts = true;
2360 base_time = time;
2362 if (dump_file)
2363 fprintf (dump_file, " Decided to specialize for all "
2364 "known contexts, code not going to grow.\n");
2366 else if (good_cloning_opportunity_p (node, base_time - time,
2367 stats.freq_sum, stats.count_sum,
2368 size))
2370 if (size + overall_size <= max_new_size)
2372 info->do_clone_for_all_contexts = true;
2373 base_time = time;
2374 overall_size += size;
2376 if (dump_file)
2377 fprintf (dump_file, " Decided to specialize for all "
2378 "known contexts, growth deemed beneficial.\n");
2380 else if (dump_file && (dump_flags & TDF_DETAILS))
2381 fprintf (dump_file, " Not cloning for all contexts because "
2382 "max_new_size would be reached with %li.\n",
2383 size + overall_size);
2387 for (i = 0; i < count ; i++)
2389 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
2390 ipcp_lattice<tree> *lat = &plats->itself;
2391 ipcp_value<tree> *val;
2393 if (lat->bottom
2394 || !lat->values
2395 || known_csts[i])
2396 continue;
2398 for (val = lat->values; val; val = val->next)
2400 gcc_checking_assert (TREE_CODE (val->value) != TREE_BINFO);
2401 known_csts[i] = val->value;
2403 int emc = estimate_move_cost (TREE_TYPE (val->value), true);
2404 perform_estimation_of_a_value (node, known_csts, known_contexts,
2405 known_aggs_ptrs, base_time,
2406 removable_params_cost, emc, val);
2408 if (dump_file && (dump_flags & TDF_DETAILS))
2410 fprintf (dump_file, " - estimates for value ");
2411 print_ipcp_constant_value (dump_file, val->value);
2412 fprintf (dump_file, " for ");
2413 ipa_dump_param (dump_file, info, i);
2414 fprintf (dump_file, ": time_benefit: %i, size: %i\n",
2415 val->local_time_benefit, val->local_size_cost);
2418 known_csts[i] = NULL_TREE;
2421 for (i = 0; i < count; i++)
2423 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
2425 if (!plats->virt_call)
2426 continue;
2428 ipcp_lattice<ipa_polymorphic_call_context> *ctxlat = &plats->ctxlat;
2429 ipcp_value<ipa_polymorphic_call_context> *val;
2431 if (ctxlat->bottom
2432 || !ctxlat->values
2433 || !known_contexts[i].useless_p ())
2434 continue;
2436 for (val = ctxlat->values; val; val = val->next)
2438 known_contexts[i] = val->value;
2439 perform_estimation_of_a_value (node, known_csts, known_contexts,
2440 known_aggs_ptrs, base_time,
2441 removable_params_cost, 0, val);
2443 if (dump_file && (dump_flags & TDF_DETAILS))
2445 fprintf (dump_file, " - estimates for polymorphic context ");
2446 print_ipcp_constant_value (dump_file, val->value);
2447 fprintf (dump_file, " for ");
2448 ipa_dump_param (dump_file, info, i);
2449 fprintf (dump_file, ": time_benefit: %i, size: %i\n",
2450 val->local_time_benefit, val->local_size_cost);
2453 known_contexts[i] = ipa_polymorphic_call_context ();
2456 for (i = 0; i < count ; i++)
2458 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
2459 struct ipa_agg_jump_function *ajf;
2460 struct ipcp_agg_lattice *aglat;
2462 if (plats->aggs_bottom || !plats->aggs)
2463 continue;
2465 ajf = &known_aggs[i];
2466 for (aglat = plats->aggs; aglat; aglat = aglat->next)
2468 ipcp_value<tree> *val;
2469 if (aglat->bottom || !aglat->values
2470 /* If the following is true, the one value is in known_aggs. */
2471 || (!plats->aggs_contain_variable
2472 && aglat->is_single_const ()))
2473 continue;
2475 for (val = aglat->values; val; val = val->next)
2477 struct ipa_agg_jf_item item;
2479 item.offset = aglat->offset;
2480 item.value = val->value;
2481 vec_safe_push (ajf->items, item);
2483 perform_estimation_of_a_value (node, known_csts, known_contexts,
2484 known_aggs_ptrs, base_time,
2485 removable_params_cost, 0, val);
2487 if (dump_file && (dump_flags & TDF_DETAILS))
2489 fprintf (dump_file, " - estimates for value ");
2490 print_ipcp_constant_value (dump_file, val->value);
2491 fprintf (dump_file, " for ");
2492 ipa_dump_param (dump_file, info, i);
2493 fprintf (dump_file, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
2494 "]: time_benefit: %i, size: %i\n",
2495 plats->aggs_by_ref ? "ref " : "",
2496 aglat->offset,
2497 val->local_time_benefit, val->local_size_cost);
2500 ajf->items->pop ();
2505 for (i = 0; i < count ; i++)
2506 vec_free (known_aggs[i].items);
2508 known_csts.release ();
2509 known_contexts.release ();
2510 known_aggs.release ();
2511 known_aggs_ptrs.release ();
2515 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
2516 topological sort of values. */
2518 template <typename valtype>
2519 void
2520 value_topo_info<valtype>::add_val (ipcp_value<valtype> *cur_val)
2522 ipcp_value_source<valtype> *src;
2524 if (cur_val->dfs)
2525 return;
2527 dfs_counter++;
2528 cur_val->dfs = dfs_counter;
2529 cur_val->low_link = dfs_counter;
2531 cur_val->topo_next = stack;
2532 stack = cur_val;
2533 cur_val->on_stack = true;
2535 for (src = cur_val->sources; src; src = src->next)
2536 if (src->val)
2538 if (src->val->dfs == 0)
2540 add_val (src->val);
2541 if (src->val->low_link < cur_val->low_link)
2542 cur_val->low_link = src->val->low_link;
2544 else if (src->val->on_stack
2545 && src->val->dfs < cur_val->low_link)
2546 cur_val->low_link = src->val->dfs;
2549 if (cur_val->dfs == cur_val->low_link)
2551 ipcp_value<valtype> *v, *scc_list = NULL;
2555 v = stack;
2556 stack = v->topo_next;
2557 v->on_stack = false;
2559 v->scc_next = scc_list;
2560 scc_list = v;
2562 while (v != cur_val);
2564 cur_val->topo_next = values_topo;
2565 values_topo = cur_val;
2569 /* Add all values in lattices associated with NODE to the topological sort if
2570 they are not there yet. */
2572 static void
2573 add_all_node_vals_to_toposort (cgraph_node *node, ipa_topo_info *topo)
2575 struct ipa_node_params *info = IPA_NODE_REF (node);
2576 int i, count = ipa_get_param_count (info);
2578 for (i = 0; i < count ; i++)
2580 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
2581 ipcp_lattice<tree> *lat = &plats->itself;
2582 struct ipcp_agg_lattice *aglat;
2584 if (!lat->bottom)
2586 ipcp_value<tree> *val;
2587 for (val = lat->values; val; val = val->next)
2588 topo->constants.add_val (val);
2591 if (!plats->aggs_bottom)
2592 for (aglat = plats->aggs; aglat; aglat = aglat->next)
2593 if (!aglat->bottom)
2595 ipcp_value<tree> *val;
2596 for (val = aglat->values; val; val = val->next)
2597 topo->constants.add_val (val);
2600 ipcp_lattice<ipa_polymorphic_call_context> *ctxlat = &plats->ctxlat;
2601 if (!ctxlat->bottom)
2603 ipcp_value<ipa_polymorphic_call_context> *ctxval;
2604 for (ctxval = ctxlat->values; ctxval; ctxval = ctxval->next)
2605 topo->contexts.add_val (ctxval);
2610 /* One pass of constants propagation along the call graph edges, from callers
2611 to callees (requires topological ordering in TOPO), iterate over strongly
2612 connected components. */
2614 static void
2615 propagate_constants_topo (struct ipa_topo_info *topo)
2617 int i;
2619 for (i = topo->nnodes - 1; i >= 0; i--)
2621 unsigned j;
2622 struct cgraph_node *v, *node = topo->order[i];
2623 vec<cgraph_node *> cycle_nodes = ipa_get_nodes_in_cycle (node);
2625 /* First, iteratively propagate within the strongly connected component
2626 until all lattices stabilize. */
2627 FOR_EACH_VEC_ELT (cycle_nodes, j, v)
2628 if (v->has_gimple_body_p ())
2629 push_node_to_stack (topo, v);
2631 v = pop_node_from_stack (topo);
2632 while (v)
2634 struct cgraph_edge *cs;
2636 for (cs = v->callees; cs; cs = cs->next_callee)
2637 if (ipa_edge_within_scc (cs)
2638 && propagate_constants_accross_call (cs))
2639 push_node_to_stack (topo, cs->callee);
2640 v = pop_node_from_stack (topo);
2643 /* Afterwards, propagate along edges leading out of the SCC, calculates
2644 the local effects of the discovered constants and all valid values to
2645 their topological sort. */
2646 FOR_EACH_VEC_ELT (cycle_nodes, j, v)
2647 if (v->has_gimple_body_p ())
2649 struct cgraph_edge *cs;
2651 estimate_local_effects (v);
2652 add_all_node_vals_to_toposort (v, topo);
2653 for (cs = v->callees; cs; cs = cs->next_callee)
2654 if (!ipa_edge_within_scc (cs))
2655 propagate_constants_accross_call (cs);
2657 cycle_nodes.release ();
2662 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
2663 the bigger one if otherwise. */
2665 static int
2666 safe_add (int a, int b)
2668 if (a > INT_MAX/2 || b > INT_MAX/2)
2669 return a > b ? a : b;
2670 else
2671 return a + b;
2675 /* Propagate the estimated effects of individual values along the topological
2676 from the dependent values to those they depend on. */
2678 template <typename valtype>
2679 void
2680 value_topo_info<valtype>::propagate_effects ()
2682 ipcp_value<valtype> *base;
2684 for (base = values_topo; base; base = base->topo_next)
2686 ipcp_value_source<valtype> *src;
2687 ipcp_value<valtype> *val;
2688 int time = 0, size = 0;
2690 for (val = base; val; val = val->scc_next)
2692 time = safe_add (time,
2693 val->local_time_benefit + val->prop_time_benefit);
2694 size = safe_add (size, val->local_size_cost + val->prop_size_cost);
2697 for (val = base; val; val = val->scc_next)
2698 for (src = val->sources; src; src = src->next)
2699 if (src->val
2700 && src->cs->maybe_hot_p ())
2702 src->val->prop_time_benefit = safe_add (time,
2703 src->val->prop_time_benefit);
2704 src->val->prop_size_cost = safe_add (size,
2705 src->val->prop_size_cost);
2711 /* Propagate constants, polymorphic contexts and their effects from the
2712 summaries interprocedurally. */
2714 static void
2715 ipcp_propagate_stage (struct ipa_topo_info *topo)
2717 struct cgraph_node *node;
2719 if (dump_file)
2720 fprintf (dump_file, "\n Propagating constants:\n\n");
2722 if (in_lto_p)
2723 ipa_update_after_lto_read ();
2726 FOR_EACH_DEFINED_FUNCTION (node)
2728 struct ipa_node_params *info = IPA_NODE_REF (node);
2730 determine_versionability (node);
2731 if (node->has_gimple_body_p ())
2733 info->lattices = XCNEWVEC (struct ipcp_param_lattices,
2734 ipa_get_param_count (info));
2735 initialize_node_lattices (node);
2737 if (node->definition && !node->alias)
2738 overall_size += inline_summaries->get (node)->self_size;
2739 if (node->count > max_count)
2740 max_count = node->count;
2743 max_new_size = overall_size;
2744 if (max_new_size < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
2745 max_new_size = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
2746 max_new_size += max_new_size * PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH) / 100 + 1;
2748 if (dump_file)
2749 fprintf (dump_file, "\noverall_size: %li, max_new_size: %li\n",
2750 overall_size, max_new_size);
2752 propagate_constants_topo (topo);
2753 #ifdef ENABLE_CHECKING
2754 ipcp_verify_propagated_values ();
2755 #endif
2756 topo->constants.propagate_effects ();
2757 topo->contexts.propagate_effects ();
2759 if (dump_file)
2761 fprintf (dump_file, "\nIPA lattices after all propagation:\n");
2762 print_all_lattices (dump_file, (dump_flags & TDF_DETAILS), true);
2766 /* Discover newly direct outgoing edges from NODE which is a new clone with
2767 known KNOWN_CSTS and make them direct. */
2769 static void
2770 ipcp_discover_new_direct_edges (struct cgraph_node *node,
2771 vec<tree> known_csts,
2772 vec<ipa_polymorphic_call_context>
2773 known_contexts,
2774 struct ipa_agg_replacement_value *aggvals)
2776 struct cgraph_edge *ie, *next_ie;
2777 bool found = false;
2779 for (ie = node->indirect_calls; ie; ie = next_ie)
2781 tree target;
2782 bool speculative;
2784 next_ie = ie->next_callee;
2785 target = ipa_get_indirect_edge_target_1 (ie, known_csts, known_contexts,
2786 vNULL, aggvals, &speculative);
2787 if (target)
2789 bool agg_contents = ie->indirect_info->agg_contents;
2790 bool polymorphic = ie->indirect_info->polymorphic;
2791 int param_index = ie->indirect_info->param_index;
2792 struct cgraph_edge *cs = ipa_make_edge_direct_to_target (ie, target,
2793 speculative);
2794 found = true;
2796 if (cs && !agg_contents && !polymorphic)
2798 struct ipa_node_params *info = IPA_NODE_REF (node);
2799 int c = ipa_get_controlled_uses (info, param_index);
2800 if (c != IPA_UNDESCRIBED_USE)
2802 struct ipa_ref *to_del;
2804 c--;
2805 ipa_set_controlled_uses (info, param_index, c);
2806 if (dump_file && (dump_flags & TDF_DETAILS))
2807 fprintf (dump_file, " controlled uses count of param "
2808 "%i bumped down to %i\n", param_index, c);
2809 if (c == 0
2810 && (to_del = node->find_reference (cs->callee, NULL, 0)))
2812 if (dump_file && (dump_flags & TDF_DETAILS))
2813 fprintf (dump_file, " and even removing its "
2814 "cloning-created reference\n");
2815 to_del->remove_reference ();
2821 /* Turning calls to direct calls will improve overall summary. */
2822 if (found)
2823 inline_update_overall_summary (node);
2826 /* Vector of pointers which for linked lists of clones of an original crgaph
2827 edge. */
2829 static vec<cgraph_edge *> next_edge_clone;
2830 static vec<cgraph_edge *> prev_edge_clone;
2832 static inline void
2833 grow_edge_clone_vectors (void)
2835 if (next_edge_clone.length ()
2836 <= (unsigned) symtab->edges_max_uid)
2837 next_edge_clone.safe_grow_cleared (symtab->edges_max_uid + 1);
2838 if (prev_edge_clone.length ()
2839 <= (unsigned) symtab->edges_max_uid)
2840 prev_edge_clone.safe_grow_cleared (symtab->edges_max_uid + 1);
2843 /* Edge duplication hook to grow the appropriate linked list in
2844 next_edge_clone. */
2846 static void
2847 ipcp_edge_duplication_hook (struct cgraph_edge *src, struct cgraph_edge *dst,
2848 void *)
2850 grow_edge_clone_vectors ();
2852 struct cgraph_edge *old_next = next_edge_clone[src->uid];
2853 if (old_next)
2854 prev_edge_clone[old_next->uid] = dst;
2855 prev_edge_clone[dst->uid] = src;
2857 next_edge_clone[dst->uid] = old_next;
2858 next_edge_clone[src->uid] = dst;
2861 /* Hook that is called by cgraph.c when an edge is removed. */
2863 static void
2864 ipcp_edge_removal_hook (struct cgraph_edge *cs, void *)
2866 grow_edge_clone_vectors ();
2868 struct cgraph_edge *prev = prev_edge_clone[cs->uid];
2869 struct cgraph_edge *next = next_edge_clone[cs->uid];
2870 if (prev)
2871 next_edge_clone[prev->uid] = next;
2872 if (next)
2873 prev_edge_clone[next->uid] = prev;
2876 /* See if NODE is a clone with a known aggregate value at a given OFFSET of a
2877 parameter with the given INDEX. */
2879 static tree
2880 get_clone_agg_value (struct cgraph_node *node, HOST_WIDE_INT offset,
2881 int index)
2883 struct ipa_agg_replacement_value *aggval;
2885 aggval = ipa_get_agg_replacements_for_node (node);
2886 while (aggval)
2888 if (aggval->offset == offset
2889 && aggval->index == index)
2890 return aggval->value;
2891 aggval = aggval->next;
2893 return NULL_TREE;
2896 /* Return true is NODE is DEST or its clone for all contexts. */
2898 static bool
2899 same_node_or_its_all_contexts_clone_p (cgraph_node *node, cgraph_node *dest)
2901 if (node == dest)
2902 return true;
2904 struct ipa_node_params *info = IPA_NODE_REF (node);
2905 return info->is_all_contexts_clone && info->ipcp_orig_node == dest;
2908 /* Return true if edge CS does bring about the value described by SRC to node
2909 DEST or its clone for all contexts. */
2911 static bool
2912 cgraph_edge_brings_value_p (cgraph_edge *cs, ipcp_value_source<tree> *src,
2913 cgraph_node *dest)
2915 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
2916 enum availability availability;
2917 cgraph_node *real_dest = cs->callee->function_symbol (&availability);
2919 if (!same_node_or_its_all_contexts_clone_p (real_dest, dest)
2920 || availability <= AVAIL_INTERPOSABLE
2921 || caller_info->node_dead)
2922 return false;
2923 if (!src->val)
2924 return true;
2926 if (caller_info->ipcp_orig_node)
2928 tree t;
2929 if (src->offset == -1)
2930 t = caller_info->known_csts[src->index];
2931 else
2932 t = get_clone_agg_value (cs->caller, src->offset, src->index);
2933 return (t != NULL_TREE
2934 && values_equal_for_ipcp_p (src->val->value, t));
2936 else
2938 struct ipcp_agg_lattice *aglat;
2939 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (caller_info,
2940 src->index);
2941 if (src->offset == -1)
2942 return (plats->itself.is_single_const ()
2943 && values_equal_for_ipcp_p (src->val->value,
2944 plats->itself.values->value));
2945 else
2947 if (plats->aggs_bottom || plats->aggs_contain_variable)
2948 return false;
2949 for (aglat = plats->aggs; aglat; aglat = aglat->next)
2950 if (aglat->offset == src->offset)
2951 return (aglat->is_single_const ()
2952 && values_equal_for_ipcp_p (src->val->value,
2953 aglat->values->value));
2955 return false;
2959 /* Return true if edge CS does bring about the value described by SRC to node
2960 DEST or its clone for all contexts. */
2962 static bool
2963 cgraph_edge_brings_value_p (cgraph_edge *cs,
2964 ipcp_value_source<ipa_polymorphic_call_context> *src,
2965 cgraph_node *dest)
2967 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
2968 cgraph_node *real_dest = cs->callee->function_symbol ();
2970 if (!same_node_or_its_all_contexts_clone_p (real_dest, dest)
2971 || caller_info->node_dead)
2972 return false;
2973 if (!src->val)
2974 return true;
2976 if (caller_info->ipcp_orig_node)
2977 return (caller_info->known_contexts.length () > (unsigned) src->index)
2978 && values_equal_for_ipcp_p (src->val->value,
2979 caller_info->known_contexts[src->index]);
2981 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (caller_info,
2982 src->index);
2983 return plats->ctxlat.is_single_const ()
2984 && values_equal_for_ipcp_p (src->val->value,
2985 plats->ctxlat.values->value);
2988 /* Get the next clone in the linked list of clones of an edge. */
2990 static inline struct cgraph_edge *
2991 get_next_cgraph_edge_clone (struct cgraph_edge *cs)
2993 return next_edge_clone[cs->uid];
2996 /* Given VAL that is intended for DEST, iterate over all its sources and if
2997 they still hold, add their edge frequency and their number into *FREQUENCY
2998 and *CALLER_COUNT respectively. */
3000 template <typename valtype>
3001 static bool
3002 get_info_about_necessary_edges (ipcp_value<valtype> *val, cgraph_node *dest,
3003 int *freq_sum,
3004 gcov_type *count_sum, int *caller_count)
3006 ipcp_value_source<valtype> *src;
3007 int freq = 0, count = 0;
3008 gcov_type cnt = 0;
3009 bool hot = false;
3011 for (src = val->sources; src; src = src->next)
3013 struct cgraph_edge *cs = src->cs;
3014 while (cs)
3016 if (cgraph_edge_brings_value_p (cs, src, dest))
3018 count++;
3019 freq += cs->frequency;
3020 cnt += cs->count;
3021 hot |= cs->maybe_hot_p ();
3023 cs = get_next_cgraph_edge_clone (cs);
3027 *freq_sum = freq;
3028 *count_sum = cnt;
3029 *caller_count = count;
3030 return hot;
3033 /* Return a vector of incoming edges that do bring value VAL to node DEST. It
3034 is assumed their number is known and equal to CALLER_COUNT. */
3036 template <typename valtype>
3037 static vec<cgraph_edge *>
3038 gather_edges_for_value (ipcp_value<valtype> *val, cgraph_node *dest,
3039 int caller_count)
3041 ipcp_value_source<valtype> *src;
3042 vec<cgraph_edge *> ret;
3044 ret.create (caller_count);
3045 for (src = val->sources; src; src = src->next)
3047 struct cgraph_edge *cs = src->cs;
3048 while (cs)
3050 if (cgraph_edge_brings_value_p (cs, src, dest))
3051 ret.quick_push (cs);
3052 cs = get_next_cgraph_edge_clone (cs);
3056 return ret;
3059 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
3060 Return it or NULL if for some reason it cannot be created. */
3062 static struct ipa_replace_map *
3063 get_replacement_map (struct ipa_node_params *info, tree value, int parm_num)
3065 struct ipa_replace_map *replace_map;
3068 replace_map = ggc_alloc<ipa_replace_map> ();
3069 if (dump_file)
3071 fprintf (dump_file, " replacing ");
3072 ipa_dump_param (dump_file, info, parm_num);
3074 fprintf (dump_file, " with const ");
3075 print_generic_expr (dump_file, value, 0);
3076 fprintf (dump_file, "\n");
3078 replace_map->old_tree = NULL;
3079 replace_map->parm_num = parm_num;
3080 replace_map->new_tree = value;
3081 replace_map->replace_p = true;
3082 replace_map->ref_p = false;
3084 return replace_map;
3087 /* Dump new profiling counts */
3089 static void
3090 dump_profile_updates (struct cgraph_node *orig_node,
3091 struct cgraph_node *new_node)
3093 struct cgraph_edge *cs;
3095 fprintf (dump_file, " setting count of the specialized node to "
3096 HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) new_node->count);
3097 for (cs = new_node->callees; cs ; cs = cs->next_callee)
3098 fprintf (dump_file, " edge to %s has count "
3099 HOST_WIDE_INT_PRINT_DEC "\n",
3100 cs->callee->name (), (HOST_WIDE_INT) cs->count);
3102 fprintf (dump_file, " setting count of the original node to "
3103 HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) orig_node->count);
3104 for (cs = orig_node->callees; cs ; cs = cs->next_callee)
3105 fprintf (dump_file, " edge to %s is left with "
3106 HOST_WIDE_INT_PRINT_DEC "\n",
3107 cs->callee->name (), (HOST_WIDE_INT) cs->count);
3110 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
3111 their profile information to reflect this. */
3113 static void
3114 update_profiling_info (struct cgraph_node *orig_node,
3115 struct cgraph_node *new_node)
3117 struct cgraph_edge *cs;
3118 struct caller_statistics stats;
3119 gcov_type new_sum, orig_sum;
3120 gcov_type remainder, orig_node_count = orig_node->count;
3122 if (orig_node_count == 0)
3123 return;
3125 init_caller_stats (&stats);
3126 orig_node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats,
3127 false);
3128 orig_sum = stats.count_sum;
3129 init_caller_stats (&stats);
3130 new_node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats,
3131 false);
3132 new_sum = stats.count_sum;
3134 if (orig_node_count < orig_sum + new_sum)
3136 if (dump_file)
3137 fprintf (dump_file, " Problem: node %s/%i has too low count "
3138 HOST_WIDE_INT_PRINT_DEC " while the sum of incoming "
3139 "counts is " HOST_WIDE_INT_PRINT_DEC "\n",
3140 orig_node->name (), orig_node->order,
3141 (HOST_WIDE_INT) orig_node_count,
3142 (HOST_WIDE_INT) (orig_sum + new_sum));
3144 orig_node_count = (orig_sum + new_sum) * 12 / 10;
3145 if (dump_file)
3146 fprintf (dump_file, " proceeding by pretending it was "
3147 HOST_WIDE_INT_PRINT_DEC "\n",
3148 (HOST_WIDE_INT) orig_node_count);
3151 new_node->count = new_sum;
3152 remainder = orig_node_count - new_sum;
3153 orig_node->count = remainder;
3155 for (cs = new_node->callees; cs ; cs = cs->next_callee)
3156 if (cs->frequency)
3157 cs->count = apply_probability (cs->count,
3158 GCOV_COMPUTE_SCALE (new_sum,
3159 orig_node_count));
3160 else
3161 cs->count = 0;
3163 for (cs = orig_node->callees; cs ; cs = cs->next_callee)
3164 cs->count = apply_probability (cs->count,
3165 GCOV_COMPUTE_SCALE (remainder,
3166 orig_node_count));
3168 if (dump_file)
3169 dump_profile_updates (orig_node, new_node);
3172 /* Update the respective profile of specialized NEW_NODE and the original
3173 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
3174 have been redirected to the specialized version. */
3176 static void
3177 update_specialized_profile (struct cgraph_node *new_node,
3178 struct cgraph_node *orig_node,
3179 gcov_type redirected_sum)
3181 struct cgraph_edge *cs;
3182 gcov_type new_node_count, orig_node_count = orig_node->count;
3184 if (dump_file)
3185 fprintf (dump_file, " the sum of counts of redirected edges is "
3186 HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) redirected_sum);
3187 if (orig_node_count == 0)
3188 return;
3190 gcc_assert (orig_node_count >= redirected_sum);
3192 new_node_count = new_node->count;
3193 new_node->count += redirected_sum;
3194 orig_node->count -= redirected_sum;
3196 for (cs = new_node->callees; cs ; cs = cs->next_callee)
3197 if (cs->frequency)
3198 cs->count += apply_probability (cs->count,
3199 GCOV_COMPUTE_SCALE (redirected_sum,
3200 new_node_count));
3201 else
3202 cs->count = 0;
3204 for (cs = orig_node->callees; cs ; cs = cs->next_callee)
3206 gcov_type dec = apply_probability (cs->count,
3207 GCOV_COMPUTE_SCALE (redirected_sum,
3208 orig_node_count));
3209 if (dec < cs->count)
3210 cs->count -= dec;
3211 else
3212 cs->count = 0;
3215 if (dump_file)
3216 dump_profile_updates (orig_node, new_node);
3219 /* Create a specialized version of NODE with known constants in KNOWN_CSTS,
3220 known contexts in KNOWN_CONTEXTS and known aggregate values in AGGVALS and
3221 redirect all edges in CALLERS to it. */
3223 static struct cgraph_node *
3224 create_specialized_node (struct cgraph_node *node,
3225 vec<tree> known_csts,
3226 vec<ipa_polymorphic_call_context> known_contexts,
3227 struct ipa_agg_replacement_value *aggvals,
3228 vec<cgraph_edge *> callers)
3230 struct ipa_node_params *new_info, *info = IPA_NODE_REF (node);
3231 vec<ipa_replace_map *, va_gc> *replace_trees = NULL;
3232 struct ipa_agg_replacement_value *av;
3233 struct cgraph_node *new_node;
3234 int i, count = ipa_get_param_count (info);
3235 bitmap args_to_skip;
3237 gcc_assert (!info->ipcp_orig_node);
3239 if (node->local.can_change_signature)
3241 args_to_skip = BITMAP_GGC_ALLOC ();
3242 for (i = 0; i < count; i++)
3244 tree t = known_csts[i];
3246 if (t || !ipa_is_param_used (info, i))
3247 bitmap_set_bit (args_to_skip, i);
3250 else
3252 args_to_skip = NULL;
3253 if (dump_file && (dump_flags & TDF_DETAILS))
3254 fprintf (dump_file, " cannot change function signature\n");
3257 for (i = 0; i < count ; i++)
3259 tree t = known_csts[i];
3260 if (t)
3262 struct ipa_replace_map *replace_map;
3264 gcc_checking_assert (TREE_CODE (t) != TREE_BINFO);
3265 replace_map = get_replacement_map (info, t, i);
3266 if (replace_map)
3267 vec_safe_push (replace_trees, replace_map);
3271 new_node = node->create_virtual_clone (callers, replace_trees,
3272 args_to_skip, "constprop");
3273 ipa_set_node_agg_value_chain (new_node, aggvals);
3274 for (av = aggvals; av; av = av->next)
3275 new_node->maybe_create_reference (av->value, IPA_REF_ADDR, NULL);
3277 if (dump_file && (dump_flags & TDF_DETAILS))
3279 fprintf (dump_file, " the new node is %s/%i.\n",
3280 new_node->name (), new_node->order);
3281 if (known_contexts.exists ())
3283 for (i = 0; i < count ; i++)
3284 if (!known_contexts[i].useless_p ())
3286 fprintf (dump_file, " known ctx %i is ", i);
3287 known_contexts[i].dump (dump_file);
3290 if (aggvals)
3291 ipa_dump_agg_replacement_values (dump_file, aggvals);
3293 ipa_check_create_node_params ();
3294 update_profiling_info (node, new_node);
3295 new_info = IPA_NODE_REF (new_node);
3296 new_info->ipcp_orig_node = node;
3297 new_info->known_csts = known_csts;
3298 new_info->known_contexts = known_contexts;
3300 ipcp_discover_new_direct_edges (new_node, known_csts, known_contexts, aggvals);
3302 callers.release ();
3303 return new_node;
3306 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
3307 KNOWN_CSTS with constants that are also known for all of the CALLERS. */
3309 static void
3310 find_more_scalar_values_for_callers_subset (struct cgraph_node *node,
3311 vec<tree> known_csts,
3312 vec<cgraph_edge *> callers)
3314 struct ipa_node_params *info = IPA_NODE_REF (node);
3315 int i, count = ipa_get_param_count (info);
3317 for (i = 0; i < count ; i++)
3319 struct cgraph_edge *cs;
3320 tree newval = NULL_TREE;
3321 int j;
3322 bool first = true;
3324 if (ipa_get_scalar_lat (info, i)->bottom || known_csts[i])
3325 continue;
3327 FOR_EACH_VEC_ELT (callers, j, cs)
3329 struct ipa_jump_func *jump_func;
3330 tree t;
3332 if (i >= ipa_get_cs_argument_count (IPA_EDGE_REF (cs)))
3334 newval = NULL_TREE;
3335 break;
3337 jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
3338 t = ipa_value_from_jfunc (IPA_NODE_REF (cs->caller), jump_func);
3339 if (!t
3340 || (newval
3341 && !values_equal_for_ipcp_p (t, newval))
3342 || (!first && !newval))
3344 newval = NULL_TREE;
3345 break;
3347 else
3348 newval = t;
3349 first = false;
3352 if (newval)
3354 if (dump_file && (dump_flags & TDF_DETAILS))
3356 fprintf (dump_file, " adding an extra known scalar value ");
3357 print_ipcp_constant_value (dump_file, newval);
3358 fprintf (dump_file, " for ");
3359 ipa_dump_param (dump_file, info, i);
3360 fprintf (dump_file, "\n");
3363 known_csts[i] = newval;
3368 /* Given a NODE and a subset of its CALLERS, try to populate plank slots in
3369 KNOWN_CONTEXTS with polymorphic contexts that are also known for all of the
3370 CALLERS. */
3372 static void
3373 find_more_contexts_for_caller_subset (cgraph_node *node,
3374 vec<ipa_polymorphic_call_context>
3375 *known_contexts,
3376 vec<cgraph_edge *> callers)
3378 ipa_node_params *info = IPA_NODE_REF (node);
3379 int i, count = ipa_get_param_count (info);
3381 for (i = 0; i < count ; i++)
3383 cgraph_edge *cs;
3385 if (ipa_get_poly_ctx_lat (info, i)->bottom
3386 || (known_contexts->exists ()
3387 && !(*known_contexts)[i].useless_p ()))
3388 continue;
3390 ipa_polymorphic_call_context newval;
3391 bool first = true;
3392 int j;
3394 FOR_EACH_VEC_ELT (callers, j, cs)
3396 if (i >= ipa_get_cs_argument_count (IPA_EDGE_REF (cs)))
3397 return;
3398 ipa_jump_func *jfunc = ipa_get_ith_jump_func (IPA_EDGE_REF (cs),
3400 ipa_polymorphic_call_context ctx;
3401 ctx = ipa_context_from_jfunc (IPA_NODE_REF (cs->caller), cs, i,
3402 jfunc);
3403 if (first)
3405 newval = ctx;
3406 first = false;
3408 else
3409 newval.meet_with (ctx);
3410 if (newval.useless_p ())
3411 break;
3414 if (!newval.useless_p ())
3416 if (dump_file && (dump_flags & TDF_DETAILS))
3418 fprintf (dump_file, " adding an extra known polymorphic "
3419 "context ");
3420 print_ipcp_constant_value (dump_file, newval);
3421 fprintf (dump_file, " for ");
3422 ipa_dump_param (dump_file, info, i);
3423 fprintf (dump_file, "\n");
3426 if (!known_contexts->exists ())
3427 known_contexts->safe_grow_cleared (ipa_get_param_count (info));
3428 (*known_contexts)[i] = newval;
3434 /* Go through PLATS and create a vector of values consisting of values and
3435 offsets (minus OFFSET) of lattices that contain only a single value. */
3437 static vec<ipa_agg_jf_item>
3438 copy_plats_to_inter (struct ipcp_param_lattices *plats, HOST_WIDE_INT offset)
3440 vec<ipa_agg_jf_item> res = vNULL;
3442 if (!plats->aggs || plats->aggs_contain_variable || plats->aggs_bottom)
3443 return vNULL;
3445 for (struct ipcp_agg_lattice *aglat = plats->aggs; aglat; aglat = aglat->next)
3446 if (aglat->is_single_const ())
3448 struct ipa_agg_jf_item ti;
3449 ti.offset = aglat->offset - offset;
3450 ti.value = aglat->values->value;
3451 res.safe_push (ti);
3453 return res;
3456 /* Intersect all values in INTER with single value lattices in PLATS (while
3457 subtracting OFFSET). */
3459 static void
3460 intersect_with_plats (struct ipcp_param_lattices *plats,
3461 vec<ipa_agg_jf_item> *inter,
3462 HOST_WIDE_INT offset)
3464 struct ipcp_agg_lattice *aglat;
3465 struct ipa_agg_jf_item *item;
3466 int k;
3468 if (!plats->aggs || plats->aggs_contain_variable || plats->aggs_bottom)
3470 inter->release ();
3471 return;
3474 aglat = plats->aggs;
3475 FOR_EACH_VEC_ELT (*inter, k, item)
3477 bool found = false;
3478 if (!item->value)
3479 continue;
3480 while (aglat)
3482 if (aglat->offset - offset > item->offset)
3483 break;
3484 if (aglat->offset - offset == item->offset)
3486 gcc_checking_assert (item->value);
3487 if (values_equal_for_ipcp_p (item->value, aglat->values->value))
3488 found = true;
3489 break;
3491 aglat = aglat->next;
3493 if (!found)
3494 item->value = NULL_TREE;
3498 /* Copy agggregate replacement values of NODE (which is an IPA-CP clone) to the
3499 vector result while subtracting OFFSET from the individual value offsets. */
3501 static vec<ipa_agg_jf_item>
3502 agg_replacements_to_vector (struct cgraph_node *node, int index,
3503 HOST_WIDE_INT offset)
3505 struct ipa_agg_replacement_value *av;
3506 vec<ipa_agg_jf_item> res = vNULL;
3508 for (av = ipa_get_agg_replacements_for_node (node); av; av = av->next)
3509 if (av->index == index
3510 && (av->offset - offset) >= 0)
3512 struct ipa_agg_jf_item item;
3513 gcc_checking_assert (av->value);
3514 item.offset = av->offset - offset;
3515 item.value = av->value;
3516 res.safe_push (item);
3519 return res;
3522 /* Intersect all values in INTER with those that we have already scheduled to
3523 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
3524 (while subtracting OFFSET). */
3526 static void
3527 intersect_with_agg_replacements (struct cgraph_node *node, int index,
3528 vec<ipa_agg_jf_item> *inter,
3529 HOST_WIDE_INT offset)
3531 struct ipa_agg_replacement_value *srcvals;
3532 struct ipa_agg_jf_item *item;
3533 int i;
3535 srcvals = ipa_get_agg_replacements_for_node (node);
3536 if (!srcvals)
3538 inter->release ();
3539 return;
3542 FOR_EACH_VEC_ELT (*inter, i, item)
3544 struct ipa_agg_replacement_value *av;
3545 bool found = false;
3546 if (!item->value)
3547 continue;
3548 for (av = srcvals; av; av = av->next)
3550 gcc_checking_assert (av->value);
3551 if (av->index == index
3552 && av->offset - offset == item->offset)
3554 if (values_equal_for_ipcp_p (item->value, av->value))
3555 found = true;
3556 break;
3559 if (!found)
3560 item->value = NULL_TREE;
3564 /* Intersect values in INTER with aggregate values that come along edge CS to
3565 parameter number INDEX and return it. If INTER does not actually exist yet,
3566 copy all incoming values to it. If we determine we ended up with no values
3567 whatsoever, return a released vector. */
3569 static vec<ipa_agg_jf_item>
3570 intersect_aggregates_with_edge (struct cgraph_edge *cs, int index,
3571 vec<ipa_agg_jf_item> inter)
3573 struct ipa_jump_func *jfunc;
3574 jfunc = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), index);
3575 if (jfunc->type == IPA_JF_PASS_THROUGH
3576 && ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
3578 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
3579 int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
3581 if (caller_info->ipcp_orig_node)
3583 struct cgraph_node *orig_node = caller_info->ipcp_orig_node;
3584 struct ipcp_param_lattices *orig_plats;
3585 orig_plats = ipa_get_parm_lattices (IPA_NODE_REF (orig_node),
3586 src_idx);
3587 if (agg_pass_through_permissible_p (orig_plats, jfunc))
3589 if (!inter.exists ())
3590 inter = agg_replacements_to_vector (cs->caller, src_idx, 0);
3591 else
3592 intersect_with_agg_replacements (cs->caller, src_idx,
3593 &inter, 0);
3595 else
3597 inter.release ();
3598 return vNULL;
3601 else
3603 struct ipcp_param_lattices *src_plats;
3604 src_plats = ipa_get_parm_lattices (caller_info, src_idx);
3605 if (agg_pass_through_permissible_p (src_plats, jfunc))
3607 /* Currently we do not produce clobber aggregate jump
3608 functions, adjust when we do. */
3609 gcc_checking_assert (!jfunc->agg.items);
3610 if (!inter.exists ())
3611 inter = copy_plats_to_inter (src_plats, 0);
3612 else
3613 intersect_with_plats (src_plats, &inter, 0);
3615 else
3617 inter.release ();
3618 return vNULL;
3622 else if (jfunc->type == IPA_JF_ANCESTOR
3623 && ipa_get_jf_ancestor_agg_preserved (jfunc))
3625 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
3626 int src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
3627 struct ipcp_param_lattices *src_plats;
3628 HOST_WIDE_INT delta = ipa_get_jf_ancestor_offset (jfunc);
3630 if (caller_info->ipcp_orig_node)
3632 if (!inter.exists ())
3633 inter = agg_replacements_to_vector (cs->caller, src_idx, delta);
3634 else
3635 intersect_with_agg_replacements (cs->caller, src_idx, &inter,
3636 delta);
3638 else
3640 src_plats = ipa_get_parm_lattices (caller_info, src_idx);;
3641 /* Currently we do not produce clobber aggregate jump
3642 functions, adjust when we do. */
3643 gcc_checking_assert (!src_plats->aggs || !jfunc->agg.items);
3644 if (!inter.exists ())
3645 inter = copy_plats_to_inter (src_plats, delta);
3646 else
3647 intersect_with_plats (src_plats, &inter, delta);
3650 else if (jfunc->agg.items)
3652 struct ipa_agg_jf_item *item;
3653 int k;
3655 if (!inter.exists ())
3656 for (unsigned i = 0; i < jfunc->agg.items->length (); i++)
3657 inter.safe_push ((*jfunc->agg.items)[i]);
3658 else
3659 FOR_EACH_VEC_ELT (inter, k, item)
3661 int l = 0;
3662 bool found = false;;
3664 if (!item->value)
3665 continue;
3667 while ((unsigned) l < jfunc->agg.items->length ())
3669 struct ipa_agg_jf_item *ti;
3670 ti = &(*jfunc->agg.items)[l];
3671 if (ti->offset > item->offset)
3672 break;
3673 if (ti->offset == item->offset)
3675 gcc_checking_assert (ti->value);
3676 if (values_equal_for_ipcp_p (item->value,
3677 ti->value))
3678 found = true;
3679 break;
3681 l++;
3683 if (!found)
3684 item->value = NULL;
3687 else
3689 inter.release ();
3690 return vec<ipa_agg_jf_item>();
3692 return inter;
3695 /* Look at edges in CALLERS and collect all known aggregate values that arrive
3696 from all of them. */
3698 static struct ipa_agg_replacement_value *
3699 find_aggregate_values_for_callers_subset (struct cgraph_node *node,
3700 vec<cgraph_edge *> callers)
3702 struct ipa_node_params *dest_info = IPA_NODE_REF (node);
3703 struct ipa_agg_replacement_value *res;
3704 struct ipa_agg_replacement_value **tail = &res;
3705 struct cgraph_edge *cs;
3706 int i, j, count = ipa_get_param_count (dest_info);
3708 FOR_EACH_VEC_ELT (callers, j, cs)
3710 int c = ipa_get_cs_argument_count (IPA_EDGE_REF (cs));
3711 if (c < count)
3712 count = c;
3715 for (i = 0; i < count ; i++)
3717 struct cgraph_edge *cs;
3718 vec<ipa_agg_jf_item> inter = vNULL;
3719 struct ipa_agg_jf_item *item;
3720 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (dest_info, i);
3721 int j;
3723 /* Among other things, the following check should deal with all by_ref
3724 mismatches. */
3725 if (plats->aggs_bottom)
3726 continue;
3728 FOR_EACH_VEC_ELT (callers, j, cs)
3730 inter = intersect_aggregates_with_edge (cs, i, inter);
3732 if (!inter.exists ())
3733 goto next_param;
3736 FOR_EACH_VEC_ELT (inter, j, item)
3738 struct ipa_agg_replacement_value *v;
3740 if (!item->value)
3741 continue;
3743 v = ggc_alloc<ipa_agg_replacement_value> ();
3744 v->index = i;
3745 v->offset = item->offset;
3746 v->value = item->value;
3747 v->by_ref = plats->aggs_by_ref;
3748 *tail = v;
3749 tail = &v->next;
3752 next_param:
3753 if (inter.exists ())
3754 inter.release ();
3756 *tail = NULL;
3757 return res;
3760 /* Turn KNOWN_AGGS into a list of aggreate replacement values. */
3762 static struct ipa_agg_replacement_value *
3763 known_aggs_to_agg_replacement_list (vec<ipa_agg_jump_function> known_aggs)
3765 struct ipa_agg_replacement_value *res;
3766 struct ipa_agg_replacement_value **tail = &res;
3767 struct ipa_agg_jump_function *aggjf;
3768 struct ipa_agg_jf_item *item;
3769 int i, j;
3771 FOR_EACH_VEC_ELT (known_aggs, i, aggjf)
3772 FOR_EACH_VEC_SAFE_ELT (aggjf->items, j, item)
3774 struct ipa_agg_replacement_value *v;
3775 v = ggc_alloc<ipa_agg_replacement_value> ();
3776 v->index = i;
3777 v->offset = item->offset;
3778 v->value = item->value;
3779 v->by_ref = aggjf->by_ref;
3780 *tail = v;
3781 tail = &v->next;
3783 *tail = NULL;
3784 return res;
3787 /* Determine whether CS also brings all scalar values that the NODE is
3788 specialized for. */
3790 static bool
3791 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge *cs,
3792 struct cgraph_node *node)
3794 struct ipa_node_params *dest_info = IPA_NODE_REF (node);
3795 int count = ipa_get_param_count (dest_info);
3796 struct ipa_node_params *caller_info;
3797 struct ipa_edge_args *args;
3798 int i;
3800 caller_info = IPA_NODE_REF (cs->caller);
3801 args = IPA_EDGE_REF (cs);
3802 for (i = 0; i < count; i++)
3804 struct ipa_jump_func *jump_func;
3805 tree val, t;
3807 val = dest_info->known_csts[i];
3808 if (!val)
3809 continue;
3811 if (i >= ipa_get_cs_argument_count (args))
3812 return false;
3813 jump_func = ipa_get_ith_jump_func (args, i);
3814 t = ipa_value_from_jfunc (caller_info, jump_func);
3815 if (!t || !values_equal_for_ipcp_p (val, t))
3816 return false;
3818 return true;
3821 /* Determine whether CS also brings all aggregate values that NODE is
3822 specialized for. */
3823 static bool
3824 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge *cs,
3825 struct cgraph_node *node)
3827 struct ipa_node_params *orig_caller_info = IPA_NODE_REF (cs->caller);
3828 struct ipa_node_params *orig_node_info;
3829 struct ipa_agg_replacement_value *aggval;
3830 int i, ec, count;
3832 aggval = ipa_get_agg_replacements_for_node (node);
3833 if (!aggval)
3834 return true;
3836 count = ipa_get_param_count (IPA_NODE_REF (node));
3837 ec = ipa_get_cs_argument_count (IPA_EDGE_REF (cs));
3838 if (ec < count)
3839 for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next)
3840 if (aggval->index >= ec)
3841 return false;
3843 orig_node_info = IPA_NODE_REF (IPA_NODE_REF (node)->ipcp_orig_node);
3844 if (orig_caller_info->ipcp_orig_node)
3845 orig_caller_info = IPA_NODE_REF (orig_caller_info->ipcp_orig_node);
3847 for (i = 0; i < count; i++)
3849 static vec<ipa_agg_jf_item> values = vec<ipa_agg_jf_item>();
3850 struct ipcp_param_lattices *plats;
3851 bool interesting = false;
3852 for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next)
3853 if (aggval->index == i)
3855 interesting = true;
3856 break;
3858 if (!interesting)
3859 continue;
3861 plats = ipa_get_parm_lattices (orig_node_info, aggval->index);
3862 if (plats->aggs_bottom)
3863 return false;
3865 values = intersect_aggregates_with_edge (cs, i, values);
3866 if (!values.exists ())
3867 return false;
3869 for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next)
3870 if (aggval->index == i)
3872 struct ipa_agg_jf_item *item;
3873 int j;
3874 bool found = false;
3875 FOR_EACH_VEC_ELT (values, j, item)
3876 if (item->value
3877 && item->offset == av->offset
3878 && values_equal_for_ipcp_p (item->value, av->value))
3880 found = true;
3881 break;
3883 if (!found)
3885 values.release ();
3886 return false;
3890 return true;
3893 /* Given an original NODE and a VAL for which we have already created a
3894 specialized clone, look whether there are incoming edges that still lead
3895 into the old node but now also bring the requested value and also conform to
3896 all other criteria such that they can be redirected the the special node.
3897 This function can therefore redirect the final edge in a SCC. */
3899 template <typename valtype>
3900 static void
3901 perhaps_add_new_callers (cgraph_node *node, ipcp_value<valtype> *val)
3903 ipcp_value_source<valtype> *src;
3904 gcov_type redirected_sum = 0;
3906 for (src = val->sources; src; src = src->next)
3908 struct cgraph_edge *cs = src->cs;
3909 while (cs)
3911 if (cgraph_edge_brings_value_p (cs, src, node)
3912 && cgraph_edge_brings_all_scalars_for_node (cs, val->spec_node)
3913 && cgraph_edge_brings_all_agg_vals_for_node (cs, val->spec_node))
3915 if (dump_file)
3916 fprintf (dump_file, " - adding an extra caller %s/%i"
3917 " of %s/%i\n",
3918 xstrdup_for_dump (cs->caller->name ()),
3919 cs->caller->order,
3920 xstrdup_for_dump (val->spec_node->name ()),
3921 val->spec_node->order);
3923 cs->redirect_callee_duplicating_thunks (val->spec_node);
3924 val->spec_node->expand_all_artificial_thunks ();
3925 redirected_sum += cs->count;
3927 cs = get_next_cgraph_edge_clone (cs);
3931 if (redirected_sum)
3932 update_specialized_profile (val->spec_node, node, redirected_sum);
3935 /* Return true if KNOWN_CONTEXTS contain at least one useful context. */
3937 static bool
3938 known_contexts_useful_p (vec<ipa_polymorphic_call_context> known_contexts)
3940 ipa_polymorphic_call_context *ctx;
3941 int i;
3943 FOR_EACH_VEC_ELT (known_contexts, i, ctx)
3944 if (!ctx->useless_p ())
3945 return true;
3946 return false;
3949 /* Return a copy of KNOWN_CSTS if it is not empty, otherwise return vNULL. */
3951 static vec<ipa_polymorphic_call_context>
3952 copy_useful_known_contexts (vec<ipa_polymorphic_call_context> known_contexts)
3954 if (known_contexts_useful_p (known_contexts))
3955 return known_contexts.copy ();
3956 else
3957 return vNULL;
3960 /* Copy KNOWN_CSTS and modify the copy according to VAL and INDEX. If
3961 non-empty, replace KNOWN_CONTEXTS with its copy too. */
3963 static void
3964 modify_known_vectors_with_val (vec<tree> *known_csts,
3965 vec<ipa_polymorphic_call_context> *known_contexts,
3966 ipcp_value<tree> *val,
3967 int index)
3969 *known_csts = known_csts->copy ();
3970 *known_contexts = copy_useful_known_contexts (*known_contexts);
3971 (*known_csts)[index] = val->value;
3974 /* Replace KNOWN_CSTS with its copy. Also copy KNOWN_CONTEXTS and modify the
3975 copy according to VAL and INDEX. */
3977 static void
3978 modify_known_vectors_with_val (vec<tree> *known_csts,
3979 vec<ipa_polymorphic_call_context> *known_contexts,
3980 ipcp_value<ipa_polymorphic_call_context> *val,
3981 int index)
3983 *known_csts = known_csts->copy ();
3984 *known_contexts = known_contexts->copy ();
3985 (*known_contexts)[index] = val->value;
3988 /* Return true if OFFSET indicates this was not an aggregate value or there is
3989 a replacement equivalent to VALUE, INDEX and OFFSET among those in the
3990 AGGVALS list. */
3992 DEBUG_FUNCTION bool
3993 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value *aggvals,
3994 int index, HOST_WIDE_INT offset, tree value)
3996 if (offset == -1)
3997 return true;
3999 while (aggvals)
4001 if (aggvals->index == index
4002 && aggvals->offset == offset
4003 && values_equal_for_ipcp_p (aggvals->value, value))
4004 return true;
4005 aggvals = aggvals->next;
4007 return false;
4010 /* Return true if offset is minus one because source of a polymorphic contect
4011 cannot be an aggregate value. */
4013 DEBUG_FUNCTION bool
4014 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value *,
4015 int , HOST_WIDE_INT offset,
4016 ipa_polymorphic_call_context)
4018 return offset == -1;
4021 /* Decide wheter to create a special version of NODE for value VAL of parameter
4022 at the given INDEX. If OFFSET is -1, the value is for the parameter itself,
4023 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS,
4024 KNOWN_CONTEXTS and KNOWN_AGGS describe the other already known values. */
4026 template <typename valtype>
4027 static bool
4028 decide_about_value (struct cgraph_node *node, int index, HOST_WIDE_INT offset,
4029 ipcp_value<valtype> *val, vec<tree> known_csts,
4030 vec<ipa_polymorphic_call_context> known_contexts)
4032 struct ipa_agg_replacement_value *aggvals;
4033 int freq_sum, caller_count;
4034 gcov_type count_sum;
4035 vec<cgraph_edge *> callers;
4037 if (val->spec_node)
4039 perhaps_add_new_callers (node, val);
4040 return false;
4042 else if (val->local_size_cost + overall_size > max_new_size)
4044 if (dump_file && (dump_flags & TDF_DETAILS))
4045 fprintf (dump_file, " Ignoring candidate value because "
4046 "max_new_size would be reached with %li.\n",
4047 val->local_size_cost + overall_size);
4048 return false;
4050 else if (!get_info_about_necessary_edges (val, node, &freq_sum, &count_sum,
4051 &caller_count))
4052 return false;
4054 if (dump_file && (dump_flags & TDF_DETAILS))
4056 fprintf (dump_file, " - considering value ");
4057 print_ipcp_constant_value (dump_file, val->value);
4058 fprintf (dump_file, " for ");
4059 ipa_dump_param (dump_file, IPA_NODE_REF (node), index);
4060 if (offset != -1)
4061 fprintf (dump_file, ", offset: " HOST_WIDE_INT_PRINT_DEC, offset);
4062 fprintf (dump_file, " (caller_count: %i)\n", caller_count);
4065 if (!good_cloning_opportunity_p (node, val->local_time_benefit,
4066 freq_sum, count_sum,
4067 val->local_size_cost)
4068 && !good_cloning_opportunity_p (node,
4069 val->local_time_benefit
4070 + val->prop_time_benefit,
4071 freq_sum, count_sum,
4072 val->local_size_cost
4073 + val->prop_size_cost))
4074 return false;
4076 if (dump_file)
4077 fprintf (dump_file, " Creating a specialized node of %s/%i.\n",
4078 node->name (), node->order);
4080 callers = gather_edges_for_value (val, node, caller_count);
4081 if (offset == -1)
4082 modify_known_vectors_with_val (&known_csts, &known_contexts, val, index);
4083 else
4085 known_csts = known_csts.copy ();
4086 known_contexts = copy_useful_known_contexts (known_contexts);
4088 find_more_scalar_values_for_callers_subset (node, known_csts, callers);
4089 find_more_contexts_for_caller_subset (node, &known_contexts, callers);
4090 aggvals = find_aggregate_values_for_callers_subset (node, callers);
4091 gcc_checking_assert (ipcp_val_agg_replacement_ok_p (aggvals, index,
4092 offset, val->value));
4093 val->spec_node = create_specialized_node (node, known_csts, known_contexts,
4094 aggvals, callers);
4095 overall_size += val->local_size_cost;
4097 /* TODO: If for some lattice there is only one other known value
4098 left, make a special node for it too. */
4100 return true;
4103 /* Decide whether and what specialized clones of NODE should be created. */
4105 static bool
4106 decide_whether_version_node (struct cgraph_node *node)
4108 struct ipa_node_params *info = IPA_NODE_REF (node);
4109 int i, count = ipa_get_param_count (info);
4110 vec<tree> known_csts;
4111 vec<ipa_polymorphic_call_context> known_contexts;
4112 vec<ipa_agg_jump_function> known_aggs = vNULL;
4113 bool ret = false;
4115 if (count == 0)
4116 return false;
4118 if (dump_file && (dump_flags & TDF_DETAILS))
4119 fprintf (dump_file, "\nEvaluating opportunities for %s/%i.\n",
4120 node->name (), node->order);
4122 gather_context_independent_values (info, &known_csts, &known_contexts,
4123 info->do_clone_for_all_contexts ? &known_aggs
4124 : NULL, NULL);
4126 for (i = 0; i < count ;i++)
4128 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
4129 ipcp_lattice<tree> *lat = &plats->itself;
4130 ipcp_lattice<ipa_polymorphic_call_context> *ctxlat = &plats->ctxlat;
4132 if (!lat->bottom
4133 && !known_csts[i])
4135 ipcp_value<tree> *val;
4136 for (val = lat->values; val; val = val->next)
4137 ret |= decide_about_value (node, i, -1, val, known_csts,
4138 known_contexts);
4141 if (!plats->aggs_bottom)
4143 struct ipcp_agg_lattice *aglat;
4144 ipcp_value<tree> *val;
4145 for (aglat = plats->aggs; aglat; aglat = aglat->next)
4146 if (!aglat->bottom && aglat->values
4147 /* If the following is false, the one value is in
4148 known_aggs. */
4149 && (plats->aggs_contain_variable
4150 || !aglat->is_single_const ()))
4151 for (val = aglat->values; val; val = val->next)
4152 ret |= decide_about_value (node, i, aglat->offset, val,
4153 known_csts, known_contexts);
4156 if (!ctxlat->bottom
4157 && known_contexts[i].useless_p ())
4159 ipcp_value<ipa_polymorphic_call_context> *val;
4160 for (val = ctxlat->values; val; val = val->next)
4161 ret |= decide_about_value (node, i, -1, val, known_csts,
4162 known_contexts);
4165 info = IPA_NODE_REF (node);
4168 if (info->do_clone_for_all_contexts)
4170 struct cgraph_node *clone;
4171 vec<cgraph_edge *> callers;
4173 if (dump_file)
4174 fprintf (dump_file, " - Creating a specialized node of %s/%i "
4175 "for all known contexts.\n", node->name (),
4176 node->order);
4178 callers = node->collect_callers ();
4180 if (!known_contexts_useful_p (known_contexts))
4182 known_contexts.release ();
4183 known_contexts = vNULL;
4185 clone = create_specialized_node (node, known_csts, known_contexts,
4186 known_aggs_to_agg_replacement_list (known_aggs),
4187 callers);
4188 info = IPA_NODE_REF (node);
4189 info->do_clone_for_all_contexts = false;
4190 IPA_NODE_REF (clone)->is_all_contexts_clone = true;
4191 for (i = 0; i < count ; i++)
4192 vec_free (known_aggs[i].items);
4193 known_aggs.release ();
4194 ret = true;
4196 else
4198 known_csts.release ();
4199 known_contexts.release ();
4202 return ret;
4205 /* Transitively mark all callees of NODE within the same SCC as not dead. */
4207 static void
4208 spread_undeadness (struct cgraph_node *node)
4210 struct cgraph_edge *cs;
4212 for (cs = node->callees; cs; cs = cs->next_callee)
4213 if (ipa_edge_within_scc (cs))
4215 struct cgraph_node *callee;
4216 struct ipa_node_params *info;
4218 callee = cs->callee->function_symbol (NULL);
4219 info = IPA_NODE_REF (callee);
4221 if (info->node_dead)
4223 info->node_dead = 0;
4224 spread_undeadness (callee);
4229 /* Return true if NODE has a caller from outside of its SCC that is not
4230 dead. Worker callback for cgraph_for_node_and_aliases. */
4232 static bool
4233 has_undead_caller_from_outside_scc_p (struct cgraph_node *node,
4234 void *data ATTRIBUTE_UNUSED)
4236 struct cgraph_edge *cs;
4238 for (cs = node->callers; cs; cs = cs->next_caller)
4239 if (cs->caller->thunk.thunk_p
4240 && cs->caller->call_for_symbol_thunks_and_aliases
4241 (has_undead_caller_from_outside_scc_p, NULL, true))
4242 return true;
4243 else if (!ipa_edge_within_scc (cs)
4244 && !IPA_NODE_REF (cs->caller)->node_dead)
4245 return true;
4246 return false;
4250 /* Identify nodes within the same SCC as NODE which are no longer needed
4251 because of new clones and will be removed as unreachable. */
4253 static void
4254 identify_dead_nodes (struct cgraph_node *node)
4256 struct cgraph_node *v;
4257 for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
4258 if (v->will_be_removed_from_program_if_no_direct_calls_p ()
4259 && !v->call_for_symbol_thunks_and_aliases
4260 (has_undead_caller_from_outside_scc_p, NULL, true))
4261 IPA_NODE_REF (v)->node_dead = 1;
4263 for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
4264 if (!IPA_NODE_REF (v)->node_dead)
4265 spread_undeadness (v);
4267 if (dump_file && (dump_flags & TDF_DETAILS))
4269 for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
4270 if (IPA_NODE_REF (v)->node_dead)
4271 fprintf (dump_file, " Marking node as dead: %s/%i.\n",
4272 v->name (), v->order);
4276 /* The decision stage. Iterate over the topological order of call graph nodes
4277 TOPO and make specialized clones if deemed beneficial. */
4279 static void
4280 ipcp_decision_stage (struct ipa_topo_info *topo)
4282 int i;
4284 if (dump_file)
4285 fprintf (dump_file, "\nIPA decision stage:\n\n");
4287 for (i = topo->nnodes - 1; i >= 0; i--)
4289 struct cgraph_node *node = topo->order[i];
4290 bool change = false, iterate = true;
4292 while (iterate)
4294 struct cgraph_node *v;
4295 iterate = false;
4296 for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
4297 if (v->has_gimple_body_p ()
4298 && ipcp_versionable_function_p (v))
4299 iterate |= decide_whether_version_node (v);
4301 change |= iterate;
4303 if (change)
4304 identify_dead_nodes (node);
4308 /* Look up all alignment information that we have discovered and copy it over
4309 to the transformation summary. */
4311 static void
4312 ipcp_store_alignment_results (void)
4314 cgraph_node *node;
4316 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
4318 ipa_node_params *info = IPA_NODE_REF (node);
4319 bool dumped_sth = false;
4320 bool found_useful_result = false;
4322 if (info->ipcp_orig_node)
4323 info = IPA_NODE_REF (info->ipcp_orig_node);
4325 unsigned count = ipa_get_param_count (info);
4326 for (unsigned i = 0; i < count ; i++)
4328 ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
4329 if (plats->alignment.known
4330 && plats->alignment.align > 0)
4332 found_useful_result = true;
4333 break;
4336 if (!found_useful_result)
4337 continue;
4339 ipcp_grow_transformations_if_necessary ();
4340 ipcp_transformation_summary *ts = ipcp_get_transformation_summary (node);
4341 vec_safe_reserve_exact (ts->alignments, count);
4343 for (unsigned i = 0; i < count ; i++)
4345 ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
4347 if (plats->alignment.align == 0)
4348 plats->alignment.known = false;
4350 ts->alignments->quick_push (plats->alignment);
4351 if (!dump_file || !plats->alignment.known)
4352 continue;
4353 if (!dumped_sth)
4355 fprintf (dump_file, "Propagated alignment info for function %s/%i:\n",
4356 node->name (), node->order);
4357 dumped_sth = true;
4359 fprintf (dump_file, " param %i: align: %u, misalign: %u\n",
4360 i, plats->alignment.align, plats->alignment.misalign);
4365 /* The IPCP driver. */
4367 static unsigned int
4368 ipcp_driver (void)
4370 struct cgraph_2edge_hook_list *edge_duplication_hook_holder;
4371 struct cgraph_edge_hook_list *edge_removal_hook_holder;
4372 struct ipa_topo_info topo;
4374 ipa_check_create_node_params ();
4375 ipa_check_create_edge_args ();
4376 grow_edge_clone_vectors ();
4377 edge_duplication_hook_holder =
4378 symtab->add_edge_duplication_hook (&ipcp_edge_duplication_hook, NULL);
4379 edge_removal_hook_holder =
4380 symtab->add_edge_removal_hook (&ipcp_edge_removal_hook, NULL);
4382 ipcp_cst_values_pool = create_alloc_pool ("IPA-CP constant values",
4383 sizeof (ipcp_value<tree>), 32);
4384 ipcp_poly_ctx_values_pool = create_alloc_pool
4385 ("IPA-CP polymorphic contexts",
4386 sizeof (ipcp_value<ipa_polymorphic_call_context>), 32);
4387 ipcp_sources_pool = create_alloc_pool ("IPA-CP value sources",
4388 sizeof (ipcp_value_source<tree>), 64);
4389 ipcp_agg_lattice_pool = create_alloc_pool ("IPA_CP aggregate lattices",
4390 sizeof (struct ipcp_agg_lattice),
4391 32);
4392 if (dump_file)
4394 fprintf (dump_file, "\nIPA structures before propagation:\n");
4395 if (dump_flags & TDF_DETAILS)
4396 ipa_print_all_params (dump_file);
4397 ipa_print_all_jump_functions (dump_file);
4400 /* Topological sort. */
4401 build_toporder_info (&topo);
4402 /* Do the interprocedural propagation. */
4403 ipcp_propagate_stage (&topo);
4404 /* Decide what constant propagation and cloning should be performed. */
4405 ipcp_decision_stage (&topo);
4406 /* Store results of alignment propagation. */
4407 ipcp_store_alignment_results ();
4409 /* Free all IPCP structures. */
4410 free_toporder_info (&topo);
4411 next_edge_clone.release ();
4412 symtab->remove_edge_removal_hook (edge_removal_hook_holder);
4413 symtab->remove_edge_duplication_hook (edge_duplication_hook_holder);
4414 ipa_free_all_structures_after_ipa_cp ();
4415 if (dump_file)
4416 fprintf (dump_file, "\nIPA constant propagation end\n");
4417 return 0;
4420 /* Initialization and computation of IPCP data structures. This is the initial
4421 intraprocedural analysis of functions, which gathers information to be
4422 propagated later on. */
4424 static void
4425 ipcp_generate_summary (void)
4427 struct cgraph_node *node;
4429 if (dump_file)
4430 fprintf (dump_file, "\nIPA constant propagation start:\n");
4431 ipa_register_cgraph_hooks ();
4433 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
4435 node->local.versionable
4436 = tree_versionable_function_p (node->decl);
4437 ipa_analyze_node (node);
4441 /* Write ipcp summary for nodes in SET. */
4443 static void
4444 ipcp_write_summary (void)
4446 ipa_prop_write_jump_functions ();
4449 /* Read ipcp summary. */
4451 static void
4452 ipcp_read_summary (void)
4454 ipa_prop_read_jump_functions ();
4457 namespace {
4459 const pass_data pass_data_ipa_cp =
4461 IPA_PASS, /* type */
4462 "cp", /* name */
4463 OPTGROUP_NONE, /* optinfo_flags */
4464 TV_IPA_CONSTANT_PROP, /* tv_id */
4465 0, /* properties_required */
4466 0, /* properties_provided */
4467 0, /* properties_destroyed */
4468 0, /* todo_flags_start */
4469 ( TODO_dump_symtab | TODO_remove_functions ), /* todo_flags_finish */
4472 class pass_ipa_cp : public ipa_opt_pass_d
4474 public:
4475 pass_ipa_cp (gcc::context *ctxt)
4476 : ipa_opt_pass_d (pass_data_ipa_cp, ctxt,
4477 ipcp_generate_summary, /* generate_summary */
4478 ipcp_write_summary, /* write_summary */
4479 ipcp_read_summary, /* read_summary */
4480 ipcp_write_transformation_summaries, /*
4481 write_optimization_summary */
4482 ipcp_read_transformation_summaries, /*
4483 read_optimization_summary */
4484 NULL, /* stmt_fixup */
4485 0, /* function_transform_todo_flags_start */
4486 ipcp_transform_function, /* function_transform */
4487 NULL) /* variable_transform */
4490 /* opt_pass methods: */
4491 virtual bool gate (function *)
4493 /* FIXME: We should remove the optimize check after we ensure we never run
4494 IPA passes when not optimizing. */
4495 return (flag_ipa_cp && optimize) || in_lto_p;
4498 virtual unsigned int execute (function *) { return ipcp_driver (); }
4500 }; // class pass_ipa_cp
4502 } // anon namespace
4504 ipa_opt_pass_d *
4505 make_pass_ipa_cp (gcc::context *ctxt)
4507 return new pass_ipa_cp (ctxt);
4510 /* Reset all state within ipa-cp.c so that we can rerun the compiler
4511 within the same process. For use by toplev::finalize. */
4513 void
4514 ipa_cp_c_finalize (void)
4516 max_count = 0;
4517 overall_size = 0;
4518 max_new_size = 0;