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
)
802 ? ipa_get_jf_ancestor_type (jfunc
)
803 : ptr_type_node
, NULL
, false);
804 return build_fold_addr_expr (t
);
810 /* Determine whether JFUNC evaluates to a known value (that is either a
811 constant or a binfo) and if so, return it. Otherwise return NULL. INFO
812 describes the caller node so that pass-through jump functions can be
816 ipa_value_from_jfunc (struct ipa_node_params
*info
, struct ipa_jump_func
*jfunc
)
818 if (jfunc
->type
== IPA_JF_CONST
)
819 return ipa_get_jf_constant (jfunc
);
820 else if (jfunc
->type
== IPA_JF_KNOWN_TYPE
)
821 return ipa_binfo_from_known_type_jfunc (jfunc
);
822 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
823 || jfunc
->type
== IPA_JF_ANCESTOR
)
828 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
829 idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
831 idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
833 if (info
->ipcp_orig_node
)
834 input
= info
->known_vals
[idx
];
837 struct ipcp_lattice
*lat
;
841 gcc_checking_assert (!flag_ipa_cp
);
844 lat
= ipa_get_scalar_lat (info
, idx
);
845 if (!ipa_lat_is_single_const (lat
))
847 input
= lat
->values
->value
;
853 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
854 return ipa_get_jf_pass_through_result (jfunc
, input
);
856 return ipa_get_jf_ancestor_result (jfunc
, input
);
863 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
864 bottom, not containing a variable component and without any known value at
868 ipcp_verify_propagated_values (void)
870 struct cgraph_node
*node
;
872 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
874 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
875 int i
, count
= ipa_get_param_count (info
);
877 for (i
= 0; i
< count
; i
++)
879 struct ipcp_lattice
*lat
= ipa_get_scalar_lat (info
, i
);
882 && !lat
->contains_variable
883 && lat
->values_count
== 0)
887 dump_symtab (dump_file
);
888 fprintf (dump_file
, "\nIPA lattices after constant "
889 "propagation, before gcc_unreachable:\n");
890 print_all_lattices (dump_file
, true, false);
899 /* Return true iff X and Y should be considered equal values by IPA-CP. */
902 values_equal_for_ipcp_p (tree x
, tree y
)
904 gcc_checking_assert (x
!= NULL_TREE
&& y
!= NULL_TREE
);
909 if (TREE_CODE (x
) == TREE_BINFO
|| TREE_CODE (y
) == TREE_BINFO
)
912 if (TREE_CODE (x
) == ADDR_EXPR
913 && TREE_CODE (y
) == ADDR_EXPR
914 && TREE_CODE (TREE_OPERAND (x
, 0)) == CONST_DECL
915 && TREE_CODE (TREE_OPERAND (y
, 0)) == CONST_DECL
)
916 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x
, 0)),
917 DECL_INITIAL (TREE_OPERAND (y
, 0)), 0);
919 return operand_equal_p (x
, y
, 0);
922 /* Add a new value source to VAL, marking that a value comes from edge CS and
923 (if the underlying jump function is a pass-through or an ancestor one) from
924 a caller value SRC_VAL of a caller parameter described by SRC_INDEX. OFFSET
925 is negative if the source was the scalar value of the parameter itself or
926 the offset within an aggregate. */
929 add_value_source (struct ipcp_value
*val
, struct cgraph_edge
*cs
,
930 struct ipcp_value
*src_val
, int src_idx
, HOST_WIDE_INT offset
)
932 struct ipcp_value_source
*src
;
934 src
= (struct ipcp_value_source
*) pool_alloc (ipcp_sources_pool
);
935 src
->offset
= offset
;
938 src
->index
= src_idx
;
940 src
->next
= val
->sources
;
944 /* Try to add NEWVAL to LAT, potentially creating a new struct ipcp_value for
945 it. CS, SRC_VAL SRC_INDEX and OFFSET are meant for add_value_source and
946 have the same meaning. */
949 add_value_to_lattice (struct ipcp_lattice
*lat
, tree newval
,
950 struct cgraph_edge
*cs
, struct ipcp_value
*src_val
,
951 int src_idx
, HOST_WIDE_INT offset
)
953 struct ipcp_value
*val
;
958 for (val
= lat
->values
; val
; val
= val
->next
)
959 if (values_equal_for_ipcp_p (val
->value
, newval
))
961 if (ipa_edge_within_scc (cs
))
963 struct ipcp_value_source
*s
;
964 for (s
= val
->sources
; s
; s
= s
->next
)
971 add_value_source (val
, cs
, src_val
, src_idx
, offset
);
975 if (lat
->values_count
== PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE
))
977 /* We can only free sources, not the values themselves, because sources
978 of other values in this this SCC might point to them. */
979 for (val
= lat
->values
; val
; val
= val
->next
)
983 struct ipcp_value_source
*src
= val
->sources
;
984 val
->sources
= src
->next
;
985 pool_free (ipcp_sources_pool
, src
);
990 return set_lattice_to_bottom (lat
);
994 val
= (struct ipcp_value
*) pool_alloc (ipcp_values_pool
);
995 memset (val
, 0, sizeof (*val
));
997 add_value_source (val
, cs
, src_val
, src_idx
, offset
);
999 val
->next
= lat
->values
;
1004 /* Like above but passes a special value of offset to distinguish that the
1005 origin is the scalar value of the parameter rather than a part of an
1009 add_scalar_value_to_lattice (struct ipcp_lattice
*lat
, tree newval
,
1010 struct cgraph_edge
*cs
,
1011 struct ipcp_value
*src_val
, int src_idx
)
1013 return add_value_to_lattice (lat
, newval
, cs
, src_val
, src_idx
, -1);
1016 /* Propagate values through a pass-through jump function JFUNC associated with
1017 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1018 is the index of the source parameter. */
1021 propagate_vals_accross_pass_through (struct cgraph_edge
*cs
,
1022 struct ipa_jump_func
*jfunc
,
1023 struct ipcp_lattice
*src_lat
,
1024 struct ipcp_lattice
*dest_lat
,
1027 struct ipcp_value
*src_val
;
1030 /* Do not create new values when propagating within an SCC because if there
1031 are arithmetic functions with circular dependencies, there is infinite
1032 number of them and we would just make lattices bottom. */
1033 if ((ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1034 && ipa_edge_within_scc (cs
))
1035 ret
= set_lattice_contains_variable (dest_lat
);
1037 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1039 tree cstval
= ipa_get_jf_pass_through_result (jfunc
, src_val
->value
);
1042 ret
|= add_scalar_value_to_lattice (dest_lat
, cstval
, cs
, src_val
,
1045 ret
|= set_lattice_contains_variable (dest_lat
);
1051 /* Propagate values through an ancestor jump function JFUNC associated with
1052 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1053 is the index of the source parameter. */
1056 propagate_vals_accross_ancestor (struct cgraph_edge
*cs
,
1057 struct ipa_jump_func
*jfunc
,
1058 struct ipcp_lattice
*src_lat
,
1059 struct ipcp_lattice
*dest_lat
,
1062 struct ipcp_value
*src_val
;
1065 if (ipa_edge_within_scc (cs
))
1066 return set_lattice_contains_variable (dest_lat
);
1068 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1070 tree t
= ipa_get_jf_ancestor_result (jfunc
, src_val
->value
);
1073 ret
|= add_scalar_value_to_lattice (dest_lat
, t
, cs
, src_val
, src_idx
);
1075 ret
|= set_lattice_contains_variable (dest_lat
);
1081 /* Propagate scalar values across jump function JFUNC that is associated with
1082 edge CS and put the values into DEST_LAT. */
1085 propagate_scalar_accross_jump_function (struct cgraph_edge
*cs
,
1086 struct ipa_jump_func
*jfunc
,
1087 struct ipcp_lattice
*dest_lat
)
1089 if (dest_lat
->bottom
)
1092 if (jfunc
->type
== IPA_JF_CONST
1093 || jfunc
->type
== IPA_JF_KNOWN_TYPE
)
1097 if (jfunc
->type
== IPA_JF_KNOWN_TYPE
)
1099 val
= ipa_binfo_from_known_type_jfunc (jfunc
);
1101 return set_lattice_contains_variable (dest_lat
);
1104 val
= ipa_get_jf_constant (jfunc
);
1105 return add_scalar_value_to_lattice (dest_lat
, val
, cs
, NULL
, 0);
1107 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1108 || jfunc
->type
== IPA_JF_ANCESTOR
)
1110 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1111 struct ipcp_lattice
*src_lat
;
1115 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1116 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1118 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1120 src_lat
= ipa_get_scalar_lat (caller_info
, src_idx
);
1121 if (src_lat
->bottom
)
1122 return set_lattice_contains_variable (dest_lat
);
1124 /* If we would need to clone the caller and cannot, do not propagate. */
1125 if (!ipcp_versionable_function_p (cs
->caller
)
1126 && (src_lat
->contains_variable
1127 || (src_lat
->values_count
> 1)))
1128 return set_lattice_contains_variable (dest_lat
);
1130 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1131 ret
= propagate_vals_accross_pass_through (cs
, jfunc
, src_lat
,
1134 ret
= propagate_vals_accross_ancestor (cs
, jfunc
, src_lat
, dest_lat
,
1137 if (src_lat
->contains_variable
)
1138 ret
|= set_lattice_contains_variable (dest_lat
);
1143 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1144 use it for indirect inlining), we should propagate them too. */
1145 return set_lattice_contains_variable (dest_lat
);
1148 /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
1149 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
1150 other cases, return false). If there are no aggregate items, set
1151 aggs_by_ref to NEW_AGGS_BY_REF. */
1154 set_check_aggs_by_ref (struct ipcp_param_lattices
*dest_plats
,
1155 bool new_aggs_by_ref
)
1157 if (dest_plats
->aggs
)
1159 if (dest_plats
->aggs_by_ref
!= new_aggs_by_ref
)
1161 set_agg_lats_to_bottom (dest_plats
);
1166 dest_plats
->aggs_by_ref
= new_aggs_by_ref
;
1170 /* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
1171 already existing lattice for the given OFFSET and SIZE, marking all skipped
1172 lattices as containing variable and checking for overlaps. If there is no
1173 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
1174 it with offset, size and contains_variable to PRE_EXISTING, and return true,
1175 unless there are too many already. If there are two many, return false. If
1176 there are overlaps turn whole DEST_PLATS to bottom and return false. If any
1177 skipped lattices were newly marked as containing variable, set *CHANGE to
1181 merge_agg_lats_step (struct ipcp_param_lattices
*dest_plats
,
1182 HOST_WIDE_INT offset
, HOST_WIDE_INT val_size
,
1183 struct ipcp_agg_lattice
***aglat
,
1184 bool pre_existing
, bool *change
)
1186 gcc_checking_assert (offset
>= 0);
1188 while (**aglat
&& (**aglat
)->offset
< offset
)
1190 if ((**aglat
)->offset
+ (**aglat
)->size
> offset
)
1192 set_agg_lats_to_bottom (dest_plats
);
1195 *change
|= set_lattice_contains_variable (**aglat
);
1196 *aglat
= &(**aglat
)->next
;
1199 if (**aglat
&& (**aglat
)->offset
== offset
)
1201 if ((**aglat
)->size
!= val_size
1203 && (**aglat
)->next
->offset
< offset
+ val_size
))
1205 set_agg_lats_to_bottom (dest_plats
);
1208 gcc_checking_assert (!(**aglat
)->next
1209 || (**aglat
)->next
->offset
>= offset
+ val_size
);
1214 struct ipcp_agg_lattice
*new_al
;
1216 if (**aglat
&& (**aglat
)->offset
< offset
+ val_size
)
1218 set_agg_lats_to_bottom (dest_plats
);
1221 if (dest_plats
->aggs_count
== PARAM_VALUE (PARAM_IPA_MAX_AGG_ITEMS
))
1223 dest_plats
->aggs_count
++;
1224 new_al
= (struct ipcp_agg_lattice
*) pool_alloc (ipcp_agg_lattice_pool
);
1225 memset (new_al
, 0, sizeof (*new_al
));
1227 new_al
->offset
= offset
;
1228 new_al
->size
= val_size
;
1229 new_al
->contains_variable
= pre_existing
;
1231 new_al
->next
= **aglat
;
1237 /* Set all AGLAT and all other aggregate lattices reachable by next pointers as
1238 containing an unknown value. */
1241 set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice
*aglat
)
1246 ret
|= set_lattice_contains_variable (aglat
);
1247 aglat
= aglat
->next
;
1252 /* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
1253 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source
1254 parameter used for lattice value sources. Return true if DEST_PLATS changed
1258 merge_aggregate_lattices (struct cgraph_edge
*cs
,
1259 struct ipcp_param_lattices
*dest_plats
,
1260 struct ipcp_param_lattices
*src_plats
,
1261 int src_idx
, HOST_WIDE_INT offset_delta
)
1263 bool pre_existing
= dest_plats
->aggs
!= NULL
;
1264 struct ipcp_agg_lattice
**dst_aglat
;
1267 if (set_check_aggs_by_ref (dest_plats
, src_plats
->aggs_by_ref
))
1269 if (src_plats
->aggs_bottom
)
1270 return set_agg_lats_contain_variable (dest_plats
);
1271 if (src_plats
->aggs_contain_variable
)
1272 ret
|= set_agg_lats_contain_variable (dest_plats
);
1273 dst_aglat
= &dest_plats
->aggs
;
1275 for (struct ipcp_agg_lattice
*src_aglat
= src_plats
->aggs
;
1277 src_aglat
= src_aglat
->next
)
1279 HOST_WIDE_INT new_offset
= src_aglat
->offset
- offset_delta
;
1283 if (merge_agg_lats_step (dest_plats
, new_offset
, src_aglat
->size
,
1284 &dst_aglat
, pre_existing
, &ret
))
1286 struct ipcp_agg_lattice
*new_al
= *dst_aglat
;
1288 dst_aglat
= &(*dst_aglat
)->next
;
1289 if (src_aglat
->bottom
)
1291 ret
|= set_lattice_contains_variable (new_al
);
1294 if (src_aglat
->contains_variable
)
1295 ret
|= set_lattice_contains_variable (new_al
);
1296 for (struct ipcp_value
*val
= src_aglat
->values
;
1299 ret
|= add_value_to_lattice (new_al
, val
->value
, cs
, val
, src_idx
,
1302 else if (dest_plats
->aggs_bottom
)
1305 ret
|= set_chain_of_aglats_contains_variable (*dst_aglat
);
1309 /* Determine whether there is anything to propagate FROM SRC_PLATS through a
1310 pass-through JFUNC and if so, whether it has conform and conforms to the
1311 rules about propagating values passed by reference. */
1314 agg_pass_through_permissible_p (struct ipcp_param_lattices
*src_plats
,
1315 struct ipa_jump_func
*jfunc
)
1317 return src_plats
->aggs
1318 && (!src_plats
->aggs_by_ref
1319 || ipa_get_jf_pass_through_agg_preserved (jfunc
));
1322 /* Propagate scalar values across jump function JFUNC that is associated with
1323 edge CS and put the values into DEST_LAT. */
1326 propagate_aggs_accross_jump_function (struct cgraph_edge
*cs
,
1327 struct ipa_jump_func
*jfunc
,
1328 struct ipcp_param_lattices
*dest_plats
)
1332 if (dest_plats
->aggs_bottom
)
1335 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1336 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
1338 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1339 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1340 struct ipcp_param_lattices
*src_plats
;
1342 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
1343 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
1345 /* Currently we do not produce clobber aggregate jump
1346 functions, replace with merging when we do. */
1347 gcc_assert (!jfunc
->agg
.items
);
1348 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
,
1352 ret
|= set_agg_lats_contain_variable (dest_plats
);
1354 else if (jfunc
->type
== IPA_JF_ANCESTOR
1355 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
1357 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1358 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1359 struct ipcp_param_lattices
*src_plats
;
1361 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
1362 if (src_plats
->aggs
&& src_plats
->aggs_by_ref
)
1364 /* Currently we do not produce clobber aggregate jump
1365 functions, replace with merging when we do. */
1366 gcc_assert (!jfunc
->agg
.items
);
1367 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
, src_idx
,
1368 ipa_get_jf_ancestor_offset (jfunc
));
1370 else if (!src_plats
->aggs_by_ref
)
1371 ret
|= set_agg_lats_to_bottom (dest_plats
);
1373 ret
|= set_agg_lats_contain_variable (dest_plats
);
1375 else if (jfunc
->agg
.items
)
1377 bool pre_existing
= dest_plats
->aggs
!= NULL
;
1378 struct ipcp_agg_lattice
**aglat
= &dest_plats
->aggs
;
1379 struct ipa_agg_jf_item
*item
;
1382 if (set_check_aggs_by_ref (dest_plats
, jfunc
->agg
.by_ref
))
1385 FOR_EACH_VEC_ELT (*jfunc
->agg
.items
, i
, item
)
1387 HOST_WIDE_INT val_size
;
1389 if (item
->offset
< 0)
1391 gcc_checking_assert (is_gimple_ip_invariant (item
->value
));
1392 val_size
= tree_to_uhwi (TYPE_SIZE (TREE_TYPE (item
->value
)));
1394 if (merge_agg_lats_step (dest_plats
, item
->offset
, val_size
,
1395 &aglat
, pre_existing
, &ret
))
1397 ret
|= add_value_to_lattice (*aglat
, item
->value
, cs
, NULL
, 0, 0);
1398 aglat
= &(*aglat
)->next
;
1400 else if (dest_plats
->aggs_bottom
)
1404 ret
|= set_chain_of_aglats_contains_variable (*aglat
);
1407 ret
|= set_agg_lats_contain_variable (dest_plats
);
1412 /* Propagate constants from the caller to the callee of CS. INFO describes the
1416 propagate_constants_accross_call (struct cgraph_edge
*cs
)
1418 struct ipa_node_params
*callee_info
;
1419 enum availability availability
;
1420 struct cgraph_node
*callee
, *alias_or_thunk
;
1421 struct ipa_edge_args
*args
;
1423 int i
, args_count
, parms_count
;
1425 callee
= cgraph_function_node (cs
->callee
, &availability
);
1426 if (!callee
->definition
)
1428 gcc_checking_assert (cgraph_function_with_gimple_body_p (callee
));
1429 callee_info
= IPA_NODE_REF (callee
);
1431 args
= IPA_EDGE_REF (cs
);
1432 args_count
= ipa_get_cs_argument_count (args
);
1433 parms_count
= ipa_get_param_count (callee_info
);
1434 if (parms_count
== 0)
1437 /* If this call goes through a thunk we must not propagate to the first (0th)
1438 parameter. However, we might need to uncover a thunk from below a series
1439 of aliases first. */
1440 alias_or_thunk
= cs
->callee
;
1441 while (alias_or_thunk
->alias
)
1442 alias_or_thunk
= cgraph_alias_target (alias_or_thunk
);
1443 if (alias_or_thunk
->thunk
.thunk_p
)
1445 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
1452 for (; (i
< args_count
) && (i
< parms_count
); i
++)
1454 struct ipa_jump_func
*jump_func
= ipa_get_ith_jump_func (args
, i
);
1455 struct ipcp_param_lattices
*dest_plats
;
1457 dest_plats
= ipa_get_parm_lattices (callee_info
, i
);
1458 if (availability
== AVAIL_OVERWRITABLE
)
1459 ret
|= set_all_contains_variable (dest_plats
);
1462 ret
|= propagate_scalar_accross_jump_function (cs
, jump_func
,
1463 &dest_plats
->itself
);
1464 ret
|= propagate_aggs_accross_jump_function (cs
, jump_func
,
1468 for (; i
< parms_count
; i
++)
1469 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
, i
));
1474 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
1475 (which can contain both constants and binfos), KNOWN_BINFOS, KNOWN_AGGS or
1476 AGG_REPS return the destination. The latter three can be NULL. If AGG_REPS
1477 is not NULL, KNOWN_AGGS is ignored. */
1480 ipa_get_indirect_edge_target_1 (struct cgraph_edge
*ie
,
1481 vec
<tree
> known_vals
,
1482 vec
<tree
> known_binfos
,
1483 vec
<ipa_agg_jump_function_p
> known_aggs
,
1484 struct ipa_agg_replacement_value
*agg_reps
)
1486 int param_index
= ie
->indirect_info
->param_index
;
1487 HOST_WIDE_INT token
, anc_offset
;
1492 if (param_index
== -1
1493 || known_vals
.length () <= (unsigned int) param_index
)
1496 if (!ie
->indirect_info
->polymorphic
)
1500 if (ie
->indirect_info
->agg_contents
)
1507 if (agg_reps
->index
== param_index
1508 && agg_reps
->offset
== ie
->indirect_info
->offset
1509 && agg_reps
->by_ref
== ie
->indirect_info
->by_ref
)
1511 t
= agg_reps
->value
;
1514 agg_reps
= agg_reps
->next
;
1517 else if (known_aggs
.length () > (unsigned int) param_index
)
1519 struct ipa_agg_jump_function
*agg
;
1520 agg
= known_aggs
[param_index
];
1521 t
= ipa_find_agg_cst_for_param (agg
, ie
->indirect_info
->offset
,
1522 ie
->indirect_info
->by_ref
);
1528 t
= known_vals
[param_index
];
1531 TREE_CODE (t
) == ADDR_EXPR
1532 && TREE_CODE (TREE_OPERAND (t
, 0)) == FUNCTION_DECL
)
1533 return TREE_OPERAND (t
, 0);
1538 if (!flag_devirtualize
)
1541 gcc_assert (!ie
->indirect_info
->agg_contents
);
1542 token
= ie
->indirect_info
->otr_token
;
1543 anc_offset
= ie
->indirect_info
->offset
;
1544 otr_type
= ie
->indirect_info
->otr_type
;
1548 /* Try to work out value of virtual table pointer value in replacemnets. */
1549 if (!t
&& agg_reps
&& !ie
->indirect_info
->by_ref
)
1553 if (agg_reps
->index
== param_index
1554 && agg_reps
->offset
== ie
->indirect_info
->offset
1555 && agg_reps
->by_ref
)
1557 t
= agg_reps
->value
;
1560 agg_reps
= agg_reps
->next
;
1564 /* Try to work out value of virtual table pointer value in known
1565 aggregate values. */
1566 if (!t
&& known_aggs
.length () > (unsigned int) param_index
1567 && !ie
->indirect_info
->by_ref
)
1569 struct ipa_agg_jump_function
*agg
;
1570 agg
= known_aggs
[param_index
];
1571 t
= ipa_find_agg_cst_for_param (agg
, ie
->indirect_info
->offset
,
1575 /* If we found the virtual table pointer, lookup the target. */
1579 unsigned HOST_WIDE_INT offset
;
1580 if (vtable_pointer_value_to_vtable (t
, &vtable
, &offset
))
1582 target
= gimple_get_virt_method_for_vtable (ie
->indirect_info
->otr_token
,
1586 if ((TREE_CODE (TREE_TYPE (target
)) == FUNCTION_TYPE
1587 && DECL_FUNCTION_CODE (target
) == BUILT_IN_UNREACHABLE
)
1588 || !possible_polymorphic_call_target_p
1589 (ie
, cgraph_get_node (target
)))
1593 "Type inconsident devirtualization: %s/%i->%s\n",
1594 ie
->caller
->name (), ie
->caller
->order
,
1595 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (target
)));
1596 target
= builtin_decl_implicit (BUILT_IN_UNREACHABLE
);
1597 cgraph_get_create_node (target
);
1604 /* Did we work out BINFO via type propagation? */
1605 if (!t
&& known_binfos
.length () > (unsigned int) param_index
)
1606 t
= known_binfos
[param_index
];
1607 /* Or do we know the constant value of pointer? */
1609 t
= known_vals
[param_index
];
1613 if (TREE_CODE (t
) != TREE_BINFO
)
1615 ipa_polymorphic_call_context context
;
1616 vec
<cgraph_node
*>targets
;
1619 if (!get_polymorphic_call_info_from_invariant
1620 (&context
, t
, ie
->indirect_info
->otr_type
,
1623 targets
= possible_polymorphic_call_targets
1624 (ie
->indirect_info
->otr_type
,
1625 ie
->indirect_info
->otr_token
,
1627 if (!final
|| targets
.length () > 1)
1629 if (targets
.length () == 1)
1630 target
= targets
[0]->decl
;
1632 target
= builtin_decl_implicit (BUILT_IN_UNREACHABLE
);
1638 binfo
= get_binfo_at_offset (t
, anc_offset
, otr_type
);
1641 target
= gimple_get_virt_method_for_binfo (token
, binfo
);
1644 if (target
&& !possible_polymorphic_call_target_p (ie
,
1645 cgraph_get_node (target
)))
1649 "Type inconsident devirtualization: %s/%i->%s\n",
1650 ie
->caller
->name (), ie
->caller
->order
,
1651 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (target
)));
1652 target
= builtin_decl_implicit (BUILT_IN_UNREACHABLE
);
1653 cgraph_get_create_node (target
);
1660 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
1661 (which can contain both constants and binfos), KNOWN_BINFOS (which can be
1662 NULL) or KNOWN_AGGS (which also can be NULL) return the destination. */
1665 ipa_get_indirect_edge_target (struct cgraph_edge
*ie
,
1666 vec
<tree
> known_vals
,
1667 vec
<tree
> known_binfos
,
1668 vec
<ipa_agg_jump_function_p
> known_aggs
)
1670 return ipa_get_indirect_edge_target_1 (ie
, known_vals
, known_binfos
,
1674 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
1675 and KNOWN_BINFOS. */
1678 devirtualization_time_bonus (struct cgraph_node
*node
,
1679 vec
<tree
> known_csts
,
1680 vec
<tree
> known_binfos
,
1681 vec
<ipa_agg_jump_function_p
> known_aggs
)
1683 struct cgraph_edge
*ie
;
1686 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
1688 struct cgraph_node
*callee
;
1689 struct inline_summary
*isummary
;
1692 target
= ipa_get_indirect_edge_target (ie
, known_csts
, known_binfos
,
1697 /* Only bare minimum benefit for clearly un-inlineable targets. */
1699 callee
= cgraph_get_node (target
);
1700 if (!callee
|| !callee
->definition
)
1702 isummary
= inline_summary (callee
);
1703 if (!isummary
->inlinable
)
1706 /* FIXME: The values below need re-considering and perhaps also
1707 integrating into the cost metrics, at lest in some very basic way. */
1708 if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 4)
1710 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 2)
1712 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
1713 || DECL_DECLARED_INLINE_P (callee
->decl
))
1720 /* Return time bonus incurred because of HINTS. */
1723 hint_time_bonus (inline_hints hints
)
1726 if (hints
& (INLINE_HINT_loop_iterations
| INLINE_HINT_loop_stride
))
1727 result
+= PARAM_VALUE (PARAM_IPA_CP_LOOP_HINT_BONUS
);
1728 if (hints
& INLINE_HINT_array_index
)
1729 result
+= PARAM_VALUE (PARAM_IPA_CP_ARRAY_INDEX_HINT_BONUS
);
1733 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
1734 and SIZE_COST and with the sum of frequencies of incoming edges to the
1735 potential new clone in FREQUENCIES. */
1738 good_cloning_opportunity_p (struct cgraph_node
*node
, int time_benefit
,
1739 int freq_sum
, gcov_type count_sum
, int size_cost
)
1741 if (time_benefit
== 0
1742 || !flag_ipa_cp_clone
1743 || !optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node
->decl
)))
1746 gcc_assert (size_cost
> 0);
1750 int factor
= (count_sum
* 1000) / max_count
;
1751 int64_t evaluation
= (((int64_t) time_benefit
* factor
)
1754 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1755 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
1756 "size: %i, count_sum: " HOST_WIDE_INT_PRINT_DEC
1757 ") -> evaluation: " "%"PRId64
1758 ", threshold: %i\n",
1759 time_benefit
, size_cost
, (HOST_WIDE_INT
) count_sum
,
1760 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
1762 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
1766 int64_t evaluation
= (((int64_t) time_benefit
* freq_sum
)
1769 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1770 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
1771 "size: %i, freq_sum: %i) -> evaluation: "
1772 "%"PRId64
", threshold: %i\n",
1773 time_benefit
, size_cost
, freq_sum
, evaluation
,
1774 PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
1776 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
1780 /* Return all context independent values from aggregate lattices in PLATS in a
1781 vector. Return NULL if there are none. */
1783 static vec
<ipa_agg_jf_item
, va_gc
> *
1784 context_independent_aggregate_values (struct ipcp_param_lattices
*plats
)
1786 vec
<ipa_agg_jf_item
, va_gc
> *res
= NULL
;
1788 if (plats
->aggs_bottom
1789 || plats
->aggs_contain_variable
1790 || plats
->aggs_count
== 0)
1793 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
;
1795 aglat
= aglat
->next
)
1796 if (ipa_lat_is_single_const (aglat
))
1798 struct ipa_agg_jf_item item
;
1799 item
.offset
= aglat
->offset
;
1800 item
.value
= aglat
->values
->value
;
1801 vec_safe_push (res
, item
);
1806 /* Allocate KNOWN_CSTS, KNOWN_BINFOS and, if non-NULL, KNOWN_AGGS and populate
1807 them with values of parameters that are known independent of the context.
1808 INFO describes the function. If REMOVABLE_PARAMS_COST is non-NULL, the
1809 movement cost of all removable parameters will be stored in it. */
1812 gather_context_independent_values (struct ipa_node_params
*info
,
1813 vec
<tree
> *known_csts
,
1814 vec
<tree
> *known_binfos
,
1815 vec
<ipa_agg_jump_function
> *known_aggs
,
1816 int *removable_params_cost
)
1818 int i
, count
= ipa_get_param_count (info
);
1821 known_csts
->create (0);
1822 known_binfos
->create (0);
1823 known_csts
->safe_grow_cleared (count
);
1824 known_binfos
->safe_grow_cleared (count
);
1827 known_aggs
->create (0);
1828 known_aggs
->safe_grow_cleared (count
);
1831 if (removable_params_cost
)
1832 *removable_params_cost
= 0;
1834 for (i
= 0; i
< count
; i
++)
1836 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1837 struct ipcp_lattice
*lat
= &plats
->itself
;
1839 if (ipa_lat_is_single_const (lat
))
1841 struct ipcp_value
*val
= lat
->values
;
1842 if (TREE_CODE (val
->value
) != TREE_BINFO
)
1844 (*known_csts
)[i
] = val
->value
;
1845 if (removable_params_cost
)
1846 *removable_params_cost
1847 += estimate_move_cost (TREE_TYPE (val
->value
));
1850 else if (plats
->virt_call
)
1852 (*known_binfos
)[i
] = val
->value
;
1855 else if (removable_params_cost
1856 && !ipa_is_param_used (info
, i
))
1857 *removable_params_cost
+= ipa_get_param_move_cost (info
, i
);
1859 else if (removable_params_cost
1860 && !ipa_is_param_used (info
, i
))
1861 *removable_params_cost
1862 += ipa_get_param_move_cost (info
, i
);
1866 vec
<ipa_agg_jf_item
, va_gc
> *agg_items
;
1867 struct ipa_agg_jump_function
*ajf
;
1869 agg_items
= context_independent_aggregate_values (plats
);
1870 ajf
= &(*known_aggs
)[i
];
1871 ajf
->items
= agg_items
;
1872 ajf
->by_ref
= plats
->aggs_by_ref
;
1873 ret
|= agg_items
!= NULL
;
1880 /* The current interface in ipa-inline-analysis requires a pointer vector.
1883 FIXME: That interface should be re-worked, this is slightly silly. Still,
1884 I'd like to discuss how to change it first and this demonstrates the
1887 static vec
<ipa_agg_jump_function_p
>
1888 agg_jmp_p_vec_for_t_vec (vec
<ipa_agg_jump_function
> known_aggs
)
1890 vec
<ipa_agg_jump_function_p
> ret
;
1891 struct ipa_agg_jump_function
*ajf
;
1894 ret
.create (known_aggs
.length ());
1895 FOR_EACH_VEC_ELT (known_aggs
, i
, ajf
)
1896 ret
.quick_push (ajf
);
1900 /* Iterate over known values of parameters of NODE and estimate the local
1901 effects in terms of time and size they have. */
1904 estimate_local_effects (struct cgraph_node
*node
)
1906 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1907 int i
, count
= ipa_get_param_count (info
);
1908 vec
<tree
> known_csts
, known_binfos
;
1909 vec
<ipa_agg_jump_function
> known_aggs
;
1910 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
;
1912 int base_time
= inline_summary (node
)->time
;
1913 int removable_params_cost
;
1915 if (!count
|| !ipcp_versionable_function_p (node
))
1918 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1919 fprintf (dump_file
, "\nEstimating effects for %s/%i, base_time: %i.\n",
1920 node
->name (), node
->order
, base_time
);
1922 always_const
= gather_context_independent_values (info
, &known_csts
,
1923 &known_binfos
, &known_aggs
,
1924 &removable_params_cost
);
1925 known_aggs_ptrs
= agg_jmp_p_vec_for_t_vec (known_aggs
);
1928 struct caller_statistics stats
;
1932 init_caller_stats (&stats
);
1933 cgraph_for_node_and_aliases (node
, gather_caller_stats
, &stats
, false);
1934 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_binfos
,
1935 known_aggs_ptrs
, &size
, &time
, &hints
);
1936 time
-= devirtualization_time_bonus (node
, known_csts
, known_binfos
,
1938 time
-= hint_time_bonus (hints
);
1939 time
-= removable_params_cost
;
1940 size
-= stats
.n_calls
* removable_params_cost
;
1943 fprintf (dump_file
, " - context independent values, size: %i, "
1944 "time_benefit: %i\n", size
, base_time
- time
);
1947 || cgraph_will_be_removed_from_program_if_no_direct_calls (node
))
1949 info
->do_clone_for_all_contexts
= true;
1953 fprintf (dump_file
, " Decided to specialize for all "
1954 "known contexts, code not going to grow.\n");
1956 else if (good_cloning_opportunity_p (node
, base_time
- time
,
1957 stats
.freq_sum
, stats
.count_sum
,
1960 if (size
+ overall_size
<= max_new_size
)
1962 info
->do_clone_for_all_contexts
= true;
1964 overall_size
+= size
;
1967 fprintf (dump_file
, " Decided to specialize for all "
1968 "known contexts, growth deemed beneficial.\n");
1970 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1971 fprintf (dump_file
, " Not cloning for all contexts because "
1972 "max_new_size would be reached with %li.\n",
1973 size
+ overall_size
);
1977 for (i
= 0; i
< count
; i
++)
1979 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1980 struct ipcp_lattice
*lat
= &plats
->itself
;
1981 struct ipcp_value
*val
;
1990 for (val
= lat
->values
; val
; val
= val
->next
)
1992 int time
, size
, time_benefit
;
1995 if (TREE_CODE (val
->value
) != TREE_BINFO
)
1997 known_csts
[i
] = val
->value
;
1998 known_binfos
[i
] = NULL_TREE
;
1999 emc
= estimate_move_cost (TREE_TYPE (val
->value
));
2001 else if (plats
->virt_call
)
2003 known_csts
[i
] = NULL_TREE
;
2004 known_binfos
[i
] = val
->value
;
2010 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_binfos
,
2011 known_aggs_ptrs
, &size
, &time
,
2013 time_benefit
= base_time
- time
2014 + devirtualization_time_bonus (node
, known_csts
, known_binfos
,
2016 + hint_time_bonus (hints
)
2017 + removable_params_cost
+ emc
;
2019 gcc_checking_assert (size
>=0);
2020 /* The inliner-heuristics based estimates may think that in certain
2021 contexts some functions do not have any size at all but we want
2022 all specializations to have at least a tiny cost, not least not to
2027 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2029 fprintf (dump_file
, " - estimates for value ");
2030 print_ipcp_constant_value (dump_file
, val
->value
);
2031 fprintf (dump_file
, " for ");
2032 ipa_dump_param (dump_file
, info
, i
);
2033 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
2034 time_benefit
, size
);
2037 val
->local_time_benefit
= time_benefit
;
2038 val
->local_size_cost
= size
;
2040 known_binfos
[i
] = NULL_TREE
;
2041 known_csts
[i
] = NULL_TREE
;
2044 for (i
= 0; i
< count
; i
++)
2046 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2047 struct ipa_agg_jump_function
*ajf
;
2048 struct ipcp_agg_lattice
*aglat
;
2050 if (plats
->aggs_bottom
|| !plats
->aggs
)
2053 ajf
= &known_aggs
[i
];
2054 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2056 struct ipcp_value
*val
;
2057 if (aglat
->bottom
|| !aglat
->values
2058 /* If the following is true, the one value is in known_aggs. */
2059 || (!plats
->aggs_contain_variable
2060 && ipa_lat_is_single_const (aglat
)))
2063 for (val
= aglat
->values
; val
; val
= val
->next
)
2065 int time
, size
, time_benefit
;
2066 struct ipa_agg_jf_item item
;
2069 item
.offset
= aglat
->offset
;
2070 item
.value
= val
->value
;
2071 vec_safe_push (ajf
->items
, item
);
2073 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_binfos
,
2074 known_aggs_ptrs
, &size
, &time
,
2076 time_benefit
= base_time
- time
2077 + devirtualization_time_bonus (node
, known_csts
, known_binfos
,
2079 + hint_time_bonus (hints
);
2080 gcc_checking_assert (size
>=0);
2084 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2086 fprintf (dump_file
, " - estimates for value ");
2087 print_ipcp_constant_value (dump_file
, val
->value
);
2088 fprintf (dump_file
, " for ");
2089 ipa_dump_param (dump_file
, info
, i
);
2090 fprintf (dump_file
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
2091 "]: time_benefit: %i, size: %i\n",
2092 plats
->aggs_by_ref
? "ref " : "",
2093 aglat
->offset
, time_benefit
, size
);
2096 val
->local_time_benefit
= time_benefit
;
2097 val
->local_size_cost
= size
;
2103 for (i
= 0; i
< count
; i
++)
2104 vec_free (known_aggs
[i
].items
);
2106 known_csts
.release ();
2107 known_binfos
.release ();
2108 known_aggs
.release ();
2109 known_aggs_ptrs
.release ();
2113 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
2114 topological sort of values. */
2117 add_val_to_toposort (struct ipcp_value
*cur_val
)
2119 static int dfs_counter
= 0;
2120 static struct ipcp_value
*stack
;
2121 struct ipcp_value_source
*src
;
2127 cur_val
->dfs
= dfs_counter
;
2128 cur_val
->low_link
= dfs_counter
;
2130 cur_val
->topo_next
= stack
;
2132 cur_val
->on_stack
= true;
2134 for (src
= cur_val
->sources
; src
; src
= src
->next
)
2137 if (src
->val
->dfs
== 0)
2139 add_val_to_toposort (src
->val
);
2140 if (src
->val
->low_link
< cur_val
->low_link
)
2141 cur_val
->low_link
= src
->val
->low_link
;
2143 else if (src
->val
->on_stack
2144 && src
->val
->dfs
< cur_val
->low_link
)
2145 cur_val
->low_link
= src
->val
->dfs
;
2148 if (cur_val
->dfs
== cur_val
->low_link
)
2150 struct ipcp_value
*v
, *scc_list
= NULL
;
2155 stack
= v
->topo_next
;
2156 v
->on_stack
= false;
2158 v
->scc_next
= scc_list
;
2161 while (v
!= cur_val
);
2163 cur_val
->topo_next
= values_topo
;
2164 values_topo
= cur_val
;
2168 /* Add all values in lattices associated with NODE to the topological sort if
2169 they are not there yet. */
2172 add_all_node_vals_to_toposort (struct cgraph_node
*node
)
2174 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2175 int i
, count
= ipa_get_param_count (info
);
2177 for (i
= 0; i
< count
; i
++)
2179 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2180 struct ipcp_lattice
*lat
= &plats
->itself
;
2181 struct ipcp_agg_lattice
*aglat
;
2182 struct ipcp_value
*val
;
2185 for (val
= lat
->values
; val
; val
= val
->next
)
2186 add_val_to_toposort (val
);
2188 if (!plats
->aggs_bottom
)
2189 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2191 for (val
= aglat
->values
; val
; val
= val
->next
)
2192 add_val_to_toposort (val
);
2196 /* One pass of constants propagation along the call graph edges, from callers
2197 to callees (requires topological ordering in TOPO), iterate over strongly
2198 connected components. */
2201 propagate_constants_topo (struct topo_info
*topo
)
2205 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
2208 struct cgraph_node
*v
, *node
= topo
->order
[i
];
2209 vec
<cgraph_node_ptr
> cycle_nodes
= ipa_get_nodes_in_cycle (node
);
2211 /* First, iteratively propagate within the strongly connected component
2212 until all lattices stabilize. */
2213 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
2214 if (cgraph_function_with_gimple_body_p (v
))
2215 push_node_to_stack (topo
, v
);
2217 v
= pop_node_from_stack (topo
);
2220 struct cgraph_edge
*cs
;
2222 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
2223 if (ipa_edge_within_scc (cs
)
2224 && propagate_constants_accross_call (cs
))
2225 push_node_to_stack (topo
, cs
->callee
);
2226 v
= pop_node_from_stack (topo
);
2229 /* Afterwards, propagate along edges leading out of the SCC, calculates
2230 the local effects of the discovered constants and all valid values to
2231 their topological sort. */
2232 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
2233 if (cgraph_function_with_gimple_body_p (v
))
2235 struct cgraph_edge
*cs
;
2237 estimate_local_effects (v
);
2238 add_all_node_vals_to_toposort (v
);
2239 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
2240 if (!ipa_edge_within_scc (cs
))
2241 propagate_constants_accross_call (cs
);
2243 cycle_nodes
.release ();
2248 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
2249 the bigger one if otherwise. */
2252 safe_add (int a
, int b
)
2254 if (a
> INT_MAX
/2 || b
> INT_MAX
/2)
2255 return a
> b
? a
: b
;
2261 /* Propagate the estimated effects of individual values along the topological
2262 from the dependent values to those they depend on. */
2265 propagate_effects (void)
2267 struct ipcp_value
*base
;
2269 for (base
= values_topo
; base
; base
= base
->topo_next
)
2271 struct ipcp_value_source
*src
;
2272 struct ipcp_value
*val
;
2273 int time
= 0, size
= 0;
2275 for (val
= base
; val
; val
= val
->scc_next
)
2277 time
= safe_add (time
,
2278 val
->local_time_benefit
+ val
->prop_time_benefit
);
2279 size
= safe_add (size
, val
->local_size_cost
+ val
->prop_size_cost
);
2282 for (val
= base
; val
; val
= val
->scc_next
)
2283 for (src
= val
->sources
; src
; src
= src
->next
)
2285 && cgraph_maybe_hot_edge_p (src
->cs
))
2287 src
->val
->prop_time_benefit
= safe_add (time
,
2288 src
->val
->prop_time_benefit
);
2289 src
->val
->prop_size_cost
= safe_add (size
,
2290 src
->val
->prop_size_cost
);
2296 /* Propagate constants, binfos and their effects from the summaries
2297 interprocedurally. */
2300 ipcp_propagate_stage (struct topo_info
*topo
)
2302 struct cgraph_node
*node
;
2305 fprintf (dump_file
, "\n Propagating constants:\n\n");
2308 ipa_update_after_lto_read ();
2311 FOR_EACH_DEFINED_FUNCTION (node
)
2313 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2315 determine_versionability (node
);
2316 if (cgraph_function_with_gimple_body_p (node
))
2318 info
->lattices
= XCNEWVEC (struct ipcp_param_lattices
,
2319 ipa_get_param_count (info
));
2320 initialize_node_lattices (node
);
2322 if (node
->definition
&& !node
->alias
)
2323 overall_size
+= inline_summary (node
)->self_size
;
2324 if (node
->count
> max_count
)
2325 max_count
= node
->count
;
2328 max_new_size
= overall_size
;
2329 if (max_new_size
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
2330 max_new_size
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
2331 max_new_size
+= max_new_size
* PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH
) / 100 + 1;
2334 fprintf (dump_file
, "\noverall_size: %li, max_new_size: %li\n",
2335 overall_size
, max_new_size
);
2337 propagate_constants_topo (topo
);
2338 #ifdef ENABLE_CHECKING
2339 ipcp_verify_propagated_values ();
2341 propagate_effects ();
2345 fprintf (dump_file
, "\nIPA lattices after all propagation:\n");
2346 print_all_lattices (dump_file
, (dump_flags
& TDF_DETAILS
), true);
2350 /* Discover newly direct outgoing edges from NODE which is a new clone with
2351 known KNOWN_VALS and make them direct. */
2354 ipcp_discover_new_direct_edges (struct cgraph_node
*node
,
2355 vec
<tree
> known_vals
,
2356 struct ipa_agg_replacement_value
*aggvals
)
2358 struct cgraph_edge
*ie
, *next_ie
;
2361 for (ie
= node
->indirect_calls
; ie
; ie
= next_ie
)
2365 next_ie
= ie
->next_callee
;
2366 target
= ipa_get_indirect_edge_target_1 (ie
, known_vals
, vNULL
, vNULL
,
2370 bool agg_contents
= ie
->indirect_info
->agg_contents
;
2371 bool polymorphic
= ie
->indirect_info
->polymorphic
;
2372 int param_index
= ie
->indirect_info
->param_index
;
2373 struct cgraph_edge
*cs
= ipa_make_edge_direct_to_target (ie
, target
);
2376 if (cs
&& !agg_contents
&& !polymorphic
)
2378 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2379 int c
= ipa_get_controlled_uses (info
, param_index
);
2380 if (c
!= IPA_UNDESCRIBED_USE
)
2382 struct ipa_ref
*to_del
;
2385 ipa_set_controlled_uses (info
, param_index
, c
);
2386 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2387 fprintf (dump_file
, " controlled uses count of param "
2388 "%i bumped down to %i\n", param_index
, c
);
2390 && (to_del
= node
->find_reference (cs
->callee
, NULL
, 0)))
2392 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2393 fprintf (dump_file
, " and even removing its "
2394 "cloning-created reference\n");
2395 to_del
->remove_reference ();
2401 /* Turning calls to direct calls will improve overall summary. */
2403 inline_update_overall_summary (node
);
2406 /* Vector of pointers which for linked lists of clones of an original crgaph
2409 static vec
<cgraph_edge_p
> next_edge_clone
;
2410 static vec
<cgraph_edge_p
> prev_edge_clone
;
2413 grow_edge_clone_vectors (void)
2415 if (next_edge_clone
.length ()
2416 <= (unsigned) cgraph_edge_max_uid
)
2417 next_edge_clone
.safe_grow_cleared (cgraph_edge_max_uid
+ 1);
2418 if (prev_edge_clone
.length ()
2419 <= (unsigned) cgraph_edge_max_uid
)
2420 prev_edge_clone
.safe_grow_cleared (cgraph_edge_max_uid
+ 1);
2423 /* Edge duplication hook to grow the appropriate linked list in
2427 ipcp_edge_duplication_hook (struct cgraph_edge
*src
, struct cgraph_edge
*dst
,
2430 grow_edge_clone_vectors ();
2432 struct cgraph_edge
*old_next
= next_edge_clone
[src
->uid
];
2434 prev_edge_clone
[old_next
->uid
] = dst
;
2435 prev_edge_clone
[dst
->uid
] = src
;
2437 next_edge_clone
[dst
->uid
] = old_next
;
2438 next_edge_clone
[src
->uid
] = dst
;
2441 /* Hook that is called by cgraph.c when an edge is removed. */
2444 ipcp_edge_removal_hook (struct cgraph_edge
*cs
, void *)
2446 grow_edge_clone_vectors ();
2448 struct cgraph_edge
*prev
= prev_edge_clone
[cs
->uid
];
2449 struct cgraph_edge
*next
= next_edge_clone
[cs
->uid
];
2451 next_edge_clone
[prev
->uid
] = next
;
2453 prev_edge_clone
[next
->uid
] = prev
;
2456 /* See if NODE is a clone with a known aggregate value at a given OFFSET of a
2457 parameter with the given INDEX. */
2460 get_clone_agg_value (struct cgraph_node
*node
, HOST_WIDE_INT offset
,
2463 struct ipa_agg_replacement_value
*aggval
;
2465 aggval
= ipa_get_agg_replacements_for_node (node
);
2468 if (aggval
->offset
== offset
2469 && aggval
->index
== index
)
2470 return aggval
->value
;
2471 aggval
= aggval
->next
;
2476 /* Return true if edge CS does bring about the value described by SRC. */
2479 cgraph_edge_brings_value_p (struct cgraph_edge
*cs
,
2480 struct ipcp_value_source
*src
)
2482 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2483 cgraph_node
*real_dest
= cgraph_function_node (cs
->callee
);
2484 struct ipa_node_params
*dst_info
= IPA_NODE_REF (real_dest
);
2486 if ((dst_info
->ipcp_orig_node
&& !dst_info
->is_all_contexts_clone
)
2487 || caller_info
->node_dead
)
2492 if (caller_info
->ipcp_orig_node
)
2495 if (src
->offset
== -1)
2496 t
= caller_info
->known_vals
[src
->index
];
2498 t
= get_clone_agg_value (cs
->caller
, src
->offset
, src
->index
);
2499 return (t
!= NULL_TREE
2500 && values_equal_for_ipcp_p (src
->val
->value
, t
));
2504 struct ipcp_agg_lattice
*aglat
;
2505 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
2507 if (src
->offset
== -1)
2508 return (ipa_lat_is_single_const (&plats
->itself
)
2509 && values_equal_for_ipcp_p (src
->val
->value
,
2510 plats
->itself
.values
->value
));
2513 if (plats
->aggs_bottom
|| plats
->aggs_contain_variable
)
2515 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2516 if (aglat
->offset
== src
->offset
)
2517 return (ipa_lat_is_single_const (aglat
)
2518 && values_equal_for_ipcp_p (src
->val
->value
,
2519 aglat
->values
->value
));
2525 /* Get the next clone in the linked list of clones of an edge. */
2527 static inline struct cgraph_edge
*
2528 get_next_cgraph_edge_clone (struct cgraph_edge
*cs
)
2530 return next_edge_clone
[cs
->uid
];
2533 /* Given VAL, iterate over all its sources and if they still hold, add their
2534 edge frequency and their number into *FREQUENCY and *CALLER_COUNT
2538 get_info_about_necessary_edges (struct ipcp_value
*val
, int *freq_sum
,
2539 gcov_type
*count_sum
, int *caller_count
)
2541 struct ipcp_value_source
*src
;
2542 int freq
= 0, count
= 0;
2546 for (src
= val
->sources
; src
; src
= src
->next
)
2548 struct cgraph_edge
*cs
= src
->cs
;
2551 if (cgraph_edge_brings_value_p (cs
, src
))
2554 freq
+= cs
->frequency
;
2556 hot
|= cgraph_maybe_hot_edge_p (cs
);
2558 cs
= get_next_cgraph_edge_clone (cs
);
2564 *caller_count
= count
;
2568 /* Return a vector of incoming edges that do bring value VAL. It is assumed
2569 their number is known and equal to CALLER_COUNT. */
2571 static vec
<cgraph_edge_p
>
2572 gather_edges_for_value (struct ipcp_value
*val
, int caller_count
)
2574 struct ipcp_value_source
*src
;
2575 vec
<cgraph_edge_p
> ret
;
2577 ret
.create (caller_count
);
2578 for (src
= val
->sources
; src
; src
= src
->next
)
2580 struct cgraph_edge
*cs
= src
->cs
;
2583 if (cgraph_edge_brings_value_p (cs
, src
))
2584 ret
.quick_push (cs
);
2585 cs
= get_next_cgraph_edge_clone (cs
);
2592 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
2593 Return it or NULL if for some reason it cannot be created. */
2595 static struct ipa_replace_map
*
2596 get_replacement_map (struct ipa_node_params
*info
, tree value
, int parm_num
)
2598 struct ipa_replace_map
*replace_map
;
2601 replace_map
= ggc_alloc
<ipa_replace_map
> ();
2604 fprintf (dump_file
, " replacing ");
2605 ipa_dump_param (dump_file
, info
, parm_num
);
2607 fprintf (dump_file
, " with const ");
2608 print_generic_expr (dump_file
, value
, 0);
2609 fprintf (dump_file
, "\n");
2611 replace_map
->old_tree
= NULL
;
2612 replace_map
->parm_num
= parm_num
;
2613 replace_map
->new_tree
= value
;
2614 replace_map
->replace_p
= true;
2615 replace_map
->ref_p
= false;
2620 /* Dump new profiling counts */
2623 dump_profile_updates (struct cgraph_node
*orig_node
,
2624 struct cgraph_node
*new_node
)
2626 struct cgraph_edge
*cs
;
2628 fprintf (dump_file
, " setting count of the specialized node to "
2629 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) new_node
->count
);
2630 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
2631 fprintf (dump_file
, " edge to %s has count "
2632 HOST_WIDE_INT_PRINT_DEC
"\n",
2633 cs
->callee
->name (), (HOST_WIDE_INT
) cs
->count
);
2635 fprintf (dump_file
, " setting count of the original node to "
2636 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) orig_node
->count
);
2637 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
2638 fprintf (dump_file
, " edge to %s is left with "
2639 HOST_WIDE_INT_PRINT_DEC
"\n",
2640 cs
->callee
->name (), (HOST_WIDE_INT
) cs
->count
);
2643 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
2644 their profile information to reflect this. */
2647 update_profiling_info (struct cgraph_node
*orig_node
,
2648 struct cgraph_node
*new_node
)
2650 struct cgraph_edge
*cs
;
2651 struct caller_statistics stats
;
2652 gcov_type new_sum
, orig_sum
;
2653 gcov_type remainder
, orig_node_count
= orig_node
->count
;
2655 if (orig_node_count
== 0)
2658 init_caller_stats (&stats
);
2659 cgraph_for_node_and_aliases (orig_node
, gather_caller_stats
, &stats
, false);
2660 orig_sum
= stats
.count_sum
;
2661 init_caller_stats (&stats
);
2662 cgraph_for_node_and_aliases (new_node
, gather_caller_stats
, &stats
, false);
2663 new_sum
= stats
.count_sum
;
2665 if (orig_node_count
< orig_sum
+ new_sum
)
2668 fprintf (dump_file
, " Problem: node %s/%i has too low count "
2669 HOST_WIDE_INT_PRINT_DEC
" while the sum of incoming "
2670 "counts is " HOST_WIDE_INT_PRINT_DEC
"\n",
2671 orig_node
->name (), orig_node
->order
,
2672 (HOST_WIDE_INT
) orig_node_count
,
2673 (HOST_WIDE_INT
) (orig_sum
+ new_sum
));
2675 orig_node_count
= (orig_sum
+ new_sum
) * 12 / 10;
2677 fprintf (dump_file
, " proceeding by pretending it was "
2678 HOST_WIDE_INT_PRINT_DEC
"\n",
2679 (HOST_WIDE_INT
) orig_node_count
);
2682 new_node
->count
= new_sum
;
2683 remainder
= orig_node_count
- new_sum
;
2684 orig_node
->count
= remainder
;
2686 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
2688 cs
->count
= apply_probability (cs
->count
,
2689 GCOV_COMPUTE_SCALE (new_sum
,
2694 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
2695 cs
->count
= apply_probability (cs
->count
,
2696 GCOV_COMPUTE_SCALE (remainder
,
2700 dump_profile_updates (orig_node
, new_node
);
2703 /* Update the respective profile of specialized NEW_NODE and the original
2704 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
2705 have been redirected to the specialized version. */
2708 update_specialized_profile (struct cgraph_node
*new_node
,
2709 struct cgraph_node
*orig_node
,
2710 gcov_type redirected_sum
)
2712 struct cgraph_edge
*cs
;
2713 gcov_type new_node_count
, orig_node_count
= orig_node
->count
;
2716 fprintf (dump_file
, " the sum of counts of redirected edges is "
2717 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) redirected_sum
);
2718 if (orig_node_count
== 0)
2721 gcc_assert (orig_node_count
>= redirected_sum
);
2723 new_node_count
= new_node
->count
;
2724 new_node
->count
+= redirected_sum
;
2725 orig_node
->count
-= redirected_sum
;
2727 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
2729 cs
->count
+= apply_probability (cs
->count
,
2730 GCOV_COMPUTE_SCALE (redirected_sum
,
2735 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
2737 gcov_type dec
= apply_probability (cs
->count
,
2738 GCOV_COMPUTE_SCALE (redirected_sum
,
2740 if (dec
< cs
->count
)
2747 dump_profile_updates (orig_node
, new_node
);
2750 /* Create a specialized version of NODE with known constants and types of
2751 parameters in KNOWN_VALS and redirect all edges in CALLERS to it. */
2753 static struct cgraph_node
*
2754 create_specialized_node (struct cgraph_node
*node
,
2755 vec
<tree
> known_vals
,
2756 struct ipa_agg_replacement_value
*aggvals
,
2757 vec
<cgraph_edge_p
> callers
)
2759 struct ipa_node_params
*new_info
, *info
= IPA_NODE_REF (node
);
2760 vec
<ipa_replace_map_p
, va_gc
> *replace_trees
= NULL
;
2761 struct ipa_agg_replacement_value
*av
;
2762 struct cgraph_node
*new_node
;
2763 int i
, count
= ipa_get_param_count (info
);
2764 bitmap args_to_skip
;
2766 gcc_assert (!info
->ipcp_orig_node
);
2768 if (node
->local
.can_change_signature
)
2770 args_to_skip
= BITMAP_GGC_ALLOC ();
2771 for (i
= 0; i
< count
; i
++)
2773 tree t
= known_vals
[i
];
2775 if ((t
&& TREE_CODE (t
) != TREE_BINFO
)
2776 || !ipa_is_param_used (info
, i
))
2777 bitmap_set_bit (args_to_skip
, i
);
2782 args_to_skip
= NULL
;
2783 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2784 fprintf (dump_file
, " cannot change function signature\n");
2787 for (i
= 0; i
< count
; i
++)
2789 tree t
= known_vals
[i
];
2790 if (t
&& TREE_CODE (t
) != TREE_BINFO
)
2792 struct ipa_replace_map
*replace_map
;
2794 replace_map
= get_replacement_map (info
, t
, i
);
2796 vec_safe_push (replace_trees
, replace_map
);
2800 new_node
= cgraph_create_virtual_clone (node
, callers
, replace_trees
,
2801 args_to_skip
, "constprop");
2802 ipa_set_node_agg_value_chain (new_node
, aggvals
);
2803 for (av
= aggvals
; av
; av
= av
->next
)
2804 new_node
->maybe_add_reference (av
->value
, IPA_REF_ADDR
, NULL
);
2806 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2808 fprintf (dump_file
, " the new node is %s/%i.\n",
2809 new_node
->name (), new_node
->order
);
2811 ipa_dump_agg_replacement_values (dump_file
, aggvals
);
2813 ipa_check_create_node_params ();
2814 update_profiling_info (node
, new_node
);
2815 new_info
= IPA_NODE_REF (new_node
);
2816 new_info
->ipcp_orig_node
= node
;
2817 new_info
->known_vals
= known_vals
;
2819 ipcp_discover_new_direct_edges (new_node
, known_vals
, aggvals
);
2825 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
2826 KNOWN_VALS with constants and types that are also known for all of the
2830 find_more_scalar_values_for_callers_subset (struct cgraph_node
*node
,
2831 vec
<tree
> known_vals
,
2832 vec
<cgraph_edge_p
> callers
)
2834 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2835 int i
, count
= ipa_get_param_count (info
);
2837 for (i
= 0; i
< count
; i
++)
2839 struct cgraph_edge
*cs
;
2840 tree newval
= NULL_TREE
;
2843 if (ipa_get_scalar_lat (info
, i
)->bottom
|| known_vals
[i
])
2846 FOR_EACH_VEC_ELT (callers
, j
, cs
)
2848 struct ipa_jump_func
*jump_func
;
2851 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
)))
2856 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
2857 t
= ipa_value_from_jfunc (IPA_NODE_REF (cs
->caller
), jump_func
);
2860 && !values_equal_for_ipcp_p (t
, newval
)))
2871 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2873 fprintf (dump_file
, " adding an extra known scalar value ");
2874 print_ipcp_constant_value (dump_file
, newval
);
2875 fprintf (dump_file
, " for ");
2876 ipa_dump_param (dump_file
, info
, i
);
2877 fprintf (dump_file
, "\n");
2880 known_vals
[i
] = newval
;
2885 /* Go through PLATS and create a vector of values consisting of values and
2886 offsets (minus OFFSET) of lattices that contain only a single value. */
2888 static vec
<ipa_agg_jf_item
>
2889 copy_plats_to_inter (struct ipcp_param_lattices
*plats
, HOST_WIDE_INT offset
)
2891 vec
<ipa_agg_jf_item
> res
= vNULL
;
2893 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
2896 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2897 if (ipa_lat_is_single_const (aglat
))
2899 struct ipa_agg_jf_item ti
;
2900 ti
.offset
= aglat
->offset
- offset
;
2901 ti
.value
= aglat
->values
->value
;
2907 /* Intersect all values in INTER with single value lattices in PLATS (while
2908 subtracting OFFSET). */
2911 intersect_with_plats (struct ipcp_param_lattices
*plats
,
2912 vec
<ipa_agg_jf_item
> *inter
,
2913 HOST_WIDE_INT offset
)
2915 struct ipcp_agg_lattice
*aglat
;
2916 struct ipa_agg_jf_item
*item
;
2919 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
2925 aglat
= plats
->aggs
;
2926 FOR_EACH_VEC_ELT (*inter
, k
, item
)
2933 if (aglat
->offset
- offset
> item
->offset
)
2935 if (aglat
->offset
- offset
== item
->offset
)
2937 gcc_checking_assert (item
->value
);
2938 if (values_equal_for_ipcp_p (item
->value
, aglat
->values
->value
))
2942 aglat
= aglat
->next
;
2945 item
->value
= NULL_TREE
;
2949 /* Copy agggregate replacement values of NODE (which is an IPA-CP clone) to the
2950 vector result while subtracting OFFSET from the individual value offsets. */
2952 static vec
<ipa_agg_jf_item
>
2953 agg_replacements_to_vector (struct cgraph_node
*node
, int index
,
2954 HOST_WIDE_INT offset
)
2956 struct ipa_agg_replacement_value
*av
;
2957 vec
<ipa_agg_jf_item
> res
= vNULL
;
2959 for (av
= ipa_get_agg_replacements_for_node (node
); av
; av
= av
->next
)
2960 if (av
->index
== index
2961 && (av
->offset
- offset
) >= 0)
2963 struct ipa_agg_jf_item item
;
2964 gcc_checking_assert (av
->value
);
2965 item
.offset
= av
->offset
- offset
;
2966 item
.value
= av
->value
;
2967 res
.safe_push (item
);
2973 /* Intersect all values in INTER with those that we have already scheduled to
2974 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
2975 (while subtracting OFFSET). */
2978 intersect_with_agg_replacements (struct cgraph_node
*node
, int index
,
2979 vec
<ipa_agg_jf_item
> *inter
,
2980 HOST_WIDE_INT offset
)
2982 struct ipa_agg_replacement_value
*srcvals
;
2983 struct ipa_agg_jf_item
*item
;
2986 srcvals
= ipa_get_agg_replacements_for_node (node
);
2993 FOR_EACH_VEC_ELT (*inter
, i
, item
)
2995 struct ipa_agg_replacement_value
*av
;
2999 for (av
= srcvals
; av
; av
= av
->next
)
3001 gcc_checking_assert (av
->value
);
3002 if (av
->index
== index
3003 && av
->offset
- offset
== item
->offset
)
3005 if (values_equal_for_ipcp_p (item
->value
, av
->value
))
3011 item
->value
= NULL_TREE
;
3015 /* Intersect values in INTER with aggregate values that come along edge CS to
3016 parameter number INDEX and return it. If INTER does not actually exist yet,
3017 copy all incoming values to it. If we determine we ended up with no values
3018 whatsoever, return a released vector. */
3020 static vec
<ipa_agg_jf_item
>
3021 intersect_aggregates_with_edge (struct cgraph_edge
*cs
, int index
,
3022 vec
<ipa_agg_jf_item
> inter
)
3024 struct ipa_jump_func
*jfunc
;
3025 jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), index
);
3026 if (jfunc
->type
== IPA_JF_PASS_THROUGH
3027 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
3029 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3030 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
3032 if (caller_info
->ipcp_orig_node
)
3034 struct cgraph_node
*orig_node
= caller_info
->ipcp_orig_node
;
3035 struct ipcp_param_lattices
*orig_plats
;
3036 orig_plats
= ipa_get_parm_lattices (IPA_NODE_REF (orig_node
),
3038 if (agg_pass_through_permissible_p (orig_plats
, jfunc
))
3040 if (!inter
.exists ())
3041 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, 0);
3043 intersect_with_agg_replacements (cs
->caller
, src_idx
,
3049 struct ipcp_param_lattices
*src_plats
;
3050 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
3051 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
3053 /* Currently we do not produce clobber aggregate jump
3054 functions, adjust when we do. */
3055 gcc_checking_assert (!jfunc
->agg
.items
);
3056 if (!inter
.exists ())
3057 inter
= copy_plats_to_inter (src_plats
, 0);
3059 intersect_with_plats (src_plats
, &inter
, 0);
3063 else if (jfunc
->type
== IPA_JF_ANCESTOR
3064 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
3066 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3067 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
3068 struct ipcp_param_lattices
*src_plats
;
3069 HOST_WIDE_INT delta
= ipa_get_jf_ancestor_offset (jfunc
);
3071 if (caller_info
->ipcp_orig_node
)
3073 if (!inter
.exists ())
3074 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, delta
);
3076 intersect_with_agg_replacements (cs
->caller
, src_idx
, &inter
,
3081 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);;
3082 /* Currently we do not produce clobber aggregate jump
3083 functions, adjust when we do. */
3084 gcc_checking_assert (!src_plats
->aggs
|| !jfunc
->agg
.items
);
3085 if (!inter
.exists ())
3086 inter
= copy_plats_to_inter (src_plats
, delta
);
3088 intersect_with_plats (src_plats
, &inter
, delta
);
3091 else if (jfunc
->agg
.items
)
3093 struct ipa_agg_jf_item
*item
;
3096 if (!inter
.exists ())
3097 for (unsigned i
= 0; i
< jfunc
->agg
.items
->length (); i
++)
3098 inter
.safe_push ((*jfunc
->agg
.items
)[i
]);
3100 FOR_EACH_VEC_ELT (inter
, k
, item
)
3103 bool found
= false;;
3108 while ((unsigned) l
< jfunc
->agg
.items
->length ())
3110 struct ipa_agg_jf_item
*ti
;
3111 ti
= &(*jfunc
->agg
.items
)[l
];
3112 if (ti
->offset
> item
->offset
)
3114 if (ti
->offset
== item
->offset
)
3116 gcc_checking_assert (ti
->value
);
3117 if (values_equal_for_ipcp_p (item
->value
,
3131 return vec
<ipa_agg_jf_item
>();
3136 /* Look at edges in CALLERS and collect all known aggregate values that arrive
3137 from all of them. */
3139 static struct ipa_agg_replacement_value
*
3140 find_aggregate_values_for_callers_subset (struct cgraph_node
*node
,
3141 vec
<cgraph_edge_p
> callers
)
3143 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
3144 struct ipa_agg_replacement_value
*res
= NULL
;
3145 struct cgraph_edge
*cs
;
3146 int i
, j
, count
= ipa_get_param_count (dest_info
);
3148 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3150 int c
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
3155 for (i
= 0; i
< count
; i
++)
3157 struct cgraph_edge
*cs
;
3158 vec
<ipa_agg_jf_item
> inter
= vNULL
;
3159 struct ipa_agg_jf_item
*item
;
3160 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (dest_info
, i
);
3163 /* Among other things, the following check should deal with all by_ref
3165 if (plats
->aggs_bottom
)
3168 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3170 inter
= intersect_aggregates_with_edge (cs
, i
, inter
);
3172 if (!inter
.exists ())
3176 FOR_EACH_VEC_ELT (inter
, j
, item
)
3178 struct ipa_agg_replacement_value
*v
;
3183 v
= ggc_alloc
<ipa_agg_replacement_value
> ();
3185 v
->offset
= item
->offset
;
3186 v
->value
= item
->value
;
3187 v
->by_ref
= plats
->aggs_by_ref
;
3193 if (inter
.exists ())
3199 /* Turn KNOWN_AGGS into a list of aggreate replacement values. */
3201 static struct ipa_agg_replacement_value
*
3202 known_aggs_to_agg_replacement_list (vec
<ipa_agg_jump_function
> known_aggs
)
3204 struct ipa_agg_replacement_value
*res
= NULL
;
3205 struct ipa_agg_jump_function
*aggjf
;
3206 struct ipa_agg_jf_item
*item
;
3209 FOR_EACH_VEC_ELT (known_aggs
, i
, aggjf
)
3210 FOR_EACH_VEC_SAFE_ELT (aggjf
->items
, j
, item
)
3212 struct ipa_agg_replacement_value
*v
;
3213 v
= ggc_alloc
<ipa_agg_replacement_value
> ();
3215 v
->offset
= item
->offset
;
3216 v
->value
= item
->value
;
3217 v
->by_ref
= aggjf
->by_ref
;
3224 /* Determine whether CS also brings all scalar values that the NODE is
3228 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge
*cs
,
3229 struct cgraph_node
*node
)
3231 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
3232 int count
= ipa_get_param_count (dest_info
);
3233 struct ipa_node_params
*caller_info
;
3234 struct ipa_edge_args
*args
;
3237 caller_info
= IPA_NODE_REF (cs
->caller
);
3238 args
= IPA_EDGE_REF (cs
);
3239 for (i
= 0; i
< count
; i
++)
3241 struct ipa_jump_func
*jump_func
;
3244 val
= dest_info
->known_vals
[i
];
3248 if (i
>= ipa_get_cs_argument_count (args
))
3250 jump_func
= ipa_get_ith_jump_func (args
, i
);
3251 t
= ipa_value_from_jfunc (caller_info
, jump_func
);
3252 if (!t
|| !values_equal_for_ipcp_p (val
, t
))
3258 /* Determine whether CS also brings all aggregate values that NODE is
3261 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge
*cs
,
3262 struct cgraph_node
*node
)
3264 struct ipa_node_params
*orig_caller_info
= IPA_NODE_REF (cs
->caller
);
3265 struct ipa_node_params
*orig_node_info
;
3266 struct ipa_agg_replacement_value
*aggval
;
3269 aggval
= ipa_get_agg_replacements_for_node (node
);
3273 count
= ipa_get_param_count (IPA_NODE_REF (node
));
3274 ec
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
3276 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
3277 if (aggval
->index
>= ec
)
3280 orig_node_info
= IPA_NODE_REF (IPA_NODE_REF (node
)->ipcp_orig_node
);
3281 if (orig_caller_info
->ipcp_orig_node
)
3282 orig_caller_info
= IPA_NODE_REF (orig_caller_info
->ipcp_orig_node
);
3284 for (i
= 0; i
< count
; i
++)
3286 static vec
<ipa_agg_jf_item
> values
= vec
<ipa_agg_jf_item
>();
3287 struct ipcp_param_lattices
*plats
;
3288 bool interesting
= false;
3289 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
3290 if (aggval
->index
== i
)
3298 plats
= ipa_get_parm_lattices (orig_node_info
, aggval
->index
);
3299 if (plats
->aggs_bottom
)
3302 values
= intersect_aggregates_with_edge (cs
, i
, values
);
3303 if (!values
.exists ())
3306 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
3307 if (aggval
->index
== i
)
3309 struct ipa_agg_jf_item
*item
;
3312 FOR_EACH_VEC_ELT (values
, j
, item
)
3314 && item
->offset
== av
->offset
3315 && values_equal_for_ipcp_p (item
->value
, av
->value
))
3330 /* Given an original NODE and a VAL for which we have already created a
3331 specialized clone, look whether there are incoming edges that still lead
3332 into the old node but now also bring the requested value and also conform to
3333 all other criteria such that they can be redirected the the special node.
3334 This function can therefore redirect the final edge in a SCC. */
3337 perhaps_add_new_callers (struct cgraph_node
*node
, struct ipcp_value
*val
)
3339 struct ipcp_value_source
*src
;
3340 gcov_type redirected_sum
= 0;
3342 for (src
= val
->sources
; src
; src
= src
->next
)
3344 struct cgraph_edge
*cs
= src
->cs
;
3347 enum availability availability
;
3348 struct cgraph_node
*dst
= cgraph_function_node (cs
->callee
,
3350 if ((dst
== node
|| IPA_NODE_REF (dst
)->is_all_contexts_clone
)
3351 && availability
> AVAIL_OVERWRITABLE
3352 && cgraph_edge_brings_value_p (cs
, src
))
3354 if (cgraph_edge_brings_all_scalars_for_node (cs
, val
->spec_node
)
3355 && cgraph_edge_brings_all_agg_vals_for_node (cs
,
3359 fprintf (dump_file
, " - adding an extra caller %s/%i"
3361 xstrdup (cs
->caller
->name ()),
3363 xstrdup (val
->spec_node
->name ()),
3364 val
->spec_node
->order
);
3366 cgraph_redirect_edge_callee (cs
, val
->spec_node
);
3367 redirected_sum
+= cs
->count
;
3370 cs
= get_next_cgraph_edge_clone (cs
);
3375 update_specialized_profile (val
->spec_node
, node
, redirected_sum
);
3379 /* Copy KNOWN_BINFOS to KNOWN_VALS. */
3382 move_binfos_to_values (vec
<tree
> known_vals
,
3383 vec
<tree
> known_binfos
)
3388 for (i
= 0; known_binfos
.iterate (i
, &t
); i
++)
3393 /* Return true if there is a replacement equivalent to VALUE, INDEX and OFFSET
3394 among those in the AGGVALS list. */
3397 ipcp_val_in_agg_replacements_p (struct ipa_agg_replacement_value
*aggvals
,
3398 int index
, HOST_WIDE_INT offset
, tree value
)
3402 if (aggvals
->index
== index
3403 && aggvals
->offset
== offset
3404 && values_equal_for_ipcp_p (aggvals
->value
, value
))
3406 aggvals
= aggvals
->next
;
3411 /* Decide wheter to create a special version of NODE for value VAL of parameter
3412 at the given INDEX. If OFFSET is -1, the value is for the parameter itself,
3413 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS,
3414 KNOWN_BINFOS and KNOWN_AGGS describe the other already known values. */
3417 decide_about_value (struct cgraph_node
*node
, int index
, HOST_WIDE_INT offset
,
3418 struct ipcp_value
*val
, vec
<tree
> known_csts
,
3419 vec
<tree
> known_binfos
)
3421 struct ipa_agg_replacement_value
*aggvals
;
3422 int freq_sum
, caller_count
;
3423 gcov_type count_sum
;
3424 vec
<cgraph_edge_p
> callers
;
3429 perhaps_add_new_callers (node
, val
);
3432 else if (val
->local_size_cost
+ overall_size
> max_new_size
)
3434 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3435 fprintf (dump_file
, " Ignoring candidate value because "
3436 "max_new_size would be reached with %li.\n",
3437 val
->local_size_cost
+ overall_size
);
3440 else if (!get_info_about_necessary_edges (val
, &freq_sum
, &count_sum
,
3444 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3446 fprintf (dump_file
, " - considering value ");
3447 print_ipcp_constant_value (dump_file
, val
->value
);
3448 fprintf (dump_file
, " for ");
3449 ipa_dump_param (dump_file
, IPA_NODE_REF (node
), index
);
3451 fprintf (dump_file
, ", offset: " HOST_WIDE_INT_PRINT_DEC
, offset
);
3452 fprintf (dump_file
, " (caller_count: %i)\n", caller_count
);
3455 if (!good_cloning_opportunity_p (node
, val
->local_time_benefit
,
3456 freq_sum
, count_sum
,
3457 val
->local_size_cost
)
3458 && !good_cloning_opportunity_p (node
,
3459 val
->local_time_benefit
3460 + val
->prop_time_benefit
,
3461 freq_sum
, count_sum
,
3462 val
->local_size_cost
3463 + val
->prop_size_cost
))
3467 fprintf (dump_file
, " Creating a specialized node of %s/%i.\n",
3468 node
->name (), node
->order
);
3470 callers
= gather_edges_for_value (val
, caller_count
);
3471 kv
= known_csts
.copy ();
3472 move_binfos_to_values (kv
, known_binfos
);
3474 kv
[index
] = val
->value
;
3475 find_more_scalar_values_for_callers_subset (node
, kv
, callers
);
3476 aggvals
= find_aggregate_values_for_callers_subset (node
, callers
);
3477 gcc_checking_assert (offset
== -1
3478 || ipcp_val_in_agg_replacements_p (aggvals
, index
,
3479 offset
, val
->value
));
3480 val
->spec_node
= create_specialized_node (node
, kv
, aggvals
, callers
);
3481 overall_size
+= val
->local_size_cost
;
3483 /* TODO: If for some lattice there is only one other known value
3484 left, make a special node for it too. */
3489 /* Decide whether and what specialized clones of NODE should be created. */
3492 decide_whether_version_node (struct cgraph_node
*node
)
3494 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3495 int i
, count
= ipa_get_param_count (info
);
3496 vec
<tree
> known_csts
, known_binfos
;
3497 vec
<ipa_agg_jump_function
> known_aggs
= vNULL
;
3503 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3504 fprintf (dump_file
, "\nEvaluating opportunities for %s/%i.\n",
3505 node
->name (), node
->order
);
3507 gather_context_independent_values (info
, &known_csts
, &known_binfos
,
3508 info
->do_clone_for_all_contexts
? &known_aggs
3511 for (i
= 0; i
< count
;i
++)
3513 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3514 struct ipcp_lattice
*lat
= &plats
->itself
;
3515 struct ipcp_value
*val
;
3519 && !known_binfos
[i
])
3520 for (val
= lat
->values
; val
; val
= val
->next
)
3521 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
3524 if (!plats
->aggs_bottom
)
3526 struct ipcp_agg_lattice
*aglat
;
3527 struct ipcp_value
*val
;
3528 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3529 if (!aglat
->bottom
&& aglat
->values
3530 /* If the following is false, the one value is in
3532 && (plats
->aggs_contain_variable
3533 || !ipa_lat_is_single_const (aglat
)))
3534 for (val
= aglat
->values
; val
; val
= val
->next
)
3535 ret
|= decide_about_value (node
, i
, aglat
->offset
, val
,
3536 known_csts
, known_binfos
);
3538 info
= IPA_NODE_REF (node
);
3541 if (info
->do_clone_for_all_contexts
)
3543 struct cgraph_node
*clone
;
3544 vec
<cgraph_edge_p
> callers
;
3547 fprintf (dump_file
, " - Creating a specialized node of %s/%i "
3548 "for all known contexts.\n", node
->name (),
3551 callers
= collect_callers_of_node (node
);
3552 move_binfos_to_values (known_csts
, known_binfos
);
3553 clone
= create_specialized_node (node
, known_csts
,
3554 known_aggs_to_agg_replacement_list (known_aggs
),
3556 info
= IPA_NODE_REF (node
);
3557 info
->do_clone_for_all_contexts
= false;
3558 IPA_NODE_REF (clone
)->is_all_contexts_clone
= true;
3559 for (i
= 0; i
< count
; i
++)
3560 vec_free (known_aggs
[i
].items
);
3561 known_aggs
.release ();
3565 known_csts
.release ();
3567 known_binfos
.release ();
3571 /* Transitively mark all callees of NODE within the same SCC as not dead. */
3574 spread_undeadness (struct cgraph_node
*node
)
3576 struct cgraph_edge
*cs
;
3578 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
3579 if (ipa_edge_within_scc (cs
))
3581 struct cgraph_node
*callee
;
3582 struct ipa_node_params
*info
;
3584 callee
= cgraph_function_node (cs
->callee
, NULL
);
3585 info
= IPA_NODE_REF (callee
);
3587 if (info
->node_dead
)
3589 info
->node_dead
= 0;
3590 spread_undeadness (callee
);
3595 /* Return true if NODE has a caller from outside of its SCC that is not
3596 dead. Worker callback for cgraph_for_node_and_aliases. */
3599 has_undead_caller_from_outside_scc_p (struct cgraph_node
*node
,
3600 void *data ATTRIBUTE_UNUSED
)
3602 struct cgraph_edge
*cs
;
3604 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
3605 if (cs
->caller
->thunk
.thunk_p
3606 && cgraph_for_node_and_aliases (cs
->caller
,
3607 has_undead_caller_from_outside_scc_p
,
3610 else if (!ipa_edge_within_scc (cs
)
3611 && !IPA_NODE_REF (cs
->caller
)->node_dead
)
3617 /* Identify nodes within the same SCC as NODE which are no longer needed
3618 because of new clones and will be removed as unreachable. */
3621 identify_dead_nodes (struct cgraph_node
*node
)
3623 struct cgraph_node
*v
;
3624 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
3625 if (cgraph_will_be_removed_from_program_if_no_direct_calls (v
)
3626 && !cgraph_for_node_and_aliases (v
,
3627 has_undead_caller_from_outside_scc_p
,
3629 IPA_NODE_REF (v
)->node_dead
= 1;
3631 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
3632 if (!IPA_NODE_REF (v
)->node_dead
)
3633 spread_undeadness (v
);
3635 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3637 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
3638 if (IPA_NODE_REF (v
)->node_dead
)
3639 fprintf (dump_file
, " Marking node as dead: %s/%i.\n",
3640 v
->name (), v
->order
);
3644 /* The decision stage. Iterate over the topological order of call graph nodes
3645 TOPO and make specialized clones if deemed beneficial. */
3648 ipcp_decision_stage (struct topo_info
*topo
)
3653 fprintf (dump_file
, "\nIPA decision stage:\n\n");
3655 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
3657 struct cgraph_node
*node
= topo
->order
[i
];
3658 bool change
= false, iterate
= true;
3662 struct cgraph_node
*v
;
3664 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
3665 if (cgraph_function_with_gimple_body_p (v
)
3666 && ipcp_versionable_function_p (v
))
3667 iterate
|= decide_whether_version_node (v
);
3672 identify_dead_nodes (node
);
3676 /* The IPCP driver. */
3681 struct cgraph_2edge_hook_list
*edge_duplication_hook_holder
;
3682 struct cgraph_edge_hook_list
*edge_removal_hook_holder
;
3683 struct topo_info topo
;
3685 ipa_check_create_node_params ();
3686 ipa_check_create_edge_args ();
3687 grow_edge_clone_vectors ();
3688 edge_duplication_hook_holder
=
3689 cgraph_add_edge_duplication_hook (&ipcp_edge_duplication_hook
, NULL
);
3690 edge_removal_hook_holder
=
3691 cgraph_add_edge_removal_hook (&ipcp_edge_removal_hook
, NULL
);
3693 ipcp_values_pool
= create_alloc_pool ("IPA-CP values",
3694 sizeof (struct ipcp_value
), 32);
3695 ipcp_sources_pool
= create_alloc_pool ("IPA-CP value sources",
3696 sizeof (struct ipcp_value_source
), 64);
3697 ipcp_agg_lattice_pool
= create_alloc_pool ("IPA_CP aggregate lattices",
3698 sizeof (struct ipcp_agg_lattice
),
3702 fprintf (dump_file
, "\nIPA structures before propagation:\n");
3703 if (dump_flags
& TDF_DETAILS
)
3704 ipa_print_all_params (dump_file
);
3705 ipa_print_all_jump_functions (dump_file
);
3708 /* Topological sort. */
3709 build_toporder_info (&topo
);
3710 /* Do the interprocedural propagation. */
3711 ipcp_propagate_stage (&topo
);
3712 /* Decide what constant propagation and cloning should be performed. */
3713 ipcp_decision_stage (&topo
);
3715 /* Free all IPCP structures. */
3716 free_toporder_info (&topo
);
3717 next_edge_clone
.release ();
3718 cgraph_remove_edge_removal_hook (edge_removal_hook_holder
);
3719 cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder
);
3720 ipa_free_all_structures_after_ipa_cp ();
3722 fprintf (dump_file
, "\nIPA constant propagation end\n");
3726 /* Initialization and computation of IPCP data structures. This is the initial
3727 intraprocedural analysis of functions, which gathers information to be
3728 propagated later on. */
3731 ipcp_generate_summary (void)
3733 struct cgraph_node
*node
;
3736 fprintf (dump_file
, "\nIPA constant propagation start:\n");
3737 ipa_register_cgraph_hooks ();
3739 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
3741 node
->local
.versionable
3742 = tree_versionable_function_p (node
->decl
);
3743 ipa_analyze_node (node
);
3747 /* Write ipcp summary for nodes in SET. */
3750 ipcp_write_summary (void)
3752 ipa_prop_write_jump_functions ();
3755 /* Read ipcp summary. */
3758 ipcp_read_summary (void)
3760 ipa_prop_read_jump_functions ();
3765 const pass_data pass_data_ipa_cp
=
3767 IPA_PASS
, /* type */
3769 OPTGROUP_NONE
, /* optinfo_flags */
3770 true, /* has_execute */
3771 TV_IPA_CONSTANT_PROP
, /* tv_id */
3772 0, /* properties_required */
3773 0, /* properties_provided */
3774 0, /* properties_destroyed */
3775 0, /* todo_flags_start */
3776 ( TODO_dump_symtab
| TODO_remove_functions
), /* todo_flags_finish */
3779 class pass_ipa_cp
: public ipa_opt_pass_d
3782 pass_ipa_cp (gcc::context
*ctxt
)
3783 : ipa_opt_pass_d (pass_data_ipa_cp
, ctxt
,
3784 ipcp_generate_summary
, /* generate_summary */
3785 ipcp_write_summary
, /* write_summary */
3786 ipcp_read_summary
, /* read_summary */
3787 ipa_prop_write_all_agg_replacement
, /*
3788 write_optimization_summary */
3789 ipa_prop_read_all_agg_replacement
, /*
3790 read_optimization_summary */
3791 NULL
, /* stmt_fixup */
3792 0, /* function_transform_todo_flags_start */
3793 ipcp_transform_function
, /* function_transform */
3794 NULL
) /* variable_transform */
3797 /* opt_pass methods: */
3798 virtual bool gate (function
*)
3800 /* FIXME: We should remove the optimize check after we ensure we never run
3801 IPA passes when not optimizing. */
3802 return flag_ipa_cp
&& optimize
;
3805 virtual unsigned int execute (function
*) { return ipcp_driver (); }
3807 }; // class pass_ipa_cp
3812 make_pass_ipa_cp (gcc::context
*ctxt
)
3814 return new pass_ipa_cp (ctxt
);