1 /* Interprocedural constant propagation
2 Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
3 Free Software Foundation, Inc.
5 Contributed by Razya Ladelsky <RAZYA@il.ibm.com> and Martin Jambor
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
24 /* Interprocedural constant propagation (IPA-CP).
26 The goal of this transformation is to
28 1) discover functions which are always invoked with some arguments with the
29 same known constant values and modify the functions so that the
30 subsequent optimizations can take advantage of the knowledge, and
32 2) partial specialization - create specialized versions of functions
33 transformed in this way if some parameters are known constants only in
34 certain contexts but the estimated tradeoff between speedup and cost size
37 The algorithm also propagates types and attempts to perform type based
38 devirtualization. Types are propagated much like constants.
40 The algorithm basically consists of three stages. In the first, functions
41 are analyzed one at a time and jump functions are constructed for all known
42 call-sites. In the second phase, the pass propagates information from the
43 jump functions across the call to reveal what values are available at what
44 call sites, performs estimations of effects of known values on functions and
45 their callees, and finally decides what specialized extra versions should be
46 created. In the third, the special versions materialize and appropriate
49 The algorithm used is to a certain extent based on "Interprocedural Constant
50 Propagation", by David Callahan, Keith D Cooper, Ken Kennedy, Linda Torczon,
51 Comp86, pg 152-161 and "A Methodology for Procedure Cloning" by Keith D
52 Cooper, Mary W. Hall, and Ken Kennedy.
55 First stage - intraprocedural analysis
56 =======================================
58 This phase computes jump_function and modification flags.
60 A jump function for a call-site represents the values passed as an actual
61 arguments of a given call-site. In principle, there are three types of
64 Pass through - the caller's formal parameter is passed as an actual
65 argument, plus an operation on it can be performed.
66 Constant - a constant is passed as an actual argument.
67 Unknown - neither of the above.
69 All jump function types are described in detail in ipa-prop.h, together with
70 the data structures that represent them and methods of accessing them.
72 ipcp_generate_summary() is the main function of the first stage.
74 Second stage - interprocedural analysis
75 ========================================
77 This stage is itself divided into two phases. In the first, we propagate
78 known values over the call graph, in the second, we make cloning decisions.
79 It uses a different algorithm than the original Callahan's paper.
81 First, we traverse the functions topologically from callers to callees and,
82 for each strongly connected component (SCC), we propagate constants
83 according to previously computed jump functions. We also record what known
84 values depend on other known values and estimate local effects. Finally, we
85 propagate cumulative information about these effects from dependent values
86 to those on which they depend.
88 Second, we again traverse the call graph in the same topological order and
89 make clones for functions which we know are called with the same values in
90 all contexts and decide about extra specialized clones of functions just for
91 some contexts - these decisions are based on both local estimates and
92 cumulative estimates propagated from callees.
94 ipcp_propagate_stage() and ipcp_decision_stage() together constitute the
97 Third phase - materialization of clones, call statement updates.
98 ============================================
100 This stage is currently performed by call graph code (mainly in cgraphunit.c
101 and tree-inline.c) according to instructions inserted to the call graph by
106 #include "coretypes.h"
111 #include "ipa-prop.h"
112 #include "tree-flow.h"
113 #include "tree-pass.h"
115 #include "diagnostic.h"
116 #include "tree-pretty-print.h"
117 #include "tree-inline.h"
119 #include "ipa-inline.h"
120 #include "ipa-utils.h"
124 /* Describes a particular source for an IPA-CP value. */
126 struct ipcp_value_source
128 /* The incoming edge that brought the value. */
129 struct cgraph_edge
*cs
;
130 /* If the jump function that resulted into his value was a pass-through or an
131 ancestor, this is the ipcp_value of the caller from which the described
132 value has been derived. Otherwise it is NULL. */
133 struct ipcp_value
*val
;
134 /* Next pointer in a linked list of sources of a value. */
135 struct ipcp_value_source
*next
;
136 /* If the jump function that resulted into his value was a pass-through or an
137 ancestor, this is the index of the parameter of the caller the jump
138 function references. */
142 /* Describes one particular value stored in struct ipcp_lattice. */
146 /* The actual value for the given parameter. This is either an IPA invariant
147 or a TREE_BINFO describing a type that can be used for
150 /* The list of sources from which this value originates. */
151 struct ipcp_value_source
*sources
;
152 /* Next pointers in a linked list of all values in a lattice. */
153 struct ipcp_value
*next
;
154 /* Next pointers in a linked list of values in a strongly connected component
156 struct ipcp_value
*scc_next
;
157 /* Next pointers in a linked list of SCCs of values sorted topologically
158 according their sources. */
159 struct ipcp_value
*topo_next
;
160 /* A specialized node created for this value, NULL if none has been (so far)
162 struct cgraph_node
*spec_node
;
163 /* Depth first search number and low link for topological sorting of
166 /* Time benefit and size cost that specializing the function for this value
167 would bring about in this function alone. */
168 int local_time_benefit
, local_size_cost
;
169 /* Time benefit and size cost that specializing the function for this value
170 can bring about in it's callees (transitively). */
171 int prop_time_benefit
, prop_size_cost
;
172 /* True if this valye is currently on the topo-sort stack. */
176 /* Allocation pools for values and their sources in ipa-cp. */
178 alloc_pool ipcp_values_pool
;
179 alloc_pool ipcp_sources_pool
;
181 /* Lattice describing potential values of a formal parameter of a function and
182 some of their other properties. TOP is represented by a lattice with zero
183 values and with contains_variable and bottom flags cleared. BOTTOM is
184 represented by a lattice with the bottom flag set. In that case, values and
185 contains_variable flag should be disregarded. */
189 /* The list of known values and types in this lattice. Note that values are
190 not deallocated if a lattice is set to bottom because there may be value
191 sources referencing them. */
192 struct ipcp_value
*values
;
193 /* Number of known values and types in this lattice. */
195 /* The lattice contains a variable component (in addition to values). */
196 bool contains_variable
;
197 /* The value of the lattice is bottom (i.e. variable and unusable for any
200 /* There is a virtual call based on this parameter. */
204 /* Maximal count found in program. */
206 static gcov_type max_count
;
208 /* Original overall size of the program. */
210 static long overall_size
, max_new_size
;
212 /* Head of the linked list of topologically sorted values. */
214 static struct ipcp_value
*values_topo
;
216 /* Return the lattice corresponding to the Ith formal parameter of the function
217 described by INFO. */
218 static inline struct ipcp_lattice
*
219 ipa_get_lattice (struct ipa_node_params
*info
, int i
)
221 gcc_assert (i
>= 0 && i
< ipa_get_param_count (info
));
222 gcc_checking_assert (!info
->ipcp_orig_node
);
223 gcc_checking_assert (info
->lattices
);
224 return &(info
->lattices
[i
]);
227 /* Return whether LAT is a lattice with a single constant and without an
231 ipa_lat_is_single_const (struct ipcp_lattice
*lat
)
234 || lat
->contains_variable
235 || lat
->values_count
!= 1)
241 /* Return true iff the CS is an edge within a strongly connected component as
242 computed by ipa_reduced_postorder. */
245 edge_within_scc (struct cgraph_edge
*cs
)
247 struct ipa_dfs_info
*caller_dfs
= (struct ipa_dfs_info
*) cs
->caller
->symbol
.aux
;
248 struct ipa_dfs_info
*callee_dfs
;
249 struct cgraph_node
*callee
= cgraph_function_node (cs
->callee
, NULL
);
251 callee_dfs
= (struct ipa_dfs_info
*) callee
->symbol
.aux
;
254 && caller_dfs
->scc_no
== callee_dfs
->scc_no
);
257 /* Print V which is extracted from a value in a lattice to F. */
260 print_ipcp_constant_value (FILE * f
, tree v
)
262 if (TREE_CODE (v
) == TREE_BINFO
)
264 fprintf (f
, "BINFO ");
265 print_generic_expr (f
, BINFO_TYPE (v
), 0);
267 else if (TREE_CODE (v
) == ADDR_EXPR
268 && TREE_CODE (TREE_OPERAND (v
, 0)) == CONST_DECL
)
271 print_generic_expr (f
, DECL_INITIAL (TREE_OPERAND (v
, 0)), 0);
274 print_generic_expr (f
, v
, 0);
277 /* Print all ipcp_lattices of all functions to F. */
280 print_all_lattices (FILE * f
, bool dump_sources
, bool dump_benefits
)
282 struct cgraph_node
*node
;
285 fprintf (f
, "\nLattices:\n");
286 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
288 struct ipa_node_params
*info
;
290 info
= IPA_NODE_REF (node
);
291 fprintf (f
, " Node: %s/%i:\n", cgraph_node_name (node
), node
->uid
);
292 count
= ipa_get_param_count (info
);
293 for (i
= 0; i
< count
; i
++)
295 struct ipcp_lattice
*lat
= ipa_get_lattice (info
, i
);
296 struct ipcp_value
*val
;
299 fprintf (f
, " param [%d]: ", i
);
302 fprintf (f
, "BOTTOM\n");
306 if (!lat
->values_count
&& !lat
->contains_variable
)
308 fprintf (f
, "TOP\n");
312 if (lat
->contains_variable
)
314 fprintf (f
, "VARIABLE");
320 for (val
= lat
->values
; val
; val
= val
->next
)
322 if (dump_benefits
&& prev
)
324 else if (!dump_benefits
&& prev
)
329 print_ipcp_constant_value (f
, val
->value
);
333 struct ipcp_value_source
*s
;
335 fprintf (f
, " [from:");
336 for (s
= val
->sources
; s
; s
= s
->next
)
337 fprintf (f
, " %i(%i)", s
->cs
->caller
->uid
,s
->cs
->frequency
);
342 fprintf (f
, " [loc_time: %i, loc_size: %i, "
343 "prop_time: %i, prop_size: %i]\n",
344 val
->local_time_benefit
, val
->local_size_cost
,
345 val
->prop_time_benefit
, val
->prop_size_cost
);
353 /* Determine whether it is at all technically possible to create clones of NODE
354 and store this information in the ipa_node_params structure associated
358 determine_versionability (struct cgraph_node
*node
)
360 const char *reason
= NULL
;
362 /* There are a number of generic reasons functions cannot be versioned. We
363 also cannot remove parameters if there are type attributes such as fnspec
365 if (node
->alias
|| node
->thunk
.thunk_p
)
366 reason
= "alias or thunk";
367 else if (!node
->local
.versionable
)
368 reason
= "not a tree_versionable_function";
369 else if (cgraph_function_body_availability (node
) <= AVAIL_OVERWRITABLE
)
370 reason
= "insufficient body availability";
372 if (reason
&& dump_file
&& !node
->alias
&& !node
->thunk
.thunk_p
)
373 fprintf (dump_file
, "Function %s/%i is not versionable, reason: %s.\n",
374 cgraph_node_name (node
), node
->uid
, reason
);
376 node
->local
.versionable
= (reason
== NULL
);
379 /* Return true if it is at all technically possible to create clones of a
383 ipcp_versionable_function_p (struct cgraph_node
*node
)
385 return node
->local
.versionable
;
388 /* Structure holding accumulated information about callers of a node. */
390 struct caller_statistics
393 int n_calls
, n_hot_calls
, freq_sum
;
396 /* Initialize fields of STAT to zeroes. */
399 init_caller_stats (struct caller_statistics
*stats
)
401 stats
->count_sum
= 0;
403 stats
->n_hot_calls
= 0;
407 /* Worker callback of cgraph_for_node_and_aliases accumulating statistics of
408 non-thunk incoming edges to NODE. */
411 gather_caller_stats (struct cgraph_node
*node
, void *data
)
413 struct caller_statistics
*stats
= (struct caller_statistics
*) data
;
414 struct cgraph_edge
*cs
;
416 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
417 if (cs
->caller
->thunk
.thunk_p
)
418 cgraph_for_node_and_aliases (cs
->caller
, gather_caller_stats
,
422 stats
->count_sum
+= cs
->count
;
423 stats
->freq_sum
+= cs
->frequency
;
425 if (cgraph_maybe_hot_edge_p (cs
))
426 stats
->n_hot_calls
++;
432 /* Return true if this NODE is viable candidate for cloning. */
435 ipcp_cloning_candidate_p (struct cgraph_node
*node
)
437 struct caller_statistics stats
;
439 gcc_checking_assert (cgraph_function_with_gimple_body_p (node
));
441 if (!flag_ipa_cp_clone
)
444 fprintf (dump_file
, "Not considering %s for cloning; "
445 "-fipa-cp-clone disabled.\n",
446 cgraph_node_name (node
));
450 if (!optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node
->symbol
.decl
)))
453 fprintf (dump_file
, "Not considering %s for cloning; "
454 "optimizing it for size.\n",
455 cgraph_node_name (node
));
459 init_caller_stats (&stats
);
460 cgraph_for_node_and_aliases (node
, gather_caller_stats
, &stats
, false);
462 if (inline_summary (node
)->self_size
< stats
.n_calls
)
465 fprintf (dump_file
, "Considering %s for cloning; code might shrink.\n",
466 cgraph_node_name (node
));
470 /* When profile is available and function is hot, propagate into it even if
471 calls seems cold; constant propagation can improve function's speed
475 if (stats
.count_sum
> node
->count
* 90 / 100)
478 fprintf (dump_file
, "Considering %s for cloning; "
479 "usually called directly.\n",
480 cgraph_node_name (node
));
484 if (!stats
.n_hot_calls
)
487 fprintf (dump_file
, "Not considering %s for cloning; no hot calls.\n",
488 cgraph_node_name (node
));
492 fprintf (dump_file
, "Considering %s for cloning.\n",
493 cgraph_node_name (node
));
497 /* Arrays representing a topological ordering of call graph nodes and a stack
498 of noes used during constant propagation. */
502 struct cgraph_node
**order
;
503 struct cgraph_node
**stack
;
504 int nnodes
, stack_top
;
507 /* Allocate the arrays in TOPO and topologically sort the nodes into order. */
510 build_toporder_info (struct topo_info
*topo
)
512 topo
->order
= XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
513 topo
->stack
= XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
515 topo
->nnodes
= ipa_reduced_postorder (topo
->order
, true, true, NULL
);
518 /* Free information about strongly connected components and the arrays in
522 free_toporder_info (struct topo_info
*topo
)
524 ipa_free_postorder_info ();
529 /* Add NODE to the stack in TOPO, unless it is already there. */
532 push_node_to_stack (struct topo_info
*topo
, struct cgraph_node
*node
)
534 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
535 if (info
->node_enqueued
)
537 info
->node_enqueued
= 1;
538 topo
->stack
[topo
->stack_top
++] = node
;
541 /* Pop a node from the stack in TOPO and return it or return NULL if the stack
544 static struct cgraph_node
*
545 pop_node_from_stack (struct topo_info
*topo
)
549 struct cgraph_node
*node
;
551 node
= topo
->stack
[topo
->stack_top
];
552 IPA_NODE_REF (node
)->node_enqueued
= 0;
559 /* Set lattice LAT to bottom and return true if it previously was not set as
563 set_lattice_to_bottom (struct ipcp_lattice
*lat
)
565 bool ret
= !lat
->bottom
;
570 /* Mark lattice as containing an unknown value and return true if it previously
571 was not marked as such. */
574 set_lattice_contains_variable (struct ipcp_lattice
*lat
)
576 bool ret
= !lat
->contains_variable
;
577 lat
->contains_variable
= true;
581 /* Initialize ipcp_lattices. */
584 initialize_node_lattices (struct cgraph_node
*node
)
586 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
587 struct cgraph_edge
*ie
;
588 bool disable
= false, variable
= false;
591 gcc_checking_assert (cgraph_function_with_gimple_body_p (node
));
592 if (!node
->local
.local
)
594 /* When cloning is allowed, we can assume that externally visible
595 functions are not called. We will compensate this by cloning
597 if (ipcp_versionable_function_p (node
)
598 && ipcp_cloning_candidate_p (node
))
604 if (disable
|| variable
)
606 for (i
= 0; i
< ipa_get_param_count (info
) ; i
++)
608 struct ipcp_lattice
*lat
= ipa_get_lattice (info
, i
);
610 set_lattice_to_bottom (lat
);
612 set_lattice_contains_variable (lat
);
614 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
615 && node
->alias
&& node
->thunk
.thunk_p
)
616 fprintf (dump_file
, "Marking all lattices of %s/%i as %s\n",
617 cgraph_node_name (node
), node
->uid
,
618 disable
? "BOTTOM" : "VARIABLE");
621 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
622 if (ie
->indirect_info
->polymorphic
)
624 gcc_checking_assert (ie
->indirect_info
->param_index
>= 0);
625 ipa_get_lattice (info
, ie
->indirect_info
->param_index
)->virt_call
= 1;
629 /* Return the result of a (possibly arithmetic) pass through jump function
630 JFUNC on the constant value INPUT. Return NULL_TREE if that cannot be
631 determined or itself is considered an interprocedural invariant. */
634 ipa_get_jf_pass_through_result (struct ipa_jump_func
*jfunc
, tree input
)
638 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
640 else if (TREE_CODE (input
) == TREE_BINFO
)
643 gcc_checking_assert (is_gimple_ip_invariant (input
));
644 if (TREE_CODE_CLASS (ipa_get_jf_pass_through_operation (jfunc
))
646 restype
= boolean_type_node
;
648 restype
= TREE_TYPE (input
);
649 res
= fold_binary (ipa_get_jf_pass_through_operation (jfunc
), restype
,
650 input
, ipa_get_jf_pass_through_operand (jfunc
));
652 if (res
&& !is_gimple_ip_invariant (res
))
658 /* Return the result of an ancestor jump function JFUNC on the constant value
659 INPUT. Return NULL_TREE if that cannot be determined. */
662 ipa_get_jf_ancestor_result (struct ipa_jump_func
*jfunc
, tree input
)
664 if (TREE_CODE (input
) == TREE_BINFO
)
665 return get_binfo_at_offset (input
,
666 ipa_get_jf_ancestor_offset (jfunc
),
667 ipa_get_jf_ancestor_type (jfunc
));
668 else if (TREE_CODE (input
) == ADDR_EXPR
)
670 tree t
= TREE_OPERAND (input
, 0);
671 t
= build_ref_for_offset (EXPR_LOCATION (t
), t
,
672 ipa_get_jf_ancestor_offset (jfunc
),
673 ipa_get_jf_ancestor_type (jfunc
), NULL
, false);
674 return build_fold_addr_expr (t
);
680 /* Extract the acual BINFO being described by JFUNC which must be a known type
684 ipa_value_from_known_type_jfunc (struct ipa_jump_func
*jfunc
)
686 tree base_binfo
= TYPE_BINFO (ipa_get_jf_known_type_base_type (jfunc
));
689 return get_binfo_at_offset (base_binfo
,
690 ipa_get_jf_known_type_offset (jfunc
),
691 ipa_get_jf_known_type_component_type (jfunc
));
694 /* Determine whether JFUNC evaluates to a known value (that is either a
695 constant or a binfo) and if so, return it. Otherwise return NULL. INFO
696 describes the caller node so that pass-through jump functions can be
700 ipa_value_from_jfunc (struct ipa_node_params
*info
, struct ipa_jump_func
*jfunc
)
702 if (jfunc
->type
== IPA_JF_CONST
)
703 return ipa_get_jf_constant (jfunc
);
704 else if (jfunc
->type
== IPA_JF_KNOWN_TYPE
)
705 return ipa_value_from_known_type_jfunc (jfunc
);
706 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
707 || jfunc
->type
== IPA_JF_ANCESTOR
)
712 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
713 idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
715 idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
717 if (info
->ipcp_orig_node
)
718 input
= VEC_index (tree
, info
->known_vals
, idx
);
721 struct ipcp_lattice
*lat
;
725 gcc_checking_assert (!flag_ipa_cp
);
728 lat
= ipa_get_lattice (info
, idx
);
729 if (!ipa_lat_is_single_const (lat
))
731 input
= lat
->values
->value
;
737 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
738 return ipa_get_jf_pass_through_result (jfunc
, input
);
740 return ipa_get_jf_ancestor_result (jfunc
, input
);
747 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
748 bottom, not containing a variable component and without any known value at
752 ipcp_verify_propagated_values (void)
754 struct cgraph_node
*node
;
756 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
758 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
759 int i
, count
= ipa_get_param_count (info
);
761 for (i
= 0; i
< count
; i
++)
763 struct ipcp_lattice
*lat
= ipa_get_lattice (info
, i
);
766 && !lat
->contains_variable
767 && lat
->values_count
== 0)
771 fprintf (dump_file
, "\nIPA lattices after constant "
773 print_all_lattices (dump_file
, true, false);
782 /* Return true iff X and Y should be considered equal values by IPA-CP. */
785 values_equal_for_ipcp_p (tree x
, tree y
)
787 gcc_checking_assert (x
!= NULL_TREE
&& y
!= NULL_TREE
);
792 if (TREE_CODE (x
) == TREE_BINFO
|| TREE_CODE (y
) == TREE_BINFO
)
795 if (TREE_CODE (x
) == ADDR_EXPR
796 && TREE_CODE (y
) == ADDR_EXPR
797 && TREE_CODE (TREE_OPERAND (x
, 0)) == CONST_DECL
798 && TREE_CODE (TREE_OPERAND (y
, 0)) == CONST_DECL
)
799 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x
, 0)),
800 DECL_INITIAL (TREE_OPERAND (y
, 0)), 0);
802 return operand_equal_p (x
, y
, 0);
805 /* Add a new value source to VAL, marking that a value comes from edge CS and
806 (if the underlying jump function is a pass-through or an ancestor one) from
807 a caller value SRC_VAL of a caller parameter described by SRC_INDEX. */
810 add_value_source (struct ipcp_value
*val
, struct cgraph_edge
*cs
,
811 struct ipcp_value
*src_val
, int src_idx
)
813 struct ipcp_value_source
*src
;
815 src
= (struct ipcp_value_source
*) pool_alloc (ipcp_sources_pool
);
818 src
->index
= src_idx
;
820 src
->next
= val
->sources
;
825 /* Try to add NEWVAL to LAT, potentially creating a new struct ipcp_value for
826 it. CS, SRC_VAL and SRC_INDEX are meant for add_value_source and have the
830 add_value_to_lattice (struct ipcp_lattice
*lat
, tree newval
,
831 struct cgraph_edge
*cs
, struct ipcp_value
*src_val
,
834 struct ipcp_value
*val
;
840 for (val
= lat
->values
; val
; val
= val
->next
)
841 if (values_equal_for_ipcp_p (val
->value
, newval
))
843 if (edge_within_scc (cs
))
845 struct ipcp_value_source
*s
;
846 for (s
= val
->sources
; s
; s
= s
->next
)
853 add_value_source (val
, cs
, src_val
, src_idx
);
857 if (lat
->values_count
== PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE
))
859 /* We can only free sources, not the values themselves, because sources
860 of other values in this this SCC might point to them. */
861 for (val
= lat
->values
; val
; val
= val
->next
)
865 struct ipcp_value_source
*src
= val
->sources
;
866 val
->sources
= src
->next
;
867 pool_free (ipcp_sources_pool
, src
);
872 return set_lattice_to_bottom (lat
);
876 val
= (struct ipcp_value
*) pool_alloc (ipcp_values_pool
);
877 memset (val
, 0, sizeof (*val
));
879 add_value_source (val
, cs
, src_val
, src_idx
);
881 val
->next
= lat
->values
;
886 /* Propagate values through a pass-through jump function JFUNC associated with
887 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
888 is the index of the source parameter. */
891 propagate_vals_accross_pass_through (struct cgraph_edge
*cs
,
892 struct ipa_jump_func
*jfunc
,
893 struct ipcp_lattice
*src_lat
,
894 struct ipcp_lattice
*dest_lat
,
897 struct ipcp_value
*src_val
;
900 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
901 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
902 ret
|= add_value_to_lattice (dest_lat
, src_val
->value
, cs
,
904 /* Do not create new values when propagating within an SCC because if there
905 are arithmetic functions with circular dependencies, there is infinite
906 number of them and we would just make lattices bottom. */
907 else if (edge_within_scc (cs
))
908 ret
= set_lattice_contains_variable (dest_lat
);
910 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
912 tree cstval
= src_val
->value
;
914 if (TREE_CODE (cstval
) == TREE_BINFO
)
916 ret
|= set_lattice_contains_variable (dest_lat
);
919 cstval
= ipa_get_jf_pass_through_result (jfunc
, cstval
);
922 ret
|= add_value_to_lattice (dest_lat
, cstval
, cs
, src_val
, src_idx
);
924 ret
|= set_lattice_contains_variable (dest_lat
);
930 /* Propagate values through an ancestor jump function JFUNC associated with
931 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
932 is the index of the source parameter. */
935 propagate_vals_accross_ancestor (struct cgraph_edge
*cs
,
936 struct ipa_jump_func
*jfunc
,
937 struct ipcp_lattice
*src_lat
,
938 struct ipcp_lattice
*dest_lat
,
941 struct ipcp_value
*src_val
;
944 if (edge_within_scc (cs
))
945 return set_lattice_contains_variable (dest_lat
);
947 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
949 tree t
= ipa_get_jf_ancestor_result (jfunc
, src_val
->value
);
952 ret
|= add_value_to_lattice (dest_lat
, t
, cs
, src_val
, src_idx
);
954 ret
|= set_lattice_contains_variable (dest_lat
);
960 /* Propagate values across jump function JFUNC that is associated with edge CS
961 and put the values into DEST_LAT. */
964 propagate_accross_jump_function (struct cgraph_edge
*cs
,
965 struct ipa_jump_func
*jfunc
,
966 struct ipcp_lattice
*dest_lat
)
968 if (dest_lat
->bottom
)
971 if (jfunc
->type
== IPA_JF_CONST
972 || jfunc
->type
== IPA_JF_KNOWN_TYPE
)
976 if (jfunc
->type
== IPA_JF_KNOWN_TYPE
)
978 val
= ipa_value_from_known_type_jfunc (jfunc
);
980 return set_lattice_contains_variable (dest_lat
);
983 val
= ipa_get_jf_constant (jfunc
);
984 return add_value_to_lattice (dest_lat
, val
, cs
, NULL
, 0);
986 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
987 || jfunc
->type
== IPA_JF_ANCESTOR
)
989 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
990 struct ipcp_lattice
*src_lat
;
994 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
995 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
997 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
999 src_lat
= ipa_get_lattice (caller_info
, src_idx
);
1000 if (src_lat
->bottom
)
1001 return set_lattice_contains_variable (dest_lat
);
1003 /* If we would need to clone the caller and cannot, do not propagate. */
1004 if (!ipcp_versionable_function_p (cs
->caller
)
1005 && (src_lat
->contains_variable
1006 || (src_lat
->values_count
> 1)))
1007 return set_lattice_contains_variable (dest_lat
);
1009 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1010 ret
= propagate_vals_accross_pass_through (cs
, jfunc
, src_lat
,
1013 ret
= propagate_vals_accross_ancestor (cs
, jfunc
, src_lat
, dest_lat
,
1016 if (src_lat
->contains_variable
)
1017 ret
|= set_lattice_contains_variable (dest_lat
);
1022 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1023 use it for indirect inlining), we should propagate them too. */
1024 return set_lattice_contains_variable (dest_lat
);
1027 /* Propagate constants from the caller to the callee of CS. INFO describes the
1031 propagate_constants_accross_call (struct cgraph_edge
*cs
)
1033 struct ipa_node_params
*callee_info
;
1034 enum availability availability
;
1035 struct cgraph_node
*callee
, *alias_or_thunk
;
1036 struct ipa_edge_args
*args
;
1038 int i
, args_count
, parms_count
;
1040 callee
= cgraph_function_node (cs
->callee
, &availability
);
1041 if (!callee
->analyzed
)
1043 gcc_checking_assert (cgraph_function_with_gimple_body_p (callee
));
1044 callee_info
= IPA_NODE_REF (callee
);
1046 args
= IPA_EDGE_REF (cs
);
1047 args_count
= ipa_get_cs_argument_count (args
);
1048 parms_count
= ipa_get_param_count (callee_info
);
1050 /* If this call goes through a thunk we must not propagate to the first (0th)
1051 parameter. However, we might need to uncover a thunk from below a series
1052 of aliases first. */
1053 alias_or_thunk
= cs
->callee
;
1054 while (alias_or_thunk
->alias
)
1055 alias_or_thunk
= cgraph_alias_aliased_node (alias_or_thunk
);
1056 if (alias_or_thunk
->thunk
.thunk_p
)
1058 ret
|= set_lattice_contains_variable (ipa_get_lattice (callee_info
, 0));
1064 for (; (i
< args_count
) && (i
< parms_count
); i
++)
1066 struct ipa_jump_func
*jump_func
= ipa_get_ith_jump_func (args
, i
);
1067 struct ipcp_lattice
*dest_lat
= ipa_get_lattice (callee_info
, i
);
1069 if (availability
== AVAIL_OVERWRITABLE
)
1070 ret
|= set_lattice_contains_variable (dest_lat
);
1072 ret
|= propagate_accross_jump_function (cs
, jump_func
, dest_lat
);
1074 for (; i
< parms_count
; i
++)
1075 ret
|= set_lattice_contains_variable (ipa_get_lattice (callee_info
, i
));
1080 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
1081 (which can contain both constants and binfos) or KNOWN_BINFOS (which can be
1082 NULL) return the destination. */
1085 ipa_get_indirect_edge_target (struct cgraph_edge
*ie
,
1086 VEC (tree
, heap
) *known_vals
,
1087 VEC (tree
, heap
) *known_binfos
,
1088 VEC (ipa_agg_jump_function_p
, heap
) *known_aggs
)
1090 int param_index
= ie
->indirect_info
->param_index
;
1091 HOST_WIDE_INT token
, anc_offset
;
1095 if (param_index
== -1)
1098 if (!ie
->indirect_info
->polymorphic
)
1102 if (ie
->indirect_info
->agg_contents
)
1104 if (VEC_length (ipa_agg_jump_function_p
, known_aggs
)
1105 > (unsigned int) param_index
)
1107 struct ipa_agg_jump_function
*agg
;
1108 agg
= VEC_index (ipa_agg_jump_function_p
, known_aggs
,
1110 t
= ipa_find_agg_cst_for_param (agg
, ie
->indirect_info
->offset
,
1111 ie
->indirect_info
->by_ref
);
1117 t
= (VEC_length (tree
, known_vals
) > (unsigned int) param_index
1118 ? VEC_index (tree
, known_vals
, param_index
) : NULL
);
1121 TREE_CODE (t
) == ADDR_EXPR
1122 && TREE_CODE (TREE_OPERAND (t
, 0)) == FUNCTION_DECL
)
1123 return TREE_OPERAND (t
, 0);
1128 gcc_assert (!ie
->indirect_info
->agg_contents
);
1129 token
= ie
->indirect_info
->otr_token
;
1130 anc_offset
= ie
->indirect_info
->offset
;
1131 otr_type
= ie
->indirect_info
->otr_type
;
1133 t
= VEC_index (tree
, known_vals
, param_index
);
1134 if (!t
&& known_binfos
1135 && VEC_length (tree
, known_binfos
) > (unsigned int) param_index
)
1136 t
= VEC_index (tree
, known_binfos
, param_index
);
1140 if (TREE_CODE (t
) != TREE_BINFO
)
1143 binfo
= gimple_extract_devirt_binfo_from_cst (t
);
1146 binfo
= get_binfo_at_offset (binfo
, anc_offset
, otr_type
);
1149 return gimple_get_virt_method_for_binfo (token
, binfo
);
1155 binfo
= get_binfo_at_offset (t
, anc_offset
, otr_type
);
1158 return gimple_get_virt_method_for_binfo (token
, binfo
);
1162 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
1163 and KNOWN_BINFOS. */
1166 devirtualization_time_bonus (struct cgraph_node
*node
,
1167 VEC (tree
, heap
) *known_csts
,
1168 VEC (tree
, heap
) *known_binfos
)
1170 struct cgraph_edge
*ie
;
1173 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
1175 struct cgraph_node
*callee
;
1176 struct inline_summary
*isummary
;
1179 target
= ipa_get_indirect_edge_target (ie
, known_csts
, known_binfos
,
1184 /* Only bare minimum benefit for clearly un-inlineable targets. */
1186 callee
= cgraph_get_node (target
);
1187 if (!callee
|| !callee
->analyzed
)
1189 isummary
= inline_summary (callee
);
1190 if (!isummary
->inlinable
)
1193 /* FIXME: The values below need re-considering and perhaps also
1194 integrating into the cost metrics, at lest in some very basic way. */
1195 if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 4)
1197 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 2)
1199 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
1200 || DECL_DECLARED_INLINE_P (callee
->symbol
.decl
))
1207 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
1208 and SIZE_COST and with the sum of frequencies of incoming edges to the
1209 potential new clone in FREQUENCIES. */
1212 good_cloning_opportunity_p (struct cgraph_node
*node
, int time_benefit
,
1213 int freq_sum
, gcov_type count_sum
, int size_cost
)
1215 if (time_benefit
== 0
1216 || !flag_ipa_cp_clone
1217 || !optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node
->symbol
.decl
)))
1220 gcc_assert (size_cost
> 0);
1224 int factor
= (count_sum
* 1000) / max_count
;
1225 HOST_WIDEST_INT evaluation
= (((HOST_WIDEST_INT
) time_benefit
* factor
)
1228 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1229 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
1230 "size: %i, count_sum: " HOST_WIDE_INT_PRINT_DEC
1231 ") -> evaluation: " HOST_WIDEST_INT_PRINT_DEC
1232 ", threshold: %i\n",
1233 time_benefit
, size_cost
, (HOST_WIDE_INT
) count_sum
,
1236 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
1240 HOST_WIDEST_INT evaluation
= (((HOST_WIDEST_INT
) time_benefit
* freq_sum
)
1243 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1244 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
1245 "size: %i, freq_sum: %i) -> evaluation: "
1246 HOST_WIDEST_INT_PRINT_DEC
", threshold: %i\n",
1247 time_benefit
, size_cost
, freq_sum
, evaluation
,
1248 CGRAPH_FREQ_BASE
/2);
1250 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
1255 /* Allocate KNOWN_CSTS and KNOWN_BINFOS and populate them with values of
1256 parameters that are known independent of the context. INFO describes the
1257 function. If REMOVABLE_PARAMS_COST is non-NULL, the movement cost of all
1258 removable parameters will be stored in it. */
1261 gather_context_independent_values (struct ipa_node_params
*info
,
1262 VEC (tree
, heap
) **known_csts
,
1263 VEC (tree
, heap
) **known_binfos
,
1264 int *removable_params_cost
)
1266 int i
, count
= ipa_get_param_count (info
);
1270 *known_binfos
= NULL
;
1271 VEC_safe_grow_cleared (tree
, heap
, *known_csts
, count
);
1272 VEC_safe_grow_cleared (tree
, heap
, *known_binfos
, count
);
1274 if (removable_params_cost
)
1275 *removable_params_cost
= 0;
1277 for (i
= 0; i
< count
; i
++)
1279 struct ipcp_lattice
*lat
= ipa_get_lattice (info
, i
);
1281 if (ipa_lat_is_single_const (lat
))
1283 struct ipcp_value
*val
= lat
->values
;
1284 if (TREE_CODE (val
->value
) != TREE_BINFO
)
1286 VEC_replace (tree
, *known_csts
, i
, val
->value
);
1287 if (removable_params_cost
)
1288 *removable_params_cost
1289 += estimate_move_cost (TREE_TYPE (val
->value
));
1292 else if (lat
->virt_call
)
1294 VEC_replace (tree
, *known_binfos
, i
, val
->value
);
1297 else if (removable_params_cost
1298 && !ipa_is_param_used (info
, i
))
1299 *removable_params_cost
1300 += estimate_move_cost (TREE_TYPE (ipa_get_param (info
, i
)));
1302 else if (removable_params_cost
1303 && !ipa_is_param_used (info
, i
))
1304 *removable_params_cost
1305 += estimate_move_cost (TREE_TYPE (ipa_get_param (info
, i
)));
1311 /* Iterate over known values of parameters of NODE and estimate the local
1312 effects in terms of time and size they have. */
1315 estimate_local_effects (struct cgraph_node
*node
)
1317 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1318 int i
, count
= ipa_get_param_count (info
);
1319 VEC (tree
, heap
) *known_csts
, *known_binfos
;
1321 int base_time
= inline_summary (node
)->time
;
1322 int removable_params_cost
;
1324 if (!count
|| !ipcp_versionable_function_p (node
))
1327 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1328 fprintf (dump_file
, "\nEstimating effects for %s/%i, base_time: %i.\n",
1329 cgraph_node_name (node
), node
->uid
, base_time
);
1331 always_const
= gather_context_independent_values (info
, &known_csts
,
1333 &removable_params_cost
);
1336 struct caller_statistics stats
;
1339 init_caller_stats (&stats
);
1340 cgraph_for_node_and_aliases (node
, gather_caller_stats
, &stats
, false);
1341 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_binfos
,
1343 time
-= devirtualization_time_bonus (node
, known_csts
, known_binfos
);
1344 time
-= removable_params_cost
;
1345 size
-= stats
.n_calls
* removable_params_cost
;
1348 fprintf (dump_file
, " - context independent values, size: %i, "
1349 "time_benefit: %i\n", size
, base_time
- time
);
1352 || cgraph_will_be_removed_from_program_if_no_direct_calls (node
))
1354 info
->clone_for_all_contexts
= true;
1358 fprintf (dump_file
, " Decided to specialize for all "
1359 "known contexts, code not going to grow.\n");
1361 else if (good_cloning_opportunity_p (node
, base_time
- time
,
1362 stats
.freq_sum
, stats
.count_sum
,
1365 if (size
+ overall_size
<= max_new_size
)
1367 info
->clone_for_all_contexts
= true;
1369 overall_size
+= size
;
1372 fprintf (dump_file
, " Decided to specialize for all "
1373 "known contexts, growth deemed beneficial.\n");
1375 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1376 fprintf (dump_file
, " Not cloning for all contexts because "
1377 "max_new_size would be reached with %li.\n",
1378 size
+ overall_size
);
1382 for (i
= 0; i
< count
; i
++)
1384 struct ipcp_lattice
*lat
= ipa_get_lattice (info
, i
);
1385 struct ipcp_value
*val
;
1390 || VEC_index (tree
, known_csts
, i
)
1391 || VEC_index (tree
, known_binfos
, i
))
1394 for (val
= lat
->values
; val
; val
= val
->next
)
1396 int time
, size
, time_benefit
;
1398 if (TREE_CODE (val
->value
) != TREE_BINFO
)
1400 VEC_replace (tree
, known_csts
, i
, val
->value
);
1401 VEC_replace (tree
, known_binfos
, i
, NULL_TREE
);
1402 emc
= estimate_move_cost (TREE_TYPE (val
->value
));
1404 else if (lat
->virt_call
)
1406 VEC_replace (tree
, known_csts
, i
, NULL_TREE
);
1407 VEC_replace (tree
, known_binfos
, i
, val
->value
);
1413 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_binfos
,
1415 time_benefit
= base_time
- time
1416 + devirtualization_time_bonus (node
, known_csts
, known_binfos
)
1417 + removable_params_cost
+ emc
;
1419 gcc_checking_assert (size
>=0);
1420 /* The inliner-heuristics based estimates may think that in certain
1421 contexts some functions do not have any size at all but we want
1422 all specializations to have at least a tiny cost, not least not to
1427 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1429 fprintf (dump_file
, " - estimates for value ");
1430 print_ipcp_constant_value (dump_file
, val
->value
);
1431 fprintf (dump_file
, " for parameter ");
1432 print_generic_expr (dump_file
, ipa_get_param (info
, i
), 0);
1433 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
1434 time_benefit
, size
);
1437 val
->local_time_benefit
= time_benefit
;
1438 val
->local_size_cost
= size
;
1442 VEC_free (tree
, heap
, known_csts
);
1443 VEC_free (tree
, heap
, known_binfos
);
1447 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
1448 topological sort of values. */
1451 add_val_to_toposort (struct ipcp_value
*cur_val
)
1453 static int dfs_counter
= 0;
1454 static struct ipcp_value
*stack
;
1455 struct ipcp_value_source
*src
;
1461 cur_val
->dfs
= dfs_counter
;
1462 cur_val
->low_link
= dfs_counter
;
1464 cur_val
->topo_next
= stack
;
1466 cur_val
->on_stack
= true;
1468 for (src
= cur_val
->sources
; src
; src
= src
->next
)
1471 if (src
->val
->dfs
== 0)
1473 add_val_to_toposort (src
->val
);
1474 if (src
->val
->low_link
< cur_val
->low_link
)
1475 cur_val
->low_link
= src
->val
->low_link
;
1477 else if (src
->val
->on_stack
1478 && src
->val
->dfs
< cur_val
->low_link
)
1479 cur_val
->low_link
= src
->val
->dfs
;
1482 if (cur_val
->dfs
== cur_val
->low_link
)
1484 struct ipcp_value
*v
, *scc_list
= NULL
;
1489 stack
= v
->topo_next
;
1490 v
->on_stack
= false;
1492 v
->scc_next
= scc_list
;
1495 while (v
!= cur_val
);
1497 cur_val
->topo_next
= values_topo
;
1498 values_topo
= cur_val
;
1502 /* Add all values in lattices associated with NODE to the topological sort if
1503 they are not there yet. */
1506 add_all_node_vals_to_toposort (struct cgraph_node
*node
)
1508 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1509 int i
, count
= ipa_get_param_count (info
);
1511 for (i
= 0; i
< count
; i
++)
1513 struct ipcp_lattice
*lat
= ipa_get_lattice (info
, i
);
1514 struct ipcp_value
*val
;
1516 if (lat
->bottom
|| !lat
->values
)
1518 for (val
= lat
->values
; val
; val
= val
->next
)
1519 add_val_to_toposort (val
);
1523 /* One pass of constants propagation along the call graph edges, from callers
1524 to callees (requires topological ordering in TOPO), iterate over strongly
1525 connected components. */
1528 propagate_constants_topo (struct topo_info
*topo
)
1532 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
1534 struct cgraph_node
*v
, *node
= topo
->order
[i
];
1535 struct ipa_dfs_info
*node_dfs_info
;
1537 if (!cgraph_function_with_gimple_body_p (node
))
1540 node_dfs_info
= (struct ipa_dfs_info
*) node
->symbol
.aux
;
1541 /* First, iteratively propagate within the strongly connected component
1542 until all lattices stabilize. */
1543 v
= node_dfs_info
->next_cycle
;
1546 push_node_to_stack (topo
, v
);
1547 v
= ((struct ipa_dfs_info
*) v
->symbol
.aux
)->next_cycle
;
1553 struct cgraph_edge
*cs
;
1555 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
1556 if (edge_within_scc (cs
)
1557 && propagate_constants_accross_call (cs
))
1558 push_node_to_stack (topo
, cs
->callee
);
1559 v
= pop_node_from_stack (topo
);
1562 /* Afterwards, propagate along edges leading out of the SCC, calculates
1563 the local effects of the discovered constants and all valid values to
1564 their topological sort. */
1568 struct cgraph_edge
*cs
;
1570 estimate_local_effects (v
);
1571 add_all_node_vals_to_toposort (v
);
1572 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
1573 if (!edge_within_scc (cs
))
1574 propagate_constants_accross_call (cs
);
1576 v
= ((struct ipa_dfs_info
*) v
->symbol
.aux
)->next_cycle
;
1582 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
1583 the bigger one if otherwise. */
1586 safe_add (int a
, int b
)
1588 if (a
> INT_MAX
/2 || b
> INT_MAX
/2)
1589 return a
> b
? a
: b
;
1595 /* Propagate the estimated effects of individual values along the topological
1596 from the dependent values to those they depend on. */
1599 propagate_effects (void)
1601 struct ipcp_value
*base
;
1603 for (base
= values_topo
; base
; base
= base
->topo_next
)
1605 struct ipcp_value_source
*src
;
1606 struct ipcp_value
*val
;
1607 int time
= 0, size
= 0;
1609 for (val
= base
; val
; val
= val
->scc_next
)
1611 time
= safe_add (time
,
1612 val
->local_time_benefit
+ val
->prop_time_benefit
);
1613 size
= safe_add (size
, val
->local_size_cost
+ val
->prop_size_cost
);
1616 for (val
= base
; val
; val
= val
->scc_next
)
1617 for (src
= val
->sources
; src
; src
= src
->next
)
1619 && cgraph_maybe_hot_edge_p (src
->cs
))
1621 src
->val
->prop_time_benefit
= safe_add (time
,
1622 src
->val
->prop_time_benefit
);
1623 src
->val
->prop_size_cost
= safe_add (size
,
1624 src
->val
->prop_size_cost
);
1630 /* Propagate constants, binfos and their effects from the summaries
1631 interprocedurally. */
1634 ipcp_propagate_stage (struct topo_info
*topo
)
1636 struct cgraph_node
*node
;
1639 fprintf (dump_file
, "\n Propagating constants:\n\n");
1642 ipa_update_after_lto_read ();
1645 FOR_EACH_DEFINED_FUNCTION (node
)
1647 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1649 determine_versionability (node
);
1650 if (cgraph_function_with_gimple_body_p (node
))
1652 info
->lattices
= XCNEWVEC (struct ipcp_lattice
,
1653 ipa_get_param_count (info
));
1654 initialize_node_lattices (node
);
1656 if (node
->count
> max_count
)
1657 max_count
= node
->count
;
1658 overall_size
+= inline_summary (node
)->self_size
;
1661 max_new_size
= overall_size
;
1662 if (max_new_size
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
1663 max_new_size
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
1664 max_new_size
+= max_new_size
* PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH
) / 100 + 1;
1667 fprintf (dump_file
, "\noverall_size: %li, max_new_size: %li\n",
1668 overall_size
, max_new_size
);
1670 propagate_constants_topo (topo
);
1671 #ifdef ENABLE_CHECKING
1672 ipcp_verify_propagated_values ();
1674 propagate_effects ();
1678 fprintf (dump_file
, "\nIPA lattices after all propagation:\n");
1679 print_all_lattices (dump_file
, (dump_flags
& TDF_DETAILS
), true);
1683 /* Discover newly direct outgoing edges from NODE which is a new clone with
1684 known KNOWN_VALS and make them direct. */
1687 ipcp_discover_new_direct_edges (struct cgraph_node
*node
,
1688 VEC (tree
, heap
) *known_vals
)
1690 struct cgraph_edge
*ie
, *next_ie
;
1693 for (ie
= node
->indirect_calls
; ie
; ie
= next_ie
)
1697 next_ie
= ie
->next_callee
;
1698 target
= ipa_get_indirect_edge_target (ie
, known_vals
, NULL
, NULL
);
1701 ipa_make_edge_direct_to_target (ie
, target
);
1705 /* Turning calls to direct calls will improve overall summary. */
1707 inline_update_overall_summary (node
);
1710 /* Vector of pointers which for linked lists of clones of an original crgaph
1713 static VEC (cgraph_edge_p
, heap
) *next_edge_clone
;
1716 grow_next_edge_clone_vector (void)
1718 if (VEC_length (cgraph_edge_p
, next_edge_clone
)
1719 <= (unsigned) cgraph_edge_max_uid
)
1720 VEC_safe_grow_cleared (cgraph_edge_p
, heap
, next_edge_clone
,
1721 cgraph_edge_max_uid
+ 1);
1724 /* Edge duplication hook to grow the appropriate linked list in
1728 ipcp_edge_duplication_hook (struct cgraph_edge
*src
, struct cgraph_edge
*dst
,
1729 __attribute__((unused
)) void *data
)
1731 grow_next_edge_clone_vector ();
1732 VEC_replace (cgraph_edge_p
, next_edge_clone
, dst
->uid
,
1733 VEC_index (cgraph_edge_p
, next_edge_clone
, src
->uid
));
1734 VEC_replace (cgraph_edge_p
, next_edge_clone
, src
->uid
, dst
);
1737 /* Get the next clone in the linked list of clones of an edge. */
1739 static inline struct cgraph_edge
*
1740 get_next_cgraph_edge_clone (struct cgraph_edge
*cs
)
1742 return VEC_index (cgraph_edge_p
, next_edge_clone
, cs
->uid
);
1745 /* Return true if edge CS does bring about the value described by SRC. */
1748 cgraph_edge_brings_value_p (struct cgraph_edge
*cs
,
1749 struct ipcp_value_source
*src
)
1751 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1753 if (IPA_NODE_REF (cs
->callee
)->ipcp_orig_node
1754 || caller_info
->node_dead
)
1759 if (caller_info
->ipcp_orig_node
)
1761 tree t
= VEC_index (tree
, caller_info
->known_vals
, src
->index
);
1762 return (t
!= NULL_TREE
1763 && values_equal_for_ipcp_p (src
->val
->value
, t
));
1767 struct ipcp_lattice
*lat
= ipa_get_lattice (caller_info
, src
->index
);
1768 if (ipa_lat_is_single_const (lat
)
1769 && values_equal_for_ipcp_p (src
->val
->value
, lat
->values
->value
))
1776 /* Given VAL, iterate over all its sources and if they still hold, add their
1777 edge frequency and their number into *FREQUENCY and *CALLER_COUNT
1781 get_info_about_necessary_edges (struct ipcp_value
*val
, int *freq_sum
,
1782 gcov_type
*count_sum
, int *caller_count
)
1784 struct ipcp_value_source
*src
;
1785 int freq
= 0, count
= 0;
1789 for (src
= val
->sources
; src
; src
= src
->next
)
1791 struct cgraph_edge
*cs
= src
->cs
;
1794 if (cgraph_edge_brings_value_p (cs
, src
))
1797 freq
+= cs
->frequency
;
1799 hot
|= cgraph_maybe_hot_edge_p (cs
);
1801 cs
= get_next_cgraph_edge_clone (cs
);
1807 *caller_count
= count
;
1811 /* Return a vector of incoming edges that do bring value VAL. It is assumed
1812 their number is known and equal to CALLER_COUNT. */
1814 static VEC (cgraph_edge_p
,heap
) *
1815 gather_edges_for_value (struct ipcp_value
*val
, int caller_count
)
1817 struct ipcp_value_source
*src
;
1818 VEC (cgraph_edge_p
,heap
) *ret
;
1820 ret
= VEC_alloc (cgraph_edge_p
, heap
, caller_count
);
1821 for (src
= val
->sources
; src
; src
= src
->next
)
1823 struct cgraph_edge
*cs
= src
->cs
;
1826 if (cgraph_edge_brings_value_p (cs
, src
))
1827 VEC_quick_push (cgraph_edge_p
, ret
, cs
);
1828 cs
= get_next_cgraph_edge_clone (cs
);
1835 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
1836 Return it or NULL if for some reason it cannot be created. */
1838 static struct ipa_replace_map
*
1839 get_replacement_map (tree value
, tree parm
)
1841 tree req_type
= TREE_TYPE (parm
);
1842 struct ipa_replace_map
*replace_map
;
1844 if (!useless_type_conversion_p (req_type
, TREE_TYPE (value
)))
1846 if (fold_convertible_p (req_type
, value
))
1847 value
= fold_build1 (NOP_EXPR
, req_type
, value
);
1848 else if (TYPE_SIZE (req_type
) == TYPE_SIZE (TREE_TYPE (value
)))
1849 value
= fold_build1 (VIEW_CONVERT_EXPR
, req_type
, value
);
1854 fprintf (dump_file
, " const ");
1855 print_generic_expr (dump_file
, value
, 0);
1856 fprintf (dump_file
, " can't be converted to param ");
1857 print_generic_expr (dump_file
, parm
, 0);
1858 fprintf (dump_file
, "\n");
1864 replace_map
= ggc_alloc_ipa_replace_map ();
1867 fprintf (dump_file
, " replacing param ");
1868 print_generic_expr (dump_file
, parm
, 0);
1869 fprintf (dump_file
, " with const ");
1870 print_generic_expr (dump_file
, value
, 0);
1871 fprintf (dump_file
, "\n");
1873 replace_map
->old_tree
= parm
;
1874 replace_map
->new_tree
= value
;
1875 replace_map
->replace_p
= true;
1876 replace_map
->ref_p
= false;
1881 /* Dump new profiling counts */
1884 dump_profile_updates (struct cgraph_node
*orig_node
,
1885 struct cgraph_node
*new_node
)
1887 struct cgraph_edge
*cs
;
1889 fprintf (dump_file
, " setting count of the specialized node to "
1890 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) new_node
->count
);
1891 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
1892 fprintf (dump_file
, " edge to %s has count "
1893 HOST_WIDE_INT_PRINT_DEC
"\n",
1894 cgraph_node_name (cs
->callee
), (HOST_WIDE_INT
) cs
->count
);
1896 fprintf (dump_file
, " setting count of the original node to "
1897 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) orig_node
->count
);
1898 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
1899 fprintf (dump_file
, " edge to %s is left with "
1900 HOST_WIDE_INT_PRINT_DEC
"\n",
1901 cgraph_node_name (cs
->callee
), (HOST_WIDE_INT
) cs
->count
);
1904 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
1905 their profile information to reflect this. */
1908 update_profiling_info (struct cgraph_node
*orig_node
,
1909 struct cgraph_node
*new_node
)
1911 struct cgraph_edge
*cs
;
1912 struct caller_statistics stats
;
1913 gcov_type new_sum
, orig_sum
;
1914 gcov_type remainder
, orig_node_count
= orig_node
->count
;
1916 if (orig_node_count
== 0)
1919 init_caller_stats (&stats
);
1920 cgraph_for_node_and_aliases (orig_node
, gather_caller_stats
, &stats
, false);
1921 orig_sum
= stats
.count_sum
;
1922 init_caller_stats (&stats
);
1923 cgraph_for_node_and_aliases (new_node
, gather_caller_stats
, &stats
, false);
1924 new_sum
= stats
.count_sum
;
1926 if (orig_node_count
< orig_sum
+ new_sum
)
1929 fprintf (dump_file
, " Problem: node %s/%i has too low count "
1930 HOST_WIDE_INT_PRINT_DEC
" while the sum of incoming "
1931 "counts is " HOST_WIDE_INT_PRINT_DEC
"\n",
1932 cgraph_node_name (orig_node
), orig_node
->uid
,
1933 (HOST_WIDE_INT
) orig_node_count
,
1934 (HOST_WIDE_INT
) (orig_sum
+ new_sum
));
1936 orig_node_count
= (orig_sum
+ new_sum
) * 12 / 10;
1938 fprintf (dump_file
, " proceeding by pretending it was "
1939 HOST_WIDE_INT_PRINT_DEC
"\n",
1940 (HOST_WIDE_INT
) orig_node_count
);
1943 new_node
->count
= new_sum
;
1944 remainder
= orig_node_count
- new_sum
;
1945 orig_node
->count
= remainder
;
1947 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
1949 cs
->count
= cs
->count
* (new_sum
* REG_BR_PROB_BASE
1950 / orig_node_count
) / REG_BR_PROB_BASE
;
1954 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
1955 cs
->count
= cs
->count
* (remainder
* REG_BR_PROB_BASE
1956 / orig_node_count
) / REG_BR_PROB_BASE
;
1959 dump_profile_updates (orig_node
, new_node
);
1962 /* Update the respective profile of specialized NEW_NODE and the original
1963 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
1964 have been redirected to the specialized version. */
1967 update_specialized_profile (struct cgraph_node
*new_node
,
1968 struct cgraph_node
*orig_node
,
1969 gcov_type redirected_sum
)
1971 struct cgraph_edge
*cs
;
1972 gcov_type new_node_count
, orig_node_count
= orig_node
->count
;
1975 fprintf (dump_file
, " the sum of counts of redirected edges is "
1976 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) redirected_sum
);
1977 if (orig_node_count
== 0)
1980 gcc_assert (orig_node_count
>= redirected_sum
);
1982 new_node_count
= new_node
->count
;
1983 new_node
->count
+= redirected_sum
;
1984 orig_node
->count
-= redirected_sum
;
1986 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
1988 cs
->count
+= cs
->count
* redirected_sum
/ new_node_count
;
1992 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
1994 gcov_type dec
= cs
->count
* (redirected_sum
* REG_BR_PROB_BASE
1995 / orig_node_count
) / REG_BR_PROB_BASE
;
1996 if (dec
< cs
->count
)
2003 dump_profile_updates (orig_node
, new_node
);
2006 /* Create a specialized version of NODE with known constants and types of
2007 parameters in KNOWN_VALS and redirect all edges in CALLERS to it. */
2009 static struct cgraph_node
*
2010 create_specialized_node (struct cgraph_node
*node
,
2011 VEC (tree
, heap
) *known_vals
,
2012 VEC (cgraph_edge_p
,heap
) *callers
)
2014 struct ipa_node_params
*new_info
, *info
= IPA_NODE_REF (node
);
2015 VEC (ipa_replace_map_p
,gc
)* replace_trees
= NULL
;
2016 struct cgraph_node
*new_node
;
2017 int i
, count
= ipa_get_param_count (info
);
2018 bitmap args_to_skip
;
2020 gcc_assert (!info
->ipcp_orig_node
);
2022 if (node
->local
.can_change_signature
)
2024 args_to_skip
= BITMAP_GGC_ALLOC ();
2025 for (i
= 0; i
< count
; i
++)
2027 tree t
= VEC_index (tree
, known_vals
, i
);
2029 if ((t
&& TREE_CODE (t
) != TREE_BINFO
)
2030 || !ipa_is_param_used (info
, i
))
2031 bitmap_set_bit (args_to_skip
, i
);
2036 args_to_skip
= NULL
;
2037 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2038 fprintf (dump_file
, " cannot change function signature\n");
2041 for (i
= 0; i
< count
; i
++)
2043 tree t
= VEC_index (tree
, known_vals
, i
);
2044 if (t
&& TREE_CODE (t
) != TREE_BINFO
)
2046 struct ipa_replace_map
*replace_map
;
2048 replace_map
= get_replacement_map (t
, ipa_get_param (info
, i
));
2050 VEC_safe_push (ipa_replace_map_p
, gc
, replace_trees
, replace_map
);
2054 new_node
= cgraph_create_virtual_clone (node
, callers
, replace_trees
,
2055 args_to_skip
, "constprop");
2056 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2057 fprintf (dump_file
, " the new node is %s/%i.\n",
2058 cgraph_node_name (new_node
), new_node
->uid
);
2059 gcc_checking_assert (ipa_node_params_vector
2060 && (VEC_length (ipa_node_params_t
,
2061 ipa_node_params_vector
)
2062 > (unsigned) cgraph_max_uid
));
2063 update_profiling_info (node
, new_node
);
2064 new_info
= IPA_NODE_REF (new_node
);
2065 new_info
->ipcp_orig_node
= node
;
2066 new_info
->known_vals
= known_vals
;
2068 ipcp_discover_new_direct_edges (new_node
, known_vals
);
2070 VEC_free (cgraph_edge_p
, heap
, callers
);
2074 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
2075 KNOWN_VALS with constants and types that are also known for all of the
2079 find_more_values_for_callers_subset (struct cgraph_node
*node
,
2080 VEC (tree
, heap
) *known_vals
,
2081 VEC (cgraph_edge_p
,heap
) *callers
)
2083 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2084 int i
, count
= ipa_get_param_count (info
);
2086 for (i
= 0; i
< count
; i
++)
2088 struct cgraph_edge
*cs
;
2089 tree newval
= NULL_TREE
;
2092 if (ipa_get_lattice (info
, i
)->bottom
2093 || VEC_index (tree
, known_vals
, i
))
2096 FOR_EACH_VEC_ELT (cgraph_edge_p
, callers
, j
, cs
)
2098 struct ipa_jump_func
*jump_func
;
2101 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
)))
2106 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
2107 t
= ipa_value_from_jfunc (IPA_NODE_REF (cs
->caller
), jump_func
);
2110 && !values_equal_for_ipcp_p (t
, newval
)))
2121 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2123 fprintf (dump_file
, " adding an extra known value ");
2124 print_ipcp_constant_value (dump_file
, newval
);
2125 fprintf (dump_file
, " for parameter ");
2126 print_generic_expr (dump_file
, ipa_get_param (info
, i
), 0);
2127 fprintf (dump_file
, "\n");
2130 VEC_replace (tree
, known_vals
, i
, newval
);
2135 /* Given an original NODE and a VAL for which we have already created a
2136 specialized clone, look whether there are incoming edges that still lead
2137 into the old node but now also bring the requested value and also conform to
2138 all other criteria such that they can be redirected the the special node.
2139 This function can therefore redirect the final edge in a SCC. */
2142 perhaps_add_new_callers (struct cgraph_node
*node
, struct ipcp_value
*val
)
2144 struct ipa_node_params
*dest_info
= IPA_NODE_REF (val
->spec_node
);
2145 struct ipcp_value_source
*src
;
2146 int count
= ipa_get_param_count (dest_info
);
2147 gcov_type redirected_sum
= 0;
2149 for (src
= val
->sources
; src
; src
= src
->next
)
2151 struct cgraph_edge
*cs
= src
->cs
;
2154 enum availability availability
;
2155 bool insufficient
= false;
2157 if (cgraph_function_node (cs
->callee
, &availability
) == node
2158 && availability
> AVAIL_OVERWRITABLE
2159 && cgraph_edge_brings_value_p (cs
, src
))
2161 struct ipa_node_params
*caller_info
;
2162 struct ipa_edge_args
*args
;
2165 caller_info
= IPA_NODE_REF (cs
->caller
);
2166 args
= IPA_EDGE_REF (cs
);
2167 for (i
= 0; i
< count
; i
++)
2169 struct ipa_jump_func
*jump_func
;
2172 val
= VEC_index (tree
, dest_info
->known_vals
, i
);
2176 if (i
>= ipa_get_cs_argument_count (args
))
2178 insufficient
= true;
2181 jump_func
= ipa_get_ith_jump_func (args
, i
);
2182 t
= ipa_value_from_jfunc (caller_info
, jump_func
);
2183 if (!t
|| !values_equal_for_ipcp_p (val
, t
))
2185 insufficient
= true;
2193 fprintf (dump_file
, " - adding an extra caller %s/%i"
2195 xstrdup (cgraph_node_name (cs
->caller
)),
2197 xstrdup (cgraph_node_name (val
->spec_node
)),
2198 val
->spec_node
->uid
);
2200 cgraph_redirect_edge_callee (cs
, val
->spec_node
);
2201 redirected_sum
+= cs
->count
;
2204 cs
= get_next_cgraph_edge_clone (cs
);
2209 update_specialized_profile (val
->spec_node
, node
, redirected_sum
);
2213 /* Copy KNOWN_BINFOS to KNOWN_VALS. */
2216 move_binfos_to_values (VEC (tree
, heap
) *known_vals
,
2217 VEC (tree
, heap
) *known_binfos
)
2222 for (i
= 0; VEC_iterate (tree
, known_binfos
, i
, t
); i
++)
2224 VEC_replace (tree
, known_vals
, i
, t
);
2228 /* Decide whether and what specialized clones of NODE should be created. */
2231 decide_whether_version_node (struct cgraph_node
*node
)
2233 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2234 int i
, count
= ipa_get_param_count (info
);
2235 VEC (tree
, heap
) *known_csts
, *known_binfos
;
2241 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2242 fprintf (dump_file
, "\nEvaluating opportunities for %s/%i.\n",
2243 cgraph_node_name (node
), node
->uid
);
2245 gather_context_independent_values (info
, &known_csts
, &known_binfos
,
2248 for (i
= 0; i
< count
; i
++)
2250 struct ipcp_lattice
*lat
= ipa_get_lattice (info
, i
);
2251 struct ipcp_value
*val
;
2254 || VEC_index (tree
, known_csts
, i
)
2255 || VEC_index (tree
, known_binfos
, i
))
2258 for (val
= lat
->values
; val
; val
= val
->next
)
2260 int freq_sum
, caller_count
;
2261 gcov_type count_sum
;
2262 VEC (cgraph_edge_p
, heap
) *callers
;
2263 VEC (tree
, heap
) *kv
;
2267 perhaps_add_new_callers (node
, val
);
2270 else if (val
->local_size_cost
+ overall_size
> max_new_size
)
2272 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2273 fprintf (dump_file
, " Ignoring candidate value because "
2274 "max_new_size would be reached with %li.\n",
2275 val
->local_size_cost
+ overall_size
);
2278 else if (!get_info_about_necessary_edges (val
, &freq_sum
, &count_sum
,
2282 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2284 fprintf (dump_file
, " - considering value ");
2285 print_ipcp_constant_value (dump_file
, val
->value
);
2286 fprintf (dump_file
, " for parameter ");
2287 print_generic_expr (dump_file
, ipa_get_param (info
, i
), 0);
2288 fprintf (dump_file
, " (caller_count: %i)\n", caller_count
);
2292 if (!good_cloning_opportunity_p (node
, val
->local_time_benefit
,
2293 freq_sum
, count_sum
,
2294 val
->local_size_cost
)
2295 && !good_cloning_opportunity_p (node
,
2296 val
->local_time_benefit
2297 + val
->prop_time_benefit
,
2298 freq_sum
, count_sum
,
2299 val
->local_size_cost
2300 + val
->prop_size_cost
))
2304 fprintf (dump_file
, " Creating a specialized node of %s/%i.\n",
2305 cgraph_node_name (node
), node
->uid
);
2307 callers
= gather_edges_for_value (val
, caller_count
);
2308 kv
= VEC_copy (tree
, heap
, known_csts
);
2309 move_binfos_to_values (kv
, known_binfos
);
2310 VEC_replace (tree
, kv
, i
, val
->value
);
2311 find_more_values_for_callers_subset (node
, kv
, callers
);
2312 val
->spec_node
= create_specialized_node (node
, kv
, callers
);
2313 overall_size
+= val
->local_size_cost
;
2314 info
= IPA_NODE_REF (node
);
2316 /* TODO: If for some lattice there is only one other known value
2317 left, make a special node for it too. */
2320 VEC_replace (tree
, kv
, i
, val
->value
);
2324 if (info
->clone_for_all_contexts
)
2326 VEC (cgraph_edge_p
, heap
) *callers
;
2329 fprintf (dump_file
, " - Creating a specialized node of %s/%i "
2330 "for all known contexts.\n", cgraph_node_name (node
),
2333 callers
= collect_callers_of_node (node
);
2334 move_binfos_to_values (known_csts
, known_binfos
);
2335 create_specialized_node (node
, known_csts
, callers
);
2336 info
= IPA_NODE_REF (node
);
2337 info
->clone_for_all_contexts
= false;
2341 VEC_free (tree
, heap
, known_csts
);
2343 VEC_free (tree
, heap
, known_binfos
);
2347 /* Transitively mark all callees of NODE within the same SCC as not dead. */
2350 spread_undeadness (struct cgraph_node
*node
)
2352 struct cgraph_edge
*cs
;
2354 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
2355 if (edge_within_scc (cs
))
2357 struct cgraph_node
*callee
;
2358 struct ipa_node_params
*info
;
2360 callee
= cgraph_function_node (cs
->callee
, NULL
);
2361 info
= IPA_NODE_REF (callee
);
2363 if (info
->node_dead
)
2365 info
->node_dead
= 0;
2366 spread_undeadness (callee
);
2371 /* Return true if NODE has a caller from outside of its SCC that is not
2372 dead. Worker callback for cgraph_for_node_and_aliases. */
2375 has_undead_caller_from_outside_scc_p (struct cgraph_node
*node
,
2376 void *data ATTRIBUTE_UNUSED
)
2378 struct cgraph_edge
*cs
;
2380 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
2381 if (cs
->caller
->thunk
.thunk_p
2382 && cgraph_for_node_and_aliases (cs
->caller
,
2383 has_undead_caller_from_outside_scc_p
,
2386 else if (!edge_within_scc (cs
)
2387 && !IPA_NODE_REF (cs
->caller
)->node_dead
)
2393 /* Identify nodes within the same SCC as NODE which are no longer needed
2394 because of new clones and will be removed as unreachable. */
2397 identify_dead_nodes (struct cgraph_node
*node
)
2399 struct cgraph_node
*v
;
2400 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->symbol
.aux
)->next_cycle
)
2401 if (cgraph_will_be_removed_from_program_if_no_direct_calls (v
)
2402 && !cgraph_for_node_and_aliases (v
,
2403 has_undead_caller_from_outside_scc_p
,
2405 IPA_NODE_REF (v
)->node_dead
= 1;
2407 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->symbol
.aux
)->next_cycle
)
2408 if (!IPA_NODE_REF (v
)->node_dead
)
2409 spread_undeadness (v
);
2411 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2413 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->symbol
.aux
)->next_cycle
)
2414 if (IPA_NODE_REF (v
)->node_dead
)
2415 fprintf (dump_file
, " Marking node as dead: %s/%i.\n",
2416 cgraph_node_name (v
), v
->uid
);
2420 /* The decision stage. Iterate over the topological order of call graph nodes
2421 TOPO and make specialized clones if deemed beneficial. */
2424 ipcp_decision_stage (struct topo_info
*topo
)
2429 fprintf (dump_file
, "\nIPA decision stage:\n\n");
2431 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
2433 struct cgraph_node
*node
= topo
->order
[i
];
2434 bool change
= false, iterate
= true;
2438 struct cgraph_node
*v
;
2440 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->symbol
.aux
)->next_cycle
)
2441 if (cgraph_function_with_gimple_body_p (v
)
2442 && ipcp_versionable_function_p (v
))
2443 iterate
|= decide_whether_version_node (v
);
2448 identify_dead_nodes (node
);
2452 /* The IPCP driver. */
2457 struct cgraph_2edge_hook_list
*edge_duplication_hook_holder
;
2458 struct topo_info topo
;
2460 ipa_check_create_node_params ();
2461 ipa_check_create_edge_args ();
2462 grow_next_edge_clone_vector ();
2463 edge_duplication_hook_holder
=
2464 cgraph_add_edge_duplication_hook (&ipcp_edge_duplication_hook
, NULL
);
2465 ipcp_values_pool
= create_alloc_pool ("IPA-CP values",
2466 sizeof (struct ipcp_value
), 32);
2467 ipcp_sources_pool
= create_alloc_pool ("IPA-CP value sources",
2468 sizeof (struct ipcp_value_source
), 64);
2471 fprintf (dump_file
, "\nIPA structures before propagation:\n");
2472 if (dump_flags
& TDF_DETAILS
)
2473 ipa_print_all_params (dump_file
);
2474 ipa_print_all_jump_functions (dump_file
);
2477 /* Topological sort. */
2478 build_toporder_info (&topo
);
2479 /* Do the interprocedural propagation. */
2480 ipcp_propagate_stage (&topo
);
2481 /* Decide what constant propagation and cloning should be performed. */
2482 ipcp_decision_stage (&topo
);
2484 /* Free all IPCP structures. */
2485 free_toporder_info (&topo
);
2486 VEC_free (cgraph_edge_p
, heap
, next_edge_clone
);
2487 cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder
);
2488 ipa_free_all_structures_after_ipa_cp ();
2490 fprintf (dump_file
, "\nIPA constant propagation end\n");
2494 /* Initialization and computation of IPCP data structures. This is the initial
2495 intraprocedural analysis of functions, which gathers information to be
2496 propagated later on. */
2499 ipcp_generate_summary (void)
2501 struct cgraph_node
*node
;
2504 fprintf (dump_file
, "\nIPA constant propagation start:\n");
2505 ipa_register_cgraph_hooks ();
2507 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
2509 node
->local
.versionable
2510 = tree_versionable_function_p (node
->symbol
.decl
);
2511 ipa_analyze_node (node
);
2515 /* Write ipcp summary for nodes in SET. */
2518 ipcp_write_summary (void)
2520 ipa_prop_write_jump_functions ();
2523 /* Read ipcp summary. */
2526 ipcp_read_summary (void)
2528 ipa_prop_read_jump_functions ();
2531 /* Gate for IPCP optimization. */
2534 cgraph_gate_cp (void)
2536 /* FIXME: We should remove the optimize check after we ensure we never run
2537 IPA passes when not optimizing. */
2538 return flag_ipa_cp
&& optimize
;
2541 struct ipa_opt_pass_d pass_ipa_cp
=
2546 OPTGROUP_NONE
, /* optinfo_flags */
2547 cgraph_gate_cp
, /* gate */
2548 ipcp_driver
, /* execute */
2551 0, /* static_pass_number */
2552 TV_IPA_CONSTANT_PROP
, /* tv_id */
2553 0, /* properties_required */
2554 0, /* properties_provided */
2555 0, /* properties_destroyed */
2556 0, /* todo_flags_start */
2558 TODO_remove_functions
| TODO_ggc_collect
/* todo_flags_finish */
2560 ipcp_generate_summary
, /* generate_summary */
2561 ipcp_write_summary
, /* write_summary */
2562 ipcp_read_summary
, /* read_summary */
2563 NULL
, /* write_optimization_summary */
2564 NULL
, /* read_optimization_summary */
2565 NULL
, /* stmt_fixup */
2567 NULL
, /* function_transform */
2568 NULL
, /* variable_transform */