1 /* Interprocedural constant propagation
2 Copyright (C) 2005-2017 Free Software Foundation, Inc.
4 Contributed by Razya Ladelsky <RAZYA@il.ibm.com> and Martin Jambor
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
23 /* Interprocedural constant propagation (IPA-CP).
25 The goal of this transformation is to
27 1) discover functions which are always invoked with some arguments with the
28 same known constant values and modify the functions so that the
29 subsequent optimizations can take advantage of the knowledge, and
31 2) partial specialization - create specialized versions of functions
32 transformed in this way if some parameters are known constants only in
33 certain contexts but the estimated tradeoff between speedup and cost size
36 The algorithm also propagates types and attempts to perform type based
37 devirtualization. Types are propagated much like constants.
39 The algorithm basically consists of three stages. In the first, functions
40 are analyzed one at a time and jump functions are constructed for all known
41 call-sites. In the second phase, the pass propagates information from the
42 jump functions across the call to reveal what values are available at what
43 call sites, performs estimations of effects of known values on functions and
44 their callees, and finally decides what specialized extra versions should be
45 created. In the third, the special versions materialize and appropriate
48 The algorithm used is to a certain extent based on "Interprocedural Constant
49 Propagation", by David Callahan, Keith D Cooper, Ken Kennedy, Linda Torczon,
50 Comp86, pg 152-161 and "A Methodology for Procedure Cloning" by Keith D
51 Cooper, Mary W. Hall, and Ken Kennedy.
54 First stage - intraprocedural analysis
55 =======================================
57 This phase computes jump_function and modification flags.
59 A jump function for a call-site represents the values passed as an actual
60 arguments of a given call-site. In principle, there are three types of
63 Pass through - the caller's formal parameter is passed as an actual
64 argument, plus an operation on it can be performed.
65 Constant - a constant is passed as an actual argument.
66 Unknown - neither of the above.
68 All jump function types are described in detail in ipa-prop.h, together with
69 the data structures that represent them and methods of accessing them.
71 ipcp_generate_summary() is the main function of the first stage.
73 Second stage - interprocedural analysis
74 ========================================
76 This stage is itself divided into two phases. In the first, we propagate
77 known values over the call graph, in the second, we make cloning decisions.
78 It uses a different algorithm than the original Callahan's paper.
80 First, we traverse the functions topologically from callers to callees and,
81 for each strongly connected component (SCC), we propagate constants
82 according to previously computed jump functions. We also record what known
83 values depend on other known values and estimate local effects. Finally, we
84 propagate cumulative information about these effects from dependent values
85 to those on which they depend.
87 Second, we again traverse the call graph in the same topological order and
88 make clones for functions which we know are called with the same values in
89 all contexts and decide about extra specialized clones of functions just for
90 some contexts - these decisions are based on both local estimates and
91 cumulative estimates propagated from callees.
93 ipcp_propagate_stage() and ipcp_decision_stage() together constitute the
96 Third phase - materialization of clones, call statement updates.
97 ============================================
99 This stage is currently performed by call graph code (mainly in cgraphunit.c
100 and tree-inline.c) according to instructions inserted to the call graph by
105 #include "coretypes.h"
108 #include "gimple-expr.h"
110 #include "alloc-pool.h"
111 #include "tree-pass.h"
113 #include "diagnostic.h"
114 #include "fold-const.h"
115 #include "gimple-fold.h"
116 #include "symbol-summary.h"
117 #include "tree-vrp.h"
118 #include "ipa-prop.h"
119 #include "tree-pretty-print.h"
120 #include "tree-inline.h"
122 #include "ipa-fnsummary.h"
123 #include "ipa-utils.h"
124 #include "tree-ssa-ccp.h"
126 template <typename valtype
> class ipcp_value
;
128 /* Describes a particular source for an IPA-CP value. */
130 template <typename valtype
>
131 class ipcp_value_source
134 /* Aggregate offset of the source, negative if the source is scalar value of
135 the argument itself. */
136 HOST_WIDE_INT offset
;
137 /* The incoming edge that brought the value. */
139 /* If the jump function that resulted into his value was a pass-through or an
140 ancestor, this is the ipcp_value of the caller from which the described
141 value has been derived. Otherwise it is NULL. */
142 ipcp_value
<valtype
> *val
;
143 /* Next pointer in a linked list of sources of a value. */
144 ipcp_value_source
*next
;
145 /* If the jump function that resulted into his value was a pass-through or an
146 ancestor, this is the index of the parameter of the caller the jump
147 function references. */
151 /* Common ancestor for all ipcp_value instantiations. */
153 class ipcp_value_base
156 /* Time benefit and size cost that specializing the function for this value
157 would bring about in this function alone. */
158 int local_time_benefit
, local_size_cost
;
159 /* Time benefit and size cost that specializing the function for this value
160 can bring about in it's callees (transitively). */
161 int prop_time_benefit
, prop_size_cost
;
164 /* Describes one particular value stored in struct ipcp_lattice. */
166 template <typename valtype
>
167 class ipcp_value
: public ipcp_value_base
170 /* The actual value for the given parameter. */
172 /* The list of sources from which this value originates. */
173 ipcp_value_source
<valtype
> *sources
;
174 /* Next pointers in a linked list of all values in a lattice. */
176 /* Next pointers in a linked list of values in a strongly connected component
178 ipcp_value
*scc_next
;
179 /* Next pointers in a linked list of SCCs of values sorted topologically
180 according their sources. */
181 ipcp_value
*topo_next
;
182 /* A specialized node created for this value, NULL if none has been (so far)
184 cgraph_node
*spec_node
;
185 /* Depth first search number and low link for topological sorting of
188 /* True if this valye is currently on the topo-sort stack. */
191 void add_source (cgraph_edge
*cs
, ipcp_value
*src_val
, int src_idx
,
192 HOST_WIDE_INT offset
);
195 /* Lattice describing potential values of a formal parameter of a function, or
196 a part of an aggregate. TOP is represented by a lattice with zero values
197 and with contains_variable and bottom flags cleared. BOTTOM is represented
198 by a lattice with the bottom flag set. In that case, values and
199 contains_variable flag should be disregarded. */
201 template <typename valtype
>
205 /* The list of known values and types in this lattice. Note that values are
206 not deallocated if a lattice is set to bottom because there may be value
207 sources referencing them. */
208 ipcp_value
<valtype
> *values
;
209 /* Number of known values and types in this lattice. */
211 /* The lattice contains a variable component (in addition to values). */
212 bool contains_variable
;
213 /* The value of the lattice is bottom (i.e. variable and unusable for any
217 inline bool is_single_const ();
218 inline bool set_to_bottom ();
219 inline bool set_contains_variable ();
220 bool add_value (valtype newval
, cgraph_edge
*cs
,
221 ipcp_value
<valtype
> *src_val
= NULL
,
222 int src_idx
= 0, HOST_WIDE_INT offset
= -1);
223 void print (FILE * f
, bool dump_sources
, bool dump_benefits
);
226 /* Lattice of tree values with an offset to describe a part of an
229 class ipcp_agg_lattice
: public ipcp_lattice
<tree
>
232 /* Offset that is being described by this lattice. */
233 HOST_WIDE_INT offset
;
234 /* Size so that we don't have to re-compute it every time we traverse the
235 list. Must correspond to TYPE_SIZE of all lat values. */
237 /* Next element of the linked list. */
238 struct ipcp_agg_lattice
*next
;
241 /* Lattice of known bits, only capable of holding one value.
242 Bitwise constant propagation propagates which bits of a
258 In the above case, the param 'x' will always have all
259 the bits (except the bits in lsb) set to 0.
260 Hence the mask of 'x' would be 0xff. The mask
261 reflects that the bits in lsb are unknown.
262 The actual propagated value is given by m_value & ~m_mask. */
264 class ipcp_bits_lattice
267 bool bottom_p () { return m_lattice_val
== IPA_BITS_VARYING
; }
268 bool top_p () { return m_lattice_val
== IPA_BITS_UNDEFINED
; }
269 bool constant_p () { return m_lattice_val
== IPA_BITS_CONSTANT
; }
270 bool set_to_bottom ();
271 bool set_to_constant (widest_int
, widest_int
);
273 widest_int
get_value () { return m_value
; }
274 widest_int
get_mask () { return m_mask
; }
276 bool meet_with (ipcp_bits_lattice
& other
, unsigned, signop
,
277 enum tree_code
, tree
);
279 bool meet_with (widest_int
, widest_int
, unsigned);
284 enum { IPA_BITS_UNDEFINED
, IPA_BITS_CONSTANT
, IPA_BITS_VARYING
} m_lattice_val
;
286 /* Similar to ccp_lattice_t, mask represents which bits of value are constant.
287 If a bit in mask is set to 0, then the corresponding bit in
288 value is known to be constant. */
289 widest_int m_value
, m_mask
;
291 bool meet_with_1 (widest_int
, widest_int
, unsigned);
292 void get_value_and_mask (tree
, widest_int
*, widest_int
*);
295 /* Lattice of value ranges. */
297 class ipcp_vr_lattice
302 inline bool bottom_p () const;
303 inline bool top_p () const;
304 inline bool set_to_bottom ();
305 bool meet_with (const value_range
*p_vr
);
306 bool meet_with (const ipcp_vr_lattice
&other
);
307 void init () { m_vr
.type
= VR_UNDEFINED
; }
308 void print (FILE * f
);
311 bool meet_with_1 (const value_range
*other_vr
);
314 /* Structure containing lattices for a parameter itself and for pieces of
315 aggregates that are passed in the parameter or by a reference in a parameter
316 plus some other useful flags. */
318 class ipcp_param_lattices
321 /* Lattice describing the value of the parameter itself. */
322 ipcp_lattice
<tree
> itself
;
323 /* Lattice describing the polymorphic contexts of a parameter. */
324 ipcp_lattice
<ipa_polymorphic_call_context
> ctxlat
;
325 /* Lattices describing aggregate parts. */
326 ipcp_agg_lattice
*aggs
;
327 /* Lattice describing known bits. */
328 ipcp_bits_lattice bits_lattice
;
329 /* Lattice describing value range. */
330 ipcp_vr_lattice m_value_range
;
331 /* Number of aggregate lattices */
333 /* True if aggregate data were passed by reference (as opposed to by
336 /* All aggregate lattices contain a variable component (in addition to
338 bool aggs_contain_variable
;
339 /* The value of all aggregate lattices is bottom (i.e. variable and unusable
340 for any propagation). */
343 /* There is a virtual call based on this parameter. */
347 /* Allocation pools for values and their sources in ipa-cp. */
349 object_allocator
<ipcp_value
<tree
> > ipcp_cst_values_pool
350 ("IPA-CP constant values");
352 object_allocator
<ipcp_value
<ipa_polymorphic_call_context
> >
353 ipcp_poly_ctx_values_pool ("IPA-CP polymorphic contexts");
355 object_allocator
<ipcp_value_source
<tree
> > ipcp_sources_pool
356 ("IPA-CP value sources");
358 object_allocator
<ipcp_agg_lattice
> ipcp_agg_lattice_pool
359 ("IPA_CP aggregate lattices");
361 /* Maximal count found in program. */
363 static 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)));
433 print_generic_expr (f
, v
);
436 /* Print V which is extracted from a value in a lattice to F. */
439 print_ipcp_constant_value (FILE * f
, ipa_polymorphic_call_context v
)
444 /* Print a lattice LAT to F. */
446 template <typename valtype
>
448 ipcp_lattice
<valtype
>::print (FILE * f
, bool dump_sources
, bool dump_benefits
)
450 ipcp_value
<valtype
> *val
;
455 fprintf (f
, "BOTTOM\n");
459 if (!values_count
&& !contains_variable
)
461 fprintf (f
, "TOP\n");
465 if (contains_variable
)
467 fprintf (f
, "VARIABLE");
473 for (val
= values
; val
; val
= val
->next
)
475 if (dump_benefits
&& prev
)
477 else if (!dump_benefits
&& prev
)
482 print_ipcp_constant_value (f
, val
->value
);
486 ipcp_value_source
<valtype
> *s
;
488 fprintf (f
, " [from:");
489 for (s
= val
->sources
; s
; s
= s
->next
)
490 fprintf (f
, " %i(%i)", s
->cs
->caller
->order
,
496 fprintf (f
, " [loc_time: %i, loc_size: %i, "
497 "prop_time: %i, prop_size: %i]\n",
498 val
->local_time_benefit
, val
->local_size_cost
,
499 val
->prop_time_benefit
, val
->prop_size_cost
);
506 ipcp_bits_lattice::print (FILE *f
)
509 fprintf (f
, " Bits unknown (TOP)\n");
510 else if (bottom_p ())
511 fprintf (f
, " Bits unusable (BOTTOM)\n");
514 fprintf (f
, " Bits: value = "); print_hex (get_value (), f
);
515 fprintf (f
, ", mask = "); print_hex (get_mask (), f
);
520 /* Print value range lattice to F. */
523 ipcp_vr_lattice::print (FILE * f
)
525 dump_value_range (f
, &m_vr
);
528 /* Print all ipcp_lattices of all functions to F. */
531 print_all_lattices (FILE * f
, bool dump_sources
, bool dump_benefits
)
533 struct cgraph_node
*node
;
536 fprintf (f
, "\nLattices:\n");
537 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
539 struct ipa_node_params
*info
;
541 info
= IPA_NODE_REF (node
);
542 fprintf (f
, " Node: %s:\n", node
->dump_name ());
543 count
= ipa_get_param_count (info
);
544 for (i
= 0; i
< count
; i
++)
546 struct ipcp_agg_lattice
*aglat
;
547 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
548 fprintf (f
, " param [%d]: ", i
);
549 plats
->itself
.print (f
, dump_sources
, dump_benefits
);
550 fprintf (f
, " ctxs: ");
551 plats
->ctxlat
.print (f
, dump_sources
, dump_benefits
);
552 plats
->bits_lattice
.print (f
);
554 plats
->m_value_range
.print (f
);
556 if (plats
->virt_call
)
557 fprintf (f
, " virt_call flag set\n");
559 if (plats
->aggs_bottom
)
561 fprintf (f
, " AGGS BOTTOM\n");
564 if (plats
->aggs_contain_variable
)
565 fprintf (f
, " AGGS VARIABLE\n");
566 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
568 fprintf (f
, " %soffset " HOST_WIDE_INT_PRINT_DEC
": ",
569 plats
->aggs_by_ref
? "ref " : "", aglat
->offset
);
570 aglat
->print (f
, dump_sources
, dump_benefits
);
576 /* Determine whether it is at all technically possible to create clones of NODE
577 and store this information in the ipa_node_params structure associated
581 determine_versionability (struct cgraph_node
*node
,
582 struct ipa_node_params
*info
)
584 const char *reason
= NULL
;
586 /* There are a number of generic reasons functions cannot be versioned. We
587 also cannot remove parameters if there are type attributes such as fnspec
589 if (node
->alias
|| node
->thunk
.thunk_p
)
590 reason
= "alias or thunk";
591 else if (!node
->local
.versionable
)
592 reason
= "not a tree_versionable_function";
593 else if (node
->get_availability () <= AVAIL_INTERPOSABLE
)
594 reason
= "insufficient body availability";
595 else if (!opt_for_fn (node
->decl
, optimize
)
596 || !opt_for_fn (node
->decl
, flag_ipa_cp
))
597 reason
= "non-optimized function";
598 else if (lookup_attribute ("omp declare simd", DECL_ATTRIBUTES (node
->decl
)))
600 /* Ideally we should clone the SIMD clones themselves and create
601 vector copies of them, so IPA-cp and SIMD clones can happily
602 coexist, but that may not be worth the effort. */
603 reason
= "function has SIMD clones";
605 else if (lookup_attribute ("target_clones", DECL_ATTRIBUTES (node
->decl
)))
607 /* Ideally we should clone the target clones themselves and create
608 copies of them, so IPA-cp and target clones can happily
609 coexist, but that may not be worth the effort. */
610 reason
= "function target_clones attribute";
612 /* Don't clone decls local to a comdat group; it breaks and for C++
613 decloned constructors, inlining is always better anyway. */
614 else if (node
->comdat_local_p ())
615 reason
= "comdat-local function";
616 else if (node
->calls_comdat_local
)
618 /* TODO: call is versionable if we make sure that all
619 callers are inside of a comdat group. */
620 reason
= "calls comdat-local function";
623 if (reason
&& dump_file
&& !node
->alias
&& !node
->thunk
.thunk_p
)
624 fprintf (dump_file
, "Function %s is not versionable, reason: %s.\n",
625 node
->dump_name (), reason
);
627 info
->versionable
= (reason
== NULL
);
630 /* Return true if it is at all technically possible to create clones of a
634 ipcp_versionable_function_p (struct cgraph_node
*node
)
636 return IPA_NODE_REF (node
)->versionable
;
639 /* Structure holding accumulated information about callers of a node. */
641 struct caller_statistics
644 int n_calls
, n_hot_calls
, freq_sum
;
647 /* Initialize fields of STAT to zeroes. */
650 init_caller_stats (struct caller_statistics
*stats
)
652 stats
->count_sum
= 0;
654 stats
->n_hot_calls
= 0;
658 /* Worker callback of cgraph_for_node_and_aliases accumulating statistics of
659 non-thunk incoming edges to NODE. */
662 gather_caller_stats (struct cgraph_node
*node
, void *data
)
664 struct caller_statistics
*stats
= (struct caller_statistics
*) data
;
665 struct cgraph_edge
*cs
;
667 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
668 if (!cs
->caller
->thunk
.thunk_p
)
670 stats
->count_sum
+= cs
->count
;
671 stats
->freq_sum
+= cs
->frequency
;
673 if (cs
->maybe_hot_p ())
674 stats
->n_hot_calls
++;
680 /* Return true if this NODE is viable candidate for cloning. */
683 ipcp_cloning_candidate_p (struct cgraph_node
*node
)
685 struct caller_statistics stats
;
687 gcc_checking_assert (node
->has_gimple_body_p ());
689 if (!opt_for_fn (node
->decl
, flag_ipa_cp_clone
))
692 fprintf (dump_file
, "Not considering %s for cloning; "
693 "-fipa-cp-clone disabled.\n",
698 if (node
->optimize_for_size_p ())
701 fprintf (dump_file
, "Not considering %s for cloning; "
702 "optimizing it for size.\n",
707 init_caller_stats (&stats
);
708 node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
, false);
710 if (ipa_fn_summaries
->get (node
)->self_size
< stats
.n_calls
)
713 fprintf (dump_file
, "Considering %s for cloning; code might shrink.\n",
718 /* When profile is available and function is hot, propagate into it even if
719 calls seems cold; constant propagation can improve function's speed
723 if (stats
.count_sum
> node
->count
* 90 / 100)
726 fprintf (dump_file
, "Considering %s for cloning; "
727 "usually called directly.\n",
732 if (!stats
.n_hot_calls
)
735 fprintf (dump_file
, "Not considering %s for cloning; no hot calls.\n",
740 fprintf (dump_file
, "Considering %s for cloning.\n",
745 template <typename valtype
>
746 class value_topo_info
749 /* Head of the linked list of topologically sorted values. */
750 ipcp_value
<valtype
> *values_topo
;
751 /* Stack for creating SCCs, represented by a linked list too. */
752 ipcp_value
<valtype
> *stack
;
753 /* Counter driving the algorithm in add_val_to_toposort. */
756 value_topo_info () : values_topo (NULL
), stack (NULL
), dfs_counter (0)
758 void add_val (ipcp_value
<valtype
> *cur_val
);
759 void propagate_effects ();
762 /* Arrays representing a topological ordering of call graph nodes and a stack
763 of nodes used during constant propagation and also data required to perform
764 topological sort of values and propagation of benefits in the determined
770 /* Array with obtained topological order of cgraph nodes. */
771 struct cgraph_node
**order
;
772 /* Stack of cgraph nodes used during propagation within SCC until all values
773 in the SCC stabilize. */
774 struct cgraph_node
**stack
;
775 int nnodes
, stack_top
;
777 value_topo_info
<tree
> constants
;
778 value_topo_info
<ipa_polymorphic_call_context
> contexts
;
780 ipa_topo_info () : order(NULL
), stack(NULL
), nnodes(0), stack_top(0),
785 /* Allocate the arrays in TOPO and topologically sort the nodes into order. */
788 build_toporder_info (struct ipa_topo_info
*topo
)
790 topo
->order
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
791 topo
->stack
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
793 gcc_checking_assert (topo
->stack_top
== 0);
794 topo
->nnodes
= ipa_reduced_postorder (topo
->order
, true, true, NULL
);
797 /* Free information about strongly connected components and the arrays in
801 free_toporder_info (struct ipa_topo_info
*topo
)
803 ipa_free_postorder_info ();
808 /* Add NODE to the stack in TOPO, unless it is already there. */
811 push_node_to_stack (struct ipa_topo_info
*topo
, struct cgraph_node
*node
)
813 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
814 if (info
->node_enqueued
)
816 info
->node_enqueued
= 1;
817 topo
->stack
[topo
->stack_top
++] = node
;
820 /* Pop a node from the stack in TOPO and return it or return NULL if the stack
823 static struct cgraph_node
*
824 pop_node_from_stack (struct ipa_topo_info
*topo
)
828 struct cgraph_node
*node
;
830 node
= topo
->stack
[topo
->stack_top
];
831 IPA_NODE_REF (node
)->node_enqueued
= 0;
838 /* Set lattice LAT to bottom and return true if it previously was not set as
841 template <typename valtype
>
843 ipcp_lattice
<valtype
>::set_to_bottom ()
850 /* Mark lattice as containing an unknown value and return true if it previously
851 was not marked as such. */
853 template <typename valtype
>
855 ipcp_lattice
<valtype
>::set_contains_variable ()
857 bool ret
= !contains_variable
;
858 contains_variable
= true;
862 /* Set all aggegate lattices in PLATS to bottom and return true if they were
863 not previously set as such. */
866 set_agg_lats_to_bottom (struct ipcp_param_lattices
*plats
)
868 bool ret
= !plats
->aggs_bottom
;
869 plats
->aggs_bottom
= true;
873 /* Mark all aggegate lattices in PLATS as containing an unknown value and
874 return true if they were not previously marked as such. */
877 set_agg_lats_contain_variable (struct ipcp_param_lattices
*plats
)
879 bool ret
= !plats
->aggs_contain_variable
;
880 plats
->aggs_contain_variable
= true;
885 ipcp_vr_lattice::meet_with (const ipcp_vr_lattice
&other
)
887 return meet_with_1 (&other
.m_vr
);
890 /* Meet the current value of the lattice with value ranfge described by VR
894 ipcp_vr_lattice::meet_with (const value_range
*p_vr
)
896 return meet_with_1 (p_vr
);
899 /* Meet the current value of the lattice with value ranfge described by
903 ipcp_vr_lattice::meet_with_1 (const value_range
*other_vr
)
905 tree min
= m_vr
.min
, max
= m_vr
.max
;
906 value_range_type type
= m_vr
.type
;
911 if (other_vr
->type
== VR_VARYING
)
912 return set_to_bottom ();
914 vrp_meet (&m_vr
, other_vr
);
915 if (type
!= m_vr
.type
923 /* Return true if value range information in the lattice is yet unknown. */
926 ipcp_vr_lattice::top_p () const
928 return m_vr
.type
== VR_UNDEFINED
;
931 /* Return true if value range information in the lattice is known to be
935 ipcp_vr_lattice::bottom_p () const
937 return m_vr
.type
== VR_VARYING
;
940 /* Set value range information in the lattice to bottom. Return true if it
941 previously was in a different state. */
944 ipcp_vr_lattice::set_to_bottom ()
946 if (m_vr
.type
== VR_VARYING
)
948 m_vr
.type
= VR_VARYING
;
952 /* Set lattice value to bottom, if it already isn't the case. */
955 ipcp_bits_lattice::set_to_bottom ()
959 m_lattice_val
= IPA_BITS_VARYING
;
965 /* Set to constant if it isn't already. Only meant to be called
966 when switching state from TOP. */
969 ipcp_bits_lattice::set_to_constant (widest_int value
, widest_int mask
)
971 gcc_assert (top_p ());
972 m_lattice_val
= IPA_BITS_CONSTANT
;
978 /* Convert operand to value, mask form. */
981 ipcp_bits_lattice::get_value_and_mask (tree operand
, widest_int
*valuep
, widest_int
*maskp
)
983 wide_int
get_nonzero_bits (const_tree
);
985 if (TREE_CODE (operand
) == INTEGER_CST
)
987 *valuep
= wi::to_widest (operand
);
997 /* Meet operation, similar to ccp_lattice_meet, we xor values
998 if this->value, value have different values at same bit positions, we want
999 to drop that bit to varying. Return true if mask is changed.
1000 This function assumes that the lattice value is in CONSTANT state */
1003 ipcp_bits_lattice::meet_with_1 (widest_int value
, widest_int mask
,
1006 gcc_assert (constant_p ());
1008 widest_int old_mask
= m_mask
;
1009 m_mask
= (m_mask
| mask
) | (m_value
^ value
);
1011 if (wi::sext (m_mask
, precision
) == -1)
1012 return set_to_bottom ();
1014 return m_mask
!= old_mask
;
1017 /* Meet the bits lattice with operand
1018 described by <value, mask, sgn, precision. */
1021 ipcp_bits_lattice::meet_with (widest_int value
, widest_int mask
,
1029 if (wi::sext (mask
, precision
) == -1)
1030 return set_to_bottom ();
1031 return set_to_constant (value
, mask
);
1034 return meet_with_1 (value
, mask
, precision
);
1037 /* Meet bits lattice with the result of bit_value_binop (other, operand)
1038 if code is binary operation or bit_value_unop (other) if code is unary op.
1039 In the case when code is nop_expr, no adjustment is required. */
1042 ipcp_bits_lattice::meet_with (ipcp_bits_lattice
& other
, unsigned precision
,
1043 signop sgn
, enum tree_code code
, tree operand
)
1045 if (other
.bottom_p ())
1046 return set_to_bottom ();
1048 if (bottom_p () || other
.top_p ())
1051 widest_int adjusted_value
, adjusted_mask
;
1053 if (TREE_CODE_CLASS (code
) == tcc_binary
)
1055 tree type
= TREE_TYPE (operand
);
1056 gcc_assert (INTEGRAL_TYPE_P (type
));
1057 widest_int o_value
, o_mask
;
1058 get_value_and_mask (operand
, &o_value
, &o_mask
);
1060 bit_value_binop (code
, sgn
, precision
, &adjusted_value
, &adjusted_mask
,
1061 sgn
, precision
, other
.get_value (), other
.get_mask (),
1062 TYPE_SIGN (type
), TYPE_PRECISION (type
), o_value
, o_mask
);
1064 if (wi::sext (adjusted_mask
, precision
) == -1)
1065 return set_to_bottom ();
1068 else if (TREE_CODE_CLASS (code
) == tcc_unary
)
1070 bit_value_unop (code
, sgn
, precision
, &adjusted_value
,
1071 &adjusted_mask
, sgn
, precision
, other
.get_value (),
1074 if (wi::sext (adjusted_mask
, precision
) == -1)
1075 return set_to_bottom ();
1079 return set_to_bottom ();
1083 if (wi::sext (adjusted_mask
, precision
) == -1)
1084 return set_to_bottom ();
1085 return set_to_constant (adjusted_value
, adjusted_mask
);
1088 return meet_with_1 (adjusted_value
, adjusted_mask
, precision
);
1091 /* Mark bot aggregate and scalar lattices as containing an unknown variable,
1092 return true is any of them has not been marked as such so far. */
1095 set_all_contains_variable (struct ipcp_param_lattices
*plats
)
1098 ret
= plats
->itself
.set_contains_variable ();
1099 ret
|= plats
->ctxlat
.set_contains_variable ();
1100 ret
|= set_agg_lats_contain_variable (plats
);
1101 ret
|= plats
->bits_lattice
.set_to_bottom ();
1102 ret
|= plats
->m_value_range
.set_to_bottom ();
1106 /* Worker of call_for_symbol_thunks_and_aliases, increment the integer DATA
1107 points to by the number of callers to NODE. */
1110 count_callers (cgraph_node
*node
, void *data
)
1112 int *caller_count
= (int *) data
;
1114 for (cgraph_edge
*cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
1115 /* Local thunks can be handled transparently, but if the thunk can not
1116 be optimized out, count it as a real use. */
1117 if (!cs
->caller
->thunk
.thunk_p
|| !cs
->caller
->local
.local
)
1122 /* Worker of call_for_symbol_thunks_and_aliases, it is supposed to be called on
1123 the one caller of some other node. Set the caller's corresponding flag. */
1126 set_single_call_flag (cgraph_node
*node
, void *)
1128 cgraph_edge
*cs
= node
->callers
;
1129 /* Local thunks can be handled transparently, skip them. */
1130 while (cs
&& cs
->caller
->thunk
.thunk_p
&& cs
->caller
->local
.local
)
1131 cs
= cs
->next_caller
;
1134 IPA_NODE_REF (cs
->caller
)->node_calling_single_call
= true;
1140 /* Initialize ipcp_lattices. */
1143 initialize_node_lattices (struct cgraph_node
*node
)
1145 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1146 struct cgraph_edge
*ie
;
1147 bool disable
= false, variable
= false;
1150 gcc_checking_assert (node
->has_gimple_body_p ());
1151 if (cgraph_local_p (node
))
1153 int caller_count
= 0;
1154 node
->call_for_symbol_thunks_and_aliases (count_callers
, &caller_count
,
1156 gcc_checking_assert (caller_count
> 0);
1157 if (caller_count
== 1)
1158 node
->call_for_symbol_thunks_and_aliases (set_single_call_flag
,
1163 /* When cloning is allowed, we can assume that externally visible
1164 functions are not called. We will compensate this by cloning
1166 if (ipcp_versionable_function_p (node
)
1167 && ipcp_cloning_candidate_p (node
))
1173 for (i
= 0; i
< ipa_get_param_count (info
); i
++)
1175 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1176 plats
->m_value_range
.init ();
1179 if (disable
|| variable
)
1181 for (i
= 0; i
< ipa_get_param_count (info
); i
++)
1183 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1186 plats
->itself
.set_to_bottom ();
1187 plats
->ctxlat
.set_to_bottom ();
1188 set_agg_lats_to_bottom (plats
);
1189 plats
->bits_lattice
.set_to_bottom ();
1190 plats
->m_value_range
.set_to_bottom ();
1193 set_all_contains_variable (plats
);
1195 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1196 && !node
->alias
&& !node
->thunk
.thunk_p
)
1197 fprintf (dump_file
, "Marking all lattices of %s as %s\n",
1198 node
->dump_name (), disable
? "BOTTOM" : "VARIABLE");
1201 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
1202 if (ie
->indirect_info
->polymorphic
1203 && ie
->indirect_info
->param_index
>= 0)
1205 gcc_checking_assert (ie
->indirect_info
->param_index
>= 0);
1206 ipa_get_parm_lattices (info
,
1207 ie
->indirect_info
->param_index
)->virt_call
= 1;
1211 /* Return the result of a (possibly arithmetic) pass through jump function
1212 JFUNC on the constant value INPUT. Return NULL_TREE if that cannot be
1213 determined or be considered an interprocedural invariant. */
1216 ipa_get_jf_pass_through_result (struct ipa_jump_func
*jfunc
, tree input
)
1220 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
1222 if (!is_gimple_ip_invariant (input
))
1225 if (TREE_CODE_CLASS (ipa_get_jf_pass_through_operation (jfunc
))
1227 res
= fold_unary (ipa_get_jf_pass_through_operation (jfunc
),
1228 TREE_TYPE (input
), input
);
1231 if (TREE_CODE_CLASS (ipa_get_jf_pass_through_operation (jfunc
))
1233 restype
= boolean_type_node
;
1235 restype
= TREE_TYPE (input
);
1236 res
= fold_binary (ipa_get_jf_pass_through_operation (jfunc
), restype
,
1237 input
, ipa_get_jf_pass_through_operand (jfunc
));
1239 if (res
&& !is_gimple_ip_invariant (res
))
1245 /* Return the result of an ancestor jump function JFUNC on the constant value
1246 INPUT. Return NULL_TREE if that cannot be determined. */
1249 ipa_get_jf_ancestor_result (struct ipa_jump_func
*jfunc
, tree input
)
1251 gcc_checking_assert (TREE_CODE (input
) != TREE_BINFO
);
1252 if (TREE_CODE (input
) == ADDR_EXPR
)
1254 tree t
= TREE_OPERAND (input
, 0);
1255 t
= build_ref_for_offset (EXPR_LOCATION (t
), t
,
1256 ipa_get_jf_ancestor_offset (jfunc
), false,
1257 ptr_type_node
, NULL
, false);
1258 return build_fold_addr_expr (t
);
1264 /* Determine whether JFUNC evaluates to a single known constant value and if
1265 so, return it. Otherwise return NULL. INFO describes the caller node or
1266 the one it is inlined to, so that pass-through jump functions can be
1270 ipa_value_from_jfunc (struct ipa_node_params
*info
, struct ipa_jump_func
*jfunc
)
1272 if (jfunc
->type
== IPA_JF_CONST
)
1273 return ipa_get_jf_constant (jfunc
);
1274 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1275 || jfunc
->type
== IPA_JF_ANCESTOR
)
1280 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1281 idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1283 idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1285 if (info
->ipcp_orig_node
)
1286 input
= info
->known_csts
[idx
];
1289 ipcp_lattice
<tree
> *lat
;
1292 || idx
>= ipa_get_param_count (info
))
1294 lat
= ipa_get_scalar_lat (info
, idx
);
1295 if (!lat
->is_single_const ())
1297 input
= lat
->values
->value
;
1303 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1304 return ipa_get_jf_pass_through_result (jfunc
, input
);
1306 return ipa_get_jf_ancestor_result (jfunc
, input
);
1312 /* Determie whether JFUNC evaluates to single known polymorphic context, given
1313 that INFO describes the caller node or the one it is inlined to, CS is the
1314 call graph edge corresponding to JFUNC and CSIDX index of the described
1317 ipa_polymorphic_call_context
1318 ipa_context_from_jfunc (ipa_node_params
*info
, cgraph_edge
*cs
, int csidx
,
1319 ipa_jump_func
*jfunc
)
1321 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
1322 ipa_polymorphic_call_context ctx
;
1323 ipa_polymorphic_call_context
*edge_ctx
1324 = cs
? ipa_get_ith_polymorhic_call_context (args
, csidx
) : NULL
;
1326 if (edge_ctx
&& !edge_ctx
->useless_p ())
1329 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1330 || jfunc
->type
== IPA_JF_ANCESTOR
)
1332 ipa_polymorphic_call_context srcctx
;
1334 bool type_preserved
= true;
1335 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1337 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1339 type_preserved
= ipa_get_jf_pass_through_type_preserved (jfunc
);
1340 srcidx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1344 type_preserved
= ipa_get_jf_ancestor_type_preserved (jfunc
);
1345 srcidx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1347 if (info
->ipcp_orig_node
)
1349 if (info
->known_contexts
.exists ())
1350 srcctx
= info
->known_contexts
[srcidx
];
1355 || srcidx
>= ipa_get_param_count (info
))
1357 ipcp_lattice
<ipa_polymorphic_call_context
> *lat
;
1358 lat
= ipa_get_poly_ctx_lat (info
, srcidx
);
1359 if (!lat
->is_single_const ())
1361 srcctx
= lat
->values
->value
;
1363 if (srcctx
.useless_p ())
1365 if (jfunc
->type
== IPA_JF_ANCESTOR
)
1366 srcctx
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
1367 if (!type_preserved
)
1368 srcctx
.possible_dynamic_type_change (cs
->in_polymorphic_cdtor
);
1369 srcctx
.combine_with (ctx
);
1376 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
1377 bottom, not containing a variable component and without any known value at
1381 ipcp_verify_propagated_values (void)
1383 struct cgraph_node
*node
;
1385 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
1387 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1388 int i
, count
= ipa_get_param_count (info
);
1390 for (i
= 0; i
< count
; i
++)
1392 ipcp_lattice
<tree
> *lat
= ipa_get_scalar_lat (info
, i
);
1395 && !lat
->contains_variable
1396 && lat
->values_count
== 0)
1400 symtab
->dump (dump_file
);
1401 fprintf (dump_file
, "\nIPA lattices after constant "
1402 "propagation, before gcc_unreachable:\n");
1403 print_all_lattices (dump_file
, true, false);
1412 /* Return true iff X and Y should be considered equal values by IPA-CP. */
1415 values_equal_for_ipcp_p (tree x
, tree y
)
1417 gcc_checking_assert (x
!= NULL_TREE
&& y
!= NULL_TREE
);
1422 if (TREE_CODE (x
) == ADDR_EXPR
1423 && TREE_CODE (y
) == ADDR_EXPR
1424 && TREE_CODE (TREE_OPERAND (x
, 0)) == CONST_DECL
1425 && TREE_CODE (TREE_OPERAND (y
, 0)) == CONST_DECL
)
1426 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x
, 0)),
1427 DECL_INITIAL (TREE_OPERAND (y
, 0)), 0);
1429 return operand_equal_p (x
, y
, 0);
1432 /* Return true iff X and Y should be considered equal contexts by IPA-CP. */
1435 values_equal_for_ipcp_p (ipa_polymorphic_call_context x
,
1436 ipa_polymorphic_call_context y
)
1438 return x
.equal_to (y
);
1442 /* Add a new value source to the value represented by THIS, marking that a
1443 value comes from edge CS and (if the underlying jump function is a
1444 pass-through or an ancestor one) from a caller value SRC_VAL of a caller
1445 parameter described by SRC_INDEX. OFFSET is negative if the source was the
1446 scalar value of the parameter itself or the offset within an aggregate. */
1448 template <typename valtype
>
1450 ipcp_value
<valtype
>::add_source (cgraph_edge
*cs
, ipcp_value
*src_val
,
1451 int src_idx
, HOST_WIDE_INT offset
)
1453 ipcp_value_source
<valtype
> *src
;
1455 src
= new (ipcp_sources_pool
.allocate ()) ipcp_value_source
<valtype
>;
1456 src
->offset
= offset
;
1459 src
->index
= src_idx
;
1461 src
->next
= sources
;
1465 /* Allocate a new ipcp_value holding a tree constant, initialize its value to
1466 SOURCE and clear all other fields. */
1468 static ipcp_value
<tree
> *
1469 allocate_and_init_ipcp_value (tree source
)
1471 ipcp_value
<tree
> *val
;
1473 val
= ipcp_cst_values_pool
.allocate ();
1474 memset (val
, 0, sizeof (*val
));
1475 val
->value
= source
;
1479 /* Allocate a new ipcp_value holding a polymorphic context, initialize its
1480 value to SOURCE and clear all other fields. */
1482 static ipcp_value
<ipa_polymorphic_call_context
> *
1483 allocate_and_init_ipcp_value (ipa_polymorphic_call_context source
)
1485 ipcp_value
<ipa_polymorphic_call_context
> *val
;
1488 val
= ipcp_poly_ctx_values_pool
.allocate ();
1489 memset (val
, 0, sizeof (*val
));
1490 val
->value
= source
;
1494 /* Try to add NEWVAL to LAT, potentially creating a new ipcp_value for it. CS,
1495 SRC_VAL SRC_INDEX and OFFSET are meant for add_source and have the same
1496 meaning. OFFSET -1 means the source is scalar and not a part of an
1499 template <typename valtype
>
1501 ipcp_lattice
<valtype
>::add_value (valtype newval
, cgraph_edge
*cs
,
1502 ipcp_value
<valtype
> *src_val
,
1503 int src_idx
, HOST_WIDE_INT offset
)
1505 ipcp_value
<valtype
> *val
;
1510 for (val
= values
; val
; val
= val
->next
)
1511 if (values_equal_for_ipcp_p (val
->value
, newval
))
1513 if (ipa_edge_within_scc (cs
))
1515 ipcp_value_source
<valtype
> *s
;
1516 for (s
= val
->sources
; s
; s
= s
->next
)
1523 val
->add_source (cs
, src_val
, src_idx
, offset
);
1527 if (values_count
== PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE
))
1529 /* We can only free sources, not the values themselves, because sources
1530 of other values in this SCC might point to them. */
1531 for (val
= values
; val
; val
= val
->next
)
1533 while (val
->sources
)
1535 ipcp_value_source
<valtype
> *src
= val
->sources
;
1536 val
->sources
= src
->next
;
1537 ipcp_sources_pool
.remove ((ipcp_value_source
<tree
>*)src
);
1542 return set_to_bottom ();
1546 val
= allocate_and_init_ipcp_value (newval
);
1547 val
->add_source (cs
, src_val
, src_idx
, offset
);
1553 /* Propagate values through a pass-through jump function JFUNC associated with
1554 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1555 is the index of the source parameter. */
1558 propagate_vals_across_pass_through (cgraph_edge
*cs
, ipa_jump_func
*jfunc
,
1559 ipcp_lattice
<tree
> *src_lat
,
1560 ipcp_lattice
<tree
> *dest_lat
, int src_idx
)
1562 ipcp_value
<tree
> *src_val
;
1565 /* Do not create new values when propagating within an SCC because if there
1566 are arithmetic functions with circular dependencies, there is infinite
1567 number of them and we would just make lattices bottom. */
1568 if ((ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1569 && ipa_edge_within_scc (cs
))
1570 ret
= dest_lat
->set_contains_variable ();
1572 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1574 tree cstval
= ipa_get_jf_pass_through_result (jfunc
, src_val
->value
);
1577 ret
|= dest_lat
->add_value (cstval
, cs
, src_val
, src_idx
);
1579 ret
|= dest_lat
->set_contains_variable ();
1585 /* Propagate values through an ancestor jump function JFUNC associated with
1586 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1587 is the index of the source parameter. */
1590 propagate_vals_across_ancestor (struct cgraph_edge
*cs
,
1591 struct ipa_jump_func
*jfunc
,
1592 ipcp_lattice
<tree
> *src_lat
,
1593 ipcp_lattice
<tree
> *dest_lat
, int src_idx
)
1595 ipcp_value
<tree
> *src_val
;
1598 if (ipa_edge_within_scc (cs
))
1599 return dest_lat
->set_contains_variable ();
1601 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1603 tree t
= ipa_get_jf_ancestor_result (jfunc
, src_val
->value
);
1606 ret
|= dest_lat
->add_value (t
, cs
, src_val
, src_idx
);
1608 ret
|= dest_lat
->set_contains_variable ();
1614 /* Propagate scalar values across jump function JFUNC that is associated with
1615 edge CS and put the values into DEST_LAT. */
1618 propagate_scalar_across_jump_function (struct cgraph_edge
*cs
,
1619 struct ipa_jump_func
*jfunc
,
1620 ipcp_lattice
<tree
> *dest_lat
)
1622 if (dest_lat
->bottom
)
1625 if (jfunc
->type
== IPA_JF_CONST
)
1627 tree val
= ipa_get_jf_constant (jfunc
);
1628 return dest_lat
->add_value (val
, cs
, NULL
, 0);
1630 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1631 || jfunc
->type
== IPA_JF_ANCESTOR
)
1633 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1634 ipcp_lattice
<tree
> *src_lat
;
1638 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1639 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1641 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1643 src_lat
= ipa_get_scalar_lat (caller_info
, src_idx
);
1644 if (src_lat
->bottom
)
1645 return dest_lat
->set_contains_variable ();
1647 /* If we would need to clone the caller and cannot, do not propagate. */
1648 if (!ipcp_versionable_function_p (cs
->caller
)
1649 && (src_lat
->contains_variable
1650 || (src_lat
->values_count
> 1)))
1651 return dest_lat
->set_contains_variable ();
1653 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1654 ret
= propagate_vals_across_pass_through (cs
, jfunc
, src_lat
,
1657 ret
= propagate_vals_across_ancestor (cs
, jfunc
, src_lat
, dest_lat
,
1660 if (src_lat
->contains_variable
)
1661 ret
|= dest_lat
->set_contains_variable ();
1666 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1667 use it for indirect inlining), we should propagate them too. */
1668 return dest_lat
->set_contains_variable ();
1671 /* Propagate scalar values across jump function JFUNC that is associated with
1672 edge CS and describes argument IDX and put the values into DEST_LAT. */
1675 propagate_context_across_jump_function (cgraph_edge
*cs
,
1676 ipa_jump_func
*jfunc
, int idx
,
1677 ipcp_lattice
<ipa_polymorphic_call_context
> *dest_lat
)
1679 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
1680 if (dest_lat
->bottom
)
1683 bool added_sth
= false;
1684 bool type_preserved
= true;
1686 ipa_polymorphic_call_context edge_ctx
, *edge_ctx_ptr
1687 = ipa_get_ith_polymorhic_call_context (args
, idx
);
1690 edge_ctx
= *edge_ctx_ptr
;
1692 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1693 || jfunc
->type
== IPA_JF_ANCESTOR
)
1695 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1697 ipcp_lattice
<ipa_polymorphic_call_context
> *src_lat
;
1699 /* TODO: Once we figure out how to propagate speculations, it will
1700 probably be a good idea to switch to speculation if type_preserved is
1701 not set instead of punting. */
1702 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1704 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1706 type_preserved
= ipa_get_jf_pass_through_type_preserved (jfunc
);
1707 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1711 type_preserved
= ipa_get_jf_ancestor_type_preserved (jfunc
);
1712 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1715 src_lat
= ipa_get_poly_ctx_lat (caller_info
, src_idx
);
1716 /* If we would need to clone the caller and cannot, do not propagate. */
1717 if (!ipcp_versionable_function_p (cs
->caller
)
1718 && (src_lat
->contains_variable
1719 || (src_lat
->values_count
> 1)))
1722 ipcp_value
<ipa_polymorphic_call_context
> *src_val
;
1723 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1725 ipa_polymorphic_call_context cur
= src_val
->value
;
1727 if (!type_preserved
)
1728 cur
.possible_dynamic_type_change (cs
->in_polymorphic_cdtor
);
1729 if (jfunc
->type
== IPA_JF_ANCESTOR
)
1730 cur
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
1731 /* TODO: In cases we know how the context is going to be used,
1732 we can improve the result by passing proper OTR_TYPE. */
1733 cur
.combine_with (edge_ctx
);
1734 if (!cur
.useless_p ())
1736 if (src_lat
->contains_variable
1737 && !edge_ctx
.equal_to (cur
))
1738 ret
|= dest_lat
->set_contains_variable ();
1739 ret
|= dest_lat
->add_value (cur
, cs
, src_val
, src_idx
);
1749 if (!edge_ctx
.useless_p ())
1750 ret
|= dest_lat
->add_value (edge_ctx
, cs
);
1752 ret
|= dest_lat
->set_contains_variable ();
1758 /* Propagate bits across jfunc that is associated with
1759 edge cs and update dest_lattice accordingly. */
1762 propagate_bits_across_jump_function (cgraph_edge
*cs
, int idx
,
1763 ipa_jump_func
*jfunc
,
1764 ipcp_bits_lattice
*dest_lattice
)
1766 if (dest_lattice
->bottom_p ())
1769 enum availability availability
;
1770 cgraph_node
*callee
= cs
->callee
->function_symbol (&availability
);
1771 struct ipa_node_params
*callee_info
= IPA_NODE_REF (callee
);
1772 tree parm_type
= ipa_get_type (callee_info
, idx
);
1774 /* For K&R C programs, ipa_get_type() could return NULL_TREE.
1775 Avoid the transform for these cases. */
1778 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1779 fprintf (dump_file
, "Setting dest_lattice to bottom, because"
1780 " param %i type is NULL for %s\n", idx
,
1781 cs
->callee
->name ());
1783 return dest_lattice
->set_to_bottom ();
1786 unsigned precision
= TYPE_PRECISION (parm_type
);
1787 signop sgn
= TYPE_SIGN (parm_type
);
1789 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1790 || jfunc
->type
== IPA_JF_ANCESTOR
)
1792 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1793 tree operand
= NULL_TREE
;
1794 enum tree_code code
;
1797 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1799 code
= ipa_get_jf_pass_through_operation (jfunc
);
1800 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1801 if (code
!= NOP_EXPR
)
1802 operand
= ipa_get_jf_pass_through_operand (jfunc
);
1806 code
= POINTER_PLUS_EXPR
;
1807 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1808 unsigned HOST_WIDE_INT offset
= ipa_get_jf_ancestor_offset (jfunc
) / BITS_PER_UNIT
;
1809 operand
= build_int_cstu (size_type_node
, offset
);
1812 struct ipcp_param_lattices
*src_lats
1813 = ipa_get_parm_lattices (caller_info
, src_idx
);
1815 /* Try to propagate bits if src_lattice is bottom, but jfunc is known.
1821 Assume lattice for x is bottom, however we can still propagate
1822 result of x & 0xff == 0xff, which gets computed during ccp1 pass
1823 and we store it in jump function during analysis stage. */
1825 if (src_lats
->bits_lattice
.bottom_p ()
1827 return dest_lattice
->meet_with (jfunc
->bits
->value
, jfunc
->bits
->mask
,
1830 return dest_lattice
->meet_with (src_lats
->bits_lattice
, precision
, sgn
,
1834 else if (jfunc
->type
== IPA_JF_ANCESTOR
)
1835 return dest_lattice
->set_to_bottom ();
1836 else if (jfunc
->bits
)
1837 return dest_lattice
->meet_with (jfunc
->bits
->value
, jfunc
->bits
->mask
,
1840 return dest_lattice
->set_to_bottom ();
1843 /* Emulate effects of unary OPERATION and/or conversion from SRC_TYPE to
1844 DST_TYPE on value range in SRC_VR and store it to DST_VR. Return true if
1845 the result is a range or an anti-range. */
1848 ipa_vr_operation_and_type_effects (value_range
*dst_vr
, value_range
*src_vr
,
1849 enum tree_code operation
,
1850 tree dst_type
, tree src_type
)
1852 memset (dst_vr
, 0, sizeof (*dst_vr
));
1853 extract_range_from_unary_expr (dst_vr
, operation
, dst_type
, src_vr
, src_type
);
1854 if (dst_vr
->type
== VR_RANGE
|| dst_vr
->type
== VR_ANTI_RANGE
)
1860 /* Propagate value range across jump function JFUNC that is associated with
1861 edge CS with param of callee of PARAM_TYPE and update DEST_PLATS
1865 propagate_vr_across_jump_function (cgraph_edge
*cs
, ipa_jump_func
*jfunc
,
1866 struct ipcp_param_lattices
*dest_plats
,
1869 ipcp_vr_lattice
*dest_lat
= &dest_plats
->m_value_range
;
1871 if (dest_lat
->bottom_p ())
1875 || (!INTEGRAL_TYPE_P (param_type
)
1876 && !POINTER_TYPE_P (param_type
)))
1877 return dest_lat
->set_to_bottom ();
1879 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1881 enum tree_code operation
= ipa_get_jf_pass_through_operation (jfunc
);
1883 if (TREE_CODE_CLASS (operation
) == tcc_unary
)
1885 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1886 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1887 tree operand_type
= ipa_get_type (caller_info
, src_idx
);
1888 struct ipcp_param_lattices
*src_lats
1889 = ipa_get_parm_lattices (caller_info
, src_idx
);
1891 if (src_lats
->m_value_range
.bottom_p ())
1892 return dest_lat
->set_to_bottom ();
1894 if (ipa_vr_operation_and_type_effects (&vr
,
1895 &src_lats
->m_value_range
.m_vr
,
1896 operation
, param_type
,
1898 return dest_lat
->meet_with (&vr
);
1901 else if (jfunc
->type
== IPA_JF_CONST
)
1903 tree val
= ipa_get_jf_constant (jfunc
);
1904 if (TREE_CODE (val
) == INTEGER_CST
)
1906 val
= fold_convert (param_type
, val
);
1907 if (TREE_OVERFLOW_P (val
))
1908 val
= drop_tree_overflow (val
);
1911 memset (&tmpvr
, 0, sizeof (tmpvr
));
1912 tmpvr
.type
= VR_RANGE
;
1915 return dest_lat
->meet_with (&tmpvr
);
1921 && ipa_vr_operation_and_type_effects (&vr
, jfunc
->m_vr
, NOP_EXPR
,
1923 TREE_TYPE (jfunc
->m_vr
->min
)))
1924 return dest_lat
->meet_with (&vr
);
1926 return dest_lat
->set_to_bottom ();
1929 /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
1930 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
1931 other cases, return false). If there are no aggregate items, set
1932 aggs_by_ref to NEW_AGGS_BY_REF. */
1935 set_check_aggs_by_ref (struct ipcp_param_lattices
*dest_plats
,
1936 bool new_aggs_by_ref
)
1938 if (dest_plats
->aggs
)
1940 if (dest_plats
->aggs_by_ref
!= new_aggs_by_ref
)
1942 set_agg_lats_to_bottom (dest_plats
);
1947 dest_plats
->aggs_by_ref
= new_aggs_by_ref
;
1951 /* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
1952 already existing lattice for the given OFFSET and SIZE, marking all skipped
1953 lattices as containing variable and checking for overlaps. If there is no
1954 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
1955 it with offset, size and contains_variable to PRE_EXISTING, and return true,
1956 unless there are too many already. If there are two many, return false. If
1957 there are overlaps turn whole DEST_PLATS to bottom and return false. If any
1958 skipped lattices were newly marked as containing variable, set *CHANGE to
1962 merge_agg_lats_step (struct ipcp_param_lattices
*dest_plats
,
1963 HOST_WIDE_INT offset
, HOST_WIDE_INT val_size
,
1964 struct ipcp_agg_lattice
***aglat
,
1965 bool pre_existing
, bool *change
)
1967 gcc_checking_assert (offset
>= 0);
1969 while (**aglat
&& (**aglat
)->offset
< offset
)
1971 if ((**aglat
)->offset
+ (**aglat
)->size
> offset
)
1973 set_agg_lats_to_bottom (dest_plats
);
1976 *change
|= (**aglat
)->set_contains_variable ();
1977 *aglat
= &(**aglat
)->next
;
1980 if (**aglat
&& (**aglat
)->offset
== offset
)
1982 if ((**aglat
)->size
!= val_size
1984 && (**aglat
)->next
->offset
< offset
+ val_size
))
1986 set_agg_lats_to_bottom (dest_plats
);
1989 gcc_checking_assert (!(**aglat
)->next
1990 || (**aglat
)->next
->offset
>= offset
+ val_size
);
1995 struct ipcp_agg_lattice
*new_al
;
1997 if (**aglat
&& (**aglat
)->offset
< offset
+ val_size
)
1999 set_agg_lats_to_bottom (dest_plats
);
2002 if (dest_plats
->aggs_count
== PARAM_VALUE (PARAM_IPA_MAX_AGG_ITEMS
))
2004 dest_plats
->aggs_count
++;
2005 new_al
= ipcp_agg_lattice_pool
.allocate ();
2006 memset (new_al
, 0, sizeof (*new_al
));
2008 new_al
->offset
= offset
;
2009 new_al
->size
= val_size
;
2010 new_al
->contains_variable
= pre_existing
;
2012 new_al
->next
= **aglat
;
2018 /* Set all AGLAT and all other aggregate lattices reachable by next pointers as
2019 containing an unknown value. */
2022 set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice
*aglat
)
2027 ret
|= aglat
->set_contains_variable ();
2028 aglat
= aglat
->next
;
2033 /* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
2034 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source
2035 parameter used for lattice value sources. Return true if DEST_PLATS changed
2039 merge_aggregate_lattices (struct cgraph_edge
*cs
,
2040 struct ipcp_param_lattices
*dest_plats
,
2041 struct ipcp_param_lattices
*src_plats
,
2042 int src_idx
, HOST_WIDE_INT offset_delta
)
2044 bool pre_existing
= dest_plats
->aggs
!= NULL
;
2045 struct ipcp_agg_lattice
**dst_aglat
;
2048 if (set_check_aggs_by_ref (dest_plats
, src_plats
->aggs_by_ref
))
2050 if (src_plats
->aggs_bottom
)
2051 return set_agg_lats_contain_variable (dest_plats
);
2052 if (src_plats
->aggs_contain_variable
)
2053 ret
|= set_agg_lats_contain_variable (dest_plats
);
2054 dst_aglat
= &dest_plats
->aggs
;
2056 for (struct ipcp_agg_lattice
*src_aglat
= src_plats
->aggs
;
2058 src_aglat
= src_aglat
->next
)
2060 HOST_WIDE_INT new_offset
= src_aglat
->offset
- offset_delta
;
2064 if (merge_agg_lats_step (dest_plats
, new_offset
, src_aglat
->size
,
2065 &dst_aglat
, pre_existing
, &ret
))
2067 struct ipcp_agg_lattice
*new_al
= *dst_aglat
;
2069 dst_aglat
= &(*dst_aglat
)->next
;
2070 if (src_aglat
->bottom
)
2072 ret
|= new_al
->set_contains_variable ();
2075 if (src_aglat
->contains_variable
)
2076 ret
|= new_al
->set_contains_variable ();
2077 for (ipcp_value
<tree
> *val
= src_aglat
->values
;
2080 ret
|= new_al
->add_value (val
->value
, cs
, val
, src_idx
,
2083 else if (dest_plats
->aggs_bottom
)
2086 ret
|= set_chain_of_aglats_contains_variable (*dst_aglat
);
2090 /* Determine whether there is anything to propagate FROM SRC_PLATS through a
2091 pass-through JFUNC and if so, whether it has conform and conforms to the
2092 rules about propagating values passed by reference. */
2095 agg_pass_through_permissible_p (struct ipcp_param_lattices
*src_plats
,
2096 struct ipa_jump_func
*jfunc
)
2098 return src_plats
->aggs
2099 && (!src_plats
->aggs_by_ref
2100 || ipa_get_jf_pass_through_agg_preserved (jfunc
));
2103 /* Propagate scalar values across jump function JFUNC that is associated with
2104 edge CS and put the values into DEST_LAT. */
2107 propagate_aggs_across_jump_function (struct cgraph_edge
*cs
,
2108 struct ipa_jump_func
*jfunc
,
2109 struct ipcp_param_lattices
*dest_plats
)
2113 if (dest_plats
->aggs_bottom
)
2116 if (jfunc
->type
== IPA_JF_PASS_THROUGH
2117 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
2119 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2120 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
2121 struct ipcp_param_lattices
*src_plats
;
2123 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2124 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
2126 /* Currently we do not produce clobber aggregate jump
2127 functions, replace with merging when we do. */
2128 gcc_assert (!jfunc
->agg
.items
);
2129 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
,
2133 ret
|= set_agg_lats_contain_variable (dest_plats
);
2135 else if (jfunc
->type
== IPA_JF_ANCESTOR
2136 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
2138 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2139 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
2140 struct ipcp_param_lattices
*src_plats
;
2142 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2143 if (src_plats
->aggs
&& src_plats
->aggs_by_ref
)
2145 /* Currently we do not produce clobber aggregate jump
2146 functions, replace with merging when we do. */
2147 gcc_assert (!jfunc
->agg
.items
);
2148 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
, src_idx
,
2149 ipa_get_jf_ancestor_offset (jfunc
));
2151 else if (!src_plats
->aggs_by_ref
)
2152 ret
|= set_agg_lats_to_bottom (dest_plats
);
2154 ret
|= set_agg_lats_contain_variable (dest_plats
);
2156 else if (jfunc
->agg
.items
)
2158 bool pre_existing
= dest_plats
->aggs
!= NULL
;
2159 struct ipcp_agg_lattice
**aglat
= &dest_plats
->aggs
;
2160 struct ipa_agg_jf_item
*item
;
2163 if (set_check_aggs_by_ref (dest_plats
, jfunc
->agg
.by_ref
))
2166 FOR_EACH_VEC_ELT (*jfunc
->agg
.items
, i
, item
)
2168 HOST_WIDE_INT val_size
;
2170 if (item
->offset
< 0)
2172 gcc_checking_assert (is_gimple_ip_invariant (item
->value
));
2173 val_size
= tree_to_uhwi (TYPE_SIZE (TREE_TYPE (item
->value
)));
2175 if (merge_agg_lats_step (dest_plats
, item
->offset
, val_size
,
2176 &aglat
, pre_existing
, &ret
))
2178 ret
|= (*aglat
)->add_value (item
->value
, cs
, NULL
, 0, 0);
2179 aglat
= &(*aglat
)->next
;
2181 else if (dest_plats
->aggs_bottom
)
2185 ret
|= set_chain_of_aglats_contains_variable (*aglat
);
2188 ret
|= set_agg_lats_contain_variable (dest_plats
);
2193 /* Return true if on the way cfrom CS->caller to the final (non-alias and
2194 non-thunk) destination, the call passes through a thunk. */
2197 call_passes_through_thunk_p (cgraph_edge
*cs
)
2199 cgraph_node
*alias_or_thunk
= cs
->callee
;
2200 while (alias_or_thunk
->alias
)
2201 alias_or_thunk
= alias_or_thunk
->get_alias_target ();
2202 return alias_or_thunk
->thunk
.thunk_p
;
2205 /* Propagate constants from the caller to the callee of CS. INFO describes the
2209 propagate_constants_across_call (struct cgraph_edge
*cs
)
2211 struct ipa_node_params
*callee_info
;
2212 enum availability availability
;
2213 cgraph_node
*callee
;
2214 struct ipa_edge_args
*args
;
2216 int i
, args_count
, parms_count
;
2218 callee
= cs
->callee
->function_symbol (&availability
);
2219 if (!callee
->definition
)
2221 gcc_checking_assert (callee
->has_gimple_body_p ());
2222 callee_info
= IPA_NODE_REF (callee
);
2224 args
= IPA_EDGE_REF (cs
);
2225 args_count
= ipa_get_cs_argument_count (args
);
2226 parms_count
= ipa_get_param_count (callee_info
);
2227 if (parms_count
== 0)
2230 /* No propagation through instrumentation thunks is available yet.
2231 It should be possible with proper mapping of call args and
2232 instrumented callee params in the propagation loop below. But
2233 this case mostly occurs when legacy code calls instrumented code
2234 and it is not a primary target for optimizations.
2235 We detect instrumentation thunks in aliases and thunks chain by
2236 checking instrumentation_clone flag for chain source and target.
2237 Going through instrumentation thunks we always have it changed
2238 from 0 to 1 and all other nodes do not change it. */
2239 if (!cs
->callee
->instrumentation_clone
2240 && callee
->instrumentation_clone
)
2242 for (i
= 0; i
< parms_count
; i
++)
2243 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
2248 /* If this call goes through a thunk we must not propagate to the first (0th)
2249 parameter. However, we might need to uncover a thunk from below a series
2250 of aliases first. */
2251 if (call_passes_through_thunk_p (cs
))
2253 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
2260 for (; (i
< args_count
) && (i
< parms_count
); i
++)
2262 struct ipa_jump_func
*jump_func
= ipa_get_ith_jump_func (args
, i
);
2263 struct ipcp_param_lattices
*dest_plats
;
2264 tree param_type
= ipa_get_type (callee_info
, i
);
2266 dest_plats
= ipa_get_parm_lattices (callee_info
, i
);
2267 if (availability
== AVAIL_INTERPOSABLE
)
2268 ret
|= set_all_contains_variable (dest_plats
);
2271 ret
|= propagate_scalar_across_jump_function (cs
, jump_func
,
2272 &dest_plats
->itself
);
2273 ret
|= propagate_context_across_jump_function (cs
, jump_func
, i
,
2274 &dest_plats
->ctxlat
);
2276 |= propagate_bits_across_jump_function (cs
, i
, jump_func
,
2277 &dest_plats
->bits_lattice
);
2278 ret
|= propagate_aggs_across_jump_function (cs
, jump_func
,
2280 if (opt_for_fn (callee
->decl
, flag_ipa_vrp
))
2281 ret
|= propagate_vr_across_jump_function (cs
, jump_func
,
2282 dest_plats
, param_type
);
2284 ret
|= dest_plats
->m_value_range
.set_to_bottom ();
2287 for (; i
< parms_count
; i
++)
2288 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
, i
));
2293 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
2294 KNOWN_CONTEXTS, KNOWN_AGGS or AGG_REPS return the destination. The latter
2295 three can be NULL. If AGG_REPS is not NULL, KNOWN_AGGS is ignored. */
2298 ipa_get_indirect_edge_target_1 (struct cgraph_edge
*ie
,
2299 vec
<tree
> known_csts
,
2300 vec
<ipa_polymorphic_call_context
> known_contexts
,
2301 vec
<ipa_agg_jump_function_p
> known_aggs
,
2302 struct ipa_agg_replacement_value
*agg_reps
,
2305 int param_index
= ie
->indirect_info
->param_index
;
2306 HOST_WIDE_INT anc_offset
;
2310 *speculative
= false;
2312 if (param_index
== -1
2313 || known_csts
.length () <= (unsigned int) param_index
)
2316 if (!ie
->indirect_info
->polymorphic
)
2320 if (ie
->indirect_info
->agg_contents
)
2323 if (agg_reps
&& ie
->indirect_info
->guaranteed_unmodified
)
2327 if (agg_reps
->index
== param_index
2328 && agg_reps
->offset
== ie
->indirect_info
->offset
2329 && agg_reps
->by_ref
== ie
->indirect_info
->by_ref
)
2331 t
= agg_reps
->value
;
2334 agg_reps
= agg_reps
->next
;
2339 struct ipa_agg_jump_function
*agg
;
2340 if (known_aggs
.length () > (unsigned int) param_index
)
2341 agg
= known_aggs
[param_index
];
2344 bool from_global_constant
;
2345 t
= ipa_find_agg_cst_for_param (agg
, known_csts
[param_index
],
2346 ie
->indirect_info
->offset
,
2347 ie
->indirect_info
->by_ref
,
2348 &from_global_constant
);
2350 && !from_global_constant
2351 && !ie
->indirect_info
->guaranteed_unmodified
)
2356 t
= known_csts
[param_index
];
2359 && TREE_CODE (t
) == ADDR_EXPR
2360 && TREE_CODE (TREE_OPERAND (t
, 0)) == FUNCTION_DECL
)
2361 return TREE_OPERAND (t
, 0);
2366 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize
))
2369 gcc_assert (!ie
->indirect_info
->agg_contents
);
2370 anc_offset
= ie
->indirect_info
->offset
;
2374 /* Try to work out value of virtual table pointer value in replacemnets. */
2375 if (!t
&& agg_reps
&& !ie
->indirect_info
->by_ref
)
2379 if (agg_reps
->index
== param_index
2380 && agg_reps
->offset
== ie
->indirect_info
->offset
2381 && agg_reps
->by_ref
)
2383 t
= agg_reps
->value
;
2386 agg_reps
= agg_reps
->next
;
2390 /* Try to work out value of virtual table pointer value in known
2391 aggregate values. */
2392 if (!t
&& known_aggs
.length () > (unsigned int) param_index
2393 && !ie
->indirect_info
->by_ref
)
2395 struct ipa_agg_jump_function
*agg
;
2396 agg
= known_aggs
[param_index
];
2397 t
= ipa_find_agg_cst_for_param (agg
, known_csts
[param_index
],
2398 ie
->indirect_info
->offset
, true);
2401 /* If we found the virtual table pointer, lookup the target. */
2405 unsigned HOST_WIDE_INT offset
;
2406 if (vtable_pointer_value_to_vtable (t
, &vtable
, &offset
))
2409 target
= gimple_get_virt_method_for_vtable (ie
->indirect_info
->otr_token
,
2410 vtable
, offset
, &can_refer
);
2414 || (TREE_CODE (TREE_TYPE (target
)) == FUNCTION_TYPE
2415 && DECL_FUNCTION_CODE (target
) == BUILT_IN_UNREACHABLE
)
2416 || !possible_polymorphic_call_target_p
2417 (ie
, cgraph_node::get (target
)))
2419 /* Do not speculate builtin_unreachable, it is stupid! */
2420 if (ie
->indirect_info
->vptr_changed
)
2422 target
= ipa_impossible_devirt_target (ie
, target
);
2424 *speculative
= ie
->indirect_info
->vptr_changed
;
2431 /* Do we know the constant value of pointer? */
2433 t
= known_csts
[param_index
];
2435 gcc_checking_assert (!t
|| TREE_CODE (t
) != TREE_BINFO
);
2437 ipa_polymorphic_call_context context
;
2438 if (known_contexts
.length () > (unsigned int) param_index
)
2440 context
= known_contexts
[param_index
];
2441 context
.offset_by (anc_offset
);
2442 if (ie
->indirect_info
->vptr_changed
)
2443 context
.possible_dynamic_type_change (ie
->in_polymorphic_cdtor
,
2444 ie
->indirect_info
->otr_type
);
2447 ipa_polymorphic_call_context ctx2
= ipa_polymorphic_call_context
2448 (t
, ie
->indirect_info
->otr_type
, anc_offset
);
2449 if (!ctx2
.useless_p ())
2450 context
.combine_with (ctx2
, ie
->indirect_info
->otr_type
);
2455 context
= ipa_polymorphic_call_context (t
, ie
->indirect_info
->otr_type
,
2457 if (ie
->indirect_info
->vptr_changed
)
2458 context
.possible_dynamic_type_change (ie
->in_polymorphic_cdtor
,
2459 ie
->indirect_info
->otr_type
);
2464 vec
<cgraph_node
*>targets
;
2467 targets
= possible_polymorphic_call_targets
2468 (ie
->indirect_info
->otr_type
,
2469 ie
->indirect_info
->otr_token
,
2471 if (!final
|| targets
.length () > 1)
2473 struct cgraph_node
*node
;
2476 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize_speculatively
)
2477 || ie
->speculative
|| !ie
->maybe_hot_p ())
2479 node
= try_speculative_devirtualization (ie
->indirect_info
->otr_type
,
2480 ie
->indirect_info
->otr_token
,
2484 *speculative
= true;
2485 target
= node
->decl
;
2492 *speculative
= false;
2493 if (targets
.length () == 1)
2494 target
= targets
[0]->decl
;
2496 target
= ipa_impossible_devirt_target (ie
, NULL_TREE
);
2499 if (target
&& !possible_polymorphic_call_target_p (ie
,
2500 cgraph_node::get (target
)))
2504 target
= ipa_impossible_devirt_target (ie
, target
);
2511 /* If an indirect edge IE can be turned into a direct one based on KNOWN_CSTS,
2512 KNOWN_CONTEXTS (which can be vNULL) or KNOWN_AGGS (which also can be vNULL)
2513 return the destination. */
2516 ipa_get_indirect_edge_target (struct cgraph_edge
*ie
,
2517 vec
<tree
> known_csts
,
2518 vec
<ipa_polymorphic_call_context
> known_contexts
,
2519 vec
<ipa_agg_jump_function_p
> known_aggs
,
2522 return ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
2523 known_aggs
, NULL
, speculative
);
2526 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
2527 and KNOWN_CONTEXTS. */
2530 devirtualization_time_bonus (struct cgraph_node
*node
,
2531 vec
<tree
> known_csts
,
2532 vec
<ipa_polymorphic_call_context
> known_contexts
,
2533 vec
<ipa_agg_jump_function_p
> known_aggs
)
2535 struct cgraph_edge
*ie
;
2538 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
2540 struct cgraph_node
*callee
;
2541 struct ipa_fn_summary
*isummary
;
2542 enum availability avail
;
2546 target
= ipa_get_indirect_edge_target (ie
, known_csts
, known_contexts
,
2547 known_aggs
, &speculative
);
2551 /* Only bare minimum benefit for clearly un-inlineable targets. */
2553 callee
= cgraph_node::get (target
);
2554 if (!callee
|| !callee
->definition
)
2556 callee
= callee
->function_symbol (&avail
);
2557 if (avail
< AVAIL_AVAILABLE
)
2559 isummary
= ipa_fn_summaries
->get (callee
);
2560 if (!isummary
->inlinable
)
2563 /* FIXME: The values below need re-considering and perhaps also
2564 integrating into the cost metrics, at lest in some very basic way. */
2565 if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 4)
2566 res
+= 31 / ((int)speculative
+ 1);
2567 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 2)
2568 res
+= 15 / ((int)speculative
+ 1);
2569 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
2570 || DECL_DECLARED_INLINE_P (callee
->decl
))
2571 res
+= 7 / ((int)speculative
+ 1);
2577 /* Return time bonus incurred because of HINTS. */
2580 hint_time_bonus (ipa_hints hints
)
2583 if (hints
& (INLINE_HINT_loop_iterations
| INLINE_HINT_loop_stride
))
2584 result
+= PARAM_VALUE (PARAM_IPA_CP_LOOP_HINT_BONUS
);
2585 if (hints
& INLINE_HINT_array_index
)
2586 result
+= PARAM_VALUE (PARAM_IPA_CP_ARRAY_INDEX_HINT_BONUS
);
2590 /* If there is a reason to penalize the function described by INFO in the
2591 cloning goodness evaluation, do so. */
2593 static inline int64_t
2594 incorporate_penalties (ipa_node_params
*info
, int64_t evaluation
)
2596 if (info
->node_within_scc
)
2597 evaluation
= (evaluation
2598 * (100 - PARAM_VALUE (PARAM_IPA_CP_RECURSION_PENALTY
))) / 100;
2600 if (info
->node_calling_single_call
)
2601 evaluation
= (evaluation
2602 * (100 - PARAM_VALUE (PARAM_IPA_CP_SINGLE_CALL_PENALTY
)))
2608 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
2609 and SIZE_COST and with the sum of frequencies of incoming edges to the
2610 potential new clone in FREQUENCIES. */
2613 good_cloning_opportunity_p (struct cgraph_node
*node
, int time_benefit
,
2614 int freq_sum
, gcov_type count_sum
, int size_cost
)
2616 if (time_benefit
== 0
2617 || !opt_for_fn (node
->decl
, flag_ipa_cp_clone
)
2618 || node
->optimize_for_size_p ())
2621 gcc_assert (size_cost
> 0);
2623 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2626 int factor
= (count_sum
* 1000) / max_count
;
2627 int64_t evaluation
= (((int64_t) time_benefit
* factor
)
2629 evaluation
= incorporate_penalties (info
, evaluation
);
2631 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2632 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
2633 "size: %i, count_sum: " HOST_WIDE_INT_PRINT_DEC
2634 "%s%s) -> evaluation: " "%" PRId64
2635 ", threshold: %i\n",
2636 time_benefit
, size_cost
, (HOST_WIDE_INT
) count_sum
,
2637 info
->node_within_scc
? ", scc" : "",
2638 info
->node_calling_single_call
? ", single_call" : "",
2639 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
2641 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
2645 int64_t evaluation
= (((int64_t) time_benefit
* freq_sum
)
2647 evaluation
= incorporate_penalties (info
, evaluation
);
2649 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2650 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
2651 "size: %i, freq_sum: %i%s%s) -> evaluation: "
2652 "%" PRId64
", threshold: %i\n",
2653 time_benefit
, size_cost
, freq_sum
,
2654 info
->node_within_scc
? ", scc" : "",
2655 info
->node_calling_single_call
? ", single_call" : "",
2656 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
2658 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
2662 /* Return all context independent values from aggregate lattices in PLATS in a
2663 vector. Return NULL if there are none. */
2665 static vec
<ipa_agg_jf_item
, va_gc
> *
2666 context_independent_aggregate_values (struct ipcp_param_lattices
*plats
)
2668 vec
<ipa_agg_jf_item
, va_gc
> *res
= NULL
;
2670 if (plats
->aggs_bottom
2671 || plats
->aggs_contain_variable
2672 || plats
->aggs_count
== 0)
2675 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
;
2677 aglat
= aglat
->next
)
2678 if (aglat
->is_single_const ())
2680 struct ipa_agg_jf_item item
;
2681 item
.offset
= aglat
->offset
;
2682 item
.value
= aglat
->values
->value
;
2683 vec_safe_push (res
, item
);
2688 /* Allocate KNOWN_CSTS, KNOWN_CONTEXTS and, if non-NULL, KNOWN_AGGS and
2689 populate them with values of parameters that are known independent of the
2690 context. INFO describes the function. If REMOVABLE_PARAMS_COST is
2691 non-NULL, the movement cost of all removable parameters will be stored in
2695 gather_context_independent_values (struct ipa_node_params
*info
,
2696 vec
<tree
> *known_csts
,
2697 vec
<ipa_polymorphic_call_context
>
2699 vec
<ipa_agg_jump_function
> *known_aggs
,
2700 int *removable_params_cost
)
2702 int i
, count
= ipa_get_param_count (info
);
2705 known_csts
->create (0);
2706 known_contexts
->create (0);
2707 known_csts
->safe_grow_cleared (count
);
2708 known_contexts
->safe_grow_cleared (count
);
2711 known_aggs
->create (0);
2712 known_aggs
->safe_grow_cleared (count
);
2715 if (removable_params_cost
)
2716 *removable_params_cost
= 0;
2718 for (i
= 0; i
< count
; i
++)
2720 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2721 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
2723 if (lat
->is_single_const ())
2725 ipcp_value
<tree
> *val
= lat
->values
;
2726 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
2727 (*known_csts
)[i
] = val
->value
;
2728 if (removable_params_cost
)
2729 *removable_params_cost
2730 += estimate_move_cost (TREE_TYPE (val
->value
), false);
2733 else if (removable_params_cost
2734 && !ipa_is_param_used (info
, i
))
2735 *removable_params_cost
2736 += ipa_get_param_move_cost (info
, i
);
2738 if (!ipa_is_param_used (info
, i
))
2741 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
2742 /* Do not account known context as reason for cloning. We can see
2743 if it permits devirtualization. */
2744 if (ctxlat
->is_single_const ())
2745 (*known_contexts
)[i
] = ctxlat
->values
->value
;
2749 vec
<ipa_agg_jf_item
, va_gc
> *agg_items
;
2750 struct ipa_agg_jump_function
*ajf
;
2752 agg_items
= context_independent_aggregate_values (plats
);
2753 ajf
= &(*known_aggs
)[i
];
2754 ajf
->items
= agg_items
;
2755 ajf
->by_ref
= plats
->aggs_by_ref
;
2756 ret
|= agg_items
!= NULL
;
2763 /* The current interface in ipa-inline-analysis requires a pointer vector.
2766 FIXME: That interface should be re-worked, this is slightly silly. Still,
2767 I'd like to discuss how to change it first and this demonstrates the
2770 static vec
<ipa_agg_jump_function_p
>
2771 agg_jmp_p_vec_for_t_vec (vec
<ipa_agg_jump_function
> known_aggs
)
2773 vec
<ipa_agg_jump_function_p
> ret
;
2774 struct ipa_agg_jump_function
*ajf
;
2777 ret
.create (known_aggs
.length ());
2778 FOR_EACH_VEC_ELT (known_aggs
, i
, ajf
)
2779 ret
.quick_push (ajf
);
2783 /* Perform time and size measurement of NODE with the context given in
2784 KNOWN_CSTS, KNOWN_CONTEXTS and KNOWN_AGGS, calculate the benefit and cost
2785 given BASE_TIME of the node without specialization, REMOVABLE_PARAMS_COST of
2786 all context-independent removable parameters and EST_MOVE_COST of estimated
2787 movement of the considered parameter and store it into VAL. */
2790 perform_estimation_of_a_value (cgraph_node
*node
, vec
<tree
> known_csts
,
2791 vec
<ipa_polymorphic_call_context
> known_contexts
,
2792 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
,
2793 int removable_params_cost
,
2794 int est_move_cost
, ipcp_value_base
*val
)
2796 int size
, time_benefit
;
2797 sreal time
, base_time
;
2800 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
2801 known_aggs_ptrs
, &size
, &time
,
2802 &base_time
, &hints
);
2804 if (base_time
> 65535)
2806 time_benefit
= base_time
.to_int ()
2807 + devirtualization_time_bonus (node
, known_csts
, known_contexts
,
2809 + hint_time_bonus (hints
)
2810 + removable_params_cost
+ est_move_cost
;
2812 gcc_checking_assert (size
>=0);
2813 /* The inliner-heuristics based estimates may think that in certain
2814 contexts some functions do not have any size at all but we want
2815 all specializations to have at least a tiny cost, not least not to
2820 val
->local_time_benefit
= time_benefit
;
2821 val
->local_size_cost
= size
;
2824 /* Iterate over known values of parameters of NODE and estimate the local
2825 effects in terms of time and size they have. */
2828 estimate_local_effects (struct cgraph_node
*node
)
2830 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2831 int i
, count
= ipa_get_param_count (info
);
2832 vec
<tree
> known_csts
;
2833 vec
<ipa_polymorphic_call_context
> known_contexts
;
2834 vec
<ipa_agg_jump_function
> known_aggs
;
2835 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
;
2837 int removable_params_cost
;
2839 if (!count
|| !ipcp_versionable_function_p (node
))
2842 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2843 fprintf (dump_file
, "\nEstimating effects for %s.\n", node
->dump_name ());
2845 always_const
= gather_context_independent_values (info
, &known_csts
,
2846 &known_contexts
, &known_aggs
,
2847 &removable_params_cost
);
2848 known_aggs_ptrs
= agg_jmp_p_vec_for_t_vec (known_aggs
);
2849 int devirt_bonus
= devirtualization_time_bonus (node
, known_csts
,
2850 known_contexts
, known_aggs_ptrs
);
2851 if (always_const
|| devirt_bonus
2852 || (removable_params_cost
&& node
->local
.can_change_signature
))
2854 struct caller_statistics stats
;
2856 sreal time
, base_time
;
2859 init_caller_stats (&stats
);
2860 node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
2862 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
2863 known_aggs_ptrs
, &size
, &time
,
2864 &base_time
, &hints
);
2865 time
-= devirt_bonus
;
2866 time
-= hint_time_bonus (hints
);
2867 time
-= removable_params_cost
;
2868 size
-= stats
.n_calls
* removable_params_cost
;
2871 fprintf (dump_file
, " - context independent values, size: %i, "
2872 "time_benefit: %f\n", size
, (base_time
- time
).to_double ());
2874 if (size
<= 0 || node
->local
.local
)
2876 info
->do_clone_for_all_contexts
= true;
2879 fprintf (dump_file
, " Decided to specialize for all "
2880 "known contexts, code not going to grow.\n");
2882 else if (good_cloning_opportunity_p (node
,
2883 MAX ((base_time
- time
).to_int (),
2885 stats
.freq_sum
, stats
.count_sum
,
2888 if (size
+ overall_size
<= max_new_size
)
2890 info
->do_clone_for_all_contexts
= true;
2891 overall_size
+= size
;
2894 fprintf (dump_file
, " Decided to specialize for all "
2895 "known contexts, growth deemed beneficial.\n");
2897 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2898 fprintf (dump_file
, " Not cloning for all contexts because "
2899 "max_new_size would be reached with %li.\n",
2900 size
+ overall_size
);
2902 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2903 fprintf (dump_file
, " Not cloning for all contexts because "
2904 "!good_cloning_opportunity_p.\n");
2908 for (i
= 0; i
< count
; i
++)
2910 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2911 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
2912 ipcp_value
<tree
> *val
;
2919 for (val
= lat
->values
; val
; val
= val
->next
)
2921 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
2922 known_csts
[i
] = val
->value
;
2924 int emc
= estimate_move_cost (TREE_TYPE (val
->value
), true);
2925 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
2927 removable_params_cost
, emc
, val
);
2929 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2931 fprintf (dump_file
, " - estimates for value ");
2932 print_ipcp_constant_value (dump_file
, val
->value
);
2933 fprintf (dump_file
, " for ");
2934 ipa_dump_param (dump_file
, info
, i
);
2935 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
2936 val
->local_time_benefit
, val
->local_size_cost
);
2939 known_csts
[i
] = NULL_TREE
;
2942 for (i
= 0; i
< count
; i
++)
2944 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2946 if (!plats
->virt_call
)
2949 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
2950 ipcp_value
<ipa_polymorphic_call_context
> *val
;
2954 || !known_contexts
[i
].useless_p ())
2957 for (val
= ctxlat
->values
; val
; val
= val
->next
)
2959 known_contexts
[i
] = val
->value
;
2960 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
2962 removable_params_cost
, 0, val
);
2964 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2966 fprintf (dump_file
, " - estimates for polymorphic context ");
2967 print_ipcp_constant_value (dump_file
, val
->value
);
2968 fprintf (dump_file
, " for ");
2969 ipa_dump_param (dump_file
, info
, i
);
2970 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
2971 val
->local_time_benefit
, val
->local_size_cost
);
2974 known_contexts
[i
] = ipa_polymorphic_call_context ();
2977 for (i
= 0; i
< count
; i
++)
2979 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2980 struct ipa_agg_jump_function
*ajf
;
2981 struct ipcp_agg_lattice
*aglat
;
2983 if (plats
->aggs_bottom
|| !plats
->aggs
)
2986 ajf
= &known_aggs
[i
];
2987 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2989 ipcp_value
<tree
> *val
;
2990 if (aglat
->bottom
|| !aglat
->values
2991 /* If the following is true, the one value is in known_aggs. */
2992 || (!plats
->aggs_contain_variable
2993 && aglat
->is_single_const ()))
2996 for (val
= aglat
->values
; val
; val
= val
->next
)
2998 struct ipa_agg_jf_item item
;
3000 item
.offset
= aglat
->offset
;
3001 item
.value
= val
->value
;
3002 vec_safe_push (ajf
->items
, item
);
3004 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
3006 removable_params_cost
, 0, val
);
3008 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3010 fprintf (dump_file
, " - estimates for value ");
3011 print_ipcp_constant_value (dump_file
, val
->value
);
3012 fprintf (dump_file
, " for ");
3013 ipa_dump_param (dump_file
, info
, i
);
3014 fprintf (dump_file
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
3015 "]: time_benefit: %i, size: %i\n",
3016 plats
->aggs_by_ref
? "ref " : "",
3018 val
->local_time_benefit
, val
->local_size_cost
);
3026 for (i
= 0; i
< count
; i
++)
3027 vec_free (known_aggs
[i
].items
);
3029 known_csts
.release ();
3030 known_contexts
.release ();
3031 known_aggs
.release ();
3032 known_aggs_ptrs
.release ();
3036 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
3037 topological sort of values. */
3039 template <typename valtype
>
3041 value_topo_info
<valtype
>::add_val (ipcp_value
<valtype
> *cur_val
)
3043 ipcp_value_source
<valtype
> *src
;
3049 cur_val
->dfs
= dfs_counter
;
3050 cur_val
->low_link
= dfs_counter
;
3052 cur_val
->topo_next
= stack
;
3054 cur_val
->on_stack
= true;
3056 for (src
= cur_val
->sources
; src
; src
= src
->next
)
3059 if (src
->val
->dfs
== 0)
3062 if (src
->val
->low_link
< cur_val
->low_link
)
3063 cur_val
->low_link
= src
->val
->low_link
;
3065 else if (src
->val
->on_stack
3066 && src
->val
->dfs
< cur_val
->low_link
)
3067 cur_val
->low_link
= src
->val
->dfs
;
3070 if (cur_val
->dfs
== cur_val
->low_link
)
3072 ipcp_value
<valtype
> *v
, *scc_list
= NULL
;
3077 stack
= v
->topo_next
;
3078 v
->on_stack
= false;
3080 v
->scc_next
= scc_list
;
3083 while (v
!= cur_val
);
3085 cur_val
->topo_next
= values_topo
;
3086 values_topo
= cur_val
;
3090 /* Add all values in lattices associated with NODE to the topological sort if
3091 they are not there yet. */
3094 add_all_node_vals_to_toposort (cgraph_node
*node
, ipa_topo_info
*topo
)
3096 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3097 int i
, count
= ipa_get_param_count (info
);
3099 for (i
= 0; i
< count
; i
++)
3101 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3102 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
3103 struct ipcp_agg_lattice
*aglat
;
3107 ipcp_value
<tree
> *val
;
3108 for (val
= lat
->values
; val
; val
= val
->next
)
3109 topo
->constants
.add_val (val
);
3112 if (!plats
->aggs_bottom
)
3113 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3116 ipcp_value
<tree
> *val
;
3117 for (val
= aglat
->values
; val
; val
= val
->next
)
3118 topo
->constants
.add_val (val
);
3121 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
3122 if (!ctxlat
->bottom
)
3124 ipcp_value
<ipa_polymorphic_call_context
> *ctxval
;
3125 for (ctxval
= ctxlat
->values
; ctxval
; ctxval
= ctxval
->next
)
3126 topo
->contexts
.add_val (ctxval
);
3131 /* One pass of constants propagation along the call graph edges, from callers
3132 to callees (requires topological ordering in TOPO), iterate over strongly
3133 connected components. */
3136 propagate_constants_topo (struct ipa_topo_info
*topo
)
3140 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
3143 struct cgraph_node
*v
, *node
= topo
->order
[i
];
3144 vec
<cgraph_node
*> cycle_nodes
= ipa_get_nodes_in_cycle (node
);
3146 /* First, iteratively propagate within the strongly connected component
3147 until all lattices stabilize. */
3148 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
3149 if (v
->has_gimple_body_p ())
3150 push_node_to_stack (topo
, v
);
3152 v
= pop_node_from_stack (topo
);
3155 struct cgraph_edge
*cs
;
3157 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3158 if (ipa_edge_within_scc (cs
))
3160 IPA_NODE_REF (v
)->node_within_scc
= true;
3161 if (propagate_constants_across_call (cs
))
3162 push_node_to_stack (topo
, cs
->callee
->function_symbol ());
3164 v
= pop_node_from_stack (topo
);
3167 /* Afterwards, propagate along edges leading out of the SCC, calculates
3168 the local effects of the discovered constants and all valid values to
3169 their topological sort. */
3170 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
3171 if (v
->has_gimple_body_p ())
3173 struct cgraph_edge
*cs
;
3175 estimate_local_effects (v
);
3176 add_all_node_vals_to_toposort (v
, topo
);
3177 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3178 if (!ipa_edge_within_scc (cs
))
3179 propagate_constants_across_call (cs
);
3181 cycle_nodes
.release ();
3186 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
3187 the bigger one if otherwise. */
3190 safe_add (int a
, int b
)
3192 if (a
> INT_MAX
/2 || b
> INT_MAX
/2)
3193 return a
> b
? a
: b
;
3199 /* Propagate the estimated effects of individual values along the topological
3200 from the dependent values to those they depend on. */
3202 template <typename valtype
>
3204 value_topo_info
<valtype
>::propagate_effects ()
3206 ipcp_value
<valtype
> *base
;
3208 for (base
= values_topo
; base
; base
= base
->topo_next
)
3210 ipcp_value_source
<valtype
> *src
;
3211 ipcp_value
<valtype
> *val
;
3212 int time
= 0, size
= 0;
3214 for (val
= base
; val
; val
= val
->scc_next
)
3216 time
= safe_add (time
,
3217 val
->local_time_benefit
+ val
->prop_time_benefit
);
3218 size
= safe_add (size
, val
->local_size_cost
+ val
->prop_size_cost
);
3221 for (val
= base
; val
; val
= val
->scc_next
)
3222 for (src
= val
->sources
; src
; src
= src
->next
)
3224 && src
->cs
->maybe_hot_p ())
3226 src
->val
->prop_time_benefit
= safe_add (time
,
3227 src
->val
->prop_time_benefit
);
3228 src
->val
->prop_size_cost
= safe_add (size
,
3229 src
->val
->prop_size_cost
);
3235 /* Propagate constants, polymorphic contexts and their effects from the
3236 summaries interprocedurally. */
3239 ipcp_propagate_stage (struct ipa_topo_info
*topo
)
3241 struct cgraph_node
*node
;
3244 fprintf (dump_file
, "\n Propagating constants:\n\n");
3246 FOR_EACH_DEFINED_FUNCTION (node
)
3248 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3250 determine_versionability (node
, info
);
3251 if (node
->has_gimple_body_p ())
3253 info
->lattices
= XCNEWVEC (struct ipcp_param_lattices
,
3254 ipa_get_param_count (info
));
3255 initialize_node_lattices (node
);
3257 if (node
->definition
&& !node
->alias
)
3258 overall_size
+= ipa_fn_summaries
->get (node
)->self_size
;
3259 if (node
->count
> max_count
)
3260 max_count
= node
->count
;
3263 max_new_size
= overall_size
;
3264 if (max_new_size
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
3265 max_new_size
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
3266 max_new_size
+= max_new_size
* PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH
) / 100 + 1;
3269 fprintf (dump_file
, "\noverall_size: %li, max_new_size: %li\n",
3270 overall_size
, max_new_size
);
3272 propagate_constants_topo (topo
);
3274 ipcp_verify_propagated_values ();
3275 topo
->constants
.propagate_effects ();
3276 topo
->contexts
.propagate_effects ();
3280 fprintf (dump_file
, "\nIPA lattices after all propagation:\n");
3281 print_all_lattices (dump_file
, (dump_flags
& TDF_DETAILS
), true);
3285 /* Discover newly direct outgoing edges from NODE which is a new clone with
3286 known KNOWN_CSTS and make them direct. */
3289 ipcp_discover_new_direct_edges (struct cgraph_node
*node
,
3290 vec
<tree
> known_csts
,
3291 vec
<ipa_polymorphic_call_context
>
3293 struct ipa_agg_replacement_value
*aggvals
)
3295 struct cgraph_edge
*ie
, *next_ie
;
3298 for (ie
= node
->indirect_calls
; ie
; ie
= next_ie
)
3303 next_ie
= ie
->next_callee
;
3304 target
= ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
3305 vNULL
, aggvals
, &speculative
);
3308 bool agg_contents
= ie
->indirect_info
->agg_contents
;
3309 bool polymorphic
= ie
->indirect_info
->polymorphic
;
3310 int param_index
= ie
->indirect_info
->param_index
;
3311 struct cgraph_edge
*cs
= ipa_make_edge_direct_to_target (ie
, target
,
3315 if (cs
&& !agg_contents
&& !polymorphic
)
3317 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3318 int c
= ipa_get_controlled_uses (info
, param_index
);
3319 if (c
!= IPA_UNDESCRIBED_USE
)
3321 struct ipa_ref
*to_del
;
3324 ipa_set_controlled_uses (info
, param_index
, c
);
3325 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3326 fprintf (dump_file
, " controlled uses count of param "
3327 "%i bumped down to %i\n", param_index
, c
);
3329 && (to_del
= node
->find_reference (cs
->callee
, NULL
, 0)))
3331 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3332 fprintf (dump_file
, " and even removing its "
3333 "cloning-created reference\n");
3334 to_del
->remove_reference ();
3340 /* Turning calls to direct calls will improve overall summary. */
3342 ipa_update_overall_fn_summary (node
);
3345 /* Vector of pointers which for linked lists of clones of an original crgaph
3348 static vec
<cgraph_edge
*> next_edge_clone
;
3349 static vec
<cgraph_edge
*> prev_edge_clone
;
3352 grow_edge_clone_vectors (void)
3354 if (next_edge_clone
.length ()
3355 <= (unsigned) symtab
->edges_max_uid
)
3356 next_edge_clone
.safe_grow_cleared (symtab
->edges_max_uid
+ 1);
3357 if (prev_edge_clone
.length ()
3358 <= (unsigned) symtab
->edges_max_uid
)
3359 prev_edge_clone
.safe_grow_cleared (symtab
->edges_max_uid
+ 1);
3362 /* Edge duplication hook to grow the appropriate linked list in
3366 ipcp_edge_duplication_hook (struct cgraph_edge
*src
, struct cgraph_edge
*dst
,
3369 grow_edge_clone_vectors ();
3371 struct cgraph_edge
*old_next
= next_edge_clone
[src
->uid
];
3373 prev_edge_clone
[old_next
->uid
] = dst
;
3374 prev_edge_clone
[dst
->uid
] = src
;
3376 next_edge_clone
[dst
->uid
] = old_next
;
3377 next_edge_clone
[src
->uid
] = dst
;
3380 /* Hook that is called by cgraph.c when an edge is removed. */
3383 ipcp_edge_removal_hook (struct cgraph_edge
*cs
, void *)
3385 grow_edge_clone_vectors ();
3387 struct cgraph_edge
*prev
= prev_edge_clone
[cs
->uid
];
3388 struct cgraph_edge
*next
= next_edge_clone
[cs
->uid
];
3390 next_edge_clone
[prev
->uid
] = next
;
3392 prev_edge_clone
[next
->uid
] = prev
;
3395 /* See if NODE is a clone with a known aggregate value at a given OFFSET of a
3396 parameter with the given INDEX. */
3399 get_clone_agg_value (struct cgraph_node
*node
, HOST_WIDE_INT offset
,
3402 struct ipa_agg_replacement_value
*aggval
;
3404 aggval
= ipa_get_agg_replacements_for_node (node
);
3407 if (aggval
->offset
== offset
3408 && aggval
->index
== index
)
3409 return aggval
->value
;
3410 aggval
= aggval
->next
;
3415 /* Return true is NODE is DEST or its clone for all contexts. */
3418 same_node_or_its_all_contexts_clone_p (cgraph_node
*node
, cgraph_node
*dest
)
3423 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3424 return info
->is_all_contexts_clone
&& info
->ipcp_orig_node
== dest
;
3427 /* Return true if edge CS does bring about the value described by SRC to node
3428 DEST or its clone for all contexts. */
3431 cgraph_edge_brings_value_p (cgraph_edge
*cs
, ipcp_value_source
<tree
> *src
,
3434 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3435 enum availability availability
;
3436 cgraph_node
*real_dest
= cs
->callee
->function_symbol (&availability
);
3438 if (!same_node_or_its_all_contexts_clone_p (real_dest
, dest
)
3439 || availability
<= AVAIL_INTERPOSABLE
3440 || caller_info
->node_dead
)
3445 if (caller_info
->ipcp_orig_node
)
3448 if (src
->offset
== -1)
3449 t
= caller_info
->known_csts
[src
->index
];
3451 t
= get_clone_agg_value (cs
->caller
, src
->offset
, src
->index
);
3452 return (t
!= NULL_TREE
3453 && values_equal_for_ipcp_p (src
->val
->value
, t
));
3457 struct ipcp_agg_lattice
*aglat
;
3458 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
3460 if (src
->offset
== -1)
3461 return (plats
->itself
.is_single_const ()
3462 && values_equal_for_ipcp_p (src
->val
->value
,
3463 plats
->itself
.values
->value
));
3466 if (plats
->aggs_bottom
|| plats
->aggs_contain_variable
)
3468 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3469 if (aglat
->offset
== src
->offset
)
3470 return (aglat
->is_single_const ()
3471 && values_equal_for_ipcp_p (src
->val
->value
,
3472 aglat
->values
->value
));
3478 /* Return true if edge CS does bring about the value described by SRC to node
3479 DEST or its clone for all contexts. */
3482 cgraph_edge_brings_value_p (cgraph_edge
*cs
,
3483 ipcp_value_source
<ipa_polymorphic_call_context
> *src
,
3486 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3487 cgraph_node
*real_dest
= cs
->callee
->function_symbol ();
3489 if (!same_node_or_its_all_contexts_clone_p (real_dest
, dest
)
3490 || caller_info
->node_dead
)
3495 if (caller_info
->ipcp_orig_node
)
3496 return (caller_info
->known_contexts
.length () > (unsigned) src
->index
)
3497 && values_equal_for_ipcp_p (src
->val
->value
,
3498 caller_info
->known_contexts
[src
->index
]);
3500 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
3502 return plats
->ctxlat
.is_single_const ()
3503 && values_equal_for_ipcp_p (src
->val
->value
,
3504 plats
->ctxlat
.values
->value
);
3507 /* Get the next clone in the linked list of clones of an edge. */
3509 static inline struct cgraph_edge
*
3510 get_next_cgraph_edge_clone (struct cgraph_edge
*cs
)
3512 return next_edge_clone
[cs
->uid
];
3515 /* Given VAL that is intended for DEST, iterate over all its sources and if
3516 they still hold, add their edge frequency and their number into *FREQUENCY
3517 and *CALLER_COUNT respectively. */
3519 template <typename valtype
>
3521 get_info_about_necessary_edges (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
3523 gcov_type
*count_sum
, int *caller_count
)
3525 ipcp_value_source
<valtype
> *src
;
3526 int freq
= 0, count
= 0;
3530 for (src
= val
->sources
; src
; src
= src
->next
)
3532 struct cgraph_edge
*cs
= src
->cs
;
3535 if (cgraph_edge_brings_value_p (cs
, src
, dest
))
3538 freq
+= cs
->frequency
;
3540 hot
|= cs
->maybe_hot_p ();
3542 cs
= get_next_cgraph_edge_clone (cs
);
3548 *caller_count
= count
;
3552 /* Return a vector of incoming edges that do bring value VAL to node DEST. It
3553 is assumed their number is known and equal to CALLER_COUNT. */
3555 template <typename valtype
>
3556 static vec
<cgraph_edge
*>
3557 gather_edges_for_value (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
3560 ipcp_value_source
<valtype
> *src
;
3561 vec
<cgraph_edge
*> ret
;
3563 ret
.create (caller_count
);
3564 for (src
= val
->sources
; src
; src
= src
->next
)
3566 struct cgraph_edge
*cs
= src
->cs
;
3569 if (cgraph_edge_brings_value_p (cs
, src
, dest
))
3570 ret
.quick_push (cs
);
3571 cs
= get_next_cgraph_edge_clone (cs
);
3578 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
3579 Return it or NULL if for some reason it cannot be created. */
3581 static struct ipa_replace_map
*
3582 get_replacement_map (struct ipa_node_params
*info
, tree value
, int parm_num
)
3584 struct ipa_replace_map
*replace_map
;
3587 replace_map
= ggc_alloc
<ipa_replace_map
> ();
3590 fprintf (dump_file
, " replacing ");
3591 ipa_dump_param (dump_file
, info
, parm_num
);
3593 fprintf (dump_file
, " with const ");
3594 print_generic_expr (dump_file
, value
);
3595 fprintf (dump_file
, "\n");
3597 replace_map
->old_tree
= NULL
;
3598 replace_map
->parm_num
= parm_num
;
3599 replace_map
->new_tree
= value
;
3600 replace_map
->replace_p
= true;
3601 replace_map
->ref_p
= false;
3606 /* Dump new profiling counts */
3609 dump_profile_updates (struct cgraph_node
*orig_node
,
3610 struct cgraph_node
*new_node
)
3612 struct cgraph_edge
*cs
;
3614 fprintf (dump_file
, " setting count of the specialized node to "
3615 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) new_node
->count
);
3616 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3617 fprintf (dump_file
, " edge to %s has count "
3618 HOST_WIDE_INT_PRINT_DEC
"\n",
3619 cs
->callee
->name (), (HOST_WIDE_INT
) cs
->count
);
3621 fprintf (dump_file
, " setting count of the original node to "
3622 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) orig_node
->count
);
3623 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3624 fprintf (dump_file
, " edge to %s is left with "
3625 HOST_WIDE_INT_PRINT_DEC
"\n",
3626 cs
->callee
->name (), (HOST_WIDE_INT
) cs
->count
);
3629 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
3630 their profile information to reflect this. */
3633 update_profiling_info (struct cgraph_node
*orig_node
,
3634 struct cgraph_node
*new_node
)
3636 struct cgraph_edge
*cs
;
3637 struct caller_statistics stats
;
3638 gcov_type new_sum
, orig_sum
;
3639 gcov_type remainder
, orig_node_count
= orig_node
->count
;
3641 if (orig_node_count
== 0)
3644 init_caller_stats (&stats
);
3645 orig_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
3647 orig_sum
= stats
.count_sum
;
3648 init_caller_stats (&stats
);
3649 new_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
3651 new_sum
= stats
.count_sum
;
3653 if (orig_node_count
< orig_sum
+ new_sum
)
3656 fprintf (dump_file
, " Problem: node %s has too low count "
3657 HOST_WIDE_INT_PRINT_DEC
" while the sum of incoming "
3658 "counts is " HOST_WIDE_INT_PRINT_DEC
"\n",
3659 orig_node
->dump_name (),
3660 (HOST_WIDE_INT
) orig_node_count
,
3661 (HOST_WIDE_INT
) (orig_sum
+ new_sum
));
3663 orig_node_count
= (orig_sum
+ new_sum
) * 12 / 10;
3665 fprintf (dump_file
, " proceeding by pretending it was "
3666 HOST_WIDE_INT_PRINT_DEC
"\n",
3667 (HOST_WIDE_INT
) orig_node_count
);
3670 new_node
->count
= new_sum
;
3671 remainder
= orig_node_count
- new_sum
;
3672 orig_node
->count
= remainder
;
3674 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3676 cs
->count
= apply_probability (cs
->count
,
3677 GCOV_COMPUTE_SCALE (new_sum
,
3682 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3683 cs
->count
= apply_probability (cs
->count
,
3684 GCOV_COMPUTE_SCALE (remainder
,
3688 dump_profile_updates (orig_node
, new_node
);
3691 /* Update the respective profile of specialized NEW_NODE and the original
3692 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
3693 have been redirected to the specialized version. */
3696 update_specialized_profile (struct cgraph_node
*new_node
,
3697 struct cgraph_node
*orig_node
,
3698 gcov_type redirected_sum
)
3700 struct cgraph_edge
*cs
;
3701 gcov_type new_node_count
, orig_node_count
= orig_node
->count
;
3704 fprintf (dump_file
, " the sum of counts of redirected edges is "
3705 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) redirected_sum
);
3706 if (orig_node_count
== 0)
3709 gcc_assert (orig_node_count
>= redirected_sum
);
3711 new_node_count
= new_node
->count
;
3712 new_node
->count
+= redirected_sum
;
3713 orig_node
->count
-= redirected_sum
;
3715 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3717 cs
->count
+= apply_probability (cs
->count
,
3718 GCOV_COMPUTE_SCALE (redirected_sum
,
3723 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3725 gcov_type dec
= apply_probability (cs
->count
,
3726 GCOV_COMPUTE_SCALE (redirected_sum
,
3728 if (dec
< cs
->count
)
3735 dump_profile_updates (orig_node
, new_node
);
3738 /* Create a specialized version of NODE with known constants in KNOWN_CSTS,
3739 known contexts in KNOWN_CONTEXTS and known aggregate values in AGGVALS and
3740 redirect all edges in CALLERS to it. */
3742 static struct cgraph_node
*
3743 create_specialized_node (struct cgraph_node
*node
,
3744 vec
<tree
> known_csts
,
3745 vec
<ipa_polymorphic_call_context
> known_contexts
,
3746 struct ipa_agg_replacement_value
*aggvals
,
3747 vec
<cgraph_edge
*> callers
)
3749 struct ipa_node_params
*new_info
, *info
= IPA_NODE_REF (node
);
3750 vec
<ipa_replace_map
*, va_gc
> *replace_trees
= NULL
;
3751 struct ipa_agg_replacement_value
*av
;
3752 struct cgraph_node
*new_node
;
3753 int i
, count
= ipa_get_param_count (info
);
3754 bitmap args_to_skip
;
3756 gcc_assert (!info
->ipcp_orig_node
);
3758 if (node
->local
.can_change_signature
)
3760 args_to_skip
= BITMAP_GGC_ALLOC ();
3761 for (i
= 0; i
< count
; i
++)
3763 tree t
= known_csts
[i
];
3765 if (t
|| !ipa_is_param_used (info
, i
))
3766 bitmap_set_bit (args_to_skip
, i
);
3771 args_to_skip
= NULL
;
3772 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3773 fprintf (dump_file
, " cannot change function signature\n");
3776 for (i
= 0; i
< count
; i
++)
3778 tree t
= known_csts
[i
];
3781 struct ipa_replace_map
*replace_map
;
3783 gcc_checking_assert (TREE_CODE (t
) != TREE_BINFO
);
3784 replace_map
= get_replacement_map (info
, t
, i
);
3786 vec_safe_push (replace_trees
, replace_map
);
3790 new_node
= node
->create_virtual_clone (callers
, replace_trees
,
3791 args_to_skip
, "constprop");
3792 ipa_set_node_agg_value_chain (new_node
, aggvals
);
3793 for (av
= aggvals
; av
; av
= av
->next
)
3794 new_node
->maybe_create_reference (av
->value
, NULL
);
3796 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3798 fprintf (dump_file
, " the new node is %s.\n", new_node
->dump_name ());
3799 if (known_contexts
.exists ())
3801 for (i
= 0; i
< count
; i
++)
3802 if (!known_contexts
[i
].useless_p ())
3804 fprintf (dump_file
, " known ctx %i is ", i
);
3805 known_contexts
[i
].dump (dump_file
);
3809 ipa_dump_agg_replacement_values (dump_file
, aggvals
);
3811 ipa_check_create_node_params ();
3812 update_profiling_info (node
, new_node
);
3813 new_info
= IPA_NODE_REF (new_node
);
3814 new_info
->ipcp_orig_node
= node
;
3815 new_info
->known_csts
= known_csts
;
3816 new_info
->known_contexts
= known_contexts
;
3818 ipcp_discover_new_direct_edges (new_node
, known_csts
, known_contexts
, aggvals
);
3824 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
3825 KNOWN_CSTS with constants that are also known for all of the CALLERS. */
3828 find_more_scalar_values_for_callers_subset (struct cgraph_node
*node
,
3829 vec
<tree
> known_csts
,
3830 vec
<cgraph_edge
*> callers
)
3832 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3833 int i
, count
= ipa_get_param_count (info
);
3835 for (i
= 0; i
< count
; i
++)
3837 struct cgraph_edge
*cs
;
3838 tree newval
= NULL_TREE
;
3842 if (ipa_get_scalar_lat (info
, i
)->bottom
|| known_csts
[i
])
3845 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3847 struct ipa_jump_func
*jump_func
;
3850 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
))
3852 && call_passes_through_thunk_p (cs
))
3853 || (!cs
->callee
->instrumentation_clone
3854 && cs
->callee
->function_symbol ()->instrumentation_clone
))
3859 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
3860 t
= ipa_value_from_jfunc (IPA_NODE_REF (cs
->caller
), jump_func
);
3863 && !values_equal_for_ipcp_p (t
, newval
))
3864 || (!first
&& !newval
))
3876 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3878 fprintf (dump_file
, " adding an extra known scalar value ");
3879 print_ipcp_constant_value (dump_file
, newval
);
3880 fprintf (dump_file
, " for ");
3881 ipa_dump_param (dump_file
, info
, i
);
3882 fprintf (dump_file
, "\n");
3885 known_csts
[i
] = newval
;
3890 /* Given a NODE and a subset of its CALLERS, try to populate plank slots in
3891 KNOWN_CONTEXTS with polymorphic contexts that are also known for all of the
3895 find_more_contexts_for_caller_subset (cgraph_node
*node
,
3896 vec
<ipa_polymorphic_call_context
>
3898 vec
<cgraph_edge
*> callers
)
3900 ipa_node_params
*info
= IPA_NODE_REF (node
);
3901 int i
, count
= ipa_get_param_count (info
);
3903 for (i
= 0; i
< count
; i
++)
3907 if (ipa_get_poly_ctx_lat (info
, i
)->bottom
3908 || (known_contexts
->exists ()
3909 && !(*known_contexts
)[i
].useless_p ()))
3912 ipa_polymorphic_call_context newval
;
3916 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3918 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
)))
3920 ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
),
3922 ipa_polymorphic_call_context ctx
;
3923 ctx
= ipa_context_from_jfunc (IPA_NODE_REF (cs
->caller
), cs
, i
,
3931 newval
.meet_with (ctx
);
3932 if (newval
.useless_p ())
3936 if (!newval
.useless_p ())
3938 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3940 fprintf (dump_file
, " adding an extra known polymorphic "
3942 print_ipcp_constant_value (dump_file
, newval
);
3943 fprintf (dump_file
, " for ");
3944 ipa_dump_param (dump_file
, info
, i
);
3945 fprintf (dump_file
, "\n");
3948 if (!known_contexts
->exists ())
3949 known_contexts
->safe_grow_cleared (ipa_get_param_count (info
));
3950 (*known_contexts
)[i
] = newval
;
3956 /* Go through PLATS and create a vector of values consisting of values and
3957 offsets (minus OFFSET) of lattices that contain only a single value. */
3959 static vec
<ipa_agg_jf_item
>
3960 copy_plats_to_inter (struct ipcp_param_lattices
*plats
, HOST_WIDE_INT offset
)
3962 vec
<ipa_agg_jf_item
> res
= vNULL
;
3964 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
3967 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3968 if (aglat
->is_single_const ())
3970 struct ipa_agg_jf_item ti
;
3971 ti
.offset
= aglat
->offset
- offset
;
3972 ti
.value
= aglat
->values
->value
;
3978 /* Intersect all values in INTER with single value lattices in PLATS (while
3979 subtracting OFFSET). */
3982 intersect_with_plats (struct ipcp_param_lattices
*plats
,
3983 vec
<ipa_agg_jf_item
> *inter
,
3984 HOST_WIDE_INT offset
)
3986 struct ipcp_agg_lattice
*aglat
;
3987 struct ipa_agg_jf_item
*item
;
3990 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
3996 aglat
= plats
->aggs
;
3997 FOR_EACH_VEC_ELT (*inter
, k
, item
)
4004 if (aglat
->offset
- offset
> item
->offset
)
4006 if (aglat
->offset
- offset
== item
->offset
)
4008 gcc_checking_assert (item
->value
);
4009 if (values_equal_for_ipcp_p (item
->value
, aglat
->values
->value
))
4013 aglat
= aglat
->next
;
4016 item
->value
= NULL_TREE
;
4020 /* Copy aggregate replacement values of NODE (which is an IPA-CP clone) to the
4021 vector result while subtracting OFFSET from the individual value offsets. */
4023 static vec
<ipa_agg_jf_item
>
4024 agg_replacements_to_vector (struct cgraph_node
*node
, int index
,
4025 HOST_WIDE_INT offset
)
4027 struct ipa_agg_replacement_value
*av
;
4028 vec
<ipa_agg_jf_item
> res
= vNULL
;
4030 for (av
= ipa_get_agg_replacements_for_node (node
); av
; av
= av
->next
)
4031 if (av
->index
== index
4032 && (av
->offset
- offset
) >= 0)
4034 struct ipa_agg_jf_item item
;
4035 gcc_checking_assert (av
->value
);
4036 item
.offset
= av
->offset
- offset
;
4037 item
.value
= av
->value
;
4038 res
.safe_push (item
);
4044 /* Intersect all values in INTER with those that we have already scheduled to
4045 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
4046 (while subtracting OFFSET). */
4049 intersect_with_agg_replacements (struct cgraph_node
*node
, int index
,
4050 vec
<ipa_agg_jf_item
> *inter
,
4051 HOST_WIDE_INT offset
)
4053 struct ipa_agg_replacement_value
*srcvals
;
4054 struct ipa_agg_jf_item
*item
;
4057 srcvals
= ipa_get_agg_replacements_for_node (node
);
4064 FOR_EACH_VEC_ELT (*inter
, i
, item
)
4066 struct ipa_agg_replacement_value
*av
;
4070 for (av
= srcvals
; av
; av
= av
->next
)
4072 gcc_checking_assert (av
->value
);
4073 if (av
->index
== index
4074 && av
->offset
- offset
== item
->offset
)
4076 if (values_equal_for_ipcp_p (item
->value
, av
->value
))
4082 item
->value
= NULL_TREE
;
4086 /* Intersect values in INTER with aggregate values that come along edge CS to
4087 parameter number INDEX and return it. If INTER does not actually exist yet,
4088 copy all incoming values to it. If we determine we ended up with no values
4089 whatsoever, return a released vector. */
4091 static vec
<ipa_agg_jf_item
>
4092 intersect_aggregates_with_edge (struct cgraph_edge
*cs
, int index
,
4093 vec
<ipa_agg_jf_item
> inter
)
4095 struct ipa_jump_func
*jfunc
;
4096 jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), index
);
4097 if (jfunc
->type
== IPA_JF_PASS_THROUGH
4098 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
4100 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4101 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
4103 if (caller_info
->ipcp_orig_node
)
4105 struct cgraph_node
*orig_node
= caller_info
->ipcp_orig_node
;
4106 struct ipcp_param_lattices
*orig_plats
;
4107 orig_plats
= ipa_get_parm_lattices (IPA_NODE_REF (orig_node
),
4109 if (agg_pass_through_permissible_p (orig_plats
, jfunc
))
4111 if (!inter
.exists ())
4112 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, 0);
4114 intersect_with_agg_replacements (cs
->caller
, src_idx
,
4125 struct ipcp_param_lattices
*src_plats
;
4126 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
4127 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
4129 /* Currently we do not produce clobber aggregate jump
4130 functions, adjust when we do. */
4131 gcc_checking_assert (!jfunc
->agg
.items
);
4132 if (!inter
.exists ())
4133 inter
= copy_plats_to_inter (src_plats
, 0);
4135 intersect_with_plats (src_plats
, &inter
, 0);
4144 else if (jfunc
->type
== IPA_JF_ANCESTOR
4145 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
4147 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4148 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
4149 struct ipcp_param_lattices
*src_plats
;
4150 HOST_WIDE_INT delta
= ipa_get_jf_ancestor_offset (jfunc
);
4152 if (caller_info
->ipcp_orig_node
)
4154 if (!inter
.exists ())
4155 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, delta
);
4157 intersect_with_agg_replacements (cs
->caller
, src_idx
, &inter
,
4162 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);;
4163 /* Currently we do not produce clobber aggregate jump
4164 functions, adjust when we do. */
4165 gcc_checking_assert (!src_plats
->aggs
|| !jfunc
->agg
.items
);
4166 if (!inter
.exists ())
4167 inter
= copy_plats_to_inter (src_plats
, delta
);
4169 intersect_with_plats (src_plats
, &inter
, delta
);
4172 else if (jfunc
->agg
.items
)
4174 struct ipa_agg_jf_item
*item
;
4177 if (!inter
.exists ())
4178 for (unsigned i
= 0; i
< jfunc
->agg
.items
->length (); i
++)
4179 inter
.safe_push ((*jfunc
->agg
.items
)[i
]);
4181 FOR_EACH_VEC_ELT (inter
, k
, item
)
4184 bool found
= false;;
4189 while ((unsigned) l
< jfunc
->agg
.items
->length ())
4191 struct ipa_agg_jf_item
*ti
;
4192 ti
= &(*jfunc
->agg
.items
)[l
];
4193 if (ti
->offset
> item
->offset
)
4195 if (ti
->offset
== item
->offset
)
4197 gcc_checking_assert (ti
->value
);
4198 if (values_equal_for_ipcp_p (item
->value
,
4212 return vec
<ipa_agg_jf_item
>();
4217 /* Look at edges in CALLERS and collect all known aggregate values that arrive
4218 from all of them. */
4220 static struct ipa_agg_replacement_value
*
4221 find_aggregate_values_for_callers_subset (struct cgraph_node
*node
,
4222 vec
<cgraph_edge
*> callers
)
4224 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
4225 struct ipa_agg_replacement_value
*res
;
4226 struct ipa_agg_replacement_value
**tail
= &res
;
4227 struct cgraph_edge
*cs
;
4228 int i
, j
, count
= ipa_get_param_count (dest_info
);
4230 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4232 int c
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
4237 for (i
= 0; i
< count
; i
++)
4239 struct cgraph_edge
*cs
;
4240 vec
<ipa_agg_jf_item
> inter
= vNULL
;
4241 struct ipa_agg_jf_item
*item
;
4242 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (dest_info
, i
);
4245 /* Among other things, the following check should deal with all by_ref
4247 if (plats
->aggs_bottom
)
4250 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4252 inter
= intersect_aggregates_with_edge (cs
, i
, inter
);
4254 if (!inter
.exists ())
4258 FOR_EACH_VEC_ELT (inter
, j
, item
)
4260 struct ipa_agg_replacement_value
*v
;
4265 v
= ggc_alloc
<ipa_agg_replacement_value
> ();
4267 v
->offset
= item
->offset
;
4268 v
->value
= item
->value
;
4269 v
->by_ref
= plats
->aggs_by_ref
;
4275 if (inter
.exists ())
4282 /* Turn KNOWN_AGGS into a list of aggregate replacement values. */
4284 static struct ipa_agg_replacement_value
*
4285 known_aggs_to_agg_replacement_list (vec
<ipa_agg_jump_function
> known_aggs
)
4287 struct ipa_agg_replacement_value
*res
;
4288 struct ipa_agg_replacement_value
**tail
= &res
;
4289 struct ipa_agg_jump_function
*aggjf
;
4290 struct ipa_agg_jf_item
*item
;
4293 FOR_EACH_VEC_ELT (known_aggs
, i
, aggjf
)
4294 FOR_EACH_VEC_SAFE_ELT (aggjf
->items
, j
, item
)
4296 struct ipa_agg_replacement_value
*v
;
4297 v
= ggc_alloc
<ipa_agg_replacement_value
> ();
4299 v
->offset
= item
->offset
;
4300 v
->value
= item
->value
;
4301 v
->by_ref
= aggjf
->by_ref
;
4309 /* Determine whether CS also brings all scalar values that the NODE is
4313 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge
*cs
,
4314 struct cgraph_node
*node
)
4316 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
4317 int count
= ipa_get_param_count (dest_info
);
4318 struct ipa_node_params
*caller_info
;
4319 struct ipa_edge_args
*args
;
4322 caller_info
= IPA_NODE_REF (cs
->caller
);
4323 args
= IPA_EDGE_REF (cs
);
4324 for (i
= 0; i
< count
; i
++)
4326 struct ipa_jump_func
*jump_func
;
4329 val
= dest_info
->known_csts
[i
];
4333 if (i
>= ipa_get_cs_argument_count (args
))
4335 jump_func
= ipa_get_ith_jump_func (args
, i
);
4336 t
= ipa_value_from_jfunc (caller_info
, jump_func
);
4337 if (!t
|| !values_equal_for_ipcp_p (val
, t
))
4343 /* Determine whether CS also brings all aggregate values that NODE is
4346 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge
*cs
,
4347 struct cgraph_node
*node
)
4349 struct ipa_node_params
*orig_caller_info
= IPA_NODE_REF (cs
->caller
);
4350 struct ipa_node_params
*orig_node_info
;
4351 struct ipa_agg_replacement_value
*aggval
;
4354 aggval
= ipa_get_agg_replacements_for_node (node
);
4358 count
= ipa_get_param_count (IPA_NODE_REF (node
));
4359 ec
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
4361 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4362 if (aggval
->index
>= ec
)
4365 orig_node_info
= IPA_NODE_REF (IPA_NODE_REF (node
)->ipcp_orig_node
);
4366 if (orig_caller_info
->ipcp_orig_node
)
4367 orig_caller_info
= IPA_NODE_REF (orig_caller_info
->ipcp_orig_node
);
4369 for (i
= 0; i
< count
; i
++)
4371 static vec
<ipa_agg_jf_item
> values
= vec
<ipa_agg_jf_item
>();
4372 struct ipcp_param_lattices
*plats
;
4373 bool interesting
= false;
4374 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4375 if (aggval
->index
== i
)
4383 plats
= ipa_get_parm_lattices (orig_node_info
, aggval
->index
);
4384 if (plats
->aggs_bottom
)
4387 values
= intersect_aggregates_with_edge (cs
, i
, values
);
4388 if (!values
.exists ())
4391 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4392 if (aggval
->index
== i
)
4394 struct ipa_agg_jf_item
*item
;
4397 FOR_EACH_VEC_ELT (values
, j
, item
)
4399 && item
->offset
== av
->offset
4400 && values_equal_for_ipcp_p (item
->value
, av
->value
))
4415 /* Given an original NODE and a VAL for which we have already created a
4416 specialized clone, look whether there are incoming edges that still lead
4417 into the old node but now also bring the requested value and also conform to
4418 all other criteria such that they can be redirected the special node.
4419 This function can therefore redirect the final edge in a SCC. */
4421 template <typename valtype
>
4423 perhaps_add_new_callers (cgraph_node
*node
, ipcp_value
<valtype
> *val
)
4425 ipcp_value_source
<valtype
> *src
;
4426 gcov_type redirected_sum
= 0;
4428 for (src
= val
->sources
; src
; src
= src
->next
)
4430 struct cgraph_edge
*cs
= src
->cs
;
4433 if (cgraph_edge_brings_value_p (cs
, src
, node
)
4434 && cgraph_edge_brings_all_scalars_for_node (cs
, val
->spec_node
)
4435 && cgraph_edge_brings_all_agg_vals_for_node (cs
, val
->spec_node
))
4438 fprintf (dump_file
, " - adding an extra caller %s of %s\n",
4439 cs
->caller
->dump_name (),
4440 val
->spec_node
->dump_name ());
4442 cs
->redirect_callee_duplicating_thunks (val
->spec_node
);
4443 val
->spec_node
->expand_all_artificial_thunks ();
4444 redirected_sum
+= cs
->count
;
4446 cs
= get_next_cgraph_edge_clone (cs
);
4451 update_specialized_profile (val
->spec_node
, node
, redirected_sum
);
4454 /* Return true if KNOWN_CONTEXTS contain at least one useful context. */
4457 known_contexts_useful_p (vec
<ipa_polymorphic_call_context
> known_contexts
)
4459 ipa_polymorphic_call_context
*ctx
;
4462 FOR_EACH_VEC_ELT (known_contexts
, i
, ctx
)
4463 if (!ctx
->useless_p ())
4468 /* Return a copy of KNOWN_CSTS if it is not empty, otherwise return vNULL. */
4470 static vec
<ipa_polymorphic_call_context
>
4471 copy_useful_known_contexts (vec
<ipa_polymorphic_call_context
> known_contexts
)
4473 if (known_contexts_useful_p (known_contexts
))
4474 return known_contexts
.copy ();
4479 /* Copy KNOWN_CSTS and modify the copy according to VAL and INDEX. If
4480 non-empty, replace KNOWN_CONTEXTS with its copy too. */
4483 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
4484 vec
<ipa_polymorphic_call_context
> *known_contexts
,
4485 ipcp_value
<tree
> *val
,
4488 *known_csts
= known_csts
->copy ();
4489 *known_contexts
= copy_useful_known_contexts (*known_contexts
);
4490 (*known_csts
)[index
] = val
->value
;
4493 /* Replace KNOWN_CSTS with its copy. Also copy KNOWN_CONTEXTS and modify the
4494 copy according to VAL and INDEX. */
4497 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
4498 vec
<ipa_polymorphic_call_context
> *known_contexts
,
4499 ipcp_value
<ipa_polymorphic_call_context
> *val
,
4502 *known_csts
= known_csts
->copy ();
4503 *known_contexts
= known_contexts
->copy ();
4504 (*known_contexts
)[index
] = val
->value
;
4507 /* Return true if OFFSET indicates this was not an aggregate value or there is
4508 a replacement equivalent to VALUE, INDEX and OFFSET among those in the
4512 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*aggvals
,
4513 int index
, HOST_WIDE_INT offset
, tree value
)
4520 if (aggvals
->index
== index
4521 && aggvals
->offset
== offset
4522 && values_equal_for_ipcp_p (aggvals
->value
, value
))
4524 aggvals
= aggvals
->next
;
4529 /* Return true if offset is minus one because source of a polymorphic contect
4530 cannot be an aggregate value. */
4533 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*,
4534 int , HOST_WIDE_INT offset
,
4535 ipa_polymorphic_call_context
)
4537 return offset
== -1;
4540 /* Decide wheter to create a special version of NODE for value VAL of parameter
4541 at the given INDEX. If OFFSET is -1, the value is for the parameter itself,
4542 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS,
4543 KNOWN_CONTEXTS and KNOWN_AGGS describe the other already known values. */
4545 template <typename valtype
>
4547 decide_about_value (struct cgraph_node
*node
, int index
, HOST_WIDE_INT offset
,
4548 ipcp_value
<valtype
> *val
, vec
<tree
> known_csts
,
4549 vec
<ipa_polymorphic_call_context
> known_contexts
)
4551 struct ipa_agg_replacement_value
*aggvals
;
4552 int freq_sum
, caller_count
;
4553 gcov_type count_sum
;
4554 vec
<cgraph_edge
*> callers
;
4558 perhaps_add_new_callers (node
, val
);
4561 else if (val
->local_size_cost
+ overall_size
> max_new_size
)
4563 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4564 fprintf (dump_file
, " Ignoring candidate value because "
4565 "max_new_size would be reached with %li.\n",
4566 val
->local_size_cost
+ overall_size
);
4569 else if (!get_info_about_necessary_edges (val
, node
, &freq_sum
, &count_sum
,
4573 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4575 fprintf (dump_file
, " - considering value ");
4576 print_ipcp_constant_value (dump_file
, val
->value
);
4577 fprintf (dump_file
, " for ");
4578 ipa_dump_param (dump_file
, IPA_NODE_REF (node
), index
);
4580 fprintf (dump_file
, ", offset: " HOST_WIDE_INT_PRINT_DEC
, offset
);
4581 fprintf (dump_file
, " (caller_count: %i)\n", caller_count
);
4584 if (!good_cloning_opportunity_p (node
, val
->local_time_benefit
,
4585 freq_sum
, count_sum
,
4586 val
->local_size_cost
)
4587 && !good_cloning_opportunity_p (node
,
4588 val
->local_time_benefit
4589 + val
->prop_time_benefit
,
4590 freq_sum
, count_sum
,
4591 val
->local_size_cost
4592 + val
->prop_size_cost
))
4596 fprintf (dump_file
, " Creating a specialized node of %s.\n",
4597 node
->dump_name ());
4599 callers
= gather_edges_for_value (val
, node
, caller_count
);
4601 modify_known_vectors_with_val (&known_csts
, &known_contexts
, val
, index
);
4604 known_csts
= known_csts
.copy ();
4605 known_contexts
= copy_useful_known_contexts (known_contexts
);
4607 find_more_scalar_values_for_callers_subset (node
, known_csts
, callers
);
4608 find_more_contexts_for_caller_subset (node
, &known_contexts
, callers
);
4609 aggvals
= find_aggregate_values_for_callers_subset (node
, callers
);
4610 gcc_checking_assert (ipcp_val_agg_replacement_ok_p (aggvals
, index
,
4611 offset
, val
->value
));
4612 val
->spec_node
= create_specialized_node (node
, known_csts
, known_contexts
,
4614 overall_size
+= val
->local_size_cost
;
4616 /* TODO: If for some lattice there is only one other known value
4617 left, make a special node for it too. */
4622 /* Decide whether and what specialized clones of NODE should be created. */
4625 decide_whether_version_node (struct cgraph_node
*node
)
4627 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
4628 int i
, count
= ipa_get_param_count (info
);
4629 vec
<tree
> known_csts
;
4630 vec
<ipa_polymorphic_call_context
> known_contexts
;
4631 vec
<ipa_agg_jump_function
> known_aggs
= vNULL
;
4637 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4638 fprintf (dump_file
, "\nEvaluating opportunities for %s.\n",
4639 node
->dump_name ());
4641 gather_context_independent_values (info
, &known_csts
, &known_contexts
,
4642 info
->do_clone_for_all_contexts
? &known_aggs
4645 for (i
= 0; i
< count
;i
++)
4647 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4648 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
4649 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
4654 ipcp_value
<tree
> *val
;
4655 for (val
= lat
->values
; val
; val
= val
->next
)
4656 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
4660 if (!plats
->aggs_bottom
)
4662 struct ipcp_agg_lattice
*aglat
;
4663 ipcp_value
<tree
> *val
;
4664 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
4665 if (!aglat
->bottom
&& aglat
->values
4666 /* If the following is false, the one value is in
4668 && (plats
->aggs_contain_variable
4669 || !aglat
->is_single_const ()))
4670 for (val
= aglat
->values
; val
; val
= val
->next
)
4671 ret
|= decide_about_value (node
, i
, aglat
->offset
, val
,
4672 known_csts
, known_contexts
);
4676 && known_contexts
[i
].useless_p ())
4678 ipcp_value
<ipa_polymorphic_call_context
> *val
;
4679 for (val
= ctxlat
->values
; val
; val
= val
->next
)
4680 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
4684 info
= IPA_NODE_REF (node
);
4687 if (info
->do_clone_for_all_contexts
)
4689 struct cgraph_node
*clone
;
4690 vec
<cgraph_edge
*> callers
;
4693 fprintf (dump_file
, " - Creating a specialized node of %s "
4694 "for all known contexts.\n", node
->dump_name ());
4696 callers
= node
->collect_callers ();
4698 if (!known_contexts_useful_p (known_contexts
))
4700 known_contexts
.release ();
4701 known_contexts
= vNULL
;
4703 clone
= create_specialized_node (node
, known_csts
, known_contexts
,
4704 known_aggs_to_agg_replacement_list (known_aggs
),
4706 info
= IPA_NODE_REF (node
);
4707 info
->do_clone_for_all_contexts
= false;
4708 IPA_NODE_REF (clone
)->is_all_contexts_clone
= true;
4709 for (i
= 0; i
< count
; i
++)
4710 vec_free (known_aggs
[i
].items
);
4711 known_aggs
.release ();
4716 known_csts
.release ();
4717 known_contexts
.release ();
4723 /* Transitively mark all callees of NODE within the same SCC as not dead. */
4726 spread_undeadness (struct cgraph_node
*node
)
4728 struct cgraph_edge
*cs
;
4730 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
4731 if (ipa_edge_within_scc (cs
))
4733 struct cgraph_node
*callee
;
4734 struct ipa_node_params
*info
;
4736 callee
= cs
->callee
->function_symbol (NULL
);
4737 info
= IPA_NODE_REF (callee
);
4739 if (info
->node_dead
)
4741 info
->node_dead
= 0;
4742 spread_undeadness (callee
);
4747 /* Return true if NODE has a caller from outside of its SCC that is not
4748 dead. Worker callback for cgraph_for_node_and_aliases. */
4751 has_undead_caller_from_outside_scc_p (struct cgraph_node
*node
,
4752 void *data ATTRIBUTE_UNUSED
)
4754 struct cgraph_edge
*cs
;
4756 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
4757 if (cs
->caller
->thunk
.thunk_p
4758 && cs
->caller
->call_for_symbol_thunks_and_aliases
4759 (has_undead_caller_from_outside_scc_p
, NULL
, true))
4761 else if (!ipa_edge_within_scc (cs
)
4762 && !IPA_NODE_REF (cs
->caller
)->node_dead
)
4768 /* Identify nodes within the same SCC as NODE which are no longer needed
4769 because of new clones and will be removed as unreachable. */
4772 identify_dead_nodes (struct cgraph_node
*node
)
4774 struct cgraph_node
*v
;
4775 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4777 && !v
->call_for_symbol_thunks_and_aliases
4778 (has_undead_caller_from_outside_scc_p
, NULL
, true))
4779 IPA_NODE_REF (v
)->node_dead
= 1;
4781 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4782 if (!IPA_NODE_REF (v
)->node_dead
)
4783 spread_undeadness (v
);
4785 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4787 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4788 if (IPA_NODE_REF (v
)->node_dead
)
4789 fprintf (dump_file
, " Marking node as dead: %s.\n", v
->dump_name ());
4793 /* The decision stage. Iterate over the topological order of call graph nodes
4794 TOPO and make specialized clones if deemed beneficial. */
4797 ipcp_decision_stage (struct ipa_topo_info
*topo
)
4802 fprintf (dump_file
, "\nIPA decision stage:\n\n");
4804 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
4806 struct cgraph_node
*node
= topo
->order
[i
];
4807 bool change
= false, iterate
= true;
4811 struct cgraph_node
*v
;
4813 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4814 if (v
->has_gimple_body_p ()
4815 && ipcp_versionable_function_p (v
))
4816 iterate
|= decide_whether_version_node (v
);
4821 identify_dead_nodes (node
);
4825 /* Look up all the bits information that we have discovered and copy it over
4826 to the transformation summary. */
4829 ipcp_store_bits_results (void)
4833 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
4835 ipa_node_params
*info
= IPA_NODE_REF (node
);
4836 bool dumped_sth
= false;
4837 bool found_useful_result
= false;
4839 if (!opt_for_fn (node
->decl
, flag_ipa_bit_cp
))
4842 fprintf (dump_file
, "Not considering %s for ipa bitwise propagation "
4843 "; -fipa-bit-cp: disabled.\n",
4848 if (info
->ipcp_orig_node
)
4849 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
4851 unsigned count
= ipa_get_param_count (info
);
4852 for (unsigned i
= 0; i
< count
; i
++)
4854 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4855 if (plats
->bits_lattice
.constant_p ())
4857 found_useful_result
= true;
4862 if (!found_useful_result
)
4865 ipcp_grow_transformations_if_necessary ();
4866 ipcp_transformation_summary
*ts
= ipcp_get_transformation_summary (node
);
4867 vec_safe_reserve_exact (ts
->bits
, count
);
4869 for (unsigned i
= 0; i
< count
; i
++)
4871 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4874 if (plats
->bits_lattice
.constant_p ())
4876 = ipa_get_ipa_bits_for_value (plats
->bits_lattice
.get_value (),
4877 plats
->bits_lattice
.get_mask ());
4881 ts
->bits
->quick_push (jfbits
);
4882 if (!dump_file
|| !jfbits
)
4886 fprintf (dump_file
, "Propagated bits info for function %s:\n",
4887 node
->dump_name ());
4890 fprintf (dump_file
, " param %i: value = ", i
);
4891 print_hex (jfbits
->value
, dump_file
);
4892 fprintf (dump_file
, ", mask = ");
4893 print_hex (jfbits
->mask
, dump_file
);
4894 fprintf (dump_file
, "\n");
4899 /* Look up all VR information that we have discovered and copy it over
4900 to the transformation summary. */
4903 ipcp_store_vr_results (void)
4907 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
4909 ipa_node_params
*info
= IPA_NODE_REF (node
);
4910 bool found_useful_result
= false;
4912 if (!opt_for_fn (node
->decl
, flag_ipa_vrp
))
4915 fprintf (dump_file
, "Not considering %s for VR discovery "
4916 "and propagate; -fipa-ipa-vrp: disabled.\n",
4921 if (info
->ipcp_orig_node
)
4922 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
4924 unsigned count
= ipa_get_param_count (info
);
4925 for (unsigned i
= 0; i
< count
; i
++)
4927 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4928 if (!plats
->m_value_range
.bottom_p ()
4929 && !plats
->m_value_range
.top_p ())
4931 found_useful_result
= true;
4935 if (!found_useful_result
)
4938 ipcp_grow_transformations_if_necessary ();
4939 ipcp_transformation_summary
*ts
= ipcp_get_transformation_summary (node
);
4940 vec_safe_reserve_exact (ts
->m_vr
, count
);
4942 for (unsigned i
= 0; i
< count
; i
++)
4944 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4947 if (!plats
->m_value_range
.bottom_p ()
4948 && !plats
->m_value_range
.top_p ())
4951 vr
.type
= plats
->m_value_range
.m_vr
.type
;
4952 vr
.min
= plats
->m_value_range
.m_vr
.min
;
4953 vr
.max
= plats
->m_value_range
.m_vr
.max
;
4958 vr
.type
= VR_VARYING
;
4959 vr
.min
= vr
.max
= wi::zero (INT_TYPE_SIZE
);
4961 ts
->m_vr
->quick_push (vr
);
4966 /* The IPCP driver. */
4971 struct cgraph_2edge_hook_list
*edge_duplication_hook_holder
;
4972 struct cgraph_edge_hook_list
*edge_removal_hook_holder
;
4973 struct ipa_topo_info topo
;
4975 ipa_check_create_node_params ();
4976 ipa_check_create_edge_args ();
4977 grow_edge_clone_vectors ();
4978 edge_duplication_hook_holder
4979 = symtab
->add_edge_duplication_hook (&ipcp_edge_duplication_hook
, NULL
);
4980 edge_removal_hook_holder
4981 = symtab
->add_edge_removal_hook (&ipcp_edge_removal_hook
, NULL
);
4985 fprintf (dump_file
, "\nIPA structures before propagation:\n");
4986 if (dump_flags
& TDF_DETAILS
)
4987 ipa_print_all_params (dump_file
);
4988 ipa_print_all_jump_functions (dump_file
);
4991 /* Topological sort. */
4992 build_toporder_info (&topo
);
4993 /* Do the interprocedural propagation. */
4994 ipcp_propagate_stage (&topo
);
4995 /* Decide what constant propagation and cloning should be performed. */
4996 ipcp_decision_stage (&topo
);
4997 /* Store results of bits propagation. */
4998 ipcp_store_bits_results ();
4999 /* Store results of value range propagation. */
5000 ipcp_store_vr_results ();
5002 /* Free all IPCP structures. */
5003 free_toporder_info (&topo
);
5004 next_edge_clone
.release ();
5005 prev_edge_clone
.release ();
5006 symtab
->remove_edge_removal_hook (edge_removal_hook_holder
);
5007 symtab
->remove_edge_duplication_hook (edge_duplication_hook_holder
);
5008 ipa_free_all_structures_after_ipa_cp ();
5010 fprintf (dump_file
, "\nIPA constant propagation end\n");
5014 /* Initialization and computation of IPCP data structures. This is the initial
5015 intraprocedural analysis of functions, which gathers information to be
5016 propagated later on. */
5019 ipcp_generate_summary (void)
5021 struct cgraph_node
*node
;
5024 fprintf (dump_file
, "\nIPA constant propagation start:\n");
5025 ipa_register_cgraph_hooks ();
5027 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5028 ipa_analyze_node (node
);
5031 /* Write ipcp summary for nodes in SET. */
5034 ipcp_write_summary (void)
5036 ipa_prop_write_jump_functions ();
5039 /* Read ipcp summary. */
5042 ipcp_read_summary (void)
5044 ipa_prop_read_jump_functions ();
5049 const pass_data pass_data_ipa_cp
=
5051 IPA_PASS
, /* type */
5053 OPTGROUP_NONE
, /* optinfo_flags */
5054 TV_IPA_CONSTANT_PROP
, /* tv_id */
5055 0, /* properties_required */
5056 0, /* properties_provided */
5057 0, /* properties_destroyed */
5058 0, /* todo_flags_start */
5059 ( TODO_dump_symtab
| TODO_remove_functions
), /* todo_flags_finish */
5062 class pass_ipa_cp
: public ipa_opt_pass_d
5065 pass_ipa_cp (gcc::context
*ctxt
)
5066 : ipa_opt_pass_d (pass_data_ipa_cp
, ctxt
,
5067 ipcp_generate_summary
, /* generate_summary */
5068 ipcp_write_summary
, /* write_summary */
5069 ipcp_read_summary
, /* read_summary */
5070 ipcp_write_transformation_summaries
, /*
5071 write_optimization_summary */
5072 ipcp_read_transformation_summaries
, /*
5073 read_optimization_summary */
5074 NULL
, /* stmt_fixup */
5075 0, /* function_transform_todo_flags_start */
5076 ipcp_transform_function
, /* function_transform */
5077 NULL
) /* variable_transform */
5080 /* opt_pass methods: */
5081 virtual bool gate (function
*)
5083 /* FIXME: We should remove the optimize check after we ensure we never run
5084 IPA passes when not optimizing. */
5085 return (flag_ipa_cp
&& optimize
) || in_lto_p
;
5088 virtual unsigned int execute (function
*) { return ipcp_driver (); }
5090 }; // class pass_ipa_cp
5095 make_pass_ipa_cp (gcc::context
*ctxt
)
5097 return new pass_ipa_cp (ctxt
);
5100 /* Reset all state within ipa-cp.c so that we can rerun the compiler
5101 within the same process. For use by toplev::finalize. */
5104 ipa_cp_c_finalize (void)