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 res
= fold_unary (ipa_get_jf_pass_through_operation (jfunc
),
1224 TREE_TYPE (input
), input
);
1227 if (TREE_CODE_CLASS (ipa_get_jf_pass_through_operation (jfunc
))
1229 restype
= boolean_type_node
;
1231 restype
= TREE_TYPE (input
);
1232 res
= fold_binary (ipa_get_jf_pass_through_operation (jfunc
), restype
,
1233 input
, ipa_get_jf_pass_through_operand (jfunc
));
1235 if (res
&& !is_gimple_ip_invariant (res
))
1241 /* Return the result of an ancestor jump function JFUNC on the constant value
1242 INPUT. Return NULL_TREE if that cannot be determined. */
1245 ipa_get_jf_ancestor_result (struct ipa_jump_func
*jfunc
, tree input
)
1247 gcc_checking_assert (TREE_CODE (input
) != TREE_BINFO
);
1248 if (TREE_CODE (input
) == ADDR_EXPR
)
1250 tree t
= TREE_OPERAND (input
, 0);
1251 t
= build_ref_for_offset (EXPR_LOCATION (t
), t
,
1252 ipa_get_jf_ancestor_offset (jfunc
), false,
1253 ptr_type_node
, NULL
, false);
1254 return build_fold_addr_expr (t
);
1260 /* Determine whether JFUNC evaluates to a single known constant value and if
1261 so, return it. Otherwise return NULL. INFO describes the caller node or
1262 the one it is inlined to, so that pass-through jump functions can be
1266 ipa_value_from_jfunc (struct ipa_node_params
*info
, struct ipa_jump_func
*jfunc
)
1268 if (jfunc
->type
== IPA_JF_CONST
)
1269 return ipa_get_jf_constant (jfunc
);
1270 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1271 || jfunc
->type
== IPA_JF_ANCESTOR
)
1276 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1277 idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1279 idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1281 if (info
->ipcp_orig_node
)
1282 input
= info
->known_csts
[idx
];
1285 ipcp_lattice
<tree
> *lat
;
1288 || idx
>= ipa_get_param_count (info
))
1290 lat
= ipa_get_scalar_lat (info
, idx
);
1291 if (!lat
->is_single_const ())
1293 input
= lat
->values
->value
;
1299 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1300 return ipa_get_jf_pass_through_result (jfunc
, input
);
1302 return ipa_get_jf_ancestor_result (jfunc
, input
);
1308 /* Determie whether JFUNC evaluates to single known polymorphic context, given
1309 that INFO describes the caller node or the one it is inlined to, CS is the
1310 call graph edge corresponding to JFUNC and CSIDX index of the described
1313 ipa_polymorphic_call_context
1314 ipa_context_from_jfunc (ipa_node_params
*info
, cgraph_edge
*cs
, int csidx
,
1315 ipa_jump_func
*jfunc
)
1317 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
1318 ipa_polymorphic_call_context ctx
;
1319 ipa_polymorphic_call_context
*edge_ctx
1320 = cs
? ipa_get_ith_polymorhic_call_context (args
, csidx
) : NULL
;
1322 if (edge_ctx
&& !edge_ctx
->useless_p ())
1325 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1326 || jfunc
->type
== IPA_JF_ANCESTOR
)
1328 ipa_polymorphic_call_context srcctx
;
1330 bool type_preserved
= true;
1331 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1333 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1335 type_preserved
= ipa_get_jf_pass_through_type_preserved (jfunc
);
1336 srcidx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1340 type_preserved
= ipa_get_jf_ancestor_type_preserved (jfunc
);
1341 srcidx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1343 if (info
->ipcp_orig_node
)
1345 if (info
->known_contexts
.exists ())
1346 srcctx
= info
->known_contexts
[srcidx
];
1351 || srcidx
>= ipa_get_param_count (info
))
1353 ipcp_lattice
<ipa_polymorphic_call_context
> *lat
;
1354 lat
= ipa_get_poly_ctx_lat (info
, srcidx
);
1355 if (!lat
->is_single_const ())
1357 srcctx
= lat
->values
->value
;
1359 if (srcctx
.useless_p ())
1361 if (jfunc
->type
== IPA_JF_ANCESTOR
)
1362 srcctx
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
1363 if (!type_preserved
)
1364 srcctx
.possible_dynamic_type_change (cs
->in_polymorphic_cdtor
);
1365 srcctx
.combine_with (ctx
);
1372 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
1373 bottom, not containing a variable component and without any known value at
1377 ipcp_verify_propagated_values (void)
1379 struct cgraph_node
*node
;
1381 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
1383 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1384 int i
, count
= ipa_get_param_count (info
);
1386 for (i
= 0; i
< count
; i
++)
1388 ipcp_lattice
<tree
> *lat
= ipa_get_scalar_lat (info
, i
);
1391 && !lat
->contains_variable
1392 && lat
->values_count
== 0)
1396 symtab_node::dump_table (dump_file
);
1397 fprintf (dump_file
, "\nIPA lattices after constant "
1398 "propagation, before gcc_unreachable:\n");
1399 print_all_lattices (dump_file
, true, false);
1408 /* Return true iff X and Y should be considered equal values by IPA-CP. */
1411 values_equal_for_ipcp_p (tree x
, tree y
)
1413 gcc_checking_assert (x
!= NULL_TREE
&& y
!= NULL_TREE
);
1418 if (TREE_CODE (x
) == ADDR_EXPR
1419 && TREE_CODE (y
) == ADDR_EXPR
1420 && TREE_CODE (TREE_OPERAND (x
, 0)) == CONST_DECL
1421 && TREE_CODE (TREE_OPERAND (y
, 0)) == CONST_DECL
)
1422 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x
, 0)),
1423 DECL_INITIAL (TREE_OPERAND (y
, 0)), 0);
1425 return operand_equal_p (x
, y
, 0);
1428 /* Return true iff X and Y should be considered equal contexts by IPA-CP. */
1431 values_equal_for_ipcp_p (ipa_polymorphic_call_context x
,
1432 ipa_polymorphic_call_context y
)
1434 return x
.equal_to (y
);
1438 /* Add a new value source to the value represented by THIS, marking that a
1439 value comes from edge CS and (if the underlying jump function is a
1440 pass-through or an ancestor one) from a caller value SRC_VAL of a caller
1441 parameter described by SRC_INDEX. OFFSET is negative if the source was the
1442 scalar value of the parameter itself or the offset within an aggregate. */
1444 template <typename valtype
>
1446 ipcp_value
<valtype
>::add_source (cgraph_edge
*cs
, ipcp_value
*src_val
,
1447 int src_idx
, HOST_WIDE_INT offset
)
1449 ipcp_value_source
<valtype
> *src
;
1451 src
= new (ipcp_sources_pool
.allocate ()) ipcp_value_source
<valtype
>;
1452 src
->offset
= offset
;
1455 src
->index
= src_idx
;
1457 src
->next
= sources
;
1461 /* Allocate a new ipcp_value holding a tree constant, initialize its value to
1462 SOURCE and clear all other fields. */
1464 static ipcp_value
<tree
> *
1465 allocate_and_init_ipcp_value (tree source
)
1467 ipcp_value
<tree
> *val
;
1469 val
= ipcp_cst_values_pool
.allocate ();
1470 memset (val
, 0, sizeof (*val
));
1471 val
->value
= source
;
1475 /* Allocate a new ipcp_value holding a polymorphic context, initialize its
1476 value to SOURCE and clear all other fields. */
1478 static ipcp_value
<ipa_polymorphic_call_context
> *
1479 allocate_and_init_ipcp_value (ipa_polymorphic_call_context source
)
1481 ipcp_value
<ipa_polymorphic_call_context
> *val
;
1484 val
= ipcp_poly_ctx_values_pool
.allocate ();
1485 memset (val
, 0, sizeof (*val
));
1486 val
->value
= source
;
1490 /* Try to add NEWVAL to LAT, potentially creating a new ipcp_value for it. CS,
1491 SRC_VAL SRC_INDEX and OFFSET are meant for add_source and have the same
1492 meaning. OFFSET -1 means the source is scalar and not a part of an
1495 template <typename valtype
>
1497 ipcp_lattice
<valtype
>::add_value (valtype newval
, cgraph_edge
*cs
,
1498 ipcp_value
<valtype
> *src_val
,
1499 int src_idx
, HOST_WIDE_INT offset
)
1501 ipcp_value
<valtype
> *val
;
1506 for (val
= values
; val
; val
= val
->next
)
1507 if (values_equal_for_ipcp_p (val
->value
, newval
))
1509 if (ipa_edge_within_scc (cs
))
1511 ipcp_value_source
<valtype
> *s
;
1512 for (s
= val
->sources
; s
; s
= s
->next
)
1519 val
->add_source (cs
, src_val
, src_idx
, offset
);
1523 if (values_count
== PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE
))
1525 /* We can only free sources, not the values themselves, because sources
1526 of other values in this SCC might point to them. */
1527 for (val
= values
; val
; val
= val
->next
)
1529 while (val
->sources
)
1531 ipcp_value_source
<valtype
> *src
= val
->sources
;
1532 val
->sources
= src
->next
;
1533 ipcp_sources_pool
.remove ((ipcp_value_source
<tree
>*)src
);
1538 return set_to_bottom ();
1542 val
= allocate_and_init_ipcp_value (newval
);
1543 val
->add_source (cs
, src_val
, src_idx
, offset
);
1549 /* Propagate values through a pass-through jump function JFUNC associated with
1550 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1551 is the index of the source parameter. */
1554 propagate_vals_across_pass_through (cgraph_edge
*cs
, ipa_jump_func
*jfunc
,
1555 ipcp_lattice
<tree
> *src_lat
,
1556 ipcp_lattice
<tree
> *dest_lat
, int src_idx
)
1558 ipcp_value
<tree
> *src_val
;
1561 /* Do not create new values when propagating within an SCC because if there
1562 are arithmetic functions with circular dependencies, there is infinite
1563 number of them and we would just make lattices bottom. */
1564 if ((ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1565 && ipa_edge_within_scc (cs
))
1566 ret
= dest_lat
->set_contains_variable ();
1568 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1570 tree cstval
= ipa_get_jf_pass_through_result (jfunc
, src_val
->value
);
1573 ret
|= dest_lat
->add_value (cstval
, cs
, src_val
, src_idx
);
1575 ret
|= dest_lat
->set_contains_variable ();
1581 /* Propagate values through an ancestor jump function JFUNC associated with
1582 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1583 is the index of the source parameter. */
1586 propagate_vals_across_ancestor (struct cgraph_edge
*cs
,
1587 struct ipa_jump_func
*jfunc
,
1588 ipcp_lattice
<tree
> *src_lat
,
1589 ipcp_lattice
<tree
> *dest_lat
, int src_idx
)
1591 ipcp_value
<tree
> *src_val
;
1594 if (ipa_edge_within_scc (cs
))
1595 return dest_lat
->set_contains_variable ();
1597 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1599 tree t
= ipa_get_jf_ancestor_result (jfunc
, src_val
->value
);
1602 ret
|= dest_lat
->add_value (t
, cs
, src_val
, src_idx
);
1604 ret
|= dest_lat
->set_contains_variable ();
1610 /* Propagate scalar values across jump function JFUNC that is associated with
1611 edge CS and put the values into DEST_LAT. */
1614 propagate_scalar_across_jump_function (struct cgraph_edge
*cs
,
1615 struct ipa_jump_func
*jfunc
,
1616 ipcp_lattice
<tree
> *dest_lat
)
1618 if (dest_lat
->bottom
)
1621 if (jfunc
->type
== IPA_JF_CONST
)
1623 tree val
= ipa_get_jf_constant (jfunc
);
1624 return dest_lat
->add_value (val
, cs
, NULL
, 0);
1626 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
1627 || jfunc
->type
== IPA_JF_ANCESTOR
)
1629 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1630 ipcp_lattice
<tree
> *src_lat
;
1634 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1635 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1637 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1639 src_lat
= ipa_get_scalar_lat (caller_info
, src_idx
);
1640 if (src_lat
->bottom
)
1641 return dest_lat
->set_contains_variable ();
1643 /* If we would need to clone the caller and cannot, do not propagate. */
1644 if (!ipcp_versionable_function_p (cs
->caller
)
1645 && (src_lat
->contains_variable
1646 || (src_lat
->values_count
> 1)))
1647 return dest_lat
->set_contains_variable ();
1649 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1650 ret
= propagate_vals_across_pass_through (cs
, jfunc
, src_lat
,
1653 ret
= propagate_vals_across_ancestor (cs
, jfunc
, src_lat
, dest_lat
,
1656 if (src_lat
->contains_variable
)
1657 ret
|= dest_lat
->set_contains_variable ();
1662 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1663 use it for indirect inlining), we should propagate them too. */
1664 return dest_lat
->set_contains_variable ();
1667 /* Propagate scalar values across jump function JFUNC that is associated with
1668 edge CS and describes argument IDX and put the values into DEST_LAT. */
1671 propagate_context_across_jump_function (cgraph_edge
*cs
,
1672 ipa_jump_func
*jfunc
, int idx
,
1673 ipcp_lattice
<ipa_polymorphic_call_context
> *dest_lat
)
1675 ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
1676 if (dest_lat
->bottom
)
1679 bool added_sth
= false;
1680 bool type_preserved
= true;
1682 ipa_polymorphic_call_context edge_ctx
, *edge_ctx_ptr
1683 = ipa_get_ith_polymorhic_call_context (args
, idx
);
1686 edge_ctx
= *edge_ctx_ptr
;
1688 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1689 || jfunc
->type
== IPA_JF_ANCESTOR
)
1691 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1693 ipcp_lattice
<ipa_polymorphic_call_context
> *src_lat
;
1695 /* TODO: Once we figure out how to propagate speculations, it will
1696 probably be a good idea to switch to speculation if type_preserved is
1697 not set instead of punting. */
1698 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1700 if (ipa_get_jf_pass_through_operation (jfunc
) != NOP_EXPR
)
1702 type_preserved
= ipa_get_jf_pass_through_type_preserved (jfunc
);
1703 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1707 type_preserved
= ipa_get_jf_ancestor_type_preserved (jfunc
);
1708 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1711 src_lat
= ipa_get_poly_ctx_lat (caller_info
, src_idx
);
1712 /* If we would need to clone the caller and cannot, do not propagate. */
1713 if (!ipcp_versionable_function_p (cs
->caller
)
1714 && (src_lat
->contains_variable
1715 || (src_lat
->values_count
> 1)))
1718 ipcp_value
<ipa_polymorphic_call_context
> *src_val
;
1719 for (src_val
= src_lat
->values
; src_val
; src_val
= src_val
->next
)
1721 ipa_polymorphic_call_context cur
= src_val
->value
;
1723 if (!type_preserved
)
1724 cur
.possible_dynamic_type_change (cs
->in_polymorphic_cdtor
);
1725 if (jfunc
->type
== IPA_JF_ANCESTOR
)
1726 cur
.offset_by (ipa_get_jf_ancestor_offset (jfunc
));
1727 /* TODO: In cases we know how the context is going to be used,
1728 we can improve the result by passing proper OTR_TYPE. */
1729 cur
.combine_with (edge_ctx
);
1730 if (!cur
.useless_p ())
1732 if (src_lat
->contains_variable
1733 && !edge_ctx
.equal_to (cur
))
1734 ret
|= dest_lat
->set_contains_variable ();
1735 ret
|= dest_lat
->add_value (cur
, cs
, src_val
, src_idx
);
1745 if (!edge_ctx
.useless_p ())
1746 ret
|= dest_lat
->add_value (edge_ctx
, cs
);
1748 ret
|= dest_lat
->set_contains_variable ();
1754 /* Propagate bits across jfunc that is associated with
1755 edge cs and update dest_lattice accordingly. */
1758 propagate_bits_across_jump_function (cgraph_edge
*cs
, int idx
,
1759 ipa_jump_func
*jfunc
,
1760 ipcp_bits_lattice
*dest_lattice
)
1762 if (dest_lattice
->bottom_p ())
1765 enum availability availability
;
1766 cgraph_node
*callee
= cs
->callee
->function_symbol (&availability
);
1767 struct ipa_node_params
*callee_info
= IPA_NODE_REF (callee
);
1768 tree parm_type
= ipa_get_type (callee_info
, idx
);
1770 /* For K&R C programs, ipa_get_type() could return NULL_TREE.
1771 Avoid the transform for these cases. */
1774 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1775 fprintf (dump_file
, "Setting dest_lattice to bottom, because"
1776 " param %i type is NULL for %s\n", idx
,
1777 cs
->callee
->name ());
1779 return dest_lattice
->set_to_bottom ();
1782 unsigned precision
= TYPE_PRECISION (parm_type
);
1783 signop sgn
= TYPE_SIGN (parm_type
);
1785 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1786 || jfunc
->type
== IPA_JF_ANCESTOR
)
1788 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1789 tree operand
= NULL_TREE
;
1790 enum tree_code code
;
1793 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1795 code
= ipa_get_jf_pass_through_operation (jfunc
);
1796 src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1797 if (code
!= NOP_EXPR
)
1798 operand
= ipa_get_jf_pass_through_operand (jfunc
);
1802 code
= POINTER_PLUS_EXPR
;
1803 src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
1804 unsigned HOST_WIDE_INT offset
= ipa_get_jf_ancestor_offset (jfunc
) / BITS_PER_UNIT
;
1805 operand
= build_int_cstu (size_type_node
, offset
);
1808 struct ipcp_param_lattices
*src_lats
1809 = ipa_get_parm_lattices (caller_info
, src_idx
);
1811 /* Try to propagate bits if src_lattice is bottom, but jfunc is known.
1817 Assume lattice for x is bottom, however we can still propagate
1818 result of x & 0xff == 0xff, which gets computed during ccp1 pass
1819 and we store it in jump function during analysis stage. */
1821 if (src_lats
->bits_lattice
.bottom_p ()
1822 && jfunc
->bits
.known
)
1823 return dest_lattice
->meet_with (jfunc
->bits
.value
, jfunc
->bits
.mask
,
1826 return dest_lattice
->meet_with (src_lats
->bits_lattice
, precision
, sgn
,
1830 else if (jfunc
->type
== IPA_JF_ANCESTOR
)
1831 return dest_lattice
->set_to_bottom ();
1833 else if (jfunc
->bits
.known
)
1834 return dest_lattice
->meet_with (jfunc
->bits
.value
, jfunc
->bits
.mask
, precision
);
1837 return dest_lattice
->set_to_bottom ();
1840 /* Propagate value range across jump function JFUNC that is associated with
1841 edge CS with param of callee of PARAM_TYPE and update DEST_PLATS
1845 propagate_vr_across_jump_function (cgraph_edge
*cs
, ipa_jump_func
*jfunc
,
1846 struct ipcp_param_lattices
*dest_plats
,
1849 struct ipcp_param_lattices
*src_lats
;
1850 ipcp_vr_lattice
*dest_lat
= &dest_plats
->m_value_range
;
1852 if (dest_lat
->bottom_p ())
1856 || (!INTEGRAL_TYPE_P (param_type
)
1857 && !POINTER_TYPE_P (param_type
)))
1858 return dest_lat
->set_to_bottom ();
1860 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
1862 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
1863 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
1864 src_lats
= ipa_get_parm_lattices (caller_info
, src_idx
);
1866 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
1867 return dest_lat
->meet_with (src_lats
->m_value_range
);
1869 && (TREE_CODE_CLASS (ipa_get_jf_pass_through_operation (jfunc
))
1873 memset (&vr
, 0, sizeof (vr
));
1874 tree operand_type
= ipa_get_type (caller_info
, src_idx
);
1875 enum tree_code operation
= ipa_get_jf_pass_through_operation (jfunc
);
1877 if (src_lats
->m_value_range
.bottom_p ())
1878 return dest_lat
->set_to_bottom ();
1880 extract_range_from_unary_expr (&vr
,
1883 &src_lats
->m_value_range
.m_vr
,
1885 if (vr
.type
== VR_RANGE
1886 || vr
.type
== VR_ANTI_RANGE
)
1887 return dest_lat
->meet_with (&vr
);
1890 else if (jfunc
->type
== IPA_JF_CONST
)
1892 tree val
= ipa_get_jf_constant (jfunc
);
1893 if (TREE_CODE (val
) == INTEGER_CST
)
1895 val
= fold_convert (param_type
, val
);
1896 if (TREE_OVERFLOW_P (val
))
1897 val
= drop_tree_overflow (val
);
1898 jfunc
->vr_known
= true;
1899 jfunc
->m_vr
.type
= VR_RANGE
;
1900 jfunc
->m_vr
.min
= val
;
1901 jfunc
->m_vr
.max
= val
;
1902 return dest_lat
->meet_with (&jfunc
->m_vr
);
1906 if (jfunc
->vr_known
)
1907 return dest_lat
->meet_with (&jfunc
->m_vr
);
1909 return dest_lat
->set_to_bottom ();
1912 /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
1913 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
1914 other cases, return false). If there are no aggregate items, set
1915 aggs_by_ref to NEW_AGGS_BY_REF. */
1918 set_check_aggs_by_ref (struct ipcp_param_lattices
*dest_plats
,
1919 bool new_aggs_by_ref
)
1921 if (dest_plats
->aggs
)
1923 if (dest_plats
->aggs_by_ref
!= new_aggs_by_ref
)
1925 set_agg_lats_to_bottom (dest_plats
);
1930 dest_plats
->aggs_by_ref
= new_aggs_by_ref
;
1934 /* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
1935 already existing lattice for the given OFFSET and SIZE, marking all skipped
1936 lattices as containing variable and checking for overlaps. If there is no
1937 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
1938 it with offset, size and contains_variable to PRE_EXISTING, and return true,
1939 unless there are too many already. If there are two many, return false. If
1940 there are overlaps turn whole DEST_PLATS to bottom and return false. If any
1941 skipped lattices were newly marked as containing variable, set *CHANGE to
1945 merge_agg_lats_step (struct ipcp_param_lattices
*dest_plats
,
1946 HOST_WIDE_INT offset
, HOST_WIDE_INT val_size
,
1947 struct ipcp_agg_lattice
***aglat
,
1948 bool pre_existing
, bool *change
)
1950 gcc_checking_assert (offset
>= 0);
1952 while (**aglat
&& (**aglat
)->offset
< offset
)
1954 if ((**aglat
)->offset
+ (**aglat
)->size
> offset
)
1956 set_agg_lats_to_bottom (dest_plats
);
1959 *change
|= (**aglat
)->set_contains_variable ();
1960 *aglat
= &(**aglat
)->next
;
1963 if (**aglat
&& (**aglat
)->offset
== offset
)
1965 if ((**aglat
)->size
!= val_size
1967 && (**aglat
)->next
->offset
< offset
+ val_size
))
1969 set_agg_lats_to_bottom (dest_plats
);
1972 gcc_checking_assert (!(**aglat
)->next
1973 || (**aglat
)->next
->offset
>= offset
+ val_size
);
1978 struct ipcp_agg_lattice
*new_al
;
1980 if (**aglat
&& (**aglat
)->offset
< offset
+ val_size
)
1982 set_agg_lats_to_bottom (dest_plats
);
1985 if (dest_plats
->aggs_count
== PARAM_VALUE (PARAM_IPA_MAX_AGG_ITEMS
))
1987 dest_plats
->aggs_count
++;
1988 new_al
= ipcp_agg_lattice_pool
.allocate ();
1989 memset (new_al
, 0, sizeof (*new_al
));
1991 new_al
->offset
= offset
;
1992 new_al
->size
= val_size
;
1993 new_al
->contains_variable
= pre_existing
;
1995 new_al
->next
= **aglat
;
2001 /* Set all AGLAT and all other aggregate lattices reachable by next pointers as
2002 containing an unknown value. */
2005 set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice
*aglat
)
2010 ret
|= aglat
->set_contains_variable ();
2011 aglat
= aglat
->next
;
2016 /* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
2017 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source
2018 parameter used for lattice value sources. Return true if DEST_PLATS changed
2022 merge_aggregate_lattices (struct cgraph_edge
*cs
,
2023 struct ipcp_param_lattices
*dest_plats
,
2024 struct ipcp_param_lattices
*src_plats
,
2025 int src_idx
, HOST_WIDE_INT offset_delta
)
2027 bool pre_existing
= dest_plats
->aggs
!= NULL
;
2028 struct ipcp_agg_lattice
**dst_aglat
;
2031 if (set_check_aggs_by_ref (dest_plats
, src_plats
->aggs_by_ref
))
2033 if (src_plats
->aggs_bottom
)
2034 return set_agg_lats_contain_variable (dest_plats
);
2035 if (src_plats
->aggs_contain_variable
)
2036 ret
|= set_agg_lats_contain_variable (dest_plats
);
2037 dst_aglat
= &dest_plats
->aggs
;
2039 for (struct ipcp_agg_lattice
*src_aglat
= src_plats
->aggs
;
2041 src_aglat
= src_aglat
->next
)
2043 HOST_WIDE_INT new_offset
= src_aglat
->offset
- offset_delta
;
2047 if (merge_agg_lats_step (dest_plats
, new_offset
, src_aglat
->size
,
2048 &dst_aglat
, pre_existing
, &ret
))
2050 struct ipcp_agg_lattice
*new_al
= *dst_aglat
;
2052 dst_aglat
= &(*dst_aglat
)->next
;
2053 if (src_aglat
->bottom
)
2055 ret
|= new_al
->set_contains_variable ();
2058 if (src_aglat
->contains_variable
)
2059 ret
|= new_al
->set_contains_variable ();
2060 for (ipcp_value
<tree
> *val
= src_aglat
->values
;
2063 ret
|= new_al
->add_value (val
->value
, cs
, val
, src_idx
,
2066 else if (dest_plats
->aggs_bottom
)
2069 ret
|= set_chain_of_aglats_contains_variable (*dst_aglat
);
2073 /* Determine whether there is anything to propagate FROM SRC_PLATS through a
2074 pass-through JFUNC and if so, whether it has conform and conforms to the
2075 rules about propagating values passed by reference. */
2078 agg_pass_through_permissible_p (struct ipcp_param_lattices
*src_plats
,
2079 struct ipa_jump_func
*jfunc
)
2081 return src_plats
->aggs
2082 && (!src_plats
->aggs_by_ref
2083 || ipa_get_jf_pass_through_agg_preserved (jfunc
));
2086 /* Propagate scalar values across jump function JFUNC that is associated with
2087 edge CS and put the values into DEST_LAT. */
2090 propagate_aggs_across_jump_function (struct cgraph_edge
*cs
,
2091 struct ipa_jump_func
*jfunc
,
2092 struct ipcp_param_lattices
*dest_plats
)
2096 if (dest_plats
->aggs_bottom
)
2099 if (jfunc
->type
== IPA_JF_PASS_THROUGH
2100 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
2102 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2103 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
2104 struct ipcp_param_lattices
*src_plats
;
2106 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2107 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
2109 /* Currently we do not produce clobber aggregate jump
2110 functions, replace with merging when we do. */
2111 gcc_assert (!jfunc
->agg
.items
);
2112 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
,
2116 ret
|= set_agg_lats_contain_variable (dest_plats
);
2118 else if (jfunc
->type
== IPA_JF_ANCESTOR
2119 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
2121 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
2122 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
2123 struct ipcp_param_lattices
*src_plats
;
2125 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
2126 if (src_plats
->aggs
&& src_plats
->aggs_by_ref
)
2128 /* Currently we do not produce clobber aggregate jump
2129 functions, replace with merging when we do. */
2130 gcc_assert (!jfunc
->agg
.items
);
2131 ret
|= merge_aggregate_lattices (cs
, dest_plats
, src_plats
, src_idx
,
2132 ipa_get_jf_ancestor_offset (jfunc
));
2134 else if (!src_plats
->aggs_by_ref
)
2135 ret
|= set_agg_lats_to_bottom (dest_plats
);
2137 ret
|= set_agg_lats_contain_variable (dest_plats
);
2139 else if (jfunc
->agg
.items
)
2141 bool pre_existing
= dest_plats
->aggs
!= NULL
;
2142 struct ipcp_agg_lattice
**aglat
= &dest_plats
->aggs
;
2143 struct ipa_agg_jf_item
*item
;
2146 if (set_check_aggs_by_ref (dest_plats
, jfunc
->agg
.by_ref
))
2149 FOR_EACH_VEC_ELT (*jfunc
->agg
.items
, i
, item
)
2151 HOST_WIDE_INT val_size
;
2153 if (item
->offset
< 0)
2155 gcc_checking_assert (is_gimple_ip_invariant (item
->value
));
2156 val_size
= tree_to_uhwi (TYPE_SIZE (TREE_TYPE (item
->value
)));
2158 if (merge_agg_lats_step (dest_plats
, item
->offset
, val_size
,
2159 &aglat
, pre_existing
, &ret
))
2161 ret
|= (*aglat
)->add_value (item
->value
, cs
, NULL
, 0, 0);
2162 aglat
= &(*aglat
)->next
;
2164 else if (dest_plats
->aggs_bottom
)
2168 ret
|= set_chain_of_aglats_contains_variable (*aglat
);
2171 ret
|= set_agg_lats_contain_variable (dest_plats
);
2176 /* Return true if on the way cfrom CS->caller to the final (non-alias and
2177 non-thunk) destination, the call passes through a thunk. */
2180 call_passes_through_thunk_p (cgraph_edge
*cs
)
2182 cgraph_node
*alias_or_thunk
= cs
->callee
;
2183 while (alias_or_thunk
->alias
)
2184 alias_or_thunk
= alias_or_thunk
->get_alias_target ();
2185 return alias_or_thunk
->thunk
.thunk_p
;
2188 /* Propagate constants from the caller to the callee of CS. INFO describes the
2192 propagate_constants_across_call (struct cgraph_edge
*cs
)
2194 struct ipa_node_params
*callee_info
;
2195 enum availability availability
;
2196 cgraph_node
*callee
;
2197 struct ipa_edge_args
*args
;
2199 int i
, args_count
, parms_count
;
2201 callee
= cs
->callee
->function_symbol (&availability
);
2202 if (!callee
->definition
)
2204 gcc_checking_assert (callee
->has_gimple_body_p ());
2205 callee_info
= IPA_NODE_REF (callee
);
2207 args
= IPA_EDGE_REF (cs
);
2208 args_count
= ipa_get_cs_argument_count (args
);
2209 parms_count
= ipa_get_param_count (callee_info
);
2210 if (parms_count
== 0)
2213 /* No propagation through instrumentation thunks is available yet.
2214 It should be possible with proper mapping of call args and
2215 instrumented callee params in the propagation loop below. But
2216 this case mostly occurs when legacy code calls instrumented code
2217 and it is not a primary target for optimizations.
2218 We detect instrumentation thunks in aliases and thunks chain by
2219 checking instrumentation_clone flag for chain source and target.
2220 Going through instrumentation thunks we always have it changed
2221 from 0 to 1 and all other nodes do not change it. */
2222 if (!cs
->callee
->instrumentation_clone
2223 && callee
->instrumentation_clone
)
2225 for (i
= 0; i
< parms_count
; i
++)
2226 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
2231 /* If this call goes through a thunk we must not propagate to the first (0th)
2232 parameter. However, we might need to uncover a thunk from below a series
2233 of aliases first. */
2234 if (call_passes_through_thunk_p (cs
))
2236 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
,
2243 for (; (i
< args_count
) && (i
< parms_count
); i
++)
2245 struct ipa_jump_func
*jump_func
= ipa_get_ith_jump_func (args
, i
);
2246 struct ipcp_param_lattices
*dest_plats
;
2247 tree param_type
= ipa_get_callee_param_type (cs
, i
);
2249 dest_plats
= ipa_get_parm_lattices (callee_info
, i
);
2250 if (availability
== AVAIL_INTERPOSABLE
)
2251 ret
|= set_all_contains_variable (dest_plats
);
2254 ret
|= propagate_scalar_across_jump_function (cs
, jump_func
,
2255 &dest_plats
->itself
);
2256 ret
|= propagate_context_across_jump_function (cs
, jump_func
, i
,
2257 &dest_plats
->ctxlat
);
2259 |= propagate_bits_across_jump_function (cs
, i
, jump_func
,
2260 &dest_plats
->bits_lattice
);
2261 ret
|= propagate_aggs_across_jump_function (cs
, jump_func
,
2263 if (opt_for_fn (callee
->decl
, flag_ipa_vrp
))
2264 ret
|= propagate_vr_across_jump_function (cs
, jump_func
,
2265 dest_plats
, param_type
);
2267 ret
|= dest_plats
->m_value_range
.set_to_bottom ();
2270 for (; i
< parms_count
; i
++)
2271 ret
|= set_all_contains_variable (ipa_get_parm_lattices (callee_info
, i
));
2276 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
2277 KNOWN_CONTEXTS, KNOWN_AGGS or AGG_REPS return the destination. The latter
2278 three can be NULL. If AGG_REPS is not NULL, KNOWN_AGGS is ignored. */
2281 ipa_get_indirect_edge_target_1 (struct cgraph_edge
*ie
,
2282 vec
<tree
> known_csts
,
2283 vec
<ipa_polymorphic_call_context
> known_contexts
,
2284 vec
<ipa_agg_jump_function_p
> known_aggs
,
2285 struct ipa_agg_replacement_value
*agg_reps
,
2288 int param_index
= ie
->indirect_info
->param_index
;
2289 HOST_WIDE_INT anc_offset
;
2293 *speculative
= false;
2295 if (param_index
== -1
2296 || known_csts
.length () <= (unsigned int) param_index
)
2299 if (!ie
->indirect_info
->polymorphic
)
2303 if (ie
->indirect_info
->agg_contents
)
2306 if (agg_reps
&& ie
->indirect_info
->guaranteed_unmodified
)
2310 if (agg_reps
->index
== param_index
2311 && agg_reps
->offset
== ie
->indirect_info
->offset
2312 && agg_reps
->by_ref
== ie
->indirect_info
->by_ref
)
2314 t
= agg_reps
->value
;
2317 agg_reps
= agg_reps
->next
;
2322 struct ipa_agg_jump_function
*agg
;
2323 if (known_aggs
.length () > (unsigned int) param_index
)
2324 agg
= known_aggs
[param_index
];
2327 bool from_global_constant
;
2328 t
= ipa_find_agg_cst_for_param (agg
, known_csts
[param_index
],
2329 ie
->indirect_info
->offset
,
2330 ie
->indirect_info
->by_ref
,
2331 &from_global_constant
);
2333 && !from_global_constant
2334 && !ie
->indirect_info
->guaranteed_unmodified
)
2339 t
= known_csts
[param_index
];
2342 && TREE_CODE (t
) == ADDR_EXPR
2343 && TREE_CODE (TREE_OPERAND (t
, 0)) == FUNCTION_DECL
)
2344 return TREE_OPERAND (t
, 0);
2349 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize
))
2352 gcc_assert (!ie
->indirect_info
->agg_contents
);
2353 anc_offset
= ie
->indirect_info
->offset
;
2357 /* Try to work out value of virtual table pointer value in replacemnets. */
2358 if (!t
&& agg_reps
&& !ie
->indirect_info
->by_ref
)
2362 if (agg_reps
->index
== param_index
2363 && agg_reps
->offset
== ie
->indirect_info
->offset
2364 && agg_reps
->by_ref
)
2366 t
= agg_reps
->value
;
2369 agg_reps
= agg_reps
->next
;
2373 /* Try to work out value of virtual table pointer value in known
2374 aggregate values. */
2375 if (!t
&& known_aggs
.length () > (unsigned int) param_index
2376 && !ie
->indirect_info
->by_ref
)
2378 struct ipa_agg_jump_function
*agg
;
2379 agg
= known_aggs
[param_index
];
2380 t
= ipa_find_agg_cst_for_param (agg
, known_csts
[param_index
],
2381 ie
->indirect_info
->offset
, true);
2384 /* If we found the virtual table pointer, lookup the target. */
2388 unsigned HOST_WIDE_INT offset
;
2389 if (vtable_pointer_value_to_vtable (t
, &vtable
, &offset
))
2392 target
= gimple_get_virt_method_for_vtable (ie
->indirect_info
->otr_token
,
2393 vtable
, offset
, &can_refer
);
2397 || (TREE_CODE (TREE_TYPE (target
)) == FUNCTION_TYPE
2398 && DECL_FUNCTION_CODE (target
) == BUILT_IN_UNREACHABLE
)
2399 || !possible_polymorphic_call_target_p
2400 (ie
, cgraph_node::get (target
)))
2402 /* Do not speculate builtin_unreachable, it is stupid! */
2403 if (ie
->indirect_info
->vptr_changed
)
2405 target
= ipa_impossible_devirt_target (ie
, target
);
2407 *speculative
= ie
->indirect_info
->vptr_changed
;
2414 /* Do we know the constant value of pointer? */
2416 t
= known_csts
[param_index
];
2418 gcc_checking_assert (!t
|| TREE_CODE (t
) != TREE_BINFO
);
2420 ipa_polymorphic_call_context context
;
2421 if (known_contexts
.length () > (unsigned int) param_index
)
2423 context
= known_contexts
[param_index
];
2424 context
.offset_by (anc_offset
);
2425 if (ie
->indirect_info
->vptr_changed
)
2426 context
.possible_dynamic_type_change (ie
->in_polymorphic_cdtor
,
2427 ie
->indirect_info
->otr_type
);
2430 ipa_polymorphic_call_context ctx2
= ipa_polymorphic_call_context
2431 (t
, ie
->indirect_info
->otr_type
, anc_offset
);
2432 if (!ctx2
.useless_p ())
2433 context
.combine_with (ctx2
, ie
->indirect_info
->otr_type
);
2438 context
= ipa_polymorphic_call_context (t
, ie
->indirect_info
->otr_type
,
2440 if (ie
->indirect_info
->vptr_changed
)
2441 context
.possible_dynamic_type_change (ie
->in_polymorphic_cdtor
,
2442 ie
->indirect_info
->otr_type
);
2447 vec
<cgraph_node
*>targets
;
2450 targets
= possible_polymorphic_call_targets
2451 (ie
->indirect_info
->otr_type
,
2452 ie
->indirect_info
->otr_token
,
2454 if (!final
|| targets
.length () > 1)
2456 struct cgraph_node
*node
;
2459 if (!opt_for_fn (ie
->caller
->decl
, flag_devirtualize_speculatively
)
2460 || ie
->speculative
|| !ie
->maybe_hot_p ())
2462 node
= try_speculative_devirtualization (ie
->indirect_info
->otr_type
,
2463 ie
->indirect_info
->otr_token
,
2467 *speculative
= true;
2468 target
= node
->decl
;
2475 *speculative
= false;
2476 if (targets
.length () == 1)
2477 target
= targets
[0]->decl
;
2479 target
= ipa_impossible_devirt_target (ie
, NULL_TREE
);
2482 if (target
&& !possible_polymorphic_call_target_p (ie
,
2483 cgraph_node::get (target
)))
2487 target
= ipa_impossible_devirt_target (ie
, target
);
2494 /* If an indirect edge IE can be turned into a direct one based on KNOWN_CSTS,
2495 KNOWN_CONTEXTS (which can be vNULL) or KNOWN_AGGS (which also can be vNULL)
2496 return the destination. */
2499 ipa_get_indirect_edge_target (struct cgraph_edge
*ie
,
2500 vec
<tree
> known_csts
,
2501 vec
<ipa_polymorphic_call_context
> known_contexts
,
2502 vec
<ipa_agg_jump_function_p
> known_aggs
,
2505 return ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
2506 known_aggs
, NULL
, speculative
);
2509 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
2510 and KNOWN_CONTEXTS. */
2513 devirtualization_time_bonus (struct cgraph_node
*node
,
2514 vec
<tree
> known_csts
,
2515 vec
<ipa_polymorphic_call_context
> known_contexts
,
2516 vec
<ipa_agg_jump_function_p
> known_aggs
)
2518 struct cgraph_edge
*ie
;
2521 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
2523 struct cgraph_node
*callee
;
2524 struct inline_summary
*isummary
;
2525 enum availability avail
;
2529 target
= ipa_get_indirect_edge_target (ie
, known_csts
, known_contexts
,
2530 known_aggs
, &speculative
);
2534 /* Only bare minimum benefit for clearly un-inlineable targets. */
2536 callee
= cgraph_node::get (target
);
2537 if (!callee
|| !callee
->definition
)
2539 callee
= callee
->function_symbol (&avail
);
2540 if (avail
< AVAIL_AVAILABLE
)
2542 isummary
= inline_summaries
->get (callee
);
2543 if (!isummary
->inlinable
)
2546 /* FIXME: The values below need re-considering and perhaps also
2547 integrating into the cost metrics, at lest in some very basic way. */
2548 if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 4)
2549 res
+= 31 / ((int)speculative
+ 1);
2550 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
/ 2)
2551 res
+= 15 / ((int)speculative
+ 1);
2552 else if (isummary
->size
<= MAX_INLINE_INSNS_AUTO
2553 || DECL_DECLARED_INLINE_P (callee
->decl
))
2554 res
+= 7 / ((int)speculative
+ 1);
2560 /* Return time bonus incurred because of HINTS. */
2563 hint_time_bonus (inline_hints hints
)
2566 if (hints
& (INLINE_HINT_loop_iterations
| INLINE_HINT_loop_stride
))
2567 result
+= PARAM_VALUE (PARAM_IPA_CP_LOOP_HINT_BONUS
);
2568 if (hints
& INLINE_HINT_array_index
)
2569 result
+= PARAM_VALUE (PARAM_IPA_CP_ARRAY_INDEX_HINT_BONUS
);
2573 /* If there is a reason to penalize the function described by INFO in the
2574 cloning goodness evaluation, do so. */
2576 static inline int64_t
2577 incorporate_penalties (ipa_node_params
*info
, int64_t evaluation
)
2579 if (info
->node_within_scc
)
2580 evaluation
= (evaluation
2581 * (100 - PARAM_VALUE (PARAM_IPA_CP_RECURSION_PENALTY
))) / 100;
2583 if (info
->node_calling_single_call
)
2584 evaluation
= (evaluation
2585 * (100 - PARAM_VALUE (PARAM_IPA_CP_SINGLE_CALL_PENALTY
)))
2591 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
2592 and SIZE_COST and with the sum of frequencies of incoming edges to the
2593 potential new clone in FREQUENCIES. */
2596 good_cloning_opportunity_p (struct cgraph_node
*node
, int time_benefit
,
2597 int freq_sum
, gcov_type count_sum
, int size_cost
)
2599 if (time_benefit
== 0
2600 || !opt_for_fn (node
->decl
, flag_ipa_cp_clone
)
2601 || node
->optimize_for_size_p ())
2604 gcc_assert (size_cost
> 0);
2606 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2609 int factor
= (count_sum
* 1000) / max_count
;
2610 int64_t evaluation
= (((int64_t) time_benefit
* factor
)
2612 evaluation
= incorporate_penalties (info
, evaluation
);
2614 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2615 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
2616 "size: %i, count_sum: " HOST_WIDE_INT_PRINT_DEC
2617 "%s%s) -> evaluation: " "%" PRId64
2618 ", threshold: %i\n",
2619 time_benefit
, size_cost
, (HOST_WIDE_INT
) count_sum
,
2620 info
->node_within_scc
? ", scc" : "",
2621 info
->node_calling_single_call
? ", single_call" : "",
2622 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
2624 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
2628 int64_t evaluation
= (((int64_t) time_benefit
* freq_sum
)
2630 evaluation
= incorporate_penalties (info
, evaluation
);
2632 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2633 fprintf (dump_file
, " good_cloning_opportunity_p (time: %i, "
2634 "size: %i, freq_sum: %i%s%s) -> evaluation: "
2635 "%" PRId64
", threshold: %i\n",
2636 time_benefit
, size_cost
, freq_sum
,
2637 info
->node_within_scc
? ", scc" : "",
2638 info
->node_calling_single_call
? ", single_call" : "",
2639 evaluation
, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
));
2641 return evaluation
>= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD
);
2645 /* Return all context independent values from aggregate lattices in PLATS in a
2646 vector. Return NULL if there are none. */
2648 static vec
<ipa_agg_jf_item
, va_gc
> *
2649 context_independent_aggregate_values (struct ipcp_param_lattices
*plats
)
2651 vec
<ipa_agg_jf_item
, va_gc
> *res
= NULL
;
2653 if (plats
->aggs_bottom
2654 || plats
->aggs_contain_variable
2655 || plats
->aggs_count
== 0)
2658 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
;
2660 aglat
= aglat
->next
)
2661 if (aglat
->is_single_const ())
2663 struct ipa_agg_jf_item item
;
2664 item
.offset
= aglat
->offset
;
2665 item
.value
= aglat
->values
->value
;
2666 vec_safe_push (res
, item
);
2671 /* Allocate KNOWN_CSTS, KNOWN_CONTEXTS and, if non-NULL, KNOWN_AGGS and
2672 populate them with values of parameters that are known independent of the
2673 context. INFO describes the function. If REMOVABLE_PARAMS_COST is
2674 non-NULL, the movement cost of all removable parameters will be stored in
2678 gather_context_independent_values (struct ipa_node_params
*info
,
2679 vec
<tree
> *known_csts
,
2680 vec
<ipa_polymorphic_call_context
>
2682 vec
<ipa_agg_jump_function
> *known_aggs
,
2683 int *removable_params_cost
)
2685 int i
, count
= ipa_get_param_count (info
);
2688 known_csts
->create (0);
2689 known_contexts
->create (0);
2690 known_csts
->safe_grow_cleared (count
);
2691 known_contexts
->safe_grow_cleared (count
);
2694 known_aggs
->create (0);
2695 known_aggs
->safe_grow_cleared (count
);
2698 if (removable_params_cost
)
2699 *removable_params_cost
= 0;
2701 for (i
= 0; i
< count
; i
++)
2703 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2704 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
2706 if (lat
->is_single_const ())
2708 ipcp_value
<tree
> *val
= lat
->values
;
2709 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
2710 (*known_csts
)[i
] = val
->value
;
2711 if (removable_params_cost
)
2712 *removable_params_cost
2713 += estimate_move_cost (TREE_TYPE (val
->value
), false);
2716 else if (removable_params_cost
2717 && !ipa_is_param_used (info
, i
))
2718 *removable_params_cost
2719 += ipa_get_param_move_cost (info
, i
);
2721 if (!ipa_is_param_used (info
, i
))
2724 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
2725 /* Do not account known context as reason for cloning. We can see
2726 if it permits devirtualization. */
2727 if (ctxlat
->is_single_const ())
2728 (*known_contexts
)[i
] = ctxlat
->values
->value
;
2732 vec
<ipa_agg_jf_item
, va_gc
> *agg_items
;
2733 struct ipa_agg_jump_function
*ajf
;
2735 agg_items
= context_independent_aggregate_values (plats
);
2736 ajf
= &(*known_aggs
)[i
];
2737 ajf
->items
= agg_items
;
2738 ajf
->by_ref
= plats
->aggs_by_ref
;
2739 ret
|= agg_items
!= NULL
;
2746 /* The current interface in ipa-inline-analysis requires a pointer vector.
2749 FIXME: That interface should be re-worked, this is slightly silly. Still,
2750 I'd like to discuss how to change it first and this demonstrates the
2753 static vec
<ipa_agg_jump_function_p
>
2754 agg_jmp_p_vec_for_t_vec (vec
<ipa_agg_jump_function
> known_aggs
)
2756 vec
<ipa_agg_jump_function_p
> ret
;
2757 struct ipa_agg_jump_function
*ajf
;
2760 ret
.create (known_aggs
.length ());
2761 FOR_EACH_VEC_ELT (known_aggs
, i
, ajf
)
2762 ret
.quick_push (ajf
);
2766 /* Perform time and size measurement of NODE with the context given in
2767 KNOWN_CSTS, KNOWN_CONTEXTS and KNOWN_AGGS, calculate the benefit and cost
2768 given BASE_TIME of the node without specialization, REMOVABLE_PARAMS_COST of
2769 all context-independent removable parameters and EST_MOVE_COST of estimated
2770 movement of the considered parameter and store it into VAL. */
2773 perform_estimation_of_a_value (cgraph_node
*node
, vec
<tree
> known_csts
,
2774 vec
<ipa_polymorphic_call_context
> known_contexts
,
2775 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
,
2776 int base_time
, int removable_params_cost
,
2777 int est_move_cost
, ipcp_value_base
*val
)
2779 int time
, size
, time_benefit
;
2782 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
2783 known_aggs_ptrs
, &size
, &time
,
2785 time_benefit
= base_time
- time
2786 + devirtualization_time_bonus (node
, known_csts
, known_contexts
,
2788 + hint_time_bonus (hints
)
2789 + removable_params_cost
+ est_move_cost
;
2791 gcc_checking_assert (size
>=0);
2792 /* The inliner-heuristics based estimates may think that in certain
2793 contexts some functions do not have any size at all but we want
2794 all specializations to have at least a tiny cost, not least not to
2799 val
->local_time_benefit
= time_benefit
;
2800 val
->local_size_cost
= size
;
2803 /* Iterate over known values of parameters of NODE and estimate the local
2804 effects in terms of time and size they have. */
2807 estimate_local_effects (struct cgraph_node
*node
)
2809 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
2810 int i
, count
= ipa_get_param_count (info
);
2811 vec
<tree
> known_csts
;
2812 vec
<ipa_polymorphic_call_context
> known_contexts
;
2813 vec
<ipa_agg_jump_function
> known_aggs
;
2814 vec
<ipa_agg_jump_function_p
> known_aggs_ptrs
;
2816 int base_time
= inline_summaries
->get (node
)->time
;
2817 int removable_params_cost
;
2819 if (!count
|| !ipcp_versionable_function_p (node
))
2822 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2823 fprintf (dump_file
, "\nEstimating effects for %s/%i, base_time: %i.\n",
2824 node
->name (), node
->order
, base_time
);
2826 always_const
= gather_context_independent_values (info
, &known_csts
,
2827 &known_contexts
, &known_aggs
,
2828 &removable_params_cost
);
2829 known_aggs_ptrs
= agg_jmp_p_vec_for_t_vec (known_aggs
);
2830 int devirt_bonus
= devirtualization_time_bonus (node
, known_csts
,
2831 known_contexts
, known_aggs_ptrs
);
2832 if (always_const
|| devirt_bonus
2833 || (removable_params_cost
&& node
->local
.can_change_signature
))
2835 struct caller_statistics stats
;
2839 init_caller_stats (&stats
);
2840 node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
2842 estimate_ipcp_clone_size_and_time (node
, known_csts
, known_contexts
,
2843 known_aggs_ptrs
, &size
, &time
, &hints
);
2844 time
-= devirt_bonus
;
2845 time
-= hint_time_bonus (hints
);
2846 time
-= removable_params_cost
;
2847 size
-= stats
.n_calls
* removable_params_cost
;
2850 fprintf (dump_file
, " - context independent values, size: %i, "
2851 "time_benefit: %i\n", size
, base_time
- time
);
2853 if (size
<= 0 || node
->local
.local
)
2855 info
->do_clone_for_all_contexts
= true;
2859 fprintf (dump_file
, " Decided to specialize for all "
2860 "known contexts, code not going to grow.\n");
2862 else if (good_cloning_opportunity_p (node
, base_time
- time
,
2863 stats
.freq_sum
, stats
.count_sum
,
2866 if (size
+ overall_size
<= max_new_size
)
2868 info
->do_clone_for_all_contexts
= true;
2870 overall_size
+= size
;
2873 fprintf (dump_file
, " Decided to specialize for all "
2874 "known contexts, growth deemed beneficial.\n");
2876 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2877 fprintf (dump_file
, " Not cloning for all contexts because "
2878 "max_new_size would be reached with %li.\n",
2879 size
+ overall_size
);
2881 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2882 fprintf (dump_file
, " Not cloning for all contexts because "
2883 "!good_cloning_opportunity_p.\n");
2887 for (i
= 0; i
< count
; i
++)
2889 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2890 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
2891 ipcp_value
<tree
> *val
;
2898 for (val
= lat
->values
; val
; val
= val
->next
)
2900 gcc_checking_assert (TREE_CODE (val
->value
) != TREE_BINFO
);
2901 known_csts
[i
] = val
->value
;
2903 int emc
= estimate_move_cost (TREE_TYPE (val
->value
), true);
2904 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
2905 known_aggs_ptrs
, base_time
,
2906 removable_params_cost
, emc
, val
);
2908 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2910 fprintf (dump_file
, " - estimates for value ");
2911 print_ipcp_constant_value (dump_file
, val
->value
);
2912 fprintf (dump_file
, " for ");
2913 ipa_dump_param (dump_file
, info
, i
);
2914 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
2915 val
->local_time_benefit
, val
->local_size_cost
);
2918 known_csts
[i
] = NULL_TREE
;
2921 for (i
= 0; i
< count
; i
++)
2923 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2925 if (!plats
->virt_call
)
2928 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
2929 ipcp_value
<ipa_polymorphic_call_context
> *val
;
2933 || !known_contexts
[i
].useless_p ())
2936 for (val
= ctxlat
->values
; val
; val
= val
->next
)
2938 known_contexts
[i
] = val
->value
;
2939 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
2940 known_aggs_ptrs
, base_time
,
2941 removable_params_cost
, 0, val
);
2943 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2945 fprintf (dump_file
, " - estimates for polymorphic context ");
2946 print_ipcp_constant_value (dump_file
, val
->value
);
2947 fprintf (dump_file
, " for ");
2948 ipa_dump_param (dump_file
, info
, i
);
2949 fprintf (dump_file
, ": time_benefit: %i, size: %i\n",
2950 val
->local_time_benefit
, val
->local_size_cost
);
2953 known_contexts
[i
] = ipa_polymorphic_call_context ();
2956 for (i
= 0; i
< count
; i
++)
2958 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
2959 struct ipa_agg_jump_function
*ajf
;
2960 struct ipcp_agg_lattice
*aglat
;
2962 if (plats
->aggs_bottom
|| !plats
->aggs
)
2965 ajf
= &known_aggs
[i
];
2966 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
2968 ipcp_value
<tree
> *val
;
2969 if (aglat
->bottom
|| !aglat
->values
2970 /* If the following is true, the one value is in known_aggs. */
2971 || (!plats
->aggs_contain_variable
2972 && aglat
->is_single_const ()))
2975 for (val
= aglat
->values
; val
; val
= val
->next
)
2977 struct ipa_agg_jf_item item
;
2979 item
.offset
= aglat
->offset
;
2980 item
.value
= val
->value
;
2981 vec_safe_push (ajf
->items
, item
);
2983 perform_estimation_of_a_value (node
, known_csts
, known_contexts
,
2984 known_aggs_ptrs
, base_time
,
2985 removable_params_cost
, 0, val
);
2987 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2989 fprintf (dump_file
, " - estimates for value ");
2990 print_ipcp_constant_value (dump_file
, val
->value
);
2991 fprintf (dump_file
, " for ");
2992 ipa_dump_param (dump_file
, info
, i
);
2993 fprintf (dump_file
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
2994 "]: time_benefit: %i, size: %i\n",
2995 plats
->aggs_by_ref
? "ref " : "",
2997 val
->local_time_benefit
, val
->local_size_cost
);
3005 for (i
= 0; i
< count
; i
++)
3006 vec_free (known_aggs
[i
].items
);
3008 known_csts
.release ();
3009 known_contexts
.release ();
3010 known_aggs
.release ();
3011 known_aggs_ptrs
.release ();
3015 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
3016 topological sort of values. */
3018 template <typename valtype
>
3020 value_topo_info
<valtype
>::add_val (ipcp_value
<valtype
> *cur_val
)
3022 ipcp_value_source
<valtype
> *src
;
3028 cur_val
->dfs
= dfs_counter
;
3029 cur_val
->low_link
= dfs_counter
;
3031 cur_val
->topo_next
= stack
;
3033 cur_val
->on_stack
= true;
3035 for (src
= cur_val
->sources
; src
; src
= src
->next
)
3038 if (src
->val
->dfs
== 0)
3041 if (src
->val
->low_link
< cur_val
->low_link
)
3042 cur_val
->low_link
= src
->val
->low_link
;
3044 else if (src
->val
->on_stack
3045 && src
->val
->dfs
< cur_val
->low_link
)
3046 cur_val
->low_link
= src
->val
->dfs
;
3049 if (cur_val
->dfs
== cur_val
->low_link
)
3051 ipcp_value
<valtype
> *v
, *scc_list
= NULL
;
3056 stack
= v
->topo_next
;
3057 v
->on_stack
= false;
3059 v
->scc_next
= scc_list
;
3062 while (v
!= cur_val
);
3064 cur_val
->topo_next
= values_topo
;
3065 values_topo
= cur_val
;
3069 /* Add all values in lattices associated with NODE to the topological sort if
3070 they are not there yet. */
3073 add_all_node_vals_to_toposort (cgraph_node
*node
, ipa_topo_info
*topo
)
3075 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3076 int i
, count
= ipa_get_param_count (info
);
3078 for (i
= 0; i
< count
; i
++)
3080 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
3081 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
3082 struct ipcp_agg_lattice
*aglat
;
3086 ipcp_value
<tree
> *val
;
3087 for (val
= lat
->values
; val
; val
= val
->next
)
3088 topo
->constants
.add_val (val
);
3091 if (!plats
->aggs_bottom
)
3092 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3095 ipcp_value
<tree
> *val
;
3096 for (val
= aglat
->values
; val
; val
= val
->next
)
3097 topo
->constants
.add_val (val
);
3100 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
3101 if (!ctxlat
->bottom
)
3103 ipcp_value
<ipa_polymorphic_call_context
> *ctxval
;
3104 for (ctxval
= ctxlat
->values
; ctxval
; ctxval
= ctxval
->next
)
3105 topo
->contexts
.add_val (ctxval
);
3110 /* One pass of constants propagation along the call graph edges, from callers
3111 to callees (requires topological ordering in TOPO), iterate over strongly
3112 connected components. */
3115 propagate_constants_topo (struct ipa_topo_info
*topo
)
3119 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
3122 struct cgraph_node
*v
, *node
= topo
->order
[i
];
3123 vec
<cgraph_node
*> cycle_nodes
= ipa_get_nodes_in_cycle (node
);
3125 /* First, iteratively propagate within the strongly connected component
3126 until all lattices stabilize. */
3127 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
3128 if (v
->has_gimple_body_p ())
3129 push_node_to_stack (topo
, v
);
3131 v
= pop_node_from_stack (topo
);
3134 struct cgraph_edge
*cs
;
3136 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3137 if (ipa_edge_within_scc (cs
))
3139 IPA_NODE_REF (v
)->node_within_scc
= true;
3140 if (propagate_constants_across_call (cs
))
3141 push_node_to_stack (topo
, cs
->callee
->function_symbol ());
3143 v
= pop_node_from_stack (topo
);
3146 /* Afterwards, propagate along edges leading out of the SCC, calculates
3147 the local effects of the discovered constants and all valid values to
3148 their topological sort. */
3149 FOR_EACH_VEC_ELT (cycle_nodes
, j
, v
)
3150 if (v
->has_gimple_body_p ())
3152 struct cgraph_edge
*cs
;
3154 estimate_local_effects (v
);
3155 add_all_node_vals_to_toposort (v
, topo
);
3156 for (cs
= v
->callees
; cs
; cs
= cs
->next_callee
)
3157 if (!ipa_edge_within_scc (cs
))
3158 propagate_constants_across_call (cs
);
3160 cycle_nodes
.release ();
3165 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
3166 the bigger one if otherwise. */
3169 safe_add (int a
, int b
)
3171 if (a
> INT_MAX
/2 || b
> INT_MAX
/2)
3172 return a
> b
? a
: b
;
3178 /* Propagate the estimated effects of individual values along the topological
3179 from the dependent values to those they depend on. */
3181 template <typename valtype
>
3183 value_topo_info
<valtype
>::propagate_effects ()
3185 ipcp_value
<valtype
> *base
;
3187 for (base
= values_topo
; base
; base
= base
->topo_next
)
3189 ipcp_value_source
<valtype
> *src
;
3190 ipcp_value
<valtype
> *val
;
3191 int time
= 0, size
= 0;
3193 for (val
= base
; val
; val
= val
->scc_next
)
3195 time
= safe_add (time
,
3196 val
->local_time_benefit
+ val
->prop_time_benefit
);
3197 size
= safe_add (size
, val
->local_size_cost
+ val
->prop_size_cost
);
3200 for (val
= base
; val
; val
= val
->scc_next
)
3201 for (src
= val
->sources
; src
; src
= src
->next
)
3203 && src
->cs
->maybe_hot_p ())
3205 src
->val
->prop_time_benefit
= safe_add (time
,
3206 src
->val
->prop_time_benefit
);
3207 src
->val
->prop_size_cost
= safe_add (size
,
3208 src
->val
->prop_size_cost
);
3214 /* Propagate constants, polymorphic contexts and their effects from the
3215 summaries interprocedurally. */
3218 ipcp_propagate_stage (struct ipa_topo_info
*topo
)
3220 struct cgraph_node
*node
;
3223 fprintf (dump_file
, "\n Propagating constants:\n\n");
3226 ipa_update_after_lto_read ();
3229 FOR_EACH_DEFINED_FUNCTION (node
)
3231 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3233 /* In LTO we do not have PARM_DECLs but we would still like to be able to
3234 look at types of parameters. */
3237 tree t
= TYPE_ARG_TYPES (TREE_TYPE (node
->decl
));
3238 for (int k
= 0; k
< ipa_get_param_count (info
) && t
; k
++)
3240 gcc_assert (t
!= void_list_node
);
3241 info
->descriptors
[k
].decl_or_type
= TREE_VALUE (t
);
3242 t
= t
? TREE_CHAIN (t
) : NULL
;
3246 determine_versionability (node
, info
);
3247 if (node
->has_gimple_body_p ())
3249 info
->lattices
= XCNEWVEC (struct ipcp_param_lattices
,
3250 ipa_get_param_count (info
));
3251 initialize_node_lattices (node
);
3253 if (node
->definition
&& !node
->alias
)
3254 overall_size
+= inline_summaries
->get (node
)->self_size
;
3255 if (node
->count
> max_count
)
3256 max_count
= node
->count
;
3259 max_new_size
= overall_size
;
3260 if (max_new_size
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
3261 max_new_size
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
3262 max_new_size
+= max_new_size
* PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH
) / 100 + 1;
3265 fprintf (dump_file
, "\noverall_size: %li, max_new_size: %li\n",
3266 overall_size
, max_new_size
);
3268 propagate_constants_topo (topo
);
3270 ipcp_verify_propagated_values ();
3271 topo
->constants
.propagate_effects ();
3272 topo
->contexts
.propagate_effects ();
3276 fprintf (dump_file
, "\nIPA lattices after all propagation:\n");
3277 print_all_lattices (dump_file
, (dump_flags
& TDF_DETAILS
), true);
3281 /* Discover newly direct outgoing edges from NODE which is a new clone with
3282 known KNOWN_CSTS and make them direct. */
3285 ipcp_discover_new_direct_edges (struct cgraph_node
*node
,
3286 vec
<tree
> known_csts
,
3287 vec
<ipa_polymorphic_call_context
>
3289 struct ipa_agg_replacement_value
*aggvals
)
3291 struct cgraph_edge
*ie
, *next_ie
;
3294 for (ie
= node
->indirect_calls
; ie
; ie
= next_ie
)
3299 next_ie
= ie
->next_callee
;
3300 target
= ipa_get_indirect_edge_target_1 (ie
, known_csts
, known_contexts
,
3301 vNULL
, aggvals
, &speculative
);
3304 bool agg_contents
= ie
->indirect_info
->agg_contents
;
3305 bool polymorphic
= ie
->indirect_info
->polymorphic
;
3306 int param_index
= ie
->indirect_info
->param_index
;
3307 struct cgraph_edge
*cs
= ipa_make_edge_direct_to_target (ie
, target
,
3311 if (cs
&& !agg_contents
&& !polymorphic
)
3313 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3314 int c
= ipa_get_controlled_uses (info
, param_index
);
3315 if (c
!= IPA_UNDESCRIBED_USE
)
3317 struct ipa_ref
*to_del
;
3320 ipa_set_controlled_uses (info
, param_index
, c
);
3321 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3322 fprintf (dump_file
, " controlled uses count of param "
3323 "%i bumped down to %i\n", param_index
, c
);
3325 && (to_del
= node
->find_reference (cs
->callee
, NULL
, 0)))
3327 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3328 fprintf (dump_file
, " and even removing its "
3329 "cloning-created reference\n");
3330 to_del
->remove_reference ();
3336 /* Turning calls to direct calls will improve overall summary. */
3338 inline_update_overall_summary (node
);
3341 /* Vector of pointers which for linked lists of clones of an original crgaph
3344 static vec
<cgraph_edge
*> next_edge_clone
;
3345 static vec
<cgraph_edge
*> prev_edge_clone
;
3348 grow_edge_clone_vectors (void)
3350 if (next_edge_clone
.length ()
3351 <= (unsigned) symtab
->edges_max_uid
)
3352 next_edge_clone
.safe_grow_cleared (symtab
->edges_max_uid
+ 1);
3353 if (prev_edge_clone
.length ()
3354 <= (unsigned) symtab
->edges_max_uid
)
3355 prev_edge_clone
.safe_grow_cleared (symtab
->edges_max_uid
+ 1);
3358 /* Edge duplication hook to grow the appropriate linked list in
3362 ipcp_edge_duplication_hook (struct cgraph_edge
*src
, struct cgraph_edge
*dst
,
3365 grow_edge_clone_vectors ();
3367 struct cgraph_edge
*old_next
= next_edge_clone
[src
->uid
];
3369 prev_edge_clone
[old_next
->uid
] = dst
;
3370 prev_edge_clone
[dst
->uid
] = src
;
3372 next_edge_clone
[dst
->uid
] = old_next
;
3373 next_edge_clone
[src
->uid
] = dst
;
3376 /* Hook that is called by cgraph.c when an edge is removed. */
3379 ipcp_edge_removal_hook (struct cgraph_edge
*cs
, void *)
3381 grow_edge_clone_vectors ();
3383 struct cgraph_edge
*prev
= prev_edge_clone
[cs
->uid
];
3384 struct cgraph_edge
*next
= next_edge_clone
[cs
->uid
];
3386 next_edge_clone
[prev
->uid
] = next
;
3388 prev_edge_clone
[next
->uid
] = prev
;
3391 /* See if NODE is a clone with a known aggregate value at a given OFFSET of a
3392 parameter with the given INDEX. */
3395 get_clone_agg_value (struct cgraph_node
*node
, HOST_WIDE_INT offset
,
3398 struct ipa_agg_replacement_value
*aggval
;
3400 aggval
= ipa_get_agg_replacements_for_node (node
);
3403 if (aggval
->offset
== offset
3404 && aggval
->index
== index
)
3405 return aggval
->value
;
3406 aggval
= aggval
->next
;
3411 /* Return true is NODE is DEST or its clone for all contexts. */
3414 same_node_or_its_all_contexts_clone_p (cgraph_node
*node
, cgraph_node
*dest
)
3419 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3420 return info
->is_all_contexts_clone
&& info
->ipcp_orig_node
== dest
;
3423 /* Return true if edge CS does bring about the value described by SRC to node
3424 DEST or its clone for all contexts. */
3427 cgraph_edge_brings_value_p (cgraph_edge
*cs
, ipcp_value_source
<tree
> *src
,
3430 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3431 enum availability availability
;
3432 cgraph_node
*real_dest
= cs
->callee
->function_symbol (&availability
);
3434 if (!same_node_or_its_all_contexts_clone_p (real_dest
, dest
)
3435 || availability
<= AVAIL_INTERPOSABLE
3436 || caller_info
->node_dead
)
3441 if (caller_info
->ipcp_orig_node
)
3444 if (src
->offset
== -1)
3445 t
= caller_info
->known_csts
[src
->index
];
3447 t
= get_clone_agg_value (cs
->caller
, src
->offset
, src
->index
);
3448 return (t
!= NULL_TREE
3449 && values_equal_for_ipcp_p (src
->val
->value
, t
));
3453 struct ipcp_agg_lattice
*aglat
;
3454 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
3456 if (src
->offset
== -1)
3457 return (plats
->itself
.is_single_const ()
3458 && values_equal_for_ipcp_p (src
->val
->value
,
3459 plats
->itself
.values
->value
));
3462 if (plats
->aggs_bottom
|| plats
->aggs_contain_variable
)
3464 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3465 if (aglat
->offset
== src
->offset
)
3466 return (aglat
->is_single_const ()
3467 && values_equal_for_ipcp_p (src
->val
->value
,
3468 aglat
->values
->value
));
3474 /* Return true if edge CS does bring about the value described by SRC to node
3475 DEST or its clone for all contexts. */
3478 cgraph_edge_brings_value_p (cgraph_edge
*cs
,
3479 ipcp_value_source
<ipa_polymorphic_call_context
> *src
,
3482 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
3483 cgraph_node
*real_dest
= cs
->callee
->function_symbol ();
3485 if (!same_node_or_its_all_contexts_clone_p (real_dest
, dest
)
3486 || caller_info
->node_dead
)
3491 if (caller_info
->ipcp_orig_node
)
3492 return (caller_info
->known_contexts
.length () > (unsigned) src
->index
)
3493 && values_equal_for_ipcp_p (src
->val
->value
,
3494 caller_info
->known_contexts
[src
->index
]);
3496 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (caller_info
,
3498 return plats
->ctxlat
.is_single_const ()
3499 && values_equal_for_ipcp_p (src
->val
->value
,
3500 plats
->ctxlat
.values
->value
);
3503 /* Get the next clone in the linked list of clones of an edge. */
3505 static inline struct cgraph_edge
*
3506 get_next_cgraph_edge_clone (struct cgraph_edge
*cs
)
3508 return next_edge_clone
[cs
->uid
];
3511 /* Given VAL that is intended for DEST, iterate over all its sources and if
3512 they still hold, add their edge frequency and their number into *FREQUENCY
3513 and *CALLER_COUNT respectively. */
3515 template <typename valtype
>
3517 get_info_about_necessary_edges (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
3519 gcov_type
*count_sum
, int *caller_count
)
3521 ipcp_value_source
<valtype
> *src
;
3522 int freq
= 0, count
= 0;
3526 for (src
= val
->sources
; src
; src
= src
->next
)
3528 struct cgraph_edge
*cs
= src
->cs
;
3531 if (cgraph_edge_brings_value_p (cs
, src
, dest
))
3534 freq
+= cs
->frequency
;
3536 hot
|= cs
->maybe_hot_p ();
3538 cs
= get_next_cgraph_edge_clone (cs
);
3544 *caller_count
= count
;
3548 /* Return a vector of incoming edges that do bring value VAL to node DEST. It
3549 is assumed their number is known and equal to CALLER_COUNT. */
3551 template <typename valtype
>
3552 static vec
<cgraph_edge
*>
3553 gather_edges_for_value (ipcp_value
<valtype
> *val
, cgraph_node
*dest
,
3556 ipcp_value_source
<valtype
> *src
;
3557 vec
<cgraph_edge
*> ret
;
3559 ret
.create (caller_count
);
3560 for (src
= val
->sources
; src
; src
= src
->next
)
3562 struct cgraph_edge
*cs
= src
->cs
;
3565 if (cgraph_edge_brings_value_p (cs
, src
, dest
))
3566 ret
.quick_push (cs
);
3567 cs
= get_next_cgraph_edge_clone (cs
);
3574 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
3575 Return it or NULL if for some reason it cannot be created. */
3577 static struct ipa_replace_map
*
3578 get_replacement_map (struct ipa_node_params
*info
, tree value
, int parm_num
)
3580 struct ipa_replace_map
*replace_map
;
3583 replace_map
= ggc_alloc
<ipa_replace_map
> ();
3586 fprintf (dump_file
, " replacing ");
3587 ipa_dump_param (dump_file
, info
, parm_num
);
3589 fprintf (dump_file
, " with const ");
3590 print_generic_expr (dump_file
, value
, 0);
3591 fprintf (dump_file
, "\n");
3593 replace_map
->old_tree
= NULL
;
3594 replace_map
->parm_num
= parm_num
;
3595 replace_map
->new_tree
= value
;
3596 replace_map
->replace_p
= true;
3597 replace_map
->ref_p
= false;
3602 /* Dump new profiling counts */
3605 dump_profile_updates (struct cgraph_node
*orig_node
,
3606 struct cgraph_node
*new_node
)
3608 struct cgraph_edge
*cs
;
3610 fprintf (dump_file
, " setting count of the specialized node to "
3611 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) new_node
->count
);
3612 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3613 fprintf (dump_file
, " edge to %s has count "
3614 HOST_WIDE_INT_PRINT_DEC
"\n",
3615 cs
->callee
->name (), (HOST_WIDE_INT
) cs
->count
);
3617 fprintf (dump_file
, " setting count of the original node to "
3618 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) orig_node
->count
);
3619 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3620 fprintf (dump_file
, " edge to %s is left with "
3621 HOST_WIDE_INT_PRINT_DEC
"\n",
3622 cs
->callee
->name (), (HOST_WIDE_INT
) cs
->count
);
3625 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
3626 their profile information to reflect this. */
3629 update_profiling_info (struct cgraph_node
*orig_node
,
3630 struct cgraph_node
*new_node
)
3632 struct cgraph_edge
*cs
;
3633 struct caller_statistics stats
;
3634 gcov_type new_sum
, orig_sum
;
3635 gcov_type remainder
, orig_node_count
= orig_node
->count
;
3637 if (orig_node_count
== 0)
3640 init_caller_stats (&stats
);
3641 orig_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
3643 orig_sum
= stats
.count_sum
;
3644 init_caller_stats (&stats
);
3645 new_node
->call_for_symbol_thunks_and_aliases (gather_caller_stats
, &stats
,
3647 new_sum
= stats
.count_sum
;
3649 if (orig_node_count
< orig_sum
+ new_sum
)
3652 fprintf (dump_file
, " Problem: node %s/%i has too low count "
3653 HOST_WIDE_INT_PRINT_DEC
" while the sum of incoming "
3654 "counts is " HOST_WIDE_INT_PRINT_DEC
"\n",
3655 orig_node
->name (), orig_node
->order
,
3656 (HOST_WIDE_INT
) orig_node_count
,
3657 (HOST_WIDE_INT
) (orig_sum
+ new_sum
));
3659 orig_node_count
= (orig_sum
+ new_sum
) * 12 / 10;
3661 fprintf (dump_file
, " proceeding by pretending it was "
3662 HOST_WIDE_INT_PRINT_DEC
"\n",
3663 (HOST_WIDE_INT
) orig_node_count
);
3666 new_node
->count
= new_sum
;
3667 remainder
= orig_node_count
- new_sum
;
3668 orig_node
->count
= remainder
;
3670 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3672 cs
->count
= apply_probability (cs
->count
,
3673 GCOV_COMPUTE_SCALE (new_sum
,
3678 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3679 cs
->count
= apply_probability (cs
->count
,
3680 GCOV_COMPUTE_SCALE (remainder
,
3684 dump_profile_updates (orig_node
, new_node
);
3687 /* Update the respective profile of specialized NEW_NODE and the original
3688 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
3689 have been redirected to the specialized version. */
3692 update_specialized_profile (struct cgraph_node
*new_node
,
3693 struct cgraph_node
*orig_node
,
3694 gcov_type redirected_sum
)
3696 struct cgraph_edge
*cs
;
3697 gcov_type new_node_count
, orig_node_count
= orig_node
->count
;
3700 fprintf (dump_file
, " the sum of counts of redirected edges is "
3701 HOST_WIDE_INT_PRINT_DEC
"\n", (HOST_WIDE_INT
) redirected_sum
);
3702 if (orig_node_count
== 0)
3705 gcc_assert (orig_node_count
>= redirected_sum
);
3707 new_node_count
= new_node
->count
;
3708 new_node
->count
+= redirected_sum
;
3709 orig_node
->count
-= redirected_sum
;
3711 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
3713 cs
->count
+= apply_probability (cs
->count
,
3714 GCOV_COMPUTE_SCALE (redirected_sum
,
3719 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
3721 gcov_type dec
= apply_probability (cs
->count
,
3722 GCOV_COMPUTE_SCALE (redirected_sum
,
3724 if (dec
< cs
->count
)
3731 dump_profile_updates (orig_node
, new_node
);
3734 /* Create a specialized version of NODE with known constants in KNOWN_CSTS,
3735 known contexts in KNOWN_CONTEXTS and known aggregate values in AGGVALS and
3736 redirect all edges in CALLERS to it. */
3738 static struct cgraph_node
*
3739 create_specialized_node (struct cgraph_node
*node
,
3740 vec
<tree
> known_csts
,
3741 vec
<ipa_polymorphic_call_context
> known_contexts
,
3742 struct ipa_agg_replacement_value
*aggvals
,
3743 vec
<cgraph_edge
*> callers
)
3745 struct ipa_node_params
*new_info
, *info
= IPA_NODE_REF (node
);
3746 vec
<ipa_replace_map
*, va_gc
> *replace_trees
= NULL
;
3747 struct ipa_agg_replacement_value
*av
;
3748 struct cgraph_node
*new_node
;
3749 int i
, count
= ipa_get_param_count (info
);
3750 bitmap args_to_skip
;
3752 gcc_assert (!info
->ipcp_orig_node
);
3754 if (node
->local
.can_change_signature
)
3756 args_to_skip
= BITMAP_GGC_ALLOC ();
3757 for (i
= 0; i
< count
; i
++)
3759 tree t
= known_csts
[i
];
3761 if (t
|| !ipa_is_param_used (info
, i
))
3762 bitmap_set_bit (args_to_skip
, i
);
3767 args_to_skip
= NULL
;
3768 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3769 fprintf (dump_file
, " cannot change function signature\n");
3772 for (i
= 0; i
< count
; i
++)
3774 tree t
= known_csts
[i
];
3777 struct ipa_replace_map
*replace_map
;
3779 gcc_checking_assert (TREE_CODE (t
) != TREE_BINFO
);
3780 replace_map
= get_replacement_map (info
, t
, i
);
3782 vec_safe_push (replace_trees
, replace_map
);
3786 new_node
= node
->create_virtual_clone (callers
, replace_trees
,
3787 args_to_skip
, "constprop");
3788 ipa_set_node_agg_value_chain (new_node
, aggvals
);
3789 for (av
= aggvals
; av
; av
= av
->next
)
3790 new_node
->maybe_create_reference (av
->value
, IPA_REF_ADDR
, NULL
);
3792 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3794 fprintf (dump_file
, " the new node is %s/%i.\n",
3795 new_node
->name (), new_node
->order
);
3796 if (known_contexts
.exists ())
3798 for (i
= 0; i
< count
; i
++)
3799 if (!known_contexts
[i
].useless_p ())
3801 fprintf (dump_file
, " known ctx %i is ", i
);
3802 known_contexts
[i
].dump (dump_file
);
3806 ipa_dump_agg_replacement_values (dump_file
, aggvals
);
3808 ipa_check_create_node_params ();
3809 update_profiling_info (node
, new_node
);
3810 new_info
= IPA_NODE_REF (new_node
);
3811 new_info
->ipcp_orig_node
= node
;
3812 new_info
->known_csts
= known_csts
;
3813 new_info
->known_contexts
= known_contexts
;
3815 ipcp_discover_new_direct_edges (new_node
, known_csts
, known_contexts
, aggvals
);
3821 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
3822 KNOWN_CSTS with constants that are also known for all of the CALLERS. */
3825 find_more_scalar_values_for_callers_subset (struct cgraph_node
*node
,
3826 vec
<tree
> known_csts
,
3827 vec
<cgraph_edge
*> callers
)
3829 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
3830 int i
, count
= ipa_get_param_count (info
);
3832 for (i
= 0; i
< count
; i
++)
3834 struct cgraph_edge
*cs
;
3835 tree newval
= NULL_TREE
;
3839 if (ipa_get_scalar_lat (info
, i
)->bottom
|| known_csts
[i
])
3842 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3844 struct ipa_jump_func
*jump_func
;
3847 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
))
3849 && call_passes_through_thunk_p (cs
))
3850 || (!cs
->callee
->instrumentation_clone
3851 && cs
->callee
->function_symbol ()->instrumentation_clone
))
3856 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
3857 t
= ipa_value_from_jfunc (IPA_NODE_REF (cs
->caller
), jump_func
);
3860 && !values_equal_for_ipcp_p (t
, newval
))
3861 || (!first
&& !newval
))
3873 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3875 fprintf (dump_file
, " adding an extra known scalar value ");
3876 print_ipcp_constant_value (dump_file
, newval
);
3877 fprintf (dump_file
, " for ");
3878 ipa_dump_param (dump_file
, info
, i
);
3879 fprintf (dump_file
, "\n");
3882 known_csts
[i
] = newval
;
3887 /* Given a NODE and a subset of its CALLERS, try to populate plank slots in
3888 KNOWN_CONTEXTS with polymorphic contexts that are also known for all of the
3892 find_more_contexts_for_caller_subset (cgraph_node
*node
,
3893 vec
<ipa_polymorphic_call_context
>
3895 vec
<cgraph_edge
*> callers
)
3897 ipa_node_params
*info
= IPA_NODE_REF (node
);
3898 int i
, count
= ipa_get_param_count (info
);
3900 for (i
= 0; i
< count
; i
++)
3904 if (ipa_get_poly_ctx_lat (info
, i
)->bottom
3905 || (known_contexts
->exists ()
3906 && !(*known_contexts
)[i
].useless_p ()))
3909 ipa_polymorphic_call_context newval
;
3913 FOR_EACH_VEC_ELT (callers
, j
, cs
)
3915 if (i
>= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
)))
3917 ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
),
3919 ipa_polymorphic_call_context ctx
;
3920 ctx
= ipa_context_from_jfunc (IPA_NODE_REF (cs
->caller
), cs
, i
,
3928 newval
.meet_with (ctx
);
3929 if (newval
.useless_p ())
3933 if (!newval
.useless_p ())
3935 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3937 fprintf (dump_file
, " adding an extra known polymorphic "
3939 print_ipcp_constant_value (dump_file
, newval
);
3940 fprintf (dump_file
, " for ");
3941 ipa_dump_param (dump_file
, info
, i
);
3942 fprintf (dump_file
, "\n");
3945 if (!known_contexts
->exists ())
3946 known_contexts
->safe_grow_cleared (ipa_get_param_count (info
));
3947 (*known_contexts
)[i
] = newval
;
3953 /* Go through PLATS and create a vector of values consisting of values and
3954 offsets (minus OFFSET) of lattices that contain only a single value. */
3956 static vec
<ipa_agg_jf_item
>
3957 copy_plats_to_inter (struct ipcp_param_lattices
*plats
, HOST_WIDE_INT offset
)
3959 vec
<ipa_agg_jf_item
> res
= vNULL
;
3961 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
3964 for (struct ipcp_agg_lattice
*aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
3965 if (aglat
->is_single_const ())
3967 struct ipa_agg_jf_item ti
;
3968 ti
.offset
= aglat
->offset
- offset
;
3969 ti
.value
= aglat
->values
->value
;
3975 /* Intersect all values in INTER with single value lattices in PLATS (while
3976 subtracting OFFSET). */
3979 intersect_with_plats (struct ipcp_param_lattices
*plats
,
3980 vec
<ipa_agg_jf_item
> *inter
,
3981 HOST_WIDE_INT offset
)
3983 struct ipcp_agg_lattice
*aglat
;
3984 struct ipa_agg_jf_item
*item
;
3987 if (!plats
->aggs
|| plats
->aggs_contain_variable
|| plats
->aggs_bottom
)
3993 aglat
= plats
->aggs
;
3994 FOR_EACH_VEC_ELT (*inter
, k
, item
)
4001 if (aglat
->offset
- offset
> item
->offset
)
4003 if (aglat
->offset
- offset
== item
->offset
)
4005 gcc_checking_assert (item
->value
);
4006 if (values_equal_for_ipcp_p (item
->value
, aglat
->values
->value
))
4010 aglat
= aglat
->next
;
4013 item
->value
= NULL_TREE
;
4017 /* Copy agggregate replacement values of NODE (which is an IPA-CP clone) to the
4018 vector result while subtracting OFFSET from the individual value offsets. */
4020 static vec
<ipa_agg_jf_item
>
4021 agg_replacements_to_vector (struct cgraph_node
*node
, int index
,
4022 HOST_WIDE_INT offset
)
4024 struct ipa_agg_replacement_value
*av
;
4025 vec
<ipa_agg_jf_item
> res
= vNULL
;
4027 for (av
= ipa_get_agg_replacements_for_node (node
); av
; av
= av
->next
)
4028 if (av
->index
== index
4029 && (av
->offset
- offset
) >= 0)
4031 struct ipa_agg_jf_item item
;
4032 gcc_checking_assert (av
->value
);
4033 item
.offset
= av
->offset
- offset
;
4034 item
.value
= av
->value
;
4035 res
.safe_push (item
);
4041 /* Intersect all values in INTER with those that we have already scheduled to
4042 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
4043 (while subtracting OFFSET). */
4046 intersect_with_agg_replacements (struct cgraph_node
*node
, int index
,
4047 vec
<ipa_agg_jf_item
> *inter
,
4048 HOST_WIDE_INT offset
)
4050 struct ipa_agg_replacement_value
*srcvals
;
4051 struct ipa_agg_jf_item
*item
;
4054 srcvals
= ipa_get_agg_replacements_for_node (node
);
4061 FOR_EACH_VEC_ELT (*inter
, i
, item
)
4063 struct ipa_agg_replacement_value
*av
;
4067 for (av
= srcvals
; av
; av
= av
->next
)
4069 gcc_checking_assert (av
->value
);
4070 if (av
->index
== index
4071 && av
->offset
- offset
== item
->offset
)
4073 if (values_equal_for_ipcp_p (item
->value
, av
->value
))
4079 item
->value
= NULL_TREE
;
4083 /* Intersect values in INTER with aggregate values that come along edge CS to
4084 parameter number INDEX and return it. If INTER does not actually exist yet,
4085 copy all incoming values to it. If we determine we ended up with no values
4086 whatsoever, return a released vector. */
4088 static vec
<ipa_agg_jf_item
>
4089 intersect_aggregates_with_edge (struct cgraph_edge
*cs
, int index
,
4090 vec
<ipa_agg_jf_item
> inter
)
4092 struct ipa_jump_func
*jfunc
;
4093 jfunc
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), index
);
4094 if (jfunc
->type
== IPA_JF_PASS_THROUGH
4095 && ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
4097 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4098 int src_idx
= ipa_get_jf_pass_through_formal_id (jfunc
);
4100 if (caller_info
->ipcp_orig_node
)
4102 struct cgraph_node
*orig_node
= caller_info
->ipcp_orig_node
;
4103 struct ipcp_param_lattices
*orig_plats
;
4104 orig_plats
= ipa_get_parm_lattices (IPA_NODE_REF (orig_node
),
4106 if (agg_pass_through_permissible_p (orig_plats
, jfunc
))
4108 if (!inter
.exists ())
4109 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, 0);
4111 intersect_with_agg_replacements (cs
->caller
, src_idx
,
4122 struct ipcp_param_lattices
*src_plats
;
4123 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);
4124 if (agg_pass_through_permissible_p (src_plats
, jfunc
))
4126 /* Currently we do not produce clobber aggregate jump
4127 functions, adjust when we do. */
4128 gcc_checking_assert (!jfunc
->agg
.items
);
4129 if (!inter
.exists ())
4130 inter
= copy_plats_to_inter (src_plats
, 0);
4132 intersect_with_plats (src_plats
, &inter
, 0);
4141 else if (jfunc
->type
== IPA_JF_ANCESTOR
4142 && ipa_get_jf_ancestor_agg_preserved (jfunc
))
4144 struct ipa_node_params
*caller_info
= IPA_NODE_REF (cs
->caller
);
4145 int src_idx
= ipa_get_jf_ancestor_formal_id (jfunc
);
4146 struct ipcp_param_lattices
*src_plats
;
4147 HOST_WIDE_INT delta
= ipa_get_jf_ancestor_offset (jfunc
);
4149 if (caller_info
->ipcp_orig_node
)
4151 if (!inter
.exists ())
4152 inter
= agg_replacements_to_vector (cs
->caller
, src_idx
, delta
);
4154 intersect_with_agg_replacements (cs
->caller
, src_idx
, &inter
,
4159 src_plats
= ipa_get_parm_lattices (caller_info
, src_idx
);;
4160 /* Currently we do not produce clobber aggregate jump
4161 functions, adjust when we do. */
4162 gcc_checking_assert (!src_plats
->aggs
|| !jfunc
->agg
.items
);
4163 if (!inter
.exists ())
4164 inter
= copy_plats_to_inter (src_plats
, delta
);
4166 intersect_with_plats (src_plats
, &inter
, delta
);
4169 else if (jfunc
->agg
.items
)
4171 struct ipa_agg_jf_item
*item
;
4174 if (!inter
.exists ())
4175 for (unsigned i
= 0; i
< jfunc
->agg
.items
->length (); i
++)
4176 inter
.safe_push ((*jfunc
->agg
.items
)[i
]);
4178 FOR_EACH_VEC_ELT (inter
, k
, item
)
4181 bool found
= false;;
4186 while ((unsigned) l
< jfunc
->agg
.items
->length ())
4188 struct ipa_agg_jf_item
*ti
;
4189 ti
= &(*jfunc
->agg
.items
)[l
];
4190 if (ti
->offset
> item
->offset
)
4192 if (ti
->offset
== item
->offset
)
4194 gcc_checking_assert (ti
->value
);
4195 if (values_equal_for_ipcp_p (item
->value
,
4209 return vec
<ipa_agg_jf_item
>();
4214 /* Look at edges in CALLERS and collect all known aggregate values that arrive
4215 from all of them. */
4217 static struct ipa_agg_replacement_value
*
4218 find_aggregate_values_for_callers_subset (struct cgraph_node
*node
,
4219 vec
<cgraph_edge
*> callers
)
4221 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
4222 struct ipa_agg_replacement_value
*res
;
4223 struct ipa_agg_replacement_value
**tail
= &res
;
4224 struct cgraph_edge
*cs
;
4225 int i
, j
, count
= ipa_get_param_count (dest_info
);
4227 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4229 int c
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
4234 for (i
= 0; i
< count
; i
++)
4236 struct cgraph_edge
*cs
;
4237 vec
<ipa_agg_jf_item
> inter
= vNULL
;
4238 struct ipa_agg_jf_item
*item
;
4239 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (dest_info
, i
);
4242 /* Among other things, the following check should deal with all by_ref
4244 if (plats
->aggs_bottom
)
4247 FOR_EACH_VEC_ELT (callers
, j
, cs
)
4249 inter
= intersect_aggregates_with_edge (cs
, i
, inter
);
4251 if (!inter
.exists ())
4255 FOR_EACH_VEC_ELT (inter
, j
, item
)
4257 struct ipa_agg_replacement_value
*v
;
4262 v
= ggc_alloc
<ipa_agg_replacement_value
> ();
4264 v
->offset
= item
->offset
;
4265 v
->value
= item
->value
;
4266 v
->by_ref
= plats
->aggs_by_ref
;
4272 if (inter
.exists ())
4279 /* Turn KNOWN_AGGS into a list of aggreate replacement values. */
4281 static struct ipa_agg_replacement_value
*
4282 known_aggs_to_agg_replacement_list (vec
<ipa_agg_jump_function
> known_aggs
)
4284 struct ipa_agg_replacement_value
*res
;
4285 struct ipa_agg_replacement_value
**tail
= &res
;
4286 struct ipa_agg_jump_function
*aggjf
;
4287 struct ipa_agg_jf_item
*item
;
4290 FOR_EACH_VEC_ELT (known_aggs
, i
, aggjf
)
4291 FOR_EACH_VEC_SAFE_ELT (aggjf
->items
, j
, item
)
4293 struct ipa_agg_replacement_value
*v
;
4294 v
= ggc_alloc
<ipa_agg_replacement_value
> ();
4296 v
->offset
= item
->offset
;
4297 v
->value
= item
->value
;
4298 v
->by_ref
= aggjf
->by_ref
;
4306 /* Determine whether CS also brings all scalar values that the NODE is
4310 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge
*cs
,
4311 struct cgraph_node
*node
)
4313 struct ipa_node_params
*dest_info
= IPA_NODE_REF (node
);
4314 int count
= ipa_get_param_count (dest_info
);
4315 struct ipa_node_params
*caller_info
;
4316 struct ipa_edge_args
*args
;
4319 caller_info
= IPA_NODE_REF (cs
->caller
);
4320 args
= IPA_EDGE_REF (cs
);
4321 for (i
= 0; i
< count
; i
++)
4323 struct ipa_jump_func
*jump_func
;
4326 val
= dest_info
->known_csts
[i
];
4330 if (i
>= ipa_get_cs_argument_count (args
))
4332 jump_func
= ipa_get_ith_jump_func (args
, i
);
4333 t
= ipa_value_from_jfunc (caller_info
, jump_func
);
4334 if (!t
|| !values_equal_for_ipcp_p (val
, t
))
4340 /* Determine whether CS also brings all aggregate values that NODE is
4343 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge
*cs
,
4344 struct cgraph_node
*node
)
4346 struct ipa_node_params
*orig_caller_info
= IPA_NODE_REF (cs
->caller
);
4347 struct ipa_node_params
*orig_node_info
;
4348 struct ipa_agg_replacement_value
*aggval
;
4351 aggval
= ipa_get_agg_replacements_for_node (node
);
4355 count
= ipa_get_param_count (IPA_NODE_REF (node
));
4356 ec
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
4358 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4359 if (aggval
->index
>= ec
)
4362 orig_node_info
= IPA_NODE_REF (IPA_NODE_REF (node
)->ipcp_orig_node
);
4363 if (orig_caller_info
->ipcp_orig_node
)
4364 orig_caller_info
= IPA_NODE_REF (orig_caller_info
->ipcp_orig_node
);
4366 for (i
= 0; i
< count
; i
++)
4368 static vec
<ipa_agg_jf_item
> values
= vec
<ipa_agg_jf_item
>();
4369 struct ipcp_param_lattices
*plats
;
4370 bool interesting
= false;
4371 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4372 if (aggval
->index
== i
)
4380 plats
= ipa_get_parm_lattices (orig_node_info
, aggval
->index
);
4381 if (plats
->aggs_bottom
)
4384 values
= intersect_aggregates_with_edge (cs
, i
, values
);
4385 if (!values
.exists ())
4388 for (struct ipa_agg_replacement_value
*av
= aggval
; av
; av
= av
->next
)
4389 if (aggval
->index
== i
)
4391 struct ipa_agg_jf_item
*item
;
4394 FOR_EACH_VEC_ELT (values
, j
, item
)
4396 && item
->offset
== av
->offset
4397 && values_equal_for_ipcp_p (item
->value
, av
->value
))
4412 /* Given an original NODE and a VAL for which we have already created a
4413 specialized clone, look whether there are incoming edges that still lead
4414 into the old node but now also bring the requested value and also conform to
4415 all other criteria such that they can be redirected the special node.
4416 This function can therefore redirect the final edge in a SCC. */
4418 template <typename valtype
>
4420 perhaps_add_new_callers (cgraph_node
*node
, ipcp_value
<valtype
> *val
)
4422 ipcp_value_source
<valtype
> *src
;
4423 gcov_type redirected_sum
= 0;
4425 for (src
= val
->sources
; src
; src
= src
->next
)
4427 struct cgraph_edge
*cs
= src
->cs
;
4430 if (cgraph_edge_brings_value_p (cs
, src
, node
)
4431 && cgraph_edge_brings_all_scalars_for_node (cs
, val
->spec_node
)
4432 && cgraph_edge_brings_all_agg_vals_for_node (cs
, val
->spec_node
))
4435 fprintf (dump_file
, " - adding an extra caller %s/%i"
4437 xstrdup_for_dump (cs
->caller
->name ()),
4439 xstrdup_for_dump (val
->spec_node
->name ()),
4440 val
->spec_node
->order
);
4442 cs
->redirect_callee_duplicating_thunks (val
->spec_node
);
4443 val
->spec_node
->expand_all_artificial_thunks ();
4444 redirected_sum
+= cs
->count
;
4446 cs
= get_next_cgraph_edge_clone (cs
);
4451 update_specialized_profile (val
->spec_node
, node
, redirected_sum
);
4454 /* Return true if KNOWN_CONTEXTS contain at least one useful context. */
4457 known_contexts_useful_p (vec
<ipa_polymorphic_call_context
> known_contexts
)
4459 ipa_polymorphic_call_context
*ctx
;
4462 FOR_EACH_VEC_ELT (known_contexts
, i
, ctx
)
4463 if (!ctx
->useless_p ())
4468 /* Return a copy of KNOWN_CSTS if it is not empty, otherwise return vNULL. */
4470 static vec
<ipa_polymorphic_call_context
>
4471 copy_useful_known_contexts (vec
<ipa_polymorphic_call_context
> known_contexts
)
4473 if (known_contexts_useful_p (known_contexts
))
4474 return known_contexts
.copy ();
4479 /* Copy KNOWN_CSTS and modify the copy according to VAL and INDEX. If
4480 non-empty, replace KNOWN_CONTEXTS with its copy too. */
4483 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
4484 vec
<ipa_polymorphic_call_context
> *known_contexts
,
4485 ipcp_value
<tree
> *val
,
4488 *known_csts
= known_csts
->copy ();
4489 *known_contexts
= copy_useful_known_contexts (*known_contexts
);
4490 (*known_csts
)[index
] = val
->value
;
4493 /* Replace KNOWN_CSTS with its copy. Also copy KNOWN_CONTEXTS and modify the
4494 copy according to VAL and INDEX. */
4497 modify_known_vectors_with_val (vec
<tree
> *known_csts
,
4498 vec
<ipa_polymorphic_call_context
> *known_contexts
,
4499 ipcp_value
<ipa_polymorphic_call_context
> *val
,
4502 *known_csts
= known_csts
->copy ();
4503 *known_contexts
= known_contexts
->copy ();
4504 (*known_contexts
)[index
] = val
->value
;
4507 /* Return true if OFFSET indicates this was not an aggregate value or there is
4508 a replacement equivalent to VALUE, INDEX and OFFSET among those in the
4512 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*aggvals
,
4513 int index
, HOST_WIDE_INT offset
, tree value
)
4520 if (aggvals
->index
== index
4521 && aggvals
->offset
== offset
4522 && values_equal_for_ipcp_p (aggvals
->value
, value
))
4524 aggvals
= aggvals
->next
;
4529 /* Return true if offset is minus one because source of a polymorphic contect
4530 cannot be an aggregate value. */
4533 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value
*,
4534 int , HOST_WIDE_INT offset
,
4535 ipa_polymorphic_call_context
)
4537 return offset
== -1;
4540 /* Decide wheter to create a special version of NODE for value VAL of parameter
4541 at the given INDEX. If OFFSET is -1, the value is for the parameter itself,
4542 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS,
4543 KNOWN_CONTEXTS and KNOWN_AGGS describe the other already known values. */
4545 template <typename valtype
>
4547 decide_about_value (struct cgraph_node
*node
, int index
, HOST_WIDE_INT offset
,
4548 ipcp_value
<valtype
> *val
, vec
<tree
> known_csts
,
4549 vec
<ipa_polymorphic_call_context
> known_contexts
)
4551 struct ipa_agg_replacement_value
*aggvals
;
4552 int freq_sum
, caller_count
;
4553 gcov_type count_sum
;
4554 vec
<cgraph_edge
*> callers
;
4558 perhaps_add_new_callers (node
, val
);
4561 else if (val
->local_size_cost
+ overall_size
> max_new_size
)
4563 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4564 fprintf (dump_file
, " Ignoring candidate value because "
4565 "max_new_size would be reached with %li.\n",
4566 val
->local_size_cost
+ overall_size
);
4569 else if (!get_info_about_necessary_edges (val
, node
, &freq_sum
, &count_sum
,
4573 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4575 fprintf (dump_file
, " - considering value ");
4576 print_ipcp_constant_value (dump_file
, val
->value
);
4577 fprintf (dump_file
, " for ");
4578 ipa_dump_param (dump_file
, IPA_NODE_REF (node
), index
);
4580 fprintf (dump_file
, ", offset: " HOST_WIDE_INT_PRINT_DEC
, offset
);
4581 fprintf (dump_file
, " (caller_count: %i)\n", caller_count
);
4584 if (!good_cloning_opportunity_p (node
, val
->local_time_benefit
,
4585 freq_sum
, count_sum
,
4586 val
->local_size_cost
)
4587 && !good_cloning_opportunity_p (node
,
4588 val
->local_time_benefit
4589 + val
->prop_time_benefit
,
4590 freq_sum
, count_sum
,
4591 val
->local_size_cost
4592 + val
->prop_size_cost
))
4596 fprintf (dump_file
, " Creating a specialized node of %s/%i.\n",
4597 node
->name (), node
->order
);
4599 callers
= gather_edges_for_value (val
, node
, caller_count
);
4601 modify_known_vectors_with_val (&known_csts
, &known_contexts
, val
, index
);
4604 known_csts
= known_csts
.copy ();
4605 known_contexts
= copy_useful_known_contexts (known_contexts
);
4607 find_more_scalar_values_for_callers_subset (node
, known_csts
, callers
);
4608 find_more_contexts_for_caller_subset (node
, &known_contexts
, callers
);
4609 aggvals
= find_aggregate_values_for_callers_subset (node
, callers
);
4610 gcc_checking_assert (ipcp_val_agg_replacement_ok_p (aggvals
, index
,
4611 offset
, val
->value
));
4612 val
->spec_node
= create_specialized_node (node
, known_csts
, known_contexts
,
4614 overall_size
+= val
->local_size_cost
;
4616 /* TODO: If for some lattice there is only one other known value
4617 left, make a special node for it too. */
4622 /* Decide whether and what specialized clones of NODE should be created. */
4625 decide_whether_version_node (struct cgraph_node
*node
)
4627 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
4628 int i
, count
= ipa_get_param_count (info
);
4629 vec
<tree
> known_csts
;
4630 vec
<ipa_polymorphic_call_context
> known_contexts
;
4631 vec
<ipa_agg_jump_function
> known_aggs
= vNULL
;
4637 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4638 fprintf (dump_file
, "\nEvaluating opportunities for %s/%i.\n",
4639 node
->name (), node
->order
);
4641 gather_context_independent_values (info
, &known_csts
, &known_contexts
,
4642 info
->do_clone_for_all_contexts
? &known_aggs
4645 for (i
= 0; i
< count
;i
++)
4647 struct ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4648 ipcp_lattice
<tree
> *lat
= &plats
->itself
;
4649 ipcp_lattice
<ipa_polymorphic_call_context
> *ctxlat
= &plats
->ctxlat
;
4654 ipcp_value
<tree
> *val
;
4655 for (val
= lat
->values
; val
; val
= val
->next
)
4656 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
4660 if (!plats
->aggs_bottom
)
4662 struct ipcp_agg_lattice
*aglat
;
4663 ipcp_value
<tree
> *val
;
4664 for (aglat
= plats
->aggs
; aglat
; aglat
= aglat
->next
)
4665 if (!aglat
->bottom
&& aglat
->values
4666 /* If the following is false, the one value is in
4668 && (plats
->aggs_contain_variable
4669 || !aglat
->is_single_const ()))
4670 for (val
= aglat
->values
; val
; val
= val
->next
)
4671 ret
|= decide_about_value (node
, i
, aglat
->offset
, val
,
4672 known_csts
, known_contexts
);
4676 && known_contexts
[i
].useless_p ())
4678 ipcp_value
<ipa_polymorphic_call_context
> *val
;
4679 for (val
= ctxlat
->values
; val
; val
= val
->next
)
4680 ret
|= decide_about_value (node
, i
, -1, val
, known_csts
,
4684 info
= IPA_NODE_REF (node
);
4687 if (info
->do_clone_for_all_contexts
)
4689 struct cgraph_node
*clone
;
4690 vec
<cgraph_edge
*> callers
;
4693 fprintf (dump_file
, " - Creating a specialized node of %s/%i "
4694 "for all known contexts.\n", node
->name (),
4697 callers
= node
->collect_callers ();
4699 if (!known_contexts_useful_p (known_contexts
))
4701 known_contexts
.release ();
4702 known_contexts
= vNULL
;
4704 clone
= create_specialized_node (node
, known_csts
, known_contexts
,
4705 known_aggs_to_agg_replacement_list (known_aggs
),
4707 info
= IPA_NODE_REF (node
);
4708 info
->do_clone_for_all_contexts
= false;
4709 IPA_NODE_REF (clone
)->is_all_contexts_clone
= true;
4710 for (i
= 0; i
< count
; i
++)
4711 vec_free (known_aggs
[i
].items
);
4712 known_aggs
.release ();
4717 known_csts
.release ();
4718 known_contexts
.release ();
4724 /* Transitively mark all callees of NODE within the same SCC as not dead. */
4727 spread_undeadness (struct cgraph_node
*node
)
4729 struct cgraph_edge
*cs
;
4731 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
4732 if (ipa_edge_within_scc (cs
))
4734 struct cgraph_node
*callee
;
4735 struct ipa_node_params
*info
;
4737 callee
= cs
->callee
->function_symbol (NULL
);
4738 info
= IPA_NODE_REF (callee
);
4740 if (info
->node_dead
)
4742 info
->node_dead
= 0;
4743 spread_undeadness (callee
);
4748 /* Return true if NODE has a caller from outside of its SCC that is not
4749 dead. Worker callback for cgraph_for_node_and_aliases. */
4752 has_undead_caller_from_outside_scc_p (struct cgraph_node
*node
,
4753 void *data ATTRIBUTE_UNUSED
)
4755 struct cgraph_edge
*cs
;
4757 for (cs
= node
->callers
; cs
; cs
= cs
->next_caller
)
4758 if (cs
->caller
->thunk
.thunk_p
4759 && cs
->caller
->call_for_symbol_thunks_and_aliases
4760 (has_undead_caller_from_outside_scc_p
, NULL
, true))
4762 else if (!ipa_edge_within_scc (cs
)
4763 && !IPA_NODE_REF (cs
->caller
)->node_dead
)
4769 /* Identify nodes within the same SCC as NODE which are no longer needed
4770 because of new clones and will be removed as unreachable. */
4773 identify_dead_nodes (struct cgraph_node
*node
)
4775 struct cgraph_node
*v
;
4776 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4778 && !v
->call_for_symbol_thunks_and_aliases
4779 (has_undead_caller_from_outside_scc_p
, NULL
, true))
4780 IPA_NODE_REF (v
)->node_dead
= 1;
4782 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4783 if (!IPA_NODE_REF (v
)->node_dead
)
4784 spread_undeadness (v
);
4786 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4788 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4789 if (IPA_NODE_REF (v
)->node_dead
)
4790 fprintf (dump_file
, " Marking node as dead: %s/%i.\n",
4791 v
->name (), v
->order
);
4795 /* The decision stage. Iterate over the topological order of call graph nodes
4796 TOPO and make specialized clones if deemed beneficial. */
4799 ipcp_decision_stage (struct ipa_topo_info
*topo
)
4804 fprintf (dump_file
, "\nIPA decision stage:\n\n");
4806 for (i
= topo
->nnodes
- 1; i
>= 0; i
--)
4808 struct cgraph_node
*node
= topo
->order
[i
];
4809 bool change
= false, iterate
= true;
4813 struct cgraph_node
*v
;
4815 for (v
= node
; v
; v
= ((struct ipa_dfs_info
*) v
->aux
)->next_cycle
)
4816 if (v
->has_gimple_body_p ()
4817 && ipcp_versionable_function_p (v
))
4818 iterate
|= decide_whether_version_node (v
);
4823 identify_dead_nodes (node
);
4827 /* Look up all the bits information that we have discovered and copy it over
4828 to the transformation summary. */
4831 ipcp_store_bits_results (void)
4835 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
4837 ipa_node_params
*info
= IPA_NODE_REF (node
);
4838 bool dumped_sth
= false;
4839 bool found_useful_result
= false;
4841 if (!opt_for_fn (node
->decl
, flag_ipa_bit_cp
))
4844 fprintf (dump_file
, "Not considering %s for ipa bitwise propagation "
4845 "; -fipa-bit-cp: disabled.\n",
4850 if (info
->ipcp_orig_node
)
4851 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
4853 unsigned count
= ipa_get_param_count (info
);
4854 for (unsigned i
= 0; i
< count
; i
++)
4856 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4857 if (plats
->bits_lattice
.constant_p ())
4859 found_useful_result
= true;
4864 if (!found_useful_result
)
4867 ipcp_grow_transformations_if_necessary ();
4868 ipcp_transformation_summary
*ts
= ipcp_get_transformation_summary (node
);
4869 vec_safe_reserve_exact (ts
->bits
, count
);
4871 for (unsigned i
= 0; i
< count
; i
++)
4873 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4874 ipa_bits bits_jfunc
;
4876 if (plats
->bits_lattice
.constant_p ())
4878 bits_jfunc
.known
= true;
4879 bits_jfunc
.value
= plats
->bits_lattice
.get_value ();
4880 bits_jfunc
.mask
= plats
->bits_lattice
.get_mask ();
4883 bits_jfunc
.known
= false;
4885 ts
->bits
->quick_push (bits_jfunc
);
4886 if (!dump_file
|| !bits_jfunc
.known
)
4890 fprintf (dump_file
, "Propagated bits info for function %s/%i:\n",
4891 node
->name (), node
->order
);
4894 fprintf (dump_file
, " param %i: value = ", i
);
4895 print_hex (bits_jfunc
.value
, dump_file
);
4896 fprintf (dump_file
, ", mask = ");
4897 print_hex (bits_jfunc
.mask
, dump_file
);
4898 fprintf (dump_file
, "\n");
4903 /* Look up all VR information that we have discovered and copy it over
4904 to the transformation summary. */
4907 ipcp_store_vr_results (void)
4911 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
4913 ipa_node_params
*info
= IPA_NODE_REF (node
);
4914 bool found_useful_result
= false;
4916 if (!opt_for_fn (node
->decl
, flag_ipa_vrp
))
4919 fprintf (dump_file
, "Not considering %s for VR discovery "
4920 "and propagate; -fipa-ipa-vrp: disabled.\n",
4925 if (info
->ipcp_orig_node
)
4926 info
= IPA_NODE_REF (info
->ipcp_orig_node
);
4928 unsigned count
= ipa_get_param_count (info
);
4929 for (unsigned i
= 0; i
< count
; i
++)
4931 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4932 if (!plats
->m_value_range
.bottom_p ()
4933 && !plats
->m_value_range
.top_p ())
4935 found_useful_result
= true;
4939 if (!found_useful_result
)
4942 ipcp_grow_transformations_if_necessary ();
4943 ipcp_transformation_summary
*ts
= ipcp_get_transformation_summary (node
);
4944 vec_safe_reserve_exact (ts
->m_vr
, count
);
4946 for (unsigned i
= 0; i
< count
; i
++)
4948 ipcp_param_lattices
*plats
= ipa_get_parm_lattices (info
, i
);
4951 if (!plats
->m_value_range
.bottom_p ()
4952 && !plats
->m_value_range
.top_p ())
4955 vr
.type
= plats
->m_value_range
.m_vr
.type
;
4956 vr
.min
= plats
->m_value_range
.m_vr
.min
;
4957 vr
.max
= plats
->m_value_range
.m_vr
.max
;
4962 vr
.type
= VR_VARYING
;
4963 vr
.min
= vr
.max
= wi::zero (INT_TYPE_SIZE
);
4965 ts
->m_vr
->quick_push (vr
);
4970 /* The IPCP driver. */
4975 struct cgraph_2edge_hook_list
*edge_duplication_hook_holder
;
4976 struct cgraph_edge_hook_list
*edge_removal_hook_holder
;
4977 struct ipa_topo_info topo
;
4979 ipa_check_create_node_params ();
4980 ipa_check_create_edge_args ();
4981 grow_edge_clone_vectors ();
4982 edge_duplication_hook_holder
4983 = symtab
->add_edge_duplication_hook (&ipcp_edge_duplication_hook
, NULL
);
4984 edge_removal_hook_holder
4985 = symtab
->add_edge_removal_hook (&ipcp_edge_removal_hook
, NULL
);
4989 fprintf (dump_file
, "\nIPA structures before propagation:\n");
4990 if (dump_flags
& TDF_DETAILS
)
4991 ipa_print_all_params (dump_file
);
4992 ipa_print_all_jump_functions (dump_file
);
4995 /* Topological sort. */
4996 build_toporder_info (&topo
);
4997 /* Do the interprocedural propagation. */
4998 ipcp_propagate_stage (&topo
);
4999 /* Decide what constant propagation and cloning should be performed. */
5000 ipcp_decision_stage (&topo
);
5001 /* Store results of bits propagation. */
5002 ipcp_store_bits_results ();
5003 /* Store results of value range propagation. */
5004 ipcp_store_vr_results ();
5006 /* Free all IPCP structures. */
5007 free_toporder_info (&topo
);
5008 next_edge_clone
.release ();
5009 prev_edge_clone
.release ();
5010 symtab
->remove_edge_removal_hook (edge_removal_hook_holder
);
5011 symtab
->remove_edge_duplication_hook (edge_duplication_hook_holder
);
5012 ipa_free_all_structures_after_ipa_cp ();
5014 fprintf (dump_file
, "\nIPA constant propagation end\n");
5018 /* Initialization and computation of IPCP data structures. This is the initial
5019 intraprocedural analysis of functions, which gathers information to be
5020 propagated later on. */
5023 ipcp_generate_summary (void)
5025 struct cgraph_node
*node
;
5028 fprintf (dump_file
, "\nIPA constant propagation start:\n");
5029 ipa_register_cgraph_hooks ();
5031 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5032 ipa_analyze_node (node
);
5035 /* Write ipcp summary for nodes in SET. */
5038 ipcp_write_summary (void)
5040 ipa_prop_write_jump_functions ();
5043 /* Read ipcp summary. */
5046 ipcp_read_summary (void)
5048 ipa_prop_read_jump_functions ();
5053 const pass_data pass_data_ipa_cp
=
5055 IPA_PASS
, /* type */
5057 OPTGROUP_NONE
, /* optinfo_flags */
5058 TV_IPA_CONSTANT_PROP
, /* tv_id */
5059 0, /* properties_required */
5060 0, /* properties_provided */
5061 0, /* properties_destroyed */
5062 0, /* todo_flags_start */
5063 ( TODO_dump_symtab
| TODO_remove_functions
), /* todo_flags_finish */
5066 class pass_ipa_cp
: public ipa_opt_pass_d
5069 pass_ipa_cp (gcc::context
*ctxt
)
5070 : ipa_opt_pass_d (pass_data_ipa_cp
, ctxt
,
5071 ipcp_generate_summary
, /* generate_summary */
5072 ipcp_write_summary
, /* write_summary */
5073 ipcp_read_summary
, /* read_summary */
5074 ipcp_write_transformation_summaries
, /*
5075 write_optimization_summary */
5076 ipcp_read_transformation_summaries
, /*
5077 read_optimization_summary */
5078 NULL
, /* stmt_fixup */
5079 0, /* function_transform_todo_flags_start */
5080 ipcp_transform_function
, /* function_transform */
5081 NULL
) /* variable_transform */
5084 /* opt_pass methods: */
5085 virtual bool gate (function
*)
5087 /* FIXME: We should remove the optimize check after we ensure we never run
5088 IPA passes when not optimizing. */
5089 return (flag_ipa_cp
&& optimize
) || in_lto_p
;
5092 virtual unsigned int execute (function
*) { return ipcp_driver (); }
5094 }; // class pass_ipa_cp
5099 make_pass_ipa_cp (gcc::context
*ctxt
)
5101 return new pass_ipa_cp (ctxt
);
5104 /* Reset all state within ipa-cp.c so that we can rerun the compiler
5105 within the same process. For use by toplev::finalize. */
5108 ipa_cp_c_finalize (void)