Merge branch 'vendor/GCC47'
[dragonfly.git] / contrib / gcc-4.7 / gcc / ipa-cp.c
1 /* Interprocedural constant propagation
2    Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
3    Free Software Foundation, Inc.
4
5    Contributed by Razya Ladelsky <RAZYA@il.ibm.com> and Martin Jambor
6    <mjambor@suse.cz>
7
8 This file is part of GCC.
9
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
13 version.
14
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
18 for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3.  If not see
22 <http://www.gnu.org/licenses/>.  */
23
24 /* Interprocedural constant propagation (IPA-CP).
25
26    The goal of this transformation is to
27
28    1) discover functions which are always invoked with some arguments with the
29       same known constant values and modify the functions so that the
30       subsequent optimizations can take advantage of the knowledge, and
31
32    2) partial specialization - create specialized versions of functions
33       transformed in this way if some parameters are known constants only in
34       certain contexts but the estimated tradeoff between speedup and cost size
35       is deemed good.
36
37    The algorithm also propagates types and attempts to perform type based
38    devirtualization.  Types are propagated much like constants.
39
40    The algorithm basically consists of three stages.  In the first, functions
41    are analyzed one at a time and jump functions are constructed for all known
42    call-sites.  In the second phase, the pass propagates information from the
43    jump functions across the call to reveal what values are available at what
44    call sites, performs estimations of effects of known values on functions and
45    their callees, and finally decides what specialized extra versions should be
46    created.  In the third, the special versions materialize and appropriate
47    calls are redirected.
48
49    The algorithm used is to a certain extent based on "Interprocedural Constant
50    Propagation", by David Callahan, Keith D Cooper, Ken Kennedy, Linda Torczon,
51    Comp86, pg 152-161 and "A Methodology for Procedure Cloning" by Keith D
52    Cooper, Mary W. Hall, and Ken Kennedy.
53
54
55    First stage - intraprocedural analysis
56    =======================================
57
58    This phase computes jump_function and modification flags.
59
60    A jump function for a call-site represents the values passed as an actual
61    arguments of a given call-site. In principle, there are three types of
62    values:
63
64    Pass through - the caller's formal parameter is passed as an actual
65                   argument, plus an operation on it can be performed.
66    Constant - a constant is passed as an actual argument.
67    Unknown - neither of the above.
68
69    All jump function types are described in detail in ipa-prop.h, together with
70    the data structures that represent them and methods of accessing them.
71
72    ipcp_generate_summary() is the main function of the first stage.
73
74    Second stage - interprocedural analysis
75    ========================================
76
77    This stage is itself divided into two phases.  In the first, we propagate
78    known values over the call graph, in the second, we make cloning decisions.
79    It uses a different algorithm than the original Callahan's paper.
80
81    First, we traverse the functions topologically from callers to callees and,
82    for each strongly connected component (SCC), we propagate constants
83    according to previously computed jump functions.  We also record what known
84    values depend on other known values and estimate local effects.  Finally, we
85    propagate cumulative information about these effects from dependant values
86    to those on which they depend.
87
88    Second, we again traverse the call graph in the same topological order and
89    make clones for functions which we know are called with the same values in
90    all contexts and decide about extra specialized clones of functions just for
91    some contexts - these decisions are based on both local estimates and
92    cumulative estimates propagated from callees.
93
94    ipcp_propagate_stage() and ipcp_decision_stage() together constitute the
95    third stage.
96
97    Third phase - materialization of clones, call statement updates.
98    ============================================
99
100    This stage is currently performed by call graph code (mainly in cgraphunit.c
101    and tree-inline.c) according to instructions inserted to the call graph by
102    the second stage.  */
103
104 #include "config.h"
105 #include "system.h"
106 #include "coretypes.h"
107 #include "tree.h"
108 #include "target.h"
109 #include "gimple.h"
110 #include "cgraph.h"
111 #include "ipa-prop.h"
112 #include "tree-flow.h"
113 #include "tree-pass.h"
114 #include "flags.h"
115 #include "timevar.h"
116 #include "diagnostic.h"
117 #include "tree-pretty-print.h"
118 #include "tree-dump.h"
119 #include "tree-inline.h"
120 #include "fibheap.h"
121 #include "params.h"
122 #include "ipa-inline.h"
123 #include "ipa-utils.h"
124
125 struct ipcp_value;
126
127 /* Describes a particular source for an IPA-CP value.  */
128
129 struct ipcp_value_source
130 {
131   /* The incoming edge that brought the value.  */
132   struct cgraph_edge *cs;
133   /* If the jump function that resulted into his value was a pass-through or an
134      ancestor, this is the ipcp_value of the caller from which the described
135      value has been derived.  Otherwise it is NULL.  */
136   struct ipcp_value *val;
137   /* Next pointer in a linked list of sources of a value.  */
138   struct ipcp_value_source *next;
139   /* If the jump function that resulted into his value was a pass-through or an
140      ancestor, this is the index of the parameter of the caller the jump
141      function references.  */
142   int index;
143 };
144
145 /* Describes one particular value stored in struct ipcp_lattice.  */
146
147 struct ipcp_value
148 {
149   /* The actual value for the given parameter.  This is either an IPA invariant
150      or a TREE_BINFO describing a type that can be used for
151      devirtualization.  */
152   tree value;
153   /* The list of sources from which this value originates.  */
154   struct ipcp_value_source *sources;
155   /* Next pointers in a linked list of all values in a lattice.  */
156   struct ipcp_value *next;
157   /* Next pointers in a linked list of values in a strongly connected component
158      of values. */
159   struct ipcp_value *scc_next;
160   /* Next pointers in a linked list of SCCs of values sorted topologically
161      according their sources.  */
162   struct ipcp_value  *topo_next;
163   /* A specialized node created for this value, NULL if none has been (so far)
164      created.  */
165   struct cgraph_node *spec_node;
166   /* Depth first search number and low link for topological sorting of
167      values.  */
168   int dfs, low_link;
169   /* Time benefit and size cost that specializing the function for this value
170      would bring about in this function alone.  */
171   int local_time_benefit, local_size_cost;
172   /* Time benefit and size cost that specializing the function for this value
173      can bring about in it's callees (transitively).  */
174   int prop_time_benefit, prop_size_cost;
175   /* True if this valye is currently on the topo-sort stack.  */
176   bool on_stack;
177 };
178
179 /* Allocation pools for values and their sources in ipa-cp.  */
180
181 alloc_pool ipcp_values_pool;
182 alloc_pool ipcp_sources_pool;
183
184 /* Lattice describing potential values of a formal parameter of a function and
185    some of their other properties.  TOP is represented by a lattice with zero
186    values and with contains_variable and bottom flags cleared.  BOTTOM is
187    represented by a lattice with the bottom flag set.  In that case, values and
188    contains_variable flag should be disregarded.  */
189
190 struct ipcp_lattice
191 {
192   /* The list of known values and types in this lattice.  Note that values are
193      not deallocated if a lattice is set to bottom because there may be value
194      sources referencing them.  */
195   struct ipcp_value *values;
196   /* Number of known values and types in this lattice.  */
197   int values_count;
198   /* The lattice contains a variable component  (in addition to values).  */
199   bool contains_variable;
200   /* The value of the lattice is bottom (i.e. variable and unusable for any
201      propagation).  */
202   bool bottom;
203   /* There is a virtual call based on this parameter.  */
204   bool virt_call;
205 };
206
207 /* Maximal count found in program.  */
208
209 static gcov_type max_count;
210
211 /* Original overall size of the program.  */
212
213 static long overall_size, max_new_size;
214
215 /* Head of the linked list of topologically sorted values. */
216
217 static struct ipcp_value *values_topo;
218
219 /* Return the lattice corresponding to the Ith formal parameter of the function
220    described by INFO.  */
221 static inline struct ipcp_lattice *
222 ipa_get_lattice (struct ipa_node_params *info, int i)
223 {
224   gcc_assert (i >= 0 && i < ipa_get_param_count (info));
225   gcc_checking_assert (!info->ipcp_orig_node);
226   gcc_checking_assert (info->lattices);
227   return &(info->lattices[i]);
228 }
229
230 /* Return whether LAT is a lattice with a single constant and without an
231    undefined value.  */
232
233 static inline bool
234 ipa_lat_is_single_const (struct ipcp_lattice *lat)
235 {
236   if (lat->bottom
237       || lat->contains_variable
238       || lat->values_count != 1)
239     return false;
240   else
241     return true;
242 }
243
244 /* Return true iff the CS is an edge within a strongly connected component as
245    computed by ipa_reduced_postorder.  */
246
247 static inline bool
248 edge_within_scc (struct cgraph_edge *cs)
249 {
250   struct ipa_dfs_info *caller_dfs = (struct ipa_dfs_info *) cs->caller->aux;
251   struct ipa_dfs_info *callee_dfs;
252   struct cgraph_node *callee = cgraph_function_node (cs->callee, NULL);
253
254   callee_dfs = (struct ipa_dfs_info *) callee->aux;
255   return (caller_dfs
256           && callee_dfs
257           && caller_dfs->scc_no == callee_dfs->scc_no);
258 }
259
260 /* Print V which is extracted from a value in a lattice to F.  */
261
262 static void
263 print_ipcp_constant_value (FILE * f, tree v)
264 {
265   if (TREE_CODE (v) == TREE_BINFO)
266     {
267       fprintf (f, "BINFO ");
268       print_generic_expr (f, BINFO_TYPE (v), 0);
269     }
270   else if (TREE_CODE (v) == ADDR_EXPR
271            && TREE_CODE (TREE_OPERAND (v, 0)) == CONST_DECL)
272     {
273       fprintf (f, "& ");
274       print_generic_expr (f, DECL_INITIAL (TREE_OPERAND (v, 0)), 0);
275     }
276   else
277     print_generic_expr (f, v, 0);
278 }
279
280 /* Print all ipcp_lattices of all functions to F.  */
281
282 static void
283 print_all_lattices (FILE * f, bool dump_sources, bool dump_benefits)
284 {
285   struct cgraph_node *node;
286   int i, count;
287
288   fprintf (f, "\nLattices:\n");
289   FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
290     {
291       struct ipa_node_params *info;
292
293       info = IPA_NODE_REF (node);
294       fprintf (f, "  Node: %s/%i:\n", cgraph_node_name (node), node->uid);
295       count = ipa_get_param_count (info);
296       for (i = 0; i < count; i++)
297         {
298           struct ipcp_lattice *lat = ipa_get_lattice (info, i);
299           struct ipcp_value *val;
300           bool prev = false;
301
302           fprintf (f, "    param [%d]: ", i);
303           if (lat->bottom)
304             {
305               fprintf (f, "BOTTOM\n");
306               continue;
307             }
308
309           if (!lat->values_count && !lat->contains_variable)
310             {
311               fprintf (f, "TOP\n");
312               continue;
313             }
314
315           if (lat->contains_variable)
316             {
317               fprintf (f, "VARIABLE");
318               prev = true;
319               if (dump_benefits)
320                 fprintf (f, "\n");
321             }
322
323           for (val = lat->values; val; val = val->next)
324             {
325               if (dump_benefits && prev)
326                 fprintf (f, "               ");
327               else if (!dump_benefits && prev)
328                 fprintf (f, ", ");
329               else
330                 prev = true;
331
332               print_ipcp_constant_value (f, val->value);
333
334               if (dump_sources)
335                 {
336                   struct ipcp_value_source *s;
337
338                   fprintf (f, " [from:");
339                   for (s = val->sources; s; s = s->next)
340                     fprintf (f, " %i(%i)", s->cs->caller->uid,s->cs->frequency);
341                   fprintf (f, "]");
342                 }
343
344               if (dump_benefits)
345                 fprintf (f, " [loc_time: %i, loc_size: %i, "
346                          "prop_time: %i, prop_size: %i]\n",
347                          val->local_time_benefit, val->local_size_cost,
348                          val->prop_time_benefit, val->prop_size_cost);
349             }
350           if (!dump_benefits)
351             fprintf (f, "\n");
352         }
353     }
354 }
355
356 /* Determine whether it is at all technically possible to create clones of NODE
357    and store this information in the ipa_node_params structure associated
358    with NODE.  */
359
360 static void
361 determine_versionability (struct cgraph_node *node)
362 {
363   const char *reason = NULL;
364
365   /* There are a number of generic reasons functions cannot be versioned.  We
366      also cannot remove parameters if there are type attributes such as fnspec
367      present.  */
368   if (node->alias || node->thunk.thunk_p)
369     reason = "alias or thunk";
370   else if (!node->local.versionable)
371     reason = "not a tree_versionable_function";
372   else if (cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE)
373     reason = "insufficient body availability";
374
375   if (reason && dump_file && !node->alias && !node->thunk.thunk_p)
376     fprintf (dump_file, "Function %s/%i is not versionable, reason: %s.\n",
377              cgraph_node_name (node), node->uid, reason);
378
379   node->local.versionable = (reason == NULL);
380 }
381
382 /* Return true if it is at all technically possible to create clones of a
383    NODE.  */
384
385 static bool
386 ipcp_versionable_function_p (struct cgraph_node *node)
387 {
388   return node->local.versionable;
389 }
390
391 /* Structure holding accumulated information about callers of a node.  */
392
393 struct caller_statistics
394 {
395   gcov_type count_sum;
396   int n_calls, n_hot_calls, freq_sum;
397 };
398
399 /* Initialize fields of STAT to zeroes.  */
400
401 static inline void
402 init_caller_stats (struct caller_statistics *stats)
403 {
404   stats->count_sum = 0;
405   stats->n_calls = 0;
406   stats->n_hot_calls = 0;
407   stats->freq_sum = 0;
408 }
409
410 /* Worker callback of cgraph_for_node_and_aliases accumulating statistics of
411    non-thunk incoming edges to NODE.  */
412
413 static bool
414 gather_caller_stats (struct cgraph_node *node, void *data)
415 {
416   struct caller_statistics *stats = (struct caller_statistics *) data;
417   struct cgraph_edge *cs;
418
419   for (cs = node->callers; cs; cs = cs->next_caller)
420     if (cs->caller->thunk.thunk_p)
421       cgraph_for_node_and_aliases (cs->caller, gather_caller_stats,
422                                    stats, false);
423     else
424       {
425         stats->count_sum += cs->count;
426         stats->freq_sum += cs->frequency;
427         stats->n_calls++;
428         if (cgraph_maybe_hot_edge_p (cs))
429           stats->n_hot_calls ++;
430       }
431   return false;
432
433 }
434
435 /* Return true if this NODE is viable candidate for cloning.  */
436
437 static bool
438 ipcp_cloning_candidate_p (struct cgraph_node *node)
439 {
440   struct caller_statistics stats;
441
442   gcc_checking_assert (cgraph_function_with_gimple_body_p (node));
443
444   if (!flag_ipa_cp_clone)
445     {
446       if (dump_file)
447         fprintf (dump_file, "Not considering %s for cloning; "
448                  "-fipa-cp-clone disabled.\n",
449                  cgraph_node_name (node));
450       return false;
451     }
452
453   if (!optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node->decl)))
454     {
455       if (dump_file)
456         fprintf (dump_file, "Not considering %s for cloning; "
457                  "optimizing it for size.\n",
458                  cgraph_node_name (node));
459       return false;
460     }
461
462   init_caller_stats (&stats);
463   cgraph_for_node_and_aliases (node, gather_caller_stats, &stats, false);
464
465   if (inline_summary (node)->self_size < stats.n_calls)
466     {
467       if (dump_file)
468         fprintf (dump_file, "Considering %s for cloning; code might shrink.\n",
469                  cgraph_node_name (node));
470       return true;
471     }
472
473   /* When profile is available and function is hot, propagate into it even if
474      calls seems cold; constant propagation can improve function's speed
475      significantly.  */
476   if (max_count)
477     {
478       if (stats.count_sum > node->count * 90 / 100)
479         {
480           if (dump_file)
481             fprintf (dump_file, "Considering %s for cloning; "
482                      "usually called directly.\n",
483                      cgraph_node_name (node));
484           return true;
485         }
486     }
487   if (!stats.n_hot_calls)
488     {
489       if (dump_file)
490         fprintf (dump_file, "Not considering %s for cloning; no hot calls.\n",
491                  cgraph_node_name (node));
492       return false;
493     }
494   if (dump_file)
495     fprintf (dump_file, "Considering %s for cloning.\n",
496              cgraph_node_name (node));
497   return true;
498 }
499
500 /* Arrays representing a topological ordering of call graph nodes and a stack
501    of noes used during constant propagation.  */
502
503 struct topo_info
504 {
505   struct cgraph_node **order;
506   struct cgraph_node **stack;
507   int nnodes, stack_top;
508 };
509
510 /* Allocate the arrays in TOPO and topologically sort the nodes into order.  */
511
512 static void
513 build_toporder_info (struct topo_info *topo)
514 {
515   topo->order = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
516   topo->stack = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
517   topo->stack_top = 0;
518   topo->nnodes = ipa_reduced_postorder (topo->order, true, true, NULL);
519 }
520
521 /* Free information about strongly connected components and the arrays in
522    TOPO.  */
523
524 static void
525 free_toporder_info (struct topo_info *topo)
526 {
527   ipa_free_postorder_info ();
528   free (topo->order);
529   free (topo->stack);
530 }
531
532 /* Add NODE to the stack in TOPO, unless it is already there.  */
533
534 static inline void
535 push_node_to_stack (struct topo_info *topo, struct cgraph_node *node)
536 {
537   struct ipa_node_params *info = IPA_NODE_REF (node);
538   if (info->node_enqueued)
539     return;
540   info->node_enqueued = 1;
541   topo->stack[topo->stack_top++] = node;
542 }
543
544 /* Pop a node from the stack in TOPO and return it or return NULL if the stack
545    is empty.  */
546
547 static struct cgraph_node *
548 pop_node_from_stack (struct topo_info *topo)
549 {
550   if (topo->stack_top)
551     {
552       struct cgraph_node *node;
553       topo->stack_top--;
554       node = topo->stack[topo->stack_top];
555       IPA_NODE_REF (node)->node_enqueued = 0;
556       return node;
557     }
558   else
559     return NULL;
560 }
561
562 /* Set lattice LAT to bottom and return true if it previously was not set as
563    such.  */
564
565 static inline bool
566 set_lattice_to_bottom (struct ipcp_lattice *lat)
567 {
568   bool ret = !lat->bottom;
569   lat->bottom = true;
570   return ret;
571 }
572
573 /* Mark lattice as containing an unknown value and return true if it previously
574    was not marked as such.  */
575
576 static inline bool
577 set_lattice_contains_variable (struct ipcp_lattice *lat)
578 {
579   bool ret = !lat->contains_variable;
580   lat->contains_variable = true;
581   return ret;
582 }
583
584 /* Initialize ipcp_lattices.  */
585
586 static void
587 initialize_node_lattices (struct cgraph_node *node)
588 {
589   struct ipa_node_params *info = IPA_NODE_REF (node);
590   struct cgraph_edge *ie;
591   bool disable = false, variable = false;
592   int i;
593
594   gcc_checking_assert (cgraph_function_with_gimple_body_p (node));
595   if (!node->local.local)
596     {
597       /* When cloning is allowed, we can assume that externally visible
598          functions are not called.  We will compensate this by cloning
599          later.  */
600       if (ipcp_versionable_function_p (node)
601           && ipcp_cloning_candidate_p (node))
602         variable = true;
603       else
604         disable = true;
605     }
606
607   if (disable || variable)
608     {
609       for (i = 0; i < ipa_get_param_count (info) ; i++)
610         {
611           struct ipcp_lattice *lat = ipa_get_lattice (info, i);
612           if (disable)
613             set_lattice_to_bottom (lat);
614           else
615             set_lattice_contains_variable (lat);
616         }
617       if (dump_file && (dump_flags & TDF_DETAILS)
618           && node->alias && node->thunk.thunk_p)
619         fprintf (dump_file, "Marking all lattices of %s/%i as %s\n",
620                  cgraph_node_name (node), node->uid,
621                  disable ? "BOTTOM" : "VARIABLE");
622     }
623
624   for (ie = node->indirect_calls; ie; ie = ie->next_callee)
625     if (ie->indirect_info->polymorphic)
626       {
627         gcc_checking_assert (ie->indirect_info->param_index >= 0);
628         ipa_get_lattice (info, ie->indirect_info->param_index)->virt_call = 1;
629       }
630 }
631
632 /* Return the result of a (possibly arithmetic) pass through jump function
633    JFUNC on the constant value INPUT.  Return NULL_TREE if that cannot be
634    determined or itself is considered an interprocedural invariant.  */
635
636 static tree
637 ipa_get_jf_pass_through_result (struct ipa_jump_func *jfunc, tree input)
638 {
639   tree restype, res;
640
641   gcc_checking_assert (is_gimple_ip_invariant (input));
642   if (jfunc->value.pass_through.operation == NOP_EXPR)
643     return input;
644
645   if (TREE_CODE_CLASS (jfunc->value.pass_through.operation)
646       == tcc_comparison)
647     restype = boolean_type_node;
648   else
649     restype = TREE_TYPE (input);
650   res = fold_binary (jfunc->value.pass_through.operation, restype,
651                      input, jfunc->value.pass_through.operand);
652
653   if (res && !is_gimple_ip_invariant (res))
654     return NULL_TREE;
655
656   return res;
657 }
658
659 /* Return the result of an ancestor jump function JFUNC on the constant value
660    INPUT.  Return NULL_TREE if that cannot be determined.  */
661
662 static tree
663 ipa_get_jf_ancestor_result (struct ipa_jump_func *jfunc, tree input)
664 {
665   if (TREE_CODE (input) == ADDR_EXPR)
666     {
667       tree t = TREE_OPERAND (input, 0);
668       t = build_ref_for_offset (EXPR_LOCATION (t), t,
669                                 jfunc->value.ancestor.offset,
670                                 jfunc->value.ancestor.type, NULL, false);
671       return build_fold_addr_expr (t);
672     }
673   else
674     return NULL_TREE;
675 }
676
677 /* Extract the acual BINFO being described by JFUNC which must be a known type
678    jump function.  */
679
680 static tree
681 ipa_value_from_known_type_jfunc (struct ipa_jump_func *jfunc)
682 {
683   tree base_binfo = TYPE_BINFO (jfunc->value.known_type.base_type);
684   if (!base_binfo)
685     return NULL_TREE;
686   return get_binfo_at_offset (base_binfo,
687                               jfunc->value.known_type.offset,
688                               jfunc->value.known_type.component_type);
689 }
690
691 /* Determine whether JFUNC evaluates to a known value (that is either a
692    constant or a binfo) and if so, return it.  Otherwise return NULL. INFO
693    describes the caller node so that pass-through jump functions can be
694    evaluated.  */
695
696 tree
697 ipa_value_from_jfunc (struct ipa_node_params *info, struct ipa_jump_func *jfunc)
698 {
699   if (jfunc->type == IPA_JF_CONST)
700     return jfunc->value.constant;
701   else if (jfunc->type == IPA_JF_KNOWN_TYPE)
702     return ipa_value_from_known_type_jfunc (jfunc);
703   else if (jfunc->type == IPA_JF_PASS_THROUGH
704            || jfunc->type == IPA_JF_ANCESTOR)
705     {
706       tree input;
707       int idx;
708
709       if (jfunc->type == IPA_JF_PASS_THROUGH)
710         idx = jfunc->value.pass_through.formal_id;
711       else
712         idx = jfunc->value.ancestor.formal_id;
713
714       if (info->ipcp_orig_node)
715         input = VEC_index (tree, info->known_vals, idx);
716       else
717         {
718           struct ipcp_lattice *lat;
719
720           if (!info->lattices)
721             {
722               gcc_checking_assert (!flag_ipa_cp);
723               return NULL_TREE;
724             }
725           lat = ipa_get_lattice (info, idx);
726           if (!ipa_lat_is_single_const (lat))
727             return NULL_TREE;
728           input = lat->values->value;
729         }
730
731       if (!input)
732         return NULL_TREE;
733
734       if (jfunc->type == IPA_JF_PASS_THROUGH)
735         {
736           if (jfunc->value.pass_through.operation == NOP_EXPR)
737             return input;
738           else if (TREE_CODE (input) == TREE_BINFO)
739             return NULL_TREE;
740           else
741             return ipa_get_jf_pass_through_result (jfunc, input);
742         }
743       else
744         {
745           if (TREE_CODE (input) == TREE_BINFO)
746             return get_binfo_at_offset (input, jfunc->value.ancestor.offset,
747                                         jfunc->value.ancestor.type);
748           else
749             return ipa_get_jf_ancestor_result (jfunc, input);
750         }
751     }
752   else
753     return NULL_TREE;
754 }
755
756
757 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
758    bottom, not containing a variable component and without any known value at
759    the same time.  */
760
761 DEBUG_FUNCTION void
762 ipcp_verify_propagated_values (void)
763 {
764   struct cgraph_node *node;
765
766   FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
767     {
768       struct ipa_node_params *info = IPA_NODE_REF (node);
769       int i, count = ipa_get_param_count (info);
770
771       for (i = 0; i < count; i++)
772         {
773           struct ipcp_lattice *lat = ipa_get_lattice (info, i);
774
775           if (!lat->bottom
776               && !lat->contains_variable
777               && lat->values_count == 0)
778             {
779               if (dump_file)
780                 {
781                   fprintf (dump_file, "\nIPA lattices after constant "
782                            "propagation:\n");
783                   print_all_lattices (dump_file, true, false);
784                 }
785
786               gcc_unreachable ();
787             }
788         }
789     }
790 }
791
792 /* Return true iff X and Y should be considered equal values by IPA-CP.  */
793
794 static bool
795 values_equal_for_ipcp_p (tree x, tree y)
796 {
797   gcc_checking_assert (x != NULL_TREE && y != NULL_TREE);
798
799   if (x == y)
800     return true;
801
802   if (TREE_CODE (x) == TREE_BINFO || TREE_CODE (y) == TREE_BINFO)
803     return false;
804
805   if (TREE_CODE (x) ==  ADDR_EXPR
806       && TREE_CODE (y) ==  ADDR_EXPR
807       && TREE_CODE (TREE_OPERAND (x, 0)) == CONST_DECL
808       && TREE_CODE (TREE_OPERAND (y, 0)) == CONST_DECL)
809     return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x, 0)),
810                             DECL_INITIAL (TREE_OPERAND (y, 0)), 0);
811   else
812     return operand_equal_p (x, y, 0);
813 }
814
815 /* Add a new value source to VAL, marking that a value comes from edge CS and
816    (if the underlying jump function is a pass-through or an ancestor one) from
817    a caller value SRC_VAL of a caller parameter described by SRC_INDEX.  */
818
819 static void
820 add_value_source (struct ipcp_value *val, struct cgraph_edge *cs,
821                   struct ipcp_value *src_val, int src_idx)
822 {
823   struct ipcp_value_source *src;
824
825   src = (struct ipcp_value_source *) pool_alloc (ipcp_sources_pool);
826   src->cs = cs;
827   src->val = src_val;
828   src->index = src_idx;
829
830   src->next = val->sources;
831   val->sources = src;
832 }
833
834
835 /* Try to add NEWVAL to LAT, potentially creating a new struct ipcp_value for
836    it.  CS, SRC_VAL and SRC_INDEX are meant for add_value_source and have the
837    same meaning.  */
838
839 static bool
840 add_value_to_lattice (struct ipcp_lattice *lat, tree newval,
841                       struct cgraph_edge *cs, struct ipcp_value *src_val,
842                       int src_idx)
843 {
844   struct ipcp_value *val;
845
846   if (lat->bottom)
847     return false;
848
849
850   for (val = lat->values; val; val = val->next)
851     if (values_equal_for_ipcp_p (val->value, newval))
852       {
853         if (edge_within_scc (cs))
854           {
855             struct ipcp_value_source *s;
856             for (s = val->sources; s ; s = s->next)
857               if (s->cs == cs)
858                 break;
859             if (s)
860               return false;
861           }
862
863         add_value_source (val, cs, src_val, src_idx);
864         return false;
865       }
866
867   if (lat->values_count == PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE))
868     {
869       /* We can only free sources, not the values themselves, because sources
870          of other values in this this SCC might point to them.   */
871       for (val = lat->values; val; val = val->next)
872         {
873           while (val->sources)
874             {
875               struct ipcp_value_source *src = val->sources;
876               val->sources = src->next;
877               pool_free (ipcp_sources_pool, src);
878             }
879         }
880
881       lat->values = NULL;
882       return set_lattice_to_bottom (lat);
883     }
884
885   lat->values_count++;
886   val = (struct ipcp_value *) pool_alloc (ipcp_values_pool);
887   memset (val, 0, sizeof (*val));
888
889   add_value_source (val, cs, src_val, src_idx);
890   val->value = newval;
891   val->next = lat->values;
892   lat->values = val;
893   return true;
894 }
895
896 /* Propagate values through a pass-through jump function JFUNC associated with
897    edge CS, taking values from SRC_LAT and putting them into DEST_LAT.  SRC_IDX
898    is the index of the source parameter.  */
899
900 static bool
901 propagate_vals_accross_pass_through (struct cgraph_edge *cs,
902                                      struct ipa_jump_func *jfunc,
903                                      struct ipcp_lattice *src_lat,
904                                      struct ipcp_lattice *dest_lat,
905                                      int src_idx)
906 {
907   struct ipcp_value *src_val;
908   bool ret = false;
909
910   if (jfunc->value.pass_through.operation == NOP_EXPR)
911     for (src_val = src_lat->values; src_val; src_val = src_val->next)
912       ret |= add_value_to_lattice (dest_lat, src_val->value, cs,
913                                    src_val, src_idx);
914   /* Do not create new values when propagating within an SCC because if there
915      arithmetic functions with circular dependencies, there is infinite number
916      of them and we would just make lattices bottom.  */
917   else if (edge_within_scc (cs))
918     ret = set_lattice_contains_variable (dest_lat);
919   else
920     for (src_val = src_lat->values; src_val; src_val = src_val->next)
921       {
922         tree cstval = src_val->value;
923
924         if (TREE_CODE (cstval) == TREE_BINFO)
925           {
926             ret |= set_lattice_contains_variable (dest_lat);
927             continue;
928           }
929         cstval = ipa_get_jf_pass_through_result (jfunc, cstval);
930
931         if (cstval)
932           ret |= add_value_to_lattice (dest_lat, cstval, cs, src_val, src_idx);
933         else
934           ret |= set_lattice_contains_variable (dest_lat);
935       }
936
937   return ret;
938 }
939
940 /* Propagate values through an ancestor jump function JFUNC associated with
941    edge CS, taking values from SRC_LAT and putting them into DEST_LAT.  SRC_IDX
942    is the index of the source parameter.  */
943
944 static bool
945 propagate_vals_accross_ancestor (struct cgraph_edge *cs,
946                                  struct ipa_jump_func *jfunc,
947                                  struct ipcp_lattice *src_lat,
948                                  struct ipcp_lattice *dest_lat,
949                                  int src_idx)
950 {
951   struct ipcp_value *src_val;
952   bool ret = false;
953
954   if (edge_within_scc (cs))
955     return set_lattice_contains_variable (dest_lat);
956
957   for (src_val = src_lat->values; src_val; src_val = src_val->next)
958     {
959       tree t = src_val->value;
960
961       if (TREE_CODE (t) == TREE_BINFO)
962         t = get_binfo_at_offset (t, jfunc->value.ancestor.offset,
963                                  jfunc->value.ancestor.type);
964       else
965         t = ipa_get_jf_ancestor_result (jfunc, t);
966
967       if (t)
968         ret |= add_value_to_lattice (dest_lat, t, cs, src_val, src_idx);
969       else
970         ret |= set_lattice_contains_variable (dest_lat);
971     }
972
973   return ret;
974 }
975
976 /* Propagate values across jump function JFUNC that is associated with edge CS
977    and put the values into DEST_LAT.  */
978
979 static bool
980 propagate_accross_jump_function (struct cgraph_edge *cs,
981                                  struct ipa_jump_func *jfunc,
982                                  struct ipcp_lattice *dest_lat)
983 {
984   if (dest_lat->bottom)
985     return false;
986
987   if (jfunc->type == IPA_JF_CONST
988       || jfunc->type == IPA_JF_KNOWN_TYPE)
989     {
990       tree val;
991
992       if (jfunc->type == IPA_JF_KNOWN_TYPE)
993         {
994           val = ipa_value_from_known_type_jfunc (jfunc);
995           if (!val)
996             return set_lattice_contains_variable (dest_lat);
997         }
998       else
999         val = jfunc->value.constant;
1000       return add_value_to_lattice (dest_lat, val, cs, NULL, 0);
1001     }
1002   else if (jfunc->type == IPA_JF_PASS_THROUGH
1003            || jfunc->type == IPA_JF_ANCESTOR)
1004     {
1005       struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1006       struct ipcp_lattice *src_lat;
1007       int src_idx;
1008       bool ret;
1009
1010       if (jfunc->type == IPA_JF_PASS_THROUGH)
1011         src_idx = jfunc->value.pass_through.formal_id;
1012       else
1013         src_idx = jfunc->value.ancestor.formal_id;
1014
1015       src_lat = ipa_get_lattice (caller_info, src_idx);
1016       if (src_lat->bottom)
1017         return set_lattice_contains_variable (dest_lat);
1018
1019       /* If we would need to clone the caller and cannot, do not propagate.  */
1020       if (!ipcp_versionable_function_p (cs->caller)
1021           && (src_lat->contains_variable
1022               || (src_lat->values_count > 1)))
1023         return set_lattice_contains_variable (dest_lat);
1024
1025       if (jfunc->type == IPA_JF_PASS_THROUGH)
1026         ret = propagate_vals_accross_pass_through (cs, jfunc, src_lat,
1027                                                    dest_lat, src_idx);
1028       else
1029         ret = propagate_vals_accross_ancestor (cs, jfunc, src_lat, dest_lat,
1030                                                src_idx);
1031
1032       if (src_lat->contains_variable)
1033         ret |= set_lattice_contains_variable (dest_lat);
1034
1035       return ret;
1036     }
1037
1038   /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1039      use it for indirect inlining), we should propagate them too.  */
1040   return set_lattice_contains_variable (dest_lat);
1041 }
1042
1043 /* Propagate constants from the caller to the callee of CS.  INFO describes the
1044    caller.  */
1045
1046 static bool
1047 propagate_constants_accross_call (struct cgraph_edge *cs)
1048 {
1049   struct ipa_node_params *callee_info;
1050   enum availability availability;
1051   struct cgraph_node *callee, *alias_or_thunk;
1052   struct ipa_edge_args *args;
1053   bool ret = false;
1054   int i, args_count, parms_count;
1055
1056   callee = cgraph_function_node (cs->callee, &availability);
1057   if (!callee->analyzed)
1058     return false;
1059   gcc_checking_assert (cgraph_function_with_gimple_body_p (callee));
1060   callee_info = IPA_NODE_REF (callee);
1061
1062   args = IPA_EDGE_REF (cs);
1063   args_count = ipa_get_cs_argument_count (args);
1064   parms_count = ipa_get_param_count (callee_info);
1065
1066   /* If this call goes through a thunk we should not propagate because we
1067      cannot redirect edges to thunks.  However, we might need to uncover a
1068      thunk from below a series of aliases first.  */
1069   alias_or_thunk = cs->callee;
1070   while (alias_or_thunk->alias)
1071     alias_or_thunk = cgraph_alias_aliased_node (alias_or_thunk);
1072   if (alias_or_thunk->thunk.thunk_p)
1073     {
1074       for (i = 0; i < parms_count; i++)
1075         ret |= set_lattice_contains_variable (ipa_get_lattice (callee_info, i));
1076
1077       return ret;
1078     }
1079
1080   for (i = 0; (i < args_count) && (i < parms_count); i++)
1081     {
1082       struct ipa_jump_func *jump_func = ipa_get_ith_jump_func (args, i);
1083       struct ipcp_lattice *dest_lat = ipa_get_lattice (callee_info, i);
1084
1085       if (availability == AVAIL_OVERWRITABLE)
1086         ret |= set_lattice_contains_variable (dest_lat);
1087       else
1088         ret |= propagate_accross_jump_function (cs, jump_func, dest_lat);
1089     }
1090   for (; i < parms_count; i++)
1091     ret |= set_lattice_contains_variable (ipa_get_lattice (callee_info, i));
1092
1093   return ret;
1094 }
1095
1096 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
1097    (which can contain both constants and binfos) or KNOWN_BINFOS (which can be
1098    NULL) return the destination.  */
1099
1100 tree
1101 ipa_get_indirect_edge_target (struct cgraph_edge *ie,
1102                               VEC (tree, heap) *known_vals,
1103                               VEC (tree, heap) *known_binfos)
1104 {
1105   int param_index = ie->indirect_info->param_index;
1106   HOST_WIDE_INT token, anc_offset;
1107   tree otr_type;
1108   tree t;
1109
1110   if (param_index == -1)
1111     return NULL_TREE;
1112
1113   if (!ie->indirect_info->polymorphic)
1114     {
1115       tree t = (VEC_length (tree, known_vals) > (unsigned int) param_index
1116                 ? VEC_index (tree, known_vals, param_index) : NULL);
1117       if (t &&
1118           TREE_CODE (t) == ADDR_EXPR
1119           && TREE_CODE (TREE_OPERAND (t, 0)) == FUNCTION_DECL)
1120         return TREE_OPERAND (t, 0);
1121       else
1122         return NULL_TREE;
1123     }
1124
1125   token = ie->indirect_info->otr_token;
1126   anc_offset = ie->indirect_info->anc_offset;
1127   otr_type = ie->indirect_info->otr_type;
1128
1129   t = VEC_index (tree, known_vals, param_index);
1130   if (!t && known_binfos
1131       && VEC_length (tree, known_binfos) > (unsigned int) param_index)
1132     t = VEC_index (tree, known_binfos, param_index);
1133   if (!t)
1134     return NULL_TREE;
1135
1136   if (TREE_CODE (t) != TREE_BINFO)
1137     {
1138       tree binfo;
1139       binfo = gimple_extract_devirt_binfo_from_cst (t);
1140       if (!binfo)
1141         return NULL_TREE;
1142       binfo = get_binfo_at_offset (binfo, anc_offset, otr_type);
1143       if (!binfo)
1144         return NULL_TREE;
1145       return gimple_get_virt_method_for_binfo (token, binfo);
1146     }
1147   else
1148     {
1149       tree binfo;
1150
1151       binfo = get_binfo_at_offset (t, anc_offset, otr_type);
1152       if (!binfo)
1153         return NULL_TREE;
1154       return gimple_get_virt_method_for_binfo (token, binfo);
1155     }
1156 }
1157
1158 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
1159    and KNOWN_BINFOS.  */
1160
1161 static int
1162 devirtualization_time_bonus (struct cgraph_node *node,
1163                              VEC (tree, heap) *known_csts,
1164                              VEC (tree, heap) *known_binfos)
1165 {
1166   struct cgraph_edge *ie;
1167   int res = 0;
1168
1169   for (ie = node->indirect_calls; ie; ie = ie->next_callee)
1170     {
1171       struct cgraph_node *callee;
1172       struct inline_summary *isummary;
1173       tree target;
1174
1175       target = ipa_get_indirect_edge_target (ie, known_csts, known_binfos);
1176       if (!target)
1177         continue;
1178
1179       /* Only bare minimum benefit for clearly un-inlineable targets.  */
1180       res += 1;
1181       callee = cgraph_get_node (target);
1182       if (!callee || !callee->analyzed)
1183         continue;
1184       isummary = inline_summary (callee);
1185       if (!isummary->inlinable)
1186         continue;
1187
1188       /* FIXME: The values below need re-considering and perhaps also
1189          integrating into the cost metrics, at lest in some very basic way.  */
1190       if (isummary->size <= MAX_INLINE_INSNS_AUTO / 4)
1191         res += 31;
1192       else if (isummary->size <= MAX_INLINE_INSNS_AUTO / 2)
1193         res += 15;
1194       else if (isummary->size <= MAX_INLINE_INSNS_AUTO
1195                || DECL_DECLARED_INLINE_P (callee->decl))
1196         res += 7;
1197     }
1198
1199   return res;
1200 }
1201
1202 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
1203    and SIZE_COST and with the sum of frequencies of incoming edges to the
1204    potential new clone in FREQUENCIES.  */
1205
1206 static bool
1207 good_cloning_opportunity_p (struct cgraph_node *node, int time_benefit,
1208                             int freq_sum, gcov_type count_sum, int size_cost)
1209 {
1210   if (time_benefit == 0
1211       || !flag_ipa_cp_clone
1212       || !optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node->decl)))
1213     return false;
1214
1215   gcc_assert (size_cost > 0);
1216
1217   if (max_count)
1218     {
1219       int factor = (count_sum * 1000) / max_count;
1220       HOST_WIDEST_INT evaluation = (((HOST_WIDEST_INT) time_benefit * factor)
1221                                     / size_cost);
1222
1223       if (dump_file && (dump_flags & TDF_DETAILS))
1224         fprintf (dump_file, "     good_cloning_opportunity_p (time: %i, "
1225                  "size: %i, count_sum: " HOST_WIDE_INT_PRINT_DEC
1226                  ") -> evaluation: " HOST_WIDEST_INT_PRINT_DEC
1227                  ", threshold: %i\n",
1228                  time_benefit, size_cost, (HOST_WIDE_INT) count_sum,
1229                  evaluation, 500);
1230
1231       return evaluation >= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD);
1232     }
1233   else
1234     {
1235       HOST_WIDEST_INT evaluation = (((HOST_WIDEST_INT) time_benefit * freq_sum)
1236                                     / size_cost);
1237
1238       if (dump_file && (dump_flags & TDF_DETAILS))
1239         fprintf (dump_file, "     good_cloning_opportunity_p (time: %i, "
1240                  "size: %i, freq_sum: %i) -> evaluation: "
1241                  HOST_WIDEST_INT_PRINT_DEC ", threshold: %i\n",
1242                  time_benefit, size_cost, freq_sum, evaluation,
1243                  CGRAPH_FREQ_BASE /2);
1244
1245       return evaluation >= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD);
1246     }
1247 }
1248
1249
1250 /* Allocate KNOWN_CSTS and KNOWN_BINFOS and populate them with values of
1251    parameters that are known independent of the context.  INFO describes the
1252    function.  If REMOVABLE_PARAMS_COST is non-NULL, the movement cost of all
1253    removable parameters will be stored in it.  */
1254
1255 static bool
1256 gather_context_independent_values (struct ipa_node_params *info,
1257                                    VEC (tree, heap) **known_csts,
1258                                    VEC (tree, heap) **known_binfos,
1259                                    int *removable_params_cost)
1260 {
1261   int i, count = ipa_get_param_count (info);
1262   bool ret = false;
1263
1264   *known_csts = NULL;
1265   *known_binfos = NULL;
1266   VEC_safe_grow_cleared (tree, heap, *known_csts, count);
1267   VEC_safe_grow_cleared (tree, heap, *known_binfos, count);
1268
1269   if (removable_params_cost)
1270     *removable_params_cost = 0;
1271
1272   for (i = 0; i < count ; i++)
1273     {
1274       struct ipcp_lattice *lat = ipa_get_lattice (info, i);
1275
1276       if (ipa_lat_is_single_const (lat))
1277         {
1278           struct ipcp_value *val = lat->values;
1279           if (TREE_CODE (val->value) != TREE_BINFO)
1280             {
1281               VEC_replace (tree, *known_csts, i, val->value);
1282               if (removable_params_cost)
1283                 *removable_params_cost
1284                   += estimate_move_cost (TREE_TYPE (val->value));
1285               ret = true;
1286             }
1287           else if (lat->virt_call)
1288             {
1289               VEC_replace (tree, *known_binfos, i, val->value);
1290               ret = true;
1291             }
1292           else if (removable_params_cost
1293                    && !ipa_is_param_used (info, i))
1294             *removable_params_cost
1295               += estimate_move_cost (TREE_TYPE (ipa_get_param (info, i)));
1296         }
1297       else if (removable_params_cost
1298                && !ipa_is_param_used (info, i))
1299         *removable_params_cost
1300           +=  estimate_move_cost (TREE_TYPE (ipa_get_param (info, i)));
1301     }
1302
1303   return ret;
1304 }
1305
1306 /* Iterate over known values of parameters of NODE and estimate the local
1307    effects in terms of time and size they have.  */
1308
1309 static void
1310 estimate_local_effects (struct cgraph_node *node)
1311 {
1312   struct ipa_node_params *info = IPA_NODE_REF (node);
1313   int i, count = ipa_get_param_count (info);
1314   VEC (tree, heap) *known_csts, *known_binfos;
1315   bool always_const;
1316   int base_time = inline_summary (node)->time;
1317   int removable_params_cost;
1318
1319   if (!count || !ipcp_versionable_function_p (node))
1320     return;
1321
1322   if (dump_file && (dump_flags & TDF_DETAILS))
1323     fprintf (dump_file, "\nEstimating effects for %s/%i, base_time: %i.\n",
1324              cgraph_node_name (node), node->uid, base_time);
1325
1326   always_const = gather_context_independent_values (info, &known_csts,
1327                                                     &known_binfos,
1328                                                     &removable_params_cost);
1329   if (always_const)
1330     {
1331       struct caller_statistics stats;
1332       int time, size;
1333
1334       init_caller_stats (&stats);
1335       cgraph_for_node_and_aliases (node, gather_caller_stats, &stats, false);
1336       estimate_ipcp_clone_size_and_time (node, known_csts, known_binfos,
1337                                          &size, &time);
1338       time -= devirtualization_time_bonus (node, known_csts, known_binfos);
1339       time -= removable_params_cost;
1340       size -= stats.n_calls * removable_params_cost;
1341
1342       if (dump_file)
1343         fprintf (dump_file, " - context independent values, size: %i, "
1344                  "time_benefit: %i\n", size, base_time - time);
1345
1346       if (size <= 0
1347           || cgraph_will_be_removed_from_program_if_no_direct_calls (node))
1348         {
1349           info->clone_for_all_contexts = true;
1350           base_time = time;
1351
1352           if (dump_file)
1353             fprintf (dump_file, "     Decided to specialize for all "
1354                      "known contexts, code not going to grow.\n");
1355         }
1356       else if (good_cloning_opportunity_p (node, base_time - time,
1357                                            stats.freq_sum, stats.count_sum,
1358                                            size))
1359         {
1360           if (size + overall_size <= max_new_size)
1361             {
1362               info->clone_for_all_contexts = true;
1363               base_time = time;
1364               overall_size += size;
1365
1366               if (dump_file)
1367                 fprintf (dump_file, "     Decided to specialize for all "
1368                          "known contexts, growth deemed beneficial.\n");
1369             }
1370           else if (dump_file && (dump_flags & TDF_DETAILS))
1371             fprintf (dump_file, "   Not cloning for all contexts because "
1372                      "max_new_size would be reached with %li.\n",
1373                      size + overall_size);
1374         }
1375     }
1376
1377   for (i = 0; i < count ; i++)
1378     {
1379       struct ipcp_lattice *lat = ipa_get_lattice (info, i);
1380       struct ipcp_value *val;
1381       int emc;
1382
1383       if (lat->bottom
1384           || !lat->values
1385           || VEC_index (tree, known_csts, i)
1386           || VEC_index (tree, known_binfos, i))
1387         continue;
1388
1389       for (val = lat->values; val; val = val->next)
1390         {
1391           int time, size, time_benefit;
1392
1393           if (TREE_CODE (val->value) != TREE_BINFO)
1394             {
1395               VEC_replace (tree, known_csts, i, val->value);
1396               VEC_replace (tree, known_binfos, i, NULL_TREE);
1397               emc = estimate_move_cost (TREE_TYPE (val->value));
1398             }
1399           else if (lat->virt_call)
1400             {
1401               VEC_replace (tree, known_csts, i, NULL_TREE);
1402               VEC_replace (tree, known_binfos, i, val->value);
1403               emc = 0;
1404             }
1405           else
1406             continue;
1407
1408           estimate_ipcp_clone_size_and_time (node, known_csts, known_binfos,
1409                                              &size, &time);
1410           time_benefit = base_time - time
1411             + devirtualization_time_bonus (node, known_csts, known_binfos)
1412             + removable_params_cost + emc;
1413
1414           gcc_checking_assert (size >=0);
1415           /* The inliner-heuristics based estimates may think that in certain
1416              contexts some functions do not have any size at all but we want
1417              all specializations to have at least a tiny cost, not least not to
1418              divide by zero.  */
1419           if (size == 0)
1420             size = 1;
1421
1422           if (dump_file && (dump_flags & TDF_DETAILS))
1423             {
1424               fprintf (dump_file, " - estimates for value ");
1425               print_ipcp_constant_value (dump_file, val->value);
1426               fprintf (dump_file, " for parameter ");
1427               print_generic_expr (dump_file, ipa_get_param (info, i), 0);
1428               fprintf (dump_file, ": time_benefit: %i, size: %i\n",
1429                        time_benefit, size);
1430             }
1431
1432           val->local_time_benefit = time_benefit;
1433           val->local_size_cost = size;
1434         }
1435     }
1436
1437   VEC_free (tree, heap, known_csts);
1438   VEC_free (tree, heap, known_binfos);
1439 }
1440
1441
1442 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
1443    topological sort of values.  */
1444
1445 static void
1446 add_val_to_toposort (struct ipcp_value *cur_val)
1447 {
1448   static int dfs_counter = 0;
1449   static struct ipcp_value *stack;
1450   struct ipcp_value_source *src;
1451
1452   if (cur_val->dfs)
1453     return;
1454
1455   dfs_counter++;
1456   cur_val->dfs = dfs_counter;
1457   cur_val->low_link = dfs_counter;
1458
1459   cur_val->topo_next = stack;
1460   stack = cur_val;
1461   cur_val->on_stack = true;
1462
1463   for (src = cur_val->sources; src; src = src->next)
1464     if (src->val)
1465       {
1466         if (src->val->dfs == 0)
1467           {
1468             add_val_to_toposort (src->val);
1469             if (src->val->low_link < cur_val->low_link)
1470               cur_val->low_link = src->val->low_link;
1471           }
1472         else if (src->val->on_stack
1473                  && src->val->dfs < cur_val->low_link)
1474           cur_val->low_link = src->val->dfs;
1475       }
1476
1477   if (cur_val->dfs == cur_val->low_link)
1478     {
1479       struct ipcp_value *v, *scc_list = NULL;
1480
1481       do
1482         {
1483           v = stack;
1484           stack = v->topo_next;
1485           v->on_stack = false;
1486
1487           v->scc_next = scc_list;
1488           scc_list = v;
1489         }
1490       while (v != cur_val);
1491
1492       cur_val->topo_next = values_topo;
1493       values_topo = cur_val;
1494     }
1495 }
1496
1497 /* Add all values in lattices associated with NODE to the topological sort if
1498    they are not there yet.  */
1499
1500 static void
1501 add_all_node_vals_to_toposort (struct cgraph_node *node)
1502 {
1503   struct ipa_node_params *info = IPA_NODE_REF (node);
1504   int i, count = ipa_get_param_count (info);
1505
1506   for (i = 0; i < count ; i++)
1507     {
1508       struct ipcp_lattice *lat = ipa_get_lattice (info, i);
1509       struct ipcp_value *val;
1510
1511       if (lat->bottom || !lat->values)
1512         continue;
1513       for (val = lat->values; val; val = val->next)
1514         add_val_to_toposort (val);
1515     }
1516 }
1517
1518 /* One pass of constants propagation along the call graph edges, from callers
1519    to callees (requires topological ordering in TOPO), iterate over strongly
1520    connected components.  */
1521
1522 static void
1523 propagate_constants_topo (struct topo_info *topo)
1524 {
1525   int i;
1526
1527   for (i = topo->nnodes - 1; i >= 0; i--)
1528     {
1529       struct cgraph_node *v, *node = topo->order[i];
1530       struct ipa_dfs_info *node_dfs_info;
1531
1532       if (!cgraph_function_with_gimple_body_p (node))
1533         continue;
1534
1535       node_dfs_info = (struct ipa_dfs_info *) node->aux;
1536       /* First, iteratively propagate within the strongly connected component
1537          until all lattices stabilize.  */
1538       v = node_dfs_info->next_cycle;
1539       while (v)
1540         {
1541           push_node_to_stack (topo, v);
1542           v = ((struct ipa_dfs_info *) v->aux)->next_cycle;
1543         }
1544
1545       v = node;
1546       while (v)
1547         {
1548           struct cgraph_edge *cs;
1549
1550           for (cs = v->callees; cs; cs = cs->next_callee)
1551             if (edge_within_scc (cs)
1552                 && propagate_constants_accross_call (cs))
1553               push_node_to_stack (topo, cs->callee);
1554           v = pop_node_from_stack (topo);
1555         }
1556
1557       /* Afterwards, propagate along edges leading out of the SCC, calculates
1558          the local effects of the discovered constants and all valid values to
1559          their topological sort.  */
1560       v = node;
1561       while (v)
1562         {
1563           struct cgraph_edge *cs;
1564
1565           estimate_local_effects (v);
1566           add_all_node_vals_to_toposort (v);
1567           for (cs = v->callees; cs; cs = cs->next_callee)
1568             if (!edge_within_scc (cs))
1569               propagate_constants_accross_call (cs);
1570
1571           v = ((struct ipa_dfs_info *) v->aux)->next_cycle;
1572         }
1573     }
1574 }
1575
1576
1577 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
1578    the bigger one if otherwise.  */
1579
1580 static int
1581 safe_add (int a, int b)
1582 {
1583   if (a > INT_MAX/2 || b > INT_MAX/2)
1584     return a > b ? a : b;
1585   else
1586     return a + b;
1587 }
1588
1589
1590 /* Propagate the estimated effects of individual values along the topological
1591    from the dependant values to those they depend on.  */
1592
1593 static void
1594 propagate_effects (void)
1595 {
1596   struct ipcp_value *base;
1597
1598   for (base = values_topo; base; base = base->topo_next)
1599     {
1600       struct ipcp_value_source *src;
1601       struct ipcp_value *val;
1602       int time = 0, size = 0;
1603
1604       for (val = base; val; val = val->scc_next)
1605         {
1606           time = safe_add (time,
1607                            val->local_time_benefit + val->prop_time_benefit);
1608           size = safe_add (size, val->local_size_cost + val->prop_size_cost);
1609         }
1610
1611       for (val = base; val; val = val->scc_next)
1612         for (src = val->sources; src; src = src->next)
1613           if (src->val
1614               && cgraph_maybe_hot_edge_p (src->cs))
1615             {
1616               src->val->prop_time_benefit = safe_add (time,
1617                                                 src->val->prop_time_benefit);
1618               src->val->prop_size_cost = safe_add (size,
1619                                                    src->val->prop_size_cost);
1620             }
1621     }
1622 }
1623
1624
1625 /* Propagate constants, binfos and their effects from the summaries
1626    interprocedurally.  */
1627
1628 static void
1629 ipcp_propagate_stage (struct topo_info *topo)
1630 {
1631   struct cgraph_node *node;
1632
1633   if (dump_file)
1634     fprintf (dump_file, "\n Propagating constants:\n\n");
1635
1636   if (in_lto_p)
1637     ipa_update_after_lto_read ();
1638
1639
1640   FOR_EACH_DEFINED_FUNCTION (node)
1641   {
1642     struct ipa_node_params *info = IPA_NODE_REF (node);
1643
1644     determine_versionability (node);
1645     if (cgraph_function_with_gimple_body_p (node))
1646       {
1647         info->lattices = XCNEWVEC (struct ipcp_lattice,
1648                                    ipa_get_param_count (info));
1649         initialize_node_lattices (node);
1650       }
1651     if (node->count > max_count)
1652       max_count = node->count;
1653     overall_size += inline_summary (node)->self_size;
1654   }
1655
1656   max_new_size = overall_size;
1657   if (max_new_size < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
1658     max_new_size = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
1659   max_new_size += max_new_size * PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH) / 100 + 1;
1660
1661   if (dump_file)
1662     fprintf (dump_file, "\noverall_size: %li, max_new_size: %li\n",
1663              overall_size, max_new_size);
1664
1665   propagate_constants_topo (topo);
1666 #ifdef ENABLE_CHECKING
1667   ipcp_verify_propagated_values ();
1668 #endif
1669   propagate_effects ();
1670
1671   if (dump_file)
1672     {
1673       fprintf (dump_file, "\nIPA lattices after all propagation:\n");
1674       print_all_lattices (dump_file, (dump_flags & TDF_DETAILS), true);
1675     }
1676 }
1677
1678 /* Discover newly direct outgoing edges from NODE which is a new clone with
1679    known KNOWN_VALS and make them direct.  */
1680
1681 static void
1682 ipcp_discover_new_direct_edges (struct cgraph_node *node,
1683                                 VEC (tree, heap) *known_vals)
1684 {
1685   struct cgraph_edge *ie, *next_ie;
1686
1687   for (ie = node->indirect_calls; ie; ie = next_ie)
1688     {
1689       tree target;
1690
1691       next_ie = ie->next_callee;
1692       target = ipa_get_indirect_edge_target (ie, known_vals, NULL);
1693       if (target)
1694         ipa_make_edge_direct_to_target (ie, target);
1695     }
1696 }
1697
1698 /* Vector of pointers which for linked lists of clones of an original crgaph
1699    edge. */
1700
1701 static VEC (cgraph_edge_p, heap) *next_edge_clone;
1702
1703 static inline void
1704 grow_next_edge_clone_vector (void)
1705 {
1706   if (VEC_length (cgraph_edge_p, next_edge_clone)
1707       <=  (unsigned) cgraph_edge_max_uid)
1708     VEC_safe_grow_cleared (cgraph_edge_p, heap, next_edge_clone,
1709                            cgraph_edge_max_uid + 1);
1710 }
1711
1712 /* Edge duplication hook to grow the appropriate linked list in
1713    next_edge_clone. */
1714
1715 static void
1716 ipcp_edge_duplication_hook (struct cgraph_edge *src, struct cgraph_edge *dst,
1717                             __attribute__((unused)) void *data)
1718 {
1719   grow_next_edge_clone_vector ();
1720   VEC_replace (cgraph_edge_p, next_edge_clone, dst->uid,
1721                VEC_index (cgraph_edge_p, next_edge_clone, src->uid));
1722   VEC_replace (cgraph_edge_p, next_edge_clone, src->uid, dst);
1723 }
1724
1725 /* Get the next clone in the linked list of clones of an edge.  */
1726
1727 static inline struct cgraph_edge *
1728 get_next_cgraph_edge_clone (struct cgraph_edge *cs)
1729 {
1730   return VEC_index (cgraph_edge_p, next_edge_clone, cs->uid);
1731 }
1732
1733 /* Return true if edge CS does bring about the value described by SRC.  */
1734
1735 static bool
1736 cgraph_edge_brings_value_p (struct cgraph_edge *cs,
1737                             struct ipcp_value_source *src)
1738 {
1739   struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1740
1741   if (IPA_NODE_REF (cs->callee)->ipcp_orig_node
1742       || caller_info->node_dead)
1743     return false;
1744   if (!src->val)
1745     return true;
1746
1747   if (caller_info->ipcp_orig_node)
1748     {
1749       tree t = VEC_index (tree, caller_info->known_vals, src->index);
1750       return (t != NULL_TREE
1751               && values_equal_for_ipcp_p (src->val->value, t));
1752     }
1753   else
1754     {
1755       struct ipcp_lattice *lat = ipa_get_lattice (caller_info, src->index);
1756       if (ipa_lat_is_single_const (lat)
1757           && values_equal_for_ipcp_p (src->val->value, lat->values->value))
1758         return true;
1759       else
1760         return false;
1761     }
1762 }
1763
1764 /* Given VAL, iterate over all its sources and if they still hold, add their
1765    edge frequency and their number into *FREQUENCY and *CALLER_COUNT
1766    respectively.  */
1767
1768 static bool
1769 get_info_about_necessary_edges (struct ipcp_value *val, int *freq_sum,
1770                                 gcov_type *count_sum, int *caller_count)
1771 {
1772   struct ipcp_value_source *src;
1773   int freq = 0, count = 0;
1774   gcov_type cnt = 0;
1775   bool hot = false;
1776
1777   for (src = val->sources; src; src = src->next)
1778     {
1779       struct cgraph_edge *cs = src->cs;
1780       while (cs)
1781         {
1782           if (cgraph_edge_brings_value_p (cs, src))
1783             {
1784               count++;
1785               freq += cs->frequency;
1786               cnt += cs->count;
1787               hot |= cgraph_maybe_hot_edge_p (cs);
1788             }
1789           cs = get_next_cgraph_edge_clone (cs);
1790         }
1791     }
1792
1793   *freq_sum = freq;
1794   *count_sum = cnt;
1795   *caller_count = count;
1796   return hot;
1797 }
1798
1799 /* Return a vector of incoming edges that do bring value VAL.  It is assumed
1800    their number is known and equal to CALLER_COUNT.  */
1801
1802 static VEC (cgraph_edge_p,heap) *
1803 gather_edges_for_value (struct ipcp_value *val, int caller_count)
1804 {
1805   struct ipcp_value_source *src;
1806   VEC (cgraph_edge_p,heap) *ret;
1807
1808   ret = VEC_alloc (cgraph_edge_p, heap, caller_count);
1809   for (src = val->sources; src; src = src->next)
1810     {
1811       struct cgraph_edge *cs = src->cs;
1812       while (cs)
1813         {
1814           if (cgraph_edge_brings_value_p (cs, src))
1815             VEC_quick_push (cgraph_edge_p, ret, cs);
1816           cs = get_next_cgraph_edge_clone (cs);
1817         }
1818     }
1819
1820   return ret;
1821 }
1822
1823 /* Construct a replacement map for a know VALUE for a formal parameter PARAM.
1824    Return it or NULL if for some reason it cannot be created.  */
1825
1826 static struct ipa_replace_map *
1827 get_replacement_map (tree value, tree parm)
1828 {
1829   tree req_type = TREE_TYPE (parm);
1830   struct ipa_replace_map *replace_map;
1831
1832   if (!useless_type_conversion_p (req_type, TREE_TYPE (value)))
1833     {
1834       if (fold_convertible_p (req_type, value))
1835         value = fold_build1 (NOP_EXPR, req_type, value);
1836       else if (TYPE_SIZE (req_type) == TYPE_SIZE (TREE_TYPE (value)))
1837         value = fold_build1 (VIEW_CONVERT_EXPR, req_type, value);
1838       else
1839         {
1840           if (dump_file)
1841             {
1842               fprintf (dump_file, "    const ");
1843               print_generic_expr (dump_file, value, 0);
1844               fprintf (dump_file, "  can't be converted to param ");
1845               print_generic_expr (dump_file, parm, 0);
1846               fprintf (dump_file, "\n");
1847             }
1848           return NULL;
1849         }
1850     }
1851
1852   replace_map = ggc_alloc_ipa_replace_map ();
1853   if (dump_file)
1854     {
1855       fprintf (dump_file, "    replacing param ");
1856       print_generic_expr (dump_file, parm, 0);
1857       fprintf (dump_file, " with const ");
1858       print_generic_expr (dump_file, value, 0);
1859       fprintf (dump_file, "\n");
1860     }
1861   replace_map->old_tree = parm;
1862   replace_map->new_tree = value;
1863   replace_map->replace_p = true;
1864   replace_map->ref_p = false;
1865
1866   return replace_map;
1867 }
1868
1869 /* Dump new profiling counts */
1870
1871 static void
1872 dump_profile_updates (struct cgraph_node *orig_node,
1873                       struct cgraph_node *new_node)
1874 {
1875   struct cgraph_edge *cs;
1876
1877   fprintf (dump_file, "    setting count of the specialized node to "
1878            HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) new_node->count);
1879   for (cs = new_node->callees; cs ; cs = cs->next_callee)
1880     fprintf (dump_file, "      edge to %s has count "
1881              HOST_WIDE_INT_PRINT_DEC "\n",
1882              cgraph_node_name (cs->callee), (HOST_WIDE_INT) cs->count);
1883
1884   fprintf (dump_file, "    setting count of the original node to "
1885            HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) orig_node->count);
1886   for (cs = orig_node->callees; cs ; cs = cs->next_callee)
1887     fprintf (dump_file, "      edge to %s is left with "
1888              HOST_WIDE_INT_PRINT_DEC "\n",
1889              cgraph_node_name (cs->callee), (HOST_WIDE_INT) cs->count);
1890 }
1891
1892 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update
1893    their profile information to reflect this.  */
1894
1895 static void
1896 update_profiling_info (struct cgraph_node *orig_node,
1897                        struct cgraph_node *new_node)
1898 {
1899   struct cgraph_edge *cs;
1900   struct caller_statistics stats;
1901   gcov_type new_sum, orig_sum;
1902   gcov_type remainder, orig_node_count = orig_node->count;
1903
1904   if (orig_node_count == 0)
1905     return;
1906
1907   init_caller_stats (&stats);
1908   cgraph_for_node_and_aliases (orig_node, gather_caller_stats, &stats, false);
1909   orig_sum = stats.count_sum;
1910   init_caller_stats (&stats);
1911   cgraph_for_node_and_aliases (new_node, gather_caller_stats, &stats, false);
1912   new_sum = stats.count_sum;
1913
1914   if (orig_node_count < orig_sum + new_sum)
1915     {
1916       if (dump_file)
1917         fprintf (dump_file, "    Problem: node %s/%i has too low count "
1918                  HOST_WIDE_INT_PRINT_DEC " while the sum of incoming "
1919                  "counts is " HOST_WIDE_INT_PRINT_DEC "\n",
1920                  cgraph_node_name (orig_node), orig_node->uid,
1921                  (HOST_WIDE_INT) orig_node_count,
1922                  (HOST_WIDE_INT) (orig_sum + new_sum));
1923
1924       orig_node_count = (orig_sum + new_sum) * 12 / 10;
1925       if (dump_file)
1926         fprintf (dump_file, "      proceeding by pretending it was "
1927                  HOST_WIDE_INT_PRINT_DEC "\n",
1928                  (HOST_WIDE_INT) orig_node_count);
1929     }
1930
1931   new_node->count = new_sum;
1932   remainder = orig_node_count - new_sum;
1933   orig_node->count = remainder;
1934
1935   for (cs = new_node->callees; cs ; cs = cs->next_callee)
1936     if (cs->frequency)
1937       cs->count = cs->count * (new_sum * REG_BR_PROB_BASE
1938                                / orig_node_count) / REG_BR_PROB_BASE;
1939     else
1940       cs->count = 0;
1941
1942   for (cs = orig_node->callees; cs ; cs = cs->next_callee)
1943     cs->count = cs->count * (remainder * REG_BR_PROB_BASE
1944                              / orig_node_count) / REG_BR_PROB_BASE;
1945
1946   if (dump_file)
1947     dump_profile_updates (orig_node, new_node);
1948 }
1949
1950 /* Update the respective profile of specialized NEW_NODE and the original
1951    ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
1952    have been redirected to the specialized version.  */
1953
1954 static void
1955 update_specialized_profile (struct cgraph_node *new_node,
1956                             struct cgraph_node *orig_node,
1957                             gcov_type redirected_sum)
1958 {
1959   struct cgraph_edge *cs;
1960   gcov_type new_node_count, orig_node_count = orig_node->count;
1961
1962   if (dump_file)
1963     fprintf (dump_file, "    the sum of counts of redirected  edges is "
1964              HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) redirected_sum);
1965   if (orig_node_count == 0)
1966     return;
1967
1968   gcc_assert (orig_node_count >= redirected_sum);
1969
1970   new_node_count = new_node->count;
1971   new_node->count += redirected_sum;
1972   orig_node->count -= redirected_sum;
1973
1974   for (cs = new_node->callees; cs ; cs = cs->next_callee)
1975     if (cs->frequency)
1976       cs->count += cs->count * redirected_sum / new_node_count;
1977     else
1978       cs->count = 0;
1979
1980   for (cs = orig_node->callees; cs ; cs = cs->next_callee)
1981     {
1982       gcov_type dec = cs->count * (redirected_sum * REG_BR_PROB_BASE
1983                                    / orig_node_count) / REG_BR_PROB_BASE;
1984       if (dec < cs->count)
1985         cs->count -= dec;
1986       else
1987         cs->count = 0;
1988     }
1989
1990   if (dump_file)
1991     dump_profile_updates (orig_node, new_node);
1992 }
1993
1994 /* Create a specialized version of NODE with known constants and types of
1995    parameters in KNOWN_VALS and redirect all edges in CALLERS to it.  */
1996
1997 static struct cgraph_node *
1998 create_specialized_node (struct cgraph_node *node,
1999                          VEC (tree, heap) *known_vals,
2000                          VEC (cgraph_edge_p,heap) *callers)
2001 {
2002   struct ipa_node_params *new_info, *info = IPA_NODE_REF (node);
2003   VEC (ipa_replace_map_p,gc)* replace_trees = NULL;
2004   struct cgraph_node *new_node;
2005   int i, count = ipa_get_param_count (info);
2006   bitmap args_to_skip;
2007
2008   gcc_assert (!info->ipcp_orig_node);
2009
2010   if (node->local.can_change_signature)
2011     {
2012       args_to_skip = BITMAP_GGC_ALLOC ();
2013       for (i = 0; i < count; i++)
2014         {
2015           tree t = VEC_index (tree, known_vals, i);
2016
2017           if ((t && TREE_CODE (t) != TREE_BINFO)
2018               || !ipa_is_param_used (info, i))
2019             bitmap_set_bit (args_to_skip, i);
2020         }
2021     }
2022   else
2023     {
2024       args_to_skip = NULL;
2025       if (dump_file && (dump_flags & TDF_DETAILS))
2026         fprintf (dump_file, "      cannot change function signature\n");
2027     }
2028
2029   for (i = 0; i < count ; i++)
2030     {
2031       tree t = VEC_index (tree, known_vals, i);
2032       if (t && TREE_CODE (t) != TREE_BINFO)
2033         {
2034           struct ipa_replace_map *replace_map;
2035
2036           replace_map = get_replacement_map (t, ipa_get_param (info, i));
2037           if (replace_map)
2038             VEC_safe_push (ipa_replace_map_p, gc, replace_trees, replace_map);
2039         }
2040     }
2041
2042   new_node = cgraph_create_virtual_clone (node, callers, replace_trees,
2043                                           args_to_skip, "constprop");
2044   if (dump_file && (dump_flags & TDF_DETAILS))
2045     fprintf (dump_file, "     the new node is %s/%i.\n",
2046              cgraph_node_name (new_node), new_node->uid);
2047   gcc_checking_assert (ipa_node_params_vector
2048                        && (VEC_length (ipa_node_params_t,
2049                                        ipa_node_params_vector)
2050                            > (unsigned) cgraph_max_uid));
2051   update_profiling_info (node, new_node);
2052   new_info = IPA_NODE_REF (new_node);
2053   new_info->ipcp_orig_node = node;
2054   new_info->known_vals = known_vals;
2055
2056   ipcp_discover_new_direct_edges (new_node, known_vals);
2057
2058   VEC_free (cgraph_edge_p, heap, callers);
2059   return new_node;
2060 }
2061
2062 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
2063    KNOWN_VALS with constants and types that are also known for all of the
2064    CALLERS.  */
2065
2066 static void
2067 find_more_values_for_callers_subset (struct cgraph_node *node,
2068                                      VEC (tree, heap) *known_vals,
2069                                      VEC (cgraph_edge_p,heap) *callers)
2070 {
2071   struct ipa_node_params *info = IPA_NODE_REF (node);
2072   int i, count = ipa_get_param_count (info);
2073
2074   for (i = 0; i < count ; i++)
2075     {
2076       struct cgraph_edge *cs;
2077       tree newval = NULL_TREE;
2078       int j;
2079
2080       if (ipa_get_lattice (info, i)->bottom
2081           || VEC_index (tree, known_vals, i))
2082         continue;
2083
2084       FOR_EACH_VEC_ELT (cgraph_edge_p, callers, j, cs)
2085         {
2086           struct ipa_jump_func *jump_func;
2087           tree t;
2088
2089           if (i >= ipa_get_cs_argument_count (IPA_EDGE_REF (cs)))
2090             {
2091               newval = NULL_TREE;
2092               break;
2093             }
2094           jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
2095           t = ipa_value_from_jfunc (IPA_NODE_REF (cs->caller), jump_func);
2096           if (!t
2097               || (newval
2098                   && !values_equal_for_ipcp_p (t, newval)))
2099             {
2100               newval = NULL_TREE;
2101               break;
2102             }
2103           else
2104             newval = t;
2105         }
2106
2107       if (newval)
2108         {
2109           if (dump_file && (dump_flags & TDF_DETAILS))
2110             {
2111               fprintf (dump_file, "    adding an extra known value ");
2112               print_ipcp_constant_value (dump_file, newval);
2113               fprintf (dump_file, " for parameter ");
2114               print_generic_expr (dump_file, ipa_get_param (info, i), 0);
2115               fprintf (dump_file, "\n");
2116             }
2117
2118           VEC_replace (tree, known_vals, i, newval);
2119         }
2120     }
2121 }
2122
2123 /* Given an original NODE and a VAL for which we have already created a
2124    specialized clone, look whether there are incoming edges that still lead
2125    into the old node but now also bring the requested value and also conform to
2126    all other criteria such that they can be redirected the the special node.
2127    This function can therefore redirect the final edge in a SCC.  */
2128
2129 static void
2130 perhaps_add_new_callers (struct cgraph_node *node, struct ipcp_value *val)
2131 {
2132   struct ipa_node_params *dest_info = IPA_NODE_REF (val->spec_node);
2133   struct ipcp_value_source *src;
2134   int count = ipa_get_param_count (dest_info);
2135   gcov_type redirected_sum = 0;
2136
2137   for (src = val->sources; src; src = src->next)
2138     {
2139       struct cgraph_edge *cs = src->cs;
2140       while (cs)
2141         {
2142           enum availability availability;
2143           bool insufficient = false;
2144
2145           if (cgraph_function_node (cs->callee, &availability) == node
2146               && availability > AVAIL_OVERWRITABLE
2147               && cgraph_edge_brings_value_p (cs, src))
2148             {
2149               struct ipa_node_params *caller_info;
2150               struct ipa_edge_args *args;
2151               int i;
2152
2153               caller_info = IPA_NODE_REF (cs->caller);
2154               args = IPA_EDGE_REF (cs);
2155               for (i = 0; i < count; i++)
2156                 {
2157                   struct ipa_jump_func *jump_func;
2158                   tree val, t;
2159
2160                   val = VEC_index (tree, dest_info->known_vals, i);
2161                   if (!val)
2162                     continue;
2163
2164                   if (i >= ipa_get_cs_argument_count (args))
2165                     {
2166                       insufficient = true;
2167                       break;
2168                     }
2169                   jump_func = ipa_get_ith_jump_func (args, i);
2170                   t = ipa_value_from_jfunc (caller_info, jump_func);
2171                   if (!t || !values_equal_for_ipcp_p (val, t))
2172                     {
2173                       insufficient = true;
2174                       break;
2175                     }
2176                 }
2177
2178               if (!insufficient)
2179                 {
2180                   if (dump_file)
2181                     fprintf (dump_file, " - adding an extra caller %s/%i"
2182                              " of %s/%i\n",
2183                              xstrdup (cgraph_node_name (cs->caller)),
2184                              cs->caller->uid,
2185                              xstrdup (cgraph_node_name (val->spec_node)),
2186                              val->spec_node->uid);
2187
2188                   cgraph_redirect_edge_callee (cs, val->spec_node);
2189                   redirected_sum += cs->count;
2190                 }
2191             }
2192           cs = get_next_cgraph_edge_clone (cs);
2193         }
2194     }
2195
2196   if (redirected_sum)
2197     update_specialized_profile (val->spec_node, node, redirected_sum);
2198 }
2199
2200
2201 /* Copy KNOWN_BINFOS to KNOWN_VALS.  */
2202
2203 static void
2204 move_binfos_to_values (VEC (tree, heap) *known_vals,
2205                        VEC (tree, heap) *known_binfos)
2206 {
2207   tree t;
2208   int i;
2209
2210   for (i = 0; VEC_iterate (tree, known_binfos, i, t); i++)
2211     if (t)
2212       VEC_replace (tree, known_vals, i, t);
2213 }
2214
2215
2216 /* Decide whether and what specialized clones of NODE should be created.  */
2217
2218 static bool
2219 decide_whether_version_node (struct cgraph_node *node)
2220 {
2221   struct ipa_node_params *info = IPA_NODE_REF (node);
2222   int i, count = ipa_get_param_count (info);
2223   VEC (tree, heap) *known_csts, *known_binfos;
2224   bool ret = false;
2225
2226   if (count == 0)
2227     return false;
2228
2229   if (dump_file && (dump_flags & TDF_DETAILS))
2230     fprintf (dump_file, "\nEvaluating opportunities for %s/%i.\n",
2231              cgraph_node_name (node), node->uid);
2232
2233   gather_context_independent_values (info, &known_csts, &known_binfos,
2234                                      NULL);
2235
2236   for (i = 0; i < count ; i++)
2237     {
2238       struct ipcp_lattice *lat = ipa_get_lattice (info, i);
2239       struct ipcp_value *val;
2240
2241       if (lat->bottom
2242           || VEC_index (tree, known_csts, i)
2243           || VEC_index (tree, known_binfos, i))
2244         continue;
2245
2246       for (val = lat->values; val; val = val->next)
2247         {
2248           int freq_sum, caller_count;
2249           gcov_type count_sum;
2250           VEC (cgraph_edge_p, heap) *callers;
2251           VEC (tree, heap) *kv;
2252
2253           if (val->spec_node)
2254             {
2255               perhaps_add_new_callers (node, val);
2256               continue;
2257             }
2258           else if (val->local_size_cost + overall_size > max_new_size)
2259             {
2260               if (dump_file && (dump_flags & TDF_DETAILS))
2261                 fprintf (dump_file, "   Ignoring candidate value because "
2262                          "max_new_size would be reached with %li.\n",
2263                          val->local_size_cost + overall_size);
2264               continue;
2265             }
2266           else if (!get_info_about_necessary_edges (val, &freq_sum, &count_sum,
2267                                                     &caller_count))
2268             continue;
2269
2270           if (dump_file && (dump_flags & TDF_DETAILS))
2271             {
2272               fprintf (dump_file, " - considering value ");
2273               print_ipcp_constant_value (dump_file, val->value);
2274               fprintf (dump_file, " for parameter ");
2275               print_generic_expr (dump_file, ipa_get_param (info, i), 0);
2276               fprintf (dump_file, " (caller_count: %i)\n", caller_count);
2277             }
2278
2279
2280           if (!good_cloning_opportunity_p (node, val->local_time_benefit,
2281                                            freq_sum, count_sum,
2282                                            val->local_size_cost)
2283               && !good_cloning_opportunity_p (node,
2284                                               val->local_time_benefit
2285                                               + val->prop_time_benefit,
2286                                               freq_sum, count_sum,
2287                                               val->local_size_cost
2288                                               + val->prop_size_cost))
2289             continue;
2290
2291           if (dump_file)
2292             fprintf (dump_file, "  Creating a specialized node of %s/%i.\n",
2293                      cgraph_node_name (node), node->uid);
2294
2295           callers = gather_edges_for_value (val, caller_count);
2296           kv = VEC_copy (tree, heap, known_csts);
2297           move_binfos_to_values (kv, known_binfos);
2298           VEC_replace (tree, kv, i, val->value);
2299           find_more_values_for_callers_subset (node, kv, callers);
2300           val->spec_node = create_specialized_node (node, kv, callers);
2301           overall_size += val->local_size_cost;
2302           info = IPA_NODE_REF (node);
2303
2304           /* TODO: If for some lattice there is only one other known value
2305              left, make a special node for it too. */
2306           ret = true;
2307
2308           VEC_replace (tree, kv, i, val->value);
2309         }
2310     }
2311
2312   if (info->clone_for_all_contexts)
2313     {
2314       VEC (cgraph_edge_p, heap) *callers;
2315
2316       if (dump_file)
2317         fprintf (dump_file, " - Creating a specialized node of %s/%i "
2318                  "for all known contexts.\n", cgraph_node_name (node),
2319                  node->uid);
2320
2321       callers = collect_callers_of_node (node);
2322       move_binfos_to_values (known_csts, known_binfos);
2323       create_specialized_node (node, known_csts, callers);
2324       info = IPA_NODE_REF (node);
2325       info->clone_for_all_contexts = false;
2326       ret = true;
2327     }
2328   else
2329     VEC_free (tree, heap, known_csts);
2330
2331   VEC_free (tree, heap, known_binfos);
2332   return ret;
2333 }
2334
2335 /* Transitively mark all callees of NODE within the same SCC as not dead.  */
2336
2337 static void
2338 spread_undeadness (struct cgraph_node *node)
2339 {
2340   struct cgraph_edge *cs;
2341
2342   for (cs = node->callees; cs; cs = cs->next_callee)
2343     if (edge_within_scc (cs))
2344       {
2345         struct cgraph_node *callee;
2346         struct ipa_node_params *info;
2347
2348         callee = cgraph_function_node (cs->callee, NULL);
2349         info = IPA_NODE_REF (callee);
2350
2351         if (info->node_dead)
2352           {
2353             info->node_dead = 0;
2354             spread_undeadness (callee);
2355           }
2356       }
2357 }
2358
2359 /* Return true if NODE has a caller from outside of its SCC that is not
2360    dead.  Worker callback for cgraph_for_node_and_aliases.  */
2361
2362 static bool
2363 has_undead_caller_from_outside_scc_p (struct cgraph_node *node,
2364                                      void *data ATTRIBUTE_UNUSED)
2365 {
2366   struct cgraph_edge *cs;
2367
2368   for (cs = node->callers; cs; cs = cs->next_caller)
2369     if (cs->caller->thunk.thunk_p
2370         && cgraph_for_node_and_aliases (cs->caller,
2371                                         has_undead_caller_from_outside_scc_p,
2372                                         NULL, true))
2373       return true;
2374     else if (!edge_within_scc (cs)
2375              && !IPA_NODE_REF (cs->caller)->node_dead)
2376       return true;
2377   return false;
2378 }
2379
2380
2381 /* Identify nodes within the same SCC as NODE which are no longer needed
2382    because of new clones and will be removed as unreachable.  */
2383
2384 static void
2385 identify_dead_nodes (struct cgraph_node *node)
2386 {
2387   struct cgraph_node *v;
2388   for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
2389     if (cgraph_will_be_removed_from_program_if_no_direct_calls (v)
2390         && !cgraph_for_node_and_aliases (v,
2391                                          has_undead_caller_from_outside_scc_p,
2392                                          NULL, true))
2393       IPA_NODE_REF (v)->node_dead = 1;
2394
2395   for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
2396     if (!IPA_NODE_REF (v)->node_dead)
2397       spread_undeadness (v);
2398
2399   if (dump_file && (dump_flags & TDF_DETAILS))
2400     {
2401       for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
2402         if (IPA_NODE_REF (v)->node_dead)
2403           fprintf (dump_file, "  Marking node as dead: %s/%i.\n",
2404                    cgraph_node_name (v), v->uid);
2405     }
2406 }
2407
2408 /* The decision stage.  Iterate over the topological order of call graph nodes
2409    TOPO and make specialized clones if deemed beneficial.  */
2410
2411 static void
2412 ipcp_decision_stage (struct topo_info *topo)
2413 {
2414   int i;
2415
2416   if (dump_file)
2417     fprintf (dump_file, "\nIPA decision stage:\n\n");
2418
2419   for (i = topo->nnodes - 1; i >= 0; i--)
2420     {
2421       struct cgraph_node *node = topo->order[i];
2422       bool change = false, iterate = true;
2423
2424       while (iterate)
2425         {
2426           struct cgraph_node *v;
2427           iterate = false;
2428           for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
2429             if (cgraph_function_with_gimple_body_p (v)
2430                 && ipcp_versionable_function_p (v))
2431               iterate |= decide_whether_version_node (v);
2432
2433           change |= iterate;
2434         }
2435       if (change)
2436         identify_dead_nodes (node);
2437     }
2438 }
2439
2440 /* The IPCP driver.  */
2441
2442 static unsigned int
2443 ipcp_driver (void)
2444 {
2445   struct cgraph_2edge_hook_list *edge_duplication_hook_holder;
2446   struct topo_info topo;
2447
2448   cgraph_remove_unreachable_nodes (true,dump_file);
2449   ipa_check_create_node_params ();
2450   ipa_check_create_edge_args ();
2451   grow_next_edge_clone_vector ();
2452   edge_duplication_hook_holder =
2453     cgraph_add_edge_duplication_hook (&ipcp_edge_duplication_hook, NULL);
2454   ipcp_values_pool = create_alloc_pool ("IPA-CP values",
2455                                         sizeof (struct ipcp_value), 32);
2456   ipcp_sources_pool = create_alloc_pool ("IPA-CP value sources",
2457                                          sizeof (struct ipcp_value_source), 64);
2458   if (dump_file)
2459     {
2460       fprintf (dump_file, "\nIPA structures before propagation:\n");
2461       if (dump_flags & TDF_DETAILS)
2462         ipa_print_all_params (dump_file);
2463       ipa_print_all_jump_functions (dump_file);
2464     }
2465
2466   /* Topological sort.  */
2467   build_toporder_info (&topo);
2468   /* Do the interprocedural propagation.  */
2469   ipcp_propagate_stage (&topo);
2470   /* Decide what constant propagation and cloning should be performed.  */
2471   ipcp_decision_stage (&topo);
2472
2473   /* Free all IPCP structures.  */
2474   free_toporder_info (&topo);
2475   VEC_free (cgraph_edge_p, heap, next_edge_clone);
2476   cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder);
2477   ipa_free_all_structures_after_ipa_cp ();
2478   if (dump_file)
2479     fprintf (dump_file, "\nIPA constant propagation end\n");
2480   return 0;
2481 }
2482
2483 /* Initialization and computation of IPCP data structures.  This is the initial
2484    intraprocedural analysis of functions, which gathers information to be
2485    propagated later on.  */
2486
2487 static void
2488 ipcp_generate_summary (void)
2489 {
2490   struct cgraph_node *node;
2491
2492   if (dump_file)
2493     fprintf (dump_file, "\nIPA constant propagation start:\n");
2494   ipa_register_cgraph_hooks ();
2495
2496   FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
2497       {
2498         /* Unreachable nodes should have been eliminated before ipcp.  */
2499         gcc_assert (node->needed || node->reachable);
2500         node->local.versionable = tree_versionable_function_p (node->decl);
2501         ipa_analyze_node (node);
2502       }
2503 }
2504
2505 /* Write ipcp summary for nodes in SET.  */
2506
2507 static void
2508 ipcp_write_summary (cgraph_node_set set,
2509                     varpool_node_set vset ATTRIBUTE_UNUSED)
2510 {
2511   ipa_prop_write_jump_functions (set);
2512 }
2513
2514 /* Read ipcp summary.  */
2515
2516 static void
2517 ipcp_read_summary (void)
2518 {
2519   ipa_prop_read_jump_functions ();
2520 }
2521
2522 /* Gate for IPCP optimization.  */
2523
2524 static bool
2525 cgraph_gate_cp (void)
2526 {
2527   /* FIXME: We should remove the optimize check after we ensure we never run
2528      IPA passes when not optimizing.  */
2529   return flag_ipa_cp && optimize;
2530 }
2531
2532 struct ipa_opt_pass_d pass_ipa_cp =
2533 {
2534  {
2535   IPA_PASS,
2536   "cp",                         /* name */
2537   cgraph_gate_cp,               /* gate */
2538   ipcp_driver,                  /* execute */
2539   NULL,                         /* sub */
2540   NULL,                         /* next */
2541   0,                            /* static_pass_number */
2542   TV_IPA_CONSTANT_PROP,         /* tv_id */
2543   0,                            /* properties_required */
2544   0,                            /* properties_provided */
2545   0,                            /* properties_destroyed */
2546   0,                            /* todo_flags_start */
2547   TODO_dump_cgraph |
2548   TODO_remove_functions | TODO_ggc_collect /* todo_flags_finish */
2549  },
2550  ipcp_generate_summary,                 /* generate_summary */
2551  ipcp_write_summary,                    /* write_summary */
2552  ipcp_read_summary,                     /* read_summary */
2553  NULL,                                  /* write_optimization_summary */
2554  NULL,                                  /* read_optimization_summary */
2555  NULL,                                  /* stmt_fixup */
2556  0,                                     /* TODOs */
2557  NULL,                                  /* function_transform */
2558  NULL,                                  /* variable_transform */
2559 };