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
, max_new_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 tree t
= TREE_OPERAND (input
, 0);
1356 t
= build_ref_for_offset (EXPR_LOCATION (t
), t
,
1357 ipa_get_jf_ancestor_offset (jfunc
), false,
1358 ptr_type_node
, NULL
, false);
1359 return build_fold_addr_expr (t
);
1365 /* Determine whether JFUNC evaluates to a single known constant value and if
1366 so, return it. Otherwise return NULL. INFO describes the caller node or
1367 the one it is inlined to, so that pass-through jump functions can be
1368 evaluated. PARM_TYPE is the type of the parameter to which the result is
1372 ipa_value_from_jfunc (class ipa_node_params
*info
, struct ipa_jump_func
*jfunc
,
1375 if (jfunc
->type
== IPA_JF_CONST
)
1376 return ipa_get_jf_constant (jfunc
);
1377 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1378 || jfunc
->type
== IPA_JF_ANCESTOR
)
1383 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1384 idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1386 idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1388 if (info
->ipcp_orig_node
)
1389 input
= info
->known_csts
[idx
];
1392 ipcp_lattice
<tree
> *lat
;
1395 || idx
>= ipa_get_param_count (info
))
1397 lat
= ipa_get_scalar_lat (info
, idx
);
1398 if (!lat
->is_single_const ())
1400 input
= lat
->values
->value
;
1406 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1407 return ipa_get_jf_pass_through_result (jfunc
, input
, parm_type
);
1409 return ipa_get_jf_ancestor_result (jfunc
, input
);
1415 /* Determine whether JFUNC evaluates to single known polymorphic context, given
1416 that INFO describes the caller node or the one it is inlined to, CS is the
1417 call graph edge corresponding to JFUNC and CSIDX index of the described
1420 ipa_polymorphic_call_context
1421 ipa_context_from_jfunc (ipa_node_params
*info
, cgraph_edge
*cs
, int csidx
,
1422 ipa_jump_func
*jfunc
)
1424 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
1425 ipa_polymorphic_call_context ctx
;
1426 ipa_polymorphic_call_context
*edge_ctx
1427 = cs
? ipa_get_ith_polymorhic_call_context (args
, csidx
) : NULL
;
1429 if (edge_ctx
&& !edge_ctx
->useless_p ())
1432 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1433 || jfunc
->type
== IPA_JF_ANCESTOR
)
1435 ipa_polymorphic_call_context srcctx
;
1437 bool type_preserved
= true;
1438 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1440 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1442 type_preserved
= ipa_get_jf_pass_through_type_preserved (jfunc
);
1443 srcidx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1447 type_preserved
= ipa_get_jf_ancestor_type_preserved (jfunc
);
1448 srcidx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1450 if (info
->ipcp_orig_node
)
1452 if (info
->known_contexts
.exists ())
1453 srcctx
= info
->known_contexts
[srcidx
];
1458 || srcidx
>= ipa_get_param_count (info
))
1460 ipcp_lattice
<ipa_polymorphic_call_context
> *lat
;
1461 lat
= ipa_get_poly_ctx_lat (info
, srcidx
);
1462 if (!lat
->is_single_const ())
1464 srcctx
= lat
->values
->value
;
1466 if (srcctx
.useless_p ())
1468 if (jfunc
->type
== IPA_JF_ANCESTOR
)
1469 srcctx
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
1470 if (!type_preserved
)
1471 srcctx
.possible_dynamic_type_change (cs
->in_polymorphic_cdtor
);
1472 srcctx
.combine_with (ctx
);
1479 /* Emulate effects of unary OPERATION and/or conversion from SRC_TYPE to
1480 DST_TYPE on value range in SRC_VR and store it to DST_VR. Return true if
1481 the result is a range or an anti-range. */
1484 ipa_vr_operation_and_type_effects (value_range
*dst_vr
,
1485 value_range
*src_vr
,
1486 enum tree_code operation
,
1487 tree dst_type
, tree src_type
)
1489 range_fold_unary_expr (dst_vr
, operation
, dst_type
, src_vr
, src_type
);
1490 if (dst_vr
->varying_p () || dst_vr
->undefined_p ())
1495 /* Determine value_range of JFUNC given that INFO describes the caller node or
1496 the one it is inlined to, CS is the call graph edge corresponding to JFUNC
1497 and PARM_TYPE of the parameter. */
1500 ipa_value_range_from_jfunc (ipa_node_params
*info
, cgraph_edge
*cs
,
1501 ipa_jump_func
*jfunc
, tree parm_type
)
1506 ipa_vr_operation_and_type_effects (&vr
,
1508 NOP_EXPR
, parm_type
,
1509 jfunc
->m_vr
->type ());
1510 if (vr
.singleton_p ())
1512 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1515 ipcp_transformation
*sum
1516 = ipcp_get_transformation_summary (cs
->caller
->inlined_to
1517 ? cs
->caller
->inlined_to
1519 if (!sum
|| !sum
->m_vr
)
1522 idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1524 if (!(*sum
->m_vr
)[idx
].known
)
1526 tree vr_type
= ipa_get_type (info
, idx
);
1527 value_range
srcvr (wide_int_to_tree (vr_type
, (*sum
->m_vr
)[idx
].min
),
1528 wide_int_to_tree (vr_type
, (*sum
->m_vr
)[idx
].max
),
1529 (*sum
->m_vr
)[idx
].type
);
1531 enum tree_code operation
= ipa_get_jf_pass_through_operation (jfunc
);
1533 if (TREE_CODE_CLASS (operation
) == tcc_unary
)
1537 if (ipa_vr_operation_and_type_effects (&res
,
1539 operation
, parm_type
,
1545 value_range op_res
, res
;
1546 tree op
= ipa_get_jf_pass_through_operand (jfunc
);
1547 value_range
op_vr (op
, op
);
1549 range_fold_binary_expr (&op_res
, operation
, vr_type
, &srcvr
, &op_vr
);
1550 if (ipa_vr_operation_and_type_effects (&res
,
1552 NOP_EXPR
, parm_type
,
1560 /* See if NODE is a clone with a known aggregate value at a given OFFSET of a
1561 parameter with the given INDEX. */
1564 get_clone_agg_value (struct cgraph_node
*node
, HOST_WIDE_INT offset
,
1567 struct ipa_agg_replacement_value
*aggval
;
1569 aggval
= ipa_get_agg_replacements_for_node (node
);
1572 if (aggval
->offset
== offset
1573 && aggval
->index
== index
)
1574 return aggval
->value
;
1575 aggval
= aggval
->next
;
1580 /* Determine whether ITEM, jump function for an aggregate part, evaluates to a
1581 single known constant value and if so, return it. Otherwise return NULL.
1582 NODE and INFO describes the caller node or the one it is inlined to, and
1583 its related info. */
1586 ipa_agg_value_from_node (class ipa_node_params
*info
,
1587 struct cgraph_node
*node
,
1588 struct ipa_agg_jf_item
*item
)
1590 tree value
= NULL_TREE
;
1593 if (item
->offset
< 0 || item
->jftype
== IPA_JF_UNKNOWN
)
1596 if (item
->jftype
== IPA_JF_CONST
)
1597 return item
->value
.constant
;
1599 gcc_checking_assert (item
->jftype
== IPA_JF_PASS_THROUGH
1600 || item
->jftype
== IPA_JF_LOAD_AGG
);
1602 src_idx
= item
->value
.pass_through
.formal_id
;
1604 if (info
->ipcp_orig_node
)
1606 if (item
->jftype
== IPA_JF_PASS_THROUGH
)
1607 value
= info
->known_csts
[src_idx
];
1609 value
= get_clone_agg_value (node
, item
->value
.load_agg
.offset
,
1612 else if (info
->lattices
)
1614 class ipcp_param_lattices
*src_plats
1615 = ipa_get_parm_lattices (info
, src_idx
);
1617 if (item
->jftype
== IPA_JF_PASS_THROUGH
)
1619 struct ipcp_lattice
<tree
> *lat
= &src_plats
->itself
;
1621 if (!lat
->is_single_const ())
1624 value
= lat
->values
->value
;
1626 else if (src_plats
->aggs
1627 && !src_plats
->aggs_bottom
1628 && !src_plats
->aggs_contain_variable
1629 && src_plats
->aggs_by_ref
== item
->value
.load_agg
.by_ref
)
1631 struct ipcp_agg_lattice
*aglat
;
1633 for (aglat
= src_plats
->aggs
; aglat
; aglat
= aglat
->next
)
1635 if (aglat
->offset
> item
->value
.load_agg
.offset
)
1638 if (aglat
->offset
== item
->value
.load_agg
.offset
)
1640 if (aglat
->is_single_const ())
1641 value
= aglat
->values
->value
;
1651 if (item
->jftype
== IPA_JF_LOAD_AGG
)
1653 tree load_type
= item
->value
.load_agg
.type
;
1654 tree value_type
= TREE_TYPE (value
);
1656 /* Ensure value type is compatible with load type. */
1657 if (!useless_type_conversion_p (load_type
, value_type
))
1661 return ipa_get_jf_arith_result (item
->value
.pass_through
.operation
,
1663 item
->value
.pass_through
.operand
,
1667 /* Determine whether AGG_JFUNC evaluates to a set of known constant value for
1668 an aggregate and if so, return it. Otherwise return an empty set. NODE
1669 and INFO describes the caller node or the one it is inlined to, and its
1672 struct ipa_agg_value_set
1673 ipa_agg_value_set_from_jfunc (class ipa_node_params
*info
, cgraph_node
*node
,
1674 struct ipa_agg_jump_function
*agg_jfunc
)
1676 struct ipa_agg_value_set agg
;
1677 struct ipa_agg_jf_item
*item
;
1681 agg
.by_ref
= agg_jfunc
->by_ref
;
1683 FOR_EACH_VEC_SAFE_ELT (agg_jfunc
->items
, i
, item
)
1685 tree value
= ipa_agg_value_from_node (info
, node
, item
);
1689 struct ipa_agg_value value_item
;
1691 value_item
.offset
= item
->offset
;
1692 value_item
.value
= value
;
1694 agg
.items
.safe_push (value_item
);
1700 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
1701 bottom, not containing a variable component and without any known value at
1705 ipcp_verify_propagated_values (void)
1707 struct cgraph_node
*node
;
1709 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
1711 class ipa_node_params
*info
= IPA_NODE_REF (node
);
1712 if (!opt_for_fn (node
->decl
, flag_ipa_cp
)
1713 || !opt_for_fn (node
->decl
, optimize
))
1715 int i
, count
= ipa_get_param_count (info
);
1717 for (i
= 0; i
< count
; i
++)
1719 ipcp_lattice
<tree
> *lat
= ipa_get_scalar_lat (info
, i
);
1722 && !lat
->contains_variable
1723 && lat
->values_count
== 0)
1727 symtab
->dump (dump_file
);
1728 fprintf (dump_file
, "\nIPA lattices after constant "
1729 "propagation, before gcc_unreachable:\n");
1730 print_all_lattices (dump_file
, true, false);
1739 /* Return true iff X and Y should be considered equal values by IPA-CP. */
1742 values_equal_for_ipcp_p (tree x
, tree y
)
1744 gcc_checking_assert (x
!= NULL_TREE
&& y
!= NULL_TREE
);
1749 if (TREE_CODE (x
) == ADDR_EXPR
1750 && TREE_CODE (y
) == ADDR_EXPR
1751 && TREE_CODE (TREE_OPERAND (x
, 0)) == CONST_DECL
1752 && TREE_CODE (TREE_OPERAND (y
, 0)) == CONST_DECL
)
1753 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x
, 0)),
1754 DECL_INITIAL (TREE_OPERAND (y
, 0)), 0);
1756 return operand_equal_p (x
, y
, 0);
1759 /* Return true iff X and Y should be considered equal contexts by IPA-CP. */
1762 values_equal_for_ipcp_p (ipa_polymorphic_call_context x
,
1763 ipa_polymorphic_call_context y
)
1765 return x
.equal_to (y
);
1769 /* Add a new value source to the value represented by THIS, marking that a
1770 value comes from edge CS and (if the underlying jump function is a
1771 pass-through or an ancestor one) from a caller value SRC_VAL of a caller
1772 parameter described by SRC_INDEX. OFFSET is negative if the source was the
1773 scalar value of the parameter itself or the offset within an aggregate. */
1775 template <typename valtype
>
1777 ipcp_value
<valtype
>::add_source (cgraph_edge
*cs
, ipcp_value
*src_val
,
1778 int src_idx
, HOST_WIDE_INT offset
)
1780 ipcp_value_source
<valtype
> *src
;
1782 src
= new (ipcp_sources_pool
.allocate ()) ipcp_value_source
<valtype
>;
1783 src
->offset
= offset
;
1786 src
->index
= src_idx
;
1788 src
->next
= sources
;
1792 /* Allocate a new ipcp_value holding a tree constant, initialize its value to
1793 SOURCE and clear all other fields. */
1795 static ipcp_value
<tree
> *
1796 allocate_and_init_ipcp_value (tree source
)
1798 ipcp_value
<tree
> *val
;
1800 val
= new (ipcp_cst_values_pool
.allocate ()) ipcp_value
<tree
>();
1801 val
->value
= source
;
1805 /* Allocate a new ipcp_value holding a polymorphic context, initialize its
1806 value to SOURCE and clear all other fields. */
1808 static ipcp_value
<ipa_polymorphic_call_context
> *
1809 allocate_and_init_ipcp_value (ipa_polymorphic_call_context source
)
1811 ipcp_value
<ipa_polymorphic_call_context
> *val
;
1814 val
= new (ipcp_poly_ctx_values_pool
.allocate ())
1815 ipcp_value
<ipa_polymorphic_call_context
>();
1816 val
->value
= source
;
1820 /* Try to add NEWVAL to LAT, potentially creating a new ipcp_value for it. CS,
1821 SRC_VAL SRC_INDEX and OFFSET are meant for add_source and have the same
1822 meaning. OFFSET -1 means the source is scalar and not a part of an
1823 aggregate. If non-NULL, VAL_P records address of existing or newly added
1824 ipcp_value. UNLIMITED means whether value count should not exceed the limit
1825 given by PARAM_IPA_CP_VALUE_LIST_SIZE. */
1827 template <typename valtype
>
1829 ipcp_lattice
<valtype
>::add_value (valtype newval
, cgraph_edge
*cs
,
1830 ipcp_value
<valtype
> *src_val
,
1831 int src_idx
, HOST_WIDE_INT offset
,
1832 ipcp_value
<valtype
> **val_p
,
1835 ipcp_value
<valtype
> *val
, *last_val
= NULL
;
1843 for (val
= values
; val
; last_val
= val
, val
= val
->next
)
1844 if (values_equal_for_ipcp_p (val
->value
, newval
))
1849 if (ipa_edge_within_scc (cs
))
1851 ipcp_value_source
<valtype
> *s
;
1852 for (s
= val
->sources
; s
; s
= s
->next
)
1859 val
->add_source (cs
, src_val
, src_idx
, offset
);
1863 if (!unlimited
&& values_count
== opt_for_fn (cs
->caller
->decl
,
1864 param_ipa_cp_value_list_size
))
1866 /* We can only free sources, not the values themselves, because sources
1867 of other values in this SCC might point to them. */
1868 for (val
= values
; val
; val
= val
->next
)
1870 while (val
->sources
)
1872 ipcp_value_source
<valtype
> *src
= val
->sources
;
1873 val
->sources
= src
->next
;
1874 ipcp_sources_pool
.remove ((ipcp_value_source
<tree
>*)src
);
1878 return set_to_bottom ();
1882 val
= allocate_and_init_ipcp_value (newval
);
1883 val
->add_source (cs
, src_val
, src_idx
, offset
);
1886 /* Add the new value to end of value list, which can reduce iterations
1887 of propagation stage for recursive function. */
1889 last_val
->next
= val
;
1899 /* Return true, if a ipcp_value VAL is orginated from parameter value of
1900 self-feeding recursive function by applying non-passthrough arithmetic
1904 self_recursively_generated_p (ipcp_value
<tree
> *val
)
1906 class ipa_node_params
*info
= NULL
;
1908 for (ipcp_value_source
<tree
> *src
= val
->sources
; src
; src
= src
->next
)
1910 cgraph_edge
*cs
= src
->cs
;
1912 if (!src
->val
|| cs
->caller
!= cs
->callee
->function_symbol ()
1917 info
= IPA_NODE_REF (cs
->caller
);
1919 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
,
1921 ipcp_lattice
<tree
> *src_lat
;
1922 ipcp_value
<tree
> *src_val
;
1924 if (src
->offset
== -1)
1925 src_lat
= &plats
->itself
;
1928 struct ipcp_agg_lattice
*src_aglat
;
1930 for (src_aglat
= plats
->aggs
; src_aglat
; src_aglat
= src_aglat
->next
)
1931 if (src_aglat
->offset
== src
->offset
)
1937 src_lat
= src_aglat
;
1940 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1951 /* A helper function that returns result of operation specified by OPCODE on
1952 the value of SRC_VAL. If non-NULL, OPND1_TYPE is expected type for the
1953 value of SRC_VAL. If the operation is binary, OPND2 is a constant value
1954 acting as its second operand. If non-NULL, RES_TYPE is expected type of
1958 get_val_across_arith_op (enum tree_code opcode
,
1961 ipcp_value
<tree
> *src_val
,
1964 tree opnd1
= src_val
->value
;
1966 /* Skip source values that is incompatible with specified type. */
1968 && !useless_type_conversion_p (opnd1_type
, TREE_TYPE (opnd1
)))
1971 return ipa_get_jf_arith_result (opcode
, opnd1
, opnd2
, res_type
);
1974 /* Propagate values through an arithmetic transformation described by a jump
1975 function associated with edge CS, taking values from SRC_LAT and putting
1976 them into DEST_LAT. OPND1_TYPE is expected type for the values in SRC_LAT.
1977 OPND2 is a constant value if transformation is a binary operation.
1978 SRC_OFFSET specifies offset in an aggregate if SRC_LAT describes lattice of
1979 a part of the aggregate. SRC_IDX is the index of the source parameter.
1980 RES_TYPE is the value type of result being propagated into. Return true if
1981 DEST_LAT changed. */
1984 propagate_vals_across_arith_jfunc (cgraph_edge
*cs
,
1985 enum tree_code opcode
,
1988 ipcp_lattice
<tree
> *src_lat
,
1989 ipcp_lattice
<tree
> *dest_lat
,
1990 HOST_WIDE_INT src_offset
,
1994 ipcp_value
<tree
> *src_val
;
1997 /* Due to circular dependencies, propagating within an SCC through arithmetic
1998 transformation would create infinite number of values. But for
1999 self-feeding recursive function, we could allow propagation in a limited
2000 count, and this can enable a simple kind of recursive function versioning.
2001 For other scenario, we would just make lattices bottom. */
2002 if (opcode
!= NOP_EXPR
&& ipa_edge_within_scc (cs
))
2006 int max_recursive_depth
= opt_for_fn(cs
->caller
->decl
,
2007 param_ipa_cp_max_recursive_depth
);
2008 if (src_lat
!= dest_lat
|| max_recursive_depth
< 1)
2009 return dest_lat
->set_contains_variable ();
2011 /* No benefit if recursive execution is in low probability. */
2012 if (cs
->sreal_frequency () * 100
2013 <= ((sreal
) 1) * opt_for_fn (cs
->caller
->decl
,
2014 param_ipa_cp_min_recursive_probability
))
2015 return dest_lat
->set_contains_variable ();
2017 auto_vec
<ipcp_value
<tree
> *, 8> val_seeds
;
2019 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
2021 /* Now we do not use self-recursively generated value as propagation
2022 source, this is absolutely conservative, but could avoid explosion
2023 of lattice's value space, especially when one recursive function
2024 calls another recursive. */
2025 if (self_recursively_generated_p (src_val
))
2027 ipcp_value_source
<tree
> *s
;
2029 /* If the lattice has already been propagated for the call site,
2030 no need to do that again. */
2031 for (s
= src_val
->sources
; s
; s
= s
->next
)
2033 return dest_lat
->set_contains_variable ();
2036 val_seeds
.safe_push (src_val
);
2039 gcc_assert ((int) val_seeds
.length () <= param_ipa_cp_value_list_size
);
2041 /* Recursively generate lattice values with a limited count. */
2042 FOR_EACH_VEC_ELT (val_seeds
, i
, src_val
)
2044 for (int j
= 1; j
< max_recursive_depth
; j
++)
2046 tree cstval
= get_val_across_arith_op (opcode
, opnd1_type
, opnd2
,
2051 ret
|= dest_lat
->add_value (cstval
, cs
, src_val
, src_idx
,
2052 src_offset
, &src_val
, true);
2053 gcc_checking_assert (src_val
);
2056 ret
|= dest_lat
->set_contains_variable ();
2059 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
2061 /* Now we do not use self-recursively generated value as propagation
2062 source, otherwise it is easy to make value space of normal lattice
2064 if (self_recursively_generated_p (src_val
))
2066 ret
|= dest_lat
->set_contains_variable ();
2070 tree cstval
= get_val_across_arith_op (opcode
, opnd1_type
, opnd2
,
2073 ret
|= dest_lat
->add_value (cstval
, cs
, src_val
, src_idx
,
2076 ret
|= dest_lat
->set_contains_variable ();
2082 /* Propagate values through a pass-through jump function JFUNC associated with
2083 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
2084 is the index of the source parameter. PARM_TYPE is the type of the
2085 parameter to which the result is passed. */
2088 propagate_vals_across_pass_through (cgraph_edge
*cs
, ipa_jump_func
*jfunc
,
2089 ipcp_lattice
<tree
> *src_lat
,
2090 ipcp_lattice
<tree
> *dest_lat
, int src_idx
,
2093 return propagate_vals_across_arith_jfunc (cs
,
2094 ipa_get_jf_pass_through_operation (jfunc
),
2096 ipa_get_jf_pass_through_operand (jfunc
),
2097 src_lat
, dest_lat
, -1, src_idx
, parm_type
);
2100 /* Propagate values through an ancestor jump function JFUNC associated with
2101 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
2102 is the index of the source parameter. */
2105 propagate_vals_across_ancestor (struct cgraph_edge
*cs
,
2106 struct ipa_jump_func
*jfunc
,
2107 ipcp_lattice
<tree
> *src_lat
,
2108 ipcp_lattice
<tree
> *dest_lat
, int src_idx
)
2110 ipcp_value
<tree
> *src_val
;
2113 if (ipa_edge_within_scc (cs
))
2114 return dest_lat
->set_contains_variable ();
2116 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
2118 tree t
= ipa_get_jf_ancestor_result (jfunc
, src_val
->value
);
2121 ret
|= dest_lat
->add_value (t
, cs
, src_val
, src_idx
);
2123 ret
|= dest_lat
->set_contains_variable ();
2129 /* Propagate scalar values across jump function JFUNC that is associated with
2130 edge CS and put the values into DEST_LAT. PARM_TYPE is the type of the
2131 parameter to which the result is passed. */
2134 propagate_scalar_across_jump_function (struct cgraph_edge
*cs
,
2135 struct ipa_jump_func
*jfunc
,
2136 ipcp_lattice
<tree
> *dest_lat
,
2139 if (dest_lat
->bottom
)
2142 if (jfunc
->type
== IPA_JF_CONST
)
2144 tree val
= ipa_get_jf_constant (jfunc
);
2145 return dest_lat
->add_value (val
, cs
, NULL
, 0);
2147 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
2148 || jfunc
->type
== IPA_JF_ANCESTOR
)
2150 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2151 ipcp_lattice
<tree
> *src_lat
;
2155 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
2156 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
2158 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
2160 src_lat
= ipa_get_scalar_lat (caller_info
, src_idx
);
2161 if (src_lat
->bottom
)
2162 return dest_lat
->set_contains_variable ();
2164 /* If we would need to clone the caller and cannot, do not propagate. */
2165 if (!ipcp_versionable_function_p (cs
->caller
)
2166 && (src_lat
->contains_variable
2167 || (src_lat
->values_count
> 1)))
2168 return dest_lat
->set_contains_variable ();
2170 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
2171 ret
= propagate_vals_across_pass_through (cs
, jfunc
, src_lat
,
2172 dest_lat
, src_idx
, param_type
);
2174 ret
= propagate_vals_across_ancestor (cs
, jfunc
, src_lat
, dest_lat
,
2177 if (src_lat
->contains_variable
)
2178 ret
|= dest_lat
->set_contains_variable ();
2183 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
2184 use it for indirect inlining), we should propagate them too. */
2185 return dest_lat
->set_contains_variable ();
2188 /* Propagate scalar values across jump function JFUNC that is associated with
2189 edge CS and describes argument IDX and put the values into DEST_LAT. */
2192 propagate_context_across_jump_function (cgraph_edge
*cs
,
2193 ipa_jump_func
*jfunc
, int idx
,
2194 ipcp_lattice
<ipa_polymorphic_call_context
> *dest_lat
)
2196 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
2197 if (dest_lat
->bottom
)
2200 bool added_sth
= false;
2201 bool type_preserved
= true;
2203 ipa_polymorphic_call_context edge_ctx
, *edge_ctx_ptr
2204 = ipa_get_ith_polymorhic_call_context (args
, idx
);
2207 edge_ctx
= *edge_ctx_ptr
;
2209 if (jfunc
->type
== IPA_JF_PASS_THROUGH
2210 || jfunc
->type
== IPA_JF_ANCESTOR
)
2212 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2214 ipcp_lattice
<ipa_polymorphic_call_context
> *src_lat
;
2216 /* TODO: Once we figure out how to propagate speculations, it will
2217 probably be a good idea to switch to speculation if type_preserved is
2218 not set instead of punting. */
2219 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
2221 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
2223 type_preserved
= ipa_get_jf_pass_through_type_preserved (jfunc
);
2224 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
2228 type_preserved
= ipa_get_jf_ancestor_type_preserved (jfunc
);
2229 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
2232 src_lat
= ipa_get_poly_ctx_lat (caller_info
, src_idx
);
2233 /* If we would need to clone the caller and cannot, do not propagate. */
2234 if (!ipcp_versionable_function_p (cs
->caller
)
2235 && (src_lat
->contains_variable
2236 || (src_lat
->values_count
> 1)))
2239 ipcp_value
<ipa_polymorphic_call_context
> *src_val
;
2240 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
2242 ipa_polymorphic_call_context cur
= src_val
->value
;
2244 if (!type_preserved
)
2245 cur
.possible_dynamic_type_change (cs
->in_polymorphic_cdtor
);
2246 if (jfunc
->type
== IPA_JF_ANCESTOR
)
2247 cur
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
2248 /* TODO: In cases we know how the context is going to be used,
2249 we can improve the result by passing proper OTR_TYPE. */
2250 cur
.combine_with (edge_ctx
);
2251 if (!cur
.useless_p ())
2253 if (src_lat
->contains_variable
2254 && !edge_ctx
.equal_to (cur
))
2255 ret
|= dest_lat
->set_contains_variable ();
2256 ret
|= dest_lat
->add_value (cur
, cs
, src_val
, src_idx
);
2265 if (!edge_ctx
.useless_p ())
2266 ret
|= dest_lat
->add_value (edge_ctx
, cs
);
2268 ret
|= dest_lat
->set_contains_variable ();
2274 /* Propagate bits across jfunc that is associated with
2275 edge cs and update dest_lattice accordingly. */
2278 propagate_bits_across_jump_function (cgraph_edge
*cs
, int idx
,
2279 ipa_jump_func
*jfunc
,
2280 ipcp_bits_lattice
*dest_lattice
)
2282 if (dest_lattice
->bottom_p ())
2285 enum availability availability
;
2286 cgraph_node
*callee
= cs
->callee
->function_symbol (&availability
);
2287 class ipa_node_params
*callee_info
= IPA_NODE_REF (callee
);
2288 tree parm_type
= ipa_get_type (callee_info
, idx
);
2290 /* For K&R C programs, ipa_get_type() could return NULL_TREE. Avoid the
2291 transform for these cases. Similarly, we can have bad type mismatches
2292 with LTO, avoid doing anything with those too. */
2294 || (!INTEGRAL_TYPE_P (parm_type
) && !POINTER_TYPE_P (parm_type
)))
2296 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2297 fprintf (dump_file
, "Setting dest_lattice to bottom, because type of "
2298 "param %i of %s is NULL or unsuitable for bits propagation\n",
2299 idx
, cs
->callee
->dump_name ());
2301 return dest_lattice
->set_to_bottom ();
2304 unsigned precision
= TYPE_PRECISION (parm_type
);
2305 signop sgn
= TYPE_SIGN (parm_type
);
2307 if (jfunc
->type
== IPA_JF_PASS_THROUGH
2308 || jfunc
->type
== IPA_JF_ANCESTOR
)
2310 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2311 tree operand
= NULL_TREE
;
2312 enum tree_code code
;
2315 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
2317 code
= ipa_get_jf_pass_through_operation (jfunc
);
2318 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
2319 if (code
!= NOP_EXPR
)
2320 operand
= ipa_get_jf_pass_through_operand (jfunc
);
2324 code
= POINTER_PLUS_EXPR
;
2325 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
2326 unsigned HOST_WIDE_INT offset
= ipa_get_jf_ancestor_offset (jfunc
) / BITS_PER_UNIT
;
2327 operand
= build_int_cstu (size_type_node
, offset
);
2330 class ipcp_param_lattices
*src_lats
2331 = ipa_get_parm_lattices (caller_info
, src_idx
);
2333 /* Try to propagate bits if src_lattice is bottom, but jfunc is known.
2339 Assume lattice for x is bottom, however we can still propagate
2340 result of x & 0xff == 0xff, which gets computed during ccp1 pass
2341 and we store it in jump function during analysis stage. */
2343 if (src_lats
->bits_lattice
.bottom_p ()
2345 return dest_lattice
->meet_with (jfunc
->bits
->value
, jfunc
->bits
->mask
,
2348 return dest_lattice
->meet_with (src_lats
->bits_lattice
, precision
, sgn
,
2352 else if (jfunc
->type
== IPA_JF_ANCESTOR
)
2353 return dest_lattice
->set_to_bottom ();
2354 else if (jfunc
->bits
)
2355 return dest_lattice
->meet_with (jfunc
->bits
->value
, jfunc
->bits
->mask
,
2358 return dest_lattice
->set_to_bottom ();
2361 /* Propagate value range across jump function JFUNC that is associated with
2362 edge CS with param of callee of PARAM_TYPE and update DEST_PLATS
2366 propagate_vr_across_jump_function (cgraph_edge
*cs
, ipa_jump_func
*jfunc
,
2367 class ipcp_param_lattices
*dest_plats
,
2370 ipcp_vr_lattice
*dest_lat
= &dest_plats
->m_value_range
;
2372 if (dest_lat
->bottom_p ())
2376 || (!INTEGRAL_TYPE_P (param_type
)
2377 && !POINTER_TYPE_P (param_type
)))
2378 return dest_lat
->set_to_bottom ();
2380 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
2382 enum tree_code operation
= ipa_get_jf_pass_through_operation (jfunc
);
2383 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2384 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
2385 class ipcp_param_lattices
*src_lats
2386 = ipa_get_parm_lattices (caller_info
, src_idx
);
2387 tree operand_type
= ipa_get_type (caller_info
, src_idx
);
2389 if (src_lats
->m_value_range
.bottom_p ())
2390 return dest_lat
->set_to_bottom ();
2393 if (TREE_CODE_CLASS (operation
) == tcc_unary
)
2394 ipa_vr_operation_and_type_effects (&vr
,
2395 &src_lats
->m_value_range
.m_vr
,
2396 operation
, param_type
,
2398 /* A crude way to prevent unbounded number of value range updates
2399 in SCC components. We should allow limited number of updates within
2401 else if (!ipa_edge_within_scc (cs
))
2403 tree op
= ipa_get_jf_pass_through_operand (jfunc
);
2404 value_range
op_vr (op
, op
);
2405 value_range op_res
,res
;
2407 range_fold_binary_expr (&op_res
, operation
, operand_type
,
2408 &src_lats
->m_value_range
.m_vr
, &op_vr
);
2409 ipa_vr_operation_and_type_effects (&vr
,
2411 NOP_EXPR
, param_type
,
2414 if (!vr
.undefined_p () && !vr
.varying_p ())
2419 if (ipa_vr_operation_and_type_effects (&jvr
, jfunc
->m_vr
,
2422 jfunc
->m_vr
->type ()))
2425 return dest_lat
->meet_with (&vr
);
2428 else if (jfunc
->type
== IPA_JF_CONST
)
2430 tree val
= ipa_get_jf_constant (jfunc
);
2431 if (TREE_CODE (val
) == INTEGER_CST
)
2433 val
= fold_convert (param_type
, val
);
2434 if (TREE_OVERFLOW_P (val
))
2435 val
= drop_tree_overflow (val
);
2437 value_range
tmpvr (val
, val
);
2438 return dest_lat
->meet_with (&tmpvr
);
2444 && ipa_vr_operation_and_type_effects (&vr
, jfunc
->m_vr
, NOP_EXPR
,
2446 jfunc
->m_vr
->type ()))
2447 return dest_lat
->meet_with (&vr
);
2449 return dest_lat
->set_to_bottom ();
2452 /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
2453 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
2454 other cases, return false). If there are no aggregate items, set
2455 aggs_by_ref to NEW_AGGS_BY_REF. */
2458 set_check_aggs_by_ref (class ipcp_param_lattices
*dest_plats
,
2459 bool new_aggs_by_ref
)
2461 if (dest_plats
->aggs
)
2463 if (dest_plats
->aggs_by_ref
!= new_aggs_by_ref
)
2465 set_agg_lats_to_bottom (dest_plats
);
2470 dest_plats
->aggs_by_ref
= new_aggs_by_ref
;
2474 /* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
2475 already existing lattice for the given OFFSET and SIZE, marking all skipped
2476 lattices as containing variable and checking for overlaps. If there is no
2477 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
2478 it with offset, size and contains_variable to PRE_EXISTING, and return true,
2479 unless there are too many already. If there are two many, return false. If
2480 there are overlaps turn whole DEST_PLATS to bottom and return false. If any
2481 skipped lattices were newly marked as containing variable, set *CHANGE to
2485 merge_agg_lats_step (class ipcp_param_lattices
*dest_plats
,
2486 HOST_WIDE_INT offset
, HOST_WIDE_INT val_size
,
2487 struct ipcp_agg_lattice
***aglat
,
2488 bool pre_existing
, bool *change
)
2490 gcc_checking_assert (offset
>= 0);
2492 while (**aglat
&& (**aglat
)->offset
< offset
)
2494 if ((**aglat
)->offset
+ (**aglat
)->size
> offset
)
2496 set_agg_lats_to_bottom (dest_plats
);
2499 *change
|= (**aglat
)->set_contains_variable ();
2500 *aglat
= &(**aglat
)->next
;
2503 if (**aglat
&& (**aglat
)->offset
== offset
)
2505 if ((**aglat
)->size
!= val_size
)
2507 set_agg_lats_to_bottom (dest_plats
);
2510 gcc_assert (!(**aglat
)->next
2511 || (**aglat
)->next
->offset
>= offset
+ val_size
);
2516 struct ipcp_agg_lattice
*new_al
;
2518 if (**aglat
&& (**aglat
)->offset
< offset
+ val_size
)
2520 set_agg_lats_to_bottom (dest_plats
);
2523 if (dest_plats
->aggs_count
== param_ipa_max_agg_items
)
2525 dest_plats
->aggs_count
++;
2526 new_al
= ipcp_agg_lattice_pool
.allocate ();
2527 memset (new_al
, 0, sizeof (*new_al
));
2529 new_al
->offset
= offset
;
2530 new_al
->size
= val_size
;
2531 new_al
->contains_variable
= pre_existing
;
2533 new_al
->next
= **aglat
;
2539 /* Set all AGLAT and all other aggregate lattices reachable by next pointers as
2540 containing an unknown value. */
2543 set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice
*aglat
)
2548 ret
|= aglat
->set_contains_variable ();
2549 aglat
= aglat
->next
;
2554 /* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
2555 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source
2556 parameter used for lattice value sources. Return true if DEST_PLATS changed
2560 merge_aggregate_lattices (struct cgraph_edge
*cs
,
2561 class ipcp_param_lattices
*dest_plats
,
2562 class ipcp_param_lattices
*src_plats
,
2563 int src_idx
, HOST_WIDE_INT offset_delta
)
2565 bool pre_existing
= dest_plats
->aggs
!= NULL
;
2566 struct ipcp_agg_lattice
**dst_aglat
;
2569 if (set_check_aggs_by_ref (dest_plats
, src_plats
->aggs_by_ref
))
2571 if (src_plats
->aggs_bottom
)
2572 return set_agg_lats_contain_variable (dest_plats
);
2573 if (src_plats
->aggs_contain_variable
)
2574 ret
|= set_agg_lats_contain_variable (dest_plats
);
2575 dst_aglat
= &dest_plats
->aggs
;
2577 for (struct ipcp_agg_lattice
*src_aglat
= src_plats
->aggs
;
2579 src_aglat
= src_aglat
->next
)
2581 HOST_WIDE_INT new_offset
= src_aglat
->offset
- offset_delta
;
2585 if (merge_agg_lats_step (dest_plats
, new_offset
, src_aglat
->size
,
2586 &dst_aglat
, pre_existing
, &ret
))
2588 struct ipcp_agg_lattice
*new_al
= *dst_aglat
;
2590 dst_aglat
= &(*dst_aglat
)->next
;
2591 if (src_aglat
->bottom
)
2593 ret
|= new_al
->set_contains_variable ();
2596 if (src_aglat
->contains_variable
)
2597 ret
|= new_al
->set_contains_variable ();
2598 for (ipcp_value
<tree
> *val
= src_aglat
->values
;
2601 ret
|= new_al
->add_value (val
->value
, cs
, val
, src_idx
,
2604 else if (dest_plats
->aggs_bottom
)
2607 ret
|= set_chain_of_aglats_contains_variable (*dst_aglat
);
2611 /* Determine whether there is anything to propagate FROM SRC_PLATS through a
2612 pass-through JFUNC and if so, whether it has conform and conforms to the
2613 rules about propagating values passed by reference. */
2616 agg_pass_through_permissible_p (class ipcp_param_lattices
*src_plats
,
2617 struct ipa_jump_func
*jfunc
)
2619 return src_plats
->aggs
2620 && (!src_plats
->aggs_by_ref
2621 || ipa_get_jf_pass_through_agg_preserved (jfunc
));
2624 /* Propagate values through ITEM, jump function for a part of an aggregate,
2625 into corresponding aggregate lattice AGLAT. CS is the call graph edge
2626 associated with the jump function. Return true if AGLAT changed in any
2630 propagate_aggregate_lattice (struct cgraph_edge
*cs
,
2631 struct ipa_agg_jf_item
*item
,
2632 struct ipcp_agg_lattice
*aglat
)
2634 class ipa_node_params
*caller_info
;
2635 class ipcp_param_lattices
*src_plats
;
2636 struct ipcp_lattice
<tree
> *src_lat
;
2637 HOST_WIDE_INT src_offset
;
2642 if (item
->jftype
== IPA_JF_CONST
)
2644 tree value
= item
->value
.constant
;
2646 gcc_checking_assert (is_gimple_ip_invariant (value
));
2647 return aglat
->add_value (value
, cs
, NULL
, 0);
2650 gcc_checking_assert (item
->jftype
== IPA_JF_PASS_THROUGH
2651 || item
->jftype
== IPA_JF_LOAD_AGG
);
2653 caller_info
= IPA_NODE_REF (cs
->caller
);
2654 src_idx
= item
->value
.pass_through
.formal_id
;
2655 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2657 if (item
->jftype
== IPA_JF_PASS_THROUGH
)
2659 load_type
= NULL_TREE
;
2660 src_lat
= &src_plats
->itself
;
2665 HOST_WIDE_INT load_offset
= item
->value
.load_agg
.offset
;
2666 struct ipcp_agg_lattice
*src_aglat
;
2668 for (src_aglat
= src_plats
->aggs
; src_aglat
; src_aglat
= src_aglat
->next
)
2669 if (src_aglat
->offset
>= load_offset
)
2672 load_type
= item
->value
.load_agg
.type
;
2674 || src_aglat
->offset
> load_offset
2675 || src_aglat
->size
!= tree_to_shwi (TYPE_SIZE (load_type
))
2676 || src_plats
->aggs_by_ref
!= item
->value
.load_agg
.by_ref
)
2677 return aglat
->set_contains_variable ();
2679 src_lat
= src_aglat
;
2680 src_offset
= load_offset
;
2684 || (!ipcp_versionable_function_p (cs
->caller
)
2685 && !src_lat
->is_single_const ()))
2686 return aglat
->set_contains_variable ();
2688 ret
= propagate_vals_across_arith_jfunc (cs
,
2689 item
->value
.pass_through
.operation
,
2691 item
->value
.pass_through
.operand
,
2697 if (src_lat
->contains_variable
)
2698 ret
|= aglat
->set_contains_variable ();
2703 /* Propagate scalar values across jump function JFUNC that is associated with
2704 edge CS and put the values into DEST_LAT. */
2707 propagate_aggs_across_jump_function (struct cgraph_edge
*cs
,
2708 struct ipa_jump_func
*jfunc
,
2709 class ipcp_param_lattices
*dest_plats
)
2713 if (dest_plats
->aggs_bottom
)
2716 if (jfunc
->type
== IPA_JF_PASS_THROUGH
2717 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
2719 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2720 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
2721 class ipcp_param_lattices
*src_plats
;
2723 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2724 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
2726 /* Currently we do not produce clobber aggregate jump
2727 functions, replace with merging when we do. */
2728 gcc_assert (!jfunc
->agg
.items
);
2729 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
,
2733 ret
|= set_agg_lats_contain_variable (dest_plats
);
2735 else if (jfunc
->type
== IPA_JF_ANCESTOR
2736 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
2738 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2739 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
2740 class ipcp_param_lattices
*src_plats
;
2742 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2743 if (src_plats
->aggs
&& src_plats
->aggs_by_ref
)
2745 /* Currently we do not produce clobber aggregate jump
2746 functions, replace with merging when we do. */
2747 gcc_assert (!jfunc
->agg
.items
);
2748 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
, src_idx
,
2749 ipa_get_jf_ancestor_offset (jfunc
));
2751 else if (!src_plats
->aggs_by_ref
)
2752 ret
|= set_agg_lats_to_bottom (dest_plats
);
2754 ret
|= set_agg_lats_contain_variable (dest_plats
);
2756 else if (jfunc
->agg
.items
)
2758 bool pre_existing
= dest_plats
->aggs
!= NULL
;
2759 struct ipcp_agg_lattice
**aglat
= &dest_plats
->aggs
;
2760 struct ipa_agg_jf_item
*item
;
2763 if (set_check_aggs_by_ref (dest_plats
, jfunc
->agg
.by_ref
))
2766 FOR_EACH_VEC_ELT (*jfunc
->agg
.items
, i
, item
)
2768 HOST_WIDE_INT val_size
;
2770 if (item
->offset
< 0 || item
->jftype
== IPA_JF_UNKNOWN
)
2772 val_size
= tree_to_shwi (TYPE_SIZE (item
->type
));
2774 if (merge_agg_lats_step (dest_plats
, item
->offset
, val_size
,
2775 &aglat
, pre_existing
, &ret
))
2777 ret
|= propagate_aggregate_lattice (cs
, item
, *aglat
);
2778 aglat
= &(*aglat
)->next
;
2780 else if (dest_plats
->aggs_bottom
)
2784 ret
|= set_chain_of_aglats_contains_variable (*aglat
);
2787 ret
|= set_agg_lats_contain_variable (dest_plats
);
2792 /* Return true if on the way cfrom CS->caller to the final (non-alias and
2793 non-thunk) destination, the call passes through a thunk. */
2796 call_passes_through_thunk_p (cgraph_edge
*cs
)
2798 cgraph_node
*alias_or_thunk
= cs
->callee
;
2799 while (alias_or_thunk
->alias
)
2800 alias_or_thunk
= alias_or_thunk
->get_alias_target ();
2801 return alias_or_thunk
->thunk
.thunk_p
;
2804 /* Propagate constants from the caller to the callee of CS. INFO describes the
2808 propagate_constants_across_call (struct cgraph_edge
*cs
)
2810 class ipa_node_params
*callee_info
;
2811 enum availability availability
;
2812 cgraph_node
*callee
;
2813 class ipa_edge_args
*args
;
2815 int i
, args_count
, parms_count
;
2817 callee
= cs
->callee
->function_symbol (&availability
);
2818 if (!callee
->definition
)
2820 gcc_checking_assert (callee
->has_gimple_body_p ());
2821 callee_info
= IPA_NODE_REF (callee
);
2825 args
= IPA_EDGE_REF (cs
);
2826 parms_count
= ipa_get_param_count (callee_info
);
2827 if (parms_count
== 0)
2830 || !opt_for_fn (cs
->caller
->decl
, flag_ipa_cp
)
2831 || !opt_for_fn (cs
->caller
->decl
, optimize
))
2833 for (i
= 0; i
< parms_count
; i
++)
2834 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
2838 args_count
= ipa_get_cs_argument_count (args
);
2840 /* If this call goes through a thunk we must not propagate to the first (0th)
2841 parameter. However, we might need to uncover a thunk from below a series
2842 of aliases first. */
2843 if (call_passes_through_thunk_p (cs
))
2845 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
2852 for (; (i
< args_count
) && (i
< parms_count
); i
++)
2854 struct ipa_jump_func
*jump_func
= ipa_get_ith_jump_func (args
, i
);
2855 class ipcp_param_lattices
*dest_plats
;
2856 tree param_type
= ipa_get_type (callee_info
, i
);
2858 dest_plats
= ipa_get_parm_lattices (callee_info
, i
);
2859 if (availability
== AVAIL_INTERPOSABLE
)
2860 ret
|= set_all_contains_variable (dest_plats
);
2863 ret
|= propagate_scalar_across_jump_function (cs
, jump_func
,
2864 &dest_plats
->itself
,
2866 ret
|= propagate_context_across_jump_function (cs
, jump_func
, i
,
2867 &dest_plats
->ctxlat
);
2869 |= propagate_bits_across_jump_function (cs
, i
, jump_func
,
2870 &dest_plats
->bits_lattice
);
2871 ret
|= propagate_aggs_across_jump_function (cs
, jump_func
,
2873 if (opt_for_fn (callee
->decl
, flag_ipa_vrp
))
2874 ret
|= propagate_vr_across_jump_function (cs
, jump_func
,
2875 dest_plats
, param_type
);
2877 ret
|= dest_plats
->m_value_range
.set_to_bottom ();
2880 for (; i
< parms_count
; i
++)
2881 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
, i
));
2886 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
2887 KNOWN_CONTEXTS, KNOWN_AGGS or AGG_REPS return the destination. The latter
2888 three can be NULL. If AGG_REPS is not NULL, KNOWN_AGGS is ignored. */
2891 ipa_get_indirect_edge_target_1 (struct cgraph_edge
*ie
,
2892 vec
<tree
> known_csts
,
2893 vec
<ipa_polymorphic_call_context
> known_contexts
,
2894 vec
<ipa_agg_value_set
> known_aggs
,
2895 struct ipa_agg_replacement_value
*agg_reps
,
2898 int param_index
= ie
->indirect_info
->param_index
;
2899 HOST_WIDE_INT anc_offset
;
2903 *speculative
= false;
2905 if (param_index
== -1)
2908 if (!ie
->indirect_info
->polymorphic
)
2912 if (ie
->indirect_info
->agg_contents
)
2915 if (agg_reps
&& ie
->indirect_info
->guaranteed_unmodified
)
2919 if (agg_reps
->index
== param_index
2920 && agg_reps
->offset
== ie
->indirect_info
->offset
2921 && agg_reps
->by_ref
== ie
->indirect_info
->by_ref
)
2923 t
= agg_reps
->value
;
2926 agg_reps
= agg_reps
->next
;
2931 struct ipa_agg_value_set
*agg
;
2932 if (known_aggs
.length () > (unsigned int) param_index
)
2933 agg
= &known_aggs
[param_index
];
2936 bool from_global_constant
;
2937 t
= ipa_find_agg_cst_for_param (agg
,
2938 (unsigned) param_index
2939 < known_csts
.length ()
2940 ? known_csts
[param_index
]
2942 ie
->indirect_info
->offset
,
2943 ie
->indirect_info
->by_ref
,
2944 &from_global_constant
);
2946 && !from_global_constant
2947 && !ie
->indirect_info
->guaranteed_unmodified
)
2951 else if ((unsigned) param_index
< known_csts
.length ())
2952 t
= known_csts
[param_index
];
2955 && TREE_CODE (t
) == ADDR_EXPR
2956 && TREE_CODE (TREE_OPERAND (t
, 0)) == FUNCTION_DECL
)
2957 return TREE_OPERAND (t
, 0);
2962 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize
))
2965 gcc_assert (!ie
->indirect_info
->agg_contents
);
2966 anc_offset
= ie
->indirect_info
->offset
;
2970 /* Try to work out value of virtual table pointer value in replacements. */
2971 if (!t
&& agg_reps
&& !ie
->indirect_info
->by_ref
)
2975 if (agg_reps
->index
== param_index
2976 && agg_reps
->offset
== ie
->indirect_info
->offset
2977 && agg_reps
->by_ref
)
2979 t
= agg_reps
->value
;
2982 agg_reps
= agg_reps
->next
;
2986 /* Try to work out value of virtual table pointer value in known
2987 aggregate values. */
2988 if (!t
&& known_aggs
.length () > (unsigned int) param_index
2989 && !ie
->indirect_info
->by_ref
)
2991 struct ipa_agg_value_set
*agg
= &known_aggs
[param_index
];
2992 t
= ipa_find_agg_cst_for_param (agg
,
2993 (unsigned) param_index
2994 < known_csts
.length ()
2995 ? known_csts
[param_index
] : NULL
,
2996 ie
->indirect_info
->offset
, true);
2999 /* If we found the virtual table pointer, lookup the target. */
3003 unsigned HOST_WIDE_INT offset
;
3004 if (vtable_pointer_value_to_vtable (t
, &vtable
, &offset
))
3007 target
= gimple_get_virt_method_for_vtable (ie
->indirect_info
->otr_token
,
3008 vtable
, offset
, &can_refer
);
3012 || fndecl_built_in_p (target
, BUILT_IN_UNREACHABLE
)
3013 || !possible_polymorphic_call_target_p
3014 (ie
, cgraph_node::get (target
)))
3016 /* Do not speculate builtin_unreachable, it is stupid! */
3017 if (ie
->indirect_info
->vptr_changed
)
3019 target
= ipa_impossible_devirt_target (ie
, target
);
3021 *speculative
= ie
->indirect_info
->vptr_changed
;
3028 /* Do we know the constant value of pointer? */
3029 if (!t
&& (unsigned) param_index
< known_csts
.length ())
3030 t
= known_csts
[param_index
];
3032 gcc_checking_assert (!t
|| TREE_CODE (t
) != TREE_BINFO
);
3034 ipa_polymorphic_call_context context
;
3035 if (known_contexts
.length () > (unsigned int) param_index
)
3037 context
= known_contexts
[param_index
];
3038 context
.offset_by (anc_offset
);
3039 if (ie
->indirect_info
->vptr_changed
)
3040 context
.possible_dynamic_type_change (ie
->in_polymorphic_cdtor
,
3041 ie
->indirect_info
->otr_type
);
3044 ipa_polymorphic_call_context ctx2
= ipa_polymorphic_call_context
3045 (t
, ie
->indirect_info
->otr_type
, anc_offset
);
3046 if (!ctx2
.useless_p ())
3047 context
.combine_with (ctx2
, ie
->indirect_info
->otr_type
);
3052 context
= ipa_polymorphic_call_context (t
, ie
->indirect_info
->otr_type
,
3054 if (ie
->indirect_info
->vptr_changed
)
3055 context
.possible_dynamic_type_change (ie
->in_polymorphic_cdtor
,
3056 ie
->indirect_info
->otr_type
);
3061 vec
<cgraph_node
*>targets
;
3064 targets
= possible_polymorphic_call_targets
3065 (ie
->indirect_info
->otr_type
,
3066 ie
->indirect_info
->otr_token
,
3068 if (!final
|| targets
.length () > 1)
3070 struct cgraph_node
*node
;
3073 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize_speculatively
)
3074 || ie
->speculative
|| !ie
->maybe_hot_p ())
3076 node
= try_speculative_devirtualization (ie
->indirect_info
->otr_type
,
3077 ie
->indirect_info
->otr_token
,
3081 *speculative
= true;
3082 target
= node
->decl
;
3089 *speculative
= false;
3090 if (targets
.length () == 1)
3091 target
= targets
[0]->decl
;
3093 target
= ipa_impossible_devirt_target (ie
, NULL_TREE
);
3096 if (target
&& !possible_polymorphic_call_target_p (ie
,
3097 cgraph_node::get (target
)))
3101 target
= ipa_impossible_devirt_target (ie
, target
);
3108 /* If an indirect edge IE can be turned into a direct one based on KNOWN_CSTS,
3109 KNOWN_CONTEXTS (which can be vNULL) or KNOWN_AGGS (which also can be vNULL)
3110 return the destination. */
3113 ipa_get_indirect_edge_target (struct cgraph_edge
*ie
,
3114 vec
<tree
> known_csts
,
3115 vec
<ipa_polymorphic_call_context
> known_contexts
,
3116 vec
<ipa_agg_value_set
> known_aggs
,
3119 return ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
3120 known_aggs
, NULL
, speculative
);
3123 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
3124 and KNOWN_CONTEXTS. */
3127 devirtualization_time_bonus (struct cgraph_node
*node
,
3128 vec
<tree
> known_csts
,
3129 vec
<ipa_polymorphic_call_context
> known_contexts
,
3130 vec
<ipa_agg_value_set
> known_aggs
)
3132 struct cgraph_edge
*ie
;
3135 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
3137 struct cgraph_node
*callee
;
3138 class ipa_fn_summary
*isummary
;
3139 enum availability avail
;
3143 target
= ipa_get_indirect_edge_target (ie
, known_csts
, known_contexts
,
3144 known_aggs
, &speculative
);
3148 /* Only bare minimum benefit for clearly un-inlineable targets. */
3150 callee
= cgraph_node::get (target
);
3151 if (!callee
|| !callee
->definition
)
3153 callee
= callee
->function_symbol (&avail
);
3154 if (avail
< AVAIL_AVAILABLE
)
3156 isummary
= ipa_fn_summaries
->get (callee
);
3157 if (!isummary
->inlinable
)
3160 int size
= ipa_size_summaries
->get (callee
)->size
;
3161 /* FIXME: The values below need re-considering and perhaps also
3162 integrating into the cost metrics, at lest in some very basic way. */
3163 int max_inline_insns_auto
3164 = opt_for_fn (callee
->decl
, param_max_inline_insns_auto
);
3165 if (size
<= max_inline_insns_auto
/ 4)
3166 res
+= 31 / ((int)speculative
+ 1);
3167 else if (size
<= max_inline_insns_auto
/ 2)
3168 res
+= 15 / ((int)speculative
+ 1);
3169 else if (size
<= max_inline_insns_auto
3170 || DECL_DECLARED_INLINE_P (callee
->decl
))
3171 res
+= 7 / ((int)speculative
+ 1);
3177 /* Return time bonus incurred because of HINTS. */
3180 hint_time_bonus (cgraph_node
*node
, ipa_hints hints
)
3183 if (hints
& (INLINE_HINT_loop_iterations
| INLINE_HINT_loop_stride
))
3184 result
+= opt_for_fn (node
->decl
, param_ipa_cp_loop_hint_bonus
);
3188 /* If there is a reason to penalize the function described by INFO in the
3189 cloning goodness evaluation, do so. */
3191 static inline int64_t
3192 incorporate_penalties (cgraph_node
*node
, ipa_node_params
*info
,
3195 if (info
->node_within_scc
&& !info
->node_is_self_scc
)
3196 evaluation
= (evaluation
3197 * (100 - opt_for_fn (node
->decl
,
3198 param_ipa_cp_recursion_penalty
))) / 100;
3200 if (info
->node_calling_single_call
)
3201 evaluation
= (evaluation
3202 * (100 - opt_for_fn (node
->decl
,
3203 param_ipa_cp_single_call_penalty
)))
3209 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
3210 and SIZE_COST and with the sum of frequencies of incoming edges to the
3211 potential new clone in FREQUENCIES. */
3214 good_cloning_opportunity_p (struct cgraph_node
*node
, int time_benefit
,
3215 int freq_sum
, profile_count count_sum
, int size_cost
)
3217 if (time_benefit
== 0
3218 || !opt_for_fn (node
->decl
, flag_ipa_cp_clone
)
3219 || node
->optimize_for_size_p ())
3222 gcc_assert (size_cost
> 0);
3224 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3225 int eval_threshold
= opt_for_fn (node
->decl
, param_ipa_cp_eval_threshold
);
3226 if (max_count
> profile_count::zero ())
3228 int factor
= RDIV (count_sum
.probability_in
3229 (max_count
).to_reg_br_prob_base ()
3230 * 1000, REG_BR_PROB_BASE
);
3231 int64_t evaluation
= (((int64_t) time_benefit
* factor
)
3233 evaluation
= incorporate_penalties (node
, info
, evaluation
);
3235 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3237 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
3238 "size: %i, count_sum: ", time_benefit
, size_cost
);
3239 count_sum
.dump (dump_file
);
3240 fprintf (dump_file
, "%s%s) -> evaluation: " "%" PRId64
3241 ", threshold: %i\n",
3242 info
->node_within_scc
3243 ? (info
->node_is_self_scc
? ", self_scc" : ", scc") : "",
3244 info
->node_calling_single_call
? ", single_call" : "",
3245 evaluation
, eval_threshold
);
3248 return evaluation
>= eval_threshold
;
3252 int64_t evaluation
= (((int64_t) time_benefit
* freq_sum
)
3254 evaluation
= incorporate_penalties (node
, info
, evaluation
);
3256 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3257 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
3258 "size: %i, freq_sum: %i%s%s) -> evaluation: "
3259 "%" PRId64
", threshold: %i\n",
3260 time_benefit
, size_cost
, freq_sum
,
3261 info
->node_within_scc
3262 ? (info
->node_is_self_scc
? ", self_scc" : ", scc") : "",
3263 info
->node_calling_single_call
? ", single_call" : "",
3264 evaluation
, eval_threshold
);
3266 return evaluation
>= eval_threshold
;
3270 /* Return all context independent values from aggregate lattices in PLATS in a
3271 vector. Return NULL if there are none. */
3273 static vec
<ipa_agg_value
>
3274 context_independent_aggregate_values (class ipcp_param_lattices
*plats
)
3276 vec
<ipa_agg_value
> res
= vNULL
;
3278 if (plats
->aggs_bottom
3279 || plats
->aggs_contain_variable
3280 || plats
->aggs_count
== 0)
3283 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
;
3285 aglat
= aglat
->next
)
3286 if (aglat
->is_single_const ())
3288 struct ipa_agg_value item
;
3289 item
.offset
= aglat
->offset
;
3290 item
.value
= aglat
->values
->value
;
3291 res
.safe_push (item
);
3296 /* Allocate KNOWN_CSTS, KNOWN_CONTEXTS and, if non-NULL, KNOWN_AGGS and
3297 populate them with values of parameters that are known independent of the
3298 context. INFO describes the function. If REMOVABLE_PARAMS_COST is
3299 non-NULL, the movement cost of all removable parameters will be stored in
3303 gather_context_independent_values (class ipa_node_params
*info
,
3304 vec
<tree
> *known_csts
,
3305 vec
<ipa_polymorphic_call_context
>
3307 vec
<ipa_agg_value_set
> *known_aggs
,
3308 int *removable_params_cost
)
3310 int i
, count
= ipa_get_param_count (info
);
3313 known_csts
->create (0);
3314 known_contexts
->create (0);
3315 known_csts
->safe_grow_cleared (count
);
3316 known_contexts
->safe_grow_cleared (count
);
3319 known_aggs
->create (0);
3320 known_aggs
->safe_grow_cleared (count
);
3323 if (removable_params_cost
)
3324 *removable_params_cost
= 0;
3326 for (i
= 0; i
< count
; i
++)
3328 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3329 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
3331 if (lat
->is_single_const ())
3333 ipcp_value
<tree
> *val
= lat
->values
;
3334 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
3335 (*known_csts
)[i
] = val
->value
;
3336 if (removable_params_cost
)
3337 *removable_params_cost
3338 += estimate_move_cost (TREE_TYPE (val
->value
), false);
3341 else if (removable_params_cost
3342 && !ipa_is_param_used (info
, i
))
3343 *removable_params_cost
3344 += ipa_get_param_move_cost (info
, i
);
3346 if (!ipa_is_param_used (info
, i
))
3349 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
3350 /* Do not account known context as reason for cloning. We can see
3351 if it permits devirtualization. */
3352 if (ctxlat
->is_single_const ())
3353 (*known_contexts
)[i
] = ctxlat
->values
->value
;
3357 vec
<ipa_agg_value
> agg_items
;
3358 struct ipa_agg_value_set
*agg
;
3360 agg_items
= context_independent_aggregate_values (plats
);
3361 agg
= &(*known_aggs
)[i
];
3362 agg
->items
= agg_items
;
3363 agg
->by_ref
= plats
->aggs_by_ref
;
3364 ret
|= !agg_items
.is_empty ();
3371 /* Perform time and size measurement of NODE with the context given in
3372 KNOWN_CSTS, KNOWN_CONTEXTS and KNOWN_AGGS, calculate the benefit and cost
3373 given BASE_TIME of the node without specialization, REMOVABLE_PARAMS_COST of
3374 all context-independent removable parameters and EST_MOVE_COST of estimated
3375 movement of the considered parameter and store it into VAL. */
3378 perform_estimation_of_a_value (cgraph_node
*node
, vec
<tree
> known_csts
,
3379 vec
<ipa_polymorphic_call_context
> known_contexts
,
3380 vec
<ipa_agg_value_set
> known_aggs
,
3381 int removable_params_cost
,
3382 int est_move_cost
, ipcp_value_base
*val
)
3384 int size
, time_benefit
;
3385 sreal time
, base_time
;
3388 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
3389 known_aggs
, &size
, &time
,
3390 &base_time
, &hints
);
3392 if (base_time
> 65535)
3395 /* Extern inline functions have no cloning local time benefits because they
3396 will be inlined anyway. The only reason to clone them is if it enables
3397 optimization in any of the functions they call. */
3398 if (DECL_EXTERNAL (node
->decl
) && DECL_DECLARED_INLINE_P (node
->decl
))
3401 time_benefit
= base_time
.to_int ()
3402 + devirtualization_time_bonus (node
, known_csts
, known_contexts
,
3404 + hint_time_bonus (node
, hints
)
3405 + removable_params_cost
+ est_move_cost
;
3407 gcc_checking_assert (size
>=0);
3408 /* The inliner-heuristics based estimates may think that in certain
3409 contexts some functions do not have any size at all but we want
3410 all specializations to have at least a tiny cost, not least not to
3415 val
->local_time_benefit
= time_benefit
;
3416 val
->local_size_cost
= size
;
3419 /* Iterate over known values of parameters of NODE and estimate the local
3420 effects in terms of time and size they have. */
3423 estimate_local_effects (struct cgraph_node
*node
)
3425 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3426 int i
, count
= ipa_get_param_count (info
);
3427 vec
<tree
> known_csts
;
3428 vec
<ipa_polymorphic_call_context
> known_contexts
;
3429 vec
<ipa_agg_value_set
> known_aggs
;
3431 int removable_params_cost
;
3433 if (!count
|| !ipcp_versionable_function_p (node
))
3436 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3437 fprintf (dump_file
, "\nEstimating effects for %s.\n", node
->dump_name ());
3439 always_const
= gather_context_independent_values (info
, &known_csts
,
3440 &known_contexts
, &known_aggs
,
3441 &removable_params_cost
);
3442 int devirt_bonus
= devirtualization_time_bonus (node
, known_csts
,
3443 known_contexts
, known_aggs
);
3444 if (always_const
|| devirt_bonus
3445 || (removable_params_cost
&& node
->can_change_signature
))
3447 struct caller_statistics stats
;
3449 sreal time
, base_time
;
3452 init_caller_stats (&stats
);
3453 node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
3455 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
3456 known_aggs
, &size
, &time
,
3457 &base_time
, &hints
);
3458 time
-= devirt_bonus
;
3459 time
-= hint_time_bonus (node
, hints
);
3460 time
-= removable_params_cost
;
3461 size
-= stats
.n_calls
* removable_params_cost
;
3464 fprintf (dump_file
, " - context independent values, size: %i, "
3465 "time_benefit: %f\n", size
, (base_time
- time
).to_double ());
3467 if (size
<= 0 || node
->local
)
3469 info
->do_clone_for_all_contexts
= true;
3472 fprintf (dump_file
, " Decided to specialize for all "
3473 "known contexts, code not going to grow.\n");
3475 else if (good_cloning_opportunity_p (node
,
3476 MIN ((base_time
- time
).to_int (),
3478 stats
.freq_sum
, stats
.count_sum
,
3481 if (size
+ overall_size
<= max_new_size
)
3483 info
->do_clone_for_all_contexts
= true;
3484 overall_size
+= size
;
3487 fprintf (dump_file
, " Decided to specialize for all "
3488 "known contexts, growth deemed beneficial.\n");
3490 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3491 fprintf (dump_file
, " Not cloning for all contexts because "
3492 "max_new_size would be reached with %li.\n",
3493 size
+ overall_size
);
3495 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3496 fprintf (dump_file
, " Not cloning for all contexts because "
3497 "!good_cloning_opportunity_p.\n");
3501 for (i
= 0; i
< count
; i
++)
3503 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3504 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
3505 ipcp_value
<tree
> *val
;
3512 for (val
= lat
->values
; val
; val
= val
->next
)
3514 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
3515 known_csts
[i
] = val
->value
;
3517 int emc
= estimate_move_cost (TREE_TYPE (val
->value
), true);
3518 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
3520 removable_params_cost
, emc
, val
);
3522 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3524 fprintf (dump_file
, " - estimates for value ");
3525 print_ipcp_constant_value (dump_file
, val
->value
);
3526 fprintf (dump_file
, " for ");
3527 ipa_dump_param (dump_file
, info
, i
);
3528 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
3529 val
->local_time_benefit
, val
->local_size_cost
);
3532 known_csts
[i
] = NULL_TREE
;
3535 for (i
= 0; i
< count
; i
++)
3537 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3539 if (!plats
->virt_call
)
3542 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
3543 ipcp_value
<ipa_polymorphic_call_context
> *val
;
3547 || !known_contexts
[i
].useless_p ())
3550 for (val
= ctxlat
->values
; val
; val
= val
->next
)
3552 known_contexts
[i
] = val
->value
;
3553 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
3555 removable_params_cost
, 0, val
);
3557 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3559 fprintf (dump_file
, " - estimates for polymorphic context ");
3560 print_ipcp_constant_value (dump_file
, val
->value
);
3561 fprintf (dump_file
, " for ");
3562 ipa_dump_param (dump_file
, info
, i
);
3563 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
3564 val
->local_time_benefit
, val
->local_size_cost
);
3567 known_contexts
[i
] = ipa_polymorphic_call_context ();
3570 for (i
= 0; i
< count
; i
++)
3572 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3573 struct ipa_agg_value_set
*agg
;
3574 struct ipcp_agg_lattice
*aglat
;
3576 if (plats
->aggs_bottom
|| !plats
->aggs
)
3579 agg
= &known_aggs
[i
];
3580 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3582 ipcp_value
<tree
> *val
;
3583 if (aglat
->bottom
|| !aglat
->values
3584 /* If the following is true, the one value is in known_aggs. */
3585 || (!plats
->aggs_contain_variable
3586 && aglat
->is_single_const ()))
3589 for (val
= aglat
->values
; val
; val
= val
->next
)
3591 struct ipa_agg_value item
;
3593 item
.offset
= aglat
->offset
;
3594 item
.value
= val
->value
;
3595 agg
->items
.safe_push (item
);
3597 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
3599 removable_params_cost
, 0, val
);
3601 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3603 fprintf (dump_file
, " - estimates for value ");
3604 print_ipcp_constant_value (dump_file
, val
->value
);
3605 fprintf (dump_file
, " for ");
3606 ipa_dump_param (dump_file
, info
, i
);
3607 fprintf (dump_file
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
3608 "]: time_benefit: %i, size: %i\n",
3609 plats
->aggs_by_ref
? "ref " : "",
3611 val
->local_time_benefit
, val
->local_size_cost
);
3619 known_csts
.release ();
3620 known_contexts
.release ();
3621 ipa_release_agg_values (known_aggs
);
3625 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
3626 topological sort of values. */
3628 template <typename valtype
>
3630 value_topo_info
<valtype
>::add_val (ipcp_value
<valtype
> *cur_val
)
3632 ipcp_value_source
<valtype
> *src
;
3638 cur_val
->dfs
= dfs_counter
;
3639 cur_val
->low_link
= dfs_counter
;
3641 cur_val
->topo_next
= stack
;
3643 cur_val
->on_stack
= true;
3645 for (src
= cur_val
->sources
; src
; src
= src
->next
)
3648 if (src
->val
->dfs
== 0)
3651 if (src
->val
->low_link
< cur_val
->low_link
)
3652 cur_val
->low_link
= src
->val
->low_link
;
3654 else if (src
->val
->on_stack
3655 && src
->val
->dfs
< cur_val
->low_link
)
3656 cur_val
->low_link
= src
->val
->dfs
;
3659 if (cur_val
->dfs
== cur_val
->low_link
)
3661 ipcp_value
<valtype
> *v
, *scc_list
= NULL
;
3666 stack
= v
->topo_next
;
3667 v
->on_stack
= false;
3669 v
->scc_next
= scc_list
;
3672 while (v
!= cur_val
);
3674 cur_val
->topo_next
= values_topo
;
3675 values_topo
= cur_val
;
3679 /* Add all values in lattices associated with NODE to the topological sort if
3680 they are not there yet. */
3683 add_all_node_vals_to_toposort (cgraph_node
*node
, ipa_topo_info
*topo
)
3685 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3686 int i
, count
= ipa_get_param_count (info
);
3688 for (i
= 0; i
< count
; i
++)
3690 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3691 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
3692 struct ipcp_agg_lattice
*aglat
;
3696 ipcp_value
<tree
> *val
;
3697 for (val
= lat
->values
; val
; val
= val
->next
)
3698 topo
->constants
.add_val (val
);
3701 if (!plats
->aggs_bottom
)
3702 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3705 ipcp_value
<tree
> *val
;
3706 for (val
= aglat
->values
; val
; val
= val
->next
)
3707 topo
->constants
.add_val (val
);
3710 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
3711 if (!ctxlat
->bottom
)
3713 ipcp_value
<ipa_polymorphic_call_context
> *ctxval
;
3714 for (ctxval
= ctxlat
->values
; ctxval
; ctxval
= ctxval
->next
)
3715 topo
->contexts
.add_val (ctxval
);
3720 /* One pass of constants propagation along the call graph edges, from callers
3721 to callees (requires topological ordering in TOPO), iterate over strongly
3722 connected components. */
3725 propagate_constants_topo (class ipa_topo_info
*topo
)
3729 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
3732 struct cgraph_node
*v
, *node
= topo
->order
[i
];
3733 vec
<cgraph_node
*> cycle_nodes
= ipa_get_nodes_in_cycle (node
);
3735 /* First, iteratively propagate within the strongly connected component
3736 until all lattices stabilize. */
3737 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
3738 if (v
->has_gimple_body_p ())
3740 if (opt_for_fn (v
->decl
, flag_ipa_cp
)
3741 && opt_for_fn (v
->decl
, optimize
))
3742 push_node_to_stack (topo
, v
);
3743 /* When V is not optimized, we can not push it to stack, but
3744 still we need to set all its callees lattices to bottom. */
3747 for (cgraph_edge
*cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3748 propagate_constants_across_call (cs
);
3752 v
= pop_node_from_stack (topo
);
3755 struct cgraph_edge
*cs
;
3756 class ipa_node_params
*info
= NULL
;
3757 bool self_scc
= true;
3759 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3760 if (ipa_edge_within_scc (cs
))
3762 cgraph_node
*callee
= cs
->callee
->function_symbol ();
3769 info
= IPA_NODE_REF (v
);
3770 info
->node_within_scc
= true;
3773 if (propagate_constants_across_call (cs
))
3774 push_node_to_stack (topo
, callee
);
3778 info
->node_is_self_scc
= self_scc
;
3780 v
= pop_node_from_stack (topo
);
3783 /* Afterwards, propagate along edges leading out of the SCC, calculates
3784 the local effects of the discovered constants and all valid values to
3785 their topological sort. */
3786 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
3787 if (v
->has_gimple_body_p ()
3788 && opt_for_fn (v
->decl
, flag_ipa_cp
)
3789 && opt_for_fn (v
->decl
, optimize
))
3791 struct cgraph_edge
*cs
;
3793 estimate_local_effects (v
);
3794 add_all_node_vals_to_toposort (v
, topo
);
3795 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3796 if (!ipa_edge_within_scc (cs
))
3797 propagate_constants_across_call (cs
);
3799 cycle_nodes
.release ();
3804 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
3805 the bigger one if otherwise. */
3808 safe_add (int a
, int b
)
3810 if (a
> INT_MAX
/2 || b
> INT_MAX
/2)
3811 return a
> b
? a
: b
;
3817 /* Propagate the estimated effects of individual values along the topological
3818 from the dependent values to those they depend on. */
3820 template <typename valtype
>
3822 value_topo_info
<valtype
>::propagate_effects ()
3824 ipcp_value
<valtype
> *base
;
3826 for (base
= values_topo
; base
; base
= base
->topo_next
)
3828 ipcp_value_source
<valtype
> *src
;
3829 ipcp_value
<valtype
> *val
;
3830 int time
= 0, size
= 0;
3832 for (val
= base
; val
; val
= val
->scc_next
)
3834 time
= safe_add (time
,
3835 val
->local_time_benefit
+ val
->prop_time_benefit
);
3836 size
= safe_add (size
, val
->local_size_cost
+ val
->prop_size_cost
);
3839 for (val
= base
; val
; val
= val
->scc_next
)
3840 for (src
= val
->sources
; src
; src
= src
->next
)
3842 && src
->cs
->maybe_hot_p ())
3844 src
->val
->prop_time_benefit
= safe_add (time
,
3845 src
->val
->prop_time_benefit
);
3846 src
->val
->prop_size_cost
= safe_add (size
,
3847 src
->val
->prop_size_cost
);
3853 /* Propagate constants, polymorphic contexts and their effects from the
3854 summaries interprocedurally. */
3857 ipcp_propagate_stage (class ipa_topo_info
*topo
)
3859 struct cgraph_node
*node
;
3862 fprintf (dump_file
, "\n Propagating constants:\n\n");
3864 max_count
= profile_count::uninitialized ();
3866 FOR_EACH_DEFINED_FUNCTION (node
)
3868 if (node
->has_gimple_body_p ()
3869 && opt_for_fn (node
->decl
, flag_ipa_cp
)
3870 && opt_for_fn (node
->decl
, optimize
))
3872 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3873 determine_versionability (node
, info
);
3874 info
->lattices
= XCNEWVEC (class ipcp_param_lattices
,
3875 ipa_get_param_count (info
));
3876 initialize_node_lattices (node
);
3878 ipa_size_summary
*s
= ipa_size_summaries
->get (node
);
3879 if (node
->definition
&& !node
->alias
&& s
!= NULL
)
3880 overall_size
+= s
->self_size
;
3881 max_count
= max_count
.max (node
->count
.ipa ());
3884 max_new_size
= overall_size
;
3885 if (max_new_size
< param_large_unit_insns
)
3886 max_new_size
= param_large_unit_insns
;
3887 max_new_size
+= max_new_size
* param_ipa_cp_unit_growth
/ 100 + 1;
3890 fprintf (dump_file
, "\noverall_size: %li, max_new_size: %li\n",
3891 overall_size
, max_new_size
);
3893 propagate_constants_topo (topo
);
3895 ipcp_verify_propagated_values ();
3896 topo
->constants
.propagate_effects ();
3897 topo
->contexts
.propagate_effects ();
3901 fprintf (dump_file
, "\nIPA lattices after all propagation:\n");
3902 print_all_lattices (dump_file
, (dump_flags
& TDF_DETAILS
), true);
3906 /* Discover newly direct outgoing edges from NODE which is a new clone with
3907 known KNOWN_CSTS and make them direct. */
3910 ipcp_discover_new_direct_edges (struct cgraph_node
*node
,
3911 vec
<tree
> known_csts
,
3912 vec
<ipa_polymorphic_call_context
>
3914 struct ipa_agg_replacement_value
*aggvals
)
3916 struct cgraph_edge
*ie
, *next_ie
;
3919 for (ie
= node
->indirect_calls
; ie
; ie
= next_ie
)
3924 next_ie
= ie
->next_callee
;
3925 target
= ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
3926 vNULL
, aggvals
, &speculative
);
3929 bool agg_contents
= ie
->indirect_info
->agg_contents
;
3930 bool polymorphic
= ie
->indirect_info
->polymorphic
;
3931 int param_index
= ie
->indirect_info
->param_index
;
3932 struct cgraph_edge
*cs
= ipa_make_edge_direct_to_target (ie
, target
,
3936 if (cs
&& !agg_contents
&& !polymorphic
)
3938 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3939 int c
= ipa_get_controlled_uses (info
, param_index
);
3940 if (c
!= IPA_UNDESCRIBED_USE
)
3942 struct ipa_ref
*to_del
;
3945 ipa_set_controlled_uses (info
, param_index
, c
);
3946 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3947 fprintf (dump_file
, " controlled uses count of param "
3948 "%i bumped down to %i\n", param_index
, c
);
3950 && (to_del
= node
->find_reference (cs
->callee
, NULL
, 0)))
3952 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3953 fprintf (dump_file
, " and even removing its "
3954 "cloning-created reference\n");
3955 to_del
->remove_reference ();
3961 /* Turning calls to direct calls will improve overall summary. */
3963 ipa_update_overall_fn_summary (node
);
3966 class edge_clone_summary
;
3967 static call_summary
<edge_clone_summary
*> *edge_clone_summaries
= NULL
;
3969 /* Edge clone summary. */
3971 class edge_clone_summary
3974 /* Default constructor. */
3975 edge_clone_summary (): prev_clone (NULL
), next_clone (NULL
) {}
3977 /* Default destructor. */
3978 ~edge_clone_summary ()
3981 edge_clone_summaries
->get (prev_clone
)->next_clone
= next_clone
;
3983 edge_clone_summaries
->get (next_clone
)->prev_clone
= prev_clone
;
3986 cgraph_edge
*prev_clone
;
3987 cgraph_edge
*next_clone
;
3990 class edge_clone_summary_t
:
3991 public call_summary
<edge_clone_summary
*>
3994 edge_clone_summary_t (symbol_table
*symtab
):
3995 call_summary
<edge_clone_summary
*> (symtab
)
3997 m_initialize_when_cloning
= true;
4000 virtual void duplicate (cgraph_edge
*src_edge
, cgraph_edge
*dst_edge
,
4001 edge_clone_summary
*src_data
,
4002 edge_clone_summary
*dst_data
);
4005 /* Edge duplication hook. */
4008 edge_clone_summary_t::duplicate (cgraph_edge
*src_edge
, cgraph_edge
*dst_edge
,
4009 edge_clone_summary
*src_data
,
4010 edge_clone_summary
*dst_data
)
4012 if (src_data
->next_clone
)
4013 edge_clone_summaries
->get (src_data
->next_clone
)->prev_clone
= dst_edge
;
4014 dst_data
->prev_clone
= src_edge
;
4015 dst_data
->next_clone
= src_data
->next_clone
;
4016 src_data
->next_clone
= dst_edge
;
4019 /* Return true is NODE is DEST or its clone for all contexts. */
4022 same_node_or_its_all_contexts_clone_p (cgraph_node
*node
, cgraph_node
*dest
)
4027 class ipa_node_params
*info
= IPA_NODE_REF (node
);
4028 return info
->is_all_contexts_clone
&& info
->ipcp_orig_node
== dest
;
4031 /* Return true if edge CS does bring about the value described by SRC to
4032 DEST_VAL of node DEST or its clone for all contexts. */
4035 cgraph_edge_brings_value_p (cgraph_edge
*cs
, ipcp_value_source
<tree
> *src
,
4036 cgraph_node
*dest
, ipcp_value
<tree
> *dest_val
)
4038 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4039 enum availability availability
;
4040 cgraph_node
*real_dest
= cs
->callee
->function_symbol (&availability
);
4042 if (availability
<= AVAIL_INTERPOSABLE
4043 || !same_node_or_its_all_contexts_clone_p (real_dest
, dest
)
4044 || caller_info
->node_dead
)
4050 if (caller_info
->ipcp_orig_node
)
4053 if (src
->offset
== -1)
4054 t
= caller_info
->known_csts
[src
->index
];
4056 t
= get_clone_agg_value (cs
->caller
, src
->offset
, src
->index
);
4057 return (t
!= NULL_TREE
4058 && values_equal_for_ipcp_p (src
->val
->value
, t
));
4062 /* At the moment we do not propagate over arithmetic jump functions in
4063 SCCs, so it is safe to detect self-feeding recursive calls in this
4065 if (src
->val
== dest_val
)
4068 struct ipcp_agg_lattice
*aglat
;
4069 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
4071 if (src
->offset
== -1)
4072 return (plats
->itself
.is_single_const ()
4073 && values_equal_for_ipcp_p (src
->val
->value
,
4074 plats
->itself
.values
->value
));
4077 if (plats
->aggs_bottom
|| plats
->aggs_contain_variable
)
4079 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
4080 if (aglat
->offset
== src
->offset
)
4081 return (aglat
->is_single_const ()
4082 && values_equal_for_ipcp_p (src
->val
->value
,
4083 aglat
->values
->value
));
4089 /* Return true if edge CS does bring about the value described by SRC to
4090 DST_VAL of node DEST or its clone for all contexts. */
4093 cgraph_edge_brings_value_p (cgraph_edge
*cs
,
4094 ipcp_value_source
<ipa_polymorphic_call_context
> *src
,
4096 ipcp_value
<ipa_polymorphic_call_context
> *)
4098 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4099 enum availability avail
;
4100 cgraph_node
*real_dest
= cs
->callee
->function_symbol (&avail
);
4102 if (avail
<= AVAIL_INTERPOSABLE
4103 || !same_node_or_its_all_contexts_clone_p (real_dest
, dest
)
4104 || caller_info
->node_dead
)
4109 if (caller_info
->ipcp_orig_node
)
4110 return (caller_info
->known_contexts
.length () > (unsigned) src
->index
)
4111 && values_equal_for_ipcp_p (src
->val
->value
,
4112 caller_info
->known_contexts
[src
->index
]);
4114 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
4116 return plats
->ctxlat
.is_single_const ()
4117 && values_equal_for_ipcp_p (src
->val
->value
,
4118 plats
->ctxlat
.values
->value
);
4121 /* Get the next clone in the linked list of clones of an edge. */
4123 static inline struct cgraph_edge
*
4124 get_next_cgraph_edge_clone (struct cgraph_edge
*cs
)
4126 edge_clone_summary
*s
= edge_clone_summaries
->get (cs
);
4127 return s
!= NULL
? s
->next_clone
: NULL
;
4130 /* Given VAL that is intended for DEST, iterate over all its sources and if any
4131 of them is viable and hot, return true. In that case, for those that still
4132 hold, add their edge frequency and their number into *FREQUENCY and
4133 *CALLER_COUNT respectively. */
4135 template <typename valtype
>
4137 get_info_about_necessary_edges (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
4139 profile_count
*count_sum
, int *caller_count
)
4141 ipcp_value_source
<valtype
> *src
;
4142 int freq
= 0, count
= 0;
4143 profile_count cnt
= profile_count::zero ();
4145 bool non_self_recursive
= false;
4147 for (src
= val
->sources
; src
; src
= src
->next
)
4149 struct cgraph_edge
*cs
= src
->cs
;
4152 if (cgraph_edge_brings_value_p (cs
, src
, dest
, val
))
4155 freq
+= cs
->frequency ();
4156 if (cs
->count
.ipa ().initialized_p ())
4157 cnt
+= cs
->count
.ipa ();
4158 hot
|= cs
->maybe_hot_p ();
4159 if (cs
->caller
!= dest
)
4160 non_self_recursive
= true;
4162 gcc_assert (values_equal_for_ipcp_p (src
->val
->value
,
4165 cs
= get_next_cgraph_edge_clone (cs
);
4169 /* If the only edges bringing a value are self-recursive ones, do not bother
4171 if (!non_self_recursive
)
4176 *caller_count
= count
;
4178 if (!hot
&& IPA_NODE_REF (dest
)->node_within_scc
)
4180 struct cgraph_edge
*cs
;
4182 /* Cold non-SCC source edge could trigger hot recursive execution of
4183 function. Consider the case as hot and rely on following cost model
4184 computation to further select right one. */
4185 for (cs
= dest
->callers
; cs
; cs
= cs
->next_caller
)
4186 if (cs
->caller
== dest
&& cs
->maybe_hot_p ())
4193 /* Return a vector of incoming edges that do bring value VAL to node DEST. It
4194 is assumed their number is known and equal to CALLER_COUNT. */
4196 template <typename valtype
>
4197 static vec
<cgraph_edge
*>
4198 gather_edges_for_value (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
4201 ipcp_value_source
<valtype
> *src
;
4202 vec
<cgraph_edge
*> ret
;
4204 ret
.create (caller_count
);
4205 for (src
= val
->sources
; src
; src
= src
->next
)
4207 struct cgraph_edge
*cs
= src
->cs
;
4210 if (cgraph_edge_brings_value_p (cs
, src
, dest
, val
))
4211 ret
.quick_push (cs
);
4212 cs
= get_next_cgraph_edge_clone (cs
);
4219 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
4220 Return it or NULL if for some reason it cannot be created. */
4222 static struct ipa_replace_map
*
4223 get_replacement_map (class ipa_node_params
*info
, tree value
, int parm_num
)
4225 struct ipa_replace_map
*replace_map
;
4228 replace_map
= ggc_alloc
<ipa_replace_map
> ();
4231 fprintf (dump_file
, " replacing ");
4232 ipa_dump_param (dump_file
, info
, parm_num
);
4234 fprintf (dump_file
, " with const ");
4235 print_generic_expr (dump_file
, value
);
4236 fprintf (dump_file
, "\n");
4238 replace_map
->parm_num
= parm_num
;
4239 replace_map
->new_tree
= value
;
4243 /* Dump new profiling counts */
4246 dump_profile_updates (struct cgraph_node
*orig_node
,
4247 struct cgraph_node
*new_node
)
4249 struct cgraph_edge
*cs
;
4251 fprintf (dump_file
, " setting count of the specialized node to ");
4252 new_node
->count
.dump (dump_file
);
4253 fprintf (dump_file
, "\n");
4254 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
4256 fprintf (dump_file
, " edge to %s has count ",
4257 cs
->callee
->dump_name ());
4258 cs
->count
.dump (dump_file
);
4259 fprintf (dump_file
, "\n");
4262 fprintf (dump_file
, " setting count of the original node to ");
4263 orig_node
->count
.dump (dump_file
);
4264 fprintf (dump_file
, "\n");
4265 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
4267 fprintf (dump_file
, " edge to %s is left with ",
4268 cs
->callee
->dump_name ());
4269 cs
->count
.dump (dump_file
);
4270 fprintf (dump_file
, "\n");
4274 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
4275 their profile information to reflect this. */
4278 update_profiling_info (struct cgraph_node
*orig_node
,
4279 struct cgraph_node
*new_node
)
4281 struct cgraph_edge
*cs
;
4282 struct caller_statistics stats
;
4283 profile_count new_sum
, orig_sum
;
4284 profile_count remainder
, orig_node_count
= orig_node
->count
;
4285 profile_count orig_new_node_count
= new_node
->count
;
4287 if (!(orig_node_count
.ipa () > profile_count::zero ()))
4290 init_caller_stats (&stats
);
4291 orig_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
4293 orig_sum
= stats
.count_sum
;
4294 init_caller_stats (&stats
);
4295 new_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
4297 new_sum
= stats
.count_sum
;
4299 if (orig_node_count
< orig_sum
+ new_sum
)
4303 fprintf (dump_file
, " Problem: node %s has too low count ",
4304 orig_node
->dump_name ());
4305 orig_node_count
.dump (dump_file
);
4306 fprintf (dump_file
, "while the sum of incoming count is ");
4307 (orig_sum
+ new_sum
).dump (dump_file
);
4308 fprintf (dump_file
, "\n");
4311 orig_node_count
= (orig_sum
+ new_sum
).apply_scale (12, 10);
4314 fprintf (dump_file
, " proceeding by pretending it was ");
4315 orig_node_count
.dump (dump_file
);
4316 fprintf (dump_file
, "\n");
4320 remainder
= orig_node_count
.combine_with_ipa_count (orig_node_count
.ipa ()
4323 /* With partial train run we do not want to assume that original's
4324 count is zero whenever we redurect all executed edges to clone.
4325 Simply drop profile to local one in this case. */
4326 if (remainder
.ipa_p () && !remainder
.ipa ().nonzero_p ()
4327 && orig_node
->count
.ipa_p () && orig_node
->count
.ipa ().nonzero_p ()
4328 && flag_profile_partial_training
)
4329 remainder
= remainder
.guessed_local ();
4331 new_sum
= orig_node_count
.combine_with_ipa_count (new_sum
);
4332 new_node
->count
= new_sum
;
4333 orig_node
->count
= remainder
;
4335 profile_count::adjust_for_ipa_scaling (&new_sum
, &orig_new_node_count
);
4336 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
4337 cs
->count
= cs
->count
.apply_scale (new_sum
, orig_new_node_count
);
4338 for (cs
= new_node
->indirect_calls
; cs
; cs
= cs
->next_callee
)
4339 cs
->count
= cs
->count
.apply_scale (new_sum
, orig_new_node_count
);
4341 profile_count::adjust_for_ipa_scaling (&remainder
, &orig_node_count
);
4342 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
4343 cs
->count
= cs
->count
.apply_scale (remainder
, orig_node_count
);
4344 for (cs
= orig_node
->indirect_calls
; cs
; cs
= cs
->next_callee
)
4345 cs
->count
= cs
->count
.apply_scale (remainder
, orig_node_count
);
4348 dump_profile_updates (orig_node
, new_node
);
4351 /* Update the respective profile of specialized NEW_NODE and the original
4352 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
4353 have been redirected to the specialized version. */
4356 update_specialized_profile (struct cgraph_node
*new_node
,
4357 struct cgraph_node
*orig_node
,
4358 profile_count redirected_sum
)
4360 struct cgraph_edge
*cs
;
4361 profile_count new_node_count
, orig_node_count
= orig_node
->count
;
4365 fprintf (dump_file
, " the sum of counts of redirected edges is ");
4366 redirected_sum
.dump (dump_file
);
4367 fprintf (dump_file
, "\n");
4369 if (!(orig_node_count
> profile_count::zero ()))
4372 gcc_assert (orig_node_count
>= redirected_sum
);
4374 new_node_count
= new_node
->count
;
4375 new_node
->count
+= redirected_sum
;
4376 orig_node
->count
-= redirected_sum
;
4378 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
4379 cs
->count
+= cs
->count
.apply_scale (redirected_sum
, new_node_count
);
4381 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
4383 profile_count dec
= cs
->count
.apply_scale (redirected_sum
,
4389 dump_profile_updates (orig_node
, new_node
);
4392 /* Return true if we would like to remove a parameter from NODE when cloning it
4393 with KNOWN_CSTS scalar constants. */
4396 want_remove_some_param_p (cgraph_node
*node
, vec
<tree
> known_csts
)
4398 auto_vec
<bool, 16> surviving
;
4399 bool filled_vec
= false;
4400 ipa_node_params
*info
= IPA_NODE_REF (node
);
4401 int i
, count
= ipa_get_param_count (info
);
4403 for (i
= 0; i
< count
; i
++)
4405 if (!known_csts
[i
] && ipa_is_param_used (info
, i
))
4410 if (!node
->clone
.param_adjustments
)
4412 node
->clone
.param_adjustments
->get_surviving_params (&surviving
);
4415 if (surviving
.length() < (unsigned) i
&& surviving
[i
])
4421 /* Create a specialized version of NODE with known constants in KNOWN_CSTS,
4422 known contexts in KNOWN_CONTEXTS and known aggregate values in AGGVALS and
4423 redirect all edges in CALLERS to it. */
4425 static struct cgraph_node
*
4426 create_specialized_node (struct cgraph_node
*node
,
4427 vec
<tree
> known_csts
,
4428 vec
<ipa_polymorphic_call_context
> known_contexts
,
4429 struct ipa_agg_replacement_value
*aggvals
,
4430 vec
<cgraph_edge
*> callers
)
4432 class ipa_node_params
*new_info
, *info
= IPA_NODE_REF (node
);
4433 vec
<ipa_replace_map
*, va_gc
> *replace_trees
= NULL
;
4434 vec
<ipa_adjusted_param
, va_gc
> *new_params
= NULL
;
4435 struct ipa_agg_replacement_value
*av
;
4436 struct cgraph_node
*new_node
;
4437 int i
, count
= ipa_get_param_count (info
);
4438 ipa_param_adjustments
*old_adjustments
= node
->clone
.param_adjustments
;
4439 ipa_param_adjustments
*new_adjustments
;
4440 gcc_assert (!info
->ipcp_orig_node
);
4441 gcc_assert (node
->can_change_signature
4442 || !old_adjustments
);
4444 if (old_adjustments
)
4446 /* At the moment all IPA optimizations should use the number of
4447 parameters of the prevailing decl as the m_always_copy_start.
4448 Handling any other value would complicate the code below, so for the
4449 time bing let's only assert it is so. */
4450 gcc_assert (old_adjustments
->m_always_copy_start
== count
4451 || old_adjustments
->m_always_copy_start
< 0);
4452 int old_adj_count
= vec_safe_length (old_adjustments
->m_adj_params
);
4453 for (i
= 0; i
< old_adj_count
; i
++)
4455 ipa_adjusted_param
*old_adj
= &(*old_adjustments
->m_adj_params
)[i
];
4456 if (!node
->can_change_signature
4457 || old_adj
->op
!= IPA_PARAM_OP_COPY
4458 || (!known_csts
[old_adj
->base_index
]
4459 && ipa_is_param_used (info
, old_adj
->base_index
)))
4461 ipa_adjusted_param new_adj
= *old_adj
;
4463 new_adj
.prev_clone_adjustment
= true;
4464 new_adj
.prev_clone_index
= i
;
4465 vec_safe_push (new_params
, new_adj
);
4468 bool skip_return
= old_adjustments
->m_skip_return
;
4469 new_adjustments
= (new (ggc_alloc
<ipa_param_adjustments
> ())
4470 ipa_param_adjustments (new_params
, count
,
4473 else if (node
->can_change_signature
4474 && want_remove_some_param_p (node
, known_csts
))
4476 ipa_adjusted_param adj
;
4477 memset (&adj
, 0, sizeof (adj
));
4478 adj
.op
= IPA_PARAM_OP_COPY
;
4479 for (i
= 0; i
< count
; i
++)
4480 if (!known_csts
[i
] && ipa_is_param_used (info
, i
))
4483 adj
.prev_clone_index
= i
;
4484 vec_safe_push (new_params
, adj
);
4486 new_adjustments
= (new (ggc_alloc
<ipa_param_adjustments
> ())
4487 ipa_param_adjustments (new_params
, count
, false));
4490 new_adjustments
= NULL
;
4492 replace_trees
= vec_safe_copy (node
->clone
.tree_map
);
4493 for (i
= 0; i
< count
; i
++)
4495 tree t
= known_csts
[i
];
4498 struct ipa_replace_map
*replace_map
;
4500 gcc_checking_assert (TREE_CODE (t
) != TREE_BINFO
);
4501 replace_map
= get_replacement_map (info
, t
, i
);
4503 vec_safe_push (replace_trees
, replace_map
);
4506 auto_vec
<cgraph_edge
*, 2> self_recursive_calls
;
4507 for (i
= callers
.length () - 1; i
>= 0; i
--)
4509 cgraph_edge
*cs
= callers
[i
];
4510 if (cs
->caller
== node
)
4512 self_recursive_calls
.safe_push (cs
);
4513 callers
.unordered_remove (i
);
4517 unsigned &suffix_counter
= clone_num_suffixes
->get_or_insert (
4518 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (
4520 new_node
= node
->create_virtual_clone (callers
, replace_trees
,
4521 new_adjustments
, "constprop",
4525 bool have_self_recursive_calls
= !self_recursive_calls
.is_empty ();
4526 for (unsigned j
= 0; j
< self_recursive_calls
.length (); j
++)
4528 cgraph_edge
*cs
= get_next_cgraph_edge_clone (self_recursive_calls
[j
]);
4529 /* Cloned edges can disappear during cloning as speculation can be
4530 resolved, check that we have one and that it comes from the last
4532 if (cs
&& cs
->caller
== new_node
)
4533 cs
->redirect_callee_duplicating_thunks (new_node
);
4534 /* Any future code that would make more than one clone of an outgoing
4535 edge would confuse this mechanism, so let's check that does not
4537 gcc_checking_assert (!cs
4538 || !get_next_cgraph_edge_clone (cs
)
4539 || get_next_cgraph_edge_clone (cs
)->caller
!= new_node
);
4541 if (have_self_recursive_calls
)
4542 new_node
->expand_all_artificial_thunks ();
4544 ipa_set_node_agg_value_chain (new_node
, aggvals
);
4545 for (av
= aggvals
; av
; av
= av
->next
)
4546 new_node
->maybe_create_reference (av
->value
, NULL
);
4548 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4550 fprintf (dump_file
, " the new node is %s.\n", new_node
->dump_name ());
4551 if (known_contexts
.exists ())
4553 for (i
= 0; i
< count
; i
++)
4554 if (!known_contexts
[i
].useless_p ())
4556 fprintf (dump_file
, " known ctx %i is ", i
);
4557 known_contexts
[i
].dump (dump_file
);
4561 ipa_dump_agg_replacement_values (dump_file
, aggvals
);
4563 ipa_check_create_node_params ();
4564 update_profiling_info (node
, new_node
);
4565 new_info
= IPA_NODE_REF (new_node
);
4566 new_info
->ipcp_orig_node
= node
;
4567 new_node
->ipcp_clone
= true;
4568 new_info
->known_csts
= known_csts
;
4569 new_info
->known_contexts
= known_contexts
;
4571 ipcp_discover_new_direct_edges (new_node
, known_csts
, known_contexts
, aggvals
);
4577 /* Return true, if JFUNC, which describes a i-th parameter of call CS, is a
4578 simple no-operation pass-through function to itself. */
4581 self_recursive_pass_through_p (cgraph_edge
*cs
, ipa_jump_func
*jfunc
, int i
)
4583 enum availability availability
;
4584 if (cs
->caller
== cs
->callee
->function_symbol (&availability
)
4585 && availability
> AVAIL_INTERPOSABLE
4586 && jfunc
->type
== IPA_JF_PASS_THROUGH
4587 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
4588 && ipa_get_jf_pass_through_formal_id (jfunc
) == i
)
4593 /* Return true, if JFUNC, which describes a part of an aggregate represented
4594 or pointed to by the i-th parameter of call CS, is a simple no-operation
4595 pass-through function to itself. */
4598 self_recursive_agg_pass_through_p (cgraph_edge
*cs
, ipa_agg_jf_item
*jfunc
,
4601 enum availability availability
;
4602 if (cs
->caller
== cs
->callee
->function_symbol (&availability
)
4603 && availability
> AVAIL_INTERPOSABLE
4604 && jfunc
->jftype
== IPA_JF_LOAD_AGG
4605 && jfunc
->offset
== jfunc
->value
.load_agg
.offset
4606 && jfunc
->value
.pass_through
.operation
== NOP_EXPR
4607 && jfunc
->value
.pass_through
.formal_id
== i
)
4612 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
4613 KNOWN_CSTS with constants that are also known for all of the CALLERS. */
4616 find_more_scalar_values_for_callers_subset (struct cgraph_node
*node
,
4617 vec
<tree
> known_csts
,
4618 vec
<cgraph_edge
*> callers
)
4620 class ipa_node_params
*info
= IPA_NODE_REF (node
);
4621 int i
, count
= ipa_get_param_count (info
);
4623 for (i
= 0; i
< count
; i
++)
4625 struct cgraph_edge
*cs
;
4626 tree newval
= NULL_TREE
;
4629 tree type
= ipa_get_type (info
, i
);
4631 if (ipa_get_scalar_lat (info
, i
)->bottom
|| known_csts
[i
])
4634 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4636 struct ipa_jump_func
*jump_func
;
4639 if (IPA_NODE_REF (cs
->caller
) && IPA_NODE_REF (cs
->caller
)->node_dead
)
4642 if (!IPA_EDGE_REF (cs
)
4643 || i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
))
4645 && call_passes_through_thunk_p (cs
)))
4650 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
4651 if (self_recursive_pass_through_p (cs
, jump_func
, i
))
4654 t
= ipa_value_from_jfunc (IPA_NODE_REF (cs
->caller
), jump_func
, type
);
4657 && !values_equal_for_ipcp_p (t
, newval
))
4658 || (!first
&& !newval
))
4670 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4672 fprintf (dump_file
, " adding an extra known scalar value ");
4673 print_ipcp_constant_value (dump_file
, newval
);
4674 fprintf (dump_file
, " for ");
4675 ipa_dump_param (dump_file
, info
, i
);
4676 fprintf (dump_file
, "\n");
4679 known_csts
[i
] = newval
;
4684 /* Given a NODE and a subset of its CALLERS, try to populate plank slots in
4685 KNOWN_CONTEXTS with polymorphic contexts that are also known for all of the
4689 find_more_contexts_for_caller_subset (cgraph_node
*node
,
4690 vec
<ipa_polymorphic_call_context
>
4692 vec
<cgraph_edge
*> callers
)
4694 ipa_node_params
*info
= IPA_NODE_REF (node
);
4695 int i
, count
= ipa_get_param_count (info
);
4697 for (i
= 0; i
< count
; i
++)
4701 if (ipa_get_poly_ctx_lat (info
, i
)->bottom
4702 || (known_contexts
->exists ()
4703 && !(*known_contexts
)[i
].useless_p ()))
4706 ipa_polymorphic_call_context newval
;
4710 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4712 if (!IPA_EDGE_REF (cs
)
4713 || i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
)))
4715 ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
),
4717 ipa_polymorphic_call_context ctx
;
4718 ctx
= ipa_context_from_jfunc (IPA_NODE_REF (cs
->caller
), cs
, i
,
4726 newval
.meet_with (ctx
);
4727 if (newval
.useless_p ())
4731 if (!newval
.useless_p ())
4733 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4735 fprintf (dump_file
, " adding an extra known polymorphic "
4737 print_ipcp_constant_value (dump_file
, newval
);
4738 fprintf (dump_file
, " for ");
4739 ipa_dump_param (dump_file
, info
, i
);
4740 fprintf (dump_file
, "\n");
4743 if (!known_contexts
->exists ())
4744 known_contexts
->safe_grow_cleared (ipa_get_param_count (info
));
4745 (*known_contexts
)[i
] = newval
;
4751 /* Go through PLATS and create a vector of values consisting of values and
4752 offsets (minus OFFSET) of lattices that contain only a single value. */
4754 static vec
<ipa_agg_value
>
4755 copy_plats_to_inter (class ipcp_param_lattices
*plats
, HOST_WIDE_INT offset
)
4757 vec
<ipa_agg_value
> res
= vNULL
;
4759 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
4762 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
4763 if (aglat
->is_single_const ())
4765 struct ipa_agg_value ti
;
4766 ti
.offset
= aglat
->offset
- offset
;
4767 ti
.value
= aglat
->values
->value
;
4773 /* Intersect all values in INTER with single value lattices in PLATS (while
4774 subtracting OFFSET). */
4777 intersect_with_plats (class ipcp_param_lattices
*plats
,
4778 vec
<ipa_agg_value
> *inter
,
4779 HOST_WIDE_INT offset
)
4781 struct ipcp_agg_lattice
*aglat
;
4782 struct ipa_agg_value
*item
;
4785 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
4791 aglat
= plats
->aggs
;
4792 FOR_EACH_VEC_ELT (*inter
, k
, item
)
4799 if (aglat
->offset
- offset
> item
->offset
)
4801 if (aglat
->offset
- offset
== item
->offset
)
4803 gcc_checking_assert (item
->value
);
4804 if (aglat
->is_single_const ())
4806 tree value
= aglat
->values
->value
;
4808 if (values_equal_for_ipcp_p (item
->value
, value
))
4810 else if (item
->value
== error_mark_node
)
4812 /* Replace unknown place holder value with real one. */
4813 item
->value
= value
;
4819 aglat
= aglat
->next
;
4822 item
->value
= NULL_TREE
;
4826 /* Copy aggregate replacement values of NODE (which is an IPA-CP clone) to the
4827 vector result while subtracting OFFSET from the individual value offsets. */
4829 static vec
<ipa_agg_value
>
4830 agg_replacements_to_vector (struct cgraph_node
*node
, int index
,
4831 HOST_WIDE_INT offset
)
4833 struct ipa_agg_replacement_value
*av
;
4834 vec
<ipa_agg_value
> res
= vNULL
;
4836 for (av
= ipa_get_agg_replacements_for_node (node
); av
; av
= av
->next
)
4837 if (av
->index
== index
4838 && (av
->offset
- offset
) >= 0)
4840 struct ipa_agg_value item
;
4841 gcc_checking_assert (av
->value
);
4842 item
.offset
= av
->offset
- offset
;
4843 item
.value
= av
->value
;
4844 res
.safe_push (item
);
4850 /* Intersect all values in INTER with those that we have already scheduled to
4851 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
4852 (while subtracting OFFSET). */
4855 intersect_with_agg_replacements (struct cgraph_node
*node
, int index
,
4856 vec
<ipa_agg_value
> *inter
,
4857 HOST_WIDE_INT offset
)
4859 struct ipa_agg_replacement_value
*srcvals
;
4860 struct ipa_agg_value
*item
;
4863 srcvals
= ipa_get_agg_replacements_for_node (node
);
4870 FOR_EACH_VEC_ELT (*inter
, i
, item
)
4872 struct ipa_agg_replacement_value
*av
;
4876 for (av
= srcvals
; av
; av
= av
->next
)
4878 gcc_checking_assert (av
->value
);
4879 if (av
->index
== index
4880 && av
->offset
- offset
== item
->offset
)
4882 if (values_equal_for_ipcp_p (item
->value
, av
->value
))
4884 else if (item
->value
== error_mark_node
)
4886 /* Replace place holder value with real one. */
4887 item
->value
= av
->value
;
4894 item
->value
= NULL_TREE
;
4898 /* Intersect values in INTER with aggregate values that come along edge CS to
4899 parameter number INDEX and return it. If INTER does not actually exist yet,
4900 copy all incoming values to it. If we determine we ended up with no values
4901 whatsoever, return a released vector. */
4903 static vec
<ipa_agg_value
>
4904 intersect_aggregates_with_edge (struct cgraph_edge
*cs
, int index
,
4905 vec
<ipa_agg_value
> inter
)
4907 struct ipa_jump_func
*jfunc
;
4908 jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), index
);
4909 if (jfunc
->type
== IPA_JF_PASS_THROUGH
4910 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
4912 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4913 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
4915 if (caller_info
->ipcp_orig_node
)
4917 struct cgraph_node
*orig_node
= caller_info
->ipcp_orig_node
;
4918 class ipcp_param_lattices
*orig_plats
;
4919 orig_plats
= ipa_get_parm_lattices (IPA_NODE_REF (orig_node
),
4921 if (agg_pass_through_permissible_p (orig_plats
, jfunc
))
4923 if (!inter
.exists ())
4924 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, 0);
4926 intersect_with_agg_replacements (cs
->caller
, src_idx
,
4937 class ipcp_param_lattices
*src_plats
;
4938 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
4939 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
4941 /* Currently we do not produce clobber aggregate jump
4942 functions, adjust when we do. */
4943 gcc_checking_assert (!jfunc
->agg
.items
);
4944 if (!inter
.exists ())
4945 inter
= copy_plats_to_inter (src_plats
, 0);
4947 intersect_with_plats (src_plats
, &inter
, 0);
4956 else if (jfunc
->type
== IPA_JF_ANCESTOR
4957 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
4959 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4960 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
4961 class ipcp_param_lattices
*src_plats
;
4962 HOST_WIDE_INT delta
= ipa_get_jf_ancestor_offset (jfunc
);
4964 if (caller_info
->ipcp_orig_node
)
4966 if (!inter
.exists ())
4967 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, delta
);
4969 intersect_with_agg_replacements (cs
->caller
, src_idx
, &inter
,
4974 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
4975 /* Currently we do not produce clobber aggregate jump
4976 functions, adjust when we do. */
4977 gcc_checking_assert (!src_plats
->aggs
|| !jfunc
->agg
.items
);
4978 if (!inter
.exists ())
4979 inter
= copy_plats_to_inter (src_plats
, delta
);
4981 intersect_with_plats (src_plats
, &inter
, delta
);
4984 else if (jfunc
->agg
.items
)
4986 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4987 struct ipa_agg_value
*item
;
4990 if (!inter
.exists ())
4991 for (unsigned i
= 0; i
< jfunc
->agg
.items
->length (); i
++)
4993 struct ipa_agg_jf_item
*agg_item
= &(*jfunc
->agg
.items
)[i
];
4994 struct ipa_agg_value agg_value
;
4996 if (self_recursive_agg_pass_through_p (cs
, agg_item
, index
))
4998 /* For a self-recursive call, if aggregate jump function is a
4999 simple pass-through, the exact value that it stands for is
5000 not known at this point, which must comes from other call
5001 sites. But we still need to add a place holder in value
5002 sets to indicate it, here we use error_mark_node to
5003 represent the special unknown value, which will be replaced
5004 with real one during later intersecting operations. */
5005 agg_value
.value
= error_mark_node
;
5009 tree value
= ipa_agg_value_from_node (caller_info
, cs
->caller
,
5014 agg_value
.value
= value
;
5017 agg_value
.offset
= agg_item
->offset
;
5018 inter
.safe_push (agg_value
);
5021 FOR_EACH_VEC_ELT (inter
, k
, item
)
5029 while ((unsigned) l
< jfunc
->agg
.items
->length ())
5031 struct ipa_agg_jf_item
*ti
;
5032 ti
= &(*jfunc
->agg
.items
)[l
];
5033 if (ti
->offset
> item
->offset
)
5035 if (ti
->offset
== item
->offset
)
5039 if (self_recursive_agg_pass_through_p (cs
, ti
, index
))
5041 /* A simple aggregate pass-through in self-recursive
5042 call should lead to same value. */
5045 else if ((value
= ipa_agg_value_from_node (caller_info
,
5048 if (values_equal_for_ipcp_p (item
->value
, value
))
5050 else if (item
->value
== error_mark_node
)
5052 /* Replace unknown place holder value with real
5054 item
->value
= value
;
5074 /* Look at edges in CALLERS and collect all known aggregate values that arrive
5075 from all of them. */
5077 static struct ipa_agg_replacement_value
*
5078 find_aggregate_values_for_callers_subset (struct cgraph_node
*node
,
5079 vec
<cgraph_edge
*> callers
)
5081 class ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
5082 struct ipa_agg_replacement_value
*res
;
5083 struct ipa_agg_replacement_value
**tail
= &res
;
5084 struct cgraph_edge
*cs
;
5085 int i
, j
, count
= ipa_get_param_count (dest_info
);
5087 FOR_EACH_VEC_ELT (callers
, j
, cs
)
5089 if (!IPA_EDGE_REF (cs
))
5094 int c
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
5099 for (i
= 0; i
< count
; i
++)
5101 struct cgraph_edge
*cs
;
5102 vec
<ipa_agg_value
> inter
= vNULL
;
5103 struct ipa_agg_value
*item
;
5104 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (dest_info
, i
);
5107 /* Among other things, the following check should deal with all by_ref
5109 if (plats
->aggs_bottom
)
5112 FOR_EACH_VEC_ELT (callers
, j
, cs
)
5114 struct ipa_jump_func
*jfunc
5115 = ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
5116 if (self_recursive_pass_through_p (cs
, jfunc
, i
)
5117 && (!plats
->aggs_by_ref
5118 || ipa_get_jf_pass_through_agg_preserved (jfunc
)))
5120 inter
= intersect_aggregates_with_edge (cs
, i
, inter
);
5122 if (!inter
.exists ())
5126 FOR_EACH_VEC_ELT (inter
, j
, item
)
5128 struct ipa_agg_replacement_value
*v
;
5133 /* All values must be real values, not unknown place holders. */
5134 gcc_assert (item
->value
!= error_mark_node
);
5136 v
= ggc_alloc
<ipa_agg_replacement_value
> ();
5138 v
->offset
= item
->offset
;
5139 v
->value
= item
->value
;
5140 v
->by_ref
= plats
->aggs_by_ref
;
5146 if (inter
.exists ())
5153 /* Determine whether CS also brings all scalar values that the NODE is
5157 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge
*cs
,
5158 struct cgraph_node
*node
)
5160 class ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
5161 int count
= ipa_get_param_count (dest_info
);
5162 class ipa_node_params
*caller_info
;
5163 class ipa_edge_args
*args
;
5166 caller_info
= IPA_NODE_REF (cs
->caller
);
5167 args
= IPA_EDGE_REF (cs
);
5168 for (i
= 0; i
< count
; i
++)
5170 struct ipa_jump_func
*jump_func
;
5173 val
= dest_info
->known_csts
[i
];
5177 if (i
>= ipa_get_cs_argument_count (args
))
5179 jump_func
= ipa_get_ith_jump_func (args
, i
);
5180 t
= ipa_value_from_jfunc (caller_info
, jump_func
,
5181 ipa_get_type (dest_info
, i
));
5182 if (!t
|| !values_equal_for_ipcp_p (val
, t
))
5188 /* Determine whether CS also brings all aggregate values that NODE is
5191 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge
*cs
,
5192 struct cgraph_node
*node
)
5194 class ipa_node_params
*orig_node_info
;
5195 struct ipa_agg_replacement_value
*aggval
;
5198 aggval
= ipa_get_agg_replacements_for_node (node
);
5202 count
= ipa_get_param_count (IPA_NODE_REF (node
));
5203 ec
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
5205 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
5206 if (aggval
->index
>= ec
)
5209 orig_node_info
= IPA_NODE_REF (IPA_NODE_REF (node
)->ipcp_orig_node
);
5211 for (i
= 0; i
< count
; i
++)
5213 class ipcp_param_lattices
*plats
;
5214 bool interesting
= false;
5215 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
5216 if (aggval
->index
== i
)
5224 plats
= ipa_get_parm_lattices (orig_node_info
, aggval
->index
);
5225 if (plats
->aggs_bottom
)
5228 vec
<ipa_agg_value
> values
= intersect_aggregates_with_edge (cs
, i
, vNULL
);
5229 if (!values
.exists ())
5232 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
5233 if (aggval
->index
== i
)
5235 struct ipa_agg_value
*item
;
5238 FOR_EACH_VEC_ELT (values
, j
, item
)
5240 && item
->offset
== av
->offset
5241 && values_equal_for_ipcp_p (item
->value
, av
->value
))
5257 /* Given an original NODE and a VAL for which we have already created a
5258 specialized clone, look whether there are incoming edges that still lead
5259 into the old node but now also bring the requested value and also conform to
5260 all other criteria such that they can be redirected the special node.
5261 This function can therefore redirect the final edge in a SCC. */
5263 template <typename valtype
>
5265 perhaps_add_new_callers (cgraph_node
*node
, ipcp_value
<valtype
> *val
)
5267 ipcp_value_source
<valtype
> *src
;
5268 profile_count redirected_sum
= profile_count::zero ();
5270 for (src
= val
->sources
; src
; src
= src
->next
)
5272 struct cgraph_edge
*cs
= src
->cs
;
5275 if (cgraph_edge_brings_value_p (cs
, src
, node
, val
)
5276 && cgraph_edge_brings_all_scalars_for_node (cs
, val
->spec_node
)
5277 && cgraph_edge_brings_all_agg_vals_for_node (cs
, val
->spec_node
))
5280 fprintf (dump_file
, " - adding an extra caller %s of %s\n",
5281 cs
->caller
->dump_name (),
5282 val
->spec_node
->dump_name ());
5284 cs
->redirect_callee_duplicating_thunks (val
->spec_node
);
5285 val
->spec_node
->expand_all_artificial_thunks ();
5286 if (cs
->count
.ipa ().initialized_p ())
5287 redirected_sum
= redirected_sum
+ cs
->count
.ipa ();
5289 cs
= get_next_cgraph_edge_clone (cs
);
5293 if (redirected_sum
.nonzero_p ())
5294 update_specialized_profile (val
->spec_node
, node
, redirected_sum
);
5297 /* Return true if KNOWN_CONTEXTS contain at least one useful context. */
5300 known_contexts_useful_p (vec
<ipa_polymorphic_call_context
> known_contexts
)
5302 ipa_polymorphic_call_context
*ctx
;
5305 FOR_EACH_VEC_ELT (known_contexts
, i
, ctx
)
5306 if (!ctx
->useless_p ())
5311 /* Return a copy of KNOWN_CSTS if it is not empty, otherwise return vNULL. */
5313 static vec
<ipa_polymorphic_call_context
>
5314 copy_useful_known_contexts (vec
<ipa_polymorphic_call_context
> known_contexts
)
5316 if (known_contexts_useful_p (known_contexts
))
5317 return known_contexts
.copy ();
5322 /* Copy KNOWN_CSTS and modify the copy according to VAL and INDEX. If
5323 non-empty, replace KNOWN_CONTEXTS with its copy too. */
5326 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
5327 vec
<ipa_polymorphic_call_context
> *known_contexts
,
5328 ipcp_value
<tree
> *val
,
5331 *known_csts
= known_csts
->copy ();
5332 *known_contexts
= copy_useful_known_contexts (*known_contexts
);
5333 (*known_csts
)[index
] = val
->value
;
5336 /* Replace KNOWN_CSTS with its copy. Also copy KNOWN_CONTEXTS and modify the
5337 copy according to VAL and INDEX. */
5340 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
5341 vec
<ipa_polymorphic_call_context
> *known_contexts
,
5342 ipcp_value
<ipa_polymorphic_call_context
> *val
,
5345 *known_csts
= known_csts
->copy ();
5346 *known_contexts
= known_contexts
->copy ();
5347 (*known_contexts
)[index
] = val
->value
;
5350 /* Return true if OFFSET indicates this was not an aggregate value or there is
5351 a replacement equivalent to VALUE, INDEX and OFFSET among those in the
5355 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*aggvals
,
5356 int index
, HOST_WIDE_INT offset
, tree value
)
5363 if (aggvals
->index
== index
5364 && aggvals
->offset
== offset
5365 && values_equal_for_ipcp_p (aggvals
->value
, value
))
5367 aggvals
= aggvals
->next
;
5372 /* Return true if offset is minus one because source of a polymorphic context
5373 cannot be an aggregate value. */
5376 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*,
5377 int , HOST_WIDE_INT offset
,
5378 ipa_polymorphic_call_context
)
5380 return offset
== -1;
5383 /* Decide whether to create a special version of NODE for value VAL of parameter
5384 at the given INDEX. If OFFSET is -1, the value is for the parameter itself,
5385 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS,
5386 KNOWN_CONTEXTS and KNOWN_AGGS describe the other already known values. */
5388 template <typename valtype
>
5390 decide_about_value (struct cgraph_node
*node
, int index
, HOST_WIDE_INT offset
,
5391 ipcp_value
<valtype
> *val
, vec
<tree
> known_csts
,
5392 vec
<ipa_polymorphic_call_context
> known_contexts
)
5394 struct ipa_agg_replacement_value
*aggvals
;
5395 int freq_sum
, caller_count
;
5396 profile_count count_sum
;
5397 vec
<cgraph_edge
*> callers
;
5401 perhaps_add_new_callers (node
, val
);
5404 else if (val
->local_size_cost
+ overall_size
> max_new_size
)
5406 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5407 fprintf (dump_file
, " Ignoring candidate value because "
5408 "max_new_size would be reached with %li.\n",
5409 val
->local_size_cost
+ overall_size
);
5412 else if (!get_info_about_necessary_edges (val
, node
, &freq_sum
, &count_sum
,
5416 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5418 fprintf (dump_file
, " - considering value ");
5419 print_ipcp_constant_value (dump_file
, val
->value
);
5420 fprintf (dump_file
, " for ");
5421 ipa_dump_param (dump_file
, IPA_NODE_REF (node
), index
);
5423 fprintf (dump_file
, ", offset: " HOST_WIDE_INT_PRINT_DEC
, offset
);
5424 fprintf (dump_file
, " (caller_count: %i)\n", caller_count
);
5427 if (!good_cloning_opportunity_p (node
, val
->local_time_benefit
,
5428 freq_sum
, count_sum
,
5429 val
->local_size_cost
)
5430 && !good_cloning_opportunity_p (node
,
5431 val
->local_time_benefit
5432 + val
->prop_time_benefit
,
5433 freq_sum
, count_sum
,
5434 val
->local_size_cost
5435 + val
->prop_size_cost
))
5439 fprintf (dump_file
, " Creating a specialized node of %s.\n",
5440 node
->dump_name ());
5442 callers
= gather_edges_for_value (val
, node
, caller_count
);
5444 modify_known_vectors_with_val (&known_csts
, &known_contexts
, val
, index
);
5447 known_csts
= known_csts
.copy ();
5448 known_contexts
= copy_useful_known_contexts (known_contexts
);
5450 find_more_scalar_values_for_callers_subset (node
, known_csts
, callers
);
5451 find_more_contexts_for_caller_subset (node
, &known_contexts
, callers
);
5452 aggvals
= find_aggregate_values_for_callers_subset (node
, callers
);
5453 gcc_checking_assert (ipcp_val_agg_replacement_ok_p (aggvals
, index
,
5454 offset
, val
->value
));
5455 val
->spec_node
= create_specialized_node (node
, known_csts
, known_contexts
,
5457 overall_size
+= val
->local_size_cost
;
5459 /* TODO: If for some lattice there is only one other known value
5460 left, make a special node for it too. */
5465 /* Decide whether and what specialized clones of NODE should be created. */
5468 decide_whether_version_node (struct cgraph_node
*node
)
5470 class ipa_node_params
*info
= IPA_NODE_REF (node
);
5471 int i
, count
= ipa_get_param_count (info
);
5472 vec
<tree
> known_csts
;
5473 vec
<ipa_polymorphic_call_context
> known_contexts
;
5479 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5480 fprintf (dump_file
, "\nEvaluating opportunities for %s.\n",
5481 node
->dump_name ());
5483 gather_context_independent_values (info
, &known_csts
, &known_contexts
,
5486 for (i
= 0; i
< count
;i
++)
5488 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5489 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
5490 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
5495 ipcp_value
<tree
> *val
;
5496 for (val
= lat
->values
; val
; val
= val
->next
)
5497 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
5501 if (!plats
->aggs_bottom
)
5503 struct ipcp_agg_lattice
*aglat
;
5504 ipcp_value
<tree
> *val
;
5505 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
5506 if (!aglat
->bottom
&& aglat
->values
5507 /* If the following is false, the one value is in
5509 && (plats
->aggs_contain_variable
5510 || !aglat
->is_single_const ()))
5511 for (val
= aglat
->values
; val
; val
= val
->next
)
5512 ret
|= decide_about_value (node
, i
, aglat
->offset
, val
,
5513 known_csts
, known_contexts
);
5517 && known_contexts
[i
].useless_p ())
5519 ipcp_value
<ipa_polymorphic_call_context
> *val
;
5520 for (val
= ctxlat
->values
; val
; val
= val
->next
)
5521 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
5525 info
= IPA_NODE_REF (node
);
5528 if (info
->do_clone_for_all_contexts
)
5530 struct cgraph_node
*clone
;
5531 vec
<cgraph_edge
*> callers
;
5534 fprintf (dump_file
, " - Creating a specialized node of %s "
5535 "for all known contexts.\n", node
->dump_name ());
5537 callers
= node
->collect_callers ();
5538 find_more_scalar_values_for_callers_subset (node
, known_csts
, callers
);
5539 find_more_contexts_for_caller_subset (node
, &known_contexts
, callers
);
5540 ipa_agg_replacement_value
*aggvals
5541 = find_aggregate_values_for_callers_subset (node
, callers
);
5543 if (!known_contexts_useful_p (known_contexts
))
5545 known_contexts
.release ();
5546 known_contexts
= vNULL
;
5548 clone
= create_specialized_node (node
, known_csts
, known_contexts
,
5550 info
= IPA_NODE_REF (node
);
5551 info
->do_clone_for_all_contexts
= false;
5552 IPA_NODE_REF (clone
)->is_all_contexts_clone
= true;
5557 known_csts
.release ();
5558 known_contexts
.release ();
5564 /* Transitively mark all callees of NODE within the same SCC as not dead. */
5567 spread_undeadness (struct cgraph_node
*node
)
5569 struct cgraph_edge
*cs
;
5571 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
5572 if (ipa_edge_within_scc (cs
))
5574 struct cgraph_node
*callee
;
5575 class ipa_node_params
*info
;
5577 callee
= cs
->callee
->function_symbol (NULL
);
5578 info
= IPA_NODE_REF (callee
);
5580 if (info
&& info
->node_dead
)
5582 info
->node_dead
= 0;
5583 spread_undeadness (callee
);
5588 /* Return true if NODE has a caller from outside of its SCC that is not
5589 dead. Worker callback for cgraph_for_node_and_aliases. */
5592 has_undead_caller_from_outside_scc_p (struct cgraph_node
*node
,
5593 void *data ATTRIBUTE_UNUSED
)
5595 struct cgraph_edge
*cs
;
5597 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
5598 if (cs
->caller
->thunk
.thunk_p
5599 && cs
->caller
->call_for_symbol_thunks_and_aliases
5600 (has_undead_caller_from_outside_scc_p
, NULL
, true))
5602 else if (!ipa_edge_within_scc (cs
)
5603 && !IPA_NODE_REF (cs
->caller
)->node_dead
)
5609 /* Identify nodes within the same SCC as NODE which are no longer needed
5610 because of new clones and will be removed as unreachable. */
5613 identify_dead_nodes (struct cgraph_node
*node
)
5615 struct cgraph_node
*v
;
5616 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
5619 && !v
->call_for_symbol_thunks_and_aliases
5620 (has_undead_caller_from_outside_scc_p
, NULL
, true))
5621 IPA_NODE_REF (v
)->node_dead
= 1;
5623 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
5624 if (IPA_NODE_REF (v
) && !IPA_NODE_REF (v
)->node_dead
)
5625 spread_undeadness (v
);
5627 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5629 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
5630 if (IPA_NODE_REF (v
) && IPA_NODE_REF (v
)->node_dead
)
5631 fprintf (dump_file
, " Marking node as dead: %s.\n", v
->dump_name ());
5635 /* The decision stage. Iterate over the topological order of call graph nodes
5636 TOPO and make specialized clones if deemed beneficial. */
5639 ipcp_decision_stage (class ipa_topo_info
*topo
)
5644 fprintf (dump_file
, "\nIPA decision stage:\n\n");
5646 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
5648 struct cgraph_node
*node
= topo
->order
[i
];
5649 bool change
= false, iterate
= true;
5653 struct cgraph_node
*v
;
5655 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
5656 if (v
->has_gimple_body_p ()
5657 && ipcp_versionable_function_p (v
))
5658 iterate
|= decide_whether_version_node (v
);
5663 identify_dead_nodes (node
);
5667 /* Look up all the bits information that we have discovered and copy it over
5668 to the transformation summary. */
5671 ipcp_store_bits_results (void)
5675 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5677 ipa_node_params
*info
= IPA_NODE_REF (node
);
5678 bool dumped_sth
= false;
5679 bool found_useful_result
= false;
5681 if (!opt_for_fn (node
->decl
, flag_ipa_bit_cp
) || !info
)
5684 fprintf (dump_file
, "Not considering %s for ipa bitwise propagation "
5685 "; -fipa-bit-cp: disabled.\n",
5686 node
->dump_name ());
5690 if (info
->ipcp_orig_node
)
5691 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
5692 if (!info
->lattices
)
5693 /* Newly expanded artificial thunks do not have lattices. */
5696 unsigned count
= ipa_get_param_count (info
);
5697 for (unsigned i
= 0; i
< count
; i
++)
5699 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5700 if (plats
->bits_lattice
.constant_p ())
5702 found_useful_result
= true;
5707 if (!found_useful_result
)
5710 ipcp_transformation_initialize ();
5711 ipcp_transformation
*ts
= ipcp_transformation_sum
->get_create (node
);
5712 vec_safe_reserve_exact (ts
->bits
, count
);
5714 for (unsigned i
= 0; i
< count
; i
++)
5716 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5719 if (plats
->bits_lattice
.constant_p ())
5721 = ipa_get_ipa_bits_for_value (plats
->bits_lattice
.get_value (),
5722 plats
->bits_lattice
.get_mask ());
5726 ts
->bits
->quick_push (jfbits
);
5727 if (!dump_file
|| !jfbits
)
5731 fprintf (dump_file
, "Propagated bits info for function %s:\n",
5732 node
->dump_name ());
5735 fprintf (dump_file
, " param %i: value = ", i
);
5736 print_hex (jfbits
->value
, dump_file
);
5737 fprintf (dump_file
, ", mask = ");
5738 print_hex (jfbits
->mask
, dump_file
);
5739 fprintf (dump_file
, "\n");
5744 /* Look up all VR information that we have discovered and copy it over
5745 to the transformation summary. */
5748 ipcp_store_vr_results (void)
5752 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5754 ipa_node_params
*info
= IPA_NODE_REF (node
);
5755 bool found_useful_result
= false;
5757 if (!info
|| !opt_for_fn (node
->decl
, flag_ipa_vrp
))
5760 fprintf (dump_file
, "Not considering %s for VR discovery "
5761 "and propagate; -fipa-ipa-vrp: disabled.\n",
5762 node
->dump_name ());
5766 if (info
->ipcp_orig_node
)
5767 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
5768 if (!info
->lattices
)
5769 /* Newly expanded artificial thunks do not have lattices. */
5772 unsigned count
= ipa_get_param_count (info
);
5773 for (unsigned i
= 0; i
< count
; i
++)
5775 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5776 if (!plats
->m_value_range
.bottom_p ()
5777 && !plats
->m_value_range
.top_p ())
5779 found_useful_result
= true;
5783 if (!found_useful_result
)
5786 ipcp_transformation_initialize ();
5787 ipcp_transformation
*ts
= ipcp_transformation_sum
->get_create (node
);
5788 vec_safe_reserve_exact (ts
->m_vr
, count
);
5790 for (unsigned i
= 0; i
< count
; i
++)
5792 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5795 if (!plats
->m_value_range
.bottom_p ()
5796 && !plats
->m_value_range
.top_p ())
5799 vr
.type
= plats
->m_value_range
.m_vr
.kind ();
5800 vr
.min
= wi::to_wide (plats
->m_value_range
.m_vr
.min ());
5801 vr
.max
= wi::to_wide (plats
->m_value_range
.m_vr
.max ());
5806 vr
.type
= VR_VARYING
;
5807 vr
.min
= vr
.max
= wi::zero (INT_TYPE_SIZE
);
5809 ts
->m_vr
->quick_push (vr
);
5814 /* The IPCP driver. */
5819 class ipa_topo_info topo
;
5821 if (edge_clone_summaries
== NULL
)
5822 edge_clone_summaries
= new edge_clone_summary_t (symtab
);
5824 ipa_check_create_node_params ();
5825 ipa_check_create_edge_args ();
5826 clone_num_suffixes
= new hash_map
<const char *, unsigned>;
5830 fprintf (dump_file
, "\nIPA structures before propagation:\n");
5831 if (dump_flags
& TDF_DETAILS
)
5832 ipa_print_all_params (dump_file
);
5833 ipa_print_all_jump_functions (dump_file
);
5836 /* Topological sort. */
5837 build_toporder_info (&topo
);
5838 /* Do the interprocedural propagation. */
5839 ipcp_propagate_stage (&topo
);
5840 /* Decide what constant propagation and cloning should be performed. */
5841 ipcp_decision_stage (&topo
);
5842 /* Store results of bits propagation. */
5843 ipcp_store_bits_results ();
5844 /* Store results of value range propagation. */
5845 ipcp_store_vr_results ();
5847 /* Free all IPCP structures. */
5848 delete clone_num_suffixes
;
5849 free_toporder_info (&topo
);
5850 delete edge_clone_summaries
;
5851 edge_clone_summaries
= NULL
;
5852 ipa_free_all_structures_after_ipa_cp ();
5854 fprintf (dump_file
, "\nIPA constant propagation end\n");
5858 /* Initialization and computation of IPCP data structures. This is the initial
5859 intraprocedural analysis of functions, which gathers information to be
5860 propagated later on. */
5863 ipcp_generate_summary (void)
5865 struct cgraph_node
*node
;
5868 fprintf (dump_file
, "\nIPA constant propagation start:\n");
5869 ipa_register_cgraph_hooks ();
5871 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5872 ipa_analyze_node (node
);
5875 /* Write ipcp summary for nodes in SET. */
5878 ipcp_write_summary (void)
5880 ipa_prop_write_jump_functions ();
5883 /* Read ipcp summary. */
5886 ipcp_read_summary (void)
5888 ipa_prop_read_jump_functions ();
5893 const pass_data pass_data_ipa_cp
=
5895 IPA_PASS
, /* type */
5897 OPTGROUP_NONE
, /* optinfo_flags */
5898 TV_IPA_CONSTANT_PROP
, /* tv_id */
5899 0, /* properties_required */
5900 0, /* properties_provided */
5901 0, /* properties_destroyed */
5902 0, /* todo_flags_start */
5903 ( TODO_dump_symtab
| TODO_remove_functions
), /* todo_flags_finish */
5906 class pass_ipa_cp
: public ipa_opt_pass_d
5909 pass_ipa_cp (gcc::context
*ctxt
)
5910 : ipa_opt_pass_d (pass_data_ipa_cp
, ctxt
,
5911 ipcp_generate_summary
, /* generate_summary */
5912 ipcp_write_summary
, /* write_summary */
5913 ipcp_read_summary
, /* read_summary */
5914 ipcp_write_transformation_summaries
, /*
5915 write_optimization_summary */
5916 ipcp_read_transformation_summaries
, /*
5917 read_optimization_summary */
5918 NULL
, /* stmt_fixup */
5919 0, /* function_transform_todo_flags_start */
5920 ipcp_transform_function
, /* function_transform */
5921 NULL
) /* variable_transform */
5924 /* opt_pass methods: */
5925 virtual bool gate (function
*)
5927 /* FIXME: We should remove the optimize check after we ensure we never run
5928 IPA passes when not optimizing. */
5929 return (flag_ipa_cp
&& optimize
) || in_lto_p
;
5932 virtual unsigned int execute (function
*) { return ipcp_driver (); }
5934 }; // class pass_ipa_cp
5939 make_pass_ipa_cp (gcc::context
*ctxt
)
5941 return new pass_ipa_cp (ctxt
);
5944 /* Reset all state within ipa-cp.c so that we can rerun the compiler
5945 within the same process. For use by toplev::finalize. */
5948 ipa_cp_c_finalize (void)
5950 max_count
= profile_count::uninitialized ();
5953 ipcp_free_transformation_sum ();