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