1/* Interprocedural constant propagation
2 Copyright (C) 2005-2017 Free Software Foundation, Inc.
3
4 Contributed by Razya Ladelsky <RAZYA@il.ibm.com> and Martin Jambor
5 <mjambor@suse.cz>
6
7This file is part of GCC.
8
9GCC is free software; you can redistribute it and/or modify it under
10the terms of the GNU General Public License as published by the Free
11Software Foundation; either version 3, or (at your option) any later
12version.
13
14GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15WARRANTY; without even the implied warranty of MERCHANTABILITY or
16FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17for more details.
18
19You should have received a copy of the GNU General Public License
20along 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
128template <typename valtype> class ipcp_value;
129
130/* Describes a particular source for an IPA-CP value. */
131
132template <typename valtype>
133class ipcp_value_source
134{
135public:
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
155class ipcp_value_base
156{
157public:
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
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
172template <typename valtype>
173class ipcp_value : public ipcp_value_base
174{
175public:
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
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
211template <typename valtype>
212class ipcp_lattice
213{
214public:
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
239class ipcp_agg_lattice : public ipcp_lattice<tree>
240{
241public:
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
274class ipcp_bits_lattice
275{
276public:
277 bool bottom_p () { return m_lattice_val == IPA_BITS_VARYING; }
278 bool top_p () { return m_lattice_val == IPA_BITS_UNDEFINED; }
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
283 widest_int get_value () { return m_value; }
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
293private:
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
307class ipcp_vr_lattice
308{
309public:
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);
317 void init () { m_vr.type = VR_UNDEFINED; }
318 void print (FILE * f);
319
320private:
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
328class ipcp_param_lattices
329{
330public:
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
359object_allocator<ipcp_value<tree> > ipcp_cst_values_pool
360 ("IPA-CP constant values");
361
362object_allocator<ipcp_value<ipa_polymorphic_call_context> >
363 ipcp_poly_ctx_values_pool ("IPA-CP polymorphic contexts");
364
365object_allocator<ipcp_value_source<tree> > ipcp_sources_pool
366 ("IPA-CP value sources");
367
368object_allocator<ipcp_agg_lattice> ipcp_agg_lattice_pool
369 ("IPA_CP aggregate lattices");
370
371/* Maximal count found in program. */
372
373static profile_count max_count;
374
375/* Original overall size of the program. */
376
377static 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. */
381static inline struct ipcp_param_lattices *
382ipa_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. */
392static inline ipcp_lattice<tree> *
393ipa_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. */
401static inline ipcp_lattice<ipa_polymorphic_call_context> *
402ipa_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
411static inline ipcp_vr_lattice *
412ipa_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
421template <typename valtype>
422inline bool
423ipcp_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
433static void
434print_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
448static void
449print_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
456template <typename valtype>
457void
458ipcp_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
515void
516ipcp_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
532void
533ipcp_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
540static void
541print_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
590static void
591determine_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 if (reason && dump_file && !node->alias && !node->thunk.thunk_p)
634 fprintf (dump_file, "Function %s is not versionable, reason: %s.\n",
635 node->dump_name (), reason);
636
637 info->versionable = (reason == NULL);
638}
639
640/* Return true if it is at all technically possible to create clones of a
641 NODE. */
642
643static bool
644ipcp_versionable_function_p (struct cgraph_node *node)
645{
646 return IPA_NODE_REF (node)->versionable;
647}
648
649/* Structure holding accumulated information about callers of a node. */
650
651struct caller_statistics
652{
653 profile_count count_sum;
654 int n_calls, n_hot_calls, freq_sum;
655};
656
657/* Initialize fields of STAT to zeroes. */
658
659static inline void
660init_caller_stats (struct caller_statistics *stats)
661{
662 stats->count_sum = profile_count::zero ();
663 stats->n_calls = 0;
664 stats->n_hot_calls = 0;
665 stats->freq_sum = 0;
666}
667
668/* Worker callback of cgraph_for_node_and_aliases accumulating statistics of
669 non-thunk incoming edges to NODE. */
670
671static bool
672gather_caller_stats (struct cgraph_node *node, void *data)
673{
674 struct caller_statistics *stats = (struct caller_statistics *) data;
675 struct cgraph_edge *cs;
676
677 for (cs = node->callers; cs; cs = cs->next_caller)
678 if (!cs->caller->thunk.thunk_p)
679 {
680 if (cs->count.ipa ().initialized_p ())
681 stats->count_sum += cs->count.ipa ();
682 stats->freq_sum += cs->frequency ();
683 stats->n_calls++;
684 if (cs->maybe_hot_p ())
685 stats->n_hot_calls ++;
686 }
687 return false;
688
689}
690
691/* Return true if this NODE is viable candidate for cloning. */
692
693static bool
694ipcp_cloning_candidate_p (struct cgraph_node *node)
695{
696 struct caller_statistics stats;
697
698 gcc_checking_assert (node->has_gimple_body_p ());
699
700 if (!opt_for_fn (node->decl, flag_ipa_cp_clone))
701 {
702 if (dump_file)
703 fprintf (dump_file, "Not considering %s for cloning; "
704 "-fipa-cp-clone disabled.\n",
705 node->name ());
706 return false;
707 }
708
709 if (node->optimize_for_size_p ())
710 {
711 if (dump_file)
712 fprintf (dump_file, "Not considering %s for cloning; "
713 "optimizing it for size.\n",
714 node->name ());
715 return false;
716 }
717
718 init_caller_stats (&stats);
719 node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats, false);
720
721 if (ipa_fn_summaries->get (node)->self_size < stats.n_calls)
722 {
723 if (dump_file)
724 fprintf (dump_file, "Considering %s for cloning; code might shrink.\n",
725 node->name ());
726 return true;
727 }
728
729 /* When profile is available and function is hot, propagate into it even if
730 calls seems cold; constant propagation can improve function's speed
731 significantly. */
732 if (max_count > profile_count::zero ())
733 {
734 if (stats.count_sum > node->count.ipa ().apply_scale (90, 100))
735 {
736 if (dump_file)
737 fprintf (dump_file, "Considering %s for cloning; "
738 "usually called directly.\n",
739 node->name ());
740 return true;
741 }
742 }
743 if (!stats.n_hot_calls)
744 {
745 if (dump_file)
746 fprintf (dump_file, "Not considering %s for cloning; no hot calls.\n",
747 node->name ());
748 return false;
749 }
750 if (dump_file)
751 fprintf (dump_file, "Considering %s for cloning.\n",
752 node->name ());
753 return true;
754}
755
756template <typename valtype>
757class value_topo_info
758{
759public:
760 /* Head of the linked list of topologically sorted values. */
761 ipcp_value<valtype> *values_topo;
762 /* Stack for creating SCCs, represented by a linked list too. */
763 ipcp_value<valtype> *stack;
764 /* Counter driving the algorithm in add_val_to_toposort. */
765 int dfs_counter;
766
767 value_topo_info () : values_topo (NULL), stack (NULL), dfs_counter (0)
768 {}
769 void add_val (ipcp_value<valtype> *cur_val);
770 void propagate_effects ();
771};
772
773/* Arrays representing a topological ordering of call graph nodes and a stack
774 of nodes used during constant propagation and also data required to perform
775 topological sort of values and propagation of benefits in the determined
776 order. */
777
778class ipa_topo_info
779{
780public:
781 /* Array with obtained topological order of cgraph nodes. */
782 struct cgraph_node **order;
783 /* Stack of cgraph nodes used during propagation within SCC until all values
784 in the SCC stabilize. */
785 struct cgraph_node **stack;
786 int nnodes, stack_top;
787
788 value_topo_info<tree> constants;
789 value_topo_info<ipa_polymorphic_call_context> contexts;
790
791 ipa_topo_info () : order(NULL), stack(NULL), nnodes(0), stack_top(0),
792 constants ()
793 {}
794};
795
796/* Allocate the arrays in TOPO and topologically sort the nodes into order. */
797
798static void
799build_toporder_info (struct ipa_topo_info *topo)
800{
801 topo->order = XCNEWVEC (struct cgraph_node *, symtab->cgraph_count);
802 topo->stack = XCNEWVEC (struct cgraph_node *, symtab->cgraph_count);
803
804 gcc_checking_assert (topo->stack_top == 0);
805 topo->nnodes = ipa_reduced_postorder (topo->order, true, true, NULL);
806}
807
808/* Free information about strongly connected components and the arrays in
809 TOPO. */
810
811static void
812free_toporder_info (struct ipa_topo_info *topo)
813{
814 ipa_free_postorder_info ();
815 free (topo->order);
816 free (topo->stack);
817}
818
819/* Add NODE to the stack in TOPO, unless it is already there. */
820
821static inline void
822push_node_to_stack (struct ipa_topo_info *topo, struct cgraph_node *node)
823{
824 struct ipa_node_params *info = IPA_NODE_REF (node);
825 if (info->node_enqueued)
826 return;
827 info->node_enqueued = 1;
828 topo->stack[topo->stack_top++] = node;
829}
830
831/* Pop a node from the stack in TOPO and return it or return NULL if the stack
832 is empty. */
833
834static struct cgraph_node *
835pop_node_from_stack (struct ipa_topo_info *topo)
836{
837 if (topo->stack_top)
838 {
839 struct cgraph_node *node;
840 topo->stack_top--;
841 node = topo->stack[topo->stack_top];
842 IPA_NODE_REF (node)->node_enqueued = 0;
843 return node;
844 }
845 else
846 return NULL;
847}
848
849/* Set lattice LAT to bottom and return true if it previously was not set as
850 such. */
851
852template <typename valtype>
853inline bool
854ipcp_lattice<valtype>::set_to_bottom ()
855{
856 bool ret = !bottom;
857 bottom = true;
858 return ret;
859}
860
861/* Mark lattice as containing an unknown value and return true if it previously
862 was not marked as such. */
863
864template <typename valtype>
865inline bool
866ipcp_lattice<valtype>::set_contains_variable ()
867{
868 bool ret = !contains_variable;
869 contains_variable = true;
870 return ret;
871}
872
873/* Set all aggegate lattices in PLATS to bottom and return true if they were
874 not previously set as such. */
875
876static inline bool
877set_agg_lats_to_bottom (struct ipcp_param_lattices *plats)
878{
879 bool ret = !plats->aggs_bottom;
880 plats->aggs_bottom = true;
881 return ret;
882}
883
884/* Mark all aggegate lattices in PLATS as containing an unknown value and
885 return true if they were not previously marked as such. */
886
887static inline bool
888set_agg_lats_contain_variable (struct ipcp_param_lattices *plats)
889{
890 bool ret = !plats->aggs_contain_variable;
891 plats->aggs_contain_variable = true;
892 return ret;
893}
894
895bool
896ipcp_vr_lattice::meet_with (const ipcp_vr_lattice &other)
897{
898 return meet_with_1 (&other.m_vr);
899}
900
901/* Meet the current value of the lattice with value ranfge described by VR
902 lattice. */
903
904bool
905ipcp_vr_lattice::meet_with (const value_range *p_vr)
906{
907 return meet_with_1 (p_vr);
908}
909
910/* Meet the current value of the lattice with value ranfge described by
911 OTHER_VR lattice. */
912
913bool
914ipcp_vr_lattice::meet_with_1 (const value_range *other_vr)
915{
916 tree min = m_vr.min, max = m_vr.max;
917 value_range_type type = m_vr.type;
918
919 if (bottom_p ())
920 return false;
921
922 if (other_vr->type == VR_VARYING)
923 return set_to_bottom ();
924
925 vrp_meet (&m_vr, other_vr);
926 if (type != m_vr.type
927 || min != m_vr.min
928 || max != m_vr.max)
929 return true;
930 else
931 return false;
932}
933
934/* Return true if value range information in the lattice is yet unknown. */
935
936bool
937ipcp_vr_lattice::top_p () const
938{
939 return m_vr.type == VR_UNDEFINED;
940}
941
942/* Return true if value range information in the lattice is known to be
943 unusable. */
944
945bool
946ipcp_vr_lattice::bottom_p () const
947{
948 return m_vr.type == VR_VARYING;
949}
950
951/* Set value range information in the lattice to bottom. Return true if it
952 previously was in a different state. */
953
954bool
955ipcp_vr_lattice::set_to_bottom ()
956{
957 if (m_vr.type == VR_VARYING)
958 return false;
959 m_vr.type = VR_VARYING;
960 return true;
961}
962
963/* Set lattice value to bottom, if it already isn't the case. */
964
965bool
966ipcp_bits_lattice::set_to_bottom ()
967{
968 if (bottom_p ())
969 return false;
970 m_lattice_val = IPA_BITS_VARYING;
971 m_value = 0;
972 m_mask = -1;
973 return true;
974}
975
976/* Set to constant if it isn't already. Only meant to be called
977 when switching state from TOP. */
978
979bool
980ipcp_bits_lattice::set_to_constant (widest_int value, widest_int mask)
981{
982 gcc_assert (top_p ());
983 m_lattice_val = IPA_BITS_CONSTANT;
984 m_value = value;
985 m_mask = mask;
986 return true;
987}
988
989/* Convert operand to value, mask form. */
990
991void
992ipcp_bits_lattice::get_value_and_mask (tree operand, widest_int *valuep, widest_int *maskp)
993{
994 wide_int get_nonzero_bits (const_tree);
995
996 if (TREE_CODE (operand) == INTEGER_CST)
997 {
998 *valuep = wi::to_widest (operand);
999 *maskp = 0;
1000 }
1001 else
1002 {
1003 *valuep = 0;
1004 *maskp = -1;
1005 }
1006}
1007
1008/* Meet operation, similar to ccp_lattice_meet, we xor values
1009 if this->value, value have different values at same bit positions, we want
1010 to drop that bit to varying. Return true if mask is changed.
1011 This function assumes that the lattice value is in CONSTANT state */
1012
1013bool
1014ipcp_bits_lattice::meet_with_1 (widest_int value, widest_int mask,
1015 unsigned precision)
1016{
1017 gcc_assert (constant_p ());
1018
1019 widest_int old_mask = m_mask;
1020 m_mask = (m_mask | mask) | (m_value ^ value);
1021
1022 if (wi::sext (m_mask, precision) == -1)
1023 return set_to_bottom ();
1024
1025 return m_mask != old_mask;
1026}
1027
1028/* Meet the bits lattice with operand
1029 described by <value, mask, sgn, precision. */
1030
1031bool
1032ipcp_bits_lattice::meet_with (widest_int value, widest_int mask,
1033 unsigned precision)
1034{
1035 if (bottom_p ())
1036 return false;
1037
1038 if (top_p ())
1039 {
1040 if (wi::sext (mask, precision) == -1)
1041 return set_to_bottom ();
1042 return set_to_constant (value, mask);
1043 }
1044
1045 return meet_with_1 (value, mask, precision);
1046}
1047
1048/* Meet bits lattice with the result of bit_value_binop (other, operand)
1049 if code is binary operation or bit_value_unop (other) if code is unary op.
1050 In the case when code is nop_expr, no adjustment is required. */
1051
1052bool
1053ipcp_bits_lattice::meet_with (ipcp_bits_lattice& other, unsigned precision,
1054 signop sgn, enum tree_code code, tree operand)
1055{
1056 if (other.bottom_p ())
1057 return set_to_bottom ();
1058
1059 if (bottom_p () || other.top_p ())
1060 return false;
1061
1062 widest_int adjusted_value, adjusted_mask;
1063
1064 if (TREE_CODE_CLASS (code) == tcc_binary)
1065 {
1066 tree type = TREE_TYPE (operand);
1067 gcc_assert (INTEGRAL_TYPE_P (type));
1068 widest_int o_value, o_mask;
1069 get_value_and_mask (operand, &o_value, &o_mask);
1070
1071 bit_value_binop (code, sgn, precision, &adjusted_value, &adjusted_mask,
1072 sgn, precision, other.get_value (), other.get_mask (),
1073 TYPE_SIGN (type), TYPE_PRECISION (type), o_value, o_mask);
1074
1075 if (wi::sext (adjusted_mask, precision) == -1)
1076 return set_to_bottom ();
1077 }
1078
1079 else if (TREE_CODE_CLASS (code) == tcc_unary)
1080 {
1081 bit_value_unop (code, sgn, precision, &adjusted_value,
1082 &adjusted_mask, sgn, precision, other.get_value (),
1083 other.get_mask ());
1084
1085 if (wi::sext (adjusted_mask, precision) == -1)
1086 return set_to_bottom ();
1087 }
1088
1089 else
1090 return set_to_bottom ();
1091
1092 if (top_p ())
1093 {
1094 if (wi::sext (adjusted_mask, precision) == -1)
1095 return set_to_bottom ();
1096 return set_to_constant (adjusted_value, adjusted_mask);
1097 }
1098 else
1099 return meet_with_1 (adjusted_value, adjusted_mask, precision);
1100}
1101
1102/* Mark bot aggregate and scalar lattices as containing an unknown variable,
1103 return true is any of them has not been marked as such so far. */
1104
1105static inline bool
1106set_all_contains_variable (struct ipcp_param_lattices *plats)
1107{
1108 bool ret;
1109 ret = plats->itself.set_contains_variable ();
1110 ret |= plats->ctxlat.set_contains_variable ();
1111 ret |= set_agg_lats_contain_variable (plats);
1112 ret |= plats->bits_lattice.set_to_bottom ();
1113 ret |= plats->m_value_range.set_to_bottom ();
1114 return ret;
1115}
1116
1117/* Worker of call_for_symbol_thunks_and_aliases, increment the integer DATA
1118 points to by the number of callers to NODE. */
1119
1120static bool
1121count_callers (cgraph_node *node, void *data)
1122{
1123 int *caller_count = (int *) data;
1124
1125 for (cgraph_edge *cs = node->callers; cs; cs = cs->next_caller)
1126 /* Local thunks can be handled transparently, but if the thunk can not
1127 be optimized out, count it as a real use. */
1128 if (!cs->caller->thunk.thunk_p || !cs->caller->local.local)
1129 ++*caller_count;
1130 return false;
1131}
1132
1133/* Worker of call_for_symbol_thunks_and_aliases, it is supposed to be called on
1134 the one caller of some other node. Set the caller's corresponding flag. */
1135
1136static bool
1137set_single_call_flag (cgraph_node *node, void *)
1138{
1139 cgraph_edge *cs = node->callers;
1140 /* Local thunks can be handled transparently, skip them. */
1141 while (cs && cs->caller->thunk.thunk_p && cs->caller->local.local)
1142 cs = cs->next_caller;
1143 if (cs)
1144 {
1145 IPA_NODE_REF (cs->caller)->node_calling_single_call = true;
1146 return true;
1147 }
1148 return false;
1149}
1150
1151/* Initialize ipcp_lattices. */
1152
1153static void
1154initialize_node_lattices (struct cgraph_node *node)
1155{
1156 struct ipa_node_params *info = IPA_NODE_REF (node);
1157 struct cgraph_edge *ie;
1158 bool disable = false, variable = false;
1159 int i;
1160
1161 gcc_checking_assert (node->has_gimple_body_p ());
1162 if (cgraph_local_p (node))
1163 {
1164 int caller_count = 0;
1165 node->call_for_symbol_thunks_and_aliases (count_callers, &caller_count,
1166 true);
1167 gcc_checking_assert (caller_count > 0);
1168 if (caller_count == 1)
1169 node->call_for_symbol_thunks_and_aliases (set_single_call_flag,
1170 NULL, true);
1171 }
1172 else
1173 {
1174 /* When cloning is allowed, we can assume that externally visible
1175 functions are not called. We will compensate this by cloning
1176 later. */
1177 if (ipcp_versionable_function_p (node)
1178 && ipcp_cloning_candidate_p (node))
1179 variable = true;
1180 else
1181 disable = true;
1182 }
1183
1184 for (i = 0; i < ipa_get_param_count (info); i++)
1185 {
1186 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
1187 plats->m_value_range.init ();
1188 }
1189
1190 if (disable || variable)
1191 {
1192 for (i = 0; i < ipa_get_param_count (info); i++)
1193 {
1194 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
1195 if (disable)
1196 {
1197 plats->itself.set_to_bottom ();
1198 plats->ctxlat.set_to_bottom ();
1199 set_agg_lats_to_bottom (plats);
1200 plats->bits_lattice.set_to_bottom ();
1201 plats->m_value_range.set_to_bottom ();
1202 }
1203 else
1204 set_all_contains_variable (plats);
1205 }
1206 if (dump_file && (dump_flags & TDF_DETAILS)
1207 && !node->alias && !node->thunk.thunk_p)
1208 fprintf (dump_file, "Marking all lattices of %s as %s\n",
1209 node->dump_name (), disable ? "BOTTOM" : "VARIABLE");
1210 }
1211
1212 for (ie = node->indirect_calls; ie; ie = ie->next_callee)
1213 if (ie->indirect_info->polymorphic
1214 && ie->indirect_info->param_index >= 0)
1215 {
1216 gcc_checking_assert (ie->indirect_info->param_index >= 0);
1217 ipa_get_parm_lattices (info,
1218 ie->indirect_info->param_index)->virt_call = 1;
1219 }
1220}
1221
1222/* Return the result of a (possibly arithmetic) pass through jump function
1223 JFUNC on the constant value INPUT. RES_TYPE is the type of the parameter
1224 to which the result is passed. Return NULL_TREE if that cannot be
1225 determined or be considered an interprocedural invariant. */
1226
1227static tree
1228ipa_get_jf_pass_through_result (struct ipa_jump_func *jfunc, tree input,
1229 tree res_type)
1230{
1231 tree res;
1232
1233 if (ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
1234 return input;
1235 if (!is_gimple_ip_invariant (input))
1236 return NULL_TREE;
1237
1238 tree_code opcode = ipa_get_jf_pass_through_operation (jfunc);
1239 if (!res_type)
1240 {
1241 if (TREE_CODE_CLASS (opcode) == tcc_comparison)
1242 res_type = boolean_type_node;
1243 else if (expr_type_first_operand_type_p (opcode))
1244 res_type = TREE_TYPE (input);
1245 else
1246 return NULL_TREE;
1247 }
1248
1249 if (TREE_CODE_CLASS (opcode) == tcc_unary)
1250 res = fold_unary (opcode, res_type, input);
1251 else
1252 res = fold_binary (opcode, res_type, input,
1253 ipa_get_jf_pass_through_operand (jfunc));
1254
1255 if (res && !is_gimple_ip_invariant (res))
1256 return NULL_TREE;
1257
1258 return res;
1259}
1260
1261/* Return the result of an ancestor jump function JFUNC on the constant value
1262 INPUT. Return NULL_TREE if that cannot be determined. */
1263
1264static tree
1265ipa_get_jf_ancestor_result (struct ipa_jump_func *jfunc, tree input)
1266{
1267 gcc_checking_assert (TREE_CODE (input) != TREE_BINFO);
1268 if (TREE_CODE (input) == ADDR_EXPR)
1269 {
1270 tree t = TREE_OPERAND (input, 0);
1271 t = build_ref_for_offset (EXPR_LOCATION (t), t,
1272 ipa_get_jf_ancestor_offset (jfunc), false,
1273 ptr_type_node, NULL, false);
1274 return build_fold_addr_expr (t);
1275 }
1276 else
1277 return NULL_TREE;
1278}
1279
1280/* Determine whether JFUNC evaluates to a single known constant value and if
1281 so, return it. Otherwise return NULL. INFO describes the caller node or
1282 the one it is inlined to, so that pass-through jump functions can be
1283 evaluated. PARM_TYPE is the type of the parameter to which the result is
1284 passed. */
1285
1286tree
1287ipa_value_from_jfunc (struct ipa_node_params *info, struct ipa_jump_func *jfunc,
1288 tree parm_type)
1289{
1290 if (jfunc->type == IPA_JF_CONST)
1291 return ipa_get_jf_constant (jfunc);
1292 else if (jfunc->type == IPA_JF_PASS_THROUGH
1293 || jfunc->type == IPA_JF_ANCESTOR)
1294 {
1295 tree input;
1296 int idx;
1297
1298 if (jfunc->type == IPA_JF_PASS_THROUGH)
1299 idx = ipa_get_jf_pass_through_formal_id (jfunc);
1300 else
1301 idx = ipa_get_jf_ancestor_formal_id (jfunc);
1302
1303 if (info->ipcp_orig_node)
1304 input = info->known_csts[idx];
1305 else
1306 {
1307 ipcp_lattice<tree> *lat;
1308
1309 if (!info->lattices
1310 || idx >= ipa_get_param_count (info))
1311 return NULL_TREE;
1312 lat = ipa_get_scalar_lat (info, idx);
1313 if (!lat->is_single_const ())
1314 return NULL_TREE;
1315 input = lat->values->value;
1316 }
1317
1318 if (!input)
1319 return NULL_TREE;
1320
1321 if (jfunc->type == IPA_JF_PASS_THROUGH)
1322 return ipa_get_jf_pass_through_result (jfunc, input, parm_type);
1323 else
1324 return ipa_get_jf_ancestor_result (jfunc, input);
1325 }
1326 else
1327 return NULL_TREE;
1328}
1329
1330/* Determie whether JFUNC evaluates to single known polymorphic context, given
1331 that INFO describes the caller node or the one it is inlined to, CS is the
1332 call graph edge corresponding to JFUNC and CSIDX index of the described
1333 parameter. */
1334
1335ipa_polymorphic_call_context
1336ipa_context_from_jfunc (ipa_node_params *info, cgraph_edge *cs, int csidx,
1337 ipa_jump_func *jfunc)
1338{
1339 ipa_edge_args *args = IPA_EDGE_REF (cs);
1340 ipa_polymorphic_call_context ctx;
1341 ipa_polymorphic_call_context *edge_ctx
1342 = cs ? ipa_get_ith_polymorhic_call_context (args, csidx) : NULL;
1343
1344 if (edge_ctx && !edge_ctx->useless_p ())
1345 ctx = *edge_ctx;
1346
1347 if (jfunc->type == IPA_JF_PASS_THROUGH
1348 || jfunc->type == IPA_JF_ANCESTOR)
1349 {
1350 ipa_polymorphic_call_context srcctx;
1351 int srcidx;
1352 bool type_preserved = true;
1353 if (jfunc->type == IPA_JF_PASS_THROUGH)
1354 {
1355 if (ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR)
1356 return ctx;
1357 type_preserved = ipa_get_jf_pass_through_type_preserved (jfunc);
1358 srcidx = ipa_get_jf_pass_through_formal_id (jfunc);
1359 }
1360 else
1361 {
1362 type_preserved = ipa_get_jf_ancestor_type_preserved (jfunc);
1363 srcidx = ipa_get_jf_ancestor_formal_id (jfunc);
1364 }
1365 if (info->ipcp_orig_node)
1366 {
1367 if (info->known_contexts.exists ())
1368 srcctx = info->known_contexts[srcidx];
1369 }
1370 else
1371 {
1372 if (!info->lattices
1373 || srcidx >= ipa_get_param_count (info))
1374 return ctx;
1375 ipcp_lattice<ipa_polymorphic_call_context> *lat;
1376 lat = ipa_get_poly_ctx_lat (info, srcidx);
1377 if (!lat->is_single_const ())
1378 return ctx;
1379 srcctx = lat->values->value;
1380 }
1381 if (srcctx.useless_p ())
1382 return ctx;
1383 if (jfunc->type == IPA_JF_ANCESTOR)
1384 srcctx.offset_by (ipa_get_jf_ancestor_offset (jfunc));
1385 if (!type_preserved)
1386 srcctx.possible_dynamic_type_change (cs->in_polymorphic_cdtor);
1387 srcctx.combine_with (ctx);
1388 return srcctx;
1389 }
1390
1391 return ctx;
1392}
1393
1394/* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
1395 bottom, not containing a variable component and without any known value at
1396 the same time. */
1397
1398DEBUG_FUNCTION void
1399ipcp_verify_propagated_values (void)
1400{
1401 struct cgraph_node *node;
1402
1403 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
1404 {
1405 struct ipa_node_params *info = IPA_NODE_REF (node);
1406 int i, count = ipa_get_param_count (info);
1407
1408 for (i = 0; i < count; i++)
1409 {
1410 ipcp_lattice<tree> *lat = ipa_get_scalar_lat (info, i);
1411
1412 if (!lat->bottom
1413 && !lat->contains_variable
1414 && lat->values_count == 0)
1415 {
1416 if (dump_file)
1417 {
1418 symtab->dump (dump_file);
1419 fprintf (dump_file, "\nIPA lattices after constant "
1420 "propagation, before gcc_unreachable:\n");
1421 print_all_lattices (dump_file, true, false);
1422 }
1423
1424 gcc_unreachable ();
1425 }
1426 }
1427 }
1428}
1429
1430/* Return true iff X and Y should be considered equal values by IPA-CP. */
1431
1432static bool
1433values_equal_for_ipcp_p (tree x, tree y)
1434{
1435 gcc_checking_assert (x != NULL_TREE && y != NULL_TREE);
1436
1437 if (x == y)
1438 return true;
1439
1440 if (TREE_CODE (x) == ADDR_EXPR
1441 && TREE_CODE (y) == ADDR_EXPR
1442 && TREE_CODE (TREE_OPERAND (x, 0)) == CONST_DECL
1443 && TREE_CODE (TREE_OPERAND (y, 0)) == CONST_DECL)
1444 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x, 0)),
1445 DECL_INITIAL (TREE_OPERAND (y, 0)), 0);
1446 else
1447 return operand_equal_p (x, y, 0);
1448}
1449
1450/* Return true iff X and Y should be considered equal contexts by IPA-CP. */
1451
1452static bool
1453values_equal_for_ipcp_p (ipa_polymorphic_call_context x,
1454 ipa_polymorphic_call_context y)
1455{
1456 return x.equal_to (y);
1457}
1458
1459
1460/* Add a new value source to the value represented by THIS, marking that a
1461 value comes from edge CS and (if the underlying jump function is a
1462 pass-through or an ancestor one) from a caller value SRC_VAL of a caller
1463 parameter described by SRC_INDEX. OFFSET is negative if the source was the
1464 scalar value of the parameter itself or the offset within an aggregate. */
1465
1466template <typename valtype>
1467void
1468ipcp_value<valtype>::add_source (cgraph_edge *cs, ipcp_value *src_val,
1469 int src_idx, HOST_WIDE_INT offset)
1470{
1471 ipcp_value_source<valtype> *src;
1472
1473 src = new (ipcp_sources_pool.allocate ()) ipcp_value_source<valtype>;
1474 src->offset = offset;
1475 src->cs = cs;
1476 src->val = src_val;
1477 src->index = src_idx;
1478
1479 src->next = sources;
1480 sources = src;
1481}
1482
1483/* Allocate a new ipcp_value holding a tree constant, initialize its value to
1484 SOURCE and clear all other fields. */
1485
1486static ipcp_value<tree> *
1487allocate_and_init_ipcp_value (tree source)
1488{
1489 ipcp_value<tree> *val;
1490
1491 val = new (ipcp_cst_values_pool.allocate ()) ipcp_value<tree>();
1492 val->value = source;
1493 return val;
1494}
1495
1496/* Allocate a new ipcp_value holding a polymorphic context, initialize its
1497 value to SOURCE and clear all other fields. */
1498
1499static ipcp_value<ipa_polymorphic_call_context> *
1500allocate_and_init_ipcp_value (ipa_polymorphic_call_context source)
1501{
1502 ipcp_value<ipa_polymorphic_call_context> *val;
1503
1504 // TODO
1505 val = new (ipcp_poly_ctx_values_pool.allocate ())
1506 ipcp_value<ipa_polymorphic_call_context>();
1507 val->value = source;
1508 return val;
1509}
1510
1511/* Try to add NEWVAL to LAT, potentially creating a new ipcp_value for it. CS,
1512 SRC_VAL SRC_INDEX and OFFSET are meant for add_source and have the same
1513 meaning. OFFSET -1 means the source is scalar and not a part of an
1514 aggregate. */
1515
1516template <typename valtype>
1517bool
1518ipcp_lattice<valtype>::add_value (valtype newval, cgraph_edge *cs,
1519 ipcp_value<valtype> *src_val,
1520 int src_idx, HOST_WIDE_INT offset)
1521{
1522 ipcp_value<valtype> *val;
1523
1524 if (bottom)
1525 return false;
1526
1527 for (val = values; val; val = val->next)
1528 if (values_equal_for_ipcp_p (val->value, newval))
1529 {
1530 if (ipa_edge_within_scc (cs))
1531 {
1532 ipcp_value_source<valtype> *s;
1533 for (s = val->sources; s; s = s->next)
1534 if (s->cs == cs)
1535 break;
1536 if (s)
1537 return false;
1538 }
1539
1540 val->add_source (cs, src_val, src_idx, offset);
1541 return false;
1542 }
1543
1544 if (values_count == PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE))
1545 {
1546 /* We can only free sources, not the values themselves, because sources
1547 of other values in this SCC might point to them. */
1548 for (val = values; val; val = val->next)
1549 {
1550 while (val->sources)
1551 {
1552 ipcp_value_source<valtype> *src = val->sources;
1553 val->sources = src->next;
1554 ipcp_sources_pool.remove ((ipcp_value_source<tree>*)src);
1555 }
1556 }
1557
1558 values = NULL;
1559 return set_to_bottom ();
1560 }
1561
1562 values_count++;
1563 val = allocate_and_init_ipcp_value (newval);
1564 val->add_source (cs, src_val, src_idx, offset);
1565 val->next = values;
1566 values = val;
1567 return true;
1568}
1569
1570/* Propagate values through a pass-through jump function JFUNC associated with
1571 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1572 is the index of the source parameter. PARM_TYPE is the type of the
1573 parameter to which the result is passed. */
1574
1575static bool
1576propagate_vals_across_pass_through (cgraph_edge *cs, ipa_jump_func *jfunc,
1577 ipcp_lattice<tree> *src_lat,
1578 ipcp_lattice<tree> *dest_lat, int src_idx,
1579 tree parm_type)
1580{
1581 ipcp_value<tree> *src_val;
1582 bool ret = false;
1583
1584 /* Do not create new values when propagating within an SCC because if there
1585 are arithmetic functions with circular dependencies, there is infinite
1586 number of them and we would just make lattices bottom. */
1587 if ((ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR)
1588 && ipa_edge_within_scc (cs))
1589 ret = dest_lat->set_contains_variable ();
1590 else
1591 for (src_val = src_lat->values; src_val; src_val = src_val->next)
1592 {
1593 tree cstval = ipa_get_jf_pass_through_result (jfunc, src_val->value,
1594 parm_type);
1595
1596 if (cstval)
1597 ret |= dest_lat->add_value (cstval, cs, src_val, src_idx);
1598 else
1599 ret |= dest_lat->set_contains_variable ();
1600 }
1601
1602 return ret;
1603}
1604
1605/* Propagate values through an ancestor jump function JFUNC associated with
1606 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX
1607 is the index of the source parameter. */
1608
1609static bool
1610propagate_vals_across_ancestor (struct cgraph_edge *cs,
1611 struct ipa_jump_func *jfunc,
1612 ipcp_lattice<tree> *src_lat,
1613 ipcp_lattice<tree> *dest_lat, int src_idx)
1614{
1615 ipcp_value<tree> *src_val;
1616 bool ret = false;
1617
1618 if (ipa_edge_within_scc (cs))
1619 return dest_lat->set_contains_variable ();
1620
1621 for (src_val = src_lat->values; src_val; src_val = src_val->next)
1622 {
1623 tree t = ipa_get_jf_ancestor_result (jfunc, src_val->value);
1624
1625 if (t)
1626 ret |= dest_lat->add_value (t, cs, src_val, src_idx);
1627 else
1628 ret |= dest_lat->set_contains_variable ();
1629 }
1630
1631 return ret;
1632}
1633
1634/* Propagate scalar values across jump function JFUNC that is associated with
1635 edge CS and put the values into DEST_LAT. PARM_TYPE is the type of the
1636 parameter to which the result is passed. */
1637
1638static bool
1639propagate_scalar_across_jump_function (struct cgraph_edge *cs,
1640 struct ipa_jump_func *jfunc,
1641 ipcp_lattice<tree> *dest_lat,
1642 tree param_type)
1643{
1644 if (dest_lat->bottom)
1645 return false;
1646
1647 if (jfunc->type == IPA_JF_CONST)
1648 {
1649 tree val = ipa_get_jf_constant (jfunc);
1650 return dest_lat->add_value (val, cs, NULL, 0);
1651 }
1652 else if (jfunc->type == IPA_JF_PASS_THROUGH
1653 || jfunc->type == IPA_JF_ANCESTOR)
1654 {
1655 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1656 ipcp_lattice<tree> *src_lat;
1657 int src_idx;
1658 bool ret;
1659
1660 if (jfunc->type == IPA_JF_PASS_THROUGH)
1661 src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
1662 else
1663 src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
1664
1665 src_lat = ipa_get_scalar_lat (caller_info, src_idx);
1666 if (src_lat->bottom)
1667 return dest_lat->set_contains_variable ();
1668
1669 /* If we would need to clone the caller and cannot, do not propagate. */
1670 if (!ipcp_versionable_function_p (cs->caller)
1671 && (src_lat->contains_variable
1672 || (src_lat->values_count > 1)))
1673 return dest_lat->set_contains_variable ();
1674
1675 if (jfunc->type == IPA_JF_PASS_THROUGH)
1676 ret = propagate_vals_across_pass_through (cs, jfunc, src_lat,
1677 dest_lat, src_idx, param_type);
1678 else
1679 ret = propagate_vals_across_ancestor (cs, jfunc, src_lat, dest_lat,
1680 src_idx);
1681
1682 if (src_lat->contains_variable)
1683 ret |= dest_lat->set_contains_variable ();
1684
1685 return ret;
1686 }
1687
1688 /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1689 use it for indirect inlining), we should propagate them too. */
1690 return dest_lat->set_contains_variable ();
1691}
1692
1693/* Propagate scalar values across jump function JFUNC that is associated with
1694 edge CS and describes argument IDX and put the values into DEST_LAT. */
1695
1696static bool
1697propagate_context_across_jump_function (cgraph_edge *cs,
1698 ipa_jump_func *jfunc, int idx,
1699 ipcp_lattice<ipa_polymorphic_call_context> *dest_lat)
1700{
1701 ipa_edge_args *args = IPA_EDGE_REF (cs);
1702 if (dest_lat->bottom)
1703 return false;
1704 bool ret = false;
1705 bool added_sth = false;
1706 bool type_preserved = true;
1707
1708 ipa_polymorphic_call_context edge_ctx, *edge_ctx_ptr
1709 = ipa_get_ith_polymorhic_call_context (args, idx);
1710
1711 if (edge_ctx_ptr)
1712 edge_ctx = *edge_ctx_ptr;
1713
1714 if (jfunc->type == IPA_JF_PASS_THROUGH
1715 || jfunc->type == IPA_JF_ANCESTOR)
1716 {
1717 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1718 int src_idx;
1719 ipcp_lattice<ipa_polymorphic_call_context> *src_lat;
1720
1721 /* TODO: Once we figure out how to propagate speculations, it will
1722 probably be a good idea to switch to speculation if type_preserved is
1723 not set instead of punting. */
1724 if (jfunc->type == IPA_JF_PASS_THROUGH)
1725 {
1726 if (ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR)
1727 goto prop_fail;
1728 type_preserved = ipa_get_jf_pass_through_type_preserved (jfunc);
1729 src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
1730 }
1731 else
1732 {
1733 type_preserved = ipa_get_jf_ancestor_type_preserved (jfunc);
1734 src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
1735 }
1736
1737 src_lat = ipa_get_poly_ctx_lat (caller_info, src_idx);
1738 /* If we would need to clone the caller and cannot, do not propagate. */
1739 if (!ipcp_versionable_function_p (cs->caller)
1740 && (src_lat->contains_variable
1741 || (src_lat->values_count > 1)))
1742 goto prop_fail;
1743
1744 ipcp_value<ipa_polymorphic_call_context> *src_val;
1745 for (src_val = src_lat->values; src_val; src_val = src_val->next)
1746 {
1747 ipa_polymorphic_call_context cur = src_val->value;
1748
1749 if (!type_preserved)
1750 cur.possible_dynamic_type_change (cs->in_polymorphic_cdtor);
1751 if (jfunc->type == IPA_JF_ANCESTOR)
1752 cur.offset_by (ipa_get_jf_ancestor_offset (jfunc));
1753 /* TODO: In cases we know how the context is going to be used,
1754 we can improve the result by passing proper OTR_TYPE. */
1755 cur.combine_with (edge_ctx);
1756 if (!cur.useless_p ())
1757 {
1758 if (src_lat->contains_variable
1759 && !edge_ctx.equal_to (cur))
1760 ret |= dest_lat->set_contains_variable ();
1761 ret |= dest_lat->add_value (cur, cs, src_val, src_idx);
1762 added_sth = true;
1763 }
1764 }
1765
1766 }
1767
1768 prop_fail:
1769 if (!added_sth)
1770 {
1771 if (!edge_ctx.useless_p ())
1772 ret |= dest_lat->add_value (edge_ctx, cs);
1773 else
1774 ret |= dest_lat->set_contains_variable ();
1775 }
1776
1777 return ret;
1778}
1779
1780/* Propagate bits across jfunc that is associated with
1781 edge cs and update dest_lattice accordingly. */
1782
1783bool
1784propagate_bits_across_jump_function (cgraph_edge *cs, int idx,
1785 ipa_jump_func *jfunc,
1786 ipcp_bits_lattice *dest_lattice)
1787{
1788 if (dest_lattice->bottom_p ())
1789 return false;
1790
1791 enum availability availability;
1792 cgraph_node *callee = cs->callee->function_symbol (&availability);
1793 struct ipa_node_params *callee_info = IPA_NODE_REF (callee);
1794 tree parm_type = ipa_get_type (callee_info, idx);
1795
1796 /* For K&R C programs, ipa_get_type() could return NULL_TREE.
1797 Avoid the transform for these cases. */
1798 if (!parm_type)
1799 {
1800 if (dump_file && (dump_flags & TDF_DETAILS))
1801 fprintf (dump_file, "Setting dest_lattice to bottom, because"
1802 " param %i type is NULL for %s\n", idx,
1803 cs->callee->name ());
1804
1805 return dest_lattice->set_to_bottom ();
1806 }
1807
1808 unsigned precision = TYPE_PRECISION (parm_type);
1809 signop sgn = TYPE_SIGN (parm_type);
1810
1811 if (jfunc->type == IPA_JF_PASS_THROUGH
1812 || jfunc->type == IPA_JF_ANCESTOR)
1813 {
1814 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1815 tree operand = NULL_TREE;
1816 enum tree_code code;
1817 unsigned src_idx;
1818
1819 if (jfunc->type == IPA_JF_PASS_THROUGH)
1820 {
1821 code = ipa_get_jf_pass_through_operation (jfunc);
1822 src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
1823 if (code != NOP_EXPR)
1824 operand = ipa_get_jf_pass_through_operand (jfunc);
1825 }
1826 else
1827 {
1828 code = POINTER_PLUS_EXPR;
1829 src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
1830 unsigned HOST_WIDE_INT offset = ipa_get_jf_ancestor_offset (jfunc) / BITS_PER_UNIT;
1831 operand = build_int_cstu (size_type_node, offset);
1832 }
1833
1834 struct ipcp_param_lattices *src_lats
1835 = ipa_get_parm_lattices (caller_info, src_idx);
1836
1837 /* Try to propagate bits if src_lattice is bottom, but jfunc is known.
1838 for eg consider:
1839 int f(int x)
1840 {
1841 g (x & 0xff);
1842 }
1843 Assume lattice for x is bottom, however we can still propagate
1844 result of x & 0xff == 0xff, which gets computed during ccp1 pass
1845 and we store it in jump function during analysis stage. */
1846
1847 if (src_lats->bits_lattice.bottom_p ()
1848 && jfunc->bits)
1849 return dest_lattice->meet_with (jfunc->bits->value, jfunc->bits->mask,
1850 precision);
1851 else
1852 return dest_lattice->meet_with (src_lats->bits_lattice, precision, sgn,
1853 code, operand);
1854 }
1855
1856 else if (jfunc->type == IPA_JF_ANCESTOR)
1857 return dest_lattice->set_to_bottom ();
1858 else if (jfunc->bits)
1859 return dest_lattice->meet_with (jfunc->bits->value, jfunc->bits->mask,
1860 precision);
1861 else
1862 return dest_lattice->set_to_bottom ();
1863}
1864
1865/* Emulate effects of unary OPERATION and/or conversion from SRC_TYPE to
1866 DST_TYPE on value range in SRC_VR and store it to DST_VR. Return true if
1867 the result is a range or an anti-range. */
1868
1869static bool
1870ipa_vr_operation_and_type_effects (value_range *dst_vr, value_range *src_vr,
1871 enum tree_code operation,
1872 tree dst_type, tree src_type)
1873{
1874 memset (dst_vr, 0, sizeof (*dst_vr));
1875 extract_range_from_unary_expr (dst_vr, operation, dst_type, src_vr, src_type);
1876 if (dst_vr->type == VR_RANGE || dst_vr->type == VR_ANTI_RANGE)
1877 return true;
1878 else
1879 return false;
1880}
1881
1882/* Propagate value range across jump function JFUNC that is associated with
1883 edge CS with param of callee of PARAM_TYPE and update DEST_PLATS
1884 accordingly. */
1885
1886static bool
1887propagate_vr_across_jump_function (cgraph_edge *cs, ipa_jump_func *jfunc,
1888 struct ipcp_param_lattices *dest_plats,
1889 tree param_type)
1890{
1891 ipcp_vr_lattice *dest_lat = &dest_plats->m_value_range;
1892
1893 if (dest_lat->bottom_p ())
1894 return false;
1895
1896 if (!param_type
1897 || (!INTEGRAL_TYPE_P (param_type)
1898 && !POINTER_TYPE_P (param_type)))
1899 return dest_lat->set_to_bottom ();
1900
1901 if (jfunc->type == IPA_JF_PASS_THROUGH)
1902 {
1903 enum tree_code operation = ipa_get_jf_pass_through_operation (jfunc);
1904
1905 if (TREE_CODE_CLASS (operation) == tcc_unary)
1906 {
1907 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1908 int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
1909 tree operand_type = ipa_get_type (caller_info, src_idx);
1910 struct ipcp_param_lattices *src_lats
1911 = ipa_get_parm_lattices (caller_info, src_idx);
1912
1913 if (src_lats->m_value_range.bottom_p ())
1914 return dest_lat->set_to_bottom ();
1915 value_range vr;
1916 if (ipa_vr_operation_and_type_effects (&vr,
1917 &src_lats->m_value_range.m_vr,
1918 operation, param_type,
1919 operand_type))
1920 return dest_lat->meet_with (&vr);
1921 }
1922 }
1923 else if (jfunc->type == IPA_JF_CONST)
1924 {
1925 tree val = ipa_get_jf_constant (jfunc);
1926 if (TREE_CODE (val) == INTEGER_CST)
1927 {
1928 val = fold_convert (param_type, val);
1929 if (TREE_OVERFLOW_P (val))
1930 val = drop_tree_overflow (val);
1931
1932 value_range tmpvr;
1933 memset (&tmpvr, 0, sizeof (tmpvr));
1934 tmpvr.type = VR_RANGE;
1935 tmpvr.min = val;
1936 tmpvr.max = val;
1937 return dest_lat->meet_with (&tmpvr);
1938 }
1939 }
1940
1941 value_range vr;
1942 if (jfunc->m_vr
1943 && ipa_vr_operation_and_type_effects (&vr, jfunc->m_vr, NOP_EXPR,
1944 param_type,
1945 TREE_TYPE (jfunc->m_vr->min)))
1946 return dest_lat->meet_with (&vr);
1947 else
1948 return dest_lat->set_to_bottom ();
1949}
1950
1951/* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
1952 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
1953 other cases, return false). If there are no aggregate items, set
1954 aggs_by_ref to NEW_AGGS_BY_REF. */
1955
1956static bool
1957set_check_aggs_by_ref (struct ipcp_param_lattices *dest_plats,
1958 bool new_aggs_by_ref)
1959{
1960 if (dest_plats->aggs)
1961 {
1962 if (dest_plats->aggs_by_ref != new_aggs_by_ref)
1963 {
1964 set_agg_lats_to_bottom (dest_plats);
1965 return true;
1966 }
1967 }
1968 else
1969 dest_plats->aggs_by_ref = new_aggs_by_ref;
1970 return false;
1971}
1972
1973/* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an
1974 already existing lattice for the given OFFSET and SIZE, marking all skipped
1975 lattices as containing variable and checking for overlaps. If there is no
1976 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize
1977 it with offset, size and contains_variable to PRE_EXISTING, and return true,
1978 unless there are too many already. If there are two many, return false. If
1979 there are overlaps turn whole DEST_PLATS to bottom and return false. If any
1980 skipped lattices were newly marked as containing variable, set *CHANGE to
1981 true. */
1982
1983static bool
1984merge_agg_lats_step (struct ipcp_param_lattices *dest_plats,
1985 HOST_WIDE_INT offset, HOST_WIDE_INT val_size,
1986 struct ipcp_agg_lattice ***aglat,
1987 bool pre_existing, bool *change)
1988{
1989 gcc_checking_assert (offset >= 0);
1990
1991 while (**aglat && (**aglat)->offset < offset)
1992 {
1993 if ((**aglat)->offset + (**aglat)->size > offset)
1994 {
1995 set_agg_lats_to_bottom (dest_plats);
1996 return false;
1997 }
1998 *change |= (**aglat)->set_contains_variable ();
1999 *aglat = &(**aglat)->next;
2000 }
2001
2002 if (**aglat && (**aglat)->offset == offset)
2003 {
2004 if ((**aglat)->size != val_size
2005 || ((**aglat)->next
2006 && (**aglat)->next->offset < offset + val_size))
2007 {
2008 set_agg_lats_to_bottom (dest_plats);
2009 return false;
2010 }
2011 gcc_checking_assert (!(**aglat)->next
2012 || (**aglat)->next->offset >= offset + val_size);
2013 return true;
2014 }
2015 else
2016 {
2017 struct ipcp_agg_lattice *new_al;
2018
2019 if (**aglat && (**aglat)->offset < offset + val_size)
2020 {
2021 set_agg_lats_to_bottom (dest_plats);
2022 return false;
2023 }
2024 if (dest_plats->aggs_count == PARAM_VALUE (PARAM_IPA_MAX_AGG_ITEMS))
2025 return false;
2026 dest_plats->aggs_count++;
2027 new_al = ipcp_agg_lattice_pool.allocate ();
2028 memset (new_al, 0, sizeof (*new_al));
2029
2030 new_al->offset = offset;
2031 new_al->size = val_size;
2032 new_al->contains_variable = pre_existing;
2033
2034 new_al->next = **aglat;
2035 **aglat = new_al;
2036 return true;
2037 }
2038}
2039
2040/* Set all AGLAT and all other aggregate lattices reachable by next pointers as
2041 containing an unknown value. */
2042
2043static bool
2044set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice *aglat)
2045{
2046 bool ret = false;
2047 while (aglat)
2048 {
2049 ret |= aglat->set_contains_variable ();
2050 aglat = aglat->next;
2051 }
2052 return ret;
2053}
2054
2055/* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting
2056 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source
2057 parameter used for lattice value sources. Return true if DEST_PLATS changed
2058 in any way. */
2059
2060static bool
2061merge_aggregate_lattices (struct cgraph_edge *cs,
2062 struct ipcp_param_lattices *dest_plats,
2063 struct ipcp_param_lattices *src_plats,
2064 int src_idx, HOST_WIDE_INT offset_delta)
2065{
2066 bool pre_existing = dest_plats->aggs != NULL;
2067 struct ipcp_agg_lattice **dst_aglat;
2068 bool ret = false;
2069
2070 if (set_check_aggs_by_ref (dest_plats, src_plats->aggs_by_ref))
2071 return true;
2072 if (src_plats->aggs_bottom)
2073 return set_agg_lats_contain_variable (dest_plats);
2074 if (src_plats->aggs_contain_variable)
2075 ret |= set_agg_lats_contain_variable (dest_plats);
2076 dst_aglat = &dest_plats->aggs;
2077
2078 for (struct ipcp_agg_lattice *src_aglat = src_plats->aggs;
2079 src_aglat;
2080 src_aglat = src_aglat->next)
2081 {
2082 HOST_WIDE_INT new_offset = src_aglat->offset - offset_delta;
2083
2084 if (new_offset < 0)
2085 continue;
2086 if (merge_agg_lats_step (dest_plats, new_offset, src_aglat->size,
2087 &dst_aglat, pre_existing, &ret))
2088 {
2089 struct ipcp_agg_lattice *new_al = *dst_aglat;
2090
2091 dst_aglat = &(*dst_aglat)->next;
2092 if (src_aglat->bottom)
2093 {
2094 ret |= new_al->set_contains_variable ();
2095 continue;
2096 }
2097 if (src_aglat->contains_variable)
2098 ret |= new_al->set_contains_variable ();
2099 for (ipcp_value<tree> *val = src_aglat->values;
2100 val;
2101 val = val->next)
2102 ret |= new_al->add_value (val->value, cs, val, src_idx,
2103 src_aglat->offset);
2104 }
2105 else if (dest_plats->aggs_bottom)
2106 return true;
2107 }
2108 ret |= set_chain_of_aglats_contains_variable (*dst_aglat);
2109 return ret;
2110}
2111
2112/* Determine whether there is anything to propagate FROM SRC_PLATS through a
2113 pass-through JFUNC and if so, whether it has conform and conforms to the
2114 rules about propagating values passed by reference. */
2115
2116static bool
2117agg_pass_through_permissible_p (struct ipcp_param_lattices *src_plats,
2118 struct ipa_jump_func *jfunc)
2119{
2120 return src_plats->aggs
2121 && (!src_plats->aggs_by_ref
2122 || ipa_get_jf_pass_through_agg_preserved (jfunc));
2123}
2124
2125/* Propagate scalar values across jump function JFUNC that is associated with
2126 edge CS and put the values into DEST_LAT. */
2127
2128static bool
2129propagate_aggs_across_jump_function (struct cgraph_edge *cs,
2130 struct ipa_jump_func *jfunc,
2131 struct ipcp_param_lattices *dest_plats)
2132{
2133 bool ret = false;
2134
2135 if (dest_plats->aggs_bottom)
2136 return false;
2137
2138 if (jfunc->type == IPA_JF_PASS_THROUGH
2139 && ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
2140 {
2141 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
2142 int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
2143 struct ipcp_param_lattices *src_plats;
2144
2145 src_plats = ipa_get_parm_lattices (caller_info, src_idx);
2146 if (agg_pass_through_permissible_p (src_plats, jfunc))
2147 {
2148 /* Currently we do not produce clobber aggregate jump
2149 functions, replace with merging when we do. */
2150 gcc_assert (!jfunc->agg.items);
2151 ret |= merge_aggregate_lattices (cs, dest_plats, src_plats,
2152 src_idx, 0);
2153 }
2154 else
2155 ret |= set_agg_lats_contain_variable (dest_plats);
2156 }
2157 else if (jfunc->type == IPA_JF_ANCESTOR
2158 && ipa_get_jf_ancestor_agg_preserved (jfunc))
2159 {
2160 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
2161 int src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
2162 struct ipcp_param_lattices *src_plats;
2163
2164 src_plats = ipa_get_parm_lattices (caller_info, src_idx);
2165 if (src_plats->aggs && src_plats->aggs_by_ref)
2166 {
2167 /* Currently we do not produce clobber aggregate jump
2168 functions, replace with merging when we do. */
2169 gcc_assert (!jfunc->agg.items);
2170 ret |= merge_aggregate_lattices (cs, dest_plats, src_plats, src_idx,
2171 ipa_get_jf_ancestor_offset (jfunc));
2172 }
2173 else if (!src_plats->aggs_by_ref)
2174 ret |= set_agg_lats_to_bottom (dest_plats);
2175 else
2176 ret |= set_agg_lats_contain_variable (dest_plats);
2177 }
2178 else if (jfunc->agg.items)
2179 {
2180 bool pre_existing = dest_plats->aggs != NULL;
2181 struct ipcp_agg_lattice **aglat = &dest_plats->aggs;
2182 struct ipa_agg_jf_item *item;
2183 int i;
2184
2185 if (set_check_aggs_by_ref (dest_plats, jfunc->agg.by_ref))
2186 return true;
2187
2188 FOR_EACH_VEC_ELT (*jfunc->agg.items, i, item)
2189 {
2190 HOST_WIDE_INT val_size;
2191
2192 if (item->offset < 0)
2193 continue;
2194 gcc_checking_assert (is_gimple_ip_invariant (item->value));
2195 val_size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (item->value)));
2196
2197 if (merge_agg_lats_step (dest_plats, item->offset, val_size,
2198 &aglat, pre_existing, &ret))
2199 {
2200 ret |= (*aglat)->add_value (item->value, cs, NULL, 0, 0);
2201 aglat = &(*aglat)->next;
2202 }
2203 else if (dest_plats->aggs_bottom)
2204 return true;
2205 }
2206
2207 ret |= set_chain_of_aglats_contains_variable (*aglat);
2208 }
2209 else
2210 ret |= set_agg_lats_contain_variable (dest_plats);
2211
2212 return ret;
2213}
2214
2215/* Return true if on the way cfrom CS->caller to the final (non-alias and
2216 non-thunk) destination, the call passes through a thunk. */
2217
2218static bool
2219call_passes_through_thunk_p (cgraph_edge *cs)
2220{
2221 cgraph_node *alias_or_thunk = cs->callee;
2222 while (alias_or_thunk->alias)
2223 alias_or_thunk = alias_or_thunk->get_alias_target ();
2224 return alias_or_thunk->thunk.thunk_p;
2225}
2226
2227/* Propagate constants from the caller to the callee of CS. INFO describes the
2228 caller. */
2229
2230static bool
2231propagate_constants_across_call (struct cgraph_edge *cs)
2232{
2233 struct ipa_node_params *callee_info;
2234 enum availability availability;
2235 cgraph_node *callee;
2236 struct ipa_edge_args *args;
2237 bool ret = false;
2238 int i, args_count, parms_count;
2239
2240 callee = cs->callee->function_symbol (&availability);
2241 if (!callee->definition)
2242 return false;
2243 gcc_checking_assert (callee->has_gimple_body_p ());
2244 callee_info = IPA_NODE_REF (callee);
2245
2246 args = IPA_EDGE_REF (cs);
2247 args_count = ipa_get_cs_argument_count (args);
2248 parms_count = ipa_get_param_count (callee_info);
2249 if (parms_count == 0)
2250 return false;
2251
2252 /* No propagation through instrumentation thunks is available yet.
2253 It should be possible with proper mapping of call args and
2254 instrumented callee params in the propagation loop below. But
2255 this case mostly occurs when legacy code calls instrumented code
2256 and it is not a primary target for optimizations.
2257 We detect instrumentation thunks in aliases and thunks chain by
2258 checking instrumentation_clone flag for chain source and target.
2259 Going through instrumentation thunks we always have it changed
2260 from 0 to 1 and all other nodes do not change it. */
2261 if (!cs->callee->instrumentation_clone
2262 && callee->instrumentation_clone)
2263 {
2264 for (i = 0; i < parms_count; i++)
2265 ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info,
2266 i));
2267 return ret;
2268 }
2269
2270 /* If this call goes through a thunk we must not propagate to the first (0th)
2271 parameter. However, we might need to uncover a thunk from below a series
2272 of aliases first. */
2273 if (call_passes_through_thunk_p (cs))
2274 {
2275 ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info,
2276 0));
2277 i = 1;
2278 }
2279 else
2280 i = 0;
2281
2282 for (; (i < args_count) && (i < parms_count); i++)
2283 {
2284 struct ipa_jump_func *jump_func = ipa_get_ith_jump_func (args, i);
2285 struct ipcp_param_lattices *dest_plats;
2286 tree param_type = ipa_get_type (callee_info, i);
2287
2288 dest_plats = ipa_get_parm_lattices (callee_info, i);
2289 if (availability == AVAIL_INTERPOSABLE)
2290 ret |= set_all_contains_variable (dest_plats);
2291 else
2292 {
2293 ret |= propagate_scalar_across_jump_function (cs, jump_func,
2294 &dest_plats->itself,
2295 param_type);
2296 ret |= propagate_context_across_jump_function (cs, jump_func, i,
2297 &dest_plats->ctxlat);
2298 ret
2299 |= propagate_bits_across_jump_function (cs, i, jump_func,
2300 &dest_plats->bits_lattice);
2301 ret |= propagate_aggs_across_jump_function (cs, jump_func,
2302 dest_plats);
2303 if (opt_for_fn (callee->decl, flag_ipa_vrp))
2304 ret |= propagate_vr_across_jump_function (cs, jump_func,
2305 dest_plats, param_type);
2306 else
2307 ret |= dest_plats->m_value_range.set_to_bottom ();
2308 }
2309 }
2310 for (; i < parms_count; i++)
2311 ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info, i));
2312
2313 return ret;
2314}
2315
2316/* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
2317 KNOWN_CONTEXTS, KNOWN_AGGS or AGG_REPS return the destination. The latter
2318 three can be NULL. If AGG_REPS is not NULL, KNOWN_AGGS is ignored. */
2319
2320static tree
2321ipa_get_indirect_edge_target_1 (struct cgraph_edge *ie,
2322 vec<tree> known_csts,
2323 vec<ipa_polymorphic_call_context> known_contexts,
2324 vec<ipa_agg_jump_function_p> known_aggs,
2325 struct ipa_agg_replacement_value *agg_reps,
2326 bool *speculative)
2327{
2328 int param_index = ie->indirect_info->param_index;
2329 HOST_WIDE_INT anc_offset;
2330 tree t;
2331 tree target = NULL;
2332
2333 *speculative = false;
2334
2335 if (param_index == -1
2336 || known_csts.length () <= (unsigned int) param_index)
2337 return NULL_TREE;
2338
2339 if (!ie->indirect_info->polymorphic)
2340 {
2341 tree t;
2342
2343 if (ie->indirect_info->agg_contents)
2344 {
2345 t = NULL;
2346 if (agg_reps && ie->indirect_info->guaranteed_unmodified)
2347 {
2348 while (agg_reps)
2349 {
2350 if (agg_reps->index == param_index
2351 && agg_reps->offset == ie->indirect_info->offset
2352 && agg_reps->by_ref == ie->indirect_info->by_ref)
2353 {
2354 t = agg_reps->value;
2355 break;
2356 }
2357 agg_reps = agg_reps->next;
2358 }
2359 }
2360 if (!t)
2361 {
2362 struct ipa_agg_jump_function *agg;
2363 if (known_aggs.length () > (unsigned int) param_index)
2364 agg = known_aggs[param_index];
2365 else
2366 agg = NULL;
2367 bool from_global_constant;
2368 t = ipa_find_agg_cst_for_param (agg, known_csts[param_index],
2369 ie->indirect_info->offset,
2370 ie->indirect_info->by_ref,
2371 &from_global_constant);
2372 if (t
2373 && !from_global_constant
2374 && !ie->indirect_info->guaranteed_unmodified)
2375 t = NULL_TREE;
2376 }
2377 }
2378 else
2379 t = known_csts[param_index];
2380
2381 if (t
2382 && TREE_CODE (t) == ADDR_EXPR
2383 && TREE_CODE (TREE_OPERAND (t, 0)) == FUNCTION_DECL)
2384 return TREE_OPERAND (t, 0);
2385 else
2386 return NULL_TREE;
2387 }
2388
2389 if (!opt_for_fn (ie->caller->decl, flag_devirtualize))
2390 return NULL_TREE;
2391
2392 gcc_assert (!ie->indirect_info->agg_contents);
2393 anc_offset = ie->indirect_info->offset;
2394
2395 t = NULL;
2396
2397 /* Try to work out value of virtual table pointer value in replacemnets. */
2398 if (!t && agg_reps && !ie->indirect_info->by_ref)
2399 {
2400 while (agg_reps)
2401 {
2402 if (agg_reps->index == param_index
2403 && agg_reps->offset == ie->indirect_info->offset
2404 && agg_reps->by_ref)
2405 {
2406 t = agg_reps->value;
2407 break;
2408 }
2409 agg_reps = agg_reps->next;
2410 }
2411 }
2412
2413 /* Try to work out value of virtual table pointer value in known
2414 aggregate values. */
2415 if (!t && known_aggs.length () > (unsigned int) param_index
2416 && !ie->indirect_info->by_ref)
2417 {
2418 struct ipa_agg_jump_function *agg;
2419 agg = known_aggs[param_index];
2420 t = ipa_find_agg_cst_for_param (agg, known_csts[param_index],
2421 ie->indirect_info->offset, true);
2422 }
2423
2424 /* If we found the virtual table pointer, lookup the target. */
2425 if (t)
2426 {
2427 tree vtable;
2428 unsigned HOST_WIDE_INT offset;
2429 if (vtable_pointer_value_to_vtable (t, &vtable, &offset))
2430 {
2431 bool can_refer;
2432 target = gimple_get_virt_method_for_vtable (ie->indirect_info->otr_token,
2433 vtable, offset, &can_refer);
2434 if (can_refer)
2435 {
2436 if (!target
2437 || (TREE_CODE (TREE_TYPE (target)) == FUNCTION_TYPE
2438 && DECL_FUNCTION_CODE (target) == BUILT_IN_UNREACHABLE)
2439 || !possible_polymorphic_call_target_p
2440 (ie, cgraph_node::get (target)))
2441 {
2442 /* Do not speculate builtin_unreachable, it is stupid! */
2443 if (ie->indirect_info->vptr_changed)
2444 return NULL;
2445 target = ipa_impossible_devirt_target (ie, target);
2446 }
2447 *speculative = ie->indirect_info->vptr_changed;
2448 if (!*speculative)
2449 return target;
2450 }
2451 }
2452 }
2453
2454 /* Do we know the constant value of pointer? */
2455 if (!t)
2456 t = known_csts[param_index];
2457
2458 gcc_checking_assert (!t || TREE_CODE (t) != TREE_BINFO);
2459
2460 ipa_polymorphic_call_context context;
2461 if (known_contexts.length () > (unsigned int) param_index)
2462 {
2463 context = known_contexts[param_index];
2464 context.offset_by (anc_offset);
2465 if (ie->indirect_info->vptr_changed)
2466 context.possible_dynamic_type_change (ie->in_polymorphic_cdtor,
2467 ie->indirect_info->otr_type);
2468 if (t)
2469 {
2470 ipa_polymorphic_call_context ctx2 = ipa_polymorphic_call_context
2471 (t, ie->indirect_info->otr_type, anc_offset);
2472 if (!ctx2.useless_p ())
2473 context.combine_with (ctx2, ie->indirect_info->otr_type);
2474 }
2475 }
2476 else if (t)
2477 {
2478 context = ipa_polymorphic_call_context (t, ie->indirect_info->otr_type,
2479 anc_offset);
2480 if (ie->indirect_info->vptr_changed)
2481 context.possible_dynamic_type_change (ie->in_polymorphic_cdtor,
2482 ie->indirect_info->otr_type);
2483 }
2484 else
2485 return NULL_TREE;
2486
2487 vec <cgraph_node *>targets;
2488 bool final;
2489
2490 targets = possible_polymorphic_call_targets
2491 (ie->indirect_info->otr_type,
2492 ie->indirect_info->otr_token,
2493 context, &final);
2494 if (!final || targets.length () > 1)
2495 {
2496 struct cgraph_node *node;
2497 if (*speculative)
2498 return target;
2499 if (!opt_for_fn (ie->caller->decl, flag_devirtualize_speculatively)
2500 || ie->speculative || !ie->maybe_hot_p ())
2501 return NULL;
2502 node = try_speculative_devirtualization (ie->indirect_info->otr_type,
2503 ie->indirect_info->otr_token,
2504 context);
2505 if (node)
2506 {
2507 *speculative = true;
2508 target = node->decl;
2509 }
2510 else
2511 return NULL;
2512 }
2513 else
2514 {
2515 *speculative = false;
2516 if (targets.length () == 1)
2517 target = targets[0]->decl;
2518 else
2519 target = ipa_impossible_devirt_target (ie, NULL_TREE);
2520 }
2521
2522 if (target && !possible_polymorphic_call_target_p (ie,
2523 cgraph_node::get (target)))
2524 {
2525 if (*speculative)
2526 return NULL;
2527 target = ipa_impossible_devirt_target (ie, target);
2528 }
2529
2530 return target;
2531}
2532
2533
2534/* If an indirect edge IE can be turned into a direct one based on KNOWN_CSTS,
2535 KNOWN_CONTEXTS (which can be vNULL) or KNOWN_AGGS (which also can be vNULL)
2536 return the destination. */
2537
2538tree
2539ipa_get_indirect_edge_target (struct cgraph_edge *ie,
2540 vec<tree> known_csts,
2541 vec<ipa_polymorphic_call_context> known_contexts,
2542 vec<ipa_agg_jump_function_p> known_aggs,
2543 bool *speculative)
2544{
2545 return ipa_get_indirect_edge_target_1 (ie, known_csts, known_contexts,
2546 known_aggs, NULL, speculative);
2547}
2548
2549/* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
2550 and KNOWN_CONTEXTS. */
2551
2552static int
2553devirtualization_time_bonus (struct cgraph_node *node,
2554 vec<tree> known_csts,
2555 vec<ipa_polymorphic_call_context> known_contexts,
2556 vec<ipa_agg_jump_function_p> known_aggs)
2557{
2558 struct cgraph_edge *ie;
2559 int res = 0;
2560
2561 for (ie = node->indirect_calls; ie; ie = ie->next_callee)
2562 {
2563 struct cgraph_node *callee;
2564 struct ipa_fn_summary *isummary;
2565 enum availability avail;
2566 tree target;
2567 bool speculative;
2568
2569 target = ipa_get_indirect_edge_target (ie, known_csts, known_contexts,
2570 known_aggs, &speculative);
2571 if (!target)
2572 continue;
2573
2574 /* Only bare minimum benefit for clearly un-inlineable targets. */
2575 res += 1;
2576 callee = cgraph_node::get (target);
2577 if (!callee || !callee->definition)
2578 continue;
2579 callee = callee->function_symbol (&avail);
2580 if (avail < AVAIL_AVAILABLE)
2581 continue;
2582 isummary = ipa_fn_summaries->get (callee);
2583 if (!isummary->inlinable)
2584 continue;
2585
2586 /* FIXME: The values below need re-considering and perhaps also
2587 integrating into the cost metrics, at lest in some very basic way. */
2588 if (isummary->size <= MAX_INLINE_INSNS_AUTO / 4)
2589 res += 31 / ((int)speculative + 1);
2590 else if (isummary->size <= MAX_INLINE_INSNS_AUTO / 2)
2591 res += 15 / ((int)speculative + 1);
2592 else if (isummary->size <= MAX_INLINE_INSNS_AUTO
2593 || DECL_DECLARED_INLINE_P (callee->decl))
2594 res += 7 / ((int)speculative + 1);
2595 }
2596
2597 return res;
2598}
2599
2600/* Return time bonus incurred because of HINTS. */
2601
2602static int
2603hint_time_bonus (ipa_hints hints)
2604{
2605 int result = 0;
2606 if (hints & (INLINE_HINT_loop_iterations | INLINE_HINT_loop_stride))
2607 result += PARAM_VALUE (PARAM_IPA_CP_LOOP_HINT_BONUS);
2608 if (hints & INLINE_HINT_array_index)
2609 result += PARAM_VALUE (PARAM_IPA_CP_ARRAY_INDEX_HINT_BONUS);
2610 return result;
2611}
2612
2613/* If there is a reason to penalize the function described by INFO in the
2614 cloning goodness evaluation, do so. */
2615
2616static inline int64_t
2617incorporate_penalties (ipa_node_params *info, int64_t evaluation)
2618{
2619 if (info->node_within_scc)
2620 evaluation = (evaluation
2621 * (100 - PARAM_VALUE (PARAM_IPA_CP_RECURSION_PENALTY))) / 100;
2622
2623 if (info->node_calling_single_call)
2624 evaluation = (evaluation
2625 * (100 - PARAM_VALUE (PARAM_IPA_CP_SINGLE_CALL_PENALTY)))
2626 / 100;
2627
2628 return evaluation;
2629}
2630
2631/* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
2632 and SIZE_COST and with the sum of frequencies of incoming edges to the
2633 potential new clone in FREQUENCIES. */
2634
2635static bool
2636good_cloning_opportunity_p (struct cgraph_node *node, int time_benefit,
2637 int freq_sum, profile_count count_sum, int size_cost)
2638{
2639 if (time_benefit == 0
2640 || !opt_for_fn (node->decl, flag_ipa_cp_clone)
2641 || node->optimize_for_size_p ())
2642 return false;
2643
2644 gcc_assert (size_cost > 0);
2645
2646 struct ipa_node_params *info = IPA_NODE_REF (node);
2647 if (max_count > profile_count::zero ())
2648 {
2649 int factor = RDIV (count_sum.probability_in
2650 (max_count).to_reg_br_prob_base ()
2651 * 1000, REG_BR_PROB_BASE);
2652 int64_t evaluation = (((int64_t) time_benefit * factor)
2653 / size_cost);
2654 evaluation = incorporate_penalties (info, evaluation);
2655
2656 if (dump_file && (dump_flags & TDF_DETAILS))
2657 {
2658 fprintf (dump_file, " good_cloning_opportunity_p (time: %i, "
2659 "size: %i, count_sum: ", time_benefit, size_cost);
2660 count_sum.dump (dump_file);
2661 fprintf (dump_file, "%s%s) -> evaluation: " "%" PRId64
2662 ", threshold: %i\n",
2663 info->node_within_scc ? ", scc" : "",
2664 info->node_calling_single_call ? ", single_call" : "",
2665 evaluation, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD));
2666 }
2667
2668 return evaluation >= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD);
2669 }
2670 else
2671 {
2672 int64_t evaluation = (((int64_t) time_benefit * freq_sum)
2673 / size_cost);
2674 evaluation = incorporate_penalties (info, evaluation);
2675
2676 if (dump_file && (dump_flags & TDF_DETAILS))
2677 fprintf (dump_file, " good_cloning_opportunity_p (time: %i, "
2678 "size: %i, freq_sum: %i%s%s) -> evaluation: "
2679 "%" PRId64 ", threshold: %i\n",
2680 time_benefit, size_cost, freq_sum,
2681 info->node_within_scc ? ", scc" : "",
2682 info->node_calling_single_call ? ", single_call" : "",
2683 evaluation, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD));
2684
2685 return evaluation >= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD);
2686 }
2687}
2688
2689/* Return all context independent values from aggregate lattices in PLATS in a
2690 vector. Return NULL if there are none. */
2691
2692static vec<ipa_agg_jf_item, va_gc> *
2693context_independent_aggregate_values (struct ipcp_param_lattices *plats)
2694{
2695 vec<ipa_agg_jf_item, va_gc> *res = NULL;
2696
2697 if (plats->aggs_bottom
2698 || plats->aggs_contain_variable
2699 || plats->aggs_count == 0)
2700 return NULL;
2701
2702 for (struct ipcp_agg_lattice *aglat = plats->aggs;
2703 aglat;
2704 aglat = aglat->next)
2705 if (aglat->is_single_const ())
2706 {
2707 struct ipa_agg_jf_item item;
2708 item.offset = aglat->offset;
2709 item.value = aglat->values->value;
2710 vec_safe_push (res, item);
2711 }
2712 return res;
2713}
2714
2715/* Allocate KNOWN_CSTS, KNOWN_CONTEXTS and, if non-NULL, KNOWN_AGGS and
2716 populate them with values of parameters that are known independent of the
2717 context. INFO describes the function. If REMOVABLE_PARAMS_COST is
2718 non-NULL, the movement cost of all removable parameters will be stored in
2719 it. */
2720
2721static bool
2722gather_context_independent_values (struct ipa_node_params *info,
2723 vec<tree> *known_csts,
2724 vec<ipa_polymorphic_call_context>
2725 *known_contexts,
2726 vec<ipa_agg_jump_function> *known_aggs,
2727 int *removable_params_cost)
2728{
2729 int i, count = ipa_get_param_count (info);
2730 bool ret = false;
2731
2732 known_csts->create (0);
2733 known_contexts->create (0);
2734 known_csts->safe_grow_cleared (count);
2735 known_contexts->safe_grow_cleared (count);
2736 if (known_aggs)
2737 {
2738 known_aggs->create (0);
2739 known_aggs->safe_grow_cleared (count);
2740 }
2741
2742 if (removable_params_cost)
2743 *removable_params_cost = 0;
2744
2745 for (i = 0; i < count; i++)
2746 {
2747 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
2748 ipcp_lattice<tree> *lat = &plats->itself;
2749
2750 if (lat->is_single_const ())
2751 {
2752 ipcp_value<tree> *val = lat->values;
2753 gcc_checking_assert (TREE_CODE (val->value) != TREE_BINFO);
2754 (*known_csts)[i] = val->value;
2755 if (removable_params_cost)
2756 *removable_params_cost
2757 += estimate_move_cost (TREE_TYPE (val->value), false);
2758 ret = true;
2759 }
2760 else if (removable_params_cost
2761 && !ipa_is_param_used (info, i))
2762 *removable_params_cost
2763 += ipa_get_param_move_cost (info, i);
2764
2765 if (!ipa_is_param_used (info, i))
2766 continue;
2767
2768 ipcp_lattice<ipa_polymorphic_call_context> *ctxlat = &plats->ctxlat;
2769 /* Do not account known context as reason for cloning. We can see
2770 if it permits devirtualization. */
2771 if (ctxlat->is_single_const ())
2772 (*known_contexts)[i] = ctxlat->values->value;
2773
2774 if (known_aggs)
2775 {
2776 vec<ipa_agg_jf_item, va_gc> *agg_items;
2777 struct ipa_agg_jump_function *ajf;
2778
2779 agg_items = context_independent_aggregate_values (plats);
2780 ajf = &(*known_aggs)[i];
2781 ajf->items = agg_items;
2782 ajf->by_ref = plats->aggs_by_ref;
2783 ret |= agg_items != NULL;
2784 }
2785 }
2786
2787 return ret;
2788}
2789
2790/* The current interface in ipa-inline-analysis requires a pointer vector.
2791 Create it.
2792
2793 FIXME: That interface should be re-worked, this is slightly silly. Still,
2794 I'd like to discuss how to change it first and this demonstrates the
2795 issue. */
2796
2797static vec<ipa_agg_jump_function_p>
2798agg_jmp_p_vec_for_t_vec (vec<ipa_agg_jump_function> known_aggs)
2799{
2800 vec<ipa_agg_jump_function_p> ret;
2801 struct ipa_agg_jump_function *ajf;
2802 int i;
2803
2804 ret.create (known_aggs.length ());
2805 FOR_EACH_VEC_ELT (known_aggs, i, ajf)
2806 ret.quick_push (ajf);
2807 return ret;
2808}
2809
2810/* Perform time and size measurement of NODE with the context given in
2811 KNOWN_CSTS, KNOWN_CONTEXTS and KNOWN_AGGS, calculate the benefit and cost
2812 given BASE_TIME of the node without specialization, REMOVABLE_PARAMS_COST of
2813 all context-independent removable parameters and EST_MOVE_COST of estimated
2814 movement of the considered parameter and store it into VAL. */
2815
2816static void
2817perform_estimation_of_a_value (cgraph_node *node, vec<tree> known_csts,
2818 vec<ipa_polymorphic_call_context> known_contexts,
2819 vec<ipa_agg_jump_function_p> known_aggs_ptrs,
2820 int removable_params_cost,
2821 int est_move_cost, ipcp_value_base *val)
2822{
2823 int size, time_benefit;
2824 sreal time, base_time;
2825 ipa_hints hints;
2826
2827 estimate_ipcp_clone_size_and_time (node, known_csts, known_contexts,
2828 known_aggs_ptrs, &size, &time,
2829 &base_time, &hints);
2830 base_time -= time;
2831 if (base_time > 65535)
2832 base_time = 65535;
2833 time_benefit = base_time.to_int ()
2834 + devirtualization_time_bonus (node, known_csts, known_contexts,
2835 known_aggs_ptrs)
2836 + hint_time_bonus (hints)
2837 + removable_params_cost + est_move_cost;
2838
2839 gcc_checking_assert (size >=0);
2840 /* The inliner-heuristics based estimates may think that in certain
2841 contexts some functions do not have any size at all but we want
2842 all specializations to have at least a tiny cost, not least not to
2843 divide by zero. */
2844 if (size == 0)
2845 size = 1;
2846
2847 val->local_time_benefit = time_benefit;
2848 val->local_size_cost = size;
2849}
2850
2851/* Iterate over known values of parameters of NODE and estimate the local
2852 effects in terms of time and size they have. */
2853
2854static void
2855estimate_local_effects (struct cgraph_node *node)
2856{
2857 struct ipa_node_params *info = IPA_NODE_REF (node);
2858 int i, count = ipa_get_param_count (info);
2859 vec<tree> known_csts;
2860 vec<ipa_polymorphic_call_context> known_contexts;
2861 vec<ipa_agg_jump_function> known_aggs;
2862 vec<ipa_agg_jump_function_p> known_aggs_ptrs;
2863 bool always_const;
2864 int removable_params_cost;
2865
2866 if (!count || !ipcp_versionable_function_p (node))
2867 return;
2868
2869 if (dump_file && (dump_flags & TDF_DETAILS))
2870 fprintf (dump_file, "\nEstimating effects for %s.\n", node->dump_name ());
2871
2872 always_const = gather_context_independent_values (info, &known_csts,
2873 &known_contexts, &known_aggs,
2874 &removable_params_cost);
2875 known_aggs_ptrs = agg_jmp_p_vec_for_t_vec (known_aggs);
2876 int devirt_bonus = devirtualization_time_bonus (node, known_csts,
2877 known_contexts, known_aggs_ptrs);
2878 if (always_const || devirt_bonus
2879 || (removable_params_cost && node->local.can_change_signature))
2880 {
2881 struct caller_statistics stats;
2882 ipa_hints hints;
2883 sreal time, base_time;
2884 int size;
2885
2886 init_caller_stats (&stats);
2887 node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats,
2888 false);
2889 estimate_ipcp_clone_size_and_time (node, known_csts, known_contexts,
2890 known_aggs_ptrs, &size, &time,
2891 &base_time, &hints);
2892 time -= devirt_bonus;
2893 time -= hint_time_bonus (hints);
2894 time -= removable_params_cost;
2895 size -= stats.n_calls * removable_params_cost;
2896
2897 if (dump_file)
2898 fprintf (dump_file, " - context independent values, size: %i, "
2899 "time_benefit: %f\n", size, (base_time - time).to_double ());
2900
2901 if (size <= 0 || node->local.local)
2902 {
2903 info->do_clone_for_all_contexts = true;
2904
2905 if (dump_file)
2906 fprintf (dump_file, " Decided to specialize for all "
2907 "known contexts, code not going to grow.\n");
2908 }
2909 else if (good_cloning_opportunity_p (node,
2910 MAX ((base_time - time).to_int (),
2911 65536),
2912 stats.freq_sum, stats.count_sum,
2913 size))
2914 {
2915 if (size + overall_size <= max_new_size)
2916 {
2917 info->do_clone_for_all_contexts = true;
2918 overall_size += size;
2919
2920 if (dump_file)
2921 fprintf (dump_file, " Decided to specialize for all "
2922 "known contexts, growth deemed beneficial.\n");
2923 }
2924 else if (dump_file && (dump_flags & TDF_DETAILS))
2925 fprintf (dump_file, " Not cloning for all contexts because "
2926 "max_new_size would be reached with %li.\n",
2927 size + overall_size);
2928 }
2929 else if (dump_file && (dump_flags & TDF_DETAILS))
2930 fprintf (dump_file, " Not cloning for all contexts because "
2931 "!good_cloning_opportunity_p.\n");
2932
2933 }
2934
2935 for (i = 0; i < count; i++)
2936 {
2937 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
2938 ipcp_lattice<tree> *lat = &plats->itself;
2939 ipcp_value<tree> *val;
2940
2941 if (lat->bottom
2942 || !lat->values
2943 || known_csts[i])
2944 continue;
2945
2946 for (val = lat->values; val; val = val->next)
2947 {
2948 gcc_checking_assert (TREE_CODE (val->value) != TREE_BINFO);
2949 known_csts[i] = val->value;
2950
2951 int emc = estimate_move_cost (TREE_TYPE (val->value), true);
2952 perform_estimation_of_a_value (node, known_csts, known_contexts,
2953 known_aggs_ptrs,
2954 removable_params_cost, emc, val);
2955
2956 if (dump_file && (dump_flags & TDF_DETAILS))
2957 {
2958 fprintf (dump_file, " - estimates for value ");
2959 print_ipcp_constant_value (dump_file, val->value);
2960 fprintf (dump_file, " for ");
2961 ipa_dump_param (dump_file, info, i);
2962 fprintf (dump_file, ": time_benefit: %i, size: %i\n",
2963 val->local_time_benefit, val->local_size_cost);
2964 }
2965 }
2966 known_csts[i] = NULL_TREE;
2967 }
2968
2969 for (i = 0; i < count; i++)
2970 {
2971 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
2972
2973 if (!plats->virt_call)
2974 continue;
2975
2976 ipcp_lattice<ipa_polymorphic_call_context> *ctxlat = &plats->ctxlat;
2977 ipcp_value<ipa_polymorphic_call_context> *val;
2978
2979 if (ctxlat->bottom
2980 || !ctxlat->values
2981 || !known_contexts[i].useless_p ())
2982 continue;
2983
2984 for (val = ctxlat->values; val; val = val->next)
2985 {
2986 known_contexts[i] = val->value;
2987 perform_estimation_of_a_value (node, known_csts, known_contexts,
2988 known_aggs_ptrs,
2989 removable_params_cost, 0, val);
2990
2991 if (dump_file && (dump_flags & TDF_DETAILS))
2992 {
2993 fprintf (dump_file, " - estimates for polymorphic context ");
2994 print_ipcp_constant_value (dump_file, val->value);
2995 fprintf (dump_file, " for ");
2996 ipa_dump_param (dump_file, info, i);
2997 fprintf (dump_file, ": time_benefit: %i, size: %i\n",
2998 val->local_time_benefit, val->local_size_cost);
2999 }
3000 }
3001 known_contexts[i] = ipa_polymorphic_call_context ();
3002 }
3003
3004 for (i = 0; i < count; i++)
3005 {
3006 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
3007 struct ipa_agg_jump_function *ajf;
3008 struct ipcp_agg_lattice *aglat;
3009
3010 if (plats->aggs_bottom || !plats->aggs)
3011 continue;
3012
3013 ajf = &known_aggs[i];
3014 for (aglat = plats->aggs; aglat; aglat = aglat->next)
3015 {
3016 ipcp_value<tree> *val;
3017 if (aglat->bottom || !aglat->values
3018 /* If the following is true, the one value is in known_aggs. */
3019 || (!plats->aggs_contain_variable
3020 && aglat->is_single_const ()))
3021 continue;
3022
3023 for (val = aglat->values; val; val = val->next)
3024 {
3025 struct ipa_agg_jf_item item;
3026
3027 item.offset = aglat->offset;
3028 item.value = val->value;
3029 vec_safe_push (ajf->items, item);
3030
3031 perform_estimation_of_a_value (node, known_csts, known_contexts,
3032 known_aggs_ptrs,
3033 removable_params_cost, 0, val);
3034
3035 if (dump_file && (dump_flags & TDF_DETAILS))
3036 {
3037 fprintf (dump_file, " - estimates for value ");
3038 print_ipcp_constant_value (dump_file, val->value);
3039 fprintf (dump_file, " for ");
3040 ipa_dump_param (dump_file, info, i);
3041 fprintf (dump_file, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
3042 "]: time_benefit: %i, size: %i\n",
3043 plats->aggs_by_ref ? "ref " : "",
3044 aglat->offset,
3045 val->local_time_benefit, val->local_size_cost);
3046 }
3047
3048 ajf->items->pop ();
3049 }
3050 }
3051 }
3052
3053 for (i = 0; i < count; i++)
3054 vec_free (known_aggs[i].items);
3055
3056 known_csts.release ();
3057 known_contexts.release ();
3058 known_aggs.release ();
3059 known_aggs_ptrs.release ();
3060}
3061
3062
3063/* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
3064 topological sort of values. */
3065
3066template <typename valtype>
3067void
3068value_topo_info<valtype>::add_val (ipcp_value<valtype> *cur_val)
3069{
3070 ipcp_value_source<valtype> *src;
3071
3072 if (cur_val->dfs)
3073 return;
3074
3075 dfs_counter++;
3076 cur_val->dfs = dfs_counter;
3077 cur_val->low_link = dfs_counter;
3078
3079 cur_val->topo_next = stack;
3080 stack = cur_val;
3081 cur_val->on_stack = true;
3082
3083 for (src = cur_val->sources; src; src = src->next)
3084 if (src->val)
3085 {
3086 if (src->val->dfs == 0)
3087 {
3088 add_val (src->val);
3089 if (src->val->low_link < cur_val->low_link)
3090 cur_val->low_link = src->val->low_link;
3091 }
3092 else if (src->val->on_stack
3093 && src->val->dfs < cur_val->low_link)
3094 cur_val->low_link = src->val->dfs;
3095 }
3096
3097 if (cur_val->dfs == cur_val->low_link)
3098 {
3099 ipcp_value<valtype> *v, *scc_list = NULL;
3100
3101 do
3102 {
3103 v = stack;
3104 stack = v->topo_next;
3105 v->on_stack = false;
3106
3107 v->scc_next = scc_list;
3108 scc_list = v;
3109 }
3110 while (v != cur_val);
3111
3112 cur_val->topo_next = values_topo;
3113 values_topo = cur_val;
3114 }
3115}
3116
3117/* Add all values in lattices associated with NODE to the topological sort if
3118 they are not there yet. */
3119
3120static void
3121add_all_node_vals_to_toposort (cgraph_node *node, ipa_topo_info *topo)
3122{
3123 struct ipa_node_params *info = IPA_NODE_REF (node);
3124 int i, count = ipa_get_param_count (info);
3125
3126 for (i = 0; i < count; i++)
3127 {
3128 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
3129 ipcp_lattice<tree> *lat = &plats->itself;
3130 struct ipcp_agg_lattice *aglat;
3131
3132 if (!lat->bottom)
3133 {
3134 ipcp_value<tree> *val;
3135 for (val = lat->values; val; val = val->next)
3136 topo->constants.add_val (val);
3137 }
3138
3139 if (!plats->aggs_bottom)
3140 for (aglat = plats->aggs; aglat; aglat = aglat->next)
3141 if (!aglat->bottom)
3142 {
3143 ipcp_value<tree> *val;
3144 for (val = aglat->values; val; val = val->next)
3145 topo->constants.add_val (val);
3146 }
3147
3148 ipcp_lattice<ipa_polymorphic_call_context> *ctxlat = &plats->ctxlat;
3149 if (!ctxlat->bottom)
3150 {
3151 ipcp_value<ipa_polymorphic_call_context> *ctxval;
3152 for (ctxval = ctxlat->values; ctxval; ctxval = ctxval->next)
3153 topo->contexts.add_val (ctxval);
3154 }
3155 }
3156}
3157
3158/* One pass of constants propagation along the call graph edges, from callers
3159 to callees (requires topological ordering in TOPO), iterate over strongly
3160 connected components. */
3161
3162static void
3163propagate_constants_topo (struct ipa_topo_info *topo)
3164{
3165 int i;
3166
3167 for (i = topo->nnodes - 1; i >= 0; i--)
3168 {
3169 unsigned j;
3170 struct cgraph_node *v, *node = topo->order[i];
3171 vec<cgraph_node *> cycle_nodes = ipa_get_nodes_in_cycle (node);
3172
3173 /* First, iteratively propagate within the strongly connected component
3174 until all lattices stabilize. */
3175 FOR_EACH_VEC_ELT (cycle_nodes, j, v)
3176 if (v->has_gimple_body_p ())
3177 push_node_to_stack (topo, v);
3178
3179 v = pop_node_from_stack (topo);
3180 while (v)
3181 {
3182 struct cgraph_edge *cs;
3183
3184 for (cs = v->callees; cs; cs = cs->next_callee)
3185 if (ipa_edge_within_scc (cs))
3186 {
3187 IPA_NODE_REF (v)->node_within_scc = true;
3188 if (propagate_constants_across_call (cs))
3189 push_node_to_stack (topo, cs->callee->function_symbol ());
3190 }
3191 v = pop_node_from_stack (topo);
3192 }
3193
3194 /* Afterwards, propagate along edges leading out of the SCC, calculates
3195 the local effects of the discovered constants and all valid values to
3196 their topological sort. */
3197 FOR_EACH_VEC_ELT (cycle_nodes, j, v)
3198 if (v->has_gimple_body_p ())
3199 {
3200 struct cgraph_edge *cs;
3201
3202 estimate_local_effects (v);
3203 add_all_node_vals_to_toposort (v, topo);
3204 for (cs = v->callees; cs; cs = cs->next_callee)
3205 if (!ipa_edge_within_scc (cs))
3206 propagate_constants_across_call (cs);
3207 }
3208 cycle_nodes.release ();
3209 }
3210}
3211
3212
3213/* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
3214 the bigger one if otherwise. */
3215
3216static int
3217safe_add (int a, int b)
3218{
3219 if (a > INT_MAX/2 || b > INT_MAX/2)
3220 return a > b ? a : b;
3221 else
3222 return a + b;
3223}
3224
3225
3226/* Propagate the estimated effects of individual values along the topological
3227 from the dependent values to those they depend on. */
3228
3229template <typename valtype>
3230void
3231value_topo_info<valtype>::propagate_effects ()
3232{
3233 ipcp_value<valtype> *base;
3234
3235 for (base = values_topo; base; base = base->topo_next)
3236 {
3237 ipcp_value_source<valtype> *src;
3238 ipcp_value<valtype> *val;
3239 int time = 0, size = 0;
3240
3241 for (val = base; val; val = val->scc_next)
3242 {
3243 time = safe_add (time,
3244 val->local_time_benefit + val->prop_time_benefit);
3245 size = safe_add (size, val->local_size_cost + val->prop_size_cost);
3246 }
3247
3248 for (val = base; val; val = val->scc_next)
3249 for (src = val->sources; src; src = src->next)
3250 if (src->val
3251 && src->cs->maybe_hot_p ())
3252 {
3253 src->val->prop_time_benefit = safe_add (time,
3254 src->val->prop_time_benefit);
3255 src->val->prop_size_cost = safe_add (size,
3256 src->val->prop_size_cost);
3257 }
3258 }
3259}
3260
3261
3262/* Propagate constants, polymorphic contexts and their effects from the
3263 summaries interprocedurally. */
3264
3265static void
3266ipcp_propagate_stage (struct ipa_topo_info *topo)
3267{
3268 struct cgraph_node *node;
3269
3270 if (dump_file)
3271 fprintf (dump_file, "\n Propagating constants:\n\n");
3272
3273 max_count = profile_count::uninitialized ();
3274
3275 FOR_EACH_DEFINED_FUNCTION (node)
3276 {
3277 struct ipa_node_params *info = IPA_NODE_REF (node);
3278
3279 determine_versionability (node, info);
3280 if (node->has_gimple_body_p ())
3281 {
3282 info->lattices = XCNEWVEC (struct ipcp_param_lattices,
3283 ipa_get_param_count (info));
3284 initialize_node_lattices (node);
3285 }
3286 if (node->definition && !node->alias)
3287 overall_size += ipa_fn_summaries->get (node)->self_size;
3288 max_count = max_count.max (node->count.ipa ());
3289 }
3290
3291 max_new_size = overall_size;
3292 if (max_new_size < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
3293 max_new_size = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
3294 max_new_size += max_new_size * PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH) / 100 + 1;
3295
3296 if (dump_file)
3297 fprintf (dump_file, "\noverall_size: %li, max_new_size: %li\n",
3298 overall_size, max_new_size);
3299
3300 propagate_constants_topo (topo);
3301 if (flag_checking)
3302 ipcp_verify_propagated_values ();
3303 topo->constants.propagate_effects ();
3304 topo->contexts.propagate_effects ();
3305
3306 if (dump_file)
3307 {
3308 fprintf (dump_file, "\nIPA lattices after all propagation:\n");
3309 print_all_lattices (dump_file, (dump_flags & TDF_DETAILS), true);
3310 }
3311}
3312
3313/* Discover newly direct outgoing edges from NODE which is a new clone with
3314 known KNOWN_CSTS and make them direct. */
3315
3316static void
3317ipcp_discover_new_direct_edges (struct cgraph_node *node,
3318 vec<tree> known_csts,
3319 vec<ipa_polymorphic_call_context>
3320 known_contexts,
3321 struct ipa_agg_replacement_value *aggvals)
3322{
3323 struct cgraph_edge *ie, *next_ie;
3324 bool found = false;
3325
3326 for (ie = node->indirect_calls; ie; ie = next_ie)
3327 {
3328 tree target;
3329 bool speculative;
3330
3331 next_ie = ie->next_callee;
3332 target = ipa_get_indirect_edge_target_1 (ie, known_csts, known_contexts,
3333 vNULL, aggvals, &speculative);
3334 if (target)
3335 {
3336 bool agg_contents = ie->indirect_info->agg_contents;
3337 bool polymorphic = ie->indirect_info->polymorphic;
3338 int param_index = ie->indirect_info->param_index;
3339 struct cgraph_edge *cs = ipa_make_edge_direct_to_target (ie, target,
3340 speculative);
3341 found = true;
3342
3343 if (cs && !agg_contents && !polymorphic)
3344 {
3345 struct ipa_node_params *info = IPA_NODE_REF (node);
3346 int c = ipa_get_controlled_uses (info, param_index);
3347 if (c != IPA_UNDESCRIBED_USE)
3348 {
3349 struct ipa_ref *to_del;
3350
3351 c--;
3352 ipa_set_controlled_uses (info, param_index, c);
3353 if (dump_file && (dump_flags & TDF_DETAILS))
3354 fprintf (dump_file, " controlled uses count of param "
3355 "%i bumped down to %i\n", param_index, c);
3356 if (c == 0
3357 && (to_del = node->find_reference (cs->callee, NULL, 0)))
3358 {
3359 if (dump_file && (dump_flags & TDF_DETAILS))
3360 fprintf (dump_file, " and even removing its "
3361 "cloning-created reference\n");
3362 to_del->remove_reference ();
3363 }
3364 }
3365 }
3366 }
3367 }
3368 /* Turning calls to direct calls will improve overall summary. */
3369 if (found)
3370 ipa_update_overall_fn_summary (node);
3371}
3372
3373/* Vector of pointers which for linked lists of clones of an original crgaph
3374 edge. */
3375
3376static vec<cgraph_edge *> next_edge_clone;
3377static vec<cgraph_edge *> prev_edge_clone;
3378
3379static inline void
3380grow_edge_clone_vectors (void)
3381{
3382 if (next_edge_clone.length ()
3383 <= (unsigned) symtab->edges_max_uid)
3384 next_edge_clone.safe_grow_cleared (symtab->edges_max_uid + 1);
3385 if (prev_edge_clone.length ()
3386 <= (unsigned) symtab->edges_max_uid)
3387 prev_edge_clone.safe_grow_cleared (symtab->edges_max_uid + 1);
3388}
3389
3390/* Edge duplication hook to grow the appropriate linked list in
3391 next_edge_clone. */
3392
3393static void
3394ipcp_edge_duplication_hook (struct cgraph_edge *src, struct cgraph_edge *dst,
3395 void *)
3396{
3397 grow_edge_clone_vectors ();
3398
3399 struct cgraph_edge *old_next = next_edge_clone[src->uid];
3400 if (old_next)
3401 prev_edge_clone[old_next->uid] = dst;
3402 prev_edge_clone[dst->uid] = src;
3403
3404 next_edge_clone[dst->uid] = old_next;
3405 next_edge_clone[src->uid] = dst;
3406}
3407
3408/* Hook that is called by cgraph.c when an edge is removed. */
3409
3410static void
3411ipcp_edge_removal_hook (struct cgraph_edge *cs, void *)
3412{
3413 grow_edge_clone_vectors ();
3414
3415 struct cgraph_edge *prev = prev_edge_clone[cs->uid];
3416 struct cgraph_edge *next = next_edge_clone[cs->uid];
3417 if (prev)
3418 next_edge_clone[prev->uid] = next;
3419 if (next)
3420 prev_edge_clone[next->uid] = prev;
3421}
3422
3423/* See if NODE is a clone with a known aggregate value at a given OFFSET of a
3424 parameter with the given INDEX. */
3425
3426static tree
3427get_clone_agg_value (struct cgraph_node *node, HOST_WIDE_INT offset,
3428 int index)
3429{
3430 struct ipa_agg_replacement_value *aggval;
3431
3432 aggval = ipa_get_agg_replacements_for_node (node);
3433 while (aggval)
3434 {
3435 if (aggval->offset == offset
3436 && aggval->index == index)
3437 return aggval->value;
3438 aggval = aggval->next;
3439 }
3440 return NULL_TREE;
3441}
3442
3443/* Return true is NODE is DEST or its clone for all contexts. */
3444
3445static bool
3446same_node_or_its_all_contexts_clone_p (cgraph_node *node, cgraph_node *dest)
3447{
3448 if (node == dest)
3449 return true;
3450
3451 struct ipa_node_params *info = IPA_NODE_REF (node);
3452 return info->is_all_contexts_clone && info->ipcp_orig_node == dest;
3453}
3454
3455/* Return true if edge CS does bring about the value described by SRC to node
3456 DEST or its clone for all contexts. */
3457
3458static bool
3459cgraph_edge_brings_value_p (cgraph_edge *cs, ipcp_value_source<tree> *src,
3460 cgraph_node *dest)
3461{
3462 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
3463 enum availability availability;
3464 cgraph_node *real_dest = cs->callee->function_symbol (&availability);
3465
3466 if (!same_node_or_its_all_contexts_clone_p (real_dest, dest)
3467 || availability <= AVAIL_INTERPOSABLE
3468 || caller_info->node_dead)
3469 return false;
3470 if (!src->val)
3471 return true;
3472
3473 if (caller_info->ipcp_orig_node)
3474 {
3475 tree t;
3476 if (src->offset == -1)
3477 t = caller_info->known_csts[src->index];
3478 else
3479 t = get_clone_agg_value (cs->caller, src->offset, src->index);
3480 return (t != NULL_TREE
3481 && values_equal_for_ipcp_p (src->val->value, t));
3482 }
3483 else
3484 {
3485 struct ipcp_agg_lattice *aglat;
3486 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (caller_info,
3487 src->index);
3488 if (src->offset == -1)
3489 return (plats->itself.is_single_const ()
3490 && values_equal_for_ipcp_p (src->val->value,
3491 plats->itself.values->value));
3492 else
3493 {
3494 if (plats->aggs_bottom || plats->aggs_contain_variable)
3495 return false;
3496 for (aglat = plats->aggs; aglat; aglat = aglat->next)
3497 if (aglat->offset == src->offset)
3498 return (aglat->is_single_const ()
3499 && values_equal_for_ipcp_p (src->val->value,
3500 aglat->values->value));
3501 }
3502 return false;
3503 }
3504}
3505
3506/* Return true if edge CS does bring about the value described by SRC to node
3507 DEST or its clone for all contexts. */
3508
3509static bool
3510cgraph_edge_brings_value_p (cgraph_edge *cs,
3511 ipcp_value_source<ipa_polymorphic_call_context> *src,
3512 cgraph_node *dest)
3513{
3514 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
3515 cgraph_node *real_dest = cs->callee->function_symbol ();
3516
3517 if (!same_node_or_its_all_contexts_clone_p (real_dest, dest)
3518 || caller_info->node_dead)
3519 return false;
3520 if (!src->val)
3521 return true;
3522
3523 if (caller_info->ipcp_orig_node)
3524 return (caller_info->known_contexts.length () > (unsigned) src->index)
3525 && values_equal_for_ipcp_p (src->val->value,
3526 caller_info->known_contexts[src->index]);
3527
3528 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (caller_info,
3529 src->index);
3530 return plats->ctxlat.is_single_const ()
3531 && values_equal_for_ipcp_p (src->val->value,
3532 plats->ctxlat.values->value);
3533}
3534
3535/* Get the next clone in the linked list of clones of an edge. */
3536
3537static inline struct cgraph_edge *
3538get_next_cgraph_edge_clone (struct cgraph_edge *cs)
3539{
3540 return next_edge_clone[cs->uid];
3541}
3542
3543/* Given VAL that is intended for DEST, iterate over all its sources and if
3544 they still hold, add their edge frequency and their number into *FREQUENCY
3545 and *CALLER_COUNT respectively. */
3546
3547template <typename valtype>
3548static bool
3549get_info_about_necessary_edges (ipcp_value<valtype> *val, cgraph_node *dest,
3550 int *freq_sum,
3551 profile_count *count_sum, int *caller_count)
3552{
3553 ipcp_value_source<valtype> *src;
3554 int freq = 0, count = 0;
3555 profile_count cnt = profile_count::zero ();
3556 bool hot = false;
3557
3558 for (src = val->sources; src; src = src->next)
3559 {
3560 struct cgraph_edge *cs = src->cs;
3561 while (cs)
3562 {
3563 if (cgraph_edge_brings_value_p (cs, src, dest))
3564 {
3565 count++;
3566 freq += cs->frequency ();
3567 if (cs->count.ipa ().initialized_p ())
3568 cnt += cs->count.ipa ();
3569 hot |= cs->maybe_hot_p ();
3570 }
3571 cs = get_next_cgraph_edge_clone (cs);
3572 }
3573 }
3574
3575 *freq_sum = freq;
3576 *count_sum = cnt;
3577 *caller_count = count;
3578 return hot;
3579}
3580
3581/* Return a vector of incoming edges that do bring value VAL to node DEST. It
3582 is assumed their number is known and equal to CALLER_COUNT. */
3583
3584template <typename valtype>
3585static vec<cgraph_edge *>
3586gather_edges_for_value (ipcp_value<valtype> *val, cgraph_node *dest,
3587 int caller_count)
3588{
3589 ipcp_value_source<valtype> *src;
3590 vec<cgraph_edge *> ret;
3591
3592 ret.create (caller_count);
3593 for (src = val->sources; src; src = src->next)
3594 {
3595 struct cgraph_edge *cs = src->cs;
3596 while (cs)
3597 {
3598 if (cgraph_edge_brings_value_p (cs, src, dest))
3599 ret.quick_push (cs);
3600 cs = get_next_cgraph_edge_clone (cs);
3601 }
3602 }
3603
3604 return ret;
3605}
3606
3607/* Construct a replacement map for a know VALUE for a formal parameter PARAM.
3608 Return it or NULL if for some reason it cannot be created. */
3609
3610static struct ipa_replace_map *
3611get_replacement_map (struct ipa_node_params *info, tree value, int parm_num)
3612{
3613 struct ipa_replace_map *replace_map;
3614
3615
3616 replace_map = ggc_alloc<ipa_replace_map> ();
3617 if (dump_file)
3618 {
3619 fprintf (dump_file, " replacing ");
3620 ipa_dump_param (dump_file, info, parm_num);
3621
3622 fprintf (dump_file, " with const ");
3623 print_generic_expr (dump_file, value);
3624 fprintf (dump_file, "\n");
3625 }
3626 replace_map->old_tree = NULL;
3627 replace_map->parm_num = parm_num;
3628 replace_map->new_tree = value;
3629 replace_map->replace_p = true;
3630 replace_map->ref_p = false;
3631
3632 return replace_map;
3633}
3634
3635/* Dump new profiling counts */
3636
3637static void
3638dump_profile_updates (struct cgraph_node *orig_node,
3639 struct cgraph_node *new_node)
3640{
3641 struct cgraph_edge *cs;
3642
3643 fprintf (dump_file, " setting count of the specialized node to ");
3644 new_node->count.dump (dump_file);
3645 fprintf (dump_file, "\n");
3646 for (cs = new_node->callees; cs; cs = cs->next_callee)
3647 {
3648 fprintf (dump_file, " edge to %s has count ",
3649 cs->callee->name ());
3650 cs->count.dump (dump_file);
3651 fprintf (dump_file, "\n");
3652 }
3653
3654 fprintf (dump_file, " setting count of the original node to ");
3655 orig_node->count.dump (dump_file);
3656 fprintf (dump_file, "\n");
3657 for (cs = orig_node->callees; cs; cs = cs->next_callee)
3658 {
3659 fprintf (dump_file, " edge to %s is left with ",
3660 cs->callee->name ());
3661 cs->count.dump (dump_file);
3662 fprintf (dump_file, "\n");
3663 }
3664}
3665
3666/* After a specialized NEW_NODE version of ORIG_NODE has been created, update
3667 their profile information to reflect this. */
3668
3669static void
3670update_profiling_info (struct cgraph_node *orig_node,
3671 struct cgraph_node *new_node)
3672{
3673 struct cgraph_edge *cs;
3674 struct caller_statistics stats;
3675 profile_count new_sum, orig_sum;
3676 profile_count remainder, orig_node_count = orig_node->count;
3677
3678 if (!(orig_node_count.ipa () > profile_count::zero ()))
3679 return;
3680
3681 init_caller_stats (&stats);
3682 orig_node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats,
3683 false);
3684 orig_sum = stats.count_sum;
3685 init_caller_stats (&stats);
3686 new_node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats,
3687 false);
3688 new_sum = stats.count_sum;
3689
3690 if (orig_node_count < orig_sum + new_sum)
3691 {
3692 if (dump_file)
3693 {
3694 fprintf (dump_file, " Problem: node %s has too low count ",
3695 orig_node->dump_name ());
3696 orig_node_count.dump (dump_file);
3697 fprintf (dump_file, "while the sum of incoming count is ");
3698 (orig_sum + new_sum).dump (dump_file);
3699 fprintf (dump_file, "\n");
3700 }
3701
3702 orig_node_count = (orig_sum + new_sum).apply_scale (12, 10);
3703 if (dump_file)
3704 {
3705 fprintf (dump_file, " proceeding by pretending it was ");
3706 orig_node_count.dump (dump_file);
3707 fprintf (dump_file, "\n");
3708 }
3709 }
3710
3711 remainder = orig_node_count.combine_with_ipa_count (orig_node_count.ipa ()
3712 - new_sum.ipa ());
3713 new_sum = orig_node_count.combine_with_ipa_count (new_sum);
3714 orig_node->count = remainder;
3715
3716 for (cs = new_node->callees; cs; cs = cs->next_callee)
3717 cs->count = cs->count.apply_scale (new_sum, orig_node_count);
3718
3719 for (cs = orig_node->callees; cs; cs = cs->next_callee)
3720 cs->count = cs->count.apply_scale (remainder, orig_node_count);
3721
3722 if (dump_file)
3723 dump_profile_updates (orig_node, new_node);
3724}
3725
3726/* Update the respective profile of specialized NEW_NODE and the original
3727 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
3728 have been redirected to the specialized version. */
3729
3730static void
3731update_specialized_profile (struct cgraph_node *new_node,
3732 struct cgraph_node *orig_node,
3733 profile_count redirected_sum)
3734{
3735 struct cgraph_edge *cs;
3736 profile_count new_node_count, orig_node_count = orig_node->count;
3737
3738 if (dump_file)
3739 {
3740 fprintf (dump_file, " the sum of counts of redirected edges is ");
3741 redirected_sum.dump (dump_file);
3742 fprintf (dump_file, "\n");
3743 }
3744 if (!(orig_node_count > profile_count::zero ()))
3745 return;
3746
3747 gcc_assert (orig_node_count >= redirected_sum);
3748
3749 new_node_count = new_node->count;
3750 new_node->count += redirected_sum;
3751 orig_node->count -= redirected_sum;
3752
3753 for (cs = new_node->callees; cs; cs = cs->next_callee)
3754 cs->count += cs->count.apply_scale (redirected_sum, new_node_count);
3755
3756 for (cs = orig_node->callees; cs; cs = cs->next_callee)
3757 {
3758 profile_count dec = cs->count.apply_scale (redirected_sum,
3759 orig_node_count);
3760 cs->count -= dec;
3761 }
3762
3763 if (dump_file)
3764 dump_profile_updates (orig_node, new_node);
3765}
3766
3767/* Create a specialized version of NODE with known constants in KNOWN_CSTS,
3768 known contexts in KNOWN_CONTEXTS and known aggregate values in AGGVALS and
3769 redirect all edges in CALLERS to it. */
3770
3771static struct cgraph_node *
3772create_specialized_node (struct cgraph_node *node,
3773 vec<tree> known_csts,
3774 vec<ipa_polymorphic_call_context> known_contexts,
3775 struct ipa_agg_replacement_value *aggvals,
3776 vec<cgraph_edge *> callers)
3777{
3778 struct ipa_node_params *new_info, *info = IPA_NODE_REF (node);
3779 vec<ipa_replace_map *, va_gc> *replace_trees = NULL;
3780 struct ipa_agg_replacement_value *av;
3781 struct cgraph_node *new_node;
3782 int i, count = ipa_get_param_count (info);
3783 bitmap args_to_skip;
3784
3785 gcc_assert (!info->ipcp_orig_node);
3786
3787 if (node->local.can_change_signature)
3788 {
3789 args_to_skip = BITMAP_GGC_ALLOC ();
3790 for (i = 0; i < count; i++)
3791 {
3792 tree t = known_csts[i];
3793
3794 if (t || !ipa_is_param_used (info, i))
3795 bitmap_set_bit (args_to_skip, i);
3796 }
3797 }
3798 else
3799 {
3800 args_to_skip = NULL;
3801 if (dump_file && (dump_flags & TDF_DETAILS))
3802 fprintf (dump_file, " cannot change function signature\n");
3803 }
3804
3805 for (i = 0; i < count; i++)
3806 {
3807 tree t = known_csts[i];
3808 if (t)
3809 {
3810 struct ipa_replace_map *replace_map;
3811
3812 gcc_checking_assert (TREE_CODE (t) != TREE_BINFO);
3813 replace_map = get_replacement_map (info, t, i);
3814 if (replace_map)
3815 vec_safe_push (replace_trees, replace_map);
3816 }
3817 }
3818
3819 new_node = node->create_virtual_clone (callers, replace_trees,
3820 args_to_skip, "constprop");
3821 ipa_set_node_agg_value_chain (new_node, aggvals);
3822 for (av = aggvals; av; av = av->next)
3823 new_node->maybe_create_reference (av->value, NULL);
3824
3825 if (dump_file && (dump_flags & TDF_DETAILS))
3826 {
3827 fprintf (dump_file, " the new node is %s.\n", new_node->dump_name ());
3828 if (known_contexts.exists ())
3829 {
3830 for (i = 0; i < count; i++)
3831 if (!known_contexts[i].useless_p ())
3832 {
3833 fprintf (dump_file, " known ctx %i is ", i);
3834 known_contexts[i].dump (dump_file);
3835 }
3836 }
3837 if (aggvals)
3838 ipa_dump_agg_replacement_values (dump_file, aggvals);
3839 }
3840 ipa_check_create_node_params ();
3841 update_profiling_info (node, new_node);
3842 new_info = IPA_NODE_REF (new_node);
3843 new_info->ipcp_orig_node = node;
3844 new_info->known_csts = known_csts;
3845 new_info->known_contexts = known_contexts;
3846
3847 ipcp_discover_new_direct_edges (new_node, known_csts, known_contexts, aggvals);
3848
3849 callers.release ();
3850 return new_node;
3851}
3852
3853/* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
3854 KNOWN_CSTS with constants that are also known for all of the CALLERS. */
3855
3856static void
3857find_more_scalar_values_for_callers_subset (struct cgraph_node *node,
3858 vec<tree> known_csts,
3859 vec<cgraph_edge *> callers)
3860{
3861 struct ipa_node_params *info = IPA_NODE_REF (node);
3862 int i, count = ipa_get_param_count (info);
3863
3864 for (i = 0; i < count; i++)
3865 {
3866 struct cgraph_edge *cs;
3867 tree newval = NULL_TREE;
3868 int j;
3869 bool first = true;
3870 tree type = ipa_get_type (info, i);
3871
3872 if (ipa_get_scalar_lat (info, i)->bottom || known_csts[i])
3873 continue;
3874
3875 FOR_EACH_VEC_ELT (callers, j, cs)
3876 {
3877 struct ipa_jump_func *jump_func;
3878 tree t;
3879
3880 if (i >= ipa_get_cs_argument_count (IPA_EDGE_REF (cs))
3881 || (i == 0
3882 && call_passes_through_thunk_p (cs))
3883 || (!cs->callee->instrumentation_clone
3884 && cs->callee->function_symbol ()->instrumentation_clone))
3885 {
3886 newval = NULL_TREE;
3887 break;
3888 }
3889 jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
3890 t = ipa_value_from_jfunc (IPA_NODE_REF (cs->caller), jump_func, type);
3891 if (!t
3892 || (newval
3893 && !values_equal_for_ipcp_p (t, newval))
3894 || (!first && !newval))
3895 {
3896 newval = NULL_TREE;
3897 break;
3898 }
3899 else
3900 newval = t;
3901 first = false;
3902 }
3903
3904 if (newval)
3905 {
3906 if (dump_file && (dump_flags & TDF_DETAILS))
3907 {
3908 fprintf (dump_file, " adding an extra known scalar value ");
3909 print_ipcp_constant_value (dump_file, newval);
3910 fprintf (dump_file, " for ");
3911 ipa_dump_param (dump_file, info, i);
3912 fprintf (dump_file, "\n");
3913 }
3914
3915 known_csts[i] = newval;
3916 }
3917 }
3918}
3919
3920/* Given a NODE and a subset of its CALLERS, try to populate plank slots in
3921 KNOWN_CONTEXTS with polymorphic contexts that are also known for all of the
3922 CALLERS. */
3923
3924static void
3925find_more_contexts_for_caller_subset (cgraph_node *node,
3926 vec<ipa_polymorphic_call_context>
3927 *known_contexts,
3928 vec<cgraph_edge *> callers)
3929{
3930 ipa_node_params *info = IPA_NODE_REF (node);
3931 int i, count = ipa_get_param_count (info);
3932
3933 for (i = 0; i < count; i++)
3934 {
3935 cgraph_edge *cs;
3936
3937 if (ipa_get_poly_ctx_lat (info, i)->bottom
3938 || (known_contexts->exists ()
3939 && !(*known_contexts)[i].useless_p ()))
3940 continue;
3941
3942 ipa_polymorphic_call_context newval;
3943 bool first = true;
3944 int j;
3945
3946 FOR_EACH_VEC_ELT (callers, j, cs)
3947 {
3948 if (i >= ipa_get_cs_argument_count (IPA_EDGE_REF (cs)))
3949 return;
3950 ipa_jump_func *jfunc = ipa_get_ith_jump_func (IPA_EDGE_REF (cs),
3951 i);
3952 ipa_polymorphic_call_context ctx;
3953 ctx = ipa_context_from_jfunc (IPA_NODE_REF (cs->caller), cs, i,
3954 jfunc);
3955 if (first)
3956 {
3957 newval = ctx;
3958 first = false;
3959 }
3960 else
3961 newval.meet_with (ctx);
3962 if (newval.useless_p ())
3963 break;
3964 }
3965
3966 if (!newval.useless_p ())
3967 {
3968 if (dump_file && (dump_flags & TDF_DETAILS))
3969 {
3970 fprintf (dump_file, " adding an extra known polymorphic "
3971 "context ");
3972 print_ipcp_constant_value (dump_file, newval);
3973 fprintf (dump_file, " for ");
3974 ipa_dump_param (dump_file, info, i);
3975 fprintf (dump_file, "\n");
3976 }
3977
3978 if (!known_contexts->exists ())
3979 known_contexts->safe_grow_cleared (ipa_get_param_count (info));
3980 (*known_contexts)[i] = newval;
3981 }
3982
3983 }
3984}
3985
3986/* Go through PLATS and create a vector of values consisting of values and
3987 offsets (minus OFFSET) of lattices that contain only a single value. */
3988
3989static vec<ipa_agg_jf_item>
3990copy_plats_to_inter (struct ipcp_param_lattices *plats, HOST_WIDE_INT offset)
3991{
3992 vec<ipa_agg_jf_item> res = vNULL;
3993
3994 if (!plats->aggs || plats->aggs_contain_variable || plats->aggs_bottom)
3995 return vNULL;
3996
3997 for (struct ipcp_agg_lattice *aglat = plats->aggs; aglat; aglat = aglat->next)
3998 if (aglat->is_single_const ())
3999 {
4000 struct ipa_agg_jf_item ti;
4001 ti.offset = aglat->offset - offset;
4002 ti.value = aglat->values->value;
4003 res.safe_push (ti);
4004 }
4005 return res;
4006}
4007
4008/* Intersect all values in INTER with single value lattices in PLATS (while
4009 subtracting OFFSET). */
4010
4011static void
4012intersect_with_plats (struct ipcp_param_lattices *plats,
4013 vec<ipa_agg_jf_item> *inter,
4014 HOST_WIDE_INT offset)
4015{
4016 struct ipcp_agg_lattice *aglat;
4017 struct ipa_agg_jf_item *item;
4018 int k;
4019
4020 if (!plats->aggs || plats->aggs_contain_variable || plats->aggs_bottom)
4021 {
4022 inter->release ();
4023 return;
4024 }
4025
4026 aglat = plats->aggs;
4027 FOR_EACH_VEC_ELT (*inter, k, item)
4028 {
4029 bool found = false;
4030 if (!item->value)
4031 continue;
4032 while (aglat)
4033 {
4034 if (aglat->offset - offset > item->offset)
4035 break;
4036 if (aglat->offset - offset == item->offset)
4037 {
4038 gcc_checking_assert (item->value);
4039 if (values_equal_for_ipcp_p (item->value, aglat->values->value))
4040 found = true;
4041 break;
4042 }
4043 aglat = aglat->next;
4044 }
4045 if (!found)
4046 item->value = NULL_TREE;
4047 }
4048}
4049
4050/* Copy aggregate replacement values of NODE (which is an IPA-CP clone) to the
4051 vector result while subtracting OFFSET from the individual value offsets. */
4052
4053static vec<ipa_agg_jf_item>
4054agg_replacements_to_vector (struct cgraph_node *node, int index,
4055 HOST_WIDE_INT offset)
4056{
4057 struct ipa_agg_replacement_value *av;
4058 vec<ipa_agg_jf_item> res = vNULL;
4059
4060 for (av = ipa_get_agg_replacements_for_node (node); av; av = av->next)
4061 if (av->index == index
4062 && (av->offset - offset) >= 0)
4063 {
4064 struct ipa_agg_jf_item item;
4065 gcc_checking_assert (av->value);
4066 item.offset = av->offset - offset;
4067 item.value = av->value;
4068 res.