1 /* Interprocedural constant propagation
2 Copyright (C) 2005-2014 Free Software Foundation, Inc.
3
4 Contributed by Razya Ladelsky <RAZYA@il.ibm.com> and Martin Jambor
5 <mjambor@suse.cz>
6
7 This file is part of GCC.
8
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.
13
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.
18
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/>. */
22
23 /* Interprocedural constant propagation (IPA-CP).
24
25 The goal of this transformation is to
26
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
30
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.
35
36 The algorithm also propagates types and attempts to perform type based
37 devirtualization. Types are propagated much like constants.
38
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.
47
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.
52
53
54 First stage - intraprocedural analysis
55 =======================================
56
57 This phase computes jump_function and modification flags.
58
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:
62
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.
67
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.
70
71 ipcp_generate_summary() is the main function of the first stage.
72
73 Second stage - interprocedural analysis
74 ========================================
75
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.
79
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.
86
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.
92
93 ipcp_propagate_stage() and ipcp_decision_stage() together constitute the
94 third stage.
95
96 Third phase - materialization of clones, call statement updates.
97 ============================================
98
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. */
102
103 #include "config.h"
104 #include "system.h"
105 #include "coretypes.h"
106 #include "tree.h"
107 #include "gimple-fold.h"
108 #include "gimple-expr.h"
109 #include "target.h"
110 #include "ipa-prop.h"
111 #include "bitmap.h"
112 #include "tree-pass.h"
113 #include "flags.h"
114 #include "diagnostic.h"
115 #include "tree-pretty-print.h"
116 #include "tree-inline.h"
117 #include "params.h"
118 #include "ipa-inline.h"
119 #include "ipa-utils.h"
120
121 struct ipcp_value;
122
123 /* Describes a particular source for an IPA-CP value. */
124
125 struct ipcp_value_source
126 {
127 /* Aggregate offset of the source, negative if the source is scalar value of
128 the argument itself. */
129 HOST_WIDE_INT offset;
130 /* The incoming edge that brought the value. */
131 struct cgraph_edge *cs;
132 /* If the jump function that resulted into his value was a pass-through or an
133 ancestor, this is the ipcp_value of the caller from which the described
134 value has been derived. Otherwise it is NULL. */
135 struct ipcp_value *val;
136 /* Next pointer in a linked list of sources of a value. */
137 struct ipcp_value_source *next;
138 /* If the jump function that resulted into his value was a pass-through or an
139 ancestor, this is the index of the parameter of the caller the jump
140 function references. */
141 int index;
142 };
143
144 /* Describes one particular value stored in struct ipcp_lattice. */
145
146 struct ipcp_value
147 {
148 /* The actual value for the given parameter. This is either an IPA invariant
149 or a TREE_BINFO describing a type that can be used for
150 devirtualization. */
151 tree value;
152 /* The list of sources from which this value originates. */
153 struct ipcp_value_source *sources;
154 /* Next pointers in a linked list of all values in a lattice. */
155 struct ipcp_value *next;
156 /* Next pointers in a linked list of values in a strongly connected component
157 of values. */
158 struct ipcp_value *scc_next;
159 /* Next pointers in a linked list of SCCs of values sorted topologically
160 according their sources. */
161 struct ipcp_value *topo_next;
162 /* A specialized node created for this value, NULL if none has been (so far)
163 created. */
164 struct cgraph_node *spec_node;
165 /* Depth first search number and low link for topological sorting of
166 values. */
167 int dfs, low_link;
168 /* Time benefit and size cost that specializing the function for this value
169 would bring about in this function alone. */
170 int local_time_benefit, local_size_cost;
171 /* Time benefit and size cost that specializing the function for this value
172 can bring about in it's callees (transitively). */
173 int prop_time_benefit, prop_size_cost;
174 /* True if this valye is currently on the topo-sort stack. */
175 bool on_stack;
176 };
177
178 /* Lattice describing potential values of a formal parameter of a function, or
179 a part of an aggreagate. TOP is represented by a lattice with zero values
180 and with contains_variable and bottom flags cleared. BOTTOM is represented
181 by a lattice with the bottom flag set. In that case, values and
182 contains_variable flag should be disregarded. */
183
184 struct ipcp_lattice
185 {
186 /* The list of known values and types in this lattice. Note that values are
187 not deallocated if a lattice is set to bottom because there may be value
188 sources referencing them. */
189 struct ipcp_value *values;
190 /* Number of known values and types in this lattice. */
191 int values_count;
192 /* The lattice contains a variable component (in addition to values). */
193 bool contains_variable;
194 /* The value of the lattice is bottom (i.e. variable and unusable for any
195 propagation). */
196 bool bottom;
197 };
198
199 /* Lattice with an offset to describe a part of an aggregate. */
200
201 struct ipcp_agg_lattice : public ipcp_lattice
202 {
203 /* Offset that is being described by this lattice. */
204 HOST_WIDE_INT offset;
205 /* Size so that we don't have to re-compute it every time we traverse the
206 list. Must correspond to TYPE_SIZE of all lat values. */
207 HOST_WIDE_INT size;
208 /* Next element of the linked list. */
209 struct ipcp_agg_lattice *next;
210 };
211
212 /* Structure containing lattices for a parameter itself and for pieces of
213 aggregates that are passed in the parameter or by a reference in a parameter
214 plus some other useful flags. */
215
216 struct ipcp_param_lattices
217 {
218 /* Lattice describing the value of the parameter itself. */
219 struct ipcp_lattice itself;
220 /* Lattices describing aggregate parts. */
221 struct ipcp_agg_lattice *aggs;
222 /* Number of aggregate lattices */
223 int aggs_count;
224 /* True if aggregate data were passed by reference (as opposed to by
225 value). */
226 bool aggs_by_ref;
227 /* All aggregate lattices contain a variable component (in addition to
228 values). */
229 bool aggs_contain_variable;
230 /* The value of all aggregate lattices is bottom (i.e. variable and unusable
231 for any propagation). */
232 bool aggs_bottom;
233
234 /* There is a virtual call based on this parameter. */
235 bool virt_call;
236 };
237
238 /* Allocation pools for values and their sources in ipa-cp. */
239
240 alloc_pool ipcp_values_pool;
241 alloc_pool ipcp_sources_pool;
242 alloc_pool ipcp_agg_lattice_pool;
243
244 /* Maximal count found in program. */
245
246 static gcov_type max_count;
247
248 /* Original overall size of the program. */
249
250 static long overall_size, max_new_size;
251
252 /* Head of the linked list of topologically sorted values. */
253
254 static struct ipcp_value *values_topo;
255
256 /* Return the param lattices structure corresponding to the Ith formal
257 parameter of the function described by INFO. */
258 static inline struct ipcp_param_lattices *
ipa_get_parm_lattices(struct ipa_node_params * info,int i)259 ipa_get_parm_lattices (struct ipa_node_params *info, int i)
260 {
261 gcc_assert (i >= 0 && i < ipa_get_param_count (info));
262 gcc_checking_assert (!info->ipcp_orig_node);
263 gcc_checking_assert (info->lattices);
264 return &(info->lattices[i]);
265 }
266
267 /* Return the lattice corresponding to the scalar value of the Ith formal
268 parameter of the function described by INFO. */
269 static inline struct ipcp_lattice *
ipa_get_scalar_lat(struct ipa_node_params * info,int i)270 ipa_get_scalar_lat (struct ipa_node_params *info, int i)
271 {
272 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
273 return &plats->itself;
274 }
275
276 /* Return whether LAT is a lattice with a single constant and without an
277 undefined value. */
278
279 static inline bool
ipa_lat_is_single_const(struct ipcp_lattice * lat)280 ipa_lat_is_single_const (struct ipcp_lattice *lat)
281 {
282 if (lat->bottom
283 || lat->contains_variable
284 || lat->values_count != 1)
285 return false;
286 else
287 return true;
288 }
289
290 /* Print V which is extracted from a value in a lattice to F. */
291
292 static void
print_ipcp_constant_value(FILE * f,tree v)293 print_ipcp_constant_value (FILE * f, tree v)
294 {
295 if (TREE_CODE (v) == TREE_BINFO)
296 {
297 fprintf (f, "BINFO ");
298 print_generic_expr (f, BINFO_TYPE (v), 0);
299 }
300 else if (TREE_CODE (v) == ADDR_EXPR
301 && TREE_CODE (TREE_OPERAND (v, 0)) == CONST_DECL)
302 {
303 fprintf (f, "& ");
304 print_generic_expr (f, DECL_INITIAL (TREE_OPERAND (v, 0)), 0);
305 }
306 else
307 print_generic_expr (f, v, 0);
308 }
309
310 /* Print a lattice LAT to F. */
311
312 static void
print_lattice(FILE * f,struct ipcp_lattice * lat,bool dump_sources,bool dump_benefits)313 print_lattice (FILE * f, struct ipcp_lattice *lat,
314 bool dump_sources, bool dump_benefits)
315 {
316 struct ipcp_value *val;
317 bool prev = false;
318
319 if (lat->bottom)
320 {
321 fprintf (f, "BOTTOM\n");
322 return;
323 }
324
325 if (!lat->values_count && !lat->contains_variable)
326 {
327 fprintf (f, "TOP\n");
328 return;
329 }
330
331 if (lat->contains_variable)
332 {
333 fprintf (f, "VARIABLE");
334 prev = true;
335 if (dump_benefits)
336 fprintf (f, "\n");
337 }
338
339 for (val = lat->values; val; val = val->next)
340 {
341 if (dump_benefits && prev)
342 fprintf (f, " ");
343 else if (!dump_benefits && prev)
344 fprintf (f, ", ");
345 else
346 prev = true;
347
348 print_ipcp_constant_value (f, val->value);
349
350 if (dump_sources)
351 {
352 struct ipcp_value_source *s;
353
354 fprintf (f, " [from:");
355 for (s = val->sources; s; s = s->next)
356 fprintf (f, " %i(%i)", s->cs->caller->order,
357 s->cs->frequency);
358 fprintf (f, "]");
359 }
360
361 if (dump_benefits)
362 fprintf (f, " [loc_time: %i, loc_size: %i, "
363 "prop_time: %i, prop_size: %i]\n",
364 val->local_time_benefit, val->local_size_cost,
365 val->prop_time_benefit, val->prop_size_cost);
366 }
367 if (!dump_benefits)
368 fprintf (f, "\n");
369 }
370
371 /* Print all ipcp_lattices of all functions to F. */
372
373 static void
print_all_lattices(FILE * f,bool dump_sources,bool dump_benefits)374 print_all_lattices (FILE * f, bool dump_sources, bool dump_benefits)
375 {
376 struct cgraph_node *node;
377 int i, count;
378
379 fprintf (f, "\nLattices:\n");
380 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
381 {
382 struct ipa_node_params *info;
383
384 info = IPA_NODE_REF (node);
385 fprintf (f, " Node: %s/%i:\n", node->name (),
386 node->order);
387 count = ipa_get_param_count (info);
388 for (i = 0; i < count; i++)
389 {
390 struct ipcp_agg_lattice *aglat;
391 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
392 fprintf (f, " param [%d]: ", i);
393 print_lattice (f, &plats->itself, dump_sources, dump_benefits);
394
395 if (plats->virt_call)
396 fprintf (f, " virt_call flag set\n");
397
398 if (plats->aggs_bottom)
399 {
400 fprintf (f, " AGGS BOTTOM\n");
401 continue;
402 }
403 if (plats->aggs_contain_variable)
404 fprintf (f, " AGGS VARIABLE\n");
405 for (aglat = plats->aggs; aglat; aglat = aglat->next)
406 {
407 fprintf (f, " %soffset " HOST_WIDE_INT_PRINT_DEC ": ",
408 plats->aggs_by_ref ? "ref " : "", aglat->offset);
409 print_lattice (f, aglat, dump_sources, dump_benefits);
410 }
411 }
412 }
413 }
414
415 /* Determine whether it is at all technically possible to create clones of NODE
416 and store this information in the ipa_node_params structure associated
417 with NODE. */
418
419 static void
determine_versionability(struct cgraph_node * node)420 determine_versionability (struct cgraph_node *node)
421 {
422 const char *reason = NULL;
423
424 /* There are a number of generic reasons functions cannot be versioned. We
425 also cannot remove parameters if there are type attributes such as fnspec
426 present. */
427 if (node->alias || node->thunk.thunk_p)
428 reason = "alias or thunk";
429 else if (!node->local.versionable)
430 reason = "not a tree_versionable_function";
431 else if (cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE)
432 reason = "insufficient body availability";
433 else if (!opt_for_fn (node->decl, optimize)
434 || !opt_for_fn (node->decl, flag_ipa_cp))
435 reason = "non-optimized function";
436 else if (node->tm_clone)
437 reason = "transactional memory clone";
438 else if (lookup_attribute ("omp declare simd", DECL_ATTRIBUTES (node->decl)))
439 {
440 /* Ideally we should clone the SIMD clones themselves and create
441 vector copies of them, so IPA-cp and SIMD clones can happily
442 coexist, but that may not be worth the effort. */
443 reason = "function has SIMD clones";
444 }
445 /* Don't clone decls local to a comdat group; it breaks and for C++
446 decloned constructors, inlining is always better anyway. */
447 else if (symtab_comdat_local_p (node))
448 reason = "comdat-local function";
449
450 if (reason && dump_file && !node->alias && !node->thunk.thunk_p)
451 fprintf (dump_file, "Function %s/%i is not versionable, reason: %s.\n",
452 node->name (), node->order, reason);
453
454 node->local.versionable = (reason == NULL);
455 }
456
457 /* Return true if it is at all technically possible to create clones of a
458 NODE. */
459
460 static bool
ipcp_versionable_function_p(struct cgraph_node * node)461 ipcp_versionable_function_p (struct cgraph_node *node)
462 {
463 return node->local.versionable;
464 }
465
466 /* Structure holding accumulated information about callers of a node. */
467
468 struct caller_statistics
469 {
470 gcov_type count_sum;
471 int n_calls, n_hot_calls, freq_sum;
472 };
473
474 /* Initialize fields of STAT to zeroes. */
475
476 static inline void
init_caller_stats(struct caller_statistics * stats)477 init_caller_stats (struct caller_statistics *stats)
478 {
479 stats->count_sum = 0;
480 stats->n_calls = 0;
481 stats->n_hot_calls = 0;
482 stats->freq_sum = 0;
483 }
484
485 /* Worker callback of cgraph_for_node_and_aliases accumulating statistics of
486 non-thunk incoming edges to NODE. */
487
488 static bool
gather_caller_stats(struct cgraph_node * node,void * data)489 gather_caller_stats (struct cgraph_node *node, void *data)
490 {
491 struct caller_statistics *stats = (struct caller_statistics *) data;
492 struct cgraph_edge *cs;
493
494 for (cs = node->callers; cs; cs = cs->next_caller)
495 if (cs->caller->thunk.thunk_p)
496 cgraph_for_node_and_aliases (cs->caller, gather_caller_stats,
497 stats, false);
498 else
499 {
500 stats->count_sum += cs->count;
501 stats->freq_sum += cs->frequency;
502 stats->n_calls++;
503 if (cgraph_maybe_hot_edge_p (cs))
504 stats->n_hot_calls ++;
505 }
506 return false;
507
508 }
509
510 /* Return true if this NODE is viable candidate for cloning. */
511
512 static bool
ipcp_cloning_candidate_p(struct cgraph_node * node)513 ipcp_cloning_candidate_p (struct cgraph_node *node)
514 {
515 struct caller_statistics stats;
516
517 gcc_checking_assert (cgraph_function_with_gimple_body_p (node));
518
519 if (!flag_ipa_cp_clone)
520 {
521 if (dump_file)
522 fprintf (dump_file, "Not considering %s for cloning; "
523 "-fipa-cp-clone disabled.\n",
524 node->name ());
525 return false;
526 }
527
528 if (!optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node->decl)))
529 {
530 if (dump_file)
531 fprintf (dump_file, "Not considering %s for cloning; "
532 "optimizing it for size.\n",
533 node->name ());
534 return false;
535 }
536
537 init_caller_stats (&stats);
538 cgraph_for_node_and_aliases (node, gather_caller_stats, &stats, false);
539
540 if (inline_summary (node)->self_size < stats.n_calls)
541 {
542 if (dump_file)
543 fprintf (dump_file, "Considering %s for cloning; code might shrink.\n",
544 node->name ());
545 return true;
546 }
547
548 /* When profile is available and function is hot, propagate into it even if
549 calls seems cold; constant propagation can improve function's speed
550 significantly. */
551 if (max_count)
552 {
553 if (stats.count_sum > node->count * 90 / 100)
554 {
555 if (dump_file)
556 fprintf (dump_file, "Considering %s for cloning; "
557 "usually called directly.\n",
558 node->name ());
559 return true;
560 }
561 }
562 if (!stats.n_hot_calls)
563 {
564 if (dump_file)
565 fprintf (dump_file, "Not considering %s for cloning; no hot calls.\n",
566 node->name ());
567 return false;
568 }
569 if (dump_file)
570 fprintf (dump_file, "Considering %s for cloning.\n",
571 node->name ());
572 return true;
573 }
574
575 /* Arrays representing a topological ordering of call graph nodes and a stack
576 of noes used during constant propagation. */
577
578 struct topo_info
579 {
580 struct cgraph_node **order;
581 struct cgraph_node **stack;
582 int nnodes, stack_top;
583 };
584
585 /* Allocate the arrays in TOPO and topologically sort the nodes into order. */
586
587 static void
build_toporder_info(struct topo_info * topo)588 build_toporder_info (struct topo_info *topo)
589 {
590 topo->order = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
591 topo->stack = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
592 topo->stack_top = 0;
593 topo->nnodes = ipa_reduced_postorder (topo->order, true, true, NULL);
594 }
595
596 /* Free information about strongly connected components and the arrays in
597 TOPO. */
598
599 static void
free_toporder_info(struct topo_info * topo)600 free_toporder_info (struct topo_info *topo)
601 {
602 ipa_free_postorder_info ();
603 free (topo->order);
604 free (topo->stack);
605 }
606
607 /* Add NODE to the stack in TOPO, unless it is already there. */
608
609 static inline void
push_node_to_stack(struct topo_info * topo,struct cgraph_node * node)610 push_node_to_stack (struct topo_info *topo, struct cgraph_node *node)
611 {
612 struct ipa_node_params *info = IPA_NODE_REF (node);
613 if (info->node_enqueued)
614 return;
615 info->node_enqueued = 1;
616 topo->stack[topo->stack_top++] = node;
617 }
618
619 /* Pop a node from the stack in TOPO and return it or return NULL if the stack
620 is empty. */
621
622 static struct cgraph_node *
pop_node_from_stack(struct topo_info * topo)623 pop_node_from_stack (struct topo_info *topo)
624 {
625 if (topo->stack_top)
626 {
627 struct cgraph_node *node;
628 topo->stack_top--;
629 node = topo->stack[topo->stack_top];
630 IPA_NODE_REF (node)->node_enqueued = 0;
631 return node;
632 }
633 else
634 return NULL;
635 }
636
637 /* Set lattice LAT to bottom and return true if it previously was not set as
638 such. */
639
640 static inline bool
set_lattice_to_bottom(struct ipcp_lattice * lat)641 set_lattice_to_bottom (struct ipcp_lattice *lat)
642 {
643 bool ret = !lat->bottom;
644 lat->bottom = true;
645 return ret;
646 }
647
648 /* Mark lattice as containing an unknown value and return true if it previously
649 was not marked as such. */
650
651 static inline bool
set_lattice_contains_variable(struct ipcp_lattice * lat)652 set_lattice_contains_variable (struct ipcp_lattice *lat)
653 {
654 bool ret = !lat->contains_variable;
655 lat->contains_variable = true;
656 return ret;
657 }
658
659 /* Set all aggegate lattices in PLATS to bottom and return true if they were
660 not previously set as such. */
661
662 static inline bool
set_agg_lats_to_bottom(struct ipcp_param_lattices * plats)663 set_agg_lats_to_bottom (struct ipcp_param_lattices *plats)
664 {
665 bool ret = !plats->aggs_bottom;
666 plats->aggs_bottom = true;
667 return ret;
668 }
669
670 /* Mark all aggegate lattices in PLATS as containing an unknown value and
671 return true if they were not previously marked as such. */
672
673 static inline bool
set_agg_lats_contain_variable(struct ipcp_param_lattices * plats)674 set_agg_lats_contain_variable (struct ipcp_param_lattices *plats)
675 {
676 bool ret = !plats->aggs_contain_variable;
677 plats->aggs_contain_variable = true;
678 return ret;
679 }
680
681 /* Mark bot aggregate and scalar lattices as containing an unknown variable,
682 return true is any of them has not been marked as such so far. */
683
684 static inline bool
set_all_contains_variable(struct ipcp_param_lattices * plats)685 set_all_contains_variable (struct ipcp_param_lattices *plats)
686 {
687 bool ret = !plats->itself.contains_variable || !plats->aggs_contain_variable;
688 plats->itself.contains_variable = true;
689 plats->aggs_contain_variable = true;
690 return ret;
691 }
692
693 /* Initialize ipcp_lattices. */
694
695 static void
initialize_node_lattices(struct cgraph_node * node)696 initialize_node_lattices (struct cgraph_node *node)
697 {
698 struct ipa_node_params *info = IPA_NODE_REF (node);
699 struct cgraph_edge *ie;
700 bool disable = false, variable = false;
701 int i;
702
703 gcc_checking_assert (cgraph_function_with_gimple_body_p (node));
704 if (!node->local.local)
705 {
706 /* When cloning is allowed, we can assume that externally visible
707 functions are not called. We will compensate this by cloning
708 later. */
709 if (ipcp_versionable_function_p (node)
710 && ipcp_cloning_candidate_p (node))
711 variable = true;
712 else
713 disable = true;
714 }
715
716 if (disable || variable)
717 {
718 for (i = 0; i < ipa_get_param_count (info) ; i++)
719 {
720 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
721 if (disable)
722 {
723 set_lattice_to_bottom (&plats->itself);
724 set_agg_lats_to_bottom (plats);
725 }
726 else
727 set_all_contains_variable (plats);
728 }
729 if (dump_file && (dump_flags & TDF_DETAILS)
730 && !node->alias && !node->thunk.thunk_p)
731 fprintf (dump_file, "Marking all lattices of %s/%i as %s\n",
732 node->name (), node->order,
733 disable ? "BOTTOM" : "VARIABLE");
734 }
735
736 for (ie = node->indirect_calls; ie; ie = ie->next_callee)
737 if (ie->indirect_info->polymorphic
738 && ie->indirect_info->param_index >= 0)
739 {
740 gcc_checking_assert (ie->indirect_info->param_index >= 0);
741 ipa_get_parm_lattices (info,
742 ie->indirect_info->param_index)->virt_call = 1;
743 }
744 }
745
746 /* Return the result of a (possibly arithmetic) pass through jump function
747 JFUNC on the constant value INPUT. Return NULL_TREE if that cannot be
748 determined or be considered an interprocedural invariant. */
749
750 static tree
ipa_get_jf_pass_through_result(struct ipa_jump_func * jfunc,tree input)751 ipa_get_jf_pass_through_result (struct ipa_jump_func *jfunc, tree input)
752 {
753 tree restype, res;
754
755 if (TREE_CODE (input) == TREE_BINFO)
756 {
757 if (ipa_get_jf_pass_through_type_preserved (jfunc))
758 {
759 gcc_checking_assert (ipa_get_jf_pass_through_operation (jfunc)
760 == NOP_EXPR);
761 return input;
762 }
763 return NULL_TREE;
764 }
765
766 if (ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
767 return input;
768
769 gcc_checking_assert (is_gimple_ip_invariant (input));
770 if (TREE_CODE_CLASS (ipa_get_jf_pass_through_operation (jfunc))
771 == tcc_comparison)
772 restype = boolean_type_node;
773 else
774 restype = TREE_TYPE (input);
775 res = fold_binary (ipa_get_jf_pass_through_operation (jfunc), restype,
776 input, ipa_get_jf_pass_through_operand (jfunc));
777
778 if (res && !is_gimple_ip_invariant (res))
779 return NULL_TREE;
780
781 return res;
782 }
783
784 /* Return the result of an ancestor jump function JFUNC on the constant value
785 INPUT. Return NULL_TREE if that cannot be determined. */
786
787 static tree
ipa_get_jf_ancestor_result(struct ipa_jump_func * jfunc,tree input)788 ipa_get_jf_ancestor_result (struct ipa_jump_func *jfunc, tree input)
789 {
790 if (TREE_CODE (input) == TREE_BINFO)
791 {
792 if (!ipa_get_jf_ancestor_type_preserved (jfunc))
793 return NULL;
794 return get_binfo_at_offset (input,
795 ipa_get_jf_ancestor_offset (jfunc),
796 ipa_get_jf_ancestor_type (jfunc));
797 }
798 else if (TREE_CODE (input) == ADDR_EXPR)
799 {
800 tree t = TREE_OPERAND (input, 0);
801 t = build_ref_for_offset (EXPR_LOCATION (t), t,
802 ipa_get_jf_ancestor_offset (jfunc),
803 ipa_get_jf_ancestor_type (jfunc)
804 ? ipa_get_jf_ancestor_type (jfunc)
805 : ptr_type_node, NULL, false);
806 return build_fold_addr_expr (t);
807 }
808 else
809 return NULL_TREE;
810 }
811
812 /* Determine whether JFUNC evaluates to a known value (that is either a
813 constant or a binfo) and if so, return it. Otherwise return NULL. INFO
814 describes the caller node so that pass-through jump functions can be
815 evaluated. */
816
817 tree
ipa_value_from_jfunc(struct ipa_node_params * info,struct ipa_jump_func * jfunc)818 ipa_value_from_jfunc (struct ipa_node_params *info, struct ipa_jump_func *jfunc)
819 {
820 if (jfunc->type == IPA_JF_CONST)
821 return ipa_get_jf_constant (jfunc);
822 else if (jfunc->type == IPA_JF_KNOWN_TYPE)
823 return ipa_binfo_from_known_type_jfunc (jfunc);
824 else if (jfunc->type == IPA_JF_PASS_THROUGH
825 || jfunc->type == IPA_JF_ANCESTOR)
826 {
827 tree input;
828 int idx;
829
830 if (jfunc->type == IPA_JF_PASS_THROUGH)
831 idx = ipa_get_jf_pass_through_formal_id (jfunc);
832 else
833 idx = ipa_get_jf_ancestor_formal_id (jfunc);
834
835 if (info->ipcp_orig_node)
836 input = info->known_vals[idx];
837 else
838 {
839 struct ipcp_lattice *lat;
840
841 if (!info->lattices)
842 {
843 gcc_checking_assert (!flag_ipa_cp);
844 return NULL_TREE;
845 }
846 lat = ipa_get_scalar_lat (info, idx);
847 if (!ipa_lat_is_single_const (lat))
848 return NULL_TREE;
849 input = lat->values->value;
850 }
851
852 if (!input)
853 return NULL_TREE;
854
855 if (jfunc->type == IPA_JF_PASS_THROUGH)
856 return ipa_get_jf_pass_through_result (jfunc, input);
857 else
858 return ipa_get_jf_ancestor_result (jfunc, input);
859 }
860 else
861 return NULL_TREE;
862 }
863
864
865 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
866 bottom, not containing a variable component and without any known value at
867 the same time. */
868
869 DEBUG_FUNCTION void
ipcp_verify_propagated_values(void)870 ipcp_verify_propagated_values (void)
871 {
872 struct cgraph_node *node;
873
874 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
875 {
876 struct ipa_node_params *info = IPA_NODE_REF (node);
877 int i, count = ipa_get_param_count (info);
878
879 for (i = 0; i < count; i++)
880 {
881 struct ipcp_lattice *lat = ipa_get_scalar_lat (info, i);
882
883 if (!lat->bottom
884 && !lat->contains_variable
885 && lat->values_count == 0)
886 {
887 if (dump_file)
888 {
889 dump_symtab (dump_file);
890 fprintf (dump_file, "\nIPA lattices after constant "
891 "propagation, before gcc_unreachable:\n");
892 print_all_lattices (dump_file, true, false);
893 }
894
895 gcc_unreachable ();
896 }
897 }
898 }
899 }
900
901 /* Return true iff X and Y should be considered equal values by IPA-CP. */
902
903 static bool
values_equal_for_ipcp_p(tree x,tree y)904 values_equal_for_ipcp_p (tree x, tree y)
905 {
906 gcc_checking_assert (x != NULL_TREE && y != NULL_TREE);
907
908 if (x == y)
909 return true;
910
911 if (TREE_CODE (x) == TREE_BINFO || TREE_CODE (y) == TREE_BINFO)
912 return false;
913
914 if (TREE_CODE (x) == ADDR_EXPR
915 && TREE_CODE (y) == ADDR_EXPR
916 && TREE_CODE (TREE_OPERAND (x, 0)) == CONST_DECL
917 && TREE_CODE (TREE_OPERAND (y, 0)) == CONST_DECL)
918 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x, 0)),
919 DECL_INITIAL (TREE_OPERAND (y, 0)), 0);
920 else
921 return operand_equal_p (x, y, 0);
922 }
923
924 /* Add a new value source to VAL, marking that a value comes from edge CS and
925 (if the underlying jump function is a pass-through or an ancestor one) from
926 a caller value SRC_VAL of a caller parameter described by SRC_INDEX. OFFSET
927 is negative if the source was the scalar value of the parameter itself or
928 the offset within an aggregate. */
929
930 static void
add_value_source(struct ipcp_value * val,struct cgraph_edge * cs,struct ipcp_value * src_val,int src_idx,HOST_WIDE_INT offset)931 add_value_source (struct ipcp_value *val, struct cgraph_edge *cs,
932 struct ipcp_value *src_val, int src_idx, HOST_WIDE_INT offset)
933 {
934 struct ipcp_value_source *src;
935
936 src = (struct ipcp_value_source *) pool_alloc (ipcp_sources_pool);
937 src->offset = offset;
938 src->cs = cs;
939 src->val = src_val;
940 src->index = src_idx;
941
942 src->next = val->sources;
943 val->sources = src;
944 }
945
946 /* Try to add NEWVAL to LAT, potentially creating a new struct ipcp_value for
947 it. CS, SRC_VAL SRC_INDEX and OFFSET are meant for add_value_source and
948 have the same meaning. */
949
950 static bool
add_value_to_lattice(struct ipcp_lattice * lat,tree newval,struct cgraph_edge * cs,struct ipcp_value * src_val,int src_idx,HOST_WIDE_INT offset)951 add_value_to_lattice (struct ipcp_lattice *lat, tree newval,
952 struct cgraph_edge *cs, struct ipcp_value *src_val,
953 int src_idx, HOST_WIDE_INT offset)
954 {
955 struct ipcp_value *val;
956
957 if (lat->bottom)
958 return false;
959
960 for (val = lat->values; val; val = val->next)
961 if (values_equal_for_ipcp_p (val->value, newval))
962 {
963 if (ipa_edge_within_scc (cs))
964 {
965 struct ipcp_value_source *s;
966 for (s = val->sources; s ; s = s->next)
967 if (s->cs == cs)
968 break;
969 if (s)
970 return false;
971 }
972
973 add_value_source (val, cs, src_val, src_idx, offset);
974 return false;
975 }
976
977 if (lat->values_count == PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE))
978 {
979 /* We can only free sources, not the values themselves, because sources
980 of other values in this this SCC might point to them. */
981 for (val = lat->values; val; val = val->next)
982 {
983 while (val->sources)
984 {
985 struct ipcp_value_source *src = val->sources;
986 val->sources = src->next;
987 pool_free (ipcp_sources_pool, src);
988 }
989 }
990
991 lat->values = NULL;
992 return set_lattice_to_bottom (lat);
993 }
994
995 lat->values_count++;
996 val = (struct ipcp_value *) pool_alloc (ipcp_values_pool);
997 memset (val, 0, sizeof (*val));
998
999 add_value_source (val, cs, src_val, src_idx, offset);
1000 val->value = newval;
1001 val->next = lat->values;
1002 lat->values = val;
1003 return true;
1004 }
1005
1006 /* Like above but passes a special value of offset to distinguish that the
1007 origin is the scalar value of the parameter rather than a part of an
1008 aggregate. */
1009
1010 static inline bool
add_scalar_value_to_lattice(struct ipcp_lattice * lat,tree newval,struct cgraph_edge * cs,struct ipcp_value * src_val,int src_idx)1011 add_scalar_value_to_lattice (struct ipcp_lattice *lat, tree newval,
1012 struct cgraph_edge *cs,
1013 struct ipcp_value *src_val, int src_idx)
1014 {
1015 return add_value_to_lattice (lat, newval, cs, src_val, src_idx, -1);
1016 }
1017
1018 /* Propagate values through a pass-through jump function JFUNC associated with
1019 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1020 is the index of the source parameter. */
1021
1022 static bool
propagate_vals_accross_pass_through(struct cgraph_edge * cs,struct ipa_jump_func * jfunc,struct ipcp_lattice * src_lat,struct ipcp_lattice * dest_lat,int src_idx)1023 propagate_vals_accross_pass_through (struct cgraph_edge *cs,
1024 struct ipa_jump_func *jfunc,
1025 struct ipcp_lattice *src_lat,
1026 struct ipcp_lattice *dest_lat,
1027 int src_idx)
1028 {
1029 struct ipcp_value *src_val;
1030 bool ret = false;
1031
1032 /* Do not create new values when propagating within an SCC because if there
1033 are arithmetic functions with circular dependencies, there is infinite
1034 number of them and we would just make lattices bottom. */
1035 if ((ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR)
1036 && ipa_edge_within_scc (cs))
1037 ret = set_lattice_contains_variable (dest_lat);
1038 else
1039 for (src_val = src_lat->values; src_val; src_val = src_val->next)
1040 {
1041 tree cstval = ipa_get_jf_pass_through_result (jfunc, src_val->value);
1042
1043 if (cstval)
1044 ret |= add_scalar_value_to_lattice (dest_lat, cstval, cs, src_val,
1045 src_idx);
1046 else
1047 ret |= set_lattice_contains_variable (dest_lat);
1048 }
1049
1050 return ret;
1051 }
1052
1053 /* Propagate values through an ancestor jump function JFUNC associated with
1054 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1055 is the index of the source parameter. */
1056
1057 static bool
propagate_vals_accross_ancestor(struct cgraph_edge * cs,struct ipa_jump_func * jfunc,struct ipcp_lattice * src_lat,struct ipcp_lattice * dest_lat,int src_idx)1058 propagate_vals_accross_ancestor (struct cgraph_edge *cs,
1059 struct ipa_jump_func *jfunc,
1060 struct ipcp_lattice *src_lat,
1061 struct ipcp_lattice *dest_lat,
1062 int src_idx)
1063 {
1064 struct ipcp_value *src_val;
1065 bool ret = false;
1066
1067 if (ipa_edge_within_scc (cs))
1068 return set_lattice_contains_variable (dest_lat);
1069
1070 for (src_val = src_lat->values; src_val; src_val = src_val->next)
1071 {
1072 tree t = ipa_get_jf_ancestor_result (jfunc, src_val->value);
1073
1074 if (t)
1075 ret |= add_scalar_value_to_lattice (dest_lat, t, cs, src_val, src_idx);
1076 else
1077 ret |= set_lattice_contains_variable (dest_lat);
1078 }
1079
1080 return ret;
1081 }
1082
1083 /* Propagate scalar values across jump function JFUNC that is associated with
1084 edge CS and put the values into DEST_LAT. */
1085
1086 static bool
propagate_scalar_accross_jump_function(struct cgraph_edge * cs,struct ipa_jump_func * jfunc,struct ipcp_lattice * dest_lat)1087 propagate_scalar_accross_jump_function (struct cgraph_edge *cs,
1088 struct ipa_jump_func *jfunc,
1089 struct ipcp_lattice *dest_lat)
1090 {
1091 if (dest_lat->bottom)
1092 return false;
1093
1094 if (jfunc->type == IPA_JF_CONST
1095 || jfunc->type == IPA_JF_KNOWN_TYPE)
1096 {
1097 tree val;
1098
1099 if (jfunc->type == IPA_JF_KNOWN_TYPE)
1100 {
1101 val = ipa_binfo_from_known_type_jfunc (jfunc);
1102 if (!val)
1103 return set_lattice_contains_variable (dest_lat);
1104 }
1105 else
1106 val = ipa_get_jf_constant (jfunc);
1107 return add_scalar_value_to_lattice (dest_lat, val, cs, NULL, 0);
1108 }
1109 else if (jfunc->type == IPA_JF_PASS_THROUGH
1110 || jfunc->type == IPA_JF_ANCESTOR)
1111 {
1112 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1113 struct ipcp_lattice *src_lat;
1114 int src_idx;
1115 bool ret;
1116
1117 if (jfunc->type == IPA_JF_PASS_THROUGH)
1118 src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
1119 else
1120 src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
1121
1122 src_lat = ipa_get_scalar_lat (caller_info, src_idx);
1123 if (src_lat->bottom)
1124 return set_lattice_contains_variable (dest_lat);
1125
1126 /* If we would need to clone the caller and cannot, do not propagate. */
1127 if (!ipcp_versionable_function_p (cs->caller)
1128 && (src_lat->contains_variable
1129 || (src_lat->values_count > 1)))
1130 return set_lattice_contains_variable (dest_lat);
1131
1132 if (jfunc->type == IPA_JF_PASS_THROUGH)
1133 ret = propagate_vals_accross_pass_through (cs, jfunc, src_lat,
1134 dest_lat, src_idx);
1135 else
1136 ret = propagate_vals_accross_ancestor (cs, jfunc, src_lat, dest_lat,
1137 src_idx);
1138
1139 if (src_lat->contains_variable)
1140 ret |= set_lattice_contains_variable (dest_lat);
1141
1142 return ret;
1143 }
1144
1145 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1146 use it for indirect inlining), we should propagate them too. */
1147 return set_lattice_contains_variable (dest_lat);
1148 }
1149
1150 /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
1151 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
1152 other cases, return false). If there are no aggregate items, set
1153 aggs_by_ref to NEW_AGGS_BY_REF. */
1154
1155 static bool
set_check_aggs_by_ref(struct ipcp_param_lattices * dest_plats,bool new_aggs_by_ref)1156 set_check_aggs_by_ref (struct ipcp_param_lattices *dest_plats,
1157 bool new_aggs_by_ref)
1158 {
1159 if (dest_plats->aggs)
1160 {
1161 if (dest_plats->aggs_by_ref != new_aggs_by_ref)
1162 {
1163 set_agg_lats_to_bottom (dest_plats);
1164 return true;
1165 }
1166 }
1167 else
1168 dest_plats->aggs_by_ref = new_aggs_by_ref;
1169 return false;
1170 }
1171
1172 /* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
1173 already existing lattice for the given OFFSET and SIZE, marking all skipped
1174 lattices as containing variable and checking for overlaps. If there is no
1175 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
1176 it with offset, size and contains_variable to PRE_EXISTING, and return true,
1177 unless there are too many already. If there are two many, return false. If
1178 there are overlaps turn whole DEST_PLATS to bottom and return false. If any
1179 skipped lattices were newly marked as containing variable, set *CHANGE to
1180 true. */
1181
1182 static bool
merge_agg_lats_step(struct ipcp_param_lattices * dest_plats,HOST_WIDE_INT offset,HOST_WIDE_INT val_size,struct ipcp_agg_lattice *** aglat,bool pre_existing,bool * change)1183 merge_agg_lats_step (struct ipcp_param_lattices *dest_plats,
1184 HOST_WIDE_INT offset, HOST_WIDE_INT val_size,
1185 struct ipcp_agg_lattice ***aglat,
1186 bool pre_existing, bool *change)
1187 {
1188 gcc_checking_assert (offset >= 0);
1189
1190 while (**aglat && (**aglat)->offset < offset)
1191 {
1192 if ((**aglat)->offset + (**aglat)->size > offset)
1193 {
1194 set_agg_lats_to_bottom (dest_plats);
1195 return false;
1196 }
1197 *change |= set_lattice_contains_variable (**aglat);
1198 *aglat = &(**aglat)->next;
1199 }
1200
1201 if (**aglat && (**aglat)->offset == offset)
1202 {
1203 if ((**aglat)->size != val_size
1204 || ((**aglat)->next
1205 && (**aglat)->next->offset < offset + val_size))
1206 {
1207 set_agg_lats_to_bottom (dest_plats);
1208 return false;
1209 }
1210 gcc_checking_assert (!(**aglat)->next
1211 || (**aglat)->next->offset >= offset + val_size);
1212 return true;
1213 }
1214 else
1215 {
1216 struct ipcp_agg_lattice *new_al;
1217
1218 if (**aglat && (**aglat)->offset < offset + val_size)
1219 {
1220 set_agg_lats_to_bottom (dest_plats);
1221 return false;
1222 }
1223 if (dest_plats->aggs_count == PARAM_VALUE (PARAM_IPA_MAX_AGG_ITEMS))
1224 return false;
1225 dest_plats->aggs_count++;
1226 new_al = (struct ipcp_agg_lattice *) pool_alloc (ipcp_agg_lattice_pool);
1227 memset (new_al, 0, sizeof (*new_al));
1228
1229 new_al->offset = offset;
1230 new_al->size = val_size;
1231 new_al->contains_variable = pre_existing;
1232
1233 new_al->next = **aglat;
1234 **aglat = new_al;
1235 return true;
1236 }
1237 }
1238
1239 /* Set all AGLAT and all other aggregate lattices reachable by next pointers as
1240 containing an unknown value. */
1241
1242 static bool
set_chain_of_aglats_contains_variable(struct ipcp_agg_lattice * aglat)1243 set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice *aglat)
1244 {
1245 bool ret = false;
1246 while (aglat)
1247 {
1248 ret |= set_lattice_contains_variable (aglat);
1249 aglat = aglat->next;
1250 }
1251 return ret;
1252 }
1253
1254 /* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
1255 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source
1256 parameter used for lattice value sources. Return true if DEST_PLATS changed
1257 in any way. */
1258
1259 static bool
merge_aggregate_lattices(struct cgraph_edge * cs,struct ipcp_param_lattices * dest_plats,struct ipcp_param_lattices * src_plats,int src_idx,HOST_WIDE_INT offset_delta)1260 merge_aggregate_lattices (struct cgraph_edge *cs,
1261 struct ipcp_param_lattices *dest_plats,
1262 struct ipcp_param_lattices *src_plats,
1263 int src_idx, HOST_WIDE_INT offset_delta)
1264 {
1265 bool pre_existing = dest_plats->aggs != NULL;
1266 struct ipcp_agg_lattice **dst_aglat;
1267 bool ret = false;
1268
1269 if (set_check_aggs_by_ref (dest_plats, src_plats->aggs_by_ref))
1270 return true;
1271 if (src_plats->aggs_bottom)
1272 return set_agg_lats_contain_variable (dest_plats);
1273 if (src_plats->aggs_contain_variable)
1274 ret |= set_agg_lats_contain_variable (dest_plats);
1275 dst_aglat = &dest_plats->aggs;
1276
1277 for (struct ipcp_agg_lattice *src_aglat = src_plats->aggs;
1278 src_aglat;
1279 src_aglat = src_aglat->next)
1280 {
1281 HOST_WIDE_INT new_offset = src_aglat->offset - offset_delta;
1282
1283 if (new_offset < 0)
1284 continue;
1285 if (merge_agg_lats_step (dest_plats, new_offset, src_aglat->size,
1286 &dst_aglat, pre_existing, &ret))
1287 {
1288 struct ipcp_agg_lattice *new_al = *dst_aglat;
1289
1290 dst_aglat = &(*dst_aglat)->next;
1291 if (src_aglat->bottom)
1292 {
1293 ret |= set_lattice_contains_variable (new_al);
1294 continue;
1295 }
1296 if (src_aglat->contains_variable)
1297 ret |= set_lattice_contains_variable (new_al);
1298 for (struct ipcp_value *val = src_aglat->values;
1299 val;
1300 val = val->next)
1301 ret |= add_value_to_lattice (new_al, val->value, cs, val, src_idx,
1302 src_aglat->offset);
1303 }
1304 else if (dest_plats->aggs_bottom)
1305 return true;
1306 }
1307 ret |= set_chain_of_aglats_contains_variable (*dst_aglat);
1308 return ret;
1309 }
1310
1311 /* Determine whether there is anything to propagate FROM SRC_PLATS through a
1312 pass-through JFUNC and if so, whether it has conform and conforms to the
1313 rules about propagating values passed by reference. */
1314
1315 static bool
agg_pass_through_permissible_p(struct ipcp_param_lattices * src_plats,struct ipa_jump_func * jfunc)1316 agg_pass_through_permissible_p (struct ipcp_param_lattices *src_plats,
1317 struct ipa_jump_func *jfunc)
1318 {
1319 return src_plats->aggs
1320 && (!src_plats->aggs_by_ref
1321 || ipa_get_jf_pass_through_agg_preserved (jfunc));
1322 }
1323
1324 /* Propagate scalar values across jump function JFUNC that is associated with
1325 edge CS and put the values into DEST_LAT. */
1326
1327 static bool
propagate_aggs_accross_jump_function(struct cgraph_edge * cs,struct ipa_jump_func * jfunc,struct ipcp_param_lattices * dest_plats)1328 propagate_aggs_accross_jump_function (struct cgraph_edge *cs,
1329 struct ipa_jump_func *jfunc,
1330 struct ipcp_param_lattices *dest_plats)
1331 {
1332 bool ret = false;
1333
1334 if (dest_plats->aggs_bottom)
1335 return false;
1336
1337 if (jfunc->type == IPA_JF_PASS_THROUGH
1338 && ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
1339 {
1340 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1341 int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
1342 struct ipcp_param_lattices *src_plats;
1343
1344 src_plats = ipa_get_parm_lattices (caller_info, src_idx);
1345 if (agg_pass_through_permissible_p (src_plats, jfunc))
1346 {
1347 /* Currently we do not produce clobber aggregate jump
1348 functions, replace with merging when we do. */
1349 gcc_assert (!jfunc->agg.items);
1350 ret |= merge_aggregate_lattices (cs, dest_plats, src_plats,
1351 src_idx, 0);
1352 }
1353 else
1354 ret |= set_agg_lats_contain_variable (dest_plats);
1355 }
1356 else if (jfunc->type == IPA_JF_ANCESTOR
1357 && ipa_get_jf_ancestor_agg_preserved (jfunc))
1358 {
1359 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1360 int src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
1361 struct ipcp_param_lattices *src_plats;
1362
1363 src_plats = ipa_get_parm_lattices (caller_info, src_idx);
1364 if (src_plats->aggs && src_plats->aggs_by_ref)
1365 {
1366 /* Currently we do not produce clobber aggregate jump
1367 functions, replace with merging when we do. */
1368 gcc_assert (!jfunc->agg.items);
1369 ret |= merge_aggregate_lattices (cs, dest_plats, src_plats, src_idx,
1370 ipa_get_jf_ancestor_offset (jfunc));
1371 }
1372 else if (!src_plats->aggs_by_ref)
1373 ret |= set_agg_lats_to_bottom (dest_plats);
1374 else
1375 ret |= set_agg_lats_contain_variable (dest_plats);
1376 }
1377 else if (jfunc->agg.items)
1378 {
1379 bool pre_existing = dest_plats->aggs != NULL;
1380 struct ipcp_agg_lattice **aglat = &dest_plats->aggs;
1381 struct ipa_agg_jf_item *item;
1382 int i;
1383
1384 if (set_check_aggs_by_ref (dest_plats, jfunc->agg.by_ref))
1385 return true;
1386
1387 FOR_EACH_VEC_ELT (*jfunc->agg.items, i, item)
1388 {
1389 HOST_WIDE_INT val_size;
1390
1391 if (item->offset < 0)
1392 continue;
1393 gcc_checking_assert (is_gimple_ip_invariant (item->value));
1394 val_size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (item->value)));
1395
1396 if (merge_agg_lats_step (dest_plats, item->offset, val_size,
1397 &aglat, pre_existing, &ret))
1398 {
1399 ret |= add_value_to_lattice (*aglat, item->value, cs, NULL, 0, 0);
1400 aglat = &(*aglat)->next;
1401 }
1402 else if (dest_plats->aggs_bottom)
1403 return true;
1404 }
1405
1406 ret |= set_chain_of_aglats_contains_variable (*aglat);
1407 }
1408 else
1409 ret |= set_agg_lats_contain_variable (dest_plats);
1410
1411 return ret;
1412 }
1413
1414 /* Propagate constants from the caller to the callee of CS. INFO describes the
1415 caller. */
1416
1417 static bool
propagate_constants_accross_call(struct cgraph_edge * cs)1418 propagate_constants_accross_call (struct cgraph_edge *cs)
1419 {
1420 struct ipa_node_params *callee_info;
1421 enum availability availability;
1422 struct cgraph_node *callee, *alias_or_thunk;
1423 struct ipa_edge_args *args;
1424 bool ret = false;
1425 int i, args_count, parms_count;
1426
1427 callee = cgraph_function_node (cs->callee, &availability);
1428 if (!callee->definition)
1429 return false;
1430 gcc_checking_assert (cgraph_function_with_gimple_body_p (callee));
1431 callee_info = IPA_NODE_REF (callee);
1432
1433 args = IPA_EDGE_REF (cs);
1434 args_count = ipa_get_cs_argument_count (args);
1435 parms_count = ipa_get_param_count (callee_info);
1436 if (parms_count == 0)
1437 return false;
1438
1439 /* If this call goes through a thunk we must not propagate to the first (0th)
1440 parameter. However, we might need to uncover a thunk from below a series
1441 of aliases first. */
1442 alias_or_thunk = cs->callee;
1443 while (alias_or_thunk->alias)
1444 alias_or_thunk = cgraph_alias_target (alias_or_thunk);
1445 if (alias_or_thunk->thunk.thunk_p)
1446 {
1447 ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info,
1448 0));
1449 i = 1;
1450 }
1451 else
1452 i = 0;
1453
1454 for (; (i < args_count) && (i < parms_count); i++)
1455 {
1456 struct ipa_jump_func *jump_func = ipa_get_ith_jump_func (args, i);
1457 struct ipcp_param_lattices *dest_plats;
1458
1459 dest_plats = ipa_get_parm_lattices (callee_info, i);
1460 if (availability == AVAIL_OVERWRITABLE)
1461 ret |= set_all_contains_variable (dest_plats);
1462 else
1463 {
1464 ret |= propagate_scalar_accross_jump_function (cs, jump_func,
1465 &dest_plats->itself);
1466 ret |= propagate_aggs_accross_jump_function (cs, jump_func,
1467 dest_plats);
1468 }
1469 }
1470 for (; i < parms_count; i++)
1471 ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info, i));
1472
1473 return ret;
1474 }
1475
1476 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
1477 (which can contain both constants and binfos), KNOWN_BINFOS, KNOWN_AGGS or
1478 AGG_REPS return the destination. The latter three can be NULL. If AGG_REPS
1479 is not NULL, KNOWN_AGGS is ignored. */
1480
1481 static tree
ipa_get_indirect_edge_target_1(struct cgraph_edge * ie,vec<tree> known_vals,vec<tree> known_binfos,vec<ipa_agg_jump_function_p> known_aggs,struct ipa_agg_replacement_value * agg_reps)1482 ipa_get_indirect_edge_target_1 (struct cgraph_edge *ie,
1483 vec<tree> known_vals,
1484 vec<tree> known_binfos,
1485 vec<ipa_agg_jump_function_p> known_aggs,
1486 struct ipa_agg_replacement_value *agg_reps)
1487 {
1488 int param_index = ie->indirect_info->param_index;
1489 HOST_WIDE_INT token, anc_offset;
1490 tree otr_type;
1491 tree t;
1492 tree target = NULL;
1493
1494 if (param_index == -1
1495 || known_vals.length () <= (unsigned int) param_index)
1496 return NULL_TREE;
1497
1498 if (!ie->indirect_info->polymorphic)
1499 {
1500 tree t;
1501
1502 if (ie->indirect_info->agg_contents)
1503 {
1504 if (agg_reps)
1505 {
1506 t = NULL;
1507 while (agg_reps)
1508 {
1509 if (agg_reps->index == param_index
1510 && agg_reps->offset == ie->indirect_info->offset
1511 && agg_reps->by_ref == ie->indirect_info->by_ref)
1512 {
1513 t = agg_reps->value;
1514 break;
1515 }
1516 agg_reps = agg_reps->next;
1517 }
1518 }
1519 else if (known_aggs.length () > (unsigned int) param_index)
1520 {
1521 struct ipa_agg_jump_function *agg;
1522 agg = known_aggs[param_index];
1523 t = ipa_find_agg_cst_for_param (agg, ie->indirect_info->offset,
1524 ie->indirect_info->by_ref);
1525 }
1526 else
1527 t = NULL;
1528 }
1529 else
1530 t = known_vals[param_index];
1531
1532 if (t &&
1533 TREE_CODE (t) == ADDR_EXPR
1534 && TREE_CODE (TREE_OPERAND (t, 0)) == FUNCTION_DECL)
1535 return TREE_OPERAND (t, 0);
1536 else
1537 return NULL_TREE;
1538 }
1539
1540 if (!flag_devirtualize)
1541 return NULL_TREE;
1542
1543 gcc_assert (!ie->indirect_info->agg_contents);
1544 token = ie->indirect_info->otr_token;
1545 anc_offset = ie->indirect_info->offset;
1546 otr_type = ie->indirect_info->otr_type;
1547
1548 t = NULL;
1549
1550 /* Try to work out value of virtual table pointer value in replacemnets. */
1551 if (!t && agg_reps && !ie->indirect_info->by_ref)
1552 {
1553 while (agg_reps)
1554 {
1555 if (agg_reps->index == param_index
1556 && agg_reps->offset == ie->indirect_info->offset
1557 && agg_reps->by_ref)
1558 {
1559 t = agg_reps->value;
1560 break;
1561 }
1562 agg_reps = agg_reps->next;
1563 }
1564 }
1565
1566 /* Try to work out value of virtual table pointer value in known
1567 aggregate values. */
1568 if (!t && known_aggs.length () > (unsigned int) param_index
1569 && !ie->indirect_info->by_ref)
1570 {
1571 struct ipa_agg_jump_function *agg;
1572 agg = known_aggs[param_index];
1573 t = ipa_find_agg_cst_for_param (agg, ie->indirect_info->offset,
1574 true);
1575 }
1576
1577 /* If we found the virtual table pointer, lookup the target. */
1578 if (t)
1579 {
1580 tree vtable;
1581 unsigned HOST_WIDE_INT offset;
1582 if (vtable_pointer_value_to_vtable (t, &vtable, &offset))
1583 {
1584 target = gimple_get_virt_method_for_vtable (ie->indirect_info->otr_token,
1585 vtable, offset);
1586 if (target)
1587 {
1588 if ((TREE_CODE (TREE_TYPE (target)) == FUNCTION_TYPE
1589 && DECL_FUNCTION_CODE (target) == BUILT_IN_UNREACHABLE)
1590 || !possible_polymorphic_call_target_p
1591 (ie, cgraph_get_node (target)))
1592 target = ipa_impossible_devirt_target (ie, target);
1593 return target;
1594 }
1595 }
1596 }
1597
1598 /* Did we work out BINFO via type propagation? */
1599 if (!t && known_binfos.length () > (unsigned int) param_index)
1600 t = known_binfos[param_index];
1601 /* Or do we know the constant value of pointer? */
1602 if (!t)
1603 t = known_vals[param_index];
1604 if (!t)
1605 return NULL_TREE;
1606
1607 if (TREE_CODE (t) != TREE_BINFO)
1608 {
1609 ipa_polymorphic_call_context context;
1610 vec <cgraph_node *>targets;
1611 bool final;
1612
1613 if (!get_polymorphic_call_info_from_invariant
1614 (&context, t, ie->indirect_info->otr_type,
1615 anc_offset))
1616 return NULL_TREE;
1617 targets = possible_polymorphic_call_targets
1618 (ie->indirect_info->otr_type,
1619 ie->indirect_info->otr_token,
1620 context, &final);
1621 if (!final || targets.length () > 1)
1622 return NULL_TREE;
1623 if (targets.length () == 1)
1624 target = targets[0]->decl;
1625 else
1626 target = ipa_impossible_devirt_target (ie, NULL_TREE);
1627 }
1628 else
1629 {
1630 tree binfo;
1631
1632 binfo = get_binfo_at_offset (t, anc_offset, otr_type);
1633 if (!binfo)
1634 return NULL_TREE;
1635 target = gimple_get_virt_method_for_binfo (token, binfo);
1636 }
1637
1638 if (target && !possible_polymorphic_call_target_p (ie,
1639 cgraph_get_node (target)))
1640 target = ipa_impossible_devirt_target (ie, target);
1641
1642 return target;
1643 }
1644
1645
1646 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
1647 (which can contain both constants and binfos), KNOWN_BINFOS (which can be
1648 NULL) or KNOWN_AGGS (which also can be NULL) return the destination. */
1649
1650 tree
ipa_get_indirect_edge_target(struct cgraph_edge * ie,vec<tree> known_vals,vec<tree> known_binfos,vec<ipa_agg_jump_function_p> known_aggs)1651 ipa_get_indirect_edge_target (struct cgraph_edge *ie,
1652 vec<tree> known_vals,
1653 vec<tree> known_binfos,
1654 vec<ipa_agg_jump_function_p> known_aggs)
1655 {
1656 return ipa_get_indirect_edge_target_1 (ie, known_vals, known_binfos,
1657 known_aggs, NULL);
1658 }
1659
1660 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
1661 and KNOWN_BINFOS. */
1662
1663 static int
devirtualization_time_bonus(struct cgraph_node * node,vec<tree> known_csts,vec<tree> known_binfos,vec<ipa_agg_jump_function_p> known_aggs)1664 devirtualization_time_bonus (struct cgraph_node *node,
1665 vec<tree> known_csts,
1666 vec<tree> known_binfos,
1667 vec<ipa_agg_jump_function_p> known_aggs)
1668 {
1669 struct cgraph_edge *ie;
1670 int res = 0;
1671
1672 for (ie = node->indirect_calls; ie; ie = ie->next_callee)
1673 {
1674 struct cgraph_node *callee;
1675 struct inline_summary *isummary;
1676 tree target;
1677
1678 target = ipa_get_indirect_edge_target (ie, known_csts, known_binfos,
1679 known_aggs);
1680 if (!target)
1681 continue;
1682
1683 /* Only bare minimum benefit for clearly un-inlineable targets. */
1684 res += 1;
1685 callee = cgraph_get_node (target);
1686 if (!callee || !callee->definition)
1687 continue;
1688 isummary = inline_summary (callee);
1689 if (!isummary->inlinable)
1690 continue;
1691
1692 /* FIXME: The values below need re-considering and perhaps also
1693 integrating into the cost metrics, at lest in some very basic way. */
1694 if (isummary->size <= MAX_INLINE_INSNS_AUTO / 4)
1695 res += 31;
1696 else if (isummary->size <= MAX_INLINE_INSNS_AUTO / 2)
1697 res += 15;
1698 else if (isummary->size <= MAX_INLINE_INSNS_AUTO
1699 || DECL_DECLARED_INLINE_P (callee->decl))
1700 res += 7;
1701 }
1702
1703 return res;
1704 }
1705
1706 /* Return time bonus incurred because of HINTS. */
1707
1708 static int
hint_time_bonus(inline_hints hints)1709 hint_time_bonus (inline_hints hints)
1710 {
1711 int result = 0;
1712 if (hints & (INLINE_HINT_loop_iterations | INLINE_HINT_loop_stride))
1713 result += PARAM_VALUE (PARAM_IPA_CP_LOOP_HINT_BONUS);
1714 if (hints & INLINE_HINT_array_index)
1715 result += PARAM_VALUE (PARAM_IPA_CP_ARRAY_INDEX_HINT_BONUS);
1716 return result;
1717 }
1718
1719 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
1720 and SIZE_COST and with the sum of frequencies of incoming edges to the
1721 potential new clone in FREQUENCIES. */
1722
1723 static bool
good_cloning_opportunity_p(struct cgraph_node * node,int time_benefit,int freq_sum,gcov_type count_sum,int size_cost)1724 good_cloning_opportunity_p (struct cgraph_node *node, int time_benefit,
1725 int freq_sum, gcov_type count_sum, int size_cost)
1726 {
1727 if (time_benefit == 0
1728 || !flag_ipa_cp_clone
1729 || !optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node->decl)))
1730 return false;
1731
1732 gcc_assert (size_cost > 0);
1733
1734 if (max_count)
1735 {
1736 int factor = (count_sum * 1000) / max_count;
1737 HOST_WIDEST_INT evaluation = (((HOST_WIDEST_INT) time_benefit * factor)
1738 / size_cost);
1739
1740 if (dump_file && (dump_flags & TDF_DETAILS))
1741 fprintf (dump_file, " good_cloning_opportunity_p (time: %i, "
1742 "size: %i, count_sum: " HOST_WIDE_INT_PRINT_DEC
1743 ") -> evaluation: " HOST_WIDEST_INT_PRINT_DEC
1744 ", threshold: %i\n",
1745 time_benefit, size_cost, (HOST_WIDE_INT) count_sum,
1746 evaluation, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD));
1747
1748 return evaluation >= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD);
1749 }
1750 else
1751 {
1752 HOST_WIDEST_INT evaluation = (((HOST_WIDEST_INT) time_benefit * freq_sum)
1753 / size_cost);
1754
1755 if (dump_file && (dump_flags & TDF_DETAILS))
1756 fprintf (dump_file, " good_cloning_opportunity_p (time: %i, "
1757 "size: %i, freq_sum: %i) -> evaluation: "
1758 HOST_WIDEST_INT_PRINT_DEC ", threshold: %i\n",
1759 time_benefit, size_cost, freq_sum, evaluation,
1760 PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD));
1761
1762 return evaluation >= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD);
1763 }
1764 }
1765
1766 /* Return all context independent values from aggregate lattices in PLATS in a
1767 vector. Return NULL if there are none. */
1768
1769 static vec<ipa_agg_jf_item, va_gc> *
context_independent_aggregate_values(struct ipcp_param_lattices * plats)1770 context_independent_aggregate_values (struct ipcp_param_lattices *plats)
1771 {
1772 vec<ipa_agg_jf_item, va_gc> *res = NULL;
1773
1774 if (plats->aggs_bottom
1775 || plats->aggs_contain_variable
1776 || plats->aggs_count == 0)
1777 return NULL;
1778
1779 for (struct ipcp_agg_lattice *aglat = plats->aggs;
1780 aglat;
1781 aglat = aglat->next)
1782 if (ipa_lat_is_single_const (aglat))
1783 {
1784 struct ipa_agg_jf_item item;
1785 item.offset = aglat->offset;
1786 item.value = aglat->values->value;
1787 vec_safe_push (res, item);
1788 }
1789 return res;
1790 }
1791
1792 /* Allocate KNOWN_CSTS, KNOWN_BINFOS and, if non-NULL, KNOWN_AGGS and populate
1793 them with values of parameters that are known independent of the context.
1794 INFO describes the function. If REMOVABLE_PARAMS_COST is non-NULL, the
1795 movement cost of all removable parameters will be stored in it. */
1796
1797 static bool
gather_context_independent_values(struct ipa_node_params * info,vec<tree> * known_csts,vec<tree> * known_binfos,vec<ipa_agg_jump_function> * known_aggs,int * removable_params_cost)1798 gather_context_independent_values (struct ipa_node_params *info,
1799 vec<tree> *known_csts,
1800 vec<tree> *known_binfos,
1801 vec<ipa_agg_jump_function> *known_aggs,
1802 int *removable_params_cost)
1803 {
1804 int i, count = ipa_get_param_count (info);
1805 bool ret = false;
1806
1807 known_csts->create (0);
1808 known_binfos->create (0);
1809 known_csts->safe_grow_cleared (count);
1810 known_binfos->safe_grow_cleared (count);
1811 if (known_aggs)
1812 {
1813 known_aggs->create (0);
1814 known_aggs->safe_grow_cleared (count);
1815 }
1816
1817 if (removable_params_cost)
1818 *removable_params_cost = 0;
1819
1820 for (i = 0; i < count ; i++)
1821 {
1822 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
1823 struct ipcp_lattice *lat = &plats->itself;
1824
1825 if (ipa_lat_is_single_const (lat))
1826 {
1827 struct ipcp_value *val = lat->values;
1828 if (TREE_CODE (val->value) != TREE_BINFO)
1829 {
1830 (*known_csts)[i] = val->value;
1831 if (removable_params_cost)
1832 *removable_params_cost
1833 += estimate_move_cost (TREE_TYPE (val->value));
1834 ret = true;
1835 }
1836 else if (plats->virt_call)
1837 {
1838 (*known_binfos)[i] = val->value;
1839 ret = true;
1840 }
1841 else if (removable_params_cost
1842 && !ipa_is_param_used (info, i))
1843 *removable_params_cost += ipa_get_param_move_cost (info, i);
1844 }
1845 else if (removable_params_cost
1846 && !ipa_is_param_used (info, i))
1847 *removable_params_cost
1848 += ipa_get_param_move_cost (info, i);
1849
1850 if (known_aggs)
1851 {
1852 vec<ipa_agg_jf_item, va_gc> *agg_items;
1853 struct ipa_agg_jump_function *ajf;
1854
1855 agg_items = context_independent_aggregate_values (plats);
1856 ajf = &(*known_aggs)[i];
1857 ajf->items = agg_items;
1858 ajf->by_ref = plats->aggs_by_ref;
1859 ret |= agg_items != NULL;
1860 }
1861 }
1862
1863 return ret;
1864 }
1865
1866 /* The current interface in ipa-inline-analysis requires a pointer vector.
1867 Create it.
1868
1869 FIXME: That interface should be re-worked, this is slightly silly. Still,
1870 I'd like to discuss how to change it first and this demonstrates the
1871 issue. */
1872
1873 static vec<ipa_agg_jump_function_p>
agg_jmp_p_vec_for_t_vec(vec<ipa_agg_jump_function> known_aggs)1874 agg_jmp_p_vec_for_t_vec (vec<ipa_agg_jump_function> known_aggs)
1875 {
1876 vec<ipa_agg_jump_function_p> ret;
1877 struct ipa_agg_jump_function *ajf;
1878 int i;
1879
1880 ret.create (known_aggs.length ());
1881 FOR_EACH_VEC_ELT (known_aggs, i, ajf)
1882 ret.quick_push (ajf);
1883 return ret;
1884 }
1885
1886 /* Iterate over known values of parameters of NODE and estimate the local
1887 effects in terms of time and size they have. */
1888
1889 static void
estimate_local_effects(struct cgraph_node * node)1890 estimate_local_effects (struct cgraph_node *node)
1891 {
1892 struct ipa_node_params *info = IPA_NODE_REF (node);
1893 int i, count = ipa_get_param_count (info);
1894 vec<tree> known_csts, known_binfos;
1895 vec<ipa_agg_jump_function> known_aggs;
1896 vec<ipa_agg_jump_function_p> known_aggs_ptrs;
1897 bool always_const;
1898 int base_time = inline_summary (node)->time;
1899 int removable_params_cost;
1900
1901 if (!count || !ipcp_versionable_function_p (node))
1902 return;
1903
1904 if (dump_file && (dump_flags & TDF_DETAILS))
1905 fprintf (dump_file, "\nEstimating effects for %s/%i, base_time: %i.\n",
1906 node->name (), node->order, base_time);
1907
1908 always_const = gather_context_independent_values (info, &known_csts,
1909 &known_binfos, &known_aggs,
1910 &removable_params_cost);
1911 known_aggs_ptrs = agg_jmp_p_vec_for_t_vec (known_aggs);
1912 if (always_const)
1913 {
1914 struct caller_statistics stats;
1915 inline_hints hints;
1916 int time, size;
1917
1918 init_caller_stats (&stats);
1919 cgraph_for_node_and_aliases (node, gather_caller_stats, &stats, false);
1920 estimate_ipcp_clone_size_and_time (node, known_csts, known_binfos,
1921 known_aggs_ptrs, &size, &time, &hints);
1922 time -= devirtualization_time_bonus (node, known_csts, known_binfos,
1923 known_aggs_ptrs);
1924 time -= hint_time_bonus (hints);
1925 time -= removable_params_cost;
1926 size -= stats.n_calls * removable_params_cost;
1927
1928 if (dump_file)
1929 fprintf (dump_file, " - context independent values, size: %i, "
1930 "time_benefit: %i\n", size, base_time - time);
1931
1932 if (size <= 0
1933 || cgraph_will_be_removed_from_program_if_no_direct_calls (node))
1934 {
1935 info->do_clone_for_all_contexts = true;
1936 base_time = time;
1937
1938 if (dump_file)
1939 fprintf (dump_file, " Decided to specialize for all "
1940 "known contexts, code not going to grow.\n");
1941 }
1942 else if (good_cloning_opportunity_p (node, base_time - time,
1943 stats.freq_sum, stats.count_sum,
1944 size))
1945 {
1946 if (size + overall_size <= max_new_size)
1947 {
1948 info->do_clone_for_all_contexts = true;
1949 base_time = time;
1950 overall_size += size;
1951
1952 if (dump_file)
1953 fprintf (dump_file, " Decided to specialize for all "
1954 "known contexts, growth deemed beneficial.\n");
1955 }
1956 else if (dump_file && (dump_flags & TDF_DETAILS))
1957 fprintf (dump_file, " Not cloning for all contexts because "
1958 "max_new_size would be reached with %li.\n",
1959 size + overall_size);
1960 }
1961 }
1962
1963 for (i = 0; i < count ; i++)
1964 {
1965 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
1966 struct ipcp_lattice *lat = &plats->itself;
1967 struct ipcp_value *val;
1968 int emc;
1969
1970 if (lat->bottom
1971 || !lat->values
1972 || known_csts[i]
1973 || known_binfos[i])
1974 continue;
1975
1976 for (val = lat->values; val; val = val->next)
1977 {
1978 int time, size, time_benefit;
1979 inline_hints hints;
1980
1981 if (TREE_CODE (val->value) != TREE_BINFO)
1982 {
1983 known_csts[i] = val->value;
1984 known_binfos[i] = NULL_TREE;
1985 emc = estimate_move_cost (TREE_TYPE (val->value));
1986 }
1987 else if (plats->virt_call)
1988 {
1989 known_csts[i] = NULL_TREE;
1990 known_binfos[i] = val->value;
1991 emc = 0;
1992 }
1993 else
1994 continue;
1995
1996 estimate_ipcp_clone_size_and_time (node, known_csts, known_binfos,
1997 known_aggs_ptrs, &size, &time,
1998 &hints);
1999 time_benefit = base_time - time
2000 + devirtualization_time_bonus (node, known_csts, known_binfos,
2001 known_aggs_ptrs)
2002 + hint_time_bonus (hints)
2003 + removable_params_cost + emc;
2004
2005 gcc_checking_assert (size >=0);
2006 /* The inliner-heuristics based estimates may think that in certain
2007 contexts some functions do not have any size at all but we want
2008 all specializations to have at least a tiny cost, not least not to
2009 divide by zero. */
2010 if (size == 0)
2011 size = 1;
2012
2013 if (dump_file && (dump_flags & TDF_DETAILS))
2014 {
2015 fprintf (dump_file, " - estimates for value ");
2016 print_ipcp_constant_value (dump_file, val->value);
2017 fprintf (dump_file, " for ");
2018 ipa_dump_param (dump_file, info, i);
2019 fprintf (dump_file, ": time_benefit: %i, size: %i\n",
2020 time_benefit, size);
2021 }
2022
2023 val->local_time_benefit = time_benefit;
2024 val->local_size_cost = size;
2025 }
2026 known_binfos[i] = NULL_TREE;
2027 known_csts[i] = NULL_TREE;
2028 }
2029
2030 for (i = 0; i < count ; i++)
2031 {
2032 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
2033 struct ipa_agg_jump_function *ajf;
2034 struct ipcp_agg_lattice *aglat;
2035
2036 if (plats->aggs_bottom || !plats->aggs)
2037 continue;
2038
2039 ajf = &known_aggs[i];
2040 for (aglat = plats->aggs; aglat; aglat = aglat->next)
2041 {
2042 struct ipcp_value *val;
2043 if (aglat->bottom || !aglat->values
2044 /* If the following is true, the one value is in known_aggs. */
2045 || (!plats->aggs_contain_variable
2046 && ipa_lat_is_single_const (aglat)))
2047 continue;
2048
2049 for (val = aglat->values; val; val = val->next)
2050 {
2051 int time, size, time_benefit;
2052 struct ipa_agg_jf_item item;
2053 inline_hints hints;
2054
2055 item.offset = aglat->offset;
2056 item.value = val->value;
2057 vec_safe_push (ajf->items, item);
2058
2059 estimate_ipcp_clone_size_and_time (node, known_csts, known_binfos,
2060 known_aggs_ptrs, &size, &time,
2061 &hints);
2062 time_benefit = base_time - time
2063 + devirtualization_time_bonus (node, known_csts, known_binfos,
2064 known_aggs_ptrs)
2065 + hint_time_bonus (hints);
2066 gcc_checking_assert (size >=0);
2067 if (size == 0)
2068 size = 1;
2069
2070 if (dump_file && (dump_flags & TDF_DETAILS))
2071 {
2072 fprintf (dump_file, " - estimates for value ");
2073 print_ipcp_constant_value (dump_file, val->value);
2074 fprintf (dump_file, " for ");
2075 ipa_dump_param (dump_file, info, i);
2076 fprintf (dump_file, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
2077 "]: time_benefit: %i, size: %i\n",
2078 plats->aggs_by_ref ? "ref " : "",
2079 aglat->offset, time_benefit, size);
2080 }
2081
2082 val->local_time_benefit = time_benefit;
2083 val->local_size_cost = size;
2084 ajf->items->pop ();
2085 }
2086 }
2087 }
2088
2089 for (i = 0; i < count ; i++)
2090 vec_free (known_aggs[i].items);
2091
2092 known_csts.release ();
2093 known_binfos.release ();
2094 known_aggs.release ();
2095 known_aggs_ptrs.release ();
2096 }
2097
2098
2099 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
2100 topological sort of values. */
2101
2102 static void
add_val_to_toposort(struct ipcp_value * cur_val)2103 add_val_to_toposort (struct ipcp_value *cur_val)
2104 {
2105 static int dfs_counter = 0;
2106 static struct ipcp_value *stack;
2107 struct ipcp_value_source *src;
2108
2109 if (cur_val->dfs)
2110 return;
2111
2112 dfs_counter++;
2113 cur_val->dfs = dfs_counter;
2114 cur_val->low_link = dfs_counter;
2115
2116 cur_val->topo_next = stack;
2117 stack = cur_val;
2118 cur_val->on_stack = true;
2119
2120 for (src = cur_val->sources; src; src = src->next)
2121 if (src->val)
2122 {
2123 if (src->val->dfs == 0)
2124 {
2125 add_val_to_toposort (src->val);
2126 if (src->val->low_link < cur_val->low_link)
2127 cur_val->low_link = src->val->low_link;
2128 }
2129 else if (src->val->on_stack
2130 && src->val->dfs < cur_val->low_link)
2131 cur_val->low_link = src->val->dfs;
2132 }
2133
2134 if (cur_val->dfs == cur_val->low_link)
2135 {
2136 struct ipcp_value *v, *scc_list = NULL;
2137
2138 do
2139 {
2140 v = stack;
2141 stack = v->topo_next;
2142 v->on_stack = false;
2143
2144 v->scc_next = scc_list;
2145 scc_list = v;
2146 }
2147 while (v != cur_val);
2148
2149 cur_val->topo_next = values_topo;
2150 values_topo = cur_val;
2151 }
2152 }
2153
2154 /* Add all values in lattices associated with NODE to the topological sort if
2155 they are not there yet. */
2156
2157 static void
add_all_node_vals_to_toposort(struct cgraph_node * node)2158 add_all_node_vals_to_toposort (struct cgraph_node *node)
2159 {
2160 struct ipa_node_params *info = IPA_NODE_REF (node);
2161 int i, count = ipa_get_param_count (info);
2162
2163 for (i = 0; i < count ; i++)
2164 {
2165 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
2166 struct ipcp_lattice *lat = &plats->itself;
2167 struct ipcp_agg_lattice *aglat;
2168 struct ipcp_value *val;
2169
2170 if (!lat->bottom)
2171 for (val = lat->values; val; val = val->next)
2172 add_val_to_toposort (val);
2173
2174 if (!plats->aggs_bottom)
2175 for (aglat = plats->aggs; aglat; aglat = aglat->next)
2176 if (!aglat->bottom)
2177 for (val = aglat->values; val; val = val->next)
2178 add_val_to_toposort (val);
2179 }
2180 }
2181
2182 /* One pass of constants propagation along the call graph edges, from callers
2183 to callees (requires topological ordering in TOPO), iterate over strongly
2184 connected components. */
2185
2186 static void
propagate_constants_topo(struct topo_info * topo)2187 propagate_constants_topo (struct topo_info *topo)
2188 {
2189 int i;
2190
2191 for (i = topo->nnodes - 1; i >= 0; i--)
2192 {
2193 unsigned j;
2194 struct cgraph_node *v, *node = topo->order[i];
2195 vec<cgraph_node_ptr> cycle_nodes = ipa_get_nodes_in_cycle (node);
2196
2197 /* First, iteratively propagate within the strongly connected component
2198 until all lattices stabilize. */
2199 FOR_EACH_VEC_ELT (cycle_nodes, j, v)
2200 if (cgraph_function_with_gimple_body_p (v))
2201 push_node_to_stack (topo, v);
2202
2203 v = pop_node_from_stack (topo);
2204 while (v)
2205 {
2206 struct cgraph_edge *cs;
2207
2208 for (cs = v->callees; cs; cs = cs->next_callee)
2209 if (ipa_edge_within_scc (cs)
2210 && propagate_constants_accross_call (cs))
2211 push_node_to_stack (topo, cs->callee);
2212 v = pop_node_from_stack (topo);
2213 }
2214
2215 /* Afterwards, propagate along edges leading out of the SCC, calculates
2216 the local effects of the discovered constants and all valid values to
2217 their topological sort. */
2218 FOR_EACH_VEC_ELT (cycle_nodes, j, v)
2219 if (cgraph_function_with_gimple_body_p (v))
2220 {
2221 struct cgraph_edge *cs;
2222
2223 estimate_local_effects (v);
2224 add_all_node_vals_to_toposort (v);
2225 for (cs = v->callees; cs; cs = cs->next_callee)
2226 if (!ipa_edge_within_scc (cs))
2227 propagate_constants_accross_call (cs);
2228 }
2229 cycle_nodes.release ();
2230 }
2231 }
2232
2233
2234 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
2235 the bigger one if otherwise. */
2236
2237 static int
safe_add(int a,int b)2238 safe_add (int a, int b)
2239 {
2240 if (a > INT_MAX/2 || b > INT_MAX/2)
2241 return a > b ? a : b;
2242 else
2243 return a + b;
2244 }
2245
2246
2247 /* Propagate the estimated effects of individual values along the topological
2248 from the dependent values to those they depend on. */
2249
2250 static void
propagate_effects(void)2251 propagate_effects (void)
2252 {
2253 struct ipcp_value *base;
2254
2255 for (base = values_topo; base; base = base->topo_next)
2256 {
2257 struct ipcp_value_source *src;
2258 struct ipcp_value *val;
2259 int time = 0, size = 0;
2260
2261 for (val = base; val; val = val->scc_next)
2262 {
2263 time = safe_add (time,
2264 val->local_time_benefit + val->prop_time_benefit);
2265 size = safe_add (size, val->local_size_cost + val->prop_size_cost);
2266 }
2267
2268 for (val = base; val; val = val->scc_next)
2269 for (src = val->sources; src; src = src->next)
2270 if (src->val
2271 && cgraph_maybe_hot_edge_p (src->cs))
2272 {
2273 src->val->prop_time_benefit = safe_add (time,
2274 src->val->prop_time_benefit);
2275 src->val->prop_size_cost = safe_add (size,
2276 src->val->prop_size_cost);
2277 }
2278 }
2279 }
2280
2281
2282 /* Propagate constants, binfos and their effects from the summaries
2283 interprocedurally. */
2284
2285 static void
ipcp_propagate_stage(struct topo_info * topo)2286 ipcp_propagate_stage (struct topo_info *topo)
2287 {
2288 struct cgraph_node *node;
2289
2290 if (dump_file)
2291 fprintf (dump_file, "\n Propagating constants:\n\n");
2292
2293 if (in_lto_p)
2294 ipa_update_after_lto_read ();
2295
2296
2297 FOR_EACH_DEFINED_FUNCTION (node)
2298 {
2299 struct ipa_node_params *info = IPA_NODE_REF (node);
2300
2301 determine_versionability (node);
2302 if (cgraph_function_with_gimple_body_p (node))
2303 {
2304 info->lattices = XCNEWVEC (struct ipcp_param_lattices,
2305 ipa_get_param_count (info));
2306 initialize_node_lattices (node);
2307 }
2308 if (node->definition && !node->alias)
2309 overall_size += inline_summary (node)->self_size;
2310 if (node->count > max_count)
2311 max_count = node->count;
2312 }
2313
2314 max_new_size = overall_size;
2315 if (max_new_size < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
2316 max_new_size = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
2317 max_new_size += max_new_size * PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH) / 100 + 1;
2318
2319 if (dump_file)
2320 fprintf (dump_file, "\noverall_size: %li, max_new_size: %li\n",
2321 overall_size, max_new_size);
2322
2323 propagate_constants_topo (topo);
2324 #ifdef ENABLE_CHECKING
2325 ipcp_verify_propagated_values ();
2326 #endif
2327 propagate_effects ();
2328
2329 if (dump_file)
2330 {
2331 fprintf (dump_file, "\nIPA lattices after all propagation:\n");
2332 print_all_lattices (dump_file, (dump_flags & TDF_DETAILS), true);
2333 }
2334 }
2335
2336 /* Discover newly direct outgoing edges from NODE which is a new clone with
2337 known KNOWN_VALS and make them direct. */
2338
2339 static void
ipcp_discover_new_direct_edges(struct cgraph_node * node,vec<tree> known_vals,struct ipa_agg_replacement_value * aggvals)2340 ipcp_discover_new_direct_edges (struct cgraph_node *node,
2341 vec<tree> known_vals,
2342 struct ipa_agg_replacement_value *aggvals)
2343 {
2344 struct cgraph_edge *ie, *next_ie;
2345 bool found = false;
2346
2347 for (ie = node->indirect_calls; ie; ie = next_ie)
2348 {
2349 tree target;
2350
2351 next_ie = ie->next_callee;
2352 target = ipa_get_indirect_edge_target_1 (ie, known_vals, vNULL, vNULL,
2353 aggvals);
2354 if (target)
2355 {
2356 bool agg_contents = ie->indirect_info->agg_contents;
2357 bool polymorphic = ie->indirect_info->polymorphic;
2358 int param_index = ie->indirect_info->param_index;
2359 struct cgraph_edge *cs = ipa_make_edge_direct_to_target (ie, target);
2360 found = true;
2361
2362 if (cs && !agg_contents && !polymorphic)
2363 {
2364 struct ipa_node_params *info = IPA_NODE_REF (node);
2365 int c = ipa_get_controlled_uses (info, param_index);
2366 if (c != IPA_UNDESCRIBED_USE)
2367 {
2368 struct ipa_ref *to_del;
2369
2370 c--;
2371 ipa_set_controlled_uses (info, param_index, c);
2372 if (dump_file && (dump_flags & TDF_DETAILS))
2373 fprintf (dump_file, " controlled uses count of param "
2374 "%i bumped down to %i\n", param_index, c);
2375 if (c == 0
2376 && (to_del = ipa_find_reference (node,
2377 cs->callee,
2378 NULL, 0)))
2379 {
2380 if (dump_file && (dump_flags & TDF_DETAILS))
2381 fprintf (dump_file, " and even removing its "
2382 "cloning-created reference\n");
2383 ipa_remove_reference (to_del);
2384 }
2385 }
2386 }
2387 }
2388 }
2389 /* Turning calls to direct calls will improve overall summary. */
2390 if (found)
2391 inline_update_overall_summary (node);
2392 }
2393
2394 /* Vector of pointers which for linked lists of clones of an original crgaph
2395 edge. */
2396
2397 static vec<cgraph_edge_p> next_edge_clone;
2398 static vec<cgraph_edge_p> prev_edge_clone;
2399
2400 static inline void
grow_edge_clone_vectors(void)2401 grow_edge_clone_vectors (void)
2402 {
2403 if (next_edge_clone.length ()
2404 <= (unsigned) cgraph_edge_max_uid)
2405 next_edge_clone.safe_grow_cleared (cgraph_edge_max_uid + 1);
2406 if (prev_edge_clone.length ()
2407 <= (unsigned) cgraph_edge_max_uid)
2408 prev_edge_clone.safe_grow_cleared (cgraph_edge_max_uid + 1);
2409 }
2410
2411 /* Edge duplication hook to grow the appropriate linked list in
2412 next_edge_clone. */
2413
2414 static void
ipcp_edge_duplication_hook(struct cgraph_edge * src,struct cgraph_edge * dst,void *)2415 ipcp_edge_duplication_hook (struct cgraph_edge *src, struct cgraph_edge *dst,
2416 void *)
2417 {
2418 grow_edge_clone_vectors ();
2419
2420 struct cgraph_edge *old_next = next_edge_clone[src->uid];
2421 if (old_next)
2422 prev_edge_clone[old_next->uid] = dst;
2423 prev_edge_clone[dst->uid] = src;
2424
2425 next_edge_clone[dst->uid] = old_next;
2426 next_edge_clone[src->uid] = dst;
2427 }
2428
2429 /* Hook that is called by cgraph.c when an edge is removed. */
2430
2431 static void
ipcp_edge_removal_hook(struct cgraph_edge * cs,void *)2432 ipcp_edge_removal_hook (struct cgraph_edge *cs, void *)
2433 {
2434 grow_edge_clone_vectors ();
2435
2436 struct cgraph_edge *prev = prev_edge_clone[cs->uid];
2437 struct cgraph_edge *next = next_edge_clone[cs->uid];
2438 if (prev)
2439 next_edge_clone[prev->uid] = next;
2440 if (next)
2441 prev_edge_clone[next->uid] = prev;
2442 }
2443
2444 /* See if NODE is a clone with a known aggregate value at a given OFFSET of a
2445 parameter with the given INDEX. */
2446
2447 static tree
get_clone_agg_value(struct cgraph_node * node,HOST_WIDEST_INT offset,int index)2448 get_clone_agg_value (struct cgraph_node *node, HOST_WIDEST_INT offset,
2449 int index)
2450 {
2451 struct ipa_agg_replacement_value *aggval;
2452
2453 aggval = ipa_get_agg_replacements_for_node (node);
2454 while (aggval)
2455 {
2456 if (aggval->offset == offset
2457 && aggval->index == index)
2458 return aggval->value;
2459 aggval = aggval->next;
2460 }
2461 return NULL_TREE;
2462 }
2463
2464 /* Return true if edge CS does bring about the value described by SRC. */
2465
2466 static bool
cgraph_edge_brings_value_p(struct cgraph_edge * cs,struct ipcp_value_source * src)2467 cgraph_edge_brings_value_p (struct cgraph_edge *cs,
2468 struct ipcp_value_source *src)
2469 {
2470 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
2471 cgraph_node *real_dest = cgraph_function_node (cs->callee);
2472 struct ipa_node_params *dst_info = IPA_NODE_REF (real_dest);
2473
2474 if ((dst_info->ipcp_orig_node && !dst_info->is_all_contexts_clone)
2475 || caller_info->node_dead)
2476 return false;
2477 if (!src->val)
2478 return true;
2479
2480 if (caller_info->ipcp_orig_node)
2481 {
2482 tree t;
2483 if (src->offset == -1)
2484 t = caller_info->known_vals[src->index];
2485 else
2486 t = get_clone_agg_value (cs->caller, src->offset, src->index);
2487 return (t != NULL_TREE
2488 && values_equal_for_ipcp_p (src->val->value, t));
2489 }
2490 else
2491 {
2492 struct ipcp_agg_lattice *aglat;
2493 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (caller_info,
2494 src->index);
2495 if (src->offset == -1)
2496 return (ipa_lat_is_single_const (&plats->itself)
2497 && values_equal_for_ipcp_p (src->val->value,
2498 plats->itself.values->value));
2499 else
2500 {
2501 if (plats->aggs_bottom || plats->aggs_contain_variable)
2502 return false;
2503 for (aglat = plats->aggs; aglat; aglat = aglat->next)
2504 if (aglat->offset == src->offset)
2505 return (ipa_lat_is_single_const (aglat)
2506 && values_equal_for_ipcp_p (src->val->value,
2507 aglat->values->value));
2508 }
2509 return false;
2510 }
2511 }
2512
2513 /* Get the next clone in the linked list of clones of an edge. */
2514
2515 static inline struct cgraph_edge *
get_next_cgraph_edge_clone(struct cgraph_edge * cs)2516 get_next_cgraph_edge_clone (struct cgraph_edge *cs)
2517 {
2518 return next_edge_clone[cs->uid];
2519 }
2520
2521 /* Given VAL, iterate over all its sources and if they still hold, add their
2522 edge frequency and their number into *FREQUENCY and *CALLER_COUNT
2523 respectively. */
2524
2525 static bool
get_info_about_necessary_edges(struct ipcp_value * val,int * freq_sum,gcov_type * count_sum,int * caller_count)2526 get_info_about_necessary_edges (struct ipcp_value *val, int *freq_sum,
2527 gcov_type *count_sum, int *caller_count)
2528 {
2529 struct ipcp_value_source *src;
2530 int freq = 0, count = 0;
2531 gcov_type cnt = 0;
2532 bool hot = false;
2533
2534 for (src = val->sources; src; src = src->next)
2535 {
2536 struct cgraph_edge *cs = src->cs;
2537 while (cs)
2538 {
2539 if (cgraph_edge_brings_value_p (cs, src))
2540 {
2541 count++;
2542 freq += cs->frequency;
2543 cnt += cs->count;
2544 hot |= cgraph_maybe_hot_edge_p (cs);
2545 }
2546 cs = get_next_cgraph_edge_clone (cs);
2547 }
2548 }
2549
2550 *freq_sum = freq;
2551 *count_sum = cnt;
2552 *caller_count = count;
2553 return hot;
2554 }
2555
2556 /* Return a vector of incoming edges that do bring value VAL. It is assumed
2557 their number is known and equal to CALLER_COUNT. */
2558
2559 static vec<cgraph_edge_p>
gather_edges_for_value(struct ipcp_value * val,int caller_count)2560 gather_edges_for_value (struct ipcp_value *val, int caller_count)
2561 {
2562 struct ipcp_value_source *src;
2563 vec<cgraph_edge_p> ret;
2564
2565 ret.create (caller_count);
2566 for (src = val->sources; src; src = src->next)
2567 {
2568 struct cgraph_edge *cs = src->cs;
2569 while (cs)
2570 {
2571 if (cgraph_edge_brings_value_p (cs, src))
2572 ret.quick_push (cs);
2573 cs = get_next_cgraph_edge_clone (cs);
2574 }
2575 }
2576
2577 return ret;
2578 }
2579
2580 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
2581 Return it or NULL if for some reason it cannot be created. */
2582
2583 static struct ipa_replace_map *
get_replacement_map(struct ipa_node_params * info,tree value,int parm_num)2584 get_replacement_map (struct ipa_node_params *info, tree value, int parm_num)
2585 {
2586 struct ipa_replace_map *replace_map;
2587
2588
2589 replace_map = ggc_alloc_ipa_replace_map ();
2590 if (dump_file)
2591 {
2592 fprintf (dump_file, " replacing ");
2593 ipa_dump_param (dump_file, info, parm_num);
2594
2595 fprintf (dump_file, " with const ");
2596 print_generic_expr (dump_file, value, 0);
2597 fprintf (dump_file, "\n");
2598 }
2599 replace_map->old_tree = NULL;
2600 replace_map->parm_num = parm_num;
2601 replace_map->new_tree = value;
2602 replace_map->replace_p = true;
2603 replace_map->ref_p = false;
2604
2605 return replace_map;
2606 }
2607
2608 /* Dump new profiling counts */
2609
2610 static void
dump_profile_updates(struct cgraph_node * orig_node,struct cgraph_node * new_node)2611 dump_profile_updates (struct cgraph_node *orig_node,
2612 struct cgraph_node *new_node)
2613 {
2614 struct cgraph_edge *cs;
2615
2616 fprintf (dump_file, " setting count of the specialized node to "
2617 HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) new_node->count);
2618 for (cs = new_node->callees; cs ; cs = cs->next_callee)
2619 fprintf (dump_file, " edge to %s has count "
2620 HOST_WIDE_INT_PRINT_DEC "\n",
2621 cs->callee->name (), (HOST_WIDE_INT) cs->count);
2622
2623 fprintf (dump_file, " setting count of the original node to "
2624 HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) orig_node->count);
2625 for (cs = orig_node->callees; cs ; cs = cs->next_callee)
2626 fprintf (dump_file, " edge to %s is left with "
2627 HOST_WIDE_INT_PRINT_DEC "\n",
2628 cs->callee->name (), (HOST_WIDE_INT) cs->count);
2629 }
2630
2631 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
2632 their profile information to reflect this. */
2633
2634 static void
update_profiling_info(struct cgraph_node * orig_node,struct cgraph_node * new_node)2635 update_profiling_info (struct cgraph_node *orig_node,
2636 struct cgraph_node *new_node)
2637 {
2638 struct cgraph_edge *cs;
2639 struct caller_statistics stats;
2640 gcov_type new_sum, orig_sum;
2641 gcov_type remainder, orig_node_count = orig_node->count;
2642
2643 if (orig_node_count == 0)
2644 return;
2645
2646 init_caller_stats (&stats);
2647 cgraph_for_node_and_aliases (orig_node, gather_caller_stats, &stats, false);
2648 orig_sum = stats.count_sum;
2649 init_caller_stats (&stats);
2650 cgraph_for_node_and_aliases (new_node, gather_caller_stats, &stats, false);
2651 new_sum = stats.count_sum;
2652
2653 if (orig_node_count < orig_sum + new_sum)
2654 {
2655 if (dump_file)
2656 fprintf (dump_file, " Problem: node %s/%i has too low count "
2657 HOST_WIDE_INT_PRINT_DEC " while the sum of incoming "
2658 "counts is " HOST_WIDE_INT_PRINT_DEC "\n",
2659 orig_node->name (), orig_node->order,
2660 (HOST_WIDE_INT) orig_node_count,
2661 (HOST_WIDE_INT) (orig_sum + new_sum));
2662
2663 orig_node_count = (orig_sum + new_sum) * 12 / 10;
2664 if (dump_file)
2665 fprintf (dump_file, " proceeding by pretending it was "
2666 HOST_WIDE_INT_PRINT_DEC "\n",
2667 (HOST_WIDE_INT) orig_node_count);
2668 }
2669
2670 new_node->count = new_sum;
2671 remainder = orig_node_count - new_sum;
2672 orig_node->count = remainder;
2673
2674 for (cs = new_node->callees; cs ; cs = cs->next_callee)
2675 if (cs->frequency)
2676 cs->count = apply_probability (cs->count,
2677 GCOV_COMPUTE_SCALE (new_sum,
2678 orig_node_count));
2679 else
2680 cs->count = 0;
2681
2682 for (cs = orig_node->callees; cs ; cs = cs->next_callee)
2683 cs->count = apply_probability (cs->count,
2684 GCOV_COMPUTE_SCALE (remainder,
2685 orig_node_count));
2686
2687 if (dump_file)
2688 dump_profile_updates (orig_node, new_node);
2689 }
2690
2691 /* Update the respective profile of specialized NEW_NODE and the original
2692 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
2693 have been redirected to the specialized version. */
2694
2695 static void
update_specialized_profile(struct cgraph_node * new_node,struct cgraph_node * orig_node,gcov_type redirected_sum)2696 update_specialized_profile (struct cgraph_node *new_node,
2697 struct cgraph_node *orig_node,
2698 gcov_type redirected_sum)
2699 {
2700 struct cgraph_edge *cs;
2701 gcov_type new_node_count, orig_node_count = orig_node->count;
2702
2703 if (dump_file)
2704 fprintf (dump_file, " the sum of counts of redirected edges is "
2705 HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) redirected_sum);
2706 if (orig_node_count == 0)
2707 return;
2708
2709 gcc_assert (orig_node_count >= redirected_sum);
2710
2711 new_node_count = new_node->count;
2712 new_node->count += redirected_sum;
2713 orig_node->count -= redirected_sum;
2714
2715 for (cs = new_node->callees; cs ; cs = cs->next_callee)
2716 if (cs->frequency)
2717 cs->count += apply_probability (cs->count,
2718 GCOV_COMPUTE_SCALE (redirected_sum,
2719 new_node_count));
2720 else
2721 cs->count = 0;
2722
2723 for (cs = orig_node->callees; cs ; cs = cs->next_callee)
2724 {
2725 gcov_type dec = apply_probability (cs->count,
2726 GCOV_COMPUTE_SCALE (redirected_sum,
2727 orig_node_count));
2728 if (dec < cs->count)
2729 cs->count -= dec;
2730 else
2731 cs->count = 0;
2732 }
2733
2734 if (dump_file)
2735 dump_profile_updates (orig_node, new_node);
2736 }
2737
2738 /* Create a specialized version of NODE with known constants and types of
2739 parameters in KNOWN_VALS and redirect all edges in CALLERS to it. */
2740
2741 static struct cgraph_node *
create_specialized_node(struct cgraph_node * node,vec<tree> known_vals,struct ipa_agg_replacement_value * aggvals,vec<cgraph_edge_p> callers)2742 create_specialized_node (struct cgraph_node *node,
2743 vec<tree> known_vals,
2744 struct ipa_agg_replacement_value *aggvals,
2745 vec<cgraph_edge_p> callers)
2746 {
2747 struct ipa_node_params *new_info, *info = IPA_NODE_REF (node);
2748 vec<ipa_replace_map_p, va_gc> *replace_trees = NULL;
2749 struct ipa_agg_replacement_value *av;
2750 struct cgraph_node *new_node;
2751 int i, count = ipa_get_param_count (info);
2752 bitmap args_to_skip;
2753
2754 gcc_assert (!info->ipcp_orig_node);
2755
2756 if (node->local.can_change_signature)
2757 {
2758 args_to_skip = BITMAP_GGC_ALLOC ();
2759 for (i = 0; i < count; i++)
2760 {
2761 tree t = known_vals[i];
2762
2763 if ((t && TREE_CODE (t) != TREE_BINFO)
2764 || !ipa_is_param_used (info, i))
2765 bitmap_set_bit (args_to_skip, i);
2766 }
2767 }
2768 else
2769 {
2770 args_to_skip = NULL;
2771 if (dump_file && (dump_flags & TDF_DETAILS))
2772 fprintf (dump_file, " cannot change function signature\n");
2773 }
2774
2775 for (i = 0; i < count ; i++)
2776 {
2777 tree t = known_vals[i];
2778 if (t && TREE_CODE (t) != TREE_BINFO)
2779 {
2780 struct ipa_replace_map *replace_map;
2781
2782 replace_map = get_replacement_map (info, t, i);
2783 if (replace_map)
2784 vec_safe_push (replace_trees, replace_map);
2785 }
2786 }
2787
2788 new_node = cgraph_create_virtual_clone (node, callers, replace_trees,
2789 args_to_skip, "constprop");
2790 ipa_set_node_agg_value_chain (new_node, aggvals);
2791 for (av = aggvals; av; av = av->next)
2792 ipa_maybe_record_reference (new_node, av->value,
2793 IPA_REF_ADDR, NULL);
2794
2795 if (dump_file && (dump_flags & TDF_DETAILS))
2796 {
2797 fprintf (dump_file, " the new node is %s/%i.\n",
2798 new_node->name (), new_node->order);
2799 if (aggvals)
2800 ipa_dump_agg_replacement_values (dump_file, aggvals);
2801 }
2802 ipa_check_create_node_params ();
2803 update_profiling_info (node, new_node);
2804 new_info = IPA_NODE_REF (new_node);
2805 new_info->ipcp_orig_node = node;
2806 new_info->known_vals = known_vals;
2807
2808 ipcp_discover_new_direct_edges (new_node, known_vals, aggvals);
2809
2810 callers.release ();
2811 return new_node;
2812 }
2813
2814 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
2815 KNOWN_VALS with constants and types that are also known for all of the
2816 CALLERS. */
2817
2818 static void
find_more_scalar_values_for_callers_subset(struct cgraph_node * node,vec<tree> known_vals,vec<cgraph_edge_p> callers)2819 find_more_scalar_values_for_callers_subset (struct cgraph_node *node,
2820 vec<tree> known_vals,
2821 vec<cgraph_edge_p> callers)
2822 {
2823 struct ipa_node_params *info = IPA_NODE_REF (node);
2824 int i, count = ipa_get_param_count (info);
2825
2826 for (i = 0; i < count ; i++)
2827 {
2828 struct cgraph_edge *cs;
2829 tree newval = NULL_TREE;
2830 int j;
2831
2832 if (ipa_get_scalar_lat (info, i)->bottom || known_vals[i])
2833 continue;
2834
2835 FOR_EACH_VEC_ELT (callers, j, cs)
2836 {
2837 struct ipa_jump_func *jump_func;
2838 tree t;
2839
2840 if (i >= ipa_get_cs_argument_count (IPA_EDGE_REF (cs)))
2841 {
2842 newval = NULL_TREE;
2843 break;
2844 }
2845 jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
2846 t = ipa_value_from_jfunc (IPA_NODE_REF (cs->caller), jump_func);
2847 if (!t
2848 || (newval
2849 && !values_equal_for_ipcp_p (t, newval)))
2850 {
2851 newval = NULL_TREE;
2852 break;
2853 }
2854 else
2855 newval = t;
2856 }
2857
2858 if (newval)
2859 {
2860 if (dump_file && (dump_flags & TDF_DETAILS))
2861 {
2862 fprintf (dump_file, " adding an extra known scalar value ");
2863 print_ipcp_constant_value (dump_file, newval);
2864 fprintf (dump_file, " for ");
2865 ipa_dump_param (dump_file, info, i);
2866 fprintf (dump_file, "\n");
2867 }
2868
2869 known_vals[i] = newval;
2870 }
2871 }
2872 }
2873
2874 /* Go through PLATS and create a vector of values consisting of values and
2875 offsets (minus OFFSET) of lattices that contain only a single value. */
2876
2877 static vec<ipa_agg_jf_item>
copy_plats_to_inter(struct ipcp_param_lattices * plats,HOST_WIDE_INT offset)2878 copy_plats_to_inter (struct ipcp_param_lattices *plats, HOST_WIDE_INT offset)
2879 {
2880 vec<ipa_agg_jf_item> res = vNULL;
2881
2882 if (!plats->aggs || plats->aggs_contain_variable || plats->aggs_bottom)
2883 return vNULL;
2884
2885 for (struct ipcp_agg_lattice *aglat = plats->aggs; aglat; aglat = aglat->next)
2886 if (ipa_lat_is_single_const (aglat))
2887 {
2888 struct ipa_agg_jf_item ti;
2889 ti.offset = aglat->offset - offset;
2890 ti.value = aglat->values->value;
2891 res.safe_push (ti);
2892 }
2893 return res;
2894 }
2895
2896 /* Intersect all values in INTER with single value lattices in PLATS (while
2897 subtracting OFFSET). */
2898
2899 static void
intersect_with_plats(struct ipcp_param_lattices * plats,vec<ipa_agg_jf_item> * inter,HOST_WIDE_INT offset)2900 intersect_with_plats (struct ipcp_param_lattices *plats,
2901 vec<ipa_agg_jf_item> *inter,
2902 HOST_WIDE_INT offset)
2903 {
2904 struct ipcp_agg_lattice *aglat;
2905 struct ipa_agg_jf_item *item;
2906 int k;
2907
2908 if (!plats->aggs || plats->aggs_contain_variable || plats->aggs_bottom)
2909 {
2910 inter->release ();
2911 return;
2912 }
2913
2914 aglat = plats->aggs;
2915 FOR_EACH_VEC_ELT (*inter, k, item)
2916 {
2917 bool found = false;
2918 if (!item->value)
2919 continue;
2920 while (aglat)
2921 {
2922 if (aglat->offset - offset > item->offset)
2923 break;
2924 if (aglat->offset - offset == item->offset)
2925 {
2926 gcc_checking_assert (item->value);
2927 if (values_equal_for_ipcp_p (item->value, aglat->values->value))
2928 found = true;
2929 break;
2930 }
2931 aglat = aglat->next;
2932 }
2933 if (!found)
2934 item->value = NULL_TREE;
2935 }
2936 }
2937
2938 /* Copy agggregate replacement values of NODE (which is an IPA-CP clone) to the
2939 vector result while subtracting OFFSET from the individual value offsets. */
2940
2941 static vec<ipa_agg_jf_item>
agg_replacements_to_vector(struct cgraph_node * node,int index,HOST_WIDE_INT offset)2942 agg_replacements_to_vector (struct cgraph_node *node, int index,
2943 HOST_WIDE_INT offset)
2944 {
2945 struct ipa_agg_replacement_value *av;
2946 vec<ipa_agg_jf_item> res = vNULL;
2947
2948 for (av = ipa_get_agg_replacements_for_node (node); av; av = av->next)
2949 if (av->index == index
2950 && (av->offset - offset) >= 0)
2951 {
2952 struct ipa_agg_jf_item item;
2953 gcc_checking_assert (av->value);
2954 item.offset = av->offset - offset;
2955 item.value = av->value;
2956 res.safe_push (item);
2957 }
2958
2959 return res;
2960 }
2961
2962 /* Intersect all values in INTER with those that we have already scheduled to
2963 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
2964 (while subtracting OFFSET). */
2965
2966 static void
intersect_with_agg_replacements(struct cgraph_node * node,int index,vec<ipa_agg_jf_item> * inter,HOST_WIDE_INT offset)2967 intersect_with_agg_replacements (struct cgraph_node *node, int index,
2968 vec<ipa_agg_jf_item> *inter,
2969 HOST_WIDE_INT offset)
2970 {
2971 struct ipa_agg_replacement_value *srcvals;
2972 struct ipa_agg_jf_item *item;
2973 int i;
2974
2975 srcvals = ipa_get_agg_replacements_for_node (node);
2976 if (!srcvals)
2977 {
2978 inter->release ();
2979 return;
2980 }
2981
2982 FOR_EACH_VEC_ELT (*inter, i, item)
2983 {
2984 struct ipa_agg_replacement_value *av;
2985 bool found = false;
2986 if (!item->value)
2987 continue;
2988 for (av = srcvals; av; av = av->next)
2989 {
2990 gcc_checking_assert (av->value);
2991 if (av->index == index
2992 && av->offset - offset == item->offset)
2993 {
2994 if (values_equal_for_ipcp_p (item->value, av->value))
2995 found = true;
2996 break;
2997 }
2998 }
2999 if (!found)
3000 item->value = NULL_TREE;
3001 }
3002 }
3003
3004 /* Intersect values in INTER with aggregate values that come along edge CS to
3005 parameter number INDEX and return it. If INTER does not actually exist yet,
3006 copy all incoming values to it. If we determine we ended up with no values
3007 whatsoever, return a released vector. */
3008
3009 static vec<ipa_agg_jf_item>
intersect_aggregates_with_edge(struct cgraph_edge * cs,int index,vec<ipa_agg_jf_item> inter)3010 intersect_aggregates_with_edge (struct cgraph_edge *cs, int index,
3011 vec<ipa_agg_jf_item> inter)
3012 {
3013 struct ipa_jump_func *jfunc;
3014 jfunc = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), index);
3015 if (jfunc->type == IPA_JF_PASS_THROUGH
3016 && ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
3017 {
3018 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
3019 int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
3020
3021 if (caller_info->ipcp_orig_node)
3022 {
3023 struct cgraph_node *orig_node = caller_info->ipcp_orig_node;
3024 struct ipcp_param_lattices *orig_plats;
3025 orig_plats = ipa_get_parm_lattices (IPA_NODE_REF (orig_node),
3026 src_idx);
3027 if (agg_pass_through_permissible_p (orig_plats, jfunc))
3028 {
3029 if (!inter.exists ())
3030 inter = agg_replacements_to_vector (cs->caller, src_idx, 0);
3031 else
3032 intersect_with_agg_replacements (cs->caller, src_idx,
3033 &inter, 0);
3034 }
3035 else
3036 {
3037 inter.release ();
3038 return vNULL;
3039 }
3040 }
3041 else
3042 {
3043 struct ipcp_param_lattices *src_plats;
3044 src_plats = ipa_get_parm_lattices (caller_info, src_idx);
3045 if (agg_pass_through_permissible_p (src_plats, jfunc))
3046 {
3047 /* Currently we do not produce clobber aggregate jump
3048 functions, adjust when we do. */
3049 gcc_checking_assert (!jfunc->agg.items);
3050 if (!inter.exists ())
3051 inter = copy_plats_to_inter (src_plats, 0);
3052 else
3053 intersect_with_plats (src_plats, &inter, 0);
3054 }
3055 else
3056 {
3057 inter.release ();
3058 return vNULL;
3059 }
3060 }
3061 }
3062 else if (jfunc->type == IPA_JF_ANCESTOR
3063 && ipa_get_jf_ancestor_agg_preserved (jfunc))
3064 {
3065 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
3066 int src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
3067 struct ipcp_param_lattices *src_plats;
3068 HOST_WIDE_INT delta = ipa_get_jf_ancestor_offset (jfunc);
3069
3070 if (caller_info->ipcp_orig_node)
3071 {
3072 if (!inter.exists ())
3073 inter = agg_replacements_to_vector (cs->caller, src_idx, delta);
3074 else
3075 intersect_with_agg_replacements (cs->caller, src_idx, &inter,
3076 delta);
3077 }
3078 else
3079 {
3080 src_plats = ipa_get_parm_lattices (caller_info, src_idx);;
3081 /* Currently we do not produce clobber aggregate jump
3082 functions, adjust when we do. */
3083 gcc_checking_assert (!src_plats->aggs || !jfunc->agg.items);
3084 if (!inter.exists ())
3085 inter = copy_plats_to_inter (src_plats, delta);
3086 else
3087 intersect_with_plats (src_plats, &inter, delta);
3088 }
3089 }
3090 else if (jfunc->agg.items)
3091 {
3092 struct ipa_agg_jf_item *item;
3093 int k;
3094
3095 if (!inter.exists ())
3096 for (unsigned i = 0; i < jfunc->agg.items->length (); i++)
3097 inter.safe_push ((*jfunc->agg.items)[i]);
3098 else
3099 FOR_EACH_VEC_ELT (inter, k, item)
3100 {
3101 int l = 0;
3102 bool found = false;;
3103
3104 if (!item->value)
3105 continue;
3106
3107 while ((unsigned) l < jfunc->agg.items->length ())
3108 {
3109 struct ipa_agg_jf_item *ti;
3110 ti = &(*jfunc->agg.items)[l];
3111 if (ti->offset > item->offset)
3112 break;
3113 if (ti->offset == item->offset)
3114 {
3115 gcc_checking_assert (ti->value);
3116 if (values_equal_for_ipcp_p (item->value,
3117 ti->value))
3118 found = true;
3119 break;
3120 }
3121 l++;
3122 }
3123 if (!found)
3124 item->value = NULL;
3125 }
3126 }
3127 else
3128 {
3129 inter.release ();
3130 return vec<ipa_agg_jf_item>();
3131 }
3132 return inter;
3133 }
3134
3135 /* Look at edges in CALLERS and collect all known aggregate values that arrive
3136 from all of them. */
3137
3138 static struct ipa_agg_replacement_value *
find_aggregate_values_for_callers_subset(struct cgraph_node * node,vec<cgraph_edge_p> callers)3139 find_aggregate_values_for_callers_subset (struct cgraph_node *node,
3140 vec<cgraph_edge_p> callers)
3141 {
3142 struct ipa_node_params *dest_info = IPA_NODE_REF (node);
3143 struct ipa_agg_replacement_value *res;
3144 struct ipa_agg_replacement_value **tail = &res;
3145 struct cgraph_edge *cs;
3146 int i, j, count = ipa_get_param_count (dest_info);
3147
3148 FOR_EACH_VEC_ELT (callers, j, cs)
3149 {
3150 int c = ipa_get_cs_argument_count (IPA_EDGE_REF (cs));
3151 if (c < count)
3152 count = c;
3153 }
3154
3155 for (i = 0; i < count ; i++)
3156 {
3157 struct cgraph_edge *cs;
3158 vec<ipa_agg_jf_item> inter = vNULL;
3159 struct ipa_agg_jf_item *item;
3160 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (dest_info, i);
3161 int j;
3162
3163 /* Among other things, the following check should deal with all by_ref
3164 mismatches. */
3165 if (plats->aggs_bottom)
3166 continue;
3167
3168 FOR_EACH_VEC_ELT (callers, j, cs)
3169 {
3170 inter = intersect_aggregates_with_edge (cs, i, inter);
3171
3172 if (!inter.exists ())
3173 goto next_param;
3174 }
3175
3176 FOR_EACH_VEC_ELT (inter, j, item)
3177 {
3178 struct ipa_agg_replacement_value *v;
3179
3180 if (!item->value)
3181 continue;
3182
3183 v = ggc_alloc_ipa_agg_replacement_value ();
3184 v->index = i;
3185 v->offset = item->offset;
3186 v->value = item->value;
3187 v->by_ref = plats->aggs_by_ref;
3188 *tail = v;
3189 tail = &v->next;
3190 }
3191
3192 next_param:
3193 if (inter.exists ())
3194 inter.release ();
3195 }
3196 *tail = NULL;
3197 return res;
3198 }
3199
3200 /* Turn KNOWN_AGGS into a list of aggreate replacement values. */
3201
3202 static struct ipa_agg_replacement_value *
known_aggs_to_agg_replacement_list(vec<ipa_agg_jump_function> known_aggs)3203 known_aggs_to_agg_replacement_list (vec<ipa_agg_jump_function> known_aggs)
3204 {
3205 struct ipa_agg_replacement_value *res;
3206 struct ipa_agg_replacement_value **tail = &res;
3207 struct ipa_agg_jump_function *aggjf;
3208 struct ipa_agg_jf_item *item;
3209 int i, j;
3210
3211 FOR_EACH_VEC_ELT (known_aggs, i, aggjf)
3212 FOR_EACH_VEC_SAFE_ELT (aggjf->items, j, item)
3213 {
3214 struct ipa_agg_replacement_value *v;
3215 v = ggc_alloc_ipa_agg_replacement_value ();
3216 v->index = i;
3217 v->offset = item->offset;
3218 v->value = item->value;
3219 v->by_ref = aggjf->by_ref;
3220 *tail = v;
3221 tail = &v->next;
3222 }
3223 *tail = NULL;
3224 return res;
3225 }
3226
3227 /* Determine whether CS also brings all scalar values that the NODE is
3228 specialized for. */
3229
3230 static bool
cgraph_edge_brings_all_scalars_for_node(struct cgraph_edge * cs,struct cgraph_node * node)3231 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge *cs,
3232 struct cgraph_node *node)
3233 {
3234 struct ipa_node_params *dest_info = IPA_NODE_REF (node);
3235 int count = ipa_get_param_count (dest_info);
3236 struct ipa_node_params *caller_info;
3237 struct ipa_edge_args *args;
3238 int i;
3239
3240 caller_info = IPA_NODE_REF (cs->caller);
3241 args = IPA_EDGE_REF (cs);
3242 for (i = 0; i < count; i++)
3243 {
3244 struct ipa_jump_func *jump_func;
3245 tree val, t;
3246
3247 val = dest_info->known_vals[i];
3248 if (!val)
3249 continue;
3250
3251 if (i >= ipa_get_cs_argument_count (args))
3252 return false;
3253 jump_func = ipa_get_ith_jump_func (args, i);
3254 t = ipa_value_from_jfunc (caller_info, jump_func);
3255 if (!t || !values_equal_for_ipcp_p (val, t))
3256 return false;
3257 }
3258 return true;
3259 }
3260
3261 /* Determine whether CS also brings all aggregate values that NODE is
3262 specialized for. */
3263 static bool
cgraph_edge_brings_all_agg_vals_for_node(struct cgraph_edge * cs,struct cgraph_node * node)3264 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge *cs,
3265 struct cgraph_node *node)
3266 {
3267 struct ipa_node_params *orig_caller_info = IPA_NODE_REF (cs->caller);
3268 struct ipa_node_params *orig_node_info;
3269 struct ipa_agg_replacement_value *aggval;
3270 int i, ec, count;
3271
3272 aggval = ipa_get_agg_replacements_for_node (node);
3273 if (!aggval)
3274 return true;
3275
3276 count = ipa_get_param_count (IPA_NODE_REF (node));
3277 ec = ipa_get_cs_argument_count (IPA_EDGE_REF (cs));
3278 if (ec < count)
3279 for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next)
3280 if (aggval->index >= ec)
3281 return false;
3282
3283 orig_node_info = IPA_NODE_REF (IPA_NODE_REF (node)->ipcp_orig_node);
3284 if (orig_caller_info->ipcp_orig_node)
3285 orig_caller_info = IPA_NODE_REF (orig_caller_info->ipcp_orig_node);
3286
3287 for (i = 0; i < count; i++)
3288 {
3289 static vec<ipa_agg_jf_item> values = vec<ipa_agg_jf_item>();
3290 struct ipcp_param_lattices *plats;
3291 bool interesting = false;
3292 for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next)
3293 if (aggval->index == i)
3294 {
3295 interesting = true;
3296 break;
3297 }
3298 if (!interesting)
3299 continue;
3300
3301 plats = ipa_get_parm_lattices (orig_node_info, aggval->index);
3302 if (plats->aggs_bottom)
3303 return false;
3304
3305 values = intersect_aggregates_with_edge (cs, i, values);
3306 if (!values.exists ())
3307 return false;
3308
3309 for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next)
3310 if (aggval->index == i)
3311 {
3312 struct ipa_agg_jf_item *item;
3313 int j;
3314 bool found = false;
3315 FOR_EACH_VEC_ELT (values, j, item)
3316 if (item->value
3317 && item->offset == av->offset
3318 && values_equal_for_ipcp_p (item->value, av->value))
3319 {
3320 found = true;
3321 break;
3322 }
3323 if (!found)
3324 {
3325 values.release ();
3326 return false;
3327 }
3328 }
3329 }
3330 return true;
3331 }
3332
3333 /* Given an original NODE and a VAL for which we have already created a
3334 specialized clone, look whether there are incoming edges that still lead
3335 into the old node but now also bring the requested value and also conform to
3336 all other criteria such that they can be redirected the the special node.
3337 This function can therefore redirect the final edge in a SCC. */
3338
3339 static void
perhaps_add_new_callers(struct cgraph_node * node,struct ipcp_value * val)3340 perhaps_add_new_callers (struct cgraph_node *node, struct ipcp_value *val)
3341 {
3342 struct ipcp_value_source *src;
3343 gcov_type redirected_sum = 0;
3344
3345 for (src = val->sources; src; src = src->next)
3346 {
3347 struct cgraph_edge *cs = src->cs;
3348 while (cs)
3349 {
3350 enum availability availability;
3351 struct cgraph_node *dst = cgraph_function_node (cs->callee,
3352 &availability);
3353 if ((dst == node || IPA_NODE_REF (dst)->is_all_contexts_clone)
3354 && availability > AVAIL_OVERWRITABLE
3355 && cgraph_edge_brings_value_p (cs, src))
3356 {
3357 if (cgraph_edge_brings_all_scalars_for_node (cs, val->spec_node)
3358 && cgraph_edge_brings_all_agg_vals_for_node (cs,
3359 val->spec_node))
3360 {
3361 if (dump_file)
3362 fprintf (dump_file, " - adding an extra caller %s/%i"
3363 " of %s/%i\n",
3364 xstrdup (cs->caller->name ()),
3365 cs->caller->order,
3366 xstrdup (val->spec_node->name ()),
3367 val->spec_node->order);
3368
3369 cgraph_redirect_edge_callee (cs, val->spec_node);
3370 redirected_sum += cs->count;
3371 }
3372 }
3373 cs = get_next_cgraph_edge_clone (cs);
3374 }
3375 }
3376
3377 if (redirected_sum)
3378 update_specialized_profile (val->spec_node, node, redirected_sum);
3379 }
3380
3381
3382 /* Copy KNOWN_BINFOS to KNOWN_VALS. */
3383
3384 static void
move_binfos_to_values(vec<tree> known_vals,vec<tree> known_binfos)3385 move_binfos_to_values (vec<tree> known_vals,
3386 vec<tree> known_binfos)
3387 {
3388 tree t;
3389 int i;
3390
3391 for (i = 0; known_binfos.iterate (i, &t); i++)
3392 if (t)
3393 known_vals[i] = t;
3394 }
3395
3396 /* Return true if there is a replacement equivalent to VALUE, INDEX and OFFSET
3397 among those in the AGGVALS list. */
3398
3399 DEBUG_FUNCTION bool
ipcp_val_in_agg_replacements_p(struct ipa_agg_replacement_value * aggvals,int index,HOST_WIDE_INT offset,tree value)3400 ipcp_val_in_agg_replacements_p (struct ipa_agg_replacement_value *aggvals,
3401 int index, HOST_WIDE_INT offset, tree value)
3402 {
3403 while (aggvals)
3404 {
3405 if (aggvals->index == index
3406 && aggvals->offset == offset
3407 && values_equal_for_ipcp_p (aggvals->value, value))
3408 return true;
3409 aggvals = aggvals->next;
3410 }
3411 return false;
3412 }
3413
3414 /* Decide wheter to create a special version of NODE for value VAL of parameter
3415 at the given INDEX. If OFFSET is -1, the value is for the parameter itself,
3416 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS,
3417 KNOWN_BINFOS and KNOWN_AGGS describe the other already known values. */
3418
3419 static bool
decide_about_value(struct cgraph_node * node,int index,HOST_WIDE_INT offset,struct ipcp_value * val,vec<tree> known_csts,vec<tree> known_binfos)3420 decide_about_value (struct cgraph_node *node, int index, HOST_WIDE_INT offset,
3421 struct ipcp_value *val, vec<tree> known_csts,
3422 vec<tree> known_binfos)
3423 {
3424 struct ipa_agg_replacement_value *aggvals;
3425 int freq_sum, caller_count;
3426 gcov_type count_sum;
3427 vec<cgraph_edge_p> callers;
3428 vec<tree> kv;
3429
3430 if (val->spec_node)
3431 {
3432 perhaps_add_new_callers (node, val);
3433 return false;
3434 }
3435 else if (val->local_size_cost + overall_size > max_new_size)
3436 {
3437 if (dump_file && (dump_flags & TDF_DETAILS))
3438 fprintf (dump_file, " Ignoring candidate value because "
3439 "max_new_size would be reached with %li.\n",
3440 val->local_size_cost + overall_size);
3441 return false;
3442 }
3443 else if (!get_info_about_necessary_edges (val, &freq_sum, &count_sum,
3444 &caller_count))
3445 return false;
3446
3447 if (dump_file && (dump_flags & TDF_DETAILS))
3448 {
3449 fprintf (dump_file, " - considering value ");
3450 print_ipcp_constant_value (dump_file, val->value);
3451 fprintf (dump_file, " for ");
3452 ipa_dump_param (dump_file, IPA_NODE_REF (node), index);
3453 if (offset != -1)
3454 fprintf (dump_file, ", offset: " HOST_WIDE_INT_PRINT_DEC, offset);
3455 fprintf (dump_file, " (caller_count: %i)\n", caller_count);
3456 }
3457
3458 if (!good_cloning_opportunity_p (node, val->local_time_benefit,
3459 freq_sum, count_sum,
3460 val->local_size_cost)
3461 && !good_cloning_opportunity_p (node,
3462 val->local_time_benefit
3463 + val->prop_time_benefit,
3464 freq_sum, count_sum,
3465 val->local_size_cost
3466 + val->prop_size_cost))
3467 return false;
3468
3469 if (dump_file)
3470 fprintf (dump_file, " Creating a specialized node of %s/%i.\n",
3471 node->name (), node->order);
3472
3473 callers = gather_edges_for_value (val, caller_count);
3474 kv = known_csts.copy ();
3475 move_binfos_to_values (kv, known_binfos);
3476 if (offset == -1)
3477 kv[index] = val->value;
3478 find_more_scalar_values_for_callers_subset (node, kv, callers);
3479 aggvals = find_aggregate_values_for_callers_subset (node, callers);
3480 gcc_checking_assert (offset == -1
3481 || ipcp_val_in_agg_replacements_p (aggvals, index,
3482 offset, val->value));
3483 val->spec_node = create_specialized_node (node, kv, aggvals, callers);
3484 overall_size += val->local_size_cost;
3485
3486 /* TODO: If for some lattice there is only one other known value
3487 left, make a special node for it too. */
3488
3489 return true;
3490 }
3491
3492 /* Decide whether and what specialized clones of NODE should be created. */
3493
3494 static bool
decide_whether_version_node(struct cgraph_node * node)3495 decide_whether_version_node (struct cgraph_node *node)
3496 {
3497 struct ipa_node_params *info = IPA_NODE_REF (node);
3498 int i, count = ipa_get_param_count (info);
3499 vec<tree> known_csts, known_binfos;
3500 vec<ipa_agg_jump_function> known_aggs = vNULL;
3501 bool ret = false;
3502
3503 if (count == 0)
3504 return false;
3505
3506 if (dump_file && (dump_flags & TDF_DETAILS))
3507 fprintf (dump_file, "\nEvaluating opportunities for %s/%i.\n",
3508 node->name (), node->order);
3509
3510 gather_context_independent_values (info, &known_csts, &known_binfos,
3511 info->do_clone_for_all_contexts ? &known_aggs
3512 : NULL, NULL);
3513
3514 for (i = 0; i < count ;i++)
3515 {
3516 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
3517 struct ipcp_lattice *lat = &plats->itself;
3518 struct ipcp_value *val;
3519
3520 if (!lat->bottom
3521 && !known_csts[i]
3522 && !known_binfos[i])
3523 for (val = lat->values; val; val = val->next)
3524 ret |= decide_about_value (node, i, -1, val, known_csts,
3525 known_binfos);
3526
3527 if (!plats->aggs_bottom)
3528 {
3529 struct ipcp_agg_lattice *aglat;
3530 struct ipcp_value *val;
3531 for (aglat = plats->aggs; aglat; aglat = aglat->next)
3532 if (!aglat->bottom && aglat->values
3533 /* If the following is false, the one value is in
3534 known_aggs. */
3535 && (plats->aggs_contain_variable
3536 || !ipa_lat_is_single_const (aglat)))
3537 for (val = aglat->values; val; val = val->next)
3538 ret |= decide_about_value (node, i, aglat->offset, val,
3539 known_csts, known_binfos);
3540 }
3541 info = IPA_NODE_REF (node);
3542 }
3543
3544 if (info->do_clone_for_all_contexts)
3545 {
3546 struct cgraph_node *clone;
3547 vec<cgraph_edge_p> callers;
3548
3549 if (dump_file)
3550 fprintf (dump_file, " - Creating a specialized node of %s/%i "
3551 "for all known contexts.\n", node->name (),
3552 node->order);
3553
3554 callers = collect_callers_of_node (node);
3555 move_binfos_to_values (known_csts, known_binfos);
3556 clone = create_specialized_node (node, known_csts,
3557 known_aggs_to_agg_replacement_list (known_aggs),
3558 callers);
3559 info = IPA_NODE_REF (node);
3560 info->do_clone_for_all_contexts = false;
3561 IPA_NODE_REF (clone)->is_all_contexts_clone = true;
3562 for (i = 0; i < count ; i++)
3563 vec_free (known_aggs[i].items);
3564 known_aggs.release ();
3565 ret = true;
3566 }
3567 else
3568 known_csts.release ();
3569
3570 known_binfos.release ();
3571 return ret;
3572 }
3573
3574 /* Transitively mark all callees of NODE within the same SCC as not dead. */
3575
3576 static void
spread_undeadness(struct cgraph_node * node)3577 spread_undeadness (struct cgraph_node *node)
3578 {
3579 struct cgraph_edge *cs;
3580
3581 for (cs = node->callees; cs; cs = cs->next_callee)
3582 if (ipa_edge_within_scc (cs))
3583 {
3584 struct cgraph_node *callee;
3585 struct ipa_node_params *info;
3586
3587 callee = cgraph_function_node (cs->callee, NULL);
3588 info = IPA_NODE_REF (callee);
3589
3590 if (info->node_dead)
3591 {
3592 info->node_dead = 0;
3593 spread_undeadness (callee);
3594 }
3595 }
3596 }
3597
3598 /* Return true if NODE has a caller from outside of its SCC that is not
3599 dead. Worker callback for cgraph_for_node_and_aliases. */
3600
3601 static bool
has_undead_caller_from_outside_scc_p(struct cgraph_node * node,void * data ATTRIBUTE_UNUSED)3602 has_undead_caller_from_outside_scc_p (struct cgraph_node *node,
3603 void *data ATTRIBUTE_UNUSED)
3604 {
3605 struct cgraph_edge *cs;
3606
3607 for (cs = node->callers; cs; cs = cs->next_caller)
3608 if (cs->caller->thunk.thunk_p
3609 && cgraph_for_node_and_aliases (cs->caller,
3610 has_undead_caller_from_outside_scc_p,
3611 NULL, true))
3612 return true;
3613 else if (!ipa_edge_within_scc (cs)
3614 && !IPA_NODE_REF (cs->caller)->node_dead)
3615 return true;
3616 return false;
3617 }
3618
3619
3620 /* Identify nodes within the same SCC as NODE which are no longer needed
3621 because of new clones and will be removed as unreachable. */
3622
3623 static void
identify_dead_nodes(struct cgraph_node * node)3624 identify_dead_nodes (struct cgraph_node *node)
3625 {
3626 struct cgraph_node *v;
3627 for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
3628 if (cgraph_will_be_removed_from_program_if_no_direct_calls (v)
3629 && !cgraph_for_node_and_aliases (v,
3630 has_undead_caller_from_outside_scc_p,
3631 NULL, true))
3632 IPA_NODE_REF (v)->node_dead = 1;
3633
3634 for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
3635 if (!IPA_NODE_REF (v)->node_dead)
3636 spread_undeadness (v);
3637
3638 if (dump_file && (dump_flags & TDF_DETAILS))
3639 {
3640 for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
3641 if (IPA_NODE_REF (v)->node_dead)
3642 fprintf (dump_file, " Marking node as dead: %s/%i.\n",
3643 v->name (), v->order);
3644 }
3645 }
3646
3647 /* The decision stage. Iterate over the topological order of call graph nodes
3648 TOPO and make specialized clones if deemed beneficial. */
3649
3650 static void
ipcp_decision_stage(struct topo_info * topo)3651 ipcp_decision_stage (struct topo_info *topo)
3652 {
3653 int i;
3654
3655 if (dump_file)
3656 fprintf (dump_file, "\nIPA decision stage:\n\n");
3657
3658 for (i = topo->nnodes - 1; i >= 0; i--)
3659 {
3660 struct cgraph_node *node = topo->order[i];
3661 bool change = false, iterate = true;
3662
3663 while (iterate)
3664 {
3665 struct cgraph_node *v;
3666 iterate = false;
3667 for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
3668 if (cgraph_function_with_gimple_body_p (v)
3669 && ipcp_versionable_function_p (v))
3670 iterate |= decide_whether_version_node (v);
3671
3672 change |= iterate;
3673 }
3674 if (change)
3675 identify_dead_nodes (node);
3676 }
3677 }
3678
3679 /* The IPCP driver. */
3680
3681 static unsigned int
ipcp_driver(void)3682 ipcp_driver (void)
3683 {
3684 struct cgraph_2edge_hook_list *edge_duplication_hook_holder;
3685 struct cgraph_edge_hook_list *edge_removal_hook_holder;
3686 struct topo_info topo;
3687
3688 ipa_check_create_node_params ();
3689 ipa_check_create_edge_args ();
3690 grow_edge_clone_vectors ();
3691 edge_duplication_hook_holder =
3692 cgraph_add_edge_duplication_hook (&ipcp_edge_duplication_hook, NULL);
3693 edge_removal_hook_holder =
3694 cgraph_add_edge_removal_hook (&ipcp_edge_removal_hook, NULL);
3695
3696 ipcp_values_pool = create_alloc_pool ("IPA-CP values",
3697 sizeof (struct ipcp_value), 32);
3698 ipcp_sources_pool = create_alloc_pool ("IPA-CP value sources",
3699 sizeof (struct ipcp_value_source), 64);
3700 ipcp_agg_lattice_pool = create_alloc_pool ("IPA_CP aggregate lattices",
3701 sizeof (struct ipcp_agg_lattice),
3702 32);
3703 if (dump_file)
3704 {
3705 fprintf (dump_file, "\nIPA structures before propagation:\n");
3706 if (dump_flags & TDF_DETAILS)
3707 ipa_print_all_params (dump_file);
3708 ipa_print_all_jump_functions (dump_file);
3709 }
3710
3711 /* Topological sort. */
3712 build_toporder_info (&topo);
3713 /* Do the interprocedural propagation. */
3714 ipcp_propagate_stage (&topo);
3715 /* Decide what constant propagation and cloning should be performed. */
3716 ipcp_decision_stage (&topo);
3717
3718 /* Free all IPCP structures. */
3719 free_toporder_info (&topo);
3720 next_edge_clone.release ();
3721 cgraph_remove_edge_removal_hook (edge_removal_hook_holder);
3722 cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder);
3723 ipa_free_all_structures_after_ipa_cp ();
3724 if (dump_file)
3725 fprintf (dump_file, "\nIPA constant propagation end\n");
3726 return 0;
3727 }
3728
3729 /* Initialization and computation of IPCP data structures. This is the initial
3730 intraprocedural analysis of functions, which gathers information to be
3731 propagated later on. */
3732
3733 static void
ipcp_generate_summary(void)3734 ipcp_generate_summary (void)
3735 {
3736 struct cgraph_node *node;
3737
3738 if (dump_file)
3739 fprintf (dump_file, "\nIPA constant propagation start:\n");
3740 ipa_register_cgraph_hooks ();
3741
3742 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
3743 {
3744 node->local.versionable
3745 = tree_versionable_function_p (node->decl);
3746 ipa_analyze_node (node);
3747 }
3748 }
3749
3750 /* Write ipcp summary for nodes in SET. */
3751
3752 static void
ipcp_write_summary(void)3753 ipcp_write_summary (void)
3754 {
3755 ipa_prop_write_jump_functions ();
3756 }
3757
3758 /* Read ipcp summary. */
3759
3760 static void
ipcp_read_summary(void)3761 ipcp_read_summary (void)
3762 {
3763 ipa_prop_read_jump_functions ();
3764 }
3765
3766 /* Gate for IPCP optimization. */
3767
3768 static bool
cgraph_gate_cp(void)3769 cgraph_gate_cp (void)
3770 {
3771 /* FIXME: We should remove the optimize check after we ensure we never run
3772 IPA passes when not optimizing. */
3773 return flag_ipa_cp && optimize;
3774 }
3775
3776 namespace {
3777
3778 const pass_data pass_data_ipa_cp =
3779 {
3780 IPA_PASS, /* type */
3781 "cp", /* name */
3782 OPTGROUP_NONE, /* optinfo_flags */
3783 true, /* has_gate */
3784 true, /* has_execute */
3785 TV_IPA_CONSTANT_PROP, /* tv_id */
3786 0, /* properties_required */
3787 0, /* properties_provided */
3788 0, /* properties_destroyed */
3789 0, /* todo_flags_start */
3790 ( TODO_dump_symtab | TODO_remove_functions ), /* todo_flags_finish */
3791 };
3792
3793 class pass_ipa_cp : public ipa_opt_pass_d
3794 {
3795 public:
pass_ipa_cp(gcc::context * ctxt)3796 pass_ipa_cp (gcc::context *ctxt)
3797 : ipa_opt_pass_d (pass_data_ipa_cp, ctxt,
3798 ipcp_generate_summary, /* generate_summary */
3799 ipcp_write_summary, /* write_summary */
3800 ipcp_read_summary, /* read_summary */
3801 ipa_prop_write_all_agg_replacement, /*
3802 write_optimization_summary */
3803 ipa_prop_read_all_agg_replacement, /*
3804 read_optimization_summary */
3805 NULL, /* stmt_fixup */
3806 0, /* function_transform_todo_flags_start */
3807 ipcp_transform_function, /* function_transform */
3808 NULL) /* variable_transform */
3809 {}
3810
3811 /* opt_pass methods: */
gate()3812 bool gate () { return cgraph_gate_cp (); }
execute()3813 unsigned int execute () { return ipcp_driver (); }
3814
3815 }; // class pass_ipa_cp
3816
3817 } // anon namespace
3818
3819 ipa_opt_pass_d *
make_pass_ipa_cp(gcc::context * ctxt)3820 make_pass_ipa_cp (gcc::context *ctxt)
3821 {
3822 return new pass_ipa_cp (ctxt);
3823 }
3824