2013-11-13 Christophe Lyon <christophe.lyon@linaro.org>
[official-gcc.git] / gcc / ipa-cp.c
blob72a96d22c17b14ba89031fe6207a15e21b661dac
1 /* Interprocedural constant propagation
2 Copyright (C) 2005-2013 Free Software Foundation, Inc.
4 Contributed by Razya Ladelsky <RAZYA@il.ibm.com> and Martin Jambor
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.h"
108 #include "target.h"
109 #include "ipa-prop.h"
110 #include "bitmap.h"
111 #include "tree-pass.h"
112 #include "flags.h"
113 #include "diagnostic.h"
114 #include "tree-pretty-print.h"
115 #include "tree-inline.h"
116 #include "params.h"
117 #include "ipa-inline.h"
118 #include "ipa-utils.h"
120 struct ipcp_value;
122 /* Describes a particular source for an IPA-CP value. */
124 struct ipcp_value_source
126 /* Aggregate offset of the source, negative if the source is scalar value of
127 the argument itself. */
128 HOST_WIDE_INT offset;
129 /* The incoming edge that brought the value. */
130 struct cgraph_edge *cs;
131 /* If the jump function that resulted into his value was a pass-through or an
132 ancestor, this is the ipcp_value of the caller from which the described
133 value has been derived. Otherwise it is NULL. */
134 struct ipcp_value *val;
135 /* Next pointer in a linked list of sources of a value. */
136 struct ipcp_value_source *next;
137 /* If the jump function that resulted into his value was a pass-through or an
138 ancestor, this is the index of the parameter of the caller the jump
139 function references. */
140 int index;
143 /* Describes one particular value stored in struct ipcp_lattice. */
145 struct ipcp_value
147 /* The actual value for the given parameter. This is either an IPA invariant
148 or a TREE_BINFO describing a type that can be used for
149 devirtualization. */
150 tree value;
151 /* The list of sources from which this value originates. */
152 struct ipcp_value_source *sources;
153 /* Next pointers in a linked list of all values in a lattice. */
154 struct ipcp_value *next;
155 /* Next pointers in a linked list of values in a strongly connected component
156 of values. */
157 struct ipcp_value *scc_next;
158 /* Next pointers in a linked list of SCCs of values sorted topologically
159 according their sources. */
160 struct ipcp_value *topo_next;
161 /* A specialized node created for this value, NULL if none has been (so far)
162 created. */
163 struct cgraph_node *spec_node;
164 /* Depth first search number and low link for topological sorting of
165 values. */
166 int dfs, low_link;
167 /* Time benefit and size cost that specializing the function for this value
168 would bring about in this function alone. */
169 int local_time_benefit, local_size_cost;
170 /* Time benefit and size cost that specializing the function for this value
171 can bring about in it's callees (transitively). */
172 int prop_time_benefit, prop_size_cost;
173 /* True if this valye is currently on the topo-sort stack. */
174 bool on_stack;
177 /* Lattice describing potential values of a formal parameter of a function, or
178 a part of an aggreagate. TOP is represented by a lattice with zero values
179 and with contains_variable and bottom flags cleared. BOTTOM is represented
180 by a lattice with the bottom flag set. In that case, values and
181 contains_variable flag should be disregarded. */
183 struct ipcp_lattice
185 /* The list of known values and types in this lattice. Note that values are
186 not deallocated if a lattice is set to bottom because there may be value
187 sources referencing them. */
188 struct ipcp_value *values;
189 /* Number of known values and types in this lattice. */
190 int values_count;
191 /* The lattice contains a variable component (in addition to values). */
192 bool contains_variable;
193 /* The value of the lattice is bottom (i.e. variable and unusable for any
194 propagation). */
195 bool bottom;
198 /* Lattice with an offset to describe a part of an aggregate. */
200 struct ipcp_agg_lattice : public ipcp_lattice
202 /* Offset that is being described by this lattice. */
203 HOST_WIDE_INT offset;
204 /* Size so that we don't have to re-compute it every time we traverse the
205 list. Must correspond to TYPE_SIZE of all lat values. */
206 HOST_WIDE_INT size;
207 /* Next element of the linked list. */
208 struct ipcp_agg_lattice *next;
211 /* Structure containing lattices for a parameter itself and for pieces of
212 aggregates that are passed in the parameter or by a reference in a parameter
213 plus some other useful flags. */
215 struct ipcp_param_lattices
217 /* Lattice describing the value of the parameter itself. */
218 struct ipcp_lattice itself;
219 /* Lattices describing aggregate parts. */
220 struct ipcp_agg_lattice *aggs;
221 /* Number of aggregate lattices */
222 int aggs_count;
223 /* True if aggregate data were passed by reference (as opposed to by
224 value). */
225 bool aggs_by_ref;
226 /* All aggregate lattices contain a variable component (in addition to
227 values). */
228 bool aggs_contain_variable;
229 /* The value of all aggregate lattices is bottom (i.e. variable and unusable
230 for any propagation). */
231 bool aggs_bottom;
233 /* There is a virtual call based on this parameter. */
234 bool virt_call;
237 /* Allocation pools for values and their sources in ipa-cp. */
239 alloc_pool ipcp_values_pool;
240 alloc_pool ipcp_sources_pool;
241 alloc_pool ipcp_agg_lattice_pool;
243 /* Maximal count found in program. */
245 static gcov_type max_count;
247 /* Original overall size of the program. */
249 static long overall_size, max_new_size;
251 /* Head of the linked list of topologically sorted values. */
253 static struct ipcp_value *values_topo;
255 /* Return the param lattices structure corresponding to the Ith formal
256 parameter of the function described by INFO. */
257 static inline struct ipcp_param_lattices *
258 ipa_get_parm_lattices (struct ipa_node_params *info, int i)
260 gcc_assert (i >= 0 && i < ipa_get_param_count (info));
261 gcc_checking_assert (!info->ipcp_orig_node);
262 gcc_checking_assert (info->lattices);
263 return &(info->lattices[i]);
266 /* Return the lattice corresponding to the scalar value of the Ith formal
267 parameter of the function described by INFO. */
268 static inline struct ipcp_lattice *
269 ipa_get_scalar_lat (struct ipa_node_params *info, int i)
271 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
272 return &plats->itself;
275 /* Return whether LAT is a lattice with a single constant and without an
276 undefined value. */
278 static inline bool
279 ipa_lat_is_single_const (struct ipcp_lattice *lat)
281 if (lat->bottom
282 || lat->contains_variable
283 || lat->values_count != 1)
284 return false;
285 else
286 return true;
289 /* Print V which is extracted from a value in a lattice to F. */
291 static void
292 print_ipcp_constant_value (FILE * f, tree v)
294 if (TREE_CODE (v) == TREE_BINFO)
296 fprintf (f, "BINFO ");
297 print_generic_expr (f, BINFO_TYPE (v), 0);
299 else if (TREE_CODE (v) == ADDR_EXPR
300 && TREE_CODE (TREE_OPERAND (v, 0)) == CONST_DECL)
302 fprintf (f, "& ");
303 print_generic_expr (f, DECL_INITIAL (TREE_OPERAND (v, 0)), 0);
305 else
306 print_generic_expr (f, v, 0);
309 /* Print a lattice LAT to F. */
311 static void
312 print_lattice (FILE * f, struct ipcp_lattice *lat,
313 bool dump_sources, bool dump_benefits)
315 struct ipcp_value *val;
316 bool prev = false;
318 if (lat->bottom)
320 fprintf (f, "BOTTOM\n");
321 return;
324 if (!lat->values_count && !lat->contains_variable)
326 fprintf (f, "TOP\n");
327 return;
330 if (lat->contains_variable)
332 fprintf (f, "VARIABLE");
333 prev = true;
334 if (dump_benefits)
335 fprintf (f, "\n");
338 for (val = lat->values; val; val = val->next)
340 if (dump_benefits && prev)
341 fprintf (f, " ");
342 else if (!dump_benefits && prev)
343 fprintf (f, ", ");
344 else
345 prev = true;
347 print_ipcp_constant_value (f, val->value);
349 if (dump_sources)
351 struct ipcp_value_source *s;
353 fprintf (f, " [from:");
354 for (s = val->sources; s; s = s->next)
355 fprintf (f, " %i(%i)", s->cs->caller->order,
356 s->cs->frequency);
357 fprintf (f, "]");
360 if (dump_benefits)
361 fprintf (f, " [loc_time: %i, loc_size: %i, "
362 "prop_time: %i, prop_size: %i]\n",
363 val->local_time_benefit, val->local_size_cost,
364 val->prop_time_benefit, val->prop_size_cost);
366 if (!dump_benefits)
367 fprintf (f, "\n");
370 /* Print all ipcp_lattices of all functions to F. */
372 static void
373 print_all_lattices (FILE * f, bool dump_sources, bool dump_benefits)
375 struct cgraph_node *node;
376 int i, count;
378 fprintf (f, "\nLattices:\n");
379 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
381 struct ipa_node_params *info;
383 info = IPA_NODE_REF (node);
384 fprintf (f, " Node: %s/%i:\n", cgraph_node_name (node),
385 node->order);
386 count = ipa_get_param_count (info);
387 for (i = 0; i < count; i++)
389 struct ipcp_agg_lattice *aglat;
390 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
391 fprintf (f, " param [%d]: ", i);
392 print_lattice (f, &plats->itself, dump_sources, dump_benefits);
394 if (plats->virt_call)
395 fprintf (f, " virt_call flag set\n");
397 if (plats->aggs_bottom)
399 fprintf (f, " AGGS BOTTOM\n");
400 continue;
402 if (plats->aggs_contain_variable)
403 fprintf (f, " AGGS VARIABLE\n");
404 for (aglat = plats->aggs; aglat; aglat = aglat->next)
406 fprintf (f, " %soffset " HOST_WIDE_INT_PRINT_DEC ": ",
407 plats->aggs_by_ref ? "ref " : "", aglat->offset);
408 print_lattice (f, aglat, dump_sources, dump_benefits);
414 /* Determine whether it is at all technically possible to create clones of NODE
415 and store this information in the ipa_node_params structure associated
416 with NODE. */
418 static void
419 determine_versionability (struct cgraph_node *node)
421 const char *reason = NULL;
423 /* There are a number of generic reasons functions cannot be versioned. We
424 also cannot remove parameters if there are type attributes such as fnspec
425 present. */
426 if (node->alias || node->thunk.thunk_p)
427 reason = "alias or thunk";
428 else if (!node->local.versionable)
429 reason = "not a tree_versionable_function";
430 else if (cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE)
431 reason = "insufficient body availability";
433 if (reason && dump_file && !node->alias && !node->thunk.thunk_p)
434 fprintf (dump_file, "Function %s/%i is not versionable, reason: %s.\n",
435 cgraph_node_name (node), node->order, reason);
437 node->local.versionable = (reason == NULL);
440 /* Return true if it is at all technically possible to create clones of a
441 NODE. */
443 static bool
444 ipcp_versionable_function_p (struct cgraph_node *node)
446 return node->local.versionable;
449 /* Structure holding accumulated information about callers of a node. */
451 struct caller_statistics
453 gcov_type count_sum;
454 int n_calls, n_hot_calls, freq_sum;
457 /* Initialize fields of STAT to zeroes. */
459 static inline void
460 init_caller_stats (struct caller_statistics *stats)
462 stats->count_sum = 0;
463 stats->n_calls = 0;
464 stats->n_hot_calls = 0;
465 stats->freq_sum = 0;
468 /* Worker callback of cgraph_for_node_and_aliases accumulating statistics of
469 non-thunk incoming edges to NODE. */
471 static bool
472 gather_caller_stats (struct cgraph_node *node, void *data)
474 struct caller_statistics *stats = (struct caller_statistics *) data;
475 struct cgraph_edge *cs;
477 for (cs = node->callers; cs; cs = cs->next_caller)
478 if (cs->caller->thunk.thunk_p)
479 cgraph_for_node_and_aliases (cs->caller, gather_caller_stats,
480 stats, false);
481 else
483 stats->count_sum += cs->count;
484 stats->freq_sum += cs->frequency;
485 stats->n_calls++;
486 if (cgraph_maybe_hot_edge_p (cs))
487 stats->n_hot_calls ++;
489 return false;
493 /* Return true if this NODE is viable candidate for cloning. */
495 static bool
496 ipcp_cloning_candidate_p (struct cgraph_node *node)
498 struct caller_statistics stats;
500 gcc_checking_assert (cgraph_function_with_gimple_body_p (node));
502 if (!flag_ipa_cp_clone)
504 if (dump_file)
505 fprintf (dump_file, "Not considering %s for cloning; "
506 "-fipa-cp-clone disabled.\n",
507 cgraph_node_name (node));
508 return false;
511 if (!optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node->decl)))
513 if (dump_file)
514 fprintf (dump_file, "Not considering %s for cloning; "
515 "optimizing it for size.\n",
516 cgraph_node_name (node));
517 return false;
520 init_caller_stats (&stats);
521 cgraph_for_node_and_aliases (node, gather_caller_stats, &stats, false);
523 if (inline_summary (node)->self_size < stats.n_calls)
525 if (dump_file)
526 fprintf (dump_file, "Considering %s for cloning; code might shrink.\n",
527 cgraph_node_name (node));
528 return true;
531 /* When profile is available and function is hot, propagate into it even if
532 calls seems cold; constant propagation can improve function's speed
533 significantly. */
534 if (max_count)
536 if (stats.count_sum > node->count * 90 / 100)
538 if (dump_file)
539 fprintf (dump_file, "Considering %s for cloning; "
540 "usually called directly.\n",
541 cgraph_node_name (node));
542 return true;
545 if (!stats.n_hot_calls)
547 if (dump_file)
548 fprintf (dump_file, "Not considering %s for cloning; no hot calls.\n",
549 cgraph_node_name (node));
550 return false;
552 if (dump_file)
553 fprintf (dump_file, "Considering %s for cloning.\n",
554 cgraph_node_name (node));
555 return true;
558 /* Arrays representing a topological ordering of call graph nodes and a stack
559 of noes used during constant propagation. */
561 struct topo_info
563 struct cgraph_node **order;
564 struct cgraph_node **stack;
565 int nnodes, stack_top;
568 /* Allocate the arrays in TOPO and topologically sort the nodes into order. */
570 static void
571 build_toporder_info (struct topo_info *topo)
573 topo->order = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
574 topo->stack = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
575 topo->stack_top = 0;
576 topo->nnodes = ipa_reduced_postorder (topo->order, true, true, NULL);
579 /* Free information about strongly connected components and the arrays in
580 TOPO. */
582 static void
583 free_toporder_info (struct topo_info *topo)
585 ipa_free_postorder_info ();
586 free (topo->order);
587 free (topo->stack);
590 /* Add NODE to the stack in TOPO, unless it is already there. */
592 static inline void
593 push_node_to_stack (struct topo_info *topo, struct cgraph_node *node)
595 struct ipa_node_params *info = IPA_NODE_REF (node);
596 if (info->node_enqueued)
597 return;
598 info->node_enqueued = 1;
599 topo->stack[topo->stack_top++] = node;
602 /* Pop a node from the stack in TOPO and return it or return NULL if the stack
603 is empty. */
605 static struct cgraph_node *
606 pop_node_from_stack (struct topo_info *topo)
608 if (topo->stack_top)
610 struct cgraph_node *node;
611 topo->stack_top--;
612 node = topo->stack[topo->stack_top];
613 IPA_NODE_REF (node)->node_enqueued = 0;
614 return node;
616 else
617 return NULL;
620 /* Set lattice LAT to bottom and return true if it previously was not set as
621 such. */
623 static inline bool
624 set_lattice_to_bottom (struct ipcp_lattice *lat)
626 bool ret = !lat->bottom;
627 lat->bottom = true;
628 return ret;
631 /* Mark lattice as containing an unknown value and return true if it previously
632 was not marked as such. */
634 static inline bool
635 set_lattice_contains_variable (struct ipcp_lattice *lat)
637 bool ret = !lat->contains_variable;
638 lat->contains_variable = true;
639 return ret;
642 /* Set all aggegate lattices in PLATS to bottom and return true if they were
643 not previously set as such. */
645 static inline bool
646 set_agg_lats_to_bottom (struct ipcp_param_lattices *plats)
648 bool ret = !plats->aggs_bottom;
649 plats->aggs_bottom = true;
650 return ret;
653 /* Mark all aggegate lattices in PLATS as containing an unknown value and
654 return true if they were not previously marked as such. */
656 static inline bool
657 set_agg_lats_contain_variable (struct ipcp_param_lattices *plats)
659 bool ret = !plats->aggs_contain_variable;
660 plats->aggs_contain_variable = true;
661 return ret;
664 /* Mark bot aggregate and scalar lattices as containing an unknown variable,
665 return true is any of them has not been marked as such so far. */
667 static inline bool
668 set_all_contains_variable (struct ipcp_param_lattices *plats)
670 bool ret = !plats->itself.contains_variable || !plats->aggs_contain_variable;
671 plats->itself.contains_variable = true;
672 plats->aggs_contain_variable = true;
673 return ret;
676 /* Initialize ipcp_lattices. */
678 static void
679 initialize_node_lattices (struct cgraph_node *node)
681 struct ipa_node_params *info = IPA_NODE_REF (node);
682 struct cgraph_edge *ie;
683 bool disable = false, variable = false;
684 int i;
686 gcc_checking_assert (cgraph_function_with_gimple_body_p (node));
687 if (!node->local.local)
689 /* When cloning is allowed, we can assume that externally visible
690 functions are not called. We will compensate this by cloning
691 later. */
692 if (ipcp_versionable_function_p (node)
693 && ipcp_cloning_candidate_p (node))
694 variable = true;
695 else
696 disable = true;
699 if (disable || variable)
701 for (i = 0; i < ipa_get_param_count (info) ; i++)
703 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
704 if (disable)
706 set_lattice_to_bottom (&plats->itself);
707 set_agg_lats_to_bottom (plats);
709 else
710 set_all_contains_variable (plats);
712 if (dump_file && (dump_flags & TDF_DETAILS)
713 && !node->alias && !node->thunk.thunk_p)
714 fprintf (dump_file, "Marking all lattices of %s/%i as %s\n",
715 cgraph_node_name (node), node->order,
716 disable ? "BOTTOM" : "VARIABLE");
719 for (ie = node->indirect_calls; ie; ie = ie->next_callee)
720 if (ie->indirect_info->polymorphic
721 && ie->indirect_info->param_index >= 0)
723 gcc_checking_assert (ie->indirect_info->param_index >= 0);
724 ipa_get_parm_lattices (info,
725 ie->indirect_info->param_index)->virt_call = 1;
729 /* Return the result of a (possibly arithmetic) pass through jump function
730 JFUNC on the constant value INPUT. Return NULL_TREE if that cannot be
731 determined or be considered an interprocedural invariant. */
733 static tree
734 ipa_get_jf_pass_through_result (struct ipa_jump_func *jfunc, tree input)
736 tree restype, res;
738 if (TREE_CODE (input) == TREE_BINFO)
740 if (ipa_get_jf_pass_through_type_preserved (jfunc))
742 gcc_checking_assert (ipa_get_jf_pass_through_operation (jfunc)
743 == NOP_EXPR);
744 return input;
746 return NULL_TREE;
749 if (ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
750 return input;
752 gcc_checking_assert (is_gimple_ip_invariant (input));
753 if (TREE_CODE_CLASS (ipa_get_jf_pass_through_operation (jfunc))
754 == tcc_comparison)
755 restype = boolean_type_node;
756 else
757 restype = TREE_TYPE (input);
758 res = fold_binary (ipa_get_jf_pass_through_operation (jfunc), restype,
759 input, ipa_get_jf_pass_through_operand (jfunc));
761 if (res && !is_gimple_ip_invariant (res))
762 return NULL_TREE;
764 return res;
767 /* Return the result of an ancestor jump function JFUNC on the constant value
768 INPUT. Return NULL_TREE if that cannot be determined. */
770 static tree
771 ipa_get_jf_ancestor_result (struct ipa_jump_func *jfunc, tree input)
773 if (TREE_CODE (input) == TREE_BINFO)
775 if (!ipa_get_jf_ancestor_type_preserved (jfunc))
776 return NULL;
777 return get_binfo_at_offset (input,
778 ipa_get_jf_ancestor_offset (jfunc),
779 ipa_get_jf_ancestor_type (jfunc));
781 else if (TREE_CODE (input) == ADDR_EXPR)
783 tree t = TREE_OPERAND (input, 0);
784 t = build_ref_for_offset (EXPR_LOCATION (t), t,
785 ipa_get_jf_ancestor_offset (jfunc),
786 ipa_get_jf_ancestor_type (jfunc), NULL, false);
787 return build_fold_addr_expr (t);
789 else
790 return NULL_TREE;
793 /* Determine whether JFUNC evaluates to a known value (that is either a
794 constant or a binfo) and if so, return it. Otherwise return NULL. INFO
795 describes the caller node so that pass-through jump functions can be
796 evaluated. */
798 tree
799 ipa_value_from_jfunc (struct ipa_node_params *info, struct ipa_jump_func *jfunc)
801 if (jfunc->type == IPA_JF_CONST)
802 return ipa_get_jf_constant (jfunc);
803 else if (jfunc->type == IPA_JF_KNOWN_TYPE)
804 return ipa_binfo_from_known_type_jfunc (jfunc);
805 else if (jfunc->type == IPA_JF_PASS_THROUGH
806 || jfunc->type == IPA_JF_ANCESTOR)
808 tree input;
809 int idx;
811 if (jfunc->type == IPA_JF_PASS_THROUGH)
812 idx = ipa_get_jf_pass_through_formal_id (jfunc);
813 else
814 idx = ipa_get_jf_ancestor_formal_id (jfunc);
816 if (info->ipcp_orig_node)
817 input = info->known_vals[idx];
818 else
820 struct ipcp_lattice *lat;
822 if (!info->lattices)
824 gcc_checking_assert (!flag_ipa_cp);
825 return NULL_TREE;
827 lat = ipa_get_scalar_lat (info, idx);
828 if (!ipa_lat_is_single_const (lat))
829 return NULL_TREE;
830 input = lat->values->value;
833 if (!input)
834 return NULL_TREE;
836 if (jfunc->type == IPA_JF_PASS_THROUGH)
837 return ipa_get_jf_pass_through_result (jfunc, input);
838 else
839 return ipa_get_jf_ancestor_result (jfunc, input);
841 else
842 return NULL_TREE;
846 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
847 bottom, not containing a variable component and without any known value at
848 the same time. */
850 DEBUG_FUNCTION void
851 ipcp_verify_propagated_values (void)
853 struct cgraph_node *node;
855 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
857 struct ipa_node_params *info = IPA_NODE_REF (node);
858 int i, count = ipa_get_param_count (info);
860 for (i = 0; i < count; i++)
862 struct ipcp_lattice *lat = ipa_get_scalar_lat (info, i);
864 if (!lat->bottom
865 && !lat->contains_variable
866 && lat->values_count == 0)
868 if (dump_file)
870 fprintf (dump_file, "\nIPA lattices after constant "
871 "propagation:\n");
872 print_all_lattices (dump_file, true, false);
875 gcc_unreachable ();
881 /* Return true iff X and Y should be considered equal values by IPA-CP. */
883 static bool
884 values_equal_for_ipcp_p (tree x, tree y)
886 gcc_checking_assert (x != NULL_TREE && y != NULL_TREE);
888 if (x == y)
889 return true;
891 if (TREE_CODE (x) == TREE_BINFO || TREE_CODE (y) == TREE_BINFO)
892 return false;
894 if (TREE_CODE (x) == ADDR_EXPR
895 && TREE_CODE (y) == ADDR_EXPR
896 && TREE_CODE (TREE_OPERAND (x, 0)) == CONST_DECL
897 && TREE_CODE (TREE_OPERAND (y, 0)) == CONST_DECL)
898 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x, 0)),
899 DECL_INITIAL (TREE_OPERAND (y, 0)), 0);
900 else
901 return operand_equal_p (x, y, 0);
904 /* Add a new value source to VAL, marking that a value comes from edge CS and
905 (if the underlying jump function is a pass-through or an ancestor one) from
906 a caller value SRC_VAL of a caller parameter described by SRC_INDEX. OFFSET
907 is negative if the source was the scalar value of the parameter itself or
908 the offset within an aggregate. */
910 static void
911 add_value_source (struct ipcp_value *val, struct cgraph_edge *cs,
912 struct ipcp_value *src_val, int src_idx, HOST_WIDE_INT offset)
914 struct ipcp_value_source *src;
916 src = (struct ipcp_value_source *) pool_alloc (ipcp_sources_pool);
917 src->offset = offset;
918 src->cs = cs;
919 src->val = src_val;
920 src->index = src_idx;
922 src->next = val->sources;
923 val->sources = src;
926 /* Try to add NEWVAL to LAT, potentially creating a new struct ipcp_value for
927 it. CS, SRC_VAL SRC_INDEX and OFFSET are meant for add_value_source and
928 have the same meaning. */
930 static bool
931 add_value_to_lattice (struct ipcp_lattice *lat, tree newval,
932 struct cgraph_edge *cs, struct ipcp_value *src_val,
933 int src_idx, HOST_WIDE_INT offset)
935 struct ipcp_value *val;
937 if (lat->bottom)
938 return false;
940 for (val = lat->values; val; val = val->next)
941 if (values_equal_for_ipcp_p (val->value, newval))
943 if (ipa_edge_within_scc (cs))
945 struct ipcp_value_source *s;
946 for (s = val->sources; s ; s = s->next)
947 if (s->cs == cs)
948 break;
949 if (s)
950 return false;
953 add_value_source (val, cs, src_val, src_idx, offset);
954 return false;
957 if (lat->values_count == PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE))
959 /* We can only free sources, not the values themselves, because sources
960 of other values in this this SCC might point to them. */
961 for (val = lat->values; val; val = val->next)
963 while (val->sources)
965 struct ipcp_value_source *src = val->sources;
966 val->sources = src->next;
967 pool_free (ipcp_sources_pool, src);
971 lat->values = NULL;
972 return set_lattice_to_bottom (lat);
975 lat->values_count++;
976 val = (struct ipcp_value *) pool_alloc (ipcp_values_pool);
977 memset (val, 0, sizeof (*val));
979 add_value_source (val, cs, src_val, src_idx, offset);
980 val->value = newval;
981 val->next = lat->values;
982 lat->values = val;
983 return true;
986 /* Like above but passes a special value of offset to distinguish that the
987 origin is the scalar value of the parameter rather than a part of an
988 aggregate. */
990 static inline bool
991 add_scalar_value_to_lattice (struct ipcp_lattice *lat, tree newval,
992 struct cgraph_edge *cs,
993 struct ipcp_value *src_val, int src_idx)
995 return add_value_to_lattice (lat, newval, cs, src_val, src_idx, -1);
998 /* Propagate values through a pass-through jump function JFUNC associated with
999 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1000 is the index of the source parameter. */
1002 static bool
1003 propagate_vals_accross_pass_through (struct cgraph_edge *cs,
1004 struct ipa_jump_func *jfunc,
1005 struct ipcp_lattice *src_lat,
1006 struct ipcp_lattice *dest_lat,
1007 int src_idx)
1009 struct ipcp_value *src_val;
1010 bool ret = false;
1012 /* Do not create new values when propagating within an SCC because if there
1013 are arithmetic functions with circular dependencies, there is infinite
1014 number of them and we would just make lattices bottom. */
1015 if ((ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR)
1016 && ipa_edge_within_scc (cs))
1017 ret = set_lattice_contains_variable (dest_lat);
1018 else
1019 for (src_val = src_lat->values; src_val; src_val = src_val->next)
1021 tree cstval = ipa_get_jf_pass_through_result (jfunc, src_val->value);
1023 if (cstval)
1024 ret |= add_scalar_value_to_lattice (dest_lat, cstval, cs, src_val,
1025 src_idx);
1026 else
1027 ret |= set_lattice_contains_variable (dest_lat);
1030 return ret;
1033 /* Propagate values through an ancestor jump function JFUNC associated with
1034 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1035 is the index of the source parameter. */
1037 static bool
1038 propagate_vals_accross_ancestor (struct cgraph_edge *cs,
1039 struct ipa_jump_func *jfunc,
1040 struct ipcp_lattice *src_lat,
1041 struct ipcp_lattice *dest_lat,
1042 int src_idx)
1044 struct ipcp_value *src_val;
1045 bool ret = false;
1047 if (ipa_edge_within_scc (cs))
1048 return set_lattice_contains_variable (dest_lat);
1050 for (src_val = src_lat->values; src_val; src_val = src_val->next)
1052 tree t = ipa_get_jf_ancestor_result (jfunc, src_val->value);
1054 if (t)
1055 ret |= add_scalar_value_to_lattice (dest_lat, t, cs, src_val, src_idx);
1056 else
1057 ret |= set_lattice_contains_variable (dest_lat);
1060 return ret;
1063 /* Propagate scalar values across jump function JFUNC that is associated with
1064 edge CS and put the values into DEST_LAT. */
1066 static bool
1067 propagate_scalar_accross_jump_function (struct cgraph_edge *cs,
1068 struct ipa_jump_func *jfunc,
1069 struct ipcp_lattice *dest_lat)
1071 if (dest_lat->bottom)
1072 return false;
1074 if (jfunc->type == IPA_JF_CONST
1075 || jfunc->type == IPA_JF_KNOWN_TYPE)
1077 tree val;
1079 if (jfunc->type == IPA_JF_KNOWN_TYPE)
1081 val = ipa_binfo_from_known_type_jfunc (jfunc);
1082 if (!val)
1083 return set_lattice_contains_variable (dest_lat);
1085 else
1086 val = ipa_get_jf_constant (jfunc);
1087 return add_scalar_value_to_lattice (dest_lat, val, cs, NULL, 0);
1089 else if (jfunc->type == IPA_JF_PASS_THROUGH
1090 || jfunc->type == IPA_JF_ANCESTOR)
1092 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1093 struct ipcp_lattice *src_lat;
1094 int src_idx;
1095 bool ret;
1097 if (jfunc->type == IPA_JF_PASS_THROUGH)
1098 src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
1099 else
1100 src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
1102 src_lat = ipa_get_scalar_lat (caller_info, src_idx);
1103 if (src_lat->bottom)
1104 return set_lattice_contains_variable (dest_lat);
1106 /* If we would need to clone the caller and cannot, do not propagate. */
1107 if (!ipcp_versionable_function_p (cs->caller)
1108 && (src_lat->contains_variable
1109 || (src_lat->values_count > 1)))
1110 return set_lattice_contains_variable (dest_lat);
1112 if (jfunc->type == IPA_JF_PASS_THROUGH)
1113 ret = propagate_vals_accross_pass_through (cs, jfunc, src_lat,
1114 dest_lat, src_idx);
1115 else
1116 ret = propagate_vals_accross_ancestor (cs, jfunc, src_lat, dest_lat,
1117 src_idx);
1119 if (src_lat->contains_variable)
1120 ret |= set_lattice_contains_variable (dest_lat);
1122 return ret;
1125 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1126 use it for indirect inlining), we should propagate them too. */
1127 return set_lattice_contains_variable (dest_lat);
1130 /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
1131 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
1132 other cases, return false). If there are no aggregate items, set
1133 aggs_by_ref to NEW_AGGS_BY_REF. */
1135 static bool
1136 set_check_aggs_by_ref (struct ipcp_param_lattices *dest_plats,
1137 bool new_aggs_by_ref)
1139 if (dest_plats->aggs)
1141 if (dest_plats->aggs_by_ref != new_aggs_by_ref)
1143 set_agg_lats_to_bottom (dest_plats);
1144 return true;
1147 else
1148 dest_plats->aggs_by_ref = new_aggs_by_ref;
1149 return false;
1152 /* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
1153 already existing lattice for the given OFFSET and SIZE, marking all skipped
1154 lattices as containing variable and checking for overlaps. If there is no
1155 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
1156 it with offset, size and contains_variable to PRE_EXISTING, and return true,
1157 unless there are too many already. If there are two many, return false. If
1158 there are overlaps turn whole DEST_PLATS to bottom and return false. If any
1159 skipped lattices were newly marked as containing variable, set *CHANGE to
1160 true. */
1162 static bool
1163 merge_agg_lats_step (struct ipcp_param_lattices *dest_plats,
1164 HOST_WIDE_INT offset, HOST_WIDE_INT val_size,
1165 struct ipcp_agg_lattice ***aglat,
1166 bool pre_existing, bool *change)
1168 gcc_checking_assert (offset >= 0);
1170 while (**aglat && (**aglat)->offset < offset)
1172 if ((**aglat)->offset + (**aglat)->size > offset)
1174 set_agg_lats_to_bottom (dest_plats);
1175 return false;
1177 *change |= set_lattice_contains_variable (**aglat);
1178 *aglat = &(**aglat)->next;
1181 if (**aglat && (**aglat)->offset == offset)
1183 if ((**aglat)->size != val_size
1184 || ((**aglat)->next
1185 && (**aglat)->next->offset < offset + val_size))
1187 set_agg_lats_to_bottom (dest_plats);
1188 return false;
1190 gcc_checking_assert (!(**aglat)->next
1191 || (**aglat)->next->offset >= offset + val_size);
1192 return true;
1194 else
1196 struct ipcp_agg_lattice *new_al;
1198 if (**aglat && (**aglat)->offset < offset + val_size)
1200 set_agg_lats_to_bottom (dest_plats);
1201 return false;
1203 if (dest_plats->aggs_count == PARAM_VALUE (PARAM_IPA_MAX_AGG_ITEMS))
1204 return false;
1205 dest_plats->aggs_count++;
1206 new_al = (struct ipcp_agg_lattice *) pool_alloc (ipcp_agg_lattice_pool);
1207 memset (new_al, 0, sizeof (*new_al));
1209 new_al->offset = offset;
1210 new_al->size = val_size;
1211 new_al->contains_variable = pre_existing;
1213 new_al->next = **aglat;
1214 **aglat = new_al;
1215 return true;
1219 /* Set all AGLAT and all other aggregate lattices reachable by next pointers as
1220 containing an unknown value. */
1222 static bool
1223 set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice *aglat)
1225 bool ret = false;
1226 while (aglat)
1228 ret |= set_lattice_contains_variable (aglat);
1229 aglat = aglat->next;
1231 return ret;
1234 /* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
1235 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source
1236 parameter used for lattice value sources. Return true if DEST_PLATS changed
1237 in any way. */
1239 static bool
1240 merge_aggregate_lattices (struct cgraph_edge *cs,
1241 struct ipcp_param_lattices *dest_plats,
1242 struct ipcp_param_lattices *src_plats,
1243 int src_idx, HOST_WIDE_INT offset_delta)
1245 bool pre_existing = dest_plats->aggs != NULL;
1246 struct ipcp_agg_lattice **dst_aglat;
1247 bool ret = false;
1249 if (set_check_aggs_by_ref (dest_plats, src_plats->aggs_by_ref))
1250 return true;
1251 if (src_plats->aggs_bottom)
1252 return set_agg_lats_contain_variable (dest_plats);
1253 if (src_plats->aggs_contain_variable)
1254 ret |= set_agg_lats_contain_variable (dest_plats);
1255 dst_aglat = &dest_plats->aggs;
1257 for (struct ipcp_agg_lattice *src_aglat = src_plats->aggs;
1258 src_aglat;
1259 src_aglat = src_aglat->next)
1261 HOST_WIDE_INT new_offset = src_aglat->offset - offset_delta;
1263 if (new_offset < 0)
1264 continue;
1265 if (merge_agg_lats_step (dest_plats, new_offset, src_aglat->size,
1266 &dst_aglat, pre_existing, &ret))
1268 struct ipcp_agg_lattice *new_al = *dst_aglat;
1270 dst_aglat = &(*dst_aglat)->next;
1271 if (src_aglat->bottom)
1273 ret |= set_lattice_contains_variable (new_al);
1274 continue;
1276 if (src_aglat->contains_variable)
1277 ret |= set_lattice_contains_variable (new_al);
1278 for (struct ipcp_value *val = src_aglat->values;
1279 val;
1280 val = val->next)
1281 ret |= add_value_to_lattice (new_al, val->value, cs, val, src_idx,
1282 src_aglat->offset);
1284 else if (dest_plats->aggs_bottom)
1285 return true;
1287 ret |= set_chain_of_aglats_contains_variable (*dst_aglat);
1288 return ret;
1291 /* Determine whether there is anything to propagate FROM SRC_PLATS through a
1292 pass-through JFUNC and if so, whether it has conform and conforms to the
1293 rules about propagating values passed by reference. */
1295 static bool
1296 agg_pass_through_permissible_p (struct ipcp_param_lattices *src_plats,
1297 struct ipa_jump_func *jfunc)
1299 return src_plats->aggs
1300 && (!src_plats->aggs_by_ref
1301 || ipa_get_jf_pass_through_agg_preserved (jfunc));
1304 /* Propagate scalar values across jump function JFUNC that is associated with
1305 edge CS and put the values into DEST_LAT. */
1307 static bool
1308 propagate_aggs_accross_jump_function (struct cgraph_edge *cs,
1309 struct ipa_jump_func *jfunc,
1310 struct ipcp_param_lattices *dest_plats)
1312 bool ret = false;
1314 if (dest_plats->aggs_bottom)
1315 return false;
1317 if (jfunc->type == IPA_JF_PASS_THROUGH
1318 && ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
1320 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1321 int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
1322 struct ipcp_param_lattices *src_plats;
1324 src_plats = ipa_get_parm_lattices (caller_info, src_idx);
1325 if (agg_pass_through_permissible_p (src_plats, jfunc))
1327 /* Currently we do not produce clobber aggregate jump
1328 functions, replace with merging when we do. */
1329 gcc_assert (!jfunc->agg.items);
1330 ret |= merge_aggregate_lattices (cs, dest_plats, src_plats,
1331 src_idx, 0);
1333 else
1334 ret |= set_agg_lats_contain_variable (dest_plats);
1336 else if (jfunc->type == IPA_JF_ANCESTOR
1337 && ipa_get_jf_ancestor_agg_preserved (jfunc))
1339 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1340 int src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
1341 struct ipcp_param_lattices *src_plats;
1343 src_plats = ipa_get_parm_lattices (caller_info, src_idx);
1344 if (src_plats->aggs && src_plats->aggs_by_ref)
1346 /* Currently we do not produce clobber aggregate jump
1347 functions, replace with merging when we do. */
1348 gcc_assert (!jfunc->agg.items);
1349 ret |= merge_aggregate_lattices (cs, dest_plats, src_plats, src_idx,
1350 ipa_get_jf_ancestor_offset (jfunc));
1352 else if (!src_plats->aggs_by_ref)
1353 ret |= set_agg_lats_to_bottom (dest_plats);
1354 else
1355 ret |= set_agg_lats_contain_variable (dest_plats);
1357 else if (jfunc->agg.items)
1359 bool pre_existing = dest_plats->aggs != NULL;
1360 struct ipcp_agg_lattice **aglat = &dest_plats->aggs;
1361 struct ipa_agg_jf_item *item;
1362 int i;
1364 if (set_check_aggs_by_ref (dest_plats, jfunc->agg.by_ref))
1365 return true;
1367 FOR_EACH_VEC_ELT (*jfunc->agg.items, i, item)
1369 HOST_WIDE_INT val_size;
1371 if (item->offset < 0)
1372 continue;
1373 gcc_checking_assert (is_gimple_ip_invariant (item->value));
1374 val_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (item->value)), 1);
1376 if (merge_agg_lats_step (dest_plats, item->offset, val_size,
1377 &aglat, pre_existing, &ret))
1379 ret |= add_value_to_lattice (*aglat, item->value, cs, NULL, 0, 0);
1380 aglat = &(*aglat)->next;
1382 else if (dest_plats->aggs_bottom)
1383 return true;
1386 ret |= set_chain_of_aglats_contains_variable (*aglat);
1388 else
1389 ret |= set_agg_lats_contain_variable (dest_plats);
1391 return ret;
1394 /* Propagate constants from the caller to the callee of CS. INFO describes the
1395 caller. */
1397 static bool
1398 propagate_constants_accross_call (struct cgraph_edge *cs)
1400 struct ipa_node_params *callee_info;
1401 enum availability availability;
1402 struct cgraph_node *callee, *alias_or_thunk;
1403 struct ipa_edge_args *args;
1404 bool ret = false;
1405 int i, args_count, parms_count;
1407 callee = cgraph_function_node (cs->callee, &availability);
1408 if (!callee->definition)
1409 return false;
1410 gcc_checking_assert (cgraph_function_with_gimple_body_p (callee));
1411 callee_info = IPA_NODE_REF (callee);
1413 args = IPA_EDGE_REF (cs);
1414 args_count = ipa_get_cs_argument_count (args);
1415 parms_count = ipa_get_param_count (callee_info);
1417 /* If this call goes through a thunk we must not propagate to the first (0th)
1418 parameter. However, we might need to uncover a thunk from below a series
1419 of aliases first. */
1420 alias_or_thunk = cs->callee;
1421 while (alias_or_thunk->alias)
1422 alias_or_thunk = cgraph_alias_target (alias_or_thunk);
1423 if (alias_or_thunk->thunk.thunk_p)
1425 ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info,
1426 0));
1427 i = 1;
1429 else
1430 i = 0;
1432 for (; (i < args_count) && (i < parms_count); i++)
1434 struct ipa_jump_func *jump_func = ipa_get_ith_jump_func (args, i);
1435 struct ipcp_param_lattices *dest_plats;
1437 dest_plats = ipa_get_parm_lattices (callee_info, i);
1438 if (availability == AVAIL_OVERWRITABLE)
1439 ret |= set_all_contains_variable (dest_plats);
1440 else
1442 ret |= propagate_scalar_accross_jump_function (cs, jump_func,
1443 &dest_plats->itself);
1444 ret |= propagate_aggs_accross_jump_function (cs, jump_func,
1445 dest_plats);
1448 for (; i < parms_count; i++)
1449 ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info, i));
1451 return ret;
1454 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
1455 (which can contain both constants and binfos), KNOWN_BINFOS, KNOWN_AGGS or
1456 AGG_REPS return the destination. The latter three can be NULL. If AGG_REPS
1457 is not NULL, KNOWN_AGGS is ignored. */
1459 static tree
1460 ipa_get_indirect_edge_target_1 (struct cgraph_edge *ie,
1461 vec<tree> known_vals,
1462 vec<tree> known_binfos,
1463 vec<ipa_agg_jump_function_p> known_aggs,
1464 struct ipa_agg_replacement_value *agg_reps)
1466 int param_index = ie->indirect_info->param_index;
1467 HOST_WIDE_INT token, anc_offset;
1468 tree otr_type;
1469 tree t;
1470 tree target;
1472 if (param_index == -1
1473 || known_vals.length () <= (unsigned int) param_index)
1474 return NULL_TREE;
1476 if (!ie->indirect_info->polymorphic)
1478 tree t;
1480 if (ie->indirect_info->agg_contents)
1482 if (agg_reps)
1484 t = NULL;
1485 while (agg_reps)
1487 if (agg_reps->index == param_index
1488 && agg_reps->offset == ie->indirect_info->offset
1489 && agg_reps->by_ref == ie->indirect_info->by_ref)
1491 t = agg_reps->value;
1492 break;
1494 agg_reps = agg_reps->next;
1497 else if (known_aggs.length () > (unsigned int) param_index)
1499 struct ipa_agg_jump_function *agg;
1500 agg = known_aggs[param_index];
1501 t = ipa_find_agg_cst_for_param (agg, ie->indirect_info->offset,
1502 ie->indirect_info->by_ref);
1504 else
1505 t = NULL;
1507 else
1508 t = known_vals[param_index];
1510 if (t &&
1511 TREE_CODE (t) == ADDR_EXPR
1512 && TREE_CODE (TREE_OPERAND (t, 0)) == FUNCTION_DECL)
1513 return TREE_OPERAND (t, 0);
1514 else
1515 return NULL_TREE;
1518 gcc_assert (!ie->indirect_info->agg_contents);
1519 token = ie->indirect_info->otr_token;
1520 anc_offset = ie->indirect_info->offset;
1521 otr_type = ie->indirect_info->otr_type;
1523 t = known_vals[param_index];
1524 if (!t && known_binfos.length () > (unsigned int) param_index)
1525 t = known_binfos[param_index];
1526 if (!t)
1527 return NULL_TREE;
1529 if (TREE_CODE (t) != TREE_BINFO)
1531 tree binfo;
1532 binfo = gimple_extract_devirt_binfo_from_cst
1533 (t, ie->indirect_info->otr_type);
1534 if (!binfo)
1535 return NULL_TREE;
1536 binfo = get_binfo_at_offset (binfo, anc_offset, otr_type);
1537 if (!binfo)
1538 return NULL_TREE;
1539 target = gimple_get_virt_method_for_binfo (token, binfo);
1541 else
1543 tree binfo;
1545 binfo = get_binfo_at_offset (t, anc_offset, otr_type);
1546 if (!binfo)
1547 return NULL_TREE;
1548 target = gimple_get_virt_method_for_binfo (token, binfo);
1550 #ifdef ENABLE_CHECKING
1551 if (target)
1552 gcc_assert (possible_polymorphic_call_target_p
1553 (ie, cgraph_get_node (target)));
1554 #endif
1556 return target;
1560 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
1561 (which can contain both constants and binfos), KNOWN_BINFOS (which can be
1562 NULL) or KNOWN_AGGS (which also can be NULL) return the destination. */
1564 tree
1565 ipa_get_indirect_edge_target (struct cgraph_edge *ie,
1566 vec<tree> known_vals,
1567 vec<tree> known_binfos,
1568 vec<ipa_agg_jump_function_p> known_aggs)
1570 return ipa_get_indirect_edge_target_1 (ie, known_vals, known_binfos,
1571 known_aggs, NULL);
1574 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
1575 and KNOWN_BINFOS. */
1577 static int
1578 devirtualization_time_bonus (struct cgraph_node *node,
1579 vec<tree> known_csts,
1580 vec<tree> known_binfos,
1581 vec<ipa_agg_jump_function_p> known_aggs)
1583 struct cgraph_edge *ie;
1584 int res = 0;
1586 for (ie = node->indirect_calls; ie; ie = ie->next_callee)
1588 struct cgraph_node *callee;
1589 struct inline_summary *isummary;
1590 tree target;
1592 target = ipa_get_indirect_edge_target (ie, known_csts, known_binfos,
1593 known_aggs);
1594 if (!target)
1595 continue;
1597 /* Only bare minimum benefit for clearly un-inlineable targets. */
1598 res += 1;
1599 callee = cgraph_get_node (target);
1600 if (!callee || !callee->definition)
1601 continue;
1602 isummary = inline_summary (callee);
1603 if (!isummary->inlinable)
1604 continue;
1606 /* FIXME: The values below need re-considering and perhaps also
1607 integrating into the cost metrics, at lest in some very basic way. */
1608 if (isummary->size <= MAX_INLINE_INSNS_AUTO / 4)
1609 res += 31;
1610 else if (isummary->size <= MAX_INLINE_INSNS_AUTO / 2)
1611 res += 15;
1612 else if (isummary->size <= MAX_INLINE_INSNS_AUTO
1613 || DECL_DECLARED_INLINE_P (callee->decl))
1614 res += 7;
1617 return res;
1620 /* Return time bonus incurred because of HINTS. */
1622 static int
1623 hint_time_bonus (inline_hints hints)
1625 int result = 0;
1626 if (hints & (INLINE_HINT_loop_iterations | INLINE_HINT_loop_stride))
1627 result += PARAM_VALUE (PARAM_IPA_CP_LOOP_HINT_BONUS);
1628 if (hints & INLINE_HINT_array_index)
1629 result += PARAM_VALUE (PARAM_IPA_CP_ARRAY_INDEX_HINT_BONUS);
1630 return result;
1633 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
1634 and SIZE_COST and with the sum of frequencies of incoming edges to the
1635 potential new clone in FREQUENCIES. */
1637 static bool
1638 good_cloning_opportunity_p (struct cgraph_node *node, int time_benefit,
1639 int freq_sum, gcov_type count_sum, int size_cost)
1641 if (time_benefit == 0
1642 || !flag_ipa_cp_clone
1643 || !optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node->decl)))
1644 return false;
1646 gcc_assert (size_cost > 0);
1648 if (max_count)
1650 int factor = (count_sum * 1000) / max_count;
1651 HOST_WIDEST_INT evaluation = (((HOST_WIDEST_INT) time_benefit * factor)
1652 / size_cost);
1654 if (dump_file && (dump_flags & TDF_DETAILS))
1655 fprintf (dump_file, " good_cloning_opportunity_p (time: %i, "
1656 "size: %i, count_sum: " HOST_WIDE_INT_PRINT_DEC
1657 ") -> evaluation: " HOST_WIDEST_INT_PRINT_DEC
1658 ", threshold: %i\n",
1659 time_benefit, size_cost, (HOST_WIDE_INT) count_sum,
1660 evaluation, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD));
1662 return evaluation >= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD);
1664 else
1666 HOST_WIDEST_INT evaluation = (((HOST_WIDEST_INT) time_benefit * freq_sum)
1667 / size_cost);
1669 if (dump_file && (dump_flags & TDF_DETAILS))
1670 fprintf (dump_file, " good_cloning_opportunity_p (time: %i, "
1671 "size: %i, freq_sum: %i) -> evaluation: "
1672 HOST_WIDEST_INT_PRINT_DEC ", threshold: %i\n",
1673 time_benefit, size_cost, freq_sum, evaluation,
1674 PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD));
1676 return evaluation >= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD);
1680 /* Return all context independent values from aggregate lattices in PLATS in a
1681 vector. Return NULL if there are none. */
1683 static vec<ipa_agg_jf_item_t, va_gc> *
1684 context_independent_aggregate_values (struct ipcp_param_lattices *plats)
1686 vec<ipa_agg_jf_item_t, va_gc> *res = NULL;
1688 if (plats->aggs_bottom
1689 || plats->aggs_contain_variable
1690 || plats->aggs_count == 0)
1691 return NULL;
1693 for (struct ipcp_agg_lattice *aglat = plats->aggs;
1694 aglat;
1695 aglat = aglat->next)
1696 if (ipa_lat_is_single_const (aglat))
1698 struct ipa_agg_jf_item item;
1699 item.offset = aglat->offset;
1700 item.value = aglat->values->value;
1701 vec_safe_push (res, item);
1703 return res;
1706 /* Allocate KNOWN_CSTS, KNOWN_BINFOS and, if non-NULL, KNOWN_AGGS and populate
1707 them with values of parameters that are known independent of the context.
1708 INFO describes the function. If REMOVABLE_PARAMS_COST is non-NULL, the
1709 movement cost of all removable parameters will be stored in it. */
1711 static bool
1712 gather_context_independent_values (struct ipa_node_params *info,
1713 vec<tree> *known_csts,
1714 vec<tree> *known_binfos,
1715 vec<ipa_agg_jump_function_t> *known_aggs,
1716 int *removable_params_cost)
1718 int i, count = ipa_get_param_count (info);
1719 bool ret = false;
1721 known_csts->create (0);
1722 known_binfos->create (0);
1723 known_csts->safe_grow_cleared (count);
1724 known_binfos->safe_grow_cleared (count);
1725 if (known_aggs)
1727 known_aggs->create (0);
1728 known_aggs->safe_grow_cleared (count);
1731 if (removable_params_cost)
1732 *removable_params_cost = 0;
1734 for (i = 0; i < count ; i++)
1736 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
1737 struct ipcp_lattice *lat = &plats->itself;
1739 if (ipa_lat_is_single_const (lat))
1741 struct ipcp_value *val = lat->values;
1742 if (TREE_CODE (val->value) != TREE_BINFO)
1744 (*known_csts)[i] = val->value;
1745 if (removable_params_cost)
1746 *removable_params_cost
1747 += estimate_move_cost (TREE_TYPE (val->value));
1748 ret = true;
1750 else if (plats->virt_call)
1752 (*known_binfos)[i] = val->value;
1753 ret = true;
1755 else if (removable_params_cost
1756 && !ipa_is_param_used (info, i))
1757 *removable_params_cost += ipa_get_param_move_cost (info, i);
1759 else if (removable_params_cost
1760 && !ipa_is_param_used (info, i))
1761 *removable_params_cost
1762 += ipa_get_param_move_cost (info, i);
1764 if (known_aggs)
1766 vec<ipa_agg_jf_item_t, va_gc> *agg_items;
1767 struct ipa_agg_jump_function *ajf;
1769 agg_items = context_independent_aggregate_values (plats);
1770 ajf = &(*known_aggs)[i];
1771 ajf->items = agg_items;
1772 ajf->by_ref = plats->aggs_by_ref;
1773 ret |= agg_items != NULL;
1777 return ret;
1780 /* The current interface in ipa-inline-analysis requires a pointer vector.
1781 Create it.
1783 FIXME: That interface should be re-worked, this is slightly silly. Still,
1784 I'd like to discuss how to change it first and this demonstrates the
1785 issue. */
1787 static vec<ipa_agg_jump_function_p>
1788 agg_jmp_p_vec_for_t_vec (vec<ipa_agg_jump_function_t> known_aggs)
1790 vec<ipa_agg_jump_function_p> ret;
1791 struct ipa_agg_jump_function *ajf;
1792 int i;
1794 ret.create (known_aggs.length ());
1795 FOR_EACH_VEC_ELT (known_aggs, i, ajf)
1796 ret.quick_push (ajf);
1797 return ret;
1800 /* Iterate over known values of parameters of NODE and estimate the local
1801 effects in terms of time and size they have. */
1803 static void
1804 estimate_local_effects (struct cgraph_node *node)
1806 struct ipa_node_params *info = IPA_NODE_REF (node);
1807 int i, count = ipa_get_param_count (info);
1808 vec<tree> known_csts, known_binfos;
1809 vec<ipa_agg_jump_function_t> known_aggs;
1810 vec<ipa_agg_jump_function_p> known_aggs_ptrs;
1811 bool always_const;
1812 int base_time = inline_summary (node)->time;
1813 int removable_params_cost;
1815 if (!count || !ipcp_versionable_function_p (node))
1816 return;
1818 if (dump_file && (dump_flags & TDF_DETAILS))
1819 fprintf (dump_file, "\nEstimating effects for %s/%i, base_time: %i.\n",
1820 cgraph_node_name (node), node->order, base_time);
1822 always_const = gather_context_independent_values (info, &known_csts,
1823 &known_binfos, &known_aggs,
1824 &removable_params_cost);
1825 known_aggs_ptrs = agg_jmp_p_vec_for_t_vec (known_aggs);
1826 if (always_const)
1828 struct caller_statistics stats;
1829 inline_hints hints;
1830 int time, size;
1832 init_caller_stats (&stats);
1833 cgraph_for_node_and_aliases (node, gather_caller_stats, &stats, false);
1834 estimate_ipcp_clone_size_and_time (node, known_csts, known_binfos,
1835 known_aggs_ptrs, &size, &time, &hints);
1836 time -= devirtualization_time_bonus (node, known_csts, known_binfos,
1837 known_aggs_ptrs);
1838 time -= hint_time_bonus (hints);
1839 time -= removable_params_cost;
1840 size -= stats.n_calls * removable_params_cost;
1842 if (dump_file)
1843 fprintf (dump_file, " - context independent values, size: %i, "
1844 "time_benefit: %i\n", size, base_time - time);
1846 if (size <= 0
1847 || cgraph_will_be_removed_from_program_if_no_direct_calls (node))
1849 info->do_clone_for_all_contexts = true;
1850 base_time = time;
1852 if (dump_file)
1853 fprintf (dump_file, " Decided to specialize for all "
1854 "known contexts, code not going to grow.\n");
1856 else if (good_cloning_opportunity_p (node, base_time - time,
1857 stats.freq_sum, stats.count_sum,
1858 size))
1860 if (size + overall_size <= max_new_size)
1862 info->do_clone_for_all_contexts = true;
1863 base_time = time;
1864 overall_size += size;
1866 if (dump_file)
1867 fprintf (dump_file, " Decided to specialize for all "
1868 "known contexts, growth deemed beneficial.\n");
1870 else if (dump_file && (dump_flags & TDF_DETAILS))
1871 fprintf (dump_file, " Not cloning for all contexts because "
1872 "max_new_size would be reached with %li.\n",
1873 size + overall_size);
1877 for (i = 0; i < count ; i++)
1879 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
1880 struct ipcp_lattice *lat = &plats->itself;
1881 struct ipcp_value *val;
1882 int emc;
1884 if (lat->bottom
1885 || !lat->values
1886 || known_csts[i]
1887 || known_binfos[i])
1888 continue;
1890 for (val = lat->values; val; val = val->next)
1892 int time, size, time_benefit;
1893 inline_hints hints;
1895 if (TREE_CODE (val->value) != TREE_BINFO)
1897 known_csts[i] = val->value;
1898 known_binfos[i] = NULL_TREE;
1899 emc = estimate_move_cost (TREE_TYPE (val->value));
1901 else if (plats->virt_call)
1903 known_csts[i] = NULL_TREE;
1904 known_binfos[i] = val->value;
1905 emc = 0;
1907 else
1908 continue;
1910 estimate_ipcp_clone_size_and_time (node, known_csts, known_binfos,
1911 known_aggs_ptrs, &size, &time,
1912 &hints);
1913 time_benefit = base_time - time
1914 + devirtualization_time_bonus (node, known_csts, known_binfos,
1915 known_aggs_ptrs)
1916 + hint_time_bonus (hints)
1917 + removable_params_cost + emc;
1919 gcc_checking_assert (size >=0);
1920 /* The inliner-heuristics based estimates may think that in certain
1921 contexts some functions do not have any size at all but we want
1922 all specializations to have at least a tiny cost, not least not to
1923 divide by zero. */
1924 if (size == 0)
1925 size = 1;
1927 if (dump_file && (dump_flags & TDF_DETAILS))
1929 fprintf (dump_file, " - estimates for value ");
1930 print_ipcp_constant_value (dump_file, val->value);
1931 fprintf (dump_file, " for ");
1932 ipa_dump_param (dump_file, info, i);
1933 fprintf (dump_file, ": time_benefit: %i, size: %i\n",
1934 time_benefit, size);
1937 val->local_time_benefit = time_benefit;
1938 val->local_size_cost = size;
1940 known_binfos[i] = NULL_TREE;
1941 known_csts[i] = NULL_TREE;
1944 for (i = 0; i < count ; i++)
1946 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
1947 struct ipa_agg_jump_function *ajf;
1948 struct ipcp_agg_lattice *aglat;
1950 if (plats->aggs_bottom || !plats->aggs)
1951 continue;
1953 ajf = &known_aggs[i];
1954 for (aglat = plats->aggs; aglat; aglat = aglat->next)
1956 struct ipcp_value *val;
1957 if (aglat->bottom || !aglat->values
1958 /* If the following is true, the one value is in known_aggs. */
1959 || (!plats->aggs_contain_variable
1960 && ipa_lat_is_single_const (aglat)))
1961 continue;
1963 for (val = aglat->values; val; val = val->next)
1965 int time, size, time_benefit;
1966 struct ipa_agg_jf_item item;
1967 inline_hints hints;
1969 item.offset = aglat->offset;
1970 item.value = val->value;
1971 vec_safe_push (ajf->items, item);
1973 estimate_ipcp_clone_size_and_time (node, known_csts, known_binfos,
1974 known_aggs_ptrs, &size, &time,
1975 &hints);
1976 time_benefit = base_time - time
1977 + devirtualization_time_bonus (node, known_csts, known_binfos,
1978 known_aggs_ptrs)
1979 + hint_time_bonus (hints);
1980 gcc_checking_assert (size >=0);
1981 if (size == 0)
1982 size = 1;
1984 if (dump_file && (dump_flags & TDF_DETAILS))
1986 fprintf (dump_file, " - estimates for value ");
1987 print_ipcp_constant_value (dump_file, val->value);
1988 fprintf (dump_file, " for ");
1989 ipa_dump_param (dump_file, info, i);
1990 fprintf (dump_file, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
1991 "]: time_benefit: %i, size: %i\n",
1992 plats->aggs_by_ref ? "ref " : "",
1993 aglat->offset, time_benefit, size);
1996 val->local_time_benefit = time_benefit;
1997 val->local_size_cost = size;
1998 ajf->items->pop ();
2003 for (i = 0; i < count ; i++)
2004 vec_free (known_aggs[i].items);
2006 known_csts.release ();
2007 known_binfos.release ();
2008 known_aggs.release ();
2009 known_aggs_ptrs.release ();
2013 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
2014 topological sort of values. */
2016 static void
2017 add_val_to_toposort (struct ipcp_value *cur_val)
2019 static int dfs_counter = 0;
2020 static struct ipcp_value *stack;
2021 struct ipcp_value_source *src;
2023 if (cur_val->dfs)
2024 return;
2026 dfs_counter++;
2027 cur_val->dfs = dfs_counter;
2028 cur_val->low_link = dfs_counter;
2030 cur_val->topo_next = stack;
2031 stack = cur_val;
2032 cur_val->on_stack = true;
2034 for (src = cur_val->sources; src; src = src->next)
2035 if (src->val)
2037 if (src->val->dfs == 0)
2039 add_val_to_toposort (src->val);
2040 if (src->val->low_link < cur_val->low_link)
2041 cur_val->low_link = src->val->low_link;
2043 else if (src->val->on_stack
2044 && src->val->dfs < cur_val->low_link)
2045 cur_val->low_link = src->val->dfs;
2048 if (cur_val->dfs == cur_val->low_link)
2050 struct ipcp_value *v, *scc_list = NULL;
2054 v = stack;
2055 stack = v->topo_next;
2056 v->on_stack = false;
2058 v->scc_next = scc_list;
2059 scc_list = v;
2061 while (v != cur_val);
2063 cur_val->topo_next = values_topo;
2064 values_topo = cur_val;
2068 /* Add all values in lattices associated with NODE to the topological sort if
2069 they are not there yet. */
2071 static void
2072 add_all_node_vals_to_toposort (struct cgraph_node *node)
2074 struct ipa_node_params *info = IPA_NODE_REF (node);
2075 int i, count = ipa_get_param_count (info);
2077 for (i = 0; i < count ; i++)
2079 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
2080 struct ipcp_lattice *lat = &plats->itself;
2081 struct ipcp_agg_lattice *aglat;
2082 struct ipcp_value *val;
2084 if (!lat->bottom)
2085 for (val = lat->values; val; val = val->next)
2086 add_val_to_toposort (val);
2088 if (!plats->aggs_bottom)
2089 for (aglat = plats->aggs; aglat; aglat = aglat->next)
2090 if (!aglat->bottom)
2091 for (val = aglat->values; val; val = val->next)
2092 add_val_to_toposort (val);
2096 /* One pass of constants propagation along the call graph edges, from callers
2097 to callees (requires topological ordering in TOPO), iterate over strongly
2098 connected components. */
2100 static void
2101 propagate_constants_topo (struct topo_info *topo)
2103 int i;
2105 for (i = topo->nnodes - 1; i >= 0; i--)
2107 unsigned j;
2108 struct cgraph_node *v, *node = topo->order[i];
2109 vec<cgraph_node_ptr> cycle_nodes = ipa_get_nodes_in_cycle (node);
2111 /* First, iteratively propagate within the strongly connected component
2112 until all lattices stabilize. */
2113 FOR_EACH_VEC_ELT (cycle_nodes, j, v)
2114 if (cgraph_function_with_gimple_body_p (v))
2115 push_node_to_stack (topo, v);
2117 v = pop_node_from_stack (topo);
2118 while (v)
2120 struct cgraph_edge *cs;
2122 for (cs = v->callees; cs; cs = cs->next_callee)
2123 if (ipa_edge_within_scc (cs)
2124 && propagate_constants_accross_call (cs))
2125 push_node_to_stack (topo, cs->callee);
2126 v = pop_node_from_stack (topo);
2129 /* Afterwards, propagate along edges leading out of the SCC, calculates
2130 the local effects of the discovered constants and all valid values to
2131 their topological sort. */
2132 FOR_EACH_VEC_ELT (cycle_nodes, j, v)
2133 if (cgraph_function_with_gimple_body_p (v))
2135 struct cgraph_edge *cs;
2137 estimate_local_effects (v);
2138 add_all_node_vals_to_toposort (v);
2139 for (cs = v->callees; cs; cs = cs->next_callee)
2140 if (!ipa_edge_within_scc (cs))
2141 propagate_constants_accross_call (cs);
2143 cycle_nodes.release ();
2148 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
2149 the bigger one if otherwise. */
2151 static int
2152 safe_add (int a, int b)
2154 if (a > INT_MAX/2 || b > INT_MAX/2)
2155 return a > b ? a : b;
2156 else
2157 return a + b;
2161 /* Propagate the estimated effects of individual values along the topological
2162 from the dependent values to those they depend on. */
2164 static void
2165 propagate_effects (void)
2167 struct ipcp_value *base;
2169 for (base = values_topo; base; base = base->topo_next)
2171 struct ipcp_value_source *src;
2172 struct ipcp_value *val;
2173 int time = 0, size = 0;
2175 for (val = base; val; val = val->scc_next)
2177 time = safe_add (time,
2178 val->local_time_benefit + val->prop_time_benefit);
2179 size = safe_add (size, val->local_size_cost + val->prop_size_cost);
2182 for (val = base; val; val = val->scc_next)
2183 for (src = val->sources; src; src = src->next)
2184 if (src->val
2185 && cgraph_maybe_hot_edge_p (src->cs))
2187 src->val->prop_time_benefit = safe_add (time,
2188 src->val->prop_time_benefit);
2189 src->val->prop_size_cost = safe_add (size,
2190 src->val->prop_size_cost);
2196 /* Propagate constants, binfos and their effects from the summaries
2197 interprocedurally. */
2199 static void
2200 ipcp_propagate_stage (struct topo_info *topo)
2202 struct cgraph_node *node;
2204 if (dump_file)
2205 fprintf (dump_file, "\n Propagating constants:\n\n");
2207 if (in_lto_p)
2208 ipa_update_after_lto_read ();
2211 FOR_EACH_DEFINED_FUNCTION (node)
2213 struct ipa_node_params *info = IPA_NODE_REF (node);
2215 determine_versionability (node);
2216 if (cgraph_function_with_gimple_body_p (node))
2218 info->lattices = XCNEWVEC (struct ipcp_param_lattices,
2219 ipa_get_param_count (info));
2220 initialize_node_lattices (node);
2222 if (node->definition && !node->alias)
2223 overall_size += inline_summary (node)->self_size;
2224 if (node->count > max_count)
2225 max_count = node->count;
2228 max_new_size = overall_size;
2229 if (max_new_size < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
2230 max_new_size = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
2231 max_new_size += max_new_size * PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH) / 100 + 1;
2233 if (dump_file)
2234 fprintf (dump_file, "\noverall_size: %li, max_new_size: %li\n",
2235 overall_size, max_new_size);
2237 propagate_constants_topo (topo);
2238 #ifdef ENABLE_CHECKING
2239 ipcp_verify_propagated_values ();
2240 #endif
2241 propagate_effects ();
2243 if (dump_file)
2245 fprintf (dump_file, "\nIPA lattices after all propagation:\n");
2246 print_all_lattices (dump_file, (dump_flags & TDF_DETAILS), true);
2250 /* Discover newly direct outgoing edges from NODE which is a new clone with
2251 known KNOWN_VALS and make them direct. */
2253 static void
2254 ipcp_discover_new_direct_edges (struct cgraph_node *node,
2255 vec<tree> known_vals,
2256 struct ipa_agg_replacement_value *aggvals)
2258 struct cgraph_edge *ie, *next_ie;
2259 bool found = false;
2261 for (ie = node->indirect_calls; ie; ie = next_ie)
2263 tree target;
2265 next_ie = ie->next_callee;
2266 target = ipa_get_indirect_edge_target_1 (ie, known_vals, vNULL, vNULL,
2267 aggvals);
2268 if (target)
2270 bool agg_contents = ie->indirect_info->agg_contents;
2271 bool polymorphic = ie->indirect_info->polymorphic;
2272 bool param_index = ie->indirect_info->param_index;
2273 struct cgraph_edge *cs = ipa_make_edge_direct_to_target (ie, target);
2274 found = true;
2276 if (cs && !agg_contents && !polymorphic)
2278 struct ipa_node_params *info = IPA_NODE_REF (node);
2279 int c = ipa_get_controlled_uses (info, param_index);
2280 if (c != IPA_UNDESCRIBED_USE)
2282 struct ipa_ref *to_del;
2284 c--;
2285 ipa_set_controlled_uses (info, param_index, c);
2286 if (dump_file && (dump_flags & TDF_DETAILS))
2287 fprintf (dump_file, " controlled uses count of param "
2288 "%i bumped down to %i\n", param_index, c);
2289 if (c == 0
2290 && (to_del = ipa_find_reference (node,
2291 cs->callee,
2292 NULL, 0)))
2294 if (dump_file && (dump_flags & TDF_DETAILS))
2295 fprintf (dump_file, " and even removing its "
2296 "cloning-created reference\n");
2297 ipa_remove_reference (to_del);
2303 /* Turning calls to direct calls will improve overall summary. */
2304 if (found)
2305 inline_update_overall_summary (node);
2308 /* Vector of pointers which for linked lists of clones of an original crgaph
2309 edge. */
2311 static vec<cgraph_edge_p> next_edge_clone;
2313 static inline void
2314 grow_next_edge_clone_vector (void)
2316 if (next_edge_clone.length ()
2317 <= (unsigned) cgraph_edge_max_uid)
2318 next_edge_clone.safe_grow_cleared (cgraph_edge_max_uid + 1);
2321 /* Edge duplication hook to grow the appropriate linked list in
2322 next_edge_clone. */
2324 static void
2325 ipcp_edge_duplication_hook (struct cgraph_edge *src, struct cgraph_edge *dst,
2326 __attribute__((unused)) void *data)
2328 grow_next_edge_clone_vector ();
2329 next_edge_clone[dst->uid] = next_edge_clone[src->uid];
2330 next_edge_clone[src->uid] = dst;
2333 /* See if NODE is a clone with a known aggregate value at a given OFFSET of a
2334 parameter with the given INDEX. */
2336 static tree
2337 get_clone_agg_value (struct cgraph_node *node, HOST_WIDEST_INT offset,
2338 int index)
2340 struct ipa_agg_replacement_value *aggval;
2342 aggval = ipa_get_agg_replacements_for_node (node);
2343 while (aggval)
2345 if (aggval->offset == offset
2346 && aggval->index == index)
2347 return aggval->value;
2348 aggval = aggval->next;
2350 return NULL_TREE;
2353 /* Return true if edge CS does bring about the value described by SRC. */
2355 static bool
2356 cgraph_edge_brings_value_p (struct cgraph_edge *cs,
2357 struct ipcp_value_source *src)
2359 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
2360 struct ipa_node_params *dst_info = IPA_NODE_REF (cs->callee);
2362 if ((dst_info->ipcp_orig_node && !dst_info->is_all_contexts_clone)
2363 || caller_info->node_dead)
2364 return false;
2365 if (!src->val)
2366 return true;
2368 if (caller_info->ipcp_orig_node)
2370 tree t;
2371 if (src->offset == -1)
2372 t = caller_info->known_vals[src->index];
2373 else
2374 t = get_clone_agg_value (cs->caller, src->offset, src->index);
2375 return (t != NULL_TREE
2376 && values_equal_for_ipcp_p (src->val->value, t));
2378 else
2380 struct ipcp_agg_lattice *aglat;
2381 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (caller_info,
2382 src->index);
2383 if (src->offset == -1)
2384 return (ipa_lat_is_single_const (&plats->itself)
2385 && values_equal_for_ipcp_p (src->val->value,
2386 plats->itself.values->value));
2387 else
2389 if (plats->aggs_bottom || plats->aggs_contain_variable)
2390 return false;
2391 for (aglat = plats->aggs; aglat; aglat = aglat->next)
2392 if (aglat->offset == src->offset)
2393 return (ipa_lat_is_single_const (aglat)
2394 && values_equal_for_ipcp_p (src->val->value,
2395 aglat->values->value));
2397 return false;
2401 /* Get the next clone in the linked list of clones of an edge. */
2403 static inline struct cgraph_edge *
2404 get_next_cgraph_edge_clone (struct cgraph_edge *cs)
2406 return next_edge_clone[cs->uid];
2409 /* Given VAL, iterate over all its sources and if they still hold, add their
2410 edge frequency and their number into *FREQUENCY and *CALLER_COUNT
2411 respectively. */
2413 static bool
2414 get_info_about_necessary_edges (struct ipcp_value *val, int *freq_sum,
2415 gcov_type *count_sum, int *caller_count)
2417 struct ipcp_value_source *src;
2418 int freq = 0, count = 0;
2419 gcov_type cnt = 0;
2420 bool hot = false;
2422 for (src = val->sources; src; src = src->next)
2424 struct cgraph_edge *cs = src->cs;
2425 while (cs)
2427 if (cgraph_edge_brings_value_p (cs, src))
2429 count++;
2430 freq += cs->frequency;
2431 cnt += cs->count;
2432 hot |= cgraph_maybe_hot_edge_p (cs);
2434 cs = get_next_cgraph_edge_clone (cs);
2438 *freq_sum = freq;
2439 *count_sum = cnt;
2440 *caller_count = count;
2441 return hot;
2444 /* Return a vector of incoming edges that do bring value VAL. It is assumed
2445 their number is known and equal to CALLER_COUNT. */
2447 static vec<cgraph_edge_p>
2448 gather_edges_for_value (struct ipcp_value *val, int caller_count)
2450 struct ipcp_value_source *src;
2451 vec<cgraph_edge_p> ret;
2453 ret.create (caller_count);
2454 for (src = val->sources; src; src = src->next)
2456 struct cgraph_edge *cs = src->cs;
2457 while (cs)
2459 if (cgraph_edge_brings_value_p (cs, src))
2460 ret.quick_push (cs);
2461 cs = get_next_cgraph_edge_clone (cs);
2465 return ret;
2468 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
2469 Return it or NULL if for some reason it cannot be created. */
2471 static struct ipa_replace_map *
2472 get_replacement_map (struct ipa_node_params *info, tree value, int parm_num)
2474 struct ipa_replace_map *replace_map;
2477 replace_map = ggc_alloc_ipa_replace_map ();
2478 if (dump_file)
2480 fprintf (dump_file, " replacing ");
2481 ipa_dump_param (dump_file, info, parm_num);
2483 fprintf (dump_file, " with const ");
2484 print_generic_expr (dump_file, value, 0);
2485 fprintf (dump_file, "\n");
2487 replace_map->old_tree = NULL;
2488 replace_map->parm_num = parm_num;
2489 replace_map->new_tree = value;
2490 replace_map->replace_p = true;
2491 replace_map->ref_p = false;
2493 return replace_map;
2496 /* Dump new profiling counts */
2498 static void
2499 dump_profile_updates (struct cgraph_node *orig_node,
2500 struct cgraph_node *new_node)
2502 struct cgraph_edge *cs;
2504 fprintf (dump_file, " setting count of the specialized node to "
2505 HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) new_node->count);
2506 for (cs = new_node->callees; cs ; cs = cs->next_callee)
2507 fprintf (dump_file, " edge to %s has count "
2508 HOST_WIDE_INT_PRINT_DEC "\n",
2509 cgraph_node_name (cs->callee), (HOST_WIDE_INT) cs->count);
2511 fprintf (dump_file, " setting count of the original node to "
2512 HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) orig_node->count);
2513 for (cs = orig_node->callees; cs ; cs = cs->next_callee)
2514 fprintf (dump_file, " edge to %s is left with "
2515 HOST_WIDE_INT_PRINT_DEC "\n",
2516 cgraph_node_name (cs->callee), (HOST_WIDE_INT) cs->count);
2519 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
2520 their profile information to reflect this. */
2522 static void
2523 update_profiling_info (struct cgraph_node *orig_node,
2524 struct cgraph_node *new_node)
2526 struct cgraph_edge *cs;
2527 struct caller_statistics stats;
2528 gcov_type new_sum, orig_sum;
2529 gcov_type remainder, orig_node_count = orig_node->count;
2531 if (orig_node_count == 0)
2532 return;
2534 init_caller_stats (&stats);
2535 cgraph_for_node_and_aliases (orig_node, gather_caller_stats, &stats, false);
2536 orig_sum = stats.count_sum;
2537 init_caller_stats (&stats);
2538 cgraph_for_node_and_aliases (new_node, gather_caller_stats, &stats, false);
2539 new_sum = stats.count_sum;
2541 if (orig_node_count < orig_sum + new_sum)
2543 if (dump_file)
2544 fprintf (dump_file, " Problem: node %s/%i has too low count "
2545 HOST_WIDE_INT_PRINT_DEC " while the sum of incoming "
2546 "counts is " HOST_WIDE_INT_PRINT_DEC "\n",
2547 cgraph_node_name (orig_node), orig_node->order,
2548 (HOST_WIDE_INT) orig_node_count,
2549 (HOST_WIDE_INT) (orig_sum + new_sum));
2551 orig_node_count = (orig_sum + new_sum) * 12 / 10;
2552 if (dump_file)
2553 fprintf (dump_file, " proceeding by pretending it was "
2554 HOST_WIDE_INT_PRINT_DEC "\n",
2555 (HOST_WIDE_INT) orig_node_count);
2558 new_node->count = new_sum;
2559 remainder = orig_node_count - new_sum;
2560 orig_node->count = remainder;
2562 for (cs = new_node->callees; cs ; cs = cs->next_callee)
2563 if (cs->frequency)
2564 cs->count = apply_probability (cs->count,
2565 GCOV_COMPUTE_SCALE (new_sum,
2566 orig_node_count));
2567 else
2568 cs->count = 0;
2570 for (cs = orig_node->callees; cs ; cs = cs->next_callee)
2571 cs->count = apply_probability (cs->count,
2572 GCOV_COMPUTE_SCALE (remainder,
2573 orig_node_count));
2575 if (dump_file)
2576 dump_profile_updates (orig_node, new_node);
2579 /* Update the respective profile of specialized NEW_NODE and the original
2580 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
2581 have been redirected to the specialized version. */
2583 static void
2584 update_specialized_profile (struct cgraph_node *new_node,
2585 struct cgraph_node *orig_node,
2586 gcov_type redirected_sum)
2588 struct cgraph_edge *cs;
2589 gcov_type new_node_count, orig_node_count = orig_node->count;
2591 if (dump_file)
2592 fprintf (dump_file, " the sum of counts of redirected edges is "
2593 HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) redirected_sum);
2594 if (orig_node_count == 0)
2595 return;
2597 gcc_assert (orig_node_count >= redirected_sum);
2599 new_node_count = new_node->count;
2600 new_node->count += redirected_sum;
2601 orig_node->count -= redirected_sum;
2603 for (cs = new_node->callees; cs ; cs = cs->next_callee)
2604 if (cs->frequency)
2605 cs->count += apply_probability (cs->count,
2606 GCOV_COMPUTE_SCALE (redirected_sum,
2607 new_node_count));
2608 else
2609 cs->count = 0;
2611 for (cs = orig_node->callees; cs ; cs = cs->next_callee)
2613 gcov_type dec = apply_probability (cs->count,
2614 GCOV_COMPUTE_SCALE (redirected_sum,
2615 orig_node_count));
2616 if (dec < cs->count)
2617 cs->count -= dec;
2618 else
2619 cs->count = 0;
2622 if (dump_file)
2623 dump_profile_updates (orig_node, new_node);
2626 /* Create a specialized version of NODE with known constants and types of
2627 parameters in KNOWN_VALS and redirect all edges in CALLERS to it. */
2629 static struct cgraph_node *
2630 create_specialized_node (struct cgraph_node *node,
2631 vec<tree> known_vals,
2632 struct ipa_agg_replacement_value *aggvals,
2633 vec<cgraph_edge_p> callers)
2635 struct ipa_node_params *new_info, *info = IPA_NODE_REF (node);
2636 vec<ipa_replace_map_p, va_gc> *replace_trees = NULL;
2637 struct ipa_agg_replacement_value *av;
2638 struct cgraph_node *new_node;
2639 int i, count = ipa_get_param_count (info);
2640 bitmap args_to_skip;
2642 gcc_assert (!info->ipcp_orig_node);
2644 if (node->local.can_change_signature)
2646 args_to_skip = BITMAP_GGC_ALLOC ();
2647 for (i = 0; i < count; i++)
2649 tree t = known_vals[i];
2651 if ((t && TREE_CODE (t) != TREE_BINFO)
2652 || !ipa_is_param_used (info, i))
2653 bitmap_set_bit (args_to_skip, i);
2656 else
2658 args_to_skip = NULL;
2659 if (dump_file && (dump_flags & TDF_DETAILS))
2660 fprintf (dump_file, " cannot change function signature\n");
2663 for (i = 0; i < count ; i++)
2665 tree t = known_vals[i];
2666 if (t && TREE_CODE (t) != TREE_BINFO)
2668 struct ipa_replace_map *replace_map;
2670 replace_map = get_replacement_map (info, t, i);
2671 if (replace_map)
2672 vec_safe_push (replace_trees, replace_map);
2676 new_node = cgraph_create_virtual_clone (node, callers, replace_trees,
2677 args_to_skip, "constprop");
2678 ipa_set_node_agg_value_chain (new_node, aggvals);
2679 for (av = aggvals; av; av = av->next)
2680 ipa_maybe_record_reference (new_node, av->value,
2681 IPA_REF_ADDR, NULL);
2683 if (dump_file && (dump_flags & TDF_DETAILS))
2685 fprintf (dump_file, " the new node is %s/%i.\n",
2686 cgraph_node_name (new_node), new_node->order);
2687 if (aggvals)
2688 ipa_dump_agg_replacement_values (dump_file, aggvals);
2690 gcc_checking_assert (ipa_node_params_vector.exists ()
2691 && (ipa_node_params_vector.length ()
2692 > (unsigned) cgraph_max_uid));
2693 update_profiling_info (node, new_node);
2694 new_info = IPA_NODE_REF (new_node);
2695 new_info->ipcp_orig_node = node;
2696 new_info->known_vals = known_vals;
2698 ipcp_discover_new_direct_edges (new_node, known_vals, aggvals);
2700 callers.release ();
2701 return new_node;
2704 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
2705 KNOWN_VALS with constants and types that are also known for all of the
2706 CALLERS. */
2708 static void
2709 find_more_scalar_values_for_callers_subset (struct cgraph_node *node,
2710 vec<tree> known_vals,
2711 vec<cgraph_edge_p> callers)
2713 struct ipa_node_params *info = IPA_NODE_REF (node);
2714 int i, count = ipa_get_param_count (info);
2716 for (i = 0; i < count ; i++)
2718 struct cgraph_edge *cs;
2719 tree newval = NULL_TREE;
2720 int j;
2722 if (ipa_get_scalar_lat (info, i)->bottom || known_vals[i])
2723 continue;
2725 FOR_EACH_VEC_ELT (callers, j, cs)
2727 struct ipa_jump_func *jump_func;
2728 tree t;
2730 if (i >= ipa_get_cs_argument_count (IPA_EDGE_REF (cs)))
2732 newval = NULL_TREE;
2733 break;
2735 jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
2736 t = ipa_value_from_jfunc (IPA_NODE_REF (cs->caller), jump_func);
2737 if (!t
2738 || (newval
2739 && !values_equal_for_ipcp_p (t, newval)))
2741 newval = NULL_TREE;
2742 break;
2744 else
2745 newval = t;
2748 if (newval)
2750 if (dump_file && (dump_flags & TDF_DETAILS))
2752 fprintf (dump_file, " adding an extra known scalar value ");
2753 print_ipcp_constant_value (dump_file, newval);
2754 fprintf (dump_file, " for ");
2755 ipa_dump_param (dump_file, info, i);
2756 fprintf (dump_file, "\n");
2759 known_vals[i] = newval;
2764 /* Go through PLATS and create a vector of values consisting of values and
2765 offsets (minus OFFSET) of lattices that contain only a single value. */
2767 static vec<ipa_agg_jf_item_t>
2768 copy_plats_to_inter (struct ipcp_param_lattices *plats, HOST_WIDE_INT offset)
2770 vec<ipa_agg_jf_item_t> res = vNULL;
2772 if (!plats->aggs || plats->aggs_contain_variable || plats->aggs_bottom)
2773 return vNULL;
2775 for (struct ipcp_agg_lattice *aglat = plats->aggs; aglat; aglat = aglat->next)
2776 if (ipa_lat_is_single_const (aglat))
2778 struct ipa_agg_jf_item ti;
2779 ti.offset = aglat->offset - offset;
2780 ti.value = aglat->values->value;
2781 res.safe_push (ti);
2783 return res;
2786 /* Intersect all values in INTER with single value lattices in PLATS (while
2787 subtracting OFFSET). */
2789 static void
2790 intersect_with_plats (struct ipcp_param_lattices *plats,
2791 vec<ipa_agg_jf_item_t> *inter,
2792 HOST_WIDE_INT offset)
2794 struct ipcp_agg_lattice *aglat;
2795 struct ipa_agg_jf_item *item;
2796 int k;
2798 if (!plats->aggs || plats->aggs_contain_variable || plats->aggs_bottom)
2800 inter->release ();
2801 return;
2804 aglat = plats->aggs;
2805 FOR_EACH_VEC_ELT (*inter, k, item)
2807 bool found = false;
2808 if (!item->value)
2809 continue;
2810 while (aglat)
2812 if (aglat->offset - offset > item->offset)
2813 break;
2814 if (aglat->offset - offset == item->offset)
2816 gcc_checking_assert (item->value);
2817 if (values_equal_for_ipcp_p (item->value, aglat->values->value))
2818 found = true;
2819 break;
2821 aglat = aglat->next;
2823 if (!found)
2824 item->value = NULL_TREE;
2828 /* Copy agggregate replacement values of NODE (which is an IPA-CP clone) to the
2829 vector result while subtracting OFFSET from the individual value offsets. */
2831 static vec<ipa_agg_jf_item_t>
2832 agg_replacements_to_vector (struct cgraph_node *node, int index,
2833 HOST_WIDE_INT offset)
2835 struct ipa_agg_replacement_value *av;
2836 vec<ipa_agg_jf_item_t> res = vNULL;
2838 for (av = ipa_get_agg_replacements_for_node (node); av; av = av->next)
2839 if (av->index == index
2840 && (av->offset - offset) >= 0)
2842 struct ipa_agg_jf_item item;
2843 gcc_checking_assert (av->value);
2844 item.offset = av->offset - offset;
2845 item.value = av->value;
2846 res.safe_push (item);
2849 return res;
2852 /* Intersect all values in INTER with those that we have already scheduled to
2853 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
2854 (while subtracting OFFSET). */
2856 static void
2857 intersect_with_agg_replacements (struct cgraph_node *node, int index,
2858 vec<ipa_agg_jf_item_t> *inter,
2859 HOST_WIDE_INT offset)
2861 struct ipa_agg_replacement_value *srcvals;
2862 struct ipa_agg_jf_item *item;
2863 int i;
2865 srcvals = ipa_get_agg_replacements_for_node (node);
2866 if (!srcvals)
2868 inter->release ();
2869 return;
2872 FOR_EACH_VEC_ELT (*inter, i, item)
2874 struct ipa_agg_replacement_value *av;
2875 bool found = false;
2876 if (!item->value)
2877 continue;
2878 for (av = srcvals; av; av = av->next)
2880 gcc_checking_assert (av->value);
2881 if (av->index == index
2882 && av->offset - offset == item->offset)
2884 if (values_equal_for_ipcp_p (item->value, av->value))
2885 found = true;
2886 break;
2889 if (!found)
2890 item->value = NULL_TREE;
2894 /* Intersect values in INTER with aggregate values that come along edge CS to
2895 parameter number INDEX and return it. If INTER does not actually exist yet,
2896 copy all incoming values to it. If we determine we ended up with no values
2897 whatsoever, return a released vector. */
2899 static vec<ipa_agg_jf_item_t>
2900 intersect_aggregates_with_edge (struct cgraph_edge *cs, int index,
2901 vec<ipa_agg_jf_item_t> inter)
2903 struct ipa_jump_func *jfunc;
2904 jfunc = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), index);
2905 if (jfunc->type == IPA_JF_PASS_THROUGH
2906 && ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
2908 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
2909 int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
2911 if (caller_info->ipcp_orig_node)
2913 struct cgraph_node *orig_node = caller_info->ipcp_orig_node;
2914 struct ipcp_param_lattices *orig_plats;
2915 orig_plats = ipa_get_parm_lattices (IPA_NODE_REF (orig_node),
2916 src_idx);
2917 if (agg_pass_through_permissible_p (orig_plats, jfunc))
2919 if (!inter.exists ())
2920 inter = agg_replacements_to_vector (cs->caller, src_idx, 0);
2921 else
2922 intersect_with_agg_replacements (cs->caller, src_idx,
2923 &inter, 0);
2926 else
2928 struct ipcp_param_lattices *src_plats;
2929 src_plats = ipa_get_parm_lattices (caller_info, src_idx);
2930 if (agg_pass_through_permissible_p (src_plats, jfunc))
2932 /* Currently we do not produce clobber aggregate jump
2933 functions, adjust when we do. */
2934 gcc_checking_assert (!jfunc->agg.items);
2935 if (!inter.exists ())
2936 inter = copy_plats_to_inter (src_plats, 0);
2937 else
2938 intersect_with_plats (src_plats, &inter, 0);
2942 else if (jfunc->type == IPA_JF_ANCESTOR
2943 && ipa_get_jf_ancestor_agg_preserved (jfunc))
2945 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
2946 int src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
2947 struct ipcp_param_lattices *src_plats;
2948 HOST_WIDE_INT delta = ipa_get_jf_ancestor_offset (jfunc);
2950 if (caller_info->ipcp_orig_node)
2952 if (!inter.exists ())
2953 inter = agg_replacements_to_vector (cs->caller, src_idx, delta);
2954 else
2955 intersect_with_agg_replacements (cs->caller, src_idx, &inter,
2956 delta);
2958 else
2960 src_plats = ipa_get_parm_lattices (caller_info, src_idx);;
2961 /* Currently we do not produce clobber aggregate jump
2962 functions, adjust when we do. */
2963 gcc_checking_assert (!src_plats->aggs || !jfunc->agg.items);
2964 if (!inter.exists ())
2965 inter = copy_plats_to_inter (src_plats, delta);
2966 else
2967 intersect_with_plats (src_plats, &inter, delta);
2970 else if (jfunc->agg.items)
2972 struct ipa_agg_jf_item *item;
2973 int k;
2975 if (!inter.exists ())
2976 for (unsigned i = 0; i < jfunc->agg.items->length (); i++)
2977 inter.safe_push ((*jfunc->agg.items)[i]);
2978 else
2979 FOR_EACH_VEC_ELT (inter, k, item)
2981 int l = 0;
2982 bool found = false;;
2984 if (!item->value)
2985 continue;
2987 while ((unsigned) l < jfunc->agg.items->length ())
2989 struct ipa_agg_jf_item *ti;
2990 ti = &(*jfunc->agg.items)[l];
2991 if (ti->offset > item->offset)
2992 break;
2993 if (ti->offset == item->offset)
2995 gcc_checking_assert (ti->value);
2996 if (values_equal_for_ipcp_p (item->value,
2997 ti->value))
2998 found = true;
2999 break;
3001 l++;
3003 if (!found)
3004 item->value = NULL;
3007 else
3009 inter.release ();
3010 return vec<ipa_agg_jf_item_t>();
3012 return inter;
3015 /* Look at edges in CALLERS and collect all known aggregate values that arrive
3016 from all of them. */
3018 static struct ipa_agg_replacement_value *
3019 find_aggregate_values_for_callers_subset (struct cgraph_node *node,
3020 vec<cgraph_edge_p> callers)
3022 struct ipa_node_params *dest_info = IPA_NODE_REF (node);
3023 struct ipa_agg_replacement_value *res = NULL;
3024 struct cgraph_edge *cs;
3025 int i, j, count = ipa_get_param_count (dest_info);
3027 FOR_EACH_VEC_ELT (callers, j, cs)
3029 int c = ipa_get_cs_argument_count (IPA_EDGE_REF (cs));
3030 if (c < count)
3031 count = c;
3034 for (i = 0; i < count ; i++)
3036 struct cgraph_edge *cs;
3037 vec<ipa_agg_jf_item_t> inter = vNULL;
3038 struct ipa_agg_jf_item *item;
3039 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (dest_info, i);
3040 int j;
3042 /* Among other things, the following check should deal with all by_ref
3043 mismatches. */
3044 if (plats->aggs_bottom)
3045 continue;
3047 FOR_EACH_VEC_ELT (callers, j, cs)
3049 inter = intersect_aggregates_with_edge (cs, i, inter);
3051 if (!inter.exists ())
3052 goto next_param;
3055 FOR_EACH_VEC_ELT (inter, j, item)
3057 struct ipa_agg_replacement_value *v;
3059 if (!item->value)
3060 continue;
3062 v = ggc_alloc_ipa_agg_replacement_value ();
3063 v->index = i;
3064 v->offset = item->offset;
3065 v->value = item->value;
3066 v->by_ref = plats->aggs_by_ref;
3067 v->next = res;
3068 res = v;
3071 next_param:
3072 if (inter.exists ())
3073 inter.release ();
3075 return res;
3078 /* Turn KNOWN_AGGS into a list of aggreate replacement values. */
3080 static struct ipa_agg_replacement_value *
3081 known_aggs_to_agg_replacement_list (vec<ipa_agg_jump_function_t> known_aggs)
3083 struct ipa_agg_replacement_value *res = NULL;
3084 struct ipa_agg_jump_function *aggjf;
3085 struct ipa_agg_jf_item *item;
3086 int i, j;
3088 FOR_EACH_VEC_ELT (known_aggs, i, aggjf)
3089 FOR_EACH_VEC_SAFE_ELT (aggjf->items, j, item)
3091 struct ipa_agg_replacement_value *v;
3092 v = ggc_alloc_ipa_agg_replacement_value ();
3093 v->index = i;
3094 v->offset = item->offset;
3095 v->value = item->value;
3096 v->by_ref = aggjf->by_ref;
3097 v->next = res;
3098 res = v;
3100 return res;
3103 /* Determine whether CS also brings all scalar values that the NODE is
3104 specialized for. */
3106 static bool
3107 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge *cs,
3108 struct cgraph_node *node)
3110 struct ipa_node_params *dest_info = IPA_NODE_REF (node);
3111 int count = ipa_get_param_count (dest_info);
3112 struct ipa_node_params *caller_info;
3113 struct ipa_edge_args *args;
3114 int i;
3116 caller_info = IPA_NODE_REF (cs->caller);
3117 args = IPA_EDGE_REF (cs);
3118 for (i = 0; i < count; i++)
3120 struct ipa_jump_func *jump_func;
3121 tree val, t;
3123 val = dest_info->known_vals[i];
3124 if (!val)
3125 continue;
3127 if (i >= ipa_get_cs_argument_count (args))
3128 return false;
3129 jump_func = ipa_get_ith_jump_func (args, i);
3130 t = ipa_value_from_jfunc (caller_info, jump_func);
3131 if (!t || !values_equal_for_ipcp_p (val, t))
3132 return false;
3134 return true;
3137 /* Determine whether CS also brings all aggregate values that NODE is
3138 specialized for. */
3139 static bool
3140 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge *cs,
3141 struct cgraph_node *node)
3143 struct ipa_node_params *orig_caller_info = IPA_NODE_REF (cs->caller);
3144 struct ipa_agg_replacement_value *aggval;
3145 int i, ec, count;
3147 aggval = ipa_get_agg_replacements_for_node (node);
3148 if (!aggval)
3149 return true;
3151 count = ipa_get_param_count (IPA_NODE_REF (node));
3152 ec = ipa_get_cs_argument_count (IPA_EDGE_REF (cs));
3153 if (ec < count)
3154 for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next)
3155 if (aggval->index >= ec)
3156 return false;
3158 if (orig_caller_info->ipcp_orig_node)
3159 orig_caller_info = IPA_NODE_REF (orig_caller_info->ipcp_orig_node);
3161 for (i = 0; i < count; i++)
3163 static vec<ipa_agg_jf_item_t> values = vec<ipa_agg_jf_item_t>();
3164 struct ipcp_param_lattices *plats;
3165 bool interesting = false;
3166 for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next)
3167 if (aggval->index == i)
3169 interesting = true;
3170 break;
3172 if (!interesting)
3173 continue;
3175 plats = ipa_get_parm_lattices (orig_caller_info, aggval->index);
3176 if (plats->aggs_bottom)
3177 return false;
3179 values = intersect_aggregates_with_edge (cs, i, values);
3180 if (!values.exists ())
3181 return false;
3183 for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next)
3184 if (aggval->index == i)
3186 struct ipa_agg_jf_item *item;
3187 int j;
3188 bool found = false;
3189 FOR_EACH_VEC_ELT (values, j, item)
3190 if (item->value
3191 && item->offset == av->offset
3192 && values_equal_for_ipcp_p (item->value, av->value))
3194 found = true;
3195 break;
3197 if (!found)
3199 values.release ();
3200 return false;
3204 return true;
3207 /* Given an original NODE and a VAL for which we have already created a
3208 specialized clone, look whether there are incoming edges that still lead
3209 into the old node but now also bring the requested value and also conform to
3210 all other criteria such that they can be redirected the the special node.
3211 This function can therefore redirect the final edge in a SCC. */
3213 static void
3214 perhaps_add_new_callers (struct cgraph_node *node, struct ipcp_value *val)
3216 struct ipcp_value_source *src;
3217 gcov_type redirected_sum = 0;
3219 for (src = val->sources; src; src = src->next)
3221 struct cgraph_edge *cs = src->cs;
3222 while (cs)
3224 enum availability availability;
3225 struct cgraph_node *dst = cgraph_function_node (cs->callee,
3226 &availability);
3227 if ((dst == node || IPA_NODE_REF (dst)->is_all_contexts_clone)
3228 && availability > AVAIL_OVERWRITABLE
3229 && cgraph_edge_brings_value_p (cs, src))
3231 if (cgraph_edge_brings_all_scalars_for_node (cs, val->spec_node)
3232 && cgraph_edge_brings_all_agg_vals_for_node (cs,
3233 val->spec_node))
3235 if (dump_file)
3236 fprintf (dump_file, " - adding an extra caller %s/%i"
3237 " of %s/%i\n",
3238 xstrdup (cgraph_node_name (cs->caller)),
3239 cs->caller->order,
3240 xstrdup (cgraph_node_name (val->spec_node)),
3241 val->spec_node->order);
3243 cgraph_redirect_edge_callee (cs, val->spec_node);
3244 redirected_sum += cs->count;
3247 cs = get_next_cgraph_edge_clone (cs);
3251 if (redirected_sum)
3252 update_specialized_profile (val->spec_node, node, redirected_sum);
3256 /* Copy KNOWN_BINFOS to KNOWN_VALS. */
3258 static void
3259 move_binfos_to_values (vec<tree> known_vals,
3260 vec<tree> known_binfos)
3262 tree t;
3263 int i;
3265 for (i = 0; known_binfos.iterate (i, &t); i++)
3266 if (t)
3267 known_vals[i] = t;
3270 /* Return true if there is a replacement equivalent to VALUE, INDEX and OFFSET
3271 among those in the AGGVALS list. */
3273 DEBUG_FUNCTION bool
3274 ipcp_val_in_agg_replacements_p (struct ipa_agg_replacement_value *aggvals,
3275 int index, HOST_WIDE_INT offset, tree value)
3277 while (aggvals)
3279 if (aggvals->index == index
3280 && aggvals->offset == offset
3281 && values_equal_for_ipcp_p (aggvals->value, value))
3282 return true;
3283 aggvals = aggvals->next;
3285 return false;
3288 /* Decide wheter to create a special version of NODE for value VAL of parameter
3289 at the given INDEX. If OFFSET is -1, the value is for the parameter itself,
3290 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS,
3291 KNOWN_BINFOS and KNOWN_AGGS describe the other already known values. */
3293 static bool
3294 decide_about_value (struct cgraph_node *node, int index, HOST_WIDE_INT offset,
3295 struct ipcp_value *val, vec<tree> known_csts,
3296 vec<tree> known_binfos)
3298 struct ipa_agg_replacement_value *aggvals;
3299 int freq_sum, caller_count;
3300 gcov_type count_sum;
3301 vec<cgraph_edge_p> callers;
3302 vec<tree> kv;
3304 if (val->spec_node)
3306 perhaps_add_new_callers (node, val);
3307 return false;
3309 else if (val->local_size_cost + overall_size > max_new_size)
3311 if (dump_file && (dump_flags & TDF_DETAILS))
3312 fprintf (dump_file, " Ignoring candidate value because "
3313 "max_new_size would be reached with %li.\n",
3314 val->local_size_cost + overall_size);
3315 return false;
3317 else if (!get_info_about_necessary_edges (val, &freq_sum, &count_sum,
3318 &caller_count))
3319 return false;
3321 if (dump_file && (dump_flags & TDF_DETAILS))
3323 fprintf (dump_file, " - considering value ");
3324 print_ipcp_constant_value (dump_file, val->value);
3325 fprintf (dump_file, " for ");
3326 ipa_dump_param (dump_file, IPA_NODE_REF (node), index);
3327 if (offset != -1)
3328 fprintf (dump_file, ", offset: " HOST_WIDE_INT_PRINT_DEC, offset);
3329 fprintf (dump_file, " (caller_count: %i)\n", caller_count);
3332 if (!good_cloning_opportunity_p (node, val->local_time_benefit,
3333 freq_sum, count_sum,
3334 val->local_size_cost)
3335 && !good_cloning_opportunity_p (node,
3336 val->local_time_benefit
3337 + val->prop_time_benefit,
3338 freq_sum, count_sum,
3339 val->local_size_cost
3340 + val->prop_size_cost))
3341 return false;
3343 if (dump_file)
3344 fprintf (dump_file, " Creating a specialized node of %s/%i.\n",
3345 cgraph_node_name (node), node->order);
3347 callers = gather_edges_for_value (val, caller_count);
3348 kv = known_csts.copy ();
3349 move_binfos_to_values (kv, known_binfos);
3350 if (offset == -1)
3351 kv[index] = val->value;
3352 find_more_scalar_values_for_callers_subset (node, kv, callers);
3353 aggvals = find_aggregate_values_for_callers_subset (node, callers);
3354 gcc_checking_assert (offset == -1
3355 || ipcp_val_in_agg_replacements_p (aggvals, index,
3356 offset, val->value));
3357 val->spec_node = create_specialized_node (node, kv, aggvals, callers);
3358 overall_size += val->local_size_cost;
3360 /* TODO: If for some lattice there is only one other known value
3361 left, make a special node for it too. */
3363 return true;
3366 /* Decide whether and what specialized clones of NODE should be created. */
3368 static bool
3369 decide_whether_version_node (struct cgraph_node *node)
3371 struct ipa_node_params *info = IPA_NODE_REF (node);
3372 int i, count = ipa_get_param_count (info);
3373 vec<tree> known_csts, known_binfos;
3374 vec<ipa_agg_jump_function_t> known_aggs = vNULL;
3375 bool ret = false;
3377 if (count == 0)
3378 return false;
3380 if (dump_file && (dump_flags & TDF_DETAILS))
3381 fprintf (dump_file, "\nEvaluating opportunities for %s/%i.\n",
3382 cgraph_node_name (node), node->order);
3384 gather_context_independent_values (info, &known_csts, &known_binfos,
3385 info->do_clone_for_all_contexts ? &known_aggs
3386 : NULL, NULL);
3388 for (i = 0; i < count ;i++)
3390 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
3391 struct ipcp_lattice *lat = &plats->itself;
3392 struct ipcp_value *val;
3394 if (!lat->bottom
3395 && !known_csts[i]
3396 && !known_binfos[i])
3397 for (val = lat->values; val; val = val->next)
3398 ret |= decide_about_value (node, i, -1, val, known_csts,
3399 known_binfos);
3401 if (!plats->aggs_bottom)
3403 struct ipcp_agg_lattice *aglat;
3404 struct ipcp_value *val;
3405 for (aglat = plats->aggs; aglat; aglat = aglat->next)
3406 if (!aglat->bottom && aglat->values
3407 /* If the following is false, the one value is in
3408 known_aggs. */
3409 && (plats->aggs_contain_variable
3410 || !ipa_lat_is_single_const (aglat)))
3411 for (val = aglat->values; val; val = val->next)
3412 ret |= decide_about_value (node, i, aglat->offset, val,
3413 known_csts, known_binfos);
3415 info = IPA_NODE_REF (node);
3418 if (info->do_clone_for_all_contexts)
3420 struct cgraph_node *clone;
3421 vec<cgraph_edge_p> callers;
3423 if (dump_file)
3424 fprintf (dump_file, " - Creating a specialized node of %s/%i "
3425 "for all known contexts.\n", cgraph_node_name (node),
3426 node->order);
3428 callers = collect_callers_of_node (node);
3429 move_binfos_to_values (known_csts, known_binfos);
3430 clone = create_specialized_node (node, known_csts,
3431 known_aggs_to_agg_replacement_list (known_aggs),
3432 callers);
3433 info = IPA_NODE_REF (node);
3434 info->do_clone_for_all_contexts = false;
3435 IPA_NODE_REF (clone)->is_all_contexts_clone = true;
3436 for (i = 0; i < count ; i++)
3437 vec_free (known_aggs[i].items);
3438 known_aggs.release ();
3439 ret = true;
3441 else
3442 known_csts.release ();
3444 known_binfos.release ();
3445 return ret;
3448 /* Transitively mark all callees of NODE within the same SCC as not dead. */
3450 static void
3451 spread_undeadness (struct cgraph_node *node)
3453 struct cgraph_edge *cs;
3455 for (cs = node->callees; cs; cs = cs->next_callee)
3456 if (ipa_edge_within_scc (cs))
3458 struct cgraph_node *callee;
3459 struct ipa_node_params *info;
3461 callee = cgraph_function_node (cs->callee, NULL);
3462 info = IPA_NODE_REF (callee);
3464 if (info->node_dead)
3466 info->node_dead = 0;
3467 spread_undeadness (callee);
3472 /* Return true if NODE has a caller from outside of its SCC that is not
3473 dead. Worker callback for cgraph_for_node_and_aliases. */
3475 static bool
3476 has_undead_caller_from_outside_scc_p (struct cgraph_node *node,
3477 void *data ATTRIBUTE_UNUSED)
3479 struct cgraph_edge *cs;
3481 for (cs = node->callers; cs; cs = cs->next_caller)
3482 if (cs->caller->thunk.thunk_p
3483 && cgraph_for_node_and_aliases (cs->caller,
3484 has_undead_caller_from_outside_scc_p,
3485 NULL, true))
3486 return true;
3487 else if (!ipa_edge_within_scc (cs)
3488 && !IPA_NODE_REF (cs->caller)->node_dead)
3489 return true;
3490 return false;
3494 /* Identify nodes within the same SCC as NODE which are no longer needed
3495 because of new clones and will be removed as unreachable. */
3497 static void
3498 identify_dead_nodes (struct cgraph_node *node)
3500 struct cgraph_node *v;
3501 for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
3502 if (cgraph_will_be_removed_from_program_if_no_direct_calls (v)
3503 && !cgraph_for_node_and_aliases (v,
3504 has_undead_caller_from_outside_scc_p,
3505 NULL, true))
3506 IPA_NODE_REF (v)->node_dead = 1;
3508 for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
3509 if (!IPA_NODE_REF (v)->node_dead)
3510 spread_undeadness (v);
3512 if (dump_file && (dump_flags & TDF_DETAILS))
3514 for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
3515 if (IPA_NODE_REF (v)->node_dead)
3516 fprintf (dump_file, " Marking node as dead: %s/%i.\n",
3517 cgraph_node_name (v), v->order);
3521 /* The decision stage. Iterate over the topological order of call graph nodes
3522 TOPO and make specialized clones if deemed beneficial. */
3524 static void
3525 ipcp_decision_stage (struct topo_info *topo)
3527 int i;
3529 if (dump_file)
3530 fprintf (dump_file, "\nIPA decision stage:\n\n");
3532 for (i = topo->nnodes - 1; i >= 0; i--)
3534 struct cgraph_node *node = topo->order[i];
3535 bool change = false, iterate = true;
3537 while (iterate)
3539 struct cgraph_node *v;
3540 iterate = false;
3541 for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
3542 if (cgraph_function_with_gimple_body_p (v)
3543 && ipcp_versionable_function_p (v))
3544 iterate |= decide_whether_version_node (v);
3546 change |= iterate;
3548 if (change)
3549 identify_dead_nodes (node);
3553 /* The IPCP driver. */
3555 static unsigned int
3556 ipcp_driver (void)
3558 struct cgraph_2edge_hook_list *edge_duplication_hook_holder;
3559 struct topo_info topo;
3561 ipa_check_create_node_params ();
3562 ipa_check_create_edge_args ();
3563 grow_next_edge_clone_vector ();
3564 edge_duplication_hook_holder =
3565 cgraph_add_edge_duplication_hook (&ipcp_edge_duplication_hook, NULL);
3566 ipcp_values_pool = create_alloc_pool ("IPA-CP values",
3567 sizeof (struct ipcp_value), 32);
3568 ipcp_sources_pool = create_alloc_pool ("IPA-CP value sources",
3569 sizeof (struct ipcp_value_source), 64);
3570 ipcp_agg_lattice_pool = create_alloc_pool ("IPA_CP aggregate lattices",
3571 sizeof (struct ipcp_agg_lattice),
3572 32);
3573 if (dump_file)
3575 fprintf (dump_file, "\nIPA structures before propagation:\n");
3576 if (dump_flags & TDF_DETAILS)
3577 ipa_print_all_params (dump_file);
3578 ipa_print_all_jump_functions (dump_file);
3581 /* Topological sort. */
3582 build_toporder_info (&topo);
3583 /* Do the interprocedural propagation. */
3584 ipcp_propagate_stage (&topo);
3585 /* Decide what constant propagation and cloning should be performed. */
3586 ipcp_decision_stage (&topo);
3588 /* Free all IPCP structures. */
3589 free_toporder_info (&topo);
3590 next_edge_clone.release ();
3591 cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder);
3592 ipa_free_all_structures_after_ipa_cp ();
3593 if (dump_file)
3594 fprintf (dump_file, "\nIPA constant propagation end\n");
3595 return 0;
3598 /* Initialization and computation of IPCP data structures. This is the initial
3599 intraprocedural analysis of functions, which gathers information to be
3600 propagated later on. */
3602 static void
3603 ipcp_generate_summary (void)
3605 struct cgraph_node *node;
3607 if (dump_file)
3608 fprintf (dump_file, "\nIPA constant propagation start:\n");
3609 ipa_register_cgraph_hooks ();
3611 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
3613 node->local.versionable
3614 = tree_versionable_function_p (node->decl);
3615 ipa_analyze_node (node);
3619 /* Write ipcp summary for nodes in SET. */
3621 static void
3622 ipcp_write_summary (void)
3624 ipa_prop_write_jump_functions ();
3627 /* Read ipcp summary. */
3629 static void
3630 ipcp_read_summary (void)
3632 ipa_prop_read_jump_functions ();
3635 /* Gate for IPCP optimization. */
3637 static bool
3638 cgraph_gate_cp (void)
3640 /* FIXME: We should remove the optimize check after we ensure we never run
3641 IPA passes when not optimizing. */
3642 return flag_ipa_cp && optimize;
3645 namespace {
3647 const pass_data pass_data_ipa_cp =
3649 IPA_PASS, /* type */
3650 "cp", /* name */
3651 OPTGROUP_NONE, /* optinfo_flags */
3652 true, /* has_gate */
3653 true, /* has_execute */
3654 TV_IPA_CONSTANT_PROP, /* tv_id */
3655 0, /* properties_required */
3656 0, /* properties_provided */
3657 0, /* properties_destroyed */
3658 0, /* todo_flags_start */
3659 ( TODO_dump_symtab | TODO_remove_functions ), /* todo_flags_finish */
3662 class pass_ipa_cp : public ipa_opt_pass_d
3664 public:
3665 pass_ipa_cp (gcc::context *ctxt)
3666 : ipa_opt_pass_d (pass_data_ipa_cp, ctxt,
3667 ipcp_generate_summary, /* generate_summary */
3668 ipcp_write_summary, /* write_summary */
3669 ipcp_read_summary, /* read_summary */
3670 ipa_prop_write_all_agg_replacement, /*
3671 write_optimization_summary */
3672 ipa_prop_read_all_agg_replacement, /*
3673 read_optimization_summary */
3674 NULL, /* stmt_fixup */
3675 0, /* function_transform_todo_flags_start */
3676 ipcp_transform_function, /* function_transform */
3677 NULL) /* variable_transform */
3680 /* opt_pass methods: */
3681 bool gate () { return cgraph_gate_cp (); }
3682 unsigned int execute () { return ipcp_driver (); }
3684 }; // class pass_ipa_cp
3686 } // anon namespace
3688 ipa_opt_pass_d *
3689 make_pass_ipa_cp (gcc::context *ctxt)
3691 return new pass_ipa_cp (ctxt);