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 struct 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 struct 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 class ipcp_param_lattices
*
385 ipa_get_parm_lattices (class 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 (class ipa_node_params
*info
, int i
)
398 class 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 (class ipa_node_params
*info
, int i
)
407 class 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 class 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 class 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 class 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 (class 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 (class 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 (class ipa_topo_info
*topo
, struct cgraph_node
*node
)
852 class 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 (class 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 (class 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 (class 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 ())
980 /* ?? We create all sorts of VARYING ranges for floats, structures,
981 and other types which we cannot handle as ranges. We should
982 probably avoid handling them throughout the pass, but it's easier
983 to create a sensible VARYING here and let the lattice
985 m_vr
.set_varying (integer_type_node
);
989 /* Set lattice value to bottom, if it already isn't the case. */
992 ipcp_bits_lattice::set_to_bottom ()
996 m_lattice_val
= IPA_BITS_VARYING
;
1002 /* Set to constant if it isn't already. Only meant to be called
1003 when switching state from TOP. */
1006 ipcp_bits_lattice::set_to_constant (widest_int value
, widest_int mask
)
1008 gcc_assert (top_p ());
1009 m_lattice_val
= IPA_BITS_CONSTANT
;
1015 /* Convert operand to value, mask form. */
1018 ipcp_bits_lattice::get_value_and_mask (tree operand
, widest_int
*valuep
, widest_int
*maskp
)
1020 wide_int
get_nonzero_bits (const_tree
);
1022 if (TREE_CODE (operand
) == INTEGER_CST
)
1024 *valuep
= wi::to_widest (operand
);
1034 /* Meet operation, similar to ccp_lattice_meet, we xor values
1035 if this->value, value have different values at same bit positions, we want
1036 to drop that bit to varying. Return true if mask is changed.
1037 This function assumes that the lattice value is in CONSTANT state */
1040 ipcp_bits_lattice::meet_with_1 (widest_int value
, widest_int mask
,
1043 gcc_assert (constant_p ());
1045 widest_int old_mask
= m_mask
;
1046 m_mask
= (m_mask
| mask
) | (m_value
^ value
);
1048 if (wi::sext (m_mask
, precision
) == -1)
1049 return set_to_bottom ();
1051 return m_mask
!= old_mask
;
1054 /* Meet the bits lattice with operand
1055 described by <value, mask, sgn, precision. */
1058 ipcp_bits_lattice::meet_with (widest_int value
, widest_int mask
,
1066 if (wi::sext (mask
, precision
) == -1)
1067 return set_to_bottom ();
1068 return set_to_constant (value
, mask
);
1071 return meet_with_1 (value
, mask
, precision
);
1074 /* Meet bits lattice with the result of bit_value_binop (other, operand)
1075 if code is binary operation or bit_value_unop (other) if code is unary op.
1076 In the case when code is nop_expr, no adjustment is required. */
1079 ipcp_bits_lattice::meet_with (ipcp_bits_lattice
& other
, unsigned precision
,
1080 signop sgn
, enum tree_code code
, tree operand
)
1082 if (other
.bottom_p ())
1083 return set_to_bottom ();
1085 if (bottom_p () || other
.top_p ())
1088 widest_int adjusted_value
, adjusted_mask
;
1090 if (TREE_CODE_CLASS (code
) == tcc_binary
)
1092 tree type
= TREE_TYPE (operand
);
1093 widest_int o_value
, o_mask
;
1094 get_value_and_mask (operand
, &o_value
, &o_mask
);
1096 bit_value_binop (code
, sgn
, precision
, &adjusted_value
, &adjusted_mask
,
1097 sgn
, precision
, other
.get_value (), other
.get_mask (),
1098 TYPE_SIGN (type
), TYPE_PRECISION (type
), o_value
, o_mask
);
1100 if (wi::sext (adjusted_mask
, precision
) == -1)
1101 return set_to_bottom ();
1104 else if (TREE_CODE_CLASS (code
) == tcc_unary
)
1106 bit_value_unop (code
, sgn
, precision
, &adjusted_value
,
1107 &adjusted_mask
, sgn
, precision
, other
.get_value (),
1110 if (wi::sext (adjusted_mask
, precision
) == -1)
1111 return set_to_bottom ();
1115 return set_to_bottom ();
1119 if (wi::sext (adjusted_mask
, precision
) == -1)
1120 return set_to_bottom ();
1121 return set_to_constant (adjusted_value
, adjusted_mask
);
1124 return meet_with_1 (adjusted_value
, adjusted_mask
, precision
);
1127 /* Mark bot aggregate and scalar lattices as containing an unknown variable,
1128 return true is any of them has not been marked as such so far. */
1131 set_all_contains_variable (class ipcp_param_lattices
*plats
)
1134 ret
= plats
->itself
.set_contains_variable ();
1135 ret
|= plats
->ctxlat
.set_contains_variable ();
1136 ret
|= set_agg_lats_contain_variable (plats
);
1137 ret
|= plats
->bits_lattice
.set_to_bottom ();
1138 ret
|= plats
->m_value_range
.set_to_bottom ();
1142 /* Worker of call_for_symbol_thunks_and_aliases, increment the integer DATA
1143 points to by the number of callers to NODE. */
1146 count_callers (cgraph_node
*node
, void *data
)
1148 int *caller_count
= (int *) data
;
1150 for (cgraph_edge
*cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
1151 /* Local thunks can be handled transparently, but if the thunk cannot
1152 be optimized out, count it as a real use. */
1153 if (!cs
->caller
->thunk
.thunk_p
|| !cs
->caller
->local
.local
)
1158 /* Worker of call_for_symbol_thunks_and_aliases, it is supposed to be called on
1159 the one caller of some other node. Set the caller's corresponding flag. */
1162 set_single_call_flag (cgraph_node
*node
, void *)
1164 cgraph_edge
*cs
= node
->callers
;
1165 /* Local thunks can be handled transparently, skip them. */
1166 while (cs
&& cs
->caller
->thunk
.thunk_p
&& cs
->caller
->local
.local
)
1167 cs
= cs
->next_caller
;
1170 IPA_NODE_REF (cs
->caller
)->node_calling_single_call
= true;
1176 /* Initialize ipcp_lattices. */
1179 initialize_node_lattices (struct cgraph_node
*node
)
1181 class ipa_node_params
*info
= IPA_NODE_REF (node
);
1182 struct cgraph_edge
*ie
;
1183 bool disable
= false, variable
= false;
1186 gcc_checking_assert (node
->has_gimple_body_p ());
1188 if (!ipa_get_param_count (info
))
1190 else if (node
->local
.local
)
1192 int caller_count
= 0;
1193 node
->call_for_symbol_thunks_and_aliases (count_callers
, &caller_count
,
1195 gcc_checking_assert (caller_count
> 0);
1196 if (caller_count
== 1)
1197 node
->call_for_symbol_thunks_and_aliases (set_single_call_flag
,
1202 /* When cloning is allowed, we can assume that externally visible
1203 functions are not called. We will compensate this by cloning
1205 if (ipcp_versionable_function_p (node
)
1206 && ipcp_cloning_candidate_p (node
))
1212 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1213 && !node
->alias
&& !node
->thunk
.thunk_p
)
1215 fprintf (dump_file
, "Initializing lattices of %s\n",
1216 node
->dump_name ());
1217 if (disable
|| variable
)
1218 fprintf (dump_file
, " Marking all lattices as %s\n",
1219 disable
? "BOTTOM" : "VARIABLE");
1222 auto_vec
<bool, 16> surviving_params
;
1223 bool pre_modified
= false;
1224 if (!disable
&& node
->clone
.param_adjustments
)
1226 /* At the moment all IPA optimizations should use the number of
1227 parameters of the prevailing decl as the m_always_copy_start.
1228 Handling any other value would complicate the code below, so for the
1229 time bing let's only assert it is so. */
1230 gcc_assert ((node
->clone
.param_adjustments
->m_always_copy_start
1231 == ipa_get_param_count (info
))
1232 || node
->clone
.param_adjustments
->m_always_copy_start
< 0);
1234 pre_modified
= true;
1235 node
->clone
.param_adjustments
->get_surviving_params (&surviving_params
);
1237 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1238 && !node
->alias
&& !node
->thunk
.thunk_p
)
1241 for (int j
= 0; j
< ipa_get_param_count (info
); j
++)
1243 if (j
< (int) surviving_params
.length ()
1244 && surviving_params
[j
])
1249 " The following parameters are dead on arrival:");
1252 fprintf (dump_file
, " %u", j
);
1255 fprintf (dump_file
, "\n");
1259 for (i
= 0; i
< ipa_get_param_count (info
); i
++)
1261 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1263 || (pre_modified
&& (surviving_params
.length () <= (unsigned) i
1264 || !surviving_params
[i
])))
1266 plats
->itself
.set_to_bottom ();
1267 plats
->ctxlat
.set_to_bottom ();
1268 set_agg_lats_to_bottom (plats
);
1269 plats
->bits_lattice
.set_to_bottom ();
1270 plats
->m_value_range
.set_to_bottom ();
1274 plats
->m_value_range
.init ();
1276 set_all_contains_variable (plats
);
1280 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
1281 if (ie
->indirect_info
->polymorphic
1282 && ie
->indirect_info
->param_index
>= 0)
1284 gcc_checking_assert (ie
->indirect_info
->param_index
>= 0);
1285 ipa_get_parm_lattices (info
,
1286 ie
->indirect_info
->param_index
)->virt_call
= 1;
1290 /* Return the result of a (possibly arithmetic) pass through jump function
1291 JFUNC on the constant value INPUT. RES_TYPE is the type of the parameter
1292 to which the result is passed. Return NULL_TREE if that cannot be
1293 determined or be considered an interprocedural invariant. */
1296 ipa_get_jf_pass_through_result (struct ipa_jump_func
*jfunc
, tree input
,
1301 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
1303 if (!is_gimple_ip_invariant (input
))
1306 tree_code opcode
= ipa_get_jf_pass_through_operation (jfunc
);
1309 if (TREE_CODE_CLASS (opcode
) == tcc_comparison
)
1310 res_type
= boolean_type_node
;
1311 else if (expr_type_first_operand_type_p (opcode
))
1312 res_type
= TREE_TYPE (input
);
1317 if (TREE_CODE_CLASS (opcode
) == tcc_unary
)
1318 res
= fold_unary (opcode
, res_type
, input
);
1320 res
= fold_binary (opcode
, res_type
, input
,
1321 ipa_get_jf_pass_through_operand (jfunc
));
1323 if (res
&& !is_gimple_ip_invariant (res
))
1329 /* Return the result of an ancestor jump function JFUNC on the constant value
1330 INPUT. Return NULL_TREE if that cannot be determined. */
1333 ipa_get_jf_ancestor_result (struct ipa_jump_func
*jfunc
, tree input
)
1335 gcc_checking_assert (TREE_CODE (input
) != TREE_BINFO
);
1336 if (TREE_CODE (input
) == ADDR_EXPR
)
1338 tree t
= TREE_OPERAND (input
, 0);
1339 t
= build_ref_for_offset (EXPR_LOCATION (t
), t
,
1340 ipa_get_jf_ancestor_offset (jfunc
), false,
1341 ptr_type_node
, NULL
, false);
1342 return build_fold_addr_expr (t
);
1348 /* Determine whether JFUNC evaluates to a single known constant value and if
1349 so, return it. Otherwise return NULL. INFO describes the caller node or
1350 the one it is inlined to, so that pass-through jump functions can be
1351 evaluated. PARM_TYPE is the type of the parameter to which the result is
1355 ipa_value_from_jfunc (class ipa_node_params
*info
, struct ipa_jump_func
*jfunc
,
1358 if (jfunc
->type
== IPA_JF_CONST
)
1359 return ipa_get_jf_constant (jfunc
);
1360 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1361 || jfunc
->type
== IPA_JF_ANCESTOR
)
1366 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1367 idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1369 idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1371 if (info
->ipcp_orig_node
)
1372 input
= info
->known_csts
[idx
];
1375 ipcp_lattice
<tree
> *lat
;
1378 || idx
>= ipa_get_param_count (info
))
1380 lat
= ipa_get_scalar_lat (info
, idx
);
1381 if (!lat
->is_single_const ())
1383 input
= lat
->values
->value
;
1389 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1390 return ipa_get_jf_pass_through_result (jfunc
, input
, parm_type
);
1392 return ipa_get_jf_ancestor_result (jfunc
, input
);
1398 /* Determine whether JFUNC evaluates to single known polymorphic context, given
1399 that INFO describes the caller node or the one it is inlined to, CS is the
1400 call graph edge corresponding to JFUNC and CSIDX index of the described
1403 ipa_polymorphic_call_context
1404 ipa_context_from_jfunc (ipa_node_params
*info
, cgraph_edge
*cs
, int csidx
,
1405 ipa_jump_func
*jfunc
)
1407 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
1408 ipa_polymorphic_call_context ctx
;
1409 ipa_polymorphic_call_context
*edge_ctx
1410 = cs
? ipa_get_ith_polymorhic_call_context (args
, csidx
) : NULL
;
1412 if (edge_ctx
&& !edge_ctx
->useless_p ())
1415 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1416 || jfunc
->type
== IPA_JF_ANCESTOR
)
1418 ipa_polymorphic_call_context srcctx
;
1420 bool type_preserved
= true;
1421 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1423 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1425 type_preserved
= ipa_get_jf_pass_through_type_preserved (jfunc
);
1426 srcidx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1430 type_preserved
= ipa_get_jf_ancestor_type_preserved (jfunc
);
1431 srcidx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1433 if (info
->ipcp_orig_node
)
1435 if (info
->known_contexts
.exists ())
1436 srcctx
= info
->known_contexts
[srcidx
];
1441 || srcidx
>= ipa_get_param_count (info
))
1443 ipcp_lattice
<ipa_polymorphic_call_context
> *lat
;
1444 lat
= ipa_get_poly_ctx_lat (info
, srcidx
);
1445 if (!lat
->is_single_const ())
1447 srcctx
= lat
->values
->value
;
1449 if (srcctx
.useless_p ())
1451 if (jfunc
->type
== IPA_JF_ANCESTOR
)
1452 srcctx
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
1453 if (!type_preserved
)
1454 srcctx
.possible_dynamic_type_change (cs
->in_polymorphic_cdtor
);
1455 srcctx
.combine_with (ctx
);
1462 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
1463 bottom, not containing a variable component and without any known value at
1467 ipcp_verify_propagated_values (void)
1469 struct cgraph_node
*node
;
1471 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
1473 class ipa_node_params
*info
= IPA_NODE_REF (node
);
1474 int i
, count
= ipa_get_param_count (info
);
1476 for (i
= 0; i
< count
; i
++)
1478 ipcp_lattice
<tree
> *lat
= ipa_get_scalar_lat (info
, i
);
1481 && !lat
->contains_variable
1482 && lat
->values_count
== 0)
1486 symtab
->dump (dump_file
);
1487 fprintf (dump_file
, "\nIPA lattices after constant "
1488 "propagation, before gcc_unreachable:\n");
1489 print_all_lattices (dump_file
, true, false);
1498 /* Return true iff X and Y should be considered equal values by IPA-CP. */
1501 values_equal_for_ipcp_p (tree x
, tree y
)
1503 gcc_checking_assert (x
!= NULL_TREE
&& y
!= NULL_TREE
);
1508 if (TREE_CODE (x
) == ADDR_EXPR
1509 && TREE_CODE (y
) == ADDR_EXPR
1510 && TREE_CODE (TREE_OPERAND (x
, 0)) == CONST_DECL
1511 && TREE_CODE (TREE_OPERAND (y
, 0)) == CONST_DECL
)
1512 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x
, 0)),
1513 DECL_INITIAL (TREE_OPERAND (y
, 0)), 0);
1515 return operand_equal_p (x
, y
, 0);
1518 /* Return true iff X and Y should be considered equal contexts by IPA-CP. */
1521 values_equal_for_ipcp_p (ipa_polymorphic_call_context x
,
1522 ipa_polymorphic_call_context y
)
1524 return x
.equal_to (y
);
1528 /* Add a new value source to the value represented by THIS, marking that a
1529 value comes from edge CS and (if the underlying jump function is a
1530 pass-through or an ancestor one) from a caller value SRC_VAL of a caller
1531 parameter described by SRC_INDEX. OFFSET is negative if the source was the
1532 scalar value of the parameter itself or the offset within an aggregate. */
1534 template <typename valtype
>
1536 ipcp_value
<valtype
>::add_source (cgraph_edge
*cs
, ipcp_value
*src_val
,
1537 int src_idx
, HOST_WIDE_INT offset
)
1539 ipcp_value_source
<valtype
> *src
;
1541 src
= new (ipcp_sources_pool
.allocate ()) ipcp_value_source
<valtype
>;
1542 src
->offset
= offset
;
1545 src
->index
= src_idx
;
1547 src
->next
= sources
;
1551 /* Allocate a new ipcp_value holding a tree constant, initialize its value to
1552 SOURCE and clear all other fields. */
1554 static ipcp_value
<tree
> *
1555 allocate_and_init_ipcp_value (tree source
)
1557 ipcp_value
<tree
> *val
;
1559 val
= new (ipcp_cst_values_pool
.allocate ()) ipcp_value
<tree
>();
1560 val
->value
= source
;
1564 /* Allocate a new ipcp_value holding a polymorphic context, initialize its
1565 value to SOURCE and clear all other fields. */
1567 static ipcp_value
<ipa_polymorphic_call_context
> *
1568 allocate_and_init_ipcp_value (ipa_polymorphic_call_context source
)
1570 ipcp_value
<ipa_polymorphic_call_context
> *val
;
1573 val
= new (ipcp_poly_ctx_values_pool
.allocate ())
1574 ipcp_value
<ipa_polymorphic_call_context
>();
1575 val
->value
= source
;
1579 /* Try to add NEWVAL to LAT, potentially creating a new ipcp_value for it. CS,
1580 SRC_VAL SRC_INDEX and OFFSET are meant for add_source and have the same
1581 meaning. OFFSET -1 means the source is scalar and not a part of an
1584 template <typename valtype
>
1586 ipcp_lattice
<valtype
>::add_value (valtype newval
, cgraph_edge
*cs
,
1587 ipcp_value
<valtype
> *src_val
,
1588 int src_idx
, HOST_WIDE_INT offset
)
1590 ipcp_value
<valtype
> *val
;
1595 for (val
= values
; val
; val
= val
->next
)
1596 if (values_equal_for_ipcp_p (val
->value
, newval
))
1598 if (ipa_edge_within_scc (cs
))
1600 ipcp_value_source
<valtype
> *s
;
1601 for (s
= val
->sources
; s
; s
= s
->next
)
1608 val
->add_source (cs
, src_val
, src_idx
, offset
);
1612 if (values_count
== PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE
))
1614 /* We can only free sources, not the values themselves, because sources
1615 of other values in this SCC might point to them. */
1616 for (val
= values
; val
; val
= val
->next
)
1618 while (val
->sources
)
1620 ipcp_value_source
<valtype
> *src
= val
->sources
;
1621 val
->sources
= src
->next
;
1622 ipcp_sources_pool
.remove ((ipcp_value_source
<tree
>*)src
);
1627 return set_to_bottom ();
1631 val
= allocate_and_init_ipcp_value (newval
);
1632 val
->add_source (cs
, src_val
, src_idx
, offset
);
1638 /* Propagate values through a pass-through jump function JFUNC associated with
1639 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1640 is the index of the source parameter. PARM_TYPE is the type of the
1641 parameter to which the result is passed. */
1644 propagate_vals_across_pass_through (cgraph_edge
*cs
, ipa_jump_func
*jfunc
,
1645 ipcp_lattice
<tree
> *src_lat
,
1646 ipcp_lattice
<tree
> *dest_lat
, int src_idx
,
1649 ipcp_value
<tree
> *src_val
;
1652 /* Do not create new values when propagating within an SCC because if there
1653 are arithmetic functions with circular dependencies, there is infinite
1654 number of them and we would just make lattices bottom. If this condition
1655 is ever relaxed we have to detect self-feeding recursive calls in
1656 cgraph_edge_brings_value_p in a smarter way. */
1657 if ((ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1658 && ipa_edge_within_scc (cs
))
1659 ret
= dest_lat
->set_contains_variable ();
1661 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1663 tree cstval
= ipa_get_jf_pass_through_result (jfunc
, src_val
->value
,
1667 ret
|= dest_lat
->add_value (cstval
, cs
, src_val
, src_idx
);
1669 ret
|= dest_lat
->set_contains_variable ();
1675 /* Propagate values through an ancestor jump function JFUNC associated with
1676 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1677 is the index of the source parameter. */
1680 propagate_vals_across_ancestor (struct cgraph_edge
*cs
,
1681 struct ipa_jump_func
*jfunc
,
1682 ipcp_lattice
<tree
> *src_lat
,
1683 ipcp_lattice
<tree
> *dest_lat
, int src_idx
)
1685 ipcp_value
<tree
> *src_val
;
1688 if (ipa_edge_within_scc (cs
))
1689 return dest_lat
->set_contains_variable ();
1691 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1693 tree t
= ipa_get_jf_ancestor_result (jfunc
, src_val
->value
);
1696 ret
|= dest_lat
->add_value (t
, cs
, src_val
, src_idx
);
1698 ret
|= dest_lat
->set_contains_variable ();
1704 /* Propagate scalar values across jump function JFUNC that is associated with
1705 edge CS and put the values into DEST_LAT. PARM_TYPE is the type of the
1706 parameter to which the result is passed. */
1709 propagate_scalar_across_jump_function (struct cgraph_edge
*cs
,
1710 struct ipa_jump_func
*jfunc
,
1711 ipcp_lattice
<tree
> *dest_lat
,
1714 if (dest_lat
->bottom
)
1717 if (jfunc
->type
== IPA_JF_CONST
)
1719 tree val
= ipa_get_jf_constant (jfunc
);
1720 return dest_lat
->add_value (val
, cs
, NULL
, 0);
1722 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1723 || jfunc
->type
== IPA_JF_ANCESTOR
)
1725 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1726 ipcp_lattice
<tree
> *src_lat
;
1730 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1731 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1733 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1735 src_lat
= ipa_get_scalar_lat (caller_info
, src_idx
);
1736 if (src_lat
->bottom
)
1737 return dest_lat
->set_contains_variable ();
1739 /* If we would need to clone the caller and cannot, do not propagate. */
1740 if (!ipcp_versionable_function_p (cs
->caller
)
1741 && (src_lat
->contains_variable
1742 || (src_lat
->values_count
> 1)))
1743 return dest_lat
->set_contains_variable ();
1745 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1746 ret
= propagate_vals_across_pass_through (cs
, jfunc
, src_lat
,
1747 dest_lat
, src_idx
, param_type
);
1749 ret
= propagate_vals_across_ancestor (cs
, jfunc
, src_lat
, dest_lat
,
1752 if (src_lat
->contains_variable
)
1753 ret
|= dest_lat
->set_contains_variable ();
1758 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1759 use it for indirect inlining), we should propagate them too. */
1760 return dest_lat
->set_contains_variable ();
1763 /* Propagate scalar values across jump function JFUNC that is associated with
1764 edge CS and describes argument IDX and put the values into DEST_LAT. */
1767 propagate_context_across_jump_function (cgraph_edge
*cs
,
1768 ipa_jump_func
*jfunc
, int idx
,
1769 ipcp_lattice
<ipa_polymorphic_call_context
> *dest_lat
)
1771 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
1772 if (dest_lat
->bottom
)
1775 bool added_sth
= false;
1776 bool type_preserved
= true;
1778 ipa_polymorphic_call_context edge_ctx
, *edge_ctx_ptr
1779 = ipa_get_ith_polymorhic_call_context (args
, idx
);
1782 edge_ctx
= *edge_ctx_ptr
;
1784 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1785 || jfunc
->type
== IPA_JF_ANCESTOR
)
1787 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1789 ipcp_lattice
<ipa_polymorphic_call_context
> *src_lat
;
1791 /* TODO: Once we figure out how to propagate speculations, it will
1792 probably be a good idea to switch to speculation if type_preserved is
1793 not set instead of punting. */
1794 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1796 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1798 type_preserved
= ipa_get_jf_pass_through_type_preserved (jfunc
);
1799 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1803 type_preserved
= ipa_get_jf_ancestor_type_preserved (jfunc
);
1804 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1807 src_lat
= ipa_get_poly_ctx_lat (caller_info
, src_idx
);
1808 /* If we would need to clone the caller and cannot, do not propagate. */
1809 if (!ipcp_versionable_function_p (cs
->caller
)
1810 && (src_lat
->contains_variable
1811 || (src_lat
->values_count
> 1)))
1814 ipcp_value
<ipa_polymorphic_call_context
> *src_val
;
1815 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1817 ipa_polymorphic_call_context cur
= src_val
->value
;
1819 if (!type_preserved
)
1820 cur
.possible_dynamic_type_change (cs
->in_polymorphic_cdtor
);
1821 if (jfunc
->type
== IPA_JF_ANCESTOR
)
1822 cur
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
1823 /* TODO: In cases we know how the context is going to be used,
1824 we can improve the result by passing proper OTR_TYPE. */
1825 cur
.combine_with (edge_ctx
);
1826 if (!cur
.useless_p ())
1828 if (src_lat
->contains_variable
1829 && !edge_ctx
.equal_to (cur
))
1830 ret
|= dest_lat
->set_contains_variable ();
1831 ret
|= dest_lat
->add_value (cur
, cs
, src_val
, src_idx
);
1841 if (!edge_ctx
.useless_p ())
1842 ret
|= dest_lat
->add_value (edge_ctx
, cs
);
1844 ret
|= dest_lat
->set_contains_variable ();
1850 /* Propagate bits across jfunc that is associated with
1851 edge cs and update dest_lattice accordingly. */
1854 propagate_bits_across_jump_function (cgraph_edge
*cs
, int idx
,
1855 ipa_jump_func
*jfunc
,
1856 ipcp_bits_lattice
*dest_lattice
)
1858 if (dest_lattice
->bottom_p ())
1861 enum availability availability
;
1862 cgraph_node
*callee
= cs
->callee
->function_symbol (&availability
);
1863 class ipa_node_params
*callee_info
= IPA_NODE_REF (callee
);
1864 tree parm_type
= ipa_get_type (callee_info
, idx
);
1866 /* For K&R C programs, ipa_get_type() could return NULL_TREE. Avoid the
1867 transform for these cases. Similarly, we can have bad type mismatches
1868 with LTO, avoid doing anything with those too. */
1870 || (!INTEGRAL_TYPE_P (parm_type
) && !POINTER_TYPE_P (parm_type
)))
1872 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1873 fprintf (dump_file
, "Setting dest_lattice to bottom, because type of "
1874 "param %i of %s is NULL or unsuitable for bits propagation\n",
1875 idx
, cs
->callee
->name ());
1877 return dest_lattice
->set_to_bottom ();
1880 unsigned precision
= TYPE_PRECISION (parm_type
);
1881 signop sgn
= TYPE_SIGN (parm_type
);
1883 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1884 || jfunc
->type
== IPA_JF_ANCESTOR
)
1886 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1887 tree operand
= NULL_TREE
;
1888 enum tree_code code
;
1891 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1893 code
= ipa_get_jf_pass_through_operation (jfunc
);
1894 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1895 if (code
!= NOP_EXPR
)
1896 operand
= ipa_get_jf_pass_through_operand (jfunc
);
1900 code
= POINTER_PLUS_EXPR
;
1901 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1902 unsigned HOST_WIDE_INT offset
= ipa_get_jf_ancestor_offset (jfunc
) / BITS_PER_UNIT
;
1903 operand
= build_int_cstu (size_type_node
, offset
);
1906 class ipcp_param_lattices
*src_lats
1907 = ipa_get_parm_lattices (caller_info
, src_idx
);
1909 /* Try to propagate bits if src_lattice is bottom, but jfunc is known.
1915 Assume lattice for x is bottom, however we can still propagate
1916 result of x & 0xff == 0xff, which gets computed during ccp1 pass
1917 and we store it in jump function during analysis stage. */
1919 if (src_lats
->bits_lattice
.bottom_p ()
1921 return dest_lattice
->meet_with (jfunc
->bits
->value
, jfunc
->bits
->mask
,
1924 return dest_lattice
->meet_with (src_lats
->bits_lattice
, precision
, sgn
,
1928 else if (jfunc
->type
== IPA_JF_ANCESTOR
)
1929 return dest_lattice
->set_to_bottom ();
1930 else if (jfunc
->bits
)
1931 return dest_lattice
->meet_with (jfunc
->bits
->value
, jfunc
->bits
->mask
,
1934 return dest_lattice
->set_to_bottom ();
1937 /* Emulate effects of unary OPERATION and/or conversion from SRC_TYPE to
1938 DST_TYPE on value range in SRC_VR and store it to DST_VR. Return true if
1939 the result is a range or an anti-range. */
1942 ipa_vr_operation_and_type_effects (value_range_base
*dst_vr
,
1943 value_range_base
*src_vr
,
1944 enum tree_code operation
,
1945 tree dst_type
, tree src_type
)
1947 range_fold_unary_expr (dst_vr
, operation
, dst_type
, src_vr
, src_type
);
1948 if (dst_vr
->varying_p () || dst_vr
->undefined_p ())
1953 /* Propagate value range across jump function JFUNC that is associated with
1954 edge CS with param of callee of PARAM_TYPE and update DEST_PLATS
1958 propagate_vr_across_jump_function (cgraph_edge
*cs
, ipa_jump_func
*jfunc
,
1959 class ipcp_param_lattices
*dest_plats
,
1962 ipcp_vr_lattice
*dest_lat
= &dest_plats
->m_value_range
;
1964 if (dest_lat
->bottom_p ())
1968 || (!INTEGRAL_TYPE_P (param_type
)
1969 && !POINTER_TYPE_P (param_type
)))
1970 return dest_lat
->set_to_bottom ();
1972 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1974 enum tree_code operation
= ipa_get_jf_pass_through_operation (jfunc
);
1976 if (TREE_CODE_CLASS (operation
) == tcc_unary
)
1978 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1979 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1980 tree operand_type
= ipa_get_type (caller_info
, src_idx
);
1981 class ipcp_param_lattices
*src_lats
1982 = ipa_get_parm_lattices (caller_info
, src_idx
);
1984 if (src_lats
->m_value_range
.bottom_p ())
1985 return dest_lat
->set_to_bottom ();
1986 value_range_base vr
;
1987 if (ipa_vr_operation_and_type_effects (&vr
,
1988 &src_lats
->m_value_range
.m_vr
,
1989 operation
, param_type
,
1991 return dest_lat
->meet_with (&vr
);
1994 else if (jfunc
->type
== IPA_JF_CONST
)
1996 tree val
= ipa_get_jf_constant (jfunc
);
1997 if (TREE_CODE (val
) == INTEGER_CST
)
1999 val
= fold_convert (param_type
, val
);
2000 if (TREE_OVERFLOW_P (val
))
2001 val
= drop_tree_overflow (val
);
2003 value_range_base
tmpvr (VR_RANGE
, val
, val
);
2004 return dest_lat
->meet_with (&tmpvr
);
2008 value_range_base vr
;
2010 && ipa_vr_operation_and_type_effects (&vr
, jfunc
->m_vr
, NOP_EXPR
,
2012 jfunc
->m_vr
->type ()))
2013 return dest_lat
->meet_with (&vr
);
2015 return dest_lat
->set_to_bottom ();
2018 /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
2019 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
2020 other cases, return false). If there are no aggregate items, set
2021 aggs_by_ref to NEW_AGGS_BY_REF. */
2024 set_check_aggs_by_ref (class ipcp_param_lattices
*dest_plats
,
2025 bool new_aggs_by_ref
)
2027 if (dest_plats
->aggs
)
2029 if (dest_plats
->aggs_by_ref
!= new_aggs_by_ref
)
2031 set_agg_lats_to_bottom (dest_plats
);
2036 dest_plats
->aggs_by_ref
= new_aggs_by_ref
;
2040 /* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
2041 already existing lattice for the given OFFSET and SIZE, marking all skipped
2042 lattices as containing variable and checking for overlaps. If there is no
2043 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
2044 it with offset, size and contains_variable to PRE_EXISTING, and return true,
2045 unless there are too many already. If there are two many, return false. If
2046 there are overlaps turn whole DEST_PLATS to bottom and return false. If any
2047 skipped lattices were newly marked as containing variable, set *CHANGE to
2051 merge_agg_lats_step (class ipcp_param_lattices
*dest_plats
,
2052 HOST_WIDE_INT offset
, HOST_WIDE_INT val_size
,
2053 struct ipcp_agg_lattice
***aglat
,
2054 bool pre_existing
, bool *change
)
2056 gcc_checking_assert (offset
>= 0);
2058 while (**aglat
&& (**aglat
)->offset
< offset
)
2060 if ((**aglat
)->offset
+ (**aglat
)->size
> offset
)
2062 set_agg_lats_to_bottom (dest_plats
);
2065 *change
|= (**aglat
)->set_contains_variable ();
2066 *aglat
= &(**aglat
)->next
;
2069 if (**aglat
&& (**aglat
)->offset
== offset
)
2071 if ((**aglat
)->size
!= val_size
)
2073 set_agg_lats_to_bottom (dest_plats
);
2076 gcc_assert (!(**aglat
)->next
2077 || (**aglat
)->next
->offset
>= offset
+ val_size
);
2082 struct ipcp_agg_lattice
*new_al
;
2084 if (**aglat
&& (**aglat
)->offset
< offset
+ val_size
)
2086 set_agg_lats_to_bottom (dest_plats
);
2089 if (dest_plats
->aggs_count
== PARAM_VALUE (PARAM_IPA_MAX_AGG_ITEMS
))
2091 dest_plats
->aggs_count
++;
2092 new_al
= ipcp_agg_lattice_pool
.allocate ();
2093 memset (new_al
, 0, sizeof (*new_al
));
2095 new_al
->offset
= offset
;
2096 new_al
->size
= val_size
;
2097 new_al
->contains_variable
= pre_existing
;
2099 new_al
->next
= **aglat
;
2105 /* Set all AGLAT and all other aggregate lattices reachable by next pointers as
2106 containing an unknown value. */
2109 set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice
*aglat
)
2114 ret
|= aglat
->set_contains_variable ();
2115 aglat
= aglat
->next
;
2120 /* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
2121 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source
2122 parameter used for lattice value sources. Return true if DEST_PLATS changed
2126 merge_aggregate_lattices (struct cgraph_edge
*cs
,
2127 class ipcp_param_lattices
*dest_plats
,
2128 class ipcp_param_lattices
*src_plats
,
2129 int src_idx
, HOST_WIDE_INT offset_delta
)
2131 bool pre_existing
= dest_plats
->aggs
!= NULL
;
2132 struct ipcp_agg_lattice
**dst_aglat
;
2135 if (set_check_aggs_by_ref (dest_plats
, src_plats
->aggs_by_ref
))
2137 if (src_plats
->aggs_bottom
)
2138 return set_agg_lats_contain_variable (dest_plats
);
2139 if (src_plats
->aggs_contain_variable
)
2140 ret
|= set_agg_lats_contain_variable (dest_plats
);
2141 dst_aglat
= &dest_plats
->aggs
;
2143 for (struct ipcp_agg_lattice
*src_aglat
= src_plats
->aggs
;
2145 src_aglat
= src_aglat
->next
)
2147 HOST_WIDE_INT new_offset
= src_aglat
->offset
- offset_delta
;
2151 if (merge_agg_lats_step (dest_plats
, new_offset
, src_aglat
->size
,
2152 &dst_aglat
, pre_existing
, &ret
))
2154 struct ipcp_agg_lattice
*new_al
= *dst_aglat
;
2156 dst_aglat
= &(*dst_aglat
)->next
;
2157 if (src_aglat
->bottom
)
2159 ret
|= new_al
->set_contains_variable ();
2162 if (src_aglat
->contains_variable
)
2163 ret
|= new_al
->set_contains_variable ();
2164 for (ipcp_value
<tree
> *val
= src_aglat
->values
;
2167 ret
|= new_al
->add_value (val
->value
, cs
, val
, src_idx
,
2170 else if (dest_plats
->aggs_bottom
)
2173 ret
|= set_chain_of_aglats_contains_variable (*dst_aglat
);
2177 /* Determine whether there is anything to propagate FROM SRC_PLATS through a
2178 pass-through JFUNC and if so, whether it has conform and conforms to the
2179 rules about propagating values passed by reference. */
2182 agg_pass_through_permissible_p (class ipcp_param_lattices
*src_plats
,
2183 struct ipa_jump_func
*jfunc
)
2185 return src_plats
->aggs
2186 && (!src_plats
->aggs_by_ref
2187 || ipa_get_jf_pass_through_agg_preserved (jfunc
));
2190 /* Propagate scalar values across jump function JFUNC that is associated with
2191 edge CS and put the values into DEST_LAT. */
2194 propagate_aggs_across_jump_function (struct cgraph_edge
*cs
,
2195 struct ipa_jump_func
*jfunc
,
2196 class ipcp_param_lattices
*dest_plats
)
2200 if (dest_plats
->aggs_bottom
)
2203 if (jfunc
->type
== IPA_JF_PASS_THROUGH
2204 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
2206 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2207 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
2208 class ipcp_param_lattices
*src_plats
;
2210 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2211 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
2213 /* Currently we do not produce clobber aggregate jump
2214 functions, replace with merging when we do. */
2215 gcc_assert (!jfunc
->agg
.items
);
2216 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
,
2220 ret
|= set_agg_lats_contain_variable (dest_plats
);
2222 else if (jfunc
->type
== IPA_JF_ANCESTOR
2223 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
2225 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2226 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
2227 class ipcp_param_lattices
*src_plats
;
2229 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2230 if (src_plats
->aggs
&& src_plats
->aggs_by_ref
)
2232 /* Currently we do not produce clobber aggregate jump
2233 functions, replace with merging when we do. */
2234 gcc_assert (!jfunc
->agg
.items
);
2235 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
, src_idx
,
2236 ipa_get_jf_ancestor_offset (jfunc
));
2238 else if (!src_plats
->aggs_by_ref
)
2239 ret
|= set_agg_lats_to_bottom (dest_plats
);
2241 ret
|= set_agg_lats_contain_variable (dest_plats
);
2243 else if (jfunc
->agg
.items
)
2245 bool pre_existing
= dest_plats
->aggs
!= NULL
;
2246 struct ipcp_agg_lattice
**aglat
= &dest_plats
->aggs
;
2247 struct ipa_agg_jf_item
*item
;
2250 if (set_check_aggs_by_ref (dest_plats
, jfunc
->agg
.by_ref
))
2253 FOR_EACH_VEC_ELT (*jfunc
->agg
.items
, i
, item
)
2255 HOST_WIDE_INT val_size
;
2257 if (item
->offset
< 0)
2259 gcc_checking_assert (is_gimple_ip_invariant (item
->value
));
2260 val_size
= tree_to_uhwi (TYPE_SIZE (TREE_TYPE (item
->value
)));
2262 if (merge_agg_lats_step (dest_plats
, item
->offset
, val_size
,
2263 &aglat
, pre_existing
, &ret
))
2265 ret
|= (*aglat
)->add_value (item
->value
, cs
, NULL
, 0, 0);
2266 aglat
= &(*aglat
)->next
;
2268 else if (dest_plats
->aggs_bottom
)
2272 ret
|= set_chain_of_aglats_contains_variable (*aglat
);
2275 ret
|= set_agg_lats_contain_variable (dest_plats
);
2280 /* Return true if on the way cfrom CS->caller to the final (non-alias and
2281 non-thunk) destination, the call passes through a thunk. */
2284 call_passes_through_thunk_p (cgraph_edge
*cs
)
2286 cgraph_node
*alias_or_thunk
= cs
->callee
;
2287 while (alias_or_thunk
->alias
)
2288 alias_or_thunk
= alias_or_thunk
->get_alias_target ();
2289 return alias_or_thunk
->thunk
.thunk_p
;
2292 /* Propagate constants from the caller to the callee of CS. INFO describes the
2296 propagate_constants_across_call (struct cgraph_edge
*cs
)
2298 class ipa_node_params
*callee_info
;
2299 enum availability availability
;
2300 cgraph_node
*callee
;
2301 class ipa_edge_args
*args
;
2303 int i
, args_count
, parms_count
;
2305 callee
= cs
->callee
->function_symbol (&availability
);
2306 if (!callee
->definition
)
2308 gcc_checking_assert (callee
->has_gimple_body_p ());
2309 callee_info
= IPA_NODE_REF (callee
);
2311 args
= IPA_EDGE_REF (cs
);
2312 args_count
= ipa_get_cs_argument_count (args
);
2313 parms_count
= ipa_get_param_count (callee_info
);
2314 if (parms_count
== 0)
2317 /* If this call goes through a thunk we must not propagate to the first (0th)
2318 parameter. However, we might need to uncover a thunk from below a series
2319 of aliases first. */
2320 if (call_passes_through_thunk_p (cs
))
2322 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
2329 for (; (i
< args_count
) && (i
< parms_count
); i
++)
2331 struct ipa_jump_func
*jump_func
= ipa_get_ith_jump_func (args
, i
);
2332 class ipcp_param_lattices
*dest_plats
;
2333 tree param_type
= ipa_get_type (callee_info
, i
);
2335 dest_plats
= ipa_get_parm_lattices (callee_info
, i
);
2336 if (availability
== AVAIL_INTERPOSABLE
)
2337 ret
|= set_all_contains_variable (dest_plats
);
2340 ret
|= propagate_scalar_across_jump_function (cs
, jump_func
,
2341 &dest_plats
->itself
,
2343 ret
|= propagate_context_across_jump_function (cs
, jump_func
, i
,
2344 &dest_plats
->ctxlat
);
2346 |= propagate_bits_across_jump_function (cs
, i
, jump_func
,
2347 &dest_plats
->bits_lattice
);
2348 ret
|= propagate_aggs_across_jump_function (cs
, jump_func
,
2350 if (opt_for_fn (callee
->decl
, flag_ipa_vrp
))
2351 ret
|= propagate_vr_across_jump_function (cs
, jump_func
,
2352 dest_plats
, param_type
);
2354 ret
|= dest_plats
->m_value_range
.set_to_bottom ();
2357 for (; i
< parms_count
; i
++)
2358 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
, i
));
2363 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
2364 KNOWN_CONTEXTS, KNOWN_AGGS or AGG_REPS return the destination. The latter
2365 three can be NULL. If AGG_REPS is not NULL, KNOWN_AGGS is ignored. */
2368 ipa_get_indirect_edge_target_1 (struct cgraph_edge
*ie
,
2369 vec
<tree
> known_csts
,
2370 vec
<ipa_polymorphic_call_context
> known_contexts
,
2371 vec
<ipa_agg_jump_function_p
> known_aggs
,
2372 struct ipa_agg_replacement_value
*agg_reps
,
2375 int param_index
= ie
->indirect_info
->param_index
;
2376 HOST_WIDE_INT anc_offset
;
2380 *speculative
= false;
2382 if (param_index
== -1
2383 || known_csts
.length () <= (unsigned int) param_index
)
2386 if (!ie
->indirect_info
->polymorphic
)
2390 if (ie
->indirect_info
->agg_contents
)
2393 if (agg_reps
&& ie
->indirect_info
->guaranteed_unmodified
)
2397 if (agg_reps
->index
== param_index
2398 && agg_reps
->offset
== ie
->indirect_info
->offset
2399 && agg_reps
->by_ref
== ie
->indirect_info
->by_ref
)
2401 t
= agg_reps
->value
;
2404 agg_reps
= agg_reps
->next
;
2409 struct ipa_agg_jump_function
*agg
;
2410 if (known_aggs
.length () > (unsigned int) param_index
)
2411 agg
= known_aggs
[param_index
];
2414 bool from_global_constant
;
2415 t
= ipa_find_agg_cst_for_param (agg
, known_csts
[param_index
],
2416 ie
->indirect_info
->offset
,
2417 ie
->indirect_info
->by_ref
,
2418 &from_global_constant
);
2420 && !from_global_constant
2421 && !ie
->indirect_info
->guaranteed_unmodified
)
2426 t
= known_csts
[param_index
];
2429 && TREE_CODE (t
) == ADDR_EXPR
2430 && TREE_CODE (TREE_OPERAND (t
, 0)) == FUNCTION_DECL
)
2431 return TREE_OPERAND (t
, 0);
2436 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize
))
2439 gcc_assert (!ie
->indirect_info
->agg_contents
);
2440 anc_offset
= ie
->indirect_info
->offset
;
2444 /* Try to work out value of virtual table pointer value in replacements. */
2445 if (!t
&& agg_reps
&& !ie
->indirect_info
->by_ref
)
2449 if (agg_reps
->index
== param_index
2450 && agg_reps
->offset
== ie
->indirect_info
->offset
2451 && agg_reps
->by_ref
)
2453 t
= agg_reps
->value
;
2456 agg_reps
= agg_reps
->next
;
2460 /* Try to work out value of virtual table pointer value in known
2461 aggregate values. */
2462 if (!t
&& known_aggs
.length () > (unsigned int) param_index
2463 && !ie
->indirect_info
->by_ref
)
2465 struct ipa_agg_jump_function
*agg
;
2466 agg
= known_aggs
[param_index
];
2467 t
= ipa_find_agg_cst_for_param (agg
, known_csts
[param_index
],
2468 ie
->indirect_info
->offset
, true);
2471 /* If we found the virtual table pointer, lookup the target. */
2475 unsigned HOST_WIDE_INT offset
;
2476 if (vtable_pointer_value_to_vtable (t
, &vtable
, &offset
))
2479 target
= gimple_get_virt_method_for_vtable (ie
->indirect_info
->otr_token
,
2480 vtable
, offset
, &can_refer
);
2484 || fndecl_built_in_p (target
, BUILT_IN_UNREACHABLE
)
2485 || !possible_polymorphic_call_target_p
2486 (ie
, cgraph_node::get (target
)))
2488 /* Do not speculate builtin_unreachable, it is stupid! */
2489 if (ie
->indirect_info
->vptr_changed
)
2491 target
= ipa_impossible_devirt_target (ie
, target
);
2493 *speculative
= ie
->indirect_info
->vptr_changed
;
2500 /* Do we know the constant value of pointer? */
2502 t
= known_csts
[param_index
];
2504 gcc_checking_assert (!t
|| TREE_CODE (t
) != TREE_BINFO
);
2506 ipa_polymorphic_call_context context
;
2507 if (known_contexts
.length () > (unsigned int) param_index
)
2509 context
= known_contexts
[param_index
];
2510 context
.offset_by (anc_offset
);
2511 if (ie
->indirect_info
->vptr_changed
)
2512 context
.possible_dynamic_type_change (ie
->in_polymorphic_cdtor
,
2513 ie
->indirect_info
->otr_type
);
2516 ipa_polymorphic_call_context ctx2
= ipa_polymorphic_call_context
2517 (t
, ie
->indirect_info
->otr_type
, anc_offset
);
2518 if (!ctx2
.useless_p ())
2519 context
.combine_with (ctx2
, ie
->indirect_info
->otr_type
);
2524 context
= ipa_polymorphic_call_context (t
, ie
->indirect_info
->otr_type
,
2526 if (ie
->indirect_info
->vptr_changed
)
2527 context
.possible_dynamic_type_change (ie
->in_polymorphic_cdtor
,
2528 ie
->indirect_info
->otr_type
);
2533 vec
<cgraph_node
*>targets
;
2536 targets
= possible_polymorphic_call_targets
2537 (ie
->indirect_info
->otr_type
,
2538 ie
->indirect_info
->otr_token
,
2540 if (!final
|| targets
.length () > 1)
2542 struct cgraph_node
*node
;
2545 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize_speculatively
)
2546 || ie
->speculative
|| !ie
->maybe_hot_p ())
2548 node
= try_speculative_devirtualization (ie
->indirect_info
->otr_type
,
2549 ie
->indirect_info
->otr_token
,
2553 *speculative
= true;
2554 target
= node
->decl
;
2561 *speculative
= false;
2562 if (targets
.length () == 1)
2563 target
= targets
[0]->decl
;
2565 target
= ipa_impossible_devirt_target (ie
, NULL_TREE
);
2568 if (target
&& !possible_polymorphic_call_target_p (ie
,
2569 cgraph_node::get (target
)))
2573 target
= ipa_impossible_devirt_target (ie
, target
);
2580 /* If an indirect edge IE can be turned into a direct one based on KNOWN_CSTS,
2581 KNOWN_CONTEXTS (which can be vNULL) or KNOWN_AGGS (which also can be vNULL)
2582 return the destination. */
2585 ipa_get_indirect_edge_target (struct cgraph_edge
*ie
,
2586 vec
<tree
> known_csts
,
2587 vec
<ipa_polymorphic_call_context
> known_contexts
,
2588 vec
<ipa_agg_jump_function_p
> known_aggs
,
2591 return ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
2592 known_aggs
, NULL
, speculative
);
2595 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
2596 and KNOWN_CONTEXTS. */
2599 devirtualization_time_bonus (struct cgraph_node
*node
,
2600 vec
<tree
> known_csts
,
2601 vec
<ipa_polymorphic_call_context
> known_contexts
,
2602 vec
<ipa_agg_jump_function_p
> known_aggs
)
2604 struct cgraph_edge
*ie
;
2607 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
2609 struct cgraph_node
*callee
;
2610 class ipa_fn_summary
*isummary
;
2611 enum availability avail
;
2615 target
= ipa_get_indirect_edge_target (ie
, known_csts
, known_contexts
,
2616 known_aggs
, &speculative
);
2620 /* Only bare minimum benefit for clearly un-inlineable targets. */
2622 callee
= cgraph_node::get (target
);
2623 if (!callee
|| !callee
->definition
)
2625 callee
= callee
->function_symbol (&avail
);
2626 if (avail
< AVAIL_AVAILABLE
)
2628 isummary
= ipa_fn_summaries
->get (callee
);
2629 if (!isummary
->inlinable
)
2632 /* FIXME: The values below need re-considering and perhaps also
2633 integrating into the cost metrics, at lest in some very basic way. */
2634 if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 4)
2635 res
+= 31 / ((int)speculative
+ 1);
2636 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 2)
2637 res
+= 15 / ((int)speculative
+ 1);
2638 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
2639 || DECL_DECLARED_INLINE_P (callee
->decl
))
2640 res
+= 7 / ((int)speculative
+ 1);
2646 /* Return time bonus incurred because of HINTS. */
2649 hint_time_bonus (ipa_hints hints
)
2652 if (hints
& (INLINE_HINT_loop_iterations
| INLINE_HINT_loop_stride
))
2653 result
+= PARAM_VALUE (PARAM_IPA_CP_LOOP_HINT_BONUS
);
2657 /* If there is a reason to penalize the function described by INFO in the
2658 cloning goodness evaluation, do so. */
2660 static inline int64_t
2661 incorporate_penalties (ipa_node_params
*info
, int64_t evaluation
)
2663 if (info
->node_within_scc
)
2664 evaluation
= (evaluation
2665 * (100 - PARAM_VALUE (PARAM_IPA_CP_RECURSION_PENALTY
))) / 100;
2667 if (info
->node_calling_single_call
)
2668 evaluation
= (evaluation
2669 * (100 - PARAM_VALUE (PARAM_IPA_CP_SINGLE_CALL_PENALTY
)))
2675 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
2676 and SIZE_COST and with the sum of frequencies of incoming edges to the
2677 potential new clone in FREQUENCIES. */
2680 good_cloning_opportunity_p (struct cgraph_node
*node
, int time_benefit
,
2681 int freq_sum
, profile_count count_sum
, int size_cost
)
2683 if (time_benefit
== 0
2684 || !opt_for_fn (node
->decl
, flag_ipa_cp_clone
)
2685 || node
->optimize_for_size_p ())
2688 gcc_assert (size_cost
> 0);
2690 class ipa_node_params
*info
= IPA_NODE_REF (node
);
2691 if (max_count
> profile_count::zero ())
2693 int factor
= RDIV (count_sum
.probability_in
2694 (max_count
).to_reg_br_prob_base ()
2695 * 1000, REG_BR_PROB_BASE
);
2696 int64_t evaluation
= (((int64_t) time_benefit
* factor
)
2698 evaluation
= incorporate_penalties (info
, evaluation
);
2700 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2702 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
2703 "size: %i, count_sum: ", time_benefit
, size_cost
);
2704 count_sum
.dump (dump_file
);
2705 fprintf (dump_file
, "%s%s) -> evaluation: " "%" PRId64
2706 ", threshold: %i\n",
2707 info
->node_within_scc
? ", scc" : "",
2708 info
->node_calling_single_call
? ", single_call" : "",
2709 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
2712 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
2716 int64_t evaluation
= (((int64_t) time_benefit
* freq_sum
)
2718 evaluation
= incorporate_penalties (info
, evaluation
);
2720 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2721 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
2722 "size: %i, freq_sum: %i%s%s) -> evaluation: "
2723 "%" PRId64
", threshold: %i\n",
2724 time_benefit
, size_cost
, freq_sum
,
2725 info
->node_within_scc
? ", scc" : "",
2726 info
->node_calling_single_call
? ", single_call" : "",
2727 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
2729 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
2733 /* Return all context independent values from aggregate lattices in PLATS in a
2734 vector. Return NULL if there are none. */
2736 static vec
<ipa_agg_jf_item
, va_gc
> *
2737 context_independent_aggregate_values (class ipcp_param_lattices
*plats
)
2739 vec
<ipa_agg_jf_item
, va_gc
> *res
= NULL
;
2741 if (plats
->aggs_bottom
2742 || plats
->aggs_contain_variable
2743 || plats
->aggs_count
== 0)
2746 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
;
2748 aglat
= aglat
->next
)
2749 if (aglat
->is_single_const ())
2751 struct ipa_agg_jf_item item
;
2752 item
.offset
= aglat
->offset
;
2753 item
.value
= aglat
->values
->value
;
2754 vec_safe_push (res
, item
);
2759 /* Allocate KNOWN_CSTS, KNOWN_CONTEXTS and, if non-NULL, KNOWN_AGGS and
2760 populate them with values of parameters that are known independent of the
2761 context. INFO describes the function. If REMOVABLE_PARAMS_COST is
2762 non-NULL, the movement cost of all removable parameters will be stored in
2766 gather_context_independent_values (class ipa_node_params
*info
,
2767 vec
<tree
> *known_csts
,
2768 vec
<ipa_polymorphic_call_context
>
2770 vec
<ipa_agg_jump_function
> *known_aggs
,
2771 int *removable_params_cost
)
2773 int i
, count
= ipa_get_param_count (info
);
2776 known_csts
->create (0);
2777 known_contexts
->create (0);
2778 known_csts
->safe_grow_cleared (count
);
2779 known_contexts
->safe_grow_cleared (count
);
2782 known_aggs
->create (0);
2783 known_aggs
->safe_grow_cleared (count
);
2786 if (removable_params_cost
)
2787 *removable_params_cost
= 0;
2789 for (i
= 0; i
< count
; i
++)
2791 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2792 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
2794 if (lat
->is_single_const ())
2796 ipcp_value
<tree
> *val
= lat
->values
;
2797 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
2798 (*known_csts
)[i
] = val
->value
;
2799 if (removable_params_cost
)
2800 *removable_params_cost
2801 += estimate_move_cost (TREE_TYPE (val
->value
), false);
2804 else if (removable_params_cost
2805 && !ipa_is_param_used (info
, i
))
2806 *removable_params_cost
2807 += ipa_get_param_move_cost (info
, i
);
2809 if (!ipa_is_param_used (info
, i
))
2812 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
2813 /* Do not account known context as reason for cloning. We can see
2814 if it permits devirtualization. */
2815 if (ctxlat
->is_single_const ())
2816 (*known_contexts
)[i
] = ctxlat
->values
->value
;
2820 vec
<ipa_agg_jf_item
, va_gc
> *agg_items
;
2821 struct ipa_agg_jump_function
*ajf
;
2823 agg_items
= context_independent_aggregate_values (plats
);
2824 ajf
= &(*known_aggs
)[i
];
2825 ajf
->items
= agg_items
;
2826 ajf
->by_ref
= plats
->aggs_by_ref
;
2827 ret
|= agg_items
!= NULL
;
2834 /* The current interface in ipa-inline-analysis requires a pointer vector.
2837 FIXME: That interface should be re-worked, this is slightly silly. Still,
2838 I'd like to discuss how to change it first and this demonstrates the
2841 static vec
<ipa_agg_jump_function_p
>
2842 agg_jmp_p_vec_for_t_vec (vec
<ipa_agg_jump_function
> known_aggs
)
2844 vec
<ipa_agg_jump_function_p
> ret
;
2845 struct ipa_agg_jump_function
*ajf
;
2848 ret
.create (known_aggs
.length ());
2849 FOR_EACH_VEC_ELT (known_aggs
, i
, ajf
)
2850 ret
.quick_push (ajf
);
2854 /* Perform time and size measurement of NODE with the context given in
2855 KNOWN_CSTS, KNOWN_CONTEXTS and KNOWN_AGGS, calculate the benefit and cost
2856 given BASE_TIME of the node without specialization, REMOVABLE_PARAMS_COST of
2857 all context-independent removable parameters and EST_MOVE_COST of estimated
2858 movement of the considered parameter and store it into VAL. */
2861 perform_estimation_of_a_value (cgraph_node
*node
, vec
<tree
> known_csts
,
2862 vec
<ipa_polymorphic_call_context
> known_contexts
,
2863 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
,
2864 int removable_params_cost
,
2865 int est_move_cost
, ipcp_value_base
*val
)
2867 int size
, time_benefit
;
2868 sreal time
, base_time
;
2871 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
2872 known_aggs_ptrs
, &size
, &time
,
2873 &base_time
, &hints
);
2875 if (base_time
> 65535)
2878 /* Extern inline functions have no cloning local time benefits because they
2879 will be inlined anyway. The only reason to clone them is if it enables
2880 optimization in any of the functions they call. */
2881 if (DECL_EXTERNAL (node
->decl
) && DECL_DECLARED_INLINE_P (node
->decl
))
2884 time_benefit
= base_time
.to_int ()
2885 + devirtualization_time_bonus (node
, known_csts
, known_contexts
,
2887 + hint_time_bonus (hints
)
2888 + removable_params_cost
+ est_move_cost
;
2890 gcc_checking_assert (size
>=0);
2891 /* The inliner-heuristics based estimates may think that in certain
2892 contexts some functions do not have any size at all but we want
2893 all specializations to have at least a tiny cost, not least not to
2898 val
->local_time_benefit
= time_benefit
;
2899 val
->local_size_cost
= size
;
2902 /* Iterate over known values of parameters of NODE and estimate the local
2903 effects in terms of time and size they have. */
2906 estimate_local_effects (struct cgraph_node
*node
)
2908 class ipa_node_params
*info
= IPA_NODE_REF (node
);
2909 int i
, count
= ipa_get_param_count (info
);
2910 vec
<tree
> known_csts
;
2911 vec
<ipa_polymorphic_call_context
> known_contexts
;
2912 vec
<ipa_agg_jump_function
> known_aggs
;
2913 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
;
2915 int removable_params_cost
;
2917 if (!count
|| !ipcp_versionable_function_p (node
))
2920 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2921 fprintf (dump_file
, "\nEstimating effects for %s.\n", node
->dump_name ());
2923 always_const
= gather_context_independent_values (info
, &known_csts
,
2924 &known_contexts
, &known_aggs
,
2925 &removable_params_cost
);
2926 known_aggs_ptrs
= agg_jmp_p_vec_for_t_vec (known_aggs
);
2927 int devirt_bonus
= devirtualization_time_bonus (node
, known_csts
,
2928 known_contexts
, known_aggs_ptrs
);
2929 if (always_const
|| devirt_bonus
2930 || (removable_params_cost
&& node
->local
.can_change_signature
))
2932 struct caller_statistics stats
;
2934 sreal time
, base_time
;
2937 init_caller_stats (&stats
);
2938 node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
2940 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
2941 known_aggs_ptrs
, &size
, &time
,
2942 &base_time
, &hints
);
2943 time
-= devirt_bonus
;
2944 time
-= hint_time_bonus (hints
);
2945 time
-= removable_params_cost
;
2946 size
-= stats
.n_calls
* removable_params_cost
;
2949 fprintf (dump_file
, " - context independent values, size: %i, "
2950 "time_benefit: %f\n", size
, (base_time
- time
).to_double ());
2952 if (size
<= 0 || node
->local
.local
)
2954 info
->do_clone_for_all_contexts
= true;
2957 fprintf (dump_file
, " Decided to specialize for all "
2958 "known contexts, code not going to grow.\n");
2960 else if (good_cloning_opportunity_p (node
,
2961 MIN ((base_time
- time
).to_int (),
2963 stats
.freq_sum
, stats
.count_sum
,
2966 if (size
+ overall_size
<= max_new_size
)
2968 info
->do_clone_for_all_contexts
= true;
2969 overall_size
+= size
;
2972 fprintf (dump_file
, " Decided to specialize for all "
2973 "known contexts, growth deemed beneficial.\n");
2975 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2976 fprintf (dump_file
, " Not cloning for all contexts because "
2977 "max_new_size would be reached with %li.\n",
2978 size
+ overall_size
);
2980 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2981 fprintf (dump_file
, " Not cloning for all contexts because "
2982 "!good_cloning_opportunity_p.\n");
2986 for (i
= 0; i
< count
; i
++)
2988 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2989 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
2990 ipcp_value
<tree
> *val
;
2997 for (val
= lat
->values
; val
; val
= val
->next
)
2999 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
3000 known_csts
[i
] = val
->value
;
3002 int emc
= estimate_move_cost (TREE_TYPE (val
->value
), true);
3003 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
3005 removable_params_cost
, emc
, val
);
3007 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3009 fprintf (dump_file
, " - estimates for value ");
3010 print_ipcp_constant_value (dump_file
, val
->value
);
3011 fprintf (dump_file
, " for ");
3012 ipa_dump_param (dump_file
, info
, i
);
3013 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
3014 val
->local_time_benefit
, val
->local_size_cost
);
3017 known_csts
[i
] = NULL_TREE
;
3020 for (i
= 0; i
< count
; i
++)
3022 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3024 if (!plats
->virt_call
)
3027 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
3028 ipcp_value
<ipa_polymorphic_call_context
> *val
;
3032 || !known_contexts
[i
].useless_p ())
3035 for (val
= ctxlat
->values
; val
; val
= val
->next
)
3037 known_contexts
[i
] = val
->value
;
3038 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
3040 removable_params_cost
, 0, val
);
3042 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3044 fprintf (dump_file
, " - estimates for polymorphic context ");
3045 print_ipcp_constant_value (dump_file
, val
->value
);
3046 fprintf (dump_file
, " for ");
3047 ipa_dump_param (dump_file
, info
, i
);
3048 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
3049 val
->local_time_benefit
, val
->local_size_cost
);
3052 known_contexts
[i
] = ipa_polymorphic_call_context ();
3055 for (i
= 0; i
< count
; i
++)
3057 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3058 struct ipa_agg_jump_function
*ajf
;
3059 struct ipcp_agg_lattice
*aglat
;
3061 if (plats
->aggs_bottom
|| !plats
->aggs
)
3064 ajf
= &known_aggs
[i
];
3065 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3067 ipcp_value
<tree
> *val
;
3068 if (aglat
->bottom
|| !aglat
->values
3069 /* If the following is true, the one value is in known_aggs. */
3070 || (!plats
->aggs_contain_variable
3071 && aglat
->is_single_const ()))
3074 for (val
= aglat
->values
; val
; val
= val
->next
)
3076 struct ipa_agg_jf_item item
;
3078 item
.offset
= aglat
->offset
;
3079 item
.value
= val
->value
;
3080 vec_safe_push (ajf
->items
, item
);
3082 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
3084 removable_params_cost
, 0, val
);
3086 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3088 fprintf (dump_file
, " - estimates for value ");
3089 print_ipcp_constant_value (dump_file
, val
->value
);
3090 fprintf (dump_file
, " for ");
3091 ipa_dump_param (dump_file
, info
, i
);
3092 fprintf (dump_file
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
3093 "]: time_benefit: %i, size: %i\n",
3094 plats
->aggs_by_ref
? "ref " : "",
3096 val
->local_time_benefit
, val
->local_size_cost
);
3104 for (i
= 0; i
< count
; i
++)
3105 vec_free (known_aggs
[i
].items
);
3107 known_csts
.release ();
3108 known_contexts
.release ();
3109 known_aggs
.release ();
3110 known_aggs_ptrs
.release ();
3114 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
3115 topological sort of values. */
3117 template <typename valtype
>
3119 value_topo_info
<valtype
>::add_val (ipcp_value
<valtype
> *cur_val
)
3121 ipcp_value_source
<valtype
> *src
;
3127 cur_val
->dfs
= dfs_counter
;
3128 cur_val
->low_link
= dfs_counter
;
3130 cur_val
->topo_next
= stack
;
3132 cur_val
->on_stack
= true;
3134 for (src
= cur_val
->sources
; src
; src
= src
->next
)
3137 if (src
->val
->dfs
== 0)
3140 if (src
->val
->low_link
< cur_val
->low_link
)
3141 cur_val
->low_link
= src
->val
->low_link
;
3143 else if (src
->val
->on_stack
3144 && src
->val
->dfs
< cur_val
->low_link
)
3145 cur_val
->low_link
= src
->val
->dfs
;
3148 if (cur_val
->dfs
== cur_val
->low_link
)
3150 ipcp_value
<valtype
> *v
, *scc_list
= NULL
;
3155 stack
= v
->topo_next
;
3156 v
->on_stack
= false;
3158 v
->scc_next
= scc_list
;
3161 while (v
!= cur_val
);
3163 cur_val
->topo_next
= values_topo
;
3164 values_topo
= cur_val
;
3168 /* Add all values in lattices associated with NODE to the topological sort if
3169 they are not there yet. */
3172 add_all_node_vals_to_toposort (cgraph_node
*node
, ipa_topo_info
*topo
)
3174 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3175 int i
, count
= ipa_get_param_count (info
);
3177 for (i
= 0; i
< count
; i
++)
3179 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3180 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
3181 struct ipcp_agg_lattice
*aglat
;
3185 ipcp_value
<tree
> *val
;
3186 for (val
= lat
->values
; val
; val
= val
->next
)
3187 topo
->constants
.add_val (val
);
3190 if (!plats
->aggs_bottom
)
3191 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3194 ipcp_value
<tree
> *val
;
3195 for (val
= aglat
->values
; val
; val
= val
->next
)
3196 topo
->constants
.add_val (val
);
3199 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
3200 if (!ctxlat
->bottom
)
3202 ipcp_value
<ipa_polymorphic_call_context
> *ctxval
;
3203 for (ctxval
= ctxlat
->values
; ctxval
; ctxval
= ctxval
->next
)
3204 topo
->contexts
.add_val (ctxval
);
3209 /* One pass of constants propagation along the call graph edges, from callers
3210 to callees (requires topological ordering in TOPO), iterate over strongly
3211 connected components. */
3214 propagate_constants_topo (class ipa_topo_info
*topo
)
3218 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
3221 struct cgraph_node
*v
, *node
= topo
->order
[i
];
3222 vec
<cgraph_node
*> cycle_nodes
= ipa_get_nodes_in_cycle (node
);
3224 /* First, iteratively propagate within the strongly connected component
3225 until all lattices stabilize. */
3226 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
3227 if (v
->has_gimple_body_p ())
3228 push_node_to_stack (topo
, v
);
3230 v
= pop_node_from_stack (topo
);
3233 struct cgraph_edge
*cs
;
3235 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3236 if (ipa_edge_within_scc (cs
))
3238 IPA_NODE_REF (v
)->node_within_scc
= true;
3239 if (propagate_constants_across_call (cs
))
3240 push_node_to_stack (topo
, cs
->callee
->function_symbol ());
3242 v
= pop_node_from_stack (topo
);
3245 /* Afterwards, propagate along edges leading out of the SCC, calculates
3246 the local effects of the discovered constants and all valid values to
3247 their topological sort. */
3248 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
3249 if (v
->has_gimple_body_p ())
3251 struct cgraph_edge
*cs
;
3253 estimate_local_effects (v
);
3254 add_all_node_vals_to_toposort (v
, topo
);
3255 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3256 if (!ipa_edge_within_scc (cs
))
3257 propagate_constants_across_call (cs
);
3259 cycle_nodes
.release ();
3264 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
3265 the bigger one if otherwise. */
3268 safe_add (int a
, int b
)
3270 if (a
> INT_MAX
/2 || b
> INT_MAX
/2)
3271 return a
> b
? a
: b
;
3277 /* Propagate the estimated effects of individual values along the topological
3278 from the dependent values to those they depend on. */
3280 template <typename valtype
>
3282 value_topo_info
<valtype
>::propagate_effects ()
3284 ipcp_value
<valtype
> *base
;
3286 for (base
= values_topo
; base
; base
= base
->topo_next
)
3288 ipcp_value_source
<valtype
> *src
;
3289 ipcp_value
<valtype
> *val
;
3290 int time
= 0, size
= 0;
3292 for (val
= base
; val
; val
= val
->scc_next
)
3294 time
= safe_add (time
,
3295 val
->local_time_benefit
+ val
->prop_time_benefit
);
3296 size
= safe_add (size
, val
->local_size_cost
+ val
->prop_size_cost
);
3299 for (val
= base
; val
; val
= val
->scc_next
)
3300 for (src
= val
->sources
; src
; src
= src
->next
)
3302 && src
->cs
->maybe_hot_p ())
3304 src
->val
->prop_time_benefit
= safe_add (time
,
3305 src
->val
->prop_time_benefit
);
3306 src
->val
->prop_size_cost
= safe_add (size
,
3307 src
->val
->prop_size_cost
);
3313 /* Propagate constants, polymorphic contexts and their effects from the
3314 summaries interprocedurally. */
3317 ipcp_propagate_stage (class ipa_topo_info
*topo
)
3319 struct cgraph_node
*node
;
3322 fprintf (dump_file
, "\n Propagating constants:\n\n");
3324 max_count
= profile_count::uninitialized ();
3326 FOR_EACH_DEFINED_FUNCTION (node
)
3328 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3330 determine_versionability (node
, info
);
3331 if (node
->has_gimple_body_p ())
3333 info
->lattices
= XCNEWVEC (class ipcp_param_lattices
,
3334 ipa_get_param_count (info
));
3335 initialize_node_lattices (node
);
3337 ipa_fn_summary
*s
= ipa_fn_summaries
->get (node
);
3338 if (node
->definition
&& !node
->alias
&& s
!= NULL
)
3339 overall_size
+= s
->self_size
;
3340 max_count
= max_count
.max (node
->count
.ipa ());
3343 max_new_size
= overall_size
;
3344 if (max_new_size
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
3345 max_new_size
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
3346 max_new_size
+= max_new_size
* PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH
) / 100 + 1;
3349 fprintf (dump_file
, "\noverall_size: %li, max_new_size: %li\n",
3350 overall_size
, max_new_size
);
3352 propagate_constants_topo (topo
);
3354 ipcp_verify_propagated_values ();
3355 topo
->constants
.propagate_effects ();
3356 topo
->contexts
.propagate_effects ();
3360 fprintf (dump_file
, "\nIPA lattices after all propagation:\n");
3361 print_all_lattices (dump_file
, (dump_flags
& TDF_DETAILS
), true);
3365 /* Discover newly direct outgoing edges from NODE which is a new clone with
3366 known KNOWN_CSTS and make them direct. */
3369 ipcp_discover_new_direct_edges (struct cgraph_node
*node
,
3370 vec
<tree
> known_csts
,
3371 vec
<ipa_polymorphic_call_context
>
3373 struct ipa_agg_replacement_value
*aggvals
)
3375 struct cgraph_edge
*ie
, *next_ie
;
3378 for (ie
= node
->indirect_calls
; ie
; ie
= next_ie
)
3383 next_ie
= ie
->next_callee
;
3384 target
= ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
3385 vNULL
, aggvals
, &speculative
);
3388 bool agg_contents
= ie
->indirect_info
->agg_contents
;
3389 bool polymorphic
= ie
->indirect_info
->polymorphic
;
3390 int param_index
= ie
->indirect_info
->param_index
;
3391 struct cgraph_edge
*cs
= ipa_make_edge_direct_to_target (ie
, target
,
3395 if (cs
&& !agg_contents
&& !polymorphic
)
3397 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3398 int c
= ipa_get_controlled_uses (info
, param_index
);
3399 if (c
!= IPA_UNDESCRIBED_USE
)
3401 struct ipa_ref
*to_del
;
3404 ipa_set_controlled_uses (info
, param_index
, c
);
3405 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3406 fprintf (dump_file
, " controlled uses count of param "
3407 "%i bumped down to %i\n", param_index
, c
);
3409 && (to_del
= node
->find_reference (cs
->callee
, NULL
, 0)))
3411 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3412 fprintf (dump_file
, " and even removing its "
3413 "cloning-created reference\n");
3414 to_del
->remove_reference ();
3420 /* Turning calls to direct calls will improve overall summary. */
3422 ipa_update_overall_fn_summary (node
);
3425 class edge_clone_summary
;
3426 static call_summary
<edge_clone_summary
*> *edge_clone_summaries
= NULL
;
3428 /* Edge clone summary. */
3430 class edge_clone_summary
3433 /* Default constructor. */
3434 edge_clone_summary (): prev_clone (NULL
), next_clone (NULL
) {}
3436 /* Default destructor. */
3437 ~edge_clone_summary ()
3440 edge_clone_summaries
->get (prev_clone
)->next_clone
= next_clone
;
3442 edge_clone_summaries
->get (next_clone
)->prev_clone
= prev_clone
;
3445 cgraph_edge
*prev_clone
;
3446 cgraph_edge
*next_clone
;
3449 class edge_clone_summary_t
:
3450 public call_summary
<edge_clone_summary
*>
3453 edge_clone_summary_t (symbol_table
*symtab
):
3454 call_summary
<edge_clone_summary
*> (symtab
)
3456 m_initialize_when_cloning
= true;
3459 virtual void duplicate (cgraph_edge
*src_edge
, cgraph_edge
*dst_edge
,
3460 edge_clone_summary
*src_data
,
3461 edge_clone_summary
*dst_data
);
3464 /* Edge duplication hook. */
3467 edge_clone_summary_t::duplicate (cgraph_edge
*src_edge
, cgraph_edge
*dst_edge
,
3468 edge_clone_summary
*src_data
,
3469 edge_clone_summary
*dst_data
)
3471 if (src_data
->next_clone
)
3472 edge_clone_summaries
->get (src_data
->next_clone
)->prev_clone
= dst_edge
;
3473 dst_data
->prev_clone
= src_edge
;
3474 dst_data
->next_clone
= src_data
->next_clone
;
3475 src_data
->next_clone
= dst_edge
;
3478 /* See if NODE is a clone with a known aggregate value at a given OFFSET of a
3479 parameter with the given INDEX. */
3482 get_clone_agg_value (struct cgraph_node
*node
, HOST_WIDE_INT offset
,
3485 struct ipa_agg_replacement_value
*aggval
;
3487 aggval
= ipa_get_agg_replacements_for_node (node
);
3490 if (aggval
->offset
== offset
3491 && aggval
->index
== index
)
3492 return aggval
->value
;
3493 aggval
= aggval
->next
;
3498 /* Return true is NODE is DEST or its clone for all contexts. */
3501 same_node_or_its_all_contexts_clone_p (cgraph_node
*node
, cgraph_node
*dest
)
3506 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3507 return info
->is_all_contexts_clone
&& info
->ipcp_orig_node
== dest
;
3510 /* Return true if edge CS does bring about the value described by SRC to
3511 DEST_VAL of node DEST or its clone for all contexts. */
3514 cgraph_edge_brings_value_p (cgraph_edge
*cs
, ipcp_value_source
<tree
> *src
,
3515 cgraph_node
*dest
, ipcp_value
<tree
> *dest_val
)
3517 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3518 enum availability availability
;
3519 cgraph_node
*real_dest
= cs
->callee
->function_symbol (&availability
);
3521 if (!same_node_or_its_all_contexts_clone_p (real_dest
, dest
)
3522 || availability
<= AVAIL_INTERPOSABLE
3523 || caller_info
->node_dead
)
3529 if (caller_info
->ipcp_orig_node
)
3532 if (src
->offset
== -1)
3533 t
= caller_info
->known_csts
[src
->index
];
3535 t
= get_clone_agg_value (cs
->caller
, src
->offset
, src
->index
);
3536 return (t
!= NULL_TREE
3537 && values_equal_for_ipcp_p (src
->val
->value
, t
));
3541 /* At the moment we do not propagate over arithmetic jump functions in
3542 SCCs, so it is safe to detect self-feeding recursive calls in this
3544 if (src
->val
== dest_val
)
3547 struct ipcp_agg_lattice
*aglat
;
3548 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
3550 if (src
->offset
== -1)
3551 return (plats
->itself
.is_single_const ()
3552 && values_equal_for_ipcp_p (src
->val
->value
,
3553 plats
->itself
.values
->value
));
3556 if (plats
->aggs_bottom
|| plats
->aggs_contain_variable
)
3558 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3559 if (aglat
->offset
== src
->offset
)
3560 return (aglat
->is_single_const ()
3561 && values_equal_for_ipcp_p (src
->val
->value
,
3562 aglat
->values
->value
));
3568 /* Return true if edge CS does bring about the value described by SRC to
3569 DST_VAL of node DEST or its clone for all contexts. */
3572 cgraph_edge_brings_value_p (cgraph_edge
*cs
,
3573 ipcp_value_source
<ipa_polymorphic_call_context
> *src
,
3575 ipcp_value
<ipa_polymorphic_call_context
> *)
3577 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3578 cgraph_node
*real_dest
= cs
->callee
->function_symbol ();
3580 if (!same_node_or_its_all_contexts_clone_p (real_dest
, dest
)
3581 || caller_info
->node_dead
)
3586 if (caller_info
->ipcp_orig_node
)
3587 return (caller_info
->known_contexts
.length () > (unsigned) src
->index
)
3588 && values_equal_for_ipcp_p (src
->val
->value
,
3589 caller_info
->known_contexts
[src
->index
]);
3591 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
3593 return plats
->ctxlat
.is_single_const ()
3594 && values_equal_for_ipcp_p (src
->val
->value
,
3595 plats
->ctxlat
.values
->value
);
3598 /* Get the next clone in the linked list of clones of an edge. */
3600 static inline struct cgraph_edge
*
3601 get_next_cgraph_edge_clone (struct cgraph_edge
*cs
)
3603 edge_clone_summary
*s
= edge_clone_summaries
->get (cs
);
3604 return s
!= NULL
? s
->next_clone
: NULL
;
3607 /* Given VAL that is intended for DEST, iterate over all its sources and if any
3608 of them is viable and hot, return true. In that case, for those that still
3609 hold, add their edge frequency and their number into *FREQUENCY and
3610 *CALLER_COUNT respectively. */
3612 template <typename valtype
>
3614 get_info_about_necessary_edges (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
3616 profile_count
*count_sum
, int *caller_count
)
3618 ipcp_value_source
<valtype
> *src
;
3619 int freq
= 0, count
= 0;
3620 profile_count cnt
= profile_count::zero ();
3622 bool non_self_recursive
= false;
3624 for (src
= val
->sources
; src
; src
= src
->next
)
3626 struct cgraph_edge
*cs
= src
->cs
;
3629 if (cgraph_edge_brings_value_p (cs
, src
, dest
, val
))
3632 freq
+= cs
->frequency ();
3633 if (cs
->count
.ipa ().initialized_p ())
3634 cnt
+= cs
->count
.ipa ();
3635 hot
|= cs
->maybe_hot_p ();
3636 if (cs
->caller
!= dest
)
3637 non_self_recursive
= true;
3639 cs
= get_next_cgraph_edge_clone (cs
);
3643 /* If the only edges bringing a value are self-recursive ones, do not bother
3645 if (!non_self_recursive
)
3650 *caller_count
= count
;
3654 /* Return a vector of incoming edges that do bring value VAL to node DEST. It
3655 is assumed their number is known and equal to CALLER_COUNT. */
3657 template <typename valtype
>
3658 static vec
<cgraph_edge
*>
3659 gather_edges_for_value (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
3662 ipcp_value_source
<valtype
> *src
;
3663 vec
<cgraph_edge
*> ret
;
3665 ret
.create (caller_count
);
3666 for (src
= val
->sources
; src
; src
= src
->next
)
3668 struct cgraph_edge
*cs
= src
->cs
;
3671 if (cgraph_edge_brings_value_p (cs
, src
, dest
, val
))
3672 ret
.quick_push (cs
);
3673 cs
= get_next_cgraph_edge_clone (cs
);
3680 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
3681 Return it or NULL if for some reason it cannot be created. */
3683 static struct ipa_replace_map
*
3684 get_replacement_map (class ipa_node_params
*info
, tree value
, int parm_num
)
3686 struct ipa_replace_map
*replace_map
;
3689 replace_map
= ggc_alloc
<ipa_replace_map
> ();
3692 fprintf (dump_file
, " replacing ");
3693 ipa_dump_param (dump_file
, info
, parm_num
);
3695 fprintf (dump_file
, " with const ");
3696 print_generic_expr (dump_file
, value
);
3697 fprintf (dump_file
, "\n");
3699 replace_map
->parm_num
= parm_num
;
3700 replace_map
->new_tree
= value
;
3704 /* Dump new profiling counts */
3707 dump_profile_updates (struct cgraph_node
*orig_node
,
3708 struct cgraph_node
*new_node
)
3710 struct cgraph_edge
*cs
;
3712 fprintf (dump_file
, " setting count of the specialized node to ");
3713 new_node
->count
.dump (dump_file
);
3714 fprintf (dump_file
, "\n");
3715 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3717 fprintf (dump_file
, " edge to %s has count ",
3718 cs
->callee
->name ());
3719 cs
->count
.dump (dump_file
);
3720 fprintf (dump_file
, "\n");
3723 fprintf (dump_file
, " setting count of the original node to ");
3724 orig_node
->count
.dump (dump_file
);
3725 fprintf (dump_file
, "\n");
3726 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3728 fprintf (dump_file
, " edge to %s is left with ",
3729 cs
->callee
->name ());
3730 cs
->count
.dump (dump_file
);
3731 fprintf (dump_file
, "\n");
3735 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
3736 their profile information to reflect this. */
3739 update_profiling_info (struct cgraph_node
*orig_node
,
3740 struct cgraph_node
*new_node
)
3742 struct cgraph_edge
*cs
;
3743 struct caller_statistics stats
;
3744 profile_count new_sum
, orig_sum
;
3745 profile_count remainder
, orig_node_count
= orig_node
->count
;
3747 if (!(orig_node_count
.ipa () > profile_count::zero ()))
3750 init_caller_stats (&stats
);
3751 orig_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
3753 orig_sum
= stats
.count_sum
;
3754 init_caller_stats (&stats
);
3755 new_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
3757 new_sum
= stats
.count_sum
;
3759 if (orig_node_count
< orig_sum
+ new_sum
)
3763 fprintf (dump_file
, " Problem: node %s has too low count ",
3764 orig_node
->dump_name ());
3765 orig_node_count
.dump (dump_file
);
3766 fprintf (dump_file
, "while the sum of incoming count is ");
3767 (orig_sum
+ new_sum
).dump (dump_file
);
3768 fprintf (dump_file
, "\n");
3771 orig_node_count
= (orig_sum
+ new_sum
).apply_scale (12, 10);
3774 fprintf (dump_file
, " proceeding by pretending it was ");
3775 orig_node_count
.dump (dump_file
);
3776 fprintf (dump_file
, "\n");
3780 remainder
= orig_node_count
.combine_with_ipa_count (orig_node_count
.ipa ()
3782 new_sum
= orig_node_count
.combine_with_ipa_count (new_sum
);
3783 orig_node
->count
= remainder
;
3785 profile_count::adjust_for_ipa_scaling (&new_sum
, &orig_node_count
);
3786 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3787 cs
->count
= cs
->count
.apply_scale (new_sum
, orig_node_count
);
3789 profile_count::adjust_for_ipa_scaling (&remainder
, &orig_node_count
);
3790 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3791 cs
->count
= cs
->count
.apply_scale (remainder
, orig_node_count
);
3794 dump_profile_updates (orig_node
, new_node
);
3797 /* Update the respective profile of specialized NEW_NODE and the original
3798 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
3799 have been redirected to the specialized version. */
3802 update_specialized_profile (struct cgraph_node
*new_node
,
3803 struct cgraph_node
*orig_node
,
3804 profile_count redirected_sum
)
3806 struct cgraph_edge
*cs
;
3807 profile_count new_node_count
, orig_node_count
= orig_node
->count
;
3811 fprintf (dump_file
, " the sum of counts of redirected edges is ");
3812 redirected_sum
.dump (dump_file
);
3813 fprintf (dump_file
, "\n");
3815 if (!(orig_node_count
> profile_count::zero ()))
3818 gcc_assert (orig_node_count
>= redirected_sum
);
3820 new_node_count
= new_node
->count
;
3821 new_node
->count
+= redirected_sum
;
3822 orig_node
->count
-= redirected_sum
;
3824 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3825 cs
->count
+= cs
->count
.apply_scale (redirected_sum
, new_node_count
);
3827 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3829 profile_count dec
= cs
->count
.apply_scale (redirected_sum
,
3835 dump_profile_updates (orig_node
, new_node
);
3838 /* Return true if we would like to remove a parameter from NODE when cloning it
3839 with KNOWN_CSTS scalar constants. */
3842 want_remove_some_param_p (cgraph_node
*node
, vec
<tree
> known_csts
)
3844 auto_vec
<bool, 16> surviving
;
3845 bool filled_vec
= false;
3846 ipa_node_params
*info
= IPA_NODE_REF (node
);
3847 int i
, count
= ipa_get_param_count (info
);
3849 for (i
= 0; i
< count
; i
++)
3851 if (!known_csts
[i
] && ipa_is_param_used (info
, i
))
3856 if (!node
->clone
.param_adjustments
)
3858 node
->clone
.param_adjustments
->get_surviving_params (&surviving
);
3861 if (surviving
.length() < (unsigned) i
&& surviving
[i
])
3867 /* Create a specialized version of NODE with known constants in KNOWN_CSTS,
3868 known contexts in KNOWN_CONTEXTS and known aggregate values in AGGVALS and
3869 redirect all edges in CALLERS to it. */
3871 static struct cgraph_node
*
3872 create_specialized_node (struct cgraph_node
*node
,
3873 vec
<tree
> known_csts
,
3874 vec
<ipa_polymorphic_call_context
> known_contexts
,
3875 struct ipa_agg_replacement_value
*aggvals
,
3876 vec
<cgraph_edge
*> callers
)
3878 class ipa_node_params
*new_info
, *info
= IPA_NODE_REF (node
);
3879 vec
<ipa_replace_map
*, va_gc
> *replace_trees
= NULL
;
3880 vec
<ipa_adjusted_param
, va_gc
> *new_params
= NULL
;
3881 struct ipa_agg_replacement_value
*av
;
3882 struct cgraph_node
*new_node
;
3883 int i
, count
= ipa_get_param_count (info
);
3884 ipa_param_adjustments
*old_adjustments
= node
->clone
.param_adjustments
;
3885 ipa_param_adjustments
*new_adjustments
;
3886 gcc_assert (!info
->ipcp_orig_node
);
3887 gcc_assert (node
->local
.can_change_signature
3888 || !old_adjustments
);
3890 if (old_adjustments
)
3892 /* At the moment all IPA optimizations should use the number of
3893 parameters of the prevailing decl as the m_always_copy_start.
3894 Handling any other value would complicate the code below, so for the
3895 time bing let's only assert it is so. */
3896 gcc_assert (old_adjustments
->m_always_copy_start
== count
3897 || old_adjustments
->m_always_copy_start
< 0);
3898 int old_adj_count
= vec_safe_length (old_adjustments
->m_adj_params
);
3899 for (i
= 0; i
< old_adj_count
; i
++)
3901 ipa_adjusted_param
*old_adj
= &(*old_adjustments
->m_adj_params
)[i
];
3902 if (!node
->local
.can_change_signature
3903 || old_adj
->op
!= IPA_PARAM_OP_COPY
3904 || (!known_csts
[old_adj
->base_index
]
3905 && ipa_is_param_used (info
, old_adj
->base_index
)))
3907 ipa_adjusted_param new_adj
= *old_adj
;
3909 new_adj
.prev_clone_adjustment
= true;
3910 new_adj
.prev_clone_index
= i
;
3911 vec_safe_push (new_params
, new_adj
);
3914 bool skip_return
= old_adjustments
->m_skip_return
;
3915 new_adjustments
= (new (ggc_alloc
<ipa_param_adjustments
> ())
3916 ipa_param_adjustments (new_params
, count
,
3919 else if (node
->local
.can_change_signature
3920 && want_remove_some_param_p (node
, known_csts
))
3922 ipa_adjusted_param adj
;
3923 memset (&adj
, 0, sizeof (adj
));
3924 adj
.op
= IPA_PARAM_OP_COPY
;
3925 for (i
= 0; i
< count
; i
++)
3926 if (!known_csts
[i
] && ipa_is_param_used (info
, i
))
3929 adj
.prev_clone_index
= i
;
3930 vec_safe_push (new_params
, adj
);
3932 new_adjustments
= (new (ggc_alloc
<ipa_param_adjustments
> ())
3933 ipa_param_adjustments (new_params
, count
, false));
3936 new_adjustments
= NULL
;
3938 replace_trees
= vec_safe_copy (node
->clone
.tree_map
);
3939 for (i
= 0; i
< count
; i
++)
3941 tree t
= known_csts
[i
];
3944 struct ipa_replace_map
*replace_map
;
3946 gcc_checking_assert (TREE_CODE (t
) != TREE_BINFO
);
3947 replace_map
= get_replacement_map (info
, t
, i
);
3949 vec_safe_push (replace_trees
, replace_map
);
3952 auto_vec
<cgraph_edge
*, 2> self_recursive_calls
;
3953 for (i
= callers
.length () - 1; i
>= 0; i
--)
3955 cgraph_edge
*cs
= callers
[i
];
3956 if (cs
->caller
== node
)
3958 self_recursive_calls
.safe_push (cs
);
3959 callers
.unordered_remove (i
);
3963 unsigned &suffix_counter
= clone_num_suffixes
->get_or_insert (
3964 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (
3966 new_node
= node
->create_virtual_clone (callers
, replace_trees
,
3967 new_adjustments
, "constprop",
3971 bool have_self_recursive_calls
= !self_recursive_calls
.is_empty ();
3972 for (unsigned j
= 0; j
< self_recursive_calls
.length (); j
++)
3974 cgraph_edge
*cs
= get_next_cgraph_edge_clone (self_recursive_calls
[j
]);
3975 /* Cloned edges can disappear during cloning as speculation can be
3976 resolved, check that we have one and that it comes from the last
3978 if (cs
&& cs
->caller
== new_node
)
3979 cs
->redirect_callee_duplicating_thunks (new_node
);
3980 /* Any future code that would make more than one clone of an outgoing
3981 edge would confuse this mechanism, so let's check that does not
3983 gcc_checking_assert (!cs
3984 || !get_next_cgraph_edge_clone (cs
)
3985 || get_next_cgraph_edge_clone (cs
)->caller
!= new_node
);
3987 if (have_self_recursive_calls
)
3988 new_node
->expand_all_artificial_thunks ();
3990 ipa_set_node_agg_value_chain (new_node
, aggvals
);
3991 for (av
= aggvals
; av
; av
= av
->next
)
3992 new_node
->maybe_create_reference (av
->value
, NULL
);
3994 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3996 fprintf (dump_file
, " the new node is %s.\n", new_node
->dump_name ());
3997 if (known_contexts
.exists ())
3999 for (i
= 0; i
< count
; i
++)
4000 if (!known_contexts
[i
].useless_p ())
4002 fprintf (dump_file
, " known ctx %i is ", i
);
4003 known_contexts
[i
].dump (dump_file
);
4007 ipa_dump_agg_replacement_values (dump_file
, aggvals
);
4009 ipa_check_create_node_params ();
4010 update_profiling_info (node
, new_node
);
4011 new_info
= IPA_NODE_REF (new_node
);
4012 new_info
->ipcp_orig_node
= node
;
4013 new_info
->known_csts
= known_csts
;
4014 new_info
->known_contexts
= known_contexts
;
4016 ipcp_discover_new_direct_edges (new_node
, known_csts
, known_contexts
, aggvals
);
4022 /* Return true, if JFUNC, which describes a i-th parameter of call CS, is a
4023 simple no-operation pass-through function to itself. */
4026 self_recursive_pass_through_p (cgraph_edge
*cs
, ipa_jump_func
*jfunc
, int i
)
4028 enum availability availability
;
4029 if (cs
->caller
== cs
->callee
->function_symbol (&availability
)
4030 && availability
> AVAIL_INTERPOSABLE
4031 && jfunc
->type
== IPA_JF_PASS_THROUGH
4032 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
4033 && ipa_get_jf_pass_through_formal_id (jfunc
) == i
)
4038 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
4039 KNOWN_CSTS with constants that are also known for all of the CALLERS. */
4042 find_more_scalar_values_for_callers_subset (struct cgraph_node
*node
,
4043 vec
<tree
> known_csts
,
4044 vec
<cgraph_edge
*> callers
)
4046 class ipa_node_params
*info
= IPA_NODE_REF (node
);
4047 int i
, count
= ipa_get_param_count (info
);
4049 for (i
= 0; i
< count
; i
++)
4051 struct cgraph_edge
*cs
;
4052 tree newval
= NULL_TREE
;
4055 tree type
= ipa_get_type (info
, i
);
4057 if (ipa_get_scalar_lat (info
, i
)->bottom
|| known_csts
[i
])
4060 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4062 struct ipa_jump_func
*jump_func
;
4065 if (IPA_NODE_REF (cs
->caller
)->node_dead
)
4068 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
))
4070 && call_passes_through_thunk_p (cs
)))
4075 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
4076 if (self_recursive_pass_through_p (cs
, jump_func
, i
))
4079 t
= ipa_value_from_jfunc (IPA_NODE_REF (cs
->caller
), jump_func
, type
);
4082 && !values_equal_for_ipcp_p (t
, newval
))
4083 || (!first
&& !newval
))
4095 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4097 fprintf (dump_file
, " adding an extra known scalar value ");
4098 print_ipcp_constant_value (dump_file
, newval
);
4099 fprintf (dump_file
, " for ");
4100 ipa_dump_param (dump_file
, info
, i
);
4101 fprintf (dump_file
, "\n");
4104 known_csts
[i
] = newval
;
4109 /* Given a NODE and a subset of its CALLERS, try to populate plank slots in
4110 KNOWN_CONTEXTS with polymorphic contexts that are also known for all of the
4114 find_more_contexts_for_caller_subset (cgraph_node
*node
,
4115 vec
<ipa_polymorphic_call_context
>
4117 vec
<cgraph_edge
*> callers
)
4119 ipa_node_params
*info
= IPA_NODE_REF (node
);
4120 int i
, count
= ipa_get_param_count (info
);
4122 for (i
= 0; i
< count
; i
++)
4126 if (ipa_get_poly_ctx_lat (info
, i
)->bottom
4127 || (known_contexts
->exists ()
4128 && !(*known_contexts
)[i
].useless_p ()))
4131 ipa_polymorphic_call_context newval
;
4135 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4137 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
)))
4139 ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
),
4141 ipa_polymorphic_call_context ctx
;
4142 ctx
= ipa_context_from_jfunc (IPA_NODE_REF (cs
->caller
), cs
, i
,
4150 newval
.meet_with (ctx
);
4151 if (newval
.useless_p ())
4155 if (!newval
.useless_p ())
4157 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4159 fprintf (dump_file
, " adding an extra known polymorphic "
4161 print_ipcp_constant_value (dump_file
, newval
);
4162 fprintf (dump_file
, " for ");
4163 ipa_dump_param (dump_file
, info
, i
);
4164 fprintf (dump_file
, "\n");
4167 if (!known_contexts
->exists ())
4168 known_contexts
->safe_grow_cleared (ipa_get_param_count (info
));
4169 (*known_contexts
)[i
] = newval
;
4175 /* Go through PLATS and create a vector of values consisting of values and
4176 offsets (minus OFFSET) of lattices that contain only a single value. */
4178 static vec
<ipa_agg_jf_item
>
4179 copy_plats_to_inter (class ipcp_param_lattices
*plats
, HOST_WIDE_INT offset
)
4181 vec
<ipa_agg_jf_item
> res
= vNULL
;
4183 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
4186 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
4187 if (aglat
->is_single_const ())
4189 struct ipa_agg_jf_item ti
;
4190 ti
.offset
= aglat
->offset
- offset
;
4191 ti
.value
= aglat
->values
->value
;
4197 /* Intersect all values in INTER with single value lattices in PLATS (while
4198 subtracting OFFSET). */
4201 intersect_with_plats (class ipcp_param_lattices
*plats
,
4202 vec
<ipa_agg_jf_item
> *inter
,
4203 HOST_WIDE_INT offset
)
4205 struct ipcp_agg_lattice
*aglat
;
4206 struct ipa_agg_jf_item
*item
;
4209 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
4215 aglat
= plats
->aggs
;
4216 FOR_EACH_VEC_ELT (*inter
, k
, item
)
4223 if (aglat
->offset
- offset
> item
->offset
)
4225 if (aglat
->offset
- offset
== item
->offset
)
4227 gcc_checking_assert (item
->value
);
4228 if (aglat
->is_single_const ()
4229 && values_equal_for_ipcp_p (item
->value
,
4230 aglat
->values
->value
))
4234 aglat
= aglat
->next
;
4237 item
->value
= NULL_TREE
;
4241 /* Copy aggregate replacement values of NODE (which is an IPA-CP clone) to the
4242 vector result while subtracting OFFSET from the individual value offsets. */
4244 static vec
<ipa_agg_jf_item
>
4245 agg_replacements_to_vector (struct cgraph_node
*node
, int index
,
4246 HOST_WIDE_INT offset
)
4248 struct ipa_agg_replacement_value
*av
;
4249 vec
<ipa_agg_jf_item
> res
= vNULL
;
4251 for (av
= ipa_get_agg_replacements_for_node (node
); av
; av
= av
->next
)
4252 if (av
->index
== index
4253 && (av
->offset
- offset
) >= 0)
4255 struct ipa_agg_jf_item item
;
4256 gcc_checking_assert (av
->value
);
4257 item
.offset
= av
->offset
- offset
;
4258 item
.value
= av
->value
;
4259 res
.safe_push (item
);
4265 /* Intersect all values in INTER with those that we have already scheduled to
4266 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
4267 (while subtracting OFFSET). */
4270 intersect_with_agg_replacements (struct cgraph_node
*node
, int index
,
4271 vec
<ipa_agg_jf_item
> *inter
,
4272 HOST_WIDE_INT offset
)
4274 struct ipa_agg_replacement_value
*srcvals
;
4275 struct ipa_agg_jf_item
*item
;
4278 srcvals
= ipa_get_agg_replacements_for_node (node
);
4285 FOR_EACH_VEC_ELT (*inter
, i
, item
)
4287 struct ipa_agg_replacement_value
*av
;
4291 for (av
= srcvals
; av
; av
= av
->next
)
4293 gcc_checking_assert (av
->value
);
4294 if (av
->index
== index
4295 && av
->offset
- offset
== item
->offset
)
4297 if (values_equal_for_ipcp_p (item
->value
, av
->value
))
4303 item
->value
= NULL_TREE
;
4307 /* Intersect values in INTER with aggregate values that come along edge CS to
4308 parameter number INDEX and return it. If INTER does not actually exist yet,
4309 copy all incoming values to it. If we determine we ended up with no values
4310 whatsoever, return a released vector. */
4312 static vec
<ipa_agg_jf_item
>
4313 intersect_aggregates_with_edge (struct cgraph_edge
*cs
, int index
,
4314 vec
<ipa_agg_jf_item
> inter
)
4316 struct ipa_jump_func
*jfunc
;
4317 jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), index
);
4318 if (jfunc
->type
== IPA_JF_PASS_THROUGH
4319 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
4321 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4322 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
4324 if (caller_info
->ipcp_orig_node
)
4326 struct cgraph_node
*orig_node
= caller_info
->ipcp_orig_node
;
4327 class ipcp_param_lattices
*orig_plats
;
4328 orig_plats
= ipa_get_parm_lattices (IPA_NODE_REF (orig_node
),
4330 if (agg_pass_through_permissible_p (orig_plats
, jfunc
))
4332 if (!inter
.exists ())
4333 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, 0);
4335 intersect_with_agg_replacements (cs
->caller
, src_idx
,
4346 class ipcp_param_lattices
*src_plats
;
4347 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
4348 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
4350 /* Currently we do not produce clobber aggregate jump
4351 functions, adjust when we do. */
4352 gcc_checking_assert (!jfunc
->agg
.items
);
4353 if (!inter
.exists ())
4354 inter
= copy_plats_to_inter (src_plats
, 0);
4356 intersect_with_plats (src_plats
, &inter
, 0);
4365 else if (jfunc
->type
== IPA_JF_ANCESTOR
4366 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
4368 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4369 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
4370 class ipcp_param_lattices
*src_plats
;
4371 HOST_WIDE_INT delta
= ipa_get_jf_ancestor_offset (jfunc
);
4373 if (caller_info
->ipcp_orig_node
)
4375 if (!inter
.exists ())
4376 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, delta
);
4378 intersect_with_agg_replacements (cs
->caller
, src_idx
, &inter
,
4383 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
4384 /* Currently we do not produce clobber aggregate jump
4385 functions, adjust when we do. */
4386 gcc_checking_assert (!src_plats
->aggs
|| !jfunc
->agg
.items
);
4387 if (!inter
.exists ())
4388 inter
= copy_plats_to_inter (src_plats
, delta
);
4390 intersect_with_plats (src_plats
, &inter
, delta
);
4393 else if (jfunc
->agg
.items
)
4395 struct ipa_agg_jf_item
*item
;
4398 if (!inter
.exists ())
4399 for (unsigned i
= 0; i
< jfunc
->agg
.items
->length (); i
++)
4400 inter
.safe_push ((*jfunc
->agg
.items
)[i
]);
4402 FOR_EACH_VEC_ELT (inter
, k
, item
)
4410 while ((unsigned) l
< jfunc
->agg
.items
->length ())
4412 struct ipa_agg_jf_item
*ti
;
4413 ti
= &(*jfunc
->agg
.items
)[l
];
4414 if (ti
->offset
> item
->offset
)
4416 if (ti
->offset
== item
->offset
)
4418 gcc_checking_assert (ti
->value
);
4419 if (values_equal_for_ipcp_p (item
->value
,
4433 return vec
<ipa_agg_jf_item
>();
4438 /* Look at edges in CALLERS and collect all known aggregate values that arrive
4439 from all of them. */
4441 static struct ipa_agg_replacement_value
*
4442 find_aggregate_values_for_callers_subset (struct cgraph_node
*node
,
4443 vec
<cgraph_edge
*> callers
)
4445 class ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
4446 struct ipa_agg_replacement_value
*res
;
4447 struct ipa_agg_replacement_value
**tail
= &res
;
4448 struct cgraph_edge
*cs
;
4449 int i
, j
, count
= ipa_get_param_count (dest_info
);
4451 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4453 int c
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
4458 for (i
= 0; i
< count
; i
++)
4460 struct cgraph_edge
*cs
;
4461 vec
<ipa_agg_jf_item
> inter
= vNULL
;
4462 struct ipa_agg_jf_item
*item
;
4463 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (dest_info
, i
);
4466 /* Among other things, the following check should deal with all by_ref
4468 if (plats
->aggs_bottom
)
4471 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4473 struct ipa_jump_func
*jfunc
4474 = ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
4475 if (self_recursive_pass_through_p (cs
, jfunc
, i
)
4476 && (!plats
->aggs_by_ref
4477 || ipa_get_jf_pass_through_agg_preserved (jfunc
)))
4479 inter
= intersect_aggregates_with_edge (cs
, i
, inter
);
4481 if (!inter
.exists ())
4485 FOR_EACH_VEC_ELT (inter
, j
, item
)
4487 struct ipa_agg_replacement_value
*v
;
4492 v
= ggc_alloc
<ipa_agg_replacement_value
> ();
4494 v
->offset
= item
->offset
;
4495 v
->value
= item
->value
;
4496 v
->by_ref
= plats
->aggs_by_ref
;
4502 if (inter
.exists ())
4509 /* Determine whether CS also brings all scalar values that the NODE is
4513 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge
*cs
,
4514 struct cgraph_node
*node
)
4516 class ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
4517 int count
= ipa_get_param_count (dest_info
);
4518 class ipa_node_params
*caller_info
;
4519 class ipa_edge_args
*args
;
4522 caller_info
= IPA_NODE_REF (cs
->caller
);
4523 args
= IPA_EDGE_REF (cs
);
4524 for (i
= 0; i
< count
; i
++)
4526 struct ipa_jump_func
*jump_func
;
4529 val
= dest_info
->known_csts
[i
];
4533 if (i
>= ipa_get_cs_argument_count (args
))
4535 jump_func
= ipa_get_ith_jump_func (args
, i
);
4536 t
= ipa_value_from_jfunc (caller_info
, jump_func
,
4537 ipa_get_type (dest_info
, i
));
4538 if (!t
|| !values_equal_for_ipcp_p (val
, t
))
4544 /* Determine whether CS also brings all aggregate values that NODE is
4547 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge
*cs
,
4548 struct cgraph_node
*node
)
4550 class ipa_node_params
*orig_node_info
;
4551 struct ipa_agg_replacement_value
*aggval
;
4554 aggval
= ipa_get_agg_replacements_for_node (node
);
4558 count
= ipa_get_param_count (IPA_NODE_REF (node
));
4559 ec
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
4561 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4562 if (aggval
->index
>= ec
)
4565 orig_node_info
= IPA_NODE_REF (IPA_NODE_REF (node
)->ipcp_orig_node
);
4567 for (i
= 0; i
< count
; i
++)
4569 static vec
<ipa_agg_jf_item
> values
= vec
<ipa_agg_jf_item
>();
4570 class ipcp_param_lattices
*plats
;
4571 bool interesting
= false;
4572 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4573 if (aggval
->index
== i
)
4581 plats
= ipa_get_parm_lattices (orig_node_info
, aggval
->index
);
4582 if (plats
->aggs_bottom
)
4585 values
= intersect_aggregates_with_edge (cs
, i
, values
);
4586 if (!values
.exists ())
4589 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4590 if (aggval
->index
== i
)
4592 struct ipa_agg_jf_item
*item
;
4595 FOR_EACH_VEC_ELT (values
, j
, item
)
4597 && item
->offset
== av
->offset
4598 && values_equal_for_ipcp_p (item
->value
, av
->value
))
4613 /* Given an original NODE and a VAL for which we have already created a
4614 specialized clone, look whether there are incoming edges that still lead
4615 into the old node but now also bring the requested value and also conform to
4616 all other criteria such that they can be redirected the special node.
4617 This function can therefore redirect the final edge in a SCC. */
4619 template <typename valtype
>
4621 perhaps_add_new_callers (cgraph_node
*node
, ipcp_value
<valtype
> *val
)
4623 ipcp_value_source
<valtype
> *src
;
4624 profile_count redirected_sum
= profile_count::zero ();
4626 for (src
= val
->sources
; src
; src
= src
->next
)
4628 struct cgraph_edge
*cs
= src
->cs
;
4631 if (cgraph_edge_brings_value_p (cs
, src
, node
, val
)
4632 && cgraph_edge_brings_all_scalars_for_node (cs
, val
->spec_node
)
4633 && cgraph_edge_brings_all_agg_vals_for_node (cs
, val
->spec_node
))
4636 fprintf (dump_file
, " - adding an extra caller %s of %s\n",
4637 cs
->caller
->dump_name (),
4638 val
->spec_node
->dump_name ());
4640 cs
->redirect_callee_duplicating_thunks (val
->spec_node
);
4641 val
->spec_node
->expand_all_artificial_thunks ();
4642 if (cs
->count
.ipa ().initialized_p ())
4643 redirected_sum
= redirected_sum
+ cs
->count
.ipa ();
4645 cs
= get_next_cgraph_edge_clone (cs
);
4649 if (redirected_sum
.nonzero_p ())
4650 update_specialized_profile (val
->spec_node
, node
, redirected_sum
);
4653 /* Return true if KNOWN_CONTEXTS contain at least one useful context. */
4656 known_contexts_useful_p (vec
<ipa_polymorphic_call_context
> known_contexts
)
4658 ipa_polymorphic_call_context
*ctx
;
4661 FOR_EACH_VEC_ELT (known_contexts
, i
, ctx
)
4662 if (!ctx
->useless_p ())
4667 /* Return a copy of KNOWN_CSTS if it is not empty, otherwise return vNULL. */
4669 static vec
<ipa_polymorphic_call_context
>
4670 copy_useful_known_contexts (vec
<ipa_polymorphic_call_context
> known_contexts
)
4672 if (known_contexts_useful_p (known_contexts
))
4673 return known_contexts
.copy ();
4678 /* Copy KNOWN_CSTS and modify the copy according to VAL and INDEX. If
4679 non-empty, replace KNOWN_CONTEXTS with its copy too. */
4682 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
4683 vec
<ipa_polymorphic_call_context
> *known_contexts
,
4684 ipcp_value
<tree
> *val
,
4687 *known_csts
= known_csts
->copy ();
4688 *known_contexts
= copy_useful_known_contexts (*known_contexts
);
4689 (*known_csts
)[index
] = val
->value
;
4692 /* Replace KNOWN_CSTS with its copy. Also copy KNOWN_CONTEXTS and modify the
4693 copy according to VAL and INDEX. */
4696 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
4697 vec
<ipa_polymorphic_call_context
> *known_contexts
,
4698 ipcp_value
<ipa_polymorphic_call_context
> *val
,
4701 *known_csts
= known_csts
->copy ();
4702 *known_contexts
= known_contexts
->copy ();
4703 (*known_contexts
)[index
] = val
->value
;
4706 /* Return true if OFFSET indicates this was not an aggregate value or there is
4707 a replacement equivalent to VALUE, INDEX and OFFSET among those in the
4711 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*aggvals
,
4712 int index
, HOST_WIDE_INT offset
, tree value
)
4719 if (aggvals
->index
== index
4720 && aggvals
->offset
== offset
4721 && values_equal_for_ipcp_p (aggvals
->value
, value
))
4723 aggvals
= aggvals
->next
;
4728 /* Return true if offset is minus one because source of a polymorphic context
4729 cannot be an aggregate value. */
4732 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*,
4733 int , HOST_WIDE_INT offset
,
4734 ipa_polymorphic_call_context
)
4736 return offset
== -1;
4739 /* Decide whether to create a special version of NODE for value VAL of parameter
4740 at the given INDEX. If OFFSET is -1, the value is for the parameter itself,
4741 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS,
4742 KNOWN_CONTEXTS and KNOWN_AGGS describe the other already known values. */
4744 template <typename valtype
>
4746 decide_about_value (struct cgraph_node
*node
, int index
, HOST_WIDE_INT offset
,
4747 ipcp_value
<valtype
> *val
, vec
<tree
> known_csts
,
4748 vec
<ipa_polymorphic_call_context
> known_contexts
)
4750 struct ipa_agg_replacement_value
*aggvals
;
4751 int freq_sum
, caller_count
;
4752 profile_count count_sum
;
4753 vec
<cgraph_edge
*> callers
;
4757 perhaps_add_new_callers (node
, val
);
4760 else if (val
->local_size_cost
+ overall_size
> max_new_size
)
4762 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4763 fprintf (dump_file
, " Ignoring candidate value because "
4764 "max_new_size would be reached with %li.\n",
4765 val
->local_size_cost
+ overall_size
);
4768 else if (!get_info_about_necessary_edges (val
, node
, &freq_sum
, &count_sum
,
4772 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4774 fprintf (dump_file
, " - considering value ");
4775 print_ipcp_constant_value (dump_file
, val
->value
);
4776 fprintf (dump_file
, " for ");
4777 ipa_dump_param (dump_file
, IPA_NODE_REF (node
), index
);
4779 fprintf (dump_file
, ", offset: " HOST_WIDE_INT_PRINT_DEC
, offset
);
4780 fprintf (dump_file
, " (caller_count: %i)\n", caller_count
);
4783 if (!good_cloning_opportunity_p (node
, val
->local_time_benefit
,
4784 freq_sum
, count_sum
,
4785 val
->local_size_cost
)
4786 && !good_cloning_opportunity_p (node
,
4787 val
->local_time_benefit
4788 + val
->prop_time_benefit
,
4789 freq_sum
, count_sum
,
4790 val
->local_size_cost
4791 + val
->prop_size_cost
))
4795 fprintf (dump_file
, " Creating a specialized node of %s.\n",
4796 node
->dump_name ());
4798 callers
= gather_edges_for_value (val
, node
, caller_count
);
4800 modify_known_vectors_with_val (&known_csts
, &known_contexts
, val
, index
);
4803 known_csts
= known_csts
.copy ();
4804 known_contexts
= copy_useful_known_contexts (known_contexts
);
4806 find_more_scalar_values_for_callers_subset (node
, known_csts
, callers
);
4807 find_more_contexts_for_caller_subset (node
, &known_contexts
, callers
);
4808 aggvals
= find_aggregate_values_for_callers_subset (node
, callers
);
4809 gcc_checking_assert (ipcp_val_agg_replacement_ok_p (aggvals
, index
,
4810 offset
, val
->value
));
4811 val
->spec_node
= create_specialized_node (node
, known_csts
, known_contexts
,
4813 overall_size
+= val
->local_size_cost
;
4815 /* TODO: If for some lattice there is only one other known value
4816 left, make a special node for it too. */
4821 /* Decide whether and what specialized clones of NODE should be created. */
4824 decide_whether_version_node (struct cgraph_node
*node
)
4826 class ipa_node_params
*info
= IPA_NODE_REF (node
);
4827 int i
, count
= ipa_get_param_count (info
);
4828 vec
<tree
> known_csts
;
4829 vec
<ipa_polymorphic_call_context
> known_contexts
;
4830 vec
<ipa_agg_jump_function
> known_aggs
= vNULL
;
4836 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4837 fprintf (dump_file
, "\nEvaluating opportunities for %s.\n",
4838 node
->dump_name ());
4840 gather_context_independent_values (info
, &known_csts
, &known_contexts
,
4841 info
->do_clone_for_all_contexts
? &known_aggs
4844 for (i
= 0; i
< count
;i
++)
4846 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4847 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
4848 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
4853 ipcp_value
<tree
> *val
;
4854 for (val
= lat
->values
; val
; val
= val
->next
)
4855 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
4859 if (!plats
->aggs_bottom
)
4861 struct ipcp_agg_lattice
*aglat
;
4862 ipcp_value
<tree
> *val
;
4863 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
4864 if (!aglat
->bottom
&& aglat
->values
4865 /* If the following is false, the one value is in
4867 && (plats
->aggs_contain_variable
4868 || !aglat
->is_single_const ()))
4869 for (val
= aglat
->values
; val
; val
= val
->next
)
4870 ret
|= decide_about_value (node
, i
, aglat
->offset
, val
,
4871 known_csts
, known_contexts
);
4875 && known_contexts
[i
].useless_p ())
4877 ipcp_value
<ipa_polymorphic_call_context
> *val
;
4878 for (val
= ctxlat
->values
; val
; val
= val
->next
)
4879 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
4883 info
= IPA_NODE_REF (node
);
4886 if (info
->do_clone_for_all_contexts
)
4888 struct cgraph_node
*clone
;
4889 vec
<cgraph_edge
*> callers
;
4892 fprintf (dump_file
, " - Creating a specialized node of %s "
4893 "for all known contexts.\n", node
->dump_name ());
4895 callers
= node
->collect_callers ();
4896 find_more_scalar_values_for_callers_subset (node
, known_csts
, callers
);
4897 find_more_contexts_for_caller_subset (node
, &known_contexts
, callers
);
4898 ipa_agg_replacement_value
*aggvals
4899 = find_aggregate_values_for_callers_subset (node
, callers
);
4901 if (!known_contexts_useful_p (known_contexts
))
4903 known_contexts
.release ();
4904 known_contexts
= vNULL
;
4906 clone
= create_specialized_node (node
, known_csts
, known_contexts
,
4908 info
= IPA_NODE_REF (node
);
4909 info
->do_clone_for_all_contexts
= false;
4910 IPA_NODE_REF (clone
)->is_all_contexts_clone
= true;
4911 for (i
= 0; i
< count
; i
++)
4912 vec_free (known_aggs
[i
].items
);
4913 known_aggs
.release ();
4918 known_csts
.release ();
4919 known_contexts
.release ();
4925 /* Transitively mark all callees of NODE within the same SCC as not dead. */
4928 spread_undeadness (struct cgraph_node
*node
)
4930 struct cgraph_edge
*cs
;
4932 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
4933 if (ipa_edge_within_scc (cs
))
4935 struct cgraph_node
*callee
;
4936 class ipa_node_params
*info
;
4938 callee
= cs
->callee
->function_symbol (NULL
);
4939 info
= IPA_NODE_REF (callee
);
4941 if (info
->node_dead
)
4943 info
->node_dead
= 0;
4944 spread_undeadness (callee
);
4949 /* Return true if NODE has a caller from outside of its SCC that is not
4950 dead. Worker callback for cgraph_for_node_and_aliases. */
4953 has_undead_caller_from_outside_scc_p (struct cgraph_node
*node
,
4954 void *data ATTRIBUTE_UNUSED
)
4956 struct cgraph_edge
*cs
;
4958 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
4959 if (cs
->caller
->thunk
.thunk_p
4960 && cs
->caller
->call_for_symbol_thunks_and_aliases
4961 (has_undead_caller_from_outside_scc_p
, NULL
, true))
4963 else if (!ipa_edge_within_scc (cs
)
4964 && !IPA_NODE_REF (cs
->caller
)->node_dead
)
4970 /* Identify nodes within the same SCC as NODE which are no longer needed
4971 because of new clones and will be removed as unreachable. */
4974 identify_dead_nodes (struct cgraph_node
*node
)
4976 struct cgraph_node
*v
;
4977 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4979 && !v
->call_for_symbol_thunks_and_aliases
4980 (has_undead_caller_from_outside_scc_p
, NULL
, true))
4981 IPA_NODE_REF (v
)->node_dead
= 1;
4983 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4984 if (!IPA_NODE_REF (v
)->node_dead
)
4985 spread_undeadness (v
);
4987 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4989 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4990 if (IPA_NODE_REF (v
)->node_dead
)
4991 fprintf (dump_file
, " Marking node as dead: %s.\n", v
->dump_name ());
4995 /* The decision stage. Iterate over the topological order of call graph nodes
4996 TOPO and make specialized clones if deemed beneficial. */
4999 ipcp_decision_stage (class ipa_topo_info
*topo
)
5004 fprintf (dump_file
, "\nIPA decision stage:\n\n");
5006 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
5008 struct cgraph_node
*node
= topo
->order
[i
];
5009 bool change
= false, iterate
= true;
5013 struct cgraph_node
*v
;
5015 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
5016 if (v
->has_gimple_body_p ()
5017 && ipcp_versionable_function_p (v
))
5018 iterate
|= decide_whether_version_node (v
);
5023 identify_dead_nodes (node
);
5027 /* Look up all the bits information that we have discovered and copy it over
5028 to the transformation summary. */
5031 ipcp_store_bits_results (void)
5035 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5037 ipa_node_params
*info
= IPA_NODE_REF (node
);
5038 bool dumped_sth
= false;
5039 bool found_useful_result
= false;
5041 if (!opt_for_fn (node
->decl
, flag_ipa_bit_cp
))
5044 fprintf (dump_file
, "Not considering %s for ipa bitwise propagation "
5045 "; -fipa-bit-cp: disabled.\n",
5050 if (info
->ipcp_orig_node
)
5051 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
5053 unsigned count
= ipa_get_param_count (info
);
5054 for (unsigned i
= 0; i
< count
; i
++)
5056 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5057 if (plats
->bits_lattice
.constant_p ())
5059 found_useful_result
= true;
5064 if (!found_useful_result
)
5067 ipcp_transformation_initialize ();
5068 ipcp_transformation
*ts
= ipcp_transformation_sum
->get_create (node
);
5069 vec_safe_reserve_exact (ts
->bits
, count
);
5071 for (unsigned i
= 0; i
< count
; i
++)
5073 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5076 if (plats
->bits_lattice
.constant_p ())
5078 = ipa_get_ipa_bits_for_value (plats
->bits_lattice
.get_value (),
5079 plats
->bits_lattice
.get_mask ());
5083 ts
->bits
->quick_push (jfbits
);
5084 if (!dump_file
|| !jfbits
)
5088 fprintf (dump_file
, "Propagated bits info for function %s:\n",
5089 node
->dump_name ());
5092 fprintf (dump_file
, " param %i: value = ", i
);
5093 print_hex (jfbits
->value
, dump_file
);
5094 fprintf (dump_file
, ", mask = ");
5095 print_hex (jfbits
->mask
, dump_file
);
5096 fprintf (dump_file
, "\n");
5101 /* Look up all VR information that we have discovered and copy it over
5102 to the transformation summary. */
5105 ipcp_store_vr_results (void)
5109 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5111 ipa_node_params
*info
= IPA_NODE_REF (node
);
5112 bool found_useful_result
= false;
5114 if (!opt_for_fn (node
->decl
, flag_ipa_vrp
))
5117 fprintf (dump_file
, "Not considering %s for VR discovery "
5118 "and propagate; -fipa-ipa-vrp: disabled.\n",
5123 if (info
->ipcp_orig_node
)
5124 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
5126 unsigned count
= ipa_get_param_count (info
);
5127 for (unsigned i
= 0; i
< count
; i
++)
5129 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5130 if (!plats
->m_value_range
.bottom_p ()
5131 && !plats
->m_value_range
.top_p ())
5133 found_useful_result
= true;
5137 if (!found_useful_result
)
5140 ipcp_transformation_initialize ();
5141 ipcp_transformation
*ts
= ipcp_transformation_sum
->get_create (node
);
5142 vec_safe_reserve_exact (ts
->m_vr
, count
);
5144 for (unsigned i
= 0; i
< count
; i
++)
5146 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5149 if (!plats
->m_value_range
.bottom_p ()
5150 && !plats
->m_value_range
.top_p ())
5153 vr
.type
= plats
->m_value_range
.m_vr
.kind ();
5154 vr
.min
= wi::to_wide (plats
->m_value_range
.m_vr
.min ());
5155 vr
.max
= wi::to_wide (plats
->m_value_range
.m_vr
.max ());
5160 vr
.type
= VR_VARYING
;
5161 vr
.min
= vr
.max
= wi::zero (INT_TYPE_SIZE
);
5163 ts
->m_vr
->quick_push (vr
);
5168 /* The IPCP driver. */
5173 class ipa_topo_info topo
;
5175 if (edge_clone_summaries
== NULL
)
5176 edge_clone_summaries
= new edge_clone_summary_t (symtab
);
5178 ipa_check_create_node_params ();
5179 ipa_check_create_edge_args ();
5180 clone_num_suffixes
= new hash_map
<const char *, unsigned>;
5184 fprintf (dump_file
, "\nIPA structures before propagation:\n");
5185 if (dump_flags
& TDF_DETAILS
)
5186 ipa_print_all_params (dump_file
);
5187 ipa_print_all_jump_functions (dump_file
);
5190 /* Topological sort. */
5191 build_toporder_info (&topo
);
5192 /* Do the interprocedural propagation. */
5193 ipcp_propagate_stage (&topo
);
5194 /* Decide what constant propagation and cloning should be performed. */
5195 ipcp_decision_stage (&topo
);
5196 /* Store results of bits propagation. */
5197 ipcp_store_bits_results ();
5198 /* Store results of value range propagation. */
5199 ipcp_store_vr_results ();
5201 /* Free all IPCP structures. */
5202 delete clone_num_suffixes
;
5203 free_toporder_info (&topo
);
5204 delete edge_clone_summaries
;
5205 edge_clone_summaries
= NULL
;
5206 ipa_free_all_structures_after_ipa_cp ();
5208 fprintf (dump_file
, "\nIPA constant propagation end\n");
5212 /* Initialization and computation of IPCP data structures. This is the initial
5213 intraprocedural analysis of functions, which gathers information to be
5214 propagated later on. */
5217 ipcp_generate_summary (void)
5219 struct cgraph_node
*node
;
5222 fprintf (dump_file
, "\nIPA constant propagation start:\n");
5223 ipa_register_cgraph_hooks ();
5225 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5226 ipa_analyze_node (node
);
5229 /* Write ipcp summary for nodes in SET. */
5232 ipcp_write_summary (void)
5234 ipa_prop_write_jump_functions ();
5237 /* Read ipcp summary. */
5240 ipcp_read_summary (void)
5242 ipa_prop_read_jump_functions ();
5247 const pass_data pass_data_ipa_cp
=
5249 IPA_PASS
, /* type */
5251 OPTGROUP_NONE
, /* optinfo_flags */
5252 TV_IPA_CONSTANT_PROP
, /* tv_id */
5253 0, /* properties_required */
5254 0, /* properties_provided */
5255 0, /* properties_destroyed */
5256 0, /* todo_flags_start */
5257 ( TODO_dump_symtab
| TODO_remove_functions
), /* todo_flags_finish */
5260 class pass_ipa_cp
: public ipa_opt_pass_d
5263 pass_ipa_cp (gcc::context
*ctxt
)
5264 : ipa_opt_pass_d (pass_data_ipa_cp
, ctxt
,
5265 ipcp_generate_summary
, /* generate_summary */
5266 ipcp_write_summary
, /* write_summary */
5267 ipcp_read_summary
, /* read_summary */
5268 ipcp_write_transformation_summaries
, /*
5269 write_optimization_summary */
5270 ipcp_read_transformation_summaries
, /*
5271 read_optimization_summary */
5272 NULL
, /* stmt_fixup */
5273 0, /* function_transform_todo_flags_start */
5274 ipcp_transform_function
, /* function_transform */
5275 NULL
) /* variable_transform */
5278 /* opt_pass methods: */
5279 virtual bool gate (function
*)
5281 /* FIXME: We should remove the optimize check after we ensure we never run
5282 IPA passes when not optimizing. */
5283 return (flag_ipa_cp
&& optimize
) || in_lto_p
;
5286 virtual unsigned int execute (function
*) { return ipcp_driver (); }
5288 }; // class pass_ipa_cp
5293 make_pass_ipa_cp (gcc::context
*ctxt
)
5295 return new pass_ipa_cp (ctxt
);
5298 /* Reset all state within ipa-cp.c so that we can rerun the compiler
5299 within the same process. For use by toplev::finalize. */
5302 ipa_cp_c_finalize (void)
5304 max_count
= profile_count::uninitialized ();
5307 ipcp_free_transformation_sum ();