1 /* Interprocedural constant propagation
2 Copyright (C) 2005-2016 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"
108 #include "gimple-expr.h"
110 #include "alloc-pool.h"
111 #include "tree-pass.h"
113 #include "diagnostic.h"
114 #include "fold-const.h"
115 #include "gimple-fold.h"
116 #include "symbol-summary.h"
117 #include "ipa-prop.h"
118 #include "tree-pretty-print.h"
119 #include "tree-inline.h"
121 #include "ipa-inline.h"
122 #include "ipa-utils.h"
123 #include "tree-ssa-ccp.h"
125 template <typename valtype
> class ipcp_value
;
127 /* Describes a particular source for an IPA-CP value. */
129 template <typename valtype
>
130 class ipcp_value_source
133 /* Aggregate offset of the source, negative if the source is scalar value of
134 the argument itself. */
135 HOST_WIDE_INT offset
;
136 /* The incoming edge that brought the value. */
138 /* If the jump function that resulted into his value was a pass-through or an
139 ancestor, this is the ipcp_value of the caller from which the described
140 value has been derived. Otherwise it is NULL. */
141 ipcp_value
<valtype
> *val
;
142 /* Next pointer in a linked list of sources of a value. */
143 ipcp_value_source
*next
;
144 /* If the jump function that resulted into his value was a pass-through or an
145 ancestor, this is the index of the parameter of the caller the jump
146 function references. */
150 /* Common ancestor for all ipcp_value instantiations. */
152 class ipcp_value_base
155 /* Time benefit and size cost that specializing the function for this value
156 would bring about in this function alone. */
157 int local_time_benefit
, local_size_cost
;
158 /* Time benefit and size cost that specializing the function for this value
159 can bring about in it's callees (transitively). */
160 int prop_time_benefit
, prop_size_cost
;
163 /* Describes one particular value stored in struct ipcp_lattice. */
165 template <typename valtype
>
166 class ipcp_value
: public ipcp_value_base
169 /* The actual value for the given parameter. */
171 /* The list of sources from which this value originates. */
172 ipcp_value_source
<valtype
> *sources
;
173 /* Next pointers in a linked list of all values in a lattice. */
175 /* Next pointers in a linked list of values in a strongly connected component
177 ipcp_value
*scc_next
;
178 /* Next pointers in a linked list of SCCs of values sorted topologically
179 according their sources. */
180 ipcp_value
*topo_next
;
181 /* A specialized node created for this value, NULL if none has been (so far)
183 cgraph_node
*spec_node
;
184 /* Depth first search number and low link for topological sorting of
187 /* True if this valye is currently on the topo-sort stack. */
190 void add_source (cgraph_edge
*cs
, ipcp_value
*src_val
, int src_idx
,
191 HOST_WIDE_INT offset
);
194 /* Lattice describing potential values of a formal parameter of a function, or
195 a part of an aggreagate. TOP is represented by a lattice with zero values
196 and with contains_variable and bottom flags cleared. BOTTOM is represented
197 by a lattice with the bottom flag set. In that case, values and
198 contains_variable flag should be disregarded. */
200 template <typename valtype
>
204 /* The list of known values and types in this lattice. Note that values are
205 not deallocated if a lattice is set to bottom because there may be value
206 sources referencing them. */
207 ipcp_value
<valtype
> *values
;
208 /* Number of known values and types in this lattice. */
210 /* The lattice contains a variable component (in addition to values). */
211 bool contains_variable
;
212 /* The value of the lattice is bottom (i.e. variable and unusable for any
216 inline bool is_single_const ();
217 inline bool set_to_bottom ();
218 inline bool set_contains_variable ();
219 bool add_value (valtype newval
, cgraph_edge
*cs
,
220 ipcp_value
<valtype
> *src_val
= NULL
,
221 int src_idx
= 0, HOST_WIDE_INT offset
= -1);
222 void print (FILE * f
, bool dump_sources
, bool dump_benefits
);
225 /* Lattice of tree values with an offset to describe a part of an
228 class ipcp_agg_lattice
: public ipcp_lattice
<tree
>
231 /* Offset that is being described by this lattice. */
232 HOST_WIDE_INT offset
;
233 /* Size so that we don't have to re-compute it every time we traverse the
234 list. Must correspond to TYPE_SIZE of all lat values. */
236 /* Next element of the linked list. */
237 struct ipcp_agg_lattice
*next
;
240 /* Lattice of pointer alignment. Unlike the previous types of lattices, this
241 one is only capable of holding one value. */
243 class ipcp_alignment_lattice
246 /* If bottom and top are both false, these two fields hold values as given by
247 ptr_info_def and get_pointer_alignment_1. */
251 inline bool bottom_p () const;
252 inline bool top_p () const;
253 inline bool set_to_bottom ();
254 bool meet_with (unsigned new_align
, unsigned new_misalign
);
255 bool meet_with (const ipcp_alignment_lattice
&other
, HOST_WIDE_INT offset
);
256 void print (FILE * f
);
258 /* If set, this lattice is bottom and all other fields should be
261 /* If bottom and not_top are false, the lattice is TOP. If not_top is true,
262 the known alignment is stored in the fields align and misalign. The field
263 is negated so that memset to zero initializes the lattice to TOP
267 bool meet_with_1 (unsigned new_align
, unsigned new_misalign
);
270 /* Lattice of known bits, only capable of holding one value.
271 Bitwise constant propagation propagates which bits of a
287 In the above case, the param 'x' will always have all
288 the bits (except the bits in lsb) set to 0.
289 Hence the mask of 'x' would be 0xff. The mask
290 reflects that the bits in lsb are unknown.
291 The actual propagated value is given by m_value & ~m_mask. */
293 class ipcp_bits_lattice
296 bool bottom_p () { return m_lattice_val
== IPA_BITS_VARYING
; }
297 bool top_p () { return m_lattice_val
== IPA_BITS_UNDEFINED
; }
298 bool constant_p () { return m_lattice_val
== IPA_BITS_CONSTANT
; }
299 bool set_to_bottom ();
300 bool set_to_constant (widest_int
, widest_int
);
302 widest_int
get_value () { return m_value
; }
303 widest_int
get_mask () { return m_mask
; }
305 bool meet_with (ipcp_bits_lattice
& other
, unsigned, signop
,
306 enum tree_code
, tree
);
308 bool meet_with (widest_int
, widest_int
, unsigned);
313 enum { IPA_BITS_UNDEFINED
, IPA_BITS_CONSTANT
, IPA_BITS_VARYING
} m_lattice_val
;
315 /* Similar to ccp_lattice_t, mask represents which bits of value are constant.
316 If a bit in mask is set to 0, then the corresponding bit in
317 value is known to be constant. */
318 widest_int m_value
, m_mask
;
320 bool meet_with_1 (widest_int
, widest_int
, unsigned);
321 void get_value_and_mask (tree
, widest_int
*, widest_int
*);
324 /* Structure containing lattices for a parameter itself and for pieces of
325 aggregates that are passed in the parameter or by a reference in a parameter
326 plus some other useful flags. */
328 class ipcp_param_lattices
331 /* Lattice describing the value of the parameter itself. */
332 ipcp_lattice
<tree
> itself
;
333 /* Lattice describing the polymorphic contexts of a parameter. */
334 ipcp_lattice
<ipa_polymorphic_call_context
> ctxlat
;
335 /* Lattices describing aggregate parts. */
336 ipcp_agg_lattice
*aggs
;
337 /* Lattice describing known alignment. */
338 ipcp_alignment_lattice alignment
;
339 /* Lattice describing known bits. */
340 ipcp_bits_lattice bits_lattice
;
341 /* Number of aggregate lattices */
343 /* True if aggregate data were passed by reference (as opposed to by
346 /* All aggregate lattices contain a variable component (in addition to
348 bool aggs_contain_variable
;
349 /* The value of all aggregate lattices is bottom (i.e. variable and unusable
350 for any propagation). */
353 /* There is a virtual call based on this parameter. */
357 /* Allocation pools for values and their sources in ipa-cp. */
359 object_allocator
<ipcp_value
<tree
> > ipcp_cst_values_pool
360 ("IPA-CP constant values");
362 object_allocator
<ipcp_value
<ipa_polymorphic_call_context
> >
363 ipcp_poly_ctx_values_pool ("IPA-CP polymorphic contexts");
365 object_allocator
<ipcp_value_source
<tree
> > ipcp_sources_pool
366 ("IPA-CP value sources");
368 object_allocator
<ipcp_agg_lattice
> ipcp_agg_lattice_pool
369 ("IPA_CP aggregate lattices");
371 /* Maximal count found in program. */
373 static gcov_type max_count
;
375 /* Original overall size of the program. */
377 static long overall_size
, max_new_size
;
379 /* Return the param lattices structure corresponding to the Ith formal
380 parameter of the function described by INFO. */
381 static inline struct ipcp_param_lattices
*
382 ipa_get_parm_lattices (struct ipa_node_params
*info
, int i
)
384 gcc_assert (i
>= 0 && i
< ipa_get_param_count (info
));
385 gcc_checking_assert (!info
->ipcp_orig_node
);
386 gcc_checking_assert (info
->lattices
);
387 return &(info
->lattices
[i
]);
390 /* Return the lattice corresponding to the scalar value of the Ith formal
391 parameter of the function described by INFO. */
392 static inline ipcp_lattice
<tree
> *
393 ipa_get_scalar_lat (struct ipa_node_params
*info
, int i
)
395 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
396 return &plats
->itself
;
399 /* Return the lattice corresponding to the scalar value of the Ith formal
400 parameter of the function described by INFO. */
401 static inline ipcp_lattice
<ipa_polymorphic_call_context
> *
402 ipa_get_poly_ctx_lat (struct ipa_node_params
*info
, int i
)
404 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
405 return &plats
->ctxlat
;
408 /* Return whether LAT is a lattice with a single constant and without an
411 template <typename valtype
>
413 ipcp_lattice
<valtype
>::is_single_const ()
415 if (bottom
|| contains_variable
|| values_count
!= 1)
421 /* Print V which is extracted from a value in a lattice to F. */
424 print_ipcp_constant_value (FILE * f
, tree v
)
426 if (TREE_CODE (v
) == ADDR_EXPR
427 && TREE_CODE (TREE_OPERAND (v
, 0)) == CONST_DECL
)
430 print_generic_expr (f
, DECL_INITIAL (TREE_OPERAND (v
, 0)), 0);
433 print_generic_expr (f
, v
, 0);
436 /* Print V which is extracted from a value in a lattice to F. */
439 print_ipcp_constant_value (FILE * f
, ipa_polymorphic_call_context v
)
444 /* Print a lattice LAT to F. */
446 template <typename valtype
>
448 ipcp_lattice
<valtype
>::print (FILE * f
, bool dump_sources
, bool dump_benefits
)
450 ipcp_value
<valtype
> *val
;
455 fprintf (f
, "BOTTOM\n");
459 if (!values_count
&& !contains_variable
)
461 fprintf (f
, "TOP\n");
465 if (contains_variable
)
467 fprintf (f
, "VARIABLE");
473 for (val
= values
; val
; val
= val
->next
)
475 if (dump_benefits
&& prev
)
477 else if (!dump_benefits
&& prev
)
482 print_ipcp_constant_value (f
, val
->value
);
486 ipcp_value_source
<valtype
> *s
;
488 fprintf (f
, " [from:");
489 for (s
= val
->sources
; s
; s
= s
->next
)
490 fprintf (f
, " %i(%i)", s
->cs
->caller
->order
,
496 fprintf (f
, " [loc_time: %i, loc_size: %i, "
497 "prop_time: %i, prop_size: %i]\n",
498 val
->local_time_benefit
, val
->local_size_cost
,
499 val
->prop_time_benefit
, val
->prop_size_cost
);
505 /* Print alignment lattice to F. */
508 ipcp_alignment_lattice::print (FILE * f
)
511 fprintf (f
, " Alignment unknown (TOP)\n");
512 else if (bottom_p ())
513 fprintf (f
, " Alignment unusable (BOTTOM)\n");
515 fprintf (f
, " Alignment %u, misalignment %u\n", align
, misalign
);
519 ipcp_bits_lattice::print (FILE *f
)
522 fprintf (f
, " Bits unknown (TOP)\n");
523 else if (bottom_p ())
524 fprintf (f
, " Bits unusable (BOTTOM)\n");
527 fprintf (f
, " Bits: value = "); print_hex (get_value (), f
);
528 fprintf (f
, ", mask = "); print_hex (get_mask (), f
);
533 /* Print all ipcp_lattices of all functions to F. */
536 print_all_lattices (FILE * f
, bool dump_sources
, bool dump_benefits
)
538 struct cgraph_node
*node
;
541 fprintf (f
, "\nLattices:\n");
542 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
544 struct ipa_node_params
*info
;
546 info
= IPA_NODE_REF (node
);
547 fprintf (f
, " Node: %s/%i:\n", node
->name (),
549 count
= ipa_get_param_count (info
);
550 for (i
= 0; i
< count
; i
++)
552 struct ipcp_agg_lattice
*aglat
;
553 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
554 fprintf (f
, " param [%d]: ", i
);
555 plats
->itself
.print (f
, dump_sources
, dump_benefits
);
556 fprintf (f
, " ctxs: ");
557 plats
->ctxlat
.print (f
, dump_sources
, dump_benefits
);
558 plats
->alignment
.print (f
);
559 plats
->bits_lattice
.print (f
);
560 if (plats
->virt_call
)
561 fprintf (f
, " virt_call flag set\n");
563 if (plats
->aggs_bottom
)
565 fprintf (f
, " AGGS BOTTOM\n");
568 if (plats
->aggs_contain_variable
)
569 fprintf (f
, " AGGS VARIABLE\n");
570 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
572 fprintf (f
, " %soffset " HOST_WIDE_INT_PRINT_DEC
": ",
573 plats
->aggs_by_ref
? "ref " : "", aglat
->offset
);
574 aglat
->print (f
, dump_sources
, dump_benefits
);
580 /* Determine whether it is at all technically possible to create clones of NODE
581 and store this information in the ipa_node_params structure associated
585 determine_versionability (struct cgraph_node
*node
,
586 struct ipa_node_params
*info
)
588 const char *reason
= NULL
;
590 /* There are a number of generic reasons functions cannot be versioned. We
591 also cannot remove parameters if there are type attributes such as fnspec
593 if (node
->alias
|| node
->thunk
.thunk_p
)
594 reason
= "alias or thunk";
595 else if (!node
->local
.versionable
)
596 reason
= "not a tree_versionable_function";
597 else if (node
->get_availability () <= AVAIL_INTERPOSABLE
)
598 reason
= "insufficient body availability";
599 else if (!opt_for_fn (node
->decl
, optimize
)
600 || !opt_for_fn (node
->decl
, flag_ipa_cp
))
601 reason
= "non-optimized function";
602 else if (lookup_attribute ("omp declare simd", DECL_ATTRIBUTES (node
->decl
)))
604 /* Ideally we should clone the SIMD clones themselves and create
605 vector copies of them, so IPA-cp and SIMD clones can happily
606 coexist, but that may not be worth the effort. */
607 reason
= "function has SIMD clones";
609 else if (lookup_attribute ("target_clones", DECL_ATTRIBUTES (node
->decl
)))
611 /* Ideally we should clone the target clones themselves and create
612 copies of them, so IPA-cp and target clones can happily
613 coexist, but that may not be worth the effort. */
614 reason
= "function target_clones attribute";
616 /* Don't clone decls local to a comdat group; it breaks and for C++
617 decloned constructors, inlining is always better anyway. */
618 else if (node
->comdat_local_p ())
619 reason
= "comdat-local function";
621 if (reason
&& dump_file
&& !node
->alias
&& !node
->thunk
.thunk_p
)
622 fprintf (dump_file
, "Function %s/%i is not versionable, reason: %s.\n",
623 node
->name (), node
->order
, reason
);
625 info
->versionable
= (reason
== NULL
);
628 /* Return true if it is at all technically possible to create clones of a
632 ipcp_versionable_function_p (struct cgraph_node
*node
)
634 return IPA_NODE_REF (node
)->versionable
;
637 /* Structure holding accumulated information about callers of a node. */
639 struct caller_statistics
642 int n_calls
, n_hot_calls
, freq_sum
;
645 /* Initialize fields of STAT to zeroes. */
648 init_caller_stats (struct caller_statistics
*stats
)
650 stats
->count_sum
= 0;
652 stats
->n_hot_calls
= 0;
656 /* Worker callback of cgraph_for_node_and_aliases accumulating statistics of
657 non-thunk incoming edges to NODE. */
660 gather_caller_stats (struct cgraph_node
*node
, void *data
)
662 struct caller_statistics
*stats
= (struct caller_statistics
*) data
;
663 struct cgraph_edge
*cs
;
665 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
666 if (!cs
->caller
->thunk
.thunk_p
)
668 stats
->count_sum
+= cs
->count
;
669 stats
->freq_sum
+= cs
->frequency
;
671 if (cs
->maybe_hot_p ())
672 stats
->n_hot_calls
++;
678 /* Return true if this NODE is viable candidate for cloning. */
681 ipcp_cloning_candidate_p (struct cgraph_node
*node
)
683 struct caller_statistics stats
;
685 gcc_checking_assert (node
->has_gimple_body_p ());
687 if (!opt_for_fn (node
->decl
, flag_ipa_cp_clone
))
690 fprintf (dump_file
, "Not considering %s for cloning; "
691 "-fipa-cp-clone disabled.\n",
696 if (node
->optimize_for_size_p ())
699 fprintf (dump_file
, "Not considering %s for cloning; "
700 "optimizing it for size.\n",
705 init_caller_stats (&stats
);
706 node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
, false);
708 if (inline_summaries
->get (node
)->self_size
< stats
.n_calls
)
711 fprintf (dump_file
, "Considering %s for cloning; code might shrink.\n",
716 /* When profile is available and function is hot, propagate into it even if
717 calls seems cold; constant propagation can improve function's speed
721 if (stats
.count_sum
> node
->count
* 90 / 100)
724 fprintf (dump_file
, "Considering %s for cloning; "
725 "usually called directly.\n",
730 if (!stats
.n_hot_calls
)
733 fprintf (dump_file
, "Not considering %s for cloning; no hot calls.\n",
738 fprintf (dump_file
, "Considering %s for cloning.\n",
743 template <typename valtype
>
744 class value_topo_info
747 /* Head of the linked list of topologically sorted values. */
748 ipcp_value
<valtype
> *values_topo
;
749 /* Stack for creating SCCs, represented by a linked list too. */
750 ipcp_value
<valtype
> *stack
;
751 /* Counter driving the algorithm in add_val_to_toposort. */
754 value_topo_info () : values_topo (NULL
), stack (NULL
), dfs_counter (0)
756 void add_val (ipcp_value
<valtype
> *cur_val
);
757 void propagate_effects ();
760 /* Arrays representing a topological ordering of call graph nodes and a stack
761 of nodes used during constant propagation and also data required to perform
762 topological sort of values and propagation of benefits in the determined
768 /* Array with obtained topological order of cgraph nodes. */
769 struct cgraph_node
**order
;
770 /* Stack of cgraph nodes used during propagation within SCC until all values
771 in the SCC stabilize. */
772 struct cgraph_node
**stack
;
773 int nnodes
, stack_top
;
775 value_topo_info
<tree
> constants
;
776 value_topo_info
<ipa_polymorphic_call_context
> contexts
;
778 ipa_topo_info () : order(NULL
), stack(NULL
), nnodes(0), stack_top(0),
783 /* Allocate the arrays in TOPO and topologically sort the nodes into order. */
786 build_toporder_info (struct ipa_topo_info
*topo
)
788 topo
->order
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
789 topo
->stack
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
791 gcc_checking_assert (topo
->stack_top
== 0);
792 topo
->nnodes
= ipa_reduced_postorder (topo
->order
, true, true, NULL
);
795 /* Free information about strongly connected components and the arrays in
799 free_toporder_info (struct ipa_topo_info
*topo
)
801 ipa_free_postorder_info ();
806 /* Add NODE to the stack in TOPO, unless it is already there. */
809 push_node_to_stack (struct ipa_topo_info
*topo
, struct cgraph_node
*node
)
811 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
812 if (info
->node_enqueued
)
814 info
->node_enqueued
= 1;
815 topo
->stack
[topo
->stack_top
++] = node
;
818 /* Pop a node from the stack in TOPO and return it or return NULL if the stack
821 static struct cgraph_node
*
822 pop_node_from_stack (struct ipa_topo_info
*topo
)
826 struct cgraph_node
*node
;
828 node
= topo
->stack
[topo
->stack_top
];
829 IPA_NODE_REF (node
)->node_enqueued
= 0;
836 /* Set lattice LAT to bottom and return true if it previously was not set as
839 template <typename valtype
>
841 ipcp_lattice
<valtype
>::set_to_bottom ()
848 /* Mark lattice as containing an unknown value and return true if it previously
849 was not marked as such. */
851 template <typename valtype
>
853 ipcp_lattice
<valtype
>::set_contains_variable ()
855 bool ret
= !contains_variable
;
856 contains_variable
= true;
860 /* Set all aggegate lattices in PLATS to bottom and return true if they were
861 not previously set as such. */
864 set_agg_lats_to_bottom (struct ipcp_param_lattices
*plats
)
866 bool ret
= !plats
->aggs_bottom
;
867 plats
->aggs_bottom
= true;
871 /* Mark all aggegate lattices in PLATS as containing an unknown value and
872 return true if they were not previously marked as such. */
875 set_agg_lats_contain_variable (struct ipcp_param_lattices
*plats
)
877 bool ret
= !plats
->aggs_contain_variable
;
878 plats
->aggs_contain_variable
= true;
882 /* Return true if alignment information in the lattice is yet unknown. */
885 ipcp_alignment_lattice::top_p () const
887 return !bottom
&& !not_top
;
890 /* Return true if alignment information in the lattice is known to be
894 ipcp_alignment_lattice::bottom_p () const
899 /* Set alignment information in the lattice to bottom. Return true if it
900 previously was in a different state. */
903 ipcp_alignment_lattice::set_to_bottom ()
911 /* Meet the current value of the lattice with alignment described by NEW_ALIGN
912 and NEW_MISALIGN, assuming that we know the current value is neither TOP nor
913 BOTTOM. Return true if the value of lattice has changed. */
916 ipcp_alignment_lattice::meet_with_1 (unsigned new_align
, unsigned new_misalign
)
918 gcc_checking_assert (new_align
!= 0);
919 if (align
== new_align
&& misalign
== new_misalign
)
922 bool changed
= false;
923 if (align
> new_align
)
926 misalign
= misalign
% new_align
;
929 if (misalign
!= (new_misalign
% align
))
931 int diff
= abs ((int) misalign
- (int) (new_misalign
% align
));
932 align
= (unsigned) diff
& -diff
;
934 misalign
= misalign
% align
;
939 gcc_checking_assert (bottom_p () || align
!= 0);
943 /* Meet the current value of the lattice with alignment described by NEW_ALIGN
944 and NEW_MISALIGN. Return true if the value of lattice has changed. */
947 ipcp_alignment_lattice::meet_with (unsigned new_align
, unsigned new_misalign
)
949 gcc_assert (new_align
!= 0);
956 misalign
= new_misalign
;
959 return meet_with_1 (new_align
, new_misalign
);
962 /* Meet the current value of the lattice with OTHER, taking into account that
963 OFFSET has been added to the pointer value. Return true if the value of
964 lattice has changed. */
967 ipcp_alignment_lattice::meet_with (const ipcp_alignment_lattice
&other
,
968 HOST_WIDE_INT offset
)
970 if (other
.bottom_p ())
971 return set_to_bottom ();
972 if (bottom_p () || other
.top_p ())
975 unsigned adjusted_misalign
= (other
.misalign
+ offset
) % other
.align
;
980 misalign
= adjusted_misalign
;
984 return meet_with_1 (other
.align
, adjusted_misalign
);
987 /* Set lattice value to bottom, if it already isn't the case. */
990 ipcp_bits_lattice::set_to_bottom ()
994 m_lattice_val
= IPA_BITS_VARYING
;
1000 /* Set to constant if it isn't already. Only meant to be called
1001 when switching state from TOP. */
1004 ipcp_bits_lattice::set_to_constant (widest_int value
, widest_int mask
)
1006 gcc_assert (top_p ());
1007 m_lattice_val
= IPA_BITS_CONSTANT
;
1013 /* Convert operand to value, mask form. */
1016 ipcp_bits_lattice::get_value_and_mask (tree operand
, widest_int
*valuep
, widest_int
*maskp
)
1018 wide_int
get_nonzero_bits (const_tree
);
1020 if (TREE_CODE (operand
) == INTEGER_CST
)
1022 *valuep
= wi::to_widest (operand
);
1032 /* Meet operation, similar to ccp_lattice_meet, we xor values
1033 if this->value, value have different values at same bit positions, we want
1034 to drop that bit to varying. Return true if mask is changed.
1035 This function assumes that the lattice value is in CONSTANT state */
1038 ipcp_bits_lattice::meet_with_1 (widest_int value
, widest_int mask
,
1041 gcc_assert (constant_p ());
1043 widest_int old_mask
= m_mask
;
1044 m_mask
= (m_mask
| mask
) | (m_value
^ value
);
1046 if (wi::sext (m_mask
, precision
) == -1)
1047 return set_to_bottom ();
1049 return m_mask
!= old_mask
;
1052 /* Meet the bits lattice with operand
1053 described by <value, mask, sgn, precision. */
1056 ipcp_bits_lattice::meet_with (widest_int value
, widest_int mask
,
1064 if (wi::sext (mask
, precision
) == -1)
1065 return set_to_bottom ();
1066 return set_to_constant (value
, mask
);
1069 return meet_with_1 (value
, mask
, precision
);
1072 /* Meet bits lattice with the result of bit_value_binop (other, operand)
1073 if code is binary operation or bit_value_unop (other) if code is unary op.
1074 In the case when code is nop_expr, no adjustment is required. */
1077 ipcp_bits_lattice::meet_with (ipcp_bits_lattice
& other
, unsigned precision
,
1078 signop sgn
, enum tree_code code
, tree operand
)
1080 if (other
.bottom_p ())
1081 return set_to_bottom ();
1083 if (bottom_p () || other
.top_p ())
1086 widest_int adjusted_value
, adjusted_mask
;
1088 if (TREE_CODE_CLASS (code
) == tcc_binary
)
1090 tree type
= TREE_TYPE (operand
);
1091 gcc_assert (INTEGRAL_TYPE_P (type
));
1092 widest_int o_value
, o_mask
;
1093 get_value_and_mask (operand
, &o_value
, &o_mask
);
1095 bit_value_binop (code
, sgn
, precision
, &adjusted_value
, &adjusted_mask
,
1096 sgn
, precision
, other
.get_value (), other
.get_mask (),
1097 TYPE_SIGN (type
), TYPE_PRECISION (type
), o_value
, o_mask
);
1099 if (wi::sext (adjusted_mask
, precision
) == -1)
1100 return set_to_bottom ();
1103 else if (TREE_CODE_CLASS (code
) == tcc_unary
)
1105 bit_value_unop (code
, sgn
, precision
, &adjusted_value
,
1106 &adjusted_mask
, sgn
, precision
, other
.get_value (),
1109 if (wi::sext (adjusted_mask
, precision
) == -1)
1110 return set_to_bottom ();
1113 else if (code
== NOP_EXPR
)
1115 adjusted_value
= other
.m_value
;
1116 adjusted_mask
= other
.m_mask
;
1120 return set_to_bottom ();
1124 if (wi::sext (adjusted_mask
, precision
) == -1)
1125 return set_to_bottom ();
1126 return set_to_constant (adjusted_value
, adjusted_mask
);
1129 return meet_with_1 (adjusted_value
, adjusted_mask
, precision
);
1132 /* Mark bot aggregate and scalar lattices as containing an unknown variable,
1133 return true is any of them has not been marked as such so far. */
1136 set_all_contains_variable (struct ipcp_param_lattices
*plats
)
1139 ret
= plats
->itself
.set_contains_variable ();
1140 ret
|= plats
->ctxlat
.set_contains_variable ();
1141 ret
|= set_agg_lats_contain_variable (plats
);
1142 ret
|= plats
->alignment
.set_to_bottom ();
1143 ret
|= plats
->bits_lattice
.set_to_bottom ();
1147 /* Worker of call_for_symbol_thunks_and_aliases, increment the integer DATA
1148 points to by the number of callers to NODE. */
1151 count_callers (cgraph_node
*node
, void *data
)
1153 int *caller_count
= (int *) data
;
1155 for (cgraph_edge
*cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
1156 /* Local thunks can be handled transparently, but if the thunk can not
1157 be optimized out, count it as a real use. */
1158 if (!cs
->caller
->thunk
.thunk_p
|| !cs
->caller
->local
.local
)
1163 /* Worker of call_for_symbol_thunks_and_aliases, it is supposed to be called on
1164 the one caller of some other node. Set the caller's corresponding flag. */
1167 set_single_call_flag (cgraph_node
*node
, void *)
1169 cgraph_edge
*cs
= node
->callers
;
1170 /* Local thunks can be handled transparently, skip them. */
1171 while (cs
&& cs
->caller
->thunk
.thunk_p
&& cs
->caller
->local
.local
)
1172 cs
= cs
->next_caller
;
1175 IPA_NODE_REF (cs
->caller
)->node_calling_single_call
= true;
1181 /* Initialize ipcp_lattices. */
1184 initialize_node_lattices (struct cgraph_node
*node
)
1186 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1187 struct cgraph_edge
*ie
;
1188 bool disable
= false, variable
= false;
1191 gcc_checking_assert (node
->has_gimple_body_p ());
1192 if (cgraph_local_p (node
))
1194 int caller_count
= 0;
1195 node
->call_for_symbol_thunks_and_aliases (count_callers
, &caller_count
,
1197 gcc_checking_assert (caller_count
> 0);
1198 if (caller_count
== 1)
1199 node
->call_for_symbol_thunks_and_aliases (set_single_call_flag
,
1204 /* When cloning is allowed, we can assume that externally visible
1205 functions are not called. We will compensate this by cloning
1207 if (ipcp_versionable_function_p (node
)
1208 && ipcp_cloning_candidate_p (node
))
1214 if (disable
|| variable
)
1216 for (i
= 0; i
< ipa_get_param_count (info
) ; i
++)
1218 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1221 plats
->itself
.set_to_bottom ();
1222 plats
->ctxlat
.set_to_bottom ();
1223 set_agg_lats_to_bottom (plats
);
1224 plats
->alignment
.set_to_bottom ();
1225 plats
->bits_lattice
.set_to_bottom ();
1228 set_all_contains_variable (plats
);
1230 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1231 && !node
->alias
&& !node
->thunk
.thunk_p
)
1232 fprintf (dump_file
, "Marking all lattices of %s/%i as %s\n",
1233 node
->name (), node
->order
,
1234 disable
? "BOTTOM" : "VARIABLE");
1237 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
1238 if (ie
->indirect_info
->polymorphic
1239 && ie
->indirect_info
->param_index
>= 0)
1241 gcc_checking_assert (ie
->indirect_info
->param_index
>= 0);
1242 ipa_get_parm_lattices (info
,
1243 ie
->indirect_info
->param_index
)->virt_call
= 1;
1247 /* Return the result of a (possibly arithmetic) pass through jump function
1248 JFUNC on the constant value INPUT. Return NULL_TREE if that cannot be
1249 determined or be considered an interprocedural invariant. */
1252 ipa_get_jf_pass_through_result (struct ipa_jump_func
*jfunc
, tree input
)
1256 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
1258 if (!is_gimple_ip_invariant (input
))
1261 if (TREE_CODE_CLASS (ipa_get_jf_pass_through_operation (jfunc
))
1263 restype
= boolean_type_node
;
1265 restype
= TREE_TYPE (input
);
1266 res
= fold_binary (ipa_get_jf_pass_through_operation (jfunc
), restype
,
1267 input
, ipa_get_jf_pass_through_operand (jfunc
));
1269 if (res
&& !is_gimple_ip_invariant (res
))
1275 /* Return the result of an ancestor jump function JFUNC on the constant value
1276 INPUT. Return NULL_TREE if that cannot be determined. */
1279 ipa_get_jf_ancestor_result (struct ipa_jump_func
*jfunc
, tree input
)
1281 gcc_checking_assert (TREE_CODE (input
) != TREE_BINFO
);
1282 if (TREE_CODE (input
) == ADDR_EXPR
)
1284 tree t
= TREE_OPERAND (input
, 0);
1285 t
= build_ref_for_offset (EXPR_LOCATION (t
), t
,
1286 ipa_get_jf_ancestor_offset (jfunc
), false,
1287 ptr_type_node
, NULL
, false);
1288 return build_fold_addr_expr (t
);
1294 /* Determine whether JFUNC evaluates to a single known constant value and if
1295 so, return it. Otherwise return NULL. INFO describes the caller node or
1296 the one it is inlined to, so that pass-through jump functions can be
1300 ipa_value_from_jfunc (struct ipa_node_params
*info
, struct ipa_jump_func
*jfunc
)
1302 if (jfunc
->type
== IPA_JF_CONST
)
1303 return ipa_get_jf_constant (jfunc
);
1304 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1305 || jfunc
->type
== IPA_JF_ANCESTOR
)
1310 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1311 idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1313 idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1315 if (info
->ipcp_orig_node
)
1316 input
= info
->known_csts
[idx
];
1319 ipcp_lattice
<tree
> *lat
;
1322 || idx
>= ipa_get_param_count (info
))
1324 lat
= ipa_get_scalar_lat (info
, idx
);
1325 if (!lat
->is_single_const ())
1327 input
= lat
->values
->value
;
1333 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1334 return ipa_get_jf_pass_through_result (jfunc
, input
);
1336 return ipa_get_jf_ancestor_result (jfunc
, input
);
1342 /* Determie whether JFUNC evaluates to single known polymorphic context, given
1343 that INFO describes the caller node or the one it is inlined to, CS is the
1344 call graph edge corresponding to JFUNC and CSIDX index of the described
1347 ipa_polymorphic_call_context
1348 ipa_context_from_jfunc (ipa_node_params
*info
, cgraph_edge
*cs
, int csidx
,
1349 ipa_jump_func
*jfunc
)
1351 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
1352 ipa_polymorphic_call_context ctx
;
1353 ipa_polymorphic_call_context
*edge_ctx
1354 = cs
? ipa_get_ith_polymorhic_call_context (args
, csidx
) : NULL
;
1356 if (edge_ctx
&& !edge_ctx
->useless_p ())
1359 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1360 || jfunc
->type
== IPA_JF_ANCESTOR
)
1362 ipa_polymorphic_call_context srcctx
;
1364 bool type_preserved
= true;
1365 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1367 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1369 type_preserved
= ipa_get_jf_pass_through_type_preserved (jfunc
);
1370 srcidx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1374 type_preserved
= ipa_get_jf_ancestor_type_preserved (jfunc
);
1375 srcidx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1377 if (info
->ipcp_orig_node
)
1379 if (info
->known_contexts
.exists ())
1380 srcctx
= info
->known_contexts
[srcidx
];
1385 || srcidx
>= ipa_get_param_count (info
))
1387 ipcp_lattice
<ipa_polymorphic_call_context
> *lat
;
1388 lat
= ipa_get_poly_ctx_lat (info
, srcidx
);
1389 if (!lat
->is_single_const ())
1391 srcctx
= lat
->values
->value
;
1393 if (srcctx
.useless_p ())
1395 if (jfunc
->type
== IPA_JF_ANCESTOR
)
1396 srcctx
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
1397 if (!type_preserved
)
1398 srcctx
.possible_dynamic_type_change (cs
->in_polymorphic_cdtor
);
1399 srcctx
.combine_with (ctx
);
1406 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
1407 bottom, not containing a variable component and without any known value at
1411 ipcp_verify_propagated_values (void)
1413 struct cgraph_node
*node
;
1415 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
1417 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1418 int i
, count
= ipa_get_param_count (info
);
1420 for (i
= 0; i
< count
; i
++)
1422 ipcp_lattice
<tree
> *lat
= ipa_get_scalar_lat (info
, i
);
1425 && !lat
->contains_variable
1426 && lat
->values_count
== 0)
1430 symtab_node::dump_table (dump_file
);
1431 fprintf (dump_file
, "\nIPA lattices after constant "
1432 "propagation, before gcc_unreachable:\n");
1433 print_all_lattices (dump_file
, true, false);
1442 /* Return true iff X and Y should be considered equal values by IPA-CP. */
1445 values_equal_for_ipcp_p (tree x
, tree y
)
1447 gcc_checking_assert (x
!= NULL_TREE
&& y
!= NULL_TREE
);
1452 if (TREE_CODE (x
) == ADDR_EXPR
1453 && TREE_CODE (y
) == ADDR_EXPR
1454 && TREE_CODE (TREE_OPERAND (x
, 0)) == CONST_DECL
1455 && TREE_CODE (TREE_OPERAND (y
, 0)) == CONST_DECL
)
1456 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x
, 0)),
1457 DECL_INITIAL (TREE_OPERAND (y
, 0)), 0);
1459 return operand_equal_p (x
, y
, 0);
1462 /* Return true iff X and Y should be considered equal contexts by IPA-CP. */
1465 values_equal_for_ipcp_p (ipa_polymorphic_call_context x
,
1466 ipa_polymorphic_call_context y
)
1468 return x
.equal_to (y
);
1472 /* Add a new value source to the value represented by THIS, marking that a
1473 value comes from edge CS and (if the underlying jump function is a
1474 pass-through or an ancestor one) from a caller value SRC_VAL of a caller
1475 parameter described by SRC_INDEX. OFFSET is negative if the source was the
1476 scalar value of the parameter itself or the offset within an aggregate. */
1478 template <typename valtype
>
1480 ipcp_value
<valtype
>::add_source (cgraph_edge
*cs
, ipcp_value
*src_val
,
1481 int src_idx
, HOST_WIDE_INT offset
)
1483 ipcp_value_source
<valtype
> *src
;
1485 src
= new (ipcp_sources_pool
.allocate ()) ipcp_value_source
<valtype
>;
1486 src
->offset
= offset
;
1489 src
->index
= src_idx
;
1491 src
->next
= sources
;
1495 /* Allocate a new ipcp_value holding a tree constant, initialize its value to
1496 SOURCE and clear all other fields. */
1498 static ipcp_value
<tree
> *
1499 allocate_and_init_ipcp_value (tree source
)
1501 ipcp_value
<tree
> *val
;
1503 val
= ipcp_cst_values_pool
.allocate ();
1504 memset (val
, 0, sizeof (*val
));
1505 val
->value
= source
;
1509 /* Allocate a new ipcp_value holding a polymorphic context, initialize its
1510 value to SOURCE and clear all other fields. */
1512 static ipcp_value
<ipa_polymorphic_call_context
> *
1513 allocate_and_init_ipcp_value (ipa_polymorphic_call_context source
)
1515 ipcp_value
<ipa_polymorphic_call_context
> *val
;
1518 val
= ipcp_poly_ctx_values_pool
.allocate ();
1519 memset (val
, 0, sizeof (*val
));
1520 val
->value
= source
;
1524 /* Try to add NEWVAL to LAT, potentially creating a new ipcp_value for it. CS,
1525 SRC_VAL SRC_INDEX and OFFSET are meant for add_source and have the same
1526 meaning. OFFSET -1 means the source is scalar and not a part of an
1529 template <typename valtype
>
1531 ipcp_lattice
<valtype
>::add_value (valtype newval
, cgraph_edge
*cs
,
1532 ipcp_value
<valtype
> *src_val
,
1533 int src_idx
, HOST_WIDE_INT offset
)
1535 ipcp_value
<valtype
> *val
;
1540 for (val
= values
; val
; val
= val
->next
)
1541 if (values_equal_for_ipcp_p (val
->value
, newval
))
1543 if (ipa_edge_within_scc (cs
))
1545 ipcp_value_source
<valtype
> *s
;
1546 for (s
= val
->sources
; s
; s
= s
->next
)
1553 val
->add_source (cs
, src_val
, src_idx
, offset
);
1557 if (values_count
== PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE
))
1559 /* We can only free sources, not the values themselves, because sources
1560 of other values in this SCC might point to them. */
1561 for (val
= values
; val
; val
= val
->next
)
1563 while (val
->sources
)
1565 ipcp_value_source
<valtype
> *src
= val
->sources
;
1566 val
->sources
= src
->next
;
1567 ipcp_sources_pool
.remove ((ipcp_value_source
<tree
>*)src
);
1572 return set_to_bottom ();
1576 val
= allocate_and_init_ipcp_value (newval
);
1577 val
->add_source (cs
, src_val
, src_idx
, offset
);
1583 /* Propagate values through a pass-through jump function JFUNC associated with
1584 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1585 is the index of the source parameter. */
1588 propagate_vals_accross_pass_through (cgraph_edge
*cs
,
1589 ipa_jump_func
*jfunc
,
1590 ipcp_lattice
<tree
> *src_lat
,
1591 ipcp_lattice
<tree
> *dest_lat
,
1594 ipcp_value
<tree
> *src_val
;
1597 /* Do not create new values when propagating within an SCC because if there
1598 are arithmetic functions with circular dependencies, there is infinite
1599 number of them and we would just make lattices bottom. */
1600 if ((ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1601 && ipa_edge_within_scc (cs
))
1602 ret
= dest_lat
->set_contains_variable ();
1604 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1606 tree cstval
= ipa_get_jf_pass_through_result (jfunc
, src_val
->value
);
1609 ret
|= dest_lat
->add_value (cstval
, cs
, src_val
, src_idx
);
1611 ret
|= dest_lat
->set_contains_variable ();
1617 /* Propagate values through an ancestor jump function JFUNC associated with
1618 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1619 is the index of the source parameter. */
1622 propagate_vals_accross_ancestor (struct cgraph_edge
*cs
,
1623 struct ipa_jump_func
*jfunc
,
1624 ipcp_lattice
<tree
> *src_lat
,
1625 ipcp_lattice
<tree
> *dest_lat
,
1628 ipcp_value
<tree
> *src_val
;
1631 if (ipa_edge_within_scc (cs
))
1632 return dest_lat
->set_contains_variable ();
1634 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1636 tree t
= ipa_get_jf_ancestor_result (jfunc
, src_val
->value
);
1639 ret
|= dest_lat
->add_value (t
, cs
, src_val
, src_idx
);
1641 ret
|= dest_lat
->set_contains_variable ();
1647 /* Propagate scalar values across jump function JFUNC that is associated with
1648 edge CS and put the values into DEST_LAT. */
1651 propagate_scalar_accross_jump_function (struct cgraph_edge
*cs
,
1652 struct ipa_jump_func
*jfunc
,
1653 ipcp_lattice
<tree
> *dest_lat
)
1655 if (dest_lat
->bottom
)
1658 if (jfunc
->type
== IPA_JF_CONST
)
1660 tree val
= ipa_get_jf_constant (jfunc
);
1661 return dest_lat
->add_value (val
, cs
, NULL
, 0);
1663 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1664 || jfunc
->type
== IPA_JF_ANCESTOR
)
1666 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1667 ipcp_lattice
<tree
> *src_lat
;
1671 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1672 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1674 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1676 src_lat
= ipa_get_scalar_lat (caller_info
, src_idx
);
1677 if (src_lat
->bottom
)
1678 return dest_lat
->set_contains_variable ();
1680 /* If we would need to clone the caller and cannot, do not propagate. */
1681 if (!ipcp_versionable_function_p (cs
->caller
)
1682 && (src_lat
->contains_variable
1683 || (src_lat
->values_count
> 1)))
1684 return dest_lat
->set_contains_variable ();
1686 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1687 ret
= propagate_vals_accross_pass_through (cs
, jfunc
, src_lat
,
1690 ret
= propagate_vals_accross_ancestor (cs
, jfunc
, src_lat
, dest_lat
,
1693 if (src_lat
->contains_variable
)
1694 ret
|= dest_lat
->set_contains_variable ();
1699 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1700 use it for indirect inlining), we should propagate them too. */
1701 return dest_lat
->set_contains_variable ();
1704 /* Propagate scalar values across jump function JFUNC that is associated with
1705 edge CS and describes argument IDX and put the values into DEST_LAT. */
1708 propagate_context_accross_jump_function (cgraph_edge
*cs
,
1709 ipa_jump_func
*jfunc
, int idx
,
1710 ipcp_lattice
<ipa_polymorphic_call_context
> *dest_lat
)
1712 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
1713 if (dest_lat
->bottom
)
1716 bool added_sth
= false;
1717 bool type_preserved
= true;
1719 ipa_polymorphic_call_context edge_ctx
, *edge_ctx_ptr
1720 = ipa_get_ith_polymorhic_call_context (args
, idx
);
1723 edge_ctx
= *edge_ctx_ptr
;
1725 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1726 || jfunc
->type
== IPA_JF_ANCESTOR
)
1728 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1730 ipcp_lattice
<ipa_polymorphic_call_context
> *src_lat
;
1732 /* TODO: Once we figure out how to propagate speculations, it will
1733 probably be a good idea to switch to speculation if type_preserved is
1734 not set instead of punting. */
1735 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1737 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1739 type_preserved
= ipa_get_jf_pass_through_type_preserved (jfunc
);
1740 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1744 type_preserved
= ipa_get_jf_ancestor_type_preserved (jfunc
);
1745 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1748 src_lat
= ipa_get_poly_ctx_lat (caller_info
, src_idx
);
1749 /* If we would need to clone the caller and cannot, do not propagate. */
1750 if (!ipcp_versionable_function_p (cs
->caller
)
1751 && (src_lat
->contains_variable
1752 || (src_lat
->values_count
> 1)))
1755 ipcp_value
<ipa_polymorphic_call_context
> *src_val
;
1756 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1758 ipa_polymorphic_call_context cur
= src_val
->value
;
1760 if (!type_preserved
)
1761 cur
.possible_dynamic_type_change (cs
->in_polymorphic_cdtor
);
1762 if (jfunc
->type
== IPA_JF_ANCESTOR
)
1763 cur
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
1764 /* TODO: In cases we know how the context is going to be used,
1765 we can improve the result by passing proper OTR_TYPE. */
1766 cur
.combine_with (edge_ctx
);
1767 if (!cur
.useless_p ())
1769 if (src_lat
->contains_variable
1770 && !edge_ctx
.equal_to (cur
))
1771 ret
|= dest_lat
->set_contains_variable ();
1772 ret
|= dest_lat
->add_value (cur
, cs
, src_val
, src_idx
);
1782 if (!edge_ctx
.useless_p ())
1783 ret
|= dest_lat
->add_value (edge_ctx
, cs
);
1785 ret
|= dest_lat
->set_contains_variable ();
1791 /* Propagate alignments across jump function JFUNC that is associated with
1792 edge CS and update DEST_LAT accordingly. */
1795 propagate_alignment_accross_jump_function (cgraph_edge
*cs
,
1796 ipa_jump_func
*jfunc
,
1797 ipcp_alignment_lattice
*dest_lat
)
1799 if (dest_lat
->bottom_p ())
1802 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1803 || jfunc
->type
== IPA_JF_ANCESTOR
)
1805 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1806 HOST_WIDE_INT offset
= 0;
1809 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1811 enum tree_code op
= ipa_get_jf_pass_through_operation (jfunc
);
1814 if (op
!= POINTER_PLUS_EXPR
1816 return dest_lat
->set_to_bottom ();
1817 tree operand
= ipa_get_jf_pass_through_operand (jfunc
);
1818 if (!tree_fits_shwi_p (operand
))
1819 return dest_lat
->set_to_bottom ();
1820 offset
= tree_to_shwi (operand
);
1822 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1826 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1827 offset
= ipa_get_jf_ancestor_offset (jfunc
) / BITS_PER_UNIT
;
1830 struct ipcp_param_lattices
*src_lats
;
1831 src_lats
= ipa_get_parm_lattices (caller_info
, src_idx
);
1832 return dest_lat
->meet_with (src_lats
->alignment
, offset
);
1836 if (jfunc
->alignment
.known
)
1837 return dest_lat
->meet_with (jfunc
->alignment
.align
,
1838 jfunc
->alignment
.misalign
);
1840 return dest_lat
->set_to_bottom ();
1844 /* Propagate bits across jfunc that is associated with
1845 edge cs and update dest_lattice accordingly. */
1848 propagate_bits_accross_jump_function (cgraph_edge
*cs
, int idx
, ipa_jump_func
*jfunc
,
1849 ipcp_bits_lattice
*dest_lattice
)
1851 if (dest_lattice
->bottom_p ())
1854 enum availability availability
;
1855 cgraph_node
*callee
= cs
->callee
->function_symbol (&availability
);
1856 struct ipa_node_params
*callee_info
= IPA_NODE_REF (callee
);
1857 tree parm_type
= ipa_get_type (callee_info
, idx
);
1859 /* For K&R C programs, ipa_get_type() could return NULL_TREE.
1860 Avoid the transform for these cases. */
1863 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1864 fprintf (dump_file
, "Setting dest_lattice to bottom, because"
1865 "param %i type is NULL for %s\n", idx
,
1866 cs
->callee
->name ());
1868 return dest_lattice
->set_to_bottom ();
1871 unsigned precision
= TYPE_PRECISION (parm_type
);
1872 signop sgn
= TYPE_SIGN (parm_type
);
1874 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1876 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1877 enum tree_code code
= ipa_get_jf_pass_through_operation (jfunc
);
1878 tree operand
= NULL_TREE
;
1880 if (code
!= NOP_EXPR
)
1881 operand
= ipa_get_jf_pass_through_operand (jfunc
);
1883 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1884 struct ipcp_param_lattices
*src_lats
1885 = ipa_get_parm_lattices (caller_info
, src_idx
);
1887 /* Try to propagate bits if src_lattice is bottom, but jfunc is known.
1893 Assume lattice for x is bottom, however we can still propagate
1894 result of x & 0xff == 0xff, which gets computed during ccp1 pass
1895 and we store it in jump function during analysis stage. */
1897 if (src_lats
->bits_lattice
.bottom_p ()
1898 && jfunc
->bits
.known
)
1899 return dest_lattice
->meet_with (jfunc
->bits
.value
, jfunc
->bits
.mask
,
1902 return dest_lattice
->meet_with (src_lats
->bits_lattice
, precision
, sgn
,
1906 else if (jfunc
->type
== IPA_JF_ANCESTOR
)
1907 return dest_lattice
->set_to_bottom ();
1909 else if (jfunc
->bits
.known
)
1910 return dest_lattice
->meet_with (jfunc
->bits
.value
, jfunc
->bits
.mask
, precision
);
1913 return dest_lattice
->set_to_bottom ();
1916 /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
1917 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
1918 other cases, return false). If there are no aggregate items, set
1919 aggs_by_ref to NEW_AGGS_BY_REF. */
1922 set_check_aggs_by_ref (struct ipcp_param_lattices
*dest_plats
,
1923 bool new_aggs_by_ref
)
1925 if (dest_plats
->aggs
)
1927 if (dest_plats
->aggs_by_ref
!= new_aggs_by_ref
)
1929 set_agg_lats_to_bottom (dest_plats
);
1934 dest_plats
->aggs_by_ref
= new_aggs_by_ref
;
1938 /* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
1939 already existing lattice for the given OFFSET and SIZE, marking all skipped
1940 lattices as containing variable and checking for overlaps. If there is no
1941 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
1942 it with offset, size and contains_variable to PRE_EXISTING, and return true,
1943 unless there are too many already. If there are two many, return false. If
1944 there are overlaps turn whole DEST_PLATS to bottom and return false. If any
1945 skipped lattices were newly marked as containing variable, set *CHANGE to
1949 merge_agg_lats_step (struct ipcp_param_lattices
*dest_plats
,
1950 HOST_WIDE_INT offset
, HOST_WIDE_INT val_size
,
1951 struct ipcp_agg_lattice
***aglat
,
1952 bool pre_existing
, bool *change
)
1954 gcc_checking_assert (offset
>= 0);
1956 while (**aglat
&& (**aglat
)->offset
< offset
)
1958 if ((**aglat
)->offset
+ (**aglat
)->size
> offset
)
1960 set_agg_lats_to_bottom (dest_plats
);
1963 *change
|= (**aglat
)->set_contains_variable ();
1964 *aglat
= &(**aglat
)->next
;
1967 if (**aglat
&& (**aglat
)->offset
== offset
)
1969 if ((**aglat
)->size
!= val_size
1971 && (**aglat
)->next
->offset
< offset
+ val_size
))
1973 set_agg_lats_to_bottom (dest_plats
);
1976 gcc_checking_assert (!(**aglat
)->next
1977 || (**aglat
)->next
->offset
>= offset
+ val_size
);
1982 struct ipcp_agg_lattice
*new_al
;
1984 if (**aglat
&& (**aglat
)->offset
< offset
+ val_size
)
1986 set_agg_lats_to_bottom (dest_plats
);
1989 if (dest_plats
->aggs_count
== PARAM_VALUE (PARAM_IPA_MAX_AGG_ITEMS
))
1991 dest_plats
->aggs_count
++;
1992 new_al
= ipcp_agg_lattice_pool
.allocate ();
1993 memset (new_al
, 0, sizeof (*new_al
));
1995 new_al
->offset
= offset
;
1996 new_al
->size
= val_size
;
1997 new_al
->contains_variable
= pre_existing
;
1999 new_al
->next
= **aglat
;
2005 /* Set all AGLAT and all other aggregate lattices reachable by next pointers as
2006 containing an unknown value. */
2009 set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice
*aglat
)
2014 ret
|= aglat
->set_contains_variable ();
2015 aglat
= aglat
->next
;
2020 /* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
2021 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source
2022 parameter used for lattice value sources. Return true if DEST_PLATS changed
2026 merge_aggregate_lattices (struct cgraph_edge
*cs
,
2027 struct ipcp_param_lattices
*dest_plats
,
2028 struct ipcp_param_lattices
*src_plats
,
2029 int src_idx
, HOST_WIDE_INT offset_delta
)
2031 bool pre_existing
= dest_plats
->aggs
!= NULL
;
2032 struct ipcp_agg_lattice
**dst_aglat
;
2035 if (set_check_aggs_by_ref (dest_plats
, src_plats
->aggs_by_ref
))
2037 if (src_plats
->aggs_bottom
)
2038 return set_agg_lats_contain_variable (dest_plats
);
2039 if (src_plats
->aggs_contain_variable
)
2040 ret
|= set_agg_lats_contain_variable (dest_plats
);
2041 dst_aglat
= &dest_plats
->aggs
;
2043 for (struct ipcp_agg_lattice
*src_aglat
= src_plats
->aggs
;
2045 src_aglat
= src_aglat
->next
)
2047 HOST_WIDE_INT new_offset
= src_aglat
->offset
- offset_delta
;
2051 if (merge_agg_lats_step (dest_plats
, new_offset
, src_aglat
->size
,
2052 &dst_aglat
, pre_existing
, &ret
))
2054 struct ipcp_agg_lattice
*new_al
= *dst_aglat
;
2056 dst_aglat
= &(*dst_aglat
)->next
;
2057 if (src_aglat
->bottom
)
2059 ret
|= new_al
->set_contains_variable ();
2062 if (src_aglat
->contains_variable
)
2063 ret
|= new_al
->set_contains_variable ();
2064 for (ipcp_value
<tree
> *val
= src_aglat
->values
;
2067 ret
|= new_al
->add_value (val
->value
, cs
, val
, src_idx
,
2070 else if (dest_plats
->aggs_bottom
)
2073 ret
|= set_chain_of_aglats_contains_variable (*dst_aglat
);
2077 /* Determine whether there is anything to propagate FROM SRC_PLATS through a
2078 pass-through JFUNC and if so, whether it has conform and conforms to the
2079 rules about propagating values passed by reference. */
2082 agg_pass_through_permissible_p (struct ipcp_param_lattices
*src_plats
,
2083 struct ipa_jump_func
*jfunc
)
2085 return src_plats
->aggs
2086 && (!src_plats
->aggs_by_ref
2087 || ipa_get_jf_pass_through_agg_preserved (jfunc
));
2090 /* Propagate scalar values across jump function JFUNC that is associated with
2091 edge CS and put the values into DEST_LAT. */
2094 propagate_aggs_accross_jump_function (struct cgraph_edge
*cs
,
2095 struct ipa_jump_func
*jfunc
,
2096 struct ipcp_param_lattices
*dest_plats
)
2100 if (dest_plats
->aggs_bottom
)
2103 if (jfunc
->type
== IPA_JF_PASS_THROUGH
2104 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
2106 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2107 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
2108 struct ipcp_param_lattices
*src_plats
;
2110 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2111 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
2113 /* Currently we do not produce clobber aggregate jump
2114 functions, replace with merging when we do. */
2115 gcc_assert (!jfunc
->agg
.items
);
2116 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
,
2120 ret
|= set_agg_lats_contain_variable (dest_plats
);
2122 else if (jfunc
->type
== IPA_JF_ANCESTOR
2123 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
2125 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2126 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
2127 struct ipcp_param_lattices
*src_plats
;
2129 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2130 if (src_plats
->aggs
&& src_plats
->aggs_by_ref
)
2132 /* Currently we do not produce clobber aggregate jump
2133 functions, replace with merging when we do. */
2134 gcc_assert (!jfunc
->agg
.items
);
2135 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
, src_idx
,
2136 ipa_get_jf_ancestor_offset (jfunc
));
2138 else if (!src_plats
->aggs_by_ref
)
2139 ret
|= set_agg_lats_to_bottom (dest_plats
);
2141 ret
|= set_agg_lats_contain_variable (dest_plats
);
2143 else if (jfunc
->agg
.items
)
2145 bool pre_existing
= dest_plats
->aggs
!= NULL
;
2146 struct ipcp_agg_lattice
**aglat
= &dest_plats
->aggs
;
2147 struct ipa_agg_jf_item
*item
;
2150 if (set_check_aggs_by_ref (dest_plats
, jfunc
->agg
.by_ref
))
2153 FOR_EACH_VEC_ELT (*jfunc
->agg
.items
, i
, item
)
2155 HOST_WIDE_INT val_size
;
2157 if (item
->offset
< 0)
2159 gcc_checking_assert (is_gimple_ip_invariant (item
->value
));
2160 val_size
= tree_to_uhwi (TYPE_SIZE (TREE_TYPE (item
->value
)));
2162 if (merge_agg_lats_step (dest_plats
, item
->offset
, val_size
,
2163 &aglat
, pre_existing
, &ret
))
2165 ret
|= (*aglat
)->add_value (item
->value
, cs
, NULL
, 0, 0);
2166 aglat
= &(*aglat
)->next
;
2168 else if (dest_plats
->aggs_bottom
)
2172 ret
|= set_chain_of_aglats_contains_variable (*aglat
);
2175 ret
|= set_agg_lats_contain_variable (dest_plats
);
2180 /* Return true if on the way cfrom CS->caller to the final (non-alias and
2181 non-thunk) destination, the call passes through a thunk. */
2184 call_passes_through_thunk_p (cgraph_edge
*cs
)
2186 cgraph_node
*alias_or_thunk
= cs
->callee
;
2187 while (alias_or_thunk
->alias
)
2188 alias_or_thunk
= alias_or_thunk
->get_alias_target ();
2189 return alias_or_thunk
->thunk
.thunk_p
;
2192 /* Propagate constants from the caller to the callee of CS. INFO describes the
2196 propagate_constants_accross_call (struct cgraph_edge
*cs
)
2198 struct ipa_node_params
*callee_info
;
2199 enum availability availability
;
2200 cgraph_node
*callee
;
2201 struct ipa_edge_args
*args
;
2203 int i
, args_count
, parms_count
;
2205 callee
= cs
->callee
->function_symbol (&availability
);
2206 if (!callee
->definition
)
2208 gcc_checking_assert (callee
->has_gimple_body_p ());
2209 callee_info
= IPA_NODE_REF (callee
);
2211 args
= IPA_EDGE_REF (cs
);
2212 args_count
= ipa_get_cs_argument_count (args
);
2213 parms_count
= ipa_get_param_count (callee_info
);
2214 if (parms_count
== 0)
2217 /* No propagation through instrumentation thunks is available yet.
2218 It should be possible with proper mapping of call args and
2219 instrumented callee params in the propagation loop below. But
2220 this case mostly occurs when legacy code calls instrumented code
2221 and it is not a primary target for optimizations.
2222 We detect instrumentation thunks in aliases and thunks chain by
2223 checking instrumentation_clone flag for chain source and target.
2224 Going through instrumentation thunks we always have it changed
2225 from 0 to 1 and all other nodes do not change it. */
2226 if (!cs
->callee
->instrumentation_clone
2227 && callee
->instrumentation_clone
)
2229 for (i
= 0; i
< parms_count
; i
++)
2230 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
2235 /* If this call goes through a thunk we must not propagate to the first (0th)
2236 parameter. However, we might need to uncover a thunk from below a series
2237 of aliases first. */
2238 if (call_passes_through_thunk_p (cs
))
2240 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
2247 for (; (i
< args_count
) && (i
< parms_count
); i
++)
2249 struct ipa_jump_func
*jump_func
= ipa_get_ith_jump_func (args
, i
);
2250 struct ipcp_param_lattices
*dest_plats
;
2252 dest_plats
= ipa_get_parm_lattices (callee_info
, i
);
2253 if (availability
== AVAIL_INTERPOSABLE
)
2254 ret
|= set_all_contains_variable (dest_plats
);
2257 ret
|= propagate_scalar_accross_jump_function (cs
, jump_func
,
2258 &dest_plats
->itself
);
2259 ret
|= propagate_context_accross_jump_function (cs
, jump_func
, i
,
2260 &dest_plats
->ctxlat
);
2261 ret
|= propagate_alignment_accross_jump_function (cs
, jump_func
,
2262 &dest_plats
->alignment
);
2263 ret
|= propagate_bits_accross_jump_function (cs
, i
, jump_func
,
2264 &dest_plats
->bits_lattice
);
2265 ret
|= propagate_aggs_accross_jump_function (cs
, jump_func
,
2269 for (; i
< parms_count
; i
++)
2270 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
, i
));
2275 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
2276 KNOWN_CONTEXTS, KNOWN_AGGS or AGG_REPS return the destination. The latter
2277 three can be NULL. If AGG_REPS is not NULL, KNOWN_AGGS is ignored. */
2280 ipa_get_indirect_edge_target_1 (struct cgraph_edge
*ie
,
2281 vec
<tree
> known_csts
,
2282 vec
<ipa_polymorphic_call_context
> known_contexts
,
2283 vec
<ipa_agg_jump_function_p
> known_aggs
,
2284 struct ipa_agg_replacement_value
*agg_reps
,
2287 int param_index
= ie
->indirect_info
->param_index
;
2288 HOST_WIDE_INT anc_offset
;
2292 *speculative
= false;
2294 if (param_index
== -1
2295 || known_csts
.length () <= (unsigned int) param_index
)
2298 if (!ie
->indirect_info
->polymorphic
)
2302 if (ie
->indirect_info
->agg_contents
)
2305 if (agg_reps
&& ie
->indirect_info
->guaranteed_unmodified
)
2309 if (agg_reps
->index
== param_index
2310 && agg_reps
->offset
== ie
->indirect_info
->offset
2311 && agg_reps
->by_ref
== ie
->indirect_info
->by_ref
)
2313 t
= agg_reps
->value
;
2316 agg_reps
= agg_reps
->next
;
2321 struct ipa_agg_jump_function
*agg
;
2322 if (known_aggs
.length () > (unsigned int) param_index
)
2323 agg
= known_aggs
[param_index
];
2326 bool from_global_constant
;
2327 t
= ipa_find_agg_cst_for_param (agg
, known_csts
[param_index
],
2328 ie
->indirect_info
->offset
,
2329 ie
->indirect_info
->by_ref
,
2330 &from_global_constant
);
2332 && !from_global_constant
2333 && !ie
->indirect_info
->guaranteed_unmodified
)
2338 t
= known_csts
[param_index
];
2341 TREE_CODE (t
) == ADDR_EXPR
2342 && TREE_CODE (TREE_OPERAND (t
, 0)) == FUNCTION_DECL
)
2343 return TREE_OPERAND (t
, 0);
2348 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize
))
2351 gcc_assert (!ie
->indirect_info
->agg_contents
);
2352 anc_offset
= ie
->indirect_info
->offset
;
2356 /* Try to work out value of virtual table pointer value in replacemnets. */
2357 if (!t
&& agg_reps
&& !ie
->indirect_info
->by_ref
)
2361 if (agg_reps
->index
== param_index
2362 && agg_reps
->offset
== ie
->indirect_info
->offset
2363 && agg_reps
->by_ref
)
2365 t
= agg_reps
->value
;
2368 agg_reps
= agg_reps
->next
;
2372 /* Try to work out value of virtual table pointer value in known
2373 aggregate values. */
2374 if (!t
&& known_aggs
.length () > (unsigned int) param_index
2375 && !ie
->indirect_info
->by_ref
)
2377 struct ipa_agg_jump_function
*agg
;
2378 agg
= known_aggs
[param_index
];
2379 t
= ipa_find_agg_cst_for_param (agg
, known_csts
[param_index
],
2380 ie
->indirect_info
->offset
,
2384 /* If we found the virtual table pointer, lookup the target. */
2388 unsigned HOST_WIDE_INT offset
;
2389 if (vtable_pointer_value_to_vtable (t
, &vtable
, &offset
))
2392 target
= gimple_get_virt_method_for_vtable (ie
->indirect_info
->otr_token
,
2393 vtable
, offset
, &can_refer
);
2397 || (TREE_CODE (TREE_TYPE (target
)) == FUNCTION_TYPE
2398 && DECL_FUNCTION_CODE (target
) == BUILT_IN_UNREACHABLE
)
2399 || !possible_polymorphic_call_target_p
2400 (ie
, cgraph_node::get (target
)))
2402 /* Do not speculate builtin_unreachable, it is stupid! */
2403 if (ie
->indirect_info
->vptr_changed
)
2405 target
= ipa_impossible_devirt_target (ie
, target
);
2407 *speculative
= ie
->indirect_info
->vptr_changed
;
2414 /* Do we know the constant value of pointer? */
2416 t
= known_csts
[param_index
];
2418 gcc_checking_assert (!t
|| TREE_CODE (t
) != TREE_BINFO
);
2420 ipa_polymorphic_call_context context
;
2421 if (known_contexts
.length () > (unsigned int) param_index
)
2423 context
= known_contexts
[param_index
];
2424 context
.offset_by (anc_offset
);
2425 if (ie
->indirect_info
->vptr_changed
)
2426 context
.possible_dynamic_type_change (ie
->in_polymorphic_cdtor
,
2427 ie
->indirect_info
->otr_type
);
2430 ipa_polymorphic_call_context ctx2
= ipa_polymorphic_call_context
2431 (t
, ie
->indirect_info
->otr_type
, anc_offset
);
2432 if (!ctx2
.useless_p ())
2433 context
.combine_with (ctx2
, ie
->indirect_info
->otr_type
);
2438 context
= ipa_polymorphic_call_context (t
, ie
->indirect_info
->otr_type
,
2440 if (ie
->indirect_info
->vptr_changed
)
2441 context
.possible_dynamic_type_change (ie
->in_polymorphic_cdtor
,
2442 ie
->indirect_info
->otr_type
);
2447 vec
<cgraph_node
*>targets
;
2450 targets
= possible_polymorphic_call_targets
2451 (ie
->indirect_info
->otr_type
,
2452 ie
->indirect_info
->otr_token
,
2454 if (!final
|| targets
.length () > 1)
2456 struct cgraph_node
*node
;
2459 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize_speculatively
)
2460 || ie
->speculative
|| !ie
->maybe_hot_p ())
2462 node
= try_speculative_devirtualization (ie
->indirect_info
->otr_type
,
2463 ie
->indirect_info
->otr_token
,
2467 *speculative
= true;
2468 target
= node
->decl
;
2475 *speculative
= false;
2476 if (targets
.length () == 1)
2477 target
= targets
[0]->decl
;
2479 target
= ipa_impossible_devirt_target (ie
, NULL_TREE
);
2482 if (target
&& !possible_polymorphic_call_target_p (ie
,
2483 cgraph_node::get (target
)))
2487 target
= ipa_impossible_devirt_target (ie
, target
);
2494 /* If an indirect edge IE can be turned into a direct one based on KNOWN_CSTS,
2495 KNOWN_CONTEXTS (which can be vNULL) or KNOWN_AGGS (which also can be vNULL)
2496 return the destination. */
2499 ipa_get_indirect_edge_target (struct cgraph_edge
*ie
,
2500 vec
<tree
> known_csts
,
2501 vec
<ipa_polymorphic_call_context
> known_contexts
,
2502 vec
<ipa_agg_jump_function_p
> known_aggs
,
2505 return ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
2506 known_aggs
, NULL
, speculative
);
2509 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
2510 and KNOWN_CONTEXTS. */
2513 devirtualization_time_bonus (struct cgraph_node
*node
,
2514 vec
<tree
> known_csts
,
2515 vec
<ipa_polymorphic_call_context
> known_contexts
,
2516 vec
<ipa_agg_jump_function_p
> known_aggs
)
2518 struct cgraph_edge
*ie
;
2521 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
2523 struct cgraph_node
*callee
;
2524 struct inline_summary
*isummary
;
2525 enum availability avail
;
2529 target
= ipa_get_indirect_edge_target (ie
, known_csts
, known_contexts
,
2530 known_aggs
, &speculative
);
2534 /* Only bare minimum benefit for clearly un-inlineable targets. */
2536 callee
= cgraph_node::get (target
);
2537 if (!callee
|| !callee
->definition
)
2539 callee
= callee
->function_symbol (&avail
);
2540 if (avail
< AVAIL_AVAILABLE
)
2542 isummary
= inline_summaries
->get (callee
);
2543 if (!isummary
->inlinable
)
2546 /* FIXME: The values below need re-considering and perhaps also
2547 integrating into the cost metrics, at lest in some very basic way. */
2548 if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 4)
2549 res
+= 31 / ((int)speculative
+ 1);
2550 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 2)
2551 res
+= 15 / ((int)speculative
+ 1);
2552 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
2553 || DECL_DECLARED_INLINE_P (callee
->decl
))
2554 res
+= 7 / ((int)speculative
+ 1);
2560 /* Return time bonus incurred because of HINTS. */
2563 hint_time_bonus (inline_hints hints
)
2566 if (hints
& (INLINE_HINT_loop_iterations
| INLINE_HINT_loop_stride
))
2567 result
+= PARAM_VALUE (PARAM_IPA_CP_LOOP_HINT_BONUS
);
2568 if (hints
& INLINE_HINT_array_index
)
2569 result
+= PARAM_VALUE (PARAM_IPA_CP_ARRAY_INDEX_HINT_BONUS
);
2573 /* If there is a reason to penalize the function described by INFO in the
2574 cloning goodness evaluation, do so. */
2576 static inline int64_t
2577 incorporate_penalties (ipa_node_params
*info
, int64_t evaluation
)
2579 if (info
->node_within_scc
)
2580 evaluation
= (evaluation
2581 * (100 - PARAM_VALUE (PARAM_IPA_CP_RECURSION_PENALTY
))) / 100;
2583 if (info
->node_calling_single_call
)
2584 evaluation
= (evaluation
2585 * (100 - PARAM_VALUE (PARAM_IPA_CP_SINGLE_CALL_PENALTY
)))
2591 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
2592 and SIZE_COST and with the sum of frequencies of incoming edges to the
2593 potential new clone in FREQUENCIES. */
2596 good_cloning_opportunity_p (struct cgraph_node
*node
, int time_benefit
,
2597 int freq_sum
, gcov_type count_sum
, int size_cost
)
2599 if (time_benefit
== 0
2600 || !opt_for_fn (node
->decl
, flag_ipa_cp_clone
)
2601 || node
->optimize_for_size_p ())
2604 gcc_assert (size_cost
> 0);
2606 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2609 int factor
= (count_sum
* 1000) / max_count
;
2610 int64_t evaluation
= (((int64_t) time_benefit
* factor
)
2612 evaluation
= incorporate_penalties (info
, evaluation
);
2614 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2615 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
2616 "size: %i, count_sum: " HOST_WIDE_INT_PRINT_DEC
2617 "%s%s) -> evaluation: " "%" PRId64
2618 ", threshold: %i\n",
2619 time_benefit
, size_cost
, (HOST_WIDE_INT
) count_sum
,
2620 info
->node_within_scc
? ", scc" : "",
2621 info
->node_calling_single_call
? ", single_call" : "",
2622 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
2624 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
2628 int64_t evaluation
= (((int64_t) time_benefit
* freq_sum
)
2630 evaluation
= incorporate_penalties (info
, evaluation
);
2632 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2633 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
2634 "size: %i, freq_sum: %i%s%s) -> evaluation: "
2635 "%" PRId64
", threshold: %i\n",
2636 time_benefit
, size_cost
, freq_sum
,
2637 info
->node_within_scc
? ", scc" : "",
2638 info
->node_calling_single_call
? ", single_call" : "",
2639 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
2641 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
2645 /* Return all context independent values from aggregate lattices in PLATS in a
2646 vector. Return NULL if there are none. */
2648 static vec
<ipa_agg_jf_item
, va_gc
> *
2649 context_independent_aggregate_values (struct ipcp_param_lattices
*plats
)
2651 vec
<ipa_agg_jf_item
, va_gc
> *res
= NULL
;
2653 if (plats
->aggs_bottom
2654 || plats
->aggs_contain_variable
2655 || plats
->aggs_count
== 0)
2658 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
;
2660 aglat
= aglat
->next
)
2661 if (aglat
->is_single_const ())
2663 struct ipa_agg_jf_item item
;
2664 item
.offset
= aglat
->offset
;
2665 item
.value
= aglat
->values
->value
;
2666 vec_safe_push (res
, item
);
2671 /* Allocate KNOWN_CSTS, KNOWN_CONTEXTS and, if non-NULL, KNOWN_AGGS and
2672 populate them with values of parameters that are known independent of the
2673 context. INFO describes the function. If REMOVABLE_PARAMS_COST is
2674 non-NULL, the movement cost of all removable parameters will be stored in
2678 gather_context_independent_values (struct ipa_node_params
*info
,
2679 vec
<tree
> *known_csts
,
2680 vec
<ipa_polymorphic_call_context
>
2682 vec
<ipa_agg_jump_function
> *known_aggs
,
2683 int *removable_params_cost
)
2685 int i
, count
= ipa_get_param_count (info
);
2688 known_csts
->create (0);
2689 known_contexts
->create (0);
2690 known_csts
->safe_grow_cleared (count
);
2691 known_contexts
->safe_grow_cleared (count
);
2694 known_aggs
->create (0);
2695 known_aggs
->safe_grow_cleared (count
);
2698 if (removable_params_cost
)
2699 *removable_params_cost
= 0;
2701 for (i
= 0; i
< count
; i
++)
2703 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2704 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
2706 if (lat
->is_single_const ())
2708 ipcp_value
<tree
> *val
= lat
->values
;
2709 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
2710 (*known_csts
)[i
] = val
->value
;
2711 if (removable_params_cost
)
2712 *removable_params_cost
2713 += estimate_move_cost (TREE_TYPE (val
->value
), false);
2716 else if (removable_params_cost
2717 && !ipa_is_param_used (info
, i
))
2718 *removable_params_cost
2719 += ipa_get_param_move_cost (info
, i
);
2721 if (!ipa_is_param_used (info
, i
))
2724 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
2725 /* Do not account known context as reason for cloning. We can see
2726 if it permits devirtualization. */
2727 if (ctxlat
->is_single_const ())
2728 (*known_contexts
)[i
] = ctxlat
->values
->value
;
2732 vec
<ipa_agg_jf_item
, va_gc
> *agg_items
;
2733 struct ipa_agg_jump_function
*ajf
;
2735 agg_items
= context_independent_aggregate_values (plats
);
2736 ajf
= &(*known_aggs
)[i
];
2737 ajf
->items
= agg_items
;
2738 ajf
->by_ref
= plats
->aggs_by_ref
;
2739 ret
|= agg_items
!= NULL
;
2746 /* The current interface in ipa-inline-analysis requires a pointer vector.
2749 FIXME: That interface should be re-worked, this is slightly silly. Still,
2750 I'd like to discuss how to change it first and this demonstrates the
2753 static vec
<ipa_agg_jump_function_p
>
2754 agg_jmp_p_vec_for_t_vec (vec
<ipa_agg_jump_function
> known_aggs
)
2756 vec
<ipa_agg_jump_function_p
> ret
;
2757 struct ipa_agg_jump_function
*ajf
;
2760 ret
.create (known_aggs
.length ());
2761 FOR_EACH_VEC_ELT (known_aggs
, i
, ajf
)
2762 ret
.quick_push (ajf
);
2766 /* Perform time and size measurement of NODE with the context given in
2767 KNOWN_CSTS, KNOWN_CONTEXTS and KNOWN_AGGS, calculate the benefit and cost
2768 given BASE_TIME of the node without specialization, REMOVABLE_PARAMS_COST of
2769 all context-independent removable parameters and EST_MOVE_COST of estimated
2770 movement of the considered parameter and store it into VAL. */
2773 perform_estimation_of_a_value (cgraph_node
*node
, vec
<tree
> known_csts
,
2774 vec
<ipa_polymorphic_call_context
> known_contexts
,
2775 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
,
2776 int base_time
, int removable_params_cost
,
2777 int est_move_cost
, ipcp_value_base
*val
)
2779 int time
, size
, time_benefit
;
2782 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
2783 known_aggs_ptrs
, &size
, &time
,
2785 time_benefit
= base_time
- time
2786 + devirtualization_time_bonus (node
, known_csts
, known_contexts
,
2788 + hint_time_bonus (hints
)
2789 + removable_params_cost
+ est_move_cost
;
2791 gcc_checking_assert (size
>=0);
2792 /* The inliner-heuristics based estimates may think that in certain
2793 contexts some functions do not have any size at all but we want
2794 all specializations to have at least a tiny cost, not least not to
2799 val
->local_time_benefit
= time_benefit
;
2800 val
->local_size_cost
= size
;
2803 /* Iterate over known values of parameters of NODE and estimate the local
2804 effects in terms of time and size they have. */
2807 estimate_local_effects (struct cgraph_node
*node
)
2809 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2810 int i
, count
= ipa_get_param_count (info
);
2811 vec
<tree
> known_csts
;
2812 vec
<ipa_polymorphic_call_context
> known_contexts
;
2813 vec
<ipa_agg_jump_function
> known_aggs
;
2814 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
;
2816 int base_time
= inline_summaries
->get (node
)->time
;
2817 int removable_params_cost
;
2819 if (!count
|| !ipcp_versionable_function_p (node
))
2822 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2823 fprintf (dump_file
, "\nEstimating effects for %s/%i, base_time: %i.\n",
2824 node
->name (), node
->order
, base_time
);
2826 always_const
= gather_context_independent_values (info
, &known_csts
,
2827 &known_contexts
, &known_aggs
,
2828 &removable_params_cost
);
2829 known_aggs_ptrs
= agg_jmp_p_vec_for_t_vec (known_aggs
);
2830 int devirt_bonus
= devirtualization_time_bonus (node
, known_csts
,
2831 known_contexts
, known_aggs_ptrs
);
2832 if (always_const
|| devirt_bonus
2833 || (removable_params_cost
&& node
->local
.can_change_signature
))
2835 struct caller_statistics stats
;
2839 init_caller_stats (&stats
);
2840 node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
2842 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
2843 known_aggs_ptrs
, &size
, &time
, &hints
);
2844 time
-= devirt_bonus
;
2845 time
-= hint_time_bonus (hints
);
2846 time
-= removable_params_cost
;
2847 size
-= stats
.n_calls
* removable_params_cost
;
2850 fprintf (dump_file
, " - context independent values, size: %i, "
2851 "time_benefit: %i\n", size
, base_time
- time
);
2853 if (size
<= 0 || node
->local
.local
)
2855 info
->do_clone_for_all_contexts
= true;
2859 fprintf (dump_file
, " Decided to specialize for all "
2860 "known contexts, code not going to grow.\n");
2862 else if (good_cloning_opportunity_p (node
, base_time
- time
,
2863 stats
.freq_sum
, stats
.count_sum
,
2866 if (size
+ overall_size
<= max_new_size
)
2868 info
->do_clone_for_all_contexts
= true;
2870 overall_size
+= size
;
2873 fprintf (dump_file
, " Decided to specialize for all "
2874 "known contexts, growth deemed beneficial.\n");
2876 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2877 fprintf (dump_file
, " Not cloning for all contexts because "
2878 "max_new_size would be reached with %li.\n",
2879 size
+ overall_size
);
2881 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2882 fprintf (dump_file
, " Not cloning for all contexts because "
2883 "!good_cloning_opportunity_p.\n");
2887 for (i
= 0; i
< count
; i
++)
2889 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2890 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
2891 ipcp_value
<tree
> *val
;
2898 for (val
= lat
->values
; val
; val
= val
->next
)
2900 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
2901 known_csts
[i
] = val
->value
;
2903 int emc
= estimate_move_cost (TREE_TYPE (val
->value
), true);
2904 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
2905 known_aggs_ptrs
, base_time
,
2906 removable_params_cost
, emc
, val
);
2908 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2910 fprintf (dump_file
, " - estimates for value ");
2911 print_ipcp_constant_value (dump_file
, val
->value
);
2912 fprintf (dump_file
, " for ");
2913 ipa_dump_param (dump_file
, info
, i
);
2914 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
2915 val
->local_time_benefit
, val
->local_size_cost
);
2918 known_csts
[i
] = NULL_TREE
;
2921 for (i
= 0; i
< count
; i
++)
2923 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2925 if (!plats
->virt_call
)
2928 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
2929 ipcp_value
<ipa_polymorphic_call_context
> *val
;
2933 || !known_contexts
[i
].useless_p ())
2936 for (val
= ctxlat
->values
; val
; val
= val
->next
)
2938 known_contexts
[i
] = val
->value
;
2939 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
2940 known_aggs_ptrs
, base_time
,
2941 removable_params_cost
, 0, val
);
2943 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2945 fprintf (dump_file
, " - estimates for polymorphic context ");
2946 print_ipcp_constant_value (dump_file
, val
->value
);
2947 fprintf (dump_file
, " for ");
2948 ipa_dump_param (dump_file
, info
, i
);
2949 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
2950 val
->local_time_benefit
, val
->local_size_cost
);
2953 known_contexts
[i
] = ipa_polymorphic_call_context ();
2956 for (i
= 0; i
< count
; i
++)
2958 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2959 struct ipa_agg_jump_function
*ajf
;
2960 struct ipcp_agg_lattice
*aglat
;
2962 if (plats
->aggs_bottom
|| !plats
->aggs
)
2965 ajf
= &known_aggs
[i
];
2966 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2968 ipcp_value
<tree
> *val
;
2969 if (aglat
->bottom
|| !aglat
->values
2970 /* If the following is true, the one value is in known_aggs. */
2971 || (!plats
->aggs_contain_variable
2972 && aglat
->is_single_const ()))
2975 for (val
= aglat
->values
; val
; val
= val
->next
)
2977 struct ipa_agg_jf_item item
;
2979 item
.offset
= aglat
->offset
;
2980 item
.value
= val
->value
;
2981 vec_safe_push (ajf
->items
, item
);
2983 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
2984 known_aggs_ptrs
, base_time
,
2985 removable_params_cost
, 0, val
);
2987 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2989 fprintf (dump_file
, " - estimates for value ");
2990 print_ipcp_constant_value (dump_file
, val
->value
);
2991 fprintf (dump_file
, " for ");
2992 ipa_dump_param (dump_file
, info
, i
);
2993 fprintf (dump_file
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
2994 "]: time_benefit: %i, size: %i\n",
2995 plats
->aggs_by_ref
? "ref " : "",
2997 val
->local_time_benefit
, val
->local_size_cost
);
3005 for (i
= 0; i
< count
; i
++)
3006 vec_free (known_aggs
[i
].items
);
3008 known_csts
.release ();
3009 known_contexts
.release ();
3010 known_aggs
.release ();
3011 known_aggs_ptrs
.release ();
3015 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
3016 topological sort of values. */
3018 template <typename valtype
>
3020 value_topo_info
<valtype
>::add_val (ipcp_value
<valtype
> *cur_val
)
3022 ipcp_value_source
<valtype
> *src
;
3028 cur_val
->dfs
= dfs_counter
;
3029 cur_val
->low_link
= dfs_counter
;
3031 cur_val
->topo_next
= stack
;
3033 cur_val
->on_stack
= true;
3035 for (src
= cur_val
->sources
; src
; src
= src
->next
)
3038 if (src
->val
->dfs
== 0)
3041 if (src
->val
->low_link
< cur_val
->low_link
)
3042 cur_val
->low_link
= src
->val
->low_link
;
3044 else if (src
->val
->on_stack
3045 && src
->val
->dfs
< cur_val
->low_link
)
3046 cur_val
->low_link
= src
->val
->dfs
;
3049 if (cur_val
->dfs
== cur_val
->low_link
)
3051 ipcp_value
<valtype
> *v
, *scc_list
= NULL
;
3056 stack
= v
->topo_next
;
3057 v
->on_stack
= false;
3059 v
->scc_next
= scc_list
;
3062 while (v
!= cur_val
);
3064 cur_val
->topo_next
= values_topo
;
3065 values_topo
= cur_val
;
3069 /* Add all values in lattices associated with NODE to the topological sort if
3070 they are not there yet. */
3073 add_all_node_vals_to_toposort (cgraph_node
*node
, ipa_topo_info
*topo
)
3075 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3076 int i
, count
= ipa_get_param_count (info
);
3078 for (i
= 0; i
< count
; i
++)
3080 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3081 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
3082 struct ipcp_agg_lattice
*aglat
;
3086 ipcp_value
<tree
> *val
;
3087 for (val
= lat
->values
; val
; val
= val
->next
)
3088 topo
->constants
.add_val (val
);
3091 if (!plats
->aggs_bottom
)
3092 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3095 ipcp_value
<tree
> *val
;
3096 for (val
= aglat
->values
; val
; val
= val
->next
)
3097 topo
->constants
.add_val (val
);
3100 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
3101 if (!ctxlat
->bottom
)
3103 ipcp_value
<ipa_polymorphic_call_context
> *ctxval
;
3104 for (ctxval
= ctxlat
->values
; ctxval
; ctxval
= ctxval
->next
)
3105 topo
->contexts
.add_val (ctxval
);
3110 /* One pass of constants propagation along the call graph edges, from callers
3111 to callees (requires topological ordering in TOPO), iterate over strongly
3112 connected components. */
3115 propagate_constants_topo (struct ipa_topo_info
*topo
)
3119 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
3122 struct cgraph_node
*v
, *node
= topo
->order
[i
];
3123 vec
<cgraph_node
*> cycle_nodes
= ipa_get_nodes_in_cycle (node
);
3125 /* First, iteratively propagate within the strongly connected component
3126 until all lattices stabilize. */
3127 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
3128 if (v
->has_gimple_body_p ())
3129 push_node_to_stack (topo
, v
);
3131 v
= pop_node_from_stack (topo
);
3134 struct cgraph_edge
*cs
;
3136 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3137 if (ipa_edge_within_scc (cs
))
3139 IPA_NODE_REF (v
)->node_within_scc
= true;
3140 if (propagate_constants_accross_call (cs
))
3141 push_node_to_stack (topo
, cs
->callee
->function_symbol ());
3143 v
= pop_node_from_stack (topo
);
3146 /* Afterwards, propagate along edges leading out of the SCC, calculates
3147 the local effects of the discovered constants and all valid values to
3148 their topological sort. */
3149 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
3150 if (v
->has_gimple_body_p ())
3152 struct cgraph_edge
*cs
;
3154 estimate_local_effects (v
);
3155 add_all_node_vals_to_toposort (v
, topo
);
3156 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3157 if (!ipa_edge_within_scc (cs
))
3158 propagate_constants_accross_call (cs
);
3160 cycle_nodes
.release ();
3165 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
3166 the bigger one if otherwise. */
3169 safe_add (int a
, int b
)
3171 if (a
> INT_MAX
/2 || b
> INT_MAX
/2)
3172 return a
> b
? a
: b
;
3178 /* Propagate the estimated effects of individual values along the topological
3179 from the dependent values to those they depend on. */
3181 template <typename valtype
>
3183 value_topo_info
<valtype
>::propagate_effects ()
3185 ipcp_value
<valtype
> *base
;
3187 for (base
= values_topo
; base
; base
= base
->topo_next
)
3189 ipcp_value_source
<valtype
> *src
;
3190 ipcp_value
<valtype
> *val
;
3191 int time
= 0, size
= 0;
3193 for (val
= base
; val
; val
= val
->scc_next
)
3195 time
= safe_add (time
,
3196 val
->local_time_benefit
+ val
->prop_time_benefit
);
3197 size
= safe_add (size
, val
->local_size_cost
+ val
->prop_size_cost
);
3200 for (val
= base
; val
; val
= val
->scc_next
)
3201 for (src
= val
->sources
; src
; src
= src
->next
)
3203 && src
->cs
->maybe_hot_p ())
3205 src
->val
->prop_time_benefit
= safe_add (time
,
3206 src
->val
->prop_time_benefit
);
3207 src
->val
->prop_size_cost
= safe_add (size
,
3208 src
->val
->prop_size_cost
);
3214 /* Propagate constants, polymorphic contexts and their effects from the
3215 summaries interprocedurally. */
3218 ipcp_propagate_stage (struct ipa_topo_info
*topo
)
3220 struct cgraph_node
*node
;
3223 fprintf (dump_file
, "\n Propagating constants:\n\n");
3226 ipa_update_after_lto_read ();
3229 FOR_EACH_DEFINED_FUNCTION (node
)
3231 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3233 /* In LTO we do not have PARM_DECLs but we would still like to be able to
3234 look at types of parameters. */
3237 tree t
= TYPE_ARG_TYPES (TREE_TYPE (node
->decl
));
3238 for (int k
= 0; k
< ipa_get_param_count (info
) && t
; k
++)
3240 gcc_assert (t
!= void_list_node
);
3241 info
->descriptors
[k
].decl_or_type
= TREE_VALUE (t
);
3242 t
= t
? TREE_CHAIN (t
) : NULL
;
3246 determine_versionability (node
, info
);
3247 if (node
->has_gimple_body_p ())
3249 info
->lattices
= XCNEWVEC (struct ipcp_param_lattices
,
3250 ipa_get_param_count (info
));
3251 initialize_node_lattices (node
);
3253 if (node
->definition
&& !node
->alias
)
3254 overall_size
+= inline_summaries
->get (node
)->self_size
;
3255 if (node
->count
> max_count
)
3256 max_count
= node
->count
;
3259 max_new_size
= overall_size
;
3260 if (max_new_size
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
3261 max_new_size
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
3262 max_new_size
+= max_new_size
* PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH
) / 100 + 1;
3265 fprintf (dump_file
, "\noverall_size: %li, max_new_size: %li\n",
3266 overall_size
, max_new_size
);
3268 propagate_constants_topo (topo
);
3270 ipcp_verify_propagated_values ();
3271 topo
->constants
.propagate_effects ();
3272 topo
->contexts
.propagate_effects ();
3276 fprintf (dump_file
, "\nIPA lattices after all propagation:\n");
3277 print_all_lattices (dump_file
, (dump_flags
& TDF_DETAILS
), true);
3281 /* Discover newly direct outgoing edges from NODE which is a new clone with
3282 known KNOWN_CSTS and make them direct. */
3285 ipcp_discover_new_direct_edges (struct cgraph_node
*node
,
3286 vec
<tree
> known_csts
,
3287 vec
<ipa_polymorphic_call_context
>
3289 struct ipa_agg_replacement_value
*aggvals
)
3291 struct cgraph_edge
*ie
, *next_ie
;
3294 for (ie
= node
->indirect_calls
; ie
; ie
= next_ie
)
3299 next_ie
= ie
->next_callee
;
3300 target
= ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
3301 vNULL
, aggvals
, &speculative
);
3304 bool agg_contents
= ie
->indirect_info
->agg_contents
;
3305 bool polymorphic
= ie
->indirect_info
->polymorphic
;
3306 int param_index
= ie
->indirect_info
->param_index
;
3307 struct cgraph_edge
*cs
= ipa_make_edge_direct_to_target (ie
, target
,
3311 if (cs
&& !agg_contents
&& !polymorphic
)
3313 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3314 int c
= ipa_get_controlled_uses (info
, param_index
);
3315 if (c
!= IPA_UNDESCRIBED_USE
)
3317 struct ipa_ref
*to_del
;
3320 ipa_set_controlled_uses (info
, param_index
, c
);
3321 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3322 fprintf (dump_file
, " controlled uses count of param "
3323 "%i bumped down to %i\n", param_index
, c
);
3325 && (to_del
= node
->find_reference (cs
->callee
, NULL
, 0)))
3327 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3328 fprintf (dump_file
, " and even removing its "
3329 "cloning-created reference\n");
3330 to_del
->remove_reference ();
3336 /* Turning calls to direct calls will improve overall summary. */
3338 inline_update_overall_summary (node
);
3341 /* Vector of pointers which for linked lists of clones of an original crgaph
3344 static vec
<cgraph_edge
*> next_edge_clone
;
3345 static vec
<cgraph_edge
*> prev_edge_clone
;
3348 grow_edge_clone_vectors (void)
3350 if (next_edge_clone
.length ()
3351 <= (unsigned) symtab
->edges_max_uid
)
3352 next_edge_clone
.safe_grow_cleared (symtab
->edges_max_uid
+ 1);
3353 if (prev_edge_clone
.length ()
3354 <= (unsigned) symtab
->edges_max_uid
)
3355 prev_edge_clone
.safe_grow_cleared (symtab
->edges_max_uid
+ 1);
3358 /* Edge duplication hook to grow the appropriate linked list in
3362 ipcp_edge_duplication_hook (struct cgraph_edge
*src
, struct cgraph_edge
*dst
,
3365 grow_edge_clone_vectors ();
3367 struct cgraph_edge
*old_next
= next_edge_clone
[src
->uid
];
3369 prev_edge_clone
[old_next
->uid
] = dst
;
3370 prev_edge_clone
[dst
->uid
] = src
;
3372 next_edge_clone
[dst
->uid
] = old_next
;
3373 next_edge_clone
[src
->uid
] = dst
;
3376 /* Hook that is called by cgraph.c when an edge is removed. */
3379 ipcp_edge_removal_hook (struct cgraph_edge
*cs
, void *)
3381 grow_edge_clone_vectors ();
3383 struct cgraph_edge
*prev
= prev_edge_clone
[cs
->uid
];
3384 struct cgraph_edge
*next
= next_edge_clone
[cs
->uid
];
3386 next_edge_clone
[prev
->uid
] = next
;
3388 prev_edge_clone
[next
->uid
] = prev
;
3391 /* See if NODE is a clone with a known aggregate value at a given OFFSET of a
3392 parameter with the given INDEX. */
3395 get_clone_agg_value (struct cgraph_node
*node
, HOST_WIDE_INT offset
,
3398 struct ipa_agg_replacement_value
*aggval
;
3400 aggval
= ipa_get_agg_replacements_for_node (node
);
3403 if (aggval
->offset
== offset
3404 && aggval
->index
== index
)
3405 return aggval
->value
;
3406 aggval
= aggval
->next
;
3411 /* Return true is NODE is DEST or its clone for all contexts. */
3414 same_node_or_its_all_contexts_clone_p (cgraph_node
*node
, cgraph_node
*dest
)
3419 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3420 return info
->is_all_contexts_clone
&& info
->ipcp_orig_node
== dest
;
3423 /* Return true if edge CS does bring about the value described by SRC to node
3424 DEST or its clone for all contexts. */
3427 cgraph_edge_brings_value_p (cgraph_edge
*cs
, ipcp_value_source
<tree
> *src
,
3430 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3431 enum availability availability
;
3432 cgraph_node
*real_dest
= cs
->callee
->function_symbol (&availability
);
3434 if (!same_node_or_its_all_contexts_clone_p (real_dest
, dest
)
3435 || availability
<= AVAIL_INTERPOSABLE
3436 || caller_info
->node_dead
)
3441 if (caller_info
->ipcp_orig_node
)
3444 if (src
->offset
== -1)
3445 t
= caller_info
->known_csts
[src
->index
];
3447 t
= get_clone_agg_value (cs
->caller
, src
->offset
, src
->index
);
3448 return (t
!= NULL_TREE
3449 && values_equal_for_ipcp_p (src
->val
->value
, t
));
3453 struct ipcp_agg_lattice
*aglat
;
3454 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
3456 if (src
->offset
== -1)
3457 return (plats
->itself
.is_single_const ()
3458 && values_equal_for_ipcp_p (src
->val
->value
,
3459 plats
->itself
.values
->value
));
3462 if (plats
->aggs_bottom
|| plats
->aggs_contain_variable
)
3464 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3465 if (aglat
->offset
== src
->offset
)
3466 return (aglat
->is_single_const ()
3467 && values_equal_for_ipcp_p (src
->val
->value
,
3468 aglat
->values
->value
));
3474 /* Return true if edge CS does bring about the value described by SRC to node
3475 DEST or its clone for all contexts. */
3478 cgraph_edge_brings_value_p (cgraph_edge
*cs
,
3479 ipcp_value_source
<ipa_polymorphic_call_context
> *src
,
3482 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3483 cgraph_node
*real_dest
= cs
->callee
->function_symbol ();
3485 if (!same_node_or_its_all_contexts_clone_p (real_dest
, dest
)
3486 || caller_info
->node_dead
)
3491 if (caller_info
->ipcp_orig_node
)
3492 return (caller_info
->known_contexts
.length () > (unsigned) src
->index
)
3493 && values_equal_for_ipcp_p (src
->val
->value
,
3494 caller_info
->known_contexts
[src
->index
]);
3496 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
3498 return plats
->ctxlat
.is_single_const ()
3499 && values_equal_for_ipcp_p (src
->val
->value
,
3500 plats
->ctxlat
.values
->value
);
3503 /* Get the next clone in the linked list of clones of an edge. */
3505 static inline struct cgraph_edge
*
3506 get_next_cgraph_edge_clone (struct cgraph_edge
*cs
)
3508 return next_edge_clone
[cs
->uid
];
3511 /* Given VAL that is intended for DEST, iterate over all its sources and if
3512 they still hold, add their edge frequency and their number into *FREQUENCY
3513 and *CALLER_COUNT respectively. */
3515 template <typename valtype
>
3517 get_info_about_necessary_edges (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
3519 gcov_type
*count_sum
, int *caller_count
)
3521 ipcp_value_source
<valtype
> *src
;
3522 int freq
= 0, count
= 0;
3526 for (src
= val
->sources
; src
; src
= src
->next
)
3528 struct cgraph_edge
*cs
= src
->cs
;
3531 if (cgraph_edge_brings_value_p (cs
, src
, dest
))
3534 freq
+= cs
->frequency
;
3536 hot
|= cs
->maybe_hot_p ();
3538 cs
= get_next_cgraph_edge_clone (cs
);
3544 *caller_count
= count
;
3548 /* Return a vector of incoming edges that do bring value VAL to node DEST. It
3549 is assumed their number is known and equal to CALLER_COUNT. */
3551 template <typename valtype
>
3552 static vec
<cgraph_edge
*>
3553 gather_edges_for_value (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
3556 ipcp_value_source
<valtype
> *src
;
3557 vec
<cgraph_edge
*> ret
;
3559 ret
.create (caller_count
);
3560 for (src
= val
->sources
; src
; src
= src
->next
)
3562 struct cgraph_edge
*cs
= src
->cs
;
3565 if (cgraph_edge_brings_value_p (cs
, src
, dest
))
3566 ret
.quick_push (cs
);
3567 cs
= get_next_cgraph_edge_clone (cs
);
3574 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
3575 Return it or NULL if for some reason it cannot be created. */
3577 static struct ipa_replace_map
*
3578 get_replacement_map (struct ipa_node_params
*info
, tree value
, int parm_num
)
3580 struct ipa_replace_map
*replace_map
;
3583 replace_map
= ggc_alloc
<ipa_replace_map
> ();
3586 fprintf (dump_file
, " replacing ");
3587 ipa_dump_param (dump_file
, info
, parm_num
);
3589 fprintf (dump_file
, " with const ");
3590 print_generic_expr (dump_file
, value
, 0);
3591 fprintf (dump_file
, "\n");
3593 replace_map
->old_tree
= NULL
;
3594 replace_map
->parm_num
= parm_num
;
3595 replace_map
->new_tree
= value
;
3596 replace_map
->replace_p
= true;
3597 replace_map
->ref_p
= false;
3602 /* Dump new profiling counts */
3605 dump_profile_updates (struct cgraph_node
*orig_node
,
3606 struct cgraph_node
*new_node
)
3608 struct cgraph_edge
*cs
;
3610 fprintf (dump_file
, " setting count of the specialized node to "
3611 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) new_node
->count
);
3612 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3613 fprintf (dump_file
, " edge to %s has count "
3614 HOST_WIDE_INT_PRINT_DEC
"\n",
3615 cs
->callee
->name (), (HOST_WIDE_INT
) cs
->count
);
3617 fprintf (dump_file
, " setting count of the original node to "
3618 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) orig_node
->count
);
3619 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3620 fprintf (dump_file
, " edge to %s is left with "
3621 HOST_WIDE_INT_PRINT_DEC
"\n",
3622 cs
->callee
->name (), (HOST_WIDE_INT
) cs
->count
);
3625 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
3626 their profile information to reflect this. */
3629 update_profiling_info (struct cgraph_node
*orig_node
,
3630 struct cgraph_node
*new_node
)
3632 struct cgraph_edge
*cs
;
3633 struct caller_statistics stats
;
3634 gcov_type new_sum
, orig_sum
;
3635 gcov_type remainder
, orig_node_count
= orig_node
->count
;
3637 if (orig_node_count
== 0)
3640 init_caller_stats (&stats
);
3641 orig_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
3643 orig_sum
= stats
.count_sum
;
3644 init_caller_stats (&stats
);
3645 new_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
3647 new_sum
= stats
.count_sum
;
3649 if (orig_node_count
< orig_sum
+ new_sum
)
3652 fprintf (dump_file
, " Problem: node %s/%i has too low count "
3653 HOST_WIDE_INT_PRINT_DEC
" while the sum of incoming "
3654 "counts is " HOST_WIDE_INT_PRINT_DEC
"\n",
3655 orig_node
->name (), orig_node
->order
,
3656 (HOST_WIDE_INT
) orig_node_count
,
3657 (HOST_WIDE_INT
) (orig_sum
+ new_sum
));
3659 orig_node_count
= (orig_sum
+ new_sum
) * 12 / 10;
3661 fprintf (dump_file
, " proceeding by pretending it was "
3662 HOST_WIDE_INT_PRINT_DEC
"\n",
3663 (HOST_WIDE_INT
) orig_node_count
);
3666 new_node
->count
= new_sum
;
3667 remainder
= orig_node_count
- new_sum
;
3668 orig_node
->count
= remainder
;
3670 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3672 cs
->count
= apply_probability (cs
->count
,
3673 GCOV_COMPUTE_SCALE (new_sum
,
3678 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3679 cs
->count
= apply_probability (cs
->count
,
3680 GCOV_COMPUTE_SCALE (remainder
,
3684 dump_profile_updates (orig_node
, new_node
);
3687 /* Update the respective profile of specialized NEW_NODE and the original
3688 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
3689 have been redirected to the specialized version. */
3692 update_specialized_profile (struct cgraph_node
*new_node
,
3693 struct cgraph_node
*orig_node
,
3694 gcov_type redirected_sum
)
3696 struct cgraph_edge
*cs
;
3697 gcov_type new_node_count
, orig_node_count
= orig_node
->count
;
3700 fprintf (dump_file
, " the sum of counts of redirected edges is "
3701 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) redirected_sum
);
3702 if (orig_node_count
== 0)
3705 gcc_assert (orig_node_count
>= redirected_sum
);
3707 new_node_count
= new_node
->count
;
3708 new_node
->count
+= redirected_sum
;
3709 orig_node
->count
-= redirected_sum
;
3711 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3713 cs
->count
+= apply_probability (cs
->count
,
3714 GCOV_COMPUTE_SCALE (redirected_sum
,
3719 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3721 gcov_type dec
= apply_probability (cs
->count
,
3722 GCOV_COMPUTE_SCALE (redirected_sum
,
3724 if (dec
< cs
->count
)
3731 dump_profile_updates (orig_node
, new_node
);
3734 /* Create a specialized version of NODE with known constants in KNOWN_CSTS,
3735 known contexts in KNOWN_CONTEXTS and known aggregate values in AGGVALS and
3736 redirect all edges in CALLERS to it. */
3738 static struct cgraph_node
*
3739 create_specialized_node (struct cgraph_node
*node
,
3740 vec
<tree
> known_csts
,
3741 vec
<ipa_polymorphic_call_context
> known_contexts
,
3742 struct ipa_agg_replacement_value
*aggvals
,
3743 vec
<cgraph_edge
*> callers
)
3745 struct ipa_node_params
*new_info
, *info
= IPA_NODE_REF (node
);
3746 vec
<ipa_replace_map
*, va_gc
> *replace_trees
= NULL
;
3747 struct ipa_agg_replacement_value
*av
;
3748 struct cgraph_node
*new_node
;
3749 int i
, count
= ipa_get_param_count (info
);
3750 bitmap args_to_skip
;
3752 gcc_assert (!info
->ipcp_orig_node
);
3754 if (node
->local
.can_change_signature
)
3756 args_to_skip
= BITMAP_GGC_ALLOC ();
3757 for (i
= 0; i
< count
; i
++)
3759 tree t
= known_csts
[i
];
3761 if (t
|| !ipa_is_param_used (info
, i
))
3762 bitmap_set_bit (args_to_skip
, i
);
3767 args_to_skip
= NULL
;
3768 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3769 fprintf (dump_file
, " cannot change function signature\n");
3772 for (i
= 0; i
< count
; i
++)
3774 tree t
= known_csts
[i
];
3777 struct ipa_replace_map
*replace_map
;
3779 gcc_checking_assert (TREE_CODE (t
) != TREE_BINFO
);
3780 replace_map
= get_replacement_map (info
, t
, i
);
3782 vec_safe_push (replace_trees
, replace_map
);
3786 new_node
= node
->create_virtual_clone (callers
, replace_trees
,
3787 args_to_skip
, "constprop");
3788 ipa_set_node_agg_value_chain (new_node
, aggvals
);
3789 for (av
= aggvals
; av
; av
= av
->next
)
3790 new_node
->maybe_create_reference (av
->value
, IPA_REF_ADDR
, NULL
);
3792 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3794 fprintf (dump_file
, " the new node is %s/%i.\n",
3795 new_node
->name (), new_node
->order
);
3796 if (known_contexts
.exists ())
3798 for (i
= 0; i
< count
; i
++)
3799 if (!known_contexts
[i
].useless_p ())
3801 fprintf (dump_file
, " known ctx %i is ", i
);
3802 known_contexts
[i
].dump (dump_file
);
3806 ipa_dump_agg_replacement_values (dump_file
, aggvals
);
3808 ipa_check_create_node_params ();
3809 update_profiling_info (node
, new_node
);
3810 new_info
= IPA_NODE_REF (new_node
);
3811 new_info
->ipcp_orig_node
= node
;
3812 new_info
->known_csts
= known_csts
;
3813 new_info
->known_contexts
= known_contexts
;
3815 ipcp_discover_new_direct_edges (new_node
, known_csts
, known_contexts
, aggvals
);
3821 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
3822 KNOWN_CSTS with constants that are also known for all of the CALLERS. */
3825 find_more_scalar_values_for_callers_subset (struct cgraph_node
*node
,
3826 vec
<tree
> known_csts
,
3827 vec
<cgraph_edge
*> callers
)
3829 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3830 int i
, count
= ipa_get_param_count (info
);
3832 for (i
= 0; i
< count
; i
++)
3834 struct cgraph_edge
*cs
;
3835 tree newval
= NULL_TREE
;
3839 if (ipa_get_scalar_lat (info
, i
)->bottom
|| known_csts
[i
])
3842 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3844 struct ipa_jump_func
*jump_func
;
3847 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
))
3849 && call_passes_through_thunk_p (cs
))
3850 || (!cs
->callee
->instrumentation_clone
3851 && cs
->callee
->function_symbol ()->instrumentation_clone
))
3856 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
3857 t
= ipa_value_from_jfunc (IPA_NODE_REF (cs
->caller
), jump_func
);
3860 && !values_equal_for_ipcp_p (t
, newval
))
3861 || (!first
&& !newval
))
3873 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3875 fprintf (dump_file
, " adding an extra known scalar value ");
3876 print_ipcp_constant_value (dump_file
, newval
);
3877 fprintf (dump_file
, " for ");
3878 ipa_dump_param (dump_file
, info
, i
);
3879 fprintf (dump_file
, "\n");
3882 known_csts
[i
] = newval
;
3887 /* Given a NODE and a subset of its CALLERS, try to populate plank slots in
3888 KNOWN_CONTEXTS with polymorphic contexts that are also known for all of the
3892 find_more_contexts_for_caller_subset (cgraph_node
*node
,
3893 vec
<ipa_polymorphic_call_context
>
3895 vec
<cgraph_edge
*> callers
)
3897 ipa_node_params
*info
= IPA_NODE_REF (node
);
3898 int i
, count
= ipa_get_param_count (info
);
3900 for (i
= 0; i
< count
; i
++)
3904 if (ipa_get_poly_ctx_lat (info
, i
)->bottom
3905 || (known_contexts
->exists ()
3906 && !(*known_contexts
)[i
].useless_p ()))
3909 ipa_polymorphic_call_context newval
;
3913 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3915 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
)))
3917 ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
),
3919 ipa_polymorphic_call_context ctx
;
3920 ctx
= ipa_context_from_jfunc (IPA_NODE_REF (cs
->caller
), cs
, i
,
3928 newval
.meet_with (ctx
);
3929 if (newval
.useless_p ())
3933 if (!newval
.useless_p ())
3935 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3937 fprintf (dump_file
, " adding an extra known polymorphic "
3939 print_ipcp_constant_value (dump_file
, newval
);
3940 fprintf (dump_file
, " for ");
3941 ipa_dump_param (dump_file
, info
, i
);
3942 fprintf (dump_file
, "\n");
3945 if (!known_contexts
->exists ())
3946 known_contexts
->safe_grow_cleared (ipa_get_param_count (info
));
3947 (*known_contexts
)[i
] = newval
;
3953 /* Go through PLATS and create a vector of values consisting of values and
3954 offsets (minus OFFSET) of lattices that contain only a single value. */
3956 static vec
<ipa_agg_jf_item
>
3957 copy_plats_to_inter (struct ipcp_param_lattices
*plats
, HOST_WIDE_INT offset
)
3959 vec
<ipa_agg_jf_item
> res
= vNULL
;
3961 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
3964 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3965 if (aglat
->is_single_const ())
3967 struct ipa_agg_jf_item ti
;
3968 ti
.offset
= aglat
->offset
- offset
;
3969 ti
.value
= aglat
->values
->value
;
3975 /* Intersect all values in INTER with single value lattices in PLATS (while
3976 subtracting OFFSET). */
3979 intersect_with_plats (struct ipcp_param_lattices
*plats
,
3980 vec
<ipa_agg_jf_item
> *inter
,
3981 HOST_WIDE_INT offset
)
3983 struct ipcp_agg_lattice
*aglat
;
3984 struct ipa_agg_jf_item
*item
;
3987 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
3993 aglat
= plats
->aggs
;
3994 FOR_EACH_VEC_ELT (*inter
, k
, item
)
4001 if (aglat
->offset
- offset
> item
->offset
)
4003 if (aglat
->offset
- offset
== item
->offset
)
4005 gcc_checking_assert (item
->value
);
4006 if (values_equal_for_ipcp_p (item
->value
, aglat
->values
->value
))
4010 aglat
= aglat
->next
;
4013 item
->value
= NULL_TREE
;
4017 /* Copy agggregate replacement values of NODE (which is an IPA-CP clone) to the
4018 vector result while subtracting OFFSET from the individual value offsets. */
4020 static vec
<ipa_agg_jf_item
>
4021 agg_replacements_to_vector (struct cgraph_node
*node
, int index
,
4022 HOST_WIDE_INT offset
)
4024 struct ipa_agg_replacement_value
*av
;
4025 vec
<ipa_agg_jf_item
> res
= vNULL
;
4027 for (av
= ipa_get_agg_replacements_for_node (node
); av
; av
= av
->next
)
4028 if (av
->index
== index
4029 && (av
->offset
- offset
) >= 0)
4031 struct ipa_agg_jf_item item
;
4032 gcc_checking_assert (av
->value
);
4033 item
.offset
= av
->offset
- offset
;
4034 item
.value
= av
->value
;
4035 res
.safe_push (item
);
4041 /* Intersect all values in INTER with those that we have already scheduled to
4042 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
4043 (while subtracting OFFSET). */
4046 intersect_with_agg_replacements (struct cgraph_node
*node
, int index
,
4047 vec
<ipa_agg_jf_item
> *inter
,
4048 HOST_WIDE_INT offset
)
4050 struct ipa_agg_replacement_value
*srcvals
;
4051 struct ipa_agg_jf_item
*item
;
4054 srcvals
= ipa_get_agg_replacements_for_node (node
);
4061 FOR_EACH_VEC_ELT (*inter
, i
, item
)
4063 struct ipa_agg_replacement_value
*av
;
4067 for (av
= srcvals
; av
; av
= av
->next
)
4069 gcc_checking_assert (av
->value
);
4070 if (av
->index
== index
4071 && av
->offset
- offset
== item
->offset
)
4073 if (values_equal_for_ipcp_p (item
->value
, av
->value
))
4079 item
->value
= NULL_TREE
;
4083 /* Intersect values in INTER with aggregate values that come along edge CS to
4084 parameter number INDEX and return it. If INTER does not actually exist yet,
4085 copy all incoming values to it. If we determine we ended up with no values
4086 whatsoever, return a released vector. */
4088 static vec
<ipa_agg_jf_item
>
4089 intersect_aggregates_with_edge (struct cgraph_edge
*cs
, int index
,
4090 vec
<ipa_agg_jf_item
> inter
)
4092 struct ipa_jump_func
*jfunc
;
4093 jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), index
);
4094 if (jfunc
->type
== IPA_JF_PASS_THROUGH
4095 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
4097 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4098 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
4100 if (caller_info
->ipcp_orig_node
)
4102 struct cgraph_node
*orig_node
= caller_info
->ipcp_orig_node
;
4103 struct ipcp_param_lattices
*orig_plats
;
4104 orig_plats
= ipa_get_parm_lattices (IPA_NODE_REF (orig_node
),
4106 if (agg_pass_through_permissible_p (orig_plats
, jfunc
))
4108 if (!inter
.exists ())
4109 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, 0);
4111 intersect_with_agg_replacements (cs
->caller
, src_idx
,
4122 struct ipcp_param_lattices
*src_plats
;
4123 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
4124 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
4126 /* Currently we do not produce clobber aggregate jump
4127 functions, adjust when we do. */
4128 gcc_checking_assert (!jfunc
->agg
.items
);
4129 if (!inter
.exists ())
4130 inter
= copy_plats_to_inter (src_plats
, 0);
4132 intersect_with_plats (src_plats
, &inter
, 0);
4141 else if (jfunc
->type
== IPA_JF_ANCESTOR
4142 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
4144 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4145 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
4146 struct ipcp_param_lattices
*src_plats
;
4147 HOST_WIDE_INT delta
= ipa_get_jf_ancestor_offset (jfunc
);
4149 if (caller_info
->ipcp_orig_node
)
4151 if (!inter
.exists ())
4152 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, delta
);
4154 intersect_with_agg_replacements (cs
->caller
, src_idx
, &inter
,
4159 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);;
4160 /* Currently we do not produce clobber aggregate jump
4161 functions, adjust when we do. */
4162 gcc_checking_assert (!src_plats
->aggs
|| !jfunc
->agg
.items
);
4163 if (!inter
.exists ())
4164 inter
= copy_plats_to_inter (src_plats
, delta
);
4166 intersect_with_plats (src_plats
, &inter
, delta
);
4169 else if (jfunc
->agg
.items
)
4171 struct ipa_agg_jf_item
*item
;
4174 if (!inter
.exists ())
4175 for (unsigned i
= 0; i
< jfunc
->agg
.items
->length (); i
++)
4176 inter
.safe_push ((*jfunc
->agg
.items
)[i
]);
4178 FOR_EACH_VEC_ELT (inter
, k
, item
)
4181 bool found
= false;;
4186 while ((unsigned) l
< jfunc
->agg
.items
->length ())
4188 struct ipa_agg_jf_item
*ti
;
4189 ti
= &(*jfunc
->agg
.items
)[l
];
4190 if (ti
->offset
> item
->offset
)
4192 if (ti
->offset
== item
->offset
)
4194 gcc_checking_assert (ti
->value
);
4195 if (values_equal_for_ipcp_p (item
->value
,
4209 return vec
<ipa_agg_jf_item
>();
4214 /* Look at edges in CALLERS and collect all known aggregate values that arrive
4215 from all of them. */
4217 static struct ipa_agg_replacement_value
*
4218 find_aggregate_values_for_callers_subset (struct cgraph_node
*node
,
4219 vec
<cgraph_edge
*> callers
)
4221 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
4222 struct ipa_agg_replacement_value
*res
;
4223 struct ipa_agg_replacement_value
**tail
= &res
;
4224 struct cgraph_edge
*cs
;
4225 int i
, j
, count
= ipa_get_param_count (dest_info
);
4227 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4229 int c
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
4234 for (i
= 0; i
< count
; i
++)
4236 struct cgraph_edge
*cs
;
4237 vec
<ipa_agg_jf_item
> inter
= vNULL
;
4238 struct ipa_agg_jf_item
*item
;
4239 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (dest_info
, i
);
4242 /* Among other things, the following check should deal with all by_ref
4244 if (plats
->aggs_bottom
)
4247 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4249 inter
= intersect_aggregates_with_edge (cs
, i
, inter
);
4251 if (!inter
.exists ())
4255 FOR_EACH_VEC_ELT (inter
, j
, item
)
4257 struct ipa_agg_replacement_value
*v
;
4262 v
= ggc_alloc
<ipa_agg_replacement_value
> ();
4264 v
->offset
= item
->offset
;
4265 v
->value
= item
->value
;
4266 v
->by_ref
= plats
->aggs_by_ref
;
4272 if (inter
.exists ())
4279 /* Turn KNOWN_AGGS into a list of aggreate replacement values. */
4281 static struct ipa_agg_replacement_value
*
4282 known_aggs_to_agg_replacement_list (vec
<ipa_agg_jump_function
> known_aggs
)
4284 struct ipa_agg_replacement_value
*res
;
4285 struct ipa_agg_replacement_value
**tail
= &res
;
4286 struct ipa_agg_jump_function
*aggjf
;
4287 struct ipa_agg_jf_item
*item
;
4290 FOR_EACH_VEC_ELT (known_aggs
, i
, aggjf
)
4291 FOR_EACH_VEC_SAFE_ELT (aggjf
->items
, j
, item
)
4293 struct ipa_agg_replacement_value
*v
;
4294 v
= ggc_alloc
<ipa_agg_replacement_value
> ();
4296 v
->offset
= item
->offset
;
4297 v
->value
= item
->value
;
4298 v
->by_ref
= aggjf
->by_ref
;
4306 /* Determine whether CS also brings all scalar values that the NODE is
4310 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge
*cs
,
4311 struct cgraph_node
*node
)
4313 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
4314 int count
= ipa_get_param_count (dest_info
);
4315 struct ipa_node_params
*caller_info
;
4316 struct ipa_edge_args
*args
;
4319 caller_info
= IPA_NODE_REF (cs
->caller
);
4320 args
= IPA_EDGE_REF (cs
);
4321 for (i
= 0; i
< count
; i
++)
4323 struct ipa_jump_func
*jump_func
;
4326 val
= dest_info
->known_csts
[i
];
4330 if (i
>= ipa_get_cs_argument_count (args
))
4332 jump_func
= ipa_get_ith_jump_func (args
, i
);
4333 t
= ipa_value_from_jfunc (caller_info
, jump_func
);
4334 if (!t
|| !values_equal_for_ipcp_p (val
, t
))
4340 /* Determine whether CS also brings all aggregate values that NODE is
4343 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge
*cs
,
4344 struct cgraph_node
*node
)
4346 struct ipa_node_params
*orig_caller_info
= IPA_NODE_REF (cs
->caller
);
4347 struct ipa_node_params
*orig_node_info
;
4348 struct ipa_agg_replacement_value
*aggval
;
4351 aggval
= ipa_get_agg_replacements_for_node (node
);
4355 count
= ipa_get_param_count (IPA_NODE_REF (node
));
4356 ec
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
4358 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4359 if (aggval
->index
>= ec
)
4362 orig_node_info
= IPA_NODE_REF (IPA_NODE_REF (node
)->ipcp_orig_node
);
4363 if (orig_caller_info
->ipcp_orig_node
)
4364 orig_caller_info
= IPA_NODE_REF (orig_caller_info
->ipcp_orig_node
);
4366 for (i
= 0; i
< count
; i
++)
4368 static vec
<ipa_agg_jf_item
> values
= vec
<ipa_agg_jf_item
>();
4369 struct ipcp_param_lattices
*plats
;
4370 bool interesting
= false;
4371 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4372 if (aggval
->index
== i
)
4380 plats
= ipa_get_parm_lattices (orig_node_info
, aggval
->index
);
4381 if (plats
->aggs_bottom
)
4384 values
= intersect_aggregates_with_edge (cs
, i
, values
);
4385 if (!values
.exists ())
4388 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4389 if (aggval
->index
== i
)
4391 struct ipa_agg_jf_item
*item
;
4394 FOR_EACH_VEC_ELT (values
, j
, item
)
4396 && item
->offset
== av
->offset
4397 && values_equal_for_ipcp_p (item
->value
, av
->value
))
4412 /* Given an original NODE and a VAL for which we have already created a
4413 specialized clone, look whether there are incoming edges that still lead
4414 into the old node but now also bring the requested value and also conform to
4415 all other criteria such that they can be redirected the special node.
4416 This function can therefore redirect the final edge in a SCC. */
4418 template <typename valtype
>
4420 perhaps_add_new_callers (cgraph_node
*node
, ipcp_value
<valtype
> *val
)
4422 ipcp_value_source
<valtype
> *src
;
4423 gcov_type redirected_sum
= 0;
4425 for (src
= val
->sources
; src
; src
= src
->next
)
4427 struct cgraph_edge
*cs
= src
->cs
;
4430 if (cgraph_edge_brings_value_p (cs
, src
, node
)
4431 && cgraph_edge_brings_all_scalars_for_node (cs
, val
->spec_node
)
4432 && cgraph_edge_brings_all_agg_vals_for_node (cs
, val
->spec_node
))
4435 fprintf (dump_file
, " - adding an extra caller %s/%i"
4437 xstrdup_for_dump (cs
->caller
->name ()),
4439 xstrdup_for_dump (val
->spec_node
->name ()),
4440 val
->spec_node
->order
);
4442 cs
->redirect_callee_duplicating_thunks (val
->spec_node
);
4443 val
->spec_node
->expand_all_artificial_thunks ();
4444 redirected_sum
+= cs
->count
;
4446 cs
= get_next_cgraph_edge_clone (cs
);
4451 update_specialized_profile (val
->spec_node
, node
, redirected_sum
);
4454 /* Return true if KNOWN_CONTEXTS contain at least one useful context. */
4457 known_contexts_useful_p (vec
<ipa_polymorphic_call_context
> known_contexts
)
4459 ipa_polymorphic_call_context
*ctx
;
4462 FOR_EACH_VEC_ELT (known_contexts
, i
, ctx
)
4463 if (!ctx
->useless_p ())
4468 /* Return a copy of KNOWN_CSTS if it is not empty, otherwise return vNULL. */
4470 static vec
<ipa_polymorphic_call_context
>
4471 copy_useful_known_contexts (vec
<ipa_polymorphic_call_context
> known_contexts
)
4473 if (known_contexts_useful_p (known_contexts
))
4474 return known_contexts
.copy ();
4479 /* Copy KNOWN_CSTS and modify the copy according to VAL and INDEX. If
4480 non-empty, replace KNOWN_CONTEXTS with its copy too. */
4483 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
4484 vec
<ipa_polymorphic_call_context
> *known_contexts
,
4485 ipcp_value
<tree
> *val
,
4488 *known_csts
= known_csts
->copy ();
4489 *known_contexts
= copy_useful_known_contexts (*known_contexts
);
4490 (*known_csts
)[index
] = val
->value
;
4493 /* Replace KNOWN_CSTS with its copy. Also copy KNOWN_CONTEXTS and modify the
4494 copy according to VAL and INDEX. */
4497 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
4498 vec
<ipa_polymorphic_call_context
> *known_contexts
,
4499 ipcp_value
<ipa_polymorphic_call_context
> *val
,
4502 *known_csts
= known_csts
->copy ();
4503 *known_contexts
= known_contexts
->copy ();
4504 (*known_contexts
)[index
] = val
->value
;
4507 /* Return true if OFFSET indicates this was not an aggregate value or there is
4508 a replacement equivalent to VALUE, INDEX and OFFSET among those in the
4512 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*aggvals
,
4513 int index
, HOST_WIDE_INT offset
, tree value
)
4520 if (aggvals
->index
== index
4521 && aggvals
->offset
== offset
4522 && values_equal_for_ipcp_p (aggvals
->value
, value
))
4524 aggvals
= aggvals
->next
;
4529 /* Return true if offset is minus one because source of a polymorphic contect
4530 cannot be an aggregate value. */
4533 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*,
4534 int , HOST_WIDE_INT offset
,
4535 ipa_polymorphic_call_context
)
4537 return offset
== -1;
4540 /* Decide wheter to create a special version of NODE for value VAL of parameter
4541 at the given INDEX. If OFFSET is -1, the value is for the parameter itself,
4542 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS,
4543 KNOWN_CONTEXTS and KNOWN_AGGS describe the other already known values. */
4545 template <typename valtype
>
4547 decide_about_value (struct cgraph_node
*node
, int index
, HOST_WIDE_INT offset
,
4548 ipcp_value
<valtype
> *val
, vec
<tree
> known_csts
,
4549 vec
<ipa_polymorphic_call_context
> known_contexts
)
4551 struct ipa_agg_replacement_value
*aggvals
;
4552 int freq_sum
, caller_count
;
4553 gcov_type count_sum
;
4554 vec
<cgraph_edge
*> callers
;
4558 perhaps_add_new_callers (node
, val
);
4561 else if (val
->local_size_cost
+ overall_size
> max_new_size
)
4563 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4564 fprintf (dump_file
, " Ignoring candidate value because "
4565 "max_new_size would be reached with %li.\n",
4566 val
->local_size_cost
+ overall_size
);
4569 else if (!get_info_about_necessary_edges (val
, node
, &freq_sum
, &count_sum
,
4573 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4575 fprintf (dump_file
, " - considering value ");
4576 print_ipcp_constant_value (dump_file
, val
->value
);
4577 fprintf (dump_file
, " for ");
4578 ipa_dump_param (dump_file
, IPA_NODE_REF (node
), index
);
4580 fprintf (dump_file
, ", offset: " HOST_WIDE_INT_PRINT_DEC
, offset
);
4581 fprintf (dump_file
, " (caller_count: %i)\n", caller_count
);
4584 if (!good_cloning_opportunity_p (node
, val
->local_time_benefit
,
4585 freq_sum
, count_sum
,
4586 val
->local_size_cost
)
4587 && !good_cloning_opportunity_p (node
,
4588 val
->local_time_benefit
4589 + val
->prop_time_benefit
,
4590 freq_sum
, count_sum
,
4591 val
->local_size_cost
4592 + val
->prop_size_cost
))
4596 fprintf (dump_file
, " Creating a specialized node of %s/%i.\n",
4597 node
->name (), node
->order
);
4599 callers
= gather_edges_for_value (val
, node
, caller_count
);
4601 modify_known_vectors_with_val (&known_csts
, &known_contexts
, val
, index
);
4604 known_csts
= known_csts
.copy ();
4605 known_contexts
= copy_useful_known_contexts (known_contexts
);
4607 find_more_scalar_values_for_callers_subset (node
, known_csts
, callers
);
4608 find_more_contexts_for_caller_subset (node
, &known_contexts
, callers
);
4609 aggvals
= find_aggregate_values_for_callers_subset (node
, callers
);
4610 gcc_checking_assert (ipcp_val_agg_replacement_ok_p (aggvals
, index
,
4611 offset
, val
->value
));
4612 val
->spec_node
= create_specialized_node (node
, known_csts
, known_contexts
,
4614 overall_size
+= val
->local_size_cost
;
4616 /* TODO: If for some lattice there is only one other known value
4617 left, make a special node for it too. */
4622 /* Decide whether and what specialized clones of NODE should be created. */
4625 decide_whether_version_node (struct cgraph_node
*node
)
4627 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
4628 int i
, count
= ipa_get_param_count (info
);
4629 vec
<tree
> known_csts
;
4630 vec
<ipa_polymorphic_call_context
> known_contexts
;
4631 vec
<ipa_agg_jump_function
> known_aggs
= vNULL
;
4637 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4638 fprintf (dump_file
, "\nEvaluating opportunities for %s/%i.\n",
4639 node
->name (), node
->order
);
4641 gather_context_independent_values (info
, &known_csts
, &known_contexts
,
4642 info
->do_clone_for_all_contexts
? &known_aggs
4645 for (i
= 0; i
< count
;i
++)
4647 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4648 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
4649 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
4654 ipcp_value
<tree
> *val
;
4655 for (val
= lat
->values
; val
; val
= val
->next
)
4656 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
4660 if (!plats
->aggs_bottom
)
4662 struct ipcp_agg_lattice
*aglat
;
4663 ipcp_value
<tree
> *val
;
4664 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
4665 if (!aglat
->bottom
&& aglat
->values
4666 /* If the following is false, the one value is in
4668 && (plats
->aggs_contain_variable
4669 || !aglat
->is_single_const ()))
4670 for (val
= aglat
->values
; val
; val
= val
->next
)
4671 ret
|= decide_about_value (node
, i
, aglat
->offset
, val
,
4672 known_csts
, known_contexts
);
4676 && known_contexts
[i
].useless_p ())
4678 ipcp_value
<ipa_polymorphic_call_context
> *val
;
4679 for (val
= ctxlat
->values
; val
; val
= val
->next
)
4680 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
4684 info
= IPA_NODE_REF (node
);
4687 if (info
->do_clone_for_all_contexts
)
4689 struct cgraph_node
*clone
;
4690 vec
<cgraph_edge
*> callers
;
4693 fprintf (dump_file
, " - Creating a specialized node of %s/%i "
4694 "for all known contexts.\n", node
->name (),
4697 callers
= node
->collect_callers ();
4699 if (!known_contexts_useful_p (known_contexts
))
4701 known_contexts
.release ();
4702 known_contexts
= vNULL
;
4704 clone
= create_specialized_node (node
, known_csts
, known_contexts
,
4705 known_aggs_to_agg_replacement_list (known_aggs
),
4707 info
= IPA_NODE_REF (node
);
4708 info
->do_clone_for_all_contexts
= false;
4709 IPA_NODE_REF (clone
)->is_all_contexts_clone
= true;
4710 for (i
= 0; i
< count
; i
++)
4711 vec_free (known_aggs
[i
].items
);
4712 known_aggs
.release ();
4717 known_csts
.release ();
4718 known_contexts
.release ();
4724 /* Transitively mark all callees of NODE within the same SCC as not dead. */
4727 spread_undeadness (struct cgraph_node
*node
)
4729 struct cgraph_edge
*cs
;
4731 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
4732 if (ipa_edge_within_scc (cs
))
4734 struct cgraph_node
*callee
;
4735 struct ipa_node_params
*info
;
4737 callee
= cs
->callee
->function_symbol (NULL
);
4738 info
= IPA_NODE_REF (callee
);
4740 if (info
->node_dead
)
4742 info
->node_dead
= 0;
4743 spread_undeadness (callee
);
4748 /* Return true if NODE has a caller from outside of its SCC that is not
4749 dead. Worker callback for cgraph_for_node_and_aliases. */
4752 has_undead_caller_from_outside_scc_p (struct cgraph_node
*node
,
4753 void *data ATTRIBUTE_UNUSED
)
4755 struct cgraph_edge
*cs
;
4757 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
4758 if (cs
->caller
->thunk
.thunk_p
4759 && cs
->caller
->call_for_symbol_thunks_and_aliases
4760 (has_undead_caller_from_outside_scc_p
, NULL
, true))
4762 else if (!ipa_edge_within_scc (cs
)
4763 && !IPA_NODE_REF (cs
->caller
)->node_dead
)
4769 /* Identify nodes within the same SCC as NODE which are no longer needed
4770 because of new clones and will be removed as unreachable. */
4773 identify_dead_nodes (struct cgraph_node
*node
)
4775 struct cgraph_node
*v
;
4776 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4778 && !v
->call_for_symbol_thunks_and_aliases
4779 (has_undead_caller_from_outside_scc_p
, NULL
, true))
4780 IPA_NODE_REF (v
)->node_dead
= 1;
4782 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4783 if (!IPA_NODE_REF (v
)->node_dead
)
4784 spread_undeadness (v
);
4786 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4788 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4789 if (IPA_NODE_REF (v
)->node_dead
)
4790 fprintf (dump_file
, " Marking node as dead: %s/%i.\n",
4791 v
->name (), v
->order
);
4795 /* The decision stage. Iterate over the topological order of call graph nodes
4796 TOPO and make specialized clones if deemed beneficial. */
4799 ipcp_decision_stage (struct ipa_topo_info
*topo
)
4804 fprintf (dump_file
, "\nIPA decision stage:\n\n");
4806 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
4808 struct cgraph_node
*node
= topo
->order
[i
];
4809 bool change
= false, iterate
= true;
4813 struct cgraph_node
*v
;
4815 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4816 if (v
->has_gimple_body_p ()
4817 && ipcp_versionable_function_p (v
))
4818 iterate
|= decide_whether_version_node (v
);
4823 identify_dead_nodes (node
);
4827 /* Look up all alignment information that we have discovered and copy it over
4828 to the transformation summary. */
4831 ipcp_store_alignment_results (void)
4835 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
4837 ipa_node_params
*info
= IPA_NODE_REF (node
);
4838 bool dumped_sth
= false;
4839 bool found_useful_result
= false;
4841 if (!opt_for_fn (node
->decl
, flag_ipa_cp_alignment
))
4844 fprintf (dump_file
, "Not considering %s for alignment discovery "
4845 "and propagate; -fipa-cp-alignment: disabled.\n",
4850 if (info
->ipcp_orig_node
)
4851 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
4853 unsigned count
= ipa_get_param_count (info
);
4854 for (unsigned i
= 0; i
< count
; i
++)
4856 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4857 if (!plats
->alignment
.bottom_p ()
4858 && !plats
->alignment
.top_p ())
4860 gcc_checking_assert (plats
->alignment
.align
> 0);
4861 found_useful_result
= true;
4865 if (!found_useful_result
)
4868 ipcp_grow_transformations_if_necessary ();
4869 ipcp_transformation_summary
*ts
= ipcp_get_transformation_summary (node
);
4870 vec_safe_reserve_exact (ts
->alignments
, count
);
4872 for (unsigned i
= 0; i
< count
; i
++)
4874 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4877 if (!plats
->alignment
.bottom_p ()
4878 && !plats
->alignment
.top_p ())
4881 al
.align
= plats
->alignment
.align
;
4882 al
.misalign
= plats
->alignment
.misalign
;
4887 ts
->alignments
->quick_push (al
);
4888 if (!dump_file
|| !al
.known
)
4892 fprintf (dump_file
, "Propagated alignment info for function %s/%i:\n",
4893 node
->name (), node
->order
);
4896 fprintf (dump_file
, " param %i: align: %u, misalign: %u\n",
4897 i
, al
.align
, al
.misalign
);
4902 /* Look up all the bits information that we have discovered and copy it over
4903 to the transformation summary. */
4906 ipcp_store_bits_results (void)
4910 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
4912 ipa_node_params
*info
= IPA_NODE_REF (node
);
4913 bool dumped_sth
= false;
4914 bool found_useful_result
= false;
4916 if (!opt_for_fn (node
->decl
, flag_ipa_bit_cp
))
4919 fprintf (dump_file
, "Not considering %s for ipa bitwise propagation "
4920 "; -fipa-bit-cp: disabled.\n",
4925 if (info
->ipcp_orig_node
)
4926 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
4928 unsigned count
= ipa_get_param_count (info
);
4929 for (unsigned i
= 0; i
< count
; i
++)
4931 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4932 if (plats
->bits_lattice
.constant_p ())
4934 found_useful_result
= true;
4939 if (!found_useful_result
)
4942 ipcp_grow_transformations_if_necessary ();
4943 ipcp_transformation_summary
*ts
= ipcp_get_transformation_summary (node
);
4944 vec_safe_reserve_exact (ts
->bits
, count
);
4946 for (unsigned i
= 0; i
< count
; i
++)
4948 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4949 ipa_bits bits_jfunc
;
4951 if (plats
->bits_lattice
.constant_p ())
4953 bits_jfunc
.known
= true;
4954 bits_jfunc
.value
= plats
->bits_lattice
.get_value ();
4955 bits_jfunc
.mask
= plats
->bits_lattice
.get_mask ();
4958 bits_jfunc
.known
= false;
4960 ts
->bits
->quick_push (bits_jfunc
);
4961 if (!dump_file
|| !bits_jfunc
.known
)
4965 fprintf (dump_file
, "Propagated bits info for function %s/%i:\n",
4966 node
->name (), node
->order
);
4969 fprintf (dump_file
, " param %i: value = ", i
);
4970 print_hex (bits_jfunc
.value
, dump_file
);
4971 fprintf (dump_file
, ", mask = ");
4972 print_hex (bits_jfunc
.mask
, dump_file
);
4973 fprintf (dump_file
, "\n");
4977 /* The IPCP driver. */
4982 struct cgraph_2edge_hook_list
*edge_duplication_hook_holder
;
4983 struct cgraph_edge_hook_list
*edge_removal_hook_holder
;
4984 struct ipa_topo_info topo
;
4986 ipa_check_create_node_params ();
4987 ipa_check_create_edge_args ();
4988 grow_edge_clone_vectors ();
4989 edge_duplication_hook_holder
=
4990 symtab
->add_edge_duplication_hook (&ipcp_edge_duplication_hook
, NULL
);
4991 edge_removal_hook_holder
=
4992 symtab
->add_edge_removal_hook (&ipcp_edge_removal_hook
, NULL
);
4996 fprintf (dump_file
, "\nIPA structures before propagation:\n");
4997 if (dump_flags
& TDF_DETAILS
)
4998 ipa_print_all_params (dump_file
);
4999 ipa_print_all_jump_functions (dump_file
);
5002 /* Topological sort. */
5003 build_toporder_info (&topo
);
5004 /* Do the interprocedural propagation. */
5005 ipcp_propagate_stage (&topo
);
5006 /* Decide what constant propagation and cloning should be performed. */
5007 ipcp_decision_stage (&topo
);
5008 /* Store results of alignment propagation. */
5009 ipcp_store_alignment_results ();
5010 /* Store results of bits propagation. */
5011 ipcp_store_bits_results ();
5013 /* Free all IPCP structures. */
5014 free_toporder_info (&topo
);
5015 next_edge_clone
.release ();
5016 prev_edge_clone
.release ();
5017 symtab
->remove_edge_removal_hook (edge_removal_hook_holder
);
5018 symtab
->remove_edge_duplication_hook (edge_duplication_hook_holder
);
5019 ipa_free_all_structures_after_ipa_cp ();
5021 fprintf (dump_file
, "\nIPA constant propagation end\n");
5025 /* Initialization and computation of IPCP data structures. This is the initial
5026 intraprocedural analysis of functions, which gathers information to be
5027 propagated later on. */
5030 ipcp_generate_summary (void)
5032 struct cgraph_node
*node
;
5035 fprintf (dump_file
, "\nIPA constant propagation start:\n");
5036 ipa_register_cgraph_hooks ();
5038 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5039 ipa_analyze_node (node
);
5042 /* Write ipcp summary for nodes in SET. */
5045 ipcp_write_summary (void)
5047 ipa_prop_write_jump_functions ();
5050 /* Read ipcp summary. */
5053 ipcp_read_summary (void)
5055 ipa_prop_read_jump_functions ();
5060 const pass_data pass_data_ipa_cp
=
5062 IPA_PASS
, /* type */
5064 OPTGROUP_NONE
, /* optinfo_flags */
5065 TV_IPA_CONSTANT_PROP
, /* tv_id */
5066 0, /* properties_required */
5067 0, /* properties_provided */
5068 0, /* properties_destroyed */
5069 0, /* todo_flags_start */
5070 ( TODO_dump_symtab
| TODO_remove_functions
), /* todo_flags_finish */
5073 class pass_ipa_cp
: public ipa_opt_pass_d
5076 pass_ipa_cp (gcc::context
*ctxt
)
5077 : ipa_opt_pass_d (pass_data_ipa_cp
, ctxt
,
5078 ipcp_generate_summary
, /* generate_summary */
5079 ipcp_write_summary
, /* write_summary */
5080 ipcp_read_summary
, /* read_summary */
5081 ipcp_write_transformation_summaries
, /*
5082 write_optimization_summary */
5083 ipcp_read_transformation_summaries
, /*
5084 read_optimization_summary */
5085 NULL
, /* stmt_fixup */
5086 0, /* function_transform_todo_flags_start */
5087 ipcp_transform_function
, /* function_transform */
5088 NULL
) /* variable_transform */
5091 /* opt_pass methods: */
5092 virtual bool gate (function
*)
5094 /* FIXME: We should remove the optimize check after we ensure we never run
5095 IPA passes when not optimizing. */
5096 return (flag_ipa_cp
&& optimize
) || in_lto_p
;
5099 virtual unsigned int execute (function
*) { return ipcp_driver (); }
5101 }; // class pass_ipa_cp
5106 make_pass_ipa_cp (gcc::context
*ctxt
)
5108 return new pass_ipa_cp (ctxt
);
5111 /* Reset all state within ipa-cp.c so that we can rerun the compiler
5112 within the same process. For use by toplev::finalize. */
5115 ipa_cp_c_finalize (void)