1 /* Interprocedural constant propagation
2 Copyright (C) 2005-2020 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"
121 #include "ipa-fnsummary.h"
122 #include "ipa-utils.h"
123 #include "tree-ssa-ccp.h"
124 #include "stringpool.h"
127 #include "symtab-clones.h"
129 template <typename valtype
> class ipcp_value
;
131 /* Describes a particular source for an IPA-CP value. */
133 template <typename valtype
>
134 struct ipcp_value_source
137 /* Aggregate offset of the source, negative if the source is scalar value of
138 the argument itself. */
139 HOST_WIDE_INT offset
;
140 /* The incoming edge that brought the value. */
142 /* If the jump function that resulted into his value was a pass-through or an
143 ancestor, this is the ipcp_value of the caller from which the described
144 value has been derived. Otherwise it is NULL. */
145 ipcp_value
<valtype
> *val
;
146 /* Next pointer in a linked list of sources of a value. */
147 ipcp_value_source
*next
;
148 /* If the jump function that resulted into his value was a pass-through or an
149 ancestor, this is the index of the parameter of the caller the jump
150 function references. */
154 /* Common ancestor for all ipcp_value instantiations. */
156 class ipcp_value_base
159 /* Time benefit and that specializing the function for this value would bring
160 about in this function alone. */
161 sreal local_time_benefit
;
162 /* Time benefit that specializing the function for this value can bring about
164 sreal prop_time_benefit
;
165 /* Size cost that specializing the function for this value would bring about
166 in this function alone. */
168 /* Size cost that specializing the function for this value can bring about in
173 : local_time_benefit (0), prop_time_benefit (0),
174 local_size_cost (0), prop_size_cost (0) {}
177 /* Describes one particular value stored in struct ipcp_lattice. */
179 template <typename valtype
>
180 class ipcp_value
: public ipcp_value_base
183 /* The actual value for the given parameter. */
185 /* The list of sources from which this value originates. */
186 ipcp_value_source
<valtype
> *sources
;
187 /* Next pointers in a linked list of all values in a lattice. */
189 /* Next pointers in a linked list of values in a strongly connected component
191 ipcp_value
*scc_next
;
192 /* Next pointers in a linked list of SCCs of values sorted topologically
193 according their sources. */
194 ipcp_value
*topo_next
;
195 /* A specialized node created for this value, NULL if none has been (so far)
197 cgraph_node
*spec_node
;
198 /* Depth first search number and low link for topological sorting of
201 /* True if this value is currently on the topo-sort stack. */
205 : sources (0), next (0), scc_next (0), topo_next (0),
206 spec_node (0), dfs (0), low_link (0), on_stack (false) {}
208 void add_source (cgraph_edge
*cs
, ipcp_value
*src_val
, int src_idx
,
209 HOST_WIDE_INT offset
);
212 /* Lattice describing potential values of a formal parameter of a function, or
213 a part of an aggregate. TOP is represented by a lattice with zero values
214 and with contains_variable and bottom flags cleared. BOTTOM is represented
215 by a lattice with the bottom flag set. In that case, values and
216 contains_variable flag should be disregarded. */
218 template <typename valtype
>
222 /* The list of known values and types in this lattice. Note that values are
223 not deallocated if a lattice is set to bottom because there may be value
224 sources referencing them. */
225 ipcp_value
<valtype
> *values
;
226 /* Number of known values and types in this lattice. */
228 /* The lattice contains a variable component (in addition to values). */
229 bool contains_variable
;
230 /* The value of the lattice is bottom (i.e. variable and unusable for any
234 inline bool is_single_const ();
235 inline bool set_to_bottom ();
236 inline bool set_contains_variable ();
237 bool add_value (valtype newval
, cgraph_edge
*cs
,
238 ipcp_value
<valtype
> *src_val
= NULL
,
239 int src_idx
= 0, HOST_WIDE_INT offset
= -1,
240 ipcp_value
<valtype
> **val_p
= NULL
,
241 bool unlimited
= false);
242 void print (FILE * f
, bool dump_sources
, bool dump_benefits
);
245 /* Lattice of tree values with an offset to describe a part of an
248 struct ipcp_agg_lattice
: public ipcp_lattice
<tree
>
251 /* Offset that is being described by this lattice. */
252 HOST_WIDE_INT offset
;
253 /* Size so that we don't have to re-compute it every time we traverse the
254 list. Must correspond to TYPE_SIZE of all lat values. */
256 /* Next element of the linked list. */
257 struct ipcp_agg_lattice
*next
;
260 /* Lattice of known bits, only capable of holding one value.
261 Bitwise constant propagation propagates which bits of a
277 In the above case, the param 'x' will always have all
278 the bits (except the bits in lsb) set to 0.
279 Hence the mask of 'x' would be 0xff. The mask
280 reflects that the bits in lsb are unknown.
281 The actual propagated value is given by m_value & ~m_mask. */
283 class ipcp_bits_lattice
286 bool bottom_p () { return m_lattice_val
== IPA_BITS_VARYING
; }
287 bool top_p () { return m_lattice_val
== IPA_BITS_UNDEFINED
; }
288 bool constant_p () { return m_lattice_val
== IPA_BITS_CONSTANT
; }
289 bool set_to_bottom ();
290 bool set_to_constant (widest_int
, widest_int
);
292 widest_int
get_value () { return m_value
; }
293 widest_int
get_mask () { return m_mask
; }
295 bool meet_with (ipcp_bits_lattice
& other
, unsigned, signop
,
296 enum tree_code
, tree
);
298 bool meet_with (widest_int
, widest_int
, unsigned);
303 enum { IPA_BITS_UNDEFINED
, IPA_BITS_CONSTANT
, IPA_BITS_VARYING
} m_lattice_val
;
305 /* Similar to ccp_lattice_t, mask represents which bits of value are constant.
306 If a bit in mask is set to 0, then the corresponding bit in
307 value is known to be constant. */
308 widest_int m_value
, m_mask
;
310 bool meet_with_1 (widest_int
, widest_int
, unsigned);
311 void get_value_and_mask (tree
, widest_int
*, widest_int
*);
314 /* Lattice of value ranges. */
316 class ipcp_vr_lattice
321 inline bool bottom_p () const;
322 inline bool top_p () const;
323 inline bool set_to_bottom ();
324 bool meet_with (const value_range
*p_vr
);
325 bool meet_with (const ipcp_vr_lattice
&other
);
326 void init () { gcc_assert (m_vr
.undefined_p ()); }
327 void print (FILE * f
);
330 bool meet_with_1 (const value_range
*other_vr
);
333 /* Structure containing lattices for a parameter itself and for pieces of
334 aggregates that are passed in the parameter or by a reference in a parameter
335 plus some other useful flags. */
337 class ipcp_param_lattices
340 /* Lattice describing the value of the parameter itself. */
341 ipcp_lattice
<tree
> itself
;
342 /* Lattice describing the polymorphic contexts of a parameter. */
343 ipcp_lattice
<ipa_polymorphic_call_context
> ctxlat
;
344 /* Lattices describing aggregate parts. */
345 ipcp_agg_lattice
*aggs
;
346 /* Lattice describing known bits. */
347 ipcp_bits_lattice bits_lattice
;
348 /* Lattice describing value range. */
349 ipcp_vr_lattice m_value_range
;
350 /* Number of aggregate lattices */
352 /* True if aggregate data were passed by reference (as opposed to by
355 /* All aggregate lattices contain a variable component (in addition to
357 bool aggs_contain_variable
;
358 /* The value of all aggregate lattices is bottom (i.e. variable and unusable
359 for any propagation). */
362 /* There is a virtual call based on this parameter. */
366 /* Allocation pools for values and their sources in ipa-cp. */
368 object_allocator
<ipcp_value
<tree
> > ipcp_cst_values_pool
369 ("IPA-CP constant values");
371 object_allocator
<ipcp_value
<ipa_polymorphic_call_context
> >
372 ipcp_poly_ctx_values_pool ("IPA-CP polymorphic contexts");
374 object_allocator
<ipcp_value_source
<tree
> > ipcp_sources_pool
375 ("IPA-CP value sources");
377 object_allocator
<ipcp_agg_lattice
> ipcp_agg_lattice_pool
378 ("IPA_CP aggregate lattices");
380 /* Maximal count found in program. */
382 static profile_count max_count
;
384 /* Original overall size of the program. */
386 static long overall_size
, orig_overall_size
;
388 /* Node name to unique clone suffix number map. */
389 static hash_map
<const char *, unsigned> *clone_num_suffixes
;
391 /* Return the param lattices structure corresponding to the Ith formal
392 parameter of the function described by INFO. */
393 static inline class ipcp_param_lattices
*
394 ipa_get_parm_lattices (class ipa_node_params
*info
, int i
)
396 gcc_assert (i
>= 0 && i
< ipa_get_param_count (info
));
397 gcc_checking_assert (!info
->ipcp_orig_node
);
398 gcc_checking_assert (info
->lattices
);
399 return &(info
->lattices
[i
]);
402 /* Return the lattice corresponding to the scalar value of the Ith formal
403 parameter of the function described by INFO. */
404 static inline ipcp_lattice
<tree
> *
405 ipa_get_scalar_lat (class ipa_node_params
*info
, int i
)
407 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
408 return &plats
->itself
;
411 /* Return the lattice corresponding to the scalar value of the Ith formal
412 parameter of the function described by INFO. */
413 static inline ipcp_lattice
<ipa_polymorphic_call_context
> *
414 ipa_get_poly_ctx_lat (class ipa_node_params
*info
, int i
)
416 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
417 return &plats
->ctxlat
;
420 /* Return whether LAT is a lattice with a single constant and without an
423 template <typename valtype
>
425 ipcp_lattice
<valtype
>::is_single_const ()
427 if (bottom
|| contains_variable
|| values_count
!= 1)
433 /* Print V which is extracted from a value in a lattice to F. */
436 print_ipcp_constant_value (FILE * f
, tree v
)
438 if (TREE_CODE (v
) == ADDR_EXPR
439 && TREE_CODE (TREE_OPERAND (v
, 0)) == CONST_DECL
)
442 print_generic_expr (f
, DECL_INITIAL (TREE_OPERAND (v
, 0)));
445 print_generic_expr (f
, v
);
448 /* Print V which is extracted from a value in a lattice to F. */
451 print_ipcp_constant_value (FILE * f
, ipa_polymorphic_call_context v
)
456 /* Print a lattice LAT to F. */
458 template <typename valtype
>
460 ipcp_lattice
<valtype
>::print (FILE * f
, bool dump_sources
, bool dump_benefits
)
462 ipcp_value
<valtype
> *val
;
467 fprintf (f
, "BOTTOM\n");
471 if (!values_count
&& !contains_variable
)
473 fprintf (f
, "TOP\n");
477 if (contains_variable
)
479 fprintf (f
, "VARIABLE");
485 for (val
= values
; val
; val
= val
->next
)
487 if (dump_benefits
&& prev
)
489 else if (!dump_benefits
&& prev
)
494 print_ipcp_constant_value (f
, val
->value
);
498 ipcp_value_source
<valtype
> *s
;
500 fprintf (f
, " [from:");
501 for (s
= val
->sources
; s
; s
= s
->next
)
502 fprintf (f
, " %i(%f)", s
->cs
->caller
->order
,
503 s
->cs
->sreal_frequency ().to_double ());
508 fprintf (f
, " [loc_time: %g, loc_size: %i, "
509 "prop_time: %g, prop_size: %i]\n",
510 val
->local_time_benefit
.to_double (), val
->local_size_cost
,
511 val
->prop_time_benefit
.to_double (), val
->prop_size_cost
);
518 ipcp_bits_lattice::print (FILE *f
)
521 fprintf (f
, " Bits unknown (TOP)\n");
522 else if (bottom_p ())
523 fprintf (f
, " Bits unusable (BOTTOM)\n");
526 fprintf (f
, " Bits: value = "); print_hex (get_value (), f
);
527 fprintf (f
, ", mask = "); print_hex (get_mask (), f
);
532 /* Print value range lattice to F. */
535 ipcp_vr_lattice::print (FILE * f
)
537 dump_value_range (f
, &m_vr
);
540 /* Print all ipcp_lattices of all functions to F. */
543 print_all_lattices (FILE * f
, bool dump_sources
, bool dump_benefits
)
545 struct cgraph_node
*node
;
548 fprintf (f
, "\nLattices:\n");
549 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
551 class ipa_node_params
*info
;
553 info
= IPA_NODE_REF (node
);
554 /* Skip unoptimized functions and constprop clones since we don't make
555 lattices for them. */
556 if (!info
|| info
->ipcp_orig_node
)
558 fprintf (f
, " Node: %s:\n", node
->dump_name ());
559 count
= ipa_get_param_count (info
);
560 for (i
= 0; i
< count
; i
++)
562 struct ipcp_agg_lattice
*aglat
;
563 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
564 fprintf (f
, " param [%d]: ", i
);
565 plats
->itself
.print (f
, dump_sources
, dump_benefits
);
566 fprintf (f
, " ctxs: ");
567 plats
->ctxlat
.print (f
, dump_sources
, dump_benefits
);
568 plats
->bits_lattice
.print (f
);
570 plats
->m_value_range
.print (f
);
572 if (plats
->virt_call
)
573 fprintf (f
, " virt_call flag set\n");
575 if (plats
->aggs_bottom
)
577 fprintf (f
, " AGGS BOTTOM\n");
580 if (plats
->aggs_contain_variable
)
581 fprintf (f
, " AGGS VARIABLE\n");
582 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
584 fprintf (f
, " %soffset " HOST_WIDE_INT_PRINT_DEC
": ",
585 plats
->aggs_by_ref
? "ref " : "", aglat
->offset
);
586 aglat
->print (f
, dump_sources
, dump_benefits
);
592 /* Determine whether it is at all technically possible to create clones of NODE
593 and store this information in the ipa_node_params structure associated
597 determine_versionability (struct cgraph_node
*node
,
598 class ipa_node_params
*info
)
600 const char *reason
= NULL
;
602 /* There are a number of generic reasons functions cannot be versioned. We
603 also cannot remove parameters if there are type attributes such as fnspec
605 if (node
->alias
|| node
->thunk
)
606 reason
= "alias or thunk";
607 else if (!node
->versionable
)
608 reason
= "not a tree_versionable_function";
609 else if (node
->get_availability () <= AVAIL_INTERPOSABLE
)
610 reason
= "insufficient body availability";
611 else if (!opt_for_fn (node
->decl
, optimize
)
612 || !opt_for_fn (node
->decl
, flag_ipa_cp
))
613 reason
= "non-optimized function";
614 else if (lookup_attribute ("omp declare simd", DECL_ATTRIBUTES (node
->decl
)))
616 /* Ideally we should clone the SIMD clones themselves and create
617 vector copies of them, so IPA-cp and SIMD clones can happily
618 coexist, but that may not be worth the effort. */
619 reason
= "function has SIMD clones";
621 else if (lookup_attribute ("target_clones", DECL_ATTRIBUTES (node
->decl
)))
623 /* Ideally we should clone the target clones themselves and create
624 copies of them, so IPA-cp and target clones can happily
625 coexist, but that may not be worth the effort. */
626 reason
= "function target_clones attribute";
628 /* Don't clone decls local to a comdat group; it breaks and for C++
629 decloned constructors, inlining is always better anyway. */
630 else if (node
->comdat_local_p ())
631 reason
= "comdat-local function";
632 else if (node
->calls_comdat_local
)
634 /* TODO: call is versionable if we make sure that all
635 callers are inside of a comdat group. */
636 reason
= "calls comdat-local function";
639 /* Functions calling BUILT_IN_VA_ARG_PACK and BUILT_IN_VA_ARG_PACK_LEN
640 work only when inlined. Cloning them may still lead to better code
641 because ipa-cp will not give up on cloning further. If the function is
642 external this however leads to wrong code because we may end up producing
643 offline copy of the function. */
644 if (DECL_EXTERNAL (node
->decl
))
645 for (cgraph_edge
*edge
= node
->callees
; !reason
&& edge
;
646 edge
= edge
->next_callee
)
647 if (fndecl_built_in_p (edge
->callee
->decl
, BUILT_IN_NORMAL
))
649 if (DECL_FUNCTION_CODE (edge
->callee
->decl
) == BUILT_IN_VA_ARG_PACK
)
650 reason
= "external function which calls va_arg_pack";
651 if (DECL_FUNCTION_CODE (edge
->callee
->decl
)
652 == BUILT_IN_VA_ARG_PACK_LEN
)
653 reason
= "external function which calls va_arg_pack_len";
656 if (reason
&& dump_file
&& !node
->alias
&& !node
->thunk
)
657 fprintf (dump_file
, "Function %s is not versionable, reason: %s.\n",
658 node
->dump_name (), reason
);
660 info
->versionable
= (reason
== NULL
);
663 /* Return true if it is at all technically possible to create clones of a
667 ipcp_versionable_function_p (struct cgraph_node
*node
)
669 return IPA_NODE_REF (node
) && IPA_NODE_REF (node
)->versionable
;
672 /* Structure holding accumulated information about callers of a node. */
674 struct caller_statistics
676 profile_count count_sum
;
678 int n_calls
, n_hot_calls
;
681 /* Initialize fields of STAT to zeroes. */
684 init_caller_stats (struct caller_statistics
*stats
)
686 stats
->count_sum
= profile_count::zero ();
688 stats
->n_hot_calls
= 0;
692 /* Worker callback of cgraph_for_node_and_aliases accumulating statistics of
693 non-thunk incoming edges to NODE. */
696 gather_caller_stats (struct cgraph_node
*node
, void *data
)
698 struct caller_statistics
*stats
= (struct caller_statistics
*) data
;
699 struct cgraph_edge
*cs
;
701 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
702 if (!cs
->caller
->thunk
)
704 if (cs
->count
.ipa ().initialized_p ())
705 stats
->count_sum
+= cs
->count
.ipa ();
706 stats
->freq_sum
+= cs
->sreal_frequency ();
708 if (cs
->maybe_hot_p ())
709 stats
->n_hot_calls
++;
715 /* Return true if this NODE is viable candidate for cloning. */
718 ipcp_cloning_candidate_p (struct cgraph_node
*node
)
720 struct caller_statistics stats
;
722 gcc_checking_assert (node
->has_gimple_body_p ());
724 if (!opt_for_fn (node
->decl
, flag_ipa_cp_clone
))
727 fprintf (dump_file
, "Not considering %s for cloning; "
728 "-fipa-cp-clone disabled.\n",
733 if (node
->optimize_for_size_p ())
736 fprintf (dump_file
, "Not considering %s for cloning; "
737 "optimizing it for size.\n",
742 init_caller_stats (&stats
);
743 node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
, false);
745 if (ipa_size_summaries
->get (node
)->self_size
< stats
.n_calls
)
748 fprintf (dump_file
, "Considering %s for cloning; code might shrink.\n",
753 /* When profile is available and function is hot, propagate into it even if
754 calls seems cold; constant propagation can improve function's speed
756 if (max_count
> profile_count::zero ())
758 if (stats
.count_sum
> node
->count
.ipa ().apply_scale (90, 100))
761 fprintf (dump_file
, "Considering %s for cloning; "
762 "usually called directly.\n",
767 if (!stats
.n_hot_calls
)
770 fprintf (dump_file
, "Not considering %s for cloning; no hot calls.\n",
775 fprintf (dump_file
, "Considering %s for cloning.\n",
780 template <typename valtype
>
781 class value_topo_info
784 /* Head of the linked list of topologically sorted values. */
785 ipcp_value
<valtype
> *values_topo
;
786 /* Stack for creating SCCs, represented by a linked list too. */
787 ipcp_value
<valtype
> *stack
;
788 /* Counter driving the algorithm in add_val_to_toposort. */
791 value_topo_info () : values_topo (NULL
), stack (NULL
), dfs_counter (0)
793 void add_val (ipcp_value
<valtype
> *cur_val
);
794 void propagate_effects ();
797 /* Arrays representing a topological ordering of call graph nodes and a stack
798 of nodes used during constant propagation and also data required to perform
799 topological sort of values and propagation of benefits in the determined
805 /* Array with obtained topological order of cgraph nodes. */
806 struct cgraph_node
**order
;
807 /* Stack of cgraph nodes used during propagation within SCC until all values
808 in the SCC stabilize. */
809 struct cgraph_node
**stack
;
810 int nnodes
, stack_top
;
812 value_topo_info
<tree
> constants
;
813 value_topo_info
<ipa_polymorphic_call_context
> contexts
;
815 ipa_topo_info () : order(NULL
), stack(NULL
), nnodes(0), stack_top(0),
820 /* Skip edges from and to nodes without ipa_cp enabled.
821 Ignore not available symbols. */
824 ignore_edge_p (cgraph_edge
*e
)
826 enum availability avail
;
827 cgraph_node
*ultimate_target
828 = e
->callee
->function_or_virtual_thunk_symbol (&avail
, e
->caller
);
830 return (avail
<= AVAIL_INTERPOSABLE
831 || !opt_for_fn (ultimate_target
->decl
, optimize
)
832 || !opt_for_fn (ultimate_target
->decl
, flag_ipa_cp
));
835 /* Allocate the arrays in TOPO and topologically sort the nodes into order. */
838 build_toporder_info (class ipa_topo_info
*topo
)
840 topo
->order
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
841 topo
->stack
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
843 gcc_checking_assert (topo
->stack_top
== 0);
844 topo
->nnodes
= ipa_reduced_postorder (topo
->order
, true,
848 /* Free information about strongly connected components and the arrays in
852 free_toporder_info (class ipa_topo_info
*topo
)
854 ipa_free_postorder_info ();
859 /* Add NODE to the stack in TOPO, unless it is already there. */
862 push_node_to_stack (class ipa_topo_info
*topo
, struct cgraph_node
*node
)
864 class ipa_node_params
*info
= IPA_NODE_REF (node
);
865 if (info
->node_enqueued
)
867 info
->node_enqueued
= 1;
868 topo
->stack
[topo
->stack_top
++] = node
;
871 /* Pop a node from the stack in TOPO and return it or return NULL if the stack
874 static struct cgraph_node
*
875 pop_node_from_stack (class ipa_topo_info
*topo
)
879 struct cgraph_node
*node
;
881 node
= topo
->stack
[topo
->stack_top
];
882 IPA_NODE_REF (node
)->node_enqueued
= 0;
889 /* Set lattice LAT to bottom and return true if it previously was not set as
892 template <typename valtype
>
894 ipcp_lattice
<valtype
>::set_to_bottom ()
901 /* Mark lattice as containing an unknown value and return true if it previously
902 was not marked as such. */
904 template <typename valtype
>
906 ipcp_lattice
<valtype
>::set_contains_variable ()
908 bool ret
= !contains_variable
;
909 contains_variable
= true;
913 /* Set all aggregate lattices in PLATS to bottom and return true if they were
914 not previously set as such. */
917 set_agg_lats_to_bottom (class ipcp_param_lattices
*plats
)
919 bool ret
= !plats
->aggs_bottom
;
920 plats
->aggs_bottom
= true;
924 /* Mark all aggregate lattices in PLATS as containing an unknown value and
925 return true if they were not previously marked as such. */
928 set_agg_lats_contain_variable (class ipcp_param_lattices
*plats
)
930 bool ret
= !plats
->aggs_contain_variable
;
931 plats
->aggs_contain_variable
= true;
936 ipcp_vr_lattice::meet_with (const ipcp_vr_lattice
&other
)
938 return meet_with_1 (&other
.m_vr
);
941 /* Meet the current value of the lattice with value range described by VR
945 ipcp_vr_lattice::meet_with (const value_range
*p_vr
)
947 return meet_with_1 (p_vr
);
950 /* Meet the current value of the lattice with value range described by
951 OTHER_VR lattice. Return TRUE if anything changed. */
954 ipcp_vr_lattice::meet_with_1 (const value_range
*other_vr
)
959 if (other_vr
->varying_p ())
960 return set_to_bottom ();
962 value_range
save (m_vr
);
963 m_vr
.union_ (other_vr
);
964 return !m_vr
.equal_p (save
);
967 /* Return true if value range information in the lattice is yet unknown. */
970 ipcp_vr_lattice::top_p () const
972 return m_vr
.undefined_p ();
975 /* Return true if value range information in the lattice is known to be
979 ipcp_vr_lattice::bottom_p () const
981 return m_vr
.varying_p ();
984 /* Set value range information in the lattice to bottom. Return true if it
985 previously was in a different state. */
988 ipcp_vr_lattice::set_to_bottom ()
990 if (m_vr
.varying_p ())
992 /* ?? We create all sorts of VARYING ranges for floats, structures,
993 and other types which we cannot handle as ranges. We should
994 probably avoid handling them throughout the pass, but it's easier
995 to create a sensible VARYING here and let the lattice
997 m_vr
.set_varying (integer_type_node
);
1001 /* Set lattice value to bottom, if it already isn't the case. */
1004 ipcp_bits_lattice::set_to_bottom ()
1008 m_lattice_val
= IPA_BITS_VARYING
;
1014 /* Set to constant if it isn't already. Only meant to be called
1015 when switching state from TOP. */
1018 ipcp_bits_lattice::set_to_constant (widest_int value
, widest_int mask
)
1020 gcc_assert (top_p ());
1021 m_lattice_val
= IPA_BITS_CONSTANT
;
1022 m_value
= wi::bit_and (wi::bit_not (mask
), value
);
1027 /* Convert operand to value, mask form. */
1030 ipcp_bits_lattice::get_value_and_mask (tree operand
, widest_int
*valuep
, widest_int
*maskp
)
1032 wide_int
get_nonzero_bits (const_tree
);
1034 if (TREE_CODE (operand
) == INTEGER_CST
)
1036 *valuep
= wi::to_widest (operand
);
1046 /* Meet operation, similar to ccp_lattice_meet, we xor values
1047 if this->value, value have different values at same bit positions, we want
1048 to drop that bit to varying. Return true if mask is changed.
1049 This function assumes that the lattice value is in CONSTANT state */
1052 ipcp_bits_lattice::meet_with_1 (widest_int value
, widest_int mask
,
1055 gcc_assert (constant_p ());
1057 widest_int old_mask
= m_mask
;
1058 m_mask
= (m_mask
| mask
) | (m_value
^ value
);
1061 if (wi::sext (m_mask
, precision
) == -1)
1062 return set_to_bottom ();
1064 return m_mask
!= old_mask
;
1067 /* Meet the bits lattice with operand
1068 described by <value, mask, sgn, precision. */
1071 ipcp_bits_lattice::meet_with (widest_int value
, widest_int mask
,
1079 if (wi::sext (mask
, precision
) == -1)
1080 return set_to_bottom ();
1081 return set_to_constant (value
, mask
);
1084 return meet_with_1 (value
, mask
, precision
);
1087 /* Meet bits lattice with the result of bit_value_binop (other, operand)
1088 if code is binary operation or bit_value_unop (other) if code is unary op.
1089 In the case when code is nop_expr, no adjustment is required. */
1092 ipcp_bits_lattice::meet_with (ipcp_bits_lattice
& other
, unsigned precision
,
1093 signop sgn
, enum tree_code code
, tree operand
)
1095 if (other
.bottom_p ())
1096 return set_to_bottom ();
1098 if (bottom_p () || other
.top_p ())
1101 widest_int adjusted_value
, adjusted_mask
;
1103 if (TREE_CODE_CLASS (code
) == tcc_binary
)
1105 tree type
= TREE_TYPE (operand
);
1106 widest_int o_value
, o_mask
;
1107 get_value_and_mask (operand
, &o_value
, &o_mask
);
1109 bit_value_binop (code
, sgn
, precision
, &adjusted_value
, &adjusted_mask
,
1110 sgn
, precision
, other
.get_value (), other
.get_mask (),
1111 TYPE_SIGN (type
), TYPE_PRECISION (type
), o_value
, o_mask
);
1113 if (wi::sext (adjusted_mask
, precision
) == -1)
1114 return set_to_bottom ();
1117 else if (TREE_CODE_CLASS (code
) == tcc_unary
)
1119 bit_value_unop (code
, sgn
, precision
, &adjusted_value
,
1120 &adjusted_mask
, sgn
, precision
, other
.get_value (),
1123 if (wi::sext (adjusted_mask
, precision
) == -1)
1124 return set_to_bottom ();
1128 return set_to_bottom ();
1132 if (wi::sext (adjusted_mask
, precision
) == -1)
1133 return set_to_bottom ();
1134 return set_to_constant (adjusted_value
, adjusted_mask
);
1137 return meet_with_1 (adjusted_value
, adjusted_mask
, precision
);
1140 /* Mark bot aggregate and scalar lattices as containing an unknown variable,
1141 return true is any of them has not been marked as such so far. */
1144 set_all_contains_variable (class ipcp_param_lattices
*plats
)
1147 ret
= plats
->itself
.set_contains_variable ();
1148 ret
|= plats
->ctxlat
.set_contains_variable ();
1149 ret
|= set_agg_lats_contain_variable (plats
);
1150 ret
|= plats
->bits_lattice
.set_to_bottom ();
1151 ret
|= plats
->m_value_range
.set_to_bottom ();
1155 /* Worker of call_for_symbol_thunks_and_aliases, increment the integer DATA
1156 points to by the number of callers to NODE. */
1159 count_callers (cgraph_node
*node
, void *data
)
1161 int *caller_count
= (int *) data
;
1163 for (cgraph_edge
*cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
1164 /* Local thunks can be handled transparently, but if the thunk cannot
1165 be optimized out, count it as a real use. */
1166 if (!cs
->caller
->thunk
|| !cs
->caller
->local
)
1171 /* Worker of call_for_symbol_thunks_and_aliases, it is supposed to be called on
1172 the one caller of some other node. Set the caller's corresponding flag. */
1175 set_single_call_flag (cgraph_node
*node
, void *)
1177 cgraph_edge
*cs
= node
->callers
;
1178 /* Local thunks can be handled transparently, skip them. */
1179 while (cs
&& cs
->caller
->thunk
&& cs
->caller
->local
)
1180 cs
= cs
->next_caller
;
1181 if (cs
&& IPA_NODE_REF (cs
->caller
))
1183 IPA_NODE_REF (cs
->caller
)->node_calling_single_call
= true;
1189 /* Initialize ipcp_lattices. */
1192 initialize_node_lattices (struct cgraph_node
*node
)
1194 class ipa_node_params
*info
= IPA_NODE_REF (node
);
1195 struct cgraph_edge
*ie
;
1196 bool disable
= false, variable
= false;
1199 gcc_checking_assert (node
->has_gimple_body_p ());
1201 if (!ipa_get_param_count (info
))
1203 else if (node
->local
)
1205 int caller_count
= 0;
1206 node
->call_for_symbol_thunks_and_aliases (count_callers
, &caller_count
,
1208 gcc_checking_assert (caller_count
> 0);
1209 if (caller_count
== 1)
1210 node
->call_for_symbol_thunks_and_aliases (set_single_call_flag
,
1215 /* When cloning is allowed, we can assume that externally visible
1216 functions are not called. We will compensate this by cloning
1218 if (ipcp_versionable_function_p (node
)
1219 && ipcp_cloning_candidate_p (node
))
1225 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1226 && !node
->alias
&& !node
->thunk
)
1228 fprintf (dump_file
, "Initializing lattices of %s\n",
1229 node
->dump_name ());
1230 if (disable
|| variable
)
1231 fprintf (dump_file
, " Marking all lattices as %s\n",
1232 disable
? "BOTTOM" : "VARIABLE");
1235 auto_vec
<bool, 16> surviving_params
;
1236 bool pre_modified
= false;
1238 clone_info
*cinfo
= clone_info::get (node
);
1240 if (!disable
&& cinfo
&& cinfo
->param_adjustments
)
1242 /* At the moment all IPA optimizations should use the number of
1243 parameters of the prevailing decl as the m_always_copy_start.
1244 Handling any other value would complicate the code below, so for the
1245 time bing let's only assert it is so. */
1246 gcc_assert ((cinfo
->param_adjustments
->m_always_copy_start
1247 == ipa_get_param_count (info
))
1248 || cinfo
->param_adjustments
->m_always_copy_start
< 0);
1250 pre_modified
= true;
1251 cinfo
->param_adjustments
->get_surviving_params (&surviving_params
);
1253 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1254 && !node
->alias
&& !node
->thunk
)
1257 for (int j
= 0; j
< ipa_get_param_count (info
); j
++)
1259 if (j
< (int) surviving_params
.length ()
1260 && surviving_params
[j
])
1265 " The following parameters are dead on arrival:");
1268 fprintf (dump_file
, " %u", j
);
1271 fprintf (dump_file
, "\n");
1275 for (i
= 0; i
< ipa_get_param_count (info
); i
++)
1277 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1279 || (pre_modified
&& (surviving_params
.length () <= (unsigned) i
1280 || !surviving_params
[i
])))
1282 plats
->itself
.set_to_bottom ();
1283 plats
->ctxlat
.set_to_bottom ();
1284 set_agg_lats_to_bottom (plats
);
1285 plats
->bits_lattice
.set_to_bottom ();
1286 plats
->m_value_range
.m_vr
= value_range ();
1287 plats
->m_value_range
.set_to_bottom ();
1291 plats
->m_value_range
.init ();
1293 set_all_contains_variable (plats
);
1297 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
1298 if (ie
->indirect_info
->polymorphic
1299 && ie
->indirect_info
->param_index
>= 0)
1301 gcc_checking_assert (ie
->indirect_info
->param_index
>= 0);
1302 ipa_get_parm_lattices (info
,
1303 ie
->indirect_info
->param_index
)->virt_call
= 1;
1307 /* Return the result of a (possibly arithmetic) operation on the constant
1308 value INPUT. OPERAND is 2nd operand for binary operation. RES_TYPE is
1309 the type of the parameter to which the result is passed. Return
1310 NULL_TREE if that cannot be determined or be considered an
1311 interprocedural invariant. */
1314 ipa_get_jf_arith_result (enum tree_code opcode
, tree input
, tree operand
,
1319 if (opcode
== NOP_EXPR
)
1321 if (!is_gimple_ip_invariant (input
))
1326 if (TREE_CODE_CLASS (opcode
) == tcc_comparison
)
1327 res_type
= boolean_type_node
;
1328 else if (expr_type_first_operand_type_p (opcode
))
1329 res_type
= TREE_TYPE (input
);
1334 if (TREE_CODE_CLASS (opcode
) == tcc_unary
)
1335 res
= fold_unary (opcode
, res_type
, input
);
1337 res
= fold_binary (opcode
, res_type
, input
, operand
);
1339 if (res
&& !is_gimple_ip_invariant (res
))
1345 /* Return the result of a (possibly arithmetic) pass through jump function
1346 JFUNC on the constant value INPUT. RES_TYPE is the type of the parameter
1347 to which the result is passed. Return NULL_TREE if that cannot be
1348 determined or be considered an interprocedural invariant. */
1351 ipa_get_jf_pass_through_result (struct ipa_jump_func
*jfunc
, tree input
,
1354 return ipa_get_jf_arith_result (ipa_get_jf_pass_through_operation (jfunc
),
1356 ipa_get_jf_pass_through_operand (jfunc
),
1360 /* Return the result of an ancestor jump function JFUNC on the constant value
1361 INPUT. Return NULL_TREE if that cannot be determined. */
1364 ipa_get_jf_ancestor_result (struct ipa_jump_func
*jfunc
, tree input
)
1366 gcc_checking_assert (TREE_CODE (input
) != TREE_BINFO
);
1367 if (TREE_CODE (input
) == ADDR_EXPR
)
1369 gcc_checking_assert (is_gimple_ip_invariant_address (input
));
1370 poly_int64 off
= ipa_get_jf_ancestor_offset (jfunc
);
1371 if (known_eq (off
, 0))
1373 poly_int64 byte_offset
= exact_div (off
, BITS_PER_UNIT
);
1374 return build1 (ADDR_EXPR
, TREE_TYPE (input
),
1375 fold_build2 (MEM_REF
, TREE_TYPE (TREE_TYPE (input
)), input
,
1376 build_int_cst (ptr_type_node
, byte_offset
)));
1382 /* Determine whether JFUNC evaluates to a single known constant value and if
1383 so, return it. Otherwise return NULL. INFO describes the caller node or
1384 the one it is inlined to, so that pass-through jump functions can be
1385 evaluated. PARM_TYPE is the type of the parameter to which the result is
1389 ipa_value_from_jfunc (class ipa_node_params
*info
, struct ipa_jump_func
*jfunc
,
1392 if (jfunc
->type
== IPA_JF_CONST
)
1393 return ipa_get_jf_constant (jfunc
);
1394 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1395 || jfunc
->type
== IPA_JF_ANCESTOR
)
1400 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1401 idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1403 idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1405 if (info
->ipcp_orig_node
)
1406 input
= info
->known_csts
[idx
];
1409 ipcp_lattice
<tree
> *lat
;
1412 || idx
>= ipa_get_param_count (info
))
1414 lat
= ipa_get_scalar_lat (info
, idx
);
1415 if (!lat
->is_single_const ())
1417 input
= lat
->values
->value
;
1423 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1424 return ipa_get_jf_pass_through_result (jfunc
, input
, parm_type
);
1426 return ipa_get_jf_ancestor_result (jfunc
, input
);
1432 /* Determine whether JFUNC evaluates to single known polymorphic context, given
1433 that INFO describes the caller node or the one it is inlined to, CS is the
1434 call graph edge corresponding to JFUNC and CSIDX index of the described
1437 ipa_polymorphic_call_context
1438 ipa_context_from_jfunc (ipa_node_params
*info
, cgraph_edge
*cs
, int csidx
,
1439 ipa_jump_func
*jfunc
)
1441 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
1442 ipa_polymorphic_call_context ctx
;
1443 ipa_polymorphic_call_context
*edge_ctx
1444 = cs
? ipa_get_ith_polymorhic_call_context (args
, csidx
) : NULL
;
1446 if (edge_ctx
&& !edge_ctx
->useless_p ())
1449 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1450 || jfunc
->type
== IPA_JF_ANCESTOR
)
1452 ipa_polymorphic_call_context srcctx
;
1454 bool type_preserved
= true;
1455 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1457 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1459 type_preserved
= ipa_get_jf_pass_through_type_preserved (jfunc
);
1460 srcidx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1464 type_preserved
= ipa_get_jf_ancestor_type_preserved (jfunc
);
1465 srcidx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1467 if (info
->ipcp_orig_node
)
1469 if (info
->known_contexts
.exists ())
1470 srcctx
= info
->known_contexts
[srcidx
];
1475 || srcidx
>= ipa_get_param_count (info
))
1477 ipcp_lattice
<ipa_polymorphic_call_context
> *lat
;
1478 lat
= ipa_get_poly_ctx_lat (info
, srcidx
);
1479 if (!lat
->is_single_const ())
1481 srcctx
= lat
->values
->value
;
1483 if (srcctx
.useless_p ())
1485 if (jfunc
->type
== IPA_JF_ANCESTOR
)
1486 srcctx
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
1487 if (!type_preserved
)
1488 srcctx
.possible_dynamic_type_change (cs
->in_polymorphic_cdtor
);
1489 srcctx
.combine_with (ctx
);
1496 /* Emulate effects of unary OPERATION and/or conversion from SRC_TYPE to
1497 DST_TYPE on value range in SRC_VR and store it to DST_VR. Return true if
1498 the result is a range or an anti-range. */
1501 ipa_vr_operation_and_type_effects (value_range
*dst_vr
,
1502 value_range
*src_vr
,
1503 enum tree_code operation
,
1504 tree dst_type
, tree src_type
)
1506 range_fold_unary_expr (dst_vr
, operation
, dst_type
, src_vr
, src_type
);
1507 if (dst_vr
->varying_p () || dst_vr
->undefined_p ())
1512 /* Determine value_range of JFUNC given that INFO describes the caller node or
1513 the one it is inlined to, CS is the call graph edge corresponding to JFUNC
1514 and PARM_TYPE of the parameter. */
1517 ipa_value_range_from_jfunc (ipa_node_params
*info
, cgraph_edge
*cs
,
1518 ipa_jump_func
*jfunc
, tree parm_type
)
1523 ipa_vr_operation_and_type_effects (&vr
,
1525 NOP_EXPR
, parm_type
,
1526 jfunc
->m_vr
->type ());
1527 if (vr
.singleton_p ())
1529 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1532 ipcp_transformation
*sum
1533 = ipcp_get_transformation_summary (cs
->caller
->inlined_to
1534 ? cs
->caller
->inlined_to
1536 if (!sum
|| !sum
->m_vr
)
1539 idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1541 if (!(*sum
->m_vr
)[idx
].known
)
1543 tree vr_type
= ipa_get_type (info
, idx
);
1544 value_range
srcvr (wide_int_to_tree (vr_type
, (*sum
->m_vr
)[idx
].min
),
1545 wide_int_to_tree (vr_type
, (*sum
->m_vr
)[idx
].max
),
1546 (*sum
->m_vr
)[idx
].type
);
1548 enum tree_code operation
= ipa_get_jf_pass_through_operation (jfunc
);
1550 if (TREE_CODE_CLASS (operation
) == tcc_unary
)
1554 if (ipa_vr_operation_and_type_effects (&res
,
1556 operation
, parm_type
,
1562 value_range op_res
, res
;
1563 tree op
= ipa_get_jf_pass_through_operand (jfunc
);
1564 value_range
op_vr (op
, op
);
1566 range_fold_binary_expr (&op_res
, operation
, vr_type
, &srcvr
, &op_vr
);
1567 if (ipa_vr_operation_and_type_effects (&res
,
1569 NOP_EXPR
, parm_type
,
1577 /* See if NODE is a clone with a known aggregate value at a given OFFSET of a
1578 parameter with the given INDEX. */
1581 get_clone_agg_value (struct cgraph_node
*node
, HOST_WIDE_INT offset
,
1584 struct ipa_agg_replacement_value
*aggval
;
1586 aggval
= ipa_get_agg_replacements_for_node (node
);
1589 if (aggval
->offset
== offset
1590 && aggval
->index
== index
)
1591 return aggval
->value
;
1592 aggval
= aggval
->next
;
1597 /* Determine whether ITEM, jump function for an aggregate part, evaluates to a
1598 single known constant value and if so, return it. Otherwise return NULL.
1599 NODE and INFO describes the caller node or the one it is inlined to, and
1600 its related info. */
1603 ipa_agg_value_from_node (class ipa_node_params
*info
,
1604 struct cgraph_node
*node
,
1605 struct ipa_agg_jf_item
*item
)
1607 tree value
= NULL_TREE
;
1610 if (item
->offset
< 0 || item
->jftype
== IPA_JF_UNKNOWN
)
1613 if (item
->jftype
== IPA_JF_CONST
)
1614 return item
->value
.constant
;
1616 gcc_checking_assert (item
->jftype
== IPA_JF_PASS_THROUGH
1617 || item
->jftype
== IPA_JF_LOAD_AGG
);
1619 src_idx
= item
->value
.pass_through
.formal_id
;
1621 if (info
->ipcp_orig_node
)
1623 if (item
->jftype
== IPA_JF_PASS_THROUGH
)
1624 value
= info
->known_csts
[src_idx
];
1626 value
= get_clone_agg_value (node
, item
->value
.load_agg
.offset
,
1629 else if (info
->lattices
)
1631 class ipcp_param_lattices
*src_plats
1632 = ipa_get_parm_lattices (info
, src_idx
);
1634 if (item
->jftype
== IPA_JF_PASS_THROUGH
)
1636 struct ipcp_lattice
<tree
> *lat
= &src_plats
->itself
;
1638 if (!lat
->is_single_const ())
1641 value
= lat
->values
->value
;
1643 else if (src_plats
->aggs
1644 && !src_plats
->aggs_bottom
1645 && !src_plats
->aggs_contain_variable
1646 && src_plats
->aggs_by_ref
== item
->value
.load_agg
.by_ref
)
1648 struct ipcp_agg_lattice
*aglat
;
1650 for (aglat
= src_plats
->aggs
; aglat
; aglat
= aglat
->next
)
1652 if (aglat
->offset
> item
->value
.load_agg
.offset
)
1655 if (aglat
->offset
== item
->value
.load_agg
.offset
)
1657 if (aglat
->is_single_const ())
1658 value
= aglat
->values
->value
;
1668 if (item
->jftype
== IPA_JF_LOAD_AGG
)
1670 tree load_type
= item
->value
.load_agg
.type
;
1671 tree value_type
= TREE_TYPE (value
);
1673 /* Ensure value type is compatible with load type. */
1674 if (!useless_type_conversion_p (load_type
, value_type
))
1678 return ipa_get_jf_arith_result (item
->value
.pass_through
.operation
,
1680 item
->value
.pass_through
.operand
,
1684 /* Determine whether AGG_JFUNC evaluates to a set of known constant value for
1685 an aggregate and if so, return it. Otherwise return an empty set. NODE
1686 and INFO describes the caller node or the one it is inlined to, and its
1689 struct ipa_agg_value_set
1690 ipa_agg_value_set_from_jfunc (class ipa_node_params
*info
, cgraph_node
*node
,
1691 struct ipa_agg_jump_function
*agg_jfunc
)
1693 struct ipa_agg_value_set agg
;
1694 struct ipa_agg_jf_item
*item
;
1698 agg
.by_ref
= agg_jfunc
->by_ref
;
1700 FOR_EACH_VEC_SAFE_ELT (agg_jfunc
->items
, i
, item
)
1702 tree value
= ipa_agg_value_from_node (info
, node
, item
);
1706 struct ipa_agg_value value_item
;
1708 value_item
.offset
= item
->offset
;
1709 value_item
.value
= value
;
1711 agg
.items
.safe_push (value_item
);
1717 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
1718 bottom, not containing a variable component and without any known value at
1722 ipcp_verify_propagated_values (void)
1724 struct cgraph_node
*node
;
1726 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
1728 class ipa_node_params
*info
= IPA_NODE_REF (node
);
1729 if (!opt_for_fn (node
->decl
, flag_ipa_cp
)
1730 || !opt_for_fn (node
->decl
, optimize
))
1732 int i
, count
= ipa_get_param_count (info
);
1734 for (i
= 0; i
< count
; i
++)
1736 ipcp_lattice
<tree
> *lat
= ipa_get_scalar_lat (info
, i
);
1739 && !lat
->contains_variable
1740 && lat
->values_count
== 0)
1744 symtab
->dump (dump_file
);
1745 fprintf (dump_file
, "\nIPA lattices after constant "
1746 "propagation, before gcc_unreachable:\n");
1747 print_all_lattices (dump_file
, true, false);
1756 /* Return true iff X and Y should be considered equal values by IPA-CP. */
1759 values_equal_for_ipcp_p (tree x
, tree y
)
1761 gcc_checking_assert (x
!= NULL_TREE
&& y
!= NULL_TREE
);
1766 if (TREE_CODE (x
) == ADDR_EXPR
1767 && TREE_CODE (y
) == ADDR_EXPR
1768 && TREE_CODE (TREE_OPERAND (x
, 0)) == CONST_DECL
1769 && TREE_CODE (TREE_OPERAND (y
, 0)) == CONST_DECL
)
1770 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x
, 0)),
1771 DECL_INITIAL (TREE_OPERAND (y
, 0)), 0);
1773 return operand_equal_p (x
, y
, 0);
1776 /* Return true iff X and Y should be considered equal contexts by IPA-CP. */
1779 values_equal_for_ipcp_p (ipa_polymorphic_call_context x
,
1780 ipa_polymorphic_call_context y
)
1782 return x
.equal_to (y
);
1786 /* Add a new value source to the value represented by THIS, marking that a
1787 value comes from edge CS and (if the underlying jump function is a
1788 pass-through or an ancestor one) from a caller value SRC_VAL of a caller
1789 parameter described by SRC_INDEX. OFFSET is negative if the source was the
1790 scalar value of the parameter itself or the offset within an aggregate. */
1792 template <typename valtype
>
1794 ipcp_value
<valtype
>::add_source (cgraph_edge
*cs
, ipcp_value
*src_val
,
1795 int src_idx
, HOST_WIDE_INT offset
)
1797 ipcp_value_source
<valtype
> *src
;
1799 src
= new (ipcp_sources_pool
.allocate ()) ipcp_value_source
<valtype
>;
1800 src
->offset
= offset
;
1803 src
->index
= src_idx
;
1805 src
->next
= sources
;
1809 /* Allocate a new ipcp_value holding a tree constant, initialize its value to
1810 SOURCE and clear all other fields. */
1812 static ipcp_value
<tree
> *
1813 allocate_and_init_ipcp_value (tree source
)
1815 ipcp_value
<tree
> *val
;
1817 val
= new (ipcp_cst_values_pool
.allocate ()) ipcp_value
<tree
>();
1818 val
->value
= source
;
1822 /* Allocate a new ipcp_value holding a polymorphic context, initialize its
1823 value to SOURCE and clear all other fields. */
1825 static ipcp_value
<ipa_polymorphic_call_context
> *
1826 allocate_and_init_ipcp_value (ipa_polymorphic_call_context source
)
1828 ipcp_value
<ipa_polymorphic_call_context
> *val
;
1831 val
= new (ipcp_poly_ctx_values_pool
.allocate ())
1832 ipcp_value
<ipa_polymorphic_call_context
>();
1833 val
->value
= source
;
1837 /* Try to add NEWVAL to LAT, potentially creating a new ipcp_value for it. CS,
1838 SRC_VAL SRC_INDEX and OFFSET are meant for add_source and have the same
1839 meaning. OFFSET -1 means the source is scalar and not a part of an
1840 aggregate. If non-NULL, VAL_P records address of existing or newly added
1841 ipcp_value. UNLIMITED means whether value count should not exceed the limit
1842 given by PARAM_IPA_CP_VALUE_LIST_SIZE. */
1844 template <typename valtype
>
1846 ipcp_lattice
<valtype
>::add_value (valtype newval
, cgraph_edge
*cs
,
1847 ipcp_value
<valtype
> *src_val
,
1848 int src_idx
, HOST_WIDE_INT offset
,
1849 ipcp_value
<valtype
> **val_p
,
1852 ipcp_value
<valtype
> *val
, *last_val
= NULL
;
1860 for (val
= values
; val
; last_val
= val
, val
= val
->next
)
1861 if (values_equal_for_ipcp_p (val
->value
, newval
))
1866 if (ipa_edge_within_scc (cs
))
1868 ipcp_value_source
<valtype
> *s
;
1869 for (s
= val
->sources
; s
; s
= s
->next
)
1870 if (s
->cs
== cs
&& s
->val
== src_val
)
1876 val
->add_source (cs
, src_val
, src_idx
, offset
);
1880 if (!unlimited
&& values_count
== opt_for_fn (cs
->caller
->decl
,
1881 param_ipa_cp_value_list_size
))
1883 /* We can only free sources, not the values themselves, because sources
1884 of other values in this SCC might point to them. */
1885 for (val
= values
; val
; val
= val
->next
)
1887 while (val
->sources
)
1889 ipcp_value_source
<valtype
> *src
= val
->sources
;
1890 val
->sources
= src
->next
;
1891 ipcp_sources_pool
.remove ((ipcp_value_source
<tree
>*)src
);
1895 return set_to_bottom ();
1899 val
= allocate_and_init_ipcp_value (newval
);
1900 val
->add_source (cs
, src_val
, src_idx
, offset
);
1903 /* Add the new value to end of value list, which can reduce iterations
1904 of propagation stage for recursive function. */
1906 last_val
->next
= val
;
1916 /* Return true, if a ipcp_value VAL is orginated from parameter value of
1917 self-feeding recursive function via some kind of pass-through jump
1921 self_recursively_generated_p (ipcp_value
<tree
> *val
)
1923 class ipa_node_params
*info
= NULL
;
1925 for (ipcp_value_source
<tree
> *src
= val
->sources
; src
; src
= src
->next
)
1927 cgraph_edge
*cs
= src
->cs
;
1929 if (!src
->val
|| cs
->caller
!= cs
->callee
->function_symbol ())
1932 if (src
->val
== val
)
1936 info
= IPA_NODE_REF (cs
->caller
);
1938 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
,
1940 ipcp_lattice
<tree
> *src_lat
;
1941 ipcp_value
<tree
> *src_val
;
1943 if (src
->offset
== -1)
1944 src_lat
= &plats
->itself
;
1947 struct ipcp_agg_lattice
*src_aglat
;
1949 for (src_aglat
= plats
->aggs
; src_aglat
; src_aglat
= src_aglat
->next
)
1950 if (src_aglat
->offset
== src
->offset
)
1956 src_lat
= src_aglat
;
1959 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1970 /* A helper function that returns result of operation specified by OPCODE on
1971 the value of SRC_VAL. If non-NULL, OPND1_TYPE is expected type for the
1972 value of SRC_VAL. If the operation is binary, OPND2 is a constant value
1973 acting as its second operand. If non-NULL, RES_TYPE is expected type of
1977 get_val_across_arith_op (enum tree_code opcode
,
1980 ipcp_value
<tree
> *src_val
,
1983 tree opnd1
= src_val
->value
;
1985 /* Skip source values that is incompatible with specified type. */
1987 && !useless_type_conversion_p (opnd1_type
, TREE_TYPE (opnd1
)))
1990 return ipa_get_jf_arith_result (opcode
, opnd1
, opnd2
, res_type
);
1993 /* Propagate values through an arithmetic transformation described by a jump
1994 function associated with edge CS, taking values from SRC_LAT and putting
1995 them into DEST_LAT. OPND1_TYPE is expected type for the values in SRC_LAT.
1996 OPND2 is a constant value if transformation is a binary operation.
1997 SRC_OFFSET specifies offset in an aggregate if SRC_LAT describes lattice of
1998 a part of the aggregate. SRC_IDX is the index of the source parameter.
1999 RES_TYPE is the value type of result being propagated into. Return true if
2000 DEST_LAT changed. */
2003 propagate_vals_across_arith_jfunc (cgraph_edge
*cs
,
2004 enum tree_code opcode
,
2007 ipcp_lattice
<tree
> *src_lat
,
2008 ipcp_lattice
<tree
> *dest_lat
,
2009 HOST_WIDE_INT src_offset
,
2013 ipcp_value
<tree
> *src_val
;
2016 /* Due to circular dependencies, propagating within an SCC through arithmetic
2017 transformation would create infinite number of values. But for
2018 self-feeding recursive function, we could allow propagation in a limited
2019 count, and this can enable a simple kind of recursive function versioning.
2020 For other scenario, we would just make lattices bottom. */
2021 if (opcode
!= NOP_EXPR
&& ipa_edge_within_scc (cs
))
2025 int max_recursive_depth
= opt_for_fn(cs
->caller
->decl
,
2026 param_ipa_cp_max_recursive_depth
);
2027 if (src_lat
!= dest_lat
|| max_recursive_depth
< 1)
2028 return dest_lat
->set_contains_variable ();
2030 /* No benefit if recursive execution is in low probability. */
2031 if (cs
->sreal_frequency () * 100
2032 <= ((sreal
) 1) * opt_for_fn (cs
->caller
->decl
,
2033 param_ipa_cp_min_recursive_probability
))
2034 return dest_lat
->set_contains_variable ();
2036 auto_vec
<ipcp_value
<tree
> *, 8> val_seeds
;
2038 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
2040 /* Now we do not use self-recursively generated value as propagation
2041 source, this is absolutely conservative, but could avoid explosion
2042 of lattice's value space, especially when one recursive function
2043 calls another recursive. */
2044 if (self_recursively_generated_p (src_val
))
2046 ipcp_value_source
<tree
> *s
;
2048 /* If the lattice has already been propagated for the call site,
2049 no need to do that again. */
2050 for (s
= src_val
->sources
; s
; s
= s
->next
)
2052 return dest_lat
->set_contains_variable ();
2055 val_seeds
.safe_push (src_val
);
2058 gcc_assert ((int) val_seeds
.length () <= param_ipa_cp_value_list_size
);
2060 /* Recursively generate lattice values with a limited count. */
2061 FOR_EACH_VEC_ELT (val_seeds
, i
, src_val
)
2063 for (int j
= 1; j
< max_recursive_depth
; j
++)
2065 tree cstval
= get_val_across_arith_op (opcode
, opnd1_type
, opnd2
,
2070 ret
|= dest_lat
->add_value (cstval
, cs
, src_val
, src_idx
,
2071 src_offset
, &src_val
, true);
2072 gcc_checking_assert (src_val
);
2075 ret
|= dest_lat
->set_contains_variable ();
2078 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
2080 /* Now we do not use self-recursively generated value as propagation
2081 source, otherwise it is easy to make value space of normal lattice
2083 if (self_recursively_generated_p (src_val
))
2085 ret
|= dest_lat
->set_contains_variable ();
2089 tree cstval
= get_val_across_arith_op (opcode
, opnd1_type
, opnd2
,
2092 ret
|= dest_lat
->add_value (cstval
, cs
, src_val
, src_idx
,
2095 ret
|= dest_lat
->set_contains_variable ();
2101 /* Propagate values through a pass-through jump function JFUNC associated with
2102 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
2103 is the index of the source parameter. PARM_TYPE is the type of the
2104 parameter to which the result is passed. */
2107 propagate_vals_across_pass_through (cgraph_edge
*cs
, ipa_jump_func
*jfunc
,
2108 ipcp_lattice
<tree
> *src_lat
,
2109 ipcp_lattice
<tree
> *dest_lat
, int src_idx
,
2112 return propagate_vals_across_arith_jfunc (cs
,
2113 ipa_get_jf_pass_through_operation (jfunc
),
2115 ipa_get_jf_pass_through_operand (jfunc
),
2116 src_lat
, dest_lat
, -1, src_idx
, parm_type
);
2119 /* Propagate values through an ancestor jump function JFUNC associated with
2120 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
2121 is the index of the source parameter. */
2124 propagate_vals_across_ancestor (struct cgraph_edge
*cs
,
2125 struct ipa_jump_func
*jfunc
,
2126 ipcp_lattice
<tree
> *src_lat
,
2127 ipcp_lattice
<tree
> *dest_lat
, int src_idx
)
2129 ipcp_value
<tree
> *src_val
;
2132 if (ipa_edge_within_scc (cs
))
2133 return dest_lat
->set_contains_variable ();
2135 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
2137 tree t
= ipa_get_jf_ancestor_result (jfunc
, src_val
->value
);
2140 ret
|= dest_lat
->add_value (t
, cs
, src_val
, src_idx
);
2142 ret
|= dest_lat
->set_contains_variable ();
2148 /* Propagate scalar values across jump function JFUNC that is associated with
2149 edge CS and put the values into DEST_LAT. PARM_TYPE is the type of the
2150 parameter to which the result is passed. */
2153 propagate_scalar_across_jump_function (struct cgraph_edge
*cs
,
2154 struct ipa_jump_func
*jfunc
,
2155 ipcp_lattice
<tree
> *dest_lat
,
2158 if (dest_lat
->bottom
)
2161 if (jfunc
->type
== IPA_JF_CONST
)
2163 tree val
= ipa_get_jf_constant (jfunc
);
2164 return dest_lat
->add_value (val
, cs
, NULL
, 0);
2166 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
2167 || jfunc
->type
== IPA_JF_ANCESTOR
)
2169 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2170 ipcp_lattice
<tree
> *src_lat
;
2174 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
2175 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
2177 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
2179 src_lat
= ipa_get_scalar_lat (caller_info
, src_idx
);
2180 if (src_lat
->bottom
)
2181 return dest_lat
->set_contains_variable ();
2183 /* If we would need to clone the caller and cannot, do not propagate. */
2184 if (!ipcp_versionable_function_p (cs
->caller
)
2185 && (src_lat
->contains_variable
2186 || (src_lat
->values_count
> 1)))
2187 return dest_lat
->set_contains_variable ();
2189 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
2190 ret
= propagate_vals_across_pass_through (cs
, jfunc
, src_lat
,
2191 dest_lat
, src_idx
, param_type
);
2193 ret
= propagate_vals_across_ancestor (cs
, jfunc
, src_lat
, dest_lat
,
2196 if (src_lat
->contains_variable
)
2197 ret
|= dest_lat
->set_contains_variable ();
2202 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
2203 use it for indirect inlining), we should propagate them too. */
2204 return dest_lat
->set_contains_variable ();
2207 /* Propagate scalar values across jump function JFUNC that is associated with
2208 edge CS and describes argument IDX and put the values into DEST_LAT. */
2211 propagate_context_across_jump_function (cgraph_edge
*cs
,
2212 ipa_jump_func
*jfunc
, int idx
,
2213 ipcp_lattice
<ipa_polymorphic_call_context
> *dest_lat
)
2215 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
2216 if (dest_lat
->bottom
)
2219 bool added_sth
= false;
2220 bool type_preserved
= true;
2222 ipa_polymorphic_call_context edge_ctx
, *edge_ctx_ptr
2223 = ipa_get_ith_polymorhic_call_context (args
, idx
);
2226 edge_ctx
= *edge_ctx_ptr
;
2228 if (jfunc
->type
== IPA_JF_PASS_THROUGH
2229 || jfunc
->type
== IPA_JF_ANCESTOR
)
2231 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2233 ipcp_lattice
<ipa_polymorphic_call_context
> *src_lat
;
2235 /* TODO: Once we figure out how to propagate speculations, it will
2236 probably be a good idea to switch to speculation if type_preserved is
2237 not set instead of punting. */
2238 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
2240 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
2242 type_preserved
= ipa_get_jf_pass_through_type_preserved (jfunc
);
2243 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
2247 type_preserved
= ipa_get_jf_ancestor_type_preserved (jfunc
);
2248 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
2251 src_lat
= ipa_get_poly_ctx_lat (caller_info
, src_idx
);
2252 /* If we would need to clone the caller and cannot, do not propagate. */
2253 if (!ipcp_versionable_function_p (cs
->caller
)
2254 && (src_lat
->contains_variable
2255 || (src_lat
->values_count
> 1)))
2258 ipcp_value
<ipa_polymorphic_call_context
> *src_val
;
2259 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
2261 ipa_polymorphic_call_context cur
= src_val
->value
;
2263 if (!type_preserved
)
2264 cur
.possible_dynamic_type_change (cs
->in_polymorphic_cdtor
);
2265 if (jfunc
->type
== IPA_JF_ANCESTOR
)
2266 cur
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
2267 /* TODO: In cases we know how the context is going to be used,
2268 we can improve the result by passing proper OTR_TYPE. */
2269 cur
.combine_with (edge_ctx
);
2270 if (!cur
.useless_p ())
2272 if (src_lat
->contains_variable
2273 && !edge_ctx
.equal_to (cur
))
2274 ret
|= dest_lat
->set_contains_variable ();
2275 ret
|= dest_lat
->add_value (cur
, cs
, src_val
, src_idx
);
2284 if (!edge_ctx
.useless_p ())
2285 ret
|= dest_lat
->add_value (edge_ctx
, cs
);
2287 ret
|= dest_lat
->set_contains_variable ();
2293 /* Propagate bits across jfunc that is associated with
2294 edge cs and update dest_lattice accordingly. */
2297 propagate_bits_across_jump_function (cgraph_edge
*cs
, int idx
,
2298 ipa_jump_func
*jfunc
,
2299 ipcp_bits_lattice
*dest_lattice
)
2301 if (dest_lattice
->bottom_p ())
2304 enum availability availability
;
2305 cgraph_node
*callee
= cs
->callee
->function_symbol (&availability
);
2306 class ipa_node_params
*callee_info
= IPA_NODE_REF (callee
);
2307 tree parm_type
= ipa_get_type (callee_info
, idx
);
2309 /* For K&R C programs, ipa_get_type() could return NULL_TREE. Avoid the
2310 transform for these cases. Similarly, we can have bad type mismatches
2311 with LTO, avoid doing anything with those too. */
2313 || (!INTEGRAL_TYPE_P (parm_type
) && !POINTER_TYPE_P (parm_type
)))
2315 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2316 fprintf (dump_file
, "Setting dest_lattice to bottom, because type of "
2317 "param %i of %s is NULL or unsuitable for bits propagation\n",
2318 idx
, cs
->callee
->dump_name ());
2320 return dest_lattice
->set_to_bottom ();
2323 unsigned precision
= TYPE_PRECISION (parm_type
);
2324 signop sgn
= TYPE_SIGN (parm_type
);
2326 if (jfunc
->type
== IPA_JF_PASS_THROUGH
2327 || jfunc
->type
== IPA_JF_ANCESTOR
)
2329 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2330 tree operand
= NULL_TREE
;
2331 enum tree_code code
;
2334 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
2336 code
= ipa_get_jf_pass_through_operation (jfunc
);
2337 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
2338 if (code
!= NOP_EXPR
)
2339 operand
= ipa_get_jf_pass_through_operand (jfunc
);
2343 code
= POINTER_PLUS_EXPR
;
2344 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
2345 unsigned HOST_WIDE_INT offset
= ipa_get_jf_ancestor_offset (jfunc
) / BITS_PER_UNIT
;
2346 operand
= build_int_cstu (size_type_node
, offset
);
2349 class ipcp_param_lattices
*src_lats
2350 = ipa_get_parm_lattices (caller_info
, src_idx
);
2352 /* Try to propagate bits if src_lattice is bottom, but jfunc is known.
2358 Assume lattice for x is bottom, however we can still propagate
2359 result of x & 0xff == 0xff, which gets computed during ccp1 pass
2360 and we store it in jump function during analysis stage. */
2362 if (src_lats
->bits_lattice
.bottom_p ()
2364 return dest_lattice
->meet_with (jfunc
->bits
->value
, jfunc
->bits
->mask
,
2367 return dest_lattice
->meet_with (src_lats
->bits_lattice
, precision
, sgn
,
2371 else if (jfunc
->type
== IPA_JF_ANCESTOR
)
2372 return dest_lattice
->set_to_bottom ();
2373 else if (jfunc
->bits
)
2374 return dest_lattice
->meet_with (jfunc
->bits
->value
, jfunc
->bits
->mask
,
2377 return dest_lattice
->set_to_bottom ();
2380 /* Propagate value range across jump function JFUNC that is associated with
2381 edge CS with param of callee of PARAM_TYPE and update DEST_PLATS
2385 propagate_vr_across_jump_function (cgraph_edge
*cs
, ipa_jump_func
*jfunc
,
2386 class ipcp_param_lattices
*dest_plats
,
2389 ipcp_vr_lattice
*dest_lat
= &dest_plats
->m_value_range
;
2391 if (dest_lat
->bottom_p ())
2395 || (!INTEGRAL_TYPE_P (param_type
)
2396 && !POINTER_TYPE_P (param_type
)))
2397 return dest_lat
->set_to_bottom ();
2399 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
2401 enum tree_code operation
= ipa_get_jf_pass_through_operation (jfunc
);
2402 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2403 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
2404 class ipcp_param_lattices
*src_lats
2405 = ipa_get_parm_lattices (caller_info
, src_idx
);
2406 tree operand_type
= ipa_get_type (caller_info
, src_idx
);
2408 if (src_lats
->m_value_range
.bottom_p ())
2409 return dest_lat
->set_to_bottom ();
2412 if (TREE_CODE_CLASS (operation
) == tcc_unary
)
2413 ipa_vr_operation_and_type_effects (&vr
,
2414 &src_lats
->m_value_range
.m_vr
,
2415 operation
, param_type
,
2417 /* A crude way to prevent unbounded number of value range updates
2418 in SCC components. We should allow limited number of updates within
2420 else if (!ipa_edge_within_scc (cs
))
2422 tree op
= ipa_get_jf_pass_through_operand (jfunc
);
2423 value_range
op_vr (op
, op
);
2424 value_range op_res
,res
;
2426 range_fold_binary_expr (&op_res
, operation
, operand_type
,
2427 &src_lats
->m_value_range
.m_vr
, &op_vr
);
2428 ipa_vr_operation_and_type_effects (&vr
,
2430 NOP_EXPR
, param_type
,
2433 if (!vr
.undefined_p () && !vr
.varying_p ())
2438 if (ipa_vr_operation_and_type_effects (&jvr
, jfunc
->m_vr
,
2441 jfunc
->m_vr
->type ()))
2444 return dest_lat
->meet_with (&vr
);
2447 else if (jfunc
->type
== IPA_JF_CONST
)
2449 tree val
= ipa_get_jf_constant (jfunc
);
2450 if (TREE_CODE (val
) == INTEGER_CST
)
2452 val
= fold_convert (param_type
, val
);
2453 if (TREE_OVERFLOW_P (val
))
2454 val
= drop_tree_overflow (val
);
2456 value_range
tmpvr (val
, val
);
2457 return dest_lat
->meet_with (&tmpvr
);
2463 && ipa_vr_operation_and_type_effects (&vr
, jfunc
->m_vr
, NOP_EXPR
,
2465 jfunc
->m_vr
->type ()))
2466 return dest_lat
->meet_with (&vr
);
2468 return dest_lat
->set_to_bottom ();
2471 /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
2472 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
2473 other cases, return false). If there are no aggregate items, set
2474 aggs_by_ref to NEW_AGGS_BY_REF. */
2477 set_check_aggs_by_ref (class ipcp_param_lattices
*dest_plats
,
2478 bool new_aggs_by_ref
)
2480 if (dest_plats
->aggs
)
2482 if (dest_plats
->aggs_by_ref
!= new_aggs_by_ref
)
2484 set_agg_lats_to_bottom (dest_plats
);
2489 dest_plats
->aggs_by_ref
= new_aggs_by_ref
;
2493 /* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
2494 already existing lattice for the given OFFSET and SIZE, marking all skipped
2495 lattices as containing variable and checking for overlaps. If there is no
2496 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
2497 it with offset, size and contains_variable to PRE_EXISTING, and return true,
2498 unless there are too many already. If there are two many, return false. If
2499 there are overlaps turn whole DEST_PLATS to bottom and return false. If any
2500 skipped lattices were newly marked as containing variable, set *CHANGE to
2501 true. MAX_AGG_ITEMS is the maximum number of lattices. */
2504 merge_agg_lats_step (class ipcp_param_lattices
*dest_plats
,
2505 HOST_WIDE_INT offset
, HOST_WIDE_INT val_size
,
2506 struct ipcp_agg_lattice
***aglat
,
2507 bool pre_existing
, bool *change
, int max_agg_items
)
2509 gcc_checking_assert (offset
>= 0);
2511 while (**aglat
&& (**aglat
)->offset
< offset
)
2513 if ((**aglat
)->offset
+ (**aglat
)->size
> offset
)
2515 set_agg_lats_to_bottom (dest_plats
);
2518 *change
|= (**aglat
)->set_contains_variable ();
2519 *aglat
= &(**aglat
)->next
;
2522 if (**aglat
&& (**aglat
)->offset
== offset
)
2524 if ((**aglat
)->size
!= val_size
)
2526 set_agg_lats_to_bottom (dest_plats
);
2529 gcc_assert (!(**aglat
)->next
2530 || (**aglat
)->next
->offset
>= offset
+ val_size
);
2535 struct ipcp_agg_lattice
*new_al
;
2537 if (**aglat
&& (**aglat
)->offset
< offset
+ val_size
)
2539 set_agg_lats_to_bottom (dest_plats
);
2542 if (dest_plats
->aggs_count
== max_agg_items
)
2544 dest_plats
->aggs_count
++;
2545 new_al
= ipcp_agg_lattice_pool
.allocate ();
2546 memset (new_al
, 0, sizeof (*new_al
));
2548 new_al
->offset
= offset
;
2549 new_al
->size
= val_size
;
2550 new_al
->contains_variable
= pre_existing
;
2552 new_al
->next
= **aglat
;
2558 /* Set all AGLAT and all other aggregate lattices reachable by next pointers as
2559 containing an unknown value. */
2562 set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice
*aglat
)
2567 ret
|= aglat
->set_contains_variable ();
2568 aglat
= aglat
->next
;
2573 /* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
2574 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source
2575 parameter used for lattice value sources. Return true if DEST_PLATS changed
2579 merge_aggregate_lattices (struct cgraph_edge
*cs
,
2580 class ipcp_param_lattices
*dest_plats
,
2581 class ipcp_param_lattices
*src_plats
,
2582 int src_idx
, HOST_WIDE_INT offset_delta
)
2584 bool pre_existing
= dest_plats
->aggs
!= NULL
;
2585 struct ipcp_agg_lattice
**dst_aglat
;
2588 if (set_check_aggs_by_ref (dest_plats
, src_plats
->aggs_by_ref
))
2590 if (src_plats
->aggs_bottom
)
2591 return set_agg_lats_contain_variable (dest_plats
);
2592 if (src_plats
->aggs_contain_variable
)
2593 ret
|= set_agg_lats_contain_variable (dest_plats
);
2594 dst_aglat
= &dest_plats
->aggs
;
2596 int max_agg_items
= opt_for_fn (cs
->callee
->function_symbol ()->decl
,
2597 param_ipa_max_agg_items
);
2598 for (struct ipcp_agg_lattice
*src_aglat
= src_plats
->aggs
;
2600 src_aglat
= src_aglat
->next
)
2602 HOST_WIDE_INT new_offset
= src_aglat
->offset
- offset_delta
;
2606 if (merge_agg_lats_step (dest_plats
, new_offset
, src_aglat
->size
,
2607 &dst_aglat
, pre_existing
, &ret
, max_agg_items
))
2609 struct ipcp_agg_lattice
*new_al
= *dst_aglat
;
2611 dst_aglat
= &(*dst_aglat
)->next
;
2612 if (src_aglat
->bottom
)
2614 ret
|= new_al
->set_contains_variable ();
2617 if (src_aglat
->contains_variable
)
2618 ret
|= new_al
->set_contains_variable ();
2619 for (ipcp_value
<tree
> *val
= src_aglat
->values
;
2622 ret
|= new_al
->add_value (val
->value
, cs
, val
, src_idx
,
2625 else if (dest_plats
->aggs_bottom
)
2628 ret
|= set_chain_of_aglats_contains_variable (*dst_aglat
);
2632 /* Determine whether there is anything to propagate FROM SRC_PLATS through a
2633 pass-through JFUNC and if so, whether it has conform and conforms to the
2634 rules about propagating values passed by reference. */
2637 agg_pass_through_permissible_p (class ipcp_param_lattices
*src_plats
,
2638 struct ipa_jump_func
*jfunc
)
2640 return src_plats
->aggs
2641 && (!src_plats
->aggs_by_ref
2642 || ipa_get_jf_pass_through_agg_preserved (jfunc
));
2645 /* Propagate values through ITEM, jump function for a part of an aggregate,
2646 into corresponding aggregate lattice AGLAT. CS is the call graph edge
2647 associated with the jump function. Return true if AGLAT changed in any
2651 propagate_aggregate_lattice (struct cgraph_edge
*cs
,
2652 struct ipa_agg_jf_item
*item
,
2653 struct ipcp_agg_lattice
*aglat
)
2655 class ipa_node_params
*caller_info
;
2656 class ipcp_param_lattices
*src_plats
;
2657 struct ipcp_lattice
<tree
> *src_lat
;
2658 HOST_WIDE_INT src_offset
;
2663 if (item
->jftype
== IPA_JF_CONST
)
2665 tree value
= item
->value
.constant
;
2667 gcc_checking_assert (is_gimple_ip_invariant (value
));
2668 return aglat
->add_value (value
, cs
, NULL
, 0);
2671 gcc_checking_assert (item
->jftype
== IPA_JF_PASS_THROUGH
2672 || item
->jftype
== IPA_JF_LOAD_AGG
);
2674 caller_info
= IPA_NODE_REF (cs
->caller
);
2675 src_idx
= item
->value
.pass_through
.formal_id
;
2676 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2678 if (item
->jftype
== IPA_JF_PASS_THROUGH
)
2680 load_type
= NULL_TREE
;
2681 src_lat
= &src_plats
->itself
;
2686 HOST_WIDE_INT load_offset
= item
->value
.load_agg
.offset
;
2687 struct ipcp_agg_lattice
*src_aglat
;
2689 for (src_aglat
= src_plats
->aggs
; src_aglat
; src_aglat
= src_aglat
->next
)
2690 if (src_aglat
->offset
>= load_offset
)
2693 load_type
= item
->value
.load_agg
.type
;
2695 || src_aglat
->offset
> load_offset
2696 || src_aglat
->size
!= tree_to_shwi (TYPE_SIZE (load_type
))
2697 || src_plats
->aggs_by_ref
!= item
->value
.load_agg
.by_ref
)
2698 return aglat
->set_contains_variable ();
2700 src_lat
= src_aglat
;
2701 src_offset
= load_offset
;
2705 || (!ipcp_versionable_function_p (cs
->caller
)
2706 && !src_lat
->is_single_const ()))
2707 return aglat
->set_contains_variable ();
2709 ret
= propagate_vals_across_arith_jfunc (cs
,
2710 item
->value
.pass_through
.operation
,
2712 item
->value
.pass_through
.operand
,
2718 if (src_lat
->contains_variable
)
2719 ret
|= aglat
->set_contains_variable ();
2724 /* Propagate scalar values across jump function JFUNC that is associated with
2725 edge CS and put the values into DEST_LAT. */
2728 propagate_aggs_across_jump_function (struct cgraph_edge
*cs
,
2729 struct ipa_jump_func
*jfunc
,
2730 class ipcp_param_lattices
*dest_plats
)
2734 if (dest_plats
->aggs_bottom
)
2737 if (jfunc
->type
== IPA_JF_PASS_THROUGH
2738 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
2740 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2741 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
2742 class ipcp_param_lattices
*src_plats
;
2744 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2745 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
2747 /* Currently we do not produce clobber aggregate jump
2748 functions, replace with merging when we do. */
2749 gcc_assert (!jfunc
->agg
.items
);
2750 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
,
2755 else if (jfunc
->type
== IPA_JF_ANCESTOR
2756 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
2758 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2759 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
2760 class ipcp_param_lattices
*src_plats
;
2762 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2763 if (src_plats
->aggs
&& src_plats
->aggs_by_ref
)
2765 /* Currently we do not produce clobber aggregate jump
2766 functions, replace with merging when we do. */
2767 gcc_assert (!jfunc
->agg
.items
);
2768 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
, src_idx
,
2769 ipa_get_jf_ancestor_offset (jfunc
));
2771 else if (!src_plats
->aggs_by_ref
)
2772 ret
|= set_agg_lats_to_bottom (dest_plats
);
2774 ret
|= set_agg_lats_contain_variable (dest_plats
);
2778 if (jfunc
->agg
.items
)
2780 bool pre_existing
= dest_plats
->aggs
!= NULL
;
2781 struct ipcp_agg_lattice
**aglat
= &dest_plats
->aggs
;
2782 struct ipa_agg_jf_item
*item
;
2785 if (set_check_aggs_by_ref (dest_plats
, jfunc
->agg
.by_ref
))
2788 int max_agg_items
= opt_for_fn (cs
->callee
->function_symbol ()->decl
,
2789 param_ipa_max_agg_items
);
2790 FOR_EACH_VEC_ELT (*jfunc
->agg
.items
, i
, item
)
2792 HOST_WIDE_INT val_size
;
2794 if (item
->offset
< 0 || item
->jftype
== IPA_JF_UNKNOWN
)
2796 val_size
= tree_to_shwi (TYPE_SIZE (item
->type
));
2798 if (merge_agg_lats_step (dest_plats
, item
->offset
, val_size
,
2799 &aglat
, pre_existing
, &ret
, max_agg_items
))
2801 ret
|= propagate_aggregate_lattice (cs
, item
, *aglat
);
2802 aglat
= &(*aglat
)->next
;
2804 else if (dest_plats
->aggs_bottom
)
2808 ret
|= set_chain_of_aglats_contains_variable (*aglat
);
2811 ret
|= set_agg_lats_contain_variable (dest_plats
);
2816 /* Return true if on the way cfrom CS->caller to the final (non-alias and
2817 non-thunk) destination, the call passes through a thunk. */
2820 call_passes_through_thunk (cgraph_edge
*cs
)
2822 cgraph_node
*alias_or_thunk
= cs
->callee
;
2823 while (alias_or_thunk
->alias
)
2824 alias_or_thunk
= alias_or_thunk
->get_alias_target ();
2825 return alias_or_thunk
->thunk
;
2828 /* Propagate constants from the caller to the callee of CS. INFO describes the
2832 propagate_constants_across_call (struct cgraph_edge
*cs
)
2834 class ipa_node_params
*callee_info
;
2835 enum availability availability
;
2836 cgraph_node
*callee
;
2837 class ipa_edge_args
*args
;
2839 int i
, args_count
, parms_count
;
2841 callee
= cs
->callee
->function_symbol (&availability
);
2842 if (!callee
->definition
)
2844 gcc_checking_assert (callee
->has_gimple_body_p ());
2845 callee_info
= IPA_NODE_REF (callee
);
2849 args
= IPA_EDGE_REF (cs
);
2850 parms_count
= ipa_get_param_count (callee_info
);
2851 if (parms_count
== 0)
2854 || !opt_for_fn (cs
->caller
->decl
, flag_ipa_cp
)
2855 || !opt_for_fn (cs
->caller
->decl
, optimize
))
2857 for (i
= 0; i
< parms_count
; i
++)
2858 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
2862 args_count
= ipa_get_cs_argument_count (args
);
2864 /* If this call goes through a thunk we must not propagate to the first (0th)
2865 parameter. However, we might need to uncover a thunk from below a series
2866 of aliases first. */
2867 if (call_passes_through_thunk (cs
))
2869 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
2876 for (; (i
< args_count
) && (i
< parms_count
); i
++)
2878 struct ipa_jump_func
*jump_func
= ipa_get_ith_jump_func (args
, i
);
2879 class ipcp_param_lattices
*dest_plats
;
2880 tree param_type
= ipa_get_type (callee_info
, i
);
2882 dest_plats
= ipa_get_parm_lattices (callee_info
, i
);
2883 if (availability
== AVAIL_INTERPOSABLE
)
2884 ret
|= set_all_contains_variable (dest_plats
);
2887 ret
|= propagate_scalar_across_jump_function (cs
, jump_func
,
2888 &dest_plats
->itself
,
2890 ret
|= propagate_context_across_jump_function (cs
, jump_func
, i
,
2891 &dest_plats
->ctxlat
);
2893 |= propagate_bits_across_jump_function (cs
, i
, jump_func
,
2894 &dest_plats
->bits_lattice
);
2895 ret
|= propagate_aggs_across_jump_function (cs
, jump_func
,
2897 if (opt_for_fn (callee
->decl
, flag_ipa_vrp
))
2898 ret
|= propagate_vr_across_jump_function (cs
, jump_func
,
2899 dest_plats
, param_type
);
2901 ret
|= dest_plats
->m_value_range
.set_to_bottom ();
2904 for (; i
< parms_count
; i
++)
2905 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
, i
));
2910 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
2911 KNOWN_CONTEXTS, KNOWN_AGGS or AGG_REPS return the destination. The latter
2912 three can be NULL. If AGG_REPS is not NULL, KNOWN_AGGS is ignored. */
2915 ipa_get_indirect_edge_target_1 (struct cgraph_edge
*ie
,
2916 vec
<tree
> known_csts
,
2917 vec
<ipa_polymorphic_call_context
> known_contexts
,
2918 vec
<ipa_agg_value_set
> known_aggs
,
2919 struct ipa_agg_replacement_value
*agg_reps
,
2922 int param_index
= ie
->indirect_info
->param_index
;
2923 HOST_WIDE_INT anc_offset
;
2927 *speculative
= false;
2929 if (param_index
== -1)
2932 if (!ie
->indirect_info
->polymorphic
)
2936 if (ie
->indirect_info
->agg_contents
)
2939 if (agg_reps
&& ie
->indirect_info
->guaranteed_unmodified
)
2943 if (agg_reps
->index
== param_index
2944 && agg_reps
->offset
== ie
->indirect_info
->offset
2945 && agg_reps
->by_ref
== ie
->indirect_info
->by_ref
)
2947 t
= agg_reps
->value
;
2950 agg_reps
= agg_reps
->next
;
2955 struct ipa_agg_value_set
*agg
;
2956 if (known_aggs
.length () > (unsigned int) param_index
)
2957 agg
= &known_aggs
[param_index
];
2960 bool from_global_constant
;
2961 t
= ipa_find_agg_cst_for_param (agg
,
2962 (unsigned) param_index
2963 < known_csts
.length ()
2964 ? known_csts
[param_index
]
2966 ie
->indirect_info
->offset
,
2967 ie
->indirect_info
->by_ref
,
2968 &from_global_constant
);
2970 && !from_global_constant
2971 && !ie
->indirect_info
->guaranteed_unmodified
)
2975 else if ((unsigned) param_index
< known_csts
.length ())
2976 t
= known_csts
[param_index
];
2979 && TREE_CODE (t
) == ADDR_EXPR
2980 && TREE_CODE (TREE_OPERAND (t
, 0)) == FUNCTION_DECL
)
2981 return TREE_OPERAND (t
, 0);
2986 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize
))
2989 gcc_assert (!ie
->indirect_info
->agg_contents
);
2990 anc_offset
= ie
->indirect_info
->offset
;
2994 /* Try to work out value of virtual table pointer value in replacements. */
2995 if (!t
&& agg_reps
&& !ie
->indirect_info
->by_ref
)
2999 if (agg_reps
->index
== param_index
3000 && agg_reps
->offset
== ie
->indirect_info
->offset
3001 && agg_reps
->by_ref
)
3003 t
= agg_reps
->value
;
3006 agg_reps
= agg_reps
->next
;
3010 /* Try to work out value of virtual table pointer value in known
3011 aggregate values. */
3012 if (!t
&& known_aggs
.length () > (unsigned int) param_index
3013 && !ie
->indirect_info
->by_ref
)
3015 struct ipa_agg_value_set
*agg
= &known_aggs
[param_index
];
3016 t
= ipa_find_agg_cst_for_param (agg
,
3017 (unsigned) param_index
3018 < known_csts
.length ()
3019 ? known_csts
[param_index
] : NULL
,
3020 ie
->indirect_info
->offset
, true);
3023 /* If we found the virtual table pointer, lookup the target. */
3027 unsigned HOST_WIDE_INT offset
;
3028 if (vtable_pointer_value_to_vtable (t
, &vtable
, &offset
))
3031 target
= gimple_get_virt_method_for_vtable (ie
->indirect_info
->otr_token
,
3032 vtable
, offset
, &can_refer
);
3036 || fndecl_built_in_p (target
, BUILT_IN_UNREACHABLE
)
3037 || !possible_polymorphic_call_target_p
3038 (ie
, cgraph_node::get (target
)))
3040 /* Do not speculate builtin_unreachable, it is stupid! */
3041 if (ie
->indirect_info
->vptr_changed
)
3043 target
= ipa_impossible_devirt_target (ie
, target
);
3045 *speculative
= ie
->indirect_info
->vptr_changed
;
3052 /* Do we know the constant value of pointer? */
3053 if (!t
&& (unsigned) param_index
< known_csts
.length ())
3054 t
= known_csts
[param_index
];
3056 gcc_checking_assert (!t
|| TREE_CODE (t
) != TREE_BINFO
);
3058 ipa_polymorphic_call_context context
;
3059 if (known_contexts
.length () > (unsigned int) param_index
)
3061 context
= known_contexts
[param_index
];
3062 context
.offset_by (anc_offset
);
3063 if (ie
->indirect_info
->vptr_changed
)
3064 context
.possible_dynamic_type_change (ie
->in_polymorphic_cdtor
,
3065 ie
->indirect_info
->otr_type
);
3068 ipa_polymorphic_call_context ctx2
= ipa_polymorphic_call_context
3069 (t
, ie
->indirect_info
->otr_type
, anc_offset
);
3070 if (!ctx2
.useless_p ())
3071 context
.combine_with (ctx2
, ie
->indirect_info
->otr_type
);
3076 context
= ipa_polymorphic_call_context (t
, ie
->indirect_info
->otr_type
,
3078 if (ie
->indirect_info
->vptr_changed
)
3079 context
.possible_dynamic_type_change (ie
->in_polymorphic_cdtor
,
3080 ie
->indirect_info
->otr_type
);
3085 vec
<cgraph_node
*>targets
;
3088 targets
= possible_polymorphic_call_targets
3089 (ie
->indirect_info
->otr_type
,
3090 ie
->indirect_info
->otr_token
,
3092 if (!final
|| targets
.length () > 1)
3094 struct cgraph_node
*node
;
3097 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize_speculatively
)
3098 || ie
->speculative
|| !ie
->maybe_hot_p ())
3100 node
= try_speculative_devirtualization (ie
->indirect_info
->otr_type
,
3101 ie
->indirect_info
->otr_token
,
3105 *speculative
= true;
3106 target
= node
->decl
;
3113 *speculative
= false;
3114 if (targets
.length () == 1)
3115 target
= targets
[0]->decl
;
3117 target
= ipa_impossible_devirt_target (ie
, NULL_TREE
);
3120 if (target
&& !possible_polymorphic_call_target_p (ie
,
3121 cgraph_node::get (target
)))
3125 target
= ipa_impossible_devirt_target (ie
, target
);
3131 /* If an indirect edge IE can be turned into a direct one based on data in
3132 AVALS, return the destination. Store into *SPECULATIVE a boolean determinig
3133 whether the discovered target is only speculative guess. */
3136 ipa_get_indirect_edge_target (struct cgraph_edge
*ie
,
3137 ipa_call_arg_values
*avals
,
3140 return ipa_get_indirect_edge_target_1 (ie
, avals
->m_known_vals
,
3141 avals
->m_known_contexts
,
3142 avals
->m_known_aggs
,
3146 /* The same functionality as above overloaded for ipa_auto_call_arg_values. */
3149 ipa_get_indirect_edge_target (struct cgraph_edge
*ie
,
3150 ipa_auto_call_arg_values
*avals
,
3153 return ipa_get_indirect_edge_target_1 (ie
, avals
->m_known_vals
,
3154 avals
->m_known_contexts
,
3155 avals
->m_known_aggs
,
3159 /* Calculate devirtualization time bonus for NODE, assuming we know information
3160 about arguments stored in AVALS. */
3163 devirtualization_time_bonus (struct cgraph_node
*node
,
3164 ipa_auto_call_arg_values
*avals
)
3166 struct cgraph_edge
*ie
;
3169 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
3171 struct cgraph_node
*callee
;
3172 class ipa_fn_summary
*isummary
;
3173 enum availability avail
;
3177 target
= ipa_get_indirect_edge_target (ie
, avals
, &speculative
);
3181 /* Only bare minimum benefit for clearly un-inlineable targets. */
3183 callee
= cgraph_node::get (target
);
3184 if (!callee
|| !callee
->definition
)
3186 callee
= callee
->function_symbol (&avail
);
3187 if (avail
< AVAIL_AVAILABLE
)
3189 isummary
= ipa_fn_summaries
->get (callee
);
3190 if (!isummary
|| !isummary
->inlinable
)
3193 int size
= ipa_size_summaries
->get (callee
)->size
;
3194 /* FIXME: The values below need re-considering and perhaps also
3195 integrating into the cost metrics, at lest in some very basic way. */
3196 int max_inline_insns_auto
3197 = opt_for_fn (callee
->decl
, param_max_inline_insns_auto
);
3198 if (size
<= max_inline_insns_auto
/ 4)
3199 res
+= 31 / ((int)speculative
+ 1);
3200 else if (size
<= max_inline_insns_auto
/ 2)
3201 res
+= 15 / ((int)speculative
+ 1);
3202 else if (size
<= max_inline_insns_auto
3203 || DECL_DECLARED_INLINE_P (callee
->decl
))
3204 res
+= 7 / ((int)speculative
+ 1);
3210 /* Return time bonus incurred because of hints stored in ESTIMATES. */
3213 hint_time_bonus (cgraph_node
*node
, const ipa_call_estimates
&estimates
)
3216 ipa_hints hints
= estimates
.hints
;
3217 if (hints
& (INLINE_HINT_loop_iterations
| INLINE_HINT_loop_stride
))
3218 result
+= opt_for_fn (node
->decl
, param_ipa_cp_loop_hint_bonus
);
3220 sreal bonus_for_one
= opt_for_fn (node
->decl
, param_ipa_cp_loop_hint_bonus
);
3222 if (hints
& INLINE_HINT_loop_iterations
)
3223 result
+= (estimates
.loops_with_known_iterations
* bonus_for_one
).to_int ();
3225 if (hints
& INLINE_HINT_loop_stride
)
3226 result
+= (estimates
.loops_with_known_strides
* bonus_for_one
).to_int ();
3231 /* If there is a reason to penalize the function described by INFO in the
3232 cloning goodness evaluation, do so. */
3235 incorporate_penalties (cgraph_node
*node
, ipa_node_params
*info
,
3238 if (info
->node_within_scc
&& !info
->node_is_self_scc
)
3239 evaluation
= (evaluation
3240 * (100 - opt_for_fn (node
->decl
,
3241 param_ipa_cp_recursion_penalty
))) / 100;
3243 if (info
->node_calling_single_call
)
3244 evaluation
= (evaluation
3245 * (100 - opt_for_fn (node
->decl
,
3246 param_ipa_cp_single_call_penalty
)))
3252 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
3253 and SIZE_COST and with the sum of frequencies of incoming edges to the
3254 potential new clone in FREQUENCIES. */
3257 good_cloning_opportunity_p (struct cgraph_node
*node
, sreal time_benefit
,
3258 sreal freq_sum
, profile_count count_sum
,
3261 if (time_benefit
== 0
3262 || !opt_for_fn (node
->decl
, flag_ipa_cp_clone
)
3263 || node
->optimize_for_size_p ())
3266 gcc_assert (size_cost
> 0);
3267 if (size_cost
== INT_MAX
)
3269 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3270 fprintf (dump_file
, " good_cloning_opportunity_p returning "
3271 "false because of size overflow.\n");
3275 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3276 int eval_threshold
= opt_for_fn (node
->decl
, param_ipa_cp_eval_threshold
);
3277 if (max_count
> profile_count::zero ())
3280 sreal factor
= count_sum
.probability_in (max_count
).to_sreal ();
3281 sreal evaluation
= (time_benefit
* factor
) / size_cost
;
3282 evaluation
= incorporate_penalties (node
, info
, evaluation
);
3285 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3287 fprintf (dump_file
, " good_cloning_opportunity_p (time: %g, "
3288 "size: %i, count_sum: ", time_benefit
.to_double (),
3290 count_sum
.dump (dump_file
);
3291 fprintf (dump_file
, "%s%s) -> evaluation: %.2f, threshold: %i\n",
3292 info
->node_within_scc
3293 ? (info
->node_is_self_scc
? ", self_scc" : ", scc") : "",
3294 info
->node_calling_single_call
? ", single_call" : "",
3295 evaluation
.to_double (), eval_threshold
);
3298 return evaluation
.to_int () >= eval_threshold
;
3302 sreal evaluation
= (time_benefit
* freq_sum
) / size_cost
;
3303 evaluation
= incorporate_penalties (node
, info
, evaluation
);
3306 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3307 fprintf (dump_file
, " good_cloning_opportunity_p (time: %g, "
3308 "size: %i, freq_sum: %g%s%s) -> evaluation: %.2f, "
3310 time_benefit
.to_double (), size_cost
, freq_sum
.to_double (),
3311 info
->node_within_scc
3312 ? (info
->node_is_self_scc
? ", self_scc" : ", scc") : "",
3313 info
->node_calling_single_call
? ", single_call" : "",
3314 evaluation
.to_double (), eval_threshold
);
3316 return evaluation
.to_int () >= eval_threshold
;
3320 /* Return all context independent values from aggregate lattices in PLATS in a
3321 vector. Return NULL if there are none. */
3323 static vec
<ipa_agg_value
>
3324 context_independent_aggregate_values (class ipcp_param_lattices
*plats
)
3326 vec
<ipa_agg_value
> res
= vNULL
;
3328 if (plats
->aggs_bottom
3329 || plats
->aggs_contain_variable
3330 || plats
->aggs_count
== 0)
3333 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
;
3335 aglat
= aglat
->next
)
3336 if (aglat
->is_single_const ())
3338 struct ipa_agg_value item
;
3339 item
.offset
= aglat
->offset
;
3340 item
.value
= aglat
->values
->value
;
3341 res
.safe_push (item
);
3346 /* Grow vectors in AVALS and fill them with information about values of
3347 parameters that are known to be independent of the context. Only calculate
3348 m_known_aggs if CALCULATE_AGGS is true. INFO describes the function. If
3349 REMOVABLE_PARAMS_COST is non-NULL, the movement cost of all removable
3350 parameters will be stored in it.
3352 TODO: Also grow context independent value range vectors. */
3355 gather_context_independent_values (class ipa_node_params
*info
,
3356 ipa_auto_call_arg_values
*avals
,
3357 bool calculate_aggs
,
3358 int *removable_params_cost
)
3360 int i
, count
= ipa_get_param_count (info
);
3363 avals
->m_known_vals
.safe_grow_cleared (count
, true);
3364 avals
->m_known_contexts
.safe_grow_cleared (count
, true);
3366 avals
->m_known_aggs
.safe_grow_cleared (count
, true);
3368 if (removable_params_cost
)
3369 *removable_params_cost
= 0;
3371 for (i
= 0; i
< count
; i
++)
3373 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3374 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
3376 if (lat
->is_single_const ())
3378 ipcp_value
<tree
> *val
= lat
->values
;
3379 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
3380 avals
->m_known_vals
[i
] = val
->value
;
3381 if (removable_params_cost
)
3382 *removable_params_cost
3383 += estimate_move_cost (TREE_TYPE (val
->value
), false);
3386 else if (removable_params_cost
3387 && !ipa_is_param_used (info
, i
))
3388 *removable_params_cost
3389 += ipa_get_param_move_cost (info
, i
);
3391 if (!ipa_is_param_used (info
, i
))
3394 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
3395 /* Do not account known context as reason for cloning. We can see
3396 if it permits devirtualization. */
3397 if (ctxlat
->is_single_const ())
3398 avals
->m_known_contexts
[i
] = ctxlat
->values
->value
;
3402 vec
<ipa_agg_value
> agg_items
;
3403 struct ipa_agg_value_set
*agg
;
3405 agg_items
= context_independent_aggregate_values (plats
);
3406 agg
= &avals
->m_known_aggs
[i
];
3407 agg
->items
= agg_items
;
3408 agg
->by_ref
= plats
->aggs_by_ref
;
3409 ret
|= !agg_items
.is_empty ();
3416 /* Perform time and size measurement of NODE with the context given in AVALS,
3417 calculate the benefit compared to the node without specialization and store
3418 it into VAL. Take into account REMOVABLE_PARAMS_COST of all
3419 context-independent or unused removable parameters and EST_MOVE_COST, the
3420 estimated movement of the considered parameter. */
3423 perform_estimation_of_a_value (cgraph_node
*node
,
3424 ipa_auto_call_arg_values
*avals
,
3425 int removable_params_cost
, int est_move_cost
,
3426 ipcp_value_base
*val
)
3429 ipa_call_estimates estimates
;
3431 estimate_ipcp_clone_size_and_time (node
, avals
, &estimates
);
3433 /* Extern inline functions have no cloning local time benefits because they
3434 will be inlined anyway. The only reason to clone them is if it enables
3435 optimization in any of the functions they call. */
3436 if (DECL_EXTERNAL (node
->decl
) && DECL_DECLARED_INLINE_P (node
->decl
))
3439 time_benefit
= (estimates
.nonspecialized_time
- estimates
.time
)
3440 + (devirtualization_time_bonus (node
, avals
)
3441 + hint_time_bonus (node
, estimates
)
3442 + removable_params_cost
+ est_move_cost
);
3444 int size
= estimates
.size
;
3445 gcc_checking_assert (size
>=0);
3446 /* The inliner-heuristics based estimates may think that in certain
3447 contexts some functions do not have any size at all but we want
3448 all specializations to have at least a tiny cost, not least not to
3453 val
->local_time_benefit
= time_benefit
;
3454 val
->local_size_cost
= size
;
3457 /* Get the overall limit oof growth based on parameters extracted from growth.
3458 it does not really make sense to mix functions with different overall growth
3459 limits but it is possible and if it happens, we do not want to select one
3463 get_max_overall_size (cgraph_node
*node
)
3465 long max_new_size
= orig_overall_size
;
3466 long large_unit
= opt_for_fn (node
->decl
, param_ipa_cp_large_unit_insns
);
3467 if (max_new_size
< large_unit
)
3468 max_new_size
= large_unit
;
3469 int unit_growth
= opt_for_fn (node
->decl
, param_ipa_cp_unit_growth
);
3470 max_new_size
+= max_new_size
* unit_growth
/ 100 + 1;
3471 return max_new_size
;
3474 /* Iterate over known values of parameters of NODE and estimate the local
3475 effects in terms of time and size they have. */
3478 estimate_local_effects (struct cgraph_node
*node
)
3480 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3481 int i
, count
= ipa_get_param_count (info
);
3483 int removable_params_cost
;
3485 if (!count
|| !ipcp_versionable_function_p (node
))
3488 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3489 fprintf (dump_file
, "\nEstimating effects for %s.\n", node
->dump_name ());
3491 ipa_auto_call_arg_values avals
;
3492 always_const
= gather_context_independent_values (info
, &avals
, true,
3493 &removable_params_cost
);
3494 int devirt_bonus
= devirtualization_time_bonus (node
, &avals
);
3495 if (always_const
|| devirt_bonus
3496 || (removable_params_cost
&& node
->can_change_signature
))
3498 struct caller_statistics stats
;
3499 ipa_call_estimates estimates
;
3501 init_caller_stats (&stats
);
3502 node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
3504 estimate_ipcp_clone_size_and_time (node
, &avals
, &estimates
);
3505 sreal time
= estimates
.nonspecialized_time
- estimates
.time
;
3506 time
+= devirt_bonus
;
3507 time
+= hint_time_bonus (node
, estimates
);
3508 time
+= removable_params_cost
;
3509 int size
= estimates
.size
- stats
.n_calls
* removable_params_cost
;
3512 fprintf (dump_file
, " - context independent values, size: %i, "
3513 "time_benefit: %f\n", size
, (time
).to_double ());
3515 if (size
<= 0 || node
->local
)
3517 info
->do_clone_for_all_contexts
= true;
3520 fprintf (dump_file
, " Decided to specialize for all "
3521 "known contexts, code not going to grow.\n");
3523 else if (good_cloning_opportunity_p (node
, time
, stats
.freq_sum
,
3524 stats
.count_sum
, size
))
3526 if (size
+ overall_size
<= get_max_overall_size (node
))
3528 info
->do_clone_for_all_contexts
= true;
3529 overall_size
+= size
;
3532 fprintf (dump_file
, " Decided to specialize for all "
3533 "known contexts, growth (to %li) deemed "
3534 "beneficial.\n", overall_size
);
3536 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3537 fprintf (dump_file
, " Not cloning for all contexts because "
3538 "maximum unit size would be reached with %li.\n",
3539 size
+ overall_size
);
3541 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3542 fprintf (dump_file
, " Not cloning for all contexts because "
3543 "!good_cloning_opportunity_p.\n");
3547 for (i
= 0; i
< count
; i
++)
3549 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3550 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
3551 ipcp_value
<tree
> *val
;
3555 || avals
.m_known_vals
[i
])
3558 for (val
= lat
->values
; val
; val
= val
->next
)
3560 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
3561 avals
.m_known_vals
[i
] = val
->value
;
3563 int emc
= estimate_move_cost (TREE_TYPE (val
->value
), true);
3564 perform_estimation_of_a_value (node
, &avals
, removable_params_cost
,
3567 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3569 fprintf (dump_file
, " - estimates for value ");
3570 print_ipcp_constant_value (dump_file
, val
->value
);
3571 fprintf (dump_file
, " for ");
3572 ipa_dump_param (dump_file
, info
, i
);
3573 fprintf (dump_file
, ": time_benefit: %g, size: %i\n",
3574 val
->local_time_benefit
.to_double (),
3575 val
->local_size_cost
);
3578 avals
.m_known_vals
[i
] = NULL_TREE
;
3581 for (i
= 0; i
< count
; i
++)
3583 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3585 if (!plats
->virt_call
)
3588 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
3589 ipcp_value
<ipa_polymorphic_call_context
> *val
;
3593 || !avals
.m_known_contexts
[i
].useless_p ())
3596 for (val
= ctxlat
->values
; val
; val
= val
->next
)
3598 avals
.m_known_contexts
[i
] = val
->value
;
3599 perform_estimation_of_a_value (node
, &avals
, removable_params_cost
,
3602 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3604 fprintf (dump_file
, " - estimates for polymorphic context ");
3605 print_ipcp_constant_value (dump_file
, val
->value
);
3606 fprintf (dump_file
, " for ");
3607 ipa_dump_param (dump_file
, info
, i
);
3608 fprintf (dump_file
, ": time_benefit: %g, size: %i\n",
3609 val
->local_time_benefit
.to_double (),
3610 val
->local_size_cost
);
3613 avals
.m_known_contexts
[i
] = ipa_polymorphic_call_context ();
3616 for (i
= 0; i
< count
; i
++)
3618 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3620 if (plats
->aggs_bottom
|| !plats
->aggs
)
3623 ipa_agg_value_set
*agg
= &avals
.m_known_aggs
[i
];
3624 for (ipcp_agg_lattice
*aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3626 ipcp_value
<tree
> *val
;
3627 if (aglat
->bottom
|| !aglat
->values
3628 /* If the following is true, the one value is in known_aggs. */
3629 || (!plats
->aggs_contain_variable
3630 && aglat
->is_single_const ()))
3633 for (val
= aglat
->values
; val
; val
= val
->next
)
3635 struct ipa_agg_value item
;
3637 item
.offset
= aglat
->offset
;
3638 item
.value
= val
->value
;
3639 agg
->items
.safe_push (item
);
3641 perform_estimation_of_a_value (node
, &avals
,
3642 removable_params_cost
, 0, val
);
3644 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3646 fprintf (dump_file
, " - estimates for value ");
3647 print_ipcp_constant_value (dump_file
, val
->value
);
3648 fprintf (dump_file
, " for ");
3649 ipa_dump_param (dump_file
, info
, i
);
3650 fprintf (dump_file
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
3651 "]: time_benefit: %g, size: %i\n",
3652 plats
->aggs_by_ref
? "ref " : "",
3654 val
->local_time_benefit
.to_double (),
3655 val
->local_size_cost
);
3665 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
3666 topological sort of values. */
3668 template <typename valtype
>
3670 value_topo_info
<valtype
>::add_val (ipcp_value
<valtype
> *cur_val
)
3672 ipcp_value_source
<valtype
> *src
;
3678 cur_val
->dfs
= dfs_counter
;
3679 cur_val
->low_link
= dfs_counter
;
3681 cur_val
->topo_next
= stack
;
3683 cur_val
->on_stack
= true;
3685 for (src
= cur_val
->sources
; src
; src
= src
->next
)
3688 if (src
->val
->dfs
== 0)
3691 if (src
->val
->low_link
< cur_val
->low_link
)
3692 cur_val
->low_link
= src
->val
->low_link
;
3694 else if (src
->val
->on_stack
3695 && src
->val
->dfs
< cur_val
->low_link
)
3696 cur_val
->low_link
= src
->val
->dfs
;
3699 if (cur_val
->dfs
== cur_val
->low_link
)
3701 ipcp_value
<valtype
> *v
, *scc_list
= NULL
;
3706 stack
= v
->topo_next
;
3707 v
->on_stack
= false;
3709 v
->scc_next
= scc_list
;
3712 while (v
!= cur_val
);
3714 cur_val
->topo_next
= values_topo
;
3715 values_topo
= cur_val
;
3719 /* Add all values in lattices associated with NODE to the topological sort if
3720 they are not there yet. */
3723 add_all_node_vals_to_toposort (cgraph_node
*node
, ipa_topo_info
*topo
)
3725 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3726 int i
, count
= ipa_get_param_count (info
);
3728 for (i
= 0; i
< count
; i
++)
3730 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3731 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
3732 struct ipcp_agg_lattice
*aglat
;
3736 ipcp_value
<tree
> *val
;
3737 for (val
= lat
->values
; val
; val
= val
->next
)
3738 topo
->constants
.add_val (val
);
3741 if (!plats
->aggs_bottom
)
3742 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3745 ipcp_value
<tree
> *val
;
3746 for (val
= aglat
->values
; val
; val
= val
->next
)
3747 topo
->constants
.add_val (val
);
3750 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
3751 if (!ctxlat
->bottom
)
3753 ipcp_value
<ipa_polymorphic_call_context
> *ctxval
;
3754 for (ctxval
= ctxlat
->values
; ctxval
; ctxval
= ctxval
->next
)
3755 topo
->contexts
.add_val (ctxval
);
3760 /* One pass of constants propagation along the call graph edges, from callers
3761 to callees (requires topological ordering in TOPO), iterate over strongly
3762 connected components. */
3765 propagate_constants_topo (class ipa_topo_info
*topo
)
3769 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
3772 struct cgraph_node
*v
, *node
= topo
->order
[i
];
3773 vec
<cgraph_node
*> cycle_nodes
= ipa_get_nodes_in_cycle (node
);
3775 /* First, iteratively propagate within the strongly connected component
3776 until all lattices stabilize. */
3777 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
3778 if (v
->has_gimple_body_p ())
3780 if (opt_for_fn (v
->decl
, flag_ipa_cp
)
3781 && opt_for_fn (v
->decl
, optimize
))
3782 push_node_to_stack (topo
, v
);
3783 /* When V is not optimized, we can not push it to stack, but
3784 still we need to set all its callees lattices to bottom. */
3787 for (cgraph_edge
*cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3788 propagate_constants_across_call (cs
);
3792 v
= pop_node_from_stack (topo
);
3795 struct cgraph_edge
*cs
;
3796 class ipa_node_params
*info
= NULL
;
3797 bool self_scc
= true;
3799 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3800 if (ipa_edge_within_scc (cs
))
3802 cgraph_node
*callee
= cs
->callee
->function_symbol ();
3809 info
= IPA_NODE_REF (v
);
3810 info
->node_within_scc
= true;
3813 if (propagate_constants_across_call (cs
))
3814 push_node_to_stack (topo
, callee
);
3818 info
->node_is_self_scc
= self_scc
;
3820 v
= pop_node_from_stack (topo
);
3823 /* Afterwards, propagate along edges leading out of the SCC, calculates
3824 the local effects of the discovered constants and all valid values to
3825 their topological sort. */
3826 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
3827 if (v
->has_gimple_body_p ()
3828 && opt_for_fn (v
->decl
, flag_ipa_cp
)
3829 && opt_for_fn (v
->decl
, optimize
))
3831 struct cgraph_edge
*cs
;
3833 estimate_local_effects (v
);
3834 add_all_node_vals_to_toposort (v
, topo
);
3835 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3836 if (!ipa_edge_within_scc (cs
))
3837 propagate_constants_across_call (cs
);
3839 cycle_nodes
.release ();
3844 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
3848 safe_add (int a
, int b
)
3850 if (a
> INT_MAX
/2 || b
> INT_MAX
/2)
3857 /* Propagate the estimated effects of individual values along the topological
3858 from the dependent values to those they depend on. */
3860 template <typename valtype
>
3862 value_topo_info
<valtype
>::propagate_effects ()
3864 ipcp_value
<valtype
> *base
;
3866 for (base
= values_topo
; base
; base
= base
->topo_next
)
3868 ipcp_value_source
<valtype
> *src
;
3869 ipcp_value
<valtype
> *val
;
3873 for (val
= base
; val
; val
= val
->scc_next
)
3875 time
= time
+ val
->local_time_benefit
+ val
->prop_time_benefit
;
3876 size
= safe_add (size
, val
->local_size_cost
+ val
->prop_size_cost
);
3879 for (val
= base
; val
; val
= val
->scc_next
)
3880 for (src
= val
->sources
; src
; src
= src
->next
)
3882 && src
->cs
->maybe_hot_p ())
3884 src
->val
->prop_time_benefit
= time
+ src
->val
->prop_time_benefit
;
3885 src
->val
->prop_size_cost
= safe_add (size
,
3886 src
->val
->prop_size_cost
);
3892 /* Propagate constants, polymorphic contexts and their effects from the
3893 summaries interprocedurally. */
3896 ipcp_propagate_stage (class ipa_topo_info
*topo
)
3898 struct cgraph_node
*node
;
3901 fprintf (dump_file
, "\n Propagating constants:\n\n");
3903 max_count
= profile_count::uninitialized ();
3905 FOR_EACH_DEFINED_FUNCTION (node
)
3907 if (node
->has_gimple_body_p ()
3908 && opt_for_fn (node
->decl
, flag_ipa_cp
)
3909 && opt_for_fn (node
->decl
, optimize
))
3911 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3912 determine_versionability (node
, info
);
3914 unsigned nlattices
= ipa_get_param_count (info
);
3915 void *chunk
= XCNEWVEC (class ipcp_param_lattices
, nlattices
);
3916 info
->lattices
= new (chunk
) ipcp_param_lattices
[nlattices
];
3917 initialize_node_lattices (node
);
3919 ipa_size_summary
*s
= ipa_size_summaries
->get (node
);
3920 if (node
->definition
&& !node
->alias
&& s
!= NULL
)
3921 overall_size
+= s
->self_size
;
3922 max_count
= max_count
.max (node
->count
.ipa ());
3925 orig_overall_size
= overall_size
;
3928 fprintf (dump_file
, "\noverall_size: %li\n", overall_size
);
3930 propagate_constants_topo (topo
);
3932 ipcp_verify_propagated_values ();
3933 topo
->constants
.propagate_effects ();
3934 topo
->contexts
.propagate_effects ();
3938 fprintf (dump_file
, "\nIPA lattices after all propagation:\n");
3939 print_all_lattices (dump_file
, (dump_flags
& TDF_DETAILS
), true);
3943 /* Discover newly direct outgoing edges from NODE which is a new clone with
3944 known KNOWN_CSTS and make them direct. */
3947 ipcp_discover_new_direct_edges (struct cgraph_node
*node
,
3948 vec
<tree
> known_csts
,
3949 vec
<ipa_polymorphic_call_context
>
3951 struct ipa_agg_replacement_value
*aggvals
)
3953 struct cgraph_edge
*ie
, *next_ie
;
3956 for (ie
= node
->indirect_calls
; ie
; ie
= next_ie
)
3961 next_ie
= ie
->next_callee
;
3962 target
= ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
3963 vNULL
, aggvals
, &speculative
);
3966 bool agg_contents
= ie
->indirect_info
->agg_contents
;
3967 bool polymorphic
= ie
->indirect_info
->polymorphic
;
3968 int param_index
= ie
->indirect_info
->param_index
;
3969 struct cgraph_edge
*cs
= ipa_make_edge_direct_to_target (ie
, target
,
3973 if (cs
&& !agg_contents
&& !polymorphic
)
3975 class ipa_node_params
*info
= IPA_NODE_REF (node
);
3976 int c
= ipa_get_controlled_uses (info
, param_index
);
3977 if (c
!= IPA_UNDESCRIBED_USE
)
3979 struct ipa_ref
*to_del
;
3982 ipa_set_controlled_uses (info
, param_index
, c
);
3983 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3984 fprintf (dump_file
, " controlled uses count of param "
3985 "%i bumped down to %i\n", param_index
, c
);
3987 && (to_del
= node
->find_reference (cs
->callee
, NULL
, 0)))
3989 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3990 fprintf (dump_file
, " and even removing its "
3991 "cloning-created reference\n");
3992 to_del
->remove_reference ();
3998 /* Turning calls to direct calls will improve overall summary. */
4000 ipa_update_overall_fn_summary (node
);
4003 class edge_clone_summary
;
4004 static call_summary
<edge_clone_summary
*> *edge_clone_summaries
= NULL
;
4006 /* Edge clone summary. */
4008 class edge_clone_summary
4011 /* Default constructor. */
4012 edge_clone_summary (): prev_clone (NULL
), next_clone (NULL
) {}
4014 /* Default destructor. */
4015 ~edge_clone_summary ()
4018 edge_clone_summaries
->get (prev_clone
)->next_clone
= next_clone
;
4020 edge_clone_summaries
->get (next_clone
)->prev_clone
= prev_clone
;
4023 cgraph_edge
*prev_clone
;
4024 cgraph_edge
*next_clone
;
4027 class edge_clone_summary_t
:
4028 public call_summary
<edge_clone_summary
*>
4031 edge_clone_summary_t (symbol_table
*symtab
):
4032 call_summary
<edge_clone_summary
*> (symtab
)
4034 m_initialize_when_cloning
= true;
4037 virtual void duplicate (cgraph_edge
*src_edge
, cgraph_edge
*dst_edge
,
4038 edge_clone_summary
*src_data
,
4039 edge_clone_summary
*dst_data
);
4042 /* Edge duplication hook. */
4045 edge_clone_summary_t::duplicate (cgraph_edge
*src_edge
, cgraph_edge
*dst_edge
,
4046 edge_clone_summary
*src_data
,
4047 edge_clone_summary
*dst_data
)
4049 if (src_data
->next_clone
)
4050 edge_clone_summaries
->get (src_data
->next_clone
)->prev_clone
= dst_edge
;
4051 dst_data
->prev_clone
= src_edge
;
4052 dst_data
->next_clone
= src_data
->next_clone
;
4053 src_data
->next_clone
= dst_edge
;
4056 /* Return true is CS calls DEST or its clone for all contexts. When
4057 ALLOW_RECURSION_TO_CLONE is false, also return false for self-recursive
4058 edges from/to an all-context clone. */
4061 calls_same_node_or_its_all_contexts_clone_p (cgraph_edge
*cs
, cgraph_node
*dest
,
4062 bool allow_recursion_to_clone
)
4064 enum availability availability
;
4065 cgraph_node
*callee
= cs
->callee
->function_symbol (&availability
);
4067 if (availability
<= AVAIL_INTERPOSABLE
)
4071 if (!allow_recursion_to_clone
&& cs
->caller
== callee
)
4074 class ipa_node_params
*info
= IPA_NODE_REF (callee
);
4075 return info
->is_all_contexts_clone
&& info
->ipcp_orig_node
== dest
;
4078 /* Return true if edge CS does bring about the value described by SRC to
4079 DEST_VAL of node DEST or its clone for all contexts. */
4082 cgraph_edge_brings_value_p (cgraph_edge
*cs
, ipcp_value_source
<tree
> *src
,
4083 cgraph_node
*dest
, ipcp_value
<tree
> *dest_val
)
4085 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4087 if (!calls_same_node_or_its_all_contexts_clone_p (cs
, dest
, !src
->val
)
4088 || caller_info
->node_dead
)
4094 if (caller_info
->ipcp_orig_node
)
4097 if (src
->offset
== -1)
4098 t
= caller_info
->known_csts
[src
->index
];
4100 t
= get_clone_agg_value (cs
->caller
, src
->offset
, src
->index
);
4101 return (t
!= NULL_TREE
4102 && values_equal_for_ipcp_p (src
->val
->value
, t
));
4106 if (src
->val
== dest_val
)
4109 struct ipcp_agg_lattice
*aglat
;
4110 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
4112 if (src
->offset
== -1)
4113 return (plats
->itself
.is_single_const ()
4114 && values_equal_for_ipcp_p (src
->val
->value
,
4115 plats
->itself
.values
->value
));
4118 if (plats
->aggs_bottom
|| plats
->aggs_contain_variable
)
4120 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
4121 if (aglat
->offset
== src
->offset
)
4122 return (aglat
->is_single_const ()
4123 && values_equal_for_ipcp_p (src
->val
->value
,
4124 aglat
->values
->value
));
4130 /* Return true if edge CS does bring about the value described by SRC to
4131 DST_VAL of node DEST or its clone for all contexts. */
4134 cgraph_edge_brings_value_p (cgraph_edge
*cs
,
4135 ipcp_value_source
<ipa_polymorphic_call_context
> *src
,
4137 ipcp_value
<ipa_polymorphic_call_context
> *)
4139 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4141 if (!calls_same_node_or_its_all_contexts_clone_p (cs
, dest
, true)
4142 || caller_info
->node_dead
)
4147 if (caller_info
->ipcp_orig_node
)
4148 return (caller_info
->known_contexts
.length () > (unsigned) src
->index
)
4149 && values_equal_for_ipcp_p (src
->val
->value
,
4150 caller_info
->known_contexts
[src
->index
]);
4152 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
4154 return plats
->ctxlat
.is_single_const ()
4155 && values_equal_for_ipcp_p (src
->val
->value
,
4156 plats
->ctxlat
.values
->value
);
4159 /* Get the next clone in the linked list of clones of an edge. */
4161 static inline struct cgraph_edge
*
4162 get_next_cgraph_edge_clone (struct cgraph_edge
*cs
)
4164 edge_clone_summary
*s
= edge_clone_summaries
->get (cs
);
4165 return s
!= NULL
? s
->next_clone
: NULL
;
4168 /* Given VAL that is intended for DEST, iterate over all its sources and if any
4169 of them is viable and hot, return true. In that case, for those that still
4170 hold, add their edge frequency and their number into *FREQUENCY and
4171 *CALLER_COUNT respectively. */
4173 template <typename valtype
>
4175 get_info_about_necessary_edges (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
4176 sreal
*freq_sum
, profile_count
*count_sum
,
4179 ipcp_value_source
<valtype
> *src
;
4182 profile_count cnt
= profile_count::zero ();
4184 bool non_self_recursive
= false;
4186 for (src
= val
->sources
; src
; src
= src
->next
)
4188 struct cgraph_edge
*cs
= src
->cs
;
4191 if (cgraph_edge_brings_value_p (cs
, src
, dest
, val
))
4194 freq
+= cs
->sreal_frequency ();
4195 if (cs
->count
.ipa ().initialized_p ())
4196 cnt
+= cs
->count
.ipa ();
4197 hot
|= cs
->maybe_hot_p ();
4198 if (cs
->caller
!= dest
)
4199 non_self_recursive
= true;
4201 cs
= get_next_cgraph_edge_clone (cs
);
4205 /* If the only edges bringing a value are self-recursive ones, do not bother
4207 if (!non_self_recursive
)
4212 *caller_count
= count
;
4214 if (!hot
&& IPA_NODE_REF (dest
)->node_within_scc
)
4216 struct cgraph_edge
*cs
;
4218 /* Cold non-SCC source edge could trigger hot recursive execution of
4219 function. Consider the case as hot and rely on following cost model
4220 computation to further select right one. */
4221 for (cs
= dest
->callers
; cs
; cs
= cs
->next_caller
)
4222 if (cs
->caller
== dest
&& cs
->maybe_hot_p ())
4229 /* Given a NODE, and a set of its CALLERS, try to adjust order of the callers
4230 to let a non-self-recursive caller be the first element. Thus, we can
4231 simplify intersecting operations on values that arrive from all of these
4232 callers, especially when there exists self-recursive call. Return true if
4233 this kind of adjustment is possible. */
4236 adjust_callers_for_value_intersection (vec
<cgraph_edge
*> callers
,
4239 for (unsigned i
= 0; i
< callers
.length (); i
++)
4241 cgraph_edge
*cs
= callers
[i
];
4243 if (cs
->caller
!= node
)
4247 callers
[i
] = callers
[0];
4256 /* Return a vector of incoming edges that do bring value VAL to node DEST. It
4257 is assumed their number is known and equal to CALLER_COUNT. */
4259 template <typename valtype
>
4260 static vec
<cgraph_edge
*>
4261 gather_edges_for_value (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
4264 ipcp_value_source
<valtype
> *src
;
4265 vec
<cgraph_edge
*> ret
;
4267 ret
.create (caller_count
);
4268 for (src
= val
->sources
; src
; src
= src
->next
)
4270 struct cgraph_edge
*cs
= src
->cs
;
4273 if (cgraph_edge_brings_value_p (cs
, src
, dest
, val
))
4274 ret
.quick_push (cs
);
4275 cs
= get_next_cgraph_edge_clone (cs
);
4279 if (caller_count
> 1)
4280 adjust_callers_for_value_intersection (ret
, dest
);
4285 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
4286 Return it or NULL if for some reason it cannot be created. */
4288 static struct ipa_replace_map
*
4289 get_replacement_map (class ipa_node_params
*info
, tree value
, int parm_num
)
4291 struct ipa_replace_map
*replace_map
;
4293 replace_map
= ggc_alloc
<ipa_replace_map
> ();
4296 fprintf (dump_file
, " replacing ");
4297 ipa_dump_param (dump_file
, info
, parm_num
);
4299 fprintf (dump_file
, " with const ");
4300 print_generic_expr (dump_file
, value
);
4301 fprintf (dump_file
, "\n");
4303 replace_map
->parm_num
= parm_num
;
4304 replace_map
->new_tree
= value
;
4308 /* Dump new profiling counts */
4311 dump_profile_updates (struct cgraph_node
*orig_node
,
4312 struct cgraph_node
*new_node
)
4314 struct cgraph_edge
*cs
;
4316 fprintf (dump_file
, " setting count of the specialized node to ");
4317 new_node
->count
.dump (dump_file
);
4318 fprintf (dump_file
, "\n");
4319 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
4321 fprintf (dump_file
, " edge to %s has count ",
4322 cs
->callee
->dump_name ());
4323 cs
->count
.dump (dump_file
);
4324 fprintf (dump_file
, "\n");
4327 fprintf (dump_file
, " setting count of the original node to ");
4328 orig_node
->count
.dump (dump_file
);
4329 fprintf (dump_file
, "\n");
4330 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
4332 fprintf (dump_file
, " edge to %s is left with ",
4333 cs
->callee
->dump_name ());
4334 cs
->count
.dump (dump_file
);
4335 fprintf (dump_file
, "\n");
4339 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
4340 their profile information to reflect this. */
4343 update_profiling_info (struct cgraph_node
*orig_node
,
4344 struct cgraph_node
*new_node
)
4346 struct cgraph_edge
*cs
;
4347 struct caller_statistics stats
;
4348 profile_count new_sum
, orig_sum
;
4349 profile_count remainder
, orig_node_count
= orig_node
->count
;
4350 profile_count orig_new_node_count
= new_node
->count
;
4352 if (!(orig_node_count
.ipa () > profile_count::zero ()))
4355 init_caller_stats (&stats
);
4356 orig_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
4358 orig_sum
= stats
.count_sum
;
4359 init_caller_stats (&stats
);
4360 new_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
4362 new_sum
= stats
.count_sum
;
4364 if (orig_node_count
< orig_sum
+ new_sum
)
4368 fprintf (dump_file
, " Problem: node %s has too low count ",
4369 orig_node
->dump_name ());
4370 orig_node_count
.dump (dump_file
);
4371 fprintf (dump_file
, "while the sum of incoming count is ");
4372 (orig_sum
+ new_sum
).dump (dump_file
);
4373 fprintf (dump_file
, "\n");
4376 orig_node_count
= (orig_sum
+ new_sum
).apply_scale (12, 10);
4379 fprintf (dump_file
, " proceeding by pretending it was ");
4380 orig_node_count
.dump (dump_file
);
4381 fprintf (dump_file
, "\n");
4385 remainder
= orig_node_count
.combine_with_ipa_count (orig_node_count
.ipa ()
4388 /* With partial train run we do not want to assume that original's
4389 count is zero whenever we redurect all executed edges to clone.
4390 Simply drop profile to local one in this case. */
4391 if (remainder
.ipa_p () && !remainder
.ipa ().nonzero_p ()
4392 && orig_node
->count
.ipa_p () && orig_node
->count
.ipa ().nonzero_p ()
4393 && flag_profile_partial_training
)
4394 remainder
= remainder
.guessed_local ();
4396 new_sum
= orig_node_count
.combine_with_ipa_count (new_sum
);
4397 new_node
->count
= new_sum
;
4398 orig_node
->count
= remainder
;
4400 profile_count::adjust_for_ipa_scaling (&new_sum
, &orig_new_node_count
);
4401 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
4402 cs
->count
= cs
->count
.apply_scale (new_sum
, orig_new_node_count
);
4403 for (cs
= new_node
->indirect_calls
; cs
; cs
= cs
->next_callee
)
4404 cs
->count
= cs
->count
.apply_scale (new_sum
, orig_new_node_count
);
4406 profile_count::adjust_for_ipa_scaling (&remainder
, &orig_node_count
);
4407 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
4408 cs
->count
= cs
->count
.apply_scale (remainder
, orig_node_count
);
4409 for (cs
= orig_node
->indirect_calls
; cs
; cs
= cs
->next_callee
)
4410 cs
->count
= cs
->count
.apply_scale (remainder
, orig_node_count
);
4413 dump_profile_updates (orig_node
, new_node
);
4416 /* Update the respective profile of specialized NEW_NODE and the original
4417 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
4418 have been redirected to the specialized version. */
4421 update_specialized_profile (struct cgraph_node
*new_node
,
4422 struct cgraph_node
*orig_node
,
4423 profile_count redirected_sum
)
4425 struct cgraph_edge
*cs
;
4426 profile_count new_node_count
, orig_node_count
= orig_node
->count
;
4430 fprintf (dump_file
, " the sum of counts of redirected edges is ");
4431 redirected_sum
.dump (dump_file
);
4432 fprintf (dump_file
, "\n");
4434 if (!(orig_node_count
> profile_count::zero ()))
4437 gcc_assert (orig_node_count
>= redirected_sum
);
4439 new_node_count
= new_node
->count
;
4440 new_node
->count
+= redirected_sum
;
4441 orig_node
->count
-= redirected_sum
;
4443 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
4444 cs
->count
+= cs
->count
.apply_scale (redirected_sum
, new_node_count
);
4446 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
4448 profile_count dec
= cs
->count
.apply_scale (redirected_sum
,
4454 dump_profile_updates (orig_node
, new_node
);
4457 /* Return true if we would like to remove a parameter from NODE when cloning it
4458 with KNOWN_CSTS scalar constants. */
4461 want_remove_some_param_p (cgraph_node
*node
, vec
<tree
> known_csts
)
4463 auto_vec
<bool, 16> surviving
;
4464 bool filled_vec
= false;
4465 ipa_node_params
*info
= IPA_NODE_REF (node
);
4466 int i
, count
= ipa_get_param_count (info
);
4468 for (i
= 0; i
< count
; i
++)
4470 if (!known_csts
[i
] && ipa_is_param_used (info
, i
))
4475 clone_info
*info
= clone_info::get (node
);
4476 if (!info
|| !info
->param_adjustments
)
4478 info
->param_adjustments
->get_surviving_params (&surviving
);
4481 if (surviving
.length() < (unsigned) i
&& surviving
[i
])
4487 /* Create a specialized version of NODE with known constants in KNOWN_CSTS,
4488 known contexts in KNOWN_CONTEXTS and known aggregate values in AGGVALS and
4489 redirect all edges in CALLERS to it. */
4491 static struct cgraph_node
*
4492 create_specialized_node (struct cgraph_node
*node
,
4493 vec
<tree
> known_csts
,
4494 vec
<ipa_polymorphic_call_context
> known_contexts
,
4495 struct ipa_agg_replacement_value
*aggvals
,
4496 vec
<cgraph_edge
*> callers
)
4498 class ipa_node_params
*new_info
, *info
= IPA_NODE_REF (node
);
4499 vec
<ipa_replace_map
*, va_gc
> *replace_trees
= NULL
;
4500 vec
<ipa_adjusted_param
, va_gc
> *new_params
= NULL
;
4501 struct ipa_agg_replacement_value
*av
;
4502 struct cgraph_node
*new_node
;
4503 int i
, count
= ipa_get_param_count (info
);
4504 clone_info
*cinfo
= clone_info::get (node
);
4505 ipa_param_adjustments
*old_adjustments
= cinfo
4506 ? cinfo
->param_adjustments
: NULL
;
4507 ipa_param_adjustments
*new_adjustments
;
4508 gcc_assert (!info
->ipcp_orig_node
);
4509 gcc_assert (node
->can_change_signature
4510 || !old_adjustments
);
4512 if (old_adjustments
)
4514 /* At the moment all IPA optimizations should use the number of
4515 parameters of the prevailing decl as the m_always_copy_start.
4516 Handling any other value would complicate the code below, so for the
4517 time bing let's only assert it is so. */
4518 gcc_assert (old_adjustments
->m_always_copy_start
== count
4519 || old_adjustments
->m_always_copy_start
< 0);
4520 int old_adj_count
= vec_safe_length (old_adjustments
->m_adj_params
);
4521 for (i
= 0; i
< old_adj_count
; i
++)
4523 ipa_adjusted_param
*old_adj
= &(*old_adjustments
->m_adj_params
)[i
];
4524 if (!node
->can_change_signature
4525 || old_adj
->op
!= IPA_PARAM_OP_COPY
4526 || (!known_csts
[old_adj
->base_index
]
4527 && ipa_is_param_used (info
, old_adj
->base_index
)))
4529 ipa_adjusted_param new_adj
= *old_adj
;
4531 new_adj
.prev_clone_adjustment
= true;
4532 new_adj
.prev_clone_index
= i
;
4533 vec_safe_push (new_params
, new_adj
);
4536 bool skip_return
= old_adjustments
->m_skip_return
;
4537 new_adjustments
= (new (ggc_alloc
<ipa_param_adjustments
> ())
4538 ipa_param_adjustments (new_params
, count
,
4541 else if (node
->can_change_signature
4542 && want_remove_some_param_p (node
, known_csts
))
4544 ipa_adjusted_param adj
;
4545 memset (&adj
, 0, sizeof (adj
));
4546 adj
.op
= IPA_PARAM_OP_COPY
;
4547 for (i
= 0; i
< count
; i
++)
4548 if (!known_csts
[i
] && ipa_is_param_used (info
, i
))
4551 adj
.prev_clone_index
= i
;
4552 vec_safe_push (new_params
, adj
);
4554 new_adjustments
= (new (ggc_alloc
<ipa_param_adjustments
> ())
4555 ipa_param_adjustments (new_params
, count
, false));
4558 new_adjustments
= NULL
;
4560 replace_trees
= cinfo
? vec_safe_copy (cinfo
->tree_map
) : NULL
;
4561 for (i
= 0; i
< count
; i
++)
4563 tree t
= known_csts
[i
];
4566 struct ipa_replace_map
*replace_map
;
4568 gcc_checking_assert (TREE_CODE (t
) != TREE_BINFO
);
4569 replace_map
= get_replacement_map (info
, t
, i
);
4571 vec_safe_push (replace_trees
, replace_map
);
4574 auto_vec
<cgraph_edge
*, 2> self_recursive_calls
;
4575 for (i
= callers
.length () - 1; i
>= 0; i
--)
4577 cgraph_edge
*cs
= callers
[i
];
4578 if (cs
->caller
== node
)
4580 self_recursive_calls
.safe_push (cs
);
4581 callers
.unordered_remove (i
);
4585 unsigned &suffix_counter
= clone_num_suffixes
->get_or_insert (
4586 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (
4588 new_node
= node
->create_virtual_clone (callers
, replace_trees
,
4589 new_adjustments
, "constprop",
4593 bool have_self_recursive_calls
= !self_recursive_calls
.is_empty ();
4594 for (unsigned j
= 0; j
< self_recursive_calls
.length (); j
++)
4596 cgraph_edge
*cs
= get_next_cgraph_edge_clone (self_recursive_calls
[j
]);
4597 /* Cloned edges can disappear during cloning as speculation can be
4598 resolved, check that we have one and that it comes from the last
4600 if (cs
&& cs
->caller
== new_node
)
4601 cs
->redirect_callee_duplicating_thunks (new_node
);
4602 /* Any future code that would make more than one clone of an outgoing
4603 edge would confuse this mechanism, so let's check that does not
4605 gcc_checking_assert (!cs
4606 || !get_next_cgraph_edge_clone (cs
)
4607 || get_next_cgraph_edge_clone (cs
)->caller
!= new_node
);
4609 if (have_self_recursive_calls
)
4610 new_node
->expand_all_artificial_thunks ();
4612 ipa_set_node_agg_value_chain (new_node
, aggvals
);
4613 for (av
= aggvals
; av
; av
= av
->next
)
4614 new_node
->maybe_create_reference (av
->value
, NULL
);
4616 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4618 fprintf (dump_file
, " the new node is %s.\n", new_node
->dump_name ());
4619 if (known_contexts
.exists ())
4621 for (i
= 0; i
< count
; i
++)
4622 if (!known_contexts
[i
].useless_p ())
4624 fprintf (dump_file
, " known ctx %i is ", i
);
4625 known_contexts
[i
].dump (dump_file
);
4629 ipa_dump_agg_replacement_values (dump_file
, aggvals
);
4631 ipa_check_create_node_params ();
4632 update_profiling_info (node
, new_node
);
4633 new_info
= IPA_NODE_REF (new_node
);
4634 new_info
->ipcp_orig_node
= node
;
4635 new_node
->ipcp_clone
= true;
4636 new_info
->known_csts
= known_csts
;
4637 new_info
->known_contexts
= known_contexts
;
4639 ipcp_discover_new_direct_edges (new_node
, known_csts
, known_contexts
, aggvals
);
4645 /* Return true if JFUNC, which describes a i-th parameter of call CS, is a
4646 pass-through function to itself when the cgraph_node involved is not an
4647 IPA-CP clone. When SIMPLE is true, further check if JFUNC is a simple
4648 no-operation pass-through. */
4651 self_recursive_pass_through_p (cgraph_edge
*cs
, ipa_jump_func
*jfunc
, int i
,
4654 enum availability availability
;
4655 if (cs
->caller
== cs
->callee
->function_symbol (&availability
)
4656 && availability
> AVAIL_INTERPOSABLE
4657 && jfunc
->type
== IPA_JF_PASS_THROUGH
4658 && (!simple
|| ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
4659 && ipa_get_jf_pass_through_formal_id (jfunc
) == i
4660 && IPA_NODE_REF (cs
->caller
)
4661 && !IPA_NODE_REF (cs
->caller
)->ipcp_orig_node
)
4666 /* Return true if JFUNC, which describes a part of an aggregate represented or
4667 pointed to by the i-th parameter of call CS, is a pass-through function to
4668 itself when the cgraph_node involved is not an IPA-CP clone.. When
4669 SIMPLE is true, further check if JFUNC is a simple no-operation
4673 self_recursive_agg_pass_through_p (cgraph_edge
*cs
, ipa_agg_jf_item
*jfunc
,
4674 int i
, bool simple
= true)
4676 enum availability availability
;
4677 if (cs
->caller
== cs
->callee
->function_symbol (&availability
)
4678 && availability
> AVAIL_INTERPOSABLE
4679 && jfunc
->jftype
== IPA_JF_LOAD_AGG
4680 && jfunc
->offset
== jfunc
->value
.load_agg
.offset
4681 && (!simple
|| jfunc
->value
.pass_through
.operation
== NOP_EXPR
)
4682 && jfunc
->value
.pass_through
.formal_id
== i
4683 && useless_type_conversion_p (jfunc
->value
.load_agg
.type
, jfunc
->type
)
4684 && IPA_NODE_REF (cs
->caller
)
4685 && !IPA_NODE_REF (cs
->caller
)->ipcp_orig_node
)
4690 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
4691 KNOWN_CSTS with constants that are also known for all of the CALLERS. */
4694 find_more_scalar_values_for_callers_subset (struct cgraph_node
*node
,
4695 vec
<tree
> known_csts
,
4696 vec
<cgraph_edge
*> callers
)
4698 class ipa_node_params
*info
= IPA_NODE_REF (node
);
4699 int i
, count
= ipa_get_param_count (info
);
4701 for (i
= 0; i
< count
; i
++)
4703 struct cgraph_edge
*cs
;
4704 tree newval
= NULL_TREE
;
4707 tree type
= ipa_get_type (info
, i
);
4709 if (ipa_get_scalar_lat (info
, i
)->bottom
|| known_csts
[i
])
4712 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4714 struct ipa_jump_func
*jump_func
;
4717 if (!IPA_EDGE_REF (cs
)
4718 || i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
))
4720 && call_passes_through_thunk (cs
)))
4725 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
4727 /* Besides simple pass-through jump function, arithmetic jump
4728 function could also introduce argument-direct-pass-through for
4729 self-feeding recursive call. For example,
4736 Given that i is 0, recursive propagation via (i & 1) also gets
4738 if (self_recursive_pass_through_p (cs
, jump_func
, i
, false))
4740 gcc_assert (newval
);
4741 t
= ipa_get_jf_arith_result (
4742 ipa_get_jf_pass_through_operation (jump_func
),
4744 ipa_get_jf_pass_through_operand (jump_func
),
4748 t
= ipa_value_from_jfunc (IPA_NODE_REF (cs
->caller
), jump_func
,
4752 && !values_equal_for_ipcp_p (t
, newval
))
4753 || (!first
&& !newval
))
4765 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4767 fprintf (dump_file
, " adding an extra known scalar value ");
4768 print_ipcp_constant_value (dump_file
, newval
);
4769 fprintf (dump_file
, " for ");
4770 ipa_dump_param (dump_file
, info
, i
);
4771 fprintf (dump_file
, "\n");
4774 known_csts
[i
] = newval
;
4779 /* Given a NODE and a subset of its CALLERS, try to populate plank slots in
4780 KNOWN_CONTEXTS with polymorphic contexts that are also known for all of the
4784 find_more_contexts_for_caller_subset (cgraph_node
*node
,
4785 vec
<ipa_polymorphic_call_context
>
4787 vec
<cgraph_edge
*> callers
)
4789 ipa_node_params
*info
= IPA_NODE_REF (node
);
4790 int i
, count
= ipa_get_param_count (info
);
4792 for (i
= 0; i
< count
; i
++)
4796 if (ipa_get_poly_ctx_lat (info
, i
)->bottom
4797 || (known_contexts
->exists ()
4798 && !(*known_contexts
)[i
].useless_p ()))
4801 ipa_polymorphic_call_context newval
;
4805 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4807 if (!IPA_EDGE_REF (cs
)
4808 || i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
)))
4810 ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
),
4812 ipa_polymorphic_call_context ctx
;
4813 ctx
= ipa_context_from_jfunc (IPA_NODE_REF (cs
->caller
), cs
, i
,
4821 newval
.meet_with (ctx
);
4822 if (newval
.useless_p ())
4826 if (!newval
.useless_p ())
4828 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4830 fprintf (dump_file
, " adding an extra known polymorphic "
4832 print_ipcp_constant_value (dump_file
, newval
);
4833 fprintf (dump_file
, " for ");
4834 ipa_dump_param (dump_file
, info
, i
);
4835 fprintf (dump_file
, "\n");
4838 if (!known_contexts
->exists ())
4839 known_contexts
->safe_grow_cleared (ipa_get_param_count (info
),
4841 (*known_contexts
)[i
] = newval
;
4847 /* Go through PLATS and create a vector of values consisting of values and
4848 offsets (minus OFFSET) of lattices that contain only a single value. */
4850 static vec
<ipa_agg_value
>
4851 copy_plats_to_inter (class ipcp_param_lattices
*plats
, HOST_WIDE_INT offset
)
4853 vec
<ipa_agg_value
> res
= vNULL
;
4855 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
4858 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
4859 if (aglat
->is_single_const ())
4861 struct ipa_agg_value ti
;
4862 ti
.offset
= aglat
->offset
- offset
;
4863 ti
.value
= aglat
->values
->value
;
4869 /* Intersect all values in INTER with single value lattices in PLATS (while
4870 subtracting OFFSET). */
4873 intersect_with_plats (class ipcp_param_lattices
*plats
,
4874 vec
<ipa_agg_value
> *inter
,
4875 HOST_WIDE_INT offset
)
4877 struct ipcp_agg_lattice
*aglat
;
4878 struct ipa_agg_value
*item
;
4881 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
4887 aglat
= plats
->aggs
;
4888 FOR_EACH_VEC_ELT (*inter
, k
, item
)
4895 if (aglat
->offset
- offset
> item
->offset
)
4897 if (aglat
->offset
- offset
== item
->offset
)
4899 if (aglat
->is_single_const ())
4901 tree value
= aglat
->values
->value
;
4903 if (values_equal_for_ipcp_p (item
->value
, value
))
4908 aglat
= aglat
->next
;
4911 item
->value
= NULL_TREE
;
4915 /* Copy aggregate replacement values of NODE (which is an IPA-CP clone) to the
4916 vector result while subtracting OFFSET from the individual value offsets. */
4918 static vec
<ipa_agg_value
>
4919 agg_replacements_to_vector (struct cgraph_node
*node
, int index
,
4920 HOST_WIDE_INT offset
)
4922 struct ipa_agg_replacement_value
*av
;
4923 vec
<ipa_agg_value
> res
= vNULL
;
4925 for (av
= ipa_get_agg_replacements_for_node (node
); av
; av
= av
->next
)
4926 if (av
->index
== index
4927 && (av
->offset
- offset
) >= 0)
4929 struct ipa_agg_value item
;
4930 gcc_checking_assert (av
->value
);
4931 item
.offset
= av
->offset
- offset
;
4932 item
.value
= av
->value
;
4933 res
.safe_push (item
);
4939 /* Intersect all values in INTER with those that we have already scheduled to
4940 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
4941 (while subtracting OFFSET). */
4944 intersect_with_agg_replacements (struct cgraph_node
*node
, int index
,
4945 vec
<ipa_agg_value
> *inter
,
4946 HOST_WIDE_INT offset
)
4948 struct ipa_agg_replacement_value
*srcvals
;
4949 struct ipa_agg_value
*item
;
4952 srcvals
= ipa_get_agg_replacements_for_node (node
);
4959 FOR_EACH_VEC_ELT (*inter
, i
, item
)
4961 struct ipa_agg_replacement_value
*av
;
4965 for (av
= srcvals
; av
; av
= av
->next
)
4967 gcc_checking_assert (av
->value
);
4968 if (av
->index
== index
4969 && av
->offset
- offset
== item
->offset
)
4971 if (values_equal_for_ipcp_p (item
->value
, av
->value
))
4977 item
->value
= NULL_TREE
;
4981 /* Intersect values in INTER with aggregate values that come along edge CS to
4982 parameter number INDEX and return it. If INTER does not actually exist yet,
4983 copy all incoming values to it. If we determine we ended up with no values
4984 whatsoever, return a released vector. */
4986 static vec
<ipa_agg_value
>
4987 intersect_aggregates_with_edge (struct cgraph_edge
*cs
, int index
,
4988 vec
<ipa_agg_value
> inter
)
4990 struct ipa_jump_func
*jfunc
;
4991 jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), index
);
4992 if (jfunc
->type
== IPA_JF_PASS_THROUGH
4993 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
4995 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4996 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
4998 if (caller_info
->ipcp_orig_node
)
5000 struct cgraph_node
*orig_node
= caller_info
->ipcp_orig_node
;
5001 class ipcp_param_lattices
*orig_plats
;
5002 orig_plats
= ipa_get_parm_lattices (IPA_NODE_REF (orig_node
),
5004 if (agg_pass_through_permissible_p (orig_plats
, jfunc
))
5006 if (!inter
.exists ())
5007 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, 0);
5009 intersect_with_agg_replacements (cs
->caller
, src_idx
,
5016 class ipcp_param_lattices
*src_plats
;
5017 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
5018 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
5020 /* Currently we do not produce clobber aggregate jump
5021 functions, adjust when we do. */
5022 gcc_checking_assert (!jfunc
->agg
.items
);
5023 if (!inter
.exists ())
5024 inter
= copy_plats_to_inter (src_plats
, 0);
5026 intersect_with_plats (src_plats
, &inter
, 0);
5031 else if (jfunc
->type
== IPA_JF_ANCESTOR
5032 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
5034 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
5035 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
5036 class ipcp_param_lattices
*src_plats
;
5037 HOST_WIDE_INT delta
= ipa_get_jf_ancestor_offset (jfunc
);
5039 if (caller_info
->ipcp_orig_node
)
5041 if (!inter
.exists ())
5042 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, delta
);
5044 intersect_with_agg_replacements (cs
->caller
, src_idx
, &inter
,
5049 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
5050 /* Currently we do not produce clobber aggregate jump
5051 functions, adjust when we do. */
5052 gcc_checking_assert (!src_plats
->aggs
|| !jfunc
->agg
.items
);
5053 if (!inter
.exists ())
5054 inter
= copy_plats_to_inter (src_plats
, delta
);
5056 intersect_with_plats (src_plats
, &inter
, delta
);
5061 if (jfunc
->agg
.items
)
5063 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
5064 struct ipa_agg_value
*item
;
5067 if (!inter
.exists ())
5068 for (unsigned i
= 0; i
< jfunc
->agg
.items
->length (); i
++)
5070 struct ipa_agg_jf_item
*agg_item
= &(*jfunc
->agg
.items
)[i
];
5071 tree value
= ipa_agg_value_from_node (caller_info
, cs
->caller
,
5075 struct ipa_agg_value agg_value
;
5077 agg_value
.value
= value
;
5078 agg_value
.offset
= agg_item
->offset
;
5079 inter
.safe_push (agg_value
);
5083 FOR_EACH_VEC_ELT (inter
, k
, item
)
5091 while ((unsigned) l
< jfunc
->agg
.items
->length ())
5093 struct ipa_agg_jf_item
*ti
;
5094 ti
= &(*jfunc
->agg
.items
)[l
];
5095 if (ti
->offset
> item
->offset
)
5097 if (ti
->offset
== item
->offset
)
5101 /* Besides simple pass-through aggregate jump function,
5102 arithmetic aggregate jump function could also bring
5103 same aggregate value as parameter passed-in for
5104 self-feeding recursive call. For example,
5112 Given that *i is 0, recursive propagation via (*i & 1)
5114 if (self_recursive_agg_pass_through_p (cs
, ti
, index
,
5116 value
= ipa_get_jf_arith_result (
5117 ti
->value
.pass_through
.operation
,
5119 ti
->value
.pass_through
.operand
,
5122 value
= ipa_agg_value_from_node (caller_info
,
5125 if (value
&& values_equal_for_ipcp_p (item
->value
, value
))
5143 /* Look at edges in CALLERS and collect all known aggregate values that arrive
5144 from all of them. */
5146 static struct ipa_agg_replacement_value
*
5147 find_aggregate_values_for_callers_subset (struct cgraph_node
*node
,
5148 vec
<cgraph_edge
*> callers
)
5150 class ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
5151 struct ipa_agg_replacement_value
*res
;
5152 struct ipa_agg_replacement_value
**tail
= &res
;
5153 struct cgraph_edge
*cs
;
5154 int i
, j
, count
= ipa_get_param_count (dest_info
);
5156 FOR_EACH_VEC_ELT (callers
, j
, cs
)
5158 if (!IPA_EDGE_REF (cs
))
5163 int c
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
5168 for (i
= 0; i
< count
; i
++)
5170 struct cgraph_edge
*cs
;
5171 vec
<ipa_agg_value
> inter
= vNULL
;
5172 struct ipa_agg_value
*item
;
5173 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (dest_info
, i
);
5176 /* Among other things, the following check should deal with all by_ref
5178 if (plats
->aggs_bottom
)
5181 FOR_EACH_VEC_ELT (callers
, j
, cs
)
5183 struct ipa_jump_func
*jfunc
5184 = ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
5185 if (self_recursive_pass_through_p (cs
, jfunc
, i
)
5186 && (!plats
->aggs_by_ref
5187 || ipa_get_jf_pass_through_agg_preserved (jfunc
)))
5189 inter
= intersect_aggregates_with_edge (cs
, i
, inter
);
5191 if (!inter
.exists ())
5195 FOR_EACH_VEC_ELT (inter
, j
, item
)
5197 struct ipa_agg_replacement_value
*v
;
5202 v
= ggc_alloc
<ipa_agg_replacement_value
> ();
5204 v
->offset
= item
->offset
;
5205 v
->value
= item
->value
;
5206 v
->by_ref
= plats
->aggs_by_ref
;
5212 if (inter
.exists ())
5219 /* Determine whether CS also brings all scalar values that the NODE is
5223 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge
*cs
,
5224 struct cgraph_node
*node
)
5226 class ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
5227 int count
= ipa_get_param_count (dest_info
);
5228 class ipa_node_params
*caller_info
;
5229 class ipa_edge_args
*args
;
5232 caller_info
= IPA_NODE_REF (cs
->caller
);
5233 args
= IPA_EDGE_REF (cs
);
5234 for (i
= 0; i
< count
; i
++)
5236 struct ipa_jump_func
*jump_func
;
5239 val
= dest_info
->known_csts
[i
];
5243 if (i
>= ipa_get_cs_argument_count (args
))
5245 jump_func
= ipa_get_ith_jump_func (args
, i
);
5246 t
= ipa_value_from_jfunc (caller_info
, jump_func
,
5247 ipa_get_type (dest_info
, i
));
5248 if (!t
|| !values_equal_for_ipcp_p (val
, t
))
5254 /* Determine whether CS also brings all aggregate values that NODE is
5257 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge
*cs
,
5258 struct cgraph_node
*node
)
5260 class ipa_node_params
*orig_node_info
;
5261 struct ipa_agg_replacement_value
*aggval
;
5264 aggval
= ipa_get_agg_replacements_for_node (node
);
5268 count
= ipa_get_param_count (IPA_NODE_REF (node
));
5269 ec
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
5271 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
5272 if (aggval
->index
>= ec
)
5275 orig_node_info
= IPA_NODE_REF (IPA_NODE_REF (node
)->ipcp_orig_node
);
5277 for (i
= 0; i
< count
; i
++)
5279 class ipcp_param_lattices
*plats
;
5280 bool interesting
= false;
5281 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
5282 if (aggval
->index
== i
)
5290 plats
= ipa_get_parm_lattices (orig_node_info
, aggval
->index
);
5291 if (plats
->aggs_bottom
)
5294 vec
<ipa_agg_value
> values
= intersect_aggregates_with_edge (cs
, i
, vNULL
);
5295 if (!values
.exists ())
5298 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
5299 if (aggval
->index
== i
)
5301 struct ipa_agg_value
*item
;
5304 FOR_EACH_VEC_ELT (values
, j
, item
)
5306 && item
->offset
== av
->offset
5307 && values_equal_for_ipcp_p (item
->value
, av
->value
))
5323 /* Given an original NODE and a VAL for which we have already created a
5324 specialized clone, look whether there are incoming edges that still lead
5325 into the old node but now also bring the requested value and also conform to
5326 all other criteria such that they can be redirected the special node.
5327 This function can therefore redirect the final edge in a SCC. */
5329 template <typename valtype
>
5331 perhaps_add_new_callers (cgraph_node
*node
, ipcp_value
<valtype
> *val
)
5333 ipcp_value_source
<valtype
> *src
;
5334 profile_count redirected_sum
= profile_count::zero ();
5336 for (src
= val
->sources
; src
; src
= src
->next
)
5338 struct cgraph_edge
*cs
= src
->cs
;
5341 if (cgraph_edge_brings_value_p (cs
, src
, node
, val
)
5342 && cgraph_edge_brings_all_scalars_for_node (cs
, val
->spec_node
)
5343 && cgraph_edge_brings_all_agg_vals_for_node (cs
, val
->spec_node
))
5346 fprintf (dump_file
, " - adding an extra caller %s of %s\n",
5347 cs
->caller
->dump_name (),
5348 val
->spec_node
->dump_name ());
5350 cs
->redirect_callee_duplicating_thunks (val
->spec_node
);
5351 val
->spec_node
->expand_all_artificial_thunks ();
5352 if (cs
->count
.ipa ().initialized_p ())
5353 redirected_sum
= redirected_sum
+ cs
->count
.ipa ();
5355 cs
= get_next_cgraph_edge_clone (cs
);
5359 if (redirected_sum
.nonzero_p ())
5360 update_specialized_profile (val
->spec_node
, node
, redirected_sum
);
5363 /* Return true if KNOWN_CONTEXTS contain at least one useful context. */
5366 known_contexts_useful_p (vec
<ipa_polymorphic_call_context
> known_contexts
)
5368 ipa_polymorphic_call_context
*ctx
;
5371 FOR_EACH_VEC_ELT (known_contexts
, i
, ctx
)
5372 if (!ctx
->useless_p ())
5377 /* Return a copy of KNOWN_CSTS if it is not empty, otherwise return vNULL. */
5379 static vec
<ipa_polymorphic_call_context
>
5380 copy_useful_known_contexts (vec
<ipa_polymorphic_call_context
> known_contexts
)
5382 if (known_contexts_useful_p (known_contexts
))
5383 return known_contexts
.copy ();
5388 /* Copy known scalar values from AVALS into KNOWN_CSTS and modify the copy
5389 according to VAL and INDEX. If non-empty, replace KNOWN_CONTEXTS with its
5393 copy_known_vectors_add_val (ipa_auto_call_arg_values
*avals
,
5394 vec
<tree
> *known_csts
,
5395 vec
<ipa_polymorphic_call_context
> *known_contexts
,
5396 ipcp_value
<tree
> *val
, int index
)
5398 *known_csts
= avals
->m_known_vals
.copy ();
5399 *known_contexts
= copy_useful_known_contexts (avals
->m_known_contexts
);
5400 (*known_csts
)[index
] = val
->value
;
5403 /* Copy known scalar values from AVALS into KNOWN_CSTS. Similarly, copy
5404 contexts to KNOWN_CONTEXTS and modify the copy according to VAL and
5408 copy_known_vectors_add_val (ipa_auto_call_arg_values
*avals
,
5409 vec
<tree
> *known_csts
,
5410 vec
<ipa_polymorphic_call_context
> *known_contexts
,
5411 ipcp_value
<ipa_polymorphic_call_context
> *val
,
5414 *known_csts
= avals
->m_known_vals
.copy ();
5415 *known_contexts
= avals
->m_known_contexts
.copy ();
5416 (*known_contexts
)[index
] = val
->value
;
5419 /* Return true if OFFSET indicates this was not an aggregate value or there is
5420 a replacement equivalent to VALUE, INDEX and OFFSET among those in the
5424 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*aggvals
,
5425 int index
, HOST_WIDE_INT offset
, tree value
)
5432 if (aggvals
->index
== index
5433 && aggvals
->offset
== offset
5434 && values_equal_for_ipcp_p (aggvals
->value
, value
))
5436 aggvals
= aggvals
->next
;
5441 /* Return true if offset is minus one because source of a polymorphic context
5442 cannot be an aggregate value. */
5445 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*,
5446 int , HOST_WIDE_INT offset
,
5447 ipa_polymorphic_call_context
)
5449 return offset
== -1;
5452 /* Decide whether to create a special version of NODE for value VAL of
5453 parameter at the given INDEX. If OFFSET is -1, the value is for the
5454 parameter itself, otherwise it is stored at the given OFFSET of the
5455 parameter. AVALS describes the other already known values. */
5457 template <typename valtype
>
5459 decide_about_value (struct cgraph_node
*node
, int index
, HOST_WIDE_INT offset
,
5460 ipcp_value
<valtype
> *val
, ipa_auto_call_arg_values
*avals
)
5462 struct ipa_agg_replacement_value
*aggvals
;
5465 profile_count count_sum
;
5466 vec
<cgraph_edge
*> callers
;
5470 perhaps_add_new_callers (node
, val
);
5473 else if (val
->local_size_cost
+ overall_size
> get_max_overall_size (node
))
5475 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5476 fprintf (dump_file
, " Ignoring candidate value because "
5477 "maximum unit size would be reached with %li.\n",
5478 val
->local_size_cost
+ overall_size
);
5481 else if (!get_info_about_necessary_edges (val
, node
, &freq_sum
, &count_sum
,
5485 if (!dbg_cnt (ipa_cp_values
))
5488 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5490 fprintf (dump_file
, " - considering value ");
5491 print_ipcp_constant_value (dump_file
, val
->value
);
5492 fprintf (dump_file
, " for ");
5493 ipa_dump_param (dump_file
, IPA_NODE_REF (node
), index
);
5495 fprintf (dump_file
, ", offset: " HOST_WIDE_INT_PRINT_DEC
, offset
);
5496 fprintf (dump_file
, " (caller_count: %i)\n", caller_count
);
5499 if (!good_cloning_opportunity_p (node
, val
->local_time_benefit
,
5500 freq_sum
, count_sum
,
5501 val
->local_size_cost
)
5502 && !good_cloning_opportunity_p (node
,
5503 val
->local_time_benefit
5504 + val
->prop_time_benefit
,
5505 freq_sum
, count_sum
,
5506 safe_add (val
->local_size_cost
,
5507 val
->prop_size_cost
)))
5511 fprintf (dump_file
, " Creating a specialized node of %s.\n",
5512 node
->dump_name ());
5514 vec
<tree
> known_csts
;
5515 vec
<ipa_polymorphic_call_context
> known_contexts
;
5517 callers
= gather_edges_for_value (val
, node
, caller_count
);
5519 copy_known_vectors_add_val (avals
, &known_csts
, &known_contexts
, val
, index
);
5522 known_csts
= avals
->m_known_vals
.copy ();
5523 known_contexts
= copy_useful_known_contexts (avals
->m_known_contexts
);
5525 find_more_scalar_values_for_callers_subset (node
, known_csts
, callers
);
5526 find_more_contexts_for_caller_subset (node
, &known_contexts
, callers
);
5527 aggvals
= find_aggregate_values_for_callers_subset (node
, callers
);
5528 gcc_checking_assert (ipcp_val_agg_replacement_ok_p (aggvals
, index
,
5529 offset
, val
->value
));
5530 val
->spec_node
= create_specialized_node (node
, known_csts
, known_contexts
,
5532 overall_size
+= val
->local_size_cost
;
5533 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5534 fprintf (dump_file
, " overall size reached %li\n",
5537 /* TODO: If for some lattice there is only one other known value
5538 left, make a special node for it too. */
5543 /* Decide whether and what specialized clones of NODE should be created. */
5546 decide_whether_version_node (struct cgraph_node
*node
)
5548 class ipa_node_params
*info
= IPA_NODE_REF (node
);
5549 int i
, count
= ipa_get_param_count (info
);
5555 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5556 fprintf (dump_file
, "\nEvaluating opportunities for %s.\n",
5557 node
->dump_name ());
5559 ipa_auto_call_arg_values avals
;
5560 gather_context_independent_values (info
, &avals
, false, NULL
);
5562 for (i
= 0; i
< count
;i
++)
5564 class ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5565 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
5566 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
5569 && !avals
.m_known_vals
[i
])
5571 ipcp_value
<tree
> *val
;
5572 for (val
= lat
->values
; val
; val
= val
->next
)
5573 ret
|= decide_about_value (node
, i
, -1, val
, &avals
);
5576 if (!plats
->aggs_bottom
)
5578 struct ipcp_agg_lattice
*aglat
;
5579 ipcp_value
<tree
> *val
;
5580 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
5581 if (!aglat
->bottom
&& aglat
->values
5582 /* If the following is false, the one value has been considered
5583 for cloning for all contexts. */
5584 && (plats
->aggs_contain_variable
5585 || !aglat
->is_single_const ()))
5586 for (val
= aglat
->values
; val
; val
= val
->next
)
5587 ret
|= decide_about_value (node
, i
, aglat
->offset
, val
, &avals
);
5591 && avals
.m_known_contexts
[i
].useless_p ())
5593 ipcp_value
<ipa_polymorphic_call_context
> *val
;
5594 for (val
= ctxlat
->values
; val
; val
= val
->next
)
5595 ret
|= decide_about_value (node
, i
, -1, val
, &avals
);
5598 info
= IPA_NODE_REF (node
);
5601 if (info
->do_clone_for_all_contexts
)
5603 if (!dbg_cnt (ipa_cp_values
))
5605 info
->do_clone_for_all_contexts
= false;
5609 struct cgraph_node
*clone
;
5610 vec
<cgraph_edge
*> callers
= node
->collect_callers ();
5612 for (int i
= callers
.length () - 1; i
>= 0; i
--)
5614 cgraph_edge
*cs
= callers
[i
];
5615 class ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
5617 if (caller_info
&& caller_info
->node_dead
)
5618 callers
.unordered_remove (i
);
5621 if (!adjust_callers_for_value_intersection (callers
, node
))
5623 /* If node is not called by anyone, or all its caller edges are
5624 self-recursive, the node is not really in use, no need to do
5627 info
->do_clone_for_all_contexts
= false;
5632 fprintf (dump_file
, " - Creating a specialized node of %s "
5633 "for all known contexts.\n", node
->dump_name ());
5635 vec
<tree
> known_csts
= avals
.m_known_vals
.copy ();
5636 vec
<ipa_polymorphic_call_context
> known_contexts
5637 = copy_useful_known_contexts (avals
.m_known_contexts
);
5638 find_more_scalar_values_for_callers_subset (node
, known_csts
, callers
);
5639 find_more_contexts_for_caller_subset (node
, &known_contexts
, callers
);
5640 ipa_agg_replacement_value
*aggvals
5641 = find_aggregate_values_for_callers_subset (node
, callers
);
5643 if (!known_contexts_useful_p (known_contexts
))
5645 known_contexts
.release ();
5646 known_contexts
= vNULL
;
5648 clone
= create_specialized_node (node
, known_csts
, known_contexts
,
5650 info
= IPA_NODE_REF (node
);
5651 info
->do_clone_for_all_contexts
= false;
5652 IPA_NODE_REF (clone
)->is_all_contexts_clone
= true;
5659 /* Transitively mark all callees of NODE within the same SCC as not dead. */
5662 spread_undeadness (struct cgraph_node
*node
)
5664 struct cgraph_edge
*cs
;
5666 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
5667 if (ipa_edge_within_scc (cs
))
5669 struct cgraph_node
*callee
;
5670 class ipa_node_params
*info
;
5672 callee
= cs
->callee
->function_symbol (NULL
);
5673 info
= IPA_NODE_REF (callee
);
5675 if (info
&& info
->node_dead
)
5677 info
->node_dead
= 0;
5678 spread_undeadness (callee
);
5683 /* Return true if NODE has a caller from outside of its SCC that is not
5684 dead. Worker callback for cgraph_for_node_and_aliases. */
5687 has_undead_caller_from_outside_scc_p (struct cgraph_node
*node
,
5688 void *data ATTRIBUTE_UNUSED
)
5690 struct cgraph_edge
*cs
;
5692 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
5693 if (cs
->caller
->thunk
5694 && cs
->caller
->call_for_symbol_thunks_and_aliases
5695 (has_undead_caller_from_outside_scc_p
, NULL
, true))
5697 else if (!ipa_edge_within_scc (cs
)
5698 && (!IPA_NODE_REF (cs
->caller
) /* Unoptimized caller. */
5699 || !IPA_NODE_REF (cs
->caller
)->node_dead
))
5705 /* Identify nodes within the same SCC as NODE which are no longer needed
5706 because of new clones and will be removed as unreachable. */
5709 identify_dead_nodes (struct cgraph_node
*node
)
5711 struct cgraph_node
*v
;
5712 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
5715 && !v
->call_for_symbol_thunks_and_aliases
5716 (has_undead_caller_from_outside_scc_p
, NULL
, true))
5717 IPA_NODE_REF (v
)->node_dead
= 1;
5719 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
5720 if (IPA_NODE_REF (v
) && !IPA_NODE_REF (v
)->node_dead
)
5721 spread_undeadness (v
);
5723 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5725 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
5726 if (IPA_NODE_REF (v
) && IPA_NODE_REF (v
)->node_dead
)
5727 fprintf (dump_file
, " Marking node as dead: %s.\n", v
->dump_name ());
5731 /* The decision stage. Iterate over the topological order of call graph nodes
5732 TOPO and make specialized clones if deemed beneficial. */
5735 ipcp_decision_stage (class ipa_topo_info
*topo
)
5740 fprintf (dump_file
, "\nIPA decision stage:\n\n");
5742 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
5744 struct cgraph_node
*node
= topo
->order
[i
];
5745 bool change
= false, iterate
= true;
5749 struct cgraph_node
*v
;
5751 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
5752 if (v
->has_gimple_body_p ()
5753 && ipcp_versionable_function_p (v
))
5754 iterate
|= decide_whether_version_node (v
);
5759 identify_dead_nodes (node
);
5763 /* Look up all the bits information that we have discovered and copy it over
5764 to the transformation summary. */
5767 ipcp_store_bits_results (void)
5771 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5773 ipa_node_params
*info
= IPA_NODE_REF (node
);
5774 bool dumped_sth
= false;
5775 bool found_useful_result
= false;
5777 if (!opt_for_fn (node
->decl
, flag_ipa_bit_cp
) || !info
)
5780 fprintf (dump_file
, "Not considering %s for ipa bitwise propagation "
5781 "; -fipa-bit-cp: disabled.\n",
5782 node
->dump_name ());
5786 if (info
->ipcp_orig_node
)
5787 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
5788 if (!info
->lattices
)
5789 /* Newly expanded artificial thunks do not have lattices. */
5792 unsigned count
= ipa_get_param_count (info
);
5793 for (unsigned i
= 0; i
< count
; i
++)
5795 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5796 if (plats
->bits_lattice
.constant_p ())
5798 found_useful_result
= true;
5803 if (!found_useful_result
)
5806 ipcp_transformation_initialize ();
5807 ipcp_transformation
*ts
= ipcp_transformation_sum
->get_create (node
);
5808 vec_safe_reserve_exact (ts
->bits
, count
);
5810 for (unsigned i
= 0; i
< count
; i
++)
5812 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5815 if (plats
->bits_lattice
.constant_p ())
5818 = ipa_get_ipa_bits_for_value (plats
->bits_lattice
.get_value (),
5819 plats
->bits_lattice
.get_mask ());
5820 if (!dbg_cnt (ipa_cp_bits
))
5826 ts
->bits
->quick_push (jfbits
);
5827 if (!dump_file
|| !jfbits
)
5831 fprintf (dump_file
, "Propagated bits info for function %s:\n",
5832 node
->dump_name ());
5835 fprintf (dump_file
, " param %i: value = ", i
);
5836 print_hex (jfbits
->value
, dump_file
);
5837 fprintf (dump_file
, ", mask = ");
5838 print_hex (jfbits
->mask
, dump_file
);
5839 fprintf (dump_file
, "\n");
5844 /* Look up all VR information that we have discovered and copy it over
5845 to the transformation summary. */
5848 ipcp_store_vr_results (void)
5852 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5854 ipa_node_params
*info
= IPA_NODE_REF (node
);
5855 bool found_useful_result
= false;
5857 if (!info
|| !opt_for_fn (node
->decl
, flag_ipa_vrp
))
5860 fprintf (dump_file
, "Not considering %s for VR discovery "
5861 "and propagate; -fipa-ipa-vrp: disabled.\n",
5862 node
->dump_name ());
5866 if (info
->ipcp_orig_node
)
5867 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
5868 if (!info
->lattices
)
5869 /* Newly expanded artificial thunks do not have lattices. */
5872 unsigned count
= ipa_get_param_count (info
);
5873 for (unsigned i
= 0; i
< count
; i
++)
5875 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5876 if (!plats
->m_value_range
.bottom_p ()
5877 && !plats
->m_value_range
.top_p ())
5879 found_useful_result
= true;
5883 if (!found_useful_result
)
5886 ipcp_transformation_initialize ();
5887 ipcp_transformation
*ts
= ipcp_transformation_sum
->get_create (node
);
5888 vec_safe_reserve_exact (ts
->m_vr
, count
);
5890 for (unsigned i
= 0; i
< count
; i
++)
5892 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
5895 if (!plats
->m_value_range
.bottom_p ()
5896 && !plats
->m_value_range
.top_p ()
5897 && dbg_cnt (ipa_cp_vr
))
5900 vr
.type
= plats
->m_value_range
.m_vr
.kind ();
5901 vr
.min
= wi::to_wide (plats
->m_value_range
.m_vr
.min ());
5902 vr
.max
= wi::to_wide (plats
->m_value_range
.m_vr
.max ());
5907 vr
.type
= VR_VARYING
;
5908 vr
.min
= vr
.max
= wi::zero (INT_TYPE_SIZE
);
5910 ts
->m_vr
->quick_push (vr
);
5915 /* The IPCP driver. */
5920 class ipa_topo_info topo
;
5922 if (edge_clone_summaries
== NULL
)
5923 edge_clone_summaries
= new edge_clone_summary_t (symtab
);
5925 ipa_check_create_node_params ();
5926 ipa_check_create_edge_args ();
5927 clone_num_suffixes
= new hash_map
<const char *, unsigned>;
5931 fprintf (dump_file
, "\nIPA structures before propagation:\n");
5932 if (dump_flags
& TDF_DETAILS
)
5933 ipa_print_all_params (dump_file
);
5934 ipa_print_all_jump_functions (dump_file
);
5937 /* Topological sort. */
5938 build_toporder_info (&topo
);
5939 /* Do the interprocedural propagation. */
5940 ipcp_propagate_stage (&topo
);
5941 /* Decide what constant propagation and cloning should be performed. */
5942 ipcp_decision_stage (&topo
);
5943 /* Store results of bits propagation. */
5944 ipcp_store_bits_results ();
5945 /* Store results of value range propagation. */
5946 ipcp_store_vr_results ();
5948 /* Free all IPCP structures. */
5949 delete clone_num_suffixes
;
5950 free_toporder_info (&topo
);
5951 delete edge_clone_summaries
;
5952 edge_clone_summaries
= NULL
;
5953 ipa_free_all_structures_after_ipa_cp ();
5955 fprintf (dump_file
, "\nIPA constant propagation end\n");
5959 /* Initialization and computation of IPCP data structures. This is the initial
5960 intraprocedural analysis of functions, which gathers information to be
5961 propagated later on. */
5964 ipcp_generate_summary (void)
5966 struct cgraph_node
*node
;
5969 fprintf (dump_file
, "\nIPA constant propagation start:\n");
5970 ipa_register_cgraph_hooks ();
5972 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5973 ipa_analyze_node (node
);
5978 const pass_data pass_data_ipa_cp
=
5980 IPA_PASS
, /* type */
5982 OPTGROUP_NONE
, /* optinfo_flags */
5983 TV_IPA_CONSTANT_PROP
, /* tv_id */
5984 0, /* properties_required */
5985 0, /* properties_provided */
5986 0, /* properties_destroyed */
5987 0, /* todo_flags_start */
5988 ( TODO_dump_symtab
| TODO_remove_functions
), /* todo_flags_finish */
5991 class pass_ipa_cp
: public ipa_opt_pass_d
5994 pass_ipa_cp (gcc::context
*ctxt
)
5995 : ipa_opt_pass_d (pass_data_ipa_cp
, ctxt
,
5996 ipcp_generate_summary
, /* generate_summary */
5997 NULL
, /* write_summary */
5998 NULL
, /* read_summary */
5999 ipcp_write_transformation_summaries
, /*
6000 write_optimization_summary */
6001 ipcp_read_transformation_summaries
, /*
6002 read_optimization_summary */
6003 NULL
, /* stmt_fixup */
6004 0, /* function_transform_todo_flags_start */
6005 ipcp_transform_function
, /* function_transform */
6006 NULL
) /* variable_transform */
6009 /* opt_pass methods: */
6010 virtual bool gate (function
*)
6012 /* FIXME: We should remove the optimize check after we ensure we never run
6013 IPA passes when not optimizing. */
6014 return (flag_ipa_cp
&& optimize
) || in_lto_p
;
6017 virtual unsigned int execute (function
*) { return ipcp_driver (); }
6019 }; // class pass_ipa_cp
6024 make_pass_ipa_cp (gcc::context
*ctxt
)
6026 return new pass_ipa_cp (ctxt
);
6029 /* Reset all state within ipa-cp.c so that we can rerun the compiler
6030 within the same process. For use by toplev::finalize. */
6033 ipa_cp_c_finalize (void)
6035 max_count
= profile_count::uninitialized ();
6037 orig_overall_size
= 0;
6038 ipcp_free_transformation_sum ();