1 /* Interprocedural constant propagation
2 Copyright (C) 2005-2016 Free Software Foundation, Inc.
4 Contributed by Razya Ladelsky <RAZYA@il.ibm.com> and Martin Jambor
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
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
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
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
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
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
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
105 #include "coretypes.h"
108 #include "gimple-expr.h"
110 #include "alloc-pool.h"
111 #include "tree-pass.h"
113 #include "diagnostic.h"
114 #include "fold-const.h"
115 #include "gimple-fold.h"
116 #include "symbol-summary.h"
117 #include "ipa-prop.h"
118 #include "tree-pretty-print.h"
119 #include "tree-inline.h"
121 #include "ipa-inline.h"
122 #include "ipa-utils.h"
124 template <typename valtype> class ipcp_value;
126 /* Describes a particular source for an IPA-CP value. */
128 template <typename valtype>
129 class ipcp_value_source
132 /* Aggregate offset of the source, negative if the source is scalar value of
133 the argument itself. */
134 HOST_WIDE_INT offset;
135 /* The incoming edge that brought the value. */
137 /* If the jump function that resulted into his value was a pass-through or an
138 ancestor, this is the ipcp_value of the caller from which the described
139 value has been derived. Otherwise it is NULL. */
140 ipcp_value<valtype> *val;
141 /* Next pointer in a linked list of sources of a value. */
142 ipcp_value_source *next;
143 /* If the jump function that resulted into his value was a pass-through or an
144 ancestor, this is the index of the parameter of the caller the jump
145 function references. */
149 /* Common ancestor for all ipcp_value instantiations. */
151 class ipcp_value_base
154 /* Time benefit and size cost that specializing the function for this value
155 would bring about in this function alone. */
156 int local_time_benefit, local_size_cost;
157 /* Time benefit and size cost that specializing the function for this value
158 can bring about in it's callees (transitively). */
159 int prop_time_benefit, prop_size_cost;
162 /* Describes one particular value stored in struct ipcp_lattice. */
164 template <typename valtype>
165 class ipcp_value : public ipcp_value_base
168 /* The actual value for the given parameter. */
170 /* The list of sources from which this value originates. */
171 ipcp_value_source <valtype> *sources;
172 /* Next pointers in a linked list of all values in a lattice. */
174 /* Next pointers in a linked list of values in a strongly connected component
176 ipcp_value *scc_next;
177 /* Next pointers in a linked list of SCCs of values sorted topologically
178 according their sources. */
179 ipcp_value *topo_next;
180 /* A specialized node created for this value, NULL if none has been (so far)
182 cgraph_node *spec_node;
183 /* Depth first search number and low link for topological sorting of
186 /* True if this valye is currently on the topo-sort stack. */
189 void add_source (cgraph_edge *cs, ipcp_value *src_val, int src_idx,
190 HOST_WIDE_INT offset);
193 /* Lattice describing potential values of a formal parameter of a function, or
194 a part of an aggreagate. TOP is represented by a lattice with zero values
195 and with contains_variable and bottom flags cleared. BOTTOM is represented
196 by a lattice with the bottom flag set. In that case, values and
197 contains_variable flag should be disregarded. */
199 template <typename valtype>
203 /* The list of known values and types in this lattice. Note that values are
204 not deallocated if a lattice is set to bottom because there may be value
205 sources referencing them. */
206 ipcp_value<valtype> *values;
207 /* Number of known values and types in this lattice. */
209 /* The lattice contains a variable component (in addition to values). */
210 bool contains_variable;
211 /* The value of the lattice is bottom (i.e. variable and unusable for any
215 inline bool is_single_const ();
216 inline bool set_to_bottom ();
217 inline bool set_contains_variable ();
218 bool add_value (valtype newval, cgraph_edge *cs,
219 ipcp_value<valtype> *src_val = NULL,
220 int src_idx = 0, HOST_WIDE_INT offset = -1);
221 void print (FILE * f, bool dump_sources, bool dump_benefits);
224 /* Lattice of tree values with an offset to describe a part of an
227 class ipcp_agg_lattice : public ipcp_lattice<tree>
230 /* Offset that is being described by this lattice. */
231 HOST_WIDE_INT offset;
232 /* Size so that we don't have to re-compute it every time we traverse the
233 list. Must correspond to TYPE_SIZE of all lat values. */
235 /* Next element of the linked list. */
236 struct ipcp_agg_lattice *next;
239 /* Lattice of pointer alignment. Unlike the previous types of lattices, this
240 one is only capable of holding one value. */
242 class ipcp_alignment_lattice
245 /* If bottom and top are both false, these two fields hold values as given by
246 ptr_info_def and get_pointer_alignment_1. */
250 inline bool bottom_p () const;
251 inline bool top_p () const;
252 inline bool set_to_bottom ();
253 bool meet_with (unsigned new_align, unsigned new_misalign);
254 bool meet_with (const ipcp_alignment_lattice &other, HOST_WIDE_INT offset);
255 void print (FILE * f);
257 /* If set, this lattice is bottom and all other fields should be
260 /* If bottom and not_top are false, the lattice is TOP. If not_top is true,
261 the known alignment is stored in the fields align and misalign. The field
262 is negated so that memset to zero initializes the lattice to TOP
266 bool meet_with_1 (unsigned new_align, unsigned new_misalign);
269 /* Structure containing lattices for a parameter itself and for pieces of
270 aggregates that are passed in the parameter or by a reference in a parameter
271 plus some other useful flags. */
273 class ipcp_param_lattices
276 /* Lattice describing the value of the parameter itself. */
277 ipcp_lattice<tree> itself;
278 /* Lattice describing the polymorphic contexts of a parameter. */
279 ipcp_lattice<ipa_polymorphic_call_context> ctxlat;
280 /* Lattices describing aggregate parts. */
281 ipcp_agg_lattice *aggs;
282 /* Lattice describing known alignment. */
283 ipcp_alignment_lattice alignment;
284 /* Number of aggregate lattices */
286 /* True if aggregate data were passed by reference (as opposed to by
289 /* All aggregate lattices contain a variable component (in addition to
291 bool aggs_contain_variable;
292 /* The value of all aggregate lattices is bottom (i.e. variable and unusable
293 for any propagation). */
296 /* There is a virtual call based on this parameter. */
300 /* Allocation pools for values and their sources in ipa-cp. */
302 object_allocator<ipcp_value<tree> > ipcp_cst_values_pool
303 ("IPA-CP constant values");
305 object_allocator<ipcp_value<ipa_polymorphic_call_context> >
306 ipcp_poly_ctx_values_pool ("IPA-CP polymorphic contexts");
308 object_allocator<ipcp_value_source<tree> > ipcp_sources_pool
309 ("IPA-CP value sources");
311 object_allocator<ipcp_agg_lattice> ipcp_agg_lattice_pool
312 ("IPA_CP aggregate lattices");
314 /* Maximal count found in program. */
316 static gcov_type max_count;
318 /* Original overall size of the program. */
320 static long overall_size, max_new_size;
322 /* Return the param lattices structure corresponding to the Ith formal
323 parameter of the function described by INFO. */
324 static inline struct ipcp_param_lattices *
325 ipa_get_parm_lattices (struct ipa_node_params *info, int i)
327 gcc_assert (i >= 0 && i < ipa_get_param_count (info));
328 gcc_checking_assert (!info->ipcp_orig_node);
329 gcc_checking_assert (info->lattices);
330 return &(info->lattices[i]);
333 /* Return the lattice corresponding to the scalar value of the Ith formal
334 parameter of the function described by INFO. */
335 static inline ipcp_lattice<tree> *
336 ipa_get_scalar_lat (struct ipa_node_params *info, int i)
338 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
339 return &plats->itself;
342 /* Return the lattice corresponding to the scalar value of the Ith formal
343 parameter of the function described by INFO. */
344 static inline ipcp_lattice<ipa_polymorphic_call_context> *
345 ipa_get_poly_ctx_lat (struct ipa_node_params *info, int i)
347 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
348 return &plats->ctxlat;
351 /* Return whether LAT is a lattice with a single constant and without an
354 template <typename valtype>
356 ipcp_lattice<valtype>::is_single_const ()
358 if (bottom || contains_variable || values_count != 1)
364 /* Print V which is extracted from a value in a lattice to F. */
367 print_ipcp_constant_value (FILE * f, tree v)
369 if (TREE_CODE (v) == ADDR_EXPR
370 && TREE_CODE (TREE_OPERAND (v, 0)) == CONST_DECL)
373 print_generic_expr (f, DECL_INITIAL (TREE_OPERAND (v, 0)), 0);
376 print_generic_expr (f, v, 0);
379 /* Print V which is extracted from a value in a lattice to F. */
382 print_ipcp_constant_value (FILE * f, ipa_polymorphic_call_context v)
387 /* Print a lattice LAT to F. */
389 template <typename valtype>
391 ipcp_lattice<valtype>::print (FILE * f, bool dump_sources, bool dump_benefits)
393 ipcp_value<valtype> *val;
398 fprintf (f, "BOTTOM\n");
402 if (!values_count && !contains_variable)
404 fprintf (f, "TOP\n");
408 if (contains_variable)
410 fprintf (f, "VARIABLE");
416 for (val = values; val; val = val->next)
418 if (dump_benefits && prev)
420 else if (!dump_benefits && prev)
425 print_ipcp_constant_value (f, val->value);
429 ipcp_value_source<valtype> *s;
431 fprintf (f, " [from:");
432 for (s = val->sources; s; s = s->next)
433 fprintf (f, " %i(%i)", s->cs->caller->order,
439 fprintf (f, " [loc_time: %i, loc_size: %i, "
440 "prop_time: %i, prop_size: %i]\n",
441 val->local_time_benefit, val->local_size_cost,
442 val->prop_time_benefit, val->prop_size_cost);
448 /* Print alignment lattice to F. */
451 ipcp_alignment_lattice::print (FILE * f)
454 fprintf (f, " Alignment unknown (TOP)\n");
455 else if (bottom_p ())
456 fprintf (f, " Alignment unusable (BOTTOM)\n");
458 fprintf (f, " Alignment %u, misalignment %u\n", align, misalign);
461 /* Print all ipcp_lattices of all functions to F. */
464 print_all_lattices (FILE * f, bool dump_sources, bool dump_benefits)
466 struct cgraph_node *node;
469 fprintf (f, "\nLattices:\n");
470 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
472 struct ipa_node_params *info;
474 info = IPA_NODE_REF (node);
475 fprintf (f, " Node: %s/%i:\n", node->name (),
477 count = ipa_get_param_count (info);
478 for (i = 0; i < count; i++)
480 struct ipcp_agg_lattice *aglat;
481 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
482 fprintf (f, " param [%d]: ", i);
483 plats->itself.print (f, dump_sources, dump_benefits);
484 fprintf (f, " ctxs: ");
485 plats->ctxlat.print (f, dump_sources, dump_benefits);
486 plats->alignment.print (f);
487 if (plats->virt_call)
488 fprintf (f, " virt_call flag set\n");
490 if (plats->aggs_bottom)
492 fprintf (f, " AGGS BOTTOM\n");
495 if (plats->aggs_contain_variable)
496 fprintf (f, " AGGS VARIABLE\n");
497 for (aglat = plats->aggs; aglat; aglat = aglat->next)
499 fprintf (f, " %soffset " HOST_WIDE_INT_PRINT_DEC ": ",
500 plats->aggs_by_ref ? "ref " : "", aglat->offset);
501 aglat->print (f, dump_sources, dump_benefits);
507 /* Determine whether it is at all technically possible to create clones of NODE
508 and store this information in the ipa_node_params structure associated
512 determine_versionability (struct cgraph_node *node,
513 struct ipa_node_params *info)
515 const char *reason = NULL;
517 /* There are a number of generic reasons functions cannot be versioned. We
518 also cannot remove parameters if there are type attributes such as fnspec
520 if (node->alias || node->thunk.thunk_p)
521 reason = "alias or thunk";
522 else if (!node->local.versionable)
523 reason = "not a tree_versionable_function";
524 else if (node->get_availability () <= AVAIL_INTERPOSABLE)
525 reason = "insufficient body availability";
526 else if (!opt_for_fn (node->decl, optimize)
527 || !opt_for_fn (node->decl, flag_ipa_cp))
528 reason = "non-optimized function";
529 else if (lookup_attribute ("omp declare simd", DECL_ATTRIBUTES (node->decl)))
531 /* Ideally we should clone the SIMD clones themselves and create
532 vector copies of them, so IPA-cp and SIMD clones can happily
533 coexist, but that may not be worth the effort. */
534 reason = "function has SIMD clones";
536 /* Don't clone decls local to a comdat group; it breaks and for C++
537 decloned constructors, inlining is always better anyway. */
538 else if (node->comdat_local_p ())
539 reason = "comdat-local function";
541 if (reason && dump_file && !node->alias && !node->thunk.thunk_p)
542 fprintf (dump_file, "Function %s/%i is not versionable, reason: %s.\n",
543 node->name (), node->order, reason);
545 info->versionable = (reason == NULL);
548 /* Return true if it is at all technically possible to create clones of a
552 ipcp_versionable_function_p (struct cgraph_node *node)
554 return IPA_NODE_REF (node)->versionable;
557 /* Structure holding accumulated information about callers of a node. */
559 struct caller_statistics
562 int n_calls, n_hot_calls, freq_sum;
565 /* Initialize fields of STAT to zeroes. */
568 init_caller_stats (struct caller_statistics *stats)
570 stats->count_sum = 0;
572 stats->n_hot_calls = 0;
576 /* Worker callback of cgraph_for_node_and_aliases accumulating statistics of
577 non-thunk incoming edges to NODE. */
580 gather_caller_stats (struct cgraph_node *node, void *data)
582 struct caller_statistics *stats = (struct caller_statistics *) data;
583 struct cgraph_edge *cs;
585 for (cs = node->callers; cs; cs = cs->next_caller)
586 if (!cs->caller->thunk.thunk_p)
588 stats->count_sum += cs->count;
589 stats->freq_sum += cs->frequency;
591 if (cs->maybe_hot_p ())
592 stats->n_hot_calls ++;
598 /* Return true if this NODE is viable candidate for cloning. */
601 ipcp_cloning_candidate_p (struct cgraph_node *node)
603 struct caller_statistics stats;
605 gcc_checking_assert (node->has_gimple_body_p ());
607 if (!opt_for_fn (node->decl, flag_ipa_cp_clone))
610 fprintf (dump_file, "Not considering %s for cloning; "
611 "-fipa-cp-clone disabled.\n",
616 if (node->optimize_for_size_p ())
619 fprintf (dump_file, "Not considering %s for cloning; "
620 "optimizing it for size.\n",
625 init_caller_stats (&stats);
626 node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats, false);
628 if (inline_summaries->get (node)->self_size < stats.n_calls)
631 fprintf (dump_file, "Considering %s for cloning; code might shrink.\n",
636 /* When profile is available and function is hot, propagate into it even if
637 calls seems cold; constant propagation can improve function's speed
641 if (stats.count_sum > node->count * 90 / 100)
644 fprintf (dump_file, "Considering %s for cloning; "
645 "usually called directly.\n",
650 if (!stats.n_hot_calls)
653 fprintf (dump_file, "Not considering %s for cloning; no hot calls.\n",
658 fprintf (dump_file, "Considering %s for cloning.\n",
663 template <typename valtype>
664 class value_topo_info
667 /* Head of the linked list of topologically sorted values. */
668 ipcp_value<valtype> *values_topo;
669 /* Stack for creating SCCs, represented by a linked list too. */
670 ipcp_value<valtype> *stack;
671 /* Counter driving the algorithm in add_val_to_toposort. */
674 value_topo_info () : values_topo (NULL), stack (NULL), dfs_counter (0)
676 void add_val (ipcp_value<valtype> *cur_val);
677 void propagate_effects ();
680 /* Arrays representing a topological ordering of call graph nodes and a stack
681 of nodes used during constant propagation and also data required to perform
682 topological sort of values and propagation of benefits in the determined
688 /* Array with obtained topological order of cgraph nodes. */
689 struct cgraph_node **order;
690 /* Stack of cgraph nodes used during propagation within SCC until all values
691 in the SCC stabilize. */
692 struct cgraph_node **stack;
693 int nnodes, stack_top;
695 value_topo_info<tree> constants;
696 value_topo_info<ipa_polymorphic_call_context> contexts;
698 ipa_topo_info () : order(NULL), stack(NULL), nnodes(0), stack_top(0),
703 /* Allocate the arrays in TOPO and topologically sort the nodes into order. */
706 build_toporder_info (struct ipa_topo_info *topo)
708 topo->order = XCNEWVEC (struct cgraph_node *, symtab->cgraph_count);
709 topo->stack = XCNEWVEC (struct cgraph_node *, symtab->cgraph_count);
711 gcc_checking_assert (topo->stack_top == 0);
712 topo->nnodes = ipa_reduced_postorder (topo->order, true, true, NULL);
715 /* Free information about strongly connected components and the arrays in
719 free_toporder_info (struct ipa_topo_info *topo)
721 ipa_free_postorder_info ();
726 /* Add NODE to the stack in TOPO, unless it is already there. */
729 push_node_to_stack (struct ipa_topo_info *topo, struct cgraph_node *node)
731 struct ipa_node_params *info = IPA_NODE_REF (node);
732 if (info->node_enqueued)
734 info->node_enqueued = 1;
735 topo->stack[topo->stack_top++] = node;
738 /* Pop a node from the stack in TOPO and return it or return NULL if the stack
741 static struct cgraph_node *
742 pop_node_from_stack (struct ipa_topo_info *topo)
746 struct cgraph_node *node;
748 node = topo->stack[topo->stack_top];
749 IPA_NODE_REF (node)->node_enqueued = 0;
756 /* Set lattice LAT to bottom and return true if it previously was not set as
759 template <typename valtype>
761 ipcp_lattice<valtype>::set_to_bottom ()
768 /* Mark lattice as containing an unknown value and return true if it previously
769 was not marked as such. */
771 template <typename valtype>
773 ipcp_lattice<valtype>::set_contains_variable ()
775 bool ret = !contains_variable;
776 contains_variable = true;
780 /* Set all aggegate lattices in PLATS to bottom and return true if they were
781 not previously set as such. */
784 set_agg_lats_to_bottom (struct ipcp_param_lattices *plats)
786 bool ret = !plats->aggs_bottom;
787 plats->aggs_bottom = true;
791 /* Mark all aggegate lattices in PLATS as containing an unknown value and
792 return true if they were not previously marked as such. */
795 set_agg_lats_contain_variable (struct ipcp_param_lattices *plats)
797 bool ret = !plats->aggs_contain_variable;
798 plats->aggs_contain_variable = true;
802 /* Return true if alignment information in the lattice is yet unknown. */
805 ipcp_alignment_lattice::top_p () const
807 return !bottom && !not_top;
810 /* Return true if alignment information in the lattice is known to be
814 ipcp_alignment_lattice::bottom_p () const
819 /* Set alignment information in the lattice to bottom. Return true if it
820 previously was in a different state. */
823 ipcp_alignment_lattice::set_to_bottom ()
831 /* Meet the current value of the lattice with alignment described by NEW_ALIGN
832 and NEW_MISALIGN, assuming that we know the current value is neither TOP nor
833 BOTTOM. Return true if the value of lattice has changed. */
836 ipcp_alignment_lattice::meet_with_1 (unsigned new_align, unsigned new_misalign)
838 gcc_checking_assert (new_align != 0);
839 if (align == new_align && misalign == new_misalign)
842 bool changed = false;
843 if (align > new_align)
846 misalign = misalign % new_align;
849 if (misalign != (new_misalign % align))
851 int diff = abs ((int) misalign - (int) (new_misalign % align));
852 align = (unsigned) diff & -diff;
854 misalign = misalign % align;
859 gcc_checking_assert (bottom_p () || align != 0);
863 /* Meet the current value of the lattice with alignment described by NEW_ALIGN
864 and NEW_MISALIGN. Return true if the value of lattice has changed. */
867 ipcp_alignment_lattice::meet_with (unsigned new_align, unsigned new_misalign)
869 gcc_assert (new_align != 0);
876 misalign = new_misalign;
879 return meet_with_1 (new_align, new_misalign);
882 /* Meet the current value of the lattice with OTHER, taking into account that
883 OFFSET has been added to the pointer value. Return true if the value of
884 lattice has changed. */
887 ipcp_alignment_lattice::meet_with (const ipcp_alignment_lattice &other,
888 HOST_WIDE_INT offset)
890 if (other.bottom_p ())
891 return set_to_bottom ();
892 if (bottom_p () || other.top_p ())
895 unsigned adjusted_misalign = (other.misalign + offset) % other.align;
900 misalign = adjusted_misalign;
904 return meet_with_1 (other.align, adjusted_misalign);
907 /* Mark bot aggregate and scalar lattices as containing an unknown variable,
908 return true is any of them has not been marked as such so far. */
911 set_all_contains_variable (struct ipcp_param_lattices *plats)
914 ret = plats->itself.set_contains_variable ();
915 ret |= plats->ctxlat.set_contains_variable ();
916 ret |= set_agg_lats_contain_variable (plats);
917 ret |= plats->alignment.set_to_bottom ();
921 /* Worker of call_for_symbol_thunks_and_aliases, increment the integer DATA
922 points to by the number of callers to NODE. */
925 count_callers (cgraph_node *node, void *data)
927 int *caller_count = (int *) data;
929 for (cgraph_edge *cs = node->callers; cs; cs = cs->next_caller)
930 /* Local thunks can be handled transparently, but if the thunk can not
931 be optimized out, count it as a real use. */
932 if (!cs->caller->thunk.thunk_p || !cs->caller->local.local)
937 /* Worker of call_for_symbol_thunks_and_aliases, it is supposed to be called on
938 the one caller of some other node. Set the caller's corresponding flag. */
941 set_single_call_flag (cgraph_node *node, void *)
943 cgraph_edge *cs = node->callers;
944 /* Local thunks can be handled transparently, skip them. */
945 while (cs && cs->caller->thunk.thunk_p && cs->caller->local.local)
946 cs = cs->next_caller;
949 IPA_NODE_REF (cs->caller)->node_calling_single_call = true;
955 /* Initialize ipcp_lattices. */
958 initialize_node_lattices (struct cgraph_node *node)
960 struct ipa_node_params *info = IPA_NODE_REF (node);
961 struct cgraph_edge *ie;
962 bool disable = false, variable = false;
965 gcc_checking_assert (node->has_gimple_body_p ());
966 if (cgraph_local_p (node))
968 int caller_count = 0;
969 node->call_for_symbol_thunks_and_aliases (count_callers, &caller_count,
971 gcc_checking_assert (caller_count > 0);
972 if (caller_count == 1)
973 node->call_for_symbol_thunks_and_aliases (set_single_call_flag,
978 /* When cloning is allowed, we can assume that externally visible
979 functions are not called. We will compensate this by cloning
981 if (ipcp_versionable_function_p (node)
982 && ipcp_cloning_candidate_p (node))
988 if (disable || variable)
990 for (i = 0; i < ipa_get_param_count (info) ; i++)
992 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
995 plats->itself.set_to_bottom ();
996 plats->ctxlat.set_to_bottom ();
997 set_agg_lats_to_bottom (plats);
998 plats->alignment.set_to_bottom ();
1001 set_all_contains_variable (plats);
1003 if (dump_file && (dump_flags & TDF_DETAILS)
1004 && !node->alias && !node->thunk.thunk_p)
1005 fprintf (dump_file, "Marking all lattices of %s/%i as %s\n",
1006 node->name (), node->order,
1007 disable ? "BOTTOM" : "VARIABLE");
1010 for (ie = node->indirect_calls; ie; ie = ie->next_callee)
1011 if (ie->indirect_info->polymorphic
1012 && ie->indirect_info->param_index >= 0)
1014 gcc_checking_assert (ie->indirect_info->param_index >= 0);
1015 ipa_get_parm_lattices (info,
1016 ie->indirect_info->param_index)->virt_call = 1;
1020 /* Return the result of a (possibly arithmetic) pass through jump function
1021 JFUNC on the constant value INPUT. Return NULL_TREE if that cannot be
1022 determined or be considered an interprocedural invariant. */
1025 ipa_get_jf_pass_through_result (struct ipa_jump_func *jfunc, tree input)
1029 gcc_checking_assert (is_gimple_ip_invariant (input));
1030 if (ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
1033 if (TREE_CODE_CLASS (ipa_get_jf_pass_through_operation (jfunc))
1035 restype = boolean_type_node;
1037 restype = TREE_TYPE (input);
1038 res = fold_binary (ipa_get_jf_pass_through_operation (jfunc), restype,
1039 input, ipa_get_jf_pass_through_operand (jfunc));
1041 if (res && !is_gimple_ip_invariant (res))
1047 /* Return the result of an ancestor jump function JFUNC on the constant value
1048 INPUT. Return NULL_TREE if that cannot be determined. */
1051 ipa_get_jf_ancestor_result (struct ipa_jump_func *jfunc, tree input)
1053 gcc_checking_assert (TREE_CODE (input) != TREE_BINFO);
1054 if (TREE_CODE (input) == ADDR_EXPR)
1056 tree t = TREE_OPERAND (input, 0);
1057 t = build_ref_for_offset (EXPR_LOCATION (t), t,
1058 ipa_get_jf_ancestor_offset (jfunc), false,
1059 ptr_type_node, NULL, false);
1060 return build_fold_addr_expr (t);
1066 /* Determine whether JFUNC evaluates to a single known constant value and if
1067 so, return it. Otherwise return NULL. INFO describes the caller node or
1068 the one it is inlined to, so that pass-through jump functions can be
1072 ipa_value_from_jfunc (struct ipa_node_params *info, struct ipa_jump_func *jfunc)
1074 if (jfunc->type == IPA_JF_CONST)
1075 return ipa_get_jf_constant (jfunc);
1076 else if (jfunc->type == IPA_JF_PASS_THROUGH
1077 || jfunc->type == IPA_JF_ANCESTOR)
1082 if (jfunc->type == IPA_JF_PASS_THROUGH)
1083 idx = ipa_get_jf_pass_through_formal_id (jfunc);
1085 idx = ipa_get_jf_ancestor_formal_id (jfunc);
1087 if (info->ipcp_orig_node)
1088 input = info->known_csts[idx];
1091 ipcp_lattice<tree> *lat;
1094 || idx >= ipa_get_param_count (info))
1096 lat = ipa_get_scalar_lat (info, idx);
1097 if (!lat->is_single_const ())
1099 input = lat->values->value;
1105 if (jfunc->type == IPA_JF_PASS_THROUGH)
1106 return ipa_get_jf_pass_through_result (jfunc, input);
1108 return ipa_get_jf_ancestor_result (jfunc, input);
1114 /* Determie whether JFUNC evaluates to single known polymorphic context, given
1115 that INFO describes the caller node or the one it is inlined to, CS is the
1116 call graph edge corresponding to JFUNC and CSIDX index of the described
1119 ipa_polymorphic_call_context
1120 ipa_context_from_jfunc (ipa_node_params *info, cgraph_edge *cs, int csidx,
1121 ipa_jump_func *jfunc)
1123 ipa_edge_args *args = IPA_EDGE_REF (cs);
1124 ipa_polymorphic_call_context ctx;
1125 ipa_polymorphic_call_context *edge_ctx
1126 = cs ? ipa_get_ith_polymorhic_call_context (args, csidx) : NULL;
1128 if (edge_ctx && !edge_ctx->useless_p ())
1131 if (jfunc->type == IPA_JF_PASS_THROUGH
1132 || jfunc->type == IPA_JF_ANCESTOR)
1134 ipa_polymorphic_call_context srcctx;
1136 bool type_preserved = true;
1137 if (jfunc->type == IPA_JF_PASS_THROUGH)
1139 if (ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR)
1141 type_preserved = ipa_get_jf_pass_through_type_preserved (jfunc);
1142 srcidx = ipa_get_jf_pass_through_formal_id (jfunc);
1146 type_preserved = ipa_get_jf_ancestor_type_preserved (jfunc);
1147 srcidx = ipa_get_jf_ancestor_formal_id (jfunc);
1149 if (info->ipcp_orig_node)
1151 if (info->known_contexts.exists ())
1152 srcctx = info->known_contexts[srcidx];
1157 || srcidx >= ipa_get_param_count (info))
1159 ipcp_lattice<ipa_polymorphic_call_context> *lat;
1160 lat = ipa_get_poly_ctx_lat (info, srcidx);
1161 if (!lat->is_single_const ())
1163 srcctx = lat->values->value;
1165 if (srcctx.useless_p ())
1167 if (jfunc->type == IPA_JF_ANCESTOR)
1168 srcctx.offset_by (ipa_get_jf_ancestor_offset (jfunc));
1169 if (!type_preserved)
1170 srcctx.possible_dynamic_type_change (cs->in_polymorphic_cdtor);
1171 srcctx.combine_with (ctx);
1178 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
1179 bottom, not containing a variable component and without any known value at
1183 ipcp_verify_propagated_values (void)
1185 struct cgraph_node *node;
1187 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
1189 struct ipa_node_params *info = IPA_NODE_REF (node);
1190 int i, count = ipa_get_param_count (info);
1192 for (i = 0; i < count; i++)
1194 ipcp_lattice<tree> *lat = ipa_get_scalar_lat (info, i);
1197 && !lat->contains_variable
1198 && lat->values_count == 0)
1202 symtab_node::dump_table (dump_file);
1203 fprintf (dump_file, "\nIPA lattices after constant "
1204 "propagation, before gcc_unreachable:\n");
1205 print_all_lattices (dump_file, true, false);
1214 /* Return true iff X and Y should be considered equal values by IPA-CP. */
1217 values_equal_for_ipcp_p (tree x, tree y)
1219 gcc_checking_assert (x != NULL_TREE && y != NULL_TREE);
1224 if (TREE_CODE (x) == ADDR_EXPR
1225 && TREE_CODE (y) == ADDR_EXPR
1226 && TREE_CODE (TREE_OPERAND (x, 0)) == CONST_DECL
1227 && TREE_CODE (TREE_OPERAND (y, 0)) == CONST_DECL)
1228 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x, 0)),
1229 DECL_INITIAL (TREE_OPERAND (y, 0)), 0);
1231 return operand_equal_p (x, y, 0);
1234 /* Return true iff X and Y should be considered equal contexts by IPA-CP. */
1237 values_equal_for_ipcp_p (ipa_polymorphic_call_context x,
1238 ipa_polymorphic_call_context y)
1240 return x.equal_to (y);
1244 /* Add a new value source to the value represented by THIS, marking that a
1245 value comes from edge CS and (if the underlying jump function is a
1246 pass-through or an ancestor one) from a caller value SRC_VAL of a caller
1247 parameter described by SRC_INDEX. OFFSET is negative if the source was the
1248 scalar value of the parameter itself or the offset within an aggregate. */
1250 template <typename valtype>
1252 ipcp_value<valtype>::add_source (cgraph_edge *cs, ipcp_value *src_val,
1253 int src_idx, HOST_WIDE_INT offset)
1255 ipcp_value_source<valtype> *src;
1257 src = new (ipcp_sources_pool.allocate ()) ipcp_value_source<valtype>;
1258 src->offset = offset;
1261 src->index = src_idx;
1263 src->next = sources;
1267 /* Allocate a new ipcp_value holding a tree constant, initialize its value to
1268 SOURCE and clear all other fields. */
1270 static ipcp_value<tree> *
1271 allocate_and_init_ipcp_value (tree source)
1273 ipcp_value<tree> *val;
1275 val = ipcp_cst_values_pool.allocate ();
1276 memset (val, 0, sizeof (*val));
1277 val->value = source;
1281 /* Allocate a new ipcp_value holding a polymorphic context, initialize its
1282 value to SOURCE and clear all other fields. */
1284 static ipcp_value<ipa_polymorphic_call_context> *
1285 allocate_and_init_ipcp_value (ipa_polymorphic_call_context source)
1287 ipcp_value<ipa_polymorphic_call_context> *val;
1290 val = ipcp_poly_ctx_values_pool.allocate ();
1291 memset (val, 0, sizeof (*val));
1292 val->value = source;
1296 /* Try to add NEWVAL to LAT, potentially creating a new ipcp_value for it. CS,
1297 SRC_VAL SRC_INDEX and OFFSET are meant for add_source and have the same
1298 meaning. OFFSET -1 means the source is scalar and not a part of an
1301 template <typename valtype>
1303 ipcp_lattice<valtype>::add_value (valtype newval, cgraph_edge *cs,
1304 ipcp_value<valtype> *src_val,
1305 int src_idx, HOST_WIDE_INT offset)
1307 ipcp_value<valtype> *val;
1312 for (val = values; val; val = val->next)
1313 if (values_equal_for_ipcp_p (val->value, newval))
1315 if (ipa_edge_within_scc (cs))
1317 ipcp_value_source<valtype> *s;
1318 for (s = val->sources; s ; s = s->next)
1325 val->add_source (cs, src_val, src_idx, offset);
1329 if (values_count == PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE))
1331 /* We can only free sources, not the values themselves, because sources
1332 of other values in this SCC might point to them. */
1333 for (val = values; val; val = val->next)
1335 while (val->sources)
1337 ipcp_value_source<valtype> *src = val->sources;
1338 val->sources = src->next;
1339 ipcp_sources_pool.remove ((ipcp_value_source<tree>*)src);
1344 return set_to_bottom ();
1348 val = allocate_and_init_ipcp_value (newval);
1349 val->add_source (cs, src_val, src_idx, offset);
1355 /* Propagate values through a pass-through jump function JFUNC associated with
1356 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1357 is the index of the source parameter. */
1360 propagate_vals_accross_pass_through (cgraph_edge *cs,
1361 ipa_jump_func *jfunc,
1362 ipcp_lattice<tree> *src_lat,
1363 ipcp_lattice<tree> *dest_lat,
1366 ipcp_value<tree> *src_val;
1369 /* Do not create new values when propagating within an SCC because if there
1370 are arithmetic functions with circular dependencies, there is infinite
1371 number of them and we would just make lattices bottom. */
1372 if ((ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR)
1373 && ipa_edge_within_scc (cs))
1374 ret = dest_lat->set_contains_variable ();
1376 for (src_val = src_lat->values; src_val; src_val = src_val->next)
1378 tree cstval = ipa_get_jf_pass_through_result (jfunc, src_val->value);
1381 ret |= dest_lat->add_value (cstval, cs, src_val, src_idx);
1383 ret |= dest_lat->set_contains_variable ();
1389 /* Propagate values through an ancestor jump function JFUNC associated with
1390 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1391 is the index of the source parameter. */
1394 propagate_vals_accross_ancestor (struct cgraph_edge *cs,
1395 struct ipa_jump_func *jfunc,
1396 ipcp_lattice<tree> *src_lat,
1397 ipcp_lattice<tree> *dest_lat,
1400 ipcp_value<tree> *src_val;
1403 if (ipa_edge_within_scc (cs))
1404 return dest_lat->set_contains_variable ();
1406 for (src_val = src_lat->values; src_val; src_val = src_val->next)
1408 tree t = ipa_get_jf_ancestor_result (jfunc, src_val->value);
1411 ret |= dest_lat->add_value (t, cs, src_val, src_idx);
1413 ret |= dest_lat->set_contains_variable ();
1419 /* Propagate scalar values across jump function JFUNC that is associated with
1420 edge CS and put the values into DEST_LAT. */
1423 propagate_scalar_accross_jump_function (struct cgraph_edge *cs,
1424 struct ipa_jump_func *jfunc,
1425 ipcp_lattice<tree> *dest_lat)
1427 if (dest_lat->bottom)
1430 if (jfunc->type == IPA_JF_CONST)
1432 tree val = ipa_get_jf_constant (jfunc);
1433 return dest_lat->add_value (val, cs, NULL, 0);
1435 else if (jfunc->type == IPA_JF_PASS_THROUGH
1436 || jfunc->type == IPA_JF_ANCESTOR)
1438 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1439 ipcp_lattice<tree> *src_lat;
1443 if (jfunc->type == IPA_JF_PASS_THROUGH)
1444 src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
1446 src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
1448 src_lat = ipa_get_scalar_lat (caller_info, src_idx);
1449 if (src_lat->bottom)
1450 return dest_lat->set_contains_variable ();
1452 /* If we would need to clone the caller and cannot, do not propagate. */
1453 if (!ipcp_versionable_function_p (cs->caller)
1454 && (src_lat->contains_variable
1455 || (src_lat->values_count > 1)))
1456 return dest_lat->set_contains_variable ();
1458 if (jfunc->type == IPA_JF_PASS_THROUGH)
1459 ret = propagate_vals_accross_pass_through (cs, jfunc, src_lat,
1462 ret = propagate_vals_accross_ancestor (cs, jfunc, src_lat, dest_lat,
1465 if (src_lat->contains_variable)
1466 ret |= dest_lat->set_contains_variable ();
1471 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1472 use it for indirect inlining), we should propagate them too. */
1473 return dest_lat->set_contains_variable ();
1476 /* Propagate scalar values across jump function JFUNC that is associated with
1477 edge CS and describes argument IDX and put the values into DEST_LAT. */
1480 propagate_context_accross_jump_function (cgraph_edge *cs,
1481 ipa_jump_func *jfunc, int idx,
1482 ipcp_lattice<ipa_polymorphic_call_context> *dest_lat)
1484 ipa_edge_args *args = IPA_EDGE_REF (cs);
1485 if (dest_lat->bottom)
1488 bool added_sth = false;
1489 bool type_preserved = true;
1491 ipa_polymorphic_call_context edge_ctx, *edge_ctx_ptr
1492 = ipa_get_ith_polymorhic_call_context (args, idx);
1495 edge_ctx = *edge_ctx_ptr;
1497 if (jfunc->type == IPA_JF_PASS_THROUGH
1498 || jfunc->type == IPA_JF_ANCESTOR)
1500 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1502 ipcp_lattice<ipa_polymorphic_call_context> *src_lat;
1504 /* TODO: Once we figure out how to propagate speculations, it will
1505 probably be a good idea to switch to speculation if type_preserved is
1506 not set instead of punting. */
1507 if (jfunc->type == IPA_JF_PASS_THROUGH)
1509 if (ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR)
1511 type_preserved = ipa_get_jf_pass_through_type_preserved (jfunc);
1512 src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
1516 type_preserved = ipa_get_jf_ancestor_type_preserved (jfunc);
1517 src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
1520 src_lat = ipa_get_poly_ctx_lat (caller_info, src_idx);
1521 /* If we would need to clone the caller and cannot, do not propagate. */
1522 if (!ipcp_versionable_function_p (cs->caller)
1523 && (src_lat->contains_variable
1524 || (src_lat->values_count > 1)))
1527 ipcp_value<ipa_polymorphic_call_context> *src_val;
1528 for (src_val = src_lat->values; src_val; src_val = src_val->next)
1530 ipa_polymorphic_call_context cur = src_val->value;
1532 if (!type_preserved)
1533 cur.possible_dynamic_type_change (cs->in_polymorphic_cdtor);
1534 if (jfunc->type == IPA_JF_ANCESTOR)
1535 cur.offset_by (ipa_get_jf_ancestor_offset (jfunc));
1536 /* TODO: In cases we know how the context is going to be used,
1537 we can improve the result by passing proper OTR_TYPE. */
1538 cur.combine_with (edge_ctx);
1539 if (!cur.useless_p ())
1541 if (src_lat->contains_variable
1542 && !edge_ctx.equal_to (cur))
1543 ret |= dest_lat->set_contains_variable ();
1544 ret |= dest_lat->add_value (cur, cs, src_val, src_idx);
1554 if (!edge_ctx.useless_p ())
1555 ret |= dest_lat->add_value (edge_ctx, cs);
1557 ret |= dest_lat->set_contains_variable ();
1563 /* Propagate alignments across jump function JFUNC that is associated with
1564 edge CS and update DEST_LAT accordingly. */
1567 propagate_alignment_accross_jump_function (cgraph_edge *cs,
1568 ipa_jump_func *jfunc,
1569 ipcp_alignment_lattice *dest_lat)
1571 if (dest_lat->bottom_p ())
1574 if (jfunc->type == IPA_JF_PASS_THROUGH
1575 || jfunc->type == IPA_JF_ANCESTOR)
1577 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1578 HOST_WIDE_INT offset = 0;
1581 if (jfunc->type == IPA_JF_PASS_THROUGH)
1583 enum tree_code op = ipa_get_jf_pass_through_operation (jfunc);
1586 if (op != POINTER_PLUS_EXPR
1588 return dest_lat->set_to_bottom ();
1589 tree operand = ipa_get_jf_pass_through_operand (jfunc);
1590 if (!tree_fits_shwi_p (operand))
1591 return dest_lat->set_to_bottom ();
1592 offset = tree_to_shwi (operand);
1594 src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
1598 src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
1599 offset = ipa_get_jf_ancestor_offset (jfunc) / BITS_PER_UNIT;
1602 struct ipcp_param_lattices *src_lats;
1603 src_lats = ipa_get_parm_lattices (caller_info, src_idx);
1604 return dest_lat->meet_with (src_lats->alignment, offset);
1608 if (jfunc->alignment.known)
1609 return dest_lat->meet_with (jfunc->alignment.align,
1610 jfunc->alignment.misalign);
1612 return dest_lat->set_to_bottom ();
1616 /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
1617 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
1618 other cases, return false). If there are no aggregate items, set
1619 aggs_by_ref to NEW_AGGS_BY_REF. */
1622 set_check_aggs_by_ref (struct ipcp_param_lattices *dest_plats,
1623 bool new_aggs_by_ref)
1625 if (dest_plats->aggs)
1627 if (dest_plats->aggs_by_ref != new_aggs_by_ref)
1629 set_agg_lats_to_bottom (dest_plats);
1634 dest_plats->aggs_by_ref = new_aggs_by_ref;
1638 /* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
1639 already existing lattice for the given OFFSET and SIZE, marking all skipped
1640 lattices as containing variable and checking for overlaps. If there is no
1641 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
1642 it with offset, size and contains_variable to PRE_EXISTING, and return true,
1643 unless there are too many already. If there are two many, return false. If
1644 there are overlaps turn whole DEST_PLATS to bottom and return false. If any
1645 skipped lattices were newly marked as containing variable, set *CHANGE to
1649 merge_agg_lats_step (struct ipcp_param_lattices *dest_plats,
1650 HOST_WIDE_INT offset, HOST_WIDE_INT val_size,
1651 struct ipcp_agg_lattice ***aglat,
1652 bool pre_existing, bool *change)
1654 gcc_checking_assert (offset >= 0);
1656 while (**aglat && (**aglat)->offset < offset)
1658 if ((**aglat)->offset + (**aglat)->size > offset)
1660 set_agg_lats_to_bottom (dest_plats);
1663 *change |= (**aglat)->set_contains_variable ();
1664 *aglat = &(**aglat)->next;
1667 if (**aglat && (**aglat)->offset == offset)
1669 if ((**aglat)->size != val_size
1671 && (**aglat)->next->offset < offset + val_size))
1673 set_agg_lats_to_bottom (dest_plats);
1676 gcc_checking_assert (!(**aglat)->next
1677 || (**aglat)->next->offset >= offset + val_size);
1682 struct ipcp_agg_lattice *new_al;
1684 if (**aglat && (**aglat)->offset < offset + val_size)
1686 set_agg_lats_to_bottom (dest_plats);
1689 if (dest_plats->aggs_count == PARAM_VALUE (PARAM_IPA_MAX_AGG_ITEMS))
1691 dest_plats->aggs_count++;
1692 new_al = ipcp_agg_lattice_pool.allocate ();
1693 memset (new_al, 0, sizeof (*new_al));
1695 new_al->offset = offset;
1696 new_al->size = val_size;
1697 new_al->contains_variable = pre_existing;
1699 new_al->next = **aglat;
1705 /* Set all AGLAT and all other aggregate lattices reachable by next pointers as
1706 containing an unknown value. */
1709 set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice *aglat)
1714 ret |= aglat->set_contains_variable ();
1715 aglat = aglat->next;
1720 /* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
1721 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source
1722 parameter used for lattice value sources. Return true if DEST_PLATS changed
1726 merge_aggregate_lattices (struct cgraph_edge *cs,
1727 struct ipcp_param_lattices *dest_plats,
1728 struct ipcp_param_lattices *src_plats,
1729 int src_idx, HOST_WIDE_INT offset_delta)
1731 bool pre_existing = dest_plats->aggs != NULL;
1732 struct ipcp_agg_lattice **dst_aglat;
1735 if (set_check_aggs_by_ref (dest_plats, src_plats->aggs_by_ref))
1737 if (src_plats->aggs_bottom)
1738 return set_agg_lats_contain_variable (dest_plats);
1739 if (src_plats->aggs_contain_variable)
1740 ret |= set_agg_lats_contain_variable (dest_plats);
1741 dst_aglat = &dest_plats->aggs;
1743 for (struct ipcp_agg_lattice *src_aglat = src_plats->aggs;
1745 src_aglat = src_aglat->next)
1747 HOST_WIDE_INT new_offset = src_aglat->offset - offset_delta;
1751 if (merge_agg_lats_step (dest_plats, new_offset, src_aglat->size,
1752 &dst_aglat, pre_existing, &ret))
1754 struct ipcp_agg_lattice *new_al = *dst_aglat;
1756 dst_aglat = &(*dst_aglat)->next;
1757 if (src_aglat->bottom)
1759 ret |= new_al->set_contains_variable ();
1762 if (src_aglat->contains_variable)
1763 ret |= new_al->set_contains_variable ();
1764 for (ipcp_value<tree> *val = src_aglat->values;
1767 ret |= new_al->add_value (val->value, cs, val, src_idx,
1770 else if (dest_plats->aggs_bottom)
1773 ret |= set_chain_of_aglats_contains_variable (*dst_aglat);
1777 /* Determine whether there is anything to propagate FROM SRC_PLATS through a
1778 pass-through JFUNC and if so, whether it has conform and conforms to the
1779 rules about propagating values passed by reference. */
1782 agg_pass_through_permissible_p (struct ipcp_param_lattices *src_plats,
1783 struct ipa_jump_func *jfunc)
1785 return src_plats->aggs
1786 && (!src_plats->aggs_by_ref
1787 || ipa_get_jf_pass_through_agg_preserved (jfunc));
1790 /* Propagate scalar values across jump function JFUNC that is associated with
1791 edge CS and put the values into DEST_LAT. */
1794 propagate_aggs_accross_jump_function (struct cgraph_edge *cs,
1795 struct ipa_jump_func *jfunc,
1796 struct ipcp_param_lattices *dest_plats)
1800 if (dest_plats->aggs_bottom)
1803 if (jfunc->type == IPA_JF_PASS_THROUGH
1804 && ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
1806 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1807 int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
1808 struct ipcp_param_lattices *src_plats;
1810 src_plats = ipa_get_parm_lattices (caller_info, src_idx);
1811 if (agg_pass_through_permissible_p (src_plats, jfunc))
1813 /* Currently we do not produce clobber aggregate jump
1814 functions, replace with merging when we do. */
1815 gcc_assert (!jfunc->agg.items);
1816 ret |= merge_aggregate_lattices (cs, dest_plats, src_plats,
1820 ret |= set_agg_lats_contain_variable (dest_plats);
1822 else if (jfunc->type == IPA_JF_ANCESTOR
1823 && ipa_get_jf_ancestor_agg_preserved (jfunc))
1825 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1826 int src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
1827 struct ipcp_param_lattices *src_plats;
1829 src_plats = ipa_get_parm_lattices (caller_info, src_idx);
1830 if (src_plats->aggs && src_plats->aggs_by_ref)
1832 /* Currently we do not produce clobber aggregate jump
1833 functions, replace with merging when we do. */
1834 gcc_assert (!jfunc->agg.items);
1835 ret |= merge_aggregate_lattices (cs, dest_plats, src_plats, src_idx,
1836 ipa_get_jf_ancestor_offset (jfunc));
1838 else if (!src_plats->aggs_by_ref)
1839 ret |= set_agg_lats_to_bottom (dest_plats);
1841 ret |= set_agg_lats_contain_variable (dest_plats);
1843 else if (jfunc->agg.items)
1845 bool pre_existing = dest_plats->aggs != NULL;
1846 struct ipcp_agg_lattice **aglat = &dest_plats->aggs;
1847 struct ipa_agg_jf_item *item;
1850 if (set_check_aggs_by_ref (dest_plats, jfunc->agg.by_ref))
1853 FOR_EACH_VEC_ELT (*jfunc->agg.items, i, item)
1855 HOST_WIDE_INT val_size;
1857 if (item->offset < 0)
1859 gcc_checking_assert (is_gimple_ip_invariant (item->value));
1860 val_size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (item->value)));
1862 if (merge_agg_lats_step (dest_plats, item->offset, val_size,
1863 &aglat, pre_existing, &ret))
1865 ret |= (*aglat)->add_value (item->value, cs, NULL, 0, 0);
1866 aglat = &(*aglat)->next;
1868 else if (dest_plats->aggs_bottom)
1872 ret |= set_chain_of_aglats_contains_variable (*aglat);
1875 ret |= set_agg_lats_contain_variable (dest_plats);
1880 /* Return true if on the way cfrom CS->caller to the final (non-alias and
1881 non-thunk) destination, the call passes through a thunk. */
1884 call_passes_through_thunk_p (cgraph_edge *cs)
1886 cgraph_node *alias_or_thunk = cs->callee;
1887 while (alias_or_thunk->alias)
1888 alias_or_thunk = alias_or_thunk->get_alias_target ();
1889 return alias_or_thunk->thunk.thunk_p;
1892 /* Propagate constants from the caller to the callee of CS. INFO describes the
1896 propagate_constants_accross_call (struct cgraph_edge *cs)
1898 struct ipa_node_params *callee_info;
1899 enum availability availability;
1900 cgraph_node *callee;
1901 struct ipa_edge_args *args;
1903 int i, args_count, parms_count;
1905 callee = cs->callee->function_symbol (&availability);
1906 if (!callee->definition)
1908 gcc_checking_assert (callee->has_gimple_body_p ());
1909 callee_info = IPA_NODE_REF (callee);
1911 args = IPA_EDGE_REF (cs);
1912 args_count = ipa_get_cs_argument_count (args);
1913 parms_count = ipa_get_param_count (callee_info);
1914 if (parms_count == 0)
1917 /* No propagation through instrumentation thunks is available yet.
1918 It should be possible with proper mapping of call args and
1919 instrumented callee params in the propagation loop below. But
1920 this case mostly occurs when legacy code calls instrumented code
1921 and it is not a primary target for optimizations.
1922 We detect instrumentation thunks in aliases and thunks chain by
1923 checking instrumentation_clone flag for chain source and target.
1924 Going through instrumentation thunks we always have it changed
1925 from 0 to 1 and all other nodes do not change it. */
1926 if (!cs->callee->instrumentation_clone
1927 && callee->instrumentation_clone)
1929 for (i = 0; i < parms_count; i++)
1930 ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info,
1935 /* If this call goes through a thunk we must not propagate to the first (0th)
1936 parameter. However, we might need to uncover a thunk from below a series
1937 of aliases first. */
1938 if (call_passes_through_thunk_p (cs))
1940 ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info,
1947 for (; (i < args_count) && (i < parms_count); i++)
1949 struct ipa_jump_func *jump_func = ipa_get_ith_jump_func (args, i);
1950 struct ipcp_param_lattices *dest_plats;
1952 dest_plats = ipa_get_parm_lattices (callee_info, i);
1953 if (availability == AVAIL_INTERPOSABLE)
1954 ret |= set_all_contains_variable (dest_plats);
1957 ret |= propagate_scalar_accross_jump_function (cs, jump_func,
1958 &dest_plats->itself);
1959 ret |= propagate_context_accross_jump_function (cs, jump_func, i,
1960 &dest_plats->ctxlat);
1961 ret |= propagate_alignment_accross_jump_function (cs, jump_func,
1962 &dest_plats->alignment);
1963 ret |= propagate_aggs_accross_jump_function (cs, jump_func,
1967 for (; i < parms_count; i++)
1968 ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info, i));
1973 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
1974 KNOWN_CONTEXTS, KNOWN_AGGS or AGG_REPS return the destination. The latter
1975 three can be NULL. If AGG_REPS is not NULL, KNOWN_AGGS is ignored. */
1978 ipa_get_indirect_edge_target_1 (struct cgraph_edge *ie,
1979 vec<tree> known_csts,
1980 vec<ipa_polymorphic_call_context> known_contexts,
1981 vec<ipa_agg_jump_function_p> known_aggs,
1982 struct ipa_agg_replacement_value *agg_reps,
1985 int param_index = ie->indirect_info->param_index;
1986 HOST_WIDE_INT anc_offset;
1990 *speculative = false;
1992 if (param_index == -1
1993 || known_csts.length () <= (unsigned int) param_index)
1996 if (!ie->indirect_info->polymorphic)
2000 if (ie->indirect_info->agg_contents)
2007 if (agg_reps->index == param_index
2008 && agg_reps->offset == ie->indirect_info->offset
2009 && agg_reps->by_ref == ie->indirect_info->by_ref)
2011 t = agg_reps->value;
2014 agg_reps = agg_reps->next;
2017 else if (known_aggs.length () > (unsigned int) param_index)
2019 struct ipa_agg_jump_function *agg;
2020 agg = known_aggs[param_index];
2021 t = ipa_find_agg_cst_for_param (agg, ie->indirect_info->offset,
2022 ie->indirect_info->by_ref);
2028 t = known_csts[param_index];
2031 TREE_CODE (t) == ADDR_EXPR
2032 && TREE_CODE (TREE_OPERAND (t, 0)) == FUNCTION_DECL)
2033 return TREE_OPERAND (t, 0);
2038 if (!opt_for_fn (ie->caller->decl, flag_devirtualize))
2041 gcc_assert (!ie->indirect_info->agg_contents);
2042 anc_offset = ie->indirect_info->offset;
2046 /* Try to work out value of virtual table pointer value in replacemnets. */
2047 if (!t && agg_reps && !ie->indirect_info->by_ref)
2051 if (agg_reps->index == param_index
2052 && agg_reps->offset == ie->indirect_info->offset
2053 && agg_reps->by_ref)
2055 t = agg_reps->value;
2058 agg_reps = agg_reps->next;
2062 /* Try to work out value of virtual table pointer value in known
2063 aggregate values. */
2064 if (!t && known_aggs.length () > (unsigned int) param_index
2065 && !ie->indirect_info->by_ref)
2067 struct ipa_agg_jump_function *agg;
2068 agg = known_aggs[param_index];
2069 t = ipa_find_agg_cst_for_param (agg, ie->indirect_info->offset,
2073 /* If we found the virtual table pointer, lookup the target. */
2077 unsigned HOST_WIDE_INT offset;
2078 if (vtable_pointer_value_to_vtable (t, &vtable, &offset))
2081 target = gimple_get_virt_method_for_vtable (ie->indirect_info->otr_token,
2082 vtable, offset, &can_refer);
2086 || (TREE_CODE (TREE_TYPE (target)) == FUNCTION_TYPE
2087 && DECL_FUNCTION_CODE (target) == BUILT_IN_UNREACHABLE)
2088 || !possible_polymorphic_call_target_p
2089 (ie, cgraph_node::get (target)))
2091 /* Do not speculate builtin_unreachable, it is stupid! */
2092 if (ie->indirect_info->vptr_changed)
2094 target = ipa_impossible_devirt_target (ie, target);
2096 *speculative = ie->indirect_info->vptr_changed;
2103 /* Do we know the constant value of pointer? */
2105 t = known_csts[param_index];
2107 gcc_checking_assert (!t || TREE_CODE (t) != TREE_BINFO);
2109 ipa_polymorphic_call_context context;
2110 if (known_contexts.length () > (unsigned int) param_index)
2112 context = known_contexts[param_index];
2113 context.offset_by (anc_offset);
2114 if (ie->indirect_info->vptr_changed)
2115 context.possible_dynamic_type_change (ie->in_polymorphic_cdtor,
2116 ie->indirect_info->otr_type);
2119 ipa_polymorphic_call_context ctx2 = ipa_polymorphic_call_context
2120 (t, ie->indirect_info->otr_type, anc_offset);
2121 if (!ctx2.useless_p ())
2122 context.combine_with (ctx2, ie->indirect_info->otr_type);
2127 context = ipa_polymorphic_call_context (t, ie->indirect_info->otr_type,
2129 if (ie->indirect_info->vptr_changed)
2130 context.possible_dynamic_type_change (ie->in_polymorphic_cdtor,
2131 ie->indirect_info->otr_type);
2136 vec <cgraph_node *>targets;
2139 targets = possible_polymorphic_call_targets
2140 (ie->indirect_info->otr_type,
2141 ie->indirect_info->otr_token,
2143 if (!final || targets.length () > 1)
2145 struct cgraph_node *node;
2148 if (!opt_for_fn (ie->caller->decl, flag_devirtualize_speculatively)
2149 || ie->speculative || !ie->maybe_hot_p ())
2151 node = try_speculative_devirtualization (ie->indirect_info->otr_type,
2152 ie->indirect_info->otr_token,
2156 *speculative = true;
2157 target = node->decl;
2164 *speculative = false;
2165 if (targets.length () == 1)
2166 target = targets[0]->decl;
2168 target = ipa_impossible_devirt_target (ie, NULL_TREE);
2171 if (target && !possible_polymorphic_call_target_p (ie,
2172 cgraph_node::get (target)))
2176 target = ipa_impossible_devirt_target (ie, target);
2183 /* If an indirect edge IE can be turned into a direct one based on KNOWN_CSTS,
2184 KNOWN_CONTEXTS (which can be vNULL) or KNOWN_AGGS (which also can be vNULL)
2185 return the destination. */
2188 ipa_get_indirect_edge_target (struct cgraph_edge *ie,
2189 vec<tree> known_csts,
2190 vec<ipa_polymorphic_call_context> known_contexts,
2191 vec<ipa_agg_jump_function_p> known_aggs,
2194 return ipa_get_indirect_edge_target_1 (ie, known_csts, known_contexts,
2195 known_aggs, NULL, speculative);
2198 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
2199 and KNOWN_CONTEXTS. */
2202 devirtualization_time_bonus (struct cgraph_node *node,
2203 vec<tree> known_csts,
2204 vec<ipa_polymorphic_call_context> known_contexts,
2205 vec<ipa_agg_jump_function_p> known_aggs)
2207 struct cgraph_edge *ie;
2210 for (ie = node->indirect_calls; ie; ie = ie->next_callee)
2212 struct cgraph_node *callee;
2213 struct inline_summary *isummary;
2214 enum availability avail;
2218 target = ipa_get_indirect_edge_target (ie, known_csts, known_contexts,
2219 known_aggs, &speculative);
2223 /* Only bare minimum benefit for clearly un-inlineable targets. */
2225 callee = cgraph_node::get (target);
2226 if (!callee || !callee->definition)
2228 callee = callee->function_symbol (&avail);
2229 if (avail < AVAIL_AVAILABLE)
2231 isummary = inline_summaries->get (callee);
2232 if (!isummary->inlinable)
2235 /* FIXME: The values below need re-considering and perhaps also
2236 integrating into the cost metrics, at lest in some very basic way. */
2237 if (isummary->size <= MAX_INLINE_INSNS_AUTO / 4)
2238 res += 31 / ((int)speculative + 1);
2239 else if (isummary->size <= MAX_INLINE_INSNS_AUTO / 2)
2240 res += 15 / ((int)speculative + 1);
2241 else if (isummary->size <= MAX_INLINE_INSNS_AUTO
2242 || DECL_DECLARED_INLINE_P (callee->decl))
2243 res += 7 / ((int)speculative + 1);
2249 /* Return time bonus incurred because of HINTS. */
2252 hint_time_bonus (inline_hints hints)
2255 if (hints & (INLINE_HINT_loop_iterations | INLINE_HINT_loop_stride))
2256 result += PARAM_VALUE (PARAM_IPA_CP_LOOP_HINT_BONUS);
2257 if (hints & INLINE_HINT_array_index)
2258 result += PARAM_VALUE (PARAM_IPA_CP_ARRAY_INDEX_HINT_BONUS);
2262 /* If there is a reason to penalize the function described by INFO in the
2263 cloning goodness evaluation, do so. */
2265 static inline int64_t
2266 incorporate_penalties (ipa_node_params *info, int64_t evaluation)
2268 if (info->node_within_scc)
2269 evaluation = (evaluation
2270 * (100 - PARAM_VALUE (PARAM_IPA_CP_RECURSION_PENALTY))) / 100;
2272 if (info->node_calling_single_call)
2273 evaluation = (evaluation
2274 * (100 - PARAM_VALUE (PARAM_IPA_CP_SINGLE_CALL_PENALTY)))
2280 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
2281 and SIZE_COST and with the sum of frequencies of incoming edges to the
2282 potential new clone in FREQUENCIES. */
2285 good_cloning_opportunity_p (struct cgraph_node *node, int time_benefit,
2286 int freq_sum, gcov_type count_sum, int size_cost)
2288 if (time_benefit == 0
2289 || !opt_for_fn (node->decl, flag_ipa_cp_clone)
2290 || node->optimize_for_size_p ())
2293 gcc_assert (size_cost > 0);
2295 struct ipa_node_params *info = IPA_NODE_REF (node);
2298 int factor = (count_sum * 1000) / max_count;
2299 int64_t evaluation = (((int64_t) time_benefit * factor)
2301 evaluation = incorporate_penalties (info, evaluation);
2303 if (dump_file && (dump_flags & TDF_DETAILS))
2304 fprintf (dump_file, " good_cloning_opportunity_p (time: %i, "
2305 "size: %i, count_sum: " HOST_WIDE_INT_PRINT_DEC
2306 "%s%s) -> evaluation: " "%" PRId64
2307 ", threshold: %i\n",
2308 time_benefit, size_cost, (HOST_WIDE_INT) count_sum,
2309 info->node_within_scc ? ", scc" : "",
2310 info->node_calling_single_call ? ", single_call" : "",
2311 evaluation, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD));
2313 return evaluation >= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD);
2317 int64_t evaluation = (((int64_t) time_benefit * freq_sum)
2319 evaluation = incorporate_penalties (info, evaluation);
2321 if (dump_file && (dump_flags & TDF_DETAILS))
2322 fprintf (dump_file, " good_cloning_opportunity_p (time: %i, "
2323 "size: %i, freq_sum: %i%s%s) -> evaluation: "
2324 "%" PRId64 ", threshold: %i\n",
2325 time_benefit, size_cost, freq_sum,
2326 info->node_within_scc ? ", scc" : "",
2327 info->node_calling_single_call ? ", single_call" : "",
2328 evaluation, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD));
2330 return evaluation >= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD);
2334 /* Return all context independent values from aggregate lattices in PLATS in a
2335 vector. Return NULL if there are none. */
2337 static vec<ipa_agg_jf_item, va_gc> *
2338 context_independent_aggregate_values (struct ipcp_param_lattices *plats)
2340 vec<ipa_agg_jf_item, va_gc> *res = NULL;
2342 if (plats->aggs_bottom
2343 || plats->aggs_contain_variable
2344 || plats->aggs_count == 0)
2347 for (struct ipcp_agg_lattice *aglat = plats->aggs;
2349 aglat = aglat->next)
2350 if (aglat->is_single_const ())
2352 struct ipa_agg_jf_item item;
2353 item.offset = aglat->offset;
2354 item.value = aglat->values->value;
2355 vec_safe_push (res, item);
2360 /* Allocate KNOWN_CSTS, KNOWN_CONTEXTS and, if non-NULL, KNOWN_AGGS and
2361 populate them with values of parameters that are known independent of the
2362 context. INFO describes the function. If REMOVABLE_PARAMS_COST is
2363 non-NULL, the movement cost of all removable parameters will be stored in
2367 gather_context_independent_values (struct ipa_node_params *info,
2368 vec<tree> *known_csts,
2369 vec<ipa_polymorphic_call_context>
2371 vec<ipa_agg_jump_function> *known_aggs,
2372 int *removable_params_cost)
2374 int i, count = ipa_get_param_count (info);
2377 known_csts->create (0);
2378 known_contexts->create (0);
2379 known_csts->safe_grow_cleared (count);
2380 known_contexts->safe_grow_cleared (count);
2383 known_aggs->create (0);
2384 known_aggs->safe_grow_cleared (count);
2387 if (removable_params_cost)
2388 *removable_params_cost = 0;
2390 for (i = 0; i < count ; i++)
2392 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
2393 ipcp_lattice<tree> *lat = &plats->itself;
2395 if (lat->is_single_const ())
2397 ipcp_value<tree> *val = lat->values;
2398 gcc_checking_assert (TREE_CODE (val->value) != TREE_BINFO);
2399 (*known_csts)[i] = val->value;
2400 if (removable_params_cost)
2401 *removable_params_cost
2402 += estimate_move_cost (TREE_TYPE (val->value), false);
2405 else if (removable_params_cost
2406 && !ipa_is_param_used (info, i))
2407 *removable_params_cost
2408 += ipa_get_param_move_cost (info, i);
2410 if (!ipa_is_param_used (info, i))
2413 ipcp_lattice<ipa_polymorphic_call_context> *ctxlat = &plats->ctxlat;
2414 /* Do not account known context as reason for cloning. We can see
2415 if it permits devirtualization. */
2416 if (ctxlat->is_single_const ())
2417 (*known_contexts)[i] = ctxlat->values->value;
2421 vec<ipa_agg_jf_item, va_gc> *agg_items;
2422 struct ipa_agg_jump_function *ajf;
2424 agg_items = context_independent_aggregate_values (plats);
2425 ajf = &(*known_aggs)[i];
2426 ajf->items = agg_items;
2427 ajf->by_ref = plats->aggs_by_ref;
2428 ret |= agg_items != NULL;
2435 /* The current interface in ipa-inline-analysis requires a pointer vector.
2438 FIXME: That interface should be re-worked, this is slightly silly. Still,
2439 I'd like to discuss how to change it first and this demonstrates the
2442 static vec<ipa_agg_jump_function_p>
2443 agg_jmp_p_vec_for_t_vec (vec<ipa_agg_jump_function> known_aggs)
2445 vec<ipa_agg_jump_function_p> ret;
2446 struct ipa_agg_jump_function *ajf;
2449 ret.create (known_aggs.length ());
2450 FOR_EACH_VEC_ELT (known_aggs, i, ajf)
2451 ret.quick_push (ajf);
2455 /* Perform time and size measurement of NODE with the context given in
2456 KNOWN_CSTS, KNOWN_CONTEXTS and KNOWN_AGGS, calculate the benefit and cost
2457 given BASE_TIME of the node without specialization, REMOVABLE_PARAMS_COST of
2458 all context-independent removable parameters and EST_MOVE_COST of estimated
2459 movement of the considered parameter and store it into VAL. */
2462 perform_estimation_of_a_value (cgraph_node *node, vec<tree> known_csts,
2463 vec<ipa_polymorphic_call_context> known_contexts,
2464 vec<ipa_agg_jump_function_p> known_aggs_ptrs,
2465 int base_time, int removable_params_cost,
2466 int est_move_cost, ipcp_value_base *val)
2468 int time, size, time_benefit;
2471 estimate_ipcp_clone_size_and_time (node, known_csts, known_contexts,
2472 known_aggs_ptrs, &size, &time,
2474 time_benefit = base_time - time
2475 + devirtualization_time_bonus (node, known_csts, known_contexts,
2477 + hint_time_bonus (hints)
2478 + removable_params_cost + est_move_cost;
2480 gcc_checking_assert (size >=0);
2481 /* The inliner-heuristics based estimates may think that in certain
2482 contexts some functions do not have any size at all but we want
2483 all specializations to have at least a tiny cost, not least not to
2488 val->local_time_benefit = time_benefit;
2489 val->local_size_cost = size;
2492 /* Iterate over known values of parameters of NODE and estimate the local
2493 effects in terms of time and size they have. */
2496 estimate_local_effects (struct cgraph_node *node)
2498 struct ipa_node_params *info = IPA_NODE_REF (node);
2499 int i, count = ipa_get_param_count (info);
2500 vec<tree> known_csts;
2501 vec<ipa_polymorphic_call_context> known_contexts;
2502 vec<ipa_agg_jump_function> known_aggs;
2503 vec<ipa_agg_jump_function_p> known_aggs_ptrs;
2505 int base_time = inline_summaries->get (node)->time;
2506 int removable_params_cost;
2508 if (!count || !ipcp_versionable_function_p (node))
2511 if (dump_file && (dump_flags & TDF_DETAILS))
2512 fprintf (dump_file, "\nEstimating effects for %s/%i, base_time: %i.\n",
2513 node->name (), node->order, base_time);
2515 always_const = gather_context_independent_values (info, &known_csts,
2516 &known_contexts, &known_aggs,
2517 &removable_params_cost);
2518 known_aggs_ptrs = agg_jmp_p_vec_for_t_vec (known_aggs);
2519 int devirt_bonus = devirtualization_time_bonus (node, known_csts,
2520 known_contexts, known_aggs_ptrs);
2521 if (always_const || devirt_bonus
2522 || (removable_params_cost && node->local.can_change_signature))
2524 struct caller_statistics stats;
2528 init_caller_stats (&stats);
2529 node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats,
2531 estimate_ipcp_clone_size_and_time (node, known_csts, known_contexts,
2532 known_aggs_ptrs, &size, &time, &hints);
2533 time -= devirt_bonus;
2534 time -= hint_time_bonus (hints);
2535 time -= removable_params_cost;
2536 size -= stats.n_calls * removable_params_cost;
2539 fprintf (dump_file, " - context independent values, size: %i, "
2540 "time_benefit: %i\n", size, base_time - time);
2542 if (size <= 0 || node->local.local)
2544 info->do_clone_for_all_contexts = true;
2548 fprintf (dump_file, " Decided to specialize for all "
2549 "known contexts, code not going to grow.\n");
2551 else if (good_cloning_opportunity_p (node, base_time - time,
2552 stats.freq_sum, stats.count_sum,
2555 if (size + overall_size <= max_new_size)
2557 info->do_clone_for_all_contexts = true;
2559 overall_size += size;
2562 fprintf (dump_file, " Decided to specialize for all "
2563 "known contexts, growth deemed beneficial.\n");
2565 else if (dump_file && (dump_flags & TDF_DETAILS))
2566 fprintf (dump_file, " Not cloning for all contexts because "
2567 "max_new_size would be reached with %li.\n",
2568 size + overall_size);
2570 else if (dump_file && (dump_flags & TDF_DETAILS))
2571 fprintf (dump_file, " Not cloning for all contexts because "
2572 "!good_cloning_opportunity_p.\n");
2576 for (i = 0; i < count ; i++)
2578 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
2579 ipcp_lattice<tree> *lat = &plats->itself;
2580 ipcp_value<tree> *val;
2587 for (val = lat->values; val; val = val->next)
2589 gcc_checking_assert (TREE_CODE (val->value) != TREE_BINFO);
2590 known_csts[i] = val->value;
2592 int emc = estimate_move_cost (TREE_TYPE (val->value), true);
2593 perform_estimation_of_a_value (node, known_csts, known_contexts,
2594 known_aggs_ptrs, base_time,
2595 removable_params_cost, emc, val);
2597 if (dump_file && (dump_flags & TDF_DETAILS))
2599 fprintf (dump_file, " - estimates for value ");
2600 print_ipcp_constant_value (dump_file, val->value);
2601 fprintf (dump_file, " for ");
2602 ipa_dump_param (dump_file, info, i);
2603 fprintf (dump_file, ": time_benefit: %i, size: %i\n",
2604 val->local_time_benefit, val->local_size_cost);
2607 known_csts[i] = NULL_TREE;
2610 for (i = 0; i < count; i++)
2612 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
2614 if (!plats->virt_call)
2617 ipcp_lattice<ipa_polymorphic_call_context> *ctxlat = &plats->ctxlat;
2618 ipcp_value<ipa_polymorphic_call_context> *val;
2622 || !known_contexts[i].useless_p ())
2625 for (val = ctxlat->values; val; val = val->next)
2627 known_contexts[i] = val->value;
2628 perform_estimation_of_a_value (node, known_csts, known_contexts,
2629 known_aggs_ptrs, base_time,
2630 removable_params_cost, 0, val);
2632 if (dump_file && (dump_flags & TDF_DETAILS))
2634 fprintf (dump_file, " - estimates for polymorphic context ");
2635 print_ipcp_constant_value (dump_file, val->value);
2636 fprintf (dump_file, " for ");
2637 ipa_dump_param (dump_file, info, i);
2638 fprintf (dump_file, ": time_benefit: %i, size: %i\n",
2639 val->local_time_benefit, val->local_size_cost);
2642 known_contexts[i] = ipa_polymorphic_call_context ();
2645 for (i = 0; i < count ; i++)
2647 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
2648 struct ipa_agg_jump_function *ajf;
2649 struct ipcp_agg_lattice *aglat;
2651 if (plats->aggs_bottom || !plats->aggs)
2654 ajf = &known_aggs[i];
2655 for (aglat = plats->aggs; aglat; aglat = aglat->next)
2657 ipcp_value<tree> *val;
2658 if (aglat->bottom || !aglat->values
2659 /* If the following is true, the one value is in known_aggs. */
2660 || (!plats->aggs_contain_variable
2661 && aglat->is_single_const ()))
2664 for (val = aglat->values; val; val = val->next)
2666 struct ipa_agg_jf_item item;
2668 item.offset = aglat->offset;
2669 item.value = val->value;
2670 vec_safe_push (ajf->items, item);
2672 perform_estimation_of_a_value (node, known_csts, known_contexts,
2673 known_aggs_ptrs, base_time,
2674 removable_params_cost, 0, val);
2676 if (dump_file && (dump_flags & TDF_DETAILS))
2678 fprintf (dump_file, " - estimates for value ");
2679 print_ipcp_constant_value (dump_file, val->value);
2680 fprintf (dump_file, " for ");
2681 ipa_dump_param (dump_file, info, i);
2682 fprintf (dump_file, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
2683 "]: time_benefit: %i, size: %i\n",
2684 plats->aggs_by_ref ? "ref " : "",
2686 val->local_time_benefit, val->local_size_cost);
2694 for (i = 0; i < count ; i++)
2695 vec_free (known_aggs[i].items);
2697 known_csts.release ();
2698 known_contexts.release ();
2699 known_aggs.release ();
2700 known_aggs_ptrs.release ();
2704 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
2705 topological sort of values. */
2707 template <typename valtype>
2709 value_topo_info<valtype>::add_val (ipcp_value<valtype> *cur_val)
2711 ipcp_value_source<valtype> *src;
2717 cur_val->dfs = dfs_counter;
2718 cur_val->low_link = dfs_counter;
2720 cur_val->topo_next = stack;
2722 cur_val->on_stack = true;
2724 for (src = cur_val->sources; src; src = src->next)
2727 if (src->val->dfs == 0)
2730 if (src->val->low_link < cur_val->low_link)
2731 cur_val->low_link = src->val->low_link;
2733 else if (src->val->on_stack
2734 && src->val->dfs < cur_val->low_link)
2735 cur_val->low_link = src->val->dfs;
2738 if (cur_val->dfs == cur_val->low_link)
2740 ipcp_value<valtype> *v, *scc_list = NULL;
2745 stack = v->topo_next;
2746 v->on_stack = false;
2748 v->scc_next = scc_list;
2751 while (v != cur_val);
2753 cur_val->topo_next = values_topo;
2754 values_topo = cur_val;
2758 /* Add all values in lattices associated with NODE to the topological sort if
2759 they are not there yet. */
2762 add_all_node_vals_to_toposort (cgraph_node *node, ipa_topo_info *topo)
2764 struct ipa_node_params *info = IPA_NODE_REF (node);
2765 int i, count = ipa_get_param_count (info);
2767 for (i = 0; i < count ; i++)
2769 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
2770 ipcp_lattice<tree> *lat = &plats->itself;
2771 struct ipcp_agg_lattice *aglat;
2775 ipcp_value<tree> *val;
2776 for (val = lat->values; val; val = val->next)
2777 topo->constants.add_val (val);
2780 if (!plats->aggs_bottom)
2781 for (aglat = plats->aggs; aglat; aglat = aglat->next)
2784 ipcp_value<tree> *val;
2785 for (val = aglat->values; val; val = val->next)
2786 topo->constants.add_val (val);
2789 ipcp_lattice<ipa_polymorphic_call_context> *ctxlat = &plats->ctxlat;
2790 if (!ctxlat->bottom)
2792 ipcp_value<ipa_polymorphic_call_context> *ctxval;
2793 for (ctxval = ctxlat->values; ctxval; ctxval = ctxval->next)
2794 topo->contexts.add_val (ctxval);
2799 /* One pass of constants propagation along the call graph edges, from callers
2800 to callees (requires topological ordering in TOPO), iterate over strongly
2801 connected components. */
2804 propagate_constants_topo (struct ipa_topo_info *topo)
2808 for (i = topo->nnodes - 1; i >= 0; i--)
2811 struct cgraph_node *v, *node = topo->order[i];
2812 vec<cgraph_node *> cycle_nodes = ipa_get_nodes_in_cycle (node);
2814 /* First, iteratively propagate within the strongly connected component
2815 until all lattices stabilize. */
2816 FOR_EACH_VEC_ELT (cycle_nodes, j, v)
2817 if (v->has_gimple_body_p ())
2818 push_node_to_stack (topo, v);
2820 v = pop_node_from_stack (topo);
2823 struct cgraph_edge *cs;
2825 for (cs = v->callees; cs; cs = cs->next_callee)
2826 if (ipa_edge_within_scc (cs))
2828 IPA_NODE_REF (v)->node_within_scc = true;
2829 if (propagate_constants_accross_call (cs))
2830 push_node_to_stack (topo, cs->callee->function_symbol ());
2832 v = pop_node_from_stack (topo);
2835 /* Afterwards, propagate along edges leading out of the SCC, calculates
2836 the local effects of the discovered constants and all valid values to
2837 their topological sort. */
2838 FOR_EACH_VEC_ELT (cycle_nodes, j, v)
2839 if (v->has_gimple_body_p ())
2841 struct cgraph_edge *cs;
2843 estimate_local_effects (v);
2844 add_all_node_vals_to_toposort (v, topo);
2845 for (cs = v->callees; cs; cs = cs->next_callee)
2846 if (!ipa_edge_within_scc (cs))
2847 propagate_constants_accross_call (cs);
2849 cycle_nodes.release ();
2854 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
2855 the bigger one if otherwise. */
2858 safe_add (int a, int b)
2860 if (a > INT_MAX/2 || b > INT_MAX/2)
2861 return a > b ? a : b;
2867 /* Propagate the estimated effects of individual values along the topological
2868 from the dependent values to those they depend on. */
2870 template <typename valtype>
2872 value_topo_info<valtype>::propagate_effects ()
2874 ipcp_value<valtype> *base;
2876 for (base = values_topo; base; base = base->topo_next)
2878 ipcp_value_source<valtype> *src;
2879 ipcp_value<valtype> *val;
2880 int time = 0, size = 0;
2882 for (val = base; val; val = val->scc_next)
2884 time = safe_add (time,
2885 val->local_time_benefit + val->prop_time_benefit);
2886 size = safe_add (size, val->local_size_cost + val->prop_size_cost);
2889 for (val = base; val; val = val->scc_next)
2890 for (src = val->sources; src; src = src->next)
2892 && src->cs->maybe_hot_p ())
2894 src->val->prop_time_benefit = safe_add (time,
2895 src->val->prop_time_benefit);
2896 src->val->prop_size_cost = safe_add (size,
2897 src->val->prop_size_cost);
2903 /* Propagate constants, polymorphic contexts and their effects from the
2904 summaries interprocedurally. */
2907 ipcp_propagate_stage (struct ipa_topo_info *topo)
2909 struct cgraph_node *node;
2912 fprintf (dump_file, "\n Propagating constants:\n\n");
2915 ipa_update_after_lto_read ();
2918 FOR_EACH_DEFINED_FUNCTION (node)
2920 struct ipa_node_params *info = IPA_NODE_REF (node);
2922 determine_versionability (node, info);
2923 if (node->has_gimple_body_p ())
2925 info->lattices = XCNEWVEC (struct ipcp_param_lattices,
2926 ipa_get_param_count (info));
2927 initialize_node_lattices (node);
2929 if (node->definition && !node->alias)
2930 overall_size += inline_summaries->get (node)->self_size;
2931 if (node->count > max_count)
2932 max_count = node->count;
2935 max_new_size = overall_size;
2936 if (max_new_size < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
2937 max_new_size = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
2938 max_new_size += max_new_size * PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH) / 100 + 1;
2941 fprintf (dump_file, "\noverall_size: %li, max_new_size: %li\n",
2942 overall_size, max_new_size);
2944 propagate_constants_topo (topo);
2946 ipcp_verify_propagated_values ();
2947 topo->constants.propagate_effects ();
2948 topo->contexts.propagate_effects ();
2952 fprintf (dump_file, "\nIPA lattices after all propagation:\n");
2953 print_all_lattices (dump_file, (dump_flags & TDF_DETAILS), true);
2957 /* Discover newly direct outgoing edges from NODE which is a new clone with
2958 known KNOWN_CSTS and make them direct. */
2961 ipcp_discover_new_direct_edges (struct cgraph_node *node,
2962 vec<tree> known_csts,
2963 vec<ipa_polymorphic_call_context>
2965 struct ipa_agg_replacement_value *aggvals)
2967 struct cgraph_edge *ie, *next_ie;
2970 for (ie = node->indirect_calls; ie; ie = next_ie)
2975 next_ie = ie->next_callee;
2976 target = ipa_get_indirect_edge_target_1 (ie, known_csts, known_contexts,
2977 vNULL, aggvals, &speculative);
2980 bool agg_contents = ie->indirect_info->agg_contents;
2981 bool polymorphic = ie->indirect_info->polymorphic;
2982 int param_index = ie->indirect_info->param_index;
2983 struct cgraph_edge *cs = ipa_make_edge_direct_to_target (ie, target,
2987 if (cs && !agg_contents && !polymorphic)
2989 struct ipa_node_params *info = IPA_NODE_REF (node);
2990 int c = ipa_get_controlled_uses (info, param_index);
2991 if (c != IPA_UNDESCRIBED_USE)
2993 struct ipa_ref *to_del;
2996 ipa_set_controlled_uses (info, param_index, c);
2997 if (dump_file && (dump_flags & TDF_DETAILS))
2998 fprintf (dump_file, " controlled uses count of param "
2999 "%i bumped down to %i\n", param_index, c);
3001 && (to_del = node->find_reference (cs->callee, NULL, 0)))
3003 if (dump_file && (dump_flags & TDF_DETAILS))
3004 fprintf (dump_file, " and even removing its "
3005 "cloning-created reference\n");
3006 to_del->remove_reference ();
3012 /* Turning calls to direct calls will improve overall summary. */
3014 inline_update_overall_summary (node);
3017 /* Vector of pointers which for linked lists of clones of an original crgaph
3020 static vec<cgraph_edge *> next_edge_clone;
3021 static vec<cgraph_edge *> prev_edge_clone;
3024 grow_edge_clone_vectors (void)
3026 if (next_edge_clone.length ()
3027 <= (unsigned) symtab->edges_max_uid)
3028 next_edge_clone.safe_grow_cleared (symtab->edges_max_uid + 1);
3029 if (prev_edge_clone.length ()
3030 <= (unsigned) symtab->edges_max_uid)
3031 prev_edge_clone.safe_grow_cleared (symtab->edges_max_uid + 1);
3034 /* Edge duplication hook to grow the appropriate linked list in
3038 ipcp_edge_duplication_hook (struct cgraph_edge *src, struct cgraph_edge *dst,
3041 grow_edge_clone_vectors ();
3043 struct cgraph_edge *old_next = next_edge_clone[src->uid];
3045 prev_edge_clone[old_next->uid] = dst;
3046 prev_edge_clone[dst->uid] = src;
3048 next_edge_clone[dst->uid] = old_next;
3049 next_edge_clone[src->uid] = dst;
3052 /* Hook that is called by cgraph.c when an edge is removed. */
3055 ipcp_edge_removal_hook (struct cgraph_edge *cs, void *)
3057 grow_edge_clone_vectors ();
3059 struct cgraph_edge *prev = prev_edge_clone[cs->uid];
3060 struct cgraph_edge *next = next_edge_clone[cs->uid];
3062 next_edge_clone[prev->uid] = next;
3064 prev_edge_clone[next->uid] = prev;
3067 /* See if NODE is a clone with a known aggregate value at a given OFFSET of a
3068 parameter with the given INDEX. */
3071 get_clone_agg_value (struct cgraph_node *node, HOST_WIDE_INT offset,
3074 struct ipa_agg_replacement_value *aggval;
3076 aggval = ipa_get_agg_replacements_for_node (node);
3079 if (aggval->offset == offset
3080 && aggval->index == index)
3081 return aggval->value;
3082 aggval = aggval->next;
3087 /* Return true is NODE is DEST or its clone for all contexts. */
3090 same_node_or_its_all_contexts_clone_p (cgraph_node *node, cgraph_node *dest)
3095 struct ipa_node_params *info = IPA_NODE_REF (node);
3096 return info->is_all_contexts_clone && info->ipcp_orig_node == dest;
3099 /* Return true if edge CS does bring about the value described by SRC to node
3100 DEST or its clone for all contexts. */
3103 cgraph_edge_brings_value_p (cgraph_edge *cs, ipcp_value_source<tree> *src,
3106 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
3107 enum availability availability;
3108 cgraph_node *real_dest = cs->callee->function_symbol (&availability);
3110 if (!same_node_or_its_all_contexts_clone_p (real_dest, dest)
3111 || availability <= AVAIL_INTERPOSABLE
3112 || caller_info->node_dead)
3117 if (caller_info->ipcp_orig_node)
3120 if (src->offset == -1)
3121 t = caller_info->known_csts[src->index];
3123 t = get_clone_agg_value (cs->caller, src->offset, src->index);
3124 return (t != NULL_TREE
3125 && values_equal_for_ipcp_p (src->val->value, t));
3129 struct ipcp_agg_lattice *aglat;
3130 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (caller_info,
3132 if (src->offset == -1)
3133 return (plats->itself.is_single_const ()
3134 && values_equal_for_ipcp_p (src->val->value,
3135 plats->itself.values->value));
3138 if (plats->aggs_bottom || plats->aggs_contain_variable)
3140 for (aglat = plats->aggs; aglat; aglat = aglat->next)
3141 if (aglat->offset == src->offset)
3142 return (aglat->is_single_const ()
3143 && values_equal_for_ipcp_p (src->val->value,
3144 aglat->values->value));
3150 /* Return true if edge CS does bring about the value described by SRC to node
3151 DEST or its clone for all contexts. */
3154 cgraph_edge_brings_value_p (cgraph_edge *cs,
3155 ipcp_value_source<ipa_polymorphic_call_context> *src,
3158 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
3159 cgraph_node *real_dest = cs->callee->function_symbol ();
3161 if (!same_node_or_its_all_contexts_clone_p (real_dest, dest)
3162 || caller_info->node_dead)
3167 if (caller_info->ipcp_orig_node)
3168 return (caller_info->known_contexts.length () > (unsigned) src->index)
3169 && values_equal_for_ipcp_p (src->val->value,
3170 caller_info->known_contexts[src->index]);
3172 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (caller_info,
3174 return plats->ctxlat.is_single_const ()
3175 && values_equal_for_ipcp_p (src->val->value,
3176 plats->ctxlat.values->value);
3179 /* Get the next clone in the linked list of clones of an edge. */
3181 static inline struct cgraph_edge *
3182 get_next_cgraph_edge_clone (struct cgraph_edge *cs)
3184 return next_edge_clone[cs->uid];
3187 /* Given VAL that is intended for DEST, iterate over all its sources and if
3188 they still hold, add their edge frequency and their number into *FREQUENCY
3189 and *CALLER_COUNT respectively. */
3191 template <typename valtype>
3193 get_info_about_necessary_edges (ipcp_value<valtype> *val, cgraph_node *dest,
3195 gcov_type *count_sum, int *caller_count)
3197 ipcp_value_source<valtype> *src;
3198 int freq = 0, count = 0;
3202 for (src = val->sources; src; src = src->next)
3204 struct cgraph_edge *cs = src->cs;
3207 if (cgraph_edge_brings_value_p (cs, src, dest))
3210 freq += cs->frequency;
3212 hot |= cs->maybe_hot_p ();
3214 cs = get_next_cgraph_edge_clone (cs);
3220 *caller_count = count;
3224 /* Return a vector of incoming edges that do bring value VAL to node DEST. It
3225 is assumed their number is known and equal to CALLER_COUNT. */
3227 template <typename valtype>
3228 static vec<cgraph_edge *>
3229 gather_edges_for_value (ipcp_value<valtype> *val, cgraph_node *dest,
3232 ipcp_value_source<valtype> *src;
3233 vec<cgraph_edge *> ret;
3235 ret.create (caller_count);
3236 for (src = val->sources; src; src = src->next)
3238 struct cgraph_edge *cs = src->cs;
3241 if (cgraph_edge_brings_value_p (cs, src, dest))
3242 ret.quick_push (cs);
3243 cs = get_next_cgraph_edge_clone (cs);
3250 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
3251 Return it or NULL if for some reason it cannot be created. */
3253 static struct ipa_replace_map *
3254 get_replacement_map (struct ipa_node_params *info, tree value, int parm_num)
3256 struct ipa_replace_map *replace_map;
3259 replace_map = ggc_alloc<ipa_replace_map> ();
3262 fprintf (dump_file, " replacing ");
3263 ipa_dump_param (dump_file, info, parm_num);
3265 fprintf (dump_file, " with const ");
3266 print_generic_expr (dump_file, value, 0);
3267 fprintf (dump_file, "\n");
3269 replace_map->old_tree = NULL;
3270 replace_map->parm_num = parm_num;
3271 replace_map->new_tree = value;
3272 replace_map->replace_p = true;
3273 replace_map->ref_p = false;
3278 /* Dump new profiling counts */
3281 dump_profile_updates (struct cgraph_node *orig_node,
3282 struct cgraph_node *new_node)
3284 struct cgraph_edge *cs;
3286 fprintf (dump_file, " setting count of the specialized node to "
3287 HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) new_node->count);
3288 for (cs = new_node->callees; cs ; cs = cs->next_callee)
3289 fprintf (dump_file, " edge to %s has count "
3290 HOST_WIDE_INT_PRINT_DEC "\n",
3291 cs->callee->name (), (HOST_WIDE_INT) cs->count);
3293 fprintf (dump_file, " setting count of the original node to "
3294 HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) orig_node->count);
3295 for (cs = orig_node->callees; cs ; cs = cs->next_callee)
3296 fprintf (dump_file, " edge to %s is left with "
3297 HOST_WIDE_INT_PRINT_DEC "\n",
3298 cs->callee->name (), (HOST_WIDE_INT) cs->count);
3301 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
3302 their profile information to reflect this. */
3305 update_profiling_info (struct cgraph_node *orig_node,
3306 struct cgraph_node *new_node)
3308 struct cgraph_edge *cs;
3309 struct caller_statistics stats;
3310 gcov_type new_sum, orig_sum;
3311 gcov_type remainder, orig_node_count = orig_node->count;
3313 if (orig_node_count == 0)
3316 init_caller_stats (&stats);
3317 orig_node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats,
3319 orig_sum = stats.count_sum;
3320 init_caller_stats (&stats);
3321 new_node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats,
3323 new_sum = stats.count_sum;
3325 if (orig_node_count < orig_sum + new_sum)
3328 fprintf (dump_file, " Problem: node %s/%i has too low count "
3329 HOST_WIDE_INT_PRINT_DEC " while the sum of incoming "
3330 "counts is " HOST_WIDE_INT_PRINT_DEC "\n",
3331 orig_node->name (), orig_node->order,
3332 (HOST_WIDE_INT) orig_node_count,
3333 (HOST_WIDE_INT) (orig_sum + new_sum));
3335 orig_node_count = (orig_sum + new_sum) * 12 / 10;
3337 fprintf (dump_file, " proceeding by pretending it was "
3338 HOST_WIDE_INT_PRINT_DEC "\n",
3339 (HOST_WIDE_INT) orig_node_count);
3342 new_node->count = new_sum;
3343 remainder = orig_node_count - new_sum;
3344 orig_node->count = remainder;
3346 for (cs = new_node->callees; cs ; cs = cs->next_callee)
3348 cs->count = apply_probability (cs->count,
3349 GCOV_COMPUTE_SCALE (new_sum,
3354 for (cs = orig_node->callees; cs ; cs = cs->next_callee)
3355 cs->count = apply_probability (cs->count,
3356 GCOV_COMPUTE_SCALE (remainder,
3360 dump_profile_updates (orig_node, new_node);
3363 /* Update the respective profile of specialized NEW_NODE and the original
3364 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
3365 have been redirected to the specialized version. */
3368 update_specialized_profile (struct cgraph_node *new_node,
3369 struct cgraph_node *orig_node,
3370 gcov_type redirected_sum)
3372 struct cgraph_edge *cs;
3373 gcov_type new_node_count, orig_node_count = orig_node->count;
3376 fprintf (dump_file, " the sum of counts of redirected edges is "
3377 HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) redirected_sum);
3378 if (orig_node_count == 0)
3381 gcc_assert (orig_node_count >= redirected_sum);
3383 new_node_count = new_node->count;
3384 new_node->count += redirected_sum;
3385 orig_node->count -= redirected_sum;
3387 for (cs = new_node->callees; cs ; cs = cs->next_callee)
3389 cs->count += apply_probability (cs->count,
3390 GCOV_COMPUTE_SCALE (redirected_sum,
3395 for (cs = orig_node->callees; cs ; cs = cs->next_callee)
3397 gcov_type dec = apply_probability (cs->count,
3398 GCOV_COMPUTE_SCALE (redirected_sum,
3400 if (dec < cs->count)
3407 dump_profile_updates (orig_node, new_node);
3410 /* Create a specialized version of NODE with known constants in KNOWN_CSTS,
3411 known contexts in KNOWN_CONTEXTS and known aggregate values in AGGVALS and
3412 redirect all edges in CALLERS to it. */
3414 static struct cgraph_node *
3415 create_specialized_node (struct cgraph_node *node,
3416 vec<tree> known_csts,
3417 vec<ipa_polymorphic_call_context> known_contexts,
3418 struct ipa_agg_replacement_value *aggvals,
3419 vec<cgraph_edge *> callers)
3421 struct ipa_node_params *new_info, *info = IPA_NODE_REF (node);
3422 vec<ipa_replace_map *, va_gc> *replace_trees = NULL;
3423 struct ipa_agg_replacement_value *av;
3424 struct cgraph_node *new_node;
3425 int i, count = ipa_get_param_count (info);
3426 bitmap args_to_skip;
3428 gcc_assert (!info->ipcp_orig_node);
3430 if (node->local.can_change_signature)
3432 args_to_skip = BITMAP_GGC_ALLOC ();
3433 for (i = 0; i < count; i++)
3435 tree t = known_csts[i];
3437 if (t || !ipa_is_param_used (info, i))
3438 bitmap_set_bit (args_to_skip, i);
3443 args_to_skip = NULL;
3444 if (dump_file && (dump_flags & TDF_DETAILS))
3445 fprintf (dump_file, " cannot change function signature\n");
3448 for (i = 0; i < count ; i++)
3450 tree t = known_csts[i];
3453 struct ipa_replace_map *replace_map;
3455 gcc_checking_assert (TREE_CODE (t) != TREE_BINFO);
3456 replace_map = get_replacement_map (info, t, i);
3458 vec_safe_push (replace_trees, replace_map);
3462 new_node = node->create_virtual_clone (callers, replace_trees,
3463 args_to_skip, "constprop");
3464 ipa_set_node_agg_value_chain (new_node, aggvals);
3465 for (av = aggvals; av; av = av->next)
3466 new_node->maybe_create_reference (av->value, IPA_REF_ADDR, NULL);
3468 if (dump_file && (dump_flags & TDF_DETAILS))
3470 fprintf (dump_file, " the new node is %s/%i.\n",
3471 new_node->name (), new_node->order);
3472 if (known_contexts.exists ())
3474 for (i = 0; i < count ; i++)
3475 if (!known_contexts[i].useless_p ())
3477 fprintf (dump_file, " known ctx %i is ", i);
3478 known_contexts[i].dump (dump_file);
3482 ipa_dump_agg_replacement_values (dump_file, aggvals);
3484 ipa_check_create_node_params ();
3485 update_profiling_info (node, new_node);
3486 new_info = IPA_NODE_REF (new_node);
3487 new_info->ipcp_orig_node = node;
3488 new_info->known_csts = known_csts;
3489 new_info->known_contexts = known_contexts;
3491 ipcp_discover_new_direct_edges (new_node, known_csts, known_contexts, aggvals);
3497 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
3498 KNOWN_CSTS with constants that are also known for all of the CALLERS. */
3501 find_more_scalar_values_for_callers_subset (struct cgraph_node *node,
3502 vec<tree> known_csts,
3503 vec<cgraph_edge *> callers)
3505 struct ipa_node_params *info = IPA_NODE_REF (node);
3506 int i, count = ipa_get_param_count (info);
3508 for (i = 0; i < count ; i++)
3510 struct cgraph_edge *cs;
3511 tree newval = NULL_TREE;
3515 if (ipa_get_scalar_lat (info, i)->bottom || known_csts[i])
3518 FOR_EACH_VEC_ELT (callers, j, cs)
3520 struct ipa_jump_func *jump_func;
3523 if (i >= ipa_get_cs_argument_count (IPA_EDGE_REF (cs))
3525 && call_passes_through_thunk_p (cs))
3526 || (!cs->callee->instrumentation_clone
3527 && cs->callee->function_symbol ()->instrumentation_clone))
3532 jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
3533 t = ipa_value_from_jfunc (IPA_NODE_REF (cs->caller), jump_func);
3536 && !values_equal_for_ipcp_p (t, newval))
3537 || (!first && !newval))
3549 if (dump_file && (dump_flags & TDF_DETAILS))
3551 fprintf (dump_file, " adding an extra known scalar value ");
3552 print_ipcp_constant_value (dump_file, newval);
3553 fprintf (dump_file, " for ");
3554 ipa_dump_param (dump_file, info, i);
3555 fprintf (dump_file, "\n");
3558 known_csts[i] = newval;
3563 /* Given a NODE and a subset of its CALLERS, try to populate plank slots in
3564 KNOWN_CONTEXTS with polymorphic contexts that are also known for all of the
3568 find_more_contexts_for_caller_subset (cgraph_node *node,
3569 vec<ipa_polymorphic_call_context>
3571 vec<cgraph_edge *> callers)
3573 ipa_node_params *info = IPA_NODE_REF (node);
3574 int i, count = ipa_get_param_count (info);
3576 for (i = 0; i < count ; i++)
3580 if (ipa_get_poly_ctx_lat (info, i)->bottom
3581 || (known_contexts->exists ()
3582 && !(*known_contexts)[i].useless_p ()))
3585 ipa_polymorphic_call_context newval;
3589 FOR_EACH_VEC_ELT (callers, j, cs)
3591 if (i >= ipa_get_cs_argument_count (IPA_EDGE_REF (cs)))
3593 ipa_jump_func *jfunc = ipa_get_ith_jump_func (IPA_EDGE_REF (cs),
3595 ipa_polymorphic_call_context ctx;
3596 ctx = ipa_context_from_jfunc (IPA_NODE_REF (cs->caller), cs, i,
3604 newval.meet_with (ctx);
3605 if (newval.useless_p ())
3609 if (!newval.useless_p ())
3611 if (dump_file && (dump_flags & TDF_DETAILS))
3613 fprintf (dump_file, " adding an extra known polymorphic "
3615 print_ipcp_constant_value (dump_file, newval);
3616 fprintf (dump_file, " for ");
3617 ipa_dump_param (dump_file, info, i);
3618 fprintf (dump_file, "\n");
3621 if (!known_contexts->exists ())
3622 known_contexts->safe_grow_cleared (ipa_get_param_count (info));
3623 (*known_contexts)[i] = newval;
3629 /* Go through PLATS and create a vector of values consisting of values and
3630 offsets (minus OFFSET) of lattices that contain only a single value. */
3632 static vec<ipa_agg_jf_item>
3633 copy_plats_to_inter (struct ipcp_param_lattices *plats, HOST_WIDE_INT offset)
3635 vec<ipa_agg_jf_item> res = vNULL;
3637 if (!plats->aggs || plats->aggs_contain_variable || plats->aggs_bottom)
3640 for (struct ipcp_agg_lattice *aglat = plats->aggs; aglat; aglat = aglat->next)
3641 if (aglat->is_single_const ())
3643 struct ipa_agg_jf_item ti;
3644 ti.offset = aglat->offset - offset;
3645 ti.value = aglat->values->value;
3651 /* Intersect all values in INTER with single value lattices in PLATS (while
3652 subtracting OFFSET). */
3655 intersect_with_plats (struct ipcp_param_lattices *plats,
3656 vec<ipa_agg_jf_item> *inter,
3657 HOST_WIDE_INT offset)
3659 struct ipcp_agg_lattice *aglat;
3660 struct ipa_agg_jf_item *item;
3663 if (!plats->aggs || plats->aggs_contain_variable || plats->aggs_bottom)
3669 aglat = plats->aggs;
3670 FOR_EACH_VEC_ELT (*inter, k, item)
3677 if (aglat->offset - offset > item->offset)
3679 if (aglat->offset - offset == item->offset)
3681 gcc_checking_assert (item->value);
3682 if (values_equal_for_ipcp_p (item->value, aglat->values->value))
3686 aglat = aglat->next;
3689 item->value = NULL_TREE;
3693 /* Copy agggregate replacement values of NODE (which is an IPA-CP clone) to the
3694 vector result while subtracting OFFSET from the individual value offsets. */
3696 static vec<ipa_agg_jf_item>
3697 agg_replacements_to_vector (struct cgraph_node *node, int index,
3698 HOST_WIDE_INT offset)
3700 struct ipa_agg_replacement_value *av;
3701 vec<ipa_agg_jf_item> res = vNULL;
3703 for (av = ipa_get_agg_replacements_for_node (node); av; av = av->next)
3704 if (av->index == index
3705 && (av->offset - offset) >= 0)
3707 struct ipa_agg_jf_item item;
3708 gcc_checking_assert (av->value);
3709 item.offset = av->offset - offset;
3710 item.value = av->value;
3711 res.safe_push (item);
3717 /* Intersect all values in INTER with those that we have already scheduled to
3718 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
3719 (while subtracting OFFSET). */
3722 intersect_with_agg_replacements (struct cgraph_node *node, int index,
3723 vec<ipa_agg_jf_item> *inter,
3724 HOST_WIDE_INT offset)
3726 struct ipa_agg_replacement_value *srcvals;
3727 struct ipa_agg_jf_item *item;
3730 srcvals = ipa_get_agg_replacements_for_node (node);
3737 FOR_EACH_VEC_ELT (*inter, i, item)
3739 struct ipa_agg_replacement_value *av;
3743 for (av = srcvals; av; av = av->next)
3745 gcc_checking_assert (av->value);
3746 if (av->index == index
3747 && av->offset - offset == item->offset)
3749 if (values_equal_for_ipcp_p (item->value, av->value))
3755 item->value = NULL_TREE;
3759 /* Intersect values in INTER with aggregate values that come along edge CS to
3760 parameter number INDEX and return it. If INTER does not actually exist yet,
3761 copy all incoming values to it. If we determine we ended up with no values
3762 whatsoever, return a released vector. */
3764 static vec<ipa_agg_jf_item>
3765 intersect_aggregates_with_edge (struct cgraph_edge *cs, int index,
3766 vec<ipa_agg_jf_item> inter)
3768 struct ipa_jump_func *jfunc;
3769 jfunc = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), index);
3770 if (jfunc->type == IPA_JF_PASS_THROUGH
3771 && ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
3773 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
3774 int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
3776 if (caller_info->ipcp_orig_node)
3778 struct cgraph_node *orig_node = caller_info->ipcp_orig_node;
3779 struct ipcp_param_lattices *orig_plats;
3780 orig_plats = ipa_get_parm_lattices (IPA_NODE_REF (orig_node),
3782 if (agg_pass_through_permissible_p (orig_plats, jfunc))
3784 if (!inter.exists ())
3785 inter = agg_replacements_to_vector (cs->caller, src_idx, 0);
3787 intersect_with_agg_replacements (cs->caller, src_idx,
3798 struct ipcp_param_lattices *src_plats;
3799 src_plats = ipa_get_parm_lattices (caller_info, src_idx);
3800 if (agg_pass_through_permissible_p (src_plats, jfunc))
3802 /* Currently we do not produce clobber aggregate jump
3803 functions, adjust when we do. */
3804 gcc_checking_assert (!jfunc->agg.items);
3805 if (!inter.exists ())
3806 inter = copy_plats_to_inter (src_plats, 0);
3808 intersect_with_plats (src_plats, &inter, 0);
3817 else if (jfunc->type == IPA_JF_ANCESTOR
3818 && ipa_get_jf_ancestor_agg_preserved (jfunc))
3820 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
3821 int src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
3822 struct ipcp_param_lattices *src_plats;
3823 HOST_WIDE_INT delta = ipa_get_jf_ancestor_offset (jfunc);
3825 if (caller_info->ipcp_orig_node)
3827 if (!inter.exists ())
3828 inter = agg_replacements_to_vector (cs->caller, src_idx, delta);
3830 intersect_with_agg_replacements (cs->caller, src_idx, &inter,
3835 src_plats = ipa_get_parm_lattices (caller_info, src_idx);;
3836 /* Currently we do not produce clobber aggregate jump
3837 functions, adjust when we do. */
3838 gcc_checking_assert (!src_plats->aggs || !jfunc->agg.items);
3839 if (!inter.exists ())
3840 inter = copy_plats_to_inter (src_plats, delta);
3842 intersect_with_plats (src_plats, &inter, delta);
3845 else if (jfunc->agg.items)
3847 struct ipa_agg_jf_item *item;
3850 if (!inter.exists ())
3851 for (unsigned i = 0; i < jfunc->agg.items->length (); i++)
3852 inter.safe_push ((*jfunc->agg.items)[i]);
3854 FOR_EACH_VEC_ELT (inter, k, item)
3857 bool found = false;;
3862 while ((unsigned) l < jfunc->agg.items->length ())
3864 struct ipa_agg_jf_item *ti;
3865 ti = &(*jfunc->agg.items)[l];
3866 if (ti->offset > item->offset)
3868 if (ti->offset == item->offset)
3870 gcc_checking_assert (ti->value);
3871 if (values_equal_for_ipcp_p (item->value,
3885 return vec<ipa_agg_jf_item>();
3890 /* Look at edges in CALLERS and collect all known aggregate values that arrive
3891 from all of them. */
3893 static struct ipa_agg_replacement_value *
3894 find_aggregate_values_for_callers_subset (struct cgraph_node *node,
3895 vec<cgraph_edge *> callers)
3897 struct ipa_node_params *dest_info = IPA_NODE_REF (node);
3898 struct ipa_agg_replacement_value *res;
3899 struct ipa_agg_replacement_value **tail = &res;
3900 struct cgraph_edge *cs;
3901 int i, j, count = ipa_get_param_count (dest_info);
3903 FOR_EACH_VEC_ELT (callers, j, cs)
3905 int c = ipa_get_cs_argument_count (IPA_EDGE_REF (cs));
3910 for (i = 0; i < count ; i++)
3912 struct cgraph_edge *cs;
3913 vec<ipa_agg_jf_item> inter = vNULL;
3914 struct ipa_agg_jf_item *item;
3915 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (dest_info, i);
3918 /* Among other things, the following check should deal with all by_ref
3920 if (plats->aggs_bottom)
3923 FOR_EACH_VEC_ELT (callers, j, cs)
3925 inter = intersect_aggregates_with_edge (cs, i, inter);
3927 if (!inter.exists ())
3931 FOR_EACH_VEC_ELT (inter, j, item)
3933 struct ipa_agg_replacement_value *v;
3938 v = ggc_alloc<ipa_agg_replacement_value> ();
3940 v->offset = item->offset;
3941 v->value = item->value;
3942 v->by_ref = plats->aggs_by_ref;
3948 if (inter.exists ())
3955 /* Turn KNOWN_AGGS into a list of aggreate replacement values. */
3957 static struct ipa_agg_replacement_value *
3958 known_aggs_to_agg_replacement_list (vec<ipa_agg_jump_function> known_aggs)
3960 struct ipa_agg_replacement_value *res;
3961 struct ipa_agg_replacement_value **tail = &res;
3962 struct ipa_agg_jump_function *aggjf;
3963 struct ipa_agg_jf_item *item;
3966 FOR_EACH_VEC_ELT (known_aggs, i, aggjf)
3967 FOR_EACH_VEC_SAFE_ELT (aggjf->items, j, item)
3969 struct ipa_agg_replacement_value *v;
3970 v = ggc_alloc<ipa_agg_replacement_value> ();
3972 v->offset = item->offset;
3973 v->value = item->value;
3974 v->by_ref = aggjf->by_ref;
3982 /* Determine whether CS also brings all scalar values that the NODE is
3986 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge *cs,
3987 struct cgraph_node *node)
3989 struct ipa_node_params *dest_info = IPA_NODE_REF (node);
3990 int count = ipa_get_param_count (dest_info);
3991 struct ipa_node_params *caller_info;
3992 struct ipa_edge_args *args;
3995 caller_info = IPA_NODE_REF (cs->caller);
3996 args = IPA_EDGE_REF (cs);
3997 for (i = 0; i < count; i++)
3999 struct ipa_jump_func *jump_func;
4002 val = dest_info->known_csts[i];
4006 if (i >= ipa_get_cs_argument_count (args))
4008 jump_func = ipa_get_ith_jump_func (args, i);
4009 t = ipa_value_from_jfunc (caller_info, jump_func);
4010 if (!t || !values_equal_for_ipcp_p (val, t))
4016 /* Determine whether CS also brings all aggregate values that NODE is
4019 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge *cs,
4020 struct cgraph_node *node)
4022 struct ipa_node_params *orig_caller_info = IPA_NODE_REF (cs->caller);
4023 struct ipa_node_params *orig_node_info;
4024 struct ipa_agg_replacement_value *aggval;
4027 aggval = ipa_get_agg_replacements_for_node (node);
4031 count = ipa_get_param_count (IPA_NODE_REF (node));
4032 ec = ipa_get_cs_argument_count (IPA_EDGE_REF (cs));
4034 for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next)
4035 if (aggval->index >= ec)
4038 orig_node_info = IPA_NODE_REF (IPA_NODE_REF (node)->ipcp_orig_node);
4039 if (orig_caller_info->ipcp_orig_node)
4040 orig_caller_info = IPA_NODE_REF (orig_caller_info->ipcp_orig_node);
4042 for (i = 0; i < count; i++)
4044 static vec<ipa_agg_jf_item> values = vec<ipa_agg_jf_item>();
4045 struct ipcp_param_lattices *plats;
4046 bool interesting = false;
4047 for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next)
4048 if (aggval->index == i)
4056 plats = ipa_get_parm_lattices (orig_node_info, aggval->index);
4057 if (plats->aggs_bottom)
4060 values = intersect_aggregates_with_edge (cs, i, values);
4061 if (!values.exists ())
4064 for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next)
4065 if (aggval->index == i)
4067 struct ipa_agg_jf_item *item;
4070 FOR_EACH_VEC_ELT (values, j, item)
4072 && item->offset == av->offset
4073 && values_equal_for_ipcp_p (item->value, av->value))
4088 /* Given an original NODE and a VAL for which we have already created a
4089 specialized clone, look whether there are incoming edges that still lead
4090 into the old node but now also bring the requested value and also conform to
4091 all other criteria such that they can be redirected the special node.
4092 This function can therefore redirect the final edge in a SCC. */
4094 template <typename valtype>
4096 perhaps_add_new_callers (cgraph_node *node, ipcp_value<valtype> *val)
4098 ipcp_value_source<valtype> *src;
4099 gcov_type redirected_sum = 0;
4101 for (src = val->sources; src; src = src->next)
4103 struct cgraph_edge *cs = src->cs;
4106 if (cgraph_edge_brings_value_p (cs, src, node)
4107 && cgraph_edge_brings_all_scalars_for_node (cs, val->spec_node)
4108 && cgraph_edge_brings_all_agg_vals_for_node (cs, val->spec_node))
4111 fprintf (dump_file, " - adding an extra caller %s/%i"
4113 xstrdup_for_dump (cs->caller->name ()),
4115 xstrdup_for_dump (val->spec_node->name ()),
4116 val->spec_node->order);
4118 cs->redirect_callee_duplicating_thunks (val->spec_node);
4119 val->spec_node->expand_all_artificial_thunks ();
4120 redirected_sum += cs->count;
4122 cs = get_next_cgraph_edge_clone (cs);
4127 update_specialized_profile (val->spec_node, node, redirected_sum);
4130 /* Return true if KNOWN_CONTEXTS contain at least one useful context. */
4133 known_contexts_useful_p (vec<ipa_polymorphic_call_context> known_contexts)
4135 ipa_polymorphic_call_context *ctx;
4138 FOR_EACH_VEC_ELT (known_contexts, i, ctx)
4139 if (!ctx->useless_p ())
4144 /* Return a copy of KNOWN_CSTS if it is not empty, otherwise return vNULL. */
4146 static vec<ipa_polymorphic_call_context>
4147 copy_useful_known_contexts (vec<ipa_polymorphic_call_context> known_contexts)
4149 if (known_contexts_useful_p (known_contexts))
4150 return known_contexts.copy ();
4155 /* Copy KNOWN_CSTS and modify the copy according to VAL and INDEX. If
4156 non-empty, replace KNOWN_CONTEXTS with its copy too. */
4159 modify_known_vectors_with_val (vec<tree> *known_csts,
4160 vec<ipa_polymorphic_call_context> *known_contexts,
4161 ipcp_value<tree> *val,
4164 *known_csts = known_csts->copy ();
4165 *known_contexts = copy_useful_known_contexts (*known_contexts);
4166 (*known_csts)[index] = val->value;
4169 /* Replace KNOWN_CSTS with its copy. Also copy KNOWN_CONTEXTS and modify the
4170 copy according to VAL and INDEX. */
4173 modify_known_vectors_with_val (vec<tree> *known_csts,
4174 vec<ipa_polymorphic_call_context> *known_contexts,
4175 ipcp_value<ipa_polymorphic_call_context> *val,
4178 *known_csts = known_csts->copy ();
4179 *known_contexts = known_contexts->copy ();
4180 (*known_contexts)[index] = val->value;
4183 /* Return true if OFFSET indicates this was not an aggregate value or there is
4184 a replacement equivalent to VALUE, INDEX and OFFSET among those in the
4188 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value *aggvals,
4189 int index, HOST_WIDE_INT offset, tree value)
4196 if (aggvals->index == index
4197 && aggvals->offset == offset
4198 && values_equal_for_ipcp_p (aggvals->value, value))
4200 aggvals = aggvals->next;
4205 /* Return true if offset is minus one because source of a polymorphic contect
4206 cannot be an aggregate value. */
4209 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value *,
4210 int , HOST_WIDE_INT offset,
4211 ipa_polymorphic_call_context)
4213 return offset == -1;
4216 /* Decide wheter to create a special version of NODE for value VAL of parameter
4217 at the given INDEX. If OFFSET is -1, the value is for the parameter itself,
4218 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS,
4219 KNOWN_CONTEXTS and KNOWN_AGGS describe the other already known values. */
4221 template <typename valtype>
4223 decide_about_value (struct cgraph_node *node, int index, HOST_WIDE_INT offset,
4224 ipcp_value<valtype> *val, vec<tree> known_csts,
4225 vec<ipa_polymorphic_call_context> known_contexts)
4227 struct ipa_agg_replacement_value *aggvals;
4228 int freq_sum, caller_count;
4229 gcov_type count_sum;
4230 vec<cgraph_edge *> callers;
4234 perhaps_add_new_callers (node, val);
4237 else if (val->local_size_cost + overall_size > max_new_size)
4239 if (dump_file && (dump_flags & TDF_DETAILS))
4240 fprintf (dump_file, " Ignoring candidate value because "
4241 "max_new_size would be reached with %li.\n",
4242 val->local_size_cost + overall_size);
4245 else if (!get_info_about_necessary_edges (val, node, &freq_sum, &count_sum,
4249 if (dump_file && (dump_flags & TDF_DETAILS))
4251 fprintf (dump_file, " - considering value ");
4252 print_ipcp_constant_value (dump_file, val->value);
4253 fprintf (dump_file, " for ");
4254 ipa_dump_param (dump_file, IPA_NODE_REF (node), index);
4256 fprintf (dump_file, ", offset: " HOST_WIDE_INT_PRINT_DEC, offset);
4257 fprintf (dump_file, " (caller_count: %i)\n", caller_count);
4260 if (!good_cloning_opportunity_p (node, val->local_time_benefit,
4261 freq_sum, count_sum,
4262 val->local_size_cost)
4263 && !good_cloning_opportunity_p (node,
4264 val->local_time_benefit
4265 + val->prop_time_benefit,
4266 freq_sum, count_sum,
4267 val->local_size_cost
4268 + val->prop_size_cost))
4272 fprintf (dump_file, " Creating a specialized node of %s/%i.\n",
4273 node->name (), node->order);
4275 callers = gather_edges_for_value (val, node, caller_count);
4277 modify_known_vectors_with_val (&known_csts, &known_contexts, val, index);
4280 known_csts = known_csts.copy ();
4281 known_contexts = copy_useful_known_contexts (known_contexts);
4283 find_more_scalar_values_for_callers_subset (node, known_csts, callers);
4284 find_more_contexts_for_caller_subset (node, &known_contexts, callers);
4285 aggvals = find_aggregate_values_for_callers_subset (node, callers);
4286 gcc_checking_assert (ipcp_val_agg_replacement_ok_p (aggvals, index,
4287 offset, val->value));
4288 val->spec_node = create_specialized_node (node, known_csts, known_contexts,
4290 overall_size += val->local_size_cost;
4292 /* TODO: If for some lattice there is only one other known value
4293 left, make a special node for it too. */
4298 /* Decide whether and what specialized clones of NODE should be created. */
4301 decide_whether_version_node (struct cgraph_node *node)
4303 struct ipa_node_params *info = IPA_NODE_REF (node);
4304 int i, count = ipa_get_param_count (info);
4305 vec<tree> known_csts;
4306 vec<ipa_polymorphic_call_context> known_contexts;
4307 vec<ipa_agg_jump_function> known_aggs = vNULL;
4313 if (dump_file && (dump_flags & TDF_DETAILS))
4314 fprintf (dump_file, "\nEvaluating opportunities for %s/%i.\n",
4315 node->name (), node->order);
4317 gather_context_independent_values (info, &known_csts, &known_contexts,
4318 info->do_clone_for_all_contexts ? &known_aggs
4321 for (i = 0; i < count ;i++)
4323 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
4324 ipcp_lattice<tree> *lat = &plats->itself;
4325 ipcp_lattice<ipa_polymorphic_call_context> *ctxlat = &plats->ctxlat;
4330 ipcp_value<tree> *val;
4331 for (val = lat->values; val; val = val->next)
4332 ret |= decide_about_value (node, i, -1, val, known_csts,
4336 if (!plats->aggs_bottom)
4338 struct ipcp_agg_lattice *aglat;
4339 ipcp_value<tree> *val;
4340 for (aglat = plats->aggs; aglat; aglat = aglat->next)
4341 if (!aglat->bottom && aglat->values
4342 /* If the following is false, the one value is in
4344 && (plats->aggs_contain_variable
4345 || !aglat->is_single_const ()))
4346 for (val = aglat->values; val; val = val->next)
4347 ret |= decide_about_value (node, i, aglat->offset, val,
4348 known_csts, known_contexts);
4352 && known_contexts[i].useless_p ())
4354 ipcp_value<ipa_polymorphic_call_context> *val;
4355 for (val = ctxlat->values; val; val = val->next)
4356 ret |= decide_about_value (node, i, -1, val, known_csts,
4360 info = IPA_NODE_REF (node);
4363 if (info->do_clone_for_all_contexts)
4365 struct cgraph_node *clone;
4366 vec<cgraph_edge *> callers;
4369 fprintf (dump_file, " - Creating a specialized node of %s/%i "
4370 "for all known contexts.\n", node->name (),
4373 callers = node->collect_callers ();
4375 if (!known_contexts_useful_p (known_contexts))
4377 known_contexts.release ();
4378 known_contexts = vNULL;
4380 clone = create_specialized_node (node, known_csts, known_contexts,
4381 known_aggs_to_agg_replacement_list (known_aggs),
4383 info = IPA_NODE_REF (node);
4384 info->do_clone_for_all_contexts = false;
4385 IPA_NODE_REF (clone)->is_all_contexts_clone = true;
4386 for (i = 0; i < count ; i++)
4387 vec_free (known_aggs[i].items);
4388 known_aggs.release ();
4393 known_csts.release ();
4394 known_contexts.release ();
4400 /* Transitively mark all callees of NODE within the same SCC as not dead. */
4403 spread_undeadness (struct cgraph_node *node)
4405 struct cgraph_edge *cs;
4407 for (cs = node->callees; cs; cs = cs->next_callee)
4408 if (ipa_edge_within_scc (cs))
4410 struct cgraph_node *callee;
4411 struct ipa_node_params *info;
4413 callee = cs->callee->function_symbol (NULL);
4414 info = IPA_NODE_REF (callee);
4416 if (info->node_dead)
4418 info->node_dead = 0;
4419 spread_undeadness (callee);
4424 /* Return true if NODE has a caller from outside of its SCC that is not
4425 dead. Worker callback for cgraph_for_node_and_aliases. */
4428 has_undead_caller_from_outside_scc_p (struct cgraph_node *node,
4429 void *data ATTRIBUTE_UNUSED)
4431 struct cgraph_edge *cs;
4433 for (cs = node->callers; cs; cs = cs->next_caller)
4434 if (cs->caller->thunk.thunk_p
4435 && cs->caller->call_for_symbol_thunks_and_aliases
4436 (has_undead_caller_from_outside_scc_p, NULL, true))
4438 else if (!ipa_edge_within_scc (cs)
4439 && !IPA_NODE_REF (cs->caller)->node_dead)
4445 /* Identify nodes within the same SCC as NODE which are no longer needed
4446 because of new clones and will be removed as unreachable. */
4449 identify_dead_nodes (struct cgraph_node *node)
4451 struct cgraph_node *v;
4452 for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
4454 && !v->call_for_symbol_thunks_and_aliases
4455 (has_undead_caller_from_outside_scc_p, NULL, true))
4456 IPA_NODE_REF (v)->node_dead = 1;
4458 for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
4459 if (!IPA_NODE_REF (v)->node_dead)
4460 spread_undeadness (v);
4462 if (dump_file && (dump_flags & TDF_DETAILS))
4464 for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
4465 if (IPA_NODE_REF (v)->node_dead)
4466 fprintf (dump_file, " Marking node as dead: %s/%i.\n",
4467 v->name (), v->order);
4471 /* The decision stage. Iterate over the topological order of call graph nodes
4472 TOPO and make specialized clones if deemed beneficial. */
4475 ipcp_decision_stage (struct ipa_topo_info *topo)
4480 fprintf (dump_file, "\nIPA decision stage:\n\n");
4482 for (i = topo->nnodes - 1; i >= 0; i--)
4484 struct cgraph_node *node = topo->order[i];
4485 bool change = false, iterate = true;
4489 struct cgraph_node *v;
4491 for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
4492 if (v->has_gimple_body_p ()
4493 && ipcp_versionable_function_p (v))
4494 iterate |= decide_whether_version_node (v);
4499 identify_dead_nodes (node);
4503 /* Look up all alignment information that we have discovered and copy it over
4504 to the transformation summary. */
4507 ipcp_store_alignment_results (void)
4511 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
4513 ipa_node_params *info = IPA_NODE_REF (node);
4514 bool dumped_sth = false;
4515 bool found_useful_result = false;
4517 if (!opt_for_fn (node->decl, flag_ipa_cp_alignment))
4520 fprintf (dump_file, "Not considering %s for alignment discovery "
4521 "and propagate; -fipa-cp-alignment: disabled.\n",
4526 if (info->ipcp_orig_node)
4527 info = IPA_NODE_REF (info->ipcp_orig_node);
4529 unsigned count = ipa_get_param_count (info);
4530 for (unsigned i = 0; i < count ; i++)
4532 ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
4533 if (!plats->alignment.bottom_p ()
4534 && !plats->alignment.top_p ())
4536 gcc_checking_assert (plats->alignment.align > 0);
4537 found_useful_result = true;
4541 if (!found_useful_result)
4544 ipcp_grow_transformations_if_necessary ();
4545 ipcp_transformation_summary *ts = ipcp_get_transformation_summary (node);
4546 vec_safe_reserve_exact (ts->alignments, count);
4548 for (unsigned i = 0; i < count ; i++)
4550 ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
4553 if (!plats->alignment.bottom_p ()
4554 && !plats->alignment.top_p ())
4557 al.align = plats->alignment.align;
4558 al.misalign = plats->alignment.misalign;
4563 ts->alignments->quick_push (al);
4564 if (!dump_file || !al.known)
4568 fprintf (dump_file, "Propagated alignment info for function %s/%i:\n",
4569 node->name (), node->order);
4572 fprintf (dump_file, " param %i: align: %u, misalign: %u\n",
4573 i, al.align, al.misalign);
4578 /* The IPCP driver. */
4583 struct cgraph_2edge_hook_list *edge_duplication_hook_holder;
4584 struct cgraph_edge_hook_list *edge_removal_hook_holder;
4585 struct ipa_topo_info topo;
4587 ipa_check_create_node_params ();
4588 ipa_check_create_edge_args ();
4589 grow_edge_clone_vectors ();
4590 edge_duplication_hook_holder =
4591 symtab->add_edge_duplication_hook (&ipcp_edge_duplication_hook, NULL);
4592 edge_removal_hook_holder =
4593 symtab->add_edge_removal_hook (&ipcp_edge_removal_hook, NULL);
4597 fprintf (dump_file, "\nIPA structures before propagation:\n");
4598 if (dump_flags & TDF_DETAILS)
4599 ipa_print_all_params (dump_file);
4600 ipa_print_all_jump_functions (dump_file);
4603 /* Topological sort. */
4604 build_toporder_info (&topo);
4605 /* Do the interprocedural propagation. */
4606 ipcp_propagate_stage (&topo);
4607 /* Decide what constant propagation and cloning should be performed. */
4608 ipcp_decision_stage (&topo);
4609 /* Store results of alignment propagation. */
4610 ipcp_store_alignment_results ();
4612 /* Free all IPCP structures. */
4613 free_toporder_info (&topo);
4614 next_edge_clone.release ();
4615 prev_edge_clone.release ();
4616 symtab->remove_edge_removal_hook (edge_removal_hook_holder);
4617 symtab->remove_edge_duplication_hook (edge_duplication_hook_holder);
4618 ipa_free_all_structures_after_ipa_cp ();
4620 fprintf (dump_file, "\nIPA constant propagation end\n");
4624 /* Initialization and computation of IPCP data structures. This is the initial
4625 intraprocedural analysis of functions, which gathers information to be
4626 propagated later on. */
4629 ipcp_generate_summary (void)
4631 struct cgraph_node *node;
4634 fprintf (dump_file, "\nIPA constant propagation start:\n");
4635 ipa_register_cgraph_hooks ();
4637 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
4638 ipa_analyze_node (node);
4641 /* Write ipcp summary for nodes in SET. */
4644 ipcp_write_summary (void)
4646 ipa_prop_write_jump_functions ();
4649 /* Read ipcp summary. */
4652 ipcp_read_summary (void)
4654 ipa_prop_read_jump_functions ();
4659 const pass_data pass_data_ipa_cp =
4661 IPA_PASS, /* type */
4663 OPTGROUP_NONE, /* optinfo_flags */
4664 TV_IPA_CONSTANT_PROP, /* tv_id */
4665 0, /* properties_required */
4666 0, /* properties_provided */
4667 0, /* properties_destroyed */
4668 0, /* todo_flags_start */
4669 ( TODO_dump_symtab | TODO_remove_functions ), /* todo_flags_finish */
4672 class pass_ipa_cp : public ipa_opt_pass_d
4675 pass_ipa_cp (gcc::context *ctxt)
4676 : ipa_opt_pass_d (pass_data_ipa_cp, ctxt,
4677 ipcp_generate_summary, /* generate_summary */
4678 ipcp_write_summary, /* write_summary */
4679 ipcp_read_summary, /* read_summary */
4680 ipcp_write_transformation_summaries, /*
4681 write_optimization_summary */
4682 ipcp_read_transformation_summaries, /*
4683 read_optimization_summary */
4684 NULL, /* stmt_fixup */
4685 0, /* function_transform_todo_flags_start */
4686 ipcp_transform_function, /* function_transform */
4687 NULL) /* variable_transform */
4690 /* opt_pass methods: */
4691 virtual bool gate (function *)
4693 /* FIXME: We should remove the optimize check after we ensure we never run
4694 IPA passes when not optimizing. */
4695 return (flag_ipa_cp && optimize) || in_lto_p;
4698 virtual unsigned int execute (function *) { return ipcp_driver (); }
4700 }; // class pass_ipa_cp
4705 make_pass_ipa_cp (gcc::context *ctxt)
4707 return new pass_ipa_cp (ctxt);
4710 /* Reset all state within ipa-cp.c so that we can rerun the compiler
4711 within the same process. For use by toplev::finalize. */
4714 ipa_cp_c_finalize (void)