OSDN Git Service

88a5b4fffc63b7d2b76e332045372ef97c16a390
[pf3gnuchains/gcc-fork.git] / gcc / ipa-cp.c
1 /* Interprocedural constant propagation
2    Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010
3    Free Software Foundation, Inc.
4    Contributed by Razya Ladelsky <RAZYA@il.ibm.com>
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
12
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3.  If not see
20 <http://www.gnu.org/licenses/>.  */
21
22 /* Interprocedural constant propagation.  The aim of interprocedural constant
23    propagation (IPCP) is to find which function's argument has the same
24    constant value in each invocation throughout the whole program. For example,
25    consider the following program:
26
27    int g (int y)
28    {
29      printf ("value is %d",y);
30    }
31
32    int f (int x)
33    {
34      g (x);
35    }
36
37    int h (int y)
38    {
39      g (y);
40    }
41
42    void main (void)
43    {
44      f (3);
45      h (3);
46    }
47
48
49    The IPCP algorithm will find that g's formal argument y is always called
50    with the value 3.
51
52    The algorithm used is based on "Interprocedural Constant Propagation", by
53    Challahan David, Keith D Cooper, Ken Kennedy, Linda Torczon, Comp86, pg
54    152-161
55
56    The optimization is divided into three stages:
57
58    First stage - intraprocedural analysis
59    =======================================
60    This phase computes jump_function and modification flags.
61
62    A jump function for a callsite represents the values passed as an actual
63    arguments of a given callsite. There are three types of values:
64    Pass through - the caller's formal parameter is passed as an actual argument.
65    Constant - a constant is passed as an actual argument.
66    Unknown - neither of the above.
67
68    The jump function info, ipa_jump_func, is stored in ipa_edge_args
69    structure (defined in ipa_prop.h and pointed to by cgraph_node->aux)
70    modified_flags are defined in ipa_node_params structure
71    (defined in ipa_prop.h and pointed to by cgraph_edge->aux).
72
73    -ipcp_init_stage() is the first stage driver.
74
75    Second stage - interprocedural analysis
76    ========================================
77    This phase does the interprocedural constant propagation.
78    It computes lattices for all formal parameters in the program
79    and their value that may be:
80    TOP - unknown.
81    BOTTOM - non constant.
82    CONSTANT - constant value.
83
84    Lattice describing a formal parameter p will have a constant value if all
85    callsites invoking this function have the same constant value passed to p.
86
87    The lattices are stored in ipcp_lattice which is itself in ipa_node_params
88    structure (defined in ipa_prop.h and pointed to by cgraph_edge->aux).
89
90    -ipcp_iterate_stage() is the second stage driver.
91
92    Third phase - transformation of function code
93    ============================================
94    Propagates the constant-valued formals into the function.
95    For each function whose parameters are constants, we create its clone.
96
97    Then we process the clone in two ways:
98    1. We insert an assignment statement 'parameter = const' at the beginning
99       of the cloned function.
100    2. For read-only parameters that do not live in memory, we replace all their
101       uses with the constant.
102
103    We also need to modify some callsites to call the cloned functions instead
104    of the original ones.  For a callsite passing an argument found to be a
105    constant by IPCP, there are two different cases to handle:
106    1. A constant is passed as an argument.  In this case the callsite in the
107       should be redirected to call the cloned callee.
108    2. A parameter (of the caller) passed as an argument (pass through
109       argument).  In such cases both the caller and the callee have clones and
110       only the callsite in the cloned caller is redirected to call to the
111       cloned callee.
112
113    This update is done in two steps: First all cloned functions are created
114    during a traversal of the call graph, during which all callsites are
115    redirected to call the cloned function.  Then the callsites are traversed
116    and many calls redirected back to fit the description above.
117
118    -ipcp_insert_stage() is the third phase driver.
119
120 */
121
122 #include "config.h"
123 #include "system.h"
124 #include "coretypes.h"
125 #include "tree.h"
126 #include "target.h"
127 #include "cgraph.h"
128 #include "ipa-prop.h"
129 #include "tree-flow.h"
130 #include "tree-pass.h"
131 #include "flags.h"
132 #include "timevar.h"
133 #include "diagnostic.h"
134 #include "tree-dump.h"
135 #include "tree-inline.h"
136 #include "fibheap.h"
137 #include "params.h"
138
139 /* Number of functions identified as candidates for cloning. When not cloning
140    we can simplify iterate stage not forcing it to go through the decision
141    on what is profitable and what not.  */
142 static int n_cloning_candidates;
143
144 /* Maximal count found in program.  */
145 static gcov_type max_count;
146
147 /* Cgraph nodes that has been completely replaced by cloning during iterate
148  * stage and will be removed after ipcp is finished.  */
149 static bitmap dead_nodes;
150
151 static void ipcp_print_profile_data (FILE *);
152 static void ipcp_function_scale_print (FILE *);
153
154 /* Get the original node field of ipa_node_params associated with node NODE.  */
155 static inline struct cgraph_node *
156 ipcp_get_orig_node (struct cgraph_node *node)
157 {
158   return IPA_NODE_REF (node)->ipcp_orig_node;
159 }
160
161 /* Return true if NODE describes a cloned/versioned function.  */
162 static inline bool
163 ipcp_node_is_clone (struct cgraph_node *node)
164 {
165   return (ipcp_get_orig_node (node) != NULL);
166 }
167
168 /* Create ipa_node_params and its data structures for NEW_NODE.  Set ORIG_NODE
169    as the ipcp_orig_node field in ipa_node_params.  */
170 static void
171 ipcp_init_cloned_node (struct cgraph_node *orig_node,
172                        struct cgraph_node *new_node)
173 {
174   ipa_check_create_node_params ();
175   ipa_initialize_node_params (new_node);
176   IPA_NODE_REF (new_node)->ipcp_orig_node = orig_node;
177 }
178
179 /* Perform intraprocedrual analysis needed for ipcp.  */
180 static void
181 ipcp_analyze_node (struct cgraph_node *node)
182 {
183   /* Unreachable nodes should have been eliminated before ipcp.  */
184   gcc_assert (node->needed || node->reachable);
185
186   node->local.versionable = tree_versionable_function_p (node->decl);
187   ipa_initialize_node_params (node);
188   ipa_detect_param_modifications (node);
189 }
190
191 /* Return scale for NODE.  */
192 static inline gcov_type
193 ipcp_get_node_scale (struct cgraph_node *node)
194 {
195   return IPA_NODE_REF (node)->count_scale;
196 }
197
198 /* Set COUNT as scale for NODE.  */
199 static inline void
200 ipcp_set_node_scale (struct cgraph_node *node, gcov_type count)
201 {
202   IPA_NODE_REF (node)->count_scale = count;
203 }
204
205 /* Return whether LAT is a constant lattice.  */
206 static inline bool
207 ipcp_lat_is_const (struct ipcp_lattice *lat)
208 {
209   if (lat->type == IPA_CONST_VALUE)
210     return true;
211   else
212     return false;
213 }
214
215 /* Return whether LAT is a constant lattice that ipa-cp can actually insert
216    into the code (i.e. constants excluding member pointers and pointers).  */
217 static inline bool
218 ipcp_lat_is_insertable (struct ipcp_lattice *lat)
219 {
220   return lat->type == IPA_CONST_VALUE;
221 }
222
223 /* Return true if LAT1 and LAT2 are equal.  */
224 static inline bool
225 ipcp_lats_are_equal (struct ipcp_lattice *lat1, struct ipcp_lattice *lat2)
226 {
227   gcc_assert (ipcp_lat_is_const (lat1) && ipcp_lat_is_const (lat2));
228   if (lat1->type != lat2->type)
229     return false;
230
231   if (TREE_CODE (lat1->constant) ==  ADDR_EXPR
232       && TREE_CODE (lat2->constant) ==  ADDR_EXPR
233       && TREE_CODE (TREE_OPERAND (lat1->constant, 0)) == CONST_DECL
234       && TREE_CODE (TREE_OPERAND (lat2->constant, 0)) == CONST_DECL)
235     return operand_equal_p (DECL_INITIAL (TREE_OPERAND (lat1->constant, 0)),
236                             DECL_INITIAL (TREE_OPERAND (lat2->constant, 0)), 0);
237   else
238     return operand_equal_p (lat1->constant, lat2->constant, 0);
239 }
240
241 /* Compute Meet arithmetics:
242    Meet (IPA_BOTTOM, x) = IPA_BOTTOM
243    Meet (IPA_TOP,x) = x
244    Meet (const_a,const_b) = IPA_BOTTOM,  if const_a != const_b.
245    MEET (const_a,const_b) = const_a, if const_a == const_b.*/
246 static void
247 ipa_lattice_meet (struct ipcp_lattice *res, struct ipcp_lattice *lat1,
248                   struct ipcp_lattice *lat2)
249 {
250   if (lat1->type == IPA_BOTTOM || lat2->type == IPA_BOTTOM)
251     {
252       res->type = IPA_BOTTOM;
253       return;
254     }
255   if (lat1->type == IPA_TOP)
256     {
257       res->type = lat2->type;
258       res->constant = lat2->constant;
259       return;
260     }
261   if (lat2->type == IPA_TOP)
262     {
263       res->type = lat1->type;
264       res->constant = lat1->constant;
265       return;
266     }
267   if (!ipcp_lats_are_equal (lat1, lat2))
268     {
269       res->type = IPA_BOTTOM;
270       return;
271     }
272   res->type = lat1->type;
273   res->constant = lat1->constant;
274 }
275
276 /* Return the lattice corresponding to the Ith formal parameter of the function
277    described by INFO.  */
278 static inline struct ipcp_lattice *
279 ipcp_get_lattice (struct ipa_node_params *info, int i)
280 {
281   return &(info->params[i].ipcp_lattice);
282 }
283
284 /* Given the jump function JFUNC, compute the lattice LAT that describes the
285    value coming down the callsite. INFO describes the caller node so that
286    pass-through jump functions can be evaluated.  */
287 static void
288 ipcp_lattice_from_jfunc (struct ipa_node_params *info, struct ipcp_lattice *lat,
289                          struct ipa_jump_func *jfunc)
290 {
291   if (jfunc->type == IPA_JF_CONST)
292     {
293       lat->type = IPA_CONST_VALUE;
294       lat->constant = jfunc->value.constant;
295     }
296   else if (jfunc->type == IPA_JF_PASS_THROUGH)
297     {
298       struct ipcp_lattice *caller_lat;
299       tree cst;
300
301       caller_lat = ipcp_get_lattice (info, jfunc->value.pass_through.formal_id);
302       lat->type = caller_lat->type;
303       if (caller_lat->type != IPA_CONST_VALUE)
304         return;
305       cst = caller_lat->constant;
306
307       if (jfunc->value.pass_through.operation != NOP_EXPR)
308         {
309           tree restype;
310           if (TREE_CODE_CLASS (jfunc->value.pass_through.operation)
311               == tcc_comparison)
312             restype = boolean_type_node;
313           else
314             restype = TREE_TYPE (cst);
315           cst = fold_binary (jfunc->value.pass_through.operation,
316                              restype, cst, jfunc->value.pass_through.operand);
317         }
318       if (!cst || !is_gimple_ip_invariant (cst))
319         lat->type = IPA_BOTTOM;
320       lat->constant = cst;
321     }
322   else if (jfunc->type == IPA_JF_ANCESTOR)
323     {
324       struct ipcp_lattice *caller_lat;
325       tree t;
326       bool ok;
327
328       caller_lat = ipcp_get_lattice (info, jfunc->value.ancestor.formal_id);
329       lat->type = caller_lat->type;
330       if (caller_lat->type != IPA_CONST_VALUE)
331         return;
332       if (TREE_CODE (caller_lat->constant) != ADDR_EXPR)
333         {
334           /* This can happen when the constant is a NULL pointer.  */
335           lat->type = IPA_BOTTOM;
336           return;
337         }
338       t = TREE_OPERAND (caller_lat->constant, 0);
339       ok = build_ref_for_offset (&t, TREE_TYPE (t),
340                                  jfunc->value.ancestor.offset,
341                                  jfunc->value.ancestor.type, false);
342       if (!ok)
343         {
344           lat->type = IPA_BOTTOM;
345           lat->constant = NULL_TREE;
346         }
347       else
348         lat->constant = build_fold_addr_expr (t);
349     }
350   else
351     lat->type = IPA_BOTTOM;
352 }
353
354 /* True when OLD_LAT and NEW_LAT values are not the same.  */
355
356 static bool
357 ipcp_lattice_changed (struct ipcp_lattice *old_lat,
358                       struct ipcp_lattice *new_lat)
359 {
360   if (old_lat->type == new_lat->type)
361     {
362       if (!ipcp_lat_is_const (old_lat))
363         return false;
364       if (ipcp_lats_are_equal (old_lat, new_lat))
365         return false;
366     }
367   return true;
368 }
369
370 /* Print all ipcp_lattices of all functions to F.  */
371 static void
372 ipcp_print_all_lattices (FILE * f)
373 {
374   struct cgraph_node *node;
375   int i, count;
376
377   fprintf (f, "\nLattice:\n");
378   for (node = cgraph_nodes; node; node = node->next)
379     {
380       struct ipa_node_params *info;
381
382       if (!node->analyzed)
383         continue;
384       info = IPA_NODE_REF (node);
385       fprintf (f, "  Node: %s:\n", cgraph_node_name (node));
386       count = ipa_get_param_count (info);
387       for (i = 0; i < count; i++)
388         {
389           struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
390
391           fprintf (f, "    param [%d]: ", i);
392           if (lat->type == IPA_CONST_VALUE)
393             {
394               tree cst = lat->constant;
395               fprintf (f, "type is CONST ");
396               print_generic_expr (f, cst, 0);
397               if (TREE_CODE (cst) == ADDR_EXPR
398                   && TREE_CODE (TREE_OPERAND (cst, 0)) == CONST_DECL)
399                 {
400                   fprintf (f, " -> ");
401                   print_generic_expr (f, DECL_INITIAL (TREE_OPERAND (cst, 0)),
402                                                        0);
403                 }
404               fprintf (f, "\n");
405             }
406           else if (lat->type == IPA_TOP)
407             fprintf (f, "type is TOP\n");
408           else
409             fprintf (f, "type is BOTTOM\n");
410         }
411     }
412 }
413
414 /* Return true if ipcp algorithms would allow cloning NODE.  */
415
416 static bool
417 ipcp_versionable_function_p (struct cgraph_node *node)
418 {
419   tree decl = node->decl;
420   basic_block bb;
421
422   /* There are a number of generic reasons functions cannot be versioned.  */
423   if (!node->local.versionable)
424     return false;
425
426   /* Removing arguments doesn't work if the function takes varargs.  */
427   if (DECL_STRUCT_FUNCTION (decl)->stdarg)
428     return false;
429
430   /* Removing arguments doesn't work if we use __builtin_apply_args.  */
431   FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (decl))
432     {
433       gimple_stmt_iterator gsi;
434       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
435         {
436           const_gimple stmt = gsi_stmt (gsi);
437           tree t;
438
439           if (!is_gimple_call (stmt))
440             continue;
441           t = gimple_call_fndecl (stmt);
442           if (t == NULL_TREE)
443             continue;
444           if (DECL_BUILT_IN_CLASS (t) == BUILT_IN_NORMAL
445               && DECL_FUNCTION_CODE (t) == BUILT_IN_APPLY_ARGS)
446             return false;
447         }
448     }
449
450   return true;
451 }
452
453 /* Return true if this NODE is viable candidate for cloning.  */
454 static bool
455 ipcp_cloning_candidate_p (struct cgraph_node *node)
456 {
457   int n_calls = 0;
458   int n_hot_calls = 0;
459   gcov_type direct_call_sum = 0;
460   struct cgraph_edge *e;
461
462   /* We never clone functions that are not visible from outside.
463      FIXME: in future we should clone such functions when they are called with
464      different constants, but current ipcp implementation is not good on this.
465      */
466   if (cgraph_only_called_directly_p (node) || !node->analyzed)
467     return false;
468
469   if (cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE)
470     {
471       if (dump_file)
472         fprintf (dump_file, "Not considering %s for cloning; body is overwrittable.\n",
473                  cgraph_node_name (node));
474       return false;
475     }
476   if (!ipcp_versionable_function_p (node))
477     {
478       if (dump_file)
479         fprintf (dump_file, "Not considering %s for cloning; body is not versionable.\n",
480                  cgraph_node_name (node));
481       return false;
482     }
483   for (e = node->callers; e; e = e->next_caller)
484     {
485       direct_call_sum += e->count;
486       n_calls ++;
487       if (cgraph_maybe_hot_edge_p (e))
488         n_hot_calls ++;
489     }
490
491   if (!n_calls)
492     {
493       if (dump_file)
494         fprintf (dump_file, "Not considering %s for cloning; no direct calls.\n",
495                  cgraph_node_name (node));
496       return false;
497     }
498   if (node->local.inline_summary.self_size < n_calls)
499     {
500       if (dump_file)
501         fprintf (dump_file, "Considering %s for cloning; code would shrink.\n",
502                  cgraph_node_name (node));
503       return true;
504     }
505
506   if (!flag_ipa_cp_clone)
507     {
508       if (dump_file)
509         fprintf (dump_file, "Not considering %s for cloning; -fipa-cp-clone disabled.\n",
510                  cgraph_node_name (node));
511       return false;
512     }
513
514   if (!optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node->decl)))
515     {
516       if (dump_file)
517         fprintf (dump_file, "Not considering %s for cloning; optimizing it for size.\n",
518                  cgraph_node_name (node));
519       return false;
520     }
521
522   /* When profile is available and function is hot, propagate into it even if
523      calls seems cold; constant propagation can improve function's speed
524      significandly.  */
525   if (max_count)
526     {
527       if (direct_call_sum > node->count * 90 / 100)
528         {
529           if (dump_file)
530             fprintf (dump_file, "Considering %s for cloning; usually called directly.\n",
531                      cgraph_node_name (node));
532           return true;
533         }
534     }
535   if (!n_hot_calls)
536     {
537       if (dump_file)
538         fprintf (dump_file, "Not considering %s for cloning; no hot calls.\n",
539                  cgraph_node_name (node));
540       return false;
541     }
542   if (dump_file)
543     fprintf (dump_file, "Considering %s for cloning.\n",
544              cgraph_node_name (node));
545   return true;
546 }
547
548 /* Initialize ipcp_lattices array.  The lattices corresponding to supported
549    types (integers, real types and Fortran constants defined as const_decls)
550    are initialized to IPA_TOP, the rest of them to IPA_BOTTOM.  */
551 static void
552 ipcp_initialize_node_lattices (struct cgraph_node *node)
553 {
554   int i;
555   struct ipa_node_params *info = IPA_NODE_REF (node);
556   enum ipa_lattice_type type;
557
558   if (ipa_is_called_with_var_arguments (info))
559     type = IPA_BOTTOM;
560   else if (cgraph_only_called_directly_p (node))
561     type = IPA_TOP;
562   /* When cloning is allowed, we can assume that externally visible functions
563      are not called.  We will compensate this by cloning later.  */
564   else if (ipcp_cloning_candidate_p (node))
565     type = IPA_TOP, n_cloning_candidates ++;
566   else
567     type = IPA_BOTTOM;
568
569   for (i = 0; i < ipa_get_param_count (info) ; i++)
570     ipcp_get_lattice (info, i)->type = type;
571 }
572
573 /* build INTEGER_CST tree with type TREE_TYPE and value according to LAT.
574    Return the tree.  */
575 static tree
576 build_const_val (struct ipcp_lattice *lat, tree tree_type)
577 {
578   tree val;
579
580   gcc_assert (ipcp_lat_is_const (lat));
581   val = lat->constant;
582
583   if (!useless_type_conversion_p (tree_type, TREE_TYPE (val)))
584     {
585       if (fold_convertible_p (tree_type, val))
586         return fold_build1 (NOP_EXPR, tree_type, val);
587       else
588         return fold_build1 (VIEW_CONVERT_EXPR, tree_type, val);
589     }
590   return val;
591 }
592
593 /* Compute the proper scale for NODE.  It is the ratio between the number of
594    direct calls (represented on the incoming cgraph_edges) and sum of all
595    invocations of NODE (represented as count in cgraph_node).
596
597    FIXME: This code is wrong.  Since the callers can be also clones and
598    the clones are not scaled yet, the sums gets unrealistically high.
599    To properly compute the counts, we would need to do propagation across
600    callgraph (as external call to A might imply call to non-clonned B
601    if A's clone calls clonned B).  */
602 static void
603 ipcp_compute_node_scale (struct cgraph_node *node)
604 {
605   gcov_type sum;
606   struct cgraph_edge *cs;
607
608   sum = 0;
609   /* Compute sum of all counts of callers. */
610   for (cs = node->callers; cs != NULL; cs = cs->next_caller)
611     sum += cs->count;
612   /* Work around the unrealistically high sum problem.  We just don't want
613      the non-cloned body to have negative or very low frequency.  Since
614      majority of execution time will be spent in clones anyway, this should
615      give good enough profile.  */
616   if (sum > node->count * 9 / 10)
617     sum = node->count * 9 / 10;
618   if (node->count == 0)
619     ipcp_set_node_scale (node, 0);
620   else
621     ipcp_set_node_scale (node, sum * REG_BR_PROB_BASE / node->count);
622 }
623
624 /* Initialization and computation of IPCP data structures.  This is the initial
625    intraprocedural analysis of functions, which gathers information to be
626    propagated later on.  */
627 static void
628 ipcp_init_stage (void)
629 {
630   struct cgraph_node *node;
631   struct cgraph_edge *cs;
632
633   for (node = cgraph_nodes; node; node = node->next)
634     if (node->analyzed)
635       ipcp_analyze_node (node);
636   for (node = cgraph_nodes; node; node = node->next)
637     {
638       if (!node->analyzed)
639         continue;
640       /* building jump functions  */
641       for (cs = node->callees; cs; cs = cs->next_callee)
642         {
643           /* We do not need to bother analyzing calls to unknown
644              functions unless they may become known during lto/whopr.  */
645           if (!cs->callee->analyzed && !flag_lto && !flag_whopr)
646             continue;
647           ipa_count_arguments (cs);
648           if (ipa_get_cs_argument_count (IPA_EDGE_REF (cs))
649               != ipa_get_param_count (IPA_NODE_REF (cs->callee)))
650             ipa_set_called_with_variable_arg (IPA_NODE_REF (cs->callee));
651           ipa_compute_jump_functions (cs);
652         }
653     }
654 }
655
656 /* Return true if there are some formal parameters whose value is IPA_TOP (in
657    the whole compilation unit).  Change their values to IPA_BOTTOM, since they
658    most probably get their values from outside of this compilation unit.  */
659 static bool
660 ipcp_change_tops_to_bottom (void)
661 {
662   int i, count;
663   struct cgraph_node *node;
664   bool prop_again;
665
666   prop_again = false;
667   for (node = cgraph_nodes; node; node = node->next)
668     {
669       struct ipa_node_params *info = IPA_NODE_REF (node);
670       count = ipa_get_param_count (info);
671       for (i = 0; i < count; i++)
672         {
673           struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
674           if (lat->type == IPA_TOP)
675             {
676               prop_again = true;
677               if (dump_file)
678                 {
679                   fprintf (dump_file, "Forcing param ");
680                   print_generic_expr (dump_file, ipa_get_param (info, i), 0);
681                   fprintf (dump_file, " of node %s to bottom.\n",
682                            cgraph_node_name (node));
683                 }
684               lat->type = IPA_BOTTOM;
685             }
686         }
687     }
688   return prop_again;
689 }
690
691 /* Interprocedural analysis. The algorithm propagates constants from the
692    caller's parameters to the callee's arguments.  */
693 static void
694 ipcp_propagate_stage (void)
695 {
696   int i;
697   struct ipcp_lattice inc_lat = { IPA_BOTTOM, NULL };
698   struct ipcp_lattice new_lat = { IPA_BOTTOM, NULL };
699   struct ipcp_lattice *dest_lat;
700   struct cgraph_edge *cs;
701   struct ipa_jump_func *jump_func;
702   struct ipa_func_list *wl;
703   int count;
704
705   ipa_check_create_node_params ();
706   ipa_check_create_edge_args ();
707
708   /* Initialize worklist to contain all functions.  */
709   wl = ipa_init_func_list ();
710   while (wl)
711     {
712       struct cgraph_node *node = ipa_pop_func_from_list (&wl);
713       struct ipa_node_params *info = IPA_NODE_REF (node);
714
715       for (cs = node->callees; cs; cs = cs->next_callee)
716         {
717           struct ipa_node_params *callee_info = IPA_NODE_REF (cs->callee);
718           struct ipa_edge_args *args = IPA_EDGE_REF (cs);
719
720           if (ipa_is_called_with_var_arguments (callee_info)
721               || !cs->callee->analyzed
722               || ipa_is_called_with_var_arguments (callee_info))
723             continue;
724
725           count = ipa_get_cs_argument_count (args);
726           for (i = 0; i < count; i++)
727             {
728               jump_func = ipa_get_ith_jump_func (args, i);
729               ipcp_lattice_from_jfunc (info, &inc_lat, jump_func);
730               dest_lat = ipcp_get_lattice (callee_info, i);
731               ipa_lattice_meet (&new_lat, &inc_lat, dest_lat);
732               if (ipcp_lattice_changed (&new_lat, dest_lat))
733                 {
734                   dest_lat->type = new_lat.type;
735                   dest_lat->constant = new_lat.constant;
736                   ipa_push_func_to_list (&wl, cs->callee);
737                 }
738             }
739         }
740     }
741 }
742
743 /* Call the constant propagation algorithm and re-call it if necessary
744    (if there are undetermined values left).  */
745 static void
746 ipcp_iterate_stage (void)
747 {
748   struct cgraph_node *node;
749   n_cloning_candidates = 0;
750
751   if (dump_file)
752     fprintf (dump_file, "\nIPA iterate stage:\n\n");
753
754   if (in_lto_p)
755     ipa_update_after_lto_read ();
756
757   for (node = cgraph_nodes; node; node = node->next)
758     {
759       ipcp_initialize_node_lattices (node);
760       ipcp_compute_node_scale (node);
761     }
762   if (dump_file && (dump_flags & TDF_DETAILS))
763     {
764       ipcp_print_all_lattices (dump_file);
765       ipcp_function_scale_print (dump_file);
766     }
767
768   ipcp_propagate_stage ();
769   if (ipcp_change_tops_to_bottom ())
770     /* Some lattices have changed from IPA_TOP to IPA_BOTTOM.
771        This change should be propagated.  */
772     {
773       gcc_assert (n_cloning_candidates);
774       ipcp_propagate_stage ();
775     }
776   if (dump_file)
777     {
778       fprintf (dump_file, "\nIPA lattices after propagation:\n");
779       ipcp_print_all_lattices (dump_file);
780       if (dump_flags & TDF_DETAILS)
781         ipcp_print_profile_data (dump_file);
782     }
783 }
784
785 /* Check conditions to forbid constant insertion to function described by
786    NODE.  */
787 static inline bool
788 ipcp_node_modifiable_p (struct cgraph_node *node)
789 {
790   /* Once we will be able to do in-place replacement, we can be more
791      lax here.  */
792   return ipcp_versionable_function_p (node);
793 }
794
795 /* Print count scale data structures.  */
796 static void
797 ipcp_function_scale_print (FILE * f)
798 {
799   struct cgraph_node *node;
800
801   for (node = cgraph_nodes; node; node = node->next)
802     {
803       if (!node->analyzed)
804         continue;
805       fprintf (f, "printing scale for %s: ", cgraph_node_name (node));
806       fprintf (f, "value is  " HOST_WIDE_INT_PRINT_DEC
807                "  \n", (HOST_WIDE_INT) ipcp_get_node_scale (node));
808     }
809 }
810
811 /* Print counts of all cgraph nodes.  */
812 static void
813 ipcp_print_func_profile_counts (FILE * f)
814 {
815   struct cgraph_node *node;
816
817   for (node = cgraph_nodes; node; node = node->next)
818     {
819       fprintf (f, "function %s: ", cgraph_node_name (node));
820       fprintf (f, "count is  " HOST_WIDE_INT_PRINT_DEC
821                "  \n", (HOST_WIDE_INT) node->count);
822     }
823 }
824
825 /* Print counts of all cgraph edges.  */
826 static void
827 ipcp_print_call_profile_counts (FILE * f)
828 {
829   struct cgraph_node *node;
830   struct cgraph_edge *cs;
831
832   for (node = cgraph_nodes; node; node = node->next)
833     {
834       for (cs = node->callees; cs; cs = cs->next_callee)
835         {
836           fprintf (f, "%s -> %s ", cgraph_node_name (cs->caller),
837                    cgraph_node_name (cs->callee));
838           fprintf (f, "count is  " HOST_WIDE_INT_PRINT_DEC "  \n",
839                    (HOST_WIDE_INT) cs->count);
840         }
841     }
842 }
843
844 /* Print profile info for all functions.  */
845 static void
846 ipcp_print_profile_data (FILE * f)
847 {
848   fprintf (f, "\nNODE COUNTS :\n");
849   ipcp_print_func_profile_counts (f);
850   fprintf (f, "\nCS COUNTS stage:\n");
851   ipcp_print_call_profile_counts (f);
852 }
853
854 /* Build and initialize ipa_replace_map struct according to LAT. This struct is
855    processed by versioning, which operates according to the flags set.
856    PARM_TREE is the formal parameter found to be constant.  LAT represents the
857    constant.  */
858 static struct ipa_replace_map *
859 ipcp_create_replace_map (tree parm_tree, struct ipcp_lattice *lat)
860 {
861   struct ipa_replace_map *replace_map;
862   tree const_val;
863
864   replace_map = GGC_NEW (struct ipa_replace_map);
865   const_val = build_const_val (lat, TREE_TYPE (parm_tree));
866   if (dump_file)
867     {
868       fprintf (dump_file, "  replacing param ");
869       print_generic_expr (dump_file, parm_tree, 0);
870       fprintf (dump_file, " with const ");
871       print_generic_expr (dump_file, const_val, 0);
872       fprintf (dump_file, "\n");
873     }
874   replace_map->old_tree = parm_tree;
875   replace_map->new_tree = const_val;
876   replace_map->replace_p = true;
877   replace_map->ref_p = false;
878
879   return replace_map;
880 }
881
882 /* Return true if this callsite should be redirected to the original callee
883    (instead of the cloned one).  */
884 static bool
885 ipcp_need_redirect_p (struct cgraph_edge *cs)
886 {
887   struct ipa_node_params *orig_callee_info;
888   int i, count;
889   struct ipa_jump_func *jump_func;
890   struct cgraph_node *node = cs->callee, *orig;
891
892   if (!n_cloning_candidates)
893     return false;
894
895   if ((orig = ipcp_get_orig_node (node)) != NULL)
896     node = orig;
897   if (ipcp_get_orig_node (cs->caller))
898     return false;
899
900   orig_callee_info = IPA_NODE_REF (node);
901   count = ipa_get_param_count (orig_callee_info);
902   for (i = 0; i < count; i++)
903     {
904       struct ipcp_lattice *lat = ipcp_get_lattice (orig_callee_info, i);
905       if (ipcp_lat_is_const (lat))
906         {
907           jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
908           if (jump_func->type != IPA_JF_CONST)
909             return true;
910         }
911     }
912
913   return false;
914 }
915
916 /* Fix the callsites and the call graph after function cloning was done.  */
917 static void
918 ipcp_update_callgraph (void)
919 {
920   struct cgraph_node *node;
921
922   for (node = cgraph_nodes; node; node = node->next)
923     if (node->analyzed && ipcp_node_is_clone (node))
924       {
925         bitmap args_to_skip = BITMAP_ALLOC (NULL);
926         struct cgraph_node *orig_node = ipcp_get_orig_node (node);
927         struct ipa_node_params *info = IPA_NODE_REF (orig_node);
928         int i, count = ipa_get_param_count (info);
929         struct cgraph_edge *cs, *next;
930
931         for (i = 0; i < count; i++)
932           {
933             struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
934             tree parm_tree = ipa_get_param (info, i);
935
936             /* We can proactively remove obviously unused arguments.  */
937             if (is_gimple_reg (parm_tree)
938                 && !gimple_default_def (DECL_STRUCT_FUNCTION (orig_node->decl),
939                                         parm_tree))
940               {
941                 bitmap_set_bit (args_to_skip, i);
942                 continue;
943               }
944
945             if (lat->type == IPA_CONST_VALUE)
946               bitmap_set_bit (args_to_skip, i);
947           }
948         for (cs = node->callers; cs; cs = next)
949           {
950             next = cs->next_caller;
951             if (!ipcp_node_is_clone (cs->caller) && ipcp_need_redirect_p (cs))
952               cgraph_redirect_edge_callee (cs, orig_node);
953           }
954       }
955 }
956
957 /* Update profiling info for versioned functions and the functions they were
958    versioned from.  */
959 static void
960 ipcp_update_profiling (void)
961 {
962   struct cgraph_node *node, *orig_node;
963   gcov_type scale, scale_complement;
964   struct cgraph_edge *cs;
965
966   for (node = cgraph_nodes; node; node = node->next)
967     {
968       if (ipcp_node_is_clone (node))
969         {
970           orig_node = ipcp_get_orig_node (node);
971           scale = ipcp_get_node_scale (orig_node);
972           node->count = orig_node->count * scale / REG_BR_PROB_BASE;
973           scale_complement = REG_BR_PROB_BASE - scale;
974           orig_node->count =
975             orig_node->count * scale_complement / REG_BR_PROB_BASE;
976           for (cs = node->callees; cs; cs = cs->next_callee)
977             cs->count = cs->count * scale / REG_BR_PROB_BASE;
978           for (cs = orig_node->callees; cs; cs = cs->next_callee)
979             cs->count = cs->count * scale_complement / REG_BR_PROB_BASE;
980         }
981     }
982 }
983
984 /* If NODE was cloned, how much would program grow? */
985 static long
986 ipcp_estimate_growth (struct cgraph_node *node)
987 {
988   struct cgraph_edge *cs;
989   int redirectable_node_callers = 0;
990   int removable_args = 0;
991   bool need_original = !cgraph_only_called_directly_p (node);
992   struct ipa_node_params *info;
993   int i, count;
994   int growth;
995
996   for (cs = node->callers; cs != NULL; cs = cs->next_caller)
997     if (cs->caller == node || !ipcp_need_redirect_p (cs))
998       redirectable_node_callers++;
999     else
1000       need_original = true;
1001
1002   /* If we will be able to fully replace orignal node, we never increase
1003      program size.  */
1004   if (!need_original)
1005     return 0;
1006
1007   info = IPA_NODE_REF (node);
1008   count = ipa_get_param_count (info);
1009   for (i = 0; i < count; i++)
1010     {
1011       struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
1012       tree parm_tree = ipa_get_param (info, i);
1013
1014       /* We can proactively remove obviously unused arguments.  */
1015       if (is_gimple_reg (parm_tree)
1016           && !gimple_default_def (DECL_STRUCT_FUNCTION (node->decl),
1017                                   parm_tree))
1018         removable_args++;
1019
1020       if (lat->type == IPA_CONST_VALUE)
1021         removable_args++;
1022     }
1023
1024   /* We make just very simple estimate of savings for removal of operand from
1025      call site.  Precise cost is dificult to get, as our size metric counts
1026      constants and moves as free.  Generally we are looking for cases that
1027      small function is called very many times.  */
1028   growth = node->local.inline_summary.self_size
1029            - removable_args * redirectable_node_callers;
1030   if (growth < 0)
1031     return 0;
1032   return growth;
1033 }
1034
1035
1036 /* Estimate cost of cloning NODE.  */
1037 static long
1038 ipcp_estimate_cloning_cost (struct cgraph_node *node)
1039 {
1040   int freq_sum = 1;
1041   gcov_type count_sum = 1;
1042   struct cgraph_edge *e;
1043   int cost;
1044
1045   cost = ipcp_estimate_growth (node) * 1000;
1046   if (!cost)
1047     {
1048       if (dump_file)
1049         fprintf (dump_file, "Versioning of %s will save code size\n",
1050                  cgraph_node_name (node));
1051       return 0;
1052     }
1053
1054   for (e = node->callers; e; e = e->next_caller)
1055     if (!bitmap_bit_p (dead_nodes, e->caller->uid)
1056         && !ipcp_need_redirect_p (e))
1057       {
1058         count_sum += e->count;
1059         freq_sum += e->frequency + 1;
1060       }
1061
1062   if (max_count)
1063     cost /= count_sum * 1000 / max_count + 1;
1064   else
1065     cost /= freq_sum * 1000 / REG_BR_PROB_BASE + 1;
1066   if (dump_file)
1067     fprintf (dump_file, "Cost of versioning %s is %i, (size: %i, freq: %i)\n",
1068              cgraph_node_name (node), cost, node->local.inline_summary.self_size,
1069              freq_sum);
1070   return cost + 1;
1071 }
1072
1073 /* Return number of live constant parameters.  */
1074 static int
1075 ipcp_const_param_count (struct cgraph_node *node)
1076 {
1077   int const_param = 0;
1078   struct ipa_node_params *info = IPA_NODE_REF (node);
1079   int count = ipa_get_param_count (info);
1080   int i;
1081
1082   for (i = 0; i < count; i++)
1083     {
1084       struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
1085       tree parm_tree = ipa_get_param (info, i);
1086       if (ipcp_lat_is_insertable (lat)
1087           /* Do not count obviously unused arguments.  */
1088           && (!is_gimple_reg (parm_tree)
1089               || gimple_default_def (DECL_STRUCT_FUNCTION (node->decl),
1090                                      parm_tree)))
1091         const_param++;
1092     }
1093   return const_param;
1094 }
1095
1096 /* Propagate the constant parameters found by ipcp_iterate_stage()
1097    to the function's code.  */
1098 static void
1099 ipcp_insert_stage (void)
1100 {
1101   struct cgraph_node *node, *node1 = NULL;
1102   int i;
1103   VEC (cgraph_edge_p, heap) * redirect_callers;
1104   VEC (ipa_replace_map_p,gc)* replace_trees;
1105   int node_callers, count;
1106   tree parm_tree;
1107   struct ipa_replace_map *replace_param;
1108   fibheap_t heap;
1109   long overall_size = 0, new_size = 0;
1110   long max_new_size;
1111
1112   ipa_check_create_node_params ();
1113   ipa_check_create_edge_args ();
1114   if (dump_file)
1115     fprintf (dump_file, "\nIPA insert stage:\n\n");
1116
1117   dead_nodes = BITMAP_ALLOC (NULL);
1118
1119   for (node = cgraph_nodes; node; node = node->next)
1120     if (node->analyzed)
1121       {
1122         if (node->count > max_count)
1123           max_count = node->count;
1124         overall_size += node->local.inline_summary.self_size;
1125       }
1126
1127   max_new_size = overall_size;
1128   if (max_new_size < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
1129     max_new_size = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
1130   max_new_size = max_new_size * PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH) / 100 + 1;
1131
1132   /* First collect all functions we proved to have constant arguments to heap.  */
1133   heap = fibheap_new ();
1134   for (node = cgraph_nodes; node; node = node->next)
1135     {
1136       struct ipa_node_params *info;
1137       /* Propagation of the constant is forbidden in certain conditions.  */
1138       if (!node->analyzed || !ipcp_node_modifiable_p (node))
1139           continue;
1140       info = IPA_NODE_REF (node);
1141       if (ipa_is_called_with_var_arguments (info))
1142         continue;
1143       if (ipcp_const_param_count (node))
1144         node->aux = fibheap_insert (heap, ipcp_estimate_cloning_cost (node), node);
1145      }
1146
1147   /* Now clone in priority order until code size growth limits are met or
1148      heap is emptied.  */
1149   while (!fibheap_empty (heap))
1150     {
1151       struct ipa_node_params *info;
1152       int growth = 0;
1153       bitmap args_to_skip;
1154       struct cgraph_edge *cs;
1155
1156       node = (struct cgraph_node *)fibheap_extract_min (heap);
1157       node->aux = NULL;
1158       if (dump_file)
1159         fprintf (dump_file, "considering function %s\n",
1160                  cgraph_node_name (node));
1161
1162       growth = ipcp_estimate_growth (node);
1163
1164       if (new_size + growth > max_new_size)
1165         break;
1166       if (growth
1167           && optimize_function_for_size_p (DECL_STRUCT_FUNCTION (node->decl)))
1168         {
1169           if (dump_file)
1170             fprintf (dump_file, "Not versioning, cold code would grow");
1171           continue;
1172         }
1173
1174       new_size += growth;
1175
1176       /* Look if original function becomes dead after clonning.  */
1177       for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1178         if (cs->caller == node || ipcp_need_redirect_p (cs))
1179           break;
1180       if (!cs && cgraph_only_called_directly_p (node))
1181         bitmap_set_bit (dead_nodes, node->uid);
1182
1183       info = IPA_NODE_REF (node);
1184       count = ipa_get_param_count (info);
1185
1186       replace_trees = VEC_alloc (ipa_replace_map_p, gc, 1);
1187       args_to_skip = BITMAP_GGC_ALLOC ();
1188       for (i = 0; i < count; i++)
1189         {
1190           struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
1191           parm_tree = ipa_get_param (info, i);
1192
1193           /* We can proactively remove obviously unused arguments.  */
1194           if (is_gimple_reg (parm_tree)
1195               && !gimple_default_def (DECL_STRUCT_FUNCTION (node->decl),
1196                                       parm_tree))
1197             {
1198               bitmap_set_bit (args_to_skip, i);
1199               continue;
1200             }
1201
1202           if (lat->type == IPA_CONST_VALUE)
1203             {
1204               replace_param =
1205                 ipcp_create_replace_map (parm_tree, lat);
1206               VEC_safe_push (ipa_replace_map_p, gc, replace_trees, replace_param);
1207               bitmap_set_bit (args_to_skip, i);
1208             }
1209         }
1210
1211       /* Compute how many callers node has.  */
1212       node_callers = 0;
1213       for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1214         node_callers++;
1215       redirect_callers = VEC_alloc (cgraph_edge_p, heap, node_callers);
1216       for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1217         VEC_quick_push (cgraph_edge_p, redirect_callers, cs);
1218
1219       /* Redirecting all the callers of the node to the
1220          new versioned node.  */
1221       node1 =
1222         cgraph_create_virtual_clone (node, redirect_callers, replace_trees,
1223                                      args_to_skip);
1224       args_to_skip = NULL;
1225       VEC_free (cgraph_edge_p, heap, redirect_callers);
1226       replace_trees = NULL;
1227
1228       if (node1 == NULL)
1229         continue;
1230       if (dump_file)
1231         fprintf (dump_file, "versioned function %s with growth %i, overall %i\n",
1232                  cgraph_node_name (node), (int)growth, (int)new_size);
1233       ipcp_init_cloned_node (node, node1);
1234
1235       /* TODO: We can use indirect inlning info to produce new calls.  */
1236
1237       if (dump_file)
1238         dump_function_to_file (node1->decl, dump_file, dump_flags);
1239
1240       for (cs = node->callees; cs; cs = cs->next_callee)
1241         if (cs->callee->aux)
1242           {
1243             fibheap_delete_node (heap, (fibnode_t) cs->callee->aux);
1244             cs->callee->aux = fibheap_insert (heap,
1245                                               ipcp_estimate_cloning_cost (cs->callee),
1246                                               cs->callee);
1247           }
1248     }
1249
1250   while (!fibheap_empty (heap))
1251     {
1252       if (dump_file)
1253         fprintf (dump_file, "skipping function %s\n",
1254                  cgraph_node_name (node));
1255       node = (struct cgraph_node *) fibheap_extract_min (heap);
1256       node->aux = NULL;
1257     }
1258   fibheap_delete (heap);
1259   BITMAP_FREE (dead_nodes);
1260   ipcp_update_callgraph ();
1261   ipcp_update_profiling ();
1262 }
1263
1264 /* The IPCP driver.  */
1265 static unsigned int
1266 ipcp_driver (void)
1267 {
1268   cgraph_remove_unreachable_nodes (true,dump_file);
1269   if (dump_file)
1270     {
1271       fprintf (dump_file, "\nIPA structures before propagation:\n");
1272       if (dump_flags & TDF_DETAILS)
1273         ipa_print_all_params (dump_file);
1274       ipa_print_all_jump_functions (dump_file);
1275     }
1276   /* 2. Do the interprocedural propagation.  */
1277   ipcp_iterate_stage ();
1278   /* 3. Insert the constants found to the functions.  */
1279   ipcp_insert_stage ();
1280   if (dump_file && (dump_flags & TDF_DETAILS))
1281     {
1282       fprintf (dump_file, "\nProfiling info after insert stage:\n");
1283       ipcp_print_profile_data (dump_file);
1284     }
1285   /* Free all IPCP structures.  */
1286   ipa_free_all_structures_after_ipa_cp ();
1287   if (dump_file)
1288     fprintf (dump_file, "\nIPA constant propagation end\n");
1289   return 0;
1290 }
1291
1292 /* Note function body size.  */
1293 static void
1294 ipcp_generate_summary (void)
1295 {
1296   if (dump_file)
1297     fprintf (dump_file, "\nIPA constant propagation start:\n");
1298   ipa_check_create_node_params ();
1299   ipa_check_create_edge_args ();
1300   ipa_register_cgraph_hooks ();
1301   /* 1. Call the init stage to initialize
1302      the ipa_node_params and ipa_edge_args structures.  */
1303   ipcp_init_stage ();
1304 }
1305
1306 /* Write ipcp summary for nodes in SET.  */
1307 static void
1308 ipcp_write_summary (cgraph_node_set set,
1309                     varpool_node_set vset ATTRIBUTE_UNUSED)
1310 {
1311   ipa_prop_write_jump_functions (set);
1312 }
1313
1314 /* Read ipcp summary.  */
1315 static void
1316 ipcp_read_summary (void)
1317 {
1318   ipa_prop_read_jump_functions ();
1319 }
1320
1321 /* Gate for IPCP optimization.  */
1322 static bool
1323 cgraph_gate_cp (void)
1324 {
1325   return flag_ipa_cp;
1326 }
1327
1328 struct ipa_opt_pass_d pass_ipa_cp =
1329 {
1330  {
1331   IPA_PASS,
1332   "cp",                         /* name */
1333   cgraph_gate_cp,               /* gate */
1334   ipcp_driver,                  /* execute */
1335   NULL,                         /* sub */
1336   NULL,                         /* next */
1337   0,                            /* static_pass_number */
1338   TV_IPA_CONSTANT_PROP,         /* tv_id */
1339   0,                            /* properties_required */
1340   0,                            /* properties_provided */
1341   0,                            /* properties_destroyed */
1342   0,                            /* todo_flags_start */
1343   TODO_dump_cgraph | TODO_dump_func |
1344   TODO_remove_functions | TODO_ggc_collect /* todo_flags_finish */
1345  },
1346  ipcp_generate_summary,                 /* generate_summary */
1347  ipcp_write_summary,                    /* write_summary */
1348  ipcp_read_summary,                     /* read_summary */
1349  NULL,                                  /* write_optimization_summary */
1350  NULL,                                  /* read_optimization_summary */
1351  NULL,                                  /* stmt_fixup */
1352  0,                                     /* TODOs */
1353  NULL,                                  /* function_transform */
1354  NULL,                                  /* variable_transform */
1355 };