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 "tree-vrp.h"
118 #include "ipa-prop.h"
119 #include "tree-pretty-print.h"
120 #include "tree-inline.h"
122 #include "ipa-inline.h"
123 #include "ipa-utils.h"
124 #include "tree-ssa-ccp.h"
126 template <typename valtype
> class ipcp_value
;
128 /* Describes a particular source for an IPA-CP value. */
130 template <typename valtype
>
131 class ipcp_value_source
134 /* Aggregate offset of the source, negative if the source is scalar value of
135 the argument itself. */
136 HOST_WIDE_INT offset
;
137 /* The incoming edge that brought the value. */
139 /* If the jump function that resulted into his value was a pass-through or an
140 ancestor, this is the ipcp_value of the caller from which the described
141 value has been derived. Otherwise it is NULL. */
142 ipcp_value
<valtype
> *val
;
143 /* Next pointer in a linked list of sources of a value. */
144 ipcp_value_source
*next
;
145 /* If the jump function that resulted into his value was a pass-through or an
146 ancestor, this is the index of the parameter of the caller the jump
147 function references. */
151 /* Common ancestor for all ipcp_value instantiations. */
153 class ipcp_value_base
156 /* Time benefit and size cost that specializing the function for this value
157 would bring about in this function alone. */
158 int local_time_benefit
, local_size_cost
;
159 /* Time benefit and size cost that specializing the function for this value
160 can bring about in it's callees (transitively). */
161 int prop_time_benefit
, prop_size_cost
;
164 /* Describes one particular value stored in struct ipcp_lattice. */
166 template <typename valtype
>
167 class ipcp_value
: public ipcp_value_base
170 /* The actual value for the given parameter. */
172 /* The list of sources from which this value originates. */
173 ipcp_value_source
<valtype
> *sources
;
174 /* Next pointers in a linked list of all values in a lattice. */
176 /* Next pointers in a linked list of values in a strongly connected component
178 ipcp_value
*scc_next
;
179 /* Next pointers in a linked list of SCCs of values sorted topologically
180 according their sources. */
181 ipcp_value
*topo_next
;
182 /* A specialized node created for this value, NULL if none has been (so far)
184 cgraph_node
*spec_node
;
185 /* Depth first search number and low link for topological sorting of
188 /* True if this valye is currently on the topo-sort stack. */
191 void add_source (cgraph_edge
*cs
, ipcp_value
*src_val
, int src_idx
,
192 HOST_WIDE_INT offset
);
195 /* Lattice describing potential values of a formal parameter of a function, or
196 a part of an aggreagate. TOP is represented by a lattice with zero values
197 and with contains_variable and bottom flags cleared. BOTTOM is represented
198 by a lattice with the bottom flag set. In that case, values and
199 contains_variable flag should be disregarded. */
201 template <typename valtype
>
205 /* The list of known values and types in this lattice. Note that values are
206 not deallocated if a lattice is set to bottom because there may be value
207 sources referencing them. */
208 ipcp_value
<valtype
> *values
;
209 /* Number of known values and types in this lattice. */
211 /* The lattice contains a variable component (in addition to values). */
212 bool contains_variable
;
213 /* The value of the lattice is bottom (i.e. variable and unusable for any
217 inline bool is_single_const ();
218 inline bool set_to_bottom ();
219 inline bool set_contains_variable ();
220 bool add_value (valtype newval
, cgraph_edge
*cs
,
221 ipcp_value
<valtype
> *src_val
= NULL
,
222 int src_idx
= 0, HOST_WIDE_INT offset
= -1);
223 void print (FILE * f
, bool dump_sources
, bool dump_benefits
);
226 /* Lattice of tree values with an offset to describe a part of an
229 class ipcp_agg_lattice
: public ipcp_lattice
<tree
>
232 /* Offset that is being described by this lattice. */
233 HOST_WIDE_INT offset
;
234 /* Size so that we don't have to re-compute it every time we traverse the
235 list. Must correspond to TYPE_SIZE of all lat values. */
237 /* Next element of the linked list. */
238 struct ipcp_agg_lattice
*next
;
241 /* Lattice of known bits, only capable of holding one value.
242 Bitwise constant propagation propagates which bits of a
258 In the above case, the param 'x' will always have all
259 the bits (except the bits in lsb) set to 0.
260 Hence the mask of 'x' would be 0xff. The mask
261 reflects that the bits in lsb are unknown.
262 The actual propagated value is given by m_value & ~m_mask. */
264 class ipcp_bits_lattice
267 bool bottom_p () { return m_lattice_val
== IPA_BITS_VARYING
; }
268 bool top_p () { return m_lattice_val
== IPA_BITS_UNDEFINED
; }
269 bool constant_p () { return m_lattice_val
== IPA_BITS_CONSTANT
; }
270 bool set_to_bottom ();
271 bool set_to_constant (widest_int
, widest_int
);
273 widest_int
get_value () { return m_value
; }
274 widest_int
get_mask () { return m_mask
; }
276 bool meet_with (ipcp_bits_lattice
& other
, unsigned, signop
,
277 enum tree_code
, tree
);
279 bool meet_with (widest_int
, widest_int
, unsigned);
284 enum { IPA_BITS_UNDEFINED
, IPA_BITS_CONSTANT
, IPA_BITS_VARYING
} m_lattice_val
;
286 /* Similar to ccp_lattice_t, mask represents which bits of value are constant.
287 If a bit in mask is set to 0, then the corresponding bit in
288 value is known to be constant. */
289 widest_int m_value
, m_mask
;
291 bool meet_with_1 (widest_int
, widest_int
, unsigned);
292 void get_value_and_mask (tree
, widest_int
*, widest_int
*);
295 /* Lattice of value ranges. */
297 class ipcp_vr_lattice
302 inline bool bottom_p () const;
303 inline bool top_p () const;
304 inline bool set_to_bottom ();
305 bool meet_with (const value_range
*p_vr
);
306 bool meet_with (const ipcp_vr_lattice
&other
);
307 void init () { m_vr
.type
= VR_UNDEFINED
; }
308 void print (FILE * f
);
311 bool meet_with_1 (const value_range
*other_vr
);
314 /* Structure containing lattices for a parameter itself and for pieces of
315 aggregates that are passed in the parameter or by a reference in a parameter
316 plus some other useful flags. */
318 class ipcp_param_lattices
321 /* Lattice describing the value of the parameter itself. */
322 ipcp_lattice
<tree
> itself
;
323 /* Lattice describing the polymorphic contexts of a parameter. */
324 ipcp_lattice
<ipa_polymorphic_call_context
> ctxlat
;
325 /* Lattices describing aggregate parts. */
326 ipcp_agg_lattice
*aggs
;
327 /* Lattice describing known bits. */
328 ipcp_bits_lattice bits_lattice
;
329 /* Lattice describing value range. */
330 ipcp_vr_lattice m_value_range
;
331 /* Number of aggregate lattices */
333 /* True if aggregate data were passed by reference (as opposed to by
336 /* All aggregate lattices contain a variable component (in addition to
338 bool aggs_contain_variable
;
339 /* The value of all aggregate lattices is bottom (i.e. variable and unusable
340 for any propagation). */
343 /* There is a virtual call based on this parameter. */
347 /* Allocation pools for values and their sources in ipa-cp. */
349 object_allocator
<ipcp_value
<tree
> > ipcp_cst_values_pool
350 ("IPA-CP constant values");
352 object_allocator
<ipcp_value
<ipa_polymorphic_call_context
> >
353 ipcp_poly_ctx_values_pool ("IPA-CP polymorphic contexts");
355 object_allocator
<ipcp_value_source
<tree
> > ipcp_sources_pool
356 ("IPA-CP value sources");
358 object_allocator
<ipcp_agg_lattice
> ipcp_agg_lattice_pool
359 ("IPA_CP aggregate lattices");
361 /* Maximal count found in program. */
363 static gcov_type max_count
;
365 /* Original overall size of the program. */
367 static long overall_size
, max_new_size
;
369 /* Return the param lattices structure corresponding to the Ith formal
370 parameter of the function described by INFO. */
371 static inline struct ipcp_param_lattices
*
372 ipa_get_parm_lattices (struct ipa_node_params
*info
, int i
)
374 gcc_assert (i
>= 0 && i
< ipa_get_param_count (info
));
375 gcc_checking_assert (!info
->ipcp_orig_node
);
376 gcc_checking_assert (info
->lattices
);
377 return &(info
->lattices
[i
]);
380 /* Return the lattice corresponding to the scalar value of the Ith formal
381 parameter of the function described by INFO. */
382 static inline ipcp_lattice
<tree
> *
383 ipa_get_scalar_lat (struct ipa_node_params
*info
, int i
)
385 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
386 return &plats
->itself
;
389 /* Return the lattice corresponding to the scalar value of the Ith formal
390 parameter of the function described by INFO. */
391 static inline ipcp_lattice
<ipa_polymorphic_call_context
> *
392 ipa_get_poly_ctx_lat (struct ipa_node_params
*info
, int i
)
394 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
395 return &plats
->ctxlat
;
398 /* Return the lattice corresponding to the value range of the Ith formal
399 parameter of the function described by INFO. */
401 static inline ipcp_vr_lattice
*
402 ipa_get_vr_lat (struct ipa_node_params
*info
, int i
)
404 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
405 return &plats
->m_value_range
;
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
);
506 ipcp_bits_lattice::print (FILE *f
)
509 fprintf (f
, " Bits unknown (TOP)\n");
510 else if (bottom_p ())
511 fprintf (f
, " Bits unusable (BOTTOM)\n");
514 fprintf (f
, " Bits: value = "); print_hex (get_value (), f
);
515 fprintf (f
, ", mask = "); print_hex (get_mask (), f
);
520 /* Print value range lattice to F. */
523 ipcp_vr_lattice::print (FILE * f
)
525 dump_value_range (f
, &m_vr
);
528 /* Print all ipcp_lattices of all functions to F. */
531 print_all_lattices (FILE * f
, bool dump_sources
, bool dump_benefits
)
533 struct cgraph_node
*node
;
536 fprintf (f
, "\nLattices:\n");
537 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
539 struct ipa_node_params
*info
;
541 info
= IPA_NODE_REF (node
);
542 fprintf (f
, " Node: %s/%i:\n", node
->name (),
544 count
= ipa_get_param_count (info
);
545 for (i
= 0; i
< count
; i
++)
547 struct ipcp_agg_lattice
*aglat
;
548 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
549 fprintf (f
, " param [%d]: ", i
);
550 plats
->itself
.print (f
, dump_sources
, dump_benefits
);
551 fprintf (f
, " ctxs: ");
552 plats
->ctxlat
.print (f
, dump_sources
, dump_benefits
);
553 plats
->bits_lattice
.print (f
);
555 plats
->m_value_range
.print (f
);
557 if (plats
->virt_call
)
558 fprintf (f
, " virt_call flag set\n");
560 if (plats
->aggs_bottom
)
562 fprintf (f
, " AGGS BOTTOM\n");
565 if (plats
->aggs_contain_variable
)
566 fprintf (f
, " AGGS VARIABLE\n");
567 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
569 fprintf (f
, " %soffset " HOST_WIDE_INT_PRINT_DEC
": ",
570 plats
->aggs_by_ref
? "ref " : "", aglat
->offset
);
571 aglat
->print (f
, dump_sources
, dump_benefits
);
577 /* Determine whether it is at all technically possible to create clones of NODE
578 and store this information in the ipa_node_params structure associated
582 determine_versionability (struct cgraph_node
*node
,
583 struct ipa_node_params
*info
)
585 const char *reason
= NULL
;
587 /* There are a number of generic reasons functions cannot be versioned. We
588 also cannot remove parameters if there are type attributes such as fnspec
590 if (node
->alias
|| node
->thunk
.thunk_p
)
591 reason
= "alias or thunk";
592 else if (!node
->local
.versionable
)
593 reason
= "not a tree_versionable_function";
594 else if (node
->get_availability () <= AVAIL_INTERPOSABLE
)
595 reason
= "insufficient body availability";
596 else if (!opt_for_fn (node
->decl
, optimize
)
597 || !opt_for_fn (node
->decl
, flag_ipa_cp
))
598 reason
= "non-optimized function";
599 else if (lookup_attribute ("omp declare simd", DECL_ATTRIBUTES (node
->decl
)))
601 /* Ideally we should clone the SIMD clones themselves and create
602 vector copies of them, so IPA-cp and SIMD clones can happily
603 coexist, but that may not be worth the effort. */
604 reason
= "function has SIMD clones";
606 else if (lookup_attribute ("target_clones", DECL_ATTRIBUTES (node
->decl
)))
608 /* Ideally we should clone the target clones themselves and create
609 copies of them, so IPA-cp and target clones can happily
610 coexist, but that may not be worth the effort. */
611 reason
= "function target_clones attribute";
613 /* Don't clone decls local to a comdat group; it breaks and for C++
614 decloned constructors, inlining is always better anyway. */
615 else if (node
->comdat_local_p ())
616 reason
= "comdat-local function";
618 if (reason
&& dump_file
&& !node
->alias
&& !node
->thunk
.thunk_p
)
619 fprintf (dump_file
, "Function %s/%i is not versionable, reason: %s.\n",
620 node
->name (), node
->order
, reason
);
622 info
->versionable
= (reason
== NULL
);
625 /* Return true if it is at all technically possible to create clones of a
629 ipcp_versionable_function_p (struct cgraph_node
*node
)
631 return IPA_NODE_REF (node
)->versionable
;
634 /* Structure holding accumulated information about callers of a node. */
636 struct caller_statistics
639 int n_calls
, n_hot_calls
, freq_sum
;
642 /* Initialize fields of STAT to zeroes. */
645 init_caller_stats (struct caller_statistics
*stats
)
647 stats
->count_sum
= 0;
649 stats
->n_hot_calls
= 0;
653 /* Worker callback of cgraph_for_node_and_aliases accumulating statistics of
654 non-thunk incoming edges to NODE. */
657 gather_caller_stats (struct cgraph_node
*node
, void *data
)
659 struct caller_statistics
*stats
= (struct caller_statistics
*) data
;
660 struct cgraph_edge
*cs
;
662 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
663 if (!cs
->caller
->thunk
.thunk_p
)
665 stats
->count_sum
+= cs
->count
;
666 stats
->freq_sum
+= cs
->frequency
;
668 if (cs
->maybe_hot_p ())
669 stats
->n_hot_calls
++;
675 /* Return true if this NODE is viable candidate for cloning. */
678 ipcp_cloning_candidate_p (struct cgraph_node
*node
)
680 struct caller_statistics stats
;
682 gcc_checking_assert (node
->has_gimple_body_p ());
684 if (!opt_for_fn (node
->decl
, flag_ipa_cp_clone
))
687 fprintf (dump_file
, "Not considering %s for cloning; "
688 "-fipa-cp-clone disabled.\n",
693 if (node
->optimize_for_size_p ())
696 fprintf (dump_file
, "Not considering %s for cloning; "
697 "optimizing it for size.\n",
702 init_caller_stats (&stats
);
703 node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
, false);
705 if (inline_summaries
->get (node
)->self_size
< stats
.n_calls
)
708 fprintf (dump_file
, "Considering %s for cloning; code might shrink.\n",
713 /* When profile is available and function is hot, propagate into it even if
714 calls seems cold; constant propagation can improve function's speed
718 if (stats
.count_sum
> node
->count
* 90 / 100)
721 fprintf (dump_file
, "Considering %s for cloning; "
722 "usually called directly.\n",
727 if (!stats
.n_hot_calls
)
730 fprintf (dump_file
, "Not considering %s for cloning; no hot calls.\n",
735 fprintf (dump_file
, "Considering %s for cloning.\n",
740 template <typename valtype
>
741 class value_topo_info
744 /* Head of the linked list of topologically sorted values. */
745 ipcp_value
<valtype
> *values_topo
;
746 /* Stack for creating SCCs, represented by a linked list too. */
747 ipcp_value
<valtype
> *stack
;
748 /* Counter driving the algorithm in add_val_to_toposort. */
751 value_topo_info () : values_topo (NULL
), stack (NULL
), dfs_counter (0)
753 void add_val (ipcp_value
<valtype
> *cur_val
);
754 void propagate_effects ();
757 /* Arrays representing a topological ordering of call graph nodes and a stack
758 of nodes used during constant propagation and also data required to perform
759 topological sort of values and propagation of benefits in the determined
765 /* Array with obtained topological order of cgraph nodes. */
766 struct cgraph_node
**order
;
767 /* Stack of cgraph nodes used during propagation within SCC until all values
768 in the SCC stabilize. */
769 struct cgraph_node
**stack
;
770 int nnodes
, stack_top
;
772 value_topo_info
<tree
> constants
;
773 value_topo_info
<ipa_polymorphic_call_context
> contexts
;
775 ipa_topo_info () : order(NULL
), stack(NULL
), nnodes(0), stack_top(0),
780 /* Allocate the arrays in TOPO and topologically sort the nodes into order. */
783 build_toporder_info (struct ipa_topo_info
*topo
)
785 topo
->order
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
786 topo
->stack
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
788 gcc_checking_assert (topo
->stack_top
== 0);
789 topo
->nnodes
= ipa_reduced_postorder (topo
->order
, true, true, NULL
);
792 /* Free information about strongly connected components and the arrays in
796 free_toporder_info (struct ipa_topo_info
*topo
)
798 ipa_free_postorder_info ();
803 /* Add NODE to the stack in TOPO, unless it is already there. */
806 push_node_to_stack (struct ipa_topo_info
*topo
, struct cgraph_node
*node
)
808 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
809 if (info
->node_enqueued
)
811 info
->node_enqueued
= 1;
812 topo
->stack
[topo
->stack_top
++] = node
;
815 /* Pop a node from the stack in TOPO and return it or return NULL if the stack
818 static struct cgraph_node
*
819 pop_node_from_stack (struct ipa_topo_info
*topo
)
823 struct cgraph_node
*node
;
825 node
= topo
->stack
[topo
->stack_top
];
826 IPA_NODE_REF (node
)->node_enqueued
= 0;
833 /* Set lattice LAT to bottom and return true if it previously was not set as
836 template <typename valtype
>
838 ipcp_lattice
<valtype
>::set_to_bottom ()
845 /* Mark lattice as containing an unknown value and return true if it previously
846 was not marked as such. */
848 template <typename valtype
>
850 ipcp_lattice
<valtype
>::set_contains_variable ()
852 bool ret
= !contains_variable
;
853 contains_variable
= true;
857 /* Set all aggegate lattices in PLATS to bottom and return true if they were
858 not previously set as such. */
861 set_agg_lats_to_bottom (struct ipcp_param_lattices
*plats
)
863 bool ret
= !plats
->aggs_bottom
;
864 plats
->aggs_bottom
= true;
868 /* Mark all aggegate lattices in PLATS as containing an unknown value and
869 return true if they were not previously marked as such. */
872 set_agg_lats_contain_variable (struct ipcp_param_lattices
*plats
)
874 bool ret
= !plats
->aggs_contain_variable
;
875 plats
->aggs_contain_variable
= true;
880 ipcp_vr_lattice::meet_with (const ipcp_vr_lattice
&other
)
882 return meet_with_1 (&other
.m_vr
);
885 /* Meet the current value of the lattice with value ranfge described by VR
889 ipcp_vr_lattice::meet_with (const value_range
*p_vr
)
891 return meet_with_1 (p_vr
);
894 /* Meet the current value of the lattice with value ranfge described by
898 ipcp_vr_lattice::meet_with_1 (const value_range
*other_vr
)
900 tree min
= m_vr
.min
, max
= m_vr
.max
;
901 value_range_type type
= m_vr
.type
;
906 if (other_vr
->type
== VR_VARYING
)
907 return set_to_bottom ();
909 vrp_meet (&m_vr
, other_vr
);
910 if (type
!= m_vr
.type
918 /* Return true if value range information in the lattice is yet unknown. */
921 ipcp_vr_lattice::top_p () const
923 return m_vr
.type
== VR_UNDEFINED
;
926 /* Return true if value range information in the lattice is known to be
930 ipcp_vr_lattice::bottom_p () const
932 return m_vr
.type
== VR_VARYING
;
935 /* Set value range information in the lattice to bottom. Return true if it
936 previously was in a different state. */
939 ipcp_vr_lattice::set_to_bottom ()
941 if (m_vr
.type
== VR_VARYING
)
943 m_vr
.type
= VR_VARYING
;
947 /* Set lattice value to bottom, if it already isn't the case. */
950 ipcp_bits_lattice::set_to_bottom ()
954 m_lattice_val
= IPA_BITS_VARYING
;
960 /* Set to constant if it isn't already. Only meant to be called
961 when switching state from TOP. */
964 ipcp_bits_lattice::set_to_constant (widest_int value
, widest_int mask
)
966 gcc_assert (top_p ());
967 m_lattice_val
= IPA_BITS_CONSTANT
;
973 /* Convert operand to value, mask form. */
976 ipcp_bits_lattice::get_value_and_mask (tree operand
, widest_int
*valuep
, widest_int
*maskp
)
978 wide_int
get_nonzero_bits (const_tree
);
980 if (TREE_CODE (operand
) == INTEGER_CST
)
982 *valuep
= wi::to_widest (operand
);
992 /* Meet operation, similar to ccp_lattice_meet, we xor values
993 if this->value, value have different values at same bit positions, we want
994 to drop that bit to varying. Return true if mask is changed.
995 This function assumes that the lattice value is in CONSTANT state */
998 ipcp_bits_lattice::meet_with_1 (widest_int value
, widest_int mask
,
1001 gcc_assert (constant_p ());
1003 widest_int old_mask
= m_mask
;
1004 m_mask
= (m_mask
| mask
) | (m_value
^ value
);
1006 if (wi::sext (m_mask
, precision
) == -1)
1007 return set_to_bottom ();
1009 return m_mask
!= old_mask
;
1012 /* Meet the bits lattice with operand
1013 described by <value, mask, sgn, precision. */
1016 ipcp_bits_lattice::meet_with (widest_int value
, widest_int mask
,
1024 if (wi::sext (mask
, precision
) == -1)
1025 return set_to_bottom ();
1026 return set_to_constant (value
, mask
);
1029 return meet_with_1 (value
, mask
, precision
);
1032 /* Meet bits lattice with the result of bit_value_binop (other, operand)
1033 if code is binary operation or bit_value_unop (other) if code is unary op.
1034 In the case when code is nop_expr, no adjustment is required. */
1037 ipcp_bits_lattice::meet_with (ipcp_bits_lattice
& other
, unsigned precision
,
1038 signop sgn
, enum tree_code code
, tree operand
)
1040 if (other
.bottom_p ())
1041 return set_to_bottom ();
1043 if (bottom_p () || other
.top_p ())
1046 widest_int adjusted_value
, adjusted_mask
;
1048 if (TREE_CODE_CLASS (code
) == tcc_binary
)
1050 tree type
= TREE_TYPE (operand
);
1051 gcc_assert (INTEGRAL_TYPE_P (type
));
1052 widest_int o_value
, o_mask
;
1053 get_value_and_mask (operand
, &o_value
, &o_mask
);
1055 bit_value_binop (code
, sgn
, precision
, &adjusted_value
, &adjusted_mask
,
1056 sgn
, precision
, other
.get_value (), other
.get_mask (),
1057 TYPE_SIGN (type
), TYPE_PRECISION (type
), o_value
, o_mask
);
1059 if (wi::sext (adjusted_mask
, precision
) == -1)
1060 return set_to_bottom ();
1063 else if (TREE_CODE_CLASS (code
) == tcc_unary
)
1065 bit_value_unop (code
, sgn
, precision
, &adjusted_value
,
1066 &adjusted_mask
, sgn
, precision
, other
.get_value (),
1069 if (wi::sext (adjusted_mask
, precision
) == -1)
1070 return set_to_bottom ();
1074 return set_to_bottom ();
1078 if (wi::sext (adjusted_mask
, precision
) == -1)
1079 return set_to_bottom ();
1080 return set_to_constant (adjusted_value
, adjusted_mask
);
1083 return meet_with_1 (adjusted_value
, adjusted_mask
, precision
);
1086 /* Mark bot aggregate and scalar lattices as containing an unknown variable,
1087 return true is any of them has not been marked as such so far. */
1090 set_all_contains_variable (struct ipcp_param_lattices
*plats
)
1093 ret
= plats
->itself
.set_contains_variable ();
1094 ret
|= plats
->ctxlat
.set_contains_variable ();
1095 ret
|= set_agg_lats_contain_variable (plats
);
1096 ret
|= plats
->bits_lattice
.set_to_bottom ();
1097 ret
|= plats
->m_value_range
.set_to_bottom ();
1101 /* Worker of call_for_symbol_thunks_and_aliases, increment the integer DATA
1102 points to by the number of callers to NODE. */
1105 count_callers (cgraph_node
*node
, void *data
)
1107 int *caller_count
= (int *) data
;
1109 for (cgraph_edge
*cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
1110 /* Local thunks can be handled transparently, but if the thunk can not
1111 be optimized out, count it as a real use. */
1112 if (!cs
->caller
->thunk
.thunk_p
|| !cs
->caller
->local
.local
)
1117 /* Worker of call_for_symbol_thunks_and_aliases, it is supposed to be called on
1118 the one caller of some other node. Set the caller's corresponding flag. */
1121 set_single_call_flag (cgraph_node
*node
, void *)
1123 cgraph_edge
*cs
= node
->callers
;
1124 /* Local thunks can be handled transparently, skip them. */
1125 while (cs
&& cs
->caller
->thunk
.thunk_p
&& cs
->caller
->local
.local
)
1126 cs
= cs
->next_caller
;
1129 IPA_NODE_REF (cs
->caller
)->node_calling_single_call
= true;
1135 /* Initialize ipcp_lattices. */
1138 initialize_node_lattices (struct cgraph_node
*node
)
1140 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1141 struct cgraph_edge
*ie
;
1142 bool disable
= false, variable
= false;
1145 gcc_checking_assert (node
->has_gimple_body_p ());
1146 if (cgraph_local_p (node
))
1148 int caller_count
= 0;
1149 node
->call_for_symbol_thunks_and_aliases (count_callers
, &caller_count
,
1151 gcc_checking_assert (caller_count
> 0);
1152 if (caller_count
== 1)
1153 node
->call_for_symbol_thunks_and_aliases (set_single_call_flag
,
1158 /* When cloning is allowed, we can assume that externally visible
1159 functions are not called. We will compensate this by cloning
1161 if (ipcp_versionable_function_p (node
)
1162 && ipcp_cloning_candidate_p (node
))
1168 for (i
= 0; i
< ipa_get_param_count (info
) ; i
++)
1170 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1171 plats
->m_value_range
.init ();
1174 if (disable
|| variable
)
1176 for (i
= 0; i
< ipa_get_param_count (info
) ; i
++)
1178 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
1181 plats
->itself
.set_to_bottom ();
1182 plats
->ctxlat
.set_to_bottom ();
1183 set_agg_lats_to_bottom (plats
);
1184 plats
->bits_lattice
.set_to_bottom ();
1185 plats
->m_value_range
.set_to_bottom ();
1188 set_all_contains_variable (plats
);
1190 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1191 && !node
->alias
&& !node
->thunk
.thunk_p
)
1192 fprintf (dump_file
, "Marking all lattices of %s/%i as %s\n",
1193 node
->name (), node
->order
,
1194 disable
? "BOTTOM" : "VARIABLE");
1197 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
1198 if (ie
->indirect_info
->polymorphic
1199 && ie
->indirect_info
->param_index
>= 0)
1201 gcc_checking_assert (ie
->indirect_info
->param_index
>= 0);
1202 ipa_get_parm_lattices (info
,
1203 ie
->indirect_info
->param_index
)->virt_call
= 1;
1207 /* Return the result of a (possibly arithmetic) pass through jump function
1208 JFUNC on the constant value INPUT. Return NULL_TREE if that cannot be
1209 determined or be considered an interprocedural invariant. */
1212 ipa_get_jf_pass_through_result (struct ipa_jump_func
*jfunc
, tree input
)
1216 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
1218 if (!is_gimple_ip_invariant (input
))
1221 if (TREE_CODE_CLASS (ipa_get_jf_pass_through_operation (jfunc
))
1223 restype
= boolean_type_node
;
1225 restype
= TREE_TYPE (input
);
1226 res
= fold_binary (ipa_get_jf_pass_through_operation (jfunc
), restype
,
1227 input
, ipa_get_jf_pass_through_operand (jfunc
));
1229 if (res
&& !is_gimple_ip_invariant (res
))
1235 /* Return the result of an ancestor jump function JFUNC on the constant value
1236 INPUT. Return NULL_TREE if that cannot be determined. */
1239 ipa_get_jf_ancestor_result (struct ipa_jump_func
*jfunc
, tree input
)
1241 gcc_checking_assert (TREE_CODE (input
) != TREE_BINFO
);
1242 if (TREE_CODE (input
) == ADDR_EXPR
)
1244 tree t
= TREE_OPERAND (input
, 0);
1245 t
= build_ref_for_offset (EXPR_LOCATION (t
), t
,
1246 ipa_get_jf_ancestor_offset (jfunc
), false,
1247 ptr_type_node
, NULL
, false);
1248 return build_fold_addr_expr (t
);
1254 /* Determine whether JFUNC evaluates to a single known constant value and if
1255 so, return it. Otherwise return NULL. INFO describes the caller node or
1256 the one it is inlined to, so that pass-through jump functions can be
1260 ipa_value_from_jfunc (struct ipa_node_params
*info
, struct ipa_jump_func
*jfunc
)
1262 if (jfunc
->type
== IPA_JF_CONST
)
1263 return ipa_get_jf_constant (jfunc
);
1264 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1265 || jfunc
->type
== IPA_JF_ANCESTOR
)
1270 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1271 idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1273 idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1275 if (info
->ipcp_orig_node
)
1276 input
= info
->known_csts
[idx
];
1279 ipcp_lattice
<tree
> *lat
;
1282 || idx
>= ipa_get_param_count (info
))
1284 lat
= ipa_get_scalar_lat (info
, idx
);
1285 if (!lat
->is_single_const ())
1287 input
= lat
->values
->value
;
1293 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1294 return ipa_get_jf_pass_through_result (jfunc
, input
);
1296 return ipa_get_jf_ancestor_result (jfunc
, input
);
1302 /* Determie whether JFUNC evaluates to single known polymorphic context, given
1303 that INFO describes the caller node or the one it is inlined to, CS is the
1304 call graph edge corresponding to JFUNC and CSIDX index of the described
1307 ipa_polymorphic_call_context
1308 ipa_context_from_jfunc (ipa_node_params
*info
, cgraph_edge
*cs
, int csidx
,
1309 ipa_jump_func
*jfunc
)
1311 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
1312 ipa_polymorphic_call_context ctx
;
1313 ipa_polymorphic_call_context
*edge_ctx
1314 = cs
? ipa_get_ith_polymorhic_call_context (args
, csidx
) : NULL
;
1316 if (edge_ctx
&& !edge_ctx
->useless_p ())
1319 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1320 || jfunc
->type
== IPA_JF_ANCESTOR
)
1322 ipa_polymorphic_call_context srcctx
;
1324 bool type_preserved
= true;
1325 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1327 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1329 type_preserved
= ipa_get_jf_pass_through_type_preserved (jfunc
);
1330 srcidx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1334 type_preserved
= ipa_get_jf_ancestor_type_preserved (jfunc
);
1335 srcidx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1337 if (info
->ipcp_orig_node
)
1339 if (info
->known_contexts
.exists ())
1340 srcctx
= info
->known_contexts
[srcidx
];
1345 || srcidx
>= ipa_get_param_count (info
))
1347 ipcp_lattice
<ipa_polymorphic_call_context
> *lat
;
1348 lat
= ipa_get_poly_ctx_lat (info
, srcidx
);
1349 if (!lat
->is_single_const ())
1351 srcctx
= lat
->values
->value
;
1353 if (srcctx
.useless_p ())
1355 if (jfunc
->type
== IPA_JF_ANCESTOR
)
1356 srcctx
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
1357 if (!type_preserved
)
1358 srcctx
.possible_dynamic_type_change (cs
->in_polymorphic_cdtor
);
1359 srcctx
.combine_with (ctx
);
1366 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
1367 bottom, not containing a variable component and without any known value at
1371 ipcp_verify_propagated_values (void)
1373 struct cgraph_node
*node
;
1375 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
1377 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1378 int i
, count
= ipa_get_param_count (info
);
1380 for (i
= 0; i
< count
; i
++)
1382 ipcp_lattice
<tree
> *lat
= ipa_get_scalar_lat (info
, i
);
1385 && !lat
->contains_variable
1386 && lat
->values_count
== 0)
1390 symtab_node::dump_table (dump_file
);
1391 fprintf (dump_file
, "\nIPA lattices after constant "
1392 "propagation, before gcc_unreachable:\n");
1393 print_all_lattices (dump_file
, true, false);
1402 /* Return true iff X and Y should be considered equal values by IPA-CP. */
1405 values_equal_for_ipcp_p (tree x
, tree y
)
1407 gcc_checking_assert (x
!= NULL_TREE
&& y
!= NULL_TREE
);
1412 if (TREE_CODE (x
) == ADDR_EXPR
1413 && TREE_CODE (y
) == ADDR_EXPR
1414 && TREE_CODE (TREE_OPERAND (x
, 0)) == CONST_DECL
1415 && TREE_CODE (TREE_OPERAND (y
, 0)) == CONST_DECL
)
1416 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x
, 0)),
1417 DECL_INITIAL (TREE_OPERAND (y
, 0)), 0);
1419 return operand_equal_p (x
, y
, 0);
1422 /* Return true iff X and Y should be considered equal contexts by IPA-CP. */
1425 values_equal_for_ipcp_p (ipa_polymorphic_call_context x
,
1426 ipa_polymorphic_call_context y
)
1428 return x
.equal_to (y
);
1432 /* Add a new value source to the value represented by THIS, marking that a
1433 value comes from edge CS and (if the underlying jump function is a
1434 pass-through or an ancestor one) from a caller value SRC_VAL of a caller
1435 parameter described by SRC_INDEX. OFFSET is negative if the source was the
1436 scalar value of the parameter itself or the offset within an aggregate. */
1438 template <typename valtype
>
1440 ipcp_value
<valtype
>::add_source (cgraph_edge
*cs
, ipcp_value
*src_val
,
1441 int src_idx
, HOST_WIDE_INT offset
)
1443 ipcp_value_source
<valtype
> *src
;
1445 src
= new (ipcp_sources_pool
.allocate ()) ipcp_value_source
<valtype
>;
1446 src
->offset
= offset
;
1449 src
->index
= src_idx
;
1451 src
->next
= sources
;
1455 /* Allocate a new ipcp_value holding a tree constant, initialize its value to
1456 SOURCE and clear all other fields. */
1458 static ipcp_value
<tree
> *
1459 allocate_and_init_ipcp_value (tree source
)
1461 ipcp_value
<tree
> *val
;
1463 val
= ipcp_cst_values_pool
.allocate ();
1464 memset (val
, 0, sizeof (*val
));
1465 val
->value
= source
;
1469 /* Allocate a new ipcp_value holding a polymorphic context, initialize its
1470 value to SOURCE and clear all other fields. */
1472 static ipcp_value
<ipa_polymorphic_call_context
> *
1473 allocate_and_init_ipcp_value (ipa_polymorphic_call_context source
)
1475 ipcp_value
<ipa_polymorphic_call_context
> *val
;
1478 val
= ipcp_poly_ctx_values_pool
.allocate ();
1479 memset (val
, 0, sizeof (*val
));
1480 val
->value
= source
;
1484 /* Try to add NEWVAL to LAT, potentially creating a new ipcp_value for it. CS,
1485 SRC_VAL SRC_INDEX and OFFSET are meant for add_source and have the same
1486 meaning. OFFSET -1 means the source is scalar and not a part of an
1489 template <typename valtype
>
1491 ipcp_lattice
<valtype
>::add_value (valtype newval
, cgraph_edge
*cs
,
1492 ipcp_value
<valtype
> *src_val
,
1493 int src_idx
, HOST_WIDE_INT offset
)
1495 ipcp_value
<valtype
> *val
;
1500 for (val
= values
; val
; val
= val
->next
)
1501 if (values_equal_for_ipcp_p (val
->value
, newval
))
1503 if (ipa_edge_within_scc (cs
))
1505 ipcp_value_source
<valtype
> *s
;
1506 for (s
= val
->sources
; s
; s
= s
->next
)
1513 val
->add_source (cs
, src_val
, src_idx
, offset
);
1517 if (values_count
== PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE
))
1519 /* We can only free sources, not the values themselves, because sources
1520 of other values in this SCC might point to them. */
1521 for (val
= values
; val
; val
= val
->next
)
1523 while (val
->sources
)
1525 ipcp_value_source
<valtype
> *src
= val
->sources
;
1526 val
->sources
= src
->next
;
1527 ipcp_sources_pool
.remove ((ipcp_value_source
<tree
>*)src
);
1532 return set_to_bottom ();
1536 val
= allocate_and_init_ipcp_value (newval
);
1537 val
->add_source (cs
, src_val
, src_idx
, offset
);
1543 /* Propagate values through a pass-through jump function JFUNC associated with
1544 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1545 is the index of the source parameter. */
1548 propagate_vals_accross_pass_through (cgraph_edge
*cs
,
1549 ipa_jump_func
*jfunc
,
1550 ipcp_lattice
<tree
> *src_lat
,
1551 ipcp_lattice
<tree
> *dest_lat
,
1554 ipcp_value
<tree
> *src_val
;
1557 /* Do not create new values when propagating within an SCC because if there
1558 are arithmetic functions with circular dependencies, there is infinite
1559 number of them and we would just make lattices bottom. */
1560 if ((ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1561 && ipa_edge_within_scc (cs
))
1562 ret
= dest_lat
->set_contains_variable ();
1564 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1566 tree cstval
= ipa_get_jf_pass_through_result (jfunc
, src_val
->value
);
1569 ret
|= dest_lat
->add_value (cstval
, cs
, src_val
, src_idx
);
1571 ret
|= dest_lat
->set_contains_variable ();
1577 /* Propagate values through an ancestor jump function JFUNC associated with
1578 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1579 is the index of the source parameter. */
1582 propagate_vals_accross_ancestor (struct cgraph_edge
*cs
,
1583 struct ipa_jump_func
*jfunc
,
1584 ipcp_lattice
<tree
> *src_lat
,
1585 ipcp_lattice
<tree
> *dest_lat
,
1588 ipcp_value
<tree
> *src_val
;
1591 if (ipa_edge_within_scc (cs
))
1592 return dest_lat
->set_contains_variable ();
1594 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1596 tree t
= ipa_get_jf_ancestor_result (jfunc
, src_val
->value
);
1599 ret
|= dest_lat
->add_value (t
, cs
, src_val
, src_idx
);
1601 ret
|= dest_lat
->set_contains_variable ();
1607 /* Propagate scalar values across jump function JFUNC that is associated with
1608 edge CS and put the values into DEST_LAT. */
1611 propagate_scalar_accross_jump_function (struct cgraph_edge
*cs
,
1612 struct ipa_jump_func
*jfunc
,
1613 ipcp_lattice
<tree
> *dest_lat
)
1615 if (dest_lat
->bottom
)
1618 if (jfunc
->type
== IPA_JF_CONST
)
1620 tree val
= ipa_get_jf_constant (jfunc
);
1621 return dest_lat
->add_value (val
, cs
, NULL
, 0);
1623 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1624 || jfunc
->type
== IPA_JF_ANCESTOR
)
1626 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1627 ipcp_lattice
<tree
> *src_lat
;
1631 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1632 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1634 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1636 src_lat
= ipa_get_scalar_lat (caller_info
, src_idx
);
1637 if (src_lat
->bottom
)
1638 return dest_lat
->set_contains_variable ();
1640 /* If we would need to clone the caller and cannot, do not propagate. */
1641 if (!ipcp_versionable_function_p (cs
->caller
)
1642 && (src_lat
->contains_variable
1643 || (src_lat
->values_count
> 1)))
1644 return dest_lat
->set_contains_variable ();
1646 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1647 ret
= propagate_vals_accross_pass_through (cs
, jfunc
, src_lat
,
1650 ret
= propagate_vals_accross_ancestor (cs
, jfunc
, src_lat
, dest_lat
,
1653 if (src_lat
->contains_variable
)
1654 ret
|= dest_lat
->set_contains_variable ();
1659 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1660 use it for indirect inlining), we should propagate them too. */
1661 return dest_lat
->set_contains_variable ();
1664 /* Propagate scalar values across jump function JFUNC that is associated with
1665 edge CS and describes argument IDX and put the values into DEST_LAT. */
1668 propagate_context_accross_jump_function (cgraph_edge
*cs
,
1669 ipa_jump_func
*jfunc
, int idx
,
1670 ipcp_lattice
<ipa_polymorphic_call_context
> *dest_lat
)
1672 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
1673 if (dest_lat
->bottom
)
1676 bool added_sth
= false;
1677 bool type_preserved
= true;
1679 ipa_polymorphic_call_context edge_ctx
, *edge_ctx_ptr
1680 = ipa_get_ith_polymorhic_call_context (args
, idx
);
1683 edge_ctx
= *edge_ctx_ptr
;
1685 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1686 || jfunc
->type
== IPA_JF_ANCESTOR
)
1688 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1690 ipcp_lattice
<ipa_polymorphic_call_context
> *src_lat
;
1692 /* TODO: Once we figure out how to propagate speculations, it will
1693 probably be a good idea to switch to speculation if type_preserved is
1694 not set instead of punting. */
1695 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1697 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1699 type_preserved
= ipa_get_jf_pass_through_type_preserved (jfunc
);
1700 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1704 type_preserved
= ipa_get_jf_ancestor_type_preserved (jfunc
);
1705 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1708 src_lat
= ipa_get_poly_ctx_lat (caller_info
, src_idx
);
1709 /* If we would need to clone the caller and cannot, do not propagate. */
1710 if (!ipcp_versionable_function_p (cs
->caller
)
1711 && (src_lat
->contains_variable
1712 || (src_lat
->values_count
> 1)))
1715 ipcp_value
<ipa_polymorphic_call_context
> *src_val
;
1716 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1718 ipa_polymorphic_call_context cur
= src_val
->value
;
1720 if (!type_preserved
)
1721 cur
.possible_dynamic_type_change (cs
->in_polymorphic_cdtor
);
1722 if (jfunc
->type
== IPA_JF_ANCESTOR
)
1723 cur
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
1724 /* TODO: In cases we know how the context is going to be used,
1725 we can improve the result by passing proper OTR_TYPE. */
1726 cur
.combine_with (edge_ctx
);
1727 if (!cur
.useless_p ())
1729 if (src_lat
->contains_variable
1730 && !edge_ctx
.equal_to (cur
))
1731 ret
|= dest_lat
->set_contains_variable ();
1732 ret
|= dest_lat
->add_value (cur
, cs
, src_val
, src_idx
);
1742 if (!edge_ctx
.useless_p ())
1743 ret
|= dest_lat
->add_value (edge_ctx
, cs
);
1745 ret
|= dest_lat
->set_contains_variable ();
1751 /* Propagate bits across jfunc that is associated with
1752 edge cs and update dest_lattice accordingly. */
1755 propagate_bits_accross_jump_function (cgraph_edge
*cs
, int idx
, ipa_jump_func
*jfunc
,
1756 ipcp_bits_lattice
*dest_lattice
)
1758 if (dest_lattice
->bottom_p ())
1761 enum availability availability
;
1762 cgraph_node
*callee
= cs
->callee
->function_symbol (&availability
);
1763 struct ipa_node_params
*callee_info
= IPA_NODE_REF (callee
);
1764 tree parm_type
= ipa_get_type (callee_info
, idx
);
1766 /* For K&R C programs, ipa_get_type() could return NULL_TREE.
1767 Avoid the transform for these cases. */
1770 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1771 fprintf (dump_file
, "Setting dest_lattice to bottom, because"
1772 " param %i type is NULL for %s\n", idx
,
1773 cs
->callee
->name ());
1775 return dest_lattice
->set_to_bottom ();
1778 unsigned precision
= TYPE_PRECISION (parm_type
);
1779 signop sgn
= TYPE_SIGN (parm_type
);
1781 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1782 || jfunc
->type
== IPA_JF_ANCESTOR
)
1784 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1785 tree operand
= NULL_TREE
;
1786 enum tree_code code
;
1789 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1791 code
= ipa_get_jf_pass_through_operation (jfunc
);
1792 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1793 if (code
!= NOP_EXPR
)
1794 operand
= ipa_get_jf_pass_through_operand (jfunc
);
1798 code
= POINTER_PLUS_EXPR
;
1799 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1800 unsigned HOST_WIDE_INT offset
= ipa_get_jf_ancestor_offset (jfunc
) / BITS_PER_UNIT
;
1801 operand
= build_int_cstu (size_type_node
, offset
);
1804 struct ipcp_param_lattices
*src_lats
1805 = ipa_get_parm_lattices (caller_info
, src_idx
);
1807 /* Try to propagate bits if src_lattice is bottom, but jfunc is known.
1813 Assume lattice for x is bottom, however we can still propagate
1814 result of x & 0xff == 0xff, which gets computed during ccp1 pass
1815 and we store it in jump function during analysis stage. */
1817 if (src_lats
->bits_lattice
.bottom_p ()
1818 && jfunc
->bits
.known
)
1819 return dest_lattice
->meet_with (jfunc
->bits
.value
, jfunc
->bits
.mask
,
1822 return dest_lattice
->meet_with (src_lats
->bits_lattice
, precision
, sgn
,
1826 else if (jfunc
->type
== IPA_JF_ANCESTOR
)
1827 return dest_lattice
->set_to_bottom ();
1829 else if (jfunc
->bits
.known
)
1830 return dest_lattice
->meet_with (jfunc
->bits
.value
, jfunc
->bits
.mask
, precision
);
1833 return dest_lattice
->set_to_bottom ();
1836 /* Propagate value range across jump function JFUNC that is associated with
1837 edge CS and update DEST_PLATS accordingly. */
1840 propagate_vr_accross_jump_function (cgraph_edge
*cs
,
1841 ipa_jump_func
*jfunc
,
1842 struct ipcp_param_lattices
*dest_plats
)
1844 struct ipcp_param_lattices
*src_lats
;
1845 ipcp_vr_lattice
*dest_lat
= &dest_plats
->m_value_range
;
1847 if (dest_lat
->bottom_p ())
1850 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1852 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1853 if (dest_lat
->bottom_p ())
1855 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1856 src_lats
= ipa_get_parm_lattices (caller_info
, src_idx
);
1858 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
1859 return dest_lat
->meet_with (src_lats
->m_value_range
);
1861 else if (jfunc
->type
== IPA_JF_CONST
)
1863 tree val
= ipa_get_jf_constant (jfunc
);
1864 if (TREE_CODE (val
) == INTEGER_CST
)
1866 if (TREE_OVERFLOW_P (val
))
1867 val
= drop_tree_overflow (val
);
1868 jfunc
->vr_known
= true;
1869 jfunc
->m_vr
.type
= VR_RANGE
;
1870 jfunc
->m_vr
.min
= val
;
1871 jfunc
->m_vr
.max
= val
;
1872 return dest_lat
->meet_with (&jfunc
->m_vr
);
1876 if (jfunc
->vr_known
)
1877 return dest_lat
->meet_with (&jfunc
->m_vr
);
1879 return dest_lat
->set_to_bottom ();
1882 /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
1883 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
1884 other cases, return false). If there are no aggregate items, set
1885 aggs_by_ref to NEW_AGGS_BY_REF. */
1888 set_check_aggs_by_ref (struct ipcp_param_lattices
*dest_plats
,
1889 bool new_aggs_by_ref
)
1891 if (dest_plats
->aggs
)
1893 if (dest_plats
->aggs_by_ref
!= new_aggs_by_ref
)
1895 set_agg_lats_to_bottom (dest_plats
);
1900 dest_plats
->aggs_by_ref
= new_aggs_by_ref
;
1904 /* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
1905 already existing lattice for the given OFFSET and SIZE, marking all skipped
1906 lattices as containing variable and checking for overlaps. If there is no
1907 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
1908 it with offset, size and contains_variable to PRE_EXISTING, and return true,
1909 unless there are too many already. If there are two many, return false. If
1910 there are overlaps turn whole DEST_PLATS to bottom and return false. If any
1911 skipped lattices were newly marked as containing variable, set *CHANGE to
1915 merge_agg_lats_step (struct ipcp_param_lattices
*dest_plats
,
1916 HOST_WIDE_INT offset
, HOST_WIDE_INT val_size
,
1917 struct ipcp_agg_lattice
***aglat
,
1918 bool pre_existing
, bool *change
)
1920 gcc_checking_assert (offset
>= 0);
1922 while (**aglat
&& (**aglat
)->offset
< offset
)
1924 if ((**aglat
)->offset
+ (**aglat
)->size
> offset
)
1926 set_agg_lats_to_bottom (dest_plats
);
1929 *change
|= (**aglat
)->set_contains_variable ();
1930 *aglat
= &(**aglat
)->next
;
1933 if (**aglat
&& (**aglat
)->offset
== offset
)
1935 if ((**aglat
)->size
!= val_size
1937 && (**aglat
)->next
->offset
< offset
+ val_size
))
1939 set_agg_lats_to_bottom (dest_plats
);
1942 gcc_checking_assert (!(**aglat
)->next
1943 || (**aglat
)->next
->offset
>= offset
+ val_size
);
1948 struct ipcp_agg_lattice
*new_al
;
1950 if (**aglat
&& (**aglat
)->offset
< offset
+ val_size
)
1952 set_agg_lats_to_bottom (dest_plats
);
1955 if (dest_plats
->aggs_count
== PARAM_VALUE (PARAM_IPA_MAX_AGG_ITEMS
))
1957 dest_plats
->aggs_count
++;
1958 new_al
= ipcp_agg_lattice_pool
.allocate ();
1959 memset (new_al
, 0, sizeof (*new_al
));
1961 new_al
->offset
= offset
;
1962 new_al
->size
= val_size
;
1963 new_al
->contains_variable
= pre_existing
;
1965 new_al
->next
= **aglat
;
1971 /* Set all AGLAT and all other aggregate lattices reachable by next pointers as
1972 containing an unknown value. */
1975 set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice
*aglat
)
1980 ret
|= aglat
->set_contains_variable ();
1981 aglat
= aglat
->next
;
1986 /* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
1987 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source
1988 parameter used for lattice value sources. Return true if DEST_PLATS changed
1992 merge_aggregate_lattices (struct cgraph_edge
*cs
,
1993 struct ipcp_param_lattices
*dest_plats
,
1994 struct ipcp_param_lattices
*src_plats
,
1995 int src_idx
, HOST_WIDE_INT offset_delta
)
1997 bool pre_existing
= dest_plats
->aggs
!= NULL
;
1998 struct ipcp_agg_lattice
**dst_aglat
;
2001 if (set_check_aggs_by_ref (dest_plats
, src_plats
->aggs_by_ref
))
2003 if (src_plats
->aggs_bottom
)
2004 return set_agg_lats_contain_variable (dest_plats
);
2005 if (src_plats
->aggs_contain_variable
)
2006 ret
|= set_agg_lats_contain_variable (dest_plats
);
2007 dst_aglat
= &dest_plats
->aggs
;
2009 for (struct ipcp_agg_lattice
*src_aglat
= src_plats
->aggs
;
2011 src_aglat
= src_aglat
->next
)
2013 HOST_WIDE_INT new_offset
= src_aglat
->offset
- offset_delta
;
2017 if (merge_agg_lats_step (dest_plats
, new_offset
, src_aglat
->size
,
2018 &dst_aglat
, pre_existing
, &ret
))
2020 struct ipcp_agg_lattice
*new_al
= *dst_aglat
;
2022 dst_aglat
= &(*dst_aglat
)->next
;
2023 if (src_aglat
->bottom
)
2025 ret
|= new_al
->set_contains_variable ();
2028 if (src_aglat
->contains_variable
)
2029 ret
|= new_al
->set_contains_variable ();
2030 for (ipcp_value
<tree
> *val
= src_aglat
->values
;
2033 ret
|= new_al
->add_value (val
->value
, cs
, val
, src_idx
,
2036 else if (dest_plats
->aggs_bottom
)
2039 ret
|= set_chain_of_aglats_contains_variable (*dst_aglat
);
2043 /* Determine whether there is anything to propagate FROM SRC_PLATS through a
2044 pass-through JFUNC and if so, whether it has conform and conforms to the
2045 rules about propagating values passed by reference. */
2048 agg_pass_through_permissible_p (struct ipcp_param_lattices
*src_plats
,
2049 struct ipa_jump_func
*jfunc
)
2051 return src_plats
->aggs
2052 && (!src_plats
->aggs_by_ref
2053 || ipa_get_jf_pass_through_agg_preserved (jfunc
));
2056 /* Propagate scalar values across jump function JFUNC that is associated with
2057 edge CS and put the values into DEST_LAT. */
2060 propagate_aggs_accross_jump_function (struct cgraph_edge
*cs
,
2061 struct ipa_jump_func
*jfunc
,
2062 struct ipcp_param_lattices
*dest_plats
)
2066 if (dest_plats
->aggs_bottom
)
2069 if (jfunc
->type
== IPA_JF_PASS_THROUGH
2070 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
2072 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2073 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
2074 struct ipcp_param_lattices
*src_plats
;
2076 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2077 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
2079 /* Currently we do not produce clobber aggregate jump
2080 functions, replace with merging when we do. */
2081 gcc_assert (!jfunc
->agg
.items
);
2082 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
,
2086 ret
|= set_agg_lats_contain_variable (dest_plats
);
2088 else if (jfunc
->type
== IPA_JF_ANCESTOR
2089 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
2091 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2092 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
2093 struct ipcp_param_lattices
*src_plats
;
2095 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2096 if (src_plats
->aggs
&& src_plats
->aggs_by_ref
)
2098 /* Currently we do not produce clobber aggregate jump
2099 functions, replace with merging when we do. */
2100 gcc_assert (!jfunc
->agg
.items
);
2101 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
, src_idx
,
2102 ipa_get_jf_ancestor_offset (jfunc
));
2104 else if (!src_plats
->aggs_by_ref
)
2105 ret
|= set_agg_lats_to_bottom (dest_plats
);
2107 ret
|= set_agg_lats_contain_variable (dest_plats
);
2109 else if (jfunc
->agg
.items
)
2111 bool pre_existing
= dest_plats
->aggs
!= NULL
;
2112 struct ipcp_agg_lattice
**aglat
= &dest_plats
->aggs
;
2113 struct ipa_agg_jf_item
*item
;
2116 if (set_check_aggs_by_ref (dest_plats
, jfunc
->agg
.by_ref
))
2119 FOR_EACH_VEC_ELT (*jfunc
->agg
.items
, i
, item
)
2121 HOST_WIDE_INT val_size
;
2123 if (item
->offset
< 0)
2125 gcc_checking_assert (is_gimple_ip_invariant (item
->value
));
2126 val_size
= tree_to_uhwi (TYPE_SIZE (TREE_TYPE (item
->value
)));
2128 if (merge_agg_lats_step (dest_plats
, item
->offset
, val_size
,
2129 &aglat
, pre_existing
, &ret
))
2131 ret
|= (*aglat
)->add_value (item
->value
, cs
, NULL
, 0, 0);
2132 aglat
= &(*aglat
)->next
;
2134 else if (dest_plats
->aggs_bottom
)
2138 ret
|= set_chain_of_aglats_contains_variable (*aglat
);
2141 ret
|= set_agg_lats_contain_variable (dest_plats
);
2146 /* Return true if on the way cfrom CS->caller to the final (non-alias and
2147 non-thunk) destination, the call passes through a thunk. */
2150 call_passes_through_thunk_p (cgraph_edge
*cs
)
2152 cgraph_node
*alias_or_thunk
= cs
->callee
;
2153 while (alias_or_thunk
->alias
)
2154 alias_or_thunk
= alias_or_thunk
->get_alias_target ();
2155 return alias_or_thunk
->thunk
.thunk_p
;
2158 /* Propagate constants from the caller to the callee of CS. INFO describes the
2162 propagate_constants_accross_call (struct cgraph_edge
*cs
)
2164 struct ipa_node_params
*callee_info
;
2165 enum availability availability
;
2166 cgraph_node
*callee
;
2167 struct ipa_edge_args
*args
;
2169 int i
, args_count
, parms_count
;
2171 callee
= cs
->callee
->function_symbol (&availability
);
2172 if (!callee
->definition
)
2174 gcc_checking_assert (callee
->has_gimple_body_p ());
2175 callee_info
= IPA_NODE_REF (callee
);
2177 args
= IPA_EDGE_REF (cs
);
2178 args_count
= ipa_get_cs_argument_count (args
);
2179 parms_count
= ipa_get_param_count (callee_info
);
2180 if (parms_count
== 0)
2183 /* No propagation through instrumentation thunks is available yet.
2184 It should be possible with proper mapping of call args and
2185 instrumented callee params in the propagation loop below. But
2186 this case mostly occurs when legacy code calls instrumented code
2187 and it is not a primary target for optimizations.
2188 We detect instrumentation thunks in aliases and thunks chain by
2189 checking instrumentation_clone flag for chain source and target.
2190 Going through instrumentation thunks we always have it changed
2191 from 0 to 1 and all other nodes do not change it. */
2192 if (!cs
->callee
->instrumentation_clone
2193 && callee
->instrumentation_clone
)
2195 for (i
= 0; i
< parms_count
; i
++)
2196 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
2201 /* If this call goes through a thunk we must not propagate to the first (0th)
2202 parameter. However, we might need to uncover a thunk from below a series
2203 of aliases first. */
2204 if (call_passes_through_thunk_p (cs
))
2206 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
2213 for (; (i
< args_count
) && (i
< parms_count
); i
++)
2215 struct ipa_jump_func
*jump_func
= ipa_get_ith_jump_func (args
, i
);
2216 struct ipcp_param_lattices
*dest_plats
;
2218 dest_plats
= ipa_get_parm_lattices (callee_info
, i
);
2219 if (availability
== AVAIL_INTERPOSABLE
)
2220 ret
|= set_all_contains_variable (dest_plats
);
2223 ret
|= propagate_scalar_accross_jump_function (cs
, jump_func
,
2224 &dest_plats
->itself
);
2225 ret
|= propagate_context_accross_jump_function (cs
, jump_func
, i
,
2226 &dest_plats
->ctxlat
);
2227 ret
|= propagate_bits_accross_jump_function (cs
, i
, jump_func
,
2228 &dest_plats
->bits_lattice
);
2229 ret
|= propagate_aggs_accross_jump_function (cs
, jump_func
,
2231 if (opt_for_fn (callee
->decl
, flag_ipa_vrp
))
2232 ret
|= propagate_vr_accross_jump_function (cs
,
2233 jump_func
, dest_plats
);
2235 ret
|= dest_plats
->m_value_range
.set_to_bottom ();
2238 for (; i
< parms_count
; i
++)
2239 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
, i
));
2244 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
2245 KNOWN_CONTEXTS, KNOWN_AGGS or AGG_REPS return the destination. The latter
2246 three can be NULL. If AGG_REPS is not NULL, KNOWN_AGGS is ignored. */
2249 ipa_get_indirect_edge_target_1 (struct cgraph_edge
*ie
,
2250 vec
<tree
> known_csts
,
2251 vec
<ipa_polymorphic_call_context
> known_contexts
,
2252 vec
<ipa_agg_jump_function_p
> known_aggs
,
2253 struct ipa_agg_replacement_value
*agg_reps
,
2256 int param_index
= ie
->indirect_info
->param_index
;
2257 HOST_WIDE_INT anc_offset
;
2261 *speculative
= false;
2263 if (param_index
== -1
2264 || known_csts
.length () <= (unsigned int) param_index
)
2267 if (!ie
->indirect_info
->polymorphic
)
2271 if (ie
->indirect_info
->agg_contents
)
2274 if (agg_reps
&& ie
->indirect_info
->guaranteed_unmodified
)
2278 if (agg_reps
->index
== param_index
2279 && agg_reps
->offset
== ie
->indirect_info
->offset
2280 && agg_reps
->by_ref
== ie
->indirect_info
->by_ref
)
2282 t
= agg_reps
->value
;
2285 agg_reps
= agg_reps
->next
;
2290 struct ipa_agg_jump_function
*agg
;
2291 if (known_aggs
.length () > (unsigned int) param_index
)
2292 agg
= known_aggs
[param_index
];
2295 bool from_global_constant
;
2296 t
= ipa_find_agg_cst_for_param (agg
, known_csts
[param_index
],
2297 ie
->indirect_info
->offset
,
2298 ie
->indirect_info
->by_ref
,
2299 &from_global_constant
);
2301 && !from_global_constant
2302 && !ie
->indirect_info
->guaranteed_unmodified
)
2307 t
= known_csts
[param_index
];
2310 TREE_CODE (t
) == ADDR_EXPR
2311 && TREE_CODE (TREE_OPERAND (t
, 0)) == FUNCTION_DECL
)
2312 return TREE_OPERAND (t
, 0);
2317 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize
))
2320 gcc_assert (!ie
->indirect_info
->agg_contents
);
2321 anc_offset
= ie
->indirect_info
->offset
;
2325 /* Try to work out value of virtual table pointer value in replacemnets. */
2326 if (!t
&& agg_reps
&& !ie
->indirect_info
->by_ref
)
2330 if (agg_reps
->index
== param_index
2331 && agg_reps
->offset
== ie
->indirect_info
->offset
2332 && agg_reps
->by_ref
)
2334 t
= agg_reps
->value
;
2337 agg_reps
= agg_reps
->next
;
2341 /* Try to work out value of virtual table pointer value in known
2342 aggregate values. */
2343 if (!t
&& known_aggs
.length () > (unsigned int) param_index
2344 && !ie
->indirect_info
->by_ref
)
2346 struct ipa_agg_jump_function
*agg
;
2347 agg
= known_aggs
[param_index
];
2348 t
= ipa_find_agg_cst_for_param (agg
, known_csts
[param_index
],
2349 ie
->indirect_info
->offset
,
2353 /* If we found the virtual table pointer, lookup the target. */
2357 unsigned HOST_WIDE_INT offset
;
2358 if (vtable_pointer_value_to_vtable (t
, &vtable
, &offset
))
2361 target
= gimple_get_virt_method_for_vtable (ie
->indirect_info
->otr_token
,
2362 vtable
, offset
, &can_refer
);
2366 || (TREE_CODE (TREE_TYPE (target
)) == FUNCTION_TYPE
2367 && DECL_FUNCTION_CODE (target
) == BUILT_IN_UNREACHABLE
)
2368 || !possible_polymorphic_call_target_p
2369 (ie
, cgraph_node::get (target
)))
2371 /* Do not speculate builtin_unreachable, it is stupid! */
2372 if (ie
->indirect_info
->vptr_changed
)
2374 target
= ipa_impossible_devirt_target (ie
, target
);
2376 *speculative
= ie
->indirect_info
->vptr_changed
;
2383 /* Do we know the constant value of pointer? */
2385 t
= known_csts
[param_index
];
2387 gcc_checking_assert (!t
|| TREE_CODE (t
) != TREE_BINFO
);
2389 ipa_polymorphic_call_context context
;
2390 if (known_contexts
.length () > (unsigned int) param_index
)
2392 context
= known_contexts
[param_index
];
2393 context
.offset_by (anc_offset
);
2394 if (ie
->indirect_info
->vptr_changed
)
2395 context
.possible_dynamic_type_change (ie
->in_polymorphic_cdtor
,
2396 ie
->indirect_info
->otr_type
);
2399 ipa_polymorphic_call_context ctx2
= ipa_polymorphic_call_context
2400 (t
, ie
->indirect_info
->otr_type
, anc_offset
);
2401 if (!ctx2
.useless_p ())
2402 context
.combine_with (ctx2
, ie
->indirect_info
->otr_type
);
2407 context
= ipa_polymorphic_call_context (t
, ie
->indirect_info
->otr_type
,
2409 if (ie
->indirect_info
->vptr_changed
)
2410 context
.possible_dynamic_type_change (ie
->in_polymorphic_cdtor
,
2411 ie
->indirect_info
->otr_type
);
2416 vec
<cgraph_node
*>targets
;
2419 targets
= possible_polymorphic_call_targets
2420 (ie
->indirect_info
->otr_type
,
2421 ie
->indirect_info
->otr_token
,
2423 if (!final
|| targets
.length () > 1)
2425 struct cgraph_node
*node
;
2428 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize_speculatively
)
2429 || ie
->speculative
|| !ie
->maybe_hot_p ())
2431 node
= try_speculative_devirtualization (ie
->indirect_info
->otr_type
,
2432 ie
->indirect_info
->otr_token
,
2436 *speculative
= true;
2437 target
= node
->decl
;
2444 *speculative
= false;
2445 if (targets
.length () == 1)
2446 target
= targets
[0]->decl
;
2448 target
= ipa_impossible_devirt_target (ie
, NULL_TREE
);
2451 if (target
&& !possible_polymorphic_call_target_p (ie
,
2452 cgraph_node::get (target
)))
2456 target
= ipa_impossible_devirt_target (ie
, target
);
2463 /* If an indirect edge IE can be turned into a direct one based on KNOWN_CSTS,
2464 KNOWN_CONTEXTS (which can be vNULL) or KNOWN_AGGS (which also can be vNULL)
2465 return the destination. */
2468 ipa_get_indirect_edge_target (struct cgraph_edge
*ie
,
2469 vec
<tree
> known_csts
,
2470 vec
<ipa_polymorphic_call_context
> known_contexts
,
2471 vec
<ipa_agg_jump_function_p
> known_aggs
,
2474 return ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
2475 known_aggs
, NULL
, speculative
);
2478 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
2479 and KNOWN_CONTEXTS. */
2482 devirtualization_time_bonus (struct cgraph_node
*node
,
2483 vec
<tree
> known_csts
,
2484 vec
<ipa_polymorphic_call_context
> known_contexts
,
2485 vec
<ipa_agg_jump_function_p
> known_aggs
)
2487 struct cgraph_edge
*ie
;
2490 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
2492 struct cgraph_node
*callee
;
2493 struct inline_summary
*isummary
;
2494 enum availability avail
;
2498 target
= ipa_get_indirect_edge_target (ie
, known_csts
, known_contexts
,
2499 known_aggs
, &speculative
);
2503 /* Only bare minimum benefit for clearly un-inlineable targets. */
2505 callee
= cgraph_node::get (target
);
2506 if (!callee
|| !callee
->definition
)
2508 callee
= callee
->function_symbol (&avail
);
2509 if (avail
< AVAIL_AVAILABLE
)
2511 isummary
= inline_summaries
->get (callee
);
2512 if (!isummary
->inlinable
)
2515 /* FIXME: The values below need re-considering and perhaps also
2516 integrating into the cost metrics, at lest in some very basic way. */
2517 if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 4)
2518 res
+= 31 / ((int)speculative
+ 1);
2519 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 2)
2520 res
+= 15 / ((int)speculative
+ 1);
2521 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
2522 || DECL_DECLARED_INLINE_P (callee
->decl
))
2523 res
+= 7 / ((int)speculative
+ 1);
2529 /* Return time bonus incurred because of HINTS. */
2532 hint_time_bonus (inline_hints hints
)
2535 if (hints
& (INLINE_HINT_loop_iterations
| INLINE_HINT_loop_stride
))
2536 result
+= PARAM_VALUE (PARAM_IPA_CP_LOOP_HINT_BONUS
);
2537 if (hints
& INLINE_HINT_array_index
)
2538 result
+= PARAM_VALUE (PARAM_IPA_CP_ARRAY_INDEX_HINT_BONUS
);
2542 /* If there is a reason to penalize the function described by INFO in the
2543 cloning goodness evaluation, do so. */
2545 static inline int64_t
2546 incorporate_penalties (ipa_node_params
*info
, int64_t evaluation
)
2548 if (info
->node_within_scc
)
2549 evaluation
= (evaluation
2550 * (100 - PARAM_VALUE (PARAM_IPA_CP_RECURSION_PENALTY
))) / 100;
2552 if (info
->node_calling_single_call
)
2553 evaluation
= (evaluation
2554 * (100 - PARAM_VALUE (PARAM_IPA_CP_SINGLE_CALL_PENALTY
)))
2560 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
2561 and SIZE_COST and with the sum of frequencies of incoming edges to the
2562 potential new clone in FREQUENCIES. */
2565 good_cloning_opportunity_p (struct cgraph_node
*node
, int time_benefit
,
2566 int freq_sum
, gcov_type count_sum
, int size_cost
)
2568 if (time_benefit
== 0
2569 || !opt_for_fn (node
->decl
, flag_ipa_cp_clone
)
2570 || node
->optimize_for_size_p ())
2573 gcc_assert (size_cost
> 0);
2575 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2578 int factor
= (count_sum
* 1000) / max_count
;
2579 int64_t evaluation
= (((int64_t) time_benefit
* factor
)
2581 evaluation
= incorporate_penalties (info
, evaluation
);
2583 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2584 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
2585 "size: %i, count_sum: " HOST_WIDE_INT_PRINT_DEC
2586 "%s%s) -> evaluation: " "%" PRId64
2587 ", threshold: %i\n",
2588 time_benefit
, size_cost
, (HOST_WIDE_INT
) count_sum
,
2589 info
->node_within_scc
? ", scc" : "",
2590 info
->node_calling_single_call
? ", single_call" : "",
2591 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
2593 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
2597 int64_t evaluation
= (((int64_t) time_benefit
* freq_sum
)
2599 evaluation
= incorporate_penalties (info
, evaluation
);
2601 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2602 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
2603 "size: %i, freq_sum: %i%s%s) -> evaluation: "
2604 "%" PRId64
", threshold: %i\n",
2605 time_benefit
, size_cost
, freq_sum
,
2606 info
->node_within_scc
? ", scc" : "",
2607 info
->node_calling_single_call
? ", single_call" : "",
2608 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
2610 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
2614 /* Return all context independent values from aggregate lattices in PLATS in a
2615 vector. Return NULL if there are none. */
2617 static vec
<ipa_agg_jf_item
, va_gc
> *
2618 context_independent_aggregate_values (struct ipcp_param_lattices
*plats
)
2620 vec
<ipa_agg_jf_item
, va_gc
> *res
= NULL
;
2622 if (plats
->aggs_bottom
2623 || plats
->aggs_contain_variable
2624 || plats
->aggs_count
== 0)
2627 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
;
2629 aglat
= aglat
->next
)
2630 if (aglat
->is_single_const ())
2632 struct ipa_agg_jf_item item
;
2633 item
.offset
= aglat
->offset
;
2634 item
.value
= aglat
->values
->value
;
2635 vec_safe_push (res
, item
);
2640 /* Allocate KNOWN_CSTS, KNOWN_CONTEXTS and, if non-NULL, KNOWN_AGGS and
2641 populate them with values of parameters that are known independent of the
2642 context. INFO describes the function. If REMOVABLE_PARAMS_COST is
2643 non-NULL, the movement cost of all removable parameters will be stored in
2647 gather_context_independent_values (struct ipa_node_params
*info
,
2648 vec
<tree
> *known_csts
,
2649 vec
<ipa_polymorphic_call_context
>
2651 vec
<ipa_agg_jump_function
> *known_aggs
,
2652 int *removable_params_cost
)
2654 int i
, count
= ipa_get_param_count (info
);
2657 known_csts
->create (0);
2658 known_contexts
->create (0);
2659 known_csts
->safe_grow_cleared (count
);
2660 known_contexts
->safe_grow_cleared (count
);
2663 known_aggs
->create (0);
2664 known_aggs
->safe_grow_cleared (count
);
2667 if (removable_params_cost
)
2668 *removable_params_cost
= 0;
2670 for (i
= 0; i
< count
; i
++)
2672 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2673 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
2675 if (lat
->is_single_const ())
2677 ipcp_value
<tree
> *val
= lat
->values
;
2678 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
2679 (*known_csts
)[i
] = val
->value
;
2680 if (removable_params_cost
)
2681 *removable_params_cost
2682 += estimate_move_cost (TREE_TYPE (val
->value
), false);
2685 else if (removable_params_cost
2686 && !ipa_is_param_used (info
, i
))
2687 *removable_params_cost
2688 += ipa_get_param_move_cost (info
, i
);
2690 if (!ipa_is_param_used (info
, i
))
2693 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
2694 /* Do not account known context as reason for cloning. We can see
2695 if it permits devirtualization. */
2696 if (ctxlat
->is_single_const ())
2697 (*known_contexts
)[i
] = ctxlat
->values
->value
;
2701 vec
<ipa_agg_jf_item
, va_gc
> *agg_items
;
2702 struct ipa_agg_jump_function
*ajf
;
2704 agg_items
= context_independent_aggregate_values (plats
);
2705 ajf
= &(*known_aggs
)[i
];
2706 ajf
->items
= agg_items
;
2707 ajf
->by_ref
= plats
->aggs_by_ref
;
2708 ret
|= agg_items
!= NULL
;
2715 /* The current interface in ipa-inline-analysis requires a pointer vector.
2718 FIXME: That interface should be re-worked, this is slightly silly. Still,
2719 I'd like to discuss how to change it first and this demonstrates the
2722 static vec
<ipa_agg_jump_function_p
>
2723 agg_jmp_p_vec_for_t_vec (vec
<ipa_agg_jump_function
> known_aggs
)
2725 vec
<ipa_agg_jump_function_p
> ret
;
2726 struct ipa_agg_jump_function
*ajf
;
2729 ret
.create (known_aggs
.length ());
2730 FOR_EACH_VEC_ELT (known_aggs
, i
, ajf
)
2731 ret
.quick_push (ajf
);
2735 /* Perform time and size measurement of NODE with the context given in
2736 KNOWN_CSTS, KNOWN_CONTEXTS and KNOWN_AGGS, calculate the benefit and cost
2737 given BASE_TIME of the node without specialization, REMOVABLE_PARAMS_COST of
2738 all context-independent removable parameters and EST_MOVE_COST of estimated
2739 movement of the considered parameter and store it into VAL. */
2742 perform_estimation_of_a_value (cgraph_node
*node
, vec
<tree
> known_csts
,
2743 vec
<ipa_polymorphic_call_context
> known_contexts
,
2744 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
,
2745 int base_time
, int removable_params_cost
,
2746 int est_move_cost
, ipcp_value_base
*val
)
2748 int time
, size
, time_benefit
;
2751 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
2752 known_aggs_ptrs
, &size
, &time
,
2754 time_benefit
= base_time
- time
2755 + devirtualization_time_bonus (node
, known_csts
, known_contexts
,
2757 + hint_time_bonus (hints
)
2758 + removable_params_cost
+ est_move_cost
;
2760 gcc_checking_assert (size
>=0);
2761 /* The inliner-heuristics based estimates may think that in certain
2762 contexts some functions do not have any size at all but we want
2763 all specializations to have at least a tiny cost, not least not to
2768 val
->local_time_benefit
= time_benefit
;
2769 val
->local_size_cost
= size
;
2772 /* Iterate over known values of parameters of NODE and estimate the local
2773 effects in terms of time and size they have. */
2776 estimate_local_effects (struct cgraph_node
*node
)
2778 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2779 int i
, count
= ipa_get_param_count (info
);
2780 vec
<tree
> known_csts
;
2781 vec
<ipa_polymorphic_call_context
> known_contexts
;
2782 vec
<ipa_agg_jump_function
> known_aggs
;
2783 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
;
2785 int base_time
= inline_summaries
->get (node
)->time
;
2786 int removable_params_cost
;
2788 if (!count
|| !ipcp_versionable_function_p (node
))
2791 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2792 fprintf (dump_file
, "\nEstimating effects for %s/%i, base_time: %i.\n",
2793 node
->name (), node
->order
, base_time
);
2795 always_const
= gather_context_independent_values (info
, &known_csts
,
2796 &known_contexts
, &known_aggs
,
2797 &removable_params_cost
);
2798 known_aggs_ptrs
= agg_jmp_p_vec_for_t_vec (known_aggs
);
2799 int devirt_bonus
= devirtualization_time_bonus (node
, known_csts
,
2800 known_contexts
, known_aggs_ptrs
);
2801 if (always_const
|| devirt_bonus
2802 || (removable_params_cost
&& node
->local
.can_change_signature
))
2804 struct caller_statistics stats
;
2808 init_caller_stats (&stats
);
2809 node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
2811 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
2812 known_aggs_ptrs
, &size
, &time
, &hints
);
2813 time
-= devirt_bonus
;
2814 time
-= hint_time_bonus (hints
);
2815 time
-= removable_params_cost
;
2816 size
-= stats
.n_calls
* removable_params_cost
;
2819 fprintf (dump_file
, " - context independent values, size: %i, "
2820 "time_benefit: %i\n", size
, base_time
- time
);
2822 if (size
<= 0 || node
->local
.local
)
2824 info
->do_clone_for_all_contexts
= true;
2828 fprintf (dump_file
, " Decided to specialize for all "
2829 "known contexts, code not going to grow.\n");
2831 else if (good_cloning_opportunity_p (node
, base_time
- time
,
2832 stats
.freq_sum
, stats
.count_sum
,
2835 if (size
+ overall_size
<= max_new_size
)
2837 info
->do_clone_for_all_contexts
= true;
2839 overall_size
+= size
;
2842 fprintf (dump_file
, " Decided to specialize for all "
2843 "known contexts, growth deemed beneficial.\n");
2845 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2846 fprintf (dump_file
, " Not cloning for all contexts because "
2847 "max_new_size would be reached with %li.\n",
2848 size
+ overall_size
);
2850 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2851 fprintf (dump_file
, " Not cloning for all contexts because "
2852 "!good_cloning_opportunity_p.\n");
2856 for (i
= 0; i
< count
; i
++)
2858 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2859 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
2860 ipcp_value
<tree
> *val
;
2867 for (val
= lat
->values
; val
; val
= val
->next
)
2869 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
2870 known_csts
[i
] = val
->value
;
2872 int emc
= estimate_move_cost (TREE_TYPE (val
->value
), true);
2873 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
2874 known_aggs_ptrs
, base_time
,
2875 removable_params_cost
, emc
, val
);
2877 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2879 fprintf (dump_file
, " - estimates for value ");
2880 print_ipcp_constant_value (dump_file
, val
->value
);
2881 fprintf (dump_file
, " for ");
2882 ipa_dump_param (dump_file
, info
, i
);
2883 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
2884 val
->local_time_benefit
, val
->local_size_cost
);
2887 known_csts
[i
] = NULL_TREE
;
2890 for (i
= 0; i
< count
; i
++)
2892 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2894 if (!plats
->virt_call
)
2897 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
2898 ipcp_value
<ipa_polymorphic_call_context
> *val
;
2902 || !known_contexts
[i
].useless_p ())
2905 for (val
= ctxlat
->values
; val
; val
= val
->next
)
2907 known_contexts
[i
] = val
->value
;
2908 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
2909 known_aggs_ptrs
, base_time
,
2910 removable_params_cost
, 0, val
);
2912 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2914 fprintf (dump_file
, " - estimates for polymorphic context ");
2915 print_ipcp_constant_value (dump_file
, val
->value
);
2916 fprintf (dump_file
, " for ");
2917 ipa_dump_param (dump_file
, info
, i
);
2918 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
2919 val
->local_time_benefit
, val
->local_size_cost
);
2922 known_contexts
[i
] = ipa_polymorphic_call_context ();
2925 for (i
= 0; i
< count
; i
++)
2927 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2928 struct ipa_agg_jump_function
*ajf
;
2929 struct ipcp_agg_lattice
*aglat
;
2931 if (plats
->aggs_bottom
|| !plats
->aggs
)
2934 ajf
= &known_aggs
[i
];
2935 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2937 ipcp_value
<tree
> *val
;
2938 if (aglat
->bottom
|| !aglat
->values
2939 /* If the following is true, the one value is in known_aggs. */
2940 || (!plats
->aggs_contain_variable
2941 && aglat
->is_single_const ()))
2944 for (val
= aglat
->values
; val
; val
= val
->next
)
2946 struct ipa_agg_jf_item item
;
2948 item
.offset
= aglat
->offset
;
2949 item
.value
= val
->value
;
2950 vec_safe_push (ajf
->items
, item
);
2952 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
2953 known_aggs_ptrs
, base_time
,
2954 removable_params_cost
, 0, val
);
2956 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2958 fprintf (dump_file
, " - estimates for value ");
2959 print_ipcp_constant_value (dump_file
, val
->value
);
2960 fprintf (dump_file
, " for ");
2961 ipa_dump_param (dump_file
, info
, i
);
2962 fprintf (dump_file
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
2963 "]: time_benefit: %i, size: %i\n",
2964 plats
->aggs_by_ref
? "ref " : "",
2966 val
->local_time_benefit
, val
->local_size_cost
);
2974 for (i
= 0; i
< count
; i
++)
2975 vec_free (known_aggs
[i
].items
);
2977 known_csts
.release ();
2978 known_contexts
.release ();
2979 known_aggs
.release ();
2980 known_aggs_ptrs
.release ();
2984 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
2985 topological sort of values. */
2987 template <typename valtype
>
2989 value_topo_info
<valtype
>::add_val (ipcp_value
<valtype
> *cur_val
)
2991 ipcp_value_source
<valtype
> *src
;
2997 cur_val
->dfs
= dfs_counter
;
2998 cur_val
->low_link
= dfs_counter
;
3000 cur_val
->topo_next
= stack
;
3002 cur_val
->on_stack
= true;
3004 for (src
= cur_val
->sources
; src
; src
= src
->next
)
3007 if (src
->val
->dfs
== 0)
3010 if (src
->val
->low_link
< cur_val
->low_link
)
3011 cur_val
->low_link
= src
->val
->low_link
;
3013 else if (src
->val
->on_stack
3014 && src
->val
->dfs
< cur_val
->low_link
)
3015 cur_val
->low_link
= src
->val
->dfs
;
3018 if (cur_val
->dfs
== cur_val
->low_link
)
3020 ipcp_value
<valtype
> *v
, *scc_list
= NULL
;
3025 stack
= v
->topo_next
;
3026 v
->on_stack
= false;
3028 v
->scc_next
= scc_list
;
3031 while (v
!= cur_val
);
3033 cur_val
->topo_next
= values_topo
;
3034 values_topo
= cur_val
;
3038 /* Add all values in lattices associated with NODE to the topological sort if
3039 they are not there yet. */
3042 add_all_node_vals_to_toposort (cgraph_node
*node
, ipa_topo_info
*topo
)
3044 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3045 int i
, count
= ipa_get_param_count (info
);
3047 for (i
= 0; i
< count
; i
++)
3049 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3050 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
3051 struct ipcp_agg_lattice
*aglat
;
3055 ipcp_value
<tree
> *val
;
3056 for (val
= lat
->values
; val
; val
= val
->next
)
3057 topo
->constants
.add_val (val
);
3060 if (!plats
->aggs_bottom
)
3061 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3064 ipcp_value
<tree
> *val
;
3065 for (val
= aglat
->values
; val
; val
= val
->next
)
3066 topo
->constants
.add_val (val
);
3069 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
3070 if (!ctxlat
->bottom
)
3072 ipcp_value
<ipa_polymorphic_call_context
> *ctxval
;
3073 for (ctxval
= ctxlat
->values
; ctxval
; ctxval
= ctxval
->next
)
3074 topo
->contexts
.add_val (ctxval
);
3079 /* One pass of constants propagation along the call graph edges, from callers
3080 to callees (requires topological ordering in TOPO), iterate over strongly
3081 connected components. */
3084 propagate_constants_topo (struct ipa_topo_info
*topo
)
3088 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
3091 struct cgraph_node
*v
, *node
= topo
->order
[i
];
3092 vec
<cgraph_node
*> cycle_nodes
= ipa_get_nodes_in_cycle (node
);
3094 /* First, iteratively propagate within the strongly connected component
3095 until all lattices stabilize. */
3096 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
3097 if (v
->has_gimple_body_p ())
3098 push_node_to_stack (topo
, v
);
3100 v
= pop_node_from_stack (topo
);
3103 struct cgraph_edge
*cs
;
3105 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3106 if (ipa_edge_within_scc (cs
))
3108 IPA_NODE_REF (v
)->node_within_scc
= true;
3109 if (propagate_constants_accross_call (cs
))
3110 push_node_to_stack (topo
, cs
->callee
->function_symbol ());
3112 v
= pop_node_from_stack (topo
);
3115 /* Afterwards, propagate along edges leading out of the SCC, calculates
3116 the local effects of the discovered constants and all valid values to
3117 their topological sort. */
3118 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
3119 if (v
->has_gimple_body_p ())
3121 struct cgraph_edge
*cs
;
3123 estimate_local_effects (v
);
3124 add_all_node_vals_to_toposort (v
, topo
);
3125 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3126 if (!ipa_edge_within_scc (cs
))
3127 propagate_constants_accross_call (cs
);
3129 cycle_nodes
.release ();
3134 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
3135 the bigger one if otherwise. */
3138 safe_add (int a
, int b
)
3140 if (a
> INT_MAX
/2 || b
> INT_MAX
/2)
3141 return a
> b
? a
: b
;
3147 /* Propagate the estimated effects of individual values along the topological
3148 from the dependent values to those they depend on. */
3150 template <typename valtype
>
3152 value_topo_info
<valtype
>::propagate_effects ()
3154 ipcp_value
<valtype
> *base
;
3156 for (base
= values_topo
; base
; base
= base
->topo_next
)
3158 ipcp_value_source
<valtype
> *src
;
3159 ipcp_value
<valtype
> *val
;
3160 int time
= 0, size
= 0;
3162 for (val
= base
; val
; val
= val
->scc_next
)
3164 time
= safe_add (time
,
3165 val
->local_time_benefit
+ val
->prop_time_benefit
);
3166 size
= safe_add (size
, val
->local_size_cost
+ val
->prop_size_cost
);
3169 for (val
= base
; val
; val
= val
->scc_next
)
3170 for (src
= val
->sources
; src
; src
= src
->next
)
3172 && src
->cs
->maybe_hot_p ())
3174 src
->val
->prop_time_benefit
= safe_add (time
,
3175 src
->val
->prop_time_benefit
);
3176 src
->val
->prop_size_cost
= safe_add (size
,
3177 src
->val
->prop_size_cost
);
3183 /* Propagate constants, polymorphic contexts and their effects from the
3184 summaries interprocedurally. */
3187 ipcp_propagate_stage (struct ipa_topo_info
*topo
)
3189 struct cgraph_node
*node
;
3192 fprintf (dump_file
, "\n Propagating constants:\n\n");
3195 ipa_update_after_lto_read ();
3198 FOR_EACH_DEFINED_FUNCTION (node
)
3200 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3202 /* In LTO we do not have PARM_DECLs but we would still like to be able to
3203 look at types of parameters. */
3206 tree t
= TYPE_ARG_TYPES (TREE_TYPE (node
->decl
));
3207 for (int k
= 0; k
< ipa_get_param_count (info
) && t
; k
++)
3209 gcc_assert (t
!= void_list_node
);
3210 info
->descriptors
[k
].decl_or_type
= TREE_VALUE (t
);
3211 t
= t
? TREE_CHAIN (t
) : NULL
;
3215 determine_versionability (node
, info
);
3216 if (node
->has_gimple_body_p ())
3218 info
->lattices
= XCNEWVEC (struct ipcp_param_lattices
,
3219 ipa_get_param_count (info
));
3220 initialize_node_lattices (node
);
3222 if (node
->definition
&& !node
->alias
)
3223 overall_size
+= inline_summaries
->get (node
)->self_size
;
3224 if (node
->count
> max_count
)
3225 max_count
= node
->count
;
3228 max_new_size
= overall_size
;
3229 if (max_new_size
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
3230 max_new_size
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
3231 max_new_size
+= max_new_size
* PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH
) / 100 + 1;
3234 fprintf (dump_file
, "\noverall_size: %li, max_new_size: %li\n",
3235 overall_size
, max_new_size
);
3237 propagate_constants_topo (topo
);
3239 ipcp_verify_propagated_values ();
3240 topo
->constants
.propagate_effects ();
3241 topo
->contexts
.propagate_effects ();
3245 fprintf (dump_file
, "\nIPA lattices after all propagation:\n");
3246 print_all_lattices (dump_file
, (dump_flags
& TDF_DETAILS
), true);
3250 /* Discover newly direct outgoing edges from NODE which is a new clone with
3251 known KNOWN_CSTS and make them direct. */
3254 ipcp_discover_new_direct_edges (struct cgraph_node
*node
,
3255 vec
<tree
> known_csts
,
3256 vec
<ipa_polymorphic_call_context
>
3258 struct ipa_agg_replacement_value
*aggvals
)
3260 struct cgraph_edge
*ie
, *next_ie
;
3263 for (ie
= node
->indirect_calls
; ie
; ie
= next_ie
)
3268 next_ie
= ie
->next_callee
;
3269 target
= ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
3270 vNULL
, aggvals
, &speculative
);
3273 bool agg_contents
= ie
->indirect_info
->agg_contents
;
3274 bool polymorphic
= ie
->indirect_info
->polymorphic
;
3275 int param_index
= ie
->indirect_info
->param_index
;
3276 struct cgraph_edge
*cs
= ipa_make_edge_direct_to_target (ie
, target
,
3280 if (cs
&& !agg_contents
&& !polymorphic
)
3282 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3283 int c
= ipa_get_controlled_uses (info
, param_index
);
3284 if (c
!= IPA_UNDESCRIBED_USE
)
3286 struct ipa_ref
*to_del
;
3289 ipa_set_controlled_uses (info
, param_index
, c
);
3290 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3291 fprintf (dump_file
, " controlled uses count of param "
3292 "%i bumped down to %i\n", param_index
, c
);
3294 && (to_del
= node
->find_reference (cs
->callee
, NULL
, 0)))
3296 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3297 fprintf (dump_file
, " and even removing its "
3298 "cloning-created reference\n");
3299 to_del
->remove_reference ();
3305 /* Turning calls to direct calls will improve overall summary. */
3307 inline_update_overall_summary (node
);
3310 /* Vector of pointers which for linked lists of clones of an original crgaph
3313 static vec
<cgraph_edge
*> next_edge_clone
;
3314 static vec
<cgraph_edge
*> prev_edge_clone
;
3317 grow_edge_clone_vectors (void)
3319 if (next_edge_clone
.length ()
3320 <= (unsigned) symtab
->edges_max_uid
)
3321 next_edge_clone
.safe_grow_cleared (symtab
->edges_max_uid
+ 1);
3322 if (prev_edge_clone
.length ()
3323 <= (unsigned) symtab
->edges_max_uid
)
3324 prev_edge_clone
.safe_grow_cleared (symtab
->edges_max_uid
+ 1);
3327 /* Edge duplication hook to grow the appropriate linked list in
3331 ipcp_edge_duplication_hook (struct cgraph_edge
*src
, struct cgraph_edge
*dst
,
3334 grow_edge_clone_vectors ();
3336 struct cgraph_edge
*old_next
= next_edge_clone
[src
->uid
];
3338 prev_edge_clone
[old_next
->uid
] = dst
;
3339 prev_edge_clone
[dst
->uid
] = src
;
3341 next_edge_clone
[dst
->uid
] = old_next
;
3342 next_edge_clone
[src
->uid
] = dst
;
3345 /* Hook that is called by cgraph.c when an edge is removed. */
3348 ipcp_edge_removal_hook (struct cgraph_edge
*cs
, void *)
3350 grow_edge_clone_vectors ();
3352 struct cgraph_edge
*prev
= prev_edge_clone
[cs
->uid
];
3353 struct cgraph_edge
*next
= next_edge_clone
[cs
->uid
];
3355 next_edge_clone
[prev
->uid
] = next
;
3357 prev_edge_clone
[next
->uid
] = prev
;
3360 /* See if NODE is a clone with a known aggregate value at a given OFFSET of a
3361 parameter with the given INDEX. */
3364 get_clone_agg_value (struct cgraph_node
*node
, HOST_WIDE_INT offset
,
3367 struct ipa_agg_replacement_value
*aggval
;
3369 aggval
= ipa_get_agg_replacements_for_node (node
);
3372 if (aggval
->offset
== offset
3373 && aggval
->index
== index
)
3374 return aggval
->value
;
3375 aggval
= aggval
->next
;
3380 /* Return true is NODE is DEST or its clone for all contexts. */
3383 same_node_or_its_all_contexts_clone_p (cgraph_node
*node
, cgraph_node
*dest
)
3388 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3389 return info
->is_all_contexts_clone
&& info
->ipcp_orig_node
== dest
;
3392 /* Return true if edge CS does bring about the value described by SRC to node
3393 DEST or its clone for all contexts. */
3396 cgraph_edge_brings_value_p (cgraph_edge
*cs
, ipcp_value_source
<tree
> *src
,
3399 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3400 enum availability availability
;
3401 cgraph_node
*real_dest
= cs
->callee
->function_symbol (&availability
);
3403 if (!same_node_or_its_all_contexts_clone_p (real_dest
, dest
)
3404 || availability
<= AVAIL_INTERPOSABLE
3405 || caller_info
->node_dead
)
3410 if (caller_info
->ipcp_orig_node
)
3413 if (src
->offset
== -1)
3414 t
= caller_info
->known_csts
[src
->index
];
3416 t
= get_clone_agg_value (cs
->caller
, src
->offset
, src
->index
);
3417 return (t
!= NULL_TREE
3418 && values_equal_for_ipcp_p (src
->val
->value
, t
));
3422 struct ipcp_agg_lattice
*aglat
;
3423 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
3425 if (src
->offset
== -1)
3426 return (plats
->itself
.is_single_const ()
3427 && values_equal_for_ipcp_p (src
->val
->value
,
3428 plats
->itself
.values
->value
));
3431 if (plats
->aggs_bottom
|| plats
->aggs_contain_variable
)
3433 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3434 if (aglat
->offset
== src
->offset
)
3435 return (aglat
->is_single_const ()
3436 && values_equal_for_ipcp_p (src
->val
->value
,
3437 aglat
->values
->value
));
3443 /* Return true if edge CS does bring about the value described by SRC to node
3444 DEST or its clone for all contexts. */
3447 cgraph_edge_brings_value_p (cgraph_edge
*cs
,
3448 ipcp_value_source
<ipa_polymorphic_call_context
> *src
,
3451 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3452 cgraph_node
*real_dest
= cs
->callee
->function_symbol ();
3454 if (!same_node_or_its_all_contexts_clone_p (real_dest
, dest
)
3455 || caller_info
->node_dead
)
3460 if (caller_info
->ipcp_orig_node
)
3461 return (caller_info
->known_contexts
.length () > (unsigned) src
->index
)
3462 && values_equal_for_ipcp_p (src
->val
->value
,
3463 caller_info
->known_contexts
[src
->index
]);
3465 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
3467 return plats
->ctxlat
.is_single_const ()
3468 && values_equal_for_ipcp_p (src
->val
->value
,
3469 plats
->ctxlat
.values
->value
);
3472 /* Get the next clone in the linked list of clones of an edge. */
3474 static inline struct cgraph_edge
*
3475 get_next_cgraph_edge_clone (struct cgraph_edge
*cs
)
3477 return next_edge_clone
[cs
->uid
];
3480 /* Given VAL that is intended for DEST, iterate over all its sources and if
3481 they still hold, add their edge frequency and their number into *FREQUENCY
3482 and *CALLER_COUNT respectively. */
3484 template <typename valtype
>
3486 get_info_about_necessary_edges (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
3488 gcov_type
*count_sum
, int *caller_count
)
3490 ipcp_value_source
<valtype
> *src
;
3491 int freq
= 0, count
= 0;
3495 for (src
= val
->sources
; src
; src
= src
->next
)
3497 struct cgraph_edge
*cs
= src
->cs
;
3500 if (cgraph_edge_brings_value_p (cs
, src
, dest
))
3503 freq
+= cs
->frequency
;
3505 hot
|= cs
->maybe_hot_p ();
3507 cs
= get_next_cgraph_edge_clone (cs
);
3513 *caller_count
= count
;
3517 /* Return a vector of incoming edges that do bring value VAL to node DEST. It
3518 is assumed their number is known and equal to CALLER_COUNT. */
3520 template <typename valtype
>
3521 static vec
<cgraph_edge
*>
3522 gather_edges_for_value (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
3525 ipcp_value_source
<valtype
> *src
;
3526 vec
<cgraph_edge
*> ret
;
3528 ret
.create (caller_count
);
3529 for (src
= val
->sources
; src
; src
= src
->next
)
3531 struct cgraph_edge
*cs
= src
->cs
;
3534 if (cgraph_edge_brings_value_p (cs
, src
, dest
))
3535 ret
.quick_push (cs
);
3536 cs
= get_next_cgraph_edge_clone (cs
);
3543 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
3544 Return it or NULL if for some reason it cannot be created. */
3546 static struct ipa_replace_map
*
3547 get_replacement_map (struct ipa_node_params
*info
, tree value
, int parm_num
)
3549 struct ipa_replace_map
*replace_map
;
3552 replace_map
= ggc_alloc
<ipa_replace_map
> ();
3555 fprintf (dump_file
, " replacing ");
3556 ipa_dump_param (dump_file
, info
, parm_num
);
3558 fprintf (dump_file
, " with const ");
3559 print_generic_expr (dump_file
, value
, 0);
3560 fprintf (dump_file
, "\n");
3562 replace_map
->old_tree
= NULL
;
3563 replace_map
->parm_num
= parm_num
;
3564 replace_map
->new_tree
= value
;
3565 replace_map
->replace_p
= true;
3566 replace_map
->ref_p
= false;
3571 /* Dump new profiling counts */
3574 dump_profile_updates (struct cgraph_node
*orig_node
,
3575 struct cgraph_node
*new_node
)
3577 struct cgraph_edge
*cs
;
3579 fprintf (dump_file
, " setting count of the specialized node to "
3580 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) new_node
->count
);
3581 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3582 fprintf (dump_file
, " edge to %s has count "
3583 HOST_WIDE_INT_PRINT_DEC
"\n",
3584 cs
->callee
->name (), (HOST_WIDE_INT
) cs
->count
);
3586 fprintf (dump_file
, " setting count of the original node to "
3587 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) orig_node
->count
);
3588 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3589 fprintf (dump_file
, " edge to %s is left with "
3590 HOST_WIDE_INT_PRINT_DEC
"\n",
3591 cs
->callee
->name (), (HOST_WIDE_INT
) cs
->count
);
3594 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
3595 their profile information to reflect this. */
3598 update_profiling_info (struct cgraph_node
*orig_node
,
3599 struct cgraph_node
*new_node
)
3601 struct cgraph_edge
*cs
;
3602 struct caller_statistics stats
;
3603 gcov_type new_sum
, orig_sum
;
3604 gcov_type remainder
, orig_node_count
= orig_node
->count
;
3606 if (orig_node_count
== 0)
3609 init_caller_stats (&stats
);
3610 orig_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
3612 orig_sum
= stats
.count_sum
;
3613 init_caller_stats (&stats
);
3614 new_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
3616 new_sum
= stats
.count_sum
;
3618 if (orig_node_count
< orig_sum
+ new_sum
)
3621 fprintf (dump_file
, " Problem: node %s/%i has too low count "
3622 HOST_WIDE_INT_PRINT_DEC
" while the sum of incoming "
3623 "counts is " HOST_WIDE_INT_PRINT_DEC
"\n",
3624 orig_node
->name (), orig_node
->order
,
3625 (HOST_WIDE_INT
) orig_node_count
,
3626 (HOST_WIDE_INT
) (orig_sum
+ new_sum
));
3628 orig_node_count
= (orig_sum
+ new_sum
) * 12 / 10;
3630 fprintf (dump_file
, " proceeding by pretending it was "
3631 HOST_WIDE_INT_PRINT_DEC
"\n",
3632 (HOST_WIDE_INT
) orig_node_count
);
3635 new_node
->count
= new_sum
;
3636 remainder
= orig_node_count
- new_sum
;
3637 orig_node
->count
= remainder
;
3639 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3641 cs
->count
= apply_probability (cs
->count
,
3642 GCOV_COMPUTE_SCALE (new_sum
,
3647 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3648 cs
->count
= apply_probability (cs
->count
,
3649 GCOV_COMPUTE_SCALE (remainder
,
3653 dump_profile_updates (orig_node
, new_node
);
3656 /* Update the respective profile of specialized NEW_NODE and the original
3657 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
3658 have been redirected to the specialized version. */
3661 update_specialized_profile (struct cgraph_node
*new_node
,
3662 struct cgraph_node
*orig_node
,
3663 gcov_type redirected_sum
)
3665 struct cgraph_edge
*cs
;
3666 gcov_type new_node_count
, orig_node_count
= orig_node
->count
;
3669 fprintf (dump_file
, " the sum of counts of redirected edges is "
3670 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) redirected_sum
);
3671 if (orig_node_count
== 0)
3674 gcc_assert (orig_node_count
>= redirected_sum
);
3676 new_node_count
= new_node
->count
;
3677 new_node
->count
+= redirected_sum
;
3678 orig_node
->count
-= redirected_sum
;
3680 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3682 cs
->count
+= apply_probability (cs
->count
,
3683 GCOV_COMPUTE_SCALE (redirected_sum
,
3688 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3690 gcov_type dec
= apply_probability (cs
->count
,
3691 GCOV_COMPUTE_SCALE (redirected_sum
,
3693 if (dec
< cs
->count
)
3700 dump_profile_updates (orig_node
, new_node
);
3703 /* Create a specialized version of NODE with known constants in KNOWN_CSTS,
3704 known contexts in KNOWN_CONTEXTS and known aggregate values in AGGVALS and
3705 redirect all edges in CALLERS to it. */
3707 static struct cgraph_node
*
3708 create_specialized_node (struct cgraph_node
*node
,
3709 vec
<tree
> known_csts
,
3710 vec
<ipa_polymorphic_call_context
> known_contexts
,
3711 struct ipa_agg_replacement_value
*aggvals
,
3712 vec
<cgraph_edge
*> callers
)
3714 struct ipa_node_params
*new_info
, *info
= IPA_NODE_REF (node
);
3715 vec
<ipa_replace_map
*, va_gc
> *replace_trees
= NULL
;
3716 struct ipa_agg_replacement_value
*av
;
3717 struct cgraph_node
*new_node
;
3718 int i
, count
= ipa_get_param_count (info
);
3719 bitmap args_to_skip
;
3721 gcc_assert (!info
->ipcp_orig_node
);
3723 if (node
->local
.can_change_signature
)
3725 args_to_skip
= BITMAP_GGC_ALLOC ();
3726 for (i
= 0; i
< count
; i
++)
3728 tree t
= known_csts
[i
];
3730 if (t
|| !ipa_is_param_used (info
, i
))
3731 bitmap_set_bit (args_to_skip
, i
);
3736 args_to_skip
= NULL
;
3737 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3738 fprintf (dump_file
, " cannot change function signature\n");
3741 for (i
= 0; i
< count
; i
++)
3743 tree t
= known_csts
[i
];
3746 struct ipa_replace_map
*replace_map
;
3748 gcc_checking_assert (TREE_CODE (t
) != TREE_BINFO
);
3749 replace_map
= get_replacement_map (info
, t
, i
);
3751 vec_safe_push (replace_trees
, replace_map
);
3755 new_node
= node
->create_virtual_clone (callers
, replace_trees
,
3756 args_to_skip
, "constprop");
3757 ipa_set_node_agg_value_chain (new_node
, aggvals
);
3758 for (av
= aggvals
; av
; av
= av
->next
)
3759 new_node
->maybe_create_reference (av
->value
, IPA_REF_ADDR
, NULL
);
3761 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3763 fprintf (dump_file
, " the new node is %s/%i.\n",
3764 new_node
->name (), new_node
->order
);
3765 if (known_contexts
.exists ())
3767 for (i
= 0; i
< count
; i
++)
3768 if (!known_contexts
[i
].useless_p ())
3770 fprintf (dump_file
, " known ctx %i is ", i
);
3771 known_contexts
[i
].dump (dump_file
);
3775 ipa_dump_agg_replacement_values (dump_file
, aggvals
);
3777 ipa_check_create_node_params ();
3778 update_profiling_info (node
, new_node
);
3779 new_info
= IPA_NODE_REF (new_node
);
3780 new_info
->ipcp_orig_node
= node
;
3781 new_info
->known_csts
= known_csts
;
3782 new_info
->known_contexts
= known_contexts
;
3784 ipcp_discover_new_direct_edges (new_node
, known_csts
, known_contexts
, aggvals
);
3790 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
3791 KNOWN_CSTS with constants that are also known for all of the CALLERS. */
3794 find_more_scalar_values_for_callers_subset (struct cgraph_node
*node
,
3795 vec
<tree
> known_csts
,
3796 vec
<cgraph_edge
*> callers
)
3798 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3799 int i
, count
= ipa_get_param_count (info
);
3801 for (i
= 0; i
< count
; i
++)
3803 struct cgraph_edge
*cs
;
3804 tree newval
= NULL_TREE
;
3808 if (ipa_get_scalar_lat (info
, i
)->bottom
|| known_csts
[i
])
3811 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3813 struct ipa_jump_func
*jump_func
;
3816 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
))
3818 && call_passes_through_thunk_p (cs
))
3819 || (!cs
->callee
->instrumentation_clone
3820 && cs
->callee
->function_symbol ()->instrumentation_clone
))
3825 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
3826 t
= ipa_value_from_jfunc (IPA_NODE_REF (cs
->caller
), jump_func
);
3829 && !values_equal_for_ipcp_p (t
, newval
))
3830 || (!first
&& !newval
))
3842 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3844 fprintf (dump_file
, " adding an extra known scalar value ");
3845 print_ipcp_constant_value (dump_file
, newval
);
3846 fprintf (dump_file
, " for ");
3847 ipa_dump_param (dump_file
, info
, i
);
3848 fprintf (dump_file
, "\n");
3851 known_csts
[i
] = newval
;
3856 /* Given a NODE and a subset of its CALLERS, try to populate plank slots in
3857 KNOWN_CONTEXTS with polymorphic contexts that are also known for all of the
3861 find_more_contexts_for_caller_subset (cgraph_node
*node
,
3862 vec
<ipa_polymorphic_call_context
>
3864 vec
<cgraph_edge
*> callers
)
3866 ipa_node_params
*info
= IPA_NODE_REF (node
);
3867 int i
, count
= ipa_get_param_count (info
);
3869 for (i
= 0; i
< count
; i
++)
3873 if (ipa_get_poly_ctx_lat (info
, i
)->bottom
3874 || (known_contexts
->exists ()
3875 && !(*known_contexts
)[i
].useless_p ()))
3878 ipa_polymorphic_call_context newval
;
3882 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3884 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
)))
3886 ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
),
3888 ipa_polymorphic_call_context ctx
;
3889 ctx
= ipa_context_from_jfunc (IPA_NODE_REF (cs
->caller
), cs
, i
,
3897 newval
.meet_with (ctx
);
3898 if (newval
.useless_p ())
3902 if (!newval
.useless_p ())
3904 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3906 fprintf (dump_file
, " adding an extra known polymorphic "
3908 print_ipcp_constant_value (dump_file
, newval
);
3909 fprintf (dump_file
, " for ");
3910 ipa_dump_param (dump_file
, info
, i
);
3911 fprintf (dump_file
, "\n");
3914 if (!known_contexts
->exists ())
3915 known_contexts
->safe_grow_cleared (ipa_get_param_count (info
));
3916 (*known_contexts
)[i
] = newval
;
3922 /* Go through PLATS and create a vector of values consisting of values and
3923 offsets (minus OFFSET) of lattices that contain only a single value. */
3925 static vec
<ipa_agg_jf_item
>
3926 copy_plats_to_inter (struct ipcp_param_lattices
*plats
, HOST_WIDE_INT offset
)
3928 vec
<ipa_agg_jf_item
> res
= vNULL
;
3930 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
3933 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3934 if (aglat
->is_single_const ())
3936 struct ipa_agg_jf_item ti
;
3937 ti
.offset
= aglat
->offset
- offset
;
3938 ti
.value
= aglat
->values
->value
;
3944 /* Intersect all values in INTER with single value lattices in PLATS (while
3945 subtracting OFFSET). */
3948 intersect_with_plats (struct ipcp_param_lattices
*plats
,
3949 vec
<ipa_agg_jf_item
> *inter
,
3950 HOST_WIDE_INT offset
)
3952 struct ipcp_agg_lattice
*aglat
;
3953 struct ipa_agg_jf_item
*item
;
3956 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
3962 aglat
= plats
->aggs
;
3963 FOR_EACH_VEC_ELT (*inter
, k
, item
)
3970 if (aglat
->offset
- offset
> item
->offset
)
3972 if (aglat
->offset
- offset
== item
->offset
)
3974 gcc_checking_assert (item
->value
);
3975 if (values_equal_for_ipcp_p (item
->value
, aglat
->values
->value
))
3979 aglat
= aglat
->next
;
3982 item
->value
= NULL_TREE
;
3986 /* Copy agggregate replacement values of NODE (which is an IPA-CP clone) to the
3987 vector result while subtracting OFFSET from the individual value offsets. */
3989 static vec
<ipa_agg_jf_item
>
3990 agg_replacements_to_vector (struct cgraph_node
*node
, int index
,
3991 HOST_WIDE_INT offset
)
3993 struct ipa_agg_replacement_value
*av
;
3994 vec
<ipa_agg_jf_item
> res
= vNULL
;
3996 for (av
= ipa_get_agg_replacements_for_node (node
); av
; av
= av
->next
)
3997 if (av
->index
== index
3998 && (av
->offset
- offset
) >= 0)
4000 struct ipa_agg_jf_item item
;
4001 gcc_checking_assert (av
->value
);
4002 item
.offset
= av
->offset
- offset
;
4003 item
.value
= av
->value
;
4004 res
.safe_push (item
);
4010 /* Intersect all values in INTER with those that we have already scheduled to
4011 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
4012 (while subtracting OFFSET). */
4015 intersect_with_agg_replacements (struct cgraph_node
*node
, int index
,
4016 vec
<ipa_agg_jf_item
> *inter
,
4017 HOST_WIDE_INT offset
)
4019 struct ipa_agg_replacement_value
*srcvals
;
4020 struct ipa_agg_jf_item
*item
;
4023 srcvals
= ipa_get_agg_replacements_for_node (node
);
4030 FOR_EACH_VEC_ELT (*inter
, i
, item
)
4032 struct ipa_agg_replacement_value
*av
;
4036 for (av
= srcvals
; av
; av
= av
->next
)
4038 gcc_checking_assert (av
->value
);
4039 if (av
->index
== index
4040 && av
->offset
- offset
== item
->offset
)
4042 if (values_equal_for_ipcp_p (item
->value
, av
->value
))
4048 item
->value
= NULL_TREE
;
4052 /* Intersect values in INTER with aggregate values that come along edge CS to
4053 parameter number INDEX and return it. If INTER does not actually exist yet,
4054 copy all incoming values to it. If we determine we ended up with no values
4055 whatsoever, return a released vector. */
4057 static vec
<ipa_agg_jf_item
>
4058 intersect_aggregates_with_edge (struct cgraph_edge
*cs
, int index
,
4059 vec
<ipa_agg_jf_item
> inter
)
4061 struct ipa_jump_func
*jfunc
;
4062 jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), index
);
4063 if (jfunc
->type
== IPA_JF_PASS_THROUGH
4064 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
4066 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4067 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
4069 if (caller_info
->ipcp_orig_node
)
4071 struct cgraph_node
*orig_node
= caller_info
->ipcp_orig_node
;
4072 struct ipcp_param_lattices
*orig_plats
;
4073 orig_plats
= ipa_get_parm_lattices (IPA_NODE_REF (orig_node
),
4075 if (agg_pass_through_permissible_p (orig_plats
, jfunc
))
4077 if (!inter
.exists ())
4078 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, 0);
4080 intersect_with_agg_replacements (cs
->caller
, src_idx
,
4091 struct ipcp_param_lattices
*src_plats
;
4092 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
4093 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
4095 /* Currently we do not produce clobber aggregate jump
4096 functions, adjust when we do. */
4097 gcc_checking_assert (!jfunc
->agg
.items
);
4098 if (!inter
.exists ())
4099 inter
= copy_plats_to_inter (src_plats
, 0);
4101 intersect_with_plats (src_plats
, &inter
, 0);
4110 else if (jfunc
->type
== IPA_JF_ANCESTOR
4111 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
4113 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4114 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
4115 struct ipcp_param_lattices
*src_plats
;
4116 HOST_WIDE_INT delta
= ipa_get_jf_ancestor_offset (jfunc
);
4118 if (caller_info
->ipcp_orig_node
)
4120 if (!inter
.exists ())
4121 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, delta
);
4123 intersect_with_agg_replacements (cs
->caller
, src_idx
, &inter
,
4128 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);;
4129 /* Currently we do not produce clobber aggregate jump
4130 functions, adjust when we do. */
4131 gcc_checking_assert (!src_plats
->aggs
|| !jfunc
->agg
.items
);
4132 if (!inter
.exists ())
4133 inter
= copy_plats_to_inter (src_plats
, delta
);
4135 intersect_with_plats (src_plats
, &inter
, delta
);
4138 else if (jfunc
->agg
.items
)
4140 struct ipa_agg_jf_item
*item
;
4143 if (!inter
.exists ())
4144 for (unsigned i
= 0; i
< jfunc
->agg
.items
->length (); i
++)
4145 inter
.safe_push ((*jfunc
->agg
.items
)[i
]);
4147 FOR_EACH_VEC_ELT (inter
, k
, item
)
4150 bool found
= false;;
4155 while ((unsigned) l
< jfunc
->agg
.items
->length ())
4157 struct ipa_agg_jf_item
*ti
;
4158 ti
= &(*jfunc
->agg
.items
)[l
];
4159 if (ti
->offset
> item
->offset
)
4161 if (ti
->offset
== item
->offset
)
4163 gcc_checking_assert (ti
->value
);
4164 if (values_equal_for_ipcp_p (item
->value
,
4178 return vec
<ipa_agg_jf_item
>();
4183 /* Look at edges in CALLERS and collect all known aggregate values that arrive
4184 from all of them. */
4186 static struct ipa_agg_replacement_value
*
4187 find_aggregate_values_for_callers_subset (struct cgraph_node
*node
,
4188 vec
<cgraph_edge
*> callers
)
4190 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
4191 struct ipa_agg_replacement_value
*res
;
4192 struct ipa_agg_replacement_value
**tail
= &res
;
4193 struct cgraph_edge
*cs
;
4194 int i
, j
, count
= ipa_get_param_count (dest_info
);
4196 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4198 int c
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
4203 for (i
= 0; i
< count
; i
++)
4205 struct cgraph_edge
*cs
;
4206 vec
<ipa_agg_jf_item
> inter
= vNULL
;
4207 struct ipa_agg_jf_item
*item
;
4208 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (dest_info
, i
);
4211 /* Among other things, the following check should deal with all by_ref
4213 if (plats
->aggs_bottom
)
4216 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4218 inter
= intersect_aggregates_with_edge (cs
, i
, inter
);
4220 if (!inter
.exists ())
4224 FOR_EACH_VEC_ELT (inter
, j
, item
)
4226 struct ipa_agg_replacement_value
*v
;
4231 v
= ggc_alloc
<ipa_agg_replacement_value
> ();
4233 v
->offset
= item
->offset
;
4234 v
->value
= item
->value
;
4235 v
->by_ref
= plats
->aggs_by_ref
;
4241 if (inter
.exists ())
4248 /* Turn KNOWN_AGGS into a list of aggreate replacement values. */
4250 static struct ipa_agg_replacement_value
*
4251 known_aggs_to_agg_replacement_list (vec
<ipa_agg_jump_function
> known_aggs
)
4253 struct ipa_agg_replacement_value
*res
;
4254 struct ipa_agg_replacement_value
**tail
= &res
;
4255 struct ipa_agg_jump_function
*aggjf
;
4256 struct ipa_agg_jf_item
*item
;
4259 FOR_EACH_VEC_ELT (known_aggs
, i
, aggjf
)
4260 FOR_EACH_VEC_SAFE_ELT (aggjf
->items
, j
, item
)
4262 struct ipa_agg_replacement_value
*v
;
4263 v
= ggc_alloc
<ipa_agg_replacement_value
> ();
4265 v
->offset
= item
->offset
;
4266 v
->value
= item
->value
;
4267 v
->by_ref
= aggjf
->by_ref
;
4275 /* Determine whether CS also brings all scalar values that the NODE is
4279 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge
*cs
,
4280 struct cgraph_node
*node
)
4282 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
4283 int count
= ipa_get_param_count (dest_info
);
4284 struct ipa_node_params
*caller_info
;
4285 struct ipa_edge_args
*args
;
4288 caller_info
= IPA_NODE_REF (cs
->caller
);
4289 args
= IPA_EDGE_REF (cs
);
4290 for (i
= 0; i
< count
; i
++)
4292 struct ipa_jump_func
*jump_func
;
4295 val
= dest_info
->known_csts
[i
];
4299 if (i
>= ipa_get_cs_argument_count (args
))
4301 jump_func
= ipa_get_ith_jump_func (args
, i
);
4302 t
= ipa_value_from_jfunc (caller_info
, jump_func
);
4303 if (!t
|| !values_equal_for_ipcp_p (val
, t
))
4309 /* Determine whether CS also brings all aggregate values that NODE is
4312 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge
*cs
,
4313 struct cgraph_node
*node
)
4315 struct ipa_node_params
*orig_caller_info
= IPA_NODE_REF (cs
->caller
);
4316 struct ipa_node_params
*orig_node_info
;
4317 struct ipa_agg_replacement_value
*aggval
;
4320 aggval
= ipa_get_agg_replacements_for_node (node
);
4324 count
= ipa_get_param_count (IPA_NODE_REF (node
));
4325 ec
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
4327 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4328 if (aggval
->index
>= ec
)
4331 orig_node_info
= IPA_NODE_REF (IPA_NODE_REF (node
)->ipcp_orig_node
);
4332 if (orig_caller_info
->ipcp_orig_node
)
4333 orig_caller_info
= IPA_NODE_REF (orig_caller_info
->ipcp_orig_node
);
4335 for (i
= 0; i
< count
; i
++)
4337 static vec
<ipa_agg_jf_item
> values
= vec
<ipa_agg_jf_item
>();
4338 struct ipcp_param_lattices
*plats
;
4339 bool interesting
= false;
4340 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4341 if (aggval
->index
== i
)
4349 plats
= ipa_get_parm_lattices (orig_node_info
, aggval
->index
);
4350 if (plats
->aggs_bottom
)
4353 values
= intersect_aggregates_with_edge (cs
, i
, values
);
4354 if (!values
.exists ())
4357 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4358 if (aggval
->index
== i
)
4360 struct ipa_agg_jf_item
*item
;
4363 FOR_EACH_VEC_ELT (values
, j
, item
)
4365 && item
->offset
== av
->offset
4366 && values_equal_for_ipcp_p (item
->value
, av
->value
))
4381 /* Given an original NODE and a VAL for which we have already created a
4382 specialized clone, look whether there are incoming edges that still lead
4383 into the old node but now also bring the requested value and also conform to
4384 all other criteria such that they can be redirected the special node.
4385 This function can therefore redirect the final edge in a SCC. */
4387 template <typename valtype
>
4389 perhaps_add_new_callers (cgraph_node
*node
, ipcp_value
<valtype
> *val
)
4391 ipcp_value_source
<valtype
> *src
;
4392 gcov_type redirected_sum
= 0;
4394 for (src
= val
->sources
; src
; src
= src
->next
)
4396 struct cgraph_edge
*cs
= src
->cs
;
4399 if (cgraph_edge_brings_value_p (cs
, src
, node
)
4400 && cgraph_edge_brings_all_scalars_for_node (cs
, val
->spec_node
)
4401 && cgraph_edge_brings_all_agg_vals_for_node (cs
, val
->spec_node
))
4404 fprintf (dump_file
, " - adding an extra caller %s/%i"
4406 xstrdup_for_dump (cs
->caller
->name ()),
4408 xstrdup_for_dump (val
->spec_node
->name ()),
4409 val
->spec_node
->order
);
4411 cs
->redirect_callee_duplicating_thunks (val
->spec_node
);
4412 val
->spec_node
->expand_all_artificial_thunks ();
4413 redirected_sum
+= cs
->count
;
4415 cs
= get_next_cgraph_edge_clone (cs
);
4420 update_specialized_profile (val
->spec_node
, node
, redirected_sum
);
4423 /* Return true if KNOWN_CONTEXTS contain at least one useful context. */
4426 known_contexts_useful_p (vec
<ipa_polymorphic_call_context
> known_contexts
)
4428 ipa_polymorphic_call_context
*ctx
;
4431 FOR_EACH_VEC_ELT (known_contexts
, i
, ctx
)
4432 if (!ctx
->useless_p ())
4437 /* Return a copy of KNOWN_CSTS if it is not empty, otherwise return vNULL. */
4439 static vec
<ipa_polymorphic_call_context
>
4440 copy_useful_known_contexts (vec
<ipa_polymorphic_call_context
> known_contexts
)
4442 if (known_contexts_useful_p (known_contexts
))
4443 return known_contexts
.copy ();
4448 /* Copy KNOWN_CSTS and modify the copy according to VAL and INDEX. If
4449 non-empty, replace KNOWN_CONTEXTS with its copy too. */
4452 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
4453 vec
<ipa_polymorphic_call_context
> *known_contexts
,
4454 ipcp_value
<tree
> *val
,
4457 *known_csts
= known_csts
->copy ();
4458 *known_contexts
= copy_useful_known_contexts (*known_contexts
);
4459 (*known_csts
)[index
] = val
->value
;
4462 /* Replace KNOWN_CSTS with its copy. Also copy KNOWN_CONTEXTS and modify the
4463 copy according to VAL and INDEX. */
4466 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
4467 vec
<ipa_polymorphic_call_context
> *known_contexts
,
4468 ipcp_value
<ipa_polymorphic_call_context
> *val
,
4471 *known_csts
= known_csts
->copy ();
4472 *known_contexts
= known_contexts
->copy ();
4473 (*known_contexts
)[index
] = val
->value
;
4476 /* Return true if OFFSET indicates this was not an aggregate value or there is
4477 a replacement equivalent to VALUE, INDEX and OFFSET among those in the
4481 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*aggvals
,
4482 int index
, HOST_WIDE_INT offset
, tree value
)
4489 if (aggvals
->index
== index
4490 && aggvals
->offset
== offset
4491 && values_equal_for_ipcp_p (aggvals
->value
, value
))
4493 aggvals
= aggvals
->next
;
4498 /* Return true if offset is minus one because source of a polymorphic contect
4499 cannot be an aggregate value. */
4502 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*,
4503 int , HOST_WIDE_INT offset
,
4504 ipa_polymorphic_call_context
)
4506 return offset
== -1;
4509 /* Decide wheter to create a special version of NODE for value VAL of parameter
4510 at the given INDEX. If OFFSET is -1, the value is for the parameter itself,
4511 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS,
4512 KNOWN_CONTEXTS and KNOWN_AGGS describe the other already known values. */
4514 template <typename valtype
>
4516 decide_about_value (struct cgraph_node
*node
, int index
, HOST_WIDE_INT offset
,
4517 ipcp_value
<valtype
> *val
, vec
<tree
> known_csts
,
4518 vec
<ipa_polymorphic_call_context
> known_contexts
)
4520 struct ipa_agg_replacement_value
*aggvals
;
4521 int freq_sum
, caller_count
;
4522 gcov_type count_sum
;
4523 vec
<cgraph_edge
*> callers
;
4527 perhaps_add_new_callers (node
, val
);
4530 else if (val
->local_size_cost
+ overall_size
> max_new_size
)
4532 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4533 fprintf (dump_file
, " Ignoring candidate value because "
4534 "max_new_size would be reached with %li.\n",
4535 val
->local_size_cost
+ overall_size
);
4538 else if (!get_info_about_necessary_edges (val
, node
, &freq_sum
, &count_sum
,
4542 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4544 fprintf (dump_file
, " - considering value ");
4545 print_ipcp_constant_value (dump_file
, val
->value
);
4546 fprintf (dump_file
, " for ");
4547 ipa_dump_param (dump_file
, IPA_NODE_REF (node
), index
);
4549 fprintf (dump_file
, ", offset: " HOST_WIDE_INT_PRINT_DEC
, offset
);
4550 fprintf (dump_file
, " (caller_count: %i)\n", caller_count
);
4553 if (!good_cloning_opportunity_p (node
, val
->local_time_benefit
,
4554 freq_sum
, count_sum
,
4555 val
->local_size_cost
)
4556 && !good_cloning_opportunity_p (node
,
4557 val
->local_time_benefit
4558 + val
->prop_time_benefit
,
4559 freq_sum
, count_sum
,
4560 val
->local_size_cost
4561 + val
->prop_size_cost
))
4565 fprintf (dump_file
, " Creating a specialized node of %s/%i.\n",
4566 node
->name (), node
->order
);
4568 callers
= gather_edges_for_value (val
, node
, caller_count
);
4570 modify_known_vectors_with_val (&known_csts
, &known_contexts
, val
, index
);
4573 known_csts
= known_csts
.copy ();
4574 known_contexts
= copy_useful_known_contexts (known_contexts
);
4576 find_more_scalar_values_for_callers_subset (node
, known_csts
, callers
);
4577 find_more_contexts_for_caller_subset (node
, &known_contexts
, callers
);
4578 aggvals
= find_aggregate_values_for_callers_subset (node
, callers
);
4579 gcc_checking_assert (ipcp_val_agg_replacement_ok_p (aggvals
, index
,
4580 offset
, val
->value
));
4581 val
->spec_node
= create_specialized_node (node
, known_csts
, known_contexts
,
4583 overall_size
+= val
->local_size_cost
;
4585 /* TODO: If for some lattice there is only one other known value
4586 left, make a special node for it too. */
4591 /* Decide whether and what specialized clones of NODE should be created. */
4594 decide_whether_version_node (struct cgraph_node
*node
)
4596 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
4597 int i
, count
= ipa_get_param_count (info
);
4598 vec
<tree
> known_csts
;
4599 vec
<ipa_polymorphic_call_context
> known_contexts
;
4600 vec
<ipa_agg_jump_function
> known_aggs
= vNULL
;
4606 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4607 fprintf (dump_file
, "\nEvaluating opportunities for %s/%i.\n",
4608 node
->name (), node
->order
);
4610 gather_context_independent_values (info
, &known_csts
, &known_contexts
,
4611 info
->do_clone_for_all_contexts
? &known_aggs
4614 for (i
= 0; i
< count
;i
++)
4616 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4617 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
4618 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
4623 ipcp_value
<tree
> *val
;
4624 for (val
= lat
->values
; val
; val
= val
->next
)
4625 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
4629 if (!plats
->aggs_bottom
)
4631 struct ipcp_agg_lattice
*aglat
;
4632 ipcp_value
<tree
> *val
;
4633 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
4634 if (!aglat
->bottom
&& aglat
->values
4635 /* If the following is false, the one value is in
4637 && (plats
->aggs_contain_variable
4638 || !aglat
->is_single_const ()))
4639 for (val
= aglat
->values
; val
; val
= val
->next
)
4640 ret
|= decide_about_value (node
, i
, aglat
->offset
, val
,
4641 known_csts
, known_contexts
);
4645 && known_contexts
[i
].useless_p ())
4647 ipcp_value
<ipa_polymorphic_call_context
> *val
;
4648 for (val
= ctxlat
->values
; val
; val
= val
->next
)
4649 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
4653 info
= IPA_NODE_REF (node
);
4656 if (info
->do_clone_for_all_contexts
)
4658 struct cgraph_node
*clone
;
4659 vec
<cgraph_edge
*> callers
;
4662 fprintf (dump_file
, " - Creating a specialized node of %s/%i "
4663 "for all known contexts.\n", node
->name (),
4666 callers
= node
->collect_callers ();
4668 if (!known_contexts_useful_p (known_contexts
))
4670 known_contexts
.release ();
4671 known_contexts
= vNULL
;
4673 clone
= create_specialized_node (node
, known_csts
, known_contexts
,
4674 known_aggs_to_agg_replacement_list (known_aggs
),
4676 info
= IPA_NODE_REF (node
);
4677 info
->do_clone_for_all_contexts
= false;
4678 IPA_NODE_REF (clone
)->is_all_contexts_clone
= true;
4679 for (i
= 0; i
< count
; i
++)
4680 vec_free (known_aggs
[i
].items
);
4681 known_aggs
.release ();
4686 known_csts
.release ();
4687 known_contexts
.release ();
4693 /* Transitively mark all callees of NODE within the same SCC as not dead. */
4696 spread_undeadness (struct cgraph_node
*node
)
4698 struct cgraph_edge
*cs
;
4700 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
4701 if (ipa_edge_within_scc (cs
))
4703 struct cgraph_node
*callee
;
4704 struct ipa_node_params
*info
;
4706 callee
= cs
->callee
->function_symbol (NULL
);
4707 info
= IPA_NODE_REF (callee
);
4709 if (info
->node_dead
)
4711 info
->node_dead
= 0;
4712 spread_undeadness (callee
);
4717 /* Return true if NODE has a caller from outside of its SCC that is not
4718 dead. Worker callback for cgraph_for_node_and_aliases. */
4721 has_undead_caller_from_outside_scc_p (struct cgraph_node
*node
,
4722 void *data ATTRIBUTE_UNUSED
)
4724 struct cgraph_edge
*cs
;
4726 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
4727 if (cs
->caller
->thunk
.thunk_p
4728 && cs
->caller
->call_for_symbol_thunks_and_aliases
4729 (has_undead_caller_from_outside_scc_p
, NULL
, true))
4731 else if (!ipa_edge_within_scc (cs
)
4732 && !IPA_NODE_REF (cs
->caller
)->node_dead
)
4738 /* Identify nodes within the same SCC as NODE which are no longer needed
4739 because of new clones and will be removed as unreachable. */
4742 identify_dead_nodes (struct cgraph_node
*node
)
4744 struct cgraph_node
*v
;
4745 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4747 && !v
->call_for_symbol_thunks_and_aliases
4748 (has_undead_caller_from_outside_scc_p
, NULL
, true))
4749 IPA_NODE_REF (v
)->node_dead
= 1;
4751 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4752 if (!IPA_NODE_REF (v
)->node_dead
)
4753 spread_undeadness (v
);
4755 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4757 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4758 if (IPA_NODE_REF (v
)->node_dead
)
4759 fprintf (dump_file
, " Marking node as dead: %s/%i.\n",
4760 v
->name (), v
->order
);
4764 /* The decision stage. Iterate over the topological order of call graph nodes
4765 TOPO and make specialized clones if deemed beneficial. */
4768 ipcp_decision_stage (struct ipa_topo_info
*topo
)
4773 fprintf (dump_file
, "\nIPA decision stage:\n\n");
4775 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
4777 struct cgraph_node
*node
= topo
->order
[i
];
4778 bool change
= false, iterate
= true;
4782 struct cgraph_node
*v
;
4784 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4785 if (v
->has_gimple_body_p ()
4786 && ipcp_versionable_function_p (v
))
4787 iterate
|= decide_whether_version_node (v
);
4792 identify_dead_nodes (node
);
4796 /* Look up all the bits information that we have discovered and copy it over
4797 to the transformation summary. */
4800 ipcp_store_bits_results (void)
4804 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
4806 ipa_node_params
*info
= IPA_NODE_REF (node
);
4807 bool dumped_sth
= false;
4808 bool found_useful_result
= false;
4810 if (!opt_for_fn (node
->decl
, flag_ipa_bit_cp
))
4813 fprintf (dump_file
, "Not considering %s for ipa bitwise propagation "
4814 "; -fipa-bit-cp: disabled.\n",
4819 if (info
->ipcp_orig_node
)
4820 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
4822 unsigned count
= ipa_get_param_count (info
);
4823 for (unsigned i
= 0; i
< count
; i
++)
4825 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4826 if (plats
->bits_lattice
.constant_p ())
4828 found_useful_result
= true;
4833 if (!found_useful_result
)
4836 ipcp_grow_transformations_if_necessary ();
4837 ipcp_transformation_summary
*ts
= ipcp_get_transformation_summary (node
);
4838 vec_safe_reserve_exact (ts
->bits
, count
);
4840 for (unsigned i
= 0; i
< count
; i
++)
4842 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4843 ipa_bits bits_jfunc
;
4845 if (plats
->bits_lattice
.constant_p ())
4847 bits_jfunc
.known
= true;
4848 bits_jfunc
.value
= plats
->bits_lattice
.get_value ();
4849 bits_jfunc
.mask
= plats
->bits_lattice
.get_mask ();
4852 bits_jfunc
.known
= false;
4854 ts
->bits
->quick_push (bits_jfunc
);
4855 if (!dump_file
|| !bits_jfunc
.known
)
4859 fprintf (dump_file
, "Propagated bits info for function %s/%i:\n",
4860 node
->name (), node
->order
);
4863 fprintf (dump_file
, " param %i: value = ", i
);
4864 print_hex (bits_jfunc
.value
, dump_file
);
4865 fprintf (dump_file
, ", mask = ");
4866 print_hex (bits_jfunc
.mask
, dump_file
);
4867 fprintf (dump_file
, "\n");
4872 /* Look up all VR information that we have discovered and copy it over
4873 to the transformation summary. */
4876 ipcp_store_vr_results (void)
4880 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
4882 ipa_node_params
*info
= IPA_NODE_REF (node
);
4883 bool found_useful_result
= false;
4885 if (!opt_for_fn (node
->decl
, flag_ipa_vrp
))
4888 fprintf (dump_file
, "Not considering %s for VR discovery "
4889 "and propagate; -fipa-ipa-vrp: disabled.\n",
4894 if (info
->ipcp_orig_node
)
4895 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
4897 unsigned count
= ipa_get_param_count (info
);
4898 for (unsigned i
= 0; i
< count
; i
++)
4900 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4901 if (!plats
->m_value_range
.bottom_p ()
4902 && !plats
->m_value_range
.top_p ())
4904 found_useful_result
= true;
4908 if (!found_useful_result
)
4911 ipcp_grow_transformations_if_necessary ();
4912 ipcp_transformation_summary
*ts
= ipcp_get_transformation_summary (node
);
4913 vec_safe_reserve_exact (ts
->m_vr
, count
);
4915 for (unsigned i
= 0; i
< count
; i
++)
4917 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4920 if (!plats
->m_value_range
.bottom_p ()
4921 && !plats
->m_value_range
.top_p ())
4924 vr
.type
= plats
->m_value_range
.m_vr
.type
;
4925 vr
.min
= plats
->m_value_range
.m_vr
.min
;
4926 vr
.max
= plats
->m_value_range
.m_vr
.max
;
4931 vr
.type
= VR_VARYING
;
4932 vr
.min
= vr
.max
= wi::zero (INT_TYPE_SIZE
);
4934 ts
->m_vr
->quick_push (vr
);
4939 /* The IPCP driver. */
4944 struct cgraph_2edge_hook_list
*edge_duplication_hook_holder
;
4945 struct cgraph_edge_hook_list
*edge_removal_hook_holder
;
4946 struct ipa_topo_info topo
;
4948 ipa_check_create_node_params ();
4949 ipa_check_create_edge_args ();
4950 grow_edge_clone_vectors ();
4951 edge_duplication_hook_holder
=
4952 symtab
->add_edge_duplication_hook (&ipcp_edge_duplication_hook
, NULL
);
4953 edge_removal_hook_holder
=
4954 symtab
->add_edge_removal_hook (&ipcp_edge_removal_hook
, NULL
);
4958 fprintf (dump_file
, "\nIPA structures before propagation:\n");
4959 if (dump_flags
& TDF_DETAILS
)
4960 ipa_print_all_params (dump_file
);
4961 ipa_print_all_jump_functions (dump_file
);
4964 /* Topological sort. */
4965 build_toporder_info (&topo
);
4966 /* Do the interprocedural propagation. */
4967 ipcp_propagate_stage (&topo
);
4968 /* Decide what constant propagation and cloning should be performed. */
4969 ipcp_decision_stage (&topo
);
4970 /* Store results of bits propagation. */
4971 ipcp_store_bits_results ();
4972 /* Store results of value range propagation. */
4973 ipcp_store_vr_results ();
4975 /* Free all IPCP structures. */
4976 free_toporder_info (&topo
);
4977 next_edge_clone
.release ();
4978 prev_edge_clone
.release ();
4979 symtab
->remove_edge_removal_hook (edge_removal_hook_holder
);
4980 symtab
->remove_edge_duplication_hook (edge_duplication_hook_holder
);
4981 ipa_free_all_structures_after_ipa_cp ();
4983 fprintf (dump_file
, "\nIPA constant propagation end\n");
4987 /* Initialization and computation of IPCP data structures. This is the initial
4988 intraprocedural analysis of functions, which gathers information to be
4989 propagated later on. */
4992 ipcp_generate_summary (void)
4994 struct cgraph_node
*node
;
4997 fprintf (dump_file
, "\nIPA constant propagation start:\n");
4998 ipa_register_cgraph_hooks ();
5000 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5001 ipa_analyze_node (node
);
5004 /* Write ipcp summary for nodes in SET. */
5007 ipcp_write_summary (void)
5009 ipa_prop_write_jump_functions ();
5012 /* Read ipcp summary. */
5015 ipcp_read_summary (void)
5017 ipa_prop_read_jump_functions ();
5022 const pass_data pass_data_ipa_cp
=
5024 IPA_PASS
, /* type */
5026 OPTGROUP_NONE
, /* optinfo_flags */
5027 TV_IPA_CONSTANT_PROP
, /* tv_id */
5028 0, /* properties_required */
5029 0, /* properties_provided */
5030 0, /* properties_destroyed */
5031 0, /* todo_flags_start */
5032 ( TODO_dump_symtab
| TODO_remove_functions
), /* todo_flags_finish */
5035 class pass_ipa_cp
: public ipa_opt_pass_d
5038 pass_ipa_cp (gcc::context
*ctxt
)
5039 : ipa_opt_pass_d (pass_data_ipa_cp
, ctxt
,
5040 ipcp_generate_summary
, /* generate_summary */
5041 ipcp_write_summary
, /* write_summary */
5042 ipcp_read_summary
, /* read_summary */
5043 ipcp_write_transformation_summaries
, /*
5044 write_optimization_summary */
5045 ipcp_read_transformation_summaries
, /*
5046 read_optimization_summary */
5047 NULL
, /* stmt_fixup */
5048 0, /* function_transform_todo_flags_start */
5049 ipcp_transform_function
, /* function_transform */
5050 NULL
) /* variable_transform */
5053 /* opt_pass methods: */
5054 virtual bool gate (function
*)
5056 /* FIXME: We should remove the optimize check after we ensure we never run
5057 IPA passes when not optimizing. */
5058 return (flag_ipa_cp
&& optimize
) || in_lto_p
;
5061 virtual unsigned int execute (function
*) { return ipcp_driver (); }
5063 }; // class pass_ipa_cp
5068 make_pass_ipa_cp (gcc::context
*ctxt
)
5070 return new pass_ipa_cp (ctxt
);
5073 /* Reset all state within ipa-cp.c so that we can rerun the compiler
5074 within the same process. For use by toplev::finalize. */
5077 ipa_cp_c_finalize (void)