Fix memory leak in tree-vect-slp.c
[official-gcc.git] / gcc / ipa-cp.c
blob8caa973e46c7fe44a2e99c5d1b9bf618e81a986c
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
5 <mjambor@suse.cz>
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
12 version.
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 for more details.
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
23 /* Interprocedural constant propagation (IPA-CP).
25 The goal of this transformation is to
27 1) discover functions which are always invoked with some arguments with the
28 same known constant values and modify the functions so that the
29 subsequent optimizations can take advantage of the knowledge, and
31 2) partial specialization - create specialized versions of functions
32 transformed in this way if some parameters are known constants only in
33 certain contexts but the estimated tradeoff between speedup and cost size
34 is deemed good.
36 The algorithm also propagates types and attempts to perform type based
37 devirtualization. Types are propagated much like constants.
39 The algorithm basically consists of three stages. In the first, functions
40 are analyzed one at a time and jump functions are constructed for all known
41 call-sites. In the second phase, the pass propagates information from the
42 jump functions across the call to reveal what values are available at what
43 call sites, performs estimations of effects of known values on functions and
44 their callees, and finally decides what specialized extra versions should be
45 created. In the third, the special versions materialize and appropriate
46 calls are redirected.
48 The algorithm used is to a certain extent based on "Interprocedural Constant
49 Propagation", by David Callahan, Keith D Cooper, Ken Kennedy, Linda Torczon,
50 Comp86, pg 152-161 and "A Methodology for Procedure Cloning" by Keith D
51 Cooper, Mary W. Hall, and Ken Kennedy.
54 First stage - intraprocedural analysis
55 =======================================
57 This phase computes jump_function and modification flags.
59 A jump function for a call-site represents the values passed as an actual
60 arguments of a given call-site. In principle, there are three types of
61 values:
63 Pass through - the caller's formal parameter is passed as an actual
64 argument, plus an operation on it can be performed.
65 Constant - a constant is passed as an actual argument.
66 Unknown - neither of the above.
68 All jump function types are described in detail in ipa-prop.h, together with
69 the data structures that represent them and methods of accessing them.
71 ipcp_generate_summary() is the main function of the first stage.
73 Second stage - interprocedural analysis
74 ========================================
76 This stage is itself divided into two phases. In the first, we propagate
77 known values over the call graph, in the second, we make cloning decisions.
78 It uses a different algorithm than the original Callahan's paper.
80 First, we traverse the functions topologically from callers to callees and,
81 for each strongly connected component (SCC), we propagate constants
82 according to previously computed jump functions. We also record what known
83 values depend on other known values and estimate local effects. Finally, we
84 propagate cumulative information about these effects from dependent values
85 to those on which they depend.
87 Second, we again traverse the call graph in the same topological order and
88 make clones for functions which we know are called with the same values in
89 all contexts and decide about extra specialized clones of functions just for
90 some contexts - these decisions are based on both local estimates and
91 cumulative estimates propagated from callees.
93 ipcp_propagate_stage() and ipcp_decision_stage() together constitute the
94 third stage.
96 Third phase - materialization of clones, call statement updates.
97 ============================================
99 This stage is currently performed by call graph code (mainly in cgraphunit.c
100 and tree-inline.c) according to instructions inserted to the call graph by
101 the second stage. */
103 #include "config.h"
104 #include "system.h"
105 #include "coretypes.h"
106 #include "backend.h"
107 #include "tree.h"
108 #include "gimple-expr.h"
109 #include "predict.h"
110 #include "alloc-pool.h"
111 #include "tree-pass.h"
112 #include "cgraph.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"
120 #include "params.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
131 public:
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. */
136 cgraph_edge *cs;
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. */
146 int index;
149 /* Common ancestor for all ipcp_value instantiations. */
151 class ipcp_value_base
153 public:
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
167 public:
168 /* The actual value for the given parameter. */
169 valtype value;
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. */
173 ipcp_value *next;
174 /* Next pointers in a linked list of values in a strongly connected component
175 of values. */
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)
181 created. */
182 cgraph_node *spec_node;
183 /* Depth first search number and low link for topological sorting of
184 values. */
185 int dfs, low_link;
186 /* True if this valye is currently on the topo-sort stack. */
187 bool on_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>
200 class ipcp_lattice
202 public:
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. */
208 int values_count;
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
212 propagation). */
213 bool bottom;
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
225 aggregate. */
227 class ipcp_agg_lattice : public ipcp_lattice<tree>
229 public:
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. */
234 HOST_WIDE_INT size;
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
244 public:
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. */
247 unsigned align;
248 unsigned misalign;
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);
256 private:
257 /* If set, this lattice is bottom and all other fields should be
258 disregarded. */
259 bool bottom;
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
263 state. */
264 bool not_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
275 public:
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 */
285 int aggs_count;
286 /* True if aggregate data were passed by reference (as opposed to by
287 value). */
288 bool aggs_by_ref;
289 /* All aggregate lattices contain a variable component (in addition to
290 values). */
291 bool aggs_contain_variable;
292 /* The value of all aggregate lattices is bottom (i.e. variable and unusable
293 for any propagation). */
294 bool aggs_bottom;
296 /* There is a virtual call based on this parameter. */
297 bool virt_call;
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
352 undefined value. */
354 template <typename valtype>
355 inline bool
356 ipcp_lattice<valtype>::is_single_const ()
358 if (bottom || contains_variable || values_count != 1)
359 return false;
360 else
361 return true;
364 /* Print V which is extracted from a value in a lattice to F. */
366 static void
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)
372 fprintf (f, "& ");
373 print_generic_expr (f, DECL_INITIAL (TREE_OPERAND (v, 0)), 0);
375 else
376 print_generic_expr (f, v, 0);
379 /* Print V which is extracted from a value in a lattice to F. */
381 static void
382 print_ipcp_constant_value (FILE * f, ipa_polymorphic_call_context v)
384 v.dump(f, false);
387 /* Print a lattice LAT to F. */
389 template <typename valtype>
390 void
391 ipcp_lattice<valtype>::print (FILE * f, bool dump_sources, bool dump_benefits)
393 ipcp_value<valtype> *val;
394 bool prev = false;
396 if (bottom)
398 fprintf (f, "BOTTOM\n");
399 return;
402 if (!values_count && !contains_variable)
404 fprintf (f, "TOP\n");
405 return;
408 if (contains_variable)
410 fprintf (f, "VARIABLE");
411 prev = true;
412 if (dump_benefits)
413 fprintf (f, "\n");
416 for (val = values; val; val = val->next)
418 if (dump_benefits && prev)
419 fprintf (f, " ");
420 else if (!dump_benefits && prev)
421 fprintf (f, ", ");
422 else
423 prev = true;
425 print_ipcp_constant_value (f, val->value);
427 if (dump_sources)
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,
434 s->cs->frequency);
435 fprintf (f, "]");
438 if (dump_benefits)
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);
444 if (!dump_benefits)
445 fprintf (f, "\n");
448 /* Print alignment lattice to F. */
450 void
451 ipcp_alignment_lattice::print (FILE * f)
453 if (top_p ())
454 fprintf (f, " Alignment unknown (TOP)\n");
455 else if (bottom_p ())
456 fprintf (f, " Alignment unusable (BOTTOM)\n");
457 else
458 fprintf (f, " Alignment %u, misalignment %u\n", align, misalign);
461 /* Print all ipcp_lattices of all functions to F. */
463 static void
464 print_all_lattices (FILE * f, bool dump_sources, bool dump_benefits)
466 struct cgraph_node *node;
467 int i, count;
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 (),
476 node->order);
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");
493 continue;
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
509 with NODE. */
511 static void
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
519 present. */
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
549 NODE. */
551 static bool
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
561 gcov_type count_sum;
562 int n_calls, n_hot_calls, freq_sum;
565 /* Initialize fields of STAT to zeroes. */
567 static inline void
568 init_caller_stats (struct caller_statistics *stats)
570 stats->count_sum = 0;
571 stats->n_calls = 0;
572 stats->n_hot_calls = 0;
573 stats->freq_sum = 0;
576 /* Worker callback of cgraph_for_node_and_aliases accumulating statistics of
577 non-thunk incoming edges to NODE. */
579 static bool
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;
590 stats->n_calls++;
591 if (cs->maybe_hot_p ())
592 stats->n_hot_calls ++;
594 return false;
598 /* Return true if this NODE is viable candidate for cloning. */
600 static bool
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))
609 if (dump_file)
610 fprintf (dump_file, "Not considering %s for cloning; "
611 "-fipa-cp-clone disabled.\n",
612 node->name ());
613 return false;
616 if (node->optimize_for_size_p ())
618 if (dump_file)
619 fprintf (dump_file, "Not considering %s for cloning; "
620 "optimizing it for size.\n",
621 node->name ());
622 return false;
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)
630 if (dump_file)
631 fprintf (dump_file, "Considering %s for cloning; code might shrink.\n",
632 node->name ());
633 return true;
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
638 significantly. */
639 if (max_count)
641 if (stats.count_sum > node->count * 90 / 100)
643 if (dump_file)
644 fprintf (dump_file, "Considering %s for cloning; "
645 "usually called directly.\n",
646 node->name ());
647 return true;
650 if (!stats.n_hot_calls)
652 if (dump_file)
653 fprintf (dump_file, "Not considering %s for cloning; no hot calls.\n",
654 node->name ());
655 return false;
657 if (dump_file)
658 fprintf (dump_file, "Considering %s for cloning.\n",
659 node->name ());
660 return true;
663 template <typename valtype>
664 class value_topo_info
666 public:
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. */
672 int dfs_counter;
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
683 order. */
685 class ipa_topo_info
687 public:
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),
699 constants ()
703 /* Allocate the arrays in TOPO and topologically sort the nodes into order. */
705 static void
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
716 TOPO. */
718 static void
719 free_toporder_info (struct ipa_topo_info *topo)
721 ipa_free_postorder_info ();
722 free (topo->order);
723 free (topo->stack);
726 /* Add NODE to the stack in TOPO, unless it is already there. */
728 static inline void
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)
733 return;
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
739 is empty. */
741 static struct cgraph_node *
742 pop_node_from_stack (struct ipa_topo_info *topo)
744 if (topo->stack_top)
746 struct cgraph_node *node;
747 topo->stack_top--;
748 node = topo->stack[topo->stack_top];
749 IPA_NODE_REF (node)->node_enqueued = 0;
750 return node;
752 else
753 return NULL;
756 /* Set lattice LAT to bottom and return true if it previously was not set as
757 such. */
759 template <typename valtype>
760 inline bool
761 ipcp_lattice<valtype>::set_to_bottom ()
763 bool ret = !bottom;
764 bottom = true;
765 return ret;
768 /* Mark lattice as containing an unknown value and return true if it previously
769 was not marked as such. */
771 template <typename valtype>
772 inline bool
773 ipcp_lattice<valtype>::set_contains_variable ()
775 bool ret = !contains_variable;
776 contains_variable = true;
777 return ret;
780 /* Set all aggegate lattices in PLATS to bottom and return true if they were
781 not previously set as such. */
783 static inline bool
784 set_agg_lats_to_bottom (struct ipcp_param_lattices *plats)
786 bool ret = !plats->aggs_bottom;
787 plats->aggs_bottom = true;
788 return ret;
791 /* Mark all aggegate lattices in PLATS as containing an unknown value and
792 return true if they were not previously marked as such. */
794 static inline bool
795 set_agg_lats_contain_variable (struct ipcp_param_lattices *plats)
797 bool ret = !plats->aggs_contain_variable;
798 plats->aggs_contain_variable = true;
799 return ret;
802 /* Return true if alignment information in the lattice is yet unknown. */
804 bool
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
811 unusable. */
813 bool
814 ipcp_alignment_lattice::bottom_p () const
816 return bottom;
819 /* Set alignment information in the lattice to bottom. Return true if it
820 previously was in a different state. */
822 bool
823 ipcp_alignment_lattice::set_to_bottom ()
825 if (bottom_p ())
826 return false;
827 bottom = true;
828 return true;
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. */
835 bool
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)
840 return false;
842 bool changed = false;
843 if (align > new_align)
845 align = new_align;
846 misalign = misalign % new_align;
847 changed = true;
849 if (misalign != (new_misalign % align))
851 int diff = abs ((int) misalign - (int) (new_misalign % align));
852 align = (unsigned) diff & -diff;
853 if (align)
854 misalign = misalign % align;
855 else
856 set_to_bottom ();
857 changed = true;
859 gcc_checking_assert (bottom_p () || align != 0);
860 return changed;
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. */
866 bool
867 ipcp_alignment_lattice::meet_with (unsigned new_align, unsigned new_misalign)
869 gcc_assert (new_align != 0);
870 if (bottom_p ())
871 return false;
872 if (top_p ())
874 not_top = true;
875 align = new_align;
876 misalign = new_misalign;
877 return true;
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. */
886 bool
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 ())
893 return false;
895 unsigned adjusted_misalign = (other.misalign + offset) % other.align;
896 if (top_p ())
898 not_top = true;
899 align = other.align;
900 misalign = adjusted_misalign;
901 return true;
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. */
910 static inline bool
911 set_all_contains_variable (struct ipcp_param_lattices *plats)
913 bool ret;
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 ();
918 return ret;
921 /* Worker of call_for_symbol_thunks_and_aliases, increment the integer DATA
922 points to by the number of callers to NODE. */
924 static bool
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)
933 ++*caller_count;
934 return false;
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. */
940 static bool
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;
947 if (cs)
949 IPA_NODE_REF (cs->caller)->node_calling_single_call = true;
950 return true;
952 return false;
955 /* Initialize ipcp_lattices. */
957 static void
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;
963 int i;
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,
970 true);
971 gcc_checking_assert (caller_count > 0);
972 if (caller_count == 1)
973 node->call_for_symbol_thunks_and_aliases (set_single_call_flag,
974 NULL, true);
976 else
978 /* When cloning is allowed, we can assume that externally visible
979 functions are not called. We will compensate this by cloning
980 later. */
981 if (ipcp_versionable_function_p (node)
982 && ipcp_cloning_candidate_p (node))
983 variable = true;
984 else
985 disable = true;
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);
993 if (disable)
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 ();
1000 else
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. */
1024 static tree
1025 ipa_get_jf_pass_through_result (struct ipa_jump_func *jfunc, tree input)
1027 tree restype, res;
1029 if (ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
1030 return input;
1031 if (!is_gimple_ip_invariant (input))
1032 return NULL_TREE;
1034 if (TREE_CODE_CLASS (ipa_get_jf_pass_through_operation (jfunc))
1035 == tcc_comparison)
1036 restype = boolean_type_node;
1037 else
1038 restype = TREE_TYPE (input);
1039 res = fold_binary (ipa_get_jf_pass_through_operation (jfunc), restype,
1040 input, ipa_get_jf_pass_through_operand (jfunc));
1042 if (res && !is_gimple_ip_invariant (res))
1043 return NULL_TREE;
1045 return res;
1048 /* Return the result of an ancestor jump function JFUNC on the constant value
1049 INPUT. Return NULL_TREE if that cannot be determined. */
1051 static tree
1052 ipa_get_jf_ancestor_result (struct ipa_jump_func *jfunc, tree input)
1054 gcc_checking_assert (TREE_CODE (input) != TREE_BINFO);
1055 if (TREE_CODE (input) == ADDR_EXPR)
1057 tree t = TREE_OPERAND (input, 0);
1058 t = build_ref_for_offset (EXPR_LOCATION (t), t,
1059 ipa_get_jf_ancestor_offset (jfunc), false,
1060 ptr_type_node, NULL, false);
1061 return build_fold_addr_expr (t);
1063 else
1064 return NULL_TREE;
1067 /* Determine whether JFUNC evaluates to a single known constant value and if
1068 so, return it. Otherwise return NULL. INFO describes the caller node or
1069 the one it is inlined to, so that pass-through jump functions can be
1070 evaluated. */
1072 tree
1073 ipa_value_from_jfunc (struct ipa_node_params *info, struct ipa_jump_func *jfunc)
1075 if (jfunc->type == IPA_JF_CONST)
1076 return ipa_get_jf_constant (jfunc);
1077 else if (jfunc->type == IPA_JF_PASS_THROUGH
1078 || jfunc->type == IPA_JF_ANCESTOR)
1080 tree input;
1081 int idx;
1083 if (jfunc->type == IPA_JF_PASS_THROUGH)
1084 idx = ipa_get_jf_pass_through_formal_id (jfunc);
1085 else
1086 idx = ipa_get_jf_ancestor_formal_id (jfunc);
1088 if (info->ipcp_orig_node)
1089 input = info->known_csts[idx];
1090 else
1092 ipcp_lattice<tree> *lat;
1094 if (!info->lattices
1095 || idx >= ipa_get_param_count (info))
1096 return NULL_TREE;
1097 lat = ipa_get_scalar_lat (info, idx);
1098 if (!lat->is_single_const ())
1099 return NULL_TREE;
1100 input = lat->values->value;
1103 if (!input)
1104 return NULL_TREE;
1106 if (jfunc->type == IPA_JF_PASS_THROUGH)
1107 return ipa_get_jf_pass_through_result (jfunc, input);
1108 else
1109 return ipa_get_jf_ancestor_result (jfunc, input);
1111 else
1112 return NULL_TREE;
1115 /* Determie whether JFUNC evaluates to single known polymorphic context, given
1116 that INFO describes the caller node or the one it is inlined to, CS is the
1117 call graph edge corresponding to JFUNC and CSIDX index of the described
1118 parameter. */
1120 ipa_polymorphic_call_context
1121 ipa_context_from_jfunc (ipa_node_params *info, cgraph_edge *cs, int csidx,
1122 ipa_jump_func *jfunc)
1124 ipa_edge_args *args = IPA_EDGE_REF (cs);
1125 ipa_polymorphic_call_context ctx;
1126 ipa_polymorphic_call_context *edge_ctx
1127 = cs ? ipa_get_ith_polymorhic_call_context (args, csidx) : NULL;
1129 if (edge_ctx && !edge_ctx->useless_p ())
1130 ctx = *edge_ctx;
1132 if (jfunc->type == IPA_JF_PASS_THROUGH
1133 || jfunc->type == IPA_JF_ANCESTOR)
1135 ipa_polymorphic_call_context srcctx;
1136 int srcidx;
1137 bool type_preserved = true;
1138 if (jfunc->type == IPA_JF_PASS_THROUGH)
1140 if (ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR)
1141 return ctx;
1142 type_preserved = ipa_get_jf_pass_through_type_preserved (jfunc);
1143 srcidx = ipa_get_jf_pass_through_formal_id (jfunc);
1145 else
1147 type_preserved = ipa_get_jf_ancestor_type_preserved (jfunc);
1148 srcidx = ipa_get_jf_ancestor_formal_id (jfunc);
1150 if (info->ipcp_orig_node)
1152 if (info->known_contexts.exists ())
1153 srcctx = info->known_contexts[srcidx];
1155 else
1157 if (!info->lattices
1158 || srcidx >= ipa_get_param_count (info))
1159 return ctx;
1160 ipcp_lattice<ipa_polymorphic_call_context> *lat;
1161 lat = ipa_get_poly_ctx_lat (info, srcidx);
1162 if (!lat->is_single_const ())
1163 return ctx;
1164 srcctx = lat->values->value;
1166 if (srcctx.useless_p ())
1167 return ctx;
1168 if (jfunc->type == IPA_JF_ANCESTOR)
1169 srcctx.offset_by (ipa_get_jf_ancestor_offset (jfunc));
1170 if (!type_preserved)
1171 srcctx.possible_dynamic_type_change (cs->in_polymorphic_cdtor);
1172 srcctx.combine_with (ctx);
1173 return srcctx;
1176 return ctx;
1179 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
1180 bottom, not containing a variable component and without any known value at
1181 the same time. */
1183 DEBUG_FUNCTION void
1184 ipcp_verify_propagated_values (void)
1186 struct cgraph_node *node;
1188 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
1190 struct ipa_node_params *info = IPA_NODE_REF (node);
1191 int i, count = ipa_get_param_count (info);
1193 for (i = 0; i < count; i++)
1195 ipcp_lattice<tree> *lat = ipa_get_scalar_lat (info, i);
1197 if (!lat->bottom
1198 && !lat->contains_variable
1199 && lat->values_count == 0)
1201 if (dump_file)
1203 symtab_node::dump_table (dump_file);
1204 fprintf (dump_file, "\nIPA lattices after constant "
1205 "propagation, before gcc_unreachable:\n");
1206 print_all_lattices (dump_file, true, false);
1209 gcc_unreachable ();
1215 /* Return true iff X and Y should be considered equal values by IPA-CP. */
1217 static bool
1218 values_equal_for_ipcp_p (tree x, tree y)
1220 gcc_checking_assert (x != NULL_TREE && y != NULL_TREE);
1222 if (x == y)
1223 return true;
1225 if (TREE_CODE (x) == ADDR_EXPR
1226 && TREE_CODE (y) == ADDR_EXPR
1227 && TREE_CODE (TREE_OPERAND (x, 0)) == CONST_DECL
1228 && TREE_CODE (TREE_OPERAND (y, 0)) == CONST_DECL)
1229 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x, 0)),
1230 DECL_INITIAL (TREE_OPERAND (y, 0)), 0);
1231 else
1232 return operand_equal_p (x, y, 0);
1235 /* Return true iff X and Y should be considered equal contexts by IPA-CP. */
1237 static bool
1238 values_equal_for_ipcp_p (ipa_polymorphic_call_context x,
1239 ipa_polymorphic_call_context y)
1241 return x.equal_to (y);
1245 /* Add a new value source to the value represented by THIS, marking that a
1246 value comes from edge CS and (if the underlying jump function is a
1247 pass-through or an ancestor one) from a caller value SRC_VAL of a caller
1248 parameter described by SRC_INDEX. OFFSET is negative if the source was the
1249 scalar value of the parameter itself or the offset within an aggregate. */
1251 template <typename valtype>
1252 void
1253 ipcp_value<valtype>::add_source (cgraph_edge *cs, ipcp_value *src_val,
1254 int src_idx, HOST_WIDE_INT offset)
1256 ipcp_value_source<valtype> *src;
1258 src = new (ipcp_sources_pool.allocate ()) ipcp_value_source<valtype>;
1259 src->offset = offset;
1260 src->cs = cs;
1261 src->val = src_val;
1262 src->index = src_idx;
1264 src->next = sources;
1265 sources = src;
1268 /* Allocate a new ipcp_value holding a tree constant, initialize its value to
1269 SOURCE and clear all other fields. */
1271 static ipcp_value<tree> *
1272 allocate_and_init_ipcp_value (tree source)
1274 ipcp_value<tree> *val;
1276 val = ipcp_cst_values_pool.allocate ();
1277 memset (val, 0, sizeof (*val));
1278 val->value = source;
1279 return val;
1282 /* Allocate a new ipcp_value holding a polymorphic context, initialize its
1283 value to SOURCE and clear all other fields. */
1285 static ipcp_value<ipa_polymorphic_call_context> *
1286 allocate_and_init_ipcp_value (ipa_polymorphic_call_context source)
1288 ipcp_value<ipa_polymorphic_call_context> *val;
1290 // TODO
1291 val = ipcp_poly_ctx_values_pool.allocate ();
1292 memset (val, 0, sizeof (*val));
1293 val->value = source;
1294 return val;
1297 /* Try to add NEWVAL to LAT, potentially creating a new ipcp_value for it. CS,
1298 SRC_VAL SRC_INDEX and OFFSET are meant for add_source and have the same
1299 meaning. OFFSET -1 means the source is scalar and not a part of an
1300 aggregate. */
1302 template <typename valtype>
1303 bool
1304 ipcp_lattice<valtype>::add_value (valtype newval, cgraph_edge *cs,
1305 ipcp_value<valtype> *src_val,
1306 int src_idx, HOST_WIDE_INT offset)
1308 ipcp_value<valtype> *val;
1310 if (bottom)
1311 return false;
1313 for (val = values; val; val = val->next)
1314 if (values_equal_for_ipcp_p (val->value, newval))
1316 if (ipa_edge_within_scc (cs))
1318 ipcp_value_source<valtype> *s;
1319 for (s = val->sources; s ; s = s->next)
1320 if (s->cs == cs)
1321 break;
1322 if (s)
1323 return false;
1326 val->add_source (cs, src_val, src_idx, offset);
1327 return false;
1330 if (values_count == PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE))
1332 /* We can only free sources, not the values themselves, because sources
1333 of other values in this SCC might point to them. */
1334 for (val = values; val; val = val->next)
1336 while (val->sources)
1338 ipcp_value_source<valtype> *src = val->sources;
1339 val->sources = src->next;
1340 ipcp_sources_pool.remove ((ipcp_value_source<tree>*)src);
1344 values = NULL;
1345 return set_to_bottom ();
1348 values_count++;
1349 val = allocate_and_init_ipcp_value (newval);
1350 val->add_source (cs, src_val, src_idx, offset);
1351 val->next = values;
1352 values = val;
1353 return true;
1356 /* Propagate values through a pass-through jump function JFUNC associated with
1357 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1358 is the index of the source parameter. */
1360 static bool
1361 propagate_vals_accross_pass_through (cgraph_edge *cs,
1362 ipa_jump_func *jfunc,
1363 ipcp_lattice<tree> *src_lat,
1364 ipcp_lattice<tree> *dest_lat,
1365 int src_idx)
1367 ipcp_value<tree> *src_val;
1368 bool ret = false;
1370 /* Do not create new values when propagating within an SCC because if there
1371 are arithmetic functions with circular dependencies, there is infinite
1372 number of them and we would just make lattices bottom. */
1373 if ((ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR)
1374 && ipa_edge_within_scc (cs))
1375 ret = dest_lat->set_contains_variable ();
1376 else
1377 for (src_val = src_lat->values; src_val; src_val = src_val->next)
1379 tree cstval = ipa_get_jf_pass_through_result (jfunc, src_val->value);
1381 if (cstval)
1382 ret |= dest_lat->add_value (cstval, cs, src_val, src_idx);
1383 else
1384 ret |= dest_lat->set_contains_variable ();
1387 return ret;
1390 /* Propagate values through an ancestor jump function JFUNC associated with
1391 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1392 is the index of the source parameter. */
1394 static bool
1395 propagate_vals_accross_ancestor (struct cgraph_edge *cs,
1396 struct ipa_jump_func *jfunc,
1397 ipcp_lattice<tree> *src_lat,
1398 ipcp_lattice<tree> *dest_lat,
1399 int src_idx)
1401 ipcp_value<tree> *src_val;
1402 bool ret = false;
1404 if (ipa_edge_within_scc (cs))
1405 return dest_lat->set_contains_variable ();
1407 for (src_val = src_lat->values; src_val; src_val = src_val->next)
1409 tree t = ipa_get_jf_ancestor_result (jfunc, src_val->value);
1411 if (t)
1412 ret |= dest_lat->add_value (t, cs, src_val, src_idx);
1413 else
1414 ret |= dest_lat->set_contains_variable ();
1417 return ret;
1420 /* Propagate scalar values across jump function JFUNC that is associated with
1421 edge CS and put the values into DEST_LAT. */
1423 static bool
1424 propagate_scalar_accross_jump_function (struct cgraph_edge *cs,
1425 struct ipa_jump_func *jfunc,
1426 ipcp_lattice<tree> *dest_lat)
1428 if (dest_lat->bottom)
1429 return false;
1431 if (jfunc->type == IPA_JF_CONST)
1433 tree val = ipa_get_jf_constant (jfunc);
1434 return dest_lat->add_value (val, cs, NULL, 0);
1436 else if (jfunc->type == IPA_JF_PASS_THROUGH
1437 || jfunc->type == IPA_JF_ANCESTOR)
1439 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1440 ipcp_lattice<tree> *src_lat;
1441 int src_idx;
1442 bool ret;
1444 if (jfunc->type == IPA_JF_PASS_THROUGH)
1445 src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
1446 else
1447 src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
1449 src_lat = ipa_get_scalar_lat (caller_info, src_idx);
1450 if (src_lat->bottom)
1451 return dest_lat->set_contains_variable ();
1453 /* If we would need to clone the caller and cannot, do not propagate. */
1454 if (!ipcp_versionable_function_p (cs->caller)
1455 && (src_lat->contains_variable
1456 || (src_lat->values_count > 1)))
1457 return dest_lat->set_contains_variable ();
1459 if (jfunc->type == IPA_JF_PASS_THROUGH)
1460 ret = propagate_vals_accross_pass_through (cs, jfunc, src_lat,
1461 dest_lat, src_idx);
1462 else
1463 ret = propagate_vals_accross_ancestor (cs, jfunc, src_lat, dest_lat,
1464 src_idx);
1466 if (src_lat->contains_variable)
1467 ret |= dest_lat->set_contains_variable ();
1469 return ret;
1472 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1473 use it for indirect inlining), we should propagate them too. */
1474 return dest_lat->set_contains_variable ();
1477 /* Propagate scalar values across jump function JFUNC that is associated with
1478 edge CS and describes argument IDX and put the values into DEST_LAT. */
1480 static bool
1481 propagate_context_accross_jump_function (cgraph_edge *cs,
1482 ipa_jump_func *jfunc, int idx,
1483 ipcp_lattice<ipa_polymorphic_call_context> *dest_lat)
1485 ipa_edge_args *args = IPA_EDGE_REF (cs);
1486 if (dest_lat->bottom)
1487 return false;
1488 bool ret = false;
1489 bool added_sth = false;
1490 bool type_preserved = true;
1492 ipa_polymorphic_call_context edge_ctx, *edge_ctx_ptr
1493 = ipa_get_ith_polymorhic_call_context (args, idx);
1495 if (edge_ctx_ptr)
1496 edge_ctx = *edge_ctx_ptr;
1498 if (jfunc->type == IPA_JF_PASS_THROUGH
1499 || jfunc->type == IPA_JF_ANCESTOR)
1501 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1502 int src_idx;
1503 ipcp_lattice<ipa_polymorphic_call_context> *src_lat;
1505 /* TODO: Once we figure out how to propagate speculations, it will
1506 probably be a good idea to switch to speculation if type_preserved is
1507 not set instead of punting. */
1508 if (jfunc->type == IPA_JF_PASS_THROUGH)
1510 if (ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR)
1511 goto prop_fail;
1512 type_preserved = ipa_get_jf_pass_through_type_preserved (jfunc);
1513 src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
1515 else
1517 type_preserved = ipa_get_jf_ancestor_type_preserved (jfunc);
1518 src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
1521 src_lat = ipa_get_poly_ctx_lat (caller_info, src_idx);
1522 /* If we would need to clone the caller and cannot, do not propagate. */
1523 if (!ipcp_versionable_function_p (cs->caller)
1524 && (src_lat->contains_variable
1525 || (src_lat->values_count > 1)))
1526 goto prop_fail;
1528 ipcp_value<ipa_polymorphic_call_context> *src_val;
1529 for (src_val = src_lat->values; src_val; src_val = src_val->next)
1531 ipa_polymorphic_call_context cur = src_val->value;
1533 if (!type_preserved)
1534 cur.possible_dynamic_type_change (cs->in_polymorphic_cdtor);
1535 if (jfunc->type == IPA_JF_ANCESTOR)
1536 cur.offset_by (ipa_get_jf_ancestor_offset (jfunc));
1537 /* TODO: In cases we know how the context is going to be used,
1538 we can improve the result by passing proper OTR_TYPE. */
1539 cur.combine_with (edge_ctx);
1540 if (!cur.useless_p ())
1542 if (src_lat->contains_variable
1543 && !edge_ctx.equal_to (cur))
1544 ret |= dest_lat->set_contains_variable ();
1545 ret |= dest_lat->add_value (cur, cs, src_val, src_idx);
1546 added_sth = true;
1552 prop_fail:
1553 if (!added_sth)
1555 if (!edge_ctx.useless_p ())
1556 ret |= dest_lat->add_value (edge_ctx, cs);
1557 else
1558 ret |= dest_lat->set_contains_variable ();
1561 return ret;
1564 /* Propagate alignments across jump function JFUNC that is associated with
1565 edge CS and update DEST_LAT accordingly. */
1567 static bool
1568 propagate_alignment_accross_jump_function (cgraph_edge *cs,
1569 ipa_jump_func *jfunc,
1570 ipcp_alignment_lattice *dest_lat)
1572 if (dest_lat->bottom_p ())
1573 return false;
1575 if (jfunc->type == IPA_JF_PASS_THROUGH
1576 || jfunc->type == IPA_JF_ANCESTOR)
1578 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1579 HOST_WIDE_INT offset = 0;
1580 int src_idx;
1582 if (jfunc->type == IPA_JF_PASS_THROUGH)
1584 enum tree_code op = ipa_get_jf_pass_through_operation (jfunc);
1585 if (op != NOP_EXPR)
1587 if (op != POINTER_PLUS_EXPR
1588 && op != PLUS_EXPR)
1589 return dest_lat->set_to_bottom ();
1590 tree operand = ipa_get_jf_pass_through_operand (jfunc);
1591 if (!tree_fits_shwi_p (operand))
1592 return dest_lat->set_to_bottom ();
1593 offset = tree_to_shwi (operand);
1595 src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
1597 else
1599 src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
1600 offset = ipa_get_jf_ancestor_offset (jfunc) / BITS_PER_UNIT;
1603 struct ipcp_param_lattices *src_lats;
1604 src_lats = ipa_get_parm_lattices (caller_info, src_idx);
1605 return dest_lat->meet_with (src_lats->alignment, offset);
1607 else
1609 if (jfunc->alignment.known)
1610 return dest_lat->meet_with (jfunc->alignment.align,
1611 jfunc->alignment.misalign);
1612 else
1613 return dest_lat->set_to_bottom ();
1617 /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
1618 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
1619 other cases, return false). If there are no aggregate items, set
1620 aggs_by_ref to NEW_AGGS_BY_REF. */
1622 static bool
1623 set_check_aggs_by_ref (struct ipcp_param_lattices *dest_plats,
1624 bool new_aggs_by_ref)
1626 if (dest_plats->aggs)
1628 if (dest_plats->aggs_by_ref != new_aggs_by_ref)
1630 set_agg_lats_to_bottom (dest_plats);
1631 return true;
1634 else
1635 dest_plats->aggs_by_ref = new_aggs_by_ref;
1636 return false;
1639 /* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
1640 already existing lattice for the given OFFSET and SIZE, marking all skipped
1641 lattices as containing variable and checking for overlaps. If there is no
1642 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
1643 it with offset, size and contains_variable to PRE_EXISTING, and return true,
1644 unless there are too many already. If there are two many, return false. If
1645 there are overlaps turn whole DEST_PLATS to bottom and return false. If any
1646 skipped lattices were newly marked as containing variable, set *CHANGE to
1647 true. */
1649 static bool
1650 merge_agg_lats_step (struct ipcp_param_lattices *dest_plats,
1651 HOST_WIDE_INT offset, HOST_WIDE_INT val_size,
1652 struct ipcp_agg_lattice ***aglat,
1653 bool pre_existing, bool *change)
1655 gcc_checking_assert (offset >= 0);
1657 while (**aglat && (**aglat)->offset < offset)
1659 if ((**aglat)->offset + (**aglat)->size > offset)
1661 set_agg_lats_to_bottom (dest_plats);
1662 return false;
1664 *change |= (**aglat)->set_contains_variable ();
1665 *aglat = &(**aglat)->next;
1668 if (**aglat && (**aglat)->offset == offset)
1670 if ((**aglat)->size != val_size
1671 || ((**aglat)->next
1672 && (**aglat)->next->offset < offset + val_size))
1674 set_agg_lats_to_bottom (dest_plats);
1675 return false;
1677 gcc_checking_assert (!(**aglat)->next
1678 || (**aglat)->next->offset >= offset + val_size);
1679 return true;
1681 else
1683 struct ipcp_agg_lattice *new_al;
1685 if (**aglat && (**aglat)->offset < offset + val_size)
1687 set_agg_lats_to_bottom (dest_plats);
1688 return false;
1690 if (dest_plats->aggs_count == PARAM_VALUE (PARAM_IPA_MAX_AGG_ITEMS))
1691 return false;
1692 dest_plats->aggs_count++;
1693 new_al = ipcp_agg_lattice_pool.allocate ();
1694 memset (new_al, 0, sizeof (*new_al));
1696 new_al->offset = offset;
1697 new_al->size = val_size;
1698 new_al->contains_variable = pre_existing;
1700 new_al->next = **aglat;
1701 **aglat = new_al;
1702 return true;
1706 /* Set all AGLAT and all other aggregate lattices reachable by next pointers as
1707 containing an unknown value. */
1709 static bool
1710 set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice *aglat)
1712 bool ret = false;
1713 while (aglat)
1715 ret |= aglat->set_contains_variable ();
1716 aglat = aglat->next;
1718 return ret;
1721 /* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
1722 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source
1723 parameter used for lattice value sources. Return true if DEST_PLATS changed
1724 in any way. */
1726 static bool
1727 merge_aggregate_lattices (struct cgraph_edge *cs,
1728 struct ipcp_param_lattices *dest_plats,
1729 struct ipcp_param_lattices *src_plats,
1730 int src_idx, HOST_WIDE_INT offset_delta)
1732 bool pre_existing = dest_plats->aggs != NULL;
1733 struct ipcp_agg_lattice **dst_aglat;
1734 bool ret = false;
1736 if (set_check_aggs_by_ref (dest_plats, src_plats->aggs_by_ref))
1737 return true;
1738 if (src_plats->aggs_bottom)
1739 return set_agg_lats_contain_variable (dest_plats);
1740 if (src_plats->aggs_contain_variable)
1741 ret |= set_agg_lats_contain_variable (dest_plats);
1742 dst_aglat = &dest_plats->aggs;
1744 for (struct ipcp_agg_lattice *src_aglat = src_plats->aggs;
1745 src_aglat;
1746 src_aglat = src_aglat->next)
1748 HOST_WIDE_INT new_offset = src_aglat->offset - offset_delta;
1750 if (new_offset < 0)
1751 continue;
1752 if (merge_agg_lats_step (dest_plats, new_offset, src_aglat->size,
1753 &dst_aglat, pre_existing, &ret))
1755 struct ipcp_agg_lattice *new_al = *dst_aglat;
1757 dst_aglat = &(*dst_aglat)->next;
1758 if (src_aglat->bottom)
1760 ret |= new_al->set_contains_variable ();
1761 continue;
1763 if (src_aglat->contains_variable)
1764 ret |= new_al->set_contains_variable ();
1765 for (ipcp_value<tree> *val = src_aglat->values;
1766 val;
1767 val = val->next)
1768 ret |= new_al->add_value (val->value, cs, val, src_idx,
1769 src_aglat->offset);
1771 else if (dest_plats->aggs_bottom)
1772 return true;
1774 ret |= set_chain_of_aglats_contains_variable (*dst_aglat);
1775 return ret;
1778 /* Determine whether there is anything to propagate FROM SRC_PLATS through a
1779 pass-through JFUNC and if so, whether it has conform and conforms to the
1780 rules about propagating values passed by reference. */
1782 static bool
1783 agg_pass_through_permissible_p (struct ipcp_param_lattices *src_plats,
1784 struct ipa_jump_func *jfunc)
1786 return src_plats->aggs
1787 && (!src_plats->aggs_by_ref
1788 || ipa_get_jf_pass_through_agg_preserved (jfunc));
1791 /* Propagate scalar values across jump function JFUNC that is associated with
1792 edge CS and put the values into DEST_LAT. */
1794 static bool
1795 propagate_aggs_accross_jump_function (struct cgraph_edge *cs,
1796 struct ipa_jump_func *jfunc,
1797 struct ipcp_param_lattices *dest_plats)
1799 bool ret = false;
1801 if (dest_plats->aggs_bottom)
1802 return false;
1804 if (jfunc->type == IPA_JF_PASS_THROUGH
1805 && ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
1807 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1808 int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
1809 struct ipcp_param_lattices *src_plats;
1811 src_plats = ipa_get_parm_lattices (caller_info, src_idx);
1812 if (agg_pass_through_permissible_p (src_plats, jfunc))
1814 /* Currently we do not produce clobber aggregate jump
1815 functions, replace with merging when we do. */
1816 gcc_assert (!jfunc->agg.items);
1817 ret |= merge_aggregate_lattices (cs, dest_plats, src_plats,
1818 src_idx, 0);
1820 else
1821 ret |= set_agg_lats_contain_variable (dest_plats);
1823 else if (jfunc->type == IPA_JF_ANCESTOR
1824 && ipa_get_jf_ancestor_agg_preserved (jfunc))
1826 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1827 int src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
1828 struct ipcp_param_lattices *src_plats;
1830 src_plats = ipa_get_parm_lattices (caller_info, src_idx);
1831 if (src_plats->aggs && src_plats->aggs_by_ref)
1833 /* Currently we do not produce clobber aggregate jump
1834 functions, replace with merging when we do. */
1835 gcc_assert (!jfunc->agg.items);
1836 ret |= merge_aggregate_lattices (cs, dest_plats, src_plats, src_idx,
1837 ipa_get_jf_ancestor_offset (jfunc));
1839 else if (!src_plats->aggs_by_ref)
1840 ret |= set_agg_lats_to_bottom (dest_plats);
1841 else
1842 ret |= set_agg_lats_contain_variable (dest_plats);
1844 else if (jfunc->agg.items)
1846 bool pre_existing = dest_plats->aggs != NULL;
1847 struct ipcp_agg_lattice **aglat = &dest_plats->aggs;
1848 struct ipa_agg_jf_item *item;
1849 int i;
1851 if (set_check_aggs_by_ref (dest_plats, jfunc->agg.by_ref))
1852 return true;
1854 FOR_EACH_VEC_ELT (*jfunc->agg.items, i, item)
1856 HOST_WIDE_INT val_size;
1858 if (item->offset < 0)
1859 continue;
1860 gcc_checking_assert (is_gimple_ip_invariant (item->value));
1861 val_size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (item->value)));
1863 if (merge_agg_lats_step (dest_plats, item->offset, val_size,
1864 &aglat, pre_existing, &ret))
1866 ret |= (*aglat)->add_value (item->value, cs, NULL, 0, 0);
1867 aglat = &(*aglat)->next;
1869 else if (dest_plats->aggs_bottom)
1870 return true;
1873 ret |= set_chain_of_aglats_contains_variable (*aglat);
1875 else
1876 ret |= set_agg_lats_contain_variable (dest_plats);
1878 return ret;
1881 /* Return true if on the way cfrom CS->caller to the final (non-alias and
1882 non-thunk) destination, the call passes through a thunk. */
1884 static bool
1885 call_passes_through_thunk_p (cgraph_edge *cs)
1887 cgraph_node *alias_or_thunk = cs->callee;
1888 while (alias_or_thunk->alias)
1889 alias_or_thunk = alias_or_thunk->get_alias_target ();
1890 return alias_or_thunk->thunk.thunk_p;
1893 /* Propagate constants from the caller to the callee of CS. INFO describes the
1894 caller. */
1896 static bool
1897 propagate_constants_accross_call (struct cgraph_edge *cs)
1899 struct ipa_node_params *callee_info;
1900 enum availability availability;
1901 cgraph_node *callee;
1902 struct ipa_edge_args *args;
1903 bool ret = false;
1904 int i, args_count, parms_count;
1906 callee = cs->callee->function_symbol (&availability);
1907 if (!callee->definition)
1908 return false;
1909 gcc_checking_assert (callee->has_gimple_body_p ());
1910 callee_info = IPA_NODE_REF (callee);
1912 args = IPA_EDGE_REF (cs);
1913 args_count = ipa_get_cs_argument_count (args);
1914 parms_count = ipa_get_param_count (callee_info);
1915 if (parms_count == 0)
1916 return false;
1918 /* No propagation through instrumentation thunks is available yet.
1919 It should be possible with proper mapping of call args and
1920 instrumented callee params in the propagation loop below. But
1921 this case mostly occurs when legacy code calls instrumented code
1922 and it is not a primary target for optimizations.
1923 We detect instrumentation thunks in aliases and thunks chain by
1924 checking instrumentation_clone flag for chain source and target.
1925 Going through instrumentation thunks we always have it changed
1926 from 0 to 1 and all other nodes do not change it. */
1927 if (!cs->callee->instrumentation_clone
1928 && callee->instrumentation_clone)
1930 for (i = 0; i < parms_count; i++)
1931 ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info,
1932 i));
1933 return ret;
1936 /* If this call goes through a thunk we must not propagate to the first (0th)
1937 parameter. However, we might need to uncover a thunk from below a series
1938 of aliases first. */
1939 if (call_passes_through_thunk_p (cs))
1941 ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info,
1942 0));
1943 i = 1;
1945 else
1946 i = 0;
1948 for (; (i < args_count) && (i < parms_count); i++)
1950 struct ipa_jump_func *jump_func = ipa_get_ith_jump_func (args, i);
1951 struct ipcp_param_lattices *dest_plats;
1953 dest_plats = ipa_get_parm_lattices (callee_info, i);
1954 if (availability == AVAIL_INTERPOSABLE)
1955 ret |= set_all_contains_variable (dest_plats);
1956 else
1958 ret |= propagate_scalar_accross_jump_function (cs, jump_func,
1959 &dest_plats->itself);
1960 ret |= propagate_context_accross_jump_function (cs, jump_func, i,
1961 &dest_plats->ctxlat);
1962 ret |= propagate_alignment_accross_jump_function (cs, jump_func,
1963 &dest_plats->alignment);
1964 ret |= propagate_aggs_accross_jump_function (cs, jump_func,
1965 dest_plats);
1968 for (; i < parms_count; i++)
1969 ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info, i));
1971 return ret;
1974 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
1975 KNOWN_CONTEXTS, KNOWN_AGGS or AGG_REPS return the destination. The latter
1976 three can be NULL. If AGG_REPS is not NULL, KNOWN_AGGS is ignored. */
1978 static tree
1979 ipa_get_indirect_edge_target_1 (struct cgraph_edge *ie,
1980 vec<tree> known_csts,
1981 vec<ipa_polymorphic_call_context> known_contexts,
1982 vec<ipa_agg_jump_function_p> known_aggs,
1983 struct ipa_agg_replacement_value *agg_reps,
1984 bool *speculative)
1986 int param_index = ie->indirect_info->param_index;
1987 HOST_WIDE_INT anc_offset;
1988 tree t;
1989 tree target = NULL;
1991 *speculative = false;
1993 if (param_index == -1
1994 || known_csts.length () <= (unsigned int) param_index)
1995 return NULL_TREE;
1997 if (!ie->indirect_info->polymorphic)
1999 tree t;
2001 if (ie->indirect_info->agg_contents)
2003 t = NULL;
2004 if (agg_reps && ie->indirect_info->guaranteed_unmodified)
2006 while (agg_reps)
2008 if (agg_reps->index == param_index
2009 && agg_reps->offset == ie->indirect_info->offset
2010 && agg_reps->by_ref == ie->indirect_info->by_ref)
2012 t = agg_reps->value;
2013 break;
2015 agg_reps = agg_reps->next;
2018 if (!t)
2020 struct ipa_agg_jump_function *agg;
2021 if (known_aggs.length () > (unsigned int) param_index)
2022 agg = known_aggs[param_index];
2023 else
2024 agg = NULL;
2025 bool from_global_constant;
2026 t = ipa_find_agg_cst_for_param (agg, known_csts[param_index],
2027 ie->indirect_info->offset,
2028 ie->indirect_info->by_ref,
2029 &from_global_constant);
2030 if (!from_global_constant
2031 && !ie->indirect_info->guaranteed_unmodified)
2032 t = NULL_TREE;
2035 else
2036 t = known_csts[param_index];
2038 if (t &&
2039 TREE_CODE (t) == ADDR_EXPR
2040 && TREE_CODE (TREE_OPERAND (t, 0)) == FUNCTION_DECL)
2041 return TREE_OPERAND (t, 0);
2042 else
2043 return NULL_TREE;
2046 if (!opt_for_fn (ie->caller->decl, flag_devirtualize))
2047 return NULL_TREE;
2049 gcc_assert (!ie->indirect_info->agg_contents);
2050 anc_offset = ie->indirect_info->offset;
2052 t = NULL;
2054 /* Try to work out value of virtual table pointer value in replacemnets. */
2055 if (!t && agg_reps && !ie->indirect_info->by_ref)
2057 while (agg_reps)
2059 if (agg_reps->index == param_index
2060 && agg_reps->offset == ie->indirect_info->offset
2061 && agg_reps->by_ref)
2063 t = agg_reps->value;
2064 break;
2066 agg_reps = agg_reps->next;
2070 /* Try to work out value of virtual table pointer value in known
2071 aggregate values. */
2072 if (!t && known_aggs.length () > (unsigned int) param_index
2073 && !ie->indirect_info->by_ref)
2075 struct ipa_agg_jump_function *agg;
2076 agg = known_aggs[param_index];
2077 t = ipa_find_agg_cst_for_param (agg, known_csts[param_index],
2078 ie->indirect_info->offset,
2079 true);
2082 /* If we found the virtual table pointer, lookup the target. */
2083 if (t)
2085 tree vtable;
2086 unsigned HOST_WIDE_INT offset;
2087 if (vtable_pointer_value_to_vtable (t, &vtable, &offset))
2089 bool can_refer;
2090 target = gimple_get_virt_method_for_vtable (ie->indirect_info->otr_token,
2091 vtable, offset, &can_refer);
2092 if (can_refer)
2094 if (!target
2095 || (TREE_CODE (TREE_TYPE (target)) == FUNCTION_TYPE
2096 && DECL_FUNCTION_CODE (target) == BUILT_IN_UNREACHABLE)
2097 || !possible_polymorphic_call_target_p
2098 (ie, cgraph_node::get (target)))
2100 /* Do not speculate builtin_unreachable, it is stupid! */
2101 if (ie->indirect_info->vptr_changed)
2102 return NULL;
2103 target = ipa_impossible_devirt_target (ie, target);
2105 *speculative = ie->indirect_info->vptr_changed;
2106 if (!*speculative)
2107 return target;
2112 /* Do we know the constant value of pointer? */
2113 if (!t)
2114 t = known_csts[param_index];
2116 gcc_checking_assert (!t || TREE_CODE (t) != TREE_BINFO);
2118 ipa_polymorphic_call_context context;
2119 if (known_contexts.length () > (unsigned int) param_index)
2121 context = known_contexts[param_index];
2122 context.offset_by (anc_offset);
2123 if (ie->indirect_info->vptr_changed)
2124 context.possible_dynamic_type_change (ie->in_polymorphic_cdtor,
2125 ie->indirect_info->otr_type);
2126 if (t)
2128 ipa_polymorphic_call_context ctx2 = ipa_polymorphic_call_context
2129 (t, ie->indirect_info->otr_type, anc_offset);
2130 if (!ctx2.useless_p ())
2131 context.combine_with (ctx2, ie->indirect_info->otr_type);
2134 else if (t)
2136 context = ipa_polymorphic_call_context (t, ie->indirect_info->otr_type,
2137 anc_offset);
2138 if (ie->indirect_info->vptr_changed)
2139 context.possible_dynamic_type_change (ie->in_polymorphic_cdtor,
2140 ie->indirect_info->otr_type);
2142 else
2143 return NULL_TREE;
2145 vec <cgraph_node *>targets;
2146 bool final;
2148 targets = possible_polymorphic_call_targets
2149 (ie->indirect_info->otr_type,
2150 ie->indirect_info->otr_token,
2151 context, &final);
2152 if (!final || targets.length () > 1)
2154 struct cgraph_node *node;
2155 if (*speculative)
2156 return target;
2157 if (!opt_for_fn (ie->caller->decl, flag_devirtualize_speculatively)
2158 || ie->speculative || !ie->maybe_hot_p ())
2159 return NULL;
2160 node = try_speculative_devirtualization (ie->indirect_info->otr_type,
2161 ie->indirect_info->otr_token,
2162 context);
2163 if (node)
2165 *speculative = true;
2166 target = node->decl;
2168 else
2169 return NULL;
2171 else
2173 *speculative = false;
2174 if (targets.length () == 1)
2175 target = targets[0]->decl;
2176 else
2177 target = ipa_impossible_devirt_target (ie, NULL_TREE);
2180 if (target && !possible_polymorphic_call_target_p (ie,
2181 cgraph_node::get (target)))
2183 if (*speculative)
2184 return NULL;
2185 target = ipa_impossible_devirt_target (ie, target);
2188 return target;
2192 /* If an indirect edge IE can be turned into a direct one based on KNOWN_CSTS,
2193 KNOWN_CONTEXTS (which can be vNULL) or KNOWN_AGGS (which also can be vNULL)
2194 return the destination. */
2196 tree
2197 ipa_get_indirect_edge_target (struct cgraph_edge *ie,
2198 vec<tree> known_csts,
2199 vec<ipa_polymorphic_call_context> known_contexts,
2200 vec<ipa_agg_jump_function_p> known_aggs,
2201 bool *speculative)
2203 return ipa_get_indirect_edge_target_1 (ie, known_csts, known_contexts,
2204 known_aggs, NULL, speculative);
2207 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
2208 and KNOWN_CONTEXTS. */
2210 static int
2211 devirtualization_time_bonus (struct cgraph_node *node,
2212 vec<tree> known_csts,
2213 vec<ipa_polymorphic_call_context> known_contexts,
2214 vec<ipa_agg_jump_function_p> known_aggs)
2216 struct cgraph_edge *ie;
2217 int res = 0;
2219 for (ie = node->indirect_calls; ie; ie = ie->next_callee)
2221 struct cgraph_node *callee;
2222 struct inline_summary *isummary;
2223 enum availability avail;
2224 tree target;
2225 bool speculative;
2227 target = ipa_get_indirect_edge_target (ie, known_csts, known_contexts,
2228 known_aggs, &speculative);
2229 if (!target)
2230 continue;
2232 /* Only bare minimum benefit for clearly un-inlineable targets. */
2233 res += 1;
2234 callee = cgraph_node::get (target);
2235 if (!callee || !callee->definition)
2236 continue;
2237 callee = callee->function_symbol (&avail);
2238 if (avail < AVAIL_AVAILABLE)
2239 continue;
2240 isummary = inline_summaries->get (callee);
2241 if (!isummary->inlinable)
2242 continue;
2244 /* FIXME: The values below need re-considering and perhaps also
2245 integrating into the cost metrics, at lest in some very basic way. */
2246 if (isummary->size <= MAX_INLINE_INSNS_AUTO / 4)
2247 res += 31 / ((int)speculative + 1);
2248 else if (isummary->size <= MAX_INLINE_INSNS_AUTO / 2)
2249 res += 15 / ((int)speculative + 1);
2250 else if (isummary->size <= MAX_INLINE_INSNS_AUTO
2251 || DECL_DECLARED_INLINE_P (callee->decl))
2252 res += 7 / ((int)speculative + 1);
2255 return res;
2258 /* Return time bonus incurred because of HINTS. */
2260 static int
2261 hint_time_bonus (inline_hints hints)
2263 int result = 0;
2264 if (hints & (INLINE_HINT_loop_iterations | INLINE_HINT_loop_stride))
2265 result += PARAM_VALUE (PARAM_IPA_CP_LOOP_HINT_BONUS);
2266 if (hints & INLINE_HINT_array_index)
2267 result += PARAM_VALUE (PARAM_IPA_CP_ARRAY_INDEX_HINT_BONUS);
2268 return result;
2271 /* If there is a reason to penalize the function described by INFO in the
2272 cloning goodness evaluation, do so. */
2274 static inline int64_t
2275 incorporate_penalties (ipa_node_params *info, int64_t evaluation)
2277 if (info->node_within_scc)
2278 evaluation = (evaluation
2279 * (100 - PARAM_VALUE (PARAM_IPA_CP_RECURSION_PENALTY))) / 100;
2281 if (info->node_calling_single_call)
2282 evaluation = (evaluation
2283 * (100 - PARAM_VALUE (PARAM_IPA_CP_SINGLE_CALL_PENALTY)))
2284 / 100;
2286 return evaluation;
2289 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
2290 and SIZE_COST and with the sum of frequencies of incoming edges to the
2291 potential new clone in FREQUENCIES. */
2293 static bool
2294 good_cloning_opportunity_p (struct cgraph_node *node, int time_benefit,
2295 int freq_sum, gcov_type count_sum, int size_cost)
2297 if (time_benefit == 0
2298 || !opt_for_fn (node->decl, flag_ipa_cp_clone)
2299 || node->optimize_for_size_p ())
2300 return false;
2302 gcc_assert (size_cost > 0);
2304 struct ipa_node_params *info = IPA_NODE_REF (node);
2305 if (max_count)
2307 int factor = (count_sum * 1000) / max_count;
2308 int64_t evaluation = (((int64_t) time_benefit * factor)
2309 / size_cost);
2310 evaluation = incorporate_penalties (info, evaluation);
2312 if (dump_file && (dump_flags & TDF_DETAILS))
2313 fprintf (dump_file, " good_cloning_opportunity_p (time: %i, "
2314 "size: %i, count_sum: " HOST_WIDE_INT_PRINT_DEC
2315 "%s%s) -> evaluation: " "%" PRId64
2316 ", threshold: %i\n",
2317 time_benefit, size_cost, (HOST_WIDE_INT) count_sum,
2318 info->node_within_scc ? ", scc" : "",
2319 info->node_calling_single_call ? ", single_call" : "",
2320 evaluation, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD));
2322 return evaluation >= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD);
2324 else
2326 int64_t evaluation = (((int64_t) time_benefit * freq_sum)
2327 / size_cost);
2328 evaluation = incorporate_penalties (info, evaluation);
2330 if (dump_file && (dump_flags & TDF_DETAILS))
2331 fprintf (dump_file, " good_cloning_opportunity_p (time: %i, "
2332 "size: %i, freq_sum: %i%s%s) -> evaluation: "
2333 "%" PRId64 ", threshold: %i\n",
2334 time_benefit, size_cost, freq_sum,
2335 info->node_within_scc ? ", scc" : "",
2336 info->node_calling_single_call ? ", single_call" : "",
2337 evaluation, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD));
2339 return evaluation >= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD);
2343 /* Return all context independent values from aggregate lattices in PLATS in a
2344 vector. Return NULL if there are none. */
2346 static vec<ipa_agg_jf_item, va_gc> *
2347 context_independent_aggregate_values (struct ipcp_param_lattices *plats)
2349 vec<ipa_agg_jf_item, va_gc> *res = NULL;
2351 if (plats->aggs_bottom
2352 || plats->aggs_contain_variable
2353 || plats->aggs_count == 0)
2354 return NULL;
2356 for (struct ipcp_agg_lattice *aglat = plats->aggs;
2357 aglat;
2358 aglat = aglat->next)
2359 if (aglat->is_single_const ())
2361 struct ipa_agg_jf_item item;
2362 item.offset = aglat->offset;
2363 item.value = aglat->values->value;
2364 vec_safe_push (res, item);
2366 return res;
2369 /* Allocate KNOWN_CSTS, KNOWN_CONTEXTS and, if non-NULL, KNOWN_AGGS and
2370 populate them with values of parameters that are known independent of the
2371 context. INFO describes the function. If REMOVABLE_PARAMS_COST is
2372 non-NULL, the movement cost of all removable parameters will be stored in
2373 it. */
2375 static bool
2376 gather_context_independent_values (struct ipa_node_params *info,
2377 vec<tree> *known_csts,
2378 vec<ipa_polymorphic_call_context>
2379 *known_contexts,
2380 vec<ipa_agg_jump_function> *known_aggs,
2381 int *removable_params_cost)
2383 int i, count = ipa_get_param_count (info);
2384 bool ret = false;
2386 known_csts->create (0);
2387 known_contexts->create (0);
2388 known_csts->safe_grow_cleared (count);
2389 known_contexts->safe_grow_cleared (count);
2390 if (known_aggs)
2392 known_aggs->create (0);
2393 known_aggs->safe_grow_cleared (count);
2396 if (removable_params_cost)
2397 *removable_params_cost = 0;
2399 for (i = 0; i < count ; i++)
2401 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
2402 ipcp_lattice<tree> *lat = &plats->itself;
2404 if (lat->is_single_const ())
2406 ipcp_value<tree> *val = lat->values;
2407 gcc_checking_assert (TREE_CODE (val->value) != TREE_BINFO);
2408 (*known_csts)[i] = val->value;
2409 if (removable_params_cost)
2410 *removable_params_cost
2411 += estimate_move_cost (TREE_TYPE (val->value), false);
2412 ret = true;
2414 else if (removable_params_cost
2415 && !ipa_is_param_used (info, i))
2416 *removable_params_cost
2417 += ipa_get_param_move_cost (info, i);
2419 if (!ipa_is_param_used (info, i))
2420 continue;
2422 ipcp_lattice<ipa_polymorphic_call_context> *ctxlat = &plats->ctxlat;
2423 /* Do not account known context as reason for cloning. We can see
2424 if it permits devirtualization. */
2425 if (ctxlat->is_single_const ())
2426 (*known_contexts)[i] = ctxlat->values->value;
2428 if (known_aggs)
2430 vec<ipa_agg_jf_item, va_gc> *agg_items;
2431 struct ipa_agg_jump_function *ajf;
2433 agg_items = context_independent_aggregate_values (plats);
2434 ajf = &(*known_aggs)[i];
2435 ajf->items = agg_items;
2436 ajf->by_ref = plats->aggs_by_ref;
2437 ret |= agg_items != NULL;
2441 return ret;
2444 /* The current interface in ipa-inline-analysis requires a pointer vector.
2445 Create it.
2447 FIXME: That interface should be re-worked, this is slightly silly. Still,
2448 I'd like to discuss how to change it first and this demonstrates the
2449 issue. */
2451 static vec<ipa_agg_jump_function_p>
2452 agg_jmp_p_vec_for_t_vec (vec<ipa_agg_jump_function> known_aggs)
2454 vec<ipa_agg_jump_function_p> ret;
2455 struct ipa_agg_jump_function *ajf;
2456 int i;
2458 ret.create (known_aggs.length ());
2459 FOR_EACH_VEC_ELT (known_aggs, i, ajf)
2460 ret.quick_push (ajf);
2461 return ret;
2464 /* Perform time and size measurement of NODE with the context given in
2465 KNOWN_CSTS, KNOWN_CONTEXTS and KNOWN_AGGS, calculate the benefit and cost
2466 given BASE_TIME of the node without specialization, REMOVABLE_PARAMS_COST of
2467 all context-independent removable parameters and EST_MOVE_COST of estimated
2468 movement of the considered parameter and store it into VAL. */
2470 static void
2471 perform_estimation_of_a_value (cgraph_node *node, vec<tree> known_csts,
2472 vec<ipa_polymorphic_call_context> known_contexts,
2473 vec<ipa_agg_jump_function_p> known_aggs_ptrs,
2474 int base_time, int removable_params_cost,
2475 int est_move_cost, ipcp_value_base *val)
2477 int time, size, time_benefit;
2478 inline_hints hints;
2480 estimate_ipcp_clone_size_and_time (node, known_csts, known_contexts,
2481 known_aggs_ptrs, &size, &time,
2482 &hints);
2483 time_benefit = base_time - time
2484 + devirtualization_time_bonus (node, known_csts, known_contexts,
2485 known_aggs_ptrs)
2486 + hint_time_bonus (hints)
2487 + removable_params_cost + est_move_cost;
2489 gcc_checking_assert (size >=0);
2490 /* The inliner-heuristics based estimates may think that in certain
2491 contexts some functions do not have any size at all but we want
2492 all specializations to have at least a tiny cost, not least not to
2493 divide by zero. */
2494 if (size == 0)
2495 size = 1;
2497 val->local_time_benefit = time_benefit;
2498 val->local_size_cost = size;
2501 /* Iterate over known values of parameters of NODE and estimate the local
2502 effects in terms of time and size they have. */
2504 static void
2505 estimate_local_effects (struct cgraph_node *node)
2507 struct ipa_node_params *info = IPA_NODE_REF (node);
2508 int i, count = ipa_get_param_count (info);
2509 vec<tree> known_csts;
2510 vec<ipa_polymorphic_call_context> known_contexts;
2511 vec<ipa_agg_jump_function> known_aggs;
2512 vec<ipa_agg_jump_function_p> known_aggs_ptrs;
2513 bool always_const;
2514 int base_time = inline_summaries->get (node)->time;
2515 int removable_params_cost;
2517 if (!count || !ipcp_versionable_function_p (node))
2518 return;
2520 if (dump_file && (dump_flags & TDF_DETAILS))
2521 fprintf (dump_file, "\nEstimating effects for %s/%i, base_time: %i.\n",
2522 node->name (), node->order, base_time);
2524 always_const = gather_context_independent_values (info, &known_csts,
2525 &known_contexts, &known_aggs,
2526 &removable_params_cost);
2527 known_aggs_ptrs = agg_jmp_p_vec_for_t_vec (known_aggs);
2528 int devirt_bonus = devirtualization_time_bonus (node, known_csts,
2529 known_contexts, known_aggs_ptrs);
2530 if (always_const || devirt_bonus
2531 || (removable_params_cost && node->local.can_change_signature))
2533 struct caller_statistics stats;
2534 inline_hints hints;
2535 int time, size;
2537 init_caller_stats (&stats);
2538 node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats,
2539 false);
2540 estimate_ipcp_clone_size_and_time (node, known_csts, known_contexts,
2541 known_aggs_ptrs, &size, &time, &hints);
2542 time -= devirt_bonus;
2543 time -= hint_time_bonus (hints);
2544 time -= removable_params_cost;
2545 size -= stats.n_calls * removable_params_cost;
2547 if (dump_file)
2548 fprintf (dump_file, " - context independent values, size: %i, "
2549 "time_benefit: %i\n", size, base_time - time);
2551 if (size <= 0 || node->local.local)
2553 info->do_clone_for_all_contexts = true;
2554 base_time = time;
2556 if (dump_file)
2557 fprintf (dump_file, " Decided to specialize for all "
2558 "known contexts, code not going to grow.\n");
2560 else if (good_cloning_opportunity_p (node, base_time - time,
2561 stats.freq_sum, stats.count_sum,
2562 size))
2564 if (size + overall_size <= max_new_size)
2566 info->do_clone_for_all_contexts = true;
2567 base_time = time;
2568 overall_size += size;
2570 if (dump_file)
2571 fprintf (dump_file, " Decided to specialize for all "
2572 "known contexts, growth deemed beneficial.\n");
2574 else if (dump_file && (dump_flags & TDF_DETAILS))
2575 fprintf (dump_file, " Not cloning for all contexts because "
2576 "max_new_size would be reached with %li.\n",
2577 size + overall_size);
2579 else if (dump_file && (dump_flags & TDF_DETAILS))
2580 fprintf (dump_file, " Not cloning for all contexts because "
2581 "!good_cloning_opportunity_p.\n");
2585 for (i = 0; i < count ; i++)
2587 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
2588 ipcp_lattice<tree> *lat = &plats->itself;
2589 ipcp_value<tree> *val;
2591 if (lat->bottom
2592 || !lat->values
2593 || known_csts[i])
2594 continue;
2596 for (val = lat->values; val; val = val->next)
2598 gcc_checking_assert (TREE_CODE (val->value) != TREE_BINFO);
2599 known_csts[i] = val->value;
2601 int emc = estimate_move_cost (TREE_TYPE (val->value), true);
2602 perform_estimation_of_a_value (node, known_csts, known_contexts,
2603 known_aggs_ptrs, base_time,
2604 removable_params_cost, emc, val);
2606 if (dump_file && (dump_flags & TDF_DETAILS))
2608 fprintf (dump_file, " - estimates for value ");
2609 print_ipcp_constant_value (dump_file, val->value);
2610 fprintf (dump_file, " for ");
2611 ipa_dump_param (dump_file, info, i);
2612 fprintf (dump_file, ": time_benefit: %i, size: %i\n",
2613 val->local_time_benefit, val->local_size_cost);
2616 known_csts[i] = NULL_TREE;
2619 for (i = 0; i < count; i++)
2621 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
2623 if (!plats->virt_call)
2624 continue;
2626 ipcp_lattice<ipa_polymorphic_call_context> *ctxlat = &plats->ctxlat;
2627 ipcp_value<ipa_polymorphic_call_context> *val;
2629 if (ctxlat->bottom
2630 || !ctxlat->values
2631 || !known_contexts[i].useless_p ())
2632 continue;
2634 for (val = ctxlat->values; val; val = val->next)
2636 known_contexts[i] = val->value;
2637 perform_estimation_of_a_value (node, known_csts, known_contexts,
2638 known_aggs_ptrs, base_time,
2639 removable_params_cost, 0, val);
2641 if (dump_file && (dump_flags & TDF_DETAILS))
2643 fprintf (dump_file, " - estimates for polymorphic context ");
2644 print_ipcp_constant_value (dump_file, val->value);
2645 fprintf (dump_file, " for ");
2646 ipa_dump_param (dump_file, info, i);
2647 fprintf (dump_file, ": time_benefit: %i, size: %i\n",
2648 val->local_time_benefit, val->local_size_cost);
2651 known_contexts[i] = ipa_polymorphic_call_context ();
2654 for (i = 0; i < count ; i++)
2656 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
2657 struct ipa_agg_jump_function *ajf;
2658 struct ipcp_agg_lattice *aglat;
2660 if (plats->aggs_bottom || !plats->aggs)
2661 continue;
2663 ajf = &known_aggs[i];
2664 for (aglat = plats->aggs; aglat; aglat = aglat->next)
2666 ipcp_value<tree> *val;
2667 if (aglat->bottom || !aglat->values
2668 /* If the following is true, the one value is in known_aggs. */
2669 || (!plats->aggs_contain_variable
2670 && aglat->is_single_const ()))
2671 continue;
2673 for (val = aglat->values; val; val = val->next)
2675 struct ipa_agg_jf_item item;
2677 item.offset = aglat->offset;
2678 item.value = val->value;
2679 vec_safe_push (ajf->items, item);
2681 perform_estimation_of_a_value (node, known_csts, known_contexts,
2682 known_aggs_ptrs, base_time,
2683 removable_params_cost, 0, val);
2685 if (dump_file && (dump_flags & TDF_DETAILS))
2687 fprintf (dump_file, " - estimates for value ");
2688 print_ipcp_constant_value (dump_file, val->value);
2689 fprintf (dump_file, " for ");
2690 ipa_dump_param (dump_file, info, i);
2691 fprintf (dump_file, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
2692 "]: time_benefit: %i, size: %i\n",
2693 plats->aggs_by_ref ? "ref " : "",
2694 aglat->offset,
2695 val->local_time_benefit, val->local_size_cost);
2698 ajf->items->pop ();
2703 for (i = 0; i < count ; i++)
2704 vec_free (known_aggs[i].items);
2706 known_csts.release ();
2707 known_contexts.release ();
2708 known_aggs.release ();
2709 known_aggs_ptrs.release ();
2713 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
2714 topological sort of values. */
2716 template <typename valtype>
2717 void
2718 value_topo_info<valtype>::add_val (ipcp_value<valtype> *cur_val)
2720 ipcp_value_source<valtype> *src;
2722 if (cur_val->dfs)
2723 return;
2725 dfs_counter++;
2726 cur_val->dfs = dfs_counter;
2727 cur_val->low_link = dfs_counter;
2729 cur_val->topo_next = stack;
2730 stack = cur_val;
2731 cur_val->on_stack = true;
2733 for (src = cur_val->sources; src; src = src->next)
2734 if (src->val)
2736 if (src->val->dfs == 0)
2738 add_val (src->val);
2739 if (src->val->low_link < cur_val->low_link)
2740 cur_val->low_link = src->val->low_link;
2742 else if (src->val->on_stack
2743 && src->val->dfs < cur_val->low_link)
2744 cur_val->low_link = src->val->dfs;
2747 if (cur_val->dfs == cur_val->low_link)
2749 ipcp_value<valtype> *v, *scc_list = NULL;
2753 v = stack;
2754 stack = v->topo_next;
2755 v->on_stack = false;
2757 v->scc_next = scc_list;
2758 scc_list = v;
2760 while (v != cur_val);
2762 cur_val->topo_next = values_topo;
2763 values_topo = cur_val;
2767 /* Add all values in lattices associated with NODE to the topological sort if
2768 they are not there yet. */
2770 static void
2771 add_all_node_vals_to_toposort (cgraph_node *node, ipa_topo_info *topo)
2773 struct ipa_node_params *info = IPA_NODE_REF (node);
2774 int i, count = ipa_get_param_count (info);
2776 for (i = 0; i < count ; i++)
2778 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
2779 ipcp_lattice<tree> *lat = &plats->itself;
2780 struct ipcp_agg_lattice *aglat;
2782 if (!lat->bottom)
2784 ipcp_value<tree> *val;
2785 for (val = lat->values; val; val = val->next)
2786 topo->constants.add_val (val);
2789 if (!plats->aggs_bottom)
2790 for (aglat = plats->aggs; aglat; aglat = aglat->next)
2791 if (!aglat->bottom)
2793 ipcp_value<tree> *val;
2794 for (val = aglat->values; val; val = val->next)
2795 topo->constants.add_val (val);
2798 ipcp_lattice<ipa_polymorphic_call_context> *ctxlat = &plats->ctxlat;
2799 if (!ctxlat->bottom)
2801 ipcp_value<ipa_polymorphic_call_context> *ctxval;
2802 for (ctxval = ctxlat->values; ctxval; ctxval = ctxval->next)
2803 topo->contexts.add_val (ctxval);
2808 /* One pass of constants propagation along the call graph edges, from callers
2809 to callees (requires topological ordering in TOPO), iterate over strongly
2810 connected components. */
2812 static void
2813 propagate_constants_topo (struct ipa_topo_info *topo)
2815 int i;
2817 for (i = topo->nnodes - 1; i >= 0; i--)
2819 unsigned j;
2820 struct cgraph_node *v, *node = topo->order[i];
2821 vec<cgraph_node *> cycle_nodes = ipa_get_nodes_in_cycle (node);
2823 /* First, iteratively propagate within the strongly connected component
2824 until all lattices stabilize. */
2825 FOR_EACH_VEC_ELT (cycle_nodes, j, v)
2826 if (v->has_gimple_body_p ())
2827 push_node_to_stack (topo, v);
2829 v = pop_node_from_stack (topo);
2830 while (v)
2832 struct cgraph_edge *cs;
2834 for (cs = v->callees; cs; cs = cs->next_callee)
2835 if (ipa_edge_within_scc (cs))
2837 IPA_NODE_REF (v)->node_within_scc = true;
2838 if (propagate_constants_accross_call (cs))
2839 push_node_to_stack (topo, cs->callee->function_symbol ());
2841 v = pop_node_from_stack (topo);
2844 /* Afterwards, propagate along edges leading out of the SCC, calculates
2845 the local effects of the discovered constants and all valid values to
2846 their topological sort. */
2847 FOR_EACH_VEC_ELT (cycle_nodes, j, v)
2848 if (v->has_gimple_body_p ())
2850 struct cgraph_edge *cs;
2852 estimate_local_effects (v);
2853 add_all_node_vals_to_toposort (v, topo);
2854 for (cs = v->callees; cs; cs = cs->next_callee)
2855 if (!ipa_edge_within_scc (cs))
2856 propagate_constants_accross_call (cs);
2858 cycle_nodes.release ();
2863 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
2864 the bigger one if otherwise. */
2866 static int
2867 safe_add (int a, int b)
2869 if (a > INT_MAX/2 || b > INT_MAX/2)
2870 return a > b ? a : b;
2871 else
2872 return a + b;
2876 /* Propagate the estimated effects of individual values along the topological
2877 from the dependent values to those they depend on. */
2879 template <typename valtype>
2880 void
2881 value_topo_info<valtype>::propagate_effects ()
2883 ipcp_value<valtype> *base;
2885 for (base = values_topo; base; base = base->topo_next)
2887 ipcp_value_source<valtype> *src;
2888 ipcp_value<valtype> *val;
2889 int time = 0, size = 0;
2891 for (val = base; val; val = val->scc_next)
2893 time = safe_add (time,
2894 val->local_time_benefit + val->prop_time_benefit);
2895 size = safe_add (size, val->local_size_cost + val->prop_size_cost);
2898 for (val = base; val; val = val->scc_next)
2899 for (src = val->sources; src; src = src->next)
2900 if (src->val
2901 && src->cs->maybe_hot_p ())
2903 src->val->prop_time_benefit = safe_add (time,
2904 src->val->prop_time_benefit);
2905 src->val->prop_size_cost = safe_add (size,
2906 src->val->prop_size_cost);
2912 /* Propagate constants, polymorphic contexts and their effects from the
2913 summaries interprocedurally. */
2915 static void
2916 ipcp_propagate_stage (struct ipa_topo_info *topo)
2918 struct cgraph_node *node;
2920 if (dump_file)
2921 fprintf (dump_file, "\n Propagating constants:\n\n");
2923 if (in_lto_p)
2924 ipa_update_after_lto_read ();
2927 FOR_EACH_DEFINED_FUNCTION (node)
2929 struct ipa_node_params *info = IPA_NODE_REF (node);
2931 determine_versionability (node, info);
2932 if (node->has_gimple_body_p ())
2934 info->lattices = XCNEWVEC (struct ipcp_param_lattices,
2935 ipa_get_param_count (info));
2936 initialize_node_lattices (node);
2938 if (node->definition && !node->alias)
2939 overall_size += inline_summaries->get (node)->self_size;
2940 if (node->count > max_count)
2941 max_count = node->count;
2944 max_new_size = overall_size;
2945 if (max_new_size < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
2946 max_new_size = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
2947 max_new_size += max_new_size * PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH) / 100 + 1;
2949 if (dump_file)
2950 fprintf (dump_file, "\noverall_size: %li, max_new_size: %li\n",
2951 overall_size, max_new_size);
2953 propagate_constants_topo (topo);
2954 if (flag_checking)
2955 ipcp_verify_propagated_values ();
2956 topo->constants.propagate_effects ();
2957 topo->contexts.propagate_effects ();
2959 if (dump_file)
2961 fprintf (dump_file, "\nIPA lattices after all propagation:\n");
2962 print_all_lattices (dump_file, (dump_flags & TDF_DETAILS), true);
2966 /* Discover newly direct outgoing edges from NODE which is a new clone with
2967 known KNOWN_CSTS and make them direct. */
2969 static void
2970 ipcp_discover_new_direct_edges (struct cgraph_node *node,
2971 vec<tree> known_csts,
2972 vec<ipa_polymorphic_call_context>
2973 known_contexts,
2974 struct ipa_agg_replacement_value *aggvals)
2976 struct cgraph_edge *ie, *next_ie;
2977 bool found = false;
2979 for (ie = node->indirect_calls; ie; ie = next_ie)
2981 tree target;
2982 bool speculative;
2984 next_ie = ie->next_callee;
2985 target = ipa_get_indirect_edge_target_1 (ie, known_csts, known_contexts,
2986 vNULL, aggvals, &speculative);
2987 if (target)
2989 bool agg_contents = ie->indirect_info->agg_contents;
2990 bool polymorphic = ie->indirect_info->polymorphic;
2991 int param_index = ie->indirect_info->param_index;
2992 struct cgraph_edge *cs = ipa_make_edge_direct_to_target (ie, target,
2993 speculative);
2994 found = true;
2996 if (cs && !agg_contents && !polymorphic)
2998 struct ipa_node_params *info = IPA_NODE_REF (node);
2999 int c = ipa_get_controlled_uses (info, param_index);
3000 if (c != IPA_UNDESCRIBED_USE)
3002 struct ipa_ref *to_del;
3004 c--;
3005 ipa_set_controlled_uses (info, param_index, c);
3006 if (dump_file && (dump_flags & TDF_DETAILS))
3007 fprintf (dump_file, " controlled uses count of param "
3008 "%i bumped down to %i\n", param_index, c);
3009 if (c == 0
3010 && (to_del = node->find_reference (cs->callee, NULL, 0)))
3012 if (dump_file && (dump_flags & TDF_DETAILS))
3013 fprintf (dump_file, " and even removing its "
3014 "cloning-created reference\n");
3015 to_del->remove_reference ();
3021 /* Turning calls to direct calls will improve overall summary. */
3022 if (found)
3023 inline_update_overall_summary (node);
3026 /* Vector of pointers which for linked lists of clones of an original crgaph
3027 edge. */
3029 static vec<cgraph_edge *> next_edge_clone;
3030 static vec<cgraph_edge *> prev_edge_clone;
3032 static inline void
3033 grow_edge_clone_vectors (void)
3035 if (next_edge_clone.length ()
3036 <= (unsigned) symtab->edges_max_uid)
3037 next_edge_clone.safe_grow_cleared (symtab->edges_max_uid + 1);
3038 if (prev_edge_clone.length ()
3039 <= (unsigned) symtab->edges_max_uid)
3040 prev_edge_clone.safe_grow_cleared (symtab->edges_max_uid + 1);
3043 /* Edge duplication hook to grow the appropriate linked list in
3044 next_edge_clone. */
3046 static void
3047 ipcp_edge_duplication_hook (struct cgraph_edge *src, struct cgraph_edge *dst,
3048 void *)
3050 grow_edge_clone_vectors ();
3052 struct cgraph_edge *old_next = next_edge_clone[src->uid];
3053 if (old_next)
3054 prev_edge_clone[old_next->uid] = dst;
3055 prev_edge_clone[dst->uid] = src;
3057 next_edge_clone[dst->uid] = old_next;
3058 next_edge_clone[src->uid] = dst;
3061 /* Hook that is called by cgraph.c when an edge is removed. */
3063 static void
3064 ipcp_edge_removal_hook (struct cgraph_edge *cs, void *)
3066 grow_edge_clone_vectors ();
3068 struct cgraph_edge *prev = prev_edge_clone[cs->uid];
3069 struct cgraph_edge *next = next_edge_clone[cs->uid];
3070 if (prev)
3071 next_edge_clone[prev->uid] = next;
3072 if (next)
3073 prev_edge_clone[next->uid] = prev;
3076 /* See if NODE is a clone with a known aggregate value at a given OFFSET of a
3077 parameter with the given INDEX. */
3079 static tree
3080 get_clone_agg_value (struct cgraph_node *node, HOST_WIDE_INT offset,
3081 int index)
3083 struct ipa_agg_replacement_value *aggval;
3085 aggval = ipa_get_agg_replacements_for_node (node);
3086 while (aggval)
3088 if (aggval->offset == offset
3089 && aggval->index == index)
3090 return aggval->value;
3091 aggval = aggval->next;
3093 return NULL_TREE;
3096 /* Return true is NODE is DEST or its clone for all contexts. */
3098 static bool
3099 same_node_or_its_all_contexts_clone_p (cgraph_node *node, cgraph_node *dest)
3101 if (node == dest)
3102 return true;
3104 struct ipa_node_params *info = IPA_NODE_REF (node);
3105 return info->is_all_contexts_clone && info->ipcp_orig_node == dest;
3108 /* Return true if edge CS does bring about the value described by SRC to node
3109 DEST or its clone for all contexts. */
3111 static bool
3112 cgraph_edge_brings_value_p (cgraph_edge *cs, ipcp_value_source<tree> *src,
3113 cgraph_node *dest)
3115 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
3116 enum availability availability;
3117 cgraph_node *real_dest = cs->callee->function_symbol (&availability);
3119 if (!same_node_or_its_all_contexts_clone_p (real_dest, dest)
3120 || availability <= AVAIL_INTERPOSABLE
3121 || caller_info->node_dead)
3122 return false;
3123 if (!src->val)
3124 return true;
3126 if (caller_info->ipcp_orig_node)
3128 tree t;
3129 if (src->offset == -1)
3130 t = caller_info->known_csts[src->index];
3131 else
3132 t = get_clone_agg_value (cs->caller, src->offset, src->index);
3133 return (t != NULL_TREE
3134 && values_equal_for_ipcp_p (src->val->value, t));
3136 else
3138 struct ipcp_agg_lattice *aglat;
3139 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (caller_info,
3140 src->index);
3141 if (src->offset == -1)
3142 return (plats->itself.is_single_const ()
3143 && values_equal_for_ipcp_p (src->val->value,
3144 plats->itself.values->value));
3145 else
3147 if (plats->aggs_bottom || plats->aggs_contain_variable)
3148 return false;
3149 for (aglat = plats->aggs; aglat; aglat = aglat->next)
3150 if (aglat->offset == src->offset)
3151 return (aglat->is_single_const ()
3152 && values_equal_for_ipcp_p (src->val->value,
3153 aglat->values->value));
3155 return false;
3159 /* Return true if edge CS does bring about the value described by SRC to node
3160 DEST or its clone for all contexts. */
3162 static bool
3163 cgraph_edge_brings_value_p (cgraph_edge *cs,
3164 ipcp_value_source<ipa_polymorphic_call_context> *src,
3165 cgraph_node *dest)
3167 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
3168 cgraph_node *real_dest = cs->callee->function_symbol ();
3170 if (!same_node_or_its_all_contexts_clone_p (real_dest, dest)
3171 || caller_info->node_dead)
3172 return false;
3173 if (!src->val)
3174 return true;
3176 if (caller_info->ipcp_orig_node)
3177 return (caller_info->known_contexts.length () > (unsigned) src->index)
3178 && values_equal_for_ipcp_p (src->val->value,
3179 caller_info->known_contexts[src->index]);
3181 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (caller_info,
3182 src->index);
3183 return plats->ctxlat.is_single_const ()
3184 && values_equal_for_ipcp_p (src->val->value,
3185 plats->ctxlat.values->value);
3188 /* Get the next clone in the linked list of clones of an edge. */
3190 static inline struct cgraph_edge *
3191 get_next_cgraph_edge_clone (struct cgraph_edge *cs)
3193 return next_edge_clone[cs->uid];
3196 /* Given VAL that is intended for DEST, iterate over all its sources and if
3197 they still hold, add their edge frequency and their number into *FREQUENCY
3198 and *CALLER_COUNT respectively. */
3200 template <typename valtype>
3201 static bool
3202 get_info_about_necessary_edges (ipcp_value<valtype> *val, cgraph_node *dest,
3203 int *freq_sum,
3204 gcov_type *count_sum, int *caller_count)
3206 ipcp_value_source<valtype> *src;
3207 int freq = 0, count = 0;
3208 gcov_type cnt = 0;
3209 bool hot = false;
3211 for (src = val->sources; src; src = src->next)
3213 struct cgraph_edge *cs = src->cs;
3214 while (cs)
3216 if (cgraph_edge_brings_value_p (cs, src, dest))
3218 count++;
3219 freq += cs->frequency;
3220 cnt += cs->count;
3221 hot |= cs->maybe_hot_p ();
3223 cs = get_next_cgraph_edge_clone (cs);
3227 *freq_sum = freq;
3228 *count_sum = cnt;
3229 *caller_count = count;
3230 return hot;
3233 /* Return a vector of incoming edges that do bring value VAL to node DEST. It
3234 is assumed their number is known and equal to CALLER_COUNT. */
3236 template <typename valtype>
3237 static vec<cgraph_edge *>
3238 gather_edges_for_value (ipcp_value<valtype> *val, cgraph_node *dest,
3239 int caller_count)
3241 ipcp_value_source<valtype> *src;
3242 vec<cgraph_edge *> ret;
3244 ret.create (caller_count);
3245 for (src = val->sources; src; src = src->next)
3247 struct cgraph_edge *cs = src->cs;
3248 while (cs)
3250 if (cgraph_edge_brings_value_p (cs, src, dest))
3251 ret.quick_push (cs);
3252 cs = get_next_cgraph_edge_clone (cs);
3256 return ret;
3259 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
3260 Return it or NULL if for some reason it cannot be created. */
3262 static struct ipa_replace_map *
3263 get_replacement_map (struct ipa_node_params *info, tree value, int parm_num)
3265 struct ipa_replace_map *replace_map;
3268 replace_map = ggc_alloc<ipa_replace_map> ();
3269 if (dump_file)
3271 fprintf (dump_file, " replacing ");
3272 ipa_dump_param (dump_file, info, parm_num);
3274 fprintf (dump_file, " with const ");
3275 print_generic_expr (dump_file, value, 0);
3276 fprintf (dump_file, "\n");
3278 replace_map->old_tree = NULL;
3279 replace_map->parm_num = parm_num;
3280 replace_map->new_tree = value;
3281 replace_map->replace_p = true;
3282 replace_map->ref_p = false;
3284 return replace_map;
3287 /* Dump new profiling counts */
3289 static void
3290 dump_profile_updates (struct cgraph_node *orig_node,
3291 struct cgraph_node *new_node)
3293 struct cgraph_edge *cs;
3295 fprintf (dump_file, " setting count of the specialized node to "
3296 HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) new_node->count);
3297 for (cs = new_node->callees; cs ; cs = cs->next_callee)
3298 fprintf (dump_file, " edge to %s has count "
3299 HOST_WIDE_INT_PRINT_DEC "\n",
3300 cs->callee->name (), (HOST_WIDE_INT) cs->count);
3302 fprintf (dump_file, " setting count of the original node to "
3303 HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) orig_node->count);
3304 for (cs = orig_node->callees; cs ; cs = cs->next_callee)
3305 fprintf (dump_file, " edge to %s is left with "
3306 HOST_WIDE_INT_PRINT_DEC "\n",
3307 cs->callee->name (), (HOST_WIDE_INT) cs->count);
3310 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
3311 their profile information to reflect this. */
3313 static void
3314 update_profiling_info (struct cgraph_node *orig_node,
3315 struct cgraph_node *new_node)
3317 struct cgraph_edge *cs;
3318 struct caller_statistics stats;
3319 gcov_type new_sum, orig_sum;
3320 gcov_type remainder, orig_node_count = orig_node->count;
3322 if (orig_node_count == 0)
3323 return;
3325 init_caller_stats (&stats);
3326 orig_node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats,
3327 false);
3328 orig_sum = stats.count_sum;
3329 init_caller_stats (&stats);
3330 new_node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats,
3331 false);
3332 new_sum = stats.count_sum;
3334 if (orig_node_count < orig_sum + new_sum)
3336 if (dump_file)
3337 fprintf (dump_file, " Problem: node %s/%i has too low count "
3338 HOST_WIDE_INT_PRINT_DEC " while the sum of incoming "
3339 "counts is " HOST_WIDE_INT_PRINT_DEC "\n",
3340 orig_node->name (), orig_node->order,
3341 (HOST_WIDE_INT) orig_node_count,
3342 (HOST_WIDE_INT) (orig_sum + new_sum));
3344 orig_node_count = (orig_sum + new_sum) * 12 / 10;
3345 if (dump_file)
3346 fprintf (dump_file, " proceeding by pretending it was "
3347 HOST_WIDE_INT_PRINT_DEC "\n",
3348 (HOST_WIDE_INT) orig_node_count);
3351 new_node->count = new_sum;
3352 remainder = orig_node_count - new_sum;
3353 orig_node->count = remainder;
3355 for (cs = new_node->callees; cs ; cs = cs->next_callee)
3356 if (cs->frequency)
3357 cs->count = apply_probability (cs->count,
3358 GCOV_COMPUTE_SCALE (new_sum,
3359 orig_node_count));
3360 else
3361 cs->count = 0;
3363 for (cs = orig_node->callees; cs ; cs = cs->next_callee)
3364 cs->count = apply_probability (cs->count,
3365 GCOV_COMPUTE_SCALE (remainder,
3366 orig_node_count));
3368 if (dump_file)
3369 dump_profile_updates (orig_node, new_node);
3372 /* Update the respective profile of specialized NEW_NODE and the original
3373 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
3374 have been redirected to the specialized version. */
3376 static void
3377 update_specialized_profile (struct cgraph_node *new_node,
3378 struct cgraph_node *orig_node,
3379 gcov_type redirected_sum)
3381 struct cgraph_edge *cs;
3382 gcov_type new_node_count, orig_node_count = orig_node->count;
3384 if (dump_file)
3385 fprintf (dump_file, " the sum of counts of redirected edges is "
3386 HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) redirected_sum);
3387 if (orig_node_count == 0)
3388 return;
3390 gcc_assert (orig_node_count >= redirected_sum);
3392 new_node_count = new_node->count;
3393 new_node->count += redirected_sum;
3394 orig_node->count -= redirected_sum;
3396 for (cs = new_node->callees; cs ; cs = cs->next_callee)
3397 if (cs->frequency)
3398 cs->count += apply_probability (cs->count,
3399 GCOV_COMPUTE_SCALE (redirected_sum,
3400 new_node_count));
3401 else
3402 cs->count = 0;
3404 for (cs = orig_node->callees; cs ; cs = cs->next_callee)
3406 gcov_type dec = apply_probability (cs->count,
3407 GCOV_COMPUTE_SCALE (redirected_sum,
3408 orig_node_count));
3409 if (dec < cs->count)
3410 cs->count -= dec;
3411 else
3412 cs->count = 0;
3415 if (dump_file)
3416 dump_profile_updates (orig_node, new_node);
3419 /* Create a specialized version of NODE with known constants in KNOWN_CSTS,
3420 known contexts in KNOWN_CONTEXTS and known aggregate values in AGGVALS and
3421 redirect all edges in CALLERS to it. */
3423 static struct cgraph_node *
3424 create_specialized_node (struct cgraph_node *node,
3425 vec<tree> known_csts,
3426 vec<ipa_polymorphic_call_context> known_contexts,
3427 struct ipa_agg_replacement_value *aggvals,
3428 vec<cgraph_edge *> callers)
3430 struct ipa_node_params *new_info, *info = IPA_NODE_REF (node);
3431 vec<ipa_replace_map *, va_gc> *replace_trees = NULL;
3432 struct ipa_agg_replacement_value *av;
3433 struct cgraph_node *new_node;
3434 int i, count = ipa_get_param_count (info);
3435 bitmap args_to_skip;
3437 gcc_assert (!info->ipcp_orig_node);
3439 if (node->local.can_change_signature)
3441 args_to_skip = BITMAP_GGC_ALLOC ();
3442 for (i = 0; i < count; i++)
3444 tree t = known_csts[i];
3446 if (t || !ipa_is_param_used (info, i))
3447 bitmap_set_bit (args_to_skip, i);
3450 else
3452 args_to_skip = NULL;
3453 if (dump_file && (dump_flags & TDF_DETAILS))
3454 fprintf (dump_file, " cannot change function signature\n");
3457 for (i = 0; i < count ; i++)
3459 tree t = known_csts[i];
3460 if (t)
3462 struct ipa_replace_map *replace_map;
3464 gcc_checking_assert (TREE_CODE (t) != TREE_BINFO);
3465 replace_map = get_replacement_map (info, t, i);
3466 if (replace_map)
3467 vec_safe_push (replace_trees, replace_map);
3471 new_node = node->create_virtual_clone (callers, replace_trees,
3472 args_to_skip, "constprop");
3473 ipa_set_node_agg_value_chain (new_node, aggvals);
3474 for (av = aggvals; av; av = av->next)
3475 new_node->maybe_create_reference (av->value, IPA_REF_ADDR, NULL);
3477 if (dump_file && (dump_flags & TDF_DETAILS))
3479 fprintf (dump_file, " the new node is %s/%i.\n",
3480 new_node->name (), new_node->order);
3481 if (known_contexts.exists ())
3483 for (i = 0; i < count ; i++)
3484 if (!known_contexts[i].useless_p ())
3486 fprintf (dump_file, " known ctx %i is ", i);
3487 known_contexts[i].dump (dump_file);
3490 if (aggvals)
3491 ipa_dump_agg_replacement_values (dump_file, aggvals);
3493 ipa_check_create_node_params ();
3494 update_profiling_info (node, new_node);
3495 new_info = IPA_NODE_REF (new_node);
3496 new_info->ipcp_orig_node = node;
3497 new_info->known_csts = known_csts;
3498 new_info->known_contexts = known_contexts;
3500 ipcp_discover_new_direct_edges (new_node, known_csts, known_contexts, aggvals);
3502 callers.release ();
3503 return new_node;
3506 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
3507 KNOWN_CSTS with constants that are also known for all of the CALLERS. */
3509 static void
3510 find_more_scalar_values_for_callers_subset (struct cgraph_node *node,
3511 vec<tree> known_csts,
3512 vec<cgraph_edge *> callers)
3514 struct ipa_node_params *info = IPA_NODE_REF (node);
3515 int i, count = ipa_get_param_count (info);
3517 for (i = 0; i < count ; i++)
3519 struct cgraph_edge *cs;
3520 tree newval = NULL_TREE;
3521 int j;
3522 bool first = true;
3524 if (ipa_get_scalar_lat (info, i)->bottom || known_csts[i])
3525 continue;
3527 FOR_EACH_VEC_ELT (callers, j, cs)
3529 struct ipa_jump_func *jump_func;
3530 tree t;
3532 if (i >= ipa_get_cs_argument_count (IPA_EDGE_REF (cs))
3533 || (i == 0
3534 && call_passes_through_thunk_p (cs))
3535 || (!cs->callee->instrumentation_clone
3536 && cs->callee->function_symbol ()->instrumentation_clone))
3538 newval = NULL_TREE;
3539 break;
3541 jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
3542 t = ipa_value_from_jfunc (IPA_NODE_REF (cs->caller), jump_func);
3543 if (!t
3544 || (newval
3545 && !values_equal_for_ipcp_p (t, newval))
3546 || (!first && !newval))
3548 newval = NULL_TREE;
3549 break;
3551 else
3552 newval = t;
3553 first = false;
3556 if (newval)
3558 if (dump_file && (dump_flags & TDF_DETAILS))
3560 fprintf (dump_file, " adding an extra known scalar value ");
3561 print_ipcp_constant_value (dump_file, newval);
3562 fprintf (dump_file, " for ");
3563 ipa_dump_param (dump_file, info, i);
3564 fprintf (dump_file, "\n");
3567 known_csts[i] = newval;
3572 /* Given a NODE and a subset of its CALLERS, try to populate plank slots in
3573 KNOWN_CONTEXTS with polymorphic contexts that are also known for all of the
3574 CALLERS. */
3576 static void
3577 find_more_contexts_for_caller_subset (cgraph_node *node,
3578 vec<ipa_polymorphic_call_context>
3579 *known_contexts,
3580 vec<cgraph_edge *> callers)
3582 ipa_node_params *info = IPA_NODE_REF (node);
3583 int i, count = ipa_get_param_count (info);
3585 for (i = 0; i < count ; i++)
3587 cgraph_edge *cs;
3589 if (ipa_get_poly_ctx_lat (info, i)->bottom
3590 || (known_contexts->exists ()
3591 && !(*known_contexts)[i].useless_p ()))
3592 continue;
3594 ipa_polymorphic_call_context newval;
3595 bool first = true;
3596 int j;
3598 FOR_EACH_VEC_ELT (callers, j, cs)
3600 if (i >= ipa_get_cs_argument_count (IPA_EDGE_REF (cs)))
3601 return;
3602 ipa_jump_func *jfunc = ipa_get_ith_jump_func (IPA_EDGE_REF (cs),
3604 ipa_polymorphic_call_context ctx;
3605 ctx = ipa_context_from_jfunc (IPA_NODE_REF (cs->caller), cs, i,
3606 jfunc);
3607 if (first)
3609 newval = ctx;
3610 first = false;
3612 else
3613 newval.meet_with (ctx);
3614 if (newval.useless_p ())
3615 break;
3618 if (!newval.useless_p ())
3620 if (dump_file && (dump_flags & TDF_DETAILS))
3622 fprintf (dump_file, " adding an extra known polymorphic "
3623 "context ");
3624 print_ipcp_constant_value (dump_file, newval);
3625 fprintf (dump_file, " for ");
3626 ipa_dump_param (dump_file, info, i);
3627 fprintf (dump_file, "\n");
3630 if (!known_contexts->exists ())
3631 known_contexts->safe_grow_cleared (ipa_get_param_count (info));
3632 (*known_contexts)[i] = newval;
3638 /* Go through PLATS and create a vector of values consisting of values and
3639 offsets (minus OFFSET) of lattices that contain only a single value. */
3641 static vec<ipa_agg_jf_item>
3642 copy_plats_to_inter (struct ipcp_param_lattices *plats, HOST_WIDE_INT offset)
3644 vec<ipa_agg_jf_item> res = vNULL;
3646 if (!plats->aggs || plats->aggs_contain_variable || plats->aggs_bottom)
3647 return vNULL;
3649 for (struct ipcp_agg_lattice *aglat = plats->aggs; aglat; aglat = aglat->next)
3650 if (aglat->is_single_const ())
3652 struct ipa_agg_jf_item ti;
3653 ti.offset = aglat->offset - offset;
3654 ti.value = aglat->values->value;
3655 res.safe_push (ti);
3657 return res;
3660 /* Intersect all values in INTER with single value lattices in PLATS (while
3661 subtracting OFFSET). */
3663 static void
3664 intersect_with_plats (struct ipcp_param_lattices *plats,
3665 vec<ipa_agg_jf_item> *inter,
3666 HOST_WIDE_INT offset)
3668 struct ipcp_agg_lattice *aglat;
3669 struct ipa_agg_jf_item *item;
3670 int k;
3672 if (!plats->aggs || plats->aggs_contain_variable || plats->aggs_bottom)
3674 inter->release ();
3675 return;
3678 aglat = plats->aggs;
3679 FOR_EACH_VEC_ELT (*inter, k, item)
3681 bool found = false;
3682 if (!item->value)
3683 continue;
3684 while (aglat)
3686 if (aglat->offset - offset > item->offset)
3687 break;
3688 if (aglat->offset - offset == item->offset)
3690 gcc_checking_assert (item->value);
3691 if (values_equal_for_ipcp_p (item->value, aglat->values->value))
3692 found = true;
3693 break;
3695 aglat = aglat->next;
3697 if (!found)
3698 item->value = NULL_TREE;
3702 /* Copy agggregate replacement values of NODE (which is an IPA-CP clone) to the
3703 vector result while subtracting OFFSET from the individual value offsets. */
3705 static vec<ipa_agg_jf_item>
3706 agg_replacements_to_vector (struct cgraph_node *node, int index,
3707 HOST_WIDE_INT offset)
3709 struct ipa_agg_replacement_value *av;
3710 vec<ipa_agg_jf_item> res = vNULL;
3712 for (av = ipa_get_agg_replacements_for_node (node); av; av = av->next)
3713 if (av->index == index
3714 && (av->offset - offset) >= 0)
3716 struct ipa_agg_jf_item item;
3717 gcc_checking_assert (av->value);
3718 item.offset = av->offset - offset;
3719 item.value = av->value;
3720 res.safe_push (item);
3723 return res;
3726 /* Intersect all values in INTER with those that we have already scheduled to
3727 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
3728 (while subtracting OFFSET). */
3730 static void
3731 intersect_with_agg_replacements (struct cgraph_node *node, int index,
3732 vec<ipa_agg_jf_item> *inter,
3733 HOST_WIDE_INT offset)
3735 struct ipa_agg_replacement_value *srcvals;
3736 struct ipa_agg_jf_item *item;
3737 int i;
3739 srcvals = ipa_get_agg_replacements_for_node (node);
3740 if (!srcvals)
3742 inter->release ();
3743 return;
3746 FOR_EACH_VEC_ELT (*inter, i, item)
3748 struct ipa_agg_replacement_value *av;
3749 bool found = false;
3750 if (!item->value)
3751 continue;
3752 for (av = srcvals; av; av = av->next)
3754 gcc_checking_assert (av->value);
3755 if (av->index == index
3756 && av->offset - offset == item->offset)
3758 if (values_equal_for_ipcp_p (item->value, av->value))
3759 found = true;
3760 break;
3763 if (!found)
3764 item->value = NULL_TREE;
3768 /* Intersect values in INTER with aggregate values that come along edge CS to
3769 parameter number INDEX and return it. If INTER does not actually exist yet,
3770 copy all incoming values to it. If we determine we ended up with no values
3771 whatsoever, return a released vector. */
3773 static vec<ipa_agg_jf_item>
3774 intersect_aggregates_with_edge (struct cgraph_edge *cs, int index,
3775 vec<ipa_agg_jf_item> inter)
3777 struct ipa_jump_func *jfunc;
3778 jfunc = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), index);
3779 if (jfunc->type == IPA_JF_PASS_THROUGH
3780 && ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
3782 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
3783 int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
3785 if (caller_info->ipcp_orig_node)
3787 struct cgraph_node *orig_node = caller_info->ipcp_orig_node;
3788 struct ipcp_param_lattices *orig_plats;
3789 orig_plats = ipa_get_parm_lattices (IPA_NODE_REF (orig_node),
3790 src_idx);
3791 if (agg_pass_through_permissible_p (orig_plats, jfunc))
3793 if (!inter.exists ())
3794 inter = agg_replacements_to_vector (cs->caller, src_idx, 0);
3795 else
3796 intersect_with_agg_replacements (cs->caller, src_idx,
3797 &inter, 0);
3799 else
3801 inter.release ();
3802 return vNULL;
3805 else
3807 struct ipcp_param_lattices *src_plats;
3808 src_plats = ipa_get_parm_lattices (caller_info, src_idx);
3809 if (agg_pass_through_permissible_p (src_plats, jfunc))
3811 /* Currently we do not produce clobber aggregate jump
3812 functions, adjust when we do. */
3813 gcc_checking_assert (!jfunc->agg.items);
3814 if (!inter.exists ())
3815 inter = copy_plats_to_inter (src_plats, 0);
3816 else
3817 intersect_with_plats (src_plats, &inter, 0);
3819 else
3821 inter.release ();
3822 return vNULL;
3826 else if (jfunc->type == IPA_JF_ANCESTOR
3827 && ipa_get_jf_ancestor_agg_preserved (jfunc))
3829 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
3830 int src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
3831 struct ipcp_param_lattices *src_plats;
3832 HOST_WIDE_INT delta = ipa_get_jf_ancestor_offset (jfunc);
3834 if (caller_info->ipcp_orig_node)
3836 if (!inter.exists ())
3837 inter = agg_replacements_to_vector (cs->caller, src_idx, delta);
3838 else
3839 intersect_with_agg_replacements (cs->caller, src_idx, &inter,
3840 delta);
3842 else
3844 src_plats = ipa_get_parm_lattices (caller_info, src_idx);;
3845 /* Currently we do not produce clobber aggregate jump
3846 functions, adjust when we do. */
3847 gcc_checking_assert (!src_plats->aggs || !jfunc->agg.items);
3848 if (!inter.exists ())
3849 inter = copy_plats_to_inter (src_plats, delta);
3850 else
3851 intersect_with_plats (src_plats, &inter, delta);
3854 else if (jfunc->agg.items)
3856 struct ipa_agg_jf_item *item;
3857 int k;
3859 if (!inter.exists ())
3860 for (unsigned i = 0; i < jfunc->agg.items->length (); i++)
3861 inter.safe_push ((*jfunc->agg.items)[i]);
3862 else
3863 FOR_EACH_VEC_ELT (inter, k, item)
3865 int l = 0;
3866 bool found = false;;
3868 if (!item->value)
3869 continue;
3871 while ((unsigned) l < jfunc->agg.items->length ())
3873 struct ipa_agg_jf_item *ti;
3874 ti = &(*jfunc->agg.items)[l];
3875 if (ti->offset > item->offset)
3876 break;
3877 if (ti->offset == item->offset)
3879 gcc_checking_assert (ti->value);
3880 if (values_equal_for_ipcp_p (item->value,
3881 ti->value))
3882 found = true;
3883 break;
3885 l++;
3887 if (!found)
3888 item->value = NULL;
3891 else
3893 inter.release ();
3894 return vec<ipa_agg_jf_item>();
3896 return inter;
3899 /* Look at edges in CALLERS and collect all known aggregate values that arrive
3900 from all of them. */
3902 static struct ipa_agg_replacement_value *
3903 find_aggregate_values_for_callers_subset (struct cgraph_node *node,
3904 vec<cgraph_edge *> callers)
3906 struct ipa_node_params *dest_info = IPA_NODE_REF (node);
3907 struct ipa_agg_replacement_value *res;
3908 struct ipa_agg_replacement_value **tail = &res;
3909 struct cgraph_edge *cs;
3910 int i, j, count = ipa_get_param_count (dest_info);
3912 FOR_EACH_VEC_ELT (callers, j, cs)
3914 int c = ipa_get_cs_argument_count (IPA_EDGE_REF (cs));
3915 if (c < count)
3916 count = c;
3919 for (i = 0; i < count ; i++)
3921 struct cgraph_edge *cs;
3922 vec<ipa_agg_jf_item> inter = vNULL;
3923 struct ipa_agg_jf_item *item;
3924 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (dest_info, i);
3925 int j;
3927 /* Among other things, the following check should deal with all by_ref
3928 mismatches. */
3929 if (plats->aggs_bottom)
3930 continue;
3932 FOR_EACH_VEC_ELT (callers, j, cs)
3934 inter = intersect_aggregates_with_edge (cs, i, inter);
3936 if (!inter.exists ())
3937 goto next_param;
3940 FOR_EACH_VEC_ELT (inter, j, item)
3942 struct ipa_agg_replacement_value *v;
3944 if (!item->value)
3945 continue;
3947 v = ggc_alloc<ipa_agg_replacement_value> ();
3948 v->index = i;
3949 v->offset = item->offset;
3950 v->value = item->value;
3951 v->by_ref = plats->aggs_by_ref;
3952 *tail = v;
3953 tail = &v->next;
3956 next_param:
3957 if (inter.exists ())
3958 inter.release ();
3960 *tail = NULL;
3961 return res;
3964 /* Turn KNOWN_AGGS into a list of aggreate replacement values. */
3966 static struct ipa_agg_replacement_value *
3967 known_aggs_to_agg_replacement_list (vec<ipa_agg_jump_function> known_aggs)
3969 struct ipa_agg_replacement_value *res;
3970 struct ipa_agg_replacement_value **tail = &res;
3971 struct ipa_agg_jump_function *aggjf;
3972 struct ipa_agg_jf_item *item;
3973 int i, j;
3975 FOR_EACH_VEC_ELT (known_aggs, i, aggjf)
3976 FOR_EACH_VEC_SAFE_ELT (aggjf->items, j, item)
3978 struct ipa_agg_replacement_value *v;
3979 v = ggc_alloc<ipa_agg_replacement_value> ();
3980 v->index = i;
3981 v->offset = item->offset;
3982 v->value = item->value;
3983 v->by_ref = aggjf->by_ref;
3984 *tail = v;
3985 tail = &v->next;
3987 *tail = NULL;
3988 return res;
3991 /* Determine whether CS also brings all scalar values that the NODE is
3992 specialized for. */
3994 static bool
3995 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge *cs,
3996 struct cgraph_node *node)
3998 struct ipa_node_params *dest_info = IPA_NODE_REF (node);
3999 int count = ipa_get_param_count (dest_info);
4000 struct ipa_node_params *caller_info;
4001 struct ipa_edge_args *args;
4002 int i;
4004 caller_info = IPA_NODE_REF (cs->caller);
4005 args = IPA_EDGE_REF (cs);
4006 for (i = 0; i < count; i++)
4008 struct ipa_jump_func *jump_func;
4009 tree val, t;
4011 val = dest_info->known_csts[i];
4012 if (!val)
4013 continue;
4015 if (i >= ipa_get_cs_argument_count (args))
4016 return false;
4017 jump_func = ipa_get_ith_jump_func (args, i);
4018 t = ipa_value_from_jfunc (caller_info, jump_func);
4019 if (!t || !values_equal_for_ipcp_p (val, t))
4020 return false;
4022 return true;
4025 /* Determine whether CS also brings all aggregate values that NODE is
4026 specialized for. */
4027 static bool
4028 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge *cs,
4029 struct cgraph_node *node)
4031 struct ipa_node_params *orig_caller_info = IPA_NODE_REF (cs->caller);
4032 struct ipa_node_params *orig_node_info;
4033 struct ipa_agg_replacement_value *aggval;
4034 int i, ec, count;
4036 aggval = ipa_get_agg_replacements_for_node (node);
4037 if (!aggval)
4038 return true;
4040 count = ipa_get_param_count (IPA_NODE_REF (node));
4041 ec = ipa_get_cs_argument_count (IPA_EDGE_REF (cs));
4042 if (ec < count)
4043 for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next)
4044 if (aggval->index >= ec)
4045 return false;
4047 orig_node_info = IPA_NODE_REF (IPA_NODE_REF (node)->ipcp_orig_node);
4048 if (orig_caller_info->ipcp_orig_node)
4049 orig_caller_info = IPA_NODE_REF (orig_caller_info->ipcp_orig_node);
4051 for (i = 0; i < count; i++)
4053 static vec<ipa_agg_jf_item> values = vec<ipa_agg_jf_item>();
4054 struct ipcp_param_lattices *plats;
4055 bool interesting = false;
4056 for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next)
4057 if (aggval->index == i)
4059 interesting = true;
4060 break;
4062 if (!interesting)
4063 continue;
4065 plats = ipa_get_parm_lattices (orig_node_info, aggval->index);
4066 if (plats->aggs_bottom)
4067 return false;
4069 values = intersect_aggregates_with_edge (cs, i, values);
4070 if (!values.exists ())
4071 return false;
4073 for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next)
4074 if (aggval->index == i)
4076 struct ipa_agg_jf_item *item;
4077 int j;
4078 bool found = false;
4079 FOR_EACH_VEC_ELT (values, j, item)
4080 if (item->value
4081 && item->offset == av->offset
4082 && values_equal_for_ipcp_p (item->value, av->value))
4084 found = true;
4085 break;
4087 if (!found)
4089 values.release ();
4090 return false;
4094 return true;
4097 /* Given an original NODE and a VAL for which we have already created a
4098 specialized clone, look whether there are incoming edges that still lead
4099 into the old node but now also bring the requested value and also conform to
4100 all other criteria such that they can be redirected the special node.
4101 This function can therefore redirect the final edge in a SCC. */
4103 template <typename valtype>
4104 static void
4105 perhaps_add_new_callers (cgraph_node *node, ipcp_value<valtype> *val)
4107 ipcp_value_source<valtype> *src;
4108 gcov_type redirected_sum = 0;
4110 for (src = val->sources; src; src = src->next)
4112 struct cgraph_edge *cs = src->cs;
4113 while (cs)
4115 if (cgraph_edge_brings_value_p (cs, src, node)
4116 && cgraph_edge_brings_all_scalars_for_node (cs, val->spec_node)
4117 && cgraph_edge_brings_all_agg_vals_for_node (cs, val->spec_node))
4119 if (dump_file)
4120 fprintf (dump_file, " - adding an extra caller %s/%i"
4121 " of %s/%i\n",
4122 xstrdup_for_dump (cs->caller->name ()),
4123 cs->caller->order,
4124 xstrdup_for_dump (val->spec_node->name ()),
4125 val->spec_node->order);
4127 cs->redirect_callee_duplicating_thunks (val->spec_node);
4128 val->spec_node->expand_all_artificial_thunks ();
4129 redirected_sum += cs->count;
4131 cs = get_next_cgraph_edge_clone (cs);
4135 if (redirected_sum)
4136 update_specialized_profile (val->spec_node, node, redirected_sum);
4139 /* Return true if KNOWN_CONTEXTS contain at least one useful context. */
4141 static bool
4142 known_contexts_useful_p (vec<ipa_polymorphic_call_context> known_contexts)
4144 ipa_polymorphic_call_context *ctx;
4145 int i;
4147 FOR_EACH_VEC_ELT (known_contexts, i, ctx)
4148 if (!ctx->useless_p ())
4149 return true;
4150 return false;
4153 /* Return a copy of KNOWN_CSTS if it is not empty, otherwise return vNULL. */
4155 static vec<ipa_polymorphic_call_context>
4156 copy_useful_known_contexts (vec<ipa_polymorphic_call_context> known_contexts)
4158 if (known_contexts_useful_p (known_contexts))
4159 return known_contexts.copy ();
4160 else
4161 return vNULL;
4164 /* Copy KNOWN_CSTS and modify the copy according to VAL and INDEX. If
4165 non-empty, replace KNOWN_CONTEXTS with its copy too. */
4167 static void
4168 modify_known_vectors_with_val (vec<tree> *known_csts,
4169 vec<ipa_polymorphic_call_context> *known_contexts,
4170 ipcp_value<tree> *val,
4171 int index)
4173 *known_csts = known_csts->copy ();
4174 *known_contexts = copy_useful_known_contexts (*known_contexts);
4175 (*known_csts)[index] = val->value;
4178 /* Replace KNOWN_CSTS with its copy. Also copy KNOWN_CONTEXTS and modify the
4179 copy according to VAL and INDEX. */
4181 static void
4182 modify_known_vectors_with_val (vec<tree> *known_csts,
4183 vec<ipa_polymorphic_call_context> *known_contexts,
4184 ipcp_value<ipa_polymorphic_call_context> *val,
4185 int index)
4187 *known_csts = known_csts->copy ();
4188 *known_contexts = known_contexts->copy ();
4189 (*known_contexts)[index] = val->value;
4192 /* Return true if OFFSET indicates this was not an aggregate value or there is
4193 a replacement equivalent to VALUE, INDEX and OFFSET among those in the
4194 AGGVALS list. */
4196 DEBUG_FUNCTION bool
4197 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value *aggvals,
4198 int index, HOST_WIDE_INT offset, tree value)
4200 if (offset == -1)
4201 return true;
4203 while (aggvals)
4205 if (aggvals->index == index
4206 && aggvals->offset == offset
4207 && values_equal_for_ipcp_p (aggvals->value, value))
4208 return true;
4209 aggvals = aggvals->next;
4211 return false;
4214 /* Return true if offset is minus one because source of a polymorphic contect
4215 cannot be an aggregate value. */
4217 DEBUG_FUNCTION bool
4218 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value *,
4219 int , HOST_WIDE_INT offset,
4220 ipa_polymorphic_call_context)
4222 return offset == -1;
4225 /* Decide wheter to create a special version of NODE for value VAL of parameter
4226 at the given INDEX. If OFFSET is -1, the value is for the parameter itself,
4227 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS,
4228 KNOWN_CONTEXTS and KNOWN_AGGS describe the other already known values. */
4230 template <typename valtype>
4231 static bool
4232 decide_about_value (struct cgraph_node *node, int index, HOST_WIDE_INT offset,
4233 ipcp_value<valtype> *val, vec<tree> known_csts,
4234 vec<ipa_polymorphic_call_context> known_contexts)
4236 struct ipa_agg_replacement_value *aggvals;
4237 int freq_sum, caller_count;
4238 gcov_type count_sum;
4239 vec<cgraph_edge *> callers;
4241 if (val->spec_node)
4243 perhaps_add_new_callers (node, val);
4244 return false;
4246 else if (val->local_size_cost + overall_size > max_new_size)
4248 if (dump_file && (dump_flags & TDF_DETAILS))
4249 fprintf (dump_file, " Ignoring candidate value because "
4250 "max_new_size would be reached with %li.\n",
4251 val->local_size_cost + overall_size);
4252 return false;
4254 else if (!get_info_about_necessary_edges (val, node, &freq_sum, &count_sum,
4255 &caller_count))
4256 return false;
4258 if (dump_file && (dump_flags & TDF_DETAILS))
4260 fprintf (dump_file, " - considering value ");
4261 print_ipcp_constant_value (dump_file, val->value);
4262 fprintf (dump_file, " for ");
4263 ipa_dump_param (dump_file, IPA_NODE_REF (node), index);
4264 if (offset != -1)
4265 fprintf (dump_file, ", offset: " HOST_WIDE_INT_PRINT_DEC, offset);
4266 fprintf (dump_file, " (caller_count: %i)\n", caller_count);
4269 if (!good_cloning_opportunity_p (node, val->local_time_benefit,
4270 freq_sum, count_sum,
4271 val->local_size_cost)
4272 && !good_cloning_opportunity_p (node,
4273 val->local_time_benefit
4274 + val->prop_time_benefit,
4275 freq_sum, count_sum,
4276 val->local_size_cost
4277 + val->prop_size_cost))
4278 return false;
4280 if (dump_file)
4281 fprintf (dump_file, " Creating a specialized node of %s/%i.\n",
4282 node->name (), node->order);
4284 callers = gather_edges_for_value (val, node, caller_count);
4285 if (offset == -1)
4286 modify_known_vectors_with_val (&known_csts, &known_contexts, val, index);
4287 else
4289 known_csts = known_csts.copy ();
4290 known_contexts = copy_useful_known_contexts (known_contexts);
4292 find_more_scalar_values_for_callers_subset (node, known_csts, callers);
4293 find_more_contexts_for_caller_subset (node, &known_contexts, callers);
4294 aggvals = find_aggregate_values_for_callers_subset (node, callers);
4295 gcc_checking_assert (ipcp_val_agg_replacement_ok_p (aggvals, index,
4296 offset, val->value));
4297 val->spec_node = create_specialized_node (node, known_csts, known_contexts,
4298 aggvals, callers);
4299 overall_size += val->local_size_cost;
4301 /* TODO: If for some lattice there is only one other known value
4302 left, make a special node for it too. */
4304 return true;
4307 /* Decide whether and what specialized clones of NODE should be created. */
4309 static bool
4310 decide_whether_version_node (struct cgraph_node *node)
4312 struct ipa_node_params *info = IPA_NODE_REF (node);
4313 int i, count = ipa_get_param_count (info);
4314 vec<tree> known_csts;
4315 vec<ipa_polymorphic_call_context> known_contexts;
4316 vec<ipa_agg_jump_function> known_aggs = vNULL;
4317 bool ret = false;
4319 if (count == 0)
4320 return false;
4322 if (dump_file && (dump_flags & TDF_DETAILS))
4323 fprintf (dump_file, "\nEvaluating opportunities for %s/%i.\n",
4324 node->name (), node->order);
4326 gather_context_independent_values (info, &known_csts, &known_contexts,
4327 info->do_clone_for_all_contexts ? &known_aggs
4328 : NULL, NULL);
4330 for (i = 0; i < count ;i++)
4332 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
4333 ipcp_lattice<tree> *lat = &plats->itself;
4334 ipcp_lattice<ipa_polymorphic_call_context> *ctxlat = &plats->ctxlat;
4336 if (!lat->bottom
4337 && !known_csts[i])
4339 ipcp_value<tree> *val;
4340 for (val = lat->values; val; val = val->next)
4341 ret |= decide_about_value (node, i, -1, val, known_csts,
4342 known_contexts);
4345 if (!plats->aggs_bottom)
4347 struct ipcp_agg_lattice *aglat;
4348 ipcp_value<tree> *val;
4349 for (aglat = plats->aggs; aglat; aglat = aglat->next)
4350 if (!aglat->bottom && aglat->values
4351 /* If the following is false, the one value is in
4352 known_aggs. */
4353 && (plats->aggs_contain_variable
4354 || !aglat->is_single_const ()))
4355 for (val = aglat->values; val; val = val->next)
4356 ret |= decide_about_value (node, i, aglat->offset, val,
4357 known_csts, known_contexts);
4360 if (!ctxlat->bottom
4361 && known_contexts[i].useless_p ())
4363 ipcp_value<ipa_polymorphic_call_context> *val;
4364 for (val = ctxlat->values; val; val = val->next)
4365 ret |= decide_about_value (node, i, -1, val, known_csts,
4366 known_contexts);
4369 info = IPA_NODE_REF (node);
4372 if (info->do_clone_for_all_contexts)
4374 struct cgraph_node *clone;
4375 vec<cgraph_edge *> callers;
4377 if (dump_file)
4378 fprintf (dump_file, " - Creating a specialized node of %s/%i "
4379 "for all known contexts.\n", node->name (),
4380 node->order);
4382 callers = node->collect_callers ();
4384 if (!known_contexts_useful_p (known_contexts))
4386 known_contexts.release ();
4387 known_contexts = vNULL;
4389 clone = create_specialized_node (node, known_csts, known_contexts,
4390 known_aggs_to_agg_replacement_list (known_aggs),
4391 callers);
4392 info = IPA_NODE_REF (node);
4393 info->do_clone_for_all_contexts = false;
4394 IPA_NODE_REF (clone)->is_all_contexts_clone = true;
4395 for (i = 0; i < count ; i++)
4396 vec_free (known_aggs[i].items);
4397 known_aggs.release ();
4398 ret = true;
4400 else
4402 known_csts.release ();
4403 known_contexts.release ();
4406 return ret;
4409 /* Transitively mark all callees of NODE within the same SCC as not dead. */
4411 static void
4412 spread_undeadness (struct cgraph_node *node)
4414 struct cgraph_edge *cs;
4416 for (cs = node->callees; cs; cs = cs->next_callee)
4417 if (ipa_edge_within_scc (cs))
4419 struct cgraph_node *callee;
4420 struct ipa_node_params *info;
4422 callee = cs->callee->function_symbol (NULL);
4423 info = IPA_NODE_REF (callee);
4425 if (info->node_dead)
4427 info->node_dead = 0;
4428 spread_undeadness (callee);
4433 /* Return true if NODE has a caller from outside of its SCC that is not
4434 dead. Worker callback for cgraph_for_node_and_aliases. */
4436 static bool
4437 has_undead_caller_from_outside_scc_p (struct cgraph_node *node,
4438 void *data ATTRIBUTE_UNUSED)
4440 struct cgraph_edge *cs;
4442 for (cs = node->callers; cs; cs = cs->next_caller)
4443 if (cs->caller->thunk.thunk_p
4444 && cs->caller->call_for_symbol_thunks_and_aliases
4445 (has_undead_caller_from_outside_scc_p, NULL, true))
4446 return true;
4447 else if (!ipa_edge_within_scc (cs)
4448 && !IPA_NODE_REF (cs->caller)->node_dead)
4449 return true;
4450 return false;
4454 /* Identify nodes within the same SCC as NODE which are no longer needed
4455 because of new clones and will be removed as unreachable. */
4457 static void
4458 identify_dead_nodes (struct cgraph_node *node)
4460 struct cgraph_node *v;
4461 for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
4462 if (v->local.local
4463 && !v->call_for_symbol_thunks_and_aliases
4464 (has_undead_caller_from_outside_scc_p, NULL, true))
4465 IPA_NODE_REF (v)->node_dead = 1;
4467 for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
4468 if (!IPA_NODE_REF (v)->node_dead)
4469 spread_undeadness (v);
4471 if (dump_file && (dump_flags & TDF_DETAILS))
4473 for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
4474 if (IPA_NODE_REF (v)->node_dead)
4475 fprintf (dump_file, " Marking node as dead: %s/%i.\n",
4476 v->name (), v->order);
4480 /* The decision stage. Iterate over the topological order of call graph nodes
4481 TOPO and make specialized clones if deemed beneficial. */
4483 static void
4484 ipcp_decision_stage (struct ipa_topo_info *topo)
4486 int i;
4488 if (dump_file)
4489 fprintf (dump_file, "\nIPA decision stage:\n\n");
4491 for (i = topo->nnodes - 1; i >= 0; i--)
4493 struct cgraph_node *node = topo->order[i];
4494 bool change = false, iterate = true;
4496 while (iterate)
4498 struct cgraph_node *v;
4499 iterate = false;
4500 for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
4501 if (v->has_gimple_body_p ()
4502 && ipcp_versionable_function_p (v))
4503 iterate |= decide_whether_version_node (v);
4505 change |= iterate;
4507 if (change)
4508 identify_dead_nodes (node);
4512 /* Look up all alignment information that we have discovered and copy it over
4513 to the transformation summary. */
4515 static void
4516 ipcp_store_alignment_results (void)
4518 cgraph_node *node;
4520 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
4522 ipa_node_params *info = IPA_NODE_REF (node);
4523 bool dumped_sth = false;
4524 bool found_useful_result = false;
4526 if (!opt_for_fn (node->decl, flag_ipa_cp_alignment))
4528 if (dump_file)
4529 fprintf (dump_file, "Not considering %s for alignment discovery "
4530 "and propagate; -fipa-cp-alignment: disabled.\n",
4531 node->name ());
4532 continue;
4535 if (info->ipcp_orig_node)
4536 info = IPA_NODE_REF (info->ipcp_orig_node);
4538 unsigned count = ipa_get_param_count (info);
4539 for (unsigned i = 0; i < count ; i++)
4541 ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
4542 if (!plats->alignment.bottom_p ()
4543 && !plats->alignment.top_p ())
4545 gcc_checking_assert (plats->alignment.align > 0);
4546 found_useful_result = true;
4547 break;
4550 if (!found_useful_result)
4551 continue;
4553 ipcp_grow_transformations_if_necessary ();
4554 ipcp_transformation_summary *ts = ipcp_get_transformation_summary (node);
4555 vec_safe_reserve_exact (ts->alignments, count);
4557 for (unsigned i = 0; i < count ; i++)
4559 ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
4560 ipa_alignment al;
4562 if (!plats->alignment.bottom_p ()
4563 && !plats->alignment.top_p ())
4565 al.known = true;
4566 al.align = plats->alignment.align;
4567 al.misalign = plats->alignment.misalign;
4569 else
4570 al.known = false;
4572 ts->alignments->quick_push (al);
4573 if (!dump_file || !al.known)
4574 continue;
4575 if (!dumped_sth)
4577 fprintf (dump_file, "Propagated alignment info for function %s/%i:\n",
4578 node->name (), node->order);
4579 dumped_sth = true;
4581 fprintf (dump_file, " param %i: align: %u, misalign: %u\n",
4582 i, al.align, al.misalign);
4587 /* The IPCP driver. */
4589 static unsigned int
4590 ipcp_driver (void)
4592 struct cgraph_2edge_hook_list *edge_duplication_hook_holder;
4593 struct cgraph_edge_hook_list *edge_removal_hook_holder;
4594 struct ipa_topo_info topo;
4596 ipa_check_create_node_params ();
4597 ipa_check_create_edge_args ();
4598 grow_edge_clone_vectors ();
4599 edge_duplication_hook_holder =
4600 symtab->add_edge_duplication_hook (&ipcp_edge_duplication_hook, NULL);
4601 edge_removal_hook_holder =
4602 symtab->add_edge_removal_hook (&ipcp_edge_removal_hook, NULL);
4604 if (dump_file)
4606 fprintf (dump_file, "\nIPA structures before propagation:\n");
4607 if (dump_flags & TDF_DETAILS)
4608 ipa_print_all_params (dump_file);
4609 ipa_print_all_jump_functions (dump_file);
4612 /* Topological sort. */
4613 build_toporder_info (&topo);
4614 /* Do the interprocedural propagation. */
4615 ipcp_propagate_stage (&topo);
4616 /* Decide what constant propagation and cloning should be performed. */
4617 ipcp_decision_stage (&topo);
4618 /* Store results of alignment propagation. */
4619 ipcp_store_alignment_results ();
4621 /* Free all IPCP structures. */
4622 free_toporder_info (&topo);
4623 next_edge_clone.release ();
4624 prev_edge_clone.release ();
4625 symtab->remove_edge_removal_hook (edge_removal_hook_holder);
4626 symtab->remove_edge_duplication_hook (edge_duplication_hook_holder);
4627 ipa_free_all_structures_after_ipa_cp ();
4628 if (dump_file)
4629 fprintf (dump_file, "\nIPA constant propagation end\n");
4630 return 0;
4633 /* Initialization and computation of IPCP data structures. This is the initial
4634 intraprocedural analysis of functions, which gathers information to be
4635 propagated later on. */
4637 static void
4638 ipcp_generate_summary (void)
4640 struct cgraph_node *node;
4642 if (dump_file)
4643 fprintf (dump_file, "\nIPA constant propagation start:\n");
4644 ipa_register_cgraph_hooks ();
4646 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
4647 ipa_analyze_node (node);
4650 /* Write ipcp summary for nodes in SET. */
4652 static void
4653 ipcp_write_summary (void)
4655 ipa_prop_write_jump_functions ();
4658 /* Read ipcp summary. */
4660 static void
4661 ipcp_read_summary (void)
4663 ipa_prop_read_jump_functions ();
4666 namespace {
4668 const pass_data pass_data_ipa_cp =
4670 IPA_PASS, /* type */
4671 "cp", /* name */
4672 OPTGROUP_NONE, /* optinfo_flags */
4673 TV_IPA_CONSTANT_PROP, /* tv_id */
4674 0, /* properties_required */
4675 0, /* properties_provided */
4676 0, /* properties_destroyed */
4677 0, /* todo_flags_start */
4678 ( TODO_dump_symtab | TODO_remove_functions ), /* todo_flags_finish */
4681 class pass_ipa_cp : public ipa_opt_pass_d
4683 public:
4684 pass_ipa_cp (gcc::context *ctxt)
4685 : ipa_opt_pass_d (pass_data_ipa_cp, ctxt,
4686 ipcp_generate_summary, /* generate_summary */
4687 ipcp_write_summary, /* write_summary */
4688 ipcp_read_summary, /* read_summary */
4689 ipcp_write_transformation_summaries, /*
4690 write_optimization_summary */
4691 ipcp_read_transformation_summaries, /*
4692 read_optimization_summary */
4693 NULL, /* stmt_fixup */
4694 0, /* function_transform_todo_flags_start */
4695 ipcp_transform_function, /* function_transform */
4696 NULL) /* variable_transform */
4699 /* opt_pass methods: */
4700 virtual bool gate (function *)
4702 /* FIXME: We should remove the optimize check after we ensure we never run
4703 IPA passes when not optimizing. */
4704 return (flag_ipa_cp && optimize) || in_lto_p;
4707 virtual unsigned int execute (function *) { return ipcp_driver (); }
4709 }; // class pass_ipa_cp
4711 } // anon namespace
4713 ipa_opt_pass_d *
4714 make_pass_ipa_cp (gcc::context *ctxt)
4716 return new pass_ipa_cp (ctxt);
4719 /* Reset all state within ipa-cp.c so that we can rerun the compiler
4720 within the same process. For use by toplev::finalize. */
4722 void
4723 ipa_cp_c_finalize (void)
4725 max_count = 0;
4726 overall_size = 0;
4727 max_new_size = 0;