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
,
2740 ret
|= set_agg_lats_contain_variable (dest_plats
);
2742 else if (jfunc
->type
== IPA_JF_ANCESTOR
2743 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
2745 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2746 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
2747 class ipcp_param_lattices
*src_plats
;
2749 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2750 if (src_plats
->aggs
&& src_plats
->aggs_by_ref
)
2752 /* Currently we do not produce clobber aggregate jump
2753 functions, replace with merging when we do. */
2754 gcc_assert (!jfunc
->agg
.items
);
2755 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
, src_idx
,
2756 ipa_get_jf_ancestor_offset (jfunc
));
2758 else if (!src_plats
->aggs_by_ref
)
2759 ret
|= set_agg_lats_to_bottom (dest_plats
);
2761 ret
|= set_agg_lats_contain_variable (dest_plats
);
2763 else if (jfunc
->agg
.items
)
2765 bool pre_existing
= dest_plats
->aggs
!= NULL
;
2766 struct ipcp_agg_lattice
**aglat
= &dest_plats
->aggs
;
2767 struct ipa_agg_jf_item
*item
;
2770 if (set_check_aggs_by_ref (dest_plats
, jfunc
->agg
.by_ref
))
2773 int max_agg_items
= opt_for_fn (cs
->callee
->function_symbol ()->decl
,
2774 param_ipa_max_agg_items
);
2775 FOR_EACH_VEC_ELT (*jfunc
->agg
.items
, i
, item
)
2777 HOST_WIDE_INT val_size
;
2779 if (item
->offset
< 0 || item
->jftype
== IPA_JF_UNKNOWN
)
2781 val_size
= tree_to_shwi (TYPE_SIZE (item
->type
));
2783 if (merge_agg_lats_step (dest_plats
, item
->offset
, val_size
,
2784 &aglat
, pre_existing
, &ret
, max_agg_items
))
2786 ret
|= propagate_aggregate_lattice (cs
, item
, *aglat
);
2787 aglat
= &(*aglat
)->next
;
2789 else if (dest_plats
->aggs_bottom
)
2793 ret
|= set_chain_of_aglats_contains_variable (*aglat
);
2796 ret
|= set_agg_lats_contain_variable (dest_plats
);
2801 /* Return true if on the way cfrom CS->caller to the final (non-alias and
2802 non-thunk) destination, the call passes through a thunk. */
2805 call_passes_through_thunk_p (cgraph_edge
*cs
)
2807 cgraph_node
*alias_or_thunk
= cs
->callee
;
2808 while (alias_or_thunk
->alias
)
2809 alias_or_thunk
= alias_or_thunk
->get_alias_target ();
2810 return alias_or_thunk
->thunk
.thunk_p
;
2813 /* Propagate constants from the caller to the callee of CS. INFO describes the
2817 propagate_constants_across_call (struct cgraph_edge
*cs
)
2819 class ipa_node_params
*callee_info
;
2820 enum availability availability
;
2821 cgraph_node
*callee
;
2822 class ipa_edge_args
*args
;
2824 int i
, args_count
, parms_count
;
2826 callee
= cs
->callee
->function_symbol (&availability
);
2827 if (!callee
->definition
)
2829 gcc_checking_assert (callee
->has_gimple_body_p ());
2830 callee_info
= IPA_NODE_REF (callee
);
2834 args
= IPA_EDGE_REF (cs
);
2835 parms_count
= ipa_get_param_count (callee_info
);
2836 if (parms_count
== 0)
2839 || !opt_for_fn (cs
->caller
->decl
, flag_ipa_cp
)
2840 || !opt_for_fn (cs
->caller
->decl
, optimize
))
2842 for (i
= 0; i
< parms_count
; i
++)
2843 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
2847 args_count
= ipa_get_cs_argument_count (args
);
2849 /* If this call goes through a thunk we must not propagate to the first (0th)
2850 parameter. However, we might need to uncover a thunk from below a series
2851 of aliases first. */
2852 if (call_passes_through_thunk_p (cs
))
2854 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
2861 for (; (i
< args_count
) && (i
< parms_count
); i
++)
2863 struct ipa_jump_func
*jump_func
= ipa_get_ith_jump_func (args
, i
);
2864 class ipcp_param_lattices
*dest_plats
;
2865 tree param_type
= ipa_get_type (callee_info
, i
);
2867 dest_plats
= ipa_get_parm_lattices (callee_info
, i
);
2868 if (availability
== AVAIL_INTERPOSABLE
)
2869 ret
|= set_all_contains_variable (dest_plats
);
2872 ret
|= propagate_scalar_across_jump_function (cs
, jump_func
,
2873 &dest_plats
->itself
,
2875 ret
|= propagate_context_across_jump_function (cs
, jump_func
, i
,
2876 &dest_plats
->ctxlat
);
2878 |= propagate_bits_across_jump_function (cs
, i
, jump_func
,
2879 &dest_plats
->bits_lattice
);
2880 ret
|= propagate_aggs_across_jump_function (cs
, jump_func
,
2882 if (opt_for_fn (callee
->decl
, flag_ipa_vrp
))
2883 ret
|= propagate_vr_across_jump_function (cs
, jump_func
,
2884 dest_plats
, param_type
);
2886 ret
|= dest_plats
->m_value_range
.set_to_bottom ();
2889 for (; i
< parms_count
; i
++)
2890 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
, i
));
2895 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
2896 KNOWN_CONTEXTS, KNOWN_AGGS or AGG_REPS return the destination. The latter
2897 three can be NULL. If AGG_REPS is not NULL, KNOWN_AGGS is ignored. */
2900 ipa_get_indirect_edge_target_1 (struct cgraph_edge
*ie
,
2901 vec
<tree
> known_csts
,
2902 vec
<ipa_polymorphic_call_context
> known_contexts
,
2903 vec
<ipa_agg_value_set
> known_aggs
,
2904 struct ipa_agg_replacement_value
*agg_reps
,
2907 int param_index
= ie
->indirect_info
->param_index
;
2908 HOST_WIDE_INT anc_offset
;
2912 *speculative
= false;
2914 if (param_index
== -1)
2917 if (!ie
->indirect_info
->polymorphic
)
2921 if (ie
->indirect_info
->agg_contents
)
2924 if (agg_reps
&& ie
->indirect_info
->guaranteed_unmodified
)
2928 if (agg_reps
->index
== param_index
2929 && agg_reps
->offset
== ie
->indirect_info
->offset
2930 && agg_reps
->by_ref
== ie
->indirect_info
->by_ref
)
2932 t
= agg_reps
->value
;
2935 agg_reps
= agg_reps
->next
;
2940 struct ipa_agg_value_set
*agg
;
2941 if (known_aggs
.length () > (unsigned int) param_index
)
2942 agg
= &known_aggs
[param_index
];
2945 bool from_global_constant
;
2946 t
= ipa_find_agg_cst_for_param (agg
,
2947 (unsigned) param_index
2948 < known_csts
.length ()
2949 ? known_csts
[param_index
]
2951 ie
->indirect_info
->offset
,
2952 ie
->indirect_info
->by_ref
,
2953 &from_global_constant
);
2955 && !from_global_constant
2956 && !ie
->indirect_info
->guaranteed_unmodified
)
2960 else if ((unsigned) param_index
< known_csts
.length ())
2961 t
= known_csts
[param_index
];
2964 && TREE_CODE (t
) == ADDR_EXPR
2965 && TREE_CODE (TREE_OPERAND (t
, 0)) == FUNCTION_DECL
)
2966 return TREE_OPERAND (t
, 0);
2971 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize
))
2974 gcc_assert (!ie
->indirect_info
->agg_contents
);
2975 anc_offset
= ie
->indirect_info
->offset
;
2979 /* Try to work out value of virtual table pointer value in replacements. */
2980 if (!t
&& agg_reps
&& !ie
->indirect_info
->by_ref
)
2984 if (agg_reps
->index
== param_index
2985 && agg_reps
->offset
== ie
->indirect_info
->offset
2986 && agg_reps
->by_ref
)
2988 t
= agg_reps
->value
;
2991 agg_reps
= agg_reps
->next
;
2995 /* Try to work out value of virtual table pointer value in known
2996 aggregate values. */
2997 if (!t
&& known_aggs
.length () > (unsigned int) param_index
2998 && !ie
->indirect_info
->by_ref
)
3000 struct ipa_agg_value_set
*agg
= &known_aggs
[param_index
];
3001 t
= ipa_find_agg_cst_for_param (agg
,
3002 (unsigned) param_index
3003 < known_csts
.length ()
3004 ? known_csts
[param_index
] : NULL
,
3005 ie
->indirect_info
->offset
, true);
3008 /* If we found the virtual table pointer, lookup the target. */
3012 unsigned HOST_WIDE_INT offset
;
3013 if (vtable_pointer_value_to_vtable (t
, &vtable
, &offset
))
3016 target
= gimple_get_virt_method_for_vtable (ie
->indirect_info
->otr_token
,
3017 vtable
, offset
, &can_refer
);
3021 || fndecl_built_in_p (target
, BUILT_IN_UNREACHABLE
)
3022 || !possible_polymorphic_call_target_p
3023 (ie
, cgraph_node::get (target
)))
3025 /* Do not speculate builtin_unreachable, it is stupid! */
3026 if (ie
->indirect_info
->vptr_changed
)
3028 target
= ipa_impossible_devirt_target (ie
, target
);
3030 *speculative
= ie
->indirect_info
->vptr_changed
;
3037 /* Do we know the constant value of pointer? */
3038 if (!t
&& (unsigned) param_index
< known_csts
.length ())
3039 t
= known_csts
[param_index
];
3041 gcc_checking_assert (!t
|| TREE_CODE (t
) != TREE_BINFO
);
3043 ipa_polymorphic_call_context context
;
3044 if (known_contexts
.length () > (unsigned int) param_index
)
3046 context
= known_contexts
[param_index
];
3047 context
.offset_by (anc_offset
);
3048 if (ie
->indirect_info
->vptr_changed
)
3049 context
.possible_dynamic_type_change (ie
->in_polymorphic_cdtor
,
3050 ie
->indirect_info
->otr_type
);
3053 ipa_polymorphic_call_context ctx2
= ipa_polymorphic_call_context
3054 (t
, ie
->indirect_info
->otr_type
, anc_offset
);
3055 if (!ctx2
.useless_p ())
3056 context
.combine_with (ctx2
, ie
->indirect_info
->otr_type
);
3061 context
= ipa_polymorphic_call_context (t
, ie
->indirect_info
->otr_type
,
3063 if (ie
->indirect_info
->vptr_changed
)
3064 context
.possible_dynamic_type_change (ie
->in_polymorphic_cdtor
,
3065 ie
->indirect_info
->otr_type
);
3070 vec
<cgraph_node
*>targets
;
3073 targets
= possible_polymorphic_call_targets
3074 (ie
->indirect_info
->otr_type
,
3075 ie
->indirect_info
->otr_token
,
3077 if (!final
|| targets
.length () > 1)
3079 struct cgraph_node
*node
;
3082 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize_speculatively
)
3083 || ie
->speculative
|| !ie
->maybe_hot_p ())
3085 node
= try_speculative_devirtualization (ie
->indirect_info
->otr_type
,
3086 ie
->indirect_info
->otr_token
,
3090 *speculative
= true;
3091 target
= node
->decl
;
3098 *speculative
= false;
3099 if (targets
.length () == 1)
3100 target
= targets
[0]->decl
;
3102 target
= ipa_impossible_devirt_target (ie
, NULL_TREE
);
3105 if (target
&& !possible_polymorphic_call_target_p (ie
,
3106 cgraph_node::get (target
)))
3110 target
= ipa_impossible_devirt_target (ie
, target
);
3117 /* If an indirect edge IE can be turned into a direct one based on KNOWN_CSTS,
3118 KNOWN_CONTEXTS (which can be vNULL) or KNOWN_AGGS (which also can be vNULL)
3119 return the destination. */
3122 ipa_get_indirect_edge_target (struct cgraph_edge
*ie
,
3123 vec
<tree
> known_csts
,
3124 vec
<ipa_polymorphic_call_context
> known_contexts
,
3125 vec
<ipa_agg_value_set
> known_aggs
,
3128 return ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
3129 known_aggs
, NULL
, speculative
);
3132 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
3133 and KNOWN_CONTEXTS. */
3136 devirtualization_time_bonus (struct cgraph_node
*node
,
3137 vec
<tree
> known_csts
,
3138 vec
<ipa_polymorphic_call_context
> known_contexts
,
3139 vec
<ipa_agg_value_set
> known_aggs
)
3141 struct cgraph_edge
*ie
;
3144 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
3146 struct cgraph_node
*callee
;
3147 class ipa_fn_summary
*isummary
;
3148 enum availability avail
;
3152 target
= ipa_get_indirect_edge_target (ie
, known_csts
, known_contexts
,
3153 known_aggs
, &speculative
);
3157 /* Only bare minimum benefit for clearly un-inlineable targets. */
3159 callee
= cgraph_node::get (target
);
3160 if (!callee
|| !callee
->definition
)
3162 callee
= callee
->function_symbol (&avail
);
3163 if (avail
< AVAIL_AVAILABLE
)
3165 isummary
= ipa_fn_summaries
->get (callee
);
3166 if (!isummary
|| !isummary
->inlinable
)
3169 int size
= ipa_size_summaries
->get (callee
)->size
;
3170 /* FIXME: The values below need re-considering and perhaps also
3171 integrating into the cost metrics, at lest in some very basic way. */
3172 int max_inline_insns_auto
3173 = opt_for_fn (callee
->decl
, param_max_inline_insns_auto
);
3174 if (size
<= max_inline_insns_auto
/ 4)
3175 res
+= 31 / ((int)speculative
+ 1);
3176 else if (size
<= max_inline_insns_auto
/ 2)
3177 res
+= 15 / ((int)speculative
+ 1);
3178 else if (size
<= max_inline_insns_auto
3179 || DECL_DECLARED_INLINE_P (callee
->decl
))
3180 res
+= 7 / ((int)speculative
+ 1);
3186 /* Return time bonus incurred because of HINTS. */
3189 hint_time_bonus (cgraph_node
*node
, ipa_hints hints
)
3192 if (hints
& (INLINE_HINT_loop_iterations
| INLINE_HINT_loop_stride
))
3193 result
+= opt_for_fn (node
->decl
, param_ipa_cp_loop_hint_bonus
);
3197 /* If there is a reason to penalize the function described by INFO in the
3198 cloning goodness evaluation, do so. */
3200 static inline int64_t
3201 incorporate_penalties (cgraph_node
*node
, ipa_node_params
*info
,
3204 if (info
->node_within_scc
&& !info
->node_is_self_scc
)
3205 evaluation
= (evaluation
3206 * (100 - opt_for_fn (node
->decl
,
3207 param_ipa_cp_recursion_penalty
))) / 100;
3209 if (info
->node_calling_single_call
)
3210 evaluation
= (evaluation
3211 * (100 - opt_for_fn (node
->decl
,
3212 param_ipa_cp_single_call_penalty
)))
3218 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
3219 and SIZE_COST and with the sum of frequencies of incoming edges to the
3220 potential new clone in FREQUENCIES. */
3223 good_cloning_opportunity_p (struct cgraph_node
*node
, int time_benefit
,
3224 int freq_sum
, profile_count count_sum
, int size_cost
)
3226 if (time_benefit
== 0
3227 || !opt_for_fn (node
->decl
, flag_ipa_cp_clone
)
3228 || node
->optimize_for_size_p ())
3231 gcc_assert (size_cost
> 0);
3233 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3234 int eval_threshold
= opt_for_fn (node
->decl
, param_ipa_cp_eval_threshold
);
3235 if (max_count
> profile_count::zero ())
3237 int factor
= RDIV (count_sum
.probability_in
3238 (max_count
).to_reg_br_prob_base ()
3239 * 1000, REG_BR_PROB_BASE
);
3240 int64_t evaluation
= (((int64_t) time_benefit
* factor
)
3242 evaluation
= incorporate_penalties (node
, info
, evaluation
);
3244 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3246 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
3247 "size: %i, count_sum: ", time_benefit
, size_cost
);
3248 count_sum
.dump (dump_file
);
3249 fprintf (dump_file
, "%s%s) -> evaluation: " "%" PRId64
3250 ", threshold: %i\n",
3251 info
->node_within_scc
3252 ? (info
->node_is_self_scc
? ", self_scc" : ", scc") : "",
3253 info
->node_calling_single_call
? ", single_call" : "",
3254 evaluation
, eval_threshold
);
3257 return evaluation
>= eval_threshold
;
3261 int64_t evaluation
= (((int64_t) time_benefit
* freq_sum
)
3263 evaluation
= incorporate_penalties (node
, info
, evaluation
);
3265 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3266 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
3267 "size: %i, freq_sum: %i%s%s) -> evaluation: "
3268 "%" PRId64
", threshold: %i\n",
3269 time_benefit
, size_cost
, freq_sum
,
3270 info
->node_within_scc
3271 ? (info
->node_is_self_scc
? ", self_scc" : ", scc") : "",
3272 info
->node_calling_single_call
? ", single_call" : "",
3273 evaluation
, eval_threshold
);
3275 return evaluation
>= eval_threshold
;
3279 /* Return all context independent values from aggregate lattices in PLATS in a
3280 vector. Return NULL if there are none. */
3282 static vec
<ipa_agg_value
>
3283 context_independent_aggregate_values (class ipcp_param_lattices
*plats
)
3285 vec
<ipa_agg_value
> res
= vNULL
;
3287 if (plats
->aggs_bottom
3288 || plats
->aggs_contain_variable
3289 || plats
->aggs_count
== 0)
3292 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
;
3294 aglat
= aglat
->next
)
3295 if (aglat
->is_single_const ())
3297 struct ipa_agg_value item
;
3298 item
.offset
= aglat
->offset
;
3299 item
.value
= aglat
->values
->value
;
3300 res
.safe_push (item
);
3305 /* Allocate KNOWN_CSTS, KNOWN_CONTEXTS and, if non-NULL, KNOWN_AGGS and
3306 populate them with values of parameters that are known independent of the
3307 context. INFO describes the function. If REMOVABLE_PARAMS_COST is
3308 non-NULL, the movement cost of all removable parameters will be stored in
3312 gather_context_independent_values (class ipa_node_params
*info
,
3313 vec
<tree
> *known_csts
,
3314 vec
<ipa_polymorphic_call_context
>
3316 vec
<ipa_agg_value_set
> *known_aggs
,
3317 int *removable_params_cost
)
3319 int i
, count
= ipa_get_param_count (info
);
3322 known_csts
->create (0);
3323 known_contexts
->create (0);
3324 known_csts
->safe_grow_cleared (count
);
3325 known_contexts
->safe_grow_cleared (count
);
3328 known_aggs
->create (0);
3329 known_aggs
->safe_grow_cleared (count
);
3332 if (removable_params_cost
)
3333 *removable_params_cost
= 0;
3335 for (i
= 0; i
< count
; i
++)
3337 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3338 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
3340 if (lat
->is_single_const ())
3342 ipcp_value
<tree
> *val
= lat
->values
;
3343 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
3344 (*known_csts
)[i
] = val
->value
;
3345 if (removable_params_cost
)
3346 *removable_params_cost
3347 += estimate_move_cost (TREE_TYPE (val
->value
), false);
3350 else if (removable_params_cost
3351 && !ipa_is_param_used (info
, i
))
3352 *removable_params_cost
3353 += ipa_get_param_move_cost (info
, i
);
3355 if (!ipa_is_param_used (info
, i
))
3358 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
3359 /* Do not account known context as reason for cloning. We can see
3360 if it permits devirtualization. */
3361 if (ctxlat
->is_single_const ())
3362 (*known_contexts
)[i
] = ctxlat
->values
->value
;
3366 vec
<ipa_agg_value
> agg_items
;
3367 struct ipa_agg_value_set
*agg
;
3369 agg_items
= context_independent_aggregate_values (plats
);
3370 agg
= &(*known_aggs
)[i
];
3371 agg
->items
= agg_items
;
3372 agg
->by_ref
= plats
->aggs_by_ref
;
3373 ret
|= !agg_items
.is_empty ();
3380 /* Perform time and size measurement of NODE with the context given in
3381 KNOWN_CSTS, KNOWN_CONTEXTS and KNOWN_AGGS, calculate the benefit and cost
3382 given BASE_TIME of the node without specialization, REMOVABLE_PARAMS_COST of
3383 all context-independent removable parameters and EST_MOVE_COST of estimated
3384 movement of the considered parameter and store it into VAL. */
3387 perform_estimation_of_a_value (cgraph_node
*node
, vec
<tree
> known_csts
,
3388 vec
<ipa_polymorphic_call_context
> known_contexts
,
3389 vec
<ipa_agg_value_set
> known_aggs
,
3390 int removable_params_cost
,
3391 int est_move_cost
, ipcp_value_base
*val
)
3393 int size
, time_benefit
;
3394 sreal time
, base_time
;
3397 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
3398 known_aggs
, &size
, &time
,
3399 &base_time
, &hints
);
3401 if (base_time
> 65535)
3404 /* Extern inline functions have no cloning local time benefits because they
3405 will be inlined anyway. The only reason to clone them is if it enables
3406 optimization in any of the functions they call. */
3407 if (DECL_EXTERNAL (node
->decl
) && DECL_DECLARED_INLINE_P (node
->decl
))
3410 time_benefit
= base_time
.to_int ()
3411 + devirtualization_time_bonus (node
, known_csts
, known_contexts
,
3413 + hint_time_bonus (node
, hints
)
3414 + removable_params_cost
+ est_move_cost
;
3416 gcc_checking_assert (size
>=0);
3417 /* The inliner-heuristics based estimates may think that in certain
3418 contexts some functions do not have any size at all but we want
3419 all specializations to have at least a tiny cost, not least not to
3424 val
->local_time_benefit
= time_benefit
;
3425 val
->local_size_cost
= size
;
3428 /* Get the overall limit oof growth based on parameters extracted from growth.
3429 it does not really make sense to mix functions with different overall growth
3430 limits but it is possible and if it happens, we do not want to select one
3434 get_max_overall_size (cgraph_node
*node
)
3436 long max_new_size
= orig_overall_size
;
3437 long large_unit
= opt_for_fn (node
->decl
, param_large_unit_insns
);
3438 if (max_new_size
< large_unit
)
3439 max_new_size
= large_unit
;
3440 int unit_growth
= opt_for_fn (node
->decl
, param_ipa_cp_unit_growth
);
3441 max_new_size
+= max_new_size
* unit_growth
/ 100 + 1;
3442 return max_new_size
;
3445 /* Iterate over known values of parameters of NODE and estimate the local
3446 effects in terms of time and size they have. */
3449 estimate_local_effects (struct cgraph_node
*node
)
3451 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3452 int i
, count
= ipa_get_param_count (info
);
3453 vec
<tree
> known_csts
;
3454 vec
<ipa_polymorphic_call_context
> known_contexts
;
3455 vec
<ipa_agg_value_set
> known_aggs
;
3457 int removable_params_cost
;
3459 if (!count
|| !ipcp_versionable_function_p (node
))
3462 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3463 fprintf (dump_file
, "\nEstimating effects for %s.\n", node
->dump_name ());
3465 always_const
= gather_context_independent_values (info
, &known_csts
,
3466 &known_contexts
, &known_aggs
,
3467 &removable_params_cost
);
3468 int devirt_bonus
= devirtualization_time_bonus (node
, known_csts
,
3469 known_contexts
, known_aggs
);
3470 if (always_const
|| devirt_bonus
3471 || (removable_params_cost
&& node
->can_change_signature
))
3473 struct caller_statistics stats
;
3475 sreal time
, base_time
;
3478 init_caller_stats (&stats
);
3479 node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
3481 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
3482 known_aggs
, &size
, &time
,
3483 &base_time
, &hints
);
3484 time
-= devirt_bonus
;
3485 time
-= hint_time_bonus (node
, hints
);
3486 time
-= removable_params_cost
;
3487 size
-= stats
.n_calls
* removable_params_cost
;
3490 fprintf (dump_file
, " - context independent values, size: %i, "
3491 "time_benefit: %f\n", size
, (base_time
- time
).to_double ());
3493 if (size
<= 0 || node
->local
)
3495 info
->do_clone_for_all_contexts
= true;
3498 fprintf (dump_file
, " Decided to specialize for all "
3499 "known contexts, code not going to grow.\n");
3501 else if (good_cloning_opportunity_p (node
,
3502 MIN ((base_time
- time
).to_int (),
3504 stats
.freq_sum
, stats
.count_sum
,
3507 if (size
+ overall_size
<= get_max_overall_size (node
))
3509 info
->do_clone_for_all_contexts
= true;
3510 overall_size
+= size
;
3513 fprintf (dump_file
, " Decided to specialize for all "
3514 "known contexts, growth deemed beneficial.\n");
3516 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3517 fprintf (dump_file
, " Not cloning for all contexts because "
3518 "maximum unit size would be reached with %li.\n",
3519 size
+ overall_size
);
3521 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3522 fprintf (dump_file
, " Not cloning for all contexts because "
3523 "!good_cloning_opportunity_p.\n");
3527 for (i
= 0; i
< count
; i
++)
3529 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3530 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
3531 ipcp_value
<tree
> *val
;
3538 for (val
= lat
->values
; val
; val
= val
->next
)
3540 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
3541 known_csts
[i
] = val
->value
;
3543 int emc
= estimate_move_cost (TREE_TYPE (val
->value
), true);
3544 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
3546 removable_params_cost
, emc
, val
);
3548 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3550 fprintf (dump_file
, " - estimates for value ");
3551 print_ipcp_constant_value (dump_file
, val
->value
);
3552 fprintf (dump_file
, " for ");
3553 ipa_dump_param (dump_file
, info
, i
);
3554 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
3555 val
->local_time_benefit
, val
->local_size_cost
);
3558 known_csts
[i
] = NULL_TREE
;
3561 for (i
= 0; i
< count
; i
++)
3563 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3565 if (!plats
->virt_call
)
3568 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
3569 ipcp_value
<ipa_polymorphic_call_context
> *val
;
3573 || !known_contexts
[i
].useless_p ())
3576 for (val
= ctxlat
->values
; val
; val
= val
->next
)
3578 known_contexts
[i
] = val
->value
;
3579 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
3581 removable_params_cost
, 0, val
);
3583 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3585 fprintf (dump_file
, " - estimates for polymorphic context ");
3586 print_ipcp_constant_value (dump_file
, val
->value
);
3587 fprintf (dump_file
, " for ");
3588 ipa_dump_param (dump_file
, info
, i
);
3589 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
3590 val
->local_time_benefit
, val
->local_size_cost
);
3593 known_contexts
[i
] = ipa_polymorphic_call_context ();
3596 for (i
= 0; i
< count
; i
++)
3598 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3599 struct ipa_agg_value_set
*agg
;
3600 struct ipcp_agg_lattice
*aglat
;
3602 if (plats
->aggs_bottom
|| !plats
->aggs
)
3605 agg
= &known_aggs
[i
];
3606 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3608 ipcp_value
<tree
> *val
;
3609 if (aglat
->bottom
|| !aglat
->values
3610 /* If the following is true, the one value is in known_aggs. */
3611 || (!plats
->aggs_contain_variable
3612 && aglat
->is_single_const ()))
3615 for (val
= aglat
->values
; val
; val
= val
->next
)
3617 struct ipa_agg_value item
;
3619 item
.offset
= aglat
->offset
;
3620 item
.value
= val
->value
;
3621 agg
->items
.safe_push (item
);
3623 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
3625 removable_params_cost
, 0, val
);
3627 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3629 fprintf (dump_file
, " - estimates for value ");
3630 print_ipcp_constant_value (dump_file
, val
->value
);
3631 fprintf (dump_file
, " for ");
3632 ipa_dump_param (dump_file
, info
, i
);
3633 fprintf (dump_file
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
3634 "]: time_benefit: %i, size: %i\n",
3635 plats
->aggs_by_ref
? "ref " : "",
3637 val
->local_time_benefit
, val
->local_size_cost
);
3645 known_csts
.release ();
3646 known_contexts
.release ();
3647 ipa_release_agg_values (known_aggs
);
3651 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
3652 topological sort of values. */
3654 template <typename valtype
>
3656 value_topo_info
<valtype
>::add_val (ipcp_value
<valtype
> *cur_val
)
3658 ipcp_value_source
<valtype
> *src
;
3664 cur_val
->dfs
= dfs_counter
;
3665 cur_val
->low_link
= dfs_counter
;
3667 cur_val
->topo_next
= stack
;
3669 cur_val
->on_stack
= true;
3671 for (src
= cur_val
->sources
; src
; src
= src
->next
)
3674 if (src
->val
->dfs
== 0)
3677 if (src
->val
->low_link
< cur_val
->low_link
)
3678 cur_val
->low_link
= src
->val
->low_link
;
3680 else if (src
->val
->on_stack
3681 && src
->val
->dfs
< cur_val
->low_link
)
3682 cur_val
->low_link
= src
->val
->dfs
;
3685 if (cur_val
->dfs
== cur_val
->low_link
)
3687 ipcp_value
<valtype
> *v
, *scc_list
= NULL
;
3692 stack
= v
->topo_next
;
3693 v
->on_stack
= false;
3695 v
->scc_next
= scc_list
;
3698 while (v
!= cur_val
);
3700 cur_val
->topo_next
= values_topo
;
3701 values_topo
= cur_val
;
3705 /* Add all values in lattices associated with NODE to the topological sort if
3706 they are not there yet. */
3709 add_all_node_vals_to_toposort (cgraph_node
*node
, ipa_topo_info
*topo
)
3711 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3712 int i
, count
= ipa_get_param_count (info
);
3714 for (i
= 0; i
< count
; i
++)
3716 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3717 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
3718 struct ipcp_agg_lattice
*aglat
;
3722 ipcp_value
<tree
> *val
;
3723 for (val
= lat
->values
; val
; val
= val
->next
)
3724 topo
->constants
.add_val (val
);
3727 if (!plats
->aggs_bottom
)
3728 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3731 ipcp_value
<tree
> *val
;
3732 for (val
= aglat
->values
; val
; val
= val
->next
)
3733 topo
->constants
.add_val (val
);
3736 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
3737 if (!ctxlat
->bottom
)
3739 ipcp_value
<ipa_polymorphic_call_context
> *ctxval
;
3740 for (ctxval
= ctxlat
->values
; ctxval
; ctxval
= ctxval
->next
)
3741 topo
->contexts
.add_val (ctxval
);
3746 /* One pass of constants propagation along the call graph edges, from callers
3747 to callees (requires topological ordering in TOPO), iterate over strongly
3748 connected components. */
3751 propagate_constants_topo (class ipa_topo_info
*topo
)
3755 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
3758 struct cgraph_node
*v
, *node
= topo
->order
[i
];
3759 vec
<cgraph_node
*> cycle_nodes
= ipa_get_nodes_in_cycle (node
);
3761 /* First, iteratively propagate within the strongly connected component
3762 until all lattices stabilize. */
3763 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
3764 if (v
->has_gimple_body_p ())
3766 if (opt_for_fn (v
->decl
, flag_ipa_cp
)
3767 && opt_for_fn (v
->decl
, optimize
))
3768 push_node_to_stack (topo
, v
);
3769 /* When V is not optimized, we can not push it to stack, but
3770 still we need to set all its callees lattices to bottom. */
3773 for (cgraph_edge
*cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3774 propagate_constants_across_call (cs
);
3778 v
= pop_node_from_stack (topo
);
3781 struct cgraph_edge
*cs
;
3782 class ipa_node_params
*info
= NULL
;
3783 bool self_scc
= true;
3785 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3786 if (ipa_edge_within_scc (cs
))
3788 cgraph_node
*callee
= cs
->callee
->function_symbol ();
3795 info
= IPA_NODE_REF (v
);
3796 info
->node_within_scc
= true;
3799 if (propagate_constants_across_call (cs
))
3800 push_node_to_stack (topo
, callee
);
3804 info
->node_is_self_scc
= self_scc
;
3806 v
= pop_node_from_stack (topo
);
3809 /* Afterwards, propagate along edges leading out of the SCC, calculates
3810 the local effects of the discovered constants and all valid values to
3811 their topological sort. */
3812 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
3813 if (v
->has_gimple_body_p ()
3814 && opt_for_fn (v
->decl
, flag_ipa_cp
)
3815 && opt_for_fn (v
->decl
, optimize
))
3817 struct cgraph_edge
*cs
;
3819 estimate_local_effects (v
);
3820 add_all_node_vals_to_toposort (v
, topo
);
3821 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3822 if (!ipa_edge_within_scc (cs
))
3823 propagate_constants_across_call (cs
);
3825 cycle_nodes
.release ();
3830 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
3831 the bigger one if otherwise. */
3834 safe_add (int a
, int b
)
3836 if (a
> INT_MAX
/2 || b
> INT_MAX
/2)
3837 return a
> b
? a
: b
;
3843 /* Propagate the estimated effects of individual values along the topological
3844 from the dependent values to those they depend on. */
3846 template <typename valtype
>
3848 value_topo_info
<valtype
>::propagate_effects ()
3850 ipcp_value
<valtype
> *base
;
3852 for (base
= values_topo
; base
; base
= base
->topo_next
)
3854 ipcp_value_source
<valtype
> *src
;
3855 ipcp_value
<valtype
> *val
;
3856 int time
= 0, size
= 0;
3858 for (val
= base
; val
; val
= val
->scc_next
)
3860 time
= safe_add (time
,
3861 val
->local_time_benefit
+ val
->prop_time_benefit
);
3862 size
= safe_add (size
, val
->local_size_cost
+ val
->prop_size_cost
);
3865 for (val
= base
; val
; val
= val
->scc_next
)
3866 for (src
= val
->sources
; src
; src
= src
->next
)
3868 && src
->cs
->maybe_hot_p ())
3870 src
->val
->prop_time_benefit
= safe_add (time
,
3871 src
->val
->prop_time_benefit
);
3872 src
->val
->prop_size_cost
= safe_add (size
,
3873 src
->val
->prop_size_cost
);
3879 /* Propagate constants, polymorphic contexts and their effects from the
3880 summaries interprocedurally. */
3883 ipcp_propagate_stage (class ipa_topo_info
*topo
)
3885 struct cgraph_node
*node
;
3888 fprintf (dump_file
, "\n Propagating constants:\n\n");
3890 max_count
= profile_count::uninitialized ();
3892 FOR_EACH_DEFINED_FUNCTION (node
)
3894 if (node
->has_gimple_body_p ()
3895 && opt_for_fn (node
->decl
, flag_ipa_cp
)
3896 && opt_for_fn (node
->decl
, optimize
))
3898 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3899 determine_versionability (node
, info
);
3900 info
->lattices
= XCNEWVEC (class ipcp_param_lattices
,
3901 ipa_get_param_count (info
));
3902 initialize_node_lattices (node
);
3904 ipa_size_summary
*s
= ipa_size_summaries
->get (node
);
3905 if (node
->definition
&& !node
->alias
&& s
!= NULL
)
3906 overall_size
+= s
->self_size
;
3907 max_count
= max_count
.max (node
->count
.ipa ());
3910 orig_overall_size
= overall_size
;
3913 fprintf (dump_file
, "\noverall_size: %li\n", overall_size
);
3915 propagate_constants_topo (topo
);
3917 ipcp_verify_propagated_values ();
3918 topo
->constants
.propagate_effects ();
3919 topo
->contexts
.propagate_effects ();
3923 fprintf (dump_file
, "\nIPA lattices after all propagation:\n");
3924 print_all_lattices (dump_file
, (dump_flags
& TDF_DETAILS
), true);
3928 /* Discover newly direct outgoing edges from NODE which is a new clone with
3929 known KNOWN_CSTS and make them direct. */
3932 ipcp_discover_new_direct_edges (struct cgraph_node
*node
,
3933 vec
<tree
> known_csts
,
3934 vec
<ipa_polymorphic_call_context
>
3936 struct ipa_agg_replacement_value
*aggvals
)
3938 struct cgraph_edge
*ie
, *next_ie
;
3941 for (ie
= node
->indirect_calls
; ie
; ie
= next_ie
)
3946 next_ie
= ie
->next_callee
;
3947 target
= ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
3948 vNULL
, aggvals
, &speculative
);
3951 bool agg_contents
= ie
->indirect_info
->agg_contents
;
3952 bool polymorphic
= ie
->indirect_info
->polymorphic
;
3953 int param_index
= ie
->indirect_info
->param_index
;
3954 struct cgraph_edge
*cs
= ipa_make_edge_direct_to_target (ie
, target
,
3958 if (cs
&& !agg_contents
&& !polymorphic
)
3960 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3961 int c
= ipa_get_controlled_uses (info
, param_index
);
3962 if (c
!= IPA_UNDESCRIBED_USE
)
3964 struct ipa_ref
*to_del
;
3967 ipa_set_controlled_uses (info
, param_index
, c
);
3968 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3969 fprintf (dump_file
, " controlled uses count of param "
3970 "%i bumped down to %i\n", param_index
, c
);
3972 && (to_del
= node
->find_reference (cs
->callee
, NULL
, 0)))
3974 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3975 fprintf (dump_file
, " and even removing its "
3976 "cloning-created reference\n");
3977 to_del
->remove_reference ();
3983 /* Turning calls to direct calls will improve overall summary. */
3985 ipa_update_overall_fn_summary (node
);
3988 class edge_clone_summary
;
3989 static call_summary
<edge_clone_summary
*> *edge_clone_summaries
= NULL
;
3991 /* Edge clone summary. */
3993 class edge_clone_summary
3996 /* Default constructor. */
3997 edge_clone_summary (): prev_clone (NULL
), next_clone (NULL
) {}
3999 /* Default destructor. */
4000 ~edge_clone_summary ()
4003 edge_clone_summaries
->get (prev_clone
)->next_clone
= next_clone
;
4005 edge_clone_summaries
->get (next_clone
)->prev_clone
= prev_clone
;
4008 cgraph_edge
*prev_clone
;
4009 cgraph_edge
*next_clone
;
4012 class edge_clone_summary_t
:
4013 public call_summary
<edge_clone_summary
*>
4016 edge_clone_summary_t (symbol_table
*symtab
):
4017 call_summary
<edge_clone_summary
*> (symtab
)
4019 m_initialize_when_cloning
= true;
4022 virtual void duplicate (cgraph_edge
*src_edge
, cgraph_edge
*dst_edge
,
4023 edge_clone_summary
*src_data
,
4024 edge_clone_summary
*dst_data
);
4027 /* Edge duplication hook. */
4030 edge_clone_summary_t::duplicate (cgraph_edge
*src_edge
, cgraph_edge
*dst_edge
,
4031 edge_clone_summary
*src_data
,
4032 edge_clone_summary
*dst_data
)
4034 if (src_data
->next_clone
)
4035 edge_clone_summaries
->get (src_data
->next_clone
)->prev_clone
= dst_edge
;
4036 dst_data
->prev_clone
= src_edge
;
4037 dst_data
->next_clone
= src_data
->next_clone
;
4038 src_data
->next_clone
= dst_edge
;
4041 /* Return true is CS calls DEST or its clone for all contexts. When
4042 ALLOW_RECURSION_TO_CLONE is false, also return false for self-recursive
4043 edges from/to an all-context clone. */
4046 calls_same_node_or_its_all_contexts_clone_p (cgraph_edge
*cs
, cgraph_node
*dest
,
4047 bool allow_recursion_to_clone
)
4049 enum availability availability
;
4050 cgraph_node
*callee
= cs
->callee
->function_symbol (&availability
);
4052 if (availability
<= AVAIL_INTERPOSABLE
)
4056 if (!allow_recursion_to_clone
&& cs
->caller
== callee
)
4059 class ipa_node_params
*info
= IPA_NODE_REF (callee
);
4060 return info
->is_all_contexts_clone
&& info
->ipcp_orig_node
== dest
;
4063 /* Return true if edge CS does bring about the value described by SRC to
4064 DEST_VAL of node DEST or its clone for all contexts. */
4067 cgraph_edge_brings_value_p (cgraph_edge
*cs
, ipcp_value_source
<tree
> *src
,
4068 cgraph_node
*dest
, ipcp_value
<tree
> *dest_val
)
4070 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4072 if (!calls_same_node_or_its_all_contexts_clone_p (cs
, dest
, !src
->val
)
4073 || caller_info
->node_dead
)
4079 if (caller_info
->ipcp_orig_node
)
4082 if (src
->offset
== -1)
4083 t
= caller_info
->known_csts
[src
->index
];
4085 t
= get_clone_agg_value (cs
->caller
, src
->offset
, src
->index
);
4086 return (t
!= NULL_TREE
4087 && values_equal_for_ipcp_p (src
->val
->value
, t
));
4091 if (src
->val
== dest_val
)
4094 struct ipcp_agg_lattice
*aglat
;
4095 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
4097 if (src
->offset
== -1)
4098 return (plats
->itself
.is_single_const ()
4099 && values_equal_for_ipcp_p (src
->val
->value
,
4100 plats
->itself
.values
->value
));
4103 if (plats
->aggs_bottom
|| plats
->aggs_contain_variable
)
4105 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
4106 if (aglat
->offset
== src
->offset
)
4107 return (aglat
->is_single_const ()
4108 && values_equal_for_ipcp_p (src
->val
->value
,
4109 aglat
->values
->value
));
4115 /* Return true if edge CS does bring about the value described by SRC to
4116 DST_VAL of node DEST or its clone for all contexts. */
4119 cgraph_edge_brings_value_p (cgraph_edge
*cs
,
4120 ipcp_value_source
<ipa_polymorphic_call_context
> *src
,
4122 ipcp_value
<ipa_polymorphic_call_context
> *)
4124 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4126 if (!calls_same_node_or_its_all_contexts_clone_p (cs
, dest
, true)
4127 || caller_info
->node_dead
)
4132 if (caller_info
->ipcp_orig_node
)
4133 return (caller_info
->known_contexts
.length () > (unsigned) src
->index
)
4134 && values_equal_for_ipcp_p (src
->val
->value
,
4135 caller_info
->known_contexts
[src
->index
]);
4137 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
4139 return plats
->ctxlat
.is_single_const ()
4140 && values_equal_for_ipcp_p (src
->val
->value
,
4141 plats
->ctxlat
.values
->value
);
4144 /* Get the next clone in the linked list of clones of an edge. */
4146 static inline struct cgraph_edge
*
4147 get_next_cgraph_edge_clone (struct cgraph_edge
*cs
)
4149 edge_clone_summary
*s
= edge_clone_summaries
->get (cs
);
4150 return s
!= NULL
? s
->next_clone
: NULL
;
4153 /* Given VAL that is intended for DEST, iterate over all its sources and if any
4154 of them is viable and hot, return true. In that case, for those that still
4155 hold, add their edge frequency and their number into *FREQUENCY and
4156 *CALLER_COUNT respectively. */
4158 template <typename valtype
>
4160 get_info_about_necessary_edges (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
4162 profile_count
*count_sum
, int *caller_count
)
4164 ipcp_value_source
<valtype
> *src
;
4165 int freq
= 0, count
= 0;
4166 profile_count cnt
= profile_count::zero ();
4168 bool non_self_recursive
= false;
4170 for (src
= val
->sources
; src
; src
= src
->next
)
4172 struct cgraph_edge
*cs
= src
->cs
;
4175 if (cgraph_edge_brings_value_p (cs
, src
, dest
, val
))
4178 freq
+= cs
->frequency ();
4179 if (cs
->count
.ipa ().initialized_p ())
4180 cnt
+= cs
->count
.ipa ();
4181 hot
|= cs
->maybe_hot_p ();
4182 if (cs
->caller
!= dest
)
4183 non_self_recursive
= true;
4185 cs
= get_next_cgraph_edge_clone (cs
);
4189 /* If the only edges bringing a value are self-recursive ones, do not bother
4191 if (!non_self_recursive
)
4196 *caller_count
= count
;
4198 if (!hot
&& IPA_NODE_REF (dest
)->node_within_scc
)
4200 struct cgraph_edge
*cs
;
4202 /* Cold non-SCC source edge could trigger hot recursive execution of
4203 function. Consider the case as hot and rely on following cost model
4204 computation to further select right one. */
4205 for (cs
= dest
->callers
; cs
; cs
= cs
->next_caller
)
4206 if (cs
->caller
== dest
&& cs
->maybe_hot_p ())
4213 /* Given a NODE, and a set of its CALLERS, try to adjust order of the callers
4214 to let a non-self-recursive caller be the first element. Thus, we can
4215 simplify intersecting operations on values that arrive from all of these
4216 callers, especially when there exists self-recursive call. Return true if
4217 this kind of adjustment is possible. */
4220 adjust_callers_for_value_intersection (vec
<cgraph_edge
*> callers
,
4223 for (unsigned i
= 0; i
< callers
.length (); i
++)
4225 cgraph_edge
*cs
= callers
[i
];
4227 if (cs
->caller
!= node
)
4231 callers
[i
] = callers
[0];
4240 /* Return a vector of incoming edges that do bring value VAL to node DEST. It
4241 is assumed their number is known and equal to CALLER_COUNT. */
4243 template <typename valtype
>
4244 static vec
<cgraph_edge
*>
4245 gather_edges_for_value (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
4248 ipcp_value_source
<valtype
> *src
;
4249 vec
<cgraph_edge
*> ret
;
4251 ret
.create (caller_count
);
4252 for (src
= val
->sources
; src
; src
= src
->next
)
4254 struct cgraph_edge
*cs
= src
->cs
;
4257 if (cgraph_edge_brings_value_p (cs
, src
, dest
, val
))
4258 ret
.quick_push (cs
);
4259 cs
= get_next_cgraph_edge_clone (cs
);
4263 if (caller_count
> 1)
4264 adjust_callers_for_value_intersection (ret
, dest
);
4269 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
4270 Return it or NULL if for some reason it cannot be created. */
4272 static struct ipa_replace_map
*
4273 get_replacement_map (class ipa_node_params
*info
, tree value
, int parm_num
)
4275 struct ipa_replace_map
*replace_map
;
4277 replace_map
= ggc_alloc
<ipa_replace_map
> ();
4280 fprintf (dump_file
, " replacing ");
4281 ipa_dump_param (dump_file
, info
, parm_num
);
4283 fprintf (dump_file
, " with const ");
4284 print_generic_expr (dump_file
, value
);
4285 fprintf (dump_file
, "\n");
4287 replace_map
->parm_num
= parm_num
;
4288 replace_map
->new_tree
= value
;
4292 /* Dump new profiling counts */
4295 dump_profile_updates (struct cgraph_node
*orig_node
,
4296 struct cgraph_node
*new_node
)
4298 struct cgraph_edge
*cs
;
4300 fprintf (dump_file
, " setting count of the specialized node to ");
4301 new_node
->count
.dump (dump_file
);
4302 fprintf (dump_file
, "\n");
4303 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
4305 fprintf (dump_file
, " edge to %s has count ",
4306 cs
->callee
->dump_name ());
4307 cs
->count
.dump (dump_file
);
4308 fprintf (dump_file
, "\n");
4311 fprintf (dump_file
, " setting count of the original node to ");
4312 orig_node
->count
.dump (dump_file
);
4313 fprintf (dump_file
, "\n");
4314 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
4316 fprintf (dump_file
, " edge to %s is left with ",
4317 cs
->callee
->dump_name ());
4318 cs
->count
.dump (dump_file
);
4319 fprintf (dump_file
, "\n");
4323 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
4324 their profile information to reflect this. */
4327 update_profiling_info (struct cgraph_node
*orig_node
,
4328 struct cgraph_node
*new_node
)
4330 struct cgraph_edge
*cs
;
4331 struct caller_statistics stats
;
4332 profile_count new_sum
, orig_sum
;
4333 profile_count remainder
, orig_node_count
= orig_node
->count
;
4334 profile_count orig_new_node_count
= new_node
->count
;
4336 if (!(orig_node_count
.ipa () > profile_count::zero ()))
4339 init_caller_stats (&stats
);
4340 orig_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
4342 orig_sum
= stats
.count_sum
;
4343 init_caller_stats (&stats
);
4344 new_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
4346 new_sum
= stats
.count_sum
;
4348 if (orig_node_count
< orig_sum
+ new_sum
)
4352 fprintf (dump_file
, " Problem: node %s has too low count ",
4353 orig_node
->dump_name ());
4354 orig_node_count
.dump (dump_file
);
4355 fprintf (dump_file
, "while the sum of incoming count is ");
4356 (orig_sum
+ new_sum
).dump (dump_file
);
4357 fprintf (dump_file
, "\n");
4360 orig_node_count
= (orig_sum
+ new_sum
).apply_scale (12, 10);
4363 fprintf (dump_file
, " proceeding by pretending it was ");
4364 orig_node_count
.dump (dump_file
);
4365 fprintf (dump_file
, "\n");
4369 remainder
= orig_node_count
.combine_with_ipa_count (orig_node_count
.ipa ()
4372 /* With partial train run we do not want to assume that original's
4373 count is zero whenever we redurect all executed edges to clone.
4374 Simply drop profile to local one in this case. */
4375 if (remainder
.ipa_p () && !remainder
.ipa ().nonzero_p ()
4376 && orig_node
->count
.ipa_p () && orig_node
->count
.ipa ().nonzero_p ()
4377 && flag_profile_partial_training
)
4378 remainder
= remainder
.guessed_local ();
4380 new_sum
= orig_node_count
.combine_with_ipa_count (new_sum
);
4381 new_node
->count
= new_sum
;
4382 orig_node
->count
= remainder
;
4384 profile_count::adjust_for_ipa_scaling (&new_sum
, &orig_new_node_count
);
4385 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
4386 cs
->count
= cs
->count
.apply_scale (new_sum
, orig_new_node_count
);
4387 for (cs
= new_node
->indirect_calls
; cs
; cs
= cs
->next_callee
)
4388 cs
->count
= cs
->count
.apply_scale (new_sum
, orig_new_node_count
);
4390 profile_count::adjust_for_ipa_scaling (&remainder
, &orig_node_count
);
4391 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
4392 cs
->count
= cs
->count
.apply_scale (remainder
, orig_node_count
);
4393 for (cs
= orig_node
->indirect_calls
; cs
; cs
= cs
->next_callee
)
4394 cs
->count
= cs
->count
.apply_scale (remainder
, orig_node_count
);
4397 dump_profile_updates (orig_node
, new_node
);
4400 /* Update the respective profile of specialized NEW_NODE and the original
4401 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
4402 have been redirected to the specialized version. */
4405 update_specialized_profile (struct cgraph_node
*new_node
,
4406 struct cgraph_node
*orig_node
,
4407 profile_count redirected_sum
)
4409 struct cgraph_edge
*cs
;
4410 profile_count new_node_count
, orig_node_count
= orig_node
->count
;
4414 fprintf (dump_file
, " the sum of counts of redirected edges is ");
4415 redirected_sum
.dump (dump_file
);
4416 fprintf (dump_file
, "\n");
4418 if (!(orig_node_count
> profile_count::zero ()))
4421 gcc_assert (orig_node_count
>= redirected_sum
);
4423 new_node_count
= new_node
->count
;
4424 new_node
->count
+= redirected_sum
;
4425 orig_node
->count
-= redirected_sum
;
4427 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
4428 cs
->count
+= cs
->count
.apply_scale (redirected_sum
, new_node_count
);
4430 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
4432 profile_count dec
= cs
->count
.apply_scale (redirected_sum
,
4438 dump_profile_updates (orig_node
, new_node
);
4441 /* Return true if we would like to remove a parameter from NODE when cloning it
4442 with KNOWN_CSTS scalar constants. */
4445 want_remove_some_param_p (cgraph_node
*node
, vec
<tree
> known_csts
)
4447 auto_vec
<bool, 16> surviving
;
4448 bool filled_vec
= false;
4449 ipa_node_params
*info
= IPA_NODE_REF (node
);
4450 int i
, count
= ipa_get_param_count (info
);
4452 for (i
= 0; i
< count
; i
++)
4454 if (!known_csts
[i
] && ipa_is_param_used (info
, i
))
4459 if (!node
->clone
.param_adjustments
)
4461 node
->clone
.param_adjustments
->get_surviving_params (&surviving
);
4464 if (surviving
.length() < (unsigned) i
&& surviving
[i
])
4470 /* Create a specialized version of NODE with known constants in KNOWN_CSTS,
4471 known contexts in KNOWN_CONTEXTS and known aggregate values in AGGVALS and
4472 redirect all edges in CALLERS to it. */
4474 static struct cgraph_node
*
4475 create_specialized_node (struct cgraph_node
*node
,
4476 vec
<tree
> known_csts
,
4477 vec
<ipa_polymorphic_call_context
> known_contexts
,
4478 struct ipa_agg_replacement_value
*aggvals
,
4479 vec
<cgraph_edge
*> callers
)
4481 class ipa_node_params
*new_info
, *info
= IPA_NODE_REF (node
);
4482 vec
<ipa_replace_map
*, va_gc
> *replace_trees
= NULL
;
4483 vec
<ipa_adjusted_param
, va_gc
> *new_params
= NULL
;
4484 struct ipa_agg_replacement_value
*av
;
4485 struct cgraph_node
*new_node
;
4486 int i
, count
= ipa_get_param_count (info
);
4487 ipa_param_adjustments
*old_adjustments
= node
->clone
.param_adjustments
;
4488 ipa_param_adjustments
*new_adjustments
;
4489 gcc_assert (!info
->ipcp_orig_node
);
4490 gcc_assert (node
->can_change_signature
4491 || !old_adjustments
);
4493 if (old_adjustments
)
4495 /* At the moment all IPA optimizations should use the number of
4496 parameters of the prevailing decl as the m_always_copy_start.
4497 Handling any other value would complicate the code below, so for the
4498 time bing let's only assert it is so. */
4499 gcc_assert (old_adjustments
->m_always_copy_start
== count
4500 || old_adjustments
->m_always_copy_start
< 0);
4501 int old_adj_count
= vec_safe_length (old_adjustments
->m_adj_params
);
4502 for (i
= 0; i
< old_adj_count
; i
++)
4504 ipa_adjusted_param
*old_adj
= &(*old_adjustments
->m_adj_params
)[i
];
4505 if (!node
->can_change_signature
4506 || old_adj
->op
!= IPA_PARAM_OP_COPY
4507 || (!known_csts
[old_adj
->base_index
]
4508 && ipa_is_param_used (info
, old_adj
->base_index
)))
4510 ipa_adjusted_param new_adj
= *old_adj
;
4512 new_adj
.prev_clone_adjustment
= true;
4513 new_adj
.prev_clone_index
= i
;
4514 vec_safe_push (new_params
, new_adj
);
4517 bool skip_return
= old_adjustments
->m_skip_return
;
4518 new_adjustments
= (new (ggc_alloc
<ipa_param_adjustments
> ())
4519 ipa_param_adjustments (new_params
, count
,
4522 else if (node
->can_change_signature
4523 && want_remove_some_param_p (node
, known_csts
))
4525 ipa_adjusted_param adj
;
4526 memset (&adj
, 0, sizeof (adj
));
4527 adj
.op
= IPA_PARAM_OP_COPY
;
4528 for (i
= 0; i
< count
; i
++)
4529 if (!known_csts
[i
] && ipa_is_param_used (info
, i
))
4532 adj
.prev_clone_index
= i
;
4533 vec_safe_push (new_params
, adj
);
4535 new_adjustments
= (new (ggc_alloc
<ipa_param_adjustments
> ())
4536 ipa_param_adjustments (new_params
, count
, false));
4539 new_adjustments
= NULL
;
4541 replace_trees
= vec_safe_copy (node
->clone
.tree_map
);
4542 for (i
= 0; i
< count
; i
++)
4544 tree t
= known_csts
[i
];
4547 struct ipa_replace_map
*replace_map
;
4549 gcc_checking_assert (TREE_CODE (t
) != TREE_BINFO
);
4550 replace_map
= get_replacement_map (info
, t
, i
);
4552 vec_safe_push (replace_trees
, replace_map
);
4555 auto_vec
<cgraph_edge
*, 2> self_recursive_calls
;
4556 for (i
= callers
.length () - 1; i
>= 0; i
--)
4558 cgraph_edge
*cs
= callers
[i
];
4559 if (cs
->caller
== node
)
4561 self_recursive_calls
.safe_push (cs
);
4562 callers
.unordered_remove (i
);
4566 unsigned &suffix_counter
= clone_num_suffixes
->get_or_insert (
4567 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (
4569 new_node
= node
->create_virtual_clone (callers
, replace_trees
,
4570 new_adjustments
, "constprop",
4574 bool have_self_recursive_calls
= !self_recursive_calls
.is_empty ();
4575 for (unsigned j
= 0; j
< self_recursive_calls
.length (); j
++)
4577 cgraph_edge
*cs
= get_next_cgraph_edge_clone (self_recursive_calls
[j
]);
4578 /* Cloned edges can disappear during cloning as speculation can be
4579 resolved, check that we have one and that it comes from the last
4581 if (cs
&& cs
->caller
== new_node
)
4582 cs
->redirect_callee_duplicating_thunks (new_node
);
4583 /* Any future code that would make more than one clone of an outgoing
4584 edge would confuse this mechanism, so let's check that does not
4586 gcc_checking_assert (!cs
4587 || !get_next_cgraph_edge_clone (cs
)
4588 || get_next_cgraph_edge_clone (cs
)->caller
!= new_node
);
4590 if (have_self_recursive_calls
)
4591 new_node
->expand_all_artificial_thunks ();
4593 ipa_set_node_agg_value_chain (new_node
, aggvals
);
4594 for (av
= aggvals
; av
; av
= av
->next
)
4595 new_node
->maybe_create_reference (av
->value
, NULL
);
4597 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4599 fprintf (dump_file
, " the new node is %s.\n", new_node
->dump_name ());
4600 if (known_contexts
.exists ())
4602 for (i
= 0; i
< count
; i
++)
4603 if (!known_contexts
[i
].useless_p ())
4605 fprintf (dump_file
, " known ctx %i is ", i
);
4606 known_contexts
[i
].dump (dump_file
);
4610 ipa_dump_agg_replacement_values (dump_file
, aggvals
);
4612 ipa_check_create_node_params ();
4613 update_profiling_info (node
, new_node
);
4614 new_info
= IPA_NODE_REF (new_node
);
4615 new_info
->ipcp_orig_node
= node
;
4616 new_node
->ipcp_clone
= true;
4617 new_info
->known_csts
= known_csts
;
4618 new_info
->known_contexts
= known_contexts
;
4620 ipcp_discover_new_direct_edges (new_node
, known_csts
, known_contexts
, aggvals
);
4626 /* Return true if JFUNC, which describes a i-th parameter of call CS, is a
4627 pass-through function to itself when the cgraph_node involved is not an
4628 IPA-CP clone. When SIMPLE is true, further check if JFUNC is a simple
4629 no-operation pass-through. */
4632 self_recursive_pass_through_p (cgraph_edge
*cs
, ipa_jump_func
*jfunc
, int i
,
4635 enum availability availability
;
4636 if (cs
->caller
== cs
->callee
->function_symbol (&availability
)
4637 && availability
> AVAIL_INTERPOSABLE
4638 && jfunc
->type
== IPA_JF_PASS_THROUGH
4639 && (!simple
|| ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
4640 && ipa_get_jf_pass_through_formal_id (jfunc
) == i
4641 && IPA_NODE_REF (cs
->caller
)
4642 && !IPA_NODE_REF (cs
->caller
)->ipcp_orig_node
)
4647 /* Return true if JFUNC, which describes a part of an aggregate represented or
4648 pointed to by the i-th parameter of call CS, is a pass-through function to
4649 itself when the cgraph_node involved is not an IPA-CP clone.. When
4650 SIMPLE is true, further check if JFUNC is a simple no-operation
4654 self_recursive_agg_pass_through_p (cgraph_edge
*cs
, ipa_agg_jf_item
*jfunc
,
4655 int i
, bool simple
= true)
4657 enum availability availability
;
4658 if (cs
->caller
== cs
->callee
->function_symbol (&availability
)
4659 && availability
> AVAIL_INTERPOSABLE
4660 && jfunc
->jftype
== IPA_JF_LOAD_AGG
4661 && jfunc
->offset
== jfunc
->value
.load_agg
.offset
4662 && (!simple
|| jfunc
->value
.pass_through
.operation
== NOP_EXPR
)
4663 && jfunc
->value
.pass_through
.formal_id
== i
4664 && useless_type_conversion_p (jfunc
->value
.load_agg
.type
, jfunc
->type
)
4665 && IPA_NODE_REF (cs
->caller
)
4666 && !IPA_NODE_REF (cs
->caller
)->ipcp_orig_node
)
4671 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
4672 KNOWN_CSTS with constants that are also known for all of the CALLERS. */
4675 find_more_scalar_values_for_callers_subset (struct cgraph_node
*node
,
4676 vec
<tree
> known_csts
,
4677 vec
<cgraph_edge
*> callers
)
4679 class ipa_node_params
*info
= IPA_NODE_REF (node
);
4680 int i
, count
= ipa_get_param_count (info
);
4682 for (i
= 0; i
< count
; i
++)
4684 struct cgraph_edge
*cs
;
4685 tree newval
= NULL_TREE
;
4688 tree type
= ipa_get_type (info
, i
);
4690 if (ipa_get_scalar_lat (info
, i
)->bottom
|| known_csts
[i
])
4693 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4695 struct ipa_jump_func
*jump_func
;
4698 if (!IPA_EDGE_REF (cs
)
4699 || i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
))
4701 && call_passes_through_thunk_p (cs
)))
4706 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
4708 /* Besides simple pass-through jump function, arithmetic jump
4709 function could also introduce argument-direct-pass-through for
4710 self-feeding recursive call. For example,
4717 Given that i is 0, recursive propagation via (i & 1) also gets
4719 if (self_recursive_pass_through_p (cs
, jump_func
, i
, false))
4721 gcc_assert (newval
);
4722 t
= ipa_get_jf_arith_result (
4723 ipa_get_jf_pass_through_operation (jump_func
),
4725 ipa_get_jf_pass_through_operand (jump_func
),
4729 t
= ipa_value_from_jfunc (IPA_NODE_REF (cs
->caller
), jump_func
,
4733 && !values_equal_for_ipcp_p (t
, newval
))
4734 || (!first
&& !newval
))
4746 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4748 fprintf (dump_file
, " adding an extra known scalar value ");
4749 print_ipcp_constant_value (dump_file
, newval
);
4750 fprintf (dump_file
, " for ");
4751 ipa_dump_param (dump_file
, info
, i
);
4752 fprintf (dump_file
, "\n");
4755 known_csts
[i
] = newval
;
4760 /* Given a NODE and a subset of its CALLERS, try to populate plank slots in
4761 KNOWN_CONTEXTS with polymorphic contexts that are also known for all of the
4765 find_more_contexts_for_caller_subset (cgraph_node
*node
,
4766 vec
<ipa_polymorphic_call_context
>
4768 vec
<cgraph_edge
*> callers
)
4770 ipa_node_params
*info
= IPA_NODE_REF (node
);
4771 int i
, count
= ipa_get_param_count (info
);
4773 for (i
= 0; i
< count
; i
++)
4777 if (ipa_get_poly_ctx_lat (info
, i
)->bottom
4778 || (known_contexts
->exists ()
4779 && !(*known_contexts
)[i
].useless_p ()))
4782 ipa_polymorphic_call_context newval
;
4786 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4788 if (!IPA_EDGE_REF (cs
)
4789 || i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
)))
4791 ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
),
4793 ipa_polymorphic_call_context ctx
;
4794 ctx
= ipa_context_from_jfunc (IPA_NODE_REF (cs
->caller
), cs
, i
,
4802 newval
.meet_with (ctx
);
4803 if (newval
.useless_p ())
4807 if (!newval
.useless_p ())
4809 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4811 fprintf (dump_file
, " adding an extra known polymorphic "
4813 print_ipcp_constant_value (dump_file
, newval
);
4814 fprintf (dump_file
, " for ");
4815 ipa_dump_param (dump_file
, info
, i
);
4816 fprintf (dump_file
, "\n");
4819 if (!known_contexts
->exists ())
4820 known_contexts
->safe_grow_cleared (ipa_get_param_count (info
));
4821 (*known_contexts
)[i
] = newval
;
4827 /* Go through PLATS and create a vector of values consisting of values and
4828 offsets (minus OFFSET) of lattices that contain only a single value. */
4830 static vec
<ipa_agg_value
>
4831 copy_plats_to_inter (class ipcp_param_lattices
*plats
, HOST_WIDE_INT offset
)
4833 vec
<ipa_agg_value
> res
= vNULL
;
4835 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
4838 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
4839 if (aglat
->is_single_const ())
4841 struct ipa_agg_value ti
;
4842 ti
.offset
= aglat
->offset
- offset
;
4843 ti
.value
= aglat
->values
->value
;
4849 /* Intersect all values in INTER with single value lattices in PLATS (while
4850 subtracting OFFSET). */
4853 intersect_with_plats (class ipcp_param_lattices
*plats
,
4854 vec
<ipa_agg_value
> *inter
,
4855 HOST_WIDE_INT offset
)
4857 struct ipcp_agg_lattice
*aglat
;
4858 struct ipa_agg_value
*item
;
4861 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
4867 aglat
= plats
->aggs
;
4868 FOR_EACH_VEC_ELT (*inter
, k
, item
)
4875 if (aglat
->offset
- offset
> item
->offset
)
4877 if (aglat
->offset
- offset
== item
->offset
)
4879 if (aglat
->is_single_const ())
4881 tree value
= aglat
->values
->value
;
4883 if (values_equal_for_ipcp_p (item
->value
, value
))
4888 aglat
= aglat
->next
;
4891 item
->value
= NULL_TREE
;
4895 /* Copy aggregate replacement values of NODE (which is an IPA-CP clone) to the
4896 vector result while subtracting OFFSET from the individual value offsets. */
4898 static vec
<ipa_agg_value
>
4899 agg_replacements_to_vector (struct cgraph_node
*node
, int index
,
4900 HOST_WIDE_INT offset
)
4902 struct ipa_agg_replacement_value
*av
;
4903 vec
<ipa_agg_value
> res
= vNULL
;
4905 for (av
= ipa_get_agg_replacements_for_node (node
); av
; av
= av
->next
)
4906 if (av
->index
== index
4907 && (av
->offset
- offset
) >= 0)
4909 struct ipa_agg_value item
;
4910 gcc_checking_assert (av
->value
);
4911 item
.offset
= av
->offset
- offset
;
4912 item
.value
= av
->value
;
4913 res
.safe_push (item
);
4919 /* Intersect all values in INTER with those that we have already scheduled to
4920 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
4921 (while subtracting OFFSET). */
4924 intersect_with_agg_replacements (struct cgraph_node
*node
, int index
,
4925 vec
<ipa_agg_value
> *inter
,
4926 HOST_WIDE_INT offset
)
4928 struct ipa_agg_replacement_value
*srcvals
;
4929 struct ipa_agg_value
*item
;
4932 srcvals
= ipa_get_agg_replacements_for_node (node
);
4939 FOR_EACH_VEC_ELT (*inter
, i
, item
)
4941 struct ipa_agg_replacement_value
*av
;
4945 for (av
= srcvals
; av
; av
= av
->next
)
4947 gcc_checking_assert (av
->value
);
4948 if (av
->index
== index
4949 && av
->offset
- offset
== item
->offset
)
4951 if (values_equal_for_ipcp_p (item
->value
, av
->value
))
4957 item
->value
= NULL_TREE
;
4961 /* Intersect values in INTER with aggregate values that come along edge CS to
4962 parameter number INDEX and return it. If INTER does not actually exist yet,
4963 copy all incoming values to it. If we determine we ended up with no values
4964 whatsoever, return a released vector. */
4966 static vec
<ipa_agg_value
>
4967 intersect_aggregates_with_edge (struct cgraph_edge
*cs
, int index
,
4968 vec
<ipa_agg_value
> inter
)
4970 struct ipa_jump_func
*jfunc
;
4971 jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), index
);
4972 if (jfunc
->type
== IPA_JF_PASS_THROUGH
4973 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
4975 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4976 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
4978 if (caller_info
->ipcp_orig_node
)
4980 struct cgraph_node
*orig_node
= caller_info
->ipcp_orig_node
;
4981 class ipcp_param_lattices
*orig_plats
;
4982 orig_plats
= ipa_get_parm_lattices (IPA_NODE_REF (orig_node
),
4984 if (agg_pass_through_permissible_p (orig_plats
, jfunc
))
4986 if (!inter
.exists ())
4987 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, 0);
4989 intersect_with_agg_replacements (cs
->caller
, src_idx
,
5000 class ipcp_param_lattices
*src_plats
;
5001 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
5002 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
5004 /* Currently we do not produce clobber aggregate jump
5005 functions, adjust when we do. */
5006 gcc_checking_assert (!jfunc
->agg
.items
);
5007 if (!inter
.exists ())
5008 inter
= copy_plats_to_inter (src_plats
, 0);
5010 intersect_with_plats (src_plats
, &inter
, 0);
5019 else if (jfunc
->type
== IPA_JF_ANCESTOR
5020 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
5022 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
5023 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
5024 class ipcp_param_lattices
*src_plats
;
5025 HOST_WIDE_INT delta
= ipa_get_jf_ancestor_offset (jfunc
);
5027 if (caller_info
->ipcp_orig_node
)
5029 if (!inter
.exists ())
5030 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, delta
);
5032 intersect_with_agg_replacements (cs
->caller
, src_idx
, &inter
,
5037 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
5038 /* Currently we do not produce clobber aggregate jump
5039 functions, adjust when we do. */
5040 gcc_checking_assert (!src_plats
->aggs
|| !jfunc
->agg
.items
);
5041 if (!inter
.exists ())
5042 inter
= copy_plats_to_inter (src_plats
, delta
);
5044 intersect_with_plats (src_plats
, &inter
, delta
);
5047 else if (jfunc
->agg
.items
)
5049 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
5050 struct ipa_agg_value
*item
;
5053 if (!inter
.exists ())
5054 for (unsigned i
= 0; i
< jfunc
->agg
.items
->length (); i
++)
5056 struct ipa_agg_jf_item
*agg_item
= &(*jfunc
->agg
.items
)[i
];
5057 tree value
= ipa_agg_value_from_node (caller_info
, cs
->caller
,
5061 struct ipa_agg_value agg_value
;
5063 agg_value
.value
= value
;
5064 agg_value
.offset
= agg_item
->offset
;
5065 inter
.safe_push (agg_value
);
5069 FOR_EACH_VEC_ELT (inter
, k
, item
)
5077 while ((unsigned) l
< jfunc
->agg
.items
->length ())
5079 struct ipa_agg_jf_item
*ti
;
5080 ti
= &(*jfunc
->agg
.items
)[l
];
5081 if (ti
->offset
> item
->offset
)
5083 if (ti
->offset
== item
->offset
)
5087 /* Besides simple pass-through aggregate jump function,
5088 arithmetic aggregate jump function could also bring
5089 same aggregate value as parameter passed-in for
5090 self-feeding recursive call. For example,
5098 Given that *i is 0, recursive propagation via (*i & 1)
5100 if (self_recursive_agg_pass_through_p (cs
, ti
, index
,
5102 value
= ipa_get_jf_arith_result (
5103 ti
->value
.pass_through
.operation
,
5105 ti
->value
.pass_through
.operand
,
5108 value
= ipa_agg_value_from_node (caller_info
,
5111 if (value
&& values_equal_for_ipcp_p (item
->value
, value
))
5129 /* Look at edges in CALLERS and collect all known aggregate values that arrive
5130 from all of them. */
5132 static struct ipa_agg_replacement_value
*
5133 find_aggregate_values_for_callers_subset (struct cgraph_node
*node
,
5134 vec
<cgraph_edge
*> callers
)
5136 class ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
5137 struct ipa_agg_replacement_value
*res
;
5138 struct ipa_agg_replacement_value
**tail
= &res
;
5139 struct cgraph_edge
*cs
;
5140 int i
, j
, count
= ipa_get_param_count (dest_info
);
5142 FOR_EACH_VEC_ELT (callers
, j
, cs
)
5144 if (!IPA_EDGE_REF (cs
))
5149 int c
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
5154 for (i
= 0; i
< count
; i
++)
5156 struct cgraph_edge
*cs
;
5157 vec
<ipa_agg_value
> inter
= vNULL
;
5158 struct ipa_agg_value
*item
;
5159 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (dest_info
, i
);
5162 /* Among other things, the following check should deal with all by_ref
5164 if (plats
->aggs_bottom
)
5167 FOR_EACH_VEC_ELT (callers
, j
, cs
)
5169 struct ipa_jump_func
*jfunc
5170 = ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
5171 if (self_recursive_pass_through_p (cs
, jfunc
, i
)
5172 && (!plats
->aggs_by_ref
5173 || ipa_get_jf_pass_through_agg_preserved (jfunc
)))
5175 inter
= intersect_aggregates_with_edge (cs
, i
, inter
);
5177 if (!inter
.exists ())
5181 FOR_EACH_VEC_ELT (inter
, j
, item
)
5183 struct ipa_agg_replacement_value
*v
;
5188 v
= ggc_alloc
<ipa_agg_replacement_value
> ();
5190 v
->offset
= item
->offset
;
5191 v
->value
= item
->value
;
5192 v
->by_ref
= plats
->aggs_by_ref
;
5198 if (inter
.exists ())
5205 /* Determine whether CS also brings all scalar values that the NODE is
5209 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge
*cs
,
5210 struct cgraph_node
*node
)
5212 class ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
5213 int count
= ipa_get_param_count (dest_info
);
5214 class ipa_node_params
*caller_info
;
5215 class ipa_edge_args
*args
;
5218 caller_info
= IPA_NODE_REF (cs
->caller
);
5219 args
= IPA_EDGE_REF (cs
);
5220 for (i
= 0; i
< count
; i
++)
5222 struct ipa_jump_func
*jump_func
;
5225 val
= dest_info
->known_csts
[i
];
5229 if (i
>= ipa_get_cs_argument_count (args
))
5231 jump_func
= ipa_get_ith_jump_func (args
, i
);
5232 t
= ipa_value_from_jfunc (caller_info
, jump_func
,
5233 ipa_get_type (dest_info
, i
));
5234 if (!t
|| !values_equal_for_ipcp_p (val
, t
))
5240 /* Determine whether CS also brings all aggregate values that NODE is
5243 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge
*cs
,
5244 struct cgraph_node
*node
)
5246 class ipa_node_params
*orig_node_info
;
5247 struct ipa_agg_replacement_value
*aggval
;
5250 aggval
= ipa_get_agg_replacements_for_node (node
);
5254 count
= ipa_get_param_count (IPA_NODE_REF (node
));
5255 ec
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
5257 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
5258 if (aggval
->index
>= ec
)
5261 orig_node_info
= IPA_NODE_REF (IPA_NODE_REF (node
)->ipcp_orig_node
);
5263 for (i
= 0; i
< count
; i
++)
5265 class ipcp_param_lattices
*plats
;
5266 bool interesting
= false;
5267 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
5268 if (aggval
->index
== i
)
5276 plats
= ipa_get_parm_lattices (orig_node_info
, aggval
->index
);
5277 if (plats
->aggs_bottom
)
5280 vec
<ipa_agg_value
> values
= intersect_aggregates_with_edge (cs
, i
, vNULL
);
5281 if (!values
.exists ())
5284 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
5285 if (aggval
->index
== i
)
5287 struct ipa_agg_value
*item
;
5290 FOR_EACH_VEC_ELT (values
, j
, item
)
5292 && item
->offset
== av
->offset
5293 && values_equal_for_ipcp_p (item
->value
, av
->value
))
5309 /* Given an original NODE and a VAL for which we have already created a
5310 specialized clone, look whether there are incoming edges that still lead
5311 into the old node but now also bring the requested value and also conform to
5312 all other criteria such that they can be redirected the special node.
5313 This function can therefore redirect the final edge in a SCC. */
5315 template <typename valtype
>
5317 perhaps_add_new_callers (cgraph_node
*node
, ipcp_value
<valtype
> *val
)
5319 ipcp_value_source
<valtype
> *src
;
5320 profile_count redirected_sum
= profile_count::zero ();
5322 for (src
= val
->sources
; src
; src
= src
->next
)
5324 struct cgraph_edge
*cs
= src
->cs
;
5327 if (cgraph_edge_brings_value_p (cs
, src
, node
, val
)
5328 && cgraph_edge_brings_all_scalars_for_node (cs
, val
->spec_node
)
5329 && cgraph_edge_brings_all_agg_vals_for_node (cs
, val
->spec_node
))
5332 fprintf (dump_file
, " - adding an extra caller %s of %s\n",
5333 cs
->caller
->dump_name (),
5334 val
->spec_node
->dump_name ());
5336 cs
->redirect_callee_duplicating_thunks (val
->spec_node
);
5337 val
->spec_node
->expand_all_artificial_thunks ();
5338 if (cs
->count
.ipa ().initialized_p ())
5339 redirected_sum
= redirected_sum
+ cs
->count
.ipa ();
5341 cs
= get_next_cgraph_edge_clone (cs
);
5345 if (redirected_sum
.nonzero_p ())
5346 update_specialized_profile (val
->spec_node
, node
, redirected_sum
);
5349 /* Return true if KNOWN_CONTEXTS contain at least one useful context. */
5352 known_contexts_useful_p (vec
<ipa_polymorphic_call_context
> known_contexts
)
5354 ipa_polymorphic_call_context
*ctx
;
5357 FOR_EACH_VEC_ELT (known_contexts
, i
, ctx
)
5358 if (!ctx
->useless_p ())
5363 /* Return a copy of KNOWN_CSTS if it is not empty, otherwise return vNULL. */
5365 static vec
<ipa_polymorphic_call_context
>
5366 copy_useful_known_contexts (vec
<ipa_polymorphic_call_context
> known_contexts
)
5368 if (known_contexts_useful_p (known_contexts
))
5369 return known_contexts
.copy ();
5374 /* Copy KNOWN_CSTS and modify the copy according to VAL and INDEX. If
5375 non-empty, replace KNOWN_CONTEXTS with its copy too. */
5378 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
5379 vec
<ipa_polymorphic_call_context
> *known_contexts
,
5380 ipcp_value
<tree
> *val
,
5383 *known_csts
= known_csts
->copy ();
5384 *known_contexts
= copy_useful_known_contexts (*known_contexts
);
5385 (*known_csts
)[index
] = val
->value
;
5388 /* Replace KNOWN_CSTS with its copy. Also copy KNOWN_CONTEXTS and modify the
5389 copy according to VAL and INDEX. */
5392 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
5393 vec
<ipa_polymorphic_call_context
> *known_contexts
,
5394 ipcp_value
<ipa_polymorphic_call_context
> *val
,
5397 *known_csts
= known_csts
->copy ();
5398 *known_contexts
= known_contexts
->copy ();
5399 (*known_contexts
)[index
] = val
->value
;
5402 /* Return true if OFFSET indicates this was not an aggregate value or there is
5403 a replacement equivalent to VALUE, INDEX and OFFSET among those in the
5407 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*aggvals
,
5408 int index
, HOST_WIDE_INT offset
, tree value
)
5415 if (aggvals
->index
== index
5416 && aggvals
->offset
== offset
5417 && values_equal_for_ipcp_p (aggvals
->value
, value
))
5419 aggvals
= aggvals
->next
;
5424 /* Return true if offset is minus one because source of a polymorphic context
5425 cannot be an aggregate value. */
5428 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*,
5429 int , HOST_WIDE_INT offset
,
5430 ipa_polymorphic_call_context
)
5432 return offset
== -1;
5435 /* Decide whether to create a special version of NODE for value VAL of parameter
5436 at the given INDEX. If OFFSET is -1, the value is for the parameter itself,
5437 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS,
5438 KNOWN_CONTEXTS and KNOWN_AGGS describe the other already known values. */
5440 template <typename valtype
>
5442 decide_about_value (struct cgraph_node
*node
, int index
, HOST_WIDE_INT offset
,
5443 ipcp_value
<valtype
> *val
, vec
<tree
> known_csts
,
5444 vec
<ipa_polymorphic_call_context
> known_contexts
)
5446 struct ipa_agg_replacement_value
*aggvals
;
5447 int freq_sum
, caller_count
;
5448 profile_count count_sum
;
5449 vec
<cgraph_edge
*> callers
;
5453 perhaps_add_new_callers (node
, val
);
5456 else if (val
->local_size_cost
+ overall_size
> get_max_overall_size (node
))
5458 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5459 fprintf (dump_file
, " Ignoring candidate value because "
5460 "maximum unit size would be reached with %li.\n",
5461 val
->local_size_cost
+ overall_size
);
5464 else if (!get_info_about_necessary_edges (val
, node
, &freq_sum
, &count_sum
,
5468 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5470 fprintf (dump_file
, " - considering value ");
5471 print_ipcp_constant_value (dump_file
, val
->value
);
5472 fprintf (dump_file
, " for ");
5473 ipa_dump_param (dump_file
, IPA_NODE_REF (node
), index
);
5475 fprintf (dump_file
, ", offset: " HOST_WIDE_INT_PRINT_DEC
, offset
);
5476 fprintf (dump_file
, " (caller_count: %i)\n", caller_count
);
5479 if (!good_cloning_opportunity_p (node
, val
->local_time_benefit
,
5480 freq_sum
, count_sum
,
5481 val
->local_size_cost
)
5482 && !good_cloning_opportunity_p (node
,
5483 val
->local_time_benefit
5484 + val
->prop_time_benefit
,
5485 freq_sum
, count_sum
,
5486 val
->local_size_cost
5487 + val
->prop_size_cost
))
5491 fprintf (dump_file
, " Creating a specialized node of %s.\n",
5492 node
->dump_name ());
5494 callers
= gather_edges_for_value (val
, node
, caller_count
);
5496 modify_known_vectors_with_val (&known_csts
, &known_contexts
, val
, index
);
5499 known_csts
= known_csts
.copy ();
5500 known_contexts
= copy_useful_known_contexts (known_contexts
);
5502 find_more_scalar_values_for_callers_subset (node
, known_csts
, callers
);
5503 find_more_contexts_for_caller_subset (node
, &known_contexts
, callers
);
5504 aggvals
= find_aggregate_values_for_callers_subset (node
, callers
);
5505 gcc_checking_assert (ipcp_val_agg_replacement_ok_p (aggvals
, index
,
5506 offset
, val
->value
));
5507 val
->spec_node
= create_specialized_node (node
, known_csts
, known_contexts
,
5509 overall_size
+= val
->local_size_cost
;
5511 /* TODO: If for some lattice there is only one other known value
5512 left, make a special node for it too. */
5517 /* Decide whether and what specialized clones of NODE should be created. */
5520 decide_whether_version_node (struct cgraph_node
*node
)
5522 class ipa_node_params
*info
= IPA_NODE_REF (node
);
5523 int i
, count
= ipa_get_param_count (info
);
5524 vec
<tree
> known_csts
;
5525 vec
<ipa_polymorphic_call_context
> known_contexts
;
5531 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5532 fprintf (dump_file
, "\nEvaluating opportunities for %s.\n",
5533 node
->dump_name ());
5535 gather_context_independent_values (info
, &known_csts
, &known_contexts
,
5538 for (i
= 0; i
< count
;i
++)
5540 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5541 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
5542 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
5547 ipcp_value
<tree
> *val
;
5548 for (val
= lat
->values
; val
; val
= val
->next
)
5549 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
5553 if (!plats
->aggs_bottom
)
5555 struct ipcp_agg_lattice
*aglat
;
5556 ipcp_value
<tree
> *val
;
5557 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
5558 if (!aglat
->bottom
&& aglat
->values
5559 /* If the following is false, the one value is in
5561 && (plats
->aggs_contain_variable
5562 || !aglat
->is_single_const ()))
5563 for (val
= aglat
->values
; val
; val
= val
->next
)
5564 ret
|= decide_about_value (node
, i
, aglat
->offset
, val
,
5565 known_csts
, known_contexts
);
5569 && known_contexts
[i
].useless_p ())
5571 ipcp_value
<ipa_polymorphic_call_context
> *val
;
5572 for (val
= ctxlat
->values
; val
; val
= val
->next
)
5573 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
5577 info
= IPA_NODE_REF (node
);
5580 if (info
->do_clone_for_all_contexts
)
5582 struct cgraph_node
*clone
;
5583 vec
<cgraph_edge
*> callers
= node
->collect_callers ();
5585 for (int i
= callers
.length () - 1; i
>= 0; i
--)
5587 cgraph_edge
*cs
= callers
[i
];
5588 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
5590 if (caller_info
&& caller_info
->node_dead
)
5591 callers
.unordered_remove (i
);
5594 if (!adjust_callers_for_value_intersection (callers
, node
))
5596 /* If node is not called by anyone, or all its caller edges are
5597 self-recursive, the node is not really be in use, no need to
5600 known_csts
.release ();
5601 known_contexts
.release ();
5602 info
->do_clone_for_all_contexts
= false;
5607 fprintf (dump_file
, " - Creating a specialized node of %s "
5608 "for all known contexts.\n", node
->dump_name ());
5610 find_more_scalar_values_for_callers_subset (node
, known_csts
, callers
);
5611 find_more_contexts_for_caller_subset (node
, &known_contexts
, callers
);
5612 ipa_agg_replacement_value
*aggvals
5613 = find_aggregate_values_for_callers_subset (node
, callers
);
5615 if (!known_contexts_useful_p (known_contexts
))
5617 known_contexts
.release ();
5618 known_contexts
= vNULL
;
5620 clone
= create_specialized_node (node
, known_csts
, known_contexts
,
5622 info
= IPA_NODE_REF (node
);
5623 info
->do_clone_for_all_contexts
= false;
5624 IPA_NODE_REF (clone
)->is_all_contexts_clone
= true;
5629 known_csts
.release ();
5630 known_contexts
.release ();
5636 /* Transitively mark all callees of NODE within the same SCC as not dead. */
5639 spread_undeadness (struct cgraph_node
*node
)
5641 struct cgraph_edge
*cs
;
5643 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
5644 if (ipa_edge_within_scc (cs
))
5646 struct cgraph_node
*callee
;
5647 class ipa_node_params
*info
;
5649 callee
= cs
->callee
->function_symbol (NULL
);
5650 info
= IPA_NODE_REF (callee
);
5652 if (info
&& info
->node_dead
)
5654 info
->node_dead
= 0;
5655 spread_undeadness (callee
);
5660 /* Return true if NODE has a caller from outside of its SCC that is not
5661 dead. Worker callback for cgraph_for_node_and_aliases. */
5664 has_undead_caller_from_outside_scc_p (struct cgraph_node
*node
,
5665 void *data ATTRIBUTE_UNUSED
)
5667 struct cgraph_edge
*cs
;
5669 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
5670 if (cs
->caller
->thunk
.thunk_p
5671 && cs
->caller
->call_for_symbol_thunks_and_aliases
5672 (has_undead_caller_from_outside_scc_p
, NULL
, true))
5674 else if (!ipa_edge_within_scc (cs
)
5675 && !IPA_NODE_REF (cs
->caller
)->node_dead
)
5681 /* Identify nodes within the same SCC as NODE which are no longer needed
5682 because of new clones and will be removed as unreachable. */
5685 identify_dead_nodes (struct cgraph_node
*node
)
5687 struct cgraph_node
*v
;
5688 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
5691 && !v
->call_for_symbol_thunks_and_aliases
5692 (has_undead_caller_from_outside_scc_p
, NULL
, true))
5693 IPA_NODE_REF (v
)->node_dead
= 1;
5695 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
5696 if (IPA_NODE_REF (v
) && !IPA_NODE_REF (v
)->node_dead
)
5697 spread_undeadness (v
);
5699 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5701 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
5702 if (IPA_NODE_REF (v
) && IPA_NODE_REF (v
)->node_dead
)
5703 fprintf (dump_file
, " Marking node as dead: %s.\n", v
->dump_name ());
5707 /* The decision stage. Iterate over the topological order of call graph nodes
5708 TOPO and make specialized clones if deemed beneficial. */
5711 ipcp_decision_stage (class ipa_topo_info
*topo
)
5716 fprintf (dump_file
, "\nIPA decision stage:\n\n");
5718 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
5720 struct cgraph_node
*node
= topo
->order
[i
];
5721 bool change
= false, iterate
= true;
5725 struct cgraph_node
*v
;
5727 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
5728 if (v
->has_gimple_body_p ()
5729 && ipcp_versionable_function_p (v
))
5730 iterate
|= decide_whether_version_node (v
);
5735 identify_dead_nodes (node
);
5739 /* Look up all the bits information that we have discovered and copy it over
5740 to the transformation summary. */
5743 ipcp_store_bits_results (void)
5747 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5749 ipa_node_params
*info
= IPA_NODE_REF (node
);
5750 bool dumped_sth
= false;
5751 bool found_useful_result
= false;
5753 if (!opt_for_fn (node
->decl
, flag_ipa_bit_cp
) || !info
)
5756 fprintf (dump_file
, "Not considering %s for ipa bitwise propagation "
5757 "; -fipa-bit-cp: disabled.\n",
5758 node
->dump_name ());
5762 if (info
->ipcp_orig_node
)
5763 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
5764 if (!info
->lattices
)
5765 /* Newly expanded artificial thunks do not have lattices. */
5768 unsigned count
= ipa_get_param_count (info
);
5769 for (unsigned i
= 0; i
< count
; i
++)
5771 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5772 if (plats
->bits_lattice
.constant_p ())
5774 found_useful_result
= true;
5779 if (!found_useful_result
)
5782 ipcp_transformation_initialize ();
5783 ipcp_transformation
*ts
= ipcp_transformation_sum
->get_create (node
);
5784 vec_safe_reserve_exact (ts
->bits
, count
);
5786 for (unsigned i
= 0; i
< count
; i
++)
5788 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5791 if (plats
->bits_lattice
.constant_p ())
5793 = ipa_get_ipa_bits_for_value (plats
->bits_lattice
.get_value (),
5794 plats
->bits_lattice
.get_mask ());
5798 ts
->bits
->quick_push (jfbits
);
5799 if (!dump_file
|| !jfbits
)
5803 fprintf (dump_file
, "Propagated bits info for function %s:\n",
5804 node
->dump_name ());
5807 fprintf (dump_file
, " param %i: value = ", i
);
5808 print_hex (jfbits
->value
, dump_file
);
5809 fprintf (dump_file
, ", mask = ");
5810 print_hex (jfbits
->mask
, dump_file
);
5811 fprintf (dump_file
, "\n");
5816 /* Look up all VR information that we have discovered and copy it over
5817 to the transformation summary. */
5820 ipcp_store_vr_results (void)
5824 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5826 ipa_node_params
*info
= IPA_NODE_REF (node
);
5827 bool found_useful_result
= false;
5829 if (!info
|| !opt_for_fn (node
->decl
, flag_ipa_vrp
))
5832 fprintf (dump_file
, "Not considering %s for VR discovery "
5833 "and propagate; -fipa-ipa-vrp: disabled.\n",
5834 node
->dump_name ());
5838 if (info
->ipcp_orig_node
)
5839 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
5840 if (!info
->lattices
)
5841 /* Newly expanded artificial thunks do not have lattices. */
5844 unsigned count
= ipa_get_param_count (info
);
5845 for (unsigned i
= 0; i
< count
; i
++)
5847 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5848 if (!plats
->m_value_range
.bottom_p ()
5849 && !plats
->m_value_range
.top_p ())
5851 found_useful_result
= true;
5855 if (!found_useful_result
)
5858 ipcp_transformation_initialize ();
5859 ipcp_transformation
*ts
= ipcp_transformation_sum
->get_create (node
);
5860 vec_safe_reserve_exact (ts
->m_vr
, count
);
5862 for (unsigned i
= 0; i
< count
; i
++)
5864 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5867 if (!plats
->m_value_range
.bottom_p ()
5868 && !plats
->m_value_range
.top_p ())
5871 vr
.type
= plats
->m_value_range
.m_vr
.kind ();
5872 vr
.min
= wi::to_wide (plats
->m_value_range
.m_vr
.min ());
5873 vr
.max
= wi::to_wide (plats
->m_value_range
.m_vr
.max ());
5878 vr
.type
= VR_VARYING
;
5879 vr
.min
= vr
.max
= wi::zero (INT_TYPE_SIZE
);
5881 ts
->m_vr
->quick_push (vr
);
5886 /* The IPCP driver. */
5891 class ipa_topo_info topo
;
5893 if (edge_clone_summaries
== NULL
)
5894 edge_clone_summaries
= new edge_clone_summary_t (symtab
);
5896 ipa_check_create_node_params ();
5897 ipa_check_create_edge_args ();
5898 clone_num_suffixes
= new hash_map
<const char *, unsigned>;
5902 fprintf (dump_file
, "\nIPA structures before propagation:\n");
5903 if (dump_flags
& TDF_DETAILS
)
5904 ipa_print_all_params (dump_file
);
5905 ipa_print_all_jump_functions (dump_file
);
5908 /* Topological sort. */
5909 build_toporder_info (&topo
);
5910 /* Do the interprocedural propagation. */
5911 ipcp_propagate_stage (&topo
);
5912 /* Decide what constant propagation and cloning should be performed. */
5913 ipcp_decision_stage (&topo
);
5914 /* Store results of bits propagation. */
5915 ipcp_store_bits_results ();
5916 /* Store results of value range propagation. */
5917 ipcp_store_vr_results ();
5919 /* Free all IPCP structures. */
5920 delete clone_num_suffixes
;
5921 free_toporder_info (&topo
);
5922 delete edge_clone_summaries
;
5923 edge_clone_summaries
= NULL
;
5924 ipa_free_all_structures_after_ipa_cp ();
5926 fprintf (dump_file
, "\nIPA constant propagation end\n");
5930 /* Initialization and computation of IPCP data structures. This is the initial
5931 intraprocedural analysis of functions, which gathers information to be
5932 propagated later on. */
5935 ipcp_generate_summary (void)
5937 struct cgraph_node
*node
;
5940 fprintf (dump_file
, "\nIPA constant propagation start:\n");
5941 ipa_register_cgraph_hooks ();
5943 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5944 ipa_analyze_node (node
);
5947 /* Write ipcp summary for nodes in SET. */
5950 ipcp_write_summary (void)
5952 ipa_prop_write_jump_functions ();
5955 /* Read ipcp summary. */
5958 ipcp_read_summary (void)
5960 ipa_prop_read_jump_functions ();
5965 const pass_data pass_data_ipa_cp
=
5967 IPA_PASS
, /* type */
5969 OPTGROUP_NONE
, /* optinfo_flags */
5970 TV_IPA_CONSTANT_PROP
, /* tv_id */
5971 0, /* properties_required */
5972 0, /* properties_provided */
5973 0, /* properties_destroyed */
5974 0, /* todo_flags_start */
5975 ( TODO_dump_symtab
| TODO_remove_functions
), /* todo_flags_finish */
5978 class pass_ipa_cp
: public ipa_opt_pass_d
5981 pass_ipa_cp (gcc::context
*ctxt
)
5982 : ipa_opt_pass_d (pass_data_ipa_cp
, ctxt
,
5983 ipcp_generate_summary
, /* generate_summary */
5984 ipcp_write_summary
, /* write_summary */
5985 ipcp_read_summary
, /* read_summary */
5986 ipcp_write_transformation_summaries
, /*
5987 write_optimization_summary */
5988 ipcp_read_transformation_summaries
, /*
5989 read_optimization_summary */
5990 NULL
, /* stmt_fixup */
5991 0, /* function_transform_todo_flags_start */
5992 ipcp_transform_function
, /* function_transform */
5993 NULL
) /* variable_transform */
5996 /* opt_pass methods: */
5997 virtual bool gate (function
*)
5999 /* FIXME: We should remove the optimize check after we ensure we never run
6000 IPA passes when not optimizing. */
6001 return (flag_ipa_cp
&& optimize
) || in_lto_p
;
6004 virtual unsigned int execute (function
*) { return ipcp_driver (); }
6006 }; // class pass_ipa_cp
6011 make_pass_ipa_cp (gcc::context
*ctxt
)
6013 return new pass_ipa_cp (ctxt
);
6016 /* Reset all state within ipa-cp.c so that we can rerun the compiler
6017 within the same process. For use by toplev::finalize. */
6020 ipa_cp_c_finalize (void)
6022 max_count
= profile_count::uninitialized ();
6024 orig_overall_size
= 0;
6025 ipcp_free_transformation_sum ();