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-ssa.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
738 && ie
->indirect_info
->param_index
>= 0)
740 gcc_checking_assert (ie
->indirect_info
->param_index
>= 0);
741 ipa_get_parm_lattices (info
,
742 ie
->indirect_info
->param_index
)->virt_call
= 1;
746 /* Return the result of a (possibly arithmetic) pass through jump function
747 JFUNC on the constant value INPUT. Return NULL_TREE if that cannot be
748 determined or be considered an interprocedural invariant. */
751 ipa_get_jf_pass_through_result (struct ipa_jump_func
*jfunc
, tree input
)
755 if (TREE_CODE (input
) == TREE_BINFO
)
757 if (ipa_get_jf_pass_through_type_preserved (jfunc
))
759 gcc_checking_assert (ipa_get_jf_pass_through_operation (jfunc
)
766 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
769 gcc_checking_assert (is_gimple_ip_invariant (input
));
770 if (TREE_CODE_CLASS (ipa_get_jf_pass_through_operation (jfunc
))
772 restype
= boolean_type_node
;
774 restype
= TREE_TYPE (input
);
775 res
= fold_binary (ipa_get_jf_pass_through_operation (jfunc
), restype
,
776 input
, ipa_get_jf_pass_through_operand (jfunc
));
778 if (res
&& !is_gimple_ip_invariant (res
))
784 /* Return the result of an ancestor jump function JFUNC on the constant value
785 INPUT. Return NULL_TREE if that cannot be determined. */
788 ipa_get_jf_ancestor_result (struct ipa_jump_func
*jfunc
, tree input
)
790 if (TREE_CODE (input
) == TREE_BINFO
)
792 if (!ipa_get_jf_ancestor_type_preserved (jfunc
))
794 return get_binfo_at_offset (input
,
795 ipa_get_jf_ancestor_offset (jfunc
),
796 ipa_get_jf_ancestor_type (jfunc
));
798 else if (TREE_CODE (input
) == ADDR_EXPR
)
800 tree t
= TREE_OPERAND (input
, 0);
801 t
= build_ref_for_offset (EXPR_LOCATION (t
), t
,
802 ipa_get_jf_ancestor_offset (jfunc
),
803 ipa_get_jf_ancestor_type (jfunc
), NULL
, false);
804 return build_fold_addr_expr (t
);
810 /* Determine whether JFUNC evaluates to a known value (that is either a
811 constant or a binfo) and if so, return it. Otherwise return NULL. INFO
812 describes the caller node so that pass-through jump functions can be
816 ipa_value_from_jfunc (struct ipa_node_params
*info
, struct ipa_jump_func
*jfunc
)
818 if (jfunc
->type
== IPA_JF_CONST
)
819 return ipa_get_jf_constant (jfunc
);
820 else if (jfunc
->type
== IPA_JF_KNOWN_TYPE
)
821 return ipa_binfo_from_known_type_jfunc (jfunc
);
822 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
823 || jfunc
->type
== IPA_JF_ANCESTOR
)
828 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
829 idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
831 idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
833 if (info
->ipcp_orig_node
)
834 input
= info
->known_vals
[idx
];
837 struct ipcp_lattice
*lat
;
841 gcc_checking_assert (!flag_ipa_cp
);
844 lat
= ipa_get_scalar_lat (info
, idx
);
845 if (!ipa_lat_is_single_const (lat
))
847 input
= lat
->values
->value
;
853 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
854 return ipa_get_jf_pass_through_result (jfunc
, input
);
856 return ipa_get_jf_ancestor_result (jfunc
, input
);
863 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
864 bottom, not containing a variable component and without any known value at
868 ipcp_verify_propagated_values (void)
870 struct cgraph_node
*node
;
872 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
874 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
875 int i
, count
= ipa_get_param_count (info
);
877 for (i
= 0; i
< count
; i
++)
879 struct ipcp_lattice
*lat
= ipa_get_scalar_lat (info
, i
);
882 && !lat
->contains_variable
883 && lat
->values_count
== 0)
887 fprintf (dump_file
, "\nIPA lattices after constant "
889 print_all_lattices (dump_file
, true, false);
898 /* Return true iff X and Y should be considered equal values by IPA-CP. */
901 values_equal_for_ipcp_p (tree x
, tree y
)
903 gcc_checking_assert (x
!= NULL_TREE
&& y
!= NULL_TREE
);
908 if (TREE_CODE (x
) == TREE_BINFO
|| TREE_CODE (y
) == TREE_BINFO
)
911 if (TREE_CODE (x
) == ADDR_EXPR
912 && TREE_CODE (y
) == ADDR_EXPR
913 && TREE_CODE (TREE_OPERAND (x
, 0)) == CONST_DECL
914 && TREE_CODE (TREE_OPERAND (y
, 0)) == CONST_DECL
)
915 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x
, 0)),
916 DECL_INITIAL (TREE_OPERAND (y
, 0)), 0);
918 return operand_equal_p (x
, y
, 0);
921 /* Add a new value source to VAL, marking that a value comes from edge CS and
922 (if the underlying jump function is a pass-through or an ancestor one) from
923 a caller value SRC_VAL of a caller parameter described by SRC_INDEX. OFFSET
924 is negative if the source was the scalar value of the parameter itself or
925 the offset within an aggregate. */
928 add_value_source (struct ipcp_value
*val
, struct cgraph_edge
*cs
,
929 struct ipcp_value
*src_val
, int src_idx
, HOST_WIDE_INT offset
)
931 struct ipcp_value_source
*src
;
933 src
= (struct ipcp_value_source
*) pool_alloc (ipcp_sources_pool
);
934 src
->offset
= offset
;
937 src
->index
= src_idx
;
939 src
->next
= val
->sources
;
943 /* Try to add NEWVAL to LAT, potentially creating a new struct ipcp_value for
944 it. CS, SRC_VAL SRC_INDEX and OFFSET are meant for add_value_source and
945 have the same meaning. */
948 add_value_to_lattice (struct ipcp_lattice
*lat
, tree newval
,
949 struct cgraph_edge
*cs
, struct ipcp_value
*src_val
,
950 int src_idx
, HOST_WIDE_INT offset
)
952 struct ipcp_value
*val
;
957 for (val
= lat
->values
; val
; val
= val
->next
)
958 if (values_equal_for_ipcp_p (val
->value
, newval
))
960 if (edge_within_scc (cs
))
962 struct ipcp_value_source
*s
;
963 for (s
= val
->sources
; s
; s
= s
->next
)
970 add_value_source (val
, cs
, src_val
, src_idx
, offset
);
974 if (lat
->values_count
== PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE
))
976 /* We can only free sources, not the values themselves, because sources
977 of other values in this this SCC might point to them. */
978 for (val
= lat
->values
; val
; val
= val
->next
)
982 struct ipcp_value_source
*src
= val
->sources
;
983 val
->sources
= src
->next
;
984 pool_free (ipcp_sources_pool
, src
);
989 return set_lattice_to_bottom (lat
);
993 val
= (struct ipcp_value
*) pool_alloc (ipcp_values_pool
);
994 memset (val
, 0, sizeof (*val
));
996 add_value_source (val
, cs
, src_val
, src_idx
, offset
);
998 val
->next
= lat
->values
;
1003 /* Like above but passes a special value of offset to distinguish that the
1004 origin is the scalar value of the parameter rather than a part of an
1008 add_scalar_value_to_lattice (struct ipcp_lattice
*lat
, tree newval
,
1009 struct cgraph_edge
*cs
,
1010 struct ipcp_value
*src_val
, int src_idx
)
1012 return add_value_to_lattice (lat
, newval
, cs
, src_val
, src_idx
, -1);
1015 /* Propagate values through a pass-through jump function JFUNC associated with
1016 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1017 is the index of the source parameter. */
1020 propagate_vals_accross_pass_through (struct cgraph_edge
*cs
,
1021 struct ipa_jump_func
*jfunc
,
1022 struct ipcp_lattice
*src_lat
,
1023 struct ipcp_lattice
*dest_lat
,
1026 struct ipcp_value
*src_val
;
1029 /* Do not create new values when propagating within an SCC because if there
1030 are arithmetic functions with circular dependencies, there is infinite
1031 number of them and we would just make lattices bottom. */
1032 if ((ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1033 and edge_within_scc (cs
))
1034 ret
= set_lattice_contains_variable (dest_lat
);
1036 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1038 tree cstval
= ipa_get_jf_pass_through_result (jfunc
, src_val
->value
);
1041 ret
|= add_scalar_value_to_lattice (dest_lat
, cstval
, cs
, src_val
,
1044 ret
|= set_lattice_contains_variable (dest_lat
);
1050 /* Propagate values through an ancestor jump function JFUNC associated with
1051 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1052 is the index of the source parameter. */
1055 propagate_vals_accross_ancestor (struct cgraph_edge
*cs
,
1056 struct ipa_jump_func
*jfunc
,
1057 struct ipcp_lattice
*src_lat
,
1058 struct ipcp_lattice
*dest_lat
,
1061 struct ipcp_value
*src_val
;
1064 if (edge_within_scc (cs
))
1065 return set_lattice_contains_variable (dest_lat
);
1067 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1069 tree t
= ipa_get_jf_ancestor_result (jfunc
, src_val
->value
);
1072 ret
|= add_scalar_value_to_lattice (dest_lat
, t
, cs
, src_val
, src_idx
);
1074 ret
|= set_lattice_contains_variable (dest_lat
);
1080 /* Propagate scalar values across jump function JFUNC that is associated with
1081 edge CS and put the values into DEST_LAT. */
1084 propagate_scalar_accross_jump_function (struct cgraph_edge
*cs
,
1085 struct ipa_jump_func
*jfunc
,
1086 struct ipcp_lattice
*dest_lat
)
1088 if (dest_lat
->bottom
)
1091 if (jfunc
->type
== IPA_JF_CONST
1092 || jfunc
->type
== IPA_JF_KNOWN_TYPE
)
1096 if (jfunc
->type
== IPA_JF_KNOWN_TYPE
)
1098 val
= ipa_binfo_from_known_type_jfunc (jfunc
);
1100 return set_lattice_contains_variable (dest_lat
);
1103 val
= ipa_get_jf_constant (jfunc
);
1104 return add_scalar_value_to_lattice (dest_lat
, val
, cs
, NULL
, 0);
1106 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1107 || jfunc
->type
== IPA_JF_ANCESTOR
)
1109 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1110 struct ipcp_lattice
*src_lat
;
1114 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1115 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1117 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1119 src_lat
= ipa_get_scalar_lat (caller_info
, src_idx
);
1120 if (src_lat
->bottom
)
1121 return set_lattice_contains_variable (dest_lat
);
1123 /* If we would need to clone the caller and cannot, do not propagate. */
1124 if (!ipcp_versionable_function_p (cs
->caller
)
1125 && (src_lat
->contains_variable
1126 || (src_lat
->values_count
> 1)))
1127 return set_lattice_contains_variable (dest_lat
);
1129 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1130 ret
= propagate_vals_accross_pass_through (cs
, jfunc
, src_lat
,
1133 ret
= propagate_vals_accross_ancestor (cs
, jfunc
, src_lat
, dest_lat
,
1136 if (src_lat
->contains_variable
)
1137 ret
|= set_lattice_contains_variable (dest_lat
);
1142 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1143 use it for indirect inlining), we should propagate them too. */
1144 return set_lattice_contains_variable (dest_lat
);
1147 /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
1148 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
1149 other cases, return false). If there are no aggregate items, set
1150 aggs_by_ref to NEW_AGGS_BY_REF. */
1153 set_check_aggs_by_ref (struct ipcp_param_lattices
*dest_plats
,
1154 bool new_aggs_by_ref
)
1156 if (dest_plats
->aggs
)
1158 if (dest_plats
->aggs_by_ref
!= new_aggs_by_ref
)
1160 set_agg_lats_to_bottom (dest_plats
);
1165 dest_plats
->aggs_by_ref
= new_aggs_by_ref
;
1169 /* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
1170 already existing lattice for the given OFFSET and SIZE, marking all skipped
1171 lattices as containing variable and checking for overlaps. If there is no
1172 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
1173 it with offset, size and contains_variable to PRE_EXISTING, and return true,
1174 unless there are too many already. If there are two many, return false. If
1175 there are overlaps turn whole DEST_PLATS to bottom and return false. If any
1176 skipped lattices were newly marked as containing variable, set *CHANGE to
1180 merge_agg_lats_step (struct ipcp_param_lattices
*dest_plats
,
1181 HOST_WIDE_INT offset
, HOST_WIDE_INT val_size
,
1182 struct ipcp_agg_lattice
***aglat
,
1183 bool pre_existing
, bool *change
)
1185 gcc_checking_assert (offset
>= 0);
1187 while (**aglat
&& (**aglat
)->offset
< offset
)
1189 if ((**aglat
)->offset
+ (**aglat
)->size
> offset
)
1191 set_agg_lats_to_bottom (dest_plats
);
1194 *change
|= set_lattice_contains_variable (**aglat
);
1195 *aglat
= &(**aglat
)->next
;
1198 if (**aglat
&& (**aglat
)->offset
== offset
)
1200 if ((**aglat
)->size
!= val_size
1202 && (**aglat
)->next
->offset
< offset
+ val_size
))
1204 set_agg_lats_to_bottom (dest_plats
);
1207 gcc_checking_assert (!(**aglat
)->next
1208 || (**aglat
)->next
->offset
>= offset
+ val_size
);
1213 struct ipcp_agg_lattice
*new_al
;
1215 if (**aglat
&& (**aglat
)->offset
< offset
+ val_size
)
1217 set_agg_lats_to_bottom (dest_plats
);
1220 if (dest_plats
->aggs_count
== PARAM_VALUE (PARAM_IPA_MAX_AGG_ITEMS
))
1222 dest_plats
->aggs_count
++;
1223 new_al
= (struct ipcp_agg_lattice
*) pool_alloc (ipcp_agg_lattice_pool
);
1224 memset (new_al
, 0, sizeof (*new_al
));
1226 new_al
->offset
= offset
;
1227 new_al
->size
= val_size
;
1228 new_al
->contains_variable
= pre_existing
;
1230 new_al
->next
= **aglat
;
1236 /* Set all AGLAT and all other aggregate lattices reachable by next pointers as
1237 containing an unknown value. */
1240 set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice
*aglat
)
1245 ret
|= set_lattice_contains_variable (aglat
);
1246 aglat
= aglat
->next
;
1251 /* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
1252 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source
1253 parameter used for lattice value sources. Return true if DEST_PLATS changed
1257 merge_aggregate_lattices (struct cgraph_edge
*cs
,
1258 struct ipcp_param_lattices
*dest_plats
,
1259 struct ipcp_param_lattices
*src_plats
,
1260 int src_idx
, HOST_WIDE_INT offset_delta
)
1262 bool pre_existing
= dest_plats
->aggs
!= NULL
;
1263 struct ipcp_agg_lattice
**dst_aglat
;
1266 if (set_check_aggs_by_ref (dest_plats
, src_plats
->aggs_by_ref
))
1268 if (src_plats
->aggs_bottom
)
1269 return set_agg_lats_contain_variable (dest_plats
);
1270 if (src_plats
->aggs_contain_variable
)
1271 ret
|= set_agg_lats_contain_variable (dest_plats
);
1272 dst_aglat
= &dest_plats
->aggs
;
1274 for (struct ipcp_agg_lattice
*src_aglat
= src_plats
->aggs
;
1276 src_aglat
= src_aglat
->next
)
1278 HOST_WIDE_INT new_offset
= src_aglat
->offset
- offset_delta
;
1282 if (merge_agg_lats_step (dest_plats
, new_offset
, src_aglat
->size
,
1283 &dst_aglat
, pre_existing
, &ret
))
1285 struct ipcp_agg_lattice
*new_al
= *dst_aglat
;
1287 dst_aglat
= &(*dst_aglat
)->next
;
1288 if (src_aglat
->bottom
)
1290 ret
|= set_lattice_contains_variable (new_al
);
1293 if (src_aglat
->contains_variable
)
1294 ret
|= set_lattice_contains_variable (new_al
);
1295 for (struct ipcp_value
*val
= src_aglat
->values
;
1298 ret
|= add_value_to_lattice (new_al
, val
->value
, cs
, val
, src_idx
,
1301 else if (dest_plats
->aggs_bottom
)
1304 ret
|= set_chain_of_aglats_contains_variable (*dst_aglat
);
1308 /* Determine whether there is anything to propagate FROM SRC_PLATS through a
1309 pass-through JFUNC and if so, whether it has conform and conforms to the
1310 rules about propagating values passed by reference. */
1313 agg_pass_through_permissible_p (struct ipcp_param_lattices
*src_plats
,
1314 struct ipa_jump_func
*jfunc
)
1316 return src_plats
->aggs
1317 && (!src_plats
->aggs_by_ref
1318 || ipa_get_jf_pass_through_agg_preserved (jfunc
));
1321 /* Propagate scalar values across jump function JFUNC that is associated with
1322 edge CS and put the values into DEST_LAT. */
1325 propagate_aggs_accross_jump_function (struct cgraph_edge
*cs
,
1326 struct ipa_jump_func
*jfunc
,
1327 struct ipcp_param_lattices
*dest_plats
)
1331 if (dest_plats
->aggs_bottom
)
1334 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1335 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
1337 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1338 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1339 struct ipcp_param_lattices
*src_plats
;
1341 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
1342 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
1344 /* Currently we do not produce clobber aggregate jump
1345 functions, replace with merging when we do. */
1346 gcc_assert (!jfunc
->agg
.items
);
1347 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
,
1351 ret
|= set_agg_lats_contain_variable (dest_plats
);
1353 else if (jfunc
->type
== IPA_JF_ANCESTOR
1354 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
1356 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1357 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1358 struct ipcp_param_lattices
*src_plats
;
1360 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
1361 if (src_plats
->aggs
&& src_plats
->aggs_by_ref
)
1363 /* Currently we do not produce clobber aggregate jump
1364 functions, replace with merging when we do. */
1365 gcc_assert (!jfunc
->agg
.items
);
1366 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
, src_idx
,
1367 ipa_get_jf_ancestor_offset (jfunc
));
1369 else if (!src_plats
->aggs_by_ref
)
1370 ret
|= set_agg_lats_to_bottom (dest_plats
);
1372 ret
|= set_agg_lats_contain_variable (dest_plats
);
1374 else if (jfunc
->agg
.items
)
1376 bool pre_existing
= dest_plats
->aggs
!= NULL
;
1377 struct ipcp_agg_lattice
**aglat
= &dest_plats
->aggs
;
1378 struct ipa_agg_jf_item
*item
;
1381 if (set_check_aggs_by_ref (dest_plats
, jfunc
->agg
.by_ref
))
1384 FOR_EACH_VEC_ELT (*jfunc
->agg
.items
, i
, item
)
1386 HOST_WIDE_INT val_size
;
1388 if (item
->offset
< 0)
1390 gcc_checking_assert (is_gimple_ip_invariant (item
->value
));
1391 val_size
= tree_low_cst (TYPE_SIZE (TREE_TYPE (item
->value
)), 1);
1393 if (merge_agg_lats_step (dest_plats
, item
->offset
, val_size
,
1394 &aglat
, pre_existing
, &ret
))
1396 ret
|= add_value_to_lattice (*aglat
, item
->value
, cs
, NULL
, 0, 0);
1397 aglat
= &(*aglat
)->next
;
1399 else if (dest_plats
->aggs_bottom
)
1403 ret
|= set_chain_of_aglats_contains_variable (*aglat
);
1406 ret
|= set_agg_lats_contain_variable (dest_plats
);
1411 /* Propagate constants from the caller to the callee of CS. INFO describes the
1415 propagate_constants_accross_call (struct cgraph_edge
*cs
)
1417 struct ipa_node_params
*callee_info
;
1418 enum availability availability
;
1419 struct cgraph_node
*callee
, *alias_or_thunk
;
1420 struct ipa_edge_args
*args
;
1422 int i
, args_count
, parms_count
;
1424 callee
= cgraph_function_node (cs
->callee
, &availability
);
1425 if (!callee
->symbol
.definition
)
1427 gcc_checking_assert (cgraph_function_with_gimple_body_p (callee
));
1428 callee_info
= IPA_NODE_REF (callee
);
1430 args
= IPA_EDGE_REF (cs
);
1431 args_count
= ipa_get_cs_argument_count (args
);
1432 parms_count
= ipa_get_param_count (callee_info
);
1434 /* If this call goes through a thunk we must not propagate to the first (0th)
1435 parameter. However, we might need to uncover a thunk from below a series
1436 of aliases first. */
1437 alias_or_thunk
= cs
->callee
;
1438 while (alias_or_thunk
->symbol
.alias
)
1439 alias_or_thunk
= cgraph_alias_target (alias_or_thunk
);
1440 if (alias_or_thunk
->thunk
.thunk_p
)
1442 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
1449 for (; (i
< args_count
) && (i
< parms_count
); i
++)
1451 struct ipa_jump_func
*jump_func
= ipa_get_ith_jump_func (args
, i
);
1452 struct ipcp_param_lattices
*dest_plats
;
1454 dest_plats
= ipa_get_parm_lattices (callee_info
, i
);
1455 if (availability
== AVAIL_OVERWRITABLE
)
1456 ret
|= set_all_contains_variable (dest_plats
);
1459 ret
|= propagate_scalar_accross_jump_function (cs
, jump_func
,
1460 &dest_plats
->itself
);
1461 ret
|= propagate_aggs_accross_jump_function (cs
, jump_func
,
1465 for (; i
< parms_count
; i
++)
1466 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
, i
));
1471 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
1472 (which can contain both constants and binfos), KNOWN_BINFOS, KNOWN_AGGS or
1473 AGG_REPS return the destination. The latter three can be NULL. If AGG_REPS
1474 is not NULL, KNOWN_AGGS is ignored. */
1477 ipa_get_indirect_edge_target_1 (struct cgraph_edge
*ie
,
1478 vec
<tree
> known_vals
,
1479 vec
<tree
> known_binfos
,
1480 vec
<ipa_agg_jump_function_p
> known_aggs
,
1481 struct ipa_agg_replacement_value
*agg_reps
)
1483 int param_index
= ie
->indirect_info
->param_index
;
1484 HOST_WIDE_INT token
, anc_offset
;
1489 if (param_index
== -1
1490 || known_vals
.length () <= (unsigned int) param_index
)
1493 if (!ie
->indirect_info
->polymorphic
)
1497 if (ie
->indirect_info
->agg_contents
)
1504 if (agg_reps
->index
== param_index
1505 && agg_reps
->offset
== ie
->indirect_info
->offset
1506 && agg_reps
->by_ref
== ie
->indirect_info
->by_ref
)
1508 t
= agg_reps
->value
;
1511 agg_reps
= agg_reps
->next
;
1514 else if (known_aggs
.length () > (unsigned int) param_index
)
1516 struct ipa_agg_jump_function
*agg
;
1517 agg
= known_aggs
[param_index
];
1518 t
= ipa_find_agg_cst_for_param (agg
, ie
->indirect_info
->offset
,
1519 ie
->indirect_info
->by_ref
);
1525 t
= known_vals
[param_index
];
1528 TREE_CODE (t
) == ADDR_EXPR
1529 && TREE_CODE (TREE_OPERAND (t
, 0)) == FUNCTION_DECL
)
1530 return TREE_OPERAND (t
, 0);
1535 gcc_assert (!ie
->indirect_info
->agg_contents
);
1536 token
= ie
->indirect_info
->otr_token
;
1537 anc_offset
= ie
->indirect_info
->offset
;
1538 otr_type
= ie
->indirect_info
->otr_type
;
1540 t
= known_vals
[param_index
];
1541 if (!t
&& known_binfos
.length () > (unsigned int) param_index
)
1542 t
= known_binfos
[param_index
];
1546 if (TREE_CODE (t
) != TREE_BINFO
)
1549 binfo
= gimple_extract_devirt_binfo_from_cst
1550 (t
, ie
->indirect_info
->otr_type
);
1553 binfo
= get_binfo_at_offset (binfo
, anc_offset
, otr_type
);
1556 target
= gimple_get_virt_method_for_binfo (token
, binfo
);
1562 binfo
= get_binfo_at_offset (t
, anc_offset
, otr_type
);
1565 target
= gimple_get_virt_method_for_binfo (token
, binfo
);
1567 #ifdef ENABLE_CHECKING
1569 gcc_assert (possible_polymorphic_call_target_p
1570 (ie
, cgraph_get_node (target
)));
1577 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
1578 (which can contain both constants and binfos), KNOWN_BINFOS (which can be
1579 NULL) or KNOWN_AGGS (which also can be NULL) return the destination. */
1582 ipa_get_indirect_edge_target (struct cgraph_edge
*ie
,
1583 vec
<tree
> known_vals
,
1584 vec
<tree
> known_binfos
,
1585 vec
<ipa_agg_jump_function_p
> known_aggs
)
1587 return ipa_get_indirect_edge_target_1 (ie
, known_vals
, known_binfos
,
1591 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
1592 and KNOWN_BINFOS. */
1595 devirtualization_time_bonus (struct cgraph_node
*node
,
1596 vec
<tree
> known_csts
,
1597 vec
<tree
> known_binfos
,
1598 vec
<ipa_agg_jump_function_p
> known_aggs
)
1600 struct cgraph_edge
*ie
;
1603 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
1605 struct cgraph_node
*callee
;
1606 struct inline_summary
*isummary
;
1609 target
= ipa_get_indirect_edge_target (ie
, known_csts
, known_binfos
,
1614 /* Only bare minimum benefit for clearly un-inlineable targets. */
1616 callee
= cgraph_get_node (target
);
1617 if (!callee
|| !callee
->symbol
.definition
)
1619 isummary
= inline_summary (callee
);
1620 if (!isummary
->inlinable
)
1623 /* FIXME: The values below need re-considering and perhaps also
1624 integrating into the cost metrics, at lest in some very basic way. */
1625 if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 4)
1627 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 2)
1629 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
1630 || DECL_DECLARED_INLINE_P (callee
->symbol
.decl
))
1637 /* Return time bonus incurred because of HINTS. */
1640 hint_time_bonus (inline_hints hints
)
1643 if (hints
& (INLINE_HINT_loop_iterations
| INLINE_HINT_loop_stride
))
1644 result
+= PARAM_VALUE (PARAM_IPA_CP_LOOP_HINT_BONUS
);
1645 if (hints
& INLINE_HINT_array_index
)
1646 result
+= PARAM_VALUE (PARAM_IPA_CP_ARRAY_INDEX_HINT_BONUS
);
1650 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
1651 and SIZE_COST and with the sum of frequencies of incoming edges to the
1652 potential new clone in FREQUENCIES. */
1655 good_cloning_opportunity_p (struct cgraph_node
*node
, int time_benefit
,
1656 int freq_sum
, gcov_type count_sum
, int size_cost
)
1658 if (time_benefit
== 0
1659 || !flag_ipa_cp_clone
1660 || !optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node
->symbol
.decl
)))
1663 gcc_assert (size_cost
> 0);
1667 int factor
= (count_sum
* 1000) / max_count
;
1668 HOST_WIDEST_INT evaluation
= (((HOST_WIDEST_INT
) time_benefit
* factor
)
1671 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1672 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
1673 "size: %i, count_sum: " HOST_WIDE_INT_PRINT_DEC
1674 ") -> evaluation: " HOST_WIDEST_INT_PRINT_DEC
1675 ", threshold: %i\n",
1676 time_benefit
, size_cost
, (HOST_WIDE_INT
) count_sum
,
1677 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
1679 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
1683 HOST_WIDEST_INT evaluation
= (((HOST_WIDEST_INT
) time_benefit
* freq_sum
)
1686 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1687 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
1688 "size: %i, freq_sum: %i) -> evaluation: "
1689 HOST_WIDEST_INT_PRINT_DEC
", threshold: %i\n",
1690 time_benefit
, size_cost
, freq_sum
, evaluation
,
1691 PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
1693 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
1697 /* Return all context independent values from aggregate lattices in PLATS in a
1698 vector. Return NULL if there are none. */
1700 static vec
<ipa_agg_jf_item_t
, va_gc
> *
1701 context_independent_aggregate_values (struct ipcp_param_lattices
*plats
)
1703 vec
<ipa_agg_jf_item_t
, va_gc
> *res
= NULL
;
1705 if (plats
->aggs_bottom
1706 || plats
->aggs_contain_variable
1707 || plats
->aggs_count
== 0)
1710 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
;
1712 aglat
= aglat
->next
)
1713 if (ipa_lat_is_single_const (aglat
))
1715 struct ipa_agg_jf_item item
;
1716 item
.offset
= aglat
->offset
;
1717 item
.value
= aglat
->values
->value
;
1718 vec_safe_push (res
, item
);
1723 /* Allocate KNOWN_CSTS, KNOWN_BINFOS and, if non-NULL, KNOWN_AGGS and populate
1724 them with values of parameters that are known independent of the context.
1725 INFO describes the function. If REMOVABLE_PARAMS_COST is non-NULL, the
1726 movement cost of all removable parameters will be stored in it. */
1729 gather_context_independent_values (struct ipa_node_params
*info
,
1730 vec
<tree
> *known_csts
,
1731 vec
<tree
> *known_binfos
,
1732 vec
<ipa_agg_jump_function_t
> *known_aggs
,
1733 int *removable_params_cost
)
1735 int i
, count
= ipa_get_param_count (info
);
1738 known_csts
->create (0);
1739 known_binfos
->create (0);
1740 known_csts
->safe_grow_cleared (count
);
1741 known_binfos
->safe_grow_cleared (count
);
1744 known_aggs
->create (0);
1745 known_aggs
->safe_grow_cleared (count
);
1748 if (removable_params_cost
)
1749 *removable_params_cost
= 0;
1751 for (i
= 0; i
< count
; i
++)
1753 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1754 struct ipcp_lattice
*lat
= &plats
->itself
;
1756 if (ipa_lat_is_single_const (lat
))
1758 struct ipcp_value
*val
= lat
->values
;
1759 if (TREE_CODE (val
->value
) != TREE_BINFO
)
1761 (*known_csts
)[i
] = val
->value
;
1762 if (removable_params_cost
)
1763 *removable_params_cost
1764 += estimate_move_cost (TREE_TYPE (val
->value
));
1767 else if (plats
->virt_call
)
1769 (*known_binfos
)[i
] = val
->value
;
1772 else if (removable_params_cost
1773 && !ipa_is_param_used (info
, i
))
1774 *removable_params_cost
+= ipa_get_param_move_cost (info
, i
);
1776 else if (removable_params_cost
1777 && !ipa_is_param_used (info
, i
))
1778 *removable_params_cost
1779 += ipa_get_param_move_cost (info
, i
);
1783 vec
<ipa_agg_jf_item_t
, va_gc
> *agg_items
;
1784 struct ipa_agg_jump_function
*ajf
;
1786 agg_items
= context_independent_aggregate_values (plats
);
1787 ajf
= &(*known_aggs
)[i
];
1788 ajf
->items
= agg_items
;
1789 ajf
->by_ref
= plats
->aggs_by_ref
;
1790 ret
|= agg_items
!= NULL
;
1797 /* The current interface in ipa-inline-analysis requires a pointer vector.
1800 FIXME: That interface should be re-worked, this is slightly silly. Still,
1801 I'd like to discuss how to change it first and this demonstrates the
1804 static vec
<ipa_agg_jump_function_p
>
1805 agg_jmp_p_vec_for_t_vec (vec
<ipa_agg_jump_function_t
> known_aggs
)
1807 vec
<ipa_agg_jump_function_p
> ret
;
1808 struct ipa_agg_jump_function
*ajf
;
1811 ret
.create (known_aggs
.length ());
1812 FOR_EACH_VEC_ELT (known_aggs
, i
, ajf
)
1813 ret
.quick_push (ajf
);
1817 /* Iterate over known values of parameters of NODE and estimate the local
1818 effects in terms of time and size they have. */
1821 estimate_local_effects (struct cgraph_node
*node
)
1823 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1824 int i
, count
= ipa_get_param_count (info
);
1825 vec
<tree
> known_csts
, known_binfos
;
1826 vec
<ipa_agg_jump_function_t
> known_aggs
;
1827 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
;
1829 int base_time
= inline_summary (node
)->time
;
1830 int removable_params_cost
;
1832 if (!count
|| !ipcp_versionable_function_p (node
))
1835 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1836 fprintf (dump_file
, "\nEstimating effects for %s/%i, base_time: %i.\n",
1837 cgraph_node_name (node
), node
->symbol
.order
, base_time
);
1839 always_const
= gather_context_independent_values (info
, &known_csts
,
1840 &known_binfos
, &known_aggs
,
1841 &removable_params_cost
);
1842 known_aggs_ptrs
= agg_jmp_p_vec_for_t_vec (known_aggs
);
1845 struct caller_statistics stats
;
1849 init_caller_stats (&stats
);
1850 cgraph_for_node_and_aliases (node
, gather_caller_stats
, &stats
, false);
1851 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_binfos
,
1852 known_aggs_ptrs
, &size
, &time
, &hints
);
1853 time
-= devirtualization_time_bonus (node
, known_csts
, known_binfos
,
1855 time
-= hint_time_bonus (hints
);
1856 time
-= removable_params_cost
;
1857 size
-= stats
.n_calls
* removable_params_cost
;
1860 fprintf (dump_file
, " - context independent values, size: %i, "
1861 "time_benefit: %i\n", size
, base_time
- time
);
1864 || cgraph_will_be_removed_from_program_if_no_direct_calls (node
))
1866 info
->do_clone_for_all_contexts
= true;
1870 fprintf (dump_file
, " Decided to specialize for all "
1871 "known contexts, code not going to grow.\n");
1873 else if (good_cloning_opportunity_p (node
, base_time
- time
,
1874 stats
.freq_sum
, stats
.count_sum
,
1877 if (size
+ overall_size
<= max_new_size
)
1879 info
->do_clone_for_all_contexts
= true;
1881 overall_size
+= size
;
1884 fprintf (dump_file
, " Decided to specialize for all "
1885 "known contexts, growth deemed beneficial.\n");
1887 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1888 fprintf (dump_file
, " Not cloning for all contexts because "
1889 "max_new_size would be reached with %li.\n",
1890 size
+ overall_size
);
1894 for (i
= 0; i
< count
; i
++)
1896 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1897 struct ipcp_lattice
*lat
= &plats
->itself
;
1898 struct ipcp_value
*val
;
1907 for (val
= lat
->values
; val
; val
= val
->next
)
1909 int time
, size
, time_benefit
;
1912 if (TREE_CODE (val
->value
) != TREE_BINFO
)
1914 known_csts
[i
] = val
->value
;
1915 known_binfos
[i
] = NULL_TREE
;
1916 emc
= estimate_move_cost (TREE_TYPE (val
->value
));
1918 else if (plats
->virt_call
)
1920 known_csts
[i
] = NULL_TREE
;
1921 known_binfos
[i
] = val
->value
;
1927 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_binfos
,
1928 known_aggs_ptrs
, &size
, &time
,
1930 time_benefit
= base_time
- time
1931 + devirtualization_time_bonus (node
, known_csts
, known_binfos
,
1933 + hint_time_bonus (hints
)
1934 + removable_params_cost
+ emc
;
1936 gcc_checking_assert (size
>=0);
1937 /* The inliner-heuristics based estimates may think that in certain
1938 contexts some functions do not have any size at all but we want
1939 all specializations to have at least a tiny cost, not least not to
1944 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1946 fprintf (dump_file
, " - estimates for value ");
1947 print_ipcp_constant_value (dump_file
, val
->value
);
1948 fprintf (dump_file
, " for ");
1949 ipa_dump_param (dump_file
, info
, i
);
1950 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
1951 time_benefit
, size
);
1954 val
->local_time_benefit
= time_benefit
;
1955 val
->local_size_cost
= size
;
1957 known_binfos
[i
] = NULL_TREE
;
1958 known_csts
[i
] = NULL_TREE
;
1961 for (i
= 0; i
< count
; i
++)
1963 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1964 struct ipa_agg_jump_function
*ajf
;
1965 struct ipcp_agg_lattice
*aglat
;
1967 if (plats
->aggs_bottom
|| !plats
->aggs
)
1970 ajf
= &known_aggs
[i
];
1971 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
1973 struct ipcp_value
*val
;
1974 if (aglat
->bottom
|| !aglat
->values
1975 /* If the following is true, the one value is in known_aggs. */
1976 || (!plats
->aggs_contain_variable
1977 && ipa_lat_is_single_const (aglat
)))
1980 for (val
= aglat
->values
; val
; val
= val
->next
)
1982 int time
, size
, time_benefit
;
1983 struct ipa_agg_jf_item item
;
1986 item
.offset
= aglat
->offset
;
1987 item
.value
= val
->value
;
1988 vec_safe_push (ajf
->items
, item
);
1990 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_binfos
,
1991 known_aggs_ptrs
, &size
, &time
,
1993 time_benefit
= base_time
- time
1994 + devirtualization_time_bonus (node
, known_csts
, known_binfos
,
1996 + hint_time_bonus (hints
);
1997 gcc_checking_assert (size
>=0);
2001 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2003 fprintf (dump_file
, " - estimates for value ");
2004 print_ipcp_constant_value (dump_file
, val
->value
);
2005 fprintf (dump_file
, " for ");
2006 ipa_dump_param (dump_file
, info
, i
);
2007 fprintf (dump_file
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
2008 "]: time_benefit: %i, size: %i\n",
2009 plats
->aggs_by_ref
? "ref " : "",
2010 aglat
->offset
, time_benefit
, size
);
2013 val
->local_time_benefit
= time_benefit
;
2014 val
->local_size_cost
= size
;
2020 for (i
= 0; i
< count
; i
++)
2021 vec_free (known_aggs
[i
].items
);
2023 known_csts
.release ();
2024 known_binfos
.release ();
2025 known_aggs
.release ();
2026 known_aggs_ptrs
.release ();
2030 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
2031 topological sort of values. */
2034 add_val_to_toposort (struct ipcp_value
*cur_val
)
2036 static int dfs_counter
= 0;
2037 static struct ipcp_value
*stack
;
2038 struct ipcp_value_source
*src
;
2044 cur_val
->dfs
= dfs_counter
;
2045 cur_val
->low_link
= dfs_counter
;
2047 cur_val
->topo_next
= stack
;
2049 cur_val
->on_stack
= true;
2051 for (src
= cur_val
->sources
; src
; src
= src
->next
)
2054 if (src
->val
->dfs
== 0)
2056 add_val_to_toposort (src
->val
);
2057 if (src
->val
->low_link
< cur_val
->low_link
)
2058 cur_val
->low_link
= src
->val
->low_link
;
2060 else if (src
->val
->on_stack
2061 && src
->val
->dfs
< cur_val
->low_link
)
2062 cur_val
->low_link
= src
->val
->dfs
;
2065 if (cur_val
->dfs
== cur_val
->low_link
)
2067 struct ipcp_value
*v
, *scc_list
= NULL
;
2072 stack
= v
->topo_next
;
2073 v
->on_stack
= false;
2075 v
->scc_next
= scc_list
;
2078 while (v
!= cur_val
);
2080 cur_val
->topo_next
= values_topo
;
2081 values_topo
= cur_val
;
2085 /* Add all values in lattices associated with NODE to the topological sort if
2086 they are not there yet. */
2089 add_all_node_vals_to_toposort (struct cgraph_node
*node
)
2091 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2092 int i
, count
= ipa_get_param_count (info
);
2094 for (i
= 0; i
< count
; i
++)
2096 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2097 struct ipcp_lattice
*lat
= &plats
->itself
;
2098 struct ipcp_agg_lattice
*aglat
;
2099 struct ipcp_value
*val
;
2102 for (val
= lat
->values
; val
; val
= val
->next
)
2103 add_val_to_toposort (val
);
2105 if (!plats
->aggs_bottom
)
2106 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2108 for (val
= aglat
->values
; val
; val
= val
->next
)
2109 add_val_to_toposort (val
);
2113 /* One pass of constants propagation along the call graph edges, from callers
2114 to callees (requires topological ordering in TOPO), iterate over strongly
2115 connected components. */
2118 propagate_constants_topo (struct topo_info
*topo
)
2122 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
2125 struct cgraph_node
*v
, *node
= topo
->order
[i
];
2126 vec
<cgraph_node_ptr
> cycle_nodes
= ipa_get_nodes_in_cycle (node
);
2128 /* First, iteratively propagate within the strongly connected component
2129 until all lattices stabilize. */
2130 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
2131 if (cgraph_function_with_gimple_body_p (v
))
2132 push_node_to_stack (topo
, v
);
2134 v
= pop_node_from_stack (topo
);
2137 struct cgraph_edge
*cs
;
2139 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
2140 if (edge_within_scc (cs
)
2141 && propagate_constants_accross_call (cs
))
2142 push_node_to_stack (topo
, cs
->callee
);
2143 v
= pop_node_from_stack (topo
);
2146 /* Afterwards, propagate along edges leading out of the SCC, calculates
2147 the local effects of the discovered constants and all valid values to
2148 their topological sort. */
2149 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
2150 if (cgraph_function_with_gimple_body_p (v
))
2152 struct cgraph_edge
*cs
;
2154 estimate_local_effects (v
);
2155 add_all_node_vals_to_toposort (v
);
2156 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
2157 if (!edge_within_scc (cs
))
2158 propagate_constants_accross_call (cs
);
2160 cycle_nodes
.release ();
2165 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
2166 the bigger one if otherwise. */
2169 safe_add (int a
, int b
)
2171 if (a
> INT_MAX
/2 || b
> INT_MAX
/2)
2172 return a
> b
? a
: b
;
2178 /* Propagate the estimated effects of individual values along the topological
2179 from the dependent values to those they depend on. */
2182 propagate_effects (void)
2184 struct ipcp_value
*base
;
2186 for (base
= values_topo
; base
; base
= base
->topo_next
)
2188 struct ipcp_value_source
*src
;
2189 struct ipcp_value
*val
;
2190 int time
= 0, size
= 0;
2192 for (val
= base
; val
; val
= val
->scc_next
)
2194 time
= safe_add (time
,
2195 val
->local_time_benefit
+ val
->prop_time_benefit
);
2196 size
= safe_add (size
, val
->local_size_cost
+ val
->prop_size_cost
);
2199 for (val
= base
; val
; val
= val
->scc_next
)
2200 for (src
= val
->sources
; src
; src
= src
->next
)
2202 && cgraph_maybe_hot_edge_p (src
->cs
))
2204 src
->val
->prop_time_benefit
= safe_add (time
,
2205 src
->val
->prop_time_benefit
);
2206 src
->val
->prop_size_cost
= safe_add (size
,
2207 src
->val
->prop_size_cost
);
2213 /* Propagate constants, binfos and their effects from the summaries
2214 interprocedurally. */
2217 ipcp_propagate_stage (struct topo_info
*topo
)
2219 struct cgraph_node
*node
;
2222 fprintf (dump_file
, "\n Propagating constants:\n\n");
2225 ipa_update_after_lto_read ();
2228 FOR_EACH_DEFINED_FUNCTION (node
)
2230 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2232 determine_versionability (node
);
2233 if (cgraph_function_with_gimple_body_p (node
))
2235 info
->lattices
= XCNEWVEC (struct ipcp_param_lattices
,
2236 ipa_get_param_count (info
));
2237 initialize_node_lattices (node
);
2239 if (node
->symbol
.definition
&& !node
->symbol
.alias
)
2240 overall_size
+= inline_summary (node
)->self_size
;
2241 if (node
->count
> max_count
)
2242 max_count
= node
->count
;
2245 max_new_size
= overall_size
;
2246 if (max_new_size
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
2247 max_new_size
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
2248 max_new_size
+= max_new_size
* PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH
) / 100 + 1;
2251 fprintf (dump_file
, "\noverall_size: %li, max_new_size: %li\n",
2252 overall_size
, max_new_size
);
2254 propagate_constants_topo (topo
);
2255 #ifdef ENABLE_CHECKING
2256 ipcp_verify_propagated_values ();
2258 propagate_effects ();
2262 fprintf (dump_file
, "\nIPA lattices after all propagation:\n");
2263 print_all_lattices (dump_file
, (dump_flags
& TDF_DETAILS
), true);
2267 /* Discover newly direct outgoing edges from NODE which is a new clone with
2268 known KNOWN_VALS and make them direct. */
2271 ipcp_discover_new_direct_edges (struct cgraph_node
*node
,
2272 vec
<tree
> known_vals
,
2273 struct ipa_agg_replacement_value
*aggvals
)
2275 struct cgraph_edge
*ie
, *next_ie
;
2278 for (ie
= node
->indirect_calls
; ie
; ie
= next_ie
)
2282 next_ie
= ie
->next_callee
;
2283 target
= ipa_get_indirect_edge_target_1 (ie
, known_vals
, vNULL
, vNULL
,
2287 bool agg_contents
= ie
->indirect_info
->agg_contents
;
2288 bool polymorphic
= ie
->indirect_info
->polymorphic
;
2289 bool param_index
= ie
->indirect_info
->param_index
;
2290 struct cgraph_edge
*cs
= ipa_make_edge_direct_to_target (ie
, target
);
2293 if (cs
&& !agg_contents
&& !polymorphic
)
2295 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2296 int c
= ipa_get_controlled_uses (info
, param_index
);
2297 if (c
!= IPA_UNDESCRIBED_USE
)
2299 struct ipa_ref
*to_del
;
2302 ipa_set_controlled_uses (info
, param_index
, c
);
2303 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2304 fprintf (dump_file
, " controlled uses count of param "
2305 "%i bumped down to %i\n", param_index
, c
);
2307 && (to_del
= ipa_find_reference ((symtab_node
) node
,
2308 (symtab_node
) cs
->callee
,
2311 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2312 fprintf (dump_file
, " and even removing its "
2313 "cloning-created reference\n");
2314 ipa_remove_reference (to_del
);
2320 /* Turning calls to direct calls will improve overall summary. */
2322 inline_update_overall_summary (node
);
2325 /* Vector of pointers which for linked lists of clones of an original crgaph
2328 static vec
<cgraph_edge_p
> next_edge_clone
;
2331 grow_next_edge_clone_vector (void)
2333 if (next_edge_clone
.length ()
2334 <= (unsigned) cgraph_edge_max_uid
)
2335 next_edge_clone
.safe_grow_cleared (cgraph_edge_max_uid
+ 1);
2338 /* Edge duplication hook to grow the appropriate linked list in
2342 ipcp_edge_duplication_hook (struct cgraph_edge
*src
, struct cgraph_edge
*dst
,
2343 __attribute__((unused
)) void *data
)
2345 grow_next_edge_clone_vector ();
2346 next_edge_clone
[dst
->uid
] = next_edge_clone
[src
->uid
];
2347 next_edge_clone
[src
->uid
] = dst
;
2350 /* See if NODE is a clone with a known aggregate value at a given OFFSET of a
2351 parameter with the given INDEX. */
2354 get_clone_agg_value (struct cgraph_node
*node
, HOST_WIDEST_INT offset
,
2357 struct ipa_agg_replacement_value
*aggval
;
2359 aggval
= ipa_get_agg_replacements_for_node (node
);
2362 if (aggval
->offset
== offset
2363 && aggval
->index
== index
)
2364 return aggval
->value
;
2365 aggval
= aggval
->next
;
2370 /* Return true if edge CS does bring about the value described by SRC. */
2373 cgraph_edge_brings_value_p (struct cgraph_edge
*cs
,
2374 struct ipcp_value_source
*src
)
2376 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2377 struct ipa_node_params
*dst_info
= IPA_NODE_REF (cs
->callee
);
2379 if ((dst_info
->ipcp_orig_node
&& !dst_info
->is_all_contexts_clone
)
2380 || caller_info
->node_dead
)
2385 if (caller_info
->ipcp_orig_node
)
2388 if (src
->offset
== -1)
2389 t
= caller_info
->known_vals
[src
->index
];
2391 t
= get_clone_agg_value (cs
->caller
, src
->offset
, src
->index
);
2392 return (t
!= NULL_TREE
2393 && values_equal_for_ipcp_p (src
->val
->value
, t
));
2397 struct ipcp_agg_lattice
*aglat
;
2398 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
2400 if (src
->offset
== -1)
2401 return (ipa_lat_is_single_const (&plats
->itself
)
2402 && values_equal_for_ipcp_p (src
->val
->value
,
2403 plats
->itself
.values
->value
));
2406 if (plats
->aggs_bottom
|| plats
->aggs_contain_variable
)
2408 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2409 if (aglat
->offset
== src
->offset
)
2410 return (ipa_lat_is_single_const (aglat
)
2411 && values_equal_for_ipcp_p (src
->val
->value
,
2412 aglat
->values
->value
));
2418 /* Get the next clone in the linked list of clones of an edge. */
2420 static inline struct cgraph_edge
*
2421 get_next_cgraph_edge_clone (struct cgraph_edge
*cs
)
2423 return next_edge_clone
[cs
->uid
];
2426 /* Given VAL, iterate over all its sources and if they still hold, add their
2427 edge frequency and their number into *FREQUENCY and *CALLER_COUNT
2431 get_info_about_necessary_edges (struct ipcp_value
*val
, int *freq_sum
,
2432 gcov_type
*count_sum
, int *caller_count
)
2434 struct ipcp_value_source
*src
;
2435 int freq
= 0, count
= 0;
2439 for (src
= val
->sources
; src
; src
= src
->next
)
2441 struct cgraph_edge
*cs
= src
->cs
;
2444 if (cgraph_edge_brings_value_p (cs
, src
))
2447 freq
+= cs
->frequency
;
2449 hot
|= cgraph_maybe_hot_edge_p (cs
);
2451 cs
= get_next_cgraph_edge_clone (cs
);
2457 *caller_count
= count
;
2461 /* Return a vector of incoming edges that do bring value VAL. It is assumed
2462 their number is known and equal to CALLER_COUNT. */
2464 static vec
<cgraph_edge_p
>
2465 gather_edges_for_value (struct ipcp_value
*val
, int caller_count
)
2467 struct ipcp_value_source
*src
;
2468 vec
<cgraph_edge_p
> ret
;
2470 ret
.create (caller_count
);
2471 for (src
= val
->sources
; src
; src
= src
->next
)
2473 struct cgraph_edge
*cs
= src
->cs
;
2476 if (cgraph_edge_brings_value_p (cs
, src
))
2477 ret
.quick_push (cs
);
2478 cs
= get_next_cgraph_edge_clone (cs
);
2485 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
2486 Return it or NULL if for some reason it cannot be created. */
2488 static struct ipa_replace_map
*
2489 get_replacement_map (struct ipa_node_params
*info
, tree value
, int parm_num
)
2491 struct ipa_replace_map
*replace_map
;
2494 replace_map
= ggc_alloc_ipa_replace_map ();
2497 fprintf (dump_file
, " replacing ");
2498 ipa_dump_param (dump_file
, info
, parm_num
);
2500 fprintf (dump_file
, " with const ");
2501 print_generic_expr (dump_file
, value
, 0);
2502 fprintf (dump_file
, "\n");
2504 replace_map
->old_tree
= NULL
;
2505 replace_map
->parm_num
= parm_num
;
2506 replace_map
->new_tree
= value
;
2507 replace_map
->replace_p
= true;
2508 replace_map
->ref_p
= false;
2513 /* Dump new profiling counts */
2516 dump_profile_updates (struct cgraph_node
*orig_node
,
2517 struct cgraph_node
*new_node
)
2519 struct cgraph_edge
*cs
;
2521 fprintf (dump_file
, " setting count of the specialized node to "
2522 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) new_node
->count
);
2523 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
2524 fprintf (dump_file
, " edge to %s has count "
2525 HOST_WIDE_INT_PRINT_DEC
"\n",
2526 cgraph_node_name (cs
->callee
), (HOST_WIDE_INT
) cs
->count
);
2528 fprintf (dump_file
, " setting count of the original node to "
2529 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) orig_node
->count
);
2530 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
2531 fprintf (dump_file
, " edge to %s is left with "
2532 HOST_WIDE_INT_PRINT_DEC
"\n",
2533 cgraph_node_name (cs
->callee
), (HOST_WIDE_INT
) cs
->count
);
2536 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
2537 their profile information to reflect this. */
2540 update_profiling_info (struct cgraph_node
*orig_node
,
2541 struct cgraph_node
*new_node
)
2543 struct cgraph_edge
*cs
;
2544 struct caller_statistics stats
;
2545 gcov_type new_sum
, orig_sum
;
2546 gcov_type remainder
, orig_node_count
= orig_node
->count
;
2548 if (orig_node_count
== 0)
2551 init_caller_stats (&stats
);
2552 cgraph_for_node_and_aliases (orig_node
, gather_caller_stats
, &stats
, false);
2553 orig_sum
= stats
.count_sum
;
2554 init_caller_stats (&stats
);
2555 cgraph_for_node_and_aliases (new_node
, gather_caller_stats
, &stats
, false);
2556 new_sum
= stats
.count_sum
;
2558 if (orig_node_count
< orig_sum
+ new_sum
)
2561 fprintf (dump_file
, " Problem: node %s/%i has too low count "
2562 HOST_WIDE_INT_PRINT_DEC
" while the sum of incoming "
2563 "counts is " HOST_WIDE_INT_PRINT_DEC
"\n",
2564 cgraph_node_name (orig_node
), orig_node
->symbol
.order
,
2565 (HOST_WIDE_INT
) orig_node_count
,
2566 (HOST_WIDE_INT
) (orig_sum
+ new_sum
));
2568 orig_node_count
= (orig_sum
+ new_sum
) * 12 / 10;
2570 fprintf (dump_file
, " proceeding by pretending it was "
2571 HOST_WIDE_INT_PRINT_DEC
"\n",
2572 (HOST_WIDE_INT
) orig_node_count
);
2575 new_node
->count
= new_sum
;
2576 remainder
= orig_node_count
- new_sum
;
2577 orig_node
->count
= remainder
;
2579 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
2581 cs
->count
= apply_probability (cs
->count
,
2582 GCOV_COMPUTE_SCALE (new_sum
,
2587 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
2588 cs
->count
= apply_probability (cs
->count
,
2589 GCOV_COMPUTE_SCALE (remainder
,
2593 dump_profile_updates (orig_node
, new_node
);
2596 /* Update the respective profile of specialized NEW_NODE and the original
2597 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
2598 have been redirected to the specialized version. */
2601 update_specialized_profile (struct cgraph_node
*new_node
,
2602 struct cgraph_node
*orig_node
,
2603 gcov_type redirected_sum
)
2605 struct cgraph_edge
*cs
;
2606 gcov_type new_node_count
, orig_node_count
= orig_node
->count
;
2609 fprintf (dump_file
, " the sum of counts of redirected edges is "
2610 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) redirected_sum
);
2611 if (orig_node_count
== 0)
2614 gcc_assert (orig_node_count
>= redirected_sum
);
2616 new_node_count
= new_node
->count
;
2617 new_node
->count
+= redirected_sum
;
2618 orig_node
->count
-= redirected_sum
;
2620 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
2622 cs
->count
+= apply_probability (cs
->count
,
2623 GCOV_COMPUTE_SCALE (redirected_sum
,
2628 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
2630 gcov_type dec
= apply_probability (cs
->count
,
2631 GCOV_COMPUTE_SCALE (redirected_sum
,
2633 if (dec
< cs
->count
)
2640 dump_profile_updates (orig_node
, new_node
);
2643 /* Create a specialized version of NODE with known constants and types of
2644 parameters in KNOWN_VALS and redirect all edges in CALLERS to it. */
2646 static struct cgraph_node
*
2647 create_specialized_node (struct cgraph_node
*node
,
2648 vec
<tree
> known_vals
,
2649 struct ipa_agg_replacement_value
*aggvals
,
2650 vec
<cgraph_edge_p
> callers
)
2652 struct ipa_node_params
*new_info
, *info
= IPA_NODE_REF (node
);
2653 vec
<ipa_replace_map_p
, va_gc
> *replace_trees
= NULL
;
2654 struct ipa_agg_replacement_value
*av
;
2655 struct cgraph_node
*new_node
;
2656 int i
, count
= ipa_get_param_count (info
);
2657 bitmap args_to_skip
;
2659 gcc_assert (!info
->ipcp_orig_node
);
2661 if (node
->local
.can_change_signature
)
2663 args_to_skip
= BITMAP_GGC_ALLOC ();
2664 for (i
= 0; i
< count
; i
++)
2666 tree t
= known_vals
[i
];
2668 if ((t
&& TREE_CODE (t
) != TREE_BINFO
)
2669 || !ipa_is_param_used (info
, i
))
2670 bitmap_set_bit (args_to_skip
, i
);
2675 args_to_skip
= NULL
;
2676 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2677 fprintf (dump_file
, " cannot change function signature\n");
2680 for (i
= 0; i
< count
; i
++)
2682 tree t
= known_vals
[i
];
2683 if (t
&& TREE_CODE (t
) != TREE_BINFO
)
2685 struct ipa_replace_map
*replace_map
;
2687 replace_map
= get_replacement_map (info
, t
, i
);
2689 vec_safe_push (replace_trees
, replace_map
);
2693 new_node
= cgraph_create_virtual_clone (node
, callers
, replace_trees
,
2694 args_to_skip
, "constprop");
2695 ipa_set_node_agg_value_chain (new_node
, aggvals
);
2696 for (av
= aggvals
; av
; av
= av
->next
)
2697 ipa_maybe_record_reference ((symtab_node
) new_node
, av
->value
,
2698 IPA_REF_ADDR
, NULL
);
2700 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2702 fprintf (dump_file
, " the new node is %s/%i.\n",
2703 cgraph_node_name (new_node
), new_node
->symbol
.order
);
2705 ipa_dump_agg_replacement_values (dump_file
, aggvals
);
2707 gcc_checking_assert (ipa_node_params_vector
.exists ()
2708 && (ipa_node_params_vector
.length ()
2709 > (unsigned) cgraph_max_uid
));
2710 update_profiling_info (node
, new_node
);
2711 new_info
= IPA_NODE_REF (new_node
);
2712 new_info
->ipcp_orig_node
= node
;
2713 new_info
->known_vals
= known_vals
;
2715 ipcp_discover_new_direct_edges (new_node
, known_vals
, aggvals
);
2721 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
2722 KNOWN_VALS with constants and types that are also known for all of the
2726 find_more_scalar_values_for_callers_subset (struct cgraph_node
*node
,
2727 vec
<tree
> known_vals
,
2728 vec
<cgraph_edge_p
> callers
)
2730 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2731 int i
, count
= ipa_get_param_count (info
);
2733 for (i
= 0; i
< count
; i
++)
2735 struct cgraph_edge
*cs
;
2736 tree newval
= NULL_TREE
;
2739 if (ipa_get_scalar_lat (info
, i
)->bottom
|| known_vals
[i
])
2742 FOR_EACH_VEC_ELT (callers
, j
, cs
)
2744 struct ipa_jump_func
*jump_func
;
2747 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
)))
2752 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
2753 t
= ipa_value_from_jfunc (IPA_NODE_REF (cs
->caller
), jump_func
);
2756 && !values_equal_for_ipcp_p (t
, newval
)))
2767 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2769 fprintf (dump_file
, " adding an extra known scalar value ");
2770 print_ipcp_constant_value (dump_file
, newval
);
2771 fprintf (dump_file
, " for ");
2772 ipa_dump_param (dump_file
, info
, i
);
2773 fprintf (dump_file
, "\n");
2776 known_vals
[i
] = newval
;
2781 /* Go through PLATS and create a vector of values consisting of values and
2782 offsets (minus OFFSET) of lattices that contain only a single value. */
2784 static vec
<ipa_agg_jf_item_t
>
2785 copy_plats_to_inter (struct ipcp_param_lattices
*plats
, HOST_WIDE_INT offset
)
2787 vec
<ipa_agg_jf_item_t
> res
= vNULL
;
2789 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
2792 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2793 if (ipa_lat_is_single_const (aglat
))
2795 struct ipa_agg_jf_item ti
;
2796 ti
.offset
= aglat
->offset
- offset
;
2797 ti
.value
= aglat
->values
->value
;
2803 /* Intersect all values in INTER with single value lattices in PLATS (while
2804 subtracting OFFSET). */
2807 intersect_with_plats (struct ipcp_param_lattices
*plats
,
2808 vec
<ipa_agg_jf_item_t
> *inter
,
2809 HOST_WIDE_INT offset
)
2811 struct ipcp_agg_lattice
*aglat
;
2812 struct ipa_agg_jf_item
*item
;
2815 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
2821 aglat
= plats
->aggs
;
2822 FOR_EACH_VEC_ELT (*inter
, k
, item
)
2829 if (aglat
->offset
- offset
> item
->offset
)
2831 if (aglat
->offset
- offset
== item
->offset
)
2833 gcc_checking_assert (item
->value
);
2834 if (values_equal_for_ipcp_p (item
->value
, aglat
->values
->value
))
2838 aglat
= aglat
->next
;
2841 item
->value
= NULL_TREE
;
2845 /* Copy agggregate replacement values of NODE (which is an IPA-CP clone) to the
2846 vector result while subtracting OFFSET from the individual value offsets. */
2848 static vec
<ipa_agg_jf_item_t
>
2849 agg_replacements_to_vector (struct cgraph_node
*node
, int index
,
2850 HOST_WIDE_INT offset
)
2852 struct ipa_agg_replacement_value
*av
;
2853 vec
<ipa_agg_jf_item_t
> res
= vNULL
;
2855 for (av
= ipa_get_agg_replacements_for_node (node
); av
; av
= av
->next
)
2856 if (av
->index
== index
2857 && (av
->offset
- offset
) >= 0)
2859 struct ipa_agg_jf_item item
;
2860 gcc_checking_assert (av
->value
);
2861 item
.offset
= av
->offset
- offset
;
2862 item
.value
= av
->value
;
2863 res
.safe_push (item
);
2869 /* Intersect all values in INTER with those that we have already scheduled to
2870 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
2871 (while subtracting OFFSET). */
2874 intersect_with_agg_replacements (struct cgraph_node
*node
, int index
,
2875 vec
<ipa_agg_jf_item_t
> *inter
,
2876 HOST_WIDE_INT offset
)
2878 struct ipa_agg_replacement_value
*srcvals
;
2879 struct ipa_agg_jf_item
*item
;
2882 srcvals
= ipa_get_agg_replacements_for_node (node
);
2889 FOR_EACH_VEC_ELT (*inter
, i
, item
)
2891 struct ipa_agg_replacement_value
*av
;
2895 for (av
= srcvals
; av
; av
= av
->next
)
2897 gcc_checking_assert (av
->value
);
2898 if (av
->index
== index
2899 && av
->offset
- offset
== item
->offset
)
2901 if (values_equal_for_ipcp_p (item
->value
, av
->value
))
2907 item
->value
= NULL_TREE
;
2911 /* Intersect values in INTER with aggregate values that come along edge CS to
2912 parameter number INDEX and return it. If INTER does not actually exist yet,
2913 copy all incoming values to it. If we determine we ended up with no values
2914 whatsoever, return a released vector. */
2916 static vec
<ipa_agg_jf_item_t
>
2917 intersect_aggregates_with_edge (struct cgraph_edge
*cs
, int index
,
2918 vec
<ipa_agg_jf_item_t
> inter
)
2920 struct ipa_jump_func
*jfunc
;
2921 jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), index
);
2922 if (jfunc
->type
== IPA_JF_PASS_THROUGH
2923 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
2925 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2926 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
2928 if (caller_info
->ipcp_orig_node
)
2930 struct cgraph_node
*orig_node
= caller_info
->ipcp_orig_node
;
2931 struct ipcp_param_lattices
*orig_plats
;
2932 orig_plats
= ipa_get_parm_lattices (IPA_NODE_REF (orig_node
),
2934 if (agg_pass_through_permissible_p (orig_plats
, jfunc
))
2936 if (!inter
.exists ())
2937 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, 0);
2939 intersect_with_agg_replacements (cs
->caller
, src_idx
,
2945 struct ipcp_param_lattices
*src_plats
;
2946 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2947 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
2949 /* Currently we do not produce clobber aggregate jump
2950 functions, adjust when we do. */
2951 gcc_checking_assert (!jfunc
->agg
.items
);
2952 if (!inter
.exists ())
2953 inter
= copy_plats_to_inter (src_plats
, 0);
2955 intersect_with_plats (src_plats
, &inter
, 0);
2959 else if (jfunc
->type
== IPA_JF_ANCESTOR
2960 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
2962 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2963 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
2964 struct ipcp_param_lattices
*src_plats
;
2965 HOST_WIDE_INT delta
= ipa_get_jf_ancestor_offset (jfunc
);
2967 if (caller_info
->ipcp_orig_node
)
2969 if (!inter
.exists ())
2970 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, delta
);
2972 intersect_with_agg_replacements (cs
->caller
, src_idx
, &inter
,
2977 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);;
2978 /* Currently we do not produce clobber aggregate jump
2979 functions, adjust when we do. */
2980 gcc_checking_assert (!src_plats
->aggs
|| !jfunc
->agg
.items
);
2981 if (!inter
.exists ())
2982 inter
= copy_plats_to_inter (src_plats
, delta
);
2984 intersect_with_plats (src_plats
, &inter
, delta
);
2987 else if (jfunc
->agg
.items
)
2989 struct ipa_agg_jf_item
*item
;
2992 if (!inter
.exists ())
2993 for (unsigned i
= 0; i
< jfunc
->agg
.items
->length (); i
++)
2994 inter
.safe_push ((*jfunc
->agg
.items
)[i
]);
2996 FOR_EACH_VEC_ELT (inter
, k
, item
)
2999 bool found
= false;;
3004 while ((unsigned) l
< jfunc
->agg
.items
->length ())
3006 struct ipa_agg_jf_item
*ti
;
3007 ti
= &(*jfunc
->agg
.items
)[l
];
3008 if (ti
->offset
> item
->offset
)
3010 if (ti
->offset
== item
->offset
)
3012 gcc_checking_assert (ti
->value
);
3013 if (values_equal_for_ipcp_p (item
->value
,
3027 return vec
<ipa_agg_jf_item_t
>();
3032 /* Look at edges in CALLERS and collect all known aggregate values that arrive
3033 from all of them. */
3035 static struct ipa_agg_replacement_value
*
3036 find_aggregate_values_for_callers_subset (struct cgraph_node
*node
,
3037 vec
<cgraph_edge_p
> callers
)
3039 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
3040 struct ipa_agg_replacement_value
*res
= NULL
;
3041 struct cgraph_edge
*cs
;
3042 int i
, j
, count
= ipa_get_param_count (dest_info
);
3044 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3046 int c
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
3051 for (i
= 0; i
< count
; i
++)
3053 struct cgraph_edge
*cs
;
3054 vec
<ipa_agg_jf_item_t
> inter
= vNULL
;
3055 struct ipa_agg_jf_item
*item
;
3056 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (dest_info
, i
);
3059 /* Among other things, the following check should deal with all by_ref
3061 if (plats
->aggs_bottom
)
3064 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3066 inter
= intersect_aggregates_with_edge (cs
, i
, inter
);
3068 if (!inter
.exists ())
3072 FOR_EACH_VEC_ELT (inter
, j
, item
)
3074 struct ipa_agg_replacement_value
*v
;
3079 v
= ggc_alloc_ipa_agg_replacement_value ();
3081 v
->offset
= item
->offset
;
3082 v
->value
= item
->value
;
3083 v
->by_ref
= plats
->aggs_by_ref
;
3089 if (inter
.exists ())
3095 /* Turn KNOWN_AGGS into a list of aggreate replacement values. */
3097 static struct ipa_agg_replacement_value
*
3098 known_aggs_to_agg_replacement_list (vec
<ipa_agg_jump_function_t
> known_aggs
)
3100 struct ipa_agg_replacement_value
*res
= NULL
;
3101 struct ipa_agg_jump_function
*aggjf
;
3102 struct ipa_agg_jf_item
*item
;
3105 FOR_EACH_VEC_ELT (known_aggs
, i
, aggjf
)
3106 FOR_EACH_VEC_SAFE_ELT (aggjf
->items
, j
, item
)
3108 struct ipa_agg_replacement_value
*v
;
3109 v
= ggc_alloc_ipa_agg_replacement_value ();
3111 v
->offset
= item
->offset
;
3112 v
->value
= item
->value
;
3113 v
->by_ref
= aggjf
->by_ref
;
3120 /* Determine whether CS also brings all scalar values that the NODE is
3124 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge
*cs
,
3125 struct cgraph_node
*node
)
3127 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
3128 int count
= ipa_get_param_count (dest_info
);
3129 struct ipa_node_params
*caller_info
;
3130 struct ipa_edge_args
*args
;
3133 caller_info
= IPA_NODE_REF (cs
->caller
);
3134 args
= IPA_EDGE_REF (cs
);
3135 for (i
= 0; i
< count
; i
++)
3137 struct ipa_jump_func
*jump_func
;
3140 val
= dest_info
->known_vals
[i
];
3144 if (i
>= ipa_get_cs_argument_count (args
))
3146 jump_func
= ipa_get_ith_jump_func (args
, i
);
3147 t
= ipa_value_from_jfunc (caller_info
, jump_func
);
3148 if (!t
|| !values_equal_for_ipcp_p (val
, t
))
3154 /* Determine whether CS also brings all aggregate values that NODE is
3157 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge
*cs
,
3158 struct cgraph_node
*node
)
3160 struct ipa_node_params
*orig_caller_info
= IPA_NODE_REF (cs
->caller
);
3161 struct ipa_agg_replacement_value
*aggval
;
3164 aggval
= ipa_get_agg_replacements_for_node (node
);
3168 count
= ipa_get_param_count (IPA_NODE_REF (node
));
3169 ec
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
3171 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
3172 if (aggval
->index
>= ec
)
3175 if (orig_caller_info
->ipcp_orig_node
)
3176 orig_caller_info
= IPA_NODE_REF (orig_caller_info
->ipcp_orig_node
);
3178 for (i
= 0; i
< count
; i
++)
3180 static vec
<ipa_agg_jf_item_t
> values
= vec
<ipa_agg_jf_item_t
>();
3181 struct ipcp_param_lattices
*plats
;
3182 bool interesting
= false;
3183 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
3184 if (aggval
->index
== i
)
3192 plats
= ipa_get_parm_lattices (orig_caller_info
, aggval
->index
);
3193 if (plats
->aggs_bottom
)
3196 values
= intersect_aggregates_with_edge (cs
, i
, values
);
3197 if (!values
.exists())
3200 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
3201 if (aggval
->index
== i
)
3203 struct ipa_agg_jf_item
*item
;
3206 FOR_EACH_VEC_ELT (values
, j
, item
)
3208 && item
->offset
== av
->offset
3209 && values_equal_for_ipcp_p (item
->value
, av
->value
))
3224 /* Given an original NODE and a VAL for which we have already created a
3225 specialized clone, look whether there are incoming edges that still lead
3226 into the old node but now also bring the requested value and also conform to
3227 all other criteria such that they can be redirected the the special node.
3228 This function can therefore redirect the final edge in a SCC. */
3231 perhaps_add_new_callers (struct cgraph_node
*node
, struct ipcp_value
*val
)
3233 struct ipcp_value_source
*src
;
3234 gcov_type redirected_sum
= 0;
3236 for (src
= val
->sources
; src
; src
= src
->next
)
3238 struct cgraph_edge
*cs
= src
->cs
;
3241 enum availability availability
;
3242 struct cgraph_node
*dst
= cgraph_function_node (cs
->callee
,
3244 if ((dst
== node
|| IPA_NODE_REF (dst
)->is_all_contexts_clone
)
3245 && availability
> AVAIL_OVERWRITABLE
3246 && cgraph_edge_brings_value_p (cs
, src
))
3248 if (cgraph_edge_brings_all_scalars_for_node (cs
, val
->spec_node
)
3249 && cgraph_edge_brings_all_agg_vals_for_node (cs
,
3253 fprintf (dump_file
, " - adding an extra caller %s/%i"
3255 xstrdup (cgraph_node_name (cs
->caller
)),
3256 cs
->caller
->symbol
.order
,
3257 xstrdup (cgraph_node_name (val
->spec_node
)),
3258 val
->spec_node
->symbol
.order
);
3260 cgraph_redirect_edge_callee (cs
, val
->spec_node
);
3261 redirected_sum
+= cs
->count
;
3264 cs
= get_next_cgraph_edge_clone (cs
);
3269 update_specialized_profile (val
->spec_node
, node
, redirected_sum
);
3273 /* Copy KNOWN_BINFOS to KNOWN_VALS. */
3276 move_binfos_to_values (vec
<tree
> known_vals
,
3277 vec
<tree
> known_binfos
)
3282 for (i
= 0; known_binfos
.iterate (i
, &t
); i
++)
3287 /* Return true if there is a replacement equivalent to VALUE, INDEX and OFFSET
3288 among those in the AGGVALS list. */
3291 ipcp_val_in_agg_replacements_p (struct ipa_agg_replacement_value
*aggvals
,
3292 int index
, HOST_WIDE_INT offset
, tree value
)
3296 if (aggvals
->index
== index
3297 && aggvals
->offset
== offset
3298 && values_equal_for_ipcp_p (aggvals
->value
, value
))
3300 aggvals
= aggvals
->next
;
3305 /* Decide wheter to create a special version of NODE for value VAL of parameter
3306 at the given INDEX. If OFFSET is -1, the value is for the parameter itself,
3307 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS,
3308 KNOWN_BINFOS and KNOWN_AGGS describe the other already known values. */
3311 decide_about_value (struct cgraph_node
*node
, int index
, HOST_WIDE_INT offset
,
3312 struct ipcp_value
*val
, vec
<tree
> known_csts
,
3313 vec
<tree
> known_binfos
)
3315 struct ipa_agg_replacement_value
*aggvals
;
3316 int freq_sum
, caller_count
;
3317 gcov_type count_sum
;
3318 vec
<cgraph_edge_p
> callers
;
3323 perhaps_add_new_callers (node
, val
);
3326 else if (val
->local_size_cost
+ overall_size
> max_new_size
)
3328 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3329 fprintf (dump_file
, " Ignoring candidate value because "
3330 "max_new_size would be reached with %li.\n",
3331 val
->local_size_cost
+ overall_size
);
3334 else if (!get_info_about_necessary_edges (val
, &freq_sum
, &count_sum
,
3338 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3340 fprintf (dump_file
, " - considering value ");
3341 print_ipcp_constant_value (dump_file
, val
->value
);
3342 fprintf (dump_file
, " for ");
3343 ipa_dump_param (dump_file
, IPA_NODE_REF (node
), index
);
3345 fprintf (dump_file
, ", offset: " HOST_WIDE_INT_PRINT_DEC
, offset
);
3346 fprintf (dump_file
, " (caller_count: %i)\n", caller_count
);
3349 if (!good_cloning_opportunity_p (node
, val
->local_time_benefit
,
3350 freq_sum
, count_sum
,
3351 val
->local_size_cost
)
3352 && !good_cloning_opportunity_p (node
,
3353 val
->local_time_benefit
3354 + val
->prop_time_benefit
,
3355 freq_sum
, count_sum
,
3356 val
->local_size_cost
3357 + val
->prop_size_cost
))
3361 fprintf (dump_file
, " Creating a specialized node of %s/%i.\n",
3362 cgraph_node_name (node
), node
->symbol
.order
);
3364 callers
= gather_edges_for_value (val
, caller_count
);
3365 kv
= known_csts
.copy ();
3366 move_binfos_to_values (kv
, known_binfos
);
3368 kv
[index
] = val
->value
;
3369 find_more_scalar_values_for_callers_subset (node
, kv
, callers
);
3370 aggvals
= find_aggregate_values_for_callers_subset (node
, callers
);
3371 gcc_checking_assert (offset
== -1
3372 || ipcp_val_in_agg_replacements_p (aggvals
, index
,
3373 offset
, val
->value
));
3374 val
->spec_node
= create_specialized_node (node
, kv
, aggvals
, callers
);
3375 overall_size
+= val
->local_size_cost
;
3377 /* TODO: If for some lattice there is only one other known value
3378 left, make a special node for it too. */
3383 /* Decide whether and what specialized clones of NODE should be created. */
3386 decide_whether_version_node (struct cgraph_node
*node
)
3388 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3389 int i
, count
= ipa_get_param_count (info
);
3390 vec
<tree
> known_csts
, known_binfos
;
3391 vec
<ipa_agg_jump_function_t
> known_aggs
= vNULL
;
3397 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3398 fprintf (dump_file
, "\nEvaluating opportunities for %s/%i.\n",
3399 cgraph_node_name (node
), node
->symbol
.order
);
3401 gather_context_independent_values (info
, &known_csts
, &known_binfos
,
3402 info
->do_clone_for_all_contexts
? &known_aggs
3405 for (i
= 0; i
< count
;i
++)
3407 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3408 struct ipcp_lattice
*lat
= &plats
->itself
;
3409 struct ipcp_value
*val
;
3413 && !known_binfos
[i
])
3414 for (val
= lat
->values
; val
; val
= val
->next
)
3415 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
3418 if (!plats
->aggs_bottom
)
3420 struct ipcp_agg_lattice
*aglat
;
3421 struct ipcp_value
*val
;
3422 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3423 if (!aglat
->bottom
&& aglat
->values
3424 /* If the following is false, the one value is in
3426 && (plats
->aggs_contain_variable
3427 || !ipa_lat_is_single_const (aglat
)))
3428 for (val
= aglat
->values
; val
; val
= val
->next
)
3429 ret
|= decide_about_value (node
, i
, aglat
->offset
, val
,
3430 known_csts
, known_binfos
);
3432 info
= IPA_NODE_REF (node
);
3435 if (info
->do_clone_for_all_contexts
)
3437 struct cgraph_node
*clone
;
3438 vec
<cgraph_edge_p
> callers
;
3441 fprintf (dump_file
, " - Creating a specialized node of %s/%i "
3442 "for all known contexts.\n", cgraph_node_name (node
),
3443 node
->symbol
.order
);
3445 callers
= collect_callers_of_node (node
);
3446 move_binfos_to_values (known_csts
, known_binfos
);
3447 clone
= create_specialized_node (node
, known_csts
,
3448 known_aggs_to_agg_replacement_list (known_aggs
),
3450 info
= IPA_NODE_REF (node
);
3451 info
->do_clone_for_all_contexts
= false;
3452 IPA_NODE_REF (clone
)->is_all_contexts_clone
= true;
3453 for (i
= 0; i
< count
; i
++)
3454 vec_free (known_aggs
[i
].items
);
3455 known_aggs
.release ();
3459 known_csts
.release ();
3461 known_binfos
.release ();
3465 /* Transitively mark all callees of NODE within the same SCC as not dead. */
3468 spread_undeadness (struct cgraph_node
*node
)
3470 struct cgraph_edge
*cs
;
3472 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
3473 if (edge_within_scc (cs
))
3475 struct cgraph_node
*callee
;
3476 struct ipa_node_params
*info
;
3478 callee
= cgraph_function_node (cs
->callee
, NULL
);
3479 info
= IPA_NODE_REF (callee
);
3481 if (info
->node_dead
)
3483 info
->node_dead
= 0;
3484 spread_undeadness (callee
);
3489 /* Return true if NODE has a caller from outside of its SCC that is not
3490 dead. Worker callback for cgraph_for_node_and_aliases. */
3493 has_undead_caller_from_outside_scc_p (struct cgraph_node
*node
,
3494 void *data ATTRIBUTE_UNUSED
)
3496 struct cgraph_edge
*cs
;
3498 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
3499 if (cs
->caller
->thunk
.thunk_p
3500 && cgraph_for_node_and_aliases (cs
->caller
,
3501 has_undead_caller_from_outside_scc_p
,
3504 else if (!edge_within_scc (cs
)
3505 && !IPA_NODE_REF (cs
->caller
)->node_dead
)
3511 /* Identify nodes within the same SCC as NODE which are no longer needed
3512 because of new clones and will be removed as unreachable. */
3515 identify_dead_nodes (struct cgraph_node
*node
)
3517 struct cgraph_node
*v
;
3518 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->symbol
.aux
)->next_cycle
)
3519 if (cgraph_will_be_removed_from_program_if_no_direct_calls (v
)
3520 && !cgraph_for_node_and_aliases (v
,
3521 has_undead_caller_from_outside_scc_p
,
3523 IPA_NODE_REF (v
)->node_dead
= 1;
3525 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->symbol
.aux
)->next_cycle
)
3526 if (!IPA_NODE_REF (v
)->node_dead
)
3527 spread_undeadness (v
);
3529 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3531 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->symbol
.aux
)->next_cycle
)
3532 if (IPA_NODE_REF (v
)->node_dead
)
3533 fprintf (dump_file
, " Marking node as dead: %s/%i.\n",
3534 cgraph_node_name (v
), v
->symbol
.order
);
3538 /* The decision stage. Iterate over the topological order of call graph nodes
3539 TOPO and make specialized clones if deemed beneficial. */
3542 ipcp_decision_stage (struct topo_info
*topo
)
3547 fprintf (dump_file
, "\nIPA decision stage:\n\n");
3549 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
3551 struct cgraph_node
*node
= topo
->order
[i
];
3552 bool change
= false, iterate
= true;
3556 struct cgraph_node
*v
;
3558 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->symbol
.aux
)->next_cycle
)
3559 if (cgraph_function_with_gimple_body_p (v
)
3560 && ipcp_versionable_function_p (v
))
3561 iterate
|= decide_whether_version_node (v
);
3566 identify_dead_nodes (node
);
3570 /* The IPCP driver. */
3575 struct cgraph_2edge_hook_list
*edge_duplication_hook_holder
;
3576 struct topo_info topo
;
3578 ipa_check_create_node_params ();
3579 ipa_check_create_edge_args ();
3580 grow_next_edge_clone_vector ();
3581 edge_duplication_hook_holder
=
3582 cgraph_add_edge_duplication_hook (&ipcp_edge_duplication_hook
, NULL
);
3583 ipcp_values_pool
= create_alloc_pool ("IPA-CP values",
3584 sizeof (struct ipcp_value
), 32);
3585 ipcp_sources_pool
= create_alloc_pool ("IPA-CP value sources",
3586 sizeof (struct ipcp_value_source
), 64);
3587 ipcp_agg_lattice_pool
= create_alloc_pool ("IPA_CP aggregate lattices",
3588 sizeof (struct ipcp_agg_lattice
),
3592 fprintf (dump_file
, "\nIPA structures before propagation:\n");
3593 if (dump_flags
& TDF_DETAILS
)
3594 ipa_print_all_params (dump_file
);
3595 ipa_print_all_jump_functions (dump_file
);
3598 /* Topological sort. */
3599 build_toporder_info (&topo
);
3600 /* Do the interprocedural propagation. */
3601 ipcp_propagate_stage (&topo
);
3602 /* Decide what constant propagation and cloning should be performed. */
3603 ipcp_decision_stage (&topo
);
3605 /* Free all IPCP structures. */
3606 free_toporder_info (&topo
);
3607 next_edge_clone
.release ();
3608 cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder
);
3609 ipa_free_all_structures_after_ipa_cp ();
3611 fprintf (dump_file
, "\nIPA constant propagation end\n");
3615 /* Initialization and computation of IPCP data structures. This is the initial
3616 intraprocedural analysis of functions, which gathers information to be
3617 propagated later on. */
3620 ipcp_generate_summary (void)
3622 struct cgraph_node
*node
;
3625 fprintf (dump_file
, "\nIPA constant propagation start:\n");
3626 ipa_register_cgraph_hooks ();
3628 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
3630 node
->local
.versionable
3631 = tree_versionable_function_p (node
->symbol
.decl
);
3632 ipa_analyze_node (node
);
3636 /* Write ipcp summary for nodes in SET. */
3639 ipcp_write_summary (void)
3641 ipa_prop_write_jump_functions ();
3644 /* Read ipcp summary. */
3647 ipcp_read_summary (void)
3649 ipa_prop_read_jump_functions ();
3652 /* Gate for IPCP optimization. */
3655 cgraph_gate_cp (void)
3657 /* FIXME: We should remove the optimize check after we ensure we never run
3658 IPA passes when not optimizing. */
3659 return flag_ipa_cp
&& optimize
;
3664 const pass_data pass_data_ipa_cp
=
3666 IPA_PASS
, /* type */
3668 OPTGROUP_NONE
, /* optinfo_flags */
3669 true, /* has_gate */
3670 true, /* has_execute */
3671 TV_IPA_CONSTANT_PROP
, /* tv_id */
3672 0, /* properties_required */
3673 0, /* properties_provided */
3674 0, /* properties_destroyed */
3675 0, /* todo_flags_start */
3676 ( TODO_dump_symtab
| TODO_remove_functions
), /* todo_flags_finish */
3679 class pass_ipa_cp
: public ipa_opt_pass_d
3682 pass_ipa_cp(gcc::context
*ctxt
)
3683 : ipa_opt_pass_d(pass_data_ipa_cp
, ctxt
,
3684 ipcp_generate_summary
, /* generate_summary */
3685 ipcp_write_summary
, /* write_summary */
3686 ipcp_read_summary
, /* read_summary */
3687 ipa_prop_write_all_agg_replacement
, /*
3688 write_optimization_summary */
3689 ipa_prop_read_all_agg_replacement
, /*
3690 read_optimization_summary */
3691 NULL
, /* stmt_fixup */
3692 0, /* function_transform_todo_flags_start */
3693 ipcp_transform_function
, /* function_transform */
3694 NULL
) /* variable_transform */
3697 /* opt_pass methods: */
3698 bool gate () { return cgraph_gate_cp (); }
3699 unsigned int execute () { return ipcp_driver (); }
3701 }; // class pass_ipa_cp
3706 make_pass_ipa_cp (gcc::context
*ctxt
)
3708 return new pass_ipa_cp (ctxt
);