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
310 value_range_base m_vr
;
312 inline bool bottom_p () const;
313 inline bool top_p () const;
314 inline bool set_to_bottom ();
315 bool meet_with (const value_range_base
*p_vr
);
316 bool meet_with (const ipcp_vr_lattice
&other
);
317 void init () { gcc_assert (m_vr
.undefined_p ()); }
318 void print (FILE * f
);
321 bool meet_with_1 (const value_range_base
*other_vr
);
324 /* Structure containing lattices for a parameter itself and for pieces of
325 aggregates that are passed in the parameter or by a reference in a parameter
326 plus some other useful flags. */
328 class ipcp_param_lattices
331 /* Lattice describing the value of the parameter itself. */
332 ipcp_lattice
<tree
> itself
;
333 /* Lattice describing the polymorphic contexts of a parameter. */
334 ipcp_lattice
<ipa_polymorphic_call_context
> ctxlat
;
335 /* Lattices describing aggregate parts. */
336 ipcp_agg_lattice
*aggs
;
337 /* Lattice describing known bits. */
338 ipcp_bits_lattice bits_lattice
;
339 /* Lattice describing value range. */
340 ipcp_vr_lattice m_value_range
;
341 /* Number of aggregate lattices */
343 /* True if aggregate data were passed by reference (as opposed to by
346 /* All aggregate lattices contain a variable component (in addition to
348 bool aggs_contain_variable
;
349 /* The value of all aggregate lattices is bottom (i.e. variable and unusable
350 for any propagation). */
353 /* There is a virtual call based on this parameter. */
357 /* Allocation pools for values and their sources in ipa-cp. */
359 object_allocator
<ipcp_value
<tree
> > ipcp_cst_values_pool
360 ("IPA-CP constant values");
362 object_allocator
<ipcp_value
<ipa_polymorphic_call_context
> >
363 ipcp_poly_ctx_values_pool ("IPA-CP polymorphic contexts");
365 object_allocator
<ipcp_value_source
<tree
> > ipcp_sources_pool
366 ("IPA-CP value sources");
368 object_allocator
<ipcp_agg_lattice
> ipcp_agg_lattice_pool
369 ("IPA_CP aggregate lattices");
371 /* Maximal count found in program. */
373 static profile_count max_count
;
375 /* Original overall size of the program. */
377 static long overall_size
, max_new_size
;
379 /* 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 whether LAT is a lattice with a single constant and without an
411 template <typename valtype
>
413 ipcp_lattice
<valtype
>::is_single_const ()
415 if (bottom
|| contains_variable
|| values_count
!= 1)
421 /* Print V which is extracted from a value in a lattice to F. */
424 print_ipcp_constant_value (FILE * f
, tree v
)
426 if (TREE_CODE (v
) == ADDR_EXPR
427 && TREE_CODE (TREE_OPERAND (v
, 0)) == CONST_DECL
)
430 print_generic_expr (f
, DECL_INITIAL (TREE_OPERAND (v
, 0)));
433 print_generic_expr (f
, v
);
436 /* Print V which is extracted from a value in a lattice to F. */
439 print_ipcp_constant_value (FILE * f
, ipa_polymorphic_call_context v
)
444 /* Print a lattice LAT to F. */
446 template <typename valtype
>
448 ipcp_lattice
<valtype
>::print (FILE * f
, bool dump_sources
, bool dump_benefits
)
450 ipcp_value
<valtype
> *val
;
455 fprintf (f
, "BOTTOM\n");
459 if (!values_count
&& !contains_variable
)
461 fprintf (f
, "TOP\n");
465 if (contains_variable
)
467 fprintf (f
, "VARIABLE");
473 for (val
= values
; val
; val
= val
->next
)
475 if (dump_benefits
&& prev
)
477 else if (!dump_benefits
&& prev
)
482 print_ipcp_constant_value (f
, val
->value
);
486 ipcp_value_source
<valtype
> *s
;
488 fprintf (f
, " [from:");
489 for (s
= val
->sources
; s
; s
= s
->next
)
490 fprintf (f
, " %i(%f)", s
->cs
->caller
->order
,
491 s
->cs
->sreal_frequency ().to_double ());
496 fprintf (f
, " [loc_time: %i, loc_size: %i, "
497 "prop_time: %i, prop_size: %i]\n",
498 val
->local_time_benefit
, val
->local_size_cost
,
499 val
->prop_time_benefit
, val
->prop_size_cost
);
506 ipcp_bits_lattice::print (FILE *f
)
509 fprintf (f
, " Bits unknown (TOP)\n");
510 else if (bottom_p ())
511 fprintf (f
, " Bits unusable (BOTTOM)\n");
514 fprintf (f
, " Bits: value = "); print_hex (get_value (), f
);
515 fprintf (f
, ", mask = "); print_hex (get_mask (), f
);
520 /* Print value range lattice to F. */
523 ipcp_vr_lattice::print (FILE * f
)
525 dump_value_range_base (f
, &m_vr
);
528 /* Print all ipcp_lattices of all functions to F. */
531 print_all_lattices (FILE * f
, bool dump_sources
, bool dump_benefits
)
533 struct cgraph_node
*node
;
536 fprintf (f
, "\nLattices:\n");
537 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
539 struct ipa_node_params
*info
;
541 info
= IPA_NODE_REF (node
);
542 fprintf (f
, " Node: %s:\n", node
->dump_name ());
543 count
= ipa_get_param_count (info
);
544 for (i
= 0; i
< count
; i
++)
546 struct ipcp_agg_lattice
*aglat
;
547 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
548 fprintf (f
, " param [%d]: ", i
);
549 plats
->itself
.print (f
, dump_sources
, dump_benefits
);
550 fprintf (f
, " ctxs: ");
551 plats
->ctxlat
.print (f
, dump_sources
, dump_benefits
);
552 plats
->bits_lattice
.print (f
);
554 plats
->m_value_range
.print (f
);
556 if (plats
->virt_call
)
557 fprintf (f
, " virt_call flag set\n");
559 if (plats
->aggs_bottom
)
561 fprintf (f
, " AGGS BOTTOM\n");
564 if (plats
->aggs_contain_variable
)
565 fprintf (f
, " AGGS VARIABLE\n");
566 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
568 fprintf (f
, " %soffset " HOST_WIDE_INT_PRINT_DEC
": ",
569 plats
->aggs_by_ref
? "ref " : "", aglat
->offset
);
570 aglat
->print (f
, dump_sources
, dump_benefits
);
576 /* Determine whether it is at all technically possible to create clones of NODE
577 and store this information in the ipa_node_params structure associated
581 determine_versionability (struct cgraph_node
*node
,
582 struct ipa_node_params
*info
)
584 const char *reason
= NULL
;
586 /* There are a number of generic reasons functions cannot be versioned. We
587 also cannot remove parameters if there are type attributes such as fnspec
589 if (node
->alias
|| node
->thunk
.thunk_p
)
590 reason
= "alias or thunk";
591 else if (!node
->local
.versionable
)
592 reason
= "not a tree_versionable_function";
593 else if (node
->get_availability () <= AVAIL_INTERPOSABLE
)
594 reason
= "insufficient body availability";
595 else if (!opt_for_fn (node
->decl
, optimize
)
596 || !opt_for_fn (node
->decl
, flag_ipa_cp
))
597 reason
= "non-optimized function";
598 else if (lookup_attribute ("omp declare simd", DECL_ATTRIBUTES (node
->decl
)))
600 /* Ideally we should clone the SIMD clones themselves and create
601 vector copies of them, so IPA-cp and SIMD clones can happily
602 coexist, but that may not be worth the effort. */
603 reason
= "function has SIMD clones";
605 else if (lookup_attribute ("target_clones", DECL_ATTRIBUTES (node
->decl
)))
607 /* Ideally we should clone the target clones themselves and create
608 copies of them, so IPA-cp and target clones can happily
609 coexist, but that may not be worth the effort. */
610 reason
= "function target_clones attribute";
612 /* Don't clone decls local to a comdat group; it breaks and for C++
613 decloned constructors, inlining is always better anyway. */
614 else if (node
->comdat_local_p ())
615 reason
= "comdat-local function";
616 else if (node
->calls_comdat_local
)
618 /* TODO: call is versionable if we make sure that all
619 callers are inside of a comdat group. */
620 reason
= "calls comdat-local function";
623 /* Functions calling BUILT_IN_VA_ARG_PACK and BUILT_IN_VA_ARG_PACK_LEN
624 work only when inlined. Cloning them may still lead to better code
625 because ipa-cp will not give up on cloning further. If the function is
626 external this however leads to wrong code because we may end up producing
627 offline copy of the function. */
628 if (DECL_EXTERNAL (node
->decl
))
629 for (cgraph_edge
*edge
= node
->callees
; !reason
&& edge
;
630 edge
= edge
->next_callee
)
631 if (fndecl_built_in_p (edge
->callee
->decl
, BUILT_IN_NORMAL
))
633 if (DECL_FUNCTION_CODE (edge
->callee
->decl
) == BUILT_IN_VA_ARG_PACK
)
634 reason
= "external function which calls va_arg_pack";
635 if (DECL_FUNCTION_CODE (edge
->callee
->decl
)
636 == BUILT_IN_VA_ARG_PACK_LEN
)
637 reason
= "external function which calls va_arg_pack_len";
640 if (reason
&& dump_file
&& !node
->alias
&& !node
->thunk
.thunk_p
)
641 fprintf (dump_file
, "Function %s is not versionable, reason: %s.\n",
642 node
->dump_name (), reason
);
644 info
->versionable
= (reason
== NULL
);
647 /* Return true if it is at all technically possible to create clones of a
651 ipcp_versionable_function_p (struct cgraph_node
*node
)
653 return IPA_NODE_REF (node
)->versionable
;
656 /* Structure holding accumulated information about callers of a node. */
658 struct caller_statistics
660 profile_count count_sum
;
661 int n_calls
, n_hot_calls
, freq_sum
;
664 /* Initialize fields of STAT to zeroes. */
667 init_caller_stats (struct caller_statistics
*stats
)
669 stats
->count_sum
= profile_count::zero ();
671 stats
->n_hot_calls
= 0;
675 /* Worker callback of cgraph_for_node_and_aliases accumulating statistics of
676 non-thunk incoming edges to NODE. */
679 gather_caller_stats (struct cgraph_node
*node
, void *data
)
681 struct caller_statistics
*stats
= (struct caller_statistics
*) data
;
682 struct cgraph_edge
*cs
;
684 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
685 if (!cs
->caller
->thunk
.thunk_p
)
687 if (cs
->count
.ipa ().initialized_p ())
688 stats
->count_sum
+= cs
->count
.ipa ();
689 stats
->freq_sum
+= cs
->frequency ();
691 if (cs
->maybe_hot_p ())
692 stats
->n_hot_calls
++;
698 /* Return true if this NODE is viable candidate for cloning. */
701 ipcp_cloning_candidate_p (struct cgraph_node
*node
)
703 struct caller_statistics stats
;
705 gcc_checking_assert (node
->has_gimple_body_p ());
707 if (!opt_for_fn (node
->decl
, flag_ipa_cp_clone
))
710 fprintf (dump_file
, "Not considering %s for cloning; "
711 "-fipa-cp-clone disabled.\n",
716 if (node
->optimize_for_size_p ())
719 fprintf (dump_file
, "Not considering %s for cloning; "
720 "optimizing it for size.\n",
725 init_caller_stats (&stats
);
726 node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
, false);
728 if (ipa_fn_summaries
->get (node
)->self_size
< stats
.n_calls
)
731 fprintf (dump_file
, "Considering %s for cloning; code might shrink.\n",
736 /* When profile is available and function is hot, propagate into it even if
737 calls seems cold; constant propagation can improve function's speed
739 if (max_count
> profile_count::zero ())
741 if (stats
.count_sum
> node
->count
.ipa ().apply_scale (90, 100))
744 fprintf (dump_file
, "Considering %s for cloning; "
745 "usually called directly.\n",
750 if (!stats
.n_hot_calls
)
753 fprintf (dump_file
, "Not considering %s for cloning; no hot calls.\n",
758 fprintf (dump_file
, "Considering %s for cloning.\n",
763 template <typename valtype
>
764 class value_topo_info
767 /* Head of the linked list of topologically sorted values. */
768 ipcp_value
<valtype
> *values_topo
;
769 /* Stack for creating SCCs, represented by a linked list too. */
770 ipcp_value
<valtype
> *stack
;
771 /* Counter driving the algorithm in add_val_to_toposort. */
774 value_topo_info () : values_topo (NULL
), stack (NULL
), dfs_counter (0)
776 void add_val (ipcp_value
<valtype
> *cur_val
);
777 void propagate_effects ();
780 /* Arrays representing a topological ordering of call graph nodes and a stack
781 of nodes used during constant propagation and also data required to perform
782 topological sort of values and propagation of benefits in the determined
788 /* Array with obtained topological order of cgraph nodes. */
789 struct cgraph_node
**order
;
790 /* Stack of cgraph nodes used during propagation within SCC until all values
791 in the SCC stabilize. */
792 struct cgraph_node
**stack
;
793 int nnodes
, stack_top
;
795 value_topo_info
<tree
> constants
;
796 value_topo_info
<ipa_polymorphic_call_context
> contexts
;
798 ipa_topo_info () : order(NULL
), stack(NULL
), nnodes(0), stack_top(0),
803 /* Allocate the arrays in TOPO and topologically sort the nodes into order. */
806 build_toporder_info (struct ipa_topo_info
*topo
)
808 topo
->order
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
809 topo
->stack
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
811 gcc_checking_assert (topo
->stack_top
== 0);
812 topo
->nnodes
= ipa_reduced_postorder (topo
->order
, true, true, NULL
);
815 /* Free information about strongly connected components and the arrays in
819 free_toporder_info (struct ipa_topo_info
*topo
)
821 ipa_free_postorder_info ();
826 /* Add NODE to the stack in TOPO, unless it is already there. */
829 push_node_to_stack (struct ipa_topo_info
*topo
, struct cgraph_node
*node
)
831 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
832 if (info
->node_enqueued
)
834 info
->node_enqueued
= 1;
835 topo
->stack
[topo
->stack_top
++] = node
;
838 /* Pop a node from the stack in TOPO and return it or return NULL if the stack
841 static struct cgraph_node
*
842 pop_node_from_stack (struct ipa_topo_info
*topo
)
846 struct cgraph_node
*node
;
848 node
= topo
->stack
[topo
->stack_top
];
849 IPA_NODE_REF (node
)->node_enqueued
= 0;
856 /* Set lattice LAT to bottom and return true if it previously was not set as
859 template <typename valtype
>
861 ipcp_lattice
<valtype
>::set_to_bottom ()
868 /* Mark lattice as containing an unknown value and return true if it previously
869 was not marked as such. */
871 template <typename valtype
>
873 ipcp_lattice
<valtype
>::set_contains_variable ()
875 bool ret
= !contains_variable
;
876 contains_variable
= true;
880 /* Set all aggegate lattices in PLATS to bottom and return true if they were
881 not previously set as such. */
884 set_agg_lats_to_bottom (struct ipcp_param_lattices
*plats
)
886 bool ret
= !plats
->aggs_bottom
;
887 plats
->aggs_bottom
= true;
891 /* Mark all aggegate lattices in PLATS as containing an unknown value and
892 return true if they were not previously marked as such. */
895 set_agg_lats_contain_variable (struct ipcp_param_lattices
*plats
)
897 bool ret
= !plats
->aggs_contain_variable
;
898 plats
->aggs_contain_variable
= true;
903 ipcp_vr_lattice::meet_with (const ipcp_vr_lattice
&other
)
905 return meet_with_1 (&other
.m_vr
);
908 /* Meet the current value of the lattice with value ranfge described by VR
912 ipcp_vr_lattice::meet_with (const value_range_base
*p_vr
)
914 return meet_with_1 (p_vr
);
917 /* Meet the current value of the lattice with value range described by
918 OTHER_VR lattice. Return TRUE if anything changed. */
921 ipcp_vr_lattice::meet_with_1 (const value_range_base
*other_vr
)
926 if (other_vr
->varying_p ())
927 return set_to_bottom ();
929 value_range_base
save (m_vr
);
930 m_vr
.union_ (other_vr
);
931 return !m_vr
.ignore_equivs_equal_p (save
);
934 /* Return true if value range information in the lattice is yet unknown. */
937 ipcp_vr_lattice::top_p () const
939 return m_vr
.undefined_p ();
942 /* Return true if value range information in the lattice is known to be
946 ipcp_vr_lattice::bottom_p () const
948 return m_vr
.varying_p ();
951 /* Set value range information in the lattice to bottom. Return true if it
952 previously was in a different state. */
955 ipcp_vr_lattice::set_to_bottom ()
957 if (m_vr
.varying_p ())
963 /* Set lattice value to bottom, if it already isn't the case. */
966 ipcp_bits_lattice::set_to_bottom ()
970 m_lattice_val
= IPA_BITS_VARYING
;
976 /* Set to constant if it isn't already. Only meant to be called
977 when switching state from TOP. */
980 ipcp_bits_lattice::set_to_constant (widest_int value
, widest_int mask
)
982 gcc_assert (top_p ());
983 m_lattice_val
= IPA_BITS_CONSTANT
;
989 /* Convert operand to value, mask form. */
992 ipcp_bits_lattice::get_value_and_mask (tree operand
, widest_int
*valuep
, widest_int
*maskp
)
994 wide_int
get_nonzero_bits (const_tree
);
996 if (TREE_CODE (operand
) == INTEGER_CST
)
998 *valuep
= wi::to_widest (operand
);
1008 /* Meet operation, similar to ccp_lattice_meet, we xor values
1009 if this->value, value have different values at same bit positions, we want
1010 to drop that bit to varying. Return true if mask is changed.
1011 This function assumes that the lattice value is in CONSTANT state */
1014 ipcp_bits_lattice::meet_with_1 (widest_int value
, widest_int mask
,
1017 gcc_assert (constant_p ());
1019 widest_int old_mask
= m_mask
;
1020 m_mask
= (m_mask
| mask
) | (m_value
^ value
);
1022 if (wi::sext (m_mask
, precision
) == -1)
1023 return set_to_bottom ();
1025 return m_mask
!= old_mask
;
1028 /* Meet the bits lattice with operand
1029 described by <value, mask, sgn, precision. */
1032 ipcp_bits_lattice::meet_with (widest_int value
, widest_int mask
,
1040 if (wi::sext (mask
, precision
) == -1)
1041 return set_to_bottom ();
1042 return set_to_constant (value
, mask
);
1045 return meet_with_1 (value
, mask
, precision
);
1048 /* Meet bits lattice with the result of bit_value_binop (other, operand)
1049 if code is binary operation or bit_value_unop (other) if code is unary op.
1050 In the case when code is nop_expr, no adjustment is required. */
1053 ipcp_bits_lattice::meet_with (ipcp_bits_lattice
& other
, unsigned precision
,
1054 signop sgn
, enum tree_code code
, tree operand
)
1056 if (other
.bottom_p ())
1057 return set_to_bottom ();
1059 if (bottom_p () || other
.top_p ())
1062 widest_int adjusted_value
, adjusted_mask
;
1064 if (TREE_CODE_CLASS (code
) == tcc_binary
)
1066 tree type
= TREE_TYPE (operand
);
1067 gcc_assert (INTEGRAL_TYPE_P (type
));
1068 widest_int o_value
, o_mask
;
1069 get_value_and_mask (operand
, &o_value
, &o_mask
);
1071 bit_value_binop (code
, sgn
, precision
, &adjusted_value
, &adjusted_mask
,
1072 sgn
, precision
, other
.get_value (), other
.get_mask (),
1073 TYPE_SIGN (type
), TYPE_PRECISION (type
), o_value
, o_mask
);
1075 if (wi::sext (adjusted_mask
, precision
) == -1)
1076 return set_to_bottom ();
1079 else if (TREE_CODE_CLASS (code
) == tcc_unary
)
1081 bit_value_unop (code
, sgn
, precision
, &adjusted_value
,
1082 &adjusted_mask
, sgn
, precision
, other
.get_value (),
1085 if (wi::sext (adjusted_mask
, precision
) == -1)
1086 return set_to_bottom ();
1090 return set_to_bottom ();
1094 if (wi::sext (adjusted_mask
, precision
) == -1)
1095 return set_to_bottom ();
1096 return set_to_constant (adjusted_value
, adjusted_mask
);
1099 return meet_with_1 (adjusted_value
, adjusted_mask
, precision
);
1102 /* Mark bot aggregate and scalar lattices as containing an unknown variable,
1103 return true is any of them has not been marked as such so far. */
1106 set_all_contains_variable (struct ipcp_param_lattices
*plats
)
1109 ret
= plats
->itself
.set_contains_variable ();
1110 ret
|= plats
->ctxlat
.set_contains_variable ();
1111 ret
|= set_agg_lats_contain_variable (plats
);
1112 ret
|= plats
->bits_lattice
.set_to_bottom ();
1113 ret
|= plats
->m_value_range
.set_to_bottom ();
1117 /* Worker of call_for_symbol_thunks_and_aliases, increment the integer DATA
1118 points to by the number of callers to NODE. */
1121 count_callers (cgraph_node
*node
, void *data
)
1123 int *caller_count
= (int *) data
;
1125 for (cgraph_edge
*cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
1126 /* Local thunks can be handled transparently, but if the thunk can not
1127 be optimized out, count it as a real use. */
1128 if (!cs
->caller
->thunk
.thunk_p
|| !cs
->caller
->local
.local
)
1133 /* Worker of call_for_symbol_thunks_and_aliases, it is supposed to be called on
1134 the one caller of some other node. Set the caller's corresponding flag. */
1137 set_single_call_flag (cgraph_node
*node
, void *)
1139 cgraph_edge
*cs
= node
->callers
;
1140 /* Local thunks can be handled transparently, skip them. */
1141 while (cs
&& cs
->caller
->thunk
.thunk_p
&& cs
->caller
->local
.local
)
1142 cs
= cs
->next_caller
;
1145 IPA_NODE_REF (cs
->caller
)->node_calling_single_call
= true;
1151 /* Initialize ipcp_lattices. */
1154 initialize_node_lattices (struct cgraph_node
*node
)
1156 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1157 struct cgraph_edge
*ie
;
1158 bool disable
= false, variable
= false;
1161 gcc_checking_assert (node
->has_gimple_body_p ());
1162 if (node
->local
.local
)
1164 int caller_count
= 0;
1165 node
->call_for_symbol_thunks_and_aliases (count_callers
, &caller_count
,
1167 gcc_checking_assert (caller_count
> 0);
1168 if (caller_count
== 1)
1169 node
->call_for_symbol_thunks_and_aliases (set_single_call_flag
,
1174 /* When cloning is allowed, we can assume that externally visible
1175 functions are not called. We will compensate this by cloning
1177 if (ipcp_versionable_function_p (node
)
1178 && ipcp_cloning_candidate_p (node
))
1184 for (i
= 0; i
< ipa_get_param_count (info
); i
++)
1186 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1187 plats
->m_value_range
.init ();
1190 if (disable
|| variable
)
1192 for (i
= 0; i
< ipa_get_param_count (info
); i
++)
1194 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1197 plats
->itself
.set_to_bottom ();
1198 plats
->ctxlat
.set_to_bottom ();
1199 set_agg_lats_to_bottom (plats
);
1200 plats
->bits_lattice
.set_to_bottom ();
1201 plats
->m_value_range
.set_to_bottom ();
1204 set_all_contains_variable (plats
);
1206 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1207 && !node
->alias
&& !node
->thunk
.thunk_p
)
1208 fprintf (dump_file
, "Marking all lattices of %s as %s\n",
1209 node
->dump_name (), disable
? "BOTTOM" : "VARIABLE");
1212 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
1213 if (ie
->indirect_info
->polymorphic
1214 && ie
->indirect_info
->param_index
>= 0)
1216 gcc_checking_assert (ie
->indirect_info
->param_index
>= 0);
1217 ipa_get_parm_lattices (info
,
1218 ie
->indirect_info
->param_index
)->virt_call
= 1;
1222 /* Return the result of a (possibly arithmetic) pass through jump function
1223 JFUNC on the constant value INPUT. RES_TYPE is the type of the parameter
1224 to which the result is passed. Return NULL_TREE if that cannot be
1225 determined or be considered an interprocedural invariant. */
1228 ipa_get_jf_pass_through_result (struct ipa_jump_func
*jfunc
, tree input
,
1233 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
1235 if (!is_gimple_ip_invariant (input
))
1238 tree_code opcode
= ipa_get_jf_pass_through_operation (jfunc
);
1241 if (TREE_CODE_CLASS (opcode
) == tcc_comparison
)
1242 res_type
= boolean_type_node
;
1243 else if (expr_type_first_operand_type_p (opcode
))
1244 res_type
= TREE_TYPE (input
);
1249 if (TREE_CODE_CLASS (opcode
) == tcc_unary
)
1250 res
= fold_unary (opcode
, res_type
, input
);
1252 res
= fold_binary (opcode
, res_type
, input
,
1253 ipa_get_jf_pass_through_operand (jfunc
));
1255 if (res
&& !is_gimple_ip_invariant (res
))
1261 /* Return the result of an ancestor jump function JFUNC on the constant value
1262 INPUT. Return NULL_TREE if that cannot be determined. */
1265 ipa_get_jf_ancestor_result (struct ipa_jump_func
*jfunc
, tree input
)
1267 gcc_checking_assert (TREE_CODE (input
) != TREE_BINFO
);
1268 if (TREE_CODE (input
) == ADDR_EXPR
)
1270 tree t
= TREE_OPERAND (input
, 0);
1271 t
= build_ref_for_offset (EXPR_LOCATION (t
), t
,
1272 ipa_get_jf_ancestor_offset (jfunc
), false,
1273 ptr_type_node
, NULL
, false);
1274 return build_fold_addr_expr (t
);
1280 /* Determine whether JFUNC evaluates to a single known constant value and if
1281 so, return it. Otherwise return NULL. INFO describes the caller node or
1282 the one it is inlined to, so that pass-through jump functions can be
1283 evaluated. PARM_TYPE is the type of the parameter to which the result is
1287 ipa_value_from_jfunc (struct ipa_node_params
*info
, struct ipa_jump_func
*jfunc
,
1290 if (jfunc
->type
== IPA_JF_CONST
)
1291 return ipa_get_jf_constant (jfunc
);
1292 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1293 || jfunc
->type
== IPA_JF_ANCESTOR
)
1298 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1299 idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1301 idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1303 if (info
->ipcp_orig_node
)
1304 input
= info
->known_csts
[idx
];
1307 ipcp_lattice
<tree
> *lat
;
1310 || idx
>= ipa_get_param_count (info
))
1312 lat
= ipa_get_scalar_lat (info
, idx
);
1313 if (!lat
->is_single_const ())
1315 input
= lat
->values
->value
;
1321 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1322 return ipa_get_jf_pass_through_result (jfunc
, input
, parm_type
);
1324 return ipa_get_jf_ancestor_result (jfunc
, input
);
1330 /* Determie whether JFUNC evaluates to single known polymorphic context, given
1331 that INFO describes the caller node or the one it is inlined to, CS is the
1332 call graph edge corresponding to JFUNC and CSIDX index of the described
1335 ipa_polymorphic_call_context
1336 ipa_context_from_jfunc (ipa_node_params
*info
, cgraph_edge
*cs
, int csidx
,
1337 ipa_jump_func
*jfunc
)
1339 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
1340 ipa_polymorphic_call_context ctx
;
1341 ipa_polymorphic_call_context
*edge_ctx
1342 = cs
? ipa_get_ith_polymorhic_call_context (args
, csidx
) : NULL
;
1344 if (edge_ctx
&& !edge_ctx
->useless_p ())
1347 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1348 || jfunc
->type
== IPA_JF_ANCESTOR
)
1350 ipa_polymorphic_call_context srcctx
;
1352 bool type_preserved
= true;
1353 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1355 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1357 type_preserved
= ipa_get_jf_pass_through_type_preserved (jfunc
);
1358 srcidx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1362 type_preserved
= ipa_get_jf_ancestor_type_preserved (jfunc
);
1363 srcidx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1365 if (info
->ipcp_orig_node
)
1367 if (info
->known_contexts
.exists ())
1368 srcctx
= info
->known_contexts
[srcidx
];
1373 || srcidx
>= ipa_get_param_count (info
))
1375 ipcp_lattice
<ipa_polymorphic_call_context
> *lat
;
1376 lat
= ipa_get_poly_ctx_lat (info
, srcidx
);
1377 if (!lat
->is_single_const ())
1379 srcctx
= lat
->values
->value
;
1381 if (srcctx
.useless_p ())
1383 if (jfunc
->type
== IPA_JF_ANCESTOR
)
1384 srcctx
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
1385 if (!type_preserved
)
1386 srcctx
.possible_dynamic_type_change (cs
->in_polymorphic_cdtor
);
1387 srcctx
.combine_with (ctx
);
1394 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
1395 bottom, not containing a variable component and without any known value at
1399 ipcp_verify_propagated_values (void)
1401 struct cgraph_node
*node
;
1403 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
1405 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1406 int i
, count
= ipa_get_param_count (info
);
1408 for (i
= 0; i
< count
; i
++)
1410 ipcp_lattice
<tree
> *lat
= ipa_get_scalar_lat (info
, i
);
1413 && !lat
->contains_variable
1414 && lat
->values_count
== 0)
1418 symtab
->dump (dump_file
);
1419 fprintf (dump_file
, "\nIPA lattices after constant "
1420 "propagation, before gcc_unreachable:\n");
1421 print_all_lattices (dump_file
, true, false);
1430 /* Return true iff X and Y should be considered equal values by IPA-CP. */
1433 values_equal_for_ipcp_p (tree x
, tree y
)
1435 gcc_checking_assert (x
!= NULL_TREE
&& y
!= NULL_TREE
);
1440 if (TREE_CODE (x
) == ADDR_EXPR
1441 && TREE_CODE (y
) == ADDR_EXPR
1442 && TREE_CODE (TREE_OPERAND (x
, 0)) == CONST_DECL
1443 && TREE_CODE (TREE_OPERAND (y
, 0)) == CONST_DECL
)
1444 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x
, 0)),
1445 DECL_INITIAL (TREE_OPERAND (y
, 0)), 0);
1447 return operand_equal_p (x
, y
, 0);
1450 /* Return true iff X and Y should be considered equal contexts by IPA-CP. */
1453 values_equal_for_ipcp_p (ipa_polymorphic_call_context x
,
1454 ipa_polymorphic_call_context y
)
1456 return x
.equal_to (y
);
1460 /* Add a new value source to the value represented by THIS, marking that a
1461 value comes from edge CS and (if the underlying jump function is a
1462 pass-through or an ancestor one) from a caller value SRC_VAL of a caller
1463 parameter described by SRC_INDEX. OFFSET is negative if the source was the
1464 scalar value of the parameter itself or the offset within an aggregate. */
1466 template <typename valtype
>
1468 ipcp_value
<valtype
>::add_source (cgraph_edge
*cs
, ipcp_value
*src_val
,
1469 int src_idx
, HOST_WIDE_INT offset
)
1471 ipcp_value_source
<valtype
> *src
;
1473 src
= new (ipcp_sources_pool
.allocate ()) ipcp_value_source
<valtype
>;
1474 src
->offset
= offset
;
1477 src
->index
= src_idx
;
1479 src
->next
= sources
;
1483 /* Allocate a new ipcp_value holding a tree constant, initialize its value to
1484 SOURCE and clear all other fields. */
1486 static ipcp_value
<tree
> *
1487 allocate_and_init_ipcp_value (tree source
)
1489 ipcp_value
<tree
> *val
;
1491 val
= new (ipcp_cst_values_pool
.allocate ()) ipcp_value
<tree
>();
1492 val
->value
= source
;
1496 /* Allocate a new ipcp_value holding a polymorphic context, initialize its
1497 value to SOURCE and clear all other fields. */
1499 static ipcp_value
<ipa_polymorphic_call_context
> *
1500 allocate_and_init_ipcp_value (ipa_polymorphic_call_context source
)
1502 ipcp_value
<ipa_polymorphic_call_context
> *val
;
1505 val
= new (ipcp_poly_ctx_values_pool
.allocate ())
1506 ipcp_value
<ipa_polymorphic_call_context
>();
1507 val
->value
= source
;
1511 /* Try to add NEWVAL to LAT, potentially creating a new ipcp_value for it. CS,
1512 SRC_VAL SRC_INDEX and OFFSET are meant for add_source and have the same
1513 meaning. OFFSET -1 means the source is scalar and not a part of an
1516 template <typename valtype
>
1518 ipcp_lattice
<valtype
>::add_value (valtype newval
, cgraph_edge
*cs
,
1519 ipcp_value
<valtype
> *src_val
,
1520 int src_idx
, HOST_WIDE_INT offset
)
1522 ipcp_value
<valtype
> *val
;
1527 for (val
= values
; val
; val
= val
->next
)
1528 if (values_equal_for_ipcp_p (val
->value
, newval
))
1530 if (ipa_edge_within_scc (cs
))
1532 ipcp_value_source
<valtype
> *s
;
1533 for (s
= val
->sources
; s
; s
= s
->next
)
1540 val
->add_source (cs
, src_val
, src_idx
, offset
);
1544 if (values_count
== PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE
))
1546 /* We can only free sources, not the values themselves, because sources
1547 of other values in this SCC might point to them. */
1548 for (val
= values
; val
; val
= val
->next
)
1550 while (val
->sources
)
1552 ipcp_value_source
<valtype
> *src
= val
->sources
;
1553 val
->sources
= src
->next
;
1554 ipcp_sources_pool
.remove ((ipcp_value_source
<tree
>*)src
);
1559 return set_to_bottom ();
1563 val
= allocate_and_init_ipcp_value (newval
);
1564 val
->add_source (cs
, src_val
, src_idx
, offset
);
1570 /* Propagate values through a pass-through jump function JFUNC associated with
1571 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1572 is the index of the source parameter. PARM_TYPE is the type of the
1573 parameter to which the result is passed. */
1576 propagate_vals_across_pass_through (cgraph_edge
*cs
, ipa_jump_func
*jfunc
,
1577 ipcp_lattice
<tree
> *src_lat
,
1578 ipcp_lattice
<tree
> *dest_lat
, int src_idx
,
1581 ipcp_value
<tree
> *src_val
;
1584 /* Do not create new values when propagating within an SCC because if there
1585 are arithmetic functions with circular dependencies, there is infinite
1586 number of them and we would just make lattices bottom. If this condition
1587 is ever relaxed we have to detect self-feeding recursive calls in
1588 cgraph_edge_brings_value_p in a smarter way. */
1589 if ((ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1590 && ipa_edge_within_scc (cs
))
1591 ret
= dest_lat
->set_contains_variable ();
1593 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1595 tree cstval
= ipa_get_jf_pass_through_result (jfunc
, src_val
->value
,
1599 ret
|= dest_lat
->add_value (cstval
, cs
, src_val
, src_idx
);
1601 ret
|= dest_lat
->set_contains_variable ();
1607 /* Propagate values through an ancestor jump function JFUNC associated with
1608 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1609 is the index of the source parameter. */
1612 propagate_vals_across_ancestor (struct cgraph_edge
*cs
,
1613 struct ipa_jump_func
*jfunc
,
1614 ipcp_lattice
<tree
> *src_lat
,
1615 ipcp_lattice
<tree
> *dest_lat
, int src_idx
)
1617 ipcp_value
<tree
> *src_val
;
1620 if (ipa_edge_within_scc (cs
))
1621 return dest_lat
->set_contains_variable ();
1623 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1625 tree t
= ipa_get_jf_ancestor_result (jfunc
, src_val
->value
);
1628 ret
|= dest_lat
->add_value (t
, cs
, src_val
, src_idx
);
1630 ret
|= dest_lat
->set_contains_variable ();
1636 /* Propagate scalar values across jump function JFUNC that is associated with
1637 edge CS and put the values into DEST_LAT. PARM_TYPE is the type of the
1638 parameter to which the result is passed. */
1641 propagate_scalar_across_jump_function (struct cgraph_edge
*cs
,
1642 struct ipa_jump_func
*jfunc
,
1643 ipcp_lattice
<tree
> *dest_lat
,
1646 if (dest_lat
->bottom
)
1649 if (jfunc
->type
== IPA_JF_CONST
)
1651 tree val
= ipa_get_jf_constant (jfunc
);
1652 return dest_lat
->add_value (val
, cs
, NULL
, 0);
1654 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1655 || jfunc
->type
== IPA_JF_ANCESTOR
)
1657 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1658 ipcp_lattice
<tree
> *src_lat
;
1662 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1663 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1665 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1667 src_lat
= ipa_get_scalar_lat (caller_info
, src_idx
);
1668 if (src_lat
->bottom
)
1669 return dest_lat
->set_contains_variable ();
1671 /* If we would need to clone the caller and cannot, do not propagate. */
1672 if (!ipcp_versionable_function_p (cs
->caller
)
1673 && (src_lat
->contains_variable
1674 || (src_lat
->values_count
> 1)))
1675 return dest_lat
->set_contains_variable ();
1677 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1678 ret
= propagate_vals_across_pass_through (cs
, jfunc
, src_lat
,
1679 dest_lat
, src_idx
, param_type
);
1681 ret
= propagate_vals_across_ancestor (cs
, jfunc
, src_lat
, dest_lat
,
1684 if (src_lat
->contains_variable
)
1685 ret
|= dest_lat
->set_contains_variable ();
1690 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1691 use it for indirect inlining), we should propagate them too. */
1692 return dest_lat
->set_contains_variable ();
1695 /* Propagate scalar values across jump function JFUNC that is associated with
1696 edge CS and describes argument IDX and put the values into DEST_LAT. */
1699 propagate_context_across_jump_function (cgraph_edge
*cs
,
1700 ipa_jump_func
*jfunc
, int idx
,
1701 ipcp_lattice
<ipa_polymorphic_call_context
> *dest_lat
)
1703 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
1704 if (dest_lat
->bottom
)
1707 bool added_sth
= false;
1708 bool type_preserved
= true;
1710 ipa_polymorphic_call_context edge_ctx
, *edge_ctx_ptr
1711 = ipa_get_ith_polymorhic_call_context (args
, idx
);
1714 edge_ctx
= *edge_ctx_ptr
;
1716 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1717 || jfunc
->type
== IPA_JF_ANCESTOR
)
1719 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1721 ipcp_lattice
<ipa_polymorphic_call_context
> *src_lat
;
1723 /* TODO: Once we figure out how to propagate speculations, it will
1724 probably be a good idea to switch to speculation if type_preserved is
1725 not set instead of punting. */
1726 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1728 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1730 type_preserved
= ipa_get_jf_pass_through_type_preserved (jfunc
);
1731 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1735 type_preserved
= ipa_get_jf_ancestor_type_preserved (jfunc
);
1736 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1739 src_lat
= ipa_get_poly_ctx_lat (caller_info
, src_idx
);
1740 /* If we would need to clone the caller and cannot, do not propagate. */
1741 if (!ipcp_versionable_function_p (cs
->caller
)
1742 && (src_lat
->contains_variable
1743 || (src_lat
->values_count
> 1)))
1746 ipcp_value
<ipa_polymorphic_call_context
> *src_val
;
1747 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1749 ipa_polymorphic_call_context cur
= src_val
->value
;
1751 if (!type_preserved
)
1752 cur
.possible_dynamic_type_change (cs
->in_polymorphic_cdtor
);
1753 if (jfunc
->type
== IPA_JF_ANCESTOR
)
1754 cur
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
1755 /* TODO: In cases we know how the context is going to be used,
1756 we can improve the result by passing proper OTR_TYPE. */
1757 cur
.combine_with (edge_ctx
);
1758 if (!cur
.useless_p ())
1760 if (src_lat
->contains_variable
1761 && !edge_ctx
.equal_to (cur
))
1762 ret
|= dest_lat
->set_contains_variable ();
1763 ret
|= dest_lat
->add_value (cur
, cs
, src_val
, src_idx
);
1773 if (!edge_ctx
.useless_p ())
1774 ret
|= dest_lat
->add_value (edge_ctx
, cs
);
1776 ret
|= dest_lat
->set_contains_variable ();
1782 /* Propagate bits across jfunc that is associated with
1783 edge cs and update dest_lattice accordingly. */
1786 propagate_bits_across_jump_function (cgraph_edge
*cs
, int idx
,
1787 ipa_jump_func
*jfunc
,
1788 ipcp_bits_lattice
*dest_lattice
)
1790 if (dest_lattice
->bottom_p ())
1793 enum availability availability
;
1794 cgraph_node
*callee
= cs
->callee
->function_symbol (&availability
);
1795 struct ipa_node_params
*callee_info
= IPA_NODE_REF (callee
);
1796 tree parm_type
= ipa_get_type (callee_info
, idx
);
1798 /* For K&R C programs, ipa_get_type() could return NULL_TREE. Avoid the
1799 transform for these cases. Similarly, we can have bad type mismatches
1800 with LTO, avoid doing anything with those too. */
1802 || (!INTEGRAL_TYPE_P (parm_type
) && !POINTER_TYPE_P (parm_type
)))
1804 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1805 fprintf (dump_file
, "Setting dest_lattice to bottom, because type of "
1806 "param %i of %s is NULL or unsuitable for bits propagation\n",
1807 idx
, cs
->callee
->name ());
1809 return dest_lattice
->set_to_bottom ();
1812 unsigned precision
= TYPE_PRECISION (parm_type
);
1813 signop sgn
= TYPE_SIGN (parm_type
);
1815 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1816 || jfunc
->type
== IPA_JF_ANCESTOR
)
1818 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1819 tree operand
= NULL_TREE
;
1820 enum tree_code code
;
1823 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1825 code
= ipa_get_jf_pass_through_operation (jfunc
);
1826 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1827 if (code
!= NOP_EXPR
)
1828 operand
= ipa_get_jf_pass_through_operand (jfunc
);
1832 code
= POINTER_PLUS_EXPR
;
1833 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1834 unsigned HOST_WIDE_INT offset
= ipa_get_jf_ancestor_offset (jfunc
) / BITS_PER_UNIT
;
1835 operand
= build_int_cstu (size_type_node
, offset
);
1838 struct ipcp_param_lattices
*src_lats
1839 = ipa_get_parm_lattices (caller_info
, src_idx
);
1841 /* Try to propagate bits if src_lattice is bottom, but jfunc is known.
1847 Assume lattice for x is bottom, however we can still propagate
1848 result of x & 0xff == 0xff, which gets computed during ccp1 pass
1849 and we store it in jump function during analysis stage. */
1851 if (src_lats
->bits_lattice
.bottom_p ()
1853 return dest_lattice
->meet_with (jfunc
->bits
->value
, jfunc
->bits
->mask
,
1856 return dest_lattice
->meet_with (src_lats
->bits_lattice
, precision
, sgn
,
1860 else if (jfunc
->type
== IPA_JF_ANCESTOR
)
1861 return dest_lattice
->set_to_bottom ();
1862 else if (jfunc
->bits
)
1863 return dest_lattice
->meet_with (jfunc
->bits
->value
, jfunc
->bits
->mask
,
1866 return dest_lattice
->set_to_bottom ();
1869 /* Emulate effects of unary OPERATION and/or conversion from SRC_TYPE to
1870 DST_TYPE on value range in SRC_VR and store it to DST_VR. Return true if
1871 the result is a range or an anti-range. */
1874 ipa_vr_operation_and_type_effects (value_range_base
*dst_vr
,
1875 value_range_base
*src_vr
,
1876 enum tree_code operation
,
1877 tree dst_type
, tree src_type
)
1879 /* ??? We'd want to use value_range_base on the VRP workers. */
1880 value_range dst_tem
;
1881 value_range
src_tem (*src_vr
);
1882 extract_range_from_unary_expr (&dst_tem
, operation
, dst_type
,
1883 &src_tem
, src_type
);
1884 *dst_vr
= value_range_base (dst_tem
.kind (), dst_tem
.min (), dst_tem
.max ());
1885 if (dst_vr
->varying_p () || dst_vr
->undefined_p ())
1890 /* Propagate value range across jump function JFUNC that is associated with
1891 edge CS with param of callee of PARAM_TYPE and update DEST_PLATS
1895 propagate_vr_across_jump_function (cgraph_edge
*cs
, ipa_jump_func
*jfunc
,
1896 struct ipcp_param_lattices
*dest_plats
,
1899 ipcp_vr_lattice
*dest_lat
= &dest_plats
->m_value_range
;
1901 if (dest_lat
->bottom_p ())
1905 || (!INTEGRAL_TYPE_P (param_type
)
1906 && !POINTER_TYPE_P (param_type
)))
1907 return dest_lat
->set_to_bottom ();
1909 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1911 enum tree_code operation
= ipa_get_jf_pass_through_operation (jfunc
);
1913 if (TREE_CODE_CLASS (operation
) == tcc_unary
)
1915 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1916 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1917 tree operand_type
= ipa_get_type (caller_info
, src_idx
);
1918 struct ipcp_param_lattices
*src_lats
1919 = ipa_get_parm_lattices (caller_info
, src_idx
);
1921 if (src_lats
->m_value_range
.bottom_p ())
1922 return dest_lat
->set_to_bottom ();
1923 value_range_base vr
;
1924 if (ipa_vr_operation_and_type_effects (&vr
,
1925 &src_lats
->m_value_range
.m_vr
,
1926 operation
, param_type
,
1928 return dest_lat
->meet_with (&vr
);
1931 else if (jfunc
->type
== IPA_JF_CONST
)
1933 tree val
= ipa_get_jf_constant (jfunc
);
1934 if (TREE_CODE (val
) == INTEGER_CST
)
1936 val
= fold_convert (param_type
, val
);
1937 if (TREE_OVERFLOW_P (val
))
1938 val
= drop_tree_overflow (val
);
1940 value_range_base
tmpvr (VR_RANGE
, val
, val
);
1941 return dest_lat
->meet_with (&tmpvr
);
1945 value_range_base vr
;
1947 && ipa_vr_operation_and_type_effects (&vr
, jfunc
->m_vr
, NOP_EXPR
,
1949 jfunc
->m_vr
->type ()))
1950 return dest_lat
->meet_with (&vr
);
1952 return dest_lat
->set_to_bottom ();
1955 /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
1956 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
1957 other cases, return false). If there are no aggregate items, set
1958 aggs_by_ref to NEW_AGGS_BY_REF. */
1961 set_check_aggs_by_ref (struct ipcp_param_lattices
*dest_plats
,
1962 bool new_aggs_by_ref
)
1964 if (dest_plats
->aggs
)
1966 if (dest_plats
->aggs_by_ref
!= new_aggs_by_ref
)
1968 set_agg_lats_to_bottom (dest_plats
);
1973 dest_plats
->aggs_by_ref
= new_aggs_by_ref
;
1977 /* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
1978 already existing lattice for the given OFFSET and SIZE, marking all skipped
1979 lattices as containing variable and checking for overlaps. If there is no
1980 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
1981 it with offset, size and contains_variable to PRE_EXISTING, and return true,
1982 unless there are too many already. If there are two many, return false. If
1983 there are overlaps turn whole DEST_PLATS to bottom and return false. If any
1984 skipped lattices were newly marked as containing variable, set *CHANGE to
1988 merge_agg_lats_step (struct ipcp_param_lattices
*dest_plats
,
1989 HOST_WIDE_INT offset
, HOST_WIDE_INT val_size
,
1990 struct ipcp_agg_lattice
***aglat
,
1991 bool pre_existing
, bool *change
)
1993 gcc_checking_assert (offset
>= 0);
1995 while (**aglat
&& (**aglat
)->offset
< offset
)
1997 if ((**aglat
)->offset
+ (**aglat
)->size
> offset
)
1999 set_agg_lats_to_bottom (dest_plats
);
2002 *change
|= (**aglat
)->set_contains_variable ();
2003 *aglat
= &(**aglat
)->next
;
2006 if (**aglat
&& (**aglat
)->offset
== offset
)
2008 if ((**aglat
)->size
!= val_size
2010 && (**aglat
)->next
->offset
< offset
+ val_size
))
2012 set_agg_lats_to_bottom (dest_plats
);
2015 gcc_checking_assert (!(**aglat
)->next
2016 || (**aglat
)->next
->offset
>= offset
+ val_size
);
2021 struct ipcp_agg_lattice
*new_al
;
2023 if (**aglat
&& (**aglat
)->offset
< offset
+ val_size
)
2025 set_agg_lats_to_bottom (dest_plats
);
2028 if (dest_plats
->aggs_count
== PARAM_VALUE (PARAM_IPA_MAX_AGG_ITEMS
))
2030 dest_plats
->aggs_count
++;
2031 new_al
= ipcp_agg_lattice_pool
.allocate ();
2032 memset (new_al
, 0, sizeof (*new_al
));
2034 new_al
->offset
= offset
;
2035 new_al
->size
= val_size
;
2036 new_al
->contains_variable
= pre_existing
;
2038 new_al
->next
= **aglat
;
2044 /* Set all AGLAT and all other aggregate lattices reachable by next pointers as
2045 containing an unknown value. */
2048 set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice
*aglat
)
2053 ret
|= aglat
->set_contains_variable ();
2054 aglat
= aglat
->next
;
2059 /* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
2060 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source
2061 parameter used for lattice value sources. Return true if DEST_PLATS changed
2065 merge_aggregate_lattices (struct cgraph_edge
*cs
,
2066 struct ipcp_param_lattices
*dest_plats
,
2067 struct ipcp_param_lattices
*src_plats
,
2068 int src_idx
, HOST_WIDE_INT offset_delta
)
2070 bool pre_existing
= dest_plats
->aggs
!= NULL
;
2071 struct ipcp_agg_lattice
**dst_aglat
;
2074 if (set_check_aggs_by_ref (dest_plats
, src_plats
->aggs_by_ref
))
2076 if (src_plats
->aggs_bottom
)
2077 return set_agg_lats_contain_variable (dest_plats
);
2078 if (src_plats
->aggs_contain_variable
)
2079 ret
|= set_agg_lats_contain_variable (dest_plats
);
2080 dst_aglat
= &dest_plats
->aggs
;
2082 for (struct ipcp_agg_lattice
*src_aglat
= src_plats
->aggs
;
2084 src_aglat
= src_aglat
->next
)
2086 HOST_WIDE_INT new_offset
= src_aglat
->offset
- offset_delta
;
2090 if (merge_agg_lats_step (dest_plats
, new_offset
, src_aglat
->size
,
2091 &dst_aglat
, pre_existing
, &ret
))
2093 struct ipcp_agg_lattice
*new_al
= *dst_aglat
;
2095 dst_aglat
= &(*dst_aglat
)->next
;
2096 if (src_aglat
->bottom
)
2098 ret
|= new_al
->set_contains_variable ();
2101 if (src_aglat
->contains_variable
)
2102 ret
|= new_al
->set_contains_variable ();
2103 for (ipcp_value
<tree
> *val
= src_aglat
->values
;
2106 ret
|= new_al
->add_value (val
->value
, cs
, val
, src_idx
,
2109 else if (dest_plats
->aggs_bottom
)
2112 ret
|= set_chain_of_aglats_contains_variable (*dst_aglat
);
2116 /* Determine whether there is anything to propagate FROM SRC_PLATS through a
2117 pass-through JFUNC and if so, whether it has conform and conforms to the
2118 rules about propagating values passed by reference. */
2121 agg_pass_through_permissible_p (struct ipcp_param_lattices
*src_plats
,
2122 struct ipa_jump_func
*jfunc
)
2124 return src_plats
->aggs
2125 && (!src_plats
->aggs_by_ref
2126 || ipa_get_jf_pass_through_agg_preserved (jfunc
));
2129 /* Propagate scalar values across jump function JFUNC that is associated with
2130 edge CS and put the values into DEST_LAT. */
2133 propagate_aggs_across_jump_function (struct cgraph_edge
*cs
,
2134 struct ipa_jump_func
*jfunc
,
2135 struct ipcp_param_lattices
*dest_plats
)
2139 if (dest_plats
->aggs_bottom
)
2142 if (jfunc
->type
== IPA_JF_PASS_THROUGH
2143 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
2145 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2146 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
2147 struct ipcp_param_lattices
*src_plats
;
2149 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2150 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
2152 /* Currently we do not produce clobber aggregate jump
2153 functions, replace with merging when we do. */
2154 gcc_assert (!jfunc
->agg
.items
);
2155 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
,
2159 ret
|= set_agg_lats_contain_variable (dest_plats
);
2161 else if (jfunc
->type
== IPA_JF_ANCESTOR
2162 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
2164 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2165 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
2166 struct ipcp_param_lattices
*src_plats
;
2168 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2169 if (src_plats
->aggs
&& src_plats
->aggs_by_ref
)
2171 /* Currently we do not produce clobber aggregate jump
2172 functions, replace with merging when we do. */
2173 gcc_assert (!jfunc
->agg
.items
);
2174 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
, src_idx
,
2175 ipa_get_jf_ancestor_offset (jfunc
));
2177 else if (!src_plats
->aggs_by_ref
)
2178 ret
|= set_agg_lats_to_bottom (dest_plats
);
2180 ret
|= set_agg_lats_contain_variable (dest_plats
);
2182 else if (jfunc
->agg
.items
)
2184 bool pre_existing
= dest_plats
->aggs
!= NULL
;
2185 struct ipcp_agg_lattice
**aglat
= &dest_plats
->aggs
;
2186 struct ipa_agg_jf_item
*item
;
2189 if (set_check_aggs_by_ref (dest_plats
, jfunc
->agg
.by_ref
))
2192 FOR_EACH_VEC_ELT (*jfunc
->agg
.items
, i
, item
)
2194 HOST_WIDE_INT val_size
;
2196 if (item
->offset
< 0)
2198 gcc_checking_assert (is_gimple_ip_invariant (item
->value
));
2199 val_size
= tree_to_uhwi (TYPE_SIZE (TREE_TYPE (item
->value
)));
2201 if (merge_agg_lats_step (dest_plats
, item
->offset
, val_size
,
2202 &aglat
, pre_existing
, &ret
))
2204 ret
|= (*aglat
)->add_value (item
->value
, cs
, NULL
, 0, 0);
2205 aglat
= &(*aglat
)->next
;
2207 else if (dest_plats
->aggs_bottom
)
2211 ret
|= set_chain_of_aglats_contains_variable (*aglat
);
2214 ret
|= set_agg_lats_contain_variable (dest_plats
);
2219 /* Return true if on the way cfrom CS->caller to the final (non-alias and
2220 non-thunk) destination, the call passes through a thunk. */
2223 call_passes_through_thunk_p (cgraph_edge
*cs
)
2225 cgraph_node
*alias_or_thunk
= cs
->callee
;
2226 while (alias_or_thunk
->alias
)
2227 alias_or_thunk
= alias_or_thunk
->get_alias_target ();
2228 return alias_or_thunk
->thunk
.thunk_p
;
2231 /* Propagate constants from the caller to the callee of CS. INFO describes the
2235 propagate_constants_across_call (struct cgraph_edge
*cs
)
2237 struct ipa_node_params
*callee_info
;
2238 enum availability availability
;
2239 cgraph_node
*callee
;
2240 struct ipa_edge_args
*args
;
2242 int i
, args_count
, parms_count
;
2244 callee
= cs
->callee
->function_symbol (&availability
);
2245 if (!callee
->definition
)
2247 gcc_checking_assert (callee
->has_gimple_body_p ());
2248 callee_info
= IPA_NODE_REF (callee
);
2250 args
= IPA_EDGE_REF (cs
);
2251 args_count
= ipa_get_cs_argument_count (args
);
2252 parms_count
= ipa_get_param_count (callee_info
);
2253 if (parms_count
== 0)
2256 /* If this call goes through a thunk we must not propagate to the first (0th)
2257 parameter. However, we might need to uncover a thunk from below a series
2258 of aliases first. */
2259 if (call_passes_through_thunk_p (cs
))
2261 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
2268 for (; (i
< args_count
) && (i
< parms_count
); i
++)
2270 struct ipa_jump_func
*jump_func
= ipa_get_ith_jump_func (args
, i
);
2271 struct ipcp_param_lattices
*dest_plats
;
2272 tree param_type
= ipa_get_type (callee_info
, i
);
2274 dest_plats
= ipa_get_parm_lattices (callee_info
, i
);
2275 if (availability
== AVAIL_INTERPOSABLE
)
2276 ret
|= set_all_contains_variable (dest_plats
);
2279 ret
|= propagate_scalar_across_jump_function (cs
, jump_func
,
2280 &dest_plats
->itself
,
2282 ret
|= propagate_context_across_jump_function (cs
, jump_func
, i
,
2283 &dest_plats
->ctxlat
);
2285 |= propagate_bits_across_jump_function (cs
, i
, jump_func
,
2286 &dest_plats
->bits_lattice
);
2287 ret
|= propagate_aggs_across_jump_function (cs
, jump_func
,
2289 if (opt_for_fn (callee
->decl
, flag_ipa_vrp
))
2290 ret
|= propagate_vr_across_jump_function (cs
, jump_func
,
2291 dest_plats
, param_type
);
2293 ret
|= dest_plats
->m_value_range
.set_to_bottom ();
2296 for (; i
< parms_count
; i
++)
2297 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
, i
));
2302 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
2303 KNOWN_CONTEXTS, KNOWN_AGGS or AGG_REPS return the destination. The latter
2304 three can be NULL. If AGG_REPS is not NULL, KNOWN_AGGS is ignored. */
2307 ipa_get_indirect_edge_target_1 (struct cgraph_edge
*ie
,
2308 vec
<tree
> known_csts
,
2309 vec
<ipa_polymorphic_call_context
> known_contexts
,
2310 vec
<ipa_agg_jump_function_p
> known_aggs
,
2311 struct ipa_agg_replacement_value
*agg_reps
,
2314 int param_index
= ie
->indirect_info
->param_index
;
2315 HOST_WIDE_INT anc_offset
;
2319 *speculative
= false;
2321 if (param_index
== -1
2322 || known_csts
.length () <= (unsigned int) param_index
)
2325 if (!ie
->indirect_info
->polymorphic
)
2329 if (ie
->indirect_info
->agg_contents
)
2332 if (agg_reps
&& ie
->indirect_info
->guaranteed_unmodified
)
2336 if (agg_reps
->index
== param_index
2337 && agg_reps
->offset
== ie
->indirect_info
->offset
2338 && agg_reps
->by_ref
== ie
->indirect_info
->by_ref
)
2340 t
= agg_reps
->value
;
2343 agg_reps
= agg_reps
->next
;
2348 struct ipa_agg_jump_function
*agg
;
2349 if (known_aggs
.length () > (unsigned int) param_index
)
2350 agg
= known_aggs
[param_index
];
2353 bool from_global_constant
;
2354 t
= ipa_find_agg_cst_for_param (agg
, known_csts
[param_index
],
2355 ie
->indirect_info
->offset
,
2356 ie
->indirect_info
->by_ref
,
2357 &from_global_constant
);
2359 && !from_global_constant
2360 && !ie
->indirect_info
->guaranteed_unmodified
)
2365 t
= known_csts
[param_index
];
2368 && TREE_CODE (t
) == ADDR_EXPR
2369 && TREE_CODE (TREE_OPERAND (t
, 0)) == FUNCTION_DECL
)
2370 return TREE_OPERAND (t
, 0);
2375 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize
))
2378 gcc_assert (!ie
->indirect_info
->agg_contents
);
2379 anc_offset
= ie
->indirect_info
->offset
;
2383 /* Try to work out value of virtual table pointer value in replacemnets. */
2384 if (!t
&& agg_reps
&& !ie
->indirect_info
->by_ref
)
2388 if (agg_reps
->index
== param_index
2389 && agg_reps
->offset
== ie
->indirect_info
->offset
2390 && agg_reps
->by_ref
)
2392 t
= agg_reps
->value
;
2395 agg_reps
= agg_reps
->next
;
2399 /* Try to work out value of virtual table pointer value in known
2400 aggregate values. */
2401 if (!t
&& known_aggs
.length () > (unsigned int) param_index
2402 && !ie
->indirect_info
->by_ref
)
2404 struct ipa_agg_jump_function
*agg
;
2405 agg
= known_aggs
[param_index
];
2406 t
= ipa_find_agg_cst_for_param (agg
, known_csts
[param_index
],
2407 ie
->indirect_info
->offset
, true);
2410 /* If we found the virtual table pointer, lookup the target. */
2414 unsigned HOST_WIDE_INT offset
;
2415 if (vtable_pointer_value_to_vtable (t
, &vtable
, &offset
))
2418 target
= gimple_get_virt_method_for_vtable (ie
->indirect_info
->otr_token
,
2419 vtable
, offset
, &can_refer
);
2423 || (TREE_CODE (TREE_TYPE (target
)) == FUNCTION_TYPE
2424 && DECL_FUNCTION_CODE (target
) == BUILT_IN_UNREACHABLE
)
2425 || !possible_polymorphic_call_target_p
2426 (ie
, cgraph_node::get (target
)))
2428 /* Do not speculate builtin_unreachable, it is stupid! */
2429 if (ie
->indirect_info
->vptr_changed
)
2431 target
= ipa_impossible_devirt_target (ie
, target
);
2433 *speculative
= ie
->indirect_info
->vptr_changed
;
2440 /* Do we know the constant value of pointer? */
2442 t
= known_csts
[param_index
];
2444 gcc_checking_assert (!t
|| TREE_CODE (t
) != TREE_BINFO
);
2446 ipa_polymorphic_call_context context
;
2447 if (known_contexts
.length () > (unsigned int) param_index
)
2449 context
= known_contexts
[param_index
];
2450 context
.offset_by (anc_offset
);
2451 if (ie
->indirect_info
->vptr_changed
)
2452 context
.possible_dynamic_type_change (ie
->in_polymorphic_cdtor
,
2453 ie
->indirect_info
->otr_type
);
2456 ipa_polymorphic_call_context ctx2
= ipa_polymorphic_call_context
2457 (t
, ie
->indirect_info
->otr_type
, anc_offset
);
2458 if (!ctx2
.useless_p ())
2459 context
.combine_with (ctx2
, ie
->indirect_info
->otr_type
);
2464 context
= ipa_polymorphic_call_context (t
, ie
->indirect_info
->otr_type
,
2466 if (ie
->indirect_info
->vptr_changed
)
2467 context
.possible_dynamic_type_change (ie
->in_polymorphic_cdtor
,
2468 ie
->indirect_info
->otr_type
);
2473 vec
<cgraph_node
*>targets
;
2476 targets
= possible_polymorphic_call_targets
2477 (ie
->indirect_info
->otr_type
,
2478 ie
->indirect_info
->otr_token
,
2480 if (!final
|| targets
.length () > 1)
2482 struct cgraph_node
*node
;
2485 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize_speculatively
)
2486 || ie
->speculative
|| !ie
->maybe_hot_p ())
2488 node
= try_speculative_devirtualization (ie
->indirect_info
->otr_type
,
2489 ie
->indirect_info
->otr_token
,
2493 *speculative
= true;
2494 target
= node
->decl
;
2501 *speculative
= false;
2502 if (targets
.length () == 1)
2503 target
= targets
[0]->decl
;
2505 target
= ipa_impossible_devirt_target (ie
, NULL_TREE
);
2508 if (target
&& !possible_polymorphic_call_target_p (ie
,
2509 cgraph_node::get (target
)))
2513 target
= ipa_impossible_devirt_target (ie
, target
);
2520 /* If an indirect edge IE can be turned into a direct one based on KNOWN_CSTS,
2521 KNOWN_CONTEXTS (which can be vNULL) or KNOWN_AGGS (which also can be vNULL)
2522 return the destination. */
2525 ipa_get_indirect_edge_target (struct cgraph_edge
*ie
,
2526 vec
<tree
> known_csts
,
2527 vec
<ipa_polymorphic_call_context
> known_contexts
,
2528 vec
<ipa_agg_jump_function_p
> known_aggs
,
2531 return ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
2532 known_aggs
, NULL
, speculative
);
2535 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
2536 and KNOWN_CONTEXTS. */
2539 devirtualization_time_bonus (struct cgraph_node
*node
,
2540 vec
<tree
> known_csts
,
2541 vec
<ipa_polymorphic_call_context
> known_contexts
,
2542 vec
<ipa_agg_jump_function_p
> known_aggs
)
2544 struct cgraph_edge
*ie
;
2547 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
2549 struct cgraph_node
*callee
;
2550 struct ipa_fn_summary
*isummary
;
2551 enum availability avail
;
2555 target
= ipa_get_indirect_edge_target (ie
, known_csts
, known_contexts
,
2556 known_aggs
, &speculative
);
2560 /* Only bare minimum benefit for clearly un-inlineable targets. */
2562 callee
= cgraph_node::get (target
);
2563 if (!callee
|| !callee
->definition
)
2565 callee
= callee
->function_symbol (&avail
);
2566 if (avail
< AVAIL_AVAILABLE
)
2568 isummary
= ipa_fn_summaries
->get (callee
);
2569 if (!isummary
->inlinable
)
2572 /* FIXME: The values below need re-considering and perhaps also
2573 integrating into the cost metrics, at lest in some very basic way. */
2574 if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 4)
2575 res
+= 31 / ((int)speculative
+ 1);
2576 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 2)
2577 res
+= 15 / ((int)speculative
+ 1);
2578 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
2579 || DECL_DECLARED_INLINE_P (callee
->decl
))
2580 res
+= 7 / ((int)speculative
+ 1);
2586 /* Return time bonus incurred because of HINTS. */
2589 hint_time_bonus (ipa_hints hints
)
2592 if (hints
& (INLINE_HINT_loop_iterations
| INLINE_HINT_loop_stride
))
2593 result
+= PARAM_VALUE (PARAM_IPA_CP_LOOP_HINT_BONUS
);
2594 if (hints
& INLINE_HINT_array_index
)
2595 result
+= PARAM_VALUE (PARAM_IPA_CP_ARRAY_INDEX_HINT_BONUS
);
2599 /* If there is a reason to penalize the function described by INFO in the
2600 cloning goodness evaluation, do so. */
2602 static inline int64_t
2603 incorporate_penalties (ipa_node_params
*info
, int64_t evaluation
)
2605 if (info
->node_within_scc
)
2606 evaluation
= (evaluation
2607 * (100 - PARAM_VALUE (PARAM_IPA_CP_RECURSION_PENALTY
))) / 100;
2609 if (info
->node_calling_single_call
)
2610 evaluation
= (evaluation
2611 * (100 - PARAM_VALUE (PARAM_IPA_CP_SINGLE_CALL_PENALTY
)))
2617 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
2618 and SIZE_COST and with the sum of frequencies of incoming edges to the
2619 potential new clone in FREQUENCIES. */
2622 good_cloning_opportunity_p (struct cgraph_node
*node
, int time_benefit
,
2623 int freq_sum
, profile_count count_sum
, int size_cost
)
2625 if (time_benefit
== 0
2626 || !opt_for_fn (node
->decl
, flag_ipa_cp_clone
)
2627 || node
->optimize_for_size_p ())
2630 gcc_assert (size_cost
> 0);
2632 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2633 if (max_count
> profile_count::zero ())
2635 int factor
= RDIV (count_sum
.probability_in
2636 (max_count
).to_reg_br_prob_base ()
2637 * 1000, REG_BR_PROB_BASE
);
2638 int64_t evaluation
= (((int64_t) time_benefit
* factor
)
2640 evaluation
= incorporate_penalties (info
, evaluation
);
2642 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2644 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
2645 "size: %i, count_sum: ", time_benefit
, size_cost
);
2646 count_sum
.dump (dump_file
);
2647 fprintf (dump_file
, "%s%s) -> evaluation: " "%" PRId64
2648 ", threshold: %i\n",
2649 info
->node_within_scc
? ", scc" : "",
2650 info
->node_calling_single_call
? ", single_call" : "",
2651 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
2654 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
2658 int64_t evaluation
= (((int64_t) time_benefit
* freq_sum
)
2660 evaluation
= incorporate_penalties (info
, evaluation
);
2662 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2663 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
2664 "size: %i, freq_sum: %i%s%s) -> evaluation: "
2665 "%" PRId64
", threshold: %i\n",
2666 time_benefit
, size_cost
, freq_sum
,
2667 info
->node_within_scc
? ", scc" : "",
2668 info
->node_calling_single_call
? ", single_call" : "",
2669 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
2671 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
2675 /* Return all context independent values from aggregate lattices in PLATS in a
2676 vector. Return NULL if there are none. */
2678 static vec
<ipa_agg_jf_item
, va_gc
> *
2679 context_independent_aggregate_values (struct ipcp_param_lattices
*plats
)
2681 vec
<ipa_agg_jf_item
, va_gc
> *res
= NULL
;
2683 if (plats
->aggs_bottom
2684 || plats
->aggs_contain_variable
2685 || plats
->aggs_count
== 0)
2688 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
;
2690 aglat
= aglat
->next
)
2691 if (aglat
->is_single_const ())
2693 struct ipa_agg_jf_item item
;
2694 item
.offset
= aglat
->offset
;
2695 item
.value
= aglat
->values
->value
;
2696 vec_safe_push (res
, item
);
2701 /* Allocate KNOWN_CSTS, KNOWN_CONTEXTS and, if non-NULL, KNOWN_AGGS and
2702 populate them with values of parameters that are known independent of the
2703 context. INFO describes the function. If REMOVABLE_PARAMS_COST is
2704 non-NULL, the movement cost of all removable parameters will be stored in
2708 gather_context_independent_values (struct ipa_node_params
*info
,
2709 vec
<tree
> *known_csts
,
2710 vec
<ipa_polymorphic_call_context
>
2712 vec
<ipa_agg_jump_function
> *known_aggs
,
2713 int *removable_params_cost
)
2715 int i
, count
= ipa_get_param_count (info
);
2718 known_csts
->create (0);
2719 known_contexts
->create (0);
2720 known_csts
->safe_grow_cleared (count
);
2721 known_contexts
->safe_grow_cleared (count
);
2724 known_aggs
->create (0);
2725 known_aggs
->safe_grow_cleared (count
);
2728 if (removable_params_cost
)
2729 *removable_params_cost
= 0;
2731 for (i
= 0; i
< count
; i
++)
2733 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2734 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
2736 if (lat
->is_single_const ())
2738 ipcp_value
<tree
> *val
= lat
->values
;
2739 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
2740 (*known_csts
)[i
] = val
->value
;
2741 if (removable_params_cost
)
2742 *removable_params_cost
2743 += estimate_move_cost (TREE_TYPE (val
->value
), false);
2746 else if (removable_params_cost
2747 && !ipa_is_param_used (info
, i
))
2748 *removable_params_cost
2749 += ipa_get_param_move_cost (info
, i
);
2751 if (!ipa_is_param_used (info
, i
))
2754 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
2755 /* Do not account known context as reason for cloning. We can see
2756 if it permits devirtualization. */
2757 if (ctxlat
->is_single_const ())
2758 (*known_contexts
)[i
] = ctxlat
->values
->value
;
2762 vec
<ipa_agg_jf_item
, va_gc
> *agg_items
;
2763 struct ipa_agg_jump_function
*ajf
;
2765 agg_items
= context_independent_aggregate_values (plats
);
2766 ajf
= &(*known_aggs
)[i
];
2767 ajf
->items
= agg_items
;
2768 ajf
->by_ref
= plats
->aggs_by_ref
;
2769 ret
|= agg_items
!= NULL
;
2776 /* The current interface in ipa-inline-analysis requires a pointer vector.
2779 FIXME: That interface should be re-worked, this is slightly silly. Still,
2780 I'd like to discuss how to change it first and this demonstrates the
2783 static vec
<ipa_agg_jump_function_p
>
2784 agg_jmp_p_vec_for_t_vec (vec
<ipa_agg_jump_function
> known_aggs
)
2786 vec
<ipa_agg_jump_function_p
> ret
;
2787 struct ipa_agg_jump_function
*ajf
;
2790 ret
.create (known_aggs
.length ());
2791 FOR_EACH_VEC_ELT (known_aggs
, i
, ajf
)
2792 ret
.quick_push (ajf
);
2796 /* Perform time and size measurement of NODE with the context given in
2797 KNOWN_CSTS, KNOWN_CONTEXTS and KNOWN_AGGS, calculate the benefit and cost
2798 given BASE_TIME of the node without specialization, REMOVABLE_PARAMS_COST of
2799 all context-independent removable parameters and EST_MOVE_COST of estimated
2800 movement of the considered parameter and store it into VAL. */
2803 perform_estimation_of_a_value (cgraph_node
*node
, vec
<tree
> known_csts
,
2804 vec
<ipa_polymorphic_call_context
> known_contexts
,
2805 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
,
2806 int removable_params_cost
,
2807 int est_move_cost
, ipcp_value_base
*val
)
2809 int size
, time_benefit
;
2810 sreal time
, base_time
;
2813 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
2814 known_aggs_ptrs
, &size
, &time
,
2815 &base_time
, &hints
);
2817 if (base_time
> 65535)
2819 time_benefit
= base_time
.to_int ()
2820 + devirtualization_time_bonus (node
, known_csts
, known_contexts
,
2822 + hint_time_bonus (hints
)
2823 + removable_params_cost
+ est_move_cost
;
2825 gcc_checking_assert (size
>=0);
2826 /* The inliner-heuristics based estimates may think that in certain
2827 contexts some functions do not have any size at all but we want
2828 all specializations to have at least a tiny cost, not least not to
2833 val
->local_time_benefit
= time_benefit
;
2834 val
->local_size_cost
= size
;
2837 /* Iterate over known values of parameters of NODE and estimate the local
2838 effects in terms of time and size they have. */
2841 estimate_local_effects (struct cgraph_node
*node
)
2843 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2844 int i
, count
= ipa_get_param_count (info
);
2845 vec
<tree
> known_csts
;
2846 vec
<ipa_polymorphic_call_context
> known_contexts
;
2847 vec
<ipa_agg_jump_function
> known_aggs
;
2848 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
;
2850 int removable_params_cost
;
2852 if (!count
|| !ipcp_versionable_function_p (node
))
2855 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2856 fprintf (dump_file
, "\nEstimating effects for %s.\n", node
->dump_name ());
2858 always_const
= gather_context_independent_values (info
, &known_csts
,
2859 &known_contexts
, &known_aggs
,
2860 &removable_params_cost
);
2861 known_aggs_ptrs
= agg_jmp_p_vec_for_t_vec (known_aggs
);
2862 int devirt_bonus
= devirtualization_time_bonus (node
, known_csts
,
2863 known_contexts
, known_aggs_ptrs
);
2864 if (always_const
|| devirt_bonus
2865 || (removable_params_cost
&& node
->local
.can_change_signature
))
2867 struct caller_statistics stats
;
2869 sreal time
, base_time
;
2872 init_caller_stats (&stats
);
2873 node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
2875 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
2876 known_aggs_ptrs
, &size
, &time
,
2877 &base_time
, &hints
);
2878 time
-= devirt_bonus
;
2879 time
-= hint_time_bonus (hints
);
2880 time
-= removable_params_cost
;
2881 size
-= stats
.n_calls
* removable_params_cost
;
2884 fprintf (dump_file
, " - context independent values, size: %i, "
2885 "time_benefit: %f\n", size
, (base_time
- time
).to_double ());
2887 if (size
<= 0 || node
->local
.local
)
2889 info
->do_clone_for_all_contexts
= true;
2892 fprintf (dump_file
, " Decided to specialize for all "
2893 "known contexts, code not going to grow.\n");
2895 else if (good_cloning_opportunity_p (node
,
2896 MIN ((base_time
- time
).to_int (),
2898 stats
.freq_sum
, stats
.count_sum
,
2901 if (size
+ overall_size
<= max_new_size
)
2903 info
->do_clone_for_all_contexts
= true;
2904 overall_size
+= size
;
2907 fprintf (dump_file
, " Decided to specialize for all "
2908 "known contexts, growth deemed beneficial.\n");
2910 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2911 fprintf (dump_file
, " Not cloning for all contexts because "
2912 "max_new_size would be reached with %li.\n",
2913 size
+ overall_size
);
2915 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2916 fprintf (dump_file
, " Not cloning for all contexts because "
2917 "!good_cloning_opportunity_p.\n");
2921 for (i
= 0; i
< count
; i
++)
2923 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2924 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
2925 ipcp_value
<tree
> *val
;
2932 for (val
= lat
->values
; val
; val
= val
->next
)
2934 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
2935 known_csts
[i
] = val
->value
;
2937 int emc
= estimate_move_cost (TREE_TYPE (val
->value
), true);
2938 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
2940 removable_params_cost
, emc
, val
);
2942 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2944 fprintf (dump_file
, " - estimates for value ");
2945 print_ipcp_constant_value (dump_file
, val
->value
);
2946 fprintf (dump_file
, " for ");
2947 ipa_dump_param (dump_file
, info
, i
);
2948 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
2949 val
->local_time_benefit
, val
->local_size_cost
);
2952 known_csts
[i
] = NULL_TREE
;
2955 for (i
= 0; i
< count
; i
++)
2957 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2959 if (!plats
->virt_call
)
2962 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
2963 ipcp_value
<ipa_polymorphic_call_context
> *val
;
2967 || !known_contexts
[i
].useless_p ())
2970 for (val
= ctxlat
->values
; val
; val
= val
->next
)
2972 known_contexts
[i
] = val
->value
;
2973 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
2975 removable_params_cost
, 0, val
);
2977 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2979 fprintf (dump_file
, " - estimates for polymorphic context ");
2980 print_ipcp_constant_value (dump_file
, val
->value
);
2981 fprintf (dump_file
, " for ");
2982 ipa_dump_param (dump_file
, info
, i
);
2983 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
2984 val
->local_time_benefit
, val
->local_size_cost
);
2987 known_contexts
[i
] = ipa_polymorphic_call_context ();
2990 for (i
= 0; i
< count
; i
++)
2992 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2993 struct ipa_agg_jump_function
*ajf
;
2994 struct ipcp_agg_lattice
*aglat
;
2996 if (plats
->aggs_bottom
|| !plats
->aggs
)
2999 ajf
= &known_aggs
[i
];
3000 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3002 ipcp_value
<tree
> *val
;
3003 if (aglat
->bottom
|| !aglat
->values
3004 /* If the following is true, the one value is in known_aggs. */
3005 || (!plats
->aggs_contain_variable
3006 && aglat
->is_single_const ()))
3009 for (val
= aglat
->values
; val
; val
= val
->next
)
3011 struct ipa_agg_jf_item item
;
3013 item
.offset
= aglat
->offset
;
3014 item
.value
= val
->value
;
3015 vec_safe_push (ajf
->items
, item
);
3017 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
3019 removable_params_cost
, 0, val
);
3021 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3023 fprintf (dump_file
, " - estimates for value ");
3024 print_ipcp_constant_value (dump_file
, val
->value
);
3025 fprintf (dump_file
, " for ");
3026 ipa_dump_param (dump_file
, info
, i
);
3027 fprintf (dump_file
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
3028 "]: time_benefit: %i, size: %i\n",
3029 plats
->aggs_by_ref
? "ref " : "",
3031 val
->local_time_benefit
, val
->local_size_cost
);
3039 for (i
= 0; i
< count
; i
++)
3040 vec_free (known_aggs
[i
].items
);
3042 known_csts
.release ();
3043 known_contexts
.release ();
3044 known_aggs
.release ();
3045 known_aggs_ptrs
.release ();
3049 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
3050 topological sort of values. */
3052 template <typename valtype
>
3054 value_topo_info
<valtype
>::add_val (ipcp_value
<valtype
> *cur_val
)
3056 ipcp_value_source
<valtype
> *src
;
3062 cur_val
->dfs
= dfs_counter
;
3063 cur_val
->low_link
= dfs_counter
;
3065 cur_val
->topo_next
= stack
;
3067 cur_val
->on_stack
= true;
3069 for (src
= cur_val
->sources
; src
; src
= src
->next
)
3072 if (src
->val
->dfs
== 0)
3075 if (src
->val
->low_link
< cur_val
->low_link
)
3076 cur_val
->low_link
= src
->val
->low_link
;
3078 else if (src
->val
->on_stack
3079 && src
->val
->dfs
< cur_val
->low_link
)
3080 cur_val
->low_link
= src
->val
->dfs
;
3083 if (cur_val
->dfs
== cur_val
->low_link
)
3085 ipcp_value
<valtype
> *v
, *scc_list
= NULL
;
3090 stack
= v
->topo_next
;
3091 v
->on_stack
= false;
3093 v
->scc_next
= scc_list
;
3096 while (v
!= cur_val
);
3098 cur_val
->topo_next
= values_topo
;
3099 values_topo
= cur_val
;
3103 /* Add all values in lattices associated with NODE to the topological sort if
3104 they are not there yet. */
3107 add_all_node_vals_to_toposort (cgraph_node
*node
, ipa_topo_info
*topo
)
3109 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3110 int i
, count
= ipa_get_param_count (info
);
3112 for (i
= 0; i
< count
; i
++)
3114 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3115 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
3116 struct ipcp_agg_lattice
*aglat
;
3120 ipcp_value
<tree
> *val
;
3121 for (val
= lat
->values
; val
; val
= val
->next
)
3122 topo
->constants
.add_val (val
);
3125 if (!plats
->aggs_bottom
)
3126 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3129 ipcp_value
<tree
> *val
;
3130 for (val
= aglat
->values
; val
; val
= val
->next
)
3131 topo
->constants
.add_val (val
);
3134 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
3135 if (!ctxlat
->bottom
)
3137 ipcp_value
<ipa_polymorphic_call_context
> *ctxval
;
3138 for (ctxval
= ctxlat
->values
; ctxval
; ctxval
= ctxval
->next
)
3139 topo
->contexts
.add_val (ctxval
);
3144 /* One pass of constants propagation along the call graph edges, from callers
3145 to callees (requires topological ordering in TOPO), iterate over strongly
3146 connected components. */
3149 propagate_constants_topo (struct ipa_topo_info
*topo
)
3153 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
3156 struct cgraph_node
*v
, *node
= topo
->order
[i
];
3157 vec
<cgraph_node
*> cycle_nodes
= ipa_get_nodes_in_cycle (node
);
3159 /* First, iteratively propagate within the strongly connected component
3160 until all lattices stabilize. */
3161 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
3162 if (v
->has_gimple_body_p ())
3163 push_node_to_stack (topo
, v
);
3165 v
= pop_node_from_stack (topo
);
3168 struct cgraph_edge
*cs
;
3170 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3171 if (ipa_edge_within_scc (cs
))
3173 IPA_NODE_REF (v
)->node_within_scc
= true;
3174 if (propagate_constants_across_call (cs
))
3175 push_node_to_stack (topo
, cs
->callee
->function_symbol ());
3177 v
= pop_node_from_stack (topo
);
3180 /* Afterwards, propagate along edges leading out of the SCC, calculates
3181 the local effects of the discovered constants and all valid values to
3182 their topological sort. */
3183 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
3184 if (v
->has_gimple_body_p ())
3186 struct cgraph_edge
*cs
;
3188 estimate_local_effects (v
);
3189 add_all_node_vals_to_toposort (v
, topo
);
3190 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3191 if (!ipa_edge_within_scc (cs
))
3192 propagate_constants_across_call (cs
);
3194 cycle_nodes
.release ();
3199 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
3200 the bigger one if otherwise. */
3203 safe_add (int a
, int b
)
3205 if (a
> INT_MAX
/2 || b
> INT_MAX
/2)
3206 return a
> b
? a
: b
;
3212 /* Propagate the estimated effects of individual values along the topological
3213 from the dependent values to those they depend on. */
3215 template <typename valtype
>
3217 value_topo_info
<valtype
>::propagate_effects ()
3219 ipcp_value
<valtype
> *base
;
3221 for (base
= values_topo
; base
; base
= base
->topo_next
)
3223 ipcp_value_source
<valtype
> *src
;
3224 ipcp_value
<valtype
> *val
;
3225 int time
= 0, size
= 0;
3227 for (val
= base
; val
; val
= val
->scc_next
)
3229 time
= safe_add (time
,
3230 val
->local_time_benefit
+ val
->prop_time_benefit
);
3231 size
= safe_add (size
, val
->local_size_cost
+ val
->prop_size_cost
);
3234 for (val
= base
; val
; val
= val
->scc_next
)
3235 for (src
= val
->sources
; src
; src
= src
->next
)
3237 && src
->cs
->maybe_hot_p ())
3239 src
->val
->prop_time_benefit
= safe_add (time
,
3240 src
->val
->prop_time_benefit
);
3241 src
->val
->prop_size_cost
= safe_add (size
,
3242 src
->val
->prop_size_cost
);
3248 /* Propagate constants, polymorphic contexts and their effects from the
3249 summaries interprocedurally. */
3252 ipcp_propagate_stage (struct ipa_topo_info
*topo
)
3254 struct cgraph_node
*node
;
3257 fprintf (dump_file
, "\n Propagating constants:\n\n");
3259 max_count
= profile_count::uninitialized ();
3261 FOR_EACH_DEFINED_FUNCTION (node
)
3263 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3265 determine_versionability (node
, info
);
3266 if (node
->has_gimple_body_p ())
3268 info
->lattices
= XCNEWVEC (struct ipcp_param_lattices
,
3269 ipa_get_param_count (info
));
3270 initialize_node_lattices (node
);
3272 ipa_fn_summary
*s
= ipa_fn_summaries
->get (node
);
3273 if (node
->definition
&& !node
->alias
&& s
!= NULL
)
3274 overall_size
+= s
->self_size
;
3275 max_count
= max_count
.max (node
->count
.ipa ());
3278 max_new_size
= overall_size
;
3279 if (max_new_size
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
3280 max_new_size
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
3281 max_new_size
+= max_new_size
* PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH
) / 100 + 1;
3284 fprintf (dump_file
, "\noverall_size: %li, max_new_size: %li\n",
3285 overall_size
, max_new_size
);
3287 propagate_constants_topo (topo
);
3289 ipcp_verify_propagated_values ();
3290 topo
->constants
.propagate_effects ();
3291 topo
->contexts
.propagate_effects ();
3295 fprintf (dump_file
, "\nIPA lattices after all propagation:\n");
3296 print_all_lattices (dump_file
, (dump_flags
& TDF_DETAILS
), true);
3300 /* Discover newly direct outgoing edges from NODE which is a new clone with
3301 known KNOWN_CSTS and make them direct. */
3304 ipcp_discover_new_direct_edges (struct cgraph_node
*node
,
3305 vec
<tree
> known_csts
,
3306 vec
<ipa_polymorphic_call_context
>
3308 struct ipa_agg_replacement_value
*aggvals
)
3310 struct cgraph_edge
*ie
, *next_ie
;
3313 for (ie
= node
->indirect_calls
; ie
; ie
= next_ie
)
3318 next_ie
= ie
->next_callee
;
3319 target
= ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
3320 vNULL
, aggvals
, &speculative
);
3323 bool agg_contents
= ie
->indirect_info
->agg_contents
;
3324 bool polymorphic
= ie
->indirect_info
->polymorphic
;
3325 int param_index
= ie
->indirect_info
->param_index
;
3326 struct cgraph_edge
*cs
= ipa_make_edge_direct_to_target (ie
, target
,
3330 if (cs
&& !agg_contents
&& !polymorphic
)
3332 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3333 int c
= ipa_get_controlled_uses (info
, param_index
);
3334 if (c
!= IPA_UNDESCRIBED_USE
)
3336 struct ipa_ref
*to_del
;
3339 ipa_set_controlled_uses (info
, param_index
, c
);
3340 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3341 fprintf (dump_file
, " controlled uses count of param "
3342 "%i bumped down to %i\n", param_index
, c
);
3344 && (to_del
= node
->find_reference (cs
->callee
, NULL
, 0)))
3346 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3347 fprintf (dump_file
, " and even removing its "
3348 "cloning-created reference\n");
3349 to_del
->remove_reference ();
3355 /* Turning calls to direct calls will improve overall summary. */
3357 ipa_update_overall_fn_summary (node
);
3360 class edge_clone_summary
;
3361 static call_summary
<edge_clone_summary
*> *edge_clone_summaries
= NULL
;
3363 /* Edge clone summary. */
3365 struct edge_clone_summary
3367 /* Default constructor. */
3368 edge_clone_summary (): prev_clone (NULL
), next_clone (NULL
) {}
3370 /* Default destructor. */
3371 ~edge_clone_summary ()
3374 edge_clone_summaries
->get (prev_clone
)->next_clone
= next_clone
;
3376 edge_clone_summaries
->get (next_clone
)->prev_clone
= prev_clone
;
3379 cgraph_edge
*prev_clone
;
3380 cgraph_edge
*next_clone
;
3383 class edge_clone_summary_t
:
3384 public call_summary
<edge_clone_summary
*>
3387 edge_clone_summary_t (symbol_table
*symtab
):
3388 call_summary
<edge_clone_summary
*> (symtab
)
3390 m_initialize_when_cloning
= true;
3393 virtual void duplicate (cgraph_edge
*src_edge
, cgraph_edge
*dst_edge
,
3394 edge_clone_summary
*src_data
,
3395 edge_clone_summary
*dst_data
);
3398 /* Edge duplication hook. */
3401 edge_clone_summary_t::duplicate (cgraph_edge
*src_edge
, cgraph_edge
*dst_edge
,
3402 edge_clone_summary
*src_data
,
3403 edge_clone_summary
*dst_data
)
3405 if (src_data
->next_clone
)
3406 edge_clone_summaries
->get (src_data
->next_clone
)->prev_clone
= dst_edge
;
3407 dst_data
->prev_clone
= src_edge
;
3408 dst_data
->next_clone
= src_data
->next_clone
;
3409 src_data
->next_clone
= dst_edge
;
3412 /* See if NODE is a clone with a known aggregate value at a given OFFSET of a
3413 parameter with the given INDEX. */
3416 get_clone_agg_value (struct cgraph_node
*node
, HOST_WIDE_INT offset
,
3419 struct ipa_agg_replacement_value
*aggval
;
3421 aggval
= ipa_get_agg_replacements_for_node (node
);
3424 if (aggval
->offset
== offset
3425 && aggval
->index
== index
)
3426 return aggval
->value
;
3427 aggval
= aggval
->next
;
3432 /* Return true is NODE is DEST or its clone for all contexts. */
3435 same_node_or_its_all_contexts_clone_p (cgraph_node
*node
, cgraph_node
*dest
)
3440 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3441 return info
->is_all_contexts_clone
&& info
->ipcp_orig_node
== dest
;
3444 /* Return true if edge CS does bring about the value described by SRC to
3445 DEST_VAL of node DEST or its clone for all contexts. */
3448 cgraph_edge_brings_value_p (cgraph_edge
*cs
, ipcp_value_source
<tree
> *src
,
3449 cgraph_node
*dest
, ipcp_value
<tree
> *dest_val
)
3451 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3452 enum availability availability
;
3453 cgraph_node
*real_dest
= cs
->callee
->function_symbol (&availability
);
3455 if (!same_node_or_its_all_contexts_clone_p (real_dest
, dest
)
3456 || availability
<= AVAIL_INTERPOSABLE
3457 || caller_info
->node_dead
)
3463 if (caller_info
->ipcp_orig_node
)
3466 if (src
->offset
== -1)
3467 t
= caller_info
->known_csts
[src
->index
];
3469 t
= get_clone_agg_value (cs
->caller
, src
->offset
, src
->index
);
3470 return (t
!= NULL_TREE
3471 && values_equal_for_ipcp_p (src
->val
->value
, t
));
3475 /* At the moment we do not propagate over arithmetic jump functions in
3476 SCCs, so it is safe to detect self-feeding recursive calls in this
3478 if (src
->val
== dest_val
)
3481 struct ipcp_agg_lattice
*aglat
;
3482 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
3484 if (src
->offset
== -1)
3485 return (plats
->itself
.is_single_const ()
3486 && values_equal_for_ipcp_p (src
->val
->value
,
3487 plats
->itself
.values
->value
));
3490 if (plats
->aggs_bottom
|| plats
->aggs_contain_variable
)
3492 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3493 if (aglat
->offset
== src
->offset
)
3494 return (aglat
->is_single_const ()
3495 && values_equal_for_ipcp_p (src
->val
->value
,
3496 aglat
->values
->value
));
3502 /* Return true if edge CS does bring about the value described by SRC to
3503 DST_VAL of node DEST or its clone for all contexts. */
3506 cgraph_edge_brings_value_p (cgraph_edge
*cs
,
3507 ipcp_value_source
<ipa_polymorphic_call_context
> *src
,
3509 ipcp_value
<ipa_polymorphic_call_context
> *)
3511 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3512 cgraph_node
*real_dest
= cs
->callee
->function_symbol ();
3514 if (!same_node_or_its_all_contexts_clone_p (real_dest
, dest
)
3515 || caller_info
->node_dead
)
3520 if (caller_info
->ipcp_orig_node
)
3521 return (caller_info
->known_contexts
.length () > (unsigned) src
->index
)
3522 && values_equal_for_ipcp_p (src
->val
->value
,
3523 caller_info
->known_contexts
[src
->index
]);
3525 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
3527 return plats
->ctxlat
.is_single_const ()
3528 && values_equal_for_ipcp_p (src
->val
->value
,
3529 plats
->ctxlat
.values
->value
);
3532 /* Get the next clone in the linked list of clones of an edge. */
3534 static inline struct cgraph_edge
*
3535 get_next_cgraph_edge_clone (struct cgraph_edge
*cs
)
3537 edge_clone_summary
*s
= edge_clone_summaries
->get (cs
);
3538 return s
!= NULL
? s
->next_clone
: NULL
;
3541 /* Given VAL that is intended for DEST, iterate over all its sources and if any
3542 of them is viable and hot, return true. In that case, for those that still
3543 hold, add their edge frequency and their number into *FREQUENCY and
3544 *CALLER_COUNT respectively. */
3546 template <typename valtype
>
3548 get_info_about_necessary_edges (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
3550 profile_count
*count_sum
, int *caller_count
)
3552 ipcp_value_source
<valtype
> *src
;
3553 int freq
= 0, count
= 0;
3554 profile_count cnt
= profile_count::zero ();
3556 bool non_self_recursive
= false;
3558 for (src
= val
->sources
; src
; src
= src
->next
)
3560 struct cgraph_edge
*cs
= src
->cs
;
3563 if (cgraph_edge_brings_value_p (cs
, src
, dest
, val
))
3566 freq
+= cs
->frequency ();
3567 if (cs
->count
.ipa ().initialized_p ())
3568 cnt
+= cs
->count
.ipa ();
3569 hot
|= cs
->maybe_hot_p ();
3570 if (cs
->caller
!= dest
)
3571 non_self_recursive
= true;
3573 cs
= get_next_cgraph_edge_clone (cs
);
3577 /* If the only edges bringing a value are self-recursive ones, do not bother
3579 if (!non_self_recursive
)
3584 *caller_count
= count
;
3588 /* Return a vector of incoming edges that do bring value VAL to node DEST. It
3589 is assumed their number is known and equal to CALLER_COUNT. */
3591 template <typename valtype
>
3592 static vec
<cgraph_edge
*>
3593 gather_edges_for_value (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
3596 ipcp_value_source
<valtype
> *src
;
3597 vec
<cgraph_edge
*> ret
;
3599 ret
.create (caller_count
);
3600 for (src
= val
->sources
; src
; src
= src
->next
)
3602 struct cgraph_edge
*cs
= src
->cs
;
3605 if (cgraph_edge_brings_value_p (cs
, src
, dest
, val
))
3606 ret
.quick_push (cs
);
3607 cs
= get_next_cgraph_edge_clone (cs
);
3614 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
3615 Return it or NULL if for some reason it cannot be created. */
3617 static struct ipa_replace_map
*
3618 get_replacement_map (struct ipa_node_params
*info
, tree value
, int parm_num
)
3620 struct ipa_replace_map
*replace_map
;
3623 replace_map
= ggc_alloc
<ipa_replace_map
> ();
3626 fprintf (dump_file
, " replacing ");
3627 ipa_dump_param (dump_file
, info
, parm_num
);
3629 fprintf (dump_file
, " with const ");
3630 print_generic_expr (dump_file
, value
);
3631 fprintf (dump_file
, "\n");
3633 replace_map
->old_tree
= NULL
;
3634 replace_map
->parm_num
= parm_num
;
3635 replace_map
->new_tree
= value
;
3636 replace_map
->replace_p
= true;
3637 replace_map
->ref_p
= false;
3642 /* Dump new profiling counts */
3645 dump_profile_updates (struct cgraph_node
*orig_node
,
3646 struct cgraph_node
*new_node
)
3648 struct cgraph_edge
*cs
;
3650 fprintf (dump_file
, " setting count of the specialized node to ");
3651 new_node
->count
.dump (dump_file
);
3652 fprintf (dump_file
, "\n");
3653 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3655 fprintf (dump_file
, " edge to %s has count ",
3656 cs
->callee
->name ());
3657 cs
->count
.dump (dump_file
);
3658 fprintf (dump_file
, "\n");
3661 fprintf (dump_file
, " setting count of the original node to ");
3662 orig_node
->count
.dump (dump_file
);
3663 fprintf (dump_file
, "\n");
3664 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3666 fprintf (dump_file
, " edge to %s is left with ",
3667 cs
->callee
->name ());
3668 cs
->count
.dump (dump_file
);
3669 fprintf (dump_file
, "\n");
3673 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
3674 their profile information to reflect this. */
3677 update_profiling_info (struct cgraph_node
*orig_node
,
3678 struct cgraph_node
*new_node
)
3680 struct cgraph_edge
*cs
;
3681 struct caller_statistics stats
;
3682 profile_count new_sum
, orig_sum
;
3683 profile_count remainder
, orig_node_count
= orig_node
->count
;
3685 if (!(orig_node_count
.ipa () > profile_count::zero ()))
3688 init_caller_stats (&stats
);
3689 orig_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
3691 orig_sum
= stats
.count_sum
;
3692 init_caller_stats (&stats
);
3693 new_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
3695 new_sum
= stats
.count_sum
;
3697 if (orig_node_count
< orig_sum
+ new_sum
)
3701 fprintf (dump_file
, " Problem: node %s has too low count ",
3702 orig_node
->dump_name ());
3703 orig_node_count
.dump (dump_file
);
3704 fprintf (dump_file
, "while the sum of incoming count is ");
3705 (orig_sum
+ new_sum
).dump (dump_file
);
3706 fprintf (dump_file
, "\n");
3709 orig_node_count
= (orig_sum
+ new_sum
).apply_scale (12, 10);
3712 fprintf (dump_file
, " proceeding by pretending it was ");
3713 orig_node_count
.dump (dump_file
);
3714 fprintf (dump_file
, "\n");
3718 remainder
= orig_node_count
.combine_with_ipa_count (orig_node_count
.ipa ()
3720 new_sum
= orig_node_count
.combine_with_ipa_count (new_sum
);
3721 orig_node
->count
= remainder
;
3723 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3724 cs
->count
= cs
->count
.apply_scale (new_sum
, orig_node_count
);
3726 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3727 cs
->count
= cs
->count
.apply_scale (remainder
, orig_node_count
);
3730 dump_profile_updates (orig_node
, new_node
);
3733 /* Update the respective profile of specialized NEW_NODE and the original
3734 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
3735 have been redirected to the specialized version. */
3738 update_specialized_profile (struct cgraph_node
*new_node
,
3739 struct cgraph_node
*orig_node
,
3740 profile_count redirected_sum
)
3742 struct cgraph_edge
*cs
;
3743 profile_count new_node_count
, orig_node_count
= orig_node
->count
;
3747 fprintf (dump_file
, " the sum of counts of redirected edges is ");
3748 redirected_sum
.dump (dump_file
);
3749 fprintf (dump_file
, "\n");
3751 if (!(orig_node_count
> profile_count::zero ()))
3754 gcc_assert (orig_node_count
>= redirected_sum
);
3756 new_node_count
= new_node
->count
;
3757 new_node
->count
+= redirected_sum
;
3758 orig_node
->count
-= redirected_sum
;
3760 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3761 cs
->count
+= cs
->count
.apply_scale (redirected_sum
, new_node_count
);
3763 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3765 profile_count dec
= cs
->count
.apply_scale (redirected_sum
,
3771 dump_profile_updates (orig_node
, new_node
);
3774 /* Create a specialized version of NODE with known constants in KNOWN_CSTS,
3775 known contexts in KNOWN_CONTEXTS and known aggregate values in AGGVALS and
3776 redirect all edges in CALLERS to it. */
3778 static struct cgraph_node
*
3779 create_specialized_node (struct cgraph_node
*node
,
3780 vec
<tree
> known_csts
,
3781 vec
<ipa_polymorphic_call_context
> known_contexts
,
3782 struct ipa_agg_replacement_value
*aggvals
,
3783 vec
<cgraph_edge
*> callers
)
3785 struct ipa_node_params
*new_info
, *info
= IPA_NODE_REF (node
);
3786 vec
<ipa_replace_map
*, va_gc
> *replace_trees
= NULL
;
3787 struct ipa_agg_replacement_value
*av
;
3788 struct cgraph_node
*new_node
;
3789 int i
, count
= ipa_get_param_count (info
);
3790 bitmap args_to_skip
;
3792 gcc_assert (!info
->ipcp_orig_node
);
3794 if (node
->local
.can_change_signature
)
3796 args_to_skip
= BITMAP_GGC_ALLOC ();
3797 for (i
= 0; i
< count
; i
++)
3799 tree t
= known_csts
[i
];
3801 if (t
|| !ipa_is_param_used (info
, i
))
3802 bitmap_set_bit (args_to_skip
, i
);
3807 args_to_skip
= NULL
;
3808 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3809 fprintf (dump_file
, " cannot change function signature\n");
3812 for (i
= 0; i
< count
; i
++)
3814 tree t
= known_csts
[i
];
3817 struct ipa_replace_map
*replace_map
;
3819 gcc_checking_assert (TREE_CODE (t
) != TREE_BINFO
);
3820 replace_map
= get_replacement_map (info
, t
, i
);
3822 vec_safe_push (replace_trees
, replace_map
);
3825 auto_vec
<cgraph_edge
*, 2> self_recursive_calls
;
3826 for (i
= callers
.length () - 1; i
>= 0; i
--)
3828 cgraph_edge
*cs
= callers
[i
];
3829 if (cs
->caller
== node
)
3831 self_recursive_calls
.safe_push (cs
);
3832 callers
.unordered_remove (i
);
3836 new_node
= node
->create_virtual_clone (callers
, replace_trees
,
3837 args_to_skip
, "constprop");
3839 bool have_self_recursive_calls
= !self_recursive_calls
.is_empty ();
3840 for (unsigned j
= 0; j
< self_recursive_calls
.length (); j
++)
3842 cgraph_edge
*cs
= get_next_cgraph_edge_clone (self_recursive_calls
[j
]);
3843 /* Cloned edges can disappear during cloning as speculation can be
3844 resolved, check that we have one and that it comes from the last
3846 if (cs
&& cs
->caller
== new_node
)
3847 cs
->redirect_callee_duplicating_thunks (new_node
);
3848 /* Any future code that would make more than one clone of an outgoing
3849 edge would confuse this mechanism, so let's check that does not
3851 gcc_checking_assert (!cs
3852 || !get_next_cgraph_edge_clone (cs
)
3853 || get_next_cgraph_edge_clone (cs
)->caller
!= new_node
);
3855 if (have_self_recursive_calls
)
3856 new_node
->expand_all_artificial_thunks ();
3858 ipa_set_node_agg_value_chain (new_node
, aggvals
);
3859 for (av
= aggvals
; av
; av
= av
->next
)
3860 new_node
->maybe_create_reference (av
->value
, NULL
);
3862 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3864 fprintf (dump_file
, " the new node is %s.\n", new_node
->dump_name ());
3865 if (known_contexts
.exists ())
3867 for (i
= 0; i
< count
; i
++)
3868 if (!known_contexts
[i
].useless_p ())
3870 fprintf (dump_file
, " known ctx %i is ", i
);
3871 known_contexts
[i
].dump (dump_file
);
3875 ipa_dump_agg_replacement_values (dump_file
, aggvals
);
3877 ipa_check_create_node_params ();
3878 update_profiling_info (node
, new_node
);
3879 new_info
= IPA_NODE_REF (new_node
);
3880 new_info
->ipcp_orig_node
= node
;
3881 new_info
->known_csts
= known_csts
;
3882 new_info
->known_contexts
= known_contexts
;
3884 ipcp_discover_new_direct_edges (new_node
, known_csts
, known_contexts
, aggvals
);
3890 /* Return true, if JFUNC, which describes a i-th parameter of call CS, is a
3891 simple no-operation pass-through function to itself. */
3894 self_recursive_pass_through_p (cgraph_edge
*cs
, ipa_jump_func
*jfunc
, int i
)
3896 enum availability availability
;
3897 if (cs
->caller
== cs
->callee
->function_symbol (&availability
)
3898 && availability
> AVAIL_INTERPOSABLE
3899 && jfunc
->type
== IPA_JF_PASS_THROUGH
3900 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
3901 && ipa_get_jf_pass_through_formal_id (jfunc
) == i
)
3906 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
3907 KNOWN_CSTS with constants that are also known for all of the CALLERS. */
3910 find_more_scalar_values_for_callers_subset (struct cgraph_node
*node
,
3911 vec
<tree
> known_csts
,
3912 vec
<cgraph_edge
*> callers
)
3914 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3915 int i
, count
= ipa_get_param_count (info
);
3917 for (i
= 0; i
< count
; i
++)
3919 struct cgraph_edge
*cs
;
3920 tree newval
= NULL_TREE
;
3923 tree type
= ipa_get_type (info
, i
);
3925 if (ipa_get_scalar_lat (info
, i
)->bottom
|| known_csts
[i
])
3928 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3930 struct ipa_jump_func
*jump_func
;
3933 if (IPA_NODE_REF (cs
->caller
)->node_dead
)
3936 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
))
3938 && call_passes_through_thunk_p (cs
)))
3943 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
3944 if (self_recursive_pass_through_p (cs
, jump_func
, i
))
3947 t
= ipa_value_from_jfunc (IPA_NODE_REF (cs
->caller
), jump_func
, type
);
3950 && !values_equal_for_ipcp_p (t
, newval
))
3951 || (!first
&& !newval
))
3963 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3965 fprintf (dump_file
, " adding an extra known scalar value ");
3966 print_ipcp_constant_value (dump_file
, newval
);
3967 fprintf (dump_file
, " for ");
3968 ipa_dump_param (dump_file
, info
, i
);
3969 fprintf (dump_file
, "\n");
3972 known_csts
[i
] = newval
;
3977 /* Given a NODE and a subset of its CALLERS, try to populate plank slots in
3978 KNOWN_CONTEXTS with polymorphic contexts that are also known for all of the
3982 find_more_contexts_for_caller_subset (cgraph_node
*node
,
3983 vec
<ipa_polymorphic_call_context
>
3985 vec
<cgraph_edge
*> callers
)
3987 ipa_node_params
*info
= IPA_NODE_REF (node
);
3988 int i
, count
= ipa_get_param_count (info
);
3990 for (i
= 0; i
< count
; i
++)
3994 if (ipa_get_poly_ctx_lat (info
, i
)->bottom
3995 || (known_contexts
->exists ()
3996 && !(*known_contexts
)[i
].useless_p ()))
3999 ipa_polymorphic_call_context newval
;
4003 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4005 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
)))
4007 ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
),
4009 ipa_polymorphic_call_context ctx
;
4010 ctx
= ipa_context_from_jfunc (IPA_NODE_REF (cs
->caller
), cs
, i
,
4018 newval
.meet_with (ctx
);
4019 if (newval
.useless_p ())
4023 if (!newval
.useless_p ())
4025 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4027 fprintf (dump_file
, " adding an extra known polymorphic "
4029 print_ipcp_constant_value (dump_file
, newval
);
4030 fprintf (dump_file
, " for ");
4031 ipa_dump_param (dump_file
, info
, i
);
4032 fprintf (dump_file
, "\n");
4035 if (!known_contexts
->exists ())
4036 known_contexts
->safe_grow_cleared (ipa_get_param_count (info
));
4037 (*known_contexts
)[i
] = newval
;
4043 /* Go through PLATS and create a vector of values consisting of values and
4044 offsets (minus OFFSET) of lattices that contain only a single value. */
4046 static vec
<ipa_agg_jf_item
>
4047 copy_plats_to_inter (struct ipcp_param_lattices
*plats
, HOST_WIDE_INT offset
)
4049 vec
<ipa_agg_jf_item
> res
= vNULL
;
4051 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
4054 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
4055 if (aglat
->is_single_const ())
4057 struct ipa_agg_jf_item ti
;
4058 ti
.offset
= aglat
->offset
- offset
;
4059 ti
.value
= aglat
->values
->value
;
4065 /* Intersect all values in INTER with single value lattices in PLATS (while
4066 subtracting OFFSET). */
4069 intersect_with_plats (struct ipcp_param_lattices
*plats
,
4070 vec
<ipa_agg_jf_item
> *inter
,
4071 HOST_WIDE_INT offset
)
4073 struct ipcp_agg_lattice
*aglat
;
4074 struct ipa_agg_jf_item
*item
;
4077 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
4083 aglat
= plats
->aggs
;
4084 FOR_EACH_VEC_ELT (*inter
, k
, item
)
4091 if (aglat
->offset
- offset
> item
->offset
)
4093 if (aglat
->offset
- offset
== item
->offset
)
4095 gcc_checking_assert (item
->value
);
4096 if (aglat
->is_single_const ()
4097 && values_equal_for_ipcp_p (item
->value
,
4098 aglat
->values
->value
))
4102 aglat
= aglat
->next
;
4105 item
->value
= NULL_TREE
;
4109 /* Copy aggregate replacement values of NODE (which is an IPA-CP clone) to the
4110 vector result while subtracting OFFSET from the individual value offsets. */
4112 static vec
<ipa_agg_jf_item
>
4113 agg_replacements_to_vector (struct cgraph_node
*node
, int index
,
4114 HOST_WIDE_INT offset
)
4116 struct ipa_agg_replacement_value
*av
;
4117 vec
<ipa_agg_jf_item
> res
= vNULL
;
4119 for (av
= ipa_get_agg_replacements_for_node (node
); av
; av
= av
->next
)
4120 if (av
->index
== index
4121 && (av
->offset
- offset
) >= 0)
4123 struct ipa_agg_jf_item item
;
4124 gcc_checking_assert (av
->value
);
4125 item
.offset
= av
->offset
- offset
;
4126 item
.value
= av
->value
;
4127 res
.safe_push (item
);
4133 /* Intersect all values in INTER with those that we have already scheduled to
4134 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
4135 (while subtracting OFFSET). */
4138 intersect_with_agg_replacements (struct cgraph_node
*node
, int index
,
4139 vec
<ipa_agg_jf_item
> *inter
,
4140 HOST_WIDE_INT offset
)
4142 struct ipa_agg_replacement_value
*srcvals
;
4143 struct ipa_agg_jf_item
*item
;
4146 srcvals
= ipa_get_agg_replacements_for_node (node
);
4153 FOR_EACH_VEC_ELT (*inter
, i
, item
)
4155 struct ipa_agg_replacement_value
*av
;
4159 for (av
= srcvals
; av
; av
= av
->next
)
4161 gcc_checking_assert (av
->value
);
4162 if (av
->index
== index
4163 && av
->offset
- offset
== item
->offset
)
4165 if (values_equal_for_ipcp_p (item
->value
, av
->value
))
4171 item
->value
= NULL_TREE
;
4175 /* Intersect values in INTER with aggregate values that come along edge CS to
4176 parameter number INDEX and return it. If INTER does not actually exist yet,
4177 copy all incoming values to it. If we determine we ended up with no values
4178 whatsoever, return a released vector. */
4180 static vec
<ipa_agg_jf_item
>
4181 intersect_aggregates_with_edge (struct cgraph_edge
*cs
, int index
,
4182 vec
<ipa_agg_jf_item
> inter
)
4184 struct ipa_jump_func
*jfunc
;
4185 jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), index
);
4186 if (jfunc
->type
== IPA_JF_PASS_THROUGH
4187 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
4189 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4190 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
4192 if (caller_info
->ipcp_orig_node
)
4194 struct cgraph_node
*orig_node
= caller_info
->ipcp_orig_node
;
4195 struct ipcp_param_lattices
*orig_plats
;
4196 orig_plats
= ipa_get_parm_lattices (IPA_NODE_REF (orig_node
),
4198 if (agg_pass_through_permissible_p (orig_plats
, jfunc
))
4200 if (!inter
.exists ())
4201 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, 0);
4203 intersect_with_agg_replacements (cs
->caller
, src_idx
,
4214 struct ipcp_param_lattices
*src_plats
;
4215 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
4216 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
4218 /* Currently we do not produce clobber aggregate jump
4219 functions, adjust when we do. */
4220 gcc_checking_assert (!jfunc
->agg
.items
);
4221 if (!inter
.exists ())
4222 inter
= copy_plats_to_inter (src_plats
, 0);
4224 intersect_with_plats (src_plats
, &inter
, 0);
4233 else if (jfunc
->type
== IPA_JF_ANCESTOR
4234 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
4236 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4237 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
4238 struct ipcp_param_lattices
*src_plats
;
4239 HOST_WIDE_INT delta
= ipa_get_jf_ancestor_offset (jfunc
);
4241 if (caller_info
->ipcp_orig_node
)
4243 if (!inter
.exists ())
4244 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, delta
);
4246 intersect_with_agg_replacements (cs
->caller
, src_idx
, &inter
,
4251 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
4252 /* Currently we do not produce clobber aggregate jump
4253 functions, adjust when we do. */
4254 gcc_checking_assert (!src_plats
->aggs
|| !jfunc
->agg
.items
);
4255 if (!inter
.exists ())
4256 inter
= copy_plats_to_inter (src_plats
, delta
);
4258 intersect_with_plats (src_plats
, &inter
, delta
);
4261 else if (jfunc
->agg
.items
)
4263 struct ipa_agg_jf_item
*item
;
4266 if (!inter
.exists ())
4267 for (unsigned i
= 0; i
< jfunc
->agg
.items
->length (); i
++)
4268 inter
.safe_push ((*jfunc
->agg
.items
)[i
]);
4270 FOR_EACH_VEC_ELT (inter
, k
, item
)
4278 while ((unsigned) l
< jfunc
->agg
.items
->length ())
4280 struct ipa_agg_jf_item
*ti
;
4281 ti
= &(*jfunc
->agg
.items
)[l
];
4282 if (ti
->offset
> item
->offset
)
4284 if (ti
->offset
== item
->offset
)
4286 gcc_checking_assert (ti
->value
);
4287 if (values_equal_for_ipcp_p (item
->value
,
4301 return vec
<ipa_agg_jf_item
>();
4306 /* Look at edges in CALLERS and collect all known aggregate values that arrive
4307 from all of them. */
4309 static struct ipa_agg_replacement_value
*
4310 find_aggregate_values_for_callers_subset (struct cgraph_node
*node
,
4311 vec
<cgraph_edge
*> callers
)
4313 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
4314 struct ipa_agg_replacement_value
*res
;
4315 struct ipa_agg_replacement_value
**tail
= &res
;
4316 struct cgraph_edge
*cs
;
4317 int i
, j
, count
= ipa_get_param_count (dest_info
);
4319 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4321 int c
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
4326 for (i
= 0; i
< count
; i
++)
4328 struct cgraph_edge
*cs
;
4329 vec
<ipa_agg_jf_item
> inter
= vNULL
;
4330 struct ipa_agg_jf_item
*item
;
4331 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (dest_info
, i
);
4334 /* Among other things, the following check should deal with all by_ref
4336 if (plats
->aggs_bottom
)
4339 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4341 struct ipa_jump_func
*jfunc
4342 = ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
4343 if (self_recursive_pass_through_p (cs
, jfunc
, i
)
4344 && (!plats
->aggs_by_ref
4345 || ipa_get_jf_pass_through_agg_preserved (jfunc
)))
4347 inter
= intersect_aggregates_with_edge (cs
, i
, inter
);
4349 if (!inter
.exists ())
4353 FOR_EACH_VEC_ELT (inter
, j
, item
)
4355 struct ipa_agg_replacement_value
*v
;
4360 v
= ggc_alloc
<ipa_agg_replacement_value
> ();
4362 v
->offset
= item
->offset
;
4363 v
->value
= item
->value
;
4364 v
->by_ref
= plats
->aggs_by_ref
;
4370 if (inter
.exists ())
4377 /* Determine whether CS also brings all scalar values that the NODE is
4381 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge
*cs
,
4382 struct cgraph_node
*node
)
4384 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
4385 int count
= ipa_get_param_count (dest_info
);
4386 struct ipa_node_params
*caller_info
;
4387 struct ipa_edge_args
*args
;
4390 caller_info
= IPA_NODE_REF (cs
->caller
);
4391 args
= IPA_EDGE_REF (cs
);
4392 for (i
= 0; i
< count
; i
++)
4394 struct ipa_jump_func
*jump_func
;
4397 val
= dest_info
->known_csts
[i
];
4401 if (i
>= ipa_get_cs_argument_count (args
))
4403 jump_func
= ipa_get_ith_jump_func (args
, i
);
4404 t
= ipa_value_from_jfunc (caller_info
, jump_func
,
4405 ipa_get_type (dest_info
, i
));
4406 if (!t
|| !values_equal_for_ipcp_p (val
, t
))
4412 /* Determine whether CS also brings all aggregate values that NODE is
4415 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge
*cs
,
4416 struct cgraph_node
*node
)
4418 struct ipa_node_params
*orig_caller_info
= IPA_NODE_REF (cs
->caller
);
4419 struct ipa_node_params
*orig_node_info
;
4420 struct ipa_agg_replacement_value
*aggval
;
4423 aggval
= ipa_get_agg_replacements_for_node (node
);
4427 count
= ipa_get_param_count (IPA_NODE_REF (node
));
4428 ec
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
4430 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4431 if (aggval
->index
>= ec
)
4434 orig_node_info
= IPA_NODE_REF (IPA_NODE_REF (node
)->ipcp_orig_node
);
4435 if (orig_caller_info
->ipcp_orig_node
)
4436 orig_caller_info
= IPA_NODE_REF (orig_caller_info
->ipcp_orig_node
);
4438 for (i
= 0; i
< count
; i
++)
4440 static vec
<ipa_agg_jf_item
> values
= vec
<ipa_agg_jf_item
>();
4441 struct ipcp_param_lattices
*plats
;
4442 bool interesting
= false;
4443 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4444 if (aggval
->index
== i
)
4452 plats
= ipa_get_parm_lattices (orig_node_info
, aggval
->index
);
4453 if (plats
->aggs_bottom
)
4456 values
= intersect_aggregates_with_edge (cs
, i
, values
);
4457 if (!values
.exists ())
4460 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4461 if (aggval
->index
== i
)
4463 struct ipa_agg_jf_item
*item
;
4466 FOR_EACH_VEC_ELT (values
, j
, item
)
4468 && item
->offset
== av
->offset
4469 && values_equal_for_ipcp_p (item
->value
, av
->value
))
4484 /* Given an original NODE and a VAL for which we have already created a
4485 specialized clone, look whether there are incoming edges that still lead
4486 into the old node but now also bring the requested value and also conform to
4487 all other criteria such that they can be redirected the special node.
4488 This function can therefore redirect the final edge in a SCC. */
4490 template <typename valtype
>
4492 perhaps_add_new_callers (cgraph_node
*node
, ipcp_value
<valtype
> *val
)
4494 ipcp_value_source
<valtype
> *src
;
4495 profile_count redirected_sum
= profile_count::zero ();
4497 for (src
= val
->sources
; src
; src
= src
->next
)
4499 struct cgraph_edge
*cs
= src
->cs
;
4502 if (cgraph_edge_brings_value_p (cs
, src
, node
, val
)
4503 && cgraph_edge_brings_all_scalars_for_node (cs
, val
->spec_node
)
4504 && cgraph_edge_brings_all_agg_vals_for_node (cs
, val
->spec_node
))
4507 fprintf (dump_file
, " - adding an extra caller %s of %s\n",
4508 cs
->caller
->dump_name (),
4509 val
->spec_node
->dump_name ());
4511 cs
->redirect_callee_duplicating_thunks (val
->spec_node
);
4512 val
->spec_node
->expand_all_artificial_thunks ();
4513 if (cs
->count
.ipa ().initialized_p ())
4514 redirected_sum
= redirected_sum
+ cs
->count
.ipa ();
4516 cs
= get_next_cgraph_edge_clone (cs
);
4520 if (redirected_sum
.nonzero_p ())
4521 update_specialized_profile (val
->spec_node
, node
, redirected_sum
);
4524 /* Return true if KNOWN_CONTEXTS contain at least one useful context. */
4527 known_contexts_useful_p (vec
<ipa_polymorphic_call_context
> known_contexts
)
4529 ipa_polymorphic_call_context
*ctx
;
4532 FOR_EACH_VEC_ELT (known_contexts
, i
, ctx
)
4533 if (!ctx
->useless_p ())
4538 /* Return a copy of KNOWN_CSTS if it is not empty, otherwise return vNULL. */
4540 static vec
<ipa_polymorphic_call_context
>
4541 copy_useful_known_contexts (vec
<ipa_polymorphic_call_context
> known_contexts
)
4543 if (known_contexts_useful_p (known_contexts
))
4544 return known_contexts
.copy ();
4549 /* Copy KNOWN_CSTS and modify the copy according to VAL and INDEX. If
4550 non-empty, replace KNOWN_CONTEXTS with its copy too. */
4553 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
4554 vec
<ipa_polymorphic_call_context
> *known_contexts
,
4555 ipcp_value
<tree
> *val
,
4558 *known_csts
= known_csts
->copy ();
4559 *known_contexts
= copy_useful_known_contexts (*known_contexts
);
4560 (*known_csts
)[index
] = val
->value
;
4563 /* Replace KNOWN_CSTS with its copy. Also copy KNOWN_CONTEXTS and modify the
4564 copy according to VAL and INDEX. */
4567 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
4568 vec
<ipa_polymorphic_call_context
> *known_contexts
,
4569 ipcp_value
<ipa_polymorphic_call_context
> *val
,
4572 *known_csts
= known_csts
->copy ();
4573 *known_contexts
= known_contexts
->copy ();
4574 (*known_contexts
)[index
] = val
->value
;
4577 /* Return true if OFFSET indicates this was not an aggregate value or there is
4578 a replacement equivalent to VALUE, INDEX and OFFSET among those in the
4582 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*aggvals
,
4583 int index
, HOST_WIDE_INT offset
, tree value
)
4590 if (aggvals
->index
== index
4591 && aggvals
->offset
== offset
4592 && values_equal_for_ipcp_p (aggvals
->value
, value
))
4594 aggvals
= aggvals
->next
;
4599 /* Return true if offset is minus one because source of a polymorphic contect
4600 cannot be an aggregate value. */
4603 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*,
4604 int , HOST_WIDE_INT offset
,
4605 ipa_polymorphic_call_context
)
4607 return offset
== -1;
4610 /* Decide wheter to create a special version of NODE for value VAL of parameter
4611 at the given INDEX. If OFFSET is -1, the value is for the parameter itself,
4612 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS,
4613 KNOWN_CONTEXTS and KNOWN_AGGS describe the other already known values. */
4615 template <typename valtype
>
4617 decide_about_value (struct cgraph_node
*node
, int index
, HOST_WIDE_INT offset
,
4618 ipcp_value
<valtype
> *val
, vec
<tree
> known_csts
,
4619 vec
<ipa_polymorphic_call_context
> known_contexts
)
4621 struct ipa_agg_replacement_value
*aggvals
;
4622 int freq_sum
, caller_count
;
4623 profile_count count_sum
;
4624 vec
<cgraph_edge
*> callers
;
4628 perhaps_add_new_callers (node
, val
);
4631 else if (val
->local_size_cost
+ overall_size
> max_new_size
)
4633 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4634 fprintf (dump_file
, " Ignoring candidate value because "
4635 "max_new_size would be reached with %li.\n",
4636 val
->local_size_cost
+ overall_size
);
4639 else if (!get_info_about_necessary_edges (val
, node
, &freq_sum
, &count_sum
,
4643 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4645 fprintf (dump_file
, " - considering value ");
4646 print_ipcp_constant_value (dump_file
, val
->value
);
4647 fprintf (dump_file
, " for ");
4648 ipa_dump_param (dump_file
, IPA_NODE_REF (node
), index
);
4650 fprintf (dump_file
, ", offset: " HOST_WIDE_INT_PRINT_DEC
, offset
);
4651 fprintf (dump_file
, " (caller_count: %i)\n", caller_count
);
4654 if (!good_cloning_opportunity_p (node
, val
->local_time_benefit
,
4655 freq_sum
, count_sum
,
4656 val
->local_size_cost
)
4657 && !good_cloning_opportunity_p (node
,
4658 val
->local_time_benefit
4659 + val
->prop_time_benefit
,
4660 freq_sum
, count_sum
,
4661 val
->local_size_cost
4662 + val
->prop_size_cost
))
4666 fprintf (dump_file
, " Creating a specialized node of %s.\n",
4667 node
->dump_name ());
4669 callers
= gather_edges_for_value (val
, node
, caller_count
);
4671 modify_known_vectors_with_val (&known_csts
, &known_contexts
, val
, index
);
4674 known_csts
= known_csts
.copy ();
4675 known_contexts
= copy_useful_known_contexts (known_contexts
);
4677 find_more_scalar_values_for_callers_subset (node
, known_csts
, callers
);
4678 find_more_contexts_for_caller_subset (node
, &known_contexts
, callers
);
4679 aggvals
= find_aggregate_values_for_callers_subset (node
, callers
);
4680 gcc_checking_assert (ipcp_val_agg_replacement_ok_p (aggvals
, index
,
4681 offset
, val
->value
));
4682 val
->spec_node
= create_specialized_node (node
, known_csts
, known_contexts
,
4684 overall_size
+= val
->local_size_cost
;
4686 /* TODO: If for some lattice there is only one other known value
4687 left, make a special node for it too. */
4692 /* Decide whether and what specialized clones of NODE should be created. */
4695 decide_whether_version_node (struct cgraph_node
*node
)
4697 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
4698 int i
, count
= ipa_get_param_count (info
);
4699 vec
<tree
> known_csts
;
4700 vec
<ipa_polymorphic_call_context
> known_contexts
;
4701 vec
<ipa_agg_jump_function
> known_aggs
= vNULL
;
4707 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4708 fprintf (dump_file
, "\nEvaluating opportunities for %s.\n",
4709 node
->dump_name ());
4711 gather_context_independent_values (info
, &known_csts
, &known_contexts
,
4712 info
->do_clone_for_all_contexts
? &known_aggs
4715 for (i
= 0; i
< count
;i
++)
4717 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4718 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
4719 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
4724 ipcp_value
<tree
> *val
;
4725 for (val
= lat
->values
; val
; val
= val
->next
)
4726 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
4730 if (!plats
->aggs_bottom
)
4732 struct ipcp_agg_lattice
*aglat
;
4733 ipcp_value
<tree
> *val
;
4734 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
4735 if (!aglat
->bottom
&& aglat
->values
4736 /* If the following is false, the one value is in
4738 && (plats
->aggs_contain_variable
4739 || !aglat
->is_single_const ()))
4740 for (val
= aglat
->values
; val
; val
= val
->next
)
4741 ret
|= decide_about_value (node
, i
, aglat
->offset
, val
,
4742 known_csts
, known_contexts
);
4746 && known_contexts
[i
].useless_p ())
4748 ipcp_value
<ipa_polymorphic_call_context
> *val
;
4749 for (val
= ctxlat
->values
; val
; val
= val
->next
)
4750 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
4754 info
= IPA_NODE_REF (node
);
4757 if (info
->do_clone_for_all_contexts
)
4759 struct cgraph_node
*clone
;
4760 vec
<cgraph_edge
*> callers
;
4763 fprintf (dump_file
, " - Creating a specialized node of %s "
4764 "for all known contexts.\n", node
->dump_name ());
4766 callers
= node
->collect_callers ();
4767 find_more_scalar_values_for_callers_subset (node
, known_csts
, callers
);
4768 find_more_contexts_for_caller_subset (node
, &known_contexts
, callers
);
4769 ipa_agg_replacement_value
*aggvals
4770 = find_aggregate_values_for_callers_subset (node
, callers
);
4772 if (!known_contexts_useful_p (known_contexts
))
4774 known_contexts
.release ();
4775 known_contexts
= vNULL
;
4777 clone
= create_specialized_node (node
, known_csts
, known_contexts
,
4779 info
= IPA_NODE_REF (node
);
4780 info
->do_clone_for_all_contexts
= false;
4781 IPA_NODE_REF (clone
)->is_all_contexts_clone
= true;
4782 for (i
= 0; i
< count
; i
++)
4783 vec_free (known_aggs
[i
].items
);
4784 known_aggs
.release ();
4789 known_csts
.release ();
4790 known_contexts
.release ();
4796 /* Transitively mark all callees of NODE within the same SCC as not dead. */
4799 spread_undeadness (struct cgraph_node
*node
)
4801 struct cgraph_edge
*cs
;
4803 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
4804 if (ipa_edge_within_scc (cs
))
4806 struct cgraph_node
*callee
;
4807 struct ipa_node_params
*info
;
4809 callee
= cs
->callee
->function_symbol (NULL
);
4810 info
= IPA_NODE_REF (callee
);
4812 if (info
->node_dead
)
4814 info
->node_dead
= 0;
4815 spread_undeadness (callee
);
4820 /* Return true if NODE has a caller from outside of its SCC that is not
4821 dead. Worker callback for cgraph_for_node_and_aliases. */
4824 has_undead_caller_from_outside_scc_p (struct cgraph_node
*node
,
4825 void *data ATTRIBUTE_UNUSED
)
4827 struct cgraph_edge
*cs
;
4829 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
4830 if (cs
->caller
->thunk
.thunk_p
4831 && cs
->caller
->call_for_symbol_thunks_and_aliases
4832 (has_undead_caller_from_outside_scc_p
, NULL
, true))
4834 else if (!ipa_edge_within_scc (cs
)
4835 && !IPA_NODE_REF (cs
->caller
)->node_dead
)
4841 /* Identify nodes within the same SCC as NODE which are no longer needed
4842 because of new clones and will be removed as unreachable. */
4845 identify_dead_nodes (struct cgraph_node
*node
)
4847 struct cgraph_node
*v
;
4848 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4850 && !v
->call_for_symbol_thunks_and_aliases
4851 (has_undead_caller_from_outside_scc_p
, NULL
, true))
4852 IPA_NODE_REF (v
)->node_dead
= 1;
4854 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4855 if (!IPA_NODE_REF (v
)->node_dead
)
4856 spread_undeadness (v
);
4858 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4860 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4861 if (IPA_NODE_REF (v
)->node_dead
)
4862 fprintf (dump_file
, " Marking node as dead: %s.\n", v
->dump_name ());
4866 /* The decision stage. Iterate over the topological order of call graph nodes
4867 TOPO and make specialized clones if deemed beneficial. */
4870 ipcp_decision_stage (struct ipa_topo_info
*topo
)
4875 fprintf (dump_file
, "\nIPA decision stage:\n\n");
4877 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
4879 struct cgraph_node
*node
= topo
->order
[i
];
4880 bool change
= false, iterate
= true;
4884 struct cgraph_node
*v
;
4886 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4887 if (v
->has_gimple_body_p ()
4888 && ipcp_versionable_function_p (v
))
4889 iterate
|= decide_whether_version_node (v
);
4894 identify_dead_nodes (node
);
4898 /* Look up all the bits information that we have discovered and copy it over
4899 to the transformation summary. */
4902 ipcp_store_bits_results (void)
4906 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
4908 ipa_node_params
*info
= IPA_NODE_REF (node
);
4909 bool dumped_sth
= false;
4910 bool found_useful_result
= false;
4912 if (!opt_for_fn (node
->decl
, flag_ipa_bit_cp
))
4915 fprintf (dump_file
, "Not considering %s for ipa bitwise propagation "
4916 "; -fipa-bit-cp: disabled.\n",
4921 if (info
->ipcp_orig_node
)
4922 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
4924 unsigned count
= ipa_get_param_count (info
);
4925 for (unsigned i
= 0; i
< count
; i
++)
4927 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4928 if (plats
->bits_lattice
.constant_p ())
4930 found_useful_result
= true;
4935 if (!found_useful_result
)
4938 ipcp_transformation_initialize ();
4939 ipcp_transformation
*ts
= ipcp_transformation_sum
->get_create (node
);
4940 vec_safe_reserve_exact (ts
->bits
, count
);
4942 for (unsigned i
= 0; i
< count
; i
++)
4944 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4947 if (plats
->bits_lattice
.constant_p ())
4949 = ipa_get_ipa_bits_for_value (plats
->bits_lattice
.get_value (),
4950 plats
->bits_lattice
.get_mask ());
4954 ts
->bits
->quick_push (jfbits
);
4955 if (!dump_file
|| !jfbits
)
4959 fprintf (dump_file
, "Propagated bits info for function %s:\n",
4960 node
->dump_name ());
4963 fprintf (dump_file
, " param %i: value = ", i
);
4964 print_hex (jfbits
->value
, dump_file
);
4965 fprintf (dump_file
, ", mask = ");
4966 print_hex (jfbits
->mask
, dump_file
);
4967 fprintf (dump_file
, "\n");
4972 /* Look up all VR information that we have discovered and copy it over
4973 to the transformation summary. */
4976 ipcp_store_vr_results (void)
4980 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
4982 ipa_node_params
*info
= IPA_NODE_REF (node
);
4983 bool found_useful_result
= false;
4985 if (!opt_for_fn (node
->decl
, flag_ipa_vrp
))
4988 fprintf (dump_file
, "Not considering %s for VR discovery "
4989 "and propagate; -fipa-ipa-vrp: disabled.\n",
4994 if (info
->ipcp_orig_node
)
4995 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
4997 unsigned count
= ipa_get_param_count (info
);
4998 for (unsigned i
= 0; i
< count
; i
++)
5000 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5001 if (!plats
->m_value_range
.bottom_p ()
5002 && !plats
->m_value_range
.top_p ())
5004 found_useful_result
= true;
5008 if (!found_useful_result
)
5011 ipcp_transformation_initialize ();
5012 ipcp_transformation
*ts
= ipcp_transformation_sum
->get_create (node
);
5013 vec_safe_reserve_exact (ts
->m_vr
, count
);
5015 for (unsigned i
= 0; i
< count
; i
++)
5017 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5020 if (!plats
->m_value_range
.bottom_p ()
5021 && !plats
->m_value_range
.top_p ())
5024 vr
.type
= plats
->m_value_range
.m_vr
.kind ();
5025 vr
.min
= wi::to_wide (plats
->m_value_range
.m_vr
.min ());
5026 vr
.max
= wi::to_wide (plats
->m_value_range
.m_vr
.max ());
5031 vr
.type
= VR_VARYING
;
5032 vr
.min
= vr
.max
= wi::zero (INT_TYPE_SIZE
);
5034 ts
->m_vr
->quick_push (vr
);
5039 /* The IPCP driver. */
5044 struct ipa_topo_info topo
;
5046 if (edge_clone_summaries
== NULL
)
5047 edge_clone_summaries
= new edge_clone_summary_t (symtab
);
5049 ipa_check_create_node_params ();
5050 ipa_check_create_edge_args ();
5054 fprintf (dump_file
, "\nIPA structures before propagation:\n");
5055 if (dump_flags
& TDF_DETAILS
)
5056 ipa_print_all_params (dump_file
);
5057 ipa_print_all_jump_functions (dump_file
);
5060 /* Topological sort. */
5061 build_toporder_info (&topo
);
5062 /* Do the interprocedural propagation. */
5063 ipcp_propagate_stage (&topo
);
5064 /* Decide what constant propagation and cloning should be performed. */
5065 ipcp_decision_stage (&topo
);
5066 /* Store results of bits propagation. */
5067 ipcp_store_bits_results ();
5068 /* Store results of value range propagation. */
5069 ipcp_store_vr_results ();
5071 /* Free all IPCP structures. */
5072 free_toporder_info (&topo
);
5073 delete edge_clone_summaries
;
5074 edge_clone_summaries
= NULL
;
5075 ipa_free_all_structures_after_ipa_cp ();
5077 fprintf (dump_file
, "\nIPA constant propagation end\n");
5081 /* Initialization and computation of IPCP data structures. This is the initial
5082 intraprocedural analysis of functions, which gathers information to be
5083 propagated later on. */
5086 ipcp_generate_summary (void)
5088 struct cgraph_node
*node
;
5091 fprintf (dump_file
, "\nIPA constant propagation start:\n");
5092 ipa_register_cgraph_hooks ();
5094 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5095 ipa_analyze_node (node
);
5098 /* Write ipcp summary for nodes in SET. */
5101 ipcp_write_summary (void)
5103 ipa_prop_write_jump_functions ();
5106 /* Read ipcp summary. */
5109 ipcp_read_summary (void)
5111 ipa_prop_read_jump_functions ();
5116 const pass_data pass_data_ipa_cp
=
5118 IPA_PASS
, /* type */
5120 OPTGROUP_NONE
, /* optinfo_flags */
5121 TV_IPA_CONSTANT_PROP
, /* tv_id */
5122 0, /* properties_required */
5123 0, /* properties_provided */
5124 0, /* properties_destroyed */
5125 0, /* todo_flags_start */
5126 ( TODO_dump_symtab
| TODO_remove_functions
), /* todo_flags_finish */
5129 class pass_ipa_cp
: public ipa_opt_pass_d
5132 pass_ipa_cp (gcc::context
*ctxt
)
5133 : ipa_opt_pass_d (pass_data_ipa_cp
, ctxt
,
5134 ipcp_generate_summary
, /* generate_summary */
5135 ipcp_write_summary
, /* write_summary */
5136 ipcp_read_summary
, /* read_summary */
5137 ipcp_write_transformation_summaries
, /*
5138 write_optimization_summary */
5139 ipcp_read_transformation_summaries
, /*
5140 read_optimization_summary */
5141 NULL
, /* stmt_fixup */
5142 0, /* function_transform_todo_flags_start */
5143 ipcp_transform_function
, /* function_transform */
5144 NULL
) /* variable_transform */
5147 /* opt_pass methods: */
5148 virtual bool gate (function
*)
5150 /* FIXME: We should remove the optimize check after we ensure we never run
5151 IPA passes when not optimizing. */
5152 return (flag_ipa_cp
&& optimize
) || in_lto_p
;
5155 virtual unsigned int execute (function
*) { return ipcp_driver (); }
5157 }; // class pass_ipa_cp
5162 make_pass_ipa_cp (gcc::context
*ctxt
)
5164 return new pass_ipa_cp (ctxt
);
5167 /* Reset all state within ipa-cp.c so that we can rerun the compiler
5168 within the same process. For use by toplev::finalize. */
5171 ipa_cp_c_finalize (void)
5173 max_count
= profile_count::uninitialized ();