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 /* Determine whether JFUNC evaluates to a known value (that is either a
795 constant or a binfo) and if so, return it. Otherwise return NULL. INFO
796 describes the caller node so that pass-through jump functions can be
800 ipa_value_from_jfunc (struct ipa_node_params
*info
, struct ipa_jump_func
*jfunc
)
802 if (jfunc
->type
== IPA_JF_CONST
)
803 return ipa_get_jf_constant (jfunc
);
804 else if (jfunc
->type
== IPA_JF_KNOWN_TYPE
)
805 return ipa_binfo_from_known_type_jfunc (jfunc
);
806 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
807 || jfunc
->type
== IPA_JF_ANCESTOR
)
812 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
813 idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
815 idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
817 if (info
->ipcp_orig_node
)
818 input
= info
->known_vals
[idx
];
821 struct ipcp_lattice
*lat
;
825 gcc_checking_assert (!flag_ipa_cp
);
828 lat
= ipa_get_scalar_lat (info
, idx
);
829 if (!ipa_lat_is_single_const (lat
))
831 input
= lat
->values
->value
;
837 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
838 return ipa_get_jf_pass_through_result (jfunc
, input
);
840 return ipa_get_jf_ancestor_result (jfunc
, input
);
847 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
848 bottom, not containing a variable component and without any known value at
852 ipcp_verify_propagated_values (void)
854 struct cgraph_node
*node
;
856 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
858 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
859 int i
, count
= ipa_get_param_count (info
);
861 for (i
= 0; i
< count
; i
++)
863 struct ipcp_lattice
*lat
= ipa_get_scalar_lat (info
, i
);
866 && !lat
->contains_variable
867 && lat
->values_count
== 0)
871 fprintf (dump_file
, "\nIPA lattices after constant "
873 print_all_lattices (dump_file
, true, false);
882 /* Return true iff X and Y should be considered equal values by IPA-CP. */
885 values_equal_for_ipcp_p (tree x
, tree y
)
887 gcc_checking_assert (x
!= NULL_TREE
&& y
!= NULL_TREE
);
892 if (TREE_CODE (x
) == TREE_BINFO
|| TREE_CODE (y
) == TREE_BINFO
)
895 if (TREE_CODE (x
) == ADDR_EXPR
896 && TREE_CODE (y
) == ADDR_EXPR
897 && TREE_CODE (TREE_OPERAND (x
, 0)) == CONST_DECL
898 && TREE_CODE (TREE_OPERAND (y
, 0)) == CONST_DECL
)
899 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x
, 0)),
900 DECL_INITIAL (TREE_OPERAND (y
, 0)), 0);
902 return operand_equal_p (x
, y
, 0);
905 /* Add a new value source to VAL, marking that a value comes from edge CS and
906 (if the underlying jump function is a pass-through or an ancestor one) from
907 a caller value SRC_VAL of a caller parameter described by SRC_INDEX. OFFSET
908 is negative if the source was the scalar value of the parameter itself or
909 the offset within an aggregate. */
912 add_value_source (struct ipcp_value
*val
, struct cgraph_edge
*cs
,
913 struct ipcp_value
*src_val
, int src_idx
, HOST_WIDE_INT offset
)
915 struct ipcp_value_source
*src
;
917 src
= (struct ipcp_value_source
*) pool_alloc (ipcp_sources_pool
);
918 src
->offset
= offset
;
921 src
->index
= src_idx
;
923 src
->next
= val
->sources
;
927 /* Try to add NEWVAL to LAT, potentially creating a new struct ipcp_value for
928 it. CS, SRC_VAL SRC_INDEX and OFFSET are meant for add_value_source and
929 have the same meaning. */
932 add_value_to_lattice (struct ipcp_lattice
*lat
, tree newval
,
933 struct cgraph_edge
*cs
, struct ipcp_value
*src_val
,
934 int src_idx
, HOST_WIDE_INT offset
)
936 struct ipcp_value
*val
;
941 for (val
= lat
->values
; val
; val
= val
->next
)
942 if (values_equal_for_ipcp_p (val
->value
, newval
))
944 if (edge_within_scc (cs
))
946 struct ipcp_value_source
*s
;
947 for (s
= val
->sources
; s
; s
= s
->next
)
954 add_value_source (val
, cs
, src_val
, src_idx
, offset
);
958 if (lat
->values_count
== PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE
))
960 /* We can only free sources, not the values themselves, because sources
961 of other values in this this SCC might point to them. */
962 for (val
= lat
->values
; val
; val
= val
->next
)
966 struct ipcp_value_source
*src
= val
->sources
;
967 val
->sources
= src
->next
;
968 pool_free (ipcp_sources_pool
, src
);
973 return set_lattice_to_bottom (lat
);
977 val
= (struct ipcp_value
*) pool_alloc (ipcp_values_pool
);
978 memset (val
, 0, sizeof (*val
));
980 add_value_source (val
, cs
, src_val
, src_idx
, offset
);
982 val
->next
= lat
->values
;
987 /* Like above but passes a special value of offset to distinguish that the
988 origin is the scalar value of the parameter rather than a part of an
992 add_scalar_value_to_lattice (struct ipcp_lattice
*lat
, tree newval
,
993 struct cgraph_edge
*cs
,
994 struct ipcp_value
*src_val
, int src_idx
)
996 return add_value_to_lattice (lat
, newval
, cs
, src_val
, src_idx
, -1);
999 /* Propagate values through a pass-through jump function JFUNC associated with
1000 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1001 is the index of the source parameter. */
1004 propagate_vals_accross_pass_through (struct cgraph_edge
*cs
,
1005 struct ipa_jump_func
*jfunc
,
1006 struct ipcp_lattice
*src_lat
,
1007 struct ipcp_lattice
*dest_lat
,
1010 struct ipcp_value
*src_val
;
1013 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
1014 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1015 ret
|= add_scalar_value_to_lattice (dest_lat
, src_val
->value
, cs
,
1017 /* Do not create new values when propagating within an SCC because if there
1018 are arithmetic functions with circular dependencies, there is infinite
1019 number of them and we would just make lattices bottom. */
1020 else if (edge_within_scc (cs
))
1021 ret
= set_lattice_contains_variable (dest_lat
);
1023 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1025 tree cstval
= src_val
->value
;
1027 if (TREE_CODE (cstval
) == TREE_BINFO
)
1029 ret
|= set_lattice_contains_variable (dest_lat
);
1032 cstval
= ipa_get_jf_pass_through_result (jfunc
, cstval
);
1035 ret
|= add_scalar_value_to_lattice (dest_lat
, cstval
, cs
, src_val
,
1038 ret
|= set_lattice_contains_variable (dest_lat
);
1044 /* Propagate values through an ancestor jump function JFUNC associated with
1045 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1046 is the index of the source parameter. */
1049 propagate_vals_accross_ancestor (struct cgraph_edge
*cs
,
1050 struct ipa_jump_func
*jfunc
,
1051 struct ipcp_lattice
*src_lat
,
1052 struct ipcp_lattice
*dest_lat
,
1055 struct ipcp_value
*src_val
;
1058 if (edge_within_scc (cs
))
1059 return set_lattice_contains_variable (dest_lat
);
1061 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1063 tree t
= ipa_get_jf_ancestor_result (jfunc
, src_val
->value
);
1066 ret
|= add_scalar_value_to_lattice (dest_lat
, t
, cs
, src_val
, src_idx
);
1068 ret
|= set_lattice_contains_variable (dest_lat
);
1074 /* Propagate scalar values across jump function JFUNC that is associated with
1075 edge CS and put the values into DEST_LAT. */
1078 propagate_scalar_accross_jump_function (struct cgraph_edge
*cs
,
1079 struct ipa_jump_func
*jfunc
,
1080 struct ipcp_lattice
*dest_lat
)
1082 if (dest_lat
->bottom
)
1085 if (jfunc
->type
== IPA_JF_CONST
1086 || jfunc
->type
== IPA_JF_KNOWN_TYPE
)
1090 if (jfunc
->type
== IPA_JF_KNOWN_TYPE
)
1092 val
= ipa_binfo_from_known_type_jfunc (jfunc
);
1094 return set_lattice_contains_variable (dest_lat
);
1097 val
= ipa_get_jf_constant (jfunc
);
1098 return add_scalar_value_to_lattice (dest_lat
, val
, cs
, NULL
, 0);
1100 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1101 || jfunc
->type
== IPA_JF_ANCESTOR
)
1103 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1104 struct ipcp_lattice
*src_lat
;
1108 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1109 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1111 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1113 src_lat
= ipa_get_scalar_lat (caller_info
, src_idx
);
1114 if (src_lat
->bottom
)
1115 return set_lattice_contains_variable (dest_lat
);
1117 /* If we would need to clone the caller and cannot, do not propagate. */
1118 if (!ipcp_versionable_function_p (cs
->caller
)
1119 && (src_lat
->contains_variable
1120 || (src_lat
->values_count
> 1)))
1121 return set_lattice_contains_variable (dest_lat
);
1123 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1124 ret
= propagate_vals_accross_pass_through (cs
, jfunc
, src_lat
,
1127 ret
= propagate_vals_accross_ancestor (cs
, jfunc
, src_lat
, dest_lat
,
1130 if (src_lat
->contains_variable
)
1131 ret
|= set_lattice_contains_variable (dest_lat
);
1136 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1137 use it for indirect inlining), we should propagate them too. */
1138 return set_lattice_contains_variable (dest_lat
);
1141 /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
1142 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
1143 other cases, return false). If there are no aggregate items, set
1144 aggs_by_ref to NEW_AGGS_BY_REF. */
1147 set_check_aggs_by_ref (struct ipcp_param_lattices
*dest_plats
,
1148 bool new_aggs_by_ref
)
1150 if (dest_plats
->aggs
)
1152 if (dest_plats
->aggs_by_ref
!= new_aggs_by_ref
)
1154 set_agg_lats_to_bottom (dest_plats
);
1159 dest_plats
->aggs_by_ref
= new_aggs_by_ref
;
1163 /* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
1164 already existing lattice for the given OFFSET and SIZE, marking all skipped
1165 lattices as containing variable and checking for overlaps. If there is no
1166 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
1167 it with offset, size and contains_variable to PRE_EXISTING, and return true,
1168 unless there are too many already. If there are two many, return false. If
1169 there are overlaps turn whole DEST_PLATS to bottom and return false. If any
1170 skipped lattices were newly marked as containing variable, set *CHANGE to
1174 merge_agg_lats_step (struct ipcp_param_lattices
*dest_plats
,
1175 HOST_WIDE_INT offset
, HOST_WIDE_INT val_size
,
1176 struct ipcp_agg_lattice
***aglat
,
1177 bool pre_existing
, bool *change
)
1179 gcc_checking_assert (offset
>= 0);
1181 while (**aglat
&& (**aglat
)->offset
< offset
)
1183 if ((**aglat
)->offset
+ (**aglat
)->size
> offset
)
1185 set_agg_lats_to_bottom (dest_plats
);
1188 *change
|= set_lattice_contains_variable (**aglat
);
1189 *aglat
= &(**aglat
)->next
;
1192 if (**aglat
&& (**aglat
)->offset
== offset
)
1194 if ((**aglat
)->size
!= val_size
1196 && (**aglat
)->next
->offset
< offset
+ val_size
))
1198 set_agg_lats_to_bottom (dest_plats
);
1201 gcc_checking_assert (!(**aglat
)->next
1202 || (**aglat
)->next
->offset
>= offset
+ val_size
);
1207 struct ipcp_agg_lattice
*new_al
;
1209 if (**aglat
&& (**aglat
)->offset
< offset
+ val_size
)
1211 set_agg_lats_to_bottom (dest_plats
);
1214 if (dest_plats
->aggs_count
== PARAM_VALUE (PARAM_IPA_MAX_AGG_ITEMS
))
1216 dest_plats
->aggs_count
++;
1217 new_al
= (struct ipcp_agg_lattice
*) pool_alloc (ipcp_agg_lattice_pool
);
1218 memset (new_al
, 0, sizeof (*new_al
));
1220 new_al
->offset
= offset
;
1221 new_al
->size
= val_size
;
1222 new_al
->contains_variable
= pre_existing
;
1224 new_al
->next
= **aglat
;
1230 /* Set all AGLAT and all other aggregate lattices reachable by next pointers as
1231 containing an unknown value. */
1234 set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice
*aglat
)
1239 ret
|= set_lattice_contains_variable (aglat
);
1240 aglat
= aglat
->next
;
1245 /* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
1246 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source
1247 parameter used for lattice value sources. Return true if DEST_PLATS changed
1251 merge_aggregate_lattices (struct cgraph_edge
*cs
,
1252 struct ipcp_param_lattices
*dest_plats
,
1253 struct ipcp_param_lattices
*src_plats
,
1254 int src_idx
, HOST_WIDE_INT offset_delta
)
1256 bool pre_existing
= dest_plats
->aggs
!= NULL
;
1257 struct ipcp_agg_lattice
**dst_aglat
;
1260 if (set_check_aggs_by_ref (dest_plats
, src_plats
->aggs_by_ref
))
1262 if (src_plats
->aggs_bottom
)
1263 return set_agg_lats_contain_variable (dest_plats
);
1264 if (src_plats
->aggs_contain_variable
)
1265 ret
|= set_agg_lats_contain_variable (dest_plats
);
1266 dst_aglat
= &dest_plats
->aggs
;
1268 for (struct ipcp_agg_lattice
*src_aglat
= src_plats
->aggs
;
1270 src_aglat
= src_aglat
->next
)
1272 HOST_WIDE_INT new_offset
= src_aglat
->offset
- offset_delta
;
1276 if (merge_agg_lats_step (dest_plats
, new_offset
, src_aglat
->size
,
1277 &dst_aglat
, pre_existing
, &ret
))
1279 struct ipcp_agg_lattice
*new_al
= *dst_aglat
;
1281 dst_aglat
= &(*dst_aglat
)->next
;
1282 if (src_aglat
->bottom
)
1284 ret
|= set_lattice_contains_variable (new_al
);
1287 if (src_aglat
->contains_variable
)
1288 ret
|= set_lattice_contains_variable (new_al
);
1289 for (struct ipcp_value
*val
= src_aglat
->values
;
1292 ret
|= add_value_to_lattice (new_al
, val
->value
, cs
, val
, src_idx
,
1295 else if (dest_plats
->aggs_bottom
)
1298 ret
|= set_chain_of_aglats_contains_variable (*dst_aglat
);
1302 /* Determine whether there is anything to propagate FROM SRC_PLATS through a
1303 pass-through JFUNC and if so, whether it has conform and conforms to the
1304 rules about propagating values passed by reference. */
1307 agg_pass_through_permissible_p (struct ipcp_param_lattices
*src_plats
,
1308 struct ipa_jump_func
*jfunc
)
1310 return src_plats
->aggs
1311 && (!src_plats
->aggs_by_ref
1312 || ipa_get_jf_pass_through_agg_preserved (jfunc
));
1315 /* Propagate scalar values across jump function JFUNC that is associated with
1316 edge CS and put the values into DEST_LAT. */
1319 propagate_aggs_accross_jump_function (struct cgraph_edge
*cs
,
1320 struct ipa_jump_func
*jfunc
,
1321 struct ipcp_param_lattices
*dest_plats
)
1325 if (dest_plats
->aggs_bottom
)
1328 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1329 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
1331 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1332 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1333 struct ipcp_param_lattices
*src_plats
;
1335 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
1336 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
1338 /* Currently we do not produce clobber aggregate jump
1339 functions, replace with merging when we do. */
1340 gcc_assert (!jfunc
->agg
.items
);
1341 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
,
1345 ret
|= set_agg_lats_contain_variable (dest_plats
);
1347 else if (jfunc
->type
== IPA_JF_ANCESTOR
1348 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
1350 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1351 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1352 struct ipcp_param_lattices
*src_plats
;
1354 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
1355 if (src_plats
->aggs
&& src_plats
->aggs_by_ref
)
1357 /* Currently we do not produce clobber aggregate jump
1358 functions, replace with merging when we do. */
1359 gcc_assert (!jfunc
->agg
.items
);
1360 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
, src_idx
,
1361 ipa_get_jf_ancestor_offset (jfunc
));
1363 else if (!src_plats
->aggs_by_ref
)
1364 ret
|= set_agg_lats_to_bottom (dest_plats
);
1366 ret
|= set_agg_lats_contain_variable (dest_plats
);
1368 else if (jfunc
->agg
.items
)
1370 bool pre_existing
= dest_plats
->aggs
!= NULL
;
1371 struct ipcp_agg_lattice
**aglat
= &dest_plats
->aggs
;
1372 struct ipa_agg_jf_item
*item
;
1375 if (set_check_aggs_by_ref (dest_plats
, jfunc
->agg
.by_ref
))
1378 FOR_EACH_VEC_ELT (*jfunc
->agg
.items
, i
, item
)
1380 HOST_WIDE_INT val_size
;
1382 if (item
->offset
< 0)
1384 gcc_checking_assert (is_gimple_ip_invariant (item
->value
));
1385 val_size
= tree_low_cst (TYPE_SIZE (TREE_TYPE (item
->value
)), 1);
1387 if (merge_agg_lats_step (dest_plats
, item
->offset
, val_size
,
1388 &aglat
, pre_existing
, &ret
))
1390 ret
|= add_value_to_lattice (*aglat
, item
->value
, cs
, NULL
, 0, 0);
1391 aglat
= &(*aglat
)->next
;
1393 else if (dest_plats
->aggs_bottom
)
1397 ret
|= set_chain_of_aglats_contains_variable (*aglat
);
1400 ret
|= set_agg_lats_contain_variable (dest_plats
);
1405 /* Propagate constants from the caller to the callee of CS. INFO describes the
1409 propagate_constants_accross_call (struct cgraph_edge
*cs
)
1411 struct ipa_node_params
*callee_info
;
1412 enum availability availability
;
1413 struct cgraph_node
*callee
, *alias_or_thunk
;
1414 struct ipa_edge_args
*args
;
1416 int i
, args_count
, parms_count
;
1418 callee
= cgraph_function_node (cs
->callee
, &availability
);
1419 if (!callee
->analyzed
)
1421 gcc_checking_assert (cgraph_function_with_gimple_body_p (callee
));
1422 callee_info
= IPA_NODE_REF (callee
);
1424 args
= IPA_EDGE_REF (cs
);
1425 args_count
= ipa_get_cs_argument_count (args
);
1426 parms_count
= ipa_get_param_count (callee_info
);
1428 /* If this call goes through a thunk we must not propagate to the first (0th)
1429 parameter. However, we might need to uncover a thunk from below a series
1430 of aliases first. */
1431 alias_or_thunk
= cs
->callee
;
1432 while (alias_or_thunk
->alias
)
1433 alias_or_thunk
= cgraph_alias_aliased_node (alias_or_thunk
);
1434 if (alias_or_thunk
->thunk
.thunk_p
)
1436 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
1443 for (; (i
< args_count
) && (i
< parms_count
); i
++)
1445 struct ipa_jump_func
*jump_func
= ipa_get_ith_jump_func (args
, i
);
1446 struct ipcp_param_lattices
*dest_plats
;
1448 dest_plats
= ipa_get_parm_lattices (callee_info
, i
);
1449 if (availability
== AVAIL_OVERWRITABLE
)
1450 ret
|= set_all_contains_variable (dest_plats
);
1453 ret
|= propagate_scalar_accross_jump_function (cs
, jump_func
,
1454 &dest_plats
->itself
);
1455 ret
|= propagate_aggs_accross_jump_function (cs
, jump_func
,
1459 for (; i
< parms_count
; i
++)
1460 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
, i
));
1465 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
1466 (which can contain both constants and binfos), KNOWN_BINFOS, KNOWN_AGGS or
1467 AGG_REPS return the destination. The latter three can be NULL. If AGG_REPS
1468 is not NULL, KNOWN_AGGS is ignored. */
1471 ipa_get_indirect_edge_target_1 (struct cgraph_edge
*ie
,
1472 vec
<tree
> known_vals
,
1473 vec
<tree
> known_binfos
,
1474 vec
<ipa_agg_jump_function_p
> known_aggs
,
1475 struct ipa_agg_replacement_value
*agg_reps
)
1477 int param_index
= ie
->indirect_info
->param_index
;
1478 HOST_WIDE_INT token
, anc_offset
;
1482 if (param_index
== -1)
1485 if (!ie
->indirect_info
->polymorphic
)
1489 if (ie
->indirect_info
->agg_contents
)
1496 if (agg_reps
->index
== param_index
1497 && agg_reps
->offset
== ie
->indirect_info
->offset
1498 && agg_reps
->by_ref
== ie
->indirect_info
->by_ref
)
1500 t
= agg_reps
->value
;
1503 agg_reps
= agg_reps
->next
;
1506 else if (known_aggs
.length () > (unsigned int) param_index
)
1508 struct ipa_agg_jump_function
*agg
;
1509 agg
= known_aggs
[param_index
];
1510 t
= ipa_find_agg_cst_for_param (agg
, ie
->indirect_info
->offset
,
1511 ie
->indirect_info
->by_ref
);
1517 t
= (known_vals
.length () > (unsigned int) param_index
1518 ? known_vals
[param_index
] : NULL
);
1521 TREE_CODE (t
) == ADDR_EXPR
1522 && TREE_CODE (TREE_OPERAND (t
, 0)) == FUNCTION_DECL
)
1523 return TREE_OPERAND (t
, 0);
1528 gcc_assert (!ie
->indirect_info
->agg_contents
);
1529 token
= ie
->indirect_info
->otr_token
;
1530 anc_offset
= ie
->indirect_info
->offset
;
1531 otr_type
= ie
->indirect_info
->otr_type
;
1533 t
= known_vals
[param_index
];
1534 if (!t
&& known_binfos
.length () > (unsigned int) param_index
)
1535 t
= known_binfos
[param_index
];
1539 if (TREE_CODE (t
) != TREE_BINFO
)
1542 binfo
= gimple_extract_devirt_binfo_from_cst (t
);
1545 binfo
= get_binfo_at_offset (binfo
, anc_offset
, otr_type
);
1548 return gimple_get_virt_method_for_binfo (token
, binfo
);
1554 binfo
= get_binfo_at_offset (t
, anc_offset
, otr_type
);
1557 return gimple_get_virt_method_for_binfo (token
, binfo
);
1562 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
1563 (which can contain both constants and binfos), KNOWN_BINFOS (which can be
1564 NULL) or KNOWN_AGGS (which also can be NULL) return the destination. */
1567 ipa_get_indirect_edge_target (struct cgraph_edge
*ie
,
1568 vec
<tree
> known_vals
,
1569 vec
<tree
> known_binfos
,
1570 vec
<ipa_agg_jump_function_p
> known_aggs
)
1572 return ipa_get_indirect_edge_target_1 (ie
, known_vals
, known_binfos
,
1576 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
1577 and KNOWN_BINFOS. */
1580 devirtualization_time_bonus (struct cgraph_node
*node
,
1581 vec
<tree
> known_csts
,
1582 vec
<tree
> known_binfos
,
1583 vec
<ipa_agg_jump_function_p
> known_aggs
)
1585 struct cgraph_edge
*ie
;
1588 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
1590 struct cgraph_node
*callee
;
1591 struct inline_summary
*isummary
;
1594 target
= ipa_get_indirect_edge_target (ie
, known_csts
, known_binfos
,
1599 /* Only bare minimum benefit for clearly un-inlineable targets. */
1601 callee
= cgraph_get_node (target
);
1602 if (!callee
|| !callee
->analyzed
)
1604 isummary
= inline_summary (callee
);
1605 if (!isummary
->inlinable
)
1608 /* FIXME: The values below need re-considering and perhaps also
1609 integrating into the cost metrics, at lest in some very basic way. */
1610 if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 4)
1612 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 2)
1614 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
1615 || DECL_DECLARED_INLINE_P (callee
->symbol
.decl
))
1622 /* Return time bonus incurred because of HINTS. */
1625 hint_time_bonus (inline_hints hints
)
1628 if (hints
& (INLINE_HINT_loop_iterations
| INLINE_HINT_loop_stride
))
1629 result
+= PARAM_VALUE (PARAM_IPA_CP_LOOP_HINT_BONUS
);
1630 if (hints
& INLINE_HINT_array_index
)
1631 result
+= PARAM_VALUE (PARAM_IPA_CP_ARRAY_INDEX_HINT_BONUS
);
1635 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
1636 and SIZE_COST and with the sum of frequencies of incoming edges to the
1637 potential new clone in FREQUENCIES. */
1640 good_cloning_opportunity_p (struct cgraph_node
*node
, int time_benefit
,
1641 int freq_sum
, gcov_type count_sum
, int size_cost
)
1643 if (time_benefit
== 0
1644 || !flag_ipa_cp_clone
1645 || !optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node
->symbol
.decl
)))
1648 gcc_assert (size_cost
> 0);
1652 int factor
= (count_sum
* 1000) / max_count
;
1653 HOST_WIDEST_INT evaluation
= (((HOST_WIDEST_INT
) time_benefit
* factor
)
1656 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1657 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
1658 "size: %i, count_sum: " HOST_WIDE_INT_PRINT_DEC
1659 ") -> evaluation: " HOST_WIDEST_INT_PRINT_DEC
1660 ", threshold: %i\n",
1661 time_benefit
, size_cost
, (HOST_WIDE_INT
) count_sum
,
1662 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
1664 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
1668 HOST_WIDEST_INT evaluation
= (((HOST_WIDEST_INT
) time_benefit
* freq_sum
)
1671 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1672 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
1673 "size: %i, freq_sum: %i) -> evaluation: "
1674 HOST_WIDEST_INT_PRINT_DEC
", threshold: %i\n",
1675 time_benefit
, size_cost
, freq_sum
, evaluation
,
1676 PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
1678 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
1682 /* Return all context independent values from aggregate lattices in PLATS in a
1683 vector. Return NULL if there are none. */
1685 static vec
<ipa_agg_jf_item_t
, va_gc
> *
1686 context_independent_aggregate_values (struct ipcp_param_lattices
*plats
)
1688 vec
<ipa_agg_jf_item_t
, va_gc
> *res
= NULL
;
1690 if (plats
->aggs_bottom
1691 || plats
->aggs_contain_variable
1692 || plats
->aggs_count
== 0)
1695 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
;
1697 aglat
= aglat
->next
)
1698 if (ipa_lat_is_single_const (aglat
))
1700 struct ipa_agg_jf_item item
;
1701 item
.offset
= aglat
->offset
;
1702 item
.value
= aglat
->values
->value
;
1703 vec_safe_push (res
, item
);
1708 /* Allocate KNOWN_CSTS, KNOWN_BINFOS and, if non-NULL, KNOWN_AGGS and populate
1709 them with values of parameters that are known independent of the context.
1710 INFO describes the function. If REMOVABLE_PARAMS_COST is non-NULL, the
1711 movement cost of all removable parameters will be stored in it. */
1714 gather_context_independent_values (struct ipa_node_params
*info
,
1715 vec
<tree
> *known_csts
,
1716 vec
<tree
> *known_binfos
,
1717 vec
<ipa_agg_jump_function_t
> *known_aggs
,
1718 int *removable_params_cost
)
1720 int i
, count
= ipa_get_param_count (info
);
1723 known_csts
->create (0);
1724 known_binfos
->create (0);
1725 known_csts
->safe_grow_cleared (count
);
1726 known_binfos
->safe_grow_cleared (count
);
1729 known_aggs
->create (0);
1730 known_aggs
->safe_grow_cleared (count
);
1733 if (removable_params_cost
)
1734 *removable_params_cost
= 0;
1736 for (i
= 0; i
< count
; i
++)
1738 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1739 struct ipcp_lattice
*lat
= &plats
->itself
;
1741 if (ipa_lat_is_single_const (lat
))
1743 struct ipcp_value
*val
= lat
->values
;
1744 if (TREE_CODE (val
->value
) != TREE_BINFO
)
1746 (*known_csts
)[i
] = val
->value
;
1747 if (removable_params_cost
)
1748 *removable_params_cost
1749 += estimate_move_cost (TREE_TYPE (val
->value
));
1752 else if (plats
->virt_call
)
1754 (*known_binfos
)[i
] = val
->value
;
1757 else if (removable_params_cost
1758 && !ipa_is_param_used (info
, i
))
1759 *removable_params_cost
1760 += estimate_move_cost (TREE_TYPE (ipa_get_param (info
, i
)));
1762 else if (removable_params_cost
1763 && !ipa_is_param_used (info
, i
))
1764 *removable_params_cost
1765 += estimate_move_cost (TREE_TYPE (ipa_get_param (info
, i
)));
1769 vec
<ipa_agg_jf_item_t
, va_gc
> *agg_items
;
1770 struct ipa_agg_jump_function
*ajf
;
1772 agg_items
= context_independent_aggregate_values (plats
);
1773 ajf
= &(*known_aggs
)[i
];
1774 ajf
->items
= agg_items
;
1775 ajf
->by_ref
= plats
->aggs_by_ref
;
1776 ret
|= agg_items
!= NULL
;
1783 /* The current interface in ipa-inline-analysis requires a pointer vector.
1786 FIXME: That interface should be re-worked, this is slightly silly. Still,
1787 I'd like to discuss how to change it first and this demonstrates the
1790 static vec
<ipa_agg_jump_function_p
>
1791 agg_jmp_p_vec_for_t_vec (vec
<ipa_agg_jump_function_t
> known_aggs
)
1793 vec
<ipa_agg_jump_function_p
> ret
;
1794 struct ipa_agg_jump_function
*ajf
;
1797 ret
.create (known_aggs
.length ());
1798 FOR_EACH_VEC_ELT (known_aggs
, i
, ajf
)
1799 ret
.quick_push (ajf
);
1803 /* Iterate over known values of parameters of NODE and estimate the local
1804 effects in terms of time and size they have. */
1807 estimate_local_effects (struct cgraph_node
*node
)
1809 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1810 int i
, count
= ipa_get_param_count (info
);
1811 vec
<tree
> known_csts
, known_binfos
;
1812 vec
<ipa_agg_jump_function_t
> known_aggs
;
1813 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
;
1815 int base_time
= inline_summary (node
)->time
;
1816 int removable_params_cost
;
1818 if (!count
|| !ipcp_versionable_function_p (node
))
1821 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1822 fprintf (dump_file
, "\nEstimating effects for %s/%i, base_time: %i.\n",
1823 cgraph_node_name (node
), node
->uid
, base_time
);
1825 always_const
= gather_context_independent_values (info
, &known_csts
,
1826 &known_binfos
, &known_aggs
,
1827 &removable_params_cost
);
1828 known_aggs_ptrs
= agg_jmp_p_vec_for_t_vec (known_aggs
);
1831 struct caller_statistics stats
;
1835 init_caller_stats (&stats
);
1836 cgraph_for_node_and_aliases (node
, gather_caller_stats
, &stats
, false);
1837 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_binfos
,
1838 known_aggs_ptrs
, &size
, &time
, &hints
);
1839 time
-= devirtualization_time_bonus (node
, known_csts
, known_binfos
,
1841 time
-= hint_time_bonus (hints
);
1842 time
-= removable_params_cost
;
1843 size
-= stats
.n_calls
* removable_params_cost
;
1846 fprintf (dump_file
, " - context independent values, size: %i, "
1847 "time_benefit: %i\n", size
, base_time
- time
);
1850 || cgraph_will_be_removed_from_program_if_no_direct_calls (node
))
1852 info
->do_clone_for_all_contexts
= true;
1856 fprintf (dump_file
, " Decided to specialize for all "
1857 "known contexts, code not going to grow.\n");
1859 else if (good_cloning_opportunity_p (node
, base_time
- time
,
1860 stats
.freq_sum
, stats
.count_sum
,
1863 if (size
+ overall_size
<= max_new_size
)
1865 info
->do_clone_for_all_contexts
= true;
1867 overall_size
+= size
;
1870 fprintf (dump_file
, " Decided to specialize for all "
1871 "known contexts, growth deemed beneficial.\n");
1873 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1874 fprintf (dump_file
, " Not cloning for all contexts because "
1875 "max_new_size would be reached with %li.\n",
1876 size
+ overall_size
);
1880 for (i
= 0; i
< count
; i
++)
1882 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1883 struct ipcp_lattice
*lat
= &plats
->itself
;
1884 struct ipcp_value
*val
;
1893 for (val
= lat
->values
; val
; val
= val
->next
)
1895 int time
, size
, time_benefit
;
1898 if (TREE_CODE (val
->value
) != TREE_BINFO
)
1900 known_csts
[i
] = val
->value
;
1901 known_binfos
[i
] = NULL_TREE
;
1902 emc
= estimate_move_cost (TREE_TYPE (val
->value
));
1904 else if (plats
->virt_call
)
1906 known_csts
[i
] = NULL_TREE
;
1907 known_binfos
[i
] = val
->value
;
1913 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_binfos
,
1914 known_aggs_ptrs
, &size
, &time
,
1916 time_benefit
= base_time
- time
1917 + devirtualization_time_bonus (node
, known_csts
, known_binfos
,
1919 + hint_time_bonus (hints
)
1920 + removable_params_cost
+ emc
;
1922 gcc_checking_assert (size
>=0);
1923 /* The inliner-heuristics based estimates may think that in certain
1924 contexts some functions do not have any size at all but we want
1925 all specializations to have at least a tiny cost, not least not to
1930 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1932 fprintf (dump_file
, " - estimates for value ");
1933 print_ipcp_constant_value (dump_file
, val
->value
);
1934 fprintf (dump_file
, " for parameter ");
1935 print_generic_expr (dump_file
, ipa_get_param (info
, i
), 0);
1936 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
1937 time_benefit
, size
);
1940 val
->local_time_benefit
= time_benefit
;
1941 val
->local_size_cost
= size
;
1943 known_binfos
[i
] = NULL_TREE
;
1944 known_csts
[i
] = NULL_TREE
;
1947 for (i
= 0; i
< count
; i
++)
1949 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1950 struct ipa_agg_jump_function
*ajf
;
1951 struct ipcp_agg_lattice
*aglat
;
1953 if (plats
->aggs_bottom
|| !plats
->aggs
)
1956 ajf
= &known_aggs
[i
];
1957 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
1959 struct ipcp_value
*val
;
1960 if (aglat
->bottom
|| !aglat
->values
1961 /* If the following is true, the one value is in known_aggs. */
1962 || (!plats
->aggs_contain_variable
1963 && ipa_lat_is_single_const (aglat
)))
1966 for (val
= aglat
->values
; val
; val
= val
->next
)
1968 int time
, size
, time_benefit
;
1969 struct ipa_agg_jf_item item
;
1972 item
.offset
= aglat
->offset
;
1973 item
.value
= val
->value
;
1974 vec_safe_push (ajf
->items
, item
);
1976 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_binfos
,
1977 known_aggs_ptrs
, &size
, &time
,
1979 time_benefit
= base_time
- time
1980 + devirtualization_time_bonus (node
, known_csts
, known_binfos
,
1982 + hint_time_bonus (hints
);
1983 gcc_checking_assert (size
>=0);
1987 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1989 fprintf (dump_file
, " - estimates for value ");
1990 print_ipcp_constant_value (dump_file
, val
->value
);
1991 fprintf (dump_file
, " for parameter ");
1992 print_generic_expr (dump_file
, ipa_get_param (info
, i
), 0);
1993 fprintf (dump_file
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
1994 "]: time_benefit: %i, size: %i\n",
1995 plats
->aggs_by_ref
? "ref " : "",
1996 aglat
->offset
, time_benefit
, size
);
1999 val
->local_time_benefit
= time_benefit
;
2000 val
->local_size_cost
= size
;
2006 for (i
= 0; i
< count
; i
++)
2007 vec_free (known_aggs
[i
].items
);
2009 known_csts
.release ();
2010 known_binfos
.release ();
2011 known_aggs
.release ();
2012 known_aggs_ptrs
.release ();
2016 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
2017 topological sort of values. */
2020 add_val_to_toposort (struct ipcp_value
*cur_val
)
2022 static int dfs_counter
= 0;
2023 static struct ipcp_value
*stack
;
2024 struct ipcp_value_source
*src
;
2030 cur_val
->dfs
= dfs_counter
;
2031 cur_val
->low_link
= dfs_counter
;
2033 cur_val
->topo_next
= stack
;
2035 cur_val
->on_stack
= true;
2037 for (src
= cur_val
->sources
; src
; src
= src
->next
)
2040 if (src
->val
->dfs
== 0)
2042 add_val_to_toposort (src
->val
);
2043 if (src
->val
->low_link
< cur_val
->low_link
)
2044 cur_val
->low_link
= src
->val
->low_link
;
2046 else if (src
->val
->on_stack
2047 && src
->val
->dfs
< cur_val
->low_link
)
2048 cur_val
->low_link
= src
->val
->dfs
;
2051 if (cur_val
->dfs
== cur_val
->low_link
)
2053 struct ipcp_value
*v
, *scc_list
= NULL
;
2058 stack
= v
->topo_next
;
2059 v
->on_stack
= false;
2061 v
->scc_next
= scc_list
;
2064 while (v
!= cur_val
);
2066 cur_val
->topo_next
= values_topo
;
2067 values_topo
= cur_val
;
2071 /* Add all values in lattices associated with NODE to the topological sort if
2072 they are not there yet. */
2075 add_all_node_vals_to_toposort (struct cgraph_node
*node
)
2077 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2078 int i
, count
= ipa_get_param_count (info
);
2080 for (i
= 0; i
< count
; i
++)
2082 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2083 struct ipcp_lattice
*lat
= &plats
->itself
;
2084 struct ipcp_agg_lattice
*aglat
;
2085 struct ipcp_value
*val
;
2088 for (val
= lat
->values
; val
; val
= val
->next
)
2089 add_val_to_toposort (val
);
2091 if (!plats
->aggs_bottom
)
2092 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2094 for (val
= aglat
->values
; val
; val
= val
->next
)
2095 add_val_to_toposort (val
);
2099 /* One pass of constants propagation along the call graph edges, from callers
2100 to callees (requires topological ordering in TOPO), iterate over strongly
2101 connected components. */
2104 propagate_constants_topo (struct topo_info
*topo
)
2108 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
2110 struct cgraph_node
*v
, *node
= topo
->order
[i
];
2111 struct ipa_dfs_info
*node_dfs_info
;
2113 if (!cgraph_function_with_gimple_body_p (node
))
2116 node_dfs_info
= (struct ipa_dfs_info
*) node
->symbol
.aux
;
2117 /* First, iteratively propagate within the strongly connected component
2118 until all lattices stabilize. */
2119 v
= node_dfs_info
->next_cycle
;
2122 push_node_to_stack (topo
, v
);
2123 v
= ((struct ipa_dfs_info
*) v
->symbol
.aux
)->next_cycle
;
2129 struct cgraph_edge
*cs
;
2131 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
2132 if (edge_within_scc (cs
)
2133 && propagate_constants_accross_call (cs
))
2134 push_node_to_stack (topo
, cs
->callee
);
2135 v
= pop_node_from_stack (topo
);
2138 /* Afterwards, propagate along edges leading out of the SCC, calculates
2139 the local effects of the discovered constants and all valid values to
2140 their topological sort. */
2144 struct cgraph_edge
*cs
;
2146 estimate_local_effects (v
);
2147 add_all_node_vals_to_toposort (v
);
2148 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
2149 if (!edge_within_scc (cs
))
2150 propagate_constants_accross_call (cs
);
2152 v
= ((struct ipa_dfs_info
*) v
->symbol
.aux
)->next_cycle
;
2158 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
2159 the bigger one if otherwise. */
2162 safe_add (int a
, int b
)
2164 if (a
> INT_MAX
/2 || b
> INT_MAX
/2)
2165 return a
> b
? a
: b
;
2171 /* Propagate the estimated effects of individual values along the topological
2172 from the dependent values to those they depend on. */
2175 propagate_effects (void)
2177 struct ipcp_value
*base
;
2179 for (base
= values_topo
; base
; base
= base
->topo_next
)
2181 struct ipcp_value_source
*src
;
2182 struct ipcp_value
*val
;
2183 int time
= 0, size
= 0;
2185 for (val
= base
; val
; val
= val
->scc_next
)
2187 time
= safe_add (time
,
2188 val
->local_time_benefit
+ val
->prop_time_benefit
);
2189 size
= safe_add (size
, val
->local_size_cost
+ val
->prop_size_cost
);
2192 for (val
= base
; val
; val
= val
->scc_next
)
2193 for (src
= val
->sources
; src
; src
= src
->next
)
2195 && cgraph_maybe_hot_edge_p (src
->cs
))
2197 src
->val
->prop_time_benefit
= safe_add (time
,
2198 src
->val
->prop_time_benefit
);
2199 src
->val
->prop_size_cost
= safe_add (size
,
2200 src
->val
->prop_size_cost
);
2206 /* Propagate constants, binfos and their effects from the summaries
2207 interprocedurally. */
2210 ipcp_propagate_stage (struct topo_info
*topo
)
2212 struct cgraph_node
*node
;
2215 fprintf (dump_file
, "\n Propagating constants:\n\n");
2218 ipa_update_after_lto_read ();
2221 FOR_EACH_DEFINED_FUNCTION (node
)
2223 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2225 determine_versionability (node
);
2226 if (cgraph_function_with_gimple_body_p (node
))
2228 info
->lattices
= XCNEWVEC (struct ipcp_param_lattices
,
2229 ipa_get_param_count (info
));
2230 initialize_node_lattices (node
);
2232 if (node
->count
> max_count
)
2233 max_count
= node
->count
;
2234 overall_size
+= inline_summary (node
)->self_size
;
2237 max_new_size
= overall_size
;
2238 if (max_new_size
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
2239 max_new_size
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
2240 max_new_size
+= max_new_size
* PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH
) / 100 + 1;
2243 fprintf (dump_file
, "\noverall_size: %li, max_new_size: %li\n",
2244 overall_size
, max_new_size
);
2246 propagate_constants_topo (topo
);
2247 #ifdef ENABLE_CHECKING
2248 ipcp_verify_propagated_values ();
2250 propagate_effects ();
2254 fprintf (dump_file
, "\nIPA lattices after all propagation:\n");
2255 print_all_lattices (dump_file
, (dump_flags
& TDF_DETAILS
), true);
2259 /* Discover newly direct outgoing edges from NODE which is a new clone with
2260 known KNOWN_VALS and make them direct. */
2263 ipcp_discover_new_direct_edges (struct cgraph_node
*node
,
2264 vec
<tree
> known_vals
,
2265 struct ipa_agg_replacement_value
*aggvals
)
2267 struct cgraph_edge
*ie
, *next_ie
;
2270 for (ie
= node
->indirect_calls
; ie
; ie
= next_ie
)
2274 next_ie
= ie
->next_callee
;
2275 target
= ipa_get_indirect_edge_target_1 (ie
, known_vals
, vNULL
, vNULL
,
2279 struct cgraph_edge
*cs
= ipa_make_edge_direct_to_target (ie
, target
);
2282 if (cs
&& !ie
->indirect_info
->agg_contents
2283 && !ie
->indirect_info
->polymorphic
)
2285 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2286 int param_index
= ie
->indirect_info
->param_index
;
2287 int c
= ipa_get_controlled_uses (info
, param_index
);
2288 if (c
!= IPA_UNDESCRIBED_USE
)
2290 struct ipa_ref
*to_del
;
2293 ipa_set_controlled_uses (info
, param_index
, c
);
2294 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2295 fprintf (dump_file
, " controlled uses count of param "
2296 "%i bumped down to %i\n", param_index
, c
);
2298 && (to_del
= ipa_find_reference ((symtab_node
) node
,
2299 (symtab_node
) cs
->callee
,
2302 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2303 fprintf (dump_file
, " and even removing its "
2304 "cloning-created reference\n");
2305 ipa_remove_reference (to_del
);
2311 /* Turning calls to direct calls will improve overall summary. */
2313 inline_update_overall_summary (node
);
2316 /* Vector of pointers which for linked lists of clones of an original crgaph
2319 static vec
<cgraph_edge_p
> next_edge_clone
;
2322 grow_next_edge_clone_vector (void)
2324 if (next_edge_clone
.length ()
2325 <= (unsigned) cgraph_edge_max_uid
)
2326 next_edge_clone
.safe_grow_cleared (cgraph_edge_max_uid
+ 1);
2329 /* Edge duplication hook to grow the appropriate linked list in
2333 ipcp_edge_duplication_hook (struct cgraph_edge
*src
, struct cgraph_edge
*dst
,
2334 __attribute__((unused
)) void *data
)
2336 grow_next_edge_clone_vector ();
2337 next_edge_clone
[dst
->uid
] = next_edge_clone
[src
->uid
];
2338 next_edge_clone
[src
->uid
] = dst
;
2341 /* See if NODE is a clone with a known aggregate value at a given OFFSET of a
2342 parameter with the given INDEX. */
2345 get_clone_agg_value (struct cgraph_node
*node
, HOST_WIDEST_INT offset
,
2348 struct ipa_agg_replacement_value
*aggval
;
2350 aggval
= ipa_get_agg_replacements_for_node (node
);
2353 if (aggval
->offset
== offset
2354 && aggval
->index
== index
)
2355 return aggval
->value
;
2356 aggval
= aggval
->next
;
2361 /* Return true if edge CS does bring about the value described by SRC. */
2364 cgraph_edge_brings_value_p (struct cgraph_edge
*cs
,
2365 struct ipcp_value_source
*src
)
2367 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2368 struct ipa_node_params
*dst_info
= IPA_NODE_REF (cs
->callee
);
2370 if ((dst_info
->ipcp_orig_node
&& !dst_info
->is_all_contexts_clone
)
2371 || caller_info
->node_dead
)
2376 if (caller_info
->ipcp_orig_node
)
2379 if (src
->offset
== -1)
2380 t
= caller_info
->known_vals
[src
->index
];
2382 t
= get_clone_agg_value (cs
->caller
, src
->offset
, src
->index
);
2383 return (t
!= NULL_TREE
2384 && values_equal_for_ipcp_p (src
->val
->value
, t
));
2388 struct ipcp_agg_lattice
*aglat
;
2389 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
2391 if (src
->offset
== -1)
2392 return (ipa_lat_is_single_const (&plats
->itself
)
2393 && values_equal_for_ipcp_p (src
->val
->value
,
2394 plats
->itself
.values
->value
));
2397 if (plats
->aggs_bottom
|| plats
->aggs_contain_variable
)
2399 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2400 if (aglat
->offset
== src
->offset
)
2401 return (ipa_lat_is_single_const (aglat
)
2402 && values_equal_for_ipcp_p (src
->val
->value
,
2403 aglat
->values
->value
));
2409 /* Get the next clone in the linked list of clones of an edge. */
2411 static inline struct cgraph_edge
*
2412 get_next_cgraph_edge_clone (struct cgraph_edge
*cs
)
2414 return next_edge_clone
[cs
->uid
];
2417 /* Given VAL, iterate over all its sources and if they still hold, add their
2418 edge frequency and their number into *FREQUENCY and *CALLER_COUNT
2422 get_info_about_necessary_edges (struct ipcp_value
*val
, int *freq_sum
,
2423 gcov_type
*count_sum
, int *caller_count
)
2425 struct ipcp_value_source
*src
;
2426 int freq
= 0, count
= 0;
2430 for (src
= val
->sources
; src
; src
= src
->next
)
2432 struct cgraph_edge
*cs
= src
->cs
;
2435 if (cgraph_edge_brings_value_p (cs
, src
))
2438 freq
+= cs
->frequency
;
2440 hot
|= cgraph_maybe_hot_edge_p (cs
);
2442 cs
= get_next_cgraph_edge_clone (cs
);
2448 *caller_count
= count
;
2452 /* Return a vector of incoming edges that do bring value VAL. It is assumed
2453 their number is known and equal to CALLER_COUNT. */
2455 static vec
<cgraph_edge_p
>
2456 gather_edges_for_value (struct ipcp_value
*val
, int caller_count
)
2458 struct ipcp_value_source
*src
;
2459 vec
<cgraph_edge_p
> ret
;
2461 ret
.create (caller_count
);
2462 for (src
= val
->sources
; src
; src
= src
->next
)
2464 struct cgraph_edge
*cs
= src
->cs
;
2467 if (cgraph_edge_brings_value_p (cs
, src
))
2468 ret
.quick_push (cs
);
2469 cs
= get_next_cgraph_edge_clone (cs
);
2476 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
2477 Return it or NULL if for some reason it cannot be created. */
2479 static struct ipa_replace_map
*
2480 get_replacement_map (tree value
, tree parm
)
2482 tree req_type
= TREE_TYPE (parm
);
2483 struct ipa_replace_map
*replace_map
;
2485 if (!useless_type_conversion_p (req_type
, TREE_TYPE (value
)))
2487 if (fold_convertible_p (req_type
, value
))
2488 value
= fold_build1 (NOP_EXPR
, req_type
, value
);
2489 else if (TYPE_SIZE (req_type
) == TYPE_SIZE (TREE_TYPE (value
)))
2490 value
= fold_build1 (VIEW_CONVERT_EXPR
, req_type
, value
);
2495 fprintf (dump_file
, " const ");
2496 print_generic_expr (dump_file
, value
, 0);
2497 fprintf (dump_file
, " can't be converted to param ");
2498 print_generic_expr (dump_file
, parm
, 0);
2499 fprintf (dump_file
, "\n");
2505 replace_map
= ggc_alloc_ipa_replace_map ();
2508 fprintf (dump_file
, " replacing param ");
2509 print_generic_expr (dump_file
, parm
, 0);
2510 fprintf (dump_file
, " with const ");
2511 print_generic_expr (dump_file
, value
, 0);
2512 fprintf (dump_file
, "\n");
2514 replace_map
->old_tree
= parm
;
2515 replace_map
->new_tree
= value
;
2516 replace_map
->replace_p
= true;
2517 replace_map
->ref_p
= false;
2522 /* Dump new profiling counts */
2525 dump_profile_updates (struct cgraph_node
*orig_node
,
2526 struct cgraph_node
*new_node
)
2528 struct cgraph_edge
*cs
;
2530 fprintf (dump_file
, " setting count of the specialized node to "
2531 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) new_node
->count
);
2532 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
2533 fprintf (dump_file
, " edge to %s has count "
2534 HOST_WIDE_INT_PRINT_DEC
"\n",
2535 cgraph_node_name (cs
->callee
), (HOST_WIDE_INT
) cs
->count
);
2537 fprintf (dump_file
, " setting count of the original node to "
2538 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) orig_node
->count
);
2539 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
2540 fprintf (dump_file
, " edge to %s is left with "
2541 HOST_WIDE_INT_PRINT_DEC
"\n",
2542 cgraph_node_name (cs
->callee
), (HOST_WIDE_INT
) cs
->count
);
2545 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
2546 their profile information to reflect this. */
2549 update_profiling_info (struct cgraph_node
*orig_node
,
2550 struct cgraph_node
*new_node
)
2552 struct cgraph_edge
*cs
;
2553 struct caller_statistics stats
;
2554 gcov_type new_sum
, orig_sum
;
2555 gcov_type remainder
, orig_node_count
= orig_node
->count
;
2557 if (orig_node_count
== 0)
2560 init_caller_stats (&stats
);
2561 cgraph_for_node_and_aliases (orig_node
, gather_caller_stats
, &stats
, false);
2562 orig_sum
= stats
.count_sum
;
2563 init_caller_stats (&stats
);
2564 cgraph_for_node_and_aliases (new_node
, gather_caller_stats
, &stats
, false);
2565 new_sum
= stats
.count_sum
;
2567 if (orig_node_count
< orig_sum
+ new_sum
)
2570 fprintf (dump_file
, " Problem: node %s/%i has too low count "
2571 HOST_WIDE_INT_PRINT_DEC
" while the sum of incoming "
2572 "counts is " HOST_WIDE_INT_PRINT_DEC
"\n",
2573 cgraph_node_name (orig_node
), orig_node
->uid
,
2574 (HOST_WIDE_INT
) orig_node_count
,
2575 (HOST_WIDE_INT
) (orig_sum
+ new_sum
));
2577 orig_node_count
= (orig_sum
+ new_sum
) * 12 / 10;
2579 fprintf (dump_file
, " proceeding by pretending it was "
2580 HOST_WIDE_INT_PRINT_DEC
"\n",
2581 (HOST_WIDE_INT
) orig_node_count
);
2584 new_node
->count
= new_sum
;
2585 remainder
= orig_node_count
- new_sum
;
2586 orig_node
->count
= remainder
;
2588 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
2590 cs
->count
= apply_probability (cs
->count
,
2591 GCOV_COMPUTE_SCALE (new_sum
,
2596 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
2597 cs
->count
= apply_probability (cs
->count
,
2598 GCOV_COMPUTE_SCALE (remainder
,
2602 dump_profile_updates (orig_node
, new_node
);
2605 /* Update the respective profile of specialized NEW_NODE and the original
2606 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
2607 have been redirected to the specialized version. */
2610 update_specialized_profile (struct cgraph_node
*new_node
,
2611 struct cgraph_node
*orig_node
,
2612 gcov_type redirected_sum
)
2614 struct cgraph_edge
*cs
;
2615 gcov_type new_node_count
, orig_node_count
= orig_node
->count
;
2618 fprintf (dump_file
, " the sum of counts of redirected edges is "
2619 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) redirected_sum
);
2620 if (orig_node_count
== 0)
2623 gcc_assert (orig_node_count
>= redirected_sum
);
2625 new_node_count
= new_node
->count
;
2626 new_node
->count
+= redirected_sum
;
2627 orig_node
->count
-= redirected_sum
;
2629 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
2631 cs
->count
+= apply_probability (cs
->count
,
2632 GCOV_COMPUTE_SCALE (redirected_sum
,
2637 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
2639 gcov_type dec
= apply_probability (cs
->count
,
2640 GCOV_COMPUTE_SCALE (redirected_sum
,
2642 if (dec
< cs
->count
)
2649 dump_profile_updates (orig_node
, new_node
);
2652 /* Create a specialized version of NODE with known constants and types of
2653 parameters in KNOWN_VALS and redirect all edges in CALLERS to it. */
2655 static struct cgraph_node
*
2656 create_specialized_node (struct cgraph_node
*node
,
2657 vec
<tree
> known_vals
,
2658 struct ipa_agg_replacement_value
*aggvals
,
2659 vec
<cgraph_edge_p
> callers
)
2661 struct ipa_node_params
*new_info
, *info
= IPA_NODE_REF (node
);
2662 vec
<ipa_replace_map_p
, va_gc
> *replace_trees
= NULL
;
2663 struct cgraph_node
*new_node
;
2664 int i
, count
= ipa_get_param_count (info
);
2665 bitmap args_to_skip
;
2667 gcc_assert (!info
->ipcp_orig_node
);
2669 if (node
->local
.can_change_signature
)
2671 args_to_skip
= BITMAP_GGC_ALLOC ();
2672 for (i
= 0; i
< count
; i
++)
2674 tree t
= known_vals
[i
];
2676 if ((t
&& TREE_CODE (t
) != TREE_BINFO
)
2677 || !ipa_is_param_used (info
, i
))
2678 bitmap_set_bit (args_to_skip
, i
);
2683 args_to_skip
= NULL
;
2684 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2685 fprintf (dump_file
, " cannot change function signature\n");
2688 for (i
= 0; i
< count
; i
++)
2690 tree t
= known_vals
[i
];
2691 if (t
&& TREE_CODE (t
) != TREE_BINFO
)
2693 struct ipa_replace_map
*replace_map
;
2695 replace_map
= get_replacement_map (t
, ipa_get_param (info
, i
));
2697 vec_safe_push (replace_trees
, replace_map
);
2701 new_node
= cgraph_create_virtual_clone (node
, callers
, replace_trees
,
2702 args_to_skip
, "constprop");
2703 ipa_set_node_agg_value_chain (new_node
, aggvals
);
2704 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2706 fprintf (dump_file
, " the new node is %s/%i.\n",
2707 cgraph_node_name (new_node
), new_node
->uid
);
2709 ipa_dump_agg_replacement_values (dump_file
, aggvals
);
2711 gcc_checking_assert (ipa_node_params_vector
.exists ()
2712 && (ipa_node_params_vector
.length ()
2713 > (unsigned) cgraph_max_uid
));
2714 update_profiling_info (node
, new_node
);
2715 new_info
= IPA_NODE_REF (new_node
);
2716 new_info
->ipcp_orig_node
= node
;
2717 new_info
->known_vals
= known_vals
;
2719 ipcp_discover_new_direct_edges (new_node
, known_vals
, aggvals
);
2725 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
2726 KNOWN_VALS with constants and types that are also known for all of the
2730 find_more_scalar_values_for_callers_subset (struct cgraph_node
*node
,
2731 vec
<tree
> known_vals
,
2732 vec
<cgraph_edge_p
> callers
)
2734 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2735 int i
, count
= ipa_get_param_count (info
);
2737 for (i
= 0; i
< count
; i
++)
2739 struct cgraph_edge
*cs
;
2740 tree newval
= NULL_TREE
;
2743 if (ipa_get_scalar_lat (info
, i
)->bottom
|| known_vals
[i
])
2746 FOR_EACH_VEC_ELT (callers
, j
, cs
)
2748 struct ipa_jump_func
*jump_func
;
2751 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
)))
2756 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
2757 t
= ipa_value_from_jfunc (IPA_NODE_REF (cs
->caller
), jump_func
);
2760 && !values_equal_for_ipcp_p (t
, newval
)))
2771 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2773 fprintf (dump_file
, " adding an extra known scalar value ");
2774 print_ipcp_constant_value (dump_file
, newval
);
2775 fprintf (dump_file
, " for parameter ");
2776 print_generic_expr (dump_file
, ipa_get_param (info
, i
), 0);
2777 fprintf (dump_file
, "\n");
2780 known_vals
[i
] = newval
;
2785 /* Go through PLATS and create a vector of values consisting of values and
2786 offsets (minus OFFSET) of lattices that contain only a single value. */
2788 static vec
<ipa_agg_jf_item_t
>
2789 copy_plats_to_inter (struct ipcp_param_lattices
*plats
, HOST_WIDE_INT offset
)
2791 vec
<ipa_agg_jf_item_t
> res
= vNULL
;
2793 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
2796 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2797 if (ipa_lat_is_single_const (aglat
))
2799 struct ipa_agg_jf_item ti
;
2800 ti
.offset
= aglat
->offset
- offset
;
2801 ti
.value
= aglat
->values
->value
;
2807 /* Intersect all values in INTER with single value lattices in PLATS (while
2808 subtracting OFFSET). */
2811 intersect_with_plats (struct ipcp_param_lattices
*plats
,
2812 vec
<ipa_agg_jf_item_t
> *inter
,
2813 HOST_WIDE_INT offset
)
2815 struct ipcp_agg_lattice
*aglat
;
2816 struct ipa_agg_jf_item
*item
;
2819 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
2825 aglat
= plats
->aggs
;
2826 FOR_EACH_VEC_ELT (*inter
, k
, item
)
2833 if (aglat
->offset
- offset
> item
->offset
)
2835 if (aglat
->offset
- offset
== item
->offset
)
2837 gcc_checking_assert (item
->value
);
2838 if (values_equal_for_ipcp_p (item
->value
, aglat
->values
->value
))
2842 aglat
= aglat
->next
;
2845 item
->value
= NULL_TREE
;
2849 /* Copy agggregate replacement values of NODE (which is an IPA-CP clone) to the
2850 vector result while subtracting OFFSET from the individual value offsets. */
2852 static vec
<ipa_agg_jf_item_t
>
2853 agg_replacements_to_vector (struct cgraph_node
*node
, int index
,
2854 HOST_WIDE_INT offset
)
2856 struct ipa_agg_replacement_value
*av
;
2857 vec
<ipa_agg_jf_item_t
> res
= vNULL
;
2859 for (av
= ipa_get_agg_replacements_for_node (node
); av
; av
= av
->next
)
2860 if (av
->index
== index
2861 && (av
->offset
- offset
) >= 0)
2863 struct ipa_agg_jf_item item
;
2864 gcc_checking_assert (av
->value
);
2865 item
.offset
= av
->offset
- offset
;
2866 item
.value
= av
->value
;
2867 res
.safe_push (item
);
2873 /* Intersect all values in INTER with those that we have already scheduled to
2874 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
2875 (while subtracting OFFSET). */
2878 intersect_with_agg_replacements (struct cgraph_node
*node
, int index
,
2879 vec
<ipa_agg_jf_item_t
> *inter
,
2880 HOST_WIDE_INT offset
)
2882 struct ipa_agg_replacement_value
*srcvals
;
2883 struct ipa_agg_jf_item
*item
;
2886 srcvals
= ipa_get_agg_replacements_for_node (node
);
2893 FOR_EACH_VEC_ELT (*inter
, i
, item
)
2895 struct ipa_agg_replacement_value
*av
;
2899 for (av
= srcvals
; av
; av
= av
->next
)
2901 gcc_checking_assert (av
->value
);
2902 if (av
->index
== index
2903 && av
->offset
- offset
== item
->offset
)
2905 if (values_equal_for_ipcp_p (item
->value
, av
->value
))
2911 item
->value
= NULL_TREE
;
2915 /* Intersect values in INTER with aggregate values that come along edge CS to
2916 parameter number INDEX and return it. If INTER does not actually exist yet,
2917 copy all incoming values to it. If we determine we ended up with no values
2918 whatsoever, return a released vector. */
2920 static vec
<ipa_agg_jf_item_t
>
2921 intersect_aggregates_with_edge (struct cgraph_edge
*cs
, int index
,
2922 vec
<ipa_agg_jf_item_t
> inter
)
2924 struct ipa_jump_func
*jfunc
;
2925 jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), index
);
2926 if (jfunc
->type
== IPA_JF_PASS_THROUGH
2927 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
2929 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2930 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
2932 if (caller_info
->ipcp_orig_node
)
2934 struct cgraph_node
*orig_node
= caller_info
->ipcp_orig_node
;
2935 struct ipcp_param_lattices
*orig_plats
;
2936 orig_plats
= ipa_get_parm_lattices (IPA_NODE_REF (orig_node
),
2938 if (agg_pass_through_permissible_p (orig_plats
, jfunc
))
2940 if (!inter
.exists ())
2941 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, 0);
2943 intersect_with_agg_replacements (cs
->caller
, src_idx
,
2949 struct ipcp_param_lattices
*src_plats
;
2950 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2951 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
2953 /* Currently we do not produce clobber aggregate jump
2954 functions, adjust when we do. */
2955 gcc_checking_assert (!jfunc
->agg
.items
);
2956 if (!inter
.exists ())
2957 inter
= copy_plats_to_inter (src_plats
, 0);
2959 intersect_with_plats (src_plats
, &inter
, 0);
2963 else if (jfunc
->type
== IPA_JF_ANCESTOR
2964 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
2966 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2967 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
2968 struct ipcp_param_lattices
*src_plats
;
2969 HOST_WIDE_INT delta
= ipa_get_jf_ancestor_offset (jfunc
);
2971 if (caller_info
->ipcp_orig_node
)
2973 if (!inter
.exists ())
2974 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, delta
);
2976 intersect_with_agg_replacements (cs
->caller
, src_idx
, &inter
,
2981 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);;
2982 /* Currently we do not produce clobber aggregate jump
2983 functions, adjust when we do. */
2984 gcc_checking_assert (!src_plats
->aggs
|| !jfunc
->agg
.items
);
2985 if (!inter
.exists ())
2986 inter
= copy_plats_to_inter (src_plats
, delta
);
2988 intersect_with_plats (src_plats
, &inter
, delta
);
2991 else if (jfunc
->agg
.items
)
2993 struct ipa_agg_jf_item
*item
;
2996 if (!inter
.exists ())
2997 for (unsigned i
= 0; i
< jfunc
->agg
.items
->length (); i
++)
2998 inter
.safe_push ((*jfunc
->agg
.items
)[i
]);
3000 FOR_EACH_VEC_ELT (inter
, k
, item
)
3003 bool found
= false;;
3008 while ((unsigned) l
< jfunc
->agg
.items
->length ())
3010 struct ipa_agg_jf_item
*ti
;
3011 ti
= &(*jfunc
->agg
.items
)[l
];
3012 if (ti
->offset
> item
->offset
)
3014 if (ti
->offset
== item
->offset
)
3016 gcc_checking_assert (ti
->value
);
3017 if (values_equal_for_ipcp_p (item
->value
,
3031 return vec
<ipa_agg_jf_item_t
>();
3036 /* Look at edges in CALLERS and collect all known aggregate values that arrive
3037 from all of them. */
3039 static struct ipa_agg_replacement_value
*
3040 find_aggregate_values_for_callers_subset (struct cgraph_node
*node
,
3041 vec
<cgraph_edge_p
> callers
)
3043 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
3044 struct ipa_agg_replacement_value
*res
= NULL
;
3045 struct cgraph_edge
*cs
;
3046 int i
, j
, count
= ipa_get_param_count (dest_info
);
3048 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3050 int c
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
3055 for (i
= 0; i
< count
; i
++)
3057 struct cgraph_edge
*cs
;
3058 vec
<ipa_agg_jf_item_t
> inter
= vNULL
;
3059 struct ipa_agg_jf_item
*item
;
3060 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (dest_info
, i
);
3063 /* Among other things, the following check should deal with all by_ref
3065 if (plats
->aggs_bottom
)
3068 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3070 inter
= intersect_aggregates_with_edge (cs
, i
, inter
);
3072 if (!inter
.exists ())
3076 FOR_EACH_VEC_ELT (inter
, j
, item
)
3078 struct ipa_agg_replacement_value
*v
;
3083 v
= ggc_alloc_ipa_agg_replacement_value ();
3085 v
->offset
= item
->offset
;
3086 v
->value
= item
->value
;
3087 v
->by_ref
= plats
->aggs_by_ref
;
3093 if (inter
.exists ())
3099 /* Turn KNOWN_AGGS into a list of aggreate replacement values. */
3101 static struct ipa_agg_replacement_value
*
3102 known_aggs_to_agg_replacement_list (vec
<ipa_agg_jump_function_t
> known_aggs
)
3104 struct ipa_agg_replacement_value
*res
= NULL
;
3105 struct ipa_agg_jump_function
*aggjf
;
3106 struct ipa_agg_jf_item
*item
;
3109 FOR_EACH_VEC_ELT (known_aggs
, i
, aggjf
)
3110 FOR_EACH_VEC_SAFE_ELT (aggjf
->items
, j
, item
)
3112 struct ipa_agg_replacement_value
*v
;
3113 v
= ggc_alloc_ipa_agg_replacement_value ();
3115 v
->offset
= item
->offset
;
3116 v
->value
= item
->value
;
3117 v
->by_ref
= aggjf
->by_ref
;
3124 /* Determine whether CS also brings all scalar values that the NODE is
3128 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge
*cs
,
3129 struct cgraph_node
*node
)
3131 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
3132 int count
= ipa_get_param_count (dest_info
);
3133 struct ipa_node_params
*caller_info
;
3134 struct ipa_edge_args
*args
;
3137 caller_info
= IPA_NODE_REF (cs
->caller
);
3138 args
= IPA_EDGE_REF (cs
);
3139 for (i
= 0; i
< count
; i
++)
3141 struct ipa_jump_func
*jump_func
;
3144 val
= dest_info
->known_vals
[i
];
3148 if (i
>= ipa_get_cs_argument_count (args
))
3150 jump_func
= ipa_get_ith_jump_func (args
, i
);
3151 t
= ipa_value_from_jfunc (caller_info
, jump_func
);
3152 if (!t
|| !values_equal_for_ipcp_p (val
, t
))
3158 /* Determine whether CS also brings all aggregate values that NODE is
3161 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge
*cs
,
3162 struct cgraph_node
*node
)
3164 struct ipa_node_params
*orig_caller_info
= IPA_NODE_REF (cs
->caller
);
3165 struct ipa_agg_replacement_value
*aggval
;
3168 aggval
= ipa_get_agg_replacements_for_node (node
);
3172 count
= ipa_get_param_count (IPA_NODE_REF (node
));
3173 ec
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
3175 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
3176 if (aggval
->index
>= ec
)
3179 if (orig_caller_info
->ipcp_orig_node
)
3180 orig_caller_info
= IPA_NODE_REF (orig_caller_info
->ipcp_orig_node
);
3182 for (i
= 0; i
< count
; i
++)
3184 static vec
<ipa_agg_jf_item_t
> values
= vec
<ipa_agg_jf_item_t
>();
3185 struct ipcp_param_lattices
*plats
;
3186 bool interesting
= false;
3187 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
3188 if (aggval
->index
== i
)
3196 plats
= ipa_get_parm_lattices (orig_caller_info
, aggval
->index
);
3197 if (plats
->aggs_bottom
)
3200 values
= intersect_aggregates_with_edge (cs
, i
, values
);
3201 if (!values
.exists())
3204 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
3205 if (aggval
->index
== i
)
3207 struct ipa_agg_jf_item
*item
;
3210 FOR_EACH_VEC_ELT (values
, j
, item
)
3212 && item
->offset
== av
->offset
3213 && values_equal_for_ipcp_p (item
->value
, av
->value
))
3225 /* Given an original NODE and a VAL for which we have already created a
3226 specialized clone, look whether there are incoming edges that still lead
3227 into the old node but now also bring the requested value and also conform to
3228 all other criteria such that they can be redirected the the special node.
3229 This function can therefore redirect the final edge in a SCC. */
3232 perhaps_add_new_callers (struct cgraph_node
*node
, struct ipcp_value
*val
)
3234 struct ipcp_value_source
*src
;
3235 gcov_type redirected_sum
= 0;
3237 for (src
= val
->sources
; src
; src
= src
->next
)
3239 struct cgraph_edge
*cs
= src
->cs
;
3242 enum availability availability
;
3243 struct cgraph_node
*dst
= cgraph_function_node (cs
->callee
,
3245 if ((dst
== node
|| IPA_NODE_REF (dst
)->is_all_contexts_clone
)
3246 && availability
> AVAIL_OVERWRITABLE
3247 && cgraph_edge_brings_value_p (cs
, src
))
3249 if (cgraph_edge_brings_all_scalars_for_node (cs
, val
->spec_node
)
3250 && cgraph_edge_brings_all_agg_vals_for_node (cs
,
3254 fprintf (dump_file
, " - adding an extra caller %s/%i"
3256 xstrdup (cgraph_node_name (cs
->caller
)),
3258 xstrdup (cgraph_node_name (val
->spec_node
)),
3259 val
->spec_node
->uid
);
3261 cgraph_redirect_edge_callee (cs
, val
->spec_node
);
3262 redirected_sum
+= cs
->count
;
3265 cs
= get_next_cgraph_edge_clone (cs
);
3270 update_specialized_profile (val
->spec_node
, node
, redirected_sum
);
3274 /* Copy KNOWN_BINFOS to KNOWN_VALS. */
3277 move_binfos_to_values (vec
<tree
> known_vals
,
3278 vec
<tree
> known_binfos
)
3283 for (i
= 0; known_binfos
.iterate (i
, &t
); i
++)
3288 /* Return true if there is a replacement equivalent to VALUE, INDEX and OFFSET
3289 among those in the AGGVALS list. */
3292 ipcp_val_in_agg_replacements_p (struct ipa_agg_replacement_value
*aggvals
,
3293 int index
, HOST_WIDE_INT offset
, tree value
)
3297 if (aggvals
->index
== index
3298 && aggvals
->offset
== offset
3299 && values_equal_for_ipcp_p (aggvals
->value
, value
))
3301 aggvals
= aggvals
->next
;
3306 /* Decide wheter to create a special version of NODE for value VAL of parameter
3307 at the given INDEX. If OFFSET is -1, the value is for the parameter itself,
3308 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS,
3309 KNOWN_BINFOS and KNOWN_AGGS describe the other already known values. */
3312 decide_about_value (struct cgraph_node
*node
, int index
, HOST_WIDE_INT offset
,
3313 struct ipcp_value
*val
, vec
<tree
> known_csts
,
3314 vec
<tree
> known_binfos
)
3316 struct ipa_agg_replacement_value
*aggvals
;
3317 int freq_sum
, caller_count
;
3318 gcov_type count_sum
;
3319 vec
<cgraph_edge_p
> callers
;
3324 perhaps_add_new_callers (node
, val
);
3327 else if (val
->local_size_cost
+ overall_size
> max_new_size
)
3329 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3330 fprintf (dump_file
, " Ignoring candidate value because "
3331 "max_new_size would be reached with %li.\n",
3332 val
->local_size_cost
+ overall_size
);
3335 else if (!get_info_about_necessary_edges (val
, &freq_sum
, &count_sum
,
3339 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3341 fprintf (dump_file
, " - considering value ");
3342 print_ipcp_constant_value (dump_file
, val
->value
);
3343 fprintf (dump_file
, " for parameter ");
3344 print_generic_expr (dump_file
, ipa_get_param (IPA_NODE_REF (node
),
3347 fprintf (dump_file
, ", offset: " HOST_WIDE_INT_PRINT_DEC
, offset
);
3348 fprintf (dump_file
, " (caller_count: %i)\n", caller_count
);
3351 if (!good_cloning_opportunity_p (node
, val
->local_time_benefit
,
3352 freq_sum
, count_sum
,
3353 val
->local_size_cost
)
3354 && !good_cloning_opportunity_p (node
,
3355 val
->local_time_benefit
3356 + val
->prop_time_benefit
,
3357 freq_sum
, count_sum
,
3358 val
->local_size_cost
3359 + val
->prop_size_cost
))
3363 fprintf (dump_file
, " Creating a specialized node of %s/%i.\n",
3364 cgraph_node_name (node
), node
->uid
);
3366 callers
= gather_edges_for_value (val
, caller_count
);
3367 kv
= known_csts
.copy ();
3368 move_binfos_to_values (kv
, known_binfos
);
3370 kv
[index
] = val
->value
;
3371 find_more_scalar_values_for_callers_subset (node
, kv
, callers
);
3372 aggvals
= find_aggregate_values_for_callers_subset (node
, callers
);
3373 gcc_checking_assert (offset
== -1
3374 || ipcp_val_in_agg_replacements_p (aggvals
, index
,
3375 offset
, val
->value
));
3376 val
->spec_node
= create_specialized_node (node
, kv
, aggvals
, callers
);
3377 overall_size
+= val
->local_size_cost
;
3379 /* TODO: If for some lattice there is only one other known value
3380 left, make a special node for it too. */
3385 /* Decide whether and what specialized clones of NODE should be created. */
3388 decide_whether_version_node (struct cgraph_node
*node
)
3390 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3391 int i
, count
= ipa_get_param_count (info
);
3392 vec
<tree
> known_csts
, known_binfos
;
3393 vec
<ipa_agg_jump_function_t
> known_aggs
= vNULL
;
3399 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3400 fprintf (dump_file
, "\nEvaluating opportunities for %s/%i.\n",
3401 cgraph_node_name (node
), node
->uid
);
3403 gather_context_independent_values (info
, &known_csts
, &known_binfos
,
3404 info
->do_clone_for_all_contexts
? &known_aggs
3407 for (i
= 0; i
< count
;i
++)
3409 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3410 struct ipcp_lattice
*lat
= &plats
->itself
;
3411 struct ipcp_value
*val
;
3415 && !known_binfos
[i
])
3416 for (val
= lat
->values
; val
; val
= val
->next
)
3417 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
3420 if (!plats
->aggs_bottom
)
3422 struct ipcp_agg_lattice
*aglat
;
3423 struct ipcp_value
*val
;
3424 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3425 if (!aglat
->bottom
&& aglat
->values
3426 /* If the following is false, the one value is in
3428 && (plats
->aggs_contain_variable
3429 || !ipa_lat_is_single_const (aglat
)))
3430 for (val
= aglat
->values
; val
; val
= val
->next
)
3431 ret
|= decide_about_value (node
, i
, aglat
->offset
, val
,
3432 known_csts
, known_binfos
);
3434 info
= IPA_NODE_REF (node
);
3437 if (info
->do_clone_for_all_contexts
)
3439 struct cgraph_node
*clone
;
3440 vec
<cgraph_edge_p
> callers
;
3443 fprintf (dump_file
, " - Creating a specialized node of %s/%i "
3444 "for all known contexts.\n", cgraph_node_name (node
),
3447 callers
= collect_callers_of_node (node
);
3448 move_binfos_to_values (known_csts
, known_binfos
);
3449 clone
= create_specialized_node (node
, known_csts
,
3450 known_aggs_to_agg_replacement_list (known_aggs
),
3452 info
= IPA_NODE_REF (node
);
3453 info
->do_clone_for_all_contexts
= false;
3454 IPA_NODE_REF (clone
)->is_all_contexts_clone
= true;
3455 for (i
= 0; i
< count
; i
++)
3456 vec_free (known_aggs
[i
].items
);
3457 known_aggs
.release ();
3461 known_csts
.release ();
3463 known_binfos
.release ();
3467 /* Transitively mark all callees of NODE within the same SCC as not dead. */
3470 spread_undeadness (struct cgraph_node
*node
)
3472 struct cgraph_edge
*cs
;
3474 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
3475 if (edge_within_scc (cs
))
3477 struct cgraph_node
*callee
;
3478 struct ipa_node_params
*info
;
3480 callee
= cgraph_function_node (cs
->callee
, NULL
);
3481 info
= IPA_NODE_REF (callee
);
3483 if (info
->node_dead
)
3485 info
->node_dead
= 0;
3486 spread_undeadness (callee
);
3491 /* Return true if NODE has a caller from outside of its SCC that is not
3492 dead. Worker callback for cgraph_for_node_and_aliases. */
3495 has_undead_caller_from_outside_scc_p (struct cgraph_node
*node
,
3496 void *data ATTRIBUTE_UNUSED
)
3498 struct cgraph_edge
*cs
;
3500 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
3501 if (cs
->caller
->thunk
.thunk_p
3502 && cgraph_for_node_and_aliases (cs
->caller
,
3503 has_undead_caller_from_outside_scc_p
,
3506 else if (!edge_within_scc (cs
)
3507 && !IPA_NODE_REF (cs
->caller
)->node_dead
)
3513 /* Identify nodes within the same SCC as NODE which are no longer needed
3514 because of new clones and will be removed as unreachable. */
3517 identify_dead_nodes (struct cgraph_node
*node
)
3519 struct cgraph_node
*v
;
3520 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->symbol
.aux
)->next_cycle
)
3521 if (cgraph_will_be_removed_from_program_if_no_direct_calls (v
)
3522 && !cgraph_for_node_and_aliases (v
,
3523 has_undead_caller_from_outside_scc_p
,
3525 IPA_NODE_REF (v
)->node_dead
= 1;
3527 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->symbol
.aux
)->next_cycle
)
3528 if (!IPA_NODE_REF (v
)->node_dead
)
3529 spread_undeadness (v
);
3531 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3533 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->symbol
.aux
)->next_cycle
)
3534 if (IPA_NODE_REF (v
)->node_dead
)
3535 fprintf (dump_file
, " Marking node as dead: %s/%i.\n",
3536 cgraph_node_name (v
), v
->uid
);
3540 /* The decision stage. Iterate over the topological order of call graph nodes
3541 TOPO and make specialized clones if deemed beneficial. */
3544 ipcp_decision_stage (struct topo_info
*topo
)
3549 fprintf (dump_file
, "\nIPA decision stage:\n\n");
3551 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
3553 struct cgraph_node
*node
= topo
->order
[i
];
3554 bool change
= false, iterate
= true;
3558 struct cgraph_node
*v
;
3560 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->symbol
.aux
)->next_cycle
)
3561 if (cgraph_function_with_gimple_body_p (v
)
3562 && ipcp_versionable_function_p (v
))
3563 iterate
|= decide_whether_version_node (v
);
3568 identify_dead_nodes (node
);
3572 /* The IPCP driver. */
3577 struct cgraph_2edge_hook_list
*edge_duplication_hook_holder
;
3578 struct topo_info topo
;
3580 ipa_check_create_node_params ();
3581 ipa_check_create_edge_args ();
3582 grow_next_edge_clone_vector ();
3583 edge_duplication_hook_holder
=
3584 cgraph_add_edge_duplication_hook (&ipcp_edge_duplication_hook
, NULL
);
3585 ipcp_values_pool
= create_alloc_pool ("IPA-CP values",
3586 sizeof (struct ipcp_value
), 32);
3587 ipcp_sources_pool
= create_alloc_pool ("IPA-CP value sources",
3588 sizeof (struct ipcp_value_source
), 64);
3589 ipcp_agg_lattice_pool
= create_alloc_pool ("IPA_CP aggregate lattices",
3590 sizeof (struct ipcp_agg_lattice
),
3594 fprintf (dump_file
, "\nIPA structures before propagation:\n");
3595 if (dump_flags
& TDF_DETAILS
)
3596 ipa_print_all_params (dump_file
);
3597 ipa_print_all_jump_functions (dump_file
);
3600 /* Topological sort. */
3601 build_toporder_info (&topo
);
3602 /* Do the interprocedural propagation. */
3603 ipcp_propagate_stage (&topo
);
3604 /* Decide what constant propagation and cloning should be performed. */
3605 ipcp_decision_stage (&topo
);
3607 /* Free all IPCP structures. */
3608 free_toporder_info (&topo
);
3609 next_edge_clone
.release ();
3610 cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder
);
3611 ipa_free_all_structures_after_ipa_cp ();
3613 fprintf (dump_file
, "\nIPA constant propagation end\n");
3617 /* Initialization and computation of IPCP data structures. This is the initial
3618 intraprocedural analysis of functions, which gathers information to be
3619 propagated later on. */
3622 ipcp_generate_summary (void)
3624 struct cgraph_node
*node
;
3627 fprintf (dump_file
, "\nIPA constant propagation start:\n");
3628 ipa_register_cgraph_hooks ();
3630 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
3632 node
->local
.versionable
3633 = tree_versionable_function_p (node
->symbol
.decl
);
3634 ipa_analyze_node (node
);
3638 /* Write ipcp summary for nodes in SET. */
3641 ipcp_write_summary (void)
3643 ipa_prop_write_jump_functions ();
3646 /* Read ipcp summary. */
3649 ipcp_read_summary (void)
3651 ipa_prop_read_jump_functions ();
3654 /* Gate for IPCP optimization. */
3657 cgraph_gate_cp (void)
3659 /* FIXME: We should remove the optimize check after we ensure we never run
3660 IPA passes when not optimizing. */
3661 return flag_ipa_cp
&& optimize
;
3664 struct ipa_opt_pass_d pass_ipa_cp
=
3669 OPTGROUP_NONE
, /* optinfo_flags */
3670 cgraph_gate_cp
, /* gate */
3671 ipcp_driver
, /* execute */
3674 0, /* static_pass_number */
3675 TV_IPA_CONSTANT_PROP
, /* tv_id */
3676 0, /* properties_required */
3677 0, /* properties_provided */
3678 0, /* properties_destroyed */
3679 0, /* todo_flags_start */
3681 TODO_remove_functions
/* todo_flags_finish */
3683 ipcp_generate_summary
, /* generate_summary */
3684 ipcp_write_summary
, /* write_summary */
3685 ipcp_read_summary
, /* read_summary */
3686 ipa_prop_write_all_agg_replacement
, /* write_optimization_summary */
3687 ipa_prop_read_all_agg_replacement
, /* read_optimization_summary */
3688 NULL
, /* stmt_fixup */
3690 ipcp_transform_function
, /* function_transform */
3691 NULL
, /* variable_transform */