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 widest_int o_value, o_mask;
1086 get_value_and_mask (operand, &o_value, &o_mask);
1087
1088 bit_value_binop (code, sgn, precision, &adjusted_value, &adjusted_mask,
1089 sgn, precision, other.get_value (), other.get_mask (),
1090 TYPE_SIGN (type), TYPE_PRECISION (type), o_value, o_mask);
1091
1092 if (wi::sext (adjusted_mask, precision) == -1)
1093 return set_to_bottom ();
1094 }
1095
1096 else if (TREE_CODE_CLASS (code) == tcc_unary)
1097 {
1098 bit_value_unop (code, sgn, precision, &adjusted_value,
1099 &adjusted_mask, sgn, precision, other.get_value (),
1100 other.get_mask ());
1101
1102 if (wi::sext (adjusted_mask, precision) == -1)
1103 return set_to_bottom ();
1104 }
1105
1106 else
1107 return set_to_bottom ();
1108
1109 if (top_p ())
1110 {
1111 if (wi::sext (adjusted_mask, precision) == -1)
1112 return set_to_bottom ();
1113 return set_to_constant (adjusted_value, adjusted_mask);
1114 }
1115 else
1116 return meet_with_1 (adjusted_value, adjusted_mask, precision);
1117 }
1118
1119 /* Mark bot aggregate and scalar lattices as containing an unknown variable,
1120 return true is any of them has not been marked as such so far. */
1121
1122 static inline bool
set_all_contains_variable(struct ipcp_param_lattices * plats)1123 set_all_contains_variable (struct ipcp_param_lattices *plats)
1124 {
1125 bool ret;
1126 ret = plats->itself.set_contains_variable ();
1127 ret |= plats->ctxlat.set_contains_variable ();
1128 ret |= set_agg_lats_contain_variable (plats);
1129 ret |= plats->bits_lattice.set_to_bottom ();
1130 ret |= plats->m_value_range.set_to_bottom ();
1131 return ret;
1132 }
1133
1134 /* Worker of call_for_symbol_thunks_and_aliases, increment the integer DATA
1135 points to by the number of callers to NODE. */
1136
1137 static bool
count_callers(cgraph_node * node,void * data)1138 count_callers (cgraph_node *node, void *data)
1139 {
1140 int *caller_count = (int *) data;
1141
1142 for (cgraph_edge *cs = node->callers; cs; cs = cs->next_caller)
1143 /* Local thunks can be handled transparently, but if the thunk can not
1144 be optimized out, count it as a real use. */
1145 if (!cs->caller->thunk.thunk_p || !cs->caller->local.local)
1146 ++*caller_count;
1147 return false;
1148 }
1149
1150 /* Worker of call_for_symbol_thunks_and_aliases, it is supposed to be called on
1151 the one caller of some other node. Set the caller's corresponding flag. */
1152
1153 static bool
set_single_call_flag(cgraph_node * node,void *)1154 set_single_call_flag (cgraph_node *node, void *)
1155 {
1156 cgraph_edge *cs = node->callers;
1157 /* Local thunks can be handled transparently, skip them. */
1158 while (cs && cs->caller->thunk.thunk_p && cs->caller->local.local)
1159 cs = cs->next_caller;
1160 if (cs)
1161 {
1162 IPA_NODE_REF (cs->caller)->node_calling_single_call = true;
1163 return true;
1164 }
1165 return false;
1166 }
1167
1168 /* Initialize ipcp_lattices. */
1169
1170 static void
initialize_node_lattices(struct cgraph_node * node)1171 initialize_node_lattices (struct cgraph_node *node)
1172 {
1173 struct ipa_node_params *info = IPA_NODE_REF (node);
1174 struct cgraph_edge *ie;
1175 bool disable = false, variable = false;
1176 int i;
1177
1178 gcc_checking_assert (node->has_gimple_body_p ());
1179 if (cgraph_local_p (node))
1180 {
1181 int caller_count = 0;
1182 node->call_for_symbol_thunks_and_aliases (count_callers, &caller_count,
1183 true);
1184 gcc_checking_assert (caller_count > 0);
1185 if (caller_count == 1)
1186 node->call_for_symbol_thunks_and_aliases (set_single_call_flag,
1187 NULL, true);
1188 }
1189 else
1190 {
1191 /* When cloning is allowed, we can assume that externally visible
1192 functions are not called. We will compensate this by cloning
1193 later. */
1194 if (ipcp_versionable_function_p (node)
1195 && ipcp_cloning_candidate_p (node))
1196 variable = true;
1197 else
1198 disable = true;
1199 }
1200
1201 for (i = 0; i < ipa_get_param_count (info); i++)
1202 {
1203 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
1204 plats->m_value_range.init ();
1205 }
1206
1207 if (disable || variable)
1208 {
1209 for (i = 0; i < ipa_get_param_count (info); i++)
1210 {
1211 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
1212 if (disable)
1213 {
1214 plats->itself.set_to_bottom ();
1215 plats->ctxlat.set_to_bottom ();
1216 set_agg_lats_to_bottom (plats);
1217 plats->bits_lattice.set_to_bottom ();
1218 plats->m_value_range.set_to_bottom ();
1219 }
1220 else
1221 set_all_contains_variable (plats);
1222 }
1223 if (dump_file && (dump_flags & TDF_DETAILS)
1224 && !node->alias && !node->thunk.thunk_p)
1225 fprintf (dump_file, "Marking all lattices of %s as %s\n",
1226 node->dump_name (), disable ? "BOTTOM" : "VARIABLE");
1227 }
1228
1229 for (ie = node->indirect_calls; ie; ie = ie->next_callee)
1230 if (ie->indirect_info->polymorphic
1231 && ie->indirect_info->param_index >= 0)
1232 {
1233 gcc_checking_assert (ie->indirect_info->param_index >= 0);
1234 ipa_get_parm_lattices (info,
1235 ie->indirect_info->param_index)->virt_call = 1;
1236 }
1237 }
1238
1239 /* Return the result of a (possibly arithmetic) pass through jump function
1240 JFUNC on the constant value INPUT. RES_TYPE is the type of the parameter
1241 to which the result is passed. Return NULL_TREE if that cannot be
1242 determined or be considered an interprocedural invariant. */
1243
1244 static tree
ipa_get_jf_pass_through_result(struct ipa_jump_func * jfunc,tree input,tree res_type)1245 ipa_get_jf_pass_through_result (struct ipa_jump_func *jfunc, tree input,
1246 tree res_type)
1247 {
1248 tree res;
1249
1250 if (ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
1251 return input;
1252 if (!is_gimple_ip_invariant (input))
1253 return NULL_TREE;
1254
1255 tree_code opcode = ipa_get_jf_pass_through_operation (jfunc);
1256 if (!res_type)
1257 {
1258 if (TREE_CODE_CLASS (opcode) == tcc_comparison)
1259 res_type = boolean_type_node;
1260 else if (expr_type_first_operand_type_p (opcode))
1261 res_type = TREE_TYPE (input);
1262 else
1263 return NULL_TREE;
1264 }
1265
1266 if (TREE_CODE_CLASS (opcode) == tcc_unary)
1267 res = fold_unary (opcode, res_type, input);
1268 else
1269 res = fold_binary (opcode, res_type, input,
1270 ipa_get_jf_pass_through_operand (jfunc));
1271
1272 if (res && !is_gimple_ip_invariant (res))
1273 return NULL_TREE;
1274
1275 return res;
1276 }
1277
1278 /* Return the result of an ancestor jump function JFUNC on the constant value
1279 INPUT. Return NULL_TREE if that cannot be determined. */
1280
1281 static tree
ipa_get_jf_ancestor_result(struct ipa_jump_func * jfunc,tree input)1282 ipa_get_jf_ancestor_result (struct ipa_jump_func *jfunc, tree input)
1283 {
1284 gcc_checking_assert (TREE_CODE (input) != TREE_BINFO);
1285 if (TREE_CODE (input) == ADDR_EXPR)
1286 {
1287 tree t = TREE_OPERAND (input, 0);
1288 t = build_ref_for_offset (EXPR_LOCATION (t), t,
1289 ipa_get_jf_ancestor_offset (jfunc), false,
1290 ptr_type_node, NULL, false);
1291 return build_fold_addr_expr (t);
1292 }
1293 else
1294 return NULL_TREE;
1295 }
1296
1297 /* Determine whether JFUNC evaluates to a single known constant value and if
1298 so, return it. Otherwise return NULL. INFO describes the caller node or
1299 the one it is inlined to, so that pass-through jump functions can be
1300 evaluated. PARM_TYPE is the type of the parameter to which the result is
1301 passed. */
1302
1303 tree
ipa_value_from_jfunc(struct ipa_node_params * info,struct ipa_jump_func * jfunc,tree parm_type)1304 ipa_value_from_jfunc (struct ipa_node_params *info, struct ipa_jump_func *jfunc,
1305 tree parm_type)
1306 {
1307 if (jfunc->type == IPA_JF_CONST)
1308 return ipa_get_jf_constant (jfunc);
1309 else if (jfunc->type == IPA_JF_PASS_THROUGH
1310 || jfunc->type == IPA_JF_ANCESTOR)
1311 {
1312 tree input;
1313 int idx;
1314
1315 if (jfunc->type == IPA_JF_PASS_THROUGH)
1316 idx = ipa_get_jf_pass_through_formal_id (jfunc);
1317 else
1318 idx = ipa_get_jf_ancestor_formal_id (jfunc);
1319
1320 if (info->ipcp_orig_node)
1321 input = info->known_csts[idx];
1322 else
1323 {
1324 ipcp_lattice<tree> *lat;
1325
1326 if (!info->lattices
1327 || idx >= ipa_get_param_count (info))
1328 return NULL_TREE;
1329 lat = ipa_get_scalar_lat (info, idx);
1330 if (!lat->is_single_const ())
1331 return NULL_TREE;
1332 input = lat->values->value;
1333 }
1334
1335 if (!input)
1336 return NULL_TREE;
1337
1338 if (jfunc->type == IPA_JF_PASS_THROUGH)
1339 return ipa_get_jf_pass_through_result (jfunc, input, parm_type);
1340 else
1341 return ipa_get_jf_ancestor_result (jfunc, input);
1342 }
1343 else
1344 return NULL_TREE;
1345 }
1346
1347 /* Determie whether JFUNC evaluates to single known polymorphic context, given
1348 that INFO describes the caller node or the one it is inlined to, CS is the
1349 call graph edge corresponding to JFUNC and CSIDX index of the described
1350 parameter. */
1351
1352 ipa_polymorphic_call_context
ipa_context_from_jfunc(ipa_node_params * info,cgraph_edge * cs,int csidx,ipa_jump_func * jfunc)1353 ipa_context_from_jfunc (ipa_node_params *info, cgraph_edge *cs, int csidx,
1354 ipa_jump_func *jfunc)
1355 {
1356 ipa_edge_args *args = IPA_EDGE_REF (cs);
1357 ipa_polymorphic_call_context ctx;
1358 ipa_polymorphic_call_context *edge_ctx
1359 = cs ? ipa_get_ith_polymorhic_call_context (args, csidx) : NULL;
1360
1361 if (edge_ctx && !edge_ctx->useless_p ())
1362 ctx = *edge_ctx;
1363
1364 if (jfunc->type == IPA_JF_PASS_THROUGH
1365 || jfunc->type == IPA_JF_ANCESTOR)
1366 {
1367 ipa_polymorphic_call_context srcctx;
1368 int srcidx;
1369 bool type_preserved = true;
1370 if (jfunc->type == IPA_JF_PASS_THROUGH)
1371 {
1372 if (ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR)
1373 return ctx;
1374 type_preserved = ipa_get_jf_pass_through_type_preserved (jfunc);
1375 srcidx = ipa_get_jf_pass_through_formal_id (jfunc);
1376 }
1377 else
1378 {
1379 type_preserved = ipa_get_jf_ancestor_type_preserved (jfunc);
1380 srcidx = ipa_get_jf_ancestor_formal_id (jfunc);
1381 }
1382 if (info->ipcp_orig_node)
1383 {
1384 if (info->known_contexts.exists ())
1385 srcctx = info->known_contexts[srcidx];
1386 }
1387 else
1388 {
1389 if (!info->lattices
1390 || srcidx >= ipa_get_param_count (info))
1391 return ctx;
1392 ipcp_lattice<ipa_polymorphic_call_context> *lat;
1393 lat = ipa_get_poly_ctx_lat (info, srcidx);
1394 if (!lat->is_single_const ())
1395 return ctx;
1396 srcctx = lat->values->value;
1397 }
1398 if (srcctx.useless_p ())
1399 return ctx;
1400 if (jfunc->type == IPA_JF_ANCESTOR)
1401 srcctx.offset_by (ipa_get_jf_ancestor_offset (jfunc));
1402 if (!type_preserved)
1403 srcctx.possible_dynamic_type_change (cs->in_polymorphic_cdtor);
1404 srcctx.combine_with (ctx);
1405 return srcctx;
1406 }
1407
1408 return ctx;
1409 }
1410
1411 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
1412 bottom, not containing a variable component and without any known value at
1413 the same time. */
1414
1415 DEBUG_FUNCTION void
ipcp_verify_propagated_values(void)1416 ipcp_verify_propagated_values (void)
1417 {
1418 struct cgraph_node *node;
1419
1420 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
1421 {
1422 struct ipa_node_params *info = IPA_NODE_REF (node);
1423 int i, count = ipa_get_param_count (info);
1424
1425 for (i = 0; i < count; i++)
1426 {
1427 ipcp_lattice<tree> *lat = ipa_get_scalar_lat (info, i);
1428
1429 if (!lat->bottom
1430 && !lat->contains_variable
1431 && lat->values_count == 0)
1432 {
1433 if (dump_file)
1434 {
1435 symtab->dump (dump_file);
1436 fprintf (dump_file, "\nIPA lattices after constant "
1437 "propagation, before gcc_unreachable:\n");
1438 print_all_lattices (dump_file, true, false);
1439 }
1440
1441 gcc_unreachable ();
1442 }
1443 }
1444 }
1445 }
1446
1447 /* Return true iff X and Y should be considered equal values by IPA-CP. */
1448
1449 static bool
values_equal_for_ipcp_p(tree x,tree y)1450 values_equal_for_ipcp_p (tree x, tree y)
1451 {
1452 gcc_checking_assert (x != NULL_TREE && y != NULL_TREE);
1453
1454 if (x == y)
1455 return true;
1456
1457 if (TREE_CODE (x) == ADDR_EXPR
1458 && TREE_CODE (y) == ADDR_EXPR
1459 && TREE_CODE (TREE_OPERAND (x, 0)) == CONST_DECL
1460 && TREE_CODE (TREE_OPERAND (y, 0)) == CONST_DECL)
1461 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x, 0)),
1462 DECL_INITIAL (TREE_OPERAND (y, 0)), 0);
1463 else
1464 return operand_equal_p (x, y, 0);
1465 }
1466
1467 /* Return true iff X and Y should be considered equal contexts by IPA-CP. */
1468
1469 static bool
values_equal_for_ipcp_p(ipa_polymorphic_call_context x,ipa_polymorphic_call_context y)1470 values_equal_for_ipcp_p (ipa_polymorphic_call_context x,
1471 ipa_polymorphic_call_context y)
1472 {
1473 return x.equal_to (y);
1474 }
1475
1476
1477 /* Add a new value source to the value represented by THIS, marking that a
1478 value comes from edge CS and (if the underlying jump function is a
1479 pass-through or an ancestor one) from a caller value SRC_VAL of a caller
1480 parameter described by SRC_INDEX. OFFSET is negative if the source was the
1481 scalar value of the parameter itself or the offset within an aggregate. */
1482
1483 template <typename valtype>
1484 void
add_source(cgraph_edge * cs,ipcp_value * src_val,int src_idx,HOST_WIDE_INT offset)1485 ipcp_value<valtype>::add_source (cgraph_edge *cs, ipcp_value *src_val,
1486 int src_idx, HOST_WIDE_INT offset)
1487 {
1488 ipcp_value_source<valtype> *src;
1489
1490 src = new (ipcp_sources_pool.allocate ()) ipcp_value_source<valtype>;
1491 src->offset = offset;
1492 src->cs = cs;
1493 src->val = src_val;
1494 src->index = src_idx;
1495
1496 src->next = sources;
1497 sources = src;
1498 }
1499
1500 /* Allocate a new ipcp_value holding a tree constant, initialize its value to
1501 SOURCE and clear all other fields. */
1502
1503 static ipcp_value<tree> *
allocate_and_init_ipcp_value(tree source)1504 allocate_and_init_ipcp_value (tree source)
1505 {
1506 ipcp_value<tree> *val;
1507
1508 val = new (ipcp_cst_values_pool.allocate ()) ipcp_value<tree>();
1509 val->value = source;
1510 return val;
1511 }
1512
1513 /* Allocate a new ipcp_value holding a polymorphic context, initialize its
1514 value to SOURCE and clear all other fields. */
1515
1516 static ipcp_value<ipa_polymorphic_call_context> *
allocate_and_init_ipcp_value(ipa_polymorphic_call_context source)1517 allocate_and_init_ipcp_value (ipa_polymorphic_call_context source)
1518 {
1519 ipcp_value<ipa_polymorphic_call_context> *val;
1520
1521 // TODO
1522 val = new (ipcp_poly_ctx_values_pool.allocate ())
1523 ipcp_value<ipa_polymorphic_call_context>();
1524 val->value = source;
1525 return val;
1526 }
1527
1528 /* Try to add NEWVAL to LAT, potentially creating a new ipcp_value for it. CS,
1529 SRC_VAL SRC_INDEX and OFFSET are meant for add_source and have the same
1530 meaning. OFFSET -1 means the source is scalar and not a part of an
1531 aggregate. */
1532
1533 template <typename valtype>
1534 bool
add_value(valtype newval,cgraph_edge * cs,ipcp_value<valtype> * src_val,int src_idx,HOST_WIDE_INT offset)1535 ipcp_lattice<valtype>::add_value (valtype newval, cgraph_edge *cs,
1536 ipcp_value<valtype> *src_val,
1537 int src_idx, HOST_WIDE_INT offset)
1538 {
1539 ipcp_value<valtype> *val;
1540
1541 if (bottom)
1542 return false;
1543
1544 for (val = values; val; val = val->next)
1545 if (values_equal_for_ipcp_p (val->value, newval))
1546 {
1547 if (ipa_edge_within_scc (cs))
1548 {
1549 ipcp_value_source<valtype> *s;
1550 for (s = val->sources; s; s = s->next)
1551 if (s->cs == cs)
1552 break;
1553 if (s)
1554 return false;
1555 }
1556
1557 val->add_source (cs, src_val, src_idx, offset);
1558 return false;
1559 }
1560
1561 if (values_count == PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE))
1562 {
1563 /* We can only free sources, not the values themselves, because sources
1564 of other values in this SCC might point to them. */
1565 for (val = values; val; val = val->next)
1566 {
1567 while (val->sources)
1568 {
1569 ipcp_value_source<valtype> *src = val->sources;
1570 val->sources = src->next;
1571 ipcp_sources_pool.remove ((ipcp_value_source<tree>*)src);
1572 }
1573 }
1574
1575 values = NULL;
1576 return set_to_bottom ();
1577 }
1578
1579 values_count++;
1580 val = allocate_and_init_ipcp_value (newval);
1581 val->add_source (cs, src_val, src_idx, offset);
1582 val->next = values;
1583 values = val;
1584 return true;
1585 }
1586
1587 /* Propagate values through a pass-through jump function JFUNC associated with
1588 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1589 is the index of the source parameter. PARM_TYPE is the type of the
1590 parameter to which the result is passed. */
1591
1592 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)1593 propagate_vals_across_pass_through (cgraph_edge *cs, ipa_jump_func *jfunc,
1594 ipcp_lattice<tree> *src_lat,
1595 ipcp_lattice<tree> *dest_lat, int src_idx,
1596 tree parm_type)
1597 {
1598 ipcp_value<tree> *src_val;
1599 bool ret = false;
1600
1601 /* Do not create new values when propagating within an SCC because if there
1602 are arithmetic functions with circular dependencies, there is infinite
1603 number of them and we would just make lattices bottom. If this condition
1604 is ever relaxed we have to detect self-feeding recursive calls in
1605 cgraph_edge_brings_value_p in a smarter way. */
1606 if ((ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR)
1607 && ipa_edge_within_scc (cs))
1608 ret = dest_lat->set_contains_variable ();
1609 else
1610 for (src_val = src_lat->values; src_val; src_val = src_val->next)
1611 {
1612 tree cstval = ipa_get_jf_pass_through_result (jfunc, src_val->value,
1613 parm_type);
1614
1615 if (cstval)
1616 ret |= dest_lat->add_value (cstval, cs, src_val, src_idx);
1617 else
1618 ret |= dest_lat->set_contains_variable ();
1619 }
1620
1621 return ret;
1622 }
1623
1624 /* Propagate values through an ancestor jump function JFUNC associated with
1625 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1626 is the index of the source parameter. */
1627
1628 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)1629 propagate_vals_across_ancestor (struct cgraph_edge *cs,
1630 struct ipa_jump_func *jfunc,
1631 ipcp_lattice<tree> *src_lat,
1632 ipcp_lattice<tree> *dest_lat, int src_idx)
1633 {
1634 ipcp_value<tree> *src_val;
1635 bool ret = false;
1636
1637 if (ipa_edge_within_scc (cs))
1638 return dest_lat->set_contains_variable ();
1639
1640 for (src_val = src_lat->values; src_val; src_val = src_val->next)
1641 {
1642 tree t = ipa_get_jf_ancestor_result (jfunc, src_val->value);
1643
1644 if (t)
1645 ret |= dest_lat->add_value (t, cs, src_val, src_idx);
1646 else
1647 ret |= dest_lat->set_contains_variable ();
1648 }
1649
1650 return ret;
1651 }
1652
1653 /* Propagate scalar values across jump function JFUNC that is associated with
1654 edge CS and put the values into DEST_LAT. PARM_TYPE is the type of the
1655 parameter to which the result is passed. */
1656
1657 static bool
propagate_scalar_across_jump_function(struct cgraph_edge * cs,struct ipa_jump_func * jfunc,ipcp_lattice<tree> * dest_lat,tree param_type)1658 propagate_scalar_across_jump_function (struct cgraph_edge *cs,
1659 struct ipa_jump_func *jfunc,
1660 ipcp_lattice<tree> *dest_lat,
1661 tree param_type)
1662 {
1663 if (dest_lat->bottom)
1664 return false;
1665
1666 if (jfunc->type == IPA_JF_CONST)
1667 {
1668 tree val = ipa_get_jf_constant (jfunc);
1669 return dest_lat->add_value (val, cs, NULL, 0);
1670 }
1671 else if (jfunc->type == IPA_JF_PASS_THROUGH
1672 || jfunc->type == IPA_JF_ANCESTOR)
1673 {
1674 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1675 ipcp_lattice<tree> *src_lat;
1676 int src_idx;
1677 bool ret;
1678
1679 if (jfunc->type == IPA_JF_PASS_THROUGH)
1680 src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
1681 else
1682 src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
1683
1684 src_lat = ipa_get_scalar_lat (caller_info, src_idx);
1685 if (src_lat->bottom)
1686 return dest_lat->set_contains_variable ();
1687
1688 /* If we would need to clone the caller and cannot, do not propagate. */
1689 if (!ipcp_versionable_function_p (cs->caller)
1690 && (src_lat->contains_variable
1691 || (src_lat->values_count > 1)))
1692 return dest_lat->set_contains_variable ();
1693
1694 if (jfunc->type == IPA_JF_PASS_THROUGH)
1695 ret = propagate_vals_across_pass_through (cs, jfunc, src_lat,
1696 dest_lat, src_idx, param_type);
1697 else
1698 ret = propagate_vals_across_ancestor (cs, jfunc, src_lat, dest_lat,
1699 src_idx);
1700
1701 if (src_lat->contains_variable)
1702 ret |= dest_lat->set_contains_variable ();
1703
1704 return ret;
1705 }
1706
1707 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1708 use it for indirect inlining), we should propagate them too. */
1709 return dest_lat->set_contains_variable ();
1710 }
1711
1712 /* Propagate scalar values across jump function JFUNC that is associated with
1713 edge CS and describes argument IDX and put the values into DEST_LAT. */
1714
1715 static bool
propagate_context_across_jump_function(cgraph_edge * cs,ipa_jump_func * jfunc,int idx,ipcp_lattice<ipa_polymorphic_call_context> * dest_lat)1716 propagate_context_across_jump_function (cgraph_edge *cs,
1717 ipa_jump_func *jfunc, int idx,
1718 ipcp_lattice<ipa_polymorphic_call_context> *dest_lat)
1719 {
1720 ipa_edge_args *args = IPA_EDGE_REF (cs);
1721 if (dest_lat->bottom)
1722 return false;
1723 bool ret = false;
1724 bool added_sth = false;
1725 bool type_preserved = true;
1726
1727 ipa_polymorphic_call_context edge_ctx, *edge_ctx_ptr
1728 = ipa_get_ith_polymorhic_call_context (args, idx);
1729
1730 if (edge_ctx_ptr)
1731 edge_ctx = *edge_ctx_ptr;
1732
1733 if (jfunc->type == IPA_JF_PASS_THROUGH
1734 || jfunc->type == IPA_JF_ANCESTOR)
1735 {
1736 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1737 int src_idx;
1738 ipcp_lattice<ipa_polymorphic_call_context> *src_lat;
1739
1740 /* TODO: Once we figure out how to propagate speculations, it will
1741 probably be a good idea to switch to speculation if type_preserved is
1742 not set instead of punting. */
1743 if (jfunc->type == IPA_JF_PASS_THROUGH)
1744 {
1745 if (ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR)
1746 goto prop_fail;
1747 type_preserved = ipa_get_jf_pass_through_type_preserved (jfunc);
1748 src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
1749 }
1750 else
1751 {
1752 type_preserved = ipa_get_jf_ancestor_type_preserved (jfunc);
1753 src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
1754 }
1755
1756 src_lat = ipa_get_poly_ctx_lat (caller_info, src_idx);
1757 /* If we would need to clone the caller and cannot, do not propagate. */
1758 if (!ipcp_versionable_function_p (cs->caller)
1759 && (src_lat->contains_variable
1760 || (src_lat->values_count > 1)))
1761 goto prop_fail;
1762
1763 ipcp_value<ipa_polymorphic_call_context> *src_val;
1764 for (src_val = src_lat->values; src_val; src_val = src_val->next)
1765 {
1766 ipa_polymorphic_call_context cur = src_val->value;
1767
1768 if (!type_preserved)
1769 cur.possible_dynamic_type_change (cs->in_polymorphic_cdtor);
1770 if (jfunc->type == IPA_JF_ANCESTOR)
1771 cur.offset_by (ipa_get_jf_ancestor_offset (jfunc));
1772 /* TODO: In cases we know how the context is going to be used,
1773 we can improve the result by passing proper OTR_TYPE. */
1774 cur.combine_with (edge_ctx);
1775 if (!cur.useless_p ())
1776 {
1777 if (src_lat->contains_variable
1778 && !edge_ctx.equal_to (cur))
1779 ret |= dest_lat->set_contains_variable ();
1780 ret |= dest_lat->add_value (cur, cs, src_val, src_idx);
1781 added_sth = true;
1782 }
1783 }
1784
1785 }
1786
1787 prop_fail:
1788 if (!added_sth)
1789 {
1790 if (!edge_ctx.useless_p ())
1791 ret |= dest_lat->add_value (edge_ctx, cs);
1792 else
1793 ret |= dest_lat->set_contains_variable ();
1794 }
1795
1796 return ret;
1797 }
1798
1799 /* Propagate bits across jfunc that is associated with
1800 edge cs and update dest_lattice accordingly. */
1801
1802 bool
propagate_bits_across_jump_function(cgraph_edge * cs,int idx,ipa_jump_func * jfunc,ipcp_bits_lattice * dest_lattice)1803 propagate_bits_across_jump_function (cgraph_edge *cs, int idx,
1804 ipa_jump_func *jfunc,
1805 ipcp_bits_lattice *dest_lattice)
1806 {
1807 if (dest_lattice->bottom_p ())
1808 return false;
1809
1810 enum availability availability;
1811 cgraph_node *callee = cs->callee->function_symbol (&availability);
1812 struct ipa_node_params *callee_info = IPA_NODE_REF (callee);
1813 tree parm_type = ipa_get_type (callee_info, idx);
1814
1815 /* For K&R C programs, ipa_get_type() could return NULL_TREE. Avoid the
1816 transform for these cases. Similarly, we can have bad type mismatches
1817 with LTO, avoid doing anything with those too. */
1818 if (!parm_type
1819 || (!INTEGRAL_TYPE_P (parm_type) && !POINTER_TYPE_P (parm_type)))
1820 {
1821 if (dump_file && (dump_flags & TDF_DETAILS))
1822 fprintf (dump_file, "Setting dest_lattice to bottom, because type of "
1823 "param %i of %s is NULL or unsuitable for bits propagation\n",
1824 idx, cs->callee->name ());
1825
1826 return dest_lattice->set_to_bottom ();
1827 }
1828
1829 unsigned precision = TYPE_PRECISION (parm_type);
1830 signop sgn = TYPE_SIGN (parm_type);
1831
1832 if (jfunc->type == IPA_JF_PASS_THROUGH
1833 || jfunc->type == IPA_JF_ANCESTOR)
1834 {
1835 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1836 tree operand = NULL_TREE;
1837 enum tree_code code;
1838 unsigned src_idx;
1839
1840 if (jfunc->type == IPA_JF_PASS_THROUGH)
1841 {
1842 code = ipa_get_jf_pass_through_operation (jfunc);
1843 src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
1844 if (code != NOP_EXPR)
1845 operand = ipa_get_jf_pass_through_operand (jfunc);
1846 }
1847 else
1848 {
1849 code = POINTER_PLUS_EXPR;
1850 src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
1851 unsigned HOST_WIDE_INT offset = ipa_get_jf_ancestor_offset (jfunc) / BITS_PER_UNIT;
1852 operand = build_int_cstu (size_type_node, offset);
1853 }
1854
1855 struct ipcp_param_lattices *src_lats
1856 = ipa_get_parm_lattices (caller_info, src_idx);
1857
1858 /* Try to propagate bits if src_lattice is bottom, but jfunc is known.
1859 for eg consider:
1860 int f(int x)
1861 {
1862 g (x & 0xff);
1863 }
1864 Assume lattice for x is bottom, however we can still propagate
1865 result of x & 0xff == 0xff, which gets computed during ccp1 pass
1866 and we store it in jump function during analysis stage. */
1867
1868 if (src_lats->bits_lattice.bottom_p ()
1869 && jfunc->bits)
1870 return dest_lattice->meet_with (jfunc->bits->value, jfunc->bits->mask,
1871 precision);
1872 else
1873 return dest_lattice->meet_with (src_lats->bits_lattice, precision, sgn,
1874 code, operand);
1875 }
1876
1877 else if (jfunc->type == IPA_JF_ANCESTOR)
1878 return dest_lattice->set_to_bottom ();
1879 else if (jfunc->bits)
1880 return dest_lattice->meet_with (jfunc->bits->value, jfunc->bits->mask,
1881 precision);
1882 else
1883 return dest_lattice->set_to_bottom ();
1884 }
1885
1886 /* Emulate effects of unary OPERATION and/or conversion from SRC_TYPE to
1887 DST_TYPE on value range in SRC_VR and store it to DST_VR. Return true if
1888 the result is a range or an anti-range. */
1889
1890 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)1891 ipa_vr_operation_and_type_effects (value_range *dst_vr, value_range *src_vr,
1892 enum tree_code operation,
1893 tree dst_type, tree src_type)
1894 {
1895 memset (dst_vr, 0, sizeof (*dst_vr));
1896 extract_range_from_unary_expr (dst_vr, operation, dst_type, src_vr, src_type);
1897 if (dst_vr->type == VR_RANGE || dst_vr->type == VR_ANTI_RANGE)
1898 return true;
1899 else
1900 return false;
1901 }
1902
1903 /* Propagate value range across jump function JFUNC that is associated with
1904 edge CS with param of callee of PARAM_TYPE and update DEST_PLATS
1905 accordingly. */
1906
1907 static bool
propagate_vr_across_jump_function(cgraph_edge * cs,ipa_jump_func * jfunc,struct ipcp_param_lattices * dest_plats,tree param_type)1908 propagate_vr_across_jump_function (cgraph_edge *cs, ipa_jump_func *jfunc,
1909 struct ipcp_param_lattices *dest_plats,
1910 tree param_type)
1911 {
1912 ipcp_vr_lattice *dest_lat = &dest_plats->m_value_range;
1913
1914 if (dest_lat->bottom_p ())
1915 return false;
1916
1917 if (!param_type
1918 || (!INTEGRAL_TYPE_P (param_type)
1919 && !POINTER_TYPE_P (param_type)))
1920 return dest_lat->set_to_bottom ();
1921
1922 if (jfunc->type == IPA_JF_PASS_THROUGH)
1923 {
1924 enum tree_code operation = ipa_get_jf_pass_through_operation (jfunc);
1925
1926 if (TREE_CODE_CLASS (operation) == tcc_unary)
1927 {
1928 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1929 int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
1930 tree operand_type = ipa_get_type (caller_info, src_idx);
1931 struct ipcp_param_lattices *src_lats
1932 = ipa_get_parm_lattices (caller_info, src_idx);
1933
1934 if (src_lats->m_value_range.bottom_p ())
1935 return dest_lat->set_to_bottom ();
1936 value_range vr;
1937 if (ipa_vr_operation_and_type_effects (&vr,
1938 &src_lats->m_value_range.m_vr,
1939 operation, param_type,
1940 operand_type))
1941 return dest_lat->meet_with (&vr);
1942 }
1943 }
1944 else if (jfunc->type == IPA_JF_CONST)
1945 {
1946 tree val = ipa_get_jf_constant (jfunc);
1947 if (TREE_CODE (val) == INTEGER_CST)
1948 {
1949 val = fold_convert (param_type, val);
1950 if (TREE_OVERFLOW_P (val))
1951 val = drop_tree_overflow (val);
1952
1953 value_range tmpvr;
1954 memset (&tmpvr, 0, sizeof (tmpvr));
1955 tmpvr.type = VR_RANGE;
1956 tmpvr.min = val;
1957 tmpvr.max = val;
1958 return dest_lat->meet_with (&tmpvr);
1959 }
1960 }
1961
1962 value_range vr;
1963 if (jfunc->m_vr
1964 && ipa_vr_operation_and_type_effects (&vr, jfunc->m_vr, NOP_EXPR,
1965 param_type,
1966 TREE_TYPE (jfunc->m_vr->min)))
1967 return dest_lat->meet_with (&vr);
1968 else
1969 return dest_lat->set_to_bottom ();
1970 }
1971
1972 /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
1973 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
1974 other cases, return false). If there are no aggregate items, set
1975 aggs_by_ref to NEW_AGGS_BY_REF. */
1976
1977 static bool
set_check_aggs_by_ref(struct ipcp_param_lattices * dest_plats,bool new_aggs_by_ref)1978 set_check_aggs_by_ref (struct ipcp_param_lattices *dest_plats,
1979 bool new_aggs_by_ref)
1980 {
1981 if (dest_plats->aggs)
1982 {
1983 if (dest_plats->aggs_by_ref != new_aggs_by_ref)
1984 {
1985 set_agg_lats_to_bottom (dest_plats);
1986 return true;
1987 }
1988 }
1989 else
1990 dest_plats->aggs_by_ref = new_aggs_by_ref;
1991 return false;
1992 }
1993
1994 /* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
1995 already existing lattice for the given OFFSET and SIZE, marking all skipped
1996 lattices as containing variable and checking for overlaps. If there is no
1997 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
1998 it with offset, size and contains_variable to PRE_EXISTING, and return true,
1999 unless there are too many already. If there are two many, return false. If
2000 there are overlaps turn whole DEST_PLATS to bottom and return false. If any
2001 skipped lattices were newly marked as containing variable, set *CHANGE to
2002 true. */
2003
2004 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)2005 merge_agg_lats_step (struct ipcp_param_lattices *dest_plats,
2006 HOST_WIDE_INT offset, HOST_WIDE_INT val_size,
2007 struct ipcp_agg_lattice ***aglat,
2008 bool pre_existing, bool *change)
2009 {
2010 gcc_checking_assert (offset >= 0);
2011
2012 while (**aglat && (**aglat)->offset < offset)
2013 {
2014 if ((**aglat)->offset + (**aglat)->size > offset)
2015 {
2016 set_agg_lats_to_bottom (dest_plats);
2017 return false;
2018 }
2019 *change |= (**aglat)->set_contains_variable ();
2020 *aglat = &(**aglat)->next;
2021 }
2022
2023 if (**aglat && (**aglat)->offset == offset)
2024 {
2025 if ((**aglat)->size != val_size
2026 || ((**aglat)->next
2027 && (**aglat)->next->offset < offset + val_size))
2028 {
2029 set_agg_lats_to_bottom (dest_plats);
2030 return false;
2031 }
2032 gcc_checking_assert (!(**aglat)->next
2033 || (**aglat)->next->offset >= offset + val_size);
2034 return true;
2035 }
2036 else
2037 {
2038 struct ipcp_agg_lattice *new_al;
2039
2040 if (**aglat && (**aglat)->offset < offset + val_size)
2041 {
2042 set_agg_lats_to_bottom (dest_plats);
2043 return false;
2044 }
2045 if (dest_plats->aggs_count == PARAM_VALUE (PARAM_IPA_MAX_AGG_ITEMS))
2046 return false;
2047 dest_plats->aggs_count++;
2048 new_al = ipcp_agg_lattice_pool.allocate ();
2049 memset (new_al, 0, sizeof (*new_al));
2050
2051 new_al->offset = offset;
2052 new_al->size = val_size;
2053 new_al->contains_variable = pre_existing;
2054
2055 new_al->next = **aglat;
2056 **aglat = new_al;
2057 return true;
2058 }
2059 }
2060
2061 /* Set all AGLAT and all other aggregate lattices reachable by next pointers as
2062 containing an unknown value. */
2063
2064 static bool
set_chain_of_aglats_contains_variable(struct ipcp_agg_lattice * aglat)2065 set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice *aglat)
2066 {
2067 bool ret = false;
2068 while (aglat)
2069 {
2070 ret |= aglat->set_contains_variable ();
2071 aglat = aglat->next;
2072 }
2073 return ret;
2074 }
2075
2076 /* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
2077 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source
2078 parameter used for lattice value sources. Return true if DEST_PLATS changed
2079 in any way. */
2080
2081 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)2082 merge_aggregate_lattices (struct cgraph_edge *cs,
2083 struct ipcp_param_lattices *dest_plats,
2084 struct ipcp_param_lattices *src_plats,
2085 int src_idx, HOST_WIDE_INT offset_delta)
2086 {
2087 bool pre_existing = dest_plats->aggs != NULL;
2088 struct ipcp_agg_lattice **dst_aglat;
2089 bool ret = false;
2090
2091 if (set_check_aggs_by_ref (dest_plats, src_plats->aggs_by_ref))
2092 return true;
2093 if (src_plats->aggs_bottom)
2094 return set_agg_lats_contain_variable (dest_plats);
2095 if (src_plats->aggs_contain_variable)
2096 ret |= set_agg_lats_contain_variable (dest_plats);
2097 dst_aglat = &dest_plats->aggs;
2098
2099 for (struct ipcp_agg_lattice *src_aglat = src_plats->aggs;
2100 src_aglat;
2101 src_aglat = src_aglat->next)
2102 {
2103 HOST_WIDE_INT new_offset = src_aglat->offset - offset_delta;
2104
2105 if (new_offset < 0)
2106 continue;
2107 if (merge_agg_lats_step (dest_plats, new_offset, src_aglat->size,
2108 &dst_aglat, pre_existing, &ret))
2109 {
2110 struct ipcp_agg_lattice *new_al = *dst_aglat;
2111
2112 dst_aglat = &(*dst_aglat)->next;
2113 if (src_aglat->bottom)
2114 {
2115 ret |= new_al->set_contains_variable ();
2116 continue;
2117 }
2118 if (src_aglat->contains_variable)
2119 ret |= new_al->set_contains_variable ();
2120 for (ipcp_value<tree> *val = src_aglat->values;
2121 val;
2122 val = val->next)
2123 ret |= new_al->add_value (val->value, cs, val, src_idx,
2124 src_aglat->offset);
2125 }
2126 else if (dest_plats->aggs_bottom)
2127 return true;
2128 }
2129 ret |= set_chain_of_aglats_contains_variable (*dst_aglat);
2130 return ret;
2131 }
2132
2133 /* Determine whether there is anything to propagate FROM SRC_PLATS through a
2134 pass-through JFUNC and if so, whether it has conform and conforms to the
2135 rules about propagating values passed by reference. */
2136
2137 static bool
agg_pass_through_permissible_p(struct ipcp_param_lattices * src_plats,struct ipa_jump_func * jfunc)2138 agg_pass_through_permissible_p (struct ipcp_param_lattices *src_plats,
2139 struct ipa_jump_func *jfunc)
2140 {
2141 return src_plats->aggs
2142 && (!src_plats->aggs_by_ref
2143 || ipa_get_jf_pass_through_agg_preserved (jfunc));
2144 }
2145
2146 /* Propagate scalar values across jump function JFUNC that is associated with
2147 edge CS and put the values into DEST_LAT. */
2148
2149 static bool
propagate_aggs_across_jump_function(struct cgraph_edge * cs,struct ipa_jump_func * jfunc,struct ipcp_param_lattices * dest_plats)2150 propagate_aggs_across_jump_function (struct cgraph_edge *cs,
2151 struct ipa_jump_func *jfunc,
2152 struct ipcp_param_lattices *dest_plats)
2153 {
2154 bool ret = false;
2155
2156 if (dest_plats->aggs_bottom)
2157 return false;
2158
2159 if (jfunc->type == IPA_JF_PASS_THROUGH
2160 && ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
2161 {
2162 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
2163 int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
2164 struct ipcp_param_lattices *src_plats;
2165
2166 src_plats = ipa_get_parm_lattices (caller_info, src_idx);
2167 if (agg_pass_through_permissible_p (src_plats, jfunc))
2168 {
2169 /* Currently we do not produce clobber aggregate jump
2170 functions, replace with merging when we do. */
2171 gcc_assert (!jfunc->agg.items);
2172 ret |= merge_aggregate_lattices (cs, dest_plats, src_plats,
2173 src_idx, 0);
2174 }
2175 else
2176 ret |= set_agg_lats_contain_variable (dest_plats);
2177 }
2178 else if (jfunc->type == IPA_JF_ANCESTOR
2179 && ipa_get_jf_ancestor_agg_preserved (jfunc))
2180 {
2181 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
2182 int src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
2183 struct ipcp_param_lattices *src_plats;
2184
2185 src_plats = ipa_get_parm_lattices (caller_info, src_idx);
2186 if (src_plats->aggs && src_plats->aggs_by_ref)
2187 {
2188 /* Currently we do not produce clobber aggregate jump
2189 functions, replace with merging when we do. */
2190 gcc_assert (!jfunc->agg.items);
2191 ret |= merge_aggregate_lattices (cs, dest_plats, src_plats, src_idx,
2192 ipa_get_jf_ancestor_offset (jfunc));
2193 }
2194 else if (!src_plats->aggs_by_ref)
2195 ret |= set_agg_lats_to_bottom (dest_plats);
2196 else
2197 ret |= set_agg_lats_contain_variable (dest_plats);
2198 }
2199 else if (jfunc->agg.items)
2200 {
2201 bool pre_existing = dest_plats->aggs != NULL;
2202 struct ipcp_agg_lattice **aglat = &dest_plats->aggs;
2203 struct ipa_agg_jf_item *item;
2204 int i;
2205
2206 if (set_check_aggs_by_ref (dest_plats, jfunc->agg.by_ref))
2207 return true;
2208
2209 FOR_EACH_VEC_ELT (*jfunc->agg.items, i, item)
2210 {
2211 HOST_WIDE_INT val_size;
2212
2213 if (item->offset < 0)
2214 continue;
2215 gcc_checking_assert (is_gimple_ip_invariant (item->value));
2216 val_size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (item->value)));
2217
2218 if (merge_agg_lats_step (dest_plats, item->offset, val_size,
2219 &aglat, pre_existing, &ret))
2220 {
2221 ret |= (*aglat)->add_value (item->value, cs, NULL, 0, 0);
2222 aglat = &(*aglat)->next;
2223 }
2224 else if (dest_plats->aggs_bottom)
2225 return true;
2226 }
2227
2228 ret |= set_chain_of_aglats_contains_variable (*aglat);
2229 }
2230 else
2231 ret |= set_agg_lats_contain_variable (dest_plats);
2232
2233 return ret;
2234 }
2235
2236 /* Return true if on the way cfrom CS->caller to the final (non-alias and
2237 non-thunk) destination, the call passes through a thunk. */
2238
2239 static bool
call_passes_through_thunk_p(cgraph_edge * cs)2240 call_passes_through_thunk_p (cgraph_edge *cs)
2241 {
2242 cgraph_node *alias_or_thunk = cs->callee;
2243 while (alias_or_thunk->alias)
2244 alias_or_thunk = alias_or_thunk->get_alias_target ();
2245 return alias_or_thunk->thunk.thunk_p;
2246 }
2247
2248 /* Propagate constants from the caller to the callee of CS. INFO describes the
2249 caller. */
2250
2251 static bool
propagate_constants_across_call(struct cgraph_edge * cs)2252 propagate_constants_across_call (struct cgraph_edge *cs)
2253 {
2254 struct ipa_node_params *callee_info;
2255 enum availability availability;
2256 cgraph_node *callee;
2257 struct ipa_edge_args *args;
2258 bool ret = false;
2259 int i, args_count, parms_count;
2260
2261 callee = cs->callee->function_symbol (&availability);
2262 if (!callee->definition)
2263 return false;
2264 gcc_checking_assert (callee->has_gimple_body_p ());
2265 callee_info = IPA_NODE_REF (callee);
2266
2267 args = IPA_EDGE_REF (cs);
2268 args_count = ipa_get_cs_argument_count (args);
2269 parms_count = ipa_get_param_count (callee_info);
2270 if (parms_count == 0)
2271 return false;
2272
2273 /* No propagation through instrumentation thunks is available yet.
2274 It should be possible with proper mapping of call args and
2275 instrumented callee params in the propagation loop below. But
2276 this case mostly occurs when legacy code calls instrumented code
2277 and it is not a primary target for optimizations.
2278 We detect instrumentation thunks in aliases and thunks chain by
2279 checking instrumentation_clone flag for chain source and target.
2280 Going through instrumentation thunks we always have it changed
2281 from 0 to 1 and all other nodes do not change it. */
2282 if (!cs->callee->instrumentation_clone
2283 && callee->instrumentation_clone)
2284 {
2285 for (i = 0; i < parms_count; i++)
2286 ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info,
2287 i));
2288 return ret;
2289 }
2290
2291 /* If this call goes through a thunk we must not propagate to the first (0th)
2292 parameter. However, we might need to uncover a thunk from below a series
2293 of aliases first. */
2294 if (call_passes_through_thunk_p (cs))
2295 {
2296 ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info,
2297 0));
2298 i = 1;
2299 }
2300 else
2301 i = 0;
2302
2303 for (; (i < args_count) && (i < parms_count); i++)
2304 {
2305 struct ipa_jump_func *jump_func = ipa_get_ith_jump_func (args, i);
2306 struct ipcp_param_lattices *dest_plats;
2307 tree param_type = ipa_get_type (callee_info, i);
2308
2309 dest_plats = ipa_get_parm_lattices (callee_info, i);
2310 if (availability == AVAIL_INTERPOSABLE)
2311 ret |= set_all_contains_variable (dest_plats);
2312 else
2313 {
2314 ret |= propagate_scalar_across_jump_function (cs, jump_func,
2315 &dest_plats->itself,
2316 param_type);
2317 ret |= propagate_context_across_jump_function (cs, jump_func, i,
2318 &dest_plats->ctxlat);
2319 ret
2320 |= propagate_bits_across_jump_function (cs, i, jump_func,
2321 &dest_plats->bits_lattice);
2322 ret |= propagate_aggs_across_jump_function (cs, jump_func,
2323 dest_plats);
2324 if (opt_for_fn (callee->decl, flag_ipa_vrp))
2325 ret |= propagate_vr_across_jump_function (cs, jump_func,
2326 dest_plats, param_type);
2327 else
2328 ret |= dest_plats->m_value_range.set_to_bottom ();
2329 }
2330 }
2331 for (; i < parms_count; i++)
2332 ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info, i));
2333
2334 return ret;
2335 }
2336
2337 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
2338 KNOWN_CONTEXTS, KNOWN_AGGS or AGG_REPS return the destination. The latter
2339 three can be NULL. If AGG_REPS is not NULL, KNOWN_AGGS is ignored. */
2340
2341 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)2342 ipa_get_indirect_edge_target_1 (struct cgraph_edge *ie,
2343 vec<tree> known_csts,
2344 vec<ipa_polymorphic_call_context> known_contexts,
2345 vec<ipa_agg_jump_function_p> known_aggs,
2346 struct ipa_agg_replacement_value *agg_reps,
2347 bool *speculative)
2348 {
2349 int param_index = ie->indirect_info->param_index;
2350 HOST_WIDE_INT anc_offset;
2351 tree t;
2352 tree target = NULL;
2353
2354 *speculative = false;
2355
2356 if (param_index == -1
2357 || known_csts.length () <= (unsigned int) param_index)
2358 return NULL_TREE;
2359
2360 if (!ie->indirect_info->polymorphic)
2361 {
2362 tree t;
2363
2364 if (ie->indirect_info->agg_contents)
2365 {
2366 t = NULL;
2367 if (agg_reps && ie->indirect_info->guaranteed_unmodified)
2368 {
2369 while (agg_reps)
2370 {
2371 if (agg_reps->index == param_index
2372 && agg_reps->offset == ie->indirect_info->offset
2373 && agg_reps->by_ref == ie->indirect_info->by_ref)
2374 {
2375 t = agg_reps->value;
2376 break;
2377 }
2378 agg_reps = agg_reps->next;
2379 }
2380 }
2381 if (!t)
2382 {
2383 struct ipa_agg_jump_function *agg;
2384 if (known_aggs.length () > (unsigned int) param_index)
2385 agg = known_aggs[param_index];
2386 else
2387 agg = NULL;
2388 bool from_global_constant;
2389 t = ipa_find_agg_cst_for_param (agg, known_csts[param_index],
2390 ie->indirect_info->offset,
2391 ie->indirect_info->by_ref,
2392 &from_global_constant);
2393 if (t
2394 && !from_global_constant
2395 && !ie->indirect_info->guaranteed_unmodified)
2396 t = NULL_TREE;
2397 }
2398 }
2399 else
2400 t = known_csts[param_index];
2401
2402 if (t
2403 && TREE_CODE (t) == ADDR_EXPR
2404 && TREE_CODE (TREE_OPERAND (t, 0)) == FUNCTION_DECL)
2405 return TREE_OPERAND (t, 0);
2406 else
2407 return NULL_TREE;
2408 }
2409
2410 if (!opt_for_fn (ie->caller->decl, flag_devirtualize))
2411 return NULL_TREE;
2412
2413 gcc_assert (!ie->indirect_info->agg_contents);
2414 anc_offset = ie->indirect_info->offset;
2415
2416 t = NULL;
2417
2418 /* Try to work out value of virtual table pointer value in replacemnets. */
2419 if (!t && agg_reps && !ie->indirect_info->by_ref)
2420 {
2421 while (agg_reps)
2422 {
2423 if (agg_reps->index == param_index
2424 && agg_reps->offset == ie->indirect_info->offset
2425 && agg_reps->by_ref)
2426 {
2427 t = agg_reps->value;
2428 break;
2429 }
2430 agg_reps = agg_reps->next;
2431 }
2432 }
2433
2434 /* Try to work out value of virtual table pointer value in known
2435 aggregate values. */
2436 if (!t && known_aggs.length () > (unsigned int) param_index
2437 && !ie->indirect_info->by_ref)
2438 {
2439 struct ipa_agg_jump_function *agg;
2440 agg = known_aggs[param_index];
2441 t = ipa_find_agg_cst_for_param (agg, known_csts[param_index],
2442 ie->indirect_info->offset, true);
2443 }
2444
2445 /* If we found the virtual table pointer, lookup the target. */
2446 if (t)
2447 {
2448 tree vtable;
2449 unsigned HOST_WIDE_INT offset;
2450 if (vtable_pointer_value_to_vtable (t, &vtable, &offset))
2451 {
2452 bool can_refer;
2453 target = gimple_get_virt_method_for_vtable (ie->indirect_info->otr_token,
2454 vtable, offset, &can_refer);
2455 if (can_refer)
2456 {
2457 if (!target
2458 || (TREE_CODE (TREE_TYPE (target)) == FUNCTION_TYPE
2459 && DECL_FUNCTION_CODE (target) == BUILT_IN_UNREACHABLE)
2460 || !possible_polymorphic_call_target_p
2461 (ie, cgraph_node::get (target)))
2462 {
2463 /* Do not speculate builtin_unreachable, it is stupid! */
2464 if (ie->indirect_info->vptr_changed)
2465 return NULL;
2466 target = ipa_impossible_devirt_target (ie, target);
2467 }
2468 *speculative = ie->indirect_info->vptr_changed;
2469 if (!*speculative)
2470 return target;
2471 }
2472 }
2473 }
2474
2475 /* Do we know the constant value of pointer? */
2476 if (!t)
2477 t = known_csts[param_index];
2478
2479 gcc_checking_assert (!t || TREE_CODE (t) != TREE_BINFO);
2480
2481 ipa_polymorphic_call_context context;
2482 if (known_contexts.length () > (unsigned int) param_index)
2483 {
2484 context = known_contexts[param_index];
2485 context.offset_by (anc_offset);
2486 if (ie->indirect_info->vptr_changed)
2487 context.possible_dynamic_type_change (ie->in_polymorphic_cdtor,
2488 ie->indirect_info->otr_type);
2489 if (t)
2490 {
2491 ipa_polymorphic_call_context ctx2 = ipa_polymorphic_call_context
2492 (t, ie->indirect_info->otr_type, anc_offset);
2493 if (!ctx2.useless_p ())
2494 context.combine_with (ctx2, ie->indirect_info->otr_type);
2495 }
2496 }
2497 else if (t)
2498 {
2499 context = ipa_polymorphic_call_context (t, ie->indirect_info->otr_type,
2500 anc_offset);
2501 if (ie->indirect_info->vptr_changed)
2502 context.possible_dynamic_type_change (ie->in_polymorphic_cdtor,
2503 ie->indirect_info->otr_type);
2504 }
2505 else
2506 return NULL_TREE;
2507
2508 vec <cgraph_node *>targets;
2509 bool final;
2510
2511 targets = possible_polymorphic_call_targets
2512 (ie->indirect_info->otr_type,
2513 ie->indirect_info->otr_token,
2514 context, &final);
2515 if (!final || targets.length () > 1)
2516 {
2517 struct cgraph_node *node;
2518 if (*speculative)
2519 return target;
2520 if (!opt_for_fn (ie->caller->decl, flag_devirtualize_speculatively)
2521 || ie->speculative || !ie->maybe_hot_p ())
2522 return NULL;
2523 node = try_speculative_devirtualization (ie->indirect_info->otr_type,
2524 ie->indirect_info->otr_token,
2525 context);
2526 if (node)
2527 {
2528 *speculative = true;
2529 target = node->decl;
2530 }
2531 else
2532 return NULL;
2533 }
2534 else
2535 {
2536 *speculative = false;
2537 if (targets.length () == 1)
2538 target = targets[0]->decl;
2539 else
2540 target = ipa_impossible_devirt_target (ie, NULL_TREE);
2541 }
2542
2543 if (target && !possible_polymorphic_call_target_p (ie,
2544 cgraph_node::get (target)))
2545 {
2546 if (*speculative)
2547 return NULL;
2548 target = ipa_impossible_devirt_target (ie, target);
2549 }
2550
2551 return target;
2552 }
2553
2554
2555 /* If an indirect edge IE can be turned into a direct one based on KNOWN_CSTS,
2556 KNOWN_CONTEXTS (which can be vNULL) or KNOWN_AGGS (which also can be vNULL)
2557 return the destination. */
2558
2559 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)2560 ipa_get_indirect_edge_target (struct cgraph_edge *ie,
2561 vec<tree> known_csts,
2562 vec<ipa_polymorphic_call_context> known_contexts,
2563 vec<ipa_agg_jump_function_p> known_aggs,
2564 bool *speculative)
2565 {
2566 return ipa_get_indirect_edge_target_1 (ie, known_csts, known_contexts,
2567 known_aggs, NULL, speculative);
2568 }
2569
2570 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
2571 and KNOWN_CONTEXTS. */
2572
2573 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)2574 devirtualization_time_bonus (struct cgraph_node *node,
2575 vec<tree> known_csts,
2576 vec<ipa_polymorphic_call_context> known_contexts,
2577 vec<ipa_agg_jump_function_p> known_aggs)
2578 {
2579 struct cgraph_edge *ie;
2580 int res = 0;
2581
2582 for (ie = node->indirect_calls; ie; ie = ie->next_callee)
2583 {
2584 struct cgraph_node *callee;
2585 struct ipa_fn_summary *isummary;
2586 enum availability avail;
2587 tree target;
2588 bool speculative;
2589
2590 target = ipa_get_indirect_edge_target (ie, known_csts, known_contexts,
2591 known_aggs, &speculative);
2592 if (!target)
2593 continue;
2594
2595 /* Only bare minimum benefit for clearly un-inlineable targets. */
2596 res += 1;
2597 callee = cgraph_node::get (target);
2598 if (!callee || !callee->definition)
2599 continue;
2600 callee = callee->function_symbol (&avail);
2601 if (avail < AVAIL_AVAILABLE)
2602 continue;
2603 isummary = ipa_fn_summaries->get (callee);
2604 if (!isummary->inlinable)
2605 continue;
2606
2607 /* FIXME: The values below need re-considering and perhaps also
2608 integrating into the cost metrics, at lest in some very basic way. */
2609 if (isummary->size <= MAX_INLINE_INSNS_AUTO / 4)
2610 res += 31 / ((int)speculative + 1);
2611 else if (isummary->size <= MAX_INLINE_INSNS_AUTO / 2)
2612 res += 15 / ((int)speculative + 1);
2613 else if (isummary->size <= MAX_INLINE_INSNS_AUTO
2614 || DECL_DECLARED_INLINE_P (callee->decl))
2615 res += 7 / ((int)speculative + 1);
2616 }
2617
2618 return res;
2619 }
2620
2621 /* Return time bonus incurred because of HINTS. */
2622
2623 static int
hint_time_bonus(ipa_hints hints)2624 hint_time_bonus (ipa_hints hints)
2625 {
2626 int result = 0;
2627 if (hints & (INLINE_HINT_loop_iterations | INLINE_HINT_loop_stride))
2628 result += PARAM_VALUE (PARAM_IPA_CP_LOOP_HINT_BONUS);
2629 if (hints & INLINE_HINT_array_index)
2630 result += PARAM_VALUE (PARAM_IPA_CP_ARRAY_INDEX_HINT_BONUS);
2631 return result;
2632 }
2633
2634 /* If there is a reason to penalize the function described by INFO in the
2635 cloning goodness evaluation, do so. */
2636
2637 static inline int64_t
incorporate_penalties(ipa_node_params * info,int64_t evaluation)2638 incorporate_penalties (ipa_node_params *info, int64_t evaluation)
2639 {
2640 if (info->node_within_scc)
2641 evaluation = (evaluation
2642 * (100 - PARAM_VALUE (PARAM_IPA_CP_RECURSION_PENALTY))) / 100;
2643
2644 if (info->node_calling_single_call)
2645 evaluation = (evaluation
2646 * (100 - PARAM_VALUE (PARAM_IPA_CP_SINGLE_CALL_PENALTY)))
2647 / 100;
2648
2649 return evaluation;
2650 }
2651
2652 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
2653 and SIZE_COST and with the sum of frequencies of incoming edges to the
2654 potential new clone in FREQUENCIES. */
2655
2656 static bool
good_cloning_opportunity_p(struct cgraph_node * node,int time_benefit,int freq_sum,profile_count count_sum,int size_cost)2657 good_cloning_opportunity_p (struct cgraph_node *node, int time_benefit,
2658 int freq_sum, profile_count count_sum, int size_cost)
2659 {
2660 if (time_benefit == 0
2661 || !opt_for_fn (node->decl, flag_ipa_cp_clone)
2662 || node->optimize_for_size_p ())
2663 return false;
2664
2665 gcc_assert (size_cost > 0);
2666
2667 struct ipa_node_params *info = IPA_NODE_REF (node);
2668 if (max_count > profile_count::zero ())
2669 {
2670 int factor = RDIV (count_sum.probability_in
2671 (max_count).to_reg_br_prob_base ()
2672 * 1000, REG_BR_PROB_BASE);
2673 int64_t evaluation = (((int64_t) time_benefit * factor)
2674 / size_cost);
2675 evaluation = incorporate_penalties (info, evaluation);
2676
2677 if (dump_file && (dump_flags & TDF_DETAILS))
2678 {
2679 fprintf (dump_file, " good_cloning_opportunity_p (time: %i, "
2680 "size: %i, count_sum: ", time_benefit, size_cost);
2681 count_sum.dump (dump_file);
2682 fprintf (dump_file, "%s%s) -> evaluation: " "%" PRId64
2683 ", threshold: %i\n",
2684 info->node_within_scc ? ", scc" : "",
2685 info->node_calling_single_call ? ", single_call" : "",
2686 evaluation, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD));
2687 }
2688
2689 return evaluation >= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD);
2690 }
2691 else
2692 {
2693 int64_t evaluation = (((int64_t) time_benefit * freq_sum)
2694 / size_cost);
2695 evaluation = incorporate_penalties (info, evaluation);
2696
2697 if (dump_file && (dump_flags & TDF_DETAILS))
2698 fprintf (dump_file, " good_cloning_opportunity_p (time: %i, "
2699 "size: %i, freq_sum: %i%s%s) -> evaluation: "
2700 "%" PRId64 ", threshold: %i\n",
2701 time_benefit, size_cost, freq_sum,
2702 info->node_within_scc ? ", scc" : "",
2703 info->node_calling_single_call ? ", single_call" : "",
2704 evaluation, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD));
2705
2706 return evaluation >= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD);
2707 }
2708 }
2709
2710 /* Return all context independent values from aggregate lattices in PLATS in a
2711 vector. Return NULL if there are none. */
2712
2713 static vec<ipa_agg_jf_item, va_gc> *
context_independent_aggregate_values(struct ipcp_param_lattices * plats)2714 context_independent_aggregate_values (struct ipcp_param_lattices *plats)
2715 {
2716 vec<ipa_agg_jf_item, va_gc> *res = NULL;
2717
2718 if (plats->aggs_bottom
2719 || plats->aggs_contain_variable
2720 || plats->aggs_count == 0)
2721 return NULL;
2722
2723 for (struct ipcp_agg_lattice *aglat = plats->aggs;
2724 aglat;
2725 aglat = aglat->next)
2726 if (aglat->is_single_const ())
2727 {
2728 struct ipa_agg_jf_item item;
2729 item.offset = aglat->offset;
2730 item.value = aglat->values->value;
2731 vec_safe_push (res, item);
2732 }
2733 return res;
2734 }
2735
2736 /* Allocate KNOWN_CSTS, KNOWN_CONTEXTS and, if non-NULL, KNOWN_AGGS and
2737 populate them with values of parameters that are known independent of the
2738 context. INFO describes the function. If REMOVABLE_PARAMS_COST is
2739 non-NULL, the movement cost of all removable parameters will be stored in
2740 it. */
2741
2742 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)2743 gather_context_independent_values (struct ipa_node_params *info,
2744 vec<tree> *known_csts,
2745 vec<ipa_polymorphic_call_context>
2746 *known_contexts,
2747 vec<ipa_agg_jump_function> *known_aggs,
2748 int *removable_params_cost)
2749 {
2750 int i, count = ipa_get_param_count (info);
2751 bool ret = false;
2752
2753 known_csts->create (0);
2754 known_contexts->create (0);
2755 known_csts->safe_grow_cleared (count);
2756 known_contexts->safe_grow_cleared (count);
2757 if (known_aggs)
2758 {
2759 known_aggs->create (0);
2760 known_aggs->safe_grow_cleared (count);
2761 }
2762
2763 if (removable_params_cost)
2764 *removable_params_cost = 0;
2765
2766 for (i = 0; i < count; i++)
2767 {
2768 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
2769 ipcp_lattice<tree> *lat = &plats->itself;
2770
2771 if (lat->is_single_const ())
2772 {
2773 ipcp_value<tree> *val = lat->values;
2774 gcc_checking_assert (TREE_CODE (val->value) != TREE_BINFO);
2775 (*known_csts)[i] = val->value;
2776 if (removable_params_cost)
2777 *removable_params_cost
2778 += estimate_move_cost (TREE_TYPE (val->value), false);
2779 ret = true;
2780 }
2781 else if (removable_params_cost
2782 && !ipa_is_param_used (info, i))
2783 *removable_params_cost
2784 += ipa_get_param_move_cost (info, i);
2785
2786 if (!ipa_is_param_used (info, i))
2787 continue;
2788
2789 ipcp_lattice<ipa_polymorphic_call_context> *ctxlat = &plats->ctxlat;
2790 /* Do not account known context as reason for cloning. We can see
2791 if it permits devirtualization. */
2792 if (ctxlat->is_single_const ())
2793 (*known_contexts)[i] = ctxlat->values->value;
2794
2795 if (known_aggs)
2796 {
2797 vec<ipa_agg_jf_item, va_gc> *agg_items;
2798 struct ipa_agg_jump_function *ajf;
2799
2800 agg_items = context_independent_aggregate_values (plats);
2801 ajf = &(*known_aggs)[i];
2802 ajf->items = agg_items;
2803 ajf->by_ref = plats->aggs_by_ref;
2804 ret |= agg_items != NULL;
2805 }
2806 }
2807
2808 return ret;
2809 }
2810
2811 /* The current interface in ipa-inline-analysis requires a pointer vector.
2812 Create it.
2813
2814 FIXME: That interface should be re-worked, this is slightly silly. Still,
2815 I'd like to discuss how to change it first and this demonstrates the
2816 issue. */
2817
2818 static vec<ipa_agg_jump_function_p>
agg_jmp_p_vec_for_t_vec(vec<ipa_agg_jump_function> known_aggs)2819 agg_jmp_p_vec_for_t_vec (vec<ipa_agg_jump_function> known_aggs)
2820 {
2821 vec<ipa_agg_jump_function_p> ret;
2822 struct ipa_agg_jump_function *ajf;
2823 int i;
2824
2825 ret.create (known_aggs.length ());
2826 FOR_EACH_VEC_ELT (known_aggs, i, ajf)
2827 ret.quick_push (ajf);
2828 return ret;
2829 }
2830
2831 /* Perform time and size measurement of NODE with the context given in
2832 KNOWN_CSTS, KNOWN_CONTEXTS and KNOWN_AGGS, calculate the benefit and cost
2833 given BASE_TIME of the node without specialization, REMOVABLE_PARAMS_COST of
2834 all context-independent removable parameters and EST_MOVE_COST of estimated
2835 movement of the considered parameter and store it into VAL. */
2836
2837 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)2838 perform_estimation_of_a_value (cgraph_node *node, vec<tree> known_csts,
2839 vec<ipa_polymorphic_call_context> known_contexts,
2840 vec<ipa_agg_jump_function_p> known_aggs_ptrs,
2841 int removable_params_cost,
2842 int est_move_cost, ipcp_value_base *val)
2843 {
2844 int size, time_benefit;
2845 sreal time, base_time;
2846 ipa_hints hints;
2847
2848 estimate_ipcp_clone_size_and_time (node, known_csts, known_contexts,
2849 known_aggs_ptrs, &size, &time,
2850 &base_time, &hints);
2851 base_time -= time;
2852 if (base_time > 65535)
2853 base_time = 65535;
2854
2855 /* Extern inline functions have no cloning local time benefits because they
2856 will be inlined anyway. The only reason to clone them is if it enables
2857 optimization in any of the functions they call. */
2858 if (DECL_EXTERNAL (node->decl) && DECL_DECLARED_INLINE_P (node->decl))
2859 time_benefit = 0;
2860 else
2861 time_benefit = base_time.to_int ()
2862 + devirtualization_time_bonus (node, known_csts, known_contexts,
2863 known_aggs_ptrs)
2864 + hint_time_bonus (hints)
2865 + removable_params_cost + est_move_cost;
2866
2867 gcc_checking_assert (size >=0);
2868 /* The inliner-heuristics based estimates may think that in certain
2869 contexts some functions do not have any size at all but we want
2870 all specializations to have at least a tiny cost, not least not to
2871 divide by zero. */
2872 if (size == 0)
2873 size = 1;
2874
2875 val->local_time_benefit = time_benefit;
2876 val->local_size_cost = size;
2877 }
2878
2879 /* Iterate over known values of parameters of NODE and estimate the local
2880 effects in terms of time and size they have. */
2881
2882 static void
estimate_local_effects(struct cgraph_node * node)2883 estimate_local_effects (struct cgraph_node *node)
2884 {
2885 struct ipa_node_params *info = IPA_NODE_REF (node);
2886 int i, count = ipa_get_param_count (info);
2887 vec<tree> known_csts;
2888 vec<ipa_polymorphic_call_context> known_contexts;
2889 vec<ipa_agg_jump_function> known_aggs;
2890 vec<ipa_agg_jump_function_p> known_aggs_ptrs;
2891 bool always_const;
2892 int removable_params_cost;
2893
2894 if (!count || !ipcp_versionable_function_p (node))
2895 return;
2896
2897 if (dump_file && (dump_flags & TDF_DETAILS))
2898 fprintf (dump_file, "\nEstimating effects for %s.\n", node->dump_name ());
2899
2900 always_const = gather_context_independent_values (info, &known_csts,
2901 &known_contexts, &known_aggs,
2902 &removable_params_cost);
2903 known_aggs_ptrs = agg_jmp_p_vec_for_t_vec (known_aggs);
2904 int devirt_bonus = devirtualization_time_bonus (node, known_csts,
2905 known_contexts, known_aggs_ptrs);
2906 if (always_const || devirt_bonus
2907 || (removable_params_cost && node->local.can_change_signature))
2908 {
2909 struct caller_statistics stats;
2910 ipa_hints hints;
2911 sreal time, base_time;
2912 int size;
2913
2914 init_caller_stats (&stats);
2915 node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats,
2916 false);
2917 estimate_ipcp_clone_size_and_time (node, known_csts, known_contexts,
2918 known_aggs_ptrs, &size, &time,
2919 &base_time, &hints);
2920 time -= devirt_bonus;
2921 time -= hint_time_bonus (hints);
2922 time -= removable_params_cost;
2923 size -= stats.n_calls * removable_params_cost;
2924
2925 if (dump_file)
2926 fprintf (dump_file, " - context independent values, size: %i, "
2927 "time_benefit: %f\n", size, (base_time - time).to_double ());
2928
2929 if (size <= 0 || node->local.local)
2930 {
2931 info->do_clone_for_all_contexts = true;
2932
2933 if (dump_file)
2934 fprintf (dump_file, " Decided to specialize for all "
2935 "known contexts, code not going to grow.\n");
2936 }
2937 else if (good_cloning_opportunity_p (node,
2938 MAX ((base_time - time).to_int (),
2939 65536),
2940 stats.freq_sum, stats.count_sum,
2941 size))
2942 {
2943 if (size + overall_size <= max_new_size)
2944 {
2945 info->do_clone_for_all_contexts = true;
2946 overall_size += size;
2947
2948 if (dump_file)
2949 fprintf (dump_file, " Decided to specialize for all "
2950 "known contexts, growth deemed beneficial.\n");
2951 }
2952 else if (dump_file && (dump_flags & TDF_DETAILS))
2953 fprintf (dump_file, " Not cloning for all contexts because "
2954 "max_new_size would be reached with %li.\n",
2955 size + overall_size);
2956 }
2957 else if (dump_file && (dump_flags & TDF_DETAILS))
2958 fprintf (dump_file, " Not cloning for all contexts because "
2959 "!good_cloning_opportunity_p.\n");
2960
2961 }
2962
2963 for (i = 0; i < count; i++)
2964 {
2965 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
2966 ipcp_lattice<tree> *lat = &plats->itself;
2967 ipcp_value<tree> *val;
2968
2969 if (lat->bottom
2970 || !lat->values
2971 || known_csts[i])
2972 continue;
2973
2974 for (val = lat->values; val; val = val->next)
2975 {
2976 gcc_checking_assert (TREE_CODE (val->value) != TREE_BINFO);
2977 known_csts[i] = val->value;
2978
2979 int emc = estimate_move_cost (TREE_TYPE (val->value), true);
2980 perform_estimation_of_a_value (node, known_csts, known_contexts,
2981 known_aggs_ptrs,
2982 removable_params_cost, emc, val);
2983
2984 if (dump_file && (dump_flags & TDF_DETAILS))
2985 {
2986 fprintf (dump_file, " - estimates for value ");
2987 print_ipcp_constant_value (dump_file, val->value);
2988 fprintf (dump_file, " for ");
2989 ipa_dump_param (dump_file, info, i);
2990 fprintf (dump_file, ": time_benefit: %i, size: %i\n",
2991 val->local_time_benefit, val->local_size_cost);
2992 }
2993 }
2994 known_csts[i] = NULL_TREE;
2995 }
2996
2997 for (i = 0; i < count; i++)
2998 {
2999 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
3000
3001 if (!plats->virt_call)
3002 continue;
3003
3004 ipcp_lattice<ipa_polymorphic_call_context> *ctxlat = &plats->ctxlat;
3005 ipcp_value<ipa_polymorphic_call_context> *val;
3006
3007 if (ctxlat->bottom
3008 || !ctxlat->values
3009 || !known_contexts[i].useless_p ())
3010 continue;
3011
3012 for (val = ctxlat->values; val; val = val->next)
3013 {
3014 known_contexts[i] = val->value;
3015 perform_estimation_of_a_value (node, known_csts, known_contexts,
3016 known_aggs_ptrs,
3017 removable_params_cost, 0, val);
3018
3019 if (dump_file && (dump_flags & TDF_DETAILS))
3020 {
3021 fprintf (dump_file, " - estimates for polymorphic context ");
3022 print_ipcp_constant_value (dump_file, val->value);
3023 fprintf (dump_file, " for ");
3024 ipa_dump_param (dump_file, info, i);
3025 fprintf (dump_file, ": time_benefit: %i, size: %i\n",
3026 val->local_time_benefit, val->local_size_cost);
3027 }
3028 }
3029 known_contexts[i] = ipa_polymorphic_call_context ();
3030 }
3031
3032 for (i = 0; i < count; i++)
3033 {
3034 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
3035 struct ipa_agg_jump_function *ajf;
3036 struct ipcp_agg_lattice *aglat;
3037
3038 if (plats->aggs_bottom || !plats->aggs)
3039 continue;
3040
3041 ajf = &known_aggs[i];
3042 for (aglat = plats->aggs; aglat; aglat = aglat->next)
3043 {
3044 ipcp_value<tree> *val;
3045 if (aglat->bottom || !aglat->values
3046 /* If the following is true, the one value is in known_aggs. */
3047 || (!plats->aggs_contain_variable
3048 && aglat->is_single_const ()))
3049 continue;
3050
3051 for (val = aglat->values; val; val = val->next)
3052 {
3053 struct ipa_agg_jf_item item;
3054
3055 item.offset = aglat->offset;
3056 item.value = val->value;
3057 vec_safe_push (ajf->items, item);
3058
3059 perform_estimation_of_a_value (node, known_csts, known_contexts,
3060 known_aggs_ptrs,
3061 removable_params_cost, 0, val);
3062
3063 if (dump_file && (dump_flags & TDF_DETAILS))
3064 {
3065 fprintf (dump_file, " - estimates for value ");
3066 print_ipcp_constant_value (dump_file, val->value);
3067 fprintf (dump_file, " for ");
3068 ipa_dump_param (dump_file, info, i);
3069 fprintf (dump_file, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
3070 "]: time_benefit: %i, size: %i\n",
3071 plats->aggs_by_ref ? "ref " : "",
3072 aglat->offset,
3073 val->local_time_benefit, val->local_size_cost);
3074 }
3075
3076 ajf->items->pop ();
3077 }
3078 }
3079 }
3080
3081 for (i = 0; i < count; i++)
3082 vec_free (known_aggs[i].items);
3083
3084 known_csts.release ();
3085 known_contexts.release ();
3086 known_aggs.release ();
3087 known_aggs_ptrs.release ();
3088 }
3089
3090
3091 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
3092 topological sort of values. */
3093
3094 template <typename valtype>
3095 void
add_val(ipcp_value<valtype> * cur_val)3096 value_topo_info<valtype>::add_val (ipcp_value<valtype> *cur_val)
3097 {
3098 ipcp_value_source<valtype> *src;
3099
3100 if (cur_val->dfs)
3101 return;
3102
3103 dfs_counter++;
3104 cur_val->dfs = dfs_counter;
3105 cur_val->low_link = dfs_counter;
3106
3107 cur_val->topo_next = stack;
3108 stack = cur_val;
3109 cur_val->on_stack = true;
3110
3111 for (src = cur_val->sources; src; src = src->next)
3112 if (src->val)
3113 {
3114 if (src->val->dfs == 0)
3115 {
3116 add_val (src->val);
3117 if (src->val->low_link < cur_val->low_link)
3118 cur_val->low_link = src->val->low_link;
3119 }
3120 else if (src->val->on_stack
3121 && src->val->dfs < cur_val->low_link)
3122 cur_val->low_link = src->val->dfs;
3123 }
3124
3125 if (cur_val->dfs == cur_val->low_link)
3126 {
3127 ipcp_value<valtype> *v, *scc_list = NULL;
3128
3129 do
3130 {
3131 v = stack;
3132 stack = v->topo_next;
3133 v->on_stack = false;
3134
3135 v->scc_next = scc_list;
3136 scc_list = v;
3137 }
3138 while (v != cur_val);
3139
3140 cur_val->topo_next = values_topo;
3141 values_topo = cur_val;
3142 }
3143 }
3144
3145 /* Add all values in lattices associated with NODE to the topological sort if
3146 they are not there yet. */
3147
3148 static void
add_all_node_vals_to_toposort(cgraph_node * node,ipa_topo_info * topo)3149 add_all_node_vals_to_toposort (cgraph_node *node, ipa_topo_info *topo)
3150 {
3151 struct ipa_node_params *info = IPA_NODE_REF (node);
3152 int i, count = ipa_get_param_count (info);
3153
3154 for (i = 0; i < count; i++)
3155 {
3156 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
3157 ipcp_lattice<tree> *lat = &plats->itself;
3158 struct ipcp_agg_lattice *aglat;
3159
3160 if (!lat->bottom)
3161 {
3162 ipcp_value<tree> *val;
3163 for (val = lat->values; val; val = val->next)
3164 topo->constants.add_val (val);
3165 }
3166
3167 if (!plats->aggs_bottom)
3168 for (aglat = plats->aggs; aglat; aglat = aglat->next)
3169 if (!aglat->bottom)
3170 {
3171 ipcp_value<tree> *val;
3172 for (val = aglat->values; val; val = val->next)
3173 topo->constants.add_val (val);
3174 }
3175
3176 ipcp_lattice<ipa_polymorphic_call_context> *ctxlat = &plats->ctxlat;
3177 if (!ctxlat->bottom)
3178 {
3179 ipcp_value<ipa_polymorphic_call_context> *ctxval;
3180 for (ctxval = ctxlat->values; ctxval; ctxval = ctxval->next)
3181 topo->contexts.add_val (ctxval);
3182 }
3183 }
3184 }
3185
3186 /* One pass of constants propagation along the call graph edges, from callers
3187 to callees (requires topological ordering in TOPO), iterate over strongly
3188 connected components. */
3189
3190 static void
propagate_constants_topo(struct ipa_topo_info * topo)3191 propagate_constants_topo (struct ipa_topo_info *topo)
3192 {
3193 int i;
3194
3195 for (i = topo->nnodes - 1; i >= 0; i--)
3196 {
3197 unsigned j;
3198 struct cgraph_node *v, *node = topo->order[i];
3199 vec<cgraph_node *> cycle_nodes = ipa_get_nodes_in_cycle (node);
3200
3201 /* First, iteratively propagate within the strongly connected component
3202 until all lattices stabilize. */
3203 FOR_EACH_VEC_ELT (cycle_nodes, j, v)
3204 if (v->has_gimple_body_p ())
3205 push_node_to_stack (topo, v);
3206
3207 v = pop_node_from_stack (topo);
3208 while (v)
3209 {
3210 struct cgraph_edge *cs;
3211
3212 for (cs = v->callees; cs; cs = cs->next_callee)
3213 if (ipa_edge_within_scc (cs))
3214 {
3215 IPA_NODE_REF (v)->node_within_scc = true;
3216 if (propagate_constants_across_call (cs))
3217 push_node_to_stack (topo, cs->callee->function_symbol ());
3218 }
3219 v = pop_node_from_stack (topo);
3220 }
3221
3222 /* Afterwards, propagate along edges leading out of the SCC, calculates
3223 the local effects of the discovered constants and all valid values to
3224 their topological sort. */
3225 FOR_EACH_VEC_ELT (cycle_nodes, j, v)
3226 if (v->has_gimple_body_p ())
3227 {
3228 struct cgraph_edge *cs;
3229
3230 estimate_local_effects (v);
3231 add_all_node_vals_to_toposort (v, topo);
3232 for (cs = v->callees; cs; cs = cs->next_callee)
3233 if (!ipa_edge_within_scc (cs))
3234 propagate_constants_across_call (cs);
3235 }
3236 cycle_nodes.release ();
3237 }
3238 }
3239
3240
3241 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
3242 the bigger one if otherwise. */
3243
3244 static int
safe_add(int a,int b)3245 safe_add (int a, int b)
3246 {
3247 if (a > INT_MAX/2 || b > INT_MAX/2)
3248 return a > b ? a : b;
3249 else
3250 return a + b;
3251 }
3252
3253
3254 /* Propagate the estimated effects of individual values along the topological
3255 from the dependent values to those they depend on. */
3256
3257 template <typename valtype>
3258 void
propagate_effects()3259 value_topo_info<valtype>::propagate_effects ()
3260 {
3261 ipcp_value<valtype> *base;
3262
3263 for (base = values_topo; base; base = base->topo_next)
3264 {
3265 ipcp_value_source<valtype> *src;
3266 ipcp_value<valtype> *val;
3267 int time = 0, size = 0;
3268
3269 for (val = base; val; val = val->scc_next)
3270 {
3271 time = safe_add (time,
3272 val->local_time_benefit + val->prop_time_benefit);
3273 size = safe_add (size, val->local_size_cost + val->prop_size_cost);
3274 }
3275
3276 for (val = base; val; val = val->scc_next)
3277 for (src = val->sources; src; src = src->next)
3278 if (src->val
3279 && src->cs->maybe_hot_p ())
3280 {
3281 src->val->prop_time_benefit = safe_add (time,
3282 src->val->prop_time_benefit);
3283 src->val->prop_size_cost = safe_add (size,
3284 src->val->prop_size_cost);
3285 }
3286 }
3287 }
3288
3289
3290 /* Propagate constants, polymorphic contexts and their effects from the
3291 summaries interprocedurally. */
3292
3293 static void
ipcp_propagate_stage(struct ipa_topo_info * topo)3294 ipcp_propagate_stage (struct ipa_topo_info *topo)
3295 {
3296 struct cgraph_node *node;
3297
3298 if (dump_file)
3299 fprintf (dump_file, "\n Propagating constants:\n\n");
3300
3301 max_count = profile_count::uninitialized ();
3302
3303 FOR_EACH_DEFINED_FUNCTION (node)
3304 {
3305 struct ipa_node_params *info = IPA_NODE_REF (node);
3306
3307 determine_versionability (node, info);
3308 if (node->has_gimple_body_p ())
3309 {
3310 info->lattices = XCNEWVEC (struct ipcp_param_lattices,
3311 ipa_get_param_count (info));
3312 initialize_node_lattices (node);
3313 }
3314 if (node->definition && !node->alias)
3315 overall_size += ipa_fn_summaries->get (node)->self_size;
3316 max_count = max_count.max (node->count.ipa ());
3317 }
3318
3319 max_new_size = overall_size;
3320 if (max_new_size < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
3321 max_new_size = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
3322 max_new_size += max_new_size * PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH) / 100 + 1;
3323
3324 if (dump_file)
3325 fprintf (dump_file, "\noverall_size: %li, max_new_size: %li\n",
3326 overall_size, max_new_size);
3327
3328 propagate_constants_topo (topo);
3329 if (flag_checking)
3330 ipcp_verify_propagated_values ();
3331 topo->constants.propagate_effects ();
3332 topo->contexts.propagate_effects ();
3333
3334 if (dump_file)
3335 {
3336 fprintf (dump_file, "\nIPA lattices after all propagation:\n");
3337 print_all_lattices (dump_file, (dump_flags & TDF_DETAILS), true);
3338 }
3339 }
3340
3341 /* Discover newly direct outgoing edges from NODE which is a new clone with
3342 known KNOWN_CSTS and make them direct. */
3343
3344 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)3345 ipcp_discover_new_direct_edges (struct cgraph_node *node,
3346 vec<tree> known_csts,
3347 vec<ipa_polymorphic_call_context>
3348 known_contexts,
3349 struct ipa_agg_replacement_value *aggvals)
3350 {
3351 struct cgraph_edge *ie, *next_ie;
3352 bool found = false;
3353
3354 for (ie = node->indirect_calls; ie; ie = next_ie)
3355 {
3356 tree target;
3357 bool speculative;
3358
3359 next_ie = ie->next_callee;
3360 target = ipa_get_indirect_edge_target_1 (ie, known_csts, known_contexts,
3361 vNULL, aggvals, &speculative);
3362 if (target)
3363 {
3364 bool agg_contents = ie->indirect_info->agg_contents;
3365 bool polymorphic = ie->indirect_info->polymorphic;
3366 int param_index = ie->indirect_info->param_index;
3367 struct cgraph_edge *cs = ipa_make_edge_direct_to_target (ie, target,
3368 speculative);
3369 found = true;
3370
3371 if (cs && !agg_contents && !polymorphic)
3372 {
3373 struct ipa_node_params *info = IPA_NODE_REF (node);
3374 int c = ipa_get_controlled_uses (info, param_index);
3375 if (c != IPA_UNDESCRIBED_USE)
3376 {
3377 struct ipa_ref *to_del;
3378
3379 c--;
3380 ipa_set_controlled_uses (info, param_index, c);
3381 if (dump_file && (dump_flags & TDF_DETAILS))
3382 fprintf (dump_file, " controlled uses count of param "
3383 "%i bumped down to %i\n", param_index, c);
3384 if (c == 0
3385 && (to_del = node->find_reference (cs->callee, NULL, 0)))
3386 {
3387 if (dump_file && (dump_flags & TDF_DETAILS))
3388 fprintf (dump_file, " and even removing its "
3389 "cloning-created reference\n");
3390 to_del->remove_reference ();
3391 }
3392 }
3393 }
3394 }
3395 }
3396 /* Turning calls to direct calls will improve overall summary. */
3397 if (found)
3398 ipa_update_overall_fn_summary (node);
3399 }
3400
3401 /* Vector of pointers which for linked lists of clones of an original crgaph
3402 edge. */
3403
3404 static vec<cgraph_edge *> next_edge_clone;
3405 static vec<cgraph_edge *> prev_edge_clone;
3406
3407 static inline void
grow_edge_clone_vectors(void)3408 grow_edge_clone_vectors (void)
3409 {
3410 if (next_edge_clone.length ()
3411 <= (unsigned) symtab->edges_max_uid)
3412 next_edge_clone.safe_grow_cleared (symtab->edges_max_uid + 1);
3413 if (prev_edge_clone.length ()
3414 <= (unsigned) symtab->edges_max_uid)
3415 prev_edge_clone.safe_grow_cleared (symtab->edges_max_uid + 1);
3416 }
3417
3418 /* Edge duplication hook to grow the appropriate linked list in
3419 next_edge_clone. */
3420
3421 static void
ipcp_edge_duplication_hook(struct cgraph_edge * src,struct cgraph_edge * dst,void *)3422 ipcp_edge_duplication_hook (struct cgraph_edge *src, struct cgraph_edge *dst,
3423 void *)
3424 {
3425 grow_edge_clone_vectors ();
3426
3427 struct cgraph_edge *old_next = next_edge_clone[src->uid];
3428 if (old_next)
3429 prev_edge_clone[old_next->uid] = dst;
3430 prev_edge_clone[dst->uid] = src;
3431
3432 next_edge_clone[dst->uid] = old_next;
3433 next_edge_clone[src->uid] = dst;
3434 }
3435
3436 /* Hook that is called by cgraph.c when an edge is removed. */
3437
3438 static void
ipcp_edge_removal_hook(struct cgraph_edge * cs,void *)3439 ipcp_edge_removal_hook (struct cgraph_edge *cs, void *)
3440 {
3441 grow_edge_clone_vectors ();
3442
3443 struct cgraph_edge *prev = prev_edge_clone[cs->uid];
3444 struct cgraph_edge *next = next_edge_clone[cs->uid];
3445 if (prev)
3446 next_edge_clone[prev->uid] = next;
3447 if (next)
3448 prev_edge_clone[next->uid] = prev;
3449 }
3450
3451 /* See if NODE is a clone with a known aggregate value at a given OFFSET of a
3452 parameter with the given INDEX. */
3453
3454 static tree
get_clone_agg_value(struct cgraph_node * node,HOST_WIDE_INT offset,int index)3455 get_clone_agg_value (struct cgraph_node *node, HOST_WIDE_INT offset,
3456 int index)
3457 {
3458 struct ipa_agg_replacement_value *aggval;
3459
3460 aggval = ipa_get_agg_replacements_for_node (node);
3461 while (aggval)
3462 {
3463 if (aggval->offset == offset
3464 && aggval->index == index)
3465 return aggval->value;
3466 aggval = aggval->next;
3467 }
3468 return NULL_TREE;
3469 }
3470
3471 /* Return true is NODE is DEST or its clone for all contexts. */
3472
3473 static bool
same_node_or_its_all_contexts_clone_p(cgraph_node * node,cgraph_node * dest)3474 same_node_or_its_all_contexts_clone_p (cgraph_node *node, cgraph_node *dest)
3475 {
3476 if (node == dest)
3477 return true;
3478
3479 struct ipa_node_params *info = IPA_NODE_REF (node);
3480 return info->is_all_contexts_clone && info->ipcp_orig_node == dest;
3481 }
3482
3483 /* Return true if edge CS does bring about the value described by SRC to
3484 DEST_VAL of node DEST or its clone for all contexts. */
3485
3486 static bool
cgraph_edge_brings_value_p(cgraph_edge * cs,ipcp_value_source<tree> * src,cgraph_node * dest,ipcp_value<tree> * dest_val)3487 cgraph_edge_brings_value_p (cgraph_edge *cs, ipcp_value_source<tree> *src,
3488 cgraph_node *dest, ipcp_value<tree> *dest_val)
3489 {
3490 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
3491 enum availability availability;
3492 cgraph_node *real_dest = cs->callee->function_symbol (&availability);
3493
3494 if (!same_node_or_its_all_contexts_clone_p (real_dest, dest)
3495 || availability <= AVAIL_INTERPOSABLE
3496 || caller_info->node_dead)
3497 return false;
3498
3499 if (!src->val)
3500 return true;
3501
3502 if (caller_info->ipcp_orig_node)
3503 {
3504 tree t;
3505 if (src->offset == -1)
3506 t = caller_info->known_csts[src->index];
3507 else
3508 t = get_clone_agg_value (cs->caller, src->offset, src->index);
3509 return (t != NULL_TREE
3510 && values_equal_for_ipcp_p (src->val->value, t));
3511 }
3512 else
3513 {
3514 /* At the moment we do not propagate over arithmetic jump functions in
3515 SCCs, so it is safe to detect self-feeding recursive calls in this
3516 way. */
3517 if (src->val == dest_val)
3518 return true;
3519
3520 struct ipcp_agg_lattice *aglat;
3521 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (caller_info,
3522 src->index);
3523 if (src->offset == -1)
3524 return (plats->itself.is_single_const ()
3525 && values_equal_for_ipcp_p (src->val->value,
3526 plats->itself.values->value));
3527 else
3528 {
3529 if (plats->aggs_bottom || plats->aggs_contain_variable)
3530 return false;
3531 for (aglat = plats->aggs; aglat; aglat = aglat->next)
3532 if (aglat->offset == src->offset)
3533 return (aglat->is_single_const ()
3534 && values_equal_for_ipcp_p (src->val->value,
3535 aglat->values->value));
3536 }
3537 return false;
3538 }
3539 }
3540
3541 /* Return true if edge CS does bring about the value described by SRC to
3542 DST_VAL of node DEST or its clone for all contexts. */
3543
3544 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> *)3545 cgraph_edge_brings_value_p (cgraph_edge *cs,
3546 ipcp_value_source<ipa_polymorphic_call_context> *src,
3547 cgraph_node *dest,
3548 ipcp_value<ipa_polymorphic_call_context> *)
3549 {
3550 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
3551 cgraph_node *real_dest = cs->callee->function_symbol ();
3552
3553 if (!same_node_or_its_all_contexts_clone_p (real_dest, dest)
3554 || caller_info->node_dead)
3555 return false;
3556 if (!src->val)
3557 return true;
3558
3559 if (caller_info->ipcp_orig_node)
3560 return (caller_info->known_contexts.length () > (unsigned) src->index)
3561 && values_equal_for_ipcp_p (src->val->value,
3562 caller_info->known_contexts[src->index]);
3563
3564 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (caller_info,
3565 src->index);
3566 return plats->ctxlat.is_single_const ()
3567 && values_equal_for_ipcp_p (src->val->value,
3568 plats->ctxlat.values->value);
3569 }
3570
3571 /* Get the next clone in the linked list of clones of an edge. */
3572
3573 static inline struct cgraph_edge *
get_next_cgraph_edge_clone(struct cgraph_edge * cs)3574 get_next_cgraph_edge_clone (struct cgraph_edge *cs)
3575 {
3576 return next_edge_clone[cs->uid];
3577 }
3578
3579 /* Given VAL that is intended for DEST, iterate over all its sources and if any
3580 of them is viable and hot, return true. In that case, for those that still
3581 hold, add their edge frequency and their number into *FREQUENCY and
3582 *CALLER_COUNT respectively. */
3583
3584 template <typename valtype>
3585 static bool
get_info_about_necessary_edges(ipcp_value<valtype> * val,cgraph_node * dest,int * freq_sum,profile_count * count_sum,int * caller_count)3586 get_info_about_necessary_edges (ipcp_value<valtype> *val, cgraph_node *dest,
3587 int *freq_sum,
3588 profile_count *count_sum, int *caller_count)
3589 {
3590 ipcp_value_source<valtype> *src;
3591 int freq = 0, count = 0;
3592 profile_count cnt = profile_count::zero ();
3593 bool hot = false;
3594 bool non_self_recursive = false;
3595
3596 for (src = val->sources; src; src = src->next)
3597 {
3598 struct cgraph_edge *cs = src->cs;
3599 while (cs)
3600 {
3601 if (cgraph_edge_brings_value_p (cs, src, dest, val))
3602 {
3603 count++;
3604 freq += cs->frequency ();
3605 if (cs->count.ipa ().initialized_p ())
3606 cnt += cs->count.ipa ();
3607 hot |= cs->maybe_hot_p ();
3608 if (cs->caller != dest)
3609 non_self_recursive = true;
3610 }
3611 cs = get_next_cgraph_edge_clone (cs);
3612 }
3613 }
3614
3615 /* If the only edges bringing a value are self-recursive ones, do not bother
3616 evaluating it. */
3617 if (!non_self_recursive)
3618 return false;
3619
3620 *freq_sum = freq;
3621 *count_sum = cnt;
3622 *caller_count = count;
3623 return hot;
3624 }
3625
3626 /* Return a vector of incoming edges that do bring value VAL to node DEST. It
3627 is assumed their number is known and equal to CALLER_COUNT. */
3628
3629 template <typename valtype>
3630 static vec<cgraph_edge *>
gather_edges_for_value(ipcp_value<valtype> * val,cgraph_node * dest,int caller_count)3631 gather_edges_for_value (ipcp_value<valtype> *val, cgraph_node *dest,
3632 int caller_count)
3633 {
3634 ipcp_value_source<valtype> *src;
3635 vec<cgraph_edge *> ret;
3636
3637 ret.create (caller_count);
3638 for (src = val->sources; src; src = src->next)
3639 {
3640 struct cgraph_edge *cs = src->cs;
3641 while (cs)
3642 {
3643 if (cgraph_edge_brings_value_p (cs, src, dest, val))
3644 ret.quick_push (cs);
3645 cs = get_next_cgraph_edge_clone (cs);
3646 }
3647 }
3648
3649 return ret;
3650 }
3651
3652 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
3653 Return it or NULL if for some reason it cannot be created. */
3654
3655 static struct ipa_replace_map *
get_replacement_map(struct ipa_node_params * info,tree value,int parm_num)3656 get_replacement_map (struct ipa_node_params *info, tree value, int parm_num)
3657 {
3658 struct ipa_replace_map *replace_map;
3659
3660
3661 replace_map = ggc_alloc<ipa_replace_map> ();
3662 if (dump_file)
3663 {
3664 fprintf (dump_file, " replacing ");
3665 ipa_dump_param (dump_file, info, parm_num);
3666
3667 fprintf (dump_file, " with const ");
3668 print_generic_expr (dump_file, value);
3669 fprintf (dump_file, "\n");
3670 }
3671 replace_map->old_tree = NULL;
3672 replace_map->parm_num = parm_num;
3673 replace_map->new_tree = value;
3674 replace_map->replace_p = true;
3675 replace_map->ref_p = false;
3676
3677 return replace_map;
3678 }
3679
3680 /* Dump new profiling counts */
3681
3682 static void
dump_profile_updates(struct cgraph_node * orig_node,struct cgraph_node * new_node)3683 dump_profile_updates (struct cgraph_node *orig_node,
3684 struct cgraph_node *new_node)
3685 {
3686 struct cgraph_edge *cs;
3687
3688 fprintf (dump_file, " setting count of the specialized node to ");
3689 new_node->count.dump (dump_file);
3690 fprintf (dump_file, "\n");
3691 for (cs = new_node->callees; cs; cs = cs->next_callee)
3692 {
3693 fprintf (dump_file, " edge to %s has count ",
3694 cs->callee->name ());
3695 cs->count.dump (dump_file);
3696 fprintf (dump_file, "\n");
3697 }
3698
3699 fprintf (dump_file, " setting count of the original node to ");
3700 orig_node->count.dump (dump_file);
3701 fprintf (dump_file, "\n");
3702 for (cs = orig_node->callees; cs; cs = cs->next_callee)
3703 {
3704 fprintf (dump_file, " edge to %s is left with ",
3705 cs->callee->name ());
3706 cs->count.dump (dump_file);
3707 fprintf (dump_file, "\n");
3708 }
3709 }
3710
3711 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
3712 their profile information to reflect this. */
3713
3714 static void
update_profiling_info(struct cgraph_node * orig_node,struct cgraph_node * new_node)3715 update_profiling_info (struct cgraph_node *orig_node,
3716 struct cgraph_node *new_node)
3717 {
3718 struct cgraph_edge *cs;
3719 struct caller_statistics stats;
3720 profile_count new_sum, orig_sum;
3721 profile_count remainder, orig_node_count = orig_node->count;
3722
3723 if (!(orig_node_count.ipa () > profile_count::zero ()))
3724 return;
3725
3726 init_caller_stats (&stats);
3727 orig_node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats,
3728 false);
3729 orig_sum = stats.count_sum;
3730 init_caller_stats (&stats);
3731 new_node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats,
3732 false);
3733 new_sum = stats.count_sum;
3734
3735 if (orig_node_count < orig_sum + new_sum)
3736 {
3737 if (dump_file)
3738 {
3739 fprintf (dump_file, " Problem: node %s has too low count ",
3740 orig_node->dump_name ());
3741 orig_node_count.dump (dump_file);
3742 fprintf (dump_file, "while the sum of incoming count is ");
3743 (orig_sum + new_sum).dump (dump_file);
3744 fprintf (dump_file, "\n");
3745 }
3746
3747 orig_node_count = (orig_sum + new_sum).apply_scale (12, 10);
3748 if (dump_file)
3749 {
3750 fprintf (dump_file, " proceeding by pretending it was ");
3751 orig_node_count.dump (dump_file);
3752 fprintf (dump_file, "\n");
3753 }
3754 }
3755
3756 remainder = orig_node_count.combine_with_ipa_count (orig_node_count.ipa ()
3757 - new_sum.ipa ());
3758 new_sum = orig_node_count.combine_with_ipa_count (new_sum);
3759 orig_node->count = remainder;
3760
3761 for (cs = new_node->callees; cs; cs = cs->next_callee)
3762 cs->count = cs->count.apply_scale (new_sum, orig_node_count);
3763
3764 for (cs = orig_node->callees; cs; cs = cs->next_callee)
3765 cs->count = cs->count.apply_scale (remainder, orig_node_count);
3766
3767 if (dump_file)
3768 dump_profile_updates (orig_node, new_node);
3769 }
3770
3771 /* Update the respective profile of specialized NEW_NODE and the original
3772 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
3773 have been redirected to the specialized version. */
3774
3775 static void
update_specialized_profile(struct cgraph_node * new_node,struct cgraph_node * orig_node,profile_count redirected_sum)3776 update_specialized_profile (struct cgraph_node *new_node,
3777 struct cgraph_node *orig_node,
3778 profile_count redirected_sum)
3779 {
3780 struct cgraph_edge *cs;
3781 profile_count new_node_count, orig_node_count = orig_node->count;
3782
3783 if (dump_file)
3784 {
3785 fprintf (dump_file, " the sum of counts of redirected edges is ");
3786 redirected_sum.dump (dump_file);
3787 fprintf (dump_file, "\n");
3788 }
3789 if (!(orig_node_count > profile_count::zero ()))
3790 return;
3791
3792 gcc_assert (orig_node_count >= redirected_sum);
3793
3794 new_node_count = new_node->count;
3795 new_node->count += redirected_sum;
3796 orig_node->count -= redirected_sum;
3797
3798 for (cs = new_node->callees; cs; cs = cs->next_callee)
3799 cs->count += cs->count.apply_scale (redirected_sum, new_node_count);
3800
3801 for (cs = orig_node->callees; cs; cs = cs->next_callee)
3802 {
3803 profile_count dec = cs->count.apply_scale (redirected_sum,
3804 orig_node_count);
3805 cs->count -= dec;
3806 }
3807
3808 if (dump_file)
3809 dump_profile_updates (orig_node, new_node);
3810 }
3811
3812 /* Create a specialized version of NODE with known constants in KNOWN_CSTS,
3813 known contexts in KNOWN_CONTEXTS and known aggregate values in AGGVALS and
3814 redirect all edges in CALLERS to it. */
3815
3816 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)3817 create_specialized_node (struct cgraph_node *node,
3818 vec<tree> known_csts,
3819 vec<ipa_polymorphic_call_context> known_contexts,
3820 struct ipa_agg_replacement_value *aggvals,
3821 vec<cgraph_edge *> callers)
3822 {
3823 struct ipa_node_params *new_info, *info = IPA_NODE_REF (node);
3824 vec<ipa_replace_map *, va_gc> *replace_trees = NULL;
3825 struct ipa_agg_replacement_value *av;
3826 struct cgraph_node *new_node;
3827 int i, count = ipa_get_param_count (info);
3828 bitmap args_to_skip;
3829
3830 gcc_assert (!info->ipcp_orig_node);
3831
3832 if (node->local.can_change_signature)
3833 {
3834 args_to_skip = BITMAP_GGC_ALLOC ();
3835 for (i = 0; i < count; i++)
3836 {
3837 tree t = known_csts[i];
3838
3839 if (t || !ipa_is_param_used (info, i))
3840 bitmap_set_bit (args_to_skip, i);
3841 }
3842 }
3843 else
3844 {
3845 args_to_skip = NULL;
3846 if (dump_file && (dump_flags & TDF_DETAILS))
3847 fprintf (dump_file, " cannot change function signature\n");
3848 }
3849
3850 for (i = 0; i < count; i++)
3851 {
3852 tree t = known_csts[i];
3853 if (t)
3854 {
3855 struct ipa_replace_map *replace_map;
3856
3857 gcc_checking_assert (TREE_CODE (t) != TREE_BINFO);
3858 replace_map = get_replacement_map (info, t, i);
3859 if (replace_map)
3860 vec_safe_push (replace_trees, replace_map);
3861 }
3862 }
3863 auto_vec<cgraph_edge *, 2> self_recursive_calls;
3864 for (i = callers.length () - 1; i >= 0; i--)
3865 {
3866 cgraph_edge *cs = callers[i];
3867 if (cs->caller == node)
3868 {
3869 self_recursive_calls.safe_push (cs);
3870 callers.unordered_remove (i);
3871 }
3872 }
3873
3874 new_node = node->create_virtual_clone (callers, replace_trees,
3875 args_to_skip, "constprop");
3876
3877 bool have_self_recursive_calls = !self_recursive_calls.is_empty ();
3878 for (unsigned j = 0; j < self_recursive_calls.length (); j++)
3879 {
3880 cgraph_edge *cs = next_edge_clone[self_recursive_calls[j]->uid];
3881 /* Cloned edges can disappear during cloning as speculation can be
3882 resolved, check that we have one and that it comes from the last
3883 cloning. */
3884 if (cs && cs->caller == new_node)
3885 cs->redirect_callee_duplicating_thunks (new_node);
3886 /* Any future code that would make more than one clone of an outgoing
3887 edge would confuse this mechanism, so let's check that does not
3888 happen. */
3889 gcc_checking_assert (!cs
3890 || !next_edge_clone[cs->uid]
3891 || next_edge_clone[cs->uid]->caller != new_node);
3892 }
3893 if (have_self_recursive_calls)
3894 new_node->expand_all_artificial_thunks ();
3895
3896 ipa_set_node_agg_value_chain (new_node, aggvals);
3897 for (av = aggvals; av; av = av->next)
3898 new_node->maybe_create_reference (av->value, NULL);
3899
3900 if (dump_file && (dump_flags & TDF_DETAILS))
3901 {
3902 fprintf (dump_file, " the new node is %s.\n", new_node->dump_name ());
3903 if (known_contexts.exists ())
3904 {
3905 for (i = 0; i < count; i++)
3906 if (!known_contexts[i].useless_p ())
3907 {
3908 fprintf (dump_file, " known ctx %i is ", i);
3909 known_contexts[i].dump (dump_file);
3910 }
3911 }
3912 if (aggvals)
3913 ipa_dump_agg_replacement_values (dump_file, aggvals);
3914 }
3915 ipa_check_create_node_params ();
3916 update_profiling_info (node, new_node);
3917 new_info = IPA_NODE_REF (new_node);
3918 new_info->ipcp_orig_node = node;
3919 new_info->known_csts = known_csts;
3920 new_info->known_contexts = known_contexts;
3921
3922 ipcp_discover_new_direct_edges (new_node, known_csts, known_contexts, aggvals);
3923
3924 callers.release ();
3925 return new_node;
3926 }
3927
3928 /* Return true, if JFUNC, which describes a i-th parameter of call CS, is a
3929 simple no-operation pass-through function to itself. */
3930
3931 static bool
self_recursive_pass_through_p(cgraph_edge * cs,ipa_jump_func * jfunc,int i)3932 self_recursive_pass_through_p (cgraph_edge *cs, ipa_jump_func *jfunc, int i)
3933 {
3934 enum availability availability;
3935 if (cs->caller == cs->callee->function_symbol (&availability)
3936 && availability > AVAIL_INTERPOSABLE
3937 && jfunc->type == IPA_JF_PASS_THROUGH
3938 && ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR
3939 && ipa_get_jf_pass_through_formal_id (jfunc) == i)
3940 return true;
3941 return false;
3942 }
3943
3944 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
3945 KNOWN_CSTS with constants that are also known for all of the CALLERS. */
3946
3947 static void
find_more_scalar_values_for_callers_subset(struct cgraph_node * node,vec<tree> known_csts,vec<cgraph_edge * > callers)3948 find_more_scalar_values_for_callers_subset (struct cgraph_node *node,
3949 vec<tree> known_csts,
3950 vec<cgraph_edge *> callers)
3951 {
3952 struct ipa_node_params *info = IPA_NODE_REF (node);
3953 int i, count = ipa_get_param_count (info);
3954
3955 for (i = 0; i < count; i++)
3956 {
3957 struct cgraph_edge *cs;
3958 tree newval = NULL_TREE;
3959 int j;
3960 bool first = true;
3961 tree type = ipa_get_type (info, i);
3962
3963 if (ipa_get_scalar_lat (info, i)->bottom || known_csts[i])
3964 continue;
3965
3966 FOR_EACH_VEC_ELT (callers, j, cs)
3967 {
3968 struct ipa_jump_func *jump_func;
3969 tree t;
3970
3971 if (IPA_NODE_REF (cs->caller)->node_dead)
3972 continue;
3973
3974 if (i >= ipa_get_cs_argument_count (IPA_EDGE_REF (cs))
3975 || (i == 0
3976 && call_passes_through_thunk_p (cs))
3977 || (!cs->callee->instrumentation_clone
3978 && cs->callee->function_symbol ()->instrumentation_clone))
3979 {
3980 newval = NULL_TREE;
3981 break;
3982 }
3983 jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
3984 if (self_recursive_pass_through_p (cs, jump_func, i))
3985 continue;
3986
3987 t = ipa_value_from_jfunc (IPA_NODE_REF (cs->caller), jump_func, type);
3988 if (!t
3989 || (newval
3990 && !values_equal_for_ipcp_p (t, newval))
3991 || (!first && !newval))
3992 {
3993 newval = NULL_TREE;
3994 break;
3995 }
3996 else
3997 newval = t;
3998 first = false;
3999 }
4000
4001 if (newval)
4002 {
4003 if (dump_file && (dump_flags & TDF_DETAILS))
4004 {
4005 fprintf (dump_file, " adding an extra known scalar value ");
4006 print_ipcp_constant_value (dump_file, newval);
4007 fprintf (dump_file, " for ");
4008 ipa_dump_param (dump_file, info, i);
4009 fprintf (dump_file, "\n");
4010 }
4011
4012 known_csts[i] = newval;
4013 }
4014 }
4015 }
4016
4017 /* Given a NODE and a subset of its CALLERS, try to populate plank slots in
4018 KNOWN_CONTEXTS with polymorphic contexts that are also known for all of the
4019 CALLERS. */
4020
4021 static void
find_more_contexts_for_caller_subset(cgraph_node * node,vec<ipa_polymorphic_call_context> * known_contexts,vec<cgraph_edge * > callers)4022 find_more_contexts_for_caller_subset (cgraph_node *node,
4023 vec<ipa_polymorphic_call_context>
4024 *known_contexts,
4025 vec<cgraph_edge *> callers)
4026 {
4027 ipa_node_params *info = IPA_NODE_REF (node);
4028 int i, count = ipa_get_param_count (info);
4029
4030 for (i = 0; i < count; i++)
4031 {
4032 cgraph_edge *cs;
4033
4034 if (ipa_get_poly_ctx_lat (info, i)->bottom
4035 || (known_contexts->exists ()
4036 && !(*known_contexts)[i].useless_p ()))
4037 continue;
4038
4039 ipa_polymorphic_call_context newval;
4040 bool first = true;
4041 int j;
4042
4043 FOR_EACH_VEC_ELT (callers, j, cs)
4044 {
4045 if (i >= ipa_get_cs_argument_count (IPA_EDGE_REF (cs)))
4046 return;
4047 ipa_jump_func *jfunc = ipa_get_ith_jump_func (IPA_EDGE_REF (cs),
4048 i);
4049 ipa_polymorphic_call_context ctx;
4050 ctx = ipa_context_from_jfunc (IPA_NODE_REF (cs->caller), cs, i,
4051 jfunc);
4052 if (first)
4053 {
4054 newval = ctx;
4055 first = false;
4056 }
4057 else
4058 newval.meet_with (ctx);
4059 if (newval.useless_p ())
4060 break;
4061 }
4062
4063 if (!newval.useless_p ())
4064 {
4065 if (dump_file && (dump_flags & TDF_DETAILS))
4066 {
4067 fprintf (dump_file, " adding an extra known polymorphic "
4068 "context ");
4069 print_ipcp_constant_value (dump_file, newval);
4070 fprintf (dump_file, " for ");
4071 ipa_dump_param (dump_file, info, i);
4072 fprintf (dump_file, "\n");
4073 }
4074
4075 if (!known_contexts->exists ())
4076 known_contexts->safe_grow_cleared (ipa_get_param_count (info));
4077 (*known_contexts)[i] = newval;
4078 }
4079
4080 }
4081 }
4082
4083 /* Go through PLATS and create a vector of values consisting of values and
4084 offsets (minus OFFSET) of lattices that contain only a single value. */
4085
4086 static vec<ipa_agg_jf_item>
copy_plats_to_inter(struct ipcp_param_lattices * plats,HOST_WIDE_INT offset)4087 copy_plats_to_inter (struct ipcp_param_lattices *plats, HOST_WIDE_INT offset)
4088 {
4089 vec<ipa_agg_jf_item> res = vNULL;
4090
4091 if (!plats->aggs || plats->aggs_contain_variable || plats->aggs_bottom)
4092 return vNULL;
4093
4094 for (struct ipcp_agg_lattice *aglat = plats->aggs; aglat; aglat = aglat->next)
4095 if (aglat->is_single_const ())
4096 {
4097 struct ipa_agg_jf_item ti;
4098 ti.offset = aglat->offset - offset;
4099 ti.value = aglat->values->value;
4100 res.safe_push (ti);
4101 }
4102 return res;
4103 }
4104
4105 /* Intersect all values in INTER with single value lattices in PLATS (while
4106 subtracting OFFSET). */
4107
4108 static void
intersect_with_plats(struct ipcp_param_lattices * plats,vec<ipa_agg_jf_item> * inter,HOST_WIDE_INT offset)4109 intersect_with_plats (struct ipcp_param_lattices *plats,
4110 vec<ipa_agg_jf_item> *inter,
4111 HOST_WIDE_INT offset)
4112 {
4113 struct ipcp_agg_lattice *aglat;
4114 struct ipa_agg_jf_item *item;
4115 int k;
4116
4117 if (!plats->aggs || plats->aggs_contain_variable || plats->aggs_bottom)
4118 {
4119 inter->release ();
4120 return;
4121 }
4122
4123 aglat = plats->aggs;
4124 FOR_EACH_VEC_ELT (*inter, k, item)
4125 {
4126 bool found = false;
4127 if (!item->value)
4128 continue;
4129 while (aglat)
4130 {
4131 if (aglat->offset - offset > item->offset)
4132 break;
4133 if (aglat->offset - offset == item->offset)
4134 {
4135 gcc_checking_assert (item->value);
4136 if (aglat->is_single_const ()
4137 && values_equal_for_ipcp_p (item->value,
4138 aglat->values->value))
4139 found = true;
4140 break;
4141 }
4142 aglat = aglat->next;
4143 }
4144 if (!found)
4145 item->value = NULL_TREE;
4146 }
4147 }
4148
4149 /* Copy aggregate replacement values of NODE (which is an IPA-CP clone) to the
4150 vector result while subtracting OFFSET from the individual value offsets. */
4151
4152 static vec<ipa_agg_jf_item>
agg_replacements_to_vector(struct cgraph_node * node,int index,HOST_WIDE_INT offset)4153 agg_replacements_to_vector (struct cgraph_node *node, int index,
4154 HOST_WIDE_INT offset)
4155 {
4156 struct ipa_agg_replacement_value *av;
4157 vec<ipa_agg_jf_item> res = vNULL;
4158
4159 for (av = ipa_get_agg_replacements_for_node (node); av; av = av->next)
4160 if (av->index == index
4161 && (av->offset - offset) >= 0)
4162 {
4163 struct ipa_agg_jf_item item;
4164 gcc_checking_assert (av->value);
4165 item.offset = av->offset - offset;
4166 item.value = av->value;
4167 res.safe_push (item);
4168 }
4169
4170 return res;
4171 }
4172
4173 /* Intersect all values in INTER with those that we have already scheduled to
4174 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone
4175 (while subtracting OFFSET). */
4176
4177 static void
intersect_with_agg_replacements(struct cgraph_node * node,int index,vec<ipa_agg_jf_item> * inter,HOST_WIDE_INT offset)4178 intersect_with_agg_replacements (struct cgraph_node *node, int index,
4179 vec<ipa_agg_jf_item> *inter,
4180 HOST_WIDE_INT offset)
4181 {
4182 struct ipa_agg_replacement_value *srcvals;
4183 struct ipa_agg_jf_item *item;
4184 int i;
4185
4186 srcvals = ipa_get_agg_replacements_for_node (node);
4187 if (!srcvals)
4188 {
4189 inter->release ();
4190 return;
4191 }
4192
4193 FOR_EACH_VEC_ELT (*inter, i, item)
4194 {
4195 struct ipa_agg_replacement_value *av;
4196 bool found = false;
4197 if (!item->value)
4198 continue;
4199 for (av = srcvals; av; av = av->next)
4200 {
4201 gcc_checking_assert (av->value);
4202 if (av->index == index
4203 && av->offset - offset == item->offset)
4204 {
4205 if (values_equal_for_ipcp_p (item->value, av->value))
4206 found = true;
4207 break;
4208 }
4209 }
4210 if (!found)
4211 item->value = NULL_TREE;
4212 }
4213 }
4214
4215 /* Intersect values in INTER with aggregate values that come along edge CS to
4216 parameter number INDEX and return it. If INTER does not actually exist yet,
4217 copy all incoming values to it. If we determine we ended up with no values
4218 whatsoever, return a released vector. */
4219
4220 static vec<ipa_agg_jf_item>
intersect_aggregates_with_edge(struct cgraph_edge * cs,int index,vec<ipa_agg_jf_item> inter)4221 intersect_aggregates_with_edge (struct cgraph_edge *cs, int index,
4222 vec<ipa_agg_jf_item> inter)
4223 {
4224 struct ipa_jump_func *jfunc;
4225 jfunc = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), index);
4226 if (jfunc->type == IPA_JF_PASS_THROUGH
4227 && ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
4228 {
4229 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
4230 int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
4231
4232 if (caller_info->ipcp_orig_node)
4233 {
4234 struct cgraph_node *orig_node = caller_info->ipcp_orig_node;
4235 struct ipcp_param_lattices *orig_plats;
4236 orig_plats = ipa_get_parm_lattices (IPA_NODE_REF (orig_node),
4237 src_idx);
4238 if (agg_pass_through_permissible_p (orig_plats, jfunc))
4239 {
4240 if (!inter.exists ())
4241 inter = agg_replacements_to_vector (cs->caller, src_idx, 0);
4242 else
4243 intersect_with_agg_replacements (cs->caller, src_idx,
4244 &inter, 0);
4245 }
4246 else
4247 {
4248 inter.release ();
4249 return vNULL;
4250 }
4251 }
4252 else
4253 {
4254 struct ipcp_param_lattices *src_plats;
4255 src_plats = ipa_get_parm_lattices (caller_info, src_idx);
4256 if (agg_pass_through_permissible_p (src_plats, jfunc))
4257 {
4258 /* Currently we do not produce clobber aggregate jump
4259 functions, adjust when we do. */
4260 gcc_checking_assert (!jfunc->agg.items);
4261 if (!inter.exists ())
4262 inter = copy_plats_to_inter (src_plats, 0);
4263 else
4264 intersect_with_plats (src_plats, &inter, 0);
4265 }
4266 else
4267 {
4268 inter.release ();
4269 return vNULL;
4270 }
4271 }
4272 }
4273 else if (jfunc->type == IPA_JF_ANCESTOR
4274 && ipa_get_jf_ancestor_agg_preserved (jfunc))
4275 {
4276 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
4277 int src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
4278 struct ipcp_param_lattices *src_plats;
4279 HOST_WIDE_INT delta = ipa_get_jf_ancestor_offset (jfunc);
4280
4281 if (caller_info->ipcp_orig_node)
4282 {
4283 if (!inter.exists ())
4284 inter = agg_replacements_to_vector (cs->caller, src_idx, delta);
4285 else
4286 intersect_with_agg_replacements (cs->caller, src_idx, &inter,
4287 delta);
4288 }
4289 else
4290 {
4291 src_plats = ipa_get_parm_lattices (caller_info, src_idx);
4292 /* Currently we do not produce clobber aggregate jump
4293 functions, adjust when we do. */
4294 gcc_checking_assert (!src_plats->aggs || !jfunc->agg.items);
4295 if (!inter.exists ())
4296 inter = copy_plats_to_inter (src_plats, delta);
4297 else
4298 intersect_with_plats (src_plats, &inter, delta);
4299 }
4300 }
4301 else if (jfunc->agg.items)
4302 {
4303 struct ipa_agg_jf_item *item;
4304 int k;
4305
4306 if (!inter.exists ())
4307 for (unsigned i = 0; i < jfunc->agg.items->length (); i++)
4308 inter.safe_push ((*jfunc->agg.items)[i]);
4309 else
4310 FOR_EACH_VEC_ELT (inter, k, item)
4311 {
4312 int l = 0;
4313 bool found = false;
4314
4315 if (!item->value)
4316 continue;
4317
4318 while ((unsigned) l < jfunc->agg.items->length ())
4319 {
4320 struct ipa_agg_jf_item *ti;
4321 ti = &(*jfunc->agg.items)[l];
4322 if (ti->offset > item->offset)
4323 break;
4324 if (ti->offset == item->offset)
4325 {
4326 gcc_checking_assert (ti->value);
4327 if (values_equal_for_ipcp_p (item->value,
4328 ti->value))
4329 found = true;
4330 break;
4331 }
4332 l++;
4333 }
4334 if (!found)
4335 item->value = NULL;
4336 }
4337 }
4338 else
4339 {
4340 inter.release ();
4341 return vec<ipa_agg_jf_item>();
4342 }
4343 return inter;
4344 }
4345
4346 /* Look at edges in CALLERS and collect all known aggregate values that arrive
4347 from all of them. */
4348
4349 static struct ipa_agg_replacement_value *
find_aggregate_values_for_callers_subset(struct cgraph_node * node,vec<cgraph_edge * > callers)4350 find_aggregate_values_for_callers_subset (struct cgraph_node *node,
4351 vec<cgraph_edge *> callers)
4352 {
4353 struct ipa_node_params *dest_info = IPA_NODE_REF (node);
4354 struct ipa_agg_replacement_value *res;
4355 struct ipa_agg_replacement_value **tail = &res;
4356 struct cgraph_edge *cs;
4357 int i, j, count = ipa_get_param_count (dest_info);
4358
4359 FOR_EACH_VEC_ELT (callers, j, cs)
4360 {
4361 int c = ipa_get_cs_argument_count (IPA_EDGE_REF (cs));
4362 if (c < count)
4363 count = c;
4364 }
4365
4366 for (i = 0; i < count; i++)
4367 {
4368 struct cgraph_edge *cs;
4369 vec<ipa_agg_jf_item> inter = vNULL;
4370 struct ipa_agg_jf_item *item;
4371 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (dest_info, i);
4372 int j;
4373
4374 /* Among other things, the following check should deal with all by_ref
4375 mismatches. */
4376 if (plats->aggs_bottom)
4377 continue;
4378
4379 FOR_EACH_VEC_ELT (callers, j, cs)
4380 {
4381 struct ipa_jump_func *jfunc
4382 = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
4383 if (self_recursive_pass_through_p (cs, jfunc, i)
4384 && (!plats->aggs_by_ref
4385 || ipa_get_jf_pass_through_agg_preserved (jfunc)))
4386 continue;
4387 inter = intersect_aggregates_with_edge (cs, i, inter);
4388
4389 if (!inter.exists ())
4390 goto next_param;
4391 }
4392
4393 FOR_EACH_VEC_ELT (inter, j, item)
4394 {
4395 struct ipa_agg_replacement_value *v;
4396
4397 if (!item->value)
4398 continue;
4399
4400 v = ggc_alloc<ipa_agg_replacement_value> ();
4401 v->index = i;
4402 v->offset = item->offset;
4403 v->value = item->value;
4404 v->by_ref = plats->aggs_by_ref;
4405 *tail = v;
4406 tail = &v->next;
4407 }
4408
4409 next_param:
4410 if (inter.exists ())
4411 inter.release ();
4412 }
4413 *tail = NULL;
4414 return res;
4415 }
4416
4417 /* Determine whether CS also brings all scalar values that the NODE is
4418 specialized for. */
4419
4420 static bool
cgraph_edge_brings_all_scalars_for_node(struct cgraph_edge * cs,struct cgraph_node * node)4421 cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge *cs,
4422 struct cgraph_node *node)
4423 {
4424 struct ipa_node_params *dest_info = IPA_NODE_REF (node);
4425 int count = ipa_get_param_count (dest_info);
4426 struct ipa_node_params *caller_info;
4427 struct ipa_edge_args *args;
4428 int i;
4429
4430 caller_info = IPA_NODE_REF (cs->caller);
4431 args = IPA_EDGE_REF (cs);
4432 for (i = 0; i < count; i++)
4433 {
4434 struct ipa_jump_func *jump_func;
4435 tree val, t;
4436
4437 val = dest_info->known_csts[i];
4438 if (!val)
4439 continue;
4440
4441 if (i >= ipa_get_cs_argument_count (args))
4442 return false;
4443 jump_func = ipa_get_ith_jump_func (args, i);
4444 t = ipa_value_from_jfunc (caller_info, jump_func,
4445 ipa_get_type (dest_info, i));
4446 if (!t || !values_equal_for_ipcp_p (val, t))
4447 return false;
4448 }
4449 return true;
4450 }
4451
4452 /* Determine whether CS also brings all aggregate values that NODE is
4453 specialized for. */
4454 static bool
cgraph_edge_brings_all_agg_vals_for_node(struct cgraph_edge * cs,struct cgraph_node * node)4455 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge *cs,
4456 struct cgraph_node *node)
4457 {
4458 struct ipa_node_params *orig_caller_info = IPA_NODE_REF (cs->caller);
4459 struct ipa_node_params *orig_node_info;
4460 struct ipa_agg_replacement_value *aggval;
4461 int i, ec, count;
4462
4463 aggval = ipa_get_agg_replacements_for_node (node);
4464 if (!aggval)
4465 return true;
4466
4467 count = ipa_get_param_count (IPA_NODE_REF (node));
4468 ec = ipa_get_cs_argument_count (IPA_EDGE_REF (cs));
4469 if (ec < count)
4470 for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next)
4471 if (aggval->index >= ec)
4472 return false;
4473
4474 orig_node_info = IPA_NODE_REF (IPA_NODE_REF (node)->ipcp_orig_node);
4475 if (orig_caller_info->ipcp_orig_node)
4476 orig_caller_info = IPA_NODE_REF (orig_caller_info->ipcp_orig_node);
4477
4478 for (i = 0; i < count; i++)
4479 {
4480 struct ipcp_param_lattices *plats;
4481 bool interesting = false;
4482 for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next)
4483 if (aggval->index == i)
4484 {
4485 interesting = true;
4486 break;
4487 }
4488 if (!interesting)
4489 continue;
4490
4491 plats = ipa_get_parm_lattices (orig_node_info, aggval->index);
4492 if (plats->aggs_bottom)
4493 return false;
4494
4495 vec<ipa_agg_jf_item> values
4496 = intersect_aggregates_with_edge (cs, i, vNULL);
4497 if (!values.exists ())
4498 return false;
4499
4500 for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next)
4501 if (aggval->index == i)
4502 {
4503 struct ipa_agg_jf_item *item;
4504 int j;
4505 bool found = false;
4506 FOR_EACH_VEC_ELT (values, j, item)
4507 if (item->value
4508 && item->offset == av->offset
4509 && values_equal_for_ipcp_p (item->value, av->value))
4510 {
4511 found = true;
4512 break;
4513 }
4514 if (!found)
4515 {
4516 values.release ();
4517 return false;
4518 }
4519 }
4520 values.release ();
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