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"
110 #include "ipa-prop.h"
111 #include "tree-flow.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 /* Return true iff the CS is an edge within a strongly connected component as
291 computed by ipa_reduced_postorder. */
294 edge_within_scc (struct cgraph_edge
*cs
)
296 struct ipa_dfs_info
*caller_dfs
= (struct ipa_dfs_info
*) cs
->caller
->symbol
.aux
;
297 struct ipa_dfs_info
*callee_dfs
;
298 struct cgraph_node
*callee
= cgraph_function_node (cs
->callee
, NULL
);
300 callee_dfs
= (struct ipa_dfs_info
*) callee
->symbol
.aux
;
303 && caller_dfs
->scc_no
== callee_dfs
->scc_no
);
306 /* Print V which is extracted from a value in a lattice to F. */
309 print_ipcp_constant_value (FILE * f
, tree v
)
311 if (TREE_CODE (v
) == TREE_BINFO
)
313 fprintf (f
, "BINFO ");
314 print_generic_expr (f
, BINFO_TYPE (v
), 0);
316 else if (TREE_CODE (v
) == ADDR_EXPR
317 && TREE_CODE (TREE_OPERAND (v
, 0)) == CONST_DECL
)
320 print_generic_expr (f
, DECL_INITIAL (TREE_OPERAND (v
, 0)), 0);
323 print_generic_expr (f
, v
, 0);
326 /* Print a lattice LAT to F. */
329 print_lattice (FILE * f
, struct ipcp_lattice
*lat
,
330 bool dump_sources
, bool dump_benefits
)
332 struct ipcp_value
*val
;
337 fprintf (f
, "BOTTOM\n");
341 if (!lat
->values_count
&& !lat
->contains_variable
)
343 fprintf (f
, "TOP\n");
347 if (lat
->contains_variable
)
349 fprintf (f
, "VARIABLE");
355 for (val
= lat
->values
; val
; val
= val
->next
)
357 if (dump_benefits
&& prev
)
359 else if (!dump_benefits
&& prev
)
364 print_ipcp_constant_value (f
, val
->value
);
368 struct ipcp_value_source
*s
;
370 fprintf (f
, " [from:");
371 for (s
= val
->sources
; s
; s
= s
->next
)
372 fprintf (f
, " %i(%i)", s
->cs
->caller
->uid
,s
->cs
->frequency
);
377 fprintf (f
, " [loc_time: %i, loc_size: %i, "
378 "prop_time: %i, prop_size: %i]\n",
379 val
->local_time_benefit
, val
->local_size_cost
,
380 val
->prop_time_benefit
, val
->prop_size_cost
);
386 /* Print all ipcp_lattices of all functions to F. */
389 print_all_lattices (FILE * f
, bool dump_sources
, bool dump_benefits
)
391 struct cgraph_node
*node
;
394 fprintf (f
, "\nLattices:\n");
395 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
397 struct ipa_node_params
*info
;
399 info
= IPA_NODE_REF (node
);
400 fprintf (f
, " Node: %s/%i:\n", cgraph_node_name (node
), node
->uid
);
401 count
= ipa_get_param_count (info
);
402 for (i
= 0; i
< count
; i
++)
404 struct ipcp_agg_lattice
*aglat
;
405 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
406 fprintf (f
, " param [%d]: ", i
);
407 print_lattice (f
, &plats
->itself
, dump_sources
, dump_benefits
);
409 if (plats
->virt_call
)
410 fprintf (f
, " virt_call flag set\n");
412 if (plats
->aggs_bottom
)
414 fprintf (f
, " AGGS BOTTOM\n");
417 if (plats
->aggs_contain_variable
)
418 fprintf (f
, " AGGS VARIABLE\n");
419 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
421 fprintf (f
, " %soffset " HOST_WIDE_INT_PRINT_DEC
": ",
422 plats
->aggs_by_ref
? "ref " : "", aglat
->offset
);
423 print_lattice (f
, aglat
, dump_sources
, dump_benefits
);
429 /* Determine whether it is at all technically possible to create clones of NODE
430 and store this information in the ipa_node_params structure associated
434 determine_versionability (struct cgraph_node
*node
)
436 const char *reason
= NULL
;
438 /* There are a number of generic reasons functions cannot be versioned. We
439 also cannot remove parameters if there are type attributes such as fnspec
441 if (node
->alias
|| node
->thunk
.thunk_p
)
442 reason
= "alias or thunk";
443 else if (!node
->local
.versionable
)
444 reason
= "not a tree_versionable_function";
445 else if (cgraph_function_body_availability (node
) <= AVAIL_OVERWRITABLE
)
446 reason
= "insufficient body availability";
448 if (reason
&& dump_file
&& !node
->alias
&& !node
->thunk
.thunk_p
)
449 fprintf (dump_file
, "Function %s/%i is not versionable, reason: %s.\n",
450 cgraph_node_name (node
), node
->uid
, reason
);
452 node
->local
.versionable
= (reason
== NULL
);
455 /* Return true if it is at all technically possible to create clones of a
459 ipcp_versionable_function_p (struct cgraph_node
*node
)
461 return node
->local
.versionable
;
464 /* Structure holding accumulated information about callers of a node. */
466 struct caller_statistics
469 int n_calls
, n_hot_calls
, freq_sum
;
472 /* Initialize fields of STAT to zeroes. */
475 init_caller_stats (struct caller_statistics
*stats
)
477 stats
->count_sum
= 0;
479 stats
->n_hot_calls
= 0;
483 /* Worker callback of cgraph_for_node_and_aliases accumulating statistics of
484 non-thunk incoming edges to NODE. */
487 gather_caller_stats (struct cgraph_node
*node
, void *data
)
489 struct caller_statistics
*stats
= (struct caller_statistics
*) data
;
490 struct cgraph_edge
*cs
;
492 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
493 if (cs
->caller
->thunk
.thunk_p
)
494 cgraph_for_node_and_aliases (cs
->caller
, gather_caller_stats
,
498 stats
->count_sum
+= cs
->count
;
499 stats
->freq_sum
+= cs
->frequency
;
501 if (cgraph_maybe_hot_edge_p (cs
))
502 stats
->n_hot_calls
++;
508 /* Return true if this NODE is viable candidate for cloning. */
511 ipcp_cloning_candidate_p (struct cgraph_node
*node
)
513 struct caller_statistics stats
;
515 gcc_checking_assert (cgraph_function_with_gimple_body_p (node
));
517 if (!flag_ipa_cp_clone
)
520 fprintf (dump_file
, "Not considering %s for cloning; "
521 "-fipa-cp-clone disabled.\n",
522 cgraph_node_name (node
));
526 if (!optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node
->symbol
.decl
)))
529 fprintf (dump_file
, "Not considering %s for cloning; "
530 "optimizing it for size.\n",
531 cgraph_node_name (node
));
535 init_caller_stats (&stats
);
536 cgraph_for_node_and_aliases (node
, gather_caller_stats
, &stats
, false);
538 if (inline_summary (node
)->self_size
< stats
.n_calls
)
541 fprintf (dump_file
, "Considering %s for cloning; code might shrink.\n",
542 cgraph_node_name (node
));
546 /* When profile is available and function is hot, propagate into it even if
547 calls seems cold; constant propagation can improve function's speed
551 if (stats
.count_sum
> node
->count
* 90 / 100)
554 fprintf (dump_file
, "Considering %s for cloning; "
555 "usually called directly.\n",
556 cgraph_node_name (node
));
560 if (!stats
.n_hot_calls
)
563 fprintf (dump_file
, "Not considering %s for cloning; no hot calls.\n",
564 cgraph_node_name (node
));
568 fprintf (dump_file
, "Considering %s for cloning.\n",
569 cgraph_node_name (node
));
573 /* Arrays representing a topological ordering of call graph nodes and a stack
574 of noes used during constant propagation. */
578 struct cgraph_node
**order
;
579 struct cgraph_node
**stack
;
580 int nnodes
, stack_top
;
583 /* Allocate the arrays in TOPO and topologically sort the nodes into order. */
586 build_toporder_info (struct topo_info
*topo
)
588 topo
->order
= XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
589 topo
->stack
= XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
591 topo
->nnodes
= ipa_reduced_postorder (topo
->order
, true, true, NULL
);
594 /* Free information about strongly connected components and the arrays in
598 free_toporder_info (struct topo_info
*topo
)
600 ipa_free_postorder_info ();
605 /* Add NODE to the stack in TOPO, unless it is already there. */
608 push_node_to_stack (struct topo_info
*topo
, struct cgraph_node
*node
)
610 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
611 if (info
->node_enqueued
)
613 info
->node_enqueued
= 1;
614 topo
->stack
[topo
->stack_top
++] = node
;
617 /* Pop a node from the stack in TOPO and return it or return NULL if the stack
620 static struct cgraph_node
*
621 pop_node_from_stack (struct topo_info
*topo
)
625 struct cgraph_node
*node
;
627 node
= topo
->stack
[topo
->stack_top
];
628 IPA_NODE_REF (node
)->node_enqueued
= 0;
635 /* Set lattice LAT to bottom and return true if it previously was not set as
639 set_lattice_to_bottom (struct ipcp_lattice
*lat
)
641 bool ret
= !lat
->bottom
;
646 /* Mark lattice as containing an unknown value and return true if it previously
647 was not marked as such. */
650 set_lattice_contains_variable (struct ipcp_lattice
*lat
)
652 bool ret
= !lat
->contains_variable
;
653 lat
->contains_variable
= true;
657 /* Set all aggegate lattices in PLATS to bottom and return true if they were
658 not previously set as such. */
661 set_agg_lats_to_bottom (struct ipcp_param_lattices
*plats
)
663 bool ret
= !plats
->aggs_bottom
;
664 plats
->aggs_bottom
= true;
668 /* Mark all aggegate lattices in PLATS as containing an unknown value and
669 return true if they were not previously marked as such. */
672 set_agg_lats_contain_variable (struct ipcp_param_lattices
*plats
)
674 bool ret
= !plats
->aggs_contain_variable
;
675 plats
->aggs_contain_variable
= true;
679 /* Mark bot aggregate and scalar lattices as containing an unknown variable,
680 return true is any of them has not been marked as such so far. */
683 set_all_contains_variable (struct ipcp_param_lattices
*plats
)
685 bool ret
= !plats
->itself
.contains_variable
|| !plats
->aggs_contain_variable
;
686 plats
->itself
.contains_variable
= true;
687 plats
->aggs_contain_variable
= true;
691 /* Initialize ipcp_lattices. */
694 initialize_node_lattices (struct cgraph_node
*node
)
696 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
697 struct cgraph_edge
*ie
;
698 bool disable
= false, variable
= false;
701 gcc_checking_assert (cgraph_function_with_gimple_body_p (node
));
702 if (!node
->local
.local
)
704 /* When cloning is allowed, we can assume that externally visible
705 functions are not called. We will compensate this by cloning
707 if (ipcp_versionable_function_p (node
)
708 && ipcp_cloning_candidate_p (node
))
714 if (disable
|| variable
)
716 for (i
= 0; i
< ipa_get_param_count (info
) ; i
++)
718 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
721 set_lattice_to_bottom (&plats
->itself
);
722 set_agg_lats_to_bottom (plats
);
725 set_all_contains_variable (plats
);
727 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
728 && !node
->alias
&& !node
->thunk
.thunk_p
)
729 fprintf (dump_file
, "Marking all lattices of %s/%i as %s\n",
730 cgraph_node_name (node
), node
->uid
,
731 disable
? "BOTTOM" : "VARIABLE");
734 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
735 if (ie
->indirect_info
->polymorphic
)
737 gcc_checking_assert (ie
->indirect_info
->param_index
>= 0);
738 ipa_get_parm_lattices (info
,
739 ie
->indirect_info
->param_index
)->virt_call
= 1;
743 /* Return the result of a (possibly arithmetic) pass through jump function
744 JFUNC on the constant value INPUT. Return NULL_TREE if that cannot be
745 determined or itself is considered an interprocedural invariant. */
748 ipa_get_jf_pass_through_result (struct ipa_jump_func
*jfunc
, tree input
)
752 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
754 else if (TREE_CODE (input
) == TREE_BINFO
)
757 gcc_checking_assert (is_gimple_ip_invariant (input
));
758 if (TREE_CODE_CLASS (ipa_get_jf_pass_through_operation (jfunc
))
760 restype
= boolean_type_node
;
762 restype
= TREE_TYPE (input
);
763 res
= fold_binary (ipa_get_jf_pass_through_operation (jfunc
), restype
,
764 input
, ipa_get_jf_pass_through_operand (jfunc
));
766 if (res
&& !is_gimple_ip_invariant (res
))
772 /* Return the result of an ancestor jump function JFUNC on the constant value
773 INPUT. Return NULL_TREE if that cannot be determined. */
776 ipa_get_jf_ancestor_result (struct ipa_jump_func
*jfunc
, tree input
)
778 if (TREE_CODE (input
) == TREE_BINFO
)
779 return get_binfo_at_offset (input
,
780 ipa_get_jf_ancestor_offset (jfunc
),
781 ipa_get_jf_ancestor_type (jfunc
));
782 else if (TREE_CODE (input
) == ADDR_EXPR
)
784 tree t
= TREE_OPERAND (input
, 0);
785 t
= build_ref_for_offset (EXPR_LOCATION (t
), t
,
786 ipa_get_jf_ancestor_offset (jfunc
),
787 ipa_get_jf_ancestor_type (jfunc
), NULL
, false);
788 return build_fold_addr_expr (t
);
794 /* Extract the acual BINFO being described by JFUNC which must be a known type
798 ipa_value_from_known_type_jfunc (struct ipa_jump_func
*jfunc
)
800 tree base_binfo
= TYPE_BINFO (ipa_get_jf_known_type_base_type (jfunc
));
803 return get_binfo_at_offset (base_binfo
,
804 ipa_get_jf_known_type_offset (jfunc
),
805 ipa_get_jf_known_type_component_type (jfunc
));
808 /* Determine whether JFUNC evaluates to a known value (that is either a
809 constant or a binfo) and if so, return it. Otherwise return NULL. INFO
810 describes the caller node so that pass-through jump functions can be
814 ipa_value_from_jfunc (struct ipa_node_params
*info
, struct ipa_jump_func
*jfunc
)
816 if (jfunc
->type
== IPA_JF_CONST
)
817 return ipa_get_jf_constant (jfunc
);
818 else if (jfunc
->type
== IPA_JF_KNOWN_TYPE
)
819 return ipa_value_from_known_type_jfunc (jfunc
);
820 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
821 || jfunc
->type
== IPA_JF_ANCESTOR
)
826 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
827 idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
829 idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
831 if (info
->ipcp_orig_node
)
832 input
= info
->known_vals
[idx
];
835 struct ipcp_lattice
*lat
;
839 gcc_checking_assert (!flag_ipa_cp
);
842 lat
= ipa_get_scalar_lat (info
, idx
);
843 if (!ipa_lat_is_single_const (lat
))
845 input
= lat
->values
->value
;
851 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
852 return ipa_get_jf_pass_through_result (jfunc
, input
);
854 return ipa_get_jf_ancestor_result (jfunc
, input
);
861 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
862 bottom, not containing a variable component and without any known value at
866 ipcp_verify_propagated_values (void)
868 struct cgraph_node
*node
;
870 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
872 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
873 int i
, count
= ipa_get_param_count (info
);
875 for (i
= 0; i
< count
; i
++)
877 struct ipcp_lattice
*lat
= ipa_get_scalar_lat (info
, i
);
880 && !lat
->contains_variable
881 && lat
->values_count
== 0)
885 fprintf (dump_file
, "\nIPA lattices after constant "
887 print_all_lattices (dump_file
, true, false);
896 /* Return true iff X and Y should be considered equal values by IPA-CP. */
899 values_equal_for_ipcp_p (tree x
, tree y
)
901 gcc_checking_assert (x
!= NULL_TREE
&& y
!= NULL_TREE
);
906 if (TREE_CODE (x
) == TREE_BINFO
|| TREE_CODE (y
) == TREE_BINFO
)
909 if (TREE_CODE (x
) == ADDR_EXPR
910 && TREE_CODE (y
) == ADDR_EXPR
911 && TREE_CODE (TREE_OPERAND (x
, 0)) == CONST_DECL
912 && TREE_CODE (TREE_OPERAND (y
, 0)) == CONST_DECL
)
913 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x
, 0)),
914 DECL_INITIAL (TREE_OPERAND (y
, 0)), 0);
916 return operand_equal_p (x
, y
, 0);
919 /* Add a new value source to VAL, marking that a value comes from edge CS and
920 (if the underlying jump function is a pass-through or an ancestor one) from
921 a caller value SRC_VAL of a caller parameter described by SRC_INDEX. OFFSET
922 is negative if the source was the scalar value of the parameter itself or
923 the offset within an aggregate. */
926 add_value_source (struct ipcp_value
*val
, struct cgraph_edge
*cs
,
927 struct ipcp_value
*src_val
, int src_idx
, HOST_WIDE_INT offset
)
929 struct ipcp_value_source
*src
;
931 src
= (struct ipcp_value_source
*) pool_alloc (ipcp_sources_pool
);
932 src
->offset
= offset
;
935 src
->index
= src_idx
;
937 src
->next
= val
->sources
;
941 /* Try to add NEWVAL to LAT, potentially creating a new struct ipcp_value for
942 it. CS, SRC_VAL SRC_INDEX and OFFSET are meant for add_value_source and
943 have the same meaning. */
946 add_value_to_lattice (struct ipcp_lattice
*lat
, tree newval
,
947 struct cgraph_edge
*cs
, struct ipcp_value
*src_val
,
948 int src_idx
, HOST_WIDE_INT offset
)
950 struct ipcp_value
*val
;
955 for (val
= lat
->values
; val
; val
= val
->next
)
956 if (values_equal_for_ipcp_p (val
->value
, newval
))
958 if (edge_within_scc (cs
))
960 struct ipcp_value_source
*s
;
961 for (s
= val
->sources
; s
; s
= s
->next
)
968 add_value_source (val
, cs
, src_val
, src_idx
, offset
);
972 if (lat
->values_count
== PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE
))
974 /* We can only free sources, not the values themselves, because sources
975 of other values in this this SCC might point to them. */
976 for (val
= lat
->values
; val
; val
= val
->next
)
980 struct ipcp_value_source
*src
= val
->sources
;
981 val
->sources
= src
->next
;
982 pool_free (ipcp_sources_pool
, src
);
987 return set_lattice_to_bottom (lat
);
991 val
= (struct ipcp_value
*) pool_alloc (ipcp_values_pool
);
992 memset (val
, 0, sizeof (*val
));
994 add_value_source (val
, cs
, src_val
, src_idx
, offset
);
996 val
->next
= lat
->values
;
1001 /* Like above but passes a special value of offset to distinguish that the
1002 origin is the scalar value of the parameter rather than a part of an
1006 add_scalar_value_to_lattice (struct ipcp_lattice
*lat
, tree newval
,
1007 struct cgraph_edge
*cs
,
1008 struct ipcp_value
*src_val
, int src_idx
)
1010 return add_value_to_lattice (lat
, newval
, cs
, src_val
, src_idx
, -1);
1013 /* Propagate values through a pass-through jump function JFUNC associated with
1014 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1015 is the index of the source parameter. */
1018 propagate_vals_accross_pass_through (struct cgraph_edge
*cs
,
1019 struct ipa_jump_func
*jfunc
,
1020 struct ipcp_lattice
*src_lat
,
1021 struct ipcp_lattice
*dest_lat
,
1024 struct ipcp_value
*src_val
;
1027 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
1028 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1029 ret
|= add_scalar_value_to_lattice (dest_lat
, src_val
->value
, cs
,
1031 /* Do not create new values when propagating within an SCC because if there
1032 are arithmetic functions with circular dependencies, there is infinite
1033 number of them and we would just make lattices bottom. */
1034 else if (edge_within_scc (cs
))
1035 ret
= set_lattice_contains_variable (dest_lat
);
1037 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1039 tree cstval
= src_val
->value
;
1041 if (TREE_CODE (cstval
) == TREE_BINFO
)
1043 ret
|= set_lattice_contains_variable (dest_lat
);
1046 cstval
= ipa_get_jf_pass_through_result (jfunc
, cstval
);
1049 ret
|= add_scalar_value_to_lattice (dest_lat
, cstval
, cs
, src_val
,
1052 ret
|= set_lattice_contains_variable (dest_lat
);
1058 /* Propagate values through an ancestor jump function JFUNC associated with
1059 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1060 is the index of the source parameter. */
1063 propagate_vals_accross_ancestor (struct cgraph_edge
*cs
,
1064 struct ipa_jump_func
*jfunc
,
1065 struct ipcp_lattice
*src_lat
,
1066 struct ipcp_lattice
*dest_lat
,
1069 struct ipcp_value
*src_val
;
1072 if (edge_within_scc (cs
))
1073 return set_lattice_contains_variable (dest_lat
);
1075 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1077 tree t
= ipa_get_jf_ancestor_result (jfunc
, src_val
->value
);
1080 ret
|= add_scalar_value_to_lattice (dest_lat
, t
, cs
, src_val
, src_idx
);
1082 ret
|= set_lattice_contains_variable (dest_lat
);
1088 /* Propagate scalar values across jump function JFUNC that is associated with
1089 edge CS and put the values into DEST_LAT. */
1092 propagate_scalar_accross_jump_function (struct cgraph_edge
*cs
,
1093 struct ipa_jump_func
*jfunc
,
1094 struct ipcp_lattice
*dest_lat
)
1096 if (dest_lat
->bottom
)
1099 if (jfunc
->type
== IPA_JF_CONST
1100 || jfunc
->type
== IPA_JF_KNOWN_TYPE
)
1104 if (jfunc
->type
== IPA_JF_KNOWN_TYPE
)
1106 val
= ipa_value_from_known_type_jfunc (jfunc
);
1108 return set_lattice_contains_variable (dest_lat
);
1111 val
= ipa_get_jf_constant (jfunc
);
1112 return add_scalar_value_to_lattice (dest_lat
, val
, cs
, NULL
, 0);
1114 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1115 || jfunc
->type
== IPA_JF_ANCESTOR
)
1117 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1118 struct ipcp_lattice
*src_lat
;
1122 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1123 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1125 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1127 src_lat
= ipa_get_scalar_lat (caller_info
, src_idx
);
1128 if (src_lat
->bottom
)
1129 return set_lattice_contains_variable (dest_lat
);
1131 /* If we would need to clone the caller and cannot, do not propagate. */
1132 if (!ipcp_versionable_function_p (cs
->caller
)
1133 && (src_lat
->contains_variable
1134 || (src_lat
->values_count
> 1)))
1135 return set_lattice_contains_variable (dest_lat
);
1137 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1138 ret
= propagate_vals_accross_pass_through (cs
, jfunc
, src_lat
,
1141 ret
= propagate_vals_accross_ancestor (cs
, jfunc
, src_lat
, dest_lat
,
1144 if (src_lat
->contains_variable
)
1145 ret
|= set_lattice_contains_variable (dest_lat
);
1150 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1151 use it for indirect inlining), we should propagate them too. */
1152 return set_lattice_contains_variable (dest_lat
);
1155 /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
1156 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
1157 other cases, return false). If there are no aggregate items, set
1158 aggs_by_ref to NEW_AGGS_BY_REF. */
1161 set_check_aggs_by_ref (struct ipcp_param_lattices
*dest_plats
,
1162 bool new_aggs_by_ref
)
1164 if (dest_plats
->aggs
)
1166 if (dest_plats
->aggs_by_ref
!= new_aggs_by_ref
)
1168 set_agg_lats_to_bottom (dest_plats
);
1173 dest_plats
->aggs_by_ref
= new_aggs_by_ref
;
1177 /* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
1178 already existing lattice for the given OFFSET and SIZE, marking all skipped
1179 lattices as containing variable and checking for overlaps. If there is no
1180 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
1181 it with offset, size and contains_variable to PRE_EXISTING, and return true,
1182 unless there are too many already. If there are two many, return false. If
1183 there are overlaps turn whole DEST_PLATS to bottom and return false. If any
1184 skipped lattices were newly marked as containing variable, set *CHANGE to
1188 merge_agg_lats_step (struct ipcp_param_lattices
*dest_plats
,
1189 HOST_WIDE_INT offset
, HOST_WIDE_INT val_size
,
1190 struct ipcp_agg_lattice
***aglat
,
1191 bool pre_existing
, bool *change
)
1193 gcc_checking_assert (offset
>= 0);
1195 while (**aglat
&& (**aglat
)->offset
< offset
)
1197 if ((**aglat
)->offset
+ (**aglat
)->size
> offset
)
1199 set_agg_lats_to_bottom (dest_plats
);
1202 *change
|= set_lattice_contains_variable (**aglat
);
1203 *aglat
= &(**aglat
)->next
;
1206 if (**aglat
&& (**aglat
)->offset
== offset
)
1208 if ((**aglat
)->size
!= val_size
1210 && (**aglat
)->next
->offset
< offset
+ val_size
))
1212 set_agg_lats_to_bottom (dest_plats
);
1215 gcc_checking_assert (!(**aglat
)->next
1216 || (**aglat
)->next
->offset
>= offset
+ val_size
);
1221 struct ipcp_agg_lattice
*new_al
;
1223 if (**aglat
&& (**aglat
)->offset
< offset
+ val_size
)
1225 set_agg_lats_to_bottom (dest_plats
);
1228 if (dest_plats
->aggs_count
== PARAM_VALUE (PARAM_IPA_MAX_AGG_ITEMS
))
1230 dest_plats
->aggs_count
++;
1231 new_al
= (struct ipcp_agg_lattice
*) pool_alloc (ipcp_agg_lattice_pool
);
1232 memset (new_al
, 0, sizeof (*new_al
));
1234 new_al
->offset
= offset
;
1235 new_al
->size
= val_size
;
1236 new_al
->contains_variable
= pre_existing
;
1238 new_al
->next
= **aglat
;
1244 /* Set all AGLAT and all other aggregate lattices reachable by next pointers as
1245 containing an unknown value. */
1248 set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice
*aglat
)
1253 ret
|= set_lattice_contains_variable (aglat
);
1254 aglat
= aglat
->next
;
1259 /* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
1260 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source
1261 parameter used for lattice value sources. Return true if DEST_PLATS changed
1265 merge_aggregate_lattices (struct cgraph_edge
*cs
,
1266 struct ipcp_param_lattices
*dest_plats
,
1267 struct ipcp_param_lattices
*src_plats
,
1268 int src_idx
, HOST_WIDE_INT offset_delta
)
1270 bool pre_existing
= dest_plats
->aggs
!= NULL
;
1271 struct ipcp_agg_lattice
**dst_aglat
;
1274 if (set_check_aggs_by_ref (dest_plats
, src_plats
->aggs_by_ref
))
1276 if (src_plats
->aggs_bottom
)
1277 return set_agg_lats_contain_variable (dest_plats
);
1278 if (src_plats
->aggs_contain_variable
)
1279 ret
|= set_agg_lats_contain_variable (dest_plats
);
1280 dst_aglat
= &dest_plats
->aggs
;
1282 for (struct ipcp_agg_lattice
*src_aglat
= src_plats
->aggs
;
1284 src_aglat
= src_aglat
->next
)
1286 HOST_WIDE_INT new_offset
= src_aglat
->offset
- offset_delta
;
1290 if (merge_agg_lats_step (dest_plats
, new_offset
, src_aglat
->size
,
1291 &dst_aglat
, pre_existing
, &ret
))
1293 struct ipcp_agg_lattice
*new_al
= *dst_aglat
;
1295 dst_aglat
= &(*dst_aglat
)->next
;
1296 if (src_aglat
->bottom
)
1298 ret
|= set_lattice_contains_variable (new_al
);
1301 if (src_aglat
->contains_variable
)
1302 ret
|= set_lattice_contains_variable (new_al
);
1303 for (struct ipcp_value
*val
= src_aglat
->values
;
1306 ret
|= add_value_to_lattice (new_al
, val
->value
, cs
, val
, src_idx
,
1309 else if (dest_plats
->aggs_bottom
)
1312 ret
|= set_chain_of_aglats_contains_variable (*dst_aglat
);
1316 /* Determine whether there is anything to propagate FROM SRC_PLATS through a
1317 pass-through JFUNC and if so, whether it has conform and conforms to the
1318 rules about propagating values passed by reference. */
1321 agg_pass_through_permissible_p (struct ipcp_param_lattices
*src_plats
,
1322 struct ipa_jump_func
*jfunc
)
1324 return src_plats
->aggs
1325 && (!src_plats
->aggs_by_ref
1326 || ipa_get_jf_pass_through_agg_preserved (jfunc
));
1329 /* Propagate scalar values across jump function JFUNC that is associated with
1330 edge CS and put the values into DEST_LAT. */
1333 propagate_aggs_accross_jump_function (struct cgraph_edge
*cs
,
1334 struct ipa_jump_func
*jfunc
,
1335 struct ipcp_param_lattices
*dest_plats
)
1339 if (dest_plats
->aggs_bottom
)
1342 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1343 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
1345 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1346 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1347 struct ipcp_param_lattices
*src_plats
;
1349 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
1350 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
1352 /* Currently we do not produce clobber aggregate jump
1353 functions, replace with merging when we do. */
1354 gcc_assert (!jfunc
->agg
.items
);
1355 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
,
1359 ret
|= set_agg_lats_contain_variable (dest_plats
);
1361 else if (jfunc
->type
== IPA_JF_ANCESTOR
1362 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
1364 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1365 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1366 struct ipcp_param_lattices
*src_plats
;
1368 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
1369 if (src_plats
->aggs
&& src_plats
->aggs_by_ref
)
1371 /* Currently we do not produce clobber aggregate jump
1372 functions, replace with merging when we do. */
1373 gcc_assert (!jfunc
->agg
.items
);
1374 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
, src_idx
,
1375 ipa_get_jf_ancestor_offset (jfunc
));
1377 else if (!src_plats
->aggs_by_ref
)
1378 ret
|= set_agg_lats_to_bottom (dest_plats
);
1380 ret
|= set_agg_lats_contain_variable (dest_plats
);
1382 else if (jfunc
->agg
.items
)
1384 bool pre_existing
= dest_plats
->aggs
!= NULL
;
1385 struct ipcp_agg_lattice
**aglat
= &dest_plats
->aggs
;
1386 struct ipa_agg_jf_item
*item
;
1389 if (set_check_aggs_by_ref (dest_plats
, jfunc
->agg
.by_ref
))
1392 FOR_EACH_VEC_ELT (*jfunc
->agg
.items
, i
, item
)
1394 HOST_WIDE_INT val_size
;
1396 if (item
->offset
< 0)
1398 gcc_checking_assert (is_gimple_ip_invariant (item
->value
));
1399 val_size
= tree_low_cst (TYPE_SIZE (TREE_TYPE (item
->value
)), 1);
1401 if (merge_agg_lats_step (dest_plats
, item
->offset
, val_size
,
1402 &aglat
, pre_existing
, &ret
))
1404 ret
|= add_value_to_lattice (*aglat
, item
->value
, cs
, NULL
, 0, 0);
1405 aglat
= &(*aglat
)->next
;
1407 else if (dest_plats
->aggs_bottom
)
1411 ret
|= set_chain_of_aglats_contains_variable (*aglat
);
1414 ret
|= set_agg_lats_contain_variable (dest_plats
);
1419 /* Propagate constants from the caller to the callee of CS. INFO describes the
1423 propagate_constants_accross_call (struct cgraph_edge
*cs
)
1425 struct ipa_node_params
*callee_info
;
1426 enum availability availability
;
1427 struct cgraph_node
*callee
, *alias_or_thunk
;
1428 struct ipa_edge_args
*args
;
1430 int i
, args_count
, parms_count
;
1432 callee
= cgraph_function_node (cs
->callee
, &availability
);
1433 if (!callee
->analyzed
)
1435 gcc_checking_assert (cgraph_function_with_gimple_body_p (callee
));
1436 callee_info
= IPA_NODE_REF (callee
);
1438 args
= IPA_EDGE_REF (cs
);
1439 args_count
= ipa_get_cs_argument_count (args
);
1440 parms_count
= ipa_get_param_count (callee_info
);
1442 /* If this call goes through a thunk we must not propagate to the first (0th)
1443 parameter. However, we might need to uncover a thunk from below a series
1444 of aliases first. */
1445 alias_or_thunk
= cs
->callee
;
1446 while (alias_or_thunk
->alias
)
1447 alias_or_thunk
= cgraph_alias_aliased_node (alias_or_thunk
);
1448 if (alias_or_thunk
->thunk
.thunk_p
)
1450 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
1457 for (; (i
< args_count
) && (i
< parms_count
); i
++)
1459 struct ipa_jump_func
*jump_func
= ipa_get_ith_jump_func (args
, i
);
1460 struct ipcp_param_lattices
*dest_plats
;
1462 dest_plats
= ipa_get_parm_lattices (callee_info
, i
);
1463 if (availability
== AVAIL_OVERWRITABLE
)
1464 ret
|= set_all_contains_variable (dest_plats
);
1467 ret
|= propagate_scalar_accross_jump_function (cs
, jump_func
,
1468 &dest_plats
->itself
);
1469 ret
|= propagate_aggs_accross_jump_function (cs
, jump_func
,
1473 for (; i
< parms_count
; i
++)
1474 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
, i
));
1479 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
1480 (which can contain both constants and binfos), KNOWN_BINFOS, KNOWN_AGGS or
1481 AGG_REPS return the destination. The latter three can be NULL. If AGG_REPS
1482 is not NULL, KNOWN_AGGS is ignored. */
1485 ipa_get_indirect_edge_target_1 (struct cgraph_edge
*ie
,
1486 vec
<tree
> known_vals
,
1487 vec
<tree
> known_binfos
,
1488 vec
<ipa_agg_jump_function_p
> known_aggs
,
1489 struct ipa_agg_replacement_value
*agg_reps
)
1491 int param_index
= ie
->indirect_info
->param_index
;
1492 HOST_WIDE_INT token
, anc_offset
;
1496 if (param_index
== -1)
1499 if (!ie
->indirect_info
->polymorphic
)
1503 if (ie
->indirect_info
->agg_contents
)
1510 if (agg_reps
->index
== param_index
1511 && agg_reps
->offset
== ie
->indirect_info
->offset
)
1513 t
= agg_reps
->value
;
1516 agg_reps
= agg_reps
->next
;
1519 else if (known_aggs
.length () > (unsigned int) param_index
)
1521 struct ipa_agg_jump_function
*agg
;
1522 agg
= known_aggs
[param_index
];
1523 t
= ipa_find_agg_cst_for_param (agg
, ie
->indirect_info
->offset
,
1524 ie
->indirect_info
->by_ref
);
1530 t
= (known_vals
.length () > (unsigned int) param_index
1531 ? known_vals
[param_index
] : NULL
);
1534 TREE_CODE (t
) == ADDR_EXPR
1535 && TREE_CODE (TREE_OPERAND (t
, 0)) == FUNCTION_DECL
)
1536 return TREE_OPERAND (t
, 0);
1541 gcc_assert (!ie
->indirect_info
->agg_contents
);
1542 token
= ie
->indirect_info
->otr_token
;
1543 anc_offset
= ie
->indirect_info
->offset
;
1544 otr_type
= ie
->indirect_info
->otr_type
;
1546 t
= known_vals
[param_index
];
1547 if (!t
&& known_binfos
.length () > (unsigned int) param_index
)
1548 t
= known_binfos
[param_index
];
1552 if (TREE_CODE (t
) != TREE_BINFO
)
1555 binfo
= gimple_extract_devirt_binfo_from_cst (t
);
1558 binfo
= get_binfo_at_offset (binfo
, anc_offset
, otr_type
);
1561 return gimple_get_virt_method_for_binfo (token
, binfo
);
1567 binfo
= get_binfo_at_offset (t
, anc_offset
, otr_type
);
1570 return gimple_get_virt_method_for_binfo (token
, binfo
);
1575 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
1576 (which can contain both constants and binfos), KNOWN_BINFOS (which can be
1577 NULL) or KNOWN_AGGS (which also can be NULL) return the destination. */
1580 ipa_get_indirect_edge_target (struct cgraph_edge
*ie
,
1581 vec
<tree
> known_vals
,
1582 vec
<tree
> known_binfos
,
1583 vec
<ipa_agg_jump_function_p
> known_aggs
)
1585 return ipa_get_indirect_edge_target_1 (ie
, known_vals
, known_binfos
,
1589 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
1590 and KNOWN_BINFOS. */
1593 devirtualization_time_bonus (struct cgraph_node
*node
,
1594 vec
<tree
> known_csts
,
1595 vec
<tree
> known_binfos
,
1596 vec
<ipa_agg_jump_function_p
> known_aggs
)
1598 struct cgraph_edge
*ie
;
1601 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
1603 struct cgraph_node
*callee
;
1604 struct inline_summary
*isummary
;
1607 target
= ipa_get_indirect_edge_target (ie
, known_csts
, known_binfos
,
1612 /* Only bare minimum benefit for clearly un-inlineable targets. */
1614 callee
= cgraph_get_node (target
);
1615 if (!callee
|| !callee
->analyzed
)
1617 isummary
= inline_summary (callee
);
1618 if (!isummary
->inlinable
)
1621 /* FIXME: The values below need re-considering and perhaps also
1622 integrating into the cost metrics, at lest in some very basic way. */
1623 if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 4)
1625 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 2)
1627 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
1628 || DECL_DECLARED_INLINE_P (callee
->symbol
.decl
))
1635 /* Return time bonus incurred because of HINTS. */
1638 hint_time_bonus (inline_hints hints
)
1641 if (hints
& (INLINE_HINT_loop_iterations
| INLINE_HINT_loop_stride
))
1642 result
+= PARAM_VALUE (PARAM_IPA_CP_LOOP_HINT_BONUS
);
1643 if (hints
& INLINE_HINT_array_index
)
1644 result
+= PARAM_VALUE (PARAM_IPA_CP_ARRAY_INDEX_HINT_BONUS
);
1648 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
1649 and SIZE_COST and with the sum of frequencies of incoming edges to the
1650 potential new clone in FREQUENCIES. */
1653 good_cloning_opportunity_p (struct cgraph_node
*node
, int time_benefit
,
1654 int freq_sum
, gcov_type count_sum
, int size_cost
)
1656 if (time_benefit
== 0
1657 || !flag_ipa_cp_clone
1658 || !optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node
->symbol
.decl
)))
1661 gcc_assert (size_cost
> 0);
1665 int factor
= (count_sum
* 1000) / max_count
;
1666 HOST_WIDEST_INT evaluation
= (((HOST_WIDEST_INT
) time_benefit
* factor
)
1669 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1670 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
1671 "size: %i, count_sum: " HOST_WIDE_INT_PRINT_DEC
1672 ") -> evaluation: " HOST_WIDEST_INT_PRINT_DEC
1673 ", threshold: %i\n",
1674 time_benefit
, size_cost
, (HOST_WIDE_INT
) count_sum
,
1675 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
1677 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
1681 HOST_WIDEST_INT evaluation
= (((HOST_WIDEST_INT
) time_benefit
* freq_sum
)
1684 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1685 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
1686 "size: %i, freq_sum: %i) -> evaluation: "
1687 HOST_WIDEST_INT_PRINT_DEC
", threshold: %i\n",
1688 time_benefit
, size_cost
, freq_sum
, evaluation
,
1689 PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
1691 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
1695 /* Return all context independent values from aggregate lattices in PLATS in a
1696 vector. Return NULL if there are none. */
1698 static vec
<ipa_agg_jf_item_t
, va_gc
> *
1699 context_independent_aggregate_values (struct ipcp_param_lattices
*plats
)
1701 vec
<ipa_agg_jf_item_t
, va_gc
> *res
= NULL
;
1703 if (plats
->aggs_bottom
1704 || plats
->aggs_contain_variable
1705 || plats
->aggs_count
== 0)
1708 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
;
1710 aglat
= aglat
->next
)
1711 if (ipa_lat_is_single_const (aglat
))
1713 struct ipa_agg_jf_item item
;
1714 item
.offset
= aglat
->offset
;
1715 item
.value
= aglat
->values
->value
;
1716 vec_safe_push (res
, item
);
1721 /* Allocate KNOWN_CSTS, KNOWN_BINFOS and, if non-NULL, KNOWN_AGGS and populate
1722 them with values of parameters that are known independent of the context.
1723 INFO describes the function. If REMOVABLE_PARAMS_COST is non-NULL, the
1724 movement cost of all removable parameters will be stored in it. */
1727 gather_context_independent_values (struct ipa_node_params
*info
,
1728 vec
<tree
> *known_csts
,
1729 vec
<tree
> *known_binfos
,
1730 vec
<ipa_agg_jump_function_t
> *known_aggs
,
1731 int *removable_params_cost
)
1733 int i
, count
= ipa_get_param_count (info
);
1736 known_csts
->create (0);
1737 known_binfos
->create (0);
1738 known_csts
->safe_grow_cleared (count
);
1739 known_binfos
->safe_grow_cleared (count
);
1742 known_aggs
->create (0);
1743 known_aggs
->safe_grow_cleared (count
);
1746 if (removable_params_cost
)
1747 *removable_params_cost
= 0;
1749 for (i
= 0; i
< count
; i
++)
1751 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1752 struct ipcp_lattice
*lat
= &plats
->itself
;
1754 if (ipa_lat_is_single_const (lat
))
1756 struct ipcp_value
*val
= lat
->values
;
1757 if (TREE_CODE (val
->value
) != TREE_BINFO
)
1759 (*known_csts
)[i
] = val
->value
;
1760 if (removable_params_cost
)
1761 *removable_params_cost
1762 += estimate_move_cost (TREE_TYPE (val
->value
));
1765 else if (plats
->virt_call
)
1767 (*known_binfos
)[i
] = val
->value
;
1770 else if (removable_params_cost
1771 && !ipa_is_param_used (info
, i
))
1772 *removable_params_cost
1773 += estimate_move_cost (TREE_TYPE (ipa_get_param (info
, i
)));
1775 else if (removable_params_cost
1776 && !ipa_is_param_used (info
, i
))
1777 *removable_params_cost
1778 += estimate_move_cost (TREE_TYPE (ipa_get_param (info
, i
)));
1782 vec
<ipa_agg_jf_item_t
, va_gc
> *agg_items
;
1783 struct ipa_agg_jump_function
*ajf
;
1785 agg_items
= context_independent_aggregate_values (plats
);
1786 ajf
= &(*known_aggs
)[i
];
1787 ajf
->items
= agg_items
;
1788 ajf
->by_ref
= plats
->aggs_by_ref
;
1789 ret
|= agg_items
!= NULL
;
1796 /* The current interface in ipa-inline-analysis requires a pointer vector.
1799 FIXME: That interface should be re-worked, this is slightly silly. Still,
1800 I'd like to discuss how to change it first and this demonstrates the
1803 static vec
<ipa_agg_jump_function_p
>
1804 agg_jmp_p_vec_for_t_vec (vec
<ipa_agg_jump_function_t
> known_aggs
)
1806 vec
<ipa_agg_jump_function_p
> ret
;
1807 struct ipa_agg_jump_function
*ajf
;
1810 ret
.create (known_aggs
.length ());
1811 FOR_EACH_VEC_ELT (known_aggs
, i
, ajf
)
1812 ret
.quick_push (ajf
);
1816 /* Iterate over known values of parameters of NODE and estimate the local
1817 effects in terms of time and size they have. */
1820 estimate_local_effects (struct cgraph_node
*node
)
1822 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1823 int i
, count
= ipa_get_param_count (info
);
1824 vec
<tree
> known_csts
, known_binfos
;
1825 vec
<ipa_agg_jump_function_t
> known_aggs
;
1826 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
;
1828 int base_time
= inline_summary (node
)->time
;
1829 int removable_params_cost
;
1831 if (!count
|| !ipcp_versionable_function_p (node
))
1834 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1835 fprintf (dump_file
, "\nEstimating effects for %s/%i, base_time: %i.\n",
1836 cgraph_node_name (node
), node
->uid
, base_time
);
1838 always_const
= gather_context_independent_values (info
, &known_csts
,
1839 &known_binfos
, &known_aggs
,
1840 &removable_params_cost
);
1841 known_aggs_ptrs
= agg_jmp_p_vec_for_t_vec (known_aggs
);
1844 struct caller_statistics stats
;
1848 init_caller_stats (&stats
);
1849 cgraph_for_node_and_aliases (node
, gather_caller_stats
, &stats
, false);
1850 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_binfos
,
1851 known_aggs_ptrs
, &size
, &time
, &hints
);
1852 time
-= devirtualization_time_bonus (node
, known_csts
, known_binfos
,
1854 time
-= hint_time_bonus (hints
);
1855 time
-= removable_params_cost
;
1856 size
-= stats
.n_calls
* removable_params_cost
;
1859 fprintf (dump_file
, " - context independent values, size: %i, "
1860 "time_benefit: %i\n", size
, base_time
- time
);
1863 || cgraph_will_be_removed_from_program_if_no_direct_calls (node
))
1865 info
->do_clone_for_all_contexts
= true;
1869 fprintf (dump_file
, " Decided to specialize for all "
1870 "known contexts, code not going to grow.\n");
1872 else if (good_cloning_opportunity_p (node
, base_time
- time
,
1873 stats
.freq_sum
, stats
.count_sum
,
1876 if (size
+ overall_size
<= max_new_size
)
1878 info
->do_clone_for_all_contexts
= true;
1880 overall_size
+= size
;
1883 fprintf (dump_file
, " Decided to specialize for all "
1884 "known contexts, growth deemed beneficial.\n");
1886 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1887 fprintf (dump_file
, " Not cloning for all contexts because "
1888 "max_new_size would be reached with %li.\n",
1889 size
+ overall_size
);
1893 for (i
= 0; i
< count
; i
++)
1895 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1896 struct ipcp_lattice
*lat
= &plats
->itself
;
1897 struct ipcp_value
*val
;
1906 for (val
= lat
->values
; val
; val
= val
->next
)
1908 int time
, size
, time_benefit
;
1911 if (TREE_CODE (val
->value
) != TREE_BINFO
)
1913 known_csts
[i
] = val
->value
;
1914 known_binfos
[i
] = NULL_TREE
;
1915 emc
= estimate_move_cost (TREE_TYPE (val
->value
));
1917 else if (plats
->virt_call
)
1919 known_csts
[i
] = NULL_TREE
;
1920 known_binfos
[i
] = val
->value
;
1926 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_binfos
,
1927 known_aggs_ptrs
, &size
, &time
,
1929 time_benefit
= base_time
- time
1930 + devirtualization_time_bonus (node
, known_csts
, known_binfos
,
1932 + hint_time_bonus (hints
)
1933 + removable_params_cost
+ emc
;
1935 gcc_checking_assert (size
>=0);
1936 /* The inliner-heuristics based estimates may think that in certain
1937 contexts some functions do not have any size at all but we want
1938 all specializations to have at least a tiny cost, not least not to
1943 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1945 fprintf (dump_file
, " - estimates for value ");
1946 print_ipcp_constant_value (dump_file
, val
->value
);
1947 fprintf (dump_file
, " for parameter ");
1948 print_generic_expr (dump_file
, ipa_get_param (info
, i
), 0);
1949 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
1950 time_benefit
, size
);
1953 val
->local_time_benefit
= time_benefit
;
1954 val
->local_size_cost
= size
;
1956 known_binfos
[i
] = NULL_TREE
;
1957 known_csts
[i
] = NULL_TREE
;
1960 for (i
= 0; i
< count
; i
++)
1962 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1963 struct ipa_agg_jump_function
*ajf
;
1964 struct ipcp_agg_lattice
*aglat
;
1966 if (plats
->aggs_bottom
|| !plats
->aggs
)
1969 ajf
= &known_aggs
[i
];
1970 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
1972 struct ipcp_value
*val
;
1973 if (aglat
->bottom
|| !aglat
->values
1974 /* If the following is true, the one value is in known_aggs. */
1975 || (!plats
->aggs_contain_variable
1976 && ipa_lat_is_single_const (aglat
)))
1979 for (val
= aglat
->values
; val
; val
= val
->next
)
1981 int time
, size
, time_benefit
;
1982 struct ipa_agg_jf_item item
;
1985 item
.offset
= aglat
->offset
;
1986 item
.value
= val
->value
;
1987 vec_safe_push (ajf
->items
, item
);
1989 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_binfos
,
1990 known_aggs_ptrs
, &size
, &time
,
1992 time_benefit
= base_time
- time
1993 + devirtualization_time_bonus (node
, known_csts
, known_binfos
,
1995 + hint_time_bonus (hints
);
1996 gcc_checking_assert (size
>=0);
2000 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2002 fprintf (dump_file
, " - estimates for value ");
2003 print_ipcp_constant_value (dump_file
, val
->value
);
2004 fprintf (dump_file
, " for parameter ");
2005 print_generic_expr (dump_file
, ipa_get_param (info
, i
), 0);
2006 fprintf (dump_file
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
2007 "]: time_benefit: %i, size: %i\n",
2008 plats
->aggs_by_ref
? "ref " : "",
2009 aglat
->offset
, time_benefit
, size
);
2012 val
->local_time_benefit
= time_benefit
;
2013 val
->local_size_cost
= size
;
2019 for (i
= 0; i
< count
; i
++)
2020 vec_free (known_aggs
[i
].items
);
2022 known_csts
.release ();
2023 known_binfos
.release ();
2024 known_aggs
.release ();
2025 known_aggs_ptrs
.release ();
2029 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
2030 topological sort of values. */
2033 add_val_to_toposort (struct ipcp_value
*cur_val
)
2035 static int dfs_counter
= 0;
2036 static struct ipcp_value
*stack
;
2037 struct ipcp_value_source
*src
;
2043 cur_val
->dfs
= dfs_counter
;
2044 cur_val
->low_link
= dfs_counter
;
2046 cur_val
->topo_next
= stack
;
2048 cur_val
->on_stack
= true;
2050 for (src
= cur_val
->sources
; src
; src
= src
->next
)
2053 if (src
->val
->dfs
== 0)
2055 add_val_to_toposort (src
->val
);
2056 if (src
->val
->low_link
< cur_val
->low_link
)
2057 cur_val
->low_link
= src
->val
->low_link
;
2059 else if (src
->val
->on_stack
2060 && src
->val
->dfs
< cur_val
->low_link
)
2061 cur_val
->low_link
= src
->val
->dfs
;
2064 if (cur_val
->dfs
== cur_val
->low_link
)
2066 struct ipcp_value
*v
, *scc_list
= NULL
;
2071 stack
= v
->topo_next
;
2072 v
->on_stack
= false;
2074 v
->scc_next
= scc_list
;
2077 while (v
!= cur_val
);
2079 cur_val
->topo_next
= values_topo
;
2080 values_topo
= cur_val
;
2084 /* Add all values in lattices associated with NODE to the topological sort if
2085 they are not there yet. */
2088 add_all_node_vals_to_toposort (struct cgraph_node
*node
)
2090 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2091 int i
, count
= ipa_get_param_count (info
);
2093 for (i
= 0; i
< count
; i
++)
2095 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2096 struct ipcp_lattice
*lat
= &plats
->itself
;
2097 struct ipcp_agg_lattice
*aglat
;
2098 struct ipcp_value
*val
;
2101 for (val
= lat
->values
; val
; val
= val
->next
)
2102 add_val_to_toposort (val
);
2104 if (!plats
->aggs_bottom
)
2105 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2107 for (val
= aglat
->values
; val
; val
= val
->next
)
2108 add_val_to_toposort (val
);
2112 /* One pass of constants propagation along the call graph edges, from callers
2113 to callees (requires topological ordering in TOPO), iterate over strongly
2114 connected components. */
2117 propagate_constants_topo (struct topo_info
*topo
)
2121 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
2123 struct cgraph_node
*v
, *node
= topo
->order
[i
];
2124 struct ipa_dfs_info
*node_dfs_info
;
2126 if (!cgraph_function_with_gimple_body_p (node
))
2129 node_dfs_info
= (struct ipa_dfs_info
*) node
->symbol
.aux
;
2130 /* First, iteratively propagate within the strongly connected component
2131 until all lattices stabilize. */
2132 v
= node_dfs_info
->next_cycle
;
2135 push_node_to_stack (topo
, v
);
2136 v
= ((struct ipa_dfs_info
*) v
->symbol
.aux
)->next_cycle
;
2142 struct cgraph_edge
*cs
;
2144 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
2145 if (edge_within_scc (cs
)
2146 && propagate_constants_accross_call (cs
))
2147 push_node_to_stack (topo
, cs
->callee
);
2148 v
= pop_node_from_stack (topo
);
2151 /* Afterwards, propagate along edges leading out of the SCC, calculates
2152 the local effects of the discovered constants and all valid values to
2153 their topological sort. */
2157 struct cgraph_edge
*cs
;
2159 estimate_local_effects (v
);
2160 add_all_node_vals_to_toposort (v
);
2161 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
2162 if (!edge_within_scc (cs
))
2163 propagate_constants_accross_call (cs
);
2165 v
= ((struct ipa_dfs_info
*) v
->symbol
.aux
)->next_cycle
;
2171 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
2172 the bigger one if otherwise. */
2175 safe_add (int a
, int b
)
2177 if (a
> INT_MAX
/2 || b
> INT_MAX
/2)
2178 return a
> b
? a
: b
;
2184 /* Propagate the estimated effects of individual values along the topological
2185 from the dependent values to those they depend on. */
2188 propagate_effects (void)
2190 struct ipcp_value
*base
;
2192 for (base
= values_topo
; base
; base
= base
->topo_next
)
2194 struct ipcp_value_source
*src
;
2195 struct ipcp_value
*val
;
2196 int time
= 0, size
= 0;
2198 for (val
= base
; val
; val
= val
->scc_next
)
2200 time
= safe_add (time
,
2201 val
->local_time_benefit
+ val
->prop_time_benefit
);
2202 size
= safe_add (size
, val
->local_size_cost
+ val
->prop_size_cost
);
2205 for (val
= base
; val
; val
= val
->scc_next
)
2206 for (src
= val
->sources
; src
; src
= src
->next
)
2208 && cgraph_maybe_hot_edge_p (src
->cs
))
2210 src
->val
->prop_time_benefit
= safe_add (time
,
2211 src
->val
->prop_time_benefit
);
2212 src
->val
->prop_size_cost
= safe_add (size
,
2213 src
->val
->prop_size_cost
);
2219 /* Propagate constants, binfos and their effects from the summaries
2220 interprocedurally. */
2223 ipcp_propagate_stage (struct topo_info
*topo
)
2225 struct cgraph_node
*node
;
2228 fprintf (dump_file
, "\n Propagating constants:\n\n");
2231 ipa_update_after_lto_read ();
2234 FOR_EACH_DEFINED_FUNCTION (node
)
2236 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2238 determine_versionability (node
);
2239 if (cgraph_function_with_gimple_body_p (node
))
2241 info
->lattices
= XCNEWVEC (struct ipcp_param_lattices
,
2242 ipa_get_param_count (info
));
2243 initialize_node_lattices (node
);
2245 if (node
->count
> max_count
)
2246 max_count
= node
->count
;
2247 overall_size
+= inline_summary (node
)->self_size
;
2250 max_new_size
= overall_size
;
2251 if (max_new_size
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
2252 max_new_size
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
2253 max_new_size
+= max_new_size
* PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH
) / 100 + 1;
2256 fprintf (dump_file
, "\noverall_size: %li, max_new_size: %li\n",
2257 overall_size
, max_new_size
);
2259 propagate_constants_topo (topo
);
2260 #ifdef ENABLE_CHECKING
2261 ipcp_verify_propagated_values ();
2263 propagate_effects ();
2267 fprintf (dump_file
, "\nIPA lattices after all propagation:\n");
2268 print_all_lattices (dump_file
, (dump_flags
& TDF_DETAILS
), true);
2272 /* Discover newly direct outgoing edges from NODE which is a new clone with
2273 known KNOWN_VALS and make them direct. */
2276 ipcp_discover_new_direct_edges (struct cgraph_node
*node
,
2277 vec
<tree
> known_vals
,
2278 struct ipa_agg_replacement_value
*aggvals
)
2280 struct cgraph_edge
*ie
, *next_ie
;
2283 for (ie
= node
->indirect_calls
; ie
; ie
= next_ie
)
2287 next_ie
= ie
->next_callee
;
2288 target
= ipa_get_indirect_edge_target_1 (ie
, known_vals
, vNULL
, vNULL
,
2292 ipa_make_edge_direct_to_target (ie
, target
);
2296 /* Turning calls to direct calls will improve overall summary. */
2298 inline_update_overall_summary (node
);
2301 /* Vector of pointers which for linked lists of clones of an original crgaph
2304 static vec
<cgraph_edge_p
> next_edge_clone
;
2307 grow_next_edge_clone_vector (void)
2309 if (next_edge_clone
.length ()
2310 <= (unsigned) cgraph_edge_max_uid
)
2311 next_edge_clone
.safe_grow_cleared (cgraph_edge_max_uid
+ 1);
2314 /* Edge duplication hook to grow the appropriate linked list in
2318 ipcp_edge_duplication_hook (struct cgraph_edge
*src
, struct cgraph_edge
*dst
,
2319 __attribute__((unused
)) void *data
)
2321 grow_next_edge_clone_vector ();
2322 next_edge_clone
[dst
->uid
] = next_edge_clone
[src
->uid
];
2323 next_edge_clone
[src
->uid
] = dst
;
2326 /* See if NODE is a clone with a known aggregate value at a given OFFSET of a
2327 parameter with the given INDEX. */
2330 get_clone_agg_value (struct cgraph_node
*node
, HOST_WIDEST_INT offset
,
2333 struct ipa_agg_replacement_value
*aggval
;
2335 aggval
= ipa_get_agg_replacements_for_node (node
);
2338 if (aggval
->offset
== offset
2339 && aggval
->index
== index
)
2340 return aggval
->value
;
2341 aggval
= aggval
->next
;
2346 /* Return true if edge CS does bring about the value described by SRC. */
2349 cgraph_edge_brings_value_p (struct cgraph_edge
*cs
,
2350 struct ipcp_value_source
*src
)
2352 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2353 struct ipa_node_params
*dst_info
= IPA_NODE_REF (cs
->callee
);
2355 if ((dst_info
->ipcp_orig_node
&& !dst_info
->is_all_contexts_clone
)
2356 || caller_info
->node_dead
)
2361 if (caller_info
->ipcp_orig_node
)
2364 if (src
->offset
== -1)
2365 t
= caller_info
->known_vals
[src
->index
];
2367 t
= get_clone_agg_value (cs
->caller
, src
->offset
, src
->index
);
2368 return (t
!= NULL_TREE
2369 && values_equal_for_ipcp_p (src
->val
->value
, t
));
2373 struct ipcp_agg_lattice
*aglat
;
2374 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
2376 if (src
->offset
== -1)
2377 return (ipa_lat_is_single_const (&plats
->itself
)
2378 && values_equal_for_ipcp_p (src
->val
->value
,
2379 plats
->itself
.values
->value
));
2382 if (plats
->aggs_bottom
|| plats
->aggs_contain_variable
)
2384 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2385 if (aglat
->offset
== src
->offset
)
2386 return (ipa_lat_is_single_const (aglat
)
2387 && values_equal_for_ipcp_p (src
->val
->value
,
2388 aglat
->values
->value
));
2394 /* Get the next clone in the linked list of clones of an edge. */
2396 static inline struct cgraph_edge
*
2397 get_next_cgraph_edge_clone (struct cgraph_edge
*cs
)
2399 return next_edge_clone
[cs
->uid
];
2402 /* Given VAL, iterate over all its sources and if they still hold, add their
2403 edge frequency and their number into *FREQUENCY and *CALLER_COUNT
2407 get_info_about_necessary_edges (struct ipcp_value
*val
, int *freq_sum
,
2408 gcov_type
*count_sum
, int *caller_count
)
2410 struct ipcp_value_source
*src
;
2411 int freq
= 0, count
= 0;
2415 for (src
= val
->sources
; src
; src
= src
->next
)
2417 struct cgraph_edge
*cs
= src
->cs
;
2420 if (cgraph_edge_brings_value_p (cs
, src
))
2423 freq
+= cs
->frequency
;
2425 hot
|= cgraph_maybe_hot_edge_p (cs
);
2427 cs
= get_next_cgraph_edge_clone (cs
);
2433 *caller_count
= count
;
2437 /* Return a vector of incoming edges that do bring value VAL. It is assumed
2438 their number is known and equal to CALLER_COUNT. */
2440 static vec
<cgraph_edge_p
>
2441 gather_edges_for_value (struct ipcp_value
*val
, int caller_count
)
2443 struct ipcp_value_source
*src
;
2444 vec
<cgraph_edge_p
> ret
;
2446 ret
.create (caller_count
);
2447 for (src
= val
->sources
; src
; src
= src
->next
)
2449 struct cgraph_edge
*cs
= src
->cs
;
2452 if (cgraph_edge_brings_value_p (cs
, src
))
2453 ret
.quick_push (cs
);
2454 cs
= get_next_cgraph_edge_clone (cs
);
2461 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
2462 Return it or NULL if for some reason it cannot be created. */
2464 static struct ipa_replace_map
*
2465 get_replacement_map (tree value
, tree parm
)
2467 tree req_type
= TREE_TYPE (parm
);
2468 struct ipa_replace_map
*replace_map
;
2470 if (!useless_type_conversion_p (req_type
, TREE_TYPE (value
)))
2472 if (fold_convertible_p (req_type
, value
))
2473 value
= fold_build1 (NOP_EXPR
, req_type
, value
);
2474 else if (TYPE_SIZE (req_type
) == TYPE_SIZE (TREE_TYPE (value
)))
2475 value
= fold_build1 (VIEW_CONVERT_EXPR
, req_type
, value
);
2480 fprintf (dump_file
, " const ");
2481 print_generic_expr (dump_file
, value
, 0);
2482 fprintf (dump_file
, " can't be converted to param ");
2483 print_generic_expr (dump_file
, parm
, 0);
2484 fprintf (dump_file
, "\n");
2490 replace_map
= ggc_alloc_ipa_replace_map ();
2493 fprintf (dump_file
, " replacing param ");
2494 print_generic_expr (dump_file
, parm
, 0);
2495 fprintf (dump_file
, " with const ");
2496 print_generic_expr (dump_file
, value
, 0);
2497 fprintf (dump_file
, "\n");
2499 replace_map
->old_tree
= parm
;
2500 replace_map
->new_tree
= value
;
2501 replace_map
->replace_p
= true;
2502 replace_map
->ref_p
= false;
2507 /* Dump new profiling counts */
2510 dump_profile_updates (struct cgraph_node
*orig_node
,
2511 struct cgraph_node
*new_node
)
2513 struct cgraph_edge
*cs
;
2515 fprintf (dump_file
, " setting count of the specialized node to "
2516 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) new_node
->count
);
2517 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
2518 fprintf (dump_file
, " edge to %s has count "
2519 HOST_WIDE_INT_PRINT_DEC
"\n",
2520 cgraph_node_name (cs
->callee
), (HOST_WIDE_INT
) cs
->count
);
2522 fprintf (dump_file
, " setting count of the original node to "
2523 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) orig_node
->count
);
2524 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
2525 fprintf (dump_file
, " edge to %s is left with "
2526 HOST_WIDE_INT_PRINT_DEC
"\n",
2527 cgraph_node_name (cs
->callee
), (HOST_WIDE_INT
) cs
->count
);
2530 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
2531 their profile information to reflect this. */
2534 update_profiling_info (struct cgraph_node
*orig_node
,
2535 struct cgraph_node
*new_node
)
2537 struct cgraph_edge
*cs
;
2538 struct caller_statistics stats
;
2539 gcov_type new_sum
, orig_sum
;
2540 gcov_type remainder
, orig_node_count
= orig_node
->count
;
2542 if (orig_node_count
== 0)
2545 init_caller_stats (&stats
);
2546 cgraph_for_node_and_aliases (orig_node
, gather_caller_stats
, &stats
, false);
2547 orig_sum
= stats
.count_sum
;
2548 init_caller_stats (&stats
);
2549 cgraph_for_node_and_aliases (new_node
, gather_caller_stats
, &stats
, false);
2550 new_sum
= stats
.count_sum
;
2552 if (orig_node_count
< orig_sum
+ new_sum
)
2555 fprintf (dump_file
, " Problem: node %s/%i has too low count "
2556 HOST_WIDE_INT_PRINT_DEC
" while the sum of incoming "
2557 "counts is " HOST_WIDE_INT_PRINT_DEC
"\n",
2558 cgraph_node_name (orig_node
), orig_node
->uid
,
2559 (HOST_WIDE_INT
) orig_node_count
,
2560 (HOST_WIDE_INT
) (orig_sum
+ new_sum
));
2562 orig_node_count
= (orig_sum
+ new_sum
) * 12 / 10;
2564 fprintf (dump_file
, " proceeding by pretending it was "
2565 HOST_WIDE_INT_PRINT_DEC
"\n",
2566 (HOST_WIDE_INT
) orig_node_count
);
2569 new_node
->count
= new_sum
;
2570 remainder
= orig_node_count
- new_sum
;
2571 orig_node
->count
= remainder
;
2573 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
2575 cs
->count
= apply_probability (cs
->count
,
2576 GCOV_COMPUTE_SCALE (new_sum
,
2581 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
2582 cs
->count
= apply_probability (cs
->count
,
2583 GCOV_COMPUTE_SCALE (remainder
,
2587 dump_profile_updates (orig_node
, new_node
);
2590 /* Update the respective profile of specialized NEW_NODE and the original
2591 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
2592 have been redirected to the specialized version. */
2595 update_specialized_profile (struct cgraph_node
*new_node
,
2596 struct cgraph_node
*orig_node
,
2597 gcov_type redirected_sum
)
2599 struct cgraph_edge
*cs
;
2600 gcov_type new_node_count
, orig_node_count
= orig_node
->count
;
2603 fprintf (dump_file
, " the sum of counts of redirected edges is "
2604 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) redirected_sum
);
2605 if (orig_node_count
== 0)
2608 gcc_assert (orig_node_count
>= redirected_sum
);
2610 new_node_count
= new_node
->count
;
2611 new_node
->count
+= redirected_sum
;
2612 orig_node
->count
-= redirected_sum
;
2614 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
2616 cs
->count
+= apply_probability (cs
->count
,
2617 GCOV_COMPUTE_SCALE (redirected_sum
,
2622 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
2624 gcov_type dec
= apply_probability (cs
->count
,
2625 GCOV_COMPUTE_SCALE (redirected_sum
,
2627 if (dec
< cs
->count
)
2634 dump_profile_updates (orig_node
, new_node
);
2637 /* Create a specialized version of NODE with known constants and types of
2638 parameters in KNOWN_VALS and redirect all edges in CALLERS to it. */
2640 static struct cgraph_node
*
2641 create_specialized_node (struct cgraph_node
*node
,
2642 vec
<tree
> known_vals
,
2643 struct ipa_agg_replacement_value
*aggvals
,
2644 vec
<cgraph_edge_p
> callers
)
2646 struct ipa_node_params
*new_info
, *info
= IPA_NODE_REF (node
);
2647 vec
<ipa_replace_map_p
, va_gc
> *replace_trees
= NULL
;
2648 struct cgraph_node
*new_node
;
2649 int i
, count
= ipa_get_param_count (info
);
2650 bitmap args_to_skip
;
2652 gcc_assert (!info
->ipcp_orig_node
);
2654 if (node
->local
.can_change_signature
)
2656 args_to_skip
= BITMAP_GGC_ALLOC ();
2657 for (i
= 0; i
< count
; i
++)
2659 tree t
= known_vals
[i
];
2661 if ((t
&& TREE_CODE (t
) != TREE_BINFO
)
2662 || !ipa_is_param_used (info
, i
))
2663 bitmap_set_bit (args_to_skip
, i
);
2668 args_to_skip
= NULL
;
2669 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2670 fprintf (dump_file
, " cannot change function signature\n");
2673 for (i
= 0; i
< count
; i
++)
2675 tree t
= known_vals
[i
];
2676 if (t
&& TREE_CODE (t
) != TREE_BINFO
)
2678 struct ipa_replace_map
*replace_map
;
2680 replace_map
= get_replacement_map (t
, ipa_get_param (info
, i
));
2682 vec_safe_push (replace_trees
, replace_map
);
2686 new_node
= cgraph_create_virtual_clone (node
, callers
, replace_trees
,
2687 args_to_skip
, "constprop");
2688 ipa_set_node_agg_value_chain (new_node
, aggvals
);
2689 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2691 fprintf (dump_file
, " the new node is %s/%i.\n",
2692 cgraph_node_name (new_node
), new_node
->uid
);
2694 ipa_dump_agg_replacement_values (dump_file
, aggvals
);
2696 gcc_checking_assert (ipa_node_params_vector
.exists ()
2697 && (ipa_node_params_vector
.length ()
2698 > (unsigned) cgraph_max_uid
));
2699 update_profiling_info (node
, new_node
);
2700 new_info
= IPA_NODE_REF (new_node
);
2701 new_info
->ipcp_orig_node
= node
;
2702 new_info
->known_vals
= known_vals
;
2704 ipcp_discover_new_direct_edges (new_node
, known_vals
, aggvals
);
2710 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
2711 KNOWN_VALS with constants and types that are also known for all of the
2715 find_more_scalar_values_for_callers_subset (struct cgraph_node
*node
,
2716 vec
<tree
> known_vals
,
2717 vec
<cgraph_edge_p
> callers
)
2719 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2720 int i
, count
= ipa_get_param_count (info
);
2722 for (i
= 0; i
< count
; i
++)
2724 struct cgraph_edge
*cs
;
2725 tree newval
= NULL_TREE
;
2728 if (ipa_get_scalar_lat (info
, i
)->bottom
|| known_vals
[i
])
2731 FOR_EACH_VEC_ELT (callers
, j
, cs
)
2733 struct ipa_jump_func
*jump_func
;
2736 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
)))
2741 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
2742 t
= ipa_value_from_jfunc (IPA_NODE_REF (cs
->caller
), jump_func
);
2745 && !values_equal_for_ipcp_p (t
, newval
)))
2756 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2758 fprintf (dump_file
, " adding an extra known scalar value ");
2759 print_ipcp_constant_value (dump_file
, newval
);
2760 fprintf (dump_file
, " for parameter ");
2761 print_generic_expr (dump_file
, ipa_get_param (info
, i
), 0);
2762 fprintf (dump_file
, "\n");
2765 known_vals
[i
] = newval
;
2770 /* Go through PLATS and create a vector of values consisting of values and
2771 offsets (minus OFFSET) of lattices that contain only a single value. */
2773 static vec
<ipa_agg_jf_item_t
>
2774 copy_plats_to_inter (struct ipcp_param_lattices
*plats
, HOST_WIDE_INT offset
)
2776 vec
<ipa_agg_jf_item_t
> res
= vNULL
;
2778 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
2781 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2782 if (ipa_lat_is_single_const (aglat
))
2784 struct ipa_agg_jf_item ti
;
2785 ti
.offset
= aglat
->offset
- offset
;
2786 ti
.value
= aglat
->values
->value
;
2792 /* Intersect all values in INTER with single value lattices in PLATS (while
2793 subtracting OFFSET). */
2796 intersect_with_plats (struct ipcp_param_lattices
*plats
,
2797 vec
<ipa_agg_jf_item_t
> *inter
,
2798 HOST_WIDE_INT offset
)
2800 struct ipcp_agg_lattice
*aglat
;
2801 struct ipa_agg_jf_item
*item
;
2804 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
2810 aglat
= plats
->aggs
;
2811 FOR_EACH_VEC_ELT (*inter
, k
, item
)
2818 if (aglat
->offset
- offset
> item
->offset
)
2820 if (aglat
->offset
- offset
== item
->offset
)
2822 gcc_checking_assert (item
->value
);
2823 if (values_equal_for_ipcp_p (item
->value
, aglat
->values
->value
))
2827 aglat
= aglat
->next
;
2830 item
->value
= NULL_TREE
;
2834 /* Copy agggregate replacement values of NODE (which is an IPA-CP clone) to the
2835 vector result while subtracting OFFSET from the individual value offsets. */
2837 static vec
<ipa_agg_jf_item_t
>
2838 agg_replacements_to_vector (struct cgraph_node
*node
, int index
,
2839 HOST_WIDE_INT offset
)
2841 struct ipa_agg_replacement_value
*av
;
2842 vec
<ipa_agg_jf_item_t
> res
= vNULL
;
2844 for (av
= ipa_get_agg_replacements_for_node (node
); av
; av
= av
->next
)
2845 if (av
->index
== index
2846 && (av
->offset
- offset
) >= 0)
2848 struct ipa_agg_jf_item item
;
2849 gcc_checking_assert (av
->value
);
2850 item
.offset
= av
->offset
- offset
;
2851 item
.value
= av
->value
;
2852 res
.safe_push (item
);
2858 /* Intersect all values in INTER with those that we have already scheduled to
2859 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
2860 (while subtracting OFFSET). */
2863 intersect_with_agg_replacements (struct cgraph_node
*node
, int index
,
2864 vec
<ipa_agg_jf_item_t
> *inter
,
2865 HOST_WIDE_INT offset
)
2867 struct ipa_agg_replacement_value
*srcvals
;
2868 struct ipa_agg_jf_item
*item
;
2871 srcvals
= ipa_get_agg_replacements_for_node (node
);
2878 FOR_EACH_VEC_ELT (*inter
, i
, item
)
2880 struct ipa_agg_replacement_value
*av
;
2884 for (av
= srcvals
; av
; av
= av
->next
)
2886 gcc_checking_assert (av
->value
);
2887 if (av
->index
== index
2888 && av
->offset
- offset
== item
->offset
)
2890 if (values_equal_for_ipcp_p (item
->value
, av
->value
))
2896 item
->value
= NULL_TREE
;
2900 /* Intersect values in INTER with aggregate values that come along edge CS to
2901 parameter number INDEX and return it. If INTER does not actually exist yet,
2902 copy all incoming values to it. If we determine we ended up with no values
2903 whatsoever, return a released vector. */
2905 static vec
<ipa_agg_jf_item_t
>
2906 intersect_aggregates_with_edge (struct cgraph_edge
*cs
, int index
,
2907 vec
<ipa_agg_jf_item_t
> inter
)
2909 struct ipa_jump_func
*jfunc
;
2910 jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), index
);
2911 if (jfunc
->type
== IPA_JF_PASS_THROUGH
2912 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
2914 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2915 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
2917 if (caller_info
->ipcp_orig_node
)
2919 struct cgraph_node
*orig_node
= caller_info
->ipcp_orig_node
;
2920 struct ipcp_param_lattices
*orig_plats
;
2921 orig_plats
= ipa_get_parm_lattices (IPA_NODE_REF (orig_node
),
2923 if (agg_pass_through_permissible_p (orig_plats
, jfunc
))
2925 if (!inter
.exists ())
2926 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, 0);
2928 intersect_with_agg_replacements (cs
->caller
, src_idx
,
2934 struct ipcp_param_lattices
*src_plats
;
2935 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2936 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
2938 /* Currently we do not produce clobber aggregate jump
2939 functions, adjust when we do. */
2940 gcc_checking_assert (!jfunc
->agg
.items
);
2941 if (!inter
.exists ())
2942 inter
= copy_plats_to_inter (src_plats
, 0);
2944 intersect_with_plats (src_plats
, &inter
, 0);
2948 else if (jfunc
->type
== IPA_JF_ANCESTOR
2949 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
2951 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2952 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
2953 struct ipcp_param_lattices
*src_plats
;
2954 HOST_WIDE_INT delta
= ipa_get_jf_ancestor_offset (jfunc
);
2956 if (caller_info
->ipcp_orig_node
)
2958 if (!inter
.exists ())
2959 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, delta
);
2961 intersect_with_agg_replacements (cs
->caller
, src_idx
, &inter
,
2966 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);;
2967 /* Currently we do not produce clobber aggregate jump
2968 functions, adjust when we do. */
2969 gcc_checking_assert (!src_plats
->aggs
|| !jfunc
->agg
.items
);
2970 if (!inter
.exists ())
2971 inter
= copy_plats_to_inter (src_plats
, delta
);
2973 intersect_with_plats (src_plats
, &inter
, delta
);
2976 else if (jfunc
->agg
.items
)
2978 struct ipa_agg_jf_item
*item
;
2981 if (!inter
.exists ())
2982 for (unsigned i
= 0; i
< jfunc
->agg
.items
->length (); i
++)
2983 inter
.safe_push ((*jfunc
->agg
.items
)[i
]);
2985 FOR_EACH_VEC_ELT (inter
, k
, item
)
2988 bool found
= false;;
2993 while ((unsigned) l
< jfunc
->agg
.items
->length ())
2995 struct ipa_agg_jf_item
*ti
;
2996 ti
= &(*jfunc
->agg
.items
)[l
];
2997 if (ti
->offset
> item
->offset
)
2999 if (ti
->offset
== item
->offset
)
3001 gcc_checking_assert (ti
->value
);
3002 if (values_equal_for_ipcp_p (item
->value
,
3016 return vec
<ipa_agg_jf_item_t
>();
3021 /* Look at edges in CALLERS and collect all known aggregate values that arrive
3022 from all of them. */
3024 static struct ipa_agg_replacement_value
*
3025 find_aggregate_values_for_callers_subset (struct cgraph_node
*node
,
3026 vec
<cgraph_edge_p
> callers
)
3028 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
3029 struct ipa_agg_replacement_value
*res
= NULL
;
3030 struct cgraph_edge
*cs
;
3031 int i
, j
, count
= ipa_get_param_count (dest_info
);
3033 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3035 int c
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
3040 for (i
= 0; i
< count
; i
++)
3042 struct cgraph_edge
*cs
;
3043 vec
<ipa_agg_jf_item_t
> inter
= vNULL
;
3044 struct ipa_agg_jf_item
*item
;
3047 /* Among other things, the following check should deal with all by_ref
3049 if (ipa_get_parm_lattices (dest_info
, i
)->aggs_bottom
)
3052 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3054 inter
= intersect_aggregates_with_edge (cs
, i
, inter
);
3056 if (!inter
.exists ())
3060 FOR_EACH_VEC_ELT (inter
, j
, item
)
3062 struct ipa_agg_replacement_value
*v
;
3067 v
= ggc_alloc_ipa_agg_replacement_value ();
3069 v
->offset
= item
->offset
;
3070 v
->value
= item
->value
;
3076 if (inter
.exists ())
3082 /* Turn KNOWN_AGGS into a list of aggreate replacement values. */
3084 static struct ipa_agg_replacement_value
*
3085 known_aggs_to_agg_replacement_list (vec
<ipa_agg_jump_function_t
> known_aggs
)
3087 struct ipa_agg_replacement_value
*res
= NULL
;
3088 struct ipa_agg_jump_function
*aggjf
;
3089 struct ipa_agg_jf_item
*item
;
3092 FOR_EACH_VEC_ELT (known_aggs
, i
, aggjf
)
3093 FOR_EACH_VEC_SAFE_ELT (aggjf
->items
, j
, item
)
3095 struct ipa_agg_replacement_value
*v
;
3096 v
= ggc_alloc_ipa_agg_replacement_value ();
3098 v
->offset
= item
->offset
;
3099 v
->value
= item
->value
;
3106 /* Determine whether CS also brings all scalar values that the NODE is
3110 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge
*cs
,
3111 struct cgraph_node
*node
)
3113 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
3114 int count
= ipa_get_param_count (dest_info
);
3115 struct ipa_node_params
*caller_info
;
3116 struct ipa_edge_args
*args
;
3119 caller_info
= IPA_NODE_REF (cs
->caller
);
3120 args
= IPA_EDGE_REF (cs
);
3121 for (i
= 0; i
< count
; i
++)
3123 struct ipa_jump_func
*jump_func
;
3126 val
= dest_info
->known_vals
[i
];
3130 if (i
>= ipa_get_cs_argument_count (args
))
3132 jump_func
= ipa_get_ith_jump_func (args
, i
);
3133 t
= ipa_value_from_jfunc (caller_info
, jump_func
);
3134 if (!t
|| !values_equal_for_ipcp_p (val
, t
))
3140 /* Determine whether CS also brings all aggregate values that NODE is
3143 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge
*cs
,
3144 struct cgraph_node
*node
)
3146 struct ipa_node_params
*orig_caller_info
= IPA_NODE_REF (cs
->caller
);
3147 struct ipa_agg_replacement_value
*aggval
;
3150 aggval
= ipa_get_agg_replacements_for_node (node
);
3154 count
= ipa_get_param_count (IPA_NODE_REF (node
));
3155 ec
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
3157 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
3158 if (aggval
->index
>= ec
)
3161 if (orig_caller_info
->ipcp_orig_node
)
3162 orig_caller_info
= IPA_NODE_REF (orig_caller_info
->ipcp_orig_node
);
3164 for (i
= 0; i
< count
; i
++)
3166 static vec
<ipa_agg_jf_item_t
> values
= vec
<ipa_agg_jf_item_t
>();
3167 struct ipcp_param_lattices
*plats
;
3168 bool interesting
= false;
3169 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
3170 if (aggval
->index
== i
)
3178 plats
= ipa_get_parm_lattices (orig_caller_info
, aggval
->index
);
3179 if (plats
->aggs_bottom
)
3182 values
= intersect_aggregates_with_edge (cs
, i
, values
);
3183 if (!values
.exists())
3186 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
3187 if (aggval
->index
== i
)
3189 struct ipa_agg_jf_item
*item
;
3192 FOR_EACH_VEC_ELT (values
, j
, item
)
3194 && item
->offset
== av
->offset
3195 && values_equal_for_ipcp_p (item
->value
, av
->value
))
3207 /* Given an original NODE and a VAL for which we have already created a
3208 specialized clone, look whether there are incoming edges that still lead
3209 into the old node but now also bring the requested value and also conform to
3210 all other criteria such that they can be redirected the the special node.
3211 This function can therefore redirect the final edge in a SCC. */
3214 perhaps_add_new_callers (struct cgraph_node
*node
, struct ipcp_value
*val
)
3216 struct ipcp_value_source
*src
;
3217 gcov_type redirected_sum
= 0;
3219 for (src
= val
->sources
; src
; src
= src
->next
)
3221 struct cgraph_edge
*cs
= src
->cs
;
3224 enum availability availability
;
3225 struct cgraph_node
*dst
= cgraph_function_node (cs
->callee
,
3227 if ((dst
== node
|| IPA_NODE_REF (dst
)->is_all_contexts_clone
)
3228 && availability
> AVAIL_OVERWRITABLE
3229 && cgraph_edge_brings_value_p (cs
, src
))
3231 if (cgraph_edge_brings_all_scalars_for_node (cs
, val
->spec_node
)
3232 && cgraph_edge_brings_all_agg_vals_for_node (cs
,
3236 fprintf (dump_file
, " - adding an extra caller %s/%i"
3238 xstrdup (cgraph_node_name (cs
->caller
)),
3240 xstrdup (cgraph_node_name (val
->spec_node
)),
3241 val
->spec_node
->uid
);
3243 cgraph_redirect_edge_callee (cs
, val
->spec_node
);
3244 redirected_sum
+= cs
->count
;
3247 cs
= get_next_cgraph_edge_clone (cs
);
3252 update_specialized_profile (val
->spec_node
, node
, redirected_sum
);
3256 /* Copy KNOWN_BINFOS to KNOWN_VALS. */
3259 move_binfos_to_values (vec
<tree
> known_vals
,
3260 vec
<tree
> known_binfos
)
3265 for (i
= 0; known_binfos
.iterate (i
, &t
); i
++)
3270 /* Return true if there is a replacement equivalent to VALUE, INDEX and OFFSET
3271 among those in the AGGVALS list. */
3274 ipcp_val_in_agg_replacements_p (struct ipa_agg_replacement_value
*aggvals
,
3275 int index
, HOST_WIDE_INT offset
, tree value
)
3279 if (aggvals
->index
== index
3280 && aggvals
->offset
== offset
3281 && values_equal_for_ipcp_p (aggvals
->value
, value
))
3283 aggvals
= aggvals
->next
;
3288 /* Decide wheter to create a special version of NODE for value VAL of parameter
3289 at the given INDEX. If OFFSET is -1, the value is for the parameter itself,
3290 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS,
3291 KNOWN_BINFOS and KNOWN_AGGS describe the other already known values. */
3294 decide_about_value (struct cgraph_node
*node
, int index
, HOST_WIDE_INT offset
,
3295 struct ipcp_value
*val
, vec
<tree
> known_csts
,
3296 vec
<tree
> known_binfos
)
3298 struct ipa_agg_replacement_value
*aggvals
;
3299 int freq_sum
, caller_count
;
3300 gcov_type count_sum
;
3301 vec
<cgraph_edge_p
> callers
;
3306 perhaps_add_new_callers (node
, val
);
3309 else if (val
->local_size_cost
+ overall_size
> max_new_size
)
3311 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3312 fprintf (dump_file
, " Ignoring candidate value because "
3313 "max_new_size would be reached with %li.\n",
3314 val
->local_size_cost
+ overall_size
);
3317 else if (!get_info_about_necessary_edges (val
, &freq_sum
, &count_sum
,
3321 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3323 fprintf (dump_file
, " - considering value ");
3324 print_ipcp_constant_value (dump_file
, val
->value
);
3325 fprintf (dump_file
, " for parameter ");
3326 print_generic_expr (dump_file
, ipa_get_param (IPA_NODE_REF (node
),
3329 fprintf (dump_file
, ", offset: " HOST_WIDE_INT_PRINT_DEC
, offset
);
3330 fprintf (dump_file
, " (caller_count: %i)\n", caller_count
);
3333 if (!good_cloning_opportunity_p (node
, val
->local_time_benefit
,
3334 freq_sum
, count_sum
,
3335 val
->local_size_cost
)
3336 && !good_cloning_opportunity_p (node
,
3337 val
->local_time_benefit
3338 + val
->prop_time_benefit
,
3339 freq_sum
, count_sum
,
3340 val
->local_size_cost
3341 + val
->prop_size_cost
))
3345 fprintf (dump_file
, " Creating a specialized node of %s/%i.\n",
3346 cgraph_node_name (node
), node
->uid
);
3348 callers
= gather_edges_for_value (val
, caller_count
);
3349 kv
= known_csts
.copy ();
3350 move_binfos_to_values (kv
, known_binfos
);
3352 kv
[index
] = val
->value
;
3353 find_more_scalar_values_for_callers_subset (node
, kv
, callers
);
3354 aggvals
= find_aggregate_values_for_callers_subset (node
, callers
);
3355 gcc_checking_assert (offset
== -1
3356 || ipcp_val_in_agg_replacements_p (aggvals
, index
,
3357 offset
, val
->value
));
3358 val
->spec_node
= create_specialized_node (node
, kv
, aggvals
, callers
);
3359 overall_size
+= val
->local_size_cost
;
3361 /* TODO: If for some lattice there is only one other known value
3362 left, make a special node for it too. */
3367 /* Decide whether and what specialized clones of NODE should be created. */
3370 decide_whether_version_node (struct cgraph_node
*node
)
3372 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3373 int i
, count
= ipa_get_param_count (info
);
3374 vec
<tree
> known_csts
, known_binfos
;
3375 vec
<ipa_agg_jump_function_t
> known_aggs
= vNULL
;
3381 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3382 fprintf (dump_file
, "\nEvaluating opportunities for %s/%i.\n",
3383 cgraph_node_name (node
), node
->uid
);
3385 gather_context_independent_values (info
, &known_csts
, &known_binfos
,
3386 info
->do_clone_for_all_contexts
? &known_aggs
3389 for (i
= 0; i
< count
;i
++)
3391 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3392 struct ipcp_lattice
*lat
= &plats
->itself
;
3393 struct ipcp_value
*val
;
3397 && !known_binfos
[i
])
3398 for (val
= lat
->values
; val
; val
= val
->next
)
3399 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
3402 if (!plats
->aggs_bottom
)
3404 struct ipcp_agg_lattice
*aglat
;
3405 struct ipcp_value
*val
;
3406 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3407 if (!aglat
->bottom
&& aglat
->values
3408 /* If the following is false, the one value is in
3410 && (plats
->aggs_contain_variable
3411 || !ipa_lat_is_single_const (aglat
)))
3412 for (val
= aglat
->values
; val
; val
= val
->next
)
3413 ret
|= decide_about_value (node
, i
, aglat
->offset
, val
,
3414 known_csts
, known_binfos
);
3416 info
= IPA_NODE_REF (node
);
3419 if (info
->do_clone_for_all_contexts
)
3421 struct cgraph_node
*clone
;
3422 vec
<cgraph_edge_p
> callers
;
3425 fprintf (dump_file
, " - Creating a specialized node of %s/%i "
3426 "for all known contexts.\n", cgraph_node_name (node
),
3429 callers
= collect_callers_of_node (node
);
3430 move_binfos_to_values (known_csts
, known_binfos
);
3431 clone
= create_specialized_node (node
, known_csts
,
3432 known_aggs_to_agg_replacement_list (known_aggs
),
3434 info
= IPA_NODE_REF (node
);
3435 info
->do_clone_for_all_contexts
= false;
3436 IPA_NODE_REF (clone
)->is_all_contexts_clone
= true;
3437 for (i
= 0; i
< count
; i
++)
3438 vec_free (known_aggs
[i
].items
);
3439 known_aggs
.release ();
3443 known_csts
.release ();
3445 known_binfos
.release ();
3449 /* Transitively mark all callees of NODE within the same SCC as not dead. */
3452 spread_undeadness (struct cgraph_node
*node
)
3454 struct cgraph_edge
*cs
;
3456 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
3457 if (edge_within_scc (cs
))
3459 struct cgraph_node
*callee
;
3460 struct ipa_node_params
*info
;
3462 callee
= cgraph_function_node (cs
->callee
, NULL
);
3463 info
= IPA_NODE_REF (callee
);
3465 if (info
->node_dead
)
3467 info
->node_dead
= 0;
3468 spread_undeadness (callee
);
3473 /* Return true if NODE has a caller from outside of its SCC that is not
3474 dead. Worker callback for cgraph_for_node_and_aliases. */
3477 has_undead_caller_from_outside_scc_p (struct cgraph_node
*node
,
3478 void *data ATTRIBUTE_UNUSED
)
3480 struct cgraph_edge
*cs
;
3482 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
3483 if (cs
->caller
->thunk
.thunk_p
3484 && cgraph_for_node_and_aliases (cs
->caller
,
3485 has_undead_caller_from_outside_scc_p
,
3488 else if (!edge_within_scc (cs
)
3489 && !IPA_NODE_REF (cs
->caller
)->node_dead
)
3495 /* Identify nodes within the same SCC as NODE which are no longer needed
3496 because of new clones and will be removed as unreachable. */
3499 identify_dead_nodes (struct cgraph_node
*node
)
3501 struct cgraph_node
*v
;
3502 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->symbol
.aux
)->next_cycle
)
3503 if (cgraph_will_be_removed_from_program_if_no_direct_calls (v
)
3504 && !cgraph_for_node_and_aliases (v
,
3505 has_undead_caller_from_outside_scc_p
,
3507 IPA_NODE_REF (v
)->node_dead
= 1;
3509 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->symbol
.aux
)->next_cycle
)
3510 if (!IPA_NODE_REF (v
)->node_dead
)
3511 spread_undeadness (v
);
3513 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3515 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->symbol
.aux
)->next_cycle
)
3516 if (IPA_NODE_REF (v
)->node_dead
)
3517 fprintf (dump_file
, " Marking node as dead: %s/%i.\n",
3518 cgraph_node_name (v
), v
->uid
);
3522 /* The decision stage. Iterate over the topological order of call graph nodes
3523 TOPO and make specialized clones if deemed beneficial. */
3526 ipcp_decision_stage (struct topo_info
*topo
)
3531 fprintf (dump_file
, "\nIPA decision stage:\n\n");
3533 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
3535 struct cgraph_node
*node
= topo
->order
[i
];
3536 bool change
= false, iterate
= true;
3540 struct cgraph_node
*v
;
3542 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->symbol
.aux
)->next_cycle
)
3543 if (cgraph_function_with_gimple_body_p (v
)
3544 && ipcp_versionable_function_p (v
))
3545 iterate
|= decide_whether_version_node (v
);
3550 identify_dead_nodes (node
);
3554 /* The IPCP driver. */
3559 struct cgraph_2edge_hook_list
*edge_duplication_hook_holder
;
3560 struct topo_info topo
;
3562 ipa_check_create_node_params ();
3563 ipa_check_create_edge_args ();
3564 grow_next_edge_clone_vector ();
3565 edge_duplication_hook_holder
=
3566 cgraph_add_edge_duplication_hook (&ipcp_edge_duplication_hook
, NULL
);
3567 ipcp_values_pool
= create_alloc_pool ("IPA-CP values",
3568 sizeof (struct ipcp_value
), 32);
3569 ipcp_sources_pool
= create_alloc_pool ("IPA-CP value sources",
3570 sizeof (struct ipcp_value_source
), 64);
3571 ipcp_agg_lattice_pool
= create_alloc_pool ("IPA_CP aggregate lattices",
3572 sizeof (struct ipcp_agg_lattice
),
3576 fprintf (dump_file
, "\nIPA structures before propagation:\n");
3577 if (dump_flags
& TDF_DETAILS
)
3578 ipa_print_all_params (dump_file
);
3579 ipa_print_all_jump_functions (dump_file
);
3582 /* Topological sort. */
3583 build_toporder_info (&topo
);
3584 /* Do the interprocedural propagation. */
3585 ipcp_propagate_stage (&topo
);
3586 /* Decide what constant propagation and cloning should be performed. */
3587 ipcp_decision_stage (&topo
);
3589 /* Free all IPCP structures. */
3590 free_toporder_info (&topo
);
3591 next_edge_clone
.release ();
3592 cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder
);
3593 ipa_free_all_structures_after_ipa_cp ();
3595 fprintf (dump_file
, "\nIPA constant propagation end\n");
3599 /* Initialization and computation of IPCP data structures. This is the initial
3600 intraprocedural analysis of functions, which gathers information to be
3601 propagated later on. */
3604 ipcp_generate_summary (void)
3606 struct cgraph_node
*node
;
3609 fprintf (dump_file
, "\nIPA constant propagation start:\n");
3610 ipa_register_cgraph_hooks ();
3612 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
3614 node
->local
.versionable
3615 = tree_versionable_function_p (node
->symbol
.decl
);
3616 ipa_analyze_node (node
);
3620 /* Write ipcp summary for nodes in SET. */
3623 ipcp_write_summary (void)
3625 ipa_prop_write_jump_functions ();
3628 /* Read ipcp summary. */
3631 ipcp_read_summary (void)
3633 ipa_prop_read_jump_functions ();
3636 /* Gate for IPCP optimization. */
3639 cgraph_gate_cp (void)
3641 /* FIXME: We should remove the optimize check after we ensure we never run
3642 IPA passes when not optimizing. */
3643 return flag_ipa_cp
&& optimize
;
3646 struct ipa_opt_pass_d pass_ipa_cp
=
3651 OPTGROUP_NONE
, /* optinfo_flags */
3652 cgraph_gate_cp
, /* gate */
3653 ipcp_driver
, /* execute */
3656 0, /* static_pass_number */
3657 TV_IPA_CONSTANT_PROP
, /* tv_id */
3658 0, /* properties_required */
3659 0, /* properties_provided */
3660 0, /* properties_destroyed */
3661 0, /* todo_flags_start */
3663 TODO_remove_functions
/* todo_flags_finish */
3665 ipcp_generate_summary
, /* generate_summary */
3666 ipcp_write_summary
, /* write_summary */
3667 ipcp_read_summary
, /* read_summary */
3668 ipa_prop_write_all_agg_replacement
, /* write_optimization_summary */
3669 ipa_prop_read_all_agg_replacement
, /* read_optimization_summary */
3670 NULL
, /* stmt_fixup */
3672 ipcp_transform_function
, /* function_transform */
3673 NULL
, /* variable_transform */