1 /* Interprocedural constant propagation
2 Copyright (C) 2005-2018 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 "backend.h"
107 #include "tree.h"
108 #include "gimple-expr.h"
109 #include "predict.h"
110 #include "alloc-pool.h"
111 #include "tree-pass.h"
112 #include "cgraph.h"
113 #include "diagnostic.h"
114 #include "fold-const.h"
115 #include "gimple-fold.h"
116 #include "symbol-summary.h"
117 #include "tree-vrp.h"
118 #include "ipa-prop.h"
119 #include "tree-pretty-print.h"
120 #include "tree-inline.h"
121 #include "params.h"
122 #include "ipa-fnsummary.h"
123 #include "ipa-utils.h"
124 #include "tree-ssa-ccp.h"
125 #include "stringpool.h"
126 #include "attribs.h"
127
128 template <typename valtype> class ipcp_value;
129
130 /* Describes a particular source for an IPA-CP value. */
131
132 template <typename valtype>
133 class ipcp_value_source
134 {
135 public:
136 /* Aggregate offset of the source, negative if the source is scalar value of
137 the argument itself. */
138 HOST_WIDE_INT offset;
139 /* The incoming edge that brought the value. */
140 cgraph_edge *cs;
141 /* If the jump function that resulted into his value was a pass-through or an
142 ancestor, this is the ipcp_value of the caller from which the described
143 value has been derived. Otherwise it is NULL. */
144 ipcp_value<valtype> *val;
145 /* Next pointer in a linked list of sources of a value. */
146 ipcp_value_source *next;
147 /* If the jump function that resulted into his value was a pass-through or an
148 ancestor, this is the index of the parameter of the caller the jump
149 function references. */
150 int index;
151 };
152
153 /* Common ancestor for all ipcp_value instantiations. */
154
155 class ipcp_value_base
156 {
157 public:
158 /* Time benefit and size cost that specializing the function for this value
159 would bring about in this function alone. */
160 int local_time_benefit, local_size_cost;
161 /* Time benefit and size cost that specializing the function for this value
162 can bring about in it's callees (transitively). */
163 int prop_time_benefit, prop_size_cost;
164
ipcp_value_base()165 ipcp_value_base ()
166 : local_time_benefit (0), local_size_cost (0),
167 prop_time_benefit (0), prop_size_cost (0) {}
168 };
169
170 /* Describes one particular value stored in struct ipcp_lattice. */
171
172 template <typename valtype>
173 class ipcp_value : public ipcp_value_base
174 {
175 public:
176 /* The actual value for the given parameter. */
177 valtype value;
178 /* The list of sources from which this value originates. */
179 ipcp_value_source <valtype> *sources;
180 /* Next pointers in a linked list of all values in a lattice. */
181 ipcp_value *next;
182 /* Next pointers in a linked list of values in a strongly connected component
183 of values. */
184 ipcp_value *scc_next;
185 /* Next pointers in a linked list of SCCs of values sorted topologically
186 according their sources. */
187 ipcp_value *topo_next;
188 /* A specialized node created for this value, NULL if none has been (so far)
189 created. */
190 cgraph_node *spec_node;
191 /* Depth first search number and low link for topological sorting of
192 values. */
193 int dfs, low_link;
194 /* True if this valye is currently on the topo-sort stack. */
195 bool on_stack;
196
ipcp_value()197 ipcp_value()
198 : sources (0), next (0), scc_next (0), topo_next (0),
199 spec_node (0), dfs (0), low_link (0), on_stack (false) {}
200
201 void add_source (cgraph_edge *cs, ipcp_value *src_val, int src_idx,
202 HOST_WIDE_INT offset);
203 };
204
205 /* Lattice describing potential values of a formal parameter of a function, or
206 a part of an aggregate. TOP is represented by a lattice with zero values
207 and with contains_variable and bottom flags cleared. BOTTOM is represented
208 by a lattice with the bottom flag set. In that case, values and
209 contains_variable flag should be disregarded. */
210
211 template <typename valtype>
212 class ipcp_lattice
213 {
214 public:
215 /* The list of known values and types in this lattice. Note that values are
216 not deallocated if a lattice is set to bottom because there may be value
217 sources referencing them. */
218 ipcp_value<valtype> *values;
219 /* Number of known values and types in this lattice. */
220 int values_count;
221 /* The lattice contains a variable component (in addition to values). */
222 bool contains_variable;
223 /* The value of the lattice is bottom (i.e. variable and unusable for any
224 propagation). */
225 bool bottom;
226
227 inline bool is_single_const ();
228 inline bool set_to_bottom ();
229 inline bool set_contains_variable ();
230 bool add_value (valtype newval, cgraph_edge *cs,
231 ipcp_value<valtype> *src_val = NULL,
232 int src_idx = 0, HOST_WIDE_INT offset = -1);
233 void print (FILE * f, bool dump_sources, bool dump_benefits);
234 };
235
236 /* Lattice of tree values with an offset to describe a part of an
237 aggregate. */
238
239 class ipcp_agg_lattice : public ipcp_lattice<tree>
240 {
241 public:
242 /* Offset that is being described by this lattice. */
243 HOST_WIDE_INT offset;
244 /* Size so that we don't have to re-compute it every time we traverse the
245 list. Must correspond to TYPE_SIZE of all lat values. */
246 HOST_WIDE_INT size;
247 /* Next element of the linked list. */
248 struct ipcp_agg_lattice *next;
249 };
250
251 /* Lattice of known bits, only capable of holding one value.
252 Bitwise constant propagation propagates which bits of a
253 value are constant.
254 For eg:
255 int f(int x)
256 {
257 return some_op (x);
258 }
259
260 int f1(int y)
261 {
262 if (cond)
263 return f (y & 0xff);
264 else
265 return f (y & 0xf);
266 }
267
268 In the above case, the param 'x' will always have all
269 the bits (except the bits in lsb) set to 0.
270 Hence the mask of 'x' would be 0xff. The mask
271 reflects that the bits in lsb are unknown.
272 The actual propagated value is given by m_value & ~m_mask. */
273
274 class ipcp_bits_lattice
275 {
276 public:
bottom_p()277 bool bottom_p () { return m_lattice_val == IPA_BITS_VARYING; }
top_p()278 bool top_p () { return m_lattice_val == IPA_BITS_UNDEFINED; }
constant_p()279 bool constant_p () { return m_lattice_val == IPA_BITS_CONSTANT; }
280 bool set_to_bottom ();
281 bool set_to_constant (widest_int, widest_int);
282
get_value()283 widest_int get_value () { return m_value; }
get_mask()284 widest_int get_mask () { return m_mask; }
285
286 bool meet_with (ipcp_bits_lattice& other, unsigned, signop,
287 enum tree_code, tree);
288
289 bool meet_with (widest_int, widest_int, unsigned);
290
291 void print (FILE *);
292
293 private:
294 enum { IPA_BITS_UNDEFINED, IPA_BITS_CONSTANT, IPA_BITS_VARYING } m_lattice_val;
295
296 /* Similar to ccp_lattice_t, mask represents which bits of value are constant.
297 If a bit in mask is set to 0, then the corresponding bit in
298 value is known to be constant. */
299 widest_int m_value, m_mask;
300
301 bool meet_with_1 (widest_int, widest_int, unsigned);
302 void get_value_and_mask (tree, widest_int *, widest_int *);
303 };
304
305 /* Lattice of value ranges. */
306
307 class ipcp_vr_lattice
308 {
309 public:
310 value_range m_vr;
311
312 inline bool bottom_p () const;
313 inline bool top_p () const;
314 inline bool set_to_bottom ();
315 bool meet_with (const value_range *p_vr);
316 bool meet_with (const ipcp_vr_lattice &other);
init()317 void init () { m_vr.type = VR_UNDEFINED; }
318 void print (FILE * f);
319
320 private:
321 bool meet_with_1 (const value_range *other_vr);
322 };
323
324 /* Structure containing lattices for a parameter itself and for pieces of
325 aggregates that are passed in the parameter or by a reference in a parameter
326 plus some other useful flags. */
327
328 class ipcp_param_lattices
329 {
330 public:
331 /* Lattice describing the value of the parameter itself. */
332 ipcp_lattice<tree> itself;
333 /* Lattice describing the polymorphic contexts of a parameter. */
334 ipcp_lattice<ipa_polymorphic_call_context> ctxlat;
335 /* Lattices describing aggregate parts. */
336 ipcp_agg_lattice *aggs;
337 /* Lattice describing known bits. */
338 ipcp_bits_lattice bits_lattice;
339 /* Lattice describing value range. */
340 ipcp_vr_lattice m_value_range;
341 /* Number of aggregate lattices */
342 int aggs_count;
343 /* True if aggregate data were passed by reference (as opposed to by
344 value). */
345 bool aggs_by_ref;
346 /* All aggregate lattices contain a variable component (in addition to
347 values). */
348 bool aggs_contain_variable;
349 /* The value of all aggregate lattices is bottom (i.e. variable and unusable
350 for any propagation). */
351 bool aggs_bottom;
352
353 /* There is a virtual call based on this parameter. */
354 bool virt_call;
355 };
356
357 /* Allocation pools for values and their sources in ipa-cp. */
358
359 object_allocator<ipcp_value<tree> > ipcp_cst_values_pool
360 ("IPA-CP constant values");
361
362 object_allocator<ipcp_value<ipa_polymorphic_call_context> >
363 ipcp_poly_ctx_values_pool ("IPA-CP polymorphic contexts");
364
365 object_allocator<ipcp_value_source<tree> > ipcp_sources_pool
366 ("IPA-CP value sources");
367
368 object_allocator<ipcp_agg_lattice> ipcp_agg_lattice_pool
369 ("IPA_CP aggregate lattices");
370
371 /* Maximal count found in program. */
372
373 static profile_count max_count;
374
375 /* Original overall size of the program. */
376
377 static long overall_size, max_new_size;
378
379 /* Return the param lattices structure corresponding to the Ith formal
380 parameter of the function described by INFO. */
381 static inline struct ipcp_param_lattices *
ipa_get_parm_lattices(struct ipa_node_params * info,int i)382 ipa_get_parm_lattices (struct ipa_node_params *info, int i)
383 {
384 gcc_assert (i >= 0 && i < ipa_get_param_count (info));
385 gcc_checking_assert (!info->ipcp_orig_node);
386 gcc_checking_assert (info->lattices);
387 return &(info->lattices[i]);
388 }
389
390 /* Return the lattice corresponding to the scalar value of the Ith formal
391 parameter of the function described by INFO. */
392 static inline ipcp_lattice<tree> *
ipa_get_scalar_lat(struct ipa_node_params * info,int i)393 ipa_get_scalar_lat (struct ipa_node_params *info, int i)
394 {
395 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
396 return &plats->itself;
397 }
398
399 /* Return the lattice corresponding to the scalar value of the Ith formal
400 parameter of the function described by INFO. */
401 static inline ipcp_lattice<ipa_polymorphic_call_context> *
ipa_get_poly_ctx_lat(struct ipa_node_params * info,int i)402 ipa_get_poly_ctx_lat (struct ipa_node_params *info, int i)
403 {
404 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
405 return &plats->ctxlat;
406 }
407
408 /* Return the lattice corresponding to the value range of the Ith formal
409 parameter of the function described by INFO. */
410
411 static inline ipcp_vr_lattice *
ipa_get_vr_lat(struct ipa_node_params * info,int i)412 ipa_get_vr_lat (struct ipa_node_params *info, int i)
413 {
414 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
415 return &plats->m_value_range;
416 }
417
418 /* Return whether LAT is a lattice with a single constant and without an
419 undefined value. */
420
421 template <typename valtype>
422 inline bool
is_single_const()423 ipcp_lattice<valtype>::is_single_const ()
424 {
425 if (bottom || contains_variable || values_count != 1)
426 return false;
427 else
428 return true;
429 }
430
431 /* Print V which is extracted from a value in a lattice to F. */
432
433 static void
print_ipcp_constant_value(FILE * f,tree v)434 print_ipcp_constant_value (FILE * f, tree v)
435 {
436 if (TREE_CODE (v) == ADDR_EXPR
437 && TREE_CODE (TREE_OPERAND (v, 0)) == CONST_DECL)
438 {
439 fprintf (f, "& ");
440 print_generic_expr (f, DECL_INITIAL (TREE_OPERAND (v, 0)));
441 }
442 else
443 print_generic_expr (f, v);
444 }
445
446 /* Print V which is extracted from a value in a lattice to F. */
447
448 static void
print_ipcp_constant_value(FILE * f,ipa_polymorphic_call_context v)449 print_ipcp_constant_value (FILE * f, ipa_polymorphic_call_context v)
450 {
451 v.dump(f, false);
452 }
453
454 /* Print a lattice LAT to F. */
455
456 template <typename valtype>
457 void
print(FILE * f,bool dump_sources,bool dump_benefits)458 ipcp_lattice<valtype>::print (FILE * f, bool dump_sources, bool dump_benefits)
459 {
460 ipcp_value<valtype> *val;
461 bool prev = false;
462
463 if (bottom)
464 {
465 fprintf (f, "BOTTOM\n");
466 return;
467 }
468
469 if (!values_count && !contains_variable)
470 {
471 fprintf (f, "TOP\n");
472 return;
473 }
474
475 if (contains_variable)
476 {
477 fprintf (f, "VARIABLE");
478 prev = true;
479 if (dump_benefits)
480 fprintf (f, "\n");
481 }
482
483 for (val = values; val; val = val->next)
484 {
485 if (dump_benefits && prev)
486 fprintf (f, " ");
487 else if (!dump_benefits && prev)
488 fprintf (f, ", ");
489 else
490 prev = true;
491
492 print_ipcp_constant_value (f, val->value);
493
494 if (dump_sources)
495 {
496 ipcp_value_source<valtype> *s;
497
498 fprintf (f, " [from:");
499 for (s = val->sources; s; s = s->next)
500 fprintf (f, " %i(%f)", s->cs->caller->order,
501 s->cs->sreal_frequency ().to_double ());
502 fprintf (f, "]");
503 }
504
505 if (dump_benefits)
506 fprintf (f, " [loc_time: %i, loc_size: %i, "
507 "prop_time: %i, prop_size: %i]\n",
508 val->local_time_benefit, val->local_size_cost,
509 val->prop_time_benefit, val->prop_size_cost);
510 }
511 if (!dump_benefits)
512 fprintf (f, "\n");
513 }
514
515 void
print(FILE * f)516 ipcp_bits_lattice::print (FILE *f)
517 {
518 if (top_p ())
519 fprintf (f, " Bits unknown (TOP)\n");
520 else if (bottom_p ())
521 fprintf (f, " Bits unusable (BOTTOM)\n");
522 else
523 {
524 fprintf (f, " Bits: value = "); print_hex (get_value (), f);
525 fprintf (f, ", mask = "); print_hex (get_mask (), f);
526 fprintf (f, "\n");
527 }
528 }
529
530 /* Print value range lattice to F. */
531
532 void
print(FILE * f)533 ipcp_vr_lattice::print (FILE * f)
534 {
535 dump_value_range (f, &m_vr);
536 }
537
538 /* Print all ipcp_lattices of all functions to F. */
539
540 static void
print_all_lattices(FILE * f,bool dump_sources,bool dump_benefits)541 print_all_lattices (FILE * f, bool dump_sources, bool dump_benefits)
542 {
543 struct cgraph_node *node;
544 int i, count;
545
546 fprintf (f, "\nLattices:\n");
547 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
548 {
549 struct ipa_node_params *info;
550
551 info = IPA_NODE_REF (node);
552 fprintf (f, " Node: %s:\n", node->dump_name ());
553 count = ipa_get_param_count (info);
554 for (i = 0; i < count; i++)
555 {
556 struct ipcp_agg_lattice *aglat;
557 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
558 fprintf (f, " param [%d]: ", i);
559 plats->itself.print (f, dump_sources, dump_benefits);
560 fprintf (f, " ctxs: ");
561 plats->ctxlat.print (f, dump_sources, dump_benefits);
562 plats->bits_lattice.print (f);
563 fprintf (f, " ");
564 plats->m_value_range.print (f);
565 fprintf (f, "\n");
566 if (plats->virt_call)
567 fprintf (f, " virt_call flag set\n");
568
569 if (plats->aggs_bottom)
570 {
571 fprintf (f, " AGGS BOTTOM\n");
572 continue;
573 }
574 if (plats->aggs_contain_variable)
575 fprintf (f, " AGGS VARIABLE\n");
576 for (aglat = plats->aggs; aglat; aglat = aglat->next)
577 {
578 fprintf (f, " %soffset " HOST_WIDE_INT_PRINT_DEC ": ",
579 plats->aggs_by_ref ? "ref " : "", aglat->offset);
580 aglat->print (f, dump_sources, dump_benefits);
581 }
582 }
583 }
584 }
585
586 /* Determine whether it is at all technically possible to create clones of NODE
587 and store this information in the ipa_node_params structure associated
588 with NODE. */
589
590 static void
determine_versionability(struct cgraph_node * node,struct ipa_node_params * info)591 determine_versionability (struct cgraph_node *node,
592 struct ipa_node_params *info)
593 {
594 const char *reason = NULL;
595
596 /* There are a number of generic reasons functions cannot be versioned. We
597 also cannot remove parameters if there are type attributes such as fnspec
598 present. */
599 if (node->alias || node->thunk.thunk_p)
600 reason = "alias or thunk";
601 else if (!node->local.versionable)
602 reason = "not a tree_versionable_function";
603 else if (node->get_availability () <= AVAIL_INTERPOSABLE)
604 reason = "insufficient body availability";
605 else if (!opt_for_fn (node->decl, optimize)
606 || !opt_for_fn (node->decl, flag_ipa_cp))
607 reason = "non-optimized function";
608 else if (lookup_attribute ("omp declare simd", DECL_ATTRIBUTES (node->decl)))
609 {
610 /* Ideally we should clone the SIMD clones themselves and create
611 vector copies of them, so IPA-cp and SIMD clones can happily
612 coexist, but that may not be worth the effort. */
613 reason = "function has SIMD clones";
614 }
615 else if (lookup_attribute ("target_clones", DECL_ATTRIBUTES (node->decl)))
616 {
617 /* Ideally we should clone the target clones themselves and create
618 copies of them, so IPA-cp and target clones can happily
619 coexist, but that may not be worth the effort. */
620 reason = "function target_clones attribute";
621 }
622 /* Don't clone decls local to a comdat group; it breaks and for C++
623 decloned constructors, inlining is always better anyway. */
624 else if (node->comdat_local_p ())
625 reason = "comdat-local function";
626 else if (node->calls_comdat_local)
627 {
628 /* TODO: call is versionable if we make sure that all
629 callers are inside of a comdat group. */
630 reason = "calls comdat-local function";
631 }
632
633 /* Functions calling BUILT_IN_VA_ARG_PACK and BUILT_IN_VA_ARG_PACK_LEN
634 work only when inlined. Cloning them may still lead to better code
635 because ipa-cp will not give up on cloning further. If the function is
636 external this however leads to wrong code because we may end up producing
637 offline copy of the function. */
638 if (DECL_EXTERNAL (node->decl))
639 for (cgraph_edge *edge = node->callees; !reason && edge;
640 edge = edge->next_callee)
641 if (DECL_BUILT_IN (edge->callee->decl)
642 && DECL_BUILT_IN_CLASS (edge->callee->decl) == BUILT_IN_NORMAL)
643 {
644 if (DECL_FUNCTION_CODE (edge->callee->decl) == BUILT_IN_VA_ARG_PACK)
645 reason = "external function which calls va_arg_pack";
646 if (DECL_FUNCTION_CODE (edge->callee->decl)
647 == BUILT_IN_VA_ARG_PACK_LEN)
648 reason = "external function which calls va_arg_pack_len";
649 }
650
651 if (reason && dump_file && !node->alias && !node->thunk.thunk_p)
652 fprintf (dump_file, "Function %s is not versionable, reason: %s.\n",
653 node->dump_name (), reason);
654
655 info->versionable = (reason == NULL);
656 }
657
658 /* Return true if it is at all technically possible to create clones of a
659 NODE. */
660
661 static bool
ipcp_versionable_function_p(struct cgraph_node * node)662 ipcp_versionable_function_p (struct cgraph_node *node)
663 {
664 return IPA_NODE_REF (node)->versionable;
665 }
666
667 /* Structure holding accumulated information about callers of a node. */
668
669 struct caller_statistics
670 {
671 profile_count count_sum;
672 int n_calls, n_hot_calls, freq_sum;
673 };
674
675 /* Initialize fields of STAT to zeroes. */
676
677 static inline void
init_caller_stats(struct caller_statistics * stats)678 init_caller_stats (struct caller_statistics *stats)
679 {
680 stats->count_sum = profile_count::zero ();
681 stats->n_calls = 0;
682 stats->n_hot_calls = 0;
683 stats->freq_sum = 0;
684 }
685
686 /* Worker callback of cgraph_for_node_and_aliases accumulating statistics of
687 non-thunk incoming edges to NODE. */
688
689 static bool
gather_caller_stats(struct cgraph_node * node,void * data)690 gather_caller_stats (struct cgraph_node *node, void *data)
691 {
692 struct caller_statistics *stats = (struct caller_statistics *) data;
693 struct cgraph_edge *cs;
694
695 for (cs = node->callers; cs; cs = cs->next_caller)
696 if (!cs->caller->thunk.thunk_p)
697 {
698 if (cs->count.ipa ().initialized_p ())
699 stats->count_sum += cs->count.ipa ();
700 stats->freq_sum += cs->frequency ();
701 stats->n_calls++;
702 if (cs->maybe_hot_p ())
703 stats->n_hot_calls ++;
704 }
705 return false;
706
707 }
708
709 /* Return true if this NODE is viable candidate for cloning. */
710
711 static bool
ipcp_cloning_candidate_p(struct cgraph_node * node)712 ipcp_cloning_candidate_p (struct cgraph_node *node)
713 {
714 struct caller_statistics stats;
715
716 gcc_checking_assert (node->has_gimple_body_p ());
717
718 if (!opt_for_fn (node->decl, flag_ipa_cp_clone))
719 {
720 if (dump_file)
721 fprintf (dump_file, "Not considering %s for cloning; "
722 "-fipa-cp-clone disabled.\n",
723 node->name ());
724 return false;
725 }
726
727 if (node->optimize_for_size_p ())
728 {
729 if (dump_file)
730 fprintf (dump_file, "Not considering %s for cloning; "
731 "optimizing it for size.\n",
732 node->name ());
733 return false;
734 }
735
736 init_caller_stats (&stats);
737 node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats, false);
738
739 if (ipa_fn_summaries->get (node)->self_size < stats.n_calls)
740 {
741 if (dump_file)
742 fprintf (dump_file, "Considering %s for cloning; code might shrink.\n",
743 node->name ());
744 return true;
745 }
746
747 /* When profile is available and function is hot, propagate into it even if
748 calls seems cold; constant propagation can improve function's speed
749 significantly. */
750 if (max_count > profile_count::zero ())
751 {
752 if (stats.count_sum > node->count.ipa ().apply_scale (90, 100))
753 {
754 if (dump_file)
755 fprintf (dump_file, "Considering %s for cloning; "
756 "usually called directly.\n",
757 node->name ());
758 return true;
759 }
760 }
761 if (!stats.n_hot_calls)
762 {
763 if (dump_file)
764 fprintf (dump_file, "Not considering %s for cloning; no hot calls.\n",
765 node->name ());
766 return false;
767 }
768 if (dump_file)
769 fprintf (dump_file, "Considering %s for cloning.\n",
770 node->name ());
771 return true;
772 }
773
774 template <typename valtype>
775 class value_topo_info
776 {
777 public:
778 /* Head of the linked list of topologically sorted values. */
779 ipcp_value<valtype> *values_topo;
780 /* Stack for creating SCCs, represented by a linked list too. */
781 ipcp_value<valtype> *stack;
782 /* Counter driving the algorithm in add_val_to_toposort. */
783 int dfs_counter;
784
value_topo_info()785 value_topo_info () : values_topo (NULL), stack (NULL), dfs_counter (0)
786 {}
787 void add_val (ipcp_value<valtype> *cur_val);
788 void propagate_effects ();
789 };
790
791 /* Arrays representing a topological ordering of call graph nodes and a stack
792 of nodes used during constant propagation and also data required to perform
793 topological sort of values and propagation of benefits in the determined
794 order. */
795
796 class ipa_topo_info
797 {
798 public:
799 /* Array with obtained topological order of cgraph nodes. */
800 struct cgraph_node **order;
801 /* Stack of cgraph nodes used during propagation within SCC until all values
802 in the SCC stabilize. */
803 struct cgraph_node **stack;
804 int nnodes, stack_top;
805
806 value_topo_info<tree> constants;
807 value_topo_info<ipa_polymorphic_call_context> contexts;
808
ipa_topo_info()809 ipa_topo_info () : order(NULL), stack(NULL), nnodes(0), stack_top(0),
810 constants ()
811 {}
812 };
813
814 /* Allocate the arrays in TOPO and topologically sort the nodes into order. */
815
816 static void
build_toporder_info(struct ipa_topo_info * topo)817 build_toporder_info (struct ipa_topo_info *topo)
818 {
819 topo->order = XCNEWVEC (struct cgraph_node *, symtab->cgraph_count);
820 topo->stack = XCNEWVEC (struct cgraph_node *, symtab->cgraph_count);
821
822 gcc_checking_assert (topo->stack_top == 0);
823 topo->nnodes = ipa_reduced_postorder (topo->order, true, NULL);
824 }
825
826 /* Free information about strongly connected components and the arrays in
827 TOPO. */
828
829 static void
free_toporder_info(struct ipa_topo_info * topo)830 free_toporder_info (struct ipa_topo_info *topo)
831 {
832 ipa_free_postorder_info ();
833 free (topo->order);
834 free (topo->stack);
835 }
836
837 /* Add NODE to the stack in TOPO, unless it is already there. */
838
839 static inline void
push_node_to_stack(struct ipa_topo_info * topo,struct cgraph_node * node)840 push_node_to_stack (struct ipa_topo_info *topo, struct cgraph_node *node)
841 {
842 struct ipa_node_params *info = IPA_NODE_REF (node);
843 if (info->node_enqueued)
844 return;
845 info->node_enqueued = 1;
846 topo->stack[topo->stack_top++] = node;
847 }
848
849 /* Pop a node from the stack in TOPO and return it or return NULL if the stack
850 is empty. */
851
852 static struct cgraph_node *
pop_node_from_stack(struct ipa_topo_info * topo)853 pop_node_from_stack (struct ipa_topo_info *topo)
854 {
855 if (topo->stack_top)
856 {
857 struct cgraph_node *node;
858 topo->stack_top--;
859 node = topo->stack[topo->stack_top];
860 IPA_NODE_REF (node)->node_enqueued = 0;
861 return node;
862 }
863 else
864 return NULL;
865 }
866
867 /* Set lattice LAT to bottom and return true if it previously was not set as
868 such. */
869
870 template <typename valtype>
871 inline bool
set_to_bottom()872 ipcp_lattice<valtype>::set_to_bottom ()
873 {
874 bool ret = !bottom;
875 bottom = true;
876 return ret;
877 }
878
879 /* Mark lattice as containing an unknown value and return true if it previously
880 was not marked as such. */
881
882 template <typename valtype>
883 inline bool
set_contains_variable()884 ipcp_lattice<valtype>::set_contains_variable ()
885 {
886 bool ret = !contains_variable;
887 contains_variable = true;
888 return ret;
889 }
890
891 /* Set all aggegate lattices in PLATS to bottom and return true if they were
892 not previously set as such. */
893
894 static inline bool
set_agg_lats_to_bottom(struct ipcp_param_lattices * plats)895 set_agg_lats_to_bottom (struct ipcp_param_lattices *plats)
896 {
897 bool ret = !plats->aggs_bottom;
898 plats->aggs_bottom = true;
899 return ret;
900 }
901
902 /* Mark all aggegate lattices in PLATS as containing an unknown value and
903 return true if they were not previously marked as such. */
904
905 static inline bool
set_agg_lats_contain_variable(struct ipcp_param_lattices * plats)906 set_agg_lats_contain_variable (struct ipcp_param_lattices *plats)
907 {
908 bool ret = !plats->aggs_contain_variable;
909 plats->aggs_contain_variable = true;
910 return ret;
911 }
912
913 bool
meet_with(const ipcp_vr_lattice & other)914 ipcp_vr_lattice::meet_with (const ipcp_vr_lattice &other)
915 {
916 return meet_with_1 (&other.m_vr);
917 }
918
919 /* Meet the current value of the lattice with value ranfge described by VR
920 lattice. */
921
922 bool
meet_with(const value_range * p_vr)923 ipcp_vr_lattice::meet_with (const value_range *p_vr)
924 {
925 return meet_with_1 (p_vr);
926 }
927
928 /* Meet the current value of the lattice with value ranfge described by
929 OTHER_VR lattice. */
930
931 bool
meet_with_1(const value_range * other_vr)932 ipcp_vr_lattice::meet_with_1 (const value_range *other_vr)
933 {
934 tree min = m_vr.min, max = m_vr.max;
935 value_range_type type = m_vr.type;
936
937 if (bottom_p ())
938 return false;
939
940 if (other_vr->type == VR_VARYING)
941 return set_to_bottom ();
942
943 vrp_meet (&m_vr, other_vr);
944 if (type != m_vr.type
945 || min != m_vr.min
946 || max != m_vr.max)
947 return true;
948 else
949 return false;
950 }
951
952 /* Return true if value range information in the lattice is yet unknown. */
953
954 bool
top_p()955 ipcp_vr_lattice::top_p () const
956 {
957 return m_vr.type == VR_UNDEFINED;
958 }
959
960 /* Return true if value range information in the lattice is known to be
961 unusable. */
962
963 bool
bottom_p()964 ipcp_vr_lattice::bottom_p () const
965 {
966 return m_vr.type == VR_VARYING;
967 }
968
969 /* Set value range information in the lattice to bottom. Return true if it
970 previously was in a different state. */
971
972 bool
set_to_bottom()973 ipcp_vr_lattice::set_to_bottom ()
974 {
975 if (m_vr.type == VR_VARYING)
976 return false;
977 m_vr.type = VR_VARYING;
978 return true;
979 }
980
981 /* Set lattice value to bottom, if it already isn't the case. */
982
983 bool
set_to_bottom()984 ipcp_bits_lattice::set_to_bottom ()
985 {
986 if (bottom_p ())
987 return false;
988 m_lattice_val = IPA_BITS_VARYING;
989 m_value = 0;
990 m_mask = -1;
991 return true;
992 }
993
994 /* Set to constant if it isn't already. Only meant to be called
995 when switching state from TOP. */
996
997 bool
set_to_constant(widest_int value,widest_int mask)998 ipcp_bits_lattice::set_to_constant (widest_int value, widest_int mask)
999 {
1000 gcc_assert (top_p ());
1001 m_lattice_val = IPA_BITS_CONSTANT;
1002 m_value = value;
1003 m_mask = mask;
1004 return true;
1005 }
1006
1007 /* Convert operand to value, mask form. */
1008
1009 void
get_value_and_mask(tree operand,widest_int * valuep,widest_int * maskp)1010 ipcp_bits_lattice::get_value_and_mask (tree operand, widest_int *valuep, widest_int *maskp)
1011 {
1012 wide_int get_nonzero_bits (const_tree);
1013
1014 if (TREE_CODE (operand) == INTEGER_CST)
1015 {
1016 *valuep = wi::to_widest (operand);
1017 *maskp = 0;
1018 }
1019 else
1020 {
1021 *valuep = 0;
1022 *maskp = -1;
1023 }
1024 }
1025
1026 /* Meet operation, similar to ccp_lattice_meet, we xor values
1027 if this->value, value have different values at same bit positions, we want
1028 to drop that bit to varying. Return true if mask is changed.
1029 This function assumes that the lattice value is in CONSTANT state */
1030
1031 bool
meet_with_1(widest_int value,widest_int mask,unsigned precision)1032 ipcp_bits_lattice::meet_with_1 (widest_int value, widest_int mask,
1033 unsigned precision)
1034 {
1035 gcc_assert (constant_p ());
1036
1037 widest_int old_mask = m_mask;
1038 m_mask = (m_mask | mask) | (m_value ^ value);
1039
1040 if (wi::sext (m_mask, precision) == -1)
1041 return set_to_bottom ();
1042
1043 return m_mask != old_mask;
1044 }
1045
1046 /* Meet the bits lattice with operand
1047 described by <value, mask, sgn, precision. */
1048
1049 bool
meet_with(widest_int value,widest_int mask,unsigned precision)1050 ipcp_bits_lattice::meet_with (widest_int value, widest_int mask,
1051 unsigned precision)
1052 {
1053 if (bottom_p ())
1054 return false;
1055
1056 if (top_p ())
1057 {
1058 if (wi::sext (mask, precision) == -1)
1059 return set_to_bottom ();
1060 return set_to_constant (value, mask);
1061 }
1062
1063 return meet_with_1 (value, mask, precision);
1064 }
1065
1066 /* Meet bits lattice with the result of bit_value_binop (other, operand)
1067 if code is binary operation or bit_value_unop (other) if code is unary op.
1068 In the case when code is nop_expr, no adjustment is required. */
1069
1070 bool
meet_with(ipcp_bits_lattice & other,unsigned precision,signop sgn,enum tree_code code,tree operand)1071 ipcp_bits_lattice::meet_with (ipcp_bits_lattice& other, unsigned precision,
1072 signop sgn, enum tree_code code, tree operand)
1073 {
1074 if (other.bottom_p ())
1075 return set_to_bottom ();
1076
1077 if (bottom_p () || other.top_p ())
1078 return false;
1079
1080 widest_int adjusted_value, adjusted_mask;
1081
1082 if (TREE_CODE_CLASS (code) == tcc_binary)
1083 {
1084 tree type = TREE_TYPE (operand);
1085 gcc_assert (INTEGRAL_TYPE_P (type));
1086 widest_int o_value, o_mask;
1087 get_value_and_mask (operand, &o_value, &o_mask);
1088
1089 bit_value_binop (code, sgn, precision, &adjusted_value, &adjusted_mask,
1090 sgn, precision, other.get_value (), other.get_mask (),
1091 TYPE_SIGN (type), TYPE_PRECISION (type), o_value, o_mask);
1092
1093 if (wi::sext (adjusted_mask, precision) == -1)
1094 return set_to_bottom ();
1095 }
1096
1097 else if (TREE_CODE_CLASS (code) == tcc_unary)
1098 {
1099 bit_value_unop (code, sgn, precision, &adjusted_value,
1100 &adjusted_mask, sgn, precision, other.get_value (),
1101 other.get_mask ());
1102
1103 if (wi::sext (adjusted_mask, precision) == -1)
1104 return set_to_bottom ();
1105 }
1106
1107 else
1108 return set_to_bottom ();
1109
1110 if (top_p ())
1111 {
1112 if (wi::sext (adjusted_mask, precision) == -1)
1113 return set_to_bottom ();
1114 return set_to_constant (adjusted_value, adjusted_mask);
1115 }
1116 else
1117 return meet_with_1 (adjusted_value, adjusted_mask, precision);
1118 }
1119
1120 /* Mark bot aggregate and scalar lattices as containing an unknown variable,
1121 return true is any of them has not been marked as such so far. */
1122
1123 static inline bool
set_all_contains_variable(struct ipcp_param_lattices * plats)1124 set_all_contains_variable (struct ipcp_param_lattices *plats)
1125 {
1126 bool ret;
1127 ret = plats->itself.set_contains_variable ();
1128 ret |= plats->ctxlat.set_contains_variable ();
1129 ret |= set_agg_lats_contain_variable (plats);
1130 ret |= plats->bits_lattice.set_to_bottom ();
1131 ret |= plats->m_value_range.set_to_bottom ();
1132 return ret;
1133 }
1134
1135 /* Worker of call_for_symbol_thunks_and_aliases, increment the integer DATA
1136 points to by the number of callers to NODE. */
1137
1138 static bool
count_callers(cgraph_node * node,void * data)1139 count_callers (cgraph_node *node, void *data)
1140 {
1141 int *caller_count = (int *) data;
1142
1143 for (cgraph_edge *cs = node->callers; cs; cs = cs->next_caller)
1144 /* Local thunks can be handled transparently, but if the thunk can not
1145 be optimized out, count it as a real use. */
1146 if (!cs->caller->thunk.thunk_p || !cs->caller->local.local)
1147 ++*caller_count;
1148 return false;
1149 }
1150
1151 /* Worker of call_for_symbol_thunks_and_aliases, it is supposed to be called on
1152 the one caller of some other node. Set the caller's corresponding flag. */
1153
1154 static bool
set_single_call_flag(cgraph_node * node,void *)1155 set_single_call_flag (cgraph_node *node, void *)
1156 {
1157 cgraph_edge *cs = node->callers;
1158 /* Local thunks can be handled transparently, skip them. */
1159 while (cs && cs->caller->thunk.thunk_p && cs->caller->local.local)
1160 cs = cs->next_caller;
1161 if (cs)
1162 {
1163 IPA_NODE_REF (cs->caller)->node_calling_single_call = true;
1164 return true;
1165 }
1166 return false;
1167 }
1168
1169 /* Initialize ipcp_lattices. */
1170
1171 static void
initialize_node_lattices(struct cgraph_node * node)1172 initialize_node_lattices (struct cgraph_node *node)
1173 {
1174 struct ipa_node_params *info = IPA_NODE_REF (node);
1175 struct cgraph_edge *ie;
1176 bool disable = false, variable = false;
1177 int i;
1178
1179 gcc_checking_assert (node->has_gimple_body_p ());
1180 if (cgraph_local_p (node))
1181 {
1182 int caller_count = 0;
1183 node->call_for_symbol_thunks_and_aliases (count_callers, &caller_count,
1184 true);
1185 gcc_checking_assert (caller_count > 0);
1186 if (caller_count == 1)
1187 node->call_for_symbol_thunks_and_aliases (set_single_call_flag,
1188 NULL, true);
1189 }
1190 else
1191 {
1192 /* When cloning is allowed, we can assume that externally visible
1193 functions are not called. We will compensate this by cloning
1194 later. */
1195 if (ipcp_versionable_function_p (node)
1196 && ipcp_cloning_candidate_p (node))
1197 variable = true;
1198 else
1199 disable = true;
1200 }
1201
1202 for (i = 0; i < ipa_get_param_count (info); i++)
1203 {
1204 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
1205 plats->m_value_range.init ();
1206 }
1207
1208 if (disable || variable)
1209 {
1210 for (i = 0; i < ipa_get_param_count (info); i++)
1211 {
1212 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
1213 if (disable)
1214 {
1215 plats->itself.set_to_bottom ();
1216 plats->ctxlat.set_to_bottom ();
1217 set_agg_lats_to_bottom (plats);
1218 plats->bits_lattice.set_to_bottom ();
1219 plats->m_value_range.set_to_bottom ();
1220 }
1221 else
1222 set_all_contains_variable (plats);
1223 }
1224 if (dump_file && (dump_flags & TDF_DETAILS)
1225 && !node->alias && !node->thunk.thunk_p)
1226 fprintf (dump_file, "Marking all lattices of %s as %s\n",
1227 node->dump_name (), disable ? "BOTTOM" : "VARIABLE");
1228 }
1229
1230 for (ie = node->indirect_calls; ie; ie = ie->next_callee)
1231 if (ie->indirect_info->polymorphic
1232 && ie->indirect_info->param_index >= 0)
1233 {
1234 gcc_checking_assert (ie->indirect_info->param_index >= 0);
1235 ipa_get_parm_lattices (info,
1236 ie->indirect_info->param_index)->virt_call = 1;
1237 }
1238 }
1239
1240 /* Return the result of a (possibly arithmetic) pass through jump function
1241 JFUNC on the constant value INPUT. RES_TYPE is the type of the parameter
1242 to which the result is passed. Return NULL_TREE if that cannot be
1243 determined or be considered an interprocedural invariant. */
1244
1245 static tree
ipa_get_jf_pass_through_result(struct ipa_jump_func * jfunc,tree input,tree res_type)1246 ipa_get_jf_pass_through_result (struct ipa_jump_func *jfunc, tree input,
1247 tree res_type)
1248 {
1249 tree res;
1250
1251 if (ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
1252 return input;
1253 if (!is_gimple_ip_invariant (input))
1254 return NULL_TREE;
1255
1256 tree_code opcode = ipa_get_jf_pass_through_operation (jfunc);
1257 if (!res_type)
1258 {
1259 if (TREE_CODE_CLASS (opcode) == tcc_comparison)
1260 res_type = boolean_type_node;
1261 else if (expr_type_first_operand_type_p (opcode))
1262 res_type = TREE_TYPE (input);
1263 else
1264 return NULL_TREE;
1265 }
1266
1267 if (TREE_CODE_CLASS (opcode) == tcc_unary)
1268 res = fold_unary (opcode, res_type, input);
1269 else
1270 res = fold_binary (opcode, res_type, input,
1271 ipa_get_jf_pass_through_operand (jfunc));
1272
1273 if (res && !is_gimple_ip_invariant (res))
1274 return NULL_TREE;
1275
1276 return res;
1277 }
1278
1279 /* Return the result of an ancestor jump function JFUNC on the constant value
1280 INPUT. Return NULL_TREE if that cannot be determined. */
1281
1282 static tree
ipa_get_jf_ancestor_result(struct ipa_jump_func * jfunc,tree input)1283 ipa_get_jf_ancestor_result (struct ipa_jump_func *jfunc, tree input)
1284 {
1285 gcc_checking_assert (TREE_CODE (input) != TREE_BINFO);
1286 if (TREE_CODE (input) == ADDR_EXPR)
1287 {
1288 tree t = TREE_OPERAND (input, 0);
1289 t = build_ref_for_offset (EXPR_LOCATION (t), t,
1290 ipa_get_jf_ancestor_offset (jfunc), false,
1291 ptr_type_node, NULL, false);
1292 return build_fold_addr_expr (t);
1293 }
1294 else
1295 return NULL_TREE;
1296 }
1297
1298 /* Determine whether JFUNC evaluates to a single known constant value and if
1299 so, return it. Otherwise return NULL. INFO describes the caller node or
1300 the one it is inlined to, so that pass-through jump functions can be
1301 evaluated. PARM_TYPE is the type of the parameter to which the result is
1302 passed. */
1303
1304 tree
ipa_value_from_jfunc(struct ipa_node_params * info,struct ipa_jump_func * jfunc,tree parm_type)1305 ipa_value_from_jfunc (struct ipa_node_params *info, struct ipa_jump_func *jfunc,
1306 tree parm_type)
1307 {
1308 if (jfunc->type == IPA_JF_CONST)
1309 return ipa_get_jf_constant (jfunc);
1310 else if (jfunc->type == IPA_JF_PASS_THROUGH
1311 || jfunc->type == IPA_JF_ANCESTOR)
1312 {
1313 tree input;
1314 int idx;
1315
1316 if (jfunc->type == IPA_JF_PASS_THROUGH)
1317 idx = ipa_get_jf_pass_through_formal_id (jfunc);
1318 else
1319 idx = ipa_get_jf_ancestor_formal_id (jfunc);
1320
1321 if (info->ipcp_orig_node)
1322 input = info->known_csts[idx];
1323 else
1324 {
1325 ipcp_lattice<tree> *lat;
1326
1327 if (!info->lattices
1328 || idx >= ipa_get_param_count (info))
1329 return NULL_TREE;
1330 lat = ipa_get_scalar_lat (info, idx);
1331 if (!lat->is_single_const ())
1332 return NULL_TREE;
1333 input = lat->values->value;
1334 }
1335
1336 if (!input)
1337 return NULL_TREE;
1338
1339 if (jfunc->type == IPA_JF_PASS_THROUGH)
1340 return ipa_get_jf_pass_through_result (jfunc, input, parm_type);
1341 else
1342 return ipa_get_jf_ancestor_result (jfunc, input);
1343 }
1344 else
1345 return NULL_TREE;
1346 }
1347
1348 /* Determie whether JFUNC evaluates to single known polymorphic context, given
1349 that INFO describes the caller node or the one it is inlined to, CS is the
1350 call graph edge corresponding to JFUNC and CSIDX index of the described
1351 parameter. */
1352
1353 ipa_polymorphic_call_context
ipa_context_from_jfunc(ipa_node_params * info,cgraph_edge * cs,int csidx,ipa_jump_func * jfunc)1354 ipa_context_from_jfunc (ipa_node_params *info, cgraph_edge *cs, int csidx,
1355 ipa_jump_func *jfunc)
1356 {
1357 ipa_edge_args *args = IPA_EDGE_REF (cs);
1358 ipa_polymorphic_call_context ctx;
1359 ipa_polymorphic_call_context *edge_ctx
1360 = cs ? ipa_get_ith_polymorhic_call_context (args, csidx) : NULL;
1361
1362 if (edge_ctx && !edge_ctx->useless_p ())
1363 ctx = *edge_ctx;
1364
1365 if (jfunc->type == IPA_JF_PASS_THROUGH
1366 || jfunc->type == IPA_JF_ANCESTOR)
1367 {
1368 ipa_polymorphic_call_context srcctx;
1369 int srcidx;
1370 bool type_preserved = true;
1371 if (jfunc->type == IPA_JF_PASS_THROUGH)
1372 {
1373 if (ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR)
1374 return ctx;
1375 type_preserved = ipa_get_jf_pass_through_type_preserved (jfunc);
1376 srcidx = ipa_get_jf_pass_through_formal_id (jfunc);
1377 }
1378 else
1379 {
1380 type_preserved = ipa_get_jf_ancestor_type_preserved (jfunc);
1381 srcidx = ipa_get_jf_ancestor_formal_id (jfunc);
1382 }
1383 if (info->ipcp_orig_node)
1384 {
1385 if (info->known_contexts.exists ())
1386 srcctx = info->known_contexts[srcidx];
1387 }
1388 else
1389 {
1390 if (!info->lattices
1391 || srcidx >= ipa_get_param_count (info))
1392 return ctx;
1393 ipcp_lattice<ipa_polymorphic_call_context> *lat;
1394 lat = ipa_get_poly_ctx_lat (info, srcidx);
1395 if (!lat->is_single_const ())
1396 return ctx;
1397 srcctx = lat->values->value;
1398 }
1399 if (srcctx.useless_p ())
1400 return ctx;
1401 if (jfunc->type == IPA_JF_ANCESTOR)
1402 srcctx.offset_by (ipa_get_jf_ancestor_offset (jfunc));
1403 if (!type_preserved)
1404 srcctx.possible_dynamic_type_change (cs->in_polymorphic_cdtor);
1405 srcctx.combine_with (ctx);
1406 return srcctx;
1407 }
1408
1409 return ctx;
1410 }
1411
1412 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
1413 bottom, not containing a variable component and without any known value at
1414 the same time. */
1415
1416 DEBUG_FUNCTION void
ipcp_verify_propagated_values(void)1417 ipcp_verify_propagated_values (void)
1418 {
1419 struct cgraph_node *node;
1420
1421 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
1422 {
1423 struct ipa_node_params *info = IPA_NODE_REF (node);
1424 int i, count = ipa_get_param_count (info);
1425
1426 for (i = 0; i < count; i++)
1427 {
1428 ipcp_lattice<tree> *lat = ipa_get_scalar_lat (info, i);
1429
1430 if (!lat->bottom
1431 && !lat->contains_variable
1432 && lat->values_count == 0)
1433 {
1434 if (dump_file)
1435 {
1436 symtab->dump (dump_file);
1437 fprintf (dump_file, "\nIPA lattices after constant "
1438 "propagation, before gcc_unreachable:\n");
1439 print_all_lattices (dump_file, true, false);
1440 }
1441
1442 gcc_unreachable ();
1443 }
1444 }
1445 }
1446 }
1447
1448 /* Return true iff X and Y should be considered equal values by IPA-CP. */
1449
1450 static bool
values_equal_for_ipcp_p(tree x,tree y)1451 values_equal_for_ipcp_p (tree x, tree y)
1452 {
1453 gcc_checking_assert (x != NULL_TREE && y != NULL_TREE);
1454
1455 if (x == y)
1456 return true;
1457
1458 if (TREE_CODE (x) == ADDR_EXPR
1459 && TREE_CODE (y) == ADDR_EXPR
1460 && TREE_CODE (TREE_OPERAND (x, 0)) == CONST_DECL
1461 && TREE_CODE (TREE_OPERAND (y, 0)) == CONST_DECL)
1462 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x, 0)),
1463 DECL_INITIAL (TREE_OPERAND (y, 0)), 0);
1464 else
1465 return operand_equal_p (x, y, 0);
1466 }
1467
1468 /* Return true iff X and Y should be considered equal contexts by IPA-CP. */
1469
1470 static bool
values_equal_for_ipcp_p(ipa_polymorphic_call_context x,ipa_polymorphic_call_context y)1471 values_equal_for_ipcp_p (ipa_polymorphic_call_context x,
1472 ipa_polymorphic_call_context y)
1473 {
1474 return x.equal_to (y);
1475 }
1476
1477
1478 /* Add a new value source to the value represented by THIS, marking that a
1479 value comes from edge CS and (if the underlying jump function is a
1480 pass-through or an ancestor one) from a caller value SRC_VAL of a caller
1481 parameter described by SRC_INDEX. OFFSET is negative if the source was the
1482 scalar value of the parameter itself or the offset within an aggregate. */
1483
1484 template <typename valtype>
1485 void
add_source(cgraph_edge * cs,ipcp_value * src_val,int src_idx,HOST_WIDE_INT offset)1486 ipcp_value<valtype>::add_source (cgraph_edge *cs, ipcp_value *src_val,
1487 int src_idx, HOST_WIDE_INT offset)
1488 {
1489 ipcp_value_source<valtype> *src;
1490
1491 src = new (ipcp_sources_pool.allocate ()) ipcp_value_source<valtype>;
1492 src->offset = offset;
1493 src->cs = cs;
1494 src->val = src_val;
1495 src->index = src_idx;
1496
1497 src->next = sources;
1498 sources = src;
1499 }
1500
1501 /* Allocate a new ipcp_value holding a tree constant, initialize its value to
1502 SOURCE and clear all other fields. */
1503
1504 static ipcp_value<tree> *
allocate_and_init_ipcp_value(tree source)1505 allocate_and_init_ipcp_value (tree source)
1506 {
1507 ipcp_value<tree> *val;
1508
1509 val = new (ipcp_cst_values_pool.allocate ()) ipcp_value<tree>();
1510 val->value = source;
1511 return val;
1512 }
1513
1514 /* Allocate a new ipcp_value holding a polymorphic context, initialize its
1515 value to SOURCE and clear all other fields. */
1516
1517 static ipcp_value<ipa_polymorphic_call_context> *
allocate_and_init_ipcp_value(ipa_polymorphic_call_context source)1518 allocate_and_init_ipcp_value (ipa_polymorphic_call_context source)
1519 {
1520 ipcp_value<ipa_polymorphic_call_context> *val;
1521
1522 // TODO
1523 val = new (ipcp_poly_ctx_values_pool.allocate ())
1524 ipcp_value<ipa_polymorphic_call_context>();
1525 val->value = source;
1526 return val;
1527 }
1528
1529 /* Try to add NEWVAL to LAT, potentially creating a new ipcp_value for it. CS,
1530 SRC_VAL SRC_INDEX and OFFSET are meant for add_source and have the same
1531 meaning. OFFSET -1 means the source is scalar and not a part of an
1532 aggregate. */
1533
1534 template <typename valtype>
1535 bool
add_value(valtype newval,cgraph_edge * cs,ipcp_value<valtype> * src_val,int src_idx,HOST_WIDE_INT offset)1536 ipcp_lattice<valtype>::add_value (valtype newval, cgraph_edge *cs,
1537 ipcp_value<valtype> *src_val,
1538 int src_idx, HOST_WIDE_INT offset)
1539 {
1540 ipcp_value<valtype> *val;
1541
1542 if (bottom)
1543 return false;
1544
1545 for (val = values; val; val = val->next)
1546 if (values_equal_for_ipcp_p (val->value, newval))
1547 {
1548 if (ipa_edge_within_scc (cs))
1549 {
1550 ipcp_value_source<valtype> *s;
1551 for (s = val->sources; s; s = s->next)
1552 if (s->cs == cs)
1553 break;
1554 if (s)
1555 return false;
1556 }
1557
1558 val->add_source (cs, src_val, src_idx, offset);
1559 return false;
1560 }
1561
1562 if (values_count == PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE))
1563 {
1564 /* We can only free sources, not the values themselves, because sources
1565 of other values in this SCC might point to them. */
1566 for (val = values; val; val = val->next)
1567 {
1568 while (val->sources)
1569 {
1570 ipcp_value_source<valtype> *src = val->sources;
1571 val->sources = src->next;
1572 ipcp_sources_pool.remove ((ipcp_value_source<tree>*)src);
1573 }
1574 }
1575
1576 values = NULL;
1577 return set_to_bottom ();
1578 }
1579
1580 values_count++;
1581 val = allocate_and_init_ipcp_value (newval);
1582 val->add_source (cs, src_val, src_idx, offset);
1583 val->next = values;
1584 values = val;
1585 return true;
1586 }
1587
1588 /* Propagate values through a pass-through jump function JFUNC associated with
1589 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1590 is the index of the source parameter. PARM_TYPE is the type of the
1591 parameter to which the result is passed. */
1592
1593 static bool
propagate_vals_across_pass_through(cgraph_edge * cs,ipa_jump_func * jfunc,ipcp_lattice<tree> * src_lat,ipcp_lattice<tree> * dest_lat,int src_idx,tree parm_type)1594 propagate_vals_across_pass_through (cgraph_edge *cs, ipa_jump_func *jfunc,
1595 ipcp_lattice<tree> *src_lat,
1596 ipcp_lattice<tree> *dest_lat, int src_idx,
1597 tree parm_type)
1598 {
1599 ipcp_value<tree> *src_val;
1600 bool ret = false;
1601
1602 /* Do not create new values when propagating within an SCC because if there
1603 are arithmetic functions with circular dependencies, there is infinite
1604 number of them and we would just make lattices bottom. If this condition
1605 is ever relaxed we have to detect self-feeding recursive calls in
1606 cgraph_edge_brings_value_p in a smarter way. */
1607 if ((ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR)
1608 && ipa_edge_within_scc (cs))
1609 ret = dest_lat->set_contains_variable ();
1610 else
1611 for (src_val = src_lat->values; src_val; src_val = src_val->next)
1612 {
1613 tree cstval = ipa_get_jf_pass_through_result (jfunc, src_val->value,
1614 parm_type);
1615
1616 if (cstval)
1617 ret |= dest_lat->add_value (cstval, cs, src_val, src_idx);
1618 else
1619 ret |= dest_lat->set_contains_variable ();
1620 }
1621
1622 return ret;
1623 }
1624
1625 /* Propagate values through an ancestor jump function JFUNC associated with
1626 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1627 is the index of the source parameter. */
1628
1629 static bool
propagate_vals_across_ancestor(struct cgraph_edge * cs,struct ipa_jump_func * jfunc,ipcp_lattice<tree> * src_lat,ipcp_lattice<tree> * dest_lat,int src_idx)1630 propagate_vals_across_ancestor (struct cgraph_edge *cs,
1631 struct ipa_jump_func *jfunc,
1632 ipcp_lattice<tree> *src_lat,
1633 ipcp_lattice<tree> *dest_lat, int src_idx)
1634 {
1635 ipcp_value<tree> *src_val;
1636 bool ret = false;
1637
1638 if (ipa_edge_within_scc (cs))
1639 return dest_lat->set_contains_variable ();
1640
1641 for (src_val = src_lat->values; src_val; src_val = src_val->next)
1642 {
1643 tree t = ipa_get_jf_ancestor_result (jfunc, src_val->value);
1644
1645 if (t)
1646 ret |= dest_lat->add_value (t, cs, src_val, src_idx);
1647 else
1648 ret |= dest_lat->set_contains_variable ();
1649 }
1650
1651 return ret;
1652 }
1653
1654 /* Propagate scalar values across jump function JFUNC that is associated with
1655 edge CS and put the values into DEST_LAT. PARM_TYPE is the type of the
1656 parameter to which the result is passed. */
1657
1658 static bool
propagate_scalar_across_jump_function(struct cgraph_edge * cs,struct ipa_jump_func * jfunc,ipcp_lattice<tree> * dest_lat,tree param_type)1659 propagate_scalar_across_jump_function (struct cgraph_edge *cs,
1660 struct ipa_jump_func *jfunc,
1661 ipcp_lattice<tree> *dest_lat,
1662 tree param_type)
1663 {
1664 if (dest_lat->bottom)
1665 return false;
1666
1667 if (jfunc->type == IPA_JF_CONST)
1668 {
1669 tree val = ipa_get_jf_constant (jfunc);
1670 return dest_lat->add_value (val, cs, NULL, 0);
1671 }
1672 else if (jfunc->type == IPA_JF_PASS_THROUGH
1673 || jfunc->type == IPA_JF_ANCESTOR)
1674 {
1675 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1676 ipcp_lattice<tree> *src_lat;
1677 int src_idx;
1678 bool ret;
1679
1680 if (jfunc->type == IPA_JF_PASS_THROUGH)
1681 src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
1682 else
1683 src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
1684
1685 src_lat = ipa_get_scalar_lat (caller_info, src_idx);
1686 if (src_lat->bottom)
1687 return dest_lat->set_contains_variable ();
1688
1689 /* If we would need to clone the caller and cannot, do not propagate. */
1690 if (!ipcp_versionable_function_p (cs->caller)
1691 && (src_lat->contains_variable
1692 || (src_lat->values_count > 1)))
1693 return dest_lat->set_contains_variable ();
1694
1695 if (jfunc->type == IPA_JF_PASS_THROUGH)
1696 ret = propagate_vals_across_pass_through (cs, jfunc, src_lat,
1697 dest_lat, src_idx, param_type);
1698 else
1699 ret = propagate_vals_across_ancestor (cs, jfunc, src_lat, dest_lat,
1700 src_idx);
1701
1702 if (src_lat->contains_variable)
1703 ret |= dest_lat->set_contains_variable ();
1704
1705 return ret;
1706 }
1707
1708 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1709 use it for indirect inlining), we should propagate them too. */
1710 return dest_lat->set_contains_variable ();
1711 }
1712
1713 /* Propagate scalar values across jump function JFUNC that is associated with
1714 edge CS and describes argument IDX and put the values into DEST_LAT. */
1715
1716 static bool
propagate_context_across_jump_function(cgraph_edge * cs,ipa_jump_func * jfunc,int idx,ipcp_lattice<ipa_polymorphic_call_context> * dest_lat)1717 propagate_context_across_jump_function (cgraph_edge *cs,
1718 ipa_jump_func *jfunc, int idx,
1719 ipcp_lattice<ipa_polymorphic_call_context> *dest_lat)
1720 {
1721 ipa_edge_args *args = IPA_EDGE_REF (cs);
1722 if (dest_lat->bottom)
1723 return false;
1724 bool ret = false;
1725 bool added_sth = false;
1726 bool type_preserved = true;
1727
1728 ipa_polymorphic_call_context edge_ctx, *edge_ctx_ptr
1729 = ipa_get_ith_polymorhic_call_context (args, idx);
1730
1731 if (edge_ctx_ptr)
1732 edge_ctx = *edge_ctx_ptr;
1733
1734 if (jfunc->type == IPA_JF_PASS_THROUGH
1735 || jfunc->type == IPA_JF_ANCESTOR)
1736 {
1737 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1738 int src_idx;
1739 ipcp_lattice<ipa_polymorphic_call_context> *src_lat;
1740
1741 /* TODO: Once we figure out how to propagate speculations, it will
1742 probably be a good idea to switch to speculation if type_preserved is
1743 not set instead of punting. */
1744 if (jfunc->type == IPA_JF_PASS_THROUGH)
1745 {
1746 if (ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR)
1747 goto prop_fail;
1748 type_preserved = ipa_get_jf_pass_through_type_preserved (jfunc);
1749 src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
1750 }
1751 else
1752 {
1753 type_preserved = ipa_get_jf_ancestor_type_preserved (jfunc);
1754 src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
1755 }
1756
1757 src_lat = ipa_get_poly_ctx_lat (caller_info, src_idx);
1758 /* If we would need to clone the caller and cannot, do not propagate. */
1759 if (!ipcp_versionable_function_p (cs->caller)
1760 && (src_lat->contains_variable
1761 || (src_lat->values_count > 1)))
1762 goto prop_fail;
1763
1764 ipcp_value<ipa_polymorphic_call_context> *src_val;
1765 for (src_val = src_lat->values; src_val; src_val = src_val->next)
1766 {
1767 ipa_polymorphic_call_context cur = src_val->value;
1768
1769 if (!type_preserved)
1770 cur.possible_dynamic_type_change (cs->in_polymorphic_cdtor);
1771 if (jfunc->type == IPA_JF_ANCESTOR)
1772 cur.offset_by (ipa_get_jf_ancestor_offset (jfunc));
1773 /* TODO: In cases we know how the context is going to be used,
1774 we can improve the result by passing proper OTR_TYPE. */
1775 cur.combine_with (edge_ctx);
1776 if (!cur.useless_p ())
1777 {
1778 if (src_lat->contains_variable
1779 && !edge_ctx.equal_to (cur))
1780 ret |= dest_lat->set_contains_variable ();
1781 ret |= dest_lat->add_value (cur, cs, src_val, src_idx);
1782 added_sth = true;
1783 }
1784 }
1785
1786 }
1787
1788 prop_fail:
1789 if (!added_sth)
1790 {
1791 if (!edge_ctx.useless_p ())
1792 ret |= dest_lat->add_value (edge_ctx, cs);
1793 else
1794 ret |= dest_lat->set_contains_variable ();
1795 }
1796
1797 return ret;
1798 }
1799
1800 /* Propagate bits across jfunc that is associated with
1801 edge cs and update dest_lattice accordingly. */
1802
1803 bool
propagate_bits_across_jump_function(cgraph_edge * cs,int idx,ipa_jump_func * jfunc,ipcp_bits_lattice * dest_lattice)1804 propagate_bits_across_jump_function (cgraph_edge *cs, int idx,
1805 ipa_jump_func *jfunc,
1806 ipcp_bits_lattice *dest_lattice)
1807 {
1808 if (dest_lattice->bottom_p ())
1809 return false;
1810
1811 enum availability availability;
1812 cgraph_node *callee = cs->callee->function_symbol (&availability);
1813 struct ipa_node_params *callee_info = IPA_NODE_REF (callee);
1814 tree parm_type = ipa_get_type (callee_info, idx);
1815
1816 /* For K&R C programs, ipa_get_type() could return NULL_TREE. Avoid the
1817 transform for these cases. Similarly, we can have bad type mismatches
1818 with LTO, avoid doing anything with those too. */
1819 if (!parm_type
1820 || (!INTEGRAL_TYPE_P (parm_type) && !POINTER_TYPE_P (parm_type)))
1821 {
1822 if (dump_file && (dump_flags & TDF_DETAILS))
1823 fprintf (dump_file, "Setting dest_lattice to bottom, because type of "
1824 "param %i of %s is NULL or unsuitable for bits propagation\n",
1825 idx, cs->callee->name ());
1826
1827 return dest_lattice->set_to_bottom ();
1828 }
1829
1830 unsigned precision = TYPE_PRECISION (parm_type);
1831 signop sgn = TYPE_SIGN (parm_type);
1832
1833 if (jfunc->type == IPA_JF_PASS_THROUGH
1834 || jfunc->type == IPA_JF_ANCESTOR)
1835 {
1836 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1837 tree operand = NULL_TREE;
1838 enum tree_code code;
1839 unsigned src_idx;
1840
1841 if (jfunc->type == IPA_JF_PASS_THROUGH)
1842 {
1843 code = ipa_get_jf_pass_through_operation (jfunc);
1844 src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
1845 if (code != NOP_EXPR)
1846 operand = ipa_get_jf_pass_through_operand (jfunc);
1847 }
1848 else
1849 {
1850 code = POINTER_PLUS_EXPR;
1851 src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
1852 unsigned HOST_WIDE_INT offset = ipa_get_jf_ancestor_offset (jfunc) / BITS_PER_UNIT;
1853 operand = build_int_cstu (size_type_node, offset);
1854 }
1855
1856 struct ipcp_param_lattices *src_lats
1857 = ipa_get_parm_lattices (caller_info, src_idx);
1858
1859 /* Try to propagate bits if src_lattice is bottom, but jfunc is known.
1860 for eg consider:
1861 int f(int x)
1862 {
1863 g (x & 0xff);
1864 }
1865 Assume lattice for x is bottom, however we can still propagate
1866 result of x & 0xff == 0xff, which gets computed during ccp1 pass
1867 and we store it in jump function during analysis stage. */
1868
1869 if (src_lats->bits_lattice.bottom_p ()
1870 && jfunc->bits)
1871 return dest_lattice->meet_with (jfunc->bits->value, jfunc->bits->mask,
1872 precision);
1873 else
1874 return dest_lattice->meet_with (src_lats->bits_lattice, precision, sgn,
1875 code, operand);
1876 }
1877
1878 else if (jfunc->type == IPA_JF_ANCESTOR)
1879 return dest_lattice->set_to_bottom ();
1880 else if (jfunc->bits)
1881 return dest_lattice->meet_with (jfunc->bits->value, jfunc->bits->mask,
1882 precision);
1883 else
1884 return dest_lattice->set_to_bottom ();
1885 }
1886
1887 /* Emulate effects of unary OPERATION and/or conversion from SRC_TYPE to
1888 DST_TYPE on value range in SRC_VR and store it to DST_VR. Return true if
1889 the result is a range or an anti-range. */
1890
1891 static bool
ipa_vr_operation_and_type_effects(value_range * dst_vr,value_range * src_vr,enum tree_code operation,tree dst_type,tree src_type)1892 ipa_vr_operation_and_type_effects (value_range *dst_vr, value_range *src_vr,
1893 enum tree_code operation,
1894 tree dst_type, tree src_type)
1895 {
1896 memset (dst_vr, 0, sizeof (*dst_vr));
1897 extract_range_from_unary_expr (dst_vr, operation, dst_type, src_vr, src_type);
1898 if (dst_vr->type == VR_RANGE || dst_vr->type == VR_ANTI_RANGE)
1899 return true;
1900 else
1901 return false;
1902 }
1903
1904 /* Propagate value range across jump function JFUNC that is associated with
1905 edge CS with param of callee of PARAM_TYPE and update DEST_PLATS
1906 accordingly. */
1907
1908 static bool
propagate_vr_across_jump_function(cgraph_edge * cs,ipa_jump_func * jfunc,struct ipcp_param_lattices * dest_plats,tree param_type)1909 propagate_vr_across_jump_function (cgraph_edge *cs, ipa_jump_func *jfunc,
1910 struct ipcp_param_lattices *dest_plats,
1911 tree param_type)
1912 {
1913 ipcp_vr_lattice *dest_lat = &dest_plats->m_value_range;
1914
1915 if (dest_lat->bottom_p ())
1916 return false;
1917
1918 if (!param_type
1919 || (!INTEGRAL_TYPE_P (param_type)
1920 && !POINTER_TYPE_P (param_type)))
1921 return dest_lat->set_to_bottom ();
1922
1923 if (jfunc->type == IPA_JF_PASS_THROUGH)
1924 {
1925 enum tree_code operation = ipa_get_jf_pass_through_operation (jfunc);
1926
1927 if (TREE_CODE_CLASS (operation) == tcc_unary)
1928 {
1929 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1930 int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
1931 tree operand_type = ipa_get_type (caller_info, src_idx);
1932 struct ipcp_param_lattices *src_lats
1933 = ipa_get_parm_lattices (caller_info, src_idx);
1934
1935 if (src_lats->m_value_range.bottom_p ())
1936 return dest_lat->set_to_bottom ();
1937 value_range vr;
1938 if (ipa_vr_operation_and_type_effects (&vr,
1939 &src_lats->m_value_range.m_vr,
1940 operation, param_type,
1941 operand_type))
1942 return dest_lat->meet_with (&vr);
1943 }
1944 }
1945 else if (jfunc->type == IPA_JF_CONST)
1946 {
1947 tree val = ipa_get_jf_constant (jfunc);
1948 if (TREE_CODE (val) == INTEGER_CST)
1949 {
1950 val = fold_convert (param_type, val);
1951 if (TREE_OVERFLOW_P (val))
1952 val = drop_tree_overflow (val);
1953
1954 value_range tmpvr;
1955 memset (&tmpvr, 0, sizeof (tmpvr));
1956 tmpvr.type = VR_RANGE;
1957 tmpvr.min = val;
1958 tmpvr.max = val;
1959 return dest_lat->meet_with (&tmpvr);
1960 }
1961 }
1962
1963 value_range vr;
1964 if (jfunc->m_vr
1965 && ipa_vr_operation_and_type_effects (&vr, jfunc->m_vr, NOP_EXPR,
1966 param_type,
1967 TREE_TYPE (jfunc->m_vr->min)))
1968 return dest_lat->meet_with (&vr);
1969 else
1970 return dest_lat->set_to_bottom ();
1971 }
1972
1973 /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
1974 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
1975 other cases, return false). If there are no aggregate items, set
1976 aggs_by_ref to NEW_AGGS_BY_REF. */
1977
1978 static bool
set_check_aggs_by_ref(struct ipcp_param_lattices * dest_plats,bool new_aggs_by_ref)1979 set_check_aggs_by_ref (struct ipcp_param_lattices *dest_plats,
1980 bool new_aggs_by_ref)
1981 {
1982 if (dest_plats->aggs)
1983 {
1984 if (dest_plats->aggs_by_ref != new_aggs_by_ref)
1985 {
1986 set_agg_lats_to_bottom (dest_plats);
1987 return true;
1988 }
1989 }
1990 else
1991 dest_plats->aggs_by_ref = new_aggs_by_ref;
1992 return false;
1993 }
1994
1995 /* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
1996 already existing lattice for the given OFFSET and SIZE, marking all skipped
1997 lattices as containing variable and checking for overlaps. If there is no
1998 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
1999 it with offset, size and contains_variable to PRE_EXISTING, and return true,
2000 unless there are too many already. If there are two many, return false. If
2001 there are overlaps turn whole DEST_PLATS to bottom and return false. If any
2002 skipped lattices were newly marked as containing variable, set *CHANGE to
2003 true. */
2004
2005 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)2006 merge_agg_lats_step (struct ipcp_param_lattices *dest_plats,
2007 HOST_WIDE_INT offset, HOST_WIDE_INT val_size,
2008 struct ipcp_agg_lattice ***aglat,
2009 bool pre_existing, bool *change)
2010 {
2011 gcc_checking_assert (offset >= 0);
2012
2013 while (**aglat && (**aglat)->offset < offset)
2014 {
2015 if ((**aglat)->offset + (**aglat)->size > offset)
2016 {
2017 set_agg_lats_to_bottom (dest_plats);
2018 return false;
2019 }
2020 *change |= (**aglat)->set_contains_variable ();
2021 *aglat = &(**aglat)->next;
2022 }
2023
2024 if (**aglat && (**aglat)->offset == offset)
2025 {
2026 if ((**aglat)->size != val_size
2027 || ((**aglat)->next
2028 && (**aglat)->next->offset < offset + val_size))
2029 {
2030 set_agg_lats_to_bottom (dest_plats);
2031 return false;
2032 }
2033 gcc_checking_assert (!(**aglat)->next
2034 || (**aglat)->next->offset >= offset + val_size);
2035 return true;
2036 }
2037 else
2038 {
2039 struct ipcp_agg_lattice *new_al;
2040
2041 if (**aglat && (**aglat)->offset < offset + val_size)
2042 {
2043 set_agg_lats_to_bottom (dest_plats);
2044 return false;
2045 }
2046 if (dest_plats->aggs_count == PARAM_VALUE (PARAM_IPA_MAX_AGG_ITEMS))
2047 return false;
2048 dest_plats->aggs_count++;
2049 new_al = ipcp_agg_lattice_pool.allocate ();
2050 memset (new_al, 0, sizeof (*new_al));
2051
2052 new_al->offset = offset;
2053 new_al->size = val_size;
2054 new_al->contains_variable = pre_existing;
2055
2056 new_al->next = **aglat;
2057 **aglat = new_al;
2058 return true;
2059 }
2060 }
2061
2062 /* Set all AGLAT and all other aggregate lattices reachable by next pointers as
2063 containing an unknown value. */
2064
2065 static bool
set_chain_of_aglats_contains_variable(struct ipcp_agg_lattice * aglat)2066 set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice *aglat)
2067 {
2068 bool ret = false;
2069 while (aglat)
2070 {
2071 ret |= aglat->set_contains_variable ();
2072 aglat = aglat->next;
2073 }
2074 return ret;
2075 }
2076
2077 /* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
2078 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source
2079 parameter used for lattice value sources. Return true if DEST_PLATS changed
2080 in any way. */
2081
2082 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)2083 merge_aggregate_lattices (struct cgraph_edge *cs,
2084 struct ipcp_param_lattices *dest_plats,
2085 struct ipcp_param_lattices *src_plats,
2086 int src_idx, HOST_WIDE_INT offset_delta)
2087 {
2088 bool pre_existing = dest_plats->aggs != NULL;
2089 struct ipcp_agg_lattice **dst_aglat;
2090 bool ret = false;
2091
2092 if (set_check_aggs_by_ref (dest_plats, src_plats->aggs_by_ref))
2093 return true;
2094 if (src_plats->aggs_bottom)
2095 return set_agg_lats_contain_variable (dest_plats);
2096 if (src_plats->aggs_contain_variable)
2097 ret |= set_agg_lats_contain_variable (dest_plats);
2098 dst_aglat = &dest_plats->aggs;
2099
2100 for (struct ipcp_agg_lattice *src_aglat = src_plats->aggs;
2101 src_aglat;
2102 src_aglat = src_aglat->next)
2103 {
2104 HOST_WIDE_INT new_offset = src_aglat->offset - offset_delta;
2105
2106 if (new_offset < 0)
2107 continue;
2108 if (merge_agg_lats_step (dest_plats, new_offset, src_aglat->size,
2109 &dst_aglat, pre_existing, &ret))
2110 {
2111 struct ipcp_agg_lattice *new_al = *dst_aglat;
2112
2113 dst_aglat = &(*dst_aglat)->next;
2114 if (src_aglat->bottom)
2115 {
2116 ret |= new_al->set_contains_variable ();
2117 continue;
2118 }
2119 if (src_aglat->contains_variable)
2120 ret |= new_al->set_contains_variable ();
2121 for (ipcp_value<tree> *val = src_aglat->values;
2122 val;
2123 val = val->next)
2124 ret |= new_al->add_value (val->value, cs, val, src_idx,
2125 src_aglat->offset);
2126 }
2127 else if (dest_plats->aggs_bottom)
2128 return true;
2129 }
2130 ret |= set_chain_of_aglats_contains_variable (*dst_aglat);
2131 return ret;
2132 }
2133
2134 /* Determine whether there is anything to propagate FROM SRC_PLATS through a
2135 pass-through JFUNC and if so, whether it has conform and conforms to the
2136 rules about propagating values passed by reference. */
2137
2138 static bool
agg_pass_through_permissible_p(struct ipcp_param_lattices * src_plats,struct ipa_jump_func * jfunc)2139 agg_pass_through_permissible_p (struct ipcp_param_lattices *src_plats,
2140 struct ipa_jump_func *jfunc)
2141 {
2142 return src_plats->aggs
2143 && (!src_plats->aggs_by_ref
2144 || ipa_get_jf_pass_through_agg_preserved (jfunc));
2145 }
2146
2147 /* Propagate scalar values across jump function JFUNC that is associated with
2148 edge CS and put the values into DEST_LAT. */
2149
2150 static bool
propagate_aggs_across_jump_function(struct cgraph_edge * cs,struct ipa_jump_func * jfunc,struct ipcp_param_lattices * dest_plats)2151 propagate_aggs_across_jump_function (struct cgraph_edge *cs,
2152 struct ipa_jump_func *jfunc,
2153 struct ipcp_param_lattices *dest_plats)
2154 {
2155 bool ret = false;
2156
2157 if (dest_plats->aggs_bottom)
2158 return false;
2159
2160 if (jfunc->type == IPA_JF_PASS_THROUGH
2161 && ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
2162 {
2163 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
2164 int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
2165 struct ipcp_param_lattices *src_plats;
2166
2167 src_plats = ipa_get_parm_lattices (caller_info, src_idx);
2168 if (agg_pass_through_permissible_p (src_plats, jfunc))
2169 {
2170 /* Currently we do not produce clobber aggregate jump
2171 functions, replace with merging when we do. */
2172 gcc_assert (!jfunc->agg.items);
2173 ret |= merge_aggregate_lattices (cs, dest_plats, src_plats,
2174 src_idx, 0);
2175 }
2176 else
2177 ret |= set_agg_lats_contain_variable (dest_plats);
2178 }
2179 else if (jfunc->type == IPA_JF_ANCESTOR
2180 && ipa_get_jf_ancestor_agg_preserved (jfunc))
2181 {
2182 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
2183 int src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
2184 struct ipcp_param_lattices *src_plats;
2185
2186 src_plats = ipa_get_parm_lattices (caller_info, src_idx);
2187 if (src_plats->aggs && src_plats->aggs_by_ref)
2188 {
2189 /* Currently we do not produce clobber aggregate jump
2190 functions, replace with merging when we do. */
2191 gcc_assert (!jfunc->agg.items);
2192 ret |= merge_aggregate_lattices (cs, dest_plats, src_plats, src_idx,
2193 ipa_get_jf_ancestor_offset (jfunc));
2194 }
2195 else if (!src_plats->aggs_by_ref)
2196 ret |= set_agg_lats_to_bottom (dest_plats);
2197 else
2198 ret |= set_agg_lats_contain_variable (dest_plats);
2199 }
2200 else if (jfunc->agg.items)
2201 {
2202 bool pre_existing = dest_plats->aggs != NULL;
2203 struct ipcp_agg_lattice **aglat = &dest_plats->aggs;
2204 struct ipa_agg_jf_item *item;
2205 int i;
2206
2207 if (set_check_aggs_by_ref (dest_plats, jfunc->agg.by_ref))
2208 return true;
2209
2210 FOR_EACH_VEC_ELT (*jfunc->agg.items, i, item)
2211 {
2212 HOST_WIDE_INT val_size;
2213
2214 if (item->offset < 0)
2215 continue;
2216 gcc_checking_assert (is_gimple_ip_invariant (item->value));
2217 val_size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (item->value)));
2218
2219 if (merge_agg_lats_step (dest_plats, item->offset, val_size,
2220 &aglat, pre_existing, &ret))
2221 {
2222 ret |= (*aglat)->add_value (item->value, cs, NULL, 0, 0);
2223 aglat = &(*aglat)->next;
2224 }
2225 else if (dest_plats->aggs_bottom)
2226 return true;
2227 }
2228
2229 ret |= set_chain_of_aglats_contains_variable (*aglat);
2230 }
2231 else
2232 ret |= set_agg_lats_contain_variable (dest_plats);
2233
2234 return ret;
2235 }
2236
2237 /* Return true if on the way cfrom CS->caller to the final (non-alias and
2238 non-thunk) destination, the call passes through a thunk. */
2239
2240 static bool
call_passes_through_thunk_p(cgraph_edge * cs)2241 call_passes_through_thunk_p (cgraph_edge *cs)
2242 {
2243 cgraph_node *alias_or_thunk = cs->callee;
2244 while (alias_or_thunk->alias)
2245 alias_or_thunk = alias_or_thunk->get_alias_target ();
2246 return alias_or_thunk->thunk.thunk_p;
2247 }
2248
2249 /* Propagate constants from the caller to the callee of CS. INFO describes the
2250 caller. */
2251
2252 static bool
propagate_constants_across_call(struct cgraph_edge * cs)2253 propagate_constants_across_call (struct cgraph_edge *cs)
2254 {
2255 struct ipa_node_params *callee_info;
2256 enum availability availability;
2257 cgraph_node *callee;
2258 struct ipa_edge_args *args;
2259 bool ret = false;
2260 int i, args_count, parms_count;
2261
2262 callee = cs->callee->function_symbol (&availability);
2263 if (!callee->definition)
2264 return false;
2265 gcc_checking_assert (callee->has_gimple_body_p ());
2266 callee_info = IPA_NODE_REF (callee);
2267
2268 args = IPA_EDGE_REF (cs);
2269 args_count = ipa_get_cs_argument_count (args);
2270 parms_count = ipa_get_param_count (callee_info);
2271 if (parms_count == 0)
2272 return false;
2273
2274 /* No propagation through instrumentation thunks is available yet.
2275 It should be possible with proper mapping of call args and
2276 instrumented callee params in the propagation loop below. But
2277 this case mostly occurs when legacy code calls instrumented code
2278 and it is not a primary target for optimizations.
2279 We detect instrumentation thunks in aliases and thunks chain by
2280 checking instrumentation_clone flag for chain source and target.
2281 Going through instrumentation thunks we always have it changed
2282 from 0 to 1 and all other nodes do not change it. */
2283 if (!cs->callee->instrumentation_clone
2284 && callee->instrumentation_clone)
2285 {
2286 for (i = 0; i < parms_count; i++)
2287 ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info,
2288 i));
2289 return ret;
2290 }
2291
2292 /* If this call goes through a thunk we must not propagate to the first (0th)
2293 parameter. However, we might need to uncover a thunk from below a series
2294 of aliases first. */
2295 if (call_passes_through_thunk_p (cs))
2296 {
2297 ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info,
2298 0));
2299 i = 1;
2300 }
2301 else
2302 i = 0;
2303
2304 for (; (i < args_count) && (i < parms_count); i++)
2305 {
2306 struct ipa_jump_func *jump_func = ipa_get_ith_jump_func (args, i);
2307 struct ipcp_param_lattices *dest_plats;
2308 tree param_type = ipa_get_type (callee_info, i);
2309
2310 dest_plats = ipa_get_parm_lattices (callee_info, i);
2311 if (availability == AVAIL_INTERPOSABLE)
2312 ret |= set_all_contains_variable (dest_plats);
2313 else
2314 {
2315 ret |= propagate_scalar_across_jump_function (cs, jump_func,
2316 &dest_plats->itself,
2317 param_type);
2318 ret |= propagate_context_across_jump_function (cs, jump_func, i,
2319 &dest_plats->ctxlat);
2320 ret
2321 |= propagate_bits_across_jump_function (cs, i, jump_func,
2322 &dest_plats->bits_lattice);
2323 ret |= propagate_aggs_across_jump_function (cs, jump_func,
2324 dest_plats);
2325 if (opt_for_fn (callee->decl, flag_ipa_vrp))
2326 ret |= propagate_vr_across_jump_function (cs, jump_func,
2327 dest_plats, param_type);
2328 else
2329 ret |= dest_plats->m_value_range.set_to_bottom ();
2330 }
2331 }
2332 for (; i < parms_count; i++)
2333 ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info, i));
2334
2335 return ret;
2336 }
2337
2338 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
2339 KNOWN_CONTEXTS, KNOWN_AGGS or AGG_REPS return the destination. The latter
2340 three can be NULL. If AGG_REPS is not NULL, KNOWN_AGGS is ignored. */
2341
2342 static tree
ipa_get_indirect_edge_target_1(struct cgraph_edge * ie,vec<tree> known_csts,vec<ipa_polymorphic_call_context> known_contexts,vec<ipa_agg_jump_function_p> known_aggs,struct ipa_agg_replacement_value * agg_reps,bool * speculative)2343 ipa_get_indirect_edge_target_1 (struct cgraph_edge *ie,
2344 vec<tree> known_csts,
2345 vec<ipa_polymorphic_call_context> known_contexts,
2346 vec<ipa_agg_jump_function_p> known_aggs,
2347 struct ipa_agg_replacement_value *agg_reps,
2348 bool *speculative)
2349 {
2350 int param_index = ie->indirect_info->param_index;
2351 HOST_WIDE_INT anc_offset;
2352 tree t;
2353 tree target = NULL;
2354
2355 *speculative = false;
2356
2357 if (param_index == -1
2358 || known_csts.length () <= (unsigned int) param_index)
2359 return NULL_TREE;
2360
2361 if (!ie->indirect_info->polymorphic)
2362 {
2363 tree t;
2364
2365 if (ie->indirect_info->agg_contents)
2366 {
2367 t = NULL;
2368 if (agg_reps && ie->indirect_info->guaranteed_unmodified)
2369 {
2370 while (agg_reps)
2371 {
2372 if (agg_reps->index == param_index
2373 && agg_reps->offset == ie->indirect_info->offset
2374 && agg_reps->by_ref == ie->indirect_info->by_ref)
2375 {
2376 t = agg_reps->value;
2377 break;
2378 }
2379 agg_reps = agg_reps->next;
2380 }
2381 }
2382 if (!t)
2383 {
2384 struct ipa_agg_jump_function *agg;
2385 if (known_aggs.length () > (unsigned int) param_index)
2386 agg = known_aggs[param_index];
2387 else
2388 agg = NULL;
2389 bool from_global_constant;
2390 t = ipa_find_agg_cst_for_param (agg, known_csts[param_index],
2391 ie->indirect_info->offset,
2392 ie->indirect_info->by_ref,
2393 &from_global_constant);
2394 if (t
2395 && !from_global_constant
2396 && !ie->indirect_info->guaranteed_unmodified)
2397 t = NULL_TREE;
2398 }
2399 }
2400 else
2401 t = known_csts[param_index];
2402
2403 if (t
2404 && TREE_CODE (t) == ADDR_EXPR
2405 && TREE_CODE (TREE_OPERAND (t, 0)) == FUNCTION_DECL)
2406 return TREE_OPERAND (t, 0);
2407 else
2408 return NULL_TREE;
2409 }
2410
2411 if (!opt_for_fn (ie->caller->decl, flag_devirtualize))
2412 return NULL_TREE;
2413
2414 gcc_assert (!ie->indirect_info->agg_contents);
2415 anc_offset = ie->indirect_info->offset;
2416
2417 t = NULL;
2418
2419 /* Try to work out value of virtual table pointer value in replacemnets. */
2420 if (!t && agg_reps && !ie->indirect_info->by_ref)
2421 {
2422 while (agg_reps)
2423 {
2424 if (agg_reps->index == param_index
2425 && agg_reps->offset == ie->indirect_info->offset
2426 && agg_reps->by_ref)
2427 {
2428 t = agg_reps->value;
2429 break;
2430 }
2431 agg_reps = agg_reps->next;
2432 }
2433 }
2434
2435 /* Try to work out value of virtual table pointer value in known
2436 aggregate values. */
2437 if (!t && known_aggs.length () > (unsigned int) param_index
2438 && !ie->indirect_info->by_ref)
2439 {
2440 struct ipa_agg_jump_function *agg;
2441 agg = known_aggs[param_index];
2442 t = ipa_find_agg_cst_for_param (agg, known_csts[param_index],
2443 ie->indirect_info->offset, true);
2444 }
2445
2446 /* If we found the virtual table pointer, lookup the target. */
2447 if (t)
2448 {
2449 tree vtable;
2450 unsigned HOST_WIDE_INT offset;
2451 if (vtable_pointer_value_to_vtable (t, &vtable, &offset))
2452 {
2453 bool can_refer;
2454 target = gimple_get_virt_method_for_vtable (ie->indirect_info->otr_token,
2455 vtable, offset, &can_refer);
2456 if (can_refer)
2457 {
2458 if (!target
2459 || (TREE_CODE (TREE_TYPE (target)) == FUNCTION_TYPE
2460 && DECL_FUNCTION_CODE (target) == BUILT_IN_UNREACHABLE)
2461 || !possible_polymorphic_call_target_p
2462 (ie, cgraph_node::get (target)))
2463 {
2464 /* Do not speculate builtin_unreachable, it is stupid! */
2465 if (ie->indirect_info->vptr_changed)
2466 return NULL;
2467 target = ipa_impossible_devirt_target (ie, target);
2468 }
2469 *speculative = ie->indirect_info->vptr_changed;
2470 if (!*speculative)
2471 return target;
2472 }
2473 }
2474 }
2475
2476 /* Do we know the constant value of pointer? */
2477 if (!t)
2478 t = known_csts[param_index];
2479
2480 gcc_checking_assert (!t || TREE_CODE (t) != TREE_BINFO);
2481
2482 ipa_polymorphic_call_context context;
2483 if (known_contexts.length () > (unsigned int) param_index)
2484 {
2485 context = known_contexts[param_index];
2486 context.offset_by (anc_offset);
2487 if (ie->indirect_info->vptr_changed)
2488 context.possible_dynamic_type_change (ie->in_polymorphic_cdtor,
2489 ie->indirect_info->otr_type);
2490 if (t)
2491 {
2492 ipa_polymorphic_call_context ctx2 = ipa_polymorphic_call_context
2493 (t, ie->indirect_info->otr_type, anc_offset);
2494 if (!ctx2.useless_p ())
2495 context.combine_with (ctx2, ie->indirect_info->otr_type);
2496 }
2497 }
2498 else if (t)
2499 {
2500 context = ipa_polymorphic_call_context (t, ie->indirect_info->otr_type,
2501 anc_offset);
2502 if (ie->indirect_info->vptr_changed)
2503 context.possible_dynamic_type_change (ie->in_polymorphic_cdtor,
2504 ie->indirect_info->otr_type);
2505 }
2506 else
2507 return NULL_TREE;
2508
2509 vec <cgraph_node *>targets;
2510 bool final;
2511
2512 targets = possible_polymorphic_call_targets
2513 (ie->indirect_info->otr_type,
2514 ie->indirect_info->otr_token,
2515 context, &final);
2516 if (!final || targets.length () > 1)
2517 {
2518 struct cgraph_node *node;
2519 if (*speculative)
2520 return target;
2521 if (!opt_for_fn (ie->caller->decl, flag_devirtualize_speculatively)
2522 || ie->speculative || !ie->maybe_hot_p ())
2523 return NULL;
2524 node = try_speculative_devirtualization (ie->indirect_info->otr_type,
2525 ie->indirect_info->otr_token,
2526 context);
2527 if (node)
2528 {
2529 *speculative = true;
2530 target = node->decl;
2531 }
2532 else
2533 return NULL;
2534 }
2535 else
2536 {
2537 *speculative = false;
2538 if (targets.length () == 1)
2539 target = targets[0]->decl;
2540 else
2541 target = ipa_impossible_devirt_target (ie, NULL_TREE);
2542 }
2543
2544 if (target && !possible_polymorphic_call_target_p (ie,
2545 cgraph_node::get (target)))
2546 {
2547 if (*speculative)
2548 return NULL;
2549 target = ipa_impossible_devirt_target (ie, target);
2550 }
2551
2552 return target;
2553 }
2554
2555
2556 /* If an indirect edge IE can be turned into a direct one based on KNOWN_CSTS,
2557 KNOWN_CONTEXTS (which can be vNULL) or KNOWN_AGGS (which also can be vNULL)
2558 return the destination. */
2559
2560 tree
ipa_get_indirect_edge_target(struct cgraph_edge * ie,vec<tree> known_csts,vec<ipa_polymorphic_call_context> known_contexts,vec<ipa_agg_jump_function_p> known_aggs,bool * speculative)2561 ipa_get_indirect_edge_target (struct cgraph_edge *ie,
2562 vec<tree> known_csts,
2563 vec<ipa_polymorphic_call_context> known_contexts,
2564 vec<ipa_agg_jump_function_p> known_aggs,
2565 bool *speculative)
2566 {
2567 return ipa_get_indirect_edge_target_1 (ie, known_csts, known_contexts,
2568 known_aggs, NULL, speculative);
2569 }
2570
2571 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
2572 and KNOWN_CONTEXTS. */
2573
2574 static int
devirtualization_time_bonus(struct cgraph_node * node,vec<tree> known_csts,vec<ipa_polymorphic_call_context> known_contexts,vec<ipa_agg_jump_function_p> known_aggs)2575 devirtualization_time_bonus (struct cgraph_node *node,
2576 vec<tree> known_csts,
2577 vec<ipa_polymorphic_call_context> known_contexts,
2578 vec<ipa_agg_jump_function_p> known_aggs)
2579 {
2580 struct cgraph_edge *ie;
2581 int res = 0;
2582
2583 for (ie = node->indirect_calls; ie; ie = ie->next_callee)
2584 {
2585 struct cgraph_node *callee;
2586 struct ipa_fn_summary *isummary;
2587 enum availability avail;
2588 tree target;
2589 bool speculative;
2590
2591 target = ipa_get_indirect_edge_target (ie, known_csts, known_contexts,
2592 known_aggs, &speculative);
2593 if (!target)
2594 continue;
2595
2596 /* Only bare minimum benefit for clearly un-inlineable targets. */
2597 res += 1;
2598 callee = cgraph_node::get (target);
2599 if (!callee || !callee->definition)
2600 continue;
2601 callee = callee->function_symbol (&avail);
2602 if (avail < AVAIL_AVAILABLE)
2603 continue;
2604 isummary = ipa_fn_summaries->get (callee);
2605 if (!isummary->inlinable)
2606 continue;
2607
2608 /* FIXME: The values below need re-considering and perhaps also
2609 integrating into the cost metrics, at lest in some very basic way. */
2610 if (isummary->size <= MAX_INLINE_INSNS_AUTO / 4)
2611 res += 31 / ((int)speculative + 1);
2612 else if (isummary->size <= MAX_INLINE_INSNS_AUTO / 2)
2613 res += 15 / ((int)speculative + 1);
2614 else if (isummary->size <= MAX_INLINE_INSNS_AUTO
2615 || DECL_DECLARED_INLINE_P (callee->decl))
2616 res += 7 / ((int)speculative + 1);
2617 }
2618
2619 return res;
2620 }
2621
2622 /* Return time bonus incurred because of HINTS. */
2623
2624 static int
hint_time_bonus(ipa_hints hints)2625 hint_time_bonus (ipa_hints hints)
2626 {
2627 int result = 0;
2628 if (hints & (INLINE_HINT_loop_iterations | INLINE_HINT_loop_stride))
2629 result += PARAM_VALUE (PARAM_IPA_CP_LOOP_HINT_BONUS);
2630 if (hints & INLINE_HINT_array_index)
2631 result += PARAM_VALUE (PARAM_IPA_CP_ARRAY_INDEX_HINT_BONUS);
2632 return result;
2633 }
2634
2635 /* If there is a reason to penalize the function described by INFO in the
2636 cloning goodness evaluation, do so. */
2637
2638 static inline int64_t
incorporate_penalties(ipa_node_params * info,int64_t evaluation)2639 incorporate_penalties (ipa_node_params *info, int64_t evaluation)
2640 {
2641 if (info->node_within_scc)
2642 evaluation = (evaluation
2643 * (100 - PARAM_VALUE (PARAM_IPA_CP_RECURSION_PENALTY))) / 100;
2644
2645 if (info->node_calling_single_call)
2646 evaluation = (evaluation
2647 * (100 - PARAM_VALUE (PARAM_IPA_CP_SINGLE_CALL_PENALTY)))
2648 / 100;
2649
2650 return evaluation;
2651 }
2652
2653 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
2654 and SIZE_COST and with the sum of frequencies of incoming edges to the
2655 potential new clone in FREQUENCIES. */
2656
2657 static bool
good_cloning_opportunity_p(struct cgraph_node * node,int time_benefit,int freq_sum,profile_count count_sum,int size_cost)2658 good_cloning_opportunity_p (struct cgraph_node *node, int time_benefit,
2659 int freq_sum, profile_count count_sum, int size_cost)
2660 {
2661 if (time_benefit == 0
2662 || !opt_for_fn (node->decl, flag_ipa_cp_clone)
2663 || node->optimize_for_size_p ())
2664 return false;
2665
2666 gcc_assert (size_cost > 0);
2667
2668 struct ipa_node_params *info = IPA_NODE_REF (node);
2669 if (max_count > profile_count::zero ())
2670 {
2671 int factor = RDIV (count_sum.probability_in
2672 (max_count).to_reg_br_prob_base ()
2673 * 1000, REG_BR_PROB_BASE);
2674 int64_t evaluation = (((int64_t) time_benefit * factor)
2675 / size_cost);
2676 evaluation = incorporate_penalties (info, evaluation);
2677
2678 if (dump_file && (dump_flags & TDF_DETAILS))
2679 {
2680 fprintf (dump_file, " good_cloning_opportunity_p (time: %i, "
2681 "size: %i, count_sum: ", time_benefit, size_cost);
2682 count_sum.dump (dump_file);
2683 fprintf (dump_file, "%s%s) -> evaluation: " "%" PRId64
2684 ", threshold: %i\n",
2685 info->node_within_scc ? ", scc" : "",
2686 info->node_calling_single_call ? ", single_call" : "",
2687 evaluation, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD));
2688 }
2689
2690 return evaluation >= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD);
2691 }
2692 else
2693 {
2694 int64_t evaluation = (((int64_t) time_benefit * freq_sum)
2695 / size_cost);
2696 evaluation = incorporate_penalties (info, evaluation);
2697
2698 if (dump_file && (dump_flags & TDF_DETAILS))
2699 fprintf (dump_file, " good_cloning_opportunity_p (time: %i, "
2700 "size: %i, freq_sum: %i%s%s) -> evaluation: "
2701 "%" PRId64 ", threshold: %i\n",
2702 time_benefit, size_cost, freq_sum,
2703 info->node_within_scc ? ", scc" : "",
2704 info->node_calling_single_call ? ", single_call" : "",
2705 evaluation, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD));
2706
2707 return evaluation >= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD);
2708 }
2709 }
2710
2711 /* Return all context independent values from aggregate lattices in PLATS in a
2712 vector. Return NULL if there are none. */
2713
2714 static vec<ipa_agg_jf_item, va_gc> *
context_independent_aggregate_values(struct ipcp_param_lattices * plats)2715 context_independent_aggregate_values (struct ipcp_param_lattices *plats)
2716 {
2717 vec<ipa_agg_jf_item, va_gc> *res = NULL;
2718
2719 if (plats->aggs_bottom
2720 || plats->aggs_contain_variable
2721 || plats->aggs_count == 0)
2722 return NULL;
2723
2724 for (struct ipcp_agg_lattice *aglat = plats->aggs;
2725 aglat;
2726 aglat = aglat->next)
2727 if (aglat->is_single_const ())
2728 {
2729 struct ipa_agg_jf_item item;
2730 item.offset = aglat->offset;
2731 item.value = aglat->values->value;
2732 vec_safe_push (res, item);
2733 }
2734 return res;
2735 }
2736
2737 /* Allocate KNOWN_CSTS, KNOWN_CONTEXTS and, if non-NULL, KNOWN_AGGS and
2738 populate them with values of parameters that are known independent of the
2739 context. INFO describes the function. If REMOVABLE_PARAMS_COST is
2740 non-NULL, the movement cost of all removable parameters will be stored in
2741 it. */
2742
2743 static bool
gather_context_independent_values(struct ipa_node_params * info,vec<tree> * known_csts,vec<ipa_polymorphic_call_context> * known_contexts,vec<ipa_agg_jump_function> * known_aggs,int * removable_params_cost)2744 gather_context_independent_values (struct ipa_node_params *info,
2745 vec<tree> *known_csts,
2746 vec<ipa_polymorphic_call_context>
2747 *known_contexts,
2748 vec<ipa_agg_jump_function> *known_aggs,
2749 int *removable_params_cost)
2750 {
2751 int i, count = ipa_get_param_count (info);
2752 bool ret = false;
2753
2754 known_csts->create (0);
2755 known_contexts->create (0);
2756 known_csts->safe_grow_cleared (count);
2757 known_contexts->safe_grow_cleared (count);
2758 if (known_aggs)
2759 {
2760 known_aggs->create (0);
2761 known_aggs->safe_grow_cleared (count);
2762 }
2763
2764 if (removable_params_cost)
2765 *removable_params_cost = 0;
2766
2767 for (i = 0; i < count; i++)
2768 {
2769 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
2770 ipcp_lattice<tree> *lat = &plats->itself;
2771
2772 if (lat->is_single_const ())
2773 {
2774 ipcp_value<tree> *val = lat->values;
2775 gcc_checking_assert (TREE_CODE (val->value) != TREE_BINFO);
2776 (*known_csts)[i] = val->value;
2777 if (removable_params_cost)
2778 *removable_params_cost
2779 += estimate_move_cost (TREE_TYPE (val->value), false);
2780 ret = true;
2781 }
2782 else if (removable_params_cost
2783 && !ipa_is_param_used (info, i))
2784 *removable_params_cost
2785 += ipa_get_param_move_cost (info, i);
2786
2787 if (!ipa_is_param_used (info, i))
2788 continue;
2789
2790 ipcp_lattice<ipa_polymorphic_call_context> *ctxlat = &plats->ctxlat;
2791 /* Do not account known context as reason for cloning. We can see
2792 if it permits devirtualization. */
2793 if (ctxlat->is_single_const ())
2794 (*known_contexts)[i] = ctxlat->values->value;
2795
2796 if (known_aggs)
2797 {
2798 vec<ipa_agg_jf_item, va_gc> *agg_items;
2799 struct ipa_agg_jump_function *ajf;
2800
2801 agg_items = context_independent_aggregate_values (plats);
2802 ajf = &(*known_aggs)[i];
2803 ajf->items = agg_items;
2804 ajf->by_ref = plats->aggs_by_ref;
2805 ret |= agg_items != NULL;
2806 }
2807 }
2808
2809 return ret;
2810 }
2811
2812 /* The current interface in ipa-inline-analysis requires a pointer vector.
2813 Create it.
2814
2815 FIXME: That interface should be re-worked, this is slightly silly. Still,
2816 I'd like to discuss how to change it first and this demonstrates the
2817 issue. */
2818
2819 static vec<ipa_agg_jump_function_p>
agg_jmp_p_vec_for_t_vec(vec<ipa_agg_jump_function> known_aggs)2820 agg_jmp_p_vec_for_t_vec (vec<ipa_agg_jump_function> known_aggs)
2821 {
2822 vec<ipa_agg_jump_function_p> ret;
2823 struct ipa_agg_jump_function *ajf;
2824 int i;
2825
2826 ret.create (known_aggs.length ());
2827 FOR_EACH_VEC_ELT (known_aggs, i, ajf)
2828 ret.quick_push (ajf);
2829 return ret;
2830 }
2831
2832 /* Perform time and size measurement of NODE with the context given in
2833 KNOWN_CSTS, KNOWN_CONTEXTS and KNOWN_AGGS, calculate the benefit and cost
2834 given BASE_TIME of the node without specialization, REMOVABLE_PARAMS_COST of
2835 all context-independent removable parameters and EST_MOVE_COST of estimated
2836 movement of the considered parameter and store it into VAL. */
2837
2838 static void
perform_estimation_of_a_value(cgraph_node * node,vec<tree> known_csts,vec<ipa_polymorphic_call_context> known_contexts,vec<ipa_agg_jump_function_p> known_aggs_ptrs,int removable_params_cost,int est_move_cost,ipcp_value_base * val)2839 perform_estimation_of_a_value (cgraph_node *node, vec<tree> known_csts,
2840 vec<ipa_polymorphic_call_context> known_contexts,
2841 vec<ipa_agg_jump_function_p> known_aggs_ptrs,
2842 int removable_params_cost,
2843 int est_move_cost, ipcp_value_base *val)
2844 {
2845 int size, time_benefit;
2846 sreal time, base_time;
2847 ipa_hints hints;
2848
2849 estimate_ipcp_clone_size_and_time (node, known_csts, known_contexts,
2850 known_aggs_ptrs, &size, &time,
2851 &base_time, &hints);
2852 base_time -= time;
2853 if (base_time > 65535)
2854 base_time = 65535;
2855
2856 /* Extern inline functions have no cloning local time benefits because they
2857 will be inlined anyway. The only reason to clone them is if it enables
2858 optimization in any of the functions they call. */
2859 if (DECL_EXTERNAL (node->decl) && DECL_DECLARED_INLINE_P (node->decl))
2860 time_benefit = 0;
2861 else
2862 time_benefit = base_time.to_int ()
2863 + devirtualization_time_bonus (node, known_csts, known_contexts,
2864 known_aggs_ptrs)
2865 + hint_time_bonus (hints)
2866 + removable_params_cost + est_move_cost;
2867
2868 gcc_checking_assert (size >=0);
2869 /* The inliner-heuristics based estimates may think that in certain
2870 contexts some functions do not have any size at all but we want
2871 all specializations to have at least a tiny cost, not least not to
2872 divide by zero. */
2873 if (size == 0)
2874 size = 1;
2875
2876 val->local_time_benefit = time_benefit;
2877 val->local_size_cost = size;
2878 }
2879
2880 /* Iterate over known values of parameters of NODE and estimate the local
2881 effects in terms of time and size they have. */
2882
2883 static void
estimate_local_effects(struct cgraph_node * node)2884 estimate_local_effects (struct cgraph_node *node)
2885 {
2886 struct ipa_node_params *info = IPA_NODE_REF (node);
2887 int i, count = ipa_get_param_count (info);
2888 vec<tree> known_csts;
2889 vec<ipa_polymorphic_call_context> known_contexts;
2890 vec<ipa_agg_jump_function> known_aggs;
2891 vec<ipa_agg_jump_function_p> known_aggs_ptrs;
2892 bool always_const;
2893 int removable_params_cost;
2894
2895 if (!count || !ipcp_versionable_function_p (node))
2896 return;
2897
2898 if (dump_file && (dump_flags & TDF_DETAILS))
2899 fprintf (dump_file, "\nEstimating effects for %s.\n", node->dump_name ());
2900
2901 always_const = gather_context_independent_values (info, &known_csts,
2902 &known_contexts, &known_aggs,
2903 &removable_params_cost);
2904 known_aggs_ptrs = agg_jmp_p_vec_for_t_vec (known_aggs);
2905 int devirt_bonus = devirtualization_time_bonus (node, known_csts,
2906 known_contexts, known_aggs_ptrs);
2907 if (always_const || devirt_bonus
2908 || (removable_params_cost && node->local.can_change_signature))
2909 {
2910 struct caller_statistics stats;
2911 ipa_hints hints;
2912 sreal time, base_time;
2913 int size;
2914
2915 init_caller_stats (&stats);
2916 node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats,
2917 false);
2918 estimate_ipcp_clone_size_and_time (node, known_csts, known_contexts,
2919 known_aggs_ptrs, &size, &time,
2920 &base_time, &hints);
2921 time -= devirt_bonus;
2922 time -= hint_time_bonus (hints);
2923 time -= removable_params_cost;
2924 size -= stats.n_calls * removable_params_cost;
2925
2926 if (dump_file)
2927 fprintf (dump_file, " - context independent values, size: %i, "
2928 "time_benefit: %f\n", size, (base_time - time).to_double ());
2929
2930 if (size <= 0 || node->local.local)
2931 {
2932 info->do_clone_for_all_contexts = true;
2933
2934 if (dump_file)
2935 fprintf (dump_file, " Decided to specialize for all "
2936 "known contexts, code not going to grow.\n");
2937 }
2938 else if (good_cloning_opportunity_p (node,
2939 MAX ((base_time - time).to_int (),
2940 65536),
2941 stats.freq_sum, stats.count_sum,
2942 size))
2943 {
2944 if (size + overall_size <= max_new_size)
2945 {
2946 info->do_clone_for_all_contexts = true;
2947 overall_size += size;
2948
2949 if (dump_file)
2950 fprintf (dump_file, " Decided to specialize for all "
2951 "known contexts, growth deemed beneficial.\n");
2952 }
2953 else if (dump_file && (dump_flags & TDF_DETAILS))
2954 fprintf (dump_file, " Not cloning for all contexts because "
2955 "max_new_size would be reached with %li.\n",
2956 size + overall_size);
2957 }
2958 else if (dump_file && (dump_flags & TDF_DETAILS))
2959 fprintf (dump_file, " Not cloning for all contexts because "
2960 "!good_cloning_opportunity_p.\n");
2961
2962 }
2963
2964 for (i = 0; i < count; i++)
2965 {
2966 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
2967 ipcp_lattice<tree> *lat = &plats->itself;
2968 ipcp_value<tree> *val;
2969
2970 if (lat->bottom
2971 || !lat->values
2972 || known_csts[i])
2973 continue;
2974
2975 for (val = lat->values; val; val = val->next)
2976 {
2977 gcc_checking_assert (TREE_CODE (val->value) != TREE_BINFO);
2978 known_csts[i] = val->value;
2979
2980 int emc = estimate_move_cost (TREE_TYPE (val->value), true);
2981 perform_estimation_of_a_value (node, known_csts, known_contexts,
2982 known_aggs_ptrs,
2983 removable_params_cost, emc, val);
2984
2985 if (dump_file && (dump_flags & TDF_DETAILS))
2986 {
2987 fprintf (dump_file, " - estimates for value ");
2988 print_ipcp_constant_value (dump_file, val->value);
2989 fprintf (dump_file, " for ");
2990 ipa_dump_param (dump_file, info, i);
2991 fprintf (dump_file, ": time_benefit: %i, size: %i\n",
2992 val->local_time_benefit, val->local_size_cost);
2993 }
2994 }
2995 known_csts[i] = NULL_TREE;
2996 }
2997
2998 for (i = 0; i < count; i++)
2999 {
3000 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
3001
3002 if (!plats->virt_call)
3003 continue;
3004
3005 ipcp_lattice<ipa_polymorphic_call_context> *ctxlat = &plats->ctxlat;
3006 ipcp_value<ipa_polymorphic_call_context> *val;
3007
3008 if (ctxlat->bottom
3009 || !ctxlat->values
3010 || !known_contexts[i].useless_p ())
3011 continue;
3012
3013 for (val = ctxlat->values; val; val = val->next)
3014 {
3015 known_contexts[i] = val->value;
3016 perform_estimation_of_a_value (node, known_csts, known_contexts,
3017 known_aggs_ptrs,
3018 removable_params_cost, 0, val);
3019
3020 if (dump_file && (dump_flags & TDF_DETAILS))
3021 {
3022 fprintf (dump_file, " - estimates for polymorphic context ");
3023 print_ipcp_constant_value (dump_file, val->value);
3024 fprintf (dump_file, " for ");
3025 ipa_dump_param (dump_file, info, i);
3026 fprintf (dump_file, ": time_benefit: %i, size: %i\n",
3027 val->local_time_benefit, val->local_size_cost);
3028 }
3029 }
3030 known_contexts[i] = ipa_polymorphic_call_context ();
3031 }
3032
3033 for (i = 0; i < count; i++)
3034 {
3035 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
3036 struct ipa_agg_jump_function *ajf;
3037 struct ipcp_agg_lattice *aglat;
3038
3039 if (plats->aggs_bottom || !plats->aggs)
3040 continue;
3041
3042 ajf = &known_aggs[i];
3043 for (aglat = plats->aggs; aglat; aglat = aglat->next)
3044 {
3045 ipcp_value<tree> *val;
3046 if (aglat->bottom || !aglat->values
3047 /* If the following is true, the one value is in known_aggs. */
3048 || (!plats->aggs_contain_variable
3049 && aglat->is_single_const ()))
3050 continue;
3051
3052 for (val = aglat->values; val; val = val->next)
3053 {
3054 struct ipa_agg_jf_item item;
3055
3056 item.offset = aglat->offset;
3057 item.value = val->value;
3058 vec_safe_push (ajf->items, item);
3059
3060 perform_estimation_of_a_value (node, known_csts, known_contexts,
3061 known_aggs_ptrs,
3062 removable_params_cost, 0, val);
3063
3064 if (dump_file && (dump_flags & TDF_DETAILS))
3065 {
3066 fprintf (dump_file, " - estimates for value ");
3067 print_ipcp_constant_value (dump_file, val->value);
3068 fprintf (dump_file, " for ");
3069 ipa_dump_param (dump_file, info, i);
3070 fprintf (dump_file, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
3071 "]: time_benefit: %i, size: %i\n",
3072 plats->aggs_by_ref ? "ref " : "",
3073 aglat->offset,
3074 val->local_time_benefit, val->local_size_cost);
3075 }
3076
3077 ajf->items->pop ();
3078 }
3079 }
3080 }
3081
3082 for (i = 0; i < count; i++)
3083 vec_free (known_aggs[i].items);
3084
3085 known_csts.release ();
3086 known_contexts.release ();
3087 known_aggs.release ();
3088 known_aggs_ptrs.release ();
3089 }
3090
3091
3092 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
3093 topological sort of values. */
3094
3095 template <typename valtype>
3096 void
add_val(ipcp_value<valtype> * cur_val)3097 value_topo_info<valtype>::add_val (ipcp_value<valtype> *cur_val)
3098 {
3099 ipcp_value_source<valtype> *src;
3100
3101 if (cur_val->dfs)
3102 return;
3103
3104 dfs_counter++;
3105 cur_val->dfs = dfs_counter;
3106 cur_val->low_link = dfs_counter;
3107
3108 cur_val->topo_next = stack;
3109 stack = cur_val;
3110 cur_val->on_stack = true;
3111
3112 for (src = cur_val->sources; src; src = src->next)
3113 if (src->val)
3114 {
3115 if (src->val->dfs == 0)
3116 {
3117 add_val (src->val);
3118 if (src->val->low_link < cur_val->low_link)
3119 cur_val->low_link = src->val->low_link;
3120 }
3121 else if (src->val->on_stack
3122 && src->val->dfs < cur_val->low_link)
3123 cur_val->low_link = src->val->dfs;
3124 }
3125
3126 if (cur_val->dfs == cur_val->low_link)
3127 {
3128 ipcp_value<valtype> *v, *scc_list = NULL;
3129
3130 do
3131 {
3132 v = stack;
3133 stack = v->topo_next;
3134 v->on_stack = false;
3135
3136 v->scc_next = scc_list;
3137 scc_list = v;
3138 }
3139 while (v != cur_val);
3140
3141 cur_val->topo_next = values_topo;
3142 values_topo = cur_val;
3143 }
3144 }
3145
3146 /* Add all values in lattices associated with NODE to the topological sort if
3147 they are not there yet. */
3148
3149 static void
add_all_node_vals_to_toposort(cgraph_node * node,ipa_topo_info * topo)3150 add_all_node_vals_to_toposort (cgraph_node *node, ipa_topo_info *topo)
3151 {
3152 struct ipa_node_params *info = IPA_NODE_REF (node);
3153 int i, count = ipa_get_param_count (info);
3154
3155 for (i = 0; i < count; i++)
3156 {
3157 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
3158 ipcp_lattice<tree> *lat = &plats->itself;
3159 struct ipcp_agg_lattice *aglat;
3160
3161 if (!lat->bottom)
3162 {
3163 ipcp_value<tree> *val;
3164 for (val = lat->values; val; val = val->next)
3165 topo->constants.add_val (val);
3166 }
3167
3168 if (!plats->aggs_bottom)
3169 for (aglat = plats->aggs; aglat; aglat = aglat->next)
3170 if (!aglat->bottom)
3171 {
3172 ipcp_value<tree> *val;
3173 for (val = aglat->values; val; val = val->next)
3174 topo->constants.add_val (val);
3175 }
3176
3177 ipcp_lattice<ipa_polymorphic_call_context> *ctxlat = &plats->ctxlat;
3178 if (!ctxlat->bottom)
3179 {
3180 ipcp_value<ipa_polymorphic_call_context> *ctxval;
3181 for (ctxval = ctxlat->values; ctxval; ctxval = ctxval->next)
3182 topo->contexts.add_val (ctxval);
3183 }
3184 }
3185 }
3186
3187 /* One pass of constants propagation along the call graph edges, from callers
3188 to callees (requires topological ordering in TOPO), iterate over strongly
3189 connected components. */
3190
3191 static void
propagate_constants_topo(struct ipa_topo_info * topo)3192 propagate_constants_topo (struct ipa_topo_info *topo)
3193 {
3194 int i;
3195
3196 for (i = topo->nnodes - 1; i >= 0; i--)
3197 {
3198 unsigned j;
3199 struct cgraph_node *v, *node = topo->order[i];
3200 vec<cgraph_node *> cycle_nodes = ipa_get_nodes_in_cycle (node);
3201
3202 /* First, iteratively propagate within the strongly connected component
3203 until all lattices stabilize. */
3204 FOR_EACH_VEC_ELT (cycle_nodes, j, v)
3205 if (v->has_gimple_body_p ())
3206 push_node_to_stack (topo, v);
3207
3208 v = pop_node_from_stack (topo);
3209 while (v)
3210 {
3211 struct cgraph_edge *cs;
3212
3213 for (cs = v->callees; cs; cs = cs->next_callee)
3214 if (ipa_edge_within_scc (cs))
3215 {
3216 IPA_NODE_REF (v)->node_within_scc = true;
3217 if (propagate_constants_across_call (cs))
3218 push_node_to_stack (topo, cs->callee->function_symbol ());
3219 }
3220 v = pop_node_from_stack (topo);
3221 }
3222
3223 /* Afterwards, propagate along edges leading out of the SCC, calculates
3224 the local effects of the discovered constants and all valid values to
3225 their topological sort. */
3226 FOR_EACH_VEC_ELT (cycle_nodes, j, v)
3227 if (v->has_gimple_body_p ())
3228 {
3229 struct cgraph_edge *cs;
3230
3231 estimate_local_effects (v);
3232 add_all_node_vals_to_toposort (v, topo);
3233 for (cs = v->callees; cs; cs = cs->next_callee)
3234 if (!ipa_edge_within_scc (cs))
3235 propagate_constants_across_call (cs);
3236 }
3237 cycle_nodes.release ();
3238 }
3239 }
3240
3241
3242 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
3243 the bigger one if otherwise. */
3244
3245 static int
safe_add(int a,int b)3246 safe_add (int a, int b)
3247 {
3248 if (a > INT_MAX/2 || b > INT_MAX/2)
3249 return a > b ? a : b;
3250 else
3251 return a + b;
3252 }
3253
3254
3255 /* Propagate the estimated effects of individual values along the topological
3256 from the dependent values to those they depend on. */
3257
3258 template <typename valtype>
3259 void
propagate_effects()3260 value_topo_info<valtype>::propagate_effects ()
3261 {
3262 ipcp_value<valtype> *base;
3263
3264 for (base = values_topo; base; base = base->topo_next)
3265 {
3266 ipcp_value_source<valtype> *src;
3267 ipcp_value<valtype> *val;
3268 int time = 0, size = 0;
3269
3270 for (val = base; val; val = val->scc_next)
3271 {
3272 time = safe_add (time,
3273 val->local_time_benefit + val->prop_time_benefit);
3274 size = safe_add (size, val->local_size_cost + val->prop_size_cost);
3275 }
3276
3277 for (val = base; val; val = val->scc_next)
3278 for (src = val->sources; src; src = src->next)
3279 if (src->val
3280 && src->cs->maybe_hot_p ())
3281 {
3282 src->val->prop_time_benefit = safe_add (time,
3283 src->val->prop_time_benefit);
3284 src->val->prop_size_cost = safe_add (size,
3285 src->val->prop_size_cost);
3286 }
3287 }
3288 }
3289
3290
3291 /* Propagate constants, polymorphic contexts and their effects from the
3292 summaries interprocedurally. */
3293
3294 static void
ipcp_propagate_stage(struct ipa_topo_info * topo)3295 ipcp_propagate_stage (struct ipa_topo_info *topo)
3296 {
3297 struct cgraph_node *node;
3298
3299 if (dump_file)
3300 fprintf (dump_file, "\n Propagating constants:\n\n");
3301
3302 max_count = profile_count::uninitialized ();
3303
3304 FOR_EACH_DEFINED_FUNCTION (node)
3305 {
3306 struct ipa_node_params *info = IPA_NODE_REF (node);
3307
3308 determine_versionability (node, info);
3309 if (node->has_gimple_body_p ())
3310 {
3311 info->lattices = XCNEWVEC (struct ipcp_param_lattices,
3312 ipa_get_param_count (info));
3313 initialize_node_lattices (node);
3314 }
3315 if (node->definition && !node->alias)
3316 overall_size += ipa_fn_summaries->get (node)->self_size;
3317 max_count = max_count.max (node->count.ipa ());
3318 }
3319
3320 max_new_size = overall_size;
3321 if (max_new_size < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
3322 max_new_size = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
3323 max_new_size += max_new_size * PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH) / 100 + 1;
3324
3325 if (dump_file)
3326 fprintf (dump_file, "\noverall_size: %li, max_new_size: %li\n",
3327 overall_size, max_new_size);
3328
3329 propagate_constants_topo (topo);
3330 if (flag_checking)
3331 ipcp_verify_propagated_values ();
3332 topo->constants.propagate_effects ();
3333 topo->contexts.propagate_effects ();
3334
3335 if (dump_file)
3336 {
3337 fprintf (dump_file, "\nIPA lattices after all propagation:\n");
3338 print_all_lattices (dump_file, (dump_flags & TDF_DETAILS), true);
3339 }
3340 }
3341
3342 /* Discover newly direct outgoing edges from NODE which is a new clone with
3343 known KNOWN_CSTS and make them direct. */
3344
3345 static void
ipcp_discover_new_direct_edges(struct cgraph_node * node,vec<tree> known_csts,vec<ipa_polymorphic_call_context> known_contexts,struct ipa_agg_replacement_value * aggvals)3346 ipcp_discover_new_direct_edges (struct cgraph_node *node,
3347 vec<tree> known_csts,
3348 vec<ipa_polymorphic_call_context>
3349 known_contexts,
3350 struct ipa_agg_replacement_value *aggvals)
3351 {
3352 struct cgraph_edge *ie, *next_ie;
3353 bool found = false;
3354
3355 for (ie = node->indirect_calls; ie; ie = next_ie)
3356 {
3357 tree target;
3358 bool speculative;
3359
3360 next_ie = ie->next_callee;
3361 target = ipa_get_indirect_edge_target_1 (ie, known_csts, known_contexts,
3362 vNULL, aggvals, &speculative);
3363 if (target)
3364 {
3365 bool agg_contents = ie->indirect_info->agg_contents;
3366 bool polymorphic = ie->indirect_info->polymorphic;
3367 int param_index = ie->indirect_info->param_index;
3368 struct cgraph_edge *cs = ipa_make_edge_direct_to_target (ie, target,
3369 speculative);
3370 found = true;
3371
3372 if (cs && !agg_contents && !polymorphic)
3373 {
3374 struct ipa_node_params *info = IPA_NODE_REF (node);
3375 int c = ipa_get_controlled_uses (info, param_index);
3376 if (c != IPA_UNDESCRIBED_USE)
3377 {
3378 struct ipa_ref *to_del;
3379
3380 c--;
3381 ipa_set_controlled_uses (info, param_index, c);
3382 if (dump_file && (dump_flags & TDF_DETAILS))
3383 fprintf (dump_file, " controlled uses count of param "
3384 "%i bumped down to %i\n", param_index, c);
3385 if (c == 0
3386 && (to_del = node->find_reference (cs->callee, NULL, 0)))
3387 {
3388 if (dump_file && (dump_flags & TDF_DETAILS))
3389 fprintf (dump_file, " and even removing its "
3390 "cloning-created reference\n");
3391 to_del->remove_reference ();
3392 }
3393 }
3394 }
3395 }
3396 }
3397 /* Turning calls to direct calls will improve overall summary. */
3398 if (found)
3399 ipa_update_overall_fn_summary (node);
3400 }
3401
3402 /* Vector of pointers which for linked lists of clones of an original crgaph
3403 edge. */
3404
3405 static vec<cgraph_edge *> next_edge_clone;
3406 static vec<cgraph_edge *> prev_edge_clone;
3407
3408 static inline void
grow_edge_clone_vectors(void)3409 grow_edge_clone_vectors (void)
3410 {
3411 if (next_edge_clone.length ()
3412 <= (unsigned) symtab->edges_max_uid)
3413 next_edge_clone.safe_grow_cleared (symtab->edges_max_uid + 1);
3414 if (prev_edge_clone.length ()
3415 <= (unsigned) symtab->edges_max_uid)
3416 prev_edge_clone.safe_grow_cleared (symtab->edges_max_uid + 1);
3417 }
3418
3419 /* Edge duplication hook to grow the appropriate linked list in
3420 next_edge_clone. */
3421
3422 static void
ipcp_edge_duplication_hook(struct cgraph_edge * src,struct cgraph_edge * dst,void *)3423 ipcp_edge_duplication_hook (struct cgraph_edge *src, struct cgraph_edge *dst,
3424 void *)
3425 {
3426 grow_edge_clone_vectors ();
3427
3428 struct cgraph_edge *old_next = next_edge_clone[src->uid];
3429 if (old_next)
3430 prev_edge_clone[old_next->uid] = dst;
3431 prev_edge_clone[dst->uid] = src;
3432
3433 next_edge_clone[dst->uid] = old_next;
3434 next_edge_clone[src->uid] = dst;
3435 }
3436
3437 /* Hook that is called by cgraph.c when an edge is removed. */
3438
3439 static void
ipcp_edge_removal_hook(struct cgraph_edge * cs,void *)3440 ipcp_edge_removal_hook (struct cgraph_edge *cs, void *)
3441 {
3442 grow_edge_clone_vectors ();
3443
3444 struct cgraph_edge *prev = prev_edge_clone[cs->uid];
3445 struct cgraph_edge *next = next_edge_clone[cs->uid];
3446 if (prev)
3447 next_edge_clone[prev->uid] = next;
3448 if (next)
3449 prev_edge_clone[next->uid] = prev;
3450 }
3451
3452 /* See if NODE is a clone with a known aggregate value at a given OFFSET of a
3453 parameter with the given INDEX. */
3454
3455 static tree
get_clone_agg_value(struct cgraph_node * node,HOST_WIDE_INT offset,int index)3456 get_clone_agg_value (struct cgraph_node *node, HOST_WIDE_INT offset,
3457 int index)
3458 {
3459 struct ipa_agg_replacement_value *aggval;
3460
3461 aggval = ipa_get_agg_replacements_for_node (node);
3462 while (aggval)
3463 {
3464 if (aggval->offset == offset
3465 && aggval->index == index)
3466 return aggval->value;
3467 aggval = aggval->next;
3468 }
3469 return NULL_TREE;
3470 }
3471
3472 /* Return true is NODE is DEST or its clone for all contexts. */
3473
3474 static bool
same_node_or_its_all_contexts_clone_p(cgraph_node * node,cgraph_node * dest)3475 same_node_or_its_all_contexts_clone_p (cgraph_node *node, cgraph_node *dest)
3476 {
3477 if (node == dest)
3478 return true;
3479
3480 struct ipa_node_params *info = IPA_NODE_REF (node);
3481 return info->is_all_contexts_clone && info->ipcp_orig_node == dest;
3482 }
3483
3484 /* Return true if edge CS does bring about the value described by SRC to
3485 DEST_VAL of node DEST or its clone for all contexts. */
3486
3487 static bool
cgraph_edge_brings_value_p(cgraph_edge * cs,ipcp_value_source<tree> * src,cgraph_node * dest,ipcp_value<tree> * dest_val)3488 cgraph_edge_brings_value_p (cgraph_edge *cs, ipcp_value_source<tree> *src,
3489 cgraph_node *dest, ipcp_value<tree> *dest_val)
3490 {
3491 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
3492 enum availability availability;
3493 cgraph_node *real_dest = cs->callee->function_symbol (&availability);
3494
3495 if (!same_node_or_its_all_contexts_clone_p (real_dest, dest)
3496 || availability <= AVAIL_INTERPOSABLE
3497 || caller_info->node_dead)
3498 return false;
3499
3500 if (!src->val)
3501 return true;
3502
3503 if (caller_info->ipcp_orig_node)
3504 {
3505 tree t;
3506 if (src->offset == -1)
3507 t = caller_info->known_csts[src->index];
3508 else
3509 t = get_clone_agg_value (cs->caller, src->offset, src->index);
3510 return (t != NULL_TREE
3511 && values_equal_for_ipcp_p (src->val->value, t));
3512 }
3513 else
3514 {
3515 /* At the moment we do not propagate over arithmetic jump functions in
3516 SCCs, so it is safe to detect self-feeding recursive calls in this
3517 way. */
3518 if (src->val == dest_val)
3519 return true;
3520
3521 struct ipcp_agg_lattice *aglat;
3522 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (caller_info,
3523 src->index);
3524 if (src->offset == -1)
3525 return (plats->itself.is_single_const ()
3526 && values_equal_for_ipcp_p (src->val->value,
3527 plats->itself.values->value));
3528 else
3529 {
3530 if (plats->aggs_bottom || plats->aggs_contain_variable)
3531 return false;
3532 for (aglat = plats->aggs; aglat; aglat = aglat->next)
3533 if (aglat->offset == src->offset)
3534 return (aglat->is_single_const ()
3535 && values_equal_for_ipcp_p (src->val->value,
3536 aglat->values->value));
3537 }
3538 return false;
3539 }
3540 }
3541
3542 /* Return true if edge CS does bring about the value described by SRC to
3543 DST_VAL of node DEST or its clone for all contexts. */
3544
3545 static bool
cgraph_edge_brings_value_p(cgraph_edge * cs,ipcp_value_source<ipa_polymorphic_call_context> * src,cgraph_node * dest,ipcp_value<ipa_polymorphic_call_context> *)3546 cgraph_edge_brings_value_p (cgraph_edge *cs,
3547 ipcp_value_source<ipa_polymorphic_call_context> *src,
3548 cgraph_node *dest,
3549 ipcp_value<ipa_polymorphic_call_context> *)
3550 {
3551 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
3552 cgraph_node *real_dest = cs->callee->function_symbol ();
3553
3554 if (!same_node_or_its_all_contexts_clone_p (real_dest, dest)
3555 || caller_info->node_dead)
3556 return false;
3557 if (!src->val)
3558 return true;
3559
3560 if (caller_info->ipcp_orig_node)
3561 return (caller_info->known_contexts.length () > (unsigned) src->index)
3562 && values_equal_for_ipcp_p (src->val->value,
3563 caller_info->known_contexts[src->index]);
3564
3565 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (caller_info,
3566 src->index);
3567 return plats->ctxlat.is_single_const ()
3568 && values_equal_for_ipcp_p (src->val->value,
3569 plats->ctxlat.values->value);
3570 }
3571
3572 /* Get the next clone in the linked list of clones of an edge. */
3573
3574 static inline struct cgraph_edge *
get_next_cgraph_edge_clone(struct cgraph_edge * cs)3575 get_next_cgraph_edge_clone (struct cgraph_edge *cs)
3576 {
3577 return next_edge_clone[cs->uid];
3578 }
3579
3580 /* Given VAL that is intended for DEST, iterate over all its sources and if any
3581 of them is viable and hot, return true. In that case, for those that still
3582 hold, add their edge frequency and their number into *FREQUENCY and
3583 *CALLER_COUNT respectively. */
3584
3585 template <typename valtype>
3586 static bool
get_info_about_necessary_edges(ipcp_value<valtype> * val,cgraph_node * dest,int * freq_sum,profile_count * count_sum,int * caller_count)3587 get_info_about_necessary_edges (ipcp_value<valtype> *val, cgraph_node *dest,
3588 int *freq_sum,
3589 profile_count *count_sum, int *caller_count)
3590 {
3591 ipcp_value_source<valtype> *src;
3592 int freq = 0, count = 0;
3593 profile_count cnt = profile_count::zero ();
3594 bool hot = false;
3595 bool non_self_recursive = false;
3596
3597 for (src = val->sources; src; src = src->next)
3598 {
3599 struct cgraph_edge *cs = src->cs;
3600 while (cs)
3601 {
3602 if (cgraph_edge_brings_value_p (cs, src, dest, val))
3603 {
3604 count++;
3605 freq += cs->frequency ();
3606 if (cs->count.ipa ().initialized_p ())
3607 cnt += cs->count.ipa ();
3608 hot |= cs->maybe_hot_p ();
3609 if (cs->caller != dest)
3610 non_self_recursive = true;
3611 }
3612 cs = get_next_cgraph_edge_clone (cs);
3613 }
3614 }
3615
3616 /* If the only edges bringing a value are self-recursive ones, do not bother
3617 evaluating it. */
3618 if (!non_self_recursive)
3619 return false;
3620
3621 *freq_sum = freq;
3622 *count_sum = cnt;
3623 *caller_count = count;
3624 return hot;
3625 }
3626
3627 /* Return a vector of incoming edges that do bring value VAL to node DEST. It
3628 is assumed their number is known and equal to CALLER_COUNT. */
3629
3630 template <typename valtype>
3631 static vec<cgraph_edge *>
gather_edges_for_value(ipcp_value<valtype> * val,cgraph_node * dest,int caller_count)3632 gather_edges_for_value (ipcp_value<valtype> *val, cgraph_node *dest,
3633 int caller_count)
3634 {
3635 ipcp_value_source<valtype> *src;
3636 vec<cgraph_edge *> ret;
3637
3638 ret.create (caller_count);
3639 for (src = val->sources; src; src = src->next)
3640 {
3641 struct cgraph_edge *cs = src->cs;
3642 while (cs)
3643 {
3644 if (cgraph_edge_brings_value_p (cs, src, dest, val))
3645 ret.quick_push (cs);
3646 cs = get_next_cgraph_edge_clone (cs);
3647 }
3648 }
3649
3650 return ret;
3651 }
3652
3653 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
3654 Return it or NULL if for some reason it cannot be created. */
3655
3656 static struct ipa_replace_map *
get_replacement_map(struct ipa_node_params * info,tree value,int parm_num)3657 get_replacement_map (struct ipa_node_params *info, tree value, int parm_num)
3658 {
3659 struct ipa_replace_map *replace_map;
3660
3661
3662 replace_map = ggc_alloc<ipa_replace_map> ();
3663 if (dump_file)
3664 {
3665 fprintf (dump_file, " replacing ");
3666 ipa_dump_param (dump_file, info, parm_num);
3667
3668 fprintf (dump_file, " with const ");
3669 print_generic_expr (dump_file, value);
3670 fprintf (dump_file, "\n");
3671 }
3672 replace_map->old_tree = NULL;
3673 replace_map->parm_num = parm_num;
3674 replace_map->new_tree = value;
3675 replace_map->replace_p = true;
3676 replace_map->ref_p = false;
3677
3678 return replace_map;
3679 }
3680
3681 /* Dump new profiling counts */
3682
3683 static void
dump_profile_updates(struct cgraph_node * orig_node,struct cgraph_node * new_node)3684 dump_profile_updates (struct cgraph_node *orig_node,
3685 struct cgraph_node *new_node)
3686 {
3687 struct cgraph_edge *cs;
3688
3689 fprintf (dump_file, " setting count of the specialized node to ");
3690 new_node->count.dump (dump_file);
3691 fprintf (dump_file, "\n");
3692 for (cs = new_node->callees; cs; cs = cs->next_callee)
3693 {
3694 fprintf (dump_file, " edge to %s has count ",
3695 cs->callee->name ());
3696 cs->count.dump (dump_file);
3697 fprintf (dump_file, "\n");
3698 }
3699
3700 fprintf (dump_file, " setting count of the original node to ");
3701 orig_node->count.dump (dump_file);
3702 fprintf (dump_file, "\n");
3703 for (cs = orig_node->callees; cs; cs = cs->next_callee)
3704 {
3705 fprintf (dump_file, " edge to %s is left with ",
3706 cs->callee->name ());
3707 cs->count.dump (dump_file);
3708 fprintf (dump_file, "\n");
3709 }
3710 }
3711
3712 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
3713 their profile information to reflect this. */
3714
3715 static void
update_profiling_info(struct cgraph_node * orig_node,struct cgraph_node * new_node)3716 update_profiling_info (struct cgraph_node *orig_node,
3717 struct cgraph_node *new_node)
3718 {
3719 struct cgraph_edge *cs;
3720 struct caller_statistics stats;
3721 profile_count new_sum, orig_sum;
3722 profile_count remainder, orig_node_count = orig_node->count;
3723
3724 if (!(orig_node_count.ipa () > profile_count::zero ()))
3725 return;
3726
3727 init_caller_stats (&stats);
3728 orig_node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats,
3729 false);
3730 orig_sum = stats.count_sum;
3731 init_caller_stats (&stats);
3732 new_node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats,
3733 false);
3734 new_sum = stats.count_sum;
3735
3736 if (orig_node_count < orig_sum + new_sum)
3737 {
3738 if (dump_file)
3739 {
3740 fprintf (dump_file, " Problem: node %s has too low count ",
3741 orig_node->dump_name ());
3742 orig_node_count.dump (dump_file);
3743 fprintf (dump_file, "while the sum of incoming count is ");
3744 (orig_sum + new_sum).dump (dump_file);
3745 fprintf (dump_file, "\n");
3746 }
3747
3748 orig_node_count = (orig_sum + new_sum).apply_scale (12, 10);
3749 if (dump_file)
3750 {
3751 fprintf (dump_file, " proceeding by pretending it was ");
3752 orig_node_count.dump (dump_file);
3753 fprintf (dump_file, "\n");
3754 }
3755 }
3756
3757 remainder = orig_node_count.combine_with_ipa_count (orig_node_count.ipa ()
3758 - new_sum.ipa ());
3759 new_sum = orig_node_count.combine_with_ipa_count (new_sum);
3760 orig_node->count = remainder;
3761
3762 for (cs = new_node->callees; cs; cs = cs->next_callee)
3763 cs->count = cs->count.apply_scale (new_sum, orig_node_count);
3764
3765 for (cs = orig_node->callees; cs; cs = cs->next_callee)
3766 cs->count = cs->count.apply_scale (remainder, orig_node_count);
3767
3768 if (dump_file)
3769 dump_profile_updates (orig_node, new_node);
3770 }
3771
3772 /* Update the respective profile of specialized NEW_NODE and the original
3773 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
3774 have been redirected to the specialized version. */
3775
3776 static void
update_specialized_profile(struct cgraph_node * new_node,struct cgraph_node * orig_node,profile_count redirected_sum)3777 update_specialized_profile (struct cgraph_node *new_node,
3778 struct cgraph_node *orig_node,
3779 profile_count redirected_sum)
3780 {
3781 struct cgraph_edge *cs;
3782 profile_count new_node_count, orig_node_count = orig_node->count;
3783
3784 if (dump_file)
3785 {
3786 fprintf (dump_file, " the sum of counts of redirected edges is ");
3787 redirected_sum.dump (dump_file);
3788 fprintf (dump_file, "\n");
3789 }
3790 if (!(orig_node_count > profile_count::zero ()))
3791 return;
3792
3793 gcc_assert (orig_node_count >= redirected_sum);
3794
3795 new_node_count = new_node->count;
3796 new_node->count += redirected_sum;
3797 orig_node->count -= redirected_sum;
3798
3799 for (cs = new_node->callees; cs; cs = cs->next_callee)
3800 cs->count += cs->count.apply_scale (redirected_sum, new_node_count);
3801
3802 for (cs = orig_node->callees; cs; cs = cs->next_callee)
3803 {
3804 profile_count dec = cs->count.apply_scale (redirected_sum,
3805 orig_node_count);
3806 cs->count -= dec;
3807 }
3808
3809 if (dump_file)
3810 dump_profile_updates (orig_node, new_node);
3811 }
3812
3813 /* Create a specialized version of NODE with known constants in KNOWN_CSTS,
3814 known contexts in KNOWN_CONTEXTS and known aggregate values in AGGVALS and
3815 redirect all edges in CALLERS to it. */
3816
3817 static struct cgraph_node *
create_specialized_node(struct cgraph_node * node,vec<tree> known_csts,vec<ipa_polymorphic_call_context> known_contexts,struct ipa_agg_replacement_value * aggvals,vec<cgraph_edge * > callers)3818 create_specialized_node (struct cgraph_node *node,
3819 vec<tree> known_csts,
3820 vec<ipa_polymorphic_call_context> known_contexts,
3821 struct ipa_agg_replacement_value *aggvals,
3822 vec<cgraph_edge *> callers)
3823 {
3824 struct ipa_node_params *new_info, *info = IPA_NODE_REF (node);
3825 vec<ipa_replace_map *, va_gc> *replace_trees = NULL;
3826 struct ipa_agg_replacement_value *av;
3827 struct cgraph_node *new_node;
3828 int i, count = ipa_get_param_count (info);
3829 bitmap args_to_skip;
3830
3831 gcc_assert (!info->ipcp_orig_node);
3832
3833 if (node->local.can_change_signature)
3834 {
3835 args_to_skip = BITMAP_GGC_ALLOC ();
3836 for (i = 0; i < count; i++)
3837 {
3838 tree t = known_csts[i];
3839
3840 if (t || !ipa_is_param_used (info, i))
3841 bitmap_set_bit (args_to_skip, i);
3842 }
3843 }
3844 else
3845 {
3846 args_to_skip = NULL;
3847 if (dump_file && (dump_flags & TDF_DETAILS))
3848 fprintf (dump_file, " cannot change function signature\n");
3849 }
3850
3851 for (i = 0; i < count; i++)
3852 {
3853 tree t = known_csts[i];
3854 if (t)
3855 {
3856 struct ipa_replace_map *replace_map;
3857
3858 gcc_checking_assert (TREE_CODE (t) != TREE_BINFO);
3859 replace_map = get_replacement_map (info, t, i);
3860 if (replace_map)
3861 vec_safe_push (replace_trees, replace_map);
3862 }
3863 }
3864 auto_vec<cgraph_edge *, 2> self_recursive_calls;
3865 for (i = callers.length () - 1; i >= 0; i--)
3866 {
3867 cgraph_edge *cs = callers[i];
3868 if (cs->caller == node)
3869 {
3870 self_recursive_calls.safe_push (cs);
3871 callers.unordered_remove (i);
3872 }
3873 }
3874
3875 new_node = node->create_virtual_clone (callers, replace_trees,
3876 args_to_skip, "constprop");
3877
3878 bool have_self_recursive_calls = !self_recursive_calls.is_empty ();
3879 for (unsigned j = 0; j < self_recursive_calls.length (); j++)
3880 {
3881 cgraph_edge *cs = next_edge_clone[self_recursive_calls[j]->uid];
3882 /* Cloned edges can disappear during cloning as speculation can be
3883 resolved, check that we have one and that it comes from the last
3884 cloning. */
3885 if (cs && cs->caller == new_node)
3886 cs->redirect_callee_duplicating_thunks (new_node);
3887 /* Any future code that would make more than one clone of an outgoing
3888 edge would confuse this mechanism, so let's check that does not
3889 happen. */
3890 gcc_checking_assert (!cs
3891 || !next_edge_clone[cs->uid]
3892 || next_edge_clone[cs->uid]->caller != new_node);
3893 }
3894 if (have_self_recursive_calls)
3895 new_node->expand_all_artificial_thunks ();
3896
3897 ipa_set_node_agg_value_chain (new_node, aggvals);
3898 for (av = aggvals; av; av = av->next)
3899 new_node->maybe_create_reference (av->value, NULL);
3900
3901 if (dump_file && (dump_flags & TDF_DETAILS))
3902 {
3903 fprintf (dump_file, " the new node is %s.\n", new_node->dump_name ());
3904 if (known_contexts.exists ())
3905 {
3906 for (i = 0; i < count; i++)
3907 if (!known_contexts[i].useless_p ())
3908 {
3909 fprintf (dump_file, " known ctx %i is ", i);
3910 known_contexts[i].dump (dump_file);
3911 }
3912 }
3913 if (aggvals)
3914 ipa_dump_agg_replacement_values (dump_file, aggvals);
3915 }
3916 ipa_check_create_node_params ();
3917 update_profiling_info (node, new_node);
3918 new_info = IPA_NODE_REF (new_node);
3919 new_info->ipcp_orig_node = node;
3920 new_info->known_csts = known_csts;
3921 new_info->known_contexts = known_contexts;
3922
3923 ipcp_discover_new_direct_edges (new_node, known_csts, known_contexts, aggvals);
3924
3925 callers.release ();
3926 return new_node;
3927 }
3928
3929 /* Return true, if JFUNC, which describes a i-th parameter of call CS, is a
3930 simple no-operation pass-through function to itself. */
3931
3932 static bool
self_recursive_pass_through_p(cgraph_edge * cs,ipa_jump_func * jfunc,int i)3933 self_recursive_pass_through_p (cgraph_edge *cs, ipa_jump_func *jfunc, int i)
3934 {
3935 enum availability availability;
3936 if (cs->caller == cs->callee->function_symbol (&availability)
3937 && availability > AVAIL_INTERPOSABLE
3938 && jfunc->type == IPA_JF_PASS_THROUGH
3939 && ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR
3940 && ipa_get_jf_pass_through_formal_id (jfunc) == i)
3941 return true;
3942 return false;
3943 }
3944
3945 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
3946 KNOWN_CSTS with constants that are also known for all of the CALLERS. */
3947
3948 static void
find_more_scalar_values_for_callers_subset(struct cgraph_node * node,vec<tree> known_csts,vec<cgraph_edge * > callers)3949 find_more_scalar_values_for_callers_subset (struct cgraph_node *node,
3950 vec<tree> known_csts,
3951 vec<cgraph_edge *> callers)
3952 {
3953 struct ipa_node_params *info = IPA_NODE_REF (node);
3954 int i, count = ipa_get_param_count (info);
3955
3956 for (i = 0; i < count; i++)
3957 {
3958 struct cgraph_edge *cs;
3959 tree newval = NULL_TREE;
3960 int j;
3961 bool first = true;
3962 tree type = ipa_get_type (info, i);
3963
3964 if (ipa_get_scalar_lat (info, i)->bottom || known_csts[i])
3965 continue;
3966
3967 FOR_EACH_VEC_ELT (callers, j, cs)
3968 {
3969 struct ipa_jump_func *jump_func;
3970 tree t;
3971
3972 if (IPA_NODE_REF (cs->caller)->node_dead)
3973 continue;
3974
3975 if (i >= ipa_get_cs_argument_count (IPA_EDGE_REF (cs))
3976 || (i == 0
3977 && call_passes_through_thunk_p (cs))
3978 || (!cs->callee->instrumentation_clone
3979 && cs->callee->function_symbol ()->instrumentation_clone))
3980 {
3981 newval = NULL_TREE;
3982 break;
3983 }
3984 jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
3985 if (self_recursive_pass_through_p (cs, jump_func, i))
3986 continue;
3987
3988 t = ipa_value_from_jfunc (IPA_NODE_REF (cs->caller), jump_func, type);
3989 if (!t
3990 || (newval
3991 && !values_equal_for_ipcp_p (t, newval))
3992 || (!first && !newval))
3993 {
3994 newval = NULL_TREE;
3995 break;
3996 }
3997 else
3998 newval = t;
3999 first = false;
4000 }
4001
4002 if (newval)
4003 {
4004 if (dump_file && (dump_flags & TDF_DETAILS))
4005 {
4006 fprintf (dump_file, " adding an extra known scalar value ");
4007 print_ipcp_constant_value (dump_file, newval);
4008 fprintf (dump_file, " for ");
4009 ipa_dump_param (dump_file, info, i);
4010 fprintf (dump_file, "\n");
4011 }
4012
4013 known_csts[i] = newval;
4014 }
4015 }
4016 }
4017
4018 /* Given a NODE and a subset of its CALLERS, try to populate plank slots in
4019 KNOWN_CONTEXTS with polymorphic contexts that are also known for all of the
4020 CALLERS. */
4021
4022 static void
find_more_contexts_for_caller_subset(cgraph_node * node,vec<ipa_polymorphic_call_context> * known_contexts,vec<cgraph_edge * > callers)4023 find_more_contexts_for_caller_subset (cgraph_node *node,
4024 vec<ipa_polymorphic_call_context>
4025 *known_contexts,
4026 vec<cgraph_edge *> callers)
4027 {
4028 ipa_node_params *info = IPA_NODE_REF (node);
4029 int i, count = ipa_get_param_count (info);
4030
4031 for (i = 0; i < count; i++)
4032 {
4033 cgraph_edge *cs;
4034
4035 if (ipa_get_poly_ctx_lat (info, i)->bottom
4036 || (known_contexts->exists ()
4037 && !(*known_contexts)[i].useless_p ()))
4038 continue;
4039
4040 ipa_polymorphic_call_context newval;
4041 bool first = true;
4042 int j;
4043
4044 FOR_EACH_VEC_ELT (callers, j, cs)
4045 {
4046 if (i >= ipa_get_cs_argument_count (IPA_EDGE_REF (cs)))
4047 return;
4048 ipa_jump_func *jfunc = ipa_get_ith_jump_func (IPA_EDGE_REF (cs),
4049 i);
4050 ipa_polymorphic_call_context ctx;
4051 ctx = ipa_context_from_jfunc (IPA_NODE_REF (cs->caller), cs, i,
4052 jfunc);
4053 if (first)
4054 {
4055 newval = ctx;
4056 first = false;
4057 }
4058 else
4059 newval.meet_with (ctx);
4060 if (newval.useless_p ())
4061 break;
4062 }
4063
4064 if (!newval.useless_p ())
4065 {
4066 if (dump_file && (dump_flags & TDF_DETAILS))
4067 {
4068 fprintf (dump_file, " adding an extra known polymorphic "
4069 "context ");
4070 print_ipcp_constant_value (dump_file, newval);
4071 fprintf (dump_file, " for ");
4072 ipa_dump_param (dump_file, info, i);
4073 fprintf (dump_file, "\n");
4074 }
4075
4076 if (!known_contexts->exists ())
4077 known_contexts->safe_grow_cleared (ipa_get_param_count (info));
4078 (*known_contexts)[i] = newval;
4079 }
4080
4081 }
4082 }
4083
4084 /* Go through PLATS and create a vector of values consisting of values and
4085 offsets (minus OFFSET) of lattices that contain only a single value. */
4086
4087 static vec<ipa_agg_jf_item>
copy_plats_to_inter(struct ipcp_param_lattices * plats,HOST_WIDE_INT offset)4088 copy_plats_to_inter (struct ipcp_param_lattices *plats, HOST_WIDE_INT offset)
4089 {
4090 vec<ipa_agg_jf_item> res = vNULL;
4091
4092 if (!plats->aggs || plats->aggs_contain_variable || plats->aggs_bottom)
4093 return vNULL;
4094
4095 for (struct ipcp_agg_lattice *aglat = plats->aggs; aglat; aglat = aglat->next)
4096 if (aglat->is_single_const ())
4097 {
4098 struct ipa_agg_jf_item ti;
4099 ti.offset = aglat->offset - offset;
4100 ti.value = aglat->values->value;
4101 res.safe_push (ti);
4102 }
4103 return res;
4104 }
4105
4106 /* Intersect all values in INTER with single value lattices in PLATS (while
4107 subtracting OFFSET). */
4108
4109 static void
intersect_with_plats(struct ipcp_param_lattices * plats,vec<ipa_agg_jf_item> * inter,HOST_WIDE_INT offset)4110 intersect_with_plats (struct ipcp_param_lattices *plats,
4111 vec<ipa_agg_jf_item> *inter,
4112 HOST_WIDE_INT offset)
4113 {
4114 struct ipcp_agg_lattice *aglat;
4115 struct ipa_agg_jf_item *item;
4116 int k;
4117
4118 if (!plats->aggs || plats->aggs_contain_variable || plats->aggs_bottom)
4119 {
4120 inter->release ();
4121 return;
4122 }
4123
4124 aglat = plats->aggs;
4125 FOR_EACH_VEC_ELT (*inter, k, item)
4126 {
4127 bool found = false;
4128 if (!item->value)
4129 continue;
4130 while (aglat)
4131 {
4132 if (aglat->offset - offset > item->offset)
4133 break;
4134 if (aglat->offset - offset == item->offset)
4135 {
4136 gcc_checking_assert (item->value);
4137 if (aglat->is_single_const ()
4138 && values_equal_for_ipcp_p (item->value,
4139 aglat->values->value))
4140 found = true;
4141 break;
4142 }
4143 aglat = aglat->next;
4144 }
4145 if (!found)
4146 item->value = NULL_TREE;
4147 }
4148 }
4149
4150 /* Copy aggregate replacement values of NODE (which is an IPA-CP clone) to the
4151 vector result while subtracting OFFSET from the individual value offsets. */
4152
4153 static vec<ipa_agg_jf_item>
agg_replacements_to_vector(struct cgraph_node * node,int index,HOST_WIDE_INT offset)4154 agg_replacements_to_vector (struct cgraph_node *node, int index,
4155 HOST_WIDE_INT offset)
4156 {
4157 struct ipa_agg_replacement_value *av;
4158 vec<ipa_agg_jf_item> res = vNULL;
4159
4160 for (av = ipa_get_agg_replacements_for_node (node); av; av = av->next)
4161 if (av->index == index
4162 && (av->offset - offset) >= 0)
4163 {
4164 struct ipa_agg_jf_item item;
4165 gcc_checking_assert (av->value);
4166 item.offset = av->offset - offset;
4167 item.value = av->value;
4168 res.safe_push (item);
4169 }
4170
4171 return res;
4172 }
4173
4174 /* Intersect all values in INTER with those that we have already scheduled to
4175 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
4176 (while subtracting OFFSET). */
4177
4178 static void
intersect_with_agg_replacements(struct cgraph_node * node,int index,vec<ipa_agg_jf_item> * inter,HOST_WIDE_INT offset)4179 intersect_with_agg_replacements (struct cgraph_node *node, int index,
4180 vec<ipa_agg_jf_item> *inter,
4181 HOST_WIDE_INT offset)
4182 {
4183 struct ipa_agg_replacement_value *srcvals;
4184 struct ipa_agg_jf_item *item;
4185 int i;
4186
4187 srcvals = ipa_get_agg_replacements_for_node (node);
4188 if (!srcvals)
4189 {
4190 inter->release ();
4191 return;
4192 }
4193
4194 FOR_EACH_VEC_ELT (*inter, i, item)
4195 {
4196 struct ipa_agg_replacement_value *av;
4197 bool found = false;
4198 if (!item->value)
4199 continue;
4200 for (av = srcvals; av; av = av->next)
4201 {
4202 gcc_checking_assert (av->value);
4203 if (av->index == index
4204 && av->offset - offset == item->offset)
4205 {
4206 if (values_equal_for_ipcp_p (item->value, av->value))
4207 found = true;
4208 break;
4209 }
4210 }
4211 if (!found)
4212 item->value = NULL_TREE;
4213 }
4214 }
4215
4216 /* Intersect values in INTER with aggregate values that come along edge CS to
4217 parameter number INDEX and return it. If INTER does not actually exist yet,
4218 copy all incoming values to it. If we determine we ended up with no values
4219 whatsoever, return a released vector. */
4220
4221 static vec<ipa_agg_jf_item>
intersect_aggregates_with_edge(struct cgraph_edge * cs,int index,vec<ipa_agg_jf_item> inter)4222 intersect_aggregates_with_edge (struct cgraph_edge *cs, int index,
4223 vec<ipa_agg_jf_item> inter)
4224 {
4225 struct ipa_jump_func *jfunc;
4226 jfunc = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), index);
4227 if (jfunc->type == IPA_JF_PASS_THROUGH
4228 && ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
4229 {
4230 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
4231 int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
4232
4233 if (caller_info->ipcp_orig_node)
4234 {
4235 struct cgraph_node *orig_node = caller_info->ipcp_orig_node;
4236 struct ipcp_param_lattices *orig_plats;
4237 orig_plats = ipa_get_parm_lattices (IPA_NODE_REF (orig_node),
4238 src_idx);
4239 if (agg_pass_through_permissible_p (orig_plats, jfunc))
4240 {
4241 if (!inter.exists ())
4242 inter = agg_replacements_to_vector (cs->caller, src_idx, 0);
4243 else
4244 intersect_with_agg_replacements (cs->caller, src_idx,
4245 &inter, 0);
4246 }
4247 else
4248 {
4249 inter.release ();
4250 return vNULL;
4251 }
4252 }
4253 else
4254 {
4255 struct ipcp_param_lattices *src_plats;
4256 src_plats = ipa_get_parm_lattices (caller_info, src_idx);
4257 if (agg_pass_through_permissible_p (src_plats, jfunc))
4258 {
4259 /* Currently we do not produce clobber aggregate jump
4260 functions, adjust when we do. */
4261 gcc_checking_assert (!jfunc->agg.items);
4262 if (!inter.exists ())
4263 inter = copy_plats_to_inter (src_plats, 0);
4264 else
4265 intersect_with_plats (src_plats, &inter, 0);
4266 }
4267 else
4268 {
4269 inter.release ();
4270 return vNULL;
4271 }
4272 }
4273 }
4274 else if (jfunc->type == IPA_JF_ANCESTOR
4275 && ipa_get_jf_ancestor_agg_preserved (jfunc))
4276 {
4277 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
4278 int src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
4279 struct ipcp_param_lattices *src_plats;
4280 HOST_WIDE_INT delta = ipa_get_jf_ancestor_offset (jfunc);
4281
4282 if (caller_info->ipcp_orig_node)
4283 {
4284 if (!inter.exists ())
4285 inter = agg_replacements_to_vector (cs->caller, src_idx, delta);
4286 else
4287 intersect_with_agg_replacements (cs->caller, src_idx, &inter,
4288 delta);
4289 }
4290 else
4291 {
4292 src_plats = ipa_get_parm_lattices (caller_info, src_idx);
4293 /* Currently we do not produce clobber aggregate jump
4294 functions, adjust when we do. */
4295 gcc_checking_assert (!src_plats->aggs || !jfunc->agg.items);
4296 if (!inter.exists ())
4297 inter = copy_plats_to_inter (src_plats, delta);
4298 else
4299 intersect_with_plats (src_plats, &inter, delta);
4300 }
4301 }
4302 else if (jfunc->agg.items)
4303 {
4304 struct ipa_agg_jf_item *item;
4305 int k;
4306
4307 if (!inter.exists ())
4308 for (unsigned i = 0; i < jfunc->agg.items->length (); i++)
4309 inter.safe_push ((*jfunc->agg.items)[i]);
4310 else
4311 FOR_EACH_VEC_ELT (inter, k, item)
4312 {
4313 int l = 0;
4314 bool found = false;
4315
4316 if (!item->value)
4317 continue;
4318
4319 while ((unsigned) l < jfunc->agg.items->length ())
4320 {
4321 struct ipa_agg_jf_item *ti;
4322 ti = &(*jfunc->agg.items)[l];
4323 if (ti->offset > item->offset)
4324 break;
4325 if (ti->offset == item->offset)
4326 {
4327 gcc_checking_assert (ti->value);
4328 if (values_equal_for_ipcp_p (item->value,
4329 ti->value))
4330 found = true;
4331 break;
4332 }
4333 l++;
4334 }
4335 if (!found)
4336 item->value = NULL;
4337 }
4338 }
4339 else
4340 {
4341 inter.release ();
4342 return vec<ipa_agg_jf_item>();
4343 }
4344 return inter;
4345 }
4346
4347 /* Look at edges in CALLERS and collect all known aggregate values that arrive
4348 from all of them. */
4349
4350 static struct ipa_agg_replacement_value *
find_aggregate_values_for_callers_subset(struct cgraph_node * node,vec<cgraph_edge * > callers)4351 find_aggregate_values_for_callers_subset (struct cgraph_node *node,
4352 vec<cgraph_edge *> callers)
4353 {
4354 struct ipa_node_params *dest_info = IPA_NODE_REF (node);
4355 struct ipa_agg_replacement_value *res;
4356 struct ipa_agg_replacement_value **tail = &res;
4357 struct cgraph_edge *cs;
4358 int i, j, count = ipa_get_param_count (dest_info);
4359
4360 FOR_EACH_VEC_ELT (callers, j, cs)
4361 {
4362 int c = ipa_get_cs_argument_count (IPA_EDGE_REF (cs));
4363 if (c < count)
4364 count = c;
4365 }
4366
4367 for (i = 0; i < count; i++)
4368 {
4369 struct cgraph_edge *cs;
4370 vec<ipa_agg_jf_item> inter = vNULL;
4371 struct ipa_agg_jf_item *item;
4372 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (dest_info, i);
4373 int j;
4374
4375 /* Among other things, the following check should deal with all by_ref
4376 mismatches. */
4377 if (plats->aggs_bottom)
4378 continue;
4379
4380 FOR_EACH_VEC_ELT (callers, j, cs)
4381 {
4382 struct ipa_jump_func *jfunc
4383 = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
4384 if (self_recursive_pass_through_p (cs, jfunc, i)
4385 && (!plats->aggs_by_ref
4386 || ipa_get_jf_pass_through_agg_preserved (jfunc)))
4387 continue;
4388 inter = intersect_aggregates_with_edge (cs, i, inter);
4389
4390 if (!inter.exists ())
4391 goto next_param;
4392 }
4393
4394 FOR_EACH_VEC_ELT (inter, j, item)
4395 {
4396 struct ipa_agg_replacement_value *v;
4397
4398 if (!item->value)
4399 continue;
4400
4401 v = ggc_alloc<ipa_agg_replacement_value> ();
4402 v->index = i;
4403 v->offset = item->offset;
4404 v->value = item->value;
4405 v->by_ref = plats->aggs_by_ref;
4406 *tail = v;
4407 tail = &v->next;
4408 }
4409
4410 next_param:
4411 if (inter.exists ())
4412 inter.release ();
4413 }
4414 *tail = NULL;
4415 return res;
4416 }
4417
4418 /* Determine whether CS also brings all scalar values that the NODE is
4419 specialized for. */
4420
4421 static bool
cgraph_edge_brings_all_scalars_for_node(struct cgraph_edge * cs,struct cgraph_node * node)4422 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge *cs,
4423 struct cgraph_node *node)
4424 {
4425 struct ipa_node_params *dest_info = IPA_NODE_REF (node);
4426 int count = ipa_get_param_count (dest_info);
4427 struct ipa_node_params *caller_info;
4428 struct ipa_edge_args *args;
4429 int i;
4430
4431 caller_info = IPA_NODE_REF (cs->caller);
4432 args = IPA_EDGE_REF (cs);
4433 for (i = 0; i < count; i++)
4434 {
4435 struct ipa_jump_func *jump_func;
4436 tree val, t;
4437
4438 val = dest_info->known_csts[i];
4439 if (!val)
4440 continue;
4441
4442 if (i >= ipa_get_cs_argument_count (args))
4443 return false;
4444 jump_func = ipa_get_ith_jump_func (args, i);
4445 t = ipa_value_from_jfunc (caller_info, jump_func,
4446 ipa_get_type (dest_info, i));
4447 if (!t || !values_equal_for_ipcp_p (val, t))
4448 return false;
4449 }
4450 return true;
4451 }
4452
4453 /* Determine whether CS also brings all aggregate values that NODE is
4454 specialized for. */
4455 static bool
cgraph_edge_brings_all_agg_vals_for_node(struct cgraph_edge * cs,struct cgraph_node * node)4456 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge *cs,
4457 struct cgraph_node *node)
4458 {
4459 struct ipa_node_params *orig_caller_info = IPA_NODE_REF (cs->caller);
4460 struct ipa_node_params *orig_node_info;
4461 struct ipa_agg_replacement_value *aggval;
4462 int i, ec, count;
4463
4464 aggval = ipa_get_agg_replacements_for_node (node);
4465 if (!aggval)
4466 return true;
4467
4468 count = ipa_get_param_count (IPA_NODE_REF (node));
4469 ec = ipa_get_cs_argument_count (IPA_EDGE_REF (cs));
4470 if (ec < count)
4471 for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next)
4472 if (aggval->index >= ec)
4473 return false;
4474
4475 orig_node_info = IPA_NODE_REF (IPA_NODE_REF (node)->ipcp_orig_node);
4476 if (orig_caller_info->ipcp_orig_node)
4477 orig_caller_info = IPA_NODE_REF (orig_caller_info->ipcp_orig_node);
4478
4479 for (i = 0; i < count; i++)
4480 {
4481 static vec<ipa_agg_jf_item> values = vec<ipa_agg_jf_item>();
4482 struct ipcp_param_lattices *plats;
4483 bool interesting = false;
4484 for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next)
4485 if (aggval->index == i)
4486 {
4487 interesting = true;
4488 break;
4489 }
4490 if (!interesting)
4491 continue;
4492
4493 plats = ipa_get_parm_lattices (orig_node_info, aggval->index);
4494 if (plats->aggs_bottom)
4495 return false;
4496
4497 values = intersect_aggregates_with_edge (cs, i, values);
4498 if (!values.exists ())
4499 return false;
4500
4501 for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next)
4502 if (aggval->index == i)
4503 {
4504 struct ipa_agg_jf_item *item;
4505 int j;
4506 bool found = false;
4507 FOR_EACH_VEC_ELT (values, j, item)
4508 if (item->value
4509 && item->offset == av->offset
4510 && values_equal_for_ipcp_p (item->value, av->value))
4511 {
4512 found = true;
4513 break;
4514 }
4515 if (!found)
4516 {
4517 values.release ();
4518 return false;
4519 }
4520 }
4521 }
4522 return true;
4523 }
4524
4525 /* Given an original NODE and a VAL for which we have already created a
4526 specialized clone, look whether there are incoming edges that still lead
4527 into the old node but now also bring the requested value and also conform to
4528 all other criteria such that they can be redirected the special node.
4529 This function can therefore redirect the final edge in a SCC. */
4530
4531 template <typename valtype>
4532 static void
perhaps_add_new_callers(cgraph_node * node,ipcp_value<valtype> * val)4533 perhaps_add_new_callers (cgraph_node *node, ipcp_value<valtype> *val)
4534 {
4535 ipcp_value_source<valtype> *src;
4536 profile_count redirected_sum = profile_count::zero ();
4537
4538 for (src = val->sources; src; src = src->next)
4539 {
4540 struct cgraph_edge *cs = src->cs;
4541 while (cs)
4542 {
4543 if (cgraph_edge_brings_value_p (cs, src, node, val)
4544 && cgraph_edge_brings_all_scalars_for_node (cs, val->spec_node)
4545 && cgraph_edge_brings_all_agg_vals_for_node (cs, val->spec_node))
4546 {
4547 if (dump_file)
4548 fprintf (dump_file, " - adding an extra caller %s of %s\n",
4549 cs->caller->dump_name (),
4550 val->spec_node->dump_name ());
4551
4552 cs->redirect_callee_duplicating_thunks (val->spec_node);
4553 val->spec_node->expand_all_artificial_thunks ();
4554 if (cs->count.ipa ().initialized_p ())
4555 redirected_sum = redirected_sum + cs->count.ipa ();
4556 }
4557 cs = get_next_cgraph_edge_clone (cs);
4558 }
4559 }
4560
4561 if (redirected_sum.nonzero_p ())
4562 update_specialized_profile (val->spec_node, node, redirected_sum);
4563 }
4564
4565 /* Return true if KNOWN_CONTEXTS contain at least one useful context. */
4566
4567 static bool
known_contexts_useful_p(vec<ipa_polymorphic_call_context> known_contexts)4568 known_contexts_useful_p (vec<ipa_polymorphic_call_context> known_contexts)
4569 {
4570 ipa_polymorphic_call_context *ctx;
4571 int i;
4572
4573 FOR_EACH_VEC_ELT (known_contexts, i, ctx)
4574 if (!ctx->useless_p ())
4575 return true;
4576 return false;
4577 }
4578
4579 /* Return a copy of KNOWN_CSTS if it is not empty, otherwise return vNULL. */
4580
4581 static vec<ipa_polymorphic_call_context>
copy_useful_known_contexts(vec<ipa_polymorphic_call_context> known_contexts)4582 copy_useful_known_contexts (vec<ipa_polymorphic_call_context> known_contexts)
4583 {
4584 if (known_contexts_useful_p (known_contexts))
4585 return known_contexts.copy ();
4586 else
4587 return vNULL;
4588 }
4589
4590 /* Copy KNOWN_CSTS and modify the copy according to VAL and INDEX. If
4591 non-empty, replace KNOWN_CONTEXTS with its copy too. */
4592
4593 static void
modify_known_vectors_with_val(vec<tree> * known_csts,vec<ipa_polymorphic_call_context> * known_contexts,ipcp_value<tree> * val,int index)4594 modify_known_vectors_with_val (vec<tree> *known_csts,
4595 vec<ipa_polymorphic_call_context> *known_contexts,
4596 ipcp_value<tree> *val,
4597 int index)
4598 {
4599 *known_csts = known_csts->copy ();
4600 *known_contexts = copy_useful_known_contexts (*known_contexts);
4601 (*known_csts)[index] = val->value;
4602 }
4603
4604 /* Replace KNOWN_CSTS with its copy. Also copy KNOWN_CONTEXTS and modify the
4605 copy according to VAL and INDEX. */
4606
4607 static void
modify_known_vectors_with_val(vec<tree> * known_csts,vec<ipa_polymorphic_call_context> * known_contexts,ipcp_value<ipa_polymorphic_call_context> * val,int index)4608 modify_known_vectors_with_val (vec<tree> *known_csts,
4609 vec<ipa_polymorphic_call_context> *known_contexts,
4610 ipcp_value<ipa_polymorphic_call_context> *val,
4611 int index)
4612 {
4613 *known_csts = known_csts->copy ();
4614 *known_contexts = known_contexts->copy ();
4615 (*known_contexts)[index] = val->value;
4616 }
4617
4618 /* Return true if OFFSET indicates this was not an aggregate value or there is
4619 a replacement equivalent to VALUE, INDEX and OFFSET among those in the
4620 AGGVALS list. */
4621
4622 DEBUG_FUNCTION bool
ipcp_val_agg_replacement_ok_p(ipa_agg_replacement_value * aggvals,int index,HOST_WIDE_INT offset,tree value)4623 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value *aggvals,
4624 int index, HOST_WIDE_INT offset, tree value)
4625 {
4626 if (offset == -1)
4627 return true;
4628
4629 while (aggvals)
4630 {
4631 if (aggvals->index == index
4632 && aggvals->offset == offset
4633 && values_equal_for_ipcp_p (aggvals->value, value))
4634 return true;
4635 aggvals = aggvals->next;
4636 }
4637 return false;
4638 }
4639
4640 /* Return true if offset is minus one because source of a polymorphic contect
4641 cannot be an aggregate value. */
4642
4643 DEBUG_FUNCTION bool
ipcp_val_agg_replacement_ok_p(ipa_agg_replacement_value *,int,HOST_WIDE_INT offset,ipa_polymorphic_call_context)4644 ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value *,
4645 int , HOST_WIDE_INT offset,
4646 ipa_polymorphic_call_context)
4647 {
4648 return offset == -1;
4649 }
4650
4651 /* Decide wheter to create a special version of NODE for value VAL of parameter
4652 at the given INDEX. If OFFSET is -1, the value is for the parameter itself,
4653 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS,
4654 KNOWN_CONTEXTS and KNOWN_AGGS describe the other already known values. */
4655
4656 template <typename valtype>
4657 static bool
decide_about_value(struct cgraph_node * node,int index,HOST_WIDE_INT offset,ipcp_value<valtype> * val,vec<tree> known_csts,vec<ipa_polymorphic_call_context> known_contexts)4658 decide_about_value (struct cgraph_node *node, int index, HOST_WIDE_INT offset,
4659 ipcp_value<valtype> *val, vec<tree> known_csts,
4660 vec<ipa_polymorphic_call_context> known_contexts)
4661 {
4662 struct ipa_agg_replacement_value *aggvals;
4663 int freq_sum, caller_count;
4664 profile_count count_sum;
4665 vec<cgraph_edge *> callers;
4666
4667 if (val->spec_node)
4668 {
4669 perhaps_add_new_callers (node, val);
4670 return false;
4671 }
4672 else if (val->local_size_cost + overall_size > max_new_size)
4673 {
4674 if (dump_file && (dump_flags & TDF_DETAILS))
4675 fprintf (dump_file, " Ignoring candidate value because "
4676 "max_new_size would be reached with %li.\n",
4677 val->local_size_cost + overall_size);
4678 return false;
4679 }
4680 else if (!get_info_about_necessary_edges (val, node, &freq_sum, &count_sum,
4681 &caller_count))
4682 return false;
4683
4684 if (dump_file && (dump_flags & TDF_DETAILS))
4685 {
4686 fprintf (dump_file, " - considering value ");
4687 print_ipcp_constant_value (dump_file, val->value);
4688 fprintf (dump_file, " for ");
4689 ipa_dump_param (dump_file, IPA_NODE_REF (node), index);
4690 if (offset != -1)
4691 fprintf (dump_file, ", offset: " HOST_WIDE_INT_PRINT_DEC, offset);
4692 fprintf (dump_file, " (caller_count: %i)\n", caller_count);
4693 }
4694
4695 if (!good_cloning_opportunity_p (node, val->local_time_benefit,
4696 freq_sum, count_sum,
4697 val->local_size_cost)
4698 && !good_cloning_opportunity_p (node,
4699 val->local_time_benefit
4700 + val->prop_time_benefit,
4701 freq_sum, count_sum,
4702 val->local_size_cost
4703 + val->prop_size_cost))
4704 return false;
4705
4706 if (dump_file)
4707 fprintf (dump_file, " Creating a specialized node of %s.\n",
4708 node->dump_name ());
4709
4710 callers = gather_edges_for_value (val, node, caller_count);
4711 if (offset == -1)
4712 modify_known_vectors_with_val (&known_csts, &known_contexts, val, index);
4713 else
4714 {
4715 known_csts = known_csts.copy ();
4716 known_contexts = copy_useful_known_contexts (known_contexts);
4717 }
4718 find_more_scalar_values_for_callers_subset (node, known_csts, callers);
4719 find_more_contexts_for_caller_subset (node, &known_contexts, callers);
4720 aggvals = find_aggregate_values_for_callers_subset (node, callers);
4721 gcc_checking_assert (ipcp_val_agg_replacement_ok_p (aggvals, index,
4722 offset, val->value));
4723 val->spec_node = create_specialized_node (node, known_csts, known_contexts,
4724 aggvals, callers);
4725 overall_size += val->local_size_cost;
4726
4727 /* TODO: If for some lattice there is only one other known value
4728 left, make a special node for it too. */
4729
4730 return true;
4731 }
4732
4733 /* Decide whether and what specialized clones of NODE should be created. */
4734
4735 static bool
decide_whether_version_node(struct cgraph_node * node)4736 decide_whether_version_node (struct cgraph_node *node)
4737 {
4738 struct ipa_node_params *info = IPA_NODE_REF (node);
4739 int i, count = ipa_get_param_count (info);
4740 vec<tree> known_csts;
4741 vec<ipa_polymorphic_call_context> known_contexts;
4742 vec<ipa_agg_jump_function> known_aggs = vNULL;
4743 bool ret = false;
4744
4745 if (count == 0)
4746 return false;
4747
4748 if (dump_file && (dump_flags & TDF_DETAILS))
4749 fprintf (dump_file, "\nEvaluating opportunities for %s.\n",
4750 node->dump_name ());
4751
4752 gather_context_independent_values (info, &known_csts, &known_contexts,
4753 info->do_clone_for_all_contexts ? &known_aggs
4754 : NULL, NULL);
4755
4756 for (i = 0; i < count;i++)
4757 {
4758 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
4759 ipcp_lattice<tree> *lat = &plats->itself;
4760 ipcp_lattice<ipa_polymorphic_call_context> *ctxlat = &plats->ctxlat;
4761
4762 if (!lat->bottom
4763 && !known_csts[i])
4764 {
4765 ipcp_value<tree> *val;
4766 for (val = lat->values; val; val = val->next)
4767 ret |= decide_about_value (node, i, -1, val, known_csts,
4768 known_contexts);
4769 }
4770
4771 if (!plats->aggs_bottom)
4772 {
4773 struct ipcp_agg_lattice *aglat;
4774 ipcp_value<tree> *val;
4775 for (aglat = plats->aggs; aglat; aglat = aglat->next)
4776 if (!aglat->bottom && aglat->values
4777 /* If the following is false, the one value is in
4778 known_aggs. */
4779 && (plats->aggs_contain_variable
4780 || !aglat->is_single_const ()))
4781 for (val = aglat->values; val; val = val->next)
4782 ret |= decide_about_value (node, i, aglat->offset, val,
4783 known_csts, known_contexts);
4784 }
4785
4786 if (!ctxlat->bottom
4787 && known_contexts[i].useless_p ())
4788 {
4789 ipcp_value<ipa_polymorphic_call_context> *val;
4790 for (val = ctxlat->values; val; val = val->next)
4791 ret |= decide_about_value (node, i, -1, val, known_csts,
4792 known_contexts);
4793 }
4794
4795 info = IPA_NODE_REF (node);
4796 }
4797
4798 if (info->do_clone_for_all_contexts)
4799 {
4800 struct cgraph_node *clone;
4801 vec<cgraph_edge *> callers;
4802
4803 if (dump_file)
4804 fprintf (dump_file, " - Creating a specialized node of %s "
4805 "for all known contexts.\n", node->dump_name ());
4806
4807 callers = node->collect_callers ();
4808 find_more_scalar_values_for_callers_subset (node, known_csts, callers);
4809 find_more_contexts_for_caller_subset (node, &known_contexts, callers);
4810 ipa_agg_replacement_value *aggvals
4811 = find_aggregate_values_for_callers_subset (node, callers);
4812
4813 if (!known_contexts_useful_p (known_contexts))
4814 {
4815 known_contexts.release ();
4816 known_contexts = vNULL;
4817 }
4818 clone = create_specialized_node (node, known_csts, known_contexts,
4819 aggvals, callers);
4820 info = IPA_NODE_REF (node);
4821 info->do_clone_for_all_contexts = false;
4822 IPA_NODE_REF (clone)->is_all_contexts_clone = true;
4823 for (i = 0; i < count; i++)
4824 vec_free (known_aggs[i].items);
4825 known_aggs.release ();
4826 ret = true;
4827 }
4828 else
4829 {
4830 known_csts.release ();
4831 known_contexts.release ();
4832 }
4833
4834 return ret;
4835 }
4836
4837 /* Transitively mark all callees of NODE within the same SCC as not dead. */
4838
4839 static void
spread_undeadness(struct cgraph_node * node)4840 spread_undeadness (struct cgraph_node *node)
4841 {
4842 struct cgraph_edge *cs;
4843
4844 for (cs = node->callees; cs; cs = cs->next_callee)
4845 if (ipa_edge_within_scc (cs))
4846 {
4847 struct cgraph_node *callee;
4848 struct ipa_node_params *info;
4849
4850 callee = cs->callee->function_symbol (NULL);
4851 info = IPA_NODE_REF (callee);
4852
4853 if (info->node_dead)
4854 {
4855 info->node_dead = 0;
4856 spread_undeadness (callee);
4857 }
4858 }
4859 }
4860
4861 /* Return true if NODE has a caller from outside of its SCC that is not
4862 dead. Worker callback for cgraph_for_node_and_aliases. */
4863
4864 static bool
has_undead_caller_from_outside_scc_p(struct cgraph_node * node,void * data ATTRIBUTE_UNUSED)4865 has_undead_caller_from_outside_scc_p (struct cgraph_node *node,
4866 void *data ATTRIBUTE_UNUSED)
4867 {
4868 struct cgraph_edge *cs;
4869
4870 for (cs = node->callers; cs; cs = cs->next_caller)
4871 if (cs->caller->thunk.thunk_p
4872 && cs->caller->call_for_symbol_thunks_and_aliases
4873 (has_undead_caller_from_outside_scc_p, NULL, true))
4874 return true;
4875 else if (!ipa_edge_within_scc (cs)
4876 && !IPA_NODE_REF (cs->caller)->node_dead)
4877 return true;
4878 return false;
4879 }
4880
4881
4882 /* Identify nodes within the same SCC as NODE which are no longer needed
4883 because of new clones and will be removed as unreachable. */
4884
4885 static void
identify_dead_nodes(struct cgraph_node * node)4886 identify_dead_nodes (struct cgraph_node *node)
4887 {
4888 struct cgraph_node *v;
4889 for (v = node; v; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
4890 if (v->local.local
4891 && !v->call_for_symbol_thunks_and_aliases
4892 (has_undead_caller_from_outside_scc_p, NULL, true))
4893 IPA_NODE_REF (v)->node_dead = 1;
4894
4895 for (v = node; v; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
4896 if (!IPA_NODE_REF (v)->node_dead)
4897 spread_undeadness (v);
4898
4899 if (dump_file && (dump_flags & TDF_DETAILS))
4900 {
4901 for (v = node; v; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
4902 if (IPA_NODE_REF (v)->node_dead)
4903 fprintf (dump_file, " Marking node as dead: %s.\n", v->dump_name ());
4904 }
4905 }
4906
4907 /* The decision stage. Iterate over the topological order of call graph nodes
4908 TOPO and make specialized clones if deemed beneficial. */
4909
4910 static void
ipcp_decision_stage(struct ipa_topo_info * topo)4911 ipcp_decision_stage (struct ipa_topo_info *topo)
4912 {
4913 int i;
4914
4915 if (dump_file)
4916 fprintf (dump_file, "\nIPA decision stage:\n\n");
4917
4918 for (i = topo->nnodes - 1; i >= 0; i--)
4919 {
4920 struct cgraph_node *node = topo->order[i];
4921 bool change = false, iterate = true;
4922
4923 while (iterate)
4924 {
4925 struct cgraph_node *v;
4926 iterate = false;
4927 for (v = node; v; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
4928 if (v->has_gimple_body_p ()
4929 && ipcp_versionable_function_p (v))
4930 iterate |= decide_whether_version_node (v);
4931
4932 change |= iterate;
4933 }
4934 if (change)
4935 identify_dead_nodes (node);
4936 }
4937 }
4938
4939 /* Look up all the bits information that we have discovered and copy it over
4940 to the transformation summary. */
4941
4942 static void
ipcp_store_bits_results(void)4943 ipcp_store_bits_results (void)
4944 {
4945 cgraph_node *node;
4946
4947 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
4948 {
4949 ipa_node_params *info = IPA_NODE_REF (node);
4950 bool dumped_sth = false;
4951 bool found_useful_result = false;
4952
4953 if (!opt_for_fn (node->decl, flag_ipa_bit_cp))
4954 {
4955 if (dump_file)
4956 fprintf (dump_file, "Not considering %s for ipa bitwise propagation "
4957 "; -fipa-bit-cp: disabled.\n",
4958 node->name ());
4959 continue;
4960 }
4961
4962 if (info->ipcp_orig_node)
4963 info = IPA_NODE_REF (info->ipcp_orig_node);
4964
4965 unsigned count = ipa_get_param_count (info);
4966 for (unsigned i = 0; i < count; i++)
4967 {
4968 ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
4969 if (plats->bits_lattice.constant_p ())
4970 {
4971 found_useful_result = true;
4972 break;
4973 }
4974 }
4975
4976 if (!found_useful_result)
4977 continue;
4978
4979 ipcp_grow_transformations_if_necessary ();
4980 ipcp_transformation_summary *ts = ipcp_get_transformation_summary (node);
4981 vec_safe_reserve_exact (ts->bits, count);
4982
4983 for (unsigned i = 0; i < count; i++)
4984 {
4985 ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
4986 ipa_bits *jfbits;
4987
4988 if (plats->bits_lattice.constant_p ())
4989 jfbits
4990 = ipa_get_ipa_bits_for_value (plats->bits_lattice.get_value (),
4991 plats->bits_lattice.get_mask ());
4992 else
4993 jfbits = NULL;
4994
4995 ts->bits->quick_push (jfbits);
4996 if (!dump_file || !jfbits)
4997 continue;
4998 if (!dumped_sth)
4999 {
5000 fprintf (dump_file, "Propagated bits info for function %s:\n",
5001 node->dump_name ());
5002 dumped_sth = true;
5003 }
5004 fprintf (dump_file, " param %i: value = ", i);
5005 print_hex (jfbits->value, dump_file);
5006 fprintf (dump_file, ", mask = ");
5007 print_hex (jfbits->mask, dump_file);
5008 fprintf (dump_file, "\n");
5009 }
5010 }
5011 }
5012
5013 /* Look up all VR information that we have discovered and copy it over
5014 to the transformation summary. */
5015
5016 static void
ipcp_store_vr_results(void)5017 ipcp_store_vr_results (void)
5018 {
5019 cgraph_node *node;
5020
5021 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
5022 {
5023 ipa_node_params *info = IPA_NODE_REF (node);
5024 bool found_useful_result = false;
5025
5026 if (!opt_for_fn (node->decl, flag_ipa_vrp))
5027 {
5028 if (dump_file)
5029 fprintf (dump_file, "Not considering %s for VR discovery "
5030 "and propagate; -fipa-ipa-vrp: disabled.\n",
5031 node->name ());
5032 continue;
5033 }
5034
5035 if (info->ipcp_orig_node)
5036 info = IPA_NODE_REF (info->ipcp_orig_node);
5037
5038 unsigned count = ipa_get_param_count (info);
5039 for (unsigned i = 0; i < count; i++)
5040 {
5041 ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
5042 if (!plats->m_value_range.bottom_p ()
5043 && !plats->m_value_range.top_p ())
5044 {
5045 found_useful_result = true;
5046 break;
5047 }
5048 }
5049 if (!found_useful_result)
5050 continue;
5051
5052 ipcp_grow_transformations_if_necessary ();
5053 ipcp_transformation_summary *ts = ipcp_get_transformation_summary (node);
5054 vec_safe_reserve_exact (ts->m_vr, count);
5055
5056 for (unsigned i = 0; i < count; i++)
5057 {
5058 ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
5059 ipa_vr vr;
5060
5061 if (!plats->m_value_range.bottom_p ()
5062 && !plats->m_value_range.top_p ())
5063 {
5064 vr.known = true;
5065 vr.type = plats->m_value_range.m_vr.type;
5066 vr.min = wi::to_wide (plats->m_value_range.m_vr.min);
5067 vr.max = wi::to_wide (plats->m_value_range.m_vr.max);
5068 }
5069 else
5070 {
5071 vr.known = false;
5072 vr.type = VR_VARYING;
5073 vr.min = vr.max = wi::zero (INT_TYPE_SIZE);
5074 }
5075 ts->m_vr->quick_push (vr);
5076 }
5077 }
5078 }
5079
5080 /* The IPCP driver. */
5081
5082 static unsigned int
ipcp_driver(void)5083 ipcp_driver (void)
5084 {
5085 struct cgraph_2edge_hook_list *edge_duplication_hook_holder;
5086 struct cgraph_edge_hook_list *edge_removal_hook_holder;
5087 struct ipa_topo_info topo;
5088
5089 ipa_check_create_node_params ();
5090 ipa_check_create_edge_args ();
5091 grow_edge_clone_vectors ();
5092 edge_duplication_hook_holder
5093 = symtab->add_edge_duplication_hook (&ipcp_edge_duplication_hook, NULL);
5094 edge_removal_hook_holder
5095 = symtab->add_edge_removal_hook (&ipcp_edge_removal_hook, NULL);
5096
5097 if (dump_file)
5098 {
5099 fprintf (dump_file, "\nIPA structures before propagation:\n");
5100 if (dump_flags & TDF_DETAILS)
5101 ipa_print_all_params (dump_file);
5102 ipa_print_all_jump_functions (dump_file);
5103 }
5104
5105 /* Topological sort. */
5106 build_toporder_info (&topo);
5107 /* Do the interprocedural propagation. */
5108 ipcp_propagate_stage (&topo);
5109 /* Decide what constant propagation and cloning should be performed. */
5110 ipcp_decision_stage (&topo);
5111 /* Store results of bits propagation. */
5112 ipcp_store_bits_results ();
5113 /* Store results of value range propagation. */
5114 ipcp_store_vr_results ();
5115
5116 /* Free all IPCP structures. */
5117 free_toporder_info (&topo);
5118 next_edge_clone.release ();
5119 prev_edge_clone.release ();
5120 symtab->remove_edge_removal_hook (edge_removal_hook_holder);
5121 symtab->remove_edge_duplication_hook (edge_duplication_hook_holder);
5122 ipa_free_all_structures_after_ipa_cp ();
5123 if (dump_file)
5124 fprintf (dump_file, "\nIPA constant propagation end\n");
5125 return 0;
5126 }
5127
5128 /* Initialization and computation of IPCP data structures. This is the initial
5129 intraprocedural analysis of functions, which gathers information to be
5130 propagated later on. */
5131
5132 static void
ipcp_generate_summary(void)5133 ipcp_generate_summary (void)
5134 {
5135 struct cgraph_node *node;
5136
5137 if (dump_file)
5138 fprintf (dump_file, "\nIPA constant propagation start:\n");
5139 ipa_register_cgraph_hooks ();
5140
5141 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
5142 ipa_analyze_node (node);
5143 }
5144
5145 /* Write ipcp summary for nodes in SET. */
5146
5147 static void
ipcp_write_summary(void)5148 ipcp_write_summary (void)
5149 {
5150 ipa_prop_write_jump_functions ();
5151 }
5152
5153 /* Read ipcp summary. */
5154
5155 static void
ipcp_read_summary(void)5156 ipcp_read_summary (void)
5157 {
5158 ipa_prop_read_jump_functions ();
5159 }
5160
5161 namespace {
5162
5163 const pass_data pass_data_ipa_cp =
5164 {
5165 IPA_PASS, /* type */
5166 "cp", /* name */
5167 OPTGROUP_NONE, /* optinfo_flags */
5168 TV_IPA_CONSTANT_PROP, /* tv_id */
5169 0, /* properties_required */
5170 0, /* properties_provided */
5171 0, /* properties_destroyed */
5172 0, /* todo_flags_start */
5173 ( TODO_dump_symtab | TODO_remove_functions ), /* todo_flags_finish */
5174 };
5175
5176 class pass_ipa_cp : public ipa_opt_pass_d
5177 {
5178 public:
pass_ipa_cp(gcc::context * ctxt)5179 pass_ipa_cp (gcc::context *ctxt)
5180 : ipa_opt_pass_d (pass_data_ipa_cp, ctxt,
5181 ipcp_generate_summary, /* generate_summary */
5182 ipcp_write_summary, /* write_summary */
5183 ipcp_read_summary, /* read_summary */
5184 ipcp_write_transformation_summaries, /*
5185 write_optimization_summary */
5186 ipcp_read_transformation_summaries, /*
5187 read_optimization_summary */
5188 NULL, /* stmt_fixup */
5189 0, /* function_transform_todo_flags_start */
5190 ipcp_transform_function, /* function_transform */
5191 NULL) /* variable_transform */
5192 {}
5193
5194 /* opt_pass methods: */
gate(function *)5195 virtual bool gate (function *)
5196 {
5197 /* FIXME: We should remove the optimize check after we ensure we never run
5198 IPA passes when not optimizing. */
5199 return (flag_ipa_cp && optimize) || in_lto_p;
5200 }
5201
execute(function *)5202 virtual unsigned int execute (function *) { return ipcp_driver (); }
5203
5204 }; // class pass_ipa_cp
5205
5206 } // anon namespace
5207
5208 ipa_opt_pass_d *
make_pass_ipa_cp(gcc::context * ctxt)5209 make_pass_ipa_cp (gcc::context *ctxt)
5210 {
5211 return new pass_ipa_cp (ctxt);
5212 }
5213
5214 /* Reset all state within ipa-cp.c so that we can rerun the compiler
5215 within the same process. For use by toplev::finalize. */
5216
5217 void
ipa_cp_c_finalize(void)5218 ipa_cp_c_finalize (void)
5219 {
5220 max_count = profile_count::uninitialized ();
5221 overall_size = 0;
5222 max_new_size = 0;
5223 }
5224