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-inline.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 gcov_type 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)), 0);
433 print_generic_expr (f
, v
, 0);
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/%i:\n", node
->name (),
544 count
= ipa_get_param_count (info
);
545 for (i
= 0; i
< count
; i
++)
547 struct ipcp_agg_lattice
*aglat
;
548 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
549 fprintf (f
, " param [%d]: ", i
);
550 plats
->itself
.print (f
, dump_sources
, dump_benefits
);
551 fprintf (f
, " ctxs: ");
552 plats
->ctxlat
.print (f
, dump_sources
, dump_benefits
);
553 plats
->bits_lattice
.print (f
);
555 plats
->m_value_range
.print (f
);
557 if (plats
->virt_call
)
558 fprintf (f
, " virt_call flag set\n");
560 if (plats
->aggs_bottom
)
562 fprintf (f
, " AGGS BOTTOM\n");
565 if (plats
->aggs_contain_variable
)
566 fprintf (f
, " AGGS VARIABLE\n");
567 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
569 fprintf (f
, " %soffset " HOST_WIDE_INT_PRINT_DEC
": ",
570 plats
->aggs_by_ref
? "ref " : "", aglat
->offset
);
571 aglat
->print (f
, dump_sources
, dump_benefits
);
577 /* Determine whether it is at all technically possible to create clones of NODE
578 and store this information in the ipa_node_params structure associated
582 determine_versionability (struct cgraph_node
*node
,
583 struct ipa_node_params
*info
)
585 const char *reason
= NULL
;
587 /* There are a number of generic reasons functions cannot be versioned. We
588 also cannot remove parameters if there are type attributes such as fnspec
590 if (node
->alias
|| node
->thunk
.thunk_p
)
591 reason
= "alias or thunk";
592 else if (!node
->local
.versionable
)
593 reason
= "not a tree_versionable_function";
594 else if (node
->get_availability () <= AVAIL_INTERPOSABLE
)
595 reason
= "insufficient body availability";
596 else if (!opt_for_fn (node
->decl
, optimize
)
597 || !opt_for_fn (node
->decl
, flag_ipa_cp
))
598 reason
= "non-optimized function";
599 else if (lookup_attribute ("omp declare simd", DECL_ATTRIBUTES (node
->decl
)))
601 /* Ideally we should clone the SIMD clones themselves and create
602 vector copies of them, so IPA-cp and SIMD clones can happily
603 coexist, but that may not be worth the effort. */
604 reason
= "function has SIMD clones";
606 else if (lookup_attribute ("target_clones", DECL_ATTRIBUTES (node
->decl
)))
608 /* Ideally we should clone the target clones themselves and create
609 copies of them, so IPA-cp and target clones can happily
610 coexist, but that may not be worth the effort. */
611 reason
= "function target_clones attribute";
613 /* Don't clone decls local to a comdat group; it breaks and for C++
614 decloned constructors, inlining is always better anyway. */
615 else if (node
->comdat_local_p ())
616 reason
= "comdat-local function";
617 else if (node
->calls_comdat_local
)
619 /* TODO: call is versionable if we make sure that all
620 callers are inside of a comdat group. */
621 reason
= "calls comdat-local function";
624 if (reason
&& dump_file
&& !node
->alias
&& !node
->thunk
.thunk_p
)
625 fprintf (dump_file
, "Function %s/%i is not versionable, reason: %s.\n",
626 node
->name (), node
->order
, reason
);
628 info
->versionable
= (reason
== NULL
);
631 /* Return true if it is at all technically possible to create clones of a
635 ipcp_versionable_function_p (struct cgraph_node
*node
)
637 return IPA_NODE_REF (node
)->versionable
;
640 /* Structure holding accumulated information about callers of a node. */
642 struct caller_statistics
645 int n_calls
, n_hot_calls
, freq_sum
;
648 /* Initialize fields of STAT to zeroes. */
651 init_caller_stats (struct caller_statistics
*stats
)
653 stats
->count_sum
= 0;
655 stats
->n_hot_calls
= 0;
659 /* Worker callback of cgraph_for_node_and_aliases accumulating statistics of
660 non-thunk incoming edges to NODE. */
663 gather_caller_stats (struct cgraph_node
*node
, void *data
)
665 struct caller_statistics
*stats
= (struct caller_statistics
*) data
;
666 struct cgraph_edge
*cs
;
668 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
669 if (!cs
->caller
->thunk
.thunk_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 (inline_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
724 if (stats
.count_sum
> node
->count
* 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/%i as %s\n",
1199 node
->name (), node
->order
,
1200 disable
? "BOTTOM" : "VARIABLE");
1203 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
1204 if (ie
->indirect_info
->polymorphic
1205 && ie
->indirect_info
->param_index
>= 0)
1207 gcc_checking_assert (ie
->indirect_info
->param_index
>= 0);
1208 ipa_get_parm_lattices (info
,
1209 ie
->indirect_info
->param_index
)->virt_call
= 1;
1213 /* Return the result of a (possibly arithmetic) pass through jump function
1214 JFUNC on the constant value INPUT. Return NULL_TREE if that cannot be
1215 determined or be considered an interprocedural invariant. */
1218 ipa_get_jf_pass_through_result (struct ipa_jump_func
*jfunc
, tree input
)
1222 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
1224 if (!is_gimple_ip_invariant (input
))
1227 if (TREE_CODE_CLASS (ipa_get_jf_pass_through_operation (jfunc
))
1229 res
= fold_unary (ipa_get_jf_pass_through_operation (jfunc
),
1230 TREE_TYPE (input
), input
);
1233 if (TREE_CODE_CLASS (ipa_get_jf_pass_through_operation (jfunc
))
1235 restype
= boolean_type_node
;
1237 restype
= TREE_TYPE (input
);
1238 res
= fold_binary (ipa_get_jf_pass_through_operation (jfunc
), restype
,
1239 input
, ipa_get_jf_pass_through_operand (jfunc
));
1241 if (res
&& !is_gimple_ip_invariant (res
))
1247 /* Return the result of an ancestor jump function JFUNC on the constant value
1248 INPUT. Return NULL_TREE if that cannot be determined. */
1251 ipa_get_jf_ancestor_result (struct ipa_jump_func
*jfunc
, tree input
)
1253 gcc_checking_assert (TREE_CODE (input
) != TREE_BINFO
);
1254 if (TREE_CODE (input
) == ADDR_EXPR
)
1256 tree t
= TREE_OPERAND (input
, 0);
1257 t
= build_ref_for_offset (EXPR_LOCATION (t
), t
,
1258 ipa_get_jf_ancestor_offset (jfunc
), false,
1259 ptr_type_node
, NULL
, false);
1260 return build_fold_addr_expr (t
);
1266 /* Determine whether JFUNC evaluates to a single known constant value and if
1267 so, return it. Otherwise return NULL. INFO describes the caller node or
1268 the one it is inlined to, so that pass-through jump functions can be
1272 ipa_value_from_jfunc (struct ipa_node_params
*info
, struct ipa_jump_func
*jfunc
)
1274 if (jfunc
->type
== IPA_JF_CONST
)
1275 return ipa_get_jf_constant (jfunc
);
1276 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1277 || jfunc
->type
== IPA_JF_ANCESTOR
)
1282 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1283 idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1285 idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1287 if (info
->ipcp_orig_node
)
1288 input
= info
->known_csts
[idx
];
1291 ipcp_lattice
<tree
> *lat
;
1294 || idx
>= ipa_get_param_count (info
))
1296 lat
= ipa_get_scalar_lat (info
, idx
);
1297 if (!lat
->is_single_const ())
1299 input
= lat
->values
->value
;
1305 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1306 return ipa_get_jf_pass_through_result (jfunc
, input
);
1308 return ipa_get_jf_ancestor_result (jfunc
, input
);
1314 /* Determie whether JFUNC evaluates to single known polymorphic context, given
1315 that INFO describes the caller node or the one it is inlined to, CS is the
1316 call graph edge corresponding to JFUNC and CSIDX index of the described
1319 ipa_polymorphic_call_context
1320 ipa_context_from_jfunc (ipa_node_params
*info
, cgraph_edge
*cs
, int csidx
,
1321 ipa_jump_func
*jfunc
)
1323 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
1324 ipa_polymorphic_call_context ctx
;
1325 ipa_polymorphic_call_context
*edge_ctx
1326 = cs
? ipa_get_ith_polymorhic_call_context (args
, csidx
) : NULL
;
1328 if (edge_ctx
&& !edge_ctx
->useless_p ())
1331 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1332 || jfunc
->type
== IPA_JF_ANCESTOR
)
1334 ipa_polymorphic_call_context srcctx
;
1336 bool type_preserved
= true;
1337 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1339 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1341 type_preserved
= ipa_get_jf_pass_through_type_preserved (jfunc
);
1342 srcidx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1346 type_preserved
= ipa_get_jf_ancestor_type_preserved (jfunc
);
1347 srcidx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1349 if (info
->ipcp_orig_node
)
1351 if (info
->known_contexts
.exists ())
1352 srcctx
= info
->known_contexts
[srcidx
];
1357 || srcidx
>= ipa_get_param_count (info
))
1359 ipcp_lattice
<ipa_polymorphic_call_context
> *lat
;
1360 lat
= ipa_get_poly_ctx_lat (info
, srcidx
);
1361 if (!lat
->is_single_const ())
1363 srcctx
= lat
->values
->value
;
1365 if (srcctx
.useless_p ())
1367 if (jfunc
->type
== IPA_JF_ANCESTOR
)
1368 srcctx
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
1369 if (!type_preserved
)
1370 srcctx
.possible_dynamic_type_change (cs
->in_polymorphic_cdtor
);
1371 srcctx
.combine_with (ctx
);
1378 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
1379 bottom, not containing a variable component and without any known value at
1383 ipcp_verify_propagated_values (void)
1385 struct cgraph_node
*node
;
1387 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
1389 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1390 int i
, count
= ipa_get_param_count (info
);
1392 for (i
= 0; i
< count
; i
++)
1394 ipcp_lattice
<tree
> *lat
= ipa_get_scalar_lat (info
, i
);
1397 && !lat
->contains_variable
1398 && lat
->values_count
== 0)
1402 symtab_node::dump_table (dump_file
);
1403 fprintf (dump_file
, "\nIPA lattices after constant "
1404 "propagation, before gcc_unreachable:\n");
1405 print_all_lattices (dump_file
, true, false);
1414 /* Return true iff X and Y should be considered equal values by IPA-CP. */
1417 values_equal_for_ipcp_p (tree x
, tree y
)
1419 gcc_checking_assert (x
!= NULL_TREE
&& y
!= NULL_TREE
);
1424 if (TREE_CODE (x
) == ADDR_EXPR
1425 && TREE_CODE (y
) == ADDR_EXPR
1426 && TREE_CODE (TREE_OPERAND (x
, 0)) == CONST_DECL
1427 && TREE_CODE (TREE_OPERAND (y
, 0)) == CONST_DECL
)
1428 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x
, 0)),
1429 DECL_INITIAL (TREE_OPERAND (y
, 0)), 0);
1431 return operand_equal_p (x
, y
, 0);
1434 /* Return true iff X and Y should be considered equal contexts by IPA-CP. */
1437 values_equal_for_ipcp_p (ipa_polymorphic_call_context x
,
1438 ipa_polymorphic_call_context y
)
1440 return x
.equal_to (y
);
1444 /* Add a new value source to the value represented by THIS, marking that a
1445 value comes from edge CS and (if the underlying jump function is a
1446 pass-through or an ancestor one) from a caller value SRC_VAL of a caller
1447 parameter described by SRC_INDEX. OFFSET is negative if the source was the
1448 scalar value of the parameter itself or the offset within an aggregate. */
1450 template <typename valtype
>
1452 ipcp_value
<valtype
>::add_source (cgraph_edge
*cs
, ipcp_value
*src_val
,
1453 int src_idx
, HOST_WIDE_INT offset
)
1455 ipcp_value_source
<valtype
> *src
;
1457 src
= new (ipcp_sources_pool
.allocate ()) ipcp_value_source
<valtype
>;
1458 src
->offset
= offset
;
1461 src
->index
= src_idx
;
1463 src
->next
= sources
;
1467 /* Allocate a new ipcp_value holding a tree constant, initialize its value to
1468 SOURCE and clear all other fields. */
1470 static ipcp_value
<tree
> *
1471 allocate_and_init_ipcp_value (tree source
)
1473 ipcp_value
<tree
> *val
;
1475 val
= ipcp_cst_values_pool
.allocate ();
1476 memset (val
, 0, sizeof (*val
));
1477 val
->value
= source
;
1481 /* Allocate a new ipcp_value holding a polymorphic context, initialize its
1482 value to SOURCE and clear all other fields. */
1484 static ipcp_value
<ipa_polymorphic_call_context
> *
1485 allocate_and_init_ipcp_value (ipa_polymorphic_call_context source
)
1487 ipcp_value
<ipa_polymorphic_call_context
> *val
;
1490 val
= ipcp_poly_ctx_values_pool
.allocate ();
1491 memset (val
, 0, sizeof (*val
));
1492 val
->value
= source
;
1496 /* Try to add NEWVAL to LAT, potentially creating a new ipcp_value for it. CS,
1497 SRC_VAL SRC_INDEX and OFFSET are meant for add_source and have the same
1498 meaning. OFFSET -1 means the source is scalar and not a part of an
1501 template <typename valtype
>
1503 ipcp_lattice
<valtype
>::add_value (valtype newval
, cgraph_edge
*cs
,
1504 ipcp_value
<valtype
> *src_val
,
1505 int src_idx
, HOST_WIDE_INT offset
)
1507 ipcp_value
<valtype
> *val
;
1512 for (val
= values
; val
; val
= val
->next
)
1513 if (values_equal_for_ipcp_p (val
->value
, newval
))
1515 if (ipa_edge_within_scc (cs
))
1517 ipcp_value_source
<valtype
> *s
;
1518 for (s
= val
->sources
; s
; s
= s
->next
)
1525 val
->add_source (cs
, src_val
, src_idx
, offset
);
1529 if (values_count
== PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE
))
1531 /* We can only free sources, not the values themselves, because sources
1532 of other values in this SCC might point to them. */
1533 for (val
= values
; val
; val
= val
->next
)
1535 while (val
->sources
)
1537 ipcp_value_source
<valtype
> *src
= val
->sources
;
1538 val
->sources
= src
->next
;
1539 ipcp_sources_pool
.remove ((ipcp_value_source
<tree
>*)src
);
1544 return set_to_bottom ();
1548 val
= allocate_and_init_ipcp_value (newval
);
1549 val
->add_source (cs
, src_val
, src_idx
, offset
);
1555 /* Propagate values through a pass-through jump function JFUNC associated with
1556 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1557 is the index of the source parameter. */
1560 propagate_vals_across_pass_through (cgraph_edge
*cs
, ipa_jump_func
*jfunc
,
1561 ipcp_lattice
<tree
> *src_lat
,
1562 ipcp_lattice
<tree
> *dest_lat
, int src_idx
)
1564 ipcp_value
<tree
> *src_val
;
1567 /* Do not create new values when propagating within an SCC because if there
1568 are arithmetic functions with circular dependencies, there is infinite
1569 number of them and we would just make lattices bottom. */
1570 if ((ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1571 && ipa_edge_within_scc (cs
))
1572 ret
= dest_lat
->set_contains_variable ();
1574 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1576 tree cstval
= ipa_get_jf_pass_through_result (jfunc
, src_val
->value
);
1579 ret
|= dest_lat
->add_value (cstval
, cs
, src_val
, src_idx
);
1581 ret
|= dest_lat
->set_contains_variable ();
1587 /* Propagate values through an ancestor jump function JFUNC associated with
1588 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1589 is the index of the source parameter. */
1592 propagate_vals_across_ancestor (struct cgraph_edge
*cs
,
1593 struct ipa_jump_func
*jfunc
,
1594 ipcp_lattice
<tree
> *src_lat
,
1595 ipcp_lattice
<tree
> *dest_lat
, int src_idx
)
1597 ipcp_value
<tree
> *src_val
;
1600 if (ipa_edge_within_scc (cs
))
1601 return dest_lat
->set_contains_variable ();
1603 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1605 tree t
= ipa_get_jf_ancestor_result (jfunc
, src_val
->value
);
1608 ret
|= dest_lat
->add_value (t
, cs
, src_val
, src_idx
);
1610 ret
|= dest_lat
->set_contains_variable ();
1616 /* Propagate scalar values across jump function JFUNC that is associated with
1617 edge CS and put the values into DEST_LAT. */
1620 propagate_scalar_across_jump_function (struct cgraph_edge
*cs
,
1621 struct ipa_jump_func
*jfunc
,
1622 ipcp_lattice
<tree
> *dest_lat
)
1624 if (dest_lat
->bottom
)
1627 if (jfunc
->type
== IPA_JF_CONST
)
1629 tree val
= ipa_get_jf_constant (jfunc
);
1630 return dest_lat
->add_value (val
, cs
, NULL
, 0);
1632 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1633 || jfunc
->type
== IPA_JF_ANCESTOR
)
1635 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1636 ipcp_lattice
<tree
> *src_lat
;
1640 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1641 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1643 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1645 src_lat
= ipa_get_scalar_lat (caller_info
, src_idx
);
1646 if (src_lat
->bottom
)
1647 return dest_lat
->set_contains_variable ();
1649 /* If we would need to clone the caller and cannot, do not propagate. */
1650 if (!ipcp_versionable_function_p (cs
->caller
)
1651 && (src_lat
->contains_variable
1652 || (src_lat
->values_count
> 1)))
1653 return dest_lat
->set_contains_variable ();
1655 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1656 ret
= propagate_vals_across_pass_through (cs
, jfunc
, src_lat
,
1659 ret
= propagate_vals_across_ancestor (cs
, jfunc
, src_lat
, dest_lat
,
1662 if (src_lat
->contains_variable
)
1663 ret
|= dest_lat
->set_contains_variable ();
1668 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1669 use it for indirect inlining), we should propagate them too. */
1670 return dest_lat
->set_contains_variable ();
1673 /* Propagate scalar values across jump function JFUNC that is associated with
1674 edge CS and describes argument IDX and put the values into DEST_LAT. */
1677 propagate_context_across_jump_function (cgraph_edge
*cs
,
1678 ipa_jump_func
*jfunc
, int idx
,
1679 ipcp_lattice
<ipa_polymorphic_call_context
> *dest_lat
)
1681 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
1682 if (dest_lat
->bottom
)
1685 bool added_sth
= false;
1686 bool type_preserved
= true;
1688 ipa_polymorphic_call_context edge_ctx
, *edge_ctx_ptr
1689 = ipa_get_ith_polymorhic_call_context (args
, idx
);
1692 edge_ctx
= *edge_ctx_ptr
;
1694 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1695 || jfunc
->type
== IPA_JF_ANCESTOR
)
1697 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1699 ipcp_lattice
<ipa_polymorphic_call_context
> *src_lat
;
1701 /* TODO: Once we figure out how to propagate speculations, it will
1702 probably be a good idea to switch to speculation if type_preserved is
1703 not set instead of punting. */
1704 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1706 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1708 type_preserved
= ipa_get_jf_pass_through_type_preserved (jfunc
);
1709 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1713 type_preserved
= ipa_get_jf_ancestor_type_preserved (jfunc
);
1714 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1717 src_lat
= ipa_get_poly_ctx_lat (caller_info
, src_idx
);
1718 /* If we would need to clone the caller and cannot, do not propagate. */
1719 if (!ipcp_versionable_function_p (cs
->caller
)
1720 && (src_lat
->contains_variable
1721 || (src_lat
->values_count
> 1)))
1724 ipcp_value
<ipa_polymorphic_call_context
> *src_val
;
1725 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1727 ipa_polymorphic_call_context cur
= src_val
->value
;
1729 if (!type_preserved
)
1730 cur
.possible_dynamic_type_change (cs
->in_polymorphic_cdtor
);
1731 if (jfunc
->type
== IPA_JF_ANCESTOR
)
1732 cur
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
1733 /* TODO: In cases we know how the context is going to be used,
1734 we can improve the result by passing proper OTR_TYPE. */
1735 cur
.combine_with (edge_ctx
);
1736 if (!cur
.useless_p ())
1738 if (src_lat
->contains_variable
1739 && !edge_ctx
.equal_to (cur
))
1740 ret
|= dest_lat
->set_contains_variable ();
1741 ret
|= dest_lat
->add_value (cur
, cs
, src_val
, src_idx
);
1751 if (!edge_ctx
.useless_p ())
1752 ret
|= dest_lat
->add_value (edge_ctx
, cs
);
1754 ret
|= dest_lat
->set_contains_variable ();
1760 /* Propagate bits across jfunc that is associated with
1761 edge cs and update dest_lattice accordingly. */
1764 propagate_bits_across_jump_function (cgraph_edge
*cs
, int idx
,
1765 ipa_jump_func
*jfunc
,
1766 ipcp_bits_lattice
*dest_lattice
)
1768 if (dest_lattice
->bottom_p ())
1771 enum availability availability
;
1772 cgraph_node
*callee
= cs
->callee
->function_symbol (&availability
);
1773 struct ipa_node_params
*callee_info
= IPA_NODE_REF (callee
);
1774 tree parm_type
= ipa_get_type (callee_info
, idx
);
1776 /* For K&R C programs, ipa_get_type() could return NULL_TREE.
1777 Avoid the transform for these cases. */
1780 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1781 fprintf (dump_file
, "Setting dest_lattice to bottom, because"
1782 " param %i type is NULL for %s\n", idx
,
1783 cs
->callee
->name ());
1785 return dest_lattice
->set_to_bottom ();
1788 unsigned precision
= TYPE_PRECISION (parm_type
);
1789 signop sgn
= TYPE_SIGN (parm_type
);
1791 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1792 || jfunc
->type
== IPA_JF_ANCESTOR
)
1794 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1795 tree operand
= NULL_TREE
;
1796 enum tree_code code
;
1799 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1801 code
= ipa_get_jf_pass_through_operation (jfunc
);
1802 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1803 if (code
!= NOP_EXPR
)
1804 operand
= ipa_get_jf_pass_through_operand (jfunc
);
1808 code
= POINTER_PLUS_EXPR
;
1809 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1810 unsigned HOST_WIDE_INT offset
= ipa_get_jf_ancestor_offset (jfunc
) / BITS_PER_UNIT
;
1811 operand
= build_int_cstu (size_type_node
, offset
);
1814 struct ipcp_param_lattices
*src_lats
1815 = ipa_get_parm_lattices (caller_info
, src_idx
);
1817 /* Try to propagate bits if src_lattice is bottom, but jfunc is known.
1823 Assume lattice for x is bottom, however we can still propagate
1824 result of x & 0xff == 0xff, which gets computed during ccp1 pass
1825 and we store it in jump function during analysis stage. */
1827 if (src_lats
->bits_lattice
.bottom_p ()
1829 return dest_lattice
->meet_with (jfunc
->bits
->value
, jfunc
->bits
->mask
,
1832 return dest_lattice
->meet_with (src_lats
->bits_lattice
, precision
, sgn
,
1836 else if (jfunc
->type
== IPA_JF_ANCESTOR
)
1837 return dest_lattice
->set_to_bottom ();
1838 else if (jfunc
->bits
)
1839 return dest_lattice
->meet_with (jfunc
->bits
->value
, jfunc
->bits
->mask
,
1842 return dest_lattice
->set_to_bottom ();
1845 /* Emulate effects of unary OPERATION and/or conversion from SRC_TYPE to
1846 DST_TYPE on value range in SRC_VR and store it to DST_VR. Return true if
1847 the result is a range or an anti-range. */
1850 ipa_vr_operation_and_type_effects (value_range
*dst_vr
, value_range
*src_vr
,
1851 enum tree_code operation
,
1852 tree dst_type
, tree src_type
)
1854 memset (dst_vr
, 0, sizeof (*dst_vr
));
1855 extract_range_from_unary_expr (dst_vr
, operation
, dst_type
, src_vr
, src_type
);
1856 if (dst_vr
->type
== VR_RANGE
|| dst_vr
->type
== VR_ANTI_RANGE
)
1862 /* Propagate value range across jump function JFUNC that is associated with
1863 edge CS with param of callee of PARAM_TYPE and update DEST_PLATS
1867 propagate_vr_across_jump_function (cgraph_edge
*cs
, ipa_jump_func
*jfunc
,
1868 struct ipcp_param_lattices
*dest_plats
,
1871 ipcp_vr_lattice
*dest_lat
= &dest_plats
->m_value_range
;
1873 if (dest_lat
->bottom_p ())
1877 || (!INTEGRAL_TYPE_P (param_type
)
1878 && !POINTER_TYPE_P (param_type
)))
1879 return dest_lat
->set_to_bottom ();
1881 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1883 enum tree_code operation
= ipa_get_jf_pass_through_operation (jfunc
);
1885 if (TREE_CODE_CLASS (operation
) == tcc_unary
)
1887 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1888 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1889 tree operand_type
= ipa_get_type (caller_info
, src_idx
);
1890 struct ipcp_param_lattices
*src_lats
1891 = ipa_get_parm_lattices (caller_info
, src_idx
);
1893 if (src_lats
->m_value_range
.bottom_p ())
1894 return dest_lat
->set_to_bottom ();
1896 if (ipa_vr_operation_and_type_effects (&vr
,
1897 &src_lats
->m_value_range
.m_vr
,
1898 operation
, param_type
,
1900 return dest_lat
->meet_with (&vr
);
1903 else if (jfunc
->type
== IPA_JF_CONST
)
1905 tree val
= ipa_get_jf_constant (jfunc
);
1906 if (TREE_CODE (val
) == INTEGER_CST
)
1908 val
= fold_convert (param_type
, val
);
1909 if (TREE_OVERFLOW_P (val
))
1910 val
= drop_tree_overflow (val
);
1913 memset (&tmpvr
, 0, sizeof (tmpvr
));
1914 tmpvr
.type
= VR_RANGE
;
1917 return dest_lat
->meet_with (&tmpvr
);
1923 && ipa_vr_operation_and_type_effects (&vr
, jfunc
->m_vr
, NOP_EXPR
,
1925 TREE_TYPE (jfunc
->m_vr
->min
)))
1926 return dest_lat
->meet_with (&vr
);
1928 return dest_lat
->set_to_bottom ();
1931 /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
1932 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
1933 other cases, return false). If there are no aggregate items, set
1934 aggs_by_ref to NEW_AGGS_BY_REF. */
1937 set_check_aggs_by_ref (struct ipcp_param_lattices
*dest_plats
,
1938 bool new_aggs_by_ref
)
1940 if (dest_plats
->aggs
)
1942 if (dest_plats
->aggs_by_ref
!= new_aggs_by_ref
)
1944 set_agg_lats_to_bottom (dest_plats
);
1949 dest_plats
->aggs_by_ref
= new_aggs_by_ref
;
1953 /* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
1954 already existing lattice for the given OFFSET and SIZE, marking all skipped
1955 lattices as containing variable and checking for overlaps. If there is no
1956 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
1957 it with offset, size and contains_variable to PRE_EXISTING, and return true,
1958 unless there are too many already. If there are two many, return false. If
1959 there are overlaps turn whole DEST_PLATS to bottom and return false. If any
1960 skipped lattices were newly marked as containing variable, set *CHANGE to
1964 merge_agg_lats_step (struct ipcp_param_lattices
*dest_plats
,
1965 HOST_WIDE_INT offset
, HOST_WIDE_INT val_size
,
1966 struct ipcp_agg_lattice
***aglat
,
1967 bool pre_existing
, bool *change
)
1969 gcc_checking_assert (offset
>= 0);
1971 while (**aglat
&& (**aglat
)->offset
< offset
)
1973 if ((**aglat
)->offset
+ (**aglat
)->size
> offset
)
1975 set_agg_lats_to_bottom (dest_plats
);
1978 *change
|= (**aglat
)->set_contains_variable ();
1979 *aglat
= &(**aglat
)->next
;
1982 if (**aglat
&& (**aglat
)->offset
== offset
)
1984 if ((**aglat
)->size
!= val_size
1986 && (**aglat
)->next
->offset
< offset
+ val_size
))
1988 set_agg_lats_to_bottom (dest_plats
);
1991 gcc_checking_assert (!(**aglat
)->next
1992 || (**aglat
)->next
->offset
>= offset
+ val_size
);
1997 struct ipcp_agg_lattice
*new_al
;
1999 if (**aglat
&& (**aglat
)->offset
< offset
+ val_size
)
2001 set_agg_lats_to_bottom (dest_plats
);
2004 if (dest_plats
->aggs_count
== PARAM_VALUE (PARAM_IPA_MAX_AGG_ITEMS
))
2006 dest_plats
->aggs_count
++;
2007 new_al
= ipcp_agg_lattice_pool
.allocate ();
2008 memset (new_al
, 0, sizeof (*new_al
));
2010 new_al
->offset
= offset
;
2011 new_al
->size
= val_size
;
2012 new_al
->contains_variable
= pre_existing
;
2014 new_al
->next
= **aglat
;
2020 /* Set all AGLAT and all other aggregate lattices reachable by next pointers as
2021 containing an unknown value. */
2024 set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice
*aglat
)
2029 ret
|= aglat
->set_contains_variable ();
2030 aglat
= aglat
->next
;
2035 /* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
2036 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source
2037 parameter used for lattice value sources. Return true if DEST_PLATS changed
2041 merge_aggregate_lattices (struct cgraph_edge
*cs
,
2042 struct ipcp_param_lattices
*dest_plats
,
2043 struct ipcp_param_lattices
*src_plats
,
2044 int src_idx
, HOST_WIDE_INT offset_delta
)
2046 bool pre_existing
= dest_plats
->aggs
!= NULL
;
2047 struct ipcp_agg_lattice
**dst_aglat
;
2050 if (set_check_aggs_by_ref (dest_plats
, src_plats
->aggs_by_ref
))
2052 if (src_plats
->aggs_bottom
)
2053 return set_agg_lats_contain_variable (dest_plats
);
2054 if (src_plats
->aggs_contain_variable
)
2055 ret
|= set_agg_lats_contain_variable (dest_plats
);
2056 dst_aglat
= &dest_plats
->aggs
;
2058 for (struct ipcp_agg_lattice
*src_aglat
= src_plats
->aggs
;
2060 src_aglat
= src_aglat
->next
)
2062 HOST_WIDE_INT new_offset
= src_aglat
->offset
- offset_delta
;
2066 if (merge_agg_lats_step (dest_plats
, new_offset
, src_aglat
->size
,
2067 &dst_aglat
, pre_existing
, &ret
))
2069 struct ipcp_agg_lattice
*new_al
= *dst_aglat
;
2071 dst_aglat
= &(*dst_aglat
)->next
;
2072 if (src_aglat
->bottom
)
2074 ret
|= new_al
->set_contains_variable ();
2077 if (src_aglat
->contains_variable
)
2078 ret
|= new_al
->set_contains_variable ();
2079 for (ipcp_value
<tree
> *val
= src_aglat
->values
;
2082 ret
|= new_al
->add_value (val
->value
, cs
, val
, src_idx
,
2085 else if (dest_plats
->aggs_bottom
)
2088 ret
|= set_chain_of_aglats_contains_variable (*dst_aglat
);
2092 /* Determine whether there is anything to propagate FROM SRC_PLATS through a
2093 pass-through JFUNC and if so, whether it has conform and conforms to the
2094 rules about propagating values passed by reference. */
2097 agg_pass_through_permissible_p (struct ipcp_param_lattices
*src_plats
,
2098 struct ipa_jump_func
*jfunc
)
2100 return src_plats
->aggs
2101 && (!src_plats
->aggs_by_ref
2102 || ipa_get_jf_pass_through_agg_preserved (jfunc
));
2105 /* Propagate scalar values across jump function JFUNC that is associated with
2106 edge CS and put the values into DEST_LAT. */
2109 propagate_aggs_across_jump_function (struct cgraph_edge
*cs
,
2110 struct ipa_jump_func
*jfunc
,
2111 struct ipcp_param_lattices
*dest_plats
)
2115 if (dest_plats
->aggs_bottom
)
2118 if (jfunc
->type
== IPA_JF_PASS_THROUGH
2119 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
2121 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2122 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
2123 struct ipcp_param_lattices
*src_plats
;
2125 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2126 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
2128 /* Currently we do not produce clobber aggregate jump
2129 functions, replace with merging when we do. */
2130 gcc_assert (!jfunc
->agg
.items
);
2131 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
,
2135 ret
|= set_agg_lats_contain_variable (dest_plats
);
2137 else if (jfunc
->type
== IPA_JF_ANCESTOR
2138 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
2140 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2141 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
2142 struct ipcp_param_lattices
*src_plats
;
2144 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2145 if (src_plats
->aggs
&& src_plats
->aggs_by_ref
)
2147 /* Currently we do not produce clobber aggregate jump
2148 functions, replace with merging when we do. */
2149 gcc_assert (!jfunc
->agg
.items
);
2150 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
, src_idx
,
2151 ipa_get_jf_ancestor_offset (jfunc
));
2153 else if (!src_plats
->aggs_by_ref
)
2154 ret
|= set_agg_lats_to_bottom (dest_plats
);
2156 ret
|= set_agg_lats_contain_variable (dest_plats
);
2158 else if (jfunc
->agg
.items
)
2160 bool pre_existing
= dest_plats
->aggs
!= NULL
;
2161 struct ipcp_agg_lattice
**aglat
= &dest_plats
->aggs
;
2162 struct ipa_agg_jf_item
*item
;
2165 if (set_check_aggs_by_ref (dest_plats
, jfunc
->agg
.by_ref
))
2168 FOR_EACH_VEC_ELT (*jfunc
->agg
.items
, i
, item
)
2170 HOST_WIDE_INT val_size
;
2172 if (item
->offset
< 0)
2174 gcc_checking_assert (is_gimple_ip_invariant (item
->value
));
2175 val_size
= tree_to_uhwi (TYPE_SIZE (TREE_TYPE (item
->value
)));
2177 if (merge_agg_lats_step (dest_plats
, item
->offset
, val_size
,
2178 &aglat
, pre_existing
, &ret
))
2180 ret
|= (*aglat
)->add_value (item
->value
, cs
, NULL
, 0, 0);
2181 aglat
= &(*aglat
)->next
;
2183 else if (dest_plats
->aggs_bottom
)
2187 ret
|= set_chain_of_aglats_contains_variable (*aglat
);
2190 ret
|= set_agg_lats_contain_variable (dest_plats
);
2195 /* Return true if on the way cfrom CS->caller to the final (non-alias and
2196 non-thunk) destination, the call passes through a thunk. */
2199 call_passes_through_thunk_p (cgraph_edge
*cs
)
2201 cgraph_node
*alias_or_thunk
= cs
->callee
;
2202 while (alias_or_thunk
->alias
)
2203 alias_or_thunk
= alias_or_thunk
->get_alias_target ();
2204 return alias_or_thunk
->thunk
.thunk_p
;
2207 /* Propagate constants from the caller to the callee of CS. INFO describes the
2211 propagate_constants_across_call (struct cgraph_edge
*cs
)
2213 struct ipa_node_params
*callee_info
;
2214 enum availability availability
;
2215 cgraph_node
*callee
;
2216 struct ipa_edge_args
*args
;
2218 int i
, args_count
, parms_count
;
2220 callee
= cs
->callee
->function_symbol (&availability
);
2221 if (!callee
->definition
)
2223 gcc_checking_assert (callee
->has_gimple_body_p ());
2224 callee_info
= IPA_NODE_REF (callee
);
2226 args
= IPA_EDGE_REF (cs
);
2227 args_count
= ipa_get_cs_argument_count (args
);
2228 parms_count
= ipa_get_param_count (callee_info
);
2229 if (parms_count
== 0)
2232 /* No propagation through instrumentation thunks is available yet.
2233 It should be possible with proper mapping of call args and
2234 instrumented callee params in the propagation loop below. But
2235 this case mostly occurs when legacy code calls instrumented code
2236 and it is not a primary target for optimizations.
2237 We detect instrumentation thunks in aliases and thunks chain by
2238 checking instrumentation_clone flag for chain source and target.
2239 Going through instrumentation thunks we always have it changed
2240 from 0 to 1 and all other nodes do not change it. */
2241 if (!cs
->callee
->instrumentation_clone
2242 && callee
->instrumentation_clone
)
2244 for (i
= 0; i
< parms_count
; i
++)
2245 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
2250 /* If this call goes through a thunk we must not propagate to the first (0th)
2251 parameter. However, we might need to uncover a thunk from below a series
2252 of aliases first. */
2253 if (call_passes_through_thunk_p (cs
))
2255 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
2262 for (; (i
< args_count
) && (i
< parms_count
); i
++)
2264 struct ipa_jump_func
*jump_func
= ipa_get_ith_jump_func (args
, i
);
2265 struct ipcp_param_lattices
*dest_plats
;
2266 tree param_type
= ipa_get_type (callee_info
, i
);
2268 dest_plats
= ipa_get_parm_lattices (callee_info
, i
);
2269 if (availability
== AVAIL_INTERPOSABLE
)
2270 ret
|= set_all_contains_variable (dest_plats
);
2273 ret
|= propagate_scalar_across_jump_function (cs
, jump_func
,
2274 &dest_plats
->itself
);
2275 ret
|= propagate_context_across_jump_function (cs
, jump_func
, i
,
2276 &dest_plats
->ctxlat
);
2278 |= propagate_bits_across_jump_function (cs
, i
, jump_func
,
2279 &dest_plats
->bits_lattice
);
2280 ret
|= propagate_aggs_across_jump_function (cs
, jump_func
,
2282 if (opt_for_fn (callee
->decl
, flag_ipa_vrp
))
2283 ret
|= propagate_vr_across_jump_function (cs
, jump_func
,
2284 dest_plats
, param_type
);
2286 ret
|= dest_plats
->m_value_range
.set_to_bottom ();
2289 for (; i
< parms_count
; i
++)
2290 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
, i
));
2295 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
2296 KNOWN_CONTEXTS, KNOWN_AGGS or AGG_REPS return the destination. The latter
2297 three can be NULL. If AGG_REPS is not NULL, KNOWN_AGGS is ignored. */
2300 ipa_get_indirect_edge_target_1 (struct cgraph_edge
*ie
,
2301 vec
<tree
> known_csts
,
2302 vec
<ipa_polymorphic_call_context
> known_contexts
,
2303 vec
<ipa_agg_jump_function_p
> known_aggs
,
2304 struct ipa_agg_replacement_value
*agg_reps
,
2307 int param_index
= ie
->indirect_info
->param_index
;
2308 HOST_WIDE_INT anc_offset
;
2312 *speculative
= false;
2314 if (param_index
== -1
2315 || known_csts
.length () <= (unsigned int) param_index
)
2318 if (!ie
->indirect_info
->polymorphic
)
2322 if (ie
->indirect_info
->agg_contents
)
2325 if (agg_reps
&& ie
->indirect_info
->guaranteed_unmodified
)
2329 if (agg_reps
->index
== param_index
2330 && agg_reps
->offset
== ie
->indirect_info
->offset
2331 && agg_reps
->by_ref
== ie
->indirect_info
->by_ref
)
2333 t
= agg_reps
->value
;
2336 agg_reps
= agg_reps
->next
;
2341 struct ipa_agg_jump_function
*agg
;
2342 if (known_aggs
.length () > (unsigned int) param_index
)
2343 agg
= known_aggs
[param_index
];
2346 bool from_global_constant
;
2347 t
= ipa_find_agg_cst_for_param (agg
, known_csts
[param_index
],
2348 ie
->indirect_info
->offset
,
2349 ie
->indirect_info
->by_ref
,
2350 &from_global_constant
);
2352 && !from_global_constant
2353 && !ie
->indirect_info
->guaranteed_unmodified
)
2358 t
= known_csts
[param_index
];
2361 && TREE_CODE (t
) == ADDR_EXPR
2362 && TREE_CODE (TREE_OPERAND (t
, 0)) == FUNCTION_DECL
)
2363 return TREE_OPERAND (t
, 0);
2368 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize
))
2371 gcc_assert (!ie
->indirect_info
->agg_contents
);
2372 anc_offset
= ie
->indirect_info
->offset
;
2376 /* Try to work out value of virtual table pointer value in replacemnets. */
2377 if (!t
&& agg_reps
&& !ie
->indirect_info
->by_ref
)
2381 if (agg_reps
->index
== param_index
2382 && agg_reps
->offset
== ie
->indirect_info
->offset
2383 && agg_reps
->by_ref
)
2385 t
= agg_reps
->value
;
2388 agg_reps
= agg_reps
->next
;
2392 /* Try to work out value of virtual table pointer value in known
2393 aggregate values. */
2394 if (!t
&& known_aggs
.length () > (unsigned int) param_index
2395 && !ie
->indirect_info
->by_ref
)
2397 struct ipa_agg_jump_function
*agg
;
2398 agg
= known_aggs
[param_index
];
2399 t
= ipa_find_agg_cst_for_param (agg
, known_csts
[param_index
],
2400 ie
->indirect_info
->offset
, true);
2403 /* If we found the virtual table pointer, lookup the target. */
2407 unsigned HOST_WIDE_INT offset
;
2408 if (vtable_pointer_value_to_vtable (t
, &vtable
, &offset
))
2411 target
= gimple_get_virt_method_for_vtable (ie
->indirect_info
->otr_token
,
2412 vtable
, offset
, &can_refer
);
2416 || (TREE_CODE (TREE_TYPE (target
)) == FUNCTION_TYPE
2417 && DECL_FUNCTION_CODE (target
) == BUILT_IN_UNREACHABLE
)
2418 || !possible_polymorphic_call_target_p
2419 (ie
, cgraph_node::get (target
)))
2421 /* Do not speculate builtin_unreachable, it is stupid! */
2422 if (ie
->indirect_info
->vptr_changed
)
2424 target
= ipa_impossible_devirt_target (ie
, target
);
2426 *speculative
= ie
->indirect_info
->vptr_changed
;
2433 /* Do we know the constant value of pointer? */
2435 t
= known_csts
[param_index
];
2437 gcc_checking_assert (!t
|| TREE_CODE (t
) != TREE_BINFO
);
2439 ipa_polymorphic_call_context context
;
2440 if (known_contexts
.length () > (unsigned int) param_index
)
2442 context
= known_contexts
[param_index
];
2443 context
.offset_by (anc_offset
);
2444 if (ie
->indirect_info
->vptr_changed
)
2445 context
.possible_dynamic_type_change (ie
->in_polymorphic_cdtor
,
2446 ie
->indirect_info
->otr_type
);
2449 ipa_polymorphic_call_context ctx2
= ipa_polymorphic_call_context
2450 (t
, ie
->indirect_info
->otr_type
, anc_offset
);
2451 if (!ctx2
.useless_p ())
2452 context
.combine_with (ctx2
, ie
->indirect_info
->otr_type
);
2457 context
= ipa_polymorphic_call_context (t
, ie
->indirect_info
->otr_type
,
2459 if (ie
->indirect_info
->vptr_changed
)
2460 context
.possible_dynamic_type_change (ie
->in_polymorphic_cdtor
,
2461 ie
->indirect_info
->otr_type
);
2466 vec
<cgraph_node
*>targets
;
2469 targets
= possible_polymorphic_call_targets
2470 (ie
->indirect_info
->otr_type
,
2471 ie
->indirect_info
->otr_token
,
2473 if (!final
|| targets
.length () > 1)
2475 struct cgraph_node
*node
;
2478 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize_speculatively
)
2479 || ie
->speculative
|| !ie
->maybe_hot_p ())
2481 node
= try_speculative_devirtualization (ie
->indirect_info
->otr_type
,
2482 ie
->indirect_info
->otr_token
,
2486 *speculative
= true;
2487 target
= node
->decl
;
2494 *speculative
= false;
2495 if (targets
.length () == 1)
2496 target
= targets
[0]->decl
;
2498 target
= ipa_impossible_devirt_target (ie
, NULL_TREE
);
2501 if (target
&& !possible_polymorphic_call_target_p (ie
,
2502 cgraph_node::get (target
)))
2506 target
= ipa_impossible_devirt_target (ie
, target
);
2513 /* If an indirect edge IE can be turned into a direct one based on KNOWN_CSTS,
2514 KNOWN_CONTEXTS (which can be vNULL) or KNOWN_AGGS (which also can be vNULL)
2515 return the destination. */
2518 ipa_get_indirect_edge_target (struct cgraph_edge
*ie
,
2519 vec
<tree
> known_csts
,
2520 vec
<ipa_polymorphic_call_context
> known_contexts
,
2521 vec
<ipa_agg_jump_function_p
> known_aggs
,
2524 return ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
2525 known_aggs
, NULL
, speculative
);
2528 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
2529 and KNOWN_CONTEXTS. */
2532 devirtualization_time_bonus (struct cgraph_node
*node
,
2533 vec
<tree
> known_csts
,
2534 vec
<ipa_polymorphic_call_context
> known_contexts
,
2535 vec
<ipa_agg_jump_function_p
> known_aggs
)
2537 struct cgraph_edge
*ie
;
2540 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
2542 struct cgraph_node
*callee
;
2543 struct inline_summary
*isummary
;
2544 enum availability avail
;
2548 target
= ipa_get_indirect_edge_target (ie
, known_csts
, known_contexts
,
2549 known_aggs
, &speculative
);
2553 /* Only bare minimum benefit for clearly un-inlineable targets. */
2555 callee
= cgraph_node::get (target
);
2556 if (!callee
|| !callee
->definition
)
2558 callee
= callee
->function_symbol (&avail
);
2559 if (avail
< AVAIL_AVAILABLE
)
2561 isummary
= inline_summaries
->get (callee
);
2562 if (!isummary
->inlinable
)
2565 /* FIXME: The values below need re-considering and perhaps also
2566 integrating into the cost metrics, at lest in some very basic way. */
2567 if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 4)
2568 res
+= 31 / ((int)speculative
+ 1);
2569 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 2)
2570 res
+= 15 / ((int)speculative
+ 1);
2571 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
2572 || DECL_DECLARED_INLINE_P (callee
->decl
))
2573 res
+= 7 / ((int)speculative
+ 1);
2579 /* Return time bonus incurred because of HINTS. */
2582 hint_time_bonus (inline_hints hints
)
2585 if (hints
& (INLINE_HINT_loop_iterations
| INLINE_HINT_loop_stride
))
2586 result
+= PARAM_VALUE (PARAM_IPA_CP_LOOP_HINT_BONUS
);
2587 if (hints
& INLINE_HINT_array_index
)
2588 result
+= PARAM_VALUE (PARAM_IPA_CP_ARRAY_INDEX_HINT_BONUS
);
2592 /* If there is a reason to penalize the function described by INFO in the
2593 cloning goodness evaluation, do so. */
2595 static inline int64_t
2596 incorporate_penalties (ipa_node_params
*info
, int64_t evaluation
)
2598 if (info
->node_within_scc
)
2599 evaluation
= (evaluation
2600 * (100 - PARAM_VALUE (PARAM_IPA_CP_RECURSION_PENALTY
))) / 100;
2602 if (info
->node_calling_single_call
)
2603 evaluation
= (evaluation
2604 * (100 - PARAM_VALUE (PARAM_IPA_CP_SINGLE_CALL_PENALTY
)))
2610 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
2611 and SIZE_COST and with the sum of frequencies of incoming edges to the
2612 potential new clone in FREQUENCIES. */
2615 good_cloning_opportunity_p (struct cgraph_node
*node
, int time_benefit
,
2616 int freq_sum
, gcov_type count_sum
, int size_cost
)
2618 if (time_benefit
== 0
2619 || !opt_for_fn (node
->decl
, flag_ipa_cp_clone
)
2620 || node
->optimize_for_size_p ())
2623 gcc_assert (size_cost
> 0);
2625 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2628 int factor
= (count_sum
* 1000) / max_count
;
2629 int64_t evaluation
= (((int64_t) time_benefit
* factor
)
2631 evaluation
= incorporate_penalties (info
, evaluation
);
2633 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2634 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
2635 "size: %i, count_sum: " HOST_WIDE_INT_PRINT_DEC
2636 "%s%s) -> evaluation: " "%" PRId64
2637 ", threshold: %i\n",
2638 time_benefit
, size_cost
, (HOST_WIDE_INT
) count_sum
,
2639 info
->node_within_scc
? ", scc" : "",
2640 info
->node_calling_single_call
? ", single_call" : "",
2641 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
2643 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
2647 int64_t evaluation
= (((int64_t) time_benefit
* freq_sum
)
2649 evaluation
= incorporate_penalties (info
, evaluation
);
2651 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2652 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
2653 "size: %i, freq_sum: %i%s%s) -> evaluation: "
2654 "%" PRId64
", threshold: %i\n",
2655 time_benefit
, size_cost
, freq_sum
,
2656 info
->node_within_scc
? ", scc" : "",
2657 info
->node_calling_single_call
? ", single_call" : "",
2658 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
2660 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
2664 /* Return all context independent values from aggregate lattices in PLATS in a
2665 vector. Return NULL if there are none. */
2667 static vec
<ipa_agg_jf_item
, va_gc
> *
2668 context_independent_aggregate_values (struct ipcp_param_lattices
*plats
)
2670 vec
<ipa_agg_jf_item
, va_gc
> *res
= NULL
;
2672 if (plats
->aggs_bottom
2673 || plats
->aggs_contain_variable
2674 || plats
->aggs_count
== 0)
2677 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
;
2679 aglat
= aglat
->next
)
2680 if (aglat
->is_single_const ())
2682 struct ipa_agg_jf_item item
;
2683 item
.offset
= aglat
->offset
;
2684 item
.value
= aglat
->values
->value
;
2685 vec_safe_push (res
, item
);
2690 /* Allocate KNOWN_CSTS, KNOWN_CONTEXTS and, if non-NULL, KNOWN_AGGS and
2691 populate them with values of parameters that are known independent of the
2692 context. INFO describes the function. If REMOVABLE_PARAMS_COST is
2693 non-NULL, the movement cost of all removable parameters will be stored in
2697 gather_context_independent_values (struct ipa_node_params
*info
,
2698 vec
<tree
> *known_csts
,
2699 vec
<ipa_polymorphic_call_context
>
2701 vec
<ipa_agg_jump_function
> *known_aggs
,
2702 int *removable_params_cost
)
2704 int i
, count
= ipa_get_param_count (info
);
2707 known_csts
->create (0);
2708 known_contexts
->create (0);
2709 known_csts
->safe_grow_cleared (count
);
2710 known_contexts
->safe_grow_cleared (count
);
2713 known_aggs
->create (0);
2714 known_aggs
->safe_grow_cleared (count
);
2717 if (removable_params_cost
)
2718 *removable_params_cost
= 0;
2720 for (i
= 0; i
< count
; i
++)
2722 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2723 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
2725 if (lat
->is_single_const ())
2727 ipcp_value
<tree
> *val
= lat
->values
;
2728 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
2729 (*known_csts
)[i
] = val
->value
;
2730 if (removable_params_cost
)
2731 *removable_params_cost
2732 += estimate_move_cost (TREE_TYPE (val
->value
), false);
2735 else if (removable_params_cost
2736 && !ipa_is_param_used (info
, i
))
2737 *removable_params_cost
2738 += ipa_get_param_move_cost (info
, i
);
2740 if (!ipa_is_param_used (info
, i
))
2743 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
2744 /* Do not account known context as reason for cloning. We can see
2745 if it permits devirtualization. */
2746 if (ctxlat
->is_single_const ())
2747 (*known_contexts
)[i
] = ctxlat
->values
->value
;
2751 vec
<ipa_agg_jf_item
, va_gc
> *agg_items
;
2752 struct ipa_agg_jump_function
*ajf
;
2754 agg_items
= context_independent_aggregate_values (plats
);
2755 ajf
= &(*known_aggs
)[i
];
2756 ajf
->items
= agg_items
;
2757 ajf
->by_ref
= plats
->aggs_by_ref
;
2758 ret
|= agg_items
!= NULL
;
2765 /* The current interface in ipa-inline-analysis requires a pointer vector.
2768 FIXME: That interface should be re-worked, this is slightly silly. Still,
2769 I'd like to discuss how to change it first and this demonstrates the
2772 static vec
<ipa_agg_jump_function_p
>
2773 agg_jmp_p_vec_for_t_vec (vec
<ipa_agg_jump_function
> known_aggs
)
2775 vec
<ipa_agg_jump_function_p
> ret
;
2776 struct ipa_agg_jump_function
*ajf
;
2779 ret
.create (known_aggs
.length ());
2780 FOR_EACH_VEC_ELT (known_aggs
, i
, ajf
)
2781 ret
.quick_push (ajf
);
2785 /* Perform time and size measurement of NODE with the context given in
2786 KNOWN_CSTS, KNOWN_CONTEXTS and KNOWN_AGGS, calculate the benefit and cost
2787 given BASE_TIME of the node without specialization, REMOVABLE_PARAMS_COST of
2788 all context-independent removable parameters and EST_MOVE_COST of estimated
2789 movement of the considered parameter and store it into VAL. */
2792 perform_estimation_of_a_value (cgraph_node
*node
, vec
<tree
> known_csts
,
2793 vec
<ipa_polymorphic_call_context
> known_contexts
,
2794 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
,
2795 sreal base_time
, int removable_params_cost
,
2796 int est_move_cost
, ipcp_value_base
*val
)
2798 int size
, time_benefit
;
2802 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
2803 known_aggs_ptrs
, &size
, &time
,
2806 if (base_time
> 65535)
2808 time_benefit
= base_time
.to_int ()
2809 + devirtualization_time_bonus (node
, known_csts
, known_contexts
,
2811 + hint_time_bonus (hints
)
2812 + removable_params_cost
+ est_move_cost
;
2814 gcc_checking_assert (size
>=0);
2815 /* The inliner-heuristics based estimates may think that in certain
2816 contexts some functions do not have any size at all but we want
2817 all specializations to have at least a tiny cost, not least not to
2822 val
->local_time_benefit
= time_benefit
;
2823 val
->local_size_cost
= size
;
2826 /* Iterate over known values of parameters of NODE and estimate the local
2827 effects in terms of time and size they have. */
2830 estimate_local_effects (struct cgraph_node
*node
)
2832 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2833 int i
, count
= ipa_get_param_count (info
);
2834 vec
<tree
> known_csts
;
2835 vec
<ipa_polymorphic_call_context
> known_contexts
;
2836 vec
<ipa_agg_jump_function
> known_aggs
;
2837 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
;
2839 sreal base_time
= inline_summaries
->get (node
)->time
.to_int ();
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/%i, base_time: %f.\n",
2847 node
->name (), node
->order
, base_time
.to_double ());
2849 always_const
= gather_context_independent_values (info
, &known_csts
,
2850 &known_contexts
, &known_aggs
,
2851 &removable_params_cost
);
2852 known_aggs_ptrs
= agg_jmp_p_vec_for_t_vec (known_aggs
);
2853 int devirt_bonus
= devirtualization_time_bonus (node
, known_csts
,
2854 known_contexts
, known_aggs_ptrs
);
2855 if (always_const
|| devirt_bonus
2856 || (removable_params_cost
&& node
->local
.can_change_signature
))
2858 struct caller_statistics stats
;
2863 init_caller_stats (&stats
);
2864 node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
2866 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
2867 known_aggs_ptrs
, &size
, &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;
2883 fprintf (dump_file
, " Decided to specialize for all "
2884 "known contexts, code not going to grow.\n");
2886 else if (good_cloning_opportunity_p (node
, (base_time
- time
).to_int (),
2887 stats
.freq_sum
, stats
.count_sum
,
2890 if (size
+ overall_size
<= max_new_size
)
2892 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
,
2929 known_aggs_ptrs
, base_time
,
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
,
2964 known_aggs_ptrs
, base_time
,
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
,
3008 known_aggs_ptrs
, base_time
,
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");
3250 ipa_update_after_lto_read ();
3253 FOR_EACH_DEFINED_FUNCTION (node
)
3255 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3257 determine_versionability (node
, info
);
3258 if (node
->has_gimple_body_p ())
3260 info
->lattices
= XCNEWVEC (struct ipcp_param_lattices
,
3261 ipa_get_param_count (info
));
3262 initialize_node_lattices (node
);
3264 if (node
->definition
&& !node
->alias
)
3265 overall_size
+= inline_summaries
->get (node
)->self_size
;
3266 if (node
->count
> max_count
)
3267 max_count
= node
->count
;
3270 max_new_size
= overall_size
;
3271 if (max_new_size
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
3272 max_new_size
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
3273 max_new_size
+= max_new_size
* PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH
) / 100 + 1;
3276 fprintf (dump_file
, "\noverall_size: %li, max_new_size: %li\n",
3277 overall_size
, max_new_size
);
3279 propagate_constants_topo (topo
);
3281 ipcp_verify_propagated_values ();
3282 topo
->constants
.propagate_effects ();
3283 topo
->contexts
.propagate_effects ();
3287 fprintf (dump_file
, "\nIPA lattices after all propagation:\n");
3288 print_all_lattices (dump_file
, (dump_flags
& TDF_DETAILS
), true);
3292 /* Discover newly direct outgoing edges from NODE which is a new clone with
3293 known KNOWN_CSTS and make them direct. */
3296 ipcp_discover_new_direct_edges (struct cgraph_node
*node
,
3297 vec
<tree
> known_csts
,
3298 vec
<ipa_polymorphic_call_context
>
3300 struct ipa_agg_replacement_value
*aggvals
)
3302 struct cgraph_edge
*ie
, *next_ie
;
3305 for (ie
= node
->indirect_calls
; ie
; ie
= next_ie
)
3310 next_ie
= ie
->next_callee
;
3311 target
= ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
3312 vNULL
, aggvals
, &speculative
);
3315 bool agg_contents
= ie
->indirect_info
->agg_contents
;
3316 bool polymorphic
= ie
->indirect_info
->polymorphic
;
3317 int param_index
= ie
->indirect_info
->param_index
;
3318 struct cgraph_edge
*cs
= ipa_make_edge_direct_to_target (ie
, target
,
3322 if (cs
&& !agg_contents
&& !polymorphic
)
3324 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3325 int c
= ipa_get_controlled_uses (info
, param_index
);
3326 if (c
!= IPA_UNDESCRIBED_USE
)
3328 struct ipa_ref
*to_del
;
3331 ipa_set_controlled_uses (info
, param_index
, c
);
3332 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3333 fprintf (dump_file
, " controlled uses count of param "
3334 "%i bumped down to %i\n", param_index
, c
);
3336 && (to_del
= node
->find_reference (cs
->callee
, NULL
, 0)))
3338 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3339 fprintf (dump_file
, " and even removing its "
3340 "cloning-created reference\n");
3341 to_del
->remove_reference ();
3347 /* Turning calls to direct calls will improve overall summary. */
3349 inline_update_overall_summary (node
);
3352 /* Vector of pointers which for linked lists of clones of an original crgaph
3355 static vec
<cgraph_edge
*> next_edge_clone
;
3356 static vec
<cgraph_edge
*> prev_edge_clone
;
3359 grow_edge_clone_vectors (void)
3361 if (next_edge_clone
.length ()
3362 <= (unsigned) symtab
->edges_max_uid
)
3363 next_edge_clone
.safe_grow_cleared (symtab
->edges_max_uid
+ 1);
3364 if (prev_edge_clone
.length ()
3365 <= (unsigned) symtab
->edges_max_uid
)
3366 prev_edge_clone
.safe_grow_cleared (symtab
->edges_max_uid
+ 1);
3369 /* Edge duplication hook to grow the appropriate linked list in
3373 ipcp_edge_duplication_hook (struct cgraph_edge
*src
, struct cgraph_edge
*dst
,
3376 grow_edge_clone_vectors ();
3378 struct cgraph_edge
*old_next
= next_edge_clone
[src
->uid
];
3380 prev_edge_clone
[old_next
->uid
] = dst
;
3381 prev_edge_clone
[dst
->uid
] = src
;
3383 next_edge_clone
[dst
->uid
] = old_next
;
3384 next_edge_clone
[src
->uid
] = dst
;
3387 /* Hook that is called by cgraph.c when an edge is removed. */
3390 ipcp_edge_removal_hook (struct cgraph_edge
*cs
, void *)
3392 grow_edge_clone_vectors ();
3394 struct cgraph_edge
*prev
= prev_edge_clone
[cs
->uid
];
3395 struct cgraph_edge
*next
= next_edge_clone
[cs
->uid
];
3397 next_edge_clone
[prev
->uid
] = next
;
3399 prev_edge_clone
[next
->uid
] = prev
;
3402 /* See if NODE is a clone with a known aggregate value at a given OFFSET of a
3403 parameter with the given INDEX. */
3406 get_clone_agg_value (struct cgraph_node
*node
, HOST_WIDE_INT offset
,
3409 struct ipa_agg_replacement_value
*aggval
;
3411 aggval
= ipa_get_agg_replacements_for_node (node
);
3414 if (aggval
->offset
== offset
3415 && aggval
->index
== index
)
3416 return aggval
->value
;
3417 aggval
= aggval
->next
;
3422 /* Return true is NODE is DEST or its clone for all contexts. */
3425 same_node_or_its_all_contexts_clone_p (cgraph_node
*node
, cgraph_node
*dest
)
3430 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3431 return info
->is_all_contexts_clone
&& info
->ipcp_orig_node
== dest
;
3434 /* Return true if edge CS does bring about the value described by SRC to node
3435 DEST or its clone for all contexts. */
3438 cgraph_edge_brings_value_p (cgraph_edge
*cs
, ipcp_value_source
<tree
> *src
,
3441 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3442 enum availability availability
;
3443 cgraph_node
*real_dest
= cs
->callee
->function_symbol (&availability
);
3445 if (!same_node_or_its_all_contexts_clone_p (real_dest
, dest
)
3446 || availability
<= AVAIL_INTERPOSABLE
3447 || caller_info
->node_dead
)
3452 if (caller_info
->ipcp_orig_node
)
3455 if (src
->offset
== -1)
3456 t
= caller_info
->known_csts
[src
->index
];
3458 t
= get_clone_agg_value (cs
->caller
, src
->offset
, src
->index
);
3459 return (t
!= NULL_TREE
3460 && values_equal_for_ipcp_p (src
->val
->value
, t
));
3464 struct ipcp_agg_lattice
*aglat
;
3465 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
3467 if (src
->offset
== -1)
3468 return (plats
->itself
.is_single_const ()
3469 && values_equal_for_ipcp_p (src
->val
->value
,
3470 plats
->itself
.values
->value
));
3473 if (plats
->aggs_bottom
|| plats
->aggs_contain_variable
)
3475 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3476 if (aglat
->offset
== src
->offset
)
3477 return (aglat
->is_single_const ()
3478 && values_equal_for_ipcp_p (src
->val
->value
,
3479 aglat
->values
->value
));
3485 /* Return true if edge CS does bring about the value described by SRC to node
3486 DEST or its clone for all contexts. */
3489 cgraph_edge_brings_value_p (cgraph_edge
*cs
,
3490 ipcp_value_source
<ipa_polymorphic_call_context
> *src
,
3493 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3494 cgraph_node
*real_dest
= cs
->callee
->function_symbol ();
3496 if (!same_node_or_its_all_contexts_clone_p (real_dest
, dest
)
3497 || caller_info
->node_dead
)
3502 if (caller_info
->ipcp_orig_node
)
3503 return (caller_info
->known_contexts
.length () > (unsigned) src
->index
)
3504 && values_equal_for_ipcp_p (src
->val
->value
,
3505 caller_info
->known_contexts
[src
->index
]);
3507 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
3509 return plats
->ctxlat
.is_single_const ()
3510 && values_equal_for_ipcp_p (src
->val
->value
,
3511 plats
->ctxlat
.values
->value
);
3514 /* Get the next clone in the linked list of clones of an edge. */
3516 static inline struct cgraph_edge
*
3517 get_next_cgraph_edge_clone (struct cgraph_edge
*cs
)
3519 return next_edge_clone
[cs
->uid
];
3522 /* Given VAL that is intended for DEST, iterate over all its sources and if
3523 they still hold, add their edge frequency and their number into *FREQUENCY
3524 and *CALLER_COUNT respectively. */
3526 template <typename valtype
>
3528 get_info_about_necessary_edges (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
3530 gcov_type
*count_sum
, int *caller_count
)
3532 ipcp_value_source
<valtype
> *src
;
3533 int freq
= 0, count
= 0;
3537 for (src
= val
->sources
; src
; src
= src
->next
)
3539 struct cgraph_edge
*cs
= src
->cs
;
3542 if (cgraph_edge_brings_value_p (cs
, src
, dest
))
3545 freq
+= cs
->frequency
;
3547 hot
|= cs
->maybe_hot_p ();
3549 cs
= get_next_cgraph_edge_clone (cs
);
3555 *caller_count
= count
;
3559 /* Return a vector of incoming edges that do bring value VAL to node DEST. It
3560 is assumed their number is known and equal to CALLER_COUNT. */
3562 template <typename valtype
>
3563 static vec
<cgraph_edge
*>
3564 gather_edges_for_value (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
3567 ipcp_value_source
<valtype
> *src
;
3568 vec
<cgraph_edge
*> ret
;
3570 ret
.create (caller_count
);
3571 for (src
= val
->sources
; src
; src
= src
->next
)
3573 struct cgraph_edge
*cs
= src
->cs
;
3576 if (cgraph_edge_brings_value_p (cs
, src
, dest
))
3577 ret
.quick_push (cs
);
3578 cs
= get_next_cgraph_edge_clone (cs
);
3585 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
3586 Return it or NULL if for some reason it cannot be created. */
3588 static struct ipa_replace_map
*
3589 get_replacement_map (struct ipa_node_params
*info
, tree value
, int parm_num
)
3591 struct ipa_replace_map
*replace_map
;
3594 replace_map
= ggc_alloc
<ipa_replace_map
> ();
3597 fprintf (dump_file
, " replacing ");
3598 ipa_dump_param (dump_file
, info
, parm_num
);
3600 fprintf (dump_file
, " with const ");
3601 print_generic_expr (dump_file
, value
, 0);
3602 fprintf (dump_file
, "\n");
3604 replace_map
->old_tree
= NULL
;
3605 replace_map
->parm_num
= parm_num
;
3606 replace_map
->new_tree
= value
;
3607 replace_map
->replace_p
= true;
3608 replace_map
->ref_p
= false;
3613 /* Dump new profiling counts */
3616 dump_profile_updates (struct cgraph_node
*orig_node
,
3617 struct cgraph_node
*new_node
)
3619 struct cgraph_edge
*cs
;
3621 fprintf (dump_file
, " setting count of the specialized node to "
3622 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) new_node
->count
);
3623 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3624 fprintf (dump_file
, " edge to %s has count "
3625 HOST_WIDE_INT_PRINT_DEC
"\n",
3626 cs
->callee
->name (), (HOST_WIDE_INT
) cs
->count
);
3628 fprintf (dump_file
, " setting count of the original node to "
3629 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) orig_node
->count
);
3630 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3631 fprintf (dump_file
, " edge to %s is left with "
3632 HOST_WIDE_INT_PRINT_DEC
"\n",
3633 cs
->callee
->name (), (HOST_WIDE_INT
) cs
->count
);
3636 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
3637 their profile information to reflect this. */
3640 update_profiling_info (struct cgraph_node
*orig_node
,
3641 struct cgraph_node
*new_node
)
3643 struct cgraph_edge
*cs
;
3644 struct caller_statistics stats
;
3645 gcov_type new_sum
, orig_sum
;
3646 gcov_type remainder
, orig_node_count
= orig_node
->count
;
3648 if (orig_node_count
== 0)
3651 init_caller_stats (&stats
);
3652 orig_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
3654 orig_sum
= stats
.count_sum
;
3655 init_caller_stats (&stats
);
3656 new_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
3658 new_sum
= stats
.count_sum
;
3660 if (orig_node_count
< orig_sum
+ new_sum
)
3663 fprintf (dump_file
, " Problem: node %s/%i has too low count "
3664 HOST_WIDE_INT_PRINT_DEC
" while the sum of incoming "
3665 "counts is " HOST_WIDE_INT_PRINT_DEC
"\n",
3666 orig_node
->name (), orig_node
->order
,
3667 (HOST_WIDE_INT
) orig_node_count
,
3668 (HOST_WIDE_INT
) (orig_sum
+ new_sum
));
3670 orig_node_count
= (orig_sum
+ new_sum
) * 12 / 10;
3672 fprintf (dump_file
, " proceeding by pretending it was "
3673 HOST_WIDE_INT_PRINT_DEC
"\n",
3674 (HOST_WIDE_INT
) orig_node_count
);
3677 new_node
->count
= new_sum
;
3678 remainder
= orig_node_count
- new_sum
;
3679 orig_node
->count
= remainder
;
3681 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3683 cs
->count
= apply_probability (cs
->count
,
3684 GCOV_COMPUTE_SCALE (new_sum
,
3689 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3690 cs
->count
= apply_probability (cs
->count
,
3691 GCOV_COMPUTE_SCALE (remainder
,
3695 dump_profile_updates (orig_node
, new_node
);
3698 /* Update the respective profile of specialized NEW_NODE and the original
3699 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
3700 have been redirected to the specialized version. */
3703 update_specialized_profile (struct cgraph_node
*new_node
,
3704 struct cgraph_node
*orig_node
,
3705 gcov_type redirected_sum
)
3707 struct cgraph_edge
*cs
;
3708 gcov_type new_node_count
, orig_node_count
= orig_node
->count
;
3711 fprintf (dump_file
, " the sum of counts of redirected edges is "
3712 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) redirected_sum
);
3713 if (orig_node_count
== 0)
3716 gcc_assert (orig_node_count
>= redirected_sum
);
3718 new_node_count
= new_node
->count
;
3719 new_node
->count
+= redirected_sum
;
3720 orig_node
->count
-= redirected_sum
;
3722 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3724 cs
->count
+= apply_probability (cs
->count
,
3725 GCOV_COMPUTE_SCALE (redirected_sum
,
3730 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3732 gcov_type dec
= apply_probability (cs
->count
,
3733 GCOV_COMPUTE_SCALE (redirected_sum
,
3735 if (dec
< cs
->count
)
3742 dump_profile_updates (orig_node
, new_node
);
3745 /* Create a specialized version of NODE with known constants in KNOWN_CSTS,
3746 known contexts in KNOWN_CONTEXTS and known aggregate values in AGGVALS and
3747 redirect all edges in CALLERS to it. */
3749 static struct cgraph_node
*
3750 create_specialized_node (struct cgraph_node
*node
,
3751 vec
<tree
> known_csts
,
3752 vec
<ipa_polymorphic_call_context
> known_contexts
,
3753 struct ipa_agg_replacement_value
*aggvals
,
3754 vec
<cgraph_edge
*> callers
)
3756 struct ipa_node_params
*new_info
, *info
= IPA_NODE_REF (node
);
3757 vec
<ipa_replace_map
*, va_gc
> *replace_trees
= NULL
;
3758 struct ipa_agg_replacement_value
*av
;
3759 struct cgraph_node
*new_node
;
3760 int i
, count
= ipa_get_param_count (info
);
3761 bitmap args_to_skip
;
3763 gcc_assert (!info
->ipcp_orig_node
);
3765 if (node
->local
.can_change_signature
)
3767 args_to_skip
= BITMAP_GGC_ALLOC ();
3768 for (i
= 0; i
< count
; i
++)
3770 tree t
= known_csts
[i
];
3772 if (t
|| !ipa_is_param_used (info
, i
))
3773 bitmap_set_bit (args_to_skip
, i
);
3778 args_to_skip
= NULL
;
3779 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3780 fprintf (dump_file
, " cannot change function signature\n");
3783 for (i
= 0; i
< count
; i
++)
3785 tree t
= known_csts
[i
];
3788 struct ipa_replace_map
*replace_map
;
3790 gcc_checking_assert (TREE_CODE (t
) != TREE_BINFO
);
3791 replace_map
= get_replacement_map (info
, t
, i
);
3793 vec_safe_push (replace_trees
, replace_map
);
3797 new_node
= node
->create_virtual_clone (callers
, replace_trees
,
3798 args_to_skip
, "constprop");
3799 ipa_set_node_agg_value_chain (new_node
, aggvals
);
3800 for (av
= aggvals
; av
; av
= av
->next
)
3801 new_node
->maybe_create_reference (av
->value
, NULL
);
3803 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3805 fprintf (dump_file
, " the new node is %s/%i.\n",
3806 new_node
->name (), new_node
->order
);
3807 if (known_contexts
.exists ())
3809 for (i
= 0; i
< count
; i
++)
3810 if (!known_contexts
[i
].useless_p ())
3812 fprintf (dump_file
, " known ctx %i is ", i
);
3813 known_contexts
[i
].dump (dump_file
);
3817 ipa_dump_agg_replacement_values (dump_file
, aggvals
);
3819 ipa_check_create_node_params ();
3820 update_profiling_info (node
, new_node
);
3821 new_info
= IPA_NODE_REF (new_node
);
3822 new_info
->ipcp_orig_node
= node
;
3823 new_info
->known_csts
= known_csts
;
3824 new_info
->known_contexts
= known_contexts
;
3826 ipcp_discover_new_direct_edges (new_node
, known_csts
, known_contexts
, aggvals
);
3832 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
3833 KNOWN_CSTS with constants that are also known for all of the CALLERS. */
3836 find_more_scalar_values_for_callers_subset (struct cgraph_node
*node
,
3837 vec
<tree
> known_csts
,
3838 vec
<cgraph_edge
*> callers
)
3840 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3841 int i
, count
= ipa_get_param_count (info
);
3843 for (i
= 0; i
< count
; i
++)
3845 struct cgraph_edge
*cs
;
3846 tree newval
= NULL_TREE
;
3850 if (ipa_get_scalar_lat (info
, i
)->bottom
|| known_csts
[i
])
3853 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3855 struct ipa_jump_func
*jump_func
;
3858 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
))
3860 && call_passes_through_thunk_p (cs
))
3861 || (!cs
->callee
->instrumentation_clone
3862 && cs
->callee
->function_symbol ()->instrumentation_clone
))
3867 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
3868 t
= ipa_value_from_jfunc (IPA_NODE_REF (cs
->caller
), jump_func
);
3871 && !values_equal_for_ipcp_p (t
, newval
))
3872 || (!first
&& !newval
))
3884 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3886 fprintf (dump_file
, " adding an extra known scalar value ");
3887 print_ipcp_constant_value (dump_file
, newval
);
3888 fprintf (dump_file
, " for ");
3889 ipa_dump_param (dump_file
, info
, i
);
3890 fprintf (dump_file
, "\n");
3893 known_csts
[i
] = newval
;
3898 /* Given a NODE and a subset of its CALLERS, try to populate plank slots in
3899 KNOWN_CONTEXTS with polymorphic contexts that are also known for all of the
3903 find_more_contexts_for_caller_subset (cgraph_node
*node
,
3904 vec
<ipa_polymorphic_call_context
>
3906 vec
<cgraph_edge
*> callers
)
3908 ipa_node_params
*info
= IPA_NODE_REF (node
);
3909 int i
, count
= ipa_get_param_count (info
);
3911 for (i
= 0; i
< count
; i
++)
3915 if (ipa_get_poly_ctx_lat (info
, i
)->bottom
3916 || (known_contexts
->exists ()
3917 && !(*known_contexts
)[i
].useless_p ()))
3920 ipa_polymorphic_call_context newval
;
3924 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3926 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
)))
3928 ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
),
3930 ipa_polymorphic_call_context ctx
;
3931 ctx
= ipa_context_from_jfunc (IPA_NODE_REF (cs
->caller
), cs
, i
,
3939 newval
.meet_with (ctx
);
3940 if (newval
.useless_p ())
3944 if (!newval
.useless_p ())
3946 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3948 fprintf (dump_file
, " adding an extra known polymorphic "
3950 print_ipcp_constant_value (dump_file
, newval
);
3951 fprintf (dump_file
, " for ");
3952 ipa_dump_param (dump_file
, info
, i
);
3953 fprintf (dump_file
, "\n");
3956 if (!known_contexts
->exists ())
3957 known_contexts
->safe_grow_cleared (ipa_get_param_count (info
));
3958 (*known_contexts
)[i
] = newval
;
3964 /* Go through PLATS and create a vector of values consisting of values and
3965 offsets (minus OFFSET) of lattices that contain only a single value. */
3967 static vec
<ipa_agg_jf_item
>
3968 copy_plats_to_inter (struct ipcp_param_lattices
*plats
, HOST_WIDE_INT offset
)
3970 vec
<ipa_agg_jf_item
> res
= vNULL
;
3972 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
3975 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3976 if (aglat
->is_single_const ())
3978 struct ipa_agg_jf_item ti
;
3979 ti
.offset
= aglat
->offset
- offset
;
3980 ti
.value
= aglat
->values
->value
;
3986 /* Intersect all values in INTER with single value lattices in PLATS (while
3987 subtracting OFFSET). */
3990 intersect_with_plats (struct ipcp_param_lattices
*plats
,
3991 vec
<ipa_agg_jf_item
> *inter
,
3992 HOST_WIDE_INT offset
)
3994 struct ipcp_agg_lattice
*aglat
;
3995 struct ipa_agg_jf_item
*item
;
3998 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
4004 aglat
= plats
->aggs
;
4005 FOR_EACH_VEC_ELT (*inter
, k
, item
)
4012 if (aglat
->offset
- offset
> item
->offset
)
4014 if (aglat
->offset
- offset
== item
->offset
)
4016 gcc_checking_assert (item
->value
);
4017 if (values_equal_for_ipcp_p (item
->value
, aglat
->values
->value
))
4021 aglat
= aglat
->next
;
4024 item
->value
= NULL_TREE
;
4028 /* Copy aggregate replacement values of NODE (which is an IPA-CP clone) to the
4029 vector result while subtracting OFFSET from the individual value offsets. */
4031 static vec
<ipa_agg_jf_item
>
4032 agg_replacements_to_vector (struct cgraph_node
*node
, int index
,
4033 HOST_WIDE_INT offset
)
4035 struct ipa_agg_replacement_value
*av
;
4036 vec
<ipa_agg_jf_item
> res
= vNULL
;
4038 for (av
= ipa_get_agg_replacements_for_node (node
); av
; av
= av
->next
)
4039 if (av
->index
== index
4040 && (av
->offset
- offset
) >= 0)
4042 struct ipa_agg_jf_item item
;
4043 gcc_checking_assert (av
->value
);
4044 item
.offset
= av
->offset
- offset
;
4045 item
.value
= av
->value
;
4046 res
.safe_push (item
);
4052 /* Intersect all values in INTER with those that we have already scheduled to
4053 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
4054 (while subtracting OFFSET). */
4057 intersect_with_agg_replacements (struct cgraph_node
*node
, int index
,
4058 vec
<ipa_agg_jf_item
> *inter
,
4059 HOST_WIDE_INT offset
)
4061 struct ipa_agg_replacement_value
*srcvals
;
4062 struct ipa_agg_jf_item
*item
;
4065 srcvals
= ipa_get_agg_replacements_for_node (node
);
4072 FOR_EACH_VEC_ELT (*inter
, i
, item
)
4074 struct ipa_agg_replacement_value
*av
;
4078 for (av
= srcvals
; av
; av
= av
->next
)
4080 gcc_checking_assert (av
->value
);
4081 if (av
->index
== index
4082 && av
->offset
- offset
== item
->offset
)
4084 if (values_equal_for_ipcp_p (item
->value
, av
->value
))
4090 item
->value
= NULL_TREE
;
4094 /* Intersect values in INTER with aggregate values that come along edge CS to
4095 parameter number INDEX and return it. If INTER does not actually exist yet,
4096 copy all incoming values to it. If we determine we ended up with no values
4097 whatsoever, return a released vector. */
4099 static vec
<ipa_agg_jf_item
>
4100 intersect_aggregates_with_edge (struct cgraph_edge
*cs
, int index
,
4101 vec
<ipa_agg_jf_item
> inter
)
4103 struct ipa_jump_func
*jfunc
;
4104 jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), index
);
4105 if (jfunc
->type
== IPA_JF_PASS_THROUGH
4106 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
4108 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4109 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
4111 if (caller_info
->ipcp_orig_node
)
4113 struct cgraph_node
*orig_node
= caller_info
->ipcp_orig_node
;
4114 struct ipcp_param_lattices
*orig_plats
;
4115 orig_plats
= ipa_get_parm_lattices (IPA_NODE_REF (orig_node
),
4117 if (agg_pass_through_permissible_p (orig_plats
, jfunc
))
4119 if (!inter
.exists ())
4120 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, 0);
4122 intersect_with_agg_replacements (cs
->caller
, src_idx
,
4133 struct ipcp_param_lattices
*src_plats
;
4134 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
4135 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
4137 /* Currently we do not produce clobber aggregate jump
4138 functions, adjust when we do. */
4139 gcc_checking_assert (!jfunc
->agg
.items
);
4140 if (!inter
.exists ())
4141 inter
= copy_plats_to_inter (src_plats
, 0);
4143 intersect_with_plats (src_plats
, &inter
, 0);
4152 else if (jfunc
->type
== IPA_JF_ANCESTOR
4153 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
4155 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4156 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
4157 struct ipcp_param_lattices
*src_plats
;
4158 HOST_WIDE_INT delta
= ipa_get_jf_ancestor_offset (jfunc
);
4160 if (caller_info
->ipcp_orig_node
)
4162 if (!inter
.exists ())
4163 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, delta
);
4165 intersect_with_agg_replacements (cs
->caller
, src_idx
, &inter
,
4170 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);;
4171 /* Currently we do not produce clobber aggregate jump
4172 functions, adjust when we do. */
4173 gcc_checking_assert (!src_plats
->aggs
|| !jfunc
->agg
.items
);
4174 if (!inter
.exists ())
4175 inter
= copy_plats_to_inter (src_plats
, delta
);
4177 intersect_with_plats (src_plats
, &inter
, delta
);
4180 else if (jfunc
->agg
.items
)
4182 struct ipa_agg_jf_item
*item
;
4185 if (!inter
.exists ())
4186 for (unsigned i
= 0; i
< jfunc
->agg
.items
->length (); i
++)
4187 inter
.safe_push ((*jfunc
->agg
.items
)[i
]);
4189 FOR_EACH_VEC_ELT (inter
, k
, item
)
4192 bool found
= false;;
4197 while ((unsigned) l
< jfunc
->agg
.items
->length ())
4199 struct ipa_agg_jf_item
*ti
;
4200 ti
= &(*jfunc
->agg
.items
)[l
];
4201 if (ti
->offset
> item
->offset
)
4203 if (ti
->offset
== item
->offset
)
4205 gcc_checking_assert (ti
->value
);
4206 if (values_equal_for_ipcp_p (item
->value
,
4220 return vec
<ipa_agg_jf_item
>();
4225 /* Look at edges in CALLERS and collect all known aggregate values that arrive
4226 from all of them. */
4228 static struct ipa_agg_replacement_value
*
4229 find_aggregate_values_for_callers_subset (struct cgraph_node
*node
,
4230 vec
<cgraph_edge
*> callers
)
4232 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
4233 struct ipa_agg_replacement_value
*res
;
4234 struct ipa_agg_replacement_value
**tail
= &res
;
4235 struct cgraph_edge
*cs
;
4236 int i
, j
, count
= ipa_get_param_count (dest_info
);
4238 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4240 int c
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
4245 for (i
= 0; i
< count
; i
++)
4247 struct cgraph_edge
*cs
;
4248 vec
<ipa_agg_jf_item
> inter
= vNULL
;
4249 struct ipa_agg_jf_item
*item
;
4250 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (dest_info
, i
);
4253 /* Among other things, the following check should deal with all by_ref
4255 if (plats
->aggs_bottom
)
4258 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4260 inter
= intersect_aggregates_with_edge (cs
, i
, inter
);
4262 if (!inter
.exists ())
4266 FOR_EACH_VEC_ELT (inter
, j
, item
)
4268 struct ipa_agg_replacement_value
*v
;
4273 v
= ggc_alloc
<ipa_agg_replacement_value
> ();
4275 v
->offset
= item
->offset
;
4276 v
->value
= item
->value
;
4277 v
->by_ref
= plats
->aggs_by_ref
;
4283 if (inter
.exists ())
4290 /* Turn KNOWN_AGGS into a list of aggregate replacement values. */
4292 static struct ipa_agg_replacement_value
*
4293 known_aggs_to_agg_replacement_list (vec
<ipa_agg_jump_function
> known_aggs
)
4295 struct ipa_agg_replacement_value
*res
;
4296 struct ipa_agg_replacement_value
**tail
= &res
;
4297 struct ipa_agg_jump_function
*aggjf
;
4298 struct ipa_agg_jf_item
*item
;
4301 FOR_EACH_VEC_ELT (known_aggs
, i
, aggjf
)
4302 FOR_EACH_VEC_SAFE_ELT (aggjf
->items
, j
, item
)
4304 struct ipa_agg_replacement_value
*v
;
4305 v
= ggc_alloc
<ipa_agg_replacement_value
> ();
4307 v
->offset
= item
->offset
;
4308 v
->value
= item
->value
;
4309 v
->by_ref
= aggjf
->by_ref
;
4317 /* Determine whether CS also brings all scalar values that the NODE is
4321 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge
*cs
,
4322 struct cgraph_node
*node
)
4324 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
4325 int count
= ipa_get_param_count (dest_info
);
4326 struct ipa_node_params
*caller_info
;
4327 struct ipa_edge_args
*args
;
4330 caller_info
= IPA_NODE_REF (cs
->caller
);
4331 args
= IPA_EDGE_REF (cs
);
4332 for (i
= 0; i
< count
; i
++)
4334 struct ipa_jump_func
*jump_func
;
4337 val
= dest_info
->known_csts
[i
];
4341 if (i
>= ipa_get_cs_argument_count (args
))
4343 jump_func
= ipa_get_ith_jump_func (args
, i
);
4344 t
= ipa_value_from_jfunc (caller_info
, jump_func
);
4345 if (!t
|| !values_equal_for_ipcp_p (val
, t
))
4351 /* Determine whether CS also brings all aggregate values that NODE is
4354 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge
*cs
,
4355 struct cgraph_node
*node
)
4357 struct ipa_node_params
*orig_caller_info
= IPA_NODE_REF (cs
->caller
);
4358 struct ipa_node_params
*orig_node_info
;
4359 struct ipa_agg_replacement_value
*aggval
;
4362 aggval
= ipa_get_agg_replacements_for_node (node
);
4366 count
= ipa_get_param_count (IPA_NODE_REF (node
));
4367 ec
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
4369 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4370 if (aggval
->index
>= ec
)
4373 orig_node_info
= IPA_NODE_REF (IPA_NODE_REF (node
)->ipcp_orig_node
);
4374 if (orig_caller_info
->ipcp_orig_node
)
4375 orig_caller_info
= IPA_NODE_REF (orig_caller_info
->ipcp_orig_node
);
4377 for (i
= 0; i
< count
; i
++)
4379 static vec
<ipa_agg_jf_item
> values
= vec
<ipa_agg_jf_item
>();
4380 struct ipcp_param_lattices
*plats
;
4381 bool interesting
= false;
4382 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4383 if (aggval
->index
== i
)
4391 plats
= ipa_get_parm_lattices (orig_node_info
, aggval
->index
);
4392 if (plats
->aggs_bottom
)
4395 values
= intersect_aggregates_with_edge (cs
, i
, values
);
4396 if (!values
.exists ())
4399 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4400 if (aggval
->index
== i
)
4402 struct ipa_agg_jf_item
*item
;
4405 FOR_EACH_VEC_ELT (values
, j
, item
)
4407 && item
->offset
== av
->offset
4408 && values_equal_for_ipcp_p (item
->value
, av
->value
))
4423 /* Given an original NODE and a VAL for which we have already created a
4424 specialized clone, look whether there are incoming edges that still lead
4425 into the old node but now also bring the requested value and also conform to
4426 all other criteria such that they can be redirected the special node.
4427 This function can therefore redirect the final edge in a SCC. */
4429 template <typename valtype
>
4431 perhaps_add_new_callers (cgraph_node
*node
, ipcp_value
<valtype
> *val
)
4433 ipcp_value_source
<valtype
> *src
;
4434 gcov_type redirected_sum
= 0;
4436 for (src
= val
->sources
; src
; src
= src
->next
)
4438 struct cgraph_edge
*cs
= src
->cs
;
4441 if (cgraph_edge_brings_value_p (cs
, src
, node
)
4442 && cgraph_edge_brings_all_scalars_for_node (cs
, val
->spec_node
)
4443 && cgraph_edge_brings_all_agg_vals_for_node (cs
, val
->spec_node
))
4446 fprintf (dump_file
, " - adding an extra caller %s/%i"
4448 xstrdup_for_dump (cs
->caller
->name ()),
4450 xstrdup_for_dump (val
->spec_node
->name ()),
4451 val
->spec_node
->order
);
4453 cs
->redirect_callee_duplicating_thunks (val
->spec_node
);
4454 val
->spec_node
->expand_all_artificial_thunks ();
4455 redirected_sum
+= cs
->count
;
4457 cs
= get_next_cgraph_edge_clone (cs
);
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 gcov_type 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/%i.\n",
4608 node
->name (), node
->order
);
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/%i.\n",
4650 node
->name (), node
->order
);
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/%i "
4705 "for all known contexts.\n", node
->name (),
4708 callers
= node
->collect_callers ();
4710 if (!known_contexts_useful_p (known_contexts
))
4712 known_contexts
.release ();
4713 known_contexts
= vNULL
;
4715 clone
= create_specialized_node (node
, known_csts
, known_contexts
,
4716 known_aggs_to_agg_replacement_list (known_aggs
),
4718 info
= IPA_NODE_REF (node
);
4719 info
->do_clone_for_all_contexts
= false;
4720 IPA_NODE_REF (clone
)->is_all_contexts_clone
= true;
4721 for (i
= 0; i
< count
; i
++)
4722 vec_free (known_aggs
[i
].items
);
4723 known_aggs
.release ();
4728 known_csts
.release ();
4729 known_contexts
.release ();
4735 /* Transitively mark all callees of NODE within the same SCC as not dead. */
4738 spread_undeadness (struct cgraph_node
*node
)
4740 struct cgraph_edge
*cs
;
4742 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
4743 if (ipa_edge_within_scc (cs
))
4745 struct cgraph_node
*callee
;
4746 struct ipa_node_params
*info
;
4748 callee
= cs
->callee
->function_symbol (NULL
);
4749 info
= IPA_NODE_REF (callee
);
4751 if (info
->node_dead
)
4753 info
->node_dead
= 0;
4754 spread_undeadness (callee
);
4759 /* Return true if NODE has a caller from outside of its SCC that is not
4760 dead. Worker callback for cgraph_for_node_and_aliases. */
4763 has_undead_caller_from_outside_scc_p (struct cgraph_node
*node
,
4764 void *data ATTRIBUTE_UNUSED
)
4766 struct cgraph_edge
*cs
;
4768 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
4769 if (cs
->caller
->thunk
.thunk_p
4770 && cs
->caller
->call_for_symbol_thunks_and_aliases
4771 (has_undead_caller_from_outside_scc_p
, NULL
, true))
4773 else if (!ipa_edge_within_scc (cs
)
4774 && !IPA_NODE_REF (cs
->caller
)->node_dead
)
4780 /* Identify nodes within the same SCC as NODE which are no longer needed
4781 because of new clones and will be removed as unreachable. */
4784 identify_dead_nodes (struct cgraph_node
*node
)
4786 struct cgraph_node
*v
;
4787 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4789 && !v
->call_for_symbol_thunks_and_aliases
4790 (has_undead_caller_from_outside_scc_p
, NULL
, true))
4791 IPA_NODE_REF (v
)->node_dead
= 1;
4793 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4794 if (!IPA_NODE_REF (v
)->node_dead
)
4795 spread_undeadness (v
);
4797 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4799 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4800 if (IPA_NODE_REF (v
)->node_dead
)
4801 fprintf (dump_file
, " Marking node as dead: %s/%i.\n",
4802 v
->name (), v
->order
);
4806 /* The decision stage. Iterate over the topological order of call graph nodes
4807 TOPO and make specialized clones if deemed beneficial. */
4810 ipcp_decision_stage (struct ipa_topo_info
*topo
)
4815 fprintf (dump_file
, "\nIPA decision stage:\n\n");
4817 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
4819 struct cgraph_node
*node
= topo
->order
[i
];
4820 bool change
= false, iterate
= true;
4824 struct cgraph_node
*v
;
4826 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4827 if (v
->has_gimple_body_p ()
4828 && ipcp_versionable_function_p (v
))
4829 iterate
|= decide_whether_version_node (v
);
4834 identify_dead_nodes (node
);
4838 /* Look up all the bits information that we have discovered and copy it over
4839 to the transformation summary. */
4842 ipcp_store_bits_results (void)
4846 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
4848 ipa_node_params
*info
= IPA_NODE_REF (node
);
4849 bool dumped_sth
= false;
4850 bool found_useful_result
= false;
4852 if (!opt_for_fn (node
->decl
, flag_ipa_bit_cp
))
4855 fprintf (dump_file
, "Not considering %s for ipa bitwise propagation "
4856 "; -fipa-bit-cp: disabled.\n",
4861 if (info
->ipcp_orig_node
)
4862 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
4864 unsigned count
= ipa_get_param_count (info
);
4865 for (unsigned i
= 0; i
< count
; i
++)
4867 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4868 if (plats
->bits_lattice
.constant_p ())
4870 found_useful_result
= true;
4875 if (!found_useful_result
)
4878 ipcp_grow_transformations_if_necessary ();
4879 ipcp_transformation_summary
*ts
= ipcp_get_transformation_summary (node
);
4880 vec_safe_reserve_exact (ts
->bits
, count
);
4882 for (unsigned i
= 0; i
< count
; i
++)
4884 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4887 if (plats
->bits_lattice
.constant_p ())
4889 = ipa_get_ipa_bits_for_value (plats
->bits_lattice
.get_value (),
4890 plats
->bits_lattice
.get_mask ());
4894 ts
->bits
->quick_push (jfbits
);
4895 if (!dump_file
|| !jfbits
)
4899 fprintf (dump_file
, "Propagated bits info for function %s/%i:\n",
4900 node
->name (), node
->order
);
4903 fprintf (dump_file
, " param %i: value = ", i
);
4904 print_hex (jfbits
->value
, dump_file
);
4905 fprintf (dump_file
, ", mask = ");
4906 print_hex (jfbits
->mask
, dump_file
);
4907 fprintf (dump_file
, "\n");
4912 /* Look up all VR information that we have discovered and copy it over
4913 to the transformation summary. */
4916 ipcp_store_vr_results (void)
4920 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
4922 ipa_node_params
*info
= IPA_NODE_REF (node
);
4923 bool found_useful_result
= false;
4925 if (!opt_for_fn (node
->decl
, flag_ipa_vrp
))
4928 fprintf (dump_file
, "Not considering %s for VR discovery "
4929 "and propagate; -fipa-ipa-vrp: disabled.\n",
4934 if (info
->ipcp_orig_node
)
4935 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
4937 unsigned count
= ipa_get_param_count (info
);
4938 for (unsigned i
= 0; i
< count
; i
++)
4940 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4941 if (!plats
->m_value_range
.bottom_p ()
4942 && !plats
->m_value_range
.top_p ())
4944 found_useful_result
= true;
4948 if (!found_useful_result
)
4951 ipcp_grow_transformations_if_necessary ();
4952 ipcp_transformation_summary
*ts
= ipcp_get_transformation_summary (node
);
4953 vec_safe_reserve_exact (ts
->m_vr
, count
);
4955 for (unsigned i
= 0; i
< count
; i
++)
4957 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4960 if (!plats
->m_value_range
.bottom_p ()
4961 && !plats
->m_value_range
.top_p ())
4964 vr
.type
= plats
->m_value_range
.m_vr
.type
;
4965 vr
.min
= plats
->m_value_range
.m_vr
.min
;
4966 vr
.max
= plats
->m_value_range
.m_vr
.max
;
4971 vr
.type
= VR_VARYING
;
4972 vr
.min
= vr
.max
= wi::zero (INT_TYPE_SIZE
);
4974 ts
->m_vr
->quick_push (vr
);
4979 /* The IPCP driver. */
4984 struct cgraph_2edge_hook_list
*edge_duplication_hook_holder
;
4985 struct cgraph_edge_hook_list
*edge_removal_hook_holder
;
4986 struct ipa_topo_info topo
;
4988 ipa_check_create_node_params ();
4989 ipa_check_create_edge_args ();
4990 grow_edge_clone_vectors ();
4991 edge_duplication_hook_holder
4992 = symtab
->add_edge_duplication_hook (&ipcp_edge_duplication_hook
, NULL
);
4993 edge_removal_hook_holder
4994 = symtab
->add_edge_removal_hook (&ipcp_edge_removal_hook
, NULL
);
4998 fprintf (dump_file
, "\nIPA structures before propagation:\n");
4999 if (dump_flags
& TDF_DETAILS
)
5000 ipa_print_all_params (dump_file
);
5001 ipa_print_all_jump_functions (dump_file
);
5004 /* Topological sort. */
5005 build_toporder_info (&topo
);
5006 /* Do the interprocedural propagation. */
5007 ipcp_propagate_stage (&topo
);
5008 /* Decide what constant propagation and cloning should be performed. */
5009 ipcp_decision_stage (&topo
);
5010 /* Store results of bits propagation. */
5011 ipcp_store_bits_results ();
5012 /* Store results of value range propagation. */
5013 ipcp_store_vr_results ();
5015 /* Free all IPCP structures. */
5016 free_toporder_info (&topo
);
5017 next_edge_clone
.release ();
5018 prev_edge_clone
.release ();
5019 symtab
->remove_edge_removal_hook (edge_removal_hook_holder
);
5020 symtab
->remove_edge_duplication_hook (edge_duplication_hook_holder
);
5021 ipa_free_all_structures_after_ipa_cp ();
5023 fprintf (dump_file
, "\nIPA constant propagation end\n");
5027 /* Initialization and computation of IPCP data structures. This is the initial
5028 intraprocedural analysis of functions, which gathers information to be
5029 propagated later on. */
5032 ipcp_generate_summary (void)
5034 struct cgraph_node
*node
;
5037 fprintf (dump_file
, "\nIPA constant propagation start:\n");
5038 ipa_register_cgraph_hooks ();
5040 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5041 ipa_analyze_node (node
);
5044 /* Write ipcp summary for nodes in SET. */
5047 ipcp_write_summary (void)
5049 ipa_prop_write_jump_functions ();
5052 /* Read ipcp summary. */
5055 ipcp_read_summary (void)
5057 ipa_prop_read_jump_functions ();
5062 const pass_data pass_data_ipa_cp
=
5064 IPA_PASS
, /* type */
5066 OPTGROUP_NONE
, /* optinfo_flags */
5067 TV_IPA_CONSTANT_PROP
, /* tv_id */
5068 0, /* properties_required */
5069 0, /* properties_provided */
5070 0, /* properties_destroyed */
5071 0, /* todo_flags_start */
5072 ( TODO_dump_symtab
| TODO_remove_functions
), /* todo_flags_finish */
5075 class pass_ipa_cp
: public ipa_opt_pass_d
5078 pass_ipa_cp (gcc::context
*ctxt
)
5079 : ipa_opt_pass_d (pass_data_ipa_cp
, ctxt
,
5080 ipcp_generate_summary
, /* generate_summary */
5081 ipcp_write_summary
, /* write_summary */
5082 ipcp_read_summary
, /* read_summary */
5083 ipcp_write_transformation_summaries
, /*
5084 write_optimization_summary */
5085 ipcp_read_transformation_summaries
, /*
5086 read_optimization_summary */
5087 NULL
, /* stmt_fixup */
5088 0, /* function_transform_todo_flags_start */
5089 ipcp_transform_function
, /* function_transform */
5090 NULL
) /* variable_transform */
5093 /* opt_pass methods: */
5094 virtual bool gate (function
*)
5096 /* FIXME: We should remove the optimize check after we ensure we never run
5097 IPA passes when not optimizing. */
5098 return (flag_ipa_cp
&& optimize
) || in_lto_p
;
5101 virtual unsigned int execute (function
*) { return ipcp_driver (); }
5103 }; // class pass_ipa_cp
5108 make_pass_ipa_cp (gcc::context
*ctxt
)
5110 return new pass_ipa_cp (ctxt
);
5113 /* Reset all state within ipa-cp.c so that we can rerun the compiler
5114 within the same process. For use by toplev::finalize. */
5117 ipa_cp_c_finalize (void)