1 /* Interprocedural constant propagation
2 Copyright (C) 2005-2019 Free Software Foundation, Inc.
4 Contributed by Razya Ladelsky <RAZYA@il.ibm.com> and Martin Jambor
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
23 /* Interprocedural constant propagation (IPA-CP).
25 The goal of this transformation is to
27 1) discover functions which are always invoked with some arguments with the
28 same known constant values and modify the functions so that the
29 subsequent optimizations can take advantage of the knowledge, and
31 2) partial specialization - create specialized versions of functions
32 transformed in this way if some parameters are known constants only in
33 certain contexts but the estimated tradeoff between speedup and cost size
36 The algorithm also propagates types and attempts to perform type based
37 devirtualization. Types are propagated much like constants.
39 The algorithm basically consists of three stages. In the first, functions
40 are analyzed one at a time and jump functions are constructed for all known
41 call-sites. In the second phase, the pass propagates information from the
42 jump functions across the call to reveal what values are available at what
43 call sites, performs estimations of effects of known values on functions and
44 their callees, and finally decides what specialized extra versions should be
45 created. In the third, the special versions materialize and appropriate
48 The algorithm used is to a certain extent based on "Interprocedural Constant
49 Propagation", by David Callahan, Keith D Cooper, Ken Kennedy, Linda Torczon,
50 Comp86, pg 152-161 and "A Methodology for Procedure Cloning" by Keith D
51 Cooper, Mary W. Hall, and Ken Kennedy.
54 First stage - intraprocedural analysis
55 =======================================
57 This phase computes jump_function and modification flags.
59 A jump function for a call-site represents the values passed as an actual
60 arguments of a given call-site. In principle, there are three types of
63 Pass through - the caller's formal parameter is passed as an actual
64 argument, plus an operation on it can be performed.
65 Constant - a constant is passed as an actual argument.
66 Unknown - neither of the above.
68 All jump function types are described in detail in ipa-prop.h, together with
69 the data structures that represent them and methods of accessing them.
71 ipcp_generate_summary() is the main function of the first stage.
73 Second stage - interprocedural analysis
74 ========================================
76 This stage is itself divided into two phases. In the first, we propagate
77 known values over the call graph, in the second, we make cloning decisions.
78 It uses a different algorithm than the original Callahan's paper.
80 First, we traverse the functions topologically from callers to callees and,
81 for each strongly connected component (SCC), we propagate constants
82 according to previously computed jump functions. We also record what known
83 values depend on other known values and estimate local effects. Finally, we
84 propagate cumulative information about these effects from dependent values
85 to those on which they depend.
87 Second, we again traverse the call graph in the same topological order and
88 make clones for functions which we know are called with the same values in
89 all contexts and decide about extra specialized clones of functions just for
90 some contexts - these decisions are based on both local estimates and
91 cumulative estimates propagated from callees.
93 ipcp_propagate_stage() and ipcp_decision_stage() together constitute the
96 Third phase - materialization of clones, call statement updates.
97 ============================================
99 This stage is currently performed by call graph code (mainly in cgraphunit.c
100 and tree-inline.c) according to instructions inserted to the call graph by
105 #include "coretypes.h"
108 #include "gimple-expr.h"
110 #include "alloc-pool.h"
111 #include "tree-pass.h"
113 #include "diagnostic.h"
114 #include "fold-const.h"
115 #include "gimple-fold.h"
116 #include "symbol-summary.h"
117 #include "tree-vrp.h"
118 #include "ipa-prop.h"
119 #include "tree-pretty-print.h"
120 #include "tree-inline.h"
122 #include "ipa-fnsummary.h"
123 #include "ipa-utils.h"
124 #include "tree-ssa-ccp.h"
125 #include "stringpool.h"
128 template <typename valtype
> class ipcp_value
;
130 /* Describes a particular source for an IPA-CP value. */
132 template <typename valtype
>
133 struct ipcp_value_source
136 /* Aggregate offset of the source, negative if the source is scalar value of
137 the argument itself. */
138 HOST_WIDE_INT offset
;
139 /* The incoming edge that brought the value. */
141 /* If the jump function that resulted into his value was a pass-through or an
142 ancestor, this is the ipcp_value of the caller from which the described
143 value has been derived. Otherwise it is NULL. */
144 ipcp_value
<valtype
> *val
;
145 /* Next pointer in a linked list of sources of a value. */
146 ipcp_value_source
*next
;
147 /* If the jump function that resulted into his value was a pass-through or an
148 ancestor, this is the index of the parameter of the caller the jump
149 function references. */
153 /* Common ancestor for all ipcp_value instantiations. */
155 class ipcp_value_base
158 /* Time benefit and size cost that specializing the function for this value
159 would bring about in this function alone. */
160 int local_time_benefit
, local_size_cost
;
161 /* Time benefit and size cost that specializing the function for this value
162 can bring about in it's callees (transitively). */
163 int prop_time_benefit
, prop_size_cost
;
166 : local_time_benefit (0), local_size_cost (0),
167 prop_time_benefit (0), prop_size_cost (0) {}
170 /* Describes one particular value stored in struct ipcp_lattice. */
172 template <typename valtype
>
173 class ipcp_value
: public ipcp_value_base
176 /* The actual value for the given parameter. */
178 /* The list of sources from which this value originates. */
179 ipcp_value_source
<valtype
> *sources
;
180 /* Next pointers in a linked list of all values in a lattice. */
182 /* Next pointers in a linked list of values in a strongly connected component
184 ipcp_value
*scc_next
;
185 /* Next pointers in a linked list of SCCs of values sorted topologically
186 according their sources. */
187 ipcp_value
*topo_next
;
188 /* A specialized node created for this value, NULL if none has been (so far)
190 cgraph_node
*spec_node
;
191 /* Depth first search number and low link for topological sorting of
194 /* True if this value is currently on the topo-sort stack. */
198 : sources (0), next (0), scc_next (0), topo_next (0),
199 spec_node (0), dfs (0), low_link (0), on_stack (false) {}
201 void add_source (cgraph_edge
*cs
, ipcp_value
*src_val
, int src_idx
,
202 HOST_WIDE_INT offset
);
205 /* Lattice describing potential values of a formal parameter of a function, or
206 a part of an aggregate. TOP is represented by a lattice with zero values
207 and with contains_variable and bottom flags cleared. BOTTOM is represented
208 by a lattice with the bottom flag set. In that case, values and
209 contains_variable flag should be disregarded. */
211 template <typename valtype
>
215 /* The list of known values and types in this lattice. Note that values are
216 not deallocated if a lattice is set to bottom because there may be value
217 sources referencing them. */
218 ipcp_value
<valtype
> *values
;
219 /* Number of known values and types in this lattice. */
221 /* The lattice contains a variable component (in addition to values). */
222 bool contains_variable
;
223 /* The value of the lattice is bottom (i.e. variable and unusable for any
227 inline bool is_single_const ();
228 inline bool set_to_bottom ();
229 inline bool set_contains_variable ();
230 bool add_value (valtype newval
, cgraph_edge
*cs
,
231 ipcp_value
<valtype
> *src_val
= NULL
,
232 int src_idx
= 0, HOST_WIDE_INT offset
= -1);
233 void print (FILE * f
, bool dump_sources
, bool dump_benefits
);
236 /* Lattice of tree values with an offset to describe a part of an
239 struct ipcp_agg_lattice
: public ipcp_lattice
<tree
>
242 /* Offset that is being described by this lattice. */
243 HOST_WIDE_INT offset
;
244 /* Size so that we don't have to re-compute it every time we traverse the
245 list. Must correspond to TYPE_SIZE of all lat values. */
247 /* Next element of the linked list. */
248 struct ipcp_agg_lattice
*next
;
251 /* Lattice of known bits, only capable of holding one value.
252 Bitwise constant propagation propagates which bits of a
268 In the above case, the param 'x' will always have all
269 the bits (except the bits in lsb) set to 0.
270 Hence the mask of 'x' would be 0xff. The mask
271 reflects that the bits in lsb are unknown.
272 The actual propagated value is given by m_value & ~m_mask. */
274 class ipcp_bits_lattice
277 bool bottom_p () { return m_lattice_val
== IPA_BITS_VARYING
; }
278 bool top_p () { return m_lattice_val
== IPA_BITS_UNDEFINED
; }
279 bool constant_p () { return m_lattice_val
== IPA_BITS_CONSTANT
; }
280 bool set_to_bottom ();
281 bool set_to_constant (widest_int
, widest_int
);
283 widest_int
get_value () { return m_value
; }
284 widest_int
get_mask () { return m_mask
; }
286 bool meet_with (ipcp_bits_lattice
& other
, unsigned, signop
,
287 enum tree_code
, tree
);
289 bool meet_with (widest_int
, widest_int
, unsigned);
294 enum { IPA_BITS_UNDEFINED
, IPA_BITS_CONSTANT
, IPA_BITS_VARYING
} m_lattice_val
;
296 /* Similar to ccp_lattice_t, mask represents which bits of value are constant.
297 If a bit in mask is set to 0, then the corresponding bit in
298 value is known to be constant. */
299 widest_int m_value
, m_mask
;
301 bool meet_with_1 (widest_int
, widest_int
, unsigned);
302 void get_value_and_mask (tree
, widest_int
*, widest_int
*);
305 /* Lattice of value ranges. */
307 class ipcp_vr_lattice
310 value_range_base m_vr
;
312 inline bool bottom_p () const;
313 inline bool top_p () const;
314 inline bool set_to_bottom ();
315 bool meet_with (const value_range_base
*p_vr
);
316 bool meet_with (const ipcp_vr_lattice
&other
);
317 void init () { gcc_assert (m_vr
.undefined_p ()); }
318 void print (FILE * f
);
321 bool meet_with_1 (const value_range_base
*other_vr
);
324 /* Structure containing lattices for a parameter itself and for pieces of
325 aggregates that are passed in the parameter or by a reference in a parameter
326 plus some other useful flags. */
328 class ipcp_param_lattices
331 /* Lattice describing the value of the parameter itself. */
332 ipcp_lattice
<tree
> itself
;
333 /* Lattice describing the polymorphic contexts of a parameter. */
334 ipcp_lattice
<ipa_polymorphic_call_context
> ctxlat
;
335 /* Lattices describing aggregate parts. */
336 ipcp_agg_lattice
*aggs
;
337 /* Lattice describing known bits. */
338 ipcp_bits_lattice bits_lattice
;
339 /* Lattice describing value range. */
340 ipcp_vr_lattice m_value_range
;
341 /* Number of aggregate lattices */
343 /* True if aggregate data were passed by reference (as opposed to by
346 /* All aggregate lattices contain a variable component (in addition to
348 bool aggs_contain_variable
;
349 /* The value of all aggregate lattices is bottom (i.e. variable and unusable
350 for any propagation). */
353 /* There is a virtual call based on this parameter. */
357 /* Allocation pools for values and their sources in ipa-cp. */
359 object_allocator
<ipcp_value
<tree
> > ipcp_cst_values_pool
360 ("IPA-CP constant values");
362 object_allocator
<ipcp_value
<ipa_polymorphic_call_context
> >
363 ipcp_poly_ctx_values_pool ("IPA-CP polymorphic contexts");
365 object_allocator
<ipcp_value_source
<tree
> > ipcp_sources_pool
366 ("IPA-CP value sources");
368 object_allocator
<ipcp_agg_lattice
> ipcp_agg_lattice_pool
369 ("IPA_CP aggregate lattices");
371 /* Maximal count found in program. */
373 static profile_count max_count
;
375 /* Original overall size of the program. */
377 static long overall_size
, max_new_size
;
379 /* Node name to unique clone suffix number map. */
380 static hash_map
<const char *, unsigned> *clone_num_suffixes
;
382 /* Return the param lattices structure corresponding to the Ith formal
383 parameter of the function described by INFO. */
384 static inline class ipcp_param_lattices
*
385 ipa_get_parm_lattices (class ipa_node_params
*info
, int i
)
387 gcc_assert (i
>= 0 && i
< ipa_get_param_count (info
));
388 gcc_checking_assert (!info
->ipcp_orig_node
);
389 gcc_checking_assert (info
->lattices
);
390 return &(info
->lattices
[i
]);
393 /* Return the lattice corresponding to the scalar value of the Ith formal
394 parameter of the function described by INFO. */
395 static inline ipcp_lattice
<tree
> *
396 ipa_get_scalar_lat (class ipa_node_params
*info
, int i
)
398 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
399 return &plats
->itself
;
402 /* Return the lattice corresponding to the scalar value of the Ith formal
403 parameter of the function described by INFO. */
404 static inline ipcp_lattice
<ipa_polymorphic_call_context
> *
405 ipa_get_poly_ctx_lat (class ipa_node_params
*info
, int i
)
407 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
408 return &plats
->ctxlat
;
411 /* Return whether LAT is a lattice with a single constant and without an
414 template <typename valtype
>
416 ipcp_lattice
<valtype
>::is_single_const ()
418 if (bottom
|| contains_variable
|| values_count
!= 1)
424 /* Print V which is extracted from a value in a lattice to F. */
427 print_ipcp_constant_value (FILE * f
, tree v
)
429 if (TREE_CODE (v
) == ADDR_EXPR
430 && TREE_CODE (TREE_OPERAND (v
, 0)) == CONST_DECL
)
433 print_generic_expr (f
, DECL_INITIAL (TREE_OPERAND (v
, 0)));
436 print_generic_expr (f
, v
);
439 /* Print V which is extracted from a value in a lattice to F. */
442 print_ipcp_constant_value (FILE * f
, ipa_polymorphic_call_context v
)
447 /* Print a lattice LAT to F. */
449 template <typename valtype
>
451 ipcp_lattice
<valtype
>::print (FILE * f
, bool dump_sources
, bool dump_benefits
)
453 ipcp_value
<valtype
> *val
;
458 fprintf (f
, "BOTTOM\n");
462 if (!values_count
&& !contains_variable
)
464 fprintf (f
, "TOP\n");
468 if (contains_variable
)
470 fprintf (f
, "VARIABLE");
476 for (val
= values
; val
; val
= val
->next
)
478 if (dump_benefits
&& prev
)
480 else if (!dump_benefits
&& prev
)
485 print_ipcp_constant_value (f
, val
->value
);
489 ipcp_value_source
<valtype
> *s
;
491 fprintf (f
, " [from:");
492 for (s
= val
->sources
; s
; s
= s
->next
)
493 fprintf (f
, " %i(%f)", s
->cs
->caller
->order
,
494 s
->cs
->sreal_frequency ().to_double ());
499 fprintf (f
, " [loc_time: %i, loc_size: %i, "
500 "prop_time: %i, prop_size: %i]\n",
501 val
->local_time_benefit
, val
->local_size_cost
,
502 val
->prop_time_benefit
, val
->prop_size_cost
);
509 ipcp_bits_lattice::print (FILE *f
)
512 fprintf (f
, " Bits unknown (TOP)\n");
513 else if (bottom_p ())
514 fprintf (f
, " Bits unusable (BOTTOM)\n");
517 fprintf (f
, " Bits: value = "); print_hex (get_value (), f
);
518 fprintf (f
, ", mask = "); print_hex (get_mask (), f
);
523 /* Print value range lattice to F. */
526 ipcp_vr_lattice::print (FILE * f
)
528 dump_value_range (f
, &m_vr
);
531 /* Print all ipcp_lattices of all functions to F. */
534 print_all_lattices (FILE * f
, bool dump_sources
, bool dump_benefits
)
536 struct cgraph_node
*node
;
539 fprintf (f
, "\nLattices:\n");
540 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
542 class ipa_node_params
*info
;
544 info
= IPA_NODE_REF (node
);
545 /* Skip constprop clones since we don't make lattices for them. */
546 if (info
->ipcp_orig_node
)
548 fprintf (f
, " Node: %s:\n", node
->dump_name ());
549 count
= ipa_get_param_count (info
);
550 for (i
= 0; i
< count
; i
++)
552 struct ipcp_agg_lattice
*aglat
;
553 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
554 fprintf (f
, " param [%d]: ", i
);
555 plats
->itself
.print (f
, dump_sources
, dump_benefits
);
556 fprintf (f
, " ctxs: ");
557 plats
->ctxlat
.print (f
, dump_sources
, dump_benefits
);
558 plats
->bits_lattice
.print (f
);
560 plats
->m_value_range
.print (f
);
562 if (plats
->virt_call
)
563 fprintf (f
, " virt_call flag set\n");
565 if (plats
->aggs_bottom
)
567 fprintf (f
, " AGGS BOTTOM\n");
570 if (plats
->aggs_contain_variable
)
571 fprintf (f
, " AGGS VARIABLE\n");
572 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
574 fprintf (f
, " %soffset " HOST_WIDE_INT_PRINT_DEC
": ",
575 plats
->aggs_by_ref
? "ref " : "", aglat
->offset
);
576 aglat
->print (f
, dump_sources
, dump_benefits
);
582 /* Determine whether it is at all technically possible to create clones of NODE
583 and store this information in the ipa_node_params structure associated
587 determine_versionability (struct cgraph_node
*node
,
588 class ipa_node_params
*info
)
590 const char *reason
= NULL
;
592 /* There are a number of generic reasons functions cannot be versioned. We
593 also cannot remove parameters if there are type attributes such as fnspec
595 if (node
->alias
|| node
->thunk
.thunk_p
)
596 reason
= "alias or thunk";
597 else if (!node
->local
.versionable
)
598 reason
= "not a tree_versionable_function";
599 else if (node
->get_availability () <= AVAIL_INTERPOSABLE
)
600 reason
= "insufficient body availability";
601 else if (!opt_for_fn (node
->decl
, optimize
)
602 || !opt_for_fn (node
->decl
, flag_ipa_cp
))
603 reason
= "non-optimized function";
604 else if (lookup_attribute ("omp declare simd", DECL_ATTRIBUTES (node
->decl
)))
606 /* Ideally we should clone the SIMD clones themselves and create
607 vector copies of them, so IPA-cp and SIMD clones can happily
608 coexist, but that may not be worth the effort. */
609 reason
= "function has SIMD clones";
611 else if (lookup_attribute ("target_clones", DECL_ATTRIBUTES (node
->decl
)))
613 /* Ideally we should clone the target clones themselves and create
614 copies of them, so IPA-cp and target clones can happily
615 coexist, but that may not be worth the effort. */
616 reason
= "function target_clones attribute";
618 /* Don't clone decls local to a comdat group; it breaks and for C++
619 decloned constructors, inlining is always better anyway. */
620 else if (node
->comdat_local_p ())
621 reason
= "comdat-local function";
622 else if (node
->calls_comdat_local
)
624 /* TODO: call is versionable if we make sure that all
625 callers are inside of a comdat group. */
626 reason
= "calls comdat-local function";
629 /* Functions calling BUILT_IN_VA_ARG_PACK and BUILT_IN_VA_ARG_PACK_LEN
630 work only when inlined. Cloning them may still lead to better code
631 because ipa-cp will not give up on cloning further. If the function is
632 external this however leads to wrong code because we may end up producing
633 offline copy of the function. */
634 if (DECL_EXTERNAL (node
->decl
))
635 for (cgraph_edge
*edge
= node
->callees
; !reason
&& edge
;
636 edge
= edge
->next_callee
)
637 if (fndecl_built_in_p (edge
->callee
->decl
, BUILT_IN_NORMAL
))
639 if (DECL_FUNCTION_CODE (edge
->callee
->decl
) == BUILT_IN_VA_ARG_PACK
)
640 reason
= "external function which calls va_arg_pack";
641 if (DECL_FUNCTION_CODE (edge
->callee
->decl
)
642 == BUILT_IN_VA_ARG_PACK_LEN
)
643 reason
= "external function which calls va_arg_pack_len";
646 if (reason
&& dump_file
&& !node
->alias
&& !node
->thunk
.thunk_p
)
647 fprintf (dump_file
, "Function %s is not versionable, reason: %s.\n",
648 node
->dump_name (), reason
);
650 info
->versionable
= (reason
== NULL
);
653 /* Return true if it is at all technically possible to create clones of a
657 ipcp_versionable_function_p (struct cgraph_node
*node
)
659 return IPA_NODE_REF (node
)->versionable
;
662 /* Structure holding accumulated information about callers of a node. */
664 struct caller_statistics
666 profile_count count_sum
;
667 int n_calls
, n_hot_calls
, freq_sum
;
670 /* Initialize fields of STAT to zeroes. */
673 init_caller_stats (struct caller_statistics
*stats
)
675 stats
->count_sum
= profile_count::zero ();
677 stats
->n_hot_calls
= 0;
681 /* Worker callback of cgraph_for_node_and_aliases accumulating statistics of
682 non-thunk incoming edges to NODE. */
685 gather_caller_stats (struct cgraph_node
*node
, void *data
)
687 struct caller_statistics
*stats
= (struct caller_statistics
*) data
;
688 struct cgraph_edge
*cs
;
690 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
691 if (!cs
->caller
->thunk
.thunk_p
)
693 if (cs
->count
.ipa ().initialized_p ())
694 stats
->count_sum
+= cs
->count
.ipa ();
695 stats
->freq_sum
+= cs
->frequency ();
697 if (cs
->maybe_hot_p ())
698 stats
->n_hot_calls
++;
704 /* Return true if this NODE is viable candidate for cloning. */
707 ipcp_cloning_candidate_p (struct cgraph_node
*node
)
709 struct caller_statistics stats
;
711 gcc_checking_assert (node
->has_gimple_body_p ());
713 if (!opt_for_fn (node
->decl
, flag_ipa_cp_clone
))
716 fprintf (dump_file
, "Not considering %s for cloning; "
717 "-fipa-cp-clone disabled.\n",
722 if (node
->optimize_for_size_p ())
725 fprintf (dump_file
, "Not considering %s for cloning; "
726 "optimizing it for size.\n",
731 init_caller_stats (&stats
);
732 node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
, false);
734 if (ipa_fn_summaries
->get (node
)->self_size
< stats
.n_calls
)
737 fprintf (dump_file
, "Considering %s for cloning; code might shrink.\n",
742 /* When profile is available and function is hot, propagate into it even if
743 calls seems cold; constant propagation can improve function's speed
745 if (max_count
> profile_count::zero ())
747 if (stats
.count_sum
> node
->count
.ipa ().apply_scale (90, 100))
750 fprintf (dump_file
, "Considering %s for cloning; "
751 "usually called directly.\n",
756 if (!stats
.n_hot_calls
)
759 fprintf (dump_file
, "Not considering %s for cloning; no hot calls.\n",
764 fprintf (dump_file
, "Considering %s for cloning.\n",
769 template <typename valtype
>
770 class value_topo_info
773 /* Head of the linked list of topologically sorted values. */
774 ipcp_value
<valtype
> *values_topo
;
775 /* Stack for creating SCCs, represented by a linked list too. */
776 ipcp_value
<valtype
> *stack
;
777 /* Counter driving the algorithm in add_val_to_toposort. */
780 value_topo_info () : values_topo (NULL
), stack (NULL
), dfs_counter (0)
782 void add_val (ipcp_value
<valtype
> *cur_val
);
783 void propagate_effects ();
786 /* Arrays representing a topological ordering of call graph nodes and a stack
787 of nodes used during constant propagation and also data required to perform
788 topological sort of values and propagation of benefits in the determined
794 /* Array with obtained topological order of cgraph nodes. */
795 struct cgraph_node
**order
;
796 /* Stack of cgraph nodes used during propagation within SCC until all values
797 in the SCC stabilize. */
798 struct cgraph_node
**stack
;
799 int nnodes
, stack_top
;
801 value_topo_info
<tree
> constants
;
802 value_topo_info
<ipa_polymorphic_call_context
> contexts
;
804 ipa_topo_info () : order(NULL
), stack(NULL
), nnodes(0), stack_top(0),
809 /* Skip edges from and to nodes without ipa_cp enabled.
810 Ignore not available symbols. */
813 ignore_edge_p (cgraph_edge
*e
)
815 enum availability avail
;
816 cgraph_node
*ultimate_target
817 = e
->callee
->function_or_virtual_thunk_symbol (&avail
, e
->caller
);
819 return (avail
<= AVAIL_INTERPOSABLE
820 || !opt_for_fn (ultimate_target
->decl
, flag_ipa_cp
));
823 /* Allocate the arrays in TOPO and topologically sort the nodes into order. */
826 build_toporder_info (class ipa_topo_info
*topo
)
828 topo
->order
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
829 topo
->stack
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
831 gcc_checking_assert (topo
->stack_top
== 0);
832 topo
->nnodes
= ipa_reduced_postorder (topo
->order
, true,
836 /* Free information about strongly connected components and the arrays in
840 free_toporder_info (class ipa_topo_info
*topo
)
842 ipa_free_postorder_info ();
847 /* Add NODE to the stack in TOPO, unless it is already there. */
850 push_node_to_stack (class ipa_topo_info
*topo
, struct cgraph_node
*node
)
852 class ipa_node_params
*info
= IPA_NODE_REF (node
);
853 if (info
->node_enqueued
)
855 info
->node_enqueued
= 1;
856 topo
->stack
[topo
->stack_top
++] = node
;
859 /* Pop a node from the stack in TOPO and return it or return NULL if the stack
862 static struct cgraph_node
*
863 pop_node_from_stack (class ipa_topo_info
*topo
)
867 struct cgraph_node
*node
;
869 node
= topo
->stack
[topo
->stack_top
];
870 IPA_NODE_REF (node
)->node_enqueued
= 0;
877 /* Set lattice LAT to bottom and return true if it previously was not set as
880 template <typename valtype
>
882 ipcp_lattice
<valtype
>::set_to_bottom ()
889 /* Mark lattice as containing an unknown value and return true if it previously
890 was not marked as such. */
892 template <typename valtype
>
894 ipcp_lattice
<valtype
>::set_contains_variable ()
896 bool ret
= !contains_variable
;
897 contains_variable
= true;
901 /* Set all aggregate lattices in PLATS to bottom and return true if they were
902 not previously set as such. */
905 set_agg_lats_to_bottom (class ipcp_param_lattices
*plats
)
907 bool ret
= !plats
->aggs_bottom
;
908 plats
->aggs_bottom
= true;
912 /* Mark all aggregate lattices in PLATS as containing an unknown value and
913 return true if they were not previously marked as such. */
916 set_agg_lats_contain_variable (class ipcp_param_lattices
*plats
)
918 bool ret
= !plats
->aggs_contain_variable
;
919 plats
->aggs_contain_variable
= true;
924 ipcp_vr_lattice::meet_with (const ipcp_vr_lattice
&other
)
926 return meet_with_1 (&other
.m_vr
);
929 /* Meet the current value of the lattice with value range described by VR
933 ipcp_vr_lattice::meet_with (const value_range_base
*p_vr
)
935 return meet_with_1 (p_vr
);
938 /* Meet the current value of the lattice with value range described by
939 OTHER_VR lattice. Return TRUE if anything changed. */
942 ipcp_vr_lattice::meet_with_1 (const value_range_base
*other_vr
)
947 if (other_vr
->varying_p ())
948 return set_to_bottom ();
950 value_range_base
save (m_vr
);
951 m_vr
.union_ (other_vr
);
952 return !m_vr
.equal_p (save
);
955 /* Return true if value range information in the lattice is yet unknown. */
958 ipcp_vr_lattice::top_p () const
960 return m_vr
.undefined_p ();
963 /* Return true if value range information in the lattice is known to be
967 ipcp_vr_lattice::bottom_p () const
969 return m_vr
.varying_p ();
972 /* Set value range information in the lattice to bottom. Return true if it
973 previously was in a different state. */
976 ipcp_vr_lattice::set_to_bottom ()
978 if (m_vr
.varying_p ())
980 /* ?? We create all sorts of VARYING ranges for floats, structures,
981 and other types which we cannot handle as ranges. We should
982 probably avoid handling them throughout the pass, but it's easier
983 to create a sensible VARYING here and let the lattice
985 m_vr
.set_varying (integer_type_node
);
989 /* Set lattice value to bottom, if it already isn't the case. */
992 ipcp_bits_lattice::set_to_bottom ()
996 m_lattice_val
= IPA_BITS_VARYING
;
1002 /* Set to constant if it isn't already. Only meant to be called
1003 when switching state from TOP. */
1006 ipcp_bits_lattice::set_to_constant (widest_int value
, widest_int mask
)
1008 gcc_assert (top_p ());
1009 m_lattice_val
= IPA_BITS_CONSTANT
;
1015 /* Convert operand to value, mask form. */
1018 ipcp_bits_lattice::get_value_and_mask (tree operand
, widest_int
*valuep
, widest_int
*maskp
)
1020 wide_int
get_nonzero_bits (const_tree
);
1022 if (TREE_CODE (operand
) == INTEGER_CST
)
1024 *valuep
= wi::to_widest (operand
);
1034 /* Meet operation, similar to ccp_lattice_meet, we xor values
1035 if this->value, value have different values at same bit positions, we want
1036 to drop that bit to varying. Return true if mask is changed.
1037 This function assumes that the lattice value is in CONSTANT state */
1040 ipcp_bits_lattice::meet_with_1 (widest_int value
, widest_int mask
,
1043 gcc_assert (constant_p ());
1045 widest_int old_mask
= m_mask
;
1046 m_mask
= (m_mask
| mask
) | (m_value
^ value
);
1048 if (wi::sext (m_mask
, precision
) == -1)
1049 return set_to_bottom ();
1051 return m_mask
!= old_mask
;
1054 /* Meet the bits lattice with operand
1055 described by <value, mask, sgn, precision. */
1058 ipcp_bits_lattice::meet_with (widest_int value
, widest_int mask
,
1066 if (wi::sext (mask
, precision
) == -1)
1067 return set_to_bottom ();
1068 return set_to_constant (value
, mask
);
1071 return meet_with_1 (value
, mask
, precision
);
1074 /* Meet bits lattice with the result of bit_value_binop (other, operand)
1075 if code is binary operation or bit_value_unop (other) if code is unary op.
1076 In the case when code is nop_expr, no adjustment is required. */
1079 ipcp_bits_lattice::meet_with (ipcp_bits_lattice
& other
, unsigned precision
,
1080 signop sgn
, enum tree_code code
, tree operand
)
1082 if (other
.bottom_p ())
1083 return set_to_bottom ();
1085 if (bottom_p () || other
.top_p ())
1088 widest_int adjusted_value
, adjusted_mask
;
1090 if (TREE_CODE_CLASS (code
) == tcc_binary
)
1092 tree type
= TREE_TYPE (operand
);
1093 widest_int o_value
, o_mask
;
1094 get_value_and_mask (operand
, &o_value
, &o_mask
);
1096 bit_value_binop (code
, sgn
, precision
, &adjusted_value
, &adjusted_mask
,
1097 sgn
, precision
, other
.get_value (), other
.get_mask (),
1098 TYPE_SIGN (type
), TYPE_PRECISION (type
), o_value
, o_mask
);
1100 if (wi::sext (adjusted_mask
, precision
) == -1)
1101 return set_to_bottom ();
1104 else if (TREE_CODE_CLASS (code
) == tcc_unary
)
1106 bit_value_unop (code
, sgn
, precision
, &adjusted_value
,
1107 &adjusted_mask
, sgn
, precision
, other
.get_value (),
1110 if (wi::sext (adjusted_mask
, precision
) == -1)
1111 return set_to_bottom ();
1115 return set_to_bottom ();
1119 if (wi::sext (adjusted_mask
, precision
) == -1)
1120 return set_to_bottom ();
1121 return set_to_constant (adjusted_value
, adjusted_mask
);
1124 return meet_with_1 (adjusted_value
, adjusted_mask
, precision
);
1127 /* Mark bot aggregate and scalar lattices as containing an unknown variable,
1128 return true is any of them has not been marked as such so far. */
1131 set_all_contains_variable (class ipcp_param_lattices
*plats
)
1134 ret
= plats
->itself
.set_contains_variable ();
1135 ret
|= plats
->ctxlat
.set_contains_variable ();
1136 ret
|= set_agg_lats_contain_variable (plats
);
1137 ret
|= plats
->bits_lattice
.set_to_bottom ();
1138 ret
|= plats
->m_value_range
.set_to_bottom ();
1142 /* Worker of call_for_symbol_thunks_and_aliases, increment the integer DATA
1143 points to by the number of callers to NODE. */
1146 count_callers (cgraph_node
*node
, void *data
)
1148 int *caller_count
= (int *) data
;
1150 for (cgraph_edge
*cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
1151 /* Local thunks can be handled transparently, but if the thunk cannot
1152 be optimized out, count it as a real use. */
1153 if (!cs
->caller
->thunk
.thunk_p
|| !cs
->caller
->local
.local
)
1158 /* Worker of call_for_symbol_thunks_and_aliases, it is supposed to be called on
1159 the one caller of some other node. Set the caller's corresponding flag. */
1162 set_single_call_flag (cgraph_node
*node
, void *)
1164 cgraph_edge
*cs
= node
->callers
;
1165 /* Local thunks can be handled transparently, skip them. */
1166 while (cs
&& cs
->caller
->thunk
.thunk_p
&& cs
->caller
->local
.local
)
1167 cs
= cs
->next_caller
;
1170 IPA_NODE_REF (cs
->caller
)->node_calling_single_call
= true;
1176 /* Initialize ipcp_lattices. */
1179 initialize_node_lattices (struct cgraph_node
*node
)
1181 class ipa_node_params
*info
= IPA_NODE_REF (node
);
1182 struct cgraph_edge
*ie
;
1183 bool disable
= false, variable
= false;
1186 gcc_checking_assert (node
->has_gimple_body_p ());
1187 if (node
->local
.local
)
1189 int caller_count
= 0;
1190 node
->call_for_symbol_thunks_and_aliases (count_callers
, &caller_count
,
1192 gcc_checking_assert (caller_count
> 0);
1193 if (caller_count
== 1)
1194 node
->call_for_symbol_thunks_and_aliases (set_single_call_flag
,
1199 /* When cloning is allowed, we can assume that externally visible
1200 functions are not called. We will compensate this by cloning
1202 if (ipcp_versionable_function_p (node
)
1203 && ipcp_cloning_candidate_p (node
))
1209 for (i
= 0; i
< ipa_get_param_count (info
); i
++)
1211 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1212 plats
->m_value_range
.init ();
1215 if (disable
|| variable
)
1217 for (i
= 0; i
< ipa_get_param_count (info
); i
++)
1219 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1222 plats
->itself
.set_to_bottom ();
1223 plats
->ctxlat
.set_to_bottom ();
1224 set_agg_lats_to_bottom (plats
);
1225 plats
->bits_lattice
.set_to_bottom ();
1226 plats
->m_value_range
.set_to_bottom ();
1229 set_all_contains_variable (plats
);
1231 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1232 && !node
->alias
&& !node
->thunk
.thunk_p
)
1233 fprintf (dump_file
, "Marking all lattices of %s as %s\n",
1234 node
->dump_name (), disable
? "BOTTOM" : "VARIABLE");
1237 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
1238 if (ie
->indirect_info
->polymorphic
1239 && ie
->indirect_info
->param_index
>= 0)
1241 gcc_checking_assert (ie
->indirect_info
->param_index
>= 0);
1242 ipa_get_parm_lattices (info
,
1243 ie
->indirect_info
->param_index
)->virt_call
= 1;
1247 /* Return the result of a (possibly arithmetic) pass through jump function
1248 JFUNC on the constant value INPUT. RES_TYPE is the type of the parameter
1249 to which the result is passed. Return NULL_TREE if that cannot be
1250 determined or be considered an interprocedural invariant. */
1253 ipa_get_jf_pass_through_result (struct ipa_jump_func
*jfunc
, tree input
,
1258 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
1260 if (!is_gimple_ip_invariant (input
))
1263 tree_code opcode
= ipa_get_jf_pass_through_operation (jfunc
);
1266 if (TREE_CODE_CLASS (opcode
) == tcc_comparison
)
1267 res_type
= boolean_type_node
;
1268 else if (expr_type_first_operand_type_p (opcode
))
1269 res_type
= TREE_TYPE (input
);
1274 if (TREE_CODE_CLASS (opcode
) == tcc_unary
)
1275 res
= fold_unary (opcode
, res_type
, input
);
1277 res
= fold_binary (opcode
, res_type
, input
,
1278 ipa_get_jf_pass_through_operand (jfunc
));
1280 if (res
&& !is_gimple_ip_invariant (res
))
1286 /* Return the result of an ancestor jump function JFUNC on the constant value
1287 INPUT. Return NULL_TREE if that cannot be determined. */
1290 ipa_get_jf_ancestor_result (struct ipa_jump_func
*jfunc
, tree input
)
1292 gcc_checking_assert (TREE_CODE (input
) != TREE_BINFO
);
1293 if (TREE_CODE (input
) == ADDR_EXPR
)
1295 tree t
= TREE_OPERAND (input
, 0);
1296 t
= build_ref_for_offset (EXPR_LOCATION (t
), t
,
1297 ipa_get_jf_ancestor_offset (jfunc
), false,
1298 ptr_type_node
, NULL
, false);
1299 return build_fold_addr_expr (t
);
1305 /* Determine whether JFUNC evaluates to a single known constant value and if
1306 so, return it. Otherwise return NULL. INFO describes the caller node or
1307 the one it is inlined to, so that pass-through jump functions can be
1308 evaluated. PARM_TYPE is the type of the parameter to which the result is
1312 ipa_value_from_jfunc (class ipa_node_params
*info
, struct ipa_jump_func
*jfunc
,
1315 if (jfunc
->type
== IPA_JF_CONST
)
1316 return ipa_get_jf_constant (jfunc
);
1317 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1318 || jfunc
->type
== IPA_JF_ANCESTOR
)
1323 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1324 idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1326 idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1328 if (info
->ipcp_orig_node
)
1329 input
= info
->known_csts
[idx
];
1332 ipcp_lattice
<tree
> *lat
;
1335 || idx
>= ipa_get_param_count (info
))
1337 lat
= ipa_get_scalar_lat (info
, idx
);
1338 if (!lat
->is_single_const ())
1340 input
= lat
->values
->value
;
1346 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1347 return ipa_get_jf_pass_through_result (jfunc
, input
, parm_type
);
1349 return ipa_get_jf_ancestor_result (jfunc
, input
);
1355 /* Determine whether JFUNC evaluates to single known polymorphic context, given
1356 that INFO describes the caller node or the one it is inlined to, CS is the
1357 call graph edge corresponding to JFUNC and CSIDX index of the described
1360 ipa_polymorphic_call_context
1361 ipa_context_from_jfunc (ipa_node_params
*info
, cgraph_edge
*cs
, int csidx
,
1362 ipa_jump_func
*jfunc
)
1364 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
1365 ipa_polymorphic_call_context ctx
;
1366 ipa_polymorphic_call_context
*edge_ctx
1367 = cs
? ipa_get_ith_polymorhic_call_context (args
, csidx
) : NULL
;
1369 if (edge_ctx
&& !edge_ctx
->useless_p ())
1372 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1373 || jfunc
->type
== IPA_JF_ANCESTOR
)
1375 ipa_polymorphic_call_context srcctx
;
1377 bool type_preserved
= true;
1378 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1380 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1382 type_preserved
= ipa_get_jf_pass_through_type_preserved (jfunc
);
1383 srcidx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1387 type_preserved
= ipa_get_jf_ancestor_type_preserved (jfunc
);
1388 srcidx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1390 if (info
->ipcp_orig_node
)
1392 if (info
->known_contexts
.exists ())
1393 srcctx
= info
->known_contexts
[srcidx
];
1398 || srcidx
>= ipa_get_param_count (info
))
1400 ipcp_lattice
<ipa_polymorphic_call_context
> *lat
;
1401 lat
= ipa_get_poly_ctx_lat (info
, srcidx
);
1402 if (!lat
->is_single_const ())
1404 srcctx
= lat
->values
->value
;
1406 if (srcctx
.useless_p ())
1408 if (jfunc
->type
== IPA_JF_ANCESTOR
)
1409 srcctx
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
1410 if (!type_preserved
)
1411 srcctx
.possible_dynamic_type_change (cs
->in_polymorphic_cdtor
);
1412 srcctx
.combine_with (ctx
);
1419 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
1420 bottom, not containing a variable component and without any known value at
1424 ipcp_verify_propagated_values (void)
1426 struct cgraph_node
*node
;
1428 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
1430 class ipa_node_params
*info
= IPA_NODE_REF (node
);
1431 int i
, count
= ipa_get_param_count (info
);
1433 for (i
= 0; i
< count
; i
++)
1435 ipcp_lattice
<tree
> *lat
= ipa_get_scalar_lat (info
, i
);
1438 && !lat
->contains_variable
1439 && lat
->values_count
== 0)
1443 symtab
->dump (dump_file
);
1444 fprintf (dump_file
, "\nIPA lattices after constant "
1445 "propagation, before gcc_unreachable:\n");
1446 print_all_lattices (dump_file
, true, false);
1455 /* Return true iff X and Y should be considered equal values by IPA-CP. */
1458 values_equal_for_ipcp_p (tree x
, tree y
)
1460 gcc_checking_assert (x
!= NULL_TREE
&& y
!= NULL_TREE
);
1465 if (TREE_CODE (x
) == ADDR_EXPR
1466 && TREE_CODE (y
) == ADDR_EXPR
1467 && TREE_CODE (TREE_OPERAND (x
, 0)) == CONST_DECL
1468 && TREE_CODE (TREE_OPERAND (y
, 0)) == CONST_DECL
)
1469 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x
, 0)),
1470 DECL_INITIAL (TREE_OPERAND (y
, 0)), 0);
1472 return operand_equal_p (x
, y
, 0);
1475 /* Return true iff X and Y should be considered equal contexts by IPA-CP. */
1478 values_equal_for_ipcp_p (ipa_polymorphic_call_context x
,
1479 ipa_polymorphic_call_context y
)
1481 return x
.equal_to (y
);
1485 /* Add a new value source to the value represented by THIS, marking that a
1486 value comes from edge CS and (if the underlying jump function is a
1487 pass-through or an ancestor one) from a caller value SRC_VAL of a caller
1488 parameter described by SRC_INDEX. OFFSET is negative if the source was the
1489 scalar value of the parameter itself or the offset within an aggregate. */
1491 template <typename valtype
>
1493 ipcp_value
<valtype
>::add_source (cgraph_edge
*cs
, ipcp_value
*src_val
,
1494 int src_idx
, HOST_WIDE_INT offset
)
1496 ipcp_value_source
<valtype
> *src
;
1498 src
= new (ipcp_sources_pool
.allocate ()) ipcp_value_source
<valtype
>;
1499 src
->offset
= offset
;
1502 src
->index
= src_idx
;
1504 src
->next
= sources
;
1508 /* Allocate a new ipcp_value holding a tree constant, initialize its value to
1509 SOURCE and clear all other fields. */
1511 static ipcp_value
<tree
> *
1512 allocate_and_init_ipcp_value (tree source
)
1514 ipcp_value
<tree
> *val
;
1516 val
= new (ipcp_cst_values_pool
.allocate ()) ipcp_value
<tree
>();
1517 val
->value
= source
;
1521 /* Allocate a new ipcp_value holding a polymorphic context, initialize its
1522 value to SOURCE and clear all other fields. */
1524 static ipcp_value
<ipa_polymorphic_call_context
> *
1525 allocate_and_init_ipcp_value (ipa_polymorphic_call_context source
)
1527 ipcp_value
<ipa_polymorphic_call_context
> *val
;
1530 val
= new (ipcp_poly_ctx_values_pool
.allocate ())
1531 ipcp_value
<ipa_polymorphic_call_context
>();
1532 val
->value
= source
;
1536 /* Try to add NEWVAL to LAT, potentially creating a new ipcp_value for it. CS,
1537 SRC_VAL SRC_INDEX and OFFSET are meant for add_source and have the same
1538 meaning. OFFSET -1 means the source is scalar and not a part of an
1541 template <typename valtype
>
1543 ipcp_lattice
<valtype
>::add_value (valtype newval
, cgraph_edge
*cs
,
1544 ipcp_value
<valtype
> *src_val
,
1545 int src_idx
, HOST_WIDE_INT offset
)
1547 ipcp_value
<valtype
> *val
;
1552 for (val
= values
; val
; val
= val
->next
)
1553 if (values_equal_for_ipcp_p (val
->value
, newval
))
1555 if (ipa_edge_within_scc (cs
))
1557 ipcp_value_source
<valtype
> *s
;
1558 for (s
= val
->sources
; s
; s
= s
->next
)
1565 val
->add_source (cs
, src_val
, src_idx
, offset
);
1569 if (values_count
== PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE
))
1571 /* We can only free sources, not the values themselves, because sources
1572 of other values in this SCC might point to them. */
1573 for (val
= values
; val
; val
= val
->next
)
1575 while (val
->sources
)
1577 ipcp_value_source
<valtype
> *src
= val
->sources
;
1578 val
->sources
= src
->next
;
1579 ipcp_sources_pool
.remove ((ipcp_value_source
<tree
>*)src
);
1584 return set_to_bottom ();
1588 val
= allocate_and_init_ipcp_value (newval
);
1589 val
->add_source (cs
, src_val
, src_idx
, offset
);
1595 /* Propagate values through a pass-through jump function JFUNC associated with
1596 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1597 is the index of the source parameter. PARM_TYPE is the type of the
1598 parameter to which the result is passed. */
1601 propagate_vals_across_pass_through (cgraph_edge
*cs
, ipa_jump_func
*jfunc
,
1602 ipcp_lattice
<tree
> *src_lat
,
1603 ipcp_lattice
<tree
> *dest_lat
, int src_idx
,
1606 ipcp_value
<tree
> *src_val
;
1609 /* Do not create new values when propagating within an SCC because if there
1610 are arithmetic functions with circular dependencies, there is infinite
1611 number of them and we would just make lattices bottom. If this condition
1612 is ever relaxed we have to detect self-feeding recursive calls in
1613 cgraph_edge_brings_value_p in a smarter way. */
1614 if ((ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1615 && ipa_edge_within_scc (cs
))
1616 ret
= dest_lat
->set_contains_variable ();
1618 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1620 tree cstval
= ipa_get_jf_pass_through_result (jfunc
, src_val
->value
,
1624 ret
|= dest_lat
->add_value (cstval
, cs
, src_val
, src_idx
);
1626 ret
|= dest_lat
->set_contains_variable ();
1632 /* Propagate values through an ancestor jump function JFUNC associated with
1633 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1634 is the index of the source parameter. */
1637 propagate_vals_across_ancestor (struct cgraph_edge
*cs
,
1638 struct ipa_jump_func
*jfunc
,
1639 ipcp_lattice
<tree
> *src_lat
,
1640 ipcp_lattice
<tree
> *dest_lat
, int src_idx
)
1642 ipcp_value
<tree
> *src_val
;
1645 if (ipa_edge_within_scc (cs
))
1646 return dest_lat
->set_contains_variable ();
1648 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1650 tree t
= ipa_get_jf_ancestor_result (jfunc
, src_val
->value
);
1653 ret
|= dest_lat
->add_value (t
, cs
, src_val
, src_idx
);
1655 ret
|= dest_lat
->set_contains_variable ();
1661 /* Propagate scalar values across jump function JFUNC that is associated with
1662 edge CS and put the values into DEST_LAT. PARM_TYPE is the type of the
1663 parameter to which the result is passed. */
1666 propagate_scalar_across_jump_function (struct cgraph_edge
*cs
,
1667 struct ipa_jump_func
*jfunc
,
1668 ipcp_lattice
<tree
> *dest_lat
,
1671 if (dest_lat
->bottom
)
1674 if (jfunc
->type
== IPA_JF_CONST
)
1676 tree val
= ipa_get_jf_constant (jfunc
);
1677 return dest_lat
->add_value (val
, cs
, NULL
, 0);
1679 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1680 || jfunc
->type
== IPA_JF_ANCESTOR
)
1682 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1683 ipcp_lattice
<tree
> *src_lat
;
1687 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1688 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1690 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1692 src_lat
= ipa_get_scalar_lat (caller_info
, src_idx
);
1693 if (src_lat
->bottom
)
1694 return dest_lat
->set_contains_variable ();
1696 /* If we would need to clone the caller and cannot, do not propagate. */
1697 if (!ipcp_versionable_function_p (cs
->caller
)
1698 && (src_lat
->contains_variable
1699 || (src_lat
->values_count
> 1)))
1700 return dest_lat
->set_contains_variable ();
1702 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1703 ret
= propagate_vals_across_pass_through (cs
, jfunc
, src_lat
,
1704 dest_lat
, src_idx
, param_type
);
1706 ret
= propagate_vals_across_ancestor (cs
, jfunc
, src_lat
, dest_lat
,
1709 if (src_lat
->contains_variable
)
1710 ret
|= dest_lat
->set_contains_variable ();
1715 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1716 use it for indirect inlining), we should propagate them too. */
1717 return dest_lat
->set_contains_variable ();
1720 /* Propagate scalar values across jump function JFUNC that is associated with
1721 edge CS and describes argument IDX and put the values into DEST_LAT. */
1724 propagate_context_across_jump_function (cgraph_edge
*cs
,
1725 ipa_jump_func
*jfunc
, int idx
,
1726 ipcp_lattice
<ipa_polymorphic_call_context
> *dest_lat
)
1728 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
1729 if (dest_lat
->bottom
)
1732 bool added_sth
= false;
1733 bool type_preserved
= true;
1735 ipa_polymorphic_call_context edge_ctx
, *edge_ctx_ptr
1736 = ipa_get_ith_polymorhic_call_context (args
, idx
);
1739 edge_ctx
= *edge_ctx_ptr
;
1741 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1742 || jfunc
->type
== IPA_JF_ANCESTOR
)
1744 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1746 ipcp_lattice
<ipa_polymorphic_call_context
> *src_lat
;
1748 /* TODO: Once we figure out how to propagate speculations, it will
1749 probably be a good idea to switch to speculation if type_preserved is
1750 not set instead of punting. */
1751 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1753 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1755 type_preserved
= ipa_get_jf_pass_through_type_preserved (jfunc
);
1756 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1760 type_preserved
= ipa_get_jf_ancestor_type_preserved (jfunc
);
1761 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1764 src_lat
= ipa_get_poly_ctx_lat (caller_info
, src_idx
);
1765 /* If we would need to clone the caller and cannot, do not propagate. */
1766 if (!ipcp_versionable_function_p (cs
->caller
)
1767 && (src_lat
->contains_variable
1768 || (src_lat
->values_count
> 1)))
1771 ipcp_value
<ipa_polymorphic_call_context
> *src_val
;
1772 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1774 ipa_polymorphic_call_context cur
= src_val
->value
;
1776 if (!type_preserved
)
1777 cur
.possible_dynamic_type_change (cs
->in_polymorphic_cdtor
);
1778 if (jfunc
->type
== IPA_JF_ANCESTOR
)
1779 cur
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
1780 /* TODO: In cases we know how the context is going to be used,
1781 we can improve the result by passing proper OTR_TYPE. */
1782 cur
.combine_with (edge_ctx
);
1783 if (!cur
.useless_p ())
1785 if (src_lat
->contains_variable
1786 && !edge_ctx
.equal_to (cur
))
1787 ret
|= dest_lat
->set_contains_variable ();
1788 ret
|= dest_lat
->add_value (cur
, cs
, src_val
, src_idx
);
1798 if (!edge_ctx
.useless_p ())
1799 ret
|= dest_lat
->add_value (edge_ctx
, cs
);
1801 ret
|= dest_lat
->set_contains_variable ();
1807 /* Propagate bits across jfunc that is associated with
1808 edge cs and update dest_lattice accordingly. */
1811 propagate_bits_across_jump_function (cgraph_edge
*cs
, int idx
,
1812 ipa_jump_func
*jfunc
,
1813 ipcp_bits_lattice
*dest_lattice
)
1815 if (dest_lattice
->bottom_p ())
1818 enum availability availability
;
1819 cgraph_node
*callee
= cs
->callee
->function_symbol (&availability
);
1820 class ipa_node_params
*callee_info
= IPA_NODE_REF (callee
);
1821 tree parm_type
= ipa_get_type (callee_info
, idx
);
1823 /* For K&R C programs, ipa_get_type() could return NULL_TREE. Avoid the
1824 transform for these cases. Similarly, we can have bad type mismatches
1825 with LTO, avoid doing anything with those too. */
1827 || (!INTEGRAL_TYPE_P (parm_type
) && !POINTER_TYPE_P (parm_type
)))
1829 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1830 fprintf (dump_file
, "Setting dest_lattice to bottom, because type of "
1831 "param %i of %s is NULL or unsuitable for bits propagation\n",
1832 idx
, cs
->callee
->name ());
1834 return dest_lattice
->set_to_bottom ();
1837 unsigned precision
= TYPE_PRECISION (parm_type
);
1838 signop sgn
= TYPE_SIGN (parm_type
);
1840 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1841 || jfunc
->type
== IPA_JF_ANCESTOR
)
1843 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1844 tree operand
= NULL_TREE
;
1845 enum tree_code code
;
1848 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1850 code
= ipa_get_jf_pass_through_operation (jfunc
);
1851 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1852 if (code
!= NOP_EXPR
)
1853 operand
= ipa_get_jf_pass_through_operand (jfunc
);
1857 code
= POINTER_PLUS_EXPR
;
1858 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1859 unsigned HOST_WIDE_INT offset
= ipa_get_jf_ancestor_offset (jfunc
) / BITS_PER_UNIT
;
1860 operand
= build_int_cstu (size_type_node
, offset
);
1863 class ipcp_param_lattices
*src_lats
1864 = ipa_get_parm_lattices (caller_info
, src_idx
);
1866 /* Try to propagate bits if src_lattice is bottom, but jfunc is known.
1872 Assume lattice for x is bottom, however we can still propagate
1873 result of x & 0xff == 0xff, which gets computed during ccp1 pass
1874 and we store it in jump function during analysis stage. */
1876 if (src_lats
->bits_lattice
.bottom_p ()
1878 return dest_lattice
->meet_with (jfunc
->bits
->value
, jfunc
->bits
->mask
,
1881 return dest_lattice
->meet_with (src_lats
->bits_lattice
, precision
, sgn
,
1885 else if (jfunc
->type
== IPA_JF_ANCESTOR
)
1886 return dest_lattice
->set_to_bottom ();
1887 else if (jfunc
->bits
)
1888 return dest_lattice
->meet_with (jfunc
->bits
->value
, jfunc
->bits
->mask
,
1891 return dest_lattice
->set_to_bottom ();
1894 /* Emulate effects of unary OPERATION and/or conversion from SRC_TYPE to
1895 DST_TYPE on value range in SRC_VR and store it to DST_VR. Return true if
1896 the result is a range or an anti-range. */
1899 ipa_vr_operation_and_type_effects (value_range_base
*dst_vr
,
1900 value_range_base
*src_vr
,
1901 enum tree_code operation
,
1902 tree dst_type
, tree src_type
)
1904 extract_range_from_unary_expr (dst_vr
, operation
, dst_type
,
1906 if (dst_vr
->varying_p () || dst_vr
->undefined_p ())
1911 /* Propagate value range across jump function JFUNC that is associated with
1912 edge CS with param of callee of PARAM_TYPE and update DEST_PLATS
1916 propagate_vr_across_jump_function (cgraph_edge
*cs
, ipa_jump_func
*jfunc
,
1917 class ipcp_param_lattices
*dest_plats
,
1920 ipcp_vr_lattice
*dest_lat
= &dest_plats
->m_value_range
;
1922 if (dest_lat
->bottom_p ())
1926 || (!INTEGRAL_TYPE_P (param_type
)
1927 && !POINTER_TYPE_P (param_type
)))
1928 return dest_lat
->set_to_bottom ();
1930 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1932 enum tree_code operation
= ipa_get_jf_pass_through_operation (jfunc
);
1934 if (TREE_CODE_CLASS (operation
) == tcc_unary
)
1936 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1937 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1938 tree operand_type
= ipa_get_type (caller_info
, src_idx
);
1939 class ipcp_param_lattices
*src_lats
1940 = ipa_get_parm_lattices (caller_info
, src_idx
);
1942 if (src_lats
->m_value_range
.bottom_p ())
1943 return dest_lat
->set_to_bottom ();
1944 value_range_base vr
;
1945 if (ipa_vr_operation_and_type_effects (&vr
,
1946 &src_lats
->m_value_range
.m_vr
,
1947 operation
, param_type
,
1949 return dest_lat
->meet_with (&vr
);
1952 else if (jfunc
->type
== IPA_JF_CONST
)
1954 tree val
= ipa_get_jf_constant (jfunc
);
1955 if (TREE_CODE (val
) == INTEGER_CST
)
1957 val
= fold_convert (param_type
, val
);
1958 if (TREE_OVERFLOW_P (val
))
1959 val
= drop_tree_overflow (val
);
1961 value_range_base
tmpvr (VR_RANGE
, val
, val
);
1962 return dest_lat
->meet_with (&tmpvr
);
1966 value_range_base vr
;
1968 && ipa_vr_operation_and_type_effects (&vr
, jfunc
->m_vr
, NOP_EXPR
,
1970 jfunc
->m_vr
->type ()))
1971 return dest_lat
->meet_with (&vr
);
1973 return dest_lat
->set_to_bottom ();
1976 /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
1977 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
1978 other cases, return false). If there are no aggregate items, set
1979 aggs_by_ref to NEW_AGGS_BY_REF. */
1982 set_check_aggs_by_ref (class ipcp_param_lattices
*dest_plats
,
1983 bool new_aggs_by_ref
)
1985 if (dest_plats
->aggs
)
1987 if (dest_plats
->aggs_by_ref
!= new_aggs_by_ref
)
1989 set_agg_lats_to_bottom (dest_plats
);
1994 dest_plats
->aggs_by_ref
= new_aggs_by_ref
;
1998 /* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
1999 already existing lattice for the given OFFSET and SIZE, marking all skipped
2000 lattices as containing variable and checking for overlaps. If there is no
2001 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
2002 it with offset, size and contains_variable to PRE_EXISTING, and return true,
2003 unless there are too many already. If there are two many, return false. If
2004 there are overlaps turn whole DEST_PLATS to bottom and return false. If any
2005 skipped lattices were newly marked as containing variable, set *CHANGE to
2009 merge_agg_lats_step (class ipcp_param_lattices
*dest_plats
,
2010 HOST_WIDE_INT offset
, HOST_WIDE_INT val_size
,
2011 struct ipcp_agg_lattice
***aglat
,
2012 bool pre_existing
, bool *change
)
2014 gcc_checking_assert (offset
>= 0);
2016 while (**aglat
&& (**aglat
)->offset
< offset
)
2018 if ((**aglat
)->offset
+ (**aglat
)->size
> offset
)
2020 set_agg_lats_to_bottom (dest_plats
);
2023 *change
|= (**aglat
)->set_contains_variable ();
2024 *aglat
= &(**aglat
)->next
;
2027 if (**aglat
&& (**aglat
)->offset
== offset
)
2029 if ((**aglat
)->size
!= val_size
)
2031 set_agg_lats_to_bottom (dest_plats
);
2034 gcc_assert (!(**aglat
)->next
2035 || (**aglat
)->next
->offset
>= offset
+ val_size
);
2040 struct ipcp_agg_lattice
*new_al
;
2042 if (**aglat
&& (**aglat
)->offset
< offset
+ val_size
)
2044 set_agg_lats_to_bottom (dest_plats
);
2047 if (dest_plats
->aggs_count
== PARAM_VALUE (PARAM_IPA_MAX_AGG_ITEMS
))
2049 dest_plats
->aggs_count
++;
2050 new_al
= ipcp_agg_lattice_pool
.allocate ();
2051 memset (new_al
, 0, sizeof (*new_al
));
2053 new_al
->offset
= offset
;
2054 new_al
->size
= val_size
;
2055 new_al
->contains_variable
= pre_existing
;
2057 new_al
->next
= **aglat
;
2063 /* Set all AGLAT and all other aggregate lattices reachable by next pointers as
2064 containing an unknown value. */
2067 set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice
*aglat
)
2072 ret
|= aglat
->set_contains_variable ();
2073 aglat
= aglat
->next
;
2078 /* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
2079 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source
2080 parameter used for lattice value sources. Return true if DEST_PLATS changed
2084 merge_aggregate_lattices (struct cgraph_edge
*cs
,
2085 class ipcp_param_lattices
*dest_plats
,
2086 class ipcp_param_lattices
*src_plats
,
2087 int src_idx
, HOST_WIDE_INT offset_delta
)
2089 bool pre_existing
= dest_plats
->aggs
!= NULL
;
2090 struct ipcp_agg_lattice
**dst_aglat
;
2093 if (set_check_aggs_by_ref (dest_plats
, src_plats
->aggs_by_ref
))
2095 if (src_plats
->aggs_bottom
)
2096 return set_agg_lats_contain_variable (dest_plats
);
2097 if (src_plats
->aggs_contain_variable
)
2098 ret
|= set_agg_lats_contain_variable (dest_plats
);
2099 dst_aglat
= &dest_plats
->aggs
;
2101 for (struct ipcp_agg_lattice
*src_aglat
= src_plats
->aggs
;
2103 src_aglat
= src_aglat
->next
)
2105 HOST_WIDE_INT new_offset
= src_aglat
->offset
- offset_delta
;
2109 if (merge_agg_lats_step (dest_plats
, new_offset
, src_aglat
->size
,
2110 &dst_aglat
, pre_existing
, &ret
))
2112 struct ipcp_agg_lattice
*new_al
= *dst_aglat
;
2114 dst_aglat
= &(*dst_aglat
)->next
;
2115 if (src_aglat
->bottom
)
2117 ret
|= new_al
->set_contains_variable ();
2120 if (src_aglat
->contains_variable
)
2121 ret
|= new_al
->set_contains_variable ();
2122 for (ipcp_value
<tree
> *val
= src_aglat
->values
;
2125 ret
|= new_al
->add_value (val
->value
, cs
, val
, src_idx
,
2128 else if (dest_plats
->aggs_bottom
)
2131 ret
|= set_chain_of_aglats_contains_variable (*dst_aglat
);
2135 /* Determine whether there is anything to propagate FROM SRC_PLATS through a
2136 pass-through JFUNC and if so, whether it has conform and conforms to the
2137 rules about propagating values passed by reference. */
2140 agg_pass_through_permissible_p (class ipcp_param_lattices
*src_plats
,
2141 struct ipa_jump_func
*jfunc
)
2143 return src_plats
->aggs
2144 && (!src_plats
->aggs_by_ref
2145 || ipa_get_jf_pass_through_agg_preserved (jfunc
));
2148 /* Propagate scalar values across jump function JFUNC that is associated with
2149 edge CS and put the values into DEST_LAT. */
2152 propagate_aggs_across_jump_function (struct cgraph_edge
*cs
,
2153 struct ipa_jump_func
*jfunc
,
2154 class ipcp_param_lattices
*dest_plats
)
2158 if (dest_plats
->aggs_bottom
)
2161 if (jfunc
->type
== IPA_JF_PASS_THROUGH
2162 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
2164 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2165 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
2166 class ipcp_param_lattices
*src_plats
;
2168 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2169 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
2171 /* Currently we do not produce clobber aggregate jump
2172 functions, replace with merging when we do. */
2173 gcc_assert (!jfunc
->agg
.items
);
2174 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
,
2178 ret
|= set_agg_lats_contain_variable (dest_plats
);
2180 else if (jfunc
->type
== IPA_JF_ANCESTOR
2181 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
2183 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2184 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
2185 class ipcp_param_lattices
*src_plats
;
2187 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2188 if (src_plats
->aggs
&& src_plats
->aggs_by_ref
)
2190 /* Currently we do not produce clobber aggregate jump
2191 functions, replace with merging when we do. */
2192 gcc_assert (!jfunc
->agg
.items
);
2193 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
, src_idx
,
2194 ipa_get_jf_ancestor_offset (jfunc
));
2196 else if (!src_plats
->aggs_by_ref
)
2197 ret
|= set_agg_lats_to_bottom (dest_plats
);
2199 ret
|= set_agg_lats_contain_variable (dest_plats
);
2201 else if (jfunc
->agg
.items
)
2203 bool pre_existing
= dest_plats
->aggs
!= NULL
;
2204 struct ipcp_agg_lattice
**aglat
= &dest_plats
->aggs
;
2205 struct ipa_agg_jf_item
*item
;
2208 if (set_check_aggs_by_ref (dest_plats
, jfunc
->agg
.by_ref
))
2211 FOR_EACH_VEC_ELT (*jfunc
->agg
.items
, i
, item
)
2213 HOST_WIDE_INT val_size
;
2215 if (item
->offset
< 0)
2217 gcc_checking_assert (is_gimple_ip_invariant (item
->value
));
2218 val_size
= tree_to_uhwi (TYPE_SIZE (TREE_TYPE (item
->value
)));
2220 if (merge_agg_lats_step (dest_plats
, item
->offset
, val_size
,
2221 &aglat
, pre_existing
, &ret
))
2223 ret
|= (*aglat
)->add_value (item
->value
, cs
, NULL
, 0, 0);
2224 aglat
= &(*aglat
)->next
;
2226 else if (dest_plats
->aggs_bottom
)
2230 ret
|= set_chain_of_aglats_contains_variable (*aglat
);
2233 ret
|= set_agg_lats_contain_variable (dest_plats
);
2238 /* Return true if on the way cfrom CS->caller to the final (non-alias and
2239 non-thunk) destination, the call passes through a thunk. */
2242 call_passes_through_thunk_p (cgraph_edge
*cs
)
2244 cgraph_node
*alias_or_thunk
= cs
->callee
;
2245 while (alias_or_thunk
->alias
)
2246 alias_or_thunk
= alias_or_thunk
->get_alias_target ();
2247 return alias_or_thunk
->thunk
.thunk_p
;
2250 /* Propagate constants from the caller to the callee of CS. INFO describes the
2254 propagate_constants_across_call (struct cgraph_edge
*cs
)
2256 class ipa_node_params
*callee_info
;
2257 enum availability availability
;
2258 cgraph_node
*callee
;
2259 class ipa_edge_args
*args
;
2261 int i
, args_count
, parms_count
;
2263 callee
= cs
->callee
->function_symbol (&availability
);
2264 if (!callee
->definition
)
2266 gcc_checking_assert (callee
->has_gimple_body_p ());
2267 callee_info
= IPA_NODE_REF (callee
);
2269 args
= IPA_EDGE_REF (cs
);
2270 args_count
= ipa_get_cs_argument_count (args
);
2271 parms_count
= ipa_get_param_count (callee_info
);
2272 if (parms_count
== 0)
2275 /* If this call goes through a thunk we must not propagate to the first (0th)
2276 parameter. However, we might need to uncover a thunk from below a series
2277 of aliases first. */
2278 if (call_passes_through_thunk_p (cs
))
2280 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
2287 for (; (i
< args_count
) && (i
< parms_count
); i
++)
2289 struct ipa_jump_func
*jump_func
= ipa_get_ith_jump_func (args
, i
);
2290 class ipcp_param_lattices
*dest_plats
;
2291 tree param_type
= ipa_get_type (callee_info
, i
);
2293 dest_plats
= ipa_get_parm_lattices (callee_info
, i
);
2294 if (availability
== AVAIL_INTERPOSABLE
)
2295 ret
|= set_all_contains_variable (dest_plats
);
2298 ret
|= propagate_scalar_across_jump_function (cs
, jump_func
,
2299 &dest_plats
->itself
,
2301 ret
|= propagate_context_across_jump_function (cs
, jump_func
, i
,
2302 &dest_plats
->ctxlat
);
2304 |= propagate_bits_across_jump_function (cs
, i
, jump_func
,
2305 &dest_plats
->bits_lattice
);
2306 ret
|= propagate_aggs_across_jump_function (cs
, jump_func
,
2308 if (opt_for_fn (callee
->decl
, flag_ipa_vrp
))
2309 ret
|= propagate_vr_across_jump_function (cs
, jump_func
,
2310 dest_plats
, param_type
);
2312 ret
|= dest_plats
->m_value_range
.set_to_bottom ();
2315 for (; i
< parms_count
; i
++)
2316 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
, i
));
2321 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
2322 KNOWN_CONTEXTS, KNOWN_AGGS or AGG_REPS return the destination. The latter
2323 three can be NULL. If AGG_REPS is not NULL, KNOWN_AGGS is ignored. */
2326 ipa_get_indirect_edge_target_1 (struct cgraph_edge
*ie
,
2327 vec
<tree
> known_csts
,
2328 vec
<ipa_polymorphic_call_context
> known_contexts
,
2329 vec
<ipa_agg_jump_function_p
> known_aggs
,
2330 struct ipa_agg_replacement_value
*agg_reps
,
2333 int param_index
= ie
->indirect_info
->param_index
;
2334 HOST_WIDE_INT anc_offset
;
2338 *speculative
= false;
2340 if (param_index
== -1
2341 || known_csts
.length () <= (unsigned int) param_index
)
2344 if (!ie
->indirect_info
->polymorphic
)
2348 if (ie
->indirect_info
->agg_contents
)
2351 if (agg_reps
&& ie
->indirect_info
->guaranteed_unmodified
)
2355 if (agg_reps
->index
== param_index
2356 && agg_reps
->offset
== ie
->indirect_info
->offset
2357 && agg_reps
->by_ref
== ie
->indirect_info
->by_ref
)
2359 t
= agg_reps
->value
;
2362 agg_reps
= agg_reps
->next
;
2367 struct ipa_agg_jump_function
*agg
;
2368 if (known_aggs
.length () > (unsigned int) param_index
)
2369 agg
= known_aggs
[param_index
];
2372 bool from_global_constant
;
2373 t
= ipa_find_agg_cst_for_param (agg
, known_csts
[param_index
],
2374 ie
->indirect_info
->offset
,
2375 ie
->indirect_info
->by_ref
,
2376 &from_global_constant
);
2378 && !from_global_constant
2379 && !ie
->indirect_info
->guaranteed_unmodified
)
2384 t
= known_csts
[param_index
];
2387 && TREE_CODE (t
) == ADDR_EXPR
2388 && TREE_CODE (TREE_OPERAND (t
, 0)) == FUNCTION_DECL
)
2389 return TREE_OPERAND (t
, 0);
2394 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize
))
2397 gcc_assert (!ie
->indirect_info
->agg_contents
);
2398 anc_offset
= ie
->indirect_info
->offset
;
2402 /* Try to work out value of virtual table pointer value in replacements. */
2403 if (!t
&& agg_reps
&& !ie
->indirect_info
->by_ref
)
2407 if (agg_reps
->index
== param_index
2408 && agg_reps
->offset
== ie
->indirect_info
->offset
2409 && agg_reps
->by_ref
)
2411 t
= agg_reps
->value
;
2414 agg_reps
= agg_reps
->next
;
2418 /* Try to work out value of virtual table pointer value in known
2419 aggregate values. */
2420 if (!t
&& known_aggs
.length () > (unsigned int) param_index
2421 && !ie
->indirect_info
->by_ref
)
2423 struct ipa_agg_jump_function
*agg
;
2424 agg
= known_aggs
[param_index
];
2425 t
= ipa_find_agg_cst_for_param (agg
, known_csts
[param_index
],
2426 ie
->indirect_info
->offset
, true);
2429 /* If we found the virtual table pointer, lookup the target. */
2433 unsigned HOST_WIDE_INT offset
;
2434 if (vtable_pointer_value_to_vtable (t
, &vtable
, &offset
))
2437 target
= gimple_get_virt_method_for_vtable (ie
->indirect_info
->otr_token
,
2438 vtable
, offset
, &can_refer
);
2442 || fndecl_built_in_p (target
, BUILT_IN_UNREACHABLE
)
2443 || !possible_polymorphic_call_target_p
2444 (ie
, cgraph_node::get (target
)))
2446 /* Do not speculate builtin_unreachable, it is stupid! */
2447 if (ie
->indirect_info
->vptr_changed
)
2449 target
= ipa_impossible_devirt_target (ie
, target
);
2451 *speculative
= ie
->indirect_info
->vptr_changed
;
2458 /* Do we know the constant value of pointer? */
2460 t
= known_csts
[param_index
];
2462 gcc_checking_assert (!t
|| TREE_CODE (t
) != TREE_BINFO
);
2464 ipa_polymorphic_call_context context
;
2465 if (known_contexts
.length () > (unsigned int) param_index
)
2467 context
= known_contexts
[param_index
];
2468 context
.offset_by (anc_offset
);
2469 if (ie
->indirect_info
->vptr_changed
)
2470 context
.possible_dynamic_type_change (ie
->in_polymorphic_cdtor
,
2471 ie
->indirect_info
->otr_type
);
2474 ipa_polymorphic_call_context ctx2
= ipa_polymorphic_call_context
2475 (t
, ie
->indirect_info
->otr_type
, anc_offset
);
2476 if (!ctx2
.useless_p ())
2477 context
.combine_with (ctx2
, ie
->indirect_info
->otr_type
);
2482 context
= ipa_polymorphic_call_context (t
, ie
->indirect_info
->otr_type
,
2484 if (ie
->indirect_info
->vptr_changed
)
2485 context
.possible_dynamic_type_change (ie
->in_polymorphic_cdtor
,
2486 ie
->indirect_info
->otr_type
);
2491 vec
<cgraph_node
*>targets
;
2494 targets
= possible_polymorphic_call_targets
2495 (ie
->indirect_info
->otr_type
,
2496 ie
->indirect_info
->otr_token
,
2498 if (!final
|| targets
.length () > 1)
2500 struct cgraph_node
*node
;
2503 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize_speculatively
)
2504 || ie
->speculative
|| !ie
->maybe_hot_p ())
2506 node
= try_speculative_devirtualization (ie
->indirect_info
->otr_type
,
2507 ie
->indirect_info
->otr_token
,
2511 *speculative
= true;
2512 target
= node
->decl
;
2519 *speculative
= false;
2520 if (targets
.length () == 1)
2521 target
= targets
[0]->decl
;
2523 target
= ipa_impossible_devirt_target (ie
, NULL_TREE
);
2526 if (target
&& !possible_polymorphic_call_target_p (ie
,
2527 cgraph_node::get (target
)))
2531 target
= ipa_impossible_devirt_target (ie
, target
);
2538 /* If an indirect edge IE can be turned into a direct one based on KNOWN_CSTS,
2539 KNOWN_CONTEXTS (which can be vNULL) or KNOWN_AGGS (which also can be vNULL)
2540 return the destination. */
2543 ipa_get_indirect_edge_target (struct cgraph_edge
*ie
,
2544 vec
<tree
> known_csts
,
2545 vec
<ipa_polymorphic_call_context
> known_contexts
,
2546 vec
<ipa_agg_jump_function_p
> known_aggs
,
2549 return ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
2550 known_aggs
, NULL
, speculative
);
2553 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
2554 and KNOWN_CONTEXTS. */
2557 devirtualization_time_bonus (struct cgraph_node
*node
,
2558 vec
<tree
> known_csts
,
2559 vec
<ipa_polymorphic_call_context
> known_contexts
,
2560 vec
<ipa_agg_jump_function_p
> known_aggs
)
2562 struct cgraph_edge
*ie
;
2565 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
2567 struct cgraph_node
*callee
;
2568 class ipa_fn_summary
*isummary
;
2569 enum availability avail
;
2573 target
= ipa_get_indirect_edge_target (ie
, known_csts
, known_contexts
,
2574 known_aggs
, &speculative
);
2578 /* Only bare minimum benefit for clearly un-inlineable targets. */
2580 callee
= cgraph_node::get (target
);
2581 if (!callee
|| !callee
->definition
)
2583 callee
= callee
->function_symbol (&avail
);
2584 if (avail
< AVAIL_AVAILABLE
)
2586 isummary
= ipa_fn_summaries
->get (callee
);
2587 if (!isummary
->inlinable
)
2590 /* FIXME: The values below need re-considering and perhaps also
2591 integrating into the cost metrics, at lest in some very basic way. */
2592 if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 4)
2593 res
+= 31 / ((int)speculative
+ 1);
2594 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 2)
2595 res
+= 15 / ((int)speculative
+ 1);
2596 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
2597 || DECL_DECLARED_INLINE_P (callee
->decl
))
2598 res
+= 7 / ((int)speculative
+ 1);
2604 /* Return time bonus incurred because of HINTS. */
2607 hint_time_bonus (ipa_hints hints
)
2610 if (hints
& (INLINE_HINT_loop_iterations
| INLINE_HINT_loop_stride
))
2611 result
+= PARAM_VALUE (PARAM_IPA_CP_LOOP_HINT_BONUS
);
2615 /* If there is a reason to penalize the function described by INFO in the
2616 cloning goodness evaluation, do so. */
2618 static inline int64_t
2619 incorporate_penalties (ipa_node_params
*info
, int64_t evaluation
)
2621 if (info
->node_within_scc
)
2622 evaluation
= (evaluation
2623 * (100 - PARAM_VALUE (PARAM_IPA_CP_RECURSION_PENALTY
))) / 100;
2625 if (info
->node_calling_single_call
)
2626 evaluation
= (evaluation
2627 * (100 - PARAM_VALUE (PARAM_IPA_CP_SINGLE_CALL_PENALTY
)))
2633 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
2634 and SIZE_COST and with the sum of frequencies of incoming edges to the
2635 potential new clone in FREQUENCIES. */
2638 good_cloning_opportunity_p (struct cgraph_node
*node
, int time_benefit
,
2639 int freq_sum
, profile_count count_sum
, int size_cost
)
2641 if (time_benefit
== 0
2642 || !opt_for_fn (node
->decl
, flag_ipa_cp_clone
)
2643 || node
->optimize_for_size_p ())
2646 gcc_assert (size_cost
> 0);
2648 class ipa_node_params
*info
= IPA_NODE_REF (node
);
2649 if (max_count
> profile_count::zero ())
2651 int factor
= RDIV (count_sum
.probability_in
2652 (max_count
).to_reg_br_prob_base ()
2653 * 1000, REG_BR_PROB_BASE
);
2654 int64_t evaluation
= (((int64_t) time_benefit
* factor
)
2656 evaluation
= incorporate_penalties (info
, evaluation
);
2658 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2660 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
2661 "size: %i, count_sum: ", time_benefit
, size_cost
);
2662 count_sum
.dump (dump_file
);
2663 fprintf (dump_file
, "%s%s) -> evaluation: " "%" PRId64
2664 ", threshold: %i\n",
2665 info
->node_within_scc
? ", scc" : "",
2666 info
->node_calling_single_call
? ", single_call" : "",
2667 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
2670 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
2674 int64_t evaluation
= (((int64_t) time_benefit
* freq_sum
)
2676 evaluation
= incorporate_penalties (info
, evaluation
);
2678 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2679 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
2680 "size: %i, freq_sum: %i%s%s) -> evaluation: "
2681 "%" PRId64
", threshold: %i\n",
2682 time_benefit
, size_cost
, freq_sum
,
2683 info
->node_within_scc
? ", scc" : "",
2684 info
->node_calling_single_call
? ", single_call" : "",
2685 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
2687 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
2691 /* Return all context independent values from aggregate lattices in PLATS in a
2692 vector. Return NULL if there are none. */
2694 static vec
<ipa_agg_jf_item
, va_gc
> *
2695 context_independent_aggregate_values (class ipcp_param_lattices
*plats
)
2697 vec
<ipa_agg_jf_item
, va_gc
> *res
= NULL
;
2699 if (plats
->aggs_bottom
2700 || plats
->aggs_contain_variable
2701 || plats
->aggs_count
== 0)
2704 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
;
2706 aglat
= aglat
->next
)
2707 if (aglat
->is_single_const ())
2709 struct ipa_agg_jf_item item
;
2710 item
.offset
= aglat
->offset
;
2711 item
.value
= aglat
->values
->value
;
2712 vec_safe_push (res
, item
);
2717 /* Allocate KNOWN_CSTS, KNOWN_CONTEXTS and, if non-NULL, KNOWN_AGGS and
2718 populate them with values of parameters that are known independent of the
2719 context. INFO describes the function. If REMOVABLE_PARAMS_COST is
2720 non-NULL, the movement cost of all removable parameters will be stored in
2724 gather_context_independent_values (class ipa_node_params
*info
,
2725 vec
<tree
> *known_csts
,
2726 vec
<ipa_polymorphic_call_context
>
2728 vec
<ipa_agg_jump_function
> *known_aggs
,
2729 int *removable_params_cost
)
2731 int i
, count
= ipa_get_param_count (info
);
2734 known_csts
->create (0);
2735 known_contexts
->create (0);
2736 known_csts
->safe_grow_cleared (count
);
2737 known_contexts
->safe_grow_cleared (count
);
2740 known_aggs
->create (0);
2741 known_aggs
->safe_grow_cleared (count
);
2744 if (removable_params_cost
)
2745 *removable_params_cost
= 0;
2747 for (i
= 0; i
< count
; i
++)
2749 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2750 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
2752 if (lat
->is_single_const ())
2754 ipcp_value
<tree
> *val
= lat
->values
;
2755 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
2756 (*known_csts
)[i
] = val
->value
;
2757 if (removable_params_cost
)
2758 *removable_params_cost
2759 += estimate_move_cost (TREE_TYPE (val
->value
), false);
2762 else if (removable_params_cost
2763 && !ipa_is_param_used (info
, i
))
2764 *removable_params_cost
2765 += ipa_get_param_move_cost (info
, i
);
2767 if (!ipa_is_param_used (info
, i
))
2770 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
2771 /* Do not account known context as reason for cloning. We can see
2772 if it permits devirtualization. */
2773 if (ctxlat
->is_single_const ())
2774 (*known_contexts
)[i
] = ctxlat
->values
->value
;
2778 vec
<ipa_agg_jf_item
, va_gc
> *agg_items
;
2779 struct ipa_agg_jump_function
*ajf
;
2781 agg_items
= context_independent_aggregate_values (plats
);
2782 ajf
= &(*known_aggs
)[i
];
2783 ajf
->items
= agg_items
;
2784 ajf
->by_ref
= plats
->aggs_by_ref
;
2785 ret
|= agg_items
!= NULL
;
2792 /* The current interface in ipa-inline-analysis requires a pointer vector.
2795 FIXME: That interface should be re-worked, this is slightly silly. Still,
2796 I'd like to discuss how to change it first and this demonstrates the
2799 static vec
<ipa_agg_jump_function_p
>
2800 agg_jmp_p_vec_for_t_vec (vec
<ipa_agg_jump_function
> known_aggs
)
2802 vec
<ipa_agg_jump_function_p
> ret
;
2803 struct ipa_agg_jump_function
*ajf
;
2806 ret
.create (known_aggs
.length ());
2807 FOR_EACH_VEC_ELT (known_aggs
, i
, ajf
)
2808 ret
.quick_push (ajf
);
2812 /* Perform time and size measurement of NODE with the context given in
2813 KNOWN_CSTS, KNOWN_CONTEXTS and KNOWN_AGGS, calculate the benefit and cost
2814 given BASE_TIME of the node without specialization, REMOVABLE_PARAMS_COST of
2815 all context-independent removable parameters and EST_MOVE_COST of estimated
2816 movement of the considered parameter and store it into VAL. */
2819 perform_estimation_of_a_value (cgraph_node
*node
, vec
<tree
> known_csts
,
2820 vec
<ipa_polymorphic_call_context
> known_contexts
,
2821 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
,
2822 int removable_params_cost
,
2823 int est_move_cost
, ipcp_value_base
*val
)
2825 int size
, time_benefit
;
2826 sreal time
, base_time
;
2829 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
2830 known_aggs_ptrs
, &size
, &time
,
2831 &base_time
, &hints
);
2833 if (base_time
> 65535)
2836 /* Extern inline functions have no cloning local time benefits because they
2837 will be inlined anyway. The only reason to clone them is if it enables
2838 optimization in any of the functions they call. */
2839 if (DECL_EXTERNAL (node
->decl
) && DECL_DECLARED_INLINE_P (node
->decl
))
2842 time_benefit
= base_time
.to_int ()
2843 + devirtualization_time_bonus (node
, known_csts
, known_contexts
,
2845 + hint_time_bonus (hints
)
2846 + removable_params_cost
+ est_move_cost
;
2848 gcc_checking_assert (size
>=0);
2849 /* The inliner-heuristics based estimates may think that in certain
2850 contexts some functions do not have any size at all but we want
2851 all specializations to have at least a tiny cost, not least not to
2856 val
->local_time_benefit
= time_benefit
;
2857 val
->local_size_cost
= size
;
2860 /* Iterate over known values of parameters of NODE and estimate the local
2861 effects in terms of time and size they have. */
2864 estimate_local_effects (struct cgraph_node
*node
)
2866 class ipa_node_params
*info
= IPA_NODE_REF (node
);
2867 int i
, count
= ipa_get_param_count (info
);
2868 vec
<tree
> known_csts
;
2869 vec
<ipa_polymorphic_call_context
> known_contexts
;
2870 vec
<ipa_agg_jump_function
> known_aggs
;
2871 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
;
2873 int removable_params_cost
;
2875 if (!count
|| !ipcp_versionable_function_p (node
))
2878 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2879 fprintf (dump_file
, "\nEstimating effects for %s.\n", node
->dump_name ());
2881 always_const
= gather_context_independent_values (info
, &known_csts
,
2882 &known_contexts
, &known_aggs
,
2883 &removable_params_cost
);
2884 known_aggs_ptrs
= agg_jmp_p_vec_for_t_vec (known_aggs
);
2885 int devirt_bonus
= devirtualization_time_bonus (node
, known_csts
,
2886 known_contexts
, known_aggs_ptrs
);
2887 if (always_const
|| devirt_bonus
2888 || (removable_params_cost
&& node
->local
.can_change_signature
))
2890 struct caller_statistics stats
;
2892 sreal time
, base_time
;
2895 init_caller_stats (&stats
);
2896 node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
2898 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
2899 known_aggs_ptrs
, &size
, &time
,
2900 &base_time
, &hints
);
2901 time
-= devirt_bonus
;
2902 time
-= hint_time_bonus (hints
);
2903 time
-= removable_params_cost
;
2904 size
-= stats
.n_calls
* removable_params_cost
;
2907 fprintf (dump_file
, " - context independent values, size: %i, "
2908 "time_benefit: %f\n", size
, (base_time
- time
).to_double ());
2910 if (size
<= 0 || node
->local
.local
)
2912 info
->do_clone_for_all_contexts
= true;
2915 fprintf (dump_file
, " Decided to specialize for all "
2916 "known contexts, code not going to grow.\n");
2918 else if (good_cloning_opportunity_p (node
,
2919 MIN ((base_time
- time
).to_int (),
2921 stats
.freq_sum
, stats
.count_sum
,
2924 if (size
+ overall_size
<= max_new_size
)
2926 info
->do_clone_for_all_contexts
= true;
2927 overall_size
+= size
;
2930 fprintf (dump_file
, " Decided to specialize for all "
2931 "known contexts, growth deemed beneficial.\n");
2933 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2934 fprintf (dump_file
, " Not cloning for all contexts because "
2935 "max_new_size would be reached with %li.\n",
2936 size
+ overall_size
);
2938 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2939 fprintf (dump_file
, " Not cloning for all contexts because "
2940 "!good_cloning_opportunity_p.\n");
2944 for (i
= 0; i
< count
; i
++)
2946 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2947 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
2948 ipcp_value
<tree
> *val
;
2955 for (val
= lat
->values
; val
; val
= val
->next
)
2957 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
2958 known_csts
[i
] = val
->value
;
2960 int emc
= estimate_move_cost (TREE_TYPE (val
->value
), true);
2961 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
2963 removable_params_cost
, emc
, val
);
2965 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2967 fprintf (dump_file
, " - estimates for value ");
2968 print_ipcp_constant_value (dump_file
, val
->value
);
2969 fprintf (dump_file
, " for ");
2970 ipa_dump_param (dump_file
, info
, i
);
2971 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
2972 val
->local_time_benefit
, val
->local_size_cost
);
2975 known_csts
[i
] = NULL_TREE
;
2978 for (i
= 0; i
< count
; i
++)
2980 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2982 if (!plats
->virt_call
)
2985 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
2986 ipcp_value
<ipa_polymorphic_call_context
> *val
;
2990 || !known_contexts
[i
].useless_p ())
2993 for (val
= ctxlat
->values
; val
; val
= val
->next
)
2995 known_contexts
[i
] = val
->value
;
2996 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
2998 removable_params_cost
, 0, val
);
3000 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3002 fprintf (dump_file
, " - estimates for polymorphic context ");
3003 print_ipcp_constant_value (dump_file
, val
->value
);
3004 fprintf (dump_file
, " for ");
3005 ipa_dump_param (dump_file
, info
, i
);
3006 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
3007 val
->local_time_benefit
, val
->local_size_cost
);
3010 known_contexts
[i
] = ipa_polymorphic_call_context ();
3013 for (i
= 0; i
< count
; i
++)
3015 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3016 struct ipa_agg_jump_function
*ajf
;
3017 struct ipcp_agg_lattice
*aglat
;
3019 if (plats
->aggs_bottom
|| !plats
->aggs
)
3022 ajf
= &known_aggs
[i
];
3023 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3025 ipcp_value
<tree
> *val
;
3026 if (aglat
->bottom
|| !aglat
->values
3027 /* If the following is true, the one value is in known_aggs. */
3028 || (!plats
->aggs_contain_variable
3029 && aglat
->is_single_const ()))
3032 for (val
= aglat
->values
; val
; val
= val
->next
)
3034 struct ipa_agg_jf_item item
;
3036 item
.offset
= aglat
->offset
;
3037 item
.value
= val
->value
;
3038 vec_safe_push (ajf
->items
, item
);
3040 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
3042 removable_params_cost
, 0, val
);
3044 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3046 fprintf (dump_file
, " - estimates for value ");
3047 print_ipcp_constant_value (dump_file
, val
->value
);
3048 fprintf (dump_file
, " for ");
3049 ipa_dump_param (dump_file
, info
, i
);
3050 fprintf (dump_file
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
3051 "]: time_benefit: %i, size: %i\n",
3052 plats
->aggs_by_ref
? "ref " : "",
3054 val
->local_time_benefit
, val
->local_size_cost
);
3062 for (i
= 0; i
< count
; i
++)
3063 vec_free (known_aggs
[i
].items
);
3065 known_csts
.release ();
3066 known_contexts
.release ();
3067 known_aggs
.release ();
3068 known_aggs_ptrs
.release ();
3072 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
3073 topological sort of values. */
3075 template <typename valtype
>
3077 value_topo_info
<valtype
>::add_val (ipcp_value
<valtype
> *cur_val
)
3079 ipcp_value_source
<valtype
> *src
;
3085 cur_val
->dfs
= dfs_counter
;
3086 cur_val
->low_link
= dfs_counter
;
3088 cur_val
->topo_next
= stack
;
3090 cur_val
->on_stack
= true;
3092 for (src
= cur_val
->sources
; src
; src
= src
->next
)
3095 if (src
->val
->dfs
== 0)
3098 if (src
->val
->low_link
< cur_val
->low_link
)
3099 cur_val
->low_link
= src
->val
->low_link
;
3101 else if (src
->val
->on_stack
3102 && src
->val
->dfs
< cur_val
->low_link
)
3103 cur_val
->low_link
= src
->val
->dfs
;
3106 if (cur_val
->dfs
== cur_val
->low_link
)
3108 ipcp_value
<valtype
> *v
, *scc_list
= NULL
;
3113 stack
= v
->topo_next
;
3114 v
->on_stack
= false;
3116 v
->scc_next
= scc_list
;
3119 while (v
!= cur_val
);
3121 cur_val
->topo_next
= values_topo
;
3122 values_topo
= cur_val
;
3126 /* Add all values in lattices associated with NODE to the topological sort if
3127 they are not there yet. */
3130 add_all_node_vals_to_toposort (cgraph_node
*node
, ipa_topo_info
*topo
)
3132 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3133 int i
, count
= ipa_get_param_count (info
);
3135 for (i
= 0; i
< count
; i
++)
3137 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3138 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
3139 struct ipcp_agg_lattice
*aglat
;
3143 ipcp_value
<tree
> *val
;
3144 for (val
= lat
->values
; val
; val
= val
->next
)
3145 topo
->constants
.add_val (val
);
3148 if (!plats
->aggs_bottom
)
3149 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3152 ipcp_value
<tree
> *val
;
3153 for (val
= aglat
->values
; val
; val
= val
->next
)
3154 topo
->constants
.add_val (val
);
3157 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
3158 if (!ctxlat
->bottom
)
3160 ipcp_value
<ipa_polymorphic_call_context
> *ctxval
;
3161 for (ctxval
= ctxlat
->values
; ctxval
; ctxval
= ctxval
->next
)
3162 topo
->contexts
.add_val (ctxval
);
3167 /* One pass of constants propagation along the call graph edges, from callers
3168 to callees (requires topological ordering in TOPO), iterate over strongly
3169 connected components. */
3172 propagate_constants_topo (class ipa_topo_info
*topo
)
3176 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
3179 struct cgraph_node
*v
, *node
= topo
->order
[i
];
3180 vec
<cgraph_node
*> cycle_nodes
= ipa_get_nodes_in_cycle (node
);
3182 /* First, iteratively propagate within the strongly connected component
3183 until all lattices stabilize. */
3184 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
3185 if (v
->has_gimple_body_p ())
3186 push_node_to_stack (topo
, v
);
3188 v
= pop_node_from_stack (topo
);
3191 struct cgraph_edge
*cs
;
3193 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3194 if (ipa_edge_within_scc (cs
))
3196 IPA_NODE_REF (v
)->node_within_scc
= true;
3197 if (propagate_constants_across_call (cs
))
3198 push_node_to_stack (topo
, cs
->callee
->function_symbol ());
3200 v
= pop_node_from_stack (topo
);
3203 /* Afterwards, propagate along edges leading out of the SCC, calculates
3204 the local effects of the discovered constants and all valid values to
3205 their topological sort. */
3206 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
3207 if (v
->has_gimple_body_p ())
3209 struct cgraph_edge
*cs
;
3211 estimate_local_effects (v
);
3212 add_all_node_vals_to_toposort (v
, topo
);
3213 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3214 if (!ipa_edge_within_scc (cs
))
3215 propagate_constants_across_call (cs
);
3217 cycle_nodes
.release ();
3222 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
3223 the bigger one if otherwise. */
3226 safe_add (int a
, int b
)
3228 if (a
> INT_MAX
/2 || b
> INT_MAX
/2)
3229 return a
> b
? a
: b
;
3235 /* Propagate the estimated effects of individual values along the topological
3236 from the dependent values to those they depend on. */
3238 template <typename valtype
>
3240 value_topo_info
<valtype
>::propagate_effects ()
3242 ipcp_value
<valtype
> *base
;
3244 for (base
= values_topo
; base
; base
= base
->topo_next
)
3246 ipcp_value_source
<valtype
> *src
;
3247 ipcp_value
<valtype
> *val
;
3248 int time
= 0, size
= 0;
3250 for (val
= base
; val
; val
= val
->scc_next
)
3252 time
= safe_add (time
,
3253 val
->local_time_benefit
+ val
->prop_time_benefit
);
3254 size
= safe_add (size
, val
->local_size_cost
+ val
->prop_size_cost
);
3257 for (val
= base
; val
; val
= val
->scc_next
)
3258 for (src
= val
->sources
; src
; src
= src
->next
)
3260 && src
->cs
->maybe_hot_p ())
3262 src
->val
->prop_time_benefit
= safe_add (time
,
3263 src
->val
->prop_time_benefit
);
3264 src
->val
->prop_size_cost
= safe_add (size
,
3265 src
->val
->prop_size_cost
);
3271 /* Propagate constants, polymorphic contexts and their effects from the
3272 summaries interprocedurally. */
3275 ipcp_propagate_stage (class ipa_topo_info
*topo
)
3277 struct cgraph_node
*node
;
3280 fprintf (dump_file
, "\n Propagating constants:\n\n");
3282 max_count
= profile_count::uninitialized ();
3284 FOR_EACH_DEFINED_FUNCTION (node
)
3286 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3288 determine_versionability (node
, info
);
3289 if (node
->has_gimple_body_p ())
3291 info
->lattices
= XCNEWVEC (class ipcp_param_lattices
,
3292 ipa_get_param_count (info
));
3293 initialize_node_lattices (node
);
3295 ipa_fn_summary
*s
= ipa_fn_summaries
->get (node
);
3296 if (node
->definition
&& !node
->alias
&& s
!= NULL
)
3297 overall_size
+= s
->self_size
;
3298 max_count
= max_count
.max (node
->count
.ipa ());
3301 max_new_size
= overall_size
;
3302 if (max_new_size
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
3303 max_new_size
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
3304 max_new_size
+= max_new_size
* PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH
) / 100 + 1;
3307 fprintf (dump_file
, "\noverall_size: %li, max_new_size: %li\n",
3308 overall_size
, max_new_size
);
3310 propagate_constants_topo (topo
);
3312 ipcp_verify_propagated_values ();
3313 topo
->constants
.propagate_effects ();
3314 topo
->contexts
.propagate_effects ();
3318 fprintf (dump_file
, "\nIPA lattices after all propagation:\n");
3319 print_all_lattices (dump_file
, (dump_flags
& TDF_DETAILS
), true);
3323 /* Discover newly direct outgoing edges from NODE which is a new clone with
3324 known KNOWN_CSTS and make them direct. */
3327 ipcp_discover_new_direct_edges (struct cgraph_node
*node
,
3328 vec
<tree
> known_csts
,
3329 vec
<ipa_polymorphic_call_context
>
3331 struct ipa_agg_replacement_value
*aggvals
)
3333 struct cgraph_edge
*ie
, *next_ie
;
3336 for (ie
= node
->indirect_calls
; ie
; ie
= next_ie
)
3341 next_ie
= ie
->next_callee
;
3342 target
= ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
3343 vNULL
, aggvals
, &speculative
);
3346 bool agg_contents
= ie
->indirect_info
->agg_contents
;
3347 bool polymorphic
= ie
->indirect_info
->polymorphic
;
3348 int param_index
= ie
->indirect_info
->param_index
;
3349 struct cgraph_edge
*cs
= ipa_make_edge_direct_to_target (ie
, target
,
3353 if (cs
&& !agg_contents
&& !polymorphic
)
3355 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3356 int c
= ipa_get_controlled_uses (info
, param_index
);
3357 if (c
!= IPA_UNDESCRIBED_USE
)
3359 struct ipa_ref
*to_del
;
3362 ipa_set_controlled_uses (info
, param_index
, c
);
3363 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3364 fprintf (dump_file
, " controlled uses count of param "
3365 "%i bumped down to %i\n", param_index
, c
);
3367 && (to_del
= node
->find_reference (cs
->callee
, NULL
, 0)))
3369 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3370 fprintf (dump_file
, " and even removing its "
3371 "cloning-created reference\n");
3372 to_del
->remove_reference ();
3378 /* Turning calls to direct calls will improve overall summary. */
3380 ipa_update_overall_fn_summary (node
);
3383 class edge_clone_summary
;
3384 static call_summary
<edge_clone_summary
*> *edge_clone_summaries
= NULL
;
3386 /* Edge clone summary. */
3388 class edge_clone_summary
3391 /* Default constructor. */
3392 edge_clone_summary (): prev_clone (NULL
), next_clone (NULL
) {}
3394 /* Default destructor. */
3395 ~edge_clone_summary ()
3398 edge_clone_summaries
->get (prev_clone
)->next_clone
= next_clone
;
3400 edge_clone_summaries
->get (next_clone
)->prev_clone
= prev_clone
;
3403 cgraph_edge
*prev_clone
;
3404 cgraph_edge
*next_clone
;
3407 class edge_clone_summary_t
:
3408 public call_summary
<edge_clone_summary
*>
3411 edge_clone_summary_t (symbol_table
*symtab
):
3412 call_summary
<edge_clone_summary
*> (symtab
)
3414 m_initialize_when_cloning
= true;
3417 virtual void duplicate (cgraph_edge
*src_edge
, cgraph_edge
*dst_edge
,
3418 edge_clone_summary
*src_data
,
3419 edge_clone_summary
*dst_data
);
3422 /* Edge duplication hook. */
3425 edge_clone_summary_t::duplicate (cgraph_edge
*src_edge
, cgraph_edge
*dst_edge
,
3426 edge_clone_summary
*src_data
,
3427 edge_clone_summary
*dst_data
)
3429 if (src_data
->next_clone
)
3430 edge_clone_summaries
->get (src_data
->next_clone
)->prev_clone
= dst_edge
;
3431 dst_data
->prev_clone
= src_edge
;
3432 dst_data
->next_clone
= src_data
->next_clone
;
3433 src_data
->next_clone
= dst_edge
;
3436 /* See if NODE is a clone with a known aggregate value at a given OFFSET of a
3437 parameter with the given INDEX. */
3440 get_clone_agg_value (struct cgraph_node
*node
, HOST_WIDE_INT offset
,
3443 struct ipa_agg_replacement_value
*aggval
;
3445 aggval
= ipa_get_agg_replacements_for_node (node
);
3448 if (aggval
->offset
== offset
3449 && aggval
->index
== index
)
3450 return aggval
->value
;
3451 aggval
= aggval
->next
;
3456 /* Return true is NODE is DEST or its clone for all contexts. */
3459 same_node_or_its_all_contexts_clone_p (cgraph_node
*node
, cgraph_node
*dest
)
3464 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3465 return info
->is_all_contexts_clone
&& info
->ipcp_orig_node
== dest
;
3468 /* Return true if edge CS does bring about the value described by SRC to
3469 DEST_VAL of node DEST or its clone for all contexts. */
3472 cgraph_edge_brings_value_p (cgraph_edge
*cs
, ipcp_value_source
<tree
> *src
,
3473 cgraph_node
*dest
, ipcp_value
<tree
> *dest_val
)
3475 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3476 enum availability availability
;
3477 cgraph_node
*real_dest
= cs
->callee
->function_symbol (&availability
);
3479 if (!same_node_or_its_all_contexts_clone_p (real_dest
, dest
)
3480 || availability
<= AVAIL_INTERPOSABLE
3481 || caller_info
->node_dead
)
3487 if (caller_info
->ipcp_orig_node
)
3490 if (src
->offset
== -1)
3491 t
= caller_info
->known_csts
[src
->index
];
3493 t
= get_clone_agg_value (cs
->caller
, src
->offset
, src
->index
);
3494 return (t
!= NULL_TREE
3495 && values_equal_for_ipcp_p (src
->val
->value
, t
));
3499 /* At the moment we do not propagate over arithmetic jump functions in
3500 SCCs, so it is safe to detect self-feeding recursive calls in this
3502 if (src
->val
== dest_val
)
3505 struct ipcp_agg_lattice
*aglat
;
3506 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
3508 if (src
->offset
== -1)
3509 return (plats
->itself
.is_single_const ()
3510 && values_equal_for_ipcp_p (src
->val
->value
,
3511 plats
->itself
.values
->value
));
3514 if (plats
->aggs_bottom
|| plats
->aggs_contain_variable
)
3516 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3517 if (aglat
->offset
== src
->offset
)
3518 return (aglat
->is_single_const ()
3519 && values_equal_for_ipcp_p (src
->val
->value
,
3520 aglat
->values
->value
));
3526 /* Return true if edge CS does bring about the value described by SRC to
3527 DST_VAL of node DEST or its clone for all contexts. */
3530 cgraph_edge_brings_value_p (cgraph_edge
*cs
,
3531 ipcp_value_source
<ipa_polymorphic_call_context
> *src
,
3533 ipcp_value
<ipa_polymorphic_call_context
> *)
3535 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3536 cgraph_node
*real_dest
= cs
->callee
->function_symbol ();
3538 if (!same_node_or_its_all_contexts_clone_p (real_dest
, dest
)
3539 || caller_info
->node_dead
)
3544 if (caller_info
->ipcp_orig_node
)
3545 return (caller_info
->known_contexts
.length () > (unsigned) src
->index
)
3546 && values_equal_for_ipcp_p (src
->val
->value
,
3547 caller_info
->known_contexts
[src
->index
]);
3549 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
3551 return plats
->ctxlat
.is_single_const ()
3552 && values_equal_for_ipcp_p (src
->val
->value
,
3553 plats
->ctxlat
.values
->value
);
3556 /* Get the next clone in the linked list of clones of an edge. */
3558 static inline struct cgraph_edge
*
3559 get_next_cgraph_edge_clone (struct cgraph_edge
*cs
)
3561 edge_clone_summary
*s
= edge_clone_summaries
->get (cs
);
3562 return s
!= NULL
? s
->next_clone
: NULL
;
3565 /* Given VAL that is intended for DEST, iterate over all its sources and if any
3566 of them is viable and hot, return true. In that case, for those that still
3567 hold, add their edge frequency and their number into *FREQUENCY and
3568 *CALLER_COUNT respectively. */
3570 template <typename valtype
>
3572 get_info_about_necessary_edges (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
3574 profile_count
*count_sum
, int *caller_count
)
3576 ipcp_value_source
<valtype
> *src
;
3577 int freq
= 0, count
= 0;
3578 profile_count cnt
= profile_count::zero ();
3580 bool non_self_recursive
= false;
3582 for (src
= val
->sources
; src
; src
= src
->next
)
3584 struct cgraph_edge
*cs
= src
->cs
;
3587 if (cgraph_edge_brings_value_p (cs
, src
, dest
, val
))
3590 freq
+= cs
->frequency ();
3591 if (cs
->count
.ipa ().initialized_p ())
3592 cnt
+= cs
->count
.ipa ();
3593 hot
|= cs
->maybe_hot_p ();
3594 if (cs
->caller
!= dest
)
3595 non_self_recursive
= true;
3597 cs
= get_next_cgraph_edge_clone (cs
);
3601 /* If the only edges bringing a value are self-recursive ones, do not bother
3603 if (!non_self_recursive
)
3608 *caller_count
= count
;
3612 /* Return a vector of incoming edges that do bring value VAL to node DEST. It
3613 is assumed their number is known and equal to CALLER_COUNT. */
3615 template <typename valtype
>
3616 static vec
<cgraph_edge
*>
3617 gather_edges_for_value (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
3620 ipcp_value_source
<valtype
> *src
;
3621 vec
<cgraph_edge
*> ret
;
3623 ret
.create (caller_count
);
3624 for (src
= val
->sources
; src
; src
= src
->next
)
3626 struct cgraph_edge
*cs
= src
->cs
;
3629 if (cgraph_edge_brings_value_p (cs
, src
, dest
, val
))
3630 ret
.quick_push (cs
);
3631 cs
= get_next_cgraph_edge_clone (cs
);
3638 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
3639 Return it or NULL if for some reason it cannot be created. */
3641 static struct ipa_replace_map
*
3642 get_replacement_map (class ipa_node_params
*info
, tree value
, int parm_num
)
3644 struct ipa_replace_map
*replace_map
;
3647 replace_map
= ggc_alloc
<ipa_replace_map
> ();
3650 fprintf (dump_file
, " replacing ");
3651 ipa_dump_param (dump_file
, info
, parm_num
);
3653 fprintf (dump_file
, " with const ");
3654 print_generic_expr (dump_file
, value
);
3655 fprintf (dump_file
, "\n");
3657 replace_map
->old_tree
= NULL
;
3658 replace_map
->parm_num
= parm_num
;
3659 replace_map
->new_tree
= value
;
3660 replace_map
->replace_p
= true;
3661 replace_map
->ref_p
= false;
3666 /* Dump new profiling counts */
3669 dump_profile_updates (struct cgraph_node
*orig_node
,
3670 struct cgraph_node
*new_node
)
3672 struct cgraph_edge
*cs
;
3674 fprintf (dump_file
, " setting count of the specialized node to ");
3675 new_node
->count
.dump (dump_file
);
3676 fprintf (dump_file
, "\n");
3677 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3679 fprintf (dump_file
, " edge to %s has count ",
3680 cs
->callee
->name ());
3681 cs
->count
.dump (dump_file
);
3682 fprintf (dump_file
, "\n");
3685 fprintf (dump_file
, " setting count of the original node to ");
3686 orig_node
->count
.dump (dump_file
);
3687 fprintf (dump_file
, "\n");
3688 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3690 fprintf (dump_file
, " edge to %s is left with ",
3691 cs
->callee
->name ());
3692 cs
->count
.dump (dump_file
);
3693 fprintf (dump_file
, "\n");
3697 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
3698 their profile information to reflect this. */
3701 update_profiling_info (struct cgraph_node
*orig_node
,
3702 struct cgraph_node
*new_node
)
3704 struct cgraph_edge
*cs
;
3705 struct caller_statistics stats
;
3706 profile_count new_sum
, orig_sum
;
3707 profile_count remainder
, orig_node_count
= orig_node
->count
;
3709 if (!(orig_node_count
.ipa () > profile_count::zero ()))
3712 init_caller_stats (&stats
);
3713 orig_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
3715 orig_sum
= stats
.count_sum
;
3716 init_caller_stats (&stats
);
3717 new_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
3719 new_sum
= stats
.count_sum
;
3721 if (orig_node_count
< orig_sum
+ new_sum
)
3725 fprintf (dump_file
, " Problem: node %s has too low count ",
3726 orig_node
->dump_name ());
3727 orig_node_count
.dump (dump_file
);
3728 fprintf (dump_file
, "while the sum of incoming count is ");
3729 (orig_sum
+ new_sum
).dump (dump_file
);
3730 fprintf (dump_file
, "\n");
3733 orig_node_count
= (orig_sum
+ new_sum
).apply_scale (12, 10);
3736 fprintf (dump_file
, " proceeding by pretending it was ");
3737 orig_node_count
.dump (dump_file
);
3738 fprintf (dump_file
, "\n");
3742 remainder
= orig_node_count
.combine_with_ipa_count (orig_node_count
.ipa ()
3744 new_sum
= orig_node_count
.combine_with_ipa_count (new_sum
);
3745 orig_node
->count
= remainder
;
3747 profile_count::adjust_for_ipa_scaling (&new_sum
, &orig_node_count
);
3748 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3749 cs
->count
= cs
->count
.apply_scale (new_sum
, orig_node_count
);
3751 profile_count::adjust_for_ipa_scaling (&remainder
, &orig_node_count
);
3752 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3753 cs
->count
= cs
->count
.apply_scale (remainder
, orig_node_count
);
3756 dump_profile_updates (orig_node
, new_node
);
3759 /* Update the respective profile of specialized NEW_NODE and the original
3760 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
3761 have been redirected to the specialized version. */
3764 update_specialized_profile (struct cgraph_node
*new_node
,
3765 struct cgraph_node
*orig_node
,
3766 profile_count redirected_sum
)
3768 struct cgraph_edge
*cs
;
3769 profile_count new_node_count
, orig_node_count
= orig_node
->count
;
3773 fprintf (dump_file
, " the sum of counts of redirected edges is ");
3774 redirected_sum
.dump (dump_file
);
3775 fprintf (dump_file
, "\n");
3777 if (!(orig_node_count
> profile_count::zero ()))
3780 gcc_assert (orig_node_count
>= redirected_sum
);
3782 new_node_count
= new_node
->count
;
3783 new_node
->count
+= redirected_sum
;
3784 orig_node
->count
-= redirected_sum
;
3786 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3787 cs
->count
+= cs
->count
.apply_scale (redirected_sum
, new_node_count
);
3789 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3791 profile_count dec
= cs
->count
.apply_scale (redirected_sum
,
3797 dump_profile_updates (orig_node
, new_node
);
3800 /* Create a specialized version of NODE with known constants in KNOWN_CSTS,
3801 known contexts in KNOWN_CONTEXTS and known aggregate values in AGGVALS and
3802 redirect all edges in CALLERS to it. */
3804 static struct cgraph_node
*
3805 create_specialized_node (struct cgraph_node
*node
,
3806 vec
<tree
> known_csts
,
3807 vec
<ipa_polymorphic_call_context
> known_contexts
,
3808 struct ipa_agg_replacement_value
*aggvals
,
3809 vec
<cgraph_edge
*> callers
)
3811 class ipa_node_params
*new_info
, *info
= IPA_NODE_REF (node
);
3812 vec
<ipa_replace_map
*, va_gc
> *replace_trees
= NULL
;
3813 struct ipa_agg_replacement_value
*av
;
3814 struct cgraph_node
*new_node
;
3815 int i
, count
= ipa_get_param_count (info
);
3816 bitmap args_to_skip
;
3818 gcc_assert (!info
->ipcp_orig_node
);
3820 if (node
->local
.can_change_signature
)
3822 args_to_skip
= BITMAP_GGC_ALLOC ();
3823 for (i
= 0; i
< count
; i
++)
3825 tree t
= known_csts
[i
];
3827 if (t
|| !ipa_is_param_used (info
, i
))
3828 bitmap_set_bit (args_to_skip
, i
);
3833 args_to_skip
= NULL
;
3834 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3835 fprintf (dump_file
, " cannot change function signature\n");
3838 for (i
= 0; i
< count
; i
++)
3840 tree t
= known_csts
[i
];
3843 struct ipa_replace_map
*replace_map
;
3845 gcc_checking_assert (TREE_CODE (t
) != TREE_BINFO
);
3846 replace_map
= get_replacement_map (info
, t
, i
);
3848 vec_safe_push (replace_trees
, replace_map
);
3851 auto_vec
<cgraph_edge
*, 2> self_recursive_calls
;
3852 for (i
= callers
.length () - 1; i
>= 0; i
--)
3854 cgraph_edge
*cs
= callers
[i
];
3855 if (cs
->caller
== node
)
3857 self_recursive_calls
.safe_push (cs
);
3858 callers
.unordered_remove (i
);
3862 unsigned &suffix_counter
= clone_num_suffixes
->get_or_insert (
3863 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (
3865 new_node
= node
->create_virtual_clone (callers
, replace_trees
,
3866 args_to_skip
, "constprop",
3870 bool have_self_recursive_calls
= !self_recursive_calls
.is_empty ();
3871 for (unsigned j
= 0; j
< self_recursive_calls
.length (); j
++)
3873 cgraph_edge
*cs
= get_next_cgraph_edge_clone (self_recursive_calls
[j
]);
3874 /* Cloned edges can disappear during cloning as speculation can be
3875 resolved, check that we have one and that it comes from the last
3877 if (cs
&& cs
->caller
== new_node
)
3878 cs
->redirect_callee_duplicating_thunks (new_node
);
3879 /* Any future code that would make more than one clone of an outgoing
3880 edge would confuse this mechanism, so let's check that does not
3882 gcc_checking_assert (!cs
3883 || !get_next_cgraph_edge_clone (cs
)
3884 || get_next_cgraph_edge_clone (cs
)->caller
!= new_node
);
3886 if (have_self_recursive_calls
)
3887 new_node
->expand_all_artificial_thunks ();
3889 ipa_set_node_agg_value_chain (new_node
, aggvals
);
3890 for (av
= aggvals
; av
; av
= av
->next
)
3891 new_node
->maybe_create_reference (av
->value
, NULL
);
3893 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3895 fprintf (dump_file
, " the new node is %s.\n", new_node
->dump_name ());
3896 if (known_contexts
.exists ())
3898 for (i
= 0; i
< count
; i
++)
3899 if (!known_contexts
[i
].useless_p ())
3901 fprintf (dump_file
, " known ctx %i is ", i
);
3902 known_contexts
[i
].dump (dump_file
);
3906 ipa_dump_agg_replacement_values (dump_file
, aggvals
);
3908 ipa_check_create_node_params ();
3909 update_profiling_info (node
, new_node
);
3910 new_info
= IPA_NODE_REF (new_node
);
3911 new_info
->ipcp_orig_node
= node
;
3912 new_info
->known_csts
= known_csts
;
3913 new_info
->known_contexts
= known_contexts
;
3915 ipcp_discover_new_direct_edges (new_node
, known_csts
, known_contexts
, aggvals
);
3921 /* Return true, if JFUNC, which describes a i-th parameter of call CS, is a
3922 simple no-operation pass-through function to itself. */
3925 self_recursive_pass_through_p (cgraph_edge
*cs
, ipa_jump_func
*jfunc
, int i
)
3927 enum availability availability
;
3928 if (cs
->caller
== cs
->callee
->function_symbol (&availability
)
3929 && availability
> AVAIL_INTERPOSABLE
3930 && jfunc
->type
== IPA_JF_PASS_THROUGH
3931 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
3932 && ipa_get_jf_pass_through_formal_id (jfunc
) == i
)
3937 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
3938 KNOWN_CSTS with constants that are also known for all of the CALLERS. */
3941 find_more_scalar_values_for_callers_subset (struct cgraph_node
*node
,
3942 vec
<tree
> known_csts
,
3943 vec
<cgraph_edge
*> callers
)
3945 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3946 int i
, count
= ipa_get_param_count (info
);
3948 for (i
= 0; i
< count
; i
++)
3950 struct cgraph_edge
*cs
;
3951 tree newval
= NULL_TREE
;
3954 tree type
= ipa_get_type (info
, i
);
3956 if (ipa_get_scalar_lat (info
, i
)->bottom
|| known_csts
[i
])
3959 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3961 struct ipa_jump_func
*jump_func
;
3964 if (IPA_NODE_REF (cs
->caller
)->node_dead
)
3967 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
))
3969 && call_passes_through_thunk_p (cs
)))
3974 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
3975 if (self_recursive_pass_through_p (cs
, jump_func
, i
))
3978 t
= ipa_value_from_jfunc (IPA_NODE_REF (cs
->caller
), jump_func
, type
);
3981 && !values_equal_for_ipcp_p (t
, newval
))
3982 || (!first
&& !newval
))
3994 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3996 fprintf (dump_file
, " adding an extra known scalar value ");
3997 print_ipcp_constant_value (dump_file
, newval
);
3998 fprintf (dump_file
, " for ");
3999 ipa_dump_param (dump_file
, info
, i
);
4000 fprintf (dump_file
, "\n");
4003 known_csts
[i
] = newval
;
4008 /* Given a NODE and a subset of its CALLERS, try to populate plank slots in
4009 KNOWN_CONTEXTS with polymorphic contexts that are also known for all of the
4013 find_more_contexts_for_caller_subset (cgraph_node
*node
,
4014 vec
<ipa_polymorphic_call_context
>
4016 vec
<cgraph_edge
*> callers
)
4018 ipa_node_params
*info
= IPA_NODE_REF (node
);
4019 int i
, count
= ipa_get_param_count (info
);
4021 for (i
= 0; i
< count
; i
++)
4025 if (ipa_get_poly_ctx_lat (info
, i
)->bottom
4026 || (known_contexts
->exists ()
4027 && !(*known_contexts
)[i
].useless_p ()))
4030 ipa_polymorphic_call_context newval
;
4034 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4036 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
)))
4038 ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
),
4040 ipa_polymorphic_call_context ctx
;
4041 ctx
= ipa_context_from_jfunc (IPA_NODE_REF (cs
->caller
), cs
, i
,
4049 newval
.meet_with (ctx
);
4050 if (newval
.useless_p ())
4054 if (!newval
.useless_p ())
4056 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4058 fprintf (dump_file
, " adding an extra known polymorphic "
4060 print_ipcp_constant_value (dump_file
, newval
);
4061 fprintf (dump_file
, " for ");
4062 ipa_dump_param (dump_file
, info
, i
);
4063 fprintf (dump_file
, "\n");
4066 if (!known_contexts
->exists ())
4067 known_contexts
->safe_grow_cleared (ipa_get_param_count (info
));
4068 (*known_contexts
)[i
] = newval
;
4074 /* Go through PLATS and create a vector of values consisting of values and
4075 offsets (minus OFFSET) of lattices that contain only a single value. */
4077 static vec
<ipa_agg_jf_item
>
4078 copy_plats_to_inter (class ipcp_param_lattices
*plats
, HOST_WIDE_INT offset
)
4080 vec
<ipa_agg_jf_item
> res
= vNULL
;
4082 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
4085 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
4086 if (aglat
->is_single_const ())
4088 struct ipa_agg_jf_item ti
;
4089 ti
.offset
= aglat
->offset
- offset
;
4090 ti
.value
= aglat
->values
->value
;
4096 /* Intersect all values in INTER with single value lattices in PLATS (while
4097 subtracting OFFSET). */
4100 intersect_with_plats (class ipcp_param_lattices
*plats
,
4101 vec
<ipa_agg_jf_item
> *inter
,
4102 HOST_WIDE_INT offset
)
4104 struct ipcp_agg_lattice
*aglat
;
4105 struct ipa_agg_jf_item
*item
;
4108 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
4114 aglat
= plats
->aggs
;
4115 FOR_EACH_VEC_ELT (*inter
, k
, item
)
4122 if (aglat
->offset
- offset
> item
->offset
)
4124 if (aglat
->offset
- offset
== item
->offset
)
4126 gcc_checking_assert (item
->value
);
4127 if (aglat
->is_single_const ()
4128 && values_equal_for_ipcp_p (item
->value
,
4129 aglat
->values
->value
))
4133 aglat
= aglat
->next
;
4136 item
->value
= NULL_TREE
;
4140 /* Copy aggregate replacement values of NODE (which is an IPA-CP clone) to the
4141 vector result while subtracting OFFSET from the individual value offsets. */
4143 static vec
<ipa_agg_jf_item
>
4144 agg_replacements_to_vector (struct cgraph_node
*node
, int index
,
4145 HOST_WIDE_INT offset
)
4147 struct ipa_agg_replacement_value
*av
;
4148 vec
<ipa_agg_jf_item
> res
= vNULL
;
4150 for (av
= ipa_get_agg_replacements_for_node (node
); av
; av
= av
->next
)
4151 if (av
->index
== index
4152 && (av
->offset
- offset
) >= 0)
4154 struct ipa_agg_jf_item item
;
4155 gcc_checking_assert (av
->value
);
4156 item
.offset
= av
->offset
- offset
;
4157 item
.value
= av
->value
;
4158 res
.safe_push (item
);
4164 /* Intersect all values in INTER with those that we have already scheduled to
4165 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
4166 (while subtracting OFFSET). */
4169 intersect_with_agg_replacements (struct cgraph_node
*node
, int index
,
4170 vec
<ipa_agg_jf_item
> *inter
,
4171 HOST_WIDE_INT offset
)
4173 struct ipa_agg_replacement_value
*srcvals
;
4174 struct ipa_agg_jf_item
*item
;
4177 srcvals
= ipa_get_agg_replacements_for_node (node
);
4184 FOR_EACH_VEC_ELT (*inter
, i
, item
)
4186 struct ipa_agg_replacement_value
*av
;
4190 for (av
= srcvals
; av
; av
= av
->next
)
4192 gcc_checking_assert (av
->value
);
4193 if (av
->index
== index
4194 && av
->offset
- offset
== item
->offset
)
4196 if (values_equal_for_ipcp_p (item
->value
, av
->value
))
4202 item
->value
= NULL_TREE
;
4206 /* Intersect values in INTER with aggregate values that come along edge CS to
4207 parameter number INDEX and return it. If INTER does not actually exist yet,
4208 copy all incoming values to it. If we determine we ended up with no values
4209 whatsoever, return a released vector. */
4211 static vec
<ipa_agg_jf_item
>
4212 intersect_aggregates_with_edge (struct cgraph_edge
*cs
, int index
,
4213 vec
<ipa_agg_jf_item
> inter
)
4215 struct ipa_jump_func
*jfunc
;
4216 jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), index
);
4217 if (jfunc
->type
== IPA_JF_PASS_THROUGH
4218 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
4220 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4221 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
4223 if (caller_info
->ipcp_orig_node
)
4225 struct cgraph_node
*orig_node
= caller_info
->ipcp_orig_node
;
4226 class ipcp_param_lattices
*orig_plats
;
4227 orig_plats
= ipa_get_parm_lattices (IPA_NODE_REF (orig_node
),
4229 if (agg_pass_through_permissible_p (orig_plats
, jfunc
))
4231 if (!inter
.exists ())
4232 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, 0);
4234 intersect_with_agg_replacements (cs
->caller
, src_idx
,
4245 class ipcp_param_lattices
*src_plats
;
4246 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
4247 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
4249 /* Currently we do not produce clobber aggregate jump
4250 functions, adjust when we do. */
4251 gcc_checking_assert (!jfunc
->agg
.items
);
4252 if (!inter
.exists ())
4253 inter
= copy_plats_to_inter (src_plats
, 0);
4255 intersect_with_plats (src_plats
, &inter
, 0);
4264 else if (jfunc
->type
== IPA_JF_ANCESTOR
4265 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
4267 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4268 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
4269 class ipcp_param_lattices
*src_plats
;
4270 HOST_WIDE_INT delta
= ipa_get_jf_ancestor_offset (jfunc
);
4272 if (caller_info
->ipcp_orig_node
)
4274 if (!inter
.exists ())
4275 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, delta
);
4277 intersect_with_agg_replacements (cs
->caller
, src_idx
, &inter
,
4282 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
4283 /* Currently we do not produce clobber aggregate jump
4284 functions, adjust when we do. */
4285 gcc_checking_assert (!src_plats
->aggs
|| !jfunc
->agg
.items
);
4286 if (!inter
.exists ())
4287 inter
= copy_plats_to_inter (src_plats
, delta
);
4289 intersect_with_plats (src_plats
, &inter
, delta
);
4292 else if (jfunc
->agg
.items
)
4294 struct ipa_agg_jf_item
*item
;
4297 if (!inter
.exists ())
4298 for (unsigned i
= 0; i
< jfunc
->agg
.items
->length (); i
++)
4299 inter
.safe_push ((*jfunc
->agg
.items
)[i
]);
4301 FOR_EACH_VEC_ELT (inter
, k
, item
)
4309 while ((unsigned) l
< jfunc
->agg
.items
->length ())
4311 struct ipa_agg_jf_item
*ti
;
4312 ti
= &(*jfunc
->agg
.items
)[l
];
4313 if (ti
->offset
> item
->offset
)
4315 if (ti
->offset
== item
->offset
)
4317 gcc_checking_assert (ti
->value
);
4318 if (values_equal_for_ipcp_p (item
->value
,
4332 return vec
<ipa_agg_jf_item
>();
4337 /* Look at edges in CALLERS and collect all known aggregate values that arrive
4338 from all of them. */
4340 static struct ipa_agg_replacement_value
*
4341 find_aggregate_values_for_callers_subset (struct cgraph_node
*node
,
4342 vec
<cgraph_edge
*> callers
)
4344 class ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
4345 struct ipa_agg_replacement_value
*res
;
4346 struct ipa_agg_replacement_value
**tail
= &res
;
4347 struct cgraph_edge
*cs
;
4348 int i
, j
, count
= ipa_get_param_count (dest_info
);
4350 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4352 int c
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
4357 for (i
= 0; i
< count
; i
++)
4359 struct cgraph_edge
*cs
;
4360 vec
<ipa_agg_jf_item
> inter
= vNULL
;
4361 struct ipa_agg_jf_item
*item
;
4362 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (dest_info
, i
);
4365 /* Among other things, the following check should deal with all by_ref
4367 if (plats
->aggs_bottom
)
4370 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4372 struct ipa_jump_func
*jfunc
4373 = ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
4374 if (self_recursive_pass_through_p (cs
, jfunc
, i
)
4375 && (!plats
->aggs_by_ref
4376 || ipa_get_jf_pass_through_agg_preserved (jfunc
)))
4378 inter
= intersect_aggregates_with_edge (cs
, i
, inter
);
4380 if (!inter
.exists ())
4384 FOR_EACH_VEC_ELT (inter
, j
, item
)
4386 struct ipa_agg_replacement_value
*v
;
4391 v
= ggc_alloc
<ipa_agg_replacement_value
> ();
4393 v
->offset
= item
->offset
;
4394 v
->value
= item
->value
;
4395 v
->by_ref
= plats
->aggs_by_ref
;
4401 if (inter
.exists ())
4408 /* Determine whether CS also brings all scalar values that the NODE is
4412 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge
*cs
,
4413 struct cgraph_node
*node
)
4415 class ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
4416 int count
= ipa_get_param_count (dest_info
);
4417 class ipa_node_params
*caller_info
;
4418 class ipa_edge_args
*args
;
4421 caller_info
= IPA_NODE_REF (cs
->caller
);
4422 args
= IPA_EDGE_REF (cs
);
4423 for (i
= 0; i
< count
; i
++)
4425 struct ipa_jump_func
*jump_func
;
4428 val
= dest_info
->known_csts
[i
];
4432 if (i
>= ipa_get_cs_argument_count (args
))
4434 jump_func
= ipa_get_ith_jump_func (args
, i
);
4435 t
= ipa_value_from_jfunc (caller_info
, jump_func
,
4436 ipa_get_type (dest_info
, i
));
4437 if (!t
|| !values_equal_for_ipcp_p (val
, t
))
4443 /* Determine whether CS also brings all aggregate values that NODE is
4446 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge
*cs
,
4447 struct cgraph_node
*node
)
4449 class ipa_node_params
*orig_node_info
;
4450 struct ipa_agg_replacement_value
*aggval
;
4453 aggval
= ipa_get_agg_replacements_for_node (node
);
4457 count
= ipa_get_param_count (IPA_NODE_REF (node
));
4458 ec
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
4460 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4461 if (aggval
->index
>= ec
)
4464 orig_node_info
= IPA_NODE_REF (IPA_NODE_REF (node
)->ipcp_orig_node
);
4466 for (i
= 0; i
< count
; i
++)
4468 static vec
<ipa_agg_jf_item
> values
= vec
<ipa_agg_jf_item
>();
4469 class ipcp_param_lattices
*plats
;
4470 bool interesting
= false;
4471 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4472 if (aggval
->index
== i
)
4480 plats
= ipa_get_parm_lattices (orig_node_info
, aggval
->index
);
4481 if (plats
->aggs_bottom
)
4484 values
= intersect_aggregates_with_edge (cs
, i
, values
);
4485 if (!values
.exists ())
4488 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4489 if (aggval
->index
== i
)
4491 struct ipa_agg_jf_item
*item
;
4494 FOR_EACH_VEC_ELT (values
, j
, item
)
4496 && item
->offset
== av
->offset
4497 && values_equal_for_ipcp_p (item
->value
, av
->value
))
4512 /* Given an original NODE and a VAL for which we have already created a
4513 specialized clone, look whether there are incoming edges that still lead
4514 into the old node but now also bring the requested value and also conform to
4515 all other criteria such that they can be redirected the special node.
4516 This function can therefore redirect the final edge in a SCC. */
4518 template <typename valtype
>
4520 perhaps_add_new_callers (cgraph_node
*node
, ipcp_value
<valtype
> *val
)
4522 ipcp_value_source
<valtype
> *src
;
4523 profile_count redirected_sum
= profile_count::zero ();
4525 for (src
= val
->sources
; src
; src
= src
->next
)
4527 struct cgraph_edge
*cs
= src
->cs
;
4530 if (cgraph_edge_brings_value_p (cs
, src
, node
, val
)
4531 && cgraph_edge_brings_all_scalars_for_node (cs
, val
->spec_node
)
4532 && cgraph_edge_brings_all_agg_vals_for_node (cs
, val
->spec_node
))
4535 fprintf (dump_file
, " - adding an extra caller %s of %s\n",
4536 cs
->caller
->dump_name (),
4537 val
->spec_node
->dump_name ());
4539 cs
->redirect_callee_duplicating_thunks (val
->spec_node
);
4540 val
->spec_node
->expand_all_artificial_thunks ();
4541 if (cs
->count
.ipa ().initialized_p ())
4542 redirected_sum
= redirected_sum
+ cs
->count
.ipa ();
4544 cs
= get_next_cgraph_edge_clone (cs
);
4548 if (redirected_sum
.nonzero_p ())
4549 update_specialized_profile (val
->spec_node
, node
, redirected_sum
);
4552 /* Return true if KNOWN_CONTEXTS contain at least one useful context. */
4555 known_contexts_useful_p (vec
<ipa_polymorphic_call_context
> known_contexts
)
4557 ipa_polymorphic_call_context
*ctx
;
4560 FOR_EACH_VEC_ELT (known_contexts
, i
, ctx
)
4561 if (!ctx
->useless_p ())
4566 /* Return a copy of KNOWN_CSTS if it is not empty, otherwise return vNULL. */
4568 static vec
<ipa_polymorphic_call_context
>
4569 copy_useful_known_contexts (vec
<ipa_polymorphic_call_context
> known_contexts
)
4571 if (known_contexts_useful_p (known_contexts
))
4572 return known_contexts
.copy ();
4577 /* Copy KNOWN_CSTS and modify the copy according to VAL and INDEX. If
4578 non-empty, replace KNOWN_CONTEXTS with its copy too. */
4581 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
4582 vec
<ipa_polymorphic_call_context
> *known_contexts
,
4583 ipcp_value
<tree
> *val
,
4586 *known_csts
= known_csts
->copy ();
4587 *known_contexts
= copy_useful_known_contexts (*known_contexts
);
4588 (*known_csts
)[index
] = val
->value
;
4591 /* Replace KNOWN_CSTS with its copy. Also copy KNOWN_CONTEXTS and modify the
4592 copy according to VAL and INDEX. */
4595 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
4596 vec
<ipa_polymorphic_call_context
> *known_contexts
,
4597 ipcp_value
<ipa_polymorphic_call_context
> *val
,
4600 *known_csts
= known_csts
->copy ();
4601 *known_contexts
= known_contexts
->copy ();
4602 (*known_contexts
)[index
] = val
->value
;
4605 /* Return true if OFFSET indicates this was not an aggregate value or there is
4606 a replacement equivalent to VALUE, INDEX and OFFSET among those in the
4610 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*aggvals
,
4611 int index
, HOST_WIDE_INT offset
, tree value
)
4618 if (aggvals
->index
== index
4619 && aggvals
->offset
== offset
4620 && values_equal_for_ipcp_p (aggvals
->value
, value
))
4622 aggvals
= aggvals
->next
;
4627 /* Return true if offset is minus one because source of a polymorphic context
4628 cannot be an aggregate value. */
4631 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*,
4632 int , HOST_WIDE_INT offset
,
4633 ipa_polymorphic_call_context
)
4635 return offset
== -1;
4638 /* Decide whether to create a special version of NODE for value VAL of parameter
4639 at the given INDEX. If OFFSET is -1, the value is for the parameter itself,
4640 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS,
4641 KNOWN_CONTEXTS and KNOWN_AGGS describe the other already known values. */
4643 template <typename valtype
>
4645 decide_about_value (struct cgraph_node
*node
, int index
, HOST_WIDE_INT offset
,
4646 ipcp_value
<valtype
> *val
, vec
<tree
> known_csts
,
4647 vec
<ipa_polymorphic_call_context
> known_contexts
)
4649 struct ipa_agg_replacement_value
*aggvals
;
4650 int freq_sum
, caller_count
;
4651 profile_count count_sum
;
4652 vec
<cgraph_edge
*> callers
;
4656 perhaps_add_new_callers (node
, val
);
4659 else if (val
->local_size_cost
+ overall_size
> max_new_size
)
4661 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4662 fprintf (dump_file
, " Ignoring candidate value because "
4663 "max_new_size would be reached with %li.\n",
4664 val
->local_size_cost
+ overall_size
);
4667 else if (!get_info_about_necessary_edges (val
, node
, &freq_sum
, &count_sum
,
4671 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4673 fprintf (dump_file
, " - considering value ");
4674 print_ipcp_constant_value (dump_file
, val
->value
);
4675 fprintf (dump_file
, " for ");
4676 ipa_dump_param (dump_file
, IPA_NODE_REF (node
), index
);
4678 fprintf (dump_file
, ", offset: " HOST_WIDE_INT_PRINT_DEC
, offset
);
4679 fprintf (dump_file
, " (caller_count: %i)\n", caller_count
);
4682 if (!good_cloning_opportunity_p (node
, val
->local_time_benefit
,
4683 freq_sum
, count_sum
,
4684 val
->local_size_cost
)
4685 && !good_cloning_opportunity_p (node
,
4686 val
->local_time_benefit
4687 + val
->prop_time_benefit
,
4688 freq_sum
, count_sum
,
4689 val
->local_size_cost
4690 + val
->prop_size_cost
))
4694 fprintf (dump_file
, " Creating a specialized node of %s.\n",
4695 node
->dump_name ());
4697 callers
= gather_edges_for_value (val
, node
, caller_count
);
4699 modify_known_vectors_with_val (&known_csts
, &known_contexts
, val
, index
);
4702 known_csts
= known_csts
.copy ();
4703 known_contexts
= copy_useful_known_contexts (known_contexts
);
4705 find_more_scalar_values_for_callers_subset (node
, known_csts
, callers
);
4706 find_more_contexts_for_caller_subset (node
, &known_contexts
, callers
);
4707 aggvals
= find_aggregate_values_for_callers_subset (node
, callers
);
4708 gcc_checking_assert (ipcp_val_agg_replacement_ok_p (aggvals
, index
,
4709 offset
, val
->value
));
4710 val
->spec_node
= create_specialized_node (node
, known_csts
, known_contexts
,
4712 overall_size
+= val
->local_size_cost
;
4714 /* TODO: If for some lattice there is only one other known value
4715 left, make a special node for it too. */
4720 /* Decide whether and what specialized clones of NODE should be created. */
4723 decide_whether_version_node (struct cgraph_node
*node
)
4725 class ipa_node_params
*info
= IPA_NODE_REF (node
);
4726 int i
, count
= ipa_get_param_count (info
);
4727 vec
<tree
> known_csts
;
4728 vec
<ipa_polymorphic_call_context
> known_contexts
;
4729 vec
<ipa_agg_jump_function
> known_aggs
= vNULL
;
4735 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4736 fprintf (dump_file
, "\nEvaluating opportunities for %s.\n",
4737 node
->dump_name ());
4739 gather_context_independent_values (info
, &known_csts
, &known_contexts
,
4740 info
->do_clone_for_all_contexts
? &known_aggs
4743 for (i
= 0; i
< count
;i
++)
4745 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4746 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
4747 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
4752 ipcp_value
<tree
> *val
;
4753 for (val
= lat
->values
; val
; val
= val
->next
)
4754 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
4758 if (!plats
->aggs_bottom
)
4760 struct ipcp_agg_lattice
*aglat
;
4761 ipcp_value
<tree
> *val
;
4762 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
4763 if (!aglat
->bottom
&& aglat
->values
4764 /* If the following is false, the one value is in
4766 && (plats
->aggs_contain_variable
4767 || !aglat
->is_single_const ()))
4768 for (val
= aglat
->values
; val
; val
= val
->next
)
4769 ret
|= decide_about_value (node
, i
, aglat
->offset
, val
,
4770 known_csts
, known_contexts
);
4774 && known_contexts
[i
].useless_p ())
4776 ipcp_value
<ipa_polymorphic_call_context
> *val
;
4777 for (val
= ctxlat
->values
; val
; val
= val
->next
)
4778 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
4782 info
= IPA_NODE_REF (node
);
4785 if (info
->do_clone_for_all_contexts
)
4787 struct cgraph_node
*clone
;
4788 vec
<cgraph_edge
*> callers
;
4791 fprintf (dump_file
, " - Creating a specialized node of %s "
4792 "for all known contexts.\n", node
->dump_name ());
4794 callers
= node
->collect_callers ();
4795 find_more_scalar_values_for_callers_subset (node
, known_csts
, callers
);
4796 find_more_contexts_for_caller_subset (node
, &known_contexts
, callers
);
4797 ipa_agg_replacement_value
*aggvals
4798 = find_aggregate_values_for_callers_subset (node
, callers
);
4800 if (!known_contexts_useful_p (known_contexts
))
4802 known_contexts
.release ();
4803 known_contexts
= vNULL
;
4805 clone
= create_specialized_node (node
, known_csts
, known_contexts
,
4807 info
= IPA_NODE_REF (node
);
4808 info
->do_clone_for_all_contexts
= false;
4809 IPA_NODE_REF (clone
)->is_all_contexts_clone
= true;
4810 for (i
= 0; i
< count
; i
++)
4811 vec_free (known_aggs
[i
].items
);
4812 known_aggs
.release ();
4817 known_csts
.release ();
4818 known_contexts
.release ();
4824 /* Transitively mark all callees of NODE within the same SCC as not dead. */
4827 spread_undeadness (struct cgraph_node
*node
)
4829 struct cgraph_edge
*cs
;
4831 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
4832 if (ipa_edge_within_scc (cs
))
4834 struct cgraph_node
*callee
;
4835 class ipa_node_params
*info
;
4837 callee
= cs
->callee
->function_symbol (NULL
);
4838 info
= IPA_NODE_REF (callee
);
4840 if (info
->node_dead
)
4842 info
->node_dead
= 0;
4843 spread_undeadness (callee
);
4848 /* Return true if NODE has a caller from outside of its SCC that is not
4849 dead. Worker callback for cgraph_for_node_and_aliases. */
4852 has_undead_caller_from_outside_scc_p (struct cgraph_node
*node
,
4853 void *data ATTRIBUTE_UNUSED
)
4855 struct cgraph_edge
*cs
;
4857 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
4858 if (cs
->caller
->thunk
.thunk_p
4859 && cs
->caller
->call_for_symbol_thunks_and_aliases
4860 (has_undead_caller_from_outside_scc_p
, NULL
, true))
4862 else if (!ipa_edge_within_scc (cs
)
4863 && !IPA_NODE_REF (cs
->caller
)->node_dead
)
4869 /* Identify nodes within the same SCC as NODE which are no longer needed
4870 because of new clones and will be removed as unreachable. */
4873 identify_dead_nodes (struct cgraph_node
*node
)
4875 struct cgraph_node
*v
;
4876 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4878 && !v
->call_for_symbol_thunks_and_aliases
4879 (has_undead_caller_from_outside_scc_p
, NULL
, true))
4880 IPA_NODE_REF (v
)->node_dead
= 1;
4882 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4883 if (!IPA_NODE_REF (v
)->node_dead
)
4884 spread_undeadness (v
);
4886 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4888 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4889 if (IPA_NODE_REF (v
)->node_dead
)
4890 fprintf (dump_file
, " Marking node as dead: %s.\n", v
->dump_name ());
4894 /* The decision stage. Iterate over the topological order of call graph nodes
4895 TOPO and make specialized clones if deemed beneficial. */
4898 ipcp_decision_stage (class ipa_topo_info
*topo
)
4903 fprintf (dump_file
, "\nIPA decision stage:\n\n");
4905 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
4907 struct cgraph_node
*node
= topo
->order
[i
];
4908 bool change
= false, iterate
= true;
4912 struct cgraph_node
*v
;
4914 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4915 if (v
->has_gimple_body_p ()
4916 && ipcp_versionable_function_p (v
))
4917 iterate
|= decide_whether_version_node (v
);
4922 identify_dead_nodes (node
);
4926 /* Look up all the bits information that we have discovered and copy it over
4927 to the transformation summary. */
4930 ipcp_store_bits_results (void)
4934 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
4936 ipa_node_params
*info
= IPA_NODE_REF (node
);
4937 bool dumped_sth
= false;
4938 bool found_useful_result
= false;
4940 if (!opt_for_fn (node
->decl
, flag_ipa_bit_cp
))
4943 fprintf (dump_file
, "Not considering %s for ipa bitwise propagation "
4944 "; -fipa-bit-cp: disabled.\n",
4949 if (info
->ipcp_orig_node
)
4950 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
4952 unsigned count
= ipa_get_param_count (info
);
4953 for (unsigned i
= 0; i
< count
; i
++)
4955 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4956 if (plats
->bits_lattice
.constant_p ())
4958 found_useful_result
= true;
4963 if (!found_useful_result
)
4966 ipcp_transformation_initialize ();
4967 ipcp_transformation
*ts
= ipcp_transformation_sum
->get_create (node
);
4968 vec_safe_reserve_exact (ts
->bits
, count
);
4970 for (unsigned i
= 0; i
< count
; i
++)
4972 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4975 if (plats
->bits_lattice
.constant_p ())
4977 = ipa_get_ipa_bits_for_value (plats
->bits_lattice
.get_value (),
4978 plats
->bits_lattice
.get_mask ());
4982 ts
->bits
->quick_push (jfbits
);
4983 if (!dump_file
|| !jfbits
)
4987 fprintf (dump_file
, "Propagated bits info for function %s:\n",
4988 node
->dump_name ());
4991 fprintf (dump_file
, " param %i: value = ", i
);
4992 print_hex (jfbits
->value
, dump_file
);
4993 fprintf (dump_file
, ", mask = ");
4994 print_hex (jfbits
->mask
, dump_file
);
4995 fprintf (dump_file
, "\n");
5000 /* Look up all VR information that we have discovered and copy it over
5001 to the transformation summary. */
5004 ipcp_store_vr_results (void)
5008 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5010 ipa_node_params
*info
= IPA_NODE_REF (node
);
5011 bool found_useful_result
= false;
5013 if (!opt_for_fn (node
->decl
, flag_ipa_vrp
))
5016 fprintf (dump_file
, "Not considering %s for VR discovery "
5017 "and propagate; -fipa-ipa-vrp: disabled.\n",
5022 if (info
->ipcp_orig_node
)
5023 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
5025 unsigned count
= ipa_get_param_count (info
);
5026 for (unsigned i
= 0; i
< count
; i
++)
5028 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5029 if (!plats
->m_value_range
.bottom_p ()
5030 && !plats
->m_value_range
.top_p ())
5032 found_useful_result
= true;
5036 if (!found_useful_result
)
5039 ipcp_transformation_initialize ();
5040 ipcp_transformation
*ts
= ipcp_transformation_sum
->get_create (node
);
5041 vec_safe_reserve_exact (ts
->m_vr
, count
);
5043 for (unsigned i
= 0; i
< count
; i
++)
5045 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5048 if (!plats
->m_value_range
.bottom_p ()
5049 && !plats
->m_value_range
.top_p ())
5052 vr
.type
= plats
->m_value_range
.m_vr
.kind ();
5053 vr
.min
= wi::to_wide (plats
->m_value_range
.m_vr
.min ());
5054 vr
.max
= wi::to_wide (plats
->m_value_range
.m_vr
.max ());
5059 vr
.type
= VR_VARYING
;
5060 vr
.min
= vr
.max
= wi::zero (INT_TYPE_SIZE
);
5062 ts
->m_vr
->quick_push (vr
);
5067 /* The IPCP driver. */
5072 class ipa_topo_info topo
;
5074 if (edge_clone_summaries
== NULL
)
5075 edge_clone_summaries
= new edge_clone_summary_t (symtab
);
5077 ipa_check_create_node_params ();
5078 ipa_check_create_edge_args ();
5079 clone_num_suffixes
= new hash_map
<const char *, unsigned>;
5083 fprintf (dump_file
, "\nIPA structures before propagation:\n");
5084 if (dump_flags
& TDF_DETAILS
)
5085 ipa_print_all_params (dump_file
);
5086 ipa_print_all_jump_functions (dump_file
);
5089 /* Topological sort. */
5090 build_toporder_info (&topo
);
5091 /* Do the interprocedural propagation. */
5092 ipcp_propagate_stage (&topo
);
5093 /* Decide what constant propagation and cloning should be performed. */
5094 ipcp_decision_stage (&topo
);
5095 /* Store results of bits propagation. */
5096 ipcp_store_bits_results ();
5097 /* Store results of value range propagation. */
5098 ipcp_store_vr_results ();
5100 /* Free all IPCP structures. */
5101 delete clone_num_suffixes
;
5102 free_toporder_info (&topo
);
5103 delete edge_clone_summaries
;
5104 edge_clone_summaries
= NULL
;
5105 ipa_free_all_structures_after_ipa_cp ();
5107 fprintf (dump_file
, "\nIPA constant propagation end\n");
5111 /* Initialization and computation of IPCP data structures. This is the initial
5112 intraprocedural analysis of functions, which gathers information to be
5113 propagated later on. */
5116 ipcp_generate_summary (void)
5118 struct cgraph_node
*node
;
5121 fprintf (dump_file
, "\nIPA constant propagation start:\n");
5122 ipa_register_cgraph_hooks ();
5124 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5125 ipa_analyze_node (node
);
5128 /* Write ipcp summary for nodes in SET. */
5131 ipcp_write_summary (void)
5133 ipa_prop_write_jump_functions ();
5136 /* Read ipcp summary. */
5139 ipcp_read_summary (void)
5141 ipa_prop_read_jump_functions ();
5146 const pass_data pass_data_ipa_cp
=
5148 IPA_PASS
, /* type */
5150 OPTGROUP_NONE
, /* optinfo_flags */
5151 TV_IPA_CONSTANT_PROP
, /* tv_id */
5152 0, /* properties_required */
5153 0, /* properties_provided */
5154 0, /* properties_destroyed */
5155 0, /* todo_flags_start */
5156 ( TODO_dump_symtab
| TODO_remove_functions
), /* todo_flags_finish */
5159 class pass_ipa_cp
: public ipa_opt_pass_d
5162 pass_ipa_cp (gcc::context
*ctxt
)
5163 : ipa_opt_pass_d (pass_data_ipa_cp
, ctxt
,
5164 ipcp_generate_summary
, /* generate_summary */
5165 ipcp_write_summary
, /* write_summary */
5166 ipcp_read_summary
, /* read_summary */
5167 ipcp_write_transformation_summaries
, /*
5168 write_optimization_summary */
5169 ipcp_read_transformation_summaries
, /*
5170 read_optimization_summary */
5171 NULL
, /* stmt_fixup */
5172 0, /* function_transform_todo_flags_start */
5173 ipcp_transform_function
, /* function_transform */
5174 NULL
) /* variable_transform */
5177 /* opt_pass methods: */
5178 virtual bool gate (function
*)
5180 /* FIXME: We should remove the optimize check after we ensure we never run
5181 IPA passes when not optimizing. */
5182 return (flag_ipa_cp
&& optimize
) || in_lto_p
;
5185 virtual unsigned int execute (function
*) { return ipcp_driver (); }
5187 }; // class pass_ipa_cp
5192 make_pass_ipa_cp (gcc::context
*ctxt
)
5194 return new pass_ipa_cp (ctxt
);
5197 /* Reset all state within ipa-cp.c so that we can rerun the compiler
5198 within the same process. For use by toplev::finalize. */
5201 ipa_cp_c_finalize (void)
5203 max_count
= profile_count::uninitialized ();