1 /* Interprocedural constant propagation
2 Copyright (C) 2005-2017 Free Software Foundation, Inc.
4 Contributed by Razya Ladelsky <RAZYA@il.ibm.com> and Martin Jambor
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
23 /* Interprocedural constant propagation (IPA-CP).
25 The goal of this transformation is to
27 1) discover functions which are always invoked with some arguments with the
28 same known constant values and modify the functions so that the
29 subsequent optimizations can take advantage of the knowledge, and
31 2) partial specialization - create specialized versions of functions
32 transformed in this way if some parameters are known constants only in
33 certain contexts but the estimated tradeoff between speedup and cost size
36 The algorithm also propagates types and attempts to perform type based
37 devirtualization. Types are propagated much like constants.
39 The algorithm basically consists of three stages. In the first, functions
40 are analyzed one at a time and jump functions are constructed for all known
41 call-sites. In the second phase, the pass propagates information from the
42 jump functions across the call to reveal what values are available at what
43 call sites, performs estimations of effects of known values on functions and
44 their callees, and finally decides what specialized extra versions should be
45 created. In the third, the special versions materialize and appropriate
48 The algorithm used is to a certain extent based on "Interprocedural Constant
49 Propagation", by David Callahan, Keith D Cooper, Ken Kennedy, Linda Torczon,
50 Comp86, pg 152-161 and "A Methodology for Procedure Cloning" by Keith D
51 Cooper, Mary W. Hall, and Ken Kennedy.
54 First stage - intraprocedural analysis
55 =======================================
57 This phase computes jump_function and modification flags.
59 A jump function for a call-site represents the values passed as an actual
60 arguments of a given call-site. In principle, there are three types of
63 Pass through - the caller's formal parameter is passed as an actual
64 argument, plus an operation on it can be performed.
65 Constant - a constant is passed as an actual argument.
66 Unknown - neither of the above.
68 All jump function types are described in detail in ipa-prop.h, together with
69 the data structures that represent them and methods of accessing them.
71 ipcp_generate_summary() is the main function of the first stage.
73 Second stage - interprocedural analysis
74 ========================================
76 This stage is itself divided into two phases. In the first, we propagate
77 known values over the call graph, in the second, we make cloning decisions.
78 It uses a different algorithm than the original Callahan's paper.
80 First, we traverse the functions topologically from callers to callees and,
81 for each strongly connected component (SCC), we propagate constants
82 according to previously computed jump functions. We also record what known
83 values depend on other known values and estimate local effects. Finally, we
84 propagate cumulative information about these effects from dependent values
85 to those on which they depend.
87 Second, we again traverse the call graph in the same topological order and
88 make clones for functions which we know are called with the same values in
89 all contexts and decide about extra specialized clones of functions just for
90 some contexts - these decisions are based on both local estimates and
91 cumulative estimates propagated from callees.
93 ipcp_propagate_stage() and ipcp_decision_stage() together constitute the
96 Third phase - materialization of clones, call statement updates.
97 ============================================
99 This stage is currently performed by call graph code (mainly in cgraphunit.c
100 and tree-inline.c) according to instructions inserted to the call graph by
105 #include "coretypes.h"
108 #include "gimple-expr.h"
110 #include "alloc-pool.h"
111 #include "tree-pass.h"
113 #include "diagnostic.h"
114 #include "fold-const.h"
115 #include "gimple-fold.h"
116 #include "symbol-summary.h"
117 #include "tree-vrp.h"
118 #include "ipa-prop.h"
119 #include "tree-pretty-print.h"
120 #include "tree-inline.h"
122 #include "ipa-fnsummary.h"
123 #include "ipa-utils.h"
124 #include "tree-ssa-ccp.h"
126 template <typename valtype
> class ipcp_value
;
128 /* Describes a particular source for an IPA-CP value. */
130 template <typename valtype
>
131 class ipcp_value_source
134 /* Aggregate offset of the source, negative if the source is scalar value of
135 the argument itself. */
136 HOST_WIDE_INT offset
;
137 /* The incoming edge that brought the value. */
139 /* If the jump function that resulted into his value was a pass-through or an
140 ancestor, this is the ipcp_value of the caller from which the described
141 value has been derived. Otherwise it is NULL. */
142 ipcp_value
<valtype
> *val
;
143 /* Next pointer in a linked list of sources of a value. */
144 ipcp_value_source
*next
;
145 /* If the jump function that resulted into his value was a pass-through or an
146 ancestor, this is the index of the parameter of the caller the jump
147 function references. */
151 /* Common ancestor for all ipcp_value instantiations. */
153 class ipcp_value_base
156 /* Time benefit and size cost that specializing the function for this value
157 would bring about in this function alone. */
158 int local_time_benefit
, local_size_cost
;
159 /* Time benefit and size cost that specializing the function for this value
160 can bring about in it's callees (transitively). */
161 int prop_time_benefit
, prop_size_cost
;
164 /* Describes one particular value stored in struct ipcp_lattice. */
166 template <typename valtype
>
167 class ipcp_value
: public ipcp_value_base
170 /* The actual value for the given parameter. */
172 /* The list of sources from which this value originates. */
173 ipcp_value_source
<valtype
> *sources
;
174 /* Next pointers in a linked list of all values in a lattice. */
176 /* Next pointers in a linked list of values in a strongly connected component
178 ipcp_value
*scc_next
;
179 /* Next pointers in a linked list of SCCs of values sorted topologically
180 according their sources. */
181 ipcp_value
*topo_next
;
182 /* A specialized node created for this value, NULL if none has been (so far)
184 cgraph_node
*spec_node
;
185 /* Depth first search number and low link for topological sorting of
188 /* True if this valye is currently on the topo-sort stack. */
191 void add_source (cgraph_edge
*cs
, ipcp_value
*src_val
, int src_idx
,
192 HOST_WIDE_INT offset
);
195 /* Lattice describing potential values of a formal parameter of a function, or
196 a part of an aggregate. TOP is represented by a lattice with zero values
197 and with contains_variable and bottom flags cleared. BOTTOM is represented
198 by a lattice with the bottom flag set. In that case, values and
199 contains_variable flag should be disregarded. */
201 template <typename valtype
>
205 /* The list of known values and types in this lattice. Note that values are
206 not deallocated if a lattice is set to bottom because there may be value
207 sources referencing them. */
208 ipcp_value
<valtype
> *values
;
209 /* Number of known values and types in this lattice. */
211 /* The lattice contains a variable component (in addition to values). */
212 bool contains_variable
;
213 /* The value of the lattice is bottom (i.e. variable and unusable for any
217 inline bool is_single_const ();
218 inline bool set_to_bottom ();
219 inline bool set_contains_variable ();
220 bool add_value (valtype newval
, cgraph_edge
*cs
,
221 ipcp_value
<valtype
> *src_val
= NULL
,
222 int src_idx
= 0, HOST_WIDE_INT offset
= -1);
223 void print (FILE * f
, bool dump_sources
, bool dump_benefits
);
226 /* Lattice of tree values with an offset to describe a part of an
229 class ipcp_agg_lattice
: public ipcp_lattice
<tree
>
232 /* Offset that is being described by this lattice. */
233 HOST_WIDE_INT offset
;
234 /* Size so that we don't have to re-compute it every time we traverse the
235 list. Must correspond to TYPE_SIZE of all lat values. */
237 /* Next element of the linked list. */
238 struct ipcp_agg_lattice
*next
;
241 /* Lattice of known bits, only capable of holding one value.
242 Bitwise constant propagation propagates which bits of a
258 In the above case, the param 'x' will always have all
259 the bits (except the bits in lsb) set to 0.
260 Hence the mask of 'x' would be 0xff. The mask
261 reflects that the bits in lsb are unknown.
262 The actual propagated value is given by m_value & ~m_mask. */
264 class ipcp_bits_lattice
267 bool bottom_p () { return m_lattice_val
== IPA_BITS_VARYING
; }
268 bool top_p () { return m_lattice_val
== IPA_BITS_UNDEFINED
; }
269 bool constant_p () { return m_lattice_val
== IPA_BITS_CONSTANT
; }
270 bool set_to_bottom ();
271 bool set_to_constant (widest_int
, widest_int
);
273 widest_int
get_value () { return m_value
; }
274 widest_int
get_mask () { return m_mask
; }
276 bool meet_with (ipcp_bits_lattice
& other
, unsigned, signop
,
277 enum tree_code
, tree
);
279 bool meet_with (widest_int
, widest_int
, unsigned);
284 enum { IPA_BITS_UNDEFINED
, IPA_BITS_CONSTANT
, IPA_BITS_VARYING
} m_lattice_val
;
286 /* Similar to ccp_lattice_t, mask represents which bits of value are constant.
287 If a bit in mask is set to 0, then the corresponding bit in
288 value is known to be constant. */
289 widest_int m_value
, m_mask
;
291 bool meet_with_1 (widest_int
, widest_int
, unsigned);
292 void get_value_and_mask (tree
, widest_int
*, widest_int
*);
295 /* Lattice of value ranges. */
297 class ipcp_vr_lattice
302 inline bool bottom_p () const;
303 inline bool top_p () const;
304 inline bool set_to_bottom ();
305 bool meet_with (const value_range
*p_vr
);
306 bool meet_with (const ipcp_vr_lattice
&other
);
307 void init () { m_vr
.type
= VR_UNDEFINED
; }
308 void print (FILE * f
);
311 bool meet_with_1 (const value_range
*other_vr
);
314 /* Structure containing lattices for a parameter itself and for pieces of
315 aggregates that are passed in the parameter or by a reference in a parameter
316 plus some other useful flags. */
318 class ipcp_param_lattices
321 /* Lattice describing the value of the parameter itself. */
322 ipcp_lattice
<tree
> itself
;
323 /* Lattice describing the polymorphic contexts of a parameter. */
324 ipcp_lattice
<ipa_polymorphic_call_context
> ctxlat
;
325 /* Lattices describing aggregate parts. */
326 ipcp_agg_lattice
*aggs
;
327 /* Lattice describing known bits. */
328 ipcp_bits_lattice bits_lattice
;
329 /* Lattice describing value range. */
330 ipcp_vr_lattice m_value_range
;
331 /* Number of aggregate lattices */
333 /* True if aggregate data were passed by reference (as opposed to by
336 /* All aggregate lattices contain a variable component (in addition to
338 bool aggs_contain_variable
;
339 /* The value of all aggregate lattices is bottom (i.e. variable and unusable
340 for any propagation). */
343 /* There is a virtual call based on this parameter. */
347 /* Allocation pools for values and their sources in ipa-cp. */
349 object_allocator
<ipcp_value
<tree
> > ipcp_cst_values_pool
350 ("IPA-CP constant values");
352 object_allocator
<ipcp_value
<ipa_polymorphic_call_context
> >
353 ipcp_poly_ctx_values_pool ("IPA-CP polymorphic contexts");
355 object_allocator
<ipcp_value_source
<tree
> > ipcp_sources_pool
356 ("IPA-CP value sources");
358 object_allocator
<ipcp_agg_lattice
> ipcp_agg_lattice_pool
359 ("IPA_CP aggregate lattices");
361 /* Maximal count found in program. */
363 static profile_count max_count
;
365 /* Original overall size of the program. */
367 static long overall_size
, max_new_size
;
369 /* Return the param lattices structure corresponding to the Ith formal
370 parameter of the function described by INFO. */
371 static inline struct ipcp_param_lattices
*
372 ipa_get_parm_lattices (struct ipa_node_params
*info
, int i
)
374 gcc_assert (i
>= 0 && i
< ipa_get_param_count (info
));
375 gcc_checking_assert (!info
->ipcp_orig_node
);
376 gcc_checking_assert (info
->lattices
);
377 return &(info
->lattices
[i
]);
380 /* Return the lattice corresponding to the scalar value of the Ith formal
381 parameter of the function described by INFO. */
382 static inline ipcp_lattice
<tree
> *
383 ipa_get_scalar_lat (struct ipa_node_params
*info
, int i
)
385 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
386 return &plats
->itself
;
389 /* Return the lattice corresponding to the scalar value of the Ith formal
390 parameter of the function described by INFO. */
391 static inline ipcp_lattice
<ipa_polymorphic_call_context
> *
392 ipa_get_poly_ctx_lat (struct ipa_node_params
*info
, int i
)
394 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
395 return &plats
->ctxlat
;
398 /* Return the lattice corresponding to the value range of the Ith formal
399 parameter of the function described by INFO. */
401 static inline ipcp_vr_lattice
*
402 ipa_get_vr_lat (struct ipa_node_params
*info
, int i
)
404 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
405 return &plats
->m_value_range
;
408 /* Return whether LAT is a lattice with a single constant and without an
411 template <typename valtype
>
413 ipcp_lattice
<valtype
>::is_single_const ()
415 if (bottom
|| contains_variable
|| values_count
!= 1)
421 /* Print V which is extracted from a value in a lattice to F. */
424 print_ipcp_constant_value (FILE * f
, tree v
)
426 if (TREE_CODE (v
) == ADDR_EXPR
427 && TREE_CODE (TREE_OPERAND (v
, 0)) == CONST_DECL
)
430 print_generic_expr (f
, DECL_INITIAL (TREE_OPERAND (v
, 0)));
433 print_generic_expr (f
, v
);
436 /* Print V which is extracted from a value in a lattice to F. */
439 print_ipcp_constant_value (FILE * f
, ipa_polymorphic_call_context v
)
444 /* Print a lattice LAT to F. */
446 template <typename valtype
>
448 ipcp_lattice
<valtype
>::print (FILE * f
, bool dump_sources
, bool dump_benefits
)
450 ipcp_value
<valtype
> *val
;
455 fprintf (f
, "BOTTOM\n");
459 if (!values_count
&& !contains_variable
)
461 fprintf (f
, "TOP\n");
465 if (contains_variable
)
467 fprintf (f
, "VARIABLE");
473 for (val
= values
; val
; val
= val
->next
)
475 if (dump_benefits
&& prev
)
477 else if (!dump_benefits
&& prev
)
482 print_ipcp_constant_value (f
, val
->value
);
486 ipcp_value_source
<valtype
> *s
;
488 fprintf (f
, " [from:");
489 for (s
= val
->sources
; s
; s
= s
->next
)
490 fprintf (f
, " %i(%i)", s
->cs
->caller
->order
,
496 fprintf (f
, " [loc_time: %i, loc_size: %i, "
497 "prop_time: %i, prop_size: %i]\n",
498 val
->local_time_benefit
, val
->local_size_cost
,
499 val
->prop_time_benefit
, val
->prop_size_cost
);
506 ipcp_bits_lattice::print (FILE *f
)
509 fprintf (f
, " Bits unknown (TOP)\n");
510 else if (bottom_p ())
511 fprintf (f
, " Bits unusable (BOTTOM)\n");
514 fprintf (f
, " Bits: value = "); print_hex (get_value (), f
);
515 fprintf (f
, ", mask = "); print_hex (get_mask (), f
);
520 /* Print value range lattice to F. */
523 ipcp_vr_lattice::print (FILE * f
)
525 dump_value_range (f
, &m_vr
);
528 /* Print all ipcp_lattices of all functions to F. */
531 print_all_lattices (FILE * f
, bool dump_sources
, bool dump_benefits
)
533 struct cgraph_node
*node
;
536 fprintf (f
, "\nLattices:\n");
537 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
539 struct ipa_node_params
*info
;
541 info
= IPA_NODE_REF (node
);
542 fprintf (f
, " Node: %s:\n", node
->dump_name ());
543 count
= ipa_get_param_count (info
);
544 for (i
= 0; i
< count
; i
++)
546 struct ipcp_agg_lattice
*aglat
;
547 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
548 fprintf (f
, " param [%d]: ", i
);
549 plats
->itself
.print (f
, dump_sources
, dump_benefits
);
550 fprintf (f
, " ctxs: ");
551 plats
->ctxlat
.print (f
, dump_sources
, dump_benefits
);
552 plats
->bits_lattice
.print (f
);
554 plats
->m_value_range
.print (f
);
556 if (plats
->virt_call
)
557 fprintf (f
, " virt_call flag set\n");
559 if (plats
->aggs_bottom
)
561 fprintf (f
, " AGGS BOTTOM\n");
564 if (plats
->aggs_contain_variable
)
565 fprintf (f
, " AGGS VARIABLE\n");
566 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
568 fprintf (f
, " %soffset " HOST_WIDE_INT_PRINT_DEC
": ",
569 plats
->aggs_by_ref
? "ref " : "", aglat
->offset
);
570 aglat
->print (f
, dump_sources
, dump_benefits
);
576 /* Determine whether it is at all technically possible to create clones of NODE
577 and store this information in the ipa_node_params structure associated
581 determine_versionability (struct cgraph_node
*node
,
582 struct ipa_node_params
*info
)
584 const char *reason
= NULL
;
586 /* There are a number of generic reasons functions cannot be versioned. We
587 also cannot remove parameters if there are type attributes such as fnspec
589 if (node
->alias
|| node
->thunk
.thunk_p
)
590 reason
= "alias or thunk";
591 else if (!node
->local
.versionable
)
592 reason
= "not a tree_versionable_function";
593 else if (node
->get_availability () <= AVAIL_INTERPOSABLE
)
594 reason
= "insufficient body availability";
595 else if (!opt_for_fn (node
->decl
, optimize
)
596 || !opt_for_fn (node
->decl
, flag_ipa_cp
))
597 reason
= "non-optimized function";
598 else if (lookup_attribute ("omp declare simd", DECL_ATTRIBUTES (node
->decl
)))
600 /* Ideally we should clone the SIMD clones themselves and create
601 vector copies of them, so IPA-cp and SIMD clones can happily
602 coexist, but that may not be worth the effort. */
603 reason
= "function has SIMD clones";
605 else if (lookup_attribute ("target_clones", DECL_ATTRIBUTES (node
->decl
)))
607 /* Ideally we should clone the target clones themselves and create
608 copies of them, so IPA-cp and target clones can happily
609 coexist, but that may not be worth the effort. */
610 reason
= "function target_clones attribute";
612 /* Don't clone decls local to a comdat group; it breaks and for C++
613 decloned constructors, inlining is always better anyway. */
614 else if (node
->comdat_local_p ())
615 reason
= "comdat-local function";
616 else if (node
->calls_comdat_local
)
618 /* TODO: call is versionable if we make sure that all
619 callers are inside of a comdat group. */
620 reason
= "calls comdat-local function";
623 if (reason
&& dump_file
&& !node
->alias
&& !node
->thunk
.thunk_p
)
624 fprintf (dump_file
, "Function %s is not versionable, reason: %s.\n",
625 node
->dump_name (), reason
);
627 info
->versionable
= (reason
== NULL
);
630 /* Return true if it is at all technically possible to create clones of a
634 ipcp_versionable_function_p (struct cgraph_node
*node
)
636 return IPA_NODE_REF (node
)->versionable
;
639 /* Structure holding accumulated information about callers of a node. */
641 struct caller_statistics
643 profile_count count_sum
;
644 int n_calls
, n_hot_calls
, freq_sum
;
647 /* Initialize fields of STAT to zeroes. */
650 init_caller_stats (struct caller_statistics
*stats
)
652 stats
->count_sum
= profile_count::zero ();
654 stats
->n_hot_calls
= 0;
658 /* Worker callback of cgraph_for_node_and_aliases accumulating statistics of
659 non-thunk incoming edges to NODE. */
662 gather_caller_stats (struct cgraph_node
*node
, void *data
)
664 struct caller_statistics
*stats
= (struct caller_statistics
*) data
;
665 struct cgraph_edge
*cs
;
667 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
668 if (!cs
->caller
->thunk
.thunk_p
)
670 if (cs
->count
.initialized_p ())
671 stats
->count_sum
+= cs
->count
;
672 stats
->freq_sum
+= cs
->frequency
;
674 if (cs
->maybe_hot_p ())
675 stats
->n_hot_calls
++;
681 /* Return true if this NODE is viable candidate for cloning. */
684 ipcp_cloning_candidate_p (struct cgraph_node
*node
)
686 struct caller_statistics stats
;
688 gcc_checking_assert (node
->has_gimple_body_p ());
690 if (!opt_for_fn (node
->decl
, flag_ipa_cp_clone
))
693 fprintf (dump_file
, "Not considering %s for cloning; "
694 "-fipa-cp-clone disabled.\n",
699 if (node
->optimize_for_size_p ())
702 fprintf (dump_file
, "Not considering %s for cloning; "
703 "optimizing it for size.\n",
708 init_caller_stats (&stats
);
709 node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
, false);
711 if (ipa_fn_summaries
->get (node
)->self_size
< stats
.n_calls
)
714 fprintf (dump_file
, "Considering %s for cloning; code might shrink.\n",
719 /* When profile is available and function is hot, propagate into it even if
720 calls seems cold; constant propagation can improve function's speed
722 if (max_count
> profile_count::zero ())
724 if (stats
.count_sum
> node
->count
.apply_scale (90, 100))
727 fprintf (dump_file
, "Considering %s for cloning; "
728 "usually called directly.\n",
733 if (!stats
.n_hot_calls
)
736 fprintf (dump_file
, "Not considering %s for cloning; no hot calls.\n",
741 fprintf (dump_file
, "Considering %s for cloning.\n",
746 template <typename valtype
>
747 class value_topo_info
750 /* Head of the linked list of topologically sorted values. */
751 ipcp_value
<valtype
> *values_topo
;
752 /* Stack for creating SCCs, represented by a linked list too. */
753 ipcp_value
<valtype
> *stack
;
754 /* Counter driving the algorithm in add_val_to_toposort. */
757 value_topo_info () : values_topo (NULL
), stack (NULL
), dfs_counter (0)
759 void add_val (ipcp_value
<valtype
> *cur_val
);
760 void propagate_effects ();
763 /* Arrays representing a topological ordering of call graph nodes and a stack
764 of nodes used during constant propagation and also data required to perform
765 topological sort of values and propagation of benefits in the determined
771 /* Array with obtained topological order of cgraph nodes. */
772 struct cgraph_node
**order
;
773 /* Stack of cgraph nodes used during propagation within SCC until all values
774 in the SCC stabilize. */
775 struct cgraph_node
**stack
;
776 int nnodes
, stack_top
;
778 value_topo_info
<tree
> constants
;
779 value_topo_info
<ipa_polymorphic_call_context
> contexts
;
781 ipa_topo_info () : order(NULL
), stack(NULL
), nnodes(0), stack_top(0),
786 /* Allocate the arrays in TOPO and topologically sort the nodes into order. */
789 build_toporder_info (struct ipa_topo_info
*topo
)
791 topo
->order
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
792 topo
->stack
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
794 gcc_checking_assert (topo
->stack_top
== 0);
795 topo
->nnodes
= ipa_reduced_postorder (topo
->order
, true, true, NULL
);
798 /* Free information about strongly connected components and the arrays in
802 free_toporder_info (struct ipa_topo_info
*topo
)
804 ipa_free_postorder_info ();
809 /* Add NODE to the stack in TOPO, unless it is already there. */
812 push_node_to_stack (struct ipa_topo_info
*topo
, struct cgraph_node
*node
)
814 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
815 if (info
->node_enqueued
)
817 info
->node_enqueued
= 1;
818 topo
->stack
[topo
->stack_top
++] = node
;
821 /* Pop a node from the stack in TOPO and return it or return NULL if the stack
824 static struct cgraph_node
*
825 pop_node_from_stack (struct ipa_topo_info
*topo
)
829 struct cgraph_node
*node
;
831 node
= topo
->stack
[topo
->stack_top
];
832 IPA_NODE_REF (node
)->node_enqueued
= 0;
839 /* Set lattice LAT to bottom and return true if it previously was not set as
842 template <typename valtype
>
844 ipcp_lattice
<valtype
>::set_to_bottom ()
851 /* Mark lattice as containing an unknown value and return true if it previously
852 was not marked as such. */
854 template <typename valtype
>
856 ipcp_lattice
<valtype
>::set_contains_variable ()
858 bool ret
= !contains_variable
;
859 contains_variable
= true;
863 /* Set all aggegate lattices in PLATS to bottom and return true if they were
864 not previously set as such. */
867 set_agg_lats_to_bottom (struct ipcp_param_lattices
*plats
)
869 bool ret
= !plats
->aggs_bottom
;
870 plats
->aggs_bottom
= true;
874 /* Mark all aggegate lattices in PLATS as containing an unknown value and
875 return true if they were not previously marked as such. */
878 set_agg_lats_contain_variable (struct ipcp_param_lattices
*plats
)
880 bool ret
= !plats
->aggs_contain_variable
;
881 plats
->aggs_contain_variable
= true;
886 ipcp_vr_lattice::meet_with (const ipcp_vr_lattice
&other
)
888 return meet_with_1 (&other
.m_vr
);
891 /* Meet the current value of the lattice with value ranfge described by VR
895 ipcp_vr_lattice::meet_with (const value_range
*p_vr
)
897 return meet_with_1 (p_vr
);
900 /* Meet the current value of the lattice with value ranfge described by
904 ipcp_vr_lattice::meet_with_1 (const value_range
*other_vr
)
906 tree min
= m_vr
.min
, max
= m_vr
.max
;
907 value_range_type type
= m_vr
.type
;
912 if (other_vr
->type
== VR_VARYING
)
913 return set_to_bottom ();
915 vrp_meet (&m_vr
, other_vr
);
916 if (type
!= m_vr
.type
924 /* Return true if value range information in the lattice is yet unknown. */
927 ipcp_vr_lattice::top_p () const
929 return m_vr
.type
== VR_UNDEFINED
;
932 /* Return true if value range information in the lattice is known to be
936 ipcp_vr_lattice::bottom_p () const
938 return m_vr
.type
== VR_VARYING
;
941 /* Set value range information in the lattice to bottom. Return true if it
942 previously was in a different state. */
945 ipcp_vr_lattice::set_to_bottom ()
947 if (m_vr
.type
== VR_VARYING
)
949 m_vr
.type
= VR_VARYING
;
953 /* Set lattice value to bottom, if it already isn't the case. */
956 ipcp_bits_lattice::set_to_bottom ()
960 m_lattice_val
= IPA_BITS_VARYING
;
966 /* Set to constant if it isn't already. Only meant to be called
967 when switching state from TOP. */
970 ipcp_bits_lattice::set_to_constant (widest_int value
, widest_int mask
)
972 gcc_assert (top_p ());
973 m_lattice_val
= IPA_BITS_CONSTANT
;
979 /* Convert operand to value, mask form. */
982 ipcp_bits_lattice::get_value_and_mask (tree operand
, widest_int
*valuep
, widest_int
*maskp
)
984 wide_int
get_nonzero_bits (const_tree
);
986 if (TREE_CODE (operand
) == INTEGER_CST
)
988 *valuep
= wi::to_widest (operand
);
998 /* Meet operation, similar to ccp_lattice_meet, we xor values
999 if this->value, value have different values at same bit positions, we want
1000 to drop that bit to varying. Return true if mask is changed.
1001 This function assumes that the lattice value is in CONSTANT state */
1004 ipcp_bits_lattice::meet_with_1 (widest_int value
, widest_int mask
,
1007 gcc_assert (constant_p ());
1009 widest_int old_mask
= m_mask
;
1010 m_mask
= (m_mask
| mask
) | (m_value
^ value
);
1012 if (wi::sext (m_mask
, precision
) == -1)
1013 return set_to_bottom ();
1015 return m_mask
!= old_mask
;
1018 /* Meet the bits lattice with operand
1019 described by <value, mask, sgn, precision. */
1022 ipcp_bits_lattice::meet_with (widest_int value
, widest_int mask
,
1030 if (wi::sext (mask
, precision
) == -1)
1031 return set_to_bottom ();
1032 return set_to_constant (value
, mask
);
1035 return meet_with_1 (value
, mask
, precision
);
1038 /* Meet bits lattice with the result of bit_value_binop (other, operand)
1039 if code is binary operation or bit_value_unop (other) if code is unary op.
1040 In the case when code is nop_expr, no adjustment is required. */
1043 ipcp_bits_lattice::meet_with (ipcp_bits_lattice
& other
, unsigned precision
,
1044 signop sgn
, enum tree_code code
, tree operand
)
1046 if (other
.bottom_p ())
1047 return set_to_bottom ();
1049 if (bottom_p () || other
.top_p ())
1052 widest_int adjusted_value
, adjusted_mask
;
1054 if (TREE_CODE_CLASS (code
) == tcc_binary
)
1056 tree type
= TREE_TYPE (operand
);
1057 gcc_assert (INTEGRAL_TYPE_P (type
));
1058 widest_int o_value
, o_mask
;
1059 get_value_and_mask (operand
, &o_value
, &o_mask
);
1061 bit_value_binop (code
, sgn
, precision
, &adjusted_value
, &adjusted_mask
,
1062 sgn
, precision
, other
.get_value (), other
.get_mask (),
1063 TYPE_SIGN (type
), TYPE_PRECISION (type
), o_value
, o_mask
);
1065 if (wi::sext (adjusted_mask
, precision
) == -1)
1066 return set_to_bottom ();
1069 else if (TREE_CODE_CLASS (code
) == tcc_unary
)
1071 bit_value_unop (code
, sgn
, precision
, &adjusted_value
,
1072 &adjusted_mask
, sgn
, precision
, other
.get_value (),
1075 if (wi::sext (adjusted_mask
, precision
) == -1)
1076 return set_to_bottom ();
1080 return set_to_bottom ();
1084 if (wi::sext (adjusted_mask
, precision
) == -1)
1085 return set_to_bottom ();
1086 return set_to_constant (adjusted_value
, adjusted_mask
);
1089 return meet_with_1 (adjusted_value
, adjusted_mask
, precision
);
1092 /* Mark bot aggregate and scalar lattices as containing an unknown variable,
1093 return true is any of them has not been marked as such so far. */
1096 set_all_contains_variable (struct ipcp_param_lattices
*plats
)
1099 ret
= plats
->itself
.set_contains_variable ();
1100 ret
|= plats
->ctxlat
.set_contains_variable ();
1101 ret
|= set_agg_lats_contain_variable (plats
);
1102 ret
|= plats
->bits_lattice
.set_to_bottom ();
1103 ret
|= plats
->m_value_range
.set_to_bottom ();
1107 /* Worker of call_for_symbol_thunks_and_aliases, increment the integer DATA
1108 points to by the number of callers to NODE. */
1111 count_callers (cgraph_node
*node
, void *data
)
1113 int *caller_count
= (int *) data
;
1115 for (cgraph_edge
*cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
1116 /* Local thunks can be handled transparently, but if the thunk can not
1117 be optimized out, count it as a real use. */
1118 if (!cs
->caller
->thunk
.thunk_p
|| !cs
->caller
->local
.local
)
1123 /* Worker of call_for_symbol_thunks_and_aliases, it is supposed to be called on
1124 the one caller of some other node. Set the caller's corresponding flag. */
1127 set_single_call_flag (cgraph_node
*node
, void *)
1129 cgraph_edge
*cs
= node
->callers
;
1130 /* Local thunks can be handled transparently, skip them. */
1131 while (cs
&& cs
->caller
->thunk
.thunk_p
&& cs
->caller
->local
.local
)
1132 cs
= cs
->next_caller
;
1135 IPA_NODE_REF (cs
->caller
)->node_calling_single_call
= true;
1141 /* Initialize ipcp_lattices. */
1144 initialize_node_lattices (struct cgraph_node
*node
)
1146 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1147 struct cgraph_edge
*ie
;
1148 bool disable
= false, variable
= false;
1151 gcc_checking_assert (node
->has_gimple_body_p ());
1152 if (cgraph_local_p (node
))
1154 int caller_count
= 0;
1155 node
->call_for_symbol_thunks_and_aliases (count_callers
, &caller_count
,
1157 gcc_checking_assert (caller_count
> 0);
1158 if (caller_count
== 1)
1159 node
->call_for_symbol_thunks_and_aliases (set_single_call_flag
,
1164 /* When cloning is allowed, we can assume that externally visible
1165 functions are not called. We will compensate this by cloning
1167 if (ipcp_versionable_function_p (node
)
1168 && ipcp_cloning_candidate_p (node
))
1174 for (i
= 0; i
< ipa_get_param_count (info
); i
++)
1176 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1177 plats
->m_value_range
.init ();
1180 if (disable
|| variable
)
1182 for (i
= 0; i
< ipa_get_param_count (info
); i
++)
1184 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1187 plats
->itself
.set_to_bottom ();
1188 plats
->ctxlat
.set_to_bottom ();
1189 set_agg_lats_to_bottom (plats
);
1190 plats
->bits_lattice
.set_to_bottom ();
1191 plats
->m_value_range
.set_to_bottom ();
1194 set_all_contains_variable (plats
);
1196 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1197 && !node
->alias
&& !node
->thunk
.thunk_p
)
1198 fprintf (dump_file
, "Marking all lattices of %s as %s\n",
1199 node
->dump_name (), disable
? "BOTTOM" : "VARIABLE");
1202 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
1203 if (ie
->indirect_info
->polymorphic
1204 && ie
->indirect_info
->param_index
>= 0)
1206 gcc_checking_assert (ie
->indirect_info
->param_index
>= 0);
1207 ipa_get_parm_lattices (info
,
1208 ie
->indirect_info
->param_index
)->virt_call
= 1;
1212 /* Return the result of a (possibly arithmetic) pass through jump function
1213 JFUNC on the constant value INPUT. Return NULL_TREE if that cannot be
1214 determined or be considered an interprocedural invariant. */
1217 ipa_get_jf_pass_through_result (struct ipa_jump_func
*jfunc
, tree input
)
1221 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
1223 if (!is_gimple_ip_invariant (input
))
1226 if (TREE_CODE_CLASS (ipa_get_jf_pass_through_operation (jfunc
))
1228 res
= fold_unary (ipa_get_jf_pass_through_operation (jfunc
),
1229 TREE_TYPE (input
), input
);
1232 if (TREE_CODE_CLASS (ipa_get_jf_pass_through_operation (jfunc
))
1234 restype
= boolean_type_node
;
1236 restype
= TREE_TYPE (input
);
1237 res
= fold_binary (ipa_get_jf_pass_through_operation (jfunc
), restype
,
1238 input
, ipa_get_jf_pass_through_operand (jfunc
));
1240 if (res
&& !is_gimple_ip_invariant (res
))
1246 /* Return the result of an ancestor jump function JFUNC on the constant value
1247 INPUT. Return NULL_TREE if that cannot be determined. */
1250 ipa_get_jf_ancestor_result (struct ipa_jump_func
*jfunc
, tree input
)
1252 gcc_checking_assert (TREE_CODE (input
) != TREE_BINFO
);
1253 if (TREE_CODE (input
) == ADDR_EXPR
)
1255 tree t
= TREE_OPERAND (input
, 0);
1256 t
= build_ref_for_offset (EXPR_LOCATION (t
), t
,
1257 ipa_get_jf_ancestor_offset (jfunc
), false,
1258 ptr_type_node
, NULL
, false);
1259 return build_fold_addr_expr (t
);
1265 /* Determine whether JFUNC evaluates to a single known constant value and if
1266 so, return it. Otherwise return NULL. INFO describes the caller node or
1267 the one it is inlined to, so that pass-through jump functions can be
1271 ipa_value_from_jfunc (struct ipa_node_params
*info
, struct ipa_jump_func
*jfunc
)
1273 if (jfunc
->type
== IPA_JF_CONST
)
1274 return ipa_get_jf_constant (jfunc
);
1275 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1276 || jfunc
->type
== IPA_JF_ANCESTOR
)
1281 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1282 idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1284 idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1286 if (info
->ipcp_orig_node
)
1287 input
= info
->known_csts
[idx
];
1290 ipcp_lattice
<tree
> *lat
;
1293 || idx
>= ipa_get_param_count (info
))
1295 lat
= ipa_get_scalar_lat (info
, idx
);
1296 if (!lat
->is_single_const ())
1298 input
= lat
->values
->value
;
1304 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1305 return ipa_get_jf_pass_through_result (jfunc
, input
);
1307 return ipa_get_jf_ancestor_result (jfunc
, input
);
1313 /* Determie whether JFUNC evaluates to single known polymorphic context, given
1314 that INFO describes the caller node or the one it is inlined to, CS is the
1315 call graph edge corresponding to JFUNC and CSIDX index of the described
1318 ipa_polymorphic_call_context
1319 ipa_context_from_jfunc (ipa_node_params
*info
, cgraph_edge
*cs
, int csidx
,
1320 ipa_jump_func
*jfunc
)
1322 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
1323 ipa_polymorphic_call_context ctx
;
1324 ipa_polymorphic_call_context
*edge_ctx
1325 = cs
? ipa_get_ith_polymorhic_call_context (args
, csidx
) : NULL
;
1327 if (edge_ctx
&& !edge_ctx
->useless_p ())
1330 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1331 || jfunc
->type
== IPA_JF_ANCESTOR
)
1333 ipa_polymorphic_call_context srcctx
;
1335 bool type_preserved
= true;
1336 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1338 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1340 type_preserved
= ipa_get_jf_pass_through_type_preserved (jfunc
);
1341 srcidx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1345 type_preserved
= ipa_get_jf_ancestor_type_preserved (jfunc
);
1346 srcidx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1348 if (info
->ipcp_orig_node
)
1350 if (info
->known_contexts
.exists ())
1351 srcctx
= info
->known_contexts
[srcidx
];
1356 || srcidx
>= ipa_get_param_count (info
))
1358 ipcp_lattice
<ipa_polymorphic_call_context
> *lat
;
1359 lat
= ipa_get_poly_ctx_lat (info
, srcidx
);
1360 if (!lat
->is_single_const ())
1362 srcctx
= lat
->values
->value
;
1364 if (srcctx
.useless_p ())
1366 if (jfunc
->type
== IPA_JF_ANCESTOR
)
1367 srcctx
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
1368 if (!type_preserved
)
1369 srcctx
.possible_dynamic_type_change (cs
->in_polymorphic_cdtor
);
1370 srcctx
.combine_with (ctx
);
1377 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
1378 bottom, not containing a variable component and without any known value at
1382 ipcp_verify_propagated_values (void)
1384 struct cgraph_node
*node
;
1386 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
1388 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1389 int i
, count
= ipa_get_param_count (info
);
1391 for (i
= 0; i
< count
; i
++)
1393 ipcp_lattice
<tree
> *lat
= ipa_get_scalar_lat (info
, i
);
1396 && !lat
->contains_variable
1397 && lat
->values_count
== 0)
1401 symtab
->dump (dump_file
);
1402 fprintf (dump_file
, "\nIPA lattices after constant "
1403 "propagation, before gcc_unreachable:\n");
1404 print_all_lattices (dump_file
, true, false);
1413 /* Return true iff X and Y should be considered equal values by IPA-CP. */
1416 values_equal_for_ipcp_p (tree x
, tree y
)
1418 gcc_checking_assert (x
!= NULL_TREE
&& y
!= NULL_TREE
);
1423 if (TREE_CODE (x
) == ADDR_EXPR
1424 && TREE_CODE (y
) == ADDR_EXPR
1425 && TREE_CODE (TREE_OPERAND (x
, 0)) == CONST_DECL
1426 && TREE_CODE (TREE_OPERAND (y
, 0)) == CONST_DECL
)
1427 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x
, 0)),
1428 DECL_INITIAL (TREE_OPERAND (y
, 0)), 0);
1430 return operand_equal_p (x
, y
, 0);
1433 /* Return true iff X and Y should be considered equal contexts by IPA-CP. */
1436 values_equal_for_ipcp_p (ipa_polymorphic_call_context x
,
1437 ipa_polymorphic_call_context y
)
1439 return x
.equal_to (y
);
1443 /* Add a new value source to the value represented by THIS, marking that a
1444 value comes from edge CS and (if the underlying jump function is a
1445 pass-through or an ancestor one) from a caller value SRC_VAL of a caller
1446 parameter described by SRC_INDEX. OFFSET is negative if the source was the
1447 scalar value of the parameter itself or the offset within an aggregate. */
1449 template <typename valtype
>
1451 ipcp_value
<valtype
>::add_source (cgraph_edge
*cs
, ipcp_value
*src_val
,
1452 int src_idx
, HOST_WIDE_INT offset
)
1454 ipcp_value_source
<valtype
> *src
;
1456 src
= new (ipcp_sources_pool
.allocate ()) ipcp_value_source
<valtype
>;
1457 src
->offset
= offset
;
1460 src
->index
= src_idx
;
1462 src
->next
= sources
;
1466 /* Allocate a new ipcp_value holding a tree constant, initialize its value to
1467 SOURCE and clear all other fields. */
1469 static ipcp_value
<tree
> *
1470 allocate_and_init_ipcp_value (tree source
)
1472 ipcp_value
<tree
> *val
;
1474 val
= new (ipcp_cst_values_pool
.allocate ()) ipcp_value
<tree
>();
1475 val
->value
= source
;
1479 /* Allocate a new ipcp_value holding a polymorphic context, initialize its
1480 value to SOURCE and clear all other fields. */
1482 static ipcp_value
<ipa_polymorphic_call_context
> *
1483 allocate_and_init_ipcp_value (ipa_polymorphic_call_context source
)
1485 ipcp_value
<ipa_polymorphic_call_context
> *val
;
1488 val
= new (ipcp_poly_ctx_values_pool
.allocate ())
1489 ipcp_value
<ipa_polymorphic_call_context
>();
1490 val
->value
= source
;
1494 /* Try to add NEWVAL to LAT, potentially creating a new ipcp_value for it. CS,
1495 SRC_VAL SRC_INDEX and OFFSET are meant for add_source and have the same
1496 meaning. OFFSET -1 means the source is scalar and not a part of an
1499 template <typename valtype
>
1501 ipcp_lattice
<valtype
>::add_value (valtype newval
, cgraph_edge
*cs
,
1502 ipcp_value
<valtype
> *src_val
,
1503 int src_idx
, HOST_WIDE_INT offset
)
1505 ipcp_value
<valtype
> *val
;
1510 for (val
= values
; val
; val
= val
->next
)
1511 if (values_equal_for_ipcp_p (val
->value
, newval
))
1513 if (ipa_edge_within_scc (cs
))
1515 ipcp_value_source
<valtype
> *s
;
1516 for (s
= val
->sources
; s
; s
= s
->next
)
1523 val
->add_source (cs
, src_val
, src_idx
, offset
);
1527 if (values_count
== PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE
))
1529 /* We can only free sources, not the values themselves, because sources
1530 of other values in this SCC might point to them. */
1531 for (val
= values
; val
; val
= val
->next
)
1533 while (val
->sources
)
1535 ipcp_value_source
<valtype
> *src
= val
->sources
;
1536 val
->sources
= src
->next
;
1537 ipcp_sources_pool
.remove ((ipcp_value_source
<tree
>*)src
);
1542 return set_to_bottom ();
1546 val
= allocate_and_init_ipcp_value (newval
);
1547 val
->add_source (cs
, src_val
, src_idx
, offset
);
1553 /* Propagate values through a pass-through jump function JFUNC associated with
1554 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1555 is the index of the source parameter. */
1558 propagate_vals_across_pass_through (cgraph_edge
*cs
, ipa_jump_func
*jfunc
,
1559 ipcp_lattice
<tree
> *src_lat
,
1560 ipcp_lattice
<tree
> *dest_lat
, int src_idx
)
1562 ipcp_value
<tree
> *src_val
;
1565 /* Do not create new values when propagating within an SCC because if there
1566 are arithmetic functions with circular dependencies, there is infinite
1567 number of them and we would just make lattices bottom. */
1568 if ((ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1569 && ipa_edge_within_scc (cs
))
1570 ret
= dest_lat
->set_contains_variable ();
1572 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1574 tree cstval
= ipa_get_jf_pass_through_result (jfunc
, src_val
->value
);
1577 ret
|= dest_lat
->add_value (cstval
, cs
, src_val
, src_idx
);
1579 ret
|= dest_lat
->set_contains_variable ();
1585 /* Propagate values through an ancestor jump function JFUNC associated with
1586 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1587 is the index of the source parameter. */
1590 propagate_vals_across_ancestor (struct cgraph_edge
*cs
,
1591 struct ipa_jump_func
*jfunc
,
1592 ipcp_lattice
<tree
> *src_lat
,
1593 ipcp_lattice
<tree
> *dest_lat
, int src_idx
)
1595 ipcp_value
<tree
> *src_val
;
1598 if (ipa_edge_within_scc (cs
))
1599 return dest_lat
->set_contains_variable ();
1601 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1603 tree t
= ipa_get_jf_ancestor_result (jfunc
, src_val
->value
);
1606 ret
|= dest_lat
->add_value (t
, cs
, src_val
, src_idx
);
1608 ret
|= dest_lat
->set_contains_variable ();
1614 /* Propagate scalar values across jump function JFUNC that is associated with
1615 edge CS and put the values into DEST_LAT. */
1618 propagate_scalar_across_jump_function (struct cgraph_edge
*cs
,
1619 struct ipa_jump_func
*jfunc
,
1620 ipcp_lattice
<tree
> *dest_lat
)
1622 if (dest_lat
->bottom
)
1625 if (jfunc
->type
== IPA_JF_CONST
)
1627 tree val
= ipa_get_jf_constant (jfunc
);
1628 return dest_lat
->add_value (val
, cs
, NULL
, 0);
1630 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1631 || jfunc
->type
== IPA_JF_ANCESTOR
)
1633 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1634 ipcp_lattice
<tree
> *src_lat
;
1638 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1639 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1641 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1643 src_lat
= ipa_get_scalar_lat (caller_info
, src_idx
);
1644 if (src_lat
->bottom
)
1645 return dest_lat
->set_contains_variable ();
1647 /* If we would need to clone the caller and cannot, do not propagate. */
1648 if (!ipcp_versionable_function_p (cs
->caller
)
1649 && (src_lat
->contains_variable
1650 || (src_lat
->values_count
> 1)))
1651 return dest_lat
->set_contains_variable ();
1653 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1654 ret
= propagate_vals_across_pass_through (cs
, jfunc
, src_lat
,
1657 ret
= propagate_vals_across_ancestor (cs
, jfunc
, src_lat
, dest_lat
,
1660 if (src_lat
->contains_variable
)
1661 ret
|= dest_lat
->set_contains_variable ();
1666 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1667 use it for indirect inlining), we should propagate them too. */
1668 return dest_lat
->set_contains_variable ();
1671 /* Propagate scalar values across jump function JFUNC that is associated with
1672 edge CS and describes argument IDX and put the values into DEST_LAT. */
1675 propagate_context_across_jump_function (cgraph_edge
*cs
,
1676 ipa_jump_func
*jfunc
, int idx
,
1677 ipcp_lattice
<ipa_polymorphic_call_context
> *dest_lat
)
1679 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
1680 if (dest_lat
->bottom
)
1683 bool added_sth
= false;
1684 bool type_preserved
= true;
1686 ipa_polymorphic_call_context edge_ctx
, *edge_ctx_ptr
1687 = ipa_get_ith_polymorhic_call_context (args
, idx
);
1690 edge_ctx
= *edge_ctx_ptr
;
1692 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1693 || jfunc
->type
== IPA_JF_ANCESTOR
)
1695 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1697 ipcp_lattice
<ipa_polymorphic_call_context
> *src_lat
;
1699 /* TODO: Once we figure out how to propagate speculations, it will
1700 probably be a good idea to switch to speculation if type_preserved is
1701 not set instead of punting. */
1702 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1704 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1706 type_preserved
= ipa_get_jf_pass_through_type_preserved (jfunc
);
1707 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1711 type_preserved
= ipa_get_jf_ancestor_type_preserved (jfunc
);
1712 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1715 src_lat
= ipa_get_poly_ctx_lat (caller_info
, src_idx
);
1716 /* If we would need to clone the caller and cannot, do not propagate. */
1717 if (!ipcp_versionable_function_p (cs
->caller
)
1718 && (src_lat
->contains_variable
1719 || (src_lat
->values_count
> 1)))
1722 ipcp_value
<ipa_polymorphic_call_context
> *src_val
;
1723 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1725 ipa_polymorphic_call_context cur
= src_val
->value
;
1727 if (!type_preserved
)
1728 cur
.possible_dynamic_type_change (cs
->in_polymorphic_cdtor
);
1729 if (jfunc
->type
== IPA_JF_ANCESTOR
)
1730 cur
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
1731 /* TODO: In cases we know how the context is going to be used,
1732 we can improve the result by passing proper OTR_TYPE. */
1733 cur
.combine_with (edge_ctx
);
1734 if (!cur
.useless_p ())
1736 if (src_lat
->contains_variable
1737 && !edge_ctx
.equal_to (cur
))
1738 ret
|= dest_lat
->set_contains_variable ();
1739 ret
|= dest_lat
->add_value (cur
, cs
, src_val
, src_idx
);
1749 if (!edge_ctx
.useless_p ())
1750 ret
|= dest_lat
->add_value (edge_ctx
, cs
);
1752 ret
|= dest_lat
->set_contains_variable ();
1758 /* Propagate bits across jfunc that is associated with
1759 edge cs and update dest_lattice accordingly. */
1762 propagate_bits_across_jump_function (cgraph_edge
*cs
, int idx
,
1763 ipa_jump_func
*jfunc
,
1764 ipcp_bits_lattice
*dest_lattice
)
1766 if (dest_lattice
->bottom_p ())
1769 enum availability availability
;
1770 cgraph_node
*callee
= cs
->callee
->function_symbol (&availability
);
1771 struct ipa_node_params
*callee_info
= IPA_NODE_REF (callee
);
1772 tree parm_type
= ipa_get_type (callee_info
, idx
);
1774 /* For K&R C programs, ipa_get_type() could return NULL_TREE.
1775 Avoid the transform for these cases. */
1778 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1779 fprintf (dump_file
, "Setting dest_lattice to bottom, because"
1780 " param %i type is NULL for %s\n", idx
,
1781 cs
->callee
->name ());
1783 return dest_lattice
->set_to_bottom ();
1786 unsigned precision
= TYPE_PRECISION (parm_type
);
1787 signop sgn
= TYPE_SIGN (parm_type
);
1789 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1790 || jfunc
->type
== IPA_JF_ANCESTOR
)
1792 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1793 tree operand
= NULL_TREE
;
1794 enum tree_code code
;
1797 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1799 code
= ipa_get_jf_pass_through_operation (jfunc
);
1800 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1801 if (code
!= NOP_EXPR
)
1802 operand
= ipa_get_jf_pass_through_operand (jfunc
);
1806 code
= POINTER_PLUS_EXPR
;
1807 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1808 unsigned HOST_WIDE_INT offset
= ipa_get_jf_ancestor_offset (jfunc
) / BITS_PER_UNIT
;
1809 operand
= build_int_cstu (size_type_node
, offset
);
1812 struct ipcp_param_lattices
*src_lats
1813 = ipa_get_parm_lattices (caller_info
, src_idx
);
1815 /* Try to propagate bits if src_lattice is bottom, but jfunc is known.
1821 Assume lattice for x is bottom, however we can still propagate
1822 result of x & 0xff == 0xff, which gets computed during ccp1 pass
1823 and we store it in jump function during analysis stage. */
1825 if (src_lats
->bits_lattice
.bottom_p ()
1827 return dest_lattice
->meet_with (jfunc
->bits
->value
, jfunc
->bits
->mask
,
1830 return dest_lattice
->meet_with (src_lats
->bits_lattice
, precision
, sgn
,
1834 else if (jfunc
->type
== IPA_JF_ANCESTOR
)
1835 return dest_lattice
->set_to_bottom ();
1836 else if (jfunc
->bits
)
1837 return dest_lattice
->meet_with (jfunc
->bits
->value
, jfunc
->bits
->mask
,
1840 return dest_lattice
->set_to_bottom ();
1843 /* Emulate effects of unary OPERATION and/or conversion from SRC_TYPE to
1844 DST_TYPE on value range in SRC_VR and store it to DST_VR. Return true if
1845 the result is a range or an anti-range. */
1848 ipa_vr_operation_and_type_effects (value_range
*dst_vr
, value_range
*src_vr
,
1849 enum tree_code operation
,
1850 tree dst_type
, tree src_type
)
1852 memset (dst_vr
, 0, sizeof (*dst_vr
));
1853 extract_range_from_unary_expr (dst_vr
, operation
, dst_type
, src_vr
, src_type
);
1854 if (dst_vr
->type
== VR_RANGE
|| dst_vr
->type
== VR_ANTI_RANGE
)
1860 /* Propagate value range across jump function JFUNC that is associated with
1861 edge CS with param of callee of PARAM_TYPE and update DEST_PLATS
1865 propagate_vr_across_jump_function (cgraph_edge
*cs
, ipa_jump_func
*jfunc
,
1866 struct ipcp_param_lattices
*dest_plats
,
1869 ipcp_vr_lattice
*dest_lat
= &dest_plats
->m_value_range
;
1871 if (dest_lat
->bottom_p ())
1875 || (!INTEGRAL_TYPE_P (param_type
)
1876 && !POINTER_TYPE_P (param_type
)))
1877 return dest_lat
->set_to_bottom ();
1879 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1881 enum tree_code operation
= ipa_get_jf_pass_through_operation (jfunc
);
1883 if (TREE_CODE_CLASS (operation
) == tcc_unary
)
1885 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1886 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1887 tree operand_type
= ipa_get_type (caller_info
, src_idx
);
1888 struct ipcp_param_lattices
*src_lats
1889 = ipa_get_parm_lattices (caller_info
, src_idx
);
1891 if (src_lats
->m_value_range
.bottom_p ())
1892 return dest_lat
->set_to_bottom ();
1894 if (ipa_vr_operation_and_type_effects (&vr
,
1895 &src_lats
->m_value_range
.m_vr
,
1896 operation
, param_type
,
1898 return dest_lat
->meet_with (&vr
);
1901 else if (jfunc
->type
== IPA_JF_CONST
)
1903 tree val
= ipa_get_jf_constant (jfunc
);
1904 if (TREE_CODE (val
) == INTEGER_CST
)
1906 val
= fold_convert (param_type
, val
);
1907 if (TREE_OVERFLOW_P (val
))
1908 val
= drop_tree_overflow (val
);
1911 memset (&tmpvr
, 0, sizeof (tmpvr
));
1912 tmpvr
.type
= VR_RANGE
;
1915 return dest_lat
->meet_with (&tmpvr
);
1921 && ipa_vr_operation_and_type_effects (&vr
, jfunc
->m_vr
, NOP_EXPR
,
1923 TREE_TYPE (jfunc
->m_vr
->min
)))
1924 return dest_lat
->meet_with (&vr
);
1926 return dest_lat
->set_to_bottom ();
1929 /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
1930 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
1931 other cases, return false). If there are no aggregate items, set
1932 aggs_by_ref to NEW_AGGS_BY_REF. */
1935 set_check_aggs_by_ref (struct ipcp_param_lattices
*dest_plats
,
1936 bool new_aggs_by_ref
)
1938 if (dest_plats
->aggs
)
1940 if (dest_plats
->aggs_by_ref
!= new_aggs_by_ref
)
1942 set_agg_lats_to_bottom (dest_plats
);
1947 dest_plats
->aggs_by_ref
= new_aggs_by_ref
;
1951 /* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
1952 already existing lattice for the given OFFSET and SIZE, marking all skipped
1953 lattices as containing variable and checking for overlaps. If there is no
1954 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
1955 it with offset, size and contains_variable to PRE_EXISTING, and return true,
1956 unless there are too many already. If there are two many, return false. If
1957 there are overlaps turn whole DEST_PLATS to bottom and return false. If any
1958 skipped lattices were newly marked as containing variable, set *CHANGE to
1962 merge_agg_lats_step (struct ipcp_param_lattices
*dest_plats
,
1963 HOST_WIDE_INT offset
, HOST_WIDE_INT val_size
,
1964 struct ipcp_agg_lattice
***aglat
,
1965 bool pre_existing
, bool *change
)
1967 gcc_checking_assert (offset
>= 0);
1969 while (**aglat
&& (**aglat
)->offset
< offset
)
1971 if ((**aglat
)->offset
+ (**aglat
)->size
> offset
)
1973 set_agg_lats_to_bottom (dest_plats
);
1976 *change
|= (**aglat
)->set_contains_variable ();
1977 *aglat
= &(**aglat
)->next
;
1980 if (**aglat
&& (**aglat
)->offset
== offset
)
1982 if ((**aglat
)->size
!= val_size
1984 && (**aglat
)->next
->offset
< offset
+ val_size
))
1986 set_agg_lats_to_bottom (dest_plats
);
1989 gcc_checking_assert (!(**aglat
)->next
1990 || (**aglat
)->next
->offset
>= offset
+ val_size
);
1995 struct ipcp_agg_lattice
*new_al
;
1997 if (**aglat
&& (**aglat
)->offset
< offset
+ val_size
)
1999 set_agg_lats_to_bottom (dest_plats
);
2002 if (dest_plats
->aggs_count
== PARAM_VALUE (PARAM_IPA_MAX_AGG_ITEMS
))
2004 dest_plats
->aggs_count
++;
2005 new_al
= ipcp_agg_lattice_pool
.allocate ();
2006 memset (new_al
, 0, sizeof (*new_al
));
2008 new_al
->offset
= offset
;
2009 new_al
->size
= val_size
;
2010 new_al
->contains_variable
= pre_existing
;
2012 new_al
->next
= **aglat
;
2018 /* Set all AGLAT and all other aggregate lattices reachable by next pointers as
2019 containing an unknown value. */
2022 set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice
*aglat
)
2027 ret
|= aglat
->set_contains_variable ();
2028 aglat
= aglat
->next
;
2033 /* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
2034 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source
2035 parameter used for lattice value sources. Return true if DEST_PLATS changed
2039 merge_aggregate_lattices (struct cgraph_edge
*cs
,
2040 struct ipcp_param_lattices
*dest_plats
,
2041 struct ipcp_param_lattices
*src_plats
,
2042 int src_idx
, HOST_WIDE_INT offset_delta
)
2044 bool pre_existing
= dest_plats
->aggs
!= NULL
;
2045 struct ipcp_agg_lattice
**dst_aglat
;
2048 if (set_check_aggs_by_ref (dest_plats
, src_plats
->aggs_by_ref
))
2050 if (src_plats
->aggs_bottom
)
2051 return set_agg_lats_contain_variable (dest_plats
);
2052 if (src_plats
->aggs_contain_variable
)
2053 ret
|= set_agg_lats_contain_variable (dest_plats
);
2054 dst_aglat
= &dest_plats
->aggs
;
2056 for (struct ipcp_agg_lattice
*src_aglat
= src_plats
->aggs
;
2058 src_aglat
= src_aglat
->next
)
2060 HOST_WIDE_INT new_offset
= src_aglat
->offset
- offset_delta
;
2064 if (merge_agg_lats_step (dest_plats
, new_offset
, src_aglat
->size
,
2065 &dst_aglat
, pre_existing
, &ret
))
2067 struct ipcp_agg_lattice
*new_al
= *dst_aglat
;
2069 dst_aglat
= &(*dst_aglat
)->next
;
2070 if (src_aglat
->bottom
)
2072 ret
|= new_al
->set_contains_variable ();
2075 if (src_aglat
->contains_variable
)
2076 ret
|= new_al
->set_contains_variable ();
2077 for (ipcp_value
<tree
> *val
= src_aglat
->values
;
2080 ret
|= new_al
->add_value (val
->value
, cs
, val
, src_idx
,
2083 else if (dest_plats
->aggs_bottom
)
2086 ret
|= set_chain_of_aglats_contains_variable (*dst_aglat
);
2090 /* Determine whether there is anything to propagate FROM SRC_PLATS through a
2091 pass-through JFUNC and if so, whether it has conform and conforms to the
2092 rules about propagating values passed by reference. */
2095 agg_pass_through_permissible_p (struct ipcp_param_lattices
*src_plats
,
2096 struct ipa_jump_func
*jfunc
)
2098 return src_plats
->aggs
2099 && (!src_plats
->aggs_by_ref
2100 || ipa_get_jf_pass_through_agg_preserved (jfunc
));
2103 /* Propagate scalar values across jump function JFUNC that is associated with
2104 edge CS and put the values into DEST_LAT. */
2107 propagate_aggs_across_jump_function (struct cgraph_edge
*cs
,
2108 struct ipa_jump_func
*jfunc
,
2109 struct ipcp_param_lattices
*dest_plats
)
2113 if (dest_plats
->aggs_bottom
)
2116 if (jfunc
->type
== IPA_JF_PASS_THROUGH
2117 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
2119 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2120 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
2121 struct ipcp_param_lattices
*src_plats
;
2123 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2124 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
2126 /* Currently we do not produce clobber aggregate jump
2127 functions, replace with merging when we do. */
2128 gcc_assert (!jfunc
->agg
.items
);
2129 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
,
2133 ret
|= set_agg_lats_contain_variable (dest_plats
);
2135 else if (jfunc
->type
== IPA_JF_ANCESTOR
2136 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
2138 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2139 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
2140 struct ipcp_param_lattices
*src_plats
;
2142 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2143 if (src_plats
->aggs
&& src_plats
->aggs_by_ref
)
2145 /* Currently we do not produce clobber aggregate jump
2146 functions, replace with merging when we do. */
2147 gcc_assert (!jfunc
->agg
.items
);
2148 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
, src_idx
,
2149 ipa_get_jf_ancestor_offset (jfunc
));
2151 else if (!src_plats
->aggs_by_ref
)
2152 ret
|= set_agg_lats_to_bottom (dest_plats
);
2154 ret
|= set_agg_lats_contain_variable (dest_plats
);
2156 else if (jfunc
->agg
.items
)
2158 bool pre_existing
= dest_plats
->aggs
!= NULL
;
2159 struct ipcp_agg_lattice
**aglat
= &dest_plats
->aggs
;
2160 struct ipa_agg_jf_item
*item
;
2163 if (set_check_aggs_by_ref (dest_plats
, jfunc
->agg
.by_ref
))
2166 FOR_EACH_VEC_ELT (*jfunc
->agg
.items
, i
, item
)
2168 HOST_WIDE_INT val_size
;
2170 if (item
->offset
< 0)
2172 gcc_checking_assert (is_gimple_ip_invariant (item
->value
));
2173 val_size
= tree_to_uhwi (TYPE_SIZE (TREE_TYPE (item
->value
)));
2175 if (merge_agg_lats_step (dest_plats
, item
->offset
, val_size
,
2176 &aglat
, pre_existing
, &ret
))
2178 ret
|= (*aglat
)->add_value (item
->value
, cs
, NULL
, 0, 0);
2179 aglat
= &(*aglat
)->next
;
2181 else if (dest_plats
->aggs_bottom
)
2185 ret
|= set_chain_of_aglats_contains_variable (*aglat
);
2188 ret
|= set_agg_lats_contain_variable (dest_plats
);
2193 /* Return true if on the way cfrom CS->caller to the final (non-alias and
2194 non-thunk) destination, the call passes through a thunk. */
2197 call_passes_through_thunk_p (cgraph_edge
*cs
)
2199 cgraph_node
*alias_or_thunk
= cs
->callee
;
2200 while (alias_or_thunk
->alias
)
2201 alias_or_thunk
= alias_or_thunk
->get_alias_target ();
2202 return alias_or_thunk
->thunk
.thunk_p
;
2205 /* Propagate constants from the caller to the callee of CS. INFO describes the
2209 propagate_constants_across_call (struct cgraph_edge
*cs
)
2211 struct ipa_node_params
*callee_info
;
2212 enum availability availability
;
2213 cgraph_node
*callee
;
2214 struct ipa_edge_args
*args
;
2216 int i
, args_count
, parms_count
;
2218 callee
= cs
->callee
->function_symbol (&availability
);
2219 if (!callee
->definition
)
2221 gcc_checking_assert (callee
->has_gimple_body_p ());
2222 callee_info
= IPA_NODE_REF (callee
);
2224 args
= IPA_EDGE_REF (cs
);
2225 args_count
= ipa_get_cs_argument_count (args
);
2226 parms_count
= ipa_get_param_count (callee_info
);
2227 if (parms_count
== 0)
2230 /* No propagation through instrumentation thunks is available yet.
2231 It should be possible with proper mapping of call args and
2232 instrumented callee params in the propagation loop below. But
2233 this case mostly occurs when legacy code calls instrumented code
2234 and it is not a primary target for optimizations.
2235 We detect instrumentation thunks in aliases and thunks chain by
2236 checking instrumentation_clone flag for chain source and target.
2237 Going through instrumentation thunks we always have it changed
2238 from 0 to 1 and all other nodes do not change it. */
2239 if (!cs
->callee
->instrumentation_clone
2240 && callee
->instrumentation_clone
)
2242 for (i
= 0; i
< parms_count
; i
++)
2243 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
2248 /* If this call goes through a thunk we must not propagate to the first (0th)
2249 parameter. However, we might need to uncover a thunk from below a series
2250 of aliases first. */
2251 if (call_passes_through_thunk_p (cs
))
2253 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
2260 for (; (i
< args_count
) && (i
< parms_count
); i
++)
2262 struct ipa_jump_func
*jump_func
= ipa_get_ith_jump_func (args
, i
);
2263 struct ipcp_param_lattices
*dest_plats
;
2264 tree param_type
= ipa_get_type (callee_info
, i
);
2266 dest_plats
= ipa_get_parm_lattices (callee_info
, i
);
2267 if (availability
== AVAIL_INTERPOSABLE
)
2268 ret
|= set_all_contains_variable (dest_plats
);
2271 ret
|= propagate_scalar_across_jump_function (cs
, jump_func
,
2272 &dest_plats
->itself
);
2273 ret
|= propagate_context_across_jump_function (cs
, jump_func
, i
,
2274 &dest_plats
->ctxlat
);
2276 |= propagate_bits_across_jump_function (cs
, i
, jump_func
,
2277 &dest_plats
->bits_lattice
);
2278 ret
|= propagate_aggs_across_jump_function (cs
, jump_func
,
2280 if (opt_for_fn (callee
->decl
, flag_ipa_vrp
))
2281 ret
|= propagate_vr_across_jump_function (cs
, jump_func
,
2282 dest_plats
, param_type
);
2284 ret
|= dest_plats
->m_value_range
.set_to_bottom ();
2287 for (; i
< parms_count
; i
++)
2288 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
, i
));
2293 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
2294 KNOWN_CONTEXTS, KNOWN_AGGS or AGG_REPS return the destination. The latter
2295 three can be NULL. If AGG_REPS is not NULL, KNOWN_AGGS is ignored. */
2298 ipa_get_indirect_edge_target_1 (struct cgraph_edge
*ie
,
2299 vec
<tree
> known_csts
,
2300 vec
<ipa_polymorphic_call_context
> known_contexts
,
2301 vec
<ipa_agg_jump_function_p
> known_aggs
,
2302 struct ipa_agg_replacement_value
*agg_reps
,
2305 int param_index
= ie
->indirect_info
->param_index
;
2306 HOST_WIDE_INT anc_offset
;
2310 *speculative
= false;
2312 if (param_index
== -1
2313 || known_csts
.length () <= (unsigned int) param_index
)
2316 if (!ie
->indirect_info
->polymorphic
)
2320 if (ie
->indirect_info
->agg_contents
)
2323 if (agg_reps
&& ie
->indirect_info
->guaranteed_unmodified
)
2327 if (agg_reps
->index
== param_index
2328 && agg_reps
->offset
== ie
->indirect_info
->offset
2329 && agg_reps
->by_ref
== ie
->indirect_info
->by_ref
)
2331 t
= agg_reps
->value
;
2334 agg_reps
= agg_reps
->next
;
2339 struct ipa_agg_jump_function
*agg
;
2340 if (known_aggs
.length () > (unsigned int) param_index
)
2341 agg
= known_aggs
[param_index
];
2344 bool from_global_constant
;
2345 t
= ipa_find_agg_cst_for_param (agg
, known_csts
[param_index
],
2346 ie
->indirect_info
->offset
,
2347 ie
->indirect_info
->by_ref
,
2348 &from_global_constant
);
2350 && !from_global_constant
2351 && !ie
->indirect_info
->guaranteed_unmodified
)
2356 t
= known_csts
[param_index
];
2359 && TREE_CODE (t
) == ADDR_EXPR
2360 && TREE_CODE (TREE_OPERAND (t
, 0)) == FUNCTION_DECL
)
2361 return TREE_OPERAND (t
, 0);
2366 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize
))
2369 gcc_assert (!ie
->indirect_info
->agg_contents
);
2370 anc_offset
= ie
->indirect_info
->offset
;
2374 /* Try to work out value of virtual table pointer value in replacemnets. */
2375 if (!t
&& agg_reps
&& !ie
->indirect_info
->by_ref
)
2379 if (agg_reps
->index
== param_index
2380 && agg_reps
->offset
== ie
->indirect_info
->offset
2381 && agg_reps
->by_ref
)
2383 t
= agg_reps
->value
;
2386 agg_reps
= agg_reps
->next
;
2390 /* Try to work out value of virtual table pointer value in known
2391 aggregate values. */
2392 if (!t
&& known_aggs
.length () > (unsigned int) param_index
2393 && !ie
->indirect_info
->by_ref
)
2395 struct ipa_agg_jump_function
*agg
;
2396 agg
= known_aggs
[param_index
];
2397 t
= ipa_find_agg_cst_for_param (agg
, known_csts
[param_index
],
2398 ie
->indirect_info
->offset
, true);
2401 /* If we found the virtual table pointer, lookup the target. */
2405 unsigned HOST_WIDE_INT offset
;
2406 if (vtable_pointer_value_to_vtable (t
, &vtable
, &offset
))
2409 target
= gimple_get_virt_method_for_vtable (ie
->indirect_info
->otr_token
,
2410 vtable
, offset
, &can_refer
);
2414 || (TREE_CODE (TREE_TYPE (target
)) == FUNCTION_TYPE
2415 && DECL_FUNCTION_CODE (target
) == BUILT_IN_UNREACHABLE
)
2416 || !possible_polymorphic_call_target_p
2417 (ie
, cgraph_node::get (target
)))
2419 /* Do not speculate builtin_unreachable, it is stupid! */
2420 if (ie
->indirect_info
->vptr_changed
)
2422 target
= ipa_impossible_devirt_target (ie
, target
);
2424 *speculative
= ie
->indirect_info
->vptr_changed
;
2431 /* Do we know the constant value of pointer? */
2433 t
= known_csts
[param_index
];
2435 gcc_checking_assert (!t
|| TREE_CODE (t
) != TREE_BINFO
);
2437 ipa_polymorphic_call_context context
;
2438 if (known_contexts
.length () > (unsigned int) param_index
)
2440 context
= known_contexts
[param_index
];
2441 context
.offset_by (anc_offset
);
2442 if (ie
->indirect_info
->vptr_changed
)
2443 context
.possible_dynamic_type_change (ie
->in_polymorphic_cdtor
,
2444 ie
->indirect_info
->otr_type
);
2447 ipa_polymorphic_call_context ctx2
= ipa_polymorphic_call_context
2448 (t
, ie
->indirect_info
->otr_type
, anc_offset
);
2449 if (!ctx2
.useless_p ())
2450 context
.combine_with (ctx2
, ie
->indirect_info
->otr_type
);
2455 context
= ipa_polymorphic_call_context (t
, ie
->indirect_info
->otr_type
,
2457 if (ie
->indirect_info
->vptr_changed
)
2458 context
.possible_dynamic_type_change (ie
->in_polymorphic_cdtor
,
2459 ie
->indirect_info
->otr_type
);
2464 vec
<cgraph_node
*>targets
;
2467 targets
= possible_polymorphic_call_targets
2468 (ie
->indirect_info
->otr_type
,
2469 ie
->indirect_info
->otr_token
,
2471 if (!final
|| targets
.length () > 1)
2473 struct cgraph_node
*node
;
2476 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize_speculatively
)
2477 || ie
->speculative
|| !ie
->maybe_hot_p ())
2479 node
= try_speculative_devirtualization (ie
->indirect_info
->otr_type
,
2480 ie
->indirect_info
->otr_token
,
2484 *speculative
= true;
2485 target
= node
->decl
;
2492 *speculative
= false;
2493 if (targets
.length () == 1)
2494 target
= targets
[0]->decl
;
2496 target
= ipa_impossible_devirt_target (ie
, NULL_TREE
);
2499 if (target
&& !possible_polymorphic_call_target_p (ie
,
2500 cgraph_node::get (target
)))
2504 target
= ipa_impossible_devirt_target (ie
, target
);
2511 /* If an indirect edge IE can be turned into a direct one based on KNOWN_CSTS,
2512 KNOWN_CONTEXTS (which can be vNULL) or KNOWN_AGGS (which also can be vNULL)
2513 return the destination. */
2516 ipa_get_indirect_edge_target (struct cgraph_edge
*ie
,
2517 vec
<tree
> known_csts
,
2518 vec
<ipa_polymorphic_call_context
> known_contexts
,
2519 vec
<ipa_agg_jump_function_p
> known_aggs
,
2522 return ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
2523 known_aggs
, NULL
, speculative
);
2526 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
2527 and KNOWN_CONTEXTS. */
2530 devirtualization_time_bonus (struct cgraph_node
*node
,
2531 vec
<tree
> known_csts
,
2532 vec
<ipa_polymorphic_call_context
> known_contexts
,
2533 vec
<ipa_agg_jump_function_p
> known_aggs
)
2535 struct cgraph_edge
*ie
;
2538 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
2540 struct cgraph_node
*callee
;
2541 struct ipa_fn_summary
*isummary
;
2542 enum availability avail
;
2546 target
= ipa_get_indirect_edge_target (ie
, known_csts
, known_contexts
,
2547 known_aggs
, &speculative
);
2551 /* Only bare minimum benefit for clearly un-inlineable targets. */
2553 callee
= cgraph_node::get (target
);
2554 if (!callee
|| !callee
->definition
)
2556 callee
= callee
->function_symbol (&avail
);
2557 if (avail
< AVAIL_AVAILABLE
)
2559 isummary
= ipa_fn_summaries
->get (callee
);
2560 if (!isummary
->inlinable
)
2563 /* FIXME: The values below need re-considering and perhaps also
2564 integrating into the cost metrics, at lest in some very basic way. */
2565 if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 4)
2566 res
+= 31 / ((int)speculative
+ 1);
2567 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 2)
2568 res
+= 15 / ((int)speculative
+ 1);
2569 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
2570 || DECL_DECLARED_INLINE_P (callee
->decl
))
2571 res
+= 7 / ((int)speculative
+ 1);
2577 /* Return time bonus incurred because of HINTS. */
2580 hint_time_bonus (ipa_hints hints
)
2583 if (hints
& (INLINE_HINT_loop_iterations
| INLINE_HINT_loop_stride
))
2584 result
+= PARAM_VALUE (PARAM_IPA_CP_LOOP_HINT_BONUS
);
2585 if (hints
& INLINE_HINT_array_index
)
2586 result
+= PARAM_VALUE (PARAM_IPA_CP_ARRAY_INDEX_HINT_BONUS
);
2590 /* If there is a reason to penalize the function described by INFO in the
2591 cloning goodness evaluation, do so. */
2593 static inline int64_t
2594 incorporate_penalties (ipa_node_params
*info
, int64_t evaluation
)
2596 if (info
->node_within_scc
)
2597 evaluation
= (evaluation
2598 * (100 - PARAM_VALUE (PARAM_IPA_CP_RECURSION_PENALTY
))) / 100;
2600 if (info
->node_calling_single_call
)
2601 evaluation
= (evaluation
2602 * (100 - PARAM_VALUE (PARAM_IPA_CP_SINGLE_CALL_PENALTY
)))
2608 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
2609 and SIZE_COST and with the sum of frequencies of incoming edges to the
2610 potential new clone in FREQUENCIES. */
2613 good_cloning_opportunity_p (struct cgraph_node
*node
, int time_benefit
,
2614 int freq_sum
, profile_count count_sum
, int size_cost
)
2616 if (time_benefit
== 0
2617 || !opt_for_fn (node
->decl
, flag_ipa_cp_clone
)
2618 || node
->optimize_for_size_p ())
2621 gcc_assert (size_cost
> 0);
2623 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2624 if (max_count
> profile_count::zero ())
2626 int factor
= RDIV (count_sum
.probability_in (max_count
)
2627 * 1000, REG_BR_PROB_BASE
);
2628 int64_t evaluation
= (((int64_t) time_benefit
* factor
)
2630 evaluation
= incorporate_penalties (info
, evaluation
);
2632 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2634 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
2635 "size: %i, count_sum: ", time_benefit
, size_cost
);
2636 count_sum
.dump (dump_file
);
2637 fprintf (dump_file
, "%s%s) -> evaluation: " "%" PRId64
2638 ", threshold: %i\n",
2639 info
->node_within_scc
? ", scc" : "",
2640 info
->node_calling_single_call
? ", single_call" : "",
2641 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
2644 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
2648 int64_t evaluation
= (((int64_t) time_benefit
* freq_sum
)
2650 evaluation
= incorporate_penalties (info
, evaluation
);
2652 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2653 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
2654 "size: %i, freq_sum: %i%s%s) -> evaluation: "
2655 "%" PRId64
", threshold: %i\n",
2656 time_benefit
, size_cost
, freq_sum
,
2657 info
->node_within_scc
? ", scc" : "",
2658 info
->node_calling_single_call
? ", single_call" : "",
2659 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
2661 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
2665 /* Return all context independent values from aggregate lattices in PLATS in a
2666 vector. Return NULL if there are none. */
2668 static vec
<ipa_agg_jf_item
, va_gc
> *
2669 context_independent_aggregate_values (struct ipcp_param_lattices
*plats
)
2671 vec
<ipa_agg_jf_item
, va_gc
> *res
= NULL
;
2673 if (plats
->aggs_bottom
2674 || plats
->aggs_contain_variable
2675 || plats
->aggs_count
== 0)
2678 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
;
2680 aglat
= aglat
->next
)
2681 if (aglat
->is_single_const ())
2683 struct ipa_agg_jf_item item
;
2684 item
.offset
= aglat
->offset
;
2685 item
.value
= aglat
->values
->value
;
2686 vec_safe_push (res
, item
);
2691 /* Allocate KNOWN_CSTS, KNOWN_CONTEXTS and, if non-NULL, KNOWN_AGGS and
2692 populate them with values of parameters that are known independent of the
2693 context. INFO describes the function. If REMOVABLE_PARAMS_COST is
2694 non-NULL, the movement cost of all removable parameters will be stored in
2698 gather_context_independent_values (struct ipa_node_params
*info
,
2699 vec
<tree
> *known_csts
,
2700 vec
<ipa_polymorphic_call_context
>
2702 vec
<ipa_agg_jump_function
> *known_aggs
,
2703 int *removable_params_cost
)
2705 int i
, count
= ipa_get_param_count (info
);
2708 known_csts
->create (0);
2709 known_contexts
->create (0);
2710 known_csts
->safe_grow_cleared (count
);
2711 known_contexts
->safe_grow_cleared (count
);
2714 known_aggs
->create (0);
2715 known_aggs
->safe_grow_cleared (count
);
2718 if (removable_params_cost
)
2719 *removable_params_cost
= 0;
2721 for (i
= 0; i
< count
; i
++)
2723 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2724 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
2726 if (lat
->is_single_const ())
2728 ipcp_value
<tree
> *val
= lat
->values
;
2729 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
2730 (*known_csts
)[i
] = val
->value
;
2731 if (removable_params_cost
)
2732 *removable_params_cost
2733 += estimate_move_cost (TREE_TYPE (val
->value
), false);
2736 else if (removable_params_cost
2737 && !ipa_is_param_used (info
, i
))
2738 *removable_params_cost
2739 += ipa_get_param_move_cost (info
, i
);
2741 if (!ipa_is_param_used (info
, i
))
2744 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
2745 /* Do not account known context as reason for cloning. We can see
2746 if it permits devirtualization. */
2747 if (ctxlat
->is_single_const ())
2748 (*known_contexts
)[i
] = ctxlat
->values
->value
;
2752 vec
<ipa_agg_jf_item
, va_gc
> *agg_items
;
2753 struct ipa_agg_jump_function
*ajf
;
2755 agg_items
= context_independent_aggregate_values (plats
);
2756 ajf
= &(*known_aggs
)[i
];
2757 ajf
->items
= agg_items
;
2758 ajf
->by_ref
= plats
->aggs_by_ref
;
2759 ret
|= agg_items
!= NULL
;
2766 /* The current interface in ipa-inline-analysis requires a pointer vector.
2769 FIXME: That interface should be re-worked, this is slightly silly. Still,
2770 I'd like to discuss how to change it first and this demonstrates the
2773 static vec
<ipa_agg_jump_function_p
>
2774 agg_jmp_p_vec_for_t_vec (vec
<ipa_agg_jump_function
> known_aggs
)
2776 vec
<ipa_agg_jump_function_p
> ret
;
2777 struct ipa_agg_jump_function
*ajf
;
2780 ret
.create (known_aggs
.length ());
2781 FOR_EACH_VEC_ELT (known_aggs
, i
, ajf
)
2782 ret
.quick_push (ajf
);
2786 /* Perform time and size measurement of NODE with the context given in
2787 KNOWN_CSTS, KNOWN_CONTEXTS and KNOWN_AGGS, calculate the benefit and cost
2788 given BASE_TIME of the node without specialization, REMOVABLE_PARAMS_COST of
2789 all context-independent removable parameters and EST_MOVE_COST of estimated
2790 movement of the considered parameter and store it into VAL. */
2793 perform_estimation_of_a_value (cgraph_node
*node
, vec
<tree
> known_csts
,
2794 vec
<ipa_polymorphic_call_context
> known_contexts
,
2795 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
,
2796 int removable_params_cost
,
2797 int est_move_cost
, ipcp_value_base
*val
)
2799 int size
, time_benefit
;
2800 sreal time
, base_time
;
2803 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
2804 known_aggs_ptrs
, &size
, &time
,
2805 &base_time
, &hints
);
2807 if (base_time
> 65535)
2809 time_benefit
= base_time
.to_int ()
2810 + devirtualization_time_bonus (node
, known_csts
, known_contexts
,
2812 + hint_time_bonus (hints
)
2813 + removable_params_cost
+ est_move_cost
;
2815 gcc_checking_assert (size
>=0);
2816 /* The inliner-heuristics based estimates may think that in certain
2817 contexts some functions do not have any size at all but we want
2818 all specializations to have at least a tiny cost, not least not to
2823 val
->local_time_benefit
= time_benefit
;
2824 val
->local_size_cost
= size
;
2827 /* Iterate over known values of parameters of NODE and estimate the local
2828 effects in terms of time and size they have. */
2831 estimate_local_effects (struct cgraph_node
*node
)
2833 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2834 int i
, count
= ipa_get_param_count (info
);
2835 vec
<tree
> known_csts
;
2836 vec
<ipa_polymorphic_call_context
> known_contexts
;
2837 vec
<ipa_agg_jump_function
> known_aggs
;
2838 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
;
2840 int removable_params_cost
;
2842 if (!count
|| !ipcp_versionable_function_p (node
))
2845 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2846 fprintf (dump_file
, "\nEstimating effects for %s.\n", node
->dump_name ());
2848 always_const
= gather_context_independent_values (info
, &known_csts
,
2849 &known_contexts
, &known_aggs
,
2850 &removable_params_cost
);
2851 known_aggs_ptrs
= agg_jmp_p_vec_for_t_vec (known_aggs
);
2852 int devirt_bonus
= devirtualization_time_bonus (node
, known_csts
,
2853 known_contexts
, known_aggs_ptrs
);
2854 if (always_const
|| devirt_bonus
2855 || (removable_params_cost
&& node
->local
.can_change_signature
))
2857 struct caller_statistics stats
;
2859 sreal time
, base_time
;
2862 init_caller_stats (&stats
);
2863 node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
2865 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
2866 known_aggs_ptrs
, &size
, &time
,
2867 &base_time
, &hints
);
2868 time
-= devirt_bonus
;
2869 time
-= hint_time_bonus (hints
);
2870 time
-= removable_params_cost
;
2871 size
-= stats
.n_calls
* removable_params_cost
;
2874 fprintf (dump_file
, " - context independent values, size: %i, "
2875 "time_benefit: %f\n", size
, (base_time
- time
).to_double ());
2877 if (size
<= 0 || node
->local
.local
)
2879 info
->do_clone_for_all_contexts
= true;
2882 fprintf (dump_file
, " Decided to specialize for all "
2883 "known contexts, code not going to grow.\n");
2885 else if (good_cloning_opportunity_p (node
,
2886 MAX ((base_time
- time
).to_int (),
2888 stats
.freq_sum
, stats
.count_sum
,
2891 if (size
+ overall_size
<= max_new_size
)
2893 info
->do_clone_for_all_contexts
= true;
2894 overall_size
+= size
;
2897 fprintf (dump_file
, " Decided to specialize for all "
2898 "known contexts, growth deemed beneficial.\n");
2900 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2901 fprintf (dump_file
, " Not cloning for all contexts because "
2902 "max_new_size would be reached with %li.\n",
2903 size
+ overall_size
);
2905 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2906 fprintf (dump_file
, " Not cloning for all contexts because "
2907 "!good_cloning_opportunity_p.\n");
2911 for (i
= 0; i
< count
; i
++)
2913 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2914 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
2915 ipcp_value
<tree
> *val
;
2922 for (val
= lat
->values
; val
; val
= val
->next
)
2924 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
2925 known_csts
[i
] = val
->value
;
2927 int emc
= estimate_move_cost (TREE_TYPE (val
->value
), true);
2928 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
2930 removable_params_cost
, emc
, val
);
2932 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2934 fprintf (dump_file
, " - estimates for value ");
2935 print_ipcp_constant_value (dump_file
, val
->value
);
2936 fprintf (dump_file
, " for ");
2937 ipa_dump_param (dump_file
, info
, i
);
2938 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
2939 val
->local_time_benefit
, val
->local_size_cost
);
2942 known_csts
[i
] = NULL_TREE
;
2945 for (i
= 0; i
< count
; i
++)
2947 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2949 if (!plats
->virt_call
)
2952 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
2953 ipcp_value
<ipa_polymorphic_call_context
> *val
;
2957 || !known_contexts
[i
].useless_p ())
2960 for (val
= ctxlat
->values
; val
; val
= val
->next
)
2962 known_contexts
[i
] = val
->value
;
2963 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
2965 removable_params_cost
, 0, val
);
2967 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2969 fprintf (dump_file
, " - estimates for polymorphic context ");
2970 print_ipcp_constant_value (dump_file
, val
->value
);
2971 fprintf (dump_file
, " for ");
2972 ipa_dump_param (dump_file
, info
, i
);
2973 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
2974 val
->local_time_benefit
, val
->local_size_cost
);
2977 known_contexts
[i
] = ipa_polymorphic_call_context ();
2980 for (i
= 0; i
< count
; i
++)
2982 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2983 struct ipa_agg_jump_function
*ajf
;
2984 struct ipcp_agg_lattice
*aglat
;
2986 if (plats
->aggs_bottom
|| !plats
->aggs
)
2989 ajf
= &known_aggs
[i
];
2990 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2992 ipcp_value
<tree
> *val
;
2993 if (aglat
->bottom
|| !aglat
->values
2994 /* If the following is true, the one value is in known_aggs. */
2995 || (!plats
->aggs_contain_variable
2996 && aglat
->is_single_const ()))
2999 for (val
= aglat
->values
; val
; val
= val
->next
)
3001 struct ipa_agg_jf_item item
;
3003 item
.offset
= aglat
->offset
;
3004 item
.value
= val
->value
;
3005 vec_safe_push (ajf
->items
, item
);
3007 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
3009 removable_params_cost
, 0, val
);
3011 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3013 fprintf (dump_file
, " - estimates for value ");
3014 print_ipcp_constant_value (dump_file
, val
->value
);
3015 fprintf (dump_file
, " for ");
3016 ipa_dump_param (dump_file
, info
, i
);
3017 fprintf (dump_file
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
3018 "]: time_benefit: %i, size: %i\n",
3019 plats
->aggs_by_ref
? "ref " : "",
3021 val
->local_time_benefit
, val
->local_size_cost
);
3029 for (i
= 0; i
< count
; i
++)
3030 vec_free (known_aggs
[i
].items
);
3032 known_csts
.release ();
3033 known_contexts
.release ();
3034 known_aggs
.release ();
3035 known_aggs_ptrs
.release ();
3039 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
3040 topological sort of values. */
3042 template <typename valtype
>
3044 value_topo_info
<valtype
>::add_val (ipcp_value
<valtype
> *cur_val
)
3046 ipcp_value_source
<valtype
> *src
;
3052 cur_val
->dfs
= dfs_counter
;
3053 cur_val
->low_link
= dfs_counter
;
3055 cur_val
->topo_next
= stack
;
3057 cur_val
->on_stack
= true;
3059 for (src
= cur_val
->sources
; src
; src
= src
->next
)
3062 if (src
->val
->dfs
== 0)
3065 if (src
->val
->low_link
< cur_val
->low_link
)
3066 cur_val
->low_link
= src
->val
->low_link
;
3068 else if (src
->val
->on_stack
3069 && src
->val
->dfs
< cur_val
->low_link
)
3070 cur_val
->low_link
= src
->val
->dfs
;
3073 if (cur_val
->dfs
== cur_val
->low_link
)
3075 ipcp_value
<valtype
> *v
, *scc_list
= NULL
;
3080 stack
= v
->topo_next
;
3081 v
->on_stack
= false;
3083 v
->scc_next
= scc_list
;
3086 while (v
!= cur_val
);
3088 cur_val
->topo_next
= values_topo
;
3089 values_topo
= cur_val
;
3093 /* Add all values in lattices associated with NODE to the topological sort if
3094 they are not there yet. */
3097 add_all_node_vals_to_toposort (cgraph_node
*node
, ipa_topo_info
*topo
)
3099 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3100 int i
, count
= ipa_get_param_count (info
);
3102 for (i
= 0; i
< count
; i
++)
3104 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3105 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
3106 struct ipcp_agg_lattice
*aglat
;
3110 ipcp_value
<tree
> *val
;
3111 for (val
= lat
->values
; val
; val
= val
->next
)
3112 topo
->constants
.add_val (val
);
3115 if (!plats
->aggs_bottom
)
3116 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3119 ipcp_value
<tree
> *val
;
3120 for (val
= aglat
->values
; val
; val
= val
->next
)
3121 topo
->constants
.add_val (val
);
3124 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
3125 if (!ctxlat
->bottom
)
3127 ipcp_value
<ipa_polymorphic_call_context
> *ctxval
;
3128 for (ctxval
= ctxlat
->values
; ctxval
; ctxval
= ctxval
->next
)
3129 topo
->contexts
.add_val (ctxval
);
3134 /* One pass of constants propagation along the call graph edges, from callers
3135 to callees (requires topological ordering in TOPO), iterate over strongly
3136 connected components. */
3139 propagate_constants_topo (struct ipa_topo_info
*topo
)
3143 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
3146 struct cgraph_node
*v
, *node
= topo
->order
[i
];
3147 vec
<cgraph_node
*> cycle_nodes
= ipa_get_nodes_in_cycle (node
);
3149 /* First, iteratively propagate within the strongly connected component
3150 until all lattices stabilize. */
3151 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
3152 if (v
->has_gimple_body_p ())
3153 push_node_to_stack (topo
, v
);
3155 v
= pop_node_from_stack (topo
);
3158 struct cgraph_edge
*cs
;
3160 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3161 if (ipa_edge_within_scc (cs
))
3163 IPA_NODE_REF (v
)->node_within_scc
= true;
3164 if (propagate_constants_across_call (cs
))
3165 push_node_to_stack (topo
, cs
->callee
->function_symbol ());
3167 v
= pop_node_from_stack (topo
);
3170 /* Afterwards, propagate along edges leading out of the SCC, calculates
3171 the local effects of the discovered constants and all valid values to
3172 their topological sort. */
3173 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
3174 if (v
->has_gimple_body_p ())
3176 struct cgraph_edge
*cs
;
3178 estimate_local_effects (v
);
3179 add_all_node_vals_to_toposort (v
, topo
);
3180 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3181 if (!ipa_edge_within_scc (cs
))
3182 propagate_constants_across_call (cs
);
3184 cycle_nodes
.release ();
3189 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
3190 the bigger one if otherwise. */
3193 safe_add (int a
, int b
)
3195 if (a
> INT_MAX
/2 || b
> INT_MAX
/2)
3196 return a
> b
? a
: b
;
3202 /* Propagate the estimated effects of individual values along the topological
3203 from the dependent values to those they depend on. */
3205 template <typename valtype
>
3207 value_topo_info
<valtype
>::propagate_effects ()
3209 ipcp_value
<valtype
> *base
;
3211 for (base
= values_topo
; base
; base
= base
->topo_next
)
3213 ipcp_value_source
<valtype
> *src
;
3214 ipcp_value
<valtype
> *val
;
3215 int time
= 0, size
= 0;
3217 for (val
= base
; val
; val
= val
->scc_next
)
3219 time
= safe_add (time
,
3220 val
->local_time_benefit
+ val
->prop_time_benefit
);
3221 size
= safe_add (size
, val
->local_size_cost
+ val
->prop_size_cost
);
3224 for (val
= base
; val
; val
= val
->scc_next
)
3225 for (src
= val
->sources
; src
; src
= src
->next
)
3227 && src
->cs
->maybe_hot_p ())
3229 src
->val
->prop_time_benefit
= safe_add (time
,
3230 src
->val
->prop_time_benefit
);
3231 src
->val
->prop_size_cost
= safe_add (size
,
3232 src
->val
->prop_size_cost
);
3238 /* Propagate constants, polymorphic contexts and their effects from the
3239 summaries interprocedurally. */
3242 ipcp_propagate_stage (struct ipa_topo_info
*topo
)
3244 struct cgraph_node
*node
;
3247 fprintf (dump_file
, "\n Propagating constants:\n\n");
3249 FOR_EACH_DEFINED_FUNCTION (node
)
3251 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3253 determine_versionability (node
, info
);
3254 if (node
->has_gimple_body_p ())
3256 info
->lattices
= XCNEWVEC (struct ipcp_param_lattices
,
3257 ipa_get_param_count (info
));
3258 initialize_node_lattices (node
);
3260 if (node
->definition
&& !node
->alias
)
3261 overall_size
+= ipa_fn_summaries
->get (node
)->self_size
;
3262 if (node
->count
> max_count
)
3263 max_count
= node
->count
;
3266 max_new_size
= overall_size
;
3267 if (max_new_size
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
3268 max_new_size
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
3269 max_new_size
+= max_new_size
* PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH
) / 100 + 1;
3272 fprintf (dump_file
, "\noverall_size: %li, max_new_size: %li\n",
3273 overall_size
, max_new_size
);
3275 propagate_constants_topo (topo
);
3277 ipcp_verify_propagated_values ();
3278 topo
->constants
.propagate_effects ();
3279 topo
->contexts
.propagate_effects ();
3283 fprintf (dump_file
, "\nIPA lattices after all propagation:\n");
3284 print_all_lattices (dump_file
, (dump_flags
& TDF_DETAILS
), true);
3288 /* Discover newly direct outgoing edges from NODE which is a new clone with
3289 known KNOWN_CSTS and make them direct. */
3292 ipcp_discover_new_direct_edges (struct cgraph_node
*node
,
3293 vec
<tree
> known_csts
,
3294 vec
<ipa_polymorphic_call_context
>
3296 struct ipa_agg_replacement_value
*aggvals
)
3298 struct cgraph_edge
*ie
, *next_ie
;
3301 for (ie
= node
->indirect_calls
; ie
; ie
= next_ie
)
3306 next_ie
= ie
->next_callee
;
3307 target
= ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
3308 vNULL
, aggvals
, &speculative
);
3311 bool agg_contents
= ie
->indirect_info
->agg_contents
;
3312 bool polymorphic
= ie
->indirect_info
->polymorphic
;
3313 int param_index
= ie
->indirect_info
->param_index
;
3314 struct cgraph_edge
*cs
= ipa_make_edge_direct_to_target (ie
, target
,
3318 if (cs
&& !agg_contents
&& !polymorphic
)
3320 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3321 int c
= ipa_get_controlled_uses (info
, param_index
);
3322 if (c
!= IPA_UNDESCRIBED_USE
)
3324 struct ipa_ref
*to_del
;
3327 ipa_set_controlled_uses (info
, param_index
, c
);
3328 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3329 fprintf (dump_file
, " controlled uses count of param "
3330 "%i bumped down to %i\n", param_index
, c
);
3332 && (to_del
= node
->find_reference (cs
->callee
, NULL
, 0)))
3334 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3335 fprintf (dump_file
, " and even removing its "
3336 "cloning-created reference\n");
3337 to_del
->remove_reference ();
3343 /* Turning calls to direct calls will improve overall summary. */
3345 ipa_update_overall_fn_summary (node
);
3348 /* Vector of pointers which for linked lists of clones of an original crgaph
3351 static vec
<cgraph_edge
*> next_edge_clone
;
3352 static vec
<cgraph_edge
*> prev_edge_clone
;
3355 grow_edge_clone_vectors (void)
3357 if (next_edge_clone
.length ()
3358 <= (unsigned) symtab
->edges_max_uid
)
3359 next_edge_clone
.safe_grow_cleared (symtab
->edges_max_uid
+ 1);
3360 if (prev_edge_clone
.length ()
3361 <= (unsigned) symtab
->edges_max_uid
)
3362 prev_edge_clone
.safe_grow_cleared (symtab
->edges_max_uid
+ 1);
3365 /* Edge duplication hook to grow the appropriate linked list in
3369 ipcp_edge_duplication_hook (struct cgraph_edge
*src
, struct cgraph_edge
*dst
,
3372 grow_edge_clone_vectors ();
3374 struct cgraph_edge
*old_next
= next_edge_clone
[src
->uid
];
3376 prev_edge_clone
[old_next
->uid
] = dst
;
3377 prev_edge_clone
[dst
->uid
] = src
;
3379 next_edge_clone
[dst
->uid
] = old_next
;
3380 next_edge_clone
[src
->uid
] = dst
;
3383 /* Hook that is called by cgraph.c when an edge is removed. */
3386 ipcp_edge_removal_hook (struct cgraph_edge
*cs
, void *)
3388 grow_edge_clone_vectors ();
3390 struct cgraph_edge
*prev
= prev_edge_clone
[cs
->uid
];
3391 struct cgraph_edge
*next
= next_edge_clone
[cs
->uid
];
3393 next_edge_clone
[prev
->uid
] = next
;
3395 prev_edge_clone
[next
->uid
] = prev
;
3398 /* See if NODE is a clone with a known aggregate value at a given OFFSET of a
3399 parameter with the given INDEX. */
3402 get_clone_agg_value (struct cgraph_node
*node
, HOST_WIDE_INT offset
,
3405 struct ipa_agg_replacement_value
*aggval
;
3407 aggval
= ipa_get_agg_replacements_for_node (node
);
3410 if (aggval
->offset
== offset
3411 && aggval
->index
== index
)
3412 return aggval
->value
;
3413 aggval
= aggval
->next
;
3418 /* Return true is NODE is DEST or its clone for all contexts. */
3421 same_node_or_its_all_contexts_clone_p (cgraph_node
*node
, cgraph_node
*dest
)
3426 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3427 return info
->is_all_contexts_clone
&& info
->ipcp_orig_node
== dest
;
3430 /* Return true if edge CS does bring about the value described by SRC to node
3431 DEST or its clone for all contexts. */
3434 cgraph_edge_brings_value_p (cgraph_edge
*cs
, ipcp_value_source
<tree
> *src
,
3437 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3438 enum availability availability
;
3439 cgraph_node
*real_dest
= cs
->callee
->function_symbol (&availability
);
3441 if (!same_node_or_its_all_contexts_clone_p (real_dest
, dest
)
3442 || availability
<= AVAIL_INTERPOSABLE
3443 || caller_info
->node_dead
)
3448 if (caller_info
->ipcp_orig_node
)
3451 if (src
->offset
== -1)
3452 t
= caller_info
->known_csts
[src
->index
];
3454 t
= get_clone_agg_value (cs
->caller
, src
->offset
, src
->index
);
3455 return (t
!= NULL_TREE
3456 && values_equal_for_ipcp_p (src
->val
->value
, t
));
3460 struct ipcp_agg_lattice
*aglat
;
3461 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
3463 if (src
->offset
== -1)
3464 return (plats
->itself
.is_single_const ()
3465 && values_equal_for_ipcp_p (src
->val
->value
,
3466 plats
->itself
.values
->value
));
3469 if (plats
->aggs_bottom
|| plats
->aggs_contain_variable
)
3471 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3472 if (aglat
->offset
== src
->offset
)
3473 return (aglat
->is_single_const ()
3474 && values_equal_for_ipcp_p (src
->val
->value
,
3475 aglat
->values
->value
));
3481 /* Return true if edge CS does bring about the value described by SRC to node
3482 DEST or its clone for all contexts. */
3485 cgraph_edge_brings_value_p (cgraph_edge
*cs
,
3486 ipcp_value_source
<ipa_polymorphic_call_context
> *src
,
3489 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3490 cgraph_node
*real_dest
= cs
->callee
->function_symbol ();
3492 if (!same_node_or_its_all_contexts_clone_p (real_dest
, dest
)
3493 || caller_info
->node_dead
)
3498 if (caller_info
->ipcp_orig_node
)
3499 return (caller_info
->known_contexts
.length () > (unsigned) src
->index
)
3500 && values_equal_for_ipcp_p (src
->val
->value
,
3501 caller_info
->known_contexts
[src
->index
]);
3503 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
3505 return plats
->ctxlat
.is_single_const ()
3506 && values_equal_for_ipcp_p (src
->val
->value
,
3507 plats
->ctxlat
.values
->value
);
3510 /* Get the next clone in the linked list of clones of an edge. */
3512 static inline struct cgraph_edge
*
3513 get_next_cgraph_edge_clone (struct cgraph_edge
*cs
)
3515 return next_edge_clone
[cs
->uid
];
3518 /* Given VAL that is intended for DEST, iterate over all its sources and if
3519 they still hold, add their edge frequency and their number into *FREQUENCY
3520 and *CALLER_COUNT respectively. */
3522 template <typename valtype
>
3524 get_info_about_necessary_edges (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
3526 profile_count
*count_sum
, int *caller_count
)
3528 ipcp_value_source
<valtype
> *src
;
3529 int freq
= 0, count
= 0;
3530 profile_count cnt
= profile_count::zero ();
3533 for (src
= val
->sources
; src
; src
= src
->next
)
3535 struct cgraph_edge
*cs
= src
->cs
;
3538 if (cgraph_edge_brings_value_p (cs
, src
, dest
))
3541 freq
+= cs
->frequency
;
3542 if (cs
->count
.initialized_p ())
3544 hot
|= cs
->maybe_hot_p ();
3546 cs
= get_next_cgraph_edge_clone (cs
);
3552 *caller_count
= count
;
3556 /* Return a vector of incoming edges that do bring value VAL to node DEST. It
3557 is assumed their number is known and equal to CALLER_COUNT. */
3559 template <typename valtype
>
3560 static vec
<cgraph_edge
*>
3561 gather_edges_for_value (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
3564 ipcp_value_source
<valtype
> *src
;
3565 vec
<cgraph_edge
*> ret
;
3567 ret
.create (caller_count
);
3568 for (src
= val
->sources
; src
; src
= src
->next
)
3570 struct cgraph_edge
*cs
= src
->cs
;
3573 if (cgraph_edge_brings_value_p (cs
, src
, dest
))
3574 ret
.quick_push (cs
);
3575 cs
= get_next_cgraph_edge_clone (cs
);
3582 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
3583 Return it or NULL if for some reason it cannot be created. */
3585 static struct ipa_replace_map
*
3586 get_replacement_map (struct ipa_node_params
*info
, tree value
, int parm_num
)
3588 struct ipa_replace_map
*replace_map
;
3591 replace_map
= ggc_alloc
<ipa_replace_map
> ();
3594 fprintf (dump_file
, " replacing ");
3595 ipa_dump_param (dump_file
, info
, parm_num
);
3597 fprintf (dump_file
, " with const ");
3598 print_generic_expr (dump_file
, value
);
3599 fprintf (dump_file
, "\n");
3601 replace_map
->old_tree
= NULL
;
3602 replace_map
->parm_num
= parm_num
;
3603 replace_map
->new_tree
= value
;
3604 replace_map
->replace_p
= true;
3605 replace_map
->ref_p
= false;
3610 /* Dump new profiling counts */
3613 dump_profile_updates (struct cgraph_node
*orig_node
,
3614 struct cgraph_node
*new_node
)
3616 struct cgraph_edge
*cs
;
3618 fprintf (dump_file
, " setting count of the specialized node to ");
3619 new_node
->count
.dump (dump_file
);
3620 fprintf (dump_file
, "\n");
3621 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3623 fprintf (dump_file
, " edge to %s has count ",
3624 cs
->callee
->name ());
3625 cs
->count
.dump (dump_file
);
3626 fprintf (dump_file
, "\n");
3629 fprintf (dump_file
, " setting count of the original node to ");
3630 orig_node
->count
.dump (dump_file
);
3631 fprintf (dump_file
, "\n");
3632 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3634 fprintf (dump_file
, " edge to %s is left with ",
3635 cs
->callee
->name ());
3636 cs
->count
.dump (dump_file
);
3637 fprintf (dump_file
, "\n");
3641 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
3642 their profile information to reflect this. */
3645 update_profiling_info (struct cgraph_node
*orig_node
,
3646 struct cgraph_node
*new_node
)
3648 struct cgraph_edge
*cs
;
3649 struct caller_statistics stats
;
3650 profile_count new_sum
, orig_sum
;
3651 profile_count remainder
, orig_node_count
= orig_node
->count
;
3653 if (!(orig_node_count
> profile_count::zero ()))
3656 init_caller_stats (&stats
);
3657 orig_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
3659 orig_sum
= stats
.count_sum
;
3660 init_caller_stats (&stats
);
3661 new_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
3663 new_sum
= stats
.count_sum
;
3665 if (orig_node_count
< orig_sum
+ new_sum
)
3669 fprintf (dump_file
, " Problem: node %s has too low count ",
3670 orig_node
->dump_name ());
3671 orig_node_count
.dump (dump_file
);
3672 fprintf (dump_file
, "while the sum of incoming count is ");
3673 (orig_sum
+ new_sum
).dump (dump_file
);
3674 fprintf (dump_file
, "\n");
3677 orig_node_count
= (orig_sum
+ new_sum
).apply_scale (12, 10);
3680 fprintf (dump_file
, " proceeding by pretending it was ");
3681 orig_node_count
.dump (dump_file
);
3682 fprintf (dump_file
, "\n");
3686 new_node
->count
= new_sum
;
3687 remainder
= orig_node_count
- new_sum
;
3688 orig_node
->count
= remainder
;
3690 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3691 /* FIXME: why we care about non-zero frequency here? */
3693 cs
->count
= cs
->count
.apply_scale (new_sum
, orig_node_count
);
3695 cs
->count
= profile_count::zero ();
3697 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3698 cs
->count
= cs
->count
.apply_scale (remainder
, orig_node_count
);
3701 dump_profile_updates (orig_node
, new_node
);
3704 /* Update the respective profile of specialized NEW_NODE and the original
3705 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
3706 have been redirected to the specialized version. */
3709 update_specialized_profile (struct cgraph_node
*new_node
,
3710 struct cgraph_node
*orig_node
,
3711 profile_count redirected_sum
)
3713 struct cgraph_edge
*cs
;
3714 profile_count new_node_count
, orig_node_count
= orig_node
->count
;
3718 fprintf (dump_file
, " the sum of counts of redirected edges is ");
3719 redirected_sum
.dump (dump_file
);
3720 fprintf (dump_file
, "\n");
3722 if (!(orig_node_count
> profile_count::zero ()))
3725 gcc_assert (orig_node_count
>= redirected_sum
);
3727 new_node_count
= new_node
->count
;
3728 new_node
->count
+= redirected_sum
;
3729 orig_node
->count
-= redirected_sum
;
3731 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3733 cs
->count
+= cs
->count
.apply_scale (redirected_sum
, new_node_count
);
3735 cs
->count
= profile_count::zero ();
3737 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3739 profile_count dec
= cs
->count
.apply_scale (redirected_sum
,
3745 dump_profile_updates (orig_node
, new_node
);
3748 /* Create a specialized version of NODE with known constants in KNOWN_CSTS,
3749 known contexts in KNOWN_CONTEXTS and known aggregate values in AGGVALS and
3750 redirect all edges in CALLERS to it. */
3752 static struct cgraph_node
*
3753 create_specialized_node (struct cgraph_node
*node
,
3754 vec
<tree
> known_csts
,
3755 vec
<ipa_polymorphic_call_context
> known_contexts
,
3756 struct ipa_agg_replacement_value
*aggvals
,
3757 vec
<cgraph_edge
*> callers
)
3759 struct ipa_node_params
*new_info
, *info
= IPA_NODE_REF (node
);
3760 vec
<ipa_replace_map
*, va_gc
> *replace_trees
= NULL
;
3761 struct ipa_agg_replacement_value
*av
;
3762 struct cgraph_node
*new_node
;
3763 int i
, count
= ipa_get_param_count (info
);
3764 bitmap args_to_skip
;
3766 gcc_assert (!info
->ipcp_orig_node
);
3768 if (node
->local
.can_change_signature
)
3770 args_to_skip
= BITMAP_GGC_ALLOC ();
3771 for (i
= 0; i
< count
; i
++)
3773 tree t
= known_csts
[i
];
3775 if (t
|| !ipa_is_param_used (info
, i
))
3776 bitmap_set_bit (args_to_skip
, i
);
3781 args_to_skip
= NULL
;
3782 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3783 fprintf (dump_file
, " cannot change function signature\n");
3786 for (i
= 0; i
< count
; i
++)
3788 tree t
= known_csts
[i
];
3791 struct ipa_replace_map
*replace_map
;
3793 gcc_checking_assert (TREE_CODE (t
) != TREE_BINFO
);
3794 replace_map
= get_replacement_map (info
, t
, i
);
3796 vec_safe_push (replace_trees
, replace_map
);
3800 new_node
= node
->create_virtual_clone (callers
, replace_trees
,
3801 args_to_skip
, "constprop");
3802 ipa_set_node_agg_value_chain (new_node
, aggvals
);
3803 for (av
= aggvals
; av
; av
= av
->next
)
3804 new_node
->maybe_create_reference (av
->value
, NULL
);
3806 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3808 fprintf (dump_file
, " the new node is %s.\n", new_node
->dump_name ());
3809 if (known_contexts
.exists ())
3811 for (i
= 0; i
< count
; i
++)
3812 if (!known_contexts
[i
].useless_p ())
3814 fprintf (dump_file
, " known ctx %i is ", i
);
3815 known_contexts
[i
].dump (dump_file
);
3819 ipa_dump_agg_replacement_values (dump_file
, aggvals
);
3821 ipa_check_create_node_params ();
3822 update_profiling_info (node
, new_node
);
3823 new_info
= IPA_NODE_REF (new_node
);
3824 new_info
->ipcp_orig_node
= node
;
3825 new_info
->known_csts
= known_csts
;
3826 new_info
->known_contexts
= known_contexts
;
3828 ipcp_discover_new_direct_edges (new_node
, known_csts
, known_contexts
, aggvals
);
3834 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
3835 KNOWN_CSTS with constants that are also known for all of the CALLERS. */
3838 find_more_scalar_values_for_callers_subset (struct cgraph_node
*node
,
3839 vec
<tree
> known_csts
,
3840 vec
<cgraph_edge
*> callers
)
3842 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3843 int i
, count
= ipa_get_param_count (info
);
3845 for (i
= 0; i
< count
; i
++)
3847 struct cgraph_edge
*cs
;
3848 tree newval
= NULL_TREE
;
3852 if (ipa_get_scalar_lat (info
, i
)->bottom
|| known_csts
[i
])
3855 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3857 struct ipa_jump_func
*jump_func
;
3860 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
))
3862 && call_passes_through_thunk_p (cs
))
3863 || (!cs
->callee
->instrumentation_clone
3864 && cs
->callee
->function_symbol ()->instrumentation_clone
))
3869 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
3870 t
= ipa_value_from_jfunc (IPA_NODE_REF (cs
->caller
), jump_func
);
3873 && !values_equal_for_ipcp_p (t
, newval
))
3874 || (!first
&& !newval
))
3886 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3888 fprintf (dump_file
, " adding an extra known scalar value ");
3889 print_ipcp_constant_value (dump_file
, newval
);
3890 fprintf (dump_file
, " for ");
3891 ipa_dump_param (dump_file
, info
, i
);
3892 fprintf (dump_file
, "\n");
3895 known_csts
[i
] = newval
;
3900 /* Given a NODE and a subset of its CALLERS, try to populate plank slots in
3901 KNOWN_CONTEXTS with polymorphic contexts that are also known for all of the
3905 find_more_contexts_for_caller_subset (cgraph_node
*node
,
3906 vec
<ipa_polymorphic_call_context
>
3908 vec
<cgraph_edge
*> callers
)
3910 ipa_node_params
*info
= IPA_NODE_REF (node
);
3911 int i
, count
= ipa_get_param_count (info
);
3913 for (i
= 0; i
< count
; i
++)
3917 if (ipa_get_poly_ctx_lat (info
, i
)->bottom
3918 || (known_contexts
->exists ()
3919 && !(*known_contexts
)[i
].useless_p ()))
3922 ipa_polymorphic_call_context newval
;
3926 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3928 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
)))
3930 ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
),
3932 ipa_polymorphic_call_context ctx
;
3933 ctx
= ipa_context_from_jfunc (IPA_NODE_REF (cs
->caller
), cs
, i
,
3941 newval
.meet_with (ctx
);
3942 if (newval
.useless_p ())
3946 if (!newval
.useless_p ())
3948 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3950 fprintf (dump_file
, " adding an extra known polymorphic "
3952 print_ipcp_constant_value (dump_file
, newval
);
3953 fprintf (dump_file
, " for ");
3954 ipa_dump_param (dump_file
, info
, i
);
3955 fprintf (dump_file
, "\n");
3958 if (!known_contexts
->exists ())
3959 known_contexts
->safe_grow_cleared (ipa_get_param_count (info
));
3960 (*known_contexts
)[i
] = newval
;
3966 /* Go through PLATS and create a vector of values consisting of values and
3967 offsets (minus OFFSET) of lattices that contain only a single value. */
3969 static vec
<ipa_agg_jf_item
>
3970 copy_plats_to_inter (struct ipcp_param_lattices
*plats
, HOST_WIDE_INT offset
)
3972 vec
<ipa_agg_jf_item
> res
= vNULL
;
3974 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
3977 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3978 if (aglat
->is_single_const ())
3980 struct ipa_agg_jf_item ti
;
3981 ti
.offset
= aglat
->offset
- offset
;
3982 ti
.value
= aglat
->values
->value
;
3988 /* Intersect all values in INTER with single value lattices in PLATS (while
3989 subtracting OFFSET). */
3992 intersect_with_plats (struct ipcp_param_lattices
*plats
,
3993 vec
<ipa_agg_jf_item
> *inter
,
3994 HOST_WIDE_INT offset
)
3996 struct ipcp_agg_lattice
*aglat
;
3997 struct ipa_agg_jf_item
*item
;
4000 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
4006 aglat
= plats
->aggs
;
4007 FOR_EACH_VEC_ELT (*inter
, k
, item
)
4014 if (aglat
->offset
- offset
> item
->offset
)
4016 if (aglat
->offset
- offset
== item
->offset
)
4018 gcc_checking_assert (item
->value
);
4019 if (values_equal_for_ipcp_p (item
->value
, aglat
->values
->value
))
4023 aglat
= aglat
->next
;
4026 item
->value
= NULL_TREE
;
4030 /* Copy aggregate replacement values of NODE (which is an IPA-CP clone) to the
4031 vector result while subtracting OFFSET from the individual value offsets. */
4033 static vec
<ipa_agg_jf_item
>
4034 agg_replacements_to_vector (struct cgraph_node
*node
, int index
,
4035 HOST_WIDE_INT offset
)
4037 struct ipa_agg_replacement_value
*av
;
4038 vec
<ipa_agg_jf_item
> res
= vNULL
;
4040 for (av
= ipa_get_agg_replacements_for_node (node
); av
; av
= av
->next
)
4041 if (av
->index
== index
4042 && (av
->offset
- offset
) >= 0)
4044 struct ipa_agg_jf_item item
;
4045 gcc_checking_assert (av
->value
);
4046 item
.offset
= av
->offset
- offset
;
4047 item
.value
= av
->value
;
4048 res
.safe_push (item
);
4054 /* Intersect all values in INTER with those that we have already scheduled to
4055 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
4056 (while subtracting OFFSET). */
4059 intersect_with_agg_replacements (struct cgraph_node
*node
, int index
,
4060 vec
<ipa_agg_jf_item
> *inter
,
4061 HOST_WIDE_INT offset
)
4063 struct ipa_agg_replacement_value
*srcvals
;
4064 struct ipa_agg_jf_item
*item
;
4067 srcvals
= ipa_get_agg_replacements_for_node (node
);
4074 FOR_EACH_VEC_ELT (*inter
, i
, item
)
4076 struct ipa_agg_replacement_value
*av
;
4080 for (av
= srcvals
; av
; av
= av
->next
)
4082 gcc_checking_assert (av
->value
);
4083 if (av
->index
== index
4084 && av
->offset
- offset
== item
->offset
)
4086 if (values_equal_for_ipcp_p (item
->value
, av
->value
))
4092 item
->value
= NULL_TREE
;
4096 /* Intersect values in INTER with aggregate values that come along edge CS to
4097 parameter number INDEX and return it. If INTER does not actually exist yet,
4098 copy all incoming values to it. If we determine we ended up with no values
4099 whatsoever, return a released vector. */
4101 static vec
<ipa_agg_jf_item
>
4102 intersect_aggregates_with_edge (struct cgraph_edge
*cs
, int index
,
4103 vec
<ipa_agg_jf_item
> inter
)
4105 struct ipa_jump_func
*jfunc
;
4106 jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), index
);
4107 if (jfunc
->type
== IPA_JF_PASS_THROUGH
4108 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
4110 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4111 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
4113 if (caller_info
->ipcp_orig_node
)
4115 struct cgraph_node
*orig_node
= caller_info
->ipcp_orig_node
;
4116 struct ipcp_param_lattices
*orig_plats
;
4117 orig_plats
= ipa_get_parm_lattices (IPA_NODE_REF (orig_node
),
4119 if (agg_pass_through_permissible_p (orig_plats
, jfunc
))
4121 if (!inter
.exists ())
4122 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, 0);
4124 intersect_with_agg_replacements (cs
->caller
, src_idx
,
4135 struct ipcp_param_lattices
*src_plats
;
4136 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
4137 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
4139 /* Currently we do not produce clobber aggregate jump
4140 functions, adjust when we do. */
4141 gcc_checking_assert (!jfunc
->agg
.items
);
4142 if (!inter
.exists ())
4143 inter
= copy_plats_to_inter (src_plats
, 0);
4145 intersect_with_plats (src_plats
, &inter
, 0);
4154 else if (jfunc
->type
== IPA_JF_ANCESTOR
4155 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
4157 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4158 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
4159 struct ipcp_param_lattices
*src_plats
;
4160 HOST_WIDE_INT delta
= ipa_get_jf_ancestor_offset (jfunc
);
4162 if (caller_info
->ipcp_orig_node
)
4164 if (!inter
.exists ())
4165 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, delta
);
4167 intersect_with_agg_replacements (cs
->caller
, src_idx
, &inter
,
4172 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);;
4173 /* Currently we do not produce clobber aggregate jump
4174 functions, adjust when we do. */
4175 gcc_checking_assert (!src_plats
->aggs
|| !jfunc
->agg
.items
);
4176 if (!inter
.exists ())
4177 inter
= copy_plats_to_inter (src_plats
, delta
);
4179 intersect_with_plats (src_plats
, &inter
, delta
);
4182 else if (jfunc
->agg
.items
)
4184 struct ipa_agg_jf_item
*item
;
4187 if (!inter
.exists ())
4188 for (unsigned i
= 0; i
< jfunc
->agg
.items
->length (); i
++)
4189 inter
.safe_push ((*jfunc
->agg
.items
)[i
]);
4191 FOR_EACH_VEC_ELT (inter
, k
, item
)
4194 bool found
= false;;
4199 while ((unsigned) l
< jfunc
->agg
.items
->length ())
4201 struct ipa_agg_jf_item
*ti
;
4202 ti
= &(*jfunc
->agg
.items
)[l
];
4203 if (ti
->offset
> item
->offset
)
4205 if (ti
->offset
== item
->offset
)
4207 gcc_checking_assert (ti
->value
);
4208 if (values_equal_for_ipcp_p (item
->value
,
4222 return vec
<ipa_agg_jf_item
>();
4227 /* Look at edges in CALLERS and collect all known aggregate values that arrive
4228 from all of them. */
4230 static struct ipa_agg_replacement_value
*
4231 find_aggregate_values_for_callers_subset (struct cgraph_node
*node
,
4232 vec
<cgraph_edge
*> callers
)
4234 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
4235 struct ipa_agg_replacement_value
*res
;
4236 struct ipa_agg_replacement_value
**tail
= &res
;
4237 struct cgraph_edge
*cs
;
4238 int i
, j
, count
= ipa_get_param_count (dest_info
);
4240 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4242 int c
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
4247 for (i
= 0; i
< count
; i
++)
4249 struct cgraph_edge
*cs
;
4250 vec
<ipa_agg_jf_item
> inter
= vNULL
;
4251 struct ipa_agg_jf_item
*item
;
4252 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (dest_info
, i
);
4255 /* Among other things, the following check should deal with all by_ref
4257 if (plats
->aggs_bottom
)
4260 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4262 inter
= intersect_aggregates_with_edge (cs
, i
, inter
);
4264 if (!inter
.exists ())
4268 FOR_EACH_VEC_ELT (inter
, j
, item
)
4270 struct ipa_agg_replacement_value
*v
;
4275 v
= ggc_alloc
<ipa_agg_replacement_value
> ();
4277 v
->offset
= item
->offset
;
4278 v
->value
= item
->value
;
4279 v
->by_ref
= plats
->aggs_by_ref
;
4285 if (inter
.exists ())
4292 /* Turn KNOWN_AGGS into a list of aggregate replacement values. */
4294 static struct ipa_agg_replacement_value
*
4295 known_aggs_to_agg_replacement_list (vec
<ipa_agg_jump_function
> known_aggs
)
4297 struct ipa_agg_replacement_value
*res
;
4298 struct ipa_agg_replacement_value
**tail
= &res
;
4299 struct ipa_agg_jump_function
*aggjf
;
4300 struct ipa_agg_jf_item
*item
;
4303 FOR_EACH_VEC_ELT (known_aggs
, i
, aggjf
)
4304 FOR_EACH_VEC_SAFE_ELT (aggjf
->items
, j
, item
)
4306 struct ipa_agg_replacement_value
*v
;
4307 v
= ggc_alloc
<ipa_agg_replacement_value
> ();
4309 v
->offset
= item
->offset
;
4310 v
->value
= item
->value
;
4311 v
->by_ref
= aggjf
->by_ref
;
4319 /* Determine whether CS also brings all scalar values that the NODE is
4323 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge
*cs
,
4324 struct cgraph_node
*node
)
4326 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
4327 int count
= ipa_get_param_count (dest_info
);
4328 struct ipa_node_params
*caller_info
;
4329 struct ipa_edge_args
*args
;
4332 caller_info
= IPA_NODE_REF (cs
->caller
);
4333 args
= IPA_EDGE_REF (cs
);
4334 for (i
= 0; i
< count
; i
++)
4336 struct ipa_jump_func
*jump_func
;
4339 val
= dest_info
->known_csts
[i
];
4343 if (i
>= ipa_get_cs_argument_count (args
))
4345 jump_func
= ipa_get_ith_jump_func (args
, i
);
4346 t
= ipa_value_from_jfunc (caller_info
, jump_func
);
4347 if (!t
|| !values_equal_for_ipcp_p (val
, t
))
4353 /* Determine whether CS also brings all aggregate values that NODE is
4356 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge
*cs
,
4357 struct cgraph_node
*node
)
4359 struct ipa_node_params
*orig_caller_info
= IPA_NODE_REF (cs
->caller
);
4360 struct ipa_node_params
*orig_node_info
;
4361 struct ipa_agg_replacement_value
*aggval
;
4364 aggval
= ipa_get_agg_replacements_for_node (node
);
4368 count
= ipa_get_param_count (IPA_NODE_REF (node
));
4369 ec
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
4371 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4372 if (aggval
->index
>= ec
)
4375 orig_node_info
= IPA_NODE_REF (IPA_NODE_REF (node
)->ipcp_orig_node
);
4376 if (orig_caller_info
->ipcp_orig_node
)
4377 orig_caller_info
= IPA_NODE_REF (orig_caller_info
->ipcp_orig_node
);
4379 for (i
= 0; i
< count
; i
++)
4381 static vec
<ipa_agg_jf_item
> values
= vec
<ipa_agg_jf_item
>();
4382 struct ipcp_param_lattices
*plats
;
4383 bool interesting
= false;
4384 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4385 if (aggval
->index
== i
)
4393 plats
= ipa_get_parm_lattices (orig_node_info
, aggval
->index
);
4394 if (plats
->aggs_bottom
)
4397 values
= intersect_aggregates_with_edge (cs
, i
, values
);
4398 if (!values
.exists ())
4401 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4402 if (aggval
->index
== i
)
4404 struct ipa_agg_jf_item
*item
;
4407 FOR_EACH_VEC_ELT (values
, j
, item
)
4409 && item
->offset
== av
->offset
4410 && values_equal_for_ipcp_p (item
->value
, av
->value
))
4425 /* Given an original NODE and a VAL for which we have already created a
4426 specialized clone, look whether there are incoming edges that still lead
4427 into the old node but now also bring the requested value and also conform to
4428 all other criteria such that they can be redirected the special node.
4429 This function can therefore redirect the final edge in a SCC. */
4431 template <typename valtype
>
4433 perhaps_add_new_callers (cgraph_node
*node
, ipcp_value
<valtype
> *val
)
4435 ipcp_value_source
<valtype
> *src
;
4436 profile_count redirected_sum
= profile_count::zero ();
4438 for (src
= val
->sources
; src
; src
= src
->next
)
4440 struct cgraph_edge
*cs
= src
->cs
;
4443 if (cgraph_edge_brings_value_p (cs
, src
, node
)
4444 && cgraph_edge_brings_all_scalars_for_node (cs
, val
->spec_node
)
4445 && cgraph_edge_brings_all_agg_vals_for_node (cs
, val
->spec_node
))
4448 fprintf (dump_file
, " - adding an extra caller %s of %s\n",
4449 cs
->caller
->dump_name (),
4450 val
->spec_node
->dump_name ());
4452 cs
->redirect_callee_duplicating_thunks (val
->spec_node
);
4453 val
->spec_node
->expand_all_artificial_thunks ();
4454 if (cs
->count
.initialized_p ())
4455 redirected_sum
= redirected_sum
+ cs
->count
;
4457 cs
= get_next_cgraph_edge_clone (cs
);
4461 if (redirected_sum
> profile_count::zero ())
4462 update_specialized_profile (val
->spec_node
, node
, redirected_sum
);
4465 /* Return true if KNOWN_CONTEXTS contain at least one useful context. */
4468 known_contexts_useful_p (vec
<ipa_polymorphic_call_context
> known_contexts
)
4470 ipa_polymorphic_call_context
*ctx
;
4473 FOR_EACH_VEC_ELT (known_contexts
, i
, ctx
)
4474 if (!ctx
->useless_p ())
4479 /* Return a copy of KNOWN_CSTS if it is not empty, otherwise return vNULL. */
4481 static vec
<ipa_polymorphic_call_context
>
4482 copy_useful_known_contexts (vec
<ipa_polymorphic_call_context
> known_contexts
)
4484 if (known_contexts_useful_p (known_contexts
))
4485 return known_contexts
.copy ();
4490 /* Copy KNOWN_CSTS and modify the copy according to VAL and INDEX. If
4491 non-empty, replace KNOWN_CONTEXTS with its copy too. */
4494 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
4495 vec
<ipa_polymorphic_call_context
> *known_contexts
,
4496 ipcp_value
<tree
> *val
,
4499 *known_csts
= known_csts
->copy ();
4500 *known_contexts
= copy_useful_known_contexts (*known_contexts
);
4501 (*known_csts
)[index
] = val
->value
;
4504 /* Replace KNOWN_CSTS with its copy. Also copy KNOWN_CONTEXTS and modify the
4505 copy according to VAL and INDEX. */
4508 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
4509 vec
<ipa_polymorphic_call_context
> *known_contexts
,
4510 ipcp_value
<ipa_polymorphic_call_context
> *val
,
4513 *known_csts
= known_csts
->copy ();
4514 *known_contexts
= known_contexts
->copy ();
4515 (*known_contexts
)[index
] = val
->value
;
4518 /* Return true if OFFSET indicates this was not an aggregate value or there is
4519 a replacement equivalent to VALUE, INDEX and OFFSET among those in the
4523 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*aggvals
,
4524 int index
, HOST_WIDE_INT offset
, tree value
)
4531 if (aggvals
->index
== index
4532 && aggvals
->offset
== offset
4533 && values_equal_for_ipcp_p (aggvals
->value
, value
))
4535 aggvals
= aggvals
->next
;
4540 /* Return true if offset is minus one because source of a polymorphic contect
4541 cannot be an aggregate value. */
4544 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*,
4545 int , HOST_WIDE_INT offset
,
4546 ipa_polymorphic_call_context
)
4548 return offset
== -1;
4551 /* Decide wheter to create a special version of NODE for value VAL of parameter
4552 at the given INDEX. If OFFSET is -1, the value is for the parameter itself,
4553 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS,
4554 KNOWN_CONTEXTS and KNOWN_AGGS describe the other already known values. */
4556 template <typename valtype
>
4558 decide_about_value (struct cgraph_node
*node
, int index
, HOST_WIDE_INT offset
,
4559 ipcp_value
<valtype
> *val
, vec
<tree
> known_csts
,
4560 vec
<ipa_polymorphic_call_context
> known_contexts
)
4562 struct ipa_agg_replacement_value
*aggvals
;
4563 int freq_sum
, caller_count
;
4564 profile_count count_sum
;
4565 vec
<cgraph_edge
*> callers
;
4569 perhaps_add_new_callers (node
, val
);
4572 else if (val
->local_size_cost
+ overall_size
> max_new_size
)
4574 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4575 fprintf (dump_file
, " Ignoring candidate value because "
4576 "max_new_size would be reached with %li.\n",
4577 val
->local_size_cost
+ overall_size
);
4580 else if (!get_info_about_necessary_edges (val
, node
, &freq_sum
, &count_sum
,
4584 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4586 fprintf (dump_file
, " - considering value ");
4587 print_ipcp_constant_value (dump_file
, val
->value
);
4588 fprintf (dump_file
, " for ");
4589 ipa_dump_param (dump_file
, IPA_NODE_REF (node
), index
);
4591 fprintf (dump_file
, ", offset: " HOST_WIDE_INT_PRINT_DEC
, offset
);
4592 fprintf (dump_file
, " (caller_count: %i)\n", caller_count
);
4595 if (!good_cloning_opportunity_p (node
, val
->local_time_benefit
,
4596 freq_sum
, count_sum
,
4597 val
->local_size_cost
)
4598 && !good_cloning_opportunity_p (node
,
4599 val
->local_time_benefit
4600 + val
->prop_time_benefit
,
4601 freq_sum
, count_sum
,
4602 val
->local_size_cost
4603 + val
->prop_size_cost
))
4607 fprintf (dump_file
, " Creating a specialized node of %s.\n",
4608 node
->dump_name ());
4610 callers
= gather_edges_for_value (val
, node
, caller_count
);
4612 modify_known_vectors_with_val (&known_csts
, &known_contexts
, val
, index
);
4615 known_csts
= known_csts
.copy ();
4616 known_contexts
= copy_useful_known_contexts (known_contexts
);
4618 find_more_scalar_values_for_callers_subset (node
, known_csts
, callers
);
4619 find_more_contexts_for_caller_subset (node
, &known_contexts
, callers
);
4620 aggvals
= find_aggregate_values_for_callers_subset (node
, callers
);
4621 gcc_checking_assert (ipcp_val_agg_replacement_ok_p (aggvals
, index
,
4622 offset
, val
->value
));
4623 val
->spec_node
= create_specialized_node (node
, known_csts
, known_contexts
,
4625 overall_size
+= val
->local_size_cost
;
4627 /* TODO: If for some lattice there is only one other known value
4628 left, make a special node for it too. */
4633 /* Decide whether and what specialized clones of NODE should be created. */
4636 decide_whether_version_node (struct cgraph_node
*node
)
4638 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
4639 int i
, count
= ipa_get_param_count (info
);
4640 vec
<tree
> known_csts
;
4641 vec
<ipa_polymorphic_call_context
> known_contexts
;
4642 vec
<ipa_agg_jump_function
> known_aggs
= vNULL
;
4648 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4649 fprintf (dump_file
, "\nEvaluating opportunities for %s.\n",
4650 node
->dump_name ());
4652 gather_context_independent_values (info
, &known_csts
, &known_contexts
,
4653 info
->do_clone_for_all_contexts
? &known_aggs
4656 for (i
= 0; i
< count
;i
++)
4658 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4659 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
4660 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
4665 ipcp_value
<tree
> *val
;
4666 for (val
= lat
->values
; val
; val
= val
->next
)
4667 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
4671 if (!plats
->aggs_bottom
)
4673 struct ipcp_agg_lattice
*aglat
;
4674 ipcp_value
<tree
> *val
;
4675 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
4676 if (!aglat
->bottom
&& aglat
->values
4677 /* If the following is false, the one value is in
4679 && (plats
->aggs_contain_variable
4680 || !aglat
->is_single_const ()))
4681 for (val
= aglat
->values
; val
; val
= val
->next
)
4682 ret
|= decide_about_value (node
, i
, aglat
->offset
, val
,
4683 known_csts
, known_contexts
);
4687 && known_contexts
[i
].useless_p ())
4689 ipcp_value
<ipa_polymorphic_call_context
> *val
;
4690 for (val
= ctxlat
->values
; val
; val
= val
->next
)
4691 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
4695 info
= IPA_NODE_REF (node
);
4698 if (info
->do_clone_for_all_contexts
)
4700 struct cgraph_node
*clone
;
4701 vec
<cgraph_edge
*> callers
;
4704 fprintf (dump_file
, " - Creating a specialized node of %s "
4705 "for all known contexts.\n", node
->dump_name ());
4707 callers
= node
->collect_callers ();
4709 if (!known_contexts_useful_p (known_contexts
))
4711 known_contexts
.release ();
4712 known_contexts
= vNULL
;
4714 clone
= create_specialized_node (node
, known_csts
, known_contexts
,
4715 known_aggs_to_agg_replacement_list (known_aggs
),
4717 info
= IPA_NODE_REF (node
);
4718 info
->do_clone_for_all_contexts
= false;
4719 IPA_NODE_REF (clone
)->is_all_contexts_clone
= true;
4720 for (i
= 0; i
< count
; i
++)
4721 vec_free (known_aggs
[i
].items
);
4722 known_aggs
.release ();
4727 known_csts
.release ();
4728 known_contexts
.release ();
4734 /* Transitively mark all callees of NODE within the same SCC as not dead. */
4737 spread_undeadness (struct cgraph_node
*node
)
4739 struct cgraph_edge
*cs
;
4741 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
4742 if (ipa_edge_within_scc (cs
))
4744 struct cgraph_node
*callee
;
4745 struct ipa_node_params
*info
;
4747 callee
= cs
->callee
->function_symbol (NULL
);
4748 info
= IPA_NODE_REF (callee
);
4750 if (info
->node_dead
)
4752 info
->node_dead
= 0;
4753 spread_undeadness (callee
);
4758 /* Return true if NODE has a caller from outside of its SCC that is not
4759 dead. Worker callback for cgraph_for_node_and_aliases. */
4762 has_undead_caller_from_outside_scc_p (struct cgraph_node
*node
,
4763 void *data ATTRIBUTE_UNUSED
)
4765 struct cgraph_edge
*cs
;
4767 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
4768 if (cs
->caller
->thunk
.thunk_p
4769 && cs
->caller
->call_for_symbol_thunks_and_aliases
4770 (has_undead_caller_from_outside_scc_p
, NULL
, true))
4772 else if (!ipa_edge_within_scc (cs
)
4773 && !IPA_NODE_REF (cs
->caller
)->node_dead
)
4779 /* Identify nodes within the same SCC as NODE which are no longer needed
4780 because of new clones and will be removed as unreachable. */
4783 identify_dead_nodes (struct cgraph_node
*node
)
4785 struct cgraph_node
*v
;
4786 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4788 && !v
->call_for_symbol_thunks_and_aliases
4789 (has_undead_caller_from_outside_scc_p
, NULL
, true))
4790 IPA_NODE_REF (v
)->node_dead
= 1;
4792 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4793 if (!IPA_NODE_REF (v
)->node_dead
)
4794 spread_undeadness (v
);
4796 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4798 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4799 if (IPA_NODE_REF (v
)->node_dead
)
4800 fprintf (dump_file
, " Marking node as dead: %s.\n", v
->dump_name ());
4804 /* The decision stage. Iterate over the topological order of call graph nodes
4805 TOPO and make specialized clones if deemed beneficial. */
4808 ipcp_decision_stage (struct ipa_topo_info
*topo
)
4813 fprintf (dump_file
, "\nIPA decision stage:\n\n");
4815 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
4817 struct cgraph_node
*node
= topo
->order
[i
];
4818 bool change
= false, iterate
= true;
4822 struct cgraph_node
*v
;
4824 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4825 if (v
->has_gimple_body_p ()
4826 && ipcp_versionable_function_p (v
))
4827 iterate
|= decide_whether_version_node (v
);
4832 identify_dead_nodes (node
);
4836 /* Look up all the bits information that we have discovered and copy it over
4837 to the transformation summary. */
4840 ipcp_store_bits_results (void)
4844 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
4846 ipa_node_params
*info
= IPA_NODE_REF (node
);
4847 bool dumped_sth
= false;
4848 bool found_useful_result
= false;
4850 if (!opt_for_fn (node
->decl
, flag_ipa_bit_cp
))
4853 fprintf (dump_file
, "Not considering %s for ipa bitwise propagation "
4854 "; -fipa-bit-cp: disabled.\n",
4859 if (info
->ipcp_orig_node
)
4860 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
4862 unsigned count
= ipa_get_param_count (info
);
4863 for (unsigned i
= 0; i
< count
; i
++)
4865 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4866 if (plats
->bits_lattice
.constant_p ())
4868 found_useful_result
= true;
4873 if (!found_useful_result
)
4876 ipcp_grow_transformations_if_necessary ();
4877 ipcp_transformation_summary
*ts
= ipcp_get_transformation_summary (node
);
4878 vec_safe_reserve_exact (ts
->bits
, count
);
4880 for (unsigned i
= 0; i
< count
; i
++)
4882 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4885 if (plats
->bits_lattice
.constant_p ())
4887 = ipa_get_ipa_bits_for_value (plats
->bits_lattice
.get_value (),
4888 plats
->bits_lattice
.get_mask ());
4892 ts
->bits
->quick_push (jfbits
);
4893 if (!dump_file
|| !jfbits
)
4897 fprintf (dump_file
, "Propagated bits info for function %s:\n",
4898 node
->dump_name ());
4901 fprintf (dump_file
, " param %i: value = ", i
);
4902 print_hex (jfbits
->value
, dump_file
);
4903 fprintf (dump_file
, ", mask = ");
4904 print_hex (jfbits
->mask
, dump_file
);
4905 fprintf (dump_file
, "\n");
4910 /* Look up all VR information that we have discovered and copy it over
4911 to the transformation summary. */
4914 ipcp_store_vr_results (void)
4918 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
4920 ipa_node_params
*info
= IPA_NODE_REF (node
);
4921 bool found_useful_result
= false;
4923 if (!opt_for_fn (node
->decl
, flag_ipa_vrp
))
4926 fprintf (dump_file
, "Not considering %s for VR discovery "
4927 "and propagate; -fipa-ipa-vrp: disabled.\n",
4932 if (info
->ipcp_orig_node
)
4933 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
4935 unsigned count
= ipa_get_param_count (info
);
4936 for (unsigned i
= 0; i
< count
; i
++)
4938 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4939 if (!plats
->m_value_range
.bottom_p ()
4940 && !plats
->m_value_range
.top_p ())
4942 found_useful_result
= true;
4946 if (!found_useful_result
)
4949 ipcp_grow_transformations_if_necessary ();
4950 ipcp_transformation_summary
*ts
= ipcp_get_transformation_summary (node
);
4951 vec_safe_reserve_exact (ts
->m_vr
, count
);
4953 for (unsigned i
= 0; i
< count
; i
++)
4955 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4958 if (!plats
->m_value_range
.bottom_p ()
4959 && !plats
->m_value_range
.top_p ())
4962 vr
.type
= plats
->m_value_range
.m_vr
.type
;
4963 vr
.min
= plats
->m_value_range
.m_vr
.min
;
4964 vr
.max
= plats
->m_value_range
.m_vr
.max
;
4969 vr
.type
= VR_VARYING
;
4970 vr
.min
= vr
.max
= wi::zero (INT_TYPE_SIZE
);
4972 ts
->m_vr
->quick_push (vr
);
4977 /* The IPCP driver. */
4982 struct cgraph_2edge_hook_list
*edge_duplication_hook_holder
;
4983 struct cgraph_edge_hook_list
*edge_removal_hook_holder
;
4984 struct ipa_topo_info topo
;
4986 ipa_check_create_node_params ();
4987 ipa_check_create_edge_args ();
4988 grow_edge_clone_vectors ();
4989 edge_duplication_hook_holder
4990 = symtab
->add_edge_duplication_hook (&ipcp_edge_duplication_hook
, NULL
);
4991 edge_removal_hook_holder
4992 = symtab
->add_edge_removal_hook (&ipcp_edge_removal_hook
, NULL
);
4996 fprintf (dump_file
, "\nIPA structures before propagation:\n");
4997 if (dump_flags
& TDF_DETAILS
)
4998 ipa_print_all_params (dump_file
);
4999 ipa_print_all_jump_functions (dump_file
);
5002 /* Topological sort. */
5003 build_toporder_info (&topo
);
5004 /* Do the interprocedural propagation. */
5005 ipcp_propagate_stage (&topo
);
5006 /* Decide what constant propagation and cloning should be performed. */
5007 ipcp_decision_stage (&topo
);
5008 /* Store results of bits propagation. */
5009 ipcp_store_bits_results ();
5010 /* Store results of value range propagation. */
5011 ipcp_store_vr_results ();
5013 /* Free all IPCP structures. */
5014 free_toporder_info (&topo
);
5015 next_edge_clone
.release ();
5016 prev_edge_clone
.release ();
5017 symtab
->remove_edge_removal_hook (edge_removal_hook_holder
);
5018 symtab
->remove_edge_duplication_hook (edge_duplication_hook_holder
);
5019 ipa_free_all_structures_after_ipa_cp ();
5021 fprintf (dump_file
, "\nIPA constant propagation end\n");
5025 /* Initialization and computation of IPCP data structures. This is the initial
5026 intraprocedural analysis of functions, which gathers information to be
5027 propagated later on. */
5030 ipcp_generate_summary (void)
5032 struct cgraph_node
*node
;
5035 fprintf (dump_file
, "\nIPA constant propagation start:\n");
5036 ipa_register_cgraph_hooks ();
5038 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5039 ipa_analyze_node (node
);
5042 /* Write ipcp summary for nodes in SET. */
5045 ipcp_write_summary (void)
5047 ipa_prop_write_jump_functions ();
5050 /* Read ipcp summary. */
5053 ipcp_read_summary (void)
5055 ipa_prop_read_jump_functions ();
5060 const pass_data pass_data_ipa_cp
=
5062 IPA_PASS
, /* type */
5064 OPTGROUP_NONE
, /* optinfo_flags */
5065 TV_IPA_CONSTANT_PROP
, /* tv_id */
5066 0, /* properties_required */
5067 0, /* properties_provided */
5068 0, /* properties_destroyed */
5069 0, /* todo_flags_start */
5070 ( TODO_dump_symtab
| TODO_remove_functions
), /* todo_flags_finish */
5073 class pass_ipa_cp
: public ipa_opt_pass_d
5076 pass_ipa_cp (gcc::context
*ctxt
)
5077 : ipa_opt_pass_d (pass_data_ipa_cp
, ctxt
,
5078 ipcp_generate_summary
, /* generate_summary */
5079 ipcp_write_summary
, /* write_summary */
5080 ipcp_read_summary
, /* read_summary */
5081 ipcp_write_transformation_summaries
, /*
5082 write_optimization_summary */
5083 ipcp_read_transformation_summaries
, /*
5084 read_optimization_summary */
5085 NULL
, /* stmt_fixup */
5086 0, /* function_transform_todo_flags_start */
5087 ipcp_transform_function
, /* function_transform */
5088 NULL
) /* variable_transform */
5091 /* opt_pass methods: */
5092 virtual bool gate (function
*)
5094 /* FIXME: We should remove the optimize check after we ensure we never run
5095 IPA passes when not optimizing. */
5096 return (flag_ipa_cp
&& optimize
) || in_lto_p
;
5099 virtual unsigned int execute (function
*) { return ipcp_driver (); }
5101 }; // class pass_ipa_cp
5106 make_pass_ipa_cp (gcc::context
*ctxt
)
5108 return new pass_ipa_cp (ctxt
);
5111 /* Reset all state within ipa-cp.c so that we can rerun the compiler
5112 within the same process. For use by toplev::finalize. */
5115 ipa_cp_c_finalize (void)
5117 max_count
= profile_count::zero ();