1 /* Interprocedural constant propagation
2 Copyright (C) 2005-2018 Free Software Foundation, Inc.
4 Contributed by Razya Ladelsky <RAZYA@il.ibm.com> and Martin Jambor
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
23 /* Interprocedural constant propagation (IPA-CP).
25 The goal of this transformation is to
27 1) discover functions which are always invoked with some arguments with the
28 same known constant values and modify the functions so that the
29 subsequent optimizations can take advantage of the knowledge, and
31 2) partial specialization - create specialized versions of functions
32 transformed in this way if some parameters are known constants only in
33 certain contexts but the estimated tradeoff between speedup and cost size
36 The algorithm also propagates types and attempts to perform type based
37 devirtualization. Types are propagated much like constants.
39 The algorithm basically consists of three stages. In the first, functions
40 are analyzed one at a time and jump functions are constructed for all known
41 call-sites. In the second phase, the pass propagates information from the
42 jump functions across the call to reveal what values are available at what
43 call sites, performs estimations of effects of known values on functions and
44 their callees, and finally decides what specialized extra versions should be
45 created. In the third, the special versions materialize and appropriate
48 The algorithm used is to a certain extent based on "Interprocedural Constant
49 Propagation", by David Callahan, Keith D Cooper, Ken Kennedy, Linda Torczon,
50 Comp86, pg 152-161 and "A Methodology for Procedure Cloning" by Keith D
51 Cooper, Mary W. Hall, and Ken Kennedy.
54 First stage - intraprocedural analysis
55 =======================================
57 This phase computes jump_function and modification flags.
59 A jump function for a call-site represents the values passed as an actual
60 arguments of a given call-site. In principle, there are three types of
63 Pass through - the caller's formal parameter is passed as an actual
64 argument, plus an operation on it can be performed.
65 Constant - a constant is passed as an actual argument.
66 Unknown - neither of the above.
68 All jump function types are described in detail in ipa-prop.h, together with
69 the data structures that represent them and methods of accessing them.
71 ipcp_generate_summary() is the main function of the first stage.
73 Second stage - interprocedural analysis
74 ========================================
76 This stage is itself divided into two phases. In the first, we propagate
77 known values over the call graph, in the second, we make cloning decisions.
78 It uses a different algorithm than the original Callahan's paper.
80 First, we traverse the functions topologically from callers to callees and,
81 for each strongly connected component (SCC), we propagate constants
82 according to previously computed jump functions. We also record what known
83 values depend on other known values and estimate local effects. Finally, we
84 propagate cumulative information about these effects from dependent values
85 to those on which they depend.
87 Second, we again traverse the call graph in the same topological order and
88 make clones for functions which we know are called with the same values in
89 all contexts and decide about extra specialized clones of functions just for
90 some contexts - these decisions are based on both local estimates and
91 cumulative estimates propagated from callees.
93 ipcp_propagate_stage() and ipcp_decision_stage() together constitute the
96 Third phase - materialization of clones, call statement updates.
97 ============================================
99 This stage is currently performed by call graph code (mainly in cgraphunit.c
100 and tree-inline.c) according to instructions inserted to the call graph by
105 #include "coretypes.h"
108 #include "gimple-expr.h"
110 #include "alloc-pool.h"
111 #include "tree-pass.h"
113 #include "diagnostic.h"
114 #include "fold-const.h"
115 #include "gimple-fold.h"
116 #include "symbol-summary.h"
117 #include "tree-vrp.h"
118 #include "ipa-prop.h"
119 #include "tree-pretty-print.h"
120 #include "tree-inline.h"
122 #include "ipa-fnsummary.h"
123 #include "ipa-utils.h"
124 #include "tree-ssa-ccp.h"
125 #include "stringpool.h"
128 template <typename valtype
> class ipcp_value
;
130 /* Describes a particular source for an IPA-CP value. */
132 template <typename valtype
>
133 class ipcp_value_source
136 /* Aggregate offset of the source, negative if the source is scalar value of
137 the argument itself. */
138 HOST_WIDE_INT offset
;
139 /* The incoming edge that brought the value. */
141 /* If the jump function that resulted into his value was a pass-through or an
142 ancestor, this is the ipcp_value of the caller from which the described
143 value has been derived. Otherwise it is NULL. */
144 ipcp_value
<valtype
> *val
;
145 /* Next pointer in a linked list of sources of a value. */
146 ipcp_value_source
*next
;
147 /* If the jump function that resulted into his value was a pass-through or an
148 ancestor, this is the index of the parameter of the caller the jump
149 function references. */
153 /* Common ancestor for all ipcp_value instantiations. */
155 class ipcp_value_base
158 /* Time benefit and size cost that specializing the function for this value
159 would bring about in this function alone. */
160 int local_time_benefit
, local_size_cost
;
161 /* Time benefit and size cost that specializing the function for this value
162 can bring about in it's callees (transitively). */
163 int prop_time_benefit
, prop_size_cost
;
166 : local_time_benefit (0), local_size_cost (0),
167 prop_time_benefit (0), prop_size_cost (0) {}
170 /* Describes one particular value stored in struct ipcp_lattice. */
172 template <typename valtype
>
173 class ipcp_value
: public ipcp_value_base
176 /* The actual value for the given parameter. */
178 /* The list of sources from which this value originates. */
179 ipcp_value_source
<valtype
> *sources
;
180 /* Next pointers in a linked list of all values in a lattice. */
182 /* Next pointers in a linked list of values in a strongly connected component
184 ipcp_value
*scc_next
;
185 /* Next pointers in a linked list of SCCs of values sorted topologically
186 according their sources. */
187 ipcp_value
*topo_next
;
188 /* A specialized node created for this value, NULL if none has been (so far)
190 cgraph_node
*spec_node
;
191 /* Depth first search number and low link for topological sorting of
194 /* True if this valye is currently on the topo-sort stack. */
198 : sources (0), next (0), scc_next (0), topo_next (0),
199 spec_node (0), dfs (0), low_link (0), on_stack (false) {}
201 void add_source (cgraph_edge
*cs
, ipcp_value
*src_val
, int src_idx
,
202 HOST_WIDE_INT offset
);
205 /* Lattice describing potential values of a formal parameter of a function, or
206 a part of an aggregate. TOP is represented by a lattice with zero values
207 and with contains_variable and bottom flags cleared. BOTTOM is represented
208 by a lattice with the bottom flag set. In that case, values and
209 contains_variable flag should be disregarded. */
211 template <typename valtype
>
215 /* The list of known values and types in this lattice. Note that values are
216 not deallocated if a lattice is set to bottom because there may be value
217 sources referencing them. */
218 ipcp_value
<valtype
> *values
;
219 /* Number of known values and types in this lattice. */
221 /* The lattice contains a variable component (in addition to values). */
222 bool contains_variable
;
223 /* The value of the lattice is bottom (i.e. variable and unusable for any
227 inline bool is_single_const ();
228 inline bool set_to_bottom ();
229 inline bool set_contains_variable ();
230 bool add_value (valtype newval
, cgraph_edge
*cs
,
231 ipcp_value
<valtype
> *src_val
= NULL
,
232 int src_idx
= 0, HOST_WIDE_INT offset
= -1);
233 void print (FILE * f
, bool dump_sources
, bool dump_benefits
);
236 /* Lattice of tree values with an offset to describe a part of an
239 class ipcp_agg_lattice
: public ipcp_lattice
<tree
>
242 /* Offset that is being described by this lattice. */
243 HOST_WIDE_INT offset
;
244 /* Size so that we don't have to re-compute it every time we traverse the
245 list. Must correspond to TYPE_SIZE of all lat values. */
247 /* Next element of the linked list. */
248 struct ipcp_agg_lattice
*next
;
251 /* Lattice of known bits, only capable of holding one value.
252 Bitwise constant propagation propagates which bits of a
268 In the above case, the param 'x' will always have all
269 the bits (except the bits in lsb) set to 0.
270 Hence the mask of 'x' would be 0xff. The mask
271 reflects that the bits in lsb are unknown.
272 The actual propagated value is given by m_value & ~m_mask. */
274 class ipcp_bits_lattice
277 bool bottom_p () { return m_lattice_val
== IPA_BITS_VARYING
; }
278 bool top_p () { return m_lattice_val
== IPA_BITS_UNDEFINED
; }
279 bool constant_p () { return m_lattice_val
== IPA_BITS_CONSTANT
; }
280 bool set_to_bottom ();
281 bool set_to_constant (widest_int
, widest_int
);
283 widest_int
get_value () { return m_value
; }
284 widest_int
get_mask () { return m_mask
; }
286 bool meet_with (ipcp_bits_lattice
& other
, unsigned, signop
,
287 enum tree_code
, tree
);
289 bool meet_with (widest_int
, widest_int
, unsigned);
294 enum { IPA_BITS_UNDEFINED
, IPA_BITS_CONSTANT
, IPA_BITS_VARYING
} m_lattice_val
;
296 /* Similar to ccp_lattice_t, mask represents which bits of value are constant.
297 If a bit in mask is set to 0, then the corresponding bit in
298 value is known to be constant. */
299 widest_int m_value
, m_mask
;
301 bool meet_with_1 (widest_int
, widest_int
, unsigned);
302 void get_value_and_mask (tree
, widest_int
*, widest_int
*);
305 /* Lattice of value ranges. */
307 class ipcp_vr_lattice
312 inline bool bottom_p () const;
313 inline bool top_p () const;
314 inline bool set_to_bottom ();
315 bool meet_with (const value_range
*p_vr
);
316 bool meet_with (const ipcp_vr_lattice
&other
);
317 void init () { m_vr
.type
= VR_UNDEFINED
; }
318 void print (FILE * f
);
321 bool meet_with_1 (const value_range
*other_vr
);
324 /* Structure containing lattices for a parameter itself and for pieces of
325 aggregates that are passed in the parameter or by a reference in a parameter
326 plus some other useful flags. */
328 class ipcp_param_lattices
331 /* Lattice describing the value of the parameter itself. */
332 ipcp_lattice
<tree
> itself
;
333 /* Lattice describing the polymorphic contexts of a parameter. */
334 ipcp_lattice
<ipa_polymorphic_call_context
> ctxlat
;
335 /* Lattices describing aggregate parts. */
336 ipcp_agg_lattice
*aggs
;
337 /* Lattice describing known bits. */
338 ipcp_bits_lattice bits_lattice
;
339 /* Lattice describing value range. */
340 ipcp_vr_lattice m_value_range
;
341 /* Number of aggregate lattices */
343 /* True if aggregate data were passed by reference (as opposed to by
346 /* All aggregate lattices contain a variable component (in addition to
348 bool aggs_contain_variable
;
349 /* The value of all aggregate lattices is bottom (i.e. variable and unusable
350 for any propagation). */
353 /* There is a virtual call based on this parameter. */
357 /* Allocation pools for values and their sources in ipa-cp. */
359 object_allocator
<ipcp_value
<tree
> > ipcp_cst_values_pool
360 ("IPA-CP constant values");
362 object_allocator
<ipcp_value
<ipa_polymorphic_call_context
> >
363 ipcp_poly_ctx_values_pool ("IPA-CP polymorphic contexts");
365 object_allocator
<ipcp_value_source
<tree
> > ipcp_sources_pool
366 ("IPA-CP value sources");
368 object_allocator
<ipcp_agg_lattice
> ipcp_agg_lattice_pool
369 ("IPA_CP aggregate lattices");
371 /* Maximal count found in program. */
373 static profile_count max_count
;
375 /* Original overall size of the program. */
377 static long overall_size
, max_new_size
;
379 /* Return the param lattices structure corresponding to the Ith formal
380 parameter of the function described by INFO. */
381 static inline struct ipcp_param_lattices
*
382 ipa_get_parm_lattices (struct ipa_node_params
*info
, int i
)
384 gcc_assert (i
>= 0 && i
< ipa_get_param_count (info
));
385 gcc_checking_assert (!info
->ipcp_orig_node
);
386 gcc_checking_assert (info
->lattices
);
387 return &(info
->lattices
[i
]);
390 /* Return the lattice corresponding to the scalar value of the Ith formal
391 parameter of the function described by INFO. */
392 static inline ipcp_lattice
<tree
> *
393 ipa_get_scalar_lat (struct ipa_node_params
*info
, int i
)
395 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
396 return &plats
->itself
;
399 /* Return the lattice corresponding to the scalar value of the Ith formal
400 parameter of the function described by INFO. */
401 static inline ipcp_lattice
<ipa_polymorphic_call_context
> *
402 ipa_get_poly_ctx_lat (struct ipa_node_params
*info
, int i
)
404 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
405 return &plats
->ctxlat
;
408 /* Return 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 (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
*p_vr
)
914 return meet_with_1 (p_vr
);
917 /* Meet the current value of the lattice with value ranfge described by
921 ipcp_vr_lattice::meet_with_1 (const value_range
*other_vr
)
923 tree min
= m_vr
.min
, max
= m_vr
.max
;
924 value_range_type type
= m_vr
.type
;
929 if (other_vr
->type
== VR_VARYING
)
930 return set_to_bottom ();
932 vrp_meet (&m_vr
, other_vr
);
933 if (type
!= m_vr
.type
941 /* Return true if value range information in the lattice is yet unknown. */
944 ipcp_vr_lattice::top_p () const
946 return m_vr
.type
== VR_UNDEFINED
;
949 /* Return true if value range information in the lattice is known to be
953 ipcp_vr_lattice::bottom_p () const
955 return m_vr
.type
== VR_VARYING
;
958 /* Set value range information in the lattice to bottom. Return true if it
959 previously was in a different state. */
962 ipcp_vr_lattice::set_to_bottom ()
964 if (m_vr
.type
== VR_VARYING
)
966 m_vr
.type
= VR_VARYING
;
970 /* Set lattice value to bottom, if it already isn't the case. */
973 ipcp_bits_lattice::set_to_bottom ()
977 m_lattice_val
= IPA_BITS_VARYING
;
983 /* Set to constant if it isn't already. Only meant to be called
984 when switching state from TOP. */
987 ipcp_bits_lattice::set_to_constant (widest_int value
, widest_int mask
)
989 gcc_assert (top_p ());
990 m_lattice_val
= IPA_BITS_CONSTANT
;
996 /* Convert operand to value, mask form. */
999 ipcp_bits_lattice::get_value_and_mask (tree operand
, widest_int
*valuep
, widest_int
*maskp
)
1001 wide_int
get_nonzero_bits (const_tree
);
1003 if (TREE_CODE (operand
) == INTEGER_CST
)
1005 *valuep
= wi::to_widest (operand
);
1015 /* Meet operation, similar to ccp_lattice_meet, we xor values
1016 if this->value, value have different values at same bit positions, we want
1017 to drop that bit to varying. Return true if mask is changed.
1018 This function assumes that the lattice value is in CONSTANT state */
1021 ipcp_bits_lattice::meet_with_1 (widest_int value
, widest_int mask
,
1024 gcc_assert (constant_p ());
1026 widest_int old_mask
= m_mask
;
1027 m_mask
= (m_mask
| mask
) | (m_value
^ value
);
1029 if (wi::sext (m_mask
, precision
) == -1)
1030 return set_to_bottom ();
1032 return m_mask
!= old_mask
;
1035 /* Meet the bits lattice with operand
1036 described by <value, mask, sgn, precision. */
1039 ipcp_bits_lattice::meet_with (widest_int value
, widest_int mask
,
1047 if (wi::sext (mask
, precision
) == -1)
1048 return set_to_bottom ();
1049 return set_to_constant (value
, mask
);
1052 return meet_with_1 (value
, mask
, precision
);
1055 /* Meet bits lattice with the result of bit_value_binop (other, operand)
1056 if code is binary operation or bit_value_unop (other) if code is unary op.
1057 In the case when code is nop_expr, no adjustment is required. */
1060 ipcp_bits_lattice::meet_with (ipcp_bits_lattice
& other
, unsigned precision
,
1061 signop sgn
, enum tree_code code
, tree operand
)
1063 if (other
.bottom_p ())
1064 return set_to_bottom ();
1066 if (bottom_p () || other
.top_p ())
1069 widest_int adjusted_value
, adjusted_mask
;
1071 if (TREE_CODE_CLASS (code
) == tcc_binary
)
1073 tree type
= TREE_TYPE (operand
);
1074 gcc_assert (INTEGRAL_TYPE_P (type
));
1075 widest_int o_value
, o_mask
;
1076 get_value_and_mask (operand
, &o_value
, &o_mask
);
1078 bit_value_binop (code
, sgn
, precision
, &adjusted_value
, &adjusted_mask
,
1079 sgn
, precision
, other
.get_value (), other
.get_mask (),
1080 TYPE_SIGN (type
), TYPE_PRECISION (type
), o_value
, o_mask
);
1082 if (wi::sext (adjusted_mask
, precision
) == -1)
1083 return set_to_bottom ();
1086 else if (TREE_CODE_CLASS (code
) == tcc_unary
)
1088 bit_value_unop (code
, sgn
, precision
, &adjusted_value
,
1089 &adjusted_mask
, sgn
, precision
, other
.get_value (),
1092 if (wi::sext (adjusted_mask
, precision
) == -1)
1093 return set_to_bottom ();
1097 return set_to_bottom ();
1101 if (wi::sext (adjusted_mask
, precision
) == -1)
1102 return set_to_bottom ();
1103 return set_to_constant (adjusted_value
, adjusted_mask
);
1106 return meet_with_1 (adjusted_value
, adjusted_mask
, precision
);
1109 /* Mark bot aggregate and scalar lattices as containing an unknown variable,
1110 return true is any of them has not been marked as such so far. */
1113 set_all_contains_variable (struct ipcp_param_lattices
*plats
)
1116 ret
= plats
->itself
.set_contains_variable ();
1117 ret
|= plats
->ctxlat
.set_contains_variable ();
1118 ret
|= set_agg_lats_contain_variable (plats
);
1119 ret
|= plats
->bits_lattice
.set_to_bottom ();
1120 ret
|= plats
->m_value_range
.set_to_bottom ();
1124 /* Worker of call_for_symbol_thunks_and_aliases, increment the integer DATA
1125 points to by the number of callers to NODE. */
1128 count_callers (cgraph_node
*node
, void *data
)
1130 int *caller_count
= (int *) data
;
1132 for (cgraph_edge
*cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
1133 /* Local thunks can be handled transparently, but if the thunk can not
1134 be optimized out, count it as a real use. */
1135 if (!cs
->caller
->thunk
.thunk_p
|| !cs
->caller
->local
.local
)
1140 /* Worker of call_for_symbol_thunks_and_aliases, it is supposed to be called on
1141 the one caller of some other node. Set the caller's corresponding flag. */
1144 set_single_call_flag (cgraph_node
*node
, void *)
1146 cgraph_edge
*cs
= node
->callers
;
1147 /* Local thunks can be handled transparently, skip them. */
1148 while (cs
&& cs
->caller
->thunk
.thunk_p
&& cs
->caller
->local
.local
)
1149 cs
= cs
->next_caller
;
1152 IPA_NODE_REF (cs
->caller
)->node_calling_single_call
= true;
1158 /* Initialize ipcp_lattices. */
1161 initialize_node_lattices (struct cgraph_node
*node
)
1163 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1164 struct cgraph_edge
*ie
;
1165 bool disable
= false, variable
= false;
1168 gcc_checking_assert (node
->has_gimple_body_p ());
1169 if (node
->local
.local
)
1171 int caller_count
= 0;
1172 node
->call_for_symbol_thunks_and_aliases (count_callers
, &caller_count
,
1174 gcc_checking_assert (caller_count
> 0);
1175 if (caller_count
== 1)
1176 node
->call_for_symbol_thunks_and_aliases (set_single_call_flag
,
1181 /* When cloning is allowed, we can assume that externally visible
1182 functions are not called. We will compensate this by cloning
1184 if (ipcp_versionable_function_p (node
)
1185 && ipcp_cloning_candidate_p (node
))
1191 for (i
= 0; i
< ipa_get_param_count (info
); i
++)
1193 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1194 plats
->m_value_range
.init ();
1197 if (disable
|| variable
)
1199 for (i
= 0; i
< ipa_get_param_count (info
); i
++)
1201 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1204 plats
->itself
.set_to_bottom ();
1205 plats
->ctxlat
.set_to_bottom ();
1206 set_agg_lats_to_bottom (plats
);
1207 plats
->bits_lattice
.set_to_bottom ();
1208 plats
->m_value_range
.set_to_bottom ();
1211 set_all_contains_variable (plats
);
1213 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1214 && !node
->alias
&& !node
->thunk
.thunk_p
)
1215 fprintf (dump_file
, "Marking all lattices of %s as %s\n",
1216 node
->dump_name (), disable
? "BOTTOM" : "VARIABLE");
1219 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
1220 if (ie
->indirect_info
->polymorphic
1221 && ie
->indirect_info
->param_index
>= 0)
1223 gcc_checking_assert (ie
->indirect_info
->param_index
>= 0);
1224 ipa_get_parm_lattices (info
,
1225 ie
->indirect_info
->param_index
)->virt_call
= 1;
1229 /* Return the result of a (possibly arithmetic) pass through jump function
1230 JFUNC on the constant value INPUT. RES_TYPE is the type of the parameter
1231 to which the result is passed. Return NULL_TREE if that cannot be
1232 determined or be considered an interprocedural invariant. */
1235 ipa_get_jf_pass_through_result (struct ipa_jump_func
*jfunc
, tree input
,
1240 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
1242 if (!is_gimple_ip_invariant (input
))
1245 tree_code opcode
= ipa_get_jf_pass_through_operation (jfunc
);
1248 if (TREE_CODE_CLASS (opcode
) == tcc_comparison
)
1249 res_type
= boolean_type_node
;
1250 else if (expr_type_first_operand_type_p (opcode
))
1251 res_type
= TREE_TYPE (input
);
1256 if (TREE_CODE_CLASS (opcode
) == tcc_unary
)
1257 res
= fold_unary (opcode
, res_type
, input
);
1259 res
= fold_binary (opcode
, res_type
, input
,
1260 ipa_get_jf_pass_through_operand (jfunc
));
1262 if (res
&& !is_gimple_ip_invariant (res
))
1268 /* Return the result of an ancestor jump function JFUNC on the constant value
1269 INPUT. Return NULL_TREE if that cannot be determined. */
1272 ipa_get_jf_ancestor_result (struct ipa_jump_func
*jfunc
, tree input
)
1274 gcc_checking_assert (TREE_CODE (input
) != TREE_BINFO
);
1275 if (TREE_CODE (input
) == ADDR_EXPR
)
1277 tree t
= TREE_OPERAND (input
, 0);
1278 t
= build_ref_for_offset (EXPR_LOCATION (t
), t
,
1279 ipa_get_jf_ancestor_offset (jfunc
), false,
1280 ptr_type_node
, NULL
, false);
1281 return build_fold_addr_expr (t
);
1287 /* Determine whether JFUNC evaluates to a single known constant value and if
1288 so, return it. Otherwise return NULL. INFO describes the caller node or
1289 the one it is inlined to, so that pass-through jump functions can be
1290 evaluated. PARM_TYPE is the type of the parameter to which the result is
1294 ipa_value_from_jfunc (struct ipa_node_params
*info
, struct ipa_jump_func
*jfunc
,
1297 if (jfunc
->type
== IPA_JF_CONST
)
1298 return ipa_get_jf_constant (jfunc
);
1299 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1300 || jfunc
->type
== IPA_JF_ANCESTOR
)
1305 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1306 idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1308 idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1310 if (info
->ipcp_orig_node
)
1311 input
= info
->known_csts
[idx
];
1314 ipcp_lattice
<tree
> *lat
;
1317 || idx
>= ipa_get_param_count (info
))
1319 lat
= ipa_get_scalar_lat (info
, idx
);
1320 if (!lat
->is_single_const ())
1322 input
= lat
->values
->value
;
1328 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1329 return ipa_get_jf_pass_through_result (jfunc
, input
, parm_type
);
1331 return ipa_get_jf_ancestor_result (jfunc
, input
);
1337 /* Determie whether JFUNC evaluates to single known polymorphic context, given
1338 that INFO describes the caller node or the one it is inlined to, CS is the
1339 call graph edge corresponding to JFUNC and CSIDX index of the described
1342 ipa_polymorphic_call_context
1343 ipa_context_from_jfunc (ipa_node_params
*info
, cgraph_edge
*cs
, int csidx
,
1344 ipa_jump_func
*jfunc
)
1346 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
1347 ipa_polymorphic_call_context ctx
;
1348 ipa_polymorphic_call_context
*edge_ctx
1349 = cs
? ipa_get_ith_polymorhic_call_context (args
, csidx
) : NULL
;
1351 if (edge_ctx
&& !edge_ctx
->useless_p ())
1354 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1355 || jfunc
->type
== IPA_JF_ANCESTOR
)
1357 ipa_polymorphic_call_context srcctx
;
1359 bool type_preserved
= true;
1360 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1362 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1364 type_preserved
= ipa_get_jf_pass_through_type_preserved (jfunc
);
1365 srcidx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1369 type_preserved
= ipa_get_jf_ancestor_type_preserved (jfunc
);
1370 srcidx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1372 if (info
->ipcp_orig_node
)
1374 if (info
->known_contexts
.exists ())
1375 srcctx
= info
->known_contexts
[srcidx
];
1380 || srcidx
>= ipa_get_param_count (info
))
1382 ipcp_lattice
<ipa_polymorphic_call_context
> *lat
;
1383 lat
= ipa_get_poly_ctx_lat (info
, srcidx
);
1384 if (!lat
->is_single_const ())
1386 srcctx
= lat
->values
->value
;
1388 if (srcctx
.useless_p ())
1390 if (jfunc
->type
== IPA_JF_ANCESTOR
)
1391 srcctx
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
1392 if (!type_preserved
)
1393 srcctx
.possible_dynamic_type_change (cs
->in_polymorphic_cdtor
);
1394 srcctx
.combine_with (ctx
);
1401 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
1402 bottom, not containing a variable component and without any known value at
1406 ipcp_verify_propagated_values (void)
1408 struct cgraph_node
*node
;
1410 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
1412 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1413 int i
, count
= ipa_get_param_count (info
);
1415 for (i
= 0; i
< count
; i
++)
1417 ipcp_lattice
<tree
> *lat
= ipa_get_scalar_lat (info
, i
);
1420 && !lat
->contains_variable
1421 && lat
->values_count
== 0)
1425 symtab
->dump (dump_file
);
1426 fprintf (dump_file
, "\nIPA lattices after constant "
1427 "propagation, before gcc_unreachable:\n");
1428 print_all_lattices (dump_file
, true, false);
1437 /* Return true iff X and Y should be considered equal values by IPA-CP. */
1440 values_equal_for_ipcp_p (tree x
, tree y
)
1442 gcc_checking_assert (x
!= NULL_TREE
&& y
!= NULL_TREE
);
1447 if (TREE_CODE (x
) == ADDR_EXPR
1448 && TREE_CODE (y
) == ADDR_EXPR
1449 && TREE_CODE (TREE_OPERAND (x
, 0)) == CONST_DECL
1450 && TREE_CODE (TREE_OPERAND (y
, 0)) == CONST_DECL
)
1451 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x
, 0)),
1452 DECL_INITIAL (TREE_OPERAND (y
, 0)), 0);
1454 return operand_equal_p (x
, y
, 0);
1457 /* Return true iff X and Y should be considered equal contexts by IPA-CP. */
1460 values_equal_for_ipcp_p (ipa_polymorphic_call_context x
,
1461 ipa_polymorphic_call_context y
)
1463 return x
.equal_to (y
);
1467 /* Add a new value source to the value represented by THIS, marking that a
1468 value comes from edge CS and (if the underlying jump function is a
1469 pass-through or an ancestor one) from a caller value SRC_VAL of a caller
1470 parameter described by SRC_INDEX. OFFSET is negative if the source was the
1471 scalar value of the parameter itself or the offset within an aggregate. */
1473 template <typename valtype
>
1475 ipcp_value
<valtype
>::add_source (cgraph_edge
*cs
, ipcp_value
*src_val
,
1476 int src_idx
, HOST_WIDE_INT offset
)
1478 ipcp_value_source
<valtype
> *src
;
1480 src
= new (ipcp_sources_pool
.allocate ()) ipcp_value_source
<valtype
>;
1481 src
->offset
= offset
;
1484 src
->index
= src_idx
;
1486 src
->next
= sources
;
1490 /* Allocate a new ipcp_value holding a tree constant, initialize its value to
1491 SOURCE and clear all other fields. */
1493 static ipcp_value
<tree
> *
1494 allocate_and_init_ipcp_value (tree source
)
1496 ipcp_value
<tree
> *val
;
1498 val
= new (ipcp_cst_values_pool
.allocate ()) ipcp_value
<tree
>();
1499 val
->value
= source
;
1503 /* Allocate a new ipcp_value holding a polymorphic context, initialize its
1504 value to SOURCE and clear all other fields. */
1506 static ipcp_value
<ipa_polymorphic_call_context
> *
1507 allocate_and_init_ipcp_value (ipa_polymorphic_call_context source
)
1509 ipcp_value
<ipa_polymorphic_call_context
> *val
;
1512 val
= new (ipcp_poly_ctx_values_pool
.allocate ())
1513 ipcp_value
<ipa_polymorphic_call_context
>();
1514 val
->value
= source
;
1518 /* Try to add NEWVAL to LAT, potentially creating a new ipcp_value for it. CS,
1519 SRC_VAL SRC_INDEX and OFFSET are meant for add_source and have the same
1520 meaning. OFFSET -1 means the source is scalar and not a part of an
1523 template <typename valtype
>
1525 ipcp_lattice
<valtype
>::add_value (valtype newval
, cgraph_edge
*cs
,
1526 ipcp_value
<valtype
> *src_val
,
1527 int src_idx
, HOST_WIDE_INT offset
)
1529 ipcp_value
<valtype
> *val
;
1534 for (val
= values
; val
; val
= val
->next
)
1535 if (values_equal_for_ipcp_p (val
->value
, newval
))
1537 if (ipa_edge_within_scc (cs
))
1539 ipcp_value_source
<valtype
> *s
;
1540 for (s
= val
->sources
; s
; s
= s
->next
)
1547 val
->add_source (cs
, src_val
, src_idx
, offset
);
1551 if (values_count
== PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE
))
1553 /* We can only free sources, not the values themselves, because sources
1554 of other values in this SCC might point to them. */
1555 for (val
= values
; val
; val
= val
->next
)
1557 while (val
->sources
)
1559 ipcp_value_source
<valtype
> *src
= val
->sources
;
1560 val
->sources
= src
->next
;
1561 ipcp_sources_pool
.remove ((ipcp_value_source
<tree
>*)src
);
1566 return set_to_bottom ();
1570 val
= allocate_and_init_ipcp_value (newval
);
1571 val
->add_source (cs
, src_val
, src_idx
, offset
);
1577 /* Propagate values through a pass-through jump function JFUNC associated with
1578 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1579 is the index of the source parameter. PARM_TYPE is the type of the
1580 parameter to which the result is passed. */
1583 propagate_vals_across_pass_through (cgraph_edge
*cs
, ipa_jump_func
*jfunc
,
1584 ipcp_lattice
<tree
> *src_lat
,
1585 ipcp_lattice
<tree
> *dest_lat
, int src_idx
,
1588 ipcp_value
<tree
> *src_val
;
1591 /* Do not create new values when propagating within an SCC because if there
1592 are arithmetic functions with circular dependencies, there is infinite
1593 number of them and we would just make lattices bottom. If this condition
1594 is ever relaxed we have to detect self-feeding recursive calls in
1595 cgraph_edge_brings_value_p in a smarter way. */
1596 if ((ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1597 && ipa_edge_within_scc (cs
))
1598 ret
= dest_lat
->set_contains_variable ();
1600 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1602 tree cstval
= ipa_get_jf_pass_through_result (jfunc
, src_val
->value
,
1606 ret
|= dest_lat
->add_value (cstval
, cs
, src_val
, src_idx
);
1608 ret
|= dest_lat
->set_contains_variable ();
1614 /* Propagate values through an ancestor jump function JFUNC associated with
1615 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1616 is the index of the source parameter. */
1619 propagate_vals_across_ancestor (struct cgraph_edge
*cs
,
1620 struct ipa_jump_func
*jfunc
,
1621 ipcp_lattice
<tree
> *src_lat
,
1622 ipcp_lattice
<tree
> *dest_lat
, int src_idx
)
1624 ipcp_value
<tree
> *src_val
;
1627 if (ipa_edge_within_scc (cs
))
1628 return dest_lat
->set_contains_variable ();
1630 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1632 tree t
= ipa_get_jf_ancestor_result (jfunc
, src_val
->value
);
1635 ret
|= dest_lat
->add_value (t
, cs
, src_val
, src_idx
);
1637 ret
|= dest_lat
->set_contains_variable ();
1643 /* Propagate scalar values across jump function JFUNC that is associated with
1644 edge CS and put the values into DEST_LAT. PARM_TYPE is the type of the
1645 parameter to which the result is passed. */
1648 propagate_scalar_across_jump_function (struct cgraph_edge
*cs
,
1649 struct ipa_jump_func
*jfunc
,
1650 ipcp_lattice
<tree
> *dest_lat
,
1653 if (dest_lat
->bottom
)
1656 if (jfunc
->type
== IPA_JF_CONST
)
1658 tree val
= ipa_get_jf_constant (jfunc
);
1659 return dest_lat
->add_value (val
, cs
, NULL
, 0);
1661 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1662 || jfunc
->type
== IPA_JF_ANCESTOR
)
1664 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1665 ipcp_lattice
<tree
> *src_lat
;
1669 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1670 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1672 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1674 src_lat
= ipa_get_scalar_lat (caller_info
, src_idx
);
1675 if (src_lat
->bottom
)
1676 return dest_lat
->set_contains_variable ();
1678 /* If we would need to clone the caller and cannot, do not propagate. */
1679 if (!ipcp_versionable_function_p (cs
->caller
)
1680 && (src_lat
->contains_variable
1681 || (src_lat
->values_count
> 1)))
1682 return dest_lat
->set_contains_variable ();
1684 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1685 ret
= propagate_vals_across_pass_through (cs
, jfunc
, src_lat
,
1686 dest_lat
, src_idx
, param_type
);
1688 ret
= propagate_vals_across_ancestor (cs
, jfunc
, src_lat
, dest_lat
,
1691 if (src_lat
->contains_variable
)
1692 ret
|= dest_lat
->set_contains_variable ();
1697 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1698 use it for indirect inlining), we should propagate them too. */
1699 return dest_lat
->set_contains_variable ();
1702 /* Propagate scalar values across jump function JFUNC that is associated with
1703 edge CS and describes argument IDX and put the values into DEST_LAT. */
1706 propagate_context_across_jump_function (cgraph_edge
*cs
,
1707 ipa_jump_func
*jfunc
, int idx
,
1708 ipcp_lattice
<ipa_polymorphic_call_context
> *dest_lat
)
1710 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
1711 if (dest_lat
->bottom
)
1714 bool added_sth
= false;
1715 bool type_preserved
= true;
1717 ipa_polymorphic_call_context edge_ctx
, *edge_ctx_ptr
1718 = ipa_get_ith_polymorhic_call_context (args
, idx
);
1721 edge_ctx
= *edge_ctx_ptr
;
1723 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1724 || jfunc
->type
== IPA_JF_ANCESTOR
)
1726 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1728 ipcp_lattice
<ipa_polymorphic_call_context
> *src_lat
;
1730 /* TODO: Once we figure out how to propagate speculations, it will
1731 probably be a good idea to switch to speculation if type_preserved is
1732 not set instead of punting. */
1733 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1735 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1737 type_preserved
= ipa_get_jf_pass_through_type_preserved (jfunc
);
1738 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1742 type_preserved
= ipa_get_jf_ancestor_type_preserved (jfunc
);
1743 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1746 src_lat
= ipa_get_poly_ctx_lat (caller_info
, src_idx
);
1747 /* If we would need to clone the caller and cannot, do not propagate. */
1748 if (!ipcp_versionable_function_p (cs
->caller
)
1749 && (src_lat
->contains_variable
1750 || (src_lat
->values_count
> 1)))
1753 ipcp_value
<ipa_polymorphic_call_context
> *src_val
;
1754 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1756 ipa_polymorphic_call_context cur
= src_val
->value
;
1758 if (!type_preserved
)
1759 cur
.possible_dynamic_type_change (cs
->in_polymorphic_cdtor
);
1760 if (jfunc
->type
== IPA_JF_ANCESTOR
)
1761 cur
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
1762 /* TODO: In cases we know how the context is going to be used,
1763 we can improve the result by passing proper OTR_TYPE. */
1764 cur
.combine_with (edge_ctx
);
1765 if (!cur
.useless_p ())
1767 if (src_lat
->contains_variable
1768 && !edge_ctx
.equal_to (cur
))
1769 ret
|= dest_lat
->set_contains_variable ();
1770 ret
|= dest_lat
->add_value (cur
, cs
, src_val
, src_idx
);
1780 if (!edge_ctx
.useless_p ())
1781 ret
|= dest_lat
->add_value (edge_ctx
, cs
);
1783 ret
|= dest_lat
->set_contains_variable ();
1789 /* Propagate bits across jfunc that is associated with
1790 edge cs and update dest_lattice accordingly. */
1793 propagate_bits_across_jump_function (cgraph_edge
*cs
, int idx
,
1794 ipa_jump_func
*jfunc
,
1795 ipcp_bits_lattice
*dest_lattice
)
1797 if (dest_lattice
->bottom_p ())
1800 enum availability availability
;
1801 cgraph_node
*callee
= cs
->callee
->function_symbol (&availability
);
1802 struct ipa_node_params
*callee_info
= IPA_NODE_REF (callee
);
1803 tree parm_type
= ipa_get_type (callee_info
, idx
);
1805 /* For K&R C programs, ipa_get_type() could return NULL_TREE. Avoid the
1806 transform for these cases. Similarly, we can have bad type mismatches
1807 with LTO, avoid doing anything with those too. */
1809 || (!INTEGRAL_TYPE_P (parm_type
) && !POINTER_TYPE_P (parm_type
)))
1811 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1812 fprintf (dump_file
, "Setting dest_lattice to bottom, because type of "
1813 "param %i of %s is NULL or unsuitable for bits propagation\n",
1814 idx
, cs
->callee
->name ());
1816 return dest_lattice
->set_to_bottom ();
1819 unsigned precision
= TYPE_PRECISION (parm_type
);
1820 signop sgn
= TYPE_SIGN (parm_type
);
1822 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1823 || jfunc
->type
== IPA_JF_ANCESTOR
)
1825 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1826 tree operand
= NULL_TREE
;
1827 enum tree_code code
;
1830 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1832 code
= ipa_get_jf_pass_through_operation (jfunc
);
1833 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1834 if (code
!= NOP_EXPR
)
1835 operand
= ipa_get_jf_pass_through_operand (jfunc
);
1839 code
= POINTER_PLUS_EXPR
;
1840 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1841 unsigned HOST_WIDE_INT offset
= ipa_get_jf_ancestor_offset (jfunc
) / BITS_PER_UNIT
;
1842 operand
= build_int_cstu (size_type_node
, offset
);
1845 struct ipcp_param_lattices
*src_lats
1846 = ipa_get_parm_lattices (caller_info
, src_idx
);
1848 /* Try to propagate bits if src_lattice is bottom, but jfunc is known.
1854 Assume lattice for x is bottom, however we can still propagate
1855 result of x & 0xff == 0xff, which gets computed during ccp1 pass
1856 and we store it in jump function during analysis stage. */
1858 if (src_lats
->bits_lattice
.bottom_p ()
1860 return dest_lattice
->meet_with (jfunc
->bits
->value
, jfunc
->bits
->mask
,
1863 return dest_lattice
->meet_with (src_lats
->bits_lattice
, precision
, sgn
,
1867 else if (jfunc
->type
== IPA_JF_ANCESTOR
)
1868 return dest_lattice
->set_to_bottom ();
1869 else if (jfunc
->bits
)
1870 return dest_lattice
->meet_with (jfunc
->bits
->value
, jfunc
->bits
->mask
,
1873 return dest_lattice
->set_to_bottom ();
1876 /* Emulate effects of unary OPERATION and/or conversion from SRC_TYPE to
1877 DST_TYPE on value range in SRC_VR and store it to DST_VR. Return true if
1878 the result is a range or an anti-range. */
1881 ipa_vr_operation_and_type_effects (value_range
*dst_vr
, value_range
*src_vr
,
1882 enum tree_code operation
,
1883 tree dst_type
, tree src_type
)
1885 memset (dst_vr
, 0, sizeof (*dst_vr
));
1886 extract_range_from_unary_expr (dst_vr
, operation
, dst_type
, src_vr
, src_type
);
1887 if (dst_vr
->type
== VR_RANGE
|| dst_vr
->type
== VR_ANTI_RANGE
)
1893 /* Propagate value range across jump function JFUNC that is associated with
1894 edge CS with param of callee of PARAM_TYPE and update DEST_PLATS
1898 propagate_vr_across_jump_function (cgraph_edge
*cs
, ipa_jump_func
*jfunc
,
1899 struct ipcp_param_lattices
*dest_plats
,
1902 ipcp_vr_lattice
*dest_lat
= &dest_plats
->m_value_range
;
1904 if (dest_lat
->bottom_p ())
1908 || (!INTEGRAL_TYPE_P (param_type
)
1909 && !POINTER_TYPE_P (param_type
)))
1910 return dest_lat
->set_to_bottom ();
1912 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1914 enum tree_code operation
= ipa_get_jf_pass_through_operation (jfunc
);
1916 if (TREE_CODE_CLASS (operation
) == tcc_unary
)
1918 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1919 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1920 tree operand_type
= ipa_get_type (caller_info
, src_idx
);
1921 struct ipcp_param_lattices
*src_lats
1922 = ipa_get_parm_lattices (caller_info
, src_idx
);
1924 if (src_lats
->m_value_range
.bottom_p ())
1925 return dest_lat
->set_to_bottom ();
1927 if (ipa_vr_operation_and_type_effects (&vr
,
1928 &src_lats
->m_value_range
.m_vr
,
1929 operation
, param_type
,
1931 return dest_lat
->meet_with (&vr
);
1934 else if (jfunc
->type
== IPA_JF_CONST
)
1936 tree val
= ipa_get_jf_constant (jfunc
);
1937 if (TREE_CODE (val
) == INTEGER_CST
)
1939 val
= fold_convert (param_type
, val
);
1940 if (TREE_OVERFLOW_P (val
))
1941 val
= drop_tree_overflow (val
);
1944 memset (&tmpvr
, 0, sizeof (tmpvr
));
1945 tmpvr
.type
= VR_RANGE
;
1948 return dest_lat
->meet_with (&tmpvr
);
1954 && ipa_vr_operation_and_type_effects (&vr
, jfunc
->m_vr
, NOP_EXPR
,
1956 TREE_TYPE (jfunc
->m_vr
->min
)))
1957 return dest_lat
->meet_with (&vr
);
1959 return dest_lat
->set_to_bottom ();
1962 /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
1963 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
1964 other cases, return false). If there are no aggregate items, set
1965 aggs_by_ref to NEW_AGGS_BY_REF. */
1968 set_check_aggs_by_ref (struct ipcp_param_lattices
*dest_plats
,
1969 bool new_aggs_by_ref
)
1971 if (dest_plats
->aggs
)
1973 if (dest_plats
->aggs_by_ref
!= new_aggs_by_ref
)
1975 set_agg_lats_to_bottom (dest_plats
);
1980 dest_plats
->aggs_by_ref
= new_aggs_by_ref
;
1984 /* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
1985 already existing lattice for the given OFFSET and SIZE, marking all skipped
1986 lattices as containing variable and checking for overlaps. If there is no
1987 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
1988 it with offset, size and contains_variable to PRE_EXISTING, and return true,
1989 unless there are too many already. If there are two many, return false. If
1990 there are overlaps turn whole DEST_PLATS to bottom and return false. If any
1991 skipped lattices were newly marked as containing variable, set *CHANGE to
1995 merge_agg_lats_step (struct ipcp_param_lattices
*dest_plats
,
1996 HOST_WIDE_INT offset
, HOST_WIDE_INT val_size
,
1997 struct ipcp_agg_lattice
***aglat
,
1998 bool pre_existing
, bool *change
)
2000 gcc_checking_assert (offset
>= 0);
2002 while (**aglat
&& (**aglat
)->offset
< offset
)
2004 if ((**aglat
)->offset
+ (**aglat
)->size
> offset
)
2006 set_agg_lats_to_bottom (dest_plats
);
2009 *change
|= (**aglat
)->set_contains_variable ();
2010 *aglat
= &(**aglat
)->next
;
2013 if (**aglat
&& (**aglat
)->offset
== offset
)
2015 if ((**aglat
)->size
!= val_size
2017 && (**aglat
)->next
->offset
< offset
+ val_size
))
2019 set_agg_lats_to_bottom (dest_plats
);
2022 gcc_checking_assert (!(**aglat
)->next
2023 || (**aglat
)->next
->offset
>= offset
+ val_size
);
2028 struct ipcp_agg_lattice
*new_al
;
2030 if (**aglat
&& (**aglat
)->offset
< offset
+ val_size
)
2032 set_agg_lats_to_bottom (dest_plats
);
2035 if (dest_plats
->aggs_count
== PARAM_VALUE (PARAM_IPA_MAX_AGG_ITEMS
))
2037 dest_plats
->aggs_count
++;
2038 new_al
= ipcp_agg_lattice_pool
.allocate ();
2039 memset (new_al
, 0, sizeof (*new_al
));
2041 new_al
->offset
= offset
;
2042 new_al
->size
= val_size
;
2043 new_al
->contains_variable
= pre_existing
;
2045 new_al
->next
= **aglat
;
2051 /* Set all AGLAT and all other aggregate lattices reachable by next pointers as
2052 containing an unknown value. */
2055 set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice
*aglat
)
2060 ret
|= aglat
->set_contains_variable ();
2061 aglat
= aglat
->next
;
2066 /* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
2067 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source
2068 parameter used for lattice value sources. Return true if DEST_PLATS changed
2072 merge_aggregate_lattices (struct cgraph_edge
*cs
,
2073 struct ipcp_param_lattices
*dest_plats
,
2074 struct ipcp_param_lattices
*src_plats
,
2075 int src_idx
, HOST_WIDE_INT offset_delta
)
2077 bool pre_existing
= dest_plats
->aggs
!= NULL
;
2078 struct ipcp_agg_lattice
**dst_aglat
;
2081 if (set_check_aggs_by_ref (dest_plats
, src_plats
->aggs_by_ref
))
2083 if (src_plats
->aggs_bottom
)
2084 return set_agg_lats_contain_variable (dest_plats
);
2085 if (src_plats
->aggs_contain_variable
)
2086 ret
|= set_agg_lats_contain_variable (dest_plats
);
2087 dst_aglat
= &dest_plats
->aggs
;
2089 for (struct ipcp_agg_lattice
*src_aglat
= src_plats
->aggs
;
2091 src_aglat
= src_aglat
->next
)
2093 HOST_WIDE_INT new_offset
= src_aglat
->offset
- offset_delta
;
2097 if (merge_agg_lats_step (dest_plats
, new_offset
, src_aglat
->size
,
2098 &dst_aglat
, pre_existing
, &ret
))
2100 struct ipcp_agg_lattice
*new_al
= *dst_aglat
;
2102 dst_aglat
= &(*dst_aglat
)->next
;
2103 if (src_aglat
->bottom
)
2105 ret
|= new_al
->set_contains_variable ();
2108 if (src_aglat
->contains_variable
)
2109 ret
|= new_al
->set_contains_variable ();
2110 for (ipcp_value
<tree
> *val
= src_aglat
->values
;
2113 ret
|= new_al
->add_value (val
->value
, cs
, val
, src_idx
,
2116 else if (dest_plats
->aggs_bottom
)
2119 ret
|= set_chain_of_aglats_contains_variable (*dst_aglat
);
2123 /* Determine whether there is anything to propagate FROM SRC_PLATS through a
2124 pass-through JFUNC and if so, whether it has conform and conforms to the
2125 rules about propagating values passed by reference. */
2128 agg_pass_through_permissible_p (struct ipcp_param_lattices
*src_plats
,
2129 struct ipa_jump_func
*jfunc
)
2131 return src_plats
->aggs
2132 && (!src_plats
->aggs_by_ref
2133 || ipa_get_jf_pass_through_agg_preserved (jfunc
));
2136 /* Propagate scalar values across jump function JFUNC that is associated with
2137 edge CS and put the values into DEST_LAT. */
2140 propagate_aggs_across_jump_function (struct cgraph_edge
*cs
,
2141 struct ipa_jump_func
*jfunc
,
2142 struct ipcp_param_lattices
*dest_plats
)
2146 if (dest_plats
->aggs_bottom
)
2149 if (jfunc
->type
== IPA_JF_PASS_THROUGH
2150 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
2152 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2153 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
2154 struct ipcp_param_lattices
*src_plats
;
2156 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2157 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
2159 /* Currently we do not produce clobber aggregate jump
2160 functions, replace with merging when we do. */
2161 gcc_assert (!jfunc
->agg
.items
);
2162 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
,
2166 ret
|= set_agg_lats_contain_variable (dest_plats
);
2168 else if (jfunc
->type
== IPA_JF_ANCESTOR
2169 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
2171 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2172 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
2173 struct ipcp_param_lattices
*src_plats
;
2175 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2176 if (src_plats
->aggs
&& src_plats
->aggs_by_ref
)
2178 /* Currently we do not produce clobber aggregate jump
2179 functions, replace with merging when we do. */
2180 gcc_assert (!jfunc
->agg
.items
);
2181 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
, src_idx
,
2182 ipa_get_jf_ancestor_offset (jfunc
));
2184 else if (!src_plats
->aggs_by_ref
)
2185 ret
|= set_agg_lats_to_bottom (dest_plats
);
2187 ret
|= set_agg_lats_contain_variable (dest_plats
);
2189 else if (jfunc
->agg
.items
)
2191 bool pre_existing
= dest_plats
->aggs
!= NULL
;
2192 struct ipcp_agg_lattice
**aglat
= &dest_plats
->aggs
;
2193 struct ipa_agg_jf_item
*item
;
2196 if (set_check_aggs_by_ref (dest_plats
, jfunc
->agg
.by_ref
))
2199 FOR_EACH_VEC_ELT (*jfunc
->agg
.items
, i
, item
)
2201 HOST_WIDE_INT val_size
;
2203 if (item
->offset
< 0)
2205 gcc_checking_assert (is_gimple_ip_invariant (item
->value
));
2206 val_size
= tree_to_uhwi (TYPE_SIZE (TREE_TYPE (item
->value
)));
2208 if (merge_agg_lats_step (dest_plats
, item
->offset
, val_size
,
2209 &aglat
, pre_existing
, &ret
))
2211 ret
|= (*aglat
)->add_value (item
->value
, cs
, NULL
, 0, 0);
2212 aglat
= &(*aglat
)->next
;
2214 else if (dest_plats
->aggs_bottom
)
2218 ret
|= set_chain_of_aglats_contains_variable (*aglat
);
2221 ret
|= set_agg_lats_contain_variable (dest_plats
);
2226 /* Return true if on the way cfrom CS->caller to the final (non-alias and
2227 non-thunk) destination, the call passes through a thunk. */
2230 call_passes_through_thunk_p (cgraph_edge
*cs
)
2232 cgraph_node
*alias_or_thunk
= cs
->callee
;
2233 while (alias_or_thunk
->alias
)
2234 alias_or_thunk
= alias_or_thunk
->get_alias_target ();
2235 return alias_or_thunk
->thunk
.thunk_p
;
2238 /* Propagate constants from the caller to the callee of CS. INFO describes the
2242 propagate_constants_across_call (struct cgraph_edge
*cs
)
2244 struct ipa_node_params
*callee_info
;
2245 enum availability availability
;
2246 cgraph_node
*callee
;
2247 struct ipa_edge_args
*args
;
2249 int i
, args_count
, parms_count
;
2251 callee
= cs
->callee
->function_symbol (&availability
);
2252 if (!callee
->definition
)
2254 gcc_checking_assert (callee
->has_gimple_body_p ());
2255 callee_info
= IPA_NODE_REF (callee
);
2257 args
= IPA_EDGE_REF (cs
);
2258 args_count
= ipa_get_cs_argument_count (args
);
2259 parms_count
= ipa_get_param_count (callee_info
);
2260 if (parms_count
== 0)
2263 /* If this call goes through a thunk we must not propagate to the first (0th)
2264 parameter. However, we might need to uncover a thunk from below a series
2265 of aliases first. */
2266 if (call_passes_through_thunk_p (cs
))
2268 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
2275 for (; (i
< args_count
) && (i
< parms_count
); i
++)
2277 struct ipa_jump_func
*jump_func
= ipa_get_ith_jump_func (args
, i
);
2278 struct ipcp_param_lattices
*dest_plats
;
2279 tree param_type
= ipa_get_type (callee_info
, i
);
2281 dest_plats
= ipa_get_parm_lattices (callee_info
, i
);
2282 if (availability
== AVAIL_INTERPOSABLE
)
2283 ret
|= set_all_contains_variable (dest_plats
);
2286 ret
|= propagate_scalar_across_jump_function (cs
, jump_func
,
2287 &dest_plats
->itself
,
2289 ret
|= propagate_context_across_jump_function (cs
, jump_func
, i
,
2290 &dest_plats
->ctxlat
);
2292 |= propagate_bits_across_jump_function (cs
, i
, jump_func
,
2293 &dest_plats
->bits_lattice
);
2294 ret
|= propagate_aggs_across_jump_function (cs
, jump_func
,
2296 if (opt_for_fn (callee
->decl
, flag_ipa_vrp
))
2297 ret
|= propagate_vr_across_jump_function (cs
, jump_func
,
2298 dest_plats
, param_type
);
2300 ret
|= dest_plats
->m_value_range
.set_to_bottom ();
2303 for (; i
< parms_count
; i
++)
2304 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
, i
));
2309 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
2310 KNOWN_CONTEXTS, KNOWN_AGGS or AGG_REPS return the destination. The latter
2311 three can be NULL. If AGG_REPS is not NULL, KNOWN_AGGS is ignored. */
2314 ipa_get_indirect_edge_target_1 (struct cgraph_edge
*ie
,
2315 vec
<tree
> known_csts
,
2316 vec
<ipa_polymorphic_call_context
> known_contexts
,
2317 vec
<ipa_agg_jump_function_p
> known_aggs
,
2318 struct ipa_agg_replacement_value
*agg_reps
,
2321 int param_index
= ie
->indirect_info
->param_index
;
2322 HOST_WIDE_INT anc_offset
;
2326 *speculative
= false;
2328 if (param_index
== -1
2329 || known_csts
.length () <= (unsigned int) param_index
)
2332 if (!ie
->indirect_info
->polymorphic
)
2336 if (ie
->indirect_info
->agg_contents
)
2339 if (agg_reps
&& ie
->indirect_info
->guaranteed_unmodified
)
2343 if (agg_reps
->index
== param_index
2344 && agg_reps
->offset
== ie
->indirect_info
->offset
2345 && agg_reps
->by_ref
== ie
->indirect_info
->by_ref
)
2347 t
= agg_reps
->value
;
2350 agg_reps
= agg_reps
->next
;
2355 struct ipa_agg_jump_function
*agg
;
2356 if (known_aggs
.length () > (unsigned int) param_index
)
2357 agg
= known_aggs
[param_index
];
2360 bool from_global_constant
;
2361 t
= ipa_find_agg_cst_for_param (agg
, known_csts
[param_index
],
2362 ie
->indirect_info
->offset
,
2363 ie
->indirect_info
->by_ref
,
2364 &from_global_constant
);
2366 && !from_global_constant
2367 && !ie
->indirect_info
->guaranteed_unmodified
)
2372 t
= known_csts
[param_index
];
2375 && TREE_CODE (t
) == ADDR_EXPR
2376 && TREE_CODE (TREE_OPERAND (t
, 0)) == FUNCTION_DECL
)
2377 return TREE_OPERAND (t
, 0);
2382 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize
))
2385 gcc_assert (!ie
->indirect_info
->agg_contents
);
2386 anc_offset
= ie
->indirect_info
->offset
;
2390 /* Try to work out value of virtual table pointer value in replacemnets. */
2391 if (!t
&& agg_reps
&& !ie
->indirect_info
->by_ref
)
2395 if (agg_reps
->index
== param_index
2396 && agg_reps
->offset
== ie
->indirect_info
->offset
2397 && agg_reps
->by_ref
)
2399 t
= agg_reps
->value
;
2402 agg_reps
= agg_reps
->next
;
2406 /* Try to work out value of virtual table pointer value in known
2407 aggregate values. */
2408 if (!t
&& known_aggs
.length () > (unsigned int) param_index
2409 && !ie
->indirect_info
->by_ref
)
2411 struct ipa_agg_jump_function
*agg
;
2412 agg
= known_aggs
[param_index
];
2413 t
= ipa_find_agg_cst_for_param (agg
, known_csts
[param_index
],
2414 ie
->indirect_info
->offset
, true);
2417 /* If we found the virtual table pointer, lookup the target. */
2421 unsigned HOST_WIDE_INT offset
;
2422 if (vtable_pointer_value_to_vtable (t
, &vtable
, &offset
))
2425 target
= gimple_get_virt_method_for_vtable (ie
->indirect_info
->otr_token
,
2426 vtable
, offset
, &can_refer
);
2430 || (TREE_CODE (TREE_TYPE (target
)) == FUNCTION_TYPE
2431 && DECL_FUNCTION_CODE (target
) == BUILT_IN_UNREACHABLE
)
2432 || !possible_polymorphic_call_target_p
2433 (ie
, cgraph_node::get (target
)))
2435 /* Do not speculate builtin_unreachable, it is stupid! */
2436 if (ie
->indirect_info
->vptr_changed
)
2438 target
= ipa_impossible_devirt_target (ie
, target
);
2440 *speculative
= ie
->indirect_info
->vptr_changed
;
2447 /* Do we know the constant value of pointer? */
2449 t
= known_csts
[param_index
];
2451 gcc_checking_assert (!t
|| TREE_CODE (t
) != TREE_BINFO
);
2453 ipa_polymorphic_call_context context
;
2454 if (known_contexts
.length () > (unsigned int) param_index
)
2456 context
= known_contexts
[param_index
];
2457 context
.offset_by (anc_offset
);
2458 if (ie
->indirect_info
->vptr_changed
)
2459 context
.possible_dynamic_type_change (ie
->in_polymorphic_cdtor
,
2460 ie
->indirect_info
->otr_type
);
2463 ipa_polymorphic_call_context ctx2
= ipa_polymorphic_call_context
2464 (t
, ie
->indirect_info
->otr_type
, anc_offset
);
2465 if (!ctx2
.useless_p ())
2466 context
.combine_with (ctx2
, ie
->indirect_info
->otr_type
);
2471 context
= ipa_polymorphic_call_context (t
, ie
->indirect_info
->otr_type
,
2473 if (ie
->indirect_info
->vptr_changed
)
2474 context
.possible_dynamic_type_change (ie
->in_polymorphic_cdtor
,
2475 ie
->indirect_info
->otr_type
);
2480 vec
<cgraph_node
*>targets
;
2483 targets
= possible_polymorphic_call_targets
2484 (ie
->indirect_info
->otr_type
,
2485 ie
->indirect_info
->otr_token
,
2487 if (!final
|| targets
.length () > 1)
2489 struct cgraph_node
*node
;
2492 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize_speculatively
)
2493 || ie
->speculative
|| !ie
->maybe_hot_p ())
2495 node
= try_speculative_devirtualization (ie
->indirect_info
->otr_type
,
2496 ie
->indirect_info
->otr_token
,
2500 *speculative
= true;
2501 target
= node
->decl
;
2508 *speculative
= false;
2509 if (targets
.length () == 1)
2510 target
= targets
[0]->decl
;
2512 target
= ipa_impossible_devirt_target (ie
, NULL_TREE
);
2515 if (target
&& !possible_polymorphic_call_target_p (ie
,
2516 cgraph_node::get (target
)))
2520 target
= ipa_impossible_devirt_target (ie
, target
);
2527 /* If an indirect edge IE can be turned into a direct one based on KNOWN_CSTS,
2528 KNOWN_CONTEXTS (which can be vNULL) or KNOWN_AGGS (which also can be vNULL)
2529 return the destination. */
2532 ipa_get_indirect_edge_target (struct cgraph_edge
*ie
,
2533 vec
<tree
> known_csts
,
2534 vec
<ipa_polymorphic_call_context
> known_contexts
,
2535 vec
<ipa_agg_jump_function_p
> known_aggs
,
2538 return ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
2539 known_aggs
, NULL
, speculative
);
2542 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
2543 and KNOWN_CONTEXTS. */
2546 devirtualization_time_bonus (struct cgraph_node
*node
,
2547 vec
<tree
> known_csts
,
2548 vec
<ipa_polymorphic_call_context
> known_contexts
,
2549 vec
<ipa_agg_jump_function_p
> known_aggs
)
2551 struct cgraph_edge
*ie
;
2554 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
2556 struct cgraph_node
*callee
;
2557 struct ipa_fn_summary
*isummary
;
2558 enum availability avail
;
2562 target
= ipa_get_indirect_edge_target (ie
, known_csts
, known_contexts
,
2563 known_aggs
, &speculative
);
2567 /* Only bare minimum benefit for clearly un-inlineable targets. */
2569 callee
= cgraph_node::get (target
);
2570 if (!callee
|| !callee
->definition
)
2572 callee
= callee
->function_symbol (&avail
);
2573 if (avail
< AVAIL_AVAILABLE
)
2575 isummary
= ipa_fn_summaries
->get (callee
);
2576 if (!isummary
->inlinable
)
2579 /* FIXME: The values below need re-considering and perhaps also
2580 integrating into the cost metrics, at lest in some very basic way. */
2581 if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 4)
2582 res
+= 31 / ((int)speculative
+ 1);
2583 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 2)
2584 res
+= 15 / ((int)speculative
+ 1);
2585 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
2586 || DECL_DECLARED_INLINE_P (callee
->decl
))
2587 res
+= 7 / ((int)speculative
+ 1);
2593 /* Return time bonus incurred because of HINTS. */
2596 hint_time_bonus (ipa_hints hints
)
2599 if (hints
& (INLINE_HINT_loop_iterations
| INLINE_HINT_loop_stride
))
2600 result
+= PARAM_VALUE (PARAM_IPA_CP_LOOP_HINT_BONUS
);
2601 if (hints
& INLINE_HINT_array_index
)
2602 result
+= PARAM_VALUE (PARAM_IPA_CP_ARRAY_INDEX_HINT_BONUS
);
2606 /* If there is a reason to penalize the function described by INFO in the
2607 cloning goodness evaluation, do so. */
2609 static inline int64_t
2610 incorporate_penalties (ipa_node_params
*info
, int64_t evaluation
)
2612 if (info
->node_within_scc
)
2613 evaluation
= (evaluation
2614 * (100 - PARAM_VALUE (PARAM_IPA_CP_RECURSION_PENALTY
))) / 100;
2616 if (info
->node_calling_single_call
)
2617 evaluation
= (evaluation
2618 * (100 - PARAM_VALUE (PARAM_IPA_CP_SINGLE_CALL_PENALTY
)))
2624 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
2625 and SIZE_COST and with the sum of frequencies of incoming edges to the
2626 potential new clone in FREQUENCIES. */
2629 good_cloning_opportunity_p (struct cgraph_node
*node
, int time_benefit
,
2630 int freq_sum
, profile_count count_sum
, int size_cost
)
2632 if (time_benefit
== 0
2633 || !opt_for_fn (node
->decl
, flag_ipa_cp_clone
)
2634 || node
->optimize_for_size_p ())
2637 gcc_assert (size_cost
> 0);
2639 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2640 if (max_count
> profile_count::zero ())
2642 int factor
= RDIV (count_sum
.probability_in
2643 (max_count
).to_reg_br_prob_base ()
2644 * 1000, REG_BR_PROB_BASE
);
2645 int64_t evaluation
= (((int64_t) time_benefit
* factor
)
2647 evaluation
= incorporate_penalties (info
, evaluation
);
2649 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2651 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
2652 "size: %i, count_sum: ", time_benefit
, size_cost
);
2653 count_sum
.dump (dump_file
);
2654 fprintf (dump_file
, "%s%s) -> evaluation: " "%" PRId64
2655 ", threshold: %i\n",
2656 info
->node_within_scc
? ", scc" : "",
2657 info
->node_calling_single_call
? ", single_call" : "",
2658 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
2661 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
2665 int64_t evaluation
= (((int64_t) time_benefit
* freq_sum
)
2667 evaluation
= incorporate_penalties (info
, evaluation
);
2669 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2670 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
2671 "size: %i, freq_sum: %i%s%s) -> evaluation: "
2672 "%" PRId64
", threshold: %i\n",
2673 time_benefit
, size_cost
, freq_sum
,
2674 info
->node_within_scc
? ", scc" : "",
2675 info
->node_calling_single_call
? ", single_call" : "",
2676 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
2678 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
2682 /* Return all context independent values from aggregate lattices in PLATS in a
2683 vector. Return NULL if there are none. */
2685 static vec
<ipa_agg_jf_item
, va_gc
> *
2686 context_independent_aggregate_values (struct ipcp_param_lattices
*plats
)
2688 vec
<ipa_agg_jf_item
, va_gc
> *res
= NULL
;
2690 if (plats
->aggs_bottom
2691 || plats
->aggs_contain_variable
2692 || plats
->aggs_count
== 0)
2695 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
;
2697 aglat
= aglat
->next
)
2698 if (aglat
->is_single_const ())
2700 struct ipa_agg_jf_item item
;
2701 item
.offset
= aglat
->offset
;
2702 item
.value
= aglat
->values
->value
;
2703 vec_safe_push (res
, item
);
2708 /* Allocate KNOWN_CSTS, KNOWN_CONTEXTS and, if non-NULL, KNOWN_AGGS and
2709 populate them with values of parameters that are known independent of the
2710 context. INFO describes the function. If REMOVABLE_PARAMS_COST is
2711 non-NULL, the movement cost of all removable parameters will be stored in
2715 gather_context_independent_values (struct ipa_node_params
*info
,
2716 vec
<tree
> *known_csts
,
2717 vec
<ipa_polymorphic_call_context
>
2719 vec
<ipa_agg_jump_function
> *known_aggs
,
2720 int *removable_params_cost
)
2722 int i
, count
= ipa_get_param_count (info
);
2725 known_csts
->create (0);
2726 known_contexts
->create (0);
2727 known_csts
->safe_grow_cleared (count
);
2728 known_contexts
->safe_grow_cleared (count
);
2731 known_aggs
->create (0);
2732 known_aggs
->safe_grow_cleared (count
);
2735 if (removable_params_cost
)
2736 *removable_params_cost
= 0;
2738 for (i
= 0; i
< count
; i
++)
2740 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2741 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
2743 if (lat
->is_single_const ())
2745 ipcp_value
<tree
> *val
= lat
->values
;
2746 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
2747 (*known_csts
)[i
] = val
->value
;
2748 if (removable_params_cost
)
2749 *removable_params_cost
2750 += estimate_move_cost (TREE_TYPE (val
->value
), false);
2753 else if (removable_params_cost
2754 && !ipa_is_param_used (info
, i
))
2755 *removable_params_cost
2756 += ipa_get_param_move_cost (info
, i
);
2758 if (!ipa_is_param_used (info
, i
))
2761 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
2762 /* Do not account known context as reason for cloning. We can see
2763 if it permits devirtualization. */
2764 if (ctxlat
->is_single_const ())
2765 (*known_contexts
)[i
] = ctxlat
->values
->value
;
2769 vec
<ipa_agg_jf_item
, va_gc
> *agg_items
;
2770 struct ipa_agg_jump_function
*ajf
;
2772 agg_items
= context_independent_aggregate_values (plats
);
2773 ajf
= &(*known_aggs
)[i
];
2774 ajf
->items
= agg_items
;
2775 ajf
->by_ref
= plats
->aggs_by_ref
;
2776 ret
|= agg_items
!= NULL
;
2783 /* The current interface in ipa-inline-analysis requires a pointer vector.
2786 FIXME: That interface should be re-worked, this is slightly silly. Still,
2787 I'd like to discuss how to change it first and this demonstrates the
2790 static vec
<ipa_agg_jump_function_p
>
2791 agg_jmp_p_vec_for_t_vec (vec
<ipa_agg_jump_function
> known_aggs
)
2793 vec
<ipa_agg_jump_function_p
> ret
;
2794 struct ipa_agg_jump_function
*ajf
;
2797 ret
.create (known_aggs
.length ());
2798 FOR_EACH_VEC_ELT (known_aggs
, i
, ajf
)
2799 ret
.quick_push (ajf
);
2803 /* Perform time and size measurement of NODE with the context given in
2804 KNOWN_CSTS, KNOWN_CONTEXTS and KNOWN_AGGS, calculate the benefit and cost
2805 given BASE_TIME of the node without specialization, REMOVABLE_PARAMS_COST of
2806 all context-independent removable parameters and EST_MOVE_COST of estimated
2807 movement of the considered parameter and store it into VAL. */
2810 perform_estimation_of_a_value (cgraph_node
*node
, vec
<tree
> known_csts
,
2811 vec
<ipa_polymorphic_call_context
> known_contexts
,
2812 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
,
2813 int removable_params_cost
,
2814 int est_move_cost
, ipcp_value_base
*val
)
2816 int size
, time_benefit
;
2817 sreal time
, base_time
;
2820 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
2821 known_aggs_ptrs
, &size
, &time
,
2822 &base_time
, &hints
);
2824 if (base_time
> 65535)
2826 time_benefit
= base_time
.to_int ()
2827 + devirtualization_time_bonus (node
, known_csts
, known_contexts
,
2829 + hint_time_bonus (hints
)
2830 + removable_params_cost
+ est_move_cost
;
2832 gcc_checking_assert (size
>=0);
2833 /* The inliner-heuristics based estimates may think that in certain
2834 contexts some functions do not have any size at all but we want
2835 all specializations to have at least a tiny cost, not least not to
2840 val
->local_time_benefit
= time_benefit
;
2841 val
->local_size_cost
= size
;
2844 /* Iterate over known values of parameters of NODE and estimate the local
2845 effects in terms of time and size they have. */
2848 estimate_local_effects (struct cgraph_node
*node
)
2850 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2851 int i
, count
= ipa_get_param_count (info
);
2852 vec
<tree
> known_csts
;
2853 vec
<ipa_polymorphic_call_context
> known_contexts
;
2854 vec
<ipa_agg_jump_function
> known_aggs
;
2855 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
;
2857 int removable_params_cost
;
2859 if (!count
|| !ipcp_versionable_function_p (node
))
2862 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2863 fprintf (dump_file
, "\nEstimating effects for %s.\n", node
->dump_name ());
2865 always_const
= gather_context_independent_values (info
, &known_csts
,
2866 &known_contexts
, &known_aggs
,
2867 &removable_params_cost
);
2868 known_aggs_ptrs
= agg_jmp_p_vec_for_t_vec (known_aggs
);
2869 int devirt_bonus
= devirtualization_time_bonus (node
, known_csts
,
2870 known_contexts
, known_aggs_ptrs
);
2871 if (always_const
|| devirt_bonus
2872 || (removable_params_cost
&& node
->local
.can_change_signature
))
2874 struct caller_statistics stats
;
2876 sreal time
, base_time
;
2879 init_caller_stats (&stats
);
2880 node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
2882 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
2883 known_aggs_ptrs
, &size
, &time
,
2884 &base_time
, &hints
);
2885 time
-= devirt_bonus
;
2886 time
-= hint_time_bonus (hints
);
2887 time
-= removable_params_cost
;
2888 size
-= stats
.n_calls
* removable_params_cost
;
2891 fprintf (dump_file
, " - context independent values, size: %i, "
2892 "time_benefit: %f\n", size
, (base_time
- time
).to_double ());
2894 if (size
<= 0 || node
->local
.local
)
2896 info
->do_clone_for_all_contexts
= true;
2899 fprintf (dump_file
, " Decided to specialize for all "
2900 "known contexts, code not going to grow.\n");
2902 else if (good_cloning_opportunity_p (node
,
2903 MIN ((base_time
- time
).to_int (),
2905 stats
.freq_sum
, stats
.count_sum
,
2908 if (size
+ overall_size
<= max_new_size
)
2910 info
->do_clone_for_all_contexts
= true;
2911 overall_size
+= size
;
2914 fprintf (dump_file
, " Decided to specialize for all "
2915 "known contexts, growth deemed beneficial.\n");
2917 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2918 fprintf (dump_file
, " Not cloning for all contexts because "
2919 "max_new_size would be reached with %li.\n",
2920 size
+ overall_size
);
2922 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2923 fprintf (dump_file
, " Not cloning for all contexts because "
2924 "!good_cloning_opportunity_p.\n");
2928 for (i
= 0; i
< count
; i
++)
2930 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2931 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
2932 ipcp_value
<tree
> *val
;
2939 for (val
= lat
->values
; val
; val
= val
->next
)
2941 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
2942 known_csts
[i
] = val
->value
;
2944 int emc
= estimate_move_cost (TREE_TYPE (val
->value
), true);
2945 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
2947 removable_params_cost
, emc
, val
);
2949 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2951 fprintf (dump_file
, " - estimates for value ");
2952 print_ipcp_constant_value (dump_file
, val
->value
);
2953 fprintf (dump_file
, " for ");
2954 ipa_dump_param (dump_file
, info
, i
);
2955 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
2956 val
->local_time_benefit
, val
->local_size_cost
);
2959 known_csts
[i
] = NULL_TREE
;
2962 for (i
= 0; i
< count
; i
++)
2964 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2966 if (!plats
->virt_call
)
2969 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
2970 ipcp_value
<ipa_polymorphic_call_context
> *val
;
2974 || !known_contexts
[i
].useless_p ())
2977 for (val
= ctxlat
->values
; val
; val
= val
->next
)
2979 known_contexts
[i
] = val
->value
;
2980 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
2982 removable_params_cost
, 0, val
);
2984 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2986 fprintf (dump_file
, " - estimates for polymorphic context ");
2987 print_ipcp_constant_value (dump_file
, val
->value
);
2988 fprintf (dump_file
, " for ");
2989 ipa_dump_param (dump_file
, info
, i
);
2990 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
2991 val
->local_time_benefit
, val
->local_size_cost
);
2994 known_contexts
[i
] = ipa_polymorphic_call_context ();
2997 for (i
= 0; i
< count
; i
++)
2999 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3000 struct ipa_agg_jump_function
*ajf
;
3001 struct ipcp_agg_lattice
*aglat
;
3003 if (plats
->aggs_bottom
|| !plats
->aggs
)
3006 ajf
= &known_aggs
[i
];
3007 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3009 ipcp_value
<tree
> *val
;
3010 if (aglat
->bottom
|| !aglat
->values
3011 /* If the following is true, the one value is in known_aggs. */
3012 || (!plats
->aggs_contain_variable
3013 && aglat
->is_single_const ()))
3016 for (val
= aglat
->values
; val
; val
= val
->next
)
3018 struct ipa_agg_jf_item item
;
3020 item
.offset
= aglat
->offset
;
3021 item
.value
= val
->value
;
3022 vec_safe_push (ajf
->items
, item
);
3024 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
3026 removable_params_cost
, 0, val
);
3028 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3030 fprintf (dump_file
, " - estimates for value ");
3031 print_ipcp_constant_value (dump_file
, val
->value
);
3032 fprintf (dump_file
, " for ");
3033 ipa_dump_param (dump_file
, info
, i
);
3034 fprintf (dump_file
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
3035 "]: time_benefit: %i, size: %i\n",
3036 plats
->aggs_by_ref
? "ref " : "",
3038 val
->local_time_benefit
, val
->local_size_cost
);
3046 for (i
= 0; i
< count
; i
++)
3047 vec_free (known_aggs
[i
].items
);
3049 known_csts
.release ();
3050 known_contexts
.release ();
3051 known_aggs
.release ();
3052 known_aggs_ptrs
.release ();
3056 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
3057 topological sort of values. */
3059 template <typename valtype
>
3061 value_topo_info
<valtype
>::add_val (ipcp_value
<valtype
> *cur_val
)
3063 ipcp_value_source
<valtype
> *src
;
3069 cur_val
->dfs
= dfs_counter
;
3070 cur_val
->low_link
= dfs_counter
;
3072 cur_val
->topo_next
= stack
;
3074 cur_val
->on_stack
= true;
3076 for (src
= cur_val
->sources
; src
; src
= src
->next
)
3079 if (src
->val
->dfs
== 0)
3082 if (src
->val
->low_link
< cur_val
->low_link
)
3083 cur_val
->low_link
= src
->val
->low_link
;
3085 else if (src
->val
->on_stack
3086 && src
->val
->dfs
< cur_val
->low_link
)
3087 cur_val
->low_link
= src
->val
->dfs
;
3090 if (cur_val
->dfs
== cur_val
->low_link
)
3092 ipcp_value
<valtype
> *v
, *scc_list
= NULL
;
3097 stack
= v
->topo_next
;
3098 v
->on_stack
= false;
3100 v
->scc_next
= scc_list
;
3103 while (v
!= cur_val
);
3105 cur_val
->topo_next
= values_topo
;
3106 values_topo
= cur_val
;
3110 /* Add all values in lattices associated with NODE to the topological sort if
3111 they are not there yet. */
3114 add_all_node_vals_to_toposort (cgraph_node
*node
, ipa_topo_info
*topo
)
3116 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3117 int i
, count
= ipa_get_param_count (info
);
3119 for (i
= 0; i
< count
; i
++)
3121 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3122 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
3123 struct ipcp_agg_lattice
*aglat
;
3127 ipcp_value
<tree
> *val
;
3128 for (val
= lat
->values
; val
; val
= val
->next
)
3129 topo
->constants
.add_val (val
);
3132 if (!plats
->aggs_bottom
)
3133 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3136 ipcp_value
<tree
> *val
;
3137 for (val
= aglat
->values
; val
; val
= val
->next
)
3138 topo
->constants
.add_val (val
);
3141 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
3142 if (!ctxlat
->bottom
)
3144 ipcp_value
<ipa_polymorphic_call_context
> *ctxval
;
3145 for (ctxval
= ctxlat
->values
; ctxval
; ctxval
= ctxval
->next
)
3146 topo
->contexts
.add_val (ctxval
);
3151 /* One pass of constants propagation along the call graph edges, from callers
3152 to callees (requires topological ordering in TOPO), iterate over strongly
3153 connected components. */
3156 propagate_constants_topo (struct ipa_topo_info
*topo
)
3160 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
3163 struct cgraph_node
*v
, *node
= topo
->order
[i
];
3164 vec
<cgraph_node
*> cycle_nodes
= ipa_get_nodes_in_cycle (node
);
3166 /* First, iteratively propagate within the strongly connected component
3167 until all lattices stabilize. */
3168 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
3169 if (v
->has_gimple_body_p ())
3170 push_node_to_stack (topo
, v
);
3172 v
= pop_node_from_stack (topo
);
3175 struct cgraph_edge
*cs
;
3177 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3178 if (ipa_edge_within_scc (cs
))
3180 IPA_NODE_REF (v
)->node_within_scc
= true;
3181 if (propagate_constants_across_call (cs
))
3182 push_node_to_stack (topo
, cs
->callee
->function_symbol ());
3184 v
= pop_node_from_stack (topo
);
3187 /* Afterwards, propagate along edges leading out of the SCC, calculates
3188 the local effects of the discovered constants and all valid values to
3189 their topological sort. */
3190 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
3191 if (v
->has_gimple_body_p ())
3193 struct cgraph_edge
*cs
;
3195 estimate_local_effects (v
);
3196 add_all_node_vals_to_toposort (v
, topo
);
3197 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3198 if (!ipa_edge_within_scc (cs
))
3199 propagate_constants_across_call (cs
);
3201 cycle_nodes
.release ();
3206 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
3207 the bigger one if otherwise. */
3210 safe_add (int a
, int b
)
3212 if (a
> INT_MAX
/2 || b
> INT_MAX
/2)
3213 return a
> b
? a
: b
;
3219 /* Propagate the estimated effects of individual values along the topological
3220 from the dependent values to those they depend on. */
3222 template <typename valtype
>
3224 value_topo_info
<valtype
>::propagate_effects ()
3226 ipcp_value
<valtype
> *base
;
3228 for (base
= values_topo
; base
; base
= base
->topo_next
)
3230 ipcp_value_source
<valtype
> *src
;
3231 ipcp_value
<valtype
> *val
;
3232 int time
= 0, size
= 0;
3234 for (val
= base
; val
; val
= val
->scc_next
)
3236 time
= safe_add (time
,
3237 val
->local_time_benefit
+ val
->prop_time_benefit
);
3238 size
= safe_add (size
, val
->local_size_cost
+ val
->prop_size_cost
);
3241 for (val
= base
; val
; val
= val
->scc_next
)
3242 for (src
= val
->sources
; src
; src
= src
->next
)
3244 && src
->cs
->maybe_hot_p ())
3246 src
->val
->prop_time_benefit
= safe_add (time
,
3247 src
->val
->prop_time_benefit
);
3248 src
->val
->prop_size_cost
= safe_add (size
,
3249 src
->val
->prop_size_cost
);
3255 /* Propagate constants, polymorphic contexts and their effects from the
3256 summaries interprocedurally. */
3259 ipcp_propagate_stage (struct ipa_topo_info
*topo
)
3261 struct cgraph_node
*node
;
3264 fprintf (dump_file
, "\n Propagating constants:\n\n");
3266 max_count
= profile_count::uninitialized ();
3268 FOR_EACH_DEFINED_FUNCTION (node
)
3270 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3272 determine_versionability (node
, info
);
3273 if (node
->has_gimple_body_p ())
3275 info
->lattices
= XCNEWVEC (struct ipcp_param_lattices
,
3276 ipa_get_param_count (info
));
3277 initialize_node_lattices (node
);
3279 ipa_fn_summary
*s
= ipa_fn_summaries
->get (node
);
3280 if (node
->definition
&& !node
->alias
&& s
!= NULL
)
3281 overall_size
+= s
->self_size
;
3282 max_count
= max_count
.max (node
->count
.ipa ());
3285 max_new_size
= overall_size
;
3286 if (max_new_size
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
3287 max_new_size
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
3288 max_new_size
+= max_new_size
* PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH
) / 100 + 1;
3291 fprintf (dump_file
, "\noverall_size: %li, max_new_size: %li\n",
3292 overall_size
, max_new_size
);
3294 propagate_constants_topo (topo
);
3296 ipcp_verify_propagated_values ();
3297 topo
->constants
.propagate_effects ();
3298 topo
->contexts
.propagate_effects ();
3302 fprintf (dump_file
, "\nIPA lattices after all propagation:\n");
3303 print_all_lattices (dump_file
, (dump_flags
& TDF_DETAILS
), true);
3307 /* Discover newly direct outgoing edges from NODE which is a new clone with
3308 known KNOWN_CSTS and make them direct. */
3311 ipcp_discover_new_direct_edges (struct cgraph_node
*node
,
3312 vec
<tree
> known_csts
,
3313 vec
<ipa_polymorphic_call_context
>
3315 struct ipa_agg_replacement_value
*aggvals
)
3317 struct cgraph_edge
*ie
, *next_ie
;
3320 for (ie
= node
->indirect_calls
; ie
; ie
= next_ie
)
3325 next_ie
= ie
->next_callee
;
3326 target
= ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
3327 vNULL
, aggvals
, &speculative
);
3330 bool agg_contents
= ie
->indirect_info
->agg_contents
;
3331 bool polymorphic
= ie
->indirect_info
->polymorphic
;
3332 int param_index
= ie
->indirect_info
->param_index
;
3333 struct cgraph_edge
*cs
= ipa_make_edge_direct_to_target (ie
, target
,
3337 if (cs
&& !agg_contents
&& !polymorphic
)
3339 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3340 int c
= ipa_get_controlled_uses (info
, param_index
);
3341 if (c
!= IPA_UNDESCRIBED_USE
)
3343 struct ipa_ref
*to_del
;
3346 ipa_set_controlled_uses (info
, param_index
, c
);
3347 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3348 fprintf (dump_file
, " controlled uses count of param "
3349 "%i bumped down to %i\n", param_index
, c
);
3351 && (to_del
= node
->find_reference (cs
->callee
, NULL
, 0)))
3353 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3354 fprintf (dump_file
, " and even removing its "
3355 "cloning-created reference\n");
3356 to_del
->remove_reference ();
3362 /* Turning calls to direct calls will improve overall summary. */
3364 ipa_update_overall_fn_summary (node
);
3367 class edge_clone_summary
;
3368 static call_summary
<edge_clone_summary
*> *edge_clone_summaries
= NULL
;
3370 /* Edge clone summary. */
3372 struct edge_clone_summary
3374 /* Default constructor. */
3375 edge_clone_summary (): prev_clone (NULL
), next_clone (NULL
) {}
3377 /* Default destructor. */
3378 ~edge_clone_summary ()
3381 edge_clone_summaries
->get (prev_clone
)->next_clone
= next_clone
;
3383 edge_clone_summaries
->get (next_clone
)->prev_clone
= prev_clone
;
3386 cgraph_edge
*prev_clone
;
3387 cgraph_edge
*next_clone
;
3390 class edge_clone_summary_t
:
3391 public call_summary
<edge_clone_summary
*>
3394 edge_clone_summary_t (symbol_table
*symtab
):
3395 call_summary
<edge_clone_summary
*> (symtab
)
3397 m_initialize_when_cloning
= true;
3400 virtual void duplicate (cgraph_edge
*src_edge
, cgraph_edge
*dst_edge
,
3401 edge_clone_summary
*src_data
,
3402 edge_clone_summary
*dst_data
);
3405 /* Edge duplication hook. */
3408 edge_clone_summary_t::duplicate (cgraph_edge
*src_edge
, cgraph_edge
*dst_edge
,
3409 edge_clone_summary
*src_data
,
3410 edge_clone_summary
*dst_data
)
3412 if (src_data
->next_clone
)
3413 edge_clone_summaries
->get (src_data
->next_clone
)->prev_clone
= dst_edge
;
3414 dst_data
->prev_clone
= src_edge
;
3415 dst_data
->next_clone
= src_data
->next_clone
;
3416 src_data
->next_clone
= dst_edge
;
3419 /* See if NODE is a clone with a known aggregate value at a given OFFSET of a
3420 parameter with the given INDEX. */
3423 get_clone_agg_value (struct cgraph_node
*node
, HOST_WIDE_INT offset
,
3426 struct ipa_agg_replacement_value
*aggval
;
3428 aggval
= ipa_get_agg_replacements_for_node (node
);
3431 if (aggval
->offset
== offset
3432 && aggval
->index
== index
)
3433 return aggval
->value
;
3434 aggval
= aggval
->next
;
3439 /* Return true is NODE is DEST or its clone for all contexts. */
3442 same_node_or_its_all_contexts_clone_p (cgraph_node
*node
, cgraph_node
*dest
)
3447 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3448 return info
->is_all_contexts_clone
&& info
->ipcp_orig_node
== dest
;
3451 /* Return true if edge CS does bring about the value described by SRC to
3452 DEST_VAL of node DEST or its clone for all contexts. */
3455 cgraph_edge_brings_value_p (cgraph_edge
*cs
, ipcp_value_source
<tree
> *src
,
3456 cgraph_node
*dest
, ipcp_value
<tree
> *dest_val
)
3458 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3459 enum availability availability
;
3460 cgraph_node
*real_dest
= cs
->callee
->function_symbol (&availability
);
3462 if (!same_node_or_its_all_contexts_clone_p (real_dest
, dest
)
3463 || availability
<= AVAIL_INTERPOSABLE
3464 || caller_info
->node_dead
)
3470 if (caller_info
->ipcp_orig_node
)
3473 if (src
->offset
== -1)
3474 t
= caller_info
->known_csts
[src
->index
];
3476 t
= get_clone_agg_value (cs
->caller
, src
->offset
, src
->index
);
3477 return (t
!= NULL_TREE
3478 && values_equal_for_ipcp_p (src
->val
->value
, t
));
3482 /* At the moment we do not propagate over arithmetic jump functions in
3483 SCCs, so it is safe to detect self-feeding recursive calls in this
3485 if (src
->val
== dest_val
)
3488 struct ipcp_agg_lattice
*aglat
;
3489 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
3491 if (src
->offset
== -1)
3492 return (plats
->itself
.is_single_const ()
3493 && values_equal_for_ipcp_p (src
->val
->value
,
3494 plats
->itself
.values
->value
));
3497 if (plats
->aggs_bottom
|| plats
->aggs_contain_variable
)
3499 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3500 if (aglat
->offset
== src
->offset
)
3501 return (aglat
->is_single_const ()
3502 && values_equal_for_ipcp_p (src
->val
->value
,
3503 aglat
->values
->value
));
3509 /* Return true if edge CS does bring about the value described by SRC to
3510 DST_VAL of node DEST or its clone for all contexts. */
3513 cgraph_edge_brings_value_p (cgraph_edge
*cs
,
3514 ipcp_value_source
<ipa_polymorphic_call_context
> *src
,
3516 ipcp_value
<ipa_polymorphic_call_context
> *)
3518 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3519 cgraph_node
*real_dest
= cs
->callee
->function_symbol ();
3521 if (!same_node_or_its_all_contexts_clone_p (real_dest
, dest
)
3522 || caller_info
->node_dead
)
3527 if (caller_info
->ipcp_orig_node
)
3528 return (caller_info
->known_contexts
.length () > (unsigned) src
->index
)
3529 && values_equal_for_ipcp_p (src
->val
->value
,
3530 caller_info
->known_contexts
[src
->index
]);
3532 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
3534 return plats
->ctxlat
.is_single_const ()
3535 && values_equal_for_ipcp_p (src
->val
->value
,
3536 plats
->ctxlat
.values
->value
);
3539 /* Get the next clone in the linked list of clones of an edge. */
3541 static inline struct cgraph_edge
*
3542 get_next_cgraph_edge_clone (struct cgraph_edge
*cs
)
3544 edge_clone_summary
*s
= edge_clone_summaries
->get (cs
);
3545 return s
!= NULL
? s
->next_clone
: NULL
;
3548 /* Given VAL that is intended for DEST, iterate over all its sources and if any
3549 of them is viable and hot, return true. In that case, for those that still
3550 hold, add their edge frequency and their number into *FREQUENCY and
3551 *CALLER_COUNT respectively. */
3553 template <typename valtype
>
3555 get_info_about_necessary_edges (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
3557 profile_count
*count_sum
, int *caller_count
)
3559 ipcp_value_source
<valtype
> *src
;
3560 int freq
= 0, count
= 0;
3561 profile_count cnt
= profile_count::zero ();
3563 bool non_self_recursive
= false;
3565 for (src
= val
->sources
; src
; src
= src
->next
)
3567 struct cgraph_edge
*cs
= src
->cs
;
3570 if (cgraph_edge_brings_value_p (cs
, src
, dest
, val
))
3573 freq
+= cs
->frequency ();
3574 if (cs
->count
.ipa ().initialized_p ())
3575 cnt
+= cs
->count
.ipa ();
3576 hot
|= cs
->maybe_hot_p ();
3577 if (cs
->caller
!= dest
)
3578 non_self_recursive
= true;
3580 cs
= get_next_cgraph_edge_clone (cs
);
3584 /* If the only edges bringing a value are self-recursive ones, do not bother
3586 if (!non_self_recursive
)
3591 *caller_count
= count
;
3595 /* Return a vector of incoming edges that do bring value VAL to node DEST. It
3596 is assumed their number is known and equal to CALLER_COUNT. */
3598 template <typename valtype
>
3599 static vec
<cgraph_edge
*>
3600 gather_edges_for_value (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
3603 ipcp_value_source
<valtype
> *src
;
3604 vec
<cgraph_edge
*> ret
;
3606 ret
.create (caller_count
);
3607 for (src
= val
->sources
; src
; src
= src
->next
)
3609 struct cgraph_edge
*cs
= src
->cs
;
3612 if (cgraph_edge_brings_value_p (cs
, src
, dest
, val
))
3613 ret
.quick_push (cs
);
3614 cs
= get_next_cgraph_edge_clone (cs
);
3621 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
3622 Return it or NULL if for some reason it cannot be created. */
3624 static struct ipa_replace_map
*
3625 get_replacement_map (struct ipa_node_params
*info
, tree value
, int parm_num
)
3627 struct ipa_replace_map
*replace_map
;
3630 replace_map
= ggc_alloc
<ipa_replace_map
> ();
3633 fprintf (dump_file
, " replacing ");
3634 ipa_dump_param (dump_file
, info
, parm_num
);
3636 fprintf (dump_file
, " with const ");
3637 print_generic_expr (dump_file
, value
);
3638 fprintf (dump_file
, "\n");
3640 replace_map
->old_tree
= NULL
;
3641 replace_map
->parm_num
= parm_num
;
3642 replace_map
->new_tree
= value
;
3643 replace_map
->replace_p
= true;
3644 replace_map
->ref_p
= false;
3649 /* Dump new profiling counts */
3652 dump_profile_updates (struct cgraph_node
*orig_node
,
3653 struct cgraph_node
*new_node
)
3655 struct cgraph_edge
*cs
;
3657 fprintf (dump_file
, " setting count of the specialized node to ");
3658 new_node
->count
.dump (dump_file
);
3659 fprintf (dump_file
, "\n");
3660 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3662 fprintf (dump_file
, " edge to %s has count ",
3663 cs
->callee
->name ());
3664 cs
->count
.dump (dump_file
);
3665 fprintf (dump_file
, "\n");
3668 fprintf (dump_file
, " setting count of the original node to ");
3669 orig_node
->count
.dump (dump_file
);
3670 fprintf (dump_file
, "\n");
3671 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3673 fprintf (dump_file
, " edge to %s is left with ",
3674 cs
->callee
->name ());
3675 cs
->count
.dump (dump_file
);
3676 fprintf (dump_file
, "\n");
3680 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
3681 their profile information to reflect this. */
3684 update_profiling_info (struct cgraph_node
*orig_node
,
3685 struct cgraph_node
*new_node
)
3687 struct cgraph_edge
*cs
;
3688 struct caller_statistics stats
;
3689 profile_count new_sum
, orig_sum
;
3690 profile_count remainder
, orig_node_count
= orig_node
->count
;
3692 if (!(orig_node_count
.ipa () > profile_count::zero ()))
3695 init_caller_stats (&stats
);
3696 orig_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
3698 orig_sum
= stats
.count_sum
;
3699 init_caller_stats (&stats
);
3700 new_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
3702 new_sum
= stats
.count_sum
;
3704 if (orig_node_count
< orig_sum
+ new_sum
)
3708 fprintf (dump_file
, " Problem: node %s has too low count ",
3709 orig_node
->dump_name ());
3710 orig_node_count
.dump (dump_file
);
3711 fprintf (dump_file
, "while the sum of incoming count is ");
3712 (orig_sum
+ new_sum
).dump (dump_file
);
3713 fprintf (dump_file
, "\n");
3716 orig_node_count
= (orig_sum
+ new_sum
).apply_scale (12, 10);
3719 fprintf (dump_file
, " proceeding by pretending it was ");
3720 orig_node_count
.dump (dump_file
);
3721 fprintf (dump_file
, "\n");
3725 remainder
= orig_node_count
.combine_with_ipa_count (orig_node_count
.ipa ()
3727 new_sum
= orig_node_count
.combine_with_ipa_count (new_sum
);
3728 orig_node
->count
= remainder
;
3730 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3731 cs
->count
= cs
->count
.apply_scale (new_sum
, orig_node_count
);
3733 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3734 cs
->count
= cs
->count
.apply_scale (remainder
, orig_node_count
);
3737 dump_profile_updates (orig_node
, new_node
);
3740 /* Update the respective profile of specialized NEW_NODE and the original
3741 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
3742 have been redirected to the specialized version. */
3745 update_specialized_profile (struct cgraph_node
*new_node
,
3746 struct cgraph_node
*orig_node
,
3747 profile_count redirected_sum
)
3749 struct cgraph_edge
*cs
;
3750 profile_count new_node_count
, orig_node_count
= orig_node
->count
;
3754 fprintf (dump_file
, " the sum of counts of redirected edges is ");
3755 redirected_sum
.dump (dump_file
);
3756 fprintf (dump_file
, "\n");
3758 if (!(orig_node_count
> profile_count::zero ()))
3761 gcc_assert (orig_node_count
>= redirected_sum
);
3763 new_node_count
= new_node
->count
;
3764 new_node
->count
+= redirected_sum
;
3765 orig_node
->count
-= redirected_sum
;
3767 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3768 cs
->count
+= cs
->count
.apply_scale (redirected_sum
, new_node_count
);
3770 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3772 profile_count dec
= cs
->count
.apply_scale (redirected_sum
,
3778 dump_profile_updates (orig_node
, new_node
);
3781 /* Create a specialized version of NODE with known constants in KNOWN_CSTS,
3782 known contexts in KNOWN_CONTEXTS and known aggregate values in AGGVALS and
3783 redirect all edges in CALLERS to it. */
3785 static struct cgraph_node
*
3786 create_specialized_node (struct cgraph_node
*node
,
3787 vec
<tree
> known_csts
,
3788 vec
<ipa_polymorphic_call_context
> known_contexts
,
3789 struct ipa_agg_replacement_value
*aggvals
,
3790 vec
<cgraph_edge
*> callers
)
3792 struct ipa_node_params
*new_info
, *info
= IPA_NODE_REF (node
);
3793 vec
<ipa_replace_map
*, va_gc
> *replace_trees
= NULL
;
3794 struct ipa_agg_replacement_value
*av
;
3795 struct cgraph_node
*new_node
;
3796 int i
, count
= ipa_get_param_count (info
);
3797 bitmap args_to_skip
;
3799 gcc_assert (!info
->ipcp_orig_node
);
3801 if (node
->local
.can_change_signature
)
3803 args_to_skip
= BITMAP_GGC_ALLOC ();
3804 for (i
= 0; i
< count
; i
++)
3806 tree t
= known_csts
[i
];
3808 if (t
|| !ipa_is_param_used (info
, i
))
3809 bitmap_set_bit (args_to_skip
, i
);
3814 args_to_skip
= NULL
;
3815 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3816 fprintf (dump_file
, " cannot change function signature\n");
3819 for (i
= 0; i
< count
; i
++)
3821 tree t
= known_csts
[i
];
3824 struct ipa_replace_map
*replace_map
;
3826 gcc_checking_assert (TREE_CODE (t
) != TREE_BINFO
);
3827 replace_map
= get_replacement_map (info
, t
, i
);
3829 vec_safe_push (replace_trees
, replace_map
);
3832 auto_vec
<cgraph_edge
*, 2> self_recursive_calls
;
3833 for (i
= callers
.length () - 1; i
>= 0; i
--)
3835 cgraph_edge
*cs
= callers
[i
];
3836 if (cs
->caller
== node
)
3838 self_recursive_calls
.safe_push (cs
);
3839 callers
.unordered_remove (i
);
3843 new_node
= node
->create_virtual_clone (callers
, replace_trees
,
3844 args_to_skip
, "constprop");
3846 bool have_self_recursive_calls
= !self_recursive_calls
.is_empty ();
3847 for (unsigned j
= 0; j
< self_recursive_calls
.length (); j
++)
3849 cgraph_edge
*cs
= get_next_cgraph_edge_clone (self_recursive_calls
[j
]);
3850 /* Cloned edges can disappear during cloning as speculation can be
3851 resolved, check that we have one and that it comes from the last
3853 if (cs
&& cs
->caller
== new_node
)
3854 cs
->redirect_callee_duplicating_thunks (new_node
);
3855 /* Any future code that would make more than one clone of an outgoing
3856 edge would confuse this mechanism, so let's check that does not
3858 gcc_checking_assert (!cs
3859 || !get_next_cgraph_edge_clone (cs
)
3860 || get_next_cgraph_edge_clone (cs
)->caller
!= new_node
);
3862 if (have_self_recursive_calls
)
3863 new_node
->expand_all_artificial_thunks ();
3865 ipa_set_node_agg_value_chain (new_node
, aggvals
);
3866 for (av
= aggvals
; av
; av
= av
->next
)
3867 new_node
->maybe_create_reference (av
->value
, NULL
);
3869 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3871 fprintf (dump_file
, " the new node is %s.\n", new_node
->dump_name ());
3872 if (known_contexts
.exists ())
3874 for (i
= 0; i
< count
; i
++)
3875 if (!known_contexts
[i
].useless_p ())
3877 fprintf (dump_file
, " known ctx %i is ", i
);
3878 known_contexts
[i
].dump (dump_file
);
3882 ipa_dump_agg_replacement_values (dump_file
, aggvals
);
3884 ipa_check_create_node_params ();
3885 update_profiling_info (node
, new_node
);
3886 new_info
= IPA_NODE_REF (new_node
);
3887 new_info
->ipcp_orig_node
= node
;
3888 new_info
->known_csts
= known_csts
;
3889 new_info
->known_contexts
= known_contexts
;
3891 ipcp_discover_new_direct_edges (new_node
, known_csts
, known_contexts
, aggvals
);
3897 /* Return true, if JFUNC, which describes a i-th parameter of call CS, is a
3898 simple no-operation pass-through function to itself. */
3901 self_recursive_pass_through_p (cgraph_edge
*cs
, ipa_jump_func
*jfunc
, int i
)
3903 enum availability availability
;
3904 if (cs
->caller
== cs
->callee
->function_symbol (&availability
)
3905 && availability
> AVAIL_INTERPOSABLE
3906 && jfunc
->type
== IPA_JF_PASS_THROUGH
3907 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
3908 && ipa_get_jf_pass_through_formal_id (jfunc
) == i
)
3913 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
3914 KNOWN_CSTS with constants that are also known for all of the CALLERS. */
3917 find_more_scalar_values_for_callers_subset (struct cgraph_node
*node
,
3918 vec
<tree
> known_csts
,
3919 vec
<cgraph_edge
*> callers
)
3921 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3922 int i
, count
= ipa_get_param_count (info
);
3924 for (i
= 0; i
< count
; i
++)
3926 struct cgraph_edge
*cs
;
3927 tree newval
= NULL_TREE
;
3930 tree type
= ipa_get_type (info
, i
);
3932 if (ipa_get_scalar_lat (info
, i
)->bottom
|| known_csts
[i
])
3935 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3937 struct ipa_jump_func
*jump_func
;
3940 if (IPA_NODE_REF (cs
->caller
)->node_dead
)
3943 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
))
3945 && call_passes_through_thunk_p (cs
)))
3950 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
3951 if (self_recursive_pass_through_p (cs
, jump_func
, i
))
3954 t
= ipa_value_from_jfunc (IPA_NODE_REF (cs
->caller
), jump_func
, type
);
3957 && !values_equal_for_ipcp_p (t
, newval
))
3958 || (!first
&& !newval
))
3970 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3972 fprintf (dump_file
, " adding an extra known scalar value ");
3973 print_ipcp_constant_value (dump_file
, newval
);
3974 fprintf (dump_file
, " for ");
3975 ipa_dump_param (dump_file
, info
, i
);
3976 fprintf (dump_file
, "\n");
3979 known_csts
[i
] = newval
;
3984 /* Given a NODE and a subset of its CALLERS, try to populate plank slots in
3985 KNOWN_CONTEXTS with polymorphic contexts that are also known for all of the
3989 find_more_contexts_for_caller_subset (cgraph_node
*node
,
3990 vec
<ipa_polymorphic_call_context
>
3992 vec
<cgraph_edge
*> callers
)
3994 ipa_node_params
*info
= IPA_NODE_REF (node
);
3995 int i
, count
= ipa_get_param_count (info
);
3997 for (i
= 0; i
< count
; i
++)
4001 if (ipa_get_poly_ctx_lat (info
, i
)->bottom
4002 || (known_contexts
->exists ()
4003 && !(*known_contexts
)[i
].useless_p ()))
4006 ipa_polymorphic_call_context newval
;
4010 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4012 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
)))
4014 ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
),
4016 ipa_polymorphic_call_context ctx
;
4017 ctx
= ipa_context_from_jfunc (IPA_NODE_REF (cs
->caller
), cs
, i
,
4025 newval
.meet_with (ctx
);
4026 if (newval
.useless_p ())
4030 if (!newval
.useless_p ())
4032 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4034 fprintf (dump_file
, " adding an extra known polymorphic "
4036 print_ipcp_constant_value (dump_file
, newval
);
4037 fprintf (dump_file
, " for ");
4038 ipa_dump_param (dump_file
, info
, i
);
4039 fprintf (dump_file
, "\n");
4042 if (!known_contexts
->exists ())
4043 known_contexts
->safe_grow_cleared (ipa_get_param_count (info
));
4044 (*known_contexts
)[i
] = newval
;
4050 /* Go through PLATS and create a vector of values consisting of values and
4051 offsets (minus OFFSET) of lattices that contain only a single value. */
4053 static vec
<ipa_agg_jf_item
>
4054 copy_plats_to_inter (struct ipcp_param_lattices
*plats
, HOST_WIDE_INT offset
)
4056 vec
<ipa_agg_jf_item
> res
= vNULL
;
4058 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
4061 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
4062 if (aglat
->is_single_const ())
4064 struct ipa_agg_jf_item ti
;
4065 ti
.offset
= aglat
->offset
- offset
;
4066 ti
.value
= aglat
->values
->value
;
4072 /* Intersect all values in INTER with single value lattices in PLATS (while
4073 subtracting OFFSET). */
4076 intersect_with_plats (struct ipcp_param_lattices
*plats
,
4077 vec
<ipa_agg_jf_item
> *inter
,
4078 HOST_WIDE_INT offset
)
4080 struct ipcp_agg_lattice
*aglat
;
4081 struct ipa_agg_jf_item
*item
;
4084 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
4090 aglat
= plats
->aggs
;
4091 FOR_EACH_VEC_ELT (*inter
, k
, item
)
4098 if (aglat
->offset
- offset
> item
->offset
)
4100 if (aglat
->offset
- offset
== item
->offset
)
4102 gcc_checking_assert (item
->value
);
4103 if (aglat
->is_single_const ()
4104 && values_equal_for_ipcp_p (item
->value
,
4105 aglat
->values
->value
))
4109 aglat
= aglat
->next
;
4112 item
->value
= NULL_TREE
;
4116 /* Copy aggregate replacement values of NODE (which is an IPA-CP clone) to the
4117 vector result while subtracting OFFSET from the individual value offsets. */
4119 static vec
<ipa_agg_jf_item
>
4120 agg_replacements_to_vector (struct cgraph_node
*node
, int index
,
4121 HOST_WIDE_INT offset
)
4123 struct ipa_agg_replacement_value
*av
;
4124 vec
<ipa_agg_jf_item
> res
= vNULL
;
4126 for (av
= ipa_get_agg_replacements_for_node (node
); av
; av
= av
->next
)
4127 if (av
->index
== index
4128 && (av
->offset
- offset
) >= 0)
4130 struct ipa_agg_jf_item item
;
4131 gcc_checking_assert (av
->value
);
4132 item
.offset
= av
->offset
- offset
;
4133 item
.value
= av
->value
;
4134 res
.safe_push (item
);
4140 /* Intersect all values in INTER with those that we have already scheduled to
4141 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
4142 (while subtracting OFFSET). */
4145 intersect_with_agg_replacements (struct cgraph_node
*node
, int index
,
4146 vec
<ipa_agg_jf_item
> *inter
,
4147 HOST_WIDE_INT offset
)
4149 struct ipa_agg_replacement_value
*srcvals
;
4150 struct ipa_agg_jf_item
*item
;
4153 srcvals
= ipa_get_agg_replacements_for_node (node
);
4160 FOR_EACH_VEC_ELT (*inter
, i
, item
)
4162 struct ipa_agg_replacement_value
*av
;
4166 for (av
= srcvals
; av
; av
= av
->next
)
4168 gcc_checking_assert (av
->value
);
4169 if (av
->index
== index
4170 && av
->offset
- offset
== item
->offset
)
4172 if (values_equal_for_ipcp_p (item
->value
, av
->value
))
4178 item
->value
= NULL_TREE
;
4182 /* Intersect values in INTER with aggregate values that come along edge CS to
4183 parameter number INDEX and return it. If INTER does not actually exist yet,
4184 copy all incoming values to it. If we determine we ended up with no values
4185 whatsoever, return a released vector. */
4187 static vec
<ipa_agg_jf_item
>
4188 intersect_aggregates_with_edge (struct cgraph_edge
*cs
, int index
,
4189 vec
<ipa_agg_jf_item
> inter
)
4191 struct ipa_jump_func
*jfunc
;
4192 jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), index
);
4193 if (jfunc
->type
== IPA_JF_PASS_THROUGH
4194 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
4196 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4197 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
4199 if (caller_info
->ipcp_orig_node
)
4201 struct cgraph_node
*orig_node
= caller_info
->ipcp_orig_node
;
4202 struct ipcp_param_lattices
*orig_plats
;
4203 orig_plats
= ipa_get_parm_lattices (IPA_NODE_REF (orig_node
),
4205 if (agg_pass_through_permissible_p (orig_plats
, jfunc
))
4207 if (!inter
.exists ())
4208 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, 0);
4210 intersect_with_agg_replacements (cs
->caller
, src_idx
,
4221 struct ipcp_param_lattices
*src_plats
;
4222 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
4223 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
4225 /* Currently we do not produce clobber aggregate jump
4226 functions, adjust when we do. */
4227 gcc_checking_assert (!jfunc
->agg
.items
);
4228 if (!inter
.exists ())
4229 inter
= copy_plats_to_inter (src_plats
, 0);
4231 intersect_with_plats (src_plats
, &inter
, 0);
4240 else if (jfunc
->type
== IPA_JF_ANCESTOR
4241 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
4243 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4244 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
4245 struct ipcp_param_lattices
*src_plats
;
4246 HOST_WIDE_INT delta
= ipa_get_jf_ancestor_offset (jfunc
);
4248 if (caller_info
->ipcp_orig_node
)
4250 if (!inter
.exists ())
4251 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, delta
);
4253 intersect_with_agg_replacements (cs
->caller
, src_idx
, &inter
,
4258 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
4259 /* Currently we do not produce clobber aggregate jump
4260 functions, adjust when we do. */
4261 gcc_checking_assert (!src_plats
->aggs
|| !jfunc
->agg
.items
);
4262 if (!inter
.exists ())
4263 inter
= copy_plats_to_inter (src_plats
, delta
);
4265 intersect_with_plats (src_plats
, &inter
, delta
);
4268 else if (jfunc
->agg
.items
)
4270 struct ipa_agg_jf_item
*item
;
4273 if (!inter
.exists ())
4274 for (unsigned i
= 0; i
< jfunc
->agg
.items
->length (); i
++)
4275 inter
.safe_push ((*jfunc
->agg
.items
)[i
]);
4277 FOR_EACH_VEC_ELT (inter
, k
, item
)
4285 while ((unsigned) l
< jfunc
->agg
.items
->length ())
4287 struct ipa_agg_jf_item
*ti
;
4288 ti
= &(*jfunc
->agg
.items
)[l
];
4289 if (ti
->offset
> item
->offset
)
4291 if (ti
->offset
== item
->offset
)
4293 gcc_checking_assert (ti
->value
);
4294 if (values_equal_for_ipcp_p (item
->value
,
4308 return vec
<ipa_agg_jf_item
>();
4313 /* Look at edges in CALLERS and collect all known aggregate values that arrive
4314 from all of them. */
4316 static struct ipa_agg_replacement_value
*
4317 find_aggregate_values_for_callers_subset (struct cgraph_node
*node
,
4318 vec
<cgraph_edge
*> callers
)
4320 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
4321 struct ipa_agg_replacement_value
*res
;
4322 struct ipa_agg_replacement_value
**tail
= &res
;
4323 struct cgraph_edge
*cs
;
4324 int i
, j
, count
= ipa_get_param_count (dest_info
);
4326 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4328 int c
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
4333 for (i
= 0; i
< count
; i
++)
4335 struct cgraph_edge
*cs
;
4336 vec
<ipa_agg_jf_item
> inter
= vNULL
;
4337 struct ipa_agg_jf_item
*item
;
4338 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (dest_info
, i
);
4341 /* Among other things, the following check should deal with all by_ref
4343 if (plats
->aggs_bottom
)
4346 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4348 struct ipa_jump_func
*jfunc
4349 = ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
4350 if (self_recursive_pass_through_p (cs
, jfunc
, i
)
4351 && (!plats
->aggs_by_ref
4352 || ipa_get_jf_pass_through_agg_preserved (jfunc
)))
4354 inter
= intersect_aggregates_with_edge (cs
, i
, inter
);
4356 if (!inter
.exists ())
4360 FOR_EACH_VEC_ELT (inter
, j
, item
)
4362 struct ipa_agg_replacement_value
*v
;
4367 v
= ggc_alloc
<ipa_agg_replacement_value
> ();
4369 v
->offset
= item
->offset
;
4370 v
->value
= item
->value
;
4371 v
->by_ref
= plats
->aggs_by_ref
;
4377 if (inter
.exists ())
4384 /* Determine whether CS also brings all scalar values that the NODE is
4388 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge
*cs
,
4389 struct cgraph_node
*node
)
4391 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
4392 int count
= ipa_get_param_count (dest_info
);
4393 struct ipa_node_params
*caller_info
;
4394 struct ipa_edge_args
*args
;
4397 caller_info
= IPA_NODE_REF (cs
->caller
);
4398 args
= IPA_EDGE_REF (cs
);
4399 for (i
= 0; i
< count
; i
++)
4401 struct ipa_jump_func
*jump_func
;
4404 val
= dest_info
->known_csts
[i
];
4408 if (i
>= ipa_get_cs_argument_count (args
))
4410 jump_func
= ipa_get_ith_jump_func (args
, i
);
4411 t
= ipa_value_from_jfunc (caller_info
, jump_func
,
4412 ipa_get_type (dest_info
, i
));
4413 if (!t
|| !values_equal_for_ipcp_p (val
, t
))
4419 /* Determine whether CS also brings all aggregate values that NODE is
4422 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge
*cs
,
4423 struct cgraph_node
*node
)
4425 struct ipa_node_params
*orig_caller_info
= IPA_NODE_REF (cs
->caller
);
4426 struct ipa_node_params
*orig_node_info
;
4427 struct ipa_agg_replacement_value
*aggval
;
4430 aggval
= ipa_get_agg_replacements_for_node (node
);
4434 count
= ipa_get_param_count (IPA_NODE_REF (node
));
4435 ec
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
4437 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4438 if (aggval
->index
>= ec
)
4441 orig_node_info
= IPA_NODE_REF (IPA_NODE_REF (node
)->ipcp_orig_node
);
4442 if (orig_caller_info
->ipcp_orig_node
)
4443 orig_caller_info
= IPA_NODE_REF (orig_caller_info
->ipcp_orig_node
);
4445 for (i
= 0; i
< count
; i
++)
4447 static vec
<ipa_agg_jf_item
> values
= vec
<ipa_agg_jf_item
>();
4448 struct ipcp_param_lattices
*plats
;
4449 bool interesting
= false;
4450 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4451 if (aggval
->index
== i
)
4459 plats
= ipa_get_parm_lattices (orig_node_info
, aggval
->index
);
4460 if (plats
->aggs_bottom
)
4463 values
= intersect_aggregates_with_edge (cs
, i
, values
);
4464 if (!values
.exists ())
4467 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4468 if (aggval
->index
== i
)
4470 struct ipa_agg_jf_item
*item
;
4473 FOR_EACH_VEC_ELT (values
, j
, item
)
4475 && item
->offset
== av
->offset
4476 && values_equal_for_ipcp_p (item
->value
, av
->value
))
4491 /* Given an original NODE and a VAL for which we have already created a
4492 specialized clone, look whether there are incoming edges that still lead
4493 into the old node but now also bring the requested value and also conform to
4494 all other criteria such that they can be redirected the special node.
4495 This function can therefore redirect the final edge in a SCC. */
4497 template <typename valtype
>
4499 perhaps_add_new_callers (cgraph_node
*node
, ipcp_value
<valtype
> *val
)
4501 ipcp_value_source
<valtype
> *src
;
4502 profile_count redirected_sum
= profile_count::zero ();
4504 for (src
= val
->sources
; src
; src
= src
->next
)
4506 struct cgraph_edge
*cs
= src
->cs
;
4509 if (cgraph_edge_brings_value_p (cs
, src
, node
, val
)
4510 && cgraph_edge_brings_all_scalars_for_node (cs
, val
->spec_node
)
4511 && cgraph_edge_brings_all_agg_vals_for_node (cs
, val
->spec_node
))
4514 fprintf (dump_file
, " - adding an extra caller %s of %s\n",
4515 cs
->caller
->dump_name (),
4516 val
->spec_node
->dump_name ());
4518 cs
->redirect_callee_duplicating_thunks (val
->spec_node
);
4519 val
->spec_node
->expand_all_artificial_thunks ();
4520 if (cs
->count
.ipa ().initialized_p ())
4521 redirected_sum
= redirected_sum
+ cs
->count
.ipa ();
4523 cs
= get_next_cgraph_edge_clone (cs
);
4527 if (redirected_sum
.nonzero_p ())
4528 update_specialized_profile (val
->spec_node
, node
, redirected_sum
);
4531 /* Return true if KNOWN_CONTEXTS contain at least one useful context. */
4534 known_contexts_useful_p (vec
<ipa_polymorphic_call_context
> known_contexts
)
4536 ipa_polymorphic_call_context
*ctx
;
4539 FOR_EACH_VEC_ELT (known_contexts
, i
, ctx
)
4540 if (!ctx
->useless_p ())
4545 /* Return a copy of KNOWN_CSTS if it is not empty, otherwise return vNULL. */
4547 static vec
<ipa_polymorphic_call_context
>
4548 copy_useful_known_contexts (vec
<ipa_polymorphic_call_context
> known_contexts
)
4550 if (known_contexts_useful_p (known_contexts
))
4551 return known_contexts
.copy ();
4556 /* Copy KNOWN_CSTS and modify the copy according to VAL and INDEX. If
4557 non-empty, replace KNOWN_CONTEXTS with its copy too. */
4560 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
4561 vec
<ipa_polymorphic_call_context
> *known_contexts
,
4562 ipcp_value
<tree
> *val
,
4565 *known_csts
= known_csts
->copy ();
4566 *known_contexts
= copy_useful_known_contexts (*known_contexts
);
4567 (*known_csts
)[index
] = val
->value
;
4570 /* Replace KNOWN_CSTS with its copy. Also copy KNOWN_CONTEXTS and modify the
4571 copy according to VAL and INDEX. */
4574 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
4575 vec
<ipa_polymorphic_call_context
> *known_contexts
,
4576 ipcp_value
<ipa_polymorphic_call_context
> *val
,
4579 *known_csts
= known_csts
->copy ();
4580 *known_contexts
= known_contexts
->copy ();
4581 (*known_contexts
)[index
] = val
->value
;
4584 /* Return true if OFFSET indicates this was not an aggregate value or there is
4585 a replacement equivalent to VALUE, INDEX and OFFSET among those in the
4589 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*aggvals
,
4590 int index
, HOST_WIDE_INT offset
, tree value
)
4597 if (aggvals
->index
== index
4598 && aggvals
->offset
== offset
4599 && values_equal_for_ipcp_p (aggvals
->value
, value
))
4601 aggvals
= aggvals
->next
;
4606 /* Return true if offset is minus one because source of a polymorphic contect
4607 cannot be an aggregate value. */
4610 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*,
4611 int , HOST_WIDE_INT offset
,
4612 ipa_polymorphic_call_context
)
4614 return offset
== -1;
4617 /* Decide wheter to create a special version of NODE for value VAL of parameter
4618 at the given INDEX. If OFFSET is -1, the value is for the parameter itself,
4619 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS,
4620 KNOWN_CONTEXTS and KNOWN_AGGS describe the other already known values. */
4622 template <typename valtype
>
4624 decide_about_value (struct cgraph_node
*node
, int index
, HOST_WIDE_INT offset
,
4625 ipcp_value
<valtype
> *val
, vec
<tree
> known_csts
,
4626 vec
<ipa_polymorphic_call_context
> known_contexts
)
4628 struct ipa_agg_replacement_value
*aggvals
;
4629 int freq_sum
, caller_count
;
4630 profile_count count_sum
;
4631 vec
<cgraph_edge
*> callers
;
4635 perhaps_add_new_callers (node
, val
);
4638 else if (val
->local_size_cost
+ overall_size
> max_new_size
)
4640 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4641 fprintf (dump_file
, " Ignoring candidate value because "
4642 "max_new_size would be reached with %li.\n",
4643 val
->local_size_cost
+ overall_size
);
4646 else if (!get_info_about_necessary_edges (val
, node
, &freq_sum
, &count_sum
,
4650 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4652 fprintf (dump_file
, " - considering value ");
4653 print_ipcp_constant_value (dump_file
, val
->value
);
4654 fprintf (dump_file
, " for ");
4655 ipa_dump_param (dump_file
, IPA_NODE_REF (node
), index
);
4657 fprintf (dump_file
, ", offset: " HOST_WIDE_INT_PRINT_DEC
, offset
);
4658 fprintf (dump_file
, " (caller_count: %i)\n", caller_count
);
4661 if (!good_cloning_opportunity_p (node
, val
->local_time_benefit
,
4662 freq_sum
, count_sum
,
4663 val
->local_size_cost
)
4664 && !good_cloning_opportunity_p (node
,
4665 val
->local_time_benefit
4666 + val
->prop_time_benefit
,
4667 freq_sum
, count_sum
,
4668 val
->local_size_cost
4669 + val
->prop_size_cost
))
4673 fprintf (dump_file
, " Creating a specialized node of %s.\n",
4674 node
->dump_name ());
4676 callers
= gather_edges_for_value (val
, node
, caller_count
);
4678 modify_known_vectors_with_val (&known_csts
, &known_contexts
, val
, index
);
4681 known_csts
= known_csts
.copy ();
4682 known_contexts
= copy_useful_known_contexts (known_contexts
);
4684 find_more_scalar_values_for_callers_subset (node
, known_csts
, callers
);
4685 find_more_contexts_for_caller_subset (node
, &known_contexts
, callers
);
4686 aggvals
= find_aggregate_values_for_callers_subset (node
, callers
);
4687 gcc_checking_assert (ipcp_val_agg_replacement_ok_p (aggvals
, index
,
4688 offset
, val
->value
));
4689 val
->spec_node
= create_specialized_node (node
, known_csts
, known_contexts
,
4691 overall_size
+= val
->local_size_cost
;
4693 /* TODO: If for some lattice there is only one other known value
4694 left, make a special node for it too. */
4699 /* Decide whether and what specialized clones of NODE should be created. */
4702 decide_whether_version_node (struct cgraph_node
*node
)
4704 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
4705 int i
, count
= ipa_get_param_count (info
);
4706 vec
<tree
> known_csts
;
4707 vec
<ipa_polymorphic_call_context
> known_contexts
;
4708 vec
<ipa_agg_jump_function
> known_aggs
= vNULL
;
4714 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4715 fprintf (dump_file
, "\nEvaluating opportunities for %s.\n",
4716 node
->dump_name ());
4718 gather_context_independent_values (info
, &known_csts
, &known_contexts
,
4719 info
->do_clone_for_all_contexts
? &known_aggs
4722 for (i
= 0; i
< count
;i
++)
4724 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4725 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
4726 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
4731 ipcp_value
<tree
> *val
;
4732 for (val
= lat
->values
; val
; val
= val
->next
)
4733 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
4737 if (!plats
->aggs_bottom
)
4739 struct ipcp_agg_lattice
*aglat
;
4740 ipcp_value
<tree
> *val
;
4741 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
4742 if (!aglat
->bottom
&& aglat
->values
4743 /* If the following is false, the one value is in
4745 && (plats
->aggs_contain_variable
4746 || !aglat
->is_single_const ()))
4747 for (val
= aglat
->values
; val
; val
= val
->next
)
4748 ret
|= decide_about_value (node
, i
, aglat
->offset
, val
,
4749 known_csts
, known_contexts
);
4753 && known_contexts
[i
].useless_p ())
4755 ipcp_value
<ipa_polymorphic_call_context
> *val
;
4756 for (val
= ctxlat
->values
; val
; val
= val
->next
)
4757 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
4761 info
= IPA_NODE_REF (node
);
4764 if (info
->do_clone_for_all_contexts
)
4766 struct cgraph_node
*clone
;
4767 vec
<cgraph_edge
*> callers
;
4770 fprintf (dump_file
, " - Creating a specialized node of %s "
4771 "for all known contexts.\n", node
->dump_name ());
4773 callers
= node
->collect_callers ();
4774 find_more_scalar_values_for_callers_subset (node
, known_csts
, callers
);
4775 find_more_contexts_for_caller_subset (node
, &known_contexts
, callers
);
4776 ipa_agg_replacement_value
*aggvals
4777 = find_aggregate_values_for_callers_subset (node
, callers
);
4779 if (!known_contexts_useful_p (known_contexts
))
4781 known_contexts
.release ();
4782 known_contexts
= vNULL
;
4784 clone
= create_specialized_node (node
, known_csts
, known_contexts
,
4786 info
= IPA_NODE_REF (node
);
4787 info
->do_clone_for_all_contexts
= false;
4788 IPA_NODE_REF (clone
)->is_all_contexts_clone
= true;
4789 for (i
= 0; i
< count
; i
++)
4790 vec_free (known_aggs
[i
].items
);
4791 known_aggs
.release ();
4796 known_csts
.release ();
4797 known_contexts
.release ();
4803 /* Transitively mark all callees of NODE within the same SCC as not dead. */
4806 spread_undeadness (struct cgraph_node
*node
)
4808 struct cgraph_edge
*cs
;
4810 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
4811 if (ipa_edge_within_scc (cs
))
4813 struct cgraph_node
*callee
;
4814 struct ipa_node_params
*info
;
4816 callee
= cs
->callee
->function_symbol (NULL
);
4817 info
= IPA_NODE_REF (callee
);
4819 if (info
->node_dead
)
4821 info
->node_dead
= 0;
4822 spread_undeadness (callee
);
4827 /* Return true if NODE has a caller from outside of its SCC that is not
4828 dead. Worker callback for cgraph_for_node_and_aliases. */
4831 has_undead_caller_from_outside_scc_p (struct cgraph_node
*node
,
4832 void *data ATTRIBUTE_UNUSED
)
4834 struct cgraph_edge
*cs
;
4836 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
4837 if (cs
->caller
->thunk
.thunk_p
4838 && cs
->caller
->call_for_symbol_thunks_and_aliases
4839 (has_undead_caller_from_outside_scc_p
, NULL
, true))
4841 else if (!ipa_edge_within_scc (cs
)
4842 && !IPA_NODE_REF (cs
->caller
)->node_dead
)
4848 /* Identify nodes within the same SCC as NODE which are no longer needed
4849 because of new clones and will be removed as unreachable. */
4852 identify_dead_nodes (struct cgraph_node
*node
)
4854 struct cgraph_node
*v
;
4855 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4857 && !v
->call_for_symbol_thunks_and_aliases
4858 (has_undead_caller_from_outside_scc_p
, NULL
, true))
4859 IPA_NODE_REF (v
)->node_dead
= 1;
4861 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4862 if (!IPA_NODE_REF (v
)->node_dead
)
4863 spread_undeadness (v
);
4865 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4867 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4868 if (IPA_NODE_REF (v
)->node_dead
)
4869 fprintf (dump_file
, " Marking node as dead: %s.\n", v
->dump_name ());
4873 /* The decision stage. Iterate over the topological order of call graph nodes
4874 TOPO and make specialized clones if deemed beneficial. */
4877 ipcp_decision_stage (struct ipa_topo_info
*topo
)
4882 fprintf (dump_file
, "\nIPA decision stage:\n\n");
4884 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
4886 struct cgraph_node
*node
= topo
->order
[i
];
4887 bool change
= false, iterate
= true;
4891 struct cgraph_node
*v
;
4893 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4894 if (v
->has_gimple_body_p ()
4895 && ipcp_versionable_function_p (v
))
4896 iterate
|= decide_whether_version_node (v
);
4901 identify_dead_nodes (node
);
4905 /* Look up all the bits information that we have discovered and copy it over
4906 to the transformation summary. */
4909 ipcp_store_bits_results (void)
4913 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
4915 ipa_node_params
*info
= IPA_NODE_REF (node
);
4916 bool dumped_sth
= false;
4917 bool found_useful_result
= false;
4919 if (!opt_for_fn (node
->decl
, flag_ipa_bit_cp
))
4922 fprintf (dump_file
, "Not considering %s for ipa bitwise propagation "
4923 "; -fipa-bit-cp: disabled.\n",
4928 if (info
->ipcp_orig_node
)
4929 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
4931 unsigned count
= ipa_get_param_count (info
);
4932 for (unsigned i
= 0; i
< count
; i
++)
4934 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4935 if (plats
->bits_lattice
.constant_p ())
4937 found_useful_result
= true;
4942 if (!found_useful_result
)
4945 ipcp_transformation_initialize ();
4946 ipcp_transformation
*ts
= ipcp_transformation_sum
->get_create (node
);
4947 vec_safe_reserve_exact (ts
->bits
, count
);
4949 for (unsigned i
= 0; i
< count
; i
++)
4951 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4954 if (plats
->bits_lattice
.constant_p ())
4956 = ipa_get_ipa_bits_for_value (plats
->bits_lattice
.get_value (),
4957 plats
->bits_lattice
.get_mask ());
4961 ts
->bits
->quick_push (jfbits
);
4962 if (!dump_file
|| !jfbits
)
4966 fprintf (dump_file
, "Propagated bits info for function %s:\n",
4967 node
->dump_name ());
4970 fprintf (dump_file
, " param %i: value = ", i
);
4971 print_hex (jfbits
->value
, dump_file
);
4972 fprintf (dump_file
, ", mask = ");
4973 print_hex (jfbits
->mask
, dump_file
);
4974 fprintf (dump_file
, "\n");
4979 /* Look up all VR information that we have discovered and copy it over
4980 to the transformation summary. */
4983 ipcp_store_vr_results (void)
4987 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
4989 ipa_node_params
*info
= IPA_NODE_REF (node
);
4990 bool found_useful_result
= false;
4992 if (!opt_for_fn (node
->decl
, flag_ipa_vrp
))
4995 fprintf (dump_file
, "Not considering %s for VR discovery "
4996 "and propagate; -fipa-ipa-vrp: disabled.\n",
5001 if (info
->ipcp_orig_node
)
5002 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
5004 unsigned count
= ipa_get_param_count (info
);
5005 for (unsigned i
= 0; i
< count
; i
++)
5007 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5008 if (!plats
->m_value_range
.bottom_p ()
5009 && !plats
->m_value_range
.top_p ())
5011 found_useful_result
= true;
5015 if (!found_useful_result
)
5018 ipcp_transformation_initialize ();
5019 ipcp_transformation
*ts
= ipcp_transformation_sum
->get_create (node
);
5020 vec_safe_reserve_exact (ts
->m_vr
, count
);
5022 for (unsigned i
= 0; i
< count
; i
++)
5024 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5027 if (!plats
->m_value_range
.bottom_p ()
5028 && !plats
->m_value_range
.top_p ())
5031 vr
.type
= plats
->m_value_range
.m_vr
.type
;
5032 vr
.min
= wi::to_wide (plats
->m_value_range
.m_vr
.min
);
5033 vr
.max
= wi::to_wide (plats
->m_value_range
.m_vr
.max
);
5038 vr
.type
= VR_VARYING
;
5039 vr
.min
= vr
.max
= wi::zero (INT_TYPE_SIZE
);
5041 ts
->m_vr
->quick_push (vr
);
5046 /* The IPCP driver. */
5051 struct ipa_topo_info topo
;
5053 if (edge_clone_summaries
== NULL
)
5054 edge_clone_summaries
= new edge_clone_summary_t (symtab
);
5056 ipa_check_create_node_params ();
5057 ipa_check_create_edge_args ();
5061 fprintf (dump_file
, "\nIPA structures before propagation:\n");
5062 if (dump_flags
& TDF_DETAILS
)
5063 ipa_print_all_params (dump_file
);
5064 ipa_print_all_jump_functions (dump_file
);
5067 /* Topological sort. */
5068 build_toporder_info (&topo
);
5069 /* Do the interprocedural propagation. */
5070 ipcp_propagate_stage (&topo
);
5071 /* Decide what constant propagation and cloning should be performed. */
5072 ipcp_decision_stage (&topo
);
5073 /* Store results of bits propagation. */
5074 ipcp_store_bits_results ();
5075 /* Store results of value range propagation. */
5076 ipcp_store_vr_results ();
5078 /* Free all IPCP structures. */
5079 free_toporder_info (&topo
);
5080 delete edge_clone_summaries
;
5081 edge_clone_summaries
= NULL
;
5082 ipa_free_all_structures_after_ipa_cp ();
5084 fprintf (dump_file
, "\nIPA constant propagation end\n");
5088 /* Initialization and computation of IPCP data structures. This is the initial
5089 intraprocedural analysis of functions, which gathers information to be
5090 propagated later on. */
5093 ipcp_generate_summary (void)
5095 struct cgraph_node
*node
;
5098 fprintf (dump_file
, "\nIPA constant propagation start:\n");
5099 ipa_register_cgraph_hooks ();
5101 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5102 ipa_analyze_node (node
);
5105 /* Write ipcp summary for nodes in SET. */
5108 ipcp_write_summary (void)
5110 ipa_prop_write_jump_functions ();
5113 /* Read ipcp summary. */
5116 ipcp_read_summary (void)
5118 ipa_prop_read_jump_functions ();
5123 const pass_data pass_data_ipa_cp
=
5125 IPA_PASS
, /* type */
5127 OPTGROUP_NONE
, /* optinfo_flags */
5128 TV_IPA_CONSTANT_PROP
, /* tv_id */
5129 0, /* properties_required */
5130 0, /* properties_provided */
5131 0, /* properties_destroyed */
5132 0, /* todo_flags_start */
5133 ( TODO_dump_symtab
| TODO_remove_functions
), /* todo_flags_finish */
5136 class pass_ipa_cp
: public ipa_opt_pass_d
5139 pass_ipa_cp (gcc::context
*ctxt
)
5140 : ipa_opt_pass_d (pass_data_ipa_cp
, ctxt
,
5141 ipcp_generate_summary
, /* generate_summary */
5142 ipcp_write_summary
, /* write_summary */
5143 ipcp_read_summary
, /* read_summary */
5144 ipcp_write_transformation_summaries
, /*
5145 write_optimization_summary */
5146 ipcp_read_transformation_summaries
, /*
5147 read_optimization_summary */
5148 NULL
, /* stmt_fixup */
5149 0, /* function_transform_todo_flags_start */
5150 ipcp_transform_function
, /* function_transform */
5151 NULL
) /* variable_transform */
5154 /* opt_pass methods: */
5155 virtual bool gate (function
*)
5157 /* FIXME: We should remove the optimize check after we ensure we never run
5158 IPA passes when not optimizing. */
5159 return (flag_ipa_cp
&& optimize
) || in_lto_p
;
5162 virtual unsigned int execute (function
*) { return ipcp_driver (); }
5164 }; // class pass_ipa_cp
5169 make_pass_ipa_cp (gcc::context
*ctxt
)
5171 return new pass_ipa_cp (ctxt
);
5174 /* Reset all state within ipa-cp.c so that we can rerun the compiler
5175 within the same process. For use by toplev::finalize. */
5178 ipa_cp_c_finalize (void)
5180 max_count
= profile_count::uninitialized ();