1 /* Interprocedural constant propagation
2 Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011
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 dependant 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"
116 #include "diagnostic.h"
117 #include "tree-pretty-print.h"
118 #include "tree-dump.h"
119 #include "tree-inline.h"
122 #include "ipa-inline.h"
123 #include "ipa-utils.h"
127 /* Describes a particular source for an IPA-CP value. */
129 struct ipcp_value_source
131 /* The incoming edge that brought the value. */
132 struct cgraph_edge
*cs
;
133 /* If the jump function that resulted into his value was a pass-through or an
134 ancestor, this is the ipcp_value of the caller from which the described
135 value has been derived. Otherwise it is NULL. */
136 struct ipcp_value
*val
;
137 /* Next pointer in a linked list of sources of a value. */
138 struct ipcp_value_source
*next
;
139 /* If the jump function that resulted into his value was a pass-through or an
140 ancestor, this is the index of the parameter of the caller the jump
141 function references. */
145 /* Describes one particular value stored in struct ipcp_lattice. */
149 /* The actual value for the given parameter. This is either an IPA invariant
150 or a TREE_BINFO describing a type that can be used for
153 /* The list of sources from which this value originates. */
154 struct ipcp_value_source
*sources
;
155 /* Next pointers in a linked list of all values in a lattice. */
156 struct ipcp_value
*next
;
157 /* Next pointers in a linked list of values in a strongly connected component
159 struct ipcp_value
*scc_next
;
160 /* Next pointers in a linked list of SCCs of values sorted topologically
161 according their sources. */
162 struct ipcp_value
*topo_next
;
163 /* A specialized node created for this value, NULL if none has been (so far)
165 struct cgraph_node
*spec_node
;
166 /* Depth first search number and low link for topological sorting of
169 /* Time benefit and size cost that specializing the function for this value
170 would bring about in this function alone. */
171 int local_time_benefit
, local_size_cost
;
172 /* Time benefit and size cost that specializing the function for this value
173 can bring about in it's callees (transitively). */
174 int prop_time_benefit
, prop_size_cost
;
175 /* True if this valye is currently on the topo-sort stack. */
179 /* Allocation pools for values and their sources in ipa-cp. */
181 alloc_pool ipcp_values_pool
;
182 alloc_pool ipcp_sources_pool
;
184 /* Lattice describing potential values of a formal parameter of a function and
185 some of their other properties. TOP is represented by a lattice with zero
186 values and with contains_variable and bottom flags cleared. BOTTOM is
187 represented by a lattice with the bottom flag set. In that case, values and
188 contains_variable flag should be disregarded. */
192 /* The list of known values and types in this lattice. Note that values are
193 not deallocated if a lattice is set to bottom because there may be value
194 sources referencing them. */
195 struct ipcp_value
*values
;
196 /* Number of known values and types in this lattice. */
198 /* The lattice contains a variable component (in addition to values). */
199 bool contains_variable
;
200 /* The value of the lattice is bottom (i.e. variable and unusable for any
203 /* There is a virtual call based on this parameter. */
207 /* Maximal count found in program. */
209 static gcov_type max_count
;
211 /* Original overall size of the program. */
213 static long overall_size
, max_new_size
;
215 /* Head of the linked list of topologically sorted values. */
217 static struct ipcp_value
*values_topo
;
219 /* Return the lattice corresponding to the Ith formal parameter of the function
220 described by INFO. */
221 static inline struct ipcp_lattice
*
222 ipa_get_lattice (struct ipa_node_params
*info
, int i
)
224 gcc_assert (i
>= 0 && i
< ipa_get_param_count (info
));
225 gcc_checking_assert (!info
->ipcp_orig_node
);
226 gcc_checking_assert (info
->lattices
);
227 return &(info
->lattices
[i
]);
230 /* Return whether LAT is a lattice with a single constant and without an
234 ipa_lat_is_single_const (struct ipcp_lattice
*lat
)
237 || lat
->contains_variable
238 || lat
->values_count
!= 1)
244 /* Return true iff the CS is an edge within a strongly connected component as
245 computed by ipa_reduced_postorder. */
248 edge_within_scc (struct cgraph_edge
*cs
)
250 struct ipa_dfs_info
*caller_dfs
= (struct ipa_dfs_info
*) cs
->caller
->aux
;
251 struct ipa_dfs_info
*callee_dfs
;
252 struct cgraph_node
*callee
= cgraph_function_node (cs
->callee
, NULL
);
254 callee_dfs
= (struct ipa_dfs_info
*) callee
->aux
;
257 && caller_dfs
->scc_no
== callee_dfs
->scc_no
);
260 /* Print V which is extracted from a value in a lattice to F. */
263 print_ipcp_constant_value (FILE * f
, tree v
)
265 if (TREE_CODE (v
) == TREE_BINFO
)
267 fprintf (f
, "BINFO ");
268 print_generic_expr (f
, BINFO_TYPE (v
), 0);
270 else if (TREE_CODE (v
) == ADDR_EXPR
271 && TREE_CODE (TREE_OPERAND (v
, 0)) == CONST_DECL
)
274 print_generic_expr (f
, DECL_INITIAL (TREE_OPERAND (v
, 0)), 0);
277 print_generic_expr (f
, v
, 0);
280 /* Print all ipcp_lattices of all functions to F. */
283 print_all_lattices (FILE * f
, bool dump_sources
, bool dump_benefits
)
285 struct cgraph_node
*node
;
288 fprintf (f
, "\nLattices:\n");
289 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
291 struct ipa_node_params
*info
;
293 info
= IPA_NODE_REF (node
);
294 fprintf (f
, " Node: %s/%i:\n", cgraph_node_name (node
), node
->uid
);
295 count
= ipa_get_param_count (info
);
296 for (i
= 0; i
< count
; i
++)
298 struct ipcp_lattice
*lat
= ipa_get_lattice (info
, i
);
299 struct ipcp_value
*val
;
302 fprintf (f
, " param [%d]: ", i
);
305 fprintf (f
, "BOTTOM\n");
309 if (!lat
->values_count
&& !lat
->contains_variable
)
311 fprintf (f
, "TOP\n");
315 if (lat
->contains_variable
)
317 fprintf (f
, "VARIABLE");
323 for (val
= lat
->values
; val
; val
= val
->next
)
325 if (dump_benefits
&& prev
)
327 else if (!dump_benefits
&& prev
)
332 print_ipcp_constant_value (f
, val
->value
);
336 struct ipcp_value_source
*s
;
338 fprintf (f
, " [from:");
339 for (s
= val
->sources
; s
; s
= s
->next
)
340 fprintf (f
, " %i(%i)", s
->cs
->caller
->uid
,s
->cs
->frequency
);
345 fprintf (f
, " [loc_time: %i, loc_size: %i, "
346 "prop_time: %i, prop_size: %i]\n",
347 val
->local_time_benefit
, val
->local_size_cost
,
348 val
->prop_time_benefit
, val
->prop_size_cost
);
356 /* Determine whether it is at all technically possible to create clones of NODE
357 and store this information in the ipa_node_params structure associated
361 determine_versionability (struct cgraph_node
*node
)
363 const char *reason
= NULL
;
365 /* There are a number of generic reasons functions cannot be versioned. We
366 also cannot remove parameters if there are type attributes such as fnspec
368 if (node
->alias
|| node
->thunk
.thunk_p
)
369 reason
= "alias or thunk";
370 else if (!node
->local
.versionable
)
371 reason
= "not a tree_versionable_function";
372 else if (cgraph_function_body_availability (node
) <= AVAIL_OVERWRITABLE
)
373 reason
= "insufficient body availability";
375 if (reason
&& dump_file
&& !node
->alias
&& !node
->thunk
.thunk_p
)
376 fprintf (dump_file
, "Function %s/%i is not versionable, reason: %s.\n",
377 cgraph_node_name (node
), node
->uid
, reason
);
379 node
->local
.versionable
= (reason
== NULL
);
382 /* Return true if it is at all technically possible to create clones of a
386 ipcp_versionable_function_p (struct cgraph_node
*node
)
388 return node
->local
.versionable
;
391 /* Structure holding accumulated information about callers of a node. */
393 struct caller_statistics
396 int n_calls
, n_hot_calls
, freq_sum
;
399 /* Initialize fields of STAT to zeroes. */
402 init_caller_stats (struct caller_statistics
*stats
)
404 stats
->count_sum
= 0;
406 stats
->n_hot_calls
= 0;
410 /* Worker callback of cgraph_for_node_and_aliases accumulating statistics of
411 non-thunk incoming edges to NODE. */
414 gather_caller_stats (struct cgraph_node
*node
, void *data
)
416 struct caller_statistics
*stats
= (struct caller_statistics
*) data
;
417 struct cgraph_edge
*cs
;
419 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
420 if (cs
->caller
->thunk
.thunk_p
)
421 cgraph_for_node_and_aliases (cs
->caller
, gather_caller_stats
,
425 stats
->count_sum
+= cs
->count
;
426 stats
->freq_sum
+= cs
->frequency
;
428 if (cgraph_maybe_hot_edge_p (cs
))
429 stats
->n_hot_calls
++;
435 /* Return true if this NODE is viable candidate for cloning. */
438 ipcp_cloning_candidate_p (struct cgraph_node
*node
)
440 struct caller_statistics stats
;
442 gcc_checking_assert (cgraph_function_with_gimple_body_p (node
));
444 if (!flag_ipa_cp_clone
)
447 fprintf (dump_file
, "Not considering %s for cloning; "
448 "-fipa-cp-clone disabled.\n",
449 cgraph_node_name (node
));
453 if (!optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node
->decl
)))
456 fprintf (dump_file
, "Not considering %s for cloning; "
457 "optimizing it for size.\n",
458 cgraph_node_name (node
));
462 init_caller_stats (&stats
);
463 cgraph_for_node_and_aliases (node
, gather_caller_stats
, &stats
, false);
465 if (inline_summary (node
)->self_size
< stats
.n_calls
)
468 fprintf (dump_file
, "Considering %s for cloning; code might shrink.\n",
469 cgraph_node_name (node
));
473 /* When profile is available and function is hot, propagate into it even if
474 calls seems cold; constant propagation can improve function's speed
478 if (stats
.count_sum
> node
->count
* 90 / 100)
481 fprintf (dump_file
, "Considering %s for cloning; "
482 "usually called directly.\n",
483 cgraph_node_name (node
));
487 if (!stats
.n_hot_calls
)
490 fprintf (dump_file
, "Not considering %s for cloning; no hot calls.\n",
491 cgraph_node_name (node
));
495 fprintf (dump_file
, "Considering %s for cloning.\n",
496 cgraph_node_name (node
));
500 /* Arrays representing a topological ordering of call graph nodes and a stack
501 of noes used during constant propagation. */
505 struct cgraph_node
**order
;
506 struct cgraph_node
**stack
;
507 int nnodes
, stack_top
;
510 /* Allocate the arrays in TOPO and topologically sort the nodes into order. */
513 build_toporder_info (struct topo_info
*topo
)
515 topo
->order
= XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
516 topo
->stack
= XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
518 topo
->nnodes
= ipa_reduced_postorder (topo
->order
, true, true, NULL
);
521 /* Free information about strongly connected components and the arrays in
525 free_toporder_info (struct topo_info
*topo
)
527 ipa_free_postorder_info ();
532 /* Add NODE to the stack in TOPO, unless it is already there. */
535 push_node_to_stack (struct topo_info
*topo
, struct cgraph_node
*node
)
537 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
538 if (info
->node_enqueued
)
540 info
->node_enqueued
= 1;
541 topo
->stack
[topo
->stack_top
++] = node
;
544 /* Pop a node from the stack in TOPO and return it or return NULL if the stack
547 static struct cgraph_node
*
548 pop_node_from_stack (struct topo_info
*topo
)
552 struct cgraph_node
*node
;
554 node
= topo
->stack
[topo
->stack_top
];
555 IPA_NODE_REF (node
)->node_enqueued
= 0;
562 /* Set lattice LAT to bottom and return true if it previously was not set as
566 set_lattice_to_bottom (struct ipcp_lattice
*lat
)
568 bool ret
= !lat
->bottom
;
573 /* Mark lattice as containing an unknown value and return true if it previously
574 was not marked as such. */
577 set_lattice_contains_variable (struct ipcp_lattice
*lat
)
579 bool ret
= !lat
->contains_variable
;
580 lat
->contains_variable
= true;
584 /* Initialize ipcp_lattices. */
587 initialize_node_lattices (struct cgraph_node
*node
)
589 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
590 struct cgraph_edge
*ie
;
591 bool disable
= false, variable
= false;
594 gcc_checking_assert (cgraph_function_with_gimple_body_p (node
));
595 if (!node
->local
.local
)
597 /* When cloning is allowed, we can assume that externally visible
598 functions are not called. We will compensate this by cloning
600 if (ipcp_versionable_function_p (node
)
601 && ipcp_cloning_candidate_p (node
))
607 if (disable
|| variable
)
609 for (i
= 0; i
< ipa_get_param_count (info
) ; i
++)
611 struct ipcp_lattice
*lat
= ipa_get_lattice (info
, i
);
613 set_lattice_to_bottom (lat
);
615 set_lattice_contains_variable (lat
);
617 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
618 && node
->alias
&& node
->thunk
.thunk_p
)
619 fprintf (dump_file
, "Marking all lattices of %s/%i as %s\n",
620 cgraph_node_name (node
), node
->uid
,
621 disable
? "BOTTOM" : "VARIABLE");
624 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
625 if (ie
->indirect_info
->polymorphic
)
627 gcc_checking_assert (ie
->indirect_info
->param_index
>= 0);
628 ipa_get_lattice (info
, ie
->indirect_info
->param_index
)->virt_call
= 1;
632 /* Return the result of a (possibly arithmetic) pass through jump function
633 JFUNC on the constant value INPUT. Return NULL_TREE if that cannot be
634 determined or itself is considered an interprocedural invariant. */
637 ipa_get_jf_pass_through_result (struct ipa_jump_func
*jfunc
, tree input
)
641 gcc_checking_assert (is_gimple_ip_invariant (input
));
642 if (jfunc
->value
.pass_through
.operation
== NOP_EXPR
)
645 if (TREE_CODE_CLASS (jfunc
->value
.pass_through
.operation
)
647 restype
= boolean_type_node
;
649 restype
= TREE_TYPE (input
);
650 res
= fold_binary (jfunc
->value
.pass_through
.operation
, restype
,
651 input
, jfunc
->value
.pass_through
.operand
);
653 if (res
&& !is_gimple_ip_invariant (res
))
659 /* Return the result of an ancestor jump function JFUNC on the constant value
660 INPUT. Return NULL_TREE if that cannot be determined. */
663 ipa_get_jf_ancestor_result (struct ipa_jump_func
*jfunc
, tree input
)
665 if (TREE_CODE (input
) == ADDR_EXPR
)
667 tree t
= TREE_OPERAND (input
, 0);
668 t
= build_ref_for_offset (EXPR_LOCATION (t
), t
,
669 jfunc
->value
.ancestor
.offset
,
670 jfunc
->value
.ancestor
.type
, NULL
, false);
671 return build_fold_addr_expr (t
);
677 /* Extract the acual BINFO being described by JFUNC which must be a known type
681 ipa_value_from_known_type_jfunc (struct ipa_jump_func
*jfunc
)
683 tree base_binfo
= TYPE_BINFO (jfunc
->value
.known_type
.base_type
);
686 return get_binfo_at_offset (base_binfo
,
687 jfunc
->value
.known_type
.offset
,
688 jfunc
->value
.known_type
.component_type
);
691 /* Determine whether JFUNC evaluates to a known value (that is either a
692 constant or a binfo) and if so, return it. Otherwise return NULL. INFO
693 describes the caller node so that pass-through jump functions can be
697 ipa_value_from_jfunc (struct ipa_node_params
*info
, struct ipa_jump_func
*jfunc
)
699 if (jfunc
->type
== IPA_JF_CONST
)
700 return jfunc
->value
.constant
;
701 else if (jfunc
->type
== IPA_JF_KNOWN_TYPE
)
702 return ipa_value_from_known_type_jfunc (jfunc
);
703 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
704 || jfunc
->type
== IPA_JF_ANCESTOR
)
709 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
710 idx
= jfunc
->value
.pass_through
.formal_id
;
712 idx
= jfunc
->value
.ancestor
.formal_id
;
714 if (info
->ipcp_orig_node
)
715 input
= VEC_index (tree
, info
->known_vals
, idx
);
718 struct ipcp_lattice
*lat
;
722 gcc_checking_assert (!flag_ipa_cp
);
725 lat
= ipa_get_lattice (info
, idx
);
726 if (!ipa_lat_is_single_const (lat
))
728 input
= lat
->values
->value
;
734 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
736 if (jfunc
->value
.pass_through
.operation
== NOP_EXPR
)
738 else if (TREE_CODE (input
) == TREE_BINFO
)
741 return ipa_get_jf_pass_through_result (jfunc
, input
);
745 if (TREE_CODE (input
) == TREE_BINFO
)
746 return get_binfo_at_offset (input
, jfunc
->value
.ancestor
.offset
,
747 jfunc
->value
.ancestor
.type
);
749 return ipa_get_jf_ancestor_result (jfunc
, input
);
757 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
758 bottom, not containing a variable component and without any known value at
762 ipcp_verify_propagated_values (void)
764 struct cgraph_node
*node
;
766 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
768 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
769 int i
, count
= ipa_get_param_count (info
);
771 for (i
= 0; i
< count
; i
++)
773 struct ipcp_lattice
*lat
= ipa_get_lattice (info
, i
);
776 && !lat
->contains_variable
777 && lat
->values_count
== 0)
781 fprintf (dump_file
, "\nIPA lattices after constant "
783 print_all_lattices (dump_file
, true, false);
792 /* Return true iff X and Y should be considered equal values by IPA-CP. */
795 values_equal_for_ipcp_p (tree x
, tree y
)
797 gcc_checking_assert (x
!= NULL_TREE
&& y
!= NULL_TREE
);
802 if (TREE_CODE (x
) == TREE_BINFO
|| TREE_CODE (y
) == TREE_BINFO
)
805 if (TREE_CODE (x
) == ADDR_EXPR
806 && TREE_CODE (y
) == ADDR_EXPR
807 && TREE_CODE (TREE_OPERAND (x
, 0)) == CONST_DECL
808 && TREE_CODE (TREE_OPERAND (y
, 0)) == CONST_DECL
)
809 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x
, 0)),
810 DECL_INITIAL (TREE_OPERAND (y
, 0)), 0);
812 return operand_equal_p (x
, y
, 0);
815 /* Add a new value source to VAL, marking that a value comes from edge CS and
816 (if the underlying jump function is a pass-through or an ancestor one) from
817 a caller value SRC_VAL of a caller parameter described by SRC_INDEX. */
820 add_value_source (struct ipcp_value
*val
, struct cgraph_edge
*cs
,
821 struct ipcp_value
*src_val
, int src_idx
)
823 struct ipcp_value_source
*src
;
825 src
= (struct ipcp_value_source
*) pool_alloc (ipcp_sources_pool
);
828 src
->index
= src_idx
;
830 src
->next
= val
->sources
;
835 /* Try to add NEWVAL to LAT, potentially creating a new struct ipcp_value for
836 it. CS, SRC_VAL and SRC_INDEX are meant for add_value_source and have the
840 add_value_to_lattice (struct ipcp_lattice
*lat
, tree newval
,
841 struct cgraph_edge
*cs
, struct ipcp_value
*src_val
,
844 struct ipcp_value
*val
;
850 for (val
= lat
->values
; val
; val
= val
->next
)
851 if (values_equal_for_ipcp_p (val
->value
, newval
))
853 if (edge_within_scc (cs
))
855 struct ipcp_value_source
*s
;
856 for (s
= val
->sources
; s
; s
= s
->next
)
863 add_value_source (val
, cs
, src_val
, src_idx
);
867 if (lat
->values_count
== PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE
))
869 /* We can only free sources, not the values themselves, because sources
870 of other values in this this SCC might point to them. */
871 for (val
= lat
->values
; val
; val
= val
->next
)
875 struct ipcp_value_source
*src
= val
->sources
;
876 val
->sources
= src
->next
;
877 pool_free (ipcp_sources_pool
, src
);
882 return set_lattice_to_bottom (lat
);
886 val
= (struct ipcp_value
*) pool_alloc (ipcp_values_pool
);
887 memset (val
, 0, sizeof (*val
));
889 add_value_source (val
, cs
, src_val
, src_idx
);
891 val
->next
= lat
->values
;
896 /* Propagate values through a pass-through jump function JFUNC associated with
897 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
898 is the index of the source parameter. */
901 propagate_vals_accross_pass_through (struct cgraph_edge
*cs
,
902 struct ipa_jump_func
*jfunc
,
903 struct ipcp_lattice
*src_lat
,
904 struct ipcp_lattice
*dest_lat
,
907 struct ipcp_value
*src_val
;
910 if (jfunc
->value
.pass_through
.operation
== NOP_EXPR
)
911 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
912 ret
|= add_value_to_lattice (dest_lat
, src_val
->value
, cs
,
914 /* Do not create new values when propagating within an SCC because if there
915 arithmetic functions with circular dependencies, there is infinite number
916 of them and we would just make lattices bottom. */
917 else if (edge_within_scc (cs
))
918 ret
= set_lattice_contains_variable (dest_lat
);
920 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
922 tree cstval
= src_val
->value
;
924 if (TREE_CODE (cstval
) == TREE_BINFO
)
926 ret
|= set_lattice_contains_variable (dest_lat
);
929 cstval
= ipa_get_jf_pass_through_result (jfunc
, cstval
);
932 ret
|= add_value_to_lattice (dest_lat
, cstval
, cs
, src_val
, src_idx
);
934 ret
|= set_lattice_contains_variable (dest_lat
);
940 /* Propagate values through an ancestor jump function JFUNC associated with
941 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
942 is the index of the source parameter. */
945 propagate_vals_accross_ancestor (struct cgraph_edge
*cs
,
946 struct ipa_jump_func
*jfunc
,
947 struct ipcp_lattice
*src_lat
,
948 struct ipcp_lattice
*dest_lat
,
951 struct ipcp_value
*src_val
;
954 if (edge_within_scc (cs
))
955 return set_lattice_contains_variable (dest_lat
);
957 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
959 tree t
= src_val
->value
;
961 if (TREE_CODE (t
) == TREE_BINFO
)
962 t
= get_binfo_at_offset (t
, jfunc
->value
.ancestor
.offset
,
963 jfunc
->value
.ancestor
.type
);
965 t
= ipa_get_jf_ancestor_result (jfunc
, t
);
968 ret
|= add_value_to_lattice (dest_lat
, t
, cs
, src_val
, src_idx
);
970 ret
|= set_lattice_contains_variable (dest_lat
);
976 /* Propagate values across jump function JFUNC that is associated with edge CS
977 and put the values into DEST_LAT. */
980 propagate_accross_jump_function (struct cgraph_edge
*cs
,
981 struct ipa_jump_func
*jfunc
,
982 struct ipcp_lattice
*dest_lat
)
984 if (dest_lat
->bottom
)
987 if (jfunc
->type
== IPA_JF_CONST
988 || jfunc
->type
== IPA_JF_KNOWN_TYPE
)
992 if (jfunc
->type
== IPA_JF_KNOWN_TYPE
)
994 val
= ipa_value_from_known_type_jfunc (jfunc
);
996 return set_lattice_contains_variable (dest_lat
);
999 val
= jfunc
->value
.constant
;
1000 return add_value_to_lattice (dest_lat
, val
, cs
, NULL
, 0);
1002 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1003 || jfunc
->type
== IPA_JF_ANCESTOR
)
1005 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1006 struct ipcp_lattice
*src_lat
;
1010 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1011 src_idx
= jfunc
->value
.pass_through
.formal_id
;
1013 src_idx
= jfunc
->value
.ancestor
.formal_id
;
1015 src_lat
= ipa_get_lattice (caller_info
, src_idx
);
1016 if (src_lat
->bottom
)
1017 return set_lattice_contains_variable (dest_lat
);
1019 /* If we would need to clone the caller and cannot, do not propagate. */
1020 if (!ipcp_versionable_function_p (cs
->caller
)
1021 && (src_lat
->contains_variable
1022 || (src_lat
->values_count
> 1)))
1023 return set_lattice_contains_variable (dest_lat
);
1025 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1026 ret
= propagate_vals_accross_pass_through (cs
, jfunc
, src_lat
,
1029 ret
= propagate_vals_accross_ancestor (cs
, jfunc
, src_lat
, dest_lat
,
1032 if (src_lat
->contains_variable
)
1033 ret
|= set_lattice_contains_variable (dest_lat
);
1038 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1039 use it for indirect inlining), we should propagate them too. */
1040 return set_lattice_contains_variable (dest_lat
);
1043 /* Propagate constants from the caller to the callee of CS. INFO describes the
1047 propagate_constants_accross_call (struct cgraph_edge
*cs
)
1049 struct ipa_node_params
*callee_info
;
1050 enum availability availability
;
1051 struct cgraph_node
*callee
, *alias_or_thunk
;
1052 struct ipa_edge_args
*args
;
1054 int i
, args_count
, parms_count
;
1056 callee
= cgraph_function_node (cs
->callee
, &availability
);
1057 if (!callee
->analyzed
)
1059 gcc_checking_assert (cgraph_function_with_gimple_body_p (callee
));
1060 callee_info
= IPA_NODE_REF (callee
);
1062 args
= IPA_EDGE_REF (cs
);
1063 args_count
= ipa_get_cs_argument_count (args
);
1064 parms_count
= ipa_get_param_count (callee_info
);
1066 /* If this call goes through a thunk we must not propagate to the first (0th)
1067 parameter. However, we might need to uncover a thunk from below a series
1068 of aliases first. */
1069 alias_or_thunk
= cs
->callee
;
1070 while (alias_or_thunk
->alias
)
1071 alias_or_thunk
= cgraph_alias_aliased_node (alias_or_thunk
);
1072 if (alias_or_thunk
->thunk
.thunk_p
)
1074 ret
|= set_lattice_contains_variable (ipa_get_lattice (callee_info
, 0));
1080 for (; (i
< args_count
) && (i
< parms_count
); i
++)
1082 struct ipa_jump_func
*jump_func
= ipa_get_ith_jump_func (args
, i
);
1083 struct ipcp_lattice
*dest_lat
= ipa_get_lattice (callee_info
, i
);
1085 if (availability
== AVAIL_OVERWRITABLE
)
1086 ret
|= set_lattice_contains_variable (dest_lat
);
1088 ret
|= propagate_accross_jump_function (cs
, jump_func
, dest_lat
);
1090 for (; i
< parms_count
; i
++)
1091 ret
|= set_lattice_contains_variable (ipa_get_lattice (callee_info
, i
));
1096 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
1097 (which can contain both constants and binfos) or KNOWN_BINFOS (which can be
1098 NULL) return the destination. */
1101 ipa_get_indirect_edge_target (struct cgraph_edge
*ie
,
1102 VEC (tree
, heap
) *known_vals
,
1103 VEC (tree
, heap
) *known_binfos
)
1105 int param_index
= ie
->indirect_info
->param_index
;
1106 HOST_WIDE_INT token
, anc_offset
;
1110 if (param_index
== -1)
1113 if (!ie
->indirect_info
->polymorphic
)
1115 tree t
= VEC_index (tree
, known_vals
, param_index
);
1117 TREE_CODE (t
) == ADDR_EXPR
1118 && TREE_CODE (TREE_OPERAND (t
, 0)) == FUNCTION_DECL
)
1119 return TREE_OPERAND (t
, 0);
1124 token
= ie
->indirect_info
->otr_token
;
1125 anc_offset
= ie
->indirect_info
->anc_offset
;
1126 otr_type
= ie
->indirect_info
->otr_type
;
1128 t
= VEC_index (tree
, known_vals
, param_index
);
1129 if (!t
&& known_binfos
)
1130 t
= VEC_index (tree
, known_binfos
, param_index
);
1134 if (TREE_CODE (t
) != TREE_BINFO
)
1137 binfo
= gimple_extract_devirt_binfo_from_cst (t
);
1140 binfo
= get_binfo_at_offset (binfo
, anc_offset
, otr_type
);
1143 return gimple_get_virt_method_for_binfo (token
, binfo
);
1149 binfo
= get_binfo_at_offset (t
, anc_offset
, otr_type
);
1152 return gimple_get_virt_method_for_binfo (token
, binfo
);
1156 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
1157 and KNOWN_BINFOS. */
1160 devirtualization_time_bonus (struct cgraph_node
*node
,
1161 VEC (tree
, heap
) *known_csts
,
1162 VEC (tree
, heap
) *known_binfos
)
1164 struct cgraph_edge
*ie
;
1167 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
1169 struct cgraph_node
*callee
;
1170 struct inline_summary
*isummary
;
1173 target
= ipa_get_indirect_edge_target (ie
, known_csts
, known_binfos
);
1177 /* Only bare minimum benefit for clearly un-inlineable targets. */
1179 callee
= cgraph_get_node (target
);
1180 if (!callee
|| !callee
->analyzed
)
1182 isummary
= inline_summary (callee
);
1183 if (!isummary
->inlinable
)
1186 /* FIXME: The values below need re-considering and perhaps also
1187 integrating into the cost metrics, at lest in some very basic way. */
1188 if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 4)
1190 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 2)
1192 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
1193 || DECL_DECLARED_INLINE_P (callee
->decl
))
1200 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
1201 and SIZE_COST and with the sum of frequencies of incoming edges to the
1202 potential new clone in FREQUENCIES. */
1205 good_cloning_opportunity_p (struct cgraph_node
*node
, int time_benefit
,
1206 int freq_sum
, gcov_type count_sum
, int size_cost
)
1208 if (time_benefit
== 0
1209 || !flag_ipa_cp_clone
1210 || !optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node
->decl
)))
1213 gcc_assert (size_cost
> 0);
1217 int factor
= (count_sum
* 1000) / max_count
;
1218 HOST_WIDEST_INT evaluation
= (((HOST_WIDEST_INT
) time_benefit
* factor
)
1221 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1222 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
1223 "size: %i, count_sum: " HOST_WIDE_INT_PRINT_DEC
1224 ") -> evaluation: " HOST_WIDEST_INT_PRINT_DEC
1225 ", threshold: %i\n",
1226 time_benefit
, size_cost
, (HOST_WIDE_INT
) count_sum
,
1229 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
1233 HOST_WIDEST_INT evaluation
= (((HOST_WIDEST_INT
) time_benefit
* freq_sum
)
1236 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1237 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
1238 "size: %i, freq_sum: %i) -> evaluation: "
1239 HOST_WIDEST_INT_PRINT_DEC
", threshold: %i\n",
1240 time_benefit
, size_cost
, freq_sum
, evaluation
,
1241 CGRAPH_FREQ_BASE
/2);
1243 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
1248 /* Allocate KNOWN_CSTS and KNOWN_BINFOS and populate them with values of
1249 parameters that are known independent of the context. INFO describes the
1250 function. If REMOVABLE_PARAMS_COST is non-NULL, the movement cost of all
1251 removable parameters will be stored in it. */
1254 gather_context_independent_values (struct ipa_node_params
*info
,
1255 VEC (tree
, heap
) **known_csts
,
1256 VEC (tree
, heap
) **known_binfos
,
1257 int *removable_params_cost
)
1259 int i
, count
= ipa_get_param_count (info
);
1263 *known_binfos
= NULL
;
1264 VEC_safe_grow_cleared (tree
, heap
, *known_csts
, count
);
1265 VEC_safe_grow_cleared (tree
, heap
, *known_binfos
, count
);
1267 if (removable_params_cost
)
1268 *removable_params_cost
= 0;
1270 for (i
= 0; i
< count
; i
++)
1272 struct ipcp_lattice
*lat
= ipa_get_lattice (info
, i
);
1274 if (ipa_lat_is_single_const (lat
))
1276 struct ipcp_value
*val
= lat
->values
;
1277 if (TREE_CODE (val
->value
) != TREE_BINFO
)
1279 VEC_replace (tree
, *known_csts
, i
, val
->value
);
1280 if (removable_params_cost
)
1281 *removable_params_cost
1282 += estimate_move_cost (TREE_TYPE (val
->value
));
1285 else if (lat
->virt_call
)
1287 VEC_replace (tree
, *known_binfos
, i
, val
->value
);
1290 else if (removable_params_cost
1291 && !ipa_is_param_used (info
, i
))
1292 *removable_params_cost
1293 += estimate_move_cost (TREE_TYPE (ipa_get_param (info
, i
)));
1295 else if (removable_params_cost
1296 && !ipa_is_param_used (info
, i
))
1297 *removable_params_cost
1298 += estimate_move_cost (TREE_TYPE (ipa_get_param (info
, i
)));
1304 /* Iterate over known values of parameters of NODE and estimate the local
1305 effects in terms of time and size they have. */
1308 estimate_local_effects (struct cgraph_node
*node
)
1310 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1311 int i
, count
= ipa_get_param_count (info
);
1312 VEC (tree
, heap
) *known_csts
, *known_binfos
;
1314 int base_time
= inline_summary (node
)->time
;
1315 int removable_params_cost
;
1317 if (!count
|| !ipcp_versionable_function_p (node
))
1320 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1321 fprintf (dump_file
, "\nEstimating effects for %s/%i, base_time: %i.\n",
1322 cgraph_node_name (node
), node
->uid
, base_time
);
1324 always_const
= gather_context_independent_values (info
, &known_csts
,
1326 &removable_params_cost
);
1329 struct caller_statistics stats
;
1332 init_caller_stats (&stats
);
1333 cgraph_for_node_and_aliases (node
, gather_caller_stats
, &stats
, false);
1334 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_binfos
,
1336 time
-= devirtualization_time_bonus (node
, known_csts
, known_binfos
);
1337 time
-= removable_params_cost
;
1338 size
-= stats
.n_calls
* removable_params_cost
;
1341 fprintf (dump_file
, " - context independent values, size: %i, "
1342 "time_benefit: %i\n", size
, base_time
- time
);
1345 || cgraph_will_be_removed_from_program_if_no_direct_calls (node
))
1347 info
->clone_for_all_contexts
= true;
1351 fprintf (dump_file
, " Decided to specialize for all "
1352 "known contexts, code not going to grow.\n");
1354 else if (good_cloning_opportunity_p (node
, base_time
- time
,
1355 stats
.freq_sum
, stats
.count_sum
,
1358 if (size
+ overall_size
<= max_new_size
)
1360 info
->clone_for_all_contexts
= true;
1362 overall_size
+= size
;
1365 fprintf (dump_file
, " Decided to specialize for all "
1366 "known contexts, growth deemed beneficial.\n");
1368 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1369 fprintf (dump_file
, " Not cloning for all contexts because "
1370 "max_new_size would be reached with %li.\n",
1371 size
+ overall_size
);
1375 for (i
= 0; i
< count
; i
++)
1377 struct ipcp_lattice
*lat
= ipa_get_lattice (info
, i
);
1378 struct ipcp_value
*val
;
1383 || VEC_index (tree
, known_csts
, i
)
1384 || VEC_index (tree
, known_binfos
, i
))
1387 for (val
= lat
->values
; val
; val
= val
->next
)
1389 int time
, size
, time_benefit
;
1391 if (TREE_CODE (val
->value
) != TREE_BINFO
)
1393 VEC_replace (tree
, known_csts
, i
, val
->value
);
1394 VEC_replace (tree
, known_binfos
, i
, NULL_TREE
);
1395 emc
= estimate_move_cost (TREE_TYPE (val
->value
));
1397 else if (lat
->virt_call
)
1399 VEC_replace (tree
, known_csts
, i
, NULL_TREE
);
1400 VEC_replace (tree
, known_binfos
, i
, val
->value
);
1406 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_binfos
,
1408 time_benefit
= base_time
- time
1409 + devirtualization_time_bonus (node
, known_csts
, known_binfos
)
1410 + removable_params_cost
+ emc
;
1412 gcc_checking_assert (size
>=0);
1413 /* The inliner-heuristics based estimates may think that in certain
1414 contexts some functions do not have any size at all but we want
1415 all specializations to have at least a tiny cost, not least not to
1420 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1422 fprintf (dump_file
, " - estimates for value ");
1423 print_ipcp_constant_value (dump_file
, val
->value
);
1424 fprintf (dump_file
, " for parameter ");
1425 print_generic_expr (dump_file
, ipa_get_param (info
, i
), 0);
1426 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
1427 time_benefit
, size
);
1430 val
->local_time_benefit
= time_benefit
;
1431 val
->local_size_cost
= size
;
1435 VEC_free (tree
, heap
, known_csts
);
1436 VEC_free (tree
, heap
, known_binfos
);
1440 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
1441 topological sort of values. */
1444 add_val_to_toposort (struct ipcp_value
*cur_val
)
1446 static int dfs_counter
= 0;
1447 static struct ipcp_value
*stack
;
1448 struct ipcp_value_source
*src
;
1454 cur_val
->dfs
= dfs_counter
;
1455 cur_val
->low_link
= dfs_counter
;
1457 cur_val
->topo_next
= stack
;
1459 cur_val
->on_stack
= true;
1461 for (src
= cur_val
->sources
; src
; src
= src
->next
)
1464 if (src
->val
->dfs
== 0)
1466 add_val_to_toposort (src
->val
);
1467 if (src
->val
->low_link
< cur_val
->low_link
)
1468 cur_val
->low_link
= src
->val
->low_link
;
1470 else if (src
->val
->on_stack
1471 && src
->val
->dfs
< cur_val
->low_link
)
1472 cur_val
->low_link
= src
->val
->dfs
;
1475 if (cur_val
->dfs
== cur_val
->low_link
)
1477 struct ipcp_value
*v
, *scc_list
= NULL
;
1482 stack
= v
->topo_next
;
1483 v
->on_stack
= false;
1485 v
->scc_next
= scc_list
;
1488 while (v
!= cur_val
);
1490 cur_val
->topo_next
= values_topo
;
1491 values_topo
= cur_val
;
1495 /* Add all values in lattices associated with NODE to the topological sort if
1496 they are not there yet. */
1499 add_all_node_vals_to_toposort (struct cgraph_node
*node
)
1501 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1502 int i
, count
= ipa_get_param_count (info
);
1504 for (i
= 0; i
< count
; i
++)
1506 struct ipcp_lattice
*lat
= ipa_get_lattice (info
, i
);
1507 struct ipcp_value
*val
;
1509 if (lat
->bottom
|| !lat
->values
)
1511 for (val
= lat
->values
; val
; val
= val
->next
)
1512 add_val_to_toposort (val
);
1516 /* One pass of constants propagation along the call graph edges, from callers
1517 to callees (requires topological ordering in TOPO), iterate over strongly
1518 connected components. */
1521 propagate_constants_topo (struct topo_info
*topo
)
1525 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
1527 struct cgraph_node
*v
, *node
= topo
->order
[i
];
1528 struct ipa_dfs_info
*node_dfs_info
;
1530 if (!cgraph_function_with_gimple_body_p (node
))
1533 node_dfs_info
= (struct ipa_dfs_info
*) node
->aux
;
1534 /* First, iteratively propagate within the strongly connected component
1535 until all lattices stabilize. */
1536 v
= node_dfs_info
->next_cycle
;
1539 push_node_to_stack (topo
, v
);
1540 v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
;
1546 struct cgraph_edge
*cs
;
1548 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
1549 if (edge_within_scc (cs
)
1550 && propagate_constants_accross_call (cs
))
1551 push_node_to_stack (topo
, cs
->callee
);
1552 v
= pop_node_from_stack (topo
);
1555 /* Afterwards, propagate along edges leading out of the SCC, calculates
1556 the local effects of the discovered constants and all valid values to
1557 their topological sort. */
1561 struct cgraph_edge
*cs
;
1563 estimate_local_effects (v
);
1564 add_all_node_vals_to_toposort (v
);
1565 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
1566 if (!edge_within_scc (cs
))
1567 propagate_constants_accross_call (cs
);
1569 v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
;
1575 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
1576 the bigger one if otherwise. */
1579 safe_add (int a
, int b
)
1581 if (a
> INT_MAX
/2 || b
> INT_MAX
/2)
1582 return a
> b
? a
: b
;
1588 /* Propagate the estimated effects of individual values along the topological
1589 from the dependant values to those they depend on. */
1592 propagate_effects (void)
1594 struct ipcp_value
*base
;
1596 for (base
= values_topo
; base
; base
= base
->topo_next
)
1598 struct ipcp_value_source
*src
;
1599 struct ipcp_value
*val
;
1600 int time
= 0, size
= 0;
1602 for (val
= base
; val
; val
= val
->scc_next
)
1604 time
= safe_add (time
,
1605 val
->local_time_benefit
+ val
->prop_time_benefit
);
1606 size
= safe_add (size
, val
->local_size_cost
+ val
->prop_size_cost
);
1609 for (val
= base
; val
; val
= val
->scc_next
)
1610 for (src
= val
->sources
; src
; src
= src
->next
)
1612 && cgraph_maybe_hot_edge_p (src
->cs
))
1614 src
->val
->prop_time_benefit
= safe_add (time
,
1615 src
->val
->prop_time_benefit
);
1616 src
->val
->prop_size_cost
= safe_add (size
,
1617 src
->val
->prop_size_cost
);
1623 /* Propagate constants, binfos and their effects from the summaries
1624 interprocedurally. */
1627 ipcp_propagate_stage (struct topo_info
*topo
)
1629 struct cgraph_node
*node
;
1632 fprintf (dump_file
, "\n Propagating constants:\n\n");
1635 ipa_update_after_lto_read ();
1638 FOR_EACH_DEFINED_FUNCTION (node
)
1640 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1642 determine_versionability (node
);
1643 if (cgraph_function_with_gimple_body_p (node
))
1645 info
->lattices
= XCNEWVEC (struct ipcp_lattice
,
1646 ipa_get_param_count (info
));
1647 initialize_node_lattices (node
);
1649 if (node
->count
> max_count
)
1650 max_count
= node
->count
;
1651 overall_size
+= inline_summary (node
)->self_size
;
1654 max_new_size
= overall_size
;
1655 if (max_new_size
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
1656 max_new_size
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
1657 max_new_size
+= max_new_size
* PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH
) / 100 + 1;
1660 fprintf (dump_file
, "\noverall_size: %li, max_new_size: %li\n",
1661 overall_size
, max_new_size
);
1663 propagate_constants_topo (topo
);
1664 #ifdef ENABLE_CHECKING
1665 ipcp_verify_propagated_values ();
1667 propagate_effects ();
1671 fprintf (dump_file
, "\nIPA lattices after all propagation:\n");
1672 print_all_lattices (dump_file
, (dump_flags
& TDF_DETAILS
), true);
1676 /* Discover newly direct outgoing edges from NODE which is a new clone with
1677 known KNOWN_VALS and make them direct. */
1680 ipcp_discover_new_direct_edges (struct cgraph_node
*node
,
1681 VEC (tree
, heap
) *known_vals
)
1683 struct cgraph_edge
*ie
, *next_ie
;
1685 for (ie
= node
->indirect_calls
; ie
; ie
= next_ie
)
1689 next_ie
= ie
->next_callee
;
1690 target
= ipa_get_indirect_edge_target (ie
, known_vals
, NULL
);
1692 ipa_make_edge_direct_to_target (ie
, target
);
1696 /* Vector of pointers which for linked lists of clones of an original crgaph
1699 static VEC (cgraph_edge_p
, heap
) *next_edge_clone
;
1702 grow_next_edge_clone_vector (void)
1704 if (VEC_length (cgraph_edge_p
, next_edge_clone
)
1705 <= (unsigned) cgraph_edge_max_uid
)
1706 VEC_safe_grow_cleared (cgraph_edge_p
, heap
, next_edge_clone
,
1707 cgraph_edge_max_uid
+ 1);
1710 /* Edge duplication hook to grow the appropriate linked list in
1714 ipcp_edge_duplication_hook (struct cgraph_edge
*src
, struct cgraph_edge
*dst
,
1715 __attribute__((unused
)) void *data
)
1717 grow_next_edge_clone_vector ();
1718 VEC_replace (cgraph_edge_p
, next_edge_clone
, dst
->uid
,
1719 VEC_index (cgraph_edge_p
, next_edge_clone
, src
->uid
));
1720 VEC_replace (cgraph_edge_p
, next_edge_clone
, src
->uid
, dst
);
1723 /* Get the next clone in the linked list of clones of an edge. */
1725 static inline struct cgraph_edge
*
1726 get_next_cgraph_edge_clone (struct cgraph_edge
*cs
)
1728 return VEC_index (cgraph_edge_p
, next_edge_clone
, cs
->uid
);
1731 /* Return true if edge CS does bring about the value described by SRC. */
1734 cgraph_edge_brings_value_p (struct cgraph_edge
*cs
,
1735 struct ipcp_value_source
*src
)
1737 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1739 if (IPA_NODE_REF (cs
->callee
)->ipcp_orig_node
1740 || caller_info
->node_dead
)
1745 if (caller_info
->ipcp_orig_node
)
1747 tree t
= VEC_index (tree
, caller_info
->known_vals
, src
->index
);
1748 return (t
!= NULL_TREE
1749 && values_equal_for_ipcp_p (src
->val
->value
, t
));
1753 struct ipcp_lattice
*lat
= ipa_get_lattice (caller_info
, src
->index
);
1754 if (ipa_lat_is_single_const (lat
)
1755 && values_equal_for_ipcp_p (src
->val
->value
, lat
->values
->value
))
1762 /* Given VAL, iterate over all its sources and if they still hold, add their
1763 edge frequency and their number into *FREQUENCY and *CALLER_COUNT
1767 get_info_about_necessary_edges (struct ipcp_value
*val
, int *freq_sum
,
1768 gcov_type
*count_sum
, int *caller_count
)
1770 struct ipcp_value_source
*src
;
1771 int freq
= 0, count
= 0;
1775 for (src
= val
->sources
; src
; src
= src
->next
)
1777 struct cgraph_edge
*cs
= src
->cs
;
1780 if (cgraph_edge_brings_value_p (cs
, src
))
1783 freq
+= cs
->frequency
;
1785 hot
|= cgraph_maybe_hot_edge_p (cs
);
1787 cs
= get_next_cgraph_edge_clone (cs
);
1793 *caller_count
= count
;
1797 /* Return a vector of incoming edges that do bring value VAL. It is assumed
1798 their number is known and equal to CALLER_COUNT. */
1800 static VEC (cgraph_edge_p
,heap
) *
1801 gather_edges_for_value (struct ipcp_value
*val
, int caller_count
)
1803 struct ipcp_value_source
*src
;
1804 VEC (cgraph_edge_p
,heap
) *ret
;
1806 ret
= VEC_alloc (cgraph_edge_p
, heap
, caller_count
);
1807 for (src
= val
->sources
; src
; src
= src
->next
)
1809 struct cgraph_edge
*cs
= src
->cs
;
1812 if (cgraph_edge_brings_value_p (cs
, src
))
1813 VEC_quick_push (cgraph_edge_p
, ret
, cs
);
1814 cs
= get_next_cgraph_edge_clone (cs
);
1821 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
1822 Return it or NULL if for some reason it cannot be created. */
1824 static struct ipa_replace_map
*
1825 get_replacement_map (tree value
, tree parm
)
1827 tree req_type
= TREE_TYPE (parm
);
1828 struct ipa_replace_map
*replace_map
;
1830 if (!useless_type_conversion_p (req_type
, TREE_TYPE (value
)))
1832 if (fold_convertible_p (req_type
, value
))
1833 value
= fold_build1 (NOP_EXPR
, req_type
, value
);
1834 else if (TYPE_SIZE (req_type
) == TYPE_SIZE (TREE_TYPE (value
)))
1835 value
= fold_build1 (VIEW_CONVERT_EXPR
, req_type
, value
);
1840 fprintf (dump_file
, " const ");
1841 print_generic_expr (dump_file
, value
, 0);
1842 fprintf (dump_file
, " can't be converted to param ");
1843 print_generic_expr (dump_file
, parm
, 0);
1844 fprintf (dump_file
, "\n");
1850 replace_map
= ggc_alloc_ipa_replace_map ();
1853 fprintf (dump_file
, " replacing param ");
1854 print_generic_expr (dump_file
, parm
, 0);
1855 fprintf (dump_file
, " with const ");
1856 print_generic_expr (dump_file
, value
, 0);
1857 fprintf (dump_file
, "\n");
1859 replace_map
->old_tree
= parm
;
1860 replace_map
->new_tree
= value
;
1861 replace_map
->replace_p
= true;
1862 replace_map
->ref_p
= false;
1867 /* Dump new profiling counts */
1870 dump_profile_updates (struct cgraph_node
*orig_node
,
1871 struct cgraph_node
*new_node
)
1873 struct cgraph_edge
*cs
;
1875 fprintf (dump_file
, " setting count of the specialized node to "
1876 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) new_node
->count
);
1877 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
1878 fprintf (dump_file
, " edge to %s has count "
1879 HOST_WIDE_INT_PRINT_DEC
"\n",
1880 cgraph_node_name (cs
->callee
), (HOST_WIDE_INT
) cs
->count
);
1882 fprintf (dump_file
, " setting count of the original node to "
1883 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) orig_node
->count
);
1884 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
1885 fprintf (dump_file
, " edge to %s is left with "
1886 HOST_WIDE_INT_PRINT_DEC
"\n",
1887 cgraph_node_name (cs
->callee
), (HOST_WIDE_INT
) cs
->count
);
1890 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
1891 their profile information to reflect this. */
1894 update_profiling_info (struct cgraph_node
*orig_node
,
1895 struct cgraph_node
*new_node
)
1897 struct cgraph_edge
*cs
;
1898 struct caller_statistics stats
;
1899 gcov_type new_sum
, orig_sum
;
1900 gcov_type remainder
, orig_node_count
= orig_node
->count
;
1902 if (orig_node_count
== 0)
1905 init_caller_stats (&stats
);
1906 cgraph_for_node_and_aliases (orig_node
, gather_caller_stats
, &stats
, false);
1907 orig_sum
= stats
.count_sum
;
1908 init_caller_stats (&stats
);
1909 cgraph_for_node_and_aliases (new_node
, gather_caller_stats
, &stats
, false);
1910 new_sum
= stats
.count_sum
;
1912 if (orig_node_count
< orig_sum
+ new_sum
)
1915 fprintf (dump_file
, " Problem: node %s/%i has too low count "
1916 HOST_WIDE_INT_PRINT_DEC
" while the sum of incoming "
1917 "counts is " HOST_WIDE_INT_PRINT_DEC
"\n",
1918 cgraph_node_name (orig_node
), orig_node
->uid
,
1919 (HOST_WIDE_INT
) orig_node_count
,
1920 (HOST_WIDE_INT
) (orig_sum
+ new_sum
));
1922 orig_node_count
= (orig_sum
+ new_sum
) * 12 / 10;
1924 fprintf (dump_file
, " proceeding by pretending it was "
1925 HOST_WIDE_INT_PRINT_DEC
"\n",
1926 (HOST_WIDE_INT
) orig_node_count
);
1929 new_node
->count
= new_sum
;
1930 remainder
= orig_node_count
- new_sum
;
1931 orig_node
->count
= remainder
;
1933 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
1935 cs
->count
= cs
->count
* (new_sum
* REG_BR_PROB_BASE
1936 / orig_node_count
) / REG_BR_PROB_BASE
;
1940 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
1941 cs
->count
= cs
->count
* (remainder
* REG_BR_PROB_BASE
1942 / orig_node_count
) / REG_BR_PROB_BASE
;
1945 dump_profile_updates (orig_node
, new_node
);
1948 /* Update the respective profile of specialized NEW_NODE and the original
1949 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
1950 have been redirected to the specialized version. */
1953 update_specialized_profile (struct cgraph_node
*new_node
,
1954 struct cgraph_node
*orig_node
,
1955 gcov_type redirected_sum
)
1957 struct cgraph_edge
*cs
;
1958 gcov_type new_node_count
, orig_node_count
= orig_node
->count
;
1961 fprintf (dump_file
, " the sum of counts of redirected edges is "
1962 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) redirected_sum
);
1963 if (orig_node_count
== 0)
1966 gcc_assert (orig_node_count
>= redirected_sum
);
1968 new_node_count
= new_node
->count
;
1969 new_node
->count
+= redirected_sum
;
1970 orig_node
->count
-= redirected_sum
;
1972 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
1974 cs
->count
+= cs
->count
* redirected_sum
/ new_node_count
;
1978 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
1980 gcov_type dec
= cs
->count
* (redirected_sum
* REG_BR_PROB_BASE
1981 / orig_node_count
) / REG_BR_PROB_BASE
;
1982 if (dec
< cs
->count
)
1989 dump_profile_updates (orig_node
, new_node
);
1992 /* Create a specialized version of NODE with known constants and types of
1993 parameters in KNOWN_VALS and redirect all edges in CALLERS to it. */
1995 static struct cgraph_node
*
1996 create_specialized_node (struct cgraph_node
*node
,
1997 VEC (tree
, heap
) *known_vals
,
1998 VEC (cgraph_edge_p
,heap
) *callers
)
2000 struct ipa_node_params
*new_info
, *info
= IPA_NODE_REF (node
);
2001 VEC (ipa_replace_map_p
,gc
)* replace_trees
= NULL
;
2002 struct cgraph_node
*new_node
;
2003 int i
, count
= ipa_get_param_count (info
);
2004 bitmap args_to_skip
;
2006 gcc_assert (!info
->ipcp_orig_node
);
2008 if (node
->local
.can_change_signature
)
2010 args_to_skip
= BITMAP_GGC_ALLOC ();
2011 for (i
= 0; i
< count
; i
++)
2013 tree t
= VEC_index (tree
, known_vals
, i
);
2015 if ((t
&& TREE_CODE (t
) != TREE_BINFO
)
2016 || !ipa_is_param_used (info
, i
))
2017 bitmap_set_bit (args_to_skip
, i
);
2022 args_to_skip
= NULL
;
2023 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2024 fprintf (dump_file
, " cannot change function signature\n");
2027 for (i
= 0; i
< count
; i
++)
2029 tree t
= VEC_index (tree
, known_vals
, i
);
2030 if (t
&& TREE_CODE (t
) != TREE_BINFO
)
2032 struct ipa_replace_map
*replace_map
;
2034 replace_map
= get_replacement_map (t
, ipa_get_param (info
, i
));
2036 VEC_safe_push (ipa_replace_map_p
, gc
, replace_trees
, replace_map
);
2040 new_node
= cgraph_create_virtual_clone (node
, callers
, replace_trees
,
2041 args_to_skip
, "constprop");
2042 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2043 fprintf (dump_file
, " the new node is %s/%i.\n",
2044 cgraph_node_name (new_node
), new_node
->uid
);
2045 gcc_checking_assert (ipa_node_params_vector
2046 && (VEC_length (ipa_node_params_t
,
2047 ipa_node_params_vector
)
2048 > (unsigned) cgraph_max_uid
));
2049 update_profiling_info (node
, new_node
);
2050 new_info
= IPA_NODE_REF (new_node
);
2051 new_info
->ipcp_orig_node
= node
;
2052 new_info
->known_vals
= known_vals
;
2054 ipcp_discover_new_direct_edges (new_node
, known_vals
);
2056 VEC_free (cgraph_edge_p
, heap
, callers
);
2060 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
2061 KNOWN_VALS with constants and types that are also known for all of the
2065 find_more_values_for_callers_subset (struct cgraph_node
*node
,
2066 VEC (tree
, heap
) *known_vals
,
2067 VEC (cgraph_edge_p
,heap
) *callers
)
2069 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2070 int i
, count
= ipa_get_param_count (info
);
2072 for (i
= 0; i
< count
; i
++)
2074 struct cgraph_edge
*cs
;
2075 tree newval
= NULL_TREE
;
2078 if (ipa_get_lattice (info
, i
)->bottom
2079 || VEC_index (tree
, known_vals
, i
))
2082 FOR_EACH_VEC_ELT (cgraph_edge_p
, callers
, j
, cs
)
2084 struct ipa_jump_func
*jump_func
;
2087 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
)))
2092 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
2093 t
= ipa_value_from_jfunc (IPA_NODE_REF (cs
->caller
), jump_func
);
2096 && !values_equal_for_ipcp_p (t
, newval
)))
2107 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2109 fprintf (dump_file
, " adding an extra known value ");
2110 print_ipcp_constant_value (dump_file
, newval
);
2111 fprintf (dump_file
, " for parameter ");
2112 print_generic_expr (dump_file
, ipa_get_param (info
, i
), 0);
2113 fprintf (dump_file
, "\n");
2116 VEC_replace (tree
, known_vals
, i
, newval
);
2121 /* Given an original NODE and a VAL for which we have already created a
2122 specialized clone, look whether there are incoming edges that still lead
2123 into the old node but now also bring the requested value and also conform to
2124 all other criteria such that they can be redirected the the special node.
2125 This function can therefore redirect the final edge in a SCC. */
2128 perhaps_add_new_callers (struct cgraph_node
*node
, struct ipcp_value
*val
)
2130 struct ipa_node_params
*dest_info
= IPA_NODE_REF (val
->spec_node
);
2131 struct ipcp_value_source
*src
;
2132 int count
= ipa_get_param_count (dest_info
);
2133 gcov_type redirected_sum
= 0;
2135 for (src
= val
->sources
; src
; src
= src
->next
)
2137 struct cgraph_edge
*cs
= src
->cs
;
2140 enum availability availability
;
2141 bool insufficient
= false;
2143 if (cgraph_function_node (cs
->callee
, &availability
) == node
2144 && availability
> AVAIL_OVERWRITABLE
2145 && cgraph_edge_brings_value_p (cs
, src
))
2147 struct ipa_node_params
*caller_info
;
2148 struct ipa_edge_args
*args
;
2151 caller_info
= IPA_NODE_REF (cs
->caller
);
2152 args
= IPA_EDGE_REF (cs
);
2153 for (i
= 0; i
< count
; i
++)
2155 struct ipa_jump_func
*jump_func
;
2158 val
= VEC_index (tree
, dest_info
->known_vals
, i
);
2162 if (i
>= ipa_get_cs_argument_count (args
))
2164 insufficient
= true;
2167 jump_func
= ipa_get_ith_jump_func (args
, i
);
2168 t
= ipa_value_from_jfunc (caller_info
, jump_func
);
2169 if (!t
|| !values_equal_for_ipcp_p (val
, t
))
2171 insufficient
= true;
2179 fprintf (dump_file
, " - adding an extra caller %s/%i"
2181 cgraph_node_name (cs
->caller
), cs
->caller
->uid
,
2182 cgraph_node_name (val
->spec_node
),
2183 val
->spec_node
->uid
);
2185 cgraph_redirect_edge_callee (cs
, val
->spec_node
);
2186 redirected_sum
+= cs
->count
;
2189 cs
= get_next_cgraph_edge_clone (cs
);
2194 update_specialized_profile (val
->spec_node
, node
, redirected_sum
);
2198 /* Copy KNOWN_BINFOS to KNOWN_VALS. */
2201 move_binfos_to_values (VEC (tree
, heap
) *known_vals
,
2202 VEC (tree
, heap
) *known_binfos
)
2207 for (i
= 0; VEC_iterate (tree
, known_binfos
, i
, t
); i
++)
2209 VEC_replace (tree
, known_vals
, i
, t
);
2213 /* Decide whether and what specialized clones of NODE should be created. */
2216 decide_whether_version_node (struct cgraph_node
*node
)
2218 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2219 int i
, count
= ipa_get_param_count (info
);
2220 VEC (tree
, heap
) *known_csts
, *known_binfos
;
2226 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2227 fprintf (dump_file
, "\nEvaluating opportunities for %s/%i.\n",
2228 cgraph_node_name (node
), node
->uid
);
2230 gather_context_independent_values (info
, &known_csts
, &known_binfos
,
2233 for (i
= 0; i
< count
; i
++)
2235 struct ipcp_lattice
*lat
= ipa_get_lattice (info
, i
);
2236 struct ipcp_value
*val
;
2239 || VEC_index (tree
, known_csts
, i
)
2240 || VEC_index (tree
, known_binfos
, i
))
2243 for (val
= lat
->values
; val
; val
= val
->next
)
2245 int freq_sum
, caller_count
;
2246 gcov_type count_sum
;
2247 VEC (cgraph_edge_p
, heap
) *callers
;
2248 VEC (tree
, heap
) *kv
;
2252 perhaps_add_new_callers (node
, val
);
2255 else if (val
->local_size_cost
+ overall_size
> max_new_size
)
2257 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2258 fprintf (dump_file
, " Ignoring candidate value because "
2259 "max_new_size would be reached with %li.\n",
2260 val
->local_size_cost
+ overall_size
);
2263 else if (!get_info_about_necessary_edges (val
, &freq_sum
, &count_sum
,
2267 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2269 fprintf (dump_file
, " - considering value ");
2270 print_ipcp_constant_value (dump_file
, val
->value
);
2271 fprintf (dump_file
, " for parameter ");
2272 print_generic_expr (dump_file
, ipa_get_param (info
, i
), 0);
2273 fprintf (dump_file
, " (caller_count: %i)\n", caller_count
);
2277 if (!good_cloning_opportunity_p (node
, val
->local_time_benefit
,
2278 freq_sum
, count_sum
,
2279 val
->local_size_cost
)
2280 && !good_cloning_opportunity_p (node
,
2281 val
->local_time_benefit
2282 + val
->prop_time_benefit
,
2283 freq_sum
, count_sum
,
2284 val
->local_size_cost
2285 + val
->prop_size_cost
))
2289 fprintf (dump_file
, " Creating a specialized node of %s/%i.\n",
2290 cgraph_node_name (node
), node
->uid
);
2292 callers
= gather_edges_for_value (val
, caller_count
);
2293 kv
= VEC_copy (tree
, heap
, known_csts
);
2294 move_binfos_to_values (kv
, known_binfos
);
2295 VEC_replace (tree
, kv
, i
, val
->value
);
2296 find_more_values_for_callers_subset (node
, kv
, callers
);
2297 val
->spec_node
= create_specialized_node (node
, kv
, callers
);
2298 overall_size
+= val
->local_size_cost
;
2299 info
= IPA_NODE_REF (node
);
2301 /* TODO: If for some lattice there is only one other known value
2302 left, make a special node for it too. */
2305 VEC_replace (tree
, kv
, i
, val
->value
);
2309 if (info
->clone_for_all_contexts
)
2311 VEC (cgraph_edge_p
, heap
) *callers
;
2314 fprintf (dump_file
, " - Creating a specialized node of %s/%i "
2315 "for all known contexts.\n", cgraph_node_name (node
),
2318 callers
= collect_callers_of_node (node
);
2319 move_binfos_to_values (known_csts
, known_binfos
);
2320 create_specialized_node (node
, known_csts
, callers
);
2321 info
= IPA_NODE_REF (node
);
2322 info
->clone_for_all_contexts
= false;
2326 VEC_free (tree
, heap
, known_csts
);
2328 VEC_free (tree
, heap
, known_binfos
);
2332 /* Transitively mark all callees of NODE within the same SCC as not dead. */
2335 spread_undeadness (struct cgraph_node
*node
)
2337 struct cgraph_edge
*cs
;
2339 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
2340 if (edge_within_scc (cs
))
2342 struct cgraph_node
*callee
;
2343 struct ipa_node_params
*info
;
2345 callee
= cgraph_function_node (cs
->callee
, NULL
);
2346 info
= IPA_NODE_REF (callee
);
2348 if (info
->node_dead
)
2350 info
->node_dead
= 0;
2351 spread_undeadness (callee
);
2356 /* Return true if NODE has a caller from outside of its SCC that is not
2357 dead. Worker callback for cgraph_for_node_and_aliases. */
2360 has_undead_caller_from_outside_scc_p (struct cgraph_node
*node
,
2361 void *data ATTRIBUTE_UNUSED
)
2363 struct cgraph_edge
*cs
;
2365 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
2366 if (cs
->caller
->thunk
.thunk_p
2367 && cgraph_for_node_and_aliases (cs
->caller
,
2368 has_undead_caller_from_outside_scc_p
,
2371 else if (!edge_within_scc (cs
)
2372 && !IPA_NODE_REF (cs
->caller
)->node_dead
)
2378 /* Identify nodes within the same SCC as NODE which are no longer needed
2379 because of new clones and will be removed as unreachable. */
2382 identify_dead_nodes (struct cgraph_node
*node
)
2384 struct cgraph_node
*v
;
2385 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
2386 if (cgraph_will_be_removed_from_program_if_no_direct_calls (v
)
2387 && !cgraph_for_node_and_aliases (v
,
2388 has_undead_caller_from_outside_scc_p
,
2390 IPA_NODE_REF (v
)->node_dead
= 1;
2392 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
2393 if (!IPA_NODE_REF (v
)->node_dead
)
2394 spread_undeadness (v
);
2396 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2398 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
2399 if (IPA_NODE_REF (v
)->node_dead
)
2400 fprintf (dump_file
, " Marking node as dead: %s/%i.\n",
2401 cgraph_node_name (v
), v
->uid
);
2405 /* The decision stage. Iterate over the topological order of call graph nodes
2406 TOPO and make specialized clones if deemed beneficial. */
2409 ipcp_decision_stage (struct topo_info
*topo
)
2414 fprintf (dump_file
, "\nIPA decision stage:\n\n");
2416 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
2418 struct cgraph_node
*node
= topo
->order
[i
];
2419 bool change
= false, iterate
= true;
2423 struct cgraph_node
*v
;
2425 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
2426 if (cgraph_function_with_gimple_body_p (v
)
2427 && ipcp_versionable_function_p (v
))
2428 iterate
|= decide_whether_version_node (v
);
2433 identify_dead_nodes (node
);
2437 /* The IPCP driver. */
2442 struct cgraph_2edge_hook_list
*edge_duplication_hook_holder
;
2443 struct topo_info topo
;
2445 cgraph_remove_unreachable_nodes (true,dump_file
);
2446 ipa_check_create_node_params ();
2447 ipa_check_create_edge_args ();
2448 grow_next_edge_clone_vector ();
2449 edge_duplication_hook_holder
=
2450 cgraph_add_edge_duplication_hook (&ipcp_edge_duplication_hook
, NULL
);
2451 ipcp_values_pool
= create_alloc_pool ("IPA-CP values",
2452 sizeof (struct ipcp_value
), 32);
2453 ipcp_sources_pool
= create_alloc_pool ("IPA-CP value sources",
2454 sizeof (struct ipcp_value_source
), 64);
2457 fprintf (dump_file
, "\nIPA structures before propagation:\n");
2458 if (dump_flags
& TDF_DETAILS
)
2459 ipa_print_all_params (dump_file
);
2460 ipa_print_all_jump_functions (dump_file
);
2463 /* Topological sort. */
2464 build_toporder_info (&topo
);
2465 /* Do the interprocedural propagation. */
2466 ipcp_propagate_stage (&topo
);
2467 /* Decide what constant propagation and cloning should be performed. */
2468 ipcp_decision_stage (&topo
);
2470 /* Free all IPCP structures. */
2471 free_toporder_info (&topo
);
2472 VEC_free (cgraph_edge_p
, heap
, next_edge_clone
);
2473 cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder
);
2474 ipa_free_all_structures_after_ipa_cp ();
2476 fprintf (dump_file
, "\nIPA constant propagation end\n");
2480 /* Initialization and computation of IPCP data structures. This is the initial
2481 intraprocedural analysis of functions, which gathers information to be
2482 propagated later on. */
2485 ipcp_generate_summary (void)
2487 struct cgraph_node
*node
;
2490 fprintf (dump_file
, "\nIPA constant propagation start:\n");
2491 ipa_register_cgraph_hooks ();
2493 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
2495 /* Unreachable nodes should have been eliminated before ipcp. */
2496 gcc_assert (node
->needed
|| node
->reachable
);
2497 node
->local
.versionable
= tree_versionable_function_p (node
->decl
);
2498 ipa_analyze_node (node
);
2502 /* Write ipcp summary for nodes in SET. */
2505 ipcp_write_summary (cgraph_node_set set
,
2506 varpool_node_set vset ATTRIBUTE_UNUSED
)
2508 ipa_prop_write_jump_functions (set
);
2511 /* Read ipcp summary. */
2514 ipcp_read_summary (void)
2516 ipa_prop_read_jump_functions ();
2519 /* Gate for IPCP optimization. */
2522 cgraph_gate_cp (void)
2524 /* FIXME: We should remove the optimize check after we ensure we never run
2525 IPA passes when not optimizing. */
2526 return flag_ipa_cp
&& optimize
;
2529 struct ipa_opt_pass_d pass_ipa_cp
=
2534 cgraph_gate_cp
, /* gate */
2535 ipcp_driver
, /* execute */
2538 0, /* static_pass_number */
2539 TV_IPA_CONSTANT_PROP
, /* tv_id */
2540 0, /* properties_required */
2541 0, /* properties_provided */
2542 0, /* properties_destroyed */
2543 0, /* todo_flags_start */
2545 TODO_remove_functions
| TODO_ggc_collect
/* todo_flags_finish */
2547 ipcp_generate_summary
, /* generate_summary */
2548 ipcp_write_summary
, /* write_summary */
2549 ipcp_read_summary
, /* read_summary */
2550 NULL
, /* write_optimization_summary */
2551 NULL
, /* read_optimization_summary */
2552 NULL
, /* stmt_fixup */
2554 NULL
, /* function_transform */
2555 NULL
, /* variable_transform */