PR target/47230
[official-gcc.git] / gcc / ipa-cp.c
blob8d3d6ed1c4b87f4d808db56a38887d0017287d1c
1 /* Interprocedural constant propagation
2 Copyright (C) 2005-2014 Free Software Foundation, Inc.
4 Contributed by Razya Ladelsky <RAZYA@il.ibm.com> and Martin Jambor
5 <mjambor@suse.cz>
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
12 version.
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
17 for more details.
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
34 is deemed good.
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
46 calls are redirected.
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
61 values:
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
94 third stage.
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
101 the second stage. */
103 #include "config.h"
104 #include "system.h"
105 #include "coretypes.h"
106 #include "tree.h"
107 #include "gimple-fold.h"
108 #include "gimple-expr.h"
109 #include "target.h"
110 #include "ipa-prop.h"
111 #include "bitmap.h"
112 #include "tree-pass.h"
113 #include "flags.h"
114 #include "diagnostic.h"
115 #include "tree-pretty-print.h"
116 #include "tree-inline.h"
117 #include "params.h"
118 #include "ipa-inline.h"
119 #include "ipa-utils.h"
121 struct ipcp_value;
123 /* Describes a particular source for an IPA-CP value. */
125 struct ipcp_value_source
127 /* Aggregate offset of the source, negative if the source is scalar value of
128 the argument itself. */
129 HOST_WIDE_INT offset;
130 /* The incoming edge that brought the value. */
131 struct cgraph_edge *cs;
132 /* If the jump function that resulted into his value was a pass-through or an
133 ancestor, this is the ipcp_value of the caller from which the described
134 value has been derived. Otherwise it is NULL. */
135 struct ipcp_value *val;
136 /* Next pointer in a linked list of sources of a value. */
137 struct ipcp_value_source *next;
138 /* If the jump function that resulted into his value was a pass-through or an
139 ancestor, this is the index of the parameter of the caller the jump
140 function references. */
141 int index;
144 /* Describes one particular value stored in struct ipcp_lattice. */
146 struct ipcp_value
148 /* The actual value for the given parameter. This is either an IPA invariant
149 or a TREE_BINFO describing a type that can be used for
150 devirtualization. */
151 tree value;
152 /* The list of sources from which this value originates. */
153 struct ipcp_value_source *sources;
154 /* Next pointers in a linked list of all values in a lattice. */
155 struct ipcp_value *next;
156 /* Next pointers in a linked list of values in a strongly connected component
157 of values. */
158 struct ipcp_value *scc_next;
159 /* Next pointers in a linked list of SCCs of values sorted topologically
160 according their sources. */
161 struct ipcp_value *topo_next;
162 /* A specialized node created for this value, NULL if none has been (so far)
163 created. */
164 struct cgraph_node *spec_node;
165 /* Depth first search number and low link for topological sorting of
166 values. */
167 int dfs, low_link;
168 /* Time benefit and size cost that specializing the function for this value
169 would bring about in this function alone. */
170 int local_time_benefit, local_size_cost;
171 /* Time benefit and size cost that specializing the function for this value
172 can bring about in it's callees (transitively). */
173 int prop_time_benefit, prop_size_cost;
174 /* True if this valye is currently on the topo-sort stack. */
175 bool on_stack;
178 /* Lattice describing potential values of a formal parameter of a function, or
179 a part of an aggreagate. TOP is represented by a lattice with zero values
180 and with contains_variable and bottom flags cleared. BOTTOM is represented
181 by a lattice with the bottom flag set. In that case, values and
182 contains_variable flag should be disregarded. */
184 struct ipcp_lattice
186 /* The list of known values and types in this lattice. Note that values are
187 not deallocated if a lattice is set to bottom because there may be value
188 sources referencing them. */
189 struct ipcp_value *values;
190 /* Number of known values and types in this lattice. */
191 int values_count;
192 /* The lattice contains a variable component (in addition to values). */
193 bool contains_variable;
194 /* The value of the lattice is bottom (i.e. variable and unusable for any
195 propagation). */
196 bool bottom;
199 /* Lattice with an offset to describe a part of an aggregate. */
201 struct ipcp_agg_lattice : public ipcp_lattice
203 /* Offset that is being described by this lattice. */
204 HOST_WIDE_INT offset;
205 /* Size so that we don't have to re-compute it every time we traverse the
206 list. Must correspond to TYPE_SIZE of all lat values. */
207 HOST_WIDE_INT size;
208 /* Next element of the linked list. */
209 struct ipcp_agg_lattice *next;
212 /* Structure containing lattices for a parameter itself and for pieces of
213 aggregates that are passed in the parameter or by a reference in a parameter
214 plus some other useful flags. */
216 struct ipcp_param_lattices
218 /* Lattice describing the value of the parameter itself. */
219 struct ipcp_lattice itself;
220 /* Lattices describing aggregate parts. */
221 struct ipcp_agg_lattice *aggs;
222 /* Number of aggregate lattices */
223 int aggs_count;
224 /* True if aggregate data were passed by reference (as opposed to by
225 value). */
226 bool aggs_by_ref;
227 /* All aggregate lattices contain a variable component (in addition to
228 values). */
229 bool aggs_contain_variable;
230 /* The value of all aggregate lattices is bottom (i.e. variable and unusable
231 for any propagation). */
232 bool aggs_bottom;
234 /* There is a virtual call based on this parameter. */
235 bool virt_call;
238 /* Allocation pools for values and their sources in ipa-cp. */
240 alloc_pool ipcp_values_pool;
241 alloc_pool ipcp_sources_pool;
242 alloc_pool ipcp_agg_lattice_pool;
244 /* Maximal count found in program. */
246 static gcov_type max_count;
248 /* Original overall size of the program. */
250 static long overall_size, max_new_size;
252 /* Head of the linked list of topologically sorted values. */
254 static struct ipcp_value *values_topo;
256 /* Return the param lattices structure corresponding to the Ith formal
257 parameter of the function described by INFO. */
258 static inline struct ipcp_param_lattices *
259 ipa_get_parm_lattices (struct ipa_node_params *info, int i)
261 gcc_assert (i >= 0 && i < ipa_get_param_count (info));
262 gcc_checking_assert (!info->ipcp_orig_node);
263 gcc_checking_assert (info->lattices);
264 return &(info->lattices[i]);
267 /* Return the lattice corresponding to the scalar value of the Ith formal
268 parameter of the function described by INFO. */
269 static inline struct ipcp_lattice *
270 ipa_get_scalar_lat (struct ipa_node_params *info, int i)
272 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
273 return &plats->itself;
276 /* Return whether LAT is a lattice with a single constant and without an
277 undefined value. */
279 static inline bool
280 ipa_lat_is_single_const (struct ipcp_lattice *lat)
282 if (lat->bottom
283 || lat->contains_variable
284 || lat->values_count != 1)
285 return false;
286 else
287 return true;
290 /* Print V which is extracted from a value in a lattice to F. */
292 static void
293 print_ipcp_constant_value (FILE * f, tree v)
295 if (TREE_CODE (v) == TREE_BINFO)
297 fprintf (f, "BINFO ");
298 print_generic_expr (f, BINFO_TYPE (v), 0);
300 else if (TREE_CODE (v) == ADDR_EXPR
301 && TREE_CODE (TREE_OPERAND (v, 0)) == CONST_DECL)
303 fprintf (f, "& ");
304 print_generic_expr (f, DECL_INITIAL (TREE_OPERAND (v, 0)), 0);
306 else
307 print_generic_expr (f, v, 0);
310 /* Print a lattice LAT to F. */
312 static void
313 print_lattice (FILE * f, struct ipcp_lattice *lat,
314 bool dump_sources, bool dump_benefits)
316 struct ipcp_value *val;
317 bool prev = false;
319 if (lat->bottom)
321 fprintf (f, "BOTTOM\n");
322 return;
325 if (!lat->values_count && !lat->contains_variable)
327 fprintf (f, "TOP\n");
328 return;
331 if (lat->contains_variable)
333 fprintf (f, "VARIABLE");
334 prev = true;
335 if (dump_benefits)
336 fprintf (f, "\n");
339 for (val = lat->values; val; val = val->next)
341 if (dump_benefits && prev)
342 fprintf (f, " ");
343 else if (!dump_benefits && prev)
344 fprintf (f, ", ");
345 else
346 prev = true;
348 print_ipcp_constant_value (f, val->value);
350 if (dump_sources)
352 struct ipcp_value_source *s;
354 fprintf (f, " [from:");
355 for (s = val->sources; s; s = s->next)
356 fprintf (f, " %i(%i)", s->cs->caller->order,
357 s->cs->frequency);
358 fprintf (f, "]");
361 if (dump_benefits)
362 fprintf (f, " [loc_time: %i, loc_size: %i, "
363 "prop_time: %i, prop_size: %i]\n",
364 val->local_time_benefit, val->local_size_cost,
365 val->prop_time_benefit, val->prop_size_cost);
367 if (!dump_benefits)
368 fprintf (f, "\n");
371 /* Print all ipcp_lattices of all functions to F. */
373 static void
374 print_all_lattices (FILE * f, bool dump_sources, bool dump_benefits)
376 struct cgraph_node *node;
377 int i, count;
379 fprintf (f, "\nLattices:\n");
380 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
382 struct ipa_node_params *info;
384 info = IPA_NODE_REF (node);
385 fprintf (f, " Node: %s/%i:\n", node->name (),
386 node->order);
387 count = ipa_get_param_count (info);
388 for (i = 0; i < count; i++)
390 struct ipcp_agg_lattice *aglat;
391 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
392 fprintf (f, " param [%d]: ", i);
393 print_lattice (f, &plats->itself, dump_sources, dump_benefits);
395 if (plats->virt_call)
396 fprintf (f, " virt_call flag set\n");
398 if (plats->aggs_bottom)
400 fprintf (f, " AGGS BOTTOM\n");
401 continue;
403 if (plats->aggs_contain_variable)
404 fprintf (f, " AGGS VARIABLE\n");
405 for (aglat = plats->aggs; aglat; aglat = aglat->next)
407 fprintf (f, " %soffset " HOST_WIDE_INT_PRINT_DEC ": ",
408 plats->aggs_by_ref ? "ref " : "", aglat->offset);
409 print_lattice (f, aglat, dump_sources, dump_benefits);
415 /* Determine whether it is at all technically possible to create clones of NODE
416 and store this information in the ipa_node_params structure associated
417 with NODE. */
419 static void
420 determine_versionability (struct cgraph_node *node)
422 const char *reason = NULL;
424 /* There are a number of generic reasons functions cannot be versioned. We
425 also cannot remove parameters if there are type attributes such as fnspec
426 present. */
427 if (node->alias || node->thunk.thunk_p)
428 reason = "alias or thunk";
429 else if (!node->local.versionable)
430 reason = "not a tree_versionable_function";
431 else if (node->get_availability () <= AVAIL_INTERPOSABLE)
432 reason = "insufficient body availability";
433 else if (!opt_for_fn (node->decl, optimize)
434 || !opt_for_fn (node->decl, flag_ipa_cp))
435 reason = "non-optimized function";
436 else if (lookup_attribute ("omp declare simd", DECL_ATTRIBUTES (node->decl)))
438 /* Ideally we should clone the SIMD clones themselves and create
439 vector copies of them, so IPA-cp and SIMD clones can happily
440 coexist, but that may not be worth the effort. */
441 reason = "function has SIMD clones";
443 /* Don't clone decls local to a comdat group; it breaks and for C++
444 decloned constructors, inlining is always better anyway. */
445 else if (node->comdat_local_p ())
446 reason = "comdat-local function";
448 if (reason && dump_file && !node->alias && !node->thunk.thunk_p)
449 fprintf (dump_file, "Function %s/%i is not versionable, reason: %s.\n",
450 node->name (), node->order, reason);
452 node->local.versionable = (reason == NULL);
455 /* Return true if it is at all technically possible to create clones of a
456 NODE. */
458 static bool
459 ipcp_versionable_function_p (struct cgraph_node *node)
461 return node->local.versionable;
464 /* Structure holding accumulated information about callers of a node. */
466 struct caller_statistics
468 gcov_type count_sum;
469 int n_calls, n_hot_calls, freq_sum;
472 /* Initialize fields of STAT to zeroes. */
474 static inline void
475 init_caller_stats (struct caller_statistics *stats)
477 stats->count_sum = 0;
478 stats->n_calls = 0;
479 stats->n_hot_calls = 0;
480 stats->freq_sum = 0;
483 /* Worker callback of cgraph_for_node_and_aliases accumulating statistics of
484 non-thunk incoming edges to NODE. */
486 static bool
487 gather_caller_stats (struct cgraph_node *node, void *data)
489 struct caller_statistics *stats = (struct caller_statistics *) data;
490 struct cgraph_edge *cs;
492 for (cs = node->callers; cs; cs = cs->next_caller)
493 if (cs->caller->thunk.thunk_p)
494 cs->caller->call_for_symbol_thunks_and_aliases (gather_caller_stats,
495 stats, false);
496 else
498 stats->count_sum += cs->count;
499 stats->freq_sum += cs->frequency;
500 stats->n_calls++;
501 if (cgraph_maybe_hot_edge_p (cs))
502 stats->n_hot_calls ++;
504 return false;
508 /* Return true if this NODE is viable candidate for cloning. */
510 static bool
511 ipcp_cloning_candidate_p (struct cgraph_node *node)
513 struct caller_statistics stats;
515 gcc_checking_assert (node->has_gimple_body_p ());
517 if (!flag_ipa_cp_clone)
519 if (dump_file)
520 fprintf (dump_file, "Not considering %s for cloning; "
521 "-fipa-cp-clone disabled.\n",
522 node->name ());
523 return false;
526 if (!optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node->decl)))
528 if (dump_file)
529 fprintf (dump_file, "Not considering %s for cloning; "
530 "optimizing it for size.\n",
531 node->name ());
532 return false;
535 init_caller_stats (&stats);
536 node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats, false);
538 if (inline_summary (node)->self_size < stats.n_calls)
540 if (dump_file)
541 fprintf (dump_file, "Considering %s for cloning; code might shrink.\n",
542 node->name ());
543 return true;
546 /* When profile is available and function is hot, propagate into it even if
547 calls seems cold; constant propagation can improve function's speed
548 significantly. */
549 if (max_count)
551 if (stats.count_sum > node->count * 90 / 100)
553 if (dump_file)
554 fprintf (dump_file, "Considering %s for cloning; "
555 "usually called directly.\n",
556 node->name ());
557 return true;
560 if (!stats.n_hot_calls)
562 if (dump_file)
563 fprintf (dump_file, "Not considering %s for cloning; no hot calls.\n",
564 node->name ());
565 return false;
567 if (dump_file)
568 fprintf (dump_file, "Considering %s for cloning.\n",
569 node->name ());
570 return true;
573 /* Arrays representing a topological ordering of call graph nodes and a stack
574 of noes used during constant propagation. */
576 struct topo_info
578 struct cgraph_node **order;
579 struct cgraph_node **stack;
580 int nnodes, stack_top;
583 /* Allocate the arrays in TOPO and topologically sort the nodes into order. */
585 static void
586 build_toporder_info (struct topo_info *topo)
588 topo->order = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
589 topo->stack = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
590 topo->stack_top = 0;
591 topo->nnodes = ipa_reduced_postorder (topo->order, true, true, NULL);
594 /* Free information about strongly connected components and the arrays in
595 TOPO. */
597 static void
598 free_toporder_info (struct topo_info *topo)
600 ipa_free_postorder_info ();
601 free (topo->order);
602 free (topo->stack);
605 /* Add NODE to the stack in TOPO, unless it is already there. */
607 static inline void
608 push_node_to_stack (struct topo_info *topo, struct cgraph_node *node)
610 struct ipa_node_params *info = IPA_NODE_REF (node);
611 if (info->node_enqueued)
612 return;
613 info->node_enqueued = 1;
614 topo->stack[topo->stack_top++] = node;
617 /* Pop a node from the stack in TOPO and return it or return NULL if the stack
618 is empty. */
620 static struct cgraph_node *
621 pop_node_from_stack (struct topo_info *topo)
623 if (topo->stack_top)
625 struct cgraph_node *node;
626 topo->stack_top--;
627 node = topo->stack[topo->stack_top];
628 IPA_NODE_REF (node)->node_enqueued = 0;
629 return node;
631 else
632 return NULL;
635 /* Set lattice LAT to bottom and return true if it previously was not set as
636 such. */
638 static inline bool
639 set_lattice_to_bottom (struct ipcp_lattice *lat)
641 bool ret = !lat->bottom;
642 lat->bottom = true;
643 return ret;
646 /* Mark lattice as containing an unknown value and return true if it previously
647 was not marked as such. */
649 static inline bool
650 set_lattice_contains_variable (struct ipcp_lattice *lat)
652 bool ret = !lat->contains_variable;
653 lat->contains_variable = true;
654 return ret;
657 /* Set all aggegate lattices in PLATS to bottom and return true if they were
658 not previously set as such. */
660 static inline bool
661 set_agg_lats_to_bottom (struct ipcp_param_lattices *plats)
663 bool ret = !plats->aggs_bottom;
664 plats->aggs_bottom = true;
665 return ret;
668 /* Mark all aggegate lattices in PLATS as containing an unknown value and
669 return true if they were not previously marked as such. */
671 static inline bool
672 set_agg_lats_contain_variable (struct ipcp_param_lattices *plats)
674 bool ret = !plats->aggs_contain_variable;
675 plats->aggs_contain_variable = true;
676 return ret;
679 /* Mark bot aggregate and scalar lattices as containing an unknown variable,
680 return true is any of them has not been marked as such so far. */
682 static inline bool
683 set_all_contains_variable (struct ipcp_param_lattices *plats)
685 bool ret = !plats->itself.contains_variable || !plats->aggs_contain_variable;
686 plats->itself.contains_variable = true;
687 plats->aggs_contain_variable = true;
688 return ret;
691 /* Initialize ipcp_lattices. */
693 static void
694 initialize_node_lattices (struct cgraph_node *node)
696 struct ipa_node_params *info = IPA_NODE_REF (node);
697 struct cgraph_edge *ie;
698 bool disable = false, variable = false;
699 int i;
701 gcc_checking_assert (node->has_gimple_body_p ());
702 if (!node->local.local)
704 /* When cloning is allowed, we can assume that externally visible
705 functions are not called. We will compensate this by cloning
706 later. */
707 if (ipcp_versionable_function_p (node)
708 && ipcp_cloning_candidate_p (node))
709 variable = true;
710 else
711 disable = true;
714 if (disable || variable)
716 for (i = 0; i < ipa_get_param_count (info) ; i++)
718 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
719 if (disable)
721 set_lattice_to_bottom (&plats->itself);
722 set_agg_lats_to_bottom (plats);
724 else
725 set_all_contains_variable (plats);
727 if (dump_file && (dump_flags & TDF_DETAILS)
728 && !node->alias && !node->thunk.thunk_p)
729 fprintf (dump_file, "Marking all lattices of %s/%i as %s\n",
730 node->name (), node->order,
731 disable ? "BOTTOM" : "VARIABLE");
734 for (ie = node->indirect_calls; ie; ie = ie->next_callee)
735 if (ie->indirect_info->polymorphic
736 && ie->indirect_info->param_index >= 0)
738 gcc_checking_assert (ie->indirect_info->param_index >= 0);
739 ipa_get_parm_lattices (info,
740 ie->indirect_info->param_index)->virt_call = 1;
744 /* Return the result of a (possibly arithmetic) pass through jump function
745 JFUNC on the constant value INPUT. Return NULL_TREE if that cannot be
746 determined or be considered an interprocedural invariant. */
748 static tree
749 ipa_get_jf_pass_through_result (struct ipa_jump_func *jfunc, tree input)
751 tree restype, res;
753 if (TREE_CODE (input) == TREE_BINFO)
755 if (ipa_get_jf_pass_through_type_preserved (jfunc))
757 gcc_checking_assert (ipa_get_jf_pass_through_operation (jfunc)
758 == NOP_EXPR);
759 return input;
761 return NULL_TREE;
764 if (ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
765 return input;
767 gcc_checking_assert (is_gimple_ip_invariant (input));
768 if (TREE_CODE_CLASS (ipa_get_jf_pass_through_operation (jfunc))
769 == tcc_comparison)
770 restype = boolean_type_node;
771 else
772 restype = TREE_TYPE (input);
773 res = fold_binary (ipa_get_jf_pass_through_operation (jfunc), restype,
774 input, ipa_get_jf_pass_through_operand (jfunc));
776 if (res && !is_gimple_ip_invariant (res))
777 return NULL_TREE;
779 return res;
782 /* Return the result of an ancestor jump function JFUNC on the constant value
783 INPUT. Return NULL_TREE if that cannot be determined. */
785 static tree
786 ipa_get_jf_ancestor_result (struct ipa_jump_func *jfunc, tree input)
788 if (TREE_CODE (input) == TREE_BINFO)
790 if (!ipa_get_jf_ancestor_type_preserved (jfunc))
791 return NULL;
792 /* FIXME: At LTO we can't propagate to non-polymorphic type, because
793 we have no ODR equivalency on those. This should be fixed by
794 propagating on types rather than binfos that would make type
795 matching here unnecesary. */
796 if (in_lto_p
797 && (TREE_CODE (ipa_get_jf_ancestor_type (jfunc)) != RECORD_TYPE
798 || !TYPE_BINFO (ipa_get_jf_ancestor_type (jfunc))
799 || !BINFO_VTABLE (TYPE_BINFO (ipa_get_jf_ancestor_type (jfunc)))))
801 if (!ipa_get_jf_ancestor_offset (jfunc))
802 return input;
803 return NULL;
805 return get_binfo_at_offset (input,
806 ipa_get_jf_ancestor_offset (jfunc),
807 ipa_get_jf_ancestor_type (jfunc));
809 else if (TREE_CODE (input) == ADDR_EXPR)
811 tree t = TREE_OPERAND (input, 0);
812 t = build_ref_for_offset (EXPR_LOCATION (t), t,
813 ipa_get_jf_ancestor_offset (jfunc),
814 ipa_get_jf_ancestor_type (jfunc)
815 ? ipa_get_jf_ancestor_type (jfunc)
816 : ptr_type_node, NULL, false);
817 return build_fold_addr_expr (t);
819 else
820 return NULL_TREE;
823 /* Determine whether JFUNC evaluates to a known value (that is either a
824 constant or a binfo) and if so, return it. Otherwise return NULL. INFO
825 describes the caller node so that pass-through jump functions can be
826 evaluated. */
828 tree
829 ipa_value_from_jfunc (struct ipa_node_params *info, struct ipa_jump_func *jfunc)
831 if (jfunc->type == IPA_JF_CONST)
832 return ipa_get_jf_constant (jfunc);
833 else if (jfunc->type == IPA_JF_KNOWN_TYPE)
834 return ipa_binfo_from_known_type_jfunc (jfunc);
835 else if (jfunc->type == IPA_JF_PASS_THROUGH
836 || jfunc->type == IPA_JF_ANCESTOR)
838 tree input;
839 int idx;
841 if (jfunc->type == IPA_JF_PASS_THROUGH)
842 idx = ipa_get_jf_pass_through_formal_id (jfunc);
843 else
844 idx = ipa_get_jf_ancestor_formal_id (jfunc);
846 if (info->ipcp_orig_node)
847 input = info->known_vals[idx];
848 else
850 struct ipcp_lattice *lat;
852 if (!info->lattices)
854 gcc_checking_assert (!flag_ipa_cp);
855 return NULL_TREE;
857 lat = ipa_get_scalar_lat (info, idx);
858 if (!ipa_lat_is_single_const (lat))
859 return NULL_TREE;
860 input = lat->values->value;
863 if (!input)
864 return NULL_TREE;
866 if (jfunc->type == IPA_JF_PASS_THROUGH)
867 return ipa_get_jf_pass_through_result (jfunc, input);
868 else
869 return ipa_get_jf_ancestor_result (jfunc, input);
871 else
872 return NULL_TREE;
876 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
877 bottom, not containing a variable component and without any known value at
878 the same time. */
880 DEBUG_FUNCTION void
881 ipcp_verify_propagated_values (void)
883 struct cgraph_node *node;
885 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
887 struct ipa_node_params *info = IPA_NODE_REF (node);
888 int i, count = ipa_get_param_count (info);
890 for (i = 0; i < count; i++)
892 struct ipcp_lattice *lat = ipa_get_scalar_lat (info, i);
894 if (!lat->bottom
895 && !lat->contains_variable
896 && lat->values_count == 0)
898 if (dump_file)
900 symtab_node::dump_table (dump_file);
901 fprintf (dump_file, "\nIPA lattices after constant "
902 "propagation, before gcc_unreachable:\n");
903 print_all_lattices (dump_file, true, false);
906 gcc_unreachable ();
912 /* Return true iff X and Y should be considered equal values by IPA-CP. */
914 static bool
915 values_equal_for_ipcp_p (tree x, tree y)
917 gcc_checking_assert (x != NULL_TREE && y != NULL_TREE);
919 if (x == y)
920 return true;
922 if (TREE_CODE (x) == TREE_BINFO || TREE_CODE (y) == TREE_BINFO)
923 return false;
925 if (TREE_CODE (x) == ADDR_EXPR
926 && TREE_CODE (y) == ADDR_EXPR
927 && TREE_CODE (TREE_OPERAND (x, 0)) == CONST_DECL
928 && TREE_CODE (TREE_OPERAND (y, 0)) == CONST_DECL)
929 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x, 0)),
930 DECL_INITIAL (TREE_OPERAND (y, 0)), 0);
931 else
932 return operand_equal_p (x, y, 0);
935 /* Add a new value source to VAL, marking that a value comes from edge CS and
936 (if the underlying jump function is a pass-through or an ancestor one) from
937 a caller value SRC_VAL of a caller parameter described by SRC_INDEX. OFFSET
938 is negative if the source was the scalar value of the parameter itself or
939 the offset within an aggregate. */
941 static void
942 add_value_source (struct ipcp_value *val, struct cgraph_edge *cs,
943 struct ipcp_value *src_val, int src_idx, HOST_WIDE_INT offset)
945 struct ipcp_value_source *src;
947 src = (struct ipcp_value_source *) pool_alloc (ipcp_sources_pool);
948 src->offset = offset;
949 src->cs = cs;
950 src->val = src_val;
951 src->index = src_idx;
953 src->next = val->sources;
954 val->sources = src;
957 /* Try to add NEWVAL to LAT, potentially creating a new struct ipcp_value for
958 it. CS, SRC_VAL SRC_INDEX and OFFSET are meant for add_value_source and
959 have the same meaning. */
961 static bool
962 add_value_to_lattice (struct ipcp_lattice *lat, tree newval,
963 struct cgraph_edge *cs, struct ipcp_value *src_val,
964 int src_idx, HOST_WIDE_INT offset)
966 struct ipcp_value *val;
968 if (lat->bottom)
969 return false;
971 for (val = lat->values; val; val = val->next)
972 if (values_equal_for_ipcp_p (val->value, newval))
974 if (ipa_edge_within_scc (cs))
976 struct ipcp_value_source *s;
977 for (s = val->sources; s ; s = s->next)
978 if (s->cs == cs)
979 break;
980 if (s)
981 return false;
984 add_value_source (val, cs, src_val, src_idx, offset);
985 return false;
988 if (lat->values_count == PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE))
990 /* We can only free sources, not the values themselves, because sources
991 of other values in this this SCC might point to them. */
992 for (val = lat->values; val; val = val->next)
994 while (val->sources)
996 struct ipcp_value_source *src = val->sources;
997 val->sources = src->next;
998 pool_free (ipcp_sources_pool, src);
1002 lat->values = NULL;
1003 return set_lattice_to_bottom (lat);
1006 lat->values_count++;
1007 val = (struct ipcp_value *) pool_alloc (ipcp_values_pool);
1008 memset (val, 0, sizeof (*val));
1010 add_value_source (val, cs, src_val, src_idx, offset);
1011 val->value = newval;
1012 val->next = lat->values;
1013 lat->values = val;
1014 return true;
1017 /* Like above but passes a special value of offset to distinguish that the
1018 origin is the scalar value of the parameter rather than a part of an
1019 aggregate. */
1021 static inline bool
1022 add_scalar_value_to_lattice (struct ipcp_lattice *lat, tree newval,
1023 struct cgraph_edge *cs,
1024 struct ipcp_value *src_val, int src_idx)
1026 return add_value_to_lattice (lat, newval, cs, src_val, src_idx, -1);
1029 /* Propagate values through a pass-through jump function JFUNC associated with
1030 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1031 is the index of the source parameter. */
1033 static bool
1034 propagate_vals_accross_pass_through (struct cgraph_edge *cs,
1035 struct ipa_jump_func *jfunc,
1036 struct ipcp_lattice *src_lat,
1037 struct ipcp_lattice *dest_lat,
1038 int src_idx)
1040 struct ipcp_value *src_val;
1041 bool ret = false;
1043 /* Do not create new values when propagating within an SCC because if there
1044 are arithmetic functions with circular dependencies, there is infinite
1045 number of them and we would just make lattices bottom. */
1046 if ((ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR)
1047 && ipa_edge_within_scc (cs))
1048 ret = set_lattice_contains_variable (dest_lat);
1049 else
1050 for (src_val = src_lat->values; src_val; src_val = src_val->next)
1052 tree cstval = ipa_get_jf_pass_through_result (jfunc, src_val->value);
1054 if (cstval)
1055 ret |= add_scalar_value_to_lattice (dest_lat, cstval, cs, src_val,
1056 src_idx);
1057 else
1058 ret |= set_lattice_contains_variable (dest_lat);
1061 return ret;
1064 /* Propagate values through an ancestor jump function JFUNC associated with
1065 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1066 is the index of the source parameter. */
1068 static bool
1069 propagate_vals_accross_ancestor (struct cgraph_edge *cs,
1070 struct ipa_jump_func *jfunc,
1071 struct ipcp_lattice *src_lat,
1072 struct ipcp_lattice *dest_lat,
1073 int src_idx)
1075 struct ipcp_value *src_val;
1076 bool ret = false;
1078 if (ipa_edge_within_scc (cs))
1079 return set_lattice_contains_variable (dest_lat);
1081 for (src_val = src_lat->values; src_val; src_val = src_val->next)
1083 tree t = ipa_get_jf_ancestor_result (jfunc, src_val->value);
1085 if (t)
1086 ret |= add_scalar_value_to_lattice (dest_lat, t, cs, src_val, src_idx);
1087 else
1088 ret |= set_lattice_contains_variable (dest_lat);
1091 return ret;
1094 /* Propagate scalar values across jump function JFUNC that is associated with
1095 edge CS and put the values into DEST_LAT. */
1097 static bool
1098 propagate_scalar_accross_jump_function (struct cgraph_edge *cs,
1099 struct ipa_jump_func *jfunc,
1100 struct ipcp_lattice *dest_lat)
1102 if (dest_lat->bottom)
1103 return false;
1105 if (jfunc->type == IPA_JF_CONST
1106 || jfunc->type == IPA_JF_KNOWN_TYPE)
1108 tree val;
1110 if (jfunc->type == IPA_JF_KNOWN_TYPE)
1112 val = ipa_binfo_from_known_type_jfunc (jfunc);
1113 if (!val)
1114 return set_lattice_contains_variable (dest_lat);
1116 else
1117 val = ipa_get_jf_constant (jfunc);
1118 return add_scalar_value_to_lattice (dest_lat, val, cs, NULL, 0);
1120 else if (jfunc->type == IPA_JF_PASS_THROUGH
1121 || jfunc->type == IPA_JF_ANCESTOR)
1123 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1124 struct ipcp_lattice *src_lat;
1125 int src_idx;
1126 bool ret;
1128 if (jfunc->type == IPA_JF_PASS_THROUGH)
1129 src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
1130 else
1131 src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
1133 src_lat = ipa_get_scalar_lat (caller_info, src_idx);
1134 if (src_lat->bottom)
1135 return set_lattice_contains_variable (dest_lat);
1137 /* If we would need to clone the caller and cannot, do not propagate. */
1138 if (!ipcp_versionable_function_p (cs->caller)
1139 && (src_lat->contains_variable
1140 || (src_lat->values_count > 1)))
1141 return set_lattice_contains_variable (dest_lat);
1143 if (jfunc->type == IPA_JF_PASS_THROUGH)
1144 ret = propagate_vals_accross_pass_through (cs, jfunc, src_lat,
1145 dest_lat, src_idx);
1146 else
1147 ret = propagate_vals_accross_ancestor (cs, jfunc, src_lat, dest_lat,
1148 src_idx);
1150 if (src_lat->contains_variable)
1151 ret |= set_lattice_contains_variable (dest_lat);
1153 return ret;
1156 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1157 use it for indirect inlining), we should propagate them too. */
1158 return set_lattice_contains_variable (dest_lat);
1161 /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
1162 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
1163 other cases, return false). If there are no aggregate items, set
1164 aggs_by_ref to NEW_AGGS_BY_REF. */
1166 static bool
1167 set_check_aggs_by_ref (struct ipcp_param_lattices *dest_plats,
1168 bool new_aggs_by_ref)
1170 if (dest_plats->aggs)
1172 if (dest_plats->aggs_by_ref != new_aggs_by_ref)
1174 set_agg_lats_to_bottom (dest_plats);
1175 return true;
1178 else
1179 dest_plats->aggs_by_ref = new_aggs_by_ref;
1180 return false;
1183 /* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
1184 already existing lattice for the given OFFSET and SIZE, marking all skipped
1185 lattices as containing variable and checking for overlaps. If there is no
1186 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
1187 it with offset, size and contains_variable to PRE_EXISTING, and return true,
1188 unless there are too many already. If there are two many, return false. If
1189 there are overlaps turn whole DEST_PLATS to bottom and return false. If any
1190 skipped lattices were newly marked as containing variable, set *CHANGE to
1191 true. */
1193 static bool
1194 merge_agg_lats_step (struct ipcp_param_lattices *dest_plats,
1195 HOST_WIDE_INT offset, HOST_WIDE_INT val_size,
1196 struct ipcp_agg_lattice ***aglat,
1197 bool pre_existing, bool *change)
1199 gcc_checking_assert (offset >= 0);
1201 while (**aglat && (**aglat)->offset < offset)
1203 if ((**aglat)->offset + (**aglat)->size > offset)
1205 set_agg_lats_to_bottom (dest_plats);
1206 return false;
1208 *change |= set_lattice_contains_variable (**aglat);
1209 *aglat = &(**aglat)->next;
1212 if (**aglat && (**aglat)->offset == offset)
1214 if ((**aglat)->size != val_size
1215 || ((**aglat)->next
1216 && (**aglat)->next->offset < offset + val_size))
1218 set_agg_lats_to_bottom (dest_plats);
1219 return false;
1221 gcc_checking_assert (!(**aglat)->next
1222 || (**aglat)->next->offset >= offset + val_size);
1223 return true;
1225 else
1227 struct ipcp_agg_lattice *new_al;
1229 if (**aglat && (**aglat)->offset < offset + val_size)
1231 set_agg_lats_to_bottom (dest_plats);
1232 return false;
1234 if (dest_plats->aggs_count == PARAM_VALUE (PARAM_IPA_MAX_AGG_ITEMS))
1235 return false;
1236 dest_plats->aggs_count++;
1237 new_al = (struct ipcp_agg_lattice *) pool_alloc (ipcp_agg_lattice_pool);
1238 memset (new_al, 0, sizeof (*new_al));
1240 new_al->offset = offset;
1241 new_al->size = val_size;
1242 new_al->contains_variable = pre_existing;
1244 new_al->next = **aglat;
1245 **aglat = new_al;
1246 return true;
1250 /* Set all AGLAT and all other aggregate lattices reachable by next pointers as
1251 containing an unknown value. */
1253 static bool
1254 set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice *aglat)
1256 bool ret = false;
1257 while (aglat)
1259 ret |= set_lattice_contains_variable (aglat);
1260 aglat = aglat->next;
1262 return ret;
1265 /* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
1266 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source
1267 parameter used for lattice value sources. Return true if DEST_PLATS changed
1268 in any way. */
1270 static bool
1271 merge_aggregate_lattices (struct cgraph_edge *cs,
1272 struct ipcp_param_lattices *dest_plats,
1273 struct ipcp_param_lattices *src_plats,
1274 int src_idx, HOST_WIDE_INT offset_delta)
1276 bool pre_existing = dest_plats->aggs != NULL;
1277 struct ipcp_agg_lattice **dst_aglat;
1278 bool ret = false;
1280 if (set_check_aggs_by_ref (dest_plats, src_plats->aggs_by_ref))
1281 return true;
1282 if (src_plats->aggs_bottom)
1283 return set_agg_lats_contain_variable (dest_plats);
1284 if (src_plats->aggs_contain_variable)
1285 ret |= set_agg_lats_contain_variable (dest_plats);
1286 dst_aglat = &dest_plats->aggs;
1288 for (struct ipcp_agg_lattice *src_aglat = src_plats->aggs;
1289 src_aglat;
1290 src_aglat = src_aglat->next)
1292 HOST_WIDE_INT new_offset = src_aglat->offset - offset_delta;
1294 if (new_offset < 0)
1295 continue;
1296 if (merge_agg_lats_step (dest_plats, new_offset, src_aglat->size,
1297 &dst_aglat, pre_existing, &ret))
1299 struct ipcp_agg_lattice *new_al = *dst_aglat;
1301 dst_aglat = &(*dst_aglat)->next;
1302 if (src_aglat->bottom)
1304 ret |= set_lattice_contains_variable (new_al);
1305 continue;
1307 if (src_aglat->contains_variable)
1308 ret |= set_lattice_contains_variable (new_al);
1309 for (struct ipcp_value *val = src_aglat->values;
1310 val;
1311 val = val->next)
1312 ret |= add_value_to_lattice (new_al, val->value, cs, val, src_idx,
1313 src_aglat->offset);
1315 else if (dest_plats->aggs_bottom)
1316 return true;
1318 ret |= set_chain_of_aglats_contains_variable (*dst_aglat);
1319 return ret;
1322 /* Determine whether there is anything to propagate FROM SRC_PLATS through a
1323 pass-through JFUNC and if so, whether it has conform and conforms to the
1324 rules about propagating values passed by reference. */
1326 static bool
1327 agg_pass_through_permissible_p (struct ipcp_param_lattices *src_plats,
1328 struct ipa_jump_func *jfunc)
1330 return src_plats->aggs
1331 && (!src_plats->aggs_by_ref
1332 || ipa_get_jf_pass_through_agg_preserved (jfunc));
1335 /* Propagate scalar values across jump function JFUNC that is associated with
1336 edge CS and put the values into DEST_LAT. */
1338 static bool
1339 propagate_aggs_accross_jump_function (struct cgraph_edge *cs,
1340 struct ipa_jump_func *jfunc,
1341 struct ipcp_param_lattices *dest_plats)
1343 bool ret = false;
1345 if (dest_plats->aggs_bottom)
1346 return false;
1348 if (jfunc->type == IPA_JF_PASS_THROUGH
1349 && ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
1351 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1352 int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
1353 struct ipcp_param_lattices *src_plats;
1355 src_plats = ipa_get_parm_lattices (caller_info, src_idx);
1356 if (agg_pass_through_permissible_p (src_plats, jfunc))
1358 /* Currently we do not produce clobber aggregate jump
1359 functions, replace with merging when we do. */
1360 gcc_assert (!jfunc->agg.items);
1361 ret |= merge_aggregate_lattices (cs, dest_plats, src_plats,
1362 src_idx, 0);
1364 else
1365 ret |= set_agg_lats_contain_variable (dest_plats);
1367 else if (jfunc->type == IPA_JF_ANCESTOR
1368 && ipa_get_jf_ancestor_agg_preserved (jfunc))
1370 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1371 int src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
1372 struct ipcp_param_lattices *src_plats;
1374 src_plats = ipa_get_parm_lattices (caller_info, src_idx);
1375 if (src_plats->aggs && src_plats->aggs_by_ref)
1377 /* Currently we do not produce clobber aggregate jump
1378 functions, replace with merging when we do. */
1379 gcc_assert (!jfunc->agg.items);
1380 ret |= merge_aggregate_lattices (cs, dest_plats, src_plats, src_idx,
1381 ipa_get_jf_ancestor_offset (jfunc));
1383 else if (!src_plats->aggs_by_ref)
1384 ret |= set_agg_lats_to_bottom (dest_plats);
1385 else
1386 ret |= set_agg_lats_contain_variable (dest_plats);
1388 else if (jfunc->agg.items)
1390 bool pre_existing = dest_plats->aggs != NULL;
1391 struct ipcp_agg_lattice **aglat = &dest_plats->aggs;
1392 struct ipa_agg_jf_item *item;
1393 int i;
1395 if (set_check_aggs_by_ref (dest_plats, jfunc->agg.by_ref))
1396 return true;
1398 FOR_EACH_VEC_ELT (*jfunc->agg.items, i, item)
1400 HOST_WIDE_INT val_size;
1402 if (item->offset < 0)
1403 continue;
1404 gcc_checking_assert (is_gimple_ip_invariant (item->value));
1405 val_size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (item->value)));
1407 if (merge_agg_lats_step (dest_plats, item->offset, val_size,
1408 &aglat, pre_existing, &ret))
1410 ret |= add_value_to_lattice (*aglat, item->value, cs, NULL, 0, 0);
1411 aglat = &(*aglat)->next;
1413 else if (dest_plats->aggs_bottom)
1414 return true;
1417 ret |= set_chain_of_aglats_contains_variable (*aglat);
1419 else
1420 ret |= set_agg_lats_contain_variable (dest_plats);
1422 return ret;
1425 /* Propagate constants from the caller to the callee of CS. INFO describes the
1426 caller. */
1428 static bool
1429 propagate_constants_accross_call (struct cgraph_edge *cs)
1431 struct ipa_node_params *callee_info;
1432 enum availability availability;
1433 struct cgraph_node *callee, *alias_or_thunk;
1434 struct ipa_edge_args *args;
1435 bool ret = false;
1436 int i, args_count, parms_count;
1438 callee = cs->callee->function_symbol (&availability);
1439 if (!callee->definition)
1440 return false;
1441 gcc_checking_assert (callee->has_gimple_body_p ());
1442 callee_info = IPA_NODE_REF (callee);
1444 args = IPA_EDGE_REF (cs);
1445 args_count = ipa_get_cs_argument_count (args);
1446 parms_count = ipa_get_param_count (callee_info);
1447 if (parms_count == 0)
1448 return false;
1450 /* If this call goes through a thunk we must not propagate to the first (0th)
1451 parameter. However, we might need to uncover a thunk from below a series
1452 of aliases first. */
1453 alias_or_thunk = cs->callee;
1454 while (alias_or_thunk->alias)
1455 alias_or_thunk = alias_or_thunk->get_alias_target ();
1456 if (alias_or_thunk->thunk.thunk_p)
1458 ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info,
1459 0));
1460 i = 1;
1462 else
1463 i = 0;
1465 for (; (i < args_count) && (i < parms_count); i++)
1467 struct ipa_jump_func *jump_func = ipa_get_ith_jump_func (args, i);
1468 struct ipcp_param_lattices *dest_plats;
1470 dest_plats = ipa_get_parm_lattices (callee_info, i);
1471 if (availability == AVAIL_INTERPOSABLE)
1472 ret |= set_all_contains_variable (dest_plats);
1473 else
1475 ret |= propagate_scalar_accross_jump_function (cs, jump_func,
1476 &dest_plats->itself);
1477 ret |= propagate_aggs_accross_jump_function (cs, jump_func,
1478 dest_plats);
1481 for (; i < parms_count; i++)
1482 ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info, i));
1484 return ret;
1487 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
1488 (which can contain both constants and binfos), KNOWN_BINFOS, KNOWN_AGGS or
1489 AGG_REPS return the destination. The latter three can be NULL. If AGG_REPS
1490 is not NULL, KNOWN_AGGS is ignored. */
1492 static tree
1493 ipa_get_indirect_edge_target_1 (struct cgraph_edge *ie,
1494 vec<tree> known_vals,
1495 vec<tree> known_binfos,
1496 vec<ipa_agg_jump_function_p> known_aggs,
1497 struct ipa_agg_replacement_value *agg_reps)
1499 int param_index = ie->indirect_info->param_index;
1500 HOST_WIDE_INT token, anc_offset;
1501 tree otr_type;
1502 tree t;
1503 tree target = NULL;
1505 if (param_index == -1
1506 || known_vals.length () <= (unsigned int) param_index)
1507 return NULL_TREE;
1509 if (!ie->indirect_info->polymorphic)
1511 tree t;
1513 if (ie->indirect_info->agg_contents)
1515 if (agg_reps)
1517 t = NULL;
1518 while (agg_reps)
1520 if (agg_reps->index == param_index
1521 && agg_reps->offset == ie->indirect_info->offset
1522 && agg_reps->by_ref == ie->indirect_info->by_ref)
1524 t = agg_reps->value;
1525 break;
1527 agg_reps = agg_reps->next;
1530 else if (known_aggs.length () > (unsigned int) param_index)
1532 struct ipa_agg_jump_function *agg;
1533 agg = known_aggs[param_index];
1534 t = ipa_find_agg_cst_for_param (agg, ie->indirect_info->offset,
1535 ie->indirect_info->by_ref);
1537 else
1538 t = NULL;
1540 else
1541 t = known_vals[param_index];
1543 if (t &&
1544 TREE_CODE (t) == ADDR_EXPR
1545 && TREE_CODE (TREE_OPERAND (t, 0)) == FUNCTION_DECL)
1546 return TREE_OPERAND (t, 0);
1547 else
1548 return NULL_TREE;
1551 if (!flag_devirtualize)
1552 return NULL_TREE;
1554 gcc_assert (!ie->indirect_info->agg_contents);
1555 token = ie->indirect_info->otr_token;
1556 anc_offset = ie->indirect_info->offset;
1557 otr_type = ie->indirect_info->otr_type;
1559 t = NULL;
1561 /* Try to work out value of virtual table pointer value in replacemnets. */
1562 if (!t && agg_reps && !ie->indirect_info->by_ref)
1564 while (agg_reps)
1566 if (agg_reps->index == param_index
1567 && agg_reps->offset == ie->indirect_info->offset
1568 && agg_reps->by_ref)
1570 t = agg_reps->value;
1571 break;
1573 agg_reps = agg_reps->next;
1577 /* Try to work out value of virtual table pointer value in known
1578 aggregate values. */
1579 if (!t && known_aggs.length () > (unsigned int) param_index
1580 && !ie->indirect_info->by_ref)
1582 struct ipa_agg_jump_function *agg;
1583 agg = known_aggs[param_index];
1584 t = ipa_find_agg_cst_for_param (agg, ie->indirect_info->offset,
1585 true);
1588 /* If we found the virtual table pointer, lookup the target. */
1589 if (t)
1591 tree vtable;
1592 unsigned HOST_WIDE_INT offset;
1593 if (vtable_pointer_value_to_vtable (t, &vtable, &offset))
1595 target = gimple_get_virt_method_for_vtable (ie->indirect_info->otr_token,
1596 vtable, offset);
1597 if (target)
1599 if ((TREE_CODE (TREE_TYPE (target)) == FUNCTION_TYPE
1600 && DECL_FUNCTION_CODE (target) == BUILT_IN_UNREACHABLE)
1601 || !possible_polymorphic_call_target_p
1602 (ie, cgraph_node::get (target)))
1603 target = ipa_impossible_devirt_target (ie, target);
1604 return target;
1609 /* Did we work out BINFO via type propagation? */
1610 if (!t && known_binfos.length () > (unsigned int) param_index)
1611 t = known_binfos[param_index];
1612 /* Or do we know the constant value of pointer? */
1613 if (!t)
1614 t = known_vals[param_index];
1615 if (!t)
1616 return NULL_TREE;
1618 if (TREE_CODE (t) != TREE_BINFO)
1620 ipa_polymorphic_call_context context;
1621 vec <cgraph_node *>targets;
1622 bool final;
1624 if (!get_polymorphic_call_info_from_invariant
1625 (&context, t, ie->indirect_info->otr_type,
1626 anc_offset))
1627 return NULL_TREE;
1628 targets = possible_polymorphic_call_targets
1629 (ie->indirect_info->otr_type,
1630 ie->indirect_info->otr_token,
1631 context, &final);
1632 if (!final || targets.length () > 1)
1633 return NULL_TREE;
1634 if (targets.length () == 1)
1635 target = targets[0]->decl;
1636 else
1637 target = ipa_impossible_devirt_target (ie, NULL_TREE);
1639 else
1641 tree binfo;
1643 binfo = get_binfo_at_offset (t, anc_offset, otr_type);
1644 if (!binfo)
1645 return NULL_TREE;
1646 target = gimple_get_virt_method_for_binfo (token, binfo);
1649 if (target && !possible_polymorphic_call_target_p (ie,
1650 cgraph_node::get (target)))
1651 target = ipa_impossible_devirt_target (ie, target);
1653 return target;
1657 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
1658 (which can contain both constants and binfos), KNOWN_BINFOS (which can be
1659 NULL) or KNOWN_AGGS (which also can be NULL) return the destination. */
1661 tree
1662 ipa_get_indirect_edge_target (struct cgraph_edge *ie,
1663 vec<tree> known_vals,
1664 vec<tree> known_binfos,
1665 vec<ipa_agg_jump_function_p> known_aggs)
1667 return ipa_get_indirect_edge_target_1 (ie, known_vals, known_binfos,
1668 known_aggs, NULL);
1671 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
1672 and KNOWN_BINFOS. */
1674 static int
1675 devirtualization_time_bonus (struct cgraph_node *node,
1676 vec<tree> known_csts,
1677 vec<tree> known_binfos,
1678 vec<ipa_agg_jump_function_p> known_aggs)
1680 struct cgraph_edge *ie;
1681 int res = 0;
1683 for (ie = node->indirect_calls; ie; ie = ie->next_callee)
1685 struct cgraph_node *callee;
1686 struct inline_summary *isummary;
1687 enum availability avail;
1688 tree target;
1690 target = ipa_get_indirect_edge_target (ie, known_csts, known_binfos,
1691 known_aggs);
1692 if (!target)
1693 continue;
1695 /* Only bare minimum benefit for clearly un-inlineable targets. */
1696 res += 1;
1697 callee = cgraph_node::get (target);
1698 if (!callee || !callee->definition)
1699 continue;
1700 callee = callee->function_symbol (&avail);
1701 if (avail < AVAIL_AVAILABLE)
1702 continue;
1703 isummary = inline_summary (callee);
1704 if (!isummary->inlinable)
1705 continue;
1707 /* FIXME: The values below need re-considering and perhaps also
1708 integrating into the cost metrics, at lest in some very basic way. */
1709 if (isummary->size <= MAX_INLINE_INSNS_AUTO / 4)
1710 res += 31;
1711 else if (isummary->size <= MAX_INLINE_INSNS_AUTO / 2)
1712 res += 15;
1713 else if (isummary->size <= MAX_INLINE_INSNS_AUTO
1714 || DECL_DECLARED_INLINE_P (callee->decl))
1715 res += 7;
1718 return res;
1721 /* Return time bonus incurred because of HINTS. */
1723 static int
1724 hint_time_bonus (inline_hints hints)
1726 int result = 0;
1727 if (hints & (INLINE_HINT_loop_iterations | INLINE_HINT_loop_stride))
1728 result += PARAM_VALUE (PARAM_IPA_CP_LOOP_HINT_BONUS);
1729 if (hints & INLINE_HINT_array_index)
1730 result += PARAM_VALUE (PARAM_IPA_CP_ARRAY_INDEX_HINT_BONUS);
1731 return result;
1734 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
1735 and SIZE_COST and with the sum of frequencies of incoming edges to the
1736 potential new clone in FREQUENCIES. */
1738 static bool
1739 good_cloning_opportunity_p (struct cgraph_node *node, int time_benefit,
1740 int freq_sum, gcov_type count_sum, int size_cost)
1742 if (time_benefit == 0
1743 || !flag_ipa_cp_clone
1744 || !optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node->decl)))
1745 return false;
1747 gcc_assert (size_cost > 0);
1749 if (max_count)
1751 int factor = (count_sum * 1000) / max_count;
1752 int64_t evaluation = (((int64_t) time_benefit * factor)
1753 / size_cost);
1755 if (dump_file && (dump_flags & TDF_DETAILS))
1756 fprintf (dump_file, " good_cloning_opportunity_p (time: %i, "
1757 "size: %i, count_sum: " HOST_WIDE_INT_PRINT_DEC
1758 ") -> evaluation: " "%"PRId64
1759 ", threshold: %i\n",
1760 time_benefit, size_cost, (HOST_WIDE_INT) count_sum,
1761 evaluation, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD));
1763 return evaluation >= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD);
1765 else
1767 int64_t evaluation = (((int64_t) time_benefit * freq_sum)
1768 / size_cost);
1770 if (dump_file && (dump_flags & TDF_DETAILS))
1771 fprintf (dump_file, " good_cloning_opportunity_p (time: %i, "
1772 "size: %i, freq_sum: %i) -> evaluation: "
1773 "%"PRId64 ", threshold: %i\n",
1774 time_benefit, size_cost, freq_sum, evaluation,
1775 PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD));
1777 return evaluation >= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD);
1781 /* Return all context independent values from aggregate lattices in PLATS in a
1782 vector. Return NULL if there are none. */
1784 static vec<ipa_agg_jf_item, va_gc> *
1785 context_independent_aggregate_values (struct ipcp_param_lattices *plats)
1787 vec<ipa_agg_jf_item, va_gc> *res = NULL;
1789 if (plats->aggs_bottom
1790 || plats->aggs_contain_variable
1791 || plats->aggs_count == 0)
1792 return NULL;
1794 for (struct ipcp_agg_lattice *aglat = plats->aggs;
1795 aglat;
1796 aglat = aglat->next)
1797 if (ipa_lat_is_single_const (aglat))
1799 struct ipa_agg_jf_item item;
1800 item.offset = aglat->offset;
1801 item.value = aglat->values->value;
1802 vec_safe_push (res, item);
1804 return res;
1807 /* Allocate KNOWN_CSTS, KNOWN_BINFOS and, if non-NULL, KNOWN_AGGS and populate
1808 them with values of parameters that are known independent of the context.
1809 INFO describes the function. If REMOVABLE_PARAMS_COST is non-NULL, the
1810 movement cost of all removable parameters will be stored in it. */
1812 static bool
1813 gather_context_independent_values (struct ipa_node_params *info,
1814 vec<tree> *known_csts,
1815 vec<tree> *known_binfos,
1816 vec<ipa_agg_jump_function> *known_aggs,
1817 int *removable_params_cost)
1819 int i, count = ipa_get_param_count (info);
1820 bool ret = false;
1822 known_csts->create (0);
1823 known_binfos->create (0);
1824 known_csts->safe_grow_cleared (count);
1825 known_binfos->safe_grow_cleared (count);
1826 if (known_aggs)
1828 known_aggs->create (0);
1829 known_aggs->safe_grow_cleared (count);
1832 if (removable_params_cost)
1833 *removable_params_cost = 0;
1835 for (i = 0; i < count ; i++)
1837 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
1838 struct ipcp_lattice *lat = &plats->itself;
1840 if (ipa_lat_is_single_const (lat))
1842 struct ipcp_value *val = lat->values;
1843 if (TREE_CODE (val->value) != TREE_BINFO)
1845 (*known_csts)[i] = val->value;
1846 if (removable_params_cost)
1847 *removable_params_cost
1848 += estimate_move_cost (TREE_TYPE (val->value), false);
1849 ret = true;
1851 else if (plats->virt_call)
1853 (*known_binfos)[i] = val->value;
1854 ret = true;
1856 else if (removable_params_cost
1857 && !ipa_is_param_used (info, i))
1858 *removable_params_cost += ipa_get_param_move_cost (info, i);
1860 else if (removable_params_cost
1861 && !ipa_is_param_used (info, i))
1862 *removable_params_cost
1863 += ipa_get_param_move_cost (info, i);
1865 if (known_aggs)
1867 vec<ipa_agg_jf_item, va_gc> *agg_items;
1868 struct ipa_agg_jump_function *ajf;
1870 agg_items = context_independent_aggregate_values (plats);
1871 ajf = &(*known_aggs)[i];
1872 ajf->items = agg_items;
1873 ajf->by_ref = plats->aggs_by_ref;
1874 ret |= agg_items != NULL;
1878 return ret;
1881 /* The current interface in ipa-inline-analysis requires a pointer vector.
1882 Create it.
1884 FIXME: That interface should be re-worked, this is slightly silly. Still,
1885 I'd like to discuss how to change it first and this demonstrates the
1886 issue. */
1888 static vec<ipa_agg_jump_function_p>
1889 agg_jmp_p_vec_for_t_vec (vec<ipa_agg_jump_function> known_aggs)
1891 vec<ipa_agg_jump_function_p> ret;
1892 struct ipa_agg_jump_function *ajf;
1893 int i;
1895 ret.create (known_aggs.length ());
1896 FOR_EACH_VEC_ELT (known_aggs, i, ajf)
1897 ret.quick_push (ajf);
1898 return ret;
1901 /* Iterate over known values of parameters of NODE and estimate the local
1902 effects in terms of time and size they have. */
1904 static void
1905 estimate_local_effects (struct cgraph_node *node)
1907 struct ipa_node_params *info = IPA_NODE_REF (node);
1908 int i, count = ipa_get_param_count (info);
1909 vec<tree> known_csts, known_binfos;
1910 vec<ipa_agg_jump_function> known_aggs;
1911 vec<ipa_agg_jump_function_p> known_aggs_ptrs;
1912 bool always_const;
1913 int base_time = inline_summary (node)->time;
1914 int removable_params_cost;
1916 if (!count || !ipcp_versionable_function_p (node))
1917 return;
1919 if (dump_file && (dump_flags & TDF_DETAILS))
1920 fprintf (dump_file, "\nEstimating effects for %s/%i, base_time: %i.\n",
1921 node->name (), node->order, base_time);
1923 always_const = gather_context_independent_values (info, &known_csts,
1924 &known_binfos, &known_aggs,
1925 &removable_params_cost);
1926 known_aggs_ptrs = agg_jmp_p_vec_for_t_vec (known_aggs);
1927 if (always_const)
1929 struct caller_statistics stats;
1930 inline_hints hints;
1931 int time, size;
1933 init_caller_stats (&stats);
1934 node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats,
1935 false);
1936 estimate_ipcp_clone_size_and_time (node, known_csts, known_binfos,
1937 known_aggs_ptrs, &size, &time, &hints);
1938 time -= devirtualization_time_bonus (node, known_csts, known_binfos,
1939 known_aggs_ptrs);
1940 time -= hint_time_bonus (hints);
1941 time -= removable_params_cost;
1942 size -= stats.n_calls * removable_params_cost;
1944 if (dump_file)
1945 fprintf (dump_file, " - context independent values, size: %i, "
1946 "time_benefit: %i\n", size, base_time - time);
1948 if (size <= 0
1949 || node->will_be_removed_from_program_if_no_direct_calls_p ())
1951 info->do_clone_for_all_contexts = true;
1952 base_time = time;
1954 if (dump_file)
1955 fprintf (dump_file, " Decided to specialize for all "
1956 "known contexts, code not going to grow.\n");
1958 else if (good_cloning_opportunity_p (node, base_time - time,
1959 stats.freq_sum, stats.count_sum,
1960 size))
1962 if (size + overall_size <= max_new_size)
1964 info->do_clone_for_all_contexts = true;
1965 base_time = time;
1966 overall_size += size;
1968 if (dump_file)
1969 fprintf (dump_file, " Decided to specialize for all "
1970 "known contexts, growth deemed beneficial.\n");
1972 else if (dump_file && (dump_flags & TDF_DETAILS))
1973 fprintf (dump_file, " Not cloning for all contexts because "
1974 "max_new_size would be reached with %li.\n",
1975 size + overall_size);
1979 for (i = 0; i < count ; i++)
1981 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
1982 struct ipcp_lattice *lat = &plats->itself;
1983 struct ipcp_value *val;
1984 int emc;
1986 if (lat->bottom
1987 || !lat->values
1988 || known_csts[i]
1989 || known_binfos[i])
1990 continue;
1992 for (val = lat->values; val; val = val->next)
1994 int time, size, time_benefit;
1995 inline_hints hints;
1997 if (TREE_CODE (val->value) != TREE_BINFO)
1999 known_csts[i] = val->value;
2000 known_binfos[i] = NULL_TREE;
2001 emc = estimate_move_cost (TREE_TYPE (val->value), true);
2003 else if (plats->virt_call)
2005 known_csts[i] = NULL_TREE;
2006 known_binfos[i] = val->value;
2007 emc = 0;
2009 else
2010 continue;
2012 estimate_ipcp_clone_size_and_time (node, known_csts, known_binfos,
2013 known_aggs_ptrs, &size, &time,
2014 &hints);
2015 time_benefit = base_time - time
2016 + devirtualization_time_bonus (node, known_csts, known_binfos,
2017 known_aggs_ptrs)
2018 + hint_time_bonus (hints)
2019 + removable_params_cost + emc;
2021 gcc_checking_assert (size >=0);
2022 /* The inliner-heuristics based estimates may think that in certain
2023 contexts some functions do not have any size at all but we want
2024 all specializations to have at least a tiny cost, not least not to
2025 divide by zero. */
2026 if (size == 0)
2027 size = 1;
2029 if (dump_file && (dump_flags & TDF_DETAILS))
2031 fprintf (dump_file, " - estimates for value ");
2032 print_ipcp_constant_value (dump_file, val->value);
2033 fprintf (dump_file, " for ");
2034 ipa_dump_param (dump_file, info, i);
2035 fprintf (dump_file, ": time_benefit: %i, size: %i\n",
2036 time_benefit, size);
2039 val->local_time_benefit = time_benefit;
2040 val->local_size_cost = size;
2042 known_binfos[i] = NULL_TREE;
2043 known_csts[i] = NULL_TREE;
2046 for (i = 0; i < count ; i++)
2048 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
2049 struct ipa_agg_jump_function *ajf;
2050 struct ipcp_agg_lattice *aglat;
2052 if (plats->aggs_bottom || !plats->aggs)
2053 continue;
2055 ajf = &known_aggs[i];
2056 for (aglat = plats->aggs; aglat; aglat = aglat->next)
2058 struct ipcp_value *val;
2059 if (aglat->bottom || !aglat->values
2060 /* If the following is true, the one value is in known_aggs. */
2061 || (!plats->aggs_contain_variable
2062 && ipa_lat_is_single_const (aglat)))
2063 continue;
2065 for (val = aglat->values; val; val = val->next)
2067 int time, size, time_benefit;
2068 struct ipa_agg_jf_item item;
2069 inline_hints hints;
2071 item.offset = aglat->offset;
2072 item.value = val->value;
2073 vec_safe_push (ajf->items, item);
2075 estimate_ipcp_clone_size_and_time (node, known_csts, known_binfos,
2076 known_aggs_ptrs, &size, &time,
2077 &hints);
2078 time_benefit = base_time - time
2079 + devirtualization_time_bonus (node, known_csts, known_binfos,
2080 known_aggs_ptrs)
2081 + hint_time_bonus (hints);
2082 gcc_checking_assert (size >=0);
2083 if (size == 0)
2084 size = 1;
2086 if (dump_file && (dump_flags & TDF_DETAILS))
2088 fprintf (dump_file, " - estimates for value ");
2089 print_ipcp_constant_value (dump_file, val->value);
2090 fprintf (dump_file, " for ");
2091 ipa_dump_param (dump_file, info, i);
2092 fprintf (dump_file, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
2093 "]: time_benefit: %i, size: %i\n",
2094 plats->aggs_by_ref ? "ref " : "",
2095 aglat->offset, time_benefit, size);
2098 val->local_time_benefit = time_benefit;
2099 val->local_size_cost = size;
2100 ajf->items->pop ();
2105 for (i = 0; i < count ; i++)
2106 vec_free (known_aggs[i].items);
2108 known_csts.release ();
2109 known_binfos.release ();
2110 known_aggs.release ();
2111 known_aggs_ptrs.release ();
2115 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
2116 topological sort of values. */
2118 static void
2119 add_val_to_toposort (struct ipcp_value *cur_val)
2121 static int dfs_counter = 0;
2122 static struct ipcp_value *stack;
2123 struct ipcp_value_source *src;
2125 if (cur_val->dfs)
2126 return;
2128 dfs_counter++;
2129 cur_val->dfs = dfs_counter;
2130 cur_val->low_link = dfs_counter;
2132 cur_val->topo_next = stack;
2133 stack = cur_val;
2134 cur_val->on_stack = true;
2136 for (src = cur_val->sources; src; src = src->next)
2137 if (src->val)
2139 if (src->val->dfs == 0)
2141 add_val_to_toposort (src->val);
2142 if (src->val->low_link < cur_val->low_link)
2143 cur_val->low_link = src->val->low_link;
2145 else if (src->val->on_stack
2146 && src->val->dfs < cur_val->low_link)
2147 cur_val->low_link = src->val->dfs;
2150 if (cur_val->dfs == cur_val->low_link)
2152 struct ipcp_value *v, *scc_list = NULL;
2156 v = stack;
2157 stack = v->topo_next;
2158 v->on_stack = false;
2160 v->scc_next = scc_list;
2161 scc_list = v;
2163 while (v != cur_val);
2165 cur_val->topo_next = values_topo;
2166 values_topo = cur_val;
2170 /* Add all values in lattices associated with NODE to the topological sort if
2171 they are not there yet. */
2173 static void
2174 add_all_node_vals_to_toposort (struct cgraph_node *node)
2176 struct ipa_node_params *info = IPA_NODE_REF (node);
2177 int i, count = ipa_get_param_count (info);
2179 for (i = 0; i < count ; i++)
2181 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
2182 struct ipcp_lattice *lat = &plats->itself;
2183 struct ipcp_agg_lattice *aglat;
2184 struct ipcp_value *val;
2186 if (!lat->bottom)
2187 for (val = lat->values; val; val = val->next)
2188 add_val_to_toposort (val);
2190 if (!plats->aggs_bottom)
2191 for (aglat = plats->aggs; aglat; aglat = aglat->next)
2192 if (!aglat->bottom)
2193 for (val = aglat->values; val; val = val->next)
2194 add_val_to_toposort (val);
2198 /* One pass of constants propagation along the call graph edges, from callers
2199 to callees (requires topological ordering in TOPO), iterate over strongly
2200 connected components. */
2202 static void
2203 propagate_constants_topo (struct topo_info *topo)
2205 int i;
2207 for (i = topo->nnodes - 1; i >= 0; i--)
2209 unsigned j;
2210 struct cgraph_node *v, *node = topo->order[i];
2211 vec<cgraph_node *> cycle_nodes = ipa_get_nodes_in_cycle (node);
2213 /* First, iteratively propagate within the strongly connected component
2214 until all lattices stabilize. */
2215 FOR_EACH_VEC_ELT (cycle_nodes, j, v)
2216 if (v->has_gimple_body_p ())
2217 push_node_to_stack (topo, v);
2219 v = pop_node_from_stack (topo);
2220 while (v)
2222 struct cgraph_edge *cs;
2224 for (cs = v->callees; cs; cs = cs->next_callee)
2225 if (ipa_edge_within_scc (cs)
2226 && propagate_constants_accross_call (cs))
2227 push_node_to_stack (topo, cs->callee);
2228 v = pop_node_from_stack (topo);
2231 /* Afterwards, propagate along edges leading out of the SCC, calculates
2232 the local effects of the discovered constants and all valid values to
2233 their topological sort. */
2234 FOR_EACH_VEC_ELT (cycle_nodes, j, v)
2235 if (v->has_gimple_body_p ())
2237 struct cgraph_edge *cs;
2239 estimate_local_effects (v);
2240 add_all_node_vals_to_toposort (v);
2241 for (cs = v->callees; cs; cs = cs->next_callee)
2242 if (!ipa_edge_within_scc (cs))
2243 propagate_constants_accross_call (cs);
2245 cycle_nodes.release ();
2250 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
2251 the bigger one if otherwise. */
2253 static int
2254 safe_add (int a, int b)
2256 if (a > INT_MAX/2 || b > INT_MAX/2)
2257 return a > b ? a : b;
2258 else
2259 return a + b;
2263 /* Propagate the estimated effects of individual values along the topological
2264 from the dependent values to those they depend on. */
2266 static void
2267 propagate_effects (void)
2269 struct ipcp_value *base;
2271 for (base = values_topo; base; base = base->topo_next)
2273 struct ipcp_value_source *src;
2274 struct ipcp_value *val;
2275 int time = 0, size = 0;
2277 for (val = base; val; val = val->scc_next)
2279 time = safe_add (time,
2280 val->local_time_benefit + val->prop_time_benefit);
2281 size = safe_add (size, val->local_size_cost + val->prop_size_cost);
2284 for (val = base; val; val = val->scc_next)
2285 for (src = val->sources; src; src = src->next)
2286 if (src->val
2287 && cgraph_maybe_hot_edge_p (src->cs))
2289 src->val->prop_time_benefit = safe_add (time,
2290 src->val->prop_time_benefit);
2291 src->val->prop_size_cost = safe_add (size,
2292 src->val->prop_size_cost);
2298 /* Propagate constants, binfos and their effects from the summaries
2299 interprocedurally. */
2301 static void
2302 ipcp_propagate_stage (struct topo_info *topo)
2304 struct cgraph_node *node;
2306 if (dump_file)
2307 fprintf (dump_file, "\n Propagating constants:\n\n");
2309 if (in_lto_p)
2310 ipa_update_after_lto_read ();
2313 FOR_EACH_DEFINED_FUNCTION (node)
2315 struct ipa_node_params *info = IPA_NODE_REF (node);
2317 determine_versionability (node);
2318 if (node->has_gimple_body_p ())
2320 info->lattices = XCNEWVEC (struct ipcp_param_lattices,
2321 ipa_get_param_count (info));
2322 initialize_node_lattices (node);
2324 if (node->definition && !node->alias)
2325 overall_size += inline_summary (node)->self_size;
2326 if (node->count > max_count)
2327 max_count = node->count;
2330 max_new_size = overall_size;
2331 if (max_new_size < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
2332 max_new_size = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
2333 max_new_size += max_new_size * PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH) / 100 + 1;
2335 if (dump_file)
2336 fprintf (dump_file, "\noverall_size: %li, max_new_size: %li\n",
2337 overall_size, max_new_size);
2339 propagate_constants_topo (topo);
2340 #ifdef ENABLE_CHECKING
2341 ipcp_verify_propagated_values ();
2342 #endif
2343 propagate_effects ();
2345 if (dump_file)
2347 fprintf (dump_file, "\nIPA lattices after all propagation:\n");
2348 print_all_lattices (dump_file, (dump_flags & TDF_DETAILS), true);
2352 /* Discover newly direct outgoing edges from NODE which is a new clone with
2353 known KNOWN_VALS and make them direct. */
2355 static void
2356 ipcp_discover_new_direct_edges (struct cgraph_node *node,
2357 vec<tree> known_vals,
2358 struct ipa_agg_replacement_value *aggvals)
2360 struct cgraph_edge *ie, *next_ie;
2361 bool found = false;
2363 for (ie = node->indirect_calls; ie; ie = next_ie)
2365 tree target;
2367 next_ie = ie->next_callee;
2368 target = ipa_get_indirect_edge_target_1 (ie, known_vals, vNULL, vNULL,
2369 aggvals);
2370 if (target)
2372 bool agg_contents = ie->indirect_info->agg_contents;
2373 bool polymorphic = ie->indirect_info->polymorphic;
2374 int param_index = ie->indirect_info->param_index;
2375 struct cgraph_edge *cs = ipa_make_edge_direct_to_target (ie, target);
2376 found = true;
2378 if (cs && !agg_contents && !polymorphic)
2380 struct ipa_node_params *info = IPA_NODE_REF (node);
2381 int c = ipa_get_controlled_uses (info, param_index);
2382 if (c != IPA_UNDESCRIBED_USE)
2384 struct ipa_ref *to_del;
2386 c--;
2387 ipa_set_controlled_uses (info, param_index, c);
2388 if (dump_file && (dump_flags & TDF_DETAILS))
2389 fprintf (dump_file, " controlled uses count of param "
2390 "%i bumped down to %i\n", param_index, c);
2391 if (c == 0
2392 && (to_del = node->find_reference (cs->callee, NULL, 0)))
2394 if (dump_file && (dump_flags & TDF_DETAILS))
2395 fprintf (dump_file, " and even removing its "
2396 "cloning-created reference\n");
2397 to_del->remove_reference ();
2403 /* Turning calls to direct calls will improve overall summary. */
2404 if (found)
2405 inline_update_overall_summary (node);
2408 /* Vector of pointers which for linked lists of clones of an original crgaph
2409 edge. */
2411 static vec<cgraph_edge *> next_edge_clone;
2412 static vec<cgraph_edge *> prev_edge_clone;
2414 static inline void
2415 grow_edge_clone_vectors (void)
2417 if (next_edge_clone.length ()
2418 <= (unsigned) cgraph_edge_max_uid)
2419 next_edge_clone.safe_grow_cleared (cgraph_edge_max_uid + 1);
2420 if (prev_edge_clone.length ()
2421 <= (unsigned) cgraph_edge_max_uid)
2422 prev_edge_clone.safe_grow_cleared (cgraph_edge_max_uid + 1);
2425 /* Edge duplication hook to grow the appropriate linked list in
2426 next_edge_clone. */
2428 static void
2429 ipcp_edge_duplication_hook (struct cgraph_edge *src, struct cgraph_edge *dst,
2430 void *)
2432 grow_edge_clone_vectors ();
2434 struct cgraph_edge *old_next = next_edge_clone[src->uid];
2435 if (old_next)
2436 prev_edge_clone[old_next->uid] = dst;
2437 prev_edge_clone[dst->uid] = src;
2439 next_edge_clone[dst->uid] = old_next;
2440 next_edge_clone[src->uid] = dst;
2443 /* Hook that is called by cgraph.c when an edge is removed. */
2445 static void
2446 ipcp_edge_removal_hook (struct cgraph_edge *cs, void *)
2448 grow_edge_clone_vectors ();
2450 struct cgraph_edge *prev = prev_edge_clone[cs->uid];
2451 struct cgraph_edge *next = next_edge_clone[cs->uid];
2452 if (prev)
2453 next_edge_clone[prev->uid] = next;
2454 if (next)
2455 prev_edge_clone[next->uid] = prev;
2458 /* See if NODE is a clone with a known aggregate value at a given OFFSET of a
2459 parameter with the given INDEX. */
2461 static tree
2462 get_clone_agg_value (struct cgraph_node *node, HOST_WIDE_INT offset,
2463 int index)
2465 struct ipa_agg_replacement_value *aggval;
2467 aggval = ipa_get_agg_replacements_for_node (node);
2468 while (aggval)
2470 if (aggval->offset == offset
2471 && aggval->index == index)
2472 return aggval->value;
2473 aggval = aggval->next;
2475 return NULL_TREE;
2478 /* Return true if edge CS does bring about the value described by SRC. */
2480 static bool
2481 cgraph_edge_brings_value_p (struct cgraph_edge *cs,
2482 struct ipcp_value_source *src)
2484 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
2485 cgraph_node *real_dest = cs->callee->function_symbol ();
2486 struct ipa_node_params *dst_info = IPA_NODE_REF (real_dest);
2488 if ((dst_info->ipcp_orig_node && !dst_info->is_all_contexts_clone)
2489 || caller_info->node_dead)
2490 return false;
2491 if (!src->val)
2492 return true;
2494 if (caller_info->ipcp_orig_node)
2496 tree t;
2497 if (src->offset == -1)
2498 t = caller_info->known_vals[src->index];
2499 else
2500 t = get_clone_agg_value (cs->caller, src->offset, src->index);
2501 return (t != NULL_TREE
2502 && values_equal_for_ipcp_p (src->val->value, t));
2504 else
2506 struct ipcp_agg_lattice *aglat;
2507 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (caller_info,
2508 src->index);
2509 if (src->offset == -1)
2510 return (ipa_lat_is_single_const (&plats->itself)
2511 && values_equal_for_ipcp_p (src->val->value,
2512 plats->itself.values->value));
2513 else
2515 if (plats->aggs_bottom || plats->aggs_contain_variable)
2516 return false;
2517 for (aglat = plats->aggs; aglat; aglat = aglat->next)
2518 if (aglat->offset == src->offset)
2519 return (ipa_lat_is_single_const (aglat)
2520 && values_equal_for_ipcp_p (src->val->value,
2521 aglat->values->value));
2523 return false;
2527 /* Get the next clone in the linked list of clones of an edge. */
2529 static inline struct cgraph_edge *
2530 get_next_cgraph_edge_clone (struct cgraph_edge *cs)
2532 return next_edge_clone[cs->uid];
2535 /* Given VAL, iterate over all its sources and if they still hold, add their
2536 edge frequency and their number into *FREQUENCY and *CALLER_COUNT
2537 respectively. */
2539 static bool
2540 get_info_about_necessary_edges (struct ipcp_value *val, int *freq_sum,
2541 gcov_type *count_sum, int *caller_count)
2543 struct ipcp_value_source *src;
2544 int freq = 0, count = 0;
2545 gcov_type cnt = 0;
2546 bool hot = false;
2548 for (src = val->sources; src; src = src->next)
2550 struct cgraph_edge *cs = src->cs;
2551 while (cs)
2553 if (cgraph_edge_brings_value_p (cs, src))
2555 count++;
2556 freq += cs->frequency;
2557 cnt += cs->count;
2558 hot |= cgraph_maybe_hot_edge_p (cs);
2560 cs = get_next_cgraph_edge_clone (cs);
2564 *freq_sum = freq;
2565 *count_sum = cnt;
2566 *caller_count = count;
2567 return hot;
2570 /* Return a vector of incoming edges that do bring value VAL. It is assumed
2571 their number is known and equal to CALLER_COUNT. */
2573 static vec<cgraph_edge *>
2574 gather_edges_for_value (struct ipcp_value *val, int caller_count)
2576 struct ipcp_value_source *src;
2577 vec<cgraph_edge *> ret;
2579 ret.create (caller_count);
2580 for (src = val->sources; src; src = src->next)
2582 struct cgraph_edge *cs = src->cs;
2583 while (cs)
2585 if (cgraph_edge_brings_value_p (cs, src))
2586 ret.quick_push (cs);
2587 cs = get_next_cgraph_edge_clone (cs);
2591 return ret;
2594 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
2595 Return it or NULL if for some reason it cannot be created. */
2597 static struct ipa_replace_map *
2598 get_replacement_map (struct ipa_node_params *info, tree value, int parm_num)
2600 struct ipa_replace_map *replace_map;
2603 replace_map = ggc_alloc<ipa_replace_map> ();
2604 if (dump_file)
2606 fprintf (dump_file, " replacing ");
2607 ipa_dump_param (dump_file, info, parm_num);
2609 fprintf (dump_file, " with const ");
2610 print_generic_expr (dump_file, value, 0);
2611 fprintf (dump_file, "\n");
2613 replace_map->old_tree = NULL;
2614 replace_map->parm_num = parm_num;
2615 replace_map->new_tree = value;
2616 replace_map->replace_p = true;
2617 replace_map->ref_p = false;
2619 return replace_map;
2622 /* Dump new profiling counts */
2624 static void
2625 dump_profile_updates (struct cgraph_node *orig_node,
2626 struct cgraph_node *new_node)
2628 struct cgraph_edge *cs;
2630 fprintf (dump_file, " setting count of the specialized node to "
2631 HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) new_node->count);
2632 for (cs = new_node->callees; cs ; cs = cs->next_callee)
2633 fprintf (dump_file, " edge to %s has count "
2634 HOST_WIDE_INT_PRINT_DEC "\n",
2635 cs->callee->name (), (HOST_WIDE_INT) cs->count);
2637 fprintf (dump_file, " setting count of the original node to "
2638 HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) orig_node->count);
2639 for (cs = orig_node->callees; cs ; cs = cs->next_callee)
2640 fprintf (dump_file, " edge to %s is left with "
2641 HOST_WIDE_INT_PRINT_DEC "\n",
2642 cs->callee->name (), (HOST_WIDE_INT) cs->count);
2645 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
2646 their profile information to reflect this. */
2648 static void
2649 update_profiling_info (struct cgraph_node *orig_node,
2650 struct cgraph_node *new_node)
2652 struct cgraph_edge *cs;
2653 struct caller_statistics stats;
2654 gcov_type new_sum, orig_sum;
2655 gcov_type remainder, orig_node_count = orig_node->count;
2657 if (orig_node_count == 0)
2658 return;
2660 init_caller_stats (&stats);
2661 orig_node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats,
2662 false);
2663 orig_sum = stats.count_sum;
2664 init_caller_stats (&stats);
2665 new_node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats,
2666 false);
2667 new_sum = stats.count_sum;
2669 if (orig_node_count < orig_sum + new_sum)
2671 if (dump_file)
2672 fprintf (dump_file, " Problem: node %s/%i has too low count "
2673 HOST_WIDE_INT_PRINT_DEC " while the sum of incoming "
2674 "counts is " HOST_WIDE_INT_PRINT_DEC "\n",
2675 orig_node->name (), orig_node->order,
2676 (HOST_WIDE_INT) orig_node_count,
2677 (HOST_WIDE_INT) (orig_sum + new_sum));
2679 orig_node_count = (orig_sum + new_sum) * 12 / 10;
2680 if (dump_file)
2681 fprintf (dump_file, " proceeding by pretending it was "
2682 HOST_WIDE_INT_PRINT_DEC "\n",
2683 (HOST_WIDE_INT) orig_node_count);
2686 new_node->count = new_sum;
2687 remainder = orig_node_count - new_sum;
2688 orig_node->count = remainder;
2690 for (cs = new_node->callees; cs ; cs = cs->next_callee)
2691 if (cs->frequency)
2692 cs->count = apply_probability (cs->count,
2693 GCOV_COMPUTE_SCALE (new_sum,
2694 orig_node_count));
2695 else
2696 cs->count = 0;
2698 for (cs = orig_node->callees; cs ; cs = cs->next_callee)
2699 cs->count = apply_probability (cs->count,
2700 GCOV_COMPUTE_SCALE (remainder,
2701 orig_node_count));
2703 if (dump_file)
2704 dump_profile_updates (orig_node, new_node);
2707 /* Update the respective profile of specialized NEW_NODE and the original
2708 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
2709 have been redirected to the specialized version. */
2711 static void
2712 update_specialized_profile (struct cgraph_node *new_node,
2713 struct cgraph_node *orig_node,
2714 gcov_type redirected_sum)
2716 struct cgraph_edge *cs;
2717 gcov_type new_node_count, orig_node_count = orig_node->count;
2719 if (dump_file)
2720 fprintf (dump_file, " the sum of counts of redirected edges is "
2721 HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) redirected_sum);
2722 if (orig_node_count == 0)
2723 return;
2725 gcc_assert (orig_node_count >= redirected_sum);
2727 new_node_count = new_node->count;
2728 new_node->count += redirected_sum;
2729 orig_node->count -= redirected_sum;
2731 for (cs = new_node->callees; cs ; cs = cs->next_callee)
2732 if (cs->frequency)
2733 cs->count += apply_probability (cs->count,
2734 GCOV_COMPUTE_SCALE (redirected_sum,
2735 new_node_count));
2736 else
2737 cs->count = 0;
2739 for (cs = orig_node->callees; cs ; cs = cs->next_callee)
2741 gcov_type dec = apply_probability (cs->count,
2742 GCOV_COMPUTE_SCALE (redirected_sum,
2743 orig_node_count));
2744 if (dec < cs->count)
2745 cs->count -= dec;
2746 else
2747 cs->count = 0;
2750 if (dump_file)
2751 dump_profile_updates (orig_node, new_node);
2754 /* Create a specialized version of NODE with known constants and types of
2755 parameters in KNOWN_VALS and redirect all edges in CALLERS to it. */
2757 static struct cgraph_node *
2758 create_specialized_node (struct cgraph_node *node,
2759 vec<tree> known_vals,
2760 struct ipa_agg_replacement_value *aggvals,
2761 vec<cgraph_edge *> callers)
2763 struct ipa_node_params *new_info, *info = IPA_NODE_REF (node);
2764 vec<ipa_replace_map *, va_gc> *replace_trees = NULL;
2765 struct ipa_agg_replacement_value *av;
2766 struct cgraph_node *new_node;
2767 int i, count = ipa_get_param_count (info);
2768 bitmap args_to_skip;
2770 gcc_assert (!info->ipcp_orig_node);
2772 if (node->local.can_change_signature)
2774 args_to_skip = BITMAP_GGC_ALLOC ();
2775 for (i = 0; i < count; i++)
2777 tree t = known_vals[i];
2779 if ((t && TREE_CODE (t) != TREE_BINFO)
2780 || !ipa_is_param_used (info, i))
2781 bitmap_set_bit (args_to_skip, i);
2784 else
2786 args_to_skip = NULL;
2787 if (dump_file && (dump_flags & TDF_DETAILS))
2788 fprintf (dump_file, " cannot change function signature\n");
2791 for (i = 0; i < count ; i++)
2793 tree t = known_vals[i];
2794 if (t && TREE_CODE (t) != TREE_BINFO)
2796 struct ipa_replace_map *replace_map;
2798 replace_map = get_replacement_map (info, t, i);
2799 if (replace_map)
2800 vec_safe_push (replace_trees, replace_map);
2804 new_node = node->create_virtual_clone (callers, replace_trees,
2805 args_to_skip, "constprop");
2806 ipa_set_node_agg_value_chain (new_node, aggvals);
2807 for (av = aggvals; av; av = av->next)
2808 new_node->maybe_add_reference (av->value, IPA_REF_ADDR, NULL);
2810 if (dump_file && (dump_flags & TDF_DETAILS))
2812 fprintf (dump_file, " the new node is %s/%i.\n",
2813 new_node->name (), new_node->order);
2814 if (aggvals)
2815 ipa_dump_agg_replacement_values (dump_file, aggvals);
2817 ipa_check_create_node_params ();
2818 update_profiling_info (node, new_node);
2819 new_info = IPA_NODE_REF (new_node);
2820 new_info->ipcp_orig_node = node;
2821 new_info->known_vals = known_vals;
2823 ipcp_discover_new_direct_edges (new_node, known_vals, aggvals);
2825 callers.release ();
2826 return new_node;
2829 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
2830 KNOWN_VALS with constants and types that are also known for all of the
2831 CALLERS. */
2833 static void
2834 find_more_scalar_values_for_callers_subset (struct cgraph_node *node,
2835 vec<tree> known_vals,
2836 vec<cgraph_edge *> callers)
2838 struct ipa_node_params *info = IPA_NODE_REF (node);
2839 int i, count = ipa_get_param_count (info);
2841 for (i = 0; i < count ; i++)
2843 struct cgraph_edge *cs;
2844 tree newval = NULL_TREE;
2845 int j;
2847 if (ipa_get_scalar_lat (info, i)->bottom || known_vals[i])
2848 continue;
2850 FOR_EACH_VEC_ELT (callers, j, cs)
2852 struct ipa_jump_func *jump_func;
2853 tree t;
2855 if (i >= ipa_get_cs_argument_count (IPA_EDGE_REF (cs)))
2857 newval = NULL_TREE;
2858 break;
2860 jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
2861 t = ipa_value_from_jfunc (IPA_NODE_REF (cs->caller), jump_func);
2862 if (!t
2863 || (newval
2864 && !values_equal_for_ipcp_p (t, newval)))
2866 newval = NULL_TREE;
2867 break;
2869 else
2870 newval = t;
2873 if (newval)
2875 if (dump_file && (dump_flags & TDF_DETAILS))
2877 fprintf (dump_file, " adding an extra known scalar value ");
2878 print_ipcp_constant_value (dump_file, newval);
2879 fprintf (dump_file, " for ");
2880 ipa_dump_param (dump_file, info, i);
2881 fprintf (dump_file, "\n");
2884 known_vals[i] = newval;
2889 /* Go through PLATS and create a vector of values consisting of values and
2890 offsets (minus OFFSET) of lattices that contain only a single value. */
2892 static vec<ipa_agg_jf_item>
2893 copy_plats_to_inter (struct ipcp_param_lattices *plats, HOST_WIDE_INT offset)
2895 vec<ipa_agg_jf_item> res = vNULL;
2897 if (!plats->aggs || plats->aggs_contain_variable || plats->aggs_bottom)
2898 return vNULL;
2900 for (struct ipcp_agg_lattice *aglat = plats->aggs; aglat; aglat = aglat->next)
2901 if (ipa_lat_is_single_const (aglat))
2903 struct ipa_agg_jf_item ti;
2904 ti.offset = aglat->offset - offset;
2905 ti.value = aglat->values->value;
2906 res.safe_push (ti);
2908 return res;
2911 /* Intersect all values in INTER with single value lattices in PLATS (while
2912 subtracting OFFSET). */
2914 static void
2915 intersect_with_plats (struct ipcp_param_lattices *plats,
2916 vec<ipa_agg_jf_item> *inter,
2917 HOST_WIDE_INT offset)
2919 struct ipcp_agg_lattice *aglat;
2920 struct ipa_agg_jf_item *item;
2921 int k;
2923 if (!plats->aggs || plats->aggs_contain_variable || plats->aggs_bottom)
2925 inter->release ();
2926 return;
2929 aglat = plats->aggs;
2930 FOR_EACH_VEC_ELT (*inter, k, item)
2932 bool found = false;
2933 if (!item->value)
2934 continue;
2935 while (aglat)
2937 if (aglat->offset - offset > item->offset)
2938 break;
2939 if (aglat->offset - offset == item->offset)
2941 gcc_checking_assert (item->value);
2942 if (values_equal_for_ipcp_p (item->value, aglat->values->value))
2943 found = true;
2944 break;
2946 aglat = aglat->next;
2948 if (!found)
2949 item->value = NULL_TREE;
2953 /* Copy agggregate replacement values of NODE (which is an IPA-CP clone) to the
2954 vector result while subtracting OFFSET from the individual value offsets. */
2956 static vec<ipa_agg_jf_item>
2957 agg_replacements_to_vector (struct cgraph_node *node, int index,
2958 HOST_WIDE_INT offset)
2960 struct ipa_agg_replacement_value *av;
2961 vec<ipa_agg_jf_item> res = vNULL;
2963 for (av = ipa_get_agg_replacements_for_node (node); av; av = av->next)
2964 if (av->index == index
2965 && (av->offset - offset) >= 0)
2967 struct ipa_agg_jf_item item;
2968 gcc_checking_assert (av->value);
2969 item.offset = av->offset - offset;
2970 item.value = av->value;
2971 res.safe_push (item);
2974 return res;
2977 /* Intersect all values in INTER with those that we have already scheduled to
2978 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
2979 (while subtracting OFFSET). */
2981 static void
2982 intersect_with_agg_replacements (struct cgraph_node *node, int index,
2983 vec<ipa_agg_jf_item> *inter,
2984 HOST_WIDE_INT offset)
2986 struct ipa_agg_replacement_value *srcvals;
2987 struct ipa_agg_jf_item *item;
2988 int i;
2990 srcvals = ipa_get_agg_replacements_for_node (node);
2991 if (!srcvals)
2993 inter->release ();
2994 return;
2997 FOR_EACH_VEC_ELT (*inter, i, item)
2999 struct ipa_agg_replacement_value *av;
3000 bool found = false;
3001 if (!item->value)
3002 continue;
3003 for (av = srcvals; av; av = av->next)
3005 gcc_checking_assert (av->value);
3006 if (av->index == index
3007 && av->offset - offset == item->offset)
3009 if (values_equal_for_ipcp_p (item->value, av->value))
3010 found = true;
3011 break;
3014 if (!found)
3015 item->value = NULL_TREE;
3019 /* Intersect values in INTER with aggregate values that come along edge CS to
3020 parameter number INDEX and return it. If INTER does not actually exist yet,
3021 copy all incoming values to it. If we determine we ended up with no values
3022 whatsoever, return a released vector. */
3024 static vec<ipa_agg_jf_item>
3025 intersect_aggregates_with_edge (struct cgraph_edge *cs, int index,
3026 vec<ipa_agg_jf_item> inter)
3028 struct ipa_jump_func *jfunc;
3029 jfunc = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), index);
3030 if (jfunc->type == IPA_JF_PASS_THROUGH
3031 && ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
3033 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
3034 int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
3036 if (caller_info->ipcp_orig_node)
3038 struct cgraph_node *orig_node = caller_info->ipcp_orig_node;
3039 struct ipcp_param_lattices *orig_plats;
3040 orig_plats = ipa_get_parm_lattices (IPA_NODE_REF (orig_node),
3041 src_idx);
3042 if (agg_pass_through_permissible_p (orig_plats, jfunc))
3044 if (!inter.exists ())
3045 inter = agg_replacements_to_vector (cs->caller, src_idx, 0);
3046 else
3047 intersect_with_agg_replacements (cs->caller, src_idx,
3048 &inter, 0);
3051 else
3053 struct ipcp_param_lattices *src_plats;
3054 src_plats = ipa_get_parm_lattices (caller_info, src_idx);
3055 if (agg_pass_through_permissible_p (src_plats, jfunc))
3057 /* Currently we do not produce clobber aggregate jump
3058 functions, adjust when we do. */
3059 gcc_checking_assert (!jfunc->agg.items);
3060 if (!inter.exists ())
3061 inter = copy_plats_to_inter (src_plats, 0);
3062 else
3063 intersect_with_plats (src_plats, &inter, 0);
3067 else if (jfunc->type == IPA_JF_ANCESTOR
3068 && ipa_get_jf_ancestor_agg_preserved (jfunc))
3070 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
3071 int src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
3072 struct ipcp_param_lattices *src_plats;
3073 HOST_WIDE_INT delta = ipa_get_jf_ancestor_offset (jfunc);
3075 if (caller_info->ipcp_orig_node)
3077 if (!inter.exists ())
3078 inter = agg_replacements_to_vector (cs->caller, src_idx, delta);
3079 else
3080 intersect_with_agg_replacements (cs->caller, src_idx, &inter,
3081 delta);
3083 else
3085 src_plats = ipa_get_parm_lattices (caller_info, src_idx);;
3086 /* Currently we do not produce clobber aggregate jump
3087 functions, adjust when we do. */
3088 gcc_checking_assert (!src_plats->aggs || !jfunc->agg.items);
3089 if (!inter.exists ())
3090 inter = copy_plats_to_inter (src_plats, delta);
3091 else
3092 intersect_with_plats (src_plats, &inter, delta);
3095 else if (jfunc->agg.items)
3097 struct ipa_agg_jf_item *item;
3098 int k;
3100 if (!inter.exists ())
3101 for (unsigned i = 0; i < jfunc->agg.items->length (); i++)
3102 inter.safe_push ((*jfunc->agg.items)[i]);
3103 else
3104 FOR_EACH_VEC_ELT (inter, k, item)
3106 int l = 0;
3107 bool found = false;;
3109 if (!item->value)
3110 continue;
3112 while ((unsigned) l < jfunc->agg.items->length ())
3114 struct ipa_agg_jf_item *ti;
3115 ti = &(*jfunc->agg.items)[l];
3116 if (ti->offset > item->offset)
3117 break;
3118 if (ti->offset == item->offset)
3120 gcc_checking_assert (ti->value);
3121 if (values_equal_for_ipcp_p (item->value,
3122 ti->value))
3123 found = true;
3124 break;
3126 l++;
3128 if (!found)
3129 item->value = NULL;
3132 else
3134 inter.release ();
3135 return vec<ipa_agg_jf_item>();
3137 return inter;
3140 /* Look at edges in CALLERS and collect all known aggregate values that arrive
3141 from all of them. */
3143 static struct ipa_agg_replacement_value *
3144 find_aggregate_values_for_callers_subset (struct cgraph_node *node,
3145 vec<cgraph_edge *> callers)
3147 struct ipa_node_params *dest_info = IPA_NODE_REF (node);
3148 struct ipa_agg_replacement_value *res = NULL;
3149 struct cgraph_edge *cs;
3150 int i, j, count = ipa_get_param_count (dest_info);
3152 FOR_EACH_VEC_ELT (callers, j, cs)
3154 int c = ipa_get_cs_argument_count (IPA_EDGE_REF (cs));
3155 if (c < count)
3156 count = c;
3159 for (i = 0; i < count ; i++)
3161 struct cgraph_edge *cs;
3162 vec<ipa_agg_jf_item> inter = vNULL;
3163 struct ipa_agg_jf_item *item;
3164 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (dest_info, i);
3165 int j;
3167 /* Among other things, the following check should deal with all by_ref
3168 mismatches. */
3169 if (plats->aggs_bottom)
3170 continue;
3172 FOR_EACH_VEC_ELT (callers, j, cs)
3174 inter = intersect_aggregates_with_edge (cs, i, inter);
3176 if (!inter.exists ())
3177 goto next_param;
3180 FOR_EACH_VEC_ELT (inter, j, item)
3182 struct ipa_agg_replacement_value *v;
3184 if (!item->value)
3185 continue;
3187 v = ggc_alloc<ipa_agg_replacement_value> ();
3188 v->index = i;
3189 v->offset = item->offset;
3190 v->value = item->value;
3191 v->by_ref = plats->aggs_by_ref;
3192 v->next = res;
3193 res = v;
3196 next_param:
3197 if (inter.exists ())
3198 inter.release ();
3200 return res;
3203 /* Turn KNOWN_AGGS into a list of aggreate replacement values. */
3205 static struct ipa_agg_replacement_value *
3206 known_aggs_to_agg_replacement_list (vec<ipa_agg_jump_function> known_aggs)
3208 struct ipa_agg_replacement_value *res = NULL;
3209 struct ipa_agg_jump_function *aggjf;
3210 struct ipa_agg_jf_item *item;
3211 int i, j;
3213 FOR_EACH_VEC_ELT (known_aggs, i, aggjf)
3214 FOR_EACH_VEC_SAFE_ELT (aggjf->items, j, item)
3216 struct ipa_agg_replacement_value *v;
3217 v = ggc_alloc<ipa_agg_replacement_value> ();
3218 v->index = i;
3219 v->offset = item->offset;
3220 v->value = item->value;
3221 v->by_ref = aggjf->by_ref;
3222 v->next = res;
3223 res = v;
3225 return res;
3228 /* Determine whether CS also brings all scalar values that the NODE is
3229 specialized for. */
3231 static bool
3232 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge *cs,
3233 struct cgraph_node *node)
3235 struct ipa_node_params *dest_info = IPA_NODE_REF (node);
3236 int count = ipa_get_param_count (dest_info);
3237 struct ipa_node_params *caller_info;
3238 struct ipa_edge_args *args;
3239 int i;
3241 caller_info = IPA_NODE_REF (cs->caller);
3242 args = IPA_EDGE_REF (cs);
3243 for (i = 0; i < count; i++)
3245 struct ipa_jump_func *jump_func;
3246 tree val, t;
3248 val = dest_info->known_vals[i];
3249 if (!val)
3250 continue;
3252 if (i >= ipa_get_cs_argument_count (args))
3253 return false;
3254 jump_func = ipa_get_ith_jump_func (args, i);
3255 t = ipa_value_from_jfunc (caller_info, jump_func);
3256 if (!t || !values_equal_for_ipcp_p (val, t))
3257 return false;
3259 return true;
3262 /* Determine whether CS also brings all aggregate values that NODE is
3263 specialized for. */
3264 static bool
3265 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge *cs,
3266 struct cgraph_node *node)
3268 struct ipa_node_params *orig_caller_info = IPA_NODE_REF (cs->caller);
3269 struct ipa_node_params *orig_node_info;
3270 struct ipa_agg_replacement_value *aggval;
3271 int i, ec, count;
3273 aggval = ipa_get_agg_replacements_for_node (node);
3274 if (!aggval)
3275 return true;
3277 count = ipa_get_param_count (IPA_NODE_REF (node));
3278 ec = ipa_get_cs_argument_count (IPA_EDGE_REF (cs));
3279 if (ec < count)
3280 for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next)
3281 if (aggval->index >= ec)
3282 return false;
3284 orig_node_info = IPA_NODE_REF (IPA_NODE_REF (node)->ipcp_orig_node);
3285 if (orig_caller_info->ipcp_orig_node)
3286 orig_caller_info = IPA_NODE_REF (orig_caller_info->ipcp_orig_node);
3288 for (i = 0; i < count; i++)
3290 static vec<ipa_agg_jf_item> values = vec<ipa_agg_jf_item>();
3291 struct ipcp_param_lattices *plats;
3292 bool interesting = false;
3293 for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next)
3294 if (aggval->index == i)
3296 interesting = true;
3297 break;
3299 if (!interesting)
3300 continue;
3302 plats = ipa_get_parm_lattices (orig_node_info, aggval->index);
3303 if (plats->aggs_bottom)
3304 return false;
3306 values = intersect_aggregates_with_edge (cs, i, values);
3307 if (!values.exists ())
3308 return false;
3310 for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next)
3311 if (aggval->index == i)
3313 struct ipa_agg_jf_item *item;
3314 int j;
3315 bool found = false;
3316 FOR_EACH_VEC_ELT (values, j, item)
3317 if (item->value
3318 && item->offset == av->offset
3319 && values_equal_for_ipcp_p (item->value, av->value))
3321 found = true;
3322 break;
3324 if (!found)
3326 values.release ();
3327 return false;
3331 return true;
3334 /* Given an original NODE and a VAL for which we have already created a
3335 specialized clone, look whether there are incoming edges that still lead
3336 into the old node but now also bring the requested value and also conform to
3337 all other criteria such that they can be redirected the the special node.
3338 This function can therefore redirect the final edge in a SCC. */
3340 static void
3341 perhaps_add_new_callers (struct cgraph_node *node, struct ipcp_value *val)
3343 struct ipcp_value_source *src;
3344 gcov_type redirected_sum = 0;
3346 for (src = val->sources; src; src = src->next)
3348 struct cgraph_edge *cs = src->cs;
3349 while (cs)
3351 enum availability availability;
3352 struct cgraph_node *dst = cs->callee->function_symbol (&availability);
3353 if ((dst == node || IPA_NODE_REF (dst)->is_all_contexts_clone)
3354 && availability > AVAIL_INTERPOSABLE
3355 && cgraph_edge_brings_value_p (cs, src))
3357 if (cgraph_edge_brings_all_scalars_for_node (cs, val->spec_node)
3358 && cgraph_edge_brings_all_agg_vals_for_node (cs,
3359 val->spec_node))
3361 if (dump_file)
3362 fprintf (dump_file, " - adding an extra caller %s/%i"
3363 " of %s/%i\n",
3364 xstrdup (cs->caller->name ()),
3365 cs->caller->order,
3366 xstrdup (val->spec_node->name ()),
3367 val->spec_node->order);
3369 cgraph_redirect_edge_callee (cs, val->spec_node);
3370 redirected_sum += cs->count;
3373 cs = get_next_cgraph_edge_clone (cs);
3377 if (redirected_sum)
3378 update_specialized_profile (val->spec_node, node, redirected_sum);
3382 /* Copy KNOWN_BINFOS to KNOWN_VALS. */
3384 static void
3385 move_binfos_to_values (vec<tree> known_vals,
3386 vec<tree> known_binfos)
3388 tree t;
3389 int i;
3391 for (i = 0; known_binfos.iterate (i, &t); i++)
3392 if (t)
3393 known_vals[i] = t;
3396 /* Return true if there is a replacement equivalent to VALUE, INDEX and OFFSET
3397 among those in the AGGVALS list. */
3399 DEBUG_FUNCTION bool
3400 ipcp_val_in_agg_replacements_p (struct ipa_agg_replacement_value *aggvals,
3401 int index, HOST_WIDE_INT offset, tree value)
3403 while (aggvals)
3405 if (aggvals->index == index
3406 && aggvals->offset == offset
3407 && values_equal_for_ipcp_p (aggvals->value, value))
3408 return true;
3409 aggvals = aggvals->next;
3411 return false;
3414 /* Decide wheter to create a special version of NODE for value VAL of parameter
3415 at the given INDEX. If OFFSET is -1, the value is for the parameter itself,
3416 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS,
3417 KNOWN_BINFOS and KNOWN_AGGS describe the other already known values. */
3419 static bool
3420 decide_about_value (struct cgraph_node *node, int index, HOST_WIDE_INT offset,
3421 struct ipcp_value *val, vec<tree> known_csts,
3422 vec<tree> known_binfos)
3424 struct ipa_agg_replacement_value *aggvals;
3425 int freq_sum, caller_count;
3426 gcov_type count_sum;
3427 vec<cgraph_edge *> callers;
3428 vec<tree> kv;
3430 if (val->spec_node)
3432 perhaps_add_new_callers (node, val);
3433 return false;
3435 else if (val->local_size_cost + overall_size > max_new_size)
3437 if (dump_file && (dump_flags & TDF_DETAILS))
3438 fprintf (dump_file, " Ignoring candidate value because "
3439 "max_new_size would be reached with %li.\n",
3440 val->local_size_cost + overall_size);
3441 return false;
3443 else if (!get_info_about_necessary_edges (val, &freq_sum, &count_sum,
3444 &caller_count))
3445 return false;
3447 if (dump_file && (dump_flags & TDF_DETAILS))
3449 fprintf (dump_file, " - considering value ");
3450 print_ipcp_constant_value (dump_file, val->value);
3451 fprintf (dump_file, " for ");
3452 ipa_dump_param (dump_file, IPA_NODE_REF (node), index);
3453 if (offset != -1)
3454 fprintf (dump_file, ", offset: " HOST_WIDE_INT_PRINT_DEC, offset);
3455 fprintf (dump_file, " (caller_count: %i)\n", caller_count);
3458 if (!good_cloning_opportunity_p (node, val->local_time_benefit,
3459 freq_sum, count_sum,
3460 val->local_size_cost)
3461 && !good_cloning_opportunity_p (node,
3462 val->local_time_benefit
3463 + val->prop_time_benefit,
3464 freq_sum, count_sum,
3465 val->local_size_cost
3466 + val->prop_size_cost))
3467 return false;
3469 if (dump_file)
3470 fprintf (dump_file, " Creating a specialized node of %s/%i.\n",
3471 node->name (), node->order);
3473 callers = gather_edges_for_value (val, caller_count);
3474 kv = known_csts.copy ();
3475 move_binfos_to_values (kv, known_binfos);
3476 if (offset == -1)
3477 kv[index] = val->value;
3478 find_more_scalar_values_for_callers_subset (node, kv, callers);
3479 aggvals = find_aggregate_values_for_callers_subset (node, callers);
3480 gcc_checking_assert (offset == -1
3481 || ipcp_val_in_agg_replacements_p (aggvals, index,
3482 offset, val->value));
3483 val->spec_node = create_specialized_node (node, kv, aggvals, callers);
3484 overall_size += val->local_size_cost;
3486 /* TODO: If for some lattice there is only one other known value
3487 left, make a special node for it too. */
3489 return true;
3492 /* Decide whether and what specialized clones of NODE should be created. */
3494 static bool
3495 decide_whether_version_node (struct cgraph_node *node)
3497 struct ipa_node_params *info = IPA_NODE_REF (node);
3498 int i, count = ipa_get_param_count (info);
3499 vec<tree> known_csts, known_binfos;
3500 vec<ipa_agg_jump_function> known_aggs = vNULL;
3501 bool ret = false;
3503 if (count == 0)
3504 return false;
3506 if (dump_file && (dump_flags & TDF_DETAILS))
3507 fprintf (dump_file, "\nEvaluating opportunities for %s/%i.\n",
3508 node->name (), node->order);
3510 gather_context_independent_values (info, &known_csts, &known_binfos,
3511 info->do_clone_for_all_contexts ? &known_aggs
3512 : NULL, NULL);
3514 for (i = 0; i < count ;i++)
3516 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
3517 struct ipcp_lattice *lat = &plats->itself;
3518 struct ipcp_value *val;
3520 if (!lat->bottom
3521 && !known_csts[i]
3522 && !known_binfos[i])
3523 for (val = lat->values; val; val = val->next)
3524 ret |= decide_about_value (node, i, -1, val, known_csts,
3525 known_binfos);
3527 if (!plats->aggs_bottom)
3529 struct ipcp_agg_lattice *aglat;
3530 struct ipcp_value *val;
3531 for (aglat = plats->aggs; aglat; aglat = aglat->next)
3532 if (!aglat->bottom && aglat->values
3533 /* If the following is false, the one value is in
3534 known_aggs. */
3535 && (plats->aggs_contain_variable
3536 || !ipa_lat_is_single_const (aglat)))
3537 for (val = aglat->values; val; val = val->next)
3538 ret |= decide_about_value (node, i, aglat->offset, val,
3539 known_csts, known_binfos);
3541 info = IPA_NODE_REF (node);
3544 if (info->do_clone_for_all_contexts)
3546 struct cgraph_node *clone;
3547 vec<cgraph_edge *> callers;
3549 if (dump_file)
3550 fprintf (dump_file, " - Creating a specialized node of %s/%i "
3551 "for all known contexts.\n", node->name (),
3552 node->order);
3554 callers = node->collect_callers ();
3555 move_binfos_to_values (known_csts, known_binfos);
3556 clone = create_specialized_node (node, known_csts,
3557 known_aggs_to_agg_replacement_list (known_aggs),
3558 callers);
3559 info = IPA_NODE_REF (node);
3560 info->do_clone_for_all_contexts = false;
3561 IPA_NODE_REF (clone)->is_all_contexts_clone = true;
3562 for (i = 0; i < count ; i++)
3563 vec_free (known_aggs[i].items);
3564 known_aggs.release ();
3565 ret = true;
3567 else
3568 known_csts.release ();
3570 known_binfos.release ();
3571 return ret;
3574 /* Transitively mark all callees of NODE within the same SCC as not dead. */
3576 static void
3577 spread_undeadness (struct cgraph_node *node)
3579 struct cgraph_edge *cs;
3581 for (cs = node->callees; cs; cs = cs->next_callee)
3582 if (ipa_edge_within_scc (cs))
3584 struct cgraph_node *callee;
3585 struct ipa_node_params *info;
3587 callee = cs->callee->function_symbol (NULL);
3588 info = IPA_NODE_REF (callee);
3590 if (info->node_dead)
3592 info->node_dead = 0;
3593 spread_undeadness (callee);
3598 /* Return true if NODE has a caller from outside of its SCC that is not
3599 dead. Worker callback for cgraph_for_node_and_aliases. */
3601 static bool
3602 has_undead_caller_from_outside_scc_p (struct cgraph_node *node,
3603 void *data ATTRIBUTE_UNUSED)
3605 struct cgraph_edge *cs;
3607 for (cs = node->callers; cs; cs = cs->next_caller)
3608 if (cs->caller->thunk.thunk_p
3609 && cs->caller->call_for_symbol_thunks_and_aliases
3610 (has_undead_caller_from_outside_scc_p, NULL, true))
3611 return true;
3612 else if (!ipa_edge_within_scc (cs)
3613 && !IPA_NODE_REF (cs->caller)->node_dead)
3614 return true;
3615 return false;
3619 /* Identify nodes within the same SCC as NODE which are no longer needed
3620 because of new clones and will be removed as unreachable. */
3622 static void
3623 identify_dead_nodes (struct cgraph_node *node)
3625 struct cgraph_node *v;
3626 for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
3627 if (v->will_be_removed_from_program_if_no_direct_calls_p ()
3628 && !v->call_for_symbol_thunks_and_aliases
3629 (has_undead_caller_from_outside_scc_p, NULL, true))
3630 IPA_NODE_REF (v)->node_dead = 1;
3632 for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
3633 if (!IPA_NODE_REF (v)->node_dead)
3634 spread_undeadness (v);
3636 if (dump_file && (dump_flags & TDF_DETAILS))
3638 for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
3639 if (IPA_NODE_REF (v)->node_dead)
3640 fprintf (dump_file, " Marking node as dead: %s/%i.\n",
3641 v->name (), v->order);
3645 /* The decision stage. Iterate over the topological order of call graph nodes
3646 TOPO and make specialized clones if deemed beneficial. */
3648 static void
3649 ipcp_decision_stage (struct topo_info *topo)
3651 int i;
3653 if (dump_file)
3654 fprintf (dump_file, "\nIPA decision stage:\n\n");
3656 for (i = topo->nnodes - 1; i >= 0; i--)
3658 struct cgraph_node *node = topo->order[i];
3659 bool change = false, iterate = true;
3661 while (iterate)
3663 struct cgraph_node *v;
3664 iterate = false;
3665 for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
3666 if (v->has_gimple_body_p ()
3667 && ipcp_versionable_function_p (v))
3668 iterate |= decide_whether_version_node (v);
3670 change |= iterate;
3672 if (change)
3673 identify_dead_nodes (node);
3677 /* The IPCP driver. */
3679 static unsigned int
3680 ipcp_driver (void)
3682 struct cgraph_2edge_hook_list *edge_duplication_hook_holder;
3683 struct cgraph_edge_hook_list *edge_removal_hook_holder;
3684 struct topo_info topo;
3686 ipa_check_create_node_params ();
3687 ipa_check_create_edge_args ();
3688 grow_edge_clone_vectors ();
3689 edge_duplication_hook_holder =
3690 cgraph_add_edge_duplication_hook (&ipcp_edge_duplication_hook, NULL);
3691 edge_removal_hook_holder =
3692 cgraph_add_edge_removal_hook (&ipcp_edge_removal_hook, NULL);
3694 ipcp_values_pool = create_alloc_pool ("IPA-CP values",
3695 sizeof (struct ipcp_value), 32);
3696 ipcp_sources_pool = create_alloc_pool ("IPA-CP value sources",
3697 sizeof (struct ipcp_value_source), 64);
3698 ipcp_agg_lattice_pool = create_alloc_pool ("IPA_CP aggregate lattices",
3699 sizeof (struct ipcp_agg_lattice),
3700 32);
3701 if (dump_file)
3703 fprintf (dump_file, "\nIPA structures before propagation:\n");
3704 if (dump_flags & TDF_DETAILS)
3705 ipa_print_all_params (dump_file);
3706 ipa_print_all_jump_functions (dump_file);
3709 /* Topological sort. */
3710 build_toporder_info (&topo);
3711 /* Do the interprocedural propagation. */
3712 ipcp_propagate_stage (&topo);
3713 /* Decide what constant propagation and cloning should be performed. */
3714 ipcp_decision_stage (&topo);
3716 /* Free all IPCP structures. */
3717 free_toporder_info (&topo);
3718 next_edge_clone.release ();
3719 cgraph_remove_edge_removal_hook (edge_removal_hook_holder);
3720 cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder);
3721 ipa_free_all_structures_after_ipa_cp ();
3722 if (dump_file)
3723 fprintf (dump_file, "\nIPA constant propagation end\n");
3724 return 0;
3727 /* Initialization and computation of IPCP data structures. This is the initial
3728 intraprocedural analysis of functions, which gathers information to be
3729 propagated later on. */
3731 static void
3732 ipcp_generate_summary (void)
3734 struct cgraph_node *node;
3736 if (dump_file)
3737 fprintf (dump_file, "\nIPA constant propagation start:\n");
3738 ipa_register_cgraph_hooks ();
3740 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
3742 node->local.versionable
3743 = tree_versionable_function_p (node->decl);
3744 ipa_analyze_node (node);
3748 /* Write ipcp summary for nodes in SET. */
3750 static void
3751 ipcp_write_summary (void)
3753 ipa_prop_write_jump_functions ();
3756 /* Read ipcp summary. */
3758 static void
3759 ipcp_read_summary (void)
3761 ipa_prop_read_jump_functions ();
3764 namespace {
3766 const pass_data pass_data_ipa_cp =
3768 IPA_PASS, /* type */
3769 "cp", /* name */
3770 OPTGROUP_NONE, /* optinfo_flags */
3771 TV_IPA_CONSTANT_PROP, /* tv_id */
3772 0, /* properties_required */
3773 0, /* properties_provided */
3774 0, /* properties_destroyed */
3775 0, /* todo_flags_start */
3776 ( TODO_dump_symtab | TODO_remove_functions ), /* todo_flags_finish */
3779 class pass_ipa_cp : public ipa_opt_pass_d
3781 public:
3782 pass_ipa_cp (gcc::context *ctxt)
3783 : ipa_opt_pass_d (pass_data_ipa_cp, ctxt,
3784 ipcp_generate_summary, /* generate_summary */
3785 ipcp_write_summary, /* write_summary */
3786 ipcp_read_summary, /* read_summary */
3787 ipa_prop_write_all_agg_replacement, /*
3788 write_optimization_summary */
3789 ipa_prop_read_all_agg_replacement, /*
3790 read_optimization_summary */
3791 NULL, /* stmt_fixup */
3792 0, /* function_transform_todo_flags_start */
3793 ipcp_transform_function, /* function_transform */
3794 NULL) /* variable_transform */
3797 /* opt_pass methods: */
3798 virtual bool gate (function *)
3800 /* FIXME: We should remove the optimize check after we ensure we never run
3801 IPA passes when not optimizing. */
3802 return flag_ipa_cp && optimize;
3805 virtual unsigned int execute (function *) { return ipcp_driver (); }
3807 }; // class pass_ipa_cp
3809 } // anon namespace
3811 ipa_opt_pass_d *
3812 make_pass_ipa_cp (gcc::context *ctxt)
3814 return new pass_ipa_cp (ctxt);