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
)
1853 if (s
->cs
== cs
&& s
->val
== src_val
)
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
|| !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 cs
= get_next_cgraph_edge_clone (cs
);
4183 /* If the only edges bringing a value are self-recursive ones, do not bother
4185 if (!non_self_recursive
)
4190 *caller_count
= count
;
4192 if (!hot
&& IPA_NODE_REF (dest
)->node_within_scc
)
4194 struct cgraph_edge
*cs
;
4196 /* Cold non-SCC source edge could trigger hot recursive execution of
4197 function. Consider the case as hot and rely on following cost model
4198 computation to further select right one. */
4199 for (cs
= dest
->callers
; cs
; cs
= cs
->next_caller
)
4200 if (cs
->caller
== dest
&& cs
->maybe_hot_p ())
4207 /* Given a NODE, and a set of its CALLERS, try to adjust order of the callers
4208 to let a non-self-recursive caller be the first element. Thus, we can
4209 simplify intersecting operations on values that arrive from all of these
4210 callers, especially when there exists self-recursive call. Return true if
4211 this kind of adjustment is possible. */
4214 adjust_callers_for_value_intersection (vec
<cgraph_edge
*> callers
,
4217 for (unsigned i
= 0; i
< callers
.length (); i
++)
4219 cgraph_edge
*cs
= callers
[i
];
4221 if (cs
->caller
!= node
)
4225 callers
[i
] = callers
[0];
4234 /* Return a vector of incoming edges that do bring value VAL to node DEST. It
4235 is assumed their number is known and equal to CALLER_COUNT. */
4237 template <typename valtype
>
4238 static vec
<cgraph_edge
*>
4239 gather_edges_for_value (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
4242 ipcp_value_source
<valtype
> *src
;
4243 vec
<cgraph_edge
*> ret
;
4245 ret
.create (caller_count
);
4246 for (src
= val
->sources
; src
; src
= src
->next
)
4248 struct cgraph_edge
*cs
= src
->cs
;
4251 if (cgraph_edge_brings_value_p (cs
, src
, dest
, val
))
4252 ret
.quick_push (cs
);
4253 cs
= get_next_cgraph_edge_clone (cs
);
4257 if (caller_count
> 1)
4258 adjust_callers_for_value_intersection (ret
, dest
);
4263 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
4264 Return it or NULL if for some reason it cannot be created. */
4266 static struct ipa_replace_map
*
4267 get_replacement_map (class ipa_node_params
*info
, tree value
, int parm_num
)
4269 struct ipa_replace_map
*replace_map
;
4271 replace_map
= ggc_alloc
<ipa_replace_map
> ();
4274 fprintf (dump_file
, " replacing ");
4275 ipa_dump_param (dump_file
, info
, parm_num
);
4277 fprintf (dump_file
, " with const ");
4278 print_generic_expr (dump_file
, value
);
4279 fprintf (dump_file
, "\n");
4281 replace_map
->parm_num
= parm_num
;
4282 replace_map
->new_tree
= value
;
4286 /* Dump new profiling counts */
4289 dump_profile_updates (struct cgraph_node
*orig_node
,
4290 struct cgraph_node
*new_node
)
4292 struct cgraph_edge
*cs
;
4294 fprintf (dump_file
, " setting count of the specialized node to ");
4295 new_node
->count
.dump (dump_file
);
4296 fprintf (dump_file
, "\n");
4297 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
4299 fprintf (dump_file
, " edge to %s has count ",
4300 cs
->callee
->dump_name ());
4301 cs
->count
.dump (dump_file
);
4302 fprintf (dump_file
, "\n");
4305 fprintf (dump_file
, " setting count of the original node to ");
4306 orig_node
->count
.dump (dump_file
);
4307 fprintf (dump_file
, "\n");
4308 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
4310 fprintf (dump_file
, " edge to %s is left with ",
4311 cs
->callee
->dump_name ());
4312 cs
->count
.dump (dump_file
);
4313 fprintf (dump_file
, "\n");
4317 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
4318 their profile information to reflect this. */
4321 update_profiling_info (struct cgraph_node
*orig_node
,
4322 struct cgraph_node
*new_node
)
4324 struct cgraph_edge
*cs
;
4325 struct caller_statistics stats
;
4326 profile_count new_sum
, orig_sum
;
4327 profile_count remainder
, orig_node_count
= orig_node
->count
;
4328 profile_count orig_new_node_count
= new_node
->count
;
4330 if (!(orig_node_count
.ipa () > profile_count::zero ()))
4333 init_caller_stats (&stats
);
4334 orig_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
4336 orig_sum
= stats
.count_sum
;
4337 init_caller_stats (&stats
);
4338 new_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
4340 new_sum
= stats
.count_sum
;
4342 if (orig_node_count
< orig_sum
+ new_sum
)
4346 fprintf (dump_file
, " Problem: node %s has too low count ",
4347 orig_node
->dump_name ());
4348 orig_node_count
.dump (dump_file
);
4349 fprintf (dump_file
, "while the sum of incoming count is ");
4350 (orig_sum
+ new_sum
).dump (dump_file
);
4351 fprintf (dump_file
, "\n");
4354 orig_node_count
= (orig_sum
+ new_sum
).apply_scale (12, 10);
4357 fprintf (dump_file
, " proceeding by pretending it was ");
4358 orig_node_count
.dump (dump_file
);
4359 fprintf (dump_file
, "\n");
4363 remainder
= orig_node_count
.combine_with_ipa_count (orig_node_count
.ipa ()
4366 /* With partial train run we do not want to assume that original's
4367 count is zero whenever we redurect all executed edges to clone.
4368 Simply drop profile to local one in this case. */
4369 if (remainder
.ipa_p () && !remainder
.ipa ().nonzero_p ()
4370 && orig_node
->count
.ipa_p () && orig_node
->count
.ipa ().nonzero_p ()
4371 && flag_profile_partial_training
)
4372 remainder
= remainder
.guessed_local ();
4374 new_sum
= orig_node_count
.combine_with_ipa_count (new_sum
);
4375 new_node
->count
= new_sum
;
4376 orig_node
->count
= remainder
;
4378 profile_count::adjust_for_ipa_scaling (&new_sum
, &orig_new_node_count
);
4379 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
4380 cs
->count
= cs
->count
.apply_scale (new_sum
, orig_new_node_count
);
4381 for (cs
= new_node
->indirect_calls
; cs
; cs
= cs
->next_callee
)
4382 cs
->count
= cs
->count
.apply_scale (new_sum
, orig_new_node_count
);
4384 profile_count::adjust_for_ipa_scaling (&remainder
, &orig_node_count
);
4385 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
4386 cs
->count
= cs
->count
.apply_scale (remainder
, orig_node_count
);
4387 for (cs
= orig_node
->indirect_calls
; cs
; cs
= cs
->next_callee
)
4388 cs
->count
= cs
->count
.apply_scale (remainder
, orig_node_count
);
4391 dump_profile_updates (orig_node
, new_node
);
4394 /* Update the respective profile of specialized NEW_NODE and the original
4395 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
4396 have been redirected to the specialized version. */
4399 update_specialized_profile (struct cgraph_node
*new_node
,
4400 struct cgraph_node
*orig_node
,
4401 profile_count redirected_sum
)
4403 struct cgraph_edge
*cs
;
4404 profile_count new_node_count
, orig_node_count
= orig_node
->count
;
4408 fprintf (dump_file
, " the sum of counts of redirected edges is ");
4409 redirected_sum
.dump (dump_file
);
4410 fprintf (dump_file
, "\n");
4412 if (!(orig_node_count
> profile_count::zero ()))
4415 gcc_assert (orig_node_count
>= redirected_sum
);
4417 new_node_count
= new_node
->count
;
4418 new_node
->count
+= redirected_sum
;
4419 orig_node
->count
-= redirected_sum
;
4421 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
4422 cs
->count
+= cs
->count
.apply_scale (redirected_sum
, new_node_count
);
4424 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
4426 profile_count dec
= cs
->count
.apply_scale (redirected_sum
,
4432 dump_profile_updates (orig_node
, new_node
);
4435 /* Return true if we would like to remove a parameter from NODE when cloning it
4436 with KNOWN_CSTS scalar constants. */
4439 want_remove_some_param_p (cgraph_node
*node
, vec
<tree
> known_csts
)
4441 auto_vec
<bool, 16> surviving
;
4442 bool filled_vec
= false;
4443 ipa_node_params
*info
= IPA_NODE_REF (node
);
4444 int i
, count
= ipa_get_param_count (info
);
4446 for (i
= 0; i
< count
; i
++)
4448 if (!known_csts
[i
] && ipa_is_param_used (info
, i
))
4453 if (!node
->clone
.param_adjustments
)
4455 node
->clone
.param_adjustments
->get_surviving_params (&surviving
);
4458 if (surviving
.length() < (unsigned) i
&& surviving
[i
])
4464 /* Create a specialized version of NODE with known constants in KNOWN_CSTS,
4465 known contexts in KNOWN_CONTEXTS and known aggregate values in AGGVALS and
4466 redirect all edges in CALLERS to it. */
4468 static struct cgraph_node
*
4469 create_specialized_node (struct cgraph_node
*node
,
4470 vec
<tree
> known_csts
,
4471 vec
<ipa_polymorphic_call_context
> known_contexts
,
4472 struct ipa_agg_replacement_value
*aggvals
,
4473 vec
<cgraph_edge
*> callers
)
4475 class ipa_node_params
*new_info
, *info
= IPA_NODE_REF (node
);
4476 vec
<ipa_replace_map
*, va_gc
> *replace_trees
= NULL
;
4477 vec
<ipa_adjusted_param
, va_gc
> *new_params
= NULL
;
4478 struct ipa_agg_replacement_value
*av
;
4479 struct cgraph_node
*new_node
;
4480 int i
, count
= ipa_get_param_count (info
);
4481 ipa_param_adjustments
*old_adjustments
= node
->clone
.param_adjustments
;
4482 ipa_param_adjustments
*new_adjustments
;
4483 gcc_assert (!info
->ipcp_orig_node
);
4484 gcc_assert (node
->can_change_signature
4485 || !old_adjustments
);
4487 if (old_adjustments
)
4489 /* At the moment all IPA optimizations should use the number of
4490 parameters of the prevailing decl as the m_always_copy_start.
4491 Handling any other value would complicate the code below, so for the
4492 time bing let's only assert it is so. */
4493 gcc_assert (old_adjustments
->m_always_copy_start
== count
4494 || old_adjustments
->m_always_copy_start
< 0);
4495 int old_adj_count
= vec_safe_length (old_adjustments
->m_adj_params
);
4496 for (i
= 0; i
< old_adj_count
; i
++)
4498 ipa_adjusted_param
*old_adj
= &(*old_adjustments
->m_adj_params
)[i
];
4499 if (!node
->can_change_signature
4500 || old_adj
->op
!= IPA_PARAM_OP_COPY
4501 || (!known_csts
[old_adj
->base_index
]
4502 && ipa_is_param_used (info
, old_adj
->base_index
)))
4504 ipa_adjusted_param new_adj
= *old_adj
;
4506 new_adj
.prev_clone_adjustment
= true;
4507 new_adj
.prev_clone_index
= i
;
4508 vec_safe_push (new_params
, new_adj
);
4511 bool skip_return
= old_adjustments
->m_skip_return
;
4512 new_adjustments
= (new (ggc_alloc
<ipa_param_adjustments
> ())
4513 ipa_param_adjustments (new_params
, count
,
4516 else if (node
->can_change_signature
4517 && want_remove_some_param_p (node
, known_csts
))
4519 ipa_adjusted_param adj
;
4520 memset (&adj
, 0, sizeof (adj
));
4521 adj
.op
= IPA_PARAM_OP_COPY
;
4522 for (i
= 0; i
< count
; i
++)
4523 if (!known_csts
[i
] && ipa_is_param_used (info
, i
))
4526 adj
.prev_clone_index
= i
;
4527 vec_safe_push (new_params
, adj
);
4529 new_adjustments
= (new (ggc_alloc
<ipa_param_adjustments
> ())
4530 ipa_param_adjustments (new_params
, count
, false));
4533 new_adjustments
= NULL
;
4535 replace_trees
= vec_safe_copy (node
->clone
.tree_map
);
4536 for (i
= 0; i
< count
; i
++)
4538 tree t
= known_csts
[i
];
4541 struct ipa_replace_map
*replace_map
;
4543 gcc_checking_assert (TREE_CODE (t
) != TREE_BINFO
);
4544 replace_map
= get_replacement_map (info
, t
, i
);
4546 vec_safe_push (replace_trees
, replace_map
);
4549 auto_vec
<cgraph_edge
*, 2> self_recursive_calls
;
4550 for (i
= callers
.length () - 1; i
>= 0; i
--)
4552 cgraph_edge
*cs
= callers
[i
];
4553 if (cs
->caller
== node
)
4555 self_recursive_calls
.safe_push (cs
);
4556 callers
.unordered_remove (i
);
4560 unsigned &suffix_counter
= clone_num_suffixes
->get_or_insert (
4561 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (
4563 new_node
= node
->create_virtual_clone (callers
, replace_trees
,
4564 new_adjustments
, "constprop",
4568 bool have_self_recursive_calls
= !self_recursive_calls
.is_empty ();
4569 for (unsigned j
= 0; j
< self_recursive_calls
.length (); j
++)
4571 cgraph_edge
*cs
= get_next_cgraph_edge_clone (self_recursive_calls
[j
]);
4572 /* Cloned edges can disappear during cloning as speculation can be
4573 resolved, check that we have one and that it comes from the last
4575 if (cs
&& cs
->caller
== new_node
)
4576 cs
->redirect_callee_duplicating_thunks (new_node
);
4577 /* Any future code that would make more than one clone of an outgoing
4578 edge would confuse this mechanism, so let's check that does not
4580 gcc_checking_assert (!cs
4581 || !get_next_cgraph_edge_clone (cs
)
4582 || get_next_cgraph_edge_clone (cs
)->caller
!= new_node
);
4584 if (have_self_recursive_calls
)
4585 new_node
->expand_all_artificial_thunks ();
4587 ipa_set_node_agg_value_chain (new_node
, aggvals
);
4588 for (av
= aggvals
; av
; av
= av
->next
)
4589 new_node
->maybe_create_reference (av
->value
, NULL
);
4591 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4593 fprintf (dump_file
, " the new node is %s.\n", new_node
->dump_name ());
4594 if (known_contexts
.exists ())
4596 for (i
= 0; i
< count
; i
++)
4597 if (!known_contexts
[i
].useless_p ())
4599 fprintf (dump_file
, " known ctx %i is ", i
);
4600 known_contexts
[i
].dump (dump_file
);
4604 ipa_dump_agg_replacement_values (dump_file
, aggvals
);
4606 ipa_check_create_node_params ();
4607 update_profiling_info (node
, new_node
);
4608 new_info
= IPA_NODE_REF (new_node
);
4609 new_info
->ipcp_orig_node
= node
;
4610 new_node
->ipcp_clone
= true;
4611 new_info
->known_csts
= known_csts
;
4612 new_info
->known_contexts
= known_contexts
;
4614 ipcp_discover_new_direct_edges (new_node
, known_csts
, known_contexts
, aggvals
);
4620 /* Return true, if JFUNC, which describes a i-th parameter of call CS, is a
4621 pass-through function to itself. When SIMPLE is true, further check if
4622 JFUNC is a simple no-operation pass-through. */
4625 self_recursive_pass_through_p (cgraph_edge
*cs
, ipa_jump_func
*jfunc
, int i
,
4628 enum availability availability
;
4629 if (cs
->caller
== cs
->callee
->function_symbol (&availability
)
4630 && availability
> AVAIL_INTERPOSABLE
4631 && jfunc
->type
== IPA_JF_PASS_THROUGH
4632 && (!simple
|| ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
4633 && ipa_get_jf_pass_through_formal_id (jfunc
) == i
)
4638 /* Return true, if JFUNC, which describes a part of an aggregate represented
4639 or pointed to by the i-th parameter of call CS, is a pass-through function
4640 to itself. When SIMPLE is true, further check if JFUNC is a simple
4641 no-operation pass-through. */
4644 self_recursive_agg_pass_through_p (cgraph_edge
*cs
, ipa_agg_jf_item
*jfunc
,
4645 int i
, bool simple
= true)
4647 enum availability availability
;
4648 if (cs
->caller
== cs
->callee
->function_symbol (&availability
)
4649 && availability
> AVAIL_INTERPOSABLE
4650 && jfunc
->jftype
== IPA_JF_LOAD_AGG
4651 && jfunc
->offset
== jfunc
->value
.load_agg
.offset
4652 && (!simple
|| jfunc
->value
.pass_through
.operation
== NOP_EXPR
)
4653 && jfunc
->value
.pass_through
.formal_id
== i
4654 && useless_type_conversion_p (jfunc
->value
.load_agg
.type
, jfunc
->type
))
4659 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
4660 KNOWN_CSTS with constants that are also known for all of the CALLERS. */
4663 find_more_scalar_values_for_callers_subset (struct cgraph_node
*node
,
4664 vec
<tree
> known_csts
,
4665 vec
<cgraph_edge
*> callers
)
4667 class ipa_node_params
*info
= IPA_NODE_REF (node
);
4668 int i
, count
= ipa_get_param_count (info
);
4670 for (i
= 0; i
< count
; i
++)
4672 struct cgraph_edge
*cs
;
4673 tree newval
= NULL_TREE
;
4676 tree type
= ipa_get_type (info
, i
);
4678 if (ipa_get_scalar_lat (info
, i
)->bottom
|| known_csts
[i
])
4681 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4683 struct ipa_jump_func
*jump_func
;
4686 if (!IPA_EDGE_REF (cs
)
4687 || i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
))
4689 && call_passes_through_thunk_p (cs
)))
4694 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
4696 /* Besides simple pass-through jump function, arithmetic jump
4697 function could also introduce argument-direct-pass-through for
4698 self-feeding recursive call. For example,
4705 Given that i is 0, recursive propagation via (i & 1) also gets
4707 if (self_recursive_pass_through_p (cs
, jump_func
, i
, false))
4709 gcc_assert (newval
);
4710 t
= ipa_get_jf_arith_result (
4711 ipa_get_jf_pass_through_operation (jump_func
),
4713 ipa_get_jf_pass_through_operand (jump_func
),
4717 t
= ipa_value_from_jfunc (IPA_NODE_REF (cs
->caller
), jump_func
,
4721 && !values_equal_for_ipcp_p (t
, newval
))
4722 || (!first
&& !newval
))
4734 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4736 fprintf (dump_file
, " adding an extra known scalar value ");
4737 print_ipcp_constant_value (dump_file
, newval
);
4738 fprintf (dump_file
, " for ");
4739 ipa_dump_param (dump_file
, info
, i
);
4740 fprintf (dump_file
, "\n");
4743 known_csts
[i
] = newval
;
4748 /* Given a NODE and a subset of its CALLERS, try to populate plank slots in
4749 KNOWN_CONTEXTS with polymorphic contexts that are also known for all of the
4753 find_more_contexts_for_caller_subset (cgraph_node
*node
,
4754 vec
<ipa_polymorphic_call_context
>
4756 vec
<cgraph_edge
*> callers
)
4758 ipa_node_params
*info
= IPA_NODE_REF (node
);
4759 int i
, count
= ipa_get_param_count (info
);
4761 for (i
= 0; i
< count
; i
++)
4765 if (ipa_get_poly_ctx_lat (info
, i
)->bottom
4766 || (known_contexts
->exists ()
4767 && !(*known_contexts
)[i
].useless_p ()))
4770 ipa_polymorphic_call_context newval
;
4774 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4776 if (!IPA_EDGE_REF (cs
)
4777 || i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
)))
4779 ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
),
4781 ipa_polymorphic_call_context ctx
;
4782 ctx
= ipa_context_from_jfunc (IPA_NODE_REF (cs
->caller
), cs
, i
,
4790 newval
.meet_with (ctx
);
4791 if (newval
.useless_p ())
4795 if (!newval
.useless_p ())
4797 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4799 fprintf (dump_file
, " adding an extra known polymorphic "
4801 print_ipcp_constant_value (dump_file
, newval
);
4802 fprintf (dump_file
, " for ");
4803 ipa_dump_param (dump_file
, info
, i
);
4804 fprintf (dump_file
, "\n");
4807 if (!known_contexts
->exists ())
4808 known_contexts
->safe_grow_cleared (ipa_get_param_count (info
));
4809 (*known_contexts
)[i
] = newval
;
4815 /* Go through PLATS and create a vector of values consisting of values and
4816 offsets (minus OFFSET) of lattices that contain only a single value. */
4818 static vec
<ipa_agg_value
>
4819 copy_plats_to_inter (class ipcp_param_lattices
*plats
, HOST_WIDE_INT offset
)
4821 vec
<ipa_agg_value
> res
= vNULL
;
4823 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
4826 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
4827 if (aglat
->is_single_const ())
4829 struct ipa_agg_value ti
;
4830 ti
.offset
= aglat
->offset
- offset
;
4831 ti
.value
= aglat
->values
->value
;
4837 /* Intersect all values in INTER with single value lattices in PLATS (while
4838 subtracting OFFSET). */
4841 intersect_with_plats (class ipcp_param_lattices
*plats
,
4842 vec
<ipa_agg_value
> *inter
,
4843 HOST_WIDE_INT offset
)
4845 struct ipcp_agg_lattice
*aglat
;
4846 struct ipa_agg_value
*item
;
4849 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
4855 aglat
= plats
->aggs
;
4856 FOR_EACH_VEC_ELT (*inter
, k
, item
)
4863 if (aglat
->offset
- offset
> item
->offset
)
4865 if (aglat
->offset
- offset
== item
->offset
)
4867 if (aglat
->is_single_const ())
4869 tree value
= aglat
->values
->value
;
4871 if (values_equal_for_ipcp_p (item
->value
, value
))
4876 aglat
= aglat
->next
;
4879 item
->value
= NULL_TREE
;
4883 /* Copy aggregate replacement values of NODE (which is an IPA-CP clone) to the
4884 vector result while subtracting OFFSET from the individual value offsets. */
4886 static vec
<ipa_agg_value
>
4887 agg_replacements_to_vector (struct cgraph_node
*node
, int index
,
4888 HOST_WIDE_INT offset
)
4890 struct ipa_agg_replacement_value
*av
;
4891 vec
<ipa_agg_value
> res
= vNULL
;
4893 for (av
= ipa_get_agg_replacements_for_node (node
); av
; av
= av
->next
)
4894 if (av
->index
== index
4895 && (av
->offset
- offset
) >= 0)
4897 struct ipa_agg_value item
;
4898 gcc_checking_assert (av
->value
);
4899 item
.offset
= av
->offset
- offset
;
4900 item
.value
= av
->value
;
4901 res
.safe_push (item
);
4907 /* Intersect all values in INTER with those that we have already scheduled to
4908 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
4909 (while subtracting OFFSET). */
4912 intersect_with_agg_replacements (struct cgraph_node
*node
, int index
,
4913 vec
<ipa_agg_value
> *inter
,
4914 HOST_WIDE_INT offset
)
4916 struct ipa_agg_replacement_value
*srcvals
;
4917 struct ipa_agg_value
*item
;
4920 srcvals
= ipa_get_agg_replacements_for_node (node
);
4927 FOR_EACH_VEC_ELT (*inter
, i
, item
)
4929 struct ipa_agg_replacement_value
*av
;
4933 for (av
= srcvals
; av
; av
= av
->next
)
4935 gcc_checking_assert (av
->value
);
4936 if (av
->index
== index
4937 && av
->offset
- offset
== item
->offset
)
4939 if (values_equal_for_ipcp_p (item
->value
, av
->value
))
4945 item
->value
= NULL_TREE
;
4949 /* Intersect values in INTER with aggregate values that come along edge CS to
4950 parameter number INDEX and return it. If INTER does not actually exist yet,
4951 copy all incoming values to it. If we determine we ended up with no values
4952 whatsoever, return a released vector. */
4954 static vec
<ipa_agg_value
>
4955 intersect_aggregates_with_edge (struct cgraph_edge
*cs
, int index
,
4956 vec
<ipa_agg_value
> inter
)
4958 struct ipa_jump_func
*jfunc
;
4959 jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), index
);
4960 if (jfunc
->type
== IPA_JF_PASS_THROUGH
4961 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
4963 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4964 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
4966 if (caller_info
->ipcp_orig_node
)
4968 struct cgraph_node
*orig_node
= caller_info
->ipcp_orig_node
;
4969 class ipcp_param_lattices
*orig_plats
;
4970 orig_plats
= ipa_get_parm_lattices (IPA_NODE_REF (orig_node
),
4972 if (agg_pass_through_permissible_p (orig_plats
, jfunc
))
4974 if (!inter
.exists ())
4975 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, 0);
4977 intersect_with_agg_replacements (cs
->caller
, src_idx
,
4988 class ipcp_param_lattices
*src_plats
;
4989 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
4990 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
4992 /* Currently we do not produce clobber aggregate jump
4993 functions, adjust when we do. */
4994 gcc_checking_assert (!jfunc
->agg
.items
);
4995 if (!inter
.exists ())
4996 inter
= copy_plats_to_inter (src_plats
, 0);
4998 intersect_with_plats (src_plats
, &inter
, 0);
5007 else if (jfunc
->type
== IPA_JF_ANCESTOR
5008 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
5010 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
5011 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
5012 class ipcp_param_lattices
*src_plats
;
5013 HOST_WIDE_INT delta
= ipa_get_jf_ancestor_offset (jfunc
);
5015 if (caller_info
->ipcp_orig_node
)
5017 if (!inter
.exists ())
5018 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, delta
);
5020 intersect_with_agg_replacements (cs
->caller
, src_idx
, &inter
,
5025 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
5026 /* Currently we do not produce clobber aggregate jump
5027 functions, adjust when we do. */
5028 gcc_checking_assert (!src_plats
->aggs
|| !jfunc
->agg
.items
);
5029 if (!inter
.exists ())
5030 inter
= copy_plats_to_inter (src_plats
, delta
);
5032 intersect_with_plats (src_plats
, &inter
, delta
);
5035 else if (jfunc
->agg
.items
)
5037 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
5038 struct ipa_agg_value
*item
;
5041 if (!inter
.exists ())
5042 for (unsigned i
= 0; i
< jfunc
->agg
.items
->length (); i
++)
5044 struct ipa_agg_jf_item
*agg_item
= &(*jfunc
->agg
.items
)[i
];
5045 tree value
= ipa_agg_value_from_node (caller_info
, cs
->caller
,
5049 struct ipa_agg_value agg_value
;
5051 agg_value
.value
= value
;
5052 agg_value
.offset
= agg_item
->offset
;
5053 inter
.safe_push (agg_value
);
5057 FOR_EACH_VEC_ELT (inter
, k
, item
)
5065 while ((unsigned) l
< jfunc
->agg
.items
->length ())
5067 struct ipa_agg_jf_item
*ti
;
5068 ti
= &(*jfunc
->agg
.items
)[l
];
5069 if (ti
->offset
> item
->offset
)
5071 if (ti
->offset
== item
->offset
)
5075 /* Besides simple pass-through aggregate jump function,
5076 arithmetic aggregate jump function could also bring
5077 same aggregate value as parameter passed-in for
5078 self-feeding recursive call. For example,
5086 Given that *i is 0, recursive propagation via (*i & 1)
5088 if (self_recursive_agg_pass_through_p (cs
, ti
, index
,
5090 value
= ipa_get_jf_arith_result (
5091 ti
->value
.pass_through
.operation
,
5093 ti
->value
.pass_through
.operand
,
5096 value
= ipa_agg_value_from_node (caller_info
,
5099 if (value
&& values_equal_for_ipcp_p (item
->value
, value
))
5117 /* Look at edges in CALLERS and collect all known aggregate values that arrive
5118 from all of them. */
5120 static struct ipa_agg_replacement_value
*
5121 find_aggregate_values_for_callers_subset (struct cgraph_node
*node
,
5122 vec
<cgraph_edge
*> callers
)
5124 class ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
5125 struct ipa_agg_replacement_value
*res
;
5126 struct ipa_agg_replacement_value
**tail
= &res
;
5127 struct cgraph_edge
*cs
;
5128 int i
, j
, count
= ipa_get_param_count (dest_info
);
5130 FOR_EACH_VEC_ELT (callers
, j
, cs
)
5132 if (!IPA_EDGE_REF (cs
))
5137 int c
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
5142 for (i
= 0; i
< count
; i
++)
5144 struct cgraph_edge
*cs
;
5145 vec
<ipa_agg_value
> inter
= vNULL
;
5146 struct ipa_agg_value
*item
;
5147 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (dest_info
, i
);
5150 /* Among other things, the following check should deal with all by_ref
5152 if (plats
->aggs_bottom
)
5155 FOR_EACH_VEC_ELT (callers
, j
, cs
)
5157 struct ipa_jump_func
*jfunc
5158 = ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
5159 if (self_recursive_pass_through_p (cs
, jfunc
, i
)
5160 && (!plats
->aggs_by_ref
5161 || ipa_get_jf_pass_through_agg_preserved (jfunc
)))
5163 inter
= intersect_aggregates_with_edge (cs
, i
, inter
);
5165 if (!inter
.exists ())
5169 FOR_EACH_VEC_ELT (inter
, j
, item
)
5171 struct ipa_agg_replacement_value
*v
;
5176 v
= ggc_alloc
<ipa_agg_replacement_value
> ();
5178 v
->offset
= item
->offset
;
5179 v
->value
= item
->value
;
5180 v
->by_ref
= plats
->aggs_by_ref
;
5186 if (inter
.exists ())
5193 /* Determine whether CS also brings all scalar values that the NODE is
5197 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge
*cs
,
5198 struct cgraph_node
*node
)
5200 class ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
5201 int count
= ipa_get_param_count (dest_info
);
5202 class ipa_node_params
*caller_info
;
5203 class ipa_edge_args
*args
;
5206 caller_info
= IPA_NODE_REF (cs
->caller
);
5207 args
= IPA_EDGE_REF (cs
);
5208 for (i
= 0; i
< count
; i
++)
5210 struct ipa_jump_func
*jump_func
;
5213 val
= dest_info
->known_csts
[i
];
5217 if (i
>= ipa_get_cs_argument_count (args
))
5219 jump_func
= ipa_get_ith_jump_func (args
, i
);
5220 t
= ipa_value_from_jfunc (caller_info
, jump_func
,
5221 ipa_get_type (dest_info
, i
));
5222 if (!t
|| !values_equal_for_ipcp_p (val
, t
))
5228 /* Determine whether CS also brings all aggregate values that NODE is
5231 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge
*cs
,
5232 struct cgraph_node
*node
)
5234 class ipa_node_params
*orig_node_info
;
5235 struct ipa_agg_replacement_value
*aggval
;
5238 aggval
= ipa_get_agg_replacements_for_node (node
);
5242 count
= ipa_get_param_count (IPA_NODE_REF (node
));
5243 ec
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
5245 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
5246 if (aggval
->index
>= ec
)
5249 orig_node_info
= IPA_NODE_REF (IPA_NODE_REF (node
)->ipcp_orig_node
);
5251 for (i
= 0; i
< count
; i
++)
5253 class ipcp_param_lattices
*plats
;
5254 bool interesting
= false;
5255 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
5256 if (aggval
->index
== i
)
5264 plats
= ipa_get_parm_lattices (orig_node_info
, aggval
->index
);
5265 if (plats
->aggs_bottom
)
5268 vec
<ipa_agg_value
> values
= intersect_aggregates_with_edge (cs
, i
, vNULL
);
5269 if (!values
.exists ())
5272 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
5273 if (aggval
->index
== i
)
5275 struct ipa_agg_value
*item
;
5278 FOR_EACH_VEC_ELT (values
, j
, item
)
5280 && item
->offset
== av
->offset
5281 && values_equal_for_ipcp_p (item
->value
, av
->value
))
5297 /* Given an original NODE and a VAL for which we have already created a
5298 specialized clone, look whether there are incoming edges that still lead
5299 into the old node but now also bring the requested value and also conform to
5300 all other criteria such that they can be redirected the special node.
5301 This function can therefore redirect the final edge in a SCC. */
5303 template <typename valtype
>
5305 perhaps_add_new_callers (cgraph_node
*node
, ipcp_value
<valtype
> *val
)
5307 ipcp_value_source
<valtype
> *src
;
5308 profile_count redirected_sum
= profile_count::zero ();
5310 for (src
= val
->sources
; src
; src
= src
->next
)
5312 struct cgraph_edge
*cs
= src
->cs
;
5315 if (cgraph_edge_brings_value_p (cs
, src
, node
, val
)
5316 && cgraph_edge_brings_all_scalars_for_node (cs
, val
->spec_node
)
5317 && cgraph_edge_brings_all_agg_vals_for_node (cs
, val
->spec_node
))
5320 fprintf (dump_file
, " - adding an extra caller %s of %s\n",
5321 cs
->caller
->dump_name (),
5322 val
->spec_node
->dump_name ());
5324 cs
->redirect_callee_duplicating_thunks (val
->spec_node
);
5325 val
->spec_node
->expand_all_artificial_thunks ();
5326 if (cs
->count
.ipa ().initialized_p ())
5327 redirected_sum
= redirected_sum
+ cs
->count
.ipa ();
5329 cs
= get_next_cgraph_edge_clone (cs
);
5333 if (redirected_sum
.nonzero_p ())
5334 update_specialized_profile (val
->spec_node
, node
, redirected_sum
);
5337 /* Return true if KNOWN_CONTEXTS contain at least one useful context. */
5340 known_contexts_useful_p (vec
<ipa_polymorphic_call_context
> known_contexts
)
5342 ipa_polymorphic_call_context
*ctx
;
5345 FOR_EACH_VEC_ELT (known_contexts
, i
, ctx
)
5346 if (!ctx
->useless_p ())
5351 /* Return a copy of KNOWN_CSTS if it is not empty, otherwise return vNULL. */
5353 static vec
<ipa_polymorphic_call_context
>
5354 copy_useful_known_contexts (vec
<ipa_polymorphic_call_context
> known_contexts
)
5356 if (known_contexts_useful_p (known_contexts
))
5357 return known_contexts
.copy ();
5362 /* Copy KNOWN_CSTS and modify the copy according to VAL and INDEX. If
5363 non-empty, replace KNOWN_CONTEXTS with its copy too. */
5366 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
5367 vec
<ipa_polymorphic_call_context
> *known_contexts
,
5368 ipcp_value
<tree
> *val
,
5371 *known_csts
= known_csts
->copy ();
5372 *known_contexts
= copy_useful_known_contexts (*known_contexts
);
5373 (*known_csts
)[index
] = val
->value
;
5376 /* Replace KNOWN_CSTS with its copy. Also copy KNOWN_CONTEXTS and modify the
5377 copy according to VAL and INDEX. */
5380 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
5381 vec
<ipa_polymorphic_call_context
> *known_contexts
,
5382 ipcp_value
<ipa_polymorphic_call_context
> *val
,
5385 *known_csts
= known_csts
->copy ();
5386 *known_contexts
= known_contexts
->copy ();
5387 (*known_contexts
)[index
] = val
->value
;
5390 /* Return true if OFFSET indicates this was not an aggregate value or there is
5391 a replacement equivalent to VALUE, INDEX and OFFSET among those in the
5395 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*aggvals
,
5396 int index
, HOST_WIDE_INT offset
, tree value
)
5403 if (aggvals
->index
== index
5404 && aggvals
->offset
== offset
5405 && values_equal_for_ipcp_p (aggvals
->value
, value
))
5407 aggvals
= aggvals
->next
;
5412 /* Return true if offset is minus one because source of a polymorphic context
5413 cannot be an aggregate value. */
5416 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*,
5417 int , HOST_WIDE_INT offset
,
5418 ipa_polymorphic_call_context
)
5420 return offset
== -1;
5423 /* Decide whether to create a special version of NODE for value VAL of parameter
5424 at the given INDEX. If OFFSET is -1, the value is for the parameter itself,
5425 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS,
5426 KNOWN_CONTEXTS and KNOWN_AGGS describe the other already known values. */
5428 template <typename valtype
>
5430 decide_about_value (struct cgraph_node
*node
, int index
, HOST_WIDE_INT offset
,
5431 ipcp_value
<valtype
> *val
, vec
<tree
> known_csts
,
5432 vec
<ipa_polymorphic_call_context
> known_contexts
)
5434 struct ipa_agg_replacement_value
*aggvals
;
5435 int freq_sum
, caller_count
;
5436 profile_count count_sum
;
5437 vec
<cgraph_edge
*> callers
;
5441 perhaps_add_new_callers (node
, val
);
5444 else if (val
->local_size_cost
+ overall_size
> get_max_overall_size (node
))
5446 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5447 fprintf (dump_file
, " Ignoring candidate value because "
5448 "maximum unit size would be reached with %li.\n",
5449 val
->local_size_cost
+ overall_size
);
5452 else if (!get_info_about_necessary_edges (val
, node
, &freq_sum
, &count_sum
,
5456 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5458 fprintf (dump_file
, " - considering value ");
5459 print_ipcp_constant_value (dump_file
, val
->value
);
5460 fprintf (dump_file
, " for ");
5461 ipa_dump_param (dump_file
, IPA_NODE_REF (node
), index
);
5463 fprintf (dump_file
, ", offset: " HOST_WIDE_INT_PRINT_DEC
, offset
);
5464 fprintf (dump_file
, " (caller_count: %i)\n", caller_count
);
5467 if (!good_cloning_opportunity_p (node
, val
->local_time_benefit
,
5468 freq_sum
, count_sum
,
5469 val
->local_size_cost
)
5470 && !good_cloning_opportunity_p (node
,
5471 val
->local_time_benefit
5472 + val
->prop_time_benefit
,
5473 freq_sum
, count_sum
,
5474 val
->local_size_cost
5475 + val
->prop_size_cost
))
5479 fprintf (dump_file
, " Creating a specialized node of %s.\n",
5480 node
->dump_name ());
5482 callers
= gather_edges_for_value (val
, node
, caller_count
);
5484 modify_known_vectors_with_val (&known_csts
, &known_contexts
, val
, index
);
5487 known_csts
= known_csts
.copy ();
5488 known_contexts
= copy_useful_known_contexts (known_contexts
);
5490 find_more_scalar_values_for_callers_subset (node
, known_csts
, callers
);
5491 find_more_contexts_for_caller_subset (node
, &known_contexts
, callers
);
5492 aggvals
= find_aggregate_values_for_callers_subset (node
, callers
);
5493 gcc_checking_assert (ipcp_val_agg_replacement_ok_p (aggvals
, index
,
5494 offset
, val
->value
));
5495 val
->spec_node
= create_specialized_node (node
, known_csts
, known_contexts
,
5497 overall_size
+= val
->local_size_cost
;
5499 /* TODO: If for some lattice there is only one other known value
5500 left, make a special node for it too. */
5505 /* Decide whether and what specialized clones of NODE should be created. */
5508 decide_whether_version_node (struct cgraph_node
*node
)
5510 class ipa_node_params
*info
= IPA_NODE_REF (node
);
5511 int i
, count
= ipa_get_param_count (info
);
5512 vec
<tree
> known_csts
;
5513 vec
<ipa_polymorphic_call_context
> known_contexts
;
5519 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5520 fprintf (dump_file
, "\nEvaluating opportunities for %s.\n",
5521 node
->dump_name ());
5523 gather_context_independent_values (info
, &known_csts
, &known_contexts
,
5526 for (i
= 0; i
< count
;i
++)
5528 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5529 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
5530 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
5535 ipcp_value
<tree
> *val
;
5536 for (val
= lat
->values
; val
; val
= val
->next
)
5537 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
5541 if (!plats
->aggs_bottom
)
5543 struct ipcp_agg_lattice
*aglat
;
5544 ipcp_value
<tree
> *val
;
5545 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
5546 if (!aglat
->bottom
&& aglat
->values
5547 /* If the following is false, the one value is in
5549 && (plats
->aggs_contain_variable
5550 || !aglat
->is_single_const ()))
5551 for (val
= aglat
->values
; val
; val
= val
->next
)
5552 ret
|= decide_about_value (node
, i
, aglat
->offset
, val
,
5553 known_csts
, known_contexts
);
5557 && known_contexts
[i
].useless_p ())
5559 ipcp_value
<ipa_polymorphic_call_context
> *val
;
5560 for (val
= ctxlat
->values
; val
; val
= val
->next
)
5561 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
5565 info
= IPA_NODE_REF (node
);
5568 if (info
->do_clone_for_all_contexts
)
5570 struct cgraph_node
*clone
;
5571 vec
<cgraph_edge
*> callers
= node
->collect_callers ();
5573 for (int i
= callers
.length () - 1; i
>= 0; i
--)
5575 cgraph_edge
*cs
= callers
[i
];
5576 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
5578 if (caller_info
&& caller_info
->node_dead
)
5579 callers
.unordered_remove (i
);
5582 if (!adjust_callers_for_value_intersection (callers
, node
))
5584 /* If node is not called by anyone, or all its caller edges are
5585 self-recursive, the node is not really be in use, no need to
5588 known_csts
.release ();
5589 known_contexts
.release ();
5590 info
->do_clone_for_all_contexts
= false;
5595 fprintf (dump_file
, " - Creating a specialized node of %s "
5596 "for all known contexts.\n", node
->dump_name ());
5598 find_more_scalar_values_for_callers_subset (node
, known_csts
, callers
);
5599 find_more_contexts_for_caller_subset (node
, &known_contexts
, callers
);
5600 ipa_agg_replacement_value
*aggvals
5601 = find_aggregate_values_for_callers_subset (node
, callers
);
5603 if (!known_contexts_useful_p (known_contexts
))
5605 known_contexts
.release ();
5606 known_contexts
= vNULL
;
5608 clone
= create_specialized_node (node
, known_csts
, known_contexts
,
5610 info
= IPA_NODE_REF (node
);
5611 info
->do_clone_for_all_contexts
= false;
5612 IPA_NODE_REF (clone
)->is_all_contexts_clone
= true;
5617 known_csts
.release ();
5618 known_contexts
.release ();
5624 /* Transitively mark all callees of NODE within the same SCC as not dead. */
5627 spread_undeadness (struct cgraph_node
*node
)
5629 struct cgraph_edge
*cs
;
5631 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
5632 if (ipa_edge_within_scc (cs
))
5634 struct cgraph_node
*callee
;
5635 class ipa_node_params
*info
;
5637 callee
= cs
->callee
->function_symbol (NULL
);
5638 info
= IPA_NODE_REF (callee
);
5640 if (info
&& info
->node_dead
)
5642 info
->node_dead
= 0;
5643 spread_undeadness (callee
);
5648 /* Return true if NODE has a caller from outside of its SCC that is not
5649 dead. Worker callback for cgraph_for_node_and_aliases. */
5652 has_undead_caller_from_outside_scc_p (struct cgraph_node
*node
,
5653 void *data ATTRIBUTE_UNUSED
)
5655 struct cgraph_edge
*cs
;
5657 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
5658 if (cs
->caller
->thunk
.thunk_p
5659 && cs
->caller
->call_for_symbol_thunks_and_aliases
5660 (has_undead_caller_from_outside_scc_p
, NULL
, true))
5662 else if (!ipa_edge_within_scc (cs
)
5663 && !IPA_NODE_REF (cs
->caller
)->node_dead
)
5669 /* Identify nodes within the same SCC as NODE which are no longer needed
5670 because of new clones and will be removed as unreachable. */
5673 identify_dead_nodes (struct cgraph_node
*node
)
5675 struct cgraph_node
*v
;
5676 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
5679 && !v
->call_for_symbol_thunks_and_aliases
5680 (has_undead_caller_from_outside_scc_p
, NULL
, true))
5681 IPA_NODE_REF (v
)->node_dead
= 1;
5683 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
5684 if (IPA_NODE_REF (v
) && !IPA_NODE_REF (v
)->node_dead
)
5685 spread_undeadness (v
);
5687 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5689 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
5690 if (IPA_NODE_REF (v
) && IPA_NODE_REF (v
)->node_dead
)
5691 fprintf (dump_file
, " Marking node as dead: %s.\n", v
->dump_name ());
5695 /* The decision stage. Iterate over the topological order of call graph nodes
5696 TOPO and make specialized clones if deemed beneficial. */
5699 ipcp_decision_stage (class ipa_topo_info
*topo
)
5704 fprintf (dump_file
, "\nIPA decision stage:\n\n");
5706 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
5708 struct cgraph_node
*node
= topo
->order
[i
];
5709 bool change
= false, iterate
= true;
5713 struct cgraph_node
*v
;
5715 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
5716 if (v
->has_gimple_body_p ()
5717 && ipcp_versionable_function_p (v
))
5718 iterate
|= decide_whether_version_node (v
);
5723 identify_dead_nodes (node
);
5727 /* Look up all the bits information that we have discovered and copy it over
5728 to the transformation summary. */
5731 ipcp_store_bits_results (void)
5735 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5737 ipa_node_params
*info
= IPA_NODE_REF (node
);
5738 bool dumped_sth
= false;
5739 bool found_useful_result
= false;
5741 if (!opt_for_fn (node
->decl
, flag_ipa_bit_cp
) || !info
)
5744 fprintf (dump_file
, "Not considering %s for ipa bitwise propagation "
5745 "; -fipa-bit-cp: disabled.\n",
5746 node
->dump_name ());
5750 if (info
->ipcp_orig_node
)
5751 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
5752 if (!info
->lattices
)
5753 /* Newly expanded artificial thunks do not have lattices. */
5756 unsigned count
= ipa_get_param_count (info
);
5757 for (unsigned i
= 0; i
< count
; i
++)
5759 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5760 if (plats
->bits_lattice
.constant_p ())
5762 found_useful_result
= true;
5767 if (!found_useful_result
)
5770 ipcp_transformation_initialize ();
5771 ipcp_transformation
*ts
= ipcp_transformation_sum
->get_create (node
);
5772 vec_safe_reserve_exact (ts
->bits
, count
);
5774 for (unsigned i
= 0; i
< count
; i
++)
5776 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5779 if (plats
->bits_lattice
.constant_p ())
5781 = ipa_get_ipa_bits_for_value (plats
->bits_lattice
.get_value (),
5782 plats
->bits_lattice
.get_mask ());
5786 ts
->bits
->quick_push (jfbits
);
5787 if (!dump_file
|| !jfbits
)
5791 fprintf (dump_file
, "Propagated bits info for function %s:\n",
5792 node
->dump_name ());
5795 fprintf (dump_file
, " param %i: value = ", i
);
5796 print_hex (jfbits
->value
, dump_file
);
5797 fprintf (dump_file
, ", mask = ");
5798 print_hex (jfbits
->mask
, dump_file
);
5799 fprintf (dump_file
, "\n");
5804 /* Look up all VR information that we have discovered and copy it over
5805 to the transformation summary. */
5808 ipcp_store_vr_results (void)
5812 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5814 ipa_node_params
*info
= IPA_NODE_REF (node
);
5815 bool found_useful_result
= false;
5817 if (!info
|| !opt_for_fn (node
->decl
, flag_ipa_vrp
))
5820 fprintf (dump_file
, "Not considering %s for VR discovery "
5821 "and propagate; -fipa-ipa-vrp: disabled.\n",
5822 node
->dump_name ());
5826 if (info
->ipcp_orig_node
)
5827 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
5828 if (!info
->lattices
)
5829 /* Newly expanded artificial thunks do not have lattices. */
5832 unsigned count
= ipa_get_param_count (info
);
5833 for (unsigned i
= 0; i
< count
; i
++)
5835 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5836 if (!plats
->m_value_range
.bottom_p ()
5837 && !plats
->m_value_range
.top_p ())
5839 found_useful_result
= true;
5843 if (!found_useful_result
)
5846 ipcp_transformation_initialize ();
5847 ipcp_transformation
*ts
= ipcp_transformation_sum
->get_create (node
);
5848 vec_safe_reserve_exact (ts
->m_vr
, count
);
5850 for (unsigned i
= 0; i
< count
; i
++)
5852 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5855 if (!plats
->m_value_range
.bottom_p ()
5856 && !plats
->m_value_range
.top_p ())
5859 vr
.type
= plats
->m_value_range
.m_vr
.kind ();
5860 vr
.min
= wi::to_wide (plats
->m_value_range
.m_vr
.min ());
5861 vr
.max
= wi::to_wide (plats
->m_value_range
.m_vr
.max ());
5866 vr
.type
= VR_VARYING
;
5867 vr
.min
= vr
.max
= wi::zero (INT_TYPE_SIZE
);
5869 ts
->m_vr
->quick_push (vr
);
5874 /* The IPCP driver. */
5879 class ipa_topo_info topo
;
5881 if (edge_clone_summaries
== NULL
)
5882 edge_clone_summaries
= new edge_clone_summary_t (symtab
);
5884 ipa_check_create_node_params ();
5885 ipa_check_create_edge_args ();
5886 clone_num_suffixes
= new hash_map
<const char *, unsigned>;
5890 fprintf (dump_file
, "\nIPA structures before propagation:\n");
5891 if (dump_flags
& TDF_DETAILS
)
5892 ipa_print_all_params (dump_file
);
5893 ipa_print_all_jump_functions (dump_file
);
5896 /* Topological sort. */
5897 build_toporder_info (&topo
);
5898 /* Do the interprocedural propagation. */
5899 ipcp_propagate_stage (&topo
);
5900 /* Decide what constant propagation and cloning should be performed. */
5901 ipcp_decision_stage (&topo
);
5902 /* Store results of bits propagation. */
5903 ipcp_store_bits_results ();
5904 /* Store results of value range propagation. */
5905 ipcp_store_vr_results ();
5907 /* Free all IPCP structures. */
5908 delete clone_num_suffixes
;
5909 free_toporder_info (&topo
);
5910 delete edge_clone_summaries
;
5911 edge_clone_summaries
= NULL
;
5912 ipa_free_all_structures_after_ipa_cp ();
5914 fprintf (dump_file
, "\nIPA constant propagation end\n");
5918 /* Initialization and computation of IPCP data structures. This is the initial
5919 intraprocedural analysis of functions, which gathers information to be
5920 propagated later on. */
5923 ipcp_generate_summary (void)
5925 struct cgraph_node
*node
;
5928 fprintf (dump_file
, "\nIPA constant propagation start:\n");
5929 ipa_register_cgraph_hooks ();
5931 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5932 ipa_analyze_node (node
);
5935 /* Write ipcp summary for nodes in SET. */
5938 ipcp_write_summary (void)
5940 ipa_prop_write_jump_functions ();
5943 /* Read ipcp summary. */
5946 ipcp_read_summary (void)
5948 ipa_prop_read_jump_functions ();
5953 const pass_data pass_data_ipa_cp
=
5955 IPA_PASS
, /* type */
5957 OPTGROUP_NONE
, /* optinfo_flags */
5958 TV_IPA_CONSTANT_PROP
, /* tv_id */
5959 0, /* properties_required */
5960 0, /* properties_provided */
5961 0, /* properties_destroyed */
5962 0, /* todo_flags_start */
5963 ( TODO_dump_symtab
| TODO_remove_functions
), /* todo_flags_finish */
5966 class pass_ipa_cp
: public ipa_opt_pass_d
5969 pass_ipa_cp (gcc::context
*ctxt
)
5970 : ipa_opt_pass_d (pass_data_ipa_cp
, ctxt
,
5971 ipcp_generate_summary
, /* generate_summary */
5972 ipcp_write_summary
, /* write_summary */
5973 ipcp_read_summary
, /* read_summary */
5974 ipcp_write_transformation_summaries
, /*
5975 write_optimization_summary */
5976 ipcp_read_transformation_summaries
, /*
5977 read_optimization_summary */
5978 NULL
, /* stmt_fixup */
5979 0, /* function_transform_todo_flags_start */
5980 ipcp_transform_function
, /* function_transform */
5981 NULL
) /* variable_transform */
5984 /* opt_pass methods: */
5985 virtual bool gate (function
*)
5987 /* FIXME: We should remove the optimize check after we ensure we never run
5988 IPA passes when not optimizing. */
5989 return (flag_ipa_cp
&& optimize
) || in_lto_p
;
5992 virtual unsigned int execute (function
*) { return ipcp_driver (); }
5994 }; // class pass_ipa_cp
5999 make_pass_ipa_cp (gcc::context
*ctxt
)
6001 return new pass_ipa_cp (ctxt
);
6004 /* Reset all state within ipa-cp.c so that we can rerun the compiler
6005 within the same process. For use by toplev::finalize. */
6008 ipa_cp_c_finalize (void)
6010 max_count
= profile_count::uninitialized ();
6012 orig_overall_size
= 0;
6013 ipcp_free_transformation_sum ();