1 /* Interprocedural constant propagation
2 Copyright (C) 2005-2013 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 (lookup_attribute ("omp declare simd", DECL_ATTRIBUTES (node
->decl
)))
435 /* Ideally we should clone the SIMD clones themselves and create
436 vector copies of them, so IPA-cp and SIMD clones can happily
437 coexist, but that may not be worth the effort. */
438 reason
= "function has SIMD clones";
441 if (reason
&& dump_file
&& !node
->alias
&& !node
->thunk
.thunk_p
)
442 fprintf (dump_file
, "Function %s/%i is not versionable, reason: %s.\n",
443 node
->name (), node
->order
, reason
);
445 node
->local
.versionable
= (reason
== NULL
);
448 /* Return true if it is at all technically possible to create clones of a
452 ipcp_versionable_function_p (struct cgraph_node
*node
)
454 return node
->local
.versionable
;
457 /* Structure holding accumulated information about callers of a node. */
459 struct caller_statistics
462 int n_calls
, n_hot_calls
, freq_sum
;
465 /* Initialize fields of STAT to zeroes. */
468 init_caller_stats (struct caller_statistics
*stats
)
470 stats
->count_sum
= 0;
472 stats
->n_hot_calls
= 0;
476 /* Worker callback of cgraph_for_node_and_aliases accumulating statistics of
477 non-thunk incoming edges to NODE. */
480 gather_caller_stats (struct cgraph_node
*node
, void *data
)
482 struct caller_statistics
*stats
= (struct caller_statistics
*) data
;
483 struct cgraph_edge
*cs
;
485 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
486 if (cs
->caller
->thunk
.thunk_p
)
487 cgraph_for_node_and_aliases (cs
->caller
, gather_caller_stats
,
491 stats
->count_sum
+= cs
->count
;
492 stats
->freq_sum
+= cs
->frequency
;
494 if (cgraph_maybe_hot_edge_p (cs
))
495 stats
->n_hot_calls
++;
501 /* Return true if this NODE is viable candidate for cloning. */
504 ipcp_cloning_candidate_p (struct cgraph_node
*node
)
506 struct caller_statistics stats
;
508 gcc_checking_assert (cgraph_function_with_gimple_body_p (node
));
510 if (!flag_ipa_cp_clone
)
513 fprintf (dump_file
, "Not considering %s for cloning; "
514 "-fipa-cp-clone disabled.\n",
519 if (!optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node
->decl
)))
522 fprintf (dump_file
, "Not considering %s for cloning; "
523 "optimizing it for size.\n",
528 init_caller_stats (&stats
);
529 cgraph_for_node_and_aliases (node
, gather_caller_stats
, &stats
, false);
531 if (inline_summary (node
)->self_size
< stats
.n_calls
)
534 fprintf (dump_file
, "Considering %s for cloning; code might shrink.\n",
539 /* When profile is available and function is hot, propagate into it even if
540 calls seems cold; constant propagation can improve function's speed
544 if (stats
.count_sum
> node
->count
* 90 / 100)
547 fprintf (dump_file
, "Considering %s for cloning; "
548 "usually called directly.\n",
553 if (!stats
.n_hot_calls
)
556 fprintf (dump_file
, "Not considering %s for cloning; no hot calls.\n",
561 fprintf (dump_file
, "Considering %s for cloning.\n",
566 /* Arrays representing a topological ordering of call graph nodes and a stack
567 of noes used during constant propagation. */
571 struct cgraph_node
**order
;
572 struct cgraph_node
**stack
;
573 int nnodes
, stack_top
;
576 /* Allocate the arrays in TOPO and topologically sort the nodes into order. */
579 build_toporder_info (struct topo_info
*topo
)
581 topo
->order
= XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
582 topo
->stack
= XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
584 topo
->nnodes
= ipa_reduced_postorder (topo
->order
, true, true, NULL
);
587 /* Free information about strongly connected components and the arrays in
591 free_toporder_info (struct topo_info
*topo
)
593 ipa_free_postorder_info ();
598 /* Add NODE to the stack in TOPO, unless it is already there. */
601 push_node_to_stack (struct topo_info
*topo
, struct cgraph_node
*node
)
603 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
604 if (info
->node_enqueued
)
606 info
->node_enqueued
= 1;
607 topo
->stack
[topo
->stack_top
++] = node
;
610 /* Pop a node from the stack in TOPO and return it or return NULL if the stack
613 static struct cgraph_node
*
614 pop_node_from_stack (struct topo_info
*topo
)
618 struct cgraph_node
*node
;
620 node
= topo
->stack
[topo
->stack_top
];
621 IPA_NODE_REF (node
)->node_enqueued
= 0;
628 /* Set lattice LAT to bottom and return true if it previously was not set as
632 set_lattice_to_bottom (struct ipcp_lattice
*lat
)
634 bool ret
= !lat
->bottom
;
639 /* Mark lattice as containing an unknown value and return true if it previously
640 was not marked as such. */
643 set_lattice_contains_variable (struct ipcp_lattice
*lat
)
645 bool ret
= !lat
->contains_variable
;
646 lat
->contains_variable
= true;
650 /* Set all aggegate lattices in PLATS to bottom and return true if they were
651 not previously set as such. */
654 set_agg_lats_to_bottom (struct ipcp_param_lattices
*plats
)
656 bool ret
= !plats
->aggs_bottom
;
657 plats
->aggs_bottom
= true;
661 /* Mark all aggegate lattices in PLATS as containing an unknown value and
662 return true if they were not previously marked as such. */
665 set_agg_lats_contain_variable (struct ipcp_param_lattices
*plats
)
667 bool ret
= !plats
->aggs_contain_variable
;
668 plats
->aggs_contain_variable
= true;
672 /* Mark bot aggregate and scalar lattices as containing an unknown variable,
673 return true is any of them has not been marked as such so far. */
676 set_all_contains_variable (struct ipcp_param_lattices
*plats
)
678 bool ret
= !plats
->itself
.contains_variable
|| !plats
->aggs_contain_variable
;
679 plats
->itself
.contains_variable
= true;
680 plats
->aggs_contain_variable
= true;
684 /* Initialize ipcp_lattices. */
687 initialize_node_lattices (struct cgraph_node
*node
)
689 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
690 struct cgraph_edge
*ie
;
691 bool disable
= false, variable
= false;
694 gcc_checking_assert (cgraph_function_with_gimple_body_p (node
));
695 if (!node
->local
.local
)
697 /* When cloning is allowed, we can assume that externally visible
698 functions are not called. We will compensate this by cloning
700 if (ipcp_versionable_function_p (node
)
701 && ipcp_cloning_candidate_p (node
))
707 if (disable
|| variable
)
709 for (i
= 0; i
< ipa_get_param_count (info
) ; i
++)
711 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
714 set_lattice_to_bottom (&plats
->itself
);
715 set_agg_lats_to_bottom (plats
);
718 set_all_contains_variable (plats
);
720 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
721 && !node
->alias
&& !node
->thunk
.thunk_p
)
722 fprintf (dump_file
, "Marking all lattices of %s/%i as %s\n",
723 node
->name (), node
->order
,
724 disable
? "BOTTOM" : "VARIABLE");
727 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
728 if (ie
->indirect_info
->polymorphic
729 && ie
->indirect_info
->param_index
>= 0)
731 gcc_checking_assert (ie
->indirect_info
->param_index
>= 0);
732 ipa_get_parm_lattices (info
,
733 ie
->indirect_info
->param_index
)->virt_call
= 1;
737 /* Return the result of a (possibly arithmetic) pass through jump function
738 JFUNC on the constant value INPUT. Return NULL_TREE if that cannot be
739 determined or be considered an interprocedural invariant. */
742 ipa_get_jf_pass_through_result (struct ipa_jump_func
*jfunc
, tree input
)
746 if (TREE_CODE (input
) == TREE_BINFO
)
748 if (ipa_get_jf_pass_through_type_preserved (jfunc
))
750 gcc_checking_assert (ipa_get_jf_pass_through_operation (jfunc
)
757 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
760 gcc_checking_assert (is_gimple_ip_invariant (input
));
761 if (TREE_CODE_CLASS (ipa_get_jf_pass_through_operation (jfunc
))
763 restype
= boolean_type_node
;
765 restype
= TREE_TYPE (input
);
766 res
= fold_binary (ipa_get_jf_pass_through_operation (jfunc
), restype
,
767 input
, ipa_get_jf_pass_through_operand (jfunc
));
769 if (res
&& !is_gimple_ip_invariant (res
))
775 /* Return the result of an ancestor jump function JFUNC on the constant value
776 INPUT. Return NULL_TREE if that cannot be determined. */
779 ipa_get_jf_ancestor_result (struct ipa_jump_func
*jfunc
, tree input
)
781 if (TREE_CODE (input
) == TREE_BINFO
)
783 if (!ipa_get_jf_ancestor_type_preserved (jfunc
))
785 return get_binfo_at_offset (input
,
786 ipa_get_jf_ancestor_offset (jfunc
),
787 ipa_get_jf_ancestor_type (jfunc
));
789 else if (TREE_CODE (input
) == ADDR_EXPR
)
791 tree t
= TREE_OPERAND (input
, 0);
792 t
= build_ref_for_offset (EXPR_LOCATION (t
), t
,
793 ipa_get_jf_ancestor_offset (jfunc
),
794 ipa_get_jf_ancestor_type (jfunc
), NULL
, false);
795 return build_fold_addr_expr (t
);
801 /* Determine whether JFUNC evaluates to a known value (that is either a
802 constant or a binfo) and if so, return it. Otherwise return NULL. INFO
803 describes the caller node so that pass-through jump functions can be
807 ipa_value_from_jfunc (struct ipa_node_params
*info
, struct ipa_jump_func
*jfunc
)
809 if (jfunc
->type
== IPA_JF_CONST
)
810 return ipa_get_jf_constant (jfunc
);
811 else if (jfunc
->type
== IPA_JF_KNOWN_TYPE
)
812 return ipa_binfo_from_known_type_jfunc (jfunc
);
813 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
814 || jfunc
->type
== IPA_JF_ANCESTOR
)
819 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
820 idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
822 idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
824 if (info
->ipcp_orig_node
)
825 input
= info
->known_vals
[idx
];
828 struct ipcp_lattice
*lat
;
832 gcc_checking_assert (!flag_ipa_cp
);
835 lat
= ipa_get_scalar_lat (info
, idx
);
836 if (!ipa_lat_is_single_const (lat
))
838 input
= lat
->values
->value
;
844 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
845 return ipa_get_jf_pass_through_result (jfunc
, input
);
847 return ipa_get_jf_ancestor_result (jfunc
, input
);
854 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
855 bottom, not containing a variable component and without any known value at
859 ipcp_verify_propagated_values (void)
861 struct cgraph_node
*node
;
863 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
865 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
866 int i
, count
= ipa_get_param_count (info
);
868 for (i
= 0; i
< count
; i
++)
870 struct ipcp_lattice
*lat
= ipa_get_scalar_lat (info
, i
);
873 && !lat
->contains_variable
874 && lat
->values_count
== 0)
878 fprintf (dump_file
, "\nIPA lattices after constant "
880 print_all_lattices (dump_file
, true, false);
889 /* Return true iff X and Y should be considered equal values by IPA-CP. */
892 values_equal_for_ipcp_p (tree x
, tree y
)
894 gcc_checking_assert (x
!= NULL_TREE
&& y
!= NULL_TREE
);
899 if (TREE_CODE (x
) == TREE_BINFO
|| TREE_CODE (y
) == TREE_BINFO
)
902 if (TREE_CODE (x
) == ADDR_EXPR
903 && TREE_CODE (y
) == ADDR_EXPR
904 && TREE_CODE (TREE_OPERAND (x
, 0)) == CONST_DECL
905 && TREE_CODE (TREE_OPERAND (y
, 0)) == CONST_DECL
)
906 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x
, 0)),
907 DECL_INITIAL (TREE_OPERAND (y
, 0)), 0);
909 return operand_equal_p (x
, y
, 0);
912 /* Add a new value source to VAL, marking that a value comes from edge CS and
913 (if the underlying jump function is a pass-through or an ancestor one) from
914 a caller value SRC_VAL of a caller parameter described by SRC_INDEX. OFFSET
915 is negative if the source was the scalar value of the parameter itself or
916 the offset within an aggregate. */
919 add_value_source (struct ipcp_value
*val
, struct cgraph_edge
*cs
,
920 struct ipcp_value
*src_val
, int src_idx
, HOST_WIDE_INT offset
)
922 struct ipcp_value_source
*src
;
924 src
= (struct ipcp_value_source
*) pool_alloc (ipcp_sources_pool
);
925 src
->offset
= offset
;
928 src
->index
= src_idx
;
930 src
->next
= val
->sources
;
934 /* Try to add NEWVAL to LAT, potentially creating a new struct ipcp_value for
935 it. CS, SRC_VAL SRC_INDEX and OFFSET are meant for add_value_source and
936 have the same meaning. */
939 add_value_to_lattice (struct ipcp_lattice
*lat
, tree newval
,
940 struct cgraph_edge
*cs
, struct ipcp_value
*src_val
,
941 int src_idx
, HOST_WIDE_INT offset
)
943 struct ipcp_value
*val
;
948 for (val
= lat
->values
; val
; val
= val
->next
)
949 if (values_equal_for_ipcp_p (val
->value
, newval
))
951 if (ipa_edge_within_scc (cs
))
953 struct ipcp_value_source
*s
;
954 for (s
= val
->sources
; s
; s
= s
->next
)
961 add_value_source (val
, cs
, src_val
, src_idx
, offset
);
965 if (lat
->values_count
== PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE
))
967 /* We can only free sources, not the values themselves, because sources
968 of other values in this this SCC might point to them. */
969 for (val
= lat
->values
; val
; val
= val
->next
)
973 struct ipcp_value_source
*src
= val
->sources
;
974 val
->sources
= src
->next
;
975 pool_free (ipcp_sources_pool
, src
);
980 return set_lattice_to_bottom (lat
);
984 val
= (struct ipcp_value
*) pool_alloc (ipcp_values_pool
);
985 memset (val
, 0, sizeof (*val
));
987 add_value_source (val
, cs
, src_val
, src_idx
, offset
);
989 val
->next
= lat
->values
;
994 /* Like above but passes a special value of offset to distinguish that the
995 origin is the scalar value of the parameter rather than a part of an
999 add_scalar_value_to_lattice (struct ipcp_lattice
*lat
, tree newval
,
1000 struct cgraph_edge
*cs
,
1001 struct ipcp_value
*src_val
, int src_idx
)
1003 return add_value_to_lattice (lat
, newval
, cs
, src_val
, src_idx
, -1);
1006 /* Propagate values through a pass-through jump function JFUNC associated with
1007 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1008 is the index of the source parameter. */
1011 propagate_vals_accross_pass_through (struct cgraph_edge
*cs
,
1012 struct ipa_jump_func
*jfunc
,
1013 struct ipcp_lattice
*src_lat
,
1014 struct ipcp_lattice
*dest_lat
,
1017 struct ipcp_value
*src_val
;
1020 /* Do not create new values when propagating within an SCC because if there
1021 are arithmetic functions with circular dependencies, there is infinite
1022 number of them and we would just make lattices bottom. */
1023 if ((ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1024 && ipa_edge_within_scc (cs
))
1025 ret
= set_lattice_contains_variable (dest_lat
);
1027 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1029 tree cstval
= ipa_get_jf_pass_through_result (jfunc
, src_val
->value
);
1032 ret
|= add_scalar_value_to_lattice (dest_lat
, cstval
, cs
, src_val
,
1035 ret
|= set_lattice_contains_variable (dest_lat
);
1041 /* Propagate values through an ancestor jump function JFUNC associated with
1042 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1043 is the index of the source parameter. */
1046 propagate_vals_accross_ancestor (struct cgraph_edge
*cs
,
1047 struct ipa_jump_func
*jfunc
,
1048 struct ipcp_lattice
*src_lat
,
1049 struct ipcp_lattice
*dest_lat
,
1052 struct ipcp_value
*src_val
;
1055 if (ipa_edge_within_scc (cs
))
1056 return set_lattice_contains_variable (dest_lat
);
1058 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1060 tree t
= ipa_get_jf_ancestor_result (jfunc
, src_val
->value
);
1063 ret
|= add_scalar_value_to_lattice (dest_lat
, t
, cs
, src_val
, src_idx
);
1065 ret
|= set_lattice_contains_variable (dest_lat
);
1071 /* Propagate scalar values across jump function JFUNC that is associated with
1072 edge CS and put the values into DEST_LAT. */
1075 propagate_scalar_accross_jump_function (struct cgraph_edge
*cs
,
1076 struct ipa_jump_func
*jfunc
,
1077 struct ipcp_lattice
*dest_lat
)
1079 if (dest_lat
->bottom
)
1082 if (jfunc
->type
== IPA_JF_CONST
1083 || jfunc
->type
== IPA_JF_KNOWN_TYPE
)
1087 if (jfunc
->type
== IPA_JF_KNOWN_TYPE
)
1089 val
= ipa_binfo_from_known_type_jfunc (jfunc
);
1091 return set_lattice_contains_variable (dest_lat
);
1094 val
= ipa_get_jf_constant (jfunc
);
1095 return add_scalar_value_to_lattice (dest_lat
, val
, cs
, NULL
, 0);
1097 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1098 || jfunc
->type
== IPA_JF_ANCESTOR
)
1100 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1101 struct ipcp_lattice
*src_lat
;
1105 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1106 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1108 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1110 src_lat
= ipa_get_scalar_lat (caller_info
, src_idx
);
1111 if (src_lat
->bottom
)
1112 return set_lattice_contains_variable (dest_lat
);
1114 /* If we would need to clone the caller and cannot, do not propagate. */
1115 if (!ipcp_versionable_function_p (cs
->caller
)
1116 && (src_lat
->contains_variable
1117 || (src_lat
->values_count
> 1)))
1118 return set_lattice_contains_variable (dest_lat
);
1120 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1121 ret
= propagate_vals_accross_pass_through (cs
, jfunc
, src_lat
,
1124 ret
= propagate_vals_accross_ancestor (cs
, jfunc
, src_lat
, dest_lat
,
1127 if (src_lat
->contains_variable
)
1128 ret
|= set_lattice_contains_variable (dest_lat
);
1133 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1134 use it for indirect inlining), we should propagate them too. */
1135 return set_lattice_contains_variable (dest_lat
);
1138 /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
1139 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
1140 other cases, return false). If there are no aggregate items, set
1141 aggs_by_ref to NEW_AGGS_BY_REF. */
1144 set_check_aggs_by_ref (struct ipcp_param_lattices
*dest_plats
,
1145 bool new_aggs_by_ref
)
1147 if (dest_plats
->aggs
)
1149 if (dest_plats
->aggs_by_ref
!= new_aggs_by_ref
)
1151 set_agg_lats_to_bottom (dest_plats
);
1156 dest_plats
->aggs_by_ref
= new_aggs_by_ref
;
1160 /* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
1161 already existing lattice for the given OFFSET and SIZE, marking all skipped
1162 lattices as containing variable and checking for overlaps. If there is no
1163 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
1164 it with offset, size and contains_variable to PRE_EXISTING, and return true,
1165 unless there are too many already. If there are two many, return false. If
1166 there are overlaps turn whole DEST_PLATS to bottom and return false. If any
1167 skipped lattices were newly marked as containing variable, set *CHANGE to
1171 merge_agg_lats_step (struct ipcp_param_lattices
*dest_plats
,
1172 HOST_WIDE_INT offset
, HOST_WIDE_INT val_size
,
1173 struct ipcp_agg_lattice
***aglat
,
1174 bool pre_existing
, bool *change
)
1176 gcc_checking_assert (offset
>= 0);
1178 while (**aglat
&& (**aglat
)->offset
< offset
)
1180 if ((**aglat
)->offset
+ (**aglat
)->size
> offset
)
1182 set_agg_lats_to_bottom (dest_plats
);
1185 *change
|= set_lattice_contains_variable (**aglat
);
1186 *aglat
= &(**aglat
)->next
;
1189 if (**aglat
&& (**aglat
)->offset
== offset
)
1191 if ((**aglat
)->size
!= val_size
1193 && (**aglat
)->next
->offset
< offset
+ val_size
))
1195 set_agg_lats_to_bottom (dest_plats
);
1198 gcc_checking_assert (!(**aglat
)->next
1199 || (**aglat
)->next
->offset
>= offset
+ val_size
);
1204 struct ipcp_agg_lattice
*new_al
;
1206 if (**aglat
&& (**aglat
)->offset
< offset
+ val_size
)
1208 set_agg_lats_to_bottom (dest_plats
);
1211 if (dest_plats
->aggs_count
== PARAM_VALUE (PARAM_IPA_MAX_AGG_ITEMS
))
1213 dest_plats
->aggs_count
++;
1214 new_al
= (struct ipcp_agg_lattice
*) pool_alloc (ipcp_agg_lattice_pool
);
1215 memset (new_al
, 0, sizeof (*new_al
));
1217 new_al
->offset
= offset
;
1218 new_al
->size
= val_size
;
1219 new_al
->contains_variable
= pre_existing
;
1221 new_al
->next
= **aglat
;
1227 /* Set all AGLAT and all other aggregate lattices reachable by next pointers as
1228 containing an unknown value. */
1231 set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice
*aglat
)
1236 ret
|= set_lattice_contains_variable (aglat
);
1237 aglat
= aglat
->next
;
1242 /* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
1243 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source
1244 parameter used for lattice value sources. Return true if DEST_PLATS changed
1248 merge_aggregate_lattices (struct cgraph_edge
*cs
,
1249 struct ipcp_param_lattices
*dest_plats
,
1250 struct ipcp_param_lattices
*src_plats
,
1251 int src_idx
, HOST_WIDE_INT offset_delta
)
1253 bool pre_existing
= dest_plats
->aggs
!= NULL
;
1254 struct ipcp_agg_lattice
**dst_aglat
;
1257 if (set_check_aggs_by_ref (dest_plats
, src_plats
->aggs_by_ref
))
1259 if (src_plats
->aggs_bottom
)
1260 return set_agg_lats_contain_variable (dest_plats
);
1261 if (src_plats
->aggs_contain_variable
)
1262 ret
|= set_agg_lats_contain_variable (dest_plats
);
1263 dst_aglat
= &dest_plats
->aggs
;
1265 for (struct ipcp_agg_lattice
*src_aglat
= src_plats
->aggs
;
1267 src_aglat
= src_aglat
->next
)
1269 HOST_WIDE_INT new_offset
= src_aglat
->offset
- offset_delta
;
1273 if (merge_agg_lats_step (dest_plats
, new_offset
, src_aglat
->size
,
1274 &dst_aglat
, pre_existing
, &ret
))
1276 struct ipcp_agg_lattice
*new_al
= *dst_aglat
;
1278 dst_aglat
= &(*dst_aglat
)->next
;
1279 if (src_aglat
->bottom
)
1281 ret
|= set_lattice_contains_variable (new_al
);
1284 if (src_aglat
->contains_variable
)
1285 ret
|= set_lattice_contains_variable (new_al
);
1286 for (struct ipcp_value
*val
= src_aglat
->values
;
1289 ret
|= add_value_to_lattice (new_al
, val
->value
, cs
, val
, src_idx
,
1292 else if (dest_plats
->aggs_bottom
)
1295 ret
|= set_chain_of_aglats_contains_variable (*dst_aglat
);
1299 /* Determine whether there is anything to propagate FROM SRC_PLATS through a
1300 pass-through JFUNC and if so, whether it has conform and conforms to the
1301 rules about propagating values passed by reference. */
1304 agg_pass_through_permissible_p (struct ipcp_param_lattices
*src_plats
,
1305 struct ipa_jump_func
*jfunc
)
1307 return src_plats
->aggs
1308 && (!src_plats
->aggs_by_ref
1309 || ipa_get_jf_pass_through_agg_preserved (jfunc
));
1312 /* Propagate scalar values across jump function JFUNC that is associated with
1313 edge CS and put the values into DEST_LAT. */
1316 propagate_aggs_accross_jump_function (struct cgraph_edge
*cs
,
1317 struct ipa_jump_func
*jfunc
,
1318 struct ipcp_param_lattices
*dest_plats
)
1322 if (dest_plats
->aggs_bottom
)
1325 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1326 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
1328 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1329 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1330 struct ipcp_param_lattices
*src_plats
;
1332 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
1333 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
1335 /* Currently we do not produce clobber aggregate jump
1336 functions, replace with merging when we do. */
1337 gcc_assert (!jfunc
->agg
.items
);
1338 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
,
1342 ret
|= set_agg_lats_contain_variable (dest_plats
);
1344 else if (jfunc
->type
== IPA_JF_ANCESTOR
1345 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
1347 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1348 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1349 struct ipcp_param_lattices
*src_plats
;
1351 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
1352 if (src_plats
->aggs
&& src_plats
->aggs_by_ref
)
1354 /* Currently we do not produce clobber aggregate jump
1355 functions, replace with merging when we do. */
1356 gcc_assert (!jfunc
->agg
.items
);
1357 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
, src_idx
,
1358 ipa_get_jf_ancestor_offset (jfunc
));
1360 else if (!src_plats
->aggs_by_ref
)
1361 ret
|= set_agg_lats_to_bottom (dest_plats
);
1363 ret
|= set_agg_lats_contain_variable (dest_plats
);
1365 else if (jfunc
->agg
.items
)
1367 bool pre_existing
= dest_plats
->aggs
!= NULL
;
1368 struct ipcp_agg_lattice
**aglat
= &dest_plats
->aggs
;
1369 struct ipa_agg_jf_item
*item
;
1372 if (set_check_aggs_by_ref (dest_plats
, jfunc
->agg
.by_ref
))
1375 FOR_EACH_VEC_ELT (*jfunc
->agg
.items
, i
, item
)
1377 HOST_WIDE_INT val_size
;
1379 if (item
->offset
< 0)
1381 gcc_checking_assert (is_gimple_ip_invariant (item
->value
));
1382 val_size
= tree_to_uhwi (TYPE_SIZE (TREE_TYPE (item
->value
)));
1384 if (merge_agg_lats_step (dest_plats
, item
->offset
, val_size
,
1385 &aglat
, pre_existing
, &ret
))
1387 ret
|= add_value_to_lattice (*aglat
, item
->value
, cs
, NULL
, 0, 0);
1388 aglat
= &(*aglat
)->next
;
1390 else if (dest_plats
->aggs_bottom
)
1394 ret
|= set_chain_of_aglats_contains_variable (*aglat
);
1397 ret
|= set_agg_lats_contain_variable (dest_plats
);
1402 /* Propagate constants from the caller to the callee of CS. INFO describes the
1406 propagate_constants_accross_call (struct cgraph_edge
*cs
)
1408 struct ipa_node_params
*callee_info
;
1409 enum availability availability
;
1410 struct cgraph_node
*callee
, *alias_or_thunk
;
1411 struct ipa_edge_args
*args
;
1413 int i
, args_count
, parms_count
;
1415 callee
= cgraph_function_node (cs
->callee
, &availability
);
1416 if (!callee
->definition
)
1418 gcc_checking_assert (cgraph_function_with_gimple_body_p (callee
));
1419 callee_info
= IPA_NODE_REF (callee
);
1421 args
= IPA_EDGE_REF (cs
);
1422 args_count
= ipa_get_cs_argument_count (args
);
1423 parms_count
= ipa_get_param_count (callee_info
);
1425 /* If this call goes through a thunk we must not propagate to the first (0th)
1426 parameter. However, we might need to uncover a thunk from below a series
1427 of aliases first. */
1428 alias_or_thunk
= cs
->callee
;
1429 while (alias_or_thunk
->alias
)
1430 alias_or_thunk
= cgraph_alias_target (alias_or_thunk
);
1431 if (alias_or_thunk
->thunk
.thunk_p
)
1433 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
1440 for (; (i
< args_count
) && (i
< parms_count
); i
++)
1442 struct ipa_jump_func
*jump_func
= ipa_get_ith_jump_func (args
, i
);
1443 struct ipcp_param_lattices
*dest_plats
;
1445 dest_plats
= ipa_get_parm_lattices (callee_info
, i
);
1446 if (availability
== AVAIL_OVERWRITABLE
)
1447 ret
|= set_all_contains_variable (dest_plats
);
1450 ret
|= propagate_scalar_accross_jump_function (cs
, jump_func
,
1451 &dest_plats
->itself
);
1452 ret
|= propagate_aggs_accross_jump_function (cs
, jump_func
,
1456 for (; i
< parms_count
; i
++)
1457 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
, i
));
1462 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
1463 (which can contain both constants and binfos), KNOWN_BINFOS, KNOWN_AGGS or
1464 AGG_REPS return the destination. The latter three can be NULL. If AGG_REPS
1465 is not NULL, KNOWN_AGGS is ignored. */
1468 ipa_get_indirect_edge_target_1 (struct cgraph_edge
*ie
,
1469 vec
<tree
> known_vals
,
1470 vec
<tree
> known_binfos
,
1471 vec
<ipa_agg_jump_function_p
> known_aggs
,
1472 struct ipa_agg_replacement_value
*agg_reps
)
1474 int param_index
= ie
->indirect_info
->param_index
;
1475 HOST_WIDE_INT token
, anc_offset
;
1480 if (param_index
== -1
1481 || known_vals
.length () <= (unsigned int) param_index
)
1484 if (!ie
->indirect_info
->polymorphic
)
1488 if (ie
->indirect_info
->agg_contents
)
1495 if (agg_reps
->index
== param_index
1496 && agg_reps
->offset
== ie
->indirect_info
->offset
1497 && agg_reps
->by_ref
== ie
->indirect_info
->by_ref
)
1499 t
= agg_reps
->value
;
1502 agg_reps
= agg_reps
->next
;
1505 else if (known_aggs
.length () > (unsigned int) param_index
)
1507 struct ipa_agg_jump_function
*agg
;
1508 agg
= known_aggs
[param_index
];
1509 t
= ipa_find_agg_cst_for_param (agg
, ie
->indirect_info
->offset
,
1510 ie
->indirect_info
->by_ref
);
1516 t
= known_vals
[param_index
];
1519 TREE_CODE (t
) == ADDR_EXPR
1520 && TREE_CODE (TREE_OPERAND (t
, 0)) == FUNCTION_DECL
)
1521 return TREE_OPERAND (t
, 0);
1526 gcc_assert (!ie
->indirect_info
->agg_contents
);
1527 token
= ie
->indirect_info
->otr_token
;
1528 anc_offset
= ie
->indirect_info
->offset
;
1529 otr_type
= ie
->indirect_info
->otr_type
;
1531 t
= known_vals
[param_index
];
1532 if (!t
&& known_binfos
.length () > (unsigned int) param_index
)
1533 t
= known_binfos
[param_index
];
1537 if (TREE_CODE (t
) != TREE_BINFO
)
1540 binfo
= gimple_extract_devirt_binfo_from_cst
1541 (t
, ie
->indirect_info
->otr_type
);
1544 binfo
= get_binfo_at_offset (binfo
, anc_offset
, otr_type
);
1547 target
= gimple_get_virt_method_for_binfo (token
, binfo
);
1553 binfo
= get_binfo_at_offset (t
, anc_offset
, otr_type
);
1556 target
= gimple_get_virt_method_for_binfo (token
, binfo
);
1558 #ifdef ENABLE_CHECKING
1560 gcc_assert (possible_polymorphic_call_target_p
1561 (ie
, cgraph_get_node (target
)));
1568 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
1569 (which can contain both constants and binfos), KNOWN_BINFOS (which can be
1570 NULL) or KNOWN_AGGS (which also can be NULL) return the destination. */
1573 ipa_get_indirect_edge_target (struct cgraph_edge
*ie
,
1574 vec
<tree
> known_vals
,
1575 vec
<tree
> known_binfos
,
1576 vec
<ipa_agg_jump_function_p
> known_aggs
)
1578 return ipa_get_indirect_edge_target_1 (ie
, known_vals
, known_binfos
,
1582 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
1583 and KNOWN_BINFOS. */
1586 devirtualization_time_bonus (struct cgraph_node
*node
,
1587 vec
<tree
> known_csts
,
1588 vec
<tree
> known_binfos
,
1589 vec
<ipa_agg_jump_function_p
> known_aggs
)
1591 struct cgraph_edge
*ie
;
1594 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
1596 struct cgraph_node
*callee
;
1597 struct inline_summary
*isummary
;
1600 target
= ipa_get_indirect_edge_target (ie
, known_csts
, known_binfos
,
1605 /* Only bare minimum benefit for clearly un-inlineable targets. */
1607 callee
= cgraph_get_node (target
);
1608 if (!callee
|| !callee
->definition
)
1610 isummary
= inline_summary (callee
);
1611 if (!isummary
->inlinable
)
1614 /* FIXME: The values below need re-considering and perhaps also
1615 integrating into the cost metrics, at lest in some very basic way. */
1616 if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 4)
1618 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 2)
1620 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
1621 || DECL_DECLARED_INLINE_P (callee
->decl
))
1628 /* Return time bonus incurred because of HINTS. */
1631 hint_time_bonus (inline_hints hints
)
1634 if (hints
& (INLINE_HINT_loop_iterations
| INLINE_HINT_loop_stride
))
1635 result
+= PARAM_VALUE (PARAM_IPA_CP_LOOP_HINT_BONUS
);
1636 if (hints
& INLINE_HINT_array_index
)
1637 result
+= PARAM_VALUE (PARAM_IPA_CP_ARRAY_INDEX_HINT_BONUS
);
1641 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
1642 and SIZE_COST and with the sum of frequencies of incoming edges to the
1643 potential new clone in FREQUENCIES. */
1646 good_cloning_opportunity_p (struct cgraph_node
*node
, int time_benefit
,
1647 int freq_sum
, gcov_type count_sum
, int size_cost
)
1649 if (time_benefit
== 0
1650 || !flag_ipa_cp_clone
1651 || !optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node
->decl
)))
1654 gcc_assert (size_cost
> 0);
1658 int factor
= (count_sum
* 1000) / max_count
;
1659 HOST_WIDEST_INT evaluation
= (((HOST_WIDEST_INT
) time_benefit
* factor
)
1662 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1663 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
1664 "size: %i, count_sum: " HOST_WIDE_INT_PRINT_DEC
1665 ") -> evaluation: " HOST_WIDEST_INT_PRINT_DEC
1666 ", threshold: %i\n",
1667 time_benefit
, size_cost
, (HOST_WIDE_INT
) count_sum
,
1668 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
1670 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
1674 HOST_WIDEST_INT evaluation
= (((HOST_WIDEST_INT
) time_benefit
* freq_sum
)
1677 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1678 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
1679 "size: %i, freq_sum: %i) -> evaluation: "
1680 HOST_WIDEST_INT_PRINT_DEC
", threshold: %i\n",
1681 time_benefit
, size_cost
, freq_sum
, evaluation
,
1682 PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
1684 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
1688 /* Return all context independent values from aggregate lattices in PLATS in a
1689 vector. Return NULL if there are none. */
1691 static vec
<ipa_agg_jf_item
, va_gc
> *
1692 context_independent_aggregate_values (struct ipcp_param_lattices
*plats
)
1694 vec
<ipa_agg_jf_item
, va_gc
> *res
= NULL
;
1696 if (plats
->aggs_bottom
1697 || plats
->aggs_contain_variable
1698 || plats
->aggs_count
== 0)
1701 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
;
1703 aglat
= aglat
->next
)
1704 if (ipa_lat_is_single_const (aglat
))
1706 struct ipa_agg_jf_item item
;
1707 item
.offset
= aglat
->offset
;
1708 item
.value
= aglat
->values
->value
;
1709 vec_safe_push (res
, item
);
1714 /* Allocate KNOWN_CSTS, KNOWN_BINFOS and, if non-NULL, KNOWN_AGGS and populate
1715 them with values of parameters that are known independent of the context.
1716 INFO describes the function. If REMOVABLE_PARAMS_COST is non-NULL, the
1717 movement cost of all removable parameters will be stored in it. */
1720 gather_context_independent_values (struct ipa_node_params
*info
,
1721 vec
<tree
> *known_csts
,
1722 vec
<tree
> *known_binfos
,
1723 vec
<ipa_agg_jump_function
> *known_aggs
,
1724 int *removable_params_cost
)
1726 int i
, count
= ipa_get_param_count (info
);
1729 known_csts
->create (0);
1730 known_binfos
->create (0);
1731 known_csts
->safe_grow_cleared (count
);
1732 known_binfos
->safe_grow_cleared (count
);
1735 known_aggs
->create (0);
1736 known_aggs
->safe_grow_cleared (count
);
1739 if (removable_params_cost
)
1740 *removable_params_cost
= 0;
1742 for (i
= 0; i
< count
; i
++)
1744 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1745 struct ipcp_lattice
*lat
= &plats
->itself
;
1747 if (ipa_lat_is_single_const (lat
))
1749 struct ipcp_value
*val
= lat
->values
;
1750 if (TREE_CODE (val
->value
) != TREE_BINFO
)
1752 (*known_csts
)[i
] = val
->value
;
1753 if (removable_params_cost
)
1754 *removable_params_cost
1755 += estimate_move_cost (TREE_TYPE (val
->value
));
1758 else if (plats
->virt_call
)
1760 (*known_binfos
)[i
] = val
->value
;
1763 else if (removable_params_cost
1764 && !ipa_is_param_used (info
, i
))
1765 *removable_params_cost
+= ipa_get_param_move_cost (info
, i
);
1767 else if (removable_params_cost
1768 && !ipa_is_param_used (info
, i
))
1769 *removable_params_cost
1770 += ipa_get_param_move_cost (info
, i
);
1774 vec
<ipa_agg_jf_item
, va_gc
> *agg_items
;
1775 struct ipa_agg_jump_function
*ajf
;
1777 agg_items
= context_independent_aggregate_values (plats
);
1778 ajf
= &(*known_aggs
)[i
];
1779 ajf
->items
= agg_items
;
1780 ajf
->by_ref
= plats
->aggs_by_ref
;
1781 ret
|= agg_items
!= NULL
;
1788 /* The current interface in ipa-inline-analysis requires a pointer vector.
1791 FIXME: That interface should be re-worked, this is slightly silly. Still,
1792 I'd like to discuss how to change it first and this demonstrates the
1795 static vec
<ipa_agg_jump_function_p
>
1796 agg_jmp_p_vec_for_t_vec (vec
<ipa_agg_jump_function
> known_aggs
)
1798 vec
<ipa_agg_jump_function_p
> ret
;
1799 struct ipa_agg_jump_function
*ajf
;
1802 ret
.create (known_aggs
.length ());
1803 FOR_EACH_VEC_ELT (known_aggs
, i
, ajf
)
1804 ret
.quick_push (ajf
);
1808 /* Iterate over known values of parameters of NODE and estimate the local
1809 effects in terms of time and size they have. */
1812 estimate_local_effects (struct cgraph_node
*node
)
1814 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1815 int i
, count
= ipa_get_param_count (info
);
1816 vec
<tree
> known_csts
, known_binfos
;
1817 vec
<ipa_agg_jump_function
> known_aggs
;
1818 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
;
1820 int base_time
= inline_summary (node
)->time
;
1821 int removable_params_cost
;
1823 if (!count
|| !ipcp_versionable_function_p (node
))
1826 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1827 fprintf (dump_file
, "\nEstimating effects for %s/%i, base_time: %i.\n",
1828 node
->name (), node
->order
, base_time
);
1830 always_const
= gather_context_independent_values (info
, &known_csts
,
1831 &known_binfos
, &known_aggs
,
1832 &removable_params_cost
);
1833 known_aggs_ptrs
= agg_jmp_p_vec_for_t_vec (known_aggs
);
1836 struct caller_statistics stats
;
1840 init_caller_stats (&stats
);
1841 cgraph_for_node_and_aliases (node
, gather_caller_stats
, &stats
, false);
1842 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_binfos
,
1843 known_aggs_ptrs
, &size
, &time
, &hints
);
1844 time
-= devirtualization_time_bonus (node
, known_csts
, known_binfos
,
1846 time
-= hint_time_bonus (hints
);
1847 time
-= removable_params_cost
;
1848 size
-= stats
.n_calls
* removable_params_cost
;
1851 fprintf (dump_file
, " - context independent values, size: %i, "
1852 "time_benefit: %i\n", size
, base_time
- time
);
1855 || cgraph_will_be_removed_from_program_if_no_direct_calls (node
))
1857 info
->do_clone_for_all_contexts
= true;
1861 fprintf (dump_file
, " Decided to specialize for all "
1862 "known contexts, code not going to grow.\n");
1864 else if (good_cloning_opportunity_p (node
, base_time
- time
,
1865 stats
.freq_sum
, stats
.count_sum
,
1868 if (size
+ overall_size
<= max_new_size
)
1870 info
->do_clone_for_all_contexts
= true;
1872 overall_size
+= size
;
1875 fprintf (dump_file
, " Decided to specialize for all "
1876 "known contexts, growth deemed beneficial.\n");
1878 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1879 fprintf (dump_file
, " Not cloning for all contexts because "
1880 "max_new_size would be reached with %li.\n",
1881 size
+ overall_size
);
1885 for (i
= 0; i
< count
; i
++)
1887 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1888 struct ipcp_lattice
*lat
= &plats
->itself
;
1889 struct ipcp_value
*val
;
1898 for (val
= lat
->values
; val
; val
= val
->next
)
1900 int time
, size
, time_benefit
;
1903 if (TREE_CODE (val
->value
) != TREE_BINFO
)
1905 known_csts
[i
] = val
->value
;
1906 known_binfos
[i
] = NULL_TREE
;
1907 emc
= estimate_move_cost (TREE_TYPE (val
->value
));
1909 else if (plats
->virt_call
)
1911 known_csts
[i
] = NULL_TREE
;
1912 known_binfos
[i
] = val
->value
;
1918 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_binfos
,
1919 known_aggs_ptrs
, &size
, &time
,
1921 time_benefit
= base_time
- time
1922 + devirtualization_time_bonus (node
, known_csts
, known_binfos
,
1924 + hint_time_bonus (hints
)
1925 + removable_params_cost
+ emc
;
1927 gcc_checking_assert (size
>=0);
1928 /* The inliner-heuristics based estimates may think that in certain
1929 contexts some functions do not have any size at all but we want
1930 all specializations to have at least a tiny cost, not least not to
1935 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1937 fprintf (dump_file
, " - estimates for value ");
1938 print_ipcp_constant_value (dump_file
, val
->value
);
1939 fprintf (dump_file
, " for ");
1940 ipa_dump_param (dump_file
, info
, i
);
1941 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
1942 time_benefit
, size
);
1945 val
->local_time_benefit
= time_benefit
;
1946 val
->local_size_cost
= size
;
1948 known_binfos
[i
] = NULL_TREE
;
1949 known_csts
[i
] = NULL_TREE
;
1952 for (i
= 0; i
< count
; i
++)
1954 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1955 struct ipa_agg_jump_function
*ajf
;
1956 struct ipcp_agg_lattice
*aglat
;
1958 if (plats
->aggs_bottom
|| !plats
->aggs
)
1961 ajf
= &known_aggs
[i
];
1962 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
1964 struct ipcp_value
*val
;
1965 if (aglat
->bottom
|| !aglat
->values
1966 /* If the following is true, the one value is in known_aggs. */
1967 || (!plats
->aggs_contain_variable
1968 && ipa_lat_is_single_const (aglat
)))
1971 for (val
= aglat
->values
; val
; val
= val
->next
)
1973 int time
, size
, time_benefit
;
1974 struct ipa_agg_jf_item item
;
1977 item
.offset
= aglat
->offset
;
1978 item
.value
= val
->value
;
1979 vec_safe_push (ajf
->items
, item
);
1981 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_binfos
,
1982 known_aggs_ptrs
, &size
, &time
,
1984 time_benefit
= base_time
- time
1985 + devirtualization_time_bonus (node
, known_csts
, known_binfos
,
1987 + hint_time_bonus (hints
);
1988 gcc_checking_assert (size
>=0);
1992 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1994 fprintf (dump_file
, " - estimates for value ");
1995 print_ipcp_constant_value (dump_file
, val
->value
);
1996 fprintf (dump_file
, " for ");
1997 ipa_dump_param (dump_file
, info
, i
);
1998 fprintf (dump_file
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
1999 "]: time_benefit: %i, size: %i\n",
2000 plats
->aggs_by_ref
? "ref " : "",
2001 aglat
->offset
, time_benefit
, size
);
2004 val
->local_time_benefit
= time_benefit
;
2005 val
->local_size_cost
= size
;
2011 for (i
= 0; i
< count
; i
++)
2012 vec_free (known_aggs
[i
].items
);
2014 known_csts
.release ();
2015 known_binfos
.release ();
2016 known_aggs
.release ();
2017 known_aggs_ptrs
.release ();
2021 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
2022 topological sort of values. */
2025 add_val_to_toposort (struct ipcp_value
*cur_val
)
2027 static int dfs_counter
= 0;
2028 static struct ipcp_value
*stack
;
2029 struct ipcp_value_source
*src
;
2035 cur_val
->dfs
= dfs_counter
;
2036 cur_val
->low_link
= dfs_counter
;
2038 cur_val
->topo_next
= stack
;
2040 cur_val
->on_stack
= true;
2042 for (src
= cur_val
->sources
; src
; src
= src
->next
)
2045 if (src
->val
->dfs
== 0)
2047 add_val_to_toposort (src
->val
);
2048 if (src
->val
->low_link
< cur_val
->low_link
)
2049 cur_val
->low_link
= src
->val
->low_link
;
2051 else if (src
->val
->on_stack
2052 && src
->val
->dfs
< cur_val
->low_link
)
2053 cur_val
->low_link
= src
->val
->dfs
;
2056 if (cur_val
->dfs
== cur_val
->low_link
)
2058 struct ipcp_value
*v
, *scc_list
= NULL
;
2063 stack
= v
->topo_next
;
2064 v
->on_stack
= false;
2066 v
->scc_next
= scc_list
;
2069 while (v
!= cur_val
);
2071 cur_val
->topo_next
= values_topo
;
2072 values_topo
= cur_val
;
2076 /* Add all values in lattices associated with NODE to the topological sort if
2077 they are not there yet. */
2080 add_all_node_vals_to_toposort (struct cgraph_node
*node
)
2082 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2083 int i
, count
= ipa_get_param_count (info
);
2085 for (i
= 0; i
< count
; i
++)
2087 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2088 struct ipcp_lattice
*lat
= &plats
->itself
;
2089 struct ipcp_agg_lattice
*aglat
;
2090 struct ipcp_value
*val
;
2093 for (val
= lat
->values
; val
; val
= val
->next
)
2094 add_val_to_toposort (val
);
2096 if (!plats
->aggs_bottom
)
2097 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2099 for (val
= aglat
->values
; val
; val
= val
->next
)
2100 add_val_to_toposort (val
);
2104 /* One pass of constants propagation along the call graph edges, from callers
2105 to callees (requires topological ordering in TOPO), iterate over strongly
2106 connected components. */
2109 propagate_constants_topo (struct topo_info
*topo
)
2113 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
2116 struct cgraph_node
*v
, *node
= topo
->order
[i
];
2117 vec
<cgraph_node_ptr
> cycle_nodes
= ipa_get_nodes_in_cycle (node
);
2119 /* First, iteratively propagate within the strongly connected component
2120 until all lattices stabilize. */
2121 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
2122 if (cgraph_function_with_gimple_body_p (v
))
2123 push_node_to_stack (topo
, v
);
2125 v
= pop_node_from_stack (topo
);
2128 struct cgraph_edge
*cs
;
2130 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
2131 if (ipa_edge_within_scc (cs
)
2132 && propagate_constants_accross_call (cs
))
2133 push_node_to_stack (topo
, cs
->callee
);
2134 v
= pop_node_from_stack (topo
);
2137 /* Afterwards, propagate along edges leading out of the SCC, calculates
2138 the local effects of the discovered constants and all valid values to
2139 their topological sort. */
2140 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
2141 if (cgraph_function_with_gimple_body_p (v
))
2143 struct cgraph_edge
*cs
;
2145 estimate_local_effects (v
);
2146 add_all_node_vals_to_toposort (v
);
2147 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
2148 if (!ipa_edge_within_scc (cs
))
2149 propagate_constants_accross_call (cs
);
2151 cycle_nodes
.release ();
2156 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
2157 the bigger one if otherwise. */
2160 safe_add (int a
, int b
)
2162 if (a
> INT_MAX
/2 || b
> INT_MAX
/2)
2163 return a
> b
? a
: b
;
2169 /* Propagate the estimated effects of individual values along the topological
2170 from the dependent values to those they depend on. */
2173 propagate_effects (void)
2175 struct ipcp_value
*base
;
2177 for (base
= values_topo
; base
; base
= base
->topo_next
)
2179 struct ipcp_value_source
*src
;
2180 struct ipcp_value
*val
;
2181 int time
= 0, size
= 0;
2183 for (val
= base
; val
; val
= val
->scc_next
)
2185 time
= safe_add (time
,
2186 val
->local_time_benefit
+ val
->prop_time_benefit
);
2187 size
= safe_add (size
, val
->local_size_cost
+ val
->prop_size_cost
);
2190 for (val
= base
; val
; val
= val
->scc_next
)
2191 for (src
= val
->sources
; src
; src
= src
->next
)
2193 && cgraph_maybe_hot_edge_p (src
->cs
))
2195 src
->val
->prop_time_benefit
= safe_add (time
,
2196 src
->val
->prop_time_benefit
);
2197 src
->val
->prop_size_cost
= safe_add (size
,
2198 src
->val
->prop_size_cost
);
2204 /* Propagate constants, binfos and their effects from the summaries
2205 interprocedurally. */
2208 ipcp_propagate_stage (struct topo_info
*topo
)
2210 struct cgraph_node
*node
;
2213 fprintf (dump_file
, "\n Propagating constants:\n\n");
2216 ipa_update_after_lto_read ();
2219 FOR_EACH_DEFINED_FUNCTION (node
)
2221 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2223 determine_versionability (node
);
2224 if (cgraph_function_with_gimple_body_p (node
))
2226 info
->lattices
= XCNEWVEC (struct ipcp_param_lattices
,
2227 ipa_get_param_count (info
));
2228 initialize_node_lattices (node
);
2230 if (node
->definition
&& !node
->alias
)
2231 overall_size
+= inline_summary (node
)->self_size
;
2232 if (node
->count
> max_count
)
2233 max_count
= node
->count
;
2236 max_new_size
= overall_size
;
2237 if (max_new_size
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
2238 max_new_size
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
2239 max_new_size
+= max_new_size
* PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH
) / 100 + 1;
2242 fprintf (dump_file
, "\noverall_size: %li, max_new_size: %li\n",
2243 overall_size
, max_new_size
);
2245 propagate_constants_topo (topo
);
2246 #ifdef ENABLE_CHECKING
2247 ipcp_verify_propagated_values ();
2249 propagate_effects ();
2253 fprintf (dump_file
, "\nIPA lattices after all propagation:\n");
2254 print_all_lattices (dump_file
, (dump_flags
& TDF_DETAILS
), true);
2258 /* Discover newly direct outgoing edges from NODE which is a new clone with
2259 known KNOWN_VALS and make them direct. */
2262 ipcp_discover_new_direct_edges (struct cgraph_node
*node
,
2263 vec
<tree
> known_vals
,
2264 struct ipa_agg_replacement_value
*aggvals
)
2266 struct cgraph_edge
*ie
, *next_ie
;
2269 for (ie
= node
->indirect_calls
; ie
; ie
= next_ie
)
2273 next_ie
= ie
->next_callee
;
2274 target
= ipa_get_indirect_edge_target_1 (ie
, known_vals
, vNULL
, vNULL
,
2278 bool agg_contents
= ie
->indirect_info
->agg_contents
;
2279 bool polymorphic
= ie
->indirect_info
->polymorphic
;
2280 bool param_index
= ie
->indirect_info
->param_index
;
2281 struct cgraph_edge
*cs
= ipa_make_edge_direct_to_target (ie
, target
);
2284 if (cs
&& !agg_contents
&& !polymorphic
)
2286 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2287 int c
= ipa_get_controlled_uses (info
, param_index
);
2288 if (c
!= IPA_UNDESCRIBED_USE
)
2290 struct ipa_ref
*to_del
;
2293 ipa_set_controlled_uses (info
, param_index
, c
);
2294 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2295 fprintf (dump_file
, " controlled uses count of param "
2296 "%i bumped down to %i\n", param_index
, c
);
2298 && (to_del
= ipa_find_reference (node
,
2302 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2303 fprintf (dump_file
, " and even removing its "
2304 "cloning-created reference\n");
2305 ipa_remove_reference (to_del
);
2311 /* Turning calls to direct calls will improve overall summary. */
2313 inline_update_overall_summary (node
);
2316 /* Vector of pointers which for linked lists of clones of an original crgaph
2319 static vec
<cgraph_edge_p
> next_edge_clone
;
2322 grow_next_edge_clone_vector (void)
2324 if (next_edge_clone
.length ()
2325 <= (unsigned) cgraph_edge_max_uid
)
2326 next_edge_clone
.safe_grow_cleared (cgraph_edge_max_uid
+ 1);
2329 /* Edge duplication hook to grow the appropriate linked list in
2333 ipcp_edge_duplication_hook (struct cgraph_edge
*src
, struct cgraph_edge
*dst
,
2334 __attribute__((unused
)) void *data
)
2336 grow_next_edge_clone_vector ();
2337 next_edge_clone
[dst
->uid
] = next_edge_clone
[src
->uid
];
2338 next_edge_clone
[src
->uid
] = dst
;
2341 /* See if NODE is a clone with a known aggregate value at a given OFFSET of a
2342 parameter with the given INDEX. */
2345 get_clone_agg_value (struct cgraph_node
*node
, HOST_WIDEST_INT offset
,
2348 struct ipa_agg_replacement_value
*aggval
;
2350 aggval
= ipa_get_agg_replacements_for_node (node
);
2353 if (aggval
->offset
== offset
2354 && aggval
->index
== index
)
2355 return aggval
->value
;
2356 aggval
= aggval
->next
;
2361 /* Return true if edge CS does bring about the value described by SRC. */
2364 cgraph_edge_brings_value_p (struct cgraph_edge
*cs
,
2365 struct ipcp_value_source
*src
)
2367 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2368 struct ipa_node_params
*dst_info
= IPA_NODE_REF (cs
->callee
);
2370 if ((dst_info
->ipcp_orig_node
&& !dst_info
->is_all_contexts_clone
)
2371 || caller_info
->node_dead
)
2376 if (caller_info
->ipcp_orig_node
)
2379 if (src
->offset
== -1)
2380 t
= caller_info
->known_vals
[src
->index
];
2382 t
= get_clone_agg_value (cs
->caller
, src
->offset
, src
->index
);
2383 return (t
!= NULL_TREE
2384 && values_equal_for_ipcp_p (src
->val
->value
, t
));
2388 struct ipcp_agg_lattice
*aglat
;
2389 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
2391 if (src
->offset
== -1)
2392 return (ipa_lat_is_single_const (&plats
->itself
)
2393 && values_equal_for_ipcp_p (src
->val
->value
,
2394 plats
->itself
.values
->value
));
2397 if (plats
->aggs_bottom
|| plats
->aggs_contain_variable
)
2399 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2400 if (aglat
->offset
== src
->offset
)
2401 return (ipa_lat_is_single_const (aglat
)
2402 && values_equal_for_ipcp_p (src
->val
->value
,
2403 aglat
->values
->value
));
2409 /* Get the next clone in the linked list of clones of an edge. */
2411 static inline struct cgraph_edge
*
2412 get_next_cgraph_edge_clone (struct cgraph_edge
*cs
)
2414 return next_edge_clone
[cs
->uid
];
2417 /* Given VAL, iterate over all its sources and if they still hold, add their
2418 edge frequency and their number into *FREQUENCY and *CALLER_COUNT
2422 get_info_about_necessary_edges (struct ipcp_value
*val
, int *freq_sum
,
2423 gcov_type
*count_sum
, int *caller_count
)
2425 struct ipcp_value_source
*src
;
2426 int freq
= 0, count
= 0;
2430 for (src
= val
->sources
; src
; src
= src
->next
)
2432 struct cgraph_edge
*cs
= src
->cs
;
2435 if (cgraph_edge_brings_value_p (cs
, src
))
2438 freq
+= cs
->frequency
;
2440 hot
|= cgraph_maybe_hot_edge_p (cs
);
2442 cs
= get_next_cgraph_edge_clone (cs
);
2448 *caller_count
= count
;
2452 /* Return a vector of incoming edges that do bring value VAL. It is assumed
2453 their number is known and equal to CALLER_COUNT. */
2455 static vec
<cgraph_edge_p
>
2456 gather_edges_for_value (struct ipcp_value
*val
, int caller_count
)
2458 struct ipcp_value_source
*src
;
2459 vec
<cgraph_edge_p
> ret
;
2461 ret
.create (caller_count
);
2462 for (src
= val
->sources
; src
; src
= src
->next
)
2464 struct cgraph_edge
*cs
= src
->cs
;
2467 if (cgraph_edge_brings_value_p (cs
, src
))
2468 ret
.quick_push (cs
);
2469 cs
= get_next_cgraph_edge_clone (cs
);
2476 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
2477 Return it or NULL if for some reason it cannot be created. */
2479 static struct ipa_replace_map
*
2480 get_replacement_map (struct ipa_node_params
*info
, tree value
, int parm_num
)
2482 struct ipa_replace_map
*replace_map
;
2485 replace_map
= ggc_alloc_ipa_replace_map ();
2488 fprintf (dump_file
, " replacing ");
2489 ipa_dump_param (dump_file
, info
, parm_num
);
2491 fprintf (dump_file
, " with const ");
2492 print_generic_expr (dump_file
, value
, 0);
2493 fprintf (dump_file
, "\n");
2495 replace_map
->old_tree
= NULL
;
2496 replace_map
->parm_num
= parm_num
;
2497 replace_map
->new_tree
= value
;
2498 replace_map
->replace_p
= true;
2499 replace_map
->ref_p
= false;
2504 /* Dump new profiling counts */
2507 dump_profile_updates (struct cgraph_node
*orig_node
,
2508 struct cgraph_node
*new_node
)
2510 struct cgraph_edge
*cs
;
2512 fprintf (dump_file
, " setting count of the specialized node to "
2513 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) new_node
->count
);
2514 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
2515 fprintf (dump_file
, " edge to %s has count "
2516 HOST_WIDE_INT_PRINT_DEC
"\n",
2517 cs
->callee
->name (), (HOST_WIDE_INT
) cs
->count
);
2519 fprintf (dump_file
, " setting count of the original node to "
2520 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) orig_node
->count
);
2521 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
2522 fprintf (dump_file
, " edge to %s is left with "
2523 HOST_WIDE_INT_PRINT_DEC
"\n",
2524 cs
->callee
->name (), (HOST_WIDE_INT
) cs
->count
);
2527 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
2528 their profile information to reflect this. */
2531 update_profiling_info (struct cgraph_node
*orig_node
,
2532 struct cgraph_node
*new_node
)
2534 struct cgraph_edge
*cs
;
2535 struct caller_statistics stats
;
2536 gcov_type new_sum
, orig_sum
;
2537 gcov_type remainder
, orig_node_count
= orig_node
->count
;
2539 if (orig_node_count
== 0)
2542 init_caller_stats (&stats
);
2543 cgraph_for_node_and_aliases (orig_node
, gather_caller_stats
, &stats
, false);
2544 orig_sum
= stats
.count_sum
;
2545 init_caller_stats (&stats
);
2546 cgraph_for_node_and_aliases (new_node
, gather_caller_stats
, &stats
, false);
2547 new_sum
= stats
.count_sum
;
2549 if (orig_node_count
< orig_sum
+ new_sum
)
2552 fprintf (dump_file
, " Problem: node %s/%i has too low count "
2553 HOST_WIDE_INT_PRINT_DEC
" while the sum of incoming "
2554 "counts is " HOST_WIDE_INT_PRINT_DEC
"\n",
2555 orig_node
->name (), orig_node
->order
,
2556 (HOST_WIDE_INT
) orig_node_count
,
2557 (HOST_WIDE_INT
) (orig_sum
+ new_sum
));
2559 orig_node_count
= (orig_sum
+ new_sum
) * 12 / 10;
2561 fprintf (dump_file
, " proceeding by pretending it was "
2562 HOST_WIDE_INT_PRINT_DEC
"\n",
2563 (HOST_WIDE_INT
) orig_node_count
);
2566 new_node
->count
= new_sum
;
2567 remainder
= orig_node_count
- new_sum
;
2568 orig_node
->count
= remainder
;
2570 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
2572 cs
->count
= apply_probability (cs
->count
,
2573 GCOV_COMPUTE_SCALE (new_sum
,
2578 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
2579 cs
->count
= apply_probability (cs
->count
,
2580 GCOV_COMPUTE_SCALE (remainder
,
2584 dump_profile_updates (orig_node
, new_node
);
2587 /* Update the respective profile of specialized NEW_NODE and the original
2588 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
2589 have been redirected to the specialized version. */
2592 update_specialized_profile (struct cgraph_node
*new_node
,
2593 struct cgraph_node
*orig_node
,
2594 gcov_type redirected_sum
)
2596 struct cgraph_edge
*cs
;
2597 gcov_type new_node_count
, orig_node_count
= orig_node
->count
;
2600 fprintf (dump_file
, " the sum of counts of redirected edges is "
2601 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) redirected_sum
);
2602 if (orig_node_count
== 0)
2605 gcc_assert (orig_node_count
>= redirected_sum
);
2607 new_node_count
= new_node
->count
;
2608 new_node
->count
+= redirected_sum
;
2609 orig_node
->count
-= redirected_sum
;
2611 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
2613 cs
->count
+= apply_probability (cs
->count
,
2614 GCOV_COMPUTE_SCALE (redirected_sum
,
2619 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
2621 gcov_type dec
= apply_probability (cs
->count
,
2622 GCOV_COMPUTE_SCALE (redirected_sum
,
2624 if (dec
< cs
->count
)
2631 dump_profile_updates (orig_node
, new_node
);
2634 /* Create a specialized version of NODE with known constants and types of
2635 parameters in KNOWN_VALS and redirect all edges in CALLERS to it. */
2637 static struct cgraph_node
*
2638 create_specialized_node (struct cgraph_node
*node
,
2639 vec
<tree
> known_vals
,
2640 struct ipa_agg_replacement_value
*aggvals
,
2641 vec
<cgraph_edge_p
> callers
)
2643 struct ipa_node_params
*new_info
, *info
= IPA_NODE_REF (node
);
2644 vec
<ipa_replace_map_p
, va_gc
> *replace_trees
= NULL
;
2645 struct ipa_agg_replacement_value
*av
;
2646 struct cgraph_node
*new_node
;
2647 int i
, count
= ipa_get_param_count (info
);
2648 bitmap args_to_skip
;
2650 gcc_assert (!info
->ipcp_orig_node
);
2652 if (node
->local
.can_change_signature
)
2654 args_to_skip
= BITMAP_GGC_ALLOC ();
2655 for (i
= 0; i
< count
; i
++)
2657 tree t
= known_vals
[i
];
2659 if ((t
&& TREE_CODE (t
) != TREE_BINFO
)
2660 || !ipa_is_param_used (info
, i
))
2661 bitmap_set_bit (args_to_skip
, i
);
2666 args_to_skip
= NULL
;
2667 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2668 fprintf (dump_file
, " cannot change function signature\n");
2671 for (i
= 0; i
< count
; i
++)
2673 tree t
= known_vals
[i
];
2674 if (t
&& TREE_CODE (t
) != TREE_BINFO
)
2676 struct ipa_replace_map
*replace_map
;
2678 replace_map
= get_replacement_map (info
, t
, i
);
2680 vec_safe_push (replace_trees
, replace_map
);
2684 new_node
= cgraph_create_virtual_clone (node
, callers
, replace_trees
,
2685 args_to_skip
, "constprop");
2686 ipa_set_node_agg_value_chain (new_node
, aggvals
);
2687 for (av
= aggvals
; av
; av
= av
->next
)
2688 ipa_maybe_record_reference (new_node
, av
->value
,
2689 IPA_REF_ADDR
, NULL
);
2691 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2693 fprintf (dump_file
, " the new node is %s/%i.\n",
2694 new_node
->name (), new_node
->order
);
2696 ipa_dump_agg_replacement_values (dump_file
, aggvals
);
2698 gcc_checking_assert (ipa_node_params_vector
.exists ()
2699 && (ipa_node_params_vector
.length ()
2700 > (unsigned) cgraph_max_uid
));
2701 update_profiling_info (node
, new_node
);
2702 new_info
= IPA_NODE_REF (new_node
);
2703 new_info
->ipcp_orig_node
= node
;
2704 new_info
->known_vals
= known_vals
;
2706 ipcp_discover_new_direct_edges (new_node
, known_vals
, aggvals
);
2712 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
2713 KNOWN_VALS with constants and types that are also known for all of the
2717 find_more_scalar_values_for_callers_subset (struct cgraph_node
*node
,
2718 vec
<tree
> known_vals
,
2719 vec
<cgraph_edge_p
> callers
)
2721 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2722 int i
, count
= ipa_get_param_count (info
);
2724 for (i
= 0; i
< count
; i
++)
2726 struct cgraph_edge
*cs
;
2727 tree newval
= NULL_TREE
;
2730 if (ipa_get_scalar_lat (info
, i
)->bottom
|| known_vals
[i
])
2733 FOR_EACH_VEC_ELT (callers
, j
, cs
)
2735 struct ipa_jump_func
*jump_func
;
2738 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
)))
2743 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
2744 t
= ipa_value_from_jfunc (IPA_NODE_REF (cs
->caller
), jump_func
);
2747 && !values_equal_for_ipcp_p (t
, newval
)))
2758 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2760 fprintf (dump_file
, " adding an extra known scalar value ");
2761 print_ipcp_constant_value (dump_file
, newval
);
2762 fprintf (dump_file
, " for ");
2763 ipa_dump_param (dump_file
, info
, i
);
2764 fprintf (dump_file
, "\n");
2767 known_vals
[i
] = newval
;
2772 /* Go through PLATS and create a vector of values consisting of values and
2773 offsets (minus OFFSET) of lattices that contain only a single value. */
2775 static vec
<ipa_agg_jf_item
>
2776 copy_plats_to_inter (struct ipcp_param_lattices
*plats
, HOST_WIDE_INT offset
)
2778 vec
<ipa_agg_jf_item
> res
= vNULL
;
2780 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
2783 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2784 if (ipa_lat_is_single_const (aglat
))
2786 struct ipa_agg_jf_item ti
;
2787 ti
.offset
= aglat
->offset
- offset
;
2788 ti
.value
= aglat
->values
->value
;
2794 /* Intersect all values in INTER with single value lattices in PLATS (while
2795 subtracting OFFSET). */
2798 intersect_with_plats (struct ipcp_param_lattices
*plats
,
2799 vec
<ipa_agg_jf_item
> *inter
,
2800 HOST_WIDE_INT offset
)
2802 struct ipcp_agg_lattice
*aglat
;
2803 struct ipa_agg_jf_item
*item
;
2806 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
2812 aglat
= plats
->aggs
;
2813 FOR_EACH_VEC_ELT (*inter
, k
, item
)
2820 if (aglat
->offset
- offset
> item
->offset
)
2822 if (aglat
->offset
- offset
== item
->offset
)
2824 gcc_checking_assert (item
->value
);
2825 if (values_equal_for_ipcp_p (item
->value
, aglat
->values
->value
))
2829 aglat
= aglat
->next
;
2832 item
->value
= NULL_TREE
;
2836 /* Copy agggregate replacement values of NODE (which is an IPA-CP clone) to the
2837 vector result while subtracting OFFSET from the individual value offsets. */
2839 static vec
<ipa_agg_jf_item
>
2840 agg_replacements_to_vector (struct cgraph_node
*node
, int index
,
2841 HOST_WIDE_INT offset
)
2843 struct ipa_agg_replacement_value
*av
;
2844 vec
<ipa_agg_jf_item
> res
= vNULL
;
2846 for (av
= ipa_get_agg_replacements_for_node (node
); av
; av
= av
->next
)
2847 if (av
->index
== index
2848 && (av
->offset
- offset
) >= 0)
2850 struct ipa_agg_jf_item item
;
2851 gcc_checking_assert (av
->value
);
2852 item
.offset
= av
->offset
- offset
;
2853 item
.value
= av
->value
;
2854 res
.safe_push (item
);
2860 /* Intersect all values in INTER with those that we have already scheduled to
2861 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
2862 (while subtracting OFFSET). */
2865 intersect_with_agg_replacements (struct cgraph_node
*node
, int index
,
2866 vec
<ipa_agg_jf_item
> *inter
,
2867 HOST_WIDE_INT offset
)
2869 struct ipa_agg_replacement_value
*srcvals
;
2870 struct ipa_agg_jf_item
*item
;
2873 srcvals
= ipa_get_agg_replacements_for_node (node
);
2880 FOR_EACH_VEC_ELT (*inter
, i
, item
)
2882 struct ipa_agg_replacement_value
*av
;
2886 for (av
= srcvals
; av
; av
= av
->next
)
2888 gcc_checking_assert (av
->value
);
2889 if (av
->index
== index
2890 && av
->offset
- offset
== item
->offset
)
2892 if (values_equal_for_ipcp_p (item
->value
, av
->value
))
2898 item
->value
= NULL_TREE
;
2902 /* Intersect values in INTER with aggregate values that come along edge CS to
2903 parameter number INDEX and return it. If INTER does not actually exist yet,
2904 copy all incoming values to it. If we determine we ended up with no values
2905 whatsoever, return a released vector. */
2907 static vec
<ipa_agg_jf_item
>
2908 intersect_aggregates_with_edge (struct cgraph_edge
*cs
, int index
,
2909 vec
<ipa_agg_jf_item
> inter
)
2911 struct ipa_jump_func
*jfunc
;
2912 jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), index
);
2913 if (jfunc
->type
== IPA_JF_PASS_THROUGH
2914 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
2916 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2917 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
2919 if (caller_info
->ipcp_orig_node
)
2921 struct cgraph_node
*orig_node
= caller_info
->ipcp_orig_node
;
2922 struct ipcp_param_lattices
*orig_plats
;
2923 orig_plats
= ipa_get_parm_lattices (IPA_NODE_REF (orig_node
),
2925 if (agg_pass_through_permissible_p (orig_plats
, jfunc
))
2927 if (!inter
.exists ())
2928 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, 0);
2930 intersect_with_agg_replacements (cs
->caller
, src_idx
,
2936 struct ipcp_param_lattices
*src_plats
;
2937 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2938 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
2940 /* Currently we do not produce clobber aggregate jump
2941 functions, adjust when we do. */
2942 gcc_checking_assert (!jfunc
->agg
.items
);
2943 if (!inter
.exists ())
2944 inter
= copy_plats_to_inter (src_plats
, 0);
2946 intersect_with_plats (src_plats
, &inter
, 0);
2950 else if (jfunc
->type
== IPA_JF_ANCESTOR
2951 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
2953 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2954 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
2955 struct ipcp_param_lattices
*src_plats
;
2956 HOST_WIDE_INT delta
= ipa_get_jf_ancestor_offset (jfunc
);
2958 if (caller_info
->ipcp_orig_node
)
2960 if (!inter
.exists ())
2961 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, delta
);
2963 intersect_with_agg_replacements (cs
->caller
, src_idx
, &inter
,
2968 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);;
2969 /* Currently we do not produce clobber aggregate jump
2970 functions, adjust when we do. */
2971 gcc_checking_assert (!src_plats
->aggs
|| !jfunc
->agg
.items
);
2972 if (!inter
.exists ())
2973 inter
= copy_plats_to_inter (src_plats
, delta
);
2975 intersect_with_plats (src_plats
, &inter
, delta
);
2978 else if (jfunc
->agg
.items
)
2980 struct ipa_agg_jf_item
*item
;
2983 if (!inter
.exists ())
2984 for (unsigned i
= 0; i
< jfunc
->agg
.items
->length (); i
++)
2985 inter
.safe_push ((*jfunc
->agg
.items
)[i
]);
2987 FOR_EACH_VEC_ELT (inter
, k
, item
)
2990 bool found
= false;;
2995 while ((unsigned) l
< jfunc
->agg
.items
->length ())
2997 struct ipa_agg_jf_item
*ti
;
2998 ti
= &(*jfunc
->agg
.items
)[l
];
2999 if (ti
->offset
> item
->offset
)
3001 if (ti
->offset
== item
->offset
)
3003 gcc_checking_assert (ti
->value
);
3004 if (values_equal_for_ipcp_p (item
->value
,
3018 return vec
<ipa_agg_jf_item
>();
3023 /* Look at edges in CALLERS and collect all known aggregate values that arrive
3024 from all of them. */
3026 static struct ipa_agg_replacement_value
*
3027 find_aggregate_values_for_callers_subset (struct cgraph_node
*node
,
3028 vec
<cgraph_edge_p
> callers
)
3030 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
3031 struct ipa_agg_replacement_value
*res
= NULL
;
3032 struct cgraph_edge
*cs
;
3033 int i
, j
, count
= ipa_get_param_count (dest_info
);
3035 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3037 int c
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
3042 for (i
= 0; i
< count
; i
++)
3044 struct cgraph_edge
*cs
;
3045 vec
<ipa_agg_jf_item
> inter
= vNULL
;
3046 struct ipa_agg_jf_item
*item
;
3047 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (dest_info
, i
);
3050 /* Among other things, the following check should deal with all by_ref
3052 if (plats
->aggs_bottom
)
3055 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3057 inter
= intersect_aggregates_with_edge (cs
, i
, inter
);
3059 if (!inter
.exists ())
3063 FOR_EACH_VEC_ELT (inter
, j
, item
)
3065 struct ipa_agg_replacement_value
*v
;
3070 v
= ggc_alloc_ipa_agg_replacement_value ();
3072 v
->offset
= item
->offset
;
3073 v
->value
= item
->value
;
3074 v
->by_ref
= plats
->aggs_by_ref
;
3080 if (inter
.exists ())
3086 /* Turn KNOWN_AGGS into a list of aggreate replacement values. */
3088 static struct ipa_agg_replacement_value
*
3089 known_aggs_to_agg_replacement_list (vec
<ipa_agg_jump_function
> known_aggs
)
3091 struct ipa_agg_replacement_value
*res
= NULL
;
3092 struct ipa_agg_jump_function
*aggjf
;
3093 struct ipa_agg_jf_item
*item
;
3096 FOR_EACH_VEC_ELT (known_aggs
, i
, aggjf
)
3097 FOR_EACH_VEC_SAFE_ELT (aggjf
->items
, j
, item
)
3099 struct ipa_agg_replacement_value
*v
;
3100 v
= ggc_alloc_ipa_agg_replacement_value ();
3102 v
->offset
= item
->offset
;
3103 v
->value
= item
->value
;
3104 v
->by_ref
= aggjf
->by_ref
;
3111 /* Determine whether CS also brings all scalar values that the NODE is
3115 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge
*cs
,
3116 struct cgraph_node
*node
)
3118 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
3119 int count
= ipa_get_param_count (dest_info
);
3120 struct ipa_node_params
*caller_info
;
3121 struct ipa_edge_args
*args
;
3124 caller_info
= IPA_NODE_REF (cs
->caller
);
3125 args
= IPA_EDGE_REF (cs
);
3126 for (i
= 0; i
< count
; i
++)
3128 struct ipa_jump_func
*jump_func
;
3131 val
= dest_info
->known_vals
[i
];
3135 if (i
>= ipa_get_cs_argument_count (args
))
3137 jump_func
= ipa_get_ith_jump_func (args
, i
);
3138 t
= ipa_value_from_jfunc (caller_info
, jump_func
);
3139 if (!t
|| !values_equal_for_ipcp_p (val
, t
))
3145 /* Determine whether CS also brings all aggregate values that NODE is
3148 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge
*cs
,
3149 struct cgraph_node
*node
)
3151 struct ipa_node_params
*orig_caller_info
= IPA_NODE_REF (cs
->caller
);
3152 struct ipa_agg_replacement_value
*aggval
;
3155 aggval
= ipa_get_agg_replacements_for_node (node
);
3159 count
= ipa_get_param_count (IPA_NODE_REF (node
));
3160 ec
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
3162 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
3163 if (aggval
->index
>= ec
)
3166 if (orig_caller_info
->ipcp_orig_node
)
3167 orig_caller_info
= IPA_NODE_REF (orig_caller_info
->ipcp_orig_node
);
3169 for (i
= 0; i
< count
; i
++)
3171 static vec
<ipa_agg_jf_item
> values
= vec
<ipa_agg_jf_item
>();
3172 struct ipcp_param_lattices
*plats
;
3173 bool interesting
= false;
3174 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
3175 if (aggval
->index
== i
)
3183 plats
= ipa_get_parm_lattices (orig_caller_info
, aggval
->index
);
3184 if (plats
->aggs_bottom
)
3187 values
= intersect_aggregates_with_edge (cs
, i
, values
);
3188 if (!values
.exists ())
3191 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
3192 if (aggval
->index
== i
)
3194 struct ipa_agg_jf_item
*item
;
3197 FOR_EACH_VEC_ELT (values
, j
, item
)
3199 && item
->offset
== av
->offset
3200 && values_equal_for_ipcp_p (item
->value
, av
->value
))
3215 /* Given an original NODE and a VAL for which we have already created a
3216 specialized clone, look whether there are incoming edges that still lead
3217 into the old node but now also bring the requested value and also conform to
3218 all other criteria such that they can be redirected the the special node.
3219 This function can therefore redirect the final edge in a SCC. */
3222 perhaps_add_new_callers (struct cgraph_node
*node
, struct ipcp_value
*val
)
3224 struct ipcp_value_source
*src
;
3225 gcov_type redirected_sum
= 0;
3227 for (src
= val
->sources
; src
; src
= src
->next
)
3229 struct cgraph_edge
*cs
= src
->cs
;
3232 enum availability availability
;
3233 struct cgraph_node
*dst
= cgraph_function_node (cs
->callee
,
3235 if ((dst
== node
|| IPA_NODE_REF (dst
)->is_all_contexts_clone
)
3236 && availability
> AVAIL_OVERWRITABLE
3237 && cgraph_edge_brings_value_p (cs
, src
))
3239 if (cgraph_edge_brings_all_scalars_for_node (cs
, val
->spec_node
)
3240 && cgraph_edge_brings_all_agg_vals_for_node (cs
,
3244 fprintf (dump_file
, " - adding an extra caller %s/%i"
3246 xstrdup (cs
->caller
->name ()),
3248 xstrdup (val
->spec_node
->name ()),
3249 val
->spec_node
->order
);
3251 cgraph_redirect_edge_callee (cs
, val
->spec_node
);
3252 redirected_sum
+= cs
->count
;
3255 cs
= get_next_cgraph_edge_clone (cs
);
3260 update_specialized_profile (val
->spec_node
, node
, redirected_sum
);
3264 /* Copy KNOWN_BINFOS to KNOWN_VALS. */
3267 move_binfos_to_values (vec
<tree
> known_vals
,
3268 vec
<tree
> known_binfos
)
3273 for (i
= 0; known_binfos
.iterate (i
, &t
); i
++)
3278 /* Return true if there is a replacement equivalent to VALUE, INDEX and OFFSET
3279 among those in the AGGVALS list. */
3282 ipcp_val_in_agg_replacements_p (struct ipa_agg_replacement_value
*aggvals
,
3283 int index
, HOST_WIDE_INT offset
, tree value
)
3287 if (aggvals
->index
== index
3288 && aggvals
->offset
== offset
3289 && values_equal_for_ipcp_p (aggvals
->value
, value
))
3291 aggvals
= aggvals
->next
;
3296 /* Decide wheter to create a special version of NODE for value VAL of parameter
3297 at the given INDEX. If OFFSET is -1, the value is for the parameter itself,
3298 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS,
3299 KNOWN_BINFOS and KNOWN_AGGS describe the other already known values. */
3302 decide_about_value (struct cgraph_node
*node
, int index
, HOST_WIDE_INT offset
,
3303 struct ipcp_value
*val
, vec
<tree
> known_csts
,
3304 vec
<tree
> known_binfos
)
3306 struct ipa_agg_replacement_value
*aggvals
;
3307 int freq_sum
, caller_count
;
3308 gcov_type count_sum
;
3309 vec
<cgraph_edge_p
> callers
;
3314 perhaps_add_new_callers (node
, val
);
3317 else if (val
->local_size_cost
+ overall_size
> max_new_size
)
3319 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3320 fprintf (dump_file
, " Ignoring candidate value because "
3321 "max_new_size would be reached with %li.\n",
3322 val
->local_size_cost
+ overall_size
);
3325 else if (!get_info_about_necessary_edges (val
, &freq_sum
, &count_sum
,
3329 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3331 fprintf (dump_file
, " - considering value ");
3332 print_ipcp_constant_value (dump_file
, val
->value
);
3333 fprintf (dump_file
, " for ");
3334 ipa_dump_param (dump_file
, IPA_NODE_REF (node
), index
);
3336 fprintf (dump_file
, ", offset: " HOST_WIDE_INT_PRINT_DEC
, offset
);
3337 fprintf (dump_file
, " (caller_count: %i)\n", caller_count
);
3340 if (!good_cloning_opportunity_p (node
, val
->local_time_benefit
,
3341 freq_sum
, count_sum
,
3342 val
->local_size_cost
)
3343 && !good_cloning_opportunity_p (node
,
3344 val
->local_time_benefit
3345 + val
->prop_time_benefit
,
3346 freq_sum
, count_sum
,
3347 val
->local_size_cost
3348 + val
->prop_size_cost
))
3352 fprintf (dump_file
, " Creating a specialized node of %s/%i.\n",
3353 node
->name (), node
->order
);
3355 callers
= gather_edges_for_value (val
, caller_count
);
3356 kv
= known_csts
.copy ();
3357 move_binfos_to_values (kv
, known_binfos
);
3359 kv
[index
] = val
->value
;
3360 find_more_scalar_values_for_callers_subset (node
, kv
, callers
);
3361 aggvals
= find_aggregate_values_for_callers_subset (node
, callers
);
3362 gcc_checking_assert (offset
== -1
3363 || ipcp_val_in_agg_replacements_p (aggvals
, index
,
3364 offset
, val
->value
));
3365 val
->spec_node
= create_specialized_node (node
, kv
, aggvals
, callers
);
3366 overall_size
+= val
->local_size_cost
;
3368 /* TODO: If for some lattice there is only one other known value
3369 left, make a special node for it too. */
3374 /* Decide whether and what specialized clones of NODE should be created. */
3377 decide_whether_version_node (struct cgraph_node
*node
)
3379 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3380 int i
, count
= ipa_get_param_count (info
);
3381 vec
<tree
> known_csts
, known_binfos
;
3382 vec
<ipa_agg_jump_function
> known_aggs
= vNULL
;
3388 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3389 fprintf (dump_file
, "\nEvaluating opportunities for %s/%i.\n",
3390 node
->name (), node
->order
);
3392 gather_context_independent_values (info
, &known_csts
, &known_binfos
,
3393 info
->do_clone_for_all_contexts
? &known_aggs
3396 for (i
= 0; i
< count
;i
++)
3398 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3399 struct ipcp_lattice
*lat
= &plats
->itself
;
3400 struct ipcp_value
*val
;
3404 && !known_binfos
[i
])
3405 for (val
= lat
->values
; val
; val
= val
->next
)
3406 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
3409 if (!plats
->aggs_bottom
)
3411 struct ipcp_agg_lattice
*aglat
;
3412 struct ipcp_value
*val
;
3413 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3414 if (!aglat
->bottom
&& aglat
->values
3415 /* If the following is false, the one value is in
3417 && (plats
->aggs_contain_variable
3418 || !ipa_lat_is_single_const (aglat
)))
3419 for (val
= aglat
->values
; val
; val
= val
->next
)
3420 ret
|= decide_about_value (node
, i
, aglat
->offset
, val
,
3421 known_csts
, known_binfos
);
3423 info
= IPA_NODE_REF (node
);
3426 if (info
->do_clone_for_all_contexts
)
3428 struct cgraph_node
*clone
;
3429 vec
<cgraph_edge_p
> callers
;
3432 fprintf (dump_file
, " - Creating a specialized node of %s/%i "
3433 "for all known contexts.\n", node
->name (),
3436 callers
= collect_callers_of_node (node
);
3437 move_binfos_to_values (known_csts
, known_binfos
);
3438 clone
= create_specialized_node (node
, known_csts
,
3439 known_aggs_to_agg_replacement_list (known_aggs
),
3441 info
= IPA_NODE_REF (node
);
3442 info
->do_clone_for_all_contexts
= false;
3443 IPA_NODE_REF (clone
)->is_all_contexts_clone
= true;
3444 for (i
= 0; i
< count
; i
++)
3445 vec_free (known_aggs
[i
].items
);
3446 known_aggs
.release ();
3450 known_csts
.release ();
3452 known_binfos
.release ();
3456 /* Transitively mark all callees of NODE within the same SCC as not dead. */
3459 spread_undeadness (struct cgraph_node
*node
)
3461 struct cgraph_edge
*cs
;
3463 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
3464 if (ipa_edge_within_scc (cs
))
3466 struct cgraph_node
*callee
;
3467 struct ipa_node_params
*info
;
3469 callee
= cgraph_function_node (cs
->callee
, NULL
);
3470 info
= IPA_NODE_REF (callee
);
3472 if (info
->node_dead
)
3474 info
->node_dead
= 0;
3475 spread_undeadness (callee
);
3480 /* Return true if NODE has a caller from outside of its SCC that is not
3481 dead. Worker callback for cgraph_for_node_and_aliases. */
3484 has_undead_caller_from_outside_scc_p (struct cgraph_node
*node
,
3485 void *data ATTRIBUTE_UNUSED
)
3487 struct cgraph_edge
*cs
;
3489 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
3490 if (cs
->caller
->thunk
.thunk_p
3491 && cgraph_for_node_and_aliases (cs
->caller
,
3492 has_undead_caller_from_outside_scc_p
,
3495 else if (!ipa_edge_within_scc (cs
)
3496 && !IPA_NODE_REF (cs
->caller
)->node_dead
)
3502 /* Identify nodes within the same SCC as NODE which are no longer needed
3503 because of new clones and will be removed as unreachable. */
3506 identify_dead_nodes (struct cgraph_node
*node
)
3508 struct cgraph_node
*v
;
3509 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
3510 if (cgraph_will_be_removed_from_program_if_no_direct_calls (v
)
3511 && !cgraph_for_node_and_aliases (v
,
3512 has_undead_caller_from_outside_scc_p
,
3514 IPA_NODE_REF (v
)->node_dead
= 1;
3516 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
3517 if (!IPA_NODE_REF (v
)->node_dead
)
3518 spread_undeadness (v
);
3520 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3522 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
3523 if (IPA_NODE_REF (v
)->node_dead
)
3524 fprintf (dump_file
, " Marking node as dead: %s/%i.\n",
3525 v
->name (), v
->order
);
3529 /* The decision stage. Iterate over the topological order of call graph nodes
3530 TOPO and make specialized clones if deemed beneficial. */
3533 ipcp_decision_stage (struct topo_info
*topo
)
3538 fprintf (dump_file
, "\nIPA decision stage:\n\n");
3540 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
3542 struct cgraph_node
*node
= topo
->order
[i
];
3543 bool change
= false, iterate
= true;
3547 struct cgraph_node
*v
;
3549 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
3550 if (cgraph_function_with_gimple_body_p (v
)
3551 && ipcp_versionable_function_p (v
))
3552 iterate
|= decide_whether_version_node (v
);
3557 identify_dead_nodes (node
);
3561 /* The IPCP driver. */
3566 struct cgraph_2edge_hook_list
*edge_duplication_hook_holder
;
3567 struct topo_info topo
;
3569 ipa_check_create_node_params ();
3570 ipa_check_create_edge_args ();
3571 grow_next_edge_clone_vector ();
3572 edge_duplication_hook_holder
=
3573 cgraph_add_edge_duplication_hook (&ipcp_edge_duplication_hook
, NULL
);
3574 ipcp_values_pool
= create_alloc_pool ("IPA-CP values",
3575 sizeof (struct ipcp_value
), 32);
3576 ipcp_sources_pool
= create_alloc_pool ("IPA-CP value sources",
3577 sizeof (struct ipcp_value_source
), 64);
3578 ipcp_agg_lattice_pool
= create_alloc_pool ("IPA_CP aggregate lattices",
3579 sizeof (struct ipcp_agg_lattice
),
3583 fprintf (dump_file
, "\nIPA structures before propagation:\n");
3584 if (dump_flags
& TDF_DETAILS
)
3585 ipa_print_all_params (dump_file
);
3586 ipa_print_all_jump_functions (dump_file
);
3589 /* Topological sort. */
3590 build_toporder_info (&topo
);
3591 /* Do the interprocedural propagation. */
3592 ipcp_propagate_stage (&topo
);
3593 /* Decide what constant propagation and cloning should be performed. */
3594 ipcp_decision_stage (&topo
);
3596 /* Free all IPCP structures. */
3597 free_toporder_info (&topo
);
3598 next_edge_clone
.release ();
3599 cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder
);
3600 ipa_free_all_structures_after_ipa_cp ();
3602 fprintf (dump_file
, "\nIPA constant propagation end\n");
3606 /* Initialization and computation of IPCP data structures. This is the initial
3607 intraprocedural analysis of functions, which gathers information to be
3608 propagated later on. */
3611 ipcp_generate_summary (void)
3613 struct cgraph_node
*node
;
3616 fprintf (dump_file
, "\nIPA constant propagation start:\n");
3617 ipa_register_cgraph_hooks ();
3619 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
3621 node
->local
.versionable
3622 = tree_versionable_function_p (node
->decl
);
3623 ipa_analyze_node (node
);
3627 /* Write ipcp summary for nodes in SET. */
3630 ipcp_write_summary (void)
3632 ipa_prop_write_jump_functions ();
3635 /* Read ipcp summary. */
3638 ipcp_read_summary (void)
3640 ipa_prop_read_jump_functions ();
3643 /* Gate for IPCP optimization. */
3646 cgraph_gate_cp (void)
3648 /* FIXME: We should remove the optimize check after we ensure we never run
3649 IPA passes when not optimizing. */
3650 return flag_ipa_cp
&& optimize
;
3655 const pass_data pass_data_ipa_cp
=
3657 IPA_PASS
, /* type */
3659 OPTGROUP_NONE
, /* optinfo_flags */
3660 true, /* has_gate */
3661 true, /* has_execute */
3662 TV_IPA_CONSTANT_PROP
, /* tv_id */
3663 0, /* properties_required */
3664 0, /* properties_provided */
3665 0, /* properties_destroyed */
3666 0, /* todo_flags_start */
3667 ( TODO_dump_symtab
| TODO_remove_functions
), /* todo_flags_finish */
3670 class pass_ipa_cp
: public ipa_opt_pass_d
3673 pass_ipa_cp (gcc::context
*ctxt
)
3674 : ipa_opt_pass_d (pass_data_ipa_cp
, ctxt
,
3675 ipcp_generate_summary
, /* generate_summary */
3676 ipcp_write_summary
, /* write_summary */
3677 ipcp_read_summary
, /* read_summary */
3678 ipa_prop_write_all_agg_replacement
, /*
3679 write_optimization_summary */
3680 ipa_prop_read_all_agg_replacement
, /*
3681 read_optimization_summary */
3682 NULL
, /* stmt_fixup */
3683 0, /* function_transform_todo_flags_start */
3684 ipcp_transform_function
, /* function_transform */
3685 NULL
) /* variable_transform */
3688 /* opt_pass methods: */
3689 bool gate () { return cgraph_gate_cp (); }
3690 unsigned int execute () { return ipcp_driver (); }
3692 }; // class pass_ipa_cp
3697 make_pass_ipa_cp (gcc::context
*ctxt
)
3699 return new pass_ipa_cp (ctxt
);