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"
110 #include "ipa-prop.h"
112 #include "tree-pass.h"
114 #include "diagnostic.h"
115 #include "tree-pretty-print.h"
116 #include "tree-inline.h"
118 #include "ipa-inline.h"
119 #include "ipa-utils.h"
123 /* Describes a particular source for an IPA-CP value. */
125 struct ipcp_value_source
127 /* Aggregate offset of the source, negative if the source is scalar value of
128 the argument itself. */
129 HOST_WIDE_INT offset
;
130 /* The incoming edge that brought the value. */
131 struct cgraph_edge
*cs
;
132 /* If the jump function that resulted into his value was a pass-through or an
133 ancestor, this is the ipcp_value of the caller from which the described
134 value has been derived. Otherwise it is NULL. */
135 struct ipcp_value
*val
;
136 /* Next pointer in a linked list of sources of a value. */
137 struct ipcp_value_source
*next
;
138 /* If the jump function that resulted into his value was a pass-through or an
139 ancestor, this is the index of the parameter of the caller the jump
140 function references. */
144 /* Describes one particular value stored in struct ipcp_lattice. */
148 /* The actual value for the given parameter. This is either an IPA invariant
149 or a TREE_BINFO describing a type that can be used for
152 /* The list of sources from which this value originates. */
153 struct ipcp_value_source
*sources
;
154 /* Next pointers in a linked list of all values in a lattice. */
155 struct ipcp_value
*next
;
156 /* Next pointers in a linked list of values in a strongly connected component
158 struct ipcp_value
*scc_next
;
159 /* Next pointers in a linked list of SCCs of values sorted topologically
160 according their sources. */
161 struct ipcp_value
*topo_next
;
162 /* A specialized node created for this value, NULL if none has been (so far)
164 struct cgraph_node
*spec_node
;
165 /* Depth first search number and low link for topological sorting of
168 /* Time benefit and size cost that specializing the function for this value
169 would bring about in this function alone. */
170 int local_time_benefit
, local_size_cost
;
171 /* Time benefit and size cost that specializing the function for this value
172 can bring about in it's callees (transitively). */
173 int prop_time_benefit
, prop_size_cost
;
174 /* True if this valye is currently on the topo-sort stack. */
178 /* Lattice describing potential values of a formal parameter of a function, or
179 a part of an aggreagate. TOP is represented by a lattice with zero values
180 and with contains_variable and bottom flags cleared. BOTTOM is represented
181 by a lattice with the bottom flag set. In that case, values and
182 contains_variable flag should be disregarded. */
186 /* The list of known values and types in this lattice. Note that values are
187 not deallocated if a lattice is set to bottom because there may be value
188 sources referencing them. */
189 struct ipcp_value
*values
;
190 /* Number of known values and types in this lattice. */
192 /* The lattice contains a variable component (in addition to values). */
193 bool contains_variable
;
194 /* The value of the lattice is bottom (i.e. variable and unusable for any
199 /* Lattice with an offset to describe a part of an aggregate. */
201 struct ipcp_agg_lattice
: public ipcp_lattice
203 /* Offset that is being described by this lattice. */
204 HOST_WIDE_INT offset
;
205 /* Size so that we don't have to re-compute it every time we traverse the
206 list. Must correspond to TYPE_SIZE of all lat values. */
208 /* Next element of the linked list. */
209 struct ipcp_agg_lattice
*next
;
212 /* Structure containing lattices for a parameter itself and for pieces of
213 aggregates that are passed in the parameter or by a reference in a parameter
214 plus some other useful flags. */
216 struct ipcp_param_lattices
218 /* Lattice describing the value of the parameter itself. */
219 struct ipcp_lattice itself
;
220 /* Lattices describing aggregate parts. */
221 struct ipcp_agg_lattice
*aggs
;
222 /* Number of aggregate lattices */
224 /* True if aggregate data were passed by reference (as opposed to by
227 /* All aggregate lattices contain a variable component (in addition to
229 bool aggs_contain_variable
;
230 /* The value of all aggregate lattices is bottom (i.e. variable and unusable
231 for any propagation). */
234 /* There is a virtual call based on this parameter. */
238 /* Allocation pools for values and their sources in ipa-cp. */
240 alloc_pool ipcp_values_pool
;
241 alloc_pool ipcp_sources_pool
;
242 alloc_pool ipcp_agg_lattice_pool
;
244 /* Maximal count found in program. */
246 static gcov_type max_count
;
248 /* Original overall size of the program. */
250 static long overall_size
, max_new_size
;
252 /* Head of the linked list of topologically sorted values. */
254 static struct ipcp_value
*values_topo
;
256 /* Return the param lattices structure corresponding to the Ith formal
257 parameter of the function described by INFO. */
258 static inline struct ipcp_param_lattices
*
259 ipa_get_parm_lattices (struct ipa_node_params
*info
, int i
)
261 gcc_assert (i
>= 0 && i
< ipa_get_param_count (info
));
262 gcc_checking_assert (!info
->ipcp_orig_node
);
263 gcc_checking_assert (info
->lattices
);
264 return &(info
->lattices
[i
]);
267 /* Return the lattice corresponding to the scalar value of the Ith formal
268 parameter of the function described by INFO. */
269 static inline struct ipcp_lattice
*
270 ipa_get_scalar_lat (struct ipa_node_params
*info
, int i
)
272 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
273 return &plats
->itself
;
276 /* Return whether LAT is a lattice with a single constant and without an
280 ipa_lat_is_single_const (struct ipcp_lattice
*lat
)
283 || lat
->contains_variable
284 || lat
->values_count
!= 1)
290 /* Print V which is extracted from a value in a lattice to F. */
293 print_ipcp_constant_value (FILE * f
, tree v
)
295 if (TREE_CODE (v
) == TREE_BINFO
)
297 fprintf (f
, "BINFO ");
298 print_generic_expr (f
, BINFO_TYPE (v
), 0);
300 else if (TREE_CODE (v
) == ADDR_EXPR
301 && TREE_CODE (TREE_OPERAND (v
, 0)) == CONST_DECL
)
304 print_generic_expr (f
, DECL_INITIAL (TREE_OPERAND (v
, 0)), 0);
307 print_generic_expr (f
, v
, 0);
310 /* Print a lattice LAT to F. */
313 print_lattice (FILE * f
, struct ipcp_lattice
*lat
,
314 bool dump_sources
, bool dump_benefits
)
316 struct ipcp_value
*val
;
321 fprintf (f
, "BOTTOM\n");
325 if (!lat
->values_count
&& !lat
->contains_variable
)
327 fprintf (f
, "TOP\n");
331 if (lat
->contains_variable
)
333 fprintf (f
, "VARIABLE");
339 for (val
= lat
->values
; val
; val
= val
->next
)
341 if (dump_benefits
&& prev
)
343 else if (!dump_benefits
&& prev
)
348 print_ipcp_constant_value (f
, val
->value
);
352 struct ipcp_value_source
*s
;
354 fprintf (f
, " [from:");
355 for (s
= val
->sources
; s
; s
= s
->next
)
356 fprintf (f
, " %i(%i)", s
->cs
->caller
->order
,
362 fprintf (f
, " [loc_time: %i, loc_size: %i, "
363 "prop_time: %i, prop_size: %i]\n",
364 val
->local_time_benefit
, val
->local_size_cost
,
365 val
->prop_time_benefit
, val
->prop_size_cost
);
371 /* Print all ipcp_lattices of all functions to F. */
374 print_all_lattices (FILE * f
, bool dump_sources
, bool dump_benefits
)
376 struct cgraph_node
*node
;
379 fprintf (f
, "\nLattices:\n");
380 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
382 struct ipa_node_params
*info
;
384 info
= IPA_NODE_REF (node
);
385 fprintf (f
, " Node: %s/%i:\n", node
->name (),
387 count
= ipa_get_param_count (info
);
388 for (i
= 0; i
< count
; i
++)
390 struct ipcp_agg_lattice
*aglat
;
391 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
392 fprintf (f
, " param [%d]: ", i
);
393 print_lattice (f
, &plats
->itself
, dump_sources
, dump_benefits
);
395 if (plats
->virt_call
)
396 fprintf (f
, " virt_call flag set\n");
398 if (plats
->aggs_bottom
)
400 fprintf (f
, " AGGS BOTTOM\n");
403 if (plats
->aggs_contain_variable
)
404 fprintf (f
, " AGGS VARIABLE\n");
405 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
407 fprintf (f
, " %soffset " HOST_WIDE_INT_PRINT_DEC
": ",
408 plats
->aggs_by_ref
? "ref " : "", aglat
->offset
);
409 print_lattice (f
, aglat
, dump_sources
, dump_benefits
);
415 /* Determine whether it is at all technically possible to create clones of NODE
416 and store this information in the ipa_node_params structure associated
420 determine_versionability (struct cgraph_node
*node
)
422 const char *reason
= NULL
;
424 /* There are a number of generic reasons functions cannot be versioned. We
425 also cannot remove parameters if there are type attributes such as fnspec
427 if (node
->alias
|| node
->thunk
.thunk_p
)
428 reason
= "alias or thunk";
429 else if (!node
->local
.versionable
)
430 reason
= "not a tree_versionable_function";
431 else if (cgraph_function_body_availability (node
) <= AVAIL_OVERWRITABLE
)
432 reason
= "insufficient body availability";
433 else if (!opt_for_fn (node
->decl
, optimize
)
434 || !opt_for_fn (node
->decl
, flag_ipa_cp
))
435 reason
= "non-optimized function";
436 else if (lookup_attribute ("omp declare simd", DECL_ATTRIBUTES (node
->decl
)))
438 /* Ideally we should clone the SIMD clones themselves and create
439 vector copies of them, so IPA-cp and SIMD clones can happily
440 coexist, but that may not be worth the effort. */
441 reason
= "function has SIMD clones";
443 /* Don't clone decls local to a comdat group; it breaks and for C++
444 decloned constructors, inlining is always better anyway. */
445 else if (symtab_comdat_local_p (node
))
446 reason
= "comdat-local function";
448 if (reason
&& dump_file
&& !node
->alias
&& !node
->thunk
.thunk_p
)
449 fprintf (dump_file
, "Function %s/%i is not versionable, reason: %s.\n",
450 node
->name (), node
->order
, reason
);
452 node
->local
.versionable
= (reason
== NULL
);
455 /* Return true if it is at all technically possible to create clones of a
459 ipcp_versionable_function_p (struct cgraph_node
*node
)
461 return node
->local
.versionable
;
464 /* Structure holding accumulated information about callers of a node. */
466 struct caller_statistics
469 int n_calls
, n_hot_calls
, freq_sum
;
472 /* Initialize fields of STAT to zeroes. */
475 init_caller_stats (struct caller_statistics
*stats
)
477 stats
->count_sum
= 0;
479 stats
->n_hot_calls
= 0;
483 /* Worker callback of cgraph_for_node_and_aliases accumulating statistics of
484 non-thunk incoming edges to NODE. */
487 gather_caller_stats (struct cgraph_node
*node
, void *data
)
489 struct caller_statistics
*stats
= (struct caller_statistics
*) data
;
490 struct cgraph_edge
*cs
;
492 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
493 if (cs
->caller
->thunk
.thunk_p
)
494 cgraph_for_node_and_aliases (cs
->caller
, gather_caller_stats
,
498 stats
->count_sum
+= cs
->count
;
499 stats
->freq_sum
+= cs
->frequency
;
501 if (cgraph_maybe_hot_edge_p (cs
))
502 stats
->n_hot_calls
++;
508 /* Return true if this NODE is viable candidate for cloning. */
511 ipcp_cloning_candidate_p (struct cgraph_node
*node
)
513 struct caller_statistics stats
;
515 gcc_checking_assert (cgraph_function_with_gimple_body_p (node
));
517 if (!flag_ipa_cp_clone
)
520 fprintf (dump_file
, "Not considering %s for cloning; "
521 "-fipa-cp-clone disabled.\n",
526 if (!optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node
->decl
)))
529 fprintf (dump_file
, "Not considering %s for cloning; "
530 "optimizing it for size.\n",
535 init_caller_stats (&stats
);
536 cgraph_for_node_and_aliases (node
, gather_caller_stats
, &stats
, false);
538 if (inline_summary (node
)->self_size
< stats
.n_calls
)
541 fprintf (dump_file
, "Considering %s for cloning; code might shrink.\n",
546 /* When profile is available and function is hot, propagate into it even if
547 calls seems cold; constant propagation can improve function's speed
551 if (stats
.count_sum
> node
->count
* 90 / 100)
554 fprintf (dump_file
, "Considering %s for cloning; "
555 "usually called directly.\n",
560 if (!stats
.n_hot_calls
)
563 fprintf (dump_file
, "Not considering %s for cloning; no hot calls.\n",
568 fprintf (dump_file
, "Considering %s for cloning.\n",
573 /* Arrays representing a topological ordering of call graph nodes and a stack
574 of noes used during constant propagation. */
578 struct cgraph_node
**order
;
579 struct cgraph_node
**stack
;
580 int nnodes
, stack_top
;
583 /* Allocate the arrays in TOPO and topologically sort the nodes into order. */
586 build_toporder_info (struct topo_info
*topo
)
588 topo
->order
= XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
589 topo
->stack
= XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
591 topo
->nnodes
= ipa_reduced_postorder (topo
->order
, true, true, NULL
);
594 /* Free information about strongly connected components and the arrays in
598 free_toporder_info (struct topo_info
*topo
)
600 ipa_free_postorder_info ();
605 /* Add NODE to the stack in TOPO, unless it is already there. */
608 push_node_to_stack (struct topo_info
*topo
, struct cgraph_node
*node
)
610 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
611 if (info
->node_enqueued
)
613 info
->node_enqueued
= 1;
614 topo
->stack
[topo
->stack_top
++] = node
;
617 /* Pop a node from the stack in TOPO and return it or return NULL if the stack
620 static struct cgraph_node
*
621 pop_node_from_stack (struct topo_info
*topo
)
625 struct cgraph_node
*node
;
627 node
= topo
->stack
[topo
->stack_top
];
628 IPA_NODE_REF (node
)->node_enqueued
= 0;
635 /* Set lattice LAT to bottom and return true if it previously was not set as
639 set_lattice_to_bottom (struct ipcp_lattice
*lat
)
641 bool ret
= !lat
->bottom
;
646 /* Mark lattice as containing an unknown value and return true if it previously
647 was not marked as such. */
650 set_lattice_contains_variable (struct ipcp_lattice
*lat
)
652 bool ret
= !lat
->contains_variable
;
653 lat
->contains_variable
= true;
657 /* Set all aggegate lattices in PLATS to bottom and return true if they were
658 not previously set as such. */
661 set_agg_lats_to_bottom (struct ipcp_param_lattices
*plats
)
663 bool ret
= !plats
->aggs_bottom
;
664 plats
->aggs_bottom
= true;
668 /* Mark all aggegate lattices in PLATS as containing an unknown value and
669 return true if they were not previously marked as such. */
672 set_agg_lats_contain_variable (struct ipcp_param_lattices
*plats
)
674 bool ret
= !plats
->aggs_contain_variable
;
675 plats
->aggs_contain_variable
= true;
679 /* Mark bot aggregate and scalar lattices as containing an unknown variable,
680 return true is any of them has not been marked as such so far. */
683 set_all_contains_variable (struct ipcp_param_lattices
*plats
)
685 bool ret
= !plats
->itself
.contains_variable
|| !plats
->aggs_contain_variable
;
686 plats
->itself
.contains_variable
= true;
687 plats
->aggs_contain_variable
= true;
691 /* Initialize ipcp_lattices. */
694 initialize_node_lattices (struct cgraph_node
*node
)
696 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
697 struct cgraph_edge
*ie
;
698 bool disable
= false, variable
= false;
701 gcc_checking_assert (cgraph_function_with_gimple_body_p (node
));
702 if (!node
->local
.local
)
704 /* When cloning is allowed, we can assume that externally visible
705 functions are not called. We will compensate this by cloning
707 if (ipcp_versionable_function_p (node
)
708 && ipcp_cloning_candidate_p (node
))
714 if (disable
|| variable
)
716 for (i
= 0; i
< ipa_get_param_count (info
) ; i
++)
718 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
721 set_lattice_to_bottom (&plats
->itself
);
722 set_agg_lats_to_bottom (plats
);
725 set_all_contains_variable (plats
);
727 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
728 && !node
->alias
&& !node
->thunk
.thunk_p
)
729 fprintf (dump_file
, "Marking all lattices of %s/%i as %s\n",
730 node
->name (), node
->order
,
731 disable
? "BOTTOM" : "VARIABLE");
734 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
735 if (ie
->indirect_info
->polymorphic
736 && ie
->indirect_info
->param_index
>= 0)
738 gcc_checking_assert (ie
->indirect_info
->param_index
>= 0);
739 ipa_get_parm_lattices (info
,
740 ie
->indirect_info
->param_index
)->virt_call
= 1;
744 /* Return the result of a (possibly arithmetic) pass through jump function
745 JFUNC on the constant value INPUT. Return NULL_TREE if that cannot be
746 determined or be considered an interprocedural invariant. */
749 ipa_get_jf_pass_through_result (struct ipa_jump_func
*jfunc
, tree input
)
753 if (TREE_CODE (input
) == TREE_BINFO
)
755 if (ipa_get_jf_pass_through_type_preserved (jfunc
))
757 gcc_checking_assert (ipa_get_jf_pass_through_operation (jfunc
)
764 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
767 gcc_checking_assert (is_gimple_ip_invariant (input
));
768 if (TREE_CODE_CLASS (ipa_get_jf_pass_through_operation (jfunc
))
770 restype
= boolean_type_node
;
772 restype
= TREE_TYPE (input
);
773 res
= fold_binary (ipa_get_jf_pass_through_operation (jfunc
), restype
,
774 input
, ipa_get_jf_pass_through_operand (jfunc
));
776 if (res
&& !is_gimple_ip_invariant (res
))
782 /* Return the result of an ancestor jump function JFUNC on the constant value
783 INPUT. Return NULL_TREE if that cannot be determined. */
786 ipa_get_jf_ancestor_result (struct ipa_jump_func
*jfunc
, tree input
)
788 if (TREE_CODE (input
) == TREE_BINFO
)
790 if (!ipa_get_jf_ancestor_type_preserved (jfunc
))
792 return get_binfo_at_offset (input
,
793 ipa_get_jf_ancestor_offset (jfunc
),
794 ipa_get_jf_ancestor_type (jfunc
));
796 else if (TREE_CODE (input
) == ADDR_EXPR
)
798 tree t
= TREE_OPERAND (input
, 0);
799 t
= build_ref_for_offset (EXPR_LOCATION (t
), t
,
800 ipa_get_jf_ancestor_offset (jfunc
),
801 ipa_get_jf_ancestor_type (jfunc
), NULL
, false);
802 return build_fold_addr_expr (t
);
808 /* Determine whether JFUNC evaluates to a known value (that is either a
809 constant or a binfo) and if so, return it. Otherwise return NULL. INFO
810 describes the caller node so that pass-through jump functions can be
814 ipa_value_from_jfunc (struct ipa_node_params
*info
, struct ipa_jump_func
*jfunc
)
816 if (jfunc
->type
== IPA_JF_CONST
)
817 return ipa_get_jf_constant (jfunc
);
818 else if (jfunc
->type
== IPA_JF_KNOWN_TYPE
)
819 return ipa_binfo_from_known_type_jfunc (jfunc
);
820 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
821 || jfunc
->type
== IPA_JF_ANCESTOR
)
826 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
827 idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
829 idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
831 if (info
->ipcp_orig_node
)
832 input
= info
->known_vals
[idx
];
835 struct ipcp_lattice
*lat
;
839 gcc_checking_assert (!flag_ipa_cp
);
842 lat
= ipa_get_scalar_lat (info
, idx
);
843 if (!ipa_lat_is_single_const (lat
))
845 input
= lat
->values
->value
;
851 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
852 return ipa_get_jf_pass_through_result (jfunc
, input
);
854 return ipa_get_jf_ancestor_result (jfunc
, input
);
861 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
862 bottom, not containing a variable component and without any known value at
866 ipcp_verify_propagated_values (void)
868 struct cgraph_node
*node
;
870 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
872 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
873 int i
, count
= ipa_get_param_count (info
);
875 for (i
= 0; i
< count
; i
++)
877 struct ipcp_lattice
*lat
= ipa_get_scalar_lat (info
, i
);
880 && !lat
->contains_variable
881 && lat
->values_count
== 0)
885 fprintf (dump_file
, "\nIPA lattices after constant "
887 print_all_lattices (dump_file
, true, false);
896 /* Return true iff X and Y should be considered equal values by IPA-CP. */
899 values_equal_for_ipcp_p (tree x
, tree y
)
901 gcc_checking_assert (x
!= NULL_TREE
&& y
!= NULL_TREE
);
906 if (TREE_CODE (x
) == TREE_BINFO
|| TREE_CODE (y
) == TREE_BINFO
)
909 if (TREE_CODE (x
) == ADDR_EXPR
910 && TREE_CODE (y
) == ADDR_EXPR
911 && TREE_CODE (TREE_OPERAND (x
, 0)) == CONST_DECL
912 && TREE_CODE (TREE_OPERAND (y
, 0)) == CONST_DECL
)
913 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x
, 0)),
914 DECL_INITIAL (TREE_OPERAND (y
, 0)), 0);
916 return operand_equal_p (x
, y
, 0);
919 /* Add a new value source to VAL, marking that a value comes from edge CS and
920 (if the underlying jump function is a pass-through or an ancestor one) from
921 a caller value SRC_VAL of a caller parameter described by SRC_INDEX. OFFSET
922 is negative if the source was the scalar value of the parameter itself or
923 the offset within an aggregate. */
926 add_value_source (struct ipcp_value
*val
, struct cgraph_edge
*cs
,
927 struct ipcp_value
*src_val
, int src_idx
, HOST_WIDE_INT offset
)
929 struct ipcp_value_source
*src
;
931 src
= (struct ipcp_value_source
*) pool_alloc (ipcp_sources_pool
);
932 src
->offset
= offset
;
935 src
->index
= src_idx
;
937 src
->next
= val
->sources
;
941 /* Try to add NEWVAL to LAT, potentially creating a new struct ipcp_value for
942 it. CS, SRC_VAL SRC_INDEX and OFFSET are meant for add_value_source and
943 have the same meaning. */
946 add_value_to_lattice (struct ipcp_lattice
*lat
, tree newval
,
947 struct cgraph_edge
*cs
, struct ipcp_value
*src_val
,
948 int src_idx
, HOST_WIDE_INT offset
)
950 struct ipcp_value
*val
;
955 for (val
= lat
->values
; val
; val
= val
->next
)
956 if (values_equal_for_ipcp_p (val
->value
, newval
))
958 if (ipa_edge_within_scc (cs
))
960 struct ipcp_value_source
*s
;
961 for (s
= val
->sources
; s
; s
= s
->next
)
968 add_value_source (val
, cs
, src_val
, src_idx
, offset
);
972 if (lat
->values_count
== PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE
))
974 /* We can only free sources, not the values themselves, because sources
975 of other values in this this SCC might point to them. */
976 for (val
= lat
->values
; val
; val
= val
->next
)
980 struct ipcp_value_source
*src
= val
->sources
;
981 val
->sources
= src
->next
;
982 pool_free (ipcp_sources_pool
, src
);
987 return set_lattice_to_bottom (lat
);
991 val
= (struct ipcp_value
*) pool_alloc (ipcp_values_pool
);
992 memset (val
, 0, sizeof (*val
));
994 add_value_source (val
, cs
, src_val
, src_idx
, offset
);
996 val
->next
= lat
->values
;
1001 /* Like above but passes a special value of offset to distinguish that the
1002 origin is the scalar value of the parameter rather than a part of an
1006 add_scalar_value_to_lattice (struct ipcp_lattice
*lat
, tree newval
,
1007 struct cgraph_edge
*cs
,
1008 struct ipcp_value
*src_val
, int src_idx
)
1010 return add_value_to_lattice (lat
, newval
, cs
, src_val
, src_idx
, -1);
1013 /* Propagate values through a pass-through jump function JFUNC associated with
1014 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1015 is the index of the source parameter. */
1018 propagate_vals_accross_pass_through (struct cgraph_edge
*cs
,
1019 struct ipa_jump_func
*jfunc
,
1020 struct ipcp_lattice
*src_lat
,
1021 struct ipcp_lattice
*dest_lat
,
1024 struct ipcp_value
*src_val
;
1027 /* Do not create new values when propagating within an SCC because if there
1028 are arithmetic functions with circular dependencies, there is infinite
1029 number of them and we would just make lattices bottom. */
1030 if ((ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1031 && ipa_edge_within_scc (cs
))
1032 ret
= set_lattice_contains_variable (dest_lat
);
1034 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1036 tree cstval
= ipa_get_jf_pass_through_result (jfunc
, src_val
->value
);
1039 ret
|= add_scalar_value_to_lattice (dest_lat
, cstval
, cs
, src_val
,
1042 ret
|= set_lattice_contains_variable (dest_lat
);
1048 /* Propagate values through an ancestor jump function JFUNC associated with
1049 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1050 is the index of the source parameter. */
1053 propagate_vals_accross_ancestor (struct cgraph_edge
*cs
,
1054 struct ipa_jump_func
*jfunc
,
1055 struct ipcp_lattice
*src_lat
,
1056 struct ipcp_lattice
*dest_lat
,
1059 struct ipcp_value
*src_val
;
1062 if (ipa_edge_within_scc (cs
))
1063 return set_lattice_contains_variable (dest_lat
);
1065 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1067 tree t
= ipa_get_jf_ancestor_result (jfunc
, src_val
->value
);
1070 ret
|= add_scalar_value_to_lattice (dest_lat
, t
, cs
, src_val
, src_idx
);
1072 ret
|= set_lattice_contains_variable (dest_lat
);
1078 /* Propagate scalar values across jump function JFUNC that is associated with
1079 edge CS and put the values into DEST_LAT. */
1082 propagate_scalar_accross_jump_function (struct cgraph_edge
*cs
,
1083 struct ipa_jump_func
*jfunc
,
1084 struct ipcp_lattice
*dest_lat
)
1086 if (dest_lat
->bottom
)
1089 if (jfunc
->type
== IPA_JF_CONST
1090 || jfunc
->type
== IPA_JF_KNOWN_TYPE
)
1094 if (jfunc
->type
== IPA_JF_KNOWN_TYPE
)
1096 val
= ipa_binfo_from_known_type_jfunc (jfunc
);
1098 return set_lattice_contains_variable (dest_lat
);
1101 val
= ipa_get_jf_constant (jfunc
);
1102 return add_scalar_value_to_lattice (dest_lat
, val
, cs
, NULL
, 0);
1104 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1105 || jfunc
->type
== IPA_JF_ANCESTOR
)
1107 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1108 struct ipcp_lattice
*src_lat
;
1112 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1113 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1115 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1117 src_lat
= ipa_get_scalar_lat (caller_info
, src_idx
);
1118 if (src_lat
->bottom
)
1119 return set_lattice_contains_variable (dest_lat
);
1121 /* If we would need to clone the caller and cannot, do not propagate. */
1122 if (!ipcp_versionable_function_p (cs
->caller
)
1123 && (src_lat
->contains_variable
1124 || (src_lat
->values_count
> 1)))
1125 return set_lattice_contains_variable (dest_lat
);
1127 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1128 ret
= propagate_vals_accross_pass_through (cs
, jfunc
, src_lat
,
1131 ret
= propagate_vals_accross_ancestor (cs
, jfunc
, src_lat
, dest_lat
,
1134 if (src_lat
->contains_variable
)
1135 ret
|= set_lattice_contains_variable (dest_lat
);
1140 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1141 use it for indirect inlining), we should propagate them too. */
1142 return set_lattice_contains_variable (dest_lat
);
1145 /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
1146 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
1147 other cases, return false). If there are no aggregate items, set
1148 aggs_by_ref to NEW_AGGS_BY_REF. */
1151 set_check_aggs_by_ref (struct ipcp_param_lattices
*dest_plats
,
1152 bool new_aggs_by_ref
)
1154 if (dest_plats
->aggs
)
1156 if (dest_plats
->aggs_by_ref
!= new_aggs_by_ref
)
1158 set_agg_lats_to_bottom (dest_plats
);
1163 dest_plats
->aggs_by_ref
= new_aggs_by_ref
;
1167 /* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
1168 already existing lattice for the given OFFSET and SIZE, marking all skipped
1169 lattices as containing variable and checking for overlaps. If there is no
1170 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
1171 it with offset, size and contains_variable to PRE_EXISTING, and return true,
1172 unless there are too many already. If there are two many, return false. If
1173 there are overlaps turn whole DEST_PLATS to bottom and return false. If any
1174 skipped lattices were newly marked as containing variable, set *CHANGE to
1178 merge_agg_lats_step (struct ipcp_param_lattices
*dest_plats
,
1179 HOST_WIDE_INT offset
, HOST_WIDE_INT val_size
,
1180 struct ipcp_agg_lattice
***aglat
,
1181 bool pre_existing
, bool *change
)
1183 gcc_checking_assert (offset
>= 0);
1185 while (**aglat
&& (**aglat
)->offset
< offset
)
1187 if ((**aglat
)->offset
+ (**aglat
)->size
> offset
)
1189 set_agg_lats_to_bottom (dest_plats
);
1192 *change
|= set_lattice_contains_variable (**aglat
);
1193 *aglat
= &(**aglat
)->next
;
1196 if (**aglat
&& (**aglat
)->offset
== offset
)
1198 if ((**aglat
)->size
!= val_size
1200 && (**aglat
)->next
->offset
< offset
+ val_size
))
1202 set_agg_lats_to_bottom (dest_plats
);
1205 gcc_checking_assert (!(**aglat
)->next
1206 || (**aglat
)->next
->offset
>= offset
+ val_size
);
1211 struct ipcp_agg_lattice
*new_al
;
1213 if (**aglat
&& (**aglat
)->offset
< offset
+ val_size
)
1215 set_agg_lats_to_bottom (dest_plats
);
1218 if (dest_plats
->aggs_count
== PARAM_VALUE (PARAM_IPA_MAX_AGG_ITEMS
))
1220 dest_plats
->aggs_count
++;
1221 new_al
= (struct ipcp_agg_lattice
*) pool_alloc (ipcp_agg_lattice_pool
);
1222 memset (new_al
, 0, sizeof (*new_al
));
1224 new_al
->offset
= offset
;
1225 new_al
->size
= val_size
;
1226 new_al
->contains_variable
= pre_existing
;
1228 new_al
->next
= **aglat
;
1234 /* Set all AGLAT and all other aggregate lattices reachable by next pointers as
1235 containing an unknown value. */
1238 set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice
*aglat
)
1243 ret
|= set_lattice_contains_variable (aglat
);
1244 aglat
= aglat
->next
;
1249 /* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
1250 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source
1251 parameter used for lattice value sources. Return true if DEST_PLATS changed
1255 merge_aggregate_lattices (struct cgraph_edge
*cs
,
1256 struct ipcp_param_lattices
*dest_plats
,
1257 struct ipcp_param_lattices
*src_plats
,
1258 int src_idx
, HOST_WIDE_INT offset_delta
)
1260 bool pre_existing
= dest_plats
->aggs
!= NULL
;
1261 struct ipcp_agg_lattice
**dst_aglat
;
1264 if (set_check_aggs_by_ref (dest_plats
, src_plats
->aggs_by_ref
))
1266 if (src_plats
->aggs_bottom
)
1267 return set_agg_lats_contain_variable (dest_plats
);
1268 if (src_plats
->aggs_contain_variable
)
1269 ret
|= set_agg_lats_contain_variable (dest_plats
);
1270 dst_aglat
= &dest_plats
->aggs
;
1272 for (struct ipcp_agg_lattice
*src_aglat
= src_plats
->aggs
;
1274 src_aglat
= src_aglat
->next
)
1276 HOST_WIDE_INT new_offset
= src_aglat
->offset
- offset_delta
;
1280 if (merge_agg_lats_step (dest_plats
, new_offset
, src_aglat
->size
,
1281 &dst_aglat
, pre_existing
, &ret
))
1283 struct ipcp_agg_lattice
*new_al
= *dst_aglat
;
1285 dst_aglat
= &(*dst_aglat
)->next
;
1286 if (src_aglat
->bottom
)
1288 ret
|= set_lattice_contains_variable (new_al
);
1291 if (src_aglat
->contains_variable
)
1292 ret
|= set_lattice_contains_variable (new_al
);
1293 for (struct ipcp_value
*val
= src_aglat
->values
;
1296 ret
|= add_value_to_lattice (new_al
, val
->value
, cs
, val
, src_idx
,
1299 else if (dest_plats
->aggs_bottom
)
1302 ret
|= set_chain_of_aglats_contains_variable (*dst_aglat
);
1306 /* Determine whether there is anything to propagate FROM SRC_PLATS through a
1307 pass-through JFUNC and if so, whether it has conform and conforms to the
1308 rules about propagating values passed by reference. */
1311 agg_pass_through_permissible_p (struct ipcp_param_lattices
*src_plats
,
1312 struct ipa_jump_func
*jfunc
)
1314 return src_plats
->aggs
1315 && (!src_plats
->aggs_by_ref
1316 || ipa_get_jf_pass_through_agg_preserved (jfunc
));
1319 /* Propagate scalar values across jump function JFUNC that is associated with
1320 edge CS and put the values into DEST_LAT. */
1323 propagate_aggs_accross_jump_function (struct cgraph_edge
*cs
,
1324 struct ipa_jump_func
*jfunc
,
1325 struct ipcp_param_lattices
*dest_plats
)
1329 if (dest_plats
->aggs_bottom
)
1332 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1333 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
1335 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1336 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1337 struct ipcp_param_lattices
*src_plats
;
1339 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
1340 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
1342 /* Currently we do not produce clobber aggregate jump
1343 functions, replace with merging when we do. */
1344 gcc_assert (!jfunc
->agg
.items
);
1345 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
,
1349 ret
|= set_agg_lats_contain_variable (dest_plats
);
1351 else if (jfunc
->type
== IPA_JF_ANCESTOR
1352 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
1354 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1355 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1356 struct ipcp_param_lattices
*src_plats
;
1358 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
1359 if (src_plats
->aggs
&& src_plats
->aggs_by_ref
)
1361 /* Currently we do not produce clobber aggregate jump
1362 functions, replace with merging when we do. */
1363 gcc_assert (!jfunc
->agg
.items
);
1364 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
, src_idx
,
1365 ipa_get_jf_ancestor_offset (jfunc
));
1367 else if (!src_plats
->aggs_by_ref
)
1368 ret
|= set_agg_lats_to_bottom (dest_plats
);
1370 ret
|= set_agg_lats_contain_variable (dest_plats
);
1372 else if (jfunc
->agg
.items
)
1374 bool pre_existing
= dest_plats
->aggs
!= NULL
;
1375 struct ipcp_agg_lattice
**aglat
= &dest_plats
->aggs
;
1376 struct ipa_agg_jf_item
*item
;
1379 if (set_check_aggs_by_ref (dest_plats
, jfunc
->agg
.by_ref
))
1382 FOR_EACH_VEC_ELT (*jfunc
->agg
.items
, i
, item
)
1384 HOST_WIDE_INT val_size
;
1386 if (item
->offset
< 0)
1388 gcc_checking_assert (is_gimple_ip_invariant (item
->value
));
1389 val_size
= tree_to_uhwi (TYPE_SIZE (TREE_TYPE (item
->value
)));
1391 if (merge_agg_lats_step (dest_plats
, item
->offset
, val_size
,
1392 &aglat
, pre_existing
, &ret
))
1394 ret
|= add_value_to_lattice (*aglat
, item
->value
, cs
, NULL
, 0, 0);
1395 aglat
= &(*aglat
)->next
;
1397 else if (dest_plats
->aggs_bottom
)
1401 ret
|= set_chain_of_aglats_contains_variable (*aglat
);
1404 ret
|= set_agg_lats_contain_variable (dest_plats
);
1409 /* Propagate constants from the caller to the callee of CS. INFO describes the
1413 propagate_constants_accross_call (struct cgraph_edge
*cs
)
1415 struct ipa_node_params
*callee_info
;
1416 enum availability availability
;
1417 struct cgraph_node
*callee
, *alias_or_thunk
;
1418 struct ipa_edge_args
*args
;
1420 int i
, args_count
, parms_count
;
1422 callee
= cgraph_function_node (cs
->callee
, &availability
);
1423 if (!callee
->definition
)
1425 gcc_checking_assert (cgraph_function_with_gimple_body_p (callee
));
1426 callee_info
= IPA_NODE_REF (callee
);
1428 args
= IPA_EDGE_REF (cs
);
1429 args_count
= ipa_get_cs_argument_count (args
);
1430 parms_count
= ipa_get_param_count (callee_info
);
1432 /* If this call goes through a thunk we must not propagate to the first (0th)
1433 parameter. However, we might need to uncover a thunk from below a series
1434 of aliases first. */
1435 alias_or_thunk
= cs
->callee
;
1436 while (alias_or_thunk
->alias
)
1437 alias_or_thunk
= cgraph_alias_target (alias_or_thunk
);
1438 if (alias_or_thunk
->thunk
.thunk_p
)
1440 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
1447 for (; (i
< args_count
) && (i
< parms_count
); i
++)
1449 struct ipa_jump_func
*jump_func
= ipa_get_ith_jump_func (args
, i
);
1450 struct ipcp_param_lattices
*dest_plats
;
1452 dest_plats
= ipa_get_parm_lattices (callee_info
, i
);
1453 if (availability
== AVAIL_OVERWRITABLE
)
1454 ret
|= set_all_contains_variable (dest_plats
);
1457 ret
|= propagate_scalar_accross_jump_function (cs
, jump_func
,
1458 &dest_plats
->itself
);
1459 ret
|= propagate_aggs_accross_jump_function (cs
, jump_func
,
1463 for (; i
< parms_count
; i
++)
1464 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
, i
));
1469 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
1470 (which can contain both constants and binfos), KNOWN_BINFOS, KNOWN_AGGS or
1471 AGG_REPS return the destination. The latter three can be NULL. If AGG_REPS
1472 is not NULL, KNOWN_AGGS is ignored. */
1475 ipa_get_indirect_edge_target_1 (struct cgraph_edge
*ie
,
1476 vec
<tree
> known_vals
,
1477 vec
<tree
> known_binfos
,
1478 vec
<ipa_agg_jump_function_p
> known_aggs
,
1479 struct ipa_agg_replacement_value
*agg_reps
)
1481 int param_index
= ie
->indirect_info
->param_index
;
1482 HOST_WIDE_INT token
, anc_offset
;
1487 if (param_index
== -1
1488 || known_vals
.length () <= (unsigned int) param_index
)
1491 if (!ie
->indirect_info
->polymorphic
)
1495 if (ie
->indirect_info
->agg_contents
)
1502 if (agg_reps
->index
== param_index
1503 && agg_reps
->offset
== ie
->indirect_info
->offset
1504 && agg_reps
->by_ref
== ie
->indirect_info
->by_ref
)
1506 t
= agg_reps
->value
;
1509 agg_reps
= agg_reps
->next
;
1512 else if (known_aggs
.length () > (unsigned int) param_index
)
1514 struct ipa_agg_jump_function
*agg
;
1515 agg
= known_aggs
[param_index
];
1516 t
= ipa_find_agg_cst_for_param (agg
, ie
->indirect_info
->offset
,
1517 ie
->indirect_info
->by_ref
);
1523 t
= known_vals
[param_index
];
1526 TREE_CODE (t
) == ADDR_EXPR
1527 && TREE_CODE (TREE_OPERAND (t
, 0)) == FUNCTION_DECL
)
1528 return TREE_OPERAND (t
, 0);
1533 if (!flag_devirtualize
)
1536 gcc_assert (!ie
->indirect_info
->agg_contents
);
1537 token
= ie
->indirect_info
->otr_token
;
1538 anc_offset
= ie
->indirect_info
->offset
;
1539 otr_type
= ie
->indirect_info
->otr_type
;
1543 /* Try to work out value of virtual table pointer value in replacemnets. */
1544 if (!t
&& agg_reps
&& !ie
->indirect_info
->by_ref
)
1548 if (agg_reps
->index
== param_index
1549 && agg_reps
->offset
== ie
->indirect_info
->offset
1550 && agg_reps
->by_ref
)
1552 t
= agg_reps
->value
;
1555 agg_reps
= agg_reps
->next
;
1559 /* Try to work out value of virtual table pointer value in known
1560 aggregate values. */
1561 if (!t
&& known_aggs
.length () > (unsigned int) param_index
1562 && !ie
->indirect_info
->by_ref
)
1564 struct ipa_agg_jump_function
*agg
;
1565 agg
= known_aggs
[param_index
];
1566 t
= ipa_find_agg_cst_for_param (agg
, ie
->indirect_info
->offset
,
1570 /* If we found the virtual table pointer, lookup the target. */
1574 unsigned HOST_WIDE_INT offset
;
1575 if (vtable_pointer_value_to_vtable (t
, &vtable
, &offset
))
1577 target
= gimple_get_virt_method_for_vtable (ie
->indirect_info
->otr_token
,
1581 if ((TREE_CODE (TREE_TYPE (target
)) == FUNCTION_TYPE
1582 && DECL_FUNCTION_CODE (target
) == BUILT_IN_UNREACHABLE
)
1583 || !possible_polymorphic_call_target_p
1584 (ie
, cgraph_get_node (target
)))
1588 "Type inconsident devirtualization: %s/%i->%s\n",
1589 ie
->caller
->name (), ie
->caller
->order
,
1590 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (target
)));
1591 target
= builtin_decl_implicit (BUILT_IN_UNREACHABLE
);
1592 cgraph_get_create_node (target
);
1599 /* Did we work out BINFO via type propagation? */
1600 if (!t
&& known_binfos
.length () > (unsigned int) param_index
)
1601 t
= known_binfos
[param_index
];
1602 /* Or do we know the constant value of pointer? */
1604 t
= known_vals
[param_index
];
1608 if (TREE_CODE (t
) != TREE_BINFO
)
1610 ipa_polymorphic_call_context context
;
1611 vec
<cgraph_node
*>targets
;
1614 if (!get_polymorphic_call_info_from_invariant
1615 (&context
, t
, ie
->indirect_info
->otr_type
,
1618 targets
= possible_polymorphic_call_targets
1619 (ie
->indirect_info
->otr_type
,
1620 ie
->indirect_info
->otr_token
,
1622 if (!final
|| targets
.length () > 1)
1624 if (targets
.length () == 1)
1625 target
= targets
[0]->decl
;
1627 target
= builtin_decl_implicit (BUILT_IN_UNREACHABLE
);
1633 binfo
= get_binfo_at_offset (t
, anc_offset
, otr_type
);
1636 target
= gimple_get_virt_method_for_binfo (token
, binfo
);
1638 #ifdef ENABLE_CHECKING
1640 gcc_assert (possible_polymorphic_call_target_p
1641 (ie
, cgraph_get_node (target
)));
1648 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
1649 (which can contain both constants and binfos), KNOWN_BINFOS (which can be
1650 NULL) or KNOWN_AGGS (which also can be NULL) return the destination. */
1653 ipa_get_indirect_edge_target (struct cgraph_edge
*ie
,
1654 vec
<tree
> known_vals
,
1655 vec
<tree
> known_binfos
,
1656 vec
<ipa_agg_jump_function_p
> known_aggs
)
1658 return ipa_get_indirect_edge_target_1 (ie
, known_vals
, known_binfos
,
1662 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
1663 and KNOWN_BINFOS. */
1666 devirtualization_time_bonus (struct cgraph_node
*node
,
1667 vec
<tree
> known_csts
,
1668 vec
<tree
> known_binfos
,
1669 vec
<ipa_agg_jump_function_p
> known_aggs
)
1671 struct cgraph_edge
*ie
;
1674 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
1676 struct cgraph_node
*callee
;
1677 struct inline_summary
*isummary
;
1680 target
= ipa_get_indirect_edge_target (ie
, known_csts
, known_binfos
,
1685 /* Only bare minimum benefit for clearly un-inlineable targets. */
1687 callee
= cgraph_get_node (target
);
1688 if (!callee
|| !callee
->definition
)
1690 isummary
= inline_summary (callee
);
1691 if (!isummary
->inlinable
)
1694 /* FIXME: The values below need re-considering and perhaps also
1695 integrating into the cost metrics, at lest in some very basic way. */
1696 if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 4)
1698 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 2)
1700 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
1701 || DECL_DECLARED_INLINE_P (callee
->decl
))
1708 /* Return time bonus incurred because of HINTS. */
1711 hint_time_bonus (inline_hints hints
)
1714 if (hints
& (INLINE_HINT_loop_iterations
| INLINE_HINT_loop_stride
))
1715 result
+= PARAM_VALUE (PARAM_IPA_CP_LOOP_HINT_BONUS
);
1716 if (hints
& INLINE_HINT_array_index
)
1717 result
+= PARAM_VALUE (PARAM_IPA_CP_ARRAY_INDEX_HINT_BONUS
);
1721 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
1722 and SIZE_COST and with the sum of frequencies of incoming edges to the
1723 potential new clone in FREQUENCIES. */
1726 good_cloning_opportunity_p (struct cgraph_node
*node
, int time_benefit
,
1727 int freq_sum
, gcov_type count_sum
, int size_cost
)
1729 if (time_benefit
== 0
1730 || !flag_ipa_cp_clone
1731 || !optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node
->decl
)))
1734 gcc_assert (size_cost
> 0);
1738 int factor
= (count_sum
* 1000) / max_count
;
1739 HOST_WIDEST_INT evaluation
= (((HOST_WIDEST_INT
) time_benefit
* factor
)
1742 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1743 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
1744 "size: %i, count_sum: " HOST_WIDE_INT_PRINT_DEC
1745 ") -> evaluation: " HOST_WIDEST_INT_PRINT_DEC
1746 ", threshold: %i\n",
1747 time_benefit
, size_cost
, (HOST_WIDE_INT
) count_sum
,
1748 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
1750 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
1754 HOST_WIDEST_INT evaluation
= (((HOST_WIDEST_INT
) time_benefit
* freq_sum
)
1757 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1758 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
1759 "size: %i, freq_sum: %i) -> evaluation: "
1760 HOST_WIDEST_INT_PRINT_DEC
", threshold: %i\n",
1761 time_benefit
, size_cost
, freq_sum
, evaluation
,
1762 PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
1764 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
1768 /* Return all context independent values from aggregate lattices in PLATS in a
1769 vector. Return NULL if there are none. */
1771 static vec
<ipa_agg_jf_item
, va_gc
> *
1772 context_independent_aggregate_values (struct ipcp_param_lattices
*plats
)
1774 vec
<ipa_agg_jf_item
, va_gc
> *res
= NULL
;
1776 if (plats
->aggs_bottom
1777 || plats
->aggs_contain_variable
1778 || plats
->aggs_count
== 0)
1781 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
;
1783 aglat
= aglat
->next
)
1784 if (ipa_lat_is_single_const (aglat
))
1786 struct ipa_agg_jf_item item
;
1787 item
.offset
= aglat
->offset
;
1788 item
.value
= aglat
->values
->value
;
1789 vec_safe_push (res
, item
);
1794 /* Allocate KNOWN_CSTS, KNOWN_BINFOS and, if non-NULL, KNOWN_AGGS and populate
1795 them with values of parameters that are known independent of the context.
1796 INFO describes the function. If REMOVABLE_PARAMS_COST is non-NULL, the
1797 movement cost of all removable parameters will be stored in it. */
1800 gather_context_independent_values (struct ipa_node_params
*info
,
1801 vec
<tree
> *known_csts
,
1802 vec
<tree
> *known_binfos
,
1803 vec
<ipa_agg_jump_function
> *known_aggs
,
1804 int *removable_params_cost
)
1806 int i
, count
= ipa_get_param_count (info
);
1809 known_csts
->create (0);
1810 known_binfos
->create (0);
1811 known_csts
->safe_grow_cleared (count
);
1812 known_binfos
->safe_grow_cleared (count
);
1815 known_aggs
->create (0);
1816 known_aggs
->safe_grow_cleared (count
);
1819 if (removable_params_cost
)
1820 *removable_params_cost
= 0;
1822 for (i
= 0; i
< count
; i
++)
1824 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1825 struct ipcp_lattice
*lat
= &plats
->itself
;
1827 if (ipa_lat_is_single_const (lat
))
1829 struct ipcp_value
*val
= lat
->values
;
1830 if (TREE_CODE (val
->value
) != TREE_BINFO
)
1832 (*known_csts
)[i
] = val
->value
;
1833 if (removable_params_cost
)
1834 *removable_params_cost
1835 += estimate_move_cost (TREE_TYPE (val
->value
));
1838 else if (plats
->virt_call
)
1840 (*known_binfos
)[i
] = val
->value
;
1843 else if (removable_params_cost
1844 && !ipa_is_param_used (info
, i
))
1845 *removable_params_cost
+= ipa_get_param_move_cost (info
, i
);
1847 else if (removable_params_cost
1848 && !ipa_is_param_used (info
, i
))
1849 *removable_params_cost
1850 += ipa_get_param_move_cost (info
, i
);
1854 vec
<ipa_agg_jf_item
, va_gc
> *agg_items
;
1855 struct ipa_agg_jump_function
*ajf
;
1857 agg_items
= context_independent_aggregate_values (plats
);
1858 ajf
= &(*known_aggs
)[i
];
1859 ajf
->items
= agg_items
;
1860 ajf
->by_ref
= plats
->aggs_by_ref
;
1861 ret
|= agg_items
!= NULL
;
1868 /* The current interface in ipa-inline-analysis requires a pointer vector.
1871 FIXME: That interface should be re-worked, this is slightly silly. Still,
1872 I'd like to discuss how to change it first and this demonstrates the
1875 static vec
<ipa_agg_jump_function_p
>
1876 agg_jmp_p_vec_for_t_vec (vec
<ipa_agg_jump_function
> known_aggs
)
1878 vec
<ipa_agg_jump_function_p
> ret
;
1879 struct ipa_agg_jump_function
*ajf
;
1882 ret
.create (known_aggs
.length ());
1883 FOR_EACH_VEC_ELT (known_aggs
, i
, ajf
)
1884 ret
.quick_push (ajf
);
1888 /* Iterate over known values of parameters of NODE and estimate the local
1889 effects in terms of time and size they have. */
1892 estimate_local_effects (struct cgraph_node
*node
)
1894 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1895 int i
, count
= ipa_get_param_count (info
);
1896 vec
<tree
> known_csts
, known_binfos
;
1897 vec
<ipa_agg_jump_function
> known_aggs
;
1898 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
;
1900 int base_time
= inline_summary (node
)->time
;
1901 int removable_params_cost
;
1903 if (!count
|| !ipcp_versionable_function_p (node
))
1906 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1907 fprintf (dump_file
, "\nEstimating effects for %s/%i, base_time: %i.\n",
1908 node
->name (), node
->order
, base_time
);
1910 always_const
= gather_context_independent_values (info
, &known_csts
,
1911 &known_binfos
, &known_aggs
,
1912 &removable_params_cost
);
1913 known_aggs_ptrs
= agg_jmp_p_vec_for_t_vec (known_aggs
);
1916 struct caller_statistics stats
;
1920 init_caller_stats (&stats
);
1921 cgraph_for_node_and_aliases (node
, gather_caller_stats
, &stats
, false);
1922 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_binfos
,
1923 known_aggs_ptrs
, &size
, &time
, &hints
);
1924 time
-= devirtualization_time_bonus (node
, known_csts
, known_binfos
,
1926 time
-= hint_time_bonus (hints
);
1927 time
-= removable_params_cost
;
1928 size
-= stats
.n_calls
* removable_params_cost
;
1931 fprintf (dump_file
, " - context independent values, size: %i, "
1932 "time_benefit: %i\n", size
, base_time
- time
);
1935 || cgraph_will_be_removed_from_program_if_no_direct_calls (node
))
1937 info
->do_clone_for_all_contexts
= true;
1941 fprintf (dump_file
, " Decided to specialize for all "
1942 "known contexts, code not going to grow.\n");
1944 else if (good_cloning_opportunity_p (node
, base_time
- time
,
1945 stats
.freq_sum
, stats
.count_sum
,
1948 if (size
+ overall_size
<= max_new_size
)
1950 info
->do_clone_for_all_contexts
= true;
1952 overall_size
+= size
;
1955 fprintf (dump_file
, " Decided to specialize for all "
1956 "known contexts, growth deemed beneficial.\n");
1958 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1959 fprintf (dump_file
, " Not cloning for all contexts because "
1960 "max_new_size would be reached with %li.\n",
1961 size
+ overall_size
);
1965 for (i
= 0; i
< count
; i
++)
1967 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1968 struct ipcp_lattice
*lat
= &plats
->itself
;
1969 struct ipcp_value
*val
;
1978 for (val
= lat
->values
; val
; val
= val
->next
)
1980 int time
, size
, time_benefit
;
1983 if (TREE_CODE (val
->value
) != TREE_BINFO
)
1985 known_csts
[i
] = val
->value
;
1986 known_binfos
[i
] = NULL_TREE
;
1987 emc
= estimate_move_cost (TREE_TYPE (val
->value
));
1989 else if (plats
->virt_call
)
1991 known_csts
[i
] = NULL_TREE
;
1992 known_binfos
[i
] = val
->value
;
1998 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_binfos
,
1999 known_aggs_ptrs
, &size
, &time
,
2001 time_benefit
= base_time
- time
2002 + devirtualization_time_bonus (node
, known_csts
, known_binfos
,
2004 + hint_time_bonus (hints
)
2005 + removable_params_cost
+ emc
;
2007 gcc_checking_assert (size
>=0);
2008 /* The inliner-heuristics based estimates may think that in certain
2009 contexts some functions do not have any size at all but we want
2010 all specializations to have at least a tiny cost, not least not to
2015 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2017 fprintf (dump_file
, " - estimates for value ");
2018 print_ipcp_constant_value (dump_file
, val
->value
);
2019 fprintf (dump_file
, " for ");
2020 ipa_dump_param (dump_file
, info
, i
);
2021 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
2022 time_benefit
, size
);
2025 val
->local_time_benefit
= time_benefit
;
2026 val
->local_size_cost
= size
;
2028 known_binfos
[i
] = NULL_TREE
;
2029 known_csts
[i
] = NULL_TREE
;
2032 for (i
= 0; i
< count
; i
++)
2034 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2035 struct ipa_agg_jump_function
*ajf
;
2036 struct ipcp_agg_lattice
*aglat
;
2038 if (plats
->aggs_bottom
|| !plats
->aggs
)
2041 ajf
= &known_aggs
[i
];
2042 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2044 struct ipcp_value
*val
;
2045 if (aglat
->bottom
|| !aglat
->values
2046 /* If the following is true, the one value is in known_aggs. */
2047 || (!plats
->aggs_contain_variable
2048 && ipa_lat_is_single_const (aglat
)))
2051 for (val
= aglat
->values
; val
; val
= val
->next
)
2053 int time
, size
, time_benefit
;
2054 struct ipa_agg_jf_item item
;
2057 item
.offset
= aglat
->offset
;
2058 item
.value
= val
->value
;
2059 vec_safe_push (ajf
->items
, item
);
2061 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_binfos
,
2062 known_aggs_ptrs
, &size
, &time
,
2064 time_benefit
= base_time
- time
2065 + devirtualization_time_bonus (node
, known_csts
, known_binfos
,
2067 + hint_time_bonus (hints
);
2068 gcc_checking_assert (size
>=0);
2072 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2074 fprintf (dump_file
, " - estimates for value ");
2075 print_ipcp_constant_value (dump_file
, val
->value
);
2076 fprintf (dump_file
, " for ");
2077 ipa_dump_param (dump_file
, info
, i
);
2078 fprintf (dump_file
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
2079 "]: time_benefit: %i, size: %i\n",
2080 plats
->aggs_by_ref
? "ref " : "",
2081 aglat
->offset
, time_benefit
, size
);
2084 val
->local_time_benefit
= time_benefit
;
2085 val
->local_size_cost
= size
;
2091 for (i
= 0; i
< count
; i
++)
2092 vec_free (known_aggs
[i
].items
);
2094 known_csts
.release ();
2095 known_binfos
.release ();
2096 known_aggs
.release ();
2097 known_aggs_ptrs
.release ();
2101 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
2102 topological sort of values. */
2105 add_val_to_toposort (struct ipcp_value
*cur_val
)
2107 static int dfs_counter
= 0;
2108 static struct ipcp_value
*stack
;
2109 struct ipcp_value_source
*src
;
2115 cur_val
->dfs
= dfs_counter
;
2116 cur_val
->low_link
= dfs_counter
;
2118 cur_val
->topo_next
= stack
;
2120 cur_val
->on_stack
= true;
2122 for (src
= cur_val
->sources
; src
; src
= src
->next
)
2125 if (src
->val
->dfs
== 0)
2127 add_val_to_toposort (src
->val
);
2128 if (src
->val
->low_link
< cur_val
->low_link
)
2129 cur_val
->low_link
= src
->val
->low_link
;
2131 else if (src
->val
->on_stack
2132 && src
->val
->dfs
< cur_val
->low_link
)
2133 cur_val
->low_link
= src
->val
->dfs
;
2136 if (cur_val
->dfs
== cur_val
->low_link
)
2138 struct ipcp_value
*v
, *scc_list
= NULL
;
2143 stack
= v
->topo_next
;
2144 v
->on_stack
= false;
2146 v
->scc_next
= scc_list
;
2149 while (v
!= cur_val
);
2151 cur_val
->topo_next
= values_topo
;
2152 values_topo
= cur_val
;
2156 /* Add all values in lattices associated with NODE to the topological sort if
2157 they are not there yet. */
2160 add_all_node_vals_to_toposort (struct cgraph_node
*node
)
2162 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2163 int i
, count
= ipa_get_param_count (info
);
2165 for (i
= 0; i
< count
; i
++)
2167 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2168 struct ipcp_lattice
*lat
= &plats
->itself
;
2169 struct ipcp_agg_lattice
*aglat
;
2170 struct ipcp_value
*val
;
2173 for (val
= lat
->values
; val
; val
= val
->next
)
2174 add_val_to_toposort (val
);
2176 if (!plats
->aggs_bottom
)
2177 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2179 for (val
= aglat
->values
; val
; val
= val
->next
)
2180 add_val_to_toposort (val
);
2184 /* One pass of constants propagation along the call graph edges, from callers
2185 to callees (requires topological ordering in TOPO), iterate over strongly
2186 connected components. */
2189 propagate_constants_topo (struct topo_info
*topo
)
2193 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
2196 struct cgraph_node
*v
, *node
= topo
->order
[i
];
2197 vec
<cgraph_node_ptr
> cycle_nodes
= ipa_get_nodes_in_cycle (node
);
2199 /* First, iteratively propagate within the strongly connected component
2200 until all lattices stabilize. */
2201 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
2202 if (cgraph_function_with_gimple_body_p (v
))
2203 push_node_to_stack (topo
, v
);
2205 v
= pop_node_from_stack (topo
);
2208 struct cgraph_edge
*cs
;
2210 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
2211 if (ipa_edge_within_scc (cs
)
2212 && propagate_constants_accross_call (cs
))
2213 push_node_to_stack (topo
, cs
->callee
);
2214 v
= pop_node_from_stack (topo
);
2217 /* Afterwards, propagate along edges leading out of the SCC, calculates
2218 the local effects of the discovered constants and all valid values to
2219 their topological sort. */
2220 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
2221 if (cgraph_function_with_gimple_body_p (v
))
2223 struct cgraph_edge
*cs
;
2225 estimate_local_effects (v
);
2226 add_all_node_vals_to_toposort (v
);
2227 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
2228 if (!ipa_edge_within_scc (cs
))
2229 propagate_constants_accross_call (cs
);
2231 cycle_nodes
.release ();
2236 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
2237 the bigger one if otherwise. */
2240 safe_add (int a
, int b
)
2242 if (a
> INT_MAX
/2 || b
> INT_MAX
/2)
2243 return a
> b
? a
: b
;
2249 /* Propagate the estimated effects of individual values along the topological
2250 from the dependent values to those they depend on. */
2253 propagate_effects (void)
2255 struct ipcp_value
*base
;
2257 for (base
= values_topo
; base
; base
= base
->topo_next
)
2259 struct ipcp_value_source
*src
;
2260 struct ipcp_value
*val
;
2261 int time
= 0, size
= 0;
2263 for (val
= base
; val
; val
= val
->scc_next
)
2265 time
= safe_add (time
,
2266 val
->local_time_benefit
+ val
->prop_time_benefit
);
2267 size
= safe_add (size
, val
->local_size_cost
+ val
->prop_size_cost
);
2270 for (val
= base
; val
; val
= val
->scc_next
)
2271 for (src
= val
->sources
; src
; src
= src
->next
)
2273 && cgraph_maybe_hot_edge_p (src
->cs
))
2275 src
->val
->prop_time_benefit
= safe_add (time
,
2276 src
->val
->prop_time_benefit
);
2277 src
->val
->prop_size_cost
= safe_add (size
,
2278 src
->val
->prop_size_cost
);
2284 /* Propagate constants, binfos and their effects from the summaries
2285 interprocedurally. */
2288 ipcp_propagate_stage (struct topo_info
*topo
)
2290 struct cgraph_node
*node
;
2293 fprintf (dump_file
, "\n Propagating constants:\n\n");
2296 ipa_update_after_lto_read ();
2299 FOR_EACH_DEFINED_FUNCTION (node
)
2301 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2303 determine_versionability (node
);
2304 if (cgraph_function_with_gimple_body_p (node
))
2306 info
->lattices
= XCNEWVEC (struct ipcp_param_lattices
,
2307 ipa_get_param_count (info
));
2308 initialize_node_lattices (node
);
2310 if (node
->definition
&& !node
->alias
)
2311 overall_size
+= inline_summary (node
)->self_size
;
2312 if (node
->count
> max_count
)
2313 max_count
= node
->count
;
2316 max_new_size
= overall_size
;
2317 if (max_new_size
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
2318 max_new_size
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
2319 max_new_size
+= max_new_size
* PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH
) / 100 + 1;
2322 fprintf (dump_file
, "\noverall_size: %li, max_new_size: %li\n",
2323 overall_size
, max_new_size
);
2325 propagate_constants_topo (topo
);
2326 #ifdef ENABLE_CHECKING
2327 ipcp_verify_propagated_values ();
2329 propagate_effects ();
2333 fprintf (dump_file
, "\nIPA lattices after all propagation:\n");
2334 print_all_lattices (dump_file
, (dump_flags
& TDF_DETAILS
), true);
2338 /* Discover newly direct outgoing edges from NODE which is a new clone with
2339 known KNOWN_VALS and make them direct. */
2342 ipcp_discover_new_direct_edges (struct cgraph_node
*node
,
2343 vec
<tree
> known_vals
,
2344 struct ipa_agg_replacement_value
*aggvals
)
2346 struct cgraph_edge
*ie
, *next_ie
;
2349 for (ie
= node
->indirect_calls
; ie
; ie
= next_ie
)
2353 next_ie
= ie
->next_callee
;
2354 target
= ipa_get_indirect_edge_target_1 (ie
, known_vals
, vNULL
, vNULL
,
2358 bool agg_contents
= ie
->indirect_info
->agg_contents
;
2359 bool polymorphic
= ie
->indirect_info
->polymorphic
;
2360 int param_index
= ie
->indirect_info
->param_index
;
2361 struct cgraph_edge
*cs
= ipa_make_edge_direct_to_target (ie
, target
);
2364 if (cs
&& !agg_contents
&& !polymorphic
)
2366 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2367 int c
= ipa_get_controlled_uses (info
, param_index
);
2368 if (c
!= IPA_UNDESCRIBED_USE
)
2370 struct ipa_ref
*to_del
;
2373 ipa_set_controlled_uses (info
, param_index
, c
);
2374 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2375 fprintf (dump_file
, " controlled uses count of param "
2376 "%i bumped down to %i\n", param_index
, c
);
2378 && (to_del
= ipa_find_reference (node
,
2382 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2383 fprintf (dump_file
, " and even removing its "
2384 "cloning-created reference\n");
2385 ipa_remove_reference (to_del
);
2391 /* Turning calls to direct calls will improve overall summary. */
2393 inline_update_overall_summary (node
);
2396 /* Vector of pointers which for linked lists of clones of an original crgaph
2399 static vec
<cgraph_edge_p
> next_edge_clone
;
2400 static vec
<cgraph_edge_p
> prev_edge_clone
;
2403 grow_edge_clone_vectors (void)
2405 if (next_edge_clone
.length ()
2406 <= (unsigned) cgraph_edge_max_uid
)
2407 next_edge_clone
.safe_grow_cleared (cgraph_edge_max_uid
+ 1);
2408 if (prev_edge_clone
.length ()
2409 <= (unsigned) cgraph_edge_max_uid
)
2410 prev_edge_clone
.safe_grow_cleared (cgraph_edge_max_uid
+ 1);
2413 /* Edge duplication hook to grow the appropriate linked list in
2417 ipcp_edge_duplication_hook (struct cgraph_edge
*src
, struct cgraph_edge
*dst
,
2420 grow_edge_clone_vectors ();
2422 struct cgraph_edge
*old_next
= next_edge_clone
[src
->uid
];
2424 prev_edge_clone
[old_next
->uid
] = dst
;
2425 prev_edge_clone
[dst
->uid
] = src
;
2427 next_edge_clone
[dst
->uid
] = old_next
;
2428 next_edge_clone
[src
->uid
] = dst
;
2431 /* Hook that is called by cgraph.c when an edge is removed. */
2434 ipcp_edge_removal_hook (struct cgraph_edge
*cs
, void *)
2436 grow_edge_clone_vectors ();
2438 struct cgraph_edge
*prev
= prev_edge_clone
[cs
->uid
];
2439 struct cgraph_edge
*next
= next_edge_clone
[cs
->uid
];
2441 next_edge_clone
[prev
->uid
] = next
;
2443 prev_edge_clone
[next
->uid
] = prev
;
2446 /* See if NODE is a clone with a known aggregate value at a given OFFSET of a
2447 parameter with the given INDEX. */
2450 get_clone_agg_value (struct cgraph_node
*node
, HOST_WIDEST_INT offset
,
2453 struct ipa_agg_replacement_value
*aggval
;
2455 aggval
= ipa_get_agg_replacements_for_node (node
);
2458 if (aggval
->offset
== offset
2459 && aggval
->index
== index
)
2460 return aggval
->value
;
2461 aggval
= aggval
->next
;
2466 /* Return true if edge CS does bring about the value described by SRC. */
2469 cgraph_edge_brings_value_p (struct cgraph_edge
*cs
,
2470 struct ipcp_value_source
*src
)
2472 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2473 struct ipa_node_params
*dst_info
= IPA_NODE_REF (cs
->callee
);
2475 if ((dst_info
->ipcp_orig_node
&& !dst_info
->is_all_contexts_clone
)
2476 || caller_info
->node_dead
)
2481 if (caller_info
->ipcp_orig_node
)
2484 if (src
->offset
== -1)
2485 t
= caller_info
->known_vals
[src
->index
];
2487 t
= get_clone_agg_value (cs
->caller
, src
->offset
, src
->index
);
2488 return (t
!= NULL_TREE
2489 && values_equal_for_ipcp_p (src
->val
->value
, t
));
2493 struct ipcp_agg_lattice
*aglat
;
2494 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
2496 if (src
->offset
== -1)
2497 return (ipa_lat_is_single_const (&plats
->itself
)
2498 && values_equal_for_ipcp_p (src
->val
->value
,
2499 plats
->itself
.values
->value
));
2502 if (plats
->aggs_bottom
|| plats
->aggs_contain_variable
)
2504 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2505 if (aglat
->offset
== src
->offset
)
2506 return (ipa_lat_is_single_const (aglat
)
2507 && values_equal_for_ipcp_p (src
->val
->value
,
2508 aglat
->values
->value
));
2514 /* Get the next clone in the linked list of clones of an edge. */
2516 static inline struct cgraph_edge
*
2517 get_next_cgraph_edge_clone (struct cgraph_edge
*cs
)
2519 return next_edge_clone
[cs
->uid
];
2522 /* Given VAL, iterate over all its sources and if they still hold, add their
2523 edge frequency and their number into *FREQUENCY and *CALLER_COUNT
2527 get_info_about_necessary_edges (struct ipcp_value
*val
, int *freq_sum
,
2528 gcov_type
*count_sum
, int *caller_count
)
2530 struct ipcp_value_source
*src
;
2531 int freq
= 0, count
= 0;
2535 for (src
= val
->sources
; src
; src
= src
->next
)
2537 struct cgraph_edge
*cs
= src
->cs
;
2540 if (cgraph_edge_brings_value_p (cs
, src
))
2543 freq
+= cs
->frequency
;
2545 hot
|= cgraph_maybe_hot_edge_p (cs
);
2547 cs
= get_next_cgraph_edge_clone (cs
);
2553 *caller_count
= count
;
2557 /* Return a vector of incoming edges that do bring value VAL. It is assumed
2558 their number is known and equal to CALLER_COUNT. */
2560 static vec
<cgraph_edge_p
>
2561 gather_edges_for_value (struct ipcp_value
*val
, int caller_count
)
2563 struct ipcp_value_source
*src
;
2564 vec
<cgraph_edge_p
> ret
;
2566 ret
.create (caller_count
);
2567 for (src
= val
->sources
; src
; src
= src
->next
)
2569 struct cgraph_edge
*cs
= src
->cs
;
2572 if (cgraph_edge_brings_value_p (cs
, src
))
2573 ret
.quick_push (cs
);
2574 cs
= get_next_cgraph_edge_clone (cs
);
2581 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
2582 Return it or NULL if for some reason it cannot be created. */
2584 static struct ipa_replace_map
*
2585 get_replacement_map (struct ipa_node_params
*info
, tree value
, int parm_num
)
2587 struct ipa_replace_map
*replace_map
;
2590 replace_map
= ggc_alloc_ipa_replace_map ();
2593 fprintf (dump_file
, " replacing ");
2594 ipa_dump_param (dump_file
, info
, parm_num
);
2596 fprintf (dump_file
, " with const ");
2597 print_generic_expr (dump_file
, value
, 0);
2598 fprintf (dump_file
, "\n");
2600 replace_map
->old_tree
= NULL
;
2601 replace_map
->parm_num
= parm_num
;
2602 replace_map
->new_tree
= value
;
2603 replace_map
->replace_p
= true;
2604 replace_map
->ref_p
= false;
2609 /* Dump new profiling counts */
2612 dump_profile_updates (struct cgraph_node
*orig_node
,
2613 struct cgraph_node
*new_node
)
2615 struct cgraph_edge
*cs
;
2617 fprintf (dump_file
, " setting count of the specialized node to "
2618 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) new_node
->count
);
2619 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
2620 fprintf (dump_file
, " edge to %s has count "
2621 HOST_WIDE_INT_PRINT_DEC
"\n",
2622 cs
->callee
->name (), (HOST_WIDE_INT
) cs
->count
);
2624 fprintf (dump_file
, " setting count of the original node to "
2625 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) orig_node
->count
);
2626 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
2627 fprintf (dump_file
, " edge to %s is left with "
2628 HOST_WIDE_INT_PRINT_DEC
"\n",
2629 cs
->callee
->name (), (HOST_WIDE_INT
) cs
->count
);
2632 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
2633 their profile information to reflect this. */
2636 update_profiling_info (struct cgraph_node
*orig_node
,
2637 struct cgraph_node
*new_node
)
2639 struct cgraph_edge
*cs
;
2640 struct caller_statistics stats
;
2641 gcov_type new_sum
, orig_sum
;
2642 gcov_type remainder
, orig_node_count
= orig_node
->count
;
2644 if (orig_node_count
== 0)
2647 init_caller_stats (&stats
);
2648 cgraph_for_node_and_aliases (orig_node
, gather_caller_stats
, &stats
, false);
2649 orig_sum
= stats
.count_sum
;
2650 init_caller_stats (&stats
);
2651 cgraph_for_node_and_aliases (new_node
, gather_caller_stats
, &stats
, false);
2652 new_sum
= stats
.count_sum
;
2654 if (orig_node_count
< orig_sum
+ new_sum
)
2657 fprintf (dump_file
, " Problem: node %s/%i has too low count "
2658 HOST_WIDE_INT_PRINT_DEC
" while the sum of incoming "
2659 "counts is " HOST_WIDE_INT_PRINT_DEC
"\n",
2660 orig_node
->name (), orig_node
->order
,
2661 (HOST_WIDE_INT
) orig_node_count
,
2662 (HOST_WIDE_INT
) (orig_sum
+ new_sum
));
2664 orig_node_count
= (orig_sum
+ new_sum
) * 12 / 10;
2666 fprintf (dump_file
, " proceeding by pretending it was "
2667 HOST_WIDE_INT_PRINT_DEC
"\n",
2668 (HOST_WIDE_INT
) orig_node_count
);
2671 new_node
->count
= new_sum
;
2672 remainder
= orig_node_count
- new_sum
;
2673 orig_node
->count
= remainder
;
2675 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
2677 cs
->count
= apply_probability (cs
->count
,
2678 GCOV_COMPUTE_SCALE (new_sum
,
2683 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
2684 cs
->count
= apply_probability (cs
->count
,
2685 GCOV_COMPUTE_SCALE (remainder
,
2689 dump_profile_updates (orig_node
, new_node
);
2692 /* Update the respective profile of specialized NEW_NODE and the original
2693 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
2694 have been redirected to the specialized version. */
2697 update_specialized_profile (struct cgraph_node
*new_node
,
2698 struct cgraph_node
*orig_node
,
2699 gcov_type redirected_sum
)
2701 struct cgraph_edge
*cs
;
2702 gcov_type new_node_count
, orig_node_count
= orig_node
->count
;
2705 fprintf (dump_file
, " the sum of counts of redirected edges is "
2706 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) redirected_sum
);
2707 if (orig_node_count
== 0)
2710 gcc_assert (orig_node_count
>= redirected_sum
);
2712 new_node_count
= new_node
->count
;
2713 new_node
->count
+= redirected_sum
;
2714 orig_node
->count
-= redirected_sum
;
2716 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
2718 cs
->count
+= apply_probability (cs
->count
,
2719 GCOV_COMPUTE_SCALE (redirected_sum
,
2724 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
2726 gcov_type dec
= apply_probability (cs
->count
,
2727 GCOV_COMPUTE_SCALE (redirected_sum
,
2729 if (dec
< cs
->count
)
2736 dump_profile_updates (orig_node
, new_node
);
2739 /* Create a specialized version of NODE with known constants and types of
2740 parameters in KNOWN_VALS and redirect all edges in CALLERS to it. */
2742 static struct cgraph_node
*
2743 create_specialized_node (struct cgraph_node
*node
,
2744 vec
<tree
> known_vals
,
2745 struct ipa_agg_replacement_value
*aggvals
,
2746 vec
<cgraph_edge_p
> callers
)
2748 struct ipa_node_params
*new_info
, *info
= IPA_NODE_REF (node
);
2749 vec
<ipa_replace_map_p
, va_gc
> *replace_trees
= NULL
;
2750 struct ipa_agg_replacement_value
*av
;
2751 struct cgraph_node
*new_node
;
2752 int i
, count
= ipa_get_param_count (info
);
2753 bitmap args_to_skip
;
2755 gcc_assert (!info
->ipcp_orig_node
);
2757 if (node
->local
.can_change_signature
)
2759 args_to_skip
= BITMAP_GGC_ALLOC ();
2760 for (i
= 0; i
< count
; i
++)
2762 tree t
= known_vals
[i
];
2764 if ((t
&& TREE_CODE (t
) != TREE_BINFO
)
2765 || !ipa_is_param_used (info
, i
))
2766 bitmap_set_bit (args_to_skip
, i
);
2771 args_to_skip
= NULL
;
2772 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2773 fprintf (dump_file
, " cannot change function signature\n");
2776 for (i
= 0; i
< count
; i
++)
2778 tree t
= known_vals
[i
];
2779 if (t
&& TREE_CODE (t
) != TREE_BINFO
)
2781 struct ipa_replace_map
*replace_map
;
2783 replace_map
= get_replacement_map (info
, t
, i
);
2785 vec_safe_push (replace_trees
, replace_map
);
2789 new_node
= cgraph_create_virtual_clone (node
, callers
, replace_trees
,
2790 args_to_skip
, "constprop");
2791 ipa_set_node_agg_value_chain (new_node
, aggvals
);
2792 for (av
= aggvals
; av
; av
= av
->next
)
2793 ipa_maybe_record_reference (new_node
, av
->value
,
2794 IPA_REF_ADDR
, NULL
);
2796 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2798 fprintf (dump_file
, " the new node is %s/%i.\n",
2799 new_node
->name (), new_node
->order
);
2801 ipa_dump_agg_replacement_values (dump_file
, aggvals
);
2803 gcc_checking_assert (ipa_node_params_vector
.exists ()
2804 && (ipa_node_params_vector
.length ()
2805 > (unsigned) cgraph_max_uid
));
2806 update_profiling_info (node
, new_node
);
2807 new_info
= IPA_NODE_REF (new_node
);
2808 new_info
->ipcp_orig_node
= node
;
2809 new_info
->known_vals
= known_vals
;
2811 ipcp_discover_new_direct_edges (new_node
, known_vals
, aggvals
);
2817 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
2818 KNOWN_VALS with constants and types that are also known for all of the
2822 find_more_scalar_values_for_callers_subset (struct cgraph_node
*node
,
2823 vec
<tree
> known_vals
,
2824 vec
<cgraph_edge_p
> callers
)
2826 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2827 int i
, count
= ipa_get_param_count (info
);
2829 for (i
= 0; i
< count
; i
++)
2831 struct cgraph_edge
*cs
;
2832 tree newval
= NULL_TREE
;
2835 if (ipa_get_scalar_lat (info
, i
)->bottom
|| known_vals
[i
])
2838 FOR_EACH_VEC_ELT (callers
, j
, cs
)
2840 struct ipa_jump_func
*jump_func
;
2843 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
)))
2848 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
2849 t
= ipa_value_from_jfunc (IPA_NODE_REF (cs
->caller
), jump_func
);
2852 && !values_equal_for_ipcp_p (t
, newval
)))
2863 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2865 fprintf (dump_file
, " adding an extra known scalar value ");
2866 print_ipcp_constant_value (dump_file
, newval
);
2867 fprintf (dump_file
, " for ");
2868 ipa_dump_param (dump_file
, info
, i
);
2869 fprintf (dump_file
, "\n");
2872 known_vals
[i
] = newval
;
2877 /* Go through PLATS and create a vector of values consisting of values and
2878 offsets (minus OFFSET) of lattices that contain only a single value. */
2880 static vec
<ipa_agg_jf_item
>
2881 copy_plats_to_inter (struct ipcp_param_lattices
*plats
, HOST_WIDE_INT offset
)
2883 vec
<ipa_agg_jf_item
> res
= vNULL
;
2885 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
2888 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2889 if (ipa_lat_is_single_const (aglat
))
2891 struct ipa_agg_jf_item ti
;
2892 ti
.offset
= aglat
->offset
- offset
;
2893 ti
.value
= aglat
->values
->value
;
2899 /* Intersect all values in INTER with single value lattices in PLATS (while
2900 subtracting OFFSET). */
2903 intersect_with_plats (struct ipcp_param_lattices
*plats
,
2904 vec
<ipa_agg_jf_item
> *inter
,
2905 HOST_WIDE_INT offset
)
2907 struct ipcp_agg_lattice
*aglat
;
2908 struct ipa_agg_jf_item
*item
;
2911 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
2917 aglat
= plats
->aggs
;
2918 FOR_EACH_VEC_ELT (*inter
, k
, item
)
2925 if (aglat
->offset
- offset
> item
->offset
)
2927 if (aglat
->offset
- offset
== item
->offset
)
2929 gcc_checking_assert (item
->value
);
2930 if (values_equal_for_ipcp_p (item
->value
, aglat
->values
->value
))
2934 aglat
= aglat
->next
;
2937 item
->value
= NULL_TREE
;
2941 /* Copy agggregate replacement values of NODE (which is an IPA-CP clone) to the
2942 vector result while subtracting OFFSET from the individual value offsets. */
2944 static vec
<ipa_agg_jf_item
>
2945 agg_replacements_to_vector (struct cgraph_node
*node
, int index
,
2946 HOST_WIDE_INT offset
)
2948 struct ipa_agg_replacement_value
*av
;
2949 vec
<ipa_agg_jf_item
> res
= vNULL
;
2951 for (av
= ipa_get_agg_replacements_for_node (node
); av
; av
= av
->next
)
2952 if (av
->index
== index
2953 && (av
->offset
- offset
) >= 0)
2955 struct ipa_agg_jf_item item
;
2956 gcc_checking_assert (av
->value
);
2957 item
.offset
= av
->offset
- offset
;
2958 item
.value
= av
->value
;
2959 res
.safe_push (item
);
2965 /* Intersect all values in INTER with those that we have already scheduled to
2966 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
2967 (while subtracting OFFSET). */
2970 intersect_with_agg_replacements (struct cgraph_node
*node
, int index
,
2971 vec
<ipa_agg_jf_item
> *inter
,
2972 HOST_WIDE_INT offset
)
2974 struct ipa_agg_replacement_value
*srcvals
;
2975 struct ipa_agg_jf_item
*item
;
2978 srcvals
= ipa_get_agg_replacements_for_node (node
);
2985 FOR_EACH_VEC_ELT (*inter
, i
, item
)
2987 struct ipa_agg_replacement_value
*av
;
2991 for (av
= srcvals
; av
; av
= av
->next
)
2993 gcc_checking_assert (av
->value
);
2994 if (av
->index
== index
2995 && av
->offset
- offset
== item
->offset
)
2997 if (values_equal_for_ipcp_p (item
->value
, av
->value
))
3003 item
->value
= NULL_TREE
;
3007 /* Intersect values in INTER with aggregate values that come along edge CS to
3008 parameter number INDEX and return it. If INTER does not actually exist yet,
3009 copy all incoming values to it. If we determine we ended up with no values
3010 whatsoever, return a released vector. */
3012 static vec
<ipa_agg_jf_item
>
3013 intersect_aggregates_with_edge (struct cgraph_edge
*cs
, int index
,
3014 vec
<ipa_agg_jf_item
> inter
)
3016 struct ipa_jump_func
*jfunc
;
3017 jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), index
);
3018 if (jfunc
->type
== IPA_JF_PASS_THROUGH
3019 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
3021 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3022 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
3024 if (caller_info
->ipcp_orig_node
)
3026 struct cgraph_node
*orig_node
= caller_info
->ipcp_orig_node
;
3027 struct ipcp_param_lattices
*orig_plats
;
3028 orig_plats
= ipa_get_parm_lattices (IPA_NODE_REF (orig_node
),
3030 if (agg_pass_through_permissible_p (orig_plats
, jfunc
))
3032 if (!inter
.exists ())
3033 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, 0);
3035 intersect_with_agg_replacements (cs
->caller
, src_idx
,
3041 struct ipcp_param_lattices
*src_plats
;
3042 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
3043 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
3045 /* Currently we do not produce clobber aggregate jump
3046 functions, adjust when we do. */
3047 gcc_checking_assert (!jfunc
->agg
.items
);
3048 if (!inter
.exists ())
3049 inter
= copy_plats_to_inter (src_plats
, 0);
3051 intersect_with_plats (src_plats
, &inter
, 0);
3055 else if (jfunc
->type
== IPA_JF_ANCESTOR
3056 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
3058 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3059 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
3060 struct ipcp_param_lattices
*src_plats
;
3061 HOST_WIDE_INT delta
= ipa_get_jf_ancestor_offset (jfunc
);
3063 if (caller_info
->ipcp_orig_node
)
3065 if (!inter
.exists ())
3066 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, delta
);
3068 intersect_with_agg_replacements (cs
->caller
, src_idx
, &inter
,
3073 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);;
3074 /* Currently we do not produce clobber aggregate jump
3075 functions, adjust when we do. */
3076 gcc_checking_assert (!src_plats
->aggs
|| !jfunc
->agg
.items
);
3077 if (!inter
.exists ())
3078 inter
= copy_plats_to_inter (src_plats
, delta
);
3080 intersect_with_plats (src_plats
, &inter
, delta
);
3083 else if (jfunc
->agg
.items
)
3085 struct ipa_agg_jf_item
*item
;
3088 if (!inter
.exists ())
3089 for (unsigned i
= 0; i
< jfunc
->agg
.items
->length (); i
++)
3090 inter
.safe_push ((*jfunc
->agg
.items
)[i
]);
3092 FOR_EACH_VEC_ELT (inter
, k
, item
)
3095 bool found
= false;;
3100 while ((unsigned) l
< jfunc
->agg
.items
->length ())
3102 struct ipa_agg_jf_item
*ti
;
3103 ti
= &(*jfunc
->agg
.items
)[l
];
3104 if (ti
->offset
> item
->offset
)
3106 if (ti
->offset
== item
->offset
)
3108 gcc_checking_assert (ti
->value
);
3109 if (values_equal_for_ipcp_p (item
->value
,
3123 return vec
<ipa_agg_jf_item
>();
3128 /* Look at edges in CALLERS and collect all known aggregate values that arrive
3129 from all of them. */
3131 static struct ipa_agg_replacement_value
*
3132 find_aggregate_values_for_callers_subset (struct cgraph_node
*node
,
3133 vec
<cgraph_edge_p
> callers
)
3135 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
3136 struct ipa_agg_replacement_value
*res
= NULL
;
3137 struct cgraph_edge
*cs
;
3138 int i
, j
, count
= ipa_get_param_count (dest_info
);
3140 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3142 int c
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
3147 for (i
= 0; i
< count
; i
++)
3149 struct cgraph_edge
*cs
;
3150 vec
<ipa_agg_jf_item
> inter
= vNULL
;
3151 struct ipa_agg_jf_item
*item
;
3152 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (dest_info
, i
);
3155 /* Among other things, the following check should deal with all by_ref
3157 if (plats
->aggs_bottom
)
3160 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3162 inter
= intersect_aggregates_with_edge (cs
, i
, inter
);
3164 if (!inter
.exists ())
3168 FOR_EACH_VEC_ELT (inter
, j
, item
)
3170 struct ipa_agg_replacement_value
*v
;
3175 v
= ggc_alloc_ipa_agg_replacement_value ();
3177 v
->offset
= item
->offset
;
3178 v
->value
= item
->value
;
3179 v
->by_ref
= plats
->aggs_by_ref
;
3185 if (inter
.exists ())
3191 /* Turn KNOWN_AGGS into a list of aggreate replacement values. */
3193 static struct ipa_agg_replacement_value
*
3194 known_aggs_to_agg_replacement_list (vec
<ipa_agg_jump_function
> known_aggs
)
3196 struct ipa_agg_replacement_value
*res
= NULL
;
3197 struct ipa_agg_jump_function
*aggjf
;
3198 struct ipa_agg_jf_item
*item
;
3201 FOR_EACH_VEC_ELT (known_aggs
, i
, aggjf
)
3202 FOR_EACH_VEC_SAFE_ELT (aggjf
->items
, j
, item
)
3204 struct ipa_agg_replacement_value
*v
;
3205 v
= ggc_alloc_ipa_agg_replacement_value ();
3207 v
->offset
= item
->offset
;
3208 v
->value
= item
->value
;
3209 v
->by_ref
= aggjf
->by_ref
;
3216 /* Determine whether CS also brings all scalar values that the NODE is
3220 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge
*cs
,
3221 struct cgraph_node
*node
)
3223 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
3224 int count
= ipa_get_param_count (dest_info
);
3225 struct ipa_node_params
*caller_info
;
3226 struct ipa_edge_args
*args
;
3229 caller_info
= IPA_NODE_REF (cs
->caller
);
3230 args
= IPA_EDGE_REF (cs
);
3231 for (i
= 0; i
< count
; i
++)
3233 struct ipa_jump_func
*jump_func
;
3236 val
= dest_info
->known_vals
[i
];
3240 if (i
>= ipa_get_cs_argument_count (args
))
3242 jump_func
= ipa_get_ith_jump_func (args
, i
);
3243 t
= ipa_value_from_jfunc (caller_info
, jump_func
);
3244 if (!t
|| !values_equal_for_ipcp_p (val
, t
))
3250 /* Determine whether CS also brings all aggregate values that NODE is
3253 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge
*cs
,
3254 struct cgraph_node
*node
)
3256 struct ipa_node_params
*orig_caller_info
= IPA_NODE_REF (cs
->caller
);
3257 struct ipa_agg_replacement_value
*aggval
;
3260 aggval
= ipa_get_agg_replacements_for_node (node
);
3264 count
= ipa_get_param_count (IPA_NODE_REF (node
));
3265 ec
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
3267 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
3268 if (aggval
->index
>= ec
)
3271 if (orig_caller_info
->ipcp_orig_node
)
3272 orig_caller_info
= IPA_NODE_REF (orig_caller_info
->ipcp_orig_node
);
3274 for (i
= 0; i
< count
; i
++)
3276 static vec
<ipa_agg_jf_item
> values
= vec
<ipa_agg_jf_item
>();
3277 struct ipcp_param_lattices
*plats
;
3278 bool interesting
= false;
3279 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
3280 if (aggval
->index
== i
)
3288 plats
= ipa_get_parm_lattices (orig_caller_info
, aggval
->index
);
3289 if (plats
->aggs_bottom
)
3292 values
= intersect_aggregates_with_edge (cs
, i
, values
);
3293 if (!values
.exists ())
3296 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
3297 if (aggval
->index
== i
)
3299 struct ipa_agg_jf_item
*item
;
3302 FOR_EACH_VEC_ELT (values
, j
, item
)
3304 && item
->offset
== av
->offset
3305 && values_equal_for_ipcp_p (item
->value
, av
->value
))
3320 /* Given an original NODE and a VAL for which we have already created a
3321 specialized clone, look whether there are incoming edges that still lead
3322 into the old node but now also bring the requested value and also conform to
3323 all other criteria such that they can be redirected the the special node.
3324 This function can therefore redirect the final edge in a SCC. */
3327 perhaps_add_new_callers (struct cgraph_node
*node
, struct ipcp_value
*val
)
3329 struct ipcp_value_source
*src
;
3330 gcov_type redirected_sum
= 0;
3332 for (src
= val
->sources
; src
; src
= src
->next
)
3334 struct cgraph_edge
*cs
= src
->cs
;
3337 enum availability availability
;
3338 struct cgraph_node
*dst
= cgraph_function_node (cs
->callee
,
3340 if ((dst
== node
|| IPA_NODE_REF (dst
)->is_all_contexts_clone
)
3341 && availability
> AVAIL_OVERWRITABLE
3342 && cgraph_edge_brings_value_p (cs
, src
))
3344 if (cgraph_edge_brings_all_scalars_for_node (cs
, val
->spec_node
)
3345 && cgraph_edge_brings_all_agg_vals_for_node (cs
,
3349 fprintf (dump_file
, " - adding an extra caller %s/%i"
3351 xstrdup (cs
->caller
->name ()),
3353 xstrdup (val
->spec_node
->name ()),
3354 val
->spec_node
->order
);
3356 cgraph_redirect_edge_callee (cs
, val
->spec_node
);
3357 redirected_sum
+= cs
->count
;
3360 cs
= get_next_cgraph_edge_clone (cs
);
3365 update_specialized_profile (val
->spec_node
, node
, redirected_sum
);
3369 /* Copy KNOWN_BINFOS to KNOWN_VALS. */
3372 move_binfos_to_values (vec
<tree
> known_vals
,
3373 vec
<tree
> known_binfos
)
3378 for (i
= 0; known_binfos
.iterate (i
, &t
); i
++)
3383 /* Return true if there is a replacement equivalent to VALUE, INDEX and OFFSET
3384 among those in the AGGVALS list. */
3387 ipcp_val_in_agg_replacements_p (struct ipa_agg_replacement_value
*aggvals
,
3388 int index
, HOST_WIDE_INT offset
, tree value
)
3392 if (aggvals
->index
== index
3393 && aggvals
->offset
== offset
3394 && values_equal_for_ipcp_p (aggvals
->value
, value
))
3396 aggvals
= aggvals
->next
;
3401 /* Decide wheter to create a special version of NODE for value VAL of parameter
3402 at the given INDEX. If OFFSET is -1, the value is for the parameter itself,
3403 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS,
3404 KNOWN_BINFOS and KNOWN_AGGS describe the other already known values. */
3407 decide_about_value (struct cgraph_node
*node
, int index
, HOST_WIDE_INT offset
,
3408 struct ipcp_value
*val
, vec
<tree
> known_csts
,
3409 vec
<tree
> known_binfos
)
3411 struct ipa_agg_replacement_value
*aggvals
;
3412 int freq_sum
, caller_count
;
3413 gcov_type count_sum
;
3414 vec
<cgraph_edge_p
> callers
;
3419 perhaps_add_new_callers (node
, val
);
3422 else if (val
->local_size_cost
+ overall_size
> max_new_size
)
3424 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3425 fprintf (dump_file
, " Ignoring candidate value because "
3426 "max_new_size would be reached with %li.\n",
3427 val
->local_size_cost
+ overall_size
);
3430 else if (!get_info_about_necessary_edges (val
, &freq_sum
, &count_sum
,
3434 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3436 fprintf (dump_file
, " - considering value ");
3437 print_ipcp_constant_value (dump_file
, val
->value
);
3438 fprintf (dump_file
, " for ");
3439 ipa_dump_param (dump_file
, IPA_NODE_REF (node
), index
);
3441 fprintf (dump_file
, ", offset: " HOST_WIDE_INT_PRINT_DEC
, offset
);
3442 fprintf (dump_file
, " (caller_count: %i)\n", caller_count
);
3445 if (!good_cloning_opportunity_p (node
, val
->local_time_benefit
,
3446 freq_sum
, count_sum
,
3447 val
->local_size_cost
)
3448 && !good_cloning_opportunity_p (node
,
3449 val
->local_time_benefit
3450 + val
->prop_time_benefit
,
3451 freq_sum
, count_sum
,
3452 val
->local_size_cost
3453 + val
->prop_size_cost
))
3457 fprintf (dump_file
, " Creating a specialized node of %s/%i.\n",
3458 node
->name (), node
->order
);
3460 callers
= gather_edges_for_value (val
, caller_count
);
3461 kv
= known_csts
.copy ();
3462 move_binfos_to_values (kv
, known_binfos
);
3464 kv
[index
] = val
->value
;
3465 find_more_scalar_values_for_callers_subset (node
, kv
, callers
);
3466 aggvals
= find_aggregate_values_for_callers_subset (node
, callers
);
3467 gcc_checking_assert (offset
== -1
3468 || ipcp_val_in_agg_replacements_p (aggvals
, index
,
3469 offset
, val
->value
));
3470 val
->spec_node
= create_specialized_node (node
, kv
, aggvals
, callers
);
3471 overall_size
+= val
->local_size_cost
;
3473 /* TODO: If for some lattice there is only one other known value
3474 left, make a special node for it too. */
3479 /* Decide whether and what specialized clones of NODE should be created. */
3482 decide_whether_version_node (struct cgraph_node
*node
)
3484 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3485 int i
, count
= ipa_get_param_count (info
);
3486 vec
<tree
> known_csts
, known_binfos
;
3487 vec
<ipa_agg_jump_function
> known_aggs
= vNULL
;
3493 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3494 fprintf (dump_file
, "\nEvaluating opportunities for %s/%i.\n",
3495 node
->name (), node
->order
);
3497 gather_context_independent_values (info
, &known_csts
, &known_binfos
,
3498 info
->do_clone_for_all_contexts
? &known_aggs
3501 for (i
= 0; i
< count
;i
++)
3503 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3504 struct ipcp_lattice
*lat
= &plats
->itself
;
3505 struct ipcp_value
*val
;
3509 && !known_binfos
[i
])
3510 for (val
= lat
->values
; val
; val
= val
->next
)
3511 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
3514 if (!plats
->aggs_bottom
)
3516 struct ipcp_agg_lattice
*aglat
;
3517 struct ipcp_value
*val
;
3518 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3519 if (!aglat
->bottom
&& aglat
->values
3520 /* If the following is false, the one value is in
3522 && (plats
->aggs_contain_variable
3523 || !ipa_lat_is_single_const (aglat
)))
3524 for (val
= aglat
->values
; val
; val
= val
->next
)
3525 ret
|= decide_about_value (node
, i
, aglat
->offset
, val
,
3526 known_csts
, known_binfos
);
3528 info
= IPA_NODE_REF (node
);
3531 if (info
->do_clone_for_all_contexts
)
3533 struct cgraph_node
*clone
;
3534 vec
<cgraph_edge_p
> callers
;
3537 fprintf (dump_file
, " - Creating a specialized node of %s/%i "
3538 "for all known contexts.\n", node
->name (),
3541 callers
= collect_callers_of_node (node
);
3542 move_binfos_to_values (known_csts
, known_binfos
);
3543 clone
= create_specialized_node (node
, known_csts
,
3544 known_aggs_to_agg_replacement_list (known_aggs
),
3546 info
= IPA_NODE_REF (node
);
3547 info
->do_clone_for_all_contexts
= false;
3548 IPA_NODE_REF (clone
)->is_all_contexts_clone
= true;
3549 for (i
= 0; i
< count
; i
++)
3550 vec_free (known_aggs
[i
].items
);
3551 known_aggs
.release ();
3555 known_csts
.release ();
3557 known_binfos
.release ();
3561 /* Transitively mark all callees of NODE within the same SCC as not dead. */
3564 spread_undeadness (struct cgraph_node
*node
)
3566 struct cgraph_edge
*cs
;
3568 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
3569 if (ipa_edge_within_scc (cs
))
3571 struct cgraph_node
*callee
;
3572 struct ipa_node_params
*info
;
3574 callee
= cgraph_function_node (cs
->callee
, NULL
);
3575 info
= IPA_NODE_REF (callee
);
3577 if (info
->node_dead
)
3579 info
->node_dead
= 0;
3580 spread_undeadness (callee
);
3585 /* Return true if NODE has a caller from outside of its SCC that is not
3586 dead. Worker callback for cgraph_for_node_and_aliases. */
3589 has_undead_caller_from_outside_scc_p (struct cgraph_node
*node
,
3590 void *data ATTRIBUTE_UNUSED
)
3592 struct cgraph_edge
*cs
;
3594 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
3595 if (cs
->caller
->thunk
.thunk_p
3596 && cgraph_for_node_and_aliases (cs
->caller
,
3597 has_undead_caller_from_outside_scc_p
,
3600 else if (!ipa_edge_within_scc (cs
)
3601 && !IPA_NODE_REF (cs
->caller
)->node_dead
)
3607 /* Identify nodes within the same SCC as NODE which are no longer needed
3608 because of new clones and will be removed as unreachable. */
3611 identify_dead_nodes (struct cgraph_node
*node
)
3613 struct cgraph_node
*v
;
3614 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
3615 if (cgraph_will_be_removed_from_program_if_no_direct_calls (v
)
3616 && !cgraph_for_node_and_aliases (v
,
3617 has_undead_caller_from_outside_scc_p
,
3619 IPA_NODE_REF (v
)->node_dead
= 1;
3621 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
3622 if (!IPA_NODE_REF (v
)->node_dead
)
3623 spread_undeadness (v
);
3625 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3627 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
3628 if (IPA_NODE_REF (v
)->node_dead
)
3629 fprintf (dump_file
, " Marking node as dead: %s/%i.\n",
3630 v
->name (), v
->order
);
3634 /* The decision stage. Iterate over the topological order of call graph nodes
3635 TOPO and make specialized clones if deemed beneficial. */
3638 ipcp_decision_stage (struct topo_info
*topo
)
3643 fprintf (dump_file
, "\nIPA decision stage:\n\n");
3645 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
3647 struct cgraph_node
*node
= topo
->order
[i
];
3648 bool change
= false, iterate
= true;
3652 struct cgraph_node
*v
;
3654 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
3655 if (cgraph_function_with_gimple_body_p (v
)
3656 && ipcp_versionable_function_p (v
))
3657 iterate
|= decide_whether_version_node (v
);
3662 identify_dead_nodes (node
);
3666 /* The IPCP driver. */
3671 struct cgraph_2edge_hook_list
*edge_duplication_hook_holder
;
3672 struct cgraph_edge_hook_list
*edge_removal_hook_holder
;
3673 struct topo_info topo
;
3675 ipa_check_create_node_params ();
3676 ipa_check_create_edge_args ();
3677 grow_edge_clone_vectors ();
3678 edge_duplication_hook_holder
=
3679 cgraph_add_edge_duplication_hook (&ipcp_edge_duplication_hook
, NULL
);
3680 edge_removal_hook_holder
=
3681 cgraph_add_edge_removal_hook (&ipcp_edge_removal_hook
, NULL
);
3683 ipcp_values_pool
= create_alloc_pool ("IPA-CP values",
3684 sizeof (struct ipcp_value
), 32);
3685 ipcp_sources_pool
= create_alloc_pool ("IPA-CP value sources",
3686 sizeof (struct ipcp_value_source
), 64);
3687 ipcp_agg_lattice_pool
= create_alloc_pool ("IPA_CP aggregate lattices",
3688 sizeof (struct ipcp_agg_lattice
),
3692 fprintf (dump_file
, "\nIPA structures before propagation:\n");
3693 if (dump_flags
& TDF_DETAILS
)
3694 ipa_print_all_params (dump_file
);
3695 ipa_print_all_jump_functions (dump_file
);
3698 /* Topological sort. */
3699 build_toporder_info (&topo
);
3700 /* Do the interprocedural propagation. */
3701 ipcp_propagate_stage (&topo
);
3702 /* Decide what constant propagation and cloning should be performed. */
3703 ipcp_decision_stage (&topo
);
3705 /* Free all IPCP structures. */
3706 free_toporder_info (&topo
);
3707 next_edge_clone
.release ();
3708 cgraph_remove_edge_removal_hook (edge_removal_hook_holder
);
3709 cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder
);
3710 ipa_free_all_structures_after_ipa_cp ();
3712 fprintf (dump_file
, "\nIPA constant propagation end\n");
3716 /* Initialization and computation of IPCP data structures. This is the initial
3717 intraprocedural analysis of functions, which gathers information to be
3718 propagated later on. */
3721 ipcp_generate_summary (void)
3723 struct cgraph_node
*node
;
3726 fprintf (dump_file
, "\nIPA constant propagation start:\n");
3727 ipa_register_cgraph_hooks ();
3729 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
3731 node
->local
.versionable
3732 = tree_versionable_function_p (node
->decl
);
3733 ipa_analyze_node (node
);
3737 /* Write ipcp summary for nodes in SET. */
3740 ipcp_write_summary (void)
3742 ipa_prop_write_jump_functions ();
3745 /* Read ipcp summary. */
3748 ipcp_read_summary (void)
3750 ipa_prop_read_jump_functions ();
3753 /* Gate for IPCP optimization. */
3756 cgraph_gate_cp (void)
3758 /* FIXME: We should remove the optimize check after we ensure we never run
3759 IPA passes when not optimizing. */
3760 return flag_ipa_cp
&& optimize
;
3765 const pass_data pass_data_ipa_cp
=
3767 IPA_PASS
, /* type */
3769 OPTGROUP_NONE
, /* optinfo_flags */
3770 true, /* has_gate */
3771 true, /* has_execute */
3772 TV_IPA_CONSTANT_PROP
, /* tv_id */
3773 0, /* properties_required */
3774 0, /* properties_provided */
3775 0, /* properties_destroyed */
3776 0, /* todo_flags_start */
3777 ( TODO_dump_symtab
| TODO_remove_functions
), /* todo_flags_finish */
3780 class pass_ipa_cp
: public ipa_opt_pass_d
3783 pass_ipa_cp (gcc::context
*ctxt
)
3784 : ipa_opt_pass_d (pass_data_ipa_cp
, ctxt
,
3785 ipcp_generate_summary
, /* generate_summary */
3786 ipcp_write_summary
, /* write_summary */
3787 ipcp_read_summary
, /* read_summary */
3788 ipa_prop_write_all_agg_replacement
, /*
3789 write_optimization_summary */
3790 ipa_prop_read_all_agg_replacement
, /*
3791 read_optimization_summary */
3792 NULL
, /* stmt_fixup */
3793 0, /* function_transform_todo_flags_start */
3794 ipcp_transform_function
, /* function_transform */
3795 NULL
) /* variable_transform */
3798 /* opt_pass methods: */
3799 bool gate () { return cgraph_gate_cp (); }
3800 unsigned int execute () { return ipcp_driver (); }
3802 }; // class pass_ipa_cp
3807 make_pass_ipa_cp (gcc::context
*ctxt
)
3809 return new pass_ipa_cp (ctxt
);