1 /* Interprocedural constant propagation
2 Copyright (C) 2005-2020 Free Software Foundation, Inc.
4 Contributed by Razya Ladelsky <RAZYA@il.ibm.com> and Martin Jambor
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
23 /* Interprocedural constant propagation (IPA-CP).
25 The goal of this transformation is to
27 1) discover functions which are always invoked with some arguments with the
28 same known constant values and modify the functions so that the
29 subsequent optimizations can take advantage of the knowledge, and
31 2) partial specialization - create specialized versions of functions
32 transformed in this way if some parameters are known constants only in
33 certain contexts but the estimated tradeoff between speedup and cost size
36 The algorithm also propagates types and attempts to perform type based
37 devirtualization. Types are propagated much like constants.
39 The algorithm basically consists of three stages. In the first, functions
40 are analyzed one at a time and jump functions are constructed for all known
41 call-sites. In the second phase, the pass propagates information from the
42 jump functions across the call to reveal what values are available at what
43 call sites, performs estimations of effects of known values on functions and
44 their callees, and finally decides what specialized extra versions should be
45 created. In the third, the special versions materialize and appropriate
48 The algorithm used is to a certain extent based on "Interprocedural Constant
49 Propagation", by David Callahan, Keith D Cooper, Ken Kennedy, Linda Torczon,
50 Comp86, pg 152-161 and "A Methodology for Procedure Cloning" by Keith D
51 Cooper, Mary W. Hall, and Ken Kennedy.
54 First stage - intraprocedural analysis
55 =======================================
57 This phase computes jump_function and modification flags.
59 A jump function for a call-site represents the values passed as an actual
60 arguments of a given call-site. In principle, there are three types of
63 Pass through - the caller's formal parameter is passed as an actual
64 argument, plus an operation on it can be performed.
65 Constant - a constant is passed as an actual argument.
66 Unknown - neither of the above.
68 All jump function types are described in detail in ipa-prop.h, together with
69 the data structures that represent them and methods of accessing them.
71 ipcp_generate_summary() is the main function of the first stage.
73 Second stage - interprocedural analysis
74 ========================================
76 This stage is itself divided into two phases. In the first, we propagate
77 known values over the call graph, in the second, we make cloning decisions.
78 It uses a different algorithm than the original Callahan's paper.
80 First, we traverse the functions topologically from callers to callees and,
81 for each strongly connected component (SCC), we propagate constants
82 according to previously computed jump functions. We also record what known
83 values depend on other known values and estimate local effects. Finally, we
84 propagate cumulative information about these effects from dependent values
85 to those on which they depend.
87 Second, we again traverse the call graph in the same topological order and
88 make clones for functions which we know are called with the same values in
89 all contexts and decide about extra specialized clones of functions just for
90 some contexts - these decisions are based on both local estimates and
91 cumulative estimates propagated from callees.
93 ipcp_propagate_stage() and ipcp_decision_stage() together constitute the
96 Third phase - materialization of clones, call statement updates.
97 ============================================
99 This stage is currently performed by call graph code (mainly in cgraphunit.c
100 and tree-inline.c) according to instructions inserted to the call graph by
105 #include "coretypes.h"
108 #include "gimple-expr.h"
110 #include "alloc-pool.h"
111 #include "tree-pass.h"
113 #include "diagnostic.h"
114 #include "fold-const.h"
115 #include "gimple-fold.h"
116 #include "symbol-summary.h"
117 #include "tree-vrp.h"
118 #include "ipa-prop.h"
119 #include "tree-pretty-print.h"
120 #include "tree-inline.h"
121 #include "ipa-fnsummary.h"
122 #include "ipa-utils.h"
123 #include "tree-ssa-ccp.h"
124 #include "stringpool.h"
127 template <typename valtype
> class ipcp_value
;
129 /* Describes a particular source for an IPA-CP value. */
131 template <typename valtype
>
132 struct ipcp_value_source
135 /* Aggregate offset of the source, negative if the source is scalar value of
136 the argument itself. */
137 HOST_WIDE_INT offset
;
138 /* The incoming edge that brought the value. */
140 /* If the jump function that resulted into his value was a pass-through or an
141 ancestor, this is the ipcp_value of the caller from which the described
142 value has been derived. Otherwise it is NULL. */
143 ipcp_value
<valtype
> *val
;
144 /* Next pointer in a linked list of sources of a value. */
145 ipcp_value_source
*next
;
146 /* If the jump function that resulted into his value was a pass-through or an
147 ancestor, this is the index of the parameter of the caller the jump
148 function references. */
152 /* Common ancestor for all ipcp_value instantiations. */
154 class ipcp_value_base
157 /* Time benefit and size cost that specializing the function for this value
158 would bring about in this function alone. */
159 int local_time_benefit
, local_size_cost
;
160 /* Time benefit and size cost that specializing the function for this value
161 can bring about in it's callees (transitively). */
162 int prop_time_benefit
, prop_size_cost
;
165 : local_time_benefit (0), local_size_cost (0),
166 prop_time_benefit (0), prop_size_cost (0) {}
169 /* Describes one particular value stored in struct ipcp_lattice. */
171 template <typename valtype
>
172 class ipcp_value
: public ipcp_value_base
175 /* The actual value for the given parameter. */
177 /* The list of sources from which this value originates. */
178 ipcp_value_source
<valtype
> *sources
;
179 /* Next pointers in a linked list of all values in a lattice. */
181 /* Next pointers in a linked list of values in a strongly connected component
183 ipcp_value
*scc_next
;
184 /* Next pointers in a linked list of SCCs of values sorted topologically
185 according their sources. */
186 ipcp_value
*topo_next
;
187 /* A specialized node created for this value, NULL if none has been (so far)
189 cgraph_node
*spec_node
;
190 /* Depth first search number and low link for topological sorting of
193 /* True if this value is currently on the topo-sort stack. */
197 : sources (0), next (0), scc_next (0), topo_next (0),
198 spec_node (0), dfs (0), low_link (0), on_stack (false) {}
200 void add_source (cgraph_edge
*cs
, ipcp_value
*src_val
, int src_idx
,
201 HOST_WIDE_INT offset
);
204 /* Lattice describing potential values of a formal parameter of a function, or
205 a part of an aggregate. TOP is represented by a lattice with zero values
206 and with contains_variable and bottom flags cleared. BOTTOM is represented
207 by a lattice with the bottom flag set. In that case, values and
208 contains_variable flag should be disregarded. */
210 template <typename valtype
>
214 /* The list of known values and types in this lattice. Note that values are
215 not deallocated if a lattice is set to bottom because there may be value
216 sources referencing them. */
217 ipcp_value
<valtype
> *values
;
218 /* Number of known values and types in this lattice. */
220 /* The lattice contains a variable component (in addition to values). */
221 bool contains_variable
;
222 /* The value of the lattice is bottom (i.e. variable and unusable for any
226 inline bool is_single_const ();
227 inline bool set_to_bottom ();
228 inline bool set_contains_variable ();
229 bool add_value (valtype newval
, cgraph_edge
*cs
,
230 ipcp_value
<valtype
> *src_val
= NULL
,
231 int src_idx
= 0, HOST_WIDE_INT offset
= -1,
232 ipcp_value
<valtype
> **val_p
= NULL
,
233 bool unlimited
= false);
234 void print (FILE * f
, bool dump_sources
, bool dump_benefits
);
237 /* Lattice of tree values with an offset to describe a part of an
240 struct ipcp_agg_lattice
: public ipcp_lattice
<tree
>
243 /* Offset that is being described by this lattice. */
244 HOST_WIDE_INT offset
;
245 /* Size so that we don't have to re-compute it every time we traverse the
246 list. Must correspond to TYPE_SIZE of all lat values. */
248 /* Next element of the linked list. */
249 struct ipcp_agg_lattice
*next
;
252 /* Lattice of known bits, only capable of holding one value.
253 Bitwise constant propagation propagates which bits of a
269 In the above case, the param 'x' will always have all
270 the bits (except the bits in lsb) set to 0.
271 Hence the mask of 'x' would be 0xff. The mask
272 reflects that the bits in lsb are unknown.
273 The actual propagated value is given by m_value & ~m_mask. */
275 class ipcp_bits_lattice
278 bool bottom_p () { return m_lattice_val
== IPA_BITS_VARYING
; }
279 bool top_p () { return m_lattice_val
== IPA_BITS_UNDEFINED
; }
280 bool constant_p () { return m_lattice_val
== IPA_BITS_CONSTANT
; }
281 bool set_to_bottom ();
282 bool set_to_constant (widest_int
, widest_int
);
284 widest_int
get_value () { return m_value
; }
285 widest_int
get_mask () { return m_mask
; }
287 bool meet_with (ipcp_bits_lattice
& other
, unsigned, signop
,
288 enum tree_code
, tree
);
290 bool meet_with (widest_int
, widest_int
, unsigned);
295 enum { IPA_BITS_UNDEFINED
, IPA_BITS_CONSTANT
, IPA_BITS_VARYING
} m_lattice_val
;
297 /* Similar to ccp_lattice_t, mask represents which bits of value are constant.
298 If a bit in mask is set to 0, then the corresponding bit in
299 value is known to be constant. */
300 widest_int m_value
, m_mask
;
302 bool meet_with_1 (widest_int
, widest_int
, unsigned);
303 void get_value_and_mask (tree
, widest_int
*, widest_int
*);
306 /* Lattice of value ranges. */
308 class ipcp_vr_lattice
313 inline bool bottom_p () const;
314 inline bool top_p () const;
315 inline bool set_to_bottom ();
316 bool meet_with (const value_range
*p_vr
);
317 bool meet_with (const ipcp_vr_lattice
&other
);
318 void init () { gcc_assert (m_vr
.undefined_p ()); }
319 void print (FILE * f
);
322 bool meet_with_1 (const value_range
*other_vr
);
325 /* Structure containing lattices for a parameter itself and for pieces of
326 aggregates that are passed in the parameter or by a reference in a parameter
327 plus some other useful flags. */
329 class ipcp_param_lattices
332 /* Lattice describing the value of the parameter itself. */
333 ipcp_lattice
<tree
> itself
;
334 /* Lattice describing the polymorphic contexts of a parameter. */
335 ipcp_lattice
<ipa_polymorphic_call_context
> ctxlat
;
336 /* Lattices describing aggregate parts. */
337 ipcp_agg_lattice
*aggs
;
338 /* Lattice describing known bits. */
339 ipcp_bits_lattice bits_lattice
;
340 /* Lattice describing value range. */
341 ipcp_vr_lattice m_value_range
;
342 /* Number of aggregate lattices */
344 /* True if aggregate data were passed by reference (as opposed to by
347 /* All aggregate lattices contain a variable component (in addition to
349 bool aggs_contain_variable
;
350 /* The value of all aggregate lattices is bottom (i.e. variable and unusable
351 for any propagation). */
354 /* There is a virtual call based on this parameter. */
358 /* Allocation pools for values and their sources in ipa-cp. */
360 object_allocator
<ipcp_value
<tree
> > ipcp_cst_values_pool
361 ("IPA-CP constant values");
363 object_allocator
<ipcp_value
<ipa_polymorphic_call_context
> >
364 ipcp_poly_ctx_values_pool ("IPA-CP polymorphic contexts");
366 object_allocator
<ipcp_value_source
<tree
> > ipcp_sources_pool
367 ("IPA-CP value sources");
369 object_allocator
<ipcp_agg_lattice
> ipcp_agg_lattice_pool
370 ("IPA_CP aggregate lattices");
372 /* Maximal count found in program. */
374 static profile_count max_count
;
376 /* Original overall size of the program. */
378 static long overall_size
, orig_overall_size
;
380 /* Node name to unique clone suffix number map. */
381 static hash_map
<const char *, unsigned> *clone_num_suffixes
;
383 /* Return the param lattices structure corresponding to the Ith formal
384 parameter of the function described by INFO. */
385 static inline class ipcp_param_lattices
*
386 ipa_get_parm_lattices (class ipa_node_params
*info
, int i
)
388 gcc_assert (i
>= 0 && i
< ipa_get_param_count (info
));
389 gcc_checking_assert (!info
->ipcp_orig_node
);
390 gcc_checking_assert (info
->lattices
);
391 return &(info
->lattices
[i
]);
394 /* Return the lattice corresponding to the scalar value of the Ith formal
395 parameter of the function described by INFO. */
396 static inline ipcp_lattice
<tree
> *
397 ipa_get_scalar_lat (class ipa_node_params
*info
, int i
)
399 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
400 return &plats
->itself
;
403 /* Return the lattice corresponding to the scalar value of the Ith formal
404 parameter of the function described by INFO. */
405 static inline ipcp_lattice
<ipa_polymorphic_call_context
> *
406 ipa_get_poly_ctx_lat (class ipa_node_params
*info
, int i
)
408 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
409 return &plats
->ctxlat
;
412 /* Return whether LAT is a lattice with a single constant and without an
415 template <typename valtype
>
417 ipcp_lattice
<valtype
>::is_single_const ()
419 if (bottom
|| contains_variable
|| values_count
!= 1)
425 /* Print V which is extracted from a value in a lattice to F. */
428 print_ipcp_constant_value (FILE * f
, tree v
)
430 if (TREE_CODE (v
) == ADDR_EXPR
431 && TREE_CODE (TREE_OPERAND (v
, 0)) == CONST_DECL
)
434 print_generic_expr (f
, DECL_INITIAL (TREE_OPERAND (v
, 0)));
437 print_generic_expr (f
, v
);
440 /* Print V which is extracted from a value in a lattice to F. */
443 print_ipcp_constant_value (FILE * f
, ipa_polymorphic_call_context v
)
448 /* Print a lattice LAT to F. */
450 template <typename valtype
>
452 ipcp_lattice
<valtype
>::print (FILE * f
, bool dump_sources
, bool dump_benefits
)
454 ipcp_value
<valtype
> *val
;
459 fprintf (f
, "BOTTOM\n");
463 if (!values_count
&& !contains_variable
)
465 fprintf (f
, "TOP\n");
469 if (contains_variable
)
471 fprintf (f
, "VARIABLE");
477 for (val
= values
; val
; val
= val
->next
)
479 if (dump_benefits
&& prev
)
481 else if (!dump_benefits
&& prev
)
486 print_ipcp_constant_value (f
, val
->value
);
490 ipcp_value_source
<valtype
> *s
;
492 fprintf (f
, " [from:");
493 for (s
= val
->sources
; s
; s
= s
->next
)
494 fprintf (f
, " %i(%f)", s
->cs
->caller
->order
,
495 s
->cs
->sreal_frequency ().to_double ());
500 fprintf (f
, " [loc_time: %i, loc_size: %i, "
501 "prop_time: %i, prop_size: %i]\n",
502 val
->local_time_benefit
, val
->local_size_cost
,
503 val
->prop_time_benefit
, val
->prop_size_cost
);
510 ipcp_bits_lattice::print (FILE *f
)
513 fprintf (f
, " Bits unknown (TOP)\n");
514 else if (bottom_p ())
515 fprintf (f
, " Bits unusable (BOTTOM)\n");
518 fprintf (f
, " Bits: value = "); print_hex (get_value (), f
);
519 fprintf (f
, ", mask = "); print_hex (get_mask (), f
);
524 /* Print value range lattice to F. */
527 ipcp_vr_lattice::print (FILE * f
)
529 dump_value_range (f
, &m_vr
);
532 /* Print all ipcp_lattices of all functions to F. */
535 print_all_lattices (FILE * f
, bool dump_sources
, bool dump_benefits
)
537 struct cgraph_node
*node
;
540 fprintf (f
, "\nLattices:\n");
541 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
543 class ipa_node_params
*info
;
545 info
= IPA_NODE_REF (node
);
546 /* Skip unoptimized functions and constprop clones since we don't make
547 lattices for them. */
548 if (!info
|| info
->ipcp_orig_node
)
550 fprintf (f
, " Node: %s:\n", node
->dump_name ());
551 count
= ipa_get_param_count (info
);
552 for (i
= 0; i
< count
; i
++)
554 struct ipcp_agg_lattice
*aglat
;
555 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
556 fprintf (f
, " param [%d]: ", i
);
557 plats
->itself
.print (f
, dump_sources
, dump_benefits
);
558 fprintf (f
, " ctxs: ");
559 plats
->ctxlat
.print (f
, dump_sources
, dump_benefits
);
560 plats
->bits_lattice
.print (f
);
562 plats
->m_value_range
.print (f
);
564 if (plats
->virt_call
)
565 fprintf (f
, " virt_call flag set\n");
567 if (plats
->aggs_bottom
)
569 fprintf (f
, " AGGS BOTTOM\n");
572 if (plats
->aggs_contain_variable
)
573 fprintf (f
, " AGGS VARIABLE\n");
574 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
576 fprintf (f
, " %soffset " HOST_WIDE_INT_PRINT_DEC
": ",
577 plats
->aggs_by_ref
? "ref " : "", aglat
->offset
);
578 aglat
->print (f
, dump_sources
, dump_benefits
);
584 /* Determine whether it is at all technically possible to create clones of NODE
585 and store this information in the ipa_node_params structure associated
589 determine_versionability (struct cgraph_node
*node
,
590 class ipa_node_params
*info
)
592 const char *reason
= NULL
;
594 /* There are a number of generic reasons functions cannot be versioned. We
595 also cannot remove parameters if there are type attributes such as fnspec
597 if (node
->alias
|| node
->thunk
.thunk_p
)
598 reason
= "alias or thunk";
599 else if (!node
->versionable
)
600 reason
= "not a tree_versionable_function";
601 else if (node
->get_availability () <= AVAIL_INTERPOSABLE
)
602 reason
= "insufficient body availability";
603 else if (!opt_for_fn (node
->decl
, optimize
)
604 || !opt_for_fn (node
->decl
, flag_ipa_cp
))
605 reason
= "non-optimized function";
606 else if (lookup_attribute ("omp declare simd", DECL_ATTRIBUTES (node
->decl
)))
608 /* Ideally we should clone the SIMD clones themselves and create
609 vector copies of them, so IPA-cp and SIMD clones can happily
610 coexist, but that may not be worth the effort. */
611 reason
= "function has SIMD clones";
613 else if (lookup_attribute ("target_clones", DECL_ATTRIBUTES (node
->decl
)))
615 /* Ideally we should clone the target clones themselves and create
616 copies of them, so IPA-cp and target clones can happily
617 coexist, but that may not be worth the effort. */
618 reason
= "function target_clones attribute";
620 /* Don't clone decls local to a comdat group; it breaks and for C++
621 decloned constructors, inlining is always better anyway. */
622 else if (node
->comdat_local_p ())
623 reason
= "comdat-local function";
624 else if (node
->calls_comdat_local
)
626 /* TODO: call is versionable if we make sure that all
627 callers are inside of a comdat group. */
628 reason
= "calls comdat-local function";
631 /* Functions calling BUILT_IN_VA_ARG_PACK and BUILT_IN_VA_ARG_PACK_LEN
632 work only when inlined. Cloning them may still lead to better code
633 because ipa-cp will not give up on cloning further. If the function is
634 external this however leads to wrong code because we may end up producing
635 offline copy of the function. */
636 if (DECL_EXTERNAL (node
->decl
))
637 for (cgraph_edge
*edge
= node
->callees
; !reason
&& edge
;
638 edge
= edge
->next_callee
)
639 if (fndecl_built_in_p (edge
->callee
->decl
, BUILT_IN_NORMAL
))
641 if (DECL_FUNCTION_CODE (edge
->callee
->decl
) == BUILT_IN_VA_ARG_PACK
)
642 reason
= "external function which calls va_arg_pack";
643 if (DECL_FUNCTION_CODE (edge
->callee
->decl
)
644 == BUILT_IN_VA_ARG_PACK_LEN
)
645 reason
= "external function which calls va_arg_pack_len";
648 if (reason
&& dump_file
&& !node
->alias
&& !node
->thunk
.thunk_p
)
649 fprintf (dump_file
, "Function %s is not versionable, reason: %s.\n",
650 node
->dump_name (), reason
);
652 info
->versionable
= (reason
== NULL
);
655 /* Return true if it is at all technically possible to create clones of a
659 ipcp_versionable_function_p (struct cgraph_node
*node
)
661 return IPA_NODE_REF (node
) && IPA_NODE_REF (node
)->versionable
;
664 /* Structure holding accumulated information about callers of a node. */
666 struct caller_statistics
668 profile_count count_sum
;
669 int n_calls
, n_hot_calls
, freq_sum
;
672 /* Initialize fields of STAT to zeroes. */
675 init_caller_stats (struct caller_statistics
*stats
)
677 stats
->count_sum
= profile_count::zero ();
679 stats
->n_hot_calls
= 0;
683 /* Worker callback of cgraph_for_node_and_aliases accumulating statistics of
684 non-thunk incoming edges to NODE. */
687 gather_caller_stats (struct cgraph_node
*node
, void *data
)
689 struct caller_statistics
*stats
= (struct caller_statistics
*) data
;
690 struct cgraph_edge
*cs
;
692 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
693 if (!cs
->caller
->thunk
.thunk_p
)
695 if (cs
->count
.ipa ().initialized_p ())
696 stats
->count_sum
+= cs
->count
.ipa ();
697 stats
->freq_sum
+= cs
->frequency ();
699 if (cs
->maybe_hot_p ())
700 stats
->n_hot_calls
++;
706 /* Return true if this NODE is viable candidate for cloning. */
709 ipcp_cloning_candidate_p (struct cgraph_node
*node
)
711 struct caller_statistics stats
;
713 gcc_checking_assert (node
->has_gimple_body_p ());
715 if (!opt_for_fn (node
->decl
, flag_ipa_cp_clone
))
718 fprintf (dump_file
, "Not considering %s for cloning; "
719 "-fipa-cp-clone disabled.\n",
724 if (node
->optimize_for_size_p ())
727 fprintf (dump_file
, "Not considering %s for cloning; "
728 "optimizing it for size.\n",
733 init_caller_stats (&stats
);
734 node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
, false);
736 if (ipa_size_summaries
->get (node
)->self_size
< stats
.n_calls
)
739 fprintf (dump_file
, "Considering %s for cloning; code might shrink.\n",
744 /* When profile is available and function is hot, propagate into it even if
745 calls seems cold; constant propagation can improve function's speed
747 if (max_count
> profile_count::zero ())
749 if (stats
.count_sum
> node
->count
.ipa ().apply_scale (90, 100))
752 fprintf (dump_file
, "Considering %s for cloning; "
753 "usually called directly.\n",
758 if (!stats
.n_hot_calls
)
761 fprintf (dump_file
, "Not considering %s for cloning; no hot calls.\n",
766 fprintf (dump_file
, "Considering %s for cloning.\n",
771 template <typename valtype
>
772 class value_topo_info
775 /* Head of the linked list of topologically sorted values. */
776 ipcp_value
<valtype
> *values_topo
;
777 /* Stack for creating SCCs, represented by a linked list too. */
778 ipcp_value
<valtype
> *stack
;
779 /* Counter driving the algorithm in add_val_to_toposort. */
782 value_topo_info () : values_topo (NULL
), stack (NULL
), dfs_counter (0)
784 void add_val (ipcp_value
<valtype
> *cur_val
);
785 void propagate_effects ();
788 /* Arrays representing a topological ordering of call graph nodes and a stack
789 of nodes used during constant propagation and also data required to perform
790 topological sort of values and propagation of benefits in the determined
796 /* Array with obtained topological order of cgraph nodes. */
797 struct cgraph_node
**order
;
798 /* Stack of cgraph nodes used during propagation within SCC until all values
799 in the SCC stabilize. */
800 struct cgraph_node
**stack
;
801 int nnodes
, stack_top
;
803 value_topo_info
<tree
> constants
;
804 value_topo_info
<ipa_polymorphic_call_context
> contexts
;
806 ipa_topo_info () : order(NULL
), stack(NULL
), nnodes(0), stack_top(0),
811 /* Skip edges from and to nodes without ipa_cp enabled.
812 Ignore not available symbols. */
815 ignore_edge_p (cgraph_edge
*e
)
817 enum availability avail
;
818 cgraph_node
*ultimate_target
819 = e
->callee
->function_or_virtual_thunk_symbol (&avail
, e
->caller
);
821 return (avail
<= AVAIL_INTERPOSABLE
822 || !opt_for_fn (ultimate_target
->decl
, optimize
)
823 || !opt_for_fn (ultimate_target
->decl
, flag_ipa_cp
));
826 /* Allocate the arrays in TOPO and topologically sort the nodes into order. */
829 build_toporder_info (class ipa_topo_info
*topo
)
831 topo
->order
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
832 topo
->stack
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
834 gcc_checking_assert (topo
->stack_top
== 0);
835 topo
->nnodes
= ipa_reduced_postorder (topo
->order
, true,
839 /* Free information about strongly connected components and the arrays in
843 free_toporder_info (class ipa_topo_info
*topo
)
845 ipa_free_postorder_info ();
850 /* Add NODE to the stack in TOPO, unless it is already there. */
853 push_node_to_stack (class ipa_topo_info
*topo
, struct cgraph_node
*node
)
855 class ipa_node_params
*info
= IPA_NODE_REF (node
);
856 if (info
->node_enqueued
)
858 info
->node_enqueued
= 1;
859 topo
->stack
[topo
->stack_top
++] = node
;
862 /* Pop a node from the stack in TOPO and return it or return NULL if the stack
865 static struct cgraph_node
*
866 pop_node_from_stack (class ipa_topo_info
*topo
)
870 struct cgraph_node
*node
;
872 node
= topo
->stack
[topo
->stack_top
];
873 IPA_NODE_REF (node
)->node_enqueued
= 0;
880 /* Set lattice LAT to bottom and return true if it previously was not set as
883 template <typename valtype
>
885 ipcp_lattice
<valtype
>::set_to_bottom ()
892 /* Mark lattice as containing an unknown value and return true if it previously
893 was not marked as such. */
895 template <typename valtype
>
897 ipcp_lattice
<valtype
>::set_contains_variable ()
899 bool ret
= !contains_variable
;
900 contains_variable
= true;
904 /* Set all aggregate lattices in PLATS to bottom and return true if they were
905 not previously set as such. */
908 set_agg_lats_to_bottom (class ipcp_param_lattices
*plats
)
910 bool ret
= !plats
->aggs_bottom
;
911 plats
->aggs_bottom
= true;
915 /* Mark all aggregate lattices in PLATS as containing an unknown value and
916 return true if they were not previously marked as such. */
919 set_agg_lats_contain_variable (class ipcp_param_lattices
*plats
)
921 bool ret
= !plats
->aggs_contain_variable
;
922 plats
->aggs_contain_variable
= true;
927 ipcp_vr_lattice::meet_with (const ipcp_vr_lattice
&other
)
929 return meet_with_1 (&other
.m_vr
);
932 /* Meet the current value of the lattice with value range described by VR
936 ipcp_vr_lattice::meet_with (const value_range
*p_vr
)
938 return meet_with_1 (p_vr
);
941 /* Meet the current value of the lattice with value range described by
942 OTHER_VR lattice. Return TRUE if anything changed. */
945 ipcp_vr_lattice::meet_with_1 (const value_range
*other_vr
)
950 if (other_vr
->varying_p ())
951 return set_to_bottom ();
953 value_range
save (m_vr
);
954 m_vr
.union_ (other_vr
);
955 return !m_vr
.equal_p (save
);
958 /* Return true if value range information in the lattice is yet unknown. */
961 ipcp_vr_lattice::top_p () const
963 return m_vr
.undefined_p ();
966 /* Return true if value range information in the lattice is known to be
970 ipcp_vr_lattice::bottom_p () const
972 return m_vr
.varying_p ();
975 /* Set value range information in the lattice to bottom. Return true if it
976 previously was in a different state. */
979 ipcp_vr_lattice::set_to_bottom ()
981 if (m_vr
.varying_p ())
983 /* ?? We create all sorts of VARYING ranges for floats, structures,
984 and other types which we cannot handle as ranges. We should
985 probably avoid handling them throughout the pass, but it's easier
986 to create a sensible VARYING here and let the lattice
988 m_vr
.set_varying (integer_type_node
);
992 /* Set lattice value to bottom, if it already isn't the case. */
995 ipcp_bits_lattice::set_to_bottom ()
999 m_lattice_val
= IPA_BITS_VARYING
;
1005 /* Set to constant if it isn't already. Only meant to be called
1006 when switching state from TOP. */
1009 ipcp_bits_lattice::set_to_constant (widest_int value
, widest_int mask
)
1011 gcc_assert (top_p ());
1012 m_lattice_val
= IPA_BITS_CONSTANT
;
1018 /* Convert operand to value, mask form. */
1021 ipcp_bits_lattice::get_value_and_mask (tree operand
, widest_int
*valuep
, widest_int
*maskp
)
1023 wide_int
get_nonzero_bits (const_tree
);
1025 if (TREE_CODE (operand
) == INTEGER_CST
)
1027 *valuep
= wi::to_widest (operand
);
1037 /* Meet operation, similar to ccp_lattice_meet, we xor values
1038 if this->value, value have different values at same bit positions, we want
1039 to drop that bit to varying. Return true if mask is changed.
1040 This function assumes that the lattice value is in CONSTANT state */
1043 ipcp_bits_lattice::meet_with_1 (widest_int value
, widest_int mask
,
1046 gcc_assert (constant_p ());
1048 widest_int old_mask
= m_mask
;
1049 m_mask
= (m_mask
| mask
) | (m_value
^ value
);
1051 if (wi::sext (m_mask
, precision
) == -1)
1052 return set_to_bottom ();
1054 return m_mask
!= old_mask
;
1057 /* Meet the bits lattice with operand
1058 described by <value, mask, sgn, precision. */
1061 ipcp_bits_lattice::meet_with (widest_int value
, widest_int mask
,
1069 if (wi::sext (mask
, precision
) == -1)
1070 return set_to_bottom ();
1071 return set_to_constant (value
, mask
);
1074 return meet_with_1 (value
, mask
, precision
);
1077 /* Meet bits lattice with the result of bit_value_binop (other, operand)
1078 if code is binary operation or bit_value_unop (other) if code is unary op.
1079 In the case when code is nop_expr, no adjustment is required. */
1082 ipcp_bits_lattice::meet_with (ipcp_bits_lattice
& other
, unsigned precision
,
1083 signop sgn
, enum tree_code code
, tree operand
)
1085 if (other
.bottom_p ())
1086 return set_to_bottom ();
1088 if (bottom_p () || other
.top_p ())
1091 widest_int adjusted_value
, adjusted_mask
;
1093 if (TREE_CODE_CLASS (code
) == tcc_binary
)
1095 tree type
= TREE_TYPE (operand
);
1096 widest_int o_value
, o_mask
;
1097 get_value_and_mask (operand
, &o_value
, &o_mask
);
1099 bit_value_binop (code
, sgn
, precision
, &adjusted_value
, &adjusted_mask
,
1100 sgn
, precision
, other
.get_value (), other
.get_mask (),
1101 TYPE_SIGN (type
), TYPE_PRECISION (type
), o_value
, o_mask
);
1103 if (wi::sext (adjusted_mask
, precision
) == -1)
1104 return set_to_bottom ();
1107 else if (TREE_CODE_CLASS (code
) == tcc_unary
)
1109 bit_value_unop (code
, sgn
, precision
, &adjusted_value
,
1110 &adjusted_mask
, sgn
, precision
, other
.get_value (),
1113 if (wi::sext (adjusted_mask
, precision
) == -1)
1114 return set_to_bottom ();
1118 return set_to_bottom ();
1122 if (wi::sext (adjusted_mask
, precision
) == -1)
1123 return set_to_bottom ();
1124 return set_to_constant (adjusted_value
, adjusted_mask
);
1127 return meet_with_1 (adjusted_value
, adjusted_mask
, precision
);
1130 /* Mark bot aggregate and scalar lattices as containing an unknown variable,
1131 return true is any of them has not been marked as such so far. */
1134 set_all_contains_variable (class ipcp_param_lattices
*plats
)
1137 ret
= plats
->itself
.set_contains_variable ();
1138 ret
|= plats
->ctxlat
.set_contains_variable ();
1139 ret
|= set_agg_lats_contain_variable (plats
);
1140 ret
|= plats
->bits_lattice
.set_to_bottom ();
1141 ret
|= plats
->m_value_range
.set_to_bottom ();
1145 /* Worker of call_for_symbol_thunks_and_aliases, increment the integer DATA
1146 points to by the number of callers to NODE. */
1149 count_callers (cgraph_node
*node
, void *data
)
1151 int *caller_count
= (int *) data
;
1153 for (cgraph_edge
*cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
1154 /* Local thunks can be handled transparently, but if the thunk cannot
1155 be optimized out, count it as a real use. */
1156 if (!cs
->caller
->thunk
.thunk_p
|| !cs
->caller
->local
)
1161 /* Worker of call_for_symbol_thunks_and_aliases, it is supposed to be called on
1162 the one caller of some other node. Set the caller's corresponding flag. */
1165 set_single_call_flag (cgraph_node
*node
, void *)
1167 cgraph_edge
*cs
= node
->callers
;
1168 /* Local thunks can be handled transparently, skip them. */
1169 while (cs
&& cs
->caller
->thunk
.thunk_p
&& cs
->caller
->local
)
1170 cs
= cs
->next_caller
;
1171 if (cs
&& IPA_NODE_REF (cs
->caller
))
1173 IPA_NODE_REF (cs
->caller
)->node_calling_single_call
= true;
1179 /* Initialize ipcp_lattices. */
1182 initialize_node_lattices (struct cgraph_node
*node
)
1184 class ipa_node_params
*info
= IPA_NODE_REF (node
);
1185 struct cgraph_edge
*ie
;
1186 bool disable
= false, variable
= false;
1189 gcc_checking_assert (node
->has_gimple_body_p ());
1191 if (!ipa_get_param_count (info
))
1193 else if (node
->local
)
1195 int caller_count
= 0;
1196 node
->call_for_symbol_thunks_and_aliases (count_callers
, &caller_count
,
1198 gcc_checking_assert (caller_count
> 0);
1199 if (caller_count
== 1)
1200 node
->call_for_symbol_thunks_and_aliases (set_single_call_flag
,
1205 /* When cloning is allowed, we can assume that externally visible
1206 functions are not called. We will compensate this by cloning
1208 if (ipcp_versionable_function_p (node
)
1209 && ipcp_cloning_candidate_p (node
))
1215 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1216 && !node
->alias
&& !node
->thunk
.thunk_p
)
1218 fprintf (dump_file
, "Initializing lattices of %s\n",
1219 node
->dump_name ());
1220 if (disable
|| variable
)
1221 fprintf (dump_file
, " Marking all lattices as %s\n",
1222 disable
? "BOTTOM" : "VARIABLE");
1225 auto_vec
<bool, 16> surviving_params
;
1226 bool pre_modified
= false;
1227 if (!disable
&& node
->clone
.param_adjustments
)
1229 /* At the moment all IPA optimizations should use the number of
1230 parameters of the prevailing decl as the m_always_copy_start.
1231 Handling any other value would complicate the code below, so for the
1232 time bing let's only assert it is so. */
1233 gcc_assert ((node
->clone
.param_adjustments
->m_always_copy_start
1234 == ipa_get_param_count (info
))
1235 || node
->clone
.param_adjustments
->m_always_copy_start
< 0);
1237 pre_modified
= true;
1238 node
->clone
.param_adjustments
->get_surviving_params (&surviving_params
);
1240 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1241 && !node
->alias
&& !node
->thunk
.thunk_p
)
1244 for (int j
= 0; j
< ipa_get_param_count (info
); j
++)
1246 if (j
< (int) surviving_params
.length ()
1247 && surviving_params
[j
])
1252 " The following parameters are dead on arrival:");
1255 fprintf (dump_file
, " %u", j
);
1258 fprintf (dump_file
, "\n");
1262 for (i
= 0; i
< ipa_get_param_count (info
); i
++)
1264 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1266 || (pre_modified
&& (surviving_params
.length () <= (unsigned) i
1267 || !surviving_params
[i
])))
1269 plats
->itself
.set_to_bottom ();
1270 plats
->ctxlat
.set_to_bottom ();
1271 set_agg_lats_to_bottom (plats
);
1272 plats
->bits_lattice
.set_to_bottom ();
1273 plats
->m_value_range
.set_to_bottom ();
1277 plats
->m_value_range
.init ();
1279 set_all_contains_variable (plats
);
1283 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
1284 if (ie
->indirect_info
->polymorphic
1285 && ie
->indirect_info
->param_index
>= 0)
1287 gcc_checking_assert (ie
->indirect_info
->param_index
>= 0);
1288 ipa_get_parm_lattices (info
,
1289 ie
->indirect_info
->param_index
)->virt_call
= 1;
1293 /* Return the result of a (possibly arithmetic) operation on the constant
1294 value INPUT. OPERAND is 2nd operand for binary operation. RES_TYPE is
1295 the type of the parameter to which the result is passed. Return
1296 NULL_TREE if that cannot be determined or be considered an
1297 interprocedural invariant. */
1300 ipa_get_jf_arith_result (enum tree_code opcode
, tree input
, tree operand
,
1305 if (opcode
== NOP_EXPR
)
1307 if (!is_gimple_ip_invariant (input
))
1312 if (TREE_CODE_CLASS (opcode
) == tcc_comparison
)
1313 res_type
= boolean_type_node
;
1314 else if (expr_type_first_operand_type_p (opcode
))
1315 res_type
= TREE_TYPE (input
);
1320 if (TREE_CODE_CLASS (opcode
) == tcc_unary
)
1321 res
= fold_unary (opcode
, res_type
, input
);
1323 res
= fold_binary (opcode
, res_type
, input
, operand
);
1325 if (res
&& !is_gimple_ip_invariant (res
))
1331 /* Return the result of a (possibly arithmetic) pass through jump function
1332 JFUNC on the constant value INPUT. RES_TYPE is the type of the parameter
1333 to which the result is passed. Return NULL_TREE if that cannot be
1334 determined or be considered an interprocedural invariant. */
1337 ipa_get_jf_pass_through_result (struct ipa_jump_func
*jfunc
, tree input
,
1340 return ipa_get_jf_arith_result (ipa_get_jf_pass_through_operation (jfunc
),
1342 ipa_get_jf_pass_through_operand (jfunc
),
1346 /* Return the result of an ancestor jump function JFUNC on the constant value
1347 INPUT. Return NULL_TREE if that cannot be determined. */
1350 ipa_get_jf_ancestor_result (struct ipa_jump_func
*jfunc
, tree input
)
1352 gcc_checking_assert (TREE_CODE (input
) != TREE_BINFO
);
1353 if (TREE_CODE (input
) == ADDR_EXPR
)
1355 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
2482 true. MAX_AGG_ITEMS is the maximum number of lattices. */
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
, int max_agg_items
)
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
== 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 int max_agg_items
= opt_for_fn (cs
->callee
->function_symbol ()->decl
,
2578 param_ipa_max_agg_items
);
2579 for (struct ipcp_agg_lattice
*src_aglat
= src_plats
->aggs
;
2581 src_aglat
= src_aglat
->next
)
2583 HOST_WIDE_INT new_offset
= src_aglat
->offset
- offset_delta
;
2587 if (merge_agg_lats_step (dest_plats
, new_offset
, src_aglat
->size
,
2588 &dst_aglat
, pre_existing
, &ret
, max_agg_items
))
2590 struct ipcp_agg_lattice
*new_al
= *dst_aglat
;
2592 dst_aglat
= &(*dst_aglat
)->next
;
2593 if (src_aglat
->bottom
)
2595 ret
|= new_al
->set_contains_variable ();
2598 if (src_aglat
->contains_variable
)
2599 ret
|= new_al
->set_contains_variable ();
2600 for (ipcp_value
<tree
> *val
= src_aglat
->values
;
2603 ret
|= new_al
->add_value (val
->value
, cs
, val
, src_idx
,
2606 else if (dest_plats
->aggs_bottom
)
2609 ret
|= set_chain_of_aglats_contains_variable (*dst_aglat
);
2613 /* Determine whether there is anything to propagate FROM SRC_PLATS through a
2614 pass-through JFUNC and if so, whether it has conform and conforms to the
2615 rules about propagating values passed by reference. */
2618 agg_pass_through_permissible_p (class ipcp_param_lattices
*src_plats
,
2619 struct ipa_jump_func
*jfunc
)
2621 return src_plats
->aggs
2622 && (!src_plats
->aggs_by_ref
2623 || ipa_get_jf_pass_through_agg_preserved (jfunc
));
2626 /* Propagate values through ITEM, jump function for a part of an aggregate,
2627 into corresponding aggregate lattice AGLAT. CS is the call graph edge
2628 associated with the jump function. Return true if AGLAT changed in any
2632 propagate_aggregate_lattice (struct cgraph_edge
*cs
,
2633 struct ipa_agg_jf_item
*item
,
2634 struct ipcp_agg_lattice
*aglat
)
2636 class ipa_node_params
*caller_info
;
2637 class ipcp_param_lattices
*src_plats
;
2638 struct ipcp_lattice
<tree
> *src_lat
;
2639 HOST_WIDE_INT src_offset
;
2644 if (item
->jftype
== IPA_JF_CONST
)
2646 tree value
= item
->value
.constant
;
2648 gcc_checking_assert (is_gimple_ip_invariant (value
));
2649 return aglat
->add_value (value
, cs
, NULL
, 0);
2652 gcc_checking_assert (item
->jftype
== IPA_JF_PASS_THROUGH
2653 || item
->jftype
== IPA_JF_LOAD_AGG
);
2655 caller_info
= IPA_NODE_REF (cs
->caller
);
2656 src_idx
= item
->value
.pass_through
.formal_id
;
2657 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2659 if (item
->jftype
== IPA_JF_PASS_THROUGH
)
2661 load_type
= NULL_TREE
;
2662 src_lat
= &src_plats
->itself
;
2667 HOST_WIDE_INT load_offset
= item
->value
.load_agg
.offset
;
2668 struct ipcp_agg_lattice
*src_aglat
;
2670 for (src_aglat
= src_plats
->aggs
; src_aglat
; src_aglat
= src_aglat
->next
)
2671 if (src_aglat
->offset
>= load_offset
)
2674 load_type
= item
->value
.load_agg
.type
;
2676 || src_aglat
->offset
> load_offset
2677 || src_aglat
->size
!= tree_to_shwi (TYPE_SIZE (load_type
))
2678 || src_plats
->aggs_by_ref
!= item
->value
.load_agg
.by_ref
)
2679 return aglat
->set_contains_variable ();
2681 src_lat
= src_aglat
;
2682 src_offset
= load_offset
;
2686 || (!ipcp_versionable_function_p (cs
->caller
)
2687 && !src_lat
->is_single_const ()))
2688 return aglat
->set_contains_variable ();
2690 ret
= propagate_vals_across_arith_jfunc (cs
,
2691 item
->value
.pass_through
.operation
,
2693 item
->value
.pass_through
.operand
,
2699 if (src_lat
->contains_variable
)
2700 ret
|= aglat
->set_contains_variable ();
2705 /* Propagate scalar values across jump function JFUNC that is associated with
2706 edge CS and put the values into DEST_LAT. */
2709 propagate_aggs_across_jump_function (struct cgraph_edge
*cs
,
2710 struct ipa_jump_func
*jfunc
,
2711 class ipcp_param_lattices
*dest_plats
)
2715 if (dest_plats
->aggs_bottom
)
2718 if (jfunc
->type
== IPA_JF_PASS_THROUGH
2719 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
2721 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2722 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
2723 class ipcp_param_lattices
*src_plats
;
2725 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2726 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
2728 /* Currently we do not produce clobber aggregate jump
2729 functions, replace with merging when we do. */
2730 gcc_assert (!jfunc
->agg
.items
);
2731 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
,
2735 ret
|= set_agg_lats_contain_variable (dest_plats
);
2737 else if (jfunc
->type
== IPA_JF_ANCESTOR
2738 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
2740 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2741 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
2742 class ipcp_param_lattices
*src_plats
;
2744 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2745 if (src_plats
->aggs
&& src_plats
->aggs_by_ref
)
2747 /* Currently we do not produce clobber aggregate jump
2748 functions, replace with merging when we do. */
2749 gcc_assert (!jfunc
->agg
.items
);
2750 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
, src_idx
,
2751 ipa_get_jf_ancestor_offset (jfunc
));
2753 else if (!src_plats
->aggs_by_ref
)
2754 ret
|= set_agg_lats_to_bottom (dest_plats
);
2756 ret
|= set_agg_lats_contain_variable (dest_plats
);
2758 else if (jfunc
->agg
.items
)
2760 bool pre_existing
= dest_plats
->aggs
!= NULL
;
2761 struct ipcp_agg_lattice
**aglat
= &dest_plats
->aggs
;
2762 struct ipa_agg_jf_item
*item
;
2765 if (set_check_aggs_by_ref (dest_plats
, jfunc
->agg
.by_ref
))
2768 int max_agg_items
= opt_for_fn (cs
->callee
->function_symbol ()->decl
,
2769 param_ipa_max_agg_items
);
2770 FOR_EACH_VEC_ELT (*jfunc
->agg
.items
, i
, item
)
2772 HOST_WIDE_INT val_size
;
2774 if (item
->offset
< 0 || item
->jftype
== IPA_JF_UNKNOWN
)
2776 val_size
= tree_to_shwi (TYPE_SIZE (item
->type
));
2778 if (merge_agg_lats_step (dest_plats
, item
->offset
, val_size
,
2779 &aglat
, pre_existing
, &ret
, max_agg_items
))
2781 ret
|= propagate_aggregate_lattice (cs
, item
, *aglat
);
2782 aglat
= &(*aglat
)->next
;
2784 else if (dest_plats
->aggs_bottom
)
2788 ret
|= set_chain_of_aglats_contains_variable (*aglat
);
2791 ret
|= set_agg_lats_contain_variable (dest_plats
);
2796 /* Return true if on the way cfrom CS->caller to the final (non-alias and
2797 non-thunk) destination, the call passes through a thunk. */
2800 call_passes_through_thunk_p (cgraph_edge
*cs
)
2802 cgraph_node
*alias_or_thunk
= cs
->callee
;
2803 while (alias_or_thunk
->alias
)
2804 alias_or_thunk
= alias_or_thunk
->get_alias_target ();
2805 return alias_or_thunk
->thunk
.thunk_p
;
2808 /* Propagate constants from the caller to the callee of CS. INFO describes the
2812 propagate_constants_across_call (struct cgraph_edge
*cs
)
2814 class ipa_node_params
*callee_info
;
2815 enum availability availability
;
2816 cgraph_node
*callee
;
2817 class ipa_edge_args
*args
;
2819 int i
, args_count
, parms_count
;
2821 callee
= cs
->callee
->function_symbol (&availability
);
2822 if (!callee
->definition
)
2824 gcc_checking_assert (callee
->has_gimple_body_p ());
2825 callee_info
= IPA_NODE_REF (callee
);
2829 args
= IPA_EDGE_REF (cs
);
2830 parms_count
= ipa_get_param_count (callee_info
);
2831 if (parms_count
== 0)
2834 || !opt_for_fn (cs
->caller
->decl
, flag_ipa_cp
)
2835 || !opt_for_fn (cs
->caller
->decl
, optimize
))
2837 for (i
= 0; i
< parms_count
; i
++)
2838 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
2842 args_count
= ipa_get_cs_argument_count (args
);
2844 /* If this call goes through a thunk we must not propagate to the first (0th)
2845 parameter. However, we might need to uncover a thunk from below a series
2846 of aliases first. */
2847 if (call_passes_through_thunk_p (cs
))
2849 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
2856 for (; (i
< args_count
) && (i
< parms_count
); i
++)
2858 struct ipa_jump_func
*jump_func
= ipa_get_ith_jump_func (args
, i
);
2859 class ipcp_param_lattices
*dest_plats
;
2860 tree param_type
= ipa_get_type (callee_info
, i
);
2862 dest_plats
= ipa_get_parm_lattices (callee_info
, i
);
2863 if (availability
== AVAIL_INTERPOSABLE
)
2864 ret
|= set_all_contains_variable (dest_plats
);
2867 ret
|= propagate_scalar_across_jump_function (cs
, jump_func
,
2868 &dest_plats
->itself
,
2870 ret
|= propagate_context_across_jump_function (cs
, jump_func
, i
,
2871 &dest_plats
->ctxlat
);
2873 |= propagate_bits_across_jump_function (cs
, i
, jump_func
,
2874 &dest_plats
->bits_lattice
);
2875 ret
|= propagate_aggs_across_jump_function (cs
, jump_func
,
2877 if (opt_for_fn (callee
->decl
, flag_ipa_vrp
))
2878 ret
|= propagate_vr_across_jump_function (cs
, jump_func
,
2879 dest_plats
, param_type
);
2881 ret
|= dest_plats
->m_value_range
.set_to_bottom ();
2884 for (; i
< parms_count
; i
++)
2885 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
, i
));
2890 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
2891 KNOWN_CONTEXTS, KNOWN_AGGS or AGG_REPS return the destination. The latter
2892 three can be NULL. If AGG_REPS is not NULL, KNOWN_AGGS is ignored. */
2895 ipa_get_indirect_edge_target_1 (struct cgraph_edge
*ie
,
2896 vec
<tree
> known_csts
,
2897 vec
<ipa_polymorphic_call_context
> known_contexts
,
2898 vec
<ipa_agg_value_set
> known_aggs
,
2899 struct ipa_agg_replacement_value
*agg_reps
,
2902 int param_index
= ie
->indirect_info
->param_index
;
2903 HOST_WIDE_INT anc_offset
;
2907 *speculative
= false;
2909 if (param_index
== -1)
2912 if (!ie
->indirect_info
->polymorphic
)
2916 if (ie
->indirect_info
->agg_contents
)
2919 if (agg_reps
&& ie
->indirect_info
->guaranteed_unmodified
)
2923 if (agg_reps
->index
== param_index
2924 && agg_reps
->offset
== ie
->indirect_info
->offset
2925 && agg_reps
->by_ref
== ie
->indirect_info
->by_ref
)
2927 t
= agg_reps
->value
;
2930 agg_reps
= agg_reps
->next
;
2935 struct ipa_agg_value_set
*agg
;
2936 if (known_aggs
.length () > (unsigned int) param_index
)
2937 agg
= &known_aggs
[param_index
];
2940 bool from_global_constant
;
2941 t
= ipa_find_agg_cst_for_param (agg
,
2942 (unsigned) param_index
2943 < known_csts
.length ()
2944 ? known_csts
[param_index
]
2946 ie
->indirect_info
->offset
,
2947 ie
->indirect_info
->by_ref
,
2948 &from_global_constant
);
2950 && !from_global_constant
2951 && !ie
->indirect_info
->guaranteed_unmodified
)
2955 else if ((unsigned) param_index
< known_csts
.length ())
2956 t
= known_csts
[param_index
];
2959 && TREE_CODE (t
) == ADDR_EXPR
2960 && TREE_CODE (TREE_OPERAND (t
, 0)) == FUNCTION_DECL
)
2961 return TREE_OPERAND (t
, 0);
2966 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize
))
2969 gcc_assert (!ie
->indirect_info
->agg_contents
);
2970 anc_offset
= ie
->indirect_info
->offset
;
2974 /* Try to work out value of virtual table pointer value in replacements. */
2975 if (!t
&& agg_reps
&& !ie
->indirect_info
->by_ref
)
2979 if (agg_reps
->index
== param_index
2980 && agg_reps
->offset
== ie
->indirect_info
->offset
2981 && agg_reps
->by_ref
)
2983 t
= agg_reps
->value
;
2986 agg_reps
= agg_reps
->next
;
2990 /* Try to work out value of virtual table pointer value in known
2991 aggregate values. */
2992 if (!t
&& known_aggs
.length () > (unsigned int) param_index
2993 && !ie
->indirect_info
->by_ref
)
2995 struct ipa_agg_value_set
*agg
= &known_aggs
[param_index
];
2996 t
= ipa_find_agg_cst_for_param (agg
,
2997 (unsigned) param_index
2998 < known_csts
.length ()
2999 ? known_csts
[param_index
] : NULL
,
3000 ie
->indirect_info
->offset
, true);
3003 /* If we found the virtual table pointer, lookup the target. */
3007 unsigned HOST_WIDE_INT offset
;
3008 if (vtable_pointer_value_to_vtable (t
, &vtable
, &offset
))
3011 target
= gimple_get_virt_method_for_vtable (ie
->indirect_info
->otr_token
,
3012 vtable
, offset
, &can_refer
);
3016 || fndecl_built_in_p (target
, BUILT_IN_UNREACHABLE
)
3017 || !possible_polymorphic_call_target_p
3018 (ie
, cgraph_node::get (target
)))
3020 /* Do not speculate builtin_unreachable, it is stupid! */
3021 if (ie
->indirect_info
->vptr_changed
)
3023 target
= ipa_impossible_devirt_target (ie
, target
);
3025 *speculative
= ie
->indirect_info
->vptr_changed
;
3032 /* Do we know the constant value of pointer? */
3033 if (!t
&& (unsigned) param_index
< known_csts
.length ())
3034 t
= known_csts
[param_index
];
3036 gcc_checking_assert (!t
|| TREE_CODE (t
) != TREE_BINFO
);
3038 ipa_polymorphic_call_context context
;
3039 if (known_contexts
.length () > (unsigned int) param_index
)
3041 context
= known_contexts
[param_index
];
3042 context
.offset_by (anc_offset
);
3043 if (ie
->indirect_info
->vptr_changed
)
3044 context
.possible_dynamic_type_change (ie
->in_polymorphic_cdtor
,
3045 ie
->indirect_info
->otr_type
);
3048 ipa_polymorphic_call_context ctx2
= ipa_polymorphic_call_context
3049 (t
, ie
->indirect_info
->otr_type
, anc_offset
);
3050 if (!ctx2
.useless_p ())
3051 context
.combine_with (ctx2
, ie
->indirect_info
->otr_type
);
3056 context
= ipa_polymorphic_call_context (t
, ie
->indirect_info
->otr_type
,
3058 if (ie
->indirect_info
->vptr_changed
)
3059 context
.possible_dynamic_type_change (ie
->in_polymorphic_cdtor
,
3060 ie
->indirect_info
->otr_type
);
3065 vec
<cgraph_node
*>targets
;
3068 targets
= possible_polymorphic_call_targets
3069 (ie
->indirect_info
->otr_type
,
3070 ie
->indirect_info
->otr_token
,
3072 if (!final
|| targets
.length () > 1)
3074 struct cgraph_node
*node
;
3077 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize_speculatively
)
3078 || ie
->speculative
|| !ie
->maybe_hot_p ())
3080 node
= try_speculative_devirtualization (ie
->indirect_info
->otr_type
,
3081 ie
->indirect_info
->otr_token
,
3085 *speculative
= true;
3086 target
= node
->decl
;
3093 *speculative
= false;
3094 if (targets
.length () == 1)
3095 target
= targets
[0]->decl
;
3097 target
= ipa_impossible_devirt_target (ie
, NULL_TREE
);
3100 if (target
&& !possible_polymorphic_call_target_p (ie
,
3101 cgraph_node::get (target
)))
3105 target
= ipa_impossible_devirt_target (ie
, target
);
3112 /* If an indirect edge IE can be turned into a direct one based on KNOWN_CSTS,
3113 KNOWN_CONTEXTS (which can be vNULL) or KNOWN_AGGS (which also can be vNULL)
3114 return the destination. */
3117 ipa_get_indirect_edge_target (struct cgraph_edge
*ie
,
3118 vec
<tree
> known_csts
,
3119 vec
<ipa_polymorphic_call_context
> known_contexts
,
3120 vec
<ipa_agg_value_set
> known_aggs
,
3123 return ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
3124 known_aggs
, NULL
, speculative
);
3127 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
3128 and KNOWN_CONTEXTS. */
3131 devirtualization_time_bonus (struct cgraph_node
*node
,
3132 vec
<tree
> known_csts
,
3133 vec
<ipa_polymorphic_call_context
> known_contexts
,
3134 vec
<ipa_agg_value_set
> known_aggs
)
3136 struct cgraph_edge
*ie
;
3139 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
3141 struct cgraph_node
*callee
;
3142 class ipa_fn_summary
*isummary
;
3143 enum availability avail
;
3147 target
= ipa_get_indirect_edge_target (ie
, known_csts
, known_contexts
,
3148 known_aggs
, &speculative
);
3152 /* Only bare minimum benefit for clearly un-inlineable targets. */
3154 callee
= cgraph_node::get (target
);
3155 if (!callee
|| !callee
->definition
)
3157 callee
= callee
->function_symbol (&avail
);
3158 if (avail
< AVAIL_AVAILABLE
)
3160 isummary
= ipa_fn_summaries
->get (callee
);
3161 if (!isummary
->inlinable
)
3164 int size
= ipa_size_summaries
->get (callee
)->size
;
3165 /* FIXME: The values below need re-considering and perhaps also
3166 integrating into the cost metrics, at lest in some very basic way. */
3167 int max_inline_insns_auto
3168 = opt_for_fn (callee
->decl
, param_max_inline_insns_auto
);
3169 if (size
<= max_inline_insns_auto
/ 4)
3170 res
+= 31 / ((int)speculative
+ 1);
3171 else if (size
<= max_inline_insns_auto
/ 2)
3172 res
+= 15 / ((int)speculative
+ 1);
3173 else if (size
<= max_inline_insns_auto
3174 || DECL_DECLARED_INLINE_P (callee
->decl
))
3175 res
+= 7 / ((int)speculative
+ 1);
3181 /* Return time bonus incurred because of HINTS. */
3184 hint_time_bonus (cgraph_node
*node
, ipa_hints hints
)
3187 if (hints
& (INLINE_HINT_loop_iterations
| INLINE_HINT_loop_stride
))
3188 result
+= opt_for_fn (node
->decl
, param_ipa_cp_loop_hint_bonus
);
3192 /* If there is a reason to penalize the function described by INFO in the
3193 cloning goodness evaluation, do so. */
3195 static inline int64_t
3196 incorporate_penalties (cgraph_node
*node
, ipa_node_params
*info
,
3199 if (info
->node_within_scc
&& !info
->node_is_self_scc
)
3200 evaluation
= (evaluation
3201 * (100 - opt_for_fn (node
->decl
,
3202 param_ipa_cp_recursion_penalty
))) / 100;
3204 if (info
->node_calling_single_call
)
3205 evaluation
= (evaluation
3206 * (100 - opt_for_fn (node
->decl
,
3207 param_ipa_cp_single_call_penalty
)))
3213 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
3214 and SIZE_COST and with the sum of frequencies of incoming edges to the
3215 potential new clone in FREQUENCIES. */
3218 good_cloning_opportunity_p (struct cgraph_node
*node
, int time_benefit
,
3219 int freq_sum
, profile_count count_sum
, int size_cost
)
3221 if (time_benefit
== 0
3222 || !opt_for_fn (node
->decl
, flag_ipa_cp_clone
)
3223 || node
->optimize_for_size_p ())
3226 gcc_assert (size_cost
> 0);
3228 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3229 int eval_threshold
= opt_for_fn (node
->decl
, param_ipa_cp_eval_threshold
);
3230 if (max_count
> profile_count::zero ())
3232 int factor
= RDIV (count_sum
.probability_in
3233 (max_count
).to_reg_br_prob_base ()
3234 * 1000, REG_BR_PROB_BASE
);
3235 int64_t evaluation
= (((int64_t) time_benefit
* factor
)
3237 evaluation
= incorporate_penalties (node
, info
, evaluation
);
3239 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3241 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
3242 "size: %i, count_sum: ", time_benefit
, size_cost
);
3243 count_sum
.dump (dump_file
);
3244 fprintf (dump_file
, "%s%s) -> evaluation: " "%" PRId64
3245 ", threshold: %i\n",
3246 info
->node_within_scc
3247 ? (info
->node_is_self_scc
? ", self_scc" : ", scc") : "",
3248 info
->node_calling_single_call
? ", single_call" : "",
3249 evaluation
, eval_threshold
);
3252 return evaluation
>= eval_threshold
;
3256 int64_t evaluation
= (((int64_t) time_benefit
* freq_sum
)
3258 evaluation
= incorporate_penalties (node
, info
, evaluation
);
3260 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3261 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
3262 "size: %i, freq_sum: %i%s%s) -> evaluation: "
3263 "%" PRId64
", threshold: %i\n",
3264 time_benefit
, size_cost
, freq_sum
,
3265 info
->node_within_scc
3266 ? (info
->node_is_self_scc
? ", self_scc" : ", scc") : "",
3267 info
->node_calling_single_call
? ", single_call" : "",
3268 evaluation
, eval_threshold
);
3270 return evaluation
>= eval_threshold
;
3274 /* Return all context independent values from aggregate lattices in PLATS in a
3275 vector. Return NULL if there are none. */
3277 static vec
<ipa_agg_value
>
3278 context_independent_aggregate_values (class ipcp_param_lattices
*plats
)
3280 vec
<ipa_agg_value
> res
= vNULL
;
3282 if (plats
->aggs_bottom
3283 || plats
->aggs_contain_variable
3284 || plats
->aggs_count
== 0)
3287 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
;
3289 aglat
= aglat
->next
)
3290 if (aglat
->is_single_const ())
3292 struct ipa_agg_value item
;
3293 item
.offset
= aglat
->offset
;
3294 item
.value
= aglat
->values
->value
;
3295 res
.safe_push (item
);
3300 /* Allocate KNOWN_CSTS, KNOWN_CONTEXTS and, if non-NULL, KNOWN_AGGS and
3301 populate them with values of parameters that are known independent of the
3302 context. INFO describes the function. If REMOVABLE_PARAMS_COST is
3303 non-NULL, the movement cost of all removable parameters will be stored in
3307 gather_context_independent_values (class ipa_node_params
*info
,
3308 vec
<tree
> *known_csts
,
3309 vec
<ipa_polymorphic_call_context
>
3311 vec
<ipa_agg_value_set
> *known_aggs
,
3312 int *removable_params_cost
)
3314 int i
, count
= ipa_get_param_count (info
);
3317 known_csts
->create (0);
3318 known_contexts
->create (0);
3319 known_csts
->safe_grow_cleared (count
);
3320 known_contexts
->safe_grow_cleared (count
);
3323 known_aggs
->create (0);
3324 known_aggs
->safe_grow_cleared (count
);
3327 if (removable_params_cost
)
3328 *removable_params_cost
= 0;
3330 for (i
= 0; i
< count
; i
++)
3332 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3333 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
3335 if (lat
->is_single_const ())
3337 ipcp_value
<tree
> *val
= lat
->values
;
3338 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
3339 (*known_csts
)[i
] = val
->value
;
3340 if (removable_params_cost
)
3341 *removable_params_cost
3342 += estimate_move_cost (TREE_TYPE (val
->value
), false);
3345 else if (removable_params_cost
3346 && !ipa_is_param_used (info
, i
))
3347 *removable_params_cost
3348 += ipa_get_param_move_cost (info
, i
);
3350 if (!ipa_is_param_used (info
, i
))
3353 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
3354 /* Do not account known context as reason for cloning. We can see
3355 if it permits devirtualization. */
3356 if (ctxlat
->is_single_const ())
3357 (*known_contexts
)[i
] = ctxlat
->values
->value
;
3361 vec
<ipa_agg_value
> agg_items
;
3362 struct ipa_agg_value_set
*agg
;
3364 agg_items
= context_independent_aggregate_values (plats
);
3365 agg
= &(*known_aggs
)[i
];
3366 agg
->items
= agg_items
;
3367 agg
->by_ref
= plats
->aggs_by_ref
;
3368 ret
|= !agg_items
.is_empty ();
3375 /* Perform time and size measurement of NODE with the context given in
3376 KNOWN_CSTS, KNOWN_CONTEXTS and KNOWN_AGGS, calculate the benefit and cost
3377 given BASE_TIME of the node without specialization, REMOVABLE_PARAMS_COST of
3378 all context-independent removable parameters and EST_MOVE_COST of estimated
3379 movement of the considered parameter and store it into VAL. */
3382 perform_estimation_of_a_value (cgraph_node
*node
, vec
<tree
> known_csts
,
3383 vec
<ipa_polymorphic_call_context
> known_contexts
,
3384 vec
<ipa_agg_value_set
> known_aggs
,
3385 int removable_params_cost
,
3386 int est_move_cost
, ipcp_value_base
*val
)
3388 int size
, time_benefit
;
3389 sreal time
, base_time
;
3392 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
3393 known_aggs
, &size
, &time
,
3394 &base_time
, &hints
);
3396 if (base_time
> 65535)
3399 /* Extern inline functions have no cloning local time benefits because they
3400 will be inlined anyway. The only reason to clone them is if it enables
3401 optimization in any of the functions they call. */
3402 if (DECL_EXTERNAL (node
->decl
) && DECL_DECLARED_INLINE_P (node
->decl
))
3405 time_benefit
= base_time
.to_int ()
3406 + devirtualization_time_bonus (node
, known_csts
, known_contexts
,
3408 + hint_time_bonus (node
, hints
)
3409 + removable_params_cost
+ est_move_cost
;
3411 gcc_checking_assert (size
>=0);
3412 /* The inliner-heuristics based estimates may think that in certain
3413 contexts some functions do not have any size at all but we want
3414 all specializations to have at least a tiny cost, not least not to
3419 val
->local_time_benefit
= time_benefit
;
3420 val
->local_size_cost
= size
;
3423 /* Get the overall limit oof growth based on parameters extracted from growth.
3424 it does not really make sense to mix functions with different overall growth
3425 limits but it is possible and if it happens, we do not want to select one
3429 get_max_overall_size (cgraph_node
*node
)
3431 long max_new_size
= orig_overall_size
;
3432 long large_unit
= opt_for_fn (node
->decl
, param_large_unit_insns
);
3433 if (max_new_size
< large_unit
)
3434 max_new_size
= large_unit
;
3435 int unit_growth
= opt_for_fn (node
->decl
, param_ipa_cp_unit_growth
);
3436 max_new_size
+= max_new_size
* unit_growth
/ 100 + 1;
3437 return max_new_size
;
3440 /* Iterate over known values of parameters of NODE and estimate the local
3441 effects in terms of time and size they have. */
3444 estimate_local_effects (struct cgraph_node
*node
)
3446 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3447 int i
, count
= ipa_get_param_count (info
);
3448 vec
<tree
> known_csts
;
3449 vec
<ipa_polymorphic_call_context
> known_contexts
;
3450 vec
<ipa_agg_value_set
> known_aggs
;
3452 int removable_params_cost
;
3454 if (!count
|| !ipcp_versionable_function_p (node
))
3457 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3458 fprintf (dump_file
, "\nEstimating effects for %s.\n", node
->dump_name ());
3460 always_const
= gather_context_independent_values (info
, &known_csts
,
3461 &known_contexts
, &known_aggs
,
3462 &removable_params_cost
);
3463 int devirt_bonus
= devirtualization_time_bonus (node
, known_csts
,
3464 known_contexts
, known_aggs
);
3465 if (always_const
|| devirt_bonus
3466 || (removable_params_cost
&& node
->can_change_signature
))
3468 struct caller_statistics stats
;
3470 sreal time
, base_time
;
3473 init_caller_stats (&stats
);
3474 node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
3476 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
3477 known_aggs
, &size
, &time
,
3478 &base_time
, &hints
);
3479 time
-= devirt_bonus
;
3480 time
-= hint_time_bonus (node
, hints
);
3481 time
-= removable_params_cost
;
3482 size
-= stats
.n_calls
* removable_params_cost
;
3485 fprintf (dump_file
, " - context independent values, size: %i, "
3486 "time_benefit: %f\n", size
, (base_time
- time
).to_double ());
3488 if (size
<= 0 || node
->local
)
3490 info
->do_clone_for_all_contexts
= true;
3493 fprintf (dump_file
, " Decided to specialize for all "
3494 "known contexts, code not going to grow.\n");
3496 else if (good_cloning_opportunity_p (node
,
3497 MIN ((base_time
- time
).to_int (),
3499 stats
.freq_sum
, stats
.count_sum
,
3502 if (size
+ overall_size
<= get_max_overall_size (node
))
3504 info
->do_clone_for_all_contexts
= true;
3505 overall_size
+= size
;
3508 fprintf (dump_file
, " Decided to specialize for all "
3509 "known contexts, growth deemed beneficial.\n");
3511 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3512 fprintf (dump_file
, " Not cloning for all contexts because "
3513 "maximum unit size would be reached with %li.\n",
3514 size
+ overall_size
);
3516 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3517 fprintf (dump_file
, " Not cloning for all contexts because "
3518 "!good_cloning_opportunity_p.\n");
3522 for (i
= 0; i
< count
; i
++)
3524 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3525 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
3526 ipcp_value
<tree
> *val
;
3533 for (val
= lat
->values
; val
; val
= val
->next
)
3535 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
3536 known_csts
[i
] = val
->value
;
3538 int emc
= estimate_move_cost (TREE_TYPE (val
->value
), true);
3539 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
3541 removable_params_cost
, emc
, val
);
3543 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3545 fprintf (dump_file
, " - estimates for value ");
3546 print_ipcp_constant_value (dump_file
, val
->value
);
3547 fprintf (dump_file
, " for ");
3548 ipa_dump_param (dump_file
, info
, i
);
3549 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
3550 val
->local_time_benefit
, val
->local_size_cost
);
3553 known_csts
[i
] = NULL_TREE
;
3556 for (i
= 0; i
< count
; i
++)
3558 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3560 if (!plats
->virt_call
)
3563 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
3564 ipcp_value
<ipa_polymorphic_call_context
> *val
;
3568 || !known_contexts
[i
].useless_p ())
3571 for (val
= ctxlat
->values
; val
; val
= val
->next
)
3573 known_contexts
[i
] = val
->value
;
3574 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
3576 removable_params_cost
, 0, val
);
3578 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3580 fprintf (dump_file
, " - estimates for polymorphic context ");
3581 print_ipcp_constant_value (dump_file
, val
->value
);
3582 fprintf (dump_file
, " for ");
3583 ipa_dump_param (dump_file
, info
, i
);
3584 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
3585 val
->local_time_benefit
, val
->local_size_cost
);
3588 known_contexts
[i
] = ipa_polymorphic_call_context ();
3591 for (i
= 0; i
< count
; i
++)
3593 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3594 struct ipa_agg_value_set
*agg
;
3595 struct ipcp_agg_lattice
*aglat
;
3597 if (plats
->aggs_bottom
|| !plats
->aggs
)
3600 agg
= &known_aggs
[i
];
3601 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3603 ipcp_value
<tree
> *val
;
3604 if (aglat
->bottom
|| !aglat
->values
3605 /* If the following is true, the one value is in known_aggs. */
3606 || (!plats
->aggs_contain_variable
3607 && aglat
->is_single_const ()))
3610 for (val
= aglat
->values
; val
; val
= val
->next
)
3612 struct ipa_agg_value item
;
3614 item
.offset
= aglat
->offset
;
3615 item
.value
= val
->value
;
3616 agg
->items
.safe_push (item
);
3618 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
3620 removable_params_cost
, 0, val
);
3622 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3624 fprintf (dump_file
, " - estimates for value ");
3625 print_ipcp_constant_value (dump_file
, val
->value
);
3626 fprintf (dump_file
, " for ");
3627 ipa_dump_param (dump_file
, info
, i
);
3628 fprintf (dump_file
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
3629 "]: time_benefit: %i, size: %i\n",
3630 plats
->aggs_by_ref
? "ref " : "",
3632 val
->local_time_benefit
, val
->local_size_cost
);
3640 known_csts
.release ();
3641 known_contexts
.release ();
3642 ipa_release_agg_values (known_aggs
);
3646 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
3647 topological sort of values. */
3649 template <typename valtype
>
3651 value_topo_info
<valtype
>::add_val (ipcp_value
<valtype
> *cur_val
)
3653 ipcp_value_source
<valtype
> *src
;
3659 cur_val
->dfs
= dfs_counter
;
3660 cur_val
->low_link
= dfs_counter
;
3662 cur_val
->topo_next
= stack
;
3664 cur_val
->on_stack
= true;
3666 for (src
= cur_val
->sources
; src
; src
= src
->next
)
3669 if (src
->val
->dfs
== 0)
3672 if (src
->val
->low_link
< cur_val
->low_link
)
3673 cur_val
->low_link
= src
->val
->low_link
;
3675 else if (src
->val
->on_stack
3676 && src
->val
->dfs
< cur_val
->low_link
)
3677 cur_val
->low_link
= src
->val
->dfs
;
3680 if (cur_val
->dfs
== cur_val
->low_link
)
3682 ipcp_value
<valtype
> *v
, *scc_list
= NULL
;
3687 stack
= v
->topo_next
;
3688 v
->on_stack
= false;
3690 v
->scc_next
= scc_list
;
3693 while (v
!= cur_val
);
3695 cur_val
->topo_next
= values_topo
;
3696 values_topo
= cur_val
;
3700 /* Add all values in lattices associated with NODE to the topological sort if
3701 they are not there yet. */
3704 add_all_node_vals_to_toposort (cgraph_node
*node
, ipa_topo_info
*topo
)
3706 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3707 int i
, count
= ipa_get_param_count (info
);
3709 for (i
= 0; i
< count
; i
++)
3711 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3712 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
3713 struct ipcp_agg_lattice
*aglat
;
3717 ipcp_value
<tree
> *val
;
3718 for (val
= lat
->values
; val
; val
= val
->next
)
3719 topo
->constants
.add_val (val
);
3722 if (!plats
->aggs_bottom
)
3723 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3726 ipcp_value
<tree
> *val
;
3727 for (val
= aglat
->values
; val
; val
= val
->next
)
3728 topo
->constants
.add_val (val
);
3731 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
3732 if (!ctxlat
->bottom
)
3734 ipcp_value
<ipa_polymorphic_call_context
> *ctxval
;
3735 for (ctxval
= ctxlat
->values
; ctxval
; ctxval
= ctxval
->next
)
3736 topo
->contexts
.add_val (ctxval
);
3741 /* One pass of constants propagation along the call graph edges, from callers
3742 to callees (requires topological ordering in TOPO), iterate over strongly
3743 connected components. */
3746 propagate_constants_topo (class ipa_topo_info
*topo
)
3750 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
3753 struct cgraph_node
*v
, *node
= topo
->order
[i
];
3754 vec
<cgraph_node
*> cycle_nodes
= ipa_get_nodes_in_cycle (node
);
3756 /* First, iteratively propagate within the strongly connected component
3757 until all lattices stabilize. */
3758 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
3759 if (v
->has_gimple_body_p ())
3761 if (opt_for_fn (v
->decl
, flag_ipa_cp
)
3762 && opt_for_fn (v
->decl
, optimize
))
3763 push_node_to_stack (topo
, v
);
3764 /* When V is not optimized, we can not push it to stack, but
3765 still we need to set all its callees lattices to bottom. */
3768 for (cgraph_edge
*cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3769 propagate_constants_across_call (cs
);
3773 v
= pop_node_from_stack (topo
);
3776 struct cgraph_edge
*cs
;
3777 class ipa_node_params
*info
= NULL
;
3778 bool self_scc
= true;
3780 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3781 if (ipa_edge_within_scc (cs
))
3783 cgraph_node
*callee
= cs
->callee
->function_symbol ();
3790 info
= IPA_NODE_REF (v
);
3791 info
->node_within_scc
= true;
3794 if (propagate_constants_across_call (cs
))
3795 push_node_to_stack (topo
, callee
);
3799 info
->node_is_self_scc
= self_scc
;
3801 v
= pop_node_from_stack (topo
);
3804 /* Afterwards, propagate along edges leading out of the SCC, calculates
3805 the local effects of the discovered constants and all valid values to
3806 their topological sort. */
3807 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
3808 if (v
->has_gimple_body_p ()
3809 && opt_for_fn (v
->decl
, flag_ipa_cp
)
3810 && opt_for_fn (v
->decl
, optimize
))
3812 struct cgraph_edge
*cs
;
3814 estimate_local_effects (v
);
3815 add_all_node_vals_to_toposort (v
, topo
);
3816 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3817 if (!ipa_edge_within_scc (cs
))
3818 propagate_constants_across_call (cs
);
3820 cycle_nodes
.release ();
3825 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
3826 the bigger one if otherwise. */
3829 safe_add (int a
, int b
)
3831 if (a
> INT_MAX
/2 || b
> INT_MAX
/2)
3832 return a
> b
? a
: b
;
3838 /* Propagate the estimated effects of individual values along the topological
3839 from the dependent values to those they depend on. */
3841 template <typename valtype
>
3843 value_topo_info
<valtype
>::propagate_effects ()
3845 ipcp_value
<valtype
> *base
;
3847 for (base
= values_topo
; base
; base
= base
->topo_next
)
3849 ipcp_value_source
<valtype
> *src
;
3850 ipcp_value
<valtype
> *val
;
3851 int time
= 0, size
= 0;
3853 for (val
= base
; val
; val
= val
->scc_next
)
3855 time
= safe_add (time
,
3856 val
->local_time_benefit
+ val
->prop_time_benefit
);
3857 size
= safe_add (size
, val
->local_size_cost
+ val
->prop_size_cost
);
3860 for (val
= base
; val
; val
= val
->scc_next
)
3861 for (src
= val
->sources
; src
; src
= src
->next
)
3863 && src
->cs
->maybe_hot_p ())
3865 src
->val
->prop_time_benefit
= safe_add (time
,
3866 src
->val
->prop_time_benefit
);
3867 src
->val
->prop_size_cost
= safe_add (size
,
3868 src
->val
->prop_size_cost
);
3874 /* Propagate constants, polymorphic contexts and their effects from the
3875 summaries interprocedurally. */
3878 ipcp_propagate_stage (class ipa_topo_info
*topo
)
3880 struct cgraph_node
*node
;
3883 fprintf (dump_file
, "\n Propagating constants:\n\n");
3885 max_count
= profile_count::uninitialized ();
3887 FOR_EACH_DEFINED_FUNCTION (node
)
3889 if (node
->has_gimple_body_p ()
3890 && opt_for_fn (node
->decl
, flag_ipa_cp
)
3891 && opt_for_fn (node
->decl
, optimize
))
3893 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3894 determine_versionability (node
, info
);
3895 info
->lattices
= XCNEWVEC (class ipcp_param_lattices
,
3896 ipa_get_param_count (info
));
3897 initialize_node_lattices (node
);
3899 ipa_size_summary
*s
= ipa_size_summaries
->get (node
);
3900 if (node
->definition
&& !node
->alias
&& s
!= NULL
)
3901 overall_size
+= s
->self_size
;
3902 max_count
= max_count
.max (node
->count
.ipa ());
3905 orig_overall_size
= overall_size
;
3908 fprintf (dump_file
, "\noverall_size: %li\n", overall_size
);
3910 propagate_constants_topo (topo
);
3912 ipcp_verify_propagated_values ();
3913 topo
->constants
.propagate_effects ();
3914 topo
->contexts
.propagate_effects ();
3918 fprintf (dump_file
, "\nIPA lattices after all propagation:\n");
3919 print_all_lattices (dump_file
, (dump_flags
& TDF_DETAILS
), true);
3923 /* Discover newly direct outgoing edges from NODE which is a new clone with
3924 known KNOWN_CSTS and make them direct. */
3927 ipcp_discover_new_direct_edges (struct cgraph_node
*node
,
3928 vec
<tree
> known_csts
,
3929 vec
<ipa_polymorphic_call_context
>
3931 struct ipa_agg_replacement_value
*aggvals
)
3933 struct cgraph_edge
*ie
, *next_ie
;
3936 for (ie
= node
->indirect_calls
; ie
; ie
= next_ie
)
3941 next_ie
= ie
->next_callee
;
3942 target
= ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
3943 vNULL
, aggvals
, &speculative
);
3946 bool agg_contents
= ie
->indirect_info
->agg_contents
;
3947 bool polymorphic
= ie
->indirect_info
->polymorphic
;
3948 int param_index
= ie
->indirect_info
->param_index
;
3949 struct cgraph_edge
*cs
= ipa_make_edge_direct_to_target (ie
, target
,
3953 if (cs
&& !agg_contents
&& !polymorphic
)
3955 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3956 int c
= ipa_get_controlled_uses (info
, param_index
);
3957 if (c
!= IPA_UNDESCRIBED_USE
)
3959 struct ipa_ref
*to_del
;
3962 ipa_set_controlled_uses (info
, param_index
, c
);
3963 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3964 fprintf (dump_file
, " controlled uses count of param "
3965 "%i bumped down to %i\n", param_index
, c
);
3967 && (to_del
= node
->find_reference (cs
->callee
, NULL
, 0)))
3969 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3970 fprintf (dump_file
, " and even removing its "
3971 "cloning-created reference\n");
3972 to_del
->remove_reference ();
3978 /* Turning calls to direct calls will improve overall summary. */
3980 ipa_update_overall_fn_summary (node
);
3983 class edge_clone_summary
;
3984 static call_summary
<edge_clone_summary
*> *edge_clone_summaries
= NULL
;
3986 /* Edge clone summary. */
3988 class edge_clone_summary
3991 /* Default constructor. */
3992 edge_clone_summary (): prev_clone (NULL
), next_clone (NULL
) {}
3994 /* Default destructor. */
3995 ~edge_clone_summary ()
3998 edge_clone_summaries
->get (prev_clone
)->next_clone
= next_clone
;
4000 edge_clone_summaries
->get (next_clone
)->prev_clone
= prev_clone
;
4003 cgraph_edge
*prev_clone
;
4004 cgraph_edge
*next_clone
;
4007 class edge_clone_summary_t
:
4008 public call_summary
<edge_clone_summary
*>
4011 edge_clone_summary_t (symbol_table
*symtab
):
4012 call_summary
<edge_clone_summary
*> (symtab
)
4014 m_initialize_when_cloning
= true;
4017 virtual void duplicate (cgraph_edge
*src_edge
, cgraph_edge
*dst_edge
,
4018 edge_clone_summary
*src_data
,
4019 edge_clone_summary
*dst_data
);
4022 /* Edge duplication hook. */
4025 edge_clone_summary_t::duplicate (cgraph_edge
*src_edge
, cgraph_edge
*dst_edge
,
4026 edge_clone_summary
*src_data
,
4027 edge_clone_summary
*dst_data
)
4029 if (src_data
->next_clone
)
4030 edge_clone_summaries
->get (src_data
->next_clone
)->prev_clone
= dst_edge
;
4031 dst_data
->prev_clone
= src_edge
;
4032 dst_data
->next_clone
= src_data
->next_clone
;
4033 src_data
->next_clone
= dst_edge
;
4036 /* Return true is NODE is DEST or its clone for all contexts. */
4039 same_node_or_its_all_contexts_clone_p (cgraph_node
*node
, cgraph_node
*dest
)
4044 class ipa_node_params
*info
= IPA_NODE_REF (node
);
4045 return info
->is_all_contexts_clone
&& info
->ipcp_orig_node
== dest
;
4048 /* Return true if edge CS does bring about the value described by SRC to
4049 DEST_VAL of node DEST or its clone for all contexts. */
4052 cgraph_edge_brings_value_p (cgraph_edge
*cs
, ipcp_value_source
<tree
> *src
,
4053 cgraph_node
*dest
, ipcp_value
<tree
> *dest_val
)
4055 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4056 enum availability availability
;
4057 cgraph_node
*real_dest
= cs
->callee
->function_symbol (&availability
);
4059 if (availability
<= AVAIL_INTERPOSABLE
4060 || !same_node_or_its_all_contexts_clone_p (real_dest
, dest
)
4061 || caller_info
->node_dead
)
4067 if (caller_info
->ipcp_orig_node
)
4070 if (src
->offset
== -1)
4071 t
= caller_info
->known_csts
[src
->index
];
4073 t
= get_clone_agg_value (cs
->caller
, src
->offset
, src
->index
);
4074 return (t
!= NULL_TREE
4075 && values_equal_for_ipcp_p (src
->val
->value
, t
));
4079 /* At the moment we do not propagate over arithmetic jump functions in
4080 SCCs, so it is safe to detect self-feeding recursive calls in this
4082 if (src
->val
== dest_val
)
4085 struct ipcp_agg_lattice
*aglat
;
4086 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
4088 if (src
->offset
== -1)
4089 return (plats
->itself
.is_single_const ()
4090 && values_equal_for_ipcp_p (src
->val
->value
,
4091 plats
->itself
.values
->value
));
4094 if (plats
->aggs_bottom
|| plats
->aggs_contain_variable
)
4096 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
4097 if (aglat
->offset
== src
->offset
)
4098 return (aglat
->is_single_const ()
4099 && values_equal_for_ipcp_p (src
->val
->value
,
4100 aglat
->values
->value
));
4106 /* Return true if edge CS does bring about the value described by SRC to
4107 DST_VAL of node DEST or its clone for all contexts. */
4110 cgraph_edge_brings_value_p (cgraph_edge
*cs
,
4111 ipcp_value_source
<ipa_polymorphic_call_context
> *src
,
4113 ipcp_value
<ipa_polymorphic_call_context
> *)
4115 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4116 enum availability avail
;
4117 cgraph_node
*real_dest
= cs
->callee
->function_symbol (&avail
);
4119 if (avail
<= AVAIL_INTERPOSABLE
4120 || !same_node_or_its_all_contexts_clone_p (real_dest
, dest
)
4121 || caller_info
->node_dead
)
4126 if (caller_info
->ipcp_orig_node
)
4127 return (caller_info
->known_contexts
.length () > (unsigned) src
->index
)
4128 && values_equal_for_ipcp_p (src
->val
->value
,
4129 caller_info
->known_contexts
[src
->index
]);
4131 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
4133 return plats
->ctxlat
.is_single_const ()
4134 && values_equal_for_ipcp_p (src
->val
->value
,
4135 plats
->ctxlat
.values
->value
);
4138 /* Get the next clone in the linked list of clones of an edge. */
4140 static inline struct cgraph_edge
*
4141 get_next_cgraph_edge_clone (struct cgraph_edge
*cs
)
4143 edge_clone_summary
*s
= edge_clone_summaries
->get (cs
);
4144 return s
!= NULL
? s
->next_clone
: NULL
;
4147 /* Given VAL that is intended for DEST, iterate over all its sources and if any
4148 of them is viable and hot, return true. In that case, for those that still
4149 hold, add their edge frequency and their number into *FREQUENCY and
4150 *CALLER_COUNT respectively. */
4152 template <typename valtype
>
4154 get_info_about_necessary_edges (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
4156 profile_count
*count_sum
, int *caller_count
)
4158 ipcp_value_source
<valtype
> *src
;
4159 int freq
= 0, count
= 0;
4160 profile_count cnt
= profile_count::zero ();
4162 bool non_self_recursive
= false;
4164 for (src
= val
->sources
; src
; src
= src
->next
)
4166 struct cgraph_edge
*cs
= src
->cs
;
4169 if (cgraph_edge_brings_value_p (cs
, src
, dest
, val
))
4172 freq
+= cs
->frequency ();
4173 if (cs
->count
.ipa ().initialized_p ())
4174 cnt
+= cs
->count
.ipa ();
4175 hot
|= cs
->maybe_hot_p ();
4176 if (cs
->caller
!= dest
)
4177 non_self_recursive
= true;
4179 gcc_assert (values_equal_for_ipcp_p (src
->val
->value
,
4182 cs
= get_next_cgraph_edge_clone (cs
);
4186 /* If the only edges bringing a value are self-recursive ones, do not bother
4188 if (!non_self_recursive
)
4193 *caller_count
= count
;
4195 if (!hot
&& IPA_NODE_REF (dest
)->node_within_scc
)
4197 struct cgraph_edge
*cs
;
4199 /* Cold non-SCC source edge could trigger hot recursive execution of
4200 function. Consider the case as hot and rely on following cost model
4201 computation to further select right one. */
4202 for (cs
= dest
->callers
; cs
; cs
= cs
->next_caller
)
4203 if (cs
->caller
== dest
&& cs
->maybe_hot_p ())
4210 /* Return a vector of incoming edges that do bring value VAL to node DEST. It
4211 is assumed their number is known and equal to CALLER_COUNT. */
4213 template <typename valtype
>
4214 static vec
<cgraph_edge
*>
4215 gather_edges_for_value (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
4218 ipcp_value_source
<valtype
> *src
;
4219 vec
<cgraph_edge
*> ret
;
4221 ret
.create (caller_count
);
4222 for (src
= val
->sources
; src
; src
= src
->next
)
4224 struct cgraph_edge
*cs
= src
->cs
;
4227 if (cgraph_edge_brings_value_p (cs
, src
, dest
, val
))
4228 ret
.quick_push (cs
);
4229 cs
= get_next_cgraph_edge_clone (cs
);
4236 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
4237 Return it or NULL if for some reason it cannot be created. */
4239 static struct ipa_replace_map
*
4240 get_replacement_map (class ipa_node_params
*info
, tree value
, int parm_num
)
4242 struct ipa_replace_map
*replace_map
;
4245 replace_map
= ggc_alloc
<ipa_replace_map
> ();
4248 fprintf (dump_file
, " replacing ");
4249 ipa_dump_param (dump_file
, info
, parm_num
);
4251 fprintf (dump_file
, " with const ");
4252 print_generic_expr (dump_file
, value
);
4253 fprintf (dump_file
, "\n");
4255 replace_map
->parm_num
= parm_num
;
4256 replace_map
->new_tree
= value
;
4260 /* Dump new profiling counts */
4263 dump_profile_updates (struct cgraph_node
*orig_node
,
4264 struct cgraph_node
*new_node
)
4266 struct cgraph_edge
*cs
;
4268 fprintf (dump_file
, " setting count of the specialized node to ");
4269 new_node
->count
.dump (dump_file
);
4270 fprintf (dump_file
, "\n");
4271 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
4273 fprintf (dump_file
, " edge to %s has count ",
4274 cs
->callee
->dump_name ());
4275 cs
->count
.dump (dump_file
);
4276 fprintf (dump_file
, "\n");
4279 fprintf (dump_file
, " setting count of the original node to ");
4280 orig_node
->count
.dump (dump_file
);
4281 fprintf (dump_file
, "\n");
4282 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
4284 fprintf (dump_file
, " edge to %s is left with ",
4285 cs
->callee
->dump_name ());
4286 cs
->count
.dump (dump_file
);
4287 fprintf (dump_file
, "\n");
4291 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
4292 their profile information to reflect this. */
4295 update_profiling_info (struct cgraph_node
*orig_node
,
4296 struct cgraph_node
*new_node
)
4298 struct cgraph_edge
*cs
;
4299 struct caller_statistics stats
;
4300 profile_count new_sum
, orig_sum
;
4301 profile_count remainder
, orig_node_count
= orig_node
->count
;
4302 profile_count orig_new_node_count
= new_node
->count
;
4304 if (!(orig_node_count
.ipa () > profile_count::zero ()))
4307 init_caller_stats (&stats
);
4308 orig_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
4310 orig_sum
= stats
.count_sum
;
4311 init_caller_stats (&stats
);
4312 new_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
4314 new_sum
= stats
.count_sum
;
4316 if (orig_node_count
< orig_sum
+ new_sum
)
4320 fprintf (dump_file
, " Problem: node %s has too low count ",
4321 orig_node
->dump_name ());
4322 orig_node_count
.dump (dump_file
);
4323 fprintf (dump_file
, "while the sum of incoming count is ");
4324 (orig_sum
+ new_sum
).dump (dump_file
);
4325 fprintf (dump_file
, "\n");
4328 orig_node_count
= (orig_sum
+ new_sum
).apply_scale (12, 10);
4331 fprintf (dump_file
, " proceeding by pretending it was ");
4332 orig_node_count
.dump (dump_file
);
4333 fprintf (dump_file
, "\n");
4337 remainder
= orig_node_count
.combine_with_ipa_count (orig_node_count
.ipa ()
4340 /* With partial train run we do not want to assume that original's
4341 count is zero whenever we redurect all executed edges to clone.
4342 Simply drop profile to local one in this case. */
4343 if (remainder
.ipa_p () && !remainder
.ipa ().nonzero_p ()
4344 && orig_node
->count
.ipa_p () && orig_node
->count
.ipa ().nonzero_p ()
4345 && flag_profile_partial_training
)
4346 remainder
= remainder
.guessed_local ();
4348 new_sum
= orig_node_count
.combine_with_ipa_count (new_sum
);
4349 new_node
->count
= new_sum
;
4350 orig_node
->count
= remainder
;
4352 profile_count::adjust_for_ipa_scaling (&new_sum
, &orig_new_node_count
);
4353 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
4354 cs
->count
= cs
->count
.apply_scale (new_sum
, orig_new_node_count
);
4355 for (cs
= new_node
->indirect_calls
; cs
; cs
= cs
->next_callee
)
4356 cs
->count
= cs
->count
.apply_scale (new_sum
, orig_new_node_count
);
4358 profile_count::adjust_for_ipa_scaling (&remainder
, &orig_node_count
);
4359 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
4360 cs
->count
= cs
->count
.apply_scale (remainder
, orig_node_count
);
4361 for (cs
= orig_node
->indirect_calls
; cs
; cs
= cs
->next_callee
)
4362 cs
->count
= cs
->count
.apply_scale (remainder
, orig_node_count
);
4365 dump_profile_updates (orig_node
, new_node
);
4368 /* Update the respective profile of specialized NEW_NODE and the original
4369 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
4370 have been redirected to the specialized version. */
4373 update_specialized_profile (struct cgraph_node
*new_node
,
4374 struct cgraph_node
*orig_node
,
4375 profile_count redirected_sum
)
4377 struct cgraph_edge
*cs
;
4378 profile_count new_node_count
, orig_node_count
= orig_node
->count
;
4382 fprintf (dump_file
, " the sum of counts of redirected edges is ");
4383 redirected_sum
.dump (dump_file
);
4384 fprintf (dump_file
, "\n");
4386 if (!(orig_node_count
> profile_count::zero ()))
4389 gcc_assert (orig_node_count
>= redirected_sum
);
4391 new_node_count
= new_node
->count
;
4392 new_node
->count
+= redirected_sum
;
4393 orig_node
->count
-= redirected_sum
;
4395 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
4396 cs
->count
+= cs
->count
.apply_scale (redirected_sum
, new_node_count
);
4398 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
4400 profile_count dec
= cs
->count
.apply_scale (redirected_sum
,
4406 dump_profile_updates (orig_node
, new_node
);
4409 /* Return true if we would like to remove a parameter from NODE when cloning it
4410 with KNOWN_CSTS scalar constants. */
4413 want_remove_some_param_p (cgraph_node
*node
, vec
<tree
> known_csts
)
4415 auto_vec
<bool, 16> surviving
;
4416 bool filled_vec
= false;
4417 ipa_node_params
*info
= IPA_NODE_REF (node
);
4418 int i
, count
= ipa_get_param_count (info
);
4420 for (i
= 0; i
< count
; i
++)
4422 if (!known_csts
[i
] && ipa_is_param_used (info
, i
))
4427 if (!node
->clone
.param_adjustments
)
4429 node
->clone
.param_adjustments
->get_surviving_params (&surviving
);
4432 if (surviving
.length() < (unsigned) i
&& surviving
[i
])
4438 /* Create a specialized version of NODE with known constants in KNOWN_CSTS,
4439 known contexts in KNOWN_CONTEXTS and known aggregate values in AGGVALS and
4440 redirect all edges in CALLERS to it. */
4442 static struct cgraph_node
*
4443 create_specialized_node (struct cgraph_node
*node
,
4444 vec
<tree
> known_csts
,
4445 vec
<ipa_polymorphic_call_context
> known_contexts
,
4446 struct ipa_agg_replacement_value
*aggvals
,
4447 vec
<cgraph_edge
*> callers
)
4449 class ipa_node_params
*new_info
, *info
= IPA_NODE_REF (node
);
4450 vec
<ipa_replace_map
*, va_gc
> *replace_trees
= NULL
;
4451 vec
<ipa_adjusted_param
, va_gc
> *new_params
= NULL
;
4452 struct ipa_agg_replacement_value
*av
;
4453 struct cgraph_node
*new_node
;
4454 int i
, count
= ipa_get_param_count (info
);
4455 ipa_param_adjustments
*old_adjustments
= node
->clone
.param_adjustments
;
4456 ipa_param_adjustments
*new_adjustments
;
4457 gcc_assert (!info
->ipcp_orig_node
);
4458 gcc_assert (node
->can_change_signature
4459 || !old_adjustments
);
4461 if (old_adjustments
)
4463 /* At the moment all IPA optimizations should use the number of
4464 parameters of the prevailing decl as the m_always_copy_start.
4465 Handling any other value would complicate the code below, so for the
4466 time bing let's only assert it is so. */
4467 gcc_assert (old_adjustments
->m_always_copy_start
== count
4468 || old_adjustments
->m_always_copy_start
< 0);
4469 int old_adj_count
= vec_safe_length (old_adjustments
->m_adj_params
);
4470 for (i
= 0; i
< old_adj_count
; i
++)
4472 ipa_adjusted_param
*old_adj
= &(*old_adjustments
->m_adj_params
)[i
];
4473 if (!node
->can_change_signature
4474 || old_adj
->op
!= IPA_PARAM_OP_COPY
4475 || (!known_csts
[old_adj
->base_index
]
4476 && ipa_is_param_used (info
, old_adj
->base_index
)))
4478 ipa_adjusted_param new_adj
= *old_adj
;
4480 new_adj
.prev_clone_adjustment
= true;
4481 new_adj
.prev_clone_index
= i
;
4482 vec_safe_push (new_params
, new_adj
);
4485 bool skip_return
= old_adjustments
->m_skip_return
;
4486 new_adjustments
= (new (ggc_alloc
<ipa_param_adjustments
> ())
4487 ipa_param_adjustments (new_params
, count
,
4490 else if (node
->can_change_signature
4491 && want_remove_some_param_p (node
, known_csts
))
4493 ipa_adjusted_param adj
;
4494 memset (&adj
, 0, sizeof (adj
));
4495 adj
.op
= IPA_PARAM_OP_COPY
;
4496 for (i
= 0; i
< count
; i
++)
4497 if (!known_csts
[i
] && ipa_is_param_used (info
, i
))
4500 adj
.prev_clone_index
= i
;
4501 vec_safe_push (new_params
, adj
);
4503 new_adjustments
= (new (ggc_alloc
<ipa_param_adjustments
> ())
4504 ipa_param_adjustments (new_params
, count
, false));
4507 new_adjustments
= NULL
;
4509 replace_trees
= vec_safe_copy (node
->clone
.tree_map
);
4510 for (i
= 0; i
< count
; i
++)
4512 tree t
= known_csts
[i
];
4515 struct ipa_replace_map
*replace_map
;
4517 gcc_checking_assert (TREE_CODE (t
) != TREE_BINFO
);
4518 replace_map
= get_replacement_map (info
, t
, i
);
4520 vec_safe_push (replace_trees
, replace_map
);
4523 auto_vec
<cgraph_edge
*, 2> self_recursive_calls
;
4524 for (i
= callers
.length () - 1; i
>= 0; i
--)
4526 cgraph_edge
*cs
= callers
[i
];
4527 if (cs
->caller
== node
)
4529 self_recursive_calls
.safe_push (cs
);
4530 callers
.unordered_remove (i
);
4534 unsigned &suffix_counter
= clone_num_suffixes
->get_or_insert (
4535 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (
4537 new_node
= node
->create_virtual_clone (callers
, replace_trees
,
4538 new_adjustments
, "constprop",
4542 bool have_self_recursive_calls
= !self_recursive_calls
.is_empty ();
4543 for (unsigned j
= 0; j
< self_recursive_calls
.length (); j
++)
4545 cgraph_edge
*cs
= get_next_cgraph_edge_clone (self_recursive_calls
[j
]);
4546 /* Cloned edges can disappear during cloning as speculation can be
4547 resolved, check that we have one and that it comes from the last
4549 if (cs
&& cs
->caller
== new_node
)
4550 cs
->redirect_callee_duplicating_thunks (new_node
);
4551 /* Any future code that would make more than one clone of an outgoing
4552 edge would confuse this mechanism, so let's check that does not
4554 gcc_checking_assert (!cs
4555 || !get_next_cgraph_edge_clone (cs
)
4556 || get_next_cgraph_edge_clone (cs
)->caller
!= new_node
);
4558 if (have_self_recursive_calls
)
4559 new_node
->expand_all_artificial_thunks ();
4561 ipa_set_node_agg_value_chain (new_node
, aggvals
);
4562 for (av
= aggvals
; av
; av
= av
->next
)
4563 new_node
->maybe_create_reference (av
->value
, NULL
);
4565 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4567 fprintf (dump_file
, " the new node is %s.\n", new_node
->dump_name ());
4568 if (known_contexts
.exists ())
4570 for (i
= 0; i
< count
; i
++)
4571 if (!known_contexts
[i
].useless_p ())
4573 fprintf (dump_file
, " known ctx %i is ", i
);
4574 known_contexts
[i
].dump (dump_file
);
4578 ipa_dump_agg_replacement_values (dump_file
, aggvals
);
4580 ipa_check_create_node_params ();
4581 update_profiling_info (node
, new_node
);
4582 new_info
= IPA_NODE_REF (new_node
);
4583 new_info
->ipcp_orig_node
= node
;
4584 new_node
->ipcp_clone
= true;
4585 new_info
->known_csts
= known_csts
;
4586 new_info
->known_contexts
= known_contexts
;
4588 ipcp_discover_new_direct_edges (new_node
, known_csts
, known_contexts
, aggvals
);
4594 /* Return true, if JFUNC, which describes a i-th parameter of call CS, is a
4595 simple no-operation pass-through function to itself. */
4598 self_recursive_pass_through_p (cgraph_edge
*cs
, ipa_jump_func
*jfunc
, int i
)
4600 enum availability availability
;
4601 if (cs
->caller
== cs
->callee
->function_symbol (&availability
)
4602 && availability
> AVAIL_INTERPOSABLE
4603 && jfunc
->type
== IPA_JF_PASS_THROUGH
4604 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
4605 && ipa_get_jf_pass_through_formal_id (jfunc
) == i
)
4610 /* Return true, if JFUNC, which describes a part of an aggregate represented
4611 or pointed to by the i-th parameter of call CS, is a simple no-operation
4612 pass-through function to itself. */
4615 self_recursive_agg_pass_through_p (cgraph_edge
*cs
, ipa_agg_jf_item
*jfunc
,
4618 enum availability availability
;
4619 if (cs
->caller
== cs
->callee
->function_symbol (&availability
)
4620 && availability
> AVAIL_INTERPOSABLE
4621 && jfunc
->jftype
== IPA_JF_LOAD_AGG
4622 && jfunc
->offset
== jfunc
->value
.load_agg
.offset
4623 && jfunc
->value
.pass_through
.operation
== NOP_EXPR
4624 && jfunc
->value
.pass_through
.formal_id
== i
)
4629 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
4630 KNOWN_CSTS with constants that are also known for all of the CALLERS. */
4633 find_more_scalar_values_for_callers_subset (struct cgraph_node
*node
,
4634 vec
<tree
> known_csts
,
4635 vec
<cgraph_edge
*> callers
)
4637 class ipa_node_params
*info
= IPA_NODE_REF (node
);
4638 int i
, count
= ipa_get_param_count (info
);
4640 for (i
= 0; i
< count
; i
++)
4642 struct cgraph_edge
*cs
;
4643 tree newval
= NULL_TREE
;
4646 tree type
= ipa_get_type (info
, i
);
4648 if (ipa_get_scalar_lat (info
, i
)->bottom
|| known_csts
[i
])
4651 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4653 struct ipa_jump_func
*jump_func
;
4656 if (IPA_NODE_REF (cs
->caller
) && IPA_NODE_REF (cs
->caller
)->node_dead
)
4659 if (!IPA_EDGE_REF (cs
)
4660 || i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
))
4662 && call_passes_through_thunk_p (cs
)))
4667 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
4668 if (self_recursive_pass_through_p (cs
, jump_func
, i
))
4671 t
= ipa_value_from_jfunc (IPA_NODE_REF (cs
->caller
), jump_func
, type
);
4674 && !values_equal_for_ipcp_p (t
, newval
))
4675 || (!first
&& !newval
))
4687 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4689 fprintf (dump_file
, " adding an extra known scalar value ");
4690 print_ipcp_constant_value (dump_file
, newval
);
4691 fprintf (dump_file
, " for ");
4692 ipa_dump_param (dump_file
, info
, i
);
4693 fprintf (dump_file
, "\n");
4696 known_csts
[i
] = newval
;
4701 /* Given a NODE and a subset of its CALLERS, try to populate plank slots in
4702 KNOWN_CONTEXTS with polymorphic contexts that are also known for all of the
4706 find_more_contexts_for_caller_subset (cgraph_node
*node
,
4707 vec
<ipa_polymorphic_call_context
>
4709 vec
<cgraph_edge
*> callers
)
4711 ipa_node_params
*info
= IPA_NODE_REF (node
);
4712 int i
, count
= ipa_get_param_count (info
);
4714 for (i
= 0; i
< count
; i
++)
4718 if (ipa_get_poly_ctx_lat (info
, i
)->bottom
4719 || (known_contexts
->exists ()
4720 && !(*known_contexts
)[i
].useless_p ()))
4723 ipa_polymorphic_call_context newval
;
4727 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4729 if (!IPA_EDGE_REF (cs
)
4730 || i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
)))
4732 ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
),
4734 ipa_polymorphic_call_context ctx
;
4735 ctx
= ipa_context_from_jfunc (IPA_NODE_REF (cs
->caller
), cs
, i
,
4743 newval
.meet_with (ctx
);
4744 if (newval
.useless_p ())
4748 if (!newval
.useless_p ())
4750 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4752 fprintf (dump_file
, " adding an extra known polymorphic "
4754 print_ipcp_constant_value (dump_file
, newval
);
4755 fprintf (dump_file
, " for ");
4756 ipa_dump_param (dump_file
, info
, i
);
4757 fprintf (dump_file
, "\n");
4760 if (!known_contexts
->exists ())
4761 known_contexts
->safe_grow_cleared (ipa_get_param_count (info
));
4762 (*known_contexts
)[i
] = newval
;
4768 /* Go through PLATS and create a vector of values consisting of values and
4769 offsets (minus OFFSET) of lattices that contain only a single value. */
4771 static vec
<ipa_agg_value
>
4772 copy_plats_to_inter (class ipcp_param_lattices
*plats
, HOST_WIDE_INT offset
)
4774 vec
<ipa_agg_value
> res
= vNULL
;
4776 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
4779 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
4780 if (aglat
->is_single_const ())
4782 struct ipa_agg_value ti
;
4783 ti
.offset
= aglat
->offset
- offset
;
4784 ti
.value
= aglat
->values
->value
;
4790 /* Intersect all values in INTER with single value lattices in PLATS (while
4791 subtracting OFFSET). */
4794 intersect_with_plats (class ipcp_param_lattices
*plats
,
4795 vec
<ipa_agg_value
> *inter
,
4796 HOST_WIDE_INT offset
)
4798 struct ipcp_agg_lattice
*aglat
;
4799 struct ipa_agg_value
*item
;
4802 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
4808 aglat
= plats
->aggs
;
4809 FOR_EACH_VEC_ELT (*inter
, k
, item
)
4816 if (aglat
->offset
- offset
> item
->offset
)
4818 if (aglat
->offset
- offset
== item
->offset
)
4820 gcc_checking_assert (item
->value
);
4821 if (aglat
->is_single_const ())
4823 tree value
= aglat
->values
->value
;
4825 if (values_equal_for_ipcp_p (item
->value
, value
))
4827 else if (item
->value
== error_mark_node
)
4829 /* Replace unknown place holder value with real one. */
4830 item
->value
= value
;
4836 aglat
= aglat
->next
;
4839 item
->value
= NULL_TREE
;
4843 /* Copy aggregate replacement values of NODE (which is an IPA-CP clone) to the
4844 vector result while subtracting OFFSET from the individual value offsets. */
4846 static vec
<ipa_agg_value
>
4847 agg_replacements_to_vector (struct cgraph_node
*node
, int index
,
4848 HOST_WIDE_INT offset
)
4850 struct ipa_agg_replacement_value
*av
;
4851 vec
<ipa_agg_value
> res
= vNULL
;
4853 for (av
= ipa_get_agg_replacements_for_node (node
); av
; av
= av
->next
)
4854 if (av
->index
== index
4855 && (av
->offset
- offset
) >= 0)
4857 struct ipa_agg_value item
;
4858 gcc_checking_assert (av
->value
);
4859 item
.offset
= av
->offset
- offset
;
4860 item
.value
= av
->value
;
4861 res
.safe_push (item
);
4867 /* Intersect all values in INTER with those that we have already scheduled to
4868 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
4869 (while subtracting OFFSET). */
4872 intersect_with_agg_replacements (struct cgraph_node
*node
, int index
,
4873 vec
<ipa_agg_value
> *inter
,
4874 HOST_WIDE_INT offset
)
4876 struct ipa_agg_replacement_value
*srcvals
;
4877 struct ipa_agg_value
*item
;
4880 srcvals
= ipa_get_agg_replacements_for_node (node
);
4887 FOR_EACH_VEC_ELT (*inter
, i
, item
)
4889 struct ipa_agg_replacement_value
*av
;
4893 for (av
= srcvals
; av
; av
= av
->next
)
4895 gcc_checking_assert (av
->value
);
4896 if (av
->index
== index
4897 && av
->offset
- offset
== item
->offset
)
4899 if (values_equal_for_ipcp_p (item
->value
, av
->value
))
4901 else if (item
->value
== error_mark_node
)
4903 /* Replace place holder value with real one. */
4904 item
->value
= av
->value
;
4911 item
->value
= NULL_TREE
;
4915 /* Intersect values in INTER with aggregate values that come along edge CS to
4916 parameter number INDEX and return it. If INTER does not actually exist yet,
4917 copy all incoming values to it. If we determine we ended up with no values
4918 whatsoever, return a released vector. */
4920 static vec
<ipa_agg_value
>
4921 intersect_aggregates_with_edge (struct cgraph_edge
*cs
, int index
,
4922 vec
<ipa_agg_value
> inter
)
4924 struct ipa_jump_func
*jfunc
;
4925 jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), index
);
4926 if (jfunc
->type
== IPA_JF_PASS_THROUGH
4927 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
4929 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4930 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
4932 if (caller_info
->ipcp_orig_node
)
4934 struct cgraph_node
*orig_node
= caller_info
->ipcp_orig_node
;
4935 class ipcp_param_lattices
*orig_plats
;
4936 orig_plats
= ipa_get_parm_lattices (IPA_NODE_REF (orig_node
),
4938 if (agg_pass_through_permissible_p (orig_plats
, jfunc
))
4940 if (!inter
.exists ())
4941 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, 0);
4943 intersect_with_agg_replacements (cs
->caller
, src_idx
,
4954 class ipcp_param_lattices
*src_plats
;
4955 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
4956 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
4958 /* Currently we do not produce clobber aggregate jump
4959 functions, adjust when we do. */
4960 gcc_checking_assert (!jfunc
->agg
.items
);
4961 if (!inter
.exists ())
4962 inter
= copy_plats_to_inter (src_plats
, 0);
4964 intersect_with_plats (src_plats
, &inter
, 0);
4973 else if (jfunc
->type
== IPA_JF_ANCESTOR
4974 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
4976 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4977 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
4978 class ipcp_param_lattices
*src_plats
;
4979 HOST_WIDE_INT delta
= ipa_get_jf_ancestor_offset (jfunc
);
4981 if (caller_info
->ipcp_orig_node
)
4983 if (!inter
.exists ())
4984 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, delta
);
4986 intersect_with_agg_replacements (cs
->caller
, src_idx
, &inter
,
4991 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
4992 /* Currently we do not produce clobber aggregate jump
4993 functions, adjust when we do. */
4994 gcc_checking_assert (!src_plats
->aggs
|| !jfunc
->agg
.items
);
4995 if (!inter
.exists ())
4996 inter
= copy_plats_to_inter (src_plats
, delta
);
4998 intersect_with_plats (src_plats
, &inter
, delta
);
5001 else if (jfunc
->agg
.items
)
5003 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
5004 struct ipa_agg_value
*item
;
5007 if (!inter
.exists ())
5008 for (unsigned i
= 0; i
< jfunc
->agg
.items
->length (); i
++)
5010 struct ipa_agg_jf_item
*agg_item
= &(*jfunc
->agg
.items
)[i
];
5011 struct ipa_agg_value agg_value
;
5013 if (self_recursive_agg_pass_through_p (cs
, agg_item
, index
))
5015 /* For a self-recursive call, if aggregate jump function is a
5016 simple pass-through, the exact value that it stands for is
5017 not known at this point, which must comes from other call
5018 sites. But we still need to add a place holder in value
5019 sets to indicate it, here we use error_mark_node to
5020 represent the special unknown value, which will be replaced
5021 with real one during later intersecting operations. */
5022 agg_value
.value
= error_mark_node
;
5026 tree value
= ipa_agg_value_from_node (caller_info
, cs
->caller
,
5031 agg_value
.value
= value
;
5034 agg_value
.offset
= agg_item
->offset
;
5035 inter
.safe_push (agg_value
);
5038 FOR_EACH_VEC_ELT (inter
, k
, item
)
5046 while ((unsigned) l
< jfunc
->agg
.items
->length ())
5048 struct ipa_agg_jf_item
*ti
;
5049 ti
= &(*jfunc
->agg
.items
)[l
];
5050 if (ti
->offset
> item
->offset
)
5052 if (ti
->offset
== item
->offset
)
5056 if (self_recursive_agg_pass_through_p (cs
, ti
, index
))
5058 /* A simple aggregate pass-through in self-recursive
5059 call should lead to same value. */
5062 else if ((value
= ipa_agg_value_from_node (caller_info
,
5065 if (values_equal_for_ipcp_p (item
->value
, value
))
5067 else if (item
->value
== error_mark_node
)
5069 /* Replace unknown place holder value with real
5071 item
->value
= value
;
5091 /* Look at edges in CALLERS and collect all known aggregate values that arrive
5092 from all of them. */
5094 static struct ipa_agg_replacement_value
*
5095 find_aggregate_values_for_callers_subset (struct cgraph_node
*node
,
5096 vec
<cgraph_edge
*> callers
)
5098 class ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
5099 struct ipa_agg_replacement_value
*res
;
5100 struct ipa_agg_replacement_value
**tail
= &res
;
5101 struct cgraph_edge
*cs
;
5102 int i
, j
, count
= ipa_get_param_count (dest_info
);
5104 FOR_EACH_VEC_ELT (callers
, j
, cs
)
5106 if (!IPA_EDGE_REF (cs
))
5111 int c
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
5116 for (i
= 0; i
< count
; i
++)
5118 struct cgraph_edge
*cs
;
5119 vec
<ipa_agg_value
> inter
= vNULL
;
5120 struct ipa_agg_value
*item
;
5121 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (dest_info
, i
);
5124 /* Among other things, the following check should deal with all by_ref
5126 if (plats
->aggs_bottom
)
5129 FOR_EACH_VEC_ELT (callers
, j
, cs
)
5131 struct ipa_jump_func
*jfunc
5132 = ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
5133 if (self_recursive_pass_through_p (cs
, jfunc
, i
)
5134 && (!plats
->aggs_by_ref
5135 || ipa_get_jf_pass_through_agg_preserved (jfunc
)))
5137 inter
= intersect_aggregates_with_edge (cs
, i
, inter
);
5139 if (!inter
.exists ())
5143 FOR_EACH_VEC_ELT (inter
, j
, item
)
5145 struct ipa_agg_replacement_value
*v
;
5150 /* All values must be real values, not unknown place holders. */
5151 gcc_assert (item
->value
!= error_mark_node
);
5153 v
= ggc_alloc
<ipa_agg_replacement_value
> ();
5155 v
->offset
= item
->offset
;
5156 v
->value
= item
->value
;
5157 v
->by_ref
= plats
->aggs_by_ref
;
5163 if (inter
.exists ())
5170 /* Determine whether CS also brings all scalar values that the NODE is
5174 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge
*cs
,
5175 struct cgraph_node
*node
)
5177 class ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
5178 int count
= ipa_get_param_count (dest_info
);
5179 class ipa_node_params
*caller_info
;
5180 class ipa_edge_args
*args
;
5183 caller_info
= IPA_NODE_REF (cs
->caller
);
5184 args
= IPA_EDGE_REF (cs
);
5185 for (i
= 0; i
< count
; i
++)
5187 struct ipa_jump_func
*jump_func
;
5190 val
= dest_info
->known_csts
[i
];
5194 if (i
>= ipa_get_cs_argument_count (args
))
5196 jump_func
= ipa_get_ith_jump_func (args
, i
);
5197 t
= ipa_value_from_jfunc (caller_info
, jump_func
,
5198 ipa_get_type (dest_info
, i
));
5199 if (!t
|| !values_equal_for_ipcp_p (val
, t
))
5205 /* Determine whether CS also brings all aggregate values that NODE is
5208 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge
*cs
,
5209 struct cgraph_node
*node
)
5211 class ipa_node_params
*orig_node_info
;
5212 struct ipa_agg_replacement_value
*aggval
;
5215 aggval
= ipa_get_agg_replacements_for_node (node
);
5219 count
= ipa_get_param_count (IPA_NODE_REF (node
));
5220 ec
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
5222 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
5223 if (aggval
->index
>= ec
)
5226 orig_node_info
= IPA_NODE_REF (IPA_NODE_REF (node
)->ipcp_orig_node
);
5228 for (i
= 0; i
< count
; i
++)
5230 class ipcp_param_lattices
*plats
;
5231 bool interesting
= false;
5232 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
5233 if (aggval
->index
== i
)
5241 plats
= ipa_get_parm_lattices (orig_node_info
, aggval
->index
);
5242 if (plats
->aggs_bottom
)
5245 vec
<ipa_agg_value
> values
= intersect_aggregates_with_edge (cs
, i
, vNULL
);
5246 if (!values
.exists ())
5249 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
5250 if (aggval
->index
== i
)
5252 struct ipa_agg_value
*item
;
5255 FOR_EACH_VEC_ELT (values
, j
, item
)
5257 && item
->offset
== av
->offset
5258 && values_equal_for_ipcp_p (item
->value
, av
->value
))
5274 /* Given an original NODE and a VAL for which we have already created a
5275 specialized clone, look whether there are incoming edges that still lead
5276 into the old node but now also bring the requested value and also conform to
5277 all other criteria such that they can be redirected the special node.
5278 This function can therefore redirect the final edge in a SCC. */
5280 template <typename valtype
>
5282 perhaps_add_new_callers (cgraph_node
*node
, ipcp_value
<valtype
> *val
)
5284 ipcp_value_source
<valtype
> *src
;
5285 profile_count redirected_sum
= profile_count::zero ();
5287 for (src
= val
->sources
; src
; src
= src
->next
)
5289 struct cgraph_edge
*cs
= src
->cs
;
5292 if (cgraph_edge_brings_value_p (cs
, src
, node
, val
)
5293 && cgraph_edge_brings_all_scalars_for_node (cs
, val
->spec_node
)
5294 && cgraph_edge_brings_all_agg_vals_for_node (cs
, val
->spec_node
))
5297 fprintf (dump_file
, " - adding an extra caller %s of %s\n",
5298 cs
->caller
->dump_name (),
5299 val
->spec_node
->dump_name ());
5301 cs
->redirect_callee_duplicating_thunks (val
->spec_node
);
5302 val
->spec_node
->expand_all_artificial_thunks ();
5303 if (cs
->count
.ipa ().initialized_p ())
5304 redirected_sum
= redirected_sum
+ cs
->count
.ipa ();
5306 cs
= get_next_cgraph_edge_clone (cs
);
5310 if (redirected_sum
.nonzero_p ())
5311 update_specialized_profile (val
->spec_node
, node
, redirected_sum
);
5314 /* Return true if KNOWN_CONTEXTS contain at least one useful context. */
5317 known_contexts_useful_p (vec
<ipa_polymorphic_call_context
> known_contexts
)
5319 ipa_polymorphic_call_context
*ctx
;
5322 FOR_EACH_VEC_ELT (known_contexts
, i
, ctx
)
5323 if (!ctx
->useless_p ())
5328 /* Return a copy of KNOWN_CSTS if it is not empty, otherwise return vNULL. */
5330 static vec
<ipa_polymorphic_call_context
>
5331 copy_useful_known_contexts (vec
<ipa_polymorphic_call_context
> known_contexts
)
5333 if (known_contexts_useful_p (known_contexts
))
5334 return known_contexts
.copy ();
5339 /* Copy KNOWN_CSTS and modify the copy according to VAL and INDEX. If
5340 non-empty, replace KNOWN_CONTEXTS with its copy too. */
5343 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
5344 vec
<ipa_polymorphic_call_context
> *known_contexts
,
5345 ipcp_value
<tree
> *val
,
5348 *known_csts
= known_csts
->copy ();
5349 *known_contexts
= copy_useful_known_contexts (*known_contexts
);
5350 (*known_csts
)[index
] = val
->value
;
5353 /* Replace KNOWN_CSTS with its copy. Also copy KNOWN_CONTEXTS and modify the
5354 copy according to VAL and INDEX. */
5357 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
5358 vec
<ipa_polymorphic_call_context
> *known_contexts
,
5359 ipcp_value
<ipa_polymorphic_call_context
> *val
,
5362 *known_csts
= known_csts
->copy ();
5363 *known_contexts
= known_contexts
->copy ();
5364 (*known_contexts
)[index
] = val
->value
;
5367 /* Return true if OFFSET indicates this was not an aggregate value or there is
5368 a replacement equivalent to VALUE, INDEX and OFFSET among those in the
5372 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*aggvals
,
5373 int index
, HOST_WIDE_INT offset
, tree value
)
5380 if (aggvals
->index
== index
5381 && aggvals
->offset
== offset
5382 && values_equal_for_ipcp_p (aggvals
->value
, value
))
5384 aggvals
= aggvals
->next
;
5389 /* Return true if offset is minus one because source of a polymorphic context
5390 cannot be an aggregate value. */
5393 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*,
5394 int , HOST_WIDE_INT offset
,
5395 ipa_polymorphic_call_context
)
5397 return offset
== -1;
5400 /* Decide whether to create a special version of NODE for value VAL of parameter
5401 at the given INDEX. If OFFSET is -1, the value is for the parameter itself,
5402 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS,
5403 KNOWN_CONTEXTS and KNOWN_AGGS describe the other already known values. */
5405 template <typename valtype
>
5407 decide_about_value (struct cgraph_node
*node
, int index
, HOST_WIDE_INT offset
,
5408 ipcp_value
<valtype
> *val
, vec
<tree
> known_csts
,
5409 vec
<ipa_polymorphic_call_context
> known_contexts
)
5411 struct ipa_agg_replacement_value
*aggvals
;
5412 int freq_sum
, caller_count
;
5413 profile_count count_sum
;
5414 vec
<cgraph_edge
*> callers
;
5418 perhaps_add_new_callers (node
, val
);
5421 else if (val
->local_size_cost
+ overall_size
> get_max_overall_size (node
))
5423 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5424 fprintf (dump_file
, " Ignoring candidate value because "
5425 "maximum unit size would be reached with %li.\n",
5426 val
->local_size_cost
+ overall_size
);
5429 else if (!get_info_about_necessary_edges (val
, node
, &freq_sum
, &count_sum
,
5433 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5435 fprintf (dump_file
, " - considering value ");
5436 print_ipcp_constant_value (dump_file
, val
->value
);
5437 fprintf (dump_file
, " for ");
5438 ipa_dump_param (dump_file
, IPA_NODE_REF (node
), index
);
5440 fprintf (dump_file
, ", offset: " HOST_WIDE_INT_PRINT_DEC
, offset
);
5441 fprintf (dump_file
, " (caller_count: %i)\n", caller_count
);
5444 if (!good_cloning_opportunity_p (node
, val
->local_time_benefit
,
5445 freq_sum
, count_sum
,
5446 val
->local_size_cost
)
5447 && !good_cloning_opportunity_p (node
,
5448 val
->local_time_benefit
5449 + val
->prop_time_benefit
,
5450 freq_sum
, count_sum
,
5451 val
->local_size_cost
5452 + val
->prop_size_cost
))
5456 fprintf (dump_file
, " Creating a specialized node of %s.\n",
5457 node
->dump_name ());
5459 callers
= gather_edges_for_value (val
, node
, caller_count
);
5461 modify_known_vectors_with_val (&known_csts
, &known_contexts
, val
, index
);
5464 known_csts
= known_csts
.copy ();
5465 known_contexts
= copy_useful_known_contexts (known_contexts
);
5467 find_more_scalar_values_for_callers_subset (node
, known_csts
, callers
);
5468 find_more_contexts_for_caller_subset (node
, &known_contexts
, callers
);
5469 aggvals
= find_aggregate_values_for_callers_subset (node
, callers
);
5470 gcc_checking_assert (ipcp_val_agg_replacement_ok_p (aggvals
, index
,
5471 offset
, val
->value
));
5472 val
->spec_node
= create_specialized_node (node
, known_csts
, known_contexts
,
5474 overall_size
+= val
->local_size_cost
;
5476 /* TODO: If for some lattice there is only one other known value
5477 left, make a special node for it too. */
5482 /* Decide whether and what specialized clones of NODE should be created. */
5485 decide_whether_version_node (struct cgraph_node
*node
)
5487 class ipa_node_params
*info
= IPA_NODE_REF (node
);
5488 int i
, count
= ipa_get_param_count (info
);
5489 vec
<tree
> known_csts
;
5490 vec
<ipa_polymorphic_call_context
> known_contexts
;
5496 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5497 fprintf (dump_file
, "\nEvaluating opportunities for %s.\n",
5498 node
->dump_name ());
5500 gather_context_independent_values (info
, &known_csts
, &known_contexts
,
5503 for (i
= 0; i
< count
;i
++)
5505 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5506 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
5507 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
5512 ipcp_value
<tree
> *val
;
5513 for (val
= lat
->values
; val
; val
= val
->next
)
5514 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
5518 if (!plats
->aggs_bottom
)
5520 struct ipcp_agg_lattice
*aglat
;
5521 ipcp_value
<tree
> *val
;
5522 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
5523 if (!aglat
->bottom
&& aglat
->values
5524 /* If the following is false, the one value is in
5526 && (plats
->aggs_contain_variable
5527 || !aglat
->is_single_const ()))
5528 for (val
= aglat
->values
; val
; val
= val
->next
)
5529 ret
|= decide_about_value (node
, i
, aglat
->offset
, val
,
5530 known_csts
, known_contexts
);
5534 && known_contexts
[i
].useless_p ())
5536 ipcp_value
<ipa_polymorphic_call_context
> *val
;
5537 for (val
= ctxlat
->values
; val
; val
= val
->next
)
5538 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
5542 info
= IPA_NODE_REF (node
);
5545 if (info
->do_clone_for_all_contexts
)
5547 struct cgraph_node
*clone
;
5548 vec
<cgraph_edge
*> callers
;
5551 fprintf (dump_file
, " - Creating a specialized node of %s "
5552 "for all known contexts.\n", node
->dump_name ());
5554 callers
= node
->collect_callers ();
5555 find_more_scalar_values_for_callers_subset (node
, known_csts
, callers
);
5556 find_more_contexts_for_caller_subset (node
, &known_contexts
, callers
);
5557 ipa_agg_replacement_value
*aggvals
5558 = find_aggregate_values_for_callers_subset (node
, callers
);
5560 if (!known_contexts_useful_p (known_contexts
))
5562 known_contexts
.release ();
5563 known_contexts
= vNULL
;
5565 clone
= create_specialized_node (node
, known_csts
, known_contexts
,
5567 info
= IPA_NODE_REF (node
);
5568 info
->do_clone_for_all_contexts
= false;
5569 IPA_NODE_REF (clone
)->is_all_contexts_clone
= true;
5574 known_csts
.release ();
5575 known_contexts
.release ();
5581 /* Transitively mark all callees of NODE within the same SCC as not dead. */
5584 spread_undeadness (struct cgraph_node
*node
)
5586 struct cgraph_edge
*cs
;
5588 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
5589 if (ipa_edge_within_scc (cs
))
5591 struct cgraph_node
*callee
;
5592 class ipa_node_params
*info
;
5594 callee
= cs
->callee
->function_symbol (NULL
);
5595 info
= IPA_NODE_REF (callee
);
5597 if (info
&& info
->node_dead
)
5599 info
->node_dead
= 0;
5600 spread_undeadness (callee
);
5605 /* Return true if NODE has a caller from outside of its SCC that is not
5606 dead. Worker callback for cgraph_for_node_and_aliases. */
5609 has_undead_caller_from_outside_scc_p (struct cgraph_node
*node
,
5610 void *data ATTRIBUTE_UNUSED
)
5612 struct cgraph_edge
*cs
;
5614 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
5615 if (cs
->caller
->thunk
.thunk_p
5616 && cs
->caller
->call_for_symbol_thunks_and_aliases
5617 (has_undead_caller_from_outside_scc_p
, NULL
, true))
5619 else if (!ipa_edge_within_scc (cs
)
5620 && !IPA_NODE_REF (cs
->caller
)->node_dead
)
5626 /* Identify nodes within the same SCC as NODE which are no longer needed
5627 because of new clones and will be removed as unreachable. */
5630 identify_dead_nodes (struct cgraph_node
*node
)
5632 struct cgraph_node
*v
;
5633 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
5636 && !v
->call_for_symbol_thunks_and_aliases
5637 (has_undead_caller_from_outside_scc_p
, NULL
, true))
5638 IPA_NODE_REF (v
)->node_dead
= 1;
5640 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
5641 if (IPA_NODE_REF (v
) && !IPA_NODE_REF (v
)->node_dead
)
5642 spread_undeadness (v
);
5644 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5646 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
5647 if (IPA_NODE_REF (v
) && IPA_NODE_REF (v
)->node_dead
)
5648 fprintf (dump_file
, " Marking node as dead: %s.\n", v
->dump_name ());
5652 /* The decision stage. Iterate over the topological order of call graph nodes
5653 TOPO and make specialized clones if deemed beneficial. */
5656 ipcp_decision_stage (class ipa_topo_info
*topo
)
5661 fprintf (dump_file
, "\nIPA decision stage:\n\n");
5663 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
5665 struct cgraph_node
*node
= topo
->order
[i
];
5666 bool change
= false, iterate
= true;
5670 struct cgraph_node
*v
;
5672 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
5673 if (v
->has_gimple_body_p ()
5674 && ipcp_versionable_function_p (v
))
5675 iterate
|= decide_whether_version_node (v
);
5680 identify_dead_nodes (node
);
5684 /* Look up all the bits information that we have discovered and copy it over
5685 to the transformation summary. */
5688 ipcp_store_bits_results (void)
5692 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5694 ipa_node_params
*info
= IPA_NODE_REF (node
);
5695 bool dumped_sth
= false;
5696 bool found_useful_result
= false;
5698 if (!opt_for_fn (node
->decl
, flag_ipa_bit_cp
) || !info
)
5701 fprintf (dump_file
, "Not considering %s for ipa bitwise propagation "
5702 "; -fipa-bit-cp: disabled.\n",
5703 node
->dump_name ());
5707 if (info
->ipcp_orig_node
)
5708 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
5709 if (!info
->lattices
)
5710 /* Newly expanded artificial thunks do not have lattices. */
5713 unsigned count
= ipa_get_param_count (info
);
5714 for (unsigned i
= 0; i
< count
; i
++)
5716 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5717 if (plats
->bits_lattice
.constant_p ())
5719 found_useful_result
= true;
5724 if (!found_useful_result
)
5727 ipcp_transformation_initialize ();
5728 ipcp_transformation
*ts
= ipcp_transformation_sum
->get_create (node
);
5729 vec_safe_reserve_exact (ts
->bits
, count
);
5731 for (unsigned i
= 0; i
< count
; i
++)
5733 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5736 if (plats
->bits_lattice
.constant_p ())
5738 = ipa_get_ipa_bits_for_value (plats
->bits_lattice
.get_value (),
5739 plats
->bits_lattice
.get_mask ());
5743 ts
->bits
->quick_push (jfbits
);
5744 if (!dump_file
|| !jfbits
)
5748 fprintf (dump_file
, "Propagated bits info for function %s:\n",
5749 node
->dump_name ());
5752 fprintf (dump_file
, " param %i: value = ", i
);
5753 print_hex (jfbits
->value
, dump_file
);
5754 fprintf (dump_file
, ", mask = ");
5755 print_hex (jfbits
->mask
, dump_file
);
5756 fprintf (dump_file
, "\n");
5761 /* Look up all VR information that we have discovered and copy it over
5762 to the transformation summary. */
5765 ipcp_store_vr_results (void)
5769 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5771 ipa_node_params
*info
= IPA_NODE_REF (node
);
5772 bool found_useful_result
= false;
5774 if (!info
|| !opt_for_fn (node
->decl
, flag_ipa_vrp
))
5777 fprintf (dump_file
, "Not considering %s for VR discovery "
5778 "and propagate; -fipa-ipa-vrp: disabled.\n",
5779 node
->dump_name ());
5783 if (info
->ipcp_orig_node
)
5784 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
5785 if (!info
->lattices
)
5786 /* Newly expanded artificial thunks do not have lattices. */
5789 unsigned count
= ipa_get_param_count (info
);
5790 for (unsigned i
= 0; i
< count
; i
++)
5792 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5793 if (!plats
->m_value_range
.bottom_p ()
5794 && !plats
->m_value_range
.top_p ())
5796 found_useful_result
= true;
5800 if (!found_useful_result
)
5803 ipcp_transformation_initialize ();
5804 ipcp_transformation
*ts
= ipcp_transformation_sum
->get_create (node
);
5805 vec_safe_reserve_exact (ts
->m_vr
, count
);
5807 for (unsigned i
= 0; i
< count
; i
++)
5809 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5812 if (!plats
->m_value_range
.bottom_p ()
5813 && !plats
->m_value_range
.top_p ())
5816 vr
.type
= plats
->m_value_range
.m_vr
.kind ();
5817 vr
.min
= wi::to_wide (plats
->m_value_range
.m_vr
.min ());
5818 vr
.max
= wi::to_wide (plats
->m_value_range
.m_vr
.max ());
5823 vr
.type
= VR_VARYING
;
5824 vr
.min
= vr
.max
= wi::zero (INT_TYPE_SIZE
);
5826 ts
->m_vr
->quick_push (vr
);
5831 /* The IPCP driver. */
5836 class ipa_topo_info topo
;
5838 if (edge_clone_summaries
== NULL
)
5839 edge_clone_summaries
= new edge_clone_summary_t (symtab
);
5841 ipa_check_create_node_params ();
5842 ipa_check_create_edge_args ();
5843 clone_num_suffixes
= new hash_map
<const char *, unsigned>;
5847 fprintf (dump_file
, "\nIPA structures before propagation:\n");
5848 if (dump_flags
& TDF_DETAILS
)
5849 ipa_print_all_params (dump_file
);
5850 ipa_print_all_jump_functions (dump_file
);
5853 /* Topological sort. */
5854 build_toporder_info (&topo
);
5855 /* Do the interprocedural propagation. */
5856 ipcp_propagate_stage (&topo
);
5857 /* Decide what constant propagation and cloning should be performed. */
5858 ipcp_decision_stage (&topo
);
5859 /* Store results of bits propagation. */
5860 ipcp_store_bits_results ();
5861 /* Store results of value range propagation. */
5862 ipcp_store_vr_results ();
5864 /* Free all IPCP structures. */
5865 delete clone_num_suffixes
;
5866 free_toporder_info (&topo
);
5867 delete edge_clone_summaries
;
5868 edge_clone_summaries
= NULL
;
5869 ipa_free_all_structures_after_ipa_cp ();
5871 fprintf (dump_file
, "\nIPA constant propagation end\n");
5875 /* Initialization and computation of IPCP data structures. This is the initial
5876 intraprocedural analysis of functions, which gathers information to be
5877 propagated later on. */
5880 ipcp_generate_summary (void)
5882 struct cgraph_node
*node
;
5885 fprintf (dump_file
, "\nIPA constant propagation start:\n");
5886 ipa_register_cgraph_hooks ();
5888 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5889 ipa_analyze_node (node
);
5892 /* Write ipcp summary for nodes in SET. */
5895 ipcp_write_summary (void)
5897 ipa_prop_write_jump_functions ();
5900 /* Read ipcp summary. */
5903 ipcp_read_summary (void)
5905 ipa_prop_read_jump_functions ();
5910 const pass_data pass_data_ipa_cp
=
5912 IPA_PASS
, /* type */
5914 OPTGROUP_NONE
, /* optinfo_flags */
5915 TV_IPA_CONSTANT_PROP
, /* tv_id */
5916 0, /* properties_required */
5917 0, /* properties_provided */
5918 0, /* properties_destroyed */
5919 0, /* todo_flags_start */
5920 ( TODO_dump_symtab
| TODO_remove_functions
), /* todo_flags_finish */
5923 class pass_ipa_cp
: public ipa_opt_pass_d
5926 pass_ipa_cp (gcc::context
*ctxt
)
5927 : ipa_opt_pass_d (pass_data_ipa_cp
, ctxt
,
5928 ipcp_generate_summary
, /* generate_summary */
5929 ipcp_write_summary
, /* write_summary */
5930 ipcp_read_summary
, /* read_summary */
5931 ipcp_write_transformation_summaries
, /*
5932 write_optimization_summary */
5933 ipcp_read_transformation_summaries
, /*
5934 read_optimization_summary */
5935 NULL
, /* stmt_fixup */
5936 0, /* function_transform_todo_flags_start */
5937 ipcp_transform_function
, /* function_transform */
5938 NULL
) /* variable_transform */
5941 /* opt_pass methods: */
5942 virtual bool gate (function
*)
5944 /* FIXME: We should remove the optimize check after we ensure we never run
5945 IPA passes when not optimizing. */
5946 return (flag_ipa_cp
&& optimize
) || in_lto_p
;
5949 virtual unsigned int execute (function
*) { return ipcp_driver (); }
5951 }; // class pass_ipa_cp
5956 make_pass_ipa_cp (gcc::context
*ctxt
)
5958 return new pass_ipa_cp (ctxt
);
5961 /* Reset all state within ipa-cp.c so that we can rerun the compiler
5962 within the same process. For use by toplev::finalize. */
5965 ipa_cp_c_finalize (void)
5967 max_count
= profile_count::uninitialized ();
5969 orig_overall_size
= 0;
5970 ipcp_free_transformation_sum ();