1 /* Interprocedural constant propagation
2 Copyright (C) 2005-2020 Free Software Foundation, Inc.
4 Contributed by Razya Ladelsky <RAZYA@il.ibm.com> and Martin Jambor
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
23 /* Interprocedural constant propagation (IPA-CP).
25 The goal of this transformation is to
27 1) discover functions which are always invoked with some arguments with the
28 same known constant values and modify the functions so that the
29 subsequent optimizations can take advantage of the knowledge, and
31 2) partial specialization - create specialized versions of functions
32 transformed in this way if some parameters are known constants only in
33 certain contexts but the estimated tradeoff between speedup and cost size
36 The algorithm also propagates types and attempts to perform type based
37 devirtualization. Types are propagated much like constants.
39 The algorithm basically consists of three stages. In the first, functions
40 are analyzed one at a time and jump functions are constructed for all known
41 call-sites. In the second phase, the pass propagates information from the
42 jump functions across the call to reveal what values are available at what
43 call sites, performs estimations of effects of known values on functions and
44 their callees, and finally decides what specialized extra versions should be
45 created. In the third, the special versions materialize and appropriate
48 The algorithm used is to a certain extent based on "Interprocedural Constant
49 Propagation", by David Callahan, Keith D Cooper, Ken Kennedy, Linda Torczon,
50 Comp86, pg 152-161 and "A Methodology for Procedure Cloning" by Keith D
51 Cooper, Mary W. Hall, and Ken Kennedy.
54 First stage - intraprocedural analysis
55 =======================================
57 This phase computes jump_function and modification flags.
59 A jump function for a call-site represents the values passed as an actual
60 arguments of a given call-site. In principle, there are three types of
63 Pass through - the caller's formal parameter is passed as an actual
64 argument, plus an operation on it can be performed.
65 Constant - a constant is passed as an actual argument.
66 Unknown - neither of the above.
68 All jump function types are described in detail in ipa-prop.h, together with
69 the data structures that represent them and methods of accessing them.
71 ipcp_generate_summary() is the main function of the first stage.
73 Second stage - interprocedural analysis
74 ========================================
76 This stage is itself divided into two phases. In the first, we propagate
77 known values over the call graph, in the second, we make cloning decisions.
78 It uses a different algorithm than the original Callahan's paper.
80 First, we traverse the functions topologically from callers to callees and,
81 for each strongly connected component (SCC), we propagate constants
82 according to previously computed jump functions. We also record what known
83 values depend on other known values and estimate local effects. Finally, we
84 propagate cumulative information about these effects from dependent values
85 to those on which they depend.
87 Second, we again traverse the call graph in the same topological order and
88 make clones for functions which we know are called with the same values in
89 all contexts and decide about extra specialized clones of functions just for
90 some contexts - these decisions are based on both local estimates and
91 cumulative estimates propagated from callees.
93 ipcp_propagate_stage() and ipcp_decision_stage() together constitute the
96 Third phase - materialization of clones, call statement updates.
97 ============================================
99 This stage is currently performed by call graph code (mainly in cgraphunit.c
100 and tree-inline.c) according to instructions inserted to the call graph by
105 #include "coretypes.h"
108 #include "gimple-expr.h"
110 #include "alloc-pool.h"
111 #include "tree-pass.h"
113 #include "diagnostic.h"
114 #include "fold-const.h"
115 #include "gimple-fold.h"
116 #include "symbol-summary.h"
117 #include "tree-vrp.h"
118 #include "ipa-prop.h"
119 #include "tree-pretty-print.h"
120 #include "tree-inline.h"
121 #include "ipa-fnsummary.h"
122 #include "ipa-utils.h"
123 #include "tree-ssa-ccp.h"
124 #include "stringpool.h"
127 template <typename valtype
> class ipcp_value
;
129 /* Describes a particular source for an IPA-CP value. */
131 template <typename valtype
>
132 struct ipcp_value_source
135 /* Aggregate offset of the source, negative if the source is scalar value of
136 the argument itself. */
137 HOST_WIDE_INT offset
;
138 /* The incoming edge that brought the value. */
140 /* If the jump function that resulted into his value was a pass-through or an
141 ancestor, this is the ipcp_value of the caller from which the described
142 value has been derived. Otherwise it is NULL. */
143 ipcp_value
<valtype
> *val
;
144 /* Next pointer in a linked list of sources of a value. */
145 ipcp_value_source
*next
;
146 /* If the jump function that resulted into his value was a pass-through or an
147 ancestor, this is the index of the parameter of the caller the jump
148 function references. */
152 /* Common ancestor for all ipcp_value instantiations. */
154 class ipcp_value_base
157 /* Time benefit and size cost that specializing the function for this value
158 would bring about in this function alone. */
159 int local_time_benefit
, local_size_cost
;
160 /* Time benefit and size cost that specializing the function for this value
161 can bring about in it's callees (transitively). */
162 int prop_time_benefit
, prop_size_cost
;
165 : local_time_benefit (0), local_size_cost (0),
166 prop_time_benefit (0), prop_size_cost (0) {}
169 /* Describes one particular value stored in struct ipcp_lattice. */
171 template <typename valtype
>
172 class ipcp_value
: public ipcp_value_base
175 /* The actual value for the given parameter. */
177 /* The list of sources from which this value originates. */
178 ipcp_value_source
<valtype
> *sources
;
179 /* Next pointers in a linked list of all values in a lattice. */
181 /* Next pointers in a linked list of values in a strongly connected component
183 ipcp_value
*scc_next
;
184 /* Next pointers in a linked list of SCCs of values sorted topologically
185 according their sources. */
186 ipcp_value
*topo_next
;
187 /* A specialized node created for this value, NULL if none has been (so far)
189 cgraph_node
*spec_node
;
190 /* Depth first search number and low link for topological sorting of
193 /* True if this value is currently on the topo-sort stack. */
197 : sources (0), next (0), scc_next (0), topo_next (0),
198 spec_node (0), dfs (0), low_link (0), on_stack (false) {}
200 void add_source (cgraph_edge
*cs
, ipcp_value
*src_val
, int src_idx
,
201 HOST_WIDE_INT offset
);
204 /* Lattice describing potential values of a formal parameter of a function, or
205 a part of an aggregate. TOP is represented by a lattice with zero values
206 and with contains_variable and bottom flags cleared. BOTTOM is represented
207 by a lattice with the bottom flag set. In that case, values and
208 contains_variable flag should be disregarded. */
210 template <typename valtype
>
214 /* The list of known values and types in this lattice. Note that values are
215 not deallocated if a lattice is set to bottom because there may be value
216 sources referencing them. */
217 ipcp_value
<valtype
> *values
;
218 /* Number of known values and types in this lattice. */
220 /* The lattice contains a variable component (in addition to values). */
221 bool contains_variable
;
222 /* The value of the lattice is bottom (i.e. variable and unusable for any
226 inline bool is_single_const ();
227 inline bool set_to_bottom ();
228 inline bool set_contains_variable ();
229 bool add_value (valtype newval
, cgraph_edge
*cs
,
230 ipcp_value
<valtype
> *src_val
= NULL
,
231 int src_idx
= 0, HOST_WIDE_INT offset
= -1,
232 ipcp_value
<valtype
> **val_p
= NULL
,
233 bool unlimited
= false);
234 void print (FILE * f
, bool dump_sources
, bool dump_benefits
);
237 /* Lattice of tree values with an offset to describe a part of an
240 struct ipcp_agg_lattice
: public ipcp_lattice
<tree
>
243 /* Offset that is being described by this lattice. */
244 HOST_WIDE_INT offset
;
245 /* Size so that we don't have to re-compute it every time we traverse the
246 list. Must correspond to TYPE_SIZE of all lat values. */
248 /* Next element of the linked list. */
249 struct ipcp_agg_lattice
*next
;
252 /* Lattice of known bits, only capable of holding one value.
253 Bitwise constant propagation propagates which bits of a
269 In the above case, the param 'x' will always have all
270 the bits (except the bits in lsb) set to 0.
271 Hence the mask of 'x' would be 0xff. The mask
272 reflects that the bits in lsb are unknown.
273 The actual propagated value is given by m_value & ~m_mask. */
275 class ipcp_bits_lattice
278 bool bottom_p () { return m_lattice_val
== IPA_BITS_VARYING
; }
279 bool top_p () { return m_lattice_val
== IPA_BITS_UNDEFINED
; }
280 bool constant_p () { return m_lattice_val
== IPA_BITS_CONSTANT
; }
281 bool set_to_bottom ();
282 bool set_to_constant (widest_int
, widest_int
);
284 widest_int
get_value () { return m_value
; }
285 widest_int
get_mask () { return m_mask
; }
287 bool meet_with (ipcp_bits_lattice
& other
, unsigned, signop
,
288 enum tree_code
, tree
);
290 bool meet_with (widest_int
, widest_int
, unsigned);
295 enum { IPA_BITS_UNDEFINED
, IPA_BITS_CONSTANT
, IPA_BITS_VARYING
} m_lattice_val
;
297 /* Similar to ccp_lattice_t, mask represents which bits of value are constant.
298 If a bit in mask is set to 0, then the corresponding bit in
299 value is known to be constant. */
300 widest_int m_value
, m_mask
;
302 bool meet_with_1 (widest_int
, widest_int
, unsigned);
303 void get_value_and_mask (tree
, widest_int
*, widest_int
*);
306 /* Lattice of value ranges. */
308 class ipcp_vr_lattice
313 inline bool bottom_p () const;
314 inline bool top_p () const;
315 inline bool set_to_bottom ();
316 bool meet_with (const value_range
*p_vr
);
317 bool meet_with (const ipcp_vr_lattice
&other
);
318 void init () { gcc_assert (m_vr
.undefined_p ()); }
319 void print (FILE * f
);
322 bool meet_with_1 (const value_range
*other_vr
);
325 /* Structure containing lattices for a parameter itself and for pieces of
326 aggregates that are passed in the parameter or by a reference in a parameter
327 plus some other useful flags. */
329 class ipcp_param_lattices
332 /* Lattice describing the value of the parameter itself. */
333 ipcp_lattice
<tree
> itself
;
334 /* Lattice describing the polymorphic contexts of a parameter. */
335 ipcp_lattice
<ipa_polymorphic_call_context
> ctxlat
;
336 /* Lattices describing aggregate parts. */
337 ipcp_agg_lattice
*aggs
;
338 /* Lattice describing known bits. */
339 ipcp_bits_lattice bits_lattice
;
340 /* Lattice describing value range. */
341 ipcp_vr_lattice m_value_range
;
342 /* Number of aggregate lattices */
344 /* True if aggregate data were passed by reference (as opposed to by
347 /* All aggregate lattices contain a variable component (in addition to
349 bool aggs_contain_variable
;
350 /* The value of all aggregate lattices is bottom (i.e. variable and unusable
351 for any propagation). */
354 /* There is a virtual call based on this parameter. */
358 /* Allocation pools for values and their sources in ipa-cp. */
360 object_allocator
<ipcp_value
<tree
> > ipcp_cst_values_pool
361 ("IPA-CP constant values");
363 object_allocator
<ipcp_value
<ipa_polymorphic_call_context
> >
364 ipcp_poly_ctx_values_pool ("IPA-CP polymorphic contexts");
366 object_allocator
<ipcp_value_source
<tree
> > ipcp_sources_pool
367 ("IPA-CP value sources");
369 object_allocator
<ipcp_agg_lattice
> ipcp_agg_lattice_pool
370 ("IPA_CP aggregate lattices");
372 /* Maximal count found in program. */
374 static profile_count max_count
;
376 /* Original overall size of the program. */
378 static long overall_size
, orig_overall_size
;
380 /* Node name to unique clone suffix number map. */
381 static hash_map
<const char *, unsigned> *clone_num_suffixes
;
383 /* Return the param lattices structure corresponding to the Ith formal
384 parameter of the function described by INFO. */
385 static inline class ipcp_param_lattices
*
386 ipa_get_parm_lattices (class ipa_node_params
*info
, int i
)
388 gcc_assert (i
>= 0 && i
< ipa_get_param_count (info
));
389 gcc_checking_assert (!info
->ipcp_orig_node
);
390 gcc_checking_assert (info
->lattices
);
391 return &(info
->lattices
[i
]);
394 /* Return the lattice corresponding to the scalar value of the Ith formal
395 parameter of the function described by INFO. */
396 static inline ipcp_lattice
<tree
> *
397 ipa_get_scalar_lat (class ipa_node_params
*info
, int i
)
399 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
400 return &plats
->itself
;
403 /* Return the lattice corresponding to the scalar value of the Ith formal
404 parameter of the function described by INFO. */
405 static inline ipcp_lattice
<ipa_polymorphic_call_context
> *
406 ipa_get_poly_ctx_lat (class ipa_node_params
*info
, int i
)
408 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
409 return &plats
->ctxlat
;
412 /* Return whether LAT is a lattice with a single constant and without an
415 template <typename valtype
>
417 ipcp_lattice
<valtype
>::is_single_const ()
419 if (bottom
|| contains_variable
|| values_count
!= 1)
425 /* Print V which is extracted from a value in a lattice to F. */
428 print_ipcp_constant_value (FILE * f
, tree v
)
430 if (TREE_CODE (v
) == ADDR_EXPR
431 && TREE_CODE (TREE_OPERAND (v
, 0)) == CONST_DECL
)
434 print_generic_expr (f
, DECL_INITIAL (TREE_OPERAND (v
, 0)));
437 print_generic_expr (f
, v
);
440 /* Print V which is extracted from a value in a lattice to F. */
443 print_ipcp_constant_value (FILE * f
, ipa_polymorphic_call_context v
)
448 /* Print a lattice LAT to F. */
450 template <typename valtype
>
452 ipcp_lattice
<valtype
>::print (FILE * f
, bool dump_sources
, bool dump_benefits
)
454 ipcp_value
<valtype
> *val
;
459 fprintf (f
, "BOTTOM\n");
463 if (!values_count
&& !contains_variable
)
465 fprintf (f
, "TOP\n");
469 if (contains_variable
)
471 fprintf (f
, "VARIABLE");
477 for (val
= values
; val
; val
= val
->next
)
479 if (dump_benefits
&& prev
)
481 else if (!dump_benefits
&& prev
)
486 print_ipcp_constant_value (f
, val
->value
);
490 ipcp_value_source
<valtype
> *s
;
492 fprintf (f
, " [from:");
493 for (s
= val
->sources
; s
; s
= s
->next
)
494 fprintf (f
, " %i(%f)", s
->cs
->caller
->order
,
495 s
->cs
->sreal_frequency ().to_double ());
500 fprintf (f
, " [loc_time: %i, loc_size: %i, "
501 "prop_time: %i, prop_size: %i]\n",
502 val
->local_time_benefit
, val
->local_size_cost
,
503 val
->prop_time_benefit
, val
->prop_size_cost
);
510 ipcp_bits_lattice::print (FILE *f
)
513 fprintf (f
, " Bits unknown (TOP)\n");
514 else if (bottom_p ())
515 fprintf (f
, " Bits unusable (BOTTOM)\n");
518 fprintf (f
, " Bits: value = "); print_hex (get_value (), f
);
519 fprintf (f
, ", mask = "); print_hex (get_mask (), f
);
524 /* Print value range lattice to F. */
527 ipcp_vr_lattice::print (FILE * f
)
529 dump_value_range (f
, &m_vr
);
532 /* Print all ipcp_lattices of all functions to F. */
535 print_all_lattices (FILE * f
, bool dump_sources
, bool dump_benefits
)
537 struct cgraph_node
*node
;
540 fprintf (f
, "\nLattices:\n");
541 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
543 class ipa_node_params
*info
;
545 info
= IPA_NODE_REF (node
);
546 /* Skip unoptimized functions and constprop clones since we don't make
547 lattices for them. */
548 if (!info
|| info
->ipcp_orig_node
)
550 fprintf (f
, " Node: %s:\n", node
->dump_name ());
551 count
= ipa_get_param_count (info
);
552 for (i
= 0; i
< count
; i
++)
554 struct ipcp_agg_lattice
*aglat
;
555 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
556 fprintf (f
, " param [%d]: ", i
);
557 plats
->itself
.print (f
, dump_sources
, dump_benefits
);
558 fprintf (f
, " ctxs: ");
559 plats
->ctxlat
.print (f
, dump_sources
, dump_benefits
);
560 plats
->bits_lattice
.print (f
);
562 plats
->m_value_range
.print (f
);
564 if (plats
->virt_call
)
565 fprintf (f
, " virt_call flag set\n");
567 if (plats
->aggs_bottom
)
569 fprintf (f
, " AGGS BOTTOM\n");
572 if (plats
->aggs_contain_variable
)
573 fprintf (f
, " AGGS VARIABLE\n");
574 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
576 fprintf (f
, " %soffset " HOST_WIDE_INT_PRINT_DEC
": ",
577 plats
->aggs_by_ref
? "ref " : "", aglat
->offset
);
578 aglat
->print (f
, dump_sources
, dump_benefits
);
584 /* Determine whether it is at all technically possible to create clones of NODE
585 and store this information in the ipa_node_params structure associated
589 determine_versionability (struct cgraph_node
*node
,
590 class ipa_node_params
*info
)
592 const char *reason
= NULL
;
594 /* There are a number of generic reasons functions cannot be versioned. We
595 also cannot remove parameters if there are type attributes such as fnspec
597 if (node
->alias
|| node
->thunk
.thunk_p
)
598 reason
= "alias or thunk";
599 else if (!node
->versionable
)
600 reason
= "not a tree_versionable_function";
601 else if (node
->get_availability () <= AVAIL_INTERPOSABLE
)
602 reason
= "insufficient body availability";
603 else if (!opt_for_fn (node
->decl
, optimize
)
604 || !opt_for_fn (node
->decl
, flag_ipa_cp
))
605 reason
= "non-optimized function";
606 else if (lookup_attribute ("omp declare simd", DECL_ATTRIBUTES (node
->decl
)))
608 /* Ideally we should clone the SIMD clones themselves and create
609 vector copies of them, so IPA-cp and SIMD clones can happily
610 coexist, but that may not be worth the effort. */
611 reason
= "function has SIMD clones";
613 else if (lookup_attribute ("target_clones", DECL_ATTRIBUTES (node
->decl
)))
615 /* Ideally we should clone the target clones themselves and create
616 copies of them, so IPA-cp and target clones can happily
617 coexist, but that may not be worth the effort. */
618 reason
= "function target_clones attribute";
620 /* Don't clone decls local to a comdat group; it breaks and for C++
621 decloned constructors, inlining is always better anyway. */
622 else if (node
->comdat_local_p ())
623 reason
= "comdat-local function";
624 else if (node
->calls_comdat_local
)
626 /* TODO: call is versionable if we make sure that all
627 callers are inside of a comdat group. */
628 reason
= "calls comdat-local function";
631 /* Functions calling BUILT_IN_VA_ARG_PACK and BUILT_IN_VA_ARG_PACK_LEN
632 work only when inlined. Cloning them may still lead to better code
633 because ipa-cp will not give up on cloning further. If the function is
634 external this however leads to wrong code because we may end up producing
635 offline copy of the function. */
636 if (DECL_EXTERNAL (node
->decl
))
637 for (cgraph_edge
*edge
= node
->callees
; !reason
&& edge
;
638 edge
= edge
->next_callee
)
639 if (fndecl_built_in_p (edge
->callee
->decl
, BUILT_IN_NORMAL
))
641 if (DECL_FUNCTION_CODE (edge
->callee
->decl
) == BUILT_IN_VA_ARG_PACK
)
642 reason
= "external function which calls va_arg_pack";
643 if (DECL_FUNCTION_CODE (edge
->callee
->decl
)
644 == BUILT_IN_VA_ARG_PACK_LEN
)
645 reason
= "external function which calls va_arg_pack_len";
648 if (reason
&& dump_file
&& !node
->alias
&& !node
->thunk
.thunk_p
)
649 fprintf (dump_file
, "Function %s is not versionable, reason: %s.\n",
650 node
->dump_name (), reason
);
652 info
->versionable
= (reason
== NULL
);
655 /* Return true if it is at all technically possible to create clones of a
659 ipcp_versionable_function_p (struct cgraph_node
*node
)
661 return IPA_NODE_REF (node
) && IPA_NODE_REF (node
)->versionable
;
664 /* Structure holding accumulated information about callers of a node. */
666 struct caller_statistics
668 profile_count count_sum
;
669 int n_calls
, n_hot_calls
, freq_sum
;
672 /* Initialize fields of STAT to zeroes. */
675 init_caller_stats (struct caller_statistics
*stats
)
677 stats
->count_sum
= profile_count::zero ();
679 stats
->n_hot_calls
= 0;
683 /* Worker callback of cgraph_for_node_and_aliases accumulating statistics of
684 non-thunk incoming edges to NODE. */
687 gather_caller_stats (struct cgraph_node
*node
, void *data
)
689 struct caller_statistics
*stats
= (struct caller_statistics
*) data
;
690 struct cgraph_edge
*cs
;
692 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
693 if (!cs
->caller
->thunk
.thunk_p
)
695 if (cs
->count
.ipa ().initialized_p ())
696 stats
->count_sum
+= cs
->count
.ipa ();
697 stats
->freq_sum
+= cs
->frequency ();
699 if (cs
->maybe_hot_p ())
700 stats
->n_hot_calls
++;
706 /* Return true if this NODE is viable candidate for cloning. */
709 ipcp_cloning_candidate_p (struct cgraph_node
*node
)
711 struct caller_statistics stats
;
713 gcc_checking_assert (node
->has_gimple_body_p ());
715 if (!opt_for_fn (node
->decl
, flag_ipa_cp_clone
))
718 fprintf (dump_file
, "Not considering %s for cloning; "
719 "-fipa-cp-clone disabled.\n",
724 if (node
->optimize_for_size_p ())
727 fprintf (dump_file
, "Not considering %s for cloning; "
728 "optimizing it for size.\n",
733 init_caller_stats (&stats
);
734 node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
, false);
736 if (ipa_size_summaries
->get (node
)->self_size
< stats
.n_calls
)
739 fprintf (dump_file
, "Considering %s for cloning; code might shrink.\n",
744 /* When profile is available and function is hot, propagate into it even if
745 calls seems cold; constant propagation can improve function's speed
747 if (max_count
> profile_count::zero ())
749 if (stats
.count_sum
> node
->count
.ipa ().apply_scale (90, 100))
752 fprintf (dump_file
, "Considering %s for cloning; "
753 "usually called directly.\n",
758 if (!stats
.n_hot_calls
)
761 fprintf (dump_file
, "Not considering %s for cloning; no hot calls.\n",
766 fprintf (dump_file
, "Considering %s for cloning.\n",
771 template <typename valtype
>
772 class value_topo_info
775 /* Head of the linked list of topologically sorted values. */
776 ipcp_value
<valtype
> *values_topo
;
777 /* Stack for creating SCCs, represented by a linked list too. */
778 ipcp_value
<valtype
> *stack
;
779 /* Counter driving the algorithm in add_val_to_toposort. */
782 value_topo_info () : values_topo (NULL
), stack (NULL
), dfs_counter (0)
784 void add_val (ipcp_value
<valtype
> *cur_val
);
785 void propagate_effects ();
788 /* Arrays representing a topological ordering of call graph nodes and a stack
789 of nodes used during constant propagation and also data required to perform
790 topological sort of values and propagation of benefits in the determined
796 /* Array with obtained topological order of cgraph nodes. */
797 struct cgraph_node
**order
;
798 /* Stack of cgraph nodes used during propagation within SCC until all values
799 in the SCC stabilize. */
800 struct cgraph_node
**stack
;
801 int nnodes
, stack_top
;
803 value_topo_info
<tree
> constants
;
804 value_topo_info
<ipa_polymorphic_call_context
> contexts
;
806 ipa_topo_info () : order(NULL
), stack(NULL
), nnodes(0), stack_top(0),
811 /* Skip edges from and to nodes without ipa_cp enabled.
812 Ignore not available symbols. */
815 ignore_edge_p (cgraph_edge
*e
)
817 enum availability avail
;
818 cgraph_node
*ultimate_target
819 = e
->callee
->function_or_virtual_thunk_symbol (&avail
, e
->caller
);
821 return (avail
<= AVAIL_INTERPOSABLE
822 || !opt_for_fn (ultimate_target
->decl
, optimize
)
823 || !opt_for_fn (ultimate_target
->decl
, flag_ipa_cp
));
826 /* Allocate the arrays in TOPO and topologically sort the nodes into order. */
829 build_toporder_info (class ipa_topo_info
*topo
)
831 topo
->order
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
832 topo
->stack
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
834 gcc_checking_assert (topo
->stack_top
== 0);
835 topo
->nnodes
= ipa_reduced_postorder (topo
->order
, true,
839 /* Free information about strongly connected components and the arrays in
843 free_toporder_info (class ipa_topo_info
*topo
)
845 ipa_free_postorder_info ();
850 /* Add NODE to the stack in TOPO, unless it is already there. */
853 push_node_to_stack (class ipa_topo_info
*topo
, struct cgraph_node
*node
)
855 class ipa_node_params
*info
= IPA_NODE_REF (node
);
856 if (info
->node_enqueued
)
858 info
->node_enqueued
= 1;
859 topo
->stack
[topo
->stack_top
++] = node
;
862 /* Pop a node from the stack in TOPO and return it or return NULL if the stack
865 static struct cgraph_node
*
866 pop_node_from_stack (class ipa_topo_info
*topo
)
870 struct cgraph_node
*node
;
872 node
= topo
->stack
[topo
->stack_top
];
873 IPA_NODE_REF (node
)->node_enqueued
= 0;
880 /* Set lattice LAT to bottom and return true if it previously was not set as
883 template <typename valtype
>
885 ipcp_lattice
<valtype
>::set_to_bottom ()
892 /* Mark lattice as containing an unknown value and return true if it previously
893 was not marked as such. */
895 template <typename valtype
>
897 ipcp_lattice
<valtype
>::set_contains_variable ()
899 bool ret
= !contains_variable
;
900 contains_variable
= true;
904 /* Set all aggregate lattices in PLATS to bottom and return true if they were
905 not previously set as such. */
908 set_agg_lats_to_bottom (class ipcp_param_lattices
*plats
)
910 bool ret
= !plats
->aggs_bottom
;
911 plats
->aggs_bottom
= true;
915 /* Mark all aggregate lattices in PLATS as containing an unknown value and
916 return true if they were not previously marked as such. */
919 set_agg_lats_contain_variable (class ipcp_param_lattices
*plats
)
921 bool ret
= !plats
->aggs_contain_variable
;
922 plats
->aggs_contain_variable
= true;
927 ipcp_vr_lattice::meet_with (const ipcp_vr_lattice
&other
)
929 return meet_with_1 (&other
.m_vr
);
932 /* Meet the current value of the lattice with value range described by VR
936 ipcp_vr_lattice::meet_with (const value_range
*p_vr
)
938 return meet_with_1 (p_vr
);
941 /* Meet the current value of the lattice with value range described by
942 OTHER_VR lattice. Return TRUE if anything changed. */
945 ipcp_vr_lattice::meet_with_1 (const value_range
*other_vr
)
950 if (other_vr
->varying_p ())
951 return set_to_bottom ();
953 value_range
save (m_vr
);
954 m_vr
.union_ (other_vr
);
955 return !m_vr
.equal_p (save
);
958 /* Return true if value range information in the lattice is yet unknown. */
961 ipcp_vr_lattice::top_p () const
963 return m_vr
.undefined_p ();
966 /* Return true if value range information in the lattice is known to be
970 ipcp_vr_lattice::bottom_p () const
972 return m_vr
.varying_p ();
975 /* Set value range information in the lattice to bottom. Return true if it
976 previously was in a different state. */
979 ipcp_vr_lattice::set_to_bottom ()
981 if (m_vr
.varying_p ())
983 /* ?? We create all sorts of VARYING ranges for floats, structures,
984 and other types which we cannot handle as ranges. We should
985 probably avoid handling them throughout the pass, but it's easier
986 to create a sensible VARYING here and let the lattice
988 m_vr
.set_varying (integer_type_node
);
992 /* Set lattice value to bottom, if it already isn't the case. */
995 ipcp_bits_lattice::set_to_bottom ()
999 m_lattice_val
= IPA_BITS_VARYING
;
1005 /* Set to constant if it isn't already. Only meant to be called
1006 when switching state from TOP. */
1009 ipcp_bits_lattice::set_to_constant (widest_int value
, widest_int mask
)
1011 gcc_assert (top_p ());
1012 m_lattice_val
= IPA_BITS_CONSTANT
;
1018 /* Convert operand to value, mask form. */
1021 ipcp_bits_lattice::get_value_and_mask (tree operand
, widest_int
*valuep
, widest_int
*maskp
)
1023 wide_int
get_nonzero_bits (const_tree
);
1025 if (TREE_CODE (operand
) == INTEGER_CST
)
1027 *valuep
= wi::to_widest (operand
);
1037 /* Meet operation, similar to ccp_lattice_meet, we xor values
1038 if this->value, value have different values at same bit positions, we want
1039 to drop that bit to varying. Return true if mask is changed.
1040 This function assumes that the lattice value is in CONSTANT state */
1043 ipcp_bits_lattice::meet_with_1 (widest_int value
, widest_int mask
,
1046 gcc_assert (constant_p ());
1048 widest_int old_mask
= m_mask
;
1049 m_mask
= (m_mask
| mask
) | (m_value
^ value
);
1051 if (wi::sext (m_mask
, precision
) == -1)
1052 return set_to_bottom ();
1054 return m_mask
!= old_mask
;
1057 /* Meet the bits lattice with operand
1058 described by <value, mask, sgn, precision. */
1061 ipcp_bits_lattice::meet_with (widest_int value
, widest_int mask
,
1069 if (wi::sext (mask
, precision
) == -1)
1070 return set_to_bottom ();
1071 return set_to_constant (value
, mask
);
1074 return meet_with_1 (value
, mask
, precision
);
1077 /* Meet bits lattice with the result of bit_value_binop (other, operand)
1078 if code is binary operation or bit_value_unop (other) if code is unary op.
1079 In the case when code is nop_expr, no adjustment is required. */
1082 ipcp_bits_lattice::meet_with (ipcp_bits_lattice
& other
, unsigned precision
,
1083 signop sgn
, enum tree_code code
, tree operand
)
1085 if (other
.bottom_p ())
1086 return set_to_bottom ();
1088 if (bottom_p () || other
.top_p ())
1091 widest_int adjusted_value
, adjusted_mask
;
1093 if (TREE_CODE_CLASS (code
) == tcc_binary
)
1095 tree type
= TREE_TYPE (operand
);
1096 widest_int o_value
, o_mask
;
1097 get_value_and_mask (operand
, &o_value
, &o_mask
);
1099 bit_value_binop (code
, sgn
, precision
, &adjusted_value
, &adjusted_mask
,
1100 sgn
, precision
, other
.get_value (), other
.get_mask (),
1101 TYPE_SIGN (type
), TYPE_PRECISION (type
), o_value
, o_mask
);
1103 if (wi::sext (adjusted_mask
, precision
) == -1)
1104 return set_to_bottom ();
1107 else if (TREE_CODE_CLASS (code
) == tcc_unary
)
1109 bit_value_unop (code
, sgn
, precision
, &adjusted_value
,
1110 &adjusted_mask
, sgn
, precision
, other
.get_value (),
1113 if (wi::sext (adjusted_mask
, precision
) == -1)
1114 return set_to_bottom ();
1118 return set_to_bottom ();
1122 if (wi::sext (adjusted_mask
, precision
) == -1)
1123 return set_to_bottom ();
1124 return set_to_constant (adjusted_value
, adjusted_mask
);
1127 return meet_with_1 (adjusted_value
, adjusted_mask
, precision
);
1130 /* Mark bot aggregate and scalar lattices as containing an unknown variable,
1131 return true is any of them has not been marked as such so far. */
1134 set_all_contains_variable (class ipcp_param_lattices
*plats
)
1137 ret
= plats
->itself
.set_contains_variable ();
1138 ret
|= plats
->ctxlat
.set_contains_variable ();
1139 ret
|= set_agg_lats_contain_variable (plats
);
1140 ret
|= plats
->bits_lattice
.set_to_bottom ();
1141 ret
|= plats
->m_value_range
.set_to_bottom ();
1145 /* Worker of call_for_symbol_thunks_and_aliases, increment the integer DATA
1146 points to by the number of callers to NODE. */
1149 count_callers (cgraph_node
*node
, void *data
)
1151 int *caller_count
= (int *) data
;
1153 for (cgraph_edge
*cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
1154 /* Local thunks can be handled transparently, but if the thunk cannot
1155 be optimized out, count it as a real use. */
1156 if (!cs
->caller
->thunk
.thunk_p
|| !cs
->caller
->local
)
1161 /* Worker of call_for_symbol_thunks_and_aliases, it is supposed to be called on
1162 the one caller of some other node. Set the caller's corresponding flag. */
1165 set_single_call_flag (cgraph_node
*node
, void *)
1167 cgraph_edge
*cs
= node
->callers
;
1168 /* Local thunks can be handled transparently, skip them. */
1169 while (cs
&& cs
->caller
->thunk
.thunk_p
&& cs
->caller
->local
)
1170 cs
= cs
->next_caller
;
1171 if (cs
&& IPA_NODE_REF (cs
->caller
))
1173 IPA_NODE_REF (cs
->caller
)->node_calling_single_call
= true;
1179 /* Initialize ipcp_lattices. */
1182 initialize_node_lattices (struct cgraph_node
*node
)
1184 class ipa_node_params
*info
= IPA_NODE_REF (node
);
1185 struct cgraph_edge
*ie
;
1186 bool disable
= false, variable
= false;
1189 gcc_checking_assert (node
->has_gimple_body_p ());
1191 if (!ipa_get_param_count (info
))
1193 else if (node
->local
)
1195 int caller_count
= 0;
1196 node
->call_for_symbol_thunks_and_aliases (count_callers
, &caller_count
,
1198 gcc_checking_assert (caller_count
> 0);
1199 if (caller_count
== 1)
1200 node
->call_for_symbol_thunks_and_aliases (set_single_call_flag
,
1205 /* When cloning is allowed, we can assume that externally visible
1206 functions are not called. We will compensate this by cloning
1208 if (ipcp_versionable_function_p (node
)
1209 && ipcp_cloning_candidate_p (node
))
1215 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1216 && !node
->alias
&& !node
->thunk
.thunk_p
)
1218 fprintf (dump_file
, "Initializing lattices of %s\n",
1219 node
->dump_name ());
1220 if (disable
|| variable
)
1221 fprintf (dump_file
, " Marking all lattices as %s\n",
1222 disable
? "BOTTOM" : "VARIABLE");
1225 auto_vec
<bool, 16> surviving_params
;
1226 bool pre_modified
= false;
1227 if (!disable
&& node
->clone
.param_adjustments
)
1229 /* At the moment all IPA optimizations should use the number of
1230 parameters of the prevailing decl as the m_always_copy_start.
1231 Handling any other value would complicate the code below, so for the
1232 time bing let's only assert it is so. */
1233 gcc_assert ((node
->clone
.param_adjustments
->m_always_copy_start
1234 == ipa_get_param_count (info
))
1235 || node
->clone
.param_adjustments
->m_always_copy_start
< 0);
1237 pre_modified
= true;
1238 node
->clone
.param_adjustments
->get_surviving_params (&surviving_params
);
1240 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1241 && !node
->alias
&& !node
->thunk
.thunk_p
)
1244 for (int j
= 0; j
< ipa_get_param_count (info
); j
++)
1246 if (j
< (int) surviving_params
.length ()
1247 && surviving_params
[j
])
1252 " The following parameters are dead on arrival:");
1255 fprintf (dump_file
, " %u", j
);
1258 fprintf (dump_file
, "\n");
1262 for (i
= 0; i
< ipa_get_param_count (info
); i
++)
1264 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1266 || (pre_modified
&& (surviving_params
.length () <= (unsigned) i
1267 || !surviving_params
[i
])))
1269 plats
->itself
.set_to_bottom ();
1270 plats
->ctxlat
.set_to_bottom ();
1271 set_agg_lats_to_bottom (plats
);
1272 plats
->bits_lattice
.set_to_bottom ();
1273 plats
->m_value_range
.set_to_bottom ();
1277 plats
->m_value_range
.init ();
1279 set_all_contains_variable (plats
);
1283 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
1284 if (ie
->indirect_info
->polymorphic
1285 && ie
->indirect_info
->param_index
>= 0)
1287 gcc_checking_assert (ie
->indirect_info
->param_index
>= 0);
1288 ipa_get_parm_lattices (info
,
1289 ie
->indirect_info
->param_index
)->virt_call
= 1;
1293 /* Return the result of a (possibly arithmetic) operation on the constant
1294 value INPUT. OPERAND is 2nd operand for binary operation. RES_TYPE is
1295 the type of the parameter to which the result is passed. Return
1296 NULL_TREE if that cannot be determined or be considered an
1297 interprocedural invariant. */
1300 ipa_get_jf_arith_result (enum tree_code opcode
, tree input
, tree operand
,
1305 if (opcode
== NOP_EXPR
)
1307 if (!is_gimple_ip_invariant (input
))
1312 if (TREE_CODE_CLASS (opcode
) == tcc_comparison
)
1313 res_type
= boolean_type_node
;
1314 else if (expr_type_first_operand_type_p (opcode
))
1315 res_type
= TREE_TYPE (input
);
1320 if (TREE_CODE_CLASS (opcode
) == tcc_unary
)
1321 res
= fold_unary (opcode
, res_type
, input
);
1323 res
= fold_binary (opcode
, res_type
, input
, operand
);
1325 if (res
&& !is_gimple_ip_invariant (res
))
1331 /* Return the result of a (possibly arithmetic) pass through jump function
1332 JFUNC on the constant value INPUT. RES_TYPE is the type of the parameter
1333 to which the result is passed. Return NULL_TREE if that cannot be
1334 determined or be considered an interprocedural invariant. */
1337 ipa_get_jf_pass_through_result (struct ipa_jump_func
*jfunc
, tree input
,
1340 return ipa_get_jf_arith_result (ipa_get_jf_pass_through_operation (jfunc
),
1342 ipa_get_jf_pass_through_operand (jfunc
),
1346 /* Return the result of an ancestor jump function JFUNC on the constant value
1347 INPUT. Return NULL_TREE if that cannot be determined. */
1350 ipa_get_jf_ancestor_result (struct ipa_jump_func
*jfunc
, tree input
)
1352 gcc_checking_assert (TREE_CODE (input
) != TREE_BINFO
);
1353 if (TREE_CODE (input
) == ADDR_EXPR
)
1355 gcc_checking_assert (is_gimple_ip_invariant_address (input
));
1356 poly_int64 off
= ipa_get_jf_ancestor_offset (jfunc
);
1357 if (known_eq (off
, 0))
1359 poly_int64 byte_offset
= exact_div (off
, BITS_PER_UNIT
);
1360 return build1 (ADDR_EXPR
, TREE_TYPE (input
),
1361 fold_build2 (MEM_REF
, TREE_TYPE (TREE_TYPE (input
)), input
,
1362 build_int_cst (ptr_type_node
, byte_offset
)));
1368 /* Determine whether JFUNC evaluates to a single known constant value and if
1369 so, return it. Otherwise return NULL. INFO describes the caller node or
1370 the one it is inlined to, so that pass-through jump functions can be
1371 evaluated. PARM_TYPE is the type of the parameter to which the result is
1375 ipa_value_from_jfunc (class ipa_node_params
*info
, struct ipa_jump_func
*jfunc
,
1378 if (jfunc
->type
== IPA_JF_CONST
)
1379 return ipa_get_jf_constant (jfunc
);
1380 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1381 || jfunc
->type
== IPA_JF_ANCESTOR
)
1386 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1387 idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1389 idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1391 if (info
->ipcp_orig_node
)
1392 input
= info
->known_csts
[idx
];
1395 ipcp_lattice
<tree
> *lat
;
1398 || idx
>= ipa_get_param_count (info
))
1400 lat
= ipa_get_scalar_lat (info
, idx
);
1401 if (!lat
->is_single_const ())
1403 input
= lat
->values
->value
;
1409 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1410 return ipa_get_jf_pass_through_result (jfunc
, input
, parm_type
);
1412 return ipa_get_jf_ancestor_result (jfunc
, input
);
1418 /* Determine whether JFUNC evaluates to single known polymorphic context, given
1419 that INFO describes the caller node or the one it is inlined to, CS is the
1420 call graph edge corresponding to JFUNC and CSIDX index of the described
1423 ipa_polymorphic_call_context
1424 ipa_context_from_jfunc (ipa_node_params
*info
, cgraph_edge
*cs
, int csidx
,
1425 ipa_jump_func
*jfunc
)
1427 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
1428 ipa_polymorphic_call_context ctx
;
1429 ipa_polymorphic_call_context
*edge_ctx
1430 = cs
? ipa_get_ith_polymorhic_call_context (args
, csidx
) : NULL
;
1432 if (edge_ctx
&& !edge_ctx
->useless_p ())
1435 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1436 || jfunc
->type
== IPA_JF_ANCESTOR
)
1438 ipa_polymorphic_call_context srcctx
;
1440 bool type_preserved
= true;
1441 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1443 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1445 type_preserved
= ipa_get_jf_pass_through_type_preserved (jfunc
);
1446 srcidx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1450 type_preserved
= ipa_get_jf_ancestor_type_preserved (jfunc
);
1451 srcidx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1453 if (info
->ipcp_orig_node
)
1455 if (info
->known_contexts
.exists ())
1456 srcctx
= info
->known_contexts
[srcidx
];
1461 || srcidx
>= ipa_get_param_count (info
))
1463 ipcp_lattice
<ipa_polymorphic_call_context
> *lat
;
1464 lat
= ipa_get_poly_ctx_lat (info
, srcidx
);
1465 if (!lat
->is_single_const ())
1467 srcctx
= lat
->values
->value
;
1469 if (srcctx
.useless_p ())
1471 if (jfunc
->type
== IPA_JF_ANCESTOR
)
1472 srcctx
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
1473 if (!type_preserved
)
1474 srcctx
.possible_dynamic_type_change (cs
->in_polymorphic_cdtor
);
1475 srcctx
.combine_with (ctx
);
1482 /* Emulate effects of unary OPERATION and/or conversion from SRC_TYPE to
1483 DST_TYPE on value range in SRC_VR and store it to DST_VR. Return true if
1484 the result is a range or an anti-range. */
1487 ipa_vr_operation_and_type_effects (value_range
*dst_vr
,
1488 value_range
*src_vr
,
1489 enum tree_code operation
,
1490 tree dst_type
, tree src_type
)
1492 range_fold_unary_expr (dst_vr
, operation
, dst_type
, src_vr
, src_type
);
1493 if (dst_vr
->varying_p () || dst_vr
->undefined_p ())
1498 /* Determine value_range of JFUNC given that INFO describes the caller node or
1499 the one it is inlined to, CS is the call graph edge corresponding to JFUNC
1500 and PARM_TYPE of the parameter. */
1503 ipa_value_range_from_jfunc (ipa_node_params
*info
, cgraph_edge
*cs
,
1504 ipa_jump_func
*jfunc
, tree parm_type
)
1509 ipa_vr_operation_and_type_effects (&vr
,
1511 NOP_EXPR
, parm_type
,
1512 jfunc
->m_vr
->type ());
1513 if (vr
.singleton_p ())
1515 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1518 ipcp_transformation
*sum
1519 = ipcp_get_transformation_summary (cs
->caller
->inlined_to
1520 ? cs
->caller
->inlined_to
1522 if (!sum
|| !sum
->m_vr
)
1525 idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1527 if (!(*sum
->m_vr
)[idx
].known
)
1529 tree vr_type
= ipa_get_type (info
, idx
);
1530 value_range
srcvr (wide_int_to_tree (vr_type
, (*sum
->m_vr
)[idx
].min
),
1531 wide_int_to_tree (vr_type
, (*sum
->m_vr
)[idx
].max
),
1532 (*sum
->m_vr
)[idx
].type
);
1534 enum tree_code operation
= ipa_get_jf_pass_through_operation (jfunc
);
1536 if (TREE_CODE_CLASS (operation
) == tcc_unary
)
1540 if (ipa_vr_operation_and_type_effects (&res
,
1542 operation
, parm_type
,
1548 value_range op_res
, res
;
1549 tree op
= ipa_get_jf_pass_through_operand (jfunc
);
1550 value_range
op_vr (op
, op
);
1552 range_fold_binary_expr (&op_res
, operation
, vr_type
, &srcvr
, &op_vr
);
1553 if (ipa_vr_operation_and_type_effects (&res
,
1555 NOP_EXPR
, parm_type
,
1563 /* See if NODE is a clone with a known aggregate value at a given OFFSET of a
1564 parameter with the given INDEX. */
1567 get_clone_agg_value (struct cgraph_node
*node
, HOST_WIDE_INT offset
,
1570 struct ipa_agg_replacement_value
*aggval
;
1572 aggval
= ipa_get_agg_replacements_for_node (node
);
1575 if (aggval
->offset
== offset
1576 && aggval
->index
== index
)
1577 return aggval
->value
;
1578 aggval
= aggval
->next
;
1583 /* Determine whether ITEM, jump function for an aggregate part, evaluates to a
1584 single known constant value and if so, return it. Otherwise return NULL.
1585 NODE and INFO describes the caller node or the one it is inlined to, and
1586 its related info. */
1589 ipa_agg_value_from_node (class ipa_node_params
*info
,
1590 struct cgraph_node
*node
,
1591 struct ipa_agg_jf_item
*item
)
1593 tree value
= NULL_TREE
;
1596 if (item
->offset
< 0 || item
->jftype
== IPA_JF_UNKNOWN
)
1599 if (item
->jftype
== IPA_JF_CONST
)
1600 return item
->value
.constant
;
1602 gcc_checking_assert (item
->jftype
== IPA_JF_PASS_THROUGH
1603 || item
->jftype
== IPA_JF_LOAD_AGG
);
1605 src_idx
= item
->value
.pass_through
.formal_id
;
1607 if (info
->ipcp_orig_node
)
1609 if (item
->jftype
== IPA_JF_PASS_THROUGH
)
1610 value
= info
->known_csts
[src_idx
];
1612 value
= get_clone_agg_value (node
, item
->value
.load_agg
.offset
,
1615 else if (info
->lattices
)
1617 class ipcp_param_lattices
*src_plats
1618 = ipa_get_parm_lattices (info
, src_idx
);
1620 if (item
->jftype
== IPA_JF_PASS_THROUGH
)
1622 struct ipcp_lattice
<tree
> *lat
= &src_plats
->itself
;
1624 if (!lat
->is_single_const ())
1627 value
= lat
->values
->value
;
1629 else if (src_plats
->aggs
1630 && !src_plats
->aggs_bottom
1631 && !src_plats
->aggs_contain_variable
1632 && src_plats
->aggs_by_ref
== item
->value
.load_agg
.by_ref
)
1634 struct ipcp_agg_lattice
*aglat
;
1636 for (aglat
= src_plats
->aggs
; aglat
; aglat
= aglat
->next
)
1638 if (aglat
->offset
> item
->value
.load_agg
.offset
)
1641 if (aglat
->offset
== item
->value
.load_agg
.offset
)
1643 if (aglat
->is_single_const ())
1644 value
= aglat
->values
->value
;
1654 if (item
->jftype
== IPA_JF_LOAD_AGG
)
1656 tree load_type
= item
->value
.load_agg
.type
;
1657 tree value_type
= TREE_TYPE (value
);
1659 /* Ensure value type is compatible with load type. */
1660 if (!useless_type_conversion_p (load_type
, value_type
))
1664 return ipa_get_jf_arith_result (item
->value
.pass_through
.operation
,
1666 item
->value
.pass_through
.operand
,
1670 /* Determine whether AGG_JFUNC evaluates to a set of known constant value for
1671 an aggregate and if so, return it. Otherwise return an empty set. NODE
1672 and INFO describes the caller node or the one it is inlined to, and its
1675 struct ipa_agg_value_set
1676 ipa_agg_value_set_from_jfunc (class ipa_node_params
*info
, cgraph_node
*node
,
1677 struct ipa_agg_jump_function
*agg_jfunc
)
1679 struct ipa_agg_value_set agg
;
1680 struct ipa_agg_jf_item
*item
;
1684 agg
.by_ref
= agg_jfunc
->by_ref
;
1686 FOR_EACH_VEC_SAFE_ELT (agg_jfunc
->items
, i
, item
)
1688 tree value
= ipa_agg_value_from_node (info
, node
, item
);
1692 struct ipa_agg_value value_item
;
1694 value_item
.offset
= item
->offset
;
1695 value_item
.value
= value
;
1697 agg
.items
.safe_push (value_item
);
1703 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
1704 bottom, not containing a variable component and without any known value at
1708 ipcp_verify_propagated_values (void)
1710 struct cgraph_node
*node
;
1712 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
1714 class ipa_node_params
*info
= IPA_NODE_REF (node
);
1715 if (!opt_for_fn (node
->decl
, flag_ipa_cp
)
1716 || !opt_for_fn (node
->decl
, optimize
))
1718 int i
, count
= ipa_get_param_count (info
);
1720 for (i
= 0; i
< count
; i
++)
1722 ipcp_lattice
<tree
> *lat
= ipa_get_scalar_lat (info
, i
);
1725 && !lat
->contains_variable
1726 && lat
->values_count
== 0)
1730 symtab
->dump (dump_file
);
1731 fprintf (dump_file
, "\nIPA lattices after constant "
1732 "propagation, before gcc_unreachable:\n");
1733 print_all_lattices (dump_file
, true, false);
1742 /* Return true iff X and Y should be considered equal values by IPA-CP. */
1745 values_equal_for_ipcp_p (tree x
, tree y
)
1747 gcc_checking_assert (x
!= NULL_TREE
&& y
!= NULL_TREE
);
1752 if (TREE_CODE (x
) == ADDR_EXPR
1753 && TREE_CODE (y
) == ADDR_EXPR
1754 && TREE_CODE (TREE_OPERAND (x
, 0)) == CONST_DECL
1755 && TREE_CODE (TREE_OPERAND (y
, 0)) == CONST_DECL
)
1756 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x
, 0)),
1757 DECL_INITIAL (TREE_OPERAND (y
, 0)), 0);
1759 return operand_equal_p (x
, y
, 0);
1762 /* Return true iff X and Y should be considered equal contexts by IPA-CP. */
1765 values_equal_for_ipcp_p (ipa_polymorphic_call_context x
,
1766 ipa_polymorphic_call_context y
)
1768 return x
.equal_to (y
);
1772 /* Add a new value source to the value represented by THIS, marking that a
1773 value comes from edge CS and (if the underlying jump function is a
1774 pass-through or an ancestor one) from a caller value SRC_VAL of a caller
1775 parameter described by SRC_INDEX. OFFSET is negative if the source was the
1776 scalar value of the parameter itself or the offset within an aggregate. */
1778 template <typename valtype
>
1780 ipcp_value
<valtype
>::add_source (cgraph_edge
*cs
, ipcp_value
*src_val
,
1781 int src_idx
, HOST_WIDE_INT offset
)
1783 ipcp_value_source
<valtype
> *src
;
1785 src
= new (ipcp_sources_pool
.allocate ()) ipcp_value_source
<valtype
>;
1786 src
->offset
= offset
;
1789 src
->index
= src_idx
;
1791 src
->next
= sources
;
1795 /* Allocate a new ipcp_value holding a tree constant, initialize its value to
1796 SOURCE and clear all other fields. */
1798 static ipcp_value
<tree
> *
1799 allocate_and_init_ipcp_value (tree source
)
1801 ipcp_value
<tree
> *val
;
1803 val
= new (ipcp_cst_values_pool
.allocate ()) ipcp_value
<tree
>();
1804 val
->value
= source
;
1808 /* Allocate a new ipcp_value holding a polymorphic context, initialize its
1809 value to SOURCE and clear all other fields. */
1811 static ipcp_value
<ipa_polymorphic_call_context
> *
1812 allocate_and_init_ipcp_value (ipa_polymorphic_call_context source
)
1814 ipcp_value
<ipa_polymorphic_call_context
> *val
;
1817 val
= new (ipcp_poly_ctx_values_pool
.allocate ())
1818 ipcp_value
<ipa_polymorphic_call_context
>();
1819 val
->value
= source
;
1823 /* Try to add NEWVAL to LAT, potentially creating a new ipcp_value for it. CS,
1824 SRC_VAL SRC_INDEX and OFFSET are meant for add_source and have the same
1825 meaning. OFFSET -1 means the source is scalar and not a part of an
1826 aggregate. If non-NULL, VAL_P records address of existing or newly added
1827 ipcp_value. UNLIMITED means whether value count should not exceed the limit
1828 given by PARAM_IPA_CP_VALUE_LIST_SIZE. */
1830 template <typename valtype
>
1832 ipcp_lattice
<valtype
>::add_value (valtype newval
, cgraph_edge
*cs
,
1833 ipcp_value
<valtype
> *src_val
,
1834 int src_idx
, HOST_WIDE_INT offset
,
1835 ipcp_value
<valtype
> **val_p
,
1838 ipcp_value
<valtype
> *val
, *last_val
= NULL
;
1846 for (val
= values
; val
; last_val
= val
, val
= val
->next
)
1847 if (values_equal_for_ipcp_p (val
->value
, newval
))
1852 if (ipa_edge_within_scc (cs
))
1854 ipcp_value_source
<valtype
> *s
;
1855 for (s
= val
->sources
; s
; s
= s
->next
)
1856 if (s
->cs
== cs
&& s
->val
== src_val
)
1862 val
->add_source (cs
, src_val
, src_idx
, offset
);
1866 if (!unlimited
&& values_count
== opt_for_fn (cs
->caller
->decl
,
1867 param_ipa_cp_value_list_size
))
1869 /* We can only free sources, not the values themselves, because sources
1870 of other values in this SCC might point to them. */
1871 for (val
= values
; val
; val
= val
->next
)
1873 while (val
->sources
)
1875 ipcp_value_source
<valtype
> *src
= val
->sources
;
1876 val
->sources
= src
->next
;
1877 ipcp_sources_pool
.remove ((ipcp_value_source
<tree
>*)src
);
1881 return set_to_bottom ();
1885 val
= allocate_and_init_ipcp_value (newval
);
1886 val
->add_source (cs
, src_val
, src_idx
, offset
);
1889 /* Add the new value to end of value list, which can reduce iterations
1890 of propagation stage for recursive function. */
1892 last_val
->next
= val
;
1902 /* Return true, if a ipcp_value VAL is orginated from parameter value of
1903 self-feeding recursive function via some kind of pass-through jump
1907 self_recursively_generated_p (ipcp_value
<tree
> *val
)
1909 class ipa_node_params
*info
= NULL
;
1911 for (ipcp_value_source
<tree
> *src
= val
->sources
; src
; src
= src
->next
)
1913 cgraph_edge
*cs
= src
->cs
;
1915 if (!src
->val
|| cs
->caller
!= cs
->callee
->function_symbol ())
1918 if (src
->val
== val
)
1922 info
= IPA_NODE_REF (cs
->caller
);
1924 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
,
1926 ipcp_lattice
<tree
> *src_lat
;
1927 ipcp_value
<tree
> *src_val
;
1929 if (src
->offset
== -1)
1930 src_lat
= &plats
->itself
;
1933 struct ipcp_agg_lattice
*src_aglat
;
1935 for (src_aglat
= plats
->aggs
; src_aglat
; src_aglat
= src_aglat
->next
)
1936 if (src_aglat
->offset
== src
->offset
)
1942 src_lat
= src_aglat
;
1945 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1956 /* A helper function that returns result of operation specified by OPCODE on
1957 the value of SRC_VAL. If non-NULL, OPND1_TYPE is expected type for the
1958 value of SRC_VAL. If the operation is binary, OPND2 is a constant value
1959 acting as its second operand. If non-NULL, RES_TYPE is expected type of
1963 get_val_across_arith_op (enum tree_code opcode
,
1966 ipcp_value
<tree
> *src_val
,
1969 tree opnd1
= src_val
->value
;
1971 /* Skip source values that is incompatible with specified type. */
1973 && !useless_type_conversion_p (opnd1_type
, TREE_TYPE (opnd1
)))
1976 return ipa_get_jf_arith_result (opcode
, opnd1
, opnd2
, res_type
);
1979 /* Propagate values through an arithmetic transformation described by a jump
1980 function associated with edge CS, taking values from SRC_LAT and putting
1981 them into DEST_LAT. OPND1_TYPE is expected type for the values in SRC_LAT.
1982 OPND2 is a constant value if transformation is a binary operation.
1983 SRC_OFFSET specifies offset in an aggregate if SRC_LAT describes lattice of
1984 a part of the aggregate. SRC_IDX is the index of the source parameter.
1985 RES_TYPE is the value type of result being propagated into. Return true if
1986 DEST_LAT changed. */
1989 propagate_vals_across_arith_jfunc (cgraph_edge
*cs
,
1990 enum tree_code opcode
,
1993 ipcp_lattice
<tree
> *src_lat
,
1994 ipcp_lattice
<tree
> *dest_lat
,
1995 HOST_WIDE_INT src_offset
,
1999 ipcp_value
<tree
> *src_val
;
2002 /* Due to circular dependencies, propagating within an SCC through arithmetic
2003 transformation would create infinite number of values. But for
2004 self-feeding recursive function, we could allow propagation in a limited
2005 count, and this can enable a simple kind of recursive function versioning.
2006 For other scenario, we would just make lattices bottom. */
2007 if (opcode
!= NOP_EXPR
&& ipa_edge_within_scc (cs
))
2011 int max_recursive_depth
= opt_for_fn(cs
->caller
->decl
,
2012 param_ipa_cp_max_recursive_depth
);
2013 if (src_lat
!= dest_lat
|| max_recursive_depth
< 1)
2014 return dest_lat
->set_contains_variable ();
2016 /* No benefit if recursive execution is in low probability. */
2017 if (cs
->sreal_frequency () * 100
2018 <= ((sreal
) 1) * opt_for_fn (cs
->caller
->decl
,
2019 param_ipa_cp_min_recursive_probability
))
2020 return dest_lat
->set_contains_variable ();
2022 auto_vec
<ipcp_value
<tree
> *, 8> val_seeds
;
2024 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
2026 /* Now we do not use self-recursively generated value as propagation
2027 source, this is absolutely conservative, but could avoid explosion
2028 of lattice's value space, especially when one recursive function
2029 calls another recursive. */
2030 if (self_recursively_generated_p (src_val
))
2032 ipcp_value_source
<tree
> *s
;
2034 /* If the lattice has already been propagated for the call site,
2035 no need to do that again. */
2036 for (s
= src_val
->sources
; s
; s
= s
->next
)
2038 return dest_lat
->set_contains_variable ();
2041 val_seeds
.safe_push (src_val
);
2044 gcc_assert ((int) val_seeds
.length () <= param_ipa_cp_value_list_size
);
2046 /* Recursively generate lattice values with a limited count. */
2047 FOR_EACH_VEC_ELT (val_seeds
, i
, src_val
)
2049 for (int j
= 1; j
< max_recursive_depth
; j
++)
2051 tree cstval
= get_val_across_arith_op (opcode
, opnd1_type
, opnd2
,
2056 ret
|= dest_lat
->add_value (cstval
, cs
, src_val
, src_idx
,
2057 src_offset
, &src_val
, true);
2058 gcc_checking_assert (src_val
);
2061 ret
|= dest_lat
->set_contains_variable ();
2064 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
2066 /* Now we do not use self-recursively generated value as propagation
2067 source, otherwise it is easy to make value space of normal lattice
2069 if (self_recursively_generated_p (src_val
))
2071 ret
|= dest_lat
->set_contains_variable ();
2075 tree cstval
= get_val_across_arith_op (opcode
, opnd1_type
, opnd2
,
2078 ret
|= dest_lat
->add_value (cstval
, cs
, src_val
, src_idx
,
2081 ret
|= dest_lat
->set_contains_variable ();
2087 /* Propagate values through a pass-through jump function JFUNC associated with
2088 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
2089 is the index of the source parameter. PARM_TYPE is the type of the
2090 parameter to which the result is passed. */
2093 propagate_vals_across_pass_through (cgraph_edge
*cs
, ipa_jump_func
*jfunc
,
2094 ipcp_lattice
<tree
> *src_lat
,
2095 ipcp_lattice
<tree
> *dest_lat
, int src_idx
,
2098 return propagate_vals_across_arith_jfunc (cs
,
2099 ipa_get_jf_pass_through_operation (jfunc
),
2101 ipa_get_jf_pass_through_operand (jfunc
),
2102 src_lat
, dest_lat
, -1, src_idx
, parm_type
);
2105 /* Propagate values through an ancestor jump function JFUNC associated with
2106 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
2107 is the index of the source parameter. */
2110 propagate_vals_across_ancestor (struct cgraph_edge
*cs
,
2111 struct ipa_jump_func
*jfunc
,
2112 ipcp_lattice
<tree
> *src_lat
,
2113 ipcp_lattice
<tree
> *dest_lat
, int src_idx
)
2115 ipcp_value
<tree
> *src_val
;
2118 if (ipa_edge_within_scc (cs
))
2119 return dest_lat
->set_contains_variable ();
2121 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
2123 tree t
= ipa_get_jf_ancestor_result (jfunc
, src_val
->value
);
2126 ret
|= dest_lat
->add_value (t
, cs
, src_val
, src_idx
);
2128 ret
|= dest_lat
->set_contains_variable ();
2134 /* Propagate scalar values across jump function JFUNC that is associated with
2135 edge CS and put the values into DEST_LAT. PARM_TYPE is the type of the
2136 parameter to which the result is passed. */
2139 propagate_scalar_across_jump_function (struct cgraph_edge
*cs
,
2140 struct ipa_jump_func
*jfunc
,
2141 ipcp_lattice
<tree
> *dest_lat
,
2144 if (dest_lat
->bottom
)
2147 if (jfunc
->type
== IPA_JF_CONST
)
2149 tree val
= ipa_get_jf_constant (jfunc
);
2150 return dest_lat
->add_value (val
, cs
, NULL
, 0);
2152 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
2153 || jfunc
->type
== IPA_JF_ANCESTOR
)
2155 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2156 ipcp_lattice
<tree
> *src_lat
;
2160 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
2161 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
2163 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
2165 src_lat
= ipa_get_scalar_lat (caller_info
, src_idx
);
2166 if (src_lat
->bottom
)
2167 return dest_lat
->set_contains_variable ();
2169 /* If we would need to clone the caller and cannot, do not propagate. */
2170 if (!ipcp_versionable_function_p (cs
->caller
)
2171 && (src_lat
->contains_variable
2172 || (src_lat
->values_count
> 1)))
2173 return dest_lat
->set_contains_variable ();
2175 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
2176 ret
= propagate_vals_across_pass_through (cs
, jfunc
, src_lat
,
2177 dest_lat
, src_idx
, param_type
);
2179 ret
= propagate_vals_across_ancestor (cs
, jfunc
, src_lat
, dest_lat
,
2182 if (src_lat
->contains_variable
)
2183 ret
|= dest_lat
->set_contains_variable ();
2188 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
2189 use it for indirect inlining), we should propagate them too. */
2190 return dest_lat
->set_contains_variable ();
2193 /* Propagate scalar values across jump function JFUNC that is associated with
2194 edge CS and describes argument IDX and put the values into DEST_LAT. */
2197 propagate_context_across_jump_function (cgraph_edge
*cs
,
2198 ipa_jump_func
*jfunc
, int idx
,
2199 ipcp_lattice
<ipa_polymorphic_call_context
> *dest_lat
)
2201 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
2202 if (dest_lat
->bottom
)
2205 bool added_sth
= false;
2206 bool type_preserved
= true;
2208 ipa_polymorphic_call_context edge_ctx
, *edge_ctx_ptr
2209 = ipa_get_ith_polymorhic_call_context (args
, idx
);
2212 edge_ctx
= *edge_ctx_ptr
;
2214 if (jfunc
->type
== IPA_JF_PASS_THROUGH
2215 || jfunc
->type
== IPA_JF_ANCESTOR
)
2217 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2219 ipcp_lattice
<ipa_polymorphic_call_context
> *src_lat
;
2221 /* TODO: Once we figure out how to propagate speculations, it will
2222 probably be a good idea to switch to speculation if type_preserved is
2223 not set instead of punting. */
2224 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
2226 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
2228 type_preserved
= ipa_get_jf_pass_through_type_preserved (jfunc
);
2229 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
2233 type_preserved
= ipa_get_jf_ancestor_type_preserved (jfunc
);
2234 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
2237 src_lat
= ipa_get_poly_ctx_lat (caller_info
, src_idx
);
2238 /* If we would need to clone the caller and cannot, do not propagate. */
2239 if (!ipcp_versionable_function_p (cs
->caller
)
2240 && (src_lat
->contains_variable
2241 || (src_lat
->values_count
> 1)))
2244 ipcp_value
<ipa_polymorphic_call_context
> *src_val
;
2245 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
2247 ipa_polymorphic_call_context cur
= src_val
->value
;
2249 if (!type_preserved
)
2250 cur
.possible_dynamic_type_change (cs
->in_polymorphic_cdtor
);
2251 if (jfunc
->type
== IPA_JF_ANCESTOR
)
2252 cur
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
2253 /* TODO: In cases we know how the context is going to be used,
2254 we can improve the result by passing proper OTR_TYPE. */
2255 cur
.combine_with (edge_ctx
);
2256 if (!cur
.useless_p ())
2258 if (src_lat
->contains_variable
2259 && !edge_ctx
.equal_to (cur
))
2260 ret
|= dest_lat
->set_contains_variable ();
2261 ret
|= dest_lat
->add_value (cur
, cs
, src_val
, src_idx
);
2270 if (!edge_ctx
.useless_p ())
2271 ret
|= dest_lat
->add_value (edge_ctx
, cs
);
2273 ret
|= dest_lat
->set_contains_variable ();
2279 /* Propagate bits across jfunc that is associated with
2280 edge cs and update dest_lattice accordingly. */
2283 propagate_bits_across_jump_function (cgraph_edge
*cs
, int idx
,
2284 ipa_jump_func
*jfunc
,
2285 ipcp_bits_lattice
*dest_lattice
)
2287 if (dest_lattice
->bottom_p ())
2290 enum availability availability
;
2291 cgraph_node
*callee
= cs
->callee
->function_symbol (&availability
);
2292 class ipa_node_params
*callee_info
= IPA_NODE_REF (callee
);
2293 tree parm_type
= ipa_get_type (callee_info
, idx
);
2295 /* For K&R C programs, ipa_get_type() could return NULL_TREE. Avoid the
2296 transform for these cases. Similarly, we can have bad type mismatches
2297 with LTO, avoid doing anything with those too. */
2299 || (!INTEGRAL_TYPE_P (parm_type
) && !POINTER_TYPE_P (parm_type
)))
2301 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2302 fprintf (dump_file
, "Setting dest_lattice to bottom, because type of "
2303 "param %i of %s is NULL or unsuitable for bits propagation\n",
2304 idx
, cs
->callee
->dump_name ());
2306 return dest_lattice
->set_to_bottom ();
2309 unsigned precision
= TYPE_PRECISION (parm_type
);
2310 signop sgn
= TYPE_SIGN (parm_type
);
2312 if (jfunc
->type
== IPA_JF_PASS_THROUGH
2313 || jfunc
->type
== IPA_JF_ANCESTOR
)
2315 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2316 tree operand
= NULL_TREE
;
2317 enum tree_code code
;
2320 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
2322 code
= ipa_get_jf_pass_through_operation (jfunc
);
2323 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
2324 if (code
!= NOP_EXPR
)
2325 operand
= ipa_get_jf_pass_through_operand (jfunc
);
2329 code
= POINTER_PLUS_EXPR
;
2330 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
2331 unsigned HOST_WIDE_INT offset
= ipa_get_jf_ancestor_offset (jfunc
) / BITS_PER_UNIT
;
2332 operand
= build_int_cstu (size_type_node
, offset
);
2335 class ipcp_param_lattices
*src_lats
2336 = ipa_get_parm_lattices (caller_info
, src_idx
);
2338 /* Try to propagate bits if src_lattice is bottom, but jfunc is known.
2344 Assume lattice for x is bottom, however we can still propagate
2345 result of x & 0xff == 0xff, which gets computed during ccp1 pass
2346 and we store it in jump function during analysis stage. */
2348 if (src_lats
->bits_lattice
.bottom_p ()
2350 return dest_lattice
->meet_with (jfunc
->bits
->value
, jfunc
->bits
->mask
,
2353 return dest_lattice
->meet_with (src_lats
->bits_lattice
, precision
, sgn
,
2357 else if (jfunc
->type
== IPA_JF_ANCESTOR
)
2358 return dest_lattice
->set_to_bottom ();
2359 else if (jfunc
->bits
)
2360 return dest_lattice
->meet_with (jfunc
->bits
->value
, jfunc
->bits
->mask
,
2363 return dest_lattice
->set_to_bottom ();
2366 /* Propagate value range across jump function JFUNC that is associated with
2367 edge CS with param of callee of PARAM_TYPE and update DEST_PLATS
2371 propagate_vr_across_jump_function (cgraph_edge
*cs
, ipa_jump_func
*jfunc
,
2372 class ipcp_param_lattices
*dest_plats
,
2375 ipcp_vr_lattice
*dest_lat
= &dest_plats
->m_value_range
;
2377 if (dest_lat
->bottom_p ())
2381 || (!INTEGRAL_TYPE_P (param_type
)
2382 && !POINTER_TYPE_P (param_type
)))
2383 return dest_lat
->set_to_bottom ();
2385 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
2387 enum tree_code operation
= ipa_get_jf_pass_through_operation (jfunc
);
2388 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2389 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
2390 class ipcp_param_lattices
*src_lats
2391 = ipa_get_parm_lattices (caller_info
, src_idx
);
2392 tree operand_type
= ipa_get_type (caller_info
, src_idx
);
2394 if (src_lats
->m_value_range
.bottom_p ())
2395 return dest_lat
->set_to_bottom ();
2398 if (TREE_CODE_CLASS (operation
) == tcc_unary
)
2399 ipa_vr_operation_and_type_effects (&vr
,
2400 &src_lats
->m_value_range
.m_vr
,
2401 operation
, param_type
,
2403 /* A crude way to prevent unbounded number of value range updates
2404 in SCC components. We should allow limited number of updates within
2406 else if (!ipa_edge_within_scc (cs
))
2408 tree op
= ipa_get_jf_pass_through_operand (jfunc
);
2409 value_range
op_vr (op
, op
);
2410 value_range op_res
,res
;
2412 range_fold_binary_expr (&op_res
, operation
, operand_type
,
2413 &src_lats
->m_value_range
.m_vr
, &op_vr
);
2414 ipa_vr_operation_and_type_effects (&vr
,
2416 NOP_EXPR
, param_type
,
2419 if (!vr
.undefined_p () && !vr
.varying_p ())
2424 if (ipa_vr_operation_and_type_effects (&jvr
, jfunc
->m_vr
,
2427 jfunc
->m_vr
->type ()))
2430 return dest_lat
->meet_with (&vr
);
2433 else if (jfunc
->type
== IPA_JF_CONST
)
2435 tree val
= ipa_get_jf_constant (jfunc
);
2436 if (TREE_CODE (val
) == INTEGER_CST
)
2438 val
= fold_convert (param_type
, val
);
2439 if (TREE_OVERFLOW_P (val
))
2440 val
= drop_tree_overflow (val
);
2442 value_range
tmpvr (val
, val
);
2443 return dest_lat
->meet_with (&tmpvr
);
2449 && ipa_vr_operation_and_type_effects (&vr
, jfunc
->m_vr
, NOP_EXPR
,
2451 jfunc
->m_vr
->type ()))
2452 return dest_lat
->meet_with (&vr
);
2454 return dest_lat
->set_to_bottom ();
2457 /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
2458 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
2459 other cases, return false). If there are no aggregate items, set
2460 aggs_by_ref to NEW_AGGS_BY_REF. */
2463 set_check_aggs_by_ref (class ipcp_param_lattices
*dest_plats
,
2464 bool new_aggs_by_ref
)
2466 if (dest_plats
->aggs
)
2468 if (dest_plats
->aggs_by_ref
!= new_aggs_by_ref
)
2470 set_agg_lats_to_bottom (dest_plats
);
2475 dest_plats
->aggs_by_ref
= new_aggs_by_ref
;
2479 /* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
2480 already existing lattice for the given OFFSET and SIZE, marking all skipped
2481 lattices as containing variable and checking for overlaps. If there is no
2482 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
2483 it with offset, size and contains_variable to PRE_EXISTING, and return true,
2484 unless there are too many already. If there are two many, return false. If
2485 there are overlaps turn whole DEST_PLATS to bottom and return false. If any
2486 skipped lattices were newly marked as containing variable, set *CHANGE to
2487 true. MAX_AGG_ITEMS is the maximum number of lattices. */
2490 merge_agg_lats_step (class ipcp_param_lattices
*dest_plats
,
2491 HOST_WIDE_INT offset
, HOST_WIDE_INT val_size
,
2492 struct ipcp_agg_lattice
***aglat
,
2493 bool pre_existing
, bool *change
, int max_agg_items
)
2495 gcc_checking_assert (offset
>= 0);
2497 while (**aglat
&& (**aglat
)->offset
< offset
)
2499 if ((**aglat
)->offset
+ (**aglat
)->size
> offset
)
2501 set_agg_lats_to_bottom (dest_plats
);
2504 *change
|= (**aglat
)->set_contains_variable ();
2505 *aglat
= &(**aglat
)->next
;
2508 if (**aglat
&& (**aglat
)->offset
== offset
)
2510 if ((**aglat
)->size
!= val_size
)
2512 set_agg_lats_to_bottom (dest_plats
);
2515 gcc_assert (!(**aglat
)->next
2516 || (**aglat
)->next
->offset
>= offset
+ val_size
);
2521 struct ipcp_agg_lattice
*new_al
;
2523 if (**aglat
&& (**aglat
)->offset
< offset
+ val_size
)
2525 set_agg_lats_to_bottom (dest_plats
);
2528 if (dest_plats
->aggs_count
== max_agg_items
)
2530 dest_plats
->aggs_count
++;
2531 new_al
= ipcp_agg_lattice_pool
.allocate ();
2532 memset (new_al
, 0, sizeof (*new_al
));
2534 new_al
->offset
= offset
;
2535 new_al
->size
= val_size
;
2536 new_al
->contains_variable
= pre_existing
;
2538 new_al
->next
= **aglat
;
2544 /* Set all AGLAT and all other aggregate lattices reachable by next pointers as
2545 containing an unknown value. */
2548 set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice
*aglat
)
2553 ret
|= aglat
->set_contains_variable ();
2554 aglat
= aglat
->next
;
2559 /* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
2560 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source
2561 parameter used for lattice value sources. Return true if DEST_PLATS changed
2565 merge_aggregate_lattices (struct cgraph_edge
*cs
,
2566 class ipcp_param_lattices
*dest_plats
,
2567 class ipcp_param_lattices
*src_plats
,
2568 int src_idx
, HOST_WIDE_INT offset_delta
)
2570 bool pre_existing
= dest_plats
->aggs
!= NULL
;
2571 struct ipcp_agg_lattice
**dst_aglat
;
2574 if (set_check_aggs_by_ref (dest_plats
, src_plats
->aggs_by_ref
))
2576 if (src_plats
->aggs_bottom
)
2577 return set_agg_lats_contain_variable (dest_plats
);
2578 if (src_plats
->aggs_contain_variable
)
2579 ret
|= set_agg_lats_contain_variable (dest_plats
);
2580 dst_aglat
= &dest_plats
->aggs
;
2582 int max_agg_items
= opt_for_fn (cs
->callee
->function_symbol ()->decl
,
2583 param_ipa_max_agg_items
);
2584 for (struct ipcp_agg_lattice
*src_aglat
= src_plats
->aggs
;
2586 src_aglat
= src_aglat
->next
)
2588 HOST_WIDE_INT new_offset
= src_aglat
->offset
- offset_delta
;
2592 if (merge_agg_lats_step (dest_plats
, new_offset
, src_aglat
->size
,
2593 &dst_aglat
, pre_existing
, &ret
, max_agg_items
))
2595 struct ipcp_agg_lattice
*new_al
= *dst_aglat
;
2597 dst_aglat
= &(*dst_aglat
)->next
;
2598 if (src_aglat
->bottom
)
2600 ret
|= new_al
->set_contains_variable ();
2603 if (src_aglat
->contains_variable
)
2604 ret
|= new_al
->set_contains_variable ();
2605 for (ipcp_value
<tree
> *val
= src_aglat
->values
;
2608 ret
|= new_al
->add_value (val
->value
, cs
, val
, src_idx
,
2611 else if (dest_plats
->aggs_bottom
)
2614 ret
|= set_chain_of_aglats_contains_variable (*dst_aglat
);
2618 /* Determine whether there is anything to propagate FROM SRC_PLATS through a
2619 pass-through JFUNC and if so, whether it has conform and conforms to the
2620 rules about propagating values passed by reference. */
2623 agg_pass_through_permissible_p (class ipcp_param_lattices
*src_plats
,
2624 struct ipa_jump_func
*jfunc
)
2626 return src_plats
->aggs
2627 && (!src_plats
->aggs_by_ref
2628 || ipa_get_jf_pass_through_agg_preserved (jfunc
));
2631 /* Propagate values through ITEM, jump function for a part of an aggregate,
2632 into corresponding aggregate lattice AGLAT. CS is the call graph edge
2633 associated with the jump function. Return true if AGLAT changed in any
2637 propagate_aggregate_lattice (struct cgraph_edge
*cs
,
2638 struct ipa_agg_jf_item
*item
,
2639 struct ipcp_agg_lattice
*aglat
)
2641 class ipa_node_params
*caller_info
;
2642 class ipcp_param_lattices
*src_plats
;
2643 struct ipcp_lattice
<tree
> *src_lat
;
2644 HOST_WIDE_INT src_offset
;
2649 if (item
->jftype
== IPA_JF_CONST
)
2651 tree value
= item
->value
.constant
;
2653 gcc_checking_assert (is_gimple_ip_invariant (value
));
2654 return aglat
->add_value (value
, cs
, NULL
, 0);
2657 gcc_checking_assert (item
->jftype
== IPA_JF_PASS_THROUGH
2658 || item
->jftype
== IPA_JF_LOAD_AGG
);
2660 caller_info
= IPA_NODE_REF (cs
->caller
);
2661 src_idx
= item
->value
.pass_through
.formal_id
;
2662 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2664 if (item
->jftype
== IPA_JF_PASS_THROUGH
)
2666 load_type
= NULL_TREE
;
2667 src_lat
= &src_plats
->itself
;
2672 HOST_WIDE_INT load_offset
= item
->value
.load_agg
.offset
;
2673 struct ipcp_agg_lattice
*src_aglat
;
2675 for (src_aglat
= src_plats
->aggs
; src_aglat
; src_aglat
= src_aglat
->next
)
2676 if (src_aglat
->offset
>= load_offset
)
2679 load_type
= item
->value
.load_agg
.type
;
2681 || src_aglat
->offset
> load_offset
2682 || src_aglat
->size
!= tree_to_shwi (TYPE_SIZE (load_type
))
2683 || src_plats
->aggs_by_ref
!= item
->value
.load_agg
.by_ref
)
2684 return aglat
->set_contains_variable ();
2686 src_lat
= src_aglat
;
2687 src_offset
= load_offset
;
2691 || (!ipcp_versionable_function_p (cs
->caller
)
2692 && !src_lat
->is_single_const ()))
2693 return aglat
->set_contains_variable ();
2695 ret
= propagate_vals_across_arith_jfunc (cs
,
2696 item
->value
.pass_through
.operation
,
2698 item
->value
.pass_through
.operand
,
2704 if (src_lat
->contains_variable
)
2705 ret
|= aglat
->set_contains_variable ();
2710 /* Propagate scalar values across jump function JFUNC that is associated with
2711 edge CS and put the values into DEST_LAT. */
2714 propagate_aggs_across_jump_function (struct cgraph_edge
*cs
,
2715 struct ipa_jump_func
*jfunc
,
2716 class ipcp_param_lattices
*dest_plats
)
2720 if (dest_plats
->aggs_bottom
)
2723 if (jfunc
->type
== IPA_JF_PASS_THROUGH
2724 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
2726 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2727 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
2728 class ipcp_param_lattices
*src_plats
;
2730 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2731 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
2733 /* Currently we do not produce clobber aggregate jump
2734 functions, replace with merging when we do. */
2735 gcc_assert (!jfunc
->agg
.items
);
2736 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
,
2741 else if (jfunc
->type
== IPA_JF_ANCESTOR
2742 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
2744 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2745 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
2746 class ipcp_param_lattices
*src_plats
;
2748 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2749 if (src_plats
->aggs
&& src_plats
->aggs_by_ref
)
2751 /* Currently we do not produce clobber aggregate jump
2752 functions, replace with merging when we do. */
2753 gcc_assert (!jfunc
->agg
.items
);
2754 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
, src_idx
,
2755 ipa_get_jf_ancestor_offset (jfunc
));
2757 else if (!src_plats
->aggs_by_ref
)
2758 ret
|= set_agg_lats_to_bottom (dest_plats
);
2760 ret
|= set_agg_lats_contain_variable (dest_plats
);
2764 if (jfunc
->agg
.items
)
2766 bool pre_existing
= dest_plats
->aggs
!= NULL
;
2767 struct ipcp_agg_lattice
**aglat
= &dest_plats
->aggs
;
2768 struct ipa_agg_jf_item
*item
;
2771 if (set_check_aggs_by_ref (dest_plats
, jfunc
->agg
.by_ref
))
2774 int max_agg_items
= opt_for_fn (cs
->callee
->function_symbol ()->decl
,
2775 param_ipa_max_agg_items
);
2776 FOR_EACH_VEC_ELT (*jfunc
->agg
.items
, i
, item
)
2778 HOST_WIDE_INT val_size
;
2780 if (item
->offset
< 0 || item
->jftype
== IPA_JF_UNKNOWN
)
2782 val_size
= tree_to_shwi (TYPE_SIZE (item
->type
));
2784 if (merge_agg_lats_step (dest_plats
, item
->offset
, val_size
,
2785 &aglat
, pre_existing
, &ret
, max_agg_items
))
2787 ret
|= propagate_aggregate_lattice (cs
, item
, *aglat
);
2788 aglat
= &(*aglat
)->next
;
2790 else if (dest_plats
->aggs_bottom
)
2794 ret
|= set_chain_of_aglats_contains_variable (*aglat
);
2797 ret
|= set_agg_lats_contain_variable (dest_plats
);
2802 /* Return true if on the way cfrom CS->caller to the final (non-alias and
2803 non-thunk) destination, the call passes through a thunk. */
2806 call_passes_through_thunk_p (cgraph_edge
*cs
)
2808 cgraph_node
*alias_or_thunk
= cs
->callee
;
2809 while (alias_or_thunk
->alias
)
2810 alias_or_thunk
= alias_or_thunk
->get_alias_target ();
2811 return alias_or_thunk
->thunk
.thunk_p
;
2814 /* Propagate constants from the caller to the callee of CS. INFO describes the
2818 propagate_constants_across_call (struct cgraph_edge
*cs
)
2820 class ipa_node_params
*callee_info
;
2821 enum availability availability
;
2822 cgraph_node
*callee
;
2823 class ipa_edge_args
*args
;
2825 int i
, args_count
, parms_count
;
2827 callee
= cs
->callee
->function_symbol (&availability
);
2828 if (!callee
->definition
)
2830 gcc_checking_assert (callee
->has_gimple_body_p ());
2831 callee_info
= IPA_NODE_REF (callee
);
2835 args
= IPA_EDGE_REF (cs
);
2836 parms_count
= ipa_get_param_count (callee_info
);
2837 if (parms_count
== 0)
2840 || !opt_for_fn (cs
->caller
->decl
, flag_ipa_cp
)
2841 || !opt_for_fn (cs
->caller
->decl
, optimize
))
2843 for (i
= 0; i
< parms_count
; i
++)
2844 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
2848 args_count
= ipa_get_cs_argument_count (args
);
2850 /* If this call goes through a thunk we must not propagate to the first (0th)
2851 parameter. However, we might need to uncover a thunk from below a series
2852 of aliases first. */
2853 if (call_passes_through_thunk_p (cs
))
2855 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
2862 for (; (i
< args_count
) && (i
< parms_count
); i
++)
2864 struct ipa_jump_func
*jump_func
= ipa_get_ith_jump_func (args
, i
);
2865 class ipcp_param_lattices
*dest_plats
;
2866 tree param_type
= ipa_get_type (callee_info
, i
);
2868 dest_plats
= ipa_get_parm_lattices (callee_info
, i
);
2869 if (availability
== AVAIL_INTERPOSABLE
)
2870 ret
|= set_all_contains_variable (dest_plats
);
2873 ret
|= propagate_scalar_across_jump_function (cs
, jump_func
,
2874 &dest_plats
->itself
,
2876 ret
|= propagate_context_across_jump_function (cs
, jump_func
, i
,
2877 &dest_plats
->ctxlat
);
2879 |= propagate_bits_across_jump_function (cs
, i
, jump_func
,
2880 &dest_plats
->bits_lattice
);
2881 ret
|= propagate_aggs_across_jump_function (cs
, jump_func
,
2883 if (opt_for_fn (callee
->decl
, flag_ipa_vrp
))
2884 ret
|= propagate_vr_across_jump_function (cs
, jump_func
,
2885 dest_plats
, param_type
);
2887 ret
|= dest_plats
->m_value_range
.set_to_bottom ();
2890 for (; i
< parms_count
; i
++)
2891 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
, i
));
2896 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
2897 KNOWN_CONTEXTS, KNOWN_AGGS or AGG_REPS return the destination. The latter
2898 three can be NULL. If AGG_REPS is not NULL, KNOWN_AGGS is ignored. */
2901 ipa_get_indirect_edge_target_1 (struct cgraph_edge
*ie
,
2902 vec
<tree
> known_csts
,
2903 vec
<ipa_polymorphic_call_context
> known_contexts
,
2904 vec
<ipa_agg_value_set
> known_aggs
,
2905 struct ipa_agg_replacement_value
*agg_reps
,
2908 int param_index
= ie
->indirect_info
->param_index
;
2909 HOST_WIDE_INT anc_offset
;
2913 *speculative
= false;
2915 if (param_index
== -1)
2918 if (!ie
->indirect_info
->polymorphic
)
2922 if (ie
->indirect_info
->agg_contents
)
2925 if (agg_reps
&& ie
->indirect_info
->guaranteed_unmodified
)
2929 if (agg_reps
->index
== param_index
2930 && agg_reps
->offset
== ie
->indirect_info
->offset
2931 && agg_reps
->by_ref
== ie
->indirect_info
->by_ref
)
2933 t
= agg_reps
->value
;
2936 agg_reps
= agg_reps
->next
;
2941 struct ipa_agg_value_set
*agg
;
2942 if (known_aggs
.length () > (unsigned int) param_index
)
2943 agg
= &known_aggs
[param_index
];
2946 bool from_global_constant
;
2947 t
= ipa_find_agg_cst_for_param (agg
,
2948 (unsigned) param_index
2949 < known_csts
.length ()
2950 ? known_csts
[param_index
]
2952 ie
->indirect_info
->offset
,
2953 ie
->indirect_info
->by_ref
,
2954 &from_global_constant
);
2956 && !from_global_constant
2957 && !ie
->indirect_info
->guaranteed_unmodified
)
2961 else if ((unsigned) param_index
< known_csts
.length ())
2962 t
= known_csts
[param_index
];
2965 && TREE_CODE (t
) == ADDR_EXPR
2966 && TREE_CODE (TREE_OPERAND (t
, 0)) == FUNCTION_DECL
)
2967 return TREE_OPERAND (t
, 0);
2972 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize
))
2975 gcc_assert (!ie
->indirect_info
->agg_contents
);
2976 anc_offset
= ie
->indirect_info
->offset
;
2980 /* Try to work out value of virtual table pointer value in replacements. */
2981 if (!t
&& agg_reps
&& !ie
->indirect_info
->by_ref
)
2985 if (agg_reps
->index
== param_index
2986 && agg_reps
->offset
== ie
->indirect_info
->offset
2987 && agg_reps
->by_ref
)
2989 t
= agg_reps
->value
;
2992 agg_reps
= agg_reps
->next
;
2996 /* Try to work out value of virtual table pointer value in known
2997 aggregate values. */
2998 if (!t
&& known_aggs
.length () > (unsigned int) param_index
2999 && !ie
->indirect_info
->by_ref
)
3001 struct ipa_agg_value_set
*agg
= &known_aggs
[param_index
];
3002 t
= ipa_find_agg_cst_for_param (agg
,
3003 (unsigned) param_index
3004 < known_csts
.length ()
3005 ? known_csts
[param_index
] : NULL
,
3006 ie
->indirect_info
->offset
, true);
3009 /* If we found the virtual table pointer, lookup the target. */
3013 unsigned HOST_WIDE_INT offset
;
3014 if (vtable_pointer_value_to_vtable (t
, &vtable
, &offset
))
3017 target
= gimple_get_virt_method_for_vtable (ie
->indirect_info
->otr_token
,
3018 vtable
, offset
, &can_refer
);
3022 || fndecl_built_in_p (target
, BUILT_IN_UNREACHABLE
)
3023 || !possible_polymorphic_call_target_p
3024 (ie
, cgraph_node::get (target
)))
3026 /* Do not speculate builtin_unreachable, it is stupid! */
3027 if (ie
->indirect_info
->vptr_changed
)
3029 target
= ipa_impossible_devirt_target (ie
, target
);
3031 *speculative
= ie
->indirect_info
->vptr_changed
;
3038 /* Do we know the constant value of pointer? */
3039 if (!t
&& (unsigned) param_index
< known_csts
.length ())
3040 t
= known_csts
[param_index
];
3042 gcc_checking_assert (!t
|| TREE_CODE (t
) != TREE_BINFO
);
3044 ipa_polymorphic_call_context context
;
3045 if (known_contexts
.length () > (unsigned int) param_index
)
3047 context
= known_contexts
[param_index
];
3048 context
.offset_by (anc_offset
);
3049 if (ie
->indirect_info
->vptr_changed
)
3050 context
.possible_dynamic_type_change (ie
->in_polymorphic_cdtor
,
3051 ie
->indirect_info
->otr_type
);
3054 ipa_polymorphic_call_context ctx2
= ipa_polymorphic_call_context
3055 (t
, ie
->indirect_info
->otr_type
, anc_offset
);
3056 if (!ctx2
.useless_p ())
3057 context
.combine_with (ctx2
, ie
->indirect_info
->otr_type
);
3062 context
= ipa_polymorphic_call_context (t
, ie
->indirect_info
->otr_type
,
3064 if (ie
->indirect_info
->vptr_changed
)
3065 context
.possible_dynamic_type_change (ie
->in_polymorphic_cdtor
,
3066 ie
->indirect_info
->otr_type
);
3071 vec
<cgraph_node
*>targets
;
3074 targets
= possible_polymorphic_call_targets
3075 (ie
->indirect_info
->otr_type
,
3076 ie
->indirect_info
->otr_token
,
3078 if (!final
|| targets
.length () > 1)
3080 struct cgraph_node
*node
;
3083 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize_speculatively
)
3084 || ie
->speculative
|| !ie
->maybe_hot_p ())
3086 node
= try_speculative_devirtualization (ie
->indirect_info
->otr_type
,
3087 ie
->indirect_info
->otr_token
,
3091 *speculative
= true;
3092 target
= node
->decl
;
3099 *speculative
= false;
3100 if (targets
.length () == 1)
3101 target
= targets
[0]->decl
;
3103 target
= ipa_impossible_devirt_target (ie
, NULL_TREE
);
3106 if (target
&& !possible_polymorphic_call_target_p (ie
,
3107 cgraph_node::get (target
)))
3111 target
= ipa_impossible_devirt_target (ie
, target
);
3118 /* If an indirect edge IE can be turned into a direct one based on KNOWN_CSTS,
3119 KNOWN_CONTEXTS (which can be vNULL) or KNOWN_AGGS (which also can be vNULL)
3120 return the destination. */
3123 ipa_get_indirect_edge_target (struct cgraph_edge
*ie
,
3124 vec
<tree
> known_csts
,
3125 vec
<ipa_polymorphic_call_context
> known_contexts
,
3126 vec
<ipa_agg_value_set
> known_aggs
,
3129 return ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
3130 known_aggs
, NULL
, speculative
);
3133 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
3134 and KNOWN_CONTEXTS. */
3137 devirtualization_time_bonus (struct cgraph_node
*node
,
3138 vec
<tree
> known_csts
,
3139 vec
<ipa_polymorphic_call_context
> known_contexts
,
3140 vec
<ipa_agg_value_set
> known_aggs
)
3142 struct cgraph_edge
*ie
;
3145 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
3147 struct cgraph_node
*callee
;
3148 class ipa_fn_summary
*isummary
;
3149 enum availability avail
;
3153 target
= ipa_get_indirect_edge_target (ie
, known_csts
, known_contexts
,
3154 known_aggs
, &speculative
);
3158 /* Only bare minimum benefit for clearly un-inlineable targets. */
3160 callee
= cgraph_node::get (target
);
3161 if (!callee
|| !callee
->definition
)
3163 callee
= callee
->function_symbol (&avail
);
3164 if (avail
< AVAIL_AVAILABLE
)
3166 isummary
= ipa_fn_summaries
->get (callee
);
3167 if (!isummary
|| !isummary
->inlinable
)
3170 int size
= ipa_size_summaries
->get (callee
)->size
;
3171 /* FIXME: The values below need re-considering and perhaps also
3172 integrating into the cost metrics, at lest in some very basic way. */
3173 int max_inline_insns_auto
3174 = opt_for_fn (callee
->decl
, param_max_inline_insns_auto
);
3175 if (size
<= max_inline_insns_auto
/ 4)
3176 res
+= 31 / ((int)speculative
+ 1);
3177 else if (size
<= max_inline_insns_auto
/ 2)
3178 res
+= 15 / ((int)speculative
+ 1);
3179 else if (size
<= max_inline_insns_auto
3180 || DECL_DECLARED_INLINE_P (callee
->decl
))
3181 res
+= 7 / ((int)speculative
+ 1);
3187 /* Return time bonus incurred because of HINTS. */
3190 hint_time_bonus (cgraph_node
*node
, ipa_hints hints
)
3193 if (hints
& (INLINE_HINT_loop_iterations
| INLINE_HINT_loop_stride
))
3194 result
+= opt_for_fn (node
->decl
, param_ipa_cp_loop_hint_bonus
);
3198 /* If there is a reason to penalize the function described by INFO in the
3199 cloning goodness evaluation, do so. */
3201 static inline int64_t
3202 incorporate_penalties (cgraph_node
*node
, ipa_node_params
*info
,
3205 if (info
->node_within_scc
&& !info
->node_is_self_scc
)
3206 evaluation
= (evaluation
3207 * (100 - opt_for_fn (node
->decl
,
3208 param_ipa_cp_recursion_penalty
))) / 100;
3210 if (info
->node_calling_single_call
)
3211 evaluation
= (evaluation
3212 * (100 - opt_for_fn (node
->decl
,
3213 param_ipa_cp_single_call_penalty
)))
3219 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
3220 and SIZE_COST and with the sum of frequencies of incoming edges to the
3221 potential new clone in FREQUENCIES. */
3224 good_cloning_opportunity_p (struct cgraph_node
*node
, int time_benefit
,
3225 int freq_sum
, profile_count count_sum
, int size_cost
)
3227 if (time_benefit
== 0
3228 || !opt_for_fn (node
->decl
, flag_ipa_cp_clone
)
3229 || node
->optimize_for_size_p ())
3232 gcc_assert (size_cost
> 0);
3234 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3235 int eval_threshold
= opt_for_fn (node
->decl
, param_ipa_cp_eval_threshold
);
3236 if (max_count
> profile_count::zero ())
3238 int factor
= RDIV (count_sum
.probability_in
3239 (max_count
).to_reg_br_prob_base ()
3240 * 1000, REG_BR_PROB_BASE
);
3241 int64_t evaluation
= (((int64_t) time_benefit
* factor
)
3243 evaluation
= incorporate_penalties (node
, info
, evaluation
);
3245 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3247 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
3248 "size: %i, count_sum: ", time_benefit
, size_cost
);
3249 count_sum
.dump (dump_file
);
3250 fprintf (dump_file
, "%s%s) -> evaluation: " "%" PRId64
3251 ", threshold: %i\n",
3252 info
->node_within_scc
3253 ? (info
->node_is_self_scc
? ", self_scc" : ", scc") : "",
3254 info
->node_calling_single_call
? ", single_call" : "",
3255 evaluation
, eval_threshold
);
3258 return evaluation
>= eval_threshold
;
3262 int64_t evaluation
= (((int64_t) time_benefit
* freq_sum
)
3264 evaluation
= incorporate_penalties (node
, info
, evaluation
);
3266 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3267 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
3268 "size: %i, freq_sum: %i%s%s) -> evaluation: "
3269 "%" PRId64
", threshold: %i\n",
3270 time_benefit
, size_cost
, freq_sum
,
3271 info
->node_within_scc
3272 ? (info
->node_is_self_scc
? ", self_scc" : ", scc") : "",
3273 info
->node_calling_single_call
? ", single_call" : "",
3274 evaluation
, eval_threshold
);
3276 return evaluation
>= eval_threshold
;
3280 /* Return all context independent values from aggregate lattices in PLATS in a
3281 vector. Return NULL if there are none. */
3283 static vec
<ipa_agg_value
>
3284 context_independent_aggregate_values (class ipcp_param_lattices
*plats
)
3286 vec
<ipa_agg_value
> res
= vNULL
;
3288 if (plats
->aggs_bottom
3289 || plats
->aggs_contain_variable
3290 || plats
->aggs_count
== 0)
3293 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
;
3295 aglat
= aglat
->next
)
3296 if (aglat
->is_single_const ())
3298 struct ipa_agg_value item
;
3299 item
.offset
= aglat
->offset
;
3300 item
.value
= aglat
->values
->value
;
3301 res
.safe_push (item
);
3306 /* Allocate KNOWN_CSTS, KNOWN_CONTEXTS and, if non-NULL, KNOWN_AGGS and
3307 populate them with values of parameters that are known independent of the
3308 context. INFO describes the function. If REMOVABLE_PARAMS_COST is
3309 non-NULL, the movement cost of all removable parameters will be stored in
3313 gather_context_independent_values (class ipa_node_params
*info
,
3314 vec
<tree
> *known_csts
,
3315 vec
<ipa_polymorphic_call_context
>
3317 vec
<ipa_agg_value_set
> *known_aggs
,
3318 int *removable_params_cost
)
3320 int i
, count
= ipa_get_param_count (info
);
3323 known_csts
->create (0);
3324 known_contexts
->create (0);
3325 known_csts
->safe_grow_cleared (count
);
3326 known_contexts
->safe_grow_cleared (count
);
3329 known_aggs
->create (0);
3330 known_aggs
->safe_grow_cleared (count
);
3333 if (removable_params_cost
)
3334 *removable_params_cost
= 0;
3336 for (i
= 0; i
< count
; i
++)
3338 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3339 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
3341 if (lat
->is_single_const ())
3343 ipcp_value
<tree
> *val
= lat
->values
;
3344 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
3345 (*known_csts
)[i
] = val
->value
;
3346 if (removable_params_cost
)
3347 *removable_params_cost
3348 += estimate_move_cost (TREE_TYPE (val
->value
), false);
3351 else if (removable_params_cost
3352 && !ipa_is_param_used (info
, i
))
3353 *removable_params_cost
3354 += ipa_get_param_move_cost (info
, i
);
3356 if (!ipa_is_param_used (info
, i
))
3359 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
3360 /* Do not account known context as reason for cloning. We can see
3361 if it permits devirtualization. */
3362 if (ctxlat
->is_single_const ())
3363 (*known_contexts
)[i
] = ctxlat
->values
->value
;
3367 vec
<ipa_agg_value
> agg_items
;
3368 struct ipa_agg_value_set
*agg
;
3370 agg_items
= context_independent_aggregate_values (plats
);
3371 agg
= &(*known_aggs
)[i
];
3372 agg
->items
= agg_items
;
3373 agg
->by_ref
= plats
->aggs_by_ref
;
3374 ret
|= !agg_items
.is_empty ();
3381 /* Perform time and size measurement of NODE with the context given in
3382 KNOWN_CSTS, KNOWN_CONTEXTS and KNOWN_AGGS, calculate the benefit and cost
3383 given BASE_TIME of the node without specialization, REMOVABLE_PARAMS_COST of
3384 all context-independent removable parameters and EST_MOVE_COST of estimated
3385 movement of the considered parameter and store it into VAL. */
3388 perform_estimation_of_a_value (cgraph_node
*node
, vec
<tree
> known_csts
,
3389 vec
<ipa_polymorphic_call_context
> known_contexts
,
3390 vec
<ipa_agg_value_set
> known_aggs
,
3391 int removable_params_cost
,
3392 int est_move_cost
, ipcp_value_base
*val
)
3394 int size
, time_benefit
;
3395 sreal time
, base_time
;
3398 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
3399 known_aggs
, &size
, &time
,
3400 &base_time
, &hints
);
3402 if (base_time
> 65535)
3405 /* Extern inline functions have no cloning local time benefits because they
3406 will be inlined anyway. The only reason to clone them is if it enables
3407 optimization in any of the functions they call. */
3408 if (DECL_EXTERNAL (node
->decl
) && DECL_DECLARED_INLINE_P (node
->decl
))
3411 time_benefit
= base_time
.to_int ()
3412 + devirtualization_time_bonus (node
, known_csts
, known_contexts
,
3414 + hint_time_bonus (node
, hints
)
3415 + removable_params_cost
+ est_move_cost
;
3417 gcc_checking_assert (size
>=0);
3418 /* The inliner-heuristics based estimates may think that in certain
3419 contexts some functions do not have any size at all but we want
3420 all specializations to have at least a tiny cost, not least not to
3425 val
->local_time_benefit
= time_benefit
;
3426 val
->local_size_cost
= size
;
3429 /* Get the overall limit oof growth based on parameters extracted from growth.
3430 it does not really make sense to mix functions with different overall growth
3431 limits but it is possible and if it happens, we do not want to select one
3435 get_max_overall_size (cgraph_node
*node
)
3437 long max_new_size
= orig_overall_size
;
3438 long large_unit
= opt_for_fn (node
->decl
, param_large_unit_insns
);
3439 if (max_new_size
< large_unit
)
3440 max_new_size
= large_unit
;
3441 int unit_growth
= opt_for_fn (node
->decl
, param_ipa_cp_unit_growth
);
3442 max_new_size
+= max_new_size
* unit_growth
/ 100 + 1;
3443 return max_new_size
;
3446 /* Iterate over known values of parameters of NODE and estimate the local
3447 effects in terms of time and size they have. */
3450 estimate_local_effects (struct cgraph_node
*node
)
3452 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3453 int i
, count
= ipa_get_param_count (info
);
3454 vec
<tree
> known_csts
;
3455 vec
<ipa_polymorphic_call_context
> known_contexts
;
3456 vec
<ipa_agg_value_set
> known_aggs
;
3458 int removable_params_cost
;
3460 if (!count
|| !ipcp_versionable_function_p (node
))
3463 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3464 fprintf (dump_file
, "\nEstimating effects for %s.\n", node
->dump_name ());
3466 always_const
= gather_context_independent_values (info
, &known_csts
,
3467 &known_contexts
, &known_aggs
,
3468 &removable_params_cost
);
3469 int devirt_bonus
= devirtualization_time_bonus (node
, known_csts
,
3470 known_contexts
, known_aggs
);
3471 if (always_const
|| devirt_bonus
3472 || (removable_params_cost
&& node
->can_change_signature
))
3474 struct caller_statistics stats
;
3476 sreal time
, base_time
;
3479 init_caller_stats (&stats
);
3480 node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
3482 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
3483 known_aggs
, &size
, &time
,
3484 &base_time
, &hints
);
3485 time
-= devirt_bonus
;
3486 time
-= hint_time_bonus (node
, hints
);
3487 time
-= removable_params_cost
;
3488 size
-= stats
.n_calls
* removable_params_cost
;
3491 fprintf (dump_file
, " - context independent values, size: %i, "
3492 "time_benefit: %f\n", size
, (base_time
- time
).to_double ());
3494 if (size
<= 0 || node
->local
)
3496 info
->do_clone_for_all_contexts
= true;
3499 fprintf (dump_file
, " Decided to specialize for all "
3500 "known contexts, code not going to grow.\n");
3502 else if (good_cloning_opportunity_p (node
,
3503 MIN ((base_time
- time
).to_int (),
3505 stats
.freq_sum
, stats
.count_sum
,
3508 if (size
+ overall_size
<= get_max_overall_size (node
))
3510 info
->do_clone_for_all_contexts
= true;
3511 overall_size
+= size
;
3514 fprintf (dump_file
, " Decided to specialize for all "
3515 "known contexts, growth deemed beneficial.\n");
3517 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3518 fprintf (dump_file
, " Not cloning for all contexts because "
3519 "maximum unit size would be reached with %li.\n",
3520 size
+ overall_size
);
3522 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3523 fprintf (dump_file
, " Not cloning for all contexts because "
3524 "!good_cloning_opportunity_p.\n");
3528 for (i
= 0; i
< count
; i
++)
3530 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3531 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
3532 ipcp_value
<tree
> *val
;
3539 for (val
= lat
->values
; val
; val
= val
->next
)
3541 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
3542 known_csts
[i
] = val
->value
;
3544 int emc
= estimate_move_cost (TREE_TYPE (val
->value
), true);
3545 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
3547 removable_params_cost
, emc
, val
);
3549 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3551 fprintf (dump_file
, " - estimates for value ");
3552 print_ipcp_constant_value (dump_file
, val
->value
);
3553 fprintf (dump_file
, " for ");
3554 ipa_dump_param (dump_file
, info
, i
);
3555 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
3556 val
->local_time_benefit
, val
->local_size_cost
);
3559 known_csts
[i
] = NULL_TREE
;
3562 for (i
= 0; i
< count
; i
++)
3564 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3566 if (!plats
->virt_call
)
3569 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
3570 ipcp_value
<ipa_polymorphic_call_context
> *val
;
3574 || !known_contexts
[i
].useless_p ())
3577 for (val
= ctxlat
->values
; val
; val
= val
->next
)
3579 known_contexts
[i
] = val
->value
;
3580 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
3582 removable_params_cost
, 0, val
);
3584 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3586 fprintf (dump_file
, " - estimates for polymorphic context ");
3587 print_ipcp_constant_value (dump_file
, val
->value
);
3588 fprintf (dump_file
, " for ");
3589 ipa_dump_param (dump_file
, info
, i
);
3590 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
3591 val
->local_time_benefit
, val
->local_size_cost
);
3594 known_contexts
[i
] = ipa_polymorphic_call_context ();
3597 for (i
= 0; i
< count
; i
++)
3599 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3600 struct ipa_agg_value_set
*agg
;
3601 struct ipcp_agg_lattice
*aglat
;
3603 if (plats
->aggs_bottom
|| !plats
->aggs
)
3606 agg
= &known_aggs
[i
];
3607 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3609 ipcp_value
<tree
> *val
;
3610 if (aglat
->bottom
|| !aglat
->values
3611 /* If the following is true, the one value is in known_aggs. */
3612 || (!plats
->aggs_contain_variable
3613 && aglat
->is_single_const ()))
3616 for (val
= aglat
->values
; val
; val
= val
->next
)
3618 struct ipa_agg_value item
;
3620 item
.offset
= aglat
->offset
;
3621 item
.value
= val
->value
;
3622 agg
->items
.safe_push (item
);
3624 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
3626 removable_params_cost
, 0, val
);
3628 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3630 fprintf (dump_file
, " - estimates for value ");
3631 print_ipcp_constant_value (dump_file
, val
->value
);
3632 fprintf (dump_file
, " for ");
3633 ipa_dump_param (dump_file
, info
, i
);
3634 fprintf (dump_file
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
3635 "]: time_benefit: %i, size: %i\n",
3636 plats
->aggs_by_ref
? "ref " : "",
3638 val
->local_time_benefit
, val
->local_size_cost
);
3646 known_csts
.release ();
3647 known_contexts
.release ();
3648 ipa_release_agg_values (known_aggs
);
3652 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
3653 topological sort of values. */
3655 template <typename valtype
>
3657 value_topo_info
<valtype
>::add_val (ipcp_value
<valtype
> *cur_val
)
3659 ipcp_value_source
<valtype
> *src
;
3665 cur_val
->dfs
= dfs_counter
;
3666 cur_val
->low_link
= dfs_counter
;
3668 cur_val
->topo_next
= stack
;
3670 cur_val
->on_stack
= true;
3672 for (src
= cur_val
->sources
; src
; src
= src
->next
)
3675 if (src
->val
->dfs
== 0)
3678 if (src
->val
->low_link
< cur_val
->low_link
)
3679 cur_val
->low_link
= src
->val
->low_link
;
3681 else if (src
->val
->on_stack
3682 && src
->val
->dfs
< cur_val
->low_link
)
3683 cur_val
->low_link
= src
->val
->dfs
;
3686 if (cur_val
->dfs
== cur_val
->low_link
)
3688 ipcp_value
<valtype
> *v
, *scc_list
= NULL
;
3693 stack
= v
->topo_next
;
3694 v
->on_stack
= false;
3696 v
->scc_next
= scc_list
;
3699 while (v
!= cur_val
);
3701 cur_val
->topo_next
= values_topo
;
3702 values_topo
= cur_val
;
3706 /* Add all values in lattices associated with NODE to the topological sort if
3707 they are not there yet. */
3710 add_all_node_vals_to_toposort (cgraph_node
*node
, ipa_topo_info
*topo
)
3712 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3713 int i
, count
= ipa_get_param_count (info
);
3715 for (i
= 0; i
< count
; i
++)
3717 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3718 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
3719 struct ipcp_agg_lattice
*aglat
;
3723 ipcp_value
<tree
> *val
;
3724 for (val
= lat
->values
; val
; val
= val
->next
)
3725 topo
->constants
.add_val (val
);
3728 if (!plats
->aggs_bottom
)
3729 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3732 ipcp_value
<tree
> *val
;
3733 for (val
= aglat
->values
; val
; val
= val
->next
)
3734 topo
->constants
.add_val (val
);
3737 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
3738 if (!ctxlat
->bottom
)
3740 ipcp_value
<ipa_polymorphic_call_context
> *ctxval
;
3741 for (ctxval
= ctxlat
->values
; ctxval
; ctxval
= ctxval
->next
)
3742 topo
->contexts
.add_val (ctxval
);
3747 /* One pass of constants propagation along the call graph edges, from callers
3748 to callees (requires topological ordering in TOPO), iterate over strongly
3749 connected components. */
3752 propagate_constants_topo (class ipa_topo_info
*topo
)
3756 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
3759 struct cgraph_node
*v
, *node
= topo
->order
[i
];
3760 vec
<cgraph_node
*> cycle_nodes
= ipa_get_nodes_in_cycle (node
);
3762 /* First, iteratively propagate within the strongly connected component
3763 until all lattices stabilize. */
3764 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
3765 if (v
->has_gimple_body_p ())
3767 if (opt_for_fn (v
->decl
, flag_ipa_cp
)
3768 && opt_for_fn (v
->decl
, optimize
))
3769 push_node_to_stack (topo
, v
);
3770 /* When V is not optimized, we can not push it to stack, but
3771 still we need to set all its callees lattices to bottom. */
3774 for (cgraph_edge
*cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3775 propagate_constants_across_call (cs
);
3779 v
= pop_node_from_stack (topo
);
3782 struct cgraph_edge
*cs
;
3783 class ipa_node_params
*info
= NULL
;
3784 bool self_scc
= true;
3786 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3787 if (ipa_edge_within_scc (cs
))
3789 cgraph_node
*callee
= cs
->callee
->function_symbol ();
3796 info
= IPA_NODE_REF (v
);
3797 info
->node_within_scc
= true;
3800 if (propagate_constants_across_call (cs
))
3801 push_node_to_stack (topo
, callee
);
3805 info
->node_is_self_scc
= self_scc
;
3807 v
= pop_node_from_stack (topo
);
3810 /* Afterwards, propagate along edges leading out of the SCC, calculates
3811 the local effects of the discovered constants and all valid values to
3812 their topological sort. */
3813 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
3814 if (v
->has_gimple_body_p ()
3815 && opt_for_fn (v
->decl
, flag_ipa_cp
)
3816 && opt_for_fn (v
->decl
, optimize
))
3818 struct cgraph_edge
*cs
;
3820 estimate_local_effects (v
);
3821 add_all_node_vals_to_toposort (v
, topo
);
3822 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3823 if (!ipa_edge_within_scc (cs
))
3824 propagate_constants_across_call (cs
);
3826 cycle_nodes
.release ();
3831 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
3832 the bigger one if otherwise. */
3835 safe_add (int a
, int b
)
3837 if (a
> INT_MAX
/2 || b
> INT_MAX
/2)
3838 return a
> b
? a
: b
;
3844 /* Propagate the estimated effects of individual values along the topological
3845 from the dependent values to those they depend on. */
3847 template <typename valtype
>
3849 value_topo_info
<valtype
>::propagate_effects ()
3851 ipcp_value
<valtype
> *base
;
3853 for (base
= values_topo
; base
; base
= base
->topo_next
)
3855 ipcp_value_source
<valtype
> *src
;
3856 ipcp_value
<valtype
> *val
;
3857 int time
= 0, size
= 0;
3859 for (val
= base
; val
; val
= val
->scc_next
)
3861 time
= safe_add (time
,
3862 val
->local_time_benefit
+ val
->prop_time_benefit
);
3863 size
= safe_add (size
, val
->local_size_cost
+ val
->prop_size_cost
);
3866 for (val
= base
; val
; val
= val
->scc_next
)
3867 for (src
= val
->sources
; src
; src
= src
->next
)
3869 && src
->cs
->maybe_hot_p ())
3871 src
->val
->prop_time_benefit
= safe_add (time
,
3872 src
->val
->prop_time_benefit
);
3873 src
->val
->prop_size_cost
= safe_add (size
,
3874 src
->val
->prop_size_cost
);
3880 /* Propagate constants, polymorphic contexts and their effects from the
3881 summaries interprocedurally. */
3884 ipcp_propagate_stage (class ipa_topo_info
*topo
)
3886 struct cgraph_node
*node
;
3889 fprintf (dump_file
, "\n Propagating constants:\n\n");
3891 max_count
= profile_count::uninitialized ();
3893 FOR_EACH_DEFINED_FUNCTION (node
)
3895 if (node
->has_gimple_body_p ()
3896 && opt_for_fn (node
->decl
, flag_ipa_cp
)
3897 && opt_for_fn (node
->decl
, optimize
))
3899 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3900 determine_versionability (node
, info
);
3901 info
->lattices
= XCNEWVEC (class ipcp_param_lattices
,
3902 ipa_get_param_count (info
));
3903 initialize_node_lattices (node
);
3905 ipa_size_summary
*s
= ipa_size_summaries
->get (node
);
3906 if (node
->definition
&& !node
->alias
&& s
!= NULL
)
3907 overall_size
+= s
->self_size
;
3908 max_count
= max_count
.max (node
->count
.ipa ());
3911 orig_overall_size
= overall_size
;
3914 fprintf (dump_file
, "\noverall_size: %li\n", overall_size
);
3916 propagate_constants_topo (topo
);
3918 ipcp_verify_propagated_values ();
3919 topo
->constants
.propagate_effects ();
3920 topo
->contexts
.propagate_effects ();
3924 fprintf (dump_file
, "\nIPA lattices after all propagation:\n");
3925 print_all_lattices (dump_file
, (dump_flags
& TDF_DETAILS
), true);
3929 /* Discover newly direct outgoing edges from NODE which is a new clone with
3930 known KNOWN_CSTS and make them direct. */
3933 ipcp_discover_new_direct_edges (struct cgraph_node
*node
,
3934 vec
<tree
> known_csts
,
3935 vec
<ipa_polymorphic_call_context
>
3937 struct ipa_agg_replacement_value
*aggvals
)
3939 struct cgraph_edge
*ie
, *next_ie
;
3942 for (ie
= node
->indirect_calls
; ie
; ie
= next_ie
)
3947 next_ie
= ie
->next_callee
;
3948 target
= ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
3949 vNULL
, aggvals
, &speculative
);
3952 bool agg_contents
= ie
->indirect_info
->agg_contents
;
3953 bool polymorphic
= ie
->indirect_info
->polymorphic
;
3954 int param_index
= ie
->indirect_info
->param_index
;
3955 struct cgraph_edge
*cs
= ipa_make_edge_direct_to_target (ie
, target
,
3959 if (cs
&& !agg_contents
&& !polymorphic
)
3961 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3962 int c
= ipa_get_controlled_uses (info
, param_index
);
3963 if (c
!= IPA_UNDESCRIBED_USE
)
3965 struct ipa_ref
*to_del
;
3968 ipa_set_controlled_uses (info
, param_index
, c
);
3969 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3970 fprintf (dump_file
, " controlled uses count of param "
3971 "%i bumped down to %i\n", param_index
, c
);
3973 && (to_del
= node
->find_reference (cs
->callee
, NULL
, 0)))
3975 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3976 fprintf (dump_file
, " and even removing its "
3977 "cloning-created reference\n");
3978 to_del
->remove_reference ();
3984 /* Turning calls to direct calls will improve overall summary. */
3986 ipa_update_overall_fn_summary (node
);
3989 class edge_clone_summary
;
3990 static call_summary
<edge_clone_summary
*> *edge_clone_summaries
= NULL
;
3992 /* Edge clone summary. */
3994 class edge_clone_summary
3997 /* Default constructor. */
3998 edge_clone_summary (): prev_clone (NULL
), next_clone (NULL
) {}
4000 /* Default destructor. */
4001 ~edge_clone_summary ()
4004 edge_clone_summaries
->get (prev_clone
)->next_clone
= next_clone
;
4006 edge_clone_summaries
->get (next_clone
)->prev_clone
= prev_clone
;
4009 cgraph_edge
*prev_clone
;
4010 cgraph_edge
*next_clone
;
4013 class edge_clone_summary_t
:
4014 public call_summary
<edge_clone_summary
*>
4017 edge_clone_summary_t (symbol_table
*symtab
):
4018 call_summary
<edge_clone_summary
*> (symtab
)
4020 m_initialize_when_cloning
= true;
4023 virtual void duplicate (cgraph_edge
*src_edge
, cgraph_edge
*dst_edge
,
4024 edge_clone_summary
*src_data
,
4025 edge_clone_summary
*dst_data
);
4028 /* Edge duplication hook. */
4031 edge_clone_summary_t::duplicate (cgraph_edge
*src_edge
, cgraph_edge
*dst_edge
,
4032 edge_clone_summary
*src_data
,
4033 edge_clone_summary
*dst_data
)
4035 if (src_data
->next_clone
)
4036 edge_clone_summaries
->get (src_data
->next_clone
)->prev_clone
= dst_edge
;
4037 dst_data
->prev_clone
= src_edge
;
4038 dst_data
->next_clone
= src_data
->next_clone
;
4039 src_data
->next_clone
= dst_edge
;
4042 /* Return true is CS calls DEST or its clone for all contexts. When
4043 ALLOW_RECURSION_TO_CLONE is false, also return false for self-recursive
4044 edges from/to an all-context clone. */
4047 calls_same_node_or_its_all_contexts_clone_p (cgraph_edge
*cs
, cgraph_node
*dest
,
4048 bool allow_recursion_to_clone
)
4050 enum availability availability
;
4051 cgraph_node
*callee
= cs
->callee
->function_symbol (&availability
);
4053 if (availability
<= AVAIL_INTERPOSABLE
)
4057 if (!allow_recursion_to_clone
&& cs
->caller
== callee
)
4060 class ipa_node_params
*info
= IPA_NODE_REF (callee
);
4061 return info
->is_all_contexts_clone
&& info
->ipcp_orig_node
== dest
;
4064 /* Return true if edge CS does bring about the value described by SRC to
4065 DEST_VAL of node DEST or its clone for all contexts. */
4068 cgraph_edge_brings_value_p (cgraph_edge
*cs
, ipcp_value_source
<tree
> *src
,
4069 cgraph_node
*dest
, ipcp_value
<tree
> *dest_val
)
4071 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4073 if (!calls_same_node_or_its_all_contexts_clone_p (cs
, dest
, !src
->val
)
4074 || caller_info
->node_dead
)
4080 if (caller_info
->ipcp_orig_node
)
4083 if (src
->offset
== -1)
4084 t
= caller_info
->known_csts
[src
->index
];
4086 t
= get_clone_agg_value (cs
->caller
, src
->offset
, src
->index
);
4087 return (t
!= NULL_TREE
4088 && values_equal_for_ipcp_p (src
->val
->value
, t
));
4092 if (src
->val
== dest_val
)
4095 struct ipcp_agg_lattice
*aglat
;
4096 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
4098 if (src
->offset
== -1)
4099 return (plats
->itself
.is_single_const ()
4100 && values_equal_for_ipcp_p (src
->val
->value
,
4101 plats
->itself
.values
->value
));
4104 if (plats
->aggs_bottom
|| plats
->aggs_contain_variable
)
4106 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
4107 if (aglat
->offset
== src
->offset
)
4108 return (aglat
->is_single_const ()
4109 && values_equal_for_ipcp_p (src
->val
->value
,
4110 aglat
->values
->value
));
4116 /* Return true if edge CS does bring about the value described by SRC to
4117 DST_VAL of node DEST or its clone for all contexts. */
4120 cgraph_edge_brings_value_p (cgraph_edge
*cs
,
4121 ipcp_value_source
<ipa_polymorphic_call_context
> *src
,
4123 ipcp_value
<ipa_polymorphic_call_context
> *)
4125 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4127 if (!calls_same_node_or_its_all_contexts_clone_p (cs
, dest
, true)
4128 || caller_info
->node_dead
)
4133 if (caller_info
->ipcp_orig_node
)
4134 return (caller_info
->known_contexts
.length () > (unsigned) src
->index
)
4135 && values_equal_for_ipcp_p (src
->val
->value
,
4136 caller_info
->known_contexts
[src
->index
]);
4138 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
4140 return plats
->ctxlat
.is_single_const ()
4141 && values_equal_for_ipcp_p (src
->val
->value
,
4142 plats
->ctxlat
.values
->value
);
4145 /* Get the next clone in the linked list of clones of an edge. */
4147 static inline struct cgraph_edge
*
4148 get_next_cgraph_edge_clone (struct cgraph_edge
*cs
)
4150 edge_clone_summary
*s
= edge_clone_summaries
->get (cs
);
4151 return s
!= NULL
? s
->next_clone
: NULL
;
4154 /* Given VAL that is intended for DEST, iterate over all its sources and if any
4155 of them is viable and hot, return true. In that case, for those that still
4156 hold, add their edge frequency and their number into *FREQUENCY and
4157 *CALLER_COUNT respectively. */
4159 template <typename valtype
>
4161 get_info_about_necessary_edges (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
4163 profile_count
*count_sum
, int *caller_count
)
4165 ipcp_value_source
<valtype
> *src
;
4166 int freq
= 0, count
= 0;
4167 profile_count cnt
= profile_count::zero ();
4169 bool non_self_recursive
= false;
4171 for (src
= val
->sources
; src
; src
= src
->next
)
4173 struct cgraph_edge
*cs
= src
->cs
;
4176 if (cgraph_edge_brings_value_p (cs
, src
, dest
, val
))
4179 freq
+= cs
->frequency ();
4180 if (cs
->count
.ipa ().initialized_p ())
4181 cnt
+= cs
->count
.ipa ();
4182 hot
|= cs
->maybe_hot_p ();
4183 if (cs
->caller
!= dest
)
4184 non_self_recursive
= true;
4186 cs
= get_next_cgraph_edge_clone (cs
);
4190 /* If the only edges bringing a value are self-recursive ones, do not bother
4192 if (!non_self_recursive
)
4197 *caller_count
= count
;
4199 if (!hot
&& IPA_NODE_REF (dest
)->node_within_scc
)
4201 struct cgraph_edge
*cs
;
4203 /* Cold non-SCC source edge could trigger hot recursive execution of
4204 function. Consider the case as hot and rely on following cost model
4205 computation to further select right one. */
4206 for (cs
= dest
->callers
; cs
; cs
= cs
->next_caller
)
4207 if (cs
->caller
== dest
&& cs
->maybe_hot_p ())
4214 /* Given a NODE, and a set of its CALLERS, try to adjust order of the callers
4215 to let a non-self-recursive caller be the first element. Thus, we can
4216 simplify intersecting operations on values that arrive from all of these
4217 callers, especially when there exists self-recursive call. Return true if
4218 this kind of adjustment is possible. */
4221 adjust_callers_for_value_intersection (vec
<cgraph_edge
*> callers
,
4224 for (unsigned i
= 0; i
< callers
.length (); i
++)
4226 cgraph_edge
*cs
= callers
[i
];
4228 if (cs
->caller
!= node
)
4232 callers
[i
] = callers
[0];
4241 /* Return a vector of incoming edges that do bring value VAL to node DEST. It
4242 is assumed their number is known and equal to CALLER_COUNT. */
4244 template <typename valtype
>
4245 static vec
<cgraph_edge
*>
4246 gather_edges_for_value (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
4249 ipcp_value_source
<valtype
> *src
;
4250 vec
<cgraph_edge
*> ret
;
4252 ret
.create (caller_count
);
4253 for (src
= val
->sources
; src
; src
= src
->next
)
4255 struct cgraph_edge
*cs
= src
->cs
;
4258 if (cgraph_edge_brings_value_p (cs
, src
, dest
, val
))
4259 ret
.quick_push (cs
);
4260 cs
= get_next_cgraph_edge_clone (cs
);
4264 if (caller_count
> 1)
4265 adjust_callers_for_value_intersection (ret
, dest
);
4270 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
4271 Return it or NULL if for some reason it cannot be created. */
4273 static struct ipa_replace_map
*
4274 get_replacement_map (class ipa_node_params
*info
, tree value
, int parm_num
)
4276 struct ipa_replace_map
*replace_map
;
4278 replace_map
= ggc_alloc
<ipa_replace_map
> ();
4281 fprintf (dump_file
, " replacing ");
4282 ipa_dump_param (dump_file
, info
, parm_num
);
4284 fprintf (dump_file
, " with const ");
4285 print_generic_expr (dump_file
, value
);
4286 fprintf (dump_file
, "\n");
4288 replace_map
->parm_num
= parm_num
;
4289 replace_map
->new_tree
= value
;
4293 /* Dump new profiling counts */
4296 dump_profile_updates (struct cgraph_node
*orig_node
,
4297 struct cgraph_node
*new_node
)
4299 struct cgraph_edge
*cs
;
4301 fprintf (dump_file
, " setting count of the specialized node to ");
4302 new_node
->count
.dump (dump_file
);
4303 fprintf (dump_file
, "\n");
4304 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
4306 fprintf (dump_file
, " edge to %s has count ",
4307 cs
->callee
->dump_name ());
4308 cs
->count
.dump (dump_file
);
4309 fprintf (dump_file
, "\n");
4312 fprintf (dump_file
, " setting count of the original node to ");
4313 orig_node
->count
.dump (dump_file
);
4314 fprintf (dump_file
, "\n");
4315 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
4317 fprintf (dump_file
, " edge to %s is left with ",
4318 cs
->callee
->dump_name ());
4319 cs
->count
.dump (dump_file
);
4320 fprintf (dump_file
, "\n");
4324 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
4325 their profile information to reflect this. */
4328 update_profiling_info (struct cgraph_node
*orig_node
,
4329 struct cgraph_node
*new_node
)
4331 struct cgraph_edge
*cs
;
4332 struct caller_statistics stats
;
4333 profile_count new_sum
, orig_sum
;
4334 profile_count remainder
, orig_node_count
= orig_node
->count
;
4335 profile_count orig_new_node_count
= new_node
->count
;
4337 if (!(orig_node_count
.ipa () > profile_count::zero ()))
4340 init_caller_stats (&stats
);
4341 orig_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
4343 orig_sum
= stats
.count_sum
;
4344 init_caller_stats (&stats
);
4345 new_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
4347 new_sum
= stats
.count_sum
;
4349 if (orig_node_count
< orig_sum
+ new_sum
)
4353 fprintf (dump_file
, " Problem: node %s has too low count ",
4354 orig_node
->dump_name ());
4355 orig_node_count
.dump (dump_file
);
4356 fprintf (dump_file
, "while the sum of incoming count is ");
4357 (orig_sum
+ new_sum
).dump (dump_file
);
4358 fprintf (dump_file
, "\n");
4361 orig_node_count
= (orig_sum
+ new_sum
).apply_scale (12, 10);
4364 fprintf (dump_file
, " proceeding by pretending it was ");
4365 orig_node_count
.dump (dump_file
);
4366 fprintf (dump_file
, "\n");
4370 remainder
= orig_node_count
.combine_with_ipa_count (orig_node_count
.ipa ()
4373 /* With partial train run we do not want to assume that original's
4374 count is zero whenever we redurect all executed edges to clone.
4375 Simply drop profile to local one in this case. */
4376 if (remainder
.ipa_p () && !remainder
.ipa ().nonzero_p ()
4377 && orig_node
->count
.ipa_p () && orig_node
->count
.ipa ().nonzero_p ()
4378 && flag_profile_partial_training
)
4379 remainder
= remainder
.guessed_local ();
4381 new_sum
= orig_node_count
.combine_with_ipa_count (new_sum
);
4382 new_node
->count
= new_sum
;
4383 orig_node
->count
= remainder
;
4385 profile_count::adjust_for_ipa_scaling (&new_sum
, &orig_new_node_count
);
4386 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
4387 cs
->count
= cs
->count
.apply_scale (new_sum
, orig_new_node_count
);
4388 for (cs
= new_node
->indirect_calls
; cs
; cs
= cs
->next_callee
)
4389 cs
->count
= cs
->count
.apply_scale (new_sum
, orig_new_node_count
);
4391 profile_count::adjust_for_ipa_scaling (&remainder
, &orig_node_count
);
4392 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
4393 cs
->count
= cs
->count
.apply_scale (remainder
, orig_node_count
);
4394 for (cs
= orig_node
->indirect_calls
; cs
; cs
= cs
->next_callee
)
4395 cs
->count
= cs
->count
.apply_scale (remainder
, orig_node_count
);
4398 dump_profile_updates (orig_node
, new_node
);
4401 /* Update the respective profile of specialized NEW_NODE and the original
4402 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
4403 have been redirected to the specialized version. */
4406 update_specialized_profile (struct cgraph_node
*new_node
,
4407 struct cgraph_node
*orig_node
,
4408 profile_count redirected_sum
)
4410 struct cgraph_edge
*cs
;
4411 profile_count new_node_count
, orig_node_count
= orig_node
->count
;
4415 fprintf (dump_file
, " the sum of counts of redirected edges is ");
4416 redirected_sum
.dump (dump_file
);
4417 fprintf (dump_file
, "\n");
4419 if (!(orig_node_count
> profile_count::zero ()))
4422 gcc_assert (orig_node_count
>= redirected_sum
);
4424 new_node_count
= new_node
->count
;
4425 new_node
->count
+= redirected_sum
;
4426 orig_node
->count
-= redirected_sum
;
4428 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
4429 cs
->count
+= cs
->count
.apply_scale (redirected_sum
, new_node_count
);
4431 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
4433 profile_count dec
= cs
->count
.apply_scale (redirected_sum
,
4439 dump_profile_updates (orig_node
, new_node
);
4442 /* Return true if we would like to remove a parameter from NODE when cloning it
4443 with KNOWN_CSTS scalar constants. */
4446 want_remove_some_param_p (cgraph_node
*node
, vec
<tree
> known_csts
)
4448 auto_vec
<bool, 16> surviving
;
4449 bool filled_vec
= false;
4450 ipa_node_params
*info
= IPA_NODE_REF (node
);
4451 int i
, count
= ipa_get_param_count (info
);
4453 for (i
= 0; i
< count
; i
++)
4455 if (!known_csts
[i
] && ipa_is_param_used (info
, i
))
4460 if (!node
->clone
.param_adjustments
)
4462 node
->clone
.param_adjustments
->get_surviving_params (&surviving
);
4465 if (surviving
.length() < (unsigned) i
&& surviving
[i
])
4471 /* Create a specialized version of NODE with known constants in KNOWN_CSTS,
4472 known contexts in KNOWN_CONTEXTS and known aggregate values in AGGVALS and
4473 redirect all edges in CALLERS to it. */
4475 static struct cgraph_node
*
4476 create_specialized_node (struct cgraph_node
*node
,
4477 vec
<tree
> known_csts
,
4478 vec
<ipa_polymorphic_call_context
> known_contexts
,
4479 struct ipa_agg_replacement_value
*aggvals
,
4480 vec
<cgraph_edge
*> callers
)
4482 class ipa_node_params
*new_info
, *info
= IPA_NODE_REF (node
);
4483 vec
<ipa_replace_map
*, va_gc
> *replace_trees
= NULL
;
4484 vec
<ipa_adjusted_param
, va_gc
> *new_params
= NULL
;
4485 struct ipa_agg_replacement_value
*av
;
4486 struct cgraph_node
*new_node
;
4487 int i
, count
= ipa_get_param_count (info
);
4488 ipa_param_adjustments
*old_adjustments
= node
->clone
.param_adjustments
;
4489 ipa_param_adjustments
*new_adjustments
;
4490 gcc_assert (!info
->ipcp_orig_node
);
4491 gcc_assert (node
->can_change_signature
4492 || !old_adjustments
);
4494 if (old_adjustments
)
4496 /* At the moment all IPA optimizations should use the number of
4497 parameters of the prevailing decl as the m_always_copy_start.
4498 Handling any other value would complicate the code below, so for the
4499 time bing let's only assert it is so. */
4500 gcc_assert (old_adjustments
->m_always_copy_start
== count
4501 || old_adjustments
->m_always_copy_start
< 0);
4502 int old_adj_count
= vec_safe_length (old_adjustments
->m_adj_params
);
4503 for (i
= 0; i
< old_adj_count
; i
++)
4505 ipa_adjusted_param
*old_adj
= &(*old_adjustments
->m_adj_params
)[i
];
4506 if (!node
->can_change_signature
4507 || old_adj
->op
!= IPA_PARAM_OP_COPY
4508 || (!known_csts
[old_adj
->base_index
]
4509 && ipa_is_param_used (info
, old_adj
->base_index
)))
4511 ipa_adjusted_param new_adj
= *old_adj
;
4513 new_adj
.prev_clone_adjustment
= true;
4514 new_adj
.prev_clone_index
= i
;
4515 vec_safe_push (new_params
, new_adj
);
4518 bool skip_return
= old_adjustments
->m_skip_return
;
4519 new_adjustments
= (new (ggc_alloc
<ipa_param_adjustments
> ())
4520 ipa_param_adjustments (new_params
, count
,
4523 else if (node
->can_change_signature
4524 && want_remove_some_param_p (node
, known_csts
))
4526 ipa_adjusted_param adj
;
4527 memset (&adj
, 0, sizeof (adj
));
4528 adj
.op
= IPA_PARAM_OP_COPY
;
4529 for (i
= 0; i
< count
; i
++)
4530 if (!known_csts
[i
] && ipa_is_param_used (info
, i
))
4533 adj
.prev_clone_index
= i
;
4534 vec_safe_push (new_params
, adj
);
4536 new_adjustments
= (new (ggc_alloc
<ipa_param_adjustments
> ())
4537 ipa_param_adjustments (new_params
, count
, false));
4540 new_adjustments
= NULL
;
4542 replace_trees
= vec_safe_copy (node
->clone
.tree_map
);
4543 for (i
= 0; i
< count
; i
++)
4545 tree t
= known_csts
[i
];
4548 struct ipa_replace_map
*replace_map
;
4550 gcc_checking_assert (TREE_CODE (t
) != TREE_BINFO
);
4551 replace_map
= get_replacement_map (info
, t
, i
);
4553 vec_safe_push (replace_trees
, replace_map
);
4556 auto_vec
<cgraph_edge
*, 2> self_recursive_calls
;
4557 for (i
= callers
.length () - 1; i
>= 0; i
--)
4559 cgraph_edge
*cs
= callers
[i
];
4560 if (cs
->caller
== node
)
4562 self_recursive_calls
.safe_push (cs
);
4563 callers
.unordered_remove (i
);
4567 unsigned &suffix_counter
= clone_num_suffixes
->get_or_insert (
4568 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (
4570 new_node
= node
->create_virtual_clone (callers
, replace_trees
,
4571 new_adjustments
, "constprop",
4575 bool have_self_recursive_calls
= !self_recursive_calls
.is_empty ();
4576 for (unsigned j
= 0; j
< self_recursive_calls
.length (); j
++)
4578 cgraph_edge
*cs
= get_next_cgraph_edge_clone (self_recursive_calls
[j
]);
4579 /* Cloned edges can disappear during cloning as speculation can be
4580 resolved, check that we have one and that it comes from the last
4582 if (cs
&& cs
->caller
== new_node
)
4583 cs
->redirect_callee_duplicating_thunks (new_node
);
4584 /* Any future code that would make more than one clone of an outgoing
4585 edge would confuse this mechanism, so let's check that does not
4587 gcc_checking_assert (!cs
4588 || !get_next_cgraph_edge_clone (cs
)
4589 || get_next_cgraph_edge_clone (cs
)->caller
!= new_node
);
4591 if (have_self_recursive_calls
)
4592 new_node
->expand_all_artificial_thunks ();
4594 ipa_set_node_agg_value_chain (new_node
, aggvals
);
4595 for (av
= aggvals
; av
; av
= av
->next
)
4596 new_node
->maybe_create_reference (av
->value
, NULL
);
4598 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4600 fprintf (dump_file
, " the new node is %s.\n", new_node
->dump_name ());
4601 if (known_contexts
.exists ())
4603 for (i
= 0; i
< count
; i
++)
4604 if (!known_contexts
[i
].useless_p ())
4606 fprintf (dump_file
, " known ctx %i is ", i
);
4607 known_contexts
[i
].dump (dump_file
);
4611 ipa_dump_agg_replacement_values (dump_file
, aggvals
);
4613 ipa_check_create_node_params ();
4614 update_profiling_info (node
, new_node
);
4615 new_info
= IPA_NODE_REF (new_node
);
4616 new_info
->ipcp_orig_node
= node
;
4617 new_node
->ipcp_clone
= true;
4618 new_info
->known_csts
= known_csts
;
4619 new_info
->known_contexts
= known_contexts
;
4621 ipcp_discover_new_direct_edges (new_node
, known_csts
, known_contexts
, aggvals
);
4627 /* Return true if JFUNC, which describes a i-th parameter of call CS, is a
4628 pass-through function to itself when the cgraph_node involved is not an
4629 IPA-CP clone. When SIMPLE is true, further check if JFUNC is a simple
4630 no-operation pass-through. */
4633 self_recursive_pass_through_p (cgraph_edge
*cs
, ipa_jump_func
*jfunc
, int i
,
4636 enum availability availability
;
4637 if (cs
->caller
== cs
->callee
->function_symbol (&availability
)
4638 && availability
> AVAIL_INTERPOSABLE
4639 && jfunc
->type
== IPA_JF_PASS_THROUGH
4640 && (!simple
|| ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
4641 && ipa_get_jf_pass_through_formal_id (jfunc
) == i
4642 && IPA_NODE_REF (cs
->caller
)
4643 && !IPA_NODE_REF (cs
->caller
)->ipcp_orig_node
)
4648 /* Return true if JFUNC, which describes a part of an aggregate represented or
4649 pointed to by the i-th parameter of call CS, is a pass-through function to
4650 itself when the cgraph_node involved is not an IPA-CP clone.. When
4651 SIMPLE is true, further check if JFUNC is a simple no-operation
4655 self_recursive_agg_pass_through_p (cgraph_edge
*cs
, ipa_agg_jf_item
*jfunc
,
4656 int i
, bool simple
= true)
4658 enum availability availability
;
4659 if (cs
->caller
== cs
->callee
->function_symbol (&availability
)
4660 && availability
> AVAIL_INTERPOSABLE
4661 && jfunc
->jftype
== IPA_JF_LOAD_AGG
4662 && jfunc
->offset
== jfunc
->value
.load_agg
.offset
4663 && (!simple
|| jfunc
->value
.pass_through
.operation
== NOP_EXPR
)
4664 && jfunc
->value
.pass_through
.formal_id
== i
4665 && useless_type_conversion_p (jfunc
->value
.load_agg
.type
, jfunc
->type
)
4666 && IPA_NODE_REF (cs
->caller
)
4667 && !IPA_NODE_REF (cs
->caller
)->ipcp_orig_node
)
4672 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
4673 KNOWN_CSTS with constants that are also known for all of the CALLERS. */
4676 find_more_scalar_values_for_callers_subset (struct cgraph_node
*node
,
4677 vec
<tree
> known_csts
,
4678 vec
<cgraph_edge
*> callers
)
4680 class ipa_node_params
*info
= IPA_NODE_REF (node
);
4681 int i
, count
= ipa_get_param_count (info
);
4683 for (i
= 0; i
< count
; i
++)
4685 struct cgraph_edge
*cs
;
4686 tree newval
= NULL_TREE
;
4689 tree type
= ipa_get_type (info
, i
);
4691 if (ipa_get_scalar_lat (info
, i
)->bottom
|| known_csts
[i
])
4694 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4696 struct ipa_jump_func
*jump_func
;
4699 if (!IPA_EDGE_REF (cs
)
4700 || i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
))
4702 && call_passes_through_thunk_p (cs
)))
4707 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
4709 /* Besides simple pass-through jump function, arithmetic jump
4710 function could also introduce argument-direct-pass-through for
4711 self-feeding recursive call. For example,
4718 Given that i is 0, recursive propagation via (i & 1) also gets
4720 if (self_recursive_pass_through_p (cs
, jump_func
, i
, false))
4722 gcc_assert (newval
);
4723 t
= ipa_get_jf_arith_result (
4724 ipa_get_jf_pass_through_operation (jump_func
),
4726 ipa_get_jf_pass_through_operand (jump_func
),
4730 t
= ipa_value_from_jfunc (IPA_NODE_REF (cs
->caller
), jump_func
,
4734 && !values_equal_for_ipcp_p (t
, newval
))
4735 || (!first
&& !newval
))
4747 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4749 fprintf (dump_file
, " adding an extra known scalar value ");
4750 print_ipcp_constant_value (dump_file
, newval
);
4751 fprintf (dump_file
, " for ");
4752 ipa_dump_param (dump_file
, info
, i
);
4753 fprintf (dump_file
, "\n");
4756 known_csts
[i
] = newval
;
4761 /* Given a NODE and a subset of its CALLERS, try to populate plank slots in
4762 KNOWN_CONTEXTS with polymorphic contexts that are also known for all of the
4766 find_more_contexts_for_caller_subset (cgraph_node
*node
,
4767 vec
<ipa_polymorphic_call_context
>
4769 vec
<cgraph_edge
*> callers
)
4771 ipa_node_params
*info
= IPA_NODE_REF (node
);
4772 int i
, count
= ipa_get_param_count (info
);
4774 for (i
= 0; i
< count
; i
++)
4778 if (ipa_get_poly_ctx_lat (info
, i
)->bottom
4779 || (known_contexts
->exists ()
4780 && !(*known_contexts
)[i
].useless_p ()))
4783 ipa_polymorphic_call_context newval
;
4787 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4789 if (!IPA_EDGE_REF (cs
)
4790 || i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
)))
4792 ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
),
4794 ipa_polymorphic_call_context ctx
;
4795 ctx
= ipa_context_from_jfunc (IPA_NODE_REF (cs
->caller
), cs
, i
,
4803 newval
.meet_with (ctx
);
4804 if (newval
.useless_p ())
4808 if (!newval
.useless_p ())
4810 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4812 fprintf (dump_file
, " adding an extra known polymorphic "
4814 print_ipcp_constant_value (dump_file
, newval
);
4815 fprintf (dump_file
, " for ");
4816 ipa_dump_param (dump_file
, info
, i
);
4817 fprintf (dump_file
, "\n");
4820 if (!known_contexts
->exists ())
4821 known_contexts
->safe_grow_cleared (ipa_get_param_count (info
));
4822 (*known_contexts
)[i
] = newval
;
4828 /* Go through PLATS and create a vector of values consisting of values and
4829 offsets (minus OFFSET) of lattices that contain only a single value. */
4831 static vec
<ipa_agg_value
>
4832 copy_plats_to_inter (class ipcp_param_lattices
*plats
, HOST_WIDE_INT offset
)
4834 vec
<ipa_agg_value
> res
= vNULL
;
4836 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
4839 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
4840 if (aglat
->is_single_const ())
4842 struct ipa_agg_value ti
;
4843 ti
.offset
= aglat
->offset
- offset
;
4844 ti
.value
= aglat
->values
->value
;
4850 /* Intersect all values in INTER with single value lattices in PLATS (while
4851 subtracting OFFSET). */
4854 intersect_with_plats (class ipcp_param_lattices
*plats
,
4855 vec
<ipa_agg_value
> *inter
,
4856 HOST_WIDE_INT offset
)
4858 struct ipcp_agg_lattice
*aglat
;
4859 struct ipa_agg_value
*item
;
4862 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
4868 aglat
= plats
->aggs
;
4869 FOR_EACH_VEC_ELT (*inter
, k
, item
)
4876 if (aglat
->offset
- offset
> item
->offset
)
4878 if (aglat
->offset
- offset
== item
->offset
)
4880 if (aglat
->is_single_const ())
4882 tree value
= aglat
->values
->value
;
4884 if (values_equal_for_ipcp_p (item
->value
, value
))
4889 aglat
= aglat
->next
;
4892 item
->value
= NULL_TREE
;
4896 /* Copy aggregate replacement values of NODE (which is an IPA-CP clone) to the
4897 vector result while subtracting OFFSET from the individual value offsets. */
4899 static vec
<ipa_agg_value
>
4900 agg_replacements_to_vector (struct cgraph_node
*node
, int index
,
4901 HOST_WIDE_INT offset
)
4903 struct ipa_agg_replacement_value
*av
;
4904 vec
<ipa_agg_value
> res
= vNULL
;
4906 for (av
= ipa_get_agg_replacements_for_node (node
); av
; av
= av
->next
)
4907 if (av
->index
== index
4908 && (av
->offset
- offset
) >= 0)
4910 struct ipa_agg_value item
;
4911 gcc_checking_assert (av
->value
);
4912 item
.offset
= av
->offset
- offset
;
4913 item
.value
= av
->value
;
4914 res
.safe_push (item
);
4920 /* Intersect all values in INTER with those that we have already scheduled to
4921 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
4922 (while subtracting OFFSET). */
4925 intersect_with_agg_replacements (struct cgraph_node
*node
, int index
,
4926 vec
<ipa_agg_value
> *inter
,
4927 HOST_WIDE_INT offset
)
4929 struct ipa_agg_replacement_value
*srcvals
;
4930 struct ipa_agg_value
*item
;
4933 srcvals
= ipa_get_agg_replacements_for_node (node
);
4940 FOR_EACH_VEC_ELT (*inter
, i
, item
)
4942 struct ipa_agg_replacement_value
*av
;
4946 for (av
= srcvals
; av
; av
= av
->next
)
4948 gcc_checking_assert (av
->value
);
4949 if (av
->index
== index
4950 && av
->offset
- offset
== item
->offset
)
4952 if (values_equal_for_ipcp_p (item
->value
, av
->value
))
4958 item
->value
= NULL_TREE
;
4962 /* Intersect values in INTER with aggregate values that come along edge CS to
4963 parameter number INDEX and return it. If INTER does not actually exist yet,
4964 copy all incoming values to it. If we determine we ended up with no values
4965 whatsoever, return a released vector. */
4967 static vec
<ipa_agg_value
>
4968 intersect_aggregates_with_edge (struct cgraph_edge
*cs
, int index
,
4969 vec
<ipa_agg_value
> inter
)
4971 struct ipa_jump_func
*jfunc
;
4972 jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), index
);
4973 if (jfunc
->type
== IPA_JF_PASS_THROUGH
4974 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
4976 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4977 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
4979 if (caller_info
->ipcp_orig_node
)
4981 struct cgraph_node
*orig_node
= caller_info
->ipcp_orig_node
;
4982 class ipcp_param_lattices
*orig_plats
;
4983 orig_plats
= ipa_get_parm_lattices (IPA_NODE_REF (orig_node
),
4985 if (agg_pass_through_permissible_p (orig_plats
, jfunc
))
4987 if (!inter
.exists ())
4988 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, 0);
4990 intersect_with_agg_replacements (cs
->caller
, src_idx
,
4997 class ipcp_param_lattices
*src_plats
;
4998 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
4999 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
5001 /* Currently we do not produce clobber aggregate jump
5002 functions, adjust when we do. */
5003 gcc_checking_assert (!jfunc
->agg
.items
);
5004 if (!inter
.exists ())
5005 inter
= copy_plats_to_inter (src_plats
, 0);
5007 intersect_with_plats (src_plats
, &inter
, 0);
5012 else if (jfunc
->type
== IPA_JF_ANCESTOR
5013 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
5015 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
5016 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
5017 class ipcp_param_lattices
*src_plats
;
5018 HOST_WIDE_INT delta
= ipa_get_jf_ancestor_offset (jfunc
);
5020 if (caller_info
->ipcp_orig_node
)
5022 if (!inter
.exists ())
5023 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, delta
);
5025 intersect_with_agg_replacements (cs
->caller
, src_idx
, &inter
,
5030 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
5031 /* Currently we do not produce clobber aggregate jump
5032 functions, adjust when we do. */
5033 gcc_checking_assert (!src_plats
->aggs
|| !jfunc
->agg
.items
);
5034 if (!inter
.exists ())
5035 inter
= copy_plats_to_inter (src_plats
, delta
);
5037 intersect_with_plats (src_plats
, &inter
, delta
);
5042 if (jfunc
->agg
.items
)
5044 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
5045 struct ipa_agg_value
*item
;
5048 if (!inter
.exists ())
5049 for (unsigned i
= 0; i
< jfunc
->agg
.items
->length (); i
++)
5051 struct ipa_agg_jf_item
*agg_item
= &(*jfunc
->agg
.items
)[i
];
5052 tree value
= ipa_agg_value_from_node (caller_info
, cs
->caller
,
5056 struct ipa_agg_value agg_value
;
5058 agg_value
.value
= value
;
5059 agg_value
.offset
= agg_item
->offset
;
5060 inter
.safe_push (agg_value
);
5064 FOR_EACH_VEC_ELT (inter
, k
, item
)
5072 while ((unsigned) l
< jfunc
->agg
.items
->length ())
5074 struct ipa_agg_jf_item
*ti
;
5075 ti
= &(*jfunc
->agg
.items
)[l
];
5076 if (ti
->offset
> item
->offset
)
5078 if (ti
->offset
== item
->offset
)
5082 /* Besides simple pass-through aggregate jump function,
5083 arithmetic aggregate jump function could also bring
5084 same aggregate value as parameter passed-in for
5085 self-feeding recursive call. For example,
5093 Given that *i is 0, recursive propagation via (*i & 1)
5095 if (self_recursive_agg_pass_through_p (cs
, ti
, index
,
5097 value
= ipa_get_jf_arith_result (
5098 ti
->value
.pass_through
.operation
,
5100 ti
->value
.pass_through
.operand
,
5103 value
= ipa_agg_value_from_node (caller_info
,
5106 if (value
&& values_equal_for_ipcp_p (item
->value
, value
))
5124 /* Look at edges in CALLERS and collect all known aggregate values that arrive
5125 from all of them. */
5127 static struct ipa_agg_replacement_value
*
5128 find_aggregate_values_for_callers_subset (struct cgraph_node
*node
,
5129 vec
<cgraph_edge
*> callers
)
5131 class ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
5132 struct ipa_agg_replacement_value
*res
;
5133 struct ipa_agg_replacement_value
**tail
= &res
;
5134 struct cgraph_edge
*cs
;
5135 int i
, j
, count
= ipa_get_param_count (dest_info
);
5137 FOR_EACH_VEC_ELT (callers
, j
, cs
)
5139 if (!IPA_EDGE_REF (cs
))
5144 int c
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
5149 for (i
= 0; i
< count
; i
++)
5151 struct cgraph_edge
*cs
;
5152 vec
<ipa_agg_value
> inter
= vNULL
;
5153 struct ipa_agg_value
*item
;
5154 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (dest_info
, i
);
5157 /* Among other things, the following check should deal with all by_ref
5159 if (plats
->aggs_bottom
)
5162 FOR_EACH_VEC_ELT (callers
, j
, cs
)
5164 struct ipa_jump_func
*jfunc
5165 = ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
5166 if (self_recursive_pass_through_p (cs
, jfunc
, i
)
5167 && (!plats
->aggs_by_ref
5168 || ipa_get_jf_pass_through_agg_preserved (jfunc
)))
5170 inter
= intersect_aggregates_with_edge (cs
, i
, inter
);
5172 if (!inter
.exists ())
5176 FOR_EACH_VEC_ELT (inter
, j
, item
)
5178 struct ipa_agg_replacement_value
*v
;
5183 v
= ggc_alloc
<ipa_agg_replacement_value
> ();
5185 v
->offset
= item
->offset
;
5186 v
->value
= item
->value
;
5187 v
->by_ref
= plats
->aggs_by_ref
;
5193 if (inter
.exists ())
5200 /* Determine whether CS also brings all scalar values that the NODE is
5204 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge
*cs
,
5205 struct cgraph_node
*node
)
5207 class ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
5208 int count
= ipa_get_param_count (dest_info
);
5209 class ipa_node_params
*caller_info
;
5210 class ipa_edge_args
*args
;
5213 caller_info
= IPA_NODE_REF (cs
->caller
);
5214 args
= IPA_EDGE_REF (cs
);
5215 for (i
= 0; i
< count
; i
++)
5217 struct ipa_jump_func
*jump_func
;
5220 val
= dest_info
->known_csts
[i
];
5224 if (i
>= ipa_get_cs_argument_count (args
))
5226 jump_func
= ipa_get_ith_jump_func (args
, i
);
5227 t
= ipa_value_from_jfunc (caller_info
, jump_func
,
5228 ipa_get_type (dest_info
, i
));
5229 if (!t
|| !values_equal_for_ipcp_p (val
, t
))
5235 /* Determine whether CS also brings all aggregate values that NODE is
5238 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge
*cs
,
5239 struct cgraph_node
*node
)
5241 class ipa_node_params
*orig_node_info
;
5242 struct ipa_agg_replacement_value
*aggval
;
5245 aggval
= ipa_get_agg_replacements_for_node (node
);
5249 count
= ipa_get_param_count (IPA_NODE_REF (node
));
5250 ec
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
5252 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
5253 if (aggval
->index
>= ec
)
5256 orig_node_info
= IPA_NODE_REF (IPA_NODE_REF (node
)->ipcp_orig_node
);
5258 for (i
= 0; i
< count
; i
++)
5260 class ipcp_param_lattices
*plats
;
5261 bool interesting
= false;
5262 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
5263 if (aggval
->index
== i
)
5271 plats
= ipa_get_parm_lattices (orig_node_info
, aggval
->index
);
5272 if (plats
->aggs_bottom
)
5275 vec
<ipa_agg_value
> values
= intersect_aggregates_with_edge (cs
, i
, vNULL
);
5276 if (!values
.exists ())
5279 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
5280 if (aggval
->index
== i
)
5282 struct ipa_agg_value
*item
;
5285 FOR_EACH_VEC_ELT (values
, j
, item
)
5287 && item
->offset
== av
->offset
5288 && values_equal_for_ipcp_p (item
->value
, av
->value
))
5304 /* Given an original NODE and a VAL for which we have already created a
5305 specialized clone, look whether there are incoming edges that still lead
5306 into the old node but now also bring the requested value and also conform to
5307 all other criteria such that they can be redirected the special node.
5308 This function can therefore redirect the final edge in a SCC. */
5310 template <typename valtype
>
5312 perhaps_add_new_callers (cgraph_node
*node
, ipcp_value
<valtype
> *val
)
5314 ipcp_value_source
<valtype
> *src
;
5315 profile_count redirected_sum
= profile_count::zero ();
5317 for (src
= val
->sources
; src
; src
= src
->next
)
5319 struct cgraph_edge
*cs
= src
->cs
;
5322 if (cgraph_edge_brings_value_p (cs
, src
, node
, val
)
5323 && cgraph_edge_brings_all_scalars_for_node (cs
, val
->spec_node
)
5324 && cgraph_edge_brings_all_agg_vals_for_node (cs
, val
->spec_node
))
5327 fprintf (dump_file
, " - adding an extra caller %s of %s\n",
5328 cs
->caller
->dump_name (),
5329 val
->spec_node
->dump_name ());
5331 cs
->redirect_callee_duplicating_thunks (val
->spec_node
);
5332 val
->spec_node
->expand_all_artificial_thunks ();
5333 if (cs
->count
.ipa ().initialized_p ())
5334 redirected_sum
= redirected_sum
+ cs
->count
.ipa ();
5336 cs
= get_next_cgraph_edge_clone (cs
);
5340 if (redirected_sum
.nonzero_p ())
5341 update_specialized_profile (val
->spec_node
, node
, redirected_sum
);
5344 /* Return true if KNOWN_CONTEXTS contain at least one useful context. */
5347 known_contexts_useful_p (vec
<ipa_polymorphic_call_context
> known_contexts
)
5349 ipa_polymorphic_call_context
*ctx
;
5352 FOR_EACH_VEC_ELT (known_contexts
, i
, ctx
)
5353 if (!ctx
->useless_p ())
5358 /* Return a copy of KNOWN_CSTS if it is not empty, otherwise return vNULL. */
5360 static vec
<ipa_polymorphic_call_context
>
5361 copy_useful_known_contexts (vec
<ipa_polymorphic_call_context
> known_contexts
)
5363 if (known_contexts_useful_p (known_contexts
))
5364 return known_contexts
.copy ();
5369 /* Copy KNOWN_CSTS and modify the copy according to VAL and INDEX. If
5370 non-empty, replace KNOWN_CONTEXTS with its copy too. */
5373 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
5374 vec
<ipa_polymorphic_call_context
> *known_contexts
,
5375 ipcp_value
<tree
> *val
,
5378 *known_csts
= known_csts
->copy ();
5379 *known_contexts
= copy_useful_known_contexts (*known_contexts
);
5380 (*known_csts
)[index
] = val
->value
;
5383 /* Replace KNOWN_CSTS with its copy. Also copy KNOWN_CONTEXTS and modify the
5384 copy according to VAL and INDEX. */
5387 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
5388 vec
<ipa_polymorphic_call_context
> *known_contexts
,
5389 ipcp_value
<ipa_polymorphic_call_context
> *val
,
5392 *known_csts
= known_csts
->copy ();
5393 *known_contexts
= known_contexts
->copy ();
5394 (*known_contexts
)[index
] = val
->value
;
5397 /* Return true if OFFSET indicates this was not an aggregate value or there is
5398 a replacement equivalent to VALUE, INDEX and OFFSET among those in the
5402 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*aggvals
,
5403 int index
, HOST_WIDE_INT offset
, tree value
)
5410 if (aggvals
->index
== index
5411 && aggvals
->offset
== offset
5412 && values_equal_for_ipcp_p (aggvals
->value
, value
))
5414 aggvals
= aggvals
->next
;
5419 /* Return true if offset is minus one because source of a polymorphic context
5420 cannot be an aggregate value. */
5423 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*,
5424 int , HOST_WIDE_INT offset
,
5425 ipa_polymorphic_call_context
)
5427 return offset
== -1;
5430 /* Decide whether to create a special version of NODE for value VAL of parameter
5431 at the given INDEX. If OFFSET is -1, the value is for the parameter itself,
5432 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS,
5433 KNOWN_CONTEXTS and KNOWN_AGGS describe the other already known values. */
5435 template <typename valtype
>
5437 decide_about_value (struct cgraph_node
*node
, int index
, HOST_WIDE_INT offset
,
5438 ipcp_value
<valtype
> *val
, vec
<tree
> known_csts
,
5439 vec
<ipa_polymorphic_call_context
> known_contexts
)
5441 struct ipa_agg_replacement_value
*aggvals
;
5442 int freq_sum
, caller_count
;
5443 profile_count count_sum
;
5444 vec
<cgraph_edge
*> callers
;
5448 perhaps_add_new_callers (node
, val
);
5451 else if (val
->local_size_cost
+ overall_size
> get_max_overall_size (node
))
5453 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5454 fprintf (dump_file
, " Ignoring candidate value because "
5455 "maximum unit size would be reached with %li.\n",
5456 val
->local_size_cost
+ overall_size
);
5459 else if (!get_info_about_necessary_edges (val
, node
, &freq_sum
, &count_sum
,
5463 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5465 fprintf (dump_file
, " - considering value ");
5466 print_ipcp_constant_value (dump_file
, val
->value
);
5467 fprintf (dump_file
, " for ");
5468 ipa_dump_param (dump_file
, IPA_NODE_REF (node
), index
);
5470 fprintf (dump_file
, ", offset: " HOST_WIDE_INT_PRINT_DEC
, offset
);
5471 fprintf (dump_file
, " (caller_count: %i)\n", caller_count
);
5474 if (!good_cloning_opportunity_p (node
, val
->local_time_benefit
,
5475 freq_sum
, count_sum
,
5476 val
->local_size_cost
)
5477 && !good_cloning_opportunity_p (node
,
5478 val
->local_time_benefit
5479 + val
->prop_time_benefit
,
5480 freq_sum
, count_sum
,
5481 val
->local_size_cost
5482 + val
->prop_size_cost
))
5486 fprintf (dump_file
, " Creating a specialized node of %s.\n",
5487 node
->dump_name ());
5489 callers
= gather_edges_for_value (val
, node
, caller_count
);
5491 modify_known_vectors_with_val (&known_csts
, &known_contexts
, val
, index
);
5494 known_csts
= known_csts
.copy ();
5495 known_contexts
= copy_useful_known_contexts (known_contexts
);
5497 find_more_scalar_values_for_callers_subset (node
, known_csts
, callers
);
5498 find_more_contexts_for_caller_subset (node
, &known_contexts
, callers
);
5499 aggvals
= find_aggregate_values_for_callers_subset (node
, callers
);
5500 gcc_checking_assert (ipcp_val_agg_replacement_ok_p (aggvals
, index
,
5501 offset
, val
->value
));
5502 val
->spec_node
= create_specialized_node (node
, known_csts
, known_contexts
,
5504 overall_size
+= val
->local_size_cost
;
5506 /* TODO: If for some lattice there is only one other known value
5507 left, make a special node for it too. */
5512 /* Decide whether and what specialized clones of NODE should be created. */
5515 decide_whether_version_node (struct cgraph_node
*node
)
5517 class ipa_node_params
*info
= IPA_NODE_REF (node
);
5518 int i
, count
= ipa_get_param_count (info
);
5519 vec
<tree
> known_csts
;
5520 vec
<ipa_polymorphic_call_context
> known_contexts
;
5526 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5527 fprintf (dump_file
, "\nEvaluating opportunities for %s.\n",
5528 node
->dump_name ());
5530 gather_context_independent_values (info
, &known_csts
, &known_contexts
,
5533 for (i
= 0; i
< count
;i
++)
5535 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5536 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
5537 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
5542 ipcp_value
<tree
> *val
;
5543 for (val
= lat
->values
; val
; val
= val
->next
)
5544 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
5548 if (!plats
->aggs_bottom
)
5550 struct ipcp_agg_lattice
*aglat
;
5551 ipcp_value
<tree
> *val
;
5552 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
5553 if (!aglat
->bottom
&& aglat
->values
5554 /* If the following is false, the one value is in
5556 && (plats
->aggs_contain_variable
5557 || !aglat
->is_single_const ()))
5558 for (val
= aglat
->values
; val
; val
= val
->next
)
5559 ret
|= decide_about_value (node
, i
, aglat
->offset
, val
,
5560 known_csts
, known_contexts
);
5564 && known_contexts
[i
].useless_p ())
5566 ipcp_value
<ipa_polymorphic_call_context
> *val
;
5567 for (val
= ctxlat
->values
; val
; val
= val
->next
)
5568 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
5572 info
= IPA_NODE_REF (node
);
5575 if (info
->do_clone_for_all_contexts
)
5577 struct cgraph_node
*clone
;
5578 vec
<cgraph_edge
*> callers
= node
->collect_callers ();
5580 for (int i
= callers
.length () - 1; i
>= 0; i
--)
5582 cgraph_edge
*cs
= callers
[i
];
5583 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
5585 if (caller_info
&& caller_info
->node_dead
)
5586 callers
.unordered_remove (i
);
5589 if (!adjust_callers_for_value_intersection (callers
, node
))
5591 /* If node is not called by anyone, or all its caller edges are
5592 self-recursive, the node is not really be in use, no need to
5595 known_csts
.release ();
5596 known_contexts
.release ();
5597 info
->do_clone_for_all_contexts
= false;
5602 fprintf (dump_file
, " - Creating a specialized node of %s "
5603 "for all known contexts.\n", node
->dump_name ());
5605 find_more_scalar_values_for_callers_subset (node
, known_csts
, callers
);
5606 find_more_contexts_for_caller_subset (node
, &known_contexts
, callers
);
5607 ipa_agg_replacement_value
*aggvals
5608 = find_aggregate_values_for_callers_subset (node
, callers
);
5610 if (!known_contexts_useful_p (known_contexts
))
5612 known_contexts
.release ();
5613 known_contexts
= vNULL
;
5615 clone
= create_specialized_node (node
, known_csts
, known_contexts
,
5617 info
= IPA_NODE_REF (node
);
5618 info
->do_clone_for_all_contexts
= false;
5619 IPA_NODE_REF (clone
)->is_all_contexts_clone
= true;
5624 known_csts
.release ();
5625 known_contexts
.release ();
5631 /* Transitively mark all callees of NODE within the same SCC as not dead. */
5634 spread_undeadness (struct cgraph_node
*node
)
5636 struct cgraph_edge
*cs
;
5638 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
5639 if (ipa_edge_within_scc (cs
))
5641 struct cgraph_node
*callee
;
5642 class ipa_node_params
*info
;
5644 callee
= cs
->callee
->function_symbol (NULL
);
5645 info
= IPA_NODE_REF (callee
);
5647 if (info
&& info
->node_dead
)
5649 info
->node_dead
= 0;
5650 spread_undeadness (callee
);
5655 /* Return true if NODE has a caller from outside of its SCC that is not
5656 dead. Worker callback for cgraph_for_node_and_aliases. */
5659 has_undead_caller_from_outside_scc_p (struct cgraph_node
*node
,
5660 void *data ATTRIBUTE_UNUSED
)
5662 struct cgraph_edge
*cs
;
5664 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
5665 if (cs
->caller
->thunk
.thunk_p
5666 && cs
->caller
->call_for_symbol_thunks_and_aliases
5667 (has_undead_caller_from_outside_scc_p
, NULL
, true))
5669 else if (!ipa_edge_within_scc (cs
)
5670 && !IPA_NODE_REF (cs
->caller
)->node_dead
)
5676 /* Identify nodes within the same SCC as NODE which are no longer needed
5677 because of new clones and will be removed as unreachable. */
5680 identify_dead_nodes (struct cgraph_node
*node
)
5682 struct cgraph_node
*v
;
5683 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
5686 && !v
->call_for_symbol_thunks_and_aliases
5687 (has_undead_caller_from_outside_scc_p
, NULL
, true))
5688 IPA_NODE_REF (v
)->node_dead
= 1;
5690 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
5691 if (IPA_NODE_REF (v
) && !IPA_NODE_REF (v
)->node_dead
)
5692 spread_undeadness (v
);
5694 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5696 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
5697 if (IPA_NODE_REF (v
) && IPA_NODE_REF (v
)->node_dead
)
5698 fprintf (dump_file
, " Marking node as dead: %s.\n", v
->dump_name ());
5702 /* The decision stage. Iterate over the topological order of call graph nodes
5703 TOPO and make specialized clones if deemed beneficial. */
5706 ipcp_decision_stage (class ipa_topo_info
*topo
)
5711 fprintf (dump_file
, "\nIPA decision stage:\n\n");
5713 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
5715 struct cgraph_node
*node
= topo
->order
[i
];
5716 bool change
= false, iterate
= true;
5720 struct cgraph_node
*v
;
5722 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
5723 if (v
->has_gimple_body_p ()
5724 && ipcp_versionable_function_p (v
))
5725 iterate
|= decide_whether_version_node (v
);
5730 identify_dead_nodes (node
);
5734 /* Look up all the bits information that we have discovered and copy it over
5735 to the transformation summary. */
5738 ipcp_store_bits_results (void)
5742 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5744 ipa_node_params
*info
= IPA_NODE_REF (node
);
5745 bool dumped_sth
= false;
5746 bool found_useful_result
= false;
5748 if (!opt_for_fn (node
->decl
, flag_ipa_bit_cp
) || !info
)
5751 fprintf (dump_file
, "Not considering %s for ipa bitwise propagation "
5752 "; -fipa-bit-cp: disabled.\n",
5753 node
->dump_name ());
5757 if (info
->ipcp_orig_node
)
5758 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
5759 if (!info
->lattices
)
5760 /* Newly expanded artificial thunks do not have lattices. */
5763 unsigned count
= ipa_get_param_count (info
);
5764 for (unsigned i
= 0; i
< count
; i
++)
5766 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5767 if (plats
->bits_lattice
.constant_p ())
5769 found_useful_result
= true;
5774 if (!found_useful_result
)
5777 ipcp_transformation_initialize ();
5778 ipcp_transformation
*ts
= ipcp_transformation_sum
->get_create (node
);
5779 vec_safe_reserve_exact (ts
->bits
, count
);
5781 for (unsigned i
= 0; i
< count
; i
++)
5783 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5786 if (plats
->bits_lattice
.constant_p ())
5788 = ipa_get_ipa_bits_for_value (plats
->bits_lattice
.get_value (),
5789 plats
->bits_lattice
.get_mask ());
5793 ts
->bits
->quick_push (jfbits
);
5794 if (!dump_file
|| !jfbits
)
5798 fprintf (dump_file
, "Propagated bits info for function %s:\n",
5799 node
->dump_name ());
5802 fprintf (dump_file
, " param %i: value = ", i
);
5803 print_hex (jfbits
->value
, dump_file
);
5804 fprintf (dump_file
, ", mask = ");
5805 print_hex (jfbits
->mask
, dump_file
);
5806 fprintf (dump_file
, "\n");
5811 /* Look up all VR information that we have discovered and copy it over
5812 to the transformation summary. */
5815 ipcp_store_vr_results (void)
5819 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5821 ipa_node_params
*info
= IPA_NODE_REF (node
);
5822 bool found_useful_result
= false;
5824 if (!info
|| !opt_for_fn (node
->decl
, flag_ipa_vrp
))
5827 fprintf (dump_file
, "Not considering %s for VR discovery "
5828 "and propagate; -fipa-ipa-vrp: disabled.\n",
5829 node
->dump_name ());
5833 if (info
->ipcp_orig_node
)
5834 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
5835 if (!info
->lattices
)
5836 /* Newly expanded artificial thunks do not have lattices. */
5839 unsigned count
= ipa_get_param_count (info
);
5840 for (unsigned i
= 0; i
< count
; i
++)
5842 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5843 if (!plats
->m_value_range
.bottom_p ()
5844 && !plats
->m_value_range
.top_p ())
5846 found_useful_result
= true;
5850 if (!found_useful_result
)
5853 ipcp_transformation_initialize ();
5854 ipcp_transformation
*ts
= ipcp_transformation_sum
->get_create (node
);
5855 vec_safe_reserve_exact (ts
->m_vr
, count
);
5857 for (unsigned i
= 0; i
< count
; i
++)
5859 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5862 if (!plats
->m_value_range
.bottom_p ()
5863 && !plats
->m_value_range
.top_p ())
5866 vr
.type
= plats
->m_value_range
.m_vr
.kind ();
5867 vr
.min
= wi::to_wide (plats
->m_value_range
.m_vr
.min ());
5868 vr
.max
= wi::to_wide (plats
->m_value_range
.m_vr
.max ());
5873 vr
.type
= VR_VARYING
;
5874 vr
.min
= vr
.max
= wi::zero (INT_TYPE_SIZE
);
5876 ts
->m_vr
->quick_push (vr
);
5881 /* The IPCP driver. */
5886 class ipa_topo_info topo
;
5888 if (edge_clone_summaries
== NULL
)
5889 edge_clone_summaries
= new edge_clone_summary_t (symtab
);
5891 ipa_check_create_node_params ();
5892 ipa_check_create_edge_args ();
5893 clone_num_suffixes
= new hash_map
<const char *, unsigned>;
5897 fprintf (dump_file
, "\nIPA structures before propagation:\n");
5898 if (dump_flags
& TDF_DETAILS
)
5899 ipa_print_all_params (dump_file
);
5900 ipa_print_all_jump_functions (dump_file
);
5903 /* Topological sort. */
5904 build_toporder_info (&topo
);
5905 /* Do the interprocedural propagation. */
5906 ipcp_propagate_stage (&topo
);
5907 /* Decide what constant propagation and cloning should be performed. */
5908 ipcp_decision_stage (&topo
);
5909 /* Store results of bits propagation. */
5910 ipcp_store_bits_results ();
5911 /* Store results of value range propagation. */
5912 ipcp_store_vr_results ();
5914 /* Free all IPCP structures. */
5915 delete clone_num_suffixes
;
5916 free_toporder_info (&topo
);
5917 delete edge_clone_summaries
;
5918 edge_clone_summaries
= NULL
;
5919 ipa_free_all_structures_after_ipa_cp ();
5921 fprintf (dump_file
, "\nIPA constant propagation end\n");
5925 /* Initialization and computation of IPCP data structures. This is the initial
5926 intraprocedural analysis of functions, which gathers information to be
5927 propagated later on. */
5930 ipcp_generate_summary (void)
5932 struct cgraph_node
*node
;
5935 fprintf (dump_file
, "\nIPA constant propagation start:\n");
5936 ipa_register_cgraph_hooks ();
5938 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5939 ipa_analyze_node (node
);
5942 /* Write ipcp summary for nodes in SET. */
5945 ipcp_write_summary (void)
5947 ipa_prop_write_jump_functions ();
5950 /* Read ipcp summary. */
5953 ipcp_read_summary (void)
5955 ipa_prop_read_jump_functions ();
5960 const pass_data pass_data_ipa_cp
=
5962 IPA_PASS
, /* type */
5964 OPTGROUP_NONE
, /* optinfo_flags */
5965 TV_IPA_CONSTANT_PROP
, /* tv_id */
5966 0, /* properties_required */
5967 0, /* properties_provided */
5968 0, /* properties_destroyed */
5969 0, /* todo_flags_start */
5970 ( TODO_dump_symtab
| TODO_remove_functions
), /* todo_flags_finish */
5973 class pass_ipa_cp
: public ipa_opt_pass_d
5976 pass_ipa_cp (gcc::context
*ctxt
)
5977 : ipa_opt_pass_d (pass_data_ipa_cp
, ctxt
,
5978 ipcp_generate_summary
, /* generate_summary */
5979 ipcp_write_summary
, /* write_summary */
5980 ipcp_read_summary
, /* read_summary */
5981 ipcp_write_transformation_summaries
, /*
5982 write_optimization_summary */
5983 ipcp_read_transformation_summaries
, /*
5984 read_optimization_summary */
5985 NULL
, /* stmt_fixup */
5986 0, /* function_transform_todo_flags_start */
5987 ipcp_transform_function
, /* function_transform */
5988 NULL
) /* variable_transform */
5991 /* opt_pass methods: */
5992 virtual bool gate (function
*)
5994 /* FIXME: We should remove the optimize check after we ensure we never run
5995 IPA passes when not optimizing. */
5996 return (flag_ipa_cp
&& optimize
) || in_lto_p
;
5999 virtual unsigned int execute (function
*) { return ipcp_driver (); }
6001 }; // class pass_ipa_cp
6006 make_pass_ipa_cp (gcc::context
*ctxt
)
6008 return new pass_ipa_cp (ctxt
);
6011 /* Reset all state within ipa-cp.c so that we can rerun the compiler
6012 within the same process. For use by toplev::finalize. */
6015 ipa_cp_c_finalize (void)
6017 max_count
= profile_count::uninitialized ();
6019 orig_overall_size
= 0;
6020 ipcp_free_transformation_sum ();