1 /* Interprocedural constant propagation
2 Copyright (C) 2005-2018 Free Software Foundation, Inc.
4 Contributed by Razya Ladelsky <RAZYA@il.ibm.com> and Martin Jambor
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
23 /* Interprocedural constant propagation (IPA-CP).
25 The goal of this transformation is to
27 1) discover functions which are always invoked with some arguments with the
28 same known constant values and modify the functions so that the
29 subsequent optimizations can take advantage of the knowledge, and
31 2) partial specialization - create specialized versions of functions
32 transformed in this way if some parameters are known constants only in
33 certain contexts but the estimated tradeoff between speedup and cost size
36 The algorithm also propagates types and attempts to perform type based
37 devirtualization. Types are propagated much like constants.
39 The algorithm basically consists of three stages. In the first, functions
40 are analyzed one at a time and jump functions are constructed for all known
41 call-sites. In the second phase, the pass propagates information from the
42 jump functions across the call to reveal what values are available at what
43 call sites, performs estimations of effects of known values on functions and
44 their callees, and finally decides what specialized extra versions should be
45 created. In the third, the special versions materialize and appropriate
48 The algorithm used is to a certain extent based on "Interprocedural Constant
49 Propagation", by David Callahan, Keith D Cooper, Ken Kennedy, Linda Torczon,
50 Comp86, pg 152-161 and "A Methodology for Procedure Cloning" by Keith D
51 Cooper, Mary W. Hall, and Ken Kennedy.
54 First stage - intraprocedural analysis
55 =======================================
57 This phase computes jump_function and modification flags.
59 A jump function for a call-site represents the values passed as an actual
60 arguments of a given call-site. In principle, there are three types of
63 Pass through - the caller's formal parameter is passed as an actual
64 argument, plus an operation on it can be performed.
65 Constant - a constant is passed as an actual argument.
66 Unknown - neither of the above.
68 All jump function types are described in detail in ipa-prop.h, together with
69 the data structures that represent them and methods of accessing them.
71 ipcp_generate_summary() is the main function of the first stage.
73 Second stage - interprocedural analysis
74 ========================================
76 This stage is itself divided into two phases. In the first, we propagate
77 known values over the call graph, in the second, we make cloning decisions.
78 It uses a different algorithm than the original Callahan's paper.
80 First, we traverse the functions topologically from callers to callees and,
81 for each strongly connected component (SCC), we propagate constants
82 according to previously computed jump functions. We also record what known
83 values depend on other known values and estimate local effects. Finally, we
84 propagate cumulative information about these effects from dependent values
85 to those on which they depend.
87 Second, we again traverse the call graph in the same topological order and
88 make clones for functions which we know are called with the same values in
89 all contexts and decide about extra specialized clones of functions just for
90 some contexts - these decisions are based on both local estimates and
91 cumulative estimates propagated from callees.
93 ipcp_propagate_stage() and ipcp_decision_stage() together constitute the
96 Third phase - materialization of clones, call statement updates.
97 ============================================
99 This stage is currently performed by call graph code (mainly in cgraphunit.c
100 and tree-inline.c) according to instructions inserted to the call graph by
105 #include "coretypes.h"
108 #include "gimple-expr.h"
110 #include "alloc-pool.h"
111 #include "tree-pass.h"
113 #include "diagnostic.h"
114 #include "fold-const.h"
115 #include "gimple-fold.h"
116 #include "symbol-summary.h"
117 #include "tree-vrp.h"
118 #include "ipa-prop.h"
119 #include "tree-pretty-print.h"
120 #include "tree-inline.h"
122 #include "ipa-fnsummary.h"
123 #include "ipa-utils.h"
124 #include "tree-ssa-ccp.h"
125 #include "stringpool.h"
128 template <typename valtype
> class ipcp_value
;
130 /* Describes a particular source for an IPA-CP value. */
132 template <typename valtype
>
133 class ipcp_value_source
136 /* Aggregate offset of the source, negative if the source is scalar value of
137 the argument itself. */
138 HOST_WIDE_INT offset
;
139 /* The incoming edge that brought the value. */
141 /* If the jump function that resulted into his value was a pass-through or an
142 ancestor, this is the ipcp_value of the caller from which the described
143 value has been derived. Otherwise it is NULL. */
144 ipcp_value
<valtype
> *val
;
145 /* Next pointer in a linked list of sources of a value. */
146 ipcp_value_source
*next
;
147 /* If the jump function that resulted into his value was a pass-through or an
148 ancestor, this is the index of the parameter of the caller the jump
149 function references. */
153 /* Common ancestor for all ipcp_value instantiations. */
155 class ipcp_value_base
158 /* Time benefit and size cost that specializing the function for this value
159 would bring about in this function alone. */
160 int local_time_benefit
, local_size_cost
;
161 /* Time benefit and size cost that specializing the function for this value
162 can bring about in it's callees (transitively). */
163 int prop_time_benefit
, prop_size_cost
;
166 : local_time_benefit (0), local_size_cost (0),
167 prop_time_benefit (0), prop_size_cost (0) {}
170 /* Describes one particular value stored in struct ipcp_lattice. */
172 template <typename valtype
>
173 class ipcp_value
: public ipcp_value_base
176 /* The actual value for the given parameter. */
178 /* The list of sources from which this value originates. */
179 ipcp_value_source
<valtype
> *sources
;
180 /* Next pointers in a linked list of all values in a lattice. */
182 /* Next pointers in a linked list of values in a strongly connected component
184 ipcp_value
*scc_next
;
185 /* Next pointers in a linked list of SCCs of values sorted topologically
186 according their sources. */
187 ipcp_value
*topo_next
;
188 /* A specialized node created for this value, NULL if none has been (so far)
190 cgraph_node
*spec_node
;
191 /* Depth first search number and low link for topological sorting of
194 /* True if this valye is currently on the topo-sort stack. */
198 : sources (0), next (0), scc_next (0), topo_next (0),
199 spec_node (0), dfs (0), low_link (0), on_stack (false) {}
201 void add_source (cgraph_edge
*cs
, ipcp_value
*src_val
, int src_idx
,
202 HOST_WIDE_INT offset
);
205 /* Lattice describing potential values of a formal parameter of a function, or
206 a part of an aggregate. TOP is represented by a lattice with zero values
207 and with contains_variable and bottom flags cleared. BOTTOM is represented
208 by a lattice with the bottom flag set. In that case, values and
209 contains_variable flag should be disregarded. */
211 template <typename valtype
>
215 /* The list of known values and types in this lattice. Note that values are
216 not deallocated if a lattice is set to bottom because there may be value
217 sources referencing them. */
218 ipcp_value
<valtype
> *values
;
219 /* Number of known values and types in this lattice. */
221 /* The lattice contains a variable component (in addition to values). */
222 bool contains_variable
;
223 /* The value of the lattice is bottom (i.e. variable and unusable for any
227 inline bool is_single_const ();
228 inline bool set_to_bottom ();
229 inline bool set_contains_variable ();
230 bool add_value (valtype newval
, cgraph_edge
*cs
,
231 ipcp_value
<valtype
> *src_val
= NULL
,
232 int src_idx
= 0, HOST_WIDE_INT offset
= -1);
233 void print (FILE * f
, bool dump_sources
, bool dump_benefits
);
236 /* Lattice of tree values with an offset to describe a part of an
239 class ipcp_agg_lattice
: public ipcp_lattice
<tree
>
242 /* Offset that is being described by this lattice. */
243 HOST_WIDE_INT offset
;
244 /* Size so that we don't have to re-compute it every time we traverse the
245 list. Must correspond to TYPE_SIZE of all lat values. */
247 /* Next element of the linked list. */
248 struct ipcp_agg_lattice
*next
;
251 /* Lattice of known bits, only capable of holding one value.
252 Bitwise constant propagation propagates which bits of a
268 In the above case, the param 'x' will always have all
269 the bits (except the bits in lsb) set to 0.
270 Hence the mask of 'x' would be 0xff. The mask
271 reflects that the bits in lsb are unknown.
272 The actual propagated value is given by m_value & ~m_mask. */
274 class ipcp_bits_lattice
277 bool bottom_p () { return m_lattice_val
== IPA_BITS_VARYING
; }
278 bool top_p () { return m_lattice_val
== IPA_BITS_UNDEFINED
; }
279 bool constant_p () { return m_lattice_val
== IPA_BITS_CONSTANT
; }
280 bool set_to_bottom ();
281 bool set_to_constant (widest_int
, widest_int
);
283 widest_int
get_value () { return m_value
; }
284 widest_int
get_mask () { return m_mask
; }
286 bool meet_with (ipcp_bits_lattice
& other
, unsigned, signop
,
287 enum tree_code
, tree
);
289 bool meet_with (widest_int
, widest_int
, unsigned);
294 enum { IPA_BITS_UNDEFINED
, IPA_BITS_CONSTANT
, IPA_BITS_VARYING
} m_lattice_val
;
296 /* Similar to ccp_lattice_t, mask represents which bits of value are constant.
297 If a bit in mask is set to 0, then the corresponding bit in
298 value is known to be constant. */
299 widest_int m_value
, m_mask
;
301 bool meet_with_1 (widest_int
, widest_int
, unsigned);
302 void get_value_and_mask (tree
, widest_int
*, widest_int
*);
305 /* Lattice of value ranges. */
307 class ipcp_vr_lattice
312 inline bool bottom_p () const;
313 inline bool top_p () const;
314 inline bool set_to_bottom ();
315 bool meet_with (const value_range
*p_vr
);
316 bool meet_with (const ipcp_vr_lattice
&other
);
317 void init () { m_vr
.type
= VR_UNDEFINED
; }
318 void print (FILE * f
);
321 bool meet_with_1 (const value_range
*other_vr
);
324 /* Structure containing lattices for a parameter itself and for pieces of
325 aggregates that are passed in the parameter or by a reference in a parameter
326 plus some other useful flags. */
328 class ipcp_param_lattices
331 /* Lattice describing the value of the parameter itself. */
332 ipcp_lattice
<tree
> itself
;
333 /* Lattice describing the polymorphic contexts of a parameter. */
334 ipcp_lattice
<ipa_polymorphic_call_context
> ctxlat
;
335 /* Lattices describing aggregate parts. */
336 ipcp_agg_lattice
*aggs
;
337 /* Lattice describing known bits. */
338 ipcp_bits_lattice bits_lattice
;
339 /* Lattice describing value range. */
340 ipcp_vr_lattice m_value_range
;
341 /* Number of aggregate lattices */
343 /* True if aggregate data were passed by reference (as opposed to by
346 /* All aggregate lattices contain a variable component (in addition to
348 bool aggs_contain_variable
;
349 /* The value of all aggregate lattices is bottom (i.e. variable and unusable
350 for any propagation). */
353 /* There is a virtual call based on this parameter. */
357 /* Allocation pools for values and their sources in ipa-cp. */
359 object_allocator
<ipcp_value
<tree
> > ipcp_cst_values_pool
360 ("IPA-CP constant values");
362 object_allocator
<ipcp_value
<ipa_polymorphic_call_context
> >
363 ipcp_poly_ctx_values_pool ("IPA-CP polymorphic contexts");
365 object_allocator
<ipcp_value_source
<tree
> > ipcp_sources_pool
366 ("IPA-CP value sources");
368 object_allocator
<ipcp_agg_lattice
> ipcp_agg_lattice_pool
369 ("IPA_CP aggregate lattices");
371 /* Maximal count found in program. */
373 static profile_count max_count
;
375 /* Original overall size of the program. */
377 static long overall_size
, max_new_size
;
379 /* Return the param lattices structure corresponding to the Ith formal
380 parameter of the function described by INFO. */
381 static inline struct ipcp_param_lattices
*
382 ipa_get_parm_lattices (struct ipa_node_params
*info
, int i
)
384 gcc_assert (i
>= 0 && i
< ipa_get_param_count (info
));
385 gcc_checking_assert (!info
->ipcp_orig_node
);
386 gcc_checking_assert (info
->lattices
);
387 return &(info
->lattices
[i
]);
390 /* Return the lattice corresponding to the scalar value of the Ith formal
391 parameter of the function described by INFO. */
392 static inline ipcp_lattice
<tree
> *
393 ipa_get_scalar_lat (struct ipa_node_params
*info
, int i
)
395 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
396 return &plats
->itself
;
399 /* Return the lattice corresponding to the scalar value of the Ith formal
400 parameter of the function described by INFO. */
401 static inline ipcp_lattice
<ipa_polymorphic_call_context
> *
402 ipa_get_poly_ctx_lat (struct ipa_node_params
*info
, int i
)
404 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
405 return &plats
->ctxlat
;
408 /* Return the lattice corresponding to the value range of the Ith formal
409 parameter of the function described by INFO. */
411 static inline ipcp_vr_lattice
*
412 ipa_get_vr_lat (struct ipa_node_params
*info
, int i
)
414 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
415 return &plats
->m_value_range
;
418 /* Return whether LAT is a lattice with a single constant and without an
421 template <typename valtype
>
423 ipcp_lattice
<valtype
>::is_single_const ()
425 if (bottom
|| contains_variable
|| values_count
!= 1)
431 /* Print V which is extracted from a value in a lattice to F. */
434 print_ipcp_constant_value (FILE * f
, tree v
)
436 if (TREE_CODE (v
) == ADDR_EXPR
437 && TREE_CODE (TREE_OPERAND (v
, 0)) == CONST_DECL
)
440 print_generic_expr (f
, DECL_INITIAL (TREE_OPERAND (v
, 0)));
443 print_generic_expr (f
, v
);
446 /* Print V which is extracted from a value in a lattice to F. */
449 print_ipcp_constant_value (FILE * f
, ipa_polymorphic_call_context v
)
454 /* Print a lattice LAT to F. */
456 template <typename valtype
>
458 ipcp_lattice
<valtype
>::print (FILE * f
, bool dump_sources
, bool dump_benefits
)
460 ipcp_value
<valtype
> *val
;
465 fprintf (f
, "BOTTOM\n");
469 if (!values_count
&& !contains_variable
)
471 fprintf (f
, "TOP\n");
475 if (contains_variable
)
477 fprintf (f
, "VARIABLE");
483 for (val
= values
; val
; val
= val
->next
)
485 if (dump_benefits
&& prev
)
487 else if (!dump_benefits
&& prev
)
492 print_ipcp_constant_value (f
, val
->value
);
496 ipcp_value_source
<valtype
> *s
;
498 fprintf (f
, " [from:");
499 for (s
= val
->sources
; s
; s
= s
->next
)
500 fprintf (f
, " %i(%f)", s
->cs
->caller
->order
,
501 s
->cs
->sreal_frequency ().to_double ());
506 fprintf (f
, " [loc_time: %i, loc_size: %i, "
507 "prop_time: %i, prop_size: %i]\n",
508 val
->local_time_benefit
, val
->local_size_cost
,
509 val
->prop_time_benefit
, val
->prop_size_cost
);
516 ipcp_bits_lattice::print (FILE *f
)
519 fprintf (f
, " Bits unknown (TOP)\n");
520 else if (bottom_p ())
521 fprintf (f
, " Bits unusable (BOTTOM)\n");
524 fprintf (f
, " Bits: value = "); print_hex (get_value (), f
);
525 fprintf (f
, ", mask = "); print_hex (get_mask (), f
);
530 /* Print value range lattice to F. */
533 ipcp_vr_lattice::print (FILE * f
)
535 dump_value_range (f
, &m_vr
);
538 /* Print all ipcp_lattices of all functions to F. */
541 print_all_lattices (FILE * f
, bool dump_sources
, bool dump_benefits
)
543 struct cgraph_node
*node
;
546 fprintf (f
, "\nLattices:\n");
547 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
549 struct ipa_node_params
*info
;
551 info
= IPA_NODE_REF (node
);
552 fprintf (f
, " Node: %s:\n", node
->dump_name ());
553 count
= ipa_get_param_count (info
);
554 for (i
= 0; i
< count
; i
++)
556 struct ipcp_agg_lattice
*aglat
;
557 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
558 fprintf (f
, " param [%d]: ", i
);
559 plats
->itself
.print (f
, dump_sources
, dump_benefits
);
560 fprintf (f
, " ctxs: ");
561 plats
->ctxlat
.print (f
, dump_sources
, dump_benefits
);
562 plats
->bits_lattice
.print (f
);
564 plats
->m_value_range
.print (f
);
566 if (plats
->virt_call
)
567 fprintf (f
, " virt_call flag set\n");
569 if (plats
->aggs_bottom
)
571 fprintf (f
, " AGGS BOTTOM\n");
574 if (plats
->aggs_contain_variable
)
575 fprintf (f
, " AGGS VARIABLE\n");
576 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
578 fprintf (f
, " %soffset " HOST_WIDE_INT_PRINT_DEC
": ",
579 plats
->aggs_by_ref
? "ref " : "", aglat
->offset
);
580 aglat
->print (f
, dump_sources
, dump_benefits
);
586 /* Determine whether it is at all technically possible to create clones of NODE
587 and store this information in the ipa_node_params structure associated
591 determine_versionability (struct cgraph_node
*node
,
592 struct ipa_node_params
*info
)
594 const char *reason
= NULL
;
596 /* There are a number of generic reasons functions cannot be versioned. We
597 also cannot remove parameters if there are type attributes such as fnspec
599 if (node
->alias
|| node
->thunk
.thunk_p
)
600 reason
= "alias or thunk";
601 else if (!node
->local
.versionable
)
602 reason
= "not a tree_versionable_function";
603 else if (node
->get_availability () <= AVAIL_INTERPOSABLE
)
604 reason
= "insufficient body availability";
605 else if (!opt_for_fn (node
->decl
, optimize
)
606 || !opt_for_fn (node
->decl
, flag_ipa_cp
))
607 reason
= "non-optimized function";
608 else if (lookup_attribute ("omp declare simd", DECL_ATTRIBUTES (node
->decl
)))
610 /* Ideally we should clone the SIMD clones themselves and create
611 vector copies of them, so IPA-cp and SIMD clones can happily
612 coexist, but that may not be worth the effort. */
613 reason
= "function has SIMD clones";
615 else if (lookup_attribute ("target_clones", DECL_ATTRIBUTES (node
->decl
)))
617 /* Ideally we should clone the target clones themselves and create
618 copies of them, so IPA-cp and target clones can happily
619 coexist, but that may not be worth the effort. */
620 reason
= "function target_clones attribute";
622 /* Don't clone decls local to a comdat group; it breaks and for C++
623 decloned constructors, inlining is always better anyway. */
624 else if (node
->comdat_local_p ())
625 reason
= "comdat-local function";
626 else if (node
->calls_comdat_local
)
628 /* TODO: call is versionable if we make sure that all
629 callers are inside of a comdat group. */
630 reason
= "calls comdat-local function";
633 /* Functions calling BUILT_IN_VA_ARG_PACK and BUILT_IN_VA_ARG_PACK_LEN
634 work only when inlined. Cloning them may still lead to better code
635 because ipa-cp will not give up on cloning further. If the function is
636 external this however leads to wrong code because we may end up producing
637 offline copy of the function. */
638 if (DECL_EXTERNAL (node
->decl
))
639 for (cgraph_edge
*edge
= node
->callees
; !reason
&& edge
;
640 edge
= edge
->next_callee
)
641 if (DECL_BUILT_IN (edge
->callee
->decl
)
642 && DECL_BUILT_IN_CLASS (edge
->callee
->decl
) == BUILT_IN_NORMAL
)
644 if (DECL_FUNCTION_CODE (edge
->callee
->decl
) == BUILT_IN_VA_ARG_PACK
)
645 reason
= "external function which calls va_arg_pack";
646 if (DECL_FUNCTION_CODE (edge
->callee
->decl
)
647 == BUILT_IN_VA_ARG_PACK_LEN
)
648 reason
= "external function which calls va_arg_pack_len";
651 if (reason
&& dump_file
&& !node
->alias
&& !node
->thunk
.thunk_p
)
652 fprintf (dump_file
, "Function %s is not versionable, reason: %s.\n",
653 node
->dump_name (), reason
);
655 info
->versionable
= (reason
== NULL
);
658 /* Return true if it is at all technically possible to create clones of a
662 ipcp_versionable_function_p (struct cgraph_node
*node
)
664 return IPA_NODE_REF (node
)->versionable
;
667 /* Structure holding accumulated information about callers of a node. */
669 struct caller_statistics
671 profile_count count_sum
;
672 int n_calls
, n_hot_calls
, freq_sum
;
675 /* Initialize fields of STAT to zeroes. */
678 init_caller_stats (struct caller_statistics
*stats
)
680 stats
->count_sum
= profile_count::zero ();
682 stats
->n_hot_calls
= 0;
686 /* Worker callback of cgraph_for_node_and_aliases accumulating statistics of
687 non-thunk incoming edges to NODE. */
690 gather_caller_stats (struct cgraph_node
*node
, void *data
)
692 struct caller_statistics
*stats
= (struct caller_statistics
*) data
;
693 struct cgraph_edge
*cs
;
695 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
696 if (!cs
->caller
->thunk
.thunk_p
)
698 if (cs
->count
.ipa ().initialized_p ())
699 stats
->count_sum
+= cs
->count
.ipa ();
700 stats
->freq_sum
+= cs
->frequency ();
702 if (cs
->maybe_hot_p ())
703 stats
->n_hot_calls
++;
709 /* Return true if this NODE is viable candidate for cloning. */
712 ipcp_cloning_candidate_p (struct cgraph_node
*node
)
714 struct caller_statistics stats
;
716 gcc_checking_assert (node
->has_gimple_body_p ());
718 if (!opt_for_fn (node
->decl
, flag_ipa_cp_clone
))
721 fprintf (dump_file
, "Not considering %s for cloning; "
722 "-fipa-cp-clone disabled.\n",
727 if (node
->optimize_for_size_p ())
730 fprintf (dump_file
, "Not considering %s for cloning; "
731 "optimizing it for size.\n",
736 init_caller_stats (&stats
);
737 node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
, false);
739 if (ipa_fn_summaries
->get_create (node
)->self_size
< stats
.n_calls
)
742 fprintf (dump_file
, "Considering %s for cloning; code might shrink.\n",
747 /* When profile is available and function is hot, propagate into it even if
748 calls seems cold; constant propagation can improve function's speed
750 if (max_count
> profile_count::zero ())
752 if (stats
.count_sum
> node
->count
.ipa ().apply_scale (90, 100))
755 fprintf (dump_file
, "Considering %s for cloning; "
756 "usually called directly.\n",
761 if (!stats
.n_hot_calls
)
764 fprintf (dump_file
, "Not considering %s for cloning; no hot calls.\n",
769 fprintf (dump_file
, "Considering %s for cloning.\n",
774 template <typename valtype
>
775 class value_topo_info
778 /* Head of the linked list of topologically sorted values. */
779 ipcp_value
<valtype
> *values_topo
;
780 /* Stack for creating SCCs, represented by a linked list too. */
781 ipcp_value
<valtype
> *stack
;
782 /* Counter driving the algorithm in add_val_to_toposort. */
785 value_topo_info () : values_topo (NULL
), stack (NULL
), dfs_counter (0)
787 void add_val (ipcp_value
<valtype
> *cur_val
);
788 void propagate_effects ();
791 /* Arrays representing a topological ordering of call graph nodes and a stack
792 of nodes used during constant propagation and also data required to perform
793 topological sort of values and propagation of benefits in the determined
799 /* Array with obtained topological order of cgraph nodes. */
800 struct cgraph_node
**order
;
801 /* Stack of cgraph nodes used during propagation within SCC until all values
802 in the SCC stabilize. */
803 struct cgraph_node
**stack
;
804 int nnodes
, stack_top
;
806 value_topo_info
<tree
> constants
;
807 value_topo_info
<ipa_polymorphic_call_context
> contexts
;
809 ipa_topo_info () : order(NULL
), stack(NULL
), nnodes(0), stack_top(0),
814 /* Allocate the arrays in TOPO and topologically sort the nodes into order. */
817 build_toporder_info (struct ipa_topo_info
*topo
)
819 topo
->order
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
820 topo
->stack
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
822 gcc_checking_assert (topo
->stack_top
== 0);
823 topo
->nnodes
= ipa_reduced_postorder (topo
->order
, true, true, NULL
);
826 /* Free information about strongly connected components and the arrays in
830 free_toporder_info (struct ipa_topo_info
*topo
)
832 ipa_free_postorder_info ();
837 /* Add NODE to the stack in TOPO, unless it is already there. */
840 push_node_to_stack (struct ipa_topo_info
*topo
, struct cgraph_node
*node
)
842 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
843 if (info
->node_enqueued
)
845 info
->node_enqueued
= 1;
846 topo
->stack
[topo
->stack_top
++] = node
;
849 /* Pop a node from the stack in TOPO and return it or return NULL if the stack
852 static struct cgraph_node
*
853 pop_node_from_stack (struct ipa_topo_info
*topo
)
857 struct cgraph_node
*node
;
859 node
= topo
->stack
[topo
->stack_top
];
860 IPA_NODE_REF (node
)->node_enqueued
= 0;
867 /* Set lattice LAT to bottom and return true if it previously was not set as
870 template <typename valtype
>
872 ipcp_lattice
<valtype
>::set_to_bottom ()
879 /* Mark lattice as containing an unknown value and return true if it previously
880 was not marked as such. */
882 template <typename valtype
>
884 ipcp_lattice
<valtype
>::set_contains_variable ()
886 bool ret
= !contains_variable
;
887 contains_variable
= true;
891 /* Set all aggegate lattices in PLATS to bottom and return true if they were
892 not previously set as such. */
895 set_agg_lats_to_bottom (struct ipcp_param_lattices
*plats
)
897 bool ret
= !plats
->aggs_bottom
;
898 plats
->aggs_bottom
= true;
902 /* Mark all aggegate lattices in PLATS as containing an unknown value and
903 return true if they were not previously marked as such. */
906 set_agg_lats_contain_variable (struct ipcp_param_lattices
*plats
)
908 bool ret
= !plats
->aggs_contain_variable
;
909 plats
->aggs_contain_variable
= true;
914 ipcp_vr_lattice::meet_with (const ipcp_vr_lattice
&other
)
916 return meet_with_1 (&other
.m_vr
);
919 /* Meet the current value of the lattice with value ranfge described by VR
923 ipcp_vr_lattice::meet_with (const value_range
*p_vr
)
925 return meet_with_1 (p_vr
);
928 /* Meet the current value of the lattice with value ranfge described by
932 ipcp_vr_lattice::meet_with_1 (const value_range
*other_vr
)
934 tree min
= m_vr
.min
, max
= m_vr
.max
;
935 value_range_type type
= m_vr
.type
;
940 if (other_vr
->type
== VR_VARYING
)
941 return set_to_bottom ();
943 vrp_meet (&m_vr
, other_vr
);
944 if (type
!= m_vr
.type
952 /* Return true if value range information in the lattice is yet unknown. */
955 ipcp_vr_lattice::top_p () const
957 return m_vr
.type
== VR_UNDEFINED
;
960 /* Return true if value range information in the lattice is known to be
964 ipcp_vr_lattice::bottom_p () const
966 return m_vr
.type
== VR_VARYING
;
969 /* Set value range information in the lattice to bottom. Return true if it
970 previously was in a different state. */
973 ipcp_vr_lattice::set_to_bottom ()
975 if (m_vr
.type
== VR_VARYING
)
977 m_vr
.type
= VR_VARYING
;
981 /* Set lattice value to bottom, if it already isn't the case. */
984 ipcp_bits_lattice::set_to_bottom ()
988 m_lattice_val
= IPA_BITS_VARYING
;
994 /* Set to constant if it isn't already. Only meant to be called
995 when switching state from TOP. */
998 ipcp_bits_lattice::set_to_constant (widest_int value
, widest_int mask
)
1000 gcc_assert (top_p ());
1001 m_lattice_val
= IPA_BITS_CONSTANT
;
1007 /* Convert operand to value, mask form. */
1010 ipcp_bits_lattice::get_value_and_mask (tree operand
, widest_int
*valuep
, widest_int
*maskp
)
1012 wide_int
get_nonzero_bits (const_tree
);
1014 if (TREE_CODE (operand
) == INTEGER_CST
)
1016 *valuep
= wi::to_widest (operand
);
1026 /* Meet operation, similar to ccp_lattice_meet, we xor values
1027 if this->value, value have different values at same bit positions, we want
1028 to drop that bit to varying. Return true if mask is changed.
1029 This function assumes that the lattice value is in CONSTANT state */
1032 ipcp_bits_lattice::meet_with_1 (widest_int value
, widest_int mask
,
1035 gcc_assert (constant_p ());
1037 widest_int old_mask
= m_mask
;
1038 m_mask
= (m_mask
| mask
) | (m_value
^ value
);
1040 if (wi::sext (m_mask
, precision
) == -1)
1041 return set_to_bottom ();
1043 return m_mask
!= old_mask
;
1046 /* Meet the bits lattice with operand
1047 described by <value, mask, sgn, precision. */
1050 ipcp_bits_lattice::meet_with (widest_int value
, widest_int mask
,
1058 if (wi::sext (mask
, precision
) == -1)
1059 return set_to_bottom ();
1060 return set_to_constant (value
, mask
);
1063 return meet_with_1 (value
, mask
, precision
);
1066 /* Meet bits lattice with the result of bit_value_binop (other, operand)
1067 if code is binary operation or bit_value_unop (other) if code is unary op.
1068 In the case when code is nop_expr, no adjustment is required. */
1071 ipcp_bits_lattice::meet_with (ipcp_bits_lattice
& other
, unsigned precision
,
1072 signop sgn
, enum tree_code code
, tree operand
)
1074 if (other
.bottom_p ())
1075 return set_to_bottom ();
1077 if (bottom_p () || other
.top_p ())
1080 widest_int adjusted_value
, adjusted_mask
;
1082 if (TREE_CODE_CLASS (code
) == tcc_binary
)
1084 tree type
= TREE_TYPE (operand
);
1085 gcc_assert (INTEGRAL_TYPE_P (type
));
1086 widest_int o_value
, o_mask
;
1087 get_value_and_mask (operand
, &o_value
, &o_mask
);
1089 bit_value_binop (code
, sgn
, precision
, &adjusted_value
, &adjusted_mask
,
1090 sgn
, precision
, other
.get_value (), other
.get_mask (),
1091 TYPE_SIGN (type
), TYPE_PRECISION (type
), o_value
, o_mask
);
1093 if (wi::sext (adjusted_mask
, precision
) == -1)
1094 return set_to_bottom ();
1097 else if (TREE_CODE_CLASS (code
) == tcc_unary
)
1099 bit_value_unop (code
, sgn
, precision
, &adjusted_value
,
1100 &adjusted_mask
, sgn
, precision
, other
.get_value (),
1103 if (wi::sext (adjusted_mask
, precision
) == -1)
1104 return set_to_bottom ();
1108 return set_to_bottom ();
1112 if (wi::sext (adjusted_mask
, precision
) == -1)
1113 return set_to_bottom ();
1114 return set_to_constant (adjusted_value
, adjusted_mask
);
1117 return meet_with_1 (adjusted_value
, adjusted_mask
, precision
);
1120 /* Mark bot aggregate and scalar lattices as containing an unknown variable,
1121 return true is any of them has not been marked as such so far. */
1124 set_all_contains_variable (struct ipcp_param_lattices
*plats
)
1127 ret
= plats
->itself
.set_contains_variable ();
1128 ret
|= plats
->ctxlat
.set_contains_variable ();
1129 ret
|= set_agg_lats_contain_variable (plats
);
1130 ret
|= plats
->bits_lattice
.set_to_bottom ();
1131 ret
|= plats
->m_value_range
.set_to_bottom ();
1135 /* Worker of call_for_symbol_thunks_and_aliases, increment the integer DATA
1136 points to by the number of callers to NODE. */
1139 count_callers (cgraph_node
*node
, void *data
)
1141 int *caller_count
= (int *) data
;
1143 for (cgraph_edge
*cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
1144 /* Local thunks can be handled transparently, but if the thunk can not
1145 be optimized out, count it as a real use. */
1146 if (!cs
->caller
->thunk
.thunk_p
|| !cs
->caller
->local
.local
)
1151 /* Worker of call_for_symbol_thunks_and_aliases, it is supposed to be called on
1152 the one caller of some other node. Set the caller's corresponding flag. */
1155 set_single_call_flag (cgraph_node
*node
, void *)
1157 cgraph_edge
*cs
= node
->callers
;
1158 /* Local thunks can be handled transparently, skip them. */
1159 while (cs
&& cs
->caller
->thunk
.thunk_p
&& cs
->caller
->local
.local
)
1160 cs
= cs
->next_caller
;
1163 IPA_NODE_REF (cs
->caller
)->node_calling_single_call
= true;
1169 /* Initialize ipcp_lattices. */
1172 initialize_node_lattices (struct cgraph_node
*node
)
1174 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1175 struct cgraph_edge
*ie
;
1176 bool disable
= false, variable
= false;
1179 gcc_checking_assert (node
->has_gimple_body_p ());
1180 if (node
->local
.local
)
1182 int caller_count
= 0;
1183 node
->call_for_symbol_thunks_and_aliases (count_callers
, &caller_count
,
1185 gcc_checking_assert (caller_count
> 0);
1186 if (caller_count
== 1)
1187 node
->call_for_symbol_thunks_and_aliases (set_single_call_flag
,
1192 /* When cloning is allowed, we can assume that externally visible
1193 functions are not called. We will compensate this by cloning
1195 if (ipcp_versionable_function_p (node
)
1196 && ipcp_cloning_candidate_p (node
))
1202 for (i
= 0; i
< ipa_get_param_count (info
); i
++)
1204 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1205 plats
->m_value_range
.init ();
1208 if (disable
|| variable
)
1210 for (i
= 0; i
< ipa_get_param_count (info
); i
++)
1212 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1215 plats
->itself
.set_to_bottom ();
1216 plats
->ctxlat
.set_to_bottom ();
1217 set_agg_lats_to_bottom (plats
);
1218 plats
->bits_lattice
.set_to_bottom ();
1219 plats
->m_value_range
.set_to_bottom ();
1222 set_all_contains_variable (plats
);
1224 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1225 && !node
->alias
&& !node
->thunk
.thunk_p
)
1226 fprintf (dump_file
, "Marking all lattices of %s as %s\n",
1227 node
->dump_name (), disable
? "BOTTOM" : "VARIABLE");
1230 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
1231 if (ie
->indirect_info
->polymorphic
1232 && ie
->indirect_info
->param_index
>= 0)
1234 gcc_checking_assert (ie
->indirect_info
->param_index
>= 0);
1235 ipa_get_parm_lattices (info
,
1236 ie
->indirect_info
->param_index
)->virt_call
= 1;
1240 /* Return the result of a (possibly arithmetic) pass through jump function
1241 JFUNC on the constant value INPUT. RES_TYPE is the type of the parameter
1242 to which the result is passed. Return NULL_TREE if that cannot be
1243 determined or be considered an interprocedural invariant. */
1246 ipa_get_jf_pass_through_result (struct ipa_jump_func
*jfunc
, tree input
,
1251 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
1253 if (!is_gimple_ip_invariant (input
))
1256 tree_code opcode
= ipa_get_jf_pass_through_operation (jfunc
);
1259 if (TREE_CODE_CLASS (opcode
) == tcc_comparison
)
1260 res_type
= boolean_type_node
;
1261 else if (expr_type_first_operand_type_p (opcode
))
1262 res_type
= TREE_TYPE (input
);
1267 if (TREE_CODE_CLASS (opcode
) == tcc_unary
)
1268 res
= fold_unary (opcode
, res_type
, input
);
1270 res
= fold_binary (opcode
, res_type
, input
,
1271 ipa_get_jf_pass_through_operand (jfunc
));
1273 if (res
&& !is_gimple_ip_invariant (res
))
1279 /* Return the result of an ancestor jump function JFUNC on the constant value
1280 INPUT. Return NULL_TREE if that cannot be determined. */
1283 ipa_get_jf_ancestor_result (struct ipa_jump_func
*jfunc
, tree input
)
1285 gcc_checking_assert (TREE_CODE (input
) != TREE_BINFO
);
1286 if (TREE_CODE (input
) == ADDR_EXPR
)
1288 tree t
= TREE_OPERAND (input
, 0);
1289 t
= build_ref_for_offset (EXPR_LOCATION (t
), t
,
1290 ipa_get_jf_ancestor_offset (jfunc
), false,
1291 ptr_type_node
, NULL
, false);
1292 return build_fold_addr_expr (t
);
1298 /* Determine whether JFUNC evaluates to a single known constant value and if
1299 so, return it. Otherwise return NULL. INFO describes the caller node or
1300 the one it is inlined to, so that pass-through jump functions can be
1301 evaluated. PARM_TYPE is the type of the parameter to which the result is
1305 ipa_value_from_jfunc (struct ipa_node_params
*info
, struct ipa_jump_func
*jfunc
,
1308 if (jfunc
->type
== IPA_JF_CONST
)
1309 return ipa_get_jf_constant (jfunc
);
1310 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1311 || jfunc
->type
== IPA_JF_ANCESTOR
)
1316 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1317 idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1319 idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1321 if (info
->ipcp_orig_node
)
1322 input
= info
->known_csts
[idx
];
1325 ipcp_lattice
<tree
> *lat
;
1328 || idx
>= ipa_get_param_count (info
))
1330 lat
= ipa_get_scalar_lat (info
, idx
);
1331 if (!lat
->is_single_const ())
1333 input
= lat
->values
->value
;
1339 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1340 return ipa_get_jf_pass_through_result (jfunc
, input
, parm_type
);
1342 return ipa_get_jf_ancestor_result (jfunc
, input
);
1348 /* Determie whether JFUNC evaluates to single known polymorphic context, given
1349 that INFO describes the caller node or the one it is inlined to, CS is the
1350 call graph edge corresponding to JFUNC and CSIDX index of the described
1353 ipa_polymorphic_call_context
1354 ipa_context_from_jfunc (ipa_node_params
*info
, cgraph_edge
*cs
, int csidx
,
1355 ipa_jump_func
*jfunc
)
1357 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
1358 ipa_polymorphic_call_context ctx
;
1359 ipa_polymorphic_call_context
*edge_ctx
1360 = cs
? ipa_get_ith_polymorhic_call_context (args
, csidx
) : NULL
;
1362 if (edge_ctx
&& !edge_ctx
->useless_p ())
1365 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1366 || jfunc
->type
== IPA_JF_ANCESTOR
)
1368 ipa_polymorphic_call_context srcctx
;
1370 bool type_preserved
= true;
1371 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1373 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1375 type_preserved
= ipa_get_jf_pass_through_type_preserved (jfunc
);
1376 srcidx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1380 type_preserved
= ipa_get_jf_ancestor_type_preserved (jfunc
);
1381 srcidx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1383 if (info
->ipcp_orig_node
)
1385 if (info
->known_contexts
.exists ())
1386 srcctx
= info
->known_contexts
[srcidx
];
1391 || srcidx
>= ipa_get_param_count (info
))
1393 ipcp_lattice
<ipa_polymorphic_call_context
> *lat
;
1394 lat
= ipa_get_poly_ctx_lat (info
, srcidx
);
1395 if (!lat
->is_single_const ())
1397 srcctx
= lat
->values
->value
;
1399 if (srcctx
.useless_p ())
1401 if (jfunc
->type
== IPA_JF_ANCESTOR
)
1402 srcctx
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
1403 if (!type_preserved
)
1404 srcctx
.possible_dynamic_type_change (cs
->in_polymorphic_cdtor
);
1405 srcctx
.combine_with (ctx
);
1412 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
1413 bottom, not containing a variable component and without any known value at
1417 ipcp_verify_propagated_values (void)
1419 struct cgraph_node
*node
;
1421 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
1423 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1424 int i
, count
= ipa_get_param_count (info
);
1426 for (i
= 0; i
< count
; i
++)
1428 ipcp_lattice
<tree
> *lat
= ipa_get_scalar_lat (info
, i
);
1431 && !lat
->contains_variable
1432 && lat
->values_count
== 0)
1436 symtab
->dump (dump_file
);
1437 fprintf (dump_file
, "\nIPA lattices after constant "
1438 "propagation, before gcc_unreachable:\n");
1439 print_all_lattices (dump_file
, true, false);
1448 /* Return true iff X and Y should be considered equal values by IPA-CP. */
1451 values_equal_for_ipcp_p (tree x
, tree y
)
1453 gcc_checking_assert (x
!= NULL_TREE
&& y
!= NULL_TREE
);
1458 if (TREE_CODE (x
) == ADDR_EXPR
1459 && TREE_CODE (y
) == ADDR_EXPR
1460 && TREE_CODE (TREE_OPERAND (x
, 0)) == CONST_DECL
1461 && TREE_CODE (TREE_OPERAND (y
, 0)) == CONST_DECL
)
1462 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x
, 0)),
1463 DECL_INITIAL (TREE_OPERAND (y
, 0)), 0);
1465 return operand_equal_p (x
, y
, 0);
1468 /* Return true iff X and Y should be considered equal contexts by IPA-CP. */
1471 values_equal_for_ipcp_p (ipa_polymorphic_call_context x
,
1472 ipa_polymorphic_call_context y
)
1474 return x
.equal_to (y
);
1478 /* Add a new value source to the value represented by THIS, marking that a
1479 value comes from edge CS and (if the underlying jump function is a
1480 pass-through or an ancestor one) from a caller value SRC_VAL of a caller
1481 parameter described by SRC_INDEX. OFFSET is negative if the source was the
1482 scalar value of the parameter itself or the offset within an aggregate. */
1484 template <typename valtype
>
1486 ipcp_value
<valtype
>::add_source (cgraph_edge
*cs
, ipcp_value
*src_val
,
1487 int src_idx
, HOST_WIDE_INT offset
)
1489 ipcp_value_source
<valtype
> *src
;
1491 src
= new (ipcp_sources_pool
.allocate ()) ipcp_value_source
<valtype
>;
1492 src
->offset
= offset
;
1495 src
->index
= src_idx
;
1497 src
->next
= sources
;
1501 /* Allocate a new ipcp_value holding a tree constant, initialize its value to
1502 SOURCE and clear all other fields. */
1504 static ipcp_value
<tree
> *
1505 allocate_and_init_ipcp_value (tree source
)
1507 ipcp_value
<tree
> *val
;
1509 val
= new (ipcp_cst_values_pool
.allocate ()) ipcp_value
<tree
>();
1510 val
->value
= source
;
1514 /* Allocate a new ipcp_value holding a polymorphic context, initialize its
1515 value to SOURCE and clear all other fields. */
1517 static ipcp_value
<ipa_polymorphic_call_context
> *
1518 allocate_and_init_ipcp_value (ipa_polymorphic_call_context source
)
1520 ipcp_value
<ipa_polymorphic_call_context
> *val
;
1523 val
= new (ipcp_poly_ctx_values_pool
.allocate ())
1524 ipcp_value
<ipa_polymorphic_call_context
>();
1525 val
->value
= source
;
1529 /* Try to add NEWVAL to LAT, potentially creating a new ipcp_value for it. CS,
1530 SRC_VAL SRC_INDEX and OFFSET are meant for add_source and have the same
1531 meaning. OFFSET -1 means the source is scalar and not a part of an
1534 template <typename valtype
>
1536 ipcp_lattice
<valtype
>::add_value (valtype newval
, cgraph_edge
*cs
,
1537 ipcp_value
<valtype
> *src_val
,
1538 int src_idx
, HOST_WIDE_INT offset
)
1540 ipcp_value
<valtype
> *val
;
1545 for (val
= values
; val
; val
= val
->next
)
1546 if (values_equal_for_ipcp_p (val
->value
, newval
))
1548 if (ipa_edge_within_scc (cs
))
1550 ipcp_value_source
<valtype
> *s
;
1551 for (s
= val
->sources
; s
; s
= s
->next
)
1558 val
->add_source (cs
, src_val
, src_idx
, offset
);
1562 if (values_count
== PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE
))
1564 /* We can only free sources, not the values themselves, because sources
1565 of other values in this SCC might point to them. */
1566 for (val
= values
; val
; val
= val
->next
)
1568 while (val
->sources
)
1570 ipcp_value_source
<valtype
> *src
= val
->sources
;
1571 val
->sources
= src
->next
;
1572 ipcp_sources_pool
.remove ((ipcp_value_source
<tree
>*)src
);
1577 return set_to_bottom ();
1581 val
= allocate_and_init_ipcp_value (newval
);
1582 val
->add_source (cs
, src_val
, src_idx
, offset
);
1588 /* Propagate values through a pass-through jump function JFUNC associated with
1589 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1590 is the index of the source parameter. PARM_TYPE is the type of the
1591 parameter to which the result is passed. */
1594 propagate_vals_across_pass_through (cgraph_edge
*cs
, ipa_jump_func
*jfunc
,
1595 ipcp_lattice
<tree
> *src_lat
,
1596 ipcp_lattice
<tree
> *dest_lat
, int src_idx
,
1599 ipcp_value
<tree
> *src_val
;
1602 /* Do not create new values when propagating within an SCC because if there
1603 are arithmetic functions with circular dependencies, there is infinite
1604 number of them and we would just make lattices bottom. If this condition
1605 is ever relaxed we have to detect self-feeding recursive calls in
1606 cgraph_edge_brings_value_p in a smarter way. */
1607 if ((ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1608 && ipa_edge_within_scc (cs
))
1609 ret
= dest_lat
->set_contains_variable ();
1611 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1613 tree cstval
= ipa_get_jf_pass_through_result (jfunc
, src_val
->value
,
1617 ret
|= dest_lat
->add_value (cstval
, cs
, src_val
, src_idx
);
1619 ret
|= dest_lat
->set_contains_variable ();
1625 /* Propagate values through an ancestor jump function JFUNC associated with
1626 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1627 is the index of the source parameter. */
1630 propagate_vals_across_ancestor (struct cgraph_edge
*cs
,
1631 struct ipa_jump_func
*jfunc
,
1632 ipcp_lattice
<tree
> *src_lat
,
1633 ipcp_lattice
<tree
> *dest_lat
, int src_idx
)
1635 ipcp_value
<tree
> *src_val
;
1638 if (ipa_edge_within_scc (cs
))
1639 return dest_lat
->set_contains_variable ();
1641 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1643 tree t
= ipa_get_jf_ancestor_result (jfunc
, src_val
->value
);
1646 ret
|= dest_lat
->add_value (t
, cs
, src_val
, src_idx
);
1648 ret
|= dest_lat
->set_contains_variable ();
1654 /* Propagate scalar values across jump function JFUNC that is associated with
1655 edge CS and put the values into DEST_LAT. PARM_TYPE is the type of the
1656 parameter to which the result is passed. */
1659 propagate_scalar_across_jump_function (struct cgraph_edge
*cs
,
1660 struct ipa_jump_func
*jfunc
,
1661 ipcp_lattice
<tree
> *dest_lat
,
1664 if (dest_lat
->bottom
)
1667 if (jfunc
->type
== IPA_JF_CONST
)
1669 tree val
= ipa_get_jf_constant (jfunc
);
1670 return dest_lat
->add_value (val
, cs
, NULL
, 0);
1672 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1673 || jfunc
->type
== IPA_JF_ANCESTOR
)
1675 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1676 ipcp_lattice
<tree
> *src_lat
;
1680 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1681 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1683 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1685 src_lat
= ipa_get_scalar_lat (caller_info
, src_idx
);
1686 if (src_lat
->bottom
)
1687 return dest_lat
->set_contains_variable ();
1689 /* If we would need to clone the caller and cannot, do not propagate. */
1690 if (!ipcp_versionable_function_p (cs
->caller
)
1691 && (src_lat
->contains_variable
1692 || (src_lat
->values_count
> 1)))
1693 return dest_lat
->set_contains_variable ();
1695 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1696 ret
= propagate_vals_across_pass_through (cs
, jfunc
, src_lat
,
1697 dest_lat
, src_idx
, param_type
);
1699 ret
= propagate_vals_across_ancestor (cs
, jfunc
, src_lat
, dest_lat
,
1702 if (src_lat
->contains_variable
)
1703 ret
|= dest_lat
->set_contains_variable ();
1708 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1709 use it for indirect inlining), we should propagate them too. */
1710 return dest_lat
->set_contains_variable ();
1713 /* Propagate scalar values across jump function JFUNC that is associated with
1714 edge CS and describes argument IDX and put the values into DEST_LAT. */
1717 propagate_context_across_jump_function (cgraph_edge
*cs
,
1718 ipa_jump_func
*jfunc
, int idx
,
1719 ipcp_lattice
<ipa_polymorphic_call_context
> *dest_lat
)
1721 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
1722 if (dest_lat
->bottom
)
1725 bool added_sth
= false;
1726 bool type_preserved
= true;
1728 ipa_polymorphic_call_context edge_ctx
, *edge_ctx_ptr
1729 = ipa_get_ith_polymorhic_call_context (args
, idx
);
1732 edge_ctx
= *edge_ctx_ptr
;
1734 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1735 || jfunc
->type
== IPA_JF_ANCESTOR
)
1737 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1739 ipcp_lattice
<ipa_polymorphic_call_context
> *src_lat
;
1741 /* TODO: Once we figure out how to propagate speculations, it will
1742 probably be a good idea to switch to speculation if type_preserved is
1743 not set instead of punting. */
1744 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1746 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1748 type_preserved
= ipa_get_jf_pass_through_type_preserved (jfunc
);
1749 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1753 type_preserved
= ipa_get_jf_ancestor_type_preserved (jfunc
);
1754 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1757 src_lat
= ipa_get_poly_ctx_lat (caller_info
, src_idx
);
1758 /* If we would need to clone the caller and cannot, do not propagate. */
1759 if (!ipcp_versionable_function_p (cs
->caller
)
1760 && (src_lat
->contains_variable
1761 || (src_lat
->values_count
> 1)))
1764 ipcp_value
<ipa_polymorphic_call_context
> *src_val
;
1765 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1767 ipa_polymorphic_call_context cur
= src_val
->value
;
1769 if (!type_preserved
)
1770 cur
.possible_dynamic_type_change (cs
->in_polymorphic_cdtor
);
1771 if (jfunc
->type
== IPA_JF_ANCESTOR
)
1772 cur
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
1773 /* TODO: In cases we know how the context is going to be used,
1774 we can improve the result by passing proper OTR_TYPE. */
1775 cur
.combine_with (edge_ctx
);
1776 if (!cur
.useless_p ())
1778 if (src_lat
->contains_variable
1779 && !edge_ctx
.equal_to (cur
))
1780 ret
|= dest_lat
->set_contains_variable ();
1781 ret
|= dest_lat
->add_value (cur
, cs
, src_val
, src_idx
);
1791 if (!edge_ctx
.useless_p ())
1792 ret
|= dest_lat
->add_value (edge_ctx
, cs
);
1794 ret
|= dest_lat
->set_contains_variable ();
1800 /* Propagate bits across jfunc that is associated with
1801 edge cs and update dest_lattice accordingly. */
1804 propagate_bits_across_jump_function (cgraph_edge
*cs
, int idx
,
1805 ipa_jump_func
*jfunc
,
1806 ipcp_bits_lattice
*dest_lattice
)
1808 if (dest_lattice
->bottom_p ())
1811 enum availability availability
;
1812 cgraph_node
*callee
= cs
->callee
->function_symbol (&availability
);
1813 struct ipa_node_params
*callee_info
= IPA_NODE_REF (callee
);
1814 tree parm_type
= ipa_get_type (callee_info
, idx
);
1816 /* For K&R C programs, ipa_get_type() could return NULL_TREE. Avoid the
1817 transform for these cases. Similarly, we can have bad type mismatches
1818 with LTO, avoid doing anything with those too. */
1820 || (!INTEGRAL_TYPE_P (parm_type
) && !POINTER_TYPE_P (parm_type
)))
1822 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1823 fprintf (dump_file
, "Setting dest_lattice to bottom, because type of "
1824 "param %i of %s is NULL or unsuitable for bits propagation\n",
1825 idx
, cs
->callee
->name ());
1827 return dest_lattice
->set_to_bottom ();
1830 unsigned precision
= TYPE_PRECISION (parm_type
);
1831 signop sgn
= TYPE_SIGN (parm_type
);
1833 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1834 || jfunc
->type
== IPA_JF_ANCESTOR
)
1836 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1837 tree operand
= NULL_TREE
;
1838 enum tree_code code
;
1841 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1843 code
= ipa_get_jf_pass_through_operation (jfunc
);
1844 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1845 if (code
!= NOP_EXPR
)
1846 operand
= ipa_get_jf_pass_through_operand (jfunc
);
1850 code
= POINTER_PLUS_EXPR
;
1851 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1852 unsigned HOST_WIDE_INT offset
= ipa_get_jf_ancestor_offset (jfunc
) / BITS_PER_UNIT
;
1853 operand
= build_int_cstu (size_type_node
, offset
);
1856 struct ipcp_param_lattices
*src_lats
1857 = ipa_get_parm_lattices (caller_info
, src_idx
);
1859 /* Try to propagate bits if src_lattice is bottom, but jfunc is known.
1865 Assume lattice for x is bottom, however we can still propagate
1866 result of x & 0xff == 0xff, which gets computed during ccp1 pass
1867 and we store it in jump function during analysis stage. */
1869 if (src_lats
->bits_lattice
.bottom_p ()
1871 return dest_lattice
->meet_with (jfunc
->bits
->value
, jfunc
->bits
->mask
,
1874 return dest_lattice
->meet_with (src_lats
->bits_lattice
, precision
, sgn
,
1878 else if (jfunc
->type
== IPA_JF_ANCESTOR
)
1879 return dest_lattice
->set_to_bottom ();
1880 else if (jfunc
->bits
)
1881 return dest_lattice
->meet_with (jfunc
->bits
->value
, jfunc
->bits
->mask
,
1884 return dest_lattice
->set_to_bottom ();
1887 /* Emulate effects of unary OPERATION and/or conversion from SRC_TYPE to
1888 DST_TYPE on value range in SRC_VR and store it to DST_VR. Return true if
1889 the result is a range or an anti-range. */
1892 ipa_vr_operation_and_type_effects (value_range
*dst_vr
, value_range
*src_vr
,
1893 enum tree_code operation
,
1894 tree dst_type
, tree src_type
)
1896 memset (dst_vr
, 0, sizeof (*dst_vr
));
1897 extract_range_from_unary_expr (dst_vr
, operation
, dst_type
, src_vr
, src_type
);
1898 if (dst_vr
->type
== VR_RANGE
|| dst_vr
->type
== VR_ANTI_RANGE
)
1904 /* Propagate value range across jump function JFUNC that is associated with
1905 edge CS with param of callee of PARAM_TYPE and update DEST_PLATS
1909 propagate_vr_across_jump_function (cgraph_edge
*cs
, ipa_jump_func
*jfunc
,
1910 struct ipcp_param_lattices
*dest_plats
,
1913 ipcp_vr_lattice
*dest_lat
= &dest_plats
->m_value_range
;
1915 if (dest_lat
->bottom_p ())
1919 || (!INTEGRAL_TYPE_P (param_type
)
1920 && !POINTER_TYPE_P (param_type
)))
1921 return dest_lat
->set_to_bottom ();
1923 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1925 enum tree_code operation
= ipa_get_jf_pass_through_operation (jfunc
);
1927 if (TREE_CODE_CLASS (operation
) == tcc_unary
)
1929 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1930 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1931 tree operand_type
= ipa_get_type (caller_info
, src_idx
);
1932 struct ipcp_param_lattices
*src_lats
1933 = ipa_get_parm_lattices (caller_info
, src_idx
);
1935 if (src_lats
->m_value_range
.bottom_p ())
1936 return dest_lat
->set_to_bottom ();
1938 if (ipa_vr_operation_and_type_effects (&vr
,
1939 &src_lats
->m_value_range
.m_vr
,
1940 operation
, param_type
,
1942 return dest_lat
->meet_with (&vr
);
1945 else if (jfunc
->type
== IPA_JF_CONST
)
1947 tree val
= ipa_get_jf_constant (jfunc
);
1948 if (TREE_CODE (val
) == INTEGER_CST
)
1950 val
= fold_convert (param_type
, val
);
1951 if (TREE_OVERFLOW_P (val
))
1952 val
= drop_tree_overflow (val
);
1955 memset (&tmpvr
, 0, sizeof (tmpvr
));
1956 tmpvr
.type
= VR_RANGE
;
1959 return dest_lat
->meet_with (&tmpvr
);
1965 && ipa_vr_operation_and_type_effects (&vr
, jfunc
->m_vr
, NOP_EXPR
,
1967 TREE_TYPE (jfunc
->m_vr
->min
)))
1968 return dest_lat
->meet_with (&vr
);
1970 return dest_lat
->set_to_bottom ();
1973 /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
1974 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
1975 other cases, return false). If there are no aggregate items, set
1976 aggs_by_ref to NEW_AGGS_BY_REF. */
1979 set_check_aggs_by_ref (struct ipcp_param_lattices
*dest_plats
,
1980 bool new_aggs_by_ref
)
1982 if (dest_plats
->aggs
)
1984 if (dest_plats
->aggs_by_ref
!= new_aggs_by_ref
)
1986 set_agg_lats_to_bottom (dest_plats
);
1991 dest_plats
->aggs_by_ref
= new_aggs_by_ref
;
1995 /* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
1996 already existing lattice for the given OFFSET and SIZE, marking all skipped
1997 lattices as containing variable and checking for overlaps. If there is no
1998 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
1999 it with offset, size and contains_variable to PRE_EXISTING, and return true,
2000 unless there are too many already. If there are two many, return false. If
2001 there are overlaps turn whole DEST_PLATS to bottom and return false. If any
2002 skipped lattices were newly marked as containing variable, set *CHANGE to
2006 merge_agg_lats_step (struct ipcp_param_lattices
*dest_plats
,
2007 HOST_WIDE_INT offset
, HOST_WIDE_INT val_size
,
2008 struct ipcp_agg_lattice
***aglat
,
2009 bool pre_existing
, bool *change
)
2011 gcc_checking_assert (offset
>= 0);
2013 while (**aglat
&& (**aglat
)->offset
< offset
)
2015 if ((**aglat
)->offset
+ (**aglat
)->size
> offset
)
2017 set_agg_lats_to_bottom (dest_plats
);
2020 *change
|= (**aglat
)->set_contains_variable ();
2021 *aglat
= &(**aglat
)->next
;
2024 if (**aglat
&& (**aglat
)->offset
== offset
)
2026 if ((**aglat
)->size
!= val_size
2028 && (**aglat
)->next
->offset
< offset
+ val_size
))
2030 set_agg_lats_to_bottom (dest_plats
);
2033 gcc_checking_assert (!(**aglat
)->next
2034 || (**aglat
)->next
->offset
>= offset
+ val_size
);
2039 struct ipcp_agg_lattice
*new_al
;
2041 if (**aglat
&& (**aglat
)->offset
< offset
+ val_size
)
2043 set_agg_lats_to_bottom (dest_plats
);
2046 if (dest_plats
->aggs_count
== PARAM_VALUE (PARAM_IPA_MAX_AGG_ITEMS
))
2048 dest_plats
->aggs_count
++;
2049 new_al
= ipcp_agg_lattice_pool
.allocate ();
2050 memset (new_al
, 0, sizeof (*new_al
));
2052 new_al
->offset
= offset
;
2053 new_al
->size
= val_size
;
2054 new_al
->contains_variable
= pre_existing
;
2056 new_al
->next
= **aglat
;
2062 /* Set all AGLAT and all other aggregate lattices reachable by next pointers as
2063 containing an unknown value. */
2066 set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice
*aglat
)
2071 ret
|= aglat
->set_contains_variable ();
2072 aglat
= aglat
->next
;
2077 /* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
2078 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source
2079 parameter used for lattice value sources. Return true if DEST_PLATS changed
2083 merge_aggregate_lattices (struct cgraph_edge
*cs
,
2084 struct ipcp_param_lattices
*dest_plats
,
2085 struct ipcp_param_lattices
*src_plats
,
2086 int src_idx
, HOST_WIDE_INT offset_delta
)
2088 bool pre_existing
= dest_plats
->aggs
!= NULL
;
2089 struct ipcp_agg_lattice
**dst_aglat
;
2092 if (set_check_aggs_by_ref (dest_plats
, src_plats
->aggs_by_ref
))
2094 if (src_plats
->aggs_bottom
)
2095 return set_agg_lats_contain_variable (dest_plats
);
2096 if (src_plats
->aggs_contain_variable
)
2097 ret
|= set_agg_lats_contain_variable (dest_plats
);
2098 dst_aglat
= &dest_plats
->aggs
;
2100 for (struct ipcp_agg_lattice
*src_aglat
= src_plats
->aggs
;
2102 src_aglat
= src_aglat
->next
)
2104 HOST_WIDE_INT new_offset
= src_aglat
->offset
- offset_delta
;
2108 if (merge_agg_lats_step (dest_plats
, new_offset
, src_aglat
->size
,
2109 &dst_aglat
, pre_existing
, &ret
))
2111 struct ipcp_agg_lattice
*new_al
= *dst_aglat
;
2113 dst_aglat
= &(*dst_aglat
)->next
;
2114 if (src_aglat
->bottom
)
2116 ret
|= new_al
->set_contains_variable ();
2119 if (src_aglat
->contains_variable
)
2120 ret
|= new_al
->set_contains_variable ();
2121 for (ipcp_value
<tree
> *val
= src_aglat
->values
;
2124 ret
|= new_al
->add_value (val
->value
, cs
, val
, src_idx
,
2127 else if (dest_plats
->aggs_bottom
)
2130 ret
|= set_chain_of_aglats_contains_variable (*dst_aglat
);
2134 /* Determine whether there is anything to propagate FROM SRC_PLATS through a
2135 pass-through JFUNC and if so, whether it has conform and conforms to the
2136 rules about propagating values passed by reference. */
2139 agg_pass_through_permissible_p (struct ipcp_param_lattices
*src_plats
,
2140 struct ipa_jump_func
*jfunc
)
2142 return src_plats
->aggs
2143 && (!src_plats
->aggs_by_ref
2144 || ipa_get_jf_pass_through_agg_preserved (jfunc
));
2147 /* Propagate scalar values across jump function JFUNC that is associated with
2148 edge CS and put the values into DEST_LAT. */
2151 propagate_aggs_across_jump_function (struct cgraph_edge
*cs
,
2152 struct ipa_jump_func
*jfunc
,
2153 struct ipcp_param_lattices
*dest_plats
)
2157 if (dest_plats
->aggs_bottom
)
2160 if (jfunc
->type
== IPA_JF_PASS_THROUGH
2161 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
2163 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2164 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
2165 struct ipcp_param_lattices
*src_plats
;
2167 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2168 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
2170 /* Currently we do not produce clobber aggregate jump
2171 functions, replace with merging when we do. */
2172 gcc_assert (!jfunc
->agg
.items
);
2173 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
,
2177 ret
|= set_agg_lats_contain_variable (dest_plats
);
2179 else if (jfunc
->type
== IPA_JF_ANCESTOR
2180 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
2182 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2183 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
2184 struct ipcp_param_lattices
*src_plats
;
2186 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2187 if (src_plats
->aggs
&& src_plats
->aggs_by_ref
)
2189 /* Currently we do not produce clobber aggregate jump
2190 functions, replace with merging when we do. */
2191 gcc_assert (!jfunc
->agg
.items
);
2192 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
, src_idx
,
2193 ipa_get_jf_ancestor_offset (jfunc
));
2195 else if (!src_plats
->aggs_by_ref
)
2196 ret
|= set_agg_lats_to_bottom (dest_plats
);
2198 ret
|= set_agg_lats_contain_variable (dest_plats
);
2200 else if (jfunc
->agg
.items
)
2202 bool pre_existing
= dest_plats
->aggs
!= NULL
;
2203 struct ipcp_agg_lattice
**aglat
= &dest_plats
->aggs
;
2204 struct ipa_agg_jf_item
*item
;
2207 if (set_check_aggs_by_ref (dest_plats
, jfunc
->agg
.by_ref
))
2210 FOR_EACH_VEC_ELT (*jfunc
->agg
.items
, i
, item
)
2212 HOST_WIDE_INT val_size
;
2214 if (item
->offset
< 0)
2216 gcc_checking_assert (is_gimple_ip_invariant (item
->value
));
2217 val_size
= tree_to_uhwi (TYPE_SIZE (TREE_TYPE (item
->value
)));
2219 if (merge_agg_lats_step (dest_plats
, item
->offset
, val_size
,
2220 &aglat
, pre_existing
, &ret
))
2222 ret
|= (*aglat
)->add_value (item
->value
, cs
, NULL
, 0, 0);
2223 aglat
= &(*aglat
)->next
;
2225 else if (dest_plats
->aggs_bottom
)
2229 ret
|= set_chain_of_aglats_contains_variable (*aglat
);
2232 ret
|= set_agg_lats_contain_variable (dest_plats
);
2237 /* Return true if on the way cfrom CS->caller to the final (non-alias and
2238 non-thunk) destination, the call passes through a thunk. */
2241 call_passes_through_thunk_p (cgraph_edge
*cs
)
2243 cgraph_node
*alias_or_thunk
= cs
->callee
;
2244 while (alias_or_thunk
->alias
)
2245 alias_or_thunk
= alias_or_thunk
->get_alias_target ();
2246 return alias_or_thunk
->thunk
.thunk_p
;
2249 /* Propagate constants from the caller to the callee of CS. INFO describes the
2253 propagate_constants_across_call (struct cgraph_edge
*cs
)
2255 struct ipa_node_params
*callee_info
;
2256 enum availability availability
;
2257 cgraph_node
*callee
;
2258 struct ipa_edge_args
*args
;
2260 int i
, args_count
, parms_count
;
2262 callee
= cs
->callee
->function_symbol (&availability
);
2263 if (!callee
->definition
)
2265 gcc_checking_assert (callee
->has_gimple_body_p ());
2266 callee_info
= IPA_NODE_REF (callee
);
2268 args
= IPA_EDGE_REF (cs
);
2269 args_count
= ipa_get_cs_argument_count (args
);
2270 parms_count
= ipa_get_param_count (callee_info
);
2271 if (parms_count
== 0)
2274 /* If this call goes through a thunk we must not propagate to the first (0th)
2275 parameter. However, we might need to uncover a thunk from below a series
2276 of aliases first. */
2277 if (call_passes_through_thunk_p (cs
))
2279 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
2286 for (; (i
< args_count
) && (i
< parms_count
); i
++)
2288 struct ipa_jump_func
*jump_func
= ipa_get_ith_jump_func (args
, i
);
2289 struct ipcp_param_lattices
*dest_plats
;
2290 tree param_type
= ipa_get_type (callee_info
, i
);
2292 dest_plats
= ipa_get_parm_lattices (callee_info
, i
);
2293 if (availability
== AVAIL_INTERPOSABLE
)
2294 ret
|= set_all_contains_variable (dest_plats
);
2297 ret
|= propagate_scalar_across_jump_function (cs
, jump_func
,
2298 &dest_plats
->itself
,
2300 ret
|= propagate_context_across_jump_function (cs
, jump_func
, i
,
2301 &dest_plats
->ctxlat
);
2303 |= propagate_bits_across_jump_function (cs
, i
, jump_func
,
2304 &dest_plats
->bits_lattice
);
2305 ret
|= propagate_aggs_across_jump_function (cs
, jump_func
,
2307 if (opt_for_fn (callee
->decl
, flag_ipa_vrp
))
2308 ret
|= propagate_vr_across_jump_function (cs
, jump_func
,
2309 dest_plats
, param_type
);
2311 ret
|= dest_plats
->m_value_range
.set_to_bottom ();
2314 for (; i
< parms_count
; i
++)
2315 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
, i
));
2320 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
2321 KNOWN_CONTEXTS, KNOWN_AGGS or AGG_REPS return the destination. The latter
2322 three can be NULL. If AGG_REPS is not NULL, KNOWN_AGGS is ignored. */
2325 ipa_get_indirect_edge_target_1 (struct cgraph_edge
*ie
,
2326 vec
<tree
> known_csts
,
2327 vec
<ipa_polymorphic_call_context
> known_contexts
,
2328 vec
<ipa_agg_jump_function_p
> known_aggs
,
2329 struct ipa_agg_replacement_value
*agg_reps
,
2332 int param_index
= ie
->indirect_info
->param_index
;
2333 HOST_WIDE_INT anc_offset
;
2337 *speculative
= false;
2339 if (param_index
== -1
2340 || known_csts
.length () <= (unsigned int) param_index
)
2343 if (!ie
->indirect_info
->polymorphic
)
2347 if (ie
->indirect_info
->agg_contents
)
2350 if (agg_reps
&& ie
->indirect_info
->guaranteed_unmodified
)
2354 if (agg_reps
->index
== param_index
2355 && agg_reps
->offset
== ie
->indirect_info
->offset
2356 && agg_reps
->by_ref
== ie
->indirect_info
->by_ref
)
2358 t
= agg_reps
->value
;
2361 agg_reps
= agg_reps
->next
;
2366 struct ipa_agg_jump_function
*agg
;
2367 if (known_aggs
.length () > (unsigned int) param_index
)
2368 agg
= known_aggs
[param_index
];
2371 bool from_global_constant
;
2372 t
= ipa_find_agg_cst_for_param (agg
, known_csts
[param_index
],
2373 ie
->indirect_info
->offset
,
2374 ie
->indirect_info
->by_ref
,
2375 &from_global_constant
);
2377 && !from_global_constant
2378 && !ie
->indirect_info
->guaranteed_unmodified
)
2383 t
= known_csts
[param_index
];
2386 && TREE_CODE (t
) == ADDR_EXPR
2387 && TREE_CODE (TREE_OPERAND (t
, 0)) == FUNCTION_DECL
)
2388 return TREE_OPERAND (t
, 0);
2393 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize
))
2396 gcc_assert (!ie
->indirect_info
->agg_contents
);
2397 anc_offset
= ie
->indirect_info
->offset
;
2401 /* Try to work out value of virtual table pointer value in replacemnets. */
2402 if (!t
&& agg_reps
&& !ie
->indirect_info
->by_ref
)
2406 if (agg_reps
->index
== param_index
2407 && agg_reps
->offset
== ie
->indirect_info
->offset
2408 && agg_reps
->by_ref
)
2410 t
= agg_reps
->value
;
2413 agg_reps
= agg_reps
->next
;
2417 /* Try to work out value of virtual table pointer value in known
2418 aggregate values. */
2419 if (!t
&& known_aggs
.length () > (unsigned int) param_index
2420 && !ie
->indirect_info
->by_ref
)
2422 struct ipa_agg_jump_function
*agg
;
2423 agg
= known_aggs
[param_index
];
2424 t
= ipa_find_agg_cst_for_param (agg
, known_csts
[param_index
],
2425 ie
->indirect_info
->offset
, true);
2428 /* If we found the virtual table pointer, lookup the target. */
2432 unsigned HOST_WIDE_INT offset
;
2433 if (vtable_pointer_value_to_vtable (t
, &vtable
, &offset
))
2436 target
= gimple_get_virt_method_for_vtable (ie
->indirect_info
->otr_token
,
2437 vtable
, offset
, &can_refer
);
2441 || (TREE_CODE (TREE_TYPE (target
)) == FUNCTION_TYPE
2442 && DECL_FUNCTION_CODE (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 struct 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_create (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
);
2612 if (hints
& INLINE_HINT_array_index
)
2613 result
+= PARAM_VALUE (PARAM_IPA_CP_ARRAY_INDEX_HINT_BONUS
);
2617 /* If there is a reason to penalize the function described by INFO in the
2618 cloning goodness evaluation, do so. */
2620 static inline int64_t
2621 incorporate_penalties (ipa_node_params
*info
, int64_t evaluation
)
2623 if (info
->node_within_scc
)
2624 evaluation
= (evaluation
2625 * (100 - PARAM_VALUE (PARAM_IPA_CP_RECURSION_PENALTY
))) / 100;
2627 if (info
->node_calling_single_call
)
2628 evaluation
= (evaluation
2629 * (100 - PARAM_VALUE (PARAM_IPA_CP_SINGLE_CALL_PENALTY
)))
2635 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
2636 and SIZE_COST and with the sum of frequencies of incoming edges to the
2637 potential new clone in FREQUENCIES. */
2640 good_cloning_opportunity_p (struct cgraph_node
*node
, int time_benefit
,
2641 int freq_sum
, profile_count count_sum
, int size_cost
)
2643 if (time_benefit
== 0
2644 || !opt_for_fn (node
->decl
, flag_ipa_cp_clone
)
2645 || node
->optimize_for_size_p ())
2648 gcc_assert (size_cost
> 0);
2650 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2651 if (max_count
> profile_count::zero ())
2653 int factor
= RDIV (count_sum
.probability_in
2654 (max_count
).to_reg_br_prob_base ()
2655 * 1000, REG_BR_PROB_BASE
);
2656 int64_t evaluation
= (((int64_t) time_benefit
* factor
)
2658 evaluation
= incorporate_penalties (info
, evaluation
);
2660 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2662 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
2663 "size: %i, count_sum: ", time_benefit
, size_cost
);
2664 count_sum
.dump (dump_file
);
2665 fprintf (dump_file
, "%s%s) -> evaluation: " "%" PRId64
2666 ", threshold: %i\n",
2667 info
->node_within_scc
? ", scc" : "",
2668 info
->node_calling_single_call
? ", single_call" : "",
2669 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
2672 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
2676 int64_t evaluation
= (((int64_t) time_benefit
* freq_sum
)
2678 evaluation
= incorporate_penalties (info
, evaluation
);
2680 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2681 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
2682 "size: %i, freq_sum: %i%s%s) -> evaluation: "
2683 "%" PRId64
", threshold: %i\n",
2684 time_benefit
, size_cost
, freq_sum
,
2685 info
->node_within_scc
? ", scc" : "",
2686 info
->node_calling_single_call
? ", single_call" : "",
2687 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
2689 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
2693 /* Return all context independent values from aggregate lattices in PLATS in a
2694 vector. Return NULL if there are none. */
2696 static vec
<ipa_agg_jf_item
, va_gc
> *
2697 context_independent_aggregate_values (struct ipcp_param_lattices
*plats
)
2699 vec
<ipa_agg_jf_item
, va_gc
> *res
= NULL
;
2701 if (plats
->aggs_bottom
2702 || plats
->aggs_contain_variable
2703 || plats
->aggs_count
== 0)
2706 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
;
2708 aglat
= aglat
->next
)
2709 if (aglat
->is_single_const ())
2711 struct ipa_agg_jf_item item
;
2712 item
.offset
= aglat
->offset
;
2713 item
.value
= aglat
->values
->value
;
2714 vec_safe_push (res
, item
);
2719 /* Allocate KNOWN_CSTS, KNOWN_CONTEXTS and, if non-NULL, KNOWN_AGGS and
2720 populate them with values of parameters that are known independent of the
2721 context. INFO describes the function. If REMOVABLE_PARAMS_COST is
2722 non-NULL, the movement cost of all removable parameters will be stored in
2726 gather_context_independent_values (struct ipa_node_params
*info
,
2727 vec
<tree
> *known_csts
,
2728 vec
<ipa_polymorphic_call_context
>
2730 vec
<ipa_agg_jump_function
> *known_aggs
,
2731 int *removable_params_cost
)
2733 int i
, count
= ipa_get_param_count (info
);
2736 known_csts
->create (0);
2737 known_contexts
->create (0);
2738 known_csts
->safe_grow_cleared (count
);
2739 known_contexts
->safe_grow_cleared (count
);
2742 known_aggs
->create (0);
2743 known_aggs
->safe_grow_cleared (count
);
2746 if (removable_params_cost
)
2747 *removable_params_cost
= 0;
2749 for (i
= 0; i
< count
; i
++)
2751 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2752 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
2754 if (lat
->is_single_const ())
2756 ipcp_value
<tree
> *val
= lat
->values
;
2757 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
2758 (*known_csts
)[i
] = val
->value
;
2759 if (removable_params_cost
)
2760 *removable_params_cost
2761 += estimate_move_cost (TREE_TYPE (val
->value
), false);
2764 else if (removable_params_cost
2765 && !ipa_is_param_used (info
, i
))
2766 *removable_params_cost
2767 += ipa_get_param_move_cost (info
, i
);
2769 if (!ipa_is_param_used (info
, i
))
2772 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
2773 /* Do not account known context as reason for cloning. We can see
2774 if it permits devirtualization. */
2775 if (ctxlat
->is_single_const ())
2776 (*known_contexts
)[i
] = ctxlat
->values
->value
;
2780 vec
<ipa_agg_jf_item
, va_gc
> *agg_items
;
2781 struct ipa_agg_jump_function
*ajf
;
2783 agg_items
= context_independent_aggregate_values (plats
);
2784 ajf
= &(*known_aggs
)[i
];
2785 ajf
->items
= agg_items
;
2786 ajf
->by_ref
= plats
->aggs_by_ref
;
2787 ret
|= agg_items
!= NULL
;
2794 /* The current interface in ipa-inline-analysis requires a pointer vector.
2797 FIXME: That interface should be re-worked, this is slightly silly. Still,
2798 I'd like to discuss how to change it first and this demonstrates the
2801 static vec
<ipa_agg_jump_function_p
>
2802 agg_jmp_p_vec_for_t_vec (vec
<ipa_agg_jump_function
> known_aggs
)
2804 vec
<ipa_agg_jump_function_p
> ret
;
2805 struct ipa_agg_jump_function
*ajf
;
2808 ret
.create (known_aggs
.length ());
2809 FOR_EACH_VEC_ELT (known_aggs
, i
, ajf
)
2810 ret
.quick_push (ajf
);
2814 /* Perform time and size measurement of NODE with the context given in
2815 KNOWN_CSTS, KNOWN_CONTEXTS and KNOWN_AGGS, calculate the benefit and cost
2816 given BASE_TIME of the node without specialization, REMOVABLE_PARAMS_COST of
2817 all context-independent removable parameters and EST_MOVE_COST of estimated
2818 movement of the considered parameter and store it into VAL. */
2821 perform_estimation_of_a_value (cgraph_node
*node
, vec
<tree
> known_csts
,
2822 vec
<ipa_polymorphic_call_context
> known_contexts
,
2823 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
,
2824 int removable_params_cost
,
2825 int est_move_cost
, ipcp_value_base
*val
)
2827 int size
, time_benefit
;
2828 sreal time
, base_time
;
2831 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
2832 known_aggs_ptrs
, &size
, &time
,
2833 &base_time
, &hints
);
2835 if (base_time
> 65535)
2837 time_benefit
= base_time
.to_int ()
2838 + devirtualization_time_bonus (node
, known_csts
, known_contexts
,
2840 + hint_time_bonus (hints
)
2841 + removable_params_cost
+ est_move_cost
;
2843 gcc_checking_assert (size
>=0);
2844 /* The inliner-heuristics based estimates may think that in certain
2845 contexts some functions do not have any size at all but we want
2846 all specializations to have at least a tiny cost, not least not to
2851 val
->local_time_benefit
= time_benefit
;
2852 val
->local_size_cost
= size
;
2855 /* Iterate over known values of parameters of NODE and estimate the local
2856 effects in terms of time and size they have. */
2859 estimate_local_effects (struct cgraph_node
*node
)
2861 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2862 int i
, count
= ipa_get_param_count (info
);
2863 vec
<tree
> known_csts
;
2864 vec
<ipa_polymorphic_call_context
> known_contexts
;
2865 vec
<ipa_agg_jump_function
> known_aggs
;
2866 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
;
2868 int removable_params_cost
;
2870 if (!count
|| !ipcp_versionable_function_p (node
))
2873 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2874 fprintf (dump_file
, "\nEstimating effects for %s.\n", node
->dump_name ());
2876 always_const
= gather_context_independent_values (info
, &known_csts
,
2877 &known_contexts
, &known_aggs
,
2878 &removable_params_cost
);
2879 known_aggs_ptrs
= agg_jmp_p_vec_for_t_vec (known_aggs
);
2880 int devirt_bonus
= devirtualization_time_bonus (node
, known_csts
,
2881 known_contexts
, known_aggs_ptrs
);
2882 if (always_const
|| devirt_bonus
2883 || (removable_params_cost
&& node
->local
.can_change_signature
))
2885 struct caller_statistics stats
;
2887 sreal time
, base_time
;
2890 init_caller_stats (&stats
);
2891 node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
2893 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
2894 known_aggs_ptrs
, &size
, &time
,
2895 &base_time
, &hints
);
2896 time
-= devirt_bonus
;
2897 time
-= hint_time_bonus (hints
);
2898 time
-= removable_params_cost
;
2899 size
-= stats
.n_calls
* removable_params_cost
;
2902 fprintf (dump_file
, " - context independent values, size: %i, "
2903 "time_benefit: %f\n", size
, (base_time
- time
).to_double ());
2905 if (size
<= 0 || node
->local
.local
)
2907 info
->do_clone_for_all_contexts
= true;
2910 fprintf (dump_file
, " Decided to specialize for all "
2911 "known contexts, code not going to grow.\n");
2913 else if (good_cloning_opportunity_p (node
,
2914 MAX ((base_time
- time
).to_int (),
2916 stats
.freq_sum
, stats
.count_sum
,
2919 if (size
+ overall_size
<= max_new_size
)
2921 info
->do_clone_for_all_contexts
= true;
2922 overall_size
+= size
;
2925 fprintf (dump_file
, " Decided to specialize for all "
2926 "known contexts, growth deemed beneficial.\n");
2928 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2929 fprintf (dump_file
, " Not cloning for all contexts because "
2930 "max_new_size would be reached with %li.\n",
2931 size
+ overall_size
);
2933 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2934 fprintf (dump_file
, " Not cloning for all contexts because "
2935 "!good_cloning_opportunity_p.\n");
2939 for (i
= 0; i
< count
; i
++)
2941 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2942 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
2943 ipcp_value
<tree
> *val
;
2950 for (val
= lat
->values
; val
; val
= val
->next
)
2952 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
2953 known_csts
[i
] = val
->value
;
2955 int emc
= estimate_move_cost (TREE_TYPE (val
->value
), true);
2956 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
2958 removable_params_cost
, emc
, val
);
2960 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2962 fprintf (dump_file
, " - estimates for value ");
2963 print_ipcp_constant_value (dump_file
, val
->value
);
2964 fprintf (dump_file
, " for ");
2965 ipa_dump_param (dump_file
, info
, i
);
2966 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
2967 val
->local_time_benefit
, val
->local_size_cost
);
2970 known_csts
[i
] = NULL_TREE
;
2973 for (i
= 0; i
< count
; i
++)
2975 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2977 if (!plats
->virt_call
)
2980 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
2981 ipcp_value
<ipa_polymorphic_call_context
> *val
;
2985 || !known_contexts
[i
].useless_p ())
2988 for (val
= ctxlat
->values
; val
; val
= val
->next
)
2990 known_contexts
[i
] = val
->value
;
2991 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
2993 removable_params_cost
, 0, val
);
2995 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2997 fprintf (dump_file
, " - estimates for polymorphic context ");
2998 print_ipcp_constant_value (dump_file
, val
->value
);
2999 fprintf (dump_file
, " for ");
3000 ipa_dump_param (dump_file
, info
, i
);
3001 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
3002 val
->local_time_benefit
, val
->local_size_cost
);
3005 known_contexts
[i
] = ipa_polymorphic_call_context ();
3008 for (i
= 0; i
< count
; i
++)
3010 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3011 struct ipa_agg_jump_function
*ajf
;
3012 struct ipcp_agg_lattice
*aglat
;
3014 if (plats
->aggs_bottom
|| !plats
->aggs
)
3017 ajf
= &known_aggs
[i
];
3018 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3020 ipcp_value
<tree
> *val
;
3021 if (aglat
->bottom
|| !aglat
->values
3022 /* If the following is true, the one value is in known_aggs. */
3023 || (!plats
->aggs_contain_variable
3024 && aglat
->is_single_const ()))
3027 for (val
= aglat
->values
; val
; val
= val
->next
)
3029 struct ipa_agg_jf_item item
;
3031 item
.offset
= aglat
->offset
;
3032 item
.value
= val
->value
;
3033 vec_safe_push (ajf
->items
, item
);
3035 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
3037 removable_params_cost
, 0, val
);
3039 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3041 fprintf (dump_file
, " - estimates for value ");
3042 print_ipcp_constant_value (dump_file
, val
->value
);
3043 fprintf (dump_file
, " for ");
3044 ipa_dump_param (dump_file
, info
, i
);
3045 fprintf (dump_file
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
3046 "]: time_benefit: %i, size: %i\n",
3047 plats
->aggs_by_ref
? "ref " : "",
3049 val
->local_time_benefit
, val
->local_size_cost
);
3057 for (i
= 0; i
< count
; i
++)
3058 vec_free (known_aggs
[i
].items
);
3060 known_csts
.release ();
3061 known_contexts
.release ();
3062 known_aggs
.release ();
3063 known_aggs_ptrs
.release ();
3067 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
3068 topological sort of values. */
3070 template <typename valtype
>
3072 value_topo_info
<valtype
>::add_val (ipcp_value
<valtype
> *cur_val
)
3074 ipcp_value_source
<valtype
> *src
;
3080 cur_val
->dfs
= dfs_counter
;
3081 cur_val
->low_link
= dfs_counter
;
3083 cur_val
->topo_next
= stack
;
3085 cur_val
->on_stack
= true;
3087 for (src
= cur_val
->sources
; src
; src
= src
->next
)
3090 if (src
->val
->dfs
== 0)
3093 if (src
->val
->low_link
< cur_val
->low_link
)
3094 cur_val
->low_link
= src
->val
->low_link
;
3096 else if (src
->val
->on_stack
3097 && src
->val
->dfs
< cur_val
->low_link
)
3098 cur_val
->low_link
= src
->val
->dfs
;
3101 if (cur_val
->dfs
== cur_val
->low_link
)
3103 ipcp_value
<valtype
> *v
, *scc_list
= NULL
;
3108 stack
= v
->topo_next
;
3109 v
->on_stack
= false;
3111 v
->scc_next
= scc_list
;
3114 while (v
!= cur_val
);
3116 cur_val
->topo_next
= values_topo
;
3117 values_topo
= cur_val
;
3121 /* Add all values in lattices associated with NODE to the topological sort if
3122 they are not there yet. */
3125 add_all_node_vals_to_toposort (cgraph_node
*node
, ipa_topo_info
*topo
)
3127 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3128 int i
, count
= ipa_get_param_count (info
);
3130 for (i
= 0; i
< count
; i
++)
3132 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3133 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
3134 struct ipcp_agg_lattice
*aglat
;
3138 ipcp_value
<tree
> *val
;
3139 for (val
= lat
->values
; val
; val
= val
->next
)
3140 topo
->constants
.add_val (val
);
3143 if (!plats
->aggs_bottom
)
3144 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3147 ipcp_value
<tree
> *val
;
3148 for (val
= aglat
->values
; val
; val
= val
->next
)
3149 topo
->constants
.add_val (val
);
3152 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
3153 if (!ctxlat
->bottom
)
3155 ipcp_value
<ipa_polymorphic_call_context
> *ctxval
;
3156 for (ctxval
= ctxlat
->values
; ctxval
; ctxval
= ctxval
->next
)
3157 topo
->contexts
.add_val (ctxval
);
3162 /* One pass of constants propagation along the call graph edges, from callers
3163 to callees (requires topological ordering in TOPO), iterate over strongly
3164 connected components. */
3167 propagate_constants_topo (struct ipa_topo_info
*topo
)
3171 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
3174 struct cgraph_node
*v
, *node
= topo
->order
[i
];
3175 vec
<cgraph_node
*> cycle_nodes
= ipa_get_nodes_in_cycle (node
);
3177 /* First, iteratively propagate within the strongly connected component
3178 until all lattices stabilize. */
3179 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
3180 if (v
->has_gimple_body_p ())
3181 push_node_to_stack (topo
, v
);
3183 v
= pop_node_from_stack (topo
);
3186 struct cgraph_edge
*cs
;
3188 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3189 if (ipa_edge_within_scc (cs
))
3191 IPA_NODE_REF (v
)->node_within_scc
= true;
3192 if (propagate_constants_across_call (cs
))
3193 push_node_to_stack (topo
, cs
->callee
->function_symbol ());
3195 v
= pop_node_from_stack (topo
);
3198 /* Afterwards, propagate along edges leading out of the SCC, calculates
3199 the local effects of the discovered constants and all valid values to
3200 their topological sort. */
3201 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
3202 if (v
->has_gimple_body_p ())
3204 struct cgraph_edge
*cs
;
3206 estimate_local_effects (v
);
3207 add_all_node_vals_to_toposort (v
, topo
);
3208 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3209 if (!ipa_edge_within_scc (cs
))
3210 propagate_constants_across_call (cs
);
3212 cycle_nodes
.release ();
3217 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
3218 the bigger one if otherwise. */
3221 safe_add (int a
, int b
)
3223 if (a
> INT_MAX
/2 || b
> INT_MAX
/2)
3224 return a
> b
? a
: b
;
3230 /* Propagate the estimated effects of individual values along the topological
3231 from the dependent values to those they depend on. */
3233 template <typename valtype
>
3235 value_topo_info
<valtype
>::propagate_effects ()
3237 ipcp_value
<valtype
> *base
;
3239 for (base
= values_topo
; base
; base
= base
->topo_next
)
3241 ipcp_value_source
<valtype
> *src
;
3242 ipcp_value
<valtype
> *val
;
3243 int time
= 0, size
= 0;
3245 for (val
= base
; val
; val
= val
->scc_next
)
3247 time
= safe_add (time
,
3248 val
->local_time_benefit
+ val
->prop_time_benefit
);
3249 size
= safe_add (size
, val
->local_size_cost
+ val
->prop_size_cost
);
3252 for (val
= base
; val
; val
= val
->scc_next
)
3253 for (src
= val
->sources
; src
; src
= src
->next
)
3255 && src
->cs
->maybe_hot_p ())
3257 src
->val
->prop_time_benefit
= safe_add (time
,
3258 src
->val
->prop_time_benefit
);
3259 src
->val
->prop_size_cost
= safe_add (size
,
3260 src
->val
->prop_size_cost
);
3266 /* Propagate constants, polymorphic contexts and their effects from the
3267 summaries interprocedurally. */
3270 ipcp_propagate_stage (struct ipa_topo_info
*topo
)
3272 struct cgraph_node
*node
;
3275 fprintf (dump_file
, "\n Propagating constants:\n\n");
3277 max_count
= profile_count::uninitialized ();
3279 FOR_EACH_DEFINED_FUNCTION (node
)
3281 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3283 determine_versionability (node
, info
);
3284 if (node
->has_gimple_body_p ())
3286 info
->lattices
= XCNEWVEC (struct ipcp_param_lattices
,
3287 ipa_get_param_count (info
));
3288 initialize_node_lattices (node
);
3290 if (node
->definition
&& !node
->alias
)
3291 overall_size
+= ipa_fn_summaries
->get_create (node
)->self_size
;
3292 max_count
= max_count
.max (node
->count
.ipa ());
3295 max_new_size
= overall_size
;
3296 if (max_new_size
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
3297 max_new_size
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
3298 max_new_size
+= max_new_size
* PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH
) / 100 + 1;
3301 fprintf (dump_file
, "\noverall_size: %li, max_new_size: %li\n",
3302 overall_size
, max_new_size
);
3304 propagate_constants_topo (topo
);
3306 ipcp_verify_propagated_values ();
3307 topo
->constants
.propagate_effects ();
3308 topo
->contexts
.propagate_effects ();
3312 fprintf (dump_file
, "\nIPA lattices after all propagation:\n");
3313 print_all_lattices (dump_file
, (dump_flags
& TDF_DETAILS
), true);
3317 /* Discover newly direct outgoing edges from NODE which is a new clone with
3318 known KNOWN_CSTS and make them direct. */
3321 ipcp_discover_new_direct_edges (struct cgraph_node
*node
,
3322 vec
<tree
> known_csts
,
3323 vec
<ipa_polymorphic_call_context
>
3325 struct ipa_agg_replacement_value
*aggvals
)
3327 struct cgraph_edge
*ie
, *next_ie
;
3330 for (ie
= node
->indirect_calls
; ie
; ie
= next_ie
)
3335 next_ie
= ie
->next_callee
;
3336 target
= ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
3337 vNULL
, aggvals
, &speculative
);
3340 bool agg_contents
= ie
->indirect_info
->agg_contents
;
3341 bool polymorphic
= ie
->indirect_info
->polymorphic
;
3342 int param_index
= ie
->indirect_info
->param_index
;
3343 struct cgraph_edge
*cs
= ipa_make_edge_direct_to_target (ie
, target
,
3347 if (cs
&& !agg_contents
&& !polymorphic
)
3349 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3350 int c
= ipa_get_controlled_uses (info
, param_index
);
3351 if (c
!= IPA_UNDESCRIBED_USE
)
3353 struct ipa_ref
*to_del
;
3356 ipa_set_controlled_uses (info
, param_index
, c
);
3357 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3358 fprintf (dump_file
, " controlled uses count of param "
3359 "%i bumped down to %i\n", param_index
, c
);
3361 && (to_del
= node
->find_reference (cs
->callee
, NULL
, 0)))
3363 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3364 fprintf (dump_file
, " and even removing its "
3365 "cloning-created reference\n");
3366 to_del
->remove_reference ();
3372 /* Turning calls to direct calls will improve overall summary. */
3374 ipa_update_overall_fn_summary (node
);
3377 class edge_clone_summary
;
3378 static call_summary
<edge_clone_summary
*> *edge_clone_summaries
= NULL
;
3380 /* Edge clone summary. */
3382 struct edge_clone_summary
3384 /* Default constructor. */
3385 edge_clone_summary (): prev_clone (NULL
), next_clone (NULL
) {}
3387 /* Default destructor. */
3388 ~edge_clone_summary ()
3391 edge_clone_summaries
->get (prev_clone
)->next_clone
= next_clone
;
3393 edge_clone_summaries
->get (next_clone
)->prev_clone
= prev_clone
;
3396 cgraph_edge
*prev_clone
;
3397 cgraph_edge
*next_clone
;
3400 class edge_clone_summary_t
:
3401 public call_summary
<edge_clone_summary
*>
3404 edge_clone_summary_t (symbol_table
*symtab
):
3405 call_summary
<edge_clone_summary
*> (symtab
)
3407 m_initialize_when_cloning
= true;
3410 virtual void duplicate (cgraph_edge
*src_edge
, cgraph_edge
*dst_edge
,
3411 edge_clone_summary
*src_data
,
3412 edge_clone_summary
*dst_data
);
3415 /* Edge duplication hook. */
3418 edge_clone_summary_t::duplicate (cgraph_edge
*src_edge
, cgraph_edge
*dst_edge
,
3419 edge_clone_summary
*src_data
,
3420 edge_clone_summary
*dst_data
)
3422 if (src_data
->next_clone
)
3423 edge_clone_summaries
->get (src_data
->next_clone
)->prev_clone
= dst_edge
;
3424 dst_data
->prev_clone
= src_edge
;
3425 dst_data
->next_clone
= src_data
->next_clone
;
3426 src_data
->next_clone
= dst_edge
;
3429 /* See if NODE is a clone with a known aggregate value at a given OFFSET of a
3430 parameter with the given INDEX. */
3433 get_clone_agg_value (struct cgraph_node
*node
, HOST_WIDE_INT offset
,
3436 struct ipa_agg_replacement_value
*aggval
;
3438 aggval
= ipa_get_agg_replacements_for_node (node
);
3441 if (aggval
->offset
== offset
3442 && aggval
->index
== index
)
3443 return aggval
->value
;
3444 aggval
= aggval
->next
;
3449 /* Return true is NODE is DEST or its clone for all contexts. */
3452 same_node_or_its_all_contexts_clone_p (cgraph_node
*node
, cgraph_node
*dest
)
3457 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3458 return info
->is_all_contexts_clone
&& info
->ipcp_orig_node
== dest
;
3461 /* Return true if edge CS does bring about the value described by SRC to
3462 DEST_VAL of node DEST or its clone for all contexts. */
3465 cgraph_edge_brings_value_p (cgraph_edge
*cs
, ipcp_value_source
<tree
> *src
,
3466 cgraph_node
*dest
, ipcp_value
<tree
> *dest_val
)
3468 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3469 enum availability availability
;
3470 cgraph_node
*real_dest
= cs
->callee
->function_symbol (&availability
);
3472 if (!same_node_or_its_all_contexts_clone_p (real_dest
, dest
)
3473 || availability
<= AVAIL_INTERPOSABLE
3474 || caller_info
->node_dead
)
3480 if (caller_info
->ipcp_orig_node
)
3483 if (src
->offset
== -1)
3484 t
= caller_info
->known_csts
[src
->index
];
3486 t
= get_clone_agg_value (cs
->caller
, src
->offset
, src
->index
);
3487 return (t
!= NULL_TREE
3488 && values_equal_for_ipcp_p (src
->val
->value
, t
));
3492 /* At the moment we do not propagate over arithmetic jump functions in
3493 SCCs, so it is safe to detect self-feeding recursive calls in this
3495 if (src
->val
== dest_val
)
3498 struct ipcp_agg_lattice
*aglat
;
3499 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
3501 if (src
->offset
== -1)
3502 return (plats
->itself
.is_single_const ()
3503 && values_equal_for_ipcp_p (src
->val
->value
,
3504 plats
->itself
.values
->value
));
3507 if (plats
->aggs_bottom
|| plats
->aggs_contain_variable
)
3509 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3510 if (aglat
->offset
== src
->offset
)
3511 return (aglat
->is_single_const ()
3512 && values_equal_for_ipcp_p (src
->val
->value
,
3513 aglat
->values
->value
));
3519 /* Return true if edge CS does bring about the value described by SRC to
3520 DST_VAL of node DEST or its clone for all contexts. */
3523 cgraph_edge_brings_value_p (cgraph_edge
*cs
,
3524 ipcp_value_source
<ipa_polymorphic_call_context
> *src
,
3526 ipcp_value
<ipa_polymorphic_call_context
> *)
3528 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3529 cgraph_node
*real_dest
= cs
->callee
->function_symbol ();
3531 if (!same_node_or_its_all_contexts_clone_p (real_dest
, dest
)
3532 || caller_info
->node_dead
)
3537 if (caller_info
->ipcp_orig_node
)
3538 return (caller_info
->known_contexts
.length () > (unsigned) src
->index
)
3539 && values_equal_for_ipcp_p (src
->val
->value
,
3540 caller_info
->known_contexts
[src
->index
]);
3542 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
3544 return plats
->ctxlat
.is_single_const ()
3545 && values_equal_for_ipcp_p (src
->val
->value
,
3546 plats
->ctxlat
.values
->value
);
3549 /* Get the next clone in the linked list of clones of an edge. */
3551 static inline struct cgraph_edge
*
3552 get_next_cgraph_edge_clone (struct cgraph_edge
*cs
)
3554 edge_clone_summary
*s
= edge_clone_summaries
->get (cs
);
3555 return s
!= NULL
? s
->next_clone
: NULL
;
3558 /* Given VAL that is intended for DEST, iterate over all its sources and if any
3559 of them is viable and hot, return true. In that case, for those that still
3560 hold, add their edge frequency and their number into *FREQUENCY and
3561 *CALLER_COUNT respectively. */
3563 template <typename valtype
>
3565 get_info_about_necessary_edges (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
3567 profile_count
*count_sum
, int *caller_count
)
3569 ipcp_value_source
<valtype
> *src
;
3570 int freq
= 0, count
= 0;
3571 profile_count cnt
= profile_count::zero ();
3573 bool non_self_recursive
= false;
3575 for (src
= val
->sources
; src
; src
= src
->next
)
3577 struct cgraph_edge
*cs
= src
->cs
;
3580 if (cgraph_edge_brings_value_p (cs
, src
, dest
, val
))
3583 freq
+= cs
->frequency ();
3584 if (cs
->count
.ipa ().initialized_p ())
3585 cnt
+= cs
->count
.ipa ();
3586 hot
|= cs
->maybe_hot_p ();
3587 if (cs
->caller
!= dest
)
3588 non_self_recursive
= true;
3590 cs
= get_next_cgraph_edge_clone (cs
);
3594 /* If the only edges bringing a value are self-recursive ones, do not bother
3596 if (!non_self_recursive
)
3601 *caller_count
= count
;
3605 /* Return a vector of incoming edges that do bring value VAL to node DEST. It
3606 is assumed their number is known and equal to CALLER_COUNT. */
3608 template <typename valtype
>
3609 static vec
<cgraph_edge
*>
3610 gather_edges_for_value (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
3613 ipcp_value_source
<valtype
> *src
;
3614 vec
<cgraph_edge
*> ret
;
3616 ret
.create (caller_count
);
3617 for (src
= val
->sources
; src
; src
= src
->next
)
3619 struct cgraph_edge
*cs
= src
->cs
;
3622 if (cgraph_edge_brings_value_p (cs
, src
, dest
, val
))
3623 ret
.quick_push (cs
);
3624 cs
= get_next_cgraph_edge_clone (cs
);
3631 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
3632 Return it or NULL if for some reason it cannot be created. */
3634 static struct ipa_replace_map
*
3635 get_replacement_map (struct ipa_node_params
*info
, tree value
, int parm_num
)
3637 struct ipa_replace_map
*replace_map
;
3640 replace_map
= ggc_alloc
<ipa_replace_map
> ();
3643 fprintf (dump_file
, " replacing ");
3644 ipa_dump_param (dump_file
, info
, parm_num
);
3646 fprintf (dump_file
, " with const ");
3647 print_generic_expr (dump_file
, value
);
3648 fprintf (dump_file
, "\n");
3650 replace_map
->old_tree
= NULL
;
3651 replace_map
->parm_num
= parm_num
;
3652 replace_map
->new_tree
= value
;
3653 replace_map
->replace_p
= true;
3654 replace_map
->ref_p
= false;
3659 /* Dump new profiling counts */
3662 dump_profile_updates (struct cgraph_node
*orig_node
,
3663 struct cgraph_node
*new_node
)
3665 struct cgraph_edge
*cs
;
3667 fprintf (dump_file
, " setting count of the specialized node to ");
3668 new_node
->count
.dump (dump_file
);
3669 fprintf (dump_file
, "\n");
3670 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3672 fprintf (dump_file
, " edge to %s has count ",
3673 cs
->callee
->name ());
3674 cs
->count
.dump (dump_file
);
3675 fprintf (dump_file
, "\n");
3678 fprintf (dump_file
, " setting count of the original node to ");
3679 orig_node
->count
.dump (dump_file
);
3680 fprintf (dump_file
, "\n");
3681 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3683 fprintf (dump_file
, " edge to %s is left with ",
3684 cs
->callee
->name ());
3685 cs
->count
.dump (dump_file
);
3686 fprintf (dump_file
, "\n");
3690 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
3691 their profile information to reflect this. */
3694 update_profiling_info (struct cgraph_node
*orig_node
,
3695 struct cgraph_node
*new_node
)
3697 struct cgraph_edge
*cs
;
3698 struct caller_statistics stats
;
3699 profile_count new_sum
, orig_sum
;
3700 profile_count remainder
, orig_node_count
= orig_node
->count
;
3702 if (!(orig_node_count
.ipa () > profile_count::zero ()))
3705 init_caller_stats (&stats
);
3706 orig_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
3708 orig_sum
= stats
.count_sum
;
3709 init_caller_stats (&stats
);
3710 new_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
3712 new_sum
= stats
.count_sum
;
3714 if (orig_node_count
< orig_sum
+ new_sum
)
3718 fprintf (dump_file
, " Problem: node %s has too low count ",
3719 orig_node
->dump_name ());
3720 orig_node_count
.dump (dump_file
);
3721 fprintf (dump_file
, "while the sum of incoming count is ");
3722 (orig_sum
+ new_sum
).dump (dump_file
);
3723 fprintf (dump_file
, "\n");
3726 orig_node_count
= (orig_sum
+ new_sum
).apply_scale (12, 10);
3729 fprintf (dump_file
, " proceeding by pretending it was ");
3730 orig_node_count
.dump (dump_file
);
3731 fprintf (dump_file
, "\n");
3735 remainder
= orig_node_count
.combine_with_ipa_count (orig_node_count
.ipa ()
3737 new_sum
= orig_node_count
.combine_with_ipa_count (new_sum
);
3738 orig_node
->count
= remainder
;
3740 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3741 cs
->count
= cs
->count
.apply_scale (new_sum
, orig_node_count
);
3743 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3744 cs
->count
= cs
->count
.apply_scale (remainder
, orig_node_count
);
3747 dump_profile_updates (orig_node
, new_node
);
3750 /* Update the respective profile of specialized NEW_NODE and the original
3751 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
3752 have been redirected to the specialized version. */
3755 update_specialized_profile (struct cgraph_node
*new_node
,
3756 struct cgraph_node
*orig_node
,
3757 profile_count redirected_sum
)
3759 struct cgraph_edge
*cs
;
3760 profile_count new_node_count
, orig_node_count
= orig_node
->count
;
3764 fprintf (dump_file
, " the sum of counts of redirected edges is ");
3765 redirected_sum
.dump (dump_file
);
3766 fprintf (dump_file
, "\n");
3768 if (!(orig_node_count
> profile_count::zero ()))
3771 gcc_assert (orig_node_count
>= redirected_sum
);
3773 new_node_count
= new_node
->count
;
3774 new_node
->count
+= redirected_sum
;
3775 orig_node
->count
-= redirected_sum
;
3777 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3778 cs
->count
+= cs
->count
.apply_scale (redirected_sum
, new_node_count
);
3780 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3782 profile_count dec
= cs
->count
.apply_scale (redirected_sum
,
3788 dump_profile_updates (orig_node
, new_node
);
3791 /* Create a specialized version of NODE with known constants in KNOWN_CSTS,
3792 known contexts in KNOWN_CONTEXTS and known aggregate values in AGGVALS and
3793 redirect all edges in CALLERS to it. */
3795 static struct cgraph_node
*
3796 create_specialized_node (struct cgraph_node
*node
,
3797 vec
<tree
> known_csts
,
3798 vec
<ipa_polymorphic_call_context
> known_contexts
,
3799 struct ipa_agg_replacement_value
*aggvals
,
3800 vec
<cgraph_edge
*> callers
)
3802 struct ipa_node_params
*new_info
, *info
= IPA_NODE_REF (node
);
3803 vec
<ipa_replace_map
*, va_gc
> *replace_trees
= NULL
;
3804 struct ipa_agg_replacement_value
*av
;
3805 struct cgraph_node
*new_node
;
3806 int i
, count
= ipa_get_param_count (info
);
3807 bitmap args_to_skip
;
3809 gcc_assert (!info
->ipcp_orig_node
);
3811 if (node
->local
.can_change_signature
)
3813 args_to_skip
= BITMAP_GGC_ALLOC ();
3814 for (i
= 0; i
< count
; i
++)
3816 tree t
= known_csts
[i
];
3818 if (t
|| !ipa_is_param_used (info
, i
))
3819 bitmap_set_bit (args_to_skip
, i
);
3824 args_to_skip
= NULL
;
3825 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3826 fprintf (dump_file
, " cannot change function signature\n");
3829 for (i
= 0; i
< count
; i
++)
3831 tree t
= known_csts
[i
];
3834 struct ipa_replace_map
*replace_map
;
3836 gcc_checking_assert (TREE_CODE (t
) != TREE_BINFO
);
3837 replace_map
= get_replacement_map (info
, t
, i
);
3839 vec_safe_push (replace_trees
, replace_map
);
3842 auto_vec
<cgraph_edge
*, 2> self_recursive_calls
;
3843 for (i
= callers
.length () - 1; i
>= 0; i
--)
3845 cgraph_edge
*cs
= callers
[i
];
3846 if (cs
->caller
== node
)
3848 self_recursive_calls
.safe_push (cs
);
3849 callers
.unordered_remove (i
);
3853 new_node
= node
->create_virtual_clone (callers
, replace_trees
,
3854 args_to_skip
, "constprop");
3856 bool have_self_recursive_calls
= !self_recursive_calls
.is_empty ();
3857 for (unsigned j
= 0; j
< self_recursive_calls
.length (); j
++)
3859 cgraph_edge
*cs
= get_next_cgraph_edge_clone (self_recursive_calls
[j
]);
3860 /* Cloned edges can disappear during cloning as speculation can be
3861 resolved, check that we have one and that it comes from the last
3863 if (cs
&& cs
->caller
== new_node
)
3864 cs
->redirect_callee_duplicating_thunks (new_node
);
3865 /* Any future code that would make more than one clone of an outgoing
3866 edge would confuse this mechanism, so let's check that does not
3868 gcc_checking_assert (!cs
3869 || !get_next_cgraph_edge_clone (cs
)
3870 || get_next_cgraph_edge_clone (cs
)->caller
!= new_node
);
3872 if (have_self_recursive_calls
)
3873 new_node
->expand_all_artificial_thunks ();
3875 ipa_set_node_agg_value_chain (new_node
, aggvals
);
3876 for (av
= aggvals
; av
; av
= av
->next
)
3877 new_node
->maybe_create_reference (av
->value
, NULL
);
3879 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3881 fprintf (dump_file
, " the new node is %s.\n", new_node
->dump_name ());
3882 if (known_contexts
.exists ())
3884 for (i
= 0; i
< count
; i
++)
3885 if (!known_contexts
[i
].useless_p ())
3887 fprintf (dump_file
, " known ctx %i is ", i
);
3888 known_contexts
[i
].dump (dump_file
);
3892 ipa_dump_agg_replacement_values (dump_file
, aggvals
);
3894 ipa_check_create_node_params ();
3895 update_profiling_info (node
, new_node
);
3896 new_info
= IPA_NODE_REF (new_node
);
3897 new_info
->ipcp_orig_node
= node
;
3898 new_info
->known_csts
= known_csts
;
3899 new_info
->known_contexts
= known_contexts
;
3901 ipcp_discover_new_direct_edges (new_node
, known_csts
, known_contexts
, aggvals
);
3907 /* Return true, if JFUNC, which describes a i-th parameter of call CS, is a
3908 simple no-operation pass-through function to itself. */
3911 self_recursive_pass_through_p (cgraph_edge
*cs
, ipa_jump_func
*jfunc
, int i
)
3913 enum availability availability
;
3914 if (cs
->caller
== cs
->callee
->function_symbol (&availability
)
3915 && availability
> AVAIL_INTERPOSABLE
3916 && jfunc
->type
== IPA_JF_PASS_THROUGH
3917 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
3918 && ipa_get_jf_pass_through_formal_id (jfunc
) == i
)
3923 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
3924 KNOWN_CSTS with constants that are also known for all of the CALLERS. */
3927 find_more_scalar_values_for_callers_subset (struct cgraph_node
*node
,
3928 vec
<tree
> known_csts
,
3929 vec
<cgraph_edge
*> callers
)
3931 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3932 int i
, count
= ipa_get_param_count (info
);
3934 for (i
= 0; i
< count
; i
++)
3936 struct cgraph_edge
*cs
;
3937 tree newval
= NULL_TREE
;
3940 tree type
= ipa_get_type (info
, i
);
3942 if (ipa_get_scalar_lat (info
, i
)->bottom
|| known_csts
[i
])
3945 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3947 struct ipa_jump_func
*jump_func
;
3950 if (IPA_NODE_REF (cs
->caller
)->node_dead
)
3953 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
))
3955 && call_passes_through_thunk_p (cs
)))
3960 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
3961 if (self_recursive_pass_through_p (cs
, jump_func
, i
))
3964 t
= ipa_value_from_jfunc (IPA_NODE_REF (cs
->caller
), jump_func
, type
);
3967 && !values_equal_for_ipcp_p (t
, newval
))
3968 || (!first
&& !newval
))
3980 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3982 fprintf (dump_file
, " adding an extra known scalar value ");
3983 print_ipcp_constant_value (dump_file
, newval
);
3984 fprintf (dump_file
, " for ");
3985 ipa_dump_param (dump_file
, info
, i
);
3986 fprintf (dump_file
, "\n");
3989 known_csts
[i
] = newval
;
3994 /* Given a NODE and a subset of its CALLERS, try to populate plank slots in
3995 KNOWN_CONTEXTS with polymorphic contexts that are also known for all of the
3999 find_more_contexts_for_caller_subset (cgraph_node
*node
,
4000 vec
<ipa_polymorphic_call_context
>
4002 vec
<cgraph_edge
*> callers
)
4004 ipa_node_params
*info
= IPA_NODE_REF (node
);
4005 int i
, count
= ipa_get_param_count (info
);
4007 for (i
= 0; i
< count
; i
++)
4011 if (ipa_get_poly_ctx_lat (info
, i
)->bottom
4012 || (known_contexts
->exists ()
4013 && !(*known_contexts
)[i
].useless_p ()))
4016 ipa_polymorphic_call_context newval
;
4020 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4022 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
)))
4024 ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
),
4026 ipa_polymorphic_call_context ctx
;
4027 ctx
= ipa_context_from_jfunc (IPA_NODE_REF (cs
->caller
), cs
, i
,
4035 newval
.meet_with (ctx
);
4036 if (newval
.useless_p ())
4040 if (!newval
.useless_p ())
4042 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4044 fprintf (dump_file
, " adding an extra known polymorphic "
4046 print_ipcp_constant_value (dump_file
, newval
);
4047 fprintf (dump_file
, " for ");
4048 ipa_dump_param (dump_file
, info
, i
);
4049 fprintf (dump_file
, "\n");
4052 if (!known_contexts
->exists ())
4053 known_contexts
->safe_grow_cleared (ipa_get_param_count (info
));
4054 (*known_contexts
)[i
] = newval
;
4060 /* Go through PLATS and create a vector of values consisting of values and
4061 offsets (minus OFFSET) of lattices that contain only a single value. */
4063 static vec
<ipa_agg_jf_item
>
4064 copy_plats_to_inter (struct ipcp_param_lattices
*plats
, HOST_WIDE_INT offset
)
4066 vec
<ipa_agg_jf_item
> res
= vNULL
;
4068 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
4071 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
4072 if (aglat
->is_single_const ())
4074 struct ipa_agg_jf_item ti
;
4075 ti
.offset
= aglat
->offset
- offset
;
4076 ti
.value
= aglat
->values
->value
;
4082 /* Intersect all values in INTER with single value lattices in PLATS (while
4083 subtracting OFFSET). */
4086 intersect_with_plats (struct ipcp_param_lattices
*plats
,
4087 vec
<ipa_agg_jf_item
> *inter
,
4088 HOST_WIDE_INT offset
)
4090 struct ipcp_agg_lattice
*aglat
;
4091 struct ipa_agg_jf_item
*item
;
4094 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
4100 aglat
= plats
->aggs
;
4101 FOR_EACH_VEC_ELT (*inter
, k
, item
)
4108 if (aglat
->offset
- offset
> item
->offset
)
4110 if (aglat
->offset
- offset
== item
->offset
)
4112 gcc_checking_assert (item
->value
);
4113 if (aglat
->is_single_const ()
4114 && values_equal_for_ipcp_p (item
->value
,
4115 aglat
->values
->value
))
4119 aglat
= aglat
->next
;
4122 item
->value
= NULL_TREE
;
4126 /* Copy aggregate replacement values of NODE (which is an IPA-CP clone) to the
4127 vector result while subtracting OFFSET from the individual value offsets. */
4129 static vec
<ipa_agg_jf_item
>
4130 agg_replacements_to_vector (struct cgraph_node
*node
, int index
,
4131 HOST_WIDE_INT offset
)
4133 struct ipa_agg_replacement_value
*av
;
4134 vec
<ipa_agg_jf_item
> res
= vNULL
;
4136 for (av
= ipa_get_agg_replacements_for_node (node
); av
; av
= av
->next
)
4137 if (av
->index
== index
4138 && (av
->offset
- offset
) >= 0)
4140 struct ipa_agg_jf_item item
;
4141 gcc_checking_assert (av
->value
);
4142 item
.offset
= av
->offset
- offset
;
4143 item
.value
= av
->value
;
4144 res
.safe_push (item
);
4150 /* Intersect all values in INTER with those that we have already scheduled to
4151 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
4152 (while subtracting OFFSET). */
4155 intersect_with_agg_replacements (struct cgraph_node
*node
, int index
,
4156 vec
<ipa_agg_jf_item
> *inter
,
4157 HOST_WIDE_INT offset
)
4159 struct ipa_agg_replacement_value
*srcvals
;
4160 struct ipa_agg_jf_item
*item
;
4163 srcvals
= ipa_get_agg_replacements_for_node (node
);
4170 FOR_EACH_VEC_ELT (*inter
, i
, item
)
4172 struct ipa_agg_replacement_value
*av
;
4176 for (av
= srcvals
; av
; av
= av
->next
)
4178 gcc_checking_assert (av
->value
);
4179 if (av
->index
== index
4180 && av
->offset
- offset
== item
->offset
)
4182 if (values_equal_for_ipcp_p (item
->value
, av
->value
))
4188 item
->value
= NULL_TREE
;
4192 /* Intersect values in INTER with aggregate values that come along edge CS to
4193 parameter number INDEX and return it. If INTER does not actually exist yet,
4194 copy all incoming values to it. If we determine we ended up with no values
4195 whatsoever, return a released vector. */
4197 static vec
<ipa_agg_jf_item
>
4198 intersect_aggregates_with_edge (struct cgraph_edge
*cs
, int index
,
4199 vec
<ipa_agg_jf_item
> inter
)
4201 struct ipa_jump_func
*jfunc
;
4202 jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), index
);
4203 if (jfunc
->type
== IPA_JF_PASS_THROUGH
4204 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
4206 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4207 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
4209 if (caller_info
->ipcp_orig_node
)
4211 struct cgraph_node
*orig_node
= caller_info
->ipcp_orig_node
;
4212 struct ipcp_param_lattices
*orig_plats
;
4213 orig_plats
= ipa_get_parm_lattices (IPA_NODE_REF (orig_node
),
4215 if (agg_pass_through_permissible_p (orig_plats
, jfunc
))
4217 if (!inter
.exists ())
4218 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, 0);
4220 intersect_with_agg_replacements (cs
->caller
, src_idx
,
4231 struct ipcp_param_lattices
*src_plats
;
4232 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
4233 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
4235 /* Currently we do not produce clobber aggregate jump
4236 functions, adjust when we do. */
4237 gcc_checking_assert (!jfunc
->agg
.items
);
4238 if (!inter
.exists ())
4239 inter
= copy_plats_to_inter (src_plats
, 0);
4241 intersect_with_plats (src_plats
, &inter
, 0);
4250 else if (jfunc
->type
== IPA_JF_ANCESTOR
4251 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
4253 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4254 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
4255 struct ipcp_param_lattices
*src_plats
;
4256 HOST_WIDE_INT delta
= ipa_get_jf_ancestor_offset (jfunc
);
4258 if (caller_info
->ipcp_orig_node
)
4260 if (!inter
.exists ())
4261 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, delta
);
4263 intersect_with_agg_replacements (cs
->caller
, src_idx
, &inter
,
4268 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
4269 /* Currently we do not produce clobber aggregate jump
4270 functions, adjust when we do. */
4271 gcc_checking_assert (!src_plats
->aggs
|| !jfunc
->agg
.items
);
4272 if (!inter
.exists ())
4273 inter
= copy_plats_to_inter (src_plats
, delta
);
4275 intersect_with_plats (src_plats
, &inter
, delta
);
4278 else if (jfunc
->agg
.items
)
4280 struct ipa_agg_jf_item
*item
;
4283 if (!inter
.exists ())
4284 for (unsigned i
= 0; i
< jfunc
->agg
.items
->length (); i
++)
4285 inter
.safe_push ((*jfunc
->agg
.items
)[i
]);
4287 FOR_EACH_VEC_ELT (inter
, k
, item
)
4295 while ((unsigned) l
< jfunc
->agg
.items
->length ())
4297 struct ipa_agg_jf_item
*ti
;
4298 ti
= &(*jfunc
->agg
.items
)[l
];
4299 if (ti
->offset
> item
->offset
)
4301 if (ti
->offset
== item
->offset
)
4303 gcc_checking_assert (ti
->value
);
4304 if (values_equal_for_ipcp_p (item
->value
,
4318 return vec
<ipa_agg_jf_item
>();
4323 /* Look at edges in CALLERS and collect all known aggregate values that arrive
4324 from all of them. */
4326 static struct ipa_agg_replacement_value
*
4327 find_aggregate_values_for_callers_subset (struct cgraph_node
*node
,
4328 vec
<cgraph_edge
*> callers
)
4330 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
4331 struct ipa_agg_replacement_value
*res
;
4332 struct ipa_agg_replacement_value
**tail
= &res
;
4333 struct cgraph_edge
*cs
;
4334 int i
, j
, count
= ipa_get_param_count (dest_info
);
4336 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4338 int c
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
4343 for (i
= 0; i
< count
; i
++)
4345 struct cgraph_edge
*cs
;
4346 vec
<ipa_agg_jf_item
> inter
= vNULL
;
4347 struct ipa_agg_jf_item
*item
;
4348 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (dest_info
, i
);
4351 /* Among other things, the following check should deal with all by_ref
4353 if (plats
->aggs_bottom
)
4356 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4358 struct ipa_jump_func
*jfunc
4359 = ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
4360 if (self_recursive_pass_through_p (cs
, jfunc
, i
)
4361 && (!plats
->aggs_by_ref
4362 || ipa_get_jf_pass_through_agg_preserved (jfunc
)))
4364 inter
= intersect_aggregates_with_edge (cs
, i
, inter
);
4366 if (!inter
.exists ())
4370 FOR_EACH_VEC_ELT (inter
, j
, item
)
4372 struct ipa_agg_replacement_value
*v
;
4377 v
= ggc_alloc
<ipa_agg_replacement_value
> ();
4379 v
->offset
= item
->offset
;
4380 v
->value
= item
->value
;
4381 v
->by_ref
= plats
->aggs_by_ref
;
4387 if (inter
.exists ())
4394 /* Determine whether CS also brings all scalar values that the NODE is
4398 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge
*cs
,
4399 struct cgraph_node
*node
)
4401 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
4402 int count
= ipa_get_param_count (dest_info
);
4403 struct ipa_node_params
*caller_info
;
4404 struct ipa_edge_args
*args
;
4407 caller_info
= IPA_NODE_REF (cs
->caller
);
4408 args
= IPA_EDGE_REF (cs
);
4409 for (i
= 0; i
< count
; i
++)
4411 struct ipa_jump_func
*jump_func
;
4414 val
= dest_info
->known_csts
[i
];
4418 if (i
>= ipa_get_cs_argument_count (args
))
4420 jump_func
= ipa_get_ith_jump_func (args
, i
);
4421 t
= ipa_value_from_jfunc (caller_info
, jump_func
,
4422 ipa_get_type (dest_info
, i
));
4423 if (!t
|| !values_equal_for_ipcp_p (val
, t
))
4429 /* Determine whether CS also brings all aggregate values that NODE is
4432 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge
*cs
,
4433 struct cgraph_node
*node
)
4435 struct ipa_node_params
*orig_caller_info
= IPA_NODE_REF (cs
->caller
);
4436 struct ipa_node_params
*orig_node_info
;
4437 struct ipa_agg_replacement_value
*aggval
;
4440 aggval
= ipa_get_agg_replacements_for_node (node
);
4444 count
= ipa_get_param_count (IPA_NODE_REF (node
));
4445 ec
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
4447 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4448 if (aggval
->index
>= ec
)
4451 orig_node_info
= IPA_NODE_REF (IPA_NODE_REF (node
)->ipcp_orig_node
);
4452 if (orig_caller_info
->ipcp_orig_node
)
4453 orig_caller_info
= IPA_NODE_REF (orig_caller_info
->ipcp_orig_node
);
4455 for (i
= 0; i
< count
; i
++)
4457 static vec
<ipa_agg_jf_item
> values
= vec
<ipa_agg_jf_item
>();
4458 struct ipcp_param_lattices
*plats
;
4459 bool interesting
= false;
4460 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4461 if (aggval
->index
== i
)
4469 plats
= ipa_get_parm_lattices (orig_node_info
, aggval
->index
);
4470 if (plats
->aggs_bottom
)
4473 values
= intersect_aggregates_with_edge (cs
, i
, values
);
4474 if (!values
.exists ())
4477 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4478 if (aggval
->index
== i
)
4480 struct ipa_agg_jf_item
*item
;
4483 FOR_EACH_VEC_ELT (values
, j
, item
)
4485 && item
->offset
== av
->offset
4486 && values_equal_for_ipcp_p (item
->value
, av
->value
))
4501 /* Given an original NODE and a VAL for which we have already created a
4502 specialized clone, look whether there are incoming edges that still lead
4503 into the old node but now also bring the requested value and also conform to
4504 all other criteria such that they can be redirected the special node.
4505 This function can therefore redirect the final edge in a SCC. */
4507 template <typename valtype
>
4509 perhaps_add_new_callers (cgraph_node
*node
, ipcp_value
<valtype
> *val
)
4511 ipcp_value_source
<valtype
> *src
;
4512 profile_count redirected_sum
= profile_count::zero ();
4514 for (src
= val
->sources
; src
; src
= src
->next
)
4516 struct cgraph_edge
*cs
= src
->cs
;
4519 if (cgraph_edge_brings_value_p (cs
, src
, node
, val
)
4520 && cgraph_edge_brings_all_scalars_for_node (cs
, val
->spec_node
)
4521 && cgraph_edge_brings_all_agg_vals_for_node (cs
, val
->spec_node
))
4524 fprintf (dump_file
, " - adding an extra caller %s of %s\n",
4525 cs
->caller
->dump_name (),
4526 val
->spec_node
->dump_name ());
4528 cs
->redirect_callee_duplicating_thunks (val
->spec_node
);
4529 val
->spec_node
->expand_all_artificial_thunks ();
4530 if (cs
->count
.ipa ().initialized_p ())
4531 redirected_sum
= redirected_sum
+ cs
->count
.ipa ();
4533 cs
= get_next_cgraph_edge_clone (cs
);
4537 if (redirected_sum
.nonzero_p ())
4538 update_specialized_profile (val
->spec_node
, node
, redirected_sum
);
4541 /* Return true if KNOWN_CONTEXTS contain at least one useful context. */
4544 known_contexts_useful_p (vec
<ipa_polymorphic_call_context
> known_contexts
)
4546 ipa_polymorphic_call_context
*ctx
;
4549 FOR_EACH_VEC_ELT (known_contexts
, i
, ctx
)
4550 if (!ctx
->useless_p ())
4555 /* Return a copy of KNOWN_CSTS if it is not empty, otherwise return vNULL. */
4557 static vec
<ipa_polymorphic_call_context
>
4558 copy_useful_known_contexts (vec
<ipa_polymorphic_call_context
> known_contexts
)
4560 if (known_contexts_useful_p (known_contexts
))
4561 return known_contexts
.copy ();
4566 /* Copy KNOWN_CSTS and modify the copy according to VAL and INDEX. If
4567 non-empty, replace KNOWN_CONTEXTS with its copy too. */
4570 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
4571 vec
<ipa_polymorphic_call_context
> *known_contexts
,
4572 ipcp_value
<tree
> *val
,
4575 *known_csts
= known_csts
->copy ();
4576 *known_contexts
= copy_useful_known_contexts (*known_contexts
);
4577 (*known_csts
)[index
] = val
->value
;
4580 /* Replace KNOWN_CSTS with its copy. Also copy KNOWN_CONTEXTS and modify the
4581 copy according to VAL and INDEX. */
4584 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
4585 vec
<ipa_polymorphic_call_context
> *known_contexts
,
4586 ipcp_value
<ipa_polymorphic_call_context
> *val
,
4589 *known_csts
= known_csts
->copy ();
4590 *known_contexts
= known_contexts
->copy ();
4591 (*known_contexts
)[index
] = val
->value
;
4594 /* Return true if OFFSET indicates this was not an aggregate value or there is
4595 a replacement equivalent to VALUE, INDEX and OFFSET among those in the
4599 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*aggvals
,
4600 int index
, HOST_WIDE_INT offset
, tree value
)
4607 if (aggvals
->index
== index
4608 && aggvals
->offset
== offset
4609 && values_equal_for_ipcp_p (aggvals
->value
, value
))
4611 aggvals
= aggvals
->next
;
4616 /* Return true if offset is minus one because source of a polymorphic contect
4617 cannot be an aggregate value. */
4620 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*,
4621 int , HOST_WIDE_INT offset
,
4622 ipa_polymorphic_call_context
)
4624 return offset
== -1;
4627 /* Decide wheter to create a special version of NODE for value VAL of parameter
4628 at the given INDEX. If OFFSET is -1, the value is for the parameter itself,
4629 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS,
4630 KNOWN_CONTEXTS and KNOWN_AGGS describe the other already known values. */
4632 template <typename valtype
>
4634 decide_about_value (struct cgraph_node
*node
, int index
, HOST_WIDE_INT offset
,
4635 ipcp_value
<valtype
> *val
, vec
<tree
> known_csts
,
4636 vec
<ipa_polymorphic_call_context
> known_contexts
)
4638 struct ipa_agg_replacement_value
*aggvals
;
4639 int freq_sum
, caller_count
;
4640 profile_count count_sum
;
4641 vec
<cgraph_edge
*> callers
;
4645 perhaps_add_new_callers (node
, val
);
4648 else if (val
->local_size_cost
+ overall_size
> max_new_size
)
4650 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4651 fprintf (dump_file
, " Ignoring candidate value because "
4652 "max_new_size would be reached with %li.\n",
4653 val
->local_size_cost
+ overall_size
);
4656 else if (!get_info_about_necessary_edges (val
, node
, &freq_sum
, &count_sum
,
4660 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4662 fprintf (dump_file
, " - considering value ");
4663 print_ipcp_constant_value (dump_file
, val
->value
);
4664 fprintf (dump_file
, " for ");
4665 ipa_dump_param (dump_file
, IPA_NODE_REF (node
), index
);
4667 fprintf (dump_file
, ", offset: " HOST_WIDE_INT_PRINT_DEC
, offset
);
4668 fprintf (dump_file
, " (caller_count: %i)\n", caller_count
);
4671 if (!good_cloning_opportunity_p (node
, val
->local_time_benefit
,
4672 freq_sum
, count_sum
,
4673 val
->local_size_cost
)
4674 && !good_cloning_opportunity_p (node
,
4675 val
->local_time_benefit
4676 + val
->prop_time_benefit
,
4677 freq_sum
, count_sum
,
4678 val
->local_size_cost
4679 + val
->prop_size_cost
))
4683 fprintf (dump_file
, " Creating a specialized node of %s.\n",
4684 node
->dump_name ());
4686 callers
= gather_edges_for_value (val
, node
, caller_count
);
4688 modify_known_vectors_with_val (&known_csts
, &known_contexts
, val
, index
);
4691 known_csts
= known_csts
.copy ();
4692 known_contexts
= copy_useful_known_contexts (known_contexts
);
4694 find_more_scalar_values_for_callers_subset (node
, known_csts
, callers
);
4695 find_more_contexts_for_caller_subset (node
, &known_contexts
, callers
);
4696 aggvals
= find_aggregate_values_for_callers_subset (node
, callers
);
4697 gcc_checking_assert (ipcp_val_agg_replacement_ok_p (aggvals
, index
,
4698 offset
, val
->value
));
4699 val
->spec_node
= create_specialized_node (node
, known_csts
, known_contexts
,
4701 overall_size
+= val
->local_size_cost
;
4703 /* TODO: If for some lattice there is only one other known value
4704 left, make a special node for it too. */
4709 /* Decide whether and what specialized clones of NODE should be created. */
4712 decide_whether_version_node (struct cgraph_node
*node
)
4714 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
4715 int i
, count
= ipa_get_param_count (info
);
4716 vec
<tree
> known_csts
;
4717 vec
<ipa_polymorphic_call_context
> known_contexts
;
4718 vec
<ipa_agg_jump_function
> known_aggs
= vNULL
;
4724 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4725 fprintf (dump_file
, "\nEvaluating opportunities for %s.\n",
4726 node
->dump_name ());
4728 gather_context_independent_values (info
, &known_csts
, &known_contexts
,
4729 info
->do_clone_for_all_contexts
? &known_aggs
4732 for (i
= 0; i
< count
;i
++)
4734 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4735 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
4736 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
4741 ipcp_value
<tree
> *val
;
4742 for (val
= lat
->values
; val
; val
= val
->next
)
4743 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
4747 if (!plats
->aggs_bottom
)
4749 struct ipcp_agg_lattice
*aglat
;
4750 ipcp_value
<tree
> *val
;
4751 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
4752 if (!aglat
->bottom
&& aglat
->values
4753 /* If the following is false, the one value is in
4755 && (plats
->aggs_contain_variable
4756 || !aglat
->is_single_const ()))
4757 for (val
= aglat
->values
; val
; val
= val
->next
)
4758 ret
|= decide_about_value (node
, i
, aglat
->offset
, val
,
4759 known_csts
, known_contexts
);
4763 && known_contexts
[i
].useless_p ())
4765 ipcp_value
<ipa_polymorphic_call_context
> *val
;
4766 for (val
= ctxlat
->values
; val
; val
= val
->next
)
4767 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
4771 info
= IPA_NODE_REF (node
);
4774 if (info
->do_clone_for_all_contexts
)
4776 struct cgraph_node
*clone
;
4777 vec
<cgraph_edge
*> callers
;
4780 fprintf (dump_file
, " - Creating a specialized node of %s "
4781 "for all known contexts.\n", node
->dump_name ());
4783 callers
= node
->collect_callers ();
4784 find_more_scalar_values_for_callers_subset (node
, known_csts
, callers
);
4785 find_more_contexts_for_caller_subset (node
, &known_contexts
, callers
);
4786 ipa_agg_replacement_value
*aggvals
4787 = find_aggregate_values_for_callers_subset (node
, callers
);
4789 if (!known_contexts_useful_p (known_contexts
))
4791 known_contexts
.release ();
4792 known_contexts
= vNULL
;
4794 clone
= create_specialized_node (node
, known_csts
, known_contexts
,
4796 info
= IPA_NODE_REF (node
);
4797 info
->do_clone_for_all_contexts
= false;
4798 IPA_NODE_REF (clone
)->is_all_contexts_clone
= true;
4799 for (i
= 0; i
< count
; i
++)
4800 vec_free (known_aggs
[i
].items
);
4801 known_aggs
.release ();
4806 known_csts
.release ();
4807 known_contexts
.release ();
4813 /* Transitively mark all callees of NODE within the same SCC as not dead. */
4816 spread_undeadness (struct cgraph_node
*node
)
4818 struct cgraph_edge
*cs
;
4820 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
4821 if (ipa_edge_within_scc (cs
))
4823 struct cgraph_node
*callee
;
4824 struct ipa_node_params
*info
;
4826 callee
= cs
->callee
->function_symbol (NULL
);
4827 info
= IPA_NODE_REF (callee
);
4829 if (info
->node_dead
)
4831 info
->node_dead
= 0;
4832 spread_undeadness (callee
);
4837 /* Return true if NODE has a caller from outside of its SCC that is not
4838 dead. Worker callback for cgraph_for_node_and_aliases. */
4841 has_undead_caller_from_outside_scc_p (struct cgraph_node
*node
,
4842 void *data ATTRIBUTE_UNUSED
)
4844 struct cgraph_edge
*cs
;
4846 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
4847 if (cs
->caller
->thunk
.thunk_p
4848 && cs
->caller
->call_for_symbol_thunks_and_aliases
4849 (has_undead_caller_from_outside_scc_p
, NULL
, true))
4851 else if (!ipa_edge_within_scc (cs
)
4852 && !IPA_NODE_REF (cs
->caller
)->node_dead
)
4858 /* Identify nodes within the same SCC as NODE which are no longer needed
4859 because of new clones and will be removed as unreachable. */
4862 identify_dead_nodes (struct cgraph_node
*node
)
4864 struct cgraph_node
*v
;
4865 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4867 && !v
->call_for_symbol_thunks_and_aliases
4868 (has_undead_caller_from_outside_scc_p
, NULL
, true))
4869 IPA_NODE_REF (v
)->node_dead
= 1;
4871 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4872 if (!IPA_NODE_REF (v
)->node_dead
)
4873 spread_undeadness (v
);
4875 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4877 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4878 if (IPA_NODE_REF (v
)->node_dead
)
4879 fprintf (dump_file
, " Marking node as dead: %s.\n", v
->dump_name ());
4883 /* The decision stage. Iterate over the topological order of call graph nodes
4884 TOPO and make specialized clones if deemed beneficial. */
4887 ipcp_decision_stage (struct ipa_topo_info
*topo
)
4892 fprintf (dump_file
, "\nIPA decision stage:\n\n");
4894 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
4896 struct cgraph_node
*node
= topo
->order
[i
];
4897 bool change
= false, iterate
= true;
4901 struct cgraph_node
*v
;
4903 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4904 if (v
->has_gimple_body_p ()
4905 && ipcp_versionable_function_p (v
))
4906 iterate
|= decide_whether_version_node (v
);
4911 identify_dead_nodes (node
);
4915 /* Look up all the bits information that we have discovered and copy it over
4916 to the transformation summary. */
4919 ipcp_store_bits_results (void)
4923 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
4925 ipa_node_params
*info
= IPA_NODE_REF (node
);
4926 bool dumped_sth
= false;
4927 bool found_useful_result
= false;
4929 if (!opt_for_fn (node
->decl
, flag_ipa_bit_cp
))
4932 fprintf (dump_file
, "Not considering %s for ipa bitwise propagation "
4933 "; -fipa-bit-cp: disabled.\n",
4938 if (info
->ipcp_orig_node
)
4939 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
4941 unsigned count
= ipa_get_param_count (info
);
4942 for (unsigned i
= 0; i
< count
; i
++)
4944 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4945 if (plats
->bits_lattice
.constant_p ())
4947 found_useful_result
= true;
4952 if (!found_useful_result
)
4955 ipcp_transformation_initialize ();
4956 ipcp_transformation
*ts
= ipcp_transformation_sum
->get_create (node
);
4957 vec_safe_reserve_exact (ts
->bits
, count
);
4959 for (unsigned i
= 0; i
< count
; i
++)
4961 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4964 if (plats
->bits_lattice
.constant_p ())
4966 = ipa_get_ipa_bits_for_value (plats
->bits_lattice
.get_value (),
4967 plats
->bits_lattice
.get_mask ());
4971 ts
->bits
->quick_push (jfbits
);
4972 if (!dump_file
|| !jfbits
)
4976 fprintf (dump_file
, "Propagated bits info for function %s:\n",
4977 node
->dump_name ());
4980 fprintf (dump_file
, " param %i: value = ", i
);
4981 print_hex (jfbits
->value
, dump_file
);
4982 fprintf (dump_file
, ", mask = ");
4983 print_hex (jfbits
->mask
, dump_file
);
4984 fprintf (dump_file
, "\n");
4989 /* Look up all VR information that we have discovered and copy it over
4990 to the transformation summary. */
4993 ipcp_store_vr_results (void)
4997 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
4999 ipa_node_params
*info
= IPA_NODE_REF (node
);
5000 bool found_useful_result
= false;
5002 if (!opt_for_fn (node
->decl
, flag_ipa_vrp
))
5005 fprintf (dump_file
, "Not considering %s for VR discovery "
5006 "and propagate; -fipa-ipa-vrp: disabled.\n",
5011 if (info
->ipcp_orig_node
)
5012 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
5014 unsigned count
= ipa_get_param_count (info
);
5015 for (unsigned i
= 0; i
< count
; i
++)
5017 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5018 if (!plats
->m_value_range
.bottom_p ()
5019 && !plats
->m_value_range
.top_p ())
5021 found_useful_result
= true;
5025 if (!found_useful_result
)
5028 ipcp_transformation_initialize ();
5029 ipcp_transformation
*ts
= ipcp_transformation_sum
->get_create (node
);
5030 vec_safe_reserve_exact (ts
->m_vr
, count
);
5032 for (unsigned i
= 0; i
< count
; i
++)
5034 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5037 if (!plats
->m_value_range
.bottom_p ()
5038 && !plats
->m_value_range
.top_p ())
5041 vr
.type
= plats
->m_value_range
.m_vr
.type
;
5042 vr
.min
= wi::to_wide (plats
->m_value_range
.m_vr
.min
);
5043 vr
.max
= wi::to_wide (plats
->m_value_range
.m_vr
.max
);
5048 vr
.type
= VR_VARYING
;
5049 vr
.min
= vr
.max
= wi::zero (INT_TYPE_SIZE
);
5051 ts
->m_vr
->quick_push (vr
);
5056 /* The IPCP driver. */
5061 struct ipa_topo_info topo
;
5063 if (edge_clone_summaries
== NULL
)
5064 edge_clone_summaries
= new edge_clone_summary_t (symtab
);
5066 ipa_check_create_node_params ();
5067 ipa_check_create_edge_args ();
5071 fprintf (dump_file
, "\nIPA structures before propagation:\n");
5072 if (dump_flags
& TDF_DETAILS
)
5073 ipa_print_all_params (dump_file
);
5074 ipa_print_all_jump_functions (dump_file
);
5077 /* Topological sort. */
5078 build_toporder_info (&topo
);
5079 /* Do the interprocedural propagation. */
5080 ipcp_propagate_stage (&topo
);
5081 /* Decide what constant propagation and cloning should be performed. */
5082 ipcp_decision_stage (&topo
);
5083 /* Store results of bits propagation. */
5084 ipcp_store_bits_results ();
5085 /* Store results of value range propagation. */
5086 ipcp_store_vr_results ();
5088 /* Free all IPCP structures. */
5089 free_toporder_info (&topo
);
5090 delete edge_clone_summaries
;
5091 ipa_free_all_structures_after_ipa_cp ();
5093 fprintf (dump_file
, "\nIPA constant propagation end\n");
5097 /* Initialization and computation of IPCP data structures. This is the initial
5098 intraprocedural analysis of functions, which gathers information to be
5099 propagated later on. */
5102 ipcp_generate_summary (void)
5104 struct cgraph_node
*node
;
5107 fprintf (dump_file
, "\nIPA constant propagation start:\n");
5108 ipa_register_cgraph_hooks ();
5110 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5111 ipa_analyze_node (node
);
5114 /* Write ipcp summary for nodes in SET. */
5117 ipcp_write_summary (void)
5119 ipa_prop_write_jump_functions ();
5122 /* Read ipcp summary. */
5125 ipcp_read_summary (void)
5127 ipa_prop_read_jump_functions ();
5132 const pass_data pass_data_ipa_cp
=
5134 IPA_PASS
, /* type */
5136 OPTGROUP_NONE
, /* optinfo_flags */
5137 TV_IPA_CONSTANT_PROP
, /* tv_id */
5138 0, /* properties_required */
5139 0, /* properties_provided */
5140 0, /* properties_destroyed */
5141 0, /* todo_flags_start */
5142 ( TODO_dump_symtab
| TODO_remove_functions
), /* todo_flags_finish */
5145 class pass_ipa_cp
: public ipa_opt_pass_d
5148 pass_ipa_cp (gcc::context
*ctxt
)
5149 : ipa_opt_pass_d (pass_data_ipa_cp
, ctxt
,
5150 ipcp_generate_summary
, /* generate_summary */
5151 ipcp_write_summary
, /* write_summary */
5152 ipcp_read_summary
, /* read_summary */
5153 ipcp_write_transformation_summaries
, /*
5154 write_optimization_summary */
5155 ipcp_read_transformation_summaries
, /*
5156 read_optimization_summary */
5157 NULL
, /* stmt_fixup */
5158 0, /* function_transform_todo_flags_start */
5159 ipcp_transform_function
, /* function_transform */
5160 NULL
) /* variable_transform */
5163 /* opt_pass methods: */
5164 virtual bool gate (function
*)
5166 /* FIXME: We should remove the optimize check after we ensure we never run
5167 IPA passes when not optimizing. */
5168 return (flag_ipa_cp
&& optimize
) || in_lto_p
;
5171 virtual unsigned int execute (function
*) { return ipcp_driver (); }
5173 }; // class pass_ipa_cp
5178 make_pass_ipa_cp (gcc::context
*ctxt
)
5180 return new pass_ipa_cp (ctxt
);
5183 /* Reset all state within ipa-cp.c so that we can rerun the compiler
5184 within the same process. For use by toplev::finalize. */
5187 ipa_cp_c_finalize (void)
5189 max_count
= profile_count::uninitialized ();