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
) == TREE_BINFO
)
345 fprintf (f
, "BINFO ");
346 print_generic_expr (f
, BINFO_TYPE (v
), 0);
348 else if (TREE_CODE (v
) == ADDR_EXPR
349 && TREE_CODE (TREE_OPERAND (v
, 0)) == CONST_DECL
)
352 print_generic_expr (f
, DECL_INITIAL (TREE_OPERAND (v
, 0)), 0);
355 print_generic_expr (f
, v
, 0);
358 /* Print V which is extracted from a value in a lattice to F. */
361 print_ipcp_constant_value (FILE * f
, ipa_polymorphic_call_context v
)
366 /* Print a lattice LAT to F. */
368 template <typename valtype
>
370 ipcp_lattice
<valtype
>::print (FILE * f
, bool dump_sources
, bool dump_benefits
)
372 ipcp_value
<valtype
> *val
;
377 fprintf (f
, "BOTTOM\n");
381 if (!values_count
&& !contains_variable
)
383 fprintf (f
, "TOP\n");
387 if (contains_variable
)
389 fprintf (f
, "VARIABLE");
395 for (val
= values
; val
; val
= val
->next
)
397 if (dump_benefits
&& prev
)
399 else if (!dump_benefits
&& prev
)
404 print_ipcp_constant_value (f
, val
->value
);
408 ipcp_value_source
<valtype
> *s
;
410 fprintf (f
, " [from:");
411 for (s
= val
->sources
; s
; s
= s
->next
)
412 fprintf (f
, " %i(%i)", s
->cs
->caller
->order
,
418 fprintf (f
, " [loc_time: %i, loc_size: %i, "
419 "prop_time: %i, prop_size: %i]\n",
420 val
->local_time_benefit
, val
->local_size_cost
,
421 val
->prop_time_benefit
, val
->prop_size_cost
);
427 /* Print all ipcp_lattices of all functions to F. */
430 print_all_lattices (FILE * f
, bool dump_sources
, bool dump_benefits
)
432 struct cgraph_node
*node
;
435 fprintf (f
, "\nLattices:\n");
436 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
438 struct ipa_node_params
*info
;
440 info
= IPA_NODE_REF (node
);
441 fprintf (f
, " Node: %s/%i:\n", node
->name (),
443 count
= ipa_get_param_count (info
);
444 for (i
= 0; i
< count
; i
++)
446 struct ipcp_agg_lattice
*aglat
;
447 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
448 fprintf (f
, " param [%d]: ", i
);
449 plats
->itself
.print (f
, dump_sources
, dump_benefits
);
450 fprintf (f
, " ctxs: ");
451 plats
->ctxlat
.print (f
, dump_sources
, dump_benefits
);
452 if (plats
->virt_call
)
453 fprintf (f
, " virt_call flag set\n");
455 if (plats
->aggs_bottom
)
457 fprintf (f
, " AGGS BOTTOM\n");
460 if (plats
->aggs_contain_variable
)
461 fprintf (f
, " AGGS VARIABLE\n");
462 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
464 fprintf (f
, " %soffset " HOST_WIDE_INT_PRINT_DEC
": ",
465 plats
->aggs_by_ref
? "ref " : "", aglat
->offset
);
466 aglat
->print (f
, dump_sources
, dump_benefits
);
472 /* Determine whether it is at all technically possible to create clones of NODE
473 and store this information in the ipa_node_params structure associated
477 determine_versionability (struct cgraph_node
*node
)
479 const char *reason
= NULL
;
481 /* There are a number of generic reasons functions cannot be versioned. We
482 also cannot remove parameters if there are type attributes such as fnspec
484 if (node
->alias
|| node
->thunk
.thunk_p
)
485 reason
= "alias or thunk";
486 else if (!node
->local
.versionable
)
487 reason
= "not a tree_versionable_function";
488 else if (node
->get_availability () <= AVAIL_INTERPOSABLE
)
489 reason
= "insufficient body availability";
490 else if (!opt_for_fn (node
->decl
, optimize
)
491 || !opt_for_fn (node
->decl
, flag_ipa_cp
))
492 reason
= "non-optimized function";
493 else if (lookup_attribute ("omp declare simd", DECL_ATTRIBUTES (node
->decl
)))
495 /* Ideally we should clone the SIMD clones themselves and create
496 vector copies of them, so IPA-cp and SIMD clones can happily
497 coexist, but that may not be worth the effort. */
498 reason
= "function has SIMD clones";
500 /* Don't clone decls local to a comdat group; it breaks and for C++
501 decloned constructors, inlining is always better anyway. */
502 else if (node
->comdat_local_p ())
503 reason
= "comdat-local function";
505 if (reason
&& dump_file
&& !node
->alias
&& !node
->thunk
.thunk_p
)
506 fprintf (dump_file
, "Function %s/%i is not versionable, reason: %s.\n",
507 node
->name (), node
->order
, reason
);
509 node
->local
.versionable
= (reason
== NULL
);
512 /* Return true if it is at all technically possible to create clones of a
516 ipcp_versionable_function_p (struct cgraph_node
*node
)
518 return node
->local
.versionable
;
521 /* Structure holding accumulated information about callers of a node. */
523 struct caller_statistics
526 int n_calls
, n_hot_calls
, freq_sum
;
529 /* Initialize fields of STAT to zeroes. */
532 init_caller_stats (struct caller_statistics
*stats
)
534 stats
->count_sum
= 0;
536 stats
->n_hot_calls
= 0;
540 /* Worker callback of cgraph_for_node_and_aliases accumulating statistics of
541 non-thunk incoming edges to NODE. */
544 gather_caller_stats (struct cgraph_node
*node
, void *data
)
546 struct caller_statistics
*stats
= (struct caller_statistics
*) data
;
547 struct cgraph_edge
*cs
;
549 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
550 if (cs
->caller
->thunk
.thunk_p
)
551 cs
->caller
->call_for_symbol_thunks_and_aliases (gather_caller_stats
,
555 stats
->count_sum
+= cs
->count
;
556 stats
->freq_sum
+= cs
->frequency
;
558 if (cs
->maybe_hot_p ())
559 stats
->n_hot_calls
++;
565 /* Return true if this NODE is viable candidate for cloning. */
568 ipcp_cloning_candidate_p (struct cgraph_node
*node
)
570 struct caller_statistics stats
;
572 gcc_checking_assert (node
->has_gimple_body_p ());
574 if (!flag_ipa_cp_clone
)
577 fprintf (dump_file
, "Not considering %s for cloning; "
578 "-fipa-cp-clone disabled.\n",
583 if (!optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node
->decl
)))
586 fprintf (dump_file
, "Not considering %s for cloning; "
587 "optimizing it for size.\n",
592 init_caller_stats (&stats
);
593 node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
, false);
595 if (inline_summary (node
)->self_size
< stats
.n_calls
)
598 fprintf (dump_file
, "Considering %s for cloning; code might shrink.\n",
603 /* When profile is available and function is hot, propagate into it even if
604 calls seems cold; constant propagation can improve function's speed
608 if (stats
.count_sum
> node
->count
* 90 / 100)
611 fprintf (dump_file
, "Considering %s for cloning; "
612 "usually called directly.\n",
617 if (!stats
.n_hot_calls
)
620 fprintf (dump_file
, "Not considering %s for cloning; no hot calls.\n",
625 fprintf (dump_file
, "Considering %s for cloning.\n",
630 template <typename valtype
>
631 class value_topo_info
634 /* Head of the linked list of topologically sorted values. */
635 ipcp_value
<valtype
> *values_topo
;
636 /* Stack for creating SCCs, represented by a linked list too. */
637 ipcp_value
<valtype
> *stack
;
638 /* Counter driving the algorithm in add_val_to_toposort. */
641 value_topo_info () : values_topo (NULL
), stack (NULL
), dfs_counter (0)
643 void add_val (ipcp_value
<valtype
> *cur_val
);
644 void propagate_effects ();
647 /* Arrays representing a topological ordering of call graph nodes and a stack
648 of nodes used during constant propagation and also data required to perform
649 topological sort of values and propagation of benefits in the determined
655 /* Array with obtained topological order of cgraph nodes. */
656 struct cgraph_node
**order
;
657 /* Stack of cgraph nodes used during propagation within SCC until all values
658 in the SCC stabilize. */
659 struct cgraph_node
**stack
;
660 int nnodes
, stack_top
;
662 value_topo_info
<tree
> constants
;
663 value_topo_info
<ipa_polymorphic_call_context
> contexts
;
665 ipa_topo_info () : order(NULL
), stack(NULL
), nnodes(0), stack_top(0),
670 /* Allocate the arrays in TOPO and topologically sort the nodes into order. */
673 build_toporder_info (struct ipa_topo_info
*topo
)
675 topo
->order
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
676 topo
->stack
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
678 gcc_checking_assert (topo
->stack_top
== 0);
679 topo
->nnodes
= ipa_reduced_postorder (topo
->order
, true, true, NULL
);
682 /* Free information about strongly connected components and the arrays in
686 free_toporder_info (struct ipa_topo_info
*topo
)
688 ipa_free_postorder_info ();
693 /* Add NODE to the stack in TOPO, unless it is already there. */
696 push_node_to_stack (struct ipa_topo_info
*topo
, struct cgraph_node
*node
)
698 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
699 if (info
->node_enqueued
)
701 info
->node_enqueued
= 1;
702 topo
->stack
[topo
->stack_top
++] = node
;
705 /* Pop a node from the stack in TOPO and return it or return NULL if the stack
708 static struct cgraph_node
*
709 pop_node_from_stack (struct ipa_topo_info
*topo
)
713 struct cgraph_node
*node
;
715 node
= topo
->stack
[topo
->stack_top
];
716 IPA_NODE_REF (node
)->node_enqueued
= 0;
723 /* Set lattice LAT to bottom and return true if it previously was not set as
726 template <typename valtype
>
728 ipcp_lattice
<valtype
>::set_to_bottom ()
735 /* Mark lattice as containing an unknown value and return true if it previously
736 was not marked as such. */
738 template <typename valtype
>
740 ipcp_lattice
<valtype
>::set_contains_variable ()
742 bool ret
= !contains_variable
;
743 contains_variable
= true;
747 /* Set all aggegate lattices in PLATS to bottom and return true if they were
748 not previously set as such. */
751 set_agg_lats_to_bottom (struct ipcp_param_lattices
*plats
)
753 bool ret
= !plats
->aggs_bottom
;
754 plats
->aggs_bottom
= true;
758 /* Mark all aggegate lattices in PLATS as containing an unknown value and
759 return true if they were not previously marked as such. */
762 set_agg_lats_contain_variable (struct ipcp_param_lattices
*plats
)
764 bool ret
= !plats
->aggs_contain_variable
;
765 plats
->aggs_contain_variable
= true;
769 /* Mark bot aggregate and scalar lattices as containing an unknown variable,
770 return true is any of them has not been marked as such so far. */
773 set_all_contains_variable (struct ipcp_param_lattices
*plats
)
776 ret
= plats
->itself
.set_contains_variable ();
777 ret
|= plats
->ctxlat
.set_contains_variable ();
778 ret
|= set_agg_lats_contain_variable (plats
);
782 /* Initialize ipcp_lattices. */
785 initialize_node_lattices (struct cgraph_node
*node
)
787 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
788 struct cgraph_edge
*ie
;
789 bool disable
= false, variable
= false;
792 gcc_checking_assert (node
->has_gimple_body_p ());
793 if (!cgraph_local_p (node
))
795 /* When cloning is allowed, we can assume that externally visible
796 functions are not called. We will compensate this by cloning
798 if (ipcp_versionable_function_p (node
)
799 && ipcp_cloning_candidate_p (node
))
805 if (disable
|| variable
)
807 for (i
= 0; i
< ipa_get_param_count (info
) ; i
++)
809 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
812 plats
->itself
.set_to_bottom ();
813 plats
->ctxlat
.set_to_bottom ();
814 set_agg_lats_to_bottom (plats
);
817 set_all_contains_variable (plats
);
819 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
820 && !node
->alias
&& !node
->thunk
.thunk_p
)
821 fprintf (dump_file
, "Marking all lattices of %s/%i as %s\n",
822 node
->name (), node
->order
,
823 disable
? "BOTTOM" : "VARIABLE");
826 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
827 if (ie
->indirect_info
->polymorphic
828 && ie
->indirect_info
->param_index
>= 0)
830 gcc_checking_assert (ie
->indirect_info
->param_index
>= 0);
831 ipa_get_parm_lattices (info
,
832 ie
->indirect_info
->param_index
)->virt_call
= 1;
836 /* Return the result of a (possibly arithmetic) pass through jump function
837 JFUNC on the constant value INPUT. Return NULL_TREE if that cannot be
838 determined or be considered an interprocedural invariant. */
841 ipa_get_jf_pass_through_result (struct ipa_jump_func
*jfunc
, tree input
)
845 if (TREE_CODE (input
) == TREE_BINFO
)
847 if (ipa_get_jf_pass_through_type_preserved (jfunc
))
849 gcc_checking_assert (ipa_get_jf_pass_through_operation (jfunc
)
856 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
859 gcc_checking_assert (is_gimple_ip_invariant (input
));
860 if (TREE_CODE_CLASS (ipa_get_jf_pass_through_operation (jfunc
))
862 restype
= boolean_type_node
;
864 restype
= TREE_TYPE (input
);
865 res
= fold_binary (ipa_get_jf_pass_through_operation (jfunc
), restype
,
866 input
, ipa_get_jf_pass_through_operand (jfunc
));
868 if (res
&& !is_gimple_ip_invariant (res
))
874 /* Return the result of an ancestor jump function JFUNC on the constant value
875 INPUT. Return NULL_TREE if that cannot be determined. */
878 ipa_get_jf_ancestor_result (struct ipa_jump_func
*jfunc
, tree input
)
880 gcc_checking_assert (TREE_CODE (input
) != TREE_BINFO
);
881 if (TREE_CODE (input
) == ADDR_EXPR
)
883 tree t
= TREE_OPERAND (input
, 0);
884 t
= build_ref_for_offset (EXPR_LOCATION (t
), t
,
885 ipa_get_jf_ancestor_offset (jfunc
),
886 ipa_get_jf_ancestor_type (jfunc
)
887 ? ipa_get_jf_ancestor_type (jfunc
)
888 : ptr_type_node
, NULL
, false);
889 return build_fold_addr_expr (t
);
895 /* Determine whether JFUNC evaluates to a single known constant value and if
896 so, return it. Otherwise return NULL. INFO describes the caller node or
897 the one it is inlined to, so that pass-through jump functions can be
901 ipa_value_from_jfunc (struct ipa_node_params
*info
, struct ipa_jump_func
*jfunc
)
903 if (jfunc
->type
== IPA_JF_CONST
)
904 return ipa_get_jf_constant (jfunc
);
905 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
906 || jfunc
->type
== IPA_JF_ANCESTOR
)
911 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
912 idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
914 idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
916 if (info
->ipcp_orig_node
)
917 input
= info
->known_csts
[idx
];
920 ipcp_lattice
<tree
> *lat
;
924 gcc_checking_assert (!flag_ipa_cp
);
927 lat
= ipa_get_scalar_lat (info
, idx
);
928 if (!lat
->is_single_const ())
930 input
= lat
->values
->value
;
936 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
937 return ipa_get_jf_pass_through_result (jfunc
, input
);
939 return ipa_get_jf_ancestor_result (jfunc
, input
);
945 /* Determie whether JFUNC evaluates to single known polymorphic context, given
946 that INFO describes the caller node or the one it is inlined to, CS is the
947 call graph edge corresponding to JFUNC and CSIDX index of the described
950 ipa_polymorphic_call_context
951 ipa_context_from_jfunc (ipa_node_params
*info
, cgraph_edge
*cs
, int csidx
,
952 ipa_jump_func
*jfunc
)
954 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
955 ipa_polymorphic_call_context ctx
;
956 ipa_polymorphic_call_context
*edge_ctx
957 = cs
? ipa_get_ith_polymorhic_call_context (args
, csidx
) : NULL
;
959 if (edge_ctx
&& !edge_ctx
->useless_p ())
962 if (jfunc
->type
== IPA_JF_PASS_THROUGH
963 || jfunc
->type
== IPA_JF_ANCESTOR
)
965 ipa_polymorphic_call_context srcctx
;
967 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
969 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
970 || !ipa_get_jf_pass_through_type_preserved (jfunc
))
972 srcidx
= ipa_get_jf_pass_through_formal_id (jfunc
);
976 if (!ipa_get_jf_ancestor_type_preserved (jfunc
))
978 srcidx
= ipa_get_jf_ancestor_formal_id (jfunc
);
980 if (info
->ipcp_orig_node
)
982 if (info
->known_contexts
.exists ())
983 srcctx
= info
->known_contexts
[srcidx
];
989 gcc_checking_assert (!flag_ipa_cp
);
992 ipcp_lattice
<ipa_polymorphic_call_context
> *lat
;
993 lat
= ipa_get_poly_ctx_lat (info
, srcidx
);
994 if (!lat
->is_single_const ())
996 srcctx
= lat
->values
->value
;
998 if (srcctx
.useless_p ())
1000 if (jfunc
->type
== IPA_JF_ANCESTOR
)
1001 srcctx
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
1002 ctx
.combine_with (srcctx
);
1008 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
1009 bottom, not containing a variable component and without any known value at
1013 ipcp_verify_propagated_values (void)
1015 struct cgraph_node
*node
;
1017 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
1019 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1020 int i
, count
= ipa_get_param_count (info
);
1022 for (i
= 0; i
< count
; i
++)
1024 ipcp_lattice
<tree
> *lat
= ipa_get_scalar_lat (info
, i
);
1027 && !lat
->contains_variable
1028 && lat
->values_count
== 0)
1032 symtab_node::dump_table (dump_file
);
1033 fprintf (dump_file
, "\nIPA lattices after constant "
1034 "propagation, before gcc_unreachable:\n");
1035 print_all_lattices (dump_file
, true, false);
1044 /* Return true iff X and Y should be considered equal values by IPA-CP. */
1047 values_equal_for_ipcp_p (tree x
, tree y
)
1049 gcc_checking_assert (x
!= NULL_TREE
&& y
!= NULL_TREE
);
1054 if (TREE_CODE (x
) == TREE_BINFO
|| TREE_CODE (y
) == TREE_BINFO
)
1057 if (TREE_CODE (x
) == ADDR_EXPR
1058 && TREE_CODE (y
) == ADDR_EXPR
1059 && TREE_CODE (TREE_OPERAND (x
, 0)) == CONST_DECL
1060 && TREE_CODE (TREE_OPERAND (y
, 0)) == CONST_DECL
)
1061 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x
, 0)),
1062 DECL_INITIAL (TREE_OPERAND (y
, 0)), 0);
1064 return operand_equal_p (x
, y
, 0);
1067 /* Return true iff X and Y should be considered equal contexts by IPA-CP. */
1070 values_equal_for_ipcp_p (ipa_polymorphic_call_context x
,
1071 ipa_polymorphic_call_context y
)
1073 return x
.equal_to (y
);
1077 /* Add a new value source to the value represented by THIS, marking that a
1078 value comes from edge CS and (if the underlying jump function is a
1079 pass-through or an ancestor one) from a caller value SRC_VAL of a caller
1080 parameter described by SRC_INDEX. OFFSET is negative if the source was the
1081 scalar value of the parameter itself or the offset within an aggregate. */
1083 template <typename valtype
>
1085 ipcp_value
<valtype
>::add_source (cgraph_edge
*cs
, ipcp_value
*src_val
,
1086 int src_idx
, HOST_WIDE_INT offset
)
1088 ipcp_value_source
<valtype
> *src
;
1090 src
= new (pool_alloc (ipcp_sources_pool
)) ipcp_value_source
<valtype
>;
1091 src
->offset
= offset
;
1094 src
->index
= src_idx
;
1096 src
->next
= sources
;
1100 /* Allocate a new ipcp_value holding a tree constant, initialize its value to
1101 SOURCE and clear all other fields. */
1103 static ipcp_value
<tree
> *
1104 allocate_and_init_ipcp_value (tree source
)
1106 ipcp_value
<tree
> *val
;
1108 val
= new (pool_alloc (ipcp_cst_values_pool
)) ipcp_value
<tree
>;
1109 memset (val
, 0, sizeof (*val
));
1110 val
->value
= source
;
1114 /* Allocate a new ipcp_value holding a polymorphic context, initialize its
1115 value to SOURCE and clear all other fields. */
1117 static ipcp_value
<ipa_polymorphic_call_context
> *
1118 allocate_and_init_ipcp_value (ipa_polymorphic_call_context source
)
1120 ipcp_value
<ipa_polymorphic_call_context
> *val
;
1122 val
= new (pool_alloc (ipcp_poly_ctx_values_pool
))
1123 ipcp_value
<ipa_polymorphic_call_context
>;
1124 memset (val
, 0, sizeof (*val
));
1125 val
->value
= source
;
1129 /* Try to add NEWVAL to LAT, potentially creating a new ipcp_value for it. CS,
1130 SRC_VAL SRC_INDEX and OFFSET are meant for add_source and have the same
1131 meaning. OFFSET -1 means the source is scalar and not a part of an
1134 template <typename valtype
>
1136 ipcp_lattice
<valtype
>::add_value (valtype newval
, cgraph_edge
*cs
,
1137 ipcp_value
<valtype
> *src_val
,
1138 int src_idx
, HOST_WIDE_INT offset
)
1140 ipcp_value
<valtype
> *val
;
1145 for (val
= values
; val
; val
= val
->next
)
1146 if (values_equal_for_ipcp_p (val
->value
, newval
))
1148 if (ipa_edge_within_scc (cs
))
1150 ipcp_value_source
<valtype
> *s
;
1151 for (s
= val
->sources
; s
; s
= s
->next
)
1158 val
->add_source (cs
, src_val
, src_idx
, offset
);
1162 if (values_count
== PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE
))
1164 /* We can only free sources, not the values themselves, because sources
1165 of other values in this this SCC might point to them. */
1166 for (val
= values
; val
; val
= val
->next
)
1168 while (val
->sources
)
1170 ipcp_value_source
<valtype
> *src
= val
->sources
;
1171 val
->sources
= src
->next
;
1172 pool_free (ipcp_sources_pool
, src
);
1177 return set_to_bottom ();
1181 val
= allocate_and_init_ipcp_value (newval
);
1182 val
->add_source (cs
, src_val
, src_idx
, offset
);
1188 /* Propagate values through a pass-through jump function JFUNC associated with
1189 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1190 is the index of the source parameter. */
1193 propagate_vals_accross_pass_through (cgraph_edge
*cs
,
1194 ipa_jump_func
*jfunc
,
1195 ipcp_lattice
<tree
> *src_lat
,
1196 ipcp_lattice
<tree
> *dest_lat
,
1199 ipcp_value
<tree
> *src_val
;
1202 /* Do not create new values when propagating within an SCC because if there
1203 are arithmetic functions with circular dependencies, there is infinite
1204 number of them and we would just make lattices bottom. */
1205 if ((ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1206 && ipa_edge_within_scc (cs
))
1207 ret
= dest_lat
->set_contains_variable ();
1209 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1211 tree cstval
= ipa_get_jf_pass_through_result (jfunc
, src_val
->value
);
1214 ret
|= dest_lat
->add_value (cstval
, cs
, src_val
, src_idx
);
1216 ret
|= dest_lat
->set_contains_variable ();
1222 /* Propagate values through an ancestor jump function JFUNC associated with
1223 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1224 is the index of the source parameter. */
1227 propagate_vals_accross_ancestor (struct cgraph_edge
*cs
,
1228 struct ipa_jump_func
*jfunc
,
1229 ipcp_lattice
<tree
> *src_lat
,
1230 ipcp_lattice
<tree
> *dest_lat
,
1233 ipcp_value
<tree
> *src_val
;
1236 if (ipa_edge_within_scc (cs
))
1237 return dest_lat
->set_contains_variable ();
1239 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1241 tree t
= ipa_get_jf_ancestor_result (jfunc
, src_val
->value
);
1244 ret
|= dest_lat
->add_value (t
, cs
, src_val
, src_idx
);
1246 ret
|= dest_lat
->set_contains_variable ();
1252 /* Propagate scalar values across jump function JFUNC that is associated with
1253 edge CS and put the values into DEST_LAT. */
1256 propagate_scalar_accross_jump_function (struct cgraph_edge
*cs
,
1257 struct ipa_jump_func
*jfunc
,
1258 ipcp_lattice
<tree
> *dest_lat
)
1260 if (dest_lat
->bottom
)
1263 if (jfunc
->type
== IPA_JF_CONST
)
1265 tree val
= ipa_get_jf_constant (jfunc
);
1266 return dest_lat
->add_value (val
, cs
, NULL
, 0);
1268 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1269 || jfunc
->type
== IPA_JF_ANCESTOR
)
1271 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1272 ipcp_lattice
<tree
> *src_lat
;
1276 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1277 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1279 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1281 src_lat
= ipa_get_scalar_lat (caller_info
, src_idx
);
1282 if (src_lat
->bottom
)
1283 return dest_lat
->set_contains_variable ();
1285 /* If we would need to clone the caller and cannot, do not propagate. */
1286 if (!ipcp_versionable_function_p (cs
->caller
)
1287 && (src_lat
->contains_variable
1288 || (src_lat
->values_count
> 1)))
1289 return dest_lat
->set_contains_variable ();
1291 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1292 ret
= propagate_vals_accross_pass_through (cs
, jfunc
, src_lat
,
1295 ret
= propagate_vals_accross_ancestor (cs
, jfunc
, src_lat
, dest_lat
,
1298 if (src_lat
->contains_variable
)
1299 ret
|= dest_lat
->set_contains_variable ();
1304 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1305 use it for indirect inlining), we should propagate them too. */
1306 return dest_lat
->set_contains_variable ();
1309 /* Propagate scalar values across jump function JFUNC that is associated with
1310 edge CS and describes argument IDX and put the values into DEST_LAT. */
1313 propagate_context_accross_jump_function (cgraph_edge
*cs
,
1314 ipa_jump_func
*jfunc
, int idx
,
1315 ipcp_lattice
<ipa_polymorphic_call_context
> *dest_lat
)
1317 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
1318 if (dest_lat
->bottom
)
1321 bool added_sth
= false;
1323 ipa_polymorphic_call_context edge_ctx
, *edge_ctx_ptr
1324 = ipa_get_ith_polymorhic_call_context (args
, idx
);
1328 edge_ctx
= *edge_ctx_ptr
;
1329 edge_ctx
.clear_speculation ();
1332 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1333 || jfunc
->type
== IPA_JF_ANCESTOR
)
1335 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1337 ipcp_lattice
<ipa_polymorphic_call_context
> *src_lat
;
1339 /* TODO: Once we figure out how to propagate speculations, it will
1340 probably be a good idea to switch to speculation if type_preserved is
1341 not set instead of punting. */
1342 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1344 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
1345 || !ipa_get_jf_pass_through_type_preserved (jfunc
))
1347 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1351 if (!ipa_get_jf_ancestor_type_preserved (jfunc
))
1353 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1356 src_lat
= ipa_get_poly_ctx_lat (caller_info
, src_idx
);
1357 /* If we would need to clone the caller and cannot, do not propagate. */
1358 if (!ipcp_versionable_function_p (cs
->caller
)
1359 && (src_lat
->contains_variable
1360 || (src_lat
->values_count
> 1)))
1362 if (src_lat
->contains_variable
)
1363 ret
|= dest_lat
->set_contains_variable ();
1365 ipcp_value
<ipa_polymorphic_call_context
> *src_val
;
1366 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1368 ipa_polymorphic_call_context cur
= src_val
->value
;
1369 if (jfunc
->type
== IPA_JF_ANCESTOR
)
1370 cur
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
1371 /* TODO: Perhaps attempt to look up some used OTR type? */
1372 cur
.clear_speculation ();
1373 if (!edge_ctx
.useless_p ())
1374 cur
.combine_with (edge_ctx
);
1375 if (!cur
.useless_p ())
1377 ret
|= dest_lat
->add_value (cur
, cs
, src_val
, src_idx
);
1387 if (!edge_ctx
.useless_p ())
1388 ret
|= dest_lat
->add_value (edge_ctx
, cs
);
1390 ret
|= dest_lat
->set_contains_variable ();
1396 /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
1397 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
1398 other cases, return false). If there are no aggregate items, set
1399 aggs_by_ref to NEW_AGGS_BY_REF. */
1402 set_check_aggs_by_ref (struct ipcp_param_lattices
*dest_plats
,
1403 bool new_aggs_by_ref
)
1405 if (dest_plats
->aggs
)
1407 if (dest_plats
->aggs_by_ref
!= new_aggs_by_ref
)
1409 set_agg_lats_to_bottom (dest_plats
);
1414 dest_plats
->aggs_by_ref
= new_aggs_by_ref
;
1418 /* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
1419 already existing lattice for the given OFFSET and SIZE, marking all skipped
1420 lattices as containing variable and checking for overlaps. If there is no
1421 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
1422 it with offset, size and contains_variable to PRE_EXISTING, and return true,
1423 unless there are too many already. If there are two many, return false. If
1424 there are overlaps turn whole DEST_PLATS to bottom and return false. If any
1425 skipped lattices were newly marked as containing variable, set *CHANGE to
1429 merge_agg_lats_step (struct ipcp_param_lattices
*dest_plats
,
1430 HOST_WIDE_INT offset
, HOST_WIDE_INT val_size
,
1431 struct ipcp_agg_lattice
***aglat
,
1432 bool pre_existing
, bool *change
)
1434 gcc_checking_assert (offset
>= 0);
1436 while (**aglat
&& (**aglat
)->offset
< offset
)
1438 if ((**aglat
)->offset
+ (**aglat
)->size
> offset
)
1440 set_agg_lats_to_bottom (dest_plats
);
1443 *change
|= (**aglat
)->set_contains_variable ();
1444 *aglat
= &(**aglat
)->next
;
1447 if (**aglat
&& (**aglat
)->offset
== offset
)
1449 if ((**aglat
)->size
!= val_size
1451 && (**aglat
)->next
->offset
< offset
+ val_size
))
1453 set_agg_lats_to_bottom (dest_plats
);
1456 gcc_checking_assert (!(**aglat
)->next
1457 || (**aglat
)->next
->offset
>= offset
+ val_size
);
1462 struct ipcp_agg_lattice
*new_al
;
1464 if (**aglat
&& (**aglat
)->offset
< offset
+ val_size
)
1466 set_agg_lats_to_bottom (dest_plats
);
1469 if (dest_plats
->aggs_count
== PARAM_VALUE (PARAM_IPA_MAX_AGG_ITEMS
))
1471 dest_plats
->aggs_count
++;
1472 new_al
= (struct ipcp_agg_lattice
*) pool_alloc (ipcp_agg_lattice_pool
);
1473 memset (new_al
, 0, sizeof (*new_al
));
1475 new_al
->offset
= offset
;
1476 new_al
->size
= val_size
;
1477 new_al
->contains_variable
= pre_existing
;
1479 new_al
->next
= **aglat
;
1485 /* Set all AGLAT and all other aggregate lattices reachable by next pointers as
1486 containing an unknown value. */
1489 set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice
*aglat
)
1494 ret
|= aglat
->set_contains_variable ();
1495 aglat
= aglat
->next
;
1500 /* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
1501 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source
1502 parameter used for lattice value sources. Return true if DEST_PLATS changed
1506 merge_aggregate_lattices (struct cgraph_edge
*cs
,
1507 struct ipcp_param_lattices
*dest_plats
,
1508 struct ipcp_param_lattices
*src_plats
,
1509 int src_idx
, HOST_WIDE_INT offset_delta
)
1511 bool pre_existing
= dest_plats
->aggs
!= NULL
;
1512 struct ipcp_agg_lattice
**dst_aglat
;
1515 if (set_check_aggs_by_ref (dest_plats
, src_plats
->aggs_by_ref
))
1517 if (src_plats
->aggs_bottom
)
1518 return set_agg_lats_contain_variable (dest_plats
);
1519 if (src_plats
->aggs_contain_variable
)
1520 ret
|= set_agg_lats_contain_variable (dest_plats
);
1521 dst_aglat
= &dest_plats
->aggs
;
1523 for (struct ipcp_agg_lattice
*src_aglat
= src_plats
->aggs
;
1525 src_aglat
= src_aglat
->next
)
1527 HOST_WIDE_INT new_offset
= src_aglat
->offset
- offset_delta
;
1531 if (merge_agg_lats_step (dest_plats
, new_offset
, src_aglat
->size
,
1532 &dst_aglat
, pre_existing
, &ret
))
1534 struct ipcp_agg_lattice
*new_al
= *dst_aglat
;
1536 dst_aglat
= &(*dst_aglat
)->next
;
1537 if (src_aglat
->bottom
)
1539 ret
|= new_al
->set_contains_variable ();
1542 if (src_aglat
->contains_variable
)
1543 ret
|= new_al
->set_contains_variable ();
1544 for (ipcp_value
<tree
> *val
= src_aglat
->values
;
1547 ret
|= new_al
->add_value (val
->value
, cs
, val
, src_idx
,
1550 else if (dest_plats
->aggs_bottom
)
1553 ret
|= set_chain_of_aglats_contains_variable (*dst_aglat
);
1557 /* Determine whether there is anything to propagate FROM SRC_PLATS through a
1558 pass-through JFUNC and if so, whether it has conform and conforms to the
1559 rules about propagating values passed by reference. */
1562 agg_pass_through_permissible_p (struct ipcp_param_lattices
*src_plats
,
1563 struct ipa_jump_func
*jfunc
)
1565 return src_plats
->aggs
1566 && (!src_plats
->aggs_by_ref
1567 || ipa_get_jf_pass_through_agg_preserved (jfunc
));
1570 /* Propagate scalar values across jump function JFUNC that is associated with
1571 edge CS and put the values into DEST_LAT. */
1574 propagate_aggs_accross_jump_function (struct cgraph_edge
*cs
,
1575 struct ipa_jump_func
*jfunc
,
1576 struct ipcp_param_lattices
*dest_plats
)
1580 if (dest_plats
->aggs_bottom
)
1583 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1584 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
1586 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1587 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1588 struct ipcp_param_lattices
*src_plats
;
1590 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
1591 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
1593 /* Currently we do not produce clobber aggregate jump
1594 functions, replace with merging when we do. */
1595 gcc_assert (!jfunc
->agg
.items
);
1596 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
,
1600 ret
|= set_agg_lats_contain_variable (dest_plats
);
1602 else if (jfunc
->type
== IPA_JF_ANCESTOR
1603 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
1605 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1606 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1607 struct ipcp_param_lattices
*src_plats
;
1609 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
1610 if (src_plats
->aggs
&& src_plats
->aggs_by_ref
)
1612 /* Currently we do not produce clobber aggregate jump
1613 functions, replace with merging when we do. */
1614 gcc_assert (!jfunc
->agg
.items
);
1615 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
, src_idx
,
1616 ipa_get_jf_ancestor_offset (jfunc
));
1618 else if (!src_plats
->aggs_by_ref
)
1619 ret
|= set_agg_lats_to_bottom (dest_plats
);
1621 ret
|= set_agg_lats_contain_variable (dest_plats
);
1623 else if (jfunc
->agg
.items
)
1625 bool pre_existing
= dest_plats
->aggs
!= NULL
;
1626 struct ipcp_agg_lattice
**aglat
= &dest_plats
->aggs
;
1627 struct ipa_agg_jf_item
*item
;
1630 if (set_check_aggs_by_ref (dest_plats
, jfunc
->agg
.by_ref
))
1633 FOR_EACH_VEC_ELT (*jfunc
->agg
.items
, i
, item
)
1635 HOST_WIDE_INT val_size
;
1637 if (item
->offset
< 0)
1639 gcc_checking_assert (is_gimple_ip_invariant (item
->value
));
1640 val_size
= tree_to_uhwi (TYPE_SIZE (TREE_TYPE (item
->value
)));
1642 if (merge_agg_lats_step (dest_plats
, item
->offset
, val_size
,
1643 &aglat
, pre_existing
, &ret
))
1645 ret
|= (*aglat
)->add_value (item
->value
, cs
, NULL
, 0, 0);
1646 aglat
= &(*aglat
)->next
;
1648 else if (dest_plats
->aggs_bottom
)
1652 ret
|= set_chain_of_aglats_contains_variable (*aglat
);
1655 ret
|= set_agg_lats_contain_variable (dest_plats
);
1660 /* Propagate constants from the caller to the callee of CS. INFO describes the
1664 propagate_constants_accross_call (struct cgraph_edge
*cs
)
1666 struct ipa_node_params
*callee_info
;
1667 enum availability availability
;
1668 struct cgraph_node
*callee
, *alias_or_thunk
;
1669 struct ipa_edge_args
*args
;
1671 int i
, args_count
, parms_count
;
1673 callee
= cs
->callee
->function_symbol (&availability
);
1674 if (!callee
->definition
)
1676 gcc_checking_assert (callee
->has_gimple_body_p ());
1677 callee_info
= IPA_NODE_REF (callee
);
1679 args
= IPA_EDGE_REF (cs
);
1680 args_count
= ipa_get_cs_argument_count (args
);
1681 parms_count
= ipa_get_param_count (callee_info
);
1682 if (parms_count
== 0)
1685 /* No propagation through instrumentation thunks is available yet.
1686 It should be possible with proper mapping of call args and
1687 instrumented callee params in the propagation loop below. But
1688 this case mostly occurs when legacy code calls instrumented code
1689 and it is not a primary target for optimizations.
1690 We detect instrumentation thunks in aliases and thunks chain by
1691 checking instrumentation_clone flag for chain source and target.
1692 Going through instrumentation thunks we always have it changed
1693 from 0 to 1 and all other nodes do not change it. */
1694 if (!cs
->callee
->instrumentation_clone
1695 && callee
->instrumentation_clone
)
1697 for (i
= 0; i
< parms_count
; i
++)
1698 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
1703 /* If this call goes through a thunk we must not propagate to the first (0th)
1704 parameter. However, we might need to uncover a thunk from below a series
1705 of aliases first. */
1706 alias_or_thunk
= cs
->callee
;
1707 while (alias_or_thunk
->alias
)
1708 alias_or_thunk
= alias_or_thunk
->get_alias_target ();
1709 if (alias_or_thunk
->thunk
.thunk_p
)
1711 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
1718 for (; (i
< args_count
) && (i
< parms_count
); i
++)
1720 struct ipa_jump_func
*jump_func
= ipa_get_ith_jump_func (args
, i
);
1721 struct ipcp_param_lattices
*dest_plats
;
1723 dest_plats
= ipa_get_parm_lattices (callee_info
, i
);
1724 if (availability
== AVAIL_INTERPOSABLE
)
1725 ret
|= set_all_contains_variable (dest_plats
);
1728 ret
|= propagate_scalar_accross_jump_function (cs
, jump_func
,
1729 &dest_plats
->itself
);
1730 ret
|= propagate_context_accross_jump_function (cs
, jump_func
, i
,
1731 &dest_plats
->ctxlat
);
1732 ret
|= propagate_aggs_accross_jump_function (cs
, jump_func
,
1736 for (; i
< parms_count
; i
++)
1737 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
, i
));
1742 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
1743 (which can contain both constants and binfos), KNOWN_CONTEXTS, KNOWN_AGGS or
1744 AGG_REPS return the destination. The latter three can be NULL. If AGG_REPS
1745 is not NULL, KNOWN_AGGS is ignored. */
1748 ipa_get_indirect_edge_target_1 (struct cgraph_edge
*ie
,
1749 vec
<tree
> known_csts
,
1750 vec
<ipa_polymorphic_call_context
> known_contexts
,
1751 vec
<ipa_agg_jump_function_p
> known_aggs
,
1752 struct ipa_agg_replacement_value
*agg_reps
)
1754 int param_index
= ie
->indirect_info
->param_index
;
1755 HOST_WIDE_INT anc_offset
;
1759 if (param_index
== -1
1760 || known_csts
.length () <= (unsigned int) param_index
)
1763 if (!ie
->indirect_info
->polymorphic
)
1767 if (ie
->indirect_info
->agg_contents
)
1774 if (agg_reps
->index
== param_index
1775 && agg_reps
->offset
== ie
->indirect_info
->offset
1776 && agg_reps
->by_ref
== ie
->indirect_info
->by_ref
)
1778 t
= agg_reps
->value
;
1781 agg_reps
= agg_reps
->next
;
1784 else if (known_aggs
.length () > (unsigned int) param_index
)
1786 struct ipa_agg_jump_function
*agg
;
1787 agg
= known_aggs
[param_index
];
1788 t
= ipa_find_agg_cst_for_param (agg
, ie
->indirect_info
->offset
,
1789 ie
->indirect_info
->by_ref
);
1795 t
= known_csts
[param_index
];
1798 TREE_CODE (t
) == ADDR_EXPR
1799 && TREE_CODE (TREE_OPERAND (t
, 0)) == FUNCTION_DECL
)
1800 return TREE_OPERAND (t
, 0);
1805 if (!flag_devirtualize
)
1808 gcc_assert (!ie
->indirect_info
->agg_contents
);
1809 anc_offset
= ie
->indirect_info
->offset
;
1813 /* Try to work out value of virtual table pointer value in replacemnets. */
1814 if (!t
&& agg_reps
&& !ie
->indirect_info
->by_ref
1815 && !ie
->indirect_info
->vptr_changed
)
1819 if (agg_reps
->index
== param_index
1820 && agg_reps
->offset
== ie
->indirect_info
->offset
1821 && agg_reps
->by_ref
)
1823 t
= agg_reps
->value
;
1826 agg_reps
= agg_reps
->next
;
1830 /* Try to work out value of virtual table pointer value in known
1831 aggregate values. */
1832 if (!t
&& known_aggs
.length () > (unsigned int) param_index
1833 && !ie
->indirect_info
->by_ref
1834 && !ie
->indirect_info
->vptr_changed
)
1836 struct ipa_agg_jump_function
*agg
;
1837 agg
= known_aggs
[param_index
];
1838 t
= ipa_find_agg_cst_for_param (agg
, ie
->indirect_info
->offset
,
1842 /* If we found the virtual table pointer, lookup the target. */
1846 unsigned HOST_WIDE_INT offset
;
1847 if (vtable_pointer_value_to_vtable (t
, &vtable
, &offset
))
1849 target
= gimple_get_virt_method_for_vtable (ie
->indirect_info
->otr_token
,
1853 if ((TREE_CODE (TREE_TYPE (target
)) == FUNCTION_TYPE
1854 && DECL_FUNCTION_CODE (target
) == BUILT_IN_UNREACHABLE
)
1855 || !possible_polymorphic_call_target_p
1856 (ie
, cgraph_node::get (target
)))
1857 target
= ipa_impossible_devirt_target (ie
, target
);
1863 /* Do we know the constant value of pointer? */
1865 t
= known_csts
[param_index
];
1867 gcc_checking_assert (!t
|| TREE_CODE (t
) != TREE_BINFO
);
1869 ipa_polymorphic_call_context context
;
1870 if (known_contexts
.length () > (unsigned int) param_index
)
1872 context
= known_contexts
[param_index
];
1875 ipa_polymorphic_call_context ctx2
= ipa_polymorphic_call_context
1876 (t
, ie
->indirect_info
->otr_type
, anc_offset
);
1877 if (!ctx2
.useless_p ())
1878 context
.combine_with (ctx2
, ie
->indirect_info
->otr_type
);
1882 context
= ipa_polymorphic_call_context (t
, ie
->indirect_info
->otr_type
,
1887 vec
<cgraph_node
*>targets
;
1890 targets
= possible_polymorphic_call_targets
1891 (ie
->indirect_info
->otr_type
,
1892 ie
->indirect_info
->otr_token
,
1894 if (!final
|| targets
.length () > 1)
1896 if (targets
.length () == 1)
1897 target
= targets
[0]->decl
;
1899 target
= ipa_impossible_devirt_target (ie
, NULL_TREE
);
1901 if (target
&& !possible_polymorphic_call_target_p (ie
,
1902 cgraph_node::get (target
)))
1903 target
= ipa_impossible_devirt_target (ie
, target
);
1909 /* If an indirect edge IE can be turned into a direct one based on KNOWN_CSTS,
1910 KNOWN_CONTEXTS (which can be vNULL) or KNOWN_AGGS (which also can be vNULL)
1911 return the destination. */
1914 ipa_get_indirect_edge_target (struct cgraph_edge
*ie
,
1915 vec
<tree
> known_csts
,
1916 vec
<ipa_polymorphic_call_context
> known_contexts
,
1917 vec
<ipa_agg_jump_function_p
> known_aggs
)
1919 return ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
1923 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
1924 and KNOWN_CONTEXTS. */
1927 devirtualization_time_bonus (struct cgraph_node
*node
,
1928 vec
<tree
> known_csts
,
1929 vec
<ipa_polymorphic_call_context
> known_contexts
,
1930 vec
<ipa_agg_jump_function_p
> known_aggs
)
1932 struct cgraph_edge
*ie
;
1935 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
1937 struct cgraph_node
*callee
;
1938 struct inline_summary
*isummary
;
1939 enum availability avail
;
1942 target
= ipa_get_indirect_edge_target (ie
, known_csts
, known_contexts
,
1947 /* Only bare minimum benefit for clearly un-inlineable targets. */
1949 callee
= cgraph_node::get (target
);
1950 if (!callee
|| !callee
->definition
)
1952 callee
= callee
->function_symbol (&avail
);
1953 if (avail
< AVAIL_AVAILABLE
)
1955 isummary
= inline_summary (callee
);
1956 if (!isummary
->inlinable
)
1959 /* FIXME: The values below need re-considering and perhaps also
1960 integrating into the cost metrics, at lest in some very basic way. */
1961 if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 4)
1963 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 2)
1965 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
1966 || DECL_DECLARED_INLINE_P (callee
->decl
))
1973 /* Return time bonus incurred because of HINTS. */
1976 hint_time_bonus (inline_hints hints
)
1979 if (hints
& (INLINE_HINT_loop_iterations
| INLINE_HINT_loop_stride
))
1980 result
+= PARAM_VALUE (PARAM_IPA_CP_LOOP_HINT_BONUS
);
1981 if (hints
& INLINE_HINT_array_index
)
1982 result
+= PARAM_VALUE (PARAM_IPA_CP_ARRAY_INDEX_HINT_BONUS
);
1986 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
1987 and SIZE_COST and with the sum of frequencies of incoming edges to the
1988 potential new clone in FREQUENCIES. */
1991 good_cloning_opportunity_p (struct cgraph_node
*node
, int time_benefit
,
1992 int freq_sum
, gcov_type count_sum
, int size_cost
)
1994 if (time_benefit
== 0
1995 || !flag_ipa_cp_clone
1996 || !optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node
->decl
)))
1999 gcc_assert (size_cost
> 0);
2003 int factor
= (count_sum
* 1000) / max_count
;
2004 int64_t evaluation
= (((int64_t) time_benefit
* factor
)
2007 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2008 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
2009 "size: %i, count_sum: " HOST_WIDE_INT_PRINT_DEC
2010 ") -> evaluation: " "%"PRId64
2011 ", threshold: %i\n",
2012 time_benefit
, size_cost
, (HOST_WIDE_INT
) count_sum
,
2013 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
2015 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
2019 int64_t evaluation
= (((int64_t) time_benefit
* freq_sum
)
2022 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2023 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
2024 "size: %i, freq_sum: %i) -> evaluation: "
2025 "%"PRId64
", threshold: %i\n",
2026 time_benefit
, size_cost
, freq_sum
, evaluation
,
2027 PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
2029 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
2033 /* Return all context independent values from aggregate lattices in PLATS in a
2034 vector. Return NULL if there are none. */
2036 static vec
<ipa_agg_jf_item
, va_gc
> *
2037 context_independent_aggregate_values (struct ipcp_param_lattices
*plats
)
2039 vec
<ipa_agg_jf_item
, va_gc
> *res
= NULL
;
2041 if (plats
->aggs_bottom
2042 || plats
->aggs_contain_variable
2043 || plats
->aggs_count
== 0)
2046 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
;
2048 aglat
= aglat
->next
)
2049 if (aglat
->is_single_const ())
2051 struct ipa_agg_jf_item item
;
2052 item
.offset
= aglat
->offset
;
2053 item
.value
= aglat
->values
->value
;
2054 vec_safe_push (res
, item
);
2059 /* Allocate KNOWN_CSTS, KNOWN_CONTEXTS and, if non-NULL, KNOWN_AGGS and
2060 populate them with values of parameters that are known independent of the
2061 context. INFO describes the function. If REMOVABLE_PARAMS_COST is
2062 non-NULL, the movement cost of all removable parameters will be stored in
2066 gather_context_independent_values (struct ipa_node_params
*info
,
2067 vec
<tree
> *known_csts
,
2068 vec
<ipa_polymorphic_call_context
>
2070 vec
<ipa_agg_jump_function
> *known_aggs
,
2071 int *removable_params_cost
)
2073 int i
, count
= ipa_get_param_count (info
);
2076 known_csts
->create (0);
2077 known_contexts
->create (0);
2078 known_csts
->safe_grow_cleared (count
);
2079 known_contexts
->safe_grow_cleared (count
);
2082 known_aggs
->create (0);
2083 known_aggs
->safe_grow_cleared (count
);
2086 if (removable_params_cost
)
2087 *removable_params_cost
= 0;
2089 for (i
= 0; i
< count
; i
++)
2091 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2092 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
2094 if (lat
->is_single_const ())
2096 ipcp_value
<tree
> *val
= lat
->values
;
2097 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
2098 (*known_csts
)[i
] = val
->value
;
2099 if (removable_params_cost
)
2100 *removable_params_cost
2101 += estimate_move_cost (TREE_TYPE (val
->value
), false);
2104 else if (removable_params_cost
2105 && !ipa_is_param_used (info
, i
))
2106 *removable_params_cost
2107 += ipa_get_param_move_cost (info
, i
);
2109 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
2110 if (ctxlat
->is_single_const ())
2112 (*known_contexts
)[i
] = ctxlat
->values
->value
;
2118 vec
<ipa_agg_jf_item
, va_gc
> *agg_items
;
2119 struct ipa_agg_jump_function
*ajf
;
2121 agg_items
= context_independent_aggregate_values (plats
);
2122 ajf
= &(*known_aggs
)[i
];
2123 ajf
->items
= agg_items
;
2124 ajf
->by_ref
= plats
->aggs_by_ref
;
2125 ret
|= agg_items
!= NULL
;
2132 /* The current interface in ipa-inline-analysis requires a pointer vector.
2135 FIXME: That interface should be re-worked, this is slightly silly. Still,
2136 I'd like to discuss how to change it first and this demonstrates the
2139 static vec
<ipa_agg_jump_function_p
>
2140 agg_jmp_p_vec_for_t_vec (vec
<ipa_agg_jump_function
> known_aggs
)
2142 vec
<ipa_agg_jump_function_p
> ret
;
2143 struct ipa_agg_jump_function
*ajf
;
2146 ret
.create (known_aggs
.length ());
2147 FOR_EACH_VEC_ELT (known_aggs
, i
, ajf
)
2148 ret
.quick_push (ajf
);
2152 /* Perform time and size measurement of NODE with the context given in
2153 KNOWN_CSTS, KNOWN_CONTEXTS and KNOWN_AGGS, calculate the benefit and cost
2154 given BASE_TIME of the node without specialization, REMOVABLE_PARAMS_COST of
2155 all context-independent removable parameters and EST_MOVE_COST of estimated
2156 movement of the considered parameter and store it into VAL. */
2159 perform_estimation_of_a_value (cgraph_node
*node
, vec
<tree
> known_csts
,
2160 vec
<ipa_polymorphic_call_context
> known_contexts
,
2161 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
,
2162 int base_time
, int removable_params_cost
,
2163 int est_move_cost
, ipcp_value_base
*val
)
2165 int time
, size
, time_benefit
;
2168 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
2169 known_aggs_ptrs
, &size
, &time
,
2171 time_benefit
= base_time
- time
2172 + devirtualization_time_bonus (node
, known_csts
, known_contexts
,
2174 + hint_time_bonus (hints
)
2175 + removable_params_cost
+ est_move_cost
;
2177 gcc_checking_assert (size
>=0);
2178 /* The inliner-heuristics based estimates may think that in certain
2179 contexts some functions do not have any size at all but we want
2180 all specializations to have at least a tiny cost, not least not to
2185 val
->local_time_benefit
= time_benefit
;
2186 val
->local_size_cost
= size
;
2189 /* Iterate over known values of parameters of NODE and estimate the local
2190 effects in terms of time and size they have. */
2193 estimate_local_effects (struct cgraph_node
*node
)
2195 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2196 int i
, count
= ipa_get_param_count (info
);
2197 vec
<tree
> known_csts
;
2198 vec
<ipa_polymorphic_call_context
> known_contexts
;
2199 vec
<ipa_agg_jump_function
> known_aggs
;
2200 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
;
2202 int base_time
= inline_summary (node
)->time
;
2203 int removable_params_cost
;
2205 if (!count
|| !ipcp_versionable_function_p (node
))
2208 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2209 fprintf (dump_file
, "\nEstimating effects for %s/%i, base_time: %i.\n",
2210 node
->name (), node
->order
, base_time
);
2212 always_const
= gather_context_independent_values (info
, &known_csts
,
2213 &known_contexts
, &known_aggs
,
2214 &removable_params_cost
);
2215 known_aggs_ptrs
= agg_jmp_p_vec_for_t_vec (known_aggs
);
2218 struct caller_statistics stats
;
2222 init_caller_stats (&stats
);
2223 node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
2225 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
2226 known_aggs_ptrs
, &size
, &time
, &hints
);
2227 time
-= devirtualization_time_bonus (node
, known_csts
, known_contexts
,
2229 time
-= hint_time_bonus (hints
);
2230 time
-= removable_params_cost
;
2231 size
-= stats
.n_calls
* removable_params_cost
;
2234 fprintf (dump_file
, " - context independent values, size: %i, "
2235 "time_benefit: %i\n", size
, base_time
- time
);
2238 || node
->will_be_removed_from_program_if_no_direct_calls_p ())
2240 info
->do_clone_for_all_contexts
= true;
2244 fprintf (dump_file
, " Decided to specialize for all "
2245 "known contexts, code not going to grow.\n");
2247 else if (good_cloning_opportunity_p (node
, base_time
- time
,
2248 stats
.freq_sum
, stats
.count_sum
,
2251 if (size
+ overall_size
<= max_new_size
)
2253 info
->do_clone_for_all_contexts
= true;
2255 overall_size
+= size
;
2258 fprintf (dump_file
, " Decided to specialize for all "
2259 "known contexts, growth deemed beneficial.\n");
2261 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2262 fprintf (dump_file
, " Not cloning for all contexts because "
2263 "max_new_size would be reached with %li.\n",
2264 size
+ overall_size
);
2268 for (i
= 0; i
< count
; i
++)
2270 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2271 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
2272 ipcp_value
<tree
> *val
;
2279 for (val
= lat
->values
; val
; val
= val
->next
)
2281 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
2282 known_csts
[i
] = val
->value
;
2284 int emc
= estimate_move_cost (TREE_TYPE (val
->value
), true);
2285 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
2286 known_aggs_ptrs
, base_time
,
2287 removable_params_cost
, emc
, val
);
2289 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2291 fprintf (dump_file
, " - estimates for value ");
2292 print_ipcp_constant_value (dump_file
, val
->value
);
2293 fprintf (dump_file
, " for ");
2294 ipa_dump_param (dump_file
, info
, i
);
2295 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
2296 val
->local_time_benefit
, val
->local_size_cost
);
2299 known_csts
[i
] = NULL_TREE
;
2302 for (i
= 0; i
< count
; i
++)
2304 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2306 if (!plats
->virt_call
)
2309 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
2310 ipcp_value
<ipa_polymorphic_call_context
> *val
;
2314 || !known_contexts
[i
].useless_p ())
2317 for (val
= ctxlat
->values
; val
; val
= val
->next
)
2319 known_contexts
[i
] = val
->value
;
2320 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
2321 known_aggs_ptrs
, base_time
,
2322 removable_params_cost
, 0, val
);
2324 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2326 fprintf (dump_file
, " - estimates for polymorphic context ");
2327 print_ipcp_constant_value (dump_file
, val
->value
);
2328 fprintf (dump_file
, " for ");
2329 ipa_dump_param (dump_file
, info
, i
);
2330 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
2331 val
->local_time_benefit
, val
->local_size_cost
);
2334 known_contexts
[i
] = ipa_polymorphic_call_context ();
2337 for (i
= 0; i
< count
; i
++)
2339 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2340 struct ipa_agg_jump_function
*ajf
;
2341 struct ipcp_agg_lattice
*aglat
;
2343 if (plats
->aggs_bottom
|| !plats
->aggs
)
2346 ajf
= &known_aggs
[i
];
2347 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2349 ipcp_value
<tree
> *val
;
2350 if (aglat
->bottom
|| !aglat
->values
2351 /* If the following is true, the one value is in known_aggs. */
2352 || (!plats
->aggs_contain_variable
2353 && aglat
->is_single_const ()))
2356 for (val
= aglat
->values
; val
; val
= val
->next
)
2358 struct ipa_agg_jf_item item
;
2360 item
.offset
= aglat
->offset
;
2361 item
.value
= val
->value
;
2362 vec_safe_push (ajf
->items
, item
);
2364 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
2365 known_aggs_ptrs
, base_time
,
2366 removable_params_cost
, 0, val
);
2368 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2370 fprintf (dump_file
, " - estimates for value ");
2371 print_ipcp_constant_value (dump_file
, val
->value
);
2372 fprintf (dump_file
, " for ");
2373 ipa_dump_param (dump_file
, info
, i
);
2374 fprintf (dump_file
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
2375 "]: time_benefit: %i, size: %i\n",
2376 plats
->aggs_by_ref
? "ref " : "",
2378 val
->local_time_benefit
, val
->local_size_cost
);
2386 for (i
= 0; i
< count
; i
++)
2387 vec_free (known_aggs
[i
].items
);
2389 known_csts
.release ();
2390 known_contexts
.release ();
2391 known_aggs
.release ();
2392 known_aggs_ptrs
.release ();
2396 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
2397 topological sort of values. */
2399 template <typename valtype
>
2401 value_topo_info
<valtype
>::add_val (ipcp_value
<valtype
> *cur_val
)
2403 ipcp_value_source
<valtype
> *src
;
2409 cur_val
->dfs
= dfs_counter
;
2410 cur_val
->low_link
= dfs_counter
;
2412 cur_val
->topo_next
= stack
;
2414 cur_val
->on_stack
= true;
2416 for (src
= cur_val
->sources
; src
; src
= src
->next
)
2419 if (src
->val
->dfs
== 0)
2422 if (src
->val
->low_link
< cur_val
->low_link
)
2423 cur_val
->low_link
= src
->val
->low_link
;
2425 else if (src
->val
->on_stack
2426 && src
->val
->dfs
< cur_val
->low_link
)
2427 cur_val
->low_link
= src
->val
->dfs
;
2430 if (cur_val
->dfs
== cur_val
->low_link
)
2432 ipcp_value
<valtype
> *v
, *scc_list
= NULL
;
2437 stack
= v
->topo_next
;
2438 v
->on_stack
= false;
2440 v
->scc_next
= scc_list
;
2443 while (v
!= cur_val
);
2445 cur_val
->topo_next
= values_topo
;
2446 values_topo
= cur_val
;
2450 /* Add all values in lattices associated with NODE to the topological sort if
2451 they are not there yet. */
2454 add_all_node_vals_to_toposort (cgraph_node
*node
, ipa_topo_info
*topo
)
2456 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2457 int i
, count
= ipa_get_param_count (info
);
2459 for (i
= 0; i
< count
; i
++)
2461 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2462 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
2463 struct ipcp_agg_lattice
*aglat
;
2467 ipcp_value
<tree
> *val
;
2468 for (val
= lat
->values
; val
; val
= val
->next
)
2469 topo
->constants
.add_val (val
);
2472 if (!plats
->aggs_bottom
)
2473 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2476 ipcp_value
<tree
> *val
;
2477 for (val
= aglat
->values
; val
; val
= val
->next
)
2478 topo
->constants
.add_val (val
);
2481 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
2482 if (!ctxlat
->bottom
)
2484 ipcp_value
<ipa_polymorphic_call_context
> *ctxval
;
2485 for (ctxval
= ctxlat
->values
; ctxval
; ctxval
= ctxval
->next
)
2486 topo
->contexts
.add_val (ctxval
);
2491 /* One pass of constants propagation along the call graph edges, from callers
2492 to callees (requires topological ordering in TOPO), iterate over strongly
2493 connected components. */
2496 propagate_constants_topo (struct ipa_topo_info
*topo
)
2500 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
2503 struct cgraph_node
*v
, *node
= topo
->order
[i
];
2504 vec
<cgraph_node
*> cycle_nodes
= ipa_get_nodes_in_cycle (node
);
2506 /* First, iteratively propagate within the strongly connected component
2507 until all lattices stabilize. */
2508 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
2509 if (v
->has_gimple_body_p ())
2510 push_node_to_stack (topo
, v
);
2512 v
= pop_node_from_stack (topo
);
2515 struct cgraph_edge
*cs
;
2517 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
2518 if (ipa_edge_within_scc (cs
)
2519 && propagate_constants_accross_call (cs
))
2520 push_node_to_stack (topo
, cs
->callee
);
2521 v
= pop_node_from_stack (topo
);
2524 /* Afterwards, propagate along edges leading out of the SCC, calculates
2525 the local effects of the discovered constants and all valid values to
2526 their topological sort. */
2527 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
2528 if (v
->has_gimple_body_p ())
2530 struct cgraph_edge
*cs
;
2532 estimate_local_effects (v
);
2533 add_all_node_vals_to_toposort (v
, topo
);
2534 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
2535 if (!ipa_edge_within_scc (cs
))
2536 propagate_constants_accross_call (cs
);
2538 cycle_nodes
.release ();
2543 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
2544 the bigger one if otherwise. */
2547 safe_add (int a
, int b
)
2549 if (a
> INT_MAX
/2 || b
> INT_MAX
/2)
2550 return a
> b
? a
: b
;
2556 /* Propagate the estimated effects of individual values along the topological
2557 from the dependent values to those they depend on. */
2559 template <typename valtype
>
2561 value_topo_info
<valtype
>::propagate_effects ()
2563 ipcp_value
<valtype
> *base
;
2565 for (base
= values_topo
; base
; base
= base
->topo_next
)
2567 ipcp_value_source
<valtype
> *src
;
2568 ipcp_value
<valtype
> *val
;
2569 int time
= 0, size
= 0;
2571 for (val
= base
; val
; val
= val
->scc_next
)
2573 time
= safe_add (time
,
2574 val
->local_time_benefit
+ val
->prop_time_benefit
);
2575 size
= safe_add (size
, val
->local_size_cost
+ val
->prop_size_cost
);
2578 for (val
= base
; val
; val
= val
->scc_next
)
2579 for (src
= val
->sources
; src
; src
= src
->next
)
2581 && src
->cs
->maybe_hot_p ())
2583 src
->val
->prop_time_benefit
= safe_add (time
,
2584 src
->val
->prop_time_benefit
);
2585 src
->val
->prop_size_cost
= safe_add (size
,
2586 src
->val
->prop_size_cost
);
2592 /* Propagate constants, polymorphic contexts and their effects from the
2593 summaries interprocedurally. */
2596 ipcp_propagate_stage (struct ipa_topo_info
*topo
)
2598 struct cgraph_node
*node
;
2601 fprintf (dump_file
, "\n Propagating constants:\n\n");
2604 ipa_update_after_lto_read ();
2607 FOR_EACH_DEFINED_FUNCTION (node
)
2609 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2611 determine_versionability (node
);
2612 if (node
->has_gimple_body_p ())
2614 info
->lattices
= XCNEWVEC (struct ipcp_param_lattices
,
2615 ipa_get_param_count (info
));
2616 initialize_node_lattices (node
);
2618 if (node
->definition
&& !node
->alias
)
2619 overall_size
+= inline_summary (node
)->self_size
;
2620 if (node
->count
> max_count
)
2621 max_count
= node
->count
;
2624 max_new_size
= overall_size
;
2625 if (max_new_size
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
2626 max_new_size
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
2627 max_new_size
+= max_new_size
* PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH
) / 100 + 1;
2630 fprintf (dump_file
, "\noverall_size: %li, max_new_size: %li\n",
2631 overall_size
, max_new_size
);
2633 propagate_constants_topo (topo
);
2634 #ifdef ENABLE_CHECKING
2635 ipcp_verify_propagated_values ();
2637 topo
->constants
.propagate_effects ();
2638 topo
->contexts
.propagate_effects ();
2642 fprintf (dump_file
, "\nIPA lattices after all propagation:\n");
2643 print_all_lattices (dump_file
, (dump_flags
& TDF_DETAILS
), true);
2647 /* Discover newly direct outgoing edges from NODE which is a new clone with
2648 known KNOWN_CSTS and make them direct. */
2651 ipcp_discover_new_direct_edges (struct cgraph_node
*node
,
2652 vec
<tree
> known_csts
,
2653 vec
<ipa_polymorphic_call_context
>
2655 struct ipa_agg_replacement_value
*aggvals
)
2657 struct cgraph_edge
*ie
, *next_ie
;
2660 for (ie
= node
->indirect_calls
; ie
; ie
= next_ie
)
2664 next_ie
= ie
->next_callee
;
2665 target
= ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
2669 bool agg_contents
= ie
->indirect_info
->agg_contents
;
2670 bool polymorphic
= ie
->indirect_info
->polymorphic
;
2671 int param_index
= ie
->indirect_info
->param_index
;
2672 struct cgraph_edge
*cs
= ipa_make_edge_direct_to_target (ie
, target
);
2675 if (cs
&& !agg_contents
&& !polymorphic
)
2677 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2678 int c
= ipa_get_controlled_uses (info
, param_index
);
2679 if (c
!= IPA_UNDESCRIBED_USE
)
2681 struct ipa_ref
*to_del
;
2684 ipa_set_controlled_uses (info
, param_index
, c
);
2685 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2686 fprintf (dump_file
, " controlled uses count of param "
2687 "%i bumped down to %i\n", param_index
, c
);
2689 && (to_del
= node
->find_reference (cs
->callee
, NULL
, 0)))
2691 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2692 fprintf (dump_file
, " and even removing its "
2693 "cloning-created reference\n");
2694 to_del
->remove_reference ();
2700 /* Turning calls to direct calls will improve overall summary. */
2702 inline_update_overall_summary (node
);
2705 /* Vector of pointers which for linked lists of clones of an original crgaph
2708 static vec
<cgraph_edge
*> next_edge_clone
;
2709 static vec
<cgraph_edge
*> prev_edge_clone
;
2712 grow_edge_clone_vectors (void)
2714 if (next_edge_clone
.length ()
2715 <= (unsigned) symtab
->edges_max_uid
)
2716 next_edge_clone
.safe_grow_cleared (symtab
->edges_max_uid
+ 1);
2717 if (prev_edge_clone
.length ()
2718 <= (unsigned) symtab
->edges_max_uid
)
2719 prev_edge_clone
.safe_grow_cleared (symtab
->edges_max_uid
+ 1);
2722 /* Edge duplication hook to grow the appropriate linked list in
2726 ipcp_edge_duplication_hook (struct cgraph_edge
*src
, struct cgraph_edge
*dst
,
2729 grow_edge_clone_vectors ();
2731 struct cgraph_edge
*old_next
= next_edge_clone
[src
->uid
];
2733 prev_edge_clone
[old_next
->uid
] = dst
;
2734 prev_edge_clone
[dst
->uid
] = src
;
2736 next_edge_clone
[dst
->uid
] = old_next
;
2737 next_edge_clone
[src
->uid
] = dst
;
2740 /* Hook that is called by cgraph.c when an edge is removed. */
2743 ipcp_edge_removal_hook (struct cgraph_edge
*cs
, void *)
2745 grow_edge_clone_vectors ();
2747 struct cgraph_edge
*prev
= prev_edge_clone
[cs
->uid
];
2748 struct cgraph_edge
*next
= next_edge_clone
[cs
->uid
];
2750 next_edge_clone
[prev
->uid
] = next
;
2752 prev_edge_clone
[next
->uid
] = prev
;
2755 /* See if NODE is a clone with a known aggregate value at a given OFFSET of a
2756 parameter with the given INDEX. */
2759 get_clone_agg_value (struct cgraph_node
*node
, HOST_WIDE_INT offset
,
2762 struct ipa_agg_replacement_value
*aggval
;
2764 aggval
= ipa_get_agg_replacements_for_node (node
);
2767 if (aggval
->offset
== offset
2768 && aggval
->index
== index
)
2769 return aggval
->value
;
2770 aggval
= aggval
->next
;
2775 /* Return true if edge CS does bring about the value described by SRC. */
2778 cgraph_edge_brings_value_p (struct cgraph_edge
*cs
,
2779 ipcp_value_source
<tree
> *src
)
2781 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2782 cgraph_node
*real_dest
= cs
->callee
->function_symbol ();
2783 struct ipa_node_params
*dst_info
= IPA_NODE_REF (real_dest
);
2785 if ((dst_info
->ipcp_orig_node
&& !dst_info
->is_all_contexts_clone
)
2786 || caller_info
->node_dead
)
2791 if (caller_info
->ipcp_orig_node
)
2794 if (src
->offset
== -1)
2795 t
= caller_info
->known_csts
[src
->index
];
2797 t
= get_clone_agg_value (cs
->caller
, src
->offset
, src
->index
);
2798 return (t
!= NULL_TREE
2799 && values_equal_for_ipcp_p (src
->val
->value
, t
));
2803 struct ipcp_agg_lattice
*aglat
;
2804 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
2806 if (src
->offset
== -1)
2807 return (plats
->itself
.is_single_const ()
2808 && values_equal_for_ipcp_p (src
->val
->value
,
2809 plats
->itself
.values
->value
));
2812 if (plats
->aggs_bottom
|| plats
->aggs_contain_variable
)
2814 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2815 if (aglat
->offset
== src
->offset
)
2816 return (aglat
->is_single_const ()
2817 && values_equal_for_ipcp_p (src
->val
->value
,
2818 aglat
->values
->value
));
2824 /* Return true if edge CS does bring about the value described by SRC. */
2827 cgraph_edge_brings_value_p (struct cgraph_edge
*cs
,
2828 ipcp_value_source
<ipa_polymorphic_call_context
>
2831 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2832 cgraph_node
*real_dest
= cs
->callee
->function_symbol ();
2833 struct ipa_node_params
*dst_info
= IPA_NODE_REF (real_dest
);
2835 if ((dst_info
->ipcp_orig_node
&& !dst_info
->is_all_contexts_clone
)
2836 || caller_info
->node_dead
)
2841 if (caller_info
->ipcp_orig_node
)
2842 return (caller_info
->known_contexts
.length () > (unsigned) src
->index
)
2843 && values_equal_for_ipcp_p (src
->val
->value
,
2844 caller_info
->known_contexts
[src
->index
]);
2846 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
2848 return plats
->ctxlat
.is_single_const ()
2849 && values_equal_for_ipcp_p (src
->val
->value
,
2850 plats
->ctxlat
.values
->value
);
2853 /* Get the next clone in the linked list of clones of an edge. */
2855 static inline struct cgraph_edge
*
2856 get_next_cgraph_edge_clone (struct cgraph_edge
*cs
)
2858 return next_edge_clone
[cs
->uid
];
2861 /* Given VAL, iterate over all its sources and if they still hold, add their
2862 edge frequency and their number into *FREQUENCY and *CALLER_COUNT
2865 template <typename valtype
>
2867 get_info_about_necessary_edges (ipcp_value
<valtype
> *val
, int *freq_sum
,
2868 gcov_type
*count_sum
, int *caller_count
)
2870 ipcp_value_source
<valtype
> *src
;
2871 int freq
= 0, count
= 0;
2875 for (src
= val
->sources
; src
; src
= src
->next
)
2877 struct cgraph_edge
*cs
= src
->cs
;
2880 if (cgraph_edge_brings_value_p (cs
, src
))
2883 freq
+= cs
->frequency
;
2885 hot
|= cs
->maybe_hot_p ();
2887 cs
= get_next_cgraph_edge_clone (cs
);
2893 *caller_count
= count
;
2897 /* Return a vector of incoming edges that do bring value VAL. It is assumed
2898 their number is known and equal to CALLER_COUNT. */
2900 template <typename valtype
>
2901 static vec
<cgraph_edge
*>
2902 gather_edges_for_value (ipcp_value
<valtype
> *val
, int caller_count
)
2904 ipcp_value_source
<valtype
> *src
;
2905 vec
<cgraph_edge
*> ret
;
2907 ret
.create (caller_count
);
2908 for (src
= val
->sources
; src
; src
= src
->next
)
2910 struct cgraph_edge
*cs
= src
->cs
;
2913 if (cgraph_edge_brings_value_p (cs
, src
))
2914 ret
.quick_push (cs
);
2915 cs
= get_next_cgraph_edge_clone (cs
);
2922 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
2923 Return it or NULL if for some reason it cannot be created. */
2925 static struct ipa_replace_map
*
2926 get_replacement_map (struct ipa_node_params
*info
, tree value
, int parm_num
)
2928 struct ipa_replace_map
*replace_map
;
2931 replace_map
= ggc_alloc
<ipa_replace_map
> ();
2934 fprintf (dump_file
, " replacing ");
2935 ipa_dump_param (dump_file
, info
, parm_num
);
2937 fprintf (dump_file
, " with const ");
2938 print_generic_expr (dump_file
, value
, 0);
2939 fprintf (dump_file
, "\n");
2941 replace_map
->old_tree
= NULL
;
2942 replace_map
->parm_num
= parm_num
;
2943 replace_map
->new_tree
= value
;
2944 replace_map
->replace_p
= true;
2945 replace_map
->ref_p
= false;
2950 /* Dump new profiling counts */
2953 dump_profile_updates (struct cgraph_node
*orig_node
,
2954 struct cgraph_node
*new_node
)
2956 struct cgraph_edge
*cs
;
2958 fprintf (dump_file
, " setting count of the specialized node to "
2959 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) new_node
->count
);
2960 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
2961 fprintf (dump_file
, " edge to %s has count "
2962 HOST_WIDE_INT_PRINT_DEC
"\n",
2963 cs
->callee
->name (), (HOST_WIDE_INT
) cs
->count
);
2965 fprintf (dump_file
, " setting count of the original node to "
2966 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) orig_node
->count
);
2967 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
2968 fprintf (dump_file
, " edge to %s is left with "
2969 HOST_WIDE_INT_PRINT_DEC
"\n",
2970 cs
->callee
->name (), (HOST_WIDE_INT
) cs
->count
);
2973 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
2974 their profile information to reflect this. */
2977 update_profiling_info (struct cgraph_node
*orig_node
,
2978 struct cgraph_node
*new_node
)
2980 struct cgraph_edge
*cs
;
2981 struct caller_statistics stats
;
2982 gcov_type new_sum
, orig_sum
;
2983 gcov_type remainder
, orig_node_count
= orig_node
->count
;
2985 if (orig_node_count
== 0)
2988 init_caller_stats (&stats
);
2989 orig_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
2991 orig_sum
= stats
.count_sum
;
2992 init_caller_stats (&stats
);
2993 new_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
2995 new_sum
= stats
.count_sum
;
2997 if (orig_node_count
< orig_sum
+ new_sum
)
3000 fprintf (dump_file
, " Problem: node %s/%i has too low count "
3001 HOST_WIDE_INT_PRINT_DEC
" while the sum of incoming "
3002 "counts is " HOST_WIDE_INT_PRINT_DEC
"\n",
3003 orig_node
->name (), orig_node
->order
,
3004 (HOST_WIDE_INT
) orig_node_count
,
3005 (HOST_WIDE_INT
) (orig_sum
+ new_sum
));
3007 orig_node_count
= (orig_sum
+ new_sum
) * 12 / 10;
3009 fprintf (dump_file
, " proceeding by pretending it was "
3010 HOST_WIDE_INT_PRINT_DEC
"\n",
3011 (HOST_WIDE_INT
) orig_node_count
);
3014 new_node
->count
= new_sum
;
3015 remainder
= orig_node_count
- new_sum
;
3016 orig_node
->count
= remainder
;
3018 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3020 cs
->count
= apply_probability (cs
->count
,
3021 GCOV_COMPUTE_SCALE (new_sum
,
3026 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3027 cs
->count
= apply_probability (cs
->count
,
3028 GCOV_COMPUTE_SCALE (remainder
,
3032 dump_profile_updates (orig_node
, new_node
);
3035 /* Update the respective profile of specialized NEW_NODE and the original
3036 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
3037 have been redirected to the specialized version. */
3040 update_specialized_profile (struct cgraph_node
*new_node
,
3041 struct cgraph_node
*orig_node
,
3042 gcov_type redirected_sum
)
3044 struct cgraph_edge
*cs
;
3045 gcov_type new_node_count
, orig_node_count
= orig_node
->count
;
3048 fprintf (dump_file
, " the sum of counts of redirected edges is "
3049 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) redirected_sum
);
3050 if (orig_node_count
== 0)
3053 gcc_assert (orig_node_count
>= redirected_sum
);
3055 new_node_count
= new_node
->count
;
3056 new_node
->count
+= redirected_sum
;
3057 orig_node
->count
-= redirected_sum
;
3059 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3061 cs
->count
+= apply_probability (cs
->count
,
3062 GCOV_COMPUTE_SCALE (redirected_sum
,
3067 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3069 gcov_type dec
= apply_probability (cs
->count
,
3070 GCOV_COMPUTE_SCALE (redirected_sum
,
3072 if (dec
< cs
->count
)
3079 dump_profile_updates (orig_node
, new_node
);
3082 /* Create a specialized version of NODE with known constants in KNOWN_CSTS,
3083 known contexts in KNOWN_CONTEXTS and known aggregate values in AGGVALS and
3084 redirect all edges in CALLERS to it. */
3086 static struct cgraph_node
*
3087 create_specialized_node (struct cgraph_node
*node
,
3088 vec
<tree
> known_csts
,
3089 vec
<ipa_polymorphic_call_context
> known_contexts
,
3090 struct ipa_agg_replacement_value
*aggvals
,
3091 vec
<cgraph_edge
*> callers
)
3093 struct ipa_node_params
*new_info
, *info
= IPA_NODE_REF (node
);
3094 vec
<ipa_replace_map
*, va_gc
> *replace_trees
= NULL
;
3095 struct ipa_agg_replacement_value
*av
;
3096 struct cgraph_node
*new_node
;
3097 int i
, count
= ipa_get_param_count (info
);
3098 bitmap args_to_skip
;
3100 gcc_assert (!info
->ipcp_orig_node
);
3102 if (node
->local
.can_change_signature
)
3104 args_to_skip
= BITMAP_GGC_ALLOC ();
3105 for (i
= 0; i
< count
; i
++)
3107 tree t
= known_csts
[i
];
3109 if (t
|| !ipa_is_param_used (info
, i
))
3110 bitmap_set_bit (args_to_skip
, i
);
3115 args_to_skip
= NULL
;
3116 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3117 fprintf (dump_file
, " cannot change function signature\n");
3120 for (i
= 0; i
< count
; i
++)
3122 tree t
= known_csts
[i
];
3125 struct ipa_replace_map
*replace_map
;
3127 gcc_checking_assert (TREE_CODE (t
) != TREE_BINFO
);
3128 replace_map
= get_replacement_map (info
, t
, i
);
3130 vec_safe_push (replace_trees
, replace_map
);
3134 new_node
= node
->create_virtual_clone (callers
, replace_trees
,
3135 args_to_skip
, "constprop");
3136 ipa_set_node_agg_value_chain (new_node
, aggvals
);
3137 for (av
= aggvals
; av
; av
= av
->next
)
3138 new_node
->maybe_create_reference (av
->value
, IPA_REF_ADDR
, NULL
);
3140 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3142 fprintf (dump_file
, " the new node is %s/%i.\n",
3143 new_node
->name (), new_node
->order
);
3144 if (known_contexts
.exists ())
3146 for (i
= 0; i
< count
; i
++)
3147 if (!known_contexts
[i
].useless_p ())
3149 fprintf (dump_file
, " known ctx %i is ", i
);
3150 known_contexts
[i
].dump (dump_file
);
3154 ipa_dump_agg_replacement_values (dump_file
, aggvals
);
3156 ipa_check_create_node_params ();
3157 update_profiling_info (node
, new_node
);
3158 new_info
= IPA_NODE_REF (new_node
);
3159 new_info
->ipcp_orig_node
= node
;
3160 new_info
->known_csts
= known_csts
;
3161 new_info
->known_contexts
= known_contexts
;
3163 ipcp_discover_new_direct_edges (new_node
, known_csts
, known_contexts
, aggvals
);
3169 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
3170 KNOWN_CSTS with constants that are also known for all of the CALLERS. */
3173 find_more_scalar_values_for_callers_subset (struct cgraph_node
*node
,
3174 vec
<tree
> known_csts
,
3175 vec
<cgraph_edge
*> callers
)
3177 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3178 int i
, count
= ipa_get_param_count (info
);
3180 for (i
= 0; i
< count
; i
++)
3182 struct cgraph_edge
*cs
;
3183 tree newval
= NULL_TREE
;
3186 if (ipa_get_scalar_lat (info
, i
)->bottom
|| known_csts
[i
])
3189 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3191 struct ipa_jump_func
*jump_func
;
3194 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
)))
3199 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
3200 t
= ipa_value_from_jfunc (IPA_NODE_REF (cs
->caller
), jump_func
);
3203 && !values_equal_for_ipcp_p (t
, newval
)))
3214 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3216 fprintf (dump_file
, " adding an extra known scalar value ");
3217 print_ipcp_constant_value (dump_file
, newval
);
3218 fprintf (dump_file
, " for ");
3219 ipa_dump_param (dump_file
, info
, i
);
3220 fprintf (dump_file
, "\n");
3223 known_csts
[i
] = newval
;
3228 /* Given a NODE and a subset of its CALLERS, try to populate plank slots in
3229 KNOWN_CONTEXTS with polymorphic contexts that are also known for all of the
3233 find_more_contexts_for_caller_subset (cgraph_node
*node
,
3234 vec
<ipa_polymorphic_call_context
>
3236 vec
<cgraph_edge
*> callers
)
3238 ipa_node_params
*info
= IPA_NODE_REF (node
);
3239 int i
, count
= ipa_get_param_count (info
);
3241 for (i
= 0; i
< count
; i
++)
3245 if (ipa_get_poly_ctx_lat (info
, i
)->bottom
3246 || (known_contexts
->exists ()
3247 && !(*known_contexts
)[i
].useless_p ()))
3250 ipa_polymorphic_call_context newval
;
3254 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3256 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
)))
3258 ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
),
3260 ipa_polymorphic_call_context ctx
;
3261 ctx
= ipa_context_from_jfunc (IPA_NODE_REF (cs
->caller
), cs
, i
,
3263 ctx
.clear_speculation ();
3264 if (ctx
.useless_p ()
3265 || (found
&& !values_equal_for_ipcp_p (newval
, ctx
)))
3279 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3281 fprintf (dump_file
, " adding an extra known polymorphic "
3283 print_ipcp_constant_value (dump_file
, newval
);
3284 fprintf (dump_file
, " for ");
3285 ipa_dump_param (dump_file
, info
, i
);
3286 fprintf (dump_file
, "\n");
3289 if (!known_contexts
->exists ())
3290 known_contexts
->safe_grow_cleared (ipa_get_param_count (info
));
3291 (*known_contexts
)[i
] = newval
;
3297 /* Go through PLATS and create a vector of values consisting of values and
3298 offsets (minus OFFSET) of lattices that contain only a single value. */
3300 static vec
<ipa_agg_jf_item
>
3301 copy_plats_to_inter (struct ipcp_param_lattices
*plats
, HOST_WIDE_INT offset
)
3303 vec
<ipa_agg_jf_item
> res
= vNULL
;
3305 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
3308 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3309 if (aglat
->is_single_const ())
3311 struct ipa_agg_jf_item ti
;
3312 ti
.offset
= aglat
->offset
- offset
;
3313 ti
.value
= aglat
->values
->value
;
3319 /* Intersect all values in INTER with single value lattices in PLATS (while
3320 subtracting OFFSET). */
3323 intersect_with_plats (struct ipcp_param_lattices
*plats
,
3324 vec
<ipa_agg_jf_item
> *inter
,
3325 HOST_WIDE_INT offset
)
3327 struct ipcp_agg_lattice
*aglat
;
3328 struct ipa_agg_jf_item
*item
;
3331 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
3337 aglat
= plats
->aggs
;
3338 FOR_EACH_VEC_ELT (*inter
, k
, item
)
3345 if (aglat
->offset
- offset
> item
->offset
)
3347 if (aglat
->offset
- offset
== item
->offset
)
3349 gcc_checking_assert (item
->value
);
3350 if (values_equal_for_ipcp_p (item
->value
, aglat
->values
->value
))
3354 aglat
= aglat
->next
;
3357 item
->value
= NULL_TREE
;
3361 /* Copy agggregate replacement values of NODE (which is an IPA-CP clone) to the
3362 vector result while subtracting OFFSET from the individual value offsets. */
3364 static vec
<ipa_agg_jf_item
>
3365 agg_replacements_to_vector (struct cgraph_node
*node
, int index
,
3366 HOST_WIDE_INT offset
)
3368 struct ipa_agg_replacement_value
*av
;
3369 vec
<ipa_agg_jf_item
> res
= vNULL
;
3371 for (av
= ipa_get_agg_replacements_for_node (node
); av
; av
= av
->next
)
3372 if (av
->index
== index
3373 && (av
->offset
- offset
) >= 0)
3375 struct ipa_agg_jf_item item
;
3376 gcc_checking_assert (av
->value
);
3377 item
.offset
= av
->offset
- offset
;
3378 item
.value
= av
->value
;
3379 res
.safe_push (item
);
3385 /* Intersect all values in INTER with those that we have already scheduled to
3386 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
3387 (while subtracting OFFSET). */
3390 intersect_with_agg_replacements (struct cgraph_node
*node
, int index
,
3391 vec
<ipa_agg_jf_item
> *inter
,
3392 HOST_WIDE_INT offset
)
3394 struct ipa_agg_replacement_value
*srcvals
;
3395 struct ipa_agg_jf_item
*item
;
3398 srcvals
= ipa_get_agg_replacements_for_node (node
);
3405 FOR_EACH_VEC_ELT (*inter
, i
, item
)
3407 struct ipa_agg_replacement_value
*av
;
3411 for (av
= srcvals
; av
; av
= av
->next
)
3413 gcc_checking_assert (av
->value
);
3414 if (av
->index
== index
3415 && av
->offset
- offset
== item
->offset
)
3417 if (values_equal_for_ipcp_p (item
->value
, av
->value
))
3423 item
->value
= NULL_TREE
;
3427 /* Intersect values in INTER with aggregate values that come along edge CS to
3428 parameter number INDEX and return it. If INTER does not actually exist yet,
3429 copy all incoming values to it. If we determine we ended up with no values
3430 whatsoever, return a released vector. */
3432 static vec
<ipa_agg_jf_item
>
3433 intersect_aggregates_with_edge (struct cgraph_edge
*cs
, int index
,
3434 vec
<ipa_agg_jf_item
> inter
)
3436 struct ipa_jump_func
*jfunc
;
3437 jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), index
);
3438 if (jfunc
->type
== IPA_JF_PASS_THROUGH
3439 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
3441 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3442 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
3444 if (caller_info
->ipcp_orig_node
)
3446 struct cgraph_node
*orig_node
= caller_info
->ipcp_orig_node
;
3447 struct ipcp_param_lattices
*orig_plats
;
3448 orig_plats
= ipa_get_parm_lattices (IPA_NODE_REF (orig_node
),
3450 if (agg_pass_through_permissible_p (orig_plats
, jfunc
))
3452 if (!inter
.exists ())
3453 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, 0);
3455 intersect_with_agg_replacements (cs
->caller
, src_idx
,
3466 struct ipcp_param_lattices
*src_plats
;
3467 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
3468 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
3470 /* Currently we do not produce clobber aggregate jump
3471 functions, adjust when we do. */
3472 gcc_checking_assert (!jfunc
->agg
.items
);
3473 if (!inter
.exists ())
3474 inter
= copy_plats_to_inter (src_plats
, 0);
3476 intersect_with_plats (src_plats
, &inter
, 0);
3485 else if (jfunc
->type
== IPA_JF_ANCESTOR
3486 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
3488 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3489 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
3490 struct ipcp_param_lattices
*src_plats
;
3491 HOST_WIDE_INT delta
= ipa_get_jf_ancestor_offset (jfunc
);
3493 if (caller_info
->ipcp_orig_node
)
3495 if (!inter
.exists ())
3496 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, delta
);
3498 intersect_with_agg_replacements (cs
->caller
, src_idx
, &inter
,
3503 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);;
3504 /* Currently we do not produce clobber aggregate jump
3505 functions, adjust when we do. */
3506 gcc_checking_assert (!src_plats
->aggs
|| !jfunc
->agg
.items
);
3507 if (!inter
.exists ())
3508 inter
= copy_plats_to_inter (src_plats
, delta
);
3510 intersect_with_plats (src_plats
, &inter
, delta
);
3513 else if (jfunc
->agg
.items
)
3515 struct ipa_agg_jf_item
*item
;
3518 if (!inter
.exists ())
3519 for (unsigned i
= 0; i
< jfunc
->agg
.items
->length (); i
++)
3520 inter
.safe_push ((*jfunc
->agg
.items
)[i
]);
3522 FOR_EACH_VEC_ELT (inter
, k
, item
)
3525 bool found
= false;;
3530 while ((unsigned) l
< jfunc
->agg
.items
->length ())
3532 struct ipa_agg_jf_item
*ti
;
3533 ti
= &(*jfunc
->agg
.items
)[l
];
3534 if (ti
->offset
> item
->offset
)
3536 if (ti
->offset
== item
->offset
)
3538 gcc_checking_assert (ti
->value
);
3539 if (values_equal_for_ipcp_p (item
->value
,
3553 return vec
<ipa_agg_jf_item
>();
3558 /* Look at edges in CALLERS and collect all known aggregate values that arrive
3559 from all of them. */
3561 static struct ipa_agg_replacement_value
*
3562 find_aggregate_values_for_callers_subset (struct cgraph_node
*node
,
3563 vec
<cgraph_edge
*> callers
)
3565 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
3566 struct ipa_agg_replacement_value
*res
;
3567 struct ipa_agg_replacement_value
**tail
= &res
;
3568 struct cgraph_edge
*cs
;
3569 int i
, j
, count
= ipa_get_param_count (dest_info
);
3571 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3573 int c
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
3578 for (i
= 0; i
< count
; i
++)
3580 struct cgraph_edge
*cs
;
3581 vec
<ipa_agg_jf_item
> inter
= vNULL
;
3582 struct ipa_agg_jf_item
*item
;
3583 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (dest_info
, i
);
3586 /* Among other things, the following check should deal with all by_ref
3588 if (plats
->aggs_bottom
)
3591 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3593 inter
= intersect_aggregates_with_edge (cs
, i
, inter
);
3595 if (!inter
.exists ())
3599 FOR_EACH_VEC_ELT (inter
, j
, item
)
3601 struct ipa_agg_replacement_value
*v
;
3606 v
= ggc_alloc
<ipa_agg_replacement_value
> ();
3608 v
->offset
= item
->offset
;
3609 v
->value
= item
->value
;
3610 v
->by_ref
= plats
->aggs_by_ref
;
3616 if (inter
.exists ())
3623 /* Turn KNOWN_AGGS into a list of aggreate replacement values. */
3625 static struct ipa_agg_replacement_value
*
3626 known_aggs_to_agg_replacement_list (vec
<ipa_agg_jump_function
> known_aggs
)
3628 struct ipa_agg_replacement_value
*res
;
3629 struct ipa_agg_replacement_value
**tail
= &res
;
3630 struct ipa_agg_jump_function
*aggjf
;
3631 struct ipa_agg_jf_item
*item
;
3634 FOR_EACH_VEC_ELT (known_aggs
, i
, aggjf
)
3635 FOR_EACH_VEC_SAFE_ELT (aggjf
->items
, j
, item
)
3637 struct ipa_agg_replacement_value
*v
;
3638 v
= ggc_alloc
<ipa_agg_replacement_value
> ();
3640 v
->offset
= item
->offset
;
3641 v
->value
= item
->value
;
3642 v
->by_ref
= aggjf
->by_ref
;
3650 /* Determine whether CS also brings all scalar values that the NODE is
3654 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge
*cs
,
3655 struct cgraph_node
*node
)
3657 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
3658 int count
= ipa_get_param_count (dest_info
);
3659 struct ipa_node_params
*caller_info
;
3660 struct ipa_edge_args
*args
;
3663 caller_info
= IPA_NODE_REF (cs
->caller
);
3664 args
= IPA_EDGE_REF (cs
);
3665 for (i
= 0; i
< count
; i
++)
3667 struct ipa_jump_func
*jump_func
;
3670 val
= dest_info
->known_csts
[i
];
3674 if (i
>= ipa_get_cs_argument_count (args
))
3676 jump_func
= ipa_get_ith_jump_func (args
, i
);
3677 t
= ipa_value_from_jfunc (caller_info
, jump_func
);
3678 if (!t
|| !values_equal_for_ipcp_p (val
, t
))
3684 /* Determine whether CS also brings all aggregate values that NODE is
3687 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge
*cs
,
3688 struct cgraph_node
*node
)
3690 struct ipa_node_params
*orig_caller_info
= IPA_NODE_REF (cs
->caller
);
3691 struct ipa_node_params
*orig_node_info
;
3692 struct ipa_agg_replacement_value
*aggval
;
3695 aggval
= ipa_get_agg_replacements_for_node (node
);
3699 count
= ipa_get_param_count (IPA_NODE_REF (node
));
3700 ec
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
3702 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
3703 if (aggval
->index
>= ec
)
3706 orig_node_info
= IPA_NODE_REF (IPA_NODE_REF (node
)->ipcp_orig_node
);
3707 if (orig_caller_info
->ipcp_orig_node
)
3708 orig_caller_info
= IPA_NODE_REF (orig_caller_info
->ipcp_orig_node
);
3710 for (i
= 0; i
< count
; i
++)
3712 static vec
<ipa_agg_jf_item
> values
= vec
<ipa_agg_jf_item
>();
3713 struct ipcp_param_lattices
*plats
;
3714 bool interesting
= false;
3715 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
3716 if (aggval
->index
== i
)
3724 plats
= ipa_get_parm_lattices (orig_node_info
, aggval
->index
);
3725 if (plats
->aggs_bottom
)
3728 values
= intersect_aggregates_with_edge (cs
, i
, values
);
3729 if (!values
.exists ())
3732 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
3733 if (aggval
->index
== i
)
3735 struct ipa_agg_jf_item
*item
;
3738 FOR_EACH_VEC_ELT (values
, j
, item
)
3740 && item
->offset
== av
->offset
3741 && values_equal_for_ipcp_p (item
->value
, av
->value
))
3756 /* Given an original NODE and a VAL for which we have already created a
3757 specialized clone, look whether there are incoming edges that still lead
3758 into the old node but now also bring the requested value and also conform to
3759 all other criteria such that they can be redirected the the special node.
3760 This function can therefore redirect the final edge in a SCC. */
3762 template <typename valtype
>
3764 perhaps_add_new_callers (cgraph_node
*node
, ipcp_value
<valtype
> *val
)
3766 ipcp_value_source
<valtype
> *src
;
3767 gcov_type redirected_sum
= 0;
3769 for (src
= val
->sources
; src
; src
= src
->next
)
3771 struct cgraph_edge
*cs
= src
->cs
;
3774 enum availability availability
;
3775 struct cgraph_node
*dst
= cs
->callee
->function_symbol (&availability
);
3776 if ((dst
== node
|| IPA_NODE_REF (dst
)->is_all_contexts_clone
)
3777 && availability
> AVAIL_INTERPOSABLE
3778 && cgraph_edge_brings_value_p (cs
, src
))
3780 if (cgraph_edge_brings_all_scalars_for_node (cs
, val
->spec_node
)
3781 && cgraph_edge_brings_all_agg_vals_for_node (cs
,
3785 fprintf (dump_file
, " - adding an extra caller %s/%i"
3787 xstrdup (cs
->caller
->name ()),
3789 xstrdup (val
->spec_node
->name ()),
3790 val
->spec_node
->order
);
3792 cs
->redirect_callee (val
->spec_node
);
3793 redirected_sum
+= cs
->count
;
3796 cs
= get_next_cgraph_edge_clone (cs
);
3801 update_specialized_profile (val
->spec_node
, node
, redirected_sum
);
3804 /* Return true if KNOWN_CONTEXTS contain at least one useful context. */
3807 known_contexts_useful_p (vec
<ipa_polymorphic_call_context
> known_contexts
)
3809 ipa_polymorphic_call_context
*ctx
;
3812 FOR_EACH_VEC_ELT (known_contexts
, i
, ctx
)
3813 if (!ctx
->useless_p ())
3818 /* Return a copy of KNOWN_CSTS if it is not empty, otherwise return vNULL. */
3820 static vec
<ipa_polymorphic_call_context
>
3821 copy_useful_known_contexts (vec
<ipa_polymorphic_call_context
> known_contexts
)
3823 if (known_contexts_useful_p (known_contexts
))
3824 return known_contexts
.copy ();
3829 /* Copy KNOWN_CSTS and modify the copy according to VAL and INDEX. If
3830 non-empty, replace KNOWN_CONTEXTS with its copy too. */
3833 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
3834 vec
<ipa_polymorphic_call_context
> *known_contexts
,
3835 ipcp_value
<tree
> *val
,
3838 *known_csts
= known_csts
->copy ();
3839 *known_contexts
= copy_useful_known_contexts (*known_contexts
);
3840 (*known_csts
)[index
] = val
->value
;
3843 /* Replace KNOWN_CSTS with its copy. Also copy KNOWN_CONTEXTS and modify the
3844 copy according to VAL and INDEX. */
3847 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
3848 vec
<ipa_polymorphic_call_context
> *known_contexts
,
3849 ipcp_value
<ipa_polymorphic_call_context
> *val
,
3852 *known_csts
= known_csts
->copy ();
3853 *known_contexts
= known_contexts
->copy ();
3854 (*known_contexts
)[index
] = val
->value
;
3857 /* Return true if OFFSET indicates this was not an aggregate value or there is
3858 a replacement equivalent to VALUE, INDEX and OFFSET among those in the
3862 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*aggvals
,
3863 int index
, HOST_WIDE_INT offset
, tree value
)
3870 if (aggvals
->index
== index
3871 && aggvals
->offset
== offset
3872 && values_equal_for_ipcp_p (aggvals
->value
, value
))
3874 aggvals
= aggvals
->next
;
3879 /* Return true if offset is minus one because source of a polymorphic contect
3880 cannot be an aggregate value. */
3883 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*,
3884 int , HOST_WIDE_INT offset
,
3885 ipa_polymorphic_call_context
)
3887 return offset
== -1;
3890 /* Decide wheter to create a special version of NODE for value VAL of parameter
3891 at the given INDEX. If OFFSET is -1, the value is for the parameter itself,
3892 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS,
3893 KNOWN_CONTEXTS and KNOWN_AGGS describe the other already known values. */
3895 template <typename valtype
>
3897 decide_about_value (struct cgraph_node
*node
, int index
, HOST_WIDE_INT offset
,
3898 ipcp_value
<valtype
> *val
, vec
<tree
> known_csts
,
3899 vec
<ipa_polymorphic_call_context
> known_contexts
)
3901 struct ipa_agg_replacement_value
*aggvals
;
3902 int freq_sum
, caller_count
;
3903 gcov_type count_sum
;
3904 vec
<cgraph_edge
*> callers
;
3908 perhaps_add_new_callers (node
, val
);
3911 else if (val
->local_size_cost
+ overall_size
> max_new_size
)
3913 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3914 fprintf (dump_file
, " Ignoring candidate value because "
3915 "max_new_size would be reached with %li.\n",
3916 val
->local_size_cost
+ overall_size
);
3919 else if (!get_info_about_necessary_edges (val
, &freq_sum
, &count_sum
,
3923 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3925 fprintf (dump_file
, " - considering value ");
3926 print_ipcp_constant_value (dump_file
, val
->value
);
3927 fprintf (dump_file
, " for ");
3928 ipa_dump_param (dump_file
, IPA_NODE_REF (node
), index
);
3930 fprintf (dump_file
, ", offset: " HOST_WIDE_INT_PRINT_DEC
, offset
);
3931 fprintf (dump_file
, " (caller_count: %i)\n", caller_count
);
3934 if (!good_cloning_opportunity_p (node
, val
->local_time_benefit
,
3935 freq_sum
, count_sum
,
3936 val
->local_size_cost
)
3937 && !good_cloning_opportunity_p (node
,
3938 val
->local_time_benefit
3939 + val
->prop_time_benefit
,
3940 freq_sum
, count_sum
,
3941 val
->local_size_cost
3942 + val
->prop_size_cost
))
3946 fprintf (dump_file
, " Creating a specialized node of %s/%i.\n",
3947 node
->name (), node
->order
);
3949 callers
= gather_edges_for_value (val
, caller_count
);
3951 modify_known_vectors_with_val (&known_csts
, &known_contexts
, val
, index
);
3954 known_csts
= known_csts
.copy ();
3955 known_contexts
= copy_useful_known_contexts (known_contexts
);
3957 find_more_scalar_values_for_callers_subset (node
, known_csts
, callers
);
3958 find_more_contexts_for_caller_subset (node
, &known_contexts
, callers
);
3959 aggvals
= find_aggregate_values_for_callers_subset (node
, callers
);
3960 gcc_checking_assert (ipcp_val_agg_replacement_ok_p (aggvals
, index
,
3961 offset
, val
->value
));
3962 val
->spec_node
= create_specialized_node (node
, known_csts
, known_contexts
,
3964 overall_size
+= val
->local_size_cost
;
3966 /* TODO: If for some lattice there is only one other known value
3967 left, make a special node for it too. */
3972 /* Decide whether and what specialized clones of NODE should be created. */
3975 decide_whether_version_node (struct cgraph_node
*node
)
3977 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3978 int i
, count
= ipa_get_param_count (info
);
3979 vec
<tree
> known_csts
;
3980 vec
<ipa_polymorphic_call_context
> known_contexts
;
3981 vec
<ipa_agg_jump_function
> known_aggs
= vNULL
;
3987 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3988 fprintf (dump_file
, "\nEvaluating opportunities for %s/%i.\n",
3989 node
->name (), node
->order
);
3991 gather_context_independent_values (info
, &known_csts
, &known_contexts
,
3992 info
->do_clone_for_all_contexts
? &known_aggs
3995 for (i
= 0; i
< count
;i
++)
3997 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3998 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
3999 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
4004 ipcp_value
<tree
> *val
;
4005 for (val
= lat
->values
; val
; val
= val
->next
)
4006 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
4010 if (!plats
->aggs_bottom
)
4012 struct ipcp_agg_lattice
*aglat
;
4013 ipcp_value
<tree
> *val
;
4014 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
4015 if (!aglat
->bottom
&& aglat
->values
4016 /* If the following is false, the one value is in
4018 && (plats
->aggs_contain_variable
4019 || !aglat
->is_single_const ()))
4020 for (val
= aglat
->values
; val
; val
= val
->next
)
4021 ret
|= decide_about_value (node
, i
, aglat
->offset
, val
,
4022 known_csts
, known_contexts
);
4026 && known_contexts
[i
].useless_p ())
4028 ipcp_value
<ipa_polymorphic_call_context
> *val
;
4029 for (val
= ctxlat
->values
; val
; val
= val
->next
)
4030 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
4034 info
= IPA_NODE_REF (node
);
4037 if (info
->do_clone_for_all_contexts
)
4039 struct cgraph_node
*clone
;
4040 vec
<cgraph_edge
*> callers
;
4043 fprintf (dump_file
, " - Creating a specialized node of %s/%i "
4044 "for all known contexts.\n", node
->name (),
4047 callers
= node
->collect_callers ();
4049 if (!known_contexts_useful_p (known_contexts
))
4051 known_contexts
.release ();
4052 known_contexts
= vNULL
;
4054 clone
= create_specialized_node (node
, known_csts
, known_contexts
,
4055 known_aggs_to_agg_replacement_list (known_aggs
),
4057 info
= IPA_NODE_REF (node
);
4058 info
->do_clone_for_all_contexts
= false;
4059 IPA_NODE_REF (clone
)->is_all_contexts_clone
= true;
4060 for (i
= 0; i
< count
; i
++)
4061 vec_free (known_aggs
[i
].items
);
4062 known_aggs
.release ();
4067 known_csts
.release ();
4068 known_contexts
.release ();
4074 /* Transitively mark all callees of NODE within the same SCC as not dead. */
4077 spread_undeadness (struct cgraph_node
*node
)
4079 struct cgraph_edge
*cs
;
4081 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
4082 if (ipa_edge_within_scc (cs
))
4084 struct cgraph_node
*callee
;
4085 struct ipa_node_params
*info
;
4087 callee
= cs
->callee
->function_symbol (NULL
);
4088 info
= IPA_NODE_REF (callee
);
4090 if (info
->node_dead
)
4092 info
->node_dead
= 0;
4093 spread_undeadness (callee
);
4098 /* Return true if NODE has a caller from outside of its SCC that is not
4099 dead. Worker callback for cgraph_for_node_and_aliases. */
4102 has_undead_caller_from_outside_scc_p (struct cgraph_node
*node
,
4103 void *data ATTRIBUTE_UNUSED
)
4105 struct cgraph_edge
*cs
;
4107 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
4108 if (cs
->caller
->thunk
.thunk_p
4109 && cs
->caller
->call_for_symbol_thunks_and_aliases
4110 (has_undead_caller_from_outside_scc_p
, NULL
, true))
4112 else if (!ipa_edge_within_scc (cs
)
4113 && !IPA_NODE_REF (cs
->caller
)->node_dead
)
4119 /* Identify nodes within the same SCC as NODE which are no longer needed
4120 because of new clones and will be removed as unreachable. */
4123 identify_dead_nodes (struct cgraph_node
*node
)
4125 struct cgraph_node
*v
;
4126 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4127 if (v
->will_be_removed_from_program_if_no_direct_calls_p ()
4128 && !v
->call_for_symbol_thunks_and_aliases
4129 (has_undead_caller_from_outside_scc_p
, NULL
, true))
4130 IPA_NODE_REF (v
)->node_dead
= 1;
4132 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4133 if (!IPA_NODE_REF (v
)->node_dead
)
4134 spread_undeadness (v
);
4136 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4138 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4139 if (IPA_NODE_REF (v
)->node_dead
)
4140 fprintf (dump_file
, " Marking node as dead: %s/%i.\n",
4141 v
->name (), v
->order
);
4145 /* The decision stage. Iterate over the topological order of call graph nodes
4146 TOPO and make specialized clones if deemed beneficial. */
4149 ipcp_decision_stage (struct ipa_topo_info
*topo
)
4154 fprintf (dump_file
, "\nIPA decision stage:\n\n");
4156 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
4158 struct cgraph_node
*node
= topo
->order
[i
];
4159 bool change
= false, iterate
= true;
4163 struct cgraph_node
*v
;
4165 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4166 if (v
->has_gimple_body_p ()
4167 && ipcp_versionable_function_p (v
))
4168 iterate
|= decide_whether_version_node (v
);
4173 identify_dead_nodes (node
);
4177 /* The IPCP driver. */
4182 struct cgraph_2edge_hook_list
*edge_duplication_hook_holder
;
4183 struct cgraph_edge_hook_list
*edge_removal_hook_holder
;
4184 struct ipa_topo_info topo
;
4186 ipa_check_create_node_params ();
4187 ipa_check_create_edge_args ();
4188 grow_edge_clone_vectors ();
4189 edge_duplication_hook_holder
=
4190 symtab
->add_edge_duplication_hook (&ipcp_edge_duplication_hook
, NULL
);
4191 edge_removal_hook_holder
=
4192 symtab
->add_edge_removal_hook (&ipcp_edge_removal_hook
, NULL
);
4194 ipcp_cst_values_pool
= create_alloc_pool ("IPA-CP constant values",
4195 sizeof (ipcp_value
<tree
>), 32);
4196 ipcp_poly_ctx_values_pool
= create_alloc_pool
4197 ("IPA-CP polymorphic contexts",
4198 sizeof (ipcp_value
<ipa_polymorphic_call_context
>), 32);
4199 ipcp_sources_pool
= create_alloc_pool ("IPA-CP value sources",
4200 sizeof (ipcp_value_source
<tree
>), 64);
4201 ipcp_agg_lattice_pool
= create_alloc_pool ("IPA_CP aggregate lattices",
4202 sizeof (struct ipcp_agg_lattice
),
4206 fprintf (dump_file
, "\nIPA structures before propagation:\n");
4207 if (dump_flags
& TDF_DETAILS
)
4208 ipa_print_all_params (dump_file
);
4209 ipa_print_all_jump_functions (dump_file
);
4212 /* Topological sort. */
4213 build_toporder_info (&topo
);
4214 /* Do the interprocedural propagation. */
4215 ipcp_propagate_stage (&topo
);
4216 /* Decide what constant propagation and cloning should be performed. */
4217 ipcp_decision_stage (&topo
);
4219 /* Free all IPCP structures. */
4220 free_toporder_info (&topo
);
4221 next_edge_clone
.release ();
4222 symtab
->remove_edge_removal_hook (edge_removal_hook_holder
);
4223 symtab
->remove_edge_duplication_hook (edge_duplication_hook_holder
);
4224 ipa_free_all_structures_after_ipa_cp ();
4226 fprintf (dump_file
, "\nIPA constant propagation end\n");
4230 /* Initialization and computation of IPCP data structures. This is the initial
4231 intraprocedural analysis of functions, which gathers information to be
4232 propagated later on. */
4235 ipcp_generate_summary (void)
4237 struct cgraph_node
*node
;
4240 fprintf (dump_file
, "\nIPA constant propagation start:\n");
4241 ipa_register_cgraph_hooks ();
4243 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
4245 node
->local
.versionable
4246 = tree_versionable_function_p (node
->decl
);
4247 ipa_analyze_node (node
);
4251 /* Write ipcp summary for nodes in SET. */
4254 ipcp_write_summary (void)
4256 ipa_prop_write_jump_functions ();
4259 /* Read ipcp summary. */
4262 ipcp_read_summary (void)
4264 ipa_prop_read_jump_functions ();
4269 const pass_data pass_data_ipa_cp
=
4271 IPA_PASS
, /* type */
4273 OPTGROUP_NONE
, /* optinfo_flags */
4274 TV_IPA_CONSTANT_PROP
, /* tv_id */
4275 0, /* properties_required */
4276 0, /* properties_provided */
4277 0, /* properties_destroyed */
4278 0, /* todo_flags_start */
4279 ( TODO_dump_symtab
| TODO_remove_functions
), /* todo_flags_finish */
4282 class pass_ipa_cp
: public ipa_opt_pass_d
4285 pass_ipa_cp (gcc::context
*ctxt
)
4286 : ipa_opt_pass_d (pass_data_ipa_cp
, ctxt
,
4287 ipcp_generate_summary
, /* generate_summary */
4288 ipcp_write_summary
, /* write_summary */
4289 ipcp_read_summary
, /* read_summary */
4290 ipa_prop_write_all_agg_replacement
, /*
4291 write_optimization_summary */
4292 ipa_prop_read_all_agg_replacement
, /*
4293 read_optimization_summary */
4294 NULL
, /* stmt_fixup */
4295 0, /* function_transform_todo_flags_start */
4296 ipcp_transform_function
, /* function_transform */
4297 NULL
) /* variable_transform */
4300 /* opt_pass methods: */
4301 virtual bool gate (function
*)
4303 /* FIXME: We should remove the optimize check after we ensure we never run
4304 IPA passes when not optimizing. */
4305 return flag_ipa_cp
&& optimize
;
4308 virtual unsigned int execute (function
*) { return ipcp_driver (); }
4310 }; // class pass_ipa_cp
4315 make_pass_ipa_cp (gcc::context
*ctxt
)
4317 return new pass_ipa_cp (ctxt
);
4320 /* Reset all state within ipa-cp.c so that we can rerun the compiler
4321 within the same process. For use by toplev::finalize. */
4324 ipa_cp_c_finalize (void)