1 /* Interprocedural constant propagation
2 Copyright (C) 2005-2014 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"
107 #include "gimple-fold.h"
108 #include "gimple-expr.h"
111 #include "basic-block.h"
113 #include "hash-map.h"
115 #include "plugin-api.h"
117 #include "hash-set.h"
118 #include "machmode.h"
120 #include "hard-reg-set.h"
122 #include "function.h"
125 #include "alloc-pool.h"
126 #include "ipa-prop.h"
128 #include "tree-pass.h"
130 #include "diagnostic.h"
131 #include "tree-pretty-print.h"
132 #include "tree-inline.h"
134 #include "ipa-inline.h"
135 #include "ipa-utils.h"
137 template <typename valtype
> class ipcp_value
;
139 /* Describes a particular source for an IPA-CP value. */
141 template <typename valtype
>
142 class ipcp_value_source
145 /* Aggregate offset of the source, negative if the source is scalar value of
146 the argument itself. */
147 HOST_WIDE_INT offset
;
148 /* The incoming edge that brought the value. */
150 /* If the jump function that resulted into his value was a pass-through or an
151 ancestor, this is the ipcp_value of the caller from which the described
152 value has been derived. Otherwise it is NULL. */
153 ipcp_value
<valtype
> *val
;
154 /* Next pointer in a linked list of sources of a value. */
155 ipcp_value_source
*next
;
156 /* If the jump function that resulted into his value was a pass-through or an
157 ancestor, this is the index of the parameter of the caller the jump
158 function references. */
162 /* Common ancestor for all ipcp_value instantiations. */
164 class ipcp_value_base
167 /* Time benefit and size cost that specializing the function for this value
168 would bring about in this function alone. */
169 int local_time_benefit
, local_size_cost
;
170 /* Time benefit and size cost that specializing the function for this value
171 can bring about in it's callees (transitively). */
172 int prop_time_benefit
, prop_size_cost
;
175 /* Describes one particular value stored in struct ipcp_lattice. */
177 template <typename valtype
>
178 class ipcp_value
: public ipcp_value_base
181 /* The actual value for the given parameter. */
183 /* The list of sources from which this value originates. */
184 ipcp_value_source
<valtype
> *sources
;
185 /* Next pointers in a linked list of all values in a lattice. */
187 /* Next pointers in a linked list of values in a strongly connected component
189 ipcp_value
*scc_next
;
190 /* Next pointers in a linked list of SCCs of values sorted topologically
191 according their sources. */
192 ipcp_value
*topo_next
;
193 /* A specialized node created for this value, NULL if none has been (so far)
195 cgraph_node
*spec_node
;
196 /* Depth first search number and low link for topological sorting of
199 /* True if this valye is currently on the topo-sort stack. */
202 void add_source (cgraph_edge
*cs
, ipcp_value
*src_val
, int src_idx
,
203 HOST_WIDE_INT offset
);
206 /* Lattice describing potential values of a formal parameter of a function, or
207 a part of an aggreagate. TOP is represented by a lattice with zero values
208 and with contains_variable and bottom flags cleared. BOTTOM is represented
209 by a lattice with the bottom flag set. In that case, values and
210 contains_variable flag should be disregarded. */
212 template <typename valtype
>
216 /* The list of known values and types in this lattice. Note that values are
217 not deallocated if a lattice is set to bottom because there may be value
218 sources referencing them. */
219 ipcp_value
<valtype
> *values
;
220 /* Number of known values and types in this lattice. */
222 /* The lattice contains a variable component (in addition to values). */
223 bool contains_variable
;
224 /* The value of the lattice is bottom (i.e. variable and unusable for any
228 inline bool is_single_const ();
229 inline bool set_to_bottom ();
230 inline bool set_contains_variable ();
231 bool add_value (valtype newval
, cgraph_edge
*cs
,
232 ipcp_value
<valtype
> *src_val
= NULL
,
233 int src_idx
= 0, HOST_WIDE_INT offset
= -1);
234 void print (FILE * f
, bool dump_sources
, bool dump_benefits
);
237 /* Lattice of tree values with an offset to describe a part of an
240 class ipcp_agg_lattice
: public ipcp_lattice
<tree
>
243 /* Offset that is being described by this lattice. */
244 HOST_WIDE_INT offset
;
245 /* Size so that we don't have to re-compute it every time we traverse the
246 list. Must correspond to TYPE_SIZE of all lat values. */
248 /* Next element of the linked list. */
249 struct ipcp_agg_lattice
*next
;
252 /* Structure containing lattices for a parameter itself and for pieces of
253 aggregates that are passed in the parameter or by a reference in a parameter
254 plus some other useful flags. */
256 class ipcp_param_lattices
259 /* Lattice describing the value of the parameter itself. */
260 ipcp_lattice
<tree
> itself
;
261 /* Lattice describing the the polymorphic contexts of a parameter. */
262 ipcp_lattice
<ipa_polymorphic_call_context
> ctxlat
;
263 /* Lattices describing aggregate parts. */
264 ipcp_agg_lattice
*aggs
;
265 /* Number of aggregate lattices */
267 /* True if aggregate data were passed by reference (as opposed to by
270 /* All aggregate lattices contain a variable component (in addition to
272 bool aggs_contain_variable
;
273 /* The value of all aggregate lattices is bottom (i.e. variable and unusable
274 for any propagation). */
277 /* There is a virtual call based on this parameter. */
281 /* Allocation pools for values and their sources in ipa-cp. */
283 alloc_pool ipcp_cst_values_pool
;
284 alloc_pool ipcp_poly_ctx_values_pool
;
285 alloc_pool ipcp_sources_pool
;
286 alloc_pool ipcp_agg_lattice_pool
;
288 /* Maximal count found in program. */
290 static gcov_type max_count
;
292 /* Original overall size of the program. */
294 static long overall_size
, max_new_size
;
296 /* Return the param lattices structure corresponding to the Ith formal
297 parameter of the function described by INFO. */
298 static inline struct ipcp_param_lattices
*
299 ipa_get_parm_lattices (struct ipa_node_params
*info
, int i
)
301 gcc_assert (i
>= 0 && i
< ipa_get_param_count (info
));
302 gcc_checking_assert (!info
->ipcp_orig_node
);
303 gcc_checking_assert (info
->lattices
);
304 return &(info
->lattices
[i
]);
307 /* Return the lattice corresponding to the scalar value of the Ith formal
308 parameter of the function described by INFO. */
309 static inline ipcp_lattice
<tree
> *
310 ipa_get_scalar_lat (struct ipa_node_params
*info
, int i
)
312 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
313 return &plats
->itself
;
316 /* Return the lattice corresponding to the scalar value of the Ith formal
317 parameter of the function described by INFO. */
318 static inline ipcp_lattice
<ipa_polymorphic_call_context
> *
319 ipa_get_poly_ctx_lat (struct ipa_node_params
*info
, int i
)
321 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
322 return &plats
->ctxlat
;
325 /* Return whether LAT is a lattice with a single constant and without an
328 template <typename valtype
>
330 ipcp_lattice
<valtype
>::is_single_const ()
332 if (bottom
|| contains_variable
|| values_count
!= 1)
338 /* Print V which is extracted from a value in a lattice to F. */
341 print_ipcp_constant_value (FILE * f
, tree v
)
343 if (TREE_CODE (v
) == ADDR_EXPR
344 && TREE_CODE (TREE_OPERAND (v
, 0)) == CONST_DECL
)
347 print_generic_expr (f
, DECL_INITIAL (TREE_OPERAND (v
, 0)), 0);
350 print_generic_expr (f
, v
, 0);
353 /* Print V which is extracted from a value in a lattice to F. */
356 print_ipcp_constant_value (FILE * f
, ipa_polymorphic_call_context v
)
361 /* Print a lattice LAT to F. */
363 template <typename valtype
>
365 ipcp_lattice
<valtype
>::print (FILE * f
, bool dump_sources
, bool dump_benefits
)
367 ipcp_value
<valtype
> *val
;
372 fprintf (f
, "BOTTOM\n");
376 if (!values_count
&& !contains_variable
)
378 fprintf (f
, "TOP\n");
382 if (contains_variable
)
384 fprintf (f
, "VARIABLE");
390 for (val
= values
; val
; val
= val
->next
)
392 if (dump_benefits
&& prev
)
394 else if (!dump_benefits
&& prev
)
399 print_ipcp_constant_value (f
, val
->value
);
403 ipcp_value_source
<valtype
> *s
;
405 fprintf (f
, " [from:");
406 for (s
= val
->sources
; s
; s
= s
->next
)
407 fprintf (f
, " %i(%i)", s
->cs
->caller
->order
,
413 fprintf (f
, " [loc_time: %i, loc_size: %i, "
414 "prop_time: %i, prop_size: %i]\n",
415 val
->local_time_benefit
, val
->local_size_cost
,
416 val
->prop_time_benefit
, val
->prop_size_cost
);
422 /* Print all ipcp_lattices of all functions to F. */
425 print_all_lattices (FILE * f
, bool dump_sources
, bool dump_benefits
)
427 struct cgraph_node
*node
;
430 fprintf (f
, "\nLattices:\n");
431 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
433 struct ipa_node_params
*info
;
435 info
= IPA_NODE_REF (node
);
436 fprintf (f
, " Node: %s/%i:\n", node
->name (),
438 count
= ipa_get_param_count (info
);
439 for (i
= 0; i
< count
; i
++)
441 struct ipcp_agg_lattice
*aglat
;
442 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
443 fprintf (f
, " param [%d]: ", i
);
444 plats
->itself
.print (f
, dump_sources
, dump_benefits
);
445 fprintf (f
, " ctxs: ");
446 plats
->ctxlat
.print (f
, dump_sources
, dump_benefits
);
447 if (plats
->virt_call
)
448 fprintf (f
, " virt_call flag set\n");
450 if (plats
->aggs_bottom
)
452 fprintf (f
, " AGGS BOTTOM\n");
455 if (plats
->aggs_contain_variable
)
456 fprintf (f
, " AGGS VARIABLE\n");
457 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
459 fprintf (f
, " %soffset " HOST_WIDE_INT_PRINT_DEC
": ",
460 plats
->aggs_by_ref
? "ref " : "", aglat
->offset
);
461 aglat
->print (f
, dump_sources
, dump_benefits
);
467 /* Determine whether it is at all technically possible to create clones of NODE
468 and store this information in the ipa_node_params structure associated
472 determine_versionability (struct cgraph_node
*node
)
474 const char *reason
= NULL
;
476 /* There are a number of generic reasons functions cannot be versioned. We
477 also cannot remove parameters if there are type attributes such as fnspec
479 if (node
->alias
|| node
->thunk
.thunk_p
)
480 reason
= "alias or thunk";
481 else if (!node
->local
.versionable
)
482 reason
= "not a tree_versionable_function";
483 else if (node
->get_availability () <= AVAIL_INTERPOSABLE
)
484 reason
= "insufficient body availability";
485 else if (!opt_for_fn (node
->decl
, optimize
)
486 || !opt_for_fn (node
->decl
, flag_ipa_cp
))
487 reason
= "non-optimized function";
488 else if (lookup_attribute ("omp declare simd", DECL_ATTRIBUTES (node
->decl
)))
490 /* Ideally we should clone the SIMD clones themselves and create
491 vector copies of them, so IPA-cp and SIMD clones can happily
492 coexist, but that may not be worth the effort. */
493 reason
= "function has SIMD clones";
495 /* Don't clone decls local to a comdat group; it breaks and for C++
496 decloned constructors, inlining is always better anyway. */
497 else if (node
->comdat_local_p ())
498 reason
= "comdat-local function";
500 if (reason
&& dump_file
&& !node
->alias
&& !node
->thunk
.thunk_p
)
501 fprintf (dump_file
, "Function %s/%i is not versionable, reason: %s.\n",
502 node
->name (), node
->order
, reason
);
504 node
->local
.versionable
= (reason
== NULL
);
507 /* Return true if it is at all technically possible to create clones of a
511 ipcp_versionable_function_p (struct cgraph_node
*node
)
513 return node
->local
.versionable
;
516 /* Structure holding accumulated information about callers of a node. */
518 struct caller_statistics
521 int n_calls
, n_hot_calls
, freq_sum
;
524 /* Initialize fields of STAT to zeroes. */
527 init_caller_stats (struct caller_statistics
*stats
)
529 stats
->count_sum
= 0;
531 stats
->n_hot_calls
= 0;
535 /* Worker callback of cgraph_for_node_and_aliases accumulating statistics of
536 non-thunk incoming edges to NODE. */
539 gather_caller_stats (struct cgraph_node
*node
, void *data
)
541 struct caller_statistics
*stats
= (struct caller_statistics
*) data
;
542 struct cgraph_edge
*cs
;
544 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
545 if (cs
->caller
->thunk
.thunk_p
)
546 cs
->caller
->call_for_symbol_thunks_and_aliases (gather_caller_stats
,
550 stats
->count_sum
+= cs
->count
;
551 stats
->freq_sum
+= cs
->frequency
;
553 if (cs
->maybe_hot_p ())
554 stats
->n_hot_calls
++;
560 /* Return true if this NODE is viable candidate for cloning. */
563 ipcp_cloning_candidate_p (struct cgraph_node
*node
)
565 struct caller_statistics stats
;
567 gcc_checking_assert (node
->has_gimple_body_p ());
569 if (!opt_for_fn (node
->decl
, flag_ipa_cp_clone
))
572 fprintf (dump_file
, "Not considering %s for cloning; "
573 "-fipa-cp-clone disabled.\n",
578 if (!optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node
->decl
)))
581 fprintf (dump_file
, "Not considering %s for cloning; "
582 "optimizing it for size.\n",
587 init_caller_stats (&stats
);
588 node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
, false);
590 if (inline_summary (node
)->self_size
< stats
.n_calls
)
593 fprintf (dump_file
, "Considering %s for cloning; code might shrink.\n",
598 /* When profile is available and function is hot, propagate into it even if
599 calls seems cold; constant propagation can improve function's speed
603 if (stats
.count_sum
> node
->count
* 90 / 100)
606 fprintf (dump_file
, "Considering %s for cloning; "
607 "usually called directly.\n",
612 if (!stats
.n_hot_calls
)
615 fprintf (dump_file
, "Not considering %s for cloning; no hot calls.\n",
620 fprintf (dump_file
, "Considering %s for cloning.\n",
625 template <typename valtype
>
626 class value_topo_info
629 /* Head of the linked list of topologically sorted values. */
630 ipcp_value
<valtype
> *values_topo
;
631 /* Stack for creating SCCs, represented by a linked list too. */
632 ipcp_value
<valtype
> *stack
;
633 /* Counter driving the algorithm in add_val_to_toposort. */
636 value_topo_info () : values_topo (NULL
), stack (NULL
), dfs_counter (0)
638 void add_val (ipcp_value
<valtype
> *cur_val
);
639 void propagate_effects ();
642 /* Arrays representing a topological ordering of call graph nodes and a stack
643 of nodes used during constant propagation and also data required to perform
644 topological sort of values and propagation of benefits in the determined
650 /* Array with obtained topological order of cgraph nodes. */
651 struct cgraph_node
**order
;
652 /* Stack of cgraph nodes used during propagation within SCC until all values
653 in the SCC stabilize. */
654 struct cgraph_node
**stack
;
655 int nnodes
, stack_top
;
657 value_topo_info
<tree
> constants
;
658 value_topo_info
<ipa_polymorphic_call_context
> contexts
;
660 ipa_topo_info () : order(NULL
), stack(NULL
), nnodes(0), stack_top(0),
665 /* Allocate the arrays in TOPO and topologically sort the nodes into order. */
668 build_toporder_info (struct ipa_topo_info
*topo
)
670 topo
->order
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
671 topo
->stack
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
673 gcc_checking_assert (topo
->stack_top
== 0);
674 topo
->nnodes
= ipa_reduced_postorder (topo
->order
, true, true, NULL
);
677 /* Free information about strongly connected components and the arrays in
681 free_toporder_info (struct ipa_topo_info
*topo
)
683 ipa_free_postorder_info ();
688 /* Add NODE to the stack in TOPO, unless it is already there. */
691 push_node_to_stack (struct ipa_topo_info
*topo
, struct cgraph_node
*node
)
693 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
694 if (info
->node_enqueued
)
696 info
->node_enqueued
= 1;
697 topo
->stack
[topo
->stack_top
++] = node
;
700 /* Pop a node from the stack in TOPO and return it or return NULL if the stack
703 static struct cgraph_node
*
704 pop_node_from_stack (struct ipa_topo_info
*topo
)
708 struct cgraph_node
*node
;
710 node
= topo
->stack
[topo
->stack_top
];
711 IPA_NODE_REF (node
)->node_enqueued
= 0;
718 /* Set lattice LAT to bottom and return true if it previously was not set as
721 template <typename valtype
>
723 ipcp_lattice
<valtype
>::set_to_bottom ()
730 /* Mark lattice as containing an unknown value and return true if it previously
731 was not marked as such. */
733 template <typename valtype
>
735 ipcp_lattice
<valtype
>::set_contains_variable ()
737 bool ret
= !contains_variable
;
738 contains_variable
= true;
742 /* Set all aggegate lattices in PLATS to bottom and return true if they were
743 not previously set as such. */
746 set_agg_lats_to_bottom (struct ipcp_param_lattices
*plats
)
748 bool ret
= !plats
->aggs_bottom
;
749 plats
->aggs_bottom
= true;
753 /* Mark all aggegate lattices in PLATS as containing an unknown value and
754 return true if they were not previously marked as such. */
757 set_agg_lats_contain_variable (struct ipcp_param_lattices
*plats
)
759 bool ret
= !plats
->aggs_contain_variable
;
760 plats
->aggs_contain_variable
= true;
764 /* Mark bot aggregate and scalar lattices as containing an unknown variable,
765 return true is any of them has not been marked as such so far. */
768 set_all_contains_variable (struct ipcp_param_lattices
*plats
)
771 ret
= plats
->itself
.set_contains_variable ();
772 ret
|= plats
->ctxlat
.set_contains_variable ();
773 ret
|= set_agg_lats_contain_variable (plats
);
777 /* Initialize ipcp_lattices. */
780 initialize_node_lattices (struct cgraph_node
*node
)
782 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
783 struct cgraph_edge
*ie
;
784 bool disable
= false, variable
= false;
787 gcc_checking_assert (node
->has_gimple_body_p ());
788 if (!cgraph_local_p (node
))
790 /* When cloning is allowed, we can assume that externally visible
791 functions are not called. We will compensate this by cloning
793 if (ipcp_versionable_function_p (node
)
794 && ipcp_cloning_candidate_p (node
))
800 if (disable
|| variable
)
802 for (i
= 0; i
< ipa_get_param_count (info
) ; i
++)
804 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
807 plats
->itself
.set_to_bottom ();
808 plats
->ctxlat
.set_to_bottom ();
809 set_agg_lats_to_bottom (plats
);
812 set_all_contains_variable (plats
);
814 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
815 && !node
->alias
&& !node
->thunk
.thunk_p
)
816 fprintf (dump_file
, "Marking all lattices of %s/%i as %s\n",
817 node
->name (), node
->order
,
818 disable
? "BOTTOM" : "VARIABLE");
821 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
822 if (ie
->indirect_info
->polymorphic
823 && ie
->indirect_info
->param_index
>= 0)
825 gcc_checking_assert (ie
->indirect_info
->param_index
>= 0);
826 ipa_get_parm_lattices (info
,
827 ie
->indirect_info
->param_index
)->virt_call
= 1;
831 /* Return the result of a (possibly arithmetic) pass through jump function
832 JFUNC on the constant value INPUT. Return NULL_TREE if that cannot be
833 determined or be considered an interprocedural invariant. */
836 ipa_get_jf_pass_through_result (struct ipa_jump_func
*jfunc
, tree input
)
840 gcc_checking_assert (is_gimple_ip_invariant (input
));
841 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
844 if (TREE_CODE_CLASS (ipa_get_jf_pass_through_operation (jfunc
))
846 restype
= boolean_type_node
;
848 restype
= TREE_TYPE (input
);
849 res
= fold_binary (ipa_get_jf_pass_through_operation (jfunc
), restype
,
850 input
, ipa_get_jf_pass_through_operand (jfunc
));
852 if (res
&& !is_gimple_ip_invariant (res
))
858 /* Return the result of an ancestor jump function JFUNC on the constant value
859 INPUT. Return NULL_TREE if that cannot be determined. */
862 ipa_get_jf_ancestor_result (struct ipa_jump_func
*jfunc
, tree input
)
864 gcc_checking_assert (TREE_CODE (input
) != TREE_BINFO
);
865 if (TREE_CODE (input
) == ADDR_EXPR
)
867 tree t
= TREE_OPERAND (input
, 0);
868 t
= build_ref_for_offset (EXPR_LOCATION (t
), t
,
869 ipa_get_jf_ancestor_offset (jfunc
),
870 ptr_type_node
, NULL
, false);
871 return build_fold_addr_expr (t
);
877 /* Determine whether JFUNC evaluates to a single known constant value and if
878 so, return it. Otherwise return NULL. INFO describes the caller node or
879 the one it is inlined to, so that pass-through jump functions can be
883 ipa_value_from_jfunc (struct ipa_node_params
*info
, struct ipa_jump_func
*jfunc
)
885 if (jfunc
->type
== IPA_JF_CONST
)
886 return ipa_get_jf_constant (jfunc
);
887 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
888 || jfunc
->type
== IPA_JF_ANCESTOR
)
893 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
894 idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
896 idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
898 if (info
->ipcp_orig_node
)
899 input
= info
->known_csts
[idx
];
902 ipcp_lattice
<tree
> *lat
;
906 lat
= ipa_get_scalar_lat (info
, idx
);
907 if (!lat
->is_single_const ())
909 input
= lat
->values
->value
;
915 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
916 return ipa_get_jf_pass_through_result (jfunc
, input
);
918 return ipa_get_jf_ancestor_result (jfunc
, input
);
924 /* Determie whether JFUNC evaluates to single known polymorphic context, given
925 that INFO describes the caller node or the one it is inlined to, CS is the
926 call graph edge corresponding to JFUNC and CSIDX index of the described
929 ipa_polymorphic_call_context
930 ipa_context_from_jfunc (ipa_node_params
*info
, cgraph_edge
*cs
, int csidx
,
931 ipa_jump_func
*jfunc
)
933 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
934 ipa_polymorphic_call_context ctx
;
935 ipa_polymorphic_call_context
*edge_ctx
936 = cs
? ipa_get_ith_polymorhic_call_context (args
, csidx
) : NULL
;
938 if (edge_ctx
&& !edge_ctx
->useless_p ())
941 if (jfunc
->type
== IPA_JF_PASS_THROUGH
942 || jfunc
->type
== IPA_JF_ANCESTOR
)
944 ipa_polymorphic_call_context srcctx
;
946 bool type_preserved
= true;
947 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
949 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
951 type_preserved
= ipa_get_jf_pass_through_type_preserved (jfunc
);
952 srcidx
= ipa_get_jf_pass_through_formal_id (jfunc
);
956 type_preserved
= ipa_get_jf_ancestor_type_preserved (jfunc
);
957 srcidx
= ipa_get_jf_ancestor_formal_id (jfunc
);
959 if (info
->ipcp_orig_node
)
961 if (info
->known_contexts
.exists ())
962 srcctx
= info
->known_contexts
[srcidx
];
968 ipcp_lattice
<ipa_polymorphic_call_context
> *lat
;
969 lat
= ipa_get_poly_ctx_lat (info
, srcidx
);
970 if (!lat
->is_single_const ())
972 srcctx
= lat
->values
->value
;
974 if (srcctx
.useless_p ())
976 if (jfunc
->type
== IPA_JF_ANCESTOR
)
977 srcctx
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
979 srcctx
.possible_dynamic_type_change (cs
->in_polymorphic_cdtor
);
980 srcctx
.combine_with (ctx
);
987 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
988 bottom, not containing a variable component and without any known value at
992 ipcp_verify_propagated_values (void)
994 struct cgraph_node
*node
;
996 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
998 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
999 int i
, count
= ipa_get_param_count (info
);
1001 for (i
= 0; i
< count
; i
++)
1003 ipcp_lattice
<tree
> *lat
= ipa_get_scalar_lat (info
, i
);
1006 && !lat
->contains_variable
1007 && lat
->values_count
== 0)
1011 symtab_node::dump_table (dump_file
);
1012 fprintf (dump_file
, "\nIPA lattices after constant "
1013 "propagation, before gcc_unreachable:\n");
1014 print_all_lattices (dump_file
, true, false);
1023 /* Return true iff X and Y should be considered equal values by IPA-CP. */
1026 values_equal_for_ipcp_p (tree x
, tree y
)
1028 gcc_checking_assert (x
!= NULL_TREE
&& y
!= NULL_TREE
);
1033 if (TREE_CODE (x
) == ADDR_EXPR
1034 && TREE_CODE (y
) == ADDR_EXPR
1035 && TREE_CODE (TREE_OPERAND (x
, 0)) == CONST_DECL
1036 && TREE_CODE (TREE_OPERAND (y
, 0)) == CONST_DECL
)
1037 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x
, 0)),
1038 DECL_INITIAL (TREE_OPERAND (y
, 0)), 0);
1040 return operand_equal_p (x
, y
, 0);
1043 /* Return true iff X and Y should be considered equal contexts by IPA-CP. */
1046 values_equal_for_ipcp_p (ipa_polymorphic_call_context x
,
1047 ipa_polymorphic_call_context y
)
1049 return x
.equal_to (y
);
1053 /* Add a new value source to the value represented by THIS, marking that a
1054 value comes from edge CS and (if the underlying jump function is a
1055 pass-through or an ancestor one) from a caller value SRC_VAL of a caller
1056 parameter described by SRC_INDEX. OFFSET is negative if the source was the
1057 scalar value of the parameter itself or the offset within an aggregate. */
1059 template <typename valtype
>
1061 ipcp_value
<valtype
>::add_source (cgraph_edge
*cs
, ipcp_value
*src_val
,
1062 int src_idx
, HOST_WIDE_INT offset
)
1064 ipcp_value_source
<valtype
> *src
;
1066 src
= new (pool_alloc (ipcp_sources_pool
)) ipcp_value_source
<valtype
>;
1067 src
->offset
= offset
;
1070 src
->index
= src_idx
;
1072 src
->next
= sources
;
1076 /* Allocate a new ipcp_value holding a tree constant, initialize its value to
1077 SOURCE and clear all other fields. */
1079 static ipcp_value
<tree
> *
1080 allocate_and_init_ipcp_value (tree source
)
1082 ipcp_value
<tree
> *val
;
1084 val
= new (pool_alloc (ipcp_cst_values_pool
)) ipcp_value
<tree
>;
1085 memset (val
, 0, sizeof (*val
));
1086 val
->value
= source
;
1090 /* Allocate a new ipcp_value holding a polymorphic context, initialize its
1091 value to SOURCE and clear all other fields. */
1093 static ipcp_value
<ipa_polymorphic_call_context
> *
1094 allocate_and_init_ipcp_value (ipa_polymorphic_call_context source
)
1096 ipcp_value
<ipa_polymorphic_call_context
> *val
;
1098 val
= new (pool_alloc (ipcp_poly_ctx_values_pool
))
1099 ipcp_value
<ipa_polymorphic_call_context
>;
1100 memset (val
, 0, sizeof (*val
));
1101 val
->value
= source
;
1105 /* Try to add NEWVAL to LAT, potentially creating a new ipcp_value for it. CS,
1106 SRC_VAL SRC_INDEX and OFFSET are meant for add_source and have the same
1107 meaning. OFFSET -1 means the source is scalar and not a part of an
1110 template <typename valtype
>
1112 ipcp_lattice
<valtype
>::add_value (valtype newval
, cgraph_edge
*cs
,
1113 ipcp_value
<valtype
> *src_val
,
1114 int src_idx
, HOST_WIDE_INT offset
)
1116 ipcp_value
<valtype
> *val
;
1121 for (val
= values
; val
; val
= val
->next
)
1122 if (values_equal_for_ipcp_p (val
->value
, newval
))
1124 if (ipa_edge_within_scc (cs
))
1126 ipcp_value_source
<valtype
> *s
;
1127 for (s
= val
->sources
; s
; s
= s
->next
)
1134 val
->add_source (cs
, src_val
, src_idx
, offset
);
1138 if (values_count
== PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE
))
1140 /* We can only free sources, not the values themselves, because sources
1141 of other values in this this SCC might point to them. */
1142 for (val
= values
; val
; val
= val
->next
)
1144 while (val
->sources
)
1146 ipcp_value_source
<valtype
> *src
= val
->sources
;
1147 val
->sources
= src
->next
;
1148 pool_free (ipcp_sources_pool
, src
);
1153 return set_to_bottom ();
1157 val
= allocate_and_init_ipcp_value (newval
);
1158 val
->add_source (cs
, src_val
, src_idx
, offset
);
1164 /* Propagate values through a pass-through jump function JFUNC associated with
1165 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1166 is the index of the source parameter. */
1169 propagate_vals_accross_pass_through (cgraph_edge
*cs
,
1170 ipa_jump_func
*jfunc
,
1171 ipcp_lattice
<tree
> *src_lat
,
1172 ipcp_lattice
<tree
> *dest_lat
,
1175 ipcp_value
<tree
> *src_val
;
1178 /* Do not create new values when propagating within an SCC because if there
1179 are arithmetic functions with circular dependencies, there is infinite
1180 number of them and we would just make lattices bottom. */
1181 if ((ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1182 && ipa_edge_within_scc (cs
))
1183 ret
= dest_lat
->set_contains_variable ();
1185 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1187 tree cstval
= ipa_get_jf_pass_through_result (jfunc
, src_val
->value
);
1190 ret
|= dest_lat
->add_value (cstval
, cs
, src_val
, src_idx
);
1192 ret
|= dest_lat
->set_contains_variable ();
1198 /* Propagate values through an ancestor jump function JFUNC associated with
1199 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1200 is the index of the source parameter. */
1203 propagate_vals_accross_ancestor (struct cgraph_edge
*cs
,
1204 struct ipa_jump_func
*jfunc
,
1205 ipcp_lattice
<tree
> *src_lat
,
1206 ipcp_lattice
<tree
> *dest_lat
,
1209 ipcp_value
<tree
> *src_val
;
1212 if (ipa_edge_within_scc (cs
))
1213 return dest_lat
->set_contains_variable ();
1215 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1217 tree t
= ipa_get_jf_ancestor_result (jfunc
, src_val
->value
);
1220 ret
|= dest_lat
->add_value (t
, cs
, src_val
, src_idx
);
1222 ret
|= dest_lat
->set_contains_variable ();
1228 /* Propagate scalar values across jump function JFUNC that is associated with
1229 edge CS and put the values into DEST_LAT. */
1232 propagate_scalar_accross_jump_function (struct cgraph_edge
*cs
,
1233 struct ipa_jump_func
*jfunc
,
1234 ipcp_lattice
<tree
> *dest_lat
)
1236 if (dest_lat
->bottom
)
1239 if (jfunc
->type
== IPA_JF_CONST
)
1241 tree val
= ipa_get_jf_constant (jfunc
);
1242 return dest_lat
->add_value (val
, cs
, NULL
, 0);
1244 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1245 || jfunc
->type
== IPA_JF_ANCESTOR
)
1247 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1248 ipcp_lattice
<tree
> *src_lat
;
1252 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1253 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1255 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1257 src_lat
= ipa_get_scalar_lat (caller_info
, src_idx
);
1258 if (src_lat
->bottom
)
1259 return dest_lat
->set_contains_variable ();
1261 /* If we would need to clone the caller and cannot, do not propagate. */
1262 if (!ipcp_versionable_function_p (cs
->caller
)
1263 && (src_lat
->contains_variable
1264 || (src_lat
->values_count
> 1)))
1265 return dest_lat
->set_contains_variable ();
1267 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1268 ret
= propagate_vals_accross_pass_through (cs
, jfunc
, src_lat
,
1271 ret
= propagate_vals_accross_ancestor (cs
, jfunc
, src_lat
, dest_lat
,
1274 if (src_lat
->contains_variable
)
1275 ret
|= dest_lat
->set_contains_variable ();
1280 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1281 use it for indirect inlining), we should propagate them too. */
1282 return dest_lat
->set_contains_variable ();
1285 /* Propagate scalar values across jump function JFUNC that is associated with
1286 edge CS and describes argument IDX and put the values into DEST_LAT. */
1289 propagate_context_accross_jump_function (cgraph_edge
*cs
,
1290 ipa_jump_func
*jfunc
, int idx
,
1291 ipcp_lattice
<ipa_polymorphic_call_context
> *dest_lat
)
1293 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
1294 if (dest_lat
->bottom
)
1297 bool added_sth
= false;
1298 bool type_preserved
= true;
1300 ipa_polymorphic_call_context edge_ctx
, *edge_ctx_ptr
1301 = ipa_get_ith_polymorhic_call_context (args
, idx
);
1304 edge_ctx
= *edge_ctx_ptr
;
1306 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1307 || jfunc
->type
== IPA_JF_ANCESTOR
)
1309 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1311 ipcp_lattice
<ipa_polymorphic_call_context
> *src_lat
;
1313 /* TODO: Once we figure out how to propagate speculations, it will
1314 probably be a good idea to switch to speculation if type_preserved is
1315 not set instead of punting. */
1316 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1318 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1320 type_preserved
= ipa_get_jf_pass_through_type_preserved (jfunc
);
1321 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1325 type_preserved
= ipa_get_jf_ancestor_type_preserved (jfunc
);
1326 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1329 src_lat
= ipa_get_poly_ctx_lat (caller_info
, src_idx
);
1330 /* If we would need to clone the caller and cannot, do not propagate. */
1331 if (!ipcp_versionable_function_p (cs
->caller
)
1332 && (src_lat
->contains_variable
1333 || (src_lat
->values_count
> 1)))
1336 ipcp_value
<ipa_polymorphic_call_context
> *src_val
;
1337 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1339 ipa_polymorphic_call_context cur
= src_val
->value
;
1341 if (!type_preserved
)
1342 cur
.possible_dynamic_type_change (cs
->in_polymorphic_cdtor
);
1343 if (jfunc
->type
== IPA_JF_ANCESTOR
)
1344 cur
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
1345 /* TODO: In cases we know how the context is going to be used,
1346 we can improve the result by passing proper OTR_TYPE. */
1347 cur
.combine_with (edge_ctx
);
1348 if (!cur
.useless_p ())
1350 if (src_lat
->contains_variable
1351 && !edge_ctx
.equal_to (cur
))
1352 ret
|= dest_lat
->set_contains_variable ();
1353 ret
|= dest_lat
->add_value (cur
, cs
, src_val
, src_idx
);
1363 if (!edge_ctx
.useless_p ())
1364 ret
|= dest_lat
->add_value (edge_ctx
, cs
);
1366 ret
|= dest_lat
->set_contains_variable ();
1372 /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
1373 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
1374 other cases, return false). If there are no aggregate items, set
1375 aggs_by_ref to NEW_AGGS_BY_REF. */
1378 set_check_aggs_by_ref (struct ipcp_param_lattices
*dest_plats
,
1379 bool new_aggs_by_ref
)
1381 if (dest_plats
->aggs
)
1383 if (dest_plats
->aggs_by_ref
!= new_aggs_by_ref
)
1385 set_agg_lats_to_bottom (dest_plats
);
1390 dest_plats
->aggs_by_ref
= new_aggs_by_ref
;
1394 /* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
1395 already existing lattice for the given OFFSET and SIZE, marking all skipped
1396 lattices as containing variable and checking for overlaps. If there is no
1397 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
1398 it with offset, size and contains_variable to PRE_EXISTING, and return true,
1399 unless there are too many already. If there are two many, return false. If
1400 there are overlaps turn whole DEST_PLATS to bottom and return false. If any
1401 skipped lattices were newly marked as containing variable, set *CHANGE to
1405 merge_agg_lats_step (struct ipcp_param_lattices
*dest_plats
,
1406 HOST_WIDE_INT offset
, HOST_WIDE_INT val_size
,
1407 struct ipcp_agg_lattice
***aglat
,
1408 bool pre_existing
, bool *change
)
1410 gcc_checking_assert (offset
>= 0);
1412 while (**aglat
&& (**aglat
)->offset
< offset
)
1414 if ((**aglat
)->offset
+ (**aglat
)->size
> offset
)
1416 set_agg_lats_to_bottom (dest_plats
);
1419 *change
|= (**aglat
)->set_contains_variable ();
1420 *aglat
= &(**aglat
)->next
;
1423 if (**aglat
&& (**aglat
)->offset
== offset
)
1425 if ((**aglat
)->size
!= val_size
1427 && (**aglat
)->next
->offset
< offset
+ val_size
))
1429 set_agg_lats_to_bottom (dest_plats
);
1432 gcc_checking_assert (!(**aglat
)->next
1433 || (**aglat
)->next
->offset
>= offset
+ val_size
);
1438 struct ipcp_agg_lattice
*new_al
;
1440 if (**aglat
&& (**aglat
)->offset
< offset
+ val_size
)
1442 set_agg_lats_to_bottom (dest_plats
);
1445 if (dest_plats
->aggs_count
== PARAM_VALUE (PARAM_IPA_MAX_AGG_ITEMS
))
1447 dest_plats
->aggs_count
++;
1448 new_al
= (struct ipcp_agg_lattice
*) pool_alloc (ipcp_agg_lattice_pool
);
1449 memset (new_al
, 0, sizeof (*new_al
));
1451 new_al
->offset
= offset
;
1452 new_al
->size
= val_size
;
1453 new_al
->contains_variable
= pre_existing
;
1455 new_al
->next
= **aglat
;
1461 /* Set all AGLAT and all other aggregate lattices reachable by next pointers as
1462 containing an unknown value. */
1465 set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice
*aglat
)
1470 ret
|= aglat
->set_contains_variable ();
1471 aglat
= aglat
->next
;
1476 /* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
1477 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source
1478 parameter used for lattice value sources. Return true if DEST_PLATS changed
1482 merge_aggregate_lattices (struct cgraph_edge
*cs
,
1483 struct ipcp_param_lattices
*dest_plats
,
1484 struct ipcp_param_lattices
*src_plats
,
1485 int src_idx
, HOST_WIDE_INT offset_delta
)
1487 bool pre_existing
= dest_plats
->aggs
!= NULL
;
1488 struct ipcp_agg_lattice
**dst_aglat
;
1491 if (set_check_aggs_by_ref (dest_plats
, src_plats
->aggs_by_ref
))
1493 if (src_plats
->aggs_bottom
)
1494 return set_agg_lats_contain_variable (dest_plats
);
1495 if (src_plats
->aggs_contain_variable
)
1496 ret
|= set_agg_lats_contain_variable (dest_plats
);
1497 dst_aglat
= &dest_plats
->aggs
;
1499 for (struct ipcp_agg_lattice
*src_aglat
= src_plats
->aggs
;
1501 src_aglat
= src_aglat
->next
)
1503 HOST_WIDE_INT new_offset
= src_aglat
->offset
- offset_delta
;
1507 if (merge_agg_lats_step (dest_plats
, new_offset
, src_aglat
->size
,
1508 &dst_aglat
, pre_existing
, &ret
))
1510 struct ipcp_agg_lattice
*new_al
= *dst_aglat
;
1512 dst_aglat
= &(*dst_aglat
)->next
;
1513 if (src_aglat
->bottom
)
1515 ret
|= new_al
->set_contains_variable ();
1518 if (src_aglat
->contains_variable
)
1519 ret
|= new_al
->set_contains_variable ();
1520 for (ipcp_value
<tree
> *val
= src_aglat
->values
;
1523 ret
|= new_al
->add_value (val
->value
, cs
, val
, src_idx
,
1526 else if (dest_plats
->aggs_bottom
)
1529 ret
|= set_chain_of_aglats_contains_variable (*dst_aglat
);
1533 /* Determine whether there is anything to propagate FROM SRC_PLATS through a
1534 pass-through JFUNC and if so, whether it has conform and conforms to the
1535 rules about propagating values passed by reference. */
1538 agg_pass_through_permissible_p (struct ipcp_param_lattices
*src_plats
,
1539 struct ipa_jump_func
*jfunc
)
1541 return src_plats
->aggs
1542 && (!src_plats
->aggs_by_ref
1543 || ipa_get_jf_pass_through_agg_preserved (jfunc
));
1546 /* Propagate scalar values across jump function JFUNC that is associated with
1547 edge CS and put the values into DEST_LAT. */
1550 propagate_aggs_accross_jump_function (struct cgraph_edge
*cs
,
1551 struct ipa_jump_func
*jfunc
,
1552 struct ipcp_param_lattices
*dest_plats
)
1556 if (dest_plats
->aggs_bottom
)
1559 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1560 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
1562 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1563 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1564 struct ipcp_param_lattices
*src_plats
;
1566 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
1567 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
1569 /* Currently we do not produce clobber aggregate jump
1570 functions, replace with merging when we do. */
1571 gcc_assert (!jfunc
->agg
.items
);
1572 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
,
1576 ret
|= set_agg_lats_contain_variable (dest_plats
);
1578 else if (jfunc
->type
== IPA_JF_ANCESTOR
1579 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
1581 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1582 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1583 struct ipcp_param_lattices
*src_plats
;
1585 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
1586 if (src_plats
->aggs
&& src_plats
->aggs_by_ref
)
1588 /* Currently we do not produce clobber aggregate jump
1589 functions, replace with merging when we do. */
1590 gcc_assert (!jfunc
->agg
.items
);
1591 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
, src_idx
,
1592 ipa_get_jf_ancestor_offset (jfunc
));
1594 else if (!src_plats
->aggs_by_ref
)
1595 ret
|= set_agg_lats_to_bottom (dest_plats
);
1597 ret
|= set_agg_lats_contain_variable (dest_plats
);
1599 else if (jfunc
->agg
.items
)
1601 bool pre_existing
= dest_plats
->aggs
!= NULL
;
1602 struct ipcp_agg_lattice
**aglat
= &dest_plats
->aggs
;
1603 struct ipa_agg_jf_item
*item
;
1606 if (set_check_aggs_by_ref (dest_plats
, jfunc
->agg
.by_ref
))
1609 FOR_EACH_VEC_ELT (*jfunc
->agg
.items
, i
, item
)
1611 HOST_WIDE_INT val_size
;
1613 if (item
->offset
< 0)
1615 gcc_checking_assert (is_gimple_ip_invariant (item
->value
));
1616 val_size
= tree_to_uhwi (TYPE_SIZE (TREE_TYPE (item
->value
)));
1618 if (merge_agg_lats_step (dest_plats
, item
->offset
, val_size
,
1619 &aglat
, pre_existing
, &ret
))
1621 ret
|= (*aglat
)->add_value (item
->value
, cs
, NULL
, 0, 0);
1622 aglat
= &(*aglat
)->next
;
1624 else if (dest_plats
->aggs_bottom
)
1628 ret
|= set_chain_of_aglats_contains_variable (*aglat
);
1631 ret
|= set_agg_lats_contain_variable (dest_plats
);
1636 /* Propagate constants from the caller to the callee of CS. INFO describes the
1640 propagate_constants_accross_call (struct cgraph_edge
*cs
)
1642 struct ipa_node_params
*callee_info
;
1643 enum availability availability
;
1644 struct cgraph_node
*callee
, *alias_or_thunk
;
1645 struct ipa_edge_args
*args
;
1647 int i
, args_count
, parms_count
;
1649 callee
= cs
->callee
->function_symbol (&availability
);
1650 if (!callee
->definition
)
1652 gcc_checking_assert (callee
->has_gimple_body_p ());
1653 callee_info
= IPA_NODE_REF (callee
);
1655 args
= IPA_EDGE_REF (cs
);
1656 args_count
= ipa_get_cs_argument_count (args
);
1657 parms_count
= ipa_get_param_count (callee_info
);
1658 if (parms_count
== 0)
1661 /* No propagation through instrumentation thunks is available yet.
1662 It should be possible with proper mapping of call args and
1663 instrumented callee params in the propagation loop below. But
1664 this case mostly occurs when legacy code calls instrumented code
1665 and it is not a primary target for optimizations.
1666 We detect instrumentation thunks in aliases and thunks chain by
1667 checking instrumentation_clone flag for chain source and target.
1668 Going through instrumentation thunks we always have it changed
1669 from 0 to 1 and all other nodes do not change it. */
1670 if (!cs
->callee
->instrumentation_clone
1671 && callee
->instrumentation_clone
)
1673 for (i
= 0; i
< parms_count
; i
++)
1674 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
1679 /* If this call goes through a thunk we must not propagate to the first (0th)
1680 parameter. However, we might need to uncover a thunk from below a series
1681 of aliases first. */
1682 alias_or_thunk
= cs
->callee
;
1683 while (alias_or_thunk
->alias
)
1684 alias_or_thunk
= alias_or_thunk
->get_alias_target ();
1685 if (alias_or_thunk
->thunk
.thunk_p
)
1687 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
1694 for (; (i
< args_count
) && (i
< parms_count
); i
++)
1696 struct ipa_jump_func
*jump_func
= ipa_get_ith_jump_func (args
, i
);
1697 struct ipcp_param_lattices
*dest_plats
;
1699 dest_plats
= ipa_get_parm_lattices (callee_info
, i
);
1700 if (availability
== AVAIL_INTERPOSABLE
)
1701 ret
|= set_all_contains_variable (dest_plats
);
1704 ret
|= propagate_scalar_accross_jump_function (cs
, jump_func
,
1705 &dest_plats
->itself
);
1706 ret
|= propagate_context_accross_jump_function (cs
, jump_func
, i
,
1707 &dest_plats
->ctxlat
);
1708 ret
|= propagate_aggs_accross_jump_function (cs
, jump_func
,
1712 for (; i
< parms_count
; i
++)
1713 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
, i
));
1718 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
1719 KNOWN_CONTEXTS, KNOWN_AGGS or AGG_REPS return the destination. The latter
1720 three can be NULL. If AGG_REPS is not NULL, KNOWN_AGGS is ignored. */
1723 ipa_get_indirect_edge_target_1 (struct cgraph_edge
*ie
,
1724 vec
<tree
> known_csts
,
1725 vec
<ipa_polymorphic_call_context
> known_contexts
,
1726 vec
<ipa_agg_jump_function_p
> known_aggs
,
1727 struct ipa_agg_replacement_value
*agg_reps
,
1730 int param_index
= ie
->indirect_info
->param_index
;
1731 HOST_WIDE_INT anc_offset
;
1735 *speculative
= false;
1737 if (param_index
== -1
1738 || known_csts
.length () <= (unsigned int) param_index
)
1741 if (!ie
->indirect_info
->polymorphic
)
1745 if (ie
->indirect_info
->agg_contents
)
1752 if (agg_reps
->index
== param_index
1753 && agg_reps
->offset
== ie
->indirect_info
->offset
1754 && agg_reps
->by_ref
== ie
->indirect_info
->by_ref
)
1756 t
= agg_reps
->value
;
1759 agg_reps
= agg_reps
->next
;
1762 else if (known_aggs
.length () > (unsigned int) param_index
)
1764 struct ipa_agg_jump_function
*agg
;
1765 agg
= known_aggs
[param_index
];
1766 t
= ipa_find_agg_cst_for_param (agg
, ie
->indirect_info
->offset
,
1767 ie
->indirect_info
->by_ref
);
1773 t
= known_csts
[param_index
];
1776 TREE_CODE (t
) == ADDR_EXPR
1777 && TREE_CODE (TREE_OPERAND (t
, 0)) == FUNCTION_DECL
)
1778 return TREE_OPERAND (t
, 0);
1783 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize
))
1786 gcc_assert (!ie
->indirect_info
->agg_contents
);
1787 anc_offset
= ie
->indirect_info
->offset
;
1791 /* Try to work out value of virtual table pointer value in replacemnets. */
1792 if (!t
&& agg_reps
&& !ie
->indirect_info
->by_ref
)
1796 if (agg_reps
->index
== param_index
1797 && agg_reps
->offset
== ie
->indirect_info
->offset
1798 && agg_reps
->by_ref
)
1800 t
= agg_reps
->value
;
1803 agg_reps
= agg_reps
->next
;
1807 /* Try to work out value of virtual table pointer value in known
1808 aggregate values. */
1809 if (!t
&& known_aggs
.length () > (unsigned int) param_index
1810 && !ie
->indirect_info
->by_ref
)
1812 struct ipa_agg_jump_function
*agg
;
1813 agg
= known_aggs
[param_index
];
1814 t
= ipa_find_agg_cst_for_param (agg
, ie
->indirect_info
->offset
,
1818 /* If we found the virtual table pointer, lookup the target. */
1822 unsigned HOST_WIDE_INT offset
;
1823 if (vtable_pointer_value_to_vtable (t
, &vtable
, &offset
))
1825 target
= gimple_get_virt_method_for_vtable (ie
->indirect_info
->otr_token
,
1829 if ((TREE_CODE (TREE_TYPE (target
)) == FUNCTION_TYPE
1830 && DECL_FUNCTION_CODE (target
) == BUILT_IN_UNREACHABLE
)
1831 || !possible_polymorphic_call_target_p
1832 (ie
, cgraph_node::get (target
)))
1833 target
= ipa_impossible_devirt_target (ie
, target
);
1834 *speculative
= ie
->indirect_info
->vptr_changed
;
1841 /* Do we know the constant value of pointer? */
1843 t
= known_csts
[param_index
];
1845 gcc_checking_assert (!t
|| TREE_CODE (t
) != TREE_BINFO
);
1847 ipa_polymorphic_call_context context
;
1848 if (known_contexts
.length () > (unsigned int) param_index
)
1850 context
= known_contexts
[param_index
];
1851 context
.offset_by (anc_offset
);
1852 if (ie
->indirect_info
->vptr_changed
)
1853 context
.possible_dynamic_type_change (ie
->in_polymorphic_cdtor
,
1854 ie
->indirect_info
->otr_type
);
1857 ipa_polymorphic_call_context ctx2
= ipa_polymorphic_call_context
1858 (t
, ie
->indirect_info
->otr_type
, anc_offset
);
1859 if (!ctx2
.useless_p ())
1860 context
.combine_with (ctx2
, ie
->indirect_info
->otr_type
);
1864 context
= ipa_polymorphic_call_context (t
, ie
->indirect_info
->otr_type
,
1869 vec
<cgraph_node
*>targets
;
1872 targets
= possible_polymorphic_call_targets
1873 (ie
->indirect_info
->otr_type
,
1874 ie
->indirect_info
->otr_token
,
1876 if (!final
|| targets
.length () > 1)
1878 struct cgraph_node
*node
;
1881 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize_speculatively
)
1882 || ie
->speculative
|| !ie
->maybe_hot_p ())
1884 node
= try_speculative_devirtualization (ie
->indirect_info
->otr_type
,
1885 ie
->indirect_info
->otr_token
,
1889 *speculative
= true;
1890 target
= node
->decl
;
1897 *speculative
= false;
1898 if (targets
.length () == 1)
1899 target
= targets
[0]->decl
;
1901 target
= ipa_impossible_devirt_target (ie
, NULL_TREE
);
1904 if (target
&& !possible_polymorphic_call_target_p (ie
,
1905 cgraph_node::get (target
)))
1906 target
= ipa_impossible_devirt_target (ie
, target
);
1912 /* If an indirect edge IE can be turned into a direct one based on KNOWN_CSTS,
1913 KNOWN_CONTEXTS (which can be vNULL) or KNOWN_AGGS (which also can be vNULL)
1914 return the destination. */
1917 ipa_get_indirect_edge_target (struct cgraph_edge
*ie
,
1918 vec
<tree
> known_csts
,
1919 vec
<ipa_polymorphic_call_context
> known_contexts
,
1920 vec
<ipa_agg_jump_function_p
> known_aggs
,
1923 return ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
1924 known_aggs
, NULL
, speculative
);
1927 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
1928 and KNOWN_CONTEXTS. */
1931 devirtualization_time_bonus (struct cgraph_node
*node
,
1932 vec
<tree
> known_csts
,
1933 vec
<ipa_polymorphic_call_context
> known_contexts
,
1934 vec
<ipa_agg_jump_function_p
> known_aggs
)
1936 struct cgraph_edge
*ie
;
1939 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
1941 struct cgraph_node
*callee
;
1942 struct inline_summary
*isummary
;
1943 enum availability avail
;
1947 target
= ipa_get_indirect_edge_target (ie
, known_csts
, known_contexts
,
1948 known_aggs
, &speculative
);
1952 /* Only bare minimum benefit for clearly un-inlineable targets. */
1954 callee
= cgraph_node::get (target
);
1955 if (!callee
|| !callee
->definition
)
1957 callee
= callee
->function_symbol (&avail
);
1958 if (avail
< AVAIL_AVAILABLE
)
1960 isummary
= inline_summary (callee
);
1961 if (!isummary
->inlinable
)
1964 /* FIXME: The values below need re-considering and perhaps also
1965 integrating into the cost metrics, at lest in some very basic way. */
1966 if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 4)
1967 res
+= 31 / ((int)speculative
+ 1);
1968 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 2)
1969 res
+= 15 / ((int)speculative
+ 1);
1970 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
1971 || DECL_DECLARED_INLINE_P (callee
->decl
))
1972 res
+= 7 / ((int)speculative
+ 1);
1978 /* Return time bonus incurred because of HINTS. */
1981 hint_time_bonus (inline_hints hints
)
1984 if (hints
& (INLINE_HINT_loop_iterations
| INLINE_HINT_loop_stride
))
1985 result
+= PARAM_VALUE (PARAM_IPA_CP_LOOP_HINT_BONUS
);
1986 if (hints
& INLINE_HINT_array_index
)
1987 result
+= PARAM_VALUE (PARAM_IPA_CP_ARRAY_INDEX_HINT_BONUS
);
1991 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
1992 and SIZE_COST and with the sum of frequencies of incoming edges to the
1993 potential new clone in FREQUENCIES. */
1996 good_cloning_opportunity_p (struct cgraph_node
*node
, int time_benefit
,
1997 int freq_sum
, gcov_type count_sum
, int size_cost
)
1999 if (time_benefit
== 0
2000 || !opt_for_fn (node
->decl
, flag_ipa_cp_clone
)
2001 || !optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node
->decl
)))
2004 gcc_assert (size_cost
> 0);
2008 int factor
= (count_sum
* 1000) / max_count
;
2009 int64_t evaluation
= (((int64_t) time_benefit
* factor
)
2012 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2013 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
2014 "size: %i, count_sum: " HOST_WIDE_INT_PRINT_DEC
2015 ") -> evaluation: " "%"PRId64
2016 ", threshold: %i\n",
2017 time_benefit
, size_cost
, (HOST_WIDE_INT
) count_sum
,
2018 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
2020 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
2024 int64_t evaluation
= (((int64_t) time_benefit
* freq_sum
)
2027 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2028 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
2029 "size: %i, freq_sum: %i) -> evaluation: "
2030 "%"PRId64
", threshold: %i\n",
2031 time_benefit
, size_cost
, freq_sum
, evaluation
,
2032 PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
2034 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
2038 /* Return all context independent values from aggregate lattices in PLATS in a
2039 vector. Return NULL if there are none. */
2041 static vec
<ipa_agg_jf_item
, va_gc
> *
2042 context_independent_aggregate_values (struct ipcp_param_lattices
*plats
)
2044 vec
<ipa_agg_jf_item
, va_gc
> *res
= NULL
;
2046 if (plats
->aggs_bottom
2047 || plats
->aggs_contain_variable
2048 || plats
->aggs_count
== 0)
2051 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
;
2053 aglat
= aglat
->next
)
2054 if (aglat
->is_single_const ())
2056 struct ipa_agg_jf_item item
;
2057 item
.offset
= aglat
->offset
;
2058 item
.value
= aglat
->values
->value
;
2059 vec_safe_push (res
, item
);
2064 /* Allocate KNOWN_CSTS, KNOWN_CONTEXTS and, if non-NULL, KNOWN_AGGS and
2065 populate them with values of parameters that are known independent of the
2066 context. INFO describes the function. If REMOVABLE_PARAMS_COST is
2067 non-NULL, the movement cost of all removable parameters will be stored in
2071 gather_context_independent_values (struct ipa_node_params
*info
,
2072 vec
<tree
> *known_csts
,
2073 vec
<ipa_polymorphic_call_context
>
2075 vec
<ipa_agg_jump_function
> *known_aggs
,
2076 int *removable_params_cost
)
2078 int i
, count
= ipa_get_param_count (info
);
2081 known_csts
->create (0);
2082 known_contexts
->create (0);
2083 known_csts
->safe_grow_cleared (count
);
2084 known_contexts
->safe_grow_cleared (count
);
2087 known_aggs
->create (0);
2088 known_aggs
->safe_grow_cleared (count
);
2091 if (removable_params_cost
)
2092 *removable_params_cost
= 0;
2094 for (i
= 0; i
< count
; i
++)
2096 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2097 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
2099 if (lat
->is_single_const ())
2101 ipcp_value
<tree
> *val
= lat
->values
;
2102 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
2103 (*known_csts
)[i
] = val
->value
;
2104 if (removable_params_cost
)
2105 *removable_params_cost
2106 += estimate_move_cost (TREE_TYPE (val
->value
), false);
2109 else if (removable_params_cost
2110 && !ipa_is_param_used (info
, i
))
2111 *removable_params_cost
2112 += ipa_get_param_move_cost (info
, i
);
2114 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
2115 if (ctxlat
->is_single_const ())
2117 (*known_contexts
)[i
] = ctxlat
->values
->value
;
2123 vec
<ipa_agg_jf_item
, va_gc
> *agg_items
;
2124 struct ipa_agg_jump_function
*ajf
;
2126 agg_items
= context_independent_aggregate_values (plats
);
2127 ajf
= &(*known_aggs
)[i
];
2128 ajf
->items
= agg_items
;
2129 ajf
->by_ref
= plats
->aggs_by_ref
;
2130 ret
|= agg_items
!= NULL
;
2137 /* The current interface in ipa-inline-analysis requires a pointer vector.
2140 FIXME: That interface should be re-worked, this is slightly silly. Still,
2141 I'd like to discuss how to change it first and this demonstrates the
2144 static vec
<ipa_agg_jump_function_p
>
2145 agg_jmp_p_vec_for_t_vec (vec
<ipa_agg_jump_function
> known_aggs
)
2147 vec
<ipa_agg_jump_function_p
> ret
;
2148 struct ipa_agg_jump_function
*ajf
;
2151 ret
.create (known_aggs
.length ());
2152 FOR_EACH_VEC_ELT (known_aggs
, i
, ajf
)
2153 ret
.quick_push (ajf
);
2157 /* Perform time and size measurement of NODE with the context given in
2158 KNOWN_CSTS, KNOWN_CONTEXTS and KNOWN_AGGS, calculate the benefit and cost
2159 given BASE_TIME of the node without specialization, REMOVABLE_PARAMS_COST of
2160 all context-independent removable parameters and EST_MOVE_COST of estimated
2161 movement of the considered parameter and store it into VAL. */
2164 perform_estimation_of_a_value (cgraph_node
*node
, vec
<tree
> known_csts
,
2165 vec
<ipa_polymorphic_call_context
> known_contexts
,
2166 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
,
2167 int base_time
, int removable_params_cost
,
2168 int est_move_cost
, ipcp_value_base
*val
)
2170 int time
, size
, time_benefit
;
2173 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
2174 known_aggs_ptrs
, &size
, &time
,
2176 time_benefit
= base_time
- time
2177 + devirtualization_time_bonus (node
, known_csts
, known_contexts
,
2179 + hint_time_bonus (hints
)
2180 + removable_params_cost
+ est_move_cost
;
2182 gcc_checking_assert (size
>=0);
2183 /* The inliner-heuristics based estimates may think that in certain
2184 contexts some functions do not have any size at all but we want
2185 all specializations to have at least a tiny cost, not least not to
2190 val
->local_time_benefit
= time_benefit
;
2191 val
->local_size_cost
= size
;
2194 /* Iterate over known values of parameters of NODE and estimate the local
2195 effects in terms of time and size they have. */
2198 estimate_local_effects (struct cgraph_node
*node
)
2200 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2201 int i
, count
= ipa_get_param_count (info
);
2202 vec
<tree
> known_csts
;
2203 vec
<ipa_polymorphic_call_context
> known_contexts
;
2204 vec
<ipa_agg_jump_function
> known_aggs
;
2205 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
;
2207 int base_time
= inline_summary (node
)->time
;
2208 int removable_params_cost
;
2210 if (!count
|| !ipcp_versionable_function_p (node
))
2213 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2214 fprintf (dump_file
, "\nEstimating effects for %s/%i, base_time: %i.\n",
2215 node
->name (), node
->order
, base_time
);
2217 always_const
= gather_context_independent_values (info
, &known_csts
,
2218 &known_contexts
, &known_aggs
,
2219 &removable_params_cost
);
2220 known_aggs_ptrs
= agg_jmp_p_vec_for_t_vec (known_aggs
);
2223 struct caller_statistics stats
;
2227 init_caller_stats (&stats
);
2228 node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
2230 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
2231 known_aggs_ptrs
, &size
, &time
, &hints
);
2232 time
-= devirtualization_time_bonus (node
, known_csts
, known_contexts
,
2234 time
-= hint_time_bonus (hints
);
2235 time
-= removable_params_cost
;
2236 size
-= stats
.n_calls
* removable_params_cost
;
2239 fprintf (dump_file
, " - context independent values, size: %i, "
2240 "time_benefit: %i\n", size
, base_time
- time
);
2243 || node
->will_be_removed_from_program_if_no_direct_calls_p ())
2245 info
->do_clone_for_all_contexts
= true;
2249 fprintf (dump_file
, " Decided to specialize for all "
2250 "known contexts, code not going to grow.\n");
2252 else if (good_cloning_opportunity_p (node
, base_time
- time
,
2253 stats
.freq_sum
, stats
.count_sum
,
2256 if (size
+ overall_size
<= max_new_size
)
2258 info
->do_clone_for_all_contexts
= true;
2260 overall_size
+= size
;
2263 fprintf (dump_file
, " Decided to specialize for all "
2264 "known contexts, growth deemed beneficial.\n");
2266 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2267 fprintf (dump_file
, " Not cloning for all contexts because "
2268 "max_new_size would be reached with %li.\n",
2269 size
+ overall_size
);
2273 for (i
= 0; i
< count
; i
++)
2275 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2276 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
2277 ipcp_value
<tree
> *val
;
2284 for (val
= lat
->values
; val
; val
= val
->next
)
2286 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
2287 known_csts
[i
] = val
->value
;
2289 int emc
= estimate_move_cost (TREE_TYPE (val
->value
), true);
2290 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
2291 known_aggs_ptrs
, base_time
,
2292 removable_params_cost
, emc
, val
);
2294 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2296 fprintf (dump_file
, " - estimates for value ");
2297 print_ipcp_constant_value (dump_file
, val
->value
);
2298 fprintf (dump_file
, " for ");
2299 ipa_dump_param (dump_file
, info
, i
);
2300 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
2301 val
->local_time_benefit
, val
->local_size_cost
);
2304 known_csts
[i
] = NULL_TREE
;
2307 for (i
= 0; i
< count
; i
++)
2309 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2311 if (!plats
->virt_call
)
2314 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
2315 ipcp_value
<ipa_polymorphic_call_context
> *val
;
2319 || !known_contexts
[i
].useless_p ())
2322 for (val
= ctxlat
->values
; val
; val
= val
->next
)
2324 known_contexts
[i
] = val
->value
;
2325 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
2326 known_aggs_ptrs
, base_time
,
2327 removable_params_cost
, 0, val
);
2329 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2331 fprintf (dump_file
, " - estimates for polymorphic context ");
2332 print_ipcp_constant_value (dump_file
, val
->value
);
2333 fprintf (dump_file
, " for ");
2334 ipa_dump_param (dump_file
, info
, i
);
2335 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
2336 val
->local_time_benefit
, val
->local_size_cost
);
2339 known_contexts
[i
] = ipa_polymorphic_call_context ();
2342 for (i
= 0; i
< count
; i
++)
2344 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2345 struct ipa_agg_jump_function
*ajf
;
2346 struct ipcp_agg_lattice
*aglat
;
2348 if (plats
->aggs_bottom
|| !plats
->aggs
)
2351 ajf
= &known_aggs
[i
];
2352 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2354 ipcp_value
<tree
> *val
;
2355 if (aglat
->bottom
|| !aglat
->values
2356 /* If the following is true, the one value is in known_aggs. */
2357 || (!plats
->aggs_contain_variable
2358 && aglat
->is_single_const ()))
2361 for (val
= aglat
->values
; val
; val
= val
->next
)
2363 struct ipa_agg_jf_item item
;
2365 item
.offset
= aglat
->offset
;
2366 item
.value
= val
->value
;
2367 vec_safe_push (ajf
->items
, item
);
2369 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
2370 known_aggs_ptrs
, base_time
,
2371 removable_params_cost
, 0, val
);
2373 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2375 fprintf (dump_file
, " - estimates for value ");
2376 print_ipcp_constant_value (dump_file
, val
->value
);
2377 fprintf (dump_file
, " for ");
2378 ipa_dump_param (dump_file
, info
, i
);
2379 fprintf (dump_file
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
2380 "]: time_benefit: %i, size: %i\n",
2381 plats
->aggs_by_ref
? "ref " : "",
2383 val
->local_time_benefit
, val
->local_size_cost
);
2391 for (i
= 0; i
< count
; i
++)
2392 vec_free (known_aggs
[i
].items
);
2394 known_csts
.release ();
2395 known_contexts
.release ();
2396 known_aggs
.release ();
2397 known_aggs_ptrs
.release ();
2401 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
2402 topological sort of values. */
2404 template <typename valtype
>
2406 value_topo_info
<valtype
>::add_val (ipcp_value
<valtype
> *cur_val
)
2408 ipcp_value_source
<valtype
> *src
;
2414 cur_val
->dfs
= dfs_counter
;
2415 cur_val
->low_link
= dfs_counter
;
2417 cur_val
->topo_next
= stack
;
2419 cur_val
->on_stack
= true;
2421 for (src
= cur_val
->sources
; src
; src
= src
->next
)
2424 if (src
->val
->dfs
== 0)
2427 if (src
->val
->low_link
< cur_val
->low_link
)
2428 cur_val
->low_link
= src
->val
->low_link
;
2430 else if (src
->val
->on_stack
2431 && src
->val
->dfs
< cur_val
->low_link
)
2432 cur_val
->low_link
= src
->val
->dfs
;
2435 if (cur_val
->dfs
== cur_val
->low_link
)
2437 ipcp_value
<valtype
> *v
, *scc_list
= NULL
;
2442 stack
= v
->topo_next
;
2443 v
->on_stack
= false;
2445 v
->scc_next
= scc_list
;
2448 while (v
!= cur_val
);
2450 cur_val
->topo_next
= values_topo
;
2451 values_topo
= cur_val
;
2455 /* Add all values in lattices associated with NODE to the topological sort if
2456 they are not there yet. */
2459 add_all_node_vals_to_toposort (cgraph_node
*node
, ipa_topo_info
*topo
)
2461 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2462 int i
, count
= ipa_get_param_count (info
);
2464 for (i
= 0; i
< count
; i
++)
2466 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2467 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
2468 struct ipcp_agg_lattice
*aglat
;
2472 ipcp_value
<tree
> *val
;
2473 for (val
= lat
->values
; val
; val
= val
->next
)
2474 topo
->constants
.add_val (val
);
2477 if (!plats
->aggs_bottom
)
2478 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2481 ipcp_value
<tree
> *val
;
2482 for (val
= aglat
->values
; val
; val
= val
->next
)
2483 topo
->constants
.add_val (val
);
2486 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
2487 if (!ctxlat
->bottom
)
2489 ipcp_value
<ipa_polymorphic_call_context
> *ctxval
;
2490 for (ctxval
= ctxlat
->values
; ctxval
; ctxval
= ctxval
->next
)
2491 topo
->contexts
.add_val (ctxval
);
2496 /* One pass of constants propagation along the call graph edges, from callers
2497 to callees (requires topological ordering in TOPO), iterate over strongly
2498 connected components. */
2501 propagate_constants_topo (struct ipa_topo_info
*topo
)
2505 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
2508 struct cgraph_node
*v
, *node
= topo
->order
[i
];
2509 vec
<cgraph_node
*> cycle_nodes
= ipa_get_nodes_in_cycle (node
);
2511 /* First, iteratively propagate within the strongly connected component
2512 until all lattices stabilize. */
2513 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
2514 if (v
->has_gimple_body_p ())
2515 push_node_to_stack (topo
, v
);
2517 v
= pop_node_from_stack (topo
);
2520 struct cgraph_edge
*cs
;
2522 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
2523 if (ipa_edge_within_scc (cs
)
2524 && propagate_constants_accross_call (cs
))
2525 push_node_to_stack (topo
, cs
->callee
);
2526 v
= pop_node_from_stack (topo
);
2529 /* Afterwards, propagate along edges leading out of the SCC, calculates
2530 the local effects of the discovered constants and all valid values to
2531 their topological sort. */
2532 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
2533 if (v
->has_gimple_body_p ())
2535 struct cgraph_edge
*cs
;
2537 estimate_local_effects (v
);
2538 add_all_node_vals_to_toposort (v
, topo
);
2539 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
2540 if (!ipa_edge_within_scc (cs
))
2541 propagate_constants_accross_call (cs
);
2543 cycle_nodes
.release ();
2548 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
2549 the bigger one if otherwise. */
2552 safe_add (int a
, int b
)
2554 if (a
> INT_MAX
/2 || b
> INT_MAX
/2)
2555 return a
> b
? a
: b
;
2561 /* Propagate the estimated effects of individual values along the topological
2562 from the dependent values to those they depend on. */
2564 template <typename valtype
>
2566 value_topo_info
<valtype
>::propagate_effects ()
2568 ipcp_value
<valtype
> *base
;
2570 for (base
= values_topo
; base
; base
= base
->topo_next
)
2572 ipcp_value_source
<valtype
> *src
;
2573 ipcp_value
<valtype
> *val
;
2574 int time
= 0, size
= 0;
2576 for (val
= base
; val
; val
= val
->scc_next
)
2578 time
= safe_add (time
,
2579 val
->local_time_benefit
+ val
->prop_time_benefit
);
2580 size
= safe_add (size
, val
->local_size_cost
+ val
->prop_size_cost
);
2583 for (val
= base
; val
; val
= val
->scc_next
)
2584 for (src
= val
->sources
; src
; src
= src
->next
)
2586 && src
->cs
->maybe_hot_p ())
2588 src
->val
->prop_time_benefit
= safe_add (time
,
2589 src
->val
->prop_time_benefit
);
2590 src
->val
->prop_size_cost
= safe_add (size
,
2591 src
->val
->prop_size_cost
);
2597 /* Propagate constants, polymorphic contexts and their effects from the
2598 summaries interprocedurally. */
2601 ipcp_propagate_stage (struct ipa_topo_info
*topo
)
2603 struct cgraph_node
*node
;
2606 fprintf (dump_file
, "\n Propagating constants:\n\n");
2609 ipa_update_after_lto_read ();
2612 FOR_EACH_DEFINED_FUNCTION (node
)
2614 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2616 determine_versionability (node
);
2617 if (node
->has_gimple_body_p ())
2619 info
->lattices
= XCNEWVEC (struct ipcp_param_lattices
,
2620 ipa_get_param_count (info
));
2621 initialize_node_lattices (node
);
2623 if (node
->definition
&& !node
->alias
)
2624 overall_size
+= inline_summary (node
)->self_size
;
2625 if (node
->count
> max_count
)
2626 max_count
= node
->count
;
2629 max_new_size
= overall_size
;
2630 if (max_new_size
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
2631 max_new_size
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
2632 max_new_size
+= max_new_size
* PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH
) / 100 + 1;
2635 fprintf (dump_file
, "\noverall_size: %li, max_new_size: %li\n",
2636 overall_size
, max_new_size
);
2638 propagate_constants_topo (topo
);
2639 #ifdef ENABLE_CHECKING
2640 ipcp_verify_propagated_values ();
2642 topo
->constants
.propagate_effects ();
2643 topo
->contexts
.propagate_effects ();
2647 fprintf (dump_file
, "\nIPA lattices after all propagation:\n");
2648 print_all_lattices (dump_file
, (dump_flags
& TDF_DETAILS
), true);
2652 /* Discover newly direct outgoing edges from NODE which is a new clone with
2653 known KNOWN_CSTS and make them direct. */
2656 ipcp_discover_new_direct_edges (struct cgraph_node
*node
,
2657 vec
<tree
> known_csts
,
2658 vec
<ipa_polymorphic_call_context
>
2660 struct ipa_agg_replacement_value
*aggvals
)
2662 struct cgraph_edge
*ie
, *next_ie
;
2665 for (ie
= node
->indirect_calls
; ie
; ie
= next_ie
)
2670 next_ie
= ie
->next_callee
;
2671 target
= ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
2672 vNULL
, aggvals
, &speculative
);
2675 bool agg_contents
= ie
->indirect_info
->agg_contents
;
2676 bool polymorphic
= ie
->indirect_info
->polymorphic
;
2677 int param_index
= ie
->indirect_info
->param_index
;
2678 struct cgraph_edge
*cs
= ipa_make_edge_direct_to_target (ie
, target
,
2682 if (cs
&& !agg_contents
&& !polymorphic
)
2684 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2685 int c
= ipa_get_controlled_uses (info
, param_index
);
2686 if (c
!= IPA_UNDESCRIBED_USE
)
2688 struct ipa_ref
*to_del
;
2691 ipa_set_controlled_uses (info
, param_index
, c
);
2692 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2693 fprintf (dump_file
, " controlled uses count of param "
2694 "%i bumped down to %i\n", param_index
, c
);
2696 && (to_del
= node
->find_reference (cs
->callee
, NULL
, 0)))
2698 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2699 fprintf (dump_file
, " and even removing its "
2700 "cloning-created reference\n");
2701 to_del
->remove_reference ();
2707 /* Turning calls to direct calls will improve overall summary. */
2709 inline_update_overall_summary (node
);
2712 /* Vector of pointers which for linked lists of clones of an original crgaph
2715 static vec
<cgraph_edge
*> next_edge_clone
;
2716 static vec
<cgraph_edge
*> prev_edge_clone
;
2719 grow_edge_clone_vectors (void)
2721 if (next_edge_clone
.length ()
2722 <= (unsigned) symtab
->edges_max_uid
)
2723 next_edge_clone
.safe_grow_cleared (symtab
->edges_max_uid
+ 1);
2724 if (prev_edge_clone
.length ()
2725 <= (unsigned) symtab
->edges_max_uid
)
2726 prev_edge_clone
.safe_grow_cleared (symtab
->edges_max_uid
+ 1);
2729 /* Edge duplication hook to grow the appropriate linked list in
2733 ipcp_edge_duplication_hook (struct cgraph_edge
*src
, struct cgraph_edge
*dst
,
2736 grow_edge_clone_vectors ();
2738 struct cgraph_edge
*old_next
= next_edge_clone
[src
->uid
];
2740 prev_edge_clone
[old_next
->uid
] = dst
;
2741 prev_edge_clone
[dst
->uid
] = src
;
2743 next_edge_clone
[dst
->uid
] = old_next
;
2744 next_edge_clone
[src
->uid
] = dst
;
2747 /* Hook that is called by cgraph.c when an edge is removed. */
2750 ipcp_edge_removal_hook (struct cgraph_edge
*cs
, void *)
2752 grow_edge_clone_vectors ();
2754 struct cgraph_edge
*prev
= prev_edge_clone
[cs
->uid
];
2755 struct cgraph_edge
*next
= next_edge_clone
[cs
->uid
];
2757 next_edge_clone
[prev
->uid
] = next
;
2759 prev_edge_clone
[next
->uid
] = prev
;
2762 /* See if NODE is a clone with a known aggregate value at a given OFFSET of a
2763 parameter with the given INDEX. */
2766 get_clone_agg_value (struct cgraph_node
*node
, HOST_WIDE_INT offset
,
2769 struct ipa_agg_replacement_value
*aggval
;
2771 aggval
= ipa_get_agg_replacements_for_node (node
);
2774 if (aggval
->offset
== offset
2775 && aggval
->index
== index
)
2776 return aggval
->value
;
2777 aggval
= aggval
->next
;
2782 /* Return true if edge CS does bring about the value described by SRC. */
2785 cgraph_edge_brings_value_p (struct cgraph_edge
*cs
,
2786 ipcp_value_source
<tree
> *src
)
2788 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2789 cgraph_node
*real_dest
= cs
->callee
->function_symbol ();
2790 struct ipa_node_params
*dst_info
= IPA_NODE_REF (real_dest
);
2792 if ((dst_info
->ipcp_orig_node
&& !dst_info
->is_all_contexts_clone
)
2793 || caller_info
->node_dead
)
2798 if (caller_info
->ipcp_orig_node
)
2801 if (src
->offset
== -1)
2802 t
= caller_info
->known_csts
[src
->index
];
2804 t
= get_clone_agg_value (cs
->caller
, src
->offset
, src
->index
);
2805 return (t
!= NULL_TREE
2806 && values_equal_for_ipcp_p (src
->val
->value
, t
));
2810 struct ipcp_agg_lattice
*aglat
;
2811 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
2813 if (src
->offset
== -1)
2814 return (plats
->itself
.is_single_const ()
2815 && values_equal_for_ipcp_p (src
->val
->value
,
2816 plats
->itself
.values
->value
));
2819 if (plats
->aggs_bottom
|| plats
->aggs_contain_variable
)
2821 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2822 if (aglat
->offset
== src
->offset
)
2823 return (aglat
->is_single_const ()
2824 && values_equal_for_ipcp_p (src
->val
->value
,
2825 aglat
->values
->value
));
2831 /* Return true if edge CS does bring about the value described by SRC. */
2834 cgraph_edge_brings_value_p (struct cgraph_edge
*cs
,
2835 ipcp_value_source
<ipa_polymorphic_call_context
>
2838 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2839 cgraph_node
*real_dest
= cs
->callee
->function_symbol ();
2840 struct ipa_node_params
*dst_info
= IPA_NODE_REF (real_dest
);
2842 if ((dst_info
->ipcp_orig_node
&& !dst_info
->is_all_contexts_clone
)
2843 || caller_info
->node_dead
)
2848 if (caller_info
->ipcp_orig_node
)
2849 return (caller_info
->known_contexts
.length () > (unsigned) src
->index
)
2850 && values_equal_for_ipcp_p (src
->val
->value
,
2851 caller_info
->known_contexts
[src
->index
]);
2853 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
2855 return plats
->ctxlat
.is_single_const ()
2856 && values_equal_for_ipcp_p (src
->val
->value
,
2857 plats
->ctxlat
.values
->value
);
2860 /* Get the next clone in the linked list of clones of an edge. */
2862 static inline struct cgraph_edge
*
2863 get_next_cgraph_edge_clone (struct cgraph_edge
*cs
)
2865 return next_edge_clone
[cs
->uid
];
2868 /* Given VAL, iterate over all its sources and if they still hold, add their
2869 edge frequency and their number into *FREQUENCY and *CALLER_COUNT
2872 template <typename valtype
>
2874 get_info_about_necessary_edges (ipcp_value
<valtype
> *val
, int *freq_sum
,
2875 gcov_type
*count_sum
, int *caller_count
)
2877 ipcp_value_source
<valtype
> *src
;
2878 int freq
= 0, count
= 0;
2882 for (src
= val
->sources
; src
; src
= src
->next
)
2884 struct cgraph_edge
*cs
= src
->cs
;
2887 if (cgraph_edge_brings_value_p (cs
, src
))
2890 freq
+= cs
->frequency
;
2892 hot
|= cs
->maybe_hot_p ();
2894 cs
= get_next_cgraph_edge_clone (cs
);
2900 *caller_count
= count
;
2904 /* Return a vector of incoming edges that do bring value VAL. It is assumed
2905 their number is known and equal to CALLER_COUNT. */
2907 template <typename valtype
>
2908 static vec
<cgraph_edge
*>
2909 gather_edges_for_value (ipcp_value
<valtype
> *val
, int caller_count
)
2911 ipcp_value_source
<valtype
> *src
;
2912 vec
<cgraph_edge
*> ret
;
2914 ret
.create (caller_count
);
2915 for (src
= val
->sources
; src
; src
= src
->next
)
2917 struct cgraph_edge
*cs
= src
->cs
;
2920 if (cgraph_edge_brings_value_p (cs
, src
))
2921 ret
.quick_push (cs
);
2922 cs
= get_next_cgraph_edge_clone (cs
);
2929 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
2930 Return it or NULL if for some reason it cannot be created. */
2932 static struct ipa_replace_map
*
2933 get_replacement_map (struct ipa_node_params
*info
, tree value
, int parm_num
)
2935 struct ipa_replace_map
*replace_map
;
2938 replace_map
= ggc_alloc
<ipa_replace_map
> ();
2941 fprintf (dump_file
, " replacing ");
2942 ipa_dump_param (dump_file
, info
, parm_num
);
2944 fprintf (dump_file
, " with const ");
2945 print_generic_expr (dump_file
, value
, 0);
2946 fprintf (dump_file
, "\n");
2948 replace_map
->old_tree
= NULL
;
2949 replace_map
->parm_num
= parm_num
;
2950 replace_map
->new_tree
= value
;
2951 replace_map
->replace_p
= true;
2952 replace_map
->ref_p
= false;
2957 /* Dump new profiling counts */
2960 dump_profile_updates (struct cgraph_node
*orig_node
,
2961 struct cgraph_node
*new_node
)
2963 struct cgraph_edge
*cs
;
2965 fprintf (dump_file
, " setting count of the specialized node to "
2966 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) new_node
->count
);
2967 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
2968 fprintf (dump_file
, " edge to %s has count "
2969 HOST_WIDE_INT_PRINT_DEC
"\n",
2970 cs
->callee
->name (), (HOST_WIDE_INT
) cs
->count
);
2972 fprintf (dump_file
, " setting count of the original node to "
2973 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) orig_node
->count
);
2974 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
2975 fprintf (dump_file
, " edge to %s is left with "
2976 HOST_WIDE_INT_PRINT_DEC
"\n",
2977 cs
->callee
->name (), (HOST_WIDE_INT
) cs
->count
);
2980 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
2981 their profile information to reflect this. */
2984 update_profiling_info (struct cgraph_node
*orig_node
,
2985 struct cgraph_node
*new_node
)
2987 struct cgraph_edge
*cs
;
2988 struct caller_statistics stats
;
2989 gcov_type new_sum
, orig_sum
;
2990 gcov_type remainder
, orig_node_count
= orig_node
->count
;
2992 if (orig_node_count
== 0)
2995 init_caller_stats (&stats
);
2996 orig_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
2998 orig_sum
= stats
.count_sum
;
2999 init_caller_stats (&stats
);
3000 new_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
3002 new_sum
= stats
.count_sum
;
3004 if (orig_node_count
< orig_sum
+ new_sum
)
3007 fprintf (dump_file
, " Problem: node %s/%i has too low count "
3008 HOST_WIDE_INT_PRINT_DEC
" while the sum of incoming "
3009 "counts is " HOST_WIDE_INT_PRINT_DEC
"\n",
3010 orig_node
->name (), orig_node
->order
,
3011 (HOST_WIDE_INT
) orig_node_count
,
3012 (HOST_WIDE_INT
) (orig_sum
+ new_sum
));
3014 orig_node_count
= (orig_sum
+ new_sum
) * 12 / 10;
3016 fprintf (dump_file
, " proceeding by pretending it was "
3017 HOST_WIDE_INT_PRINT_DEC
"\n",
3018 (HOST_WIDE_INT
) orig_node_count
);
3021 new_node
->count
= new_sum
;
3022 remainder
= orig_node_count
- new_sum
;
3023 orig_node
->count
= remainder
;
3025 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3027 cs
->count
= apply_probability (cs
->count
,
3028 GCOV_COMPUTE_SCALE (new_sum
,
3033 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3034 cs
->count
= apply_probability (cs
->count
,
3035 GCOV_COMPUTE_SCALE (remainder
,
3039 dump_profile_updates (orig_node
, new_node
);
3042 /* Update the respective profile of specialized NEW_NODE and the original
3043 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
3044 have been redirected to the specialized version. */
3047 update_specialized_profile (struct cgraph_node
*new_node
,
3048 struct cgraph_node
*orig_node
,
3049 gcov_type redirected_sum
)
3051 struct cgraph_edge
*cs
;
3052 gcov_type new_node_count
, orig_node_count
= orig_node
->count
;
3055 fprintf (dump_file
, " the sum of counts of redirected edges is "
3056 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) redirected_sum
);
3057 if (orig_node_count
== 0)
3060 gcc_assert (orig_node_count
>= redirected_sum
);
3062 new_node_count
= new_node
->count
;
3063 new_node
->count
+= redirected_sum
;
3064 orig_node
->count
-= redirected_sum
;
3066 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3068 cs
->count
+= apply_probability (cs
->count
,
3069 GCOV_COMPUTE_SCALE (redirected_sum
,
3074 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3076 gcov_type dec
= apply_probability (cs
->count
,
3077 GCOV_COMPUTE_SCALE (redirected_sum
,
3079 if (dec
< cs
->count
)
3086 dump_profile_updates (orig_node
, new_node
);
3089 /* Create a specialized version of NODE with known constants in KNOWN_CSTS,
3090 known contexts in KNOWN_CONTEXTS and known aggregate values in AGGVALS and
3091 redirect all edges in CALLERS to it. */
3093 static struct cgraph_node
*
3094 create_specialized_node (struct cgraph_node
*node
,
3095 vec
<tree
> known_csts
,
3096 vec
<ipa_polymorphic_call_context
> known_contexts
,
3097 struct ipa_agg_replacement_value
*aggvals
,
3098 vec
<cgraph_edge
*> callers
)
3100 struct ipa_node_params
*new_info
, *info
= IPA_NODE_REF (node
);
3101 vec
<ipa_replace_map
*, va_gc
> *replace_trees
= NULL
;
3102 struct ipa_agg_replacement_value
*av
;
3103 struct cgraph_node
*new_node
;
3104 int i
, count
= ipa_get_param_count (info
);
3105 bitmap args_to_skip
;
3107 gcc_assert (!info
->ipcp_orig_node
);
3109 if (node
->local
.can_change_signature
)
3111 args_to_skip
= BITMAP_GGC_ALLOC ();
3112 for (i
= 0; i
< count
; i
++)
3114 tree t
= known_csts
[i
];
3116 if (t
|| !ipa_is_param_used (info
, i
))
3117 bitmap_set_bit (args_to_skip
, i
);
3122 args_to_skip
= NULL
;
3123 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3124 fprintf (dump_file
, " cannot change function signature\n");
3127 for (i
= 0; i
< count
; i
++)
3129 tree t
= known_csts
[i
];
3132 struct ipa_replace_map
*replace_map
;
3134 gcc_checking_assert (TREE_CODE (t
) != TREE_BINFO
);
3135 replace_map
= get_replacement_map (info
, t
, i
);
3137 vec_safe_push (replace_trees
, replace_map
);
3141 new_node
= node
->create_virtual_clone (callers
, replace_trees
,
3142 args_to_skip
, "constprop");
3143 ipa_set_node_agg_value_chain (new_node
, aggvals
);
3144 for (av
= aggvals
; av
; av
= av
->next
)
3145 new_node
->maybe_create_reference (av
->value
, IPA_REF_ADDR
, NULL
);
3147 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3149 fprintf (dump_file
, " the new node is %s/%i.\n",
3150 new_node
->name (), new_node
->order
);
3151 if (known_contexts
.exists ())
3153 for (i
= 0; i
< count
; i
++)
3154 if (!known_contexts
[i
].useless_p ())
3156 fprintf (dump_file
, " known ctx %i is ", i
);
3157 known_contexts
[i
].dump (dump_file
);
3161 ipa_dump_agg_replacement_values (dump_file
, aggvals
);
3163 ipa_check_create_node_params ();
3164 update_profiling_info (node
, new_node
);
3165 new_info
= IPA_NODE_REF (new_node
);
3166 new_info
->ipcp_orig_node
= node
;
3167 new_info
->known_csts
= known_csts
;
3168 new_info
->known_contexts
= known_contexts
;
3170 ipcp_discover_new_direct_edges (new_node
, known_csts
, known_contexts
, aggvals
);
3176 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
3177 KNOWN_CSTS with constants that are also known for all of the CALLERS. */
3180 find_more_scalar_values_for_callers_subset (struct cgraph_node
*node
,
3181 vec
<tree
> known_csts
,
3182 vec
<cgraph_edge
*> callers
)
3184 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3185 int i
, count
= ipa_get_param_count (info
);
3187 for (i
= 0; i
< count
; i
++)
3189 struct cgraph_edge
*cs
;
3190 tree newval
= NULL_TREE
;
3194 if (ipa_get_scalar_lat (info
, i
)->bottom
|| known_csts
[i
])
3197 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3199 struct ipa_jump_func
*jump_func
;
3202 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
)))
3207 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
3208 t
= ipa_value_from_jfunc (IPA_NODE_REF (cs
->caller
), jump_func
);
3211 && !values_equal_for_ipcp_p (t
, newval
))
3212 || (!first
&& !newval
))
3224 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3226 fprintf (dump_file
, " adding an extra known scalar value ");
3227 print_ipcp_constant_value (dump_file
, newval
);
3228 fprintf (dump_file
, " for ");
3229 ipa_dump_param (dump_file
, info
, i
);
3230 fprintf (dump_file
, "\n");
3233 known_csts
[i
] = newval
;
3238 /* Given a NODE and a subset of its CALLERS, try to populate plank slots in
3239 KNOWN_CONTEXTS with polymorphic contexts that are also known for all of the
3243 find_more_contexts_for_caller_subset (cgraph_node
*node
,
3244 vec
<ipa_polymorphic_call_context
>
3246 vec
<cgraph_edge
*> callers
)
3248 ipa_node_params
*info
= IPA_NODE_REF (node
);
3249 int i
, count
= ipa_get_param_count (info
);
3251 for (i
= 0; i
< count
; i
++)
3255 if (ipa_get_poly_ctx_lat (info
, i
)->bottom
3256 || (known_contexts
->exists ()
3257 && !(*known_contexts
)[i
].useless_p ()))
3260 ipa_polymorphic_call_context newval
;
3264 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3266 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
)))
3268 ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
),
3270 ipa_polymorphic_call_context ctx
;
3271 ctx
= ipa_context_from_jfunc (IPA_NODE_REF (cs
->caller
), cs
, i
,
3279 newval
.meet_with (ctx
);
3280 if (newval
.useless_p ())
3284 if (!newval
.useless_p ())
3286 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3288 fprintf (dump_file
, " adding an extra known polymorphic "
3290 print_ipcp_constant_value (dump_file
, newval
);
3291 fprintf (dump_file
, " for ");
3292 ipa_dump_param (dump_file
, info
, i
);
3293 fprintf (dump_file
, "\n");
3296 if (!known_contexts
->exists ())
3297 known_contexts
->safe_grow_cleared (ipa_get_param_count (info
));
3298 (*known_contexts
)[i
] = newval
;
3304 /* Go through PLATS and create a vector of values consisting of values and
3305 offsets (minus OFFSET) of lattices that contain only a single value. */
3307 static vec
<ipa_agg_jf_item
>
3308 copy_plats_to_inter (struct ipcp_param_lattices
*plats
, HOST_WIDE_INT offset
)
3310 vec
<ipa_agg_jf_item
> res
= vNULL
;
3312 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
3315 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3316 if (aglat
->is_single_const ())
3318 struct ipa_agg_jf_item ti
;
3319 ti
.offset
= aglat
->offset
- offset
;
3320 ti
.value
= aglat
->values
->value
;
3326 /* Intersect all values in INTER with single value lattices in PLATS (while
3327 subtracting OFFSET). */
3330 intersect_with_plats (struct ipcp_param_lattices
*plats
,
3331 vec
<ipa_agg_jf_item
> *inter
,
3332 HOST_WIDE_INT offset
)
3334 struct ipcp_agg_lattice
*aglat
;
3335 struct ipa_agg_jf_item
*item
;
3338 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
3344 aglat
= plats
->aggs
;
3345 FOR_EACH_VEC_ELT (*inter
, k
, item
)
3352 if (aglat
->offset
- offset
> item
->offset
)
3354 if (aglat
->offset
- offset
== item
->offset
)
3356 gcc_checking_assert (item
->value
);
3357 if (values_equal_for_ipcp_p (item
->value
, aglat
->values
->value
))
3361 aglat
= aglat
->next
;
3364 item
->value
= NULL_TREE
;
3368 /* Copy agggregate replacement values of NODE (which is an IPA-CP clone) to the
3369 vector result while subtracting OFFSET from the individual value offsets. */
3371 static vec
<ipa_agg_jf_item
>
3372 agg_replacements_to_vector (struct cgraph_node
*node
, int index
,
3373 HOST_WIDE_INT offset
)
3375 struct ipa_agg_replacement_value
*av
;
3376 vec
<ipa_agg_jf_item
> res
= vNULL
;
3378 for (av
= ipa_get_agg_replacements_for_node (node
); av
; av
= av
->next
)
3379 if (av
->index
== index
3380 && (av
->offset
- offset
) >= 0)
3382 struct ipa_agg_jf_item item
;
3383 gcc_checking_assert (av
->value
);
3384 item
.offset
= av
->offset
- offset
;
3385 item
.value
= av
->value
;
3386 res
.safe_push (item
);
3392 /* Intersect all values in INTER with those that we have already scheduled to
3393 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
3394 (while subtracting OFFSET). */
3397 intersect_with_agg_replacements (struct cgraph_node
*node
, int index
,
3398 vec
<ipa_agg_jf_item
> *inter
,
3399 HOST_WIDE_INT offset
)
3401 struct ipa_agg_replacement_value
*srcvals
;
3402 struct ipa_agg_jf_item
*item
;
3405 srcvals
= ipa_get_agg_replacements_for_node (node
);
3412 FOR_EACH_VEC_ELT (*inter
, i
, item
)
3414 struct ipa_agg_replacement_value
*av
;
3418 for (av
= srcvals
; av
; av
= av
->next
)
3420 gcc_checking_assert (av
->value
);
3421 if (av
->index
== index
3422 && av
->offset
- offset
== item
->offset
)
3424 if (values_equal_for_ipcp_p (item
->value
, av
->value
))
3430 item
->value
= NULL_TREE
;
3434 /* Intersect values in INTER with aggregate values that come along edge CS to
3435 parameter number INDEX and return it. If INTER does not actually exist yet,
3436 copy all incoming values to it. If we determine we ended up with no values
3437 whatsoever, return a released vector. */
3439 static vec
<ipa_agg_jf_item
>
3440 intersect_aggregates_with_edge (struct cgraph_edge
*cs
, int index
,
3441 vec
<ipa_agg_jf_item
> inter
)
3443 struct ipa_jump_func
*jfunc
;
3444 jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), index
);
3445 if (jfunc
->type
== IPA_JF_PASS_THROUGH
3446 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
3448 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3449 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
3451 if (caller_info
->ipcp_orig_node
)
3453 struct cgraph_node
*orig_node
= caller_info
->ipcp_orig_node
;
3454 struct ipcp_param_lattices
*orig_plats
;
3455 orig_plats
= ipa_get_parm_lattices (IPA_NODE_REF (orig_node
),
3457 if (agg_pass_through_permissible_p (orig_plats
, jfunc
))
3459 if (!inter
.exists ())
3460 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, 0);
3462 intersect_with_agg_replacements (cs
->caller
, src_idx
,
3473 struct ipcp_param_lattices
*src_plats
;
3474 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
3475 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
3477 /* Currently we do not produce clobber aggregate jump
3478 functions, adjust when we do. */
3479 gcc_checking_assert (!jfunc
->agg
.items
);
3480 if (!inter
.exists ())
3481 inter
= copy_plats_to_inter (src_plats
, 0);
3483 intersect_with_plats (src_plats
, &inter
, 0);
3492 else if (jfunc
->type
== IPA_JF_ANCESTOR
3493 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
3495 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3496 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
3497 struct ipcp_param_lattices
*src_plats
;
3498 HOST_WIDE_INT delta
= ipa_get_jf_ancestor_offset (jfunc
);
3500 if (caller_info
->ipcp_orig_node
)
3502 if (!inter
.exists ())
3503 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, delta
);
3505 intersect_with_agg_replacements (cs
->caller
, src_idx
, &inter
,
3510 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);;
3511 /* Currently we do not produce clobber aggregate jump
3512 functions, adjust when we do. */
3513 gcc_checking_assert (!src_plats
->aggs
|| !jfunc
->agg
.items
);
3514 if (!inter
.exists ())
3515 inter
= copy_plats_to_inter (src_plats
, delta
);
3517 intersect_with_plats (src_plats
, &inter
, delta
);
3520 else if (jfunc
->agg
.items
)
3522 struct ipa_agg_jf_item
*item
;
3525 if (!inter
.exists ())
3526 for (unsigned i
= 0; i
< jfunc
->agg
.items
->length (); i
++)
3527 inter
.safe_push ((*jfunc
->agg
.items
)[i
]);
3529 FOR_EACH_VEC_ELT (inter
, k
, item
)
3532 bool found
= false;;
3537 while ((unsigned) l
< jfunc
->agg
.items
->length ())
3539 struct ipa_agg_jf_item
*ti
;
3540 ti
= &(*jfunc
->agg
.items
)[l
];
3541 if (ti
->offset
> item
->offset
)
3543 if (ti
->offset
== item
->offset
)
3545 gcc_checking_assert (ti
->value
);
3546 if (values_equal_for_ipcp_p (item
->value
,
3560 return vec
<ipa_agg_jf_item
>();
3565 /* Look at edges in CALLERS and collect all known aggregate values that arrive
3566 from all of them. */
3568 static struct ipa_agg_replacement_value
*
3569 find_aggregate_values_for_callers_subset (struct cgraph_node
*node
,
3570 vec
<cgraph_edge
*> callers
)
3572 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
3573 struct ipa_agg_replacement_value
*res
;
3574 struct ipa_agg_replacement_value
**tail
= &res
;
3575 struct cgraph_edge
*cs
;
3576 int i
, j
, count
= ipa_get_param_count (dest_info
);
3578 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3580 int c
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
3585 for (i
= 0; i
< count
; i
++)
3587 struct cgraph_edge
*cs
;
3588 vec
<ipa_agg_jf_item
> inter
= vNULL
;
3589 struct ipa_agg_jf_item
*item
;
3590 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (dest_info
, i
);
3593 /* Among other things, the following check should deal with all by_ref
3595 if (plats
->aggs_bottom
)
3598 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3600 inter
= intersect_aggregates_with_edge (cs
, i
, inter
);
3602 if (!inter
.exists ())
3606 FOR_EACH_VEC_ELT (inter
, j
, item
)
3608 struct ipa_agg_replacement_value
*v
;
3613 v
= ggc_alloc
<ipa_agg_replacement_value
> ();
3615 v
->offset
= item
->offset
;
3616 v
->value
= item
->value
;
3617 v
->by_ref
= plats
->aggs_by_ref
;
3623 if (inter
.exists ())
3630 /* Turn KNOWN_AGGS into a list of aggreate replacement values. */
3632 static struct ipa_agg_replacement_value
*
3633 known_aggs_to_agg_replacement_list (vec
<ipa_agg_jump_function
> known_aggs
)
3635 struct ipa_agg_replacement_value
*res
;
3636 struct ipa_agg_replacement_value
**tail
= &res
;
3637 struct ipa_agg_jump_function
*aggjf
;
3638 struct ipa_agg_jf_item
*item
;
3641 FOR_EACH_VEC_ELT (known_aggs
, i
, aggjf
)
3642 FOR_EACH_VEC_SAFE_ELT (aggjf
->items
, j
, item
)
3644 struct ipa_agg_replacement_value
*v
;
3645 v
= ggc_alloc
<ipa_agg_replacement_value
> ();
3647 v
->offset
= item
->offset
;
3648 v
->value
= item
->value
;
3649 v
->by_ref
= aggjf
->by_ref
;
3657 /* Determine whether CS also brings all scalar values that the NODE is
3661 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge
*cs
,
3662 struct cgraph_node
*node
)
3664 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
3665 int count
= ipa_get_param_count (dest_info
);
3666 struct ipa_node_params
*caller_info
;
3667 struct ipa_edge_args
*args
;
3670 caller_info
= IPA_NODE_REF (cs
->caller
);
3671 args
= IPA_EDGE_REF (cs
);
3672 for (i
= 0; i
< count
; i
++)
3674 struct ipa_jump_func
*jump_func
;
3677 val
= dest_info
->known_csts
[i
];
3681 if (i
>= ipa_get_cs_argument_count (args
))
3683 jump_func
= ipa_get_ith_jump_func (args
, i
);
3684 t
= ipa_value_from_jfunc (caller_info
, jump_func
);
3685 if (!t
|| !values_equal_for_ipcp_p (val
, t
))
3691 /* Determine whether CS also brings all aggregate values that NODE is
3694 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge
*cs
,
3695 struct cgraph_node
*node
)
3697 struct ipa_node_params
*orig_caller_info
= IPA_NODE_REF (cs
->caller
);
3698 struct ipa_node_params
*orig_node_info
;
3699 struct ipa_agg_replacement_value
*aggval
;
3702 aggval
= ipa_get_agg_replacements_for_node (node
);
3706 count
= ipa_get_param_count (IPA_NODE_REF (node
));
3707 ec
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
3709 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
3710 if (aggval
->index
>= ec
)
3713 orig_node_info
= IPA_NODE_REF (IPA_NODE_REF (node
)->ipcp_orig_node
);
3714 if (orig_caller_info
->ipcp_orig_node
)
3715 orig_caller_info
= IPA_NODE_REF (orig_caller_info
->ipcp_orig_node
);
3717 for (i
= 0; i
< count
; i
++)
3719 static vec
<ipa_agg_jf_item
> values
= vec
<ipa_agg_jf_item
>();
3720 struct ipcp_param_lattices
*plats
;
3721 bool interesting
= false;
3722 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
3723 if (aggval
->index
== i
)
3731 plats
= ipa_get_parm_lattices (orig_node_info
, aggval
->index
);
3732 if (plats
->aggs_bottom
)
3735 values
= intersect_aggregates_with_edge (cs
, i
, values
);
3736 if (!values
.exists ())
3739 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
3740 if (aggval
->index
== i
)
3742 struct ipa_agg_jf_item
*item
;
3745 FOR_EACH_VEC_ELT (values
, j
, item
)
3747 && item
->offset
== av
->offset
3748 && values_equal_for_ipcp_p (item
->value
, av
->value
))
3763 /* Given an original NODE and a VAL for which we have already created a
3764 specialized clone, look whether there are incoming edges that still lead
3765 into the old node but now also bring the requested value and also conform to
3766 all other criteria such that they can be redirected the the special node.
3767 This function can therefore redirect the final edge in a SCC. */
3769 template <typename valtype
>
3771 perhaps_add_new_callers (cgraph_node
*node
, ipcp_value
<valtype
> *val
)
3773 ipcp_value_source
<valtype
> *src
;
3774 gcov_type redirected_sum
= 0;
3776 for (src
= val
->sources
; src
; src
= src
->next
)
3778 struct cgraph_edge
*cs
= src
->cs
;
3781 enum availability availability
;
3782 struct cgraph_node
*dst
= cs
->callee
->function_symbol (&availability
);
3783 if ((dst
== node
|| IPA_NODE_REF (dst
)->is_all_contexts_clone
)
3784 && availability
> AVAIL_INTERPOSABLE
3785 && cgraph_edge_brings_value_p (cs
, src
))
3787 if (cgraph_edge_brings_all_scalars_for_node (cs
, val
->spec_node
)
3788 && cgraph_edge_brings_all_agg_vals_for_node (cs
,
3792 fprintf (dump_file
, " - adding an extra caller %s/%i"
3794 xstrdup (cs
->caller
->name ()),
3796 xstrdup (val
->spec_node
->name ()),
3797 val
->spec_node
->order
);
3799 cs
->redirect_callee (val
->spec_node
);
3800 redirected_sum
+= cs
->count
;
3803 cs
= get_next_cgraph_edge_clone (cs
);
3808 update_specialized_profile (val
->spec_node
, node
, redirected_sum
);
3811 /* Return true if KNOWN_CONTEXTS contain at least one useful context. */
3814 known_contexts_useful_p (vec
<ipa_polymorphic_call_context
> known_contexts
)
3816 ipa_polymorphic_call_context
*ctx
;
3819 FOR_EACH_VEC_ELT (known_contexts
, i
, ctx
)
3820 if (!ctx
->useless_p ())
3825 /* Return a copy of KNOWN_CSTS if it is not empty, otherwise return vNULL. */
3827 static vec
<ipa_polymorphic_call_context
>
3828 copy_useful_known_contexts (vec
<ipa_polymorphic_call_context
> known_contexts
)
3830 if (known_contexts_useful_p (known_contexts
))
3831 return known_contexts
.copy ();
3836 /* Copy KNOWN_CSTS and modify the copy according to VAL and INDEX. If
3837 non-empty, replace KNOWN_CONTEXTS with its copy too. */
3840 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
3841 vec
<ipa_polymorphic_call_context
> *known_contexts
,
3842 ipcp_value
<tree
> *val
,
3845 *known_csts
= known_csts
->copy ();
3846 *known_contexts
= copy_useful_known_contexts (*known_contexts
);
3847 (*known_csts
)[index
] = val
->value
;
3850 /* Replace KNOWN_CSTS with its copy. Also copy KNOWN_CONTEXTS and modify the
3851 copy according to VAL and INDEX. */
3854 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
3855 vec
<ipa_polymorphic_call_context
> *known_contexts
,
3856 ipcp_value
<ipa_polymorphic_call_context
> *val
,
3859 *known_csts
= known_csts
->copy ();
3860 *known_contexts
= known_contexts
->copy ();
3861 (*known_contexts
)[index
] = val
->value
;
3864 /* Return true if OFFSET indicates this was not an aggregate value or there is
3865 a replacement equivalent to VALUE, INDEX and OFFSET among those in the
3869 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*aggvals
,
3870 int index
, HOST_WIDE_INT offset
, tree value
)
3877 if (aggvals
->index
== index
3878 && aggvals
->offset
== offset
3879 && values_equal_for_ipcp_p (aggvals
->value
, value
))
3881 aggvals
= aggvals
->next
;
3886 /* Return true if offset is minus one because source of a polymorphic contect
3887 cannot be an aggregate value. */
3890 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*,
3891 int , HOST_WIDE_INT offset
,
3892 ipa_polymorphic_call_context
)
3894 return offset
== -1;
3897 /* Decide wheter to create a special version of NODE for value VAL of parameter
3898 at the given INDEX. If OFFSET is -1, the value is for the parameter itself,
3899 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS,
3900 KNOWN_CONTEXTS and KNOWN_AGGS describe the other already known values. */
3902 template <typename valtype
>
3904 decide_about_value (struct cgraph_node
*node
, int index
, HOST_WIDE_INT offset
,
3905 ipcp_value
<valtype
> *val
, vec
<tree
> known_csts
,
3906 vec
<ipa_polymorphic_call_context
> known_contexts
)
3908 struct ipa_agg_replacement_value
*aggvals
;
3909 int freq_sum
, caller_count
;
3910 gcov_type count_sum
;
3911 vec
<cgraph_edge
*> callers
;
3915 perhaps_add_new_callers (node
, val
);
3918 else if (val
->local_size_cost
+ overall_size
> max_new_size
)
3920 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3921 fprintf (dump_file
, " Ignoring candidate value because "
3922 "max_new_size would be reached with %li.\n",
3923 val
->local_size_cost
+ overall_size
);
3926 else if (!get_info_about_necessary_edges (val
, &freq_sum
, &count_sum
,
3930 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3932 fprintf (dump_file
, " - considering value ");
3933 print_ipcp_constant_value (dump_file
, val
->value
);
3934 fprintf (dump_file
, " for ");
3935 ipa_dump_param (dump_file
, IPA_NODE_REF (node
), index
);
3937 fprintf (dump_file
, ", offset: " HOST_WIDE_INT_PRINT_DEC
, offset
);
3938 fprintf (dump_file
, " (caller_count: %i)\n", caller_count
);
3941 if (!good_cloning_opportunity_p (node
, val
->local_time_benefit
,
3942 freq_sum
, count_sum
,
3943 val
->local_size_cost
)
3944 && !good_cloning_opportunity_p (node
,
3945 val
->local_time_benefit
3946 + val
->prop_time_benefit
,
3947 freq_sum
, count_sum
,
3948 val
->local_size_cost
3949 + val
->prop_size_cost
))
3953 fprintf (dump_file
, " Creating a specialized node of %s/%i.\n",
3954 node
->name (), node
->order
);
3956 callers
= gather_edges_for_value (val
, caller_count
);
3958 modify_known_vectors_with_val (&known_csts
, &known_contexts
, val
, index
);
3961 known_csts
= known_csts
.copy ();
3962 known_contexts
= copy_useful_known_contexts (known_contexts
);
3964 find_more_scalar_values_for_callers_subset (node
, known_csts
, callers
);
3965 find_more_contexts_for_caller_subset (node
, &known_contexts
, callers
);
3966 aggvals
= find_aggregate_values_for_callers_subset (node
, callers
);
3967 gcc_checking_assert (ipcp_val_agg_replacement_ok_p (aggvals
, index
,
3968 offset
, val
->value
));
3969 val
->spec_node
= create_specialized_node (node
, known_csts
, known_contexts
,
3971 overall_size
+= val
->local_size_cost
;
3973 /* TODO: If for some lattice there is only one other known value
3974 left, make a special node for it too. */
3979 /* Decide whether and what specialized clones of NODE should be created. */
3982 decide_whether_version_node (struct cgraph_node
*node
)
3984 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3985 int i
, count
= ipa_get_param_count (info
);
3986 vec
<tree
> known_csts
;
3987 vec
<ipa_polymorphic_call_context
> known_contexts
;
3988 vec
<ipa_agg_jump_function
> known_aggs
= vNULL
;
3994 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3995 fprintf (dump_file
, "\nEvaluating opportunities for %s/%i.\n",
3996 node
->name (), node
->order
);
3998 gather_context_independent_values (info
, &known_csts
, &known_contexts
,
3999 info
->do_clone_for_all_contexts
? &known_aggs
4002 for (i
= 0; i
< count
;i
++)
4004 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4005 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
4006 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
4011 ipcp_value
<tree
> *val
;
4012 for (val
= lat
->values
; val
; val
= val
->next
)
4013 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
4017 if (!plats
->aggs_bottom
)
4019 struct ipcp_agg_lattice
*aglat
;
4020 ipcp_value
<tree
> *val
;
4021 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
4022 if (!aglat
->bottom
&& aglat
->values
4023 /* If the following is false, the one value is in
4025 && (plats
->aggs_contain_variable
4026 || !aglat
->is_single_const ()))
4027 for (val
= aglat
->values
; val
; val
= val
->next
)
4028 ret
|= decide_about_value (node
, i
, aglat
->offset
, val
,
4029 known_csts
, known_contexts
);
4033 && known_contexts
[i
].useless_p ())
4035 ipcp_value
<ipa_polymorphic_call_context
> *val
;
4036 for (val
= ctxlat
->values
; val
; val
= val
->next
)
4037 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
4041 info
= IPA_NODE_REF (node
);
4044 if (info
->do_clone_for_all_contexts
)
4046 struct cgraph_node
*clone
;
4047 vec
<cgraph_edge
*> callers
;
4050 fprintf (dump_file
, " - Creating a specialized node of %s/%i "
4051 "for all known contexts.\n", node
->name (),
4054 callers
= node
->collect_callers ();
4056 if (!known_contexts_useful_p (known_contexts
))
4058 known_contexts
.release ();
4059 known_contexts
= vNULL
;
4061 clone
= create_specialized_node (node
, known_csts
, known_contexts
,
4062 known_aggs_to_agg_replacement_list (known_aggs
),
4064 info
= IPA_NODE_REF (node
);
4065 info
->do_clone_for_all_contexts
= false;
4066 IPA_NODE_REF (clone
)->is_all_contexts_clone
= true;
4067 for (i
= 0; i
< count
; i
++)
4068 vec_free (known_aggs
[i
].items
);
4069 known_aggs
.release ();
4074 known_csts
.release ();
4075 known_contexts
.release ();
4081 /* Transitively mark all callees of NODE within the same SCC as not dead. */
4084 spread_undeadness (struct cgraph_node
*node
)
4086 struct cgraph_edge
*cs
;
4088 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
4089 if (ipa_edge_within_scc (cs
))
4091 struct cgraph_node
*callee
;
4092 struct ipa_node_params
*info
;
4094 callee
= cs
->callee
->function_symbol (NULL
);
4095 info
= IPA_NODE_REF (callee
);
4097 if (info
->node_dead
)
4099 info
->node_dead
= 0;
4100 spread_undeadness (callee
);
4105 /* Return true if NODE has a caller from outside of its SCC that is not
4106 dead. Worker callback for cgraph_for_node_and_aliases. */
4109 has_undead_caller_from_outside_scc_p (struct cgraph_node
*node
,
4110 void *data ATTRIBUTE_UNUSED
)
4112 struct cgraph_edge
*cs
;
4114 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
4115 if (cs
->caller
->thunk
.thunk_p
4116 && cs
->caller
->call_for_symbol_thunks_and_aliases
4117 (has_undead_caller_from_outside_scc_p
, NULL
, true))
4119 else if (!ipa_edge_within_scc (cs
)
4120 && !IPA_NODE_REF (cs
->caller
)->node_dead
)
4126 /* Identify nodes within the same SCC as NODE which are no longer needed
4127 because of new clones and will be removed as unreachable. */
4130 identify_dead_nodes (struct cgraph_node
*node
)
4132 struct cgraph_node
*v
;
4133 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4134 if (v
->will_be_removed_from_program_if_no_direct_calls_p ()
4135 && !v
->call_for_symbol_thunks_and_aliases
4136 (has_undead_caller_from_outside_scc_p
, NULL
, true))
4137 IPA_NODE_REF (v
)->node_dead
= 1;
4139 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4140 if (!IPA_NODE_REF (v
)->node_dead
)
4141 spread_undeadness (v
);
4143 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4145 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4146 if (IPA_NODE_REF (v
)->node_dead
)
4147 fprintf (dump_file
, " Marking node as dead: %s/%i.\n",
4148 v
->name (), v
->order
);
4152 /* The decision stage. Iterate over the topological order of call graph nodes
4153 TOPO and make specialized clones if deemed beneficial. */
4156 ipcp_decision_stage (struct ipa_topo_info
*topo
)
4161 fprintf (dump_file
, "\nIPA decision stage:\n\n");
4163 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
4165 struct cgraph_node
*node
= topo
->order
[i
];
4166 bool change
= false, iterate
= true;
4170 struct cgraph_node
*v
;
4172 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4173 if (v
->has_gimple_body_p ()
4174 && ipcp_versionable_function_p (v
))
4175 iterate
|= decide_whether_version_node (v
);
4180 identify_dead_nodes (node
);
4184 /* The IPCP driver. */
4189 struct cgraph_2edge_hook_list
*edge_duplication_hook_holder
;
4190 struct cgraph_edge_hook_list
*edge_removal_hook_holder
;
4191 struct ipa_topo_info topo
;
4193 ipa_check_create_node_params ();
4194 ipa_check_create_edge_args ();
4195 grow_edge_clone_vectors ();
4196 edge_duplication_hook_holder
=
4197 symtab
->add_edge_duplication_hook (&ipcp_edge_duplication_hook
, NULL
);
4198 edge_removal_hook_holder
=
4199 symtab
->add_edge_removal_hook (&ipcp_edge_removal_hook
, NULL
);
4201 ipcp_cst_values_pool
= create_alloc_pool ("IPA-CP constant values",
4202 sizeof (ipcp_value
<tree
>), 32);
4203 ipcp_poly_ctx_values_pool
= create_alloc_pool
4204 ("IPA-CP polymorphic contexts",
4205 sizeof (ipcp_value
<ipa_polymorphic_call_context
>), 32);
4206 ipcp_sources_pool
= create_alloc_pool ("IPA-CP value sources",
4207 sizeof (ipcp_value_source
<tree
>), 64);
4208 ipcp_agg_lattice_pool
= create_alloc_pool ("IPA_CP aggregate lattices",
4209 sizeof (struct ipcp_agg_lattice
),
4213 fprintf (dump_file
, "\nIPA structures before propagation:\n");
4214 if (dump_flags
& TDF_DETAILS
)
4215 ipa_print_all_params (dump_file
);
4216 ipa_print_all_jump_functions (dump_file
);
4219 /* Topological sort. */
4220 build_toporder_info (&topo
);
4221 /* Do the interprocedural propagation. */
4222 ipcp_propagate_stage (&topo
);
4223 /* Decide what constant propagation and cloning should be performed. */
4224 ipcp_decision_stage (&topo
);
4226 /* Free all IPCP structures. */
4227 free_toporder_info (&topo
);
4228 next_edge_clone
.release ();
4229 symtab
->remove_edge_removal_hook (edge_removal_hook_holder
);
4230 symtab
->remove_edge_duplication_hook (edge_duplication_hook_holder
);
4231 ipa_free_all_structures_after_ipa_cp ();
4233 fprintf (dump_file
, "\nIPA constant propagation end\n");
4237 /* Initialization and computation of IPCP data structures. This is the initial
4238 intraprocedural analysis of functions, which gathers information to be
4239 propagated later on. */
4242 ipcp_generate_summary (void)
4244 struct cgraph_node
*node
;
4247 fprintf (dump_file
, "\nIPA constant propagation start:\n");
4248 ipa_register_cgraph_hooks ();
4250 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
4252 node
->local
.versionable
4253 = tree_versionable_function_p (node
->decl
);
4254 ipa_analyze_node (node
);
4258 /* Write ipcp summary for nodes in SET. */
4261 ipcp_write_summary (void)
4263 ipa_prop_write_jump_functions ();
4266 /* Read ipcp summary. */
4269 ipcp_read_summary (void)
4271 ipa_prop_read_jump_functions ();
4276 const pass_data pass_data_ipa_cp
=
4278 IPA_PASS
, /* type */
4280 OPTGROUP_NONE
, /* optinfo_flags */
4281 TV_IPA_CONSTANT_PROP
, /* tv_id */
4282 0, /* properties_required */
4283 0, /* properties_provided */
4284 0, /* properties_destroyed */
4285 0, /* todo_flags_start */
4286 ( TODO_dump_symtab
| TODO_remove_functions
), /* todo_flags_finish */
4289 class pass_ipa_cp
: public ipa_opt_pass_d
4292 pass_ipa_cp (gcc::context
*ctxt
)
4293 : ipa_opt_pass_d (pass_data_ipa_cp
, ctxt
,
4294 ipcp_generate_summary
, /* generate_summary */
4295 ipcp_write_summary
, /* write_summary */
4296 ipcp_read_summary
, /* read_summary */
4297 ipa_prop_write_all_agg_replacement
, /*
4298 write_optimization_summary */
4299 ipa_prop_read_all_agg_replacement
, /*
4300 read_optimization_summary */
4301 NULL
, /* stmt_fixup */
4302 0, /* function_transform_todo_flags_start */
4303 ipcp_transform_function
, /* function_transform */
4304 NULL
) /* variable_transform */
4307 /* opt_pass methods: */
4308 virtual bool gate (function
*)
4310 /* FIXME: We should remove the optimize check after we ensure we never run
4311 IPA passes when not optimizing. */
4312 return (flag_ipa_cp
&& optimize
) || in_lto_p
;
4315 virtual unsigned int execute (function
*) { return ipcp_driver (); }
4317 }; // class pass_ipa_cp
4322 make_pass_ipa_cp (gcc::context
*ctxt
)
4324 return new pass_ipa_cp (ctxt
);
4327 /* Reset all state within ipa-cp.c so that we can rerun the compiler
4328 within the same process. For use by toplev::finalize. */
4331 ipa_cp_c_finalize (void)