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 (!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 gcc_checking_assert (!flag_ipa_cp
);
909 lat
= ipa_get_scalar_lat (info
, idx
);
910 if (!lat
->is_single_const ())
912 input
= lat
->values
->value
;
918 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
919 return ipa_get_jf_pass_through_result (jfunc
, input
);
921 return ipa_get_jf_ancestor_result (jfunc
, input
);
927 /* Determie whether JFUNC evaluates to single known polymorphic context, given
928 that INFO describes the caller node or the one it is inlined to, CS is the
929 call graph edge corresponding to JFUNC and CSIDX index of the described
932 ipa_polymorphic_call_context
933 ipa_context_from_jfunc (ipa_node_params
*info
, cgraph_edge
*cs
, int csidx
,
934 ipa_jump_func
*jfunc
)
936 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
937 ipa_polymorphic_call_context ctx
;
938 ipa_polymorphic_call_context
*edge_ctx
939 = cs
? ipa_get_ith_polymorhic_call_context (args
, csidx
) : NULL
;
941 if (edge_ctx
&& !edge_ctx
->useless_p ())
944 if (jfunc
->type
== IPA_JF_PASS_THROUGH
945 || jfunc
->type
== IPA_JF_ANCESTOR
)
947 ipa_polymorphic_call_context srcctx
;
949 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
951 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
952 || !ipa_get_jf_pass_through_type_preserved (jfunc
))
954 srcidx
= ipa_get_jf_pass_through_formal_id (jfunc
);
958 if (!ipa_get_jf_ancestor_type_preserved (jfunc
))
960 srcidx
= ipa_get_jf_ancestor_formal_id (jfunc
);
962 if (info
->ipcp_orig_node
)
964 if (info
->known_contexts
.exists ())
965 srcctx
= info
->known_contexts
[srcidx
];
971 gcc_checking_assert (!flag_ipa_cp
);
974 ipcp_lattice
<ipa_polymorphic_call_context
> *lat
;
975 lat
= ipa_get_poly_ctx_lat (info
, srcidx
);
976 if (!lat
->is_single_const ())
978 srcctx
= lat
->values
->value
;
980 if (srcctx
.useless_p ())
982 if (jfunc
->type
== IPA_JF_ANCESTOR
)
983 srcctx
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
984 ctx
.combine_with (srcctx
);
990 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
991 bottom, not containing a variable component and without any known value at
995 ipcp_verify_propagated_values (void)
997 struct cgraph_node
*node
;
999 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
1001 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1002 int i
, count
= ipa_get_param_count (info
);
1004 for (i
= 0; i
< count
; i
++)
1006 ipcp_lattice
<tree
> *lat
= ipa_get_scalar_lat (info
, i
);
1009 && !lat
->contains_variable
1010 && lat
->values_count
== 0)
1014 symtab_node::dump_table (dump_file
);
1015 fprintf (dump_file
, "\nIPA lattices after constant "
1016 "propagation, before gcc_unreachable:\n");
1017 print_all_lattices (dump_file
, true, false);
1026 /* Return true iff X and Y should be considered equal values by IPA-CP. */
1029 values_equal_for_ipcp_p (tree x
, tree y
)
1031 gcc_checking_assert (x
!= NULL_TREE
&& y
!= NULL_TREE
);
1036 if (TREE_CODE (x
) == ADDR_EXPR
1037 && TREE_CODE (y
) == ADDR_EXPR
1038 && TREE_CODE (TREE_OPERAND (x
, 0)) == CONST_DECL
1039 && TREE_CODE (TREE_OPERAND (y
, 0)) == CONST_DECL
)
1040 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x
, 0)),
1041 DECL_INITIAL (TREE_OPERAND (y
, 0)), 0);
1043 return operand_equal_p (x
, y
, 0);
1046 /* Return true iff X and Y should be considered equal contexts by IPA-CP. */
1049 values_equal_for_ipcp_p (ipa_polymorphic_call_context x
,
1050 ipa_polymorphic_call_context y
)
1052 return x
.equal_to (y
);
1056 /* Add a new value source to the value represented by THIS, marking that a
1057 value comes from edge CS and (if the underlying jump function is a
1058 pass-through or an ancestor one) from a caller value SRC_VAL of a caller
1059 parameter described by SRC_INDEX. OFFSET is negative if the source was the
1060 scalar value of the parameter itself or the offset within an aggregate. */
1062 template <typename valtype
>
1064 ipcp_value
<valtype
>::add_source (cgraph_edge
*cs
, ipcp_value
*src_val
,
1065 int src_idx
, HOST_WIDE_INT offset
)
1067 ipcp_value_source
<valtype
> *src
;
1069 src
= new (pool_alloc (ipcp_sources_pool
)) ipcp_value_source
<valtype
>;
1070 src
->offset
= offset
;
1073 src
->index
= src_idx
;
1075 src
->next
= sources
;
1079 /* Allocate a new ipcp_value holding a tree constant, initialize its value to
1080 SOURCE and clear all other fields. */
1082 static ipcp_value
<tree
> *
1083 allocate_and_init_ipcp_value (tree source
)
1085 ipcp_value
<tree
> *val
;
1087 val
= new (pool_alloc (ipcp_cst_values_pool
)) ipcp_value
<tree
>;
1088 memset (val
, 0, sizeof (*val
));
1089 val
->value
= source
;
1093 /* Allocate a new ipcp_value holding a polymorphic context, initialize its
1094 value to SOURCE and clear all other fields. */
1096 static ipcp_value
<ipa_polymorphic_call_context
> *
1097 allocate_and_init_ipcp_value (ipa_polymorphic_call_context source
)
1099 ipcp_value
<ipa_polymorphic_call_context
> *val
;
1101 val
= new (pool_alloc (ipcp_poly_ctx_values_pool
))
1102 ipcp_value
<ipa_polymorphic_call_context
>;
1103 memset (val
, 0, sizeof (*val
));
1104 val
->value
= source
;
1108 /* Try to add NEWVAL to LAT, potentially creating a new ipcp_value for it. CS,
1109 SRC_VAL SRC_INDEX and OFFSET are meant for add_source and have the same
1110 meaning. OFFSET -1 means the source is scalar and not a part of an
1113 template <typename valtype
>
1115 ipcp_lattice
<valtype
>::add_value (valtype newval
, cgraph_edge
*cs
,
1116 ipcp_value
<valtype
> *src_val
,
1117 int src_idx
, HOST_WIDE_INT offset
)
1119 ipcp_value
<valtype
> *val
;
1124 for (val
= values
; val
; val
= val
->next
)
1125 if (values_equal_for_ipcp_p (val
->value
, newval
))
1127 if (ipa_edge_within_scc (cs
))
1129 ipcp_value_source
<valtype
> *s
;
1130 for (s
= val
->sources
; s
; s
= s
->next
)
1137 val
->add_source (cs
, src_val
, src_idx
, offset
);
1141 if (values_count
== PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE
))
1143 /* We can only free sources, not the values themselves, because sources
1144 of other values in this this SCC might point to them. */
1145 for (val
= values
; val
; val
= val
->next
)
1147 while (val
->sources
)
1149 ipcp_value_source
<valtype
> *src
= val
->sources
;
1150 val
->sources
= src
->next
;
1151 pool_free (ipcp_sources_pool
, src
);
1156 return set_to_bottom ();
1160 val
= allocate_and_init_ipcp_value (newval
);
1161 val
->add_source (cs
, src_val
, src_idx
, offset
);
1167 /* Propagate values through a pass-through jump function JFUNC associated with
1168 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1169 is the index of the source parameter. */
1172 propagate_vals_accross_pass_through (cgraph_edge
*cs
,
1173 ipa_jump_func
*jfunc
,
1174 ipcp_lattice
<tree
> *src_lat
,
1175 ipcp_lattice
<tree
> *dest_lat
,
1178 ipcp_value
<tree
> *src_val
;
1181 /* Do not create new values when propagating within an SCC because if there
1182 are arithmetic functions with circular dependencies, there is infinite
1183 number of them and we would just make lattices bottom. */
1184 if ((ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1185 && ipa_edge_within_scc (cs
))
1186 ret
= dest_lat
->set_contains_variable ();
1188 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1190 tree cstval
= ipa_get_jf_pass_through_result (jfunc
, src_val
->value
);
1193 ret
|= dest_lat
->add_value (cstval
, cs
, src_val
, src_idx
);
1195 ret
|= dest_lat
->set_contains_variable ();
1201 /* Propagate values through an ancestor jump function JFUNC associated with
1202 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1203 is the index of the source parameter. */
1206 propagate_vals_accross_ancestor (struct cgraph_edge
*cs
,
1207 struct ipa_jump_func
*jfunc
,
1208 ipcp_lattice
<tree
> *src_lat
,
1209 ipcp_lattice
<tree
> *dest_lat
,
1212 ipcp_value
<tree
> *src_val
;
1215 if (ipa_edge_within_scc (cs
))
1216 return dest_lat
->set_contains_variable ();
1218 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1220 tree t
= ipa_get_jf_ancestor_result (jfunc
, src_val
->value
);
1223 ret
|= dest_lat
->add_value (t
, cs
, src_val
, src_idx
);
1225 ret
|= dest_lat
->set_contains_variable ();
1231 /* Propagate scalar values across jump function JFUNC that is associated with
1232 edge CS and put the values into DEST_LAT. */
1235 propagate_scalar_accross_jump_function (struct cgraph_edge
*cs
,
1236 struct ipa_jump_func
*jfunc
,
1237 ipcp_lattice
<tree
> *dest_lat
)
1239 if (dest_lat
->bottom
)
1242 if (jfunc
->type
== IPA_JF_CONST
)
1244 tree val
= ipa_get_jf_constant (jfunc
);
1245 return dest_lat
->add_value (val
, cs
, NULL
, 0);
1247 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1248 || jfunc
->type
== IPA_JF_ANCESTOR
)
1250 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1251 ipcp_lattice
<tree
> *src_lat
;
1255 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1256 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1258 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1260 src_lat
= ipa_get_scalar_lat (caller_info
, src_idx
);
1261 if (src_lat
->bottom
)
1262 return dest_lat
->set_contains_variable ();
1264 /* If we would need to clone the caller and cannot, do not propagate. */
1265 if (!ipcp_versionable_function_p (cs
->caller
)
1266 && (src_lat
->contains_variable
1267 || (src_lat
->values_count
> 1)))
1268 return dest_lat
->set_contains_variable ();
1270 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1271 ret
= propagate_vals_accross_pass_through (cs
, jfunc
, src_lat
,
1274 ret
= propagate_vals_accross_ancestor (cs
, jfunc
, src_lat
, dest_lat
,
1277 if (src_lat
->contains_variable
)
1278 ret
|= dest_lat
->set_contains_variable ();
1283 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1284 use it for indirect inlining), we should propagate them too. */
1285 return dest_lat
->set_contains_variable ();
1288 /* Propagate scalar values across jump function JFUNC that is associated with
1289 edge CS and describes argument IDX and put the values into DEST_LAT. */
1292 propagate_context_accross_jump_function (cgraph_edge
*cs
,
1293 ipa_jump_func
*jfunc
, int idx
,
1294 ipcp_lattice
<ipa_polymorphic_call_context
> *dest_lat
)
1296 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
1297 if (dest_lat
->bottom
)
1300 bool added_sth
= false;
1302 ipa_polymorphic_call_context edge_ctx
, *edge_ctx_ptr
1303 = ipa_get_ith_polymorhic_call_context (args
, idx
);
1307 edge_ctx
= *edge_ctx_ptr
;
1308 edge_ctx
.clear_speculation ();
1311 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1312 || jfunc
->type
== IPA_JF_ANCESTOR
)
1314 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1316 ipcp_lattice
<ipa_polymorphic_call_context
> *src_lat
;
1318 /* TODO: Once we figure out how to propagate speculations, it will
1319 probably be a good idea to switch to speculation if type_preserved is
1320 not set instead of punting. */
1321 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1323 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
1324 || !ipa_get_jf_pass_through_type_preserved (jfunc
))
1326 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1330 if (!ipa_get_jf_ancestor_type_preserved (jfunc
))
1332 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1335 src_lat
= ipa_get_poly_ctx_lat (caller_info
, src_idx
);
1336 /* If we would need to clone the caller and cannot, do not propagate. */
1337 if (!ipcp_versionable_function_p (cs
->caller
)
1338 && (src_lat
->contains_variable
1339 || (src_lat
->values_count
> 1)))
1341 if (src_lat
->contains_variable
)
1342 ret
|= dest_lat
->set_contains_variable ();
1344 ipcp_value
<ipa_polymorphic_call_context
> *src_val
;
1345 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1347 ipa_polymorphic_call_context cur
= src_val
->value
;
1348 if (jfunc
->type
== IPA_JF_ANCESTOR
)
1349 cur
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
1350 /* TODO: Perhaps attempt to look up some used OTR type? */
1351 cur
.clear_speculation ();
1352 if (!edge_ctx
.useless_p ())
1353 cur
.combine_with (edge_ctx
);
1354 if (!cur
.useless_p ())
1356 ret
|= dest_lat
->add_value (cur
, cs
, src_val
, src_idx
);
1366 if (!edge_ctx
.useless_p ())
1367 ret
|= dest_lat
->add_value (edge_ctx
, cs
);
1369 ret
|= dest_lat
->set_contains_variable ();
1375 /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
1376 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
1377 other cases, return false). If there are no aggregate items, set
1378 aggs_by_ref to NEW_AGGS_BY_REF. */
1381 set_check_aggs_by_ref (struct ipcp_param_lattices
*dest_plats
,
1382 bool new_aggs_by_ref
)
1384 if (dest_plats
->aggs
)
1386 if (dest_plats
->aggs_by_ref
!= new_aggs_by_ref
)
1388 set_agg_lats_to_bottom (dest_plats
);
1393 dest_plats
->aggs_by_ref
= new_aggs_by_ref
;
1397 /* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
1398 already existing lattice for the given OFFSET and SIZE, marking all skipped
1399 lattices as containing variable and checking for overlaps. If there is no
1400 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
1401 it with offset, size and contains_variable to PRE_EXISTING, and return true,
1402 unless there are too many already. If there are two many, return false. If
1403 there are overlaps turn whole DEST_PLATS to bottom and return false. If any
1404 skipped lattices were newly marked as containing variable, set *CHANGE to
1408 merge_agg_lats_step (struct ipcp_param_lattices
*dest_plats
,
1409 HOST_WIDE_INT offset
, HOST_WIDE_INT val_size
,
1410 struct ipcp_agg_lattice
***aglat
,
1411 bool pre_existing
, bool *change
)
1413 gcc_checking_assert (offset
>= 0);
1415 while (**aglat
&& (**aglat
)->offset
< offset
)
1417 if ((**aglat
)->offset
+ (**aglat
)->size
> offset
)
1419 set_agg_lats_to_bottom (dest_plats
);
1422 *change
|= (**aglat
)->set_contains_variable ();
1423 *aglat
= &(**aglat
)->next
;
1426 if (**aglat
&& (**aglat
)->offset
== offset
)
1428 if ((**aglat
)->size
!= val_size
1430 && (**aglat
)->next
->offset
< offset
+ val_size
))
1432 set_agg_lats_to_bottom (dest_plats
);
1435 gcc_checking_assert (!(**aglat
)->next
1436 || (**aglat
)->next
->offset
>= offset
+ val_size
);
1441 struct ipcp_agg_lattice
*new_al
;
1443 if (**aglat
&& (**aglat
)->offset
< offset
+ val_size
)
1445 set_agg_lats_to_bottom (dest_plats
);
1448 if (dest_plats
->aggs_count
== PARAM_VALUE (PARAM_IPA_MAX_AGG_ITEMS
))
1450 dest_plats
->aggs_count
++;
1451 new_al
= (struct ipcp_agg_lattice
*) pool_alloc (ipcp_agg_lattice_pool
);
1452 memset (new_al
, 0, sizeof (*new_al
));
1454 new_al
->offset
= offset
;
1455 new_al
->size
= val_size
;
1456 new_al
->contains_variable
= pre_existing
;
1458 new_al
->next
= **aglat
;
1464 /* Set all AGLAT and all other aggregate lattices reachable by next pointers as
1465 containing an unknown value. */
1468 set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice
*aglat
)
1473 ret
|= aglat
->set_contains_variable ();
1474 aglat
= aglat
->next
;
1479 /* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
1480 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source
1481 parameter used for lattice value sources. Return true if DEST_PLATS changed
1485 merge_aggregate_lattices (struct cgraph_edge
*cs
,
1486 struct ipcp_param_lattices
*dest_plats
,
1487 struct ipcp_param_lattices
*src_plats
,
1488 int src_idx
, HOST_WIDE_INT offset_delta
)
1490 bool pre_existing
= dest_plats
->aggs
!= NULL
;
1491 struct ipcp_agg_lattice
**dst_aglat
;
1494 if (set_check_aggs_by_ref (dest_plats
, src_plats
->aggs_by_ref
))
1496 if (src_plats
->aggs_bottom
)
1497 return set_agg_lats_contain_variable (dest_plats
);
1498 if (src_plats
->aggs_contain_variable
)
1499 ret
|= set_agg_lats_contain_variable (dest_plats
);
1500 dst_aglat
= &dest_plats
->aggs
;
1502 for (struct ipcp_agg_lattice
*src_aglat
= src_plats
->aggs
;
1504 src_aglat
= src_aglat
->next
)
1506 HOST_WIDE_INT new_offset
= src_aglat
->offset
- offset_delta
;
1510 if (merge_agg_lats_step (dest_plats
, new_offset
, src_aglat
->size
,
1511 &dst_aglat
, pre_existing
, &ret
))
1513 struct ipcp_agg_lattice
*new_al
= *dst_aglat
;
1515 dst_aglat
= &(*dst_aglat
)->next
;
1516 if (src_aglat
->bottom
)
1518 ret
|= new_al
->set_contains_variable ();
1521 if (src_aglat
->contains_variable
)
1522 ret
|= new_al
->set_contains_variable ();
1523 for (ipcp_value
<tree
> *val
= src_aglat
->values
;
1526 ret
|= new_al
->add_value (val
->value
, cs
, val
, src_idx
,
1529 else if (dest_plats
->aggs_bottom
)
1532 ret
|= set_chain_of_aglats_contains_variable (*dst_aglat
);
1536 /* Determine whether there is anything to propagate FROM SRC_PLATS through a
1537 pass-through JFUNC and if so, whether it has conform and conforms to the
1538 rules about propagating values passed by reference. */
1541 agg_pass_through_permissible_p (struct ipcp_param_lattices
*src_plats
,
1542 struct ipa_jump_func
*jfunc
)
1544 return src_plats
->aggs
1545 && (!src_plats
->aggs_by_ref
1546 || ipa_get_jf_pass_through_agg_preserved (jfunc
));
1549 /* Propagate scalar values across jump function JFUNC that is associated with
1550 edge CS and put the values into DEST_LAT. */
1553 propagate_aggs_accross_jump_function (struct cgraph_edge
*cs
,
1554 struct ipa_jump_func
*jfunc
,
1555 struct ipcp_param_lattices
*dest_plats
)
1559 if (dest_plats
->aggs_bottom
)
1562 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1563 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
1565 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1566 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1567 struct ipcp_param_lattices
*src_plats
;
1569 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
1570 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
1572 /* Currently we do not produce clobber aggregate jump
1573 functions, replace with merging when we do. */
1574 gcc_assert (!jfunc
->agg
.items
);
1575 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
,
1579 ret
|= set_agg_lats_contain_variable (dest_plats
);
1581 else if (jfunc
->type
== IPA_JF_ANCESTOR
1582 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
1584 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1585 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1586 struct ipcp_param_lattices
*src_plats
;
1588 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
1589 if (src_plats
->aggs
&& src_plats
->aggs_by_ref
)
1591 /* Currently we do not produce clobber aggregate jump
1592 functions, replace with merging when we do. */
1593 gcc_assert (!jfunc
->agg
.items
);
1594 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
, src_idx
,
1595 ipa_get_jf_ancestor_offset (jfunc
));
1597 else if (!src_plats
->aggs_by_ref
)
1598 ret
|= set_agg_lats_to_bottom (dest_plats
);
1600 ret
|= set_agg_lats_contain_variable (dest_plats
);
1602 else if (jfunc
->agg
.items
)
1604 bool pre_existing
= dest_plats
->aggs
!= NULL
;
1605 struct ipcp_agg_lattice
**aglat
= &dest_plats
->aggs
;
1606 struct ipa_agg_jf_item
*item
;
1609 if (set_check_aggs_by_ref (dest_plats
, jfunc
->agg
.by_ref
))
1612 FOR_EACH_VEC_ELT (*jfunc
->agg
.items
, i
, item
)
1614 HOST_WIDE_INT val_size
;
1616 if (item
->offset
< 0)
1618 gcc_checking_assert (is_gimple_ip_invariant (item
->value
));
1619 val_size
= tree_to_uhwi (TYPE_SIZE (TREE_TYPE (item
->value
)));
1621 if (merge_agg_lats_step (dest_plats
, item
->offset
, val_size
,
1622 &aglat
, pre_existing
, &ret
))
1624 ret
|= (*aglat
)->add_value (item
->value
, cs
, NULL
, 0, 0);
1625 aglat
= &(*aglat
)->next
;
1627 else if (dest_plats
->aggs_bottom
)
1631 ret
|= set_chain_of_aglats_contains_variable (*aglat
);
1634 ret
|= set_agg_lats_contain_variable (dest_plats
);
1639 /* Propagate constants from the caller to the callee of CS. INFO describes the
1643 propagate_constants_accross_call (struct cgraph_edge
*cs
)
1645 struct ipa_node_params
*callee_info
;
1646 enum availability availability
;
1647 struct cgraph_node
*callee
, *alias_or_thunk
;
1648 struct ipa_edge_args
*args
;
1650 int i
, args_count
, parms_count
;
1652 callee
= cs
->callee
->function_symbol (&availability
);
1653 if (!callee
->definition
)
1655 gcc_checking_assert (callee
->has_gimple_body_p ());
1656 callee_info
= IPA_NODE_REF (callee
);
1658 args
= IPA_EDGE_REF (cs
);
1659 args_count
= ipa_get_cs_argument_count (args
);
1660 parms_count
= ipa_get_param_count (callee_info
);
1661 if (parms_count
== 0)
1664 /* No propagation through instrumentation thunks is available yet.
1665 It should be possible with proper mapping of call args and
1666 instrumented callee params in the propagation loop below. But
1667 this case mostly occurs when legacy code calls instrumented code
1668 and it is not a primary target for optimizations.
1669 We detect instrumentation thunks in aliases and thunks chain by
1670 checking instrumentation_clone flag for chain source and target.
1671 Going through instrumentation thunks we always have it changed
1672 from 0 to 1 and all other nodes do not change it. */
1673 if (!cs
->callee
->instrumentation_clone
1674 && callee
->instrumentation_clone
)
1676 for (i
= 0; i
< parms_count
; i
++)
1677 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
1682 /* If this call goes through a thunk we must not propagate to the first (0th)
1683 parameter. However, we might need to uncover a thunk from below a series
1684 of aliases first. */
1685 alias_or_thunk
= cs
->callee
;
1686 while (alias_or_thunk
->alias
)
1687 alias_or_thunk
= alias_or_thunk
->get_alias_target ();
1688 if (alias_or_thunk
->thunk
.thunk_p
)
1690 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
1697 for (; (i
< args_count
) && (i
< parms_count
); i
++)
1699 struct ipa_jump_func
*jump_func
= ipa_get_ith_jump_func (args
, i
);
1700 struct ipcp_param_lattices
*dest_plats
;
1702 dest_plats
= ipa_get_parm_lattices (callee_info
, i
);
1703 if (availability
== AVAIL_INTERPOSABLE
)
1704 ret
|= set_all_contains_variable (dest_plats
);
1707 ret
|= propagate_scalar_accross_jump_function (cs
, jump_func
,
1708 &dest_plats
->itself
);
1709 ret
|= propagate_context_accross_jump_function (cs
, jump_func
, i
,
1710 &dest_plats
->ctxlat
);
1711 ret
|= propagate_aggs_accross_jump_function (cs
, jump_func
,
1715 for (; i
< parms_count
; i
++)
1716 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
, i
));
1721 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
1722 KNOWN_CONTEXTS, KNOWN_AGGS or AGG_REPS return the destination. The latter
1723 three can be NULL. If AGG_REPS is not NULL, KNOWN_AGGS is ignored. */
1726 ipa_get_indirect_edge_target_1 (struct cgraph_edge
*ie
,
1727 vec
<tree
> known_csts
,
1728 vec
<ipa_polymorphic_call_context
> known_contexts
,
1729 vec
<ipa_agg_jump_function_p
> known_aggs
,
1730 struct ipa_agg_replacement_value
*agg_reps
)
1732 int param_index
= ie
->indirect_info
->param_index
;
1733 HOST_WIDE_INT anc_offset
;
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 (!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
1793 && !ie
->indirect_info
->vptr_changed
)
1797 if (agg_reps
->index
== param_index
1798 && agg_reps
->offset
== ie
->indirect_info
->offset
1799 && agg_reps
->by_ref
)
1801 t
= agg_reps
->value
;
1804 agg_reps
= agg_reps
->next
;
1808 /* Try to work out value of virtual table pointer value in known
1809 aggregate values. */
1810 if (!t
&& known_aggs
.length () > (unsigned int) param_index
1811 && !ie
->indirect_info
->by_ref
1812 && !ie
->indirect_info
->vptr_changed
)
1814 struct ipa_agg_jump_function
*agg
;
1815 agg
= known_aggs
[param_index
];
1816 t
= ipa_find_agg_cst_for_param (agg
, ie
->indirect_info
->offset
,
1820 /* If we found the virtual table pointer, lookup the target. */
1824 unsigned HOST_WIDE_INT offset
;
1825 if (vtable_pointer_value_to_vtable (t
, &vtable
, &offset
))
1827 target
= gimple_get_virt_method_for_vtable (ie
->indirect_info
->otr_token
,
1831 if ((TREE_CODE (TREE_TYPE (target
)) == FUNCTION_TYPE
1832 && DECL_FUNCTION_CODE (target
) == BUILT_IN_UNREACHABLE
)
1833 || !possible_polymorphic_call_target_p
1834 (ie
, cgraph_node::get (target
)))
1835 target
= ipa_impossible_devirt_target (ie
, target
);
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
];
1853 ipa_polymorphic_call_context ctx2
= ipa_polymorphic_call_context
1854 (t
, ie
->indirect_info
->otr_type
, anc_offset
);
1855 if (!ctx2
.useless_p ())
1856 context
.combine_with (ctx2
, ie
->indirect_info
->otr_type
);
1860 context
= ipa_polymorphic_call_context (t
, ie
->indirect_info
->otr_type
,
1865 vec
<cgraph_node
*>targets
;
1868 targets
= possible_polymorphic_call_targets
1869 (ie
->indirect_info
->otr_type
,
1870 ie
->indirect_info
->otr_token
,
1872 if (!final
|| targets
.length () > 1)
1874 if (targets
.length () == 1)
1875 target
= targets
[0]->decl
;
1877 target
= ipa_impossible_devirt_target (ie
, NULL_TREE
);
1879 if (target
&& !possible_polymorphic_call_target_p (ie
,
1880 cgraph_node::get (target
)))
1881 target
= ipa_impossible_devirt_target (ie
, target
);
1887 /* If an indirect edge IE can be turned into a direct one based on KNOWN_CSTS,
1888 KNOWN_CONTEXTS (which can be vNULL) or KNOWN_AGGS (which also can be vNULL)
1889 return the destination. */
1892 ipa_get_indirect_edge_target (struct cgraph_edge
*ie
,
1893 vec
<tree
> known_csts
,
1894 vec
<ipa_polymorphic_call_context
> known_contexts
,
1895 vec
<ipa_agg_jump_function_p
> known_aggs
)
1897 return ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
1901 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
1902 and KNOWN_CONTEXTS. */
1905 devirtualization_time_bonus (struct cgraph_node
*node
,
1906 vec
<tree
> known_csts
,
1907 vec
<ipa_polymorphic_call_context
> known_contexts
,
1908 vec
<ipa_agg_jump_function_p
> known_aggs
)
1910 struct cgraph_edge
*ie
;
1913 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
1915 struct cgraph_node
*callee
;
1916 struct inline_summary
*isummary
;
1917 enum availability avail
;
1920 target
= ipa_get_indirect_edge_target (ie
, known_csts
, known_contexts
,
1925 /* Only bare minimum benefit for clearly un-inlineable targets. */
1927 callee
= cgraph_node::get (target
);
1928 if (!callee
|| !callee
->definition
)
1930 callee
= callee
->function_symbol (&avail
);
1931 if (avail
< AVAIL_AVAILABLE
)
1933 isummary
= inline_summary (callee
);
1934 if (!isummary
->inlinable
)
1937 /* FIXME: The values below need re-considering and perhaps also
1938 integrating into the cost metrics, at lest in some very basic way. */
1939 if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 4)
1941 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 2)
1943 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
1944 || DECL_DECLARED_INLINE_P (callee
->decl
))
1951 /* Return time bonus incurred because of HINTS. */
1954 hint_time_bonus (inline_hints hints
)
1957 if (hints
& (INLINE_HINT_loop_iterations
| INLINE_HINT_loop_stride
))
1958 result
+= PARAM_VALUE (PARAM_IPA_CP_LOOP_HINT_BONUS
);
1959 if (hints
& INLINE_HINT_array_index
)
1960 result
+= PARAM_VALUE (PARAM_IPA_CP_ARRAY_INDEX_HINT_BONUS
);
1964 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
1965 and SIZE_COST and with the sum of frequencies of incoming edges to the
1966 potential new clone in FREQUENCIES. */
1969 good_cloning_opportunity_p (struct cgraph_node
*node
, int time_benefit
,
1970 int freq_sum
, gcov_type count_sum
, int size_cost
)
1972 if (time_benefit
== 0
1973 || !flag_ipa_cp_clone
1974 || !optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node
->decl
)))
1977 gcc_assert (size_cost
> 0);
1981 int factor
= (count_sum
* 1000) / max_count
;
1982 int64_t evaluation
= (((int64_t) time_benefit
* factor
)
1985 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1986 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
1987 "size: %i, count_sum: " HOST_WIDE_INT_PRINT_DEC
1988 ") -> evaluation: " "%"PRId64
1989 ", threshold: %i\n",
1990 time_benefit
, size_cost
, (HOST_WIDE_INT
) count_sum
,
1991 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
1993 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
1997 int64_t evaluation
= (((int64_t) time_benefit
* freq_sum
)
2000 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2001 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
2002 "size: %i, freq_sum: %i) -> evaluation: "
2003 "%"PRId64
", threshold: %i\n",
2004 time_benefit
, size_cost
, freq_sum
, evaluation
,
2005 PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
2007 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
2011 /* Return all context independent values from aggregate lattices in PLATS in a
2012 vector. Return NULL if there are none. */
2014 static vec
<ipa_agg_jf_item
, va_gc
> *
2015 context_independent_aggregate_values (struct ipcp_param_lattices
*plats
)
2017 vec
<ipa_agg_jf_item
, va_gc
> *res
= NULL
;
2019 if (plats
->aggs_bottom
2020 || plats
->aggs_contain_variable
2021 || plats
->aggs_count
== 0)
2024 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
;
2026 aglat
= aglat
->next
)
2027 if (aglat
->is_single_const ())
2029 struct ipa_agg_jf_item item
;
2030 item
.offset
= aglat
->offset
;
2031 item
.value
= aglat
->values
->value
;
2032 vec_safe_push (res
, item
);
2037 /* Allocate KNOWN_CSTS, KNOWN_CONTEXTS and, if non-NULL, KNOWN_AGGS and
2038 populate them with values of parameters that are known independent of the
2039 context. INFO describes the function. If REMOVABLE_PARAMS_COST is
2040 non-NULL, the movement cost of all removable parameters will be stored in
2044 gather_context_independent_values (struct ipa_node_params
*info
,
2045 vec
<tree
> *known_csts
,
2046 vec
<ipa_polymorphic_call_context
>
2048 vec
<ipa_agg_jump_function
> *known_aggs
,
2049 int *removable_params_cost
)
2051 int i
, count
= ipa_get_param_count (info
);
2054 known_csts
->create (0);
2055 known_contexts
->create (0);
2056 known_csts
->safe_grow_cleared (count
);
2057 known_contexts
->safe_grow_cleared (count
);
2060 known_aggs
->create (0);
2061 known_aggs
->safe_grow_cleared (count
);
2064 if (removable_params_cost
)
2065 *removable_params_cost
= 0;
2067 for (i
= 0; i
< count
; i
++)
2069 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2070 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
2072 if (lat
->is_single_const ())
2074 ipcp_value
<tree
> *val
= lat
->values
;
2075 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
2076 (*known_csts
)[i
] = val
->value
;
2077 if (removable_params_cost
)
2078 *removable_params_cost
2079 += estimate_move_cost (TREE_TYPE (val
->value
), false);
2082 else if (removable_params_cost
2083 && !ipa_is_param_used (info
, i
))
2084 *removable_params_cost
2085 += ipa_get_param_move_cost (info
, i
);
2087 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
2088 if (ctxlat
->is_single_const ())
2090 (*known_contexts
)[i
] = ctxlat
->values
->value
;
2096 vec
<ipa_agg_jf_item
, va_gc
> *agg_items
;
2097 struct ipa_agg_jump_function
*ajf
;
2099 agg_items
= context_independent_aggregate_values (plats
);
2100 ajf
= &(*known_aggs
)[i
];
2101 ajf
->items
= agg_items
;
2102 ajf
->by_ref
= plats
->aggs_by_ref
;
2103 ret
|= agg_items
!= NULL
;
2110 /* The current interface in ipa-inline-analysis requires a pointer vector.
2113 FIXME: That interface should be re-worked, this is slightly silly. Still,
2114 I'd like to discuss how to change it first and this demonstrates the
2117 static vec
<ipa_agg_jump_function_p
>
2118 agg_jmp_p_vec_for_t_vec (vec
<ipa_agg_jump_function
> known_aggs
)
2120 vec
<ipa_agg_jump_function_p
> ret
;
2121 struct ipa_agg_jump_function
*ajf
;
2124 ret
.create (known_aggs
.length ());
2125 FOR_EACH_VEC_ELT (known_aggs
, i
, ajf
)
2126 ret
.quick_push (ajf
);
2130 /* Perform time and size measurement of NODE with the context given in
2131 KNOWN_CSTS, KNOWN_CONTEXTS and KNOWN_AGGS, calculate the benefit and cost
2132 given BASE_TIME of the node without specialization, REMOVABLE_PARAMS_COST of
2133 all context-independent removable parameters and EST_MOVE_COST of estimated
2134 movement of the considered parameter and store it into VAL. */
2137 perform_estimation_of_a_value (cgraph_node
*node
, vec
<tree
> known_csts
,
2138 vec
<ipa_polymorphic_call_context
> known_contexts
,
2139 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
,
2140 int base_time
, int removable_params_cost
,
2141 int est_move_cost
, ipcp_value_base
*val
)
2143 int time
, size
, time_benefit
;
2146 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
2147 known_aggs_ptrs
, &size
, &time
,
2149 time_benefit
= base_time
- time
2150 + devirtualization_time_bonus (node
, known_csts
, known_contexts
,
2152 + hint_time_bonus (hints
)
2153 + removable_params_cost
+ est_move_cost
;
2155 gcc_checking_assert (size
>=0);
2156 /* The inliner-heuristics based estimates may think that in certain
2157 contexts some functions do not have any size at all but we want
2158 all specializations to have at least a tiny cost, not least not to
2163 val
->local_time_benefit
= time_benefit
;
2164 val
->local_size_cost
= size
;
2167 /* Iterate over known values of parameters of NODE and estimate the local
2168 effects in terms of time and size they have. */
2171 estimate_local_effects (struct cgraph_node
*node
)
2173 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2174 int i
, count
= ipa_get_param_count (info
);
2175 vec
<tree
> known_csts
;
2176 vec
<ipa_polymorphic_call_context
> known_contexts
;
2177 vec
<ipa_agg_jump_function
> known_aggs
;
2178 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
;
2180 int base_time
= inline_summary (node
)->time
;
2181 int removable_params_cost
;
2183 if (!count
|| !ipcp_versionable_function_p (node
))
2186 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2187 fprintf (dump_file
, "\nEstimating effects for %s/%i, base_time: %i.\n",
2188 node
->name (), node
->order
, base_time
);
2190 always_const
= gather_context_independent_values (info
, &known_csts
,
2191 &known_contexts
, &known_aggs
,
2192 &removable_params_cost
);
2193 known_aggs_ptrs
= agg_jmp_p_vec_for_t_vec (known_aggs
);
2196 struct caller_statistics stats
;
2200 init_caller_stats (&stats
);
2201 node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
2203 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
2204 known_aggs_ptrs
, &size
, &time
, &hints
);
2205 time
-= devirtualization_time_bonus (node
, known_csts
, known_contexts
,
2207 time
-= hint_time_bonus (hints
);
2208 time
-= removable_params_cost
;
2209 size
-= stats
.n_calls
* removable_params_cost
;
2212 fprintf (dump_file
, " - context independent values, size: %i, "
2213 "time_benefit: %i\n", size
, base_time
- time
);
2216 || node
->will_be_removed_from_program_if_no_direct_calls_p ())
2218 info
->do_clone_for_all_contexts
= true;
2222 fprintf (dump_file
, " Decided to specialize for all "
2223 "known contexts, code not going to grow.\n");
2225 else if (good_cloning_opportunity_p (node
, base_time
- time
,
2226 stats
.freq_sum
, stats
.count_sum
,
2229 if (size
+ overall_size
<= max_new_size
)
2231 info
->do_clone_for_all_contexts
= true;
2233 overall_size
+= size
;
2236 fprintf (dump_file
, " Decided to specialize for all "
2237 "known contexts, growth deemed beneficial.\n");
2239 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2240 fprintf (dump_file
, " Not cloning for all contexts because "
2241 "max_new_size would be reached with %li.\n",
2242 size
+ overall_size
);
2246 for (i
= 0; i
< count
; i
++)
2248 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2249 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
2250 ipcp_value
<tree
> *val
;
2257 for (val
= lat
->values
; val
; val
= val
->next
)
2259 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
2260 known_csts
[i
] = val
->value
;
2262 int emc
= estimate_move_cost (TREE_TYPE (val
->value
), true);
2263 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
2264 known_aggs_ptrs
, base_time
,
2265 removable_params_cost
, emc
, val
);
2267 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2269 fprintf (dump_file
, " - estimates for value ");
2270 print_ipcp_constant_value (dump_file
, val
->value
);
2271 fprintf (dump_file
, " for ");
2272 ipa_dump_param (dump_file
, info
, i
);
2273 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
2274 val
->local_time_benefit
, val
->local_size_cost
);
2277 known_csts
[i
] = NULL_TREE
;
2280 for (i
= 0; i
< count
; i
++)
2282 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2284 if (!plats
->virt_call
)
2287 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
2288 ipcp_value
<ipa_polymorphic_call_context
> *val
;
2292 || !known_contexts
[i
].useless_p ())
2295 for (val
= ctxlat
->values
; val
; val
= val
->next
)
2297 known_contexts
[i
] = val
->value
;
2298 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
2299 known_aggs_ptrs
, base_time
,
2300 removable_params_cost
, 0, val
);
2302 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2304 fprintf (dump_file
, " - estimates for polymorphic context ");
2305 print_ipcp_constant_value (dump_file
, val
->value
);
2306 fprintf (dump_file
, " for ");
2307 ipa_dump_param (dump_file
, info
, i
);
2308 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
2309 val
->local_time_benefit
, val
->local_size_cost
);
2312 known_contexts
[i
] = ipa_polymorphic_call_context ();
2315 for (i
= 0; i
< count
; i
++)
2317 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2318 struct ipa_agg_jump_function
*ajf
;
2319 struct ipcp_agg_lattice
*aglat
;
2321 if (plats
->aggs_bottom
|| !plats
->aggs
)
2324 ajf
= &known_aggs
[i
];
2325 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2327 ipcp_value
<tree
> *val
;
2328 if (aglat
->bottom
|| !aglat
->values
2329 /* If the following is true, the one value is in known_aggs. */
2330 || (!plats
->aggs_contain_variable
2331 && aglat
->is_single_const ()))
2334 for (val
= aglat
->values
; val
; val
= val
->next
)
2336 struct ipa_agg_jf_item item
;
2338 item
.offset
= aglat
->offset
;
2339 item
.value
= val
->value
;
2340 vec_safe_push (ajf
->items
, item
);
2342 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
2343 known_aggs_ptrs
, base_time
,
2344 removable_params_cost
, 0, val
);
2346 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2348 fprintf (dump_file
, " - estimates for value ");
2349 print_ipcp_constant_value (dump_file
, val
->value
);
2350 fprintf (dump_file
, " for ");
2351 ipa_dump_param (dump_file
, info
, i
);
2352 fprintf (dump_file
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
2353 "]: time_benefit: %i, size: %i\n",
2354 plats
->aggs_by_ref
? "ref " : "",
2356 val
->local_time_benefit
, val
->local_size_cost
);
2364 for (i
= 0; i
< count
; i
++)
2365 vec_free (known_aggs
[i
].items
);
2367 known_csts
.release ();
2368 known_contexts
.release ();
2369 known_aggs
.release ();
2370 known_aggs_ptrs
.release ();
2374 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
2375 topological sort of values. */
2377 template <typename valtype
>
2379 value_topo_info
<valtype
>::add_val (ipcp_value
<valtype
> *cur_val
)
2381 ipcp_value_source
<valtype
> *src
;
2387 cur_val
->dfs
= dfs_counter
;
2388 cur_val
->low_link
= dfs_counter
;
2390 cur_val
->topo_next
= stack
;
2392 cur_val
->on_stack
= true;
2394 for (src
= cur_val
->sources
; src
; src
= src
->next
)
2397 if (src
->val
->dfs
== 0)
2400 if (src
->val
->low_link
< cur_val
->low_link
)
2401 cur_val
->low_link
= src
->val
->low_link
;
2403 else if (src
->val
->on_stack
2404 && src
->val
->dfs
< cur_val
->low_link
)
2405 cur_val
->low_link
= src
->val
->dfs
;
2408 if (cur_val
->dfs
== cur_val
->low_link
)
2410 ipcp_value
<valtype
> *v
, *scc_list
= NULL
;
2415 stack
= v
->topo_next
;
2416 v
->on_stack
= false;
2418 v
->scc_next
= scc_list
;
2421 while (v
!= cur_val
);
2423 cur_val
->topo_next
= values_topo
;
2424 values_topo
= cur_val
;
2428 /* Add all values in lattices associated with NODE to the topological sort if
2429 they are not there yet. */
2432 add_all_node_vals_to_toposort (cgraph_node
*node
, ipa_topo_info
*topo
)
2434 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2435 int i
, count
= ipa_get_param_count (info
);
2437 for (i
= 0; i
< count
; i
++)
2439 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2440 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
2441 struct ipcp_agg_lattice
*aglat
;
2445 ipcp_value
<tree
> *val
;
2446 for (val
= lat
->values
; val
; val
= val
->next
)
2447 topo
->constants
.add_val (val
);
2450 if (!plats
->aggs_bottom
)
2451 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2454 ipcp_value
<tree
> *val
;
2455 for (val
= aglat
->values
; val
; val
= val
->next
)
2456 topo
->constants
.add_val (val
);
2459 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
2460 if (!ctxlat
->bottom
)
2462 ipcp_value
<ipa_polymorphic_call_context
> *ctxval
;
2463 for (ctxval
= ctxlat
->values
; ctxval
; ctxval
= ctxval
->next
)
2464 topo
->contexts
.add_val (ctxval
);
2469 /* One pass of constants propagation along the call graph edges, from callers
2470 to callees (requires topological ordering in TOPO), iterate over strongly
2471 connected components. */
2474 propagate_constants_topo (struct ipa_topo_info
*topo
)
2478 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
2481 struct cgraph_node
*v
, *node
= topo
->order
[i
];
2482 vec
<cgraph_node
*> cycle_nodes
= ipa_get_nodes_in_cycle (node
);
2484 /* First, iteratively propagate within the strongly connected component
2485 until all lattices stabilize. */
2486 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
2487 if (v
->has_gimple_body_p ())
2488 push_node_to_stack (topo
, v
);
2490 v
= pop_node_from_stack (topo
);
2493 struct cgraph_edge
*cs
;
2495 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
2496 if (ipa_edge_within_scc (cs
)
2497 && propagate_constants_accross_call (cs
))
2498 push_node_to_stack (topo
, cs
->callee
);
2499 v
= pop_node_from_stack (topo
);
2502 /* Afterwards, propagate along edges leading out of the SCC, calculates
2503 the local effects of the discovered constants and all valid values to
2504 their topological sort. */
2505 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
2506 if (v
->has_gimple_body_p ())
2508 struct cgraph_edge
*cs
;
2510 estimate_local_effects (v
);
2511 add_all_node_vals_to_toposort (v
, topo
);
2512 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
2513 if (!ipa_edge_within_scc (cs
))
2514 propagate_constants_accross_call (cs
);
2516 cycle_nodes
.release ();
2521 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
2522 the bigger one if otherwise. */
2525 safe_add (int a
, int b
)
2527 if (a
> INT_MAX
/2 || b
> INT_MAX
/2)
2528 return a
> b
? a
: b
;
2534 /* Propagate the estimated effects of individual values along the topological
2535 from the dependent values to those they depend on. */
2537 template <typename valtype
>
2539 value_topo_info
<valtype
>::propagate_effects ()
2541 ipcp_value
<valtype
> *base
;
2543 for (base
= values_topo
; base
; base
= base
->topo_next
)
2545 ipcp_value_source
<valtype
> *src
;
2546 ipcp_value
<valtype
> *val
;
2547 int time
= 0, size
= 0;
2549 for (val
= base
; val
; val
= val
->scc_next
)
2551 time
= safe_add (time
,
2552 val
->local_time_benefit
+ val
->prop_time_benefit
);
2553 size
= safe_add (size
, val
->local_size_cost
+ val
->prop_size_cost
);
2556 for (val
= base
; val
; val
= val
->scc_next
)
2557 for (src
= val
->sources
; src
; src
= src
->next
)
2559 && src
->cs
->maybe_hot_p ())
2561 src
->val
->prop_time_benefit
= safe_add (time
,
2562 src
->val
->prop_time_benefit
);
2563 src
->val
->prop_size_cost
= safe_add (size
,
2564 src
->val
->prop_size_cost
);
2570 /* Propagate constants, polymorphic contexts and their effects from the
2571 summaries interprocedurally. */
2574 ipcp_propagate_stage (struct ipa_topo_info
*topo
)
2576 struct cgraph_node
*node
;
2579 fprintf (dump_file
, "\n Propagating constants:\n\n");
2582 ipa_update_after_lto_read ();
2585 FOR_EACH_DEFINED_FUNCTION (node
)
2587 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2589 determine_versionability (node
);
2590 if (node
->has_gimple_body_p ())
2592 info
->lattices
= XCNEWVEC (struct ipcp_param_lattices
,
2593 ipa_get_param_count (info
));
2594 initialize_node_lattices (node
);
2596 if (node
->definition
&& !node
->alias
)
2597 overall_size
+= inline_summary (node
)->self_size
;
2598 if (node
->count
> max_count
)
2599 max_count
= node
->count
;
2602 max_new_size
= overall_size
;
2603 if (max_new_size
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
2604 max_new_size
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
2605 max_new_size
+= max_new_size
* PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH
) / 100 + 1;
2608 fprintf (dump_file
, "\noverall_size: %li, max_new_size: %li\n",
2609 overall_size
, max_new_size
);
2611 propagate_constants_topo (topo
);
2612 #ifdef ENABLE_CHECKING
2613 ipcp_verify_propagated_values ();
2615 topo
->constants
.propagate_effects ();
2616 topo
->contexts
.propagate_effects ();
2620 fprintf (dump_file
, "\nIPA lattices after all propagation:\n");
2621 print_all_lattices (dump_file
, (dump_flags
& TDF_DETAILS
), true);
2625 /* Discover newly direct outgoing edges from NODE which is a new clone with
2626 known KNOWN_CSTS and make them direct. */
2629 ipcp_discover_new_direct_edges (struct cgraph_node
*node
,
2630 vec
<tree
> known_csts
,
2631 vec
<ipa_polymorphic_call_context
>
2633 struct ipa_agg_replacement_value
*aggvals
)
2635 struct cgraph_edge
*ie
, *next_ie
;
2638 for (ie
= node
->indirect_calls
; ie
; ie
= next_ie
)
2642 next_ie
= ie
->next_callee
;
2643 target
= ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
2647 bool agg_contents
= ie
->indirect_info
->agg_contents
;
2648 bool polymorphic
= ie
->indirect_info
->polymorphic
;
2649 int param_index
= ie
->indirect_info
->param_index
;
2650 struct cgraph_edge
*cs
= ipa_make_edge_direct_to_target (ie
, target
);
2653 if (cs
&& !agg_contents
&& !polymorphic
)
2655 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2656 int c
= ipa_get_controlled_uses (info
, param_index
);
2657 if (c
!= IPA_UNDESCRIBED_USE
)
2659 struct ipa_ref
*to_del
;
2662 ipa_set_controlled_uses (info
, param_index
, c
);
2663 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2664 fprintf (dump_file
, " controlled uses count of param "
2665 "%i bumped down to %i\n", param_index
, c
);
2667 && (to_del
= node
->find_reference (cs
->callee
, NULL
, 0)))
2669 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2670 fprintf (dump_file
, " and even removing its "
2671 "cloning-created reference\n");
2672 to_del
->remove_reference ();
2678 /* Turning calls to direct calls will improve overall summary. */
2680 inline_update_overall_summary (node
);
2683 /* Vector of pointers which for linked lists of clones of an original crgaph
2686 static vec
<cgraph_edge
*> next_edge_clone
;
2687 static vec
<cgraph_edge
*> prev_edge_clone
;
2690 grow_edge_clone_vectors (void)
2692 if (next_edge_clone
.length ()
2693 <= (unsigned) symtab
->edges_max_uid
)
2694 next_edge_clone
.safe_grow_cleared (symtab
->edges_max_uid
+ 1);
2695 if (prev_edge_clone
.length ()
2696 <= (unsigned) symtab
->edges_max_uid
)
2697 prev_edge_clone
.safe_grow_cleared (symtab
->edges_max_uid
+ 1);
2700 /* Edge duplication hook to grow the appropriate linked list in
2704 ipcp_edge_duplication_hook (struct cgraph_edge
*src
, struct cgraph_edge
*dst
,
2707 grow_edge_clone_vectors ();
2709 struct cgraph_edge
*old_next
= next_edge_clone
[src
->uid
];
2711 prev_edge_clone
[old_next
->uid
] = dst
;
2712 prev_edge_clone
[dst
->uid
] = src
;
2714 next_edge_clone
[dst
->uid
] = old_next
;
2715 next_edge_clone
[src
->uid
] = dst
;
2718 /* Hook that is called by cgraph.c when an edge is removed. */
2721 ipcp_edge_removal_hook (struct cgraph_edge
*cs
, void *)
2723 grow_edge_clone_vectors ();
2725 struct cgraph_edge
*prev
= prev_edge_clone
[cs
->uid
];
2726 struct cgraph_edge
*next
= next_edge_clone
[cs
->uid
];
2728 next_edge_clone
[prev
->uid
] = next
;
2730 prev_edge_clone
[next
->uid
] = prev
;
2733 /* See if NODE is a clone with a known aggregate value at a given OFFSET of a
2734 parameter with the given INDEX. */
2737 get_clone_agg_value (struct cgraph_node
*node
, HOST_WIDE_INT offset
,
2740 struct ipa_agg_replacement_value
*aggval
;
2742 aggval
= ipa_get_agg_replacements_for_node (node
);
2745 if (aggval
->offset
== offset
2746 && aggval
->index
== index
)
2747 return aggval
->value
;
2748 aggval
= aggval
->next
;
2753 /* Return true if edge CS does bring about the value described by SRC. */
2756 cgraph_edge_brings_value_p (struct cgraph_edge
*cs
,
2757 ipcp_value_source
<tree
> *src
)
2759 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2760 cgraph_node
*real_dest
= cs
->callee
->function_symbol ();
2761 struct ipa_node_params
*dst_info
= IPA_NODE_REF (real_dest
);
2763 if ((dst_info
->ipcp_orig_node
&& !dst_info
->is_all_contexts_clone
)
2764 || caller_info
->node_dead
)
2769 if (caller_info
->ipcp_orig_node
)
2772 if (src
->offset
== -1)
2773 t
= caller_info
->known_csts
[src
->index
];
2775 t
= get_clone_agg_value (cs
->caller
, src
->offset
, src
->index
);
2776 return (t
!= NULL_TREE
2777 && values_equal_for_ipcp_p (src
->val
->value
, t
));
2781 struct ipcp_agg_lattice
*aglat
;
2782 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
2784 if (src
->offset
== -1)
2785 return (plats
->itself
.is_single_const ()
2786 && values_equal_for_ipcp_p (src
->val
->value
,
2787 plats
->itself
.values
->value
));
2790 if (plats
->aggs_bottom
|| plats
->aggs_contain_variable
)
2792 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2793 if (aglat
->offset
== src
->offset
)
2794 return (aglat
->is_single_const ()
2795 && values_equal_for_ipcp_p (src
->val
->value
,
2796 aglat
->values
->value
));
2802 /* Return true if edge CS does bring about the value described by SRC. */
2805 cgraph_edge_brings_value_p (struct cgraph_edge
*cs
,
2806 ipcp_value_source
<ipa_polymorphic_call_context
>
2809 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2810 cgraph_node
*real_dest
= cs
->callee
->function_symbol ();
2811 struct ipa_node_params
*dst_info
= IPA_NODE_REF (real_dest
);
2813 if ((dst_info
->ipcp_orig_node
&& !dst_info
->is_all_contexts_clone
)
2814 || caller_info
->node_dead
)
2819 if (caller_info
->ipcp_orig_node
)
2820 return (caller_info
->known_contexts
.length () > (unsigned) src
->index
)
2821 && values_equal_for_ipcp_p (src
->val
->value
,
2822 caller_info
->known_contexts
[src
->index
]);
2824 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
2826 return plats
->ctxlat
.is_single_const ()
2827 && values_equal_for_ipcp_p (src
->val
->value
,
2828 plats
->ctxlat
.values
->value
);
2831 /* Get the next clone in the linked list of clones of an edge. */
2833 static inline struct cgraph_edge
*
2834 get_next_cgraph_edge_clone (struct cgraph_edge
*cs
)
2836 return next_edge_clone
[cs
->uid
];
2839 /* Given VAL, iterate over all its sources and if they still hold, add their
2840 edge frequency and their number into *FREQUENCY and *CALLER_COUNT
2843 template <typename valtype
>
2845 get_info_about_necessary_edges (ipcp_value
<valtype
> *val
, int *freq_sum
,
2846 gcov_type
*count_sum
, int *caller_count
)
2848 ipcp_value_source
<valtype
> *src
;
2849 int freq
= 0, count
= 0;
2853 for (src
= val
->sources
; src
; src
= src
->next
)
2855 struct cgraph_edge
*cs
= src
->cs
;
2858 if (cgraph_edge_brings_value_p (cs
, src
))
2861 freq
+= cs
->frequency
;
2863 hot
|= cs
->maybe_hot_p ();
2865 cs
= get_next_cgraph_edge_clone (cs
);
2871 *caller_count
= count
;
2875 /* Return a vector of incoming edges that do bring value VAL. It is assumed
2876 their number is known and equal to CALLER_COUNT. */
2878 template <typename valtype
>
2879 static vec
<cgraph_edge
*>
2880 gather_edges_for_value (ipcp_value
<valtype
> *val
, int caller_count
)
2882 ipcp_value_source
<valtype
> *src
;
2883 vec
<cgraph_edge
*> ret
;
2885 ret
.create (caller_count
);
2886 for (src
= val
->sources
; src
; src
= src
->next
)
2888 struct cgraph_edge
*cs
= src
->cs
;
2891 if (cgraph_edge_brings_value_p (cs
, src
))
2892 ret
.quick_push (cs
);
2893 cs
= get_next_cgraph_edge_clone (cs
);
2900 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
2901 Return it or NULL if for some reason it cannot be created. */
2903 static struct ipa_replace_map
*
2904 get_replacement_map (struct ipa_node_params
*info
, tree value
, int parm_num
)
2906 struct ipa_replace_map
*replace_map
;
2909 replace_map
= ggc_alloc
<ipa_replace_map
> ();
2912 fprintf (dump_file
, " replacing ");
2913 ipa_dump_param (dump_file
, info
, parm_num
);
2915 fprintf (dump_file
, " with const ");
2916 print_generic_expr (dump_file
, value
, 0);
2917 fprintf (dump_file
, "\n");
2919 replace_map
->old_tree
= NULL
;
2920 replace_map
->parm_num
= parm_num
;
2921 replace_map
->new_tree
= value
;
2922 replace_map
->replace_p
= true;
2923 replace_map
->ref_p
= false;
2928 /* Dump new profiling counts */
2931 dump_profile_updates (struct cgraph_node
*orig_node
,
2932 struct cgraph_node
*new_node
)
2934 struct cgraph_edge
*cs
;
2936 fprintf (dump_file
, " setting count of the specialized node to "
2937 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) new_node
->count
);
2938 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
2939 fprintf (dump_file
, " edge to %s has count "
2940 HOST_WIDE_INT_PRINT_DEC
"\n",
2941 cs
->callee
->name (), (HOST_WIDE_INT
) cs
->count
);
2943 fprintf (dump_file
, " setting count of the original node to "
2944 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) orig_node
->count
);
2945 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
2946 fprintf (dump_file
, " edge to %s is left with "
2947 HOST_WIDE_INT_PRINT_DEC
"\n",
2948 cs
->callee
->name (), (HOST_WIDE_INT
) cs
->count
);
2951 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
2952 their profile information to reflect this. */
2955 update_profiling_info (struct cgraph_node
*orig_node
,
2956 struct cgraph_node
*new_node
)
2958 struct cgraph_edge
*cs
;
2959 struct caller_statistics stats
;
2960 gcov_type new_sum
, orig_sum
;
2961 gcov_type remainder
, orig_node_count
= orig_node
->count
;
2963 if (orig_node_count
== 0)
2966 init_caller_stats (&stats
);
2967 orig_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
2969 orig_sum
= stats
.count_sum
;
2970 init_caller_stats (&stats
);
2971 new_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
2973 new_sum
= stats
.count_sum
;
2975 if (orig_node_count
< orig_sum
+ new_sum
)
2978 fprintf (dump_file
, " Problem: node %s/%i has too low count "
2979 HOST_WIDE_INT_PRINT_DEC
" while the sum of incoming "
2980 "counts is " HOST_WIDE_INT_PRINT_DEC
"\n",
2981 orig_node
->name (), orig_node
->order
,
2982 (HOST_WIDE_INT
) orig_node_count
,
2983 (HOST_WIDE_INT
) (orig_sum
+ new_sum
));
2985 orig_node_count
= (orig_sum
+ new_sum
) * 12 / 10;
2987 fprintf (dump_file
, " proceeding by pretending it was "
2988 HOST_WIDE_INT_PRINT_DEC
"\n",
2989 (HOST_WIDE_INT
) orig_node_count
);
2992 new_node
->count
= new_sum
;
2993 remainder
= orig_node_count
- new_sum
;
2994 orig_node
->count
= remainder
;
2996 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
2998 cs
->count
= apply_probability (cs
->count
,
2999 GCOV_COMPUTE_SCALE (new_sum
,
3004 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3005 cs
->count
= apply_probability (cs
->count
,
3006 GCOV_COMPUTE_SCALE (remainder
,
3010 dump_profile_updates (orig_node
, new_node
);
3013 /* Update the respective profile of specialized NEW_NODE and the original
3014 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
3015 have been redirected to the specialized version. */
3018 update_specialized_profile (struct cgraph_node
*new_node
,
3019 struct cgraph_node
*orig_node
,
3020 gcov_type redirected_sum
)
3022 struct cgraph_edge
*cs
;
3023 gcov_type new_node_count
, orig_node_count
= orig_node
->count
;
3026 fprintf (dump_file
, " the sum of counts of redirected edges is "
3027 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) redirected_sum
);
3028 if (orig_node_count
== 0)
3031 gcc_assert (orig_node_count
>= redirected_sum
);
3033 new_node_count
= new_node
->count
;
3034 new_node
->count
+= redirected_sum
;
3035 orig_node
->count
-= redirected_sum
;
3037 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3039 cs
->count
+= apply_probability (cs
->count
,
3040 GCOV_COMPUTE_SCALE (redirected_sum
,
3045 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3047 gcov_type dec
= apply_probability (cs
->count
,
3048 GCOV_COMPUTE_SCALE (redirected_sum
,
3050 if (dec
< cs
->count
)
3057 dump_profile_updates (orig_node
, new_node
);
3060 /* Create a specialized version of NODE with known constants in KNOWN_CSTS,
3061 known contexts in KNOWN_CONTEXTS and known aggregate values in AGGVALS and
3062 redirect all edges in CALLERS to it. */
3064 static struct cgraph_node
*
3065 create_specialized_node (struct cgraph_node
*node
,
3066 vec
<tree
> known_csts
,
3067 vec
<ipa_polymorphic_call_context
> known_contexts
,
3068 struct ipa_agg_replacement_value
*aggvals
,
3069 vec
<cgraph_edge
*> callers
)
3071 struct ipa_node_params
*new_info
, *info
= IPA_NODE_REF (node
);
3072 vec
<ipa_replace_map
*, va_gc
> *replace_trees
= NULL
;
3073 struct ipa_agg_replacement_value
*av
;
3074 struct cgraph_node
*new_node
;
3075 int i
, count
= ipa_get_param_count (info
);
3076 bitmap args_to_skip
;
3078 gcc_assert (!info
->ipcp_orig_node
);
3080 if (node
->local
.can_change_signature
)
3082 args_to_skip
= BITMAP_GGC_ALLOC ();
3083 for (i
= 0; i
< count
; i
++)
3085 tree t
= known_csts
[i
];
3087 if (t
|| !ipa_is_param_used (info
, i
))
3088 bitmap_set_bit (args_to_skip
, i
);
3093 args_to_skip
= NULL
;
3094 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3095 fprintf (dump_file
, " cannot change function signature\n");
3098 for (i
= 0; i
< count
; i
++)
3100 tree t
= known_csts
[i
];
3103 struct ipa_replace_map
*replace_map
;
3105 gcc_checking_assert (TREE_CODE (t
) != TREE_BINFO
);
3106 replace_map
= get_replacement_map (info
, t
, i
);
3108 vec_safe_push (replace_trees
, replace_map
);
3112 new_node
= node
->create_virtual_clone (callers
, replace_trees
,
3113 args_to_skip
, "constprop");
3114 ipa_set_node_agg_value_chain (new_node
, aggvals
);
3115 for (av
= aggvals
; av
; av
= av
->next
)
3116 new_node
->maybe_create_reference (av
->value
, IPA_REF_ADDR
, NULL
);
3118 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3120 fprintf (dump_file
, " the new node is %s/%i.\n",
3121 new_node
->name (), new_node
->order
);
3122 if (known_contexts
.exists ())
3124 for (i
= 0; i
< count
; i
++)
3125 if (!known_contexts
[i
].useless_p ())
3127 fprintf (dump_file
, " known ctx %i is ", i
);
3128 known_contexts
[i
].dump (dump_file
);
3132 ipa_dump_agg_replacement_values (dump_file
, aggvals
);
3134 ipa_check_create_node_params ();
3135 update_profiling_info (node
, new_node
);
3136 new_info
= IPA_NODE_REF (new_node
);
3137 new_info
->ipcp_orig_node
= node
;
3138 new_info
->known_csts
= known_csts
;
3139 new_info
->known_contexts
= known_contexts
;
3141 ipcp_discover_new_direct_edges (new_node
, known_csts
, known_contexts
, aggvals
);
3147 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
3148 KNOWN_CSTS with constants that are also known for all of the CALLERS. */
3151 find_more_scalar_values_for_callers_subset (struct cgraph_node
*node
,
3152 vec
<tree
> known_csts
,
3153 vec
<cgraph_edge
*> callers
)
3155 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3156 int i
, count
= ipa_get_param_count (info
);
3158 for (i
= 0; i
< count
; i
++)
3160 struct cgraph_edge
*cs
;
3161 tree newval
= NULL_TREE
;
3164 if (ipa_get_scalar_lat (info
, i
)->bottom
|| known_csts
[i
])
3167 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3169 struct ipa_jump_func
*jump_func
;
3172 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
)))
3177 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
3178 t
= ipa_value_from_jfunc (IPA_NODE_REF (cs
->caller
), jump_func
);
3181 && !values_equal_for_ipcp_p (t
, newval
)))
3192 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3194 fprintf (dump_file
, " adding an extra known scalar value ");
3195 print_ipcp_constant_value (dump_file
, newval
);
3196 fprintf (dump_file
, " for ");
3197 ipa_dump_param (dump_file
, info
, i
);
3198 fprintf (dump_file
, "\n");
3201 known_csts
[i
] = newval
;
3206 /* Given a NODE and a subset of its CALLERS, try to populate plank slots in
3207 KNOWN_CONTEXTS with polymorphic contexts that are also known for all of the
3211 find_more_contexts_for_caller_subset (cgraph_node
*node
,
3212 vec
<ipa_polymorphic_call_context
>
3214 vec
<cgraph_edge
*> callers
)
3216 ipa_node_params
*info
= IPA_NODE_REF (node
);
3217 int i
, count
= ipa_get_param_count (info
);
3219 for (i
= 0; i
< count
; i
++)
3223 if (ipa_get_poly_ctx_lat (info
, i
)->bottom
3224 || (known_contexts
->exists ()
3225 && !(*known_contexts
)[i
].useless_p ()))
3228 ipa_polymorphic_call_context newval
;
3232 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3234 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
)))
3236 ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
),
3238 ipa_polymorphic_call_context ctx
;
3239 ctx
= ipa_context_from_jfunc (IPA_NODE_REF (cs
->caller
), cs
, i
,
3241 ctx
.clear_speculation ();
3242 if (ctx
.useless_p ()
3243 || (found
&& !values_equal_for_ipcp_p (newval
, ctx
)))
3257 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3259 fprintf (dump_file
, " adding an extra known polymorphic "
3261 print_ipcp_constant_value (dump_file
, newval
);
3262 fprintf (dump_file
, " for ");
3263 ipa_dump_param (dump_file
, info
, i
);
3264 fprintf (dump_file
, "\n");
3267 if (!known_contexts
->exists ())
3268 known_contexts
->safe_grow_cleared (ipa_get_param_count (info
));
3269 (*known_contexts
)[i
] = newval
;
3275 /* Go through PLATS and create a vector of values consisting of values and
3276 offsets (minus OFFSET) of lattices that contain only a single value. */
3278 static vec
<ipa_agg_jf_item
>
3279 copy_plats_to_inter (struct ipcp_param_lattices
*plats
, HOST_WIDE_INT offset
)
3281 vec
<ipa_agg_jf_item
> res
= vNULL
;
3283 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
3286 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3287 if (aglat
->is_single_const ())
3289 struct ipa_agg_jf_item ti
;
3290 ti
.offset
= aglat
->offset
- offset
;
3291 ti
.value
= aglat
->values
->value
;
3297 /* Intersect all values in INTER with single value lattices in PLATS (while
3298 subtracting OFFSET). */
3301 intersect_with_plats (struct ipcp_param_lattices
*plats
,
3302 vec
<ipa_agg_jf_item
> *inter
,
3303 HOST_WIDE_INT offset
)
3305 struct ipcp_agg_lattice
*aglat
;
3306 struct ipa_agg_jf_item
*item
;
3309 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
3315 aglat
= plats
->aggs
;
3316 FOR_EACH_VEC_ELT (*inter
, k
, item
)
3323 if (aglat
->offset
- offset
> item
->offset
)
3325 if (aglat
->offset
- offset
== item
->offset
)
3327 gcc_checking_assert (item
->value
);
3328 if (values_equal_for_ipcp_p (item
->value
, aglat
->values
->value
))
3332 aglat
= aglat
->next
;
3335 item
->value
= NULL_TREE
;
3339 /* Copy agggregate replacement values of NODE (which is an IPA-CP clone) to the
3340 vector result while subtracting OFFSET from the individual value offsets. */
3342 static vec
<ipa_agg_jf_item
>
3343 agg_replacements_to_vector (struct cgraph_node
*node
, int index
,
3344 HOST_WIDE_INT offset
)
3346 struct ipa_agg_replacement_value
*av
;
3347 vec
<ipa_agg_jf_item
> res
= vNULL
;
3349 for (av
= ipa_get_agg_replacements_for_node (node
); av
; av
= av
->next
)
3350 if (av
->index
== index
3351 && (av
->offset
- offset
) >= 0)
3353 struct ipa_agg_jf_item item
;
3354 gcc_checking_assert (av
->value
);
3355 item
.offset
= av
->offset
- offset
;
3356 item
.value
= av
->value
;
3357 res
.safe_push (item
);
3363 /* Intersect all values in INTER with those that we have already scheduled to
3364 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
3365 (while subtracting OFFSET). */
3368 intersect_with_agg_replacements (struct cgraph_node
*node
, int index
,
3369 vec
<ipa_agg_jf_item
> *inter
,
3370 HOST_WIDE_INT offset
)
3372 struct ipa_agg_replacement_value
*srcvals
;
3373 struct ipa_agg_jf_item
*item
;
3376 srcvals
= ipa_get_agg_replacements_for_node (node
);
3383 FOR_EACH_VEC_ELT (*inter
, i
, item
)
3385 struct ipa_agg_replacement_value
*av
;
3389 for (av
= srcvals
; av
; av
= av
->next
)
3391 gcc_checking_assert (av
->value
);
3392 if (av
->index
== index
3393 && av
->offset
- offset
== item
->offset
)
3395 if (values_equal_for_ipcp_p (item
->value
, av
->value
))
3401 item
->value
= NULL_TREE
;
3405 /* Intersect values in INTER with aggregate values that come along edge CS to
3406 parameter number INDEX and return it. If INTER does not actually exist yet,
3407 copy all incoming values to it. If we determine we ended up with no values
3408 whatsoever, return a released vector. */
3410 static vec
<ipa_agg_jf_item
>
3411 intersect_aggregates_with_edge (struct cgraph_edge
*cs
, int index
,
3412 vec
<ipa_agg_jf_item
> inter
)
3414 struct ipa_jump_func
*jfunc
;
3415 jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), index
);
3416 if (jfunc
->type
== IPA_JF_PASS_THROUGH
3417 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
3419 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3420 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
3422 if (caller_info
->ipcp_orig_node
)
3424 struct cgraph_node
*orig_node
= caller_info
->ipcp_orig_node
;
3425 struct ipcp_param_lattices
*orig_plats
;
3426 orig_plats
= ipa_get_parm_lattices (IPA_NODE_REF (orig_node
),
3428 if (agg_pass_through_permissible_p (orig_plats
, jfunc
))
3430 if (!inter
.exists ())
3431 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, 0);
3433 intersect_with_agg_replacements (cs
->caller
, src_idx
,
3444 struct ipcp_param_lattices
*src_plats
;
3445 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
3446 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
3448 /* Currently we do not produce clobber aggregate jump
3449 functions, adjust when we do. */
3450 gcc_checking_assert (!jfunc
->agg
.items
);
3451 if (!inter
.exists ())
3452 inter
= copy_plats_to_inter (src_plats
, 0);
3454 intersect_with_plats (src_plats
, &inter
, 0);
3463 else if (jfunc
->type
== IPA_JF_ANCESTOR
3464 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
3466 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3467 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
3468 struct ipcp_param_lattices
*src_plats
;
3469 HOST_WIDE_INT delta
= ipa_get_jf_ancestor_offset (jfunc
);
3471 if (caller_info
->ipcp_orig_node
)
3473 if (!inter
.exists ())
3474 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, delta
);
3476 intersect_with_agg_replacements (cs
->caller
, src_idx
, &inter
,
3481 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);;
3482 /* Currently we do not produce clobber aggregate jump
3483 functions, adjust when we do. */
3484 gcc_checking_assert (!src_plats
->aggs
|| !jfunc
->agg
.items
);
3485 if (!inter
.exists ())
3486 inter
= copy_plats_to_inter (src_plats
, delta
);
3488 intersect_with_plats (src_plats
, &inter
, delta
);
3491 else if (jfunc
->agg
.items
)
3493 struct ipa_agg_jf_item
*item
;
3496 if (!inter
.exists ())
3497 for (unsigned i
= 0; i
< jfunc
->agg
.items
->length (); i
++)
3498 inter
.safe_push ((*jfunc
->agg
.items
)[i
]);
3500 FOR_EACH_VEC_ELT (inter
, k
, item
)
3503 bool found
= false;;
3508 while ((unsigned) l
< jfunc
->agg
.items
->length ())
3510 struct ipa_agg_jf_item
*ti
;
3511 ti
= &(*jfunc
->agg
.items
)[l
];
3512 if (ti
->offset
> item
->offset
)
3514 if (ti
->offset
== item
->offset
)
3516 gcc_checking_assert (ti
->value
);
3517 if (values_equal_for_ipcp_p (item
->value
,
3531 return vec
<ipa_agg_jf_item
>();
3536 /* Look at edges in CALLERS and collect all known aggregate values that arrive
3537 from all of them. */
3539 static struct ipa_agg_replacement_value
*
3540 find_aggregate_values_for_callers_subset (struct cgraph_node
*node
,
3541 vec
<cgraph_edge
*> callers
)
3543 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
3544 struct ipa_agg_replacement_value
*res
;
3545 struct ipa_agg_replacement_value
**tail
= &res
;
3546 struct cgraph_edge
*cs
;
3547 int i
, j
, count
= ipa_get_param_count (dest_info
);
3549 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3551 int c
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
3556 for (i
= 0; i
< count
; i
++)
3558 struct cgraph_edge
*cs
;
3559 vec
<ipa_agg_jf_item
> inter
= vNULL
;
3560 struct ipa_agg_jf_item
*item
;
3561 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (dest_info
, i
);
3564 /* Among other things, the following check should deal with all by_ref
3566 if (plats
->aggs_bottom
)
3569 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3571 inter
= intersect_aggregates_with_edge (cs
, i
, inter
);
3573 if (!inter
.exists ())
3577 FOR_EACH_VEC_ELT (inter
, j
, item
)
3579 struct ipa_agg_replacement_value
*v
;
3584 v
= ggc_alloc
<ipa_agg_replacement_value
> ();
3586 v
->offset
= item
->offset
;
3587 v
->value
= item
->value
;
3588 v
->by_ref
= plats
->aggs_by_ref
;
3594 if (inter
.exists ())
3601 /* Turn KNOWN_AGGS into a list of aggreate replacement values. */
3603 static struct ipa_agg_replacement_value
*
3604 known_aggs_to_agg_replacement_list (vec
<ipa_agg_jump_function
> known_aggs
)
3606 struct ipa_agg_replacement_value
*res
;
3607 struct ipa_agg_replacement_value
**tail
= &res
;
3608 struct ipa_agg_jump_function
*aggjf
;
3609 struct ipa_agg_jf_item
*item
;
3612 FOR_EACH_VEC_ELT (known_aggs
, i
, aggjf
)
3613 FOR_EACH_VEC_SAFE_ELT (aggjf
->items
, j
, item
)
3615 struct ipa_agg_replacement_value
*v
;
3616 v
= ggc_alloc
<ipa_agg_replacement_value
> ();
3618 v
->offset
= item
->offset
;
3619 v
->value
= item
->value
;
3620 v
->by_ref
= aggjf
->by_ref
;
3628 /* Determine whether CS also brings all scalar values that the NODE is
3632 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge
*cs
,
3633 struct cgraph_node
*node
)
3635 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
3636 int count
= ipa_get_param_count (dest_info
);
3637 struct ipa_node_params
*caller_info
;
3638 struct ipa_edge_args
*args
;
3641 caller_info
= IPA_NODE_REF (cs
->caller
);
3642 args
= IPA_EDGE_REF (cs
);
3643 for (i
= 0; i
< count
; i
++)
3645 struct ipa_jump_func
*jump_func
;
3648 val
= dest_info
->known_csts
[i
];
3652 if (i
>= ipa_get_cs_argument_count (args
))
3654 jump_func
= ipa_get_ith_jump_func (args
, i
);
3655 t
= ipa_value_from_jfunc (caller_info
, jump_func
);
3656 if (!t
|| !values_equal_for_ipcp_p (val
, t
))
3662 /* Determine whether CS also brings all aggregate values that NODE is
3665 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge
*cs
,
3666 struct cgraph_node
*node
)
3668 struct ipa_node_params
*orig_caller_info
= IPA_NODE_REF (cs
->caller
);
3669 struct ipa_node_params
*orig_node_info
;
3670 struct ipa_agg_replacement_value
*aggval
;
3673 aggval
= ipa_get_agg_replacements_for_node (node
);
3677 count
= ipa_get_param_count (IPA_NODE_REF (node
));
3678 ec
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
3680 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
3681 if (aggval
->index
>= ec
)
3684 orig_node_info
= IPA_NODE_REF (IPA_NODE_REF (node
)->ipcp_orig_node
);
3685 if (orig_caller_info
->ipcp_orig_node
)
3686 orig_caller_info
= IPA_NODE_REF (orig_caller_info
->ipcp_orig_node
);
3688 for (i
= 0; i
< count
; i
++)
3690 static vec
<ipa_agg_jf_item
> values
= vec
<ipa_agg_jf_item
>();
3691 struct ipcp_param_lattices
*plats
;
3692 bool interesting
= false;
3693 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
3694 if (aggval
->index
== i
)
3702 plats
= ipa_get_parm_lattices (orig_node_info
, aggval
->index
);
3703 if (plats
->aggs_bottom
)
3706 values
= intersect_aggregates_with_edge (cs
, i
, values
);
3707 if (!values
.exists ())
3710 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
3711 if (aggval
->index
== i
)
3713 struct ipa_agg_jf_item
*item
;
3716 FOR_EACH_VEC_ELT (values
, j
, item
)
3718 && item
->offset
== av
->offset
3719 && values_equal_for_ipcp_p (item
->value
, av
->value
))
3734 /* Given an original NODE and a VAL for which we have already created a
3735 specialized clone, look whether there are incoming edges that still lead
3736 into the old node but now also bring the requested value and also conform to
3737 all other criteria such that they can be redirected the the special node.
3738 This function can therefore redirect the final edge in a SCC. */
3740 template <typename valtype
>
3742 perhaps_add_new_callers (cgraph_node
*node
, ipcp_value
<valtype
> *val
)
3744 ipcp_value_source
<valtype
> *src
;
3745 gcov_type redirected_sum
= 0;
3747 for (src
= val
->sources
; src
; src
= src
->next
)
3749 struct cgraph_edge
*cs
= src
->cs
;
3752 enum availability availability
;
3753 struct cgraph_node
*dst
= cs
->callee
->function_symbol (&availability
);
3754 if ((dst
== node
|| IPA_NODE_REF (dst
)->is_all_contexts_clone
)
3755 && availability
> AVAIL_INTERPOSABLE
3756 && cgraph_edge_brings_value_p (cs
, src
))
3758 if (cgraph_edge_brings_all_scalars_for_node (cs
, val
->spec_node
)
3759 && cgraph_edge_brings_all_agg_vals_for_node (cs
,
3763 fprintf (dump_file
, " - adding an extra caller %s/%i"
3765 xstrdup (cs
->caller
->name ()),
3767 xstrdup (val
->spec_node
->name ()),
3768 val
->spec_node
->order
);
3770 cs
->redirect_callee (val
->spec_node
);
3771 redirected_sum
+= cs
->count
;
3774 cs
= get_next_cgraph_edge_clone (cs
);
3779 update_specialized_profile (val
->spec_node
, node
, redirected_sum
);
3782 /* Return true if KNOWN_CONTEXTS contain at least one useful context. */
3785 known_contexts_useful_p (vec
<ipa_polymorphic_call_context
> known_contexts
)
3787 ipa_polymorphic_call_context
*ctx
;
3790 FOR_EACH_VEC_ELT (known_contexts
, i
, ctx
)
3791 if (!ctx
->useless_p ())
3796 /* Return a copy of KNOWN_CSTS if it is not empty, otherwise return vNULL. */
3798 static vec
<ipa_polymorphic_call_context
>
3799 copy_useful_known_contexts (vec
<ipa_polymorphic_call_context
> known_contexts
)
3801 if (known_contexts_useful_p (known_contexts
))
3802 return known_contexts
.copy ();
3807 /* Copy KNOWN_CSTS and modify the copy according to VAL and INDEX. If
3808 non-empty, replace KNOWN_CONTEXTS with its copy too. */
3811 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
3812 vec
<ipa_polymorphic_call_context
> *known_contexts
,
3813 ipcp_value
<tree
> *val
,
3816 *known_csts
= known_csts
->copy ();
3817 *known_contexts
= copy_useful_known_contexts (*known_contexts
);
3818 (*known_csts
)[index
] = val
->value
;
3821 /* Replace KNOWN_CSTS with its copy. Also copy KNOWN_CONTEXTS and modify the
3822 copy according to VAL and INDEX. */
3825 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
3826 vec
<ipa_polymorphic_call_context
> *known_contexts
,
3827 ipcp_value
<ipa_polymorphic_call_context
> *val
,
3830 *known_csts
= known_csts
->copy ();
3831 *known_contexts
= known_contexts
->copy ();
3832 (*known_contexts
)[index
] = val
->value
;
3835 /* Return true if OFFSET indicates this was not an aggregate value or there is
3836 a replacement equivalent to VALUE, INDEX and OFFSET among those in the
3840 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*aggvals
,
3841 int index
, HOST_WIDE_INT offset
, tree value
)
3848 if (aggvals
->index
== index
3849 && aggvals
->offset
== offset
3850 && values_equal_for_ipcp_p (aggvals
->value
, value
))
3852 aggvals
= aggvals
->next
;
3857 /* Return true if offset is minus one because source of a polymorphic contect
3858 cannot be an aggregate value. */
3861 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*,
3862 int , HOST_WIDE_INT offset
,
3863 ipa_polymorphic_call_context
)
3865 return offset
== -1;
3868 /* Decide wheter to create a special version of NODE for value VAL of parameter
3869 at the given INDEX. If OFFSET is -1, the value is for the parameter itself,
3870 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS,
3871 KNOWN_CONTEXTS and KNOWN_AGGS describe the other already known values. */
3873 template <typename valtype
>
3875 decide_about_value (struct cgraph_node
*node
, int index
, HOST_WIDE_INT offset
,
3876 ipcp_value
<valtype
> *val
, vec
<tree
> known_csts
,
3877 vec
<ipa_polymorphic_call_context
> known_contexts
)
3879 struct ipa_agg_replacement_value
*aggvals
;
3880 int freq_sum
, caller_count
;
3881 gcov_type count_sum
;
3882 vec
<cgraph_edge
*> callers
;
3886 perhaps_add_new_callers (node
, val
);
3889 else if (val
->local_size_cost
+ overall_size
> max_new_size
)
3891 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3892 fprintf (dump_file
, " Ignoring candidate value because "
3893 "max_new_size would be reached with %li.\n",
3894 val
->local_size_cost
+ overall_size
);
3897 else if (!get_info_about_necessary_edges (val
, &freq_sum
, &count_sum
,
3901 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3903 fprintf (dump_file
, " - considering value ");
3904 print_ipcp_constant_value (dump_file
, val
->value
);
3905 fprintf (dump_file
, " for ");
3906 ipa_dump_param (dump_file
, IPA_NODE_REF (node
), index
);
3908 fprintf (dump_file
, ", offset: " HOST_WIDE_INT_PRINT_DEC
, offset
);
3909 fprintf (dump_file
, " (caller_count: %i)\n", caller_count
);
3912 if (!good_cloning_opportunity_p (node
, val
->local_time_benefit
,
3913 freq_sum
, count_sum
,
3914 val
->local_size_cost
)
3915 && !good_cloning_opportunity_p (node
,
3916 val
->local_time_benefit
3917 + val
->prop_time_benefit
,
3918 freq_sum
, count_sum
,
3919 val
->local_size_cost
3920 + val
->prop_size_cost
))
3924 fprintf (dump_file
, " Creating a specialized node of %s/%i.\n",
3925 node
->name (), node
->order
);
3927 callers
= gather_edges_for_value (val
, caller_count
);
3929 modify_known_vectors_with_val (&known_csts
, &known_contexts
, val
, index
);
3932 known_csts
= known_csts
.copy ();
3933 known_contexts
= copy_useful_known_contexts (known_contexts
);
3935 find_more_scalar_values_for_callers_subset (node
, known_csts
, callers
);
3936 find_more_contexts_for_caller_subset (node
, &known_contexts
, callers
);
3937 aggvals
= find_aggregate_values_for_callers_subset (node
, callers
);
3938 gcc_checking_assert (ipcp_val_agg_replacement_ok_p (aggvals
, index
,
3939 offset
, val
->value
));
3940 val
->spec_node
= create_specialized_node (node
, known_csts
, known_contexts
,
3942 overall_size
+= val
->local_size_cost
;
3944 /* TODO: If for some lattice there is only one other known value
3945 left, make a special node for it too. */
3950 /* Decide whether and what specialized clones of NODE should be created. */
3953 decide_whether_version_node (struct cgraph_node
*node
)
3955 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3956 int i
, count
= ipa_get_param_count (info
);
3957 vec
<tree
> known_csts
;
3958 vec
<ipa_polymorphic_call_context
> known_contexts
;
3959 vec
<ipa_agg_jump_function
> known_aggs
= vNULL
;
3965 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3966 fprintf (dump_file
, "\nEvaluating opportunities for %s/%i.\n",
3967 node
->name (), node
->order
);
3969 gather_context_independent_values (info
, &known_csts
, &known_contexts
,
3970 info
->do_clone_for_all_contexts
? &known_aggs
3973 for (i
= 0; i
< count
;i
++)
3975 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3976 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
3977 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
3982 ipcp_value
<tree
> *val
;
3983 for (val
= lat
->values
; val
; val
= val
->next
)
3984 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
3988 if (!plats
->aggs_bottom
)
3990 struct ipcp_agg_lattice
*aglat
;
3991 ipcp_value
<tree
> *val
;
3992 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3993 if (!aglat
->bottom
&& aglat
->values
3994 /* If the following is false, the one value is in
3996 && (plats
->aggs_contain_variable
3997 || !aglat
->is_single_const ()))
3998 for (val
= aglat
->values
; val
; val
= val
->next
)
3999 ret
|= decide_about_value (node
, i
, aglat
->offset
, val
,
4000 known_csts
, known_contexts
);
4004 && known_contexts
[i
].useless_p ())
4006 ipcp_value
<ipa_polymorphic_call_context
> *val
;
4007 for (val
= ctxlat
->values
; val
; val
= val
->next
)
4008 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
4012 info
= IPA_NODE_REF (node
);
4015 if (info
->do_clone_for_all_contexts
)
4017 struct cgraph_node
*clone
;
4018 vec
<cgraph_edge
*> callers
;
4021 fprintf (dump_file
, " - Creating a specialized node of %s/%i "
4022 "for all known contexts.\n", node
->name (),
4025 callers
= node
->collect_callers ();
4027 if (!known_contexts_useful_p (known_contexts
))
4029 known_contexts
.release ();
4030 known_contexts
= vNULL
;
4032 clone
= create_specialized_node (node
, known_csts
, known_contexts
,
4033 known_aggs_to_agg_replacement_list (known_aggs
),
4035 info
= IPA_NODE_REF (node
);
4036 info
->do_clone_for_all_contexts
= false;
4037 IPA_NODE_REF (clone
)->is_all_contexts_clone
= true;
4038 for (i
= 0; i
< count
; i
++)
4039 vec_free (known_aggs
[i
].items
);
4040 known_aggs
.release ();
4045 known_csts
.release ();
4046 known_contexts
.release ();
4052 /* Transitively mark all callees of NODE within the same SCC as not dead. */
4055 spread_undeadness (struct cgraph_node
*node
)
4057 struct cgraph_edge
*cs
;
4059 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
4060 if (ipa_edge_within_scc (cs
))
4062 struct cgraph_node
*callee
;
4063 struct ipa_node_params
*info
;
4065 callee
= cs
->callee
->function_symbol (NULL
);
4066 info
= IPA_NODE_REF (callee
);
4068 if (info
->node_dead
)
4070 info
->node_dead
= 0;
4071 spread_undeadness (callee
);
4076 /* Return true if NODE has a caller from outside of its SCC that is not
4077 dead. Worker callback for cgraph_for_node_and_aliases. */
4080 has_undead_caller_from_outside_scc_p (struct cgraph_node
*node
,
4081 void *data ATTRIBUTE_UNUSED
)
4083 struct cgraph_edge
*cs
;
4085 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
4086 if (cs
->caller
->thunk
.thunk_p
4087 && cs
->caller
->call_for_symbol_thunks_and_aliases
4088 (has_undead_caller_from_outside_scc_p
, NULL
, true))
4090 else if (!ipa_edge_within_scc (cs
)
4091 && !IPA_NODE_REF (cs
->caller
)->node_dead
)
4097 /* Identify nodes within the same SCC as NODE which are no longer needed
4098 because of new clones and will be removed as unreachable. */
4101 identify_dead_nodes (struct cgraph_node
*node
)
4103 struct cgraph_node
*v
;
4104 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4105 if (v
->will_be_removed_from_program_if_no_direct_calls_p ()
4106 && !v
->call_for_symbol_thunks_and_aliases
4107 (has_undead_caller_from_outside_scc_p
, NULL
, true))
4108 IPA_NODE_REF (v
)->node_dead
= 1;
4110 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4111 if (!IPA_NODE_REF (v
)->node_dead
)
4112 spread_undeadness (v
);
4114 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4116 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4117 if (IPA_NODE_REF (v
)->node_dead
)
4118 fprintf (dump_file
, " Marking node as dead: %s/%i.\n",
4119 v
->name (), v
->order
);
4123 /* The decision stage. Iterate over the topological order of call graph nodes
4124 TOPO and make specialized clones if deemed beneficial. */
4127 ipcp_decision_stage (struct ipa_topo_info
*topo
)
4132 fprintf (dump_file
, "\nIPA decision stage:\n\n");
4134 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
4136 struct cgraph_node
*node
= topo
->order
[i
];
4137 bool change
= false, iterate
= true;
4141 struct cgraph_node
*v
;
4143 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4144 if (v
->has_gimple_body_p ()
4145 && ipcp_versionable_function_p (v
))
4146 iterate
|= decide_whether_version_node (v
);
4151 identify_dead_nodes (node
);
4155 /* The IPCP driver. */
4160 struct cgraph_2edge_hook_list
*edge_duplication_hook_holder
;
4161 struct cgraph_edge_hook_list
*edge_removal_hook_holder
;
4162 struct ipa_topo_info topo
;
4164 ipa_check_create_node_params ();
4165 ipa_check_create_edge_args ();
4166 grow_edge_clone_vectors ();
4167 edge_duplication_hook_holder
=
4168 symtab
->add_edge_duplication_hook (&ipcp_edge_duplication_hook
, NULL
);
4169 edge_removal_hook_holder
=
4170 symtab
->add_edge_removal_hook (&ipcp_edge_removal_hook
, NULL
);
4172 ipcp_cst_values_pool
= create_alloc_pool ("IPA-CP constant values",
4173 sizeof (ipcp_value
<tree
>), 32);
4174 ipcp_poly_ctx_values_pool
= create_alloc_pool
4175 ("IPA-CP polymorphic contexts",
4176 sizeof (ipcp_value
<ipa_polymorphic_call_context
>), 32);
4177 ipcp_sources_pool
= create_alloc_pool ("IPA-CP value sources",
4178 sizeof (ipcp_value_source
<tree
>), 64);
4179 ipcp_agg_lattice_pool
= create_alloc_pool ("IPA_CP aggregate lattices",
4180 sizeof (struct ipcp_agg_lattice
),
4184 fprintf (dump_file
, "\nIPA structures before propagation:\n");
4185 if (dump_flags
& TDF_DETAILS
)
4186 ipa_print_all_params (dump_file
);
4187 ipa_print_all_jump_functions (dump_file
);
4190 /* Topological sort. */
4191 build_toporder_info (&topo
);
4192 /* Do the interprocedural propagation. */
4193 ipcp_propagate_stage (&topo
);
4194 /* Decide what constant propagation and cloning should be performed. */
4195 ipcp_decision_stage (&topo
);
4197 /* Free all IPCP structures. */
4198 free_toporder_info (&topo
);
4199 next_edge_clone
.release ();
4200 symtab
->remove_edge_removal_hook (edge_removal_hook_holder
);
4201 symtab
->remove_edge_duplication_hook (edge_duplication_hook_holder
);
4202 ipa_free_all_structures_after_ipa_cp ();
4204 fprintf (dump_file
, "\nIPA constant propagation end\n");
4208 /* Initialization and computation of IPCP data structures. This is the initial
4209 intraprocedural analysis of functions, which gathers information to be
4210 propagated later on. */
4213 ipcp_generate_summary (void)
4215 struct cgraph_node
*node
;
4218 fprintf (dump_file
, "\nIPA constant propagation start:\n");
4219 ipa_register_cgraph_hooks ();
4221 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
4223 node
->local
.versionable
4224 = tree_versionable_function_p (node
->decl
);
4225 ipa_analyze_node (node
);
4229 /* Write ipcp summary for nodes in SET. */
4232 ipcp_write_summary (void)
4234 ipa_prop_write_jump_functions ();
4237 /* Read ipcp summary. */
4240 ipcp_read_summary (void)
4242 ipa_prop_read_jump_functions ();
4247 const pass_data pass_data_ipa_cp
=
4249 IPA_PASS
, /* type */
4251 OPTGROUP_NONE
, /* optinfo_flags */
4252 TV_IPA_CONSTANT_PROP
, /* tv_id */
4253 0, /* properties_required */
4254 0, /* properties_provided */
4255 0, /* properties_destroyed */
4256 0, /* todo_flags_start */
4257 ( TODO_dump_symtab
| TODO_remove_functions
), /* todo_flags_finish */
4260 class pass_ipa_cp
: public ipa_opt_pass_d
4263 pass_ipa_cp (gcc::context
*ctxt
)
4264 : ipa_opt_pass_d (pass_data_ipa_cp
, ctxt
,
4265 ipcp_generate_summary
, /* generate_summary */
4266 ipcp_write_summary
, /* write_summary */
4267 ipcp_read_summary
, /* read_summary */
4268 ipa_prop_write_all_agg_replacement
, /*
4269 write_optimization_summary */
4270 ipa_prop_read_all_agg_replacement
, /*
4271 read_optimization_summary */
4272 NULL
, /* stmt_fixup */
4273 0, /* function_transform_todo_flags_start */
4274 ipcp_transform_function
, /* function_transform */
4275 NULL
) /* variable_transform */
4278 /* opt_pass methods: */
4279 virtual bool gate (function
*)
4281 /* FIXME: We should remove the optimize check after we ensure we never run
4282 IPA passes when not optimizing. */
4283 return flag_ipa_cp
&& optimize
;
4286 virtual unsigned int execute (function
*) { return ipcp_driver (); }
4288 }; // class pass_ipa_cp
4293 make_pass_ipa_cp (gcc::context
*ctxt
)
4295 return new pass_ipa_cp (ctxt
);
4298 /* Reset all state within ipa-cp.c so that we can rerun the compiler
4299 within the same process. For use by toplev::finalize. */
4302 ipa_cp_c_finalize (void)