1 /* Interprocedural constant propagation
2 Copyright (C) 2005-2019 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"
122 #include "ipa-fnsummary.h"
123 #include "ipa-utils.h"
124 #include "tree-ssa-ccp.h"
125 #include "stringpool.h"
128 template <typename valtype
> class ipcp_value
;
130 /* Describes a particular source for an IPA-CP value. */
132 template <typename valtype
>
133 class ipcp_value_source
136 /* Aggregate offset of the source, negative if the source is scalar value of
137 the argument itself. */
138 HOST_WIDE_INT offset
;
139 /* The incoming edge that brought the value. */
141 /* If the jump function that resulted into his value was a pass-through or an
142 ancestor, this is the ipcp_value of the caller from which the described
143 value has been derived. Otherwise it is NULL. */
144 ipcp_value
<valtype
> *val
;
145 /* Next pointer in a linked list of sources of a value. */
146 ipcp_value_source
*next
;
147 /* If the jump function that resulted into his value was a pass-through or an
148 ancestor, this is the index of the parameter of the caller the jump
149 function references. */
153 /* Common ancestor for all ipcp_value instantiations. */
155 class ipcp_value_base
158 /* Time benefit and size cost that specializing the function for this value
159 would bring about in this function alone. */
160 int local_time_benefit
, local_size_cost
;
161 /* Time benefit and size cost that specializing the function for this value
162 can bring about in it's callees (transitively). */
163 int prop_time_benefit
, prop_size_cost
;
166 : local_time_benefit (0), local_size_cost (0),
167 prop_time_benefit (0), prop_size_cost (0) {}
170 /* Describes one particular value stored in struct ipcp_lattice. */
172 template <typename valtype
>
173 class ipcp_value
: public ipcp_value_base
176 /* The actual value for the given parameter. */
178 /* The list of sources from which this value originates. */
179 ipcp_value_source
<valtype
> *sources
;
180 /* Next pointers in a linked list of all values in a lattice. */
182 /* Next pointers in a linked list of values in a strongly connected component
184 ipcp_value
*scc_next
;
185 /* Next pointers in a linked list of SCCs of values sorted topologically
186 according their sources. */
187 ipcp_value
*topo_next
;
188 /* A specialized node created for this value, NULL if none has been (so far)
190 cgraph_node
*spec_node
;
191 /* Depth first search number and low link for topological sorting of
194 /* True if this value is currently on the topo-sort stack. */
198 : sources (0), next (0), scc_next (0), topo_next (0),
199 spec_node (0), dfs (0), low_link (0), on_stack (false) {}
201 void add_source (cgraph_edge
*cs
, ipcp_value
*src_val
, int src_idx
,
202 HOST_WIDE_INT offset
);
205 /* Lattice describing potential values of a formal parameter of a function, or
206 a part of an aggregate. TOP is represented by a lattice with zero values
207 and with contains_variable and bottom flags cleared. BOTTOM is represented
208 by a lattice with the bottom flag set. In that case, values and
209 contains_variable flag should be disregarded. */
211 template <typename valtype
>
215 /* The list of known values and types in this lattice. Note that values are
216 not deallocated if a lattice is set to bottom because there may be value
217 sources referencing them. */
218 ipcp_value
<valtype
> *values
;
219 /* Number of known values and types in this lattice. */
221 /* The lattice contains a variable component (in addition to values). */
222 bool contains_variable
;
223 /* The value of the lattice is bottom (i.e. variable and unusable for any
227 inline bool is_single_const ();
228 inline bool set_to_bottom ();
229 inline bool set_contains_variable ();
230 bool add_value (valtype newval
, cgraph_edge
*cs
,
231 ipcp_value
<valtype
> *src_val
= NULL
,
232 int src_idx
= 0, HOST_WIDE_INT offset
= -1);
233 void print (FILE * f
, bool dump_sources
, bool dump_benefits
);
236 /* Lattice of tree values with an offset to describe a part of an
239 class ipcp_agg_lattice
: public ipcp_lattice
<tree
>
242 /* Offset that is being described by this lattice. */
243 HOST_WIDE_INT offset
;
244 /* Size so that we don't have to re-compute it every time we traverse the
245 list. Must correspond to TYPE_SIZE of all lat values. */
247 /* Next element of the linked list. */
248 struct ipcp_agg_lattice
*next
;
251 /* Lattice of known bits, only capable of holding one value.
252 Bitwise constant propagation propagates which bits of a
268 In the above case, the param 'x' will always have all
269 the bits (except the bits in lsb) set to 0.
270 Hence the mask of 'x' would be 0xff. The mask
271 reflects that the bits in lsb are unknown.
272 The actual propagated value is given by m_value & ~m_mask. */
274 class ipcp_bits_lattice
277 bool bottom_p () { return m_lattice_val
== IPA_BITS_VARYING
; }
278 bool top_p () { return m_lattice_val
== IPA_BITS_UNDEFINED
; }
279 bool constant_p () { return m_lattice_val
== IPA_BITS_CONSTANT
; }
280 bool set_to_bottom ();
281 bool set_to_constant (widest_int
, widest_int
);
283 widest_int
get_value () { return m_value
; }
284 widest_int
get_mask () { return m_mask
; }
286 bool meet_with (ipcp_bits_lattice
& other
, unsigned, signop
,
287 enum tree_code
, tree
);
289 bool meet_with (widest_int
, widest_int
, unsigned);
294 enum { IPA_BITS_UNDEFINED
, IPA_BITS_CONSTANT
, IPA_BITS_VARYING
} m_lattice_val
;
296 /* Similar to ccp_lattice_t, mask represents which bits of value are constant.
297 If a bit in mask is set to 0, then the corresponding bit in
298 value is known to be constant. */
299 widest_int m_value
, m_mask
;
301 bool meet_with_1 (widest_int
, widest_int
, unsigned);
302 void get_value_and_mask (tree
, widest_int
*, widest_int
*);
305 /* Lattice of value ranges. */
307 class ipcp_vr_lattice
310 value_range_base m_vr
;
312 inline bool bottom_p () const;
313 inline bool top_p () const;
314 inline bool set_to_bottom ();
315 bool meet_with (const value_range_base
*p_vr
);
316 bool meet_with (const ipcp_vr_lattice
&other
);
317 void init () { gcc_assert (m_vr
.undefined_p ()); }
318 void print (FILE * f
);
321 bool meet_with_1 (const value_range_base
*other_vr
);
324 /* Structure containing lattices for a parameter itself and for pieces of
325 aggregates that are passed in the parameter or by a reference in a parameter
326 plus some other useful flags. */
328 class ipcp_param_lattices
331 /* Lattice describing the value of the parameter itself. */
332 ipcp_lattice
<tree
> itself
;
333 /* Lattice describing the polymorphic contexts of a parameter. */
334 ipcp_lattice
<ipa_polymorphic_call_context
> ctxlat
;
335 /* Lattices describing aggregate parts. */
336 ipcp_agg_lattice
*aggs
;
337 /* Lattice describing known bits. */
338 ipcp_bits_lattice bits_lattice
;
339 /* Lattice describing value range. */
340 ipcp_vr_lattice m_value_range
;
341 /* Number of aggregate lattices */
343 /* True if aggregate data were passed by reference (as opposed to by
346 /* All aggregate lattices contain a variable component (in addition to
348 bool aggs_contain_variable
;
349 /* The value of all aggregate lattices is bottom (i.e. variable and unusable
350 for any propagation). */
353 /* There is a virtual call based on this parameter. */
357 /* Allocation pools for values and their sources in ipa-cp. */
359 object_allocator
<ipcp_value
<tree
> > ipcp_cst_values_pool
360 ("IPA-CP constant values");
362 object_allocator
<ipcp_value
<ipa_polymorphic_call_context
> >
363 ipcp_poly_ctx_values_pool ("IPA-CP polymorphic contexts");
365 object_allocator
<ipcp_value_source
<tree
> > ipcp_sources_pool
366 ("IPA-CP value sources");
368 object_allocator
<ipcp_agg_lattice
> ipcp_agg_lattice_pool
369 ("IPA_CP aggregate lattices");
371 /* Maximal count found in program. */
373 static profile_count max_count
;
375 /* Original overall size of the program. */
377 static long overall_size
, max_new_size
;
379 /* Node name to unique clone suffix number map. */
380 static hash_map
<const char *, unsigned> *clone_num_suffixes
;
382 /* Return the param lattices structure corresponding to the Ith formal
383 parameter of the function described by INFO. */
384 static inline struct ipcp_param_lattices
*
385 ipa_get_parm_lattices (struct ipa_node_params
*info
, int i
)
387 gcc_assert (i
>= 0 && i
< ipa_get_param_count (info
));
388 gcc_checking_assert (!info
->ipcp_orig_node
);
389 gcc_checking_assert (info
->lattices
);
390 return &(info
->lattices
[i
]);
393 /* Return the lattice corresponding to the scalar value of the Ith formal
394 parameter of the function described by INFO. */
395 static inline ipcp_lattice
<tree
> *
396 ipa_get_scalar_lat (struct ipa_node_params
*info
, int i
)
398 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
399 return &plats
->itself
;
402 /* Return the lattice corresponding to the scalar value of the Ith formal
403 parameter of the function described by INFO. */
404 static inline ipcp_lattice
<ipa_polymorphic_call_context
> *
405 ipa_get_poly_ctx_lat (struct ipa_node_params
*info
, int i
)
407 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
408 return &plats
->ctxlat
;
411 /* Return whether LAT is a lattice with a single constant and without an
414 template <typename valtype
>
416 ipcp_lattice
<valtype
>::is_single_const ()
418 if (bottom
|| contains_variable
|| values_count
!= 1)
424 /* Print V which is extracted from a value in a lattice to F. */
427 print_ipcp_constant_value (FILE * f
, tree v
)
429 if (TREE_CODE (v
) == ADDR_EXPR
430 && TREE_CODE (TREE_OPERAND (v
, 0)) == CONST_DECL
)
433 print_generic_expr (f
, DECL_INITIAL (TREE_OPERAND (v
, 0)));
436 print_generic_expr (f
, v
);
439 /* Print V which is extracted from a value in a lattice to F. */
442 print_ipcp_constant_value (FILE * f
, ipa_polymorphic_call_context v
)
447 /* Print a lattice LAT to F. */
449 template <typename valtype
>
451 ipcp_lattice
<valtype
>::print (FILE * f
, bool dump_sources
, bool dump_benefits
)
453 ipcp_value
<valtype
> *val
;
458 fprintf (f
, "BOTTOM\n");
462 if (!values_count
&& !contains_variable
)
464 fprintf (f
, "TOP\n");
468 if (contains_variable
)
470 fprintf (f
, "VARIABLE");
476 for (val
= values
; val
; val
= val
->next
)
478 if (dump_benefits
&& prev
)
480 else if (!dump_benefits
&& prev
)
485 print_ipcp_constant_value (f
, val
->value
);
489 ipcp_value_source
<valtype
> *s
;
491 fprintf (f
, " [from:");
492 for (s
= val
->sources
; s
; s
= s
->next
)
493 fprintf (f
, " %i(%f)", s
->cs
->caller
->order
,
494 s
->cs
->sreal_frequency ().to_double ());
499 fprintf (f
, " [loc_time: %i, loc_size: %i, "
500 "prop_time: %i, prop_size: %i]\n",
501 val
->local_time_benefit
, val
->local_size_cost
,
502 val
->prop_time_benefit
, val
->prop_size_cost
);
509 ipcp_bits_lattice::print (FILE *f
)
512 fprintf (f
, " Bits unknown (TOP)\n");
513 else if (bottom_p ())
514 fprintf (f
, " Bits unusable (BOTTOM)\n");
517 fprintf (f
, " Bits: value = "); print_hex (get_value (), f
);
518 fprintf (f
, ", mask = "); print_hex (get_mask (), f
);
523 /* Print value range lattice to F. */
526 ipcp_vr_lattice::print (FILE * f
)
528 dump_value_range (f
, &m_vr
);
531 /* Print all ipcp_lattices of all functions to F. */
534 print_all_lattices (FILE * f
, bool dump_sources
, bool dump_benefits
)
536 struct cgraph_node
*node
;
539 fprintf (f
, "\nLattices:\n");
540 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
542 struct ipa_node_params
*info
;
544 info
= IPA_NODE_REF (node
);
545 /* Skip constprop clones since we don't make lattices for them. */
546 if (info
->ipcp_orig_node
)
548 fprintf (f
, " Node: %s:\n", node
->dump_name ());
549 count
= ipa_get_param_count (info
);
550 for (i
= 0; i
< count
; i
++)
552 struct ipcp_agg_lattice
*aglat
;
553 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
554 fprintf (f
, " param [%d]: ", i
);
555 plats
->itself
.print (f
, dump_sources
, dump_benefits
);
556 fprintf (f
, " ctxs: ");
557 plats
->ctxlat
.print (f
, dump_sources
, dump_benefits
);
558 plats
->bits_lattice
.print (f
);
560 plats
->m_value_range
.print (f
);
562 if (plats
->virt_call
)
563 fprintf (f
, " virt_call flag set\n");
565 if (plats
->aggs_bottom
)
567 fprintf (f
, " AGGS BOTTOM\n");
570 if (plats
->aggs_contain_variable
)
571 fprintf (f
, " AGGS VARIABLE\n");
572 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
574 fprintf (f
, " %soffset " HOST_WIDE_INT_PRINT_DEC
": ",
575 plats
->aggs_by_ref
? "ref " : "", aglat
->offset
);
576 aglat
->print (f
, dump_sources
, dump_benefits
);
582 /* Determine whether it is at all technically possible to create clones of NODE
583 and store this information in the ipa_node_params structure associated
587 determine_versionability (struct cgraph_node
*node
,
588 struct ipa_node_params
*info
)
590 const char *reason
= NULL
;
592 /* There are a number of generic reasons functions cannot be versioned. We
593 also cannot remove parameters if there are type attributes such as fnspec
595 if (node
->alias
|| node
->thunk
.thunk_p
)
596 reason
= "alias or thunk";
597 else if (!node
->local
.versionable
)
598 reason
= "not a tree_versionable_function";
599 else if (node
->get_availability () <= AVAIL_INTERPOSABLE
)
600 reason
= "insufficient body availability";
601 else if (!opt_for_fn (node
->decl
, optimize
)
602 || !opt_for_fn (node
->decl
, flag_ipa_cp
))
603 reason
= "non-optimized function";
604 else if (lookup_attribute ("omp declare simd", DECL_ATTRIBUTES (node
->decl
)))
606 /* Ideally we should clone the SIMD clones themselves and create
607 vector copies of them, so IPA-cp and SIMD clones can happily
608 coexist, but that may not be worth the effort. */
609 reason
= "function has SIMD clones";
611 else if (lookup_attribute ("target_clones", DECL_ATTRIBUTES (node
->decl
)))
613 /* Ideally we should clone the target clones themselves and create
614 copies of them, so IPA-cp and target clones can happily
615 coexist, but that may not be worth the effort. */
616 reason
= "function target_clones attribute";
618 /* Don't clone decls local to a comdat group; it breaks and for C++
619 decloned constructors, inlining is always better anyway. */
620 else if (node
->comdat_local_p ())
621 reason
= "comdat-local function";
622 else if (node
->calls_comdat_local
)
624 /* TODO: call is versionable if we make sure that all
625 callers are inside of a comdat group. */
626 reason
= "calls comdat-local function";
629 /* Functions calling BUILT_IN_VA_ARG_PACK and BUILT_IN_VA_ARG_PACK_LEN
630 work only when inlined. Cloning them may still lead to better code
631 because ipa-cp will not give up on cloning further. If the function is
632 external this however leads to wrong code because we may end up producing
633 offline copy of the function. */
634 if (DECL_EXTERNAL (node
->decl
))
635 for (cgraph_edge
*edge
= node
->callees
; !reason
&& edge
;
636 edge
= edge
->next_callee
)
637 if (fndecl_built_in_p (edge
->callee
->decl
, BUILT_IN_NORMAL
))
639 if (DECL_FUNCTION_CODE (edge
->callee
->decl
) == BUILT_IN_VA_ARG_PACK
)
640 reason
= "external function which calls va_arg_pack";
641 if (DECL_FUNCTION_CODE (edge
->callee
->decl
)
642 == BUILT_IN_VA_ARG_PACK_LEN
)
643 reason
= "external function which calls va_arg_pack_len";
646 if (reason
&& dump_file
&& !node
->alias
&& !node
->thunk
.thunk_p
)
647 fprintf (dump_file
, "Function %s is not versionable, reason: %s.\n",
648 node
->dump_name (), reason
);
650 info
->versionable
= (reason
== NULL
);
653 /* Return true if it is at all technically possible to create clones of a
657 ipcp_versionable_function_p (struct cgraph_node
*node
)
659 return IPA_NODE_REF (node
)->versionable
;
662 /* Structure holding accumulated information about callers of a node. */
664 struct caller_statistics
666 profile_count count_sum
;
667 int n_calls
, n_hot_calls
, freq_sum
;
670 /* Initialize fields of STAT to zeroes. */
673 init_caller_stats (struct caller_statistics
*stats
)
675 stats
->count_sum
= profile_count::zero ();
677 stats
->n_hot_calls
= 0;
681 /* Worker callback of cgraph_for_node_and_aliases accumulating statistics of
682 non-thunk incoming edges to NODE. */
685 gather_caller_stats (struct cgraph_node
*node
, void *data
)
687 struct caller_statistics
*stats
= (struct caller_statistics
*) data
;
688 struct cgraph_edge
*cs
;
690 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
691 if (!cs
->caller
->thunk
.thunk_p
)
693 if (cs
->count
.ipa ().initialized_p ())
694 stats
->count_sum
+= cs
->count
.ipa ();
695 stats
->freq_sum
+= cs
->frequency ();
697 if (cs
->maybe_hot_p ())
698 stats
->n_hot_calls
++;
704 /* Return true if this NODE is viable candidate for cloning. */
707 ipcp_cloning_candidate_p (struct cgraph_node
*node
)
709 struct caller_statistics stats
;
711 gcc_checking_assert (node
->has_gimple_body_p ());
713 if (!opt_for_fn (node
->decl
, flag_ipa_cp_clone
))
716 fprintf (dump_file
, "Not considering %s for cloning; "
717 "-fipa-cp-clone disabled.\n",
722 if (node
->optimize_for_size_p ())
725 fprintf (dump_file
, "Not considering %s for cloning; "
726 "optimizing it for size.\n",
731 init_caller_stats (&stats
);
732 node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
, false);
734 if (ipa_fn_summaries
->get (node
)->self_size
< stats
.n_calls
)
737 fprintf (dump_file
, "Considering %s for cloning; code might shrink.\n",
742 /* When profile is available and function is hot, propagate into it even if
743 calls seems cold; constant propagation can improve function's speed
745 if (max_count
> profile_count::zero ())
747 if (stats
.count_sum
> node
->count
.ipa ().apply_scale (90, 100))
750 fprintf (dump_file
, "Considering %s for cloning; "
751 "usually called directly.\n",
756 if (!stats
.n_hot_calls
)
759 fprintf (dump_file
, "Not considering %s for cloning; no hot calls.\n",
764 fprintf (dump_file
, "Considering %s for cloning.\n",
769 template <typename valtype
>
770 class value_topo_info
773 /* Head of the linked list of topologically sorted values. */
774 ipcp_value
<valtype
> *values_topo
;
775 /* Stack for creating SCCs, represented by a linked list too. */
776 ipcp_value
<valtype
> *stack
;
777 /* Counter driving the algorithm in add_val_to_toposort. */
780 value_topo_info () : values_topo (NULL
), stack (NULL
), dfs_counter (0)
782 void add_val (ipcp_value
<valtype
> *cur_val
);
783 void propagate_effects ();
786 /* Arrays representing a topological ordering of call graph nodes and a stack
787 of nodes used during constant propagation and also data required to perform
788 topological sort of values and propagation of benefits in the determined
794 /* Array with obtained topological order of cgraph nodes. */
795 struct cgraph_node
**order
;
796 /* Stack of cgraph nodes used during propagation within SCC until all values
797 in the SCC stabilize. */
798 struct cgraph_node
**stack
;
799 int nnodes
, stack_top
;
801 value_topo_info
<tree
> constants
;
802 value_topo_info
<ipa_polymorphic_call_context
> contexts
;
804 ipa_topo_info () : order(NULL
), stack(NULL
), nnodes(0), stack_top(0),
809 /* Skip edges from and to nodes without ipa_cp enabled.
810 Ignore not available symbols. */
813 ignore_edge_p (cgraph_edge
*e
)
815 enum availability avail
;
816 cgraph_node
*ultimate_target
817 = e
->callee
->function_or_virtual_thunk_symbol (&avail
, e
->caller
);
819 return (avail
<= AVAIL_INTERPOSABLE
820 || !opt_for_fn (ultimate_target
->decl
, flag_ipa_cp
));
823 /* Allocate the arrays in TOPO and topologically sort the nodes into order. */
826 build_toporder_info (struct ipa_topo_info
*topo
)
828 topo
->order
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
829 topo
->stack
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
831 gcc_checking_assert (topo
->stack_top
== 0);
832 topo
->nnodes
= ipa_reduced_postorder (topo
->order
, true,
836 /* Free information about strongly connected components and the arrays in
840 free_toporder_info (struct ipa_topo_info
*topo
)
842 ipa_free_postorder_info ();
847 /* Add NODE to the stack in TOPO, unless it is already there. */
850 push_node_to_stack (struct ipa_topo_info
*topo
, struct cgraph_node
*node
)
852 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
853 if (info
->node_enqueued
)
855 info
->node_enqueued
= 1;
856 topo
->stack
[topo
->stack_top
++] = node
;
859 /* Pop a node from the stack in TOPO and return it or return NULL if the stack
862 static struct cgraph_node
*
863 pop_node_from_stack (struct ipa_topo_info
*topo
)
867 struct cgraph_node
*node
;
869 node
= topo
->stack
[topo
->stack_top
];
870 IPA_NODE_REF (node
)->node_enqueued
= 0;
877 /* Set lattice LAT to bottom and return true if it previously was not set as
880 template <typename valtype
>
882 ipcp_lattice
<valtype
>::set_to_bottom ()
889 /* Mark lattice as containing an unknown value and return true if it previously
890 was not marked as such. */
892 template <typename valtype
>
894 ipcp_lattice
<valtype
>::set_contains_variable ()
896 bool ret
= !contains_variable
;
897 contains_variable
= true;
901 /* Set all aggregate lattices in PLATS to bottom and return true if they were
902 not previously set as such. */
905 set_agg_lats_to_bottom (struct ipcp_param_lattices
*plats
)
907 bool ret
= !plats
->aggs_bottom
;
908 plats
->aggs_bottom
= true;
912 /* Mark all aggregate lattices in PLATS as containing an unknown value and
913 return true if they were not previously marked as such. */
916 set_agg_lats_contain_variable (struct ipcp_param_lattices
*plats
)
918 bool ret
= !plats
->aggs_contain_variable
;
919 plats
->aggs_contain_variable
= true;
924 ipcp_vr_lattice::meet_with (const ipcp_vr_lattice
&other
)
926 return meet_with_1 (&other
.m_vr
);
929 /* Meet the current value of the lattice with value range described by VR
933 ipcp_vr_lattice::meet_with (const value_range_base
*p_vr
)
935 return meet_with_1 (p_vr
);
938 /* Meet the current value of the lattice with value range described by
939 OTHER_VR lattice. Return TRUE if anything changed. */
942 ipcp_vr_lattice::meet_with_1 (const value_range_base
*other_vr
)
947 if (other_vr
->varying_p ())
948 return set_to_bottom ();
950 value_range_base
save (m_vr
);
951 m_vr
.union_ (other_vr
);
952 return !m_vr
.equal_p (save
);
955 /* Return true if value range information in the lattice is yet unknown. */
958 ipcp_vr_lattice::top_p () const
960 return m_vr
.undefined_p ();
963 /* Return true if value range information in the lattice is known to be
967 ipcp_vr_lattice::bottom_p () const
969 return m_vr
.varying_p ();
972 /* Set value range information in the lattice to bottom. Return true if it
973 previously was in a different state. */
976 ipcp_vr_lattice::set_to_bottom ()
978 if (m_vr
.varying_p ())
984 /* Set lattice value to bottom, if it already isn't the case. */
987 ipcp_bits_lattice::set_to_bottom ()
991 m_lattice_val
= IPA_BITS_VARYING
;
997 /* Set to constant if it isn't already. Only meant to be called
998 when switching state from TOP. */
1001 ipcp_bits_lattice::set_to_constant (widest_int value
, widest_int mask
)
1003 gcc_assert (top_p ());
1004 m_lattice_val
= IPA_BITS_CONSTANT
;
1010 /* Convert operand to value, mask form. */
1013 ipcp_bits_lattice::get_value_and_mask (tree operand
, widest_int
*valuep
, widest_int
*maskp
)
1015 wide_int
get_nonzero_bits (const_tree
);
1017 if (TREE_CODE (operand
) == INTEGER_CST
)
1019 *valuep
= wi::to_widest (operand
);
1029 /* Meet operation, similar to ccp_lattice_meet, we xor values
1030 if this->value, value have different values at same bit positions, we want
1031 to drop that bit to varying. Return true if mask is changed.
1032 This function assumes that the lattice value is in CONSTANT state */
1035 ipcp_bits_lattice::meet_with_1 (widest_int value
, widest_int mask
,
1038 gcc_assert (constant_p ());
1040 widest_int old_mask
= m_mask
;
1041 m_mask
= (m_mask
| mask
) | (m_value
^ value
);
1043 if (wi::sext (m_mask
, precision
) == -1)
1044 return set_to_bottom ();
1046 return m_mask
!= old_mask
;
1049 /* Meet the bits lattice with operand
1050 described by <value, mask, sgn, precision. */
1053 ipcp_bits_lattice::meet_with (widest_int value
, widest_int mask
,
1061 if (wi::sext (mask
, precision
) == -1)
1062 return set_to_bottom ();
1063 return set_to_constant (value
, mask
);
1066 return meet_with_1 (value
, mask
, precision
);
1069 /* Meet bits lattice with the result of bit_value_binop (other, operand)
1070 if code is binary operation or bit_value_unop (other) if code is unary op.
1071 In the case when code is nop_expr, no adjustment is required. */
1074 ipcp_bits_lattice::meet_with (ipcp_bits_lattice
& other
, unsigned precision
,
1075 signop sgn
, enum tree_code code
, tree operand
)
1077 if (other
.bottom_p ())
1078 return set_to_bottom ();
1080 if (bottom_p () || other
.top_p ())
1083 widest_int adjusted_value
, adjusted_mask
;
1085 if (TREE_CODE_CLASS (code
) == tcc_binary
)
1087 tree type
= TREE_TYPE (operand
);
1088 widest_int o_value
, o_mask
;
1089 get_value_and_mask (operand
, &o_value
, &o_mask
);
1091 bit_value_binop (code
, sgn
, precision
, &adjusted_value
, &adjusted_mask
,
1092 sgn
, precision
, other
.get_value (), other
.get_mask (),
1093 TYPE_SIGN (type
), TYPE_PRECISION (type
), o_value
, o_mask
);
1095 if (wi::sext (adjusted_mask
, precision
) == -1)
1096 return set_to_bottom ();
1099 else if (TREE_CODE_CLASS (code
) == tcc_unary
)
1101 bit_value_unop (code
, sgn
, precision
, &adjusted_value
,
1102 &adjusted_mask
, sgn
, precision
, other
.get_value (),
1105 if (wi::sext (adjusted_mask
, precision
) == -1)
1106 return set_to_bottom ();
1110 return set_to_bottom ();
1114 if (wi::sext (adjusted_mask
, precision
) == -1)
1115 return set_to_bottom ();
1116 return set_to_constant (adjusted_value
, adjusted_mask
);
1119 return meet_with_1 (adjusted_value
, adjusted_mask
, precision
);
1122 /* Mark bot aggregate and scalar lattices as containing an unknown variable,
1123 return true is any of them has not been marked as such so far. */
1126 set_all_contains_variable (struct ipcp_param_lattices
*plats
)
1129 ret
= plats
->itself
.set_contains_variable ();
1130 ret
|= plats
->ctxlat
.set_contains_variable ();
1131 ret
|= set_agg_lats_contain_variable (plats
);
1132 ret
|= plats
->bits_lattice
.set_to_bottom ();
1133 ret
|= plats
->m_value_range
.set_to_bottom ();
1137 /* Worker of call_for_symbol_thunks_and_aliases, increment the integer DATA
1138 points to by the number of callers to NODE. */
1141 count_callers (cgraph_node
*node
, void *data
)
1143 int *caller_count
= (int *) data
;
1145 for (cgraph_edge
*cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
1146 /* Local thunks can be handled transparently, but if the thunk cannot
1147 be optimized out, count it as a real use. */
1148 if (!cs
->caller
->thunk
.thunk_p
|| !cs
->caller
->local
.local
)
1153 /* Worker of call_for_symbol_thunks_and_aliases, it is supposed to be called on
1154 the one caller of some other node. Set the caller's corresponding flag. */
1157 set_single_call_flag (cgraph_node
*node
, void *)
1159 cgraph_edge
*cs
= node
->callers
;
1160 /* Local thunks can be handled transparently, skip them. */
1161 while (cs
&& cs
->caller
->thunk
.thunk_p
&& cs
->caller
->local
.local
)
1162 cs
= cs
->next_caller
;
1165 IPA_NODE_REF (cs
->caller
)->node_calling_single_call
= true;
1171 /* Initialize ipcp_lattices. */
1174 initialize_node_lattices (struct cgraph_node
*node
)
1176 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1177 struct cgraph_edge
*ie
;
1178 bool disable
= false, variable
= false;
1181 gcc_checking_assert (node
->has_gimple_body_p ());
1182 if (node
->local
.local
)
1184 int caller_count
= 0;
1185 node
->call_for_symbol_thunks_and_aliases (count_callers
, &caller_count
,
1187 gcc_checking_assert (caller_count
> 0);
1188 if (caller_count
== 1)
1189 node
->call_for_symbol_thunks_and_aliases (set_single_call_flag
,
1194 /* When cloning is allowed, we can assume that externally visible
1195 functions are not called. We will compensate this by cloning
1197 if (ipcp_versionable_function_p (node
)
1198 && ipcp_cloning_candidate_p (node
))
1204 for (i
= 0; i
< ipa_get_param_count (info
); i
++)
1206 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1207 plats
->m_value_range
.init ();
1210 if (disable
|| variable
)
1212 for (i
= 0; i
< ipa_get_param_count (info
); i
++)
1214 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1217 plats
->itself
.set_to_bottom ();
1218 plats
->ctxlat
.set_to_bottom ();
1219 set_agg_lats_to_bottom (plats
);
1220 plats
->bits_lattice
.set_to_bottom ();
1221 plats
->m_value_range
.set_to_bottom ();
1224 set_all_contains_variable (plats
);
1226 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1227 && !node
->alias
&& !node
->thunk
.thunk_p
)
1228 fprintf (dump_file
, "Marking all lattices of %s as %s\n",
1229 node
->dump_name (), disable
? "BOTTOM" : "VARIABLE");
1232 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
1233 if (ie
->indirect_info
->polymorphic
1234 && ie
->indirect_info
->param_index
>= 0)
1236 gcc_checking_assert (ie
->indirect_info
->param_index
>= 0);
1237 ipa_get_parm_lattices (info
,
1238 ie
->indirect_info
->param_index
)->virt_call
= 1;
1242 /* Return the result of a (possibly arithmetic) pass through jump function
1243 JFUNC on the constant value INPUT. RES_TYPE is the type of the parameter
1244 to which the result is passed. Return NULL_TREE if that cannot be
1245 determined or be considered an interprocedural invariant. */
1248 ipa_get_jf_pass_through_result (struct ipa_jump_func
*jfunc
, tree input
,
1253 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
1255 if (!is_gimple_ip_invariant (input
))
1258 tree_code opcode
= ipa_get_jf_pass_through_operation (jfunc
);
1261 if (TREE_CODE_CLASS (opcode
) == tcc_comparison
)
1262 res_type
= boolean_type_node
;
1263 else if (expr_type_first_operand_type_p (opcode
))
1264 res_type
= TREE_TYPE (input
);
1269 if (TREE_CODE_CLASS (opcode
) == tcc_unary
)
1270 res
= fold_unary (opcode
, res_type
, input
);
1272 res
= fold_binary (opcode
, res_type
, input
,
1273 ipa_get_jf_pass_through_operand (jfunc
));
1275 if (res
&& !is_gimple_ip_invariant (res
))
1281 /* Return the result of an ancestor jump function JFUNC on the constant value
1282 INPUT. Return NULL_TREE if that cannot be determined. */
1285 ipa_get_jf_ancestor_result (struct ipa_jump_func
*jfunc
, tree input
)
1287 gcc_checking_assert (TREE_CODE (input
) != TREE_BINFO
);
1288 if (TREE_CODE (input
) == ADDR_EXPR
)
1290 tree t
= TREE_OPERAND (input
, 0);
1291 t
= build_ref_for_offset (EXPR_LOCATION (t
), t
,
1292 ipa_get_jf_ancestor_offset (jfunc
), false,
1293 ptr_type_node
, NULL
, false);
1294 return build_fold_addr_expr (t
);
1300 /* Determine whether JFUNC evaluates to a single known constant value and if
1301 so, return it. Otherwise return NULL. INFO describes the caller node or
1302 the one it is inlined to, so that pass-through jump functions can be
1303 evaluated. PARM_TYPE is the type of the parameter to which the result is
1307 ipa_value_from_jfunc (struct ipa_node_params
*info
, struct ipa_jump_func
*jfunc
,
1310 if (jfunc
->type
== IPA_JF_CONST
)
1311 return ipa_get_jf_constant (jfunc
);
1312 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1313 || jfunc
->type
== IPA_JF_ANCESTOR
)
1318 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1319 idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1321 idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1323 if (info
->ipcp_orig_node
)
1324 input
= info
->known_csts
[idx
];
1327 ipcp_lattice
<tree
> *lat
;
1330 || idx
>= ipa_get_param_count (info
))
1332 lat
= ipa_get_scalar_lat (info
, idx
);
1333 if (!lat
->is_single_const ())
1335 input
= lat
->values
->value
;
1341 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1342 return ipa_get_jf_pass_through_result (jfunc
, input
, parm_type
);
1344 return ipa_get_jf_ancestor_result (jfunc
, input
);
1350 /* Determine whether JFUNC evaluates to single known polymorphic context, given
1351 that INFO describes the caller node or the one it is inlined to, CS is the
1352 call graph edge corresponding to JFUNC and CSIDX index of the described
1355 ipa_polymorphic_call_context
1356 ipa_context_from_jfunc (ipa_node_params
*info
, cgraph_edge
*cs
, int csidx
,
1357 ipa_jump_func
*jfunc
)
1359 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
1360 ipa_polymorphic_call_context ctx
;
1361 ipa_polymorphic_call_context
*edge_ctx
1362 = cs
? ipa_get_ith_polymorhic_call_context (args
, csidx
) : NULL
;
1364 if (edge_ctx
&& !edge_ctx
->useless_p ())
1367 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1368 || jfunc
->type
== IPA_JF_ANCESTOR
)
1370 ipa_polymorphic_call_context srcctx
;
1372 bool type_preserved
= true;
1373 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1375 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1377 type_preserved
= ipa_get_jf_pass_through_type_preserved (jfunc
);
1378 srcidx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1382 type_preserved
= ipa_get_jf_ancestor_type_preserved (jfunc
);
1383 srcidx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1385 if (info
->ipcp_orig_node
)
1387 if (info
->known_contexts
.exists ())
1388 srcctx
= info
->known_contexts
[srcidx
];
1393 || srcidx
>= ipa_get_param_count (info
))
1395 ipcp_lattice
<ipa_polymorphic_call_context
> *lat
;
1396 lat
= ipa_get_poly_ctx_lat (info
, srcidx
);
1397 if (!lat
->is_single_const ())
1399 srcctx
= lat
->values
->value
;
1401 if (srcctx
.useless_p ())
1403 if (jfunc
->type
== IPA_JF_ANCESTOR
)
1404 srcctx
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
1405 if (!type_preserved
)
1406 srcctx
.possible_dynamic_type_change (cs
->in_polymorphic_cdtor
);
1407 srcctx
.combine_with (ctx
);
1414 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
1415 bottom, not containing a variable component and without any known value at
1419 ipcp_verify_propagated_values (void)
1421 struct cgraph_node
*node
;
1423 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
1425 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1426 int i
, count
= ipa_get_param_count (info
);
1428 for (i
= 0; i
< count
; i
++)
1430 ipcp_lattice
<tree
> *lat
= ipa_get_scalar_lat (info
, i
);
1433 && !lat
->contains_variable
1434 && lat
->values_count
== 0)
1438 symtab
->dump (dump_file
);
1439 fprintf (dump_file
, "\nIPA lattices after constant "
1440 "propagation, before gcc_unreachable:\n");
1441 print_all_lattices (dump_file
, true, false);
1450 /* Return true iff X and Y should be considered equal values by IPA-CP. */
1453 values_equal_for_ipcp_p (tree x
, tree y
)
1455 gcc_checking_assert (x
!= NULL_TREE
&& y
!= NULL_TREE
);
1460 if (TREE_CODE (x
) == ADDR_EXPR
1461 && TREE_CODE (y
) == ADDR_EXPR
1462 && TREE_CODE (TREE_OPERAND (x
, 0)) == CONST_DECL
1463 && TREE_CODE (TREE_OPERAND (y
, 0)) == CONST_DECL
)
1464 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x
, 0)),
1465 DECL_INITIAL (TREE_OPERAND (y
, 0)), 0);
1467 return operand_equal_p (x
, y
, 0);
1470 /* Return true iff X and Y should be considered equal contexts by IPA-CP. */
1473 values_equal_for_ipcp_p (ipa_polymorphic_call_context x
,
1474 ipa_polymorphic_call_context y
)
1476 return x
.equal_to (y
);
1480 /* Add a new value source to the value represented by THIS, marking that a
1481 value comes from edge CS and (if the underlying jump function is a
1482 pass-through or an ancestor one) from a caller value SRC_VAL of a caller
1483 parameter described by SRC_INDEX. OFFSET is negative if the source was the
1484 scalar value of the parameter itself or the offset within an aggregate. */
1486 template <typename valtype
>
1488 ipcp_value
<valtype
>::add_source (cgraph_edge
*cs
, ipcp_value
*src_val
,
1489 int src_idx
, HOST_WIDE_INT offset
)
1491 ipcp_value_source
<valtype
> *src
;
1493 src
= new (ipcp_sources_pool
.allocate ()) ipcp_value_source
<valtype
>;
1494 src
->offset
= offset
;
1497 src
->index
= src_idx
;
1499 src
->next
= sources
;
1503 /* Allocate a new ipcp_value holding a tree constant, initialize its value to
1504 SOURCE and clear all other fields. */
1506 static ipcp_value
<tree
> *
1507 allocate_and_init_ipcp_value (tree source
)
1509 ipcp_value
<tree
> *val
;
1511 val
= new (ipcp_cst_values_pool
.allocate ()) ipcp_value
<tree
>();
1512 val
->value
= source
;
1516 /* Allocate a new ipcp_value holding a polymorphic context, initialize its
1517 value to SOURCE and clear all other fields. */
1519 static ipcp_value
<ipa_polymorphic_call_context
> *
1520 allocate_and_init_ipcp_value (ipa_polymorphic_call_context source
)
1522 ipcp_value
<ipa_polymorphic_call_context
> *val
;
1525 val
= new (ipcp_poly_ctx_values_pool
.allocate ())
1526 ipcp_value
<ipa_polymorphic_call_context
>();
1527 val
->value
= source
;
1531 /* Try to add NEWVAL to LAT, potentially creating a new ipcp_value for it. CS,
1532 SRC_VAL SRC_INDEX and OFFSET are meant for add_source and have the same
1533 meaning. OFFSET -1 means the source is scalar and not a part of an
1536 template <typename valtype
>
1538 ipcp_lattice
<valtype
>::add_value (valtype newval
, cgraph_edge
*cs
,
1539 ipcp_value
<valtype
> *src_val
,
1540 int src_idx
, HOST_WIDE_INT offset
)
1542 ipcp_value
<valtype
> *val
;
1547 for (val
= values
; val
; val
= val
->next
)
1548 if (values_equal_for_ipcp_p (val
->value
, newval
))
1550 if (ipa_edge_within_scc (cs
))
1552 ipcp_value_source
<valtype
> *s
;
1553 for (s
= val
->sources
; s
; s
= s
->next
)
1560 val
->add_source (cs
, src_val
, src_idx
, offset
);
1564 if (values_count
== PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE
))
1566 /* We can only free sources, not the values themselves, because sources
1567 of other values in this SCC might point to them. */
1568 for (val
= values
; val
; val
= val
->next
)
1570 while (val
->sources
)
1572 ipcp_value_source
<valtype
> *src
= val
->sources
;
1573 val
->sources
= src
->next
;
1574 ipcp_sources_pool
.remove ((ipcp_value_source
<tree
>*)src
);
1579 return set_to_bottom ();
1583 val
= allocate_and_init_ipcp_value (newval
);
1584 val
->add_source (cs
, src_val
, src_idx
, offset
);
1590 /* Propagate values through a pass-through jump function JFUNC associated with
1591 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1592 is the index of the source parameter. PARM_TYPE is the type of the
1593 parameter to which the result is passed. */
1596 propagate_vals_across_pass_through (cgraph_edge
*cs
, ipa_jump_func
*jfunc
,
1597 ipcp_lattice
<tree
> *src_lat
,
1598 ipcp_lattice
<tree
> *dest_lat
, int src_idx
,
1601 ipcp_value
<tree
> *src_val
;
1604 /* Do not create new values when propagating within an SCC because if there
1605 are arithmetic functions with circular dependencies, there is infinite
1606 number of them and we would just make lattices bottom. If this condition
1607 is ever relaxed we have to detect self-feeding recursive calls in
1608 cgraph_edge_brings_value_p in a smarter way. */
1609 if ((ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1610 && ipa_edge_within_scc (cs
))
1611 ret
= dest_lat
->set_contains_variable ();
1613 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1615 tree cstval
= ipa_get_jf_pass_through_result (jfunc
, src_val
->value
,
1619 ret
|= dest_lat
->add_value (cstval
, cs
, src_val
, src_idx
);
1621 ret
|= dest_lat
->set_contains_variable ();
1627 /* Propagate values through an ancestor jump function JFUNC associated with
1628 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1629 is the index of the source parameter. */
1632 propagate_vals_across_ancestor (struct cgraph_edge
*cs
,
1633 struct ipa_jump_func
*jfunc
,
1634 ipcp_lattice
<tree
> *src_lat
,
1635 ipcp_lattice
<tree
> *dest_lat
, int src_idx
)
1637 ipcp_value
<tree
> *src_val
;
1640 if (ipa_edge_within_scc (cs
))
1641 return dest_lat
->set_contains_variable ();
1643 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1645 tree t
= ipa_get_jf_ancestor_result (jfunc
, src_val
->value
);
1648 ret
|= dest_lat
->add_value (t
, cs
, src_val
, src_idx
);
1650 ret
|= dest_lat
->set_contains_variable ();
1656 /* Propagate scalar values across jump function JFUNC that is associated with
1657 edge CS and put the values into DEST_LAT. PARM_TYPE is the type of the
1658 parameter to which the result is passed. */
1661 propagate_scalar_across_jump_function (struct cgraph_edge
*cs
,
1662 struct ipa_jump_func
*jfunc
,
1663 ipcp_lattice
<tree
> *dest_lat
,
1666 if (dest_lat
->bottom
)
1669 if (jfunc
->type
== IPA_JF_CONST
)
1671 tree val
= ipa_get_jf_constant (jfunc
);
1672 return dest_lat
->add_value (val
, cs
, NULL
, 0);
1674 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1675 || jfunc
->type
== IPA_JF_ANCESTOR
)
1677 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1678 ipcp_lattice
<tree
> *src_lat
;
1682 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1683 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1685 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1687 src_lat
= ipa_get_scalar_lat (caller_info
, src_idx
);
1688 if (src_lat
->bottom
)
1689 return dest_lat
->set_contains_variable ();
1691 /* If we would need to clone the caller and cannot, do not propagate. */
1692 if (!ipcp_versionable_function_p (cs
->caller
)
1693 && (src_lat
->contains_variable
1694 || (src_lat
->values_count
> 1)))
1695 return dest_lat
->set_contains_variable ();
1697 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1698 ret
= propagate_vals_across_pass_through (cs
, jfunc
, src_lat
,
1699 dest_lat
, src_idx
, param_type
);
1701 ret
= propagate_vals_across_ancestor (cs
, jfunc
, src_lat
, dest_lat
,
1704 if (src_lat
->contains_variable
)
1705 ret
|= dest_lat
->set_contains_variable ();
1710 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1711 use it for indirect inlining), we should propagate them too. */
1712 return dest_lat
->set_contains_variable ();
1715 /* Propagate scalar values across jump function JFUNC that is associated with
1716 edge CS and describes argument IDX and put the values into DEST_LAT. */
1719 propagate_context_across_jump_function (cgraph_edge
*cs
,
1720 ipa_jump_func
*jfunc
, int idx
,
1721 ipcp_lattice
<ipa_polymorphic_call_context
> *dest_lat
)
1723 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
1724 if (dest_lat
->bottom
)
1727 bool added_sth
= false;
1728 bool type_preserved
= true;
1730 ipa_polymorphic_call_context edge_ctx
, *edge_ctx_ptr
1731 = ipa_get_ith_polymorhic_call_context (args
, idx
);
1734 edge_ctx
= *edge_ctx_ptr
;
1736 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1737 || jfunc
->type
== IPA_JF_ANCESTOR
)
1739 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1741 ipcp_lattice
<ipa_polymorphic_call_context
> *src_lat
;
1743 /* TODO: Once we figure out how to propagate speculations, it will
1744 probably be a good idea to switch to speculation if type_preserved is
1745 not set instead of punting. */
1746 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1748 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1750 type_preserved
= ipa_get_jf_pass_through_type_preserved (jfunc
);
1751 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1755 type_preserved
= ipa_get_jf_ancestor_type_preserved (jfunc
);
1756 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1759 src_lat
= ipa_get_poly_ctx_lat (caller_info
, src_idx
);
1760 /* If we would need to clone the caller and cannot, do not propagate. */
1761 if (!ipcp_versionable_function_p (cs
->caller
)
1762 && (src_lat
->contains_variable
1763 || (src_lat
->values_count
> 1)))
1766 ipcp_value
<ipa_polymorphic_call_context
> *src_val
;
1767 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1769 ipa_polymorphic_call_context cur
= src_val
->value
;
1771 if (!type_preserved
)
1772 cur
.possible_dynamic_type_change (cs
->in_polymorphic_cdtor
);
1773 if (jfunc
->type
== IPA_JF_ANCESTOR
)
1774 cur
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
1775 /* TODO: In cases we know how the context is going to be used,
1776 we can improve the result by passing proper OTR_TYPE. */
1777 cur
.combine_with (edge_ctx
);
1778 if (!cur
.useless_p ())
1780 if (src_lat
->contains_variable
1781 && !edge_ctx
.equal_to (cur
))
1782 ret
|= dest_lat
->set_contains_variable ();
1783 ret
|= dest_lat
->add_value (cur
, cs
, src_val
, src_idx
);
1793 if (!edge_ctx
.useless_p ())
1794 ret
|= dest_lat
->add_value (edge_ctx
, cs
);
1796 ret
|= dest_lat
->set_contains_variable ();
1802 /* Propagate bits across jfunc that is associated with
1803 edge cs and update dest_lattice accordingly. */
1806 propagate_bits_across_jump_function (cgraph_edge
*cs
, int idx
,
1807 ipa_jump_func
*jfunc
,
1808 ipcp_bits_lattice
*dest_lattice
)
1810 if (dest_lattice
->bottom_p ())
1813 enum availability availability
;
1814 cgraph_node
*callee
= cs
->callee
->function_symbol (&availability
);
1815 struct ipa_node_params
*callee_info
= IPA_NODE_REF (callee
);
1816 tree parm_type
= ipa_get_type (callee_info
, idx
);
1818 /* For K&R C programs, ipa_get_type() could return NULL_TREE. Avoid the
1819 transform for these cases. Similarly, we can have bad type mismatches
1820 with LTO, avoid doing anything with those too. */
1822 || (!INTEGRAL_TYPE_P (parm_type
) && !POINTER_TYPE_P (parm_type
)))
1824 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1825 fprintf (dump_file
, "Setting dest_lattice to bottom, because type of "
1826 "param %i of %s is NULL or unsuitable for bits propagation\n",
1827 idx
, cs
->callee
->name ());
1829 return dest_lattice
->set_to_bottom ();
1832 unsigned precision
= TYPE_PRECISION (parm_type
);
1833 signop sgn
= TYPE_SIGN (parm_type
);
1835 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1836 || jfunc
->type
== IPA_JF_ANCESTOR
)
1838 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1839 tree operand
= NULL_TREE
;
1840 enum tree_code code
;
1843 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1845 code
= ipa_get_jf_pass_through_operation (jfunc
);
1846 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1847 if (code
!= NOP_EXPR
)
1848 operand
= ipa_get_jf_pass_through_operand (jfunc
);
1852 code
= POINTER_PLUS_EXPR
;
1853 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1854 unsigned HOST_WIDE_INT offset
= ipa_get_jf_ancestor_offset (jfunc
) / BITS_PER_UNIT
;
1855 operand
= build_int_cstu (size_type_node
, offset
);
1858 struct ipcp_param_lattices
*src_lats
1859 = ipa_get_parm_lattices (caller_info
, src_idx
);
1861 /* Try to propagate bits if src_lattice is bottom, but jfunc is known.
1867 Assume lattice for x is bottom, however we can still propagate
1868 result of x & 0xff == 0xff, which gets computed during ccp1 pass
1869 and we store it in jump function during analysis stage. */
1871 if (src_lats
->bits_lattice
.bottom_p ()
1873 return dest_lattice
->meet_with (jfunc
->bits
->value
, jfunc
->bits
->mask
,
1876 return dest_lattice
->meet_with (src_lats
->bits_lattice
, precision
, sgn
,
1880 else if (jfunc
->type
== IPA_JF_ANCESTOR
)
1881 return dest_lattice
->set_to_bottom ();
1882 else if (jfunc
->bits
)
1883 return dest_lattice
->meet_with (jfunc
->bits
->value
, jfunc
->bits
->mask
,
1886 return dest_lattice
->set_to_bottom ();
1889 /* Emulate effects of unary OPERATION and/or conversion from SRC_TYPE to
1890 DST_TYPE on value range in SRC_VR and store it to DST_VR. Return true if
1891 the result is a range or an anti-range. */
1894 ipa_vr_operation_and_type_effects (value_range_base
*dst_vr
,
1895 value_range_base
*src_vr
,
1896 enum tree_code operation
,
1897 tree dst_type
, tree src_type
)
1899 extract_range_from_unary_expr (dst_vr
, operation
, dst_type
,
1901 if (dst_vr
->varying_p () || dst_vr
->undefined_p ())
1906 /* Propagate value range across jump function JFUNC that is associated with
1907 edge CS with param of callee of PARAM_TYPE and update DEST_PLATS
1911 propagate_vr_across_jump_function (cgraph_edge
*cs
, ipa_jump_func
*jfunc
,
1912 struct ipcp_param_lattices
*dest_plats
,
1915 ipcp_vr_lattice
*dest_lat
= &dest_plats
->m_value_range
;
1917 if (dest_lat
->bottom_p ())
1921 || (!INTEGRAL_TYPE_P (param_type
)
1922 && !POINTER_TYPE_P (param_type
)))
1923 return dest_lat
->set_to_bottom ();
1925 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1927 enum tree_code operation
= ipa_get_jf_pass_through_operation (jfunc
);
1929 if (TREE_CODE_CLASS (operation
) == tcc_unary
)
1931 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1932 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1933 tree operand_type
= ipa_get_type (caller_info
, src_idx
);
1934 struct ipcp_param_lattices
*src_lats
1935 = ipa_get_parm_lattices (caller_info
, src_idx
);
1937 if (src_lats
->m_value_range
.bottom_p ())
1938 return dest_lat
->set_to_bottom ();
1939 value_range_base vr
;
1940 if (ipa_vr_operation_and_type_effects (&vr
,
1941 &src_lats
->m_value_range
.m_vr
,
1942 operation
, param_type
,
1944 return dest_lat
->meet_with (&vr
);
1947 else if (jfunc
->type
== IPA_JF_CONST
)
1949 tree val
= ipa_get_jf_constant (jfunc
);
1950 if (TREE_CODE (val
) == INTEGER_CST
)
1952 val
= fold_convert (param_type
, val
);
1953 if (TREE_OVERFLOW_P (val
))
1954 val
= drop_tree_overflow (val
);
1956 value_range_base
tmpvr (VR_RANGE
, val
, val
);
1957 return dest_lat
->meet_with (&tmpvr
);
1961 value_range_base vr
;
1963 && ipa_vr_operation_and_type_effects (&vr
, jfunc
->m_vr
, NOP_EXPR
,
1965 jfunc
->m_vr
->type ()))
1966 return dest_lat
->meet_with (&vr
);
1968 return dest_lat
->set_to_bottom ();
1971 /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
1972 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
1973 other cases, return false). If there are no aggregate items, set
1974 aggs_by_ref to NEW_AGGS_BY_REF. */
1977 set_check_aggs_by_ref (struct ipcp_param_lattices
*dest_plats
,
1978 bool new_aggs_by_ref
)
1980 if (dest_plats
->aggs
)
1982 if (dest_plats
->aggs_by_ref
!= new_aggs_by_ref
)
1984 set_agg_lats_to_bottom (dest_plats
);
1989 dest_plats
->aggs_by_ref
= new_aggs_by_ref
;
1993 /* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
1994 already existing lattice for the given OFFSET and SIZE, marking all skipped
1995 lattices as containing variable and checking for overlaps. If there is no
1996 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
1997 it with offset, size and contains_variable to PRE_EXISTING, and return true,
1998 unless there are too many already. If there are two many, return false. If
1999 there are overlaps turn whole DEST_PLATS to bottom and return false. If any
2000 skipped lattices were newly marked as containing variable, set *CHANGE to
2004 merge_agg_lats_step (struct ipcp_param_lattices
*dest_plats
,
2005 HOST_WIDE_INT offset
, HOST_WIDE_INT val_size
,
2006 struct ipcp_agg_lattice
***aglat
,
2007 bool pre_existing
, bool *change
)
2009 gcc_checking_assert (offset
>= 0);
2011 while (**aglat
&& (**aglat
)->offset
< offset
)
2013 if ((**aglat
)->offset
+ (**aglat
)->size
> offset
)
2015 set_agg_lats_to_bottom (dest_plats
);
2018 *change
|= (**aglat
)->set_contains_variable ();
2019 *aglat
= &(**aglat
)->next
;
2022 if (**aglat
&& (**aglat
)->offset
== offset
)
2024 if ((**aglat
)->size
!= val_size
2026 && (**aglat
)->next
->offset
< offset
+ val_size
))
2028 set_agg_lats_to_bottom (dest_plats
);
2031 gcc_checking_assert (!(**aglat
)->next
2032 || (**aglat
)->next
->offset
>= offset
+ val_size
);
2037 struct ipcp_agg_lattice
*new_al
;
2039 if (**aglat
&& (**aglat
)->offset
< offset
+ val_size
)
2041 set_agg_lats_to_bottom (dest_plats
);
2044 if (dest_plats
->aggs_count
== PARAM_VALUE (PARAM_IPA_MAX_AGG_ITEMS
))
2046 dest_plats
->aggs_count
++;
2047 new_al
= ipcp_agg_lattice_pool
.allocate ();
2048 memset (new_al
, 0, sizeof (*new_al
));
2050 new_al
->offset
= offset
;
2051 new_al
->size
= val_size
;
2052 new_al
->contains_variable
= pre_existing
;
2054 new_al
->next
= **aglat
;
2060 /* Set all AGLAT and all other aggregate lattices reachable by next pointers as
2061 containing an unknown value. */
2064 set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice
*aglat
)
2069 ret
|= aglat
->set_contains_variable ();
2070 aglat
= aglat
->next
;
2075 /* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
2076 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source
2077 parameter used for lattice value sources. Return true if DEST_PLATS changed
2081 merge_aggregate_lattices (struct cgraph_edge
*cs
,
2082 struct ipcp_param_lattices
*dest_plats
,
2083 struct ipcp_param_lattices
*src_plats
,
2084 int src_idx
, HOST_WIDE_INT offset_delta
)
2086 bool pre_existing
= dest_plats
->aggs
!= NULL
;
2087 struct ipcp_agg_lattice
**dst_aglat
;
2090 if (set_check_aggs_by_ref (dest_plats
, src_plats
->aggs_by_ref
))
2092 if (src_plats
->aggs_bottom
)
2093 return set_agg_lats_contain_variable (dest_plats
);
2094 if (src_plats
->aggs_contain_variable
)
2095 ret
|= set_agg_lats_contain_variable (dest_plats
);
2096 dst_aglat
= &dest_plats
->aggs
;
2098 for (struct ipcp_agg_lattice
*src_aglat
= src_plats
->aggs
;
2100 src_aglat
= src_aglat
->next
)
2102 HOST_WIDE_INT new_offset
= src_aglat
->offset
- offset_delta
;
2106 if (merge_agg_lats_step (dest_plats
, new_offset
, src_aglat
->size
,
2107 &dst_aglat
, pre_existing
, &ret
))
2109 struct ipcp_agg_lattice
*new_al
= *dst_aglat
;
2111 dst_aglat
= &(*dst_aglat
)->next
;
2112 if (src_aglat
->bottom
)
2114 ret
|= new_al
->set_contains_variable ();
2117 if (src_aglat
->contains_variable
)
2118 ret
|= new_al
->set_contains_variable ();
2119 for (ipcp_value
<tree
> *val
= src_aglat
->values
;
2122 ret
|= new_al
->add_value (val
->value
, cs
, val
, src_idx
,
2125 else if (dest_plats
->aggs_bottom
)
2128 ret
|= set_chain_of_aglats_contains_variable (*dst_aglat
);
2132 /* Determine whether there is anything to propagate FROM SRC_PLATS through a
2133 pass-through JFUNC and if so, whether it has conform and conforms to the
2134 rules about propagating values passed by reference. */
2137 agg_pass_through_permissible_p (struct ipcp_param_lattices
*src_plats
,
2138 struct ipa_jump_func
*jfunc
)
2140 return src_plats
->aggs
2141 && (!src_plats
->aggs_by_ref
2142 || ipa_get_jf_pass_through_agg_preserved (jfunc
));
2145 /* Propagate scalar values across jump function JFUNC that is associated with
2146 edge CS and put the values into DEST_LAT. */
2149 propagate_aggs_across_jump_function (struct cgraph_edge
*cs
,
2150 struct ipa_jump_func
*jfunc
,
2151 struct ipcp_param_lattices
*dest_plats
)
2155 if (dest_plats
->aggs_bottom
)
2158 if (jfunc
->type
== IPA_JF_PASS_THROUGH
2159 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
2161 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2162 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
2163 struct ipcp_param_lattices
*src_plats
;
2165 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2166 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
2168 /* Currently we do not produce clobber aggregate jump
2169 functions, replace with merging when we do. */
2170 gcc_assert (!jfunc
->agg
.items
);
2171 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
,
2175 ret
|= set_agg_lats_contain_variable (dest_plats
);
2177 else if (jfunc
->type
== IPA_JF_ANCESTOR
2178 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
2180 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2181 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
2182 struct ipcp_param_lattices
*src_plats
;
2184 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2185 if (src_plats
->aggs
&& src_plats
->aggs_by_ref
)
2187 /* Currently we do not produce clobber aggregate jump
2188 functions, replace with merging when we do. */
2189 gcc_assert (!jfunc
->agg
.items
);
2190 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
, src_idx
,
2191 ipa_get_jf_ancestor_offset (jfunc
));
2193 else if (!src_plats
->aggs_by_ref
)
2194 ret
|= set_agg_lats_to_bottom (dest_plats
);
2196 ret
|= set_agg_lats_contain_variable (dest_plats
);
2198 else if (jfunc
->agg
.items
)
2200 bool pre_existing
= dest_plats
->aggs
!= NULL
;
2201 struct ipcp_agg_lattice
**aglat
= &dest_plats
->aggs
;
2202 struct ipa_agg_jf_item
*item
;
2205 if (set_check_aggs_by_ref (dest_plats
, jfunc
->agg
.by_ref
))
2208 FOR_EACH_VEC_ELT (*jfunc
->agg
.items
, i
, item
)
2210 HOST_WIDE_INT val_size
;
2212 if (item
->offset
< 0)
2214 gcc_checking_assert (is_gimple_ip_invariant (item
->value
));
2215 val_size
= tree_to_uhwi (TYPE_SIZE (TREE_TYPE (item
->value
)));
2217 if (merge_agg_lats_step (dest_plats
, item
->offset
, val_size
,
2218 &aglat
, pre_existing
, &ret
))
2220 ret
|= (*aglat
)->add_value (item
->value
, cs
, NULL
, 0, 0);
2221 aglat
= &(*aglat
)->next
;
2223 else if (dest_plats
->aggs_bottom
)
2227 ret
|= set_chain_of_aglats_contains_variable (*aglat
);
2230 ret
|= set_agg_lats_contain_variable (dest_plats
);
2235 /* Return true if on the way cfrom CS->caller to the final (non-alias and
2236 non-thunk) destination, the call passes through a thunk. */
2239 call_passes_through_thunk_p (cgraph_edge
*cs
)
2241 cgraph_node
*alias_or_thunk
= cs
->callee
;
2242 while (alias_or_thunk
->alias
)
2243 alias_or_thunk
= alias_or_thunk
->get_alias_target ();
2244 return alias_or_thunk
->thunk
.thunk_p
;
2247 /* Propagate constants from the caller to the callee of CS. INFO describes the
2251 propagate_constants_across_call (struct cgraph_edge
*cs
)
2253 struct ipa_node_params
*callee_info
;
2254 enum availability availability
;
2255 cgraph_node
*callee
;
2256 struct ipa_edge_args
*args
;
2258 int i
, args_count
, parms_count
;
2260 callee
= cs
->callee
->function_symbol (&availability
);
2261 if (!callee
->definition
)
2263 gcc_checking_assert (callee
->has_gimple_body_p ());
2264 callee_info
= IPA_NODE_REF (callee
);
2266 args
= IPA_EDGE_REF (cs
);
2267 args_count
= ipa_get_cs_argument_count (args
);
2268 parms_count
= ipa_get_param_count (callee_info
);
2269 if (parms_count
== 0)
2272 /* If this call goes through a thunk we must not propagate to the first (0th)
2273 parameter. However, we might need to uncover a thunk from below a series
2274 of aliases first. */
2275 if (call_passes_through_thunk_p (cs
))
2277 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
2284 for (; (i
< args_count
) && (i
< parms_count
); i
++)
2286 struct ipa_jump_func
*jump_func
= ipa_get_ith_jump_func (args
, i
);
2287 struct ipcp_param_lattices
*dest_plats
;
2288 tree param_type
= ipa_get_type (callee_info
, i
);
2290 dest_plats
= ipa_get_parm_lattices (callee_info
, i
);
2291 if (availability
== AVAIL_INTERPOSABLE
)
2292 ret
|= set_all_contains_variable (dest_plats
);
2295 ret
|= propagate_scalar_across_jump_function (cs
, jump_func
,
2296 &dest_plats
->itself
,
2298 ret
|= propagate_context_across_jump_function (cs
, jump_func
, i
,
2299 &dest_plats
->ctxlat
);
2301 |= propagate_bits_across_jump_function (cs
, i
, jump_func
,
2302 &dest_plats
->bits_lattice
);
2303 ret
|= propagate_aggs_across_jump_function (cs
, jump_func
,
2305 if (opt_for_fn (callee
->decl
, flag_ipa_vrp
))
2306 ret
|= propagate_vr_across_jump_function (cs
, jump_func
,
2307 dest_plats
, param_type
);
2309 ret
|= dest_plats
->m_value_range
.set_to_bottom ();
2312 for (; i
< parms_count
; i
++)
2313 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
, i
));
2318 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
2319 KNOWN_CONTEXTS, KNOWN_AGGS or AGG_REPS return the destination. The latter
2320 three can be NULL. If AGG_REPS is not NULL, KNOWN_AGGS is ignored. */
2323 ipa_get_indirect_edge_target_1 (struct cgraph_edge
*ie
,
2324 vec
<tree
> known_csts
,
2325 vec
<ipa_polymorphic_call_context
> known_contexts
,
2326 vec
<ipa_agg_jump_function_p
> known_aggs
,
2327 struct ipa_agg_replacement_value
*agg_reps
,
2330 int param_index
= ie
->indirect_info
->param_index
;
2331 HOST_WIDE_INT anc_offset
;
2335 *speculative
= false;
2337 if (param_index
== -1
2338 || known_csts
.length () <= (unsigned int) param_index
)
2341 if (!ie
->indirect_info
->polymorphic
)
2345 if (ie
->indirect_info
->agg_contents
)
2348 if (agg_reps
&& ie
->indirect_info
->guaranteed_unmodified
)
2352 if (agg_reps
->index
== param_index
2353 && agg_reps
->offset
== ie
->indirect_info
->offset
2354 && agg_reps
->by_ref
== ie
->indirect_info
->by_ref
)
2356 t
= agg_reps
->value
;
2359 agg_reps
= agg_reps
->next
;
2364 struct ipa_agg_jump_function
*agg
;
2365 if (known_aggs
.length () > (unsigned int) param_index
)
2366 agg
= known_aggs
[param_index
];
2369 bool from_global_constant
;
2370 t
= ipa_find_agg_cst_for_param (agg
, known_csts
[param_index
],
2371 ie
->indirect_info
->offset
,
2372 ie
->indirect_info
->by_ref
,
2373 &from_global_constant
);
2375 && !from_global_constant
2376 && !ie
->indirect_info
->guaranteed_unmodified
)
2381 t
= known_csts
[param_index
];
2384 && TREE_CODE (t
) == ADDR_EXPR
2385 && TREE_CODE (TREE_OPERAND (t
, 0)) == FUNCTION_DECL
)
2386 return TREE_OPERAND (t
, 0);
2391 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize
))
2394 gcc_assert (!ie
->indirect_info
->agg_contents
);
2395 anc_offset
= ie
->indirect_info
->offset
;
2399 /* Try to work out value of virtual table pointer value in replacements. */
2400 if (!t
&& agg_reps
&& !ie
->indirect_info
->by_ref
)
2404 if (agg_reps
->index
== param_index
2405 && agg_reps
->offset
== ie
->indirect_info
->offset
2406 && agg_reps
->by_ref
)
2408 t
= agg_reps
->value
;
2411 agg_reps
= agg_reps
->next
;
2415 /* Try to work out value of virtual table pointer value in known
2416 aggregate values. */
2417 if (!t
&& known_aggs
.length () > (unsigned int) param_index
2418 && !ie
->indirect_info
->by_ref
)
2420 struct ipa_agg_jump_function
*agg
;
2421 agg
= known_aggs
[param_index
];
2422 t
= ipa_find_agg_cst_for_param (agg
, known_csts
[param_index
],
2423 ie
->indirect_info
->offset
, true);
2426 /* If we found the virtual table pointer, lookup the target. */
2430 unsigned HOST_WIDE_INT offset
;
2431 if (vtable_pointer_value_to_vtable (t
, &vtable
, &offset
))
2434 target
= gimple_get_virt_method_for_vtable (ie
->indirect_info
->otr_token
,
2435 vtable
, offset
, &can_refer
);
2439 || (TREE_CODE (TREE_TYPE (target
)) == FUNCTION_TYPE
2440 && DECL_FUNCTION_CODE (target
) == BUILT_IN_UNREACHABLE
)
2441 || !possible_polymorphic_call_target_p
2442 (ie
, cgraph_node::get (target
)))
2444 /* Do not speculate builtin_unreachable, it is stupid! */
2445 if (ie
->indirect_info
->vptr_changed
)
2447 target
= ipa_impossible_devirt_target (ie
, target
);
2449 *speculative
= ie
->indirect_info
->vptr_changed
;
2456 /* Do we know the constant value of pointer? */
2458 t
= known_csts
[param_index
];
2460 gcc_checking_assert (!t
|| TREE_CODE (t
) != TREE_BINFO
);
2462 ipa_polymorphic_call_context context
;
2463 if (known_contexts
.length () > (unsigned int) param_index
)
2465 context
= known_contexts
[param_index
];
2466 context
.offset_by (anc_offset
);
2467 if (ie
->indirect_info
->vptr_changed
)
2468 context
.possible_dynamic_type_change (ie
->in_polymorphic_cdtor
,
2469 ie
->indirect_info
->otr_type
);
2472 ipa_polymorphic_call_context ctx2
= ipa_polymorphic_call_context
2473 (t
, ie
->indirect_info
->otr_type
, anc_offset
);
2474 if (!ctx2
.useless_p ())
2475 context
.combine_with (ctx2
, ie
->indirect_info
->otr_type
);
2480 context
= ipa_polymorphic_call_context (t
, ie
->indirect_info
->otr_type
,
2482 if (ie
->indirect_info
->vptr_changed
)
2483 context
.possible_dynamic_type_change (ie
->in_polymorphic_cdtor
,
2484 ie
->indirect_info
->otr_type
);
2489 vec
<cgraph_node
*>targets
;
2492 targets
= possible_polymorphic_call_targets
2493 (ie
->indirect_info
->otr_type
,
2494 ie
->indirect_info
->otr_token
,
2496 if (!final
|| targets
.length () > 1)
2498 struct cgraph_node
*node
;
2501 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize_speculatively
)
2502 || ie
->speculative
|| !ie
->maybe_hot_p ())
2504 node
= try_speculative_devirtualization (ie
->indirect_info
->otr_type
,
2505 ie
->indirect_info
->otr_token
,
2509 *speculative
= true;
2510 target
= node
->decl
;
2517 *speculative
= false;
2518 if (targets
.length () == 1)
2519 target
= targets
[0]->decl
;
2521 target
= ipa_impossible_devirt_target (ie
, NULL_TREE
);
2524 if (target
&& !possible_polymorphic_call_target_p (ie
,
2525 cgraph_node::get (target
)))
2529 target
= ipa_impossible_devirt_target (ie
, target
);
2536 /* If an indirect edge IE can be turned into a direct one based on KNOWN_CSTS,
2537 KNOWN_CONTEXTS (which can be vNULL) or KNOWN_AGGS (which also can be vNULL)
2538 return the destination. */
2541 ipa_get_indirect_edge_target (struct cgraph_edge
*ie
,
2542 vec
<tree
> known_csts
,
2543 vec
<ipa_polymorphic_call_context
> known_contexts
,
2544 vec
<ipa_agg_jump_function_p
> known_aggs
,
2547 return ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
2548 known_aggs
, NULL
, speculative
);
2551 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
2552 and KNOWN_CONTEXTS. */
2555 devirtualization_time_bonus (struct cgraph_node
*node
,
2556 vec
<tree
> known_csts
,
2557 vec
<ipa_polymorphic_call_context
> known_contexts
,
2558 vec
<ipa_agg_jump_function_p
> known_aggs
)
2560 struct cgraph_edge
*ie
;
2563 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
2565 struct cgraph_node
*callee
;
2566 struct ipa_fn_summary
*isummary
;
2567 enum availability avail
;
2571 target
= ipa_get_indirect_edge_target (ie
, known_csts
, known_contexts
,
2572 known_aggs
, &speculative
);
2576 /* Only bare minimum benefit for clearly un-inlineable targets. */
2578 callee
= cgraph_node::get (target
);
2579 if (!callee
|| !callee
->definition
)
2581 callee
= callee
->function_symbol (&avail
);
2582 if (avail
< AVAIL_AVAILABLE
)
2584 isummary
= ipa_fn_summaries
->get (callee
);
2585 if (!isummary
->inlinable
)
2588 /* FIXME: The values below need re-considering and perhaps also
2589 integrating into the cost metrics, at lest in some very basic way. */
2590 if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 4)
2591 res
+= 31 / ((int)speculative
+ 1);
2592 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 2)
2593 res
+= 15 / ((int)speculative
+ 1);
2594 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
2595 || DECL_DECLARED_INLINE_P (callee
->decl
))
2596 res
+= 7 / ((int)speculative
+ 1);
2602 /* Return time bonus incurred because of HINTS. */
2605 hint_time_bonus (ipa_hints hints
)
2608 if (hints
& (INLINE_HINT_loop_iterations
| INLINE_HINT_loop_stride
))
2609 result
+= PARAM_VALUE (PARAM_IPA_CP_LOOP_HINT_BONUS
);
2610 if (hints
& INLINE_HINT_array_index
)
2611 result
+= PARAM_VALUE (PARAM_IPA_CP_ARRAY_INDEX_HINT_BONUS
);
2615 /* If there is a reason to penalize the function described by INFO in the
2616 cloning goodness evaluation, do so. */
2618 static inline int64_t
2619 incorporate_penalties (ipa_node_params
*info
, int64_t evaluation
)
2621 if (info
->node_within_scc
)
2622 evaluation
= (evaluation
2623 * (100 - PARAM_VALUE (PARAM_IPA_CP_RECURSION_PENALTY
))) / 100;
2625 if (info
->node_calling_single_call
)
2626 evaluation
= (evaluation
2627 * (100 - PARAM_VALUE (PARAM_IPA_CP_SINGLE_CALL_PENALTY
)))
2633 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
2634 and SIZE_COST and with the sum of frequencies of incoming edges to the
2635 potential new clone in FREQUENCIES. */
2638 good_cloning_opportunity_p (struct cgraph_node
*node
, int time_benefit
,
2639 int freq_sum
, profile_count count_sum
, int size_cost
)
2641 if (time_benefit
== 0
2642 || !opt_for_fn (node
->decl
, flag_ipa_cp_clone
)
2643 || node
->optimize_for_size_p ())
2646 gcc_assert (size_cost
> 0);
2648 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2649 if (max_count
> profile_count::zero ())
2651 int factor
= RDIV (count_sum
.probability_in
2652 (max_count
).to_reg_br_prob_base ()
2653 * 1000, REG_BR_PROB_BASE
);
2654 int64_t evaluation
= (((int64_t) time_benefit
* factor
)
2656 evaluation
= incorporate_penalties (info
, evaluation
);
2658 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2660 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
2661 "size: %i, count_sum: ", time_benefit
, size_cost
);
2662 count_sum
.dump (dump_file
);
2663 fprintf (dump_file
, "%s%s) -> evaluation: " "%" PRId64
2664 ", threshold: %i\n",
2665 info
->node_within_scc
? ", scc" : "",
2666 info
->node_calling_single_call
? ", single_call" : "",
2667 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
2670 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
2674 int64_t evaluation
= (((int64_t) time_benefit
* freq_sum
)
2676 evaluation
= incorporate_penalties (info
, evaluation
);
2678 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2679 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
2680 "size: %i, freq_sum: %i%s%s) -> evaluation: "
2681 "%" PRId64
", threshold: %i\n",
2682 time_benefit
, size_cost
, freq_sum
,
2683 info
->node_within_scc
? ", scc" : "",
2684 info
->node_calling_single_call
? ", single_call" : "",
2685 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
2687 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
2691 /* Return all context independent values from aggregate lattices in PLATS in a
2692 vector. Return NULL if there are none. */
2694 static vec
<ipa_agg_jf_item
, va_gc
> *
2695 context_independent_aggregate_values (struct ipcp_param_lattices
*plats
)
2697 vec
<ipa_agg_jf_item
, va_gc
> *res
= NULL
;
2699 if (plats
->aggs_bottom
2700 || plats
->aggs_contain_variable
2701 || plats
->aggs_count
== 0)
2704 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
;
2706 aglat
= aglat
->next
)
2707 if (aglat
->is_single_const ())
2709 struct ipa_agg_jf_item item
;
2710 item
.offset
= aglat
->offset
;
2711 item
.value
= aglat
->values
->value
;
2712 vec_safe_push (res
, item
);
2717 /* Allocate KNOWN_CSTS, KNOWN_CONTEXTS and, if non-NULL, KNOWN_AGGS and
2718 populate them with values of parameters that are known independent of the
2719 context. INFO describes the function. If REMOVABLE_PARAMS_COST is
2720 non-NULL, the movement cost of all removable parameters will be stored in
2724 gather_context_independent_values (struct ipa_node_params
*info
,
2725 vec
<tree
> *known_csts
,
2726 vec
<ipa_polymorphic_call_context
>
2728 vec
<ipa_agg_jump_function
> *known_aggs
,
2729 int *removable_params_cost
)
2731 int i
, count
= ipa_get_param_count (info
);
2734 known_csts
->create (0);
2735 known_contexts
->create (0);
2736 known_csts
->safe_grow_cleared (count
);
2737 known_contexts
->safe_grow_cleared (count
);
2740 known_aggs
->create (0);
2741 known_aggs
->safe_grow_cleared (count
);
2744 if (removable_params_cost
)
2745 *removable_params_cost
= 0;
2747 for (i
= 0; i
< count
; i
++)
2749 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2750 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
2752 if (lat
->is_single_const ())
2754 ipcp_value
<tree
> *val
= lat
->values
;
2755 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
2756 (*known_csts
)[i
] = val
->value
;
2757 if (removable_params_cost
)
2758 *removable_params_cost
2759 += estimate_move_cost (TREE_TYPE (val
->value
), false);
2762 else if (removable_params_cost
2763 && !ipa_is_param_used (info
, i
))
2764 *removable_params_cost
2765 += ipa_get_param_move_cost (info
, i
);
2767 if (!ipa_is_param_used (info
, i
))
2770 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
2771 /* Do not account known context as reason for cloning. We can see
2772 if it permits devirtualization. */
2773 if (ctxlat
->is_single_const ())
2774 (*known_contexts
)[i
] = ctxlat
->values
->value
;
2778 vec
<ipa_agg_jf_item
, va_gc
> *agg_items
;
2779 struct ipa_agg_jump_function
*ajf
;
2781 agg_items
= context_independent_aggregate_values (plats
);
2782 ajf
= &(*known_aggs
)[i
];
2783 ajf
->items
= agg_items
;
2784 ajf
->by_ref
= plats
->aggs_by_ref
;
2785 ret
|= agg_items
!= NULL
;
2792 /* The current interface in ipa-inline-analysis requires a pointer vector.
2795 FIXME: That interface should be re-worked, this is slightly silly. Still,
2796 I'd like to discuss how to change it first and this demonstrates the
2799 static vec
<ipa_agg_jump_function_p
>
2800 agg_jmp_p_vec_for_t_vec (vec
<ipa_agg_jump_function
> known_aggs
)
2802 vec
<ipa_agg_jump_function_p
> ret
;
2803 struct ipa_agg_jump_function
*ajf
;
2806 ret
.create (known_aggs
.length ());
2807 FOR_EACH_VEC_ELT (known_aggs
, i
, ajf
)
2808 ret
.quick_push (ajf
);
2812 /* Perform time and size measurement of NODE with the context given in
2813 KNOWN_CSTS, KNOWN_CONTEXTS and KNOWN_AGGS, calculate the benefit and cost
2814 given BASE_TIME of the node without specialization, REMOVABLE_PARAMS_COST of
2815 all context-independent removable parameters and EST_MOVE_COST of estimated
2816 movement of the considered parameter and store it into VAL. */
2819 perform_estimation_of_a_value (cgraph_node
*node
, vec
<tree
> known_csts
,
2820 vec
<ipa_polymorphic_call_context
> known_contexts
,
2821 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
,
2822 int removable_params_cost
,
2823 int est_move_cost
, ipcp_value_base
*val
)
2825 int size
, time_benefit
;
2826 sreal time
, base_time
;
2829 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
2830 known_aggs_ptrs
, &size
, &time
,
2831 &base_time
, &hints
);
2833 if (base_time
> 65535)
2836 /* Extern inline functions have no cloning local time benefits because they
2837 will be inlined anyway. The only reason to clone them is if it enables
2838 optimization in any of the functions they call. */
2839 if (DECL_EXTERNAL (node
->decl
) && DECL_DECLARED_INLINE_P (node
->decl
))
2842 time_benefit
= base_time
.to_int ()
2843 + devirtualization_time_bonus (node
, known_csts
, known_contexts
,
2845 + hint_time_bonus (hints
)
2846 + removable_params_cost
+ est_move_cost
;
2848 gcc_checking_assert (size
>=0);
2849 /* The inliner-heuristics based estimates may think that in certain
2850 contexts some functions do not have any size at all but we want
2851 all specializations to have at least a tiny cost, not least not to
2856 val
->local_time_benefit
= time_benefit
;
2857 val
->local_size_cost
= size
;
2860 /* Iterate over known values of parameters of NODE and estimate the local
2861 effects in terms of time and size they have. */
2864 estimate_local_effects (struct cgraph_node
*node
)
2866 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2867 int i
, count
= ipa_get_param_count (info
);
2868 vec
<tree
> known_csts
;
2869 vec
<ipa_polymorphic_call_context
> known_contexts
;
2870 vec
<ipa_agg_jump_function
> known_aggs
;
2871 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
;
2873 int removable_params_cost
;
2875 if (!count
|| !ipcp_versionable_function_p (node
))
2878 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2879 fprintf (dump_file
, "\nEstimating effects for %s.\n", node
->dump_name ());
2881 always_const
= gather_context_independent_values (info
, &known_csts
,
2882 &known_contexts
, &known_aggs
,
2883 &removable_params_cost
);
2884 known_aggs_ptrs
= agg_jmp_p_vec_for_t_vec (known_aggs
);
2885 int devirt_bonus
= devirtualization_time_bonus (node
, known_csts
,
2886 known_contexts
, known_aggs_ptrs
);
2887 if (always_const
|| devirt_bonus
2888 || (removable_params_cost
&& node
->local
.can_change_signature
))
2890 struct caller_statistics stats
;
2892 sreal time
, base_time
;
2895 init_caller_stats (&stats
);
2896 node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
2898 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
2899 known_aggs_ptrs
, &size
, &time
,
2900 &base_time
, &hints
);
2901 time
-= devirt_bonus
;
2902 time
-= hint_time_bonus (hints
);
2903 time
-= removable_params_cost
;
2904 size
-= stats
.n_calls
* removable_params_cost
;
2907 fprintf (dump_file
, " - context independent values, size: %i, "
2908 "time_benefit: %f\n", size
, (base_time
- time
).to_double ());
2910 if (size
<= 0 || node
->local
.local
)
2912 info
->do_clone_for_all_contexts
= true;
2915 fprintf (dump_file
, " Decided to specialize for all "
2916 "known contexts, code not going to grow.\n");
2918 else if (good_cloning_opportunity_p (node
,
2919 MIN ((base_time
- time
).to_int (),
2921 stats
.freq_sum
, stats
.count_sum
,
2924 if (size
+ overall_size
<= max_new_size
)
2926 info
->do_clone_for_all_contexts
= true;
2927 overall_size
+= size
;
2930 fprintf (dump_file
, " Decided to specialize for all "
2931 "known contexts, growth deemed beneficial.\n");
2933 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2934 fprintf (dump_file
, " Not cloning for all contexts because "
2935 "max_new_size would be reached with %li.\n",
2936 size
+ overall_size
);
2938 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2939 fprintf (dump_file
, " Not cloning for all contexts because "
2940 "!good_cloning_opportunity_p.\n");
2944 for (i
= 0; i
< count
; i
++)
2946 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2947 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
2948 ipcp_value
<tree
> *val
;
2955 for (val
= lat
->values
; val
; val
= val
->next
)
2957 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
2958 known_csts
[i
] = val
->value
;
2960 int emc
= estimate_move_cost (TREE_TYPE (val
->value
), true);
2961 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
2963 removable_params_cost
, emc
, val
);
2965 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2967 fprintf (dump_file
, " - estimates for value ");
2968 print_ipcp_constant_value (dump_file
, val
->value
);
2969 fprintf (dump_file
, " for ");
2970 ipa_dump_param (dump_file
, info
, i
);
2971 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
2972 val
->local_time_benefit
, val
->local_size_cost
);
2975 known_csts
[i
] = NULL_TREE
;
2978 for (i
= 0; i
< count
; i
++)
2980 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2982 if (!plats
->virt_call
)
2985 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
2986 ipcp_value
<ipa_polymorphic_call_context
> *val
;
2990 || !known_contexts
[i
].useless_p ())
2993 for (val
= ctxlat
->values
; val
; val
= val
->next
)
2995 known_contexts
[i
] = val
->value
;
2996 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
2998 removable_params_cost
, 0, val
);
3000 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3002 fprintf (dump_file
, " - estimates for polymorphic context ");
3003 print_ipcp_constant_value (dump_file
, val
->value
);
3004 fprintf (dump_file
, " for ");
3005 ipa_dump_param (dump_file
, info
, i
);
3006 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
3007 val
->local_time_benefit
, val
->local_size_cost
);
3010 known_contexts
[i
] = ipa_polymorphic_call_context ();
3013 for (i
= 0; i
< count
; i
++)
3015 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3016 struct ipa_agg_jump_function
*ajf
;
3017 struct ipcp_agg_lattice
*aglat
;
3019 if (plats
->aggs_bottom
|| !plats
->aggs
)
3022 ajf
= &known_aggs
[i
];
3023 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3025 ipcp_value
<tree
> *val
;
3026 if (aglat
->bottom
|| !aglat
->values
3027 /* If the following is true, the one value is in known_aggs. */
3028 || (!plats
->aggs_contain_variable
3029 && aglat
->is_single_const ()))
3032 for (val
= aglat
->values
; val
; val
= val
->next
)
3034 struct ipa_agg_jf_item item
;
3036 item
.offset
= aglat
->offset
;
3037 item
.value
= val
->value
;
3038 vec_safe_push (ajf
->items
, item
);
3040 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
3042 removable_params_cost
, 0, val
);
3044 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3046 fprintf (dump_file
, " - estimates for value ");
3047 print_ipcp_constant_value (dump_file
, val
->value
);
3048 fprintf (dump_file
, " for ");
3049 ipa_dump_param (dump_file
, info
, i
);
3050 fprintf (dump_file
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
3051 "]: time_benefit: %i, size: %i\n",
3052 plats
->aggs_by_ref
? "ref " : "",
3054 val
->local_time_benefit
, val
->local_size_cost
);
3062 for (i
= 0; i
< count
; i
++)
3063 vec_free (known_aggs
[i
].items
);
3065 known_csts
.release ();
3066 known_contexts
.release ();
3067 known_aggs
.release ();
3068 known_aggs_ptrs
.release ();
3072 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
3073 topological sort of values. */
3075 template <typename valtype
>
3077 value_topo_info
<valtype
>::add_val (ipcp_value
<valtype
> *cur_val
)
3079 ipcp_value_source
<valtype
> *src
;
3085 cur_val
->dfs
= dfs_counter
;
3086 cur_val
->low_link
= dfs_counter
;
3088 cur_val
->topo_next
= stack
;
3090 cur_val
->on_stack
= true;
3092 for (src
= cur_val
->sources
; src
; src
= src
->next
)
3095 if (src
->val
->dfs
== 0)
3098 if (src
->val
->low_link
< cur_val
->low_link
)
3099 cur_val
->low_link
= src
->val
->low_link
;
3101 else if (src
->val
->on_stack
3102 && src
->val
->dfs
< cur_val
->low_link
)
3103 cur_val
->low_link
= src
->val
->dfs
;
3106 if (cur_val
->dfs
== cur_val
->low_link
)
3108 ipcp_value
<valtype
> *v
, *scc_list
= NULL
;
3113 stack
= v
->topo_next
;
3114 v
->on_stack
= false;
3116 v
->scc_next
= scc_list
;
3119 while (v
!= cur_val
);
3121 cur_val
->topo_next
= values_topo
;
3122 values_topo
= cur_val
;
3126 /* Add all values in lattices associated with NODE to the topological sort if
3127 they are not there yet. */
3130 add_all_node_vals_to_toposort (cgraph_node
*node
, ipa_topo_info
*topo
)
3132 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3133 int i
, count
= ipa_get_param_count (info
);
3135 for (i
= 0; i
< count
; i
++)
3137 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3138 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
3139 struct ipcp_agg_lattice
*aglat
;
3143 ipcp_value
<tree
> *val
;
3144 for (val
= lat
->values
; val
; val
= val
->next
)
3145 topo
->constants
.add_val (val
);
3148 if (!plats
->aggs_bottom
)
3149 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3152 ipcp_value
<tree
> *val
;
3153 for (val
= aglat
->values
; val
; val
= val
->next
)
3154 topo
->constants
.add_val (val
);
3157 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
3158 if (!ctxlat
->bottom
)
3160 ipcp_value
<ipa_polymorphic_call_context
> *ctxval
;
3161 for (ctxval
= ctxlat
->values
; ctxval
; ctxval
= ctxval
->next
)
3162 topo
->contexts
.add_val (ctxval
);
3167 /* One pass of constants propagation along the call graph edges, from callers
3168 to callees (requires topological ordering in TOPO), iterate over strongly
3169 connected components. */
3172 propagate_constants_topo (struct ipa_topo_info
*topo
)
3176 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
3179 struct cgraph_node
*v
, *node
= topo
->order
[i
];
3180 vec
<cgraph_node
*> cycle_nodes
= ipa_get_nodes_in_cycle (node
);
3182 /* First, iteratively propagate within the strongly connected component
3183 until all lattices stabilize. */
3184 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
3185 if (v
->has_gimple_body_p ())
3186 push_node_to_stack (topo
, v
);
3188 v
= pop_node_from_stack (topo
);
3191 struct cgraph_edge
*cs
;
3193 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3194 if (ipa_edge_within_scc (cs
))
3196 IPA_NODE_REF (v
)->node_within_scc
= true;
3197 if (propagate_constants_across_call (cs
))
3198 push_node_to_stack (topo
, cs
->callee
->function_symbol ());
3200 v
= pop_node_from_stack (topo
);
3203 /* Afterwards, propagate along edges leading out of the SCC, calculates
3204 the local effects of the discovered constants and all valid values to
3205 their topological sort. */
3206 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
3207 if (v
->has_gimple_body_p ())
3209 struct cgraph_edge
*cs
;
3211 estimate_local_effects (v
);
3212 add_all_node_vals_to_toposort (v
, topo
);
3213 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3214 if (!ipa_edge_within_scc (cs
))
3215 propagate_constants_across_call (cs
);
3217 cycle_nodes
.release ();
3222 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
3223 the bigger one if otherwise. */
3226 safe_add (int a
, int b
)
3228 if (a
> INT_MAX
/2 || b
> INT_MAX
/2)
3229 return a
> b
? a
: b
;
3235 /* Propagate the estimated effects of individual values along the topological
3236 from the dependent values to those they depend on. */
3238 template <typename valtype
>
3240 value_topo_info
<valtype
>::propagate_effects ()
3242 ipcp_value
<valtype
> *base
;
3244 for (base
= values_topo
; base
; base
= base
->topo_next
)
3246 ipcp_value_source
<valtype
> *src
;
3247 ipcp_value
<valtype
> *val
;
3248 int time
= 0, size
= 0;
3250 for (val
= base
; val
; val
= val
->scc_next
)
3252 time
= safe_add (time
,
3253 val
->local_time_benefit
+ val
->prop_time_benefit
);
3254 size
= safe_add (size
, val
->local_size_cost
+ val
->prop_size_cost
);
3257 for (val
= base
; val
; val
= val
->scc_next
)
3258 for (src
= val
->sources
; src
; src
= src
->next
)
3260 && src
->cs
->maybe_hot_p ())
3262 src
->val
->prop_time_benefit
= safe_add (time
,
3263 src
->val
->prop_time_benefit
);
3264 src
->val
->prop_size_cost
= safe_add (size
,
3265 src
->val
->prop_size_cost
);
3271 /* Propagate constants, polymorphic contexts and their effects from the
3272 summaries interprocedurally. */
3275 ipcp_propagate_stage (struct ipa_topo_info
*topo
)
3277 struct cgraph_node
*node
;
3280 fprintf (dump_file
, "\n Propagating constants:\n\n");
3282 max_count
= profile_count::uninitialized ();
3284 FOR_EACH_DEFINED_FUNCTION (node
)
3286 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3288 determine_versionability (node
, info
);
3289 if (node
->has_gimple_body_p ())
3291 info
->lattices
= XCNEWVEC (struct ipcp_param_lattices
,
3292 ipa_get_param_count (info
));
3293 initialize_node_lattices (node
);
3295 ipa_fn_summary
*s
= ipa_fn_summaries
->get (node
);
3296 if (node
->definition
&& !node
->alias
&& s
!= NULL
)
3297 overall_size
+= s
->self_size
;
3298 max_count
= max_count
.max (node
->count
.ipa ());
3301 max_new_size
= overall_size
;
3302 if (max_new_size
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
3303 max_new_size
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
3304 max_new_size
+= max_new_size
* PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH
) / 100 + 1;
3307 fprintf (dump_file
, "\noverall_size: %li, max_new_size: %li\n",
3308 overall_size
, max_new_size
);
3310 propagate_constants_topo (topo
);
3312 ipcp_verify_propagated_values ();
3313 topo
->constants
.propagate_effects ();
3314 topo
->contexts
.propagate_effects ();
3318 fprintf (dump_file
, "\nIPA lattices after all propagation:\n");
3319 print_all_lattices (dump_file
, (dump_flags
& TDF_DETAILS
), true);
3323 /* Discover newly direct outgoing edges from NODE which is a new clone with
3324 known KNOWN_CSTS and make them direct. */
3327 ipcp_discover_new_direct_edges (struct cgraph_node
*node
,
3328 vec
<tree
> known_csts
,
3329 vec
<ipa_polymorphic_call_context
>
3331 struct ipa_agg_replacement_value
*aggvals
)
3333 struct cgraph_edge
*ie
, *next_ie
;
3336 for (ie
= node
->indirect_calls
; ie
; ie
= next_ie
)
3341 next_ie
= ie
->next_callee
;
3342 target
= ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
3343 vNULL
, aggvals
, &speculative
);
3346 bool agg_contents
= ie
->indirect_info
->agg_contents
;
3347 bool polymorphic
= ie
->indirect_info
->polymorphic
;
3348 int param_index
= ie
->indirect_info
->param_index
;
3349 struct cgraph_edge
*cs
= ipa_make_edge_direct_to_target (ie
, target
,
3353 if (cs
&& !agg_contents
&& !polymorphic
)
3355 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3356 int c
= ipa_get_controlled_uses (info
, param_index
);
3357 if (c
!= IPA_UNDESCRIBED_USE
)
3359 struct ipa_ref
*to_del
;
3362 ipa_set_controlled_uses (info
, param_index
, c
);
3363 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3364 fprintf (dump_file
, " controlled uses count of param "
3365 "%i bumped down to %i\n", param_index
, c
);
3367 && (to_del
= node
->find_reference (cs
->callee
, NULL
, 0)))
3369 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3370 fprintf (dump_file
, " and even removing its "
3371 "cloning-created reference\n");
3372 to_del
->remove_reference ();
3378 /* Turning calls to direct calls will improve overall summary. */
3380 ipa_update_overall_fn_summary (node
);
3383 class edge_clone_summary
;
3384 static call_summary
<edge_clone_summary
*> *edge_clone_summaries
= NULL
;
3386 /* Edge clone summary. */
3388 struct edge_clone_summary
3390 /* Default constructor. */
3391 edge_clone_summary (): prev_clone (NULL
), next_clone (NULL
) {}
3393 /* Default destructor. */
3394 ~edge_clone_summary ()
3397 edge_clone_summaries
->get (prev_clone
)->next_clone
= next_clone
;
3399 edge_clone_summaries
->get (next_clone
)->prev_clone
= prev_clone
;
3402 cgraph_edge
*prev_clone
;
3403 cgraph_edge
*next_clone
;
3406 class edge_clone_summary_t
:
3407 public call_summary
<edge_clone_summary
*>
3410 edge_clone_summary_t (symbol_table
*symtab
):
3411 call_summary
<edge_clone_summary
*> (symtab
)
3413 m_initialize_when_cloning
= true;
3416 virtual void duplicate (cgraph_edge
*src_edge
, cgraph_edge
*dst_edge
,
3417 edge_clone_summary
*src_data
,
3418 edge_clone_summary
*dst_data
);
3421 /* Edge duplication hook. */
3424 edge_clone_summary_t::duplicate (cgraph_edge
*src_edge
, cgraph_edge
*dst_edge
,
3425 edge_clone_summary
*src_data
,
3426 edge_clone_summary
*dst_data
)
3428 if (src_data
->next_clone
)
3429 edge_clone_summaries
->get (src_data
->next_clone
)->prev_clone
= dst_edge
;
3430 dst_data
->prev_clone
= src_edge
;
3431 dst_data
->next_clone
= src_data
->next_clone
;
3432 src_data
->next_clone
= dst_edge
;
3435 /* See if NODE is a clone with a known aggregate value at a given OFFSET of a
3436 parameter with the given INDEX. */
3439 get_clone_agg_value (struct cgraph_node
*node
, HOST_WIDE_INT offset
,
3442 struct ipa_agg_replacement_value
*aggval
;
3444 aggval
= ipa_get_agg_replacements_for_node (node
);
3447 if (aggval
->offset
== offset
3448 && aggval
->index
== index
)
3449 return aggval
->value
;
3450 aggval
= aggval
->next
;
3455 /* Return true is NODE is DEST or its clone for all contexts. */
3458 same_node_or_its_all_contexts_clone_p (cgraph_node
*node
, cgraph_node
*dest
)
3463 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3464 return info
->is_all_contexts_clone
&& info
->ipcp_orig_node
== dest
;
3467 /* Return true if edge CS does bring about the value described by SRC to
3468 DEST_VAL of node DEST or its clone for all contexts. */
3471 cgraph_edge_brings_value_p (cgraph_edge
*cs
, ipcp_value_source
<tree
> *src
,
3472 cgraph_node
*dest
, ipcp_value
<tree
> *dest_val
)
3474 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3475 enum availability availability
;
3476 cgraph_node
*real_dest
= cs
->callee
->function_symbol (&availability
);
3478 if (!same_node_or_its_all_contexts_clone_p (real_dest
, dest
)
3479 || availability
<= AVAIL_INTERPOSABLE
3480 || caller_info
->node_dead
)
3486 if (caller_info
->ipcp_orig_node
)
3489 if (src
->offset
== -1)
3490 t
= caller_info
->known_csts
[src
->index
];
3492 t
= get_clone_agg_value (cs
->caller
, src
->offset
, src
->index
);
3493 return (t
!= NULL_TREE
3494 && values_equal_for_ipcp_p (src
->val
->value
, t
));
3498 /* At the moment we do not propagate over arithmetic jump functions in
3499 SCCs, so it is safe to detect self-feeding recursive calls in this
3501 if (src
->val
== dest_val
)
3504 struct ipcp_agg_lattice
*aglat
;
3505 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
3507 if (src
->offset
== -1)
3508 return (plats
->itself
.is_single_const ()
3509 && values_equal_for_ipcp_p (src
->val
->value
,
3510 plats
->itself
.values
->value
));
3513 if (plats
->aggs_bottom
|| plats
->aggs_contain_variable
)
3515 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3516 if (aglat
->offset
== src
->offset
)
3517 return (aglat
->is_single_const ()
3518 && values_equal_for_ipcp_p (src
->val
->value
,
3519 aglat
->values
->value
));
3525 /* Return true if edge CS does bring about the value described by SRC to
3526 DST_VAL of node DEST or its clone for all contexts. */
3529 cgraph_edge_brings_value_p (cgraph_edge
*cs
,
3530 ipcp_value_source
<ipa_polymorphic_call_context
> *src
,
3532 ipcp_value
<ipa_polymorphic_call_context
> *)
3534 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3535 cgraph_node
*real_dest
= cs
->callee
->function_symbol ();
3537 if (!same_node_or_its_all_contexts_clone_p (real_dest
, dest
)
3538 || caller_info
->node_dead
)
3543 if (caller_info
->ipcp_orig_node
)
3544 return (caller_info
->known_contexts
.length () > (unsigned) src
->index
)
3545 && values_equal_for_ipcp_p (src
->val
->value
,
3546 caller_info
->known_contexts
[src
->index
]);
3548 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
3550 return plats
->ctxlat
.is_single_const ()
3551 && values_equal_for_ipcp_p (src
->val
->value
,
3552 plats
->ctxlat
.values
->value
);
3555 /* Get the next clone in the linked list of clones of an edge. */
3557 static inline struct cgraph_edge
*
3558 get_next_cgraph_edge_clone (struct cgraph_edge
*cs
)
3560 edge_clone_summary
*s
= edge_clone_summaries
->get (cs
);
3561 return s
!= NULL
? s
->next_clone
: NULL
;
3564 /* Given VAL that is intended for DEST, iterate over all its sources and if any
3565 of them is viable and hot, return true. In that case, for those that still
3566 hold, add their edge frequency and their number into *FREQUENCY and
3567 *CALLER_COUNT respectively. */
3569 template <typename valtype
>
3571 get_info_about_necessary_edges (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
3573 profile_count
*count_sum
, int *caller_count
)
3575 ipcp_value_source
<valtype
> *src
;
3576 int freq
= 0, count
= 0;
3577 profile_count cnt
= profile_count::zero ();
3579 bool non_self_recursive
= false;
3581 for (src
= val
->sources
; src
; src
= src
->next
)
3583 struct cgraph_edge
*cs
= src
->cs
;
3586 if (cgraph_edge_brings_value_p (cs
, src
, dest
, val
))
3589 freq
+= cs
->frequency ();
3590 if (cs
->count
.ipa ().initialized_p ())
3591 cnt
+= cs
->count
.ipa ();
3592 hot
|= cs
->maybe_hot_p ();
3593 if (cs
->caller
!= dest
)
3594 non_self_recursive
= true;
3596 cs
= get_next_cgraph_edge_clone (cs
);
3600 /* If the only edges bringing a value are self-recursive ones, do not bother
3602 if (!non_self_recursive
)
3607 *caller_count
= count
;
3611 /* Return a vector of incoming edges that do bring value VAL to node DEST. It
3612 is assumed their number is known and equal to CALLER_COUNT. */
3614 template <typename valtype
>
3615 static vec
<cgraph_edge
*>
3616 gather_edges_for_value (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
3619 ipcp_value_source
<valtype
> *src
;
3620 vec
<cgraph_edge
*> ret
;
3622 ret
.create (caller_count
);
3623 for (src
= val
->sources
; src
; src
= src
->next
)
3625 struct cgraph_edge
*cs
= src
->cs
;
3628 if (cgraph_edge_brings_value_p (cs
, src
, dest
, val
))
3629 ret
.quick_push (cs
);
3630 cs
= get_next_cgraph_edge_clone (cs
);
3637 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
3638 Return it or NULL if for some reason it cannot be created. */
3640 static struct ipa_replace_map
*
3641 get_replacement_map (struct ipa_node_params
*info
, tree value
, int parm_num
)
3643 struct ipa_replace_map
*replace_map
;
3646 replace_map
= ggc_alloc
<ipa_replace_map
> ();
3649 fprintf (dump_file
, " replacing ");
3650 ipa_dump_param (dump_file
, info
, parm_num
);
3652 fprintf (dump_file
, " with const ");
3653 print_generic_expr (dump_file
, value
);
3654 fprintf (dump_file
, "\n");
3656 replace_map
->old_tree
= NULL
;
3657 replace_map
->parm_num
= parm_num
;
3658 replace_map
->new_tree
= value
;
3659 replace_map
->replace_p
= true;
3660 replace_map
->ref_p
= false;
3665 /* Dump new profiling counts */
3668 dump_profile_updates (struct cgraph_node
*orig_node
,
3669 struct cgraph_node
*new_node
)
3671 struct cgraph_edge
*cs
;
3673 fprintf (dump_file
, " setting count of the specialized node to ");
3674 new_node
->count
.dump (dump_file
);
3675 fprintf (dump_file
, "\n");
3676 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3678 fprintf (dump_file
, " edge to %s has count ",
3679 cs
->callee
->name ());
3680 cs
->count
.dump (dump_file
);
3681 fprintf (dump_file
, "\n");
3684 fprintf (dump_file
, " setting count of the original node to ");
3685 orig_node
->count
.dump (dump_file
);
3686 fprintf (dump_file
, "\n");
3687 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3689 fprintf (dump_file
, " edge to %s is left with ",
3690 cs
->callee
->name ());
3691 cs
->count
.dump (dump_file
);
3692 fprintf (dump_file
, "\n");
3696 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
3697 their profile information to reflect this. */
3700 update_profiling_info (struct cgraph_node
*orig_node
,
3701 struct cgraph_node
*new_node
)
3703 struct cgraph_edge
*cs
;
3704 struct caller_statistics stats
;
3705 profile_count new_sum
, orig_sum
;
3706 profile_count remainder
, orig_node_count
= orig_node
->count
;
3708 if (!(orig_node_count
.ipa () > profile_count::zero ()))
3711 init_caller_stats (&stats
);
3712 orig_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
3714 orig_sum
= stats
.count_sum
;
3715 init_caller_stats (&stats
);
3716 new_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
3718 new_sum
= stats
.count_sum
;
3720 if (orig_node_count
< orig_sum
+ new_sum
)
3724 fprintf (dump_file
, " Problem: node %s has too low count ",
3725 orig_node
->dump_name ());
3726 orig_node_count
.dump (dump_file
);
3727 fprintf (dump_file
, "while the sum of incoming count is ");
3728 (orig_sum
+ new_sum
).dump (dump_file
);
3729 fprintf (dump_file
, "\n");
3732 orig_node_count
= (orig_sum
+ new_sum
).apply_scale (12, 10);
3735 fprintf (dump_file
, " proceeding by pretending it was ");
3736 orig_node_count
.dump (dump_file
);
3737 fprintf (dump_file
, "\n");
3741 remainder
= orig_node_count
.combine_with_ipa_count (orig_node_count
.ipa ()
3743 new_sum
= orig_node_count
.combine_with_ipa_count (new_sum
);
3744 orig_node
->count
= remainder
;
3746 profile_count::adjust_for_ipa_scaling (&new_sum
, &orig_node_count
);
3747 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3748 cs
->count
= cs
->count
.apply_scale (new_sum
, orig_node_count
);
3750 profile_count::adjust_for_ipa_scaling (&remainder
, &orig_node_count
);
3751 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3752 cs
->count
= cs
->count
.apply_scale (remainder
, orig_node_count
);
3755 dump_profile_updates (orig_node
, new_node
);
3758 /* Update the respective profile of specialized NEW_NODE and the original
3759 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
3760 have been redirected to the specialized version. */
3763 update_specialized_profile (struct cgraph_node
*new_node
,
3764 struct cgraph_node
*orig_node
,
3765 profile_count redirected_sum
)
3767 struct cgraph_edge
*cs
;
3768 profile_count new_node_count
, orig_node_count
= orig_node
->count
;
3772 fprintf (dump_file
, " the sum of counts of redirected edges is ");
3773 redirected_sum
.dump (dump_file
);
3774 fprintf (dump_file
, "\n");
3776 if (!(orig_node_count
> profile_count::zero ()))
3779 gcc_assert (orig_node_count
>= redirected_sum
);
3781 new_node_count
= new_node
->count
;
3782 new_node
->count
+= redirected_sum
;
3783 orig_node
->count
-= redirected_sum
;
3785 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3786 cs
->count
+= cs
->count
.apply_scale (redirected_sum
, new_node_count
);
3788 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3790 profile_count dec
= cs
->count
.apply_scale (redirected_sum
,
3796 dump_profile_updates (orig_node
, new_node
);
3799 /* Create a specialized version of NODE with known constants in KNOWN_CSTS,
3800 known contexts in KNOWN_CONTEXTS and known aggregate values in AGGVALS and
3801 redirect all edges in CALLERS to it. */
3803 static struct cgraph_node
*
3804 create_specialized_node (struct cgraph_node
*node
,
3805 vec
<tree
> known_csts
,
3806 vec
<ipa_polymorphic_call_context
> known_contexts
,
3807 struct ipa_agg_replacement_value
*aggvals
,
3808 vec
<cgraph_edge
*> callers
)
3810 struct ipa_node_params
*new_info
, *info
= IPA_NODE_REF (node
);
3811 vec
<ipa_replace_map
*, va_gc
> *replace_trees
= NULL
;
3812 struct ipa_agg_replacement_value
*av
;
3813 struct cgraph_node
*new_node
;
3814 int i
, count
= ipa_get_param_count (info
);
3815 bitmap args_to_skip
;
3817 gcc_assert (!info
->ipcp_orig_node
);
3819 if (node
->local
.can_change_signature
)
3821 args_to_skip
= BITMAP_GGC_ALLOC ();
3822 for (i
= 0; i
< count
; i
++)
3824 tree t
= known_csts
[i
];
3826 if (t
|| !ipa_is_param_used (info
, i
))
3827 bitmap_set_bit (args_to_skip
, i
);
3832 args_to_skip
= NULL
;
3833 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3834 fprintf (dump_file
, " cannot change function signature\n");
3837 for (i
= 0; i
< count
; i
++)
3839 tree t
= known_csts
[i
];
3842 struct ipa_replace_map
*replace_map
;
3844 gcc_checking_assert (TREE_CODE (t
) != TREE_BINFO
);
3845 replace_map
= get_replacement_map (info
, t
, i
);
3847 vec_safe_push (replace_trees
, replace_map
);
3850 auto_vec
<cgraph_edge
*, 2> self_recursive_calls
;
3851 for (i
= callers
.length () - 1; i
>= 0; i
--)
3853 cgraph_edge
*cs
= callers
[i
];
3854 if (cs
->caller
== node
)
3856 self_recursive_calls
.safe_push (cs
);
3857 callers
.unordered_remove (i
);
3861 unsigned &suffix_counter
= clone_num_suffixes
->get_or_insert (
3862 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (
3864 new_node
= node
->create_virtual_clone (callers
, replace_trees
,
3865 args_to_skip
, "constprop",
3869 bool have_self_recursive_calls
= !self_recursive_calls
.is_empty ();
3870 for (unsigned j
= 0; j
< self_recursive_calls
.length (); j
++)
3872 cgraph_edge
*cs
= get_next_cgraph_edge_clone (self_recursive_calls
[j
]);
3873 /* Cloned edges can disappear during cloning as speculation can be
3874 resolved, check that we have one and that it comes from the last
3876 if (cs
&& cs
->caller
== new_node
)
3877 cs
->redirect_callee_duplicating_thunks (new_node
);
3878 /* Any future code that would make more than one clone of an outgoing
3879 edge would confuse this mechanism, so let's check that does not
3881 gcc_checking_assert (!cs
3882 || !get_next_cgraph_edge_clone (cs
)
3883 || get_next_cgraph_edge_clone (cs
)->caller
!= new_node
);
3885 if (have_self_recursive_calls
)
3886 new_node
->expand_all_artificial_thunks ();
3888 ipa_set_node_agg_value_chain (new_node
, aggvals
);
3889 for (av
= aggvals
; av
; av
= av
->next
)
3890 new_node
->maybe_create_reference (av
->value
, NULL
);
3892 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3894 fprintf (dump_file
, " the new node is %s.\n", new_node
->dump_name ());
3895 if (known_contexts
.exists ())
3897 for (i
= 0; i
< count
; i
++)
3898 if (!known_contexts
[i
].useless_p ())
3900 fprintf (dump_file
, " known ctx %i is ", i
);
3901 known_contexts
[i
].dump (dump_file
);
3905 ipa_dump_agg_replacement_values (dump_file
, aggvals
);
3907 ipa_check_create_node_params ();
3908 update_profiling_info (node
, new_node
);
3909 new_info
= IPA_NODE_REF (new_node
);
3910 new_info
->ipcp_orig_node
= node
;
3911 new_info
->known_csts
= known_csts
;
3912 new_info
->known_contexts
= known_contexts
;
3914 ipcp_discover_new_direct_edges (new_node
, known_csts
, known_contexts
, aggvals
);
3920 /* Return true, if JFUNC, which describes a i-th parameter of call CS, is a
3921 simple no-operation pass-through function to itself. */
3924 self_recursive_pass_through_p (cgraph_edge
*cs
, ipa_jump_func
*jfunc
, int i
)
3926 enum availability availability
;
3927 if (cs
->caller
== cs
->callee
->function_symbol (&availability
)
3928 && availability
> AVAIL_INTERPOSABLE
3929 && jfunc
->type
== IPA_JF_PASS_THROUGH
3930 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
3931 && ipa_get_jf_pass_through_formal_id (jfunc
) == i
)
3936 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
3937 KNOWN_CSTS with constants that are also known for all of the CALLERS. */
3940 find_more_scalar_values_for_callers_subset (struct cgraph_node
*node
,
3941 vec
<tree
> known_csts
,
3942 vec
<cgraph_edge
*> callers
)
3944 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3945 int i
, count
= ipa_get_param_count (info
);
3947 for (i
= 0; i
< count
; i
++)
3949 struct cgraph_edge
*cs
;
3950 tree newval
= NULL_TREE
;
3953 tree type
= ipa_get_type (info
, i
);
3955 if (ipa_get_scalar_lat (info
, i
)->bottom
|| known_csts
[i
])
3958 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3960 struct ipa_jump_func
*jump_func
;
3963 if (IPA_NODE_REF (cs
->caller
)->node_dead
)
3966 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
))
3968 && call_passes_through_thunk_p (cs
)))
3973 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
3974 if (self_recursive_pass_through_p (cs
, jump_func
, i
))
3977 t
= ipa_value_from_jfunc (IPA_NODE_REF (cs
->caller
), jump_func
, type
);
3980 && !values_equal_for_ipcp_p (t
, newval
))
3981 || (!first
&& !newval
))
3993 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3995 fprintf (dump_file
, " adding an extra known scalar value ");
3996 print_ipcp_constant_value (dump_file
, newval
);
3997 fprintf (dump_file
, " for ");
3998 ipa_dump_param (dump_file
, info
, i
);
3999 fprintf (dump_file
, "\n");
4002 known_csts
[i
] = newval
;
4007 /* Given a NODE and a subset of its CALLERS, try to populate plank slots in
4008 KNOWN_CONTEXTS with polymorphic contexts that are also known for all of the
4012 find_more_contexts_for_caller_subset (cgraph_node
*node
,
4013 vec
<ipa_polymorphic_call_context
>
4015 vec
<cgraph_edge
*> callers
)
4017 ipa_node_params
*info
= IPA_NODE_REF (node
);
4018 int i
, count
= ipa_get_param_count (info
);
4020 for (i
= 0; i
< count
; i
++)
4024 if (ipa_get_poly_ctx_lat (info
, i
)->bottom
4025 || (known_contexts
->exists ()
4026 && !(*known_contexts
)[i
].useless_p ()))
4029 ipa_polymorphic_call_context newval
;
4033 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4035 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
)))
4037 ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
),
4039 ipa_polymorphic_call_context ctx
;
4040 ctx
= ipa_context_from_jfunc (IPA_NODE_REF (cs
->caller
), cs
, i
,
4048 newval
.meet_with (ctx
);
4049 if (newval
.useless_p ())
4053 if (!newval
.useless_p ())
4055 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4057 fprintf (dump_file
, " adding an extra known polymorphic "
4059 print_ipcp_constant_value (dump_file
, newval
);
4060 fprintf (dump_file
, " for ");
4061 ipa_dump_param (dump_file
, info
, i
);
4062 fprintf (dump_file
, "\n");
4065 if (!known_contexts
->exists ())
4066 known_contexts
->safe_grow_cleared (ipa_get_param_count (info
));
4067 (*known_contexts
)[i
] = newval
;
4073 /* Go through PLATS and create a vector of values consisting of values and
4074 offsets (minus OFFSET) of lattices that contain only a single value. */
4076 static vec
<ipa_agg_jf_item
>
4077 copy_plats_to_inter (struct ipcp_param_lattices
*plats
, HOST_WIDE_INT offset
)
4079 vec
<ipa_agg_jf_item
> res
= vNULL
;
4081 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
4084 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
4085 if (aglat
->is_single_const ())
4087 struct ipa_agg_jf_item ti
;
4088 ti
.offset
= aglat
->offset
- offset
;
4089 ti
.value
= aglat
->values
->value
;
4095 /* Intersect all values in INTER with single value lattices in PLATS (while
4096 subtracting OFFSET). */
4099 intersect_with_plats (struct ipcp_param_lattices
*plats
,
4100 vec
<ipa_agg_jf_item
> *inter
,
4101 HOST_WIDE_INT offset
)
4103 struct ipcp_agg_lattice
*aglat
;
4104 struct ipa_agg_jf_item
*item
;
4107 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
4113 aglat
= plats
->aggs
;
4114 FOR_EACH_VEC_ELT (*inter
, k
, item
)
4121 if (aglat
->offset
- offset
> item
->offset
)
4123 if (aglat
->offset
- offset
== item
->offset
)
4125 gcc_checking_assert (item
->value
);
4126 if (aglat
->is_single_const ()
4127 && values_equal_for_ipcp_p (item
->value
,
4128 aglat
->values
->value
))
4132 aglat
= aglat
->next
;
4135 item
->value
= NULL_TREE
;
4139 /* Copy aggregate replacement values of NODE (which is an IPA-CP clone) to the
4140 vector result while subtracting OFFSET from the individual value offsets. */
4142 static vec
<ipa_agg_jf_item
>
4143 agg_replacements_to_vector (struct cgraph_node
*node
, int index
,
4144 HOST_WIDE_INT offset
)
4146 struct ipa_agg_replacement_value
*av
;
4147 vec
<ipa_agg_jf_item
> res
= vNULL
;
4149 for (av
= ipa_get_agg_replacements_for_node (node
); av
; av
= av
->next
)
4150 if (av
->index
== index
4151 && (av
->offset
- offset
) >= 0)
4153 struct ipa_agg_jf_item item
;
4154 gcc_checking_assert (av
->value
);
4155 item
.offset
= av
->offset
- offset
;
4156 item
.value
= av
->value
;
4157 res
.safe_push (item
);
4163 /* Intersect all values in INTER with those that we have already scheduled to
4164 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
4165 (while subtracting OFFSET). */
4168 intersect_with_agg_replacements (struct cgraph_node
*node
, int index
,
4169 vec
<ipa_agg_jf_item
> *inter
,
4170 HOST_WIDE_INT offset
)
4172 struct ipa_agg_replacement_value
*srcvals
;
4173 struct ipa_agg_jf_item
*item
;
4176 srcvals
= ipa_get_agg_replacements_for_node (node
);
4183 FOR_EACH_VEC_ELT (*inter
, i
, item
)
4185 struct ipa_agg_replacement_value
*av
;
4189 for (av
= srcvals
; av
; av
= av
->next
)
4191 gcc_checking_assert (av
->value
);
4192 if (av
->index
== index
4193 && av
->offset
- offset
== item
->offset
)
4195 if (values_equal_for_ipcp_p (item
->value
, av
->value
))
4201 item
->value
= NULL_TREE
;
4205 /* Intersect values in INTER with aggregate values that come along edge CS to
4206 parameter number INDEX and return it. If INTER does not actually exist yet,
4207 copy all incoming values to it. If we determine we ended up with no values
4208 whatsoever, return a released vector. */
4210 static vec
<ipa_agg_jf_item
>
4211 intersect_aggregates_with_edge (struct cgraph_edge
*cs
, int index
,
4212 vec
<ipa_agg_jf_item
> inter
)
4214 struct ipa_jump_func
*jfunc
;
4215 jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), index
);
4216 if (jfunc
->type
== IPA_JF_PASS_THROUGH
4217 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
4219 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4220 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
4222 if (caller_info
->ipcp_orig_node
)
4224 struct cgraph_node
*orig_node
= caller_info
->ipcp_orig_node
;
4225 struct ipcp_param_lattices
*orig_plats
;
4226 orig_plats
= ipa_get_parm_lattices (IPA_NODE_REF (orig_node
),
4228 if (agg_pass_through_permissible_p (orig_plats
, jfunc
))
4230 if (!inter
.exists ())
4231 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, 0);
4233 intersect_with_agg_replacements (cs
->caller
, src_idx
,
4244 struct ipcp_param_lattices
*src_plats
;
4245 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
4246 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
4248 /* Currently we do not produce clobber aggregate jump
4249 functions, adjust when we do. */
4250 gcc_checking_assert (!jfunc
->agg
.items
);
4251 if (!inter
.exists ())
4252 inter
= copy_plats_to_inter (src_plats
, 0);
4254 intersect_with_plats (src_plats
, &inter
, 0);
4263 else if (jfunc
->type
== IPA_JF_ANCESTOR
4264 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
4266 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4267 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
4268 struct ipcp_param_lattices
*src_plats
;
4269 HOST_WIDE_INT delta
= ipa_get_jf_ancestor_offset (jfunc
);
4271 if (caller_info
->ipcp_orig_node
)
4273 if (!inter
.exists ())
4274 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, delta
);
4276 intersect_with_agg_replacements (cs
->caller
, src_idx
, &inter
,
4281 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
4282 /* Currently we do not produce clobber aggregate jump
4283 functions, adjust when we do. */
4284 gcc_checking_assert (!src_plats
->aggs
|| !jfunc
->agg
.items
);
4285 if (!inter
.exists ())
4286 inter
= copy_plats_to_inter (src_plats
, delta
);
4288 intersect_with_plats (src_plats
, &inter
, delta
);
4291 else if (jfunc
->agg
.items
)
4293 struct ipa_agg_jf_item
*item
;
4296 if (!inter
.exists ())
4297 for (unsigned i
= 0; i
< jfunc
->agg
.items
->length (); i
++)
4298 inter
.safe_push ((*jfunc
->agg
.items
)[i
]);
4300 FOR_EACH_VEC_ELT (inter
, k
, item
)
4308 while ((unsigned) l
< jfunc
->agg
.items
->length ())
4310 struct ipa_agg_jf_item
*ti
;
4311 ti
= &(*jfunc
->agg
.items
)[l
];
4312 if (ti
->offset
> item
->offset
)
4314 if (ti
->offset
== item
->offset
)
4316 gcc_checking_assert (ti
->value
);
4317 if (values_equal_for_ipcp_p (item
->value
,
4331 return vec
<ipa_agg_jf_item
>();
4336 /* Look at edges in CALLERS and collect all known aggregate values that arrive
4337 from all of them. */
4339 static struct ipa_agg_replacement_value
*
4340 find_aggregate_values_for_callers_subset (struct cgraph_node
*node
,
4341 vec
<cgraph_edge
*> callers
)
4343 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
4344 struct ipa_agg_replacement_value
*res
;
4345 struct ipa_agg_replacement_value
**tail
= &res
;
4346 struct cgraph_edge
*cs
;
4347 int i
, j
, count
= ipa_get_param_count (dest_info
);
4349 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4351 int c
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
4356 for (i
= 0; i
< count
; i
++)
4358 struct cgraph_edge
*cs
;
4359 vec
<ipa_agg_jf_item
> inter
= vNULL
;
4360 struct ipa_agg_jf_item
*item
;
4361 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (dest_info
, i
);
4364 /* Among other things, the following check should deal with all by_ref
4366 if (plats
->aggs_bottom
)
4369 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4371 struct ipa_jump_func
*jfunc
4372 = ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
4373 if (self_recursive_pass_through_p (cs
, jfunc
, i
)
4374 && (!plats
->aggs_by_ref
4375 || ipa_get_jf_pass_through_agg_preserved (jfunc
)))
4377 inter
= intersect_aggregates_with_edge (cs
, i
, inter
);
4379 if (!inter
.exists ())
4383 FOR_EACH_VEC_ELT (inter
, j
, item
)
4385 struct ipa_agg_replacement_value
*v
;
4390 v
= ggc_alloc
<ipa_agg_replacement_value
> ();
4392 v
->offset
= item
->offset
;
4393 v
->value
= item
->value
;
4394 v
->by_ref
= plats
->aggs_by_ref
;
4400 if (inter
.exists ())
4407 /* Determine whether CS also brings all scalar values that the NODE is
4411 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge
*cs
,
4412 struct cgraph_node
*node
)
4414 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
4415 int count
= ipa_get_param_count (dest_info
);
4416 struct ipa_node_params
*caller_info
;
4417 struct ipa_edge_args
*args
;
4420 caller_info
= IPA_NODE_REF (cs
->caller
);
4421 args
= IPA_EDGE_REF (cs
);
4422 for (i
= 0; i
< count
; i
++)
4424 struct ipa_jump_func
*jump_func
;
4427 val
= dest_info
->known_csts
[i
];
4431 if (i
>= ipa_get_cs_argument_count (args
))
4433 jump_func
= ipa_get_ith_jump_func (args
, i
);
4434 t
= ipa_value_from_jfunc (caller_info
, jump_func
,
4435 ipa_get_type (dest_info
, i
));
4436 if (!t
|| !values_equal_for_ipcp_p (val
, t
))
4442 /* Determine whether CS also brings all aggregate values that NODE is
4445 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge
*cs
,
4446 struct cgraph_node
*node
)
4448 struct ipa_node_params
*orig_node_info
;
4449 struct ipa_agg_replacement_value
*aggval
;
4452 aggval
= ipa_get_agg_replacements_for_node (node
);
4456 count
= ipa_get_param_count (IPA_NODE_REF (node
));
4457 ec
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
4459 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4460 if (aggval
->index
>= ec
)
4463 orig_node_info
= IPA_NODE_REF (IPA_NODE_REF (node
)->ipcp_orig_node
);
4465 for (i
= 0; i
< count
; i
++)
4467 static vec
<ipa_agg_jf_item
> values
= vec
<ipa_agg_jf_item
>();
4468 struct ipcp_param_lattices
*plats
;
4469 bool interesting
= false;
4470 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4471 if (aggval
->index
== i
)
4479 plats
= ipa_get_parm_lattices (orig_node_info
, aggval
->index
);
4480 if (plats
->aggs_bottom
)
4483 values
= intersect_aggregates_with_edge (cs
, i
, values
);
4484 if (!values
.exists ())
4487 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4488 if (aggval
->index
== i
)
4490 struct ipa_agg_jf_item
*item
;
4493 FOR_EACH_VEC_ELT (values
, j
, item
)
4495 && item
->offset
== av
->offset
4496 && values_equal_for_ipcp_p (item
->value
, av
->value
))
4511 /* Given an original NODE and a VAL for which we have already created a
4512 specialized clone, look whether there are incoming edges that still lead
4513 into the old node but now also bring the requested value and also conform to
4514 all other criteria such that they can be redirected the special node.
4515 This function can therefore redirect the final edge in a SCC. */
4517 template <typename valtype
>
4519 perhaps_add_new_callers (cgraph_node
*node
, ipcp_value
<valtype
> *val
)
4521 ipcp_value_source
<valtype
> *src
;
4522 profile_count redirected_sum
= profile_count::zero ();
4524 for (src
= val
->sources
; src
; src
= src
->next
)
4526 struct cgraph_edge
*cs
= src
->cs
;
4529 if (cgraph_edge_brings_value_p (cs
, src
, node
, val
)
4530 && cgraph_edge_brings_all_scalars_for_node (cs
, val
->spec_node
)
4531 && cgraph_edge_brings_all_agg_vals_for_node (cs
, val
->spec_node
))
4534 fprintf (dump_file
, " - adding an extra caller %s of %s\n",
4535 cs
->caller
->dump_name (),
4536 val
->spec_node
->dump_name ());
4538 cs
->redirect_callee_duplicating_thunks (val
->spec_node
);
4539 val
->spec_node
->expand_all_artificial_thunks ();
4540 if (cs
->count
.ipa ().initialized_p ())
4541 redirected_sum
= redirected_sum
+ cs
->count
.ipa ();
4543 cs
= get_next_cgraph_edge_clone (cs
);
4547 if (redirected_sum
.nonzero_p ())
4548 update_specialized_profile (val
->spec_node
, node
, redirected_sum
);
4551 /* Return true if KNOWN_CONTEXTS contain at least one useful context. */
4554 known_contexts_useful_p (vec
<ipa_polymorphic_call_context
> known_contexts
)
4556 ipa_polymorphic_call_context
*ctx
;
4559 FOR_EACH_VEC_ELT (known_contexts
, i
, ctx
)
4560 if (!ctx
->useless_p ())
4565 /* Return a copy of KNOWN_CSTS if it is not empty, otherwise return vNULL. */
4567 static vec
<ipa_polymorphic_call_context
>
4568 copy_useful_known_contexts (vec
<ipa_polymorphic_call_context
> known_contexts
)
4570 if (known_contexts_useful_p (known_contexts
))
4571 return known_contexts
.copy ();
4576 /* Copy KNOWN_CSTS and modify the copy according to VAL and INDEX. If
4577 non-empty, replace KNOWN_CONTEXTS with its copy too. */
4580 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
4581 vec
<ipa_polymorphic_call_context
> *known_contexts
,
4582 ipcp_value
<tree
> *val
,
4585 *known_csts
= known_csts
->copy ();
4586 *known_contexts
= copy_useful_known_contexts (*known_contexts
);
4587 (*known_csts
)[index
] = val
->value
;
4590 /* Replace KNOWN_CSTS with its copy. Also copy KNOWN_CONTEXTS and modify the
4591 copy according to VAL and INDEX. */
4594 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
4595 vec
<ipa_polymorphic_call_context
> *known_contexts
,
4596 ipcp_value
<ipa_polymorphic_call_context
> *val
,
4599 *known_csts
= known_csts
->copy ();
4600 *known_contexts
= known_contexts
->copy ();
4601 (*known_contexts
)[index
] = val
->value
;
4604 /* Return true if OFFSET indicates this was not an aggregate value or there is
4605 a replacement equivalent to VALUE, INDEX and OFFSET among those in the
4609 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*aggvals
,
4610 int index
, HOST_WIDE_INT offset
, tree value
)
4617 if (aggvals
->index
== index
4618 && aggvals
->offset
== offset
4619 && values_equal_for_ipcp_p (aggvals
->value
, value
))
4621 aggvals
= aggvals
->next
;
4626 /* Return true if offset is minus one because source of a polymorphic context
4627 cannot be an aggregate value. */
4630 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*,
4631 int , HOST_WIDE_INT offset
,
4632 ipa_polymorphic_call_context
)
4634 return offset
== -1;
4637 /* Decide whether to create a special version of NODE for value VAL of parameter
4638 at the given INDEX. If OFFSET is -1, the value is for the parameter itself,
4639 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS,
4640 KNOWN_CONTEXTS and KNOWN_AGGS describe the other already known values. */
4642 template <typename valtype
>
4644 decide_about_value (struct cgraph_node
*node
, int index
, HOST_WIDE_INT offset
,
4645 ipcp_value
<valtype
> *val
, vec
<tree
> known_csts
,
4646 vec
<ipa_polymorphic_call_context
> known_contexts
)
4648 struct ipa_agg_replacement_value
*aggvals
;
4649 int freq_sum
, caller_count
;
4650 profile_count count_sum
;
4651 vec
<cgraph_edge
*> callers
;
4655 perhaps_add_new_callers (node
, val
);
4658 else if (val
->local_size_cost
+ overall_size
> max_new_size
)
4660 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4661 fprintf (dump_file
, " Ignoring candidate value because "
4662 "max_new_size would be reached with %li.\n",
4663 val
->local_size_cost
+ overall_size
);
4666 else if (!get_info_about_necessary_edges (val
, node
, &freq_sum
, &count_sum
,
4670 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4672 fprintf (dump_file
, " - considering value ");
4673 print_ipcp_constant_value (dump_file
, val
->value
);
4674 fprintf (dump_file
, " for ");
4675 ipa_dump_param (dump_file
, IPA_NODE_REF (node
), index
);
4677 fprintf (dump_file
, ", offset: " HOST_WIDE_INT_PRINT_DEC
, offset
);
4678 fprintf (dump_file
, " (caller_count: %i)\n", caller_count
);
4681 if (!good_cloning_opportunity_p (node
, val
->local_time_benefit
,
4682 freq_sum
, count_sum
,
4683 val
->local_size_cost
)
4684 && !good_cloning_opportunity_p (node
,
4685 val
->local_time_benefit
4686 + val
->prop_time_benefit
,
4687 freq_sum
, count_sum
,
4688 val
->local_size_cost
4689 + val
->prop_size_cost
))
4693 fprintf (dump_file
, " Creating a specialized node of %s.\n",
4694 node
->dump_name ());
4696 callers
= gather_edges_for_value (val
, node
, caller_count
);
4698 modify_known_vectors_with_val (&known_csts
, &known_contexts
, val
, index
);
4701 known_csts
= known_csts
.copy ();
4702 known_contexts
= copy_useful_known_contexts (known_contexts
);
4704 find_more_scalar_values_for_callers_subset (node
, known_csts
, callers
);
4705 find_more_contexts_for_caller_subset (node
, &known_contexts
, callers
);
4706 aggvals
= find_aggregate_values_for_callers_subset (node
, callers
);
4707 gcc_checking_assert (ipcp_val_agg_replacement_ok_p (aggvals
, index
,
4708 offset
, val
->value
));
4709 val
->spec_node
= create_specialized_node (node
, known_csts
, known_contexts
,
4711 overall_size
+= val
->local_size_cost
;
4713 /* TODO: If for some lattice there is only one other known value
4714 left, make a special node for it too. */
4719 /* Decide whether and what specialized clones of NODE should be created. */
4722 decide_whether_version_node (struct cgraph_node
*node
)
4724 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
4725 int i
, count
= ipa_get_param_count (info
);
4726 vec
<tree
> known_csts
;
4727 vec
<ipa_polymorphic_call_context
> known_contexts
;
4728 vec
<ipa_agg_jump_function
> known_aggs
= vNULL
;
4734 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4735 fprintf (dump_file
, "\nEvaluating opportunities for %s.\n",
4736 node
->dump_name ());
4738 gather_context_independent_values (info
, &known_csts
, &known_contexts
,
4739 info
->do_clone_for_all_contexts
? &known_aggs
4742 for (i
= 0; i
< count
;i
++)
4744 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4745 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
4746 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
4751 ipcp_value
<tree
> *val
;
4752 for (val
= lat
->values
; val
; val
= val
->next
)
4753 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
4757 if (!plats
->aggs_bottom
)
4759 struct ipcp_agg_lattice
*aglat
;
4760 ipcp_value
<tree
> *val
;
4761 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
4762 if (!aglat
->bottom
&& aglat
->values
4763 /* If the following is false, the one value is in
4765 && (plats
->aggs_contain_variable
4766 || !aglat
->is_single_const ()))
4767 for (val
= aglat
->values
; val
; val
= val
->next
)
4768 ret
|= decide_about_value (node
, i
, aglat
->offset
, val
,
4769 known_csts
, known_contexts
);
4773 && known_contexts
[i
].useless_p ())
4775 ipcp_value
<ipa_polymorphic_call_context
> *val
;
4776 for (val
= ctxlat
->values
; val
; val
= val
->next
)
4777 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
4781 info
= IPA_NODE_REF (node
);
4784 if (info
->do_clone_for_all_contexts
)
4786 struct cgraph_node
*clone
;
4787 vec
<cgraph_edge
*> callers
;
4790 fprintf (dump_file
, " - Creating a specialized node of %s "
4791 "for all known contexts.\n", node
->dump_name ());
4793 callers
= node
->collect_callers ();
4794 find_more_scalar_values_for_callers_subset (node
, known_csts
, callers
);
4795 find_more_contexts_for_caller_subset (node
, &known_contexts
, callers
);
4796 ipa_agg_replacement_value
*aggvals
4797 = find_aggregate_values_for_callers_subset (node
, callers
);
4799 if (!known_contexts_useful_p (known_contexts
))
4801 known_contexts
.release ();
4802 known_contexts
= vNULL
;
4804 clone
= create_specialized_node (node
, known_csts
, known_contexts
,
4806 info
= IPA_NODE_REF (node
);
4807 info
->do_clone_for_all_contexts
= false;
4808 IPA_NODE_REF (clone
)->is_all_contexts_clone
= true;
4809 for (i
= 0; i
< count
; i
++)
4810 vec_free (known_aggs
[i
].items
);
4811 known_aggs
.release ();
4816 known_csts
.release ();
4817 known_contexts
.release ();
4823 /* Transitively mark all callees of NODE within the same SCC as not dead. */
4826 spread_undeadness (struct cgraph_node
*node
)
4828 struct cgraph_edge
*cs
;
4830 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
4831 if (ipa_edge_within_scc (cs
))
4833 struct cgraph_node
*callee
;
4834 struct ipa_node_params
*info
;
4836 callee
= cs
->callee
->function_symbol (NULL
);
4837 info
= IPA_NODE_REF (callee
);
4839 if (info
->node_dead
)
4841 info
->node_dead
= 0;
4842 spread_undeadness (callee
);
4847 /* Return true if NODE has a caller from outside of its SCC that is not
4848 dead. Worker callback for cgraph_for_node_and_aliases. */
4851 has_undead_caller_from_outside_scc_p (struct cgraph_node
*node
,
4852 void *data ATTRIBUTE_UNUSED
)
4854 struct cgraph_edge
*cs
;
4856 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
4857 if (cs
->caller
->thunk
.thunk_p
4858 && cs
->caller
->call_for_symbol_thunks_and_aliases
4859 (has_undead_caller_from_outside_scc_p
, NULL
, true))
4861 else if (!ipa_edge_within_scc (cs
)
4862 && !IPA_NODE_REF (cs
->caller
)->node_dead
)
4868 /* Identify nodes within the same SCC as NODE which are no longer needed
4869 because of new clones and will be removed as unreachable. */
4872 identify_dead_nodes (struct cgraph_node
*node
)
4874 struct cgraph_node
*v
;
4875 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4877 && !v
->call_for_symbol_thunks_and_aliases
4878 (has_undead_caller_from_outside_scc_p
, NULL
, true))
4879 IPA_NODE_REF (v
)->node_dead
= 1;
4881 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4882 if (!IPA_NODE_REF (v
)->node_dead
)
4883 spread_undeadness (v
);
4885 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4887 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4888 if (IPA_NODE_REF (v
)->node_dead
)
4889 fprintf (dump_file
, " Marking node as dead: %s.\n", v
->dump_name ());
4893 /* The decision stage. Iterate over the topological order of call graph nodes
4894 TOPO and make specialized clones if deemed beneficial. */
4897 ipcp_decision_stage (struct ipa_topo_info
*topo
)
4902 fprintf (dump_file
, "\nIPA decision stage:\n\n");
4904 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
4906 struct cgraph_node
*node
= topo
->order
[i
];
4907 bool change
= false, iterate
= true;
4911 struct cgraph_node
*v
;
4913 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4914 if (v
->has_gimple_body_p ()
4915 && ipcp_versionable_function_p (v
))
4916 iterate
|= decide_whether_version_node (v
);
4921 identify_dead_nodes (node
);
4925 /* Look up all the bits information that we have discovered and copy it over
4926 to the transformation summary. */
4929 ipcp_store_bits_results (void)
4933 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
4935 ipa_node_params
*info
= IPA_NODE_REF (node
);
4936 bool dumped_sth
= false;
4937 bool found_useful_result
= false;
4939 if (!opt_for_fn (node
->decl
, flag_ipa_bit_cp
))
4942 fprintf (dump_file
, "Not considering %s for ipa bitwise propagation "
4943 "; -fipa-bit-cp: disabled.\n",
4948 if (info
->ipcp_orig_node
)
4949 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
4951 unsigned count
= ipa_get_param_count (info
);
4952 for (unsigned i
= 0; i
< count
; i
++)
4954 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4955 if (plats
->bits_lattice
.constant_p ())
4957 found_useful_result
= true;
4962 if (!found_useful_result
)
4965 ipcp_transformation_initialize ();
4966 ipcp_transformation
*ts
= ipcp_transformation_sum
->get_create (node
);
4967 vec_safe_reserve_exact (ts
->bits
, count
);
4969 for (unsigned i
= 0; i
< count
; i
++)
4971 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4974 if (plats
->bits_lattice
.constant_p ())
4976 = ipa_get_ipa_bits_for_value (plats
->bits_lattice
.get_value (),
4977 plats
->bits_lattice
.get_mask ());
4981 ts
->bits
->quick_push (jfbits
);
4982 if (!dump_file
|| !jfbits
)
4986 fprintf (dump_file
, "Propagated bits info for function %s:\n",
4987 node
->dump_name ());
4990 fprintf (dump_file
, " param %i: value = ", i
);
4991 print_hex (jfbits
->value
, dump_file
);
4992 fprintf (dump_file
, ", mask = ");
4993 print_hex (jfbits
->mask
, dump_file
);
4994 fprintf (dump_file
, "\n");
4999 /* Look up all VR information that we have discovered and copy it over
5000 to the transformation summary. */
5003 ipcp_store_vr_results (void)
5007 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5009 ipa_node_params
*info
= IPA_NODE_REF (node
);
5010 bool found_useful_result
= false;
5012 if (!opt_for_fn (node
->decl
, flag_ipa_vrp
))
5015 fprintf (dump_file
, "Not considering %s for VR discovery "
5016 "and propagate; -fipa-ipa-vrp: disabled.\n",
5021 if (info
->ipcp_orig_node
)
5022 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
5024 unsigned count
= ipa_get_param_count (info
);
5025 for (unsigned i
= 0; i
< count
; i
++)
5027 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5028 if (!plats
->m_value_range
.bottom_p ()
5029 && !plats
->m_value_range
.top_p ())
5031 found_useful_result
= true;
5035 if (!found_useful_result
)
5038 ipcp_transformation_initialize ();
5039 ipcp_transformation
*ts
= ipcp_transformation_sum
->get_create (node
);
5040 vec_safe_reserve_exact (ts
->m_vr
, count
);
5042 for (unsigned i
= 0; i
< count
; i
++)
5044 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5047 if (!plats
->m_value_range
.bottom_p ()
5048 && !plats
->m_value_range
.top_p ())
5051 vr
.type
= plats
->m_value_range
.m_vr
.kind ();
5052 vr
.min
= wi::to_wide (plats
->m_value_range
.m_vr
.min ());
5053 vr
.max
= wi::to_wide (plats
->m_value_range
.m_vr
.max ());
5058 vr
.type
= VR_VARYING
;
5059 vr
.min
= vr
.max
= wi::zero (INT_TYPE_SIZE
);
5061 ts
->m_vr
->quick_push (vr
);
5066 /* The IPCP driver. */
5071 struct ipa_topo_info topo
;
5073 if (edge_clone_summaries
== NULL
)
5074 edge_clone_summaries
= new edge_clone_summary_t (symtab
);
5076 ipa_check_create_node_params ();
5077 ipa_check_create_edge_args ();
5078 clone_num_suffixes
= new hash_map
<const char *, unsigned>;
5082 fprintf (dump_file
, "\nIPA structures before propagation:\n");
5083 if (dump_flags
& TDF_DETAILS
)
5084 ipa_print_all_params (dump_file
);
5085 ipa_print_all_jump_functions (dump_file
);
5088 /* Topological sort. */
5089 build_toporder_info (&topo
);
5090 /* Do the interprocedural propagation. */
5091 ipcp_propagate_stage (&topo
);
5092 /* Decide what constant propagation and cloning should be performed. */
5093 ipcp_decision_stage (&topo
);
5094 /* Store results of bits propagation. */
5095 ipcp_store_bits_results ();
5096 /* Store results of value range propagation. */
5097 ipcp_store_vr_results ();
5099 /* Free all IPCP structures. */
5100 delete clone_num_suffixes
;
5101 free_toporder_info (&topo
);
5102 delete edge_clone_summaries
;
5103 edge_clone_summaries
= NULL
;
5104 ipa_free_all_structures_after_ipa_cp ();
5106 fprintf (dump_file
, "\nIPA constant propagation end\n");
5110 /* Initialization and computation of IPCP data structures. This is the initial
5111 intraprocedural analysis of functions, which gathers information to be
5112 propagated later on. */
5115 ipcp_generate_summary (void)
5117 struct cgraph_node
*node
;
5120 fprintf (dump_file
, "\nIPA constant propagation start:\n");
5121 ipa_register_cgraph_hooks ();
5123 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5124 ipa_analyze_node (node
);
5127 /* Write ipcp summary for nodes in SET. */
5130 ipcp_write_summary (void)
5132 ipa_prop_write_jump_functions ();
5135 /* Read ipcp summary. */
5138 ipcp_read_summary (void)
5140 ipa_prop_read_jump_functions ();
5145 const pass_data pass_data_ipa_cp
=
5147 IPA_PASS
, /* type */
5149 OPTGROUP_NONE
, /* optinfo_flags */
5150 TV_IPA_CONSTANT_PROP
, /* tv_id */
5151 0, /* properties_required */
5152 0, /* properties_provided */
5153 0, /* properties_destroyed */
5154 0, /* todo_flags_start */
5155 ( TODO_dump_symtab
| TODO_remove_functions
), /* todo_flags_finish */
5158 class pass_ipa_cp
: public ipa_opt_pass_d
5161 pass_ipa_cp (gcc::context
*ctxt
)
5162 : ipa_opt_pass_d (pass_data_ipa_cp
, ctxt
,
5163 ipcp_generate_summary
, /* generate_summary */
5164 ipcp_write_summary
, /* write_summary */
5165 ipcp_read_summary
, /* read_summary */
5166 ipcp_write_transformation_summaries
, /*
5167 write_optimization_summary */
5168 ipcp_read_transformation_summaries
, /*
5169 read_optimization_summary */
5170 NULL
, /* stmt_fixup */
5171 0, /* function_transform_todo_flags_start */
5172 ipcp_transform_function
, /* function_transform */
5173 NULL
) /* variable_transform */
5176 /* opt_pass methods: */
5177 virtual bool gate (function
*)
5179 /* FIXME: We should remove the optimize check after we ensure we never run
5180 IPA passes when not optimizing. */
5181 return (flag_ipa_cp
&& optimize
) || in_lto_p
;
5184 virtual unsigned int execute (function
*) { return ipcp_driver (); }
5186 }; // class pass_ipa_cp
5191 make_pass_ipa_cp (gcc::context
*ctxt
)
5193 return new pass_ipa_cp (ctxt
);
5196 /* Reset all state within ipa-cp.c so that we can rerun the compiler
5197 within the same process. For use by toplev::finalize. */
5200 ipa_cp_c_finalize (void)
5202 max_count
= profile_count::uninitialized ();