1 /* Interprocedural constant propagation
2 Copyright (C) 2005-2013 Free Software Foundation, Inc.
4 Contributed by Razya Ladelsky <RAZYA@il.ibm.com> and Martin Jambor
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
23 /* Interprocedural constant propagation (IPA-CP).
25 The goal of this transformation is to
27 1) discover functions which are always invoked with some arguments with the
28 same known constant values and modify the functions so that the
29 subsequent optimizations can take advantage of the knowledge, and
31 2) partial specialization - create specialized versions of functions
32 transformed in this way if some parameters are known constants only in
33 certain contexts but the estimated tradeoff between speedup and cost size
36 The algorithm also propagates types and attempts to perform type based
37 devirtualization. Types are propagated much like constants.
39 The algorithm basically consists of three stages. In the first, functions
40 are analyzed one at a time and jump functions are constructed for all known
41 call-sites. In the second phase, the pass propagates information from the
42 jump functions across the call to reveal what values are available at what
43 call sites, performs estimations of effects of known values on functions and
44 their callees, and finally decides what specialized extra versions should be
45 created. In the third, the special versions materialize and appropriate
48 The algorithm used is to a certain extent based on "Interprocedural Constant
49 Propagation", by David Callahan, Keith D Cooper, Ken Kennedy, Linda Torczon,
50 Comp86, pg 152-161 and "A Methodology for Procedure Cloning" by Keith D
51 Cooper, Mary W. Hall, and Ken Kennedy.
54 First stage - intraprocedural analysis
55 =======================================
57 This phase computes jump_function and modification flags.
59 A jump function for a call-site represents the values passed as an actual
60 arguments of a given call-site. In principle, there are three types of
63 Pass through - the caller's formal parameter is passed as an actual
64 argument, plus an operation on it can be performed.
65 Constant - a constant is passed as an actual argument.
66 Unknown - neither of the above.
68 All jump function types are described in detail in ipa-prop.h, together with
69 the data structures that represent them and methods of accessing them.
71 ipcp_generate_summary() is the main function of the first stage.
73 Second stage - interprocedural analysis
74 ========================================
76 This stage is itself divided into two phases. In the first, we propagate
77 known values over the call graph, in the second, we make cloning decisions.
78 It uses a different algorithm than the original Callahan's paper.
80 First, we traverse the functions topologically from callers to callees and,
81 for each strongly connected component (SCC), we propagate constants
82 according to previously computed jump functions. We also record what known
83 values depend on other known values and estimate local effects. Finally, we
84 propagate cumulative information about these effects from dependent values
85 to those on which they depend.
87 Second, we again traverse the call graph in the same topological order and
88 make clones for functions which we know are called with the same values in
89 all contexts and decide about extra specialized clones of functions just for
90 some contexts - these decisions are based on both local estimates and
91 cumulative estimates propagated from callees.
93 ipcp_propagate_stage() and ipcp_decision_stage() together constitute the
96 Third phase - materialization of clones, call statement updates.
97 ============================================
99 This stage is currently performed by call graph code (mainly in cgraphunit.c
100 and tree-inline.c) according to instructions inserted to the call graph by
105 #include "coretypes.h"
110 #include "ipa-prop.h"
111 #include "tree-flow.h"
112 #include "tree-pass.h"
114 #include "diagnostic.h"
115 #include "tree-pretty-print.h"
116 #include "tree-inline.h"
118 #include "ipa-inline.h"
119 #include "ipa-utils.h"
123 /* Describes a particular source for an IPA-CP value. */
125 struct ipcp_value_source
127 /* Aggregate offset of the source, negative if the source is scalar value of
128 the argument itself. */
129 HOST_WIDE_INT offset
;
130 /* The incoming edge that brought the value. */
131 struct cgraph_edge
*cs
;
132 /* If the jump function that resulted into his value was a pass-through or an
133 ancestor, this is the ipcp_value of the caller from which the described
134 value has been derived. Otherwise it is NULL. */
135 struct ipcp_value
*val
;
136 /* Next pointer in a linked list of sources of a value. */
137 struct ipcp_value_source
*next
;
138 /* If the jump function that resulted into his value was a pass-through or an
139 ancestor, this is the index of the parameter of the caller the jump
140 function references. */
144 /* Describes one particular value stored in struct ipcp_lattice. */
148 /* The actual value for the given parameter. This is either an IPA invariant
149 or a TREE_BINFO describing a type that can be used for
152 /* The list of sources from which this value originates. */
153 struct ipcp_value_source
*sources
;
154 /* Next pointers in a linked list of all values in a lattice. */
155 struct ipcp_value
*next
;
156 /* Next pointers in a linked list of values in a strongly connected component
158 struct ipcp_value
*scc_next
;
159 /* Next pointers in a linked list of SCCs of values sorted topologically
160 according their sources. */
161 struct ipcp_value
*topo_next
;
162 /* A specialized node created for this value, NULL if none has been (so far)
164 struct cgraph_node
*spec_node
;
165 /* Depth first search number and low link for topological sorting of
168 /* Time benefit and size cost that specializing the function for this value
169 would bring about in this function alone. */
170 int local_time_benefit
, local_size_cost
;
171 /* Time benefit and size cost that specializing the function for this value
172 can bring about in it's callees (transitively). */
173 int prop_time_benefit
, prop_size_cost
;
174 /* True if this valye is currently on the topo-sort stack. */
178 /* Lattice describing potential values of a formal parameter of a function, or
179 a part of an aggreagate. TOP is represented by a lattice with zero values
180 and with contains_variable and bottom flags cleared. BOTTOM is represented
181 by a lattice with the bottom flag set. In that case, values and
182 contains_variable flag should be disregarded. */
186 /* The list of known values and types in this lattice. Note that values are
187 not deallocated if a lattice is set to bottom because there may be value
188 sources referencing them. */
189 struct ipcp_value
*values
;
190 /* Number of known values and types in this lattice. */
192 /* The lattice contains a variable component (in addition to values). */
193 bool contains_variable
;
194 /* The value of the lattice is bottom (i.e. variable and unusable for any
199 /* Lattice with an offset to describe a part of an aggregate. */
201 struct ipcp_agg_lattice
: public ipcp_lattice
203 /* Offset that is being described by this lattice. */
204 HOST_WIDE_INT offset
;
205 /* Size so that we don't have to re-compute it every time we traverse the
206 list. Must correspond to TYPE_SIZE of all lat values. */
208 /* Next element of the linked list. */
209 struct ipcp_agg_lattice
*next
;
212 /* Structure containing lattices for a parameter itself and for pieces of
213 aggregates that are passed in the parameter or by a reference in a parameter
214 plus some other useful flags. */
216 struct ipcp_param_lattices
218 /* Lattice describing the value of the parameter itself. */
219 struct ipcp_lattice itself
;
220 /* Lattices describing aggregate parts. */
221 struct ipcp_agg_lattice
*aggs
;
222 /* Number of aggregate lattices */
224 /* True if aggregate data were passed by reference (as opposed to by
227 /* All aggregate lattices contain a variable component (in addition to
229 bool aggs_contain_variable
;
230 /* The value of all aggregate lattices is bottom (i.e. variable and unusable
231 for any propagation). */
234 /* There is a virtual call based on this parameter. */
238 /* Allocation pools for values and their sources in ipa-cp. */
240 alloc_pool ipcp_values_pool
;
241 alloc_pool ipcp_sources_pool
;
242 alloc_pool ipcp_agg_lattice_pool
;
244 /* Maximal count found in program. */
246 static gcov_type max_count
;
248 /* Original overall size of the program. */
250 static long overall_size
, max_new_size
;
252 /* Head of the linked list of topologically sorted values. */
254 static struct ipcp_value
*values_topo
;
256 /* Return the param lattices structure corresponding to the Ith formal
257 parameter of the function described by INFO. */
258 static inline struct ipcp_param_lattices
*
259 ipa_get_parm_lattices (struct ipa_node_params
*info
, int i
)
261 gcc_assert (i
>= 0 && i
< ipa_get_param_count (info
));
262 gcc_checking_assert (!info
->ipcp_orig_node
);
263 gcc_checking_assert (info
->lattices
);
264 return &(info
->lattices
[i
]);
267 /* Return the lattice corresponding to the scalar value of the Ith formal
268 parameter of the function described by INFO. */
269 static inline struct ipcp_lattice
*
270 ipa_get_scalar_lat (struct ipa_node_params
*info
, int i
)
272 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
273 return &plats
->itself
;
276 /* Return whether LAT is a lattice with a single constant and without an
280 ipa_lat_is_single_const (struct ipcp_lattice
*lat
)
283 || lat
->contains_variable
284 || lat
->values_count
!= 1)
290 /* Return true iff the CS is an edge within a strongly connected component as
291 computed by ipa_reduced_postorder. */
294 edge_within_scc (struct cgraph_edge
*cs
)
296 struct ipa_dfs_info
*caller_dfs
= (struct ipa_dfs_info
*) cs
->caller
->symbol
.aux
;
297 struct ipa_dfs_info
*callee_dfs
;
298 struct cgraph_node
*callee
= cgraph_function_node (cs
->callee
, NULL
);
300 callee_dfs
= (struct ipa_dfs_info
*) callee
->symbol
.aux
;
303 && caller_dfs
->scc_no
== callee_dfs
->scc_no
);
306 /* Print V which is extracted from a value in a lattice to F. */
309 print_ipcp_constant_value (FILE * f
, tree v
)
311 if (TREE_CODE (v
) == TREE_BINFO
)
313 fprintf (f
, "BINFO ");
314 print_generic_expr (f
, BINFO_TYPE (v
), 0);
316 else if (TREE_CODE (v
) == ADDR_EXPR
317 && TREE_CODE (TREE_OPERAND (v
, 0)) == CONST_DECL
)
320 print_generic_expr (f
, DECL_INITIAL (TREE_OPERAND (v
, 0)), 0);
323 print_generic_expr (f
, v
, 0);
326 /* Print a lattice LAT to F. */
329 print_lattice (FILE * f
, struct ipcp_lattice
*lat
,
330 bool dump_sources
, bool dump_benefits
)
332 struct ipcp_value
*val
;
337 fprintf (f
, "BOTTOM\n");
341 if (!lat
->values_count
&& !lat
->contains_variable
)
343 fprintf (f
, "TOP\n");
347 if (lat
->contains_variable
)
349 fprintf (f
, "VARIABLE");
355 for (val
= lat
->values
; val
; val
= val
->next
)
357 if (dump_benefits
&& prev
)
359 else if (!dump_benefits
&& prev
)
364 print_ipcp_constant_value (f
, val
->value
);
368 struct ipcp_value_source
*s
;
370 fprintf (f
, " [from:");
371 for (s
= val
->sources
; s
; s
= s
->next
)
372 fprintf (f
, " %i(%i)", s
->cs
->caller
->symbol
.order
,
378 fprintf (f
, " [loc_time: %i, loc_size: %i, "
379 "prop_time: %i, prop_size: %i]\n",
380 val
->local_time_benefit
, val
->local_size_cost
,
381 val
->prop_time_benefit
, val
->prop_size_cost
);
387 /* Print all ipcp_lattices of all functions to F. */
390 print_all_lattices (FILE * f
, bool dump_sources
, bool dump_benefits
)
392 struct cgraph_node
*node
;
395 fprintf (f
, "\nLattices:\n");
396 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
398 struct ipa_node_params
*info
;
400 info
= IPA_NODE_REF (node
);
401 fprintf (f
, " Node: %s/%i:\n", cgraph_node_name (node
),
403 count
= ipa_get_param_count (info
);
404 for (i
= 0; i
< count
; i
++)
406 struct ipcp_agg_lattice
*aglat
;
407 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
408 fprintf (f
, " param [%d]: ", i
);
409 print_lattice (f
, &plats
->itself
, dump_sources
, dump_benefits
);
411 if (plats
->virt_call
)
412 fprintf (f
, " virt_call flag set\n");
414 if (plats
->aggs_bottom
)
416 fprintf (f
, " AGGS BOTTOM\n");
419 if (plats
->aggs_contain_variable
)
420 fprintf (f
, " AGGS VARIABLE\n");
421 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
423 fprintf (f
, " %soffset " HOST_WIDE_INT_PRINT_DEC
": ",
424 plats
->aggs_by_ref
? "ref " : "", aglat
->offset
);
425 print_lattice (f
, aglat
, dump_sources
, dump_benefits
);
431 /* Determine whether it is at all technically possible to create clones of NODE
432 and store this information in the ipa_node_params structure associated
436 determine_versionability (struct cgraph_node
*node
)
438 const char *reason
= NULL
;
440 /* There are a number of generic reasons functions cannot be versioned. We
441 also cannot remove parameters if there are type attributes such as fnspec
443 if (node
->symbol
.alias
|| node
->thunk
.thunk_p
)
444 reason
= "alias or thunk";
445 else if (!node
->local
.versionable
)
446 reason
= "not a tree_versionable_function";
447 else if (cgraph_function_body_availability (node
) <= AVAIL_OVERWRITABLE
)
448 reason
= "insufficient body availability";
450 if (reason
&& dump_file
&& !node
->symbol
.alias
&& !node
->thunk
.thunk_p
)
451 fprintf (dump_file
, "Function %s/%i is not versionable, reason: %s.\n",
452 cgraph_node_name (node
), node
->symbol
.order
, reason
);
454 node
->local
.versionable
= (reason
== NULL
);
457 /* Return true if it is at all technically possible to create clones of a
461 ipcp_versionable_function_p (struct cgraph_node
*node
)
463 return node
->local
.versionable
;
466 /* Structure holding accumulated information about callers of a node. */
468 struct caller_statistics
471 int n_calls
, n_hot_calls
, freq_sum
;
474 /* Initialize fields of STAT to zeroes. */
477 init_caller_stats (struct caller_statistics
*stats
)
479 stats
->count_sum
= 0;
481 stats
->n_hot_calls
= 0;
485 /* Worker callback of cgraph_for_node_and_aliases accumulating statistics of
486 non-thunk incoming edges to NODE. */
489 gather_caller_stats (struct cgraph_node
*node
, void *data
)
491 struct caller_statistics
*stats
= (struct caller_statistics
*) data
;
492 struct cgraph_edge
*cs
;
494 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
495 if (cs
->caller
->thunk
.thunk_p
)
496 cgraph_for_node_and_aliases (cs
->caller
, gather_caller_stats
,
500 stats
->count_sum
+= cs
->count
;
501 stats
->freq_sum
+= cs
->frequency
;
503 if (cgraph_maybe_hot_edge_p (cs
))
504 stats
->n_hot_calls
++;
510 /* Return true if this NODE is viable candidate for cloning. */
513 ipcp_cloning_candidate_p (struct cgraph_node
*node
)
515 struct caller_statistics stats
;
517 gcc_checking_assert (cgraph_function_with_gimple_body_p (node
));
519 if (!flag_ipa_cp_clone
)
522 fprintf (dump_file
, "Not considering %s for cloning; "
523 "-fipa-cp-clone disabled.\n",
524 cgraph_node_name (node
));
528 if (!optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node
->symbol
.decl
)))
531 fprintf (dump_file
, "Not considering %s for cloning; "
532 "optimizing it for size.\n",
533 cgraph_node_name (node
));
537 init_caller_stats (&stats
);
538 cgraph_for_node_and_aliases (node
, gather_caller_stats
, &stats
, false);
540 if (inline_summary (node
)->self_size
< stats
.n_calls
)
543 fprintf (dump_file
, "Considering %s for cloning; code might shrink.\n",
544 cgraph_node_name (node
));
548 /* When profile is available and function is hot, propagate into it even if
549 calls seems cold; constant propagation can improve function's speed
553 if (stats
.count_sum
> node
->count
* 90 / 100)
556 fprintf (dump_file
, "Considering %s for cloning; "
557 "usually called directly.\n",
558 cgraph_node_name (node
));
562 if (!stats
.n_hot_calls
)
565 fprintf (dump_file
, "Not considering %s for cloning; no hot calls.\n",
566 cgraph_node_name (node
));
570 fprintf (dump_file
, "Considering %s for cloning.\n",
571 cgraph_node_name (node
));
575 /* Arrays representing a topological ordering of call graph nodes and a stack
576 of noes used during constant propagation. */
580 struct cgraph_node
**order
;
581 struct cgraph_node
**stack
;
582 int nnodes
, stack_top
;
585 /* Allocate the arrays in TOPO and topologically sort the nodes into order. */
588 build_toporder_info (struct topo_info
*topo
)
590 topo
->order
= XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
591 topo
->stack
= XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
593 topo
->nnodes
= ipa_reduced_postorder (topo
->order
, true, true, NULL
);
596 /* Free information about strongly connected components and the arrays in
600 free_toporder_info (struct topo_info
*topo
)
602 ipa_free_postorder_info ();
607 /* Add NODE to the stack in TOPO, unless it is already there. */
610 push_node_to_stack (struct topo_info
*topo
, struct cgraph_node
*node
)
612 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
613 if (info
->node_enqueued
)
615 info
->node_enqueued
= 1;
616 topo
->stack
[topo
->stack_top
++] = node
;
619 /* Pop a node from the stack in TOPO and return it or return NULL if the stack
622 static struct cgraph_node
*
623 pop_node_from_stack (struct topo_info
*topo
)
627 struct cgraph_node
*node
;
629 node
= topo
->stack
[topo
->stack_top
];
630 IPA_NODE_REF (node
)->node_enqueued
= 0;
637 /* Set lattice LAT to bottom and return true if it previously was not set as
641 set_lattice_to_bottom (struct ipcp_lattice
*lat
)
643 bool ret
= !lat
->bottom
;
648 /* Mark lattice as containing an unknown value and return true if it previously
649 was not marked as such. */
652 set_lattice_contains_variable (struct ipcp_lattice
*lat
)
654 bool ret
= !lat
->contains_variable
;
655 lat
->contains_variable
= true;
659 /* Set all aggegate lattices in PLATS to bottom and return true if they were
660 not previously set as such. */
663 set_agg_lats_to_bottom (struct ipcp_param_lattices
*plats
)
665 bool ret
= !plats
->aggs_bottom
;
666 plats
->aggs_bottom
= true;
670 /* Mark all aggegate lattices in PLATS as containing an unknown value and
671 return true if they were not previously marked as such. */
674 set_agg_lats_contain_variable (struct ipcp_param_lattices
*plats
)
676 bool ret
= !plats
->aggs_contain_variable
;
677 plats
->aggs_contain_variable
= true;
681 /* Mark bot aggregate and scalar lattices as containing an unknown variable,
682 return true is any of them has not been marked as such so far. */
685 set_all_contains_variable (struct ipcp_param_lattices
*plats
)
687 bool ret
= !plats
->itself
.contains_variable
|| !plats
->aggs_contain_variable
;
688 plats
->itself
.contains_variable
= true;
689 plats
->aggs_contain_variable
= true;
693 /* Initialize ipcp_lattices. */
696 initialize_node_lattices (struct cgraph_node
*node
)
698 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
699 struct cgraph_edge
*ie
;
700 bool disable
= false, variable
= false;
703 gcc_checking_assert (cgraph_function_with_gimple_body_p (node
));
704 if (!node
->local
.local
)
706 /* When cloning is allowed, we can assume that externally visible
707 functions are not called. We will compensate this by cloning
709 if (ipcp_versionable_function_p (node
)
710 && ipcp_cloning_candidate_p (node
))
716 if (disable
|| variable
)
718 for (i
= 0; i
< ipa_get_param_count (info
) ; i
++)
720 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
723 set_lattice_to_bottom (&plats
->itself
);
724 set_agg_lats_to_bottom (plats
);
727 set_all_contains_variable (plats
);
729 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
730 && !node
->symbol
.alias
&& !node
->thunk
.thunk_p
)
731 fprintf (dump_file
, "Marking all lattices of %s/%i as %s\n",
732 cgraph_node_name (node
), node
->symbol
.order
,
733 disable
? "BOTTOM" : "VARIABLE");
736 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
737 if (ie
->indirect_info
->polymorphic
)
739 gcc_checking_assert (ie
->indirect_info
->param_index
>= 0);
740 ipa_get_parm_lattices (info
,
741 ie
->indirect_info
->param_index
)->virt_call
= 1;
745 /* Return the result of a (possibly arithmetic) pass through jump function
746 JFUNC on the constant value INPUT. Return NULL_TREE if that cannot be
747 determined or itself is considered an interprocedural invariant. */
750 ipa_get_jf_pass_through_result (struct ipa_jump_func
*jfunc
, tree input
)
754 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
756 else if (TREE_CODE (input
) == TREE_BINFO
)
759 gcc_checking_assert (is_gimple_ip_invariant (input
));
760 if (TREE_CODE_CLASS (ipa_get_jf_pass_through_operation (jfunc
))
762 restype
= boolean_type_node
;
764 restype
= TREE_TYPE (input
);
765 res
= fold_binary (ipa_get_jf_pass_through_operation (jfunc
), restype
,
766 input
, ipa_get_jf_pass_through_operand (jfunc
));
768 if (res
&& !is_gimple_ip_invariant (res
))
774 /* Return the result of an ancestor jump function JFUNC on the constant value
775 INPUT. Return NULL_TREE if that cannot be determined. */
778 ipa_get_jf_ancestor_result (struct ipa_jump_func
*jfunc
, tree input
)
780 if (TREE_CODE (input
) == TREE_BINFO
)
781 return get_binfo_at_offset (input
,
782 ipa_get_jf_ancestor_offset (jfunc
),
783 ipa_get_jf_ancestor_type (jfunc
));
784 else if (TREE_CODE (input
) == ADDR_EXPR
)
786 tree t
= TREE_OPERAND (input
, 0);
787 t
= build_ref_for_offset (EXPR_LOCATION (t
), t
,
788 ipa_get_jf_ancestor_offset (jfunc
),
789 ipa_get_jf_ancestor_type (jfunc
), NULL
, false);
790 return build_fold_addr_expr (t
);
796 /* Determine whether JFUNC evaluates to a known value (that is either a
797 constant or a binfo) and if so, return it. Otherwise return NULL. INFO
798 describes the caller node so that pass-through jump functions can be
802 ipa_value_from_jfunc (struct ipa_node_params
*info
, struct ipa_jump_func
*jfunc
)
804 if (jfunc
->type
== IPA_JF_CONST
)
805 return ipa_get_jf_constant (jfunc
);
806 else if (jfunc
->type
== IPA_JF_KNOWN_TYPE
)
807 return ipa_binfo_from_known_type_jfunc (jfunc
);
808 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
809 || jfunc
->type
== IPA_JF_ANCESTOR
)
814 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
815 idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
817 idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
819 if (info
->ipcp_orig_node
)
820 input
= info
->known_vals
[idx
];
823 struct ipcp_lattice
*lat
;
827 gcc_checking_assert (!flag_ipa_cp
);
830 lat
= ipa_get_scalar_lat (info
, idx
);
831 if (!ipa_lat_is_single_const (lat
))
833 input
= lat
->values
->value
;
839 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
840 return ipa_get_jf_pass_through_result (jfunc
, input
);
842 return ipa_get_jf_ancestor_result (jfunc
, input
);
849 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
850 bottom, not containing a variable component and without any known value at
854 ipcp_verify_propagated_values (void)
856 struct cgraph_node
*node
;
858 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
860 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
861 int i
, count
= ipa_get_param_count (info
);
863 for (i
= 0; i
< count
; i
++)
865 struct ipcp_lattice
*lat
= ipa_get_scalar_lat (info
, i
);
868 && !lat
->contains_variable
869 && lat
->values_count
== 0)
873 fprintf (dump_file
, "\nIPA lattices after constant "
875 print_all_lattices (dump_file
, true, false);
884 /* Return true iff X and Y should be considered equal values by IPA-CP. */
887 values_equal_for_ipcp_p (tree x
, tree y
)
889 gcc_checking_assert (x
!= NULL_TREE
&& y
!= NULL_TREE
);
894 if (TREE_CODE (x
) == TREE_BINFO
|| TREE_CODE (y
) == TREE_BINFO
)
897 if (TREE_CODE (x
) == ADDR_EXPR
898 && TREE_CODE (y
) == ADDR_EXPR
899 && TREE_CODE (TREE_OPERAND (x
, 0)) == CONST_DECL
900 && TREE_CODE (TREE_OPERAND (y
, 0)) == CONST_DECL
)
901 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x
, 0)),
902 DECL_INITIAL (TREE_OPERAND (y
, 0)), 0);
904 return operand_equal_p (x
, y
, 0);
907 /* Add a new value source to VAL, marking that a value comes from edge CS and
908 (if the underlying jump function is a pass-through or an ancestor one) from
909 a caller value SRC_VAL of a caller parameter described by SRC_INDEX. OFFSET
910 is negative if the source was the scalar value of the parameter itself or
911 the offset within an aggregate. */
914 add_value_source (struct ipcp_value
*val
, struct cgraph_edge
*cs
,
915 struct ipcp_value
*src_val
, int src_idx
, HOST_WIDE_INT offset
)
917 struct ipcp_value_source
*src
;
919 src
= (struct ipcp_value_source
*) pool_alloc (ipcp_sources_pool
);
920 src
->offset
= offset
;
923 src
->index
= src_idx
;
925 src
->next
= val
->sources
;
929 /* Try to add NEWVAL to LAT, potentially creating a new struct ipcp_value for
930 it. CS, SRC_VAL SRC_INDEX and OFFSET are meant for add_value_source and
931 have the same meaning. */
934 add_value_to_lattice (struct ipcp_lattice
*lat
, tree newval
,
935 struct cgraph_edge
*cs
, struct ipcp_value
*src_val
,
936 int src_idx
, HOST_WIDE_INT offset
)
938 struct ipcp_value
*val
;
943 for (val
= lat
->values
; val
; val
= val
->next
)
944 if (values_equal_for_ipcp_p (val
->value
, newval
))
946 if (edge_within_scc (cs
))
948 struct ipcp_value_source
*s
;
949 for (s
= val
->sources
; s
; s
= s
->next
)
956 add_value_source (val
, cs
, src_val
, src_idx
, offset
);
960 if (lat
->values_count
== PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE
))
962 /* We can only free sources, not the values themselves, because sources
963 of other values in this this SCC might point to them. */
964 for (val
= lat
->values
; val
; val
= val
->next
)
968 struct ipcp_value_source
*src
= val
->sources
;
969 val
->sources
= src
->next
;
970 pool_free (ipcp_sources_pool
, src
);
975 return set_lattice_to_bottom (lat
);
979 val
= (struct ipcp_value
*) pool_alloc (ipcp_values_pool
);
980 memset (val
, 0, sizeof (*val
));
982 add_value_source (val
, cs
, src_val
, src_idx
, offset
);
984 val
->next
= lat
->values
;
989 /* Like above but passes a special value of offset to distinguish that the
990 origin is the scalar value of the parameter rather than a part of an
994 add_scalar_value_to_lattice (struct ipcp_lattice
*lat
, tree newval
,
995 struct cgraph_edge
*cs
,
996 struct ipcp_value
*src_val
, int src_idx
)
998 return add_value_to_lattice (lat
, newval
, cs
, src_val
, src_idx
, -1);
1001 /* Propagate values through a pass-through jump function JFUNC associated with
1002 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1003 is the index of the source parameter. */
1006 propagate_vals_accross_pass_through (struct cgraph_edge
*cs
,
1007 struct ipa_jump_func
*jfunc
,
1008 struct ipcp_lattice
*src_lat
,
1009 struct ipcp_lattice
*dest_lat
,
1012 struct ipcp_value
*src_val
;
1015 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
1016 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1017 ret
|= add_scalar_value_to_lattice (dest_lat
, src_val
->value
, cs
,
1019 /* Do not create new values when propagating within an SCC because if there
1020 are arithmetic functions with circular dependencies, there is infinite
1021 number of them and we would just make lattices bottom. */
1022 else if (edge_within_scc (cs
))
1023 ret
= set_lattice_contains_variable (dest_lat
);
1025 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1027 tree cstval
= src_val
->value
;
1029 if (TREE_CODE (cstval
) == TREE_BINFO
)
1031 ret
|= set_lattice_contains_variable (dest_lat
);
1034 cstval
= ipa_get_jf_pass_through_result (jfunc
, cstval
);
1037 ret
|= add_scalar_value_to_lattice (dest_lat
, cstval
, cs
, src_val
,
1040 ret
|= set_lattice_contains_variable (dest_lat
);
1046 /* Propagate values through an ancestor jump function JFUNC associated with
1047 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1048 is the index of the source parameter. */
1051 propagate_vals_accross_ancestor (struct cgraph_edge
*cs
,
1052 struct ipa_jump_func
*jfunc
,
1053 struct ipcp_lattice
*src_lat
,
1054 struct ipcp_lattice
*dest_lat
,
1057 struct ipcp_value
*src_val
;
1060 if (edge_within_scc (cs
))
1061 return set_lattice_contains_variable (dest_lat
);
1063 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1065 tree t
= ipa_get_jf_ancestor_result (jfunc
, src_val
->value
);
1068 ret
|= add_scalar_value_to_lattice (dest_lat
, t
, cs
, src_val
, src_idx
);
1070 ret
|= set_lattice_contains_variable (dest_lat
);
1076 /* Propagate scalar values across jump function JFUNC that is associated with
1077 edge CS and put the values into DEST_LAT. */
1080 propagate_scalar_accross_jump_function (struct cgraph_edge
*cs
,
1081 struct ipa_jump_func
*jfunc
,
1082 struct ipcp_lattice
*dest_lat
)
1084 if (dest_lat
->bottom
)
1087 if (jfunc
->type
== IPA_JF_CONST
1088 || jfunc
->type
== IPA_JF_KNOWN_TYPE
)
1092 if (jfunc
->type
== IPA_JF_KNOWN_TYPE
)
1094 val
= ipa_binfo_from_known_type_jfunc (jfunc
);
1096 return set_lattice_contains_variable (dest_lat
);
1099 val
= ipa_get_jf_constant (jfunc
);
1100 return add_scalar_value_to_lattice (dest_lat
, val
, cs
, NULL
, 0);
1102 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1103 || jfunc
->type
== IPA_JF_ANCESTOR
)
1105 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1106 struct ipcp_lattice
*src_lat
;
1110 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1111 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1113 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1115 src_lat
= ipa_get_scalar_lat (caller_info
, src_idx
);
1116 if (src_lat
->bottom
)
1117 return set_lattice_contains_variable (dest_lat
);
1119 /* If we would need to clone the caller and cannot, do not propagate. */
1120 if (!ipcp_versionable_function_p (cs
->caller
)
1121 && (src_lat
->contains_variable
1122 || (src_lat
->values_count
> 1)))
1123 return set_lattice_contains_variable (dest_lat
);
1125 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1126 ret
= propagate_vals_accross_pass_through (cs
, jfunc
, src_lat
,
1129 ret
= propagate_vals_accross_ancestor (cs
, jfunc
, src_lat
, dest_lat
,
1132 if (src_lat
->contains_variable
)
1133 ret
|= set_lattice_contains_variable (dest_lat
);
1138 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1139 use it for indirect inlining), we should propagate them too. */
1140 return set_lattice_contains_variable (dest_lat
);
1143 /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
1144 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
1145 other cases, return false). If there are no aggregate items, set
1146 aggs_by_ref to NEW_AGGS_BY_REF. */
1149 set_check_aggs_by_ref (struct ipcp_param_lattices
*dest_plats
,
1150 bool new_aggs_by_ref
)
1152 if (dest_plats
->aggs
)
1154 if (dest_plats
->aggs_by_ref
!= new_aggs_by_ref
)
1156 set_agg_lats_to_bottom (dest_plats
);
1161 dest_plats
->aggs_by_ref
= new_aggs_by_ref
;
1165 /* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
1166 already existing lattice for the given OFFSET and SIZE, marking all skipped
1167 lattices as containing variable and checking for overlaps. If there is no
1168 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
1169 it with offset, size and contains_variable to PRE_EXISTING, and return true,
1170 unless there are too many already. If there are two many, return false. If
1171 there are overlaps turn whole DEST_PLATS to bottom and return false. If any
1172 skipped lattices were newly marked as containing variable, set *CHANGE to
1176 merge_agg_lats_step (struct ipcp_param_lattices
*dest_plats
,
1177 HOST_WIDE_INT offset
, HOST_WIDE_INT val_size
,
1178 struct ipcp_agg_lattice
***aglat
,
1179 bool pre_existing
, bool *change
)
1181 gcc_checking_assert (offset
>= 0);
1183 while (**aglat
&& (**aglat
)->offset
< offset
)
1185 if ((**aglat
)->offset
+ (**aglat
)->size
> offset
)
1187 set_agg_lats_to_bottom (dest_plats
);
1190 *change
|= set_lattice_contains_variable (**aglat
);
1191 *aglat
= &(**aglat
)->next
;
1194 if (**aglat
&& (**aglat
)->offset
== offset
)
1196 if ((**aglat
)->size
!= val_size
1198 && (**aglat
)->next
->offset
< offset
+ val_size
))
1200 set_agg_lats_to_bottom (dest_plats
);
1203 gcc_checking_assert (!(**aglat
)->next
1204 || (**aglat
)->next
->offset
>= offset
+ val_size
);
1209 struct ipcp_agg_lattice
*new_al
;
1211 if (**aglat
&& (**aglat
)->offset
< offset
+ val_size
)
1213 set_agg_lats_to_bottom (dest_plats
);
1216 if (dest_plats
->aggs_count
== PARAM_VALUE (PARAM_IPA_MAX_AGG_ITEMS
))
1218 dest_plats
->aggs_count
++;
1219 new_al
= (struct ipcp_agg_lattice
*) pool_alloc (ipcp_agg_lattice_pool
);
1220 memset (new_al
, 0, sizeof (*new_al
));
1222 new_al
->offset
= offset
;
1223 new_al
->size
= val_size
;
1224 new_al
->contains_variable
= pre_existing
;
1226 new_al
->next
= **aglat
;
1232 /* Set all AGLAT and all other aggregate lattices reachable by next pointers as
1233 containing an unknown value. */
1236 set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice
*aglat
)
1241 ret
|= set_lattice_contains_variable (aglat
);
1242 aglat
= aglat
->next
;
1247 /* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
1248 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source
1249 parameter used for lattice value sources. Return true if DEST_PLATS changed
1253 merge_aggregate_lattices (struct cgraph_edge
*cs
,
1254 struct ipcp_param_lattices
*dest_plats
,
1255 struct ipcp_param_lattices
*src_plats
,
1256 int src_idx
, HOST_WIDE_INT offset_delta
)
1258 bool pre_existing
= dest_plats
->aggs
!= NULL
;
1259 struct ipcp_agg_lattice
**dst_aglat
;
1262 if (set_check_aggs_by_ref (dest_plats
, src_plats
->aggs_by_ref
))
1264 if (src_plats
->aggs_bottom
)
1265 return set_agg_lats_contain_variable (dest_plats
);
1266 if (src_plats
->aggs_contain_variable
)
1267 ret
|= set_agg_lats_contain_variable (dest_plats
);
1268 dst_aglat
= &dest_plats
->aggs
;
1270 for (struct ipcp_agg_lattice
*src_aglat
= src_plats
->aggs
;
1272 src_aglat
= src_aglat
->next
)
1274 HOST_WIDE_INT new_offset
= src_aglat
->offset
- offset_delta
;
1278 if (merge_agg_lats_step (dest_plats
, new_offset
, src_aglat
->size
,
1279 &dst_aglat
, pre_existing
, &ret
))
1281 struct ipcp_agg_lattice
*new_al
= *dst_aglat
;
1283 dst_aglat
= &(*dst_aglat
)->next
;
1284 if (src_aglat
->bottom
)
1286 ret
|= set_lattice_contains_variable (new_al
);
1289 if (src_aglat
->contains_variable
)
1290 ret
|= set_lattice_contains_variable (new_al
);
1291 for (struct ipcp_value
*val
= src_aglat
->values
;
1294 ret
|= add_value_to_lattice (new_al
, val
->value
, cs
, val
, src_idx
,
1297 else if (dest_plats
->aggs_bottom
)
1300 ret
|= set_chain_of_aglats_contains_variable (*dst_aglat
);
1304 /* Determine whether there is anything to propagate FROM SRC_PLATS through a
1305 pass-through JFUNC and if so, whether it has conform and conforms to the
1306 rules about propagating values passed by reference. */
1309 agg_pass_through_permissible_p (struct ipcp_param_lattices
*src_plats
,
1310 struct ipa_jump_func
*jfunc
)
1312 return src_plats
->aggs
1313 && (!src_plats
->aggs_by_ref
1314 || ipa_get_jf_pass_through_agg_preserved (jfunc
));
1317 /* Propagate scalar values across jump function JFUNC that is associated with
1318 edge CS and put the values into DEST_LAT. */
1321 propagate_aggs_accross_jump_function (struct cgraph_edge
*cs
,
1322 struct ipa_jump_func
*jfunc
,
1323 struct ipcp_param_lattices
*dest_plats
)
1327 if (dest_plats
->aggs_bottom
)
1330 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1331 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
1333 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1334 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1335 struct ipcp_param_lattices
*src_plats
;
1337 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
1338 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
1340 /* Currently we do not produce clobber aggregate jump
1341 functions, replace with merging when we do. */
1342 gcc_assert (!jfunc
->agg
.items
);
1343 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
,
1347 ret
|= set_agg_lats_contain_variable (dest_plats
);
1349 else if (jfunc
->type
== IPA_JF_ANCESTOR
1350 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
1352 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1353 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1354 struct ipcp_param_lattices
*src_plats
;
1356 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
1357 if (src_plats
->aggs
&& src_plats
->aggs_by_ref
)
1359 /* Currently we do not produce clobber aggregate jump
1360 functions, replace with merging when we do. */
1361 gcc_assert (!jfunc
->agg
.items
);
1362 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
, src_idx
,
1363 ipa_get_jf_ancestor_offset (jfunc
));
1365 else if (!src_plats
->aggs_by_ref
)
1366 ret
|= set_agg_lats_to_bottom (dest_plats
);
1368 ret
|= set_agg_lats_contain_variable (dest_plats
);
1370 else if (jfunc
->agg
.items
)
1372 bool pre_existing
= dest_plats
->aggs
!= NULL
;
1373 struct ipcp_agg_lattice
**aglat
= &dest_plats
->aggs
;
1374 struct ipa_agg_jf_item
*item
;
1377 if (set_check_aggs_by_ref (dest_plats
, jfunc
->agg
.by_ref
))
1380 FOR_EACH_VEC_ELT (*jfunc
->agg
.items
, i
, item
)
1382 HOST_WIDE_INT val_size
;
1384 if (item
->offset
< 0)
1386 gcc_checking_assert (is_gimple_ip_invariant (item
->value
));
1387 val_size
= tree_low_cst (TYPE_SIZE (TREE_TYPE (item
->value
)), 1);
1389 if (merge_agg_lats_step (dest_plats
, item
->offset
, val_size
,
1390 &aglat
, pre_existing
, &ret
))
1392 ret
|= add_value_to_lattice (*aglat
, item
->value
, cs
, NULL
, 0, 0);
1393 aglat
= &(*aglat
)->next
;
1395 else if (dest_plats
->aggs_bottom
)
1399 ret
|= set_chain_of_aglats_contains_variable (*aglat
);
1402 ret
|= set_agg_lats_contain_variable (dest_plats
);
1407 /* Propagate constants from the caller to the callee of CS. INFO describes the
1411 propagate_constants_accross_call (struct cgraph_edge
*cs
)
1413 struct ipa_node_params
*callee_info
;
1414 enum availability availability
;
1415 struct cgraph_node
*callee
, *alias_or_thunk
;
1416 struct ipa_edge_args
*args
;
1418 int i
, args_count
, parms_count
;
1420 callee
= cgraph_function_node (cs
->callee
, &availability
);
1421 if (!callee
->symbol
.definition
)
1423 gcc_checking_assert (cgraph_function_with_gimple_body_p (callee
));
1424 callee_info
= IPA_NODE_REF (callee
);
1426 args
= IPA_EDGE_REF (cs
);
1427 args_count
= ipa_get_cs_argument_count (args
);
1428 parms_count
= ipa_get_param_count (callee_info
);
1430 /* If this call goes through a thunk we must not propagate to the first (0th)
1431 parameter. However, we might need to uncover a thunk from below a series
1432 of aliases first. */
1433 alias_or_thunk
= cs
->callee
;
1434 while (alias_or_thunk
->symbol
.alias
)
1435 alias_or_thunk
= cgraph_alias_target (alias_or_thunk
);
1436 if (alias_or_thunk
->thunk
.thunk_p
)
1438 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
1445 for (; (i
< args_count
) && (i
< parms_count
); i
++)
1447 struct ipa_jump_func
*jump_func
= ipa_get_ith_jump_func (args
, i
);
1448 struct ipcp_param_lattices
*dest_plats
;
1450 dest_plats
= ipa_get_parm_lattices (callee_info
, i
);
1451 if (availability
== AVAIL_OVERWRITABLE
)
1452 ret
|= set_all_contains_variable (dest_plats
);
1455 ret
|= propagate_scalar_accross_jump_function (cs
, jump_func
,
1456 &dest_plats
->itself
);
1457 ret
|= propagate_aggs_accross_jump_function (cs
, jump_func
,
1461 for (; i
< parms_count
; i
++)
1462 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
, i
));
1467 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
1468 (which can contain both constants and binfos), KNOWN_BINFOS, KNOWN_AGGS or
1469 AGG_REPS return the destination. The latter three can be NULL. If AGG_REPS
1470 is not NULL, KNOWN_AGGS is ignored. */
1473 ipa_get_indirect_edge_target_1 (struct cgraph_edge
*ie
,
1474 vec
<tree
> known_vals
,
1475 vec
<tree
> known_binfos
,
1476 vec
<ipa_agg_jump_function_p
> known_aggs
,
1477 struct ipa_agg_replacement_value
*agg_reps
)
1479 int param_index
= ie
->indirect_info
->param_index
;
1480 HOST_WIDE_INT token
, anc_offset
;
1484 if (param_index
== -1
1485 || known_vals
.length () <= (unsigned int) param_index
)
1488 if (!ie
->indirect_info
->polymorphic
)
1492 if (ie
->indirect_info
->agg_contents
)
1499 if (agg_reps
->index
== param_index
1500 && agg_reps
->offset
== ie
->indirect_info
->offset
1501 && agg_reps
->by_ref
== ie
->indirect_info
->by_ref
)
1503 t
= agg_reps
->value
;
1506 agg_reps
= agg_reps
->next
;
1509 else if (known_aggs
.length () > (unsigned int) param_index
)
1511 struct ipa_agg_jump_function
*agg
;
1512 agg
= known_aggs
[param_index
];
1513 t
= ipa_find_agg_cst_for_param (agg
, ie
->indirect_info
->offset
,
1514 ie
->indirect_info
->by_ref
);
1520 t
= known_vals
[param_index
];
1523 TREE_CODE (t
) == ADDR_EXPR
1524 && TREE_CODE (TREE_OPERAND (t
, 0)) == FUNCTION_DECL
)
1525 return TREE_OPERAND (t
, 0);
1530 gcc_assert (!ie
->indirect_info
->agg_contents
);
1531 token
= ie
->indirect_info
->otr_token
;
1532 anc_offset
= ie
->indirect_info
->offset
;
1533 otr_type
= ie
->indirect_info
->otr_type
;
1535 t
= known_vals
[param_index
];
1536 if (!t
&& known_binfos
.length () > (unsigned int) param_index
)
1537 t
= known_binfos
[param_index
];
1541 if (TREE_CODE (t
) != TREE_BINFO
)
1544 binfo
= gimple_extract_devirt_binfo_from_cst (t
);
1547 binfo
= get_binfo_at_offset (binfo
, anc_offset
, otr_type
);
1550 return gimple_get_virt_method_for_binfo (token
, binfo
);
1556 binfo
= get_binfo_at_offset (t
, anc_offset
, otr_type
);
1559 return gimple_get_virt_method_for_binfo (token
, binfo
);
1564 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
1565 (which can contain both constants and binfos), KNOWN_BINFOS (which can be
1566 NULL) or KNOWN_AGGS (which also can be NULL) return the destination. */
1569 ipa_get_indirect_edge_target (struct cgraph_edge
*ie
,
1570 vec
<tree
> known_vals
,
1571 vec
<tree
> known_binfos
,
1572 vec
<ipa_agg_jump_function_p
> known_aggs
)
1574 return ipa_get_indirect_edge_target_1 (ie
, known_vals
, known_binfos
,
1578 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
1579 and KNOWN_BINFOS. */
1582 devirtualization_time_bonus (struct cgraph_node
*node
,
1583 vec
<tree
> known_csts
,
1584 vec
<tree
> known_binfos
,
1585 vec
<ipa_agg_jump_function_p
> known_aggs
)
1587 struct cgraph_edge
*ie
;
1590 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
1592 struct cgraph_node
*callee
;
1593 struct inline_summary
*isummary
;
1596 target
= ipa_get_indirect_edge_target (ie
, known_csts
, known_binfos
,
1601 /* Only bare minimum benefit for clearly un-inlineable targets. */
1603 callee
= cgraph_get_node (target
);
1604 if (!callee
|| !callee
->symbol
.definition
)
1606 isummary
= inline_summary (callee
);
1607 if (!isummary
->inlinable
)
1610 /* FIXME: The values below need re-considering and perhaps also
1611 integrating into the cost metrics, at lest in some very basic way. */
1612 if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 4)
1614 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 2)
1616 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
1617 || DECL_DECLARED_INLINE_P (callee
->symbol
.decl
))
1624 /* Return time bonus incurred because of HINTS. */
1627 hint_time_bonus (inline_hints hints
)
1630 if (hints
& (INLINE_HINT_loop_iterations
| INLINE_HINT_loop_stride
))
1631 result
+= PARAM_VALUE (PARAM_IPA_CP_LOOP_HINT_BONUS
);
1632 if (hints
& INLINE_HINT_array_index
)
1633 result
+= PARAM_VALUE (PARAM_IPA_CP_ARRAY_INDEX_HINT_BONUS
);
1637 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
1638 and SIZE_COST and with the sum of frequencies of incoming edges to the
1639 potential new clone in FREQUENCIES. */
1642 good_cloning_opportunity_p (struct cgraph_node
*node
, int time_benefit
,
1643 int freq_sum
, gcov_type count_sum
, int size_cost
)
1645 if (time_benefit
== 0
1646 || !flag_ipa_cp_clone
1647 || !optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node
->symbol
.decl
)))
1650 gcc_assert (size_cost
> 0);
1654 int factor
= (count_sum
* 1000) / max_count
;
1655 HOST_WIDEST_INT evaluation
= (((HOST_WIDEST_INT
) time_benefit
* factor
)
1658 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1659 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
1660 "size: %i, count_sum: " HOST_WIDE_INT_PRINT_DEC
1661 ") -> evaluation: " HOST_WIDEST_INT_PRINT_DEC
1662 ", threshold: %i\n",
1663 time_benefit
, size_cost
, (HOST_WIDE_INT
) count_sum
,
1664 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
1666 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
1670 HOST_WIDEST_INT evaluation
= (((HOST_WIDEST_INT
) time_benefit
* freq_sum
)
1673 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1674 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
1675 "size: %i, freq_sum: %i) -> evaluation: "
1676 HOST_WIDEST_INT_PRINT_DEC
", threshold: %i\n",
1677 time_benefit
, size_cost
, freq_sum
, evaluation
,
1678 PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
1680 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
1684 /* Return all context independent values from aggregate lattices in PLATS in a
1685 vector. Return NULL if there are none. */
1687 static vec
<ipa_agg_jf_item_t
, va_gc
> *
1688 context_independent_aggregate_values (struct ipcp_param_lattices
*plats
)
1690 vec
<ipa_agg_jf_item_t
, va_gc
> *res
= NULL
;
1692 if (plats
->aggs_bottom
1693 || plats
->aggs_contain_variable
1694 || plats
->aggs_count
== 0)
1697 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
;
1699 aglat
= aglat
->next
)
1700 if (ipa_lat_is_single_const (aglat
))
1702 struct ipa_agg_jf_item item
;
1703 item
.offset
= aglat
->offset
;
1704 item
.value
= aglat
->values
->value
;
1705 vec_safe_push (res
, item
);
1710 /* Allocate KNOWN_CSTS, KNOWN_BINFOS and, if non-NULL, KNOWN_AGGS and populate
1711 them with values of parameters that are known independent of the context.
1712 INFO describes the function. If REMOVABLE_PARAMS_COST is non-NULL, the
1713 movement cost of all removable parameters will be stored in it. */
1716 gather_context_independent_values (struct ipa_node_params
*info
,
1717 vec
<tree
> *known_csts
,
1718 vec
<tree
> *known_binfos
,
1719 vec
<ipa_agg_jump_function_t
> *known_aggs
,
1720 int *removable_params_cost
)
1722 int i
, count
= ipa_get_param_count (info
);
1725 known_csts
->create (0);
1726 known_binfos
->create (0);
1727 known_csts
->safe_grow_cleared (count
);
1728 known_binfos
->safe_grow_cleared (count
);
1731 known_aggs
->create (0);
1732 known_aggs
->safe_grow_cleared (count
);
1735 if (removable_params_cost
)
1736 *removable_params_cost
= 0;
1738 for (i
= 0; i
< count
; i
++)
1740 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1741 struct ipcp_lattice
*lat
= &plats
->itself
;
1743 if (ipa_lat_is_single_const (lat
))
1745 struct ipcp_value
*val
= lat
->values
;
1746 if (TREE_CODE (val
->value
) != TREE_BINFO
)
1748 (*known_csts
)[i
] = val
->value
;
1749 if (removable_params_cost
)
1750 *removable_params_cost
1751 += estimate_move_cost (TREE_TYPE (val
->value
));
1754 else if (plats
->virt_call
)
1756 (*known_binfos
)[i
] = val
->value
;
1759 else if (removable_params_cost
1760 && !ipa_is_param_used (info
, i
))
1761 *removable_params_cost
1762 += estimate_move_cost (TREE_TYPE (ipa_get_param (info
, i
)));
1764 else if (removable_params_cost
1765 && !ipa_is_param_used (info
, i
))
1766 *removable_params_cost
1767 += estimate_move_cost (TREE_TYPE (ipa_get_param (info
, i
)));
1771 vec
<ipa_agg_jf_item_t
, va_gc
> *agg_items
;
1772 struct ipa_agg_jump_function
*ajf
;
1774 agg_items
= context_independent_aggregate_values (plats
);
1775 ajf
= &(*known_aggs
)[i
];
1776 ajf
->items
= agg_items
;
1777 ajf
->by_ref
= plats
->aggs_by_ref
;
1778 ret
|= agg_items
!= NULL
;
1785 /* The current interface in ipa-inline-analysis requires a pointer vector.
1788 FIXME: That interface should be re-worked, this is slightly silly. Still,
1789 I'd like to discuss how to change it first and this demonstrates the
1792 static vec
<ipa_agg_jump_function_p
>
1793 agg_jmp_p_vec_for_t_vec (vec
<ipa_agg_jump_function_t
> known_aggs
)
1795 vec
<ipa_agg_jump_function_p
> ret
;
1796 struct ipa_agg_jump_function
*ajf
;
1799 ret
.create (known_aggs
.length ());
1800 FOR_EACH_VEC_ELT (known_aggs
, i
, ajf
)
1801 ret
.quick_push (ajf
);
1805 /* Iterate over known values of parameters of NODE and estimate the local
1806 effects in terms of time and size they have. */
1809 estimate_local_effects (struct cgraph_node
*node
)
1811 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1812 int i
, count
= ipa_get_param_count (info
);
1813 vec
<tree
> known_csts
, known_binfos
;
1814 vec
<ipa_agg_jump_function_t
> known_aggs
;
1815 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
;
1817 int base_time
= inline_summary (node
)->time
;
1818 int removable_params_cost
;
1820 if (!count
|| !ipcp_versionable_function_p (node
))
1823 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1824 fprintf (dump_file
, "\nEstimating effects for %s/%i, base_time: %i.\n",
1825 cgraph_node_name (node
), node
->symbol
.order
, base_time
);
1827 always_const
= gather_context_independent_values (info
, &known_csts
,
1828 &known_binfos
, &known_aggs
,
1829 &removable_params_cost
);
1830 known_aggs_ptrs
= agg_jmp_p_vec_for_t_vec (known_aggs
);
1833 struct caller_statistics stats
;
1837 init_caller_stats (&stats
);
1838 cgraph_for_node_and_aliases (node
, gather_caller_stats
, &stats
, false);
1839 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_binfos
,
1840 known_aggs_ptrs
, &size
, &time
, &hints
);
1841 time
-= devirtualization_time_bonus (node
, known_csts
, known_binfos
,
1843 time
-= hint_time_bonus (hints
);
1844 time
-= removable_params_cost
;
1845 size
-= stats
.n_calls
* removable_params_cost
;
1848 fprintf (dump_file
, " - context independent values, size: %i, "
1849 "time_benefit: %i\n", size
, base_time
- time
);
1852 || cgraph_will_be_removed_from_program_if_no_direct_calls (node
))
1854 info
->do_clone_for_all_contexts
= true;
1858 fprintf (dump_file
, " Decided to specialize for all "
1859 "known contexts, code not going to grow.\n");
1861 else if (good_cloning_opportunity_p (node
, base_time
- time
,
1862 stats
.freq_sum
, stats
.count_sum
,
1865 if (size
+ overall_size
<= max_new_size
)
1867 info
->do_clone_for_all_contexts
= true;
1869 overall_size
+= size
;
1872 fprintf (dump_file
, " Decided to specialize for all "
1873 "known contexts, growth deemed beneficial.\n");
1875 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1876 fprintf (dump_file
, " Not cloning for all contexts because "
1877 "max_new_size would be reached with %li.\n",
1878 size
+ overall_size
);
1882 for (i
= 0; i
< count
; i
++)
1884 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1885 struct ipcp_lattice
*lat
= &plats
->itself
;
1886 struct ipcp_value
*val
;
1895 for (val
= lat
->values
; val
; val
= val
->next
)
1897 int time
, size
, time_benefit
;
1900 if (TREE_CODE (val
->value
) != TREE_BINFO
)
1902 known_csts
[i
] = val
->value
;
1903 known_binfos
[i
] = NULL_TREE
;
1904 emc
= estimate_move_cost (TREE_TYPE (val
->value
));
1906 else if (plats
->virt_call
)
1908 known_csts
[i
] = NULL_TREE
;
1909 known_binfos
[i
] = val
->value
;
1915 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_binfos
,
1916 known_aggs_ptrs
, &size
, &time
,
1918 time_benefit
= base_time
- time
1919 + devirtualization_time_bonus (node
, known_csts
, known_binfos
,
1921 + hint_time_bonus (hints
)
1922 + removable_params_cost
+ emc
;
1924 gcc_checking_assert (size
>=0);
1925 /* The inliner-heuristics based estimates may think that in certain
1926 contexts some functions do not have any size at all but we want
1927 all specializations to have at least a tiny cost, not least not to
1932 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1934 fprintf (dump_file
, " - estimates for value ");
1935 print_ipcp_constant_value (dump_file
, val
->value
);
1936 fprintf (dump_file
, " for parameter ");
1937 print_generic_expr (dump_file
, ipa_get_param (info
, i
), 0);
1938 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
1939 time_benefit
, size
);
1942 val
->local_time_benefit
= time_benefit
;
1943 val
->local_size_cost
= size
;
1945 known_binfos
[i
] = NULL_TREE
;
1946 known_csts
[i
] = NULL_TREE
;
1949 for (i
= 0; i
< count
; i
++)
1951 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1952 struct ipa_agg_jump_function
*ajf
;
1953 struct ipcp_agg_lattice
*aglat
;
1955 if (plats
->aggs_bottom
|| !plats
->aggs
)
1958 ajf
= &known_aggs
[i
];
1959 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
1961 struct ipcp_value
*val
;
1962 if (aglat
->bottom
|| !aglat
->values
1963 /* If the following is true, the one value is in known_aggs. */
1964 || (!plats
->aggs_contain_variable
1965 && ipa_lat_is_single_const (aglat
)))
1968 for (val
= aglat
->values
; val
; val
= val
->next
)
1970 int time
, size
, time_benefit
;
1971 struct ipa_agg_jf_item item
;
1974 item
.offset
= aglat
->offset
;
1975 item
.value
= val
->value
;
1976 vec_safe_push (ajf
->items
, item
);
1978 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_binfos
,
1979 known_aggs_ptrs
, &size
, &time
,
1981 time_benefit
= base_time
- time
1982 + devirtualization_time_bonus (node
, known_csts
, known_binfos
,
1984 + hint_time_bonus (hints
);
1985 gcc_checking_assert (size
>=0);
1989 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1991 fprintf (dump_file
, " - estimates for value ");
1992 print_ipcp_constant_value (dump_file
, val
->value
);
1993 fprintf (dump_file
, " for parameter ");
1994 print_generic_expr (dump_file
, ipa_get_param (info
, i
), 0);
1995 fprintf (dump_file
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
1996 "]: time_benefit: %i, size: %i\n",
1997 plats
->aggs_by_ref
? "ref " : "",
1998 aglat
->offset
, time_benefit
, size
);
2001 val
->local_time_benefit
= time_benefit
;
2002 val
->local_size_cost
= size
;
2008 for (i
= 0; i
< count
; i
++)
2009 vec_free (known_aggs
[i
].items
);
2011 known_csts
.release ();
2012 known_binfos
.release ();
2013 known_aggs
.release ();
2014 known_aggs_ptrs
.release ();
2018 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
2019 topological sort of values. */
2022 add_val_to_toposort (struct ipcp_value
*cur_val
)
2024 static int dfs_counter
= 0;
2025 static struct ipcp_value
*stack
;
2026 struct ipcp_value_source
*src
;
2032 cur_val
->dfs
= dfs_counter
;
2033 cur_val
->low_link
= dfs_counter
;
2035 cur_val
->topo_next
= stack
;
2037 cur_val
->on_stack
= true;
2039 for (src
= cur_val
->sources
; src
; src
= src
->next
)
2042 if (src
->val
->dfs
== 0)
2044 add_val_to_toposort (src
->val
);
2045 if (src
->val
->low_link
< cur_val
->low_link
)
2046 cur_val
->low_link
= src
->val
->low_link
;
2048 else if (src
->val
->on_stack
2049 && src
->val
->dfs
< cur_val
->low_link
)
2050 cur_val
->low_link
= src
->val
->dfs
;
2053 if (cur_val
->dfs
== cur_val
->low_link
)
2055 struct ipcp_value
*v
, *scc_list
= NULL
;
2060 stack
= v
->topo_next
;
2061 v
->on_stack
= false;
2063 v
->scc_next
= scc_list
;
2066 while (v
!= cur_val
);
2068 cur_val
->topo_next
= values_topo
;
2069 values_topo
= cur_val
;
2073 /* Add all values in lattices associated with NODE to the topological sort if
2074 they are not there yet. */
2077 add_all_node_vals_to_toposort (struct cgraph_node
*node
)
2079 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2080 int i
, count
= ipa_get_param_count (info
);
2082 for (i
= 0; i
< count
; i
++)
2084 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2085 struct ipcp_lattice
*lat
= &plats
->itself
;
2086 struct ipcp_agg_lattice
*aglat
;
2087 struct ipcp_value
*val
;
2090 for (val
= lat
->values
; val
; val
= val
->next
)
2091 add_val_to_toposort (val
);
2093 if (!plats
->aggs_bottom
)
2094 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2096 for (val
= aglat
->values
; val
; val
= val
->next
)
2097 add_val_to_toposort (val
);
2101 /* One pass of constants propagation along the call graph edges, from callers
2102 to callees (requires topological ordering in TOPO), iterate over strongly
2103 connected components. */
2106 propagate_constants_topo (struct topo_info
*topo
)
2110 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
2112 struct cgraph_node
*v
, *node
= topo
->order
[i
];
2113 struct ipa_dfs_info
*node_dfs_info
;
2115 if (!cgraph_function_with_gimple_body_p (node
))
2118 node_dfs_info
= (struct ipa_dfs_info
*) node
->symbol
.aux
;
2119 /* First, iteratively propagate within the strongly connected component
2120 until all lattices stabilize. */
2121 v
= node_dfs_info
->next_cycle
;
2124 push_node_to_stack (topo
, v
);
2125 v
= ((struct ipa_dfs_info
*) v
->symbol
.aux
)->next_cycle
;
2131 struct cgraph_edge
*cs
;
2133 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
2134 if (edge_within_scc (cs
)
2135 && propagate_constants_accross_call (cs
))
2136 push_node_to_stack (topo
, cs
->callee
);
2137 v
= pop_node_from_stack (topo
);
2140 /* Afterwards, propagate along edges leading out of the SCC, calculates
2141 the local effects of the discovered constants and all valid values to
2142 their topological sort. */
2146 struct cgraph_edge
*cs
;
2148 estimate_local_effects (v
);
2149 add_all_node_vals_to_toposort (v
);
2150 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
2151 if (!edge_within_scc (cs
))
2152 propagate_constants_accross_call (cs
);
2154 v
= ((struct ipa_dfs_info
*) v
->symbol
.aux
)->next_cycle
;
2160 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
2161 the bigger one if otherwise. */
2164 safe_add (int a
, int b
)
2166 if (a
> INT_MAX
/2 || b
> INT_MAX
/2)
2167 return a
> b
? a
: b
;
2173 /* Propagate the estimated effects of individual values along the topological
2174 from the dependent values to those they depend on. */
2177 propagate_effects (void)
2179 struct ipcp_value
*base
;
2181 for (base
= values_topo
; base
; base
= base
->topo_next
)
2183 struct ipcp_value_source
*src
;
2184 struct ipcp_value
*val
;
2185 int time
= 0, size
= 0;
2187 for (val
= base
; val
; val
= val
->scc_next
)
2189 time
= safe_add (time
,
2190 val
->local_time_benefit
+ val
->prop_time_benefit
);
2191 size
= safe_add (size
, val
->local_size_cost
+ val
->prop_size_cost
);
2194 for (val
= base
; val
; val
= val
->scc_next
)
2195 for (src
= val
->sources
; src
; src
= src
->next
)
2197 && cgraph_maybe_hot_edge_p (src
->cs
))
2199 src
->val
->prop_time_benefit
= safe_add (time
,
2200 src
->val
->prop_time_benefit
);
2201 src
->val
->prop_size_cost
= safe_add (size
,
2202 src
->val
->prop_size_cost
);
2208 /* Propagate constants, binfos and their effects from the summaries
2209 interprocedurally. */
2212 ipcp_propagate_stage (struct topo_info
*topo
)
2214 struct cgraph_node
*node
;
2217 fprintf (dump_file
, "\n Propagating constants:\n\n");
2220 ipa_update_after_lto_read ();
2223 FOR_EACH_DEFINED_FUNCTION (node
)
2225 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2227 determine_versionability (node
);
2228 if (cgraph_function_with_gimple_body_p (node
))
2230 info
->lattices
= XCNEWVEC (struct ipcp_param_lattices
,
2231 ipa_get_param_count (info
));
2232 initialize_node_lattices (node
);
2234 if (node
->symbol
.definition
&& !node
->symbol
.alias
)
2235 overall_size
+= inline_summary (node
)->self_size
;
2236 if (node
->count
> max_count
)
2237 max_count
= node
->count
;
2240 max_new_size
= overall_size
;
2241 if (max_new_size
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
2242 max_new_size
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
2243 max_new_size
+= max_new_size
* PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH
) / 100 + 1;
2246 fprintf (dump_file
, "\noverall_size: %li, max_new_size: %li\n",
2247 overall_size
, max_new_size
);
2249 propagate_constants_topo (topo
);
2250 #ifdef ENABLE_CHECKING
2251 ipcp_verify_propagated_values ();
2253 propagate_effects ();
2257 fprintf (dump_file
, "\nIPA lattices after all propagation:\n");
2258 print_all_lattices (dump_file
, (dump_flags
& TDF_DETAILS
), true);
2262 /* Discover newly direct outgoing edges from NODE which is a new clone with
2263 known KNOWN_VALS and make them direct. */
2266 ipcp_discover_new_direct_edges (struct cgraph_node
*node
,
2267 vec
<tree
> known_vals
,
2268 struct ipa_agg_replacement_value
*aggvals
)
2270 struct cgraph_edge
*ie
, *next_ie
;
2273 for (ie
= node
->indirect_calls
; ie
; ie
= next_ie
)
2277 next_ie
= ie
->next_callee
;
2278 target
= ipa_get_indirect_edge_target_1 (ie
, known_vals
, vNULL
, vNULL
,
2282 struct cgraph_edge
*cs
= ipa_make_edge_direct_to_target (ie
, target
);
2285 if (cs
&& !ie
->indirect_info
->agg_contents
2286 && !ie
->indirect_info
->polymorphic
)
2288 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2289 int param_index
= ie
->indirect_info
->param_index
;
2290 int c
= ipa_get_controlled_uses (info
, param_index
);
2291 if (c
!= IPA_UNDESCRIBED_USE
)
2293 struct ipa_ref
*to_del
;
2296 ipa_set_controlled_uses (info
, param_index
, c
);
2297 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2298 fprintf (dump_file
, " controlled uses count of param "
2299 "%i bumped down to %i\n", param_index
, c
);
2301 && (to_del
= ipa_find_reference ((symtab_node
) node
,
2302 (symtab_node
) cs
->callee
,
2305 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2306 fprintf (dump_file
, " and even removing its "
2307 "cloning-created reference\n");
2308 ipa_remove_reference (to_del
);
2314 /* Turning calls to direct calls will improve overall summary. */
2316 inline_update_overall_summary (node
);
2319 /* Vector of pointers which for linked lists of clones of an original crgaph
2322 static vec
<cgraph_edge_p
> next_edge_clone
;
2325 grow_next_edge_clone_vector (void)
2327 if (next_edge_clone
.length ()
2328 <= (unsigned) cgraph_edge_max_uid
)
2329 next_edge_clone
.safe_grow_cleared (cgraph_edge_max_uid
+ 1);
2332 /* Edge duplication hook to grow the appropriate linked list in
2336 ipcp_edge_duplication_hook (struct cgraph_edge
*src
, struct cgraph_edge
*dst
,
2337 __attribute__((unused
)) void *data
)
2339 grow_next_edge_clone_vector ();
2340 next_edge_clone
[dst
->uid
] = next_edge_clone
[src
->uid
];
2341 next_edge_clone
[src
->uid
] = dst
;
2344 /* See if NODE is a clone with a known aggregate value at a given OFFSET of a
2345 parameter with the given INDEX. */
2348 get_clone_agg_value (struct cgraph_node
*node
, HOST_WIDEST_INT offset
,
2351 struct ipa_agg_replacement_value
*aggval
;
2353 aggval
= ipa_get_agg_replacements_for_node (node
);
2356 if (aggval
->offset
== offset
2357 && aggval
->index
== index
)
2358 return aggval
->value
;
2359 aggval
= aggval
->next
;
2364 /* Return true if edge CS does bring about the value described by SRC. */
2367 cgraph_edge_brings_value_p (struct cgraph_edge
*cs
,
2368 struct ipcp_value_source
*src
)
2370 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2371 struct ipa_node_params
*dst_info
= IPA_NODE_REF (cs
->callee
);
2373 if ((dst_info
->ipcp_orig_node
&& !dst_info
->is_all_contexts_clone
)
2374 || caller_info
->node_dead
)
2379 if (caller_info
->ipcp_orig_node
)
2382 if (src
->offset
== -1)
2383 t
= caller_info
->known_vals
[src
->index
];
2385 t
= get_clone_agg_value (cs
->caller
, src
->offset
, src
->index
);
2386 return (t
!= NULL_TREE
2387 && values_equal_for_ipcp_p (src
->val
->value
, t
));
2391 struct ipcp_agg_lattice
*aglat
;
2392 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
2394 if (src
->offset
== -1)
2395 return (ipa_lat_is_single_const (&plats
->itself
)
2396 && values_equal_for_ipcp_p (src
->val
->value
,
2397 plats
->itself
.values
->value
));
2400 if (plats
->aggs_bottom
|| plats
->aggs_contain_variable
)
2402 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2403 if (aglat
->offset
== src
->offset
)
2404 return (ipa_lat_is_single_const (aglat
)
2405 && values_equal_for_ipcp_p (src
->val
->value
,
2406 aglat
->values
->value
));
2412 /* Get the next clone in the linked list of clones of an edge. */
2414 static inline struct cgraph_edge
*
2415 get_next_cgraph_edge_clone (struct cgraph_edge
*cs
)
2417 return next_edge_clone
[cs
->uid
];
2420 /* Given VAL, iterate over all its sources and if they still hold, add their
2421 edge frequency and their number into *FREQUENCY and *CALLER_COUNT
2425 get_info_about_necessary_edges (struct ipcp_value
*val
, int *freq_sum
,
2426 gcov_type
*count_sum
, int *caller_count
)
2428 struct ipcp_value_source
*src
;
2429 int freq
= 0, count
= 0;
2433 for (src
= val
->sources
; src
; src
= src
->next
)
2435 struct cgraph_edge
*cs
= src
->cs
;
2438 if (cgraph_edge_brings_value_p (cs
, src
))
2441 freq
+= cs
->frequency
;
2443 hot
|= cgraph_maybe_hot_edge_p (cs
);
2445 cs
= get_next_cgraph_edge_clone (cs
);
2451 *caller_count
= count
;
2455 /* Return a vector of incoming edges that do bring value VAL. It is assumed
2456 their number is known and equal to CALLER_COUNT. */
2458 static vec
<cgraph_edge_p
>
2459 gather_edges_for_value (struct ipcp_value
*val
, int caller_count
)
2461 struct ipcp_value_source
*src
;
2462 vec
<cgraph_edge_p
> ret
;
2464 ret
.create (caller_count
);
2465 for (src
= val
->sources
; src
; src
= src
->next
)
2467 struct cgraph_edge
*cs
= src
->cs
;
2470 if (cgraph_edge_brings_value_p (cs
, src
))
2471 ret
.quick_push (cs
);
2472 cs
= get_next_cgraph_edge_clone (cs
);
2479 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
2480 Return it or NULL if for some reason it cannot be created. */
2482 static struct ipa_replace_map
*
2483 get_replacement_map (tree value
, tree parm
)
2485 tree req_type
= TREE_TYPE (parm
);
2486 struct ipa_replace_map
*replace_map
;
2488 if (!useless_type_conversion_p (req_type
, TREE_TYPE (value
)))
2490 if (fold_convertible_p (req_type
, value
))
2491 value
= fold_build1 (NOP_EXPR
, req_type
, value
);
2492 else if (TYPE_SIZE (req_type
) == TYPE_SIZE (TREE_TYPE (value
)))
2493 value
= fold_build1 (VIEW_CONVERT_EXPR
, req_type
, value
);
2498 fprintf (dump_file
, " const ");
2499 print_generic_expr (dump_file
, value
, 0);
2500 fprintf (dump_file
, " can't be converted to param ");
2501 print_generic_expr (dump_file
, parm
, 0);
2502 fprintf (dump_file
, "\n");
2508 replace_map
= ggc_alloc_ipa_replace_map ();
2511 fprintf (dump_file
, " replacing param ");
2512 print_generic_expr (dump_file
, parm
, 0);
2513 fprintf (dump_file
, " with const ");
2514 print_generic_expr (dump_file
, value
, 0);
2515 fprintf (dump_file
, "\n");
2517 replace_map
->old_tree
= parm
;
2518 replace_map
->new_tree
= value
;
2519 replace_map
->replace_p
= true;
2520 replace_map
->ref_p
= false;
2525 /* Dump new profiling counts */
2528 dump_profile_updates (struct cgraph_node
*orig_node
,
2529 struct cgraph_node
*new_node
)
2531 struct cgraph_edge
*cs
;
2533 fprintf (dump_file
, " setting count of the specialized node to "
2534 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) new_node
->count
);
2535 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
2536 fprintf (dump_file
, " edge to %s has count "
2537 HOST_WIDE_INT_PRINT_DEC
"\n",
2538 cgraph_node_name (cs
->callee
), (HOST_WIDE_INT
) cs
->count
);
2540 fprintf (dump_file
, " setting count of the original node to "
2541 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) orig_node
->count
);
2542 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
2543 fprintf (dump_file
, " edge to %s is left with "
2544 HOST_WIDE_INT_PRINT_DEC
"\n",
2545 cgraph_node_name (cs
->callee
), (HOST_WIDE_INT
) cs
->count
);
2548 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
2549 their profile information to reflect this. */
2552 update_profiling_info (struct cgraph_node
*orig_node
,
2553 struct cgraph_node
*new_node
)
2555 struct cgraph_edge
*cs
;
2556 struct caller_statistics stats
;
2557 gcov_type new_sum
, orig_sum
;
2558 gcov_type remainder
, orig_node_count
= orig_node
->count
;
2560 if (orig_node_count
== 0)
2563 init_caller_stats (&stats
);
2564 cgraph_for_node_and_aliases (orig_node
, gather_caller_stats
, &stats
, false);
2565 orig_sum
= stats
.count_sum
;
2566 init_caller_stats (&stats
);
2567 cgraph_for_node_and_aliases (new_node
, gather_caller_stats
, &stats
, false);
2568 new_sum
= stats
.count_sum
;
2570 if (orig_node_count
< orig_sum
+ new_sum
)
2573 fprintf (dump_file
, " Problem: node %s/%i has too low count "
2574 HOST_WIDE_INT_PRINT_DEC
" while the sum of incoming "
2575 "counts is " HOST_WIDE_INT_PRINT_DEC
"\n",
2576 cgraph_node_name (orig_node
), orig_node
->symbol
.order
,
2577 (HOST_WIDE_INT
) orig_node_count
,
2578 (HOST_WIDE_INT
) (orig_sum
+ new_sum
));
2580 orig_node_count
= (orig_sum
+ new_sum
) * 12 / 10;
2582 fprintf (dump_file
, " proceeding by pretending it was "
2583 HOST_WIDE_INT_PRINT_DEC
"\n",
2584 (HOST_WIDE_INT
) orig_node_count
);
2587 new_node
->count
= new_sum
;
2588 remainder
= orig_node_count
- new_sum
;
2589 orig_node
->count
= remainder
;
2591 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
2593 cs
->count
= apply_probability (cs
->count
,
2594 GCOV_COMPUTE_SCALE (new_sum
,
2599 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
2600 cs
->count
= apply_probability (cs
->count
,
2601 GCOV_COMPUTE_SCALE (remainder
,
2605 dump_profile_updates (orig_node
, new_node
);
2608 /* Update the respective profile of specialized NEW_NODE and the original
2609 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
2610 have been redirected to the specialized version. */
2613 update_specialized_profile (struct cgraph_node
*new_node
,
2614 struct cgraph_node
*orig_node
,
2615 gcov_type redirected_sum
)
2617 struct cgraph_edge
*cs
;
2618 gcov_type new_node_count
, orig_node_count
= orig_node
->count
;
2621 fprintf (dump_file
, " the sum of counts of redirected edges is "
2622 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) redirected_sum
);
2623 if (orig_node_count
== 0)
2626 gcc_assert (orig_node_count
>= redirected_sum
);
2628 new_node_count
= new_node
->count
;
2629 new_node
->count
+= redirected_sum
;
2630 orig_node
->count
-= redirected_sum
;
2632 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
2634 cs
->count
+= apply_probability (cs
->count
,
2635 GCOV_COMPUTE_SCALE (redirected_sum
,
2640 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
2642 gcov_type dec
= apply_probability (cs
->count
,
2643 GCOV_COMPUTE_SCALE (redirected_sum
,
2645 if (dec
< cs
->count
)
2652 dump_profile_updates (orig_node
, new_node
);
2655 /* Create a specialized version of NODE with known constants and types of
2656 parameters in KNOWN_VALS and redirect all edges in CALLERS to it. */
2658 static struct cgraph_node
*
2659 create_specialized_node (struct cgraph_node
*node
,
2660 vec
<tree
> known_vals
,
2661 struct ipa_agg_replacement_value
*aggvals
,
2662 vec
<cgraph_edge_p
> callers
)
2664 struct ipa_node_params
*new_info
, *info
= IPA_NODE_REF (node
);
2665 vec
<ipa_replace_map_p
, va_gc
> *replace_trees
= NULL
;
2666 struct cgraph_node
*new_node
;
2667 int i
, count
= ipa_get_param_count (info
);
2668 bitmap args_to_skip
;
2670 gcc_assert (!info
->ipcp_orig_node
);
2672 if (node
->local
.can_change_signature
)
2674 args_to_skip
= BITMAP_GGC_ALLOC ();
2675 for (i
= 0; i
< count
; i
++)
2677 tree t
= known_vals
[i
];
2679 if ((t
&& TREE_CODE (t
) != TREE_BINFO
)
2680 || !ipa_is_param_used (info
, i
))
2681 bitmap_set_bit (args_to_skip
, i
);
2686 args_to_skip
= NULL
;
2687 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2688 fprintf (dump_file
, " cannot change function signature\n");
2691 for (i
= 0; i
< count
; i
++)
2693 tree t
= known_vals
[i
];
2694 if (t
&& TREE_CODE (t
) != TREE_BINFO
)
2696 struct ipa_replace_map
*replace_map
;
2698 replace_map
= get_replacement_map (t
, ipa_get_param (info
, i
));
2700 vec_safe_push (replace_trees
, replace_map
);
2704 new_node
= cgraph_create_virtual_clone (node
, callers
, replace_trees
,
2705 args_to_skip
, "constprop");
2706 ipa_set_node_agg_value_chain (new_node
, aggvals
);
2707 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2709 fprintf (dump_file
, " the new node is %s/%i.\n",
2710 cgraph_node_name (new_node
), new_node
->symbol
.order
);
2712 ipa_dump_agg_replacement_values (dump_file
, aggvals
);
2714 gcc_checking_assert (ipa_node_params_vector
.exists ()
2715 && (ipa_node_params_vector
.length ()
2716 > (unsigned) cgraph_max_uid
));
2717 update_profiling_info (node
, new_node
);
2718 new_info
= IPA_NODE_REF (new_node
);
2719 new_info
->ipcp_orig_node
= node
;
2720 new_info
->known_vals
= known_vals
;
2722 ipcp_discover_new_direct_edges (new_node
, known_vals
, aggvals
);
2728 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
2729 KNOWN_VALS with constants and types that are also known for all of the
2733 find_more_scalar_values_for_callers_subset (struct cgraph_node
*node
,
2734 vec
<tree
> known_vals
,
2735 vec
<cgraph_edge_p
> callers
)
2737 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2738 int i
, count
= ipa_get_param_count (info
);
2740 for (i
= 0; i
< count
; i
++)
2742 struct cgraph_edge
*cs
;
2743 tree newval
= NULL_TREE
;
2746 if (ipa_get_scalar_lat (info
, i
)->bottom
|| known_vals
[i
])
2749 FOR_EACH_VEC_ELT (callers
, j
, cs
)
2751 struct ipa_jump_func
*jump_func
;
2754 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
)))
2759 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
2760 t
= ipa_value_from_jfunc (IPA_NODE_REF (cs
->caller
), jump_func
);
2763 && !values_equal_for_ipcp_p (t
, newval
)))
2774 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2776 fprintf (dump_file
, " adding an extra known scalar value ");
2777 print_ipcp_constant_value (dump_file
, newval
);
2778 fprintf (dump_file
, " for parameter ");
2779 print_generic_expr (dump_file
, ipa_get_param (info
, i
), 0);
2780 fprintf (dump_file
, "\n");
2783 known_vals
[i
] = newval
;
2788 /* Go through PLATS and create a vector of values consisting of values and
2789 offsets (minus OFFSET) of lattices that contain only a single value. */
2791 static vec
<ipa_agg_jf_item_t
>
2792 copy_plats_to_inter (struct ipcp_param_lattices
*plats
, HOST_WIDE_INT offset
)
2794 vec
<ipa_agg_jf_item_t
> res
= vNULL
;
2796 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
2799 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2800 if (ipa_lat_is_single_const (aglat
))
2802 struct ipa_agg_jf_item ti
;
2803 ti
.offset
= aglat
->offset
- offset
;
2804 ti
.value
= aglat
->values
->value
;
2810 /* Intersect all values in INTER with single value lattices in PLATS (while
2811 subtracting OFFSET). */
2814 intersect_with_plats (struct ipcp_param_lattices
*plats
,
2815 vec
<ipa_agg_jf_item_t
> *inter
,
2816 HOST_WIDE_INT offset
)
2818 struct ipcp_agg_lattice
*aglat
;
2819 struct ipa_agg_jf_item
*item
;
2822 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
2828 aglat
= plats
->aggs
;
2829 FOR_EACH_VEC_ELT (*inter
, k
, item
)
2836 if (aglat
->offset
- offset
> item
->offset
)
2838 if (aglat
->offset
- offset
== item
->offset
)
2840 gcc_checking_assert (item
->value
);
2841 if (values_equal_for_ipcp_p (item
->value
, aglat
->values
->value
))
2845 aglat
= aglat
->next
;
2848 item
->value
= NULL_TREE
;
2852 /* Copy agggregate replacement values of NODE (which is an IPA-CP clone) to the
2853 vector result while subtracting OFFSET from the individual value offsets. */
2855 static vec
<ipa_agg_jf_item_t
>
2856 agg_replacements_to_vector (struct cgraph_node
*node
, int index
,
2857 HOST_WIDE_INT offset
)
2859 struct ipa_agg_replacement_value
*av
;
2860 vec
<ipa_agg_jf_item_t
> res
= vNULL
;
2862 for (av
= ipa_get_agg_replacements_for_node (node
); av
; av
= av
->next
)
2863 if (av
->index
== index
2864 && (av
->offset
- offset
) >= 0)
2866 struct ipa_agg_jf_item item
;
2867 gcc_checking_assert (av
->value
);
2868 item
.offset
= av
->offset
- offset
;
2869 item
.value
= av
->value
;
2870 res
.safe_push (item
);
2876 /* Intersect all values in INTER with those that we have already scheduled to
2877 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
2878 (while subtracting OFFSET). */
2881 intersect_with_agg_replacements (struct cgraph_node
*node
, int index
,
2882 vec
<ipa_agg_jf_item_t
> *inter
,
2883 HOST_WIDE_INT offset
)
2885 struct ipa_agg_replacement_value
*srcvals
;
2886 struct ipa_agg_jf_item
*item
;
2889 srcvals
= ipa_get_agg_replacements_for_node (node
);
2896 FOR_EACH_VEC_ELT (*inter
, i
, item
)
2898 struct ipa_agg_replacement_value
*av
;
2902 for (av
= srcvals
; av
; av
= av
->next
)
2904 gcc_checking_assert (av
->value
);
2905 if (av
->index
== index
2906 && av
->offset
- offset
== item
->offset
)
2908 if (values_equal_for_ipcp_p (item
->value
, av
->value
))
2914 item
->value
= NULL_TREE
;
2918 /* Intersect values in INTER with aggregate values that come along edge CS to
2919 parameter number INDEX and return it. If INTER does not actually exist yet,
2920 copy all incoming values to it. If we determine we ended up with no values
2921 whatsoever, return a released vector. */
2923 static vec
<ipa_agg_jf_item_t
>
2924 intersect_aggregates_with_edge (struct cgraph_edge
*cs
, int index
,
2925 vec
<ipa_agg_jf_item_t
> inter
)
2927 struct ipa_jump_func
*jfunc
;
2928 jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), index
);
2929 if (jfunc
->type
== IPA_JF_PASS_THROUGH
2930 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
2932 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2933 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
2935 if (caller_info
->ipcp_orig_node
)
2937 struct cgraph_node
*orig_node
= caller_info
->ipcp_orig_node
;
2938 struct ipcp_param_lattices
*orig_plats
;
2939 orig_plats
= ipa_get_parm_lattices (IPA_NODE_REF (orig_node
),
2941 if (agg_pass_through_permissible_p (orig_plats
, jfunc
))
2943 if (!inter
.exists ())
2944 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, 0);
2946 intersect_with_agg_replacements (cs
->caller
, src_idx
,
2952 struct ipcp_param_lattices
*src_plats
;
2953 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2954 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
2956 /* Currently we do not produce clobber aggregate jump
2957 functions, adjust when we do. */
2958 gcc_checking_assert (!jfunc
->agg
.items
);
2959 if (!inter
.exists ())
2960 inter
= copy_plats_to_inter (src_plats
, 0);
2962 intersect_with_plats (src_plats
, &inter
, 0);
2966 else if (jfunc
->type
== IPA_JF_ANCESTOR
2967 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
2969 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2970 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
2971 struct ipcp_param_lattices
*src_plats
;
2972 HOST_WIDE_INT delta
= ipa_get_jf_ancestor_offset (jfunc
);
2974 if (caller_info
->ipcp_orig_node
)
2976 if (!inter
.exists ())
2977 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, delta
);
2979 intersect_with_agg_replacements (cs
->caller
, src_idx
, &inter
,
2984 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);;
2985 /* Currently we do not produce clobber aggregate jump
2986 functions, adjust when we do. */
2987 gcc_checking_assert (!src_plats
->aggs
|| !jfunc
->agg
.items
);
2988 if (!inter
.exists ())
2989 inter
= copy_plats_to_inter (src_plats
, delta
);
2991 intersect_with_plats (src_plats
, &inter
, delta
);
2994 else if (jfunc
->agg
.items
)
2996 struct ipa_agg_jf_item
*item
;
2999 if (!inter
.exists ())
3000 for (unsigned i
= 0; i
< jfunc
->agg
.items
->length (); i
++)
3001 inter
.safe_push ((*jfunc
->agg
.items
)[i
]);
3003 FOR_EACH_VEC_ELT (inter
, k
, item
)
3006 bool found
= false;;
3011 while ((unsigned) l
< jfunc
->agg
.items
->length ())
3013 struct ipa_agg_jf_item
*ti
;
3014 ti
= &(*jfunc
->agg
.items
)[l
];
3015 if (ti
->offset
> item
->offset
)
3017 if (ti
->offset
== item
->offset
)
3019 gcc_checking_assert (ti
->value
);
3020 if (values_equal_for_ipcp_p (item
->value
,
3034 return vec
<ipa_agg_jf_item_t
>();
3039 /* Look at edges in CALLERS and collect all known aggregate values that arrive
3040 from all of them. */
3042 static struct ipa_agg_replacement_value
*
3043 find_aggregate_values_for_callers_subset (struct cgraph_node
*node
,
3044 vec
<cgraph_edge_p
> callers
)
3046 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
3047 struct ipa_agg_replacement_value
*res
= NULL
;
3048 struct cgraph_edge
*cs
;
3049 int i
, j
, count
= ipa_get_param_count (dest_info
);
3051 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3053 int c
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
3058 for (i
= 0; i
< count
; i
++)
3060 struct cgraph_edge
*cs
;
3061 vec
<ipa_agg_jf_item_t
> inter
= vNULL
;
3062 struct ipa_agg_jf_item
*item
;
3063 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (dest_info
, i
);
3066 /* Among other things, the following check should deal with all by_ref
3068 if (plats
->aggs_bottom
)
3071 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3073 inter
= intersect_aggregates_with_edge (cs
, i
, inter
);
3075 if (!inter
.exists ())
3079 FOR_EACH_VEC_ELT (inter
, j
, item
)
3081 struct ipa_agg_replacement_value
*v
;
3086 v
= ggc_alloc_ipa_agg_replacement_value ();
3088 v
->offset
= item
->offset
;
3089 v
->value
= item
->value
;
3090 v
->by_ref
= plats
->aggs_by_ref
;
3096 if (inter
.exists ())
3102 /* Turn KNOWN_AGGS into a list of aggreate replacement values. */
3104 static struct ipa_agg_replacement_value
*
3105 known_aggs_to_agg_replacement_list (vec
<ipa_agg_jump_function_t
> known_aggs
)
3107 struct ipa_agg_replacement_value
*res
= NULL
;
3108 struct ipa_agg_jump_function
*aggjf
;
3109 struct ipa_agg_jf_item
*item
;
3112 FOR_EACH_VEC_ELT (known_aggs
, i
, aggjf
)
3113 FOR_EACH_VEC_SAFE_ELT (aggjf
->items
, j
, item
)
3115 struct ipa_agg_replacement_value
*v
;
3116 v
= ggc_alloc_ipa_agg_replacement_value ();
3118 v
->offset
= item
->offset
;
3119 v
->value
= item
->value
;
3120 v
->by_ref
= aggjf
->by_ref
;
3127 /* Determine whether CS also brings all scalar values that the NODE is
3131 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge
*cs
,
3132 struct cgraph_node
*node
)
3134 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
3135 int count
= ipa_get_param_count (dest_info
);
3136 struct ipa_node_params
*caller_info
;
3137 struct ipa_edge_args
*args
;
3140 caller_info
= IPA_NODE_REF (cs
->caller
);
3141 args
= IPA_EDGE_REF (cs
);
3142 for (i
= 0; i
< count
; i
++)
3144 struct ipa_jump_func
*jump_func
;
3147 val
= dest_info
->known_vals
[i
];
3151 if (i
>= ipa_get_cs_argument_count (args
))
3153 jump_func
= ipa_get_ith_jump_func (args
, i
);
3154 t
= ipa_value_from_jfunc (caller_info
, jump_func
);
3155 if (!t
|| !values_equal_for_ipcp_p (val
, t
))
3161 /* Determine whether CS also brings all aggregate values that NODE is
3164 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge
*cs
,
3165 struct cgraph_node
*node
)
3167 struct ipa_node_params
*orig_caller_info
= IPA_NODE_REF (cs
->caller
);
3168 struct ipa_agg_replacement_value
*aggval
;
3171 aggval
= ipa_get_agg_replacements_for_node (node
);
3175 count
= ipa_get_param_count (IPA_NODE_REF (node
));
3176 ec
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
3178 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
3179 if (aggval
->index
>= ec
)
3182 if (orig_caller_info
->ipcp_orig_node
)
3183 orig_caller_info
= IPA_NODE_REF (orig_caller_info
->ipcp_orig_node
);
3185 for (i
= 0; i
< count
; i
++)
3187 static vec
<ipa_agg_jf_item_t
> values
= vec
<ipa_agg_jf_item_t
>();
3188 struct ipcp_param_lattices
*plats
;
3189 bool interesting
= false;
3190 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
3191 if (aggval
->index
== i
)
3199 plats
= ipa_get_parm_lattices (orig_caller_info
, aggval
->index
);
3200 if (plats
->aggs_bottom
)
3203 values
= intersect_aggregates_with_edge (cs
, i
, values
);
3204 if (!values
.exists())
3207 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
3208 if (aggval
->index
== i
)
3210 struct ipa_agg_jf_item
*item
;
3213 FOR_EACH_VEC_ELT (values
, j
, item
)
3215 && item
->offset
== av
->offset
3216 && values_equal_for_ipcp_p (item
->value
, av
->value
))
3231 /* Given an original NODE and a VAL for which we have already created a
3232 specialized clone, look whether there are incoming edges that still lead
3233 into the old node but now also bring the requested value and also conform to
3234 all other criteria such that they can be redirected the the special node.
3235 This function can therefore redirect the final edge in a SCC. */
3238 perhaps_add_new_callers (struct cgraph_node
*node
, struct ipcp_value
*val
)
3240 struct ipcp_value_source
*src
;
3241 gcov_type redirected_sum
= 0;
3243 for (src
= val
->sources
; src
; src
= src
->next
)
3245 struct cgraph_edge
*cs
= src
->cs
;
3248 enum availability availability
;
3249 struct cgraph_node
*dst
= cgraph_function_node (cs
->callee
,
3251 if ((dst
== node
|| IPA_NODE_REF (dst
)->is_all_contexts_clone
)
3252 && availability
> AVAIL_OVERWRITABLE
3253 && cgraph_edge_brings_value_p (cs
, src
))
3255 if (cgraph_edge_brings_all_scalars_for_node (cs
, val
->spec_node
)
3256 && cgraph_edge_brings_all_agg_vals_for_node (cs
,
3260 fprintf (dump_file
, " - adding an extra caller %s/%i"
3262 xstrdup (cgraph_node_name (cs
->caller
)),
3263 cs
->caller
->symbol
.order
,
3264 xstrdup (cgraph_node_name (val
->spec_node
)),
3265 val
->spec_node
->symbol
.order
);
3267 cgraph_redirect_edge_callee (cs
, val
->spec_node
);
3268 redirected_sum
+= cs
->count
;
3271 cs
= get_next_cgraph_edge_clone (cs
);
3276 update_specialized_profile (val
->spec_node
, node
, redirected_sum
);
3280 /* Copy KNOWN_BINFOS to KNOWN_VALS. */
3283 move_binfos_to_values (vec
<tree
> known_vals
,
3284 vec
<tree
> known_binfos
)
3289 for (i
= 0; known_binfos
.iterate (i
, &t
); i
++)
3294 /* Return true if there is a replacement equivalent to VALUE, INDEX and OFFSET
3295 among those in the AGGVALS list. */
3298 ipcp_val_in_agg_replacements_p (struct ipa_agg_replacement_value
*aggvals
,
3299 int index
, HOST_WIDE_INT offset
, tree value
)
3303 if (aggvals
->index
== index
3304 && aggvals
->offset
== offset
3305 && values_equal_for_ipcp_p (aggvals
->value
, value
))
3307 aggvals
= aggvals
->next
;
3312 /* Decide wheter to create a special version of NODE for value VAL of parameter
3313 at the given INDEX. If OFFSET is -1, the value is for the parameter itself,
3314 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS,
3315 KNOWN_BINFOS and KNOWN_AGGS describe the other already known values. */
3318 decide_about_value (struct cgraph_node
*node
, int index
, HOST_WIDE_INT offset
,
3319 struct ipcp_value
*val
, vec
<tree
> known_csts
,
3320 vec
<tree
> known_binfos
)
3322 struct ipa_agg_replacement_value
*aggvals
;
3323 int freq_sum
, caller_count
;
3324 gcov_type count_sum
;
3325 vec
<cgraph_edge_p
> callers
;
3330 perhaps_add_new_callers (node
, val
);
3333 else if (val
->local_size_cost
+ overall_size
> max_new_size
)
3335 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3336 fprintf (dump_file
, " Ignoring candidate value because "
3337 "max_new_size would be reached with %li.\n",
3338 val
->local_size_cost
+ overall_size
);
3341 else if (!get_info_about_necessary_edges (val
, &freq_sum
, &count_sum
,
3345 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3347 fprintf (dump_file
, " - considering value ");
3348 print_ipcp_constant_value (dump_file
, val
->value
);
3349 fprintf (dump_file
, " for parameter ");
3350 print_generic_expr (dump_file
, ipa_get_param (IPA_NODE_REF (node
),
3353 fprintf (dump_file
, ", offset: " HOST_WIDE_INT_PRINT_DEC
, offset
);
3354 fprintf (dump_file
, " (caller_count: %i)\n", caller_count
);
3357 if (!good_cloning_opportunity_p (node
, val
->local_time_benefit
,
3358 freq_sum
, count_sum
,
3359 val
->local_size_cost
)
3360 && !good_cloning_opportunity_p (node
,
3361 val
->local_time_benefit
3362 + val
->prop_time_benefit
,
3363 freq_sum
, count_sum
,
3364 val
->local_size_cost
3365 + val
->prop_size_cost
))
3369 fprintf (dump_file
, " Creating a specialized node of %s/%i.\n",
3370 cgraph_node_name (node
), node
->symbol
.order
);
3372 callers
= gather_edges_for_value (val
, caller_count
);
3373 kv
= known_csts
.copy ();
3374 move_binfos_to_values (kv
, known_binfos
);
3376 kv
[index
] = val
->value
;
3377 find_more_scalar_values_for_callers_subset (node
, kv
, callers
);
3378 aggvals
= find_aggregate_values_for_callers_subset (node
, callers
);
3379 gcc_checking_assert (offset
== -1
3380 || ipcp_val_in_agg_replacements_p (aggvals
, index
,
3381 offset
, val
->value
));
3382 val
->spec_node
= create_specialized_node (node
, kv
, aggvals
, callers
);
3383 overall_size
+= val
->local_size_cost
;
3385 /* TODO: If for some lattice there is only one other known value
3386 left, make a special node for it too. */
3391 /* Decide whether and what specialized clones of NODE should be created. */
3394 decide_whether_version_node (struct cgraph_node
*node
)
3396 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3397 int i
, count
= ipa_get_param_count (info
);
3398 vec
<tree
> known_csts
, known_binfos
;
3399 vec
<ipa_agg_jump_function_t
> known_aggs
= vNULL
;
3405 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3406 fprintf (dump_file
, "\nEvaluating opportunities for %s/%i.\n",
3407 cgraph_node_name (node
), node
->symbol
.order
);
3409 gather_context_independent_values (info
, &known_csts
, &known_binfos
,
3410 info
->do_clone_for_all_contexts
? &known_aggs
3413 for (i
= 0; i
< count
;i
++)
3415 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3416 struct ipcp_lattice
*lat
= &plats
->itself
;
3417 struct ipcp_value
*val
;
3421 && !known_binfos
[i
])
3422 for (val
= lat
->values
; val
; val
= val
->next
)
3423 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
3426 if (!plats
->aggs_bottom
)
3428 struct ipcp_agg_lattice
*aglat
;
3429 struct ipcp_value
*val
;
3430 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3431 if (!aglat
->bottom
&& aglat
->values
3432 /* If the following is false, the one value is in
3434 && (plats
->aggs_contain_variable
3435 || !ipa_lat_is_single_const (aglat
)))
3436 for (val
= aglat
->values
; val
; val
= val
->next
)
3437 ret
|= decide_about_value (node
, i
, aglat
->offset
, val
,
3438 known_csts
, known_binfos
);
3440 info
= IPA_NODE_REF (node
);
3443 if (info
->do_clone_for_all_contexts
)
3445 struct cgraph_node
*clone
;
3446 vec
<cgraph_edge_p
> callers
;
3449 fprintf (dump_file
, " - Creating a specialized node of %s/%i "
3450 "for all known contexts.\n", cgraph_node_name (node
),
3451 node
->symbol
.order
);
3453 callers
= collect_callers_of_node (node
);
3454 move_binfos_to_values (known_csts
, known_binfos
);
3455 clone
= create_specialized_node (node
, known_csts
,
3456 known_aggs_to_agg_replacement_list (known_aggs
),
3458 info
= IPA_NODE_REF (node
);
3459 info
->do_clone_for_all_contexts
= false;
3460 IPA_NODE_REF (clone
)->is_all_contexts_clone
= true;
3461 for (i
= 0; i
< count
; i
++)
3462 vec_free (known_aggs
[i
].items
);
3463 known_aggs
.release ();
3467 known_csts
.release ();
3469 known_binfos
.release ();
3473 /* Transitively mark all callees of NODE within the same SCC as not dead. */
3476 spread_undeadness (struct cgraph_node
*node
)
3478 struct cgraph_edge
*cs
;
3480 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
3481 if (edge_within_scc (cs
))
3483 struct cgraph_node
*callee
;
3484 struct ipa_node_params
*info
;
3486 callee
= cgraph_function_node (cs
->callee
, NULL
);
3487 info
= IPA_NODE_REF (callee
);
3489 if (info
->node_dead
)
3491 info
->node_dead
= 0;
3492 spread_undeadness (callee
);
3497 /* Return true if NODE has a caller from outside of its SCC that is not
3498 dead. Worker callback for cgraph_for_node_and_aliases. */
3501 has_undead_caller_from_outside_scc_p (struct cgraph_node
*node
,
3502 void *data ATTRIBUTE_UNUSED
)
3504 struct cgraph_edge
*cs
;
3506 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
3507 if (cs
->caller
->thunk
.thunk_p
3508 && cgraph_for_node_and_aliases (cs
->caller
,
3509 has_undead_caller_from_outside_scc_p
,
3512 else if (!edge_within_scc (cs
)
3513 && !IPA_NODE_REF (cs
->caller
)->node_dead
)
3519 /* Identify nodes within the same SCC as NODE which are no longer needed
3520 because of new clones and will be removed as unreachable. */
3523 identify_dead_nodes (struct cgraph_node
*node
)
3525 struct cgraph_node
*v
;
3526 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->symbol
.aux
)->next_cycle
)
3527 if (cgraph_will_be_removed_from_program_if_no_direct_calls (v
)
3528 && !cgraph_for_node_and_aliases (v
,
3529 has_undead_caller_from_outside_scc_p
,
3531 IPA_NODE_REF (v
)->node_dead
= 1;
3533 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->symbol
.aux
)->next_cycle
)
3534 if (!IPA_NODE_REF (v
)->node_dead
)
3535 spread_undeadness (v
);
3537 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3539 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->symbol
.aux
)->next_cycle
)
3540 if (IPA_NODE_REF (v
)->node_dead
)
3541 fprintf (dump_file
, " Marking node as dead: %s/%i.\n",
3542 cgraph_node_name (v
), v
->symbol
.order
);
3546 /* The decision stage. Iterate over the topological order of call graph nodes
3547 TOPO and make specialized clones if deemed beneficial. */
3550 ipcp_decision_stage (struct topo_info
*topo
)
3555 fprintf (dump_file
, "\nIPA decision stage:\n\n");
3557 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
3559 struct cgraph_node
*node
= topo
->order
[i
];
3560 bool change
= false, iterate
= true;
3564 struct cgraph_node
*v
;
3566 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->symbol
.aux
)->next_cycle
)
3567 if (cgraph_function_with_gimple_body_p (v
)
3568 && ipcp_versionable_function_p (v
))
3569 iterate
|= decide_whether_version_node (v
);
3574 identify_dead_nodes (node
);
3578 /* The IPCP driver. */
3583 struct cgraph_2edge_hook_list
*edge_duplication_hook_holder
;
3584 struct topo_info topo
;
3586 ipa_check_create_node_params ();
3587 ipa_check_create_edge_args ();
3588 grow_next_edge_clone_vector ();
3589 edge_duplication_hook_holder
=
3590 cgraph_add_edge_duplication_hook (&ipcp_edge_duplication_hook
, NULL
);
3591 ipcp_values_pool
= create_alloc_pool ("IPA-CP values",
3592 sizeof (struct ipcp_value
), 32);
3593 ipcp_sources_pool
= create_alloc_pool ("IPA-CP value sources",
3594 sizeof (struct ipcp_value_source
), 64);
3595 ipcp_agg_lattice_pool
= create_alloc_pool ("IPA_CP aggregate lattices",
3596 sizeof (struct ipcp_agg_lattice
),
3600 fprintf (dump_file
, "\nIPA structures before propagation:\n");
3601 if (dump_flags
& TDF_DETAILS
)
3602 ipa_print_all_params (dump_file
);
3603 ipa_print_all_jump_functions (dump_file
);
3606 /* Topological sort. */
3607 build_toporder_info (&topo
);
3608 /* Do the interprocedural propagation. */
3609 ipcp_propagate_stage (&topo
);
3610 /* Decide what constant propagation and cloning should be performed. */
3611 ipcp_decision_stage (&topo
);
3613 /* Free all IPCP structures. */
3614 free_toporder_info (&topo
);
3615 next_edge_clone
.release ();
3616 cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder
);
3617 ipa_free_all_structures_after_ipa_cp ();
3619 fprintf (dump_file
, "\nIPA constant propagation end\n");
3623 /* Initialization and computation of IPCP data structures. This is the initial
3624 intraprocedural analysis of functions, which gathers information to be
3625 propagated later on. */
3628 ipcp_generate_summary (void)
3630 struct cgraph_node
*node
;
3633 fprintf (dump_file
, "\nIPA constant propagation start:\n");
3634 ipa_register_cgraph_hooks ();
3636 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
3638 node
->local
.versionable
3639 = tree_versionable_function_p (node
->symbol
.decl
);
3640 ipa_analyze_node (node
);
3644 /* Write ipcp summary for nodes in SET. */
3647 ipcp_write_summary (void)
3649 ipa_prop_write_jump_functions ();
3652 /* Read ipcp summary. */
3655 ipcp_read_summary (void)
3657 ipa_prop_read_jump_functions ();
3660 /* Gate for IPCP optimization. */
3663 cgraph_gate_cp (void)
3665 /* FIXME: We should remove the optimize check after we ensure we never run
3666 IPA passes when not optimizing. */
3667 return flag_ipa_cp
&& optimize
;
3670 struct ipa_opt_pass_d pass_ipa_cp
=
3675 OPTGROUP_NONE
, /* optinfo_flags */
3676 cgraph_gate_cp
, /* gate */
3677 ipcp_driver
, /* execute */
3680 0, /* static_pass_number */
3681 TV_IPA_CONSTANT_PROP
, /* tv_id */
3682 0, /* properties_required */
3683 0, /* properties_provided */
3684 0, /* properties_destroyed */
3685 0, /* todo_flags_start */
3687 TODO_remove_functions
/* todo_flags_finish */
3689 ipcp_generate_summary
, /* generate_summary */
3690 ipcp_write_summary
, /* write_summary */
3691 ipcp_read_summary
, /* read_summary */
3692 ipa_prop_write_all_agg_replacement
, /* write_optimization_summary */
3693 ipa_prop_read_all_agg_replacement
, /* read_optimization_summary */
3694 NULL
, /* stmt_fixup */
3696 ipcp_transform_function
, /* function_transform */
3697 NULL
, /* variable_transform */