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
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
*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
*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
->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_size_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
*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
*other_vr
)
947 if (other_vr
->varying_p ())
948 return set_to_bottom ();
950 value_range
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
)
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
)
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
)
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
*dst_vr
,
1943 value_range
*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 ();
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
tmpvr (VR_RANGE
, val
, val
);
2004 return dest_lat
->meet_with (&tmpvr
);
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 parms_count
= ipa_get_param_count (callee_info
);
2313 if (parms_count
== 0)
2317 for (i
= 0; i
< parms_count
; i
++)
2318 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
2322 args_count
= ipa_get_cs_argument_count (args
);
2324 /* If this call goes through a thunk we must not propagate to the first (0th)
2325 parameter. However, we might need to uncover a thunk from below a series
2326 of aliases first. */
2327 if (call_passes_through_thunk_p (cs
))
2329 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
2336 for (; (i
< args_count
) && (i
< parms_count
); i
++)
2338 struct ipa_jump_func
*jump_func
= ipa_get_ith_jump_func (args
, i
);
2339 class ipcp_param_lattices
*dest_plats
;
2340 tree param_type
= ipa_get_type (callee_info
, i
);
2342 dest_plats
= ipa_get_parm_lattices (callee_info
, i
);
2343 if (availability
== AVAIL_INTERPOSABLE
)
2344 ret
|= set_all_contains_variable (dest_plats
);
2347 ret
|= propagate_scalar_across_jump_function (cs
, jump_func
,
2348 &dest_plats
->itself
,
2350 ret
|= propagate_context_across_jump_function (cs
, jump_func
, i
,
2351 &dest_plats
->ctxlat
);
2353 |= propagate_bits_across_jump_function (cs
, i
, jump_func
,
2354 &dest_plats
->bits_lattice
);
2355 ret
|= propagate_aggs_across_jump_function (cs
, jump_func
,
2357 if (opt_for_fn (callee
->decl
, flag_ipa_vrp
))
2358 ret
|= propagate_vr_across_jump_function (cs
, jump_func
,
2359 dest_plats
, param_type
);
2361 ret
|= dest_plats
->m_value_range
.set_to_bottom ();
2364 for (; i
< parms_count
; i
++)
2365 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
, i
));
2370 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
2371 KNOWN_CONTEXTS, KNOWN_AGGS or AGG_REPS return the destination. The latter
2372 three can be NULL. If AGG_REPS is not NULL, KNOWN_AGGS is ignored. */
2375 ipa_get_indirect_edge_target_1 (struct cgraph_edge
*ie
,
2376 vec
<tree
> known_csts
,
2377 vec
<ipa_polymorphic_call_context
> known_contexts
,
2378 vec
<ipa_agg_jump_function_p
> known_aggs
,
2379 struct ipa_agg_replacement_value
*agg_reps
,
2382 int param_index
= ie
->indirect_info
->param_index
;
2383 HOST_WIDE_INT anc_offset
;
2387 *speculative
= false;
2389 if (param_index
== -1
2390 || known_csts
.length () <= (unsigned int) param_index
)
2393 if (!ie
->indirect_info
->polymorphic
)
2397 if (ie
->indirect_info
->agg_contents
)
2400 if (agg_reps
&& ie
->indirect_info
->guaranteed_unmodified
)
2404 if (agg_reps
->index
== param_index
2405 && agg_reps
->offset
== ie
->indirect_info
->offset
2406 && agg_reps
->by_ref
== ie
->indirect_info
->by_ref
)
2408 t
= agg_reps
->value
;
2411 agg_reps
= agg_reps
->next
;
2416 struct ipa_agg_jump_function
*agg
;
2417 if (known_aggs
.length () > (unsigned int) param_index
)
2418 agg
= known_aggs
[param_index
];
2421 bool from_global_constant
;
2422 t
= ipa_find_agg_cst_for_param (agg
, known_csts
[param_index
],
2423 ie
->indirect_info
->offset
,
2424 ie
->indirect_info
->by_ref
,
2425 &from_global_constant
);
2427 && !from_global_constant
2428 && !ie
->indirect_info
->guaranteed_unmodified
)
2433 t
= known_csts
[param_index
];
2436 && TREE_CODE (t
) == ADDR_EXPR
2437 && TREE_CODE (TREE_OPERAND (t
, 0)) == FUNCTION_DECL
)
2438 return TREE_OPERAND (t
, 0);
2443 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize
))
2446 gcc_assert (!ie
->indirect_info
->agg_contents
);
2447 anc_offset
= ie
->indirect_info
->offset
;
2451 /* Try to work out value of virtual table pointer value in replacements. */
2452 if (!t
&& agg_reps
&& !ie
->indirect_info
->by_ref
)
2456 if (agg_reps
->index
== param_index
2457 && agg_reps
->offset
== ie
->indirect_info
->offset
2458 && agg_reps
->by_ref
)
2460 t
= agg_reps
->value
;
2463 agg_reps
= agg_reps
->next
;
2467 /* Try to work out value of virtual table pointer value in known
2468 aggregate values. */
2469 if (!t
&& known_aggs
.length () > (unsigned int) param_index
2470 && !ie
->indirect_info
->by_ref
)
2472 struct ipa_agg_jump_function
*agg
;
2473 agg
= known_aggs
[param_index
];
2474 t
= ipa_find_agg_cst_for_param (agg
, known_csts
[param_index
],
2475 ie
->indirect_info
->offset
, true);
2478 /* If we found the virtual table pointer, lookup the target. */
2482 unsigned HOST_WIDE_INT offset
;
2483 if (vtable_pointer_value_to_vtable (t
, &vtable
, &offset
))
2486 target
= gimple_get_virt_method_for_vtable (ie
->indirect_info
->otr_token
,
2487 vtable
, offset
, &can_refer
);
2491 || fndecl_built_in_p (target
, BUILT_IN_UNREACHABLE
)
2492 || !possible_polymorphic_call_target_p
2493 (ie
, cgraph_node::get (target
)))
2495 /* Do not speculate builtin_unreachable, it is stupid! */
2496 if (ie
->indirect_info
->vptr_changed
)
2498 target
= ipa_impossible_devirt_target (ie
, target
);
2500 *speculative
= ie
->indirect_info
->vptr_changed
;
2507 /* Do we know the constant value of pointer? */
2509 t
= known_csts
[param_index
];
2511 gcc_checking_assert (!t
|| TREE_CODE (t
) != TREE_BINFO
);
2513 ipa_polymorphic_call_context context
;
2514 if (known_contexts
.length () > (unsigned int) param_index
)
2516 context
= known_contexts
[param_index
];
2517 context
.offset_by (anc_offset
);
2518 if (ie
->indirect_info
->vptr_changed
)
2519 context
.possible_dynamic_type_change (ie
->in_polymorphic_cdtor
,
2520 ie
->indirect_info
->otr_type
);
2523 ipa_polymorphic_call_context ctx2
= ipa_polymorphic_call_context
2524 (t
, ie
->indirect_info
->otr_type
, anc_offset
);
2525 if (!ctx2
.useless_p ())
2526 context
.combine_with (ctx2
, ie
->indirect_info
->otr_type
);
2531 context
= ipa_polymorphic_call_context (t
, ie
->indirect_info
->otr_type
,
2533 if (ie
->indirect_info
->vptr_changed
)
2534 context
.possible_dynamic_type_change (ie
->in_polymorphic_cdtor
,
2535 ie
->indirect_info
->otr_type
);
2540 vec
<cgraph_node
*>targets
;
2543 targets
= possible_polymorphic_call_targets
2544 (ie
->indirect_info
->otr_type
,
2545 ie
->indirect_info
->otr_token
,
2547 if (!final
|| targets
.length () > 1)
2549 struct cgraph_node
*node
;
2552 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize_speculatively
)
2553 || ie
->speculative
|| !ie
->maybe_hot_p ())
2555 node
= try_speculative_devirtualization (ie
->indirect_info
->otr_type
,
2556 ie
->indirect_info
->otr_token
,
2560 *speculative
= true;
2561 target
= node
->decl
;
2568 *speculative
= false;
2569 if (targets
.length () == 1)
2570 target
= targets
[0]->decl
;
2572 target
= ipa_impossible_devirt_target (ie
, NULL_TREE
);
2575 if (target
&& !possible_polymorphic_call_target_p (ie
,
2576 cgraph_node::get (target
)))
2580 target
= ipa_impossible_devirt_target (ie
, target
);
2587 /* If an indirect edge IE can be turned into a direct one based on KNOWN_CSTS,
2588 KNOWN_CONTEXTS (which can be vNULL) or KNOWN_AGGS (which also can be vNULL)
2589 return the destination. */
2592 ipa_get_indirect_edge_target (struct cgraph_edge
*ie
,
2593 vec
<tree
> known_csts
,
2594 vec
<ipa_polymorphic_call_context
> known_contexts
,
2595 vec
<ipa_agg_jump_function_p
> known_aggs
,
2598 return ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
2599 known_aggs
, NULL
, speculative
);
2602 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
2603 and KNOWN_CONTEXTS. */
2606 devirtualization_time_bonus (struct cgraph_node
*node
,
2607 vec
<tree
> known_csts
,
2608 vec
<ipa_polymorphic_call_context
> known_contexts
,
2609 vec
<ipa_agg_jump_function_p
> known_aggs
)
2611 struct cgraph_edge
*ie
;
2614 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
2616 struct cgraph_node
*callee
;
2617 class ipa_fn_summary
*isummary
;
2618 enum availability avail
;
2622 target
= ipa_get_indirect_edge_target (ie
, known_csts
, known_contexts
,
2623 known_aggs
, &speculative
);
2627 /* Only bare minimum benefit for clearly un-inlineable targets. */
2629 callee
= cgraph_node::get (target
);
2630 if (!callee
|| !callee
->definition
)
2632 callee
= callee
->function_symbol (&avail
);
2633 if (avail
< AVAIL_AVAILABLE
)
2635 isummary
= ipa_fn_summaries
->get (callee
);
2636 if (!isummary
->inlinable
)
2639 int size
= ipa_size_summaries
->get (callee
)->size
;
2640 /* FIXME: The values below need re-considering and perhaps also
2641 integrating into the cost metrics, at lest in some very basic way. */
2642 if (size
<= MAX_INLINE_INSNS_AUTO
/ 4)
2643 res
+= 31 / ((int)speculative
+ 1);
2644 else if (size
<= MAX_INLINE_INSNS_AUTO
/ 2)
2645 res
+= 15 / ((int)speculative
+ 1);
2646 else if (size
<= MAX_INLINE_INSNS_AUTO
2647 || DECL_DECLARED_INLINE_P (callee
->decl
))
2648 res
+= 7 / ((int)speculative
+ 1);
2654 /* Return time bonus incurred because of HINTS. */
2657 hint_time_bonus (ipa_hints hints
)
2660 if (hints
& (INLINE_HINT_loop_iterations
| INLINE_HINT_loop_stride
))
2661 result
+= PARAM_VALUE (PARAM_IPA_CP_LOOP_HINT_BONUS
);
2665 /* If there is a reason to penalize the function described by INFO in the
2666 cloning goodness evaluation, do so. */
2668 static inline int64_t
2669 incorporate_penalties (ipa_node_params
*info
, int64_t evaluation
)
2671 if (info
->node_within_scc
)
2672 evaluation
= (evaluation
2673 * (100 - PARAM_VALUE (PARAM_IPA_CP_RECURSION_PENALTY
))) / 100;
2675 if (info
->node_calling_single_call
)
2676 evaluation
= (evaluation
2677 * (100 - PARAM_VALUE (PARAM_IPA_CP_SINGLE_CALL_PENALTY
)))
2683 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
2684 and SIZE_COST and with the sum of frequencies of incoming edges to the
2685 potential new clone in FREQUENCIES. */
2688 good_cloning_opportunity_p (struct cgraph_node
*node
, int time_benefit
,
2689 int freq_sum
, profile_count count_sum
, int size_cost
)
2691 if (time_benefit
== 0
2692 || !opt_for_fn (node
->decl
, flag_ipa_cp_clone
)
2693 || node
->optimize_for_size_p ())
2696 gcc_assert (size_cost
> 0);
2698 class ipa_node_params
*info
= IPA_NODE_REF (node
);
2699 if (max_count
> profile_count::zero ())
2701 int factor
= RDIV (count_sum
.probability_in
2702 (max_count
).to_reg_br_prob_base ()
2703 * 1000, REG_BR_PROB_BASE
);
2704 int64_t evaluation
= (((int64_t) time_benefit
* factor
)
2706 evaluation
= incorporate_penalties (info
, evaluation
);
2708 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2710 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
2711 "size: %i, count_sum: ", time_benefit
, size_cost
);
2712 count_sum
.dump (dump_file
);
2713 fprintf (dump_file
, "%s%s) -> evaluation: " "%" PRId64
2714 ", threshold: %i\n",
2715 info
->node_within_scc
? ", scc" : "",
2716 info
->node_calling_single_call
? ", single_call" : "",
2717 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
2720 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
2724 int64_t evaluation
= (((int64_t) time_benefit
* freq_sum
)
2726 evaluation
= incorporate_penalties (info
, evaluation
);
2728 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2729 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
2730 "size: %i, freq_sum: %i%s%s) -> evaluation: "
2731 "%" PRId64
", threshold: %i\n",
2732 time_benefit
, size_cost
, freq_sum
,
2733 info
->node_within_scc
? ", scc" : "",
2734 info
->node_calling_single_call
? ", single_call" : "",
2735 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
2737 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
2741 /* Return all context independent values from aggregate lattices in PLATS in a
2742 vector. Return NULL if there are none. */
2744 static vec
<ipa_agg_jf_item
, va_gc
> *
2745 context_independent_aggregate_values (class ipcp_param_lattices
*plats
)
2747 vec
<ipa_agg_jf_item
, va_gc
> *res
= NULL
;
2749 if (plats
->aggs_bottom
2750 || plats
->aggs_contain_variable
2751 || plats
->aggs_count
== 0)
2754 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
;
2756 aglat
= aglat
->next
)
2757 if (aglat
->is_single_const ())
2759 struct ipa_agg_jf_item item
;
2760 item
.offset
= aglat
->offset
;
2761 item
.value
= aglat
->values
->value
;
2762 vec_safe_push (res
, item
);
2767 /* Allocate KNOWN_CSTS, KNOWN_CONTEXTS and, if non-NULL, KNOWN_AGGS and
2768 populate them with values of parameters that are known independent of the
2769 context. INFO describes the function. If REMOVABLE_PARAMS_COST is
2770 non-NULL, the movement cost of all removable parameters will be stored in
2774 gather_context_independent_values (class ipa_node_params
*info
,
2775 vec
<tree
> *known_csts
,
2776 vec
<ipa_polymorphic_call_context
>
2778 vec
<ipa_agg_jump_function
> *known_aggs
,
2779 int *removable_params_cost
)
2781 int i
, count
= ipa_get_param_count (info
);
2784 known_csts
->create (0);
2785 known_contexts
->create (0);
2786 known_csts
->safe_grow_cleared (count
);
2787 known_contexts
->safe_grow_cleared (count
);
2790 known_aggs
->create (0);
2791 known_aggs
->safe_grow_cleared (count
);
2794 if (removable_params_cost
)
2795 *removable_params_cost
= 0;
2797 for (i
= 0; i
< count
; i
++)
2799 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2800 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
2802 if (lat
->is_single_const ())
2804 ipcp_value
<tree
> *val
= lat
->values
;
2805 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
2806 (*known_csts
)[i
] = val
->value
;
2807 if (removable_params_cost
)
2808 *removable_params_cost
2809 += estimate_move_cost (TREE_TYPE (val
->value
), false);
2812 else if (removable_params_cost
2813 && !ipa_is_param_used (info
, i
))
2814 *removable_params_cost
2815 += ipa_get_param_move_cost (info
, i
);
2817 if (!ipa_is_param_used (info
, i
))
2820 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
2821 /* Do not account known context as reason for cloning. We can see
2822 if it permits devirtualization. */
2823 if (ctxlat
->is_single_const ())
2824 (*known_contexts
)[i
] = ctxlat
->values
->value
;
2828 vec
<ipa_agg_jf_item
, va_gc
> *agg_items
;
2829 struct ipa_agg_jump_function
*ajf
;
2831 agg_items
= context_independent_aggregate_values (plats
);
2832 ajf
= &(*known_aggs
)[i
];
2833 ajf
->items
= agg_items
;
2834 ajf
->by_ref
= plats
->aggs_by_ref
;
2835 ret
|= agg_items
!= NULL
;
2842 /* The current interface in ipa-inline-analysis requires a pointer vector.
2845 FIXME: That interface should be re-worked, this is slightly silly. Still,
2846 I'd like to discuss how to change it first and this demonstrates the
2849 static vec
<ipa_agg_jump_function_p
>
2850 agg_jmp_p_vec_for_t_vec (vec
<ipa_agg_jump_function
> known_aggs
)
2852 vec
<ipa_agg_jump_function_p
> ret
;
2853 struct ipa_agg_jump_function
*ajf
;
2856 ret
.create (known_aggs
.length ());
2857 FOR_EACH_VEC_ELT (known_aggs
, i
, ajf
)
2858 ret
.quick_push (ajf
);
2862 /* Perform time and size measurement of NODE with the context given in
2863 KNOWN_CSTS, KNOWN_CONTEXTS and KNOWN_AGGS, calculate the benefit and cost
2864 given BASE_TIME of the node without specialization, REMOVABLE_PARAMS_COST of
2865 all context-independent removable parameters and EST_MOVE_COST of estimated
2866 movement of the considered parameter and store it into VAL. */
2869 perform_estimation_of_a_value (cgraph_node
*node
, vec
<tree
> known_csts
,
2870 vec
<ipa_polymorphic_call_context
> known_contexts
,
2871 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
,
2872 int removable_params_cost
,
2873 int est_move_cost
, ipcp_value_base
*val
)
2875 int size
, time_benefit
;
2876 sreal time
, base_time
;
2879 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
2880 known_aggs_ptrs
, &size
, &time
,
2881 &base_time
, &hints
);
2883 if (base_time
> 65535)
2886 /* Extern inline functions have no cloning local time benefits because they
2887 will be inlined anyway. The only reason to clone them is if it enables
2888 optimization in any of the functions they call. */
2889 if (DECL_EXTERNAL (node
->decl
) && DECL_DECLARED_INLINE_P (node
->decl
))
2892 time_benefit
= base_time
.to_int ()
2893 + devirtualization_time_bonus (node
, known_csts
, known_contexts
,
2895 + hint_time_bonus (hints
)
2896 + removable_params_cost
+ est_move_cost
;
2898 gcc_checking_assert (size
>=0);
2899 /* The inliner-heuristics based estimates may think that in certain
2900 contexts some functions do not have any size at all but we want
2901 all specializations to have at least a tiny cost, not least not to
2906 val
->local_time_benefit
= time_benefit
;
2907 val
->local_size_cost
= size
;
2910 /* Iterate over known values of parameters of NODE and estimate the local
2911 effects in terms of time and size they have. */
2914 estimate_local_effects (struct cgraph_node
*node
)
2916 class ipa_node_params
*info
= IPA_NODE_REF (node
);
2917 int i
, count
= ipa_get_param_count (info
);
2918 vec
<tree
> known_csts
;
2919 vec
<ipa_polymorphic_call_context
> known_contexts
;
2920 vec
<ipa_agg_jump_function
> known_aggs
;
2921 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
;
2923 int removable_params_cost
;
2925 if (!count
|| !ipcp_versionable_function_p (node
))
2928 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2929 fprintf (dump_file
, "\nEstimating effects for %s.\n", node
->dump_name ());
2931 always_const
= gather_context_independent_values (info
, &known_csts
,
2932 &known_contexts
, &known_aggs
,
2933 &removable_params_cost
);
2934 known_aggs_ptrs
= agg_jmp_p_vec_for_t_vec (known_aggs
);
2935 int devirt_bonus
= devirtualization_time_bonus (node
, known_csts
,
2936 known_contexts
, known_aggs_ptrs
);
2937 if (always_const
|| devirt_bonus
2938 || (removable_params_cost
&& node
->can_change_signature
))
2940 struct caller_statistics stats
;
2942 sreal time
, base_time
;
2945 init_caller_stats (&stats
);
2946 node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
2948 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
2949 known_aggs_ptrs
, &size
, &time
,
2950 &base_time
, &hints
);
2951 time
-= devirt_bonus
;
2952 time
-= hint_time_bonus (hints
);
2953 time
-= removable_params_cost
;
2954 size
-= stats
.n_calls
* removable_params_cost
;
2957 fprintf (dump_file
, " - context independent values, size: %i, "
2958 "time_benefit: %f\n", size
, (base_time
- time
).to_double ());
2960 if (size
<= 0 || node
->local
)
2962 info
->do_clone_for_all_contexts
= true;
2965 fprintf (dump_file
, " Decided to specialize for all "
2966 "known contexts, code not going to grow.\n");
2968 else if (good_cloning_opportunity_p (node
,
2969 MIN ((base_time
- time
).to_int (),
2971 stats
.freq_sum
, stats
.count_sum
,
2974 if (size
+ overall_size
<= max_new_size
)
2976 info
->do_clone_for_all_contexts
= true;
2977 overall_size
+= size
;
2980 fprintf (dump_file
, " Decided to specialize for all "
2981 "known contexts, growth deemed beneficial.\n");
2983 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2984 fprintf (dump_file
, " Not cloning for all contexts because "
2985 "max_new_size would be reached with %li.\n",
2986 size
+ overall_size
);
2988 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2989 fprintf (dump_file
, " Not cloning for all contexts because "
2990 "!good_cloning_opportunity_p.\n");
2994 for (i
= 0; i
< count
; i
++)
2996 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2997 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
2998 ipcp_value
<tree
> *val
;
3005 for (val
= lat
->values
; val
; val
= val
->next
)
3007 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
3008 known_csts
[i
] = val
->value
;
3010 int emc
= estimate_move_cost (TREE_TYPE (val
->value
), true);
3011 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
3013 removable_params_cost
, emc
, val
);
3015 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3017 fprintf (dump_file
, " - estimates for value ");
3018 print_ipcp_constant_value (dump_file
, val
->value
);
3019 fprintf (dump_file
, " for ");
3020 ipa_dump_param (dump_file
, info
, i
);
3021 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
3022 val
->local_time_benefit
, val
->local_size_cost
);
3025 known_csts
[i
] = NULL_TREE
;
3028 for (i
= 0; i
< count
; i
++)
3030 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3032 if (!plats
->virt_call
)
3035 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
3036 ipcp_value
<ipa_polymorphic_call_context
> *val
;
3040 || !known_contexts
[i
].useless_p ())
3043 for (val
= ctxlat
->values
; val
; val
= val
->next
)
3045 known_contexts
[i
] = val
->value
;
3046 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
3048 removable_params_cost
, 0, val
);
3050 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3052 fprintf (dump_file
, " - estimates for polymorphic context ");
3053 print_ipcp_constant_value (dump_file
, val
->value
);
3054 fprintf (dump_file
, " for ");
3055 ipa_dump_param (dump_file
, info
, i
);
3056 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
3057 val
->local_time_benefit
, val
->local_size_cost
);
3060 known_contexts
[i
] = ipa_polymorphic_call_context ();
3063 for (i
= 0; i
< count
; i
++)
3065 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3066 struct ipa_agg_jump_function
*ajf
;
3067 struct ipcp_agg_lattice
*aglat
;
3069 if (plats
->aggs_bottom
|| !plats
->aggs
)
3072 ajf
= &known_aggs
[i
];
3073 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3075 ipcp_value
<tree
> *val
;
3076 if (aglat
->bottom
|| !aglat
->values
3077 /* If the following is true, the one value is in known_aggs. */
3078 || (!plats
->aggs_contain_variable
3079 && aglat
->is_single_const ()))
3082 for (val
= aglat
->values
; val
; val
= val
->next
)
3084 struct ipa_agg_jf_item item
;
3086 item
.offset
= aglat
->offset
;
3087 item
.value
= val
->value
;
3088 vec_safe_push (ajf
->items
, item
);
3090 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
3092 removable_params_cost
, 0, val
);
3094 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3096 fprintf (dump_file
, " - estimates for value ");
3097 print_ipcp_constant_value (dump_file
, val
->value
);
3098 fprintf (dump_file
, " for ");
3099 ipa_dump_param (dump_file
, info
, i
);
3100 fprintf (dump_file
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
3101 "]: time_benefit: %i, size: %i\n",
3102 plats
->aggs_by_ref
? "ref " : "",
3104 val
->local_time_benefit
, val
->local_size_cost
);
3112 for (i
= 0; i
< count
; i
++)
3113 vec_free (known_aggs
[i
].items
);
3115 known_csts
.release ();
3116 known_contexts
.release ();
3117 known_aggs
.release ();
3118 known_aggs_ptrs
.release ();
3122 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
3123 topological sort of values. */
3125 template <typename valtype
>
3127 value_topo_info
<valtype
>::add_val (ipcp_value
<valtype
> *cur_val
)
3129 ipcp_value_source
<valtype
> *src
;
3135 cur_val
->dfs
= dfs_counter
;
3136 cur_val
->low_link
= dfs_counter
;
3138 cur_val
->topo_next
= stack
;
3140 cur_val
->on_stack
= true;
3142 for (src
= cur_val
->sources
; src
; src
= src
->next
)
3145 if (src
->val
->dfs
== 0)
3148 if (src
->val
->low_link
< cur_val
->low_link
)
3149 cur_val
->low_link
= src
->val
->low_link
;
3151 else if (src
->val
->on_stack
3152 && src
->val
->dfs
< cur_val
->low_link
)
3153 cur_val
->low_link
= src
->val
->dfs
;
3156 if (cur_val
->dfs
== cur_val
->low_link
)
3158 ipcp_value
<valtype
> *v
, *scc_list
= NULL
;
3163 stack
= v
->topo_next
;
3164 v
->on_stack
= false;
3166 v
->scc_next
= scc_list
;
3169 while (v
!= cur_val
);
3171 cur_val
->topo_next
= values_topo
;
3172 values_topo
= cur_val
;
3176 /* Add all values in lattices associated with NODE to the topological sort if
3177 they are not there yet. */
3180 add_all_node_vals_to_toposort (cgraph_node
*node
, ipa_topo_info
*topo
)
3182 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3183 int i
, count
= ipa_get_param_count (info
);
3185 for (i
= 0; i
< count
; i
++)
3187 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3188 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
3189 struct ipcp_agg_lattice
*aglat
;
3193 ipcp_value
<tree
> *val
;
3194 for (val
= lat
->values
; val
; val
= val
->next
)
3195 topo
->constants
.add_val (val
);
3198 if (!plats
->aggs_bottom
)
3199 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3202 ipcp_value
<tree
> *val
;
3203 for (val
= aglat
->values
; val
; val
= val
->next
)
3204 topo
->constants
.add_val (val
);
3207 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
3208 if (!ctxlat
->bottom
)
3210 ipcp_value
<ipa_polymorphic_call_context
> *ctxval
;
3211 for (ctxval
= ctxlat
->values
; ctxval
; ctxval
= ctxval
->next
)
3212 topo
->contexts
.add_val (ctxval
);
3217 /* One pass of constants propagation along the call graph edges, from callers
3218 to callees (requires topological ordering in TOPO), iterate over strongly
3219 connected components. */
3222 propagate_constants_topo (class ipa_topo_info
*topo
)
3226 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
3229 struct cgraph_node
*v
, *node
= topo
->order
[i
];
3230 vec
<cgraph_node
*> cycle_nodes
= ipa_get_nodes_in_cycle (node
);
3232 /* First, iteratively propagate within the strongly connected component
3233 until all lattices stabilize. */
3234 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
3235 if (v
->has_gimple_body_p ())
3236 push_node_to_stack (topo
, v
);
3238 v
= pop_node_from_stack (topo
);
3241 struct cgraph_edge
*cs
;
3243 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3244 if (ipa_edge_within_scc (cs
))
3246 IPA_NODE_REF (v
)->node_within_scc
= true;
3247 if (propagate_constants_across_call (cs
))
3248 push_node_to_stack (topo
, cs
->callee
->function_symbol ());
3250 v
= pop_node_from_stack (topo
);
3253 /* Afterwards, propagate along edges leading out of the SCC, calculates
3254 the local effects of the discovered constants and all valid values to
3255 their topological sort. */
3256 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
3257 if (v
->has_gimple_body_p ())
3259 struct cgraph_edge
*cs
;
3261 estimate_local_effects (v
);
3262 add_all_node_vals_to_toposort (v
, topo
);
3263 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3264 if (!ipa_edge_within_scc (cs
))
3265 propagate_constants_across_call (cs
);
3267 cycle_nodes
.release ();
3272 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
3273 the bigger one if otherwise. */
3276 safe_add (int a
, int b
)
3278 if (a
> INT_MAX
/2 || b
> INT_MAX
/2)
3279 return a
> b
? a
: b
;
3285 /* Propagate the estimated effects of individual values along the topological
3286 from the dependent values to those they depend on. */
3288 template <typename valtype
>
3290 value_topo_info
<valtype
>::propagate_effects ()
3292 ipcp_value
<valtype
> *base
;
3294 for (base
= values_topo
; base
; base
= base
->topo_next
)
3296 ipcp_value_source
<valtype
> *src
;
3297 ipcp_value
<valtype
> *val
;
3298 int time
= 0, size
= 0;
3300 for (val
= base
; val
; val
= val
->scc_next
)
3302 time
= safe_add (time
,
3303 val
->local_time_benefit
+ val
->prop_time_benefit
);
3304 size
= safe_add (size
, val
->local_size_cost
+ val
->prop_size_cost
);
3307 for (val
= base
; val
; val
= val
->scc_next
)
3308 for (src
= val
->sources
; src
; src
= src
->next
)
3310 && src
->cs
->maybe_hot_p ())
3312 src
->val
->prop_time_benefit
= safe_add (time
,
3313 src
->val
->prop_time_benefit
);
3314 src
->val
->prop_size_cost
= safe_add (size
,
3315 src
->val
->prop_size_cost
);
3321 /* Propagate constants, polymorphic contexts and their effects from the
3322 summaries interprocedurally. */
3325 ipcp_propagate_stage (class ipa_topo_info
*topo
)
3327 struct cgraph_node
*node
;
3330 fprintf (dump_file
, "\n Propagating constants:\n\n");
3332 max_count
= profile_count::uninitialized ();
3334 FOR_EACH_DEFINED_FUNCTION (node
)
3336 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3338 determine_versionability (node
, info
);
3339 if (node
->has_gimple_body_p ())
3341 info
->lattices
= XCNEWVEC (class ipcp_param_lattices
,
3342 ipa_get_param_count (info
));
3343 initialize_node_lattices (node
);
3345 ipa_size_summary
*s
= ipa_size_summaries
->get (node
);
3346 if (node
->definition
&& !node
->alias
&& s
!= NULL
)
3347 overall_size
+= s
->self_size
;
3348 max_count
= max_count
.max (node
->count
.ipa ());
3351 max_new_size
= overall_size
;
3352 if (max_new_size
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
3353 max_new_size
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
3354 max_new_size
+= max_new_size
* PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH
) / 100 + 1;
3357 fprintf (dump_file
, "\noverall_size: %li, max_new_size: %li\n",
3358 overall_size
, max_new_size
);
3360 propagate_constants_topo (topo
);
3362 ipcp_verify_propagated_values ();
3363 topo
->constants
.propagate_effects ();
3364 topo
->contexts
.propagate_effects ();
3368 fprintf (dump_file
, "\nIPA lattices after all propagation:\n");
3369 print_all_lattices (dump_file
, (dump_flags
& TDF_DETAILS
), true);
3373 /* Discover newly direct outgoing edges from NODE which is a new clone with
3374 known KNOWN_CSTS and make them direct. */
3377 ipcp_discover_new_direct_edges (struct cgraph_node
*node
,
3378 vec
<tree
> known_csts
,
3379 vec
<ipa_polymorphic_call_context
>
3381 struct ipa_agg_replacement_value
*aggvals
)
3383 struct cgraph_edge
*ie
, *next_ie
;
3386 for (ie
= node
->indirect_calls
; ie
; ie
= next_ie
)
3391 next_ie
= ie
->next_callee
;
3392 target
= ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
3393 vNULL
, aggvals
, &speculative
);
3396 bool agg_contents
= ie
->indirect_info
->agg_contents
;
3397 bool polymorphic
= ie
->indirect_info
->polymorphic
;
3398 int param_index
= ie
->indirect_info
->param_index
;
3399 struct cgraph_edge
*cs
= ipa_make_edge_direct_to_target (ie
, target
,
3403 if (cs
&& !agg_contents
&& !polymorphic
)
3405 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3406 int c
= ipa_get_controlled_uses (info
, param_index
);
3407 if (c
!= IPA_UNDESCRIBED_USE
)
3409 struct ipa_ref
*to_del
;
3412 ipa_set_controlled_uses (info
, param_index
, c
);
3413 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3414 fprintf (dump_file
, " controlled uses count of param "
3415 "%i bumped down to %i\n", param_index
, c
);
3417 && (to_del
= node
->find_reference (cs
->callee
, NULL
, 0)))
3419 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3420 fprintf (dump_file
, " and even removing its "
3421 "cloning-created reference\n");
3422 to_del
->remove_reference ();
3428 /* Turning calls to direct calls will improve overall summary. */
3430 ipa_update_overall_fn_summary (node
);
3433 class edge_clone_summary
;
3434 static call_summary
<edge_clone_summary
*> *edge_clone_summaries
= NULL
;
3436 /* Edge clone summary. */
3438 class edge_clone_summary
3441 /* Default constructor. */
3442 edge_clone_summary (): prev_clone (NULL
), next_clone (NULL
) {}
3444 /* Default destructor. */
3445 ~edge_clone_summary ()
3448 edge_clone_summaries
->get (prev_clone
)->next_clone
= next_clone
;
3450 edge_clone_summaries
->get (next_clone
)->prev_clone
= prev_clone
;
3453 cgraph_edge
*prev_clone
;
3454 cgraph_edge
*next_clone
;
3457 class edge_clone_summary_t
:
3458 public call_summary
<edge_clone_summary
*>
3461 edge_clone_summary_t (symbol_table
*symtab
):
3462 call_summary
<edge_clone_summary
*> (symtab
)
3464 m_initialize_when_cloning
= true;
3467 virtual void duplicate (cgraph_edge
*src_edge
, cgraph_edge
*dst_edge
,
3468 edge_clone_summary
*src_data
,
3469 edge_clone_summary
*dst_data
);
3472 /* Edge duplication hook. */
3475 edge_clone_summary_t::duplicate (cgraph_edge
*src_edge
, cgraph_edge
*dst_edge
,
3476 edge_clone_summary
*src_data
,
3477 edge_clone_summary
*dst_data
)
3479 if (src_data
->next_clone
)
3480 edge_clone_summaries
->get (src_data
->next_clone
)->prev_clone
= dst_edge
;
3481 dst_data
->prev_clone
= src_edge
;
3482 dst_data
->next_clone
= src_data
->next_clone
;
3483 src_data
->next_clone
= dst_edge
;
3486 /* See if NODE is a clone with a known aggregate value at a given OFFSET of a
3487 parameter with the given INDEX. */
3490 get_clone_agg_value (struct cgraph_node
*node
, HOST_WIDE_INT offset
,
3493 struct ipa_agg_replacement_value
*aggval
;
3495 aggval
= ipa_get_agg_replacements_for_node (node
);
3498 if (aggval
->offset
== offset
3499 && aggval
->index
== index
)
3500 return aggval
->value
;
3501 aggval
= aggval
->next
;
3506 /* Return true is NODE is DEST or its clone for all contexts. */
3509 same_node_or_its_all_contexts_clone_p (cgraph_node
*node
, cgraph_node
*dest
)
3514 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3515 return info
->is_all_contexts_clone
&& info
->ipcp_orig_node
== dest
;
3518 /* Return true if edge CS does bring about the value described by SRC to
3519 DEST_VAL of node DEST or its clone for all contexts. */
3522 cgraph_edge_brings_value_p (cgraph_edge
*cs
, ipcp_value_source
<tree
> *src
,
3523 cgraph_node
*dest
, ipcp_value
<tree
> *dest_val
)
3525 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3526 enum availability availability
;
3527 cgraph_node
*real_dest
= cs
->callee
->function_symbol (&availability
);
3529 if (!same_node_or_its_all_contexts_clone_p (real_dest
, dest
)
3530 || availability
<= AVAIL_INTERPOSABLE
3531 || caller_info
->node_dead
)
3537 if (caller_info
->ipcp_orig_node
)
3540 if (src
->offset
== -1)
3541 t
= caller_info
->known_csts
[src
->index
];
3543 t
= get_clone_agg_value (cs
->caller
, src
->offset
, src
->index
);
3544 return (t
!= NULL_TREE
3545 && values_equal_for_ipcp_p (src
->val
->value
, t
));
3549 /* At the moment we do not propagate over arithmetic jump functions in
3550 SCCs, so it is safe to detect self-feeding recursive calls in this
3552 if (src
->val
== dest_val
)
3555 struct ipcp_agg_lattice
*aglat
;
3556 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
3558 if (src
->offset
== -1)
3559 return (plats
->itself
.is_single_const ()
3560 && values_equal_for_ipcp_p (src
->val
->value
,
3561 plats
->itself
.values
->value
));
3564 if (plats
->aggs_bottom
|| plats
->aggs_contain_variable
)
3566 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3567 if (aglat
->offset
== src
->offset
)
3568 return (aglat
->is_single_const ()
3569 && values_equal_for_ipcp_p (src
->val
->value
,
3570 aglat
->values
->value
));
3576 /* Return true if edge CS does bring about the value described by SRC to
3577 DST_VAL of node DEST or its clone for all contexts. */
3580 cgraph_edge_brings_value_p (cgraph_edge
*cs
,
3581 ipcp_value_source
<ipa_polymorphic_call_context
> *src
,
3583 ipcp_value
<ipa_polymorphic_call_context
> *)
3585 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3586 cgraph_node
*real_dest
= cs
->callee
->function_symbol ();
3588 if (!same_node_or_its_all_contexts_clone_p (real_dest
, dest
)
3589 || caller_info
->node_dead
)
3594 if (caller_info
->ipcp_orig_node
)
3595 return (caller_info
->known_contexts
.length () > (unsigned) src
->index
)
3596 && values_equal_for_ipcp_p (src
->val
->value
,
3597 caller_info
->known_contexts
[src
->index
]);
3599 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
3601 return plats
->ctxlat
.is_single_const ()
3602 && values_equal_for_ipcp_p (src
->val
->value
,
3603 plats
->ctxlat
.values
->value
);
3606 /* Get the next clone in the linked list of clones of an edge. */
3608 static inline struct cgraph_edge
*
3609 get_next_cgraph_edge_clone (struct cgraph_edge
*cs
)
3611 edge_clone_summary
*s
= edge_clone_summaries
->get (cs
);
3612 return s
!= NULL
? s
->next_clone
: NULL
;
3615 /* Given VAL that is intended for DEST, iterate over all its sources and if any
3616 of them is viable and hot, return true. In that case, for those that still
3617 hold, add their edge frequency and their number into *FREQUENCY and
3618 *CALLER_COUNT respectively. */
3620 template <typename valtype
>
3622 get_info_about_necessary_edges (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
3624 profile_count
*count_sum
, int *caller_count
)
3626 ipcp_value_source
<valtype
> *src
;
3627 int freq
= 0, count
= 0;
3628 profile_count cnt
= profile_count::zero ();
3630 bool non_self_recursive
= false;
3632 for (src
= val
->sources
; src
; src
= src
->next
)
3634 struct cgraph_edge
*cs
= src
->cs
;
3637 if (cgraph_edge_brings_value_p (cs
, src
, dest
, val
))
3640 freq
+= cs
->frequency ();
3641 if (cs
->count
.ipa ().initialized_p ())
3642 cnt
+= cs
->count
.ipa ();
3643 hot
|= cs
->maybe_hot_p ();
3644 if (cs
->caller
!= dest
)
3645 non_self_recursive
= true;
3647 cs
= get_next_cgraph_edge_clone (cs
);
3651 /* If the only edges bringing a value are self-recursive ones, do not bother
3653 if (!non_self_recursive
)
3658 *caller_count
= count
;
3662 /* Return a vector of incoming edges that do bring value VAL to node DEST. It
3663 is assumed their number is known and equal to CALLER_COUNT. */
3665 template <typename valtype
>
3666 static vec
<cgraph_edge
*>
3667 gather_edges_for_value (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
3670 ipcp_value_source
<valtype
> *src
;
3671 vec
<cgraph_edge
*> ret
;
3673 ret
.create (caller_count
);
3674 for (src
= val
->sources
; src
; src
= src
->next
)
3676 struct cgraph_edge
*cs
= src
->cs
;
3679 if (cgraph_edge_brings_value_p (cs
, src
, dest
, val
))
3680 ret
.quick_push (cs
);
3681 cs
= get_next_cgraph_edge_clone (cs
);
3688 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
3689 Return it or NULL if for some reason it cannot be created. */
3691 static struct ipa_replace_map
*
3692 get_replacement_map (class ipa_node_params
*info
, tree value
, int parm_num
)
3694 struct ipa_replace_map
*replace_map
;
3697 replace_map
= ggc_alloc
<ipa_replace_map
> ();
3700 fprintf (dump_file
, " replacing ");
3701 ipa_dump_param (dump_file
, info
, parm_num
);
3703 fprintf (dump_file
, " with const ");
3704 print_generic_expr (dump_file
, value
);
3705 fprintf (dump_file
, "\n");
3707 replace_map
->parm_num
= parm_num
;
3708 replace_map
->new_tree
= value
;
3712 /* Dump new profiling counts */
3715 dump_profile_updates (struct cgraph_node
*orig_node
,
3716 struct cgraph_node
*new_node
)
3718 struct cgraph_edge
*cs
;
3720 fprintf (dump_file
, " setting count of the specialized node to ");
3721 new_node
->count
.dump (dump_file
);
3722 fprintf (dump_file
, "\n");
3723 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3725 fprintf (dump_file
, " edge to %s has count ",
3726 cs
->callee
->name ());
3727 cs
->count
.dump (dump_file
);
3728 fprintf (dump_file
, "\n");
3731 fprintf (dump_file
, " setting count of the original node to ");
3732 orig_node
->count
.dump (dump_file
);
3733 fprintf (dump_file
, "\n");
3734 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3736 fprintf (dump_file
, " edge to %s is left with ",
3737 cs
->callee
->name ());
3738 cs
->count
.dump (dump_file
);
3739 fprintf (dump_file
, "\n");
3743 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
3744 their profile information to reflect this. */
3747 update_profiling_info (struct cgraph_node
*orig_node
,
3748 struct cgraph_node
*new_node
)
3750 struct cgraph_edge
*cs
;
3751 struct caller_statistics stats
;
3752 profile_count new_sum
, orig_sum
;
3753 profile_count remainder
, orig_node_count
= orig_node
->count
;
3755 if (!(orig_node_count
.ipa () > profile_count::zero ()))
3758 init_caller_stats (&stats
);
3759 orig_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
3761 orig_sum
= stats
.count_sum
;
3762 init_caller_stats (&stats
);
3763 new_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
3765 new_sum
= stats
.count_sum
;
3767 if (orig_node_count
< orig_sum
+ new_sum
)
3771 fprintf (dump_file
, " Problem: node %s has too low count ",
3772 orig_node
->dump_name ());
3773 orig_node_count
.dump (dump_file
);
3774 fprintf (dump_file
, "while the sum of incoming count is ");
3775 (orig_sum
+ new_sum
).dump (dump_file
);
3776 fprintf (dump_file
, "\n");
3779 orig_node_count
= (orig_sum
+ new_sum
).apply_scale (12, 10);
3782 fprintf (dump_file
, " proceeding by pretending it was ");
3783 orig_node_count
.dump (dump_file
);
3784 fprintf (dump_file
, "\n");
3788 remainder
= orig_node_count
.combine_with_ipa_count (orig_node_count
.ipa ()
3790 new_sum
= orig_node_count
.combine_with_ipa_count (new_sum
);
3791 orig_node
->count
= remainder
;
3793 profile_count::adjust_for_ipa_scaling (&new_sum
, &orig_node_count
);
3794 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3795 cs
->count
= cs
->count
.apply_scale (new_sum
, orig_node_count
);
3797 profile_count::adjust_for_ipa_scaling (&remainder
, &orig_node_count
);
3798 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3799 cs
->count
= cs
->count
.apply_scale (remainder
, orig_node_count
);
3802 dump_profile_updates (orig_node
, new_node
);
3805 /* Update the respective profile of specialized NEW_NODE and the original
3806 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
3807 have been redirected to the specialized version. */
3810 update_specialized_profile (struct cgraph_node
*new_node
,
3811 struct cgraph_node
*orig_node
,
3812 profile_count redirected_sum
)
3814 struct cgraph_edge
*cs
;
3815 profile_count new_node_count
, orig_node_count
= orig_node
->count
;
3819 fprintf (dump_file
, " the sum of counts of redirected edges is ");
3820 redirected_sum
.dump (dump_file
);
3821 fprintf (dump_file
, "\n");
3823 if (!(orig_node_count
> profile_count::zero ()))
3826 gcc_assert (orig_node_count
>= redirected_sum
);
3828 new_node_count
= new_node
->count
;
3829 new_node
->count
+= redirected_sum
;
3830 orig_node
->count
-= redirected_sum
;
3832 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3833 cs
->count
+= cs
->count
.apply_scale (redirected_sum
, new_node_count
);
3835 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3837 profile_count dec
= cs
->count
.apply_scale (redirected_sum
,
3843 dump_profile_updates (orig_node
, new_node
);
3846 /* Return true if we would like to remove a parameter from NODE when cloning it
3847 with KNOWN_CSTS scalar constants. */
3850 want_remove_some_param_p (cgraph_node
*node
, vec
<tree
> known_csts
)
3852 auto_vec
<bool, 16> surviving
;
3853 bool filled_vec
= false;
3854 ipa_node_params
*info
= IPA_NODE_REF (node
);
3855 int i
, count
= ipa_get_param_count (info
);
3857 for (i
= 0; i
< count
; i
++)
3859 if (!known_csts
[i
] && ipa_is_param_used (info
, i
))
3864 if (!node
->clone
.param_adjustments
)
3866 node
->clone
.param_adjustments
->get_surviving_params (&surviving
);
3869 if (surviving
.length() < (unsigned) i
&& surviving
[i
])
3875 /* Create a specialized version of NODE with known constants in KNOWN_CSTS,
3876 known contexts in KNOWN_CONTEXTS and known aggregate values in AGGVALS and
3877 redirect all edges in CALLERS to it. */
3879 static struct cgraph_node
*
3880 create_specialized_node (struct cgraph_node
*node
,
3881 vec
<tree
> known_csts
,
3882 vec
<ipa_polymorphic_call_context
> known_contexts
,
3883 struct ipa_agg_replacement_value
*aggvals
,
3884 vec
<cgraph_edge
*> callers
)
3886 class ipa_node_params
*new_info
, *info
= IPA_NODE_REF (node
);
3887 vec
<ipa_replace_map
*, va_gc
> *replace_trees
= NULL
;
3888 vec
<ipa_adjusted_param
, va_gc
> *new_params
= NULL
;
3889 struct ipa_agg_replacement_value
*av
;
3890 struct cgraph_node
*new_node
;
3891 int i
, count
= ipa_get_param_count (info
);
3892 ipa_param_adjustments
*old_adjustments
= node
->clone
.param_adjustments
;
3893 ipa_param_adjustments
*new_adjustments
;
3894 gcc_assert (!info
->ipcp_orig_node
);
3895 gcc_assert (node
->can_change_signature
3896 || !old_adjustments
);
3898 if (old_adjustments
)
3900 /* At the moment all IPA optimizations should use the number of
3901 parameters of the prevailing decl as the m_always_copy_start.
3902 Handling any other value would complicate the code below, so for the
3903 time bing let's only assert it is so. */
3904 gcc_assert (old_adjustments
->m_always_copy_start
== count
3905 || old_adjustments
->m_always_copy_start
< 0);
3906 int old_adj_count
= vec_safe_length (old_adjustments
->m_adj_params
);
3907 for (i
= 0; i
< old_adj_count
; i
++)
3909 ipa_adjusted_param
*old_adj
= &(*old_adjustments
->m_adj_params
)[i
];
3910 if (!node
->can_change_signature
3911 || old_adj
->op
!= IPA_PARAM_OP_COPY
3912 || (!known_csts
[old_adj
->base_index
]
3913 && ipa_is_param_used (info
, old_adj
->base_index
)))
3915 ipa_adjusted_param new_adj
= *old_adj
;
3917 new_adj
.prev_clone_adjustment
= true;
3918 new_adj
.prev_clone_index
= i
;
3919 vec_safe_push (new_params
, new_adj
);
3922 bool skip_return
= old_adjustments
->m_skip_return
;
3923 new_adjustments
= (new (ggc_alloc
<ipa_param_adjustments
> ())
3924 ipa_param_adjustments (new_params
, count
,
3927 else if (node
->can_change_signature
3928 && want_remove_some_param_p (node
, known_csts
))
3930 ipa_adjusted_param adj
;
3931 memset (&adj
, 0, sizeof (adj
));
3932 adj
.op
= IPA_PARAM_OP_COPY
;
3933 for (i
= 0; i
< count
; i
++)
3934 if (!known_csts
[i
] && ipa_is_param_used (info
, i
))
3937 adj
.prev_clone_index
= i
;
3938 vec_safe_push (new_params
, adj
);
3940 new_adjustments
= (new (ggc_alloc
<ipa_param_adjustments
> ())
3941 ipa_param_adjustments (new_params
, count
, false));
3944 new_adjustments
= NULL
;
3946 replace_trees
= vec_safe_copy (node
->clone
.tree_map
);
3947 for (i
= 0; i
< count
; i
++)
3949 tree t
= known_csts
[i
];
3952 struct ipa_replace_map
*replace_map
;
3954 gcc_checking_assert (TREE_CODE (t
) != TREE_BINFO
);
3955 replace_map
= get_replacement_map (info
, t
, i
);
3957 vec_safe_push (replace_trees
, replace_map
);
3960 auto_vec
<cgraph_edge
*, 2> self_recursive_calls
;
3961 for (i
= callers
.length () - 1; i
>= 0; i
--)
3963 cgraph_edge
*cs
= callers
[i
];
3964 if (cs
->caller
== node
)
3966 self_recursive_calls
.safe_push (cs
);
3967 callers
.unordered_remove (i
);
3971 unsigned &suffix_counter
= clone_num_suffixes
->get_or_insert (
3972 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (
3974 new_node
= node
->create_virtual_clone (callers
, replace_trees
,
3975 new_adjustments
, "constprop",
3979 bool have_self_recursive_calls
= !self_recursive_calls
.is_empty ();
3980 for (unsigned j
= 0; j
< self_recursive_calls
.length (); j
++)
3982 cgraph_edge
*cs
= get_next_cgraph_edge_clone (self_recursive_calls
[j
]);
3983 /* Cloned edges can disappear during cloning as speculation can be
3984 resolved, check that we have one and that it comes from the last
3986 if (cs
&& cs
->caller
== new_node
)
3987 cs
->redirect_callee_duplicating_thunks (new_node
);
3988 /* Any future code that would make more than one clone of an outgoing
3989 edge would confuse this mechanism, so let's check that does not
3991 gcc_checking_assert (!cs
3992 || !get_next_cgraph_edge_clone (cs
)
3993 || get_next_cgraph_edge_clone (cs
)->caller
!= new_node
);
3995 if (have_self_recursive_calls
)
3996 new_node
->expand_all_artificial_thunks ();
3998 ipa_set_node_agg_value_chain (new_node
, aggvals
);
3999 for (av
= aggvals
; av
; av
= av
->next
)
4000 new_node
->maybe_create_reference (av
->value
, NULL
);
4002 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4004 fprintf (dump_file
, " the new node is %s.\n", new_node
->dump_name ());
4005 if (known_contexts
.exists ())
4007 for (i
= 0; i
< count
; i
++)
4008 if (!known_contexts
[i
].useless_p ())
4010 fprintf (dump_file
, " known ctx %i is ", i
);
4011 known_contexts
[i
].dump (dump_file
);
4015 ipa_dump_agg_replacement_values (dump_file
, aggvals
);
4017 ipa_check_create_node_params ();
4018 update_profiling_info (node
, new_node
);
4019 new_info
= IPA_NODE_REF (new_node
);
4020 new_info
->ipcp_orig_node
= node
;
4021 new_info
->known_csts
= known_csts
;
4022 new_info
->known_contexts
= known_contexts
;
4024 ipcp_discover_new_direct_edges (new_node
, known_csts
, known_contexts
, aggvals
);
4030 /* Return true, if JFUNC, which describes a i-th parameter of call CS, is a
4031 simple no-operation pass-through function to itself. */
4034 self_recursive_pass_through_p (cgraph_edge
*cs
, ipa_jump_func
*jfunc
, int i
)
4036 enum availability availability
;
4037 if (cs
->caller
== cs
->callee
->function_symbol (&availability
)
4038 && availability
> AVAIL_INTERPOSABLE
4039 && jfunc
->type
== IPA_JF_PASS_THROUGH
4040 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
4041 && ipa_get_jf_pass_through_formal_id (jfunc
) == i
)
4046 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
4047 KNOWN_CSTS with constants that are also known for all of the CALLERS. */
4050 find_more_scalar_values_for_callers_subset (struct cgraph_node
*node
,
4051 vec
<tree
> known_csts
,
4052 vec
<cgraph_edge
*> callers
)
4054 class ipa_node_params
*info
= IPA_NODE_REF (node
);
4055 int i
, count
= ipa_get_param_count (info
);
4057 for (i
= 0; i
< count
; i
++)
4059 struct cgraph_edge
*cs
;
4060 tree newval
= NULL_TREE
;
4063 tree type
= ipa_get_type (info
, i
);
4065 if (ipa_get_scalar_lat (info
, i
)->bottom
|| known_csts
[i
])
4068 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4070 struct ipa_jump_func
*jump_func
;
4073 if (IPA_NODE_REF (cs
->caller
)->node_dead
)
4076 if (!IPA_EDGE_REF (cs
)
4077 || i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
))
4079 && call_passes_through_thunk_p (cs
)))
4084 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
4085 if (self_recursive_pass_through_p (cs
, jump_func
, i
))
4088 t
= ipa_value_from_jfunc (IPA_NODE_REF (cs
->caller
), jump_func
, type
);
4091 && !values_equal_for_ipcp_p (t
, newval
))
4092 || (!first
&& !newval
))
4104 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4106 fprintf (dump_file
, " adding an extra known scalar value ");
4107 print_ipcp_constant_value (dump_file
, newval
);
4108 fprintf (dump_file
, " for ");
4109 ipa_dump_param (dump_file
, info
, i
);
4110 fprintf (dump_file
, "\n");
4113 known_csts
[i
] = newval
;
4118 /* Given a NODE and a subset of its CALLERS, try to populate plank slots in
4119 KNOWN_CONTEXTS with polymorphic contexts that are also known for all of the
4123 find_more_contexts_for_caller_subset (cgraph_node
*node
,
4124 vec
<ipa_polymorphic_call_context
>
4126 vec
<cgraph_edge
*> callers
)
4128 ipa_node_params
*info
= IPA_NODE_REF (node
);
4129 int i
, count
= ipa_get_param_count (info
);
4131 for (i
= 0; i
< count
; i
++)
4135 if (ipa_get_poly_ctx_lat (info
, i
)->bottom
4136 || (known_contexts
->exists ()
4137 && !(*known_contexts
)[i
].useless_p ()))
4140 ipa_polymorphic_call_context newval
;
4144 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4146 if (!IPA_EDGE_REF (cs
)
4147 || i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
)))
4149 ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
),
4151 ipa_polymorphic_call_context ctx
;
4152 ctx
= ipa_context_from_jfunc (IPA_NODE_REF (cs
->caller
), cs
, i
,
4160 newval
.meet_with (ctx
);
4161 if (newval
.useless_p ())
4165 if (!newval
.useless_p ())
4167 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4169 fprintf (dump_file
, " adding an extra known polymorphic "
4171 print_ipcp_constant_value (dump_file
, newval
);
4172 fprintf (dump_file
, " for ");
4173 ipa_dump_param (dump_file
, info
, i
);
4174 fprintf (dump_file
, "\n");
4177 if (!known_contexts
->exists ())
4178 known_contexts
->safe_grow_cleared (ipa_get_param_count (info
));
4179 (*known_contexts
)[i
] = newval
;
4185 /* Go through PLATS and create a vector of values consisting of values and
4186 offsets (minus OFFSET) of lattices that contain only a single value. */
4188 static vec
<ipa_agg_jf_item
>
4189 copy_plats_to_inter (class ipcp_param_lattices
*plats
, HOST_WIDE_INT offset
)
4191 vec
<ipa_agg_jf_item
> res
= vNULL
;
4193 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
4196 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
4197 if (aglat
->is_single_const ())
4199 struct ipa_agg_jf_item ti
;
4200 ti
.offset
= aglat
->offset
- offset
;
4201 ti
.value
= aglat
->values
->value
;
4207 /* Intersect all values in INTER with single value lattices in PLATS (while
4208 subtracting OFFSET). */
4211 intersect_with_plats (class ipcp_param_lattices
*plats
,
4212 vec
<ipa_agg_jf_item
> *inter
,
4213 HOST_WIDE_INT offset
)
4215 struct ipcp_agg_lattice
*aglat
;
4216 struct ipa_agg_jf_item
*item
;
4219 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
4225 aglat
= plats
->aggs
;
4226 FOR_EACH_VEC_ELT (*inter
, k
, item
)
4233 if (aglat
->offset
- offset
> item
->offset
)
4235 if (aglat
->offset
- offset
== item
->offset
)
4237 gcc_checking_assert (item
->value
);
4238 if (aglat
->is_single_const ()
4239 && values_equal_for_ipcp_p (item
->value
,
4240 aglat
->values
->value
))
4244 aglat
= aglat
->next
;
4247 item
->value
= NULL_TREE
;
4251 /* Copy aggregate replacement values of NODE (which is an IPA-CP clone) to the
4252 vector result while subtracting OFFSET from the individual value offsets. */
4254 static vec
<ipa_agg_jf_item
>
4255 agg_replacements_to_vector (struct cgraph_node
*node
, int index
,
4256 HOST_WIDE_INT offset
)
4258 struct ipa_agg_replacement_value
*av
;
4259 vec
<ipa_agg_jf_item
> res
= vNULL
;
4261 for (av
= ipa_get_agg_replacements_for_node (node
); av
; av
= av
->next
)
4262 if (av
->index
== index
4263 && (av
->offset
- offset
) >= 0)
4265 struct ipa_agg_jf_item item
;
4266 gcc_checking_assert (av
->value
);
4267 item
.offset
= av
->offset
- offset
;
4268 item
.value
= av
->value
;
4269 res
.safe_push (item
);
4275 /* Intersect all values in INTER with those that we have already scheduled to
4276 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
4277 (while subtracting OFFSET). */
4280 intersect_with_agg_replacements (struct cgraph_node
*node
, int index
,
4281 vec
<ipa_agg_jf_item
> *inter
,
4282 HOST_WIDE_INT offset
)
4284 struct ipa_agg_replacement_value
*srcvals
;
4285 struct ipa_agg_jf_item
*item
;
4288 srcvals
= ipa_get_agg_replacements_for_node (node
);
4295 FOR_EACH_VEC_ELT (*inter
, i
, item
)
4297 struct ipa_agg_replacement_value
*av
;
4301 for (av
= srcvals
; av
; av
= av
->next
)
4303 gcc_checking_assert (av
->value
);
4304 if (av
->index
== index
4305 && av
->offset
- offset
== item
->offset
)
4307 if (values_equal_for_ipcp_p (item
->value
, av
->value
))
4313 item
->value
= NULL_TREE
;
4317 /* Intersect values in INTER with aggregate values that come along edge CS to
4318 parameter number INDEX and return it. If INTER does not actually exist yet,
4319 copy all incoming values to it. If we determine we ended up with no values
4320 whatsoever, return a released vector. */
4322 static vec
<ipa_agg_jf_item
>
4323 intersect_aggregates_with_edge (struct cgraph_edge
*cs
, int index
,
4324 vec
<ipa_agg_jf_item
> inter
)
4326 struct ipa_jump_func
*jfunc
;
4327 jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), index
);
4328 if (jfunc
->type
== IPA_JF_PASS_THROUGH
4329 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
4331 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4332 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
4334 if (caller_info
->ipcp_orig_node
)
4336 struct cgraph_node
*orig_node
= caller_info
->ipcp_orig_node
;
4337 class ipcp_param_lattices
*orig_plats
;
4338 orig_plats
= ipa_get_parm_lattices (IPA_NODE_REF (orig_node
),
4340 if (agg_pass_through_permissible_p (orig_plats
, jfunc
))
4342 if (!inter
.exists ())
4343 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, 0);
4345 intersect_with_agg_replacements (cs
->caller
, src_idx
,
4356 class ipcp_param_lattices
*src_plats
;
4357 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
4358 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
4360 /* Currently we do not produce clobber aggregate jump
4361 functions, adjust when we do. */
4362 gcc_checking_assert (!jfunc
->agg
.items
);
4363 if (!inter
.exists ())
4364 inter
= copy_plats_to_inter (src_plats
, 0);
4366 intersect_with_plats (src_plats
, &inter
, 0);
4375 else if (jfunc
->type
== IPA_JF_ANCESTOR
4376 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
4378 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4379 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
4380 class ipcp_param_lattices
*src_plats
;
4381 HOST_WIDE_INT delta
= ipa_get_jf_ancestor_offset (jfunc
);
4383 if (caller_info
->ipcp_orig_node
)
4385 if (!inter
.exists ())
4386 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, delta
);
4388 intersect_with_agg_replacements (cs
->caller
, src_idx
, &inter
,
4393 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
4394 /* Currently we do not produce clobber aggregate jump
4395 functions, adjust when we do. */
4396 gcc_checking_assert (!src_plats
->aggs
|| !jfunc
->agg
.items
);
4397 if (!inter
.exists ())
4398 inter
= copy_plats_to_inter (src_plats
, delta
);
4400 intersect_with_plats (src_plats
, &inter
, delta
);
4403 else if (jfunc
->agg
.items
)
4405 struct ipa_agg_jf_item
*item
;
4408 if (!inter
.exists ())
4409 for (unsigned i
= 0; i
< jfunc
->agg
.items
->length (); i
++)
4410 inter
.safe_push ((*jfunc
->agg
.items
)[i
]);
4412 FOR_EACH_VEC_ELT (inter
, k
, item
)
4420 while ((unsigned) l
< jfunc
->agg
.items
->length ())
4422 struct ipa_agg_jf_item
*ti
;
4423 ti
= &(*jfunc
->agg
.items
)[l
];
4424 if (ti
->offset
> item
->offset
)
4426 if (ti
->offset
== item
->offset
)
4428 gcc_checking_assert (ti
->value
);
4429 if (values_equal_for_ipcp_p (item
->value
,
4443 return vec
<ipa_agg_jf_item
>();
4448 /* Look at edges in CALLERS and collect all known aggregate values that arrive
4449 from all of them. */
4451 static struct ipa_agg_replacement_value
*
4452 find_aggregate_values_for_callers_subset (struct cgraph_node
*node
,
4453 vec
<cgraph_edge
*> callers
)
4455 class ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
4456 struct ipa_agg_replacement_value
*res
;
4457 struct ipa_agg_replacement_value
**tail
= &res
;
4458 struct cgraph_edge
*cs
;
4459 int i
, j
, count
= ipa_get_param_count (dest_info
);
4461 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4463 if (!IPA_EDGE_REF (cs
))
4468 int c
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
4473 for (i
= 0; i
< count
; i
++)
4475 struct cgraph_edge
*cs
;
4476 vec
<ipa_agg_jf_item
> inter
= vNULL
;
4477 struct ipa_agg_jf_item
*item
;
4478 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (dest_info
, i
);
4481 /* Among other things, the following check should deal with all by_ref
4483 if (plats
->aggs_bottom
)
4486 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4488 struct ipa_jump_func
*jfunc
4489 = ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
4490 if (self_recursive_pass_through_p (cs
, jfunc
, i
)
4491 && (!plats
->aggs_by_ref
4492 || ipa_get_jf_pass_through_agg_preserved (jfunc
)))
4494 inter
= intersect_aggregates_with_edge (cs
, i
, inter
);
4496 if (!inter
.exists ())
4500 FOR_EACH_VEC_ELT (inter
, j
, item
)
4502 struct ipa_agg_replacement_value
*v
;
4507 v
= ggc_alloc
<ipa_agg_replacement_value
> ();
4509 v
->offset
= item
->offset
;
4510 v
->value
= item
->value
;
4511 v
->by_ref
= plats
->aggs_by_ref
;
4517 if (inter
.exists ())
4524 /* Determine whether CS also brings all scalar values that the NODE is
4528 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge
*cs
,
4529 struct cgraph_node
*node
)
4531 class ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
4532 int count
= ipa_get_param_count (dest_info
);
4533 class ipa_node_params
*caller_info
;
4534 class ipa_edge_args
*args
;
4537 caller_info
= IPA_NODE_REF (cs
->caller
);
4538 args
= IPA_EDGE_REF (cs
);
4539 for (i
= 0; i
< count
; i
++)
4541 struct ipa_jump_func
*jump_func
;
4544 val
= dest_info
->known_csts
[i
];
4548 if (i
>= ipa_get_cs_argument_count (args
))
4550 jump_func
= ipa_get_ith_jump_func (args
, i
);
4551 t
= ipa_value_from_jfunc (caller_info
, jump_func
,
4552 ipa_get_type (dest_info
, i
));
4553 if (!t
|| !values_equal_for_ipcp_p (val
, t
))
4559 /* Determine whether CS also brings all aggregate values that NODE is
4562 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge
*cs
,
4563 struct cgraph_node
*node
)
4565 class ipa_node_params
*orig_node_info
;
4566 struct ipa_agg_replacement_value
*aggval
;
4569 aggval
= ipa_get_agg_replacements_for_node (node
);
4573 count
= ipa_get_param_count (IPA_NODE_REF (node
));
4574 ec
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
4576 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4577 if (aggval
->index
>= ec
)
4580 orig_node_info
= IPA_NODE_REF (IPA_NODE_REF (node
)->ipcp_orig_node
);
4582 for (i
= 0; i
< count
; i
++)
4584 static vec
<ipa_agg_jf_item
> values
= vec
<ipa_agg_jf_item
>();
4585 class ipcp_param_lattices
*plats
;
4586 bool interesting
= false;
4587 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4588 if (aggval
->index
== i
)
4596 plats
= ipa_get_parm_lattices (orig_node_info
, aggval
->index
);
4597 if (plats
->aggs_bottom
)
4600 values
= intersect_aggregates_with_edge (cs
, i
, values
);
4601 if (!values
.exists ())
4604 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4605 if (aggval
->index
== i
)
4607 struct ipa_agg_jf_item
*item
;
4610 FOR_EACH_VEC_ELT (values
, j
, item
)
4612 && item
->offset
== av
->offset
4613 && values_equal_for_ipcp_p (item
->value
, av
->value
))
4628 /* Given an original NODE and a VAL for which we have already created a
4629 specialized clone, look whether there are incoming edges that still lead
4630 into the old node but now also bring the requested value and also conform to
4631 all other criteria such that they can be redirected the special node.
4632 This function can therefore redirect the final edge in a SCC. */
4634 template <typename valtype
>
4636 perhaps_add_new_callers (cgraph_node
*node
, ipcp_value
<valtype
> *val
)
4638 ipcp_value_source
<valtype
> *src
;
4639 profile_count redirected_sum
= profile_count::zero ();
4641 for (src
= val
->sources
; src
; src
= src
->next
)
4643 struct cgraph_edge
*cs
= src
->cs
;
4646 if (cgraph_edge_brings_value_p (cs
, src
, node
, val
)
4647 && cgraph_edge_brings_all_scalars_for_node (cs
, val
->spec_node
)
4648 && cgraph_edge_brings_all_agg_vals_for_node (cs
, val
->spec_node
))
4651 fprintf (dump_file
, " - adding an extra caller %s of %s\n",
4652 cs
->caller
->dump_name (),
4653 val
->spec_node
->dump_name ());
4655 cs
->redirect_callee_duplicating_thunks (val
->spec_node
);
4656 val
->spec_node
->expand_all_artificial_thunks ();
4657 if (cs
->count
.ipa ().initialized_p ())
4658 redirected_sum
= redirected_sum
+ cs
->count
.ipa ();
4660 cs
= get_next_cgraph_edge_clone (cs
);
4664 if (redirected_sum
.nonzero_p ())
4665 update_specialized_profile (val
->spec_node
, node
, redirected_sum
);
4668 /* Return true if KNOWN_CONTEXTS contain at least one useful context. */
4671 known_contexts_useful_p (vec
<ipa_polymorphic_call_context
> known_contexts
)
4673 ipa_polymorphic_call_context
*ctx
;
4676 FOR_EACH_VEC_ELT (known_contexts
, i
, ctx
)
4677 if (!ctx
->useless_p ())
4682 /* Return a copy of KNOWN_CSTS if it is not empty, otherwise return vNULL. */
4684 static vec
<ipa_polymorphic_call_context
>
4685 copy_useful_known_contexts (vec
<ipa_polymorphic_call_context
> known_contexts
)
4687 if (known_contexts_useful_p (known_contexts
))
4688 return known_contexts
.copy ();
4693 /* Copy KNOWN_CSTS and modify the copy according to VAL and INDEX. If
4694 non-empty, replace KNOWN_CONTEXTS with its copy too. */
4697 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
4698 vec
<ipa_polymorphic_call_context
> *known_contexts
,
4699 ipcp_value
<tree
> *val
,
4702 *known_csts
= known_csts
->copy ();
4703 *known_contexts
= copy_useful_known_contexts (*known_contexts
);
4704 (*known_csts
)[index
] = val
->value
;
4707 /* Replace KNOWN_CSTS with its copy. Also copy KNOWN_CONTEXTS and modify the
4708 copy according to VAL and INDEX. */
4711 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
4712 vec
<ipa_polymorphic_call_context
> *known_contexts
,
4713 ipcp_value
<ipa_polymorphic_call_context
> *val
,
4716 *known_csts
= known_csts
->copy ();
4717 *known_contexts
= known_contexts
->copy ();
4718 (*known_contexts
)[index
] = val
->value
;
4721 /* Return true if OFFSET indicates this was not an aggregate value or there is
4722 a replacement equivalent to VALUE, INDEX and OFFSET among those in the
4726 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*aggvals
,
4727 int index
, HOST_WIDE_INT offset
, tree value
)
4734 if (aggvals
->index
== index
4735 && aggvals
->offset
== offset
4736 && values_equal_for_ipcp_p (aggvals
->value
, value
))
4738 aggvals
= aggvals
->next
;
4743 /* Return true if offset is minus one because source of a polymorphic context
4744 cannot be an aggregate value. */
4747 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*,
4748 int , HOST_WIDE_INT offset
,
4749 ipa_polymorphic_call_context
)
4751 return offset
== -1;
4754 /* Decide whether to create a special version of NODE for value VAL of parameter
4755 at the given INDEX. If OFFSET is -1, the value is for the parameter itself,
4756 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS,
4757 KNOWN_CONTEXTS and KNOWN_AGGS describe the other already known values. */
4759 template <typename valtype
>
4761 decide_about_value (struct cgraph_node
*node
, int index
, HOST_WIDE_INT offset
,
4762 ipcp_value
<valtype
> *val
, vec
<tree
> known_csts
,
4763 vec
<ipa_polymorphic_call_context
> known_contexts
)
4765 struct ipa_agg_replacement_value
*aggvals
;
4766 int freq_sum
, caller_count
;
4767 profile_count count_sum
;
4768 vec
<cgraph_edge
*> callers
;
4772 perhaps_add_new_callers (node
, val
);
4775 else if (val
->local_size_cost
+ overall_size
> max_new_size
)
4777 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4778 fprintf (dump_file
, " Ignoring candidate value because "
4779 "max_new_size would be reached with %li.\n",
4780 val
->local_size_cost
+ overall_size
);
4783 else if (!get_info_about_necessary_edges (val
, node
, &freq_sum
, &count_sum
,
4787 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4789 fprintf (dump_file
, " - considering value ");
4790 print_ipcp_constant_value (dump_file
, val
->value
);
4791 fprintf (dump_file
, " for ");
4792 ipa_dump_param (dump_file
, IPA_NODE_REF (node
), index
);
4794 fprintf (dump_file
, ", offset: " HOST_WIDE_INT_PRINT_DEC
, offset
);
4795 fprintf (dump_file
, " (caller_count: %i)\n", caller_count
);
4798 if (!good_cloning_opportunity_p (node
, val
->local_time_benefit
,
4799 freq_sum
, count_sum
,
4800 val
->local_size_cost
)
4801 && !good_cloning_opportunity_p (node
,
4802 val
->local_time_benefit
4803 + val
->prop_time_benefit
,
4804 freq_sum
, count_sum
,
4805 val
->local_size_cost
4806 + val
->prop_size_cost
))
4810 fprintf (dump_file
, " Creating a specialized node of %s.\n",
4811 node
->dump_name ());
4813 callers
= gather_edges_for_value (val
, node
, caller_count
);
4815 modify_known_vectors_with_val (&known_csts
, &known_contexts
, val
, index
);
4818 known_csts
= known_csts
.copy ();
4819 known_contexts
= copy_useful_known_contexts (known_contexts
);
4821 find_more_scalar_values_for_callers_subset (node
, known_csts
, callers
);
4822 find_more_contexts_for_caller_subset (node
, &known_contexts
, callers
);
4823 aggvals
= find_aggregate_values_for_callers_subset (node
, callers
);
4824 gcc_checking_assert (ipcp_val_agg_replacement_ok_p (aggvals
, index
,
4825 offset
, val
->value
));
4826 val
->spec_node
= create_specialized_node (node
, known_csts
, known_contexts
,
4828 overall_size
+= val
->local_size_cost
;
4830 /* TODO: If for some lattice there is only one other known value
4831 left, make a special node for it too. */
4836 /* Decide whether and what specialized clones of NODE should be created. */
4839 decide_whether_version_node (struct cgraph_node
*node
)
4841 class ipa_node_params
*info
= IPA_NODE_REF (node
);
4842 int i
, count
= ipa_get_param_count (info
);
4843 vec
<tree
> known_csts
;
4844 vec
<ipa_polymorphic_call_context
> known_contexts
;
4845 vec
<ipa_agg_jump_function
> known_aggs
= vNULL
;
4851 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4852 fprintf (dump_file
, "\nEvaluating opportunities for %s.\n",
4853 node
->dump_name ());
4855 gather_context_independent_values (info
, &known_csts
, &known_contexts
,
4856 info
->do_clone_for_all_contexts
? &known_aggs
4859 for (i
= 0; i
< count
;i
++)
4861 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4862 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
4863 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
4868 ipcp_value
<tree
> *val
;
4869 for (val
= lat
->values
; val
; val
= val
->next
)
4870 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
4874 if (!plats
->aggs_bottom
)
4876 struct ipcp_agg_lattice
*aglat
;
4877 ipcp_value
<tree
> *val
;
4878 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
4879 if (!aglat
->bottom
&& aglat
->values
4880 /* If the following is false, the one value is in
4882 && (plats
->aggs_contain_variable
4883 || !aglat
->is_single_const ()))
4884 for (val
= aglat
->values
; val
; val
= val
->next
)
4885 ret
|= decide_about_value (node
, i
, aglat
->offset
, val
,
4886 known_csts
, known_contexts
);
4890 && known_contexts
[i
].useless_p ())
4892 ipcp_value
<ipa_polymorphic_call_context
> *val
;
4893 for (val
= ctxlat
->values
; val
; val
= val
->next
)
4894 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
4898 info
= IPA_NODE_REF (node
);
4901 if (info
->do_clone_for_all_contexts
)
4903 struct cgraph_node
*clone
;
4904 vec
<cgraph_edge
*> callers
;
4907 fprintf (dump_file
, " - Creating a specialized node of %s "
4908 "for all known contexts.\n", node
->dump_name ());
4910 callers
= node
->collect_callers ();
4911 find_more_scalar_values_for_callers_subset (node
, known_csts
, callers
);
4912 find_more_contexts_for_caller_subset (node
, &known_contexts
, callers
);
4913 ipa_agg_replacement_value
*aggvals
4914 = find_aggregate_values_for_callers_subset (node
, callers
);
4916 if (!known_contexts_useful_p (known_contexts
))
4918 known_contexts
.release ();
4919 known_contexts
= vNULL
;
4921 clone
= create_specialized_node (node
, known_csts
, known_contexts
,
4923 info
= IPA_NODE_REF (node
);
4924 info
->do_clone_for_all_contexts
= false;
4925 IPA_NODE_REF (clone
)->is_all_contexts_clone
= true;
4926 for (i
= 0; i
< count
; i
++)
4927 vec_free (known_aggs
[i
].items
);
4928 known_aggs
.release ();
4933 known_csts
.release ();
4934 known_contexts
.release ();
4940 /* Transitively mark all callees of NODE within the same SCC as not dead. */
4943 spread_undeadness (struct cgraph_node
*node
)
4945 struct cgraph_edge
*cs
;
4947 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
4948 if (ipa_edge_within_scc (cs
))
4950 struct cgraph_node
*callee
;
4951 class ipa_node_params
*info
;
4953 callee
= cs
->callee
->function_symbol (NULL
);
4954 info
= IPA_NODE_REF (callee
);
4956 if (info
->node_dead
)
4958 info
->node_dead
= 0;
4959 spread_undeadness (callee
);
4964 /* Return true if NODE has a caller from outside of its SCC that is not
4965 dead. Worker callback for cgraph_for_node_and_aliases. */
4968 has_undead_caller_from_outside_scc_p (struct cgraph_node
*node
,
4969 void *data ATTRIBUTE_UNUSED
)
4971 struct cgraph_edge
*cs
;
4973 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
4974 if (cs
->caller
->thunk
.thunk_p
4975 && cs
->caller
->call_for_symbol_thunks_and_aliases
4976 (has_undead_caller_from_outside_scc_p
, NULL
, true))
4978 else if (!ipa_edge_within_scc (cs
)
4979 && !IPA_NODE_REF (cs
->caller
)->node_dead
)
4985 /* Identify nodes within the same SCC as NODE which are no longer needed
4986 because of new clones and will be removed as unreachable. */
4989 identify_dead_nodes (struct cgraph_node
*node
)
4991 struct cgraph_node
*v
;
4992 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4994 && !v
->call_for_symbol_thunks_and_aliases
4995 (has_undead_caller_from_outside_scc_p
, NULL
, true))
4996 IPA_NODE_REF (v
)->node_dead
= 1;
4998 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4999 if (!IPA_NODE_REF (v
)->node_dead
)
5000 spread_undeadness (v
);
5002 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5004 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
5005 if (IPA_NODE_REF (v
)->node_dead
)
5006 fprintf (dump_file
, " Marking node as dead: %s.\n", v
->dump_name ());
5010 /* The decision stage. Iterate over the topological order of call graph nodes
5011 TOPO and make specialized clones if deemed beneficial. */
5014 ipcp_decision_stage (class ipa_topo_info
*topo
)
5019 fprintf (dump_file
, "\nIPA decision stage:\n\n");
5021 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
5023 struct cgraph_node
*node
= topo
->order
[i
];
5024 bool change
= false, iterate
= true;
5028 struct cgraph_node
*v
;
5030 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
5031 if (v
->has_gimple_body_p ()
5032 && ipcp_versionable_function_p (v
))
5033 iterate
|= decide_whether_version_node (v
);
5038 identify_dead_nodes (node
);
5042 /* Look up all the bits information that we have discovered and copy it over
5043 to the transformation summary. */
5046 ipcp_store_bits_results (void)
5050 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5052 ipa_node_params
*info
= IPA_NODE_REF (node
);
5053 bool dumped_sth
= false;
5054 bool found_useful_result
= false;
5056 if (!opt_for_fn (node
->decl
, flag_ipa_bit_cp
))
5059 fprintf (dump_file
, "Not considering %s for ipa bitwise propagation "
5060 "; -fipa-bit-cp: disabled.\n",
5065 if (info
->ipcp_orig_node
)
5066 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
5068 unsigned count
= ipa_get_param_count (info
);
5069 for (unsigned i
= 0; i
< count
; i
++)
5071 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5072 if (plats
->bits_lattice
.constant_p ())
5074 found_useful_result
= true;
5079 if (!found_useful_result
)
5082 ipcp_transformation_initialize ();
5083 ipcp_transformation
*ts
= ipcp_transformation_sum
->get_create (node
);
5084 vec_safe_reserve_exact (ts
->bits
, count
);
5086 for (unsigned i
= 0; i
< count
; i
++)
5088 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5091 if (plats
->bits_lattice
.constant_p ())
5093 = ipa_get_ipa_bits_for_value (plats
->bits_lattice
.get_value (),
5094 plats
->bits_lattice
.get_mask ());
5098 ts
->bits
->quick_push (jfbits
);
5099 if (!dump_file
|| !jfbits
)
5103 fprintf (dump_file
, "Propagated bits info for function %s:\n",
5104 node
->dump_name ());
5107 fprintf (dump_file
, " param %i: value = ", i
);
5108 print_hex (jfbits
->value
, dump_file
);
5109 fprintf (dump_file
, ", mask = ");
5110 print_hex (jfbits
->mask
, dump_file
);
5111 fprintf (dump_file
, "\n");
5116 /* Look up all VR information that we have discovered and copy it over
5117 to the transformation summary. */
5120 ipcp_store_vr_results (void)
5124 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5126 ipa_node_params
*info
= IPA_NODE_REF (node
);
5127 bool found_useful_result
= false;
5129 if (!opt_for_fn (node
->decl
, flag_ipa_vrp
))
5132 fprintf (dump_file
, "Not considering %s for VR discovery "
5133 "and propagate; -fipa-ipa-vrp: disabled.\n",
5138 if (info
->ipcp_orig_node
)
5139 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
5141 unsigned count
= ipa_get_param_count (info
);
5142 for (unsigned i
= 0; i
< count
; i
++)
5144 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5145 if (!plats
->m_value_range
.bottom_p ()
5146 && !plats
->m_value_range
.top_p ())
5148 found_useful_result
= true;
5152 if (!found_useful_result
)
5155 ipcp_transformation_initialize ();
5156 ipcp_transformation
*ts
= ipcp_transformation_sum
->get_create (node
);
5157 vec_safe_reserve_exact (ts
->m_vr
, count
);
5159 for (unsigned i
= 0; i
< count
; i
++)
5161 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5164 if (!plats
->m_value_range
.bottom_p ()
5165 && !plats
->m_value_range
.top_p ())
5168 vr
.type
= plats
->m_value_range
.m_vr
.kind ();
5169 vr
.min
= wi::to_wide (plats
->m_value_range
.m_vr
.min ());
5170 vr
.max
= wi::to_wide (plats
->m_value_range
.m_vr
.max ());
5175 vr
.type
= VR_VARYING
;
5176 vr
.min
= vr
.max
= wi::zero (INT_TYPE_SIZE
);
5178 ts
->m_vr
->quick_push (vr
);
5183 /* The IPCP driver. */
5188 class ipa_topo_info topo
;
5190 if (edge_clone_summaries
== NULL
)
5191 edge_clone_summaries
= new edge_clone_summary_t (symtab
);
5193 ipa_check_create_node_params ();
5194 ipa_check_create_edge_args ();
5195 clone_num_suffixes
= new hash_map
<const char *, unsigned>;
5199 fprintf (dump_file
, "\nIPA structures before propagation:\n");
5200 if (dump_flags
& TDF_DETAILS
)
5201 ipa_print_all_params (dump_file
);
5202 ipa_print_all_jump_functions (dump_file
);
5205 /* Topological sort. */
5206 build_toporder_info (&topo
);
5207 /* Do the interprocedural propagation. */
5208 ipcp_propagate_stage (&topo
);
5209 /* Decide what constant propagation and cloning should be performed. */
5210 ipcp_decision_stage (&topo
);
5211 /* Store results of bits propagation. */
5212 ipcp_store_bits_results ();
5213 /* Store results of value range propagation. */
5214 ipcp_store_vr_results ();
5216 /* Free all IPCP structures. */
5217 delete clone_num_suffixes
;
5218 free_toporder_info (&topo
);
5219 delete edge_clone_summaries
;
5220 edge_clone_summaries
= NULL
;
5221 ipa_free_all_structures_after_ipa_cp ();
5223 fprintf (dump_file
, "\nIPA constant propagation end\n");
5227 /* Initialization and computation of IPCP data structures. This is the initial
5228 intraprocedural analysis of functions, which gathers information to be
5229 propagated later on. */
5232 ipcp_generate_summary (void)
5234 struct cgraph_node
*node
;
5237 fprintf (dump_file
, "\nIPA constant propagation start:\n");
5238 ipa_register_cgraph_hooks ();
5240 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5241 ipa_analyze_node (node
);
5244 /* Write ipcp summary for nodes in SET. */
5247 ipcp_write_summary (void)
5249 ipa_prop_write_jump_functions ();
5252 /* Read ipcp summary. */
5255 ipcp_read_summary (void)
5257 ipa_prop_read_jump_functions ();
5262 const pass_data pass_data_ipa_cp
=
5264 IPA_PASS
, /* type */
5266 OPTGROUP_NONE
, /* optinfo_flags */
5267 TV_IPA_CONSTANT_PROP
, /* tv_id */
5268 0, /* properties_required */
5269 0, /* properties_provided */
5270 0, /* properties_destroyed */
5271 0, /* todo_flags_start */
5272 ( TODO_dump_symtab
| TODO_remove_functions
), /* todo_flags_finish */
5275 class pass_ipa_cp
: public ipa_opt_pass_d
5278 pass_ipa_cp (gcc::context
*ctxt
)
5279 : ipa_opt_pass_d (pass_data_ipa_cp
, ctxt
,
5280 ipcp_generate_summary
, /* generate_summary */
5281 ipcp_write_summary
, /* write_summary */
5282 ipcp_read_summary
, /* read_summary */
5283 ipcp_write_transformation_summaries
, /*
5284 write_optimization_summary */
5285 ipcp_read_transformation_summaries
, /*
5286 read_optimization_summary */
5287 NULL
, /* stmt_fixup */
5288 0, /* function_transform_todo_flags_start */
5289 ipcp_transform_function
, /* function_transform */
5290 NULL
) /* variable_transform */
5293 /* opt_pass methods: */
5294 virtual bool gate (function
*)
5296 /* FIXME: We should remove the optimize check after we ensure we never run
5297 IPA passes when not optimizing. */
5298 return (flag_ipa_cp
&& optimize
) || in_lto_p
;
5301 virtual unsigned int execute (function
*) { return ipcp_driver (); }
5303 }; // class pass_ipa_cp
5308 make_pass_ipa_cp (gcc::context
*ctxt
)
5310 return new pass_ipa_cp (ctxt
);
5313 /* Reset all state within ipa-cp.c so that we can rerun the compiler
5314 within the same process. For use by toplev::finalize. */
5317 ipa_cp_c_finalize (void)
5319 max_count
= profile_count::uninitialized ();
5322 ipcp_free_transformation_sum ();