2017-12-01 Richard Biener <rguenther@suse.de>
[official-gcc.git] / gcc / ipa-cp.c
blob144762cf5e25a3a66c6fd09cbe1840321ae63a7f
1 /* Interprocedural constant propagation
2 Copyright (C) 2005-2017 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 "tree-vrp.h"
118 #include "ipa-prop.h"
119 #include "tree-pretty-print.h"
120 #include "tree-inline.h"
121 #include "params.h"
122 #include "ipa-fnsummary.h"
123 #include "ipa-utils.h"
124 #include "tree-ssa-ccp.h"
125 #include "stringpool.h"
126 #include "attribs.h"
128 template <typename valtype> class ipcp_value;
130 /* Describes a particular source for an IPA-CP value. */
132 template <typename valtype>
133 class ipcp_value_source
135 public:
136 /* Aggregate offset of the source, negative if the source is scalar value of
137 the argument itself. */
138 HOST_WIDE_INT offset;
139 /* The incoming edge that brought the value. */
140 cgraph_edge *cs;
141 /* If the jump function that resulted into his value was a pass-through or an
142 ancestor, this is the ipcp_value of the caller from which the described
143 value has been derived. Otherwise it is NULL. */
144 ipcp_value<valtype> *val;
145 /* Next pointer in a linked list of sources of a value. */
146 ipcp_value_source *next;
147 /* If the jump function that resulted into his value was a pass-through or an
148 ancestor, this is the index of the parameter of the caller the jump
149 function references. */
150 int index;
153 /* Common ancestor for all ipcp_value instantiations. */
155 class ipcp_value_base
157 public:
158 /* Time benefit and size cost that specializing the function for this value
159 would bring about in this function alone. */
160 int local_time_benefit, local_size_cost;
161 /* Time benefit and size cost that specializing the function for this value
162 can bring about in it's callees (transitively). */
163 int prop_time_benefit, prop_size_cost;
165 ipcp_value_base ()
166 : local_time_benefit (0), local_size_cost (0),
167 prop_time_benefit (0), prop_size_cost (0) {}
170 /* Describes one particular value stored in struct ipcp_lattice. */
172 template <typename valtype>
173 class ipcp_value : public ipcp_value_base
175 public:
176 /* The actual value for the given parameter. */
177 valtype value;
178 /* The list of sources from which this value originates. */
179 ipcp_value_source <valtype> *sources;
180 /* Next pointers in a linked list of all values in a lattice. */
181 ipcp_value *next;
182 /* Next pointers in a linked list of values in a strongly connected component
183 of values. */
184 ipcp_value *scc_next;
185 /* Next pointers in a linked list of SCCs of values sorted topologically
186 according their sources. */
187 ipcp_value *topo_next;
188 /* A specialized node created for this value, NULL if none has been (so far)
189 created. */
190 cgraph_node *spec_node;
191 /* Depth first search number and low link for topological sorting of
192 values. */
193 int dfs, low_link;
194 /* True if this valye is currently on the topo-sort stack. */
195 bool on_stack;
197 ipcp_value()
198 : sources (0), next (0), scc_next (0), topo_next (0),
199 spec_node (0), dfs (0), low_link (0), on_stack (false) {}
201 void add_source (cgraph_edge *cs, ipcp_value *src_val, int src_idx,
202 HOST_WIDE_INT offset);
205 /* Lattice describing potential values of a formal parameter of a function, or
206 a part of an aggregate. TOP is represented by a lattice with zero values
207 and with contains_variable and bottom flags cleared. BOTTOM is represented
208 by a lattice with the bottom flag set. In that case, values and
209 contains_variable flag should be disregarded. */
211 template <typename valtype>
212 class ipcp_lattice
214 public:
215 /* The list of known values and types in this lattice. Note that values are
216 not deallocated if a lattice is set to bottom because there may be value
217 sources referencing them. */
218 ipcp_value<valtype> *values;
219 /* Number of known values and types in this lattice. */
220 int values_count;
221 /* The lattice contains a variable component (in addition to values). */
222 bool contains_variable;
223 /* The value of the lattice is bottom (i.e. variable and unusable for any
224 propagation). */
225 bool bottom;
227 inline bool is_single_const ();
228 inline bool set_to_bottom ();
229 inline bool set_contains_variable ();
230 bool add_value (valtype newval, cgraph_edge *cs,
231 ipcp_value<valtype> *src_val = NULL,
232 int src_idx = 0, HOST_WIDE_INT offset = -1);
233 void print (FILE * f, bool dump_sources, bool dump_benefits);
236 /* Lattice of tree values with an offset to describe a part of an
237 aggregate. */
239 class ipcp_agg_lattice : public ipcp_lattice<tree>
241 public:
242 /* Offset that is being described by this lattice. */
243 HOST_WIDE_INT offset;
244 /* Size so that we don't have to re-compute it every time we traverse the
245 list. Must correspond to TYPE_SIZE of all lat values. */
246 HOST_WIDE_INT size;
247 /* Next element of the linked list. */
248 struct ipcp_agg_lattice *next;
251 /* Lattice of known bits, only capable of holding one value.
252 Bitwise constant propagation propagates which bits of a
253 value are constant.
254 For eg:
255 int f(int x)
257 return some_op (x);
260 int f1(int y)
262 if (cond)
263 return f (y & 0xff);
264 else
265 return f (y & 0xf);
268 In the above case, the param 'x' will always have all
269 the bits (except the bits in lsb) set to 0.
270 Hence the mask of 'x' would be 0xff. The mask
271 reflects that the bits in lsb are unknown.
272 The actual propagated value is given by m_value & ~m_mask. */
274 class ipcp_bits_lattice
276 public:
277 bool bottom_p () { return m_lattice_val == IPA_BITS_VARYING; }
278 bool top_p () { return m_lattice_val == IPA_BITS_UNDEFINED; }
279 bool constant_p () { return m_lattice_val == IPA_BITS_CONSTANT; }
280 bool set_to_bottom ();
281 bool set_to_constant (widest_int, widest_int);
283 widest_int get_value () { return m_value; }
284 widest_int get_mask () { return m_mask; }
286 bool meet_with (ipcp_bits_lattice& other, unsigned, signop,
287 enum tree_code, tree);
289 bool meet_with (widest_int, widest_int, unsigned);
291 void print (FILE *);
293 private:
294 enum { IPA_BITS_UNDEFINED, IPA_BITS_CONSTANT, IPA_BITS_VARYING } m_lattice_val;
296 /* Similar to ccp_lattice_t, mask represents which bits of value are constant.
297 If a bit in mask is set to 0, then the corresponding bit in
298 value is known to be constant. */
299 widest_int m_value, m_mask;
301 bool meet_with_1 (widest_int, widest_int, unsigned);
302 void get_value_and_mask (tree, widest_int *, widest_int *);
305 /* Lattice of value ranges. */
307 class ipcp_vr_lattice
309 public:
310 value_range m_vr;
312 inline bool bottom_p () const;
313 inline bool top_p () const;
314 inline bool set_to_bottom ();
315 bool meet_with (const value_range *p_vr);
316 bool meet_with (const ipcp_vr_lattice &other);
317 void init () { m_vr.type = VR_UNDEFINED; }
318 void print (FILE * f);
320 private:
321 bool meet_with_1 (const value_range *other_vr);
324 /* Structure containing lattices for a parameter itself and for pieces of
325 aggregates that are passed in the parameter or by a reference in a parameter
326 plus some other useful flags. */
328 class ipcp_param_lattices
330 public:
331 /* Lattice describing the value of the parameter itself. */
332 ipcp_lattice<tree> itself;
333 /* Lattice describing the polymorphic contexts of a parameter. */
334 ipcp_lattice<ipa_polymorphic_call_context> ctxlat;
335 /* Lattices describing aggregate parts. */
336 ipcp_agg_lattice *aggs;
337 /* Lattice describing known bits. */
338 ipcp_bits_lattice bits_lattice;
339 /* Lattice describing value range. */
340 ipcp_vr_lattice m_value_range;
341 /* Number of aggregate lattices */
342 int aggs_count;
343 /* True if aggregate data were passed by reference (as opposed to by
344 value). */
345 bool aggs_by_ref;
346 /* All aggregate lattices contain a variable component (in addition to
347 values). */
348 bool aggs_contain_variable;
349 /* The value of all aggregate lattices is bottom (i.e. variable and unusable
350 for any propagation). */
351 bool aggs_bottom;
353 /* There is a virtual call based on this parameter. */
354 bool virt_call;
357 /* Allocation pools for values and their sources in ipa-cp. */
359 object_allocator<ipcp_value<tree> > ipcp_cst_values_pool
360 ("IPA-CP constant values");
362 object_allocator<ipcp_value<ipa_polymorphic_call_context> >
363 ipcp_poly_ctx_values_pool ("IPA-CP polymorphic contexts");
365 object_allocator<ipcp_value_source<tree> > ipcp_sources_pool
366 ("IPA-CP value sources");
368 object_allocator<ipcp_agg_lattice> ipcp_agg_lattice_pool
369 ("IPA_CP aggregate lattices");
371 /* Maximal count found in program. */
373 static profile_count max_count;
375 /* Original overall size of the program. */
377 static long overall_size, max_new_size;
379 /* Return the param lattices structure corresponding to the Ith formal
380 parameter of the function described by INFO. */
381 static inline struct ipcp_param_lattices *
382 ipa_get_parm_lattices (struct ipa_node_params *info, int i)
384 gcc_assert (i >= 0 && i < ipa_get_param_count (info));
385 gcc_checking_assert (!info->ipcp_orig_node);
386 gcc_checking_assert (info->lattices);
387 return &(info->lattices[i]);
390 /* Return the lattice corresponding to the scalar value of the Ith formal
391 parameter of the function described by INFO. */
392 static inline ipcp_lattice<tree> *
393 ipa_get_scalar_lat (struct ipa_node_params *info, int i)
395 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
396 return &plats->itself;
399 /* Return the lattice corresponding to the scalar value of the Ith formal
400 parameter of the function described by INFO. */
401 static inline ipcp_lattice<ipa_polymorphic_call_context> *
402 ipa_get_poly_ctx_lat (struct ipa_node_params *info, int i)
404 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
405 return &plats->ctxlat;
408 /* Return the lattice corresponding to the value range of the Ith formal
409 parameter of the function described by INFO. */
411 static inline ipcp_vr_lattice *
412 ipa_get_vr_lat (struct ipa_node_params *info, int i)
414 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
415 return &plats->m_value_range;
418 /* Return whether LAT is a lattice with a single constant and without an
419 undefined value. */
421 template <typename valtype>
422 inline bool
423 ipcp_lattice<valtype>::is_single_const ()
425 if (bottom || contains_variable || values_count != 1)
426 return false;
427 else
428 return true;
431 /* Print V which is extracted from a value in a lattice to F. */
433 static void
434 print_ipcp_constant_value (FILE * f, tree v)
436 if (TREE_CODE (v) == ADDR_EXPR
437 && TREE_CODE (TREE_OPERAND (v, 0)) == CONST_DECL)
439 fprintf (f, "& ");
440 print_generic_expr (f, DECL_INITIAL (TREE_OPERAND (v, 0)));
442 else
443 print_generic_expr (f, v);
446 /* Print V which is extracted from a value in a lattice to F. */
448 static void
449 print_ipcp_constant_value (FILE * f, ipa_polymorphic_call_context v)
451 v.dump(f, false);
454 /* Print a lattice LAT to F. */
456 template <typename valtype>
457 void
458 ipcp_lattice<valtype>::print (FILE * f, bool dump_sources, bool dump_benefits)
460 ipcp_value<valtype> *val;
461 bool prev = false;
463 if (bottom)
465 fprintf (f, "BOTTOM\n");
466 return;
469 if (!values_count && !contains_variable)
471 fprintf (f, "TOP\n");
472 return;
475 if (contains_variable)
477 fprintf (f, "VARIABLE");
478 prev = true;
479 if (dump_benefits)
480 fprintf (f, "\n");
483 for (val = values; val; val = val->next)
485 if (dump_benefits && prev)
486 fprintf (f, " ");
487 else if (!dump_benefits && prev)
488 fprintf (f, ", ");
489 else
490 prev = true;
492 print_ipcp_constant_value (f, val->value);
494 if (dump_sources)
496 ipcp_value_source<valtype> *s;
498 fprintf (f, " [from:");
499 for (s = val->sources; s; s = s->next)
500 fprintf (f, " %i(%i)", s->cs->caller->order,
501 s->cs->frequency ());
502 fprintf (f, "]");
505 if (dump_benefits)
506 fprintf (f, " [loc_time: %i, loc_size: %i, "
507 "prop_time: %i, prop_size: %i]\n",
508 val->local_time_benefit, val->local_size_cost,
509 val->prop_time_benefit, val->prop_size_cost);
511 if (!dump_benefits)
512 fprintf (f, "\n");
515 void
516 ipcp_bits_lattice::print (FILE *f)
518 if (top_p ())
519 fprintf (f, " Bits unknown (TOP)\n");
520 else if (bottom_p ())
521 fprintf (f, " Bits unusable (BOTTOM)\n");
522 else
524 fprintf (f, " Bits: value = "); print_hex (get_value (), f);
525 fprintf (f, ", mask = "); print_hex (get_mask (), f);
526 fprintf (f, "\n");
530 /* Print value range lattice to F. */
532 void
533 ipcp_vr_lattice::print (FILE * f)
535 dump_value_range (f, &m_vr);
538 /* Print all ipcp_lattices of all functions to F. */
540 static void
541 print_all_lattices (FILE * f, bool dump_sources, bool dump_benefits)
543 struct cgraph_node *node;
544 int i, count;
546 fprintf (f, "\nLattices:\n");
547 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
549 struct ipa_node_params *info;
551 info = IPA_NODE_REF (node);
552 fprintf (f, " Node: %s:\n", node->dump_name ());
553 count = ipa_get_param_count (info);
554 for (i = 0; i < count; i++)
556 struct ipcp_agg_lattice *aglat;
557 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
558 fprintf (f, " param [%d]: ", i);
559 plats->itself.print (f, dump_sources, dump_benefits);
560 fprintf (f, " ctxs: ");
561 plats->ctxlat.print (f, dump_sources, dump_benefits);
562 plats->bits_lattice.print (f);
563 fprintf (f, " ");
564 plats->m_value_range.print (f);
565 fprintf (f, "\n");
566 if (plats->virt_call)
567 fprintf (f, " virt_call flag set\n");
569 if (plats->aggs_bottom)
571 fprintf (f, " AGGS BOTTOM\n");
572 continue;
574 if (plats->aggs_contain_variable)
575 fprintf (f, " AGGS VARIABLE\n");
576 for (aglat = plats->aggs; aglat; aglat = aglat->next)
578 fprintf (f, " %soffset " HOST_WIDE_INT_PRINT_DEC ": ",
579 plats->aggs_by_ref ? "ref " : "", aglat->offset);
580 aglat->print (f, dump_sources, dump_benefits);
586 /* Determine whether it is at all technically possible to create clones of NODE
587 and store this information in the ipa_node_params structure associated
588 with NODE. */
590 static void
591 determine_versionability (struct cgraph_node *node,
592 struct ipa_node_params *info)
594 const char *reason = NULL;
596 /* There are a number of generic reasons functions cannot be versioned. We
597 also cannot remove parameters if there are type attributes such as fnspec
598 present. */
599 if (node->alias || node->thunk.thunk_p)
600 reason = "alias or thunk";
601 else if (!node->local.versionable)
602 reason = "not a tree_versionable_function";
603 else if (node->get_availability () <= AVAIL_INTERPOSABLE)
604 reason = "insufficient body availability";
605 else if (!opt_for_fn (node->decl, optimize)
606 || !opt_for_fn (node->decl, flag_ipa_cp))
607 reason = "non-optimized function";
608 else if (lookup_attribute ("omp declare simd", DECL_ATTRIBUTES (node->decl)))
610 /* Ideally we should clone the SIMD clones themselves and create
611 vector copies of them, so IPA-cp and SIMD clones can happily
612 coexist, but that may not be worth the effort. */
613 reason = "function has SIMD clones";
615 else if (lookup_attribute ("target_clones", DECL_ATTRIBUTES (node->decl)))
617 /* Ideally we should clone the target clones themselves and create
618 copies of them, so IPA-cp and target clones can happily
619 coexist, but that may not be worth the effort. */
620 reason = "function target_clones attribute";
622 /* Don't clone decls local to a comdat group; it breaks and for C++
623 decloned constructors, inlining is always better anyway. */
624 else if (node->comdat_local_p ())
625 reason = "comdat-local function";
626 else if (node->calls_comdat_local)
628 /* TODO: call is versionable if we make sure that all
629 callers are inside of a comdat group. */
630 reason = "calls comdat-local function";
633 if (reason && dump_file && !node->alias && !node->thunk.thunk_p)
634 fprintf (dump_file, "Function %s is not versionable, reason: %s.\n",
635 node->dump_name (), reason);
637 info->versionable = (reason == NULL);
640 /* Return true if it is at all technically possible to create clones of a
641 NODE. */
643 static bool
644 ipcp_versionable_function_p (struct cgraph_node *node)
646 return IPA_NODE_REF (node)->versionable;
649 /* Structure holding accumulated information about callers of a node. */
651 struct caller_statistics
653 profile_count count_sum;
654 int n_calls, n_hot_calls, freq_sum;
657 /* Initialize fields of STAT to zeroes. */
659 static inline void
660 init_caller_stats (struct caller_statistics *stats)
662 stats->count_sum = profile_count::zero ();
663 stats->n_calls = 0;
664 stats->n_hot_calls = 0;
665 stats->freq_sum = 0;
668 /* Worker callback of cgraph_for_node_and_aliases accumulating statistics of
669 non-thunk incoming edges to NODE. */
671 static bool
672 gather_caller_stats (struct cgraph_node *node, void *data)
674 struct caller_statistics *stats = (struct caller_statistics *) data;
675 struct cgraph_edge *cs;
677 for (cs = node->callers; cs; cs = cs->next_caller)
678 if (!cs->caller->thunk.thunk_p)
680 if (cs->count.ipa ().initialized_p ())
681 stats->count_sum += cs->count.ipa ();
682 stats->freq_sum += cs->frequency ();
683 stats->n_calls++;
684 if (cs->maybe_hot_p ())
685 stats->n_hot_calls ++;
687 return false;
691 /* Return true if this NODE is viable candidate for cloning. */
693 static bool
694 ipcp_cloning_candidate_p (struct cgraph_node *node)
696 struct caller_statistics stats;
698 gcc_checking_assert (node->has_gimple_body_p ());
700 if (!opt_for_fn (node->decl, flag_ipa_cp_clone))
702 if (dump_file)
703 fprintf (dump_file, "Not considering %s for cloning; "
704 "-fipa-cp-clone disabled.\n",
705 node->name ());
706 return false;
709 if (node->optimize_for_size_p ())
711 if (dump_file)
712 fprintf (dump_file, "Not considering %s for cloning; "
713 "optimizing it for size.\n",
714 node->name ());
715 return false;
718 init_caller_stats (&stats);
719 node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats, false);
721 if (ipa_fn_summaries->get (node)->self_size < stats.n_calls)
723 if (dump_file)
724 fprintf (dump_file, "Considering %s for cloning; code might shrink.\n",
725 node->name ());
726 return true;
729 /* When profile is available and function is hot, propagate into it even if
730 calls seems cold; constant propagation can improve function's speed
731 significantly. */
732 if (max_count > profile_count::zero ())
734 if (stats.count_sum > node->count.ipa ().apply_scale (90, 100))
736 if (dump_file)
737 fprintf (dump_file, "Considering %s for cloning; "
738 "usually called directly.\n",
739 node->name ());
740 return true;
743 if (!stats.n_hot_calls)
745 if (dump_file)
746 fprintf (dump_file, "Not considering %s for cloning; no hot calls.\n",
747 node->name ());
748 return false;
750 if (dump_file)
751 fprintf (dump_file, "Considering %s for cloning.\n",
752 node->name ());
753 return true;
756 template <typename valtype>
757 class value_topo_info
759 public:
760 /* Head of the linked list of topologically sorted values. */
761 ipcp_value<valtype> *values_topo;
762 /* Stack for creating SCCs, represented by a linked list too. */
763 ipcp_value<valtype> *stack;
764 /* Counter driving the algorithm in add_val_to_toposort. */
765 int dfs_counter;
767 value_topo_info () : values_topo (NULL), stack (NULL), dfs_counter (0)
769 void add_val (ipcp_value<valtype> *cur_val);
770 void propagate_effects ();
773 /* Arrays representing a topological ordering of call graph nodes and a stack
774 of nodes used during constant propagation and also data required to perform
775 topological sort of values and propagation of benefits in the determined
776 order. */
778 class ipa_topo_info
780 public:
781 /* Array with obtained topological order of cgraph nodes. */
782 struct cgraph_node **order;
783 /* Stack of cgraph nodes used during propagation within SCC until all values
784 in the SCC stabilize. */
785 struct cgraph_node **stack;
786 int nnodes, stack_top;
788 value_topo_info<tree> constants;
789 value_topo_info<ipa_polymorphic_call_context> contexts;
791 ipa_topo_info () : order(NULL), stack(NULL), nnodes(0), stack_top(0),
792 constants ()
796 /* Allocate the arrays in TOPO and topologically sort the nodes into order. */
798 static void
799 build_toporder_info (struct ipa_topo_info *topo)
801 topo->order = XCNEWVEC (struct cgraph_node *, symtab->cgraph_count);
802 topo->stack = XCNEWVEC (struct cgraph_node *, symtab->cgraph_count);
804 gcc_checking_assert (topo->stack_top == 0);
805 topo->nnodes = ipa_reduced_postorder (topo->order, true, true, NULL);
808 /* Free information about strongly connected components and the arrays in
809 TOPO. */
811 static void
812 free_toporder_info (struct ipa_topo_info *topo)
814 ipa_free_postorder_info ();
815 free (topo->order);
816 free (topo->stack);
819 /* Add NODE to the stack in TOPO, unless it is already there. */
821 static inline void
822 push_node_to_stack (struct ipa_topo_info *topo, struct cgraph_node *node)
824 struct ipa_node_params *info = IPA_NODE_REF (node);
825 if (info->node_enqueued)
826 return;
827 info->node_enqueued = 1;
828 topo->stack[topo->stack_top++] = node;
831 /* Pop a node from the stack in TOPO and return it or return NULL if the stack
832 is empty. */
834 static struct cgraph_node *
835 pop_node_from_stack (struct ipa_topo_info *topo)
837 if (topo->stack_top)
839 struct cgraph_node *node;
840 topo->stack_top--;
841 node = topo->stack[topo->stack_top];
842 IPA_NODE_REF (node)->node_enqueued = 0;
843 return node;
845 else
846 return NULL;
849 /* Set lattice LAT to bottom and return true if it previously was not set as
850 such. */
852 template <typename valtype>
853 inline bool
854 ipcp_lattice<valtype>::set_to_bottom ()
856 bool ret = !bottom;
857 bottom = true;
858 return ret;
861 /* Mark lattice as containing an unknown value and return true if it previously
862 was not marked as such. */
864 template <typename valtype>
865 inline bool
866 ipcp_lattice<valtype>::set_contains_variable ()
868 bool ret = !contains_variable;
869 contains_variable = true;
870 return ret;
873 /* Set all aggegate lattices in PLATS to bottom and return true if they were
874 not previously set as such. */
876 static inline bool
877 set_agg_lats_to_bottom (struct ipcp_param_lattices *plats)
879 bool ret = !plats->aggs_bottom;
880 plats->aggs_bottom = true;
881 return ret;
884 /* Mark all aggegate lattices in PLATS as containing an unknown value and
885 return true if they were not previously marked as such. */
887 static inline bool
888 set_agg_lats_contain_variable (struct ipcp_param_lattices *plats)
890 bool ret = !plats->aggs_contain_variable;
891 plats->aggs_contain_variable = true;
892 return ret;
895 bool
896 ipcp_vr_lattice::meet_with (const ipcp_vr_lattice &other)
898 return meet_with_1 (&other.m_vr);
901 /* Meet the current value of the lattice with value ranfge described by VR
902 lattice. */
904 bool
905 ipcp_vr_lattice::meet_with (const value_range *p_vr)
907 return meet_with_1 (p_vr);
910 /* Meet the current value of the lattice with value ranfge described by
911 OTHER_VR lattice. */
913 bool
914 ipcp_vr_lattice::meet_with_1 (const value_range *other_vr)
916 tree min = m_vr.min, max = m_vr.max;
917 value_range_type type = m_vr.type;
919 if (bottom_p ())
920 return false;
922 if (other_vr->type == VR_VARYING)
923 return set_to_bottom ();
925 vrp_meet (&m_vr, other_vr);
926 if (type != m_vr.type
927 || min != m_vr.min
928 || max != m_vr.max)
929 return true;
930 else
931 return false;
934 /* Return true if value range information in the lattice is yet unknown. */
936 bool
937 ipcp_vr_lattice::top_p () const
939 return m_vr.type == VR_UNDEFINED;
942 /* Return true if value range information in the lattice is known to be
943 unusable. */
945 bool
946 ipcp_vr_lattice::bottom_p () const
948 return m_vr.type == VR_VARYING;
951 /* Set value range information in the lattice to bottom. Return true if it
952 previously was in a different state. */
954 bool
955 ipcp_vr_lattice::set_to_bottom ()
957 if (m_vr.type == VR_VARYING)
958 return false;
959 m_vr.type = VR_VARYING;
960 return true;
963 /* Set lattice value to bottom, if it already isn't the case. */
965 bool
966 ipcp_bits_lattice::set_to_bottom ()
968 if (bottom_p ())
969 return false;
970 m_lattice_val = IPA_BITS_VARYING;
971 m_value = 0;
972 m_mask = -1;
973 return true;
976 /* Set to constant if it isn't already. Only meant to be called
977 when switching state from TOP. */
979 bool
980 ipcp_bits_lattice::set_to_constant (widest_int value, widest_int mask)
982 gcc_assert (top_p ());
983 m_lattice_val = IPA_BITS_CONSTANT;
984 m_value = value;
985 m_mask = mask;
986 return true;
989 /* Convert operand to value, mask form. */
991 void
992 ipcp_bits_lattice::get_value_and_mask (tree operand, widest_int *valuep, widest_int *maskp)
994 wide_int get_nonzero_bits (const_tree);
996 if (TREE_CODE (operand) == INTEGER_CST)
998 *valuep = wi::to_widest (operand);
999 *maskp = 0;
1001 else
1003 *valuep = 0;
1004 *maskp = -1;
1008 /* Meet operation, similar to ccp_lattice_meet, we xor values
1009 if this->value, value have different values at same bit positions, we want
1010 to drop that bit to varying. Return true if mask is changed.
1011 This function assumes that the lattice value is in CONSTANT state */
1013 bool
1014 ipcp_bits_lattice::meet_with_1 (widest_int value, widest_int mask,
1015 unsigned precision)
1017 gcc_assert (constant_p ());
1019 widest_int old_mask = m_mask;
1020 m_mask = (m_mask | mask) | (m_value ^ value);
1022 if (wi::sext (m_mask, precision) == -1)
1023 return set_to_bottom ();
1025 return m_mask != old_mask;
1028 /* Meet the bits lattice with operand
1029 described by <value, mask, sgn, precision. */
1031 bool
1032 ipcp_bits_lattice::meet_with (widest_int value, widest_int mask,
1033 unsigned precision)
1035 if (bottom_p ())
1036 return false;
1038 if (top_p ())
1040 if (wi::sext (mask, precision) == -1)
1041 return set_to_bottom ();
1042 return set_to_constant (value, mask);
1045 return meet_with_1 (value, mask, precision);
1048 /* Meet bits lattice with the result of bit_value_binop (other, operand)
1049 if code is binary operation or bit_value_unop (other) if code is unary op.
1050 In the case when code is nop_expr, no adjustment is required. */
1052 bool
1053 ipcp_bits_lattice::meet_with (ipcp_bits_lattice& other, unsigned precision,
1054 signop sgn, enum tree_code code, tree operand)
1056 if (other.bottom_p ())
1057 return set_to_bottom ();
1059 if (bottom_p () || other.top_p ())
1060 return false;
1062 widest_int adjusted_value, adjusted_mask;
1064 if (TREE_CODE_CLASS (code) == tcc_binary)
1066 tree type = TREE_TYPE (operand);
1067 gcc_assert (INTEGRAL_TYPE_P (type));
1068 widest_int o_value, o_mask;
1069 get_value_and_mask (operand, &o_value, &o_mask);
1071 bit_value_binop (code, sgn, precision, &adjusted_value, &adjusted_mask,
1072 sgn, precision, other.get_value (), other.get_mask (),
1073 TYPE_SIGN (type), TYPE_PRECISION (type), o_value, o_mask);
1075 if (wi::sext (adjusted_mask, precision) == -1)
1076 return set_to_bottom ();
1079 else if (TREE_CODE_CLASS (code) == tcc_unary)
1081 bit_value_unop (code, sgn, precision, &adjusted_value,
1082 &adjusted_mask, sgn, precision, other.get_value (),
1083 other.get_mask ());
1085 if (wi::sext (adjusted_mask, precision) == -1)
1086 return set_to_bottom ();
1089 else
1090 return set_to_bottom ();
1092 if (top_p ())
1094 if (wi::sext (adjusted_mask, precision) == -1)
1095 return set_to_bottom ();
1096 return set_to_constant (adjusted_value, adjusted_mask);
1098 else
1099 return meet_with_1 (adjusted_value, adjusted_mask, precision);
1102 /* Mark bot aggregate and scalar lattices as containing an unknown variable,
1103 return true is any of them has not been marked as such so far. */
1105 static inline bool
1106 set_all_contains_variable (struct ipcp_param_lattices *plats)
1108 bool ret;
1109 ret = plats->itself.set_contains_variable ();
1110 ret |= plats->ctxlat.set_contains_variable ();
1111 ret |= set_agg_lats_contain_variable (plats);
1112 ret |= plats->bits_lattice.set_to_bottom ();
1113 ret |= plats->m_value_range.set_to_bottom ();
1114 return ret;
1117 /* Worker of call_for_symbol_thunks_and_aliases, increment the integer DATA
1118 points to by the number of callers to NODE. */
1120 static bool
1121 count_callers (cgraph_node *node, void *data)
1123 int *caller_count = (int *) data;
1125 for (cgraph_edge *cs = node->callers; cs; cs = cs->next_caller)
1126 /* Local thunks can be handled transparently, but if the thunk can not
1127 be optimized out, count it as a real use. */
1128 if (!cs->caller->thunk.thunk_p || !cs->caller->local.local)
1129 ++*caller_count;
1130 return false;
1133 /* Worker of call_for_symbol_thunks_and_aliases, it is supposed to be called on
1134 the one caller of some other node. Set the caller's corresponding flag. */
1136 static bool
1137 set_single_call_flag (cgraph_node *node, void *)
1139 cgraph_edge *cs = node->callers;
1140 /* Local thunks can be handled transparently, skip them. */
1141 while (cs && cs->caller->thunk.thunk_p && cs->caller->local.local)
1142 cs = cs->next_caller;
1143 if (cs)
1145 IPA_NODE_REF (cs->caller)->node_calling_single_call = true;
1146 return true;
1148 return false;
1151 /* Initialize ipcp_lattices. */
1153 static void
1154 initialize_node_lattices (struct cgraph_node *node)
1156 struct ipa_node_params *info = IPA_NODE_REF (node);
1157 struct cgraph_edge *ie;
1158 bool disable = false, variable = false;
1159 int i;
1161 gcc_checking_assert (node->has_gimple_body_p ());
1162 if (cgraph_local_p (node))
1164 int caller_count = 0;
1165 node->call_for_symbol_thunks_and_aliases (count_callers, &caller_count,
1166 true);
1167 gcc_checking_assert (caller_count > 0);
1168 if (caller_count == 1)
1169 node->call_for_symbol_thunks_and_aliases (set_single_call_flag,
1170 NULL, true);
1172 else
1174 /* When cloning is allowed, we can assume that externally visible
1175 functions are not called. We will compensate this by cloning
1176 later. */
1177 if (ipcp_versionable_function_p (node)
1178 && ipcp_cloning_candidate_p (node))
1179 variable = true;
1180 else
1181 disable = true;
1184 for (i = 0; i < ipa_get_param_count (info); i++)
1186 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
1187 plats->m_value_range.init ();
1190 if (disable || variable)
1192 for (i = 0; i < ipa_get_param_count (info); i++)
1194 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
1195 if (disable)
1197 plats->itself.set_to_bottom ();
1198 plats->ctxlat.set_to_bottom ();
1199 set_agg_lats_to_bottom (plats);
1200 plats->bits_lattice.set_to_bottom ();
1201 plats->m_value_range.set_to_bottom ();
1203 else
1204 set_all_contains_variable (plats);
1206 if (dump_file && (dump_flags & TDF_DETAILS)
1207 && !node->alias && !node->thunk.thunk_p)
1208 fprintf (dump_file, "Marking all lattices of %s as %s\n",
1209 node->dump_name (), disable ? "BOTTOM" : "VARIABLE");
1212 for (ie = node->indirect_calls; ie; ie = ie->next_callee)
1213 if (ie->indirect_info->polymorphic
1214 && ie->indirect_info->param_index >= 0)
1216 gcc_checking_assert (ie->indirect_info->param_index >= 0);
1217 ipa_get_parm_lattices (info,
1218 ie->indirect_info->param_index)->virt_call = 1;
1222 /* Return the result of a (possibly arithmetic) pass through jump function
1223 JFUNC on the constant value INPUT. RES_TYPE is the type of the parameter
1224 to which the result is passed. Return NULL_TREE if that cannot be
1225 determined or be considered an interprocedural invariant. */
1227 static tree
1228 ipa_get_jf_pass_through_result (struct ipa_jump_func *jfunc, tree input,
1229 tree res_type)
1231 tree res;
1233 if (ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
1234 return input;
1235 if (!is_gimple_ip_invariant (input))
1236 return NULL_TREE;
1238 tree_code opcode = ipa_get_jf_pass_through_operation (jfunc);
1239 if (!res_type)
1241 if (TREE_CODE_CLASS (opcode) == tcc_comparison)
1242 res_type = boolean_type_node;
1243 else if (expr_type_first_operand_type_p (opcode))
1244 res_type = TREE_TYPE (input);
1245 else
1246 return NULL_TREE;
1249 if (TREE_CODE_CLASS (opcode) == tcc_unary)
1250 res = fold_unary (opcode, res_type, input);
1251 else
1252 res = fold_binary (opcode, res_type, input,
1253 ipa_get_jf_pass_through_operand (jfunc));
1255 if (res && !is_gimple_ip_invariant (res))
1256 return NULL_TREE;
1258 return res;
1261 /* Return the result of an ancestor jump function JFUNC on the constant value
1262 INPUT. Return NULL_TREE if that cannot be determined. */
1264 static tree
1265 ipa_get_jf_ancestor_result (struct ipa_jump_func *jfunc, tree input)
1267 gcc_checking_assert (TREE_CODE (input) != TREE_BINFO);
1268 if (TREE_CODE (input) == ADDR_EXPR)
1270 tree t = TREE_OPERAND (input, 0);
1271 t = build_ref_for_offset (EXPR_LOCATION (t), t,
1272 ipa_get_jf_ancestor_offset (jfunc), false,
1273 ptr_type_node, NULL, false);
1274 return build_fold_addr_expr (t);
1276 else
1277 return NULL_TREE;
1280 /* Determine whether JFUNC evaluates to a single known constant value and if
1281 so, return it. Otherwise return NULL. INFO describes the caller node or
1282 the one it is inlined to, so that pass-through jump functions can be
1283 evaluated. PARM_TYPE is the type of the parameter to which the result is
1284 passed. */
1286 tree
1287 ipa_value_from_jfunc (struct ipa_node_params *info, struct ipa_jump_func *jfunc,
1288 tree parm_type)
1290 if (jfunc->type == IPA_JF_CONST)
1291 return ipa_get_jf_constant (jfunc);
1292 else if (jfunc->type == IPA_JF_PASS_THROUGH
1293 || jfunc->type == IPA_JF_ANCESTOR)
1295 tree input;
1296 int idx;
1298 if (jfunc->type == IPA_JF_PASS_THROUGH)
1299 idx = ipa_get_jf_pass_through_formal_id (jfunc);
1300 else
1301 idx = ipa_get_jf_ancestor_formal_id (jfunc);
1303 if (info->ipcp_orig_node)
1304 input = info->known_csts[idx];
1305 else
1307 ipcp_lattice<tree> *lat;
1309 if (!info->lattices
1310 || idx >= ipa_get_param_count (info))
1311 return NULL_TREE;
1312 lat = ipa_get_scalar_lat (info, idx);
1313 if (!lat->is_single_const ())
1314 return NULL_TREE;
1315 input = lat->values->value;
1318 if (!input)
1319 return NULL_TREE;
1321 if (jfunc->type == IPA_JF_PASS_THROUGH)
1322 return ipa_get_jf_pass_through_result (jfunc, input, parm_type);
1323 else
1324 return ipa_get_jf_ancestor_result (jfunc, input);
1326 else
1327 return NULL_TREE;
1330 /* Determie whether JFUNC evaluates to single known polymorphic context, given
1331 that INFO describes the caller node or the one it is inlined to, CS is the
1332 call graph edge corresponding to JFUNC and CSIDX index of the described
1333 parameter. */
1335 ipa_polymorphic_call_context
1336 ipa_context_from_jfunc (ipa_node_params *info, cgraph_edge *cs, int csidx,
1337 ipa_jump_func *jfunc)
1339 ipa_edge_args *args = IPA_EDGE_REF (cs);
1340 ipa_polymorphic_call_context ctx;
1341 ipa_polymorphic_call_context *edge_ctx
1342 = cs ? ipa_get_ith_polymorhic_call_context (args, csidx) : NULL;
1344 if (edge_ctx && !edge_ctx->useless_p ())
1345 ctx = *edge_ctx;
1347 if (jfunc->type == IPA_JF_PASS_THROUGH
1348 || jfunc->type == IPA_JF_ANCESTOR)
1350 ipa_polymorphic_call_context srcctx;
1351 int srcidx;
1352 bool type_preserved = true;
1353 if (jfunc->type == IPA_JF_PASS_THROUGH)
1355 if (ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR)
1356 return ctx;
1357 type_preserved = ipa_get_jf_pass_through_type_preserved (jfunc);
1358 srcidx = ipa_get_jf_pass_through_formal_id (jfunc);
1360 else
1362 type_preserved = ipa_get_jf_ancestor_type_preserved (jfunc);
1363 srcidx = ipa_get_jf_ancestor_formal_id (jfunc);
1365 if (info->ipcp_orig_node)
1367 if (info->known_contexts.exists ())
1368 srcctx = info->known_contexts[srcidx];
1370 else
1372 if (!info->lattices
1373 || srcidx >= ipa_get_param_count (info))
1374 return ctx;
1375 ipcp_lattice<ipa_polymorphic_call_context> *lat;
1376 lat = ipa_get_poly_ctx_lat (info, srcidx);
1377 if (!lat->is_single_const ())
1378 return ctx;
1379 srcctx = lat->values->value;
1381 if (srcctx.useless_p ())
1382 return ctx;
1383 if (jfunc->type == IPA_JF_ANCESTOR)
1384 srcctx.offset_by (ipa_get_jf_ancestor_offset (jfunc));
1385 if (!type_preserved)
1386 srcctx.possible_dynamic_type_change (cs->in_polymorphic_cdtor);
1387 srcctx.combine_with (ctx);
1388 return srcctx;
1391 return ctx;
1394 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
1395 bottom, not containing a variable component and without any known value at
1396 the same time. */
1398 DEBUG_FUNCTION void
1399 ipcp_verify_propagated_values (void)
1401 struct cgraph_node *node;
1403 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
1405 struct ipa_node_params *info = IPA_NODE_REF (node);
1406 int i, count = ipa_get_param_count (info);
1408 for (i = 0; i < count; i++)
1410 ipcp_lattice<tree> *lat = ipa_get_scalar_lat (info, i);
1412 if (!lat->bottom
1413 && !lat->contains_variable
1414 && lat->values_count == 0)
1416 if (dump_file)
1418 symtab->dump (dump_file);
1419 fprintf (dump_file, "\nIPA lattices after constant "
1420 "propagation, before gcc_unreachable:\n");
1421 print_all_lattices (dump_file, true, false);
1424 gcc_unreachable ();
1430 /* Return true iff X and Y should be considered equal values by IPA-CP. */
1432 static bool
1433 values_equal_for_ipcp_p (tree x, tree y)
1435 gcc_checking_assert (x != NULL_TREE && y != NULL_TREE);
1437 if (x == y)
1438 return true;
1440 if (TREE_CODE (x) == ADDR_EXPR
1441 && TREE_CODE (y) == ADDR_EXPR
1442 && TREE_CODE (TREE_OPERAND (x, 0)) == CONST_DECL
1443 && TREE_CODE (TREE_OPERAND (y, 0)) == CONST_DECL)
1444 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x, 0)),
1445 DECL_INITIAL (TREE_OPERAND (y, 0)), 0);
1446 else
1447 return operand_equal_p (x, y, 0);
1450 /* Return true iff X and Y should be considered equal contexts by IPA-CP. */
1452 static bool
1453 values_equal_for_ipcp_p (ipa_polymorphic_call_context x,
1454 ipa_polymorphic_call_context y)
1456 return x.equal_to (y);
1460 /* Add a new value source to the value represented by THIS, marking that a
1461 value comes from edge CS and (if the underlying jump function is a
1462 pass-through or an ancestor one) from a caller value SRC_VAL of a caller
1463 parameter described by SRC_INDEX. OFFSET is negative if the source was the
1464 scalar value of the parameter itself or the offset within an aggregate. */
1466 template <typename valtype>
1467 void
1468 ipcp_value<valtype>::add_source (cgraph_edge *cs, ipcp_value *src_val,
1469 int src_idx, HOST_WIDE_INT offset)
1471 ipcp_value_source<valtype> *src;
1473 src = new (ipcp_sources_pool.allocate ()) ipcp_value_source<valtype>;
1474 src->offset = offset;
1475 src->cs = cs;
1476 src->val = src_val;
1477 src->index = src_idx;
1479 src->next = sources;
1480 sources = src;
1483 /* Allocate a new ipcp_value holding a tree constant, initialize its value to
1484 SOURCE and clear all other fields. */
1486 static ipcp_value<tree> *
1487 allocate_and_init_ipcp_value (tree source)
1489 ipcp_value<tree> *val;
1491 val = new (ipcp_cst_values_pool.allocate ()) ipcp_value<tree>();
1492 val->value = source;
1493 return val;
1496 /* Allocate a new ipcp_value holding a polymorphic context, initialize its
1497 value to SOURCE and clear all other fields. */
1499 static ipcp_value<ipa_polymorphic_call_context> *
1500 allocate_and_init_ipcp_value (ipa_polymorphic_call_context source)
1502 ipcp_value<ipa_polymorphic_call_context> *val;
1504 // TODO
1505 val = new (ipcp_poly_ctx_values_pool.allocate ())
1506 ipcp_value<ipa_polymorphic_call_context>();
1507 val->value = source;
1508 return val;
1511 /* Try to add NEWVAL to LAT, potentially creating a new ipcp_value for it. CS,
1512 SRC_VAL SRC_INDEX and OFFSET are meant for add_source and have the same
1513 meaning. OFFSET -1 means the source is scalar and not a part of an
1514 aggregate. */
1516 template <typename valtype>
1517 bool
1518 ipcp_lattice<valtype>::add_value (valtype newval, cgraph_edge *cs,
1519 ipcp_value<valtype> *src_val,
1520 int src_idx, HOST_WIDE_INT offset)
1522 ipcp_value<valtype> *val;
1524 if (bottom)
1525 return false;
1527 for (val = values; val; val = val->next)
1528 if (values_equal_for_ipcp_p (val->value, newval))
1530 if (ipa_edge_within_scc (cs))
1532 ipcp_value_source<valtype> *s;
1533 for (s = val->sources; s; s = s->next)
1534 if (s->cs == cs)
1535 break;
1536 if (s)
1537 return false;
1540 val->add_source (cs, src_val, src_idx, offset);
1541 return false;
1544 if (values_count == PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE))
1546 /* We can only free sources, not the values themselves, because sources
1547 of other values in this SCC might point to them. */
1548 for (val = values; val; val = val->next)
1550 while (val->sources)
1552 ipcp_value_source<valtype> *src = val->sources;
1553 val->sources = src->next;
1554 ipcp_sources_pool.remove ((ipcp_value_source<tree>*)src);
1558 values = NULL;
1559 return set_to_bottom ();
1562 values_count++;
1563 val = allocate_and_init_ipcp_value (newval);
1564 val->add_source (cs, src_val, src_idx, offset);
1565 val->next = values;
1566 values = val;
1567 return true;
1570 /* Propagate values through a pass-through jump function JFUNC associated with
1571 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1572 is the index of the source parameter. PARM_TYPE is the type of the
1573 parameter to which the result is passed. */
1575 static bool
1576 propagate_vals_across_pass_through (cgraph_edge *cs, ipa_jump_func *jfunc,
1577 ipcp_lattice<tree> *src_lat,
1578 ipcp_lattice<tree> *dest_lat, int src_idx,
1579 tree parm_type)
1581 ipcp_value<tree> *src_val;
1582 bool ret = false;
1584 /* Do not create new values when propagating within an SCC because if there
1585 are arithmetic functions with circular dependencies, there is infinite
1586 number of them and we would just make lattices bottom. */
1587 if ((ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR)
1588 && ipa_edge_within_scc (cs))
1589 ret = dest_lat->set_contains_variable ();
1590 else
1591 for (src_val = src_lat->values; src_val; src_val = src_val->next)
1593 tree cstval = ipa_get_jf_pass_through_result (jfunc, src_val->value,
1594 parm_type);
1596 if (cstval)
1597 ret |= dest_lat->add_value (cstval, cs, src_val, src_idx);
1598 else
1599 ret |= dest_lat->set_contains_variable ();
1602 return ret;
1605 /* Propagate values through an ancestor jump function JFUNC associated with
1606 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1607 is the index of the source parameter. */
1609 static bool
1610 propagate_vals_across_ancestor (struct cgraph_edge *cs,
1611 struct ipa_jump_func *jfunc,
1612 ipcp_lattice<tree> *src_lat,
1613 ipcp_lattice<tree> *dest_lat, int src_idx)
1615 ipcp_value<tree> *src_val;
1616 bool ret = false;
1618 if (ipa_edge_within_scc (cs))
1619 return dest_lat->set_contains_variable ();
1621 for (src_val = src_lat->values; src_val; src_val = src_val->next)
1623 tree t = ipa_get_jf_ancestor_result (jfunc, src_val->value);
1625 if (t)
1626 ret |= dest_lat->add_value (t, cs, src_val, src_idx);
1627 else
1628 ret |= dest_lat->set_contains_variable ();
1631 return ret;
1634 /* Propagate scalar values across jump function JFUNC that is associated with
1635 edge CS and put the values into DEST_LAT. PARM_TYPE is the type of the
1636 parameter to which the result is passed. */
1638 static bool
1639 propagate_scalar_across_jump_function (struct cgraph_edge *cs,
1640 struct ipa_jump_func *jfunc,
1641 ipcp_lattice<tree> *dest_lat,
1642 tree param_type)
1644 if (dest_lat->bottom)
1645 return false;
1647 if (jfunc->type == IPA_JF_CONST)
1649 tree val = ipa_get_jf_constant (jfunc);
1650 return dest_lat->add_value (val, cs, NULL, 0);
1652 else if (jfunc->type == IPA_JF_PASS_THROUGH
1653 || jfunc->type == IPA_JF_ANCESTOR)
1655 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1656 ipcp_lattice<tree> *src_lat;
1657 int src_idx;
1658 bool ret;
1660 if (jfunc->type == IPA_JF_PASS_THROUGH)
1661 src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
1662 else
1663 src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
1665 src_lat = ipa_get_scalar_lat (caller_info, src_idx);
1666 if (src_lat->bottom)
1667 return dest_lat->set_contains_variable ();
1669 /* If we would need to clone the caller and cannot, do not propagate. */
1670 if (!ipcp_versionable_function_p (cs->caller)
1671 && (src_lat->contains_variable
1672 || (src_lat->values_count > 1)))
1673 return dest_lat->set_contains_variable ();
1675 if (jfunc->type == IPA_JF_PASS_THROUGH)
1676 ret = propagate_vals_across_pass_through (cs, jfunc, src_lat,
1677 dest_lat, src_idx, param_type);
1678 else
1679 ret = propagate_vals_across_ancestor (cs, jfunc, src_lat, dest_lat,
1680 src_idx);
1682 if (src_lat->contains_variable)
1683 ret |= dest_lat->set_contains_variable ();
1685 return ret;
1688 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1689 use it for indirect inlining), we should propagate them too. */
1690 return dest_lat->set_contains_variable ();
1693 /* Propagate scalar values across jump function JFUNC that is associated with
1694 edge CS and describes argument IDX and put the values into DEST_LAT. */
1696 static bool
1697 propagate_context_across_jump_function (cgraph_edge *cs,
1698 ipa_jump_func *jfunc, int idx,
1699 ipcp_lattice<ipa_polymorphic_call_context> *dest_lat)
1701 ipa_edge_args *args = IPA_EDGE_REF (cs);
1702 if (dest_lat->bottom)
1703 return false;
1704 bool ret = false;
1705 bool added_sth = false;
1706 bool type_preserved = true;
1708 ipa_polymorphic_call_context edge_ctx, *edge_ctx_ptr
1709 = ipa_get_ith_polymorhic_call_context (args, idx);
1711 if (edge_ctx_ptr)
1712 edge_ctx = *edge_ctx_ptr;
1714 if (jfunc->type == IPA_JF_PASS_THROUGH
1715 || jfunc->type == IPA_JF_ANCESTOR)
1717 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1718 int src_idx;
1719 ipcp_lattice<ipa_polymorphic_call_context> *src_lat;
1721 /* TODO: Once we figure out how to propagate speculations, it will
1722 probably be a good idea to switch to speculation if type_preserved is
1723 not set instead of punting. */
1724 if (jfunc->type == IPA_JF_PASS_THROUGH)
1726 if (ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR)
1727 goto prop_fail;
1728 type_preserved = ipa_get_jf_pass_through_type_preserved (jfunc);
1729 src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
1731 else
1733 type_preserved = ipa_get_jf_ancestor_type_preserved (jfunc);
1734 src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
1737 src_lat = ipa_get_poly_ctx_lat (caller_info, src_idx);
1738 /* If we would need to clone the caller and cannot, do not propagate. */
1739 if (!ipcp_versionable_function_p (cs->caller)
1740 && (src_lat->contains_variable
1741 || (src_lat->values_count > 1)))
1742 goto prop_fail;
1744 ipcp_value<ipa_polymorphic_call_context> *src_val;
1745 for (src_val = src_lat->values; src_val; src_val = src_val->next)
1747 ipa_polymorphic_call_context cur = src_val->value;
1749 if (!type_preserved)
1750 cur.possible_dynamic_type_change (cs->in_polymorphic_cdtor);
1751 if (jfunc->type == IPA_JF_ANCESTOR)
1752 cur.offset_by (ipa_get_jf_ancestor_offset (jfunc));
1753 /* TODO: In cases we know how the context is going to be used,
1754 we can improve the result by passing proper OTR_TYPE. */
1755 cur.combine_with (edge_ctx);
1756 if (!cur.useless_p ())
1758 if (src_lat->contains_variable
1759 && !edge_ctx.equal_to (cur))
1760 ret |= dest_lat->set_contains_variable ();
1761 ret |= dest_lat->add_value (cur, cs, src_val, src_idx);
1762 added_sth = true;
1768 prop_fail:
1769 if (!added_sth)
1771 if (!edge_ctx.useless_p ())
1772 ret |= dest_lat->add_value (edge_ctx, cs);
1773 else
1774 ret |= dest_lat->set_contains_variable ();
1777 return ret;
1780 /* Propagate bits across jfunc that is associated with
1781 edge cs and update dest_lattice accordingly. */
1783 bool
1784 propagate_bits_across_jump_function (cgraph_edge *cs, int idx,
1785 ipa_jump_func *jfunc,
1786 ipcp_bits_lattice *dest_lattice)
1788 if (dest_lattice->bottom_p ())
1789 return false;
1791 enum availability availability;
1792 cgraph_node *callee = cs->callee->function_symbol (&availability);
1793 struct ipa_node_params *callee_info = IPA_NODE_REF (callee);
1794 tree parm_type = ipa_get_type (callee_info, idx);
1796 /* For K&R C programs, ipa_get_type() could return NULL_TREE.
1797 Avoid the transform for these cases. */
1798 if (!parm_type)
1800 if (dump_file && (dump_flags & TDF_DETAILS))
1801 fprintf (dump_file, "Setting dest_lattice to bottom, because"
1802 " param %i type is NULL for %s\n", idx,
1803 cs->callee->name ());
1805 return dest_lattice->set_to_bottom ();
1808 unsigned precision = TYPE_PRECISION (parm_type);
1809 signop sgn = TYPE_SIGN (parm_type);
1811 if (jfunc->type == IPA_JF_PASS_THROUGH
1812 || jfunc->type == IPA_JF_ANCESTOR)
1814 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1815 tree operand = NULL_TREE;
1816 enum tree_code code;
1817 unsigned src_idx;
1819 if (jfunc->type == IPA_JF_PASS_THROUGH)
1821 code = ipa_get_jf_pass_through_operation (jfunc);
1822 src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
1823 if (code != NOP_EXPR)
1824 operand = ipa_get_jf_pass_through_operand (jfunc);
1826 else
1828 code = POINTER_PLUS_EXPR;
1829 src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
1830 unsigned HOST_WIDE_INT offset = ipa_get_jf_ancestor_offset (jfunc) / BITS_PER_UNIT;
1831 operand = build_int_cstu (size_type_node, offset);
1834 struct ipcp_param_lattices *src_lats
1835 = ipa_get_parm_lattices (caller_info, src_idx);
1837 /* Try to propagate bits if src_lattice is bottom, but jfunc is known.
1838 for eg consider:
1839 int f(int x)
1841 g (x & 0xff);
1843 Assume lattice for x is bottom, however we can still propagate
1844 result of x & 0xff == 0xff, which gets computed during ccp1 pass
1845 and we store it in jump function during analysis stage. */
1847 if (src_lats->bits_lattice.bottom_p ()
1848 && jfunc->bits)
1849 return dest_lattice->meet_with (jfunc->bits->value, jfunc->bits->mask,
1850 precision);
1851 else
1852 return dest_lattice->meet_with (src_lats->bits_lattice, precision, sgn,
1853 code, operand);
1856 else if (jfunc->type == IPA_JF_ANCESTOR)
1857 return dest_lattice->set_to_bottom ();
1858 else if (jfunc->bits)
1859 return dest_lattice->meet_with (jfunc->bits->value, jfunc->bits->mask,
1860 precision);
1861 else
1862 return dest_lattice->set_to_bottom ();
1865 /* Emulate effects of unary OPERATION and/or conversion from SRC_TYPE to
1866 DST_TYPE on value range in SRC_VR and store it to DST_VR. Return true if
1867 the result is a range or an anti-range. */
1869 static bool
1870 ipa_vr_operation_and_type_effects (value_range *dst_vr, value_range *src_vr,
1871 enum tree_code operation,
1872 tree dst_type, tree src_type)
1874 memset (dst_vr, 0, sizeof (*dst_vr));
1875 extract_range_from_unary_expr (dst_vr, operation, dst_type, src_vr, src_type);
1876 if (dst_vr->type == VR_RANGE || dst_vr->type == VR_ANTI_RANGE)
1877 return true;
1878 else
1879 return false;
1882 /* Propagate value range across jump function JFUNC that is associated with
1883 edge CS with param of callee of PARAM_TYPE and update DEST_PLATS
1884 accordingly. */
1886 static bool
1887 propagate_vr_across_jump_function (cgraph_edge *cs, ipa_jump_func *jfunc,
1888 struct ipcp_param_lattices *dest_plats,
1889 tree param_type)
1891 ipcp_vr_lattice *dest_lat = &dest_plats->m_value_range;
1893 if (dest_lat->bottom_p ())
1894 return false;
1896 if (!param_type
1897 || (!INTEGRAL_TYPE_P (param_type)
1898 && !POINTER_TYPE_P (param_type)))
1899 return dest_lat->set_to_bottom ();
1901 if (jfunc->type == IPA_JF_PASS_THROUGH)
1903 enum tree_code operation = ipa_get_jf_pass_through_operation (jfunc);
1905 if (TREE_CODE_CLASS (operation) == tcc_unary)
1907 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1908 int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
1909 tree operand_type = ipa_get_type (caller_info, src_idx);
1910 struct ipcp_param_lattices *src_lats
1911 = ipa_get_parm_lattices (caller_info, src_idx);
1913 if (src_lats->m_value_range.bottom_p ())
1914 return dest_lat->set_to_bottom ();
1915 value_range vr;
1916 if (ipa_vr_operation_and_type_effects (&vr,
1917 &src_lats->m_value_range.m_vr,
1918 operation, param_type,
1919 operand_type))
1920 return dest_lat->meet_with (&vr);
1923 else if (jfunc->type == IPA_JF_CONST)
1925 tree val = ipa_get_jf_constant (jfunc);
1926 if (TREE_CODE (val) == INTEGER_CST)
1928 val = fold_convert (param_type, val);
1929 if (TREE_OVERFLOW_P (val))
1930 val = drop_tree_overflow (val);
1932 value_range tmpvr;
1933 memset (&tmpvr, 0, sizeof (tmpvr));
1934 tmpvr.type = VR_RANGE;
1935 tmpvr.min = val;
1936 tmpvr.max = val;
1937 return dest_lat->meet_with (&tmpvr);
1941 value_range vr;
1942 if (jfunc->m_vr
1943 && ipa_vr_operation_and_type_effects (&vr, jfunc->m_vr, NOP_EXPR,
1944 param_type,
1945 TREE_TYPE (jfunc->m_vr->min)))
1946 return dest_lat->meet_with (&vr);
1947 else
1948 return dest_lat->set_to_bottom ();
1951 /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
1952 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
1953 other cases, return false). If there are no aggregate items, set
1954 aggs_by_ref to NEW_AGGS_BY_REF. */
1956 static bool
1957 set_check_aggs_by_ref (struct ipcp_param_lattices *dest_plats,
1958 bool new_aggs_by_ref)
1960 if (dest_plats->aggs)
1962 if (dest_plats->aggs_by_ref != new_aggs_by_ref)
1964 set_agg_lats_to_bottom (dest_plats);
1965 return true;
1968 else
1969 dest_plats->aggs_by_ref = new_aggs_by_ref;
1970 return false;
1973 /* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
1974 already existing lattice for the given OFFSET and SIZE, marking all skipped
1975 lattices as containing variable and checking for overlaps. If there is no
1976 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
1977 it with offset, size and contains_variable to PRE_EXISTING, and return true,
1978 unless there are too many already. If there are two many, return false. If
1979 there are overlaps turn whole DEST_PLATS to bottom and return false. If any
1980 skipped lattices were newly marked as containing variable, set *CHANGE to
1981 true. */
1983 static bool
1984 merge_agg_lats_step (struct ipcp_param_lattices *dest_plats,
1985 HOST_WIDE_INT offset, HOST_WIDE_INT val_size,
1986 struct ipcp_agg_lattice ***aglat,
1987 bool pre_existing, bool *change)
1989 gcc_checking_assert (offset >= 0);
1991 while (**aglat && (**aglat)->offset < offset)
1993 if ((**aglat)->offset + (**aglat)->size > offset)
1995 set_agg_lats_to_bottom (dest_plats);
1996 return false;
1998 *change |= (**aglat)->set_contains_variable ();
1999 *aglat = &(**aglat)->next;
2002 if (**aglat && (**aglat)->offset == offset)
2004 if ((**aglat)->size != val_size
2005 || ((**aglat)->next
2006 && (**aglat)->next->offset < offset + val_size))
2008 set_agg_lats_to_bottom (dest_plats);
2009 return false;
2011 gcc_checking_assert (!(**aglat)->next
2012 || (**aglat)->next->offset >= offset + val_size);
2013 return true;
2015 else
2017 struct ipcp_agg_lattice *new_al;
2019 if (**aglat && (**aglat)->offset < offset + val_size)
2021 set_agg_lats_to_bottom (dest_plats);
2022 return false;
2024 if (dest_plats->aggs_count == PARAM_VALUE (PARAM_IPA_MAX_AGG_ITEMS))
2025 return false;
2026 dest_plats->aggs_count++;
2027 new_al = ipcp_agg_lattice_pool.allocate ();
2028 memset (new_al, 0, sizeof (*new_al));
2030 new_al->offset = offset;
2031 new_al->size = val_size;
2032 new_al->contains_variable = pre_existing;
2034 new_al->next = **aglat;
2035 **aglat = new_al;
2036 return true;
2040 /* Set all AGLAT and all other aggregate lattices reachable by next pointers as
2041 containing an unknown value. */
2043 static bool
2044 set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice *aglat)
2046 bool ret = false;
2047 while (aglat)
2049 ret |= aglat->set_contains_variable ();
2050 aglat = aglat->next;
2052 return ret;
2055 /* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
2056 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source
2057 parameter used for lattice value sources. Return true if DEST_PLATS changed
2058 in any way. */
2060 static bool
2061 merge_aggregate_lattices (struct cgraph_edge *cs,
2062 struct ipcp_param_lattices *dest_plats,
2063 struct ipcp_param_lattices *src_plats,
2064 int src_idx, HOST_WIDE_INT offset_delta)
2066 bool pre_existing = dest_plats->aggs != NULL;
2067 struct ipcp_agg_lattice **dst_aglat;
2068 bool ret = false;
2070 if (set_check_aggs_by_ref (dest_plats, src_plats->aggs_by_ref))
2071 return true;
2072 if (src_plats->aggs_bottom)
2073 return set_agg_lats_contain_variable (dest_plats);
2074 if (src_plats->aggs_contain_variable)
2075 ret |= set_agg_lats_contain_variable (dest_plats);
2076 dst_aglat = &dest_plats->aggs;
2078 for (struct ipcp_agg_lattice *src_aglat = src_plats->aggs;
2079 src_aglat;
2080 src_aglat = src_aglat->next)
2082 HOST_WIDE_INT new_offset = src_aglat->offset - offset_delta;
2084 if (new_offset < 0)
2085 continue;
2086 if (merge_agg_lats_step (dest_plats, new_offset, src_aglat->size,
2087 &dst_aglat, pre_existing, &ret))
2089 struct ipcp_agg_lattice *new_al = *dst_aglat;
2091 dst_aglat = &(*dst_aglat)->next;
2092 if (src_aglat->bottom)
2094 ret |= new_al->set_contains_variable ();
2095 continue;
2097 if (src_aglat->contains_variable)
2098 ret |= new_al->set_contains_variable ();
2099 for (ipcp_value<tree> *val = src_aglat->values;
2100 val;
2101 val = val->next)
2102 ret |= new_al->add_value (val->value, cs, val, src_idx,
2103 src_aglat->offset);
2105 else if (dest_plats->aggs_bottom)
2106 return true;
2108 ret |= set_chain_of_aglats_contains_variable (*dst_aglat);
2109 return ret;
2112 /* Determine whether there is anything to propagate FROM SRC_PLATS through a
2113 pass-through JFUNC and if so, whether it has conform and conforms to the
2114 rules about propagating values passed by reference. */
2116 static bool
2117 agg_pass_through_permissible_p (struct ipcp_param_lattices *src_plats,
2118 struct ipa_jump_func *jfunc)
2120 return src_plats->aggs
2121 && (!src_plats->aggs_by_ref
2122 || ipa_get_jf_pass_through_agg_preserved (jfunc));
2125 /* Propagate scalar values across jump function JFUNC that is associated with
2126 edge CS and put the values into DEST_LAT. */
2128 static bool
2129 propagate_aggs_across_jump_function (struct cgraph_edge *cs,
2130 struct ipa_jump_func *jfunc,
2131 struct ipcp_param_lattices *dest_plats)
2133 bool ret = false;
2135 if (dest_plats->aggs_bottom)
2136 return false;
2138 if (jfunc->type == IPA_JF_PASS_THROUGH
2139 && ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
2141 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
2142 int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
2143 struct ipcp_param_lattices *src_plats;
2145 src_plats = ipa_get_parm_lattices (caller_info, src_idx);
2146 if (agg_pass_through_permissible_p (src_plats, jfunc))
2148 /* Currently we do not produce clobber aggregate jump
2149 functions, replace with merging when we do. */
2150 gcc_assert (!jfunc->agg.items);
2151 ret |= merge_aggregate_lattices (cs, dest_plats, src_plats,
2152 src_idx, 0);
2154 else
2155 ret |= set_agg_lats_contain_variable (dest_plats);
2157 else if (jfunc->type == IPA_JF_ANCESTOR
2158 && ipa_get_jf_ancestor_agg_preserved (jfunc))
2160 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
2161 int src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
2162 struct ipcp_param_lattices *src_plats;
2164 src_plats = ipa_get_parm_lattices (caller_info, src_idx);
2165 if (src_plats->aggs && src_plats->aggs_by_ref)
2167 /* Currently we do not produce clobber aggregate jump
2168 functions, replace with merging when we do. */
2169 gcc_assert (!jfunc->agg.items);
2170 ret |= merge_aggregate_lattices (cs, dest_plats, src_plats, src_idx,
2171 ipa_get_jf_ancestor_offset (jfunc));
2173 else if (!src_plats->aggs_by_ref)
2174 ret |= set_agg_lats_to_bottom (dest_plats);
2175 else
2176 ret |= set_agg_lats_contain_variable (dest_plats);
2178 else if (jfunc->agg.items)
2180 bool pre_existing = dest_plats->aggs != NULL;
2181 struct ipcp_agg_lattice **aglat = &dest_plats->aggs;
2182 struct ipa_agg_jf_item *item;
2183 int i;
2185 if (set_check_aggs_by_ref (dest_plats, jfunc->agg.by_ref))
2186 return true;
2188 FOR_EACH_VEC_ELT (*jfunc->agg.items, i, item)
2190 HOST_WIDE_INT val_size;
2192 if (item->offset < 0)
2193 continue;
2194 gcc_checking_assert (is_gimple_ip_invariant (item->value));
2195 val_size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (item->value)));
2197 if (merge_agg_lats_step (dest_plats, item->offset, val_size,
2198 &aglat, pre_existing, &ret))
2200 ret |= (*aglat)->add_value (item->value, cs, NULL, 0, 0);
2201 aglat = &(*aglat)->next;
2203 else if (dest_plats->aggs_bottom)
2204 return true;
2207 ret |= set_chain_of_aglats_contains_variable (*aglat);
2209 else
2210 ret |= set_agg_lats_contain_variable (dest_plats);
2212 return ret;
2215 /* Return true if on the way cfrom CS->caller to the final (non-alias and
2216 non-thunk) destination, the call passes through a thunk. */
2218 static bool
2219 call_passes_through_thunk_p (cgraph_edge *cs)
2221 cgraph_node *alias_or_thunk = cs->callee;
2222 while (alias_or_thunk->alias)
2223 alias_or_thunk = alias_or_thunk->get_alias_target ();
2224 return alias_or_thunk->thunk.thunk_p;
2227 /* Propagate constants from the caller to the callee of CS. INFO describes the
2228 caller. */
2230 static bool
2231 propagate_constants_across_call (struct cgraph_edge *cs)
2233 struct ipa_node_params *callee_info;
2234 enum availability availability;
2235 cgraph_node *callee;
2236 struct ipa_edge_args *args;
2237 bool ret = false;
2238 int i, args_count, parms_count;
2240 callee = cs->callee->function_symbol (&availability);
2241 if (!callee->definition)
2242 return false;
2243 gcc_checking_assert (callee->has_gimple_body_p ());
2244 callee_info = IPA_NODE_REF (callee);
2246 args = IPA_EDGE_REF (cs);
2247 args_count = ipa_get_cs_argument_count (args);
2248 parms_count = ipa_get_param_count (callee_info);
2249 if (parms_count == 0)
2250 return false;
2252 /* No propagation through instrumentation thunks is available yet.
2253 It should be possible with proper mapping of call args and
2254 instrumented callee params in the propagation loop below. But
2255 this case mostly occurs when legacy code calls instrumented code
2256 and it is not a primary target for optimizations.
2257 We detect instrumentation thunks in aliases and thunks chain by
2258 checking instrumentation_clone flag for chain source and target.
2259 Going through instrumentation thunks we always have it changed
2260 from 0 to 1 and all other nodes do not change it. */
2261 if (!cs->callee->instrumentation_clone
2262 && callee->instrumentation_clone)
2264 for (i = 0; i < parms_count; i++)
2265 ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info,
2266 i));
2267 return ret;
2270 /* If this call goes through a thunk we must not propagate to the first (0th)
2271 parameter. However, we might need to uncover a thunk from below a series
2272 of aliases first. */
2273 if (call_passes_through_thunk_p (cs))
2275 ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info,
2276 0));
2277 i = 1;
2279 else
2280 i = 0;
2282 for (; (i < args_count) && (i < parms_count); i++)
2284 struct ipa_jump_func *jump_func = ipa_get_ith_jump_func (args, i);
2285 struct ipcp_param_lattices *dest_plats;
2286 tree param_type = ipa_get_type (callee_info, i);
2288 dest_plats = ipa_get_parm_lattices (callee_info, i);
2289 if (availability == AVAIL_INTERPOSABLE)
2290 ret |= set_all_contains_variable (dest_plats);
2291 else
2293 ret |= propagate_scalar_across_jump_function (cs, jump_func,
2294 &dest_plats->itself,
2295 param_type);
2296 ret |= propagate_context_across_jump_function (cs, jump_func, i,
2297 &dest_plats->ctxlat);
2299 |= propagate_bits_across_jump_function (cs, i, jump_func,
2300 &dest_plats->bits_lattice);
2301 ret |= propagate_aggs_across_jump_function (cs, jump_func,
2302 dest_plats);
2303 if (opt_for_fn (callee->decl, flag_ipa_vrp))
2304 ret |= propagate_vr_across_jump_function (cs, jump_func,
2305 dest_plats, param_type);
2306 else
2307 ret |= dest_plats->m_value_range.set_to_bottom ();
2310 for (; i < parms_count; i++)
2311 ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info, i));
2313 return ret;
2316 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
2317 KNOWN_CONTEXTS, KNOWN_AGGS or AGG_REPS return the destination. The latter
2318 three can be NULL. If AGG_REPS is not NULL, KNOWN_AGGS is ignored. */
2320 static tree
2321 ipa_get_indirect_edge_target_1 (struct cgraph_edge *ie,
2322 vec<tree> known_csts,
2323 vec<ipa_polymorphic_call_context> known_contexts,
2324 vec<ipa_agg_jump_function_p> known_aggs,
2325 struct ipa_agg_replacement_value *agg_reps,
2326 bool *speculative)
2328 int param_index = ie->indirect_info->param_index;
2329 HOST_WIDE_INT anc_offset;
2330 tree t;
2331 tree target = NULL;
2333 *speculative = false;
2335 if (param_index == -1
2336 || known_csts.length () <= (unsigned int) param_index)
2337 return NULL_TREE;
2339 if (!ie->indirect_info->polymorphic)
2341 tree t;
2343 if (ie->indirect_info->agg_contents)
2345 t = NULL;
2346 if (agg_reps && ie->indirect_info->guaranteed_unmodified)
2348 while (agg_reps)
2350 if (agg_reps->index == param_index
2351 && agg_reps->offset == ie->indirect_info->offset
2352 && agg_reps->by_ref == ie->indirect_info->by_ref)
2354 t = agg_reps->value;
2355 break;
2357 agg_reps = agg_reps->next;
2360 if (!t)
2362 struct ipa_agg_jump_function *agg;
2363 if (known_aggs.length () > (unsigned int) param_index)
2364 agg = known_aggs[param_index];
2365 else
2366 agg = NULL;
2367 bool from_global_constant;
2368 t = ipa_find_agg_cst_for_param (agg, known_csts[param_index],
2369 ie->indirect_info->offset,
2370 ie->indirect_info->by_ref,
2371 &from_global_constant);
2372 if (t
2373 && !from_global_constant
2374 && !ie->indirect_info->guaranteed_unmodified)
2375 t = NULL_TREE;
2378 else
2379 t = known_csts[param_index];
2381 if (t
2382 && TREE_CODE (t) == ADDR_EXPR
2383 && TREE_CODE (TREE_OPERAND (t, 0)) == FUNCTION_DECL)
2384 return TREE_OPERAND (t, 0);
2385 else
2386 return NULL_TREE;
2389 if (!opt_for_fn (ie->caller->decl, flag_devirtualize))
2390 return NULL_TREE;
2392 gcc_assert (!ie->indirect_info->agg_contents);
2393 anc_offset = ie->indirect_info->offset;
2395 t = NULL;
2397 /* Try to work out value of virtual table pointer value in replacemnets. */
2398 if (!t && agg_reps && !ie->indirect_info->by_ref)
2400 while (agg_reps)
2402 if (agg_reps->index == param_index
2403 && agg_reps->offset == ie->indirect_info->offset
2404 && agg_reps->by_ref)
2406 t = agg_reps->value;
2407 break;
2409 agg_reps = agg_reps->next;
2413 /* Try to work out value of virtual table pointer value in known
2414 aggregate values. */
2415 if (!t && known_aggs.length () > (unsigned int) param_index
2416 && !ie->indirect_info->by_ref)
2418 struct ipa_agg_jump_function *agg;
2419 agg = known_aggs[param_index];
2420 t = ipa_find_agg_cst_for_param (agg, known_csts[param_index],
2421 ie->indirect_info->offset, true);
2424 /* If we found the virtual table pointer, lookup the target. */
2425 if (t)
2427 tree vtable;
2428 unsigned HOST_WIDE_INT offset;
2429 if (vtable_pointer_value_to_vtable (t, &vtable, &offset))
2431 bool can_refer;
2432 target = gimple_get_virt_method_for_vtable (ie->indirect_info->otr_token,
2433 vtable, offset, &can_refer);
2434 if (can_refer)
2436 if (!target
2437 || (TREE_CODE (TREE_TYPE (target)) == FUNCTION_TYPE
2438 && DECL_FUNCTION_CODE (target) == BUILT_IN_UNREACHABLE)
2439 || !possible_polymorphic_call_target_p
2440 (ie, cgraph_node::get (target)))
2442 /* Do not speculate builtin_unreachable, it is stupid! */
2443 if (ie->indirect_info->vptr_changed)
2444 return NULL;
2445 target = ipa_impossible_devirt_target (ie, target);
2447 *speculative = ie->indirect_info->vptr_changed;
2448 if (!*speculative)
2449 return target;
2454 /* Do we know the constant value of pointer? */
2455 if (!t)
2456 t = known_csts[param_index];
2458 gcc_checking_assert (!t || TREE_CODE (t) != TREE_BINFO);
2460 ipa_polymorphic_call_context context;
2461 if (known_contexts.length () > (unsigned int) param_index)
2463 context = known_contexts[param_index];
2464 context.offset_by (anc_offset);
2465 if (ie->indirect_info->vptr_changed)
2466 context.possible_dynamic_type_change (ie->in_polymorphic_cdtor,
2467 ie->indirect_info->otr_type);
2468 if (t)
2470 ipa_polymorphic_call_context ctx2 = ipa_polymorphic_call_context
2471 (t, ie->indirect_info->otr_type, anc_offset);
2472 if (!ctx2.useless_p ())
2473 context.combine_with (ctx2, ie->indirect_info->otr_type);
2476 else if (t)
2478 context = ipa_polymorphic_call_context (t, ie->indirect_info->otr_type,
2479 anc_offset);
2480 if (ie->indirect_info->vptr_changed)
2481 context.possible_dynamic_type_change (ie->in_polymorphic_cdtor,
2482 ie->indirect_info->otr_type);
2484 else
2485 return NULL_TREE;
2487 vec <cgraph_node *>targets;
2488 bool final;
2490 targets = possible_polymorphic_call_targets
2491 (ie->indirect_info->otr_type,
2492 ie->indirect_info->otr_token,
2493 context, &final);
2494 if (!final || targets.length () > 1)
2496 struct cgraph_node *node;
2497 if (*speculative)
2498 return target;
2499 if (!opt_for_fn (ie->caller->decl, flag_devirtualize_speculatively)
2500 || ie->speculative || !ie->maybe_hot_p ())
2501 return NULL;
2502 node = try_speculative_devirtualization (ie->indirect_info->otr_type,
2503 ie->indirect_info->otr_token,
2504 context);
2505 if (node)
2507 *speculative = true;
2508 target = node->decl;
2510 else
2511 return NULL;
2513 else
2515 *speculative = false;
2516 if (targets.length () == 1)
2517 target = targets[0]->decl;
2518 else
2519 target = ipa_impossible_devirt_target (ie, NULL_TREE);
2522 if (target && !possible_polymorphic_call_target_p (ie,
2523 cgraph_node::get (target)))
2525 if (*speculative)
2526 return NULL;
2527 target = ipa_impossible_devirt_target (ie, target);
2530 return target;
2534 /* If an indirect edge IE can be turned into a direct one based on KNOWN_CSTS,
2535 KNOWN_CONTEXTS (which can be vNULL) or KNOWN_AGGS (which also can be vNULL)
2536 return the destination. */
2538 tree
2539 ipa_get_indirect_edge_target (struct cgraph_edge *ie,
2540 vec<tree> known_csts,
2541 vec<ipa_polymorphic_call_context> known_contexts,
2542 vec<ipa_agg_jump_function_p> known_aggs,
2543 bool *speculative)
2545 return ipa_get_indirect_edge_target_1 (ie, known_csts, known_contexts,
2546 known_aggs, NULL, speculative);
2549 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
2550 and KNOWN_CONTEXTS. */
2552 static int
2553 devirtualization_time_bonus (struct cgraph_node *node,
2554 vec<tree> known_csts,
2555 vec<ipa_polymorphic_call_context> known_contexts,
2556 vec<ipa_agg_jump_function_p> known_aggs)
2558 struct cgraph_edge *ie;
2559 int res = 0;
2561 for (ie = node->indirect_calls; ie; ie = ie->next_callee)
2563 struct cgraph_node *callee;
2564 struct ipa_fn_summary *isummary;
2565 enum availability avail;
2566 tree target;
2567 bool speculative;
2569 target = ipa_get_indirect_edge_target (ie, known_csts, known_contexts,
2570 known_aggs, &speculative);
2571 if (!target)
2572 continue;
2574 /* Only bare minimum benefit for clearly un-inlineable targets. */
2575 res += 1;
2576 callee = cgraph_node::get (target);
2577 if (!callee || !callee->definition)
2578 continue;
2579 callee = callee->function_symbol (&avail);
2580 if (avail < AVAIL_AVAILABLE)
2581 continue;
2582 isummary = ipa_fn_summaries->get (callee);
2583 if (!isummary->inlinable)
2584 continue;
2586 /* FIXME: The values below need re-considering and perhaps also
2587 integrating into the cost metrics, at lest in some very basic way. */
2588 if (isummary->size <= MAX_INLINE_INSNS_AUTO / 4)
2589 res += 31 / ((int)speculative + 1);
2590 else if (isummary->size <= MAX_INLINE_INSNS_AUTO / 2)
2591 res += 15 / ((int)speculative + 1);
2592 else if (isummary->size <= MAX_INLINE_INSNS_AUTO
2593 || DECL_DECLARED_INLINE_P (callee->decl))
2594 res += 7 / ((int)speculative + 1);
2597 return res;
2600 /* Return time bonus incurred because of HINTS. */
2602 static int
2603 hint_time_bonus (ipa_hints hints)
2605 int result = 0;
2606 if (hints & (INLINE_HINT_loop_iterations | INLINE_HINT_loop_stride))
2607 result += PARAM_VALUE (PARAM_IPA_CP_LOOP_HINT_BONUS);
2608 if (hints & INLINE_HINT_array_index)
2609 result += PARAM_VALUE (PARAM_IPA_CP_ARRAY_INDEX_HINT_BONUS);
2610 return result;
2613 /* If there is a reason to penalize the function described by INFO in the
2614 cloning goodness evaluation, do so. */
2616 static inline int64_t
2617 incorporate_penalties (ipa_node_params *info, int64_t evaluation)
2619 if (info->node_within_scc)
2620 evaluation = (evaluation
2621 * (100 - PARAM_VALUE (PARAM_IPA_CP_RECURSION_PENALTY))) / 100;
2623 if (info->node_calling_single_call)
2624 evaluation = (evaluation
2625 * (100 - PARAM_VALUE (PARAM_IPA_CP_SINGLE_CALL_PENALTY)))
2626 / 100;
2628 return evaluation;
2631 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
2632 and SIZE_COST and with the sum of frequencies of incoming edges to the
2633 potential new clone in FREQUENCIES. */
2635 static bool
2636 good_cloning_opportunity_p (struct cgraph_node *node, int time_benefit,
2637 int freq_sum, profile_count count_sum, int size_cost)
2639 if (time_benefit == 0
2640 || !opt_for_fn (node->decl, flag_ipa_cp_clone)
2641 || node->optimize_for_size_p ())
2642 return false;
2644 gcc_assert (size_cost > 0);
2646 struct ipa_node_params *info = IPA_NODE_REF (node);
2647 if (max_count > profile_count::zero ())
2649 int factor = RDIV (count_sum.probability_in
2650 (max_count).to_reg_br_prob_base ()
2651 * 1000, REG_BR_PROB_BASE);
2652 int64_t evaluation = (((int64_t) time_benefit * factor)
2653 / size_cost);
2654 evaluation = incorporate_penalties (info, evaluation);
2656 if (dump_file && (dump_flags & TDF_DETAILS))
2658 fprintf (dump_file, " good_cloning_opportunity_p (time: %i, "
2659 "size: %i, count_sum: ", time_benefit, size_cost);
2660 count_sum.dump (dump_file);
2661 fprintf (dump_file, "%s%s) -> evaluation: " "%" PRId64
2662 ", threshold: %i\n",
2663 info->node_within_scc ? ", scc" : "",
2664 info->node_calling_single_call ? ", single_call" : "",
2665 evaluation, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD));
2668 return evaluation >= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD);
2670 else
2672 int64_t evaluation = (((int64_t) time_benefit * freq_sum)
2673 / size_cost);
2674 evaluation = incorporate_penalties (info, evaluation);
2676 if (dump_file && (dump_flags & TDF_DETAILS))
2677 fprintf (dump_file, " good_cloning_opportunity_p (time: %i, "
2678 "size: %i, freq_sum: %i%s%s) -> evaluation: "
2679 "%" PRId64 ", threshold: %i\n",
2680 time_benefit, size_cost, freq_sum,
2681 info->node_within_scc ? ", scc" : "",
2682 info->node_calling_single_call ? ", single_call" : "",
2683 evaluation, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD));
2685 return evaluation >= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD);
2689 /* Return all context independent values from aggregate lattices in PLATS in a
2690 vector. Return NULL if there are none. */
2692 static vec<ipa_agg_jf_item, va_gc> *
2693 context_independent_aggregate_values (struct ipcp_param_lattices *plats)
2695 vec<ipa_agg_jf_item, va_gc> *res = NULL;
2697 if (plats->aggs_bottom
2698 || plats->aggs_contain_variable
2699 || plats->aggs_count == 0)
2700 return NULL;
2702 for (struct ipcp_agg_lattice *aglat = plats->aggs;
2703 aglat;
2704 aglat = aglat->next)
2705 if (aglat->is_single_const ())
2707 struct ipa_agg_jf_item item;
2708 item.offset = aglat->offset;
2709 item.value = aglat->values->value;
2710 vec_safe_push (res, item);
2712 return res;
2715 /* Allocate KNOWN_CSTS, KNOWN_CONTEXTS and, if non-NULL, KNOWN_AGGS and
2716 populate them with values of parameters that are known independent of the
2717 context. INFO describes the function. If REMOVABLE_PARAMS_COST is
2718 non-NULL, the movement cost of all removable parameters will be stored in
2719 it. */
2721 static bool
2722 gather_context_independent_values (struct ipa_node_params *info,
2723 vec<tree> *known_csts,
2724 vec<ipa_polymorphic_call_context>
2725 *known_contexts,
2726 vec<ipa_agg_jump_function> *known_aggs,
2727 int *removable_params_cost)
2729 int i, count = ipa_get_param_count (info);
2730 bool ret = false;
2732 known_csts->create (0);
2733 known_contexts->create (0);
2734 known_csts->safe_grow_cleared (count);
2735 known_contexts->safe_grow_cleared (count);
2736 if (known_aggs)
2738 known_aggs->create (0);
2739 known_aggs->safe_grow_cleared (count);
2742 if (removable_params_cost)
2743 *removable_params_cost = 0;
2745 for (i = 0; i < count; i++)
2747 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
2748 ipcp_lattice<tree> *lat = &plats->itself;
2750 if (lat->is_single_const ())
2752 ipcp_value<tree> *val = lat->values;
2753 gcc_checking_assert (TREE_CODE (val->value) != TREE_BINFO);
2754 (*known_csts)[i] = val->value;
2755 if (removable_params_cost)
2756 *removable_params_cost
2757 += estimate_move_cost (TREE_TYPE (val->value), false);
2758 ret = true;
2760 else if (removable_params_cost
2761 && !ipa_is_param_used (info, i))
2762 *removable_params_cost
2763 += ipa_get_param_move_cost (info, i);
2765 if (!ipa_is_param_used (info, i))
2766 continue;
2768 ipcp_lattice<ipa_polymorphic_call_context> *ctxlat = &plats->ctxlat;
2769 /* Do not account known context as reason for cloning. We can see
2770 if it permits devirtualization. */
2771 if (ctxlat->is_single_const ())
2772 (*known_contexts)[i] = ctxlat->values->value;
2774 if (known_aggs)
2776 vec<ipa_agg_jf_item, va_gc> *agg_items;
2777 struct ipa_agg_jump_function *ajf;
2779 agg_items = context_independent_aggregate_values (plats);
2780 ajf = &(*known_aggs)[i];
2781 ajf->items = agg_items;
2782 ajf->by_ref = plats->aggs_by_ref;
2783 ret |= agg_items != NULL;
2787 return ret;
2790 /* The current interface in ipa-inline-analysis requires a pointer vector.
2791 Create it.
2793 FIXME: That interface should be re-worked, this is slightly silly. Still,
2794 I'd like to discuss how to change it first and this demonstrates the
2795 issue. */
2797 static vec<ipa_agg_jump_function_p>
2798 agg_jmp_p_vec_for_t_vec (vec<ipa_agg_jump_function> known_aggs)
2800 vec<ipa_agg_jump_function_p> ret;
2801 struct ipa_agg_jump_function *ajf;
2802 int i;
2804 ret.create (known_aggs.length ());
2805 FOR_EACH_VEC_ELT (known_aggs, i, ajf)
2806 ret.quick_push (ajf);
2807 return ret;
2810 /* Perform time and size measurement of NODE with the context given in
2811 KNOWN_CSTS, KNOWN_CONTEXTS and KNOWN_AGGS, calculate the benefit and cost
2812 given BASE_TIME of the node without specialization, REMOVABLE_PARAMS_COST of
2813 all context-independent removable parameters and EST_MOVE_COST of estimated
2814 movement of the considered parameter and store it into VAL. */
2816 static void
2817 perform_estimation_of_a_value (cgraph_node *node, vec<tree> known_csts,
2818 vec<ipa_polymorphic_call_context> known_contexts,
2819 vec<ipa_agg_jump_function_p> known_aggs_ptrs,
2820 int removable_params_cost,
2821 int est_move_cost, ipcp_value_base *val)
2823 int size, time_benefit;
2824 sreal time, base_time;
2825 ipa_hints hints;
2827 estimate_ipcp_clone_size_and_time (node, known_csts, known_contexts,
2828 known_aggs_ptrs, &size, &time,
2829 &base_time, &hints);
2830 base_time -= time;
2831 if (base_time > 65535)
2832 base_time = 65535;
2833 time_benefit = base_time.to_int ()
2834 + devirtualization_time_bonus (node, known_csts, known_contexts,
2835 known_aggs_ptrs)
2836 + hint_time_bonus (hints)
2837 + removable_params_cost + est_move_cost;
2839 gcc_checking_assert (size >=0);
2840 /* The inliner-heuristics based estimates may think that in certain
2841 contexts some functions do not have any size at all but we want
2842 all specializations to have at least a tiny cost, not least not to
2843 divide by zero. */
2844 if (size == 0)
2845 size = 1;
2847 val->local_time_benefit = time_benefit;
2848 val->local_size_cost = size;
2851 /* Iterate over known values of parameters of NODE and estimate the local
2852 effects in terms of time and size they have. */
2854 static void
2855 estimate_local_effects (struct cgraph_node *node)
2857 struct ipa_node_params *info = IPA_NODE_REF (node);
2858 int i, count = ipa_get_param_count (info);
2859 vec<tree> known_csts;
2860 vec<ipa_polymorphic_call_context> known_contexts;
2861 vec<ipa_agg_jump_function> known_aggs;
2862 vec<ipa_agg_jump_function_p> known_aggs_ptrs;
2863 bool always_const;
2864 int removable_params_cost;
2866 if (!count || !ipcp_versionable_function_p (node))
2867 return;
2869 if (dump_file && (dump_flags & TDF_DETAILS))
2870 fprintf (dump_file, "\nEstimating effects for %s.\n", node->dump_name ());
2872 always_const = gather_context_independent_values (info, &known_csts,
2873 &known_contexts, &known_aggs,
2874 &removable_params_cost);
2875 known_aggs_ptrs = agg_jmp_p_vec_for_t_vec (known_aggs);
2876 int devirt_bonus = devirtualization_time_bonus (node, known_csts,
2877 known_contexts, known_aggs_ptrs);
2878 if (always_const || devirt_bonus
2879 || (removable_params_cost && node->local.can_change_signature))
2881 struct caller_statistics stats;
2882 ipa_hints hints;
2883 sreal time, base_time;
2884 int size;
2886 init_caller_stats (&stats);
2887 node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats,
2888 false);
2889 estimate_ipcp_clone_size_and_time (node, known_csts, known_contexts,
2890 known_aggs_ptrs, &size, &time,
2891 &base_time, &hints);
2892 time -= devirt_bonus;
2893 time -= hint_time_bonus (hints);
2894 time -= removable_params_cost;
2895 size -= stats.n_calls * removable_params_cost;
2897 if (dump_file)
2898 fprintf (dump_file, " - context independent values, size: %i, "
2899 "time_benefit: %f\n", size, (base_time - time).to_double ());
2901 if (size <= 0 || node->local.local)
2903 info->do_clone_for_all_contexts = true;
2905 if (dump_file)
2906 fprintf (dump_file, " Decided to specialize for all "
2907 "known contexts, code not going to grow.\n");
2909 else if (good_cloning_opportunity_p (node,
2910 MAX ((base_time - time).to_int (),
2911 65536),
2912 stats.freq_sum, stats.count_sum,
2913 size))
2915 if (size + overall_size <= max_new_size)
2917 info->do_clone_for_all_contexts = true;
2918 overall_size += size;
2920 if (dump_file)
2921 fprintf (dump_file, " Decided to specialize for all "
2922 "known contexts, growth deemed beneficial.\n");
2924 else if (dump_file && (dump_flags & TDF_DETAILS))
2925 fprintf (dump_file, " Not cloning for all contexts because "
2926 "max_new_size would be reached with %li.\n",
2927 size + overall_size);
2929 else if (dump_file && (dump_flags & TDF_DETAILS))
2930 fprintf (dump_file, " Not cloning for all contexts because "
2931 "!good_cloning_opportunity_p.\n");
2935 for (i = 0; i < count; i++)
2937 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
2938 ipcp_lattice<tree> *lat = &plats->itself;
2939 ipcp_value<tree> *val;
2941 if (lat->bottom
2942 || !lat->values
2943 || known_csts[i])
2944 continue;
2946 for (val = lat->values; val; val = val->next)
2948 gcc_checking_assert (TREE_CODE (val->value) != TREE_BINFO);
2949 known_csts[i] = val->value;
2951 int emc = estimate_move_cost (TREE_TYPE (val->value), true);
2952 perform_estimation_of_a_value (node, known_csts, known_contexts,
2953 known_aggs_ptrs,
2954 removable_params_cost, emc, val);
2956 if (dump_file && (dump_flags & TDF_DETAILS))
2958 fprintf (dump_file, " - estimates for value ");
2959 print_ipcp_constant_value (dump_file, val->value);
2960 fprintf (dump_file, " for ");
2961 ipa_dump_param (dump_file, info, i);
2962 fprintf (dump_file, ": time_benefit: %i, size: %i\n",
2963 val->local_time_benefit, val->local_size_cost);
2966 known_csts[i] = NULL_TREE;
2969 for (i = 0; i < count; i++)
2971 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
2973 if (!plats->virt_call)
2974 continue;
2976 ipcp_lattice<ipa_polymorphic_call_context> *ctxlat = &plats->ctxlat;
2977 ipcp_value<ipa_polymorphic_call_context> *val;
2979 if (ctxlat->bottom
2980 || !ctxlat->values
2981 || !known_contexts[i].useless_p ())
2982 continue;
2984 for (val = ctxlat->values; val; val = val->next)
2986 known_contexts[i] = val->value;
2987 perform_estimation_of_a_value (node, known_csts, known_contexts,
2988 known_aggs_ptrs,
2989 removable_params_cost, 0, val);
2991 if (dump_file && (dump_flags & TDF_DETAILS))
2993 fprintf (dump_file, " - estimates for polymorphic context ");
2994 print_ipcp_constant_value (dump_file, val->value);
2995 fprintf (dump_file, " for ");
2996 ipa_dump_param (dump_file, info, i);
2997 fprintf (dump_file, ": time_benefit: %i, size: %i\n",
2998 val->local_time_benefit, val->local_size_cost);
3001 known_contexts[i] = ipa_polymorphic_call_context ();
3004 for (i = 0; i < count; i++)
3006 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
3007 struct ipa_agg_jump_function *ajf;
3008 struct ipcp_agg_lattice *aglat;
3010 if (plats->aggs_bottom || !plats->aggs)
3011 continue;
3013 ajf = &known_aggs[i];
3014 for (aglat = plats->aggs; aglat; aglat = aglat->next)
3016 ipcp_value<tree> *val;
3017 if (aglat->bottom || !aglat->values
3018 /* If the following is true, the one value is in known_aggs. */
3019 || (!plats->aggs_contain_variable
3020 && aglat->is_single_const ()))
3021 continue;
3023 for (val = aglat->values; val; val = val->next)
3025 struct ipa_agg_jf_item item;
3027 item.offset = aglat->offset;
3028 item.value = val->value;
3029 vec_safe_push (ajf->items, item);
3031 perform_estimation_of_a_value (node, known_csts, known_contexts,
3032 known_aggs_ptrs,
3033 removable_params_cost, 0, val);
3035 if (dump_file && (dump_flags & TDF_DETAILS))
3037 fprintf (dump_file, " - estimates for value ");
3038 print_ipcp_constant_value (dump_file, val->value);
3039 fprintf (dump_file, " for ");
3040 ipa_dump_param (dump_file, info, i);
3041 fprintf (dump_file, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
3042 "]: time_benefit: %i, size: %i\n",
3043 plats->aggs_by_ref ? "ref " : "",
3044 aglat->offset,
3045 val->local_time_benefit, val->local_size_cost);
3048 ajf->items->pop ();
3053 for (i = 0; i < count; i++)
3054 vec_free (known_aggs[i].items);
3056 known_csts.release ();
3057 known_contexts.release ();
3058 known_aggs.release ();
3059 known_aggs_ptrs.release ();
3063 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
3064 topological sort of values. */
3066 template <typename valtype>
3067 void
3068 value_topo_info<valtype>::add_val (ipcp_value<valtype> *cur_val)
3070 ipcp_value_source<valtype> *src;
3072 if (cur_val->dfs)
3073 return;
3075 dfs_counter++;
3076 cur_val->dfs = dfs_counter;
3077 cur_val->low_link = dfs_counter;
3079 cur_val->topo_next = stack;
3080 stack = cur_val;
3081 cur_val->on_stack = true;
3083 for (src = cur_val->sources; src; src = src->next)
3084 if (src->val)
3086 if (src->val->dfs == 0)
3088 add_val (src->val);
3089 if (src->val->low_link < cur_val->low_link)
3090 cur_val->low_link = src->val->low_link;
3092 else if (src->val->on_stack
3093 && src->val->dfs < cur_val->low_link)
3094 cur_val->low_link = src->val->dfs;
3097 if (cur_val->dfs == cur_val->low_link)
3099 ipcp_value<valtype> *v, *scc_list = NULL;
3103 v = stack;
3104 stack = v->topo_next;
3105 v->on_stack = false;
3107 v->scc_next = scc_list;
3108 scc_list = v;
3110 while (v != cur_val);
3112 cur_val->topo_next = values_topo;
3113 values_topo = cur_val;
3117 /* Add all values in lattices associated with NODE to the topological sort if
3118 they are not there yet. */
3120 static void
3121 add_all_node_vals_to_toposort (cgraph_node *node, ipa_topo_info *topo)
3123 struct ipa_node_params *info = IPA_NODE_REF (node);
3124 int i, count = ipa_get_param_count (info);
3126 for (i = 0; i < count; i++)
3128 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
3129 ipcp_lattice<tree> *lat = &plats->itself;
3130 struct ipcp_agg_lattice *aglat;
3132 if (!lat->bottom)
3134 ipcp_value<tree> *val;
3135 for (val = lat->values; val; val = val->next)
3136 topo->constants.add_val (val);
3139 if (!plats->aggs_bottom)
3140 for (aglat = plats->aggs; aglat; aglat = aglat->next)
3141 if (!aglat->bottom)
3143 ipcp_value<tree> *val;
3144 for (val = aglat->values; val; val = val->next)
3145 topo->constants.add_val (val);
3148 ipcp_lattice<ipa_polymorphic_call_context> *ctxlat = &plats->ctxlat;
3149 if (!ctxlat->bottom)
3151 ipcp_value<ipa_polymorphic_call_context> *ctxval;
3152 for (ctxval = ctxlat->values; ctxval; ctxval = ctxval->next)
3153 topo->contexts.add_val (ctxval);
3158 /* One pass of constants propagation along the call graph edges, from callers
3159 to callees (requires topological ordering in TOPO), iterate over strongly
3160 connected components. */
3162 static void
3163 propagate_constants_topo (struct ipa_topo_info *topo)
3165 int i;
3167 for (i = topo->nnodes - 1; i >= 0; i--)
3169 unsigned j;
3170 struct cgraph_node *v, *node = topo->order[i];
3171 vec<cgraph_node *> cycle_nodes = ipa_get_nodes_in_cycle (node);
3173 /* First, iteratively propagate within the strongly connected component
3174 until all lattices stabilize. */
3175 FOR_EACH_VEC_ELT (cycle_nodes, j, v)
3176 if (v->has_gimple_body_p ())
3177 push_node_to_stack (topo, v);
3179 v = pop_node_from_stack (topo);
3180 while (v)
3182 struct cgraph_edge *cs;
3184 for (cs = v->callees; cs; cs = cs->next_callee)
3185 if (ipa_edge_within_scc (cs))
3187 IPA_NODE_REF (v)->node_within_scc = true;
3188 if (propagate_constants_across_call (cs))
3189 push_node_to_stack (topo, cs->callee->function_symbol ());
3191 v = pop_node_from_stack (topo);
3194 /* Afterwards, propagate along edges leading out of the SCC, calculates
3195 the local effects of the discovered constants and all valid values to
3196 their topological sort. */
3197 FOR_EACH_VEC_ELT (cycle_nodes, j, v)
3198 if (v->has_gimple_body_p ())
3200 struct cgraph_edge *cs;
3202 estimate_local_effects (v);
3203 add_all_node_vals_to_toposort (v, topo);
3204 for (cs = v->callees; cs; cs = cs->next_callee)
3205 if (!ipa_edge_within_scc (cs))
3206 propagate_constants_across_call (cs);
3208 cycle_nodes.release ();
3213 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
3214 the bigger one if otherwise. */
3216 static int
3217 safe_add (int a, int b)
3219 if (a > INT_MAX/2 || b > INT_MAX/2)
3220 return a > b ? a : b;
3221 else
3222 return a + b;
3226 /* Propagate the estimated effects of individual values along the topological
3227 from the dependent values to those they depend on. */
3229 template <typename valtype>
3230 void
3231 value_topo_info<valtype>::propagate_effects ()
3233 ipcp_value<valtype> *base;
3235 for (base = values_topo; base; base = base->topo_next)
3237 ipcp_value_source<valtype> *src;
3238 ipcp_value<valtype> *val;
3239 int time = 0, size = 0;
3241 for (val = base; val; val = val->scc_next)
3243 time = safe_add (time,
3244 val->local_time_benefit + val->prop_time_benefit);
3245 size = safe_add (size, val->local_size_cost + val->prop_size_cost);
3248 for (val = base; val; val = val->scc_next)
3249 for (src = val->sources; src; src = src->next)
3250 if (src->val
3251 && src->cs->maybe_hot_p ())
3253 src->val->prop_time_benefit = safe_add (time,
3254 src->val->prop_time_benefit);
3255 src->val->prop_size_cost = safe_add (size,
3256 src->val->prop_size_cost);
3262 /* Propagate constants, polymorphic contexts and their effects from the
3263 summaries interprocedurally. */
3265 static void
3266 ipcp_propagate_stage (struct ipa_topo_info *topo)
3268 struct cgraph_node *node;
3270 if (dump_file)
3271 fprintf (dump_file, "\n Propagating constants:\n\n");
3273 max_count = profile_count::uninitialized ();
3275 FOR_EACH_DEFINED_FUNCTION (node)
3277 struct ipa_node_params *info = IPA_NODE_REF (node);
3279 determine_versionability (node, info);
3280 if (node->has_gimple_body_p ())
3282 info->lattices = XCNEWVEC (struct ipcp_param_lattices,
3283 ipa_get_param_count (info));
3284 initialize_node_lattices (node);
3286 if (node->definition && !node->alias)
3287 overall_size += ipa_fn_summaries->get (node)->self_size;
3288 max_count = max_count.max (node->count.ipa ());
3291 max_new_size = overall_size;
3292 if (max_new_size < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
3293 max_new_size = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
3294 max_new_size += max_new_size * PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH) / 100 + 1;
3296 if (dump_file)
3297 fprintf (dump_file, "\noverall_size: %li, max_new_size: %li\n",
3298 overall_size, max_new_size);
3300 propagate_constants_topo (topo);
3301 if (flag_checking)
3302 ipcp_verify_propagated_values ();
3303 topo->constants.propagate_effects ();
3304 topo->contexts.propagate_effects ();
3306 if (dump_file)
3308 fprintf (dump_file, "\nIPA lattices after all propagation:\n");
3309 print_all_lattices (dump_file, (dump_flags & TDF_DETAILS), true);
3313 /* Discover newly direct outgoing edges from NODE which is a new clone with
3314 known KNOWN_CSTS and make them direct. */
3316 static void
3317 ipcp_discover_new_direct_edges (struct cgraph_node *node,
3318 vec<tree> known_csts,
3319 vec<ipa_polymorphic_call_context>
3320 known_contexts,
3321 struct ipa_agg_replacement_value *aggvals)
3323 struct cgraph_edge *ie, *next_ie;
3324 bool found = false;
3326 for (ie = node->indirect_calls; ie; ie = next_ie)
3328 tree target;
3329 bool speculative;
3331 next_ie = ie->next_callee;
3332 target = ipa_get_indirect_edge_target_1 (ie, known_csts, known_contexts,
3333 vNULL, aggvals, &speculative);
3334 if (target)
3336 bool agg_contents = ie->indirect_info->agg_contents;
3337 bool polymorphic = ie->indirect_info->polymorphic;
3338 int param_index = ie->indirect_info->param_index;
3339 struct cgraph_edge *cs = ipa_make_edge_direct_to_target (ie, target,
3340 speculative);
3341 found = true;
3343 if (cs && !agg_contents && !polymorphic)
3345 struct ipa_node_params *info = IPA_NODE_REF (node);
3346 int c = ipa_get_controlled_uses (info, param_index);
3347 if (c != IPA_UNDESCRIBED_USE)
3349 struct ipa_ref *to_del;
3351 c--;
3352 ipa_set_controlled_uses (info, param_index, c);
3353 if (dump_file && (dump_flags & TDF_DETAILS))
3354 fprintf (dump_file, " controlled uses count of param "
3355 "%i bumped down to %i\n", param_index, c);
3356 if (c == 0
3357 && (to_del = node->find_reference (cs->callee, NULL, 0)))
3359 if (dump_file && (dump_flags & TDF_DETAILS))
3360 fprintf (dump_file, " and even removing its "
3361 "cloning-created reference\n");
3362 to_del->remove_reference ();
3368 /* Turning calls to direct calls will improve overall summary. */
3369 if (found)
3370 ipa_update_overall_fn_summary (node);
3373 /* Vector of pointers which for linked lists of clones of an original crgaph
3374 edge. */
3376 static vec<cgraph_edge *> next_edge_clone;
3377 static vec<cgraph_edge *> prev_edge_clone;
3379 static inline void
3380 grow_edge_clone_vectors (void)
3382 if (next_edge_clone.length ()
3383 <= (unsigned) symtab->edges_max_uid)
3384 next_edge_clone.safe_grow_cleared (symtab->edges_max_uid + 1);
3385 if (prev_edge_clone.length ()
3386 <= (unsigned) symtab->edges_max_uid)
3387 prev_edge_clone.safe_grow_cleared (symtab->edges_max_uid + 1);
3390 /* Edge duplication hook to grow the appropriate linked list in
3391 next_edge_clone. */
3393 static void
3394 ipcp_edge_duplication_hook (struct cgraph_edge *src, struct cgraph_edge *dst,
3395 void *)
3397 grow_edge_clone_vectors ();
3399 struct cgraph_edge *old_next = next_edge_clone[src->uid];
3400 if (old_next)
3401 prev_edge_clone[old_next->uid] = dst;
3402 prev_edge_clone[dst->uid] = src;
3404 next_edge_clone[dst->uid] = old_next;
3405 next_edge_clone[src->uid] = dst;
3408 /* Hook that is called by cgraph.c when an edge is removed. */
3410 static void
3411 ipcp_edge_removal_hook (struct cgraph_edge *cs, void *)
3413 grow_edge_clone_vectors ();
3415 struct cgraph_edge *prev = prev_edge_clone[cs->uid];
3416 struct cgraph_edge *next = next_edge_clone[cs->uid];
3417 if (prev)
3418 next_edge_clone[prev->uid] = next;
3419 if (next)
3420 prev_edge_clone[next->uid] = prev;
3423 /* See if NODE is a clone with a known aggregate value at a given OFFSET of a
3424 parameter with the given INDEX. */
3426 static tree
3427 get_clone_agg_value (struct cgraph_node *node, HOST_WIDE_INT offset,
3428 int index)
3430 struct ipa_agg_replacement_value *aggval;
3432 aggval = ipa_get_agg_replacements_for_node (node);
3433 while (aggval)
3435 if (aggval->offset == offset
3436 && aggval->index == index)
3437 return aggval->value;
3438 aggval = aggval->next;
3440 return NULL_TREE;
3443 /* Return true is NODE is DEST or its clone for all contexts. */
3445 static bool
3446 same_node_or_its_all_contexts_clone_p (cgraph_node *node, cgraph_node *dest)
3448 if (node == dest)
3449 return true;
3451 struct ipa_node_params *info = IPA_NODE_REF (node);
3452 return info->is_all_contexts_clone && info->ipcp_orig_node == dest;
3455 /* Return true if edge CS does bring about the value described by SRC to node
3456 DEST or its clone for all contexts. */
3458 static bool
3459 cgraph_edge_brings_value_p (cgraph_edge *cs, ipcp_value_source<tree> *src,
3460 cgraph_node *dest)
3462 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
3463 enum availability availability;
3464 cgraph_node *real_dest = cs->callee->function_symbol (&availability);
3466 if (!same_node_or_its_all_contexts_clone_p (real_dest, dest)
3467 || availability <= AVAIL_INTERPOSABLE
3468 || caller_info->node_dead)
3469 return false;
3470 if (!src->val)
3471 return true;
3473 if (caller_info->ipcp_orig_node)
3475 tree t;
3476 if (src->offset == -1)
3477 t = caller_info->known_csts[src->index];
3478 else
3479 t = get_clone_agg_value (cs->caller, src->offset, src->index);
3480 return (t != NULL_TREE
3481 && values_equal_for_ipcp_p (src->val->value, t));
3483 else
3485 struct ipcp_agg_lattice *aglat;
3486 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (caller_info,
3487 src->index);
3488 if (src->offset == -1)
3489 return (plats->itself.is_single_const ()
3490 && values_equal_for_ipcp_p (src->val->value,
3491 plats->itself.values->value));
3492 else
3494 if (plats->aggs_bottom || plats->aggs_contain_variable)
3495 return false;
3496 for (aglat = plats->aggs; aglat; aglat = aglat->next)
3497 if (aglat->offset == src->offset)
3498 return (aglat->is_single_const ()
3499 && values_equal_for_ipcp_p (src->val->value,
3500 aglat->values->value));
3502 return false;
3506 /* Return true if edge CS does bring about the value described by SRC to node
3507 DEST or its clone for all contexts. */
3509 static bool
3510 cgraph_edge_brings_value_p (cgraph_edge *cs,
3511 ipcp_value_source<ipa_polymorphic_call_context> *src,
3512 cgraph_node *dest)
3514 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
3515 cgraph_node *real_dest = cs->callee->function_symbol ();
3517 if (!same_node_or_its_all_contexts_clone_p (real_dest, dest)
3518 || caller_info->node_dead)
3519 return false;
3520 if (!src->val)
3521 return true;
3523 if (caller_info->ipcp_orig_node)
3524 return (caller_info->known_contexts.length () > (unsigned) src->index)
3525 && values_equal_for_ipcp_p (src->val->value,
3526 caller_info->known_contexts[src->index]);
3528 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (caller_info,
3529 src->index);
3530 return plats->ctxlat.is_single_const ()
3531 && values_equal_for_ipcp_p (src->val->value,
3532 plats->ctxlat.values->value);
3535 /* Get the next clone in the linked list of clones of an edge. */
3537 static inline struct cgraph_edge *
3538 get_next_cgraph_edge_clone (struct cgraph_edge *cs)
3540 return next_edge_clone[cs->uid];
3543 /* Given VAL that is intended for DEST, iterate over all its sources and if
3544 they still hold, add their edge frequency and their number into *FREQUENCY
3545 and *CALLER_COUNT respectively. */
3547 template <typename valtype>
3548 static bool
3549 get_info_about_necessary_edges (ipcp_value<valtype> *val, cgraph_node *dest,
3550 int *freq_sum,
3551 profile_count *count_sum, int *caller_count)
3553 ipcp_value_source<valtype> *src;
3554 int freq = 0, count = 0;
3555 profile_count cnt = profile_count::zero ();
3556 bool hot = false;
3558 for (src = val->sources; src; src = src->next)
3560 struct cgraph_edge *cs = src->cs;
3561 while (cs)
3563 if (cgraph_edge_brings_value_p (cs, src, dest))
3565 count++;
3566 freq += cs->frequency ();
3567 if (cs->count.ipa ().initialized_p ())
3568 cnt += cs->count.ipa ();
3569 hot |= cs->maybe_hot_p ();
3571 cs = get_next_cgraph_edge_clone (cs);
3575 *freq_sum = freq;
3576 *count_sum = cnt;
3577 *caller_count = count;
3578 return hot;
3581 /* Return a vector of incoming edges that do bring value VAL to node DEST. It
3582 is assumed their number is known and equal to CALLER_COUNT. */
3584 template <typename valtype>
3585 static vec<cgraph_edge *>
3586 gather_edges_for_value (ipcp_value<valtype> *val, cgraph_node *dest,
3587 int caller_count)
3589 ipcp_value_source<valtype> *src;
3590 vec<cgraph_edge *> ret;
3592 ret.create (caller_count);
3593 for (src = val->sources; src; src = src->next)
3595 struct cgraph_edge *cs = src->cs;
3596 while (cs)
3598 if (cgraph_edge_brings_value_p (cs, src, dest))
3599 ret.quick_push (cs);
3600 cs = get_next_cgraph_edge_clone (cs);
3604 return ret;
3607 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
3608 Return it or NULL if for some reason it cannot be created. */
3610 static struct ipa_replace_map *
3611 get_replacement_map (struct ipa_node_params *info, tree value, int parm_num)
3613 struct ipa_replace_map *replace_map;
3616 replace_map = ggc_alloc<ipa_replace_map> ();
3617 if (dump_file)
3619 fprintf (dump_file, " replacing ");
3620 ipa_dump_param (dump_file, info, parm_num);
3622 fprintf (dump_file, " with const ");
3623 print_generic_expr (dump_file, value);
3624 fprintf (dump_file, "\n");
3626 replace_map->old_tree = NULL;
3627 replace_map->parm_num = parm_num;
3628 replace_map->new_tree = value;
3629 replace_map->replace_p = true;
3630 replace_map->ref_p = false;
3632 return replace_map;
3635 /* Dump new profiling counts */
3637 static void
3638 dump_profile_updates (struct cgraph_node *orig_node,
3639 struct cgraph_node *new_node)
3641 struct cgraph_edge *cs;
3643 fprintf (dump_file, " setting count of the specialized node to ");
3644 new_node->count.dump (dump_file);
3645 fprintf (dump_file, "\n");
3646 for (cs = new_node->callees; cs; cs = cs->next_callee)
3648 fprintf (dump_file, " edge to %s has count ",
3649 cs->callee->name ());
3650 cs->count.dump (dump_file);
3651 fprintf (dump_file, "\n");
3654 fprintf (dump_file, " setting count of the original node to ");
3655 orig_node->count.dump (dump_file);
3656 fprintf (dump_file, "\n");
3657 for (cs = orig_node->callees; cs; cs = cs->next_callee)
3659 fprintf (dump_file, " edge to %s is left with ",
3660 cs->callee->name ());
3661 cs->count.dump (dump_file);
3662 fprintf (dump_file, "\n");
3666 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
3667 their profile information to reflect this. */
3669 static void
3670 update_profiling_info (struct cgraph_node *orig_node,
3671 struct cgraph_node *new_node)
3673 struct cgraph_edge *cs;
3674 struct caller_statistics stats;
3675 profile_count new_sum, orig_sum;
3676 profile_count remainder, orig_node_count = orig_node->count;
3678 if (!(orig_node_count.ipa () > profile_count::zero ()))
3679 return;
3681 init_caller_stats (&stats);
3682 orig_node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats,
3683 false);
3684 orig_sum = stats.count_sum;
3685 init_caller_stats (&stats);
3686 new_node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats,
3687 false);
3688 new_sum = stats.count_sum;
3690 if (orig_node_count < orig_sum + new_sum)
3692 if (dump_file)
3694 fprintf (dump_file, " Problem: node %s has too low count ",
3695 orig_node->dump_name ());
3696 orig_node_count.dump (dump_file);
3697 fprintf (dump_file, "while the sum of incoming count is ");
3698 (orig_sum + new_sum).dump (dump_file);
3699 fprintf (dump_file, "\n");
3702 orig_node_count = (orig_sum + new_sum).apply_scale (12, 10);
3703 if (dump_file)
3705 fprintf (dump_file, " proceeding by pretending it was ");
3706 orig_node_count.dump (dump_file);
3707 fprintf (dump_file, "\n");
3711 remainder = orig_node_count.combine_with_ipa_count (orig_node_count.ipa ()
3712 - new_sum.ipa ());
3713 new_sum = orig_node_count.combine_with_ipa_count (new_sum);
3714 orig_node->count = remainder;
3716 for (cs = new_node->callees; cs; cs = cs->next_callee)
3717 cs->count = cs->count.apply_scale (new_sum, orig_node_count);
3719 for (cs = orig_node->callees; cs; cs = cs->next_callee)
3720 cs->count = cs->count.apply_scale (remainder, orig_node_count);
3722 if (dump_file)
3723 dump_profile_updates (orig_node, new_node);
3726 /* Update the respective profile of specialized NEW_NODE and the original
3727 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
3728 have been redirected to the specialized version. */
3730 static void
3731 update_specialized_profile (struct cgraph_node *new_node,
3732 struct cgraph_node *orig_node,
3733 profile_count redirected_sum)
3735 struct cgraph_edge *cs;
3736 profile_count new_node_count, orig_node_count = orig_node->count;
3738 if (dump_file)
3740 fprintf (dump_file, " the sum of counts of redirected edges is ");
3741 redirected_sum.dump (dump_file);
3742 fprintf (dump_file, "\n");
3744 if (!(orig_node_count > profile_count::zero ()))
3745 return;
3747 gcc_assert (orig_node_count >= redirected_sum);
3749 new_node_count = new_node->count;
3750 new_node->count += redirected_sum;
3751 orig_node->count -= redirected_sum;
3753 for (cs = new_node->callees; cs; cs = cs->next_callee)
3754 if (cs->frequency ())
3755 cs->count += cs->count.apply_scale (redirected_sum, new_node_count);
3756 else
3757 cs->count = profile_count::zero ();
3759 for (cs = orig_node->callees; cs; cs = cs->next_callee)
3761 profile_count dec = cs->count.apply_scale (redirected_sum,
3762 orig_node_count);
3763 cs->count -= dec;
3766 if (dump_file)
3767 dump_profile_updates (orig_node, new_node);
3770 /* Create a specialized version of NODE with known constants in KNOWN_CSTS,
3771 known contexts in KNOWN_CONTEXTS and known aggregate values in AGGVALS and
3772 redirect all edges in CALLERS to it. */
3774 static struct cgraph_node *
3775 create_specialized_node (struct cgraph_node *node,
3776 vec<tree> known_csts,
3777 vec<ipa_polymorphic_call_context> known_contexts,
3778 struct ipa_agg_replacement_value *aggvals,
3779 vec<cgraph_edge *> callers)
3781 struct ipa_node_params *new_info, *info = IPA_NODE_REF (node);
3782 vec<ipa_replace_map *, va_gc> *replace_trees = NULL;
3783 struct ipa_agg_replacement_value *av;
3784 struct cgraph_node *new_node;
3785 int i, count = ipa_get_param_count (info);
3786 bitmap args_to_skip;
3788 gcc_assert (!info->ipcp_orig_node);
3790 if (node->local.can_change_signature)
3792 args_to_skip = BITMAP_GGC_ALLOC ();
3793 for (i = 0; i < count; i++)
3795 tree t = known_csts[i];
3797 if (t || !ipa_is_param_used (info, i))
3798 bitmap_set_bit (args_to_skip, i);
3801 else
3803 args_to_skip = NULL;
3804 if (dump_file && (dump_flags & TDF_DETAILS))
3805 fprintf (dump_file, " cannot change function signature\n");
3808 for (i = 0; i < count; i++)
3810 tree t = known_csts[i];
3811 if (t)
3813 struct ipa_replace_map *replace_map;
3815 gcc_checking_assert (TREE_CODE (t) != TREE_BINFO);
3816 replace_map = get_replacement_map (info, t, i);
3817 if (replace_map)
3818 vec_safe_push (replace_trees, replace_map);
3822 new_node = node->create_virtual_clone (callers, replace_trees,
3823 args_to_skip, "constprop");
3824 ipa_set_node_agg_value_chain (new_node, aggvals);
3825 for (av = aggvals; av; av = av->next)
3826 new_node->maybe_create_reference (av->value, NULL);
3828 if (dump_file && (dump_flags & TDF_DETAILS))
3830 fprintf (dump_file, " the new node is %s.\n", new_node->dump_name ());
3831 if (known_contexts.exists ())
3833 for (i = 0; i < count; i++)
3834 if (!known_contexts[i].useless_p ())
3836 fprintf (dump_file, " known ctx %i is ", i);
3837 known_contexts[i].dump (dump_file);
3840 if (aggvals)
3841 ipa_dump_agg_replacement_values (dump_file, aggvals);
3843 ipa_check_create_node_params ();
3844 update_profiling_info (node, new_node);
3845 new_info = IPA_NODE_REF (new_node);
3846 new_info->ipcp_orig_node = node;
3847 new_info->known_csts = known_csts;
3848 new_info->known_contexts = known_contexts;
3850 ipcp_discover_new_direct_edges (new_node, known_csts, known_contexts, aggvals);
3852 callers.release ();
3853 return new_node;
3856 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
3857 KNOWN_CSTS with constants that are also known for all of the CALLERS. */
3859 static void
3860 find_more_scalar_values_for_callers_subset (struct cgraph_node *node,
3861 vec<tree> known_csts,
3862 vec<cgraph_edge *> callers)
3864 struct ipa_node_params *info = IPA_NODE_REF (node);
3865 int i, count = ipa_get_param_count (info);
3867 for (i = 0; i < count; i++)
3869 struct cgraph_edge *cs;
3870 tree newval = NULL_TREE;
3871 int j;
3872 bool first = true;
3873 tree type = ipa_get_type (info, i);
3875 if (ipa_get_scalar_lat (info, i)->bottom || known_csts[i])
3876 continue;
3878 FOR_EACH_VEC_ELT (callers, j, cs)
3880 struct ipa_jump_func *jump_func;
3881 tree t;
3883 if (i >= ipa_get_cs_argument_count (IPA_EDGE_REF (cs))
3884 || (i == 0
3885 && call_passes_through_thunk_p (cs))
3886 || (!cs->callee->instrumentation_clone
3887 && cs->callee->function_symbol ()->instrumentation_clone))
3889 newval = NULL_TREE;
3890 break;
3892 jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
3893 t = ipa_value_from_jfunc (IPA_NODE_REF (cs->caller), jump_func, type);
3894 if (!t
3895 || (newval
3896 && !values_equal_for_ipcp_p (t, newval))
3897 || (!first && !newval))
3899 newval = NULL_TREE;
3900 break;
3902 else
3903 newval = t;
3904 first = false;
3907 if (newval)
3909 if (dump_file && (dump_flags & TDF_DETAILS))
3911 fprintf (dump_file, " adding an extra known scalar value ");
3912 print_ipcp_constant_value (dump_file, newval);
3913 fprintf (dump_file, " for ");
3914 ipa_dump_param (dump_file, info, i);
3915 fprintf (dump_file, "\n");
3918 known_csts[i] = newval;
3923 /* Given a NODE and a subset of its CALLERS, try to populate plank slots in
3924 KNOWN_CONTEXTS with polymorphic contexts that are also known for all of the
3925 CALLERS. */
3927 static void
3928 find_more_contexts_for_caller_subset (cgraph_node *node,
3929 vec<ipa_polymorphic_call_context>
3930 *known_contexts,
3931 vec<cgraph_edge *> callers)
3933 ipa_node_params *info = IPA_NODE_REF (node);
3934 int i, count = ipa_get_param_count (info);
3936 for (i = 0; i < count; i++)
3938 cgraph_edge *cs;
3940 if (ipa_get_poly_ctx_lat (info, i)->bottom
3941 || (known_contexts->exists ()
3942 && !(*known_contexts)[i].useless_p ()))
3943 continue;
3945 ipa_polymorphic_call_context newval;
3946 bool first = true;
3947 int j;
3949 FOR_EACH_VEC_ELT (callers, j, cs)
3951 if (i >= ipa_get_cs_argument_count (IPA_EDGE_REF (cs)))
3952 return;
3953 ipa_jump_func *jfunc = ipa_get_ith_jump_func (IPA_EDGE_REF (cs),
3955 ipa_polymorphic_call_context ctx;
3956 ctx = ipa_context_from_jfunc (IPA_NODE_REF (cs->caller), cs, i,
3957 jfunc);
3958 if (first)
3960 newval = ctx;
3961 first = false;
3963 else
3964 newval.meet_with (ctx);
3965 if (newval.useless_p ())
3966 break;
3969 if (!newval.useless_p ())
3971 if (dump_file && (dump_flags & TDF_DETAILS))
3973 fprintf (dump_file, " adding an extra known polymorphic "
3974 "context ");
3975 print_ipcp_constant_value (dump_file, newval);
3976 fprintf (dump_file, " for ");
3977 ipa_dump_param (dump_file, info, i);
3978 fprintf (dump_file, "\n");
3981 if (!known_contexts->exists ())
3982 known_contexts->safe_grow_cleared (ipa_get_param_count (info));
3983 (*known_contexts)[i] = newval;
3989 /* Go through PLATS and create a vector of values consisting of values and
3990 offsets (minus OFFSET) of lattices that contain only a single value. */
3992 static vec<ipa_agg_jf_item>
3993 copy_plats_to_inter (struct ipcp_param_lattices *plats, HOST_WIDE_INT offset)
3995 vec<ipa_agg_jf_item> res = vNULL;
3997 if (!plats->aggs || plats->aggs_contain_variable || plats->aggs_bottom)
3998 return vNULL;
4000 for (struct ipcp_agg_lattice *aglat = plats->aggs; aglat; aglat = aglat->next)
4001 if (aglat->is_single_const ())
4003 struct ipa_agg_jf_item ti;
4004 ti.offset = aglat->offset - offset;
4005 ti.value = aglat->values->value;
4006 res.safe_push (ti);
4008 return res;
4011 /* Intersect all values in INTER with single value lattices in PLATS (while
4012 subtracting OFFSET). */
4014 static void
4015 intersect_with_plats (struct ipcp_param_lattices *plats,
4016 vec<ipa_agg_jf_item> *inter,
4017 HOST_WIDE_INT offset)
4019 struct ipcp_agg_lattice *aglat;
4020 struct ipa_agg_jf_item *item;
4021 int k;
4023 if (!plats->aggs || plats->aggs_contain_variable || plats->aggs_bottom)
4025 inter->release ();
4026 return;
4029 aglat = plats->aggs;
4030 FOR_EACH_VEC_ELT (*inter, k, item)
4032 bool found = false;
4033 if (!item->value)
4034 continue;
4035 while (aglat)
4037 if (aglat->offset - offset > item->offset)
4038 break;
4039 if (aglat->offset - offset == item->offset)
4041 gcc_checking_assert (item->value);
4042 if (values_equal_for_ipcp_p (item->value, aglat->values->value))
4043 found = true;
4044 break;
4046 aglat = aglat->next;
4048 if (!found)
4049 item->value = NULL_TREE;
4053 /* Copy aggregate replacement values of NODE (which is an IPA-CP clone) to the
4054 vector result while subtracting OFFSET from the individual value offsets. */
4056 static vec<ipa_agg_jf_item>
4057 agg_replacements_to_vector (struct cgraph_node *node, int index,
4058 HOST_WIDE_INT offset)
4060 struct ipa_agg_replacement_value *av;
4061 vec<ipa_agg_jf_item> res = vNULL;
4063 for (av = ipa_get_agg_replacements_for_node (node); av; av = av->next)
4064 if (av->index == index
4065 && (av->offset - offset) >= 0)
4067 struct ipa_agg_jf_item item;
4068 gcc_checking_assert (av->value);
4069 item.offset = av->offset - offset;
4070 item.value = av->value;
4071 res.safe_push (item);
4074 return res;
4077 /* Intersect all values in INTER with those that we have already scheduled to
4078 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
4079 (while subtracting OFFSET). */
4081 static void
4082 intersect_with_agg_replacements (struct cgraph_node *node, int index,
4083 vec<ipa_agg_jf_item> *inter,
4084 HOST_WIDE_INT offset)
4086 struct ipa_agg_replacement_value *srcvals;
4087 struct ipa_agg_jf_item *item;
4088 int i;
4090 srcvals = ipa_get_agg_replacements_for_node (node);
4091 if (!srcvals)
4093 inter->release ();
4094 return;
4097 FOR_EACH_VEC_ELT (*inter, i, item)
4099 struct ipa_agg_replacement_value *av;
4100 bool found = false;
4101 if (!item->value)
4102 continue;
4103 for (av = srcvals; av; av = av->next)
4105 gcc_checking_assert (av->value);
4106 if (av->index == index
4107 && av->offset - offset == item->offset)
4109 if (values_equal_for_ipcp_p (item->value, av->value))
4110 found = true;
4111 break;
4114 if (!found)
4115 item->value = NULL_TREE;
4119 /* Intersect values in INTER with aggregate values that come along edge CS to
4120 parameter number INDEX and return it. If INTER does not actually exist yet,
4121 copy all incoming values to it. If we determine we ended up with no values
4122 whatsoever, return a released vector. */
4124 static vec<ipa_agg_jf_item>
4125 intersect_aggregates_with_edge (struct cgraph_edge *cs, int index,
4126 vec<ipa_agg_jf_item> inter)
4128 struct ipa_jump_func *jfunc;
4129 jfunc = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), index);
4130 if (jfunc->type == IPA_JF_PASS_THROUGH
4131 && ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
4133 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
4134 int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
4136 if (caller_info->ipcp_orig_node)
4138 struct cgraph_node *orig_node = caller_info->ipcp_orig_node;
4139 struct ipcp_param_lattices *orig_plats;
4140 orig_plats = ipa_get_parm_lattices (IPA_NODE_REF (orig_node),
4141 src_idx);
4142 if (agg_pass_through_permissible_p (orig_plats, jfunc))
4144 if (!inter.exists ())
4145 inter = agg_replacements_to_vector (cs->caller, src_idx, 0);
4146 else
4147 intersect_with_agg_replacements (cs->caller, src_idx,
4148 &inter, 0);
4150 else
4152 inter.release ();
4153 return vNULL;
4156 else
4158 struct ipcp_param_lattices *src_plats;
4159 src_plats = ipa_get_parm_lattices (caller_info, src_idx);
4160 if (agg_pass_through_permissible_p (src_plats, jfunc))
4162 /* Currently we do not produce clobber aggregate jump
4163 functions, adjust when we do. */
4164 gcc_checking_assert (!jfunc->agg.items);
4165 if (!inter.exists ())
4166 inter = copy_plats_to_inter (src_plats, 0);
4167 else
4168 intersect_with_plats (src_plats, &inter, 0);
4170 else
4172 inter.release ();
4173 return vNULL;
4177 else if (jfunc->type == IPA_JF_ANCESTOR
4178 && ipa_get_jf_ancestor_agg_preserved (jfunc))
4180 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
4181 int src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
4182 struct ipcp_param_lattices *src_plats;
4183 HOST_WIDE_INT delta = ipa_get_jf_ancestor_offset (jfunc);
4185 if (caller_info->ipcp_orig_node)
4187 if (!inter.exists ())
4188 inter = agg_replacements_to_vector (cs->caller, src_idx, delta);
4189 else
4190 intersect_with_agg_replacements (cs->caller, src_idx, &inter,
4191 delta);
4193 else
4195 src_plats = ipa_get_parm_lattices (caller_info, src_idx);
4196 /* Currently we do not produce clobber aggregate jump
4197 functions, adjust when we do. */
4198 gcc_checking_assert (!src_plats->aggs || !jfunc->agg.items);
4199 if (!inter.exists ())
4200 inter = copy_plats_to_inter (src_plats, delta);
4201 else
4202 intersect_with_plats (src_plats, &inter, delta);
4205 else if (jfunc->agg.items)
4207 struct ipa_agg_jf_item *item;
4208 int k;
4210 if (!inter.exists ())
4211 for (unsigned i = 0; i < jfunc->agg.items->length (); i++)
4212 inter.safe_push ((*jfunc->agg.items)[i]);
4213 else
4214 FOR_EACH_VEC_ELT (inter, k, item)
4216 int l = 0;
4217 bool found = false;
4219 if (!item->value)
4220 continue;
4222 while ((unsigned) l < jfunc->agg.items->length ())
4224 struct ipa_agg_jf_item *ti;
4225 ti = &(*jfunc->agg.items)[l];
4226 if (ti->offset > item->offset)
4227 break;
4228 if (ti->offset == item->offset)
4230 gcc_checking_assert (ti->value);
4231 if (values_equal_for_ipcp_p (item->value,
4232 ti->value))
4233 found = true;
4234 break;
4236 l++;
4238 if (!found)
4239 item->value = NULL;
4242 else
4244 inter.release ();
4245 return vec<ipa_agg_jf_item>();
4247 return inter;
4250 /* Look at edges in CALLERS and collect all known aggregate values that arrive
4251 from all of them. */
4253 static struct ipa_agg_replacement_value *
4254 find_aggregate_values_for_callers_subset (struct cgraph_node *node,
4255 vec<cgraph_edge *> callers)
4257 struct ipa_node_params *dest_info = IPA_NODE_REF (node);
4258 struct ipa_agg_replacement_value *res;
4259 struct ipa_agg_replacement_value **tail = &res;
4260 struct cgraph_edge *cs;
4261 int i, j, count = ipa_get_param_count (dest_info);
4263 FOR_EACH_VEC_ELT (callers, j, cs)
4265 int c = ipa_get_cs_argument_count (IPA_EDGE_REF (cs));
4266 if (c < count)
4267 count = c;
4270 for (i = 0; i < count; i++)
4272 struct cgraph_edge *cs;
4273 vec<ipa_agg_jf_item> inter = vNULL;
4274 struct ipa_agg_jf_item *item;
4275 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (dest_info, i);
4276 int j;
4278 /* Among other things, the following check should deal with all by_ref
4279 mismatches. */
4280 if (plats->aggs_bottom)
4281 continue;
4283 FOR_EACH_VEC_ELT (callers, j, cs)
4285 inter = intersect_aggregates_with_edge (cs, i, inter);
4287 if (!inter.exists ())
4288 goto next_param;
4291 FOR_EACH_VEC_ELT (inter, j, item)
4293 struct ipa_agg_replacement_value *v;
4295 if (!item->value)
4296 continue;
4298 v = ggc_alloc<ipa_agg_replacement_value> ();
4299 v->index = i;
4300 v->offset = item->offset;
4301 v->value = item->value;
4302 v->by_ref = plats->aggs_by_ref;
4303 *tail = v;
4304 tail = &v->next;
4307 next_param:
4308 if (inter.exists ())
4309 inter.release ();
4311 *tail = NULL;
4312 return res;
4315 /* Turn KNOWN_AGGS into a list of aggregate replacement values. */
4317 static struct ipa_agg_replacement_value *
4318 known_aggs_to_agg_replacement_list (vec<ipa_agg_jump_function> known_aggs)
4320 struct ipa_agg_replacement_value *res;
4321 struct ipa_agg_replacement_value **tail = &res;
4322 struct ipa_agg_jump_function *aggjf;
4323 struct ipa_agg_jf_item *item;
4324 int i, j;
4326 FOR_EACH_VEC_ELT (known_aggs, i, aggjf)
4327 FOR_EACH_VEC_SAFE_ELT (aggjf->items, j, item)
4329 struct ipa_agg_replacement_value *v;
4330 v = ggc_alloc<ipa_agg_replacement_value> ();
4331 v->index = i;
4332 v->offset = item->offset;
4333 v->value = item->value;
4334 v->by_ref = aggjf->by_ref;
4335 *tail = v;
4336 tail = &v->next;
4338 *tail = NULL;
4339 return res;
4342 /* Determine whether CS also brings all scalar values that the NODE is
4343 specialized for. */
4345 static bool
4346 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge *cs,
4347 struct cgraph_node *node)
4349 struct ipa_node_params *dest_info = IPA_NODE_REF (node);
4350 int count = ipa_get_param_count (dest_info);
4351 struct ipa_node_params *caller_info;
4352 struct ipa_edge_args *args;
4353 int i;
4355 caller_info = IPA_NODE_REF (cs->caller);
4356 args = IPA_EDGE_REF (cs);
4357 for (i = 0; i < count; i++)
4359 struct ipa_jump_func *jump_func;
4360 tree val, t;
4362 val = dest_info->known_csts[i];
4363 if (!val)
4364 continue;
4366 if (i >= ipa_get_cs_argument_count (args))
4367 return false;
4368 jump_func = ipa_get_ith_jump_func (args, i);
4369 t = ipa_value_from_jfunc (caller_info, jump_func,
4370 ipa_get_type (dest_info, i));
4371 if (!t || !values_equal_for_ipcp_p (val, t))
4372 return false;
4374 return true;
4377 /* Determine whether CS also brings all aggregate values that NODE is
4378 specialized for. */
4379 static bool
4380 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge *cs,
4381 struct cgraph_node *node)
4383 struct ipa_node_params *orig_caller_info = IPA_NODE_REF (cs->caller);
4384 struct ipa_node_params *orig_node_info;
4385 struct ipa_agg_replacement_value *aggval;
4386 int i, ec, count;
4388 aggval = ipa_get_agg_replacements_for_node (node);
4389 if (!aggval)
4390 return true;
4392 count = ipa_get_param_count (IPA_NODE_REF (node));
4393 ec = ipa_get_cs_argument_count (IPA_EDGE_REF (cs));
4394 if (ec < count)
4395 for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next)
4396 if (aggval->index >= ec)
4397 return false;
4399 orig_node_info = IPA_NODE_REF (IPA_NODE_REF (node)->ipcp_orig_node);
4400 if (orig_caller_info->ipcp_orig_node)
4401 orig_caller_info = IPA_NODE_REF (orig_caller_info->ipcp_orig_node);
4403 for (i = 0; i < count; i++)
4405 static vec<ipa_agg_jf_item> values = vec<ipa_agg_jf_item>();
4406 struct ipcp_param_lattices *plats;
4407 bool interesting = false;
4408 for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next)
4409 if (aggval->index == i)
4411 interesting = true;
4412 break;
4414 if (!interesting)
4415 continue;
4417 plats = ipa_get_parm_lattices (orig_node_info, aggval->index);
4418 if (plats->aggs_bottom)
4419 return false;
4421 values = intersect_aggregates_with_edge (cs, i, values);
4422 if (!values.exists ())
4423 return false;
4425 for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next)
4426 if (aggval->index == i)
4428 struct ipa_agg_jf_item *item;
4429 int j;
4430 bool found = false;
4431 FOR_EACH_VEC_ELT (values, j, item)
4432 if (item->value
4433 && item->offset == av->offset
4434 && values_equal_for_ipcp_p (item->value, av->value))
4436 found = true;
4437 break;
4439 if (!found)
4441 values.release ();
4442 return false;
4446 return true;
4449 /* Given an original NODE and a VAL for which we have already created a
4450 specialized clone, look whether there are incoming edges that still lead
4451 into the old node but now also bring the requested value and also conform to
4452 all other criteria such that they can be redirected the special node.
4453 This function can therefore redirect the final edge in a SCC. */
4455 template <typename valtype>
4456 static void
4457 perhaps_add_new_callers (cgraph_node *node, ipcp_value<valtype> *val)
4459 ipcp_value_source<valtype> *src;
4460 profile_count redirected_sum = profile_count::zero ();
4462 for (src = val->sources; src; src = src->next)
4464 struct cgraph_edge *cs = src->cs;
4465 while (cs)
4467 if (cgraph_edge_brings_value_p (cs, src, node)
4468 && cgraph_edge_brings_all_scalars_for_node (cs, val->spec_node)
4469 && cgraph_edge_brings_all_agg_vals_for_node (cs, val->spec_node))
4471 if (dump_file)
4472 fprintf (dump_file, " - adding an extra caller %s of %s\n",
4473 cs->caller->dump_name (),
4474 val->spec_node->dump_name ());
4476 cs->redirect_callee_duplicating_thunks (val->spec_node);
4477 val->spec_node->expand_all_artificial_thunks ();
4478 if (cs->count.ipa ().initialized_p ())
4479 redirected_sum = redirected_sum + cs->count.ipa ();
4481 cs = get_next_cgraph_edge_clone (cs);
4485 if (redirected_sum > profile_count::zero ())
4486 update_specialized_profile (val->spec_node, node, redirected_sum);
4489 /* Return true if KNOWN_CONTEXTS contain at least one useful context. */
4491 static bool
4492 known_contexts_useful_p (vec<ipa_polymorphic_call_context> known_contexts)
4494 ipa_polymorphic_call_context *ctx;
4495 int i;
4497 FOR_EACH_VEC_ELT (known_contexts, i, ctx)
4498 if (!ctx->useless_p ())
4499 return true;
4500 return false;
4503 /* Return a copy of KNOWN_CSTS if it is not empty, otherwise return vNULL. */
4505 static vec<ipa_polymorphic_call_context>
4506 copy_useful_known_contexts (vec<ipa_polymorphic_call_context> known_contexts)
4508 if (known_contexts_useful_p (known_contexts))
4509 return known_contexts.copy ();
4510 else
4511 return vNULL;
4514 /* Copy KNOWN_CSTS and modify the copy according to VAL and INDEX. If
4515 non-empty, replace KNOWN_CONTEXTS with its copy too. */
4517 static void
4518 modify_known_vectors_with_val (vec<tree> *known_csts,
4519 vec<ipa_polymorphic_call_context> *known_contexts,
4520 ipcp_value<tree> *val,
4521 int index)
4523 *known_csts = known_csts->copy ();
4524 *known_contexts = copy_useful_known_contexts (*known_contexts);
4525 (*known_csts)[index] = val->value;
4528 /* Replace KNOWN_CSTS with its copy. Also copy KNOWN_CONTEXTS and modify the
4529 copy according to VAL and INDEX. */
4531 static void
4532 modify_known_vectors_with_val (vec<tree> *known_csts,
4533 vec<ipa_polymorphic_call_context> *known_contexts,
4534 ipcp_value<ipa_polymorphic_call_context> *val,
4535 int index)
4537 *known_csts = known_csts->copy ();
4538 *known_contexts = known_contexts->copy ();
4539 (*known_contexts)[index] = val->value;
4542 /* Return true if OFFSET indicates this was not an aggregate value or there is
4543 a replacement equivalent to VALUE, INDEX and OFFSET among those in the
4544 AGGVALS list. */
4546 DEBUG_FUNCTION bool
4547 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value *aggvals,
4548 int index, HOST_WIDE_INT offset, tree value)
4550 if (offset == -1)
4551 return true;
4553 while (aggvals)
4555 if (aggvals->index == index
4556 && aggvals->offset == offset
4557 && values_equal_for_ipcp_p (aggvals->value, value))
4558 return true;
4559 aggvals = aggvals->next;
4561 return false;
4564 /* Return true if offset is minus one because source of a polymorphic contect
4565 cannot be an aggregate value. */
4567 DEBUG_FUNCTION bool
4568 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value *,
4569 int , HOST_WIDE_INT offset,
4570 ipa_polymorphic_call_context)
4572 return offset == -1;
4575 /* Decide wheter to create a special version of NODE for value VAL of parameter
4576 at the given INDEX. If OFFSET is -1, the value is for the parameter itself,
4577 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS,
4578 KNOWN_CONTEXTS and KNOWN_AGGS describe the other already known values. */
4580 template <typename valtype>
4581 static bool
4582 decide_about_value (struct cgraph_node *node, int index, HOST_WIDE_INT offset,
4583 ipcp_value<valtype> *val, vec<tree> known_csts,
4584 vec<ipa_polymorphic_call_context> known_contexts)
4586 struct ipa_agg_replacement_value *aggvals;
4587 int freq_sum, caller_count;
4588 profile_count count_sum;
4589 vec<cgraph_edge *> callers;
4591 if (val->spec_node)
4593 perhaps_add_new_callers (node, val);
4594 return false;
4596 else if (val->local_size_cost + overall_size > max_new_size)
4598 if (dump_file && (dump_flags & TDF_DETAILS))
4599 fprintf (dump_file, " Ignoring candidate value because "
4600 "max_new_size would be reached with %li.\n",
4601 val->local_size_cost + overall_size);
4602 return false;
4604 else if (!get_info_about_necessary_edges (val, node, &freq_sum, &count_sum,
4605 &caller_count))
4606 return false;
4608 if (dump_file && (dump_flags & TDF_DETAILS))
4610 fprintf (dump_file, " - considering value ");
4611 print_ipcp_constant_value (dump_file, val->value);
4612 fprintf (dump_file, " for ");
4613 ipa_dump_param (dump_file, IPA_NODE_REF (node), index);
4614 if (offset != -1)
4615 fprintf (dump_file, ", offset: " HOST_WIDE_INT_PRINT_DEC, offset);
4616 fprintf (dump_file, " (caller_count: %i)\n", caller_count);
4619 if (!good_cloning_opportunity_p (node, val->local_time_benefit,
4620 freq_sum, count_sum,
4621 val->local_size_cost)
4622 && !good_cloning_opportunity_p (node,
4623 val->local_time_benefit
4624 + val->prop_time_benefit,
4625 freq_sum, count_sum,
4626 val->local_size_cost
4627 + val->prop_size_cost))
4628 return false;
4630 if (dump_file)
4631 fprintf (dump_file, " Creating a specialized node of %s.\n",
4632 node->dump_name ());
4634 callers = gather_edges_for_value (val, node, caller_count);
4635 if (offset == -1)
4636 modify_known_vectors_with_val (&known_csts, &known_contexts, val, index);
4637 else
4639 known_csts = known_csts.copy ();
4640 known_contexts = copy_useful_known_contexts (known_contexts);
4642 find_more_scalar_values_for_callers_subset (node, known_csts, callers);
4643 find_more_contexts_for_caller_subset (node, &known_contexts, callers);
4644 aggvals = find_aggregate_values_for_callers_subset (node, callers);
4645 gcc_checking_assert (ipcp_val_agg_replacement_ok_p (aggvals, index,
4646 offset, val->value));
4647 val->spec_node = create_specialized_node (node, known_csts, known_contexts,
4648 aggvals, callers);
4649 overall_size += val->local_size_cost;
4651 /* TODO: If for some lattice there is only one other known value
4652 left, make a special node for it too. */
4654 return true;
4657 /* Decide whether and what specialized clones of NODE should be created. */
4659 static bool
4660 decide_whether_version_node (struct cgraph_node *node)
4662 struct ipa_node_params *info = IPA_NODE_REF (node);
4663 int i, count = ipa_get_param_count (info);
4664 vec<tree> known_csts;
4665 vec<ipa_polymorphic_call_context> known_contexts;
4666 vec<ipa_agg_jump_function> known_aggs = vNULL;
4667 bool ret = false;
4669 if (count == 0)
4670 return false;
4672 if (dump_file && (dump_flags & TDF_DETAILS))
4673 fprintf (dump_file, "\nEvaluating opportunities for %s.\n",
4674 node->dump_name ());
4676 gather_context_independent_values (info, &known_csts, &known_contexts,
4677 info->do_clone_for_all_contexts ? &known_aggs
4678 : NULL, NULL);
4680 for (i = 0; i < count;i++)
4682 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
4683 ipcp_lattice<tree> *lat = &plats->itself;
4684 ipcp_lattice<ipa_polymorphic_call_context> *ctxlat = &plats->ctxlat;
4686 if (!lat->bottom
4687 && !known_csts[i])
4689 ipcp_value<tree> *val;
4690 for (val = lat->values; val; val = val->next)
4691 ret |= decide_about_value (node, i, -1, val, known_csts,
4692 known_contexts);
4695 if (!plats->aggs_bottom)
4697 struct ipcp_agg_lattice *aglat;
4698 ipcp_value<tree> *val;
4699 for (aglat = plats->aggs; aglat; aglat = aglat->next)
4700 if (!aglat->bottom && aglat->values
4701 /* If the following is false, the one value is in
4702 known_aggs. */
4703 && (plats->aggs_contain_variable
4704 || !aglat->is_single_const ()))
4705 for (val = aglat->values; val; val = val->next)
4706 ret |= decide_about_value (node, i, aglat->offset, val,
4707 known_csts, known_contexts);
4710 if (!ctxlat->bottom
4711 && known_contexts[i].useless_p ())
4713 ipcp_value<ipa_polymorphic_call_context> *val;
4714 for (val = ctxlat->values; val; val = val->next)
4715 ret |= decide_about_value (node, i, -1, val, known_csts,
4716 known_contexts);
4719 info = IPA_NODE_REF (node);
4722 if (info->do_clone_for_all_contexts)
4724 struct cgraph_node *clone;
4725 vec<cgraph_edge *> callers;
4727 if (dump_file)
4728 fprintf (dump_file, " - Creating a specialized node of %s "
4729 "for all known contexts.\n", node->dump_name ());
4731 callers = node->collect_callers ();
4733 if (!known_contexts_useful_p (known_contexts))
4735 known_contexts.release ();
4736 known_contexts = vNULL;
4738 clone = create_specialized_node (node, known_csts, known_contexts,
4739 known_aggs_to_agg_replacement_list (known_aggs),
4740 callers);
4741 info = IPA_NODE_REF (node);
4742 info->do_clone_for_all_contexts = false;
4743 IPA_NODE_REF (clone)->is_all_contexts_clone = true;
4744 for (i = 0; i < count; i++)
4745 vec_free (known_aggs[i].items);
4746 known_aggs.release ();
4747 ret = true;
4749 else
4751 known_csts.release ();
4752 known_contexts.release ();
4755 return ret;
4758 /* Transitively mark all callees of NODE within the same SCC as not dead. */
4760 static void
4761 spread_undeadness (struct cgraph_node *node)
4763 struct cgraph_edge *cs;
4765 for (cs = node->callees; cs; cs = cs->next_callee)
4766 if (ipa_edge_within_scc (cs))
4768 struct cgraph_node *callee;
4769 struct ipa_node_params *info;
4771 callee = cs->callee->function_symbol (NULL);
4772 info = IPA_NODE_REF (callee);
4774 if (info->node_dead)
4776 info->node_dead = 0;
4777 spread_undeadness (callee);
4782 /* Return true if NODE has a caller from outside of its SCC that is not
4783 dead. Worker callback for cgraph_for_node_and_aliases. */
4785 static bool
4786 has_undead_caller_from_outside_scc_p (struct cgraph_node *node,
4787 void *data ATTRIBUTE_UNUSED)
4789 struct cgraph_edge *cs;
4791 for (cs = node->callers; cs; cs = cs->next_caller)
4792 if (cs->caller->thunk.thunk_p
4793 && cs->caller->call_for_symbol_thunks_and_aliases
4794 (has_undead_caller_from_outside_scc_p, NULL, true))
4795 return true;
4796 else if (!ipa_edge_within_scc (cs)
4797 && !IPA_NODE_REF (cs->caller)->node_dead)
4798 return true;
4799 return false;
4803 /* Identify nodes within the same SCC as NODE which are no longer needed
4804 because of new clones and will be removed as unreachable. */
4806 static void
4807 identify_dead_nodes (struct cgraph_node *node)
4809 struct cgraph_node *v;
4810 for (v = node; v; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
4811 if (v->local.local
4812 && !v->call_for_symbol_thunks_and_aliases
4813 (has_undead_caller_from_outside_scc_p, NULL, true))
4814 IPA_NODE_REF (v)->node_dead = 1;
4816 for (v = node; v; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
4817 if (!IPA_NODE_REF (v)->node_dead)
4818 spread_undeadness (v);
4820 if (dump_file && (dump_flags & TDF_DETAILS))
4822 for (v = node; v; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
4823 if (IPA_NODE_REF (v)->node_dead)
4824 fprintf (dump_file, " Marking node as dead: %s.\n", v->dump_name ());
4828 /* The decision stage. Iterate over the topological order of call graph nodes
4829 TOPO and make specialized clones if deemed beneficial. */
4831 static void
4832 ipcp_decision_stage (struct ipa_topo_info *topo)
4834 int i;
4836 if (dump_file)
4837 fprintf (dump_file, "\nIPA decision stage:\n\n");
4839 for (i = topo->nnodes - 1; i >= 0; i--)
4841 struct cgraph_node *node = topo->order[i];
4842 bool change = false, iterate = true;
4844 while (iterate)
4846 struct cgraph_node *v;
4847 iterate = false;
4848 for (v = node; v; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
4849 if (v->has_gimple_body_p ()
4850 && ipcp_versionable_function_p (v))
4851 iterate |= decide_whether_version_node (v);
4853 change |= iterate;
4855 if (change)
4856 identify_dead_nodes (node);
4860 /* Look up all the bits information that we have discovered and copy it over
4861 to the transformation summary. */
4863 static void
4864 ipcp_store_bits_results (void)
4866 cgraph_node *node;
4868 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
4870 ipa_node_params *info = IPA_NODE_REF (node);
4871 bool dumped_sth = false;
4872 bool found_useful_result = false;
4874 if (!opt_for_fn (node->decl, flag_ipa_bit_cp))
4876 if (dump_file)
4877 fprintf (dump_file, "Not considering %s for ipa bitwise propagation "
4878 "; -fipa-bit-cp: disabled.\n",
4879 node->name ());
4880 continue;
4883 if (info->ipcp_orig_node)
4884 info = IPA_NODE_REF (info->ipcp_orig_node);
4886 unsigned count = ipa_get_param_count (info);
4887 for (unsigned i = 0; i < count; i++)
4889 ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
4890 if (plats->bits_lattice.constant_p ())
4892 found_useful_result = true;
4893 break;
4897 if (!found_useful_result)
4898 continue;
4900 ipcp_grow_transformations_if_necessary ();
4901 ipcp_transformation_summary *ts = ipcp_get_transformation_summary (node);
4902 vec_safe_reserve_exact (ts->bits, count);
4904 for (unsigned i = 0; i < count; i++)
4906 ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
4907 ipa_bits *jfbits;
4909 if (plats->bits_lattice.constant_p ())
4910 jfbits
4911 = ipa_get_ipa_bits_for_value (plats->bits_lattice.get_value (),
4912 plats->bits_lattice.get_mask ());
4913 else
4914 jfbits = NULL;
4916 ts->bits->quick_push (jfbits);
4917 if (!dump_file || !jfbits)
4918 continue;
4919 if (!dumped_sth)
4921 fprintf (dump_file, "Propagated bits info for function %s:\n",
4922 node->dump_name ());
4923 dumped_sth = true;
4925 fprintf (dump_file, " param %i: value = ", i);
4926 print_hex (jfbits->value, dump_file);
4927 fprintf (dump_file, ", mask = ");
4928 print_hex (jfbits->mask, dump_file);
4929 fprintf (dump_file, "\n");
4934 /* Look up all VR information that we have discovered and copy it over
4935 to the transformation summary. */
4937 static void
4938 ipcp_store_vr_results (void)
4940 cgraph_node *node;
4942 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
4944 ipa_node_params *info = IPA_NODE_REF (node);
4945 bool found_useful_result = false;
4947 if (!opt_for_fn (node->decl, flag_ipa_vrp))
4949 if (dump_file)
4950 fprintf (dump_file, "Not considering %s for VR discovery "
4951 "and propagate; -fipa-ipa-vrp: disabled.\n",
4952 node->name ());
4953 continue;
4956 if (info->ipcp_orig_node)
4957 info = IPA_NODE_REF (info->ipcp_orig_node);
4959 unsigned count = ipa_get_param_count (info);
4960 for (unsigned i = 0; i < count; i++)
4962 ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
4963 if (!plats->m_value_range.bottom_p ()
4964 && !plats->m_value_range.top_p ())
4966 found_useful_result = true;
4967 break;
4970 if (!found_useful_result)
4971 continue;
4973 ipcp_grow_transformations_if_necessary ();
4974 ipcp_transformation_summary *ts = ipcp_get_transformation_summary (node);
4975 vec_safe_reserve_exact (ts->m_vr, count);
4977 for (unsigned i = 0; i < count; i++)
4979 ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
4980 ipa_vr vr;
4982 if (!plats->m_value_range.bottom_p ()
4983 && !plats->m_value_range.top_p ())
4985 vr.known = true;
4986 vr.type = plats->m_value_range.m_vr.type;
4987 vr.min = wi::to_wide (plats->m_value_range.m_vr.min);
4988 vr.max = wi::to_wide (plats->m_value_range.m_vr.max);
4990 else
4992 vr.known = false;
4993 vr.type = VR_VARYING;
4994 vr.min = vr.max = wi::zero (INT_TYPE_SIZE);
4996 ts->m_vr->quick_push (vr);
5001 /* The IPCP driver. */
5003 static unsigned int
5004 ipcp_driver (void)
5006 struct cgraph_2edge_hook_list *edge_duplication_hook_holder;
5007 struct cgraph_edge_hook_list *edge_removal_hook_holder;
5008 struct ipa_topo_info topo;
5010 ipa_check_create_node_params ();
5011 ipa_check_create_edge_args ();
5012 grow_edge_clone_vectors ();
5013 edge_duplication_hook_holder
5014 = symtab->add_edge_duplication_hook (&ipcp_edge_duplication_hook, NULL);
5015 edge_removal_hook_holder
5016 = symtab->add_edge_removal_hook (&ipcp_edge_removal_hook, NULL);
5018 if (dump_file)
5020 fprintf (dump_file, "\nIPA structures before propagation:\n");
5021 if (dump_flags & TDF_DETAILS)
5022 ipa_print_all_params (dump_file);
5023 ipa_print_all_jump_functions (dump_file);
5026 /* Topological sort. */
5027 build_toporder_info (&topo);
5028 /* Do the interprocedural propagation. */
5029 ipcp_propagate_stage (&topo);
5030 /* Decide what constant propagation and cloning should be performed. */
5031 ipcp_decision_stage (&topo);
5032 /* Store results of bits propagation. */
5033 ipcp_store_bits_results ();
5034 /* Store results of value range propagation. */
5035 ipcp_store_vr_results ();
5037 /* Free all IPCP structures. */
5038 free_toporder_info (&topo);
5039 next_edge_clone.release ();
5040 prev_edge_clone.release ();
5041 symtab->remove_edge_removal_hook (edge_removal_hook_holder);
5042 symtab->remove_edge_duplication_hook (edge_duplication_hook_holder);
5043 ipa_free_all_structures_after_ipa_cp ();
5044 if (dump_file)
5045 fprintf (dump_file, "\nIPA constant propagation end\n");
5046 return 0;
5049 /* Initialization and computation of IPCP data structures. This is the initial
5050 intraprocedural analysis of functions, which gathers information to be
5051 propagated later on. */
5053 static void
5054 ipcp_generate_summary (void)
5056 struct cgraph_node *node;
5058 if (dump_file)
5059 fprintf (dump_file, "\nIPA constant propagation start:\n");
5060 ipa_register_cgraph_hooks ();
5062 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
5063 ipa_analyze_node (node);
5066 /* Write ipcp summary for nodes in SET. */
5068 static void
5069 ipcp_write_summary (void)
5071 ipa_prop_write_jump_functions ();
5074 /* Read ipcp summary. */
5076 static void
5077 ipcp_read_summary (void)
5079 ipa_prop_read_jump_functions ();
5082 namespace {
5084 const pass_data pass_data_ipa_cp =
5086 IPA_PASS, /* type */
5087 "cp", /* name */
5088 OPTGROUP_NONE, /* optinfo_flags */
5089 TV_IPA_CONSTANT_PROP, /* tv_id */
5090 0, /* properties_required */
5091 0, /* properties_provided */
5092 0, /* properties_destroyed */
5093 0, /* todo_flags_start */
5094 ( TODO_dump_symtab | TODO_remove_functions ), /* todo_flags_finish */
5097 class pass_ipa_cp : public ipa_opt_pass_d
5099 public:
5100 pass_ipa_cp (gcc::context *ctxt)
5101 : ipa_opt_pass_d (pass_data_ipa_cp, ctxt,
5102 ipcp_generate_summary, /* generate_summary */
5103 ipcp_write_summary, /* write_summary */
5104 ipcp_read_summary, /* read_summary */
5105 ipcp_write_transformation_summaries, /*
5106 write_optimization_summary */
5107 ipcp_read_transformation_summaries, /*
5108 read_optimization_summary */
5109 NULL, /* stmt_fixup */
5110 0, /* function_transform_todo_flags_start */
5111 ipcp_transform_function, /* function_transform */
5112 NULL) /* variable_transform */
5115 /* opt_pass methods: */
5116 virtual bool gate (function *)
5118 /* FIXME: We should remove the optimize check after we ensure we never run
5119 IPA passes when not optimizing. */
5120 return (flag_ipa_cp && optimize) || in_lto_p;
5123 virtual unsigned int execute (function *) { return ipcp_driver (); }
5125 }; // class pass_ipa_cp
5127 } // anon namespace
5129 ipa_opt_pass_d *
5130 make_pass_ipa_cp (gcc::context *ctxt)
5132 return new pass_ipa_cp (ctxt);
5135 /* Reset all state within ipa-cp.c so that we can rerun the compiler
5136 within the same process. For use by toplev::finalize. */
5138 void
5139 ipa_cp_c_finalize (void)
5141 max_count = profile_count::uninitialized ();
5142 overall_size = 0;
5143 max_new_size = 0;