OSDN Git Service

723de162b1f20f40eb78c0cef5eec29bda6f8eef
[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   struct cgraph_edge *edge;
420
421   /* There are a number of generic reasons functions cannot be versioned.  */
422   if (!node->local.versionable)
423     return false;
424
425   /* Removing arguments doesn't work if the function takes varargs
426      or use __builtin_apply_args. */
427   for (edge = node->callees; edge; edge = edge->next_callee)
428     {
429       tree t = edge->callee->decl;
430       if (DECL_BUILT_IN_CLASS (t) == BUILT_IN_NORMAL
431           && (DECL_FUNCTION_CODE (t) == BUILT_IN_APPLY_ARGS
432              || DECL_FUNCTION_CODE (t) == BUILT_IN_VA_START))
433         return false;
434     }
435
436   return true;
437 }
438
439 /* Return true if this NODE is viable candidate for cloning.  */
440 static bool
441 ipcp_cloning_candidate_p (struct cgraph_node *node)
442 {
443   int n_calls = 0;
444   int n_hot_calls = 0;
445   gcov_type direct_call_sum = 0;
446   struct cgraph_edge *e;
447
448   /* We never clone functions that are not visible from outside.
449      FIXME: in future we should clone such functions when they are called with
450      different constants, but current ipcp implementation is not good on this.
451      */
452   if (cgraph_only_called_directly_p (node) || !node->analyzed)
453     return false;
454
455   if (cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE)
456     {
457       if (dump_file)
458         fprintf (dump_file, "Not considering %s for cloning; body is overwrittable.\n",
459                  cgraph_node_name (node));
460       return false;
461     }
462   if (!ipcp_versionable_function_p (node))
463     {
464       if (dump_file)
465         fprintf (dump_file, "Not considering %s for cloning; body is not versionable.\n",
466                  cgraph_node_name (node));
467       return false;
468     }
469   for (e = node->callers; e; e = e->next_caller)
470     {
471       direct_call_sum += e->count;
472       n_calls ++;
473       if (cgraph_maybe_hot_edge_p (e))
474         n_hot_calls ++;
475     }
476
477   if (!n_calls)
478     {
479       if (dump_file)
480         fprintf (dump_file, "Not considering %s for cloning; no direct calls.\n",
481                  cgraph_node_name (node));
482       return false;
483     }
484   if (node->local.inline_summary.self_size < n_calls)
485     {
486       if (dump_file)
487         fprintf (dump_file, "Considering %s for cloning; code would shrink.\n",
488                  cgraph_node_name (node));
489       return true;
490     }
491
492   if (!flag_ipa_cp_clone)
493     {
494       if (dump_file)
495         fprintf (dump_file, "Not considering %s for cloning; -fipa-cp-clone disabled.\n",
496                  cgraph_node_name (node));
497       return false;
498     }
499
500   if (!optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node->decl)))
501     {
502       if (dump_file)
503         fprintf (dump_file, "Not considering %s for cloning; optimizing it for size.\n",
504                  cgraph_node_name (node));
505       return false;
506     }
507
508   /* When profile is available and function is hot, propagate into it even if
509      calls seems cold; constant propagation can improve function's speed
510      significandly.  */
511   if (max_count)
512     {
513       if (direct_call_sum > node->count * 90 / 100)
514         {
515           if (dump_file)
516             fprintf (dump_file, "Considering %s for cloning; usually called directly.\n",
517                      cgraph_node_name (node));
518           return true;
519         }
520     }
521   if (!n_hot_calls)
522     {
523       if (dump_file)
524         fprintf (dump_file, "Not considering %s for cloning; no hot calls.\n",
525                  cgraph_node_name (node));
526       return false;
527     }
528   if (dump_file)
529     fprintf (dump_file, "Considering %s for cloning.\n",
530              cgraph_node_name (node));
531   return true;
532 }
533
534 /* Initialize ipcp_lattices array.  The lattices corresponding to supported
535    types (integers, real types and Fortran constants defined as const_decls)
536    are initialized to IPA_TOP, the rest of them to IPA_BOTTOM.  */
537 static void
538 ipcp_initialize_node_lattices (struct cgraph_node *node)
539 {
540   int i;
541   struct ipa_node_params *info = IPA_NODE_REF (node);
542   enum ipa_lattice_type type;
543
544   if (ipa_is_called_with_var_arguments (info))
545     type = IPA_BOTTOM;
546   else if (cgraph_only_called_directly_p (node))
547     type = IPA_TOP;
548   /* When cloning is allowed, we can assume that externally visible functions
549      are not called.  We will compensate this by cloning later.  */
550   else if (ipcp_cloning_candidate_p (node))
551     type = IPA_TOP, n_cloning_candidates ++;
552   else
553     type = IPA_BOTTOM;
554
555   for (i = 0; i < ipa_get_param_count (info) ; i++)
556     ipcp_get_lattice (info, i)->type = type;
557 }
558
559 /* build INTEGER_CST tree with type TREE_TYPE and value according to LAT.
560    Return the tree.  */
561 static tree
562 build_const_val (struct ipcp_lattice *lat, tree tree_type)
563 {
564   tree val;
565
566   gcc_assert (ipcp_lat_is_const (lat));
567   val = lat->constant;
568
569   if (!useless_type_conversion_p (tree_type, TREE_TYPE (val)))
570     {
571       if (fold_convertible_p (tree_type, val))
572         return fold_build1 (NOP_EXPR, tree_type, val);
573       else
574         return fold_build1 (VIEW_CONVERT_EXPR, tree_type, val);
575     }
576   return val;
577 }
578
579 /* Compute the proper scale for NODE.  It is the ratio between the number of
580    direct calls (represented on the incoming cgraph_edges) and sum of all
581    invocations of NODE (represented as count in cgraph_node).
582
583    FIXME: This code is wrong.  Since the callers can be also clones and
584    the clones are not scaled yet, the sums gets unrealistically high.
585    To properly compute the counts, we would need to do propagation across
586    callgraph (as external call to A might imply call to non-clonned B
587    if A's clone calls clonned B).  */
588 static void
589 ipcp_compute_node_scale (struct cgraph_node *node)
590 {
591   gcov_type sum;
592   struct cgraph_edge *cs;
593
594   sum = 0;
595   /* Compute sum of all counts of callers. */
596   for (cs = node->callers; cs != NULL; cs = cs->next_caller)
597     sum += cs->count;
598   /* Work around the unrealistically high sum problem.  We just don't want
599      the non-cloned body to have negative or very low frequency.  Since
600      majority of execution time will be spent in clones anyway, this should
601      give good enough profile.  */
602   if (sum > node->count * 9 / 10)
603     sum = node->count * 9 / 10;
604   if (node->count == 0)
605     ipcp_set_node_scale (node, 0);
606   else
607     ipcp_set_node_scale (node, sum * REG_BR_PROB_BASE / node->count);
608 }
609
610 /* Initialization and computation of IPCP data structures.  This is the initial
611    intraprocedural analysis of functions, which gathers information to be
612    propagated later on.  */
613 static void
614 ipcp_init_stage (void)
615 {
616   struct cgraph_node *node;
617   struct cgraph_edge *cs;
618
619   for (node = cgraph_nodes; node; node = node->next)
620     if (node->analyzed)
621       ipcp_analyze_node (node);
622   for (node = cgraph_nodes; node; node = node->next)
623     {
624       if (!node->analyzed)
625         continue;
626       /* building jump functions  */
627       for (cs = node->callees; cs; cs = cs->next_callee)
628         {
629           /* We do not need to bother analyzing calls to unknown
630              functions unless they may become known during lto/whopr.  */
631           if (!cs->callee->analyzed && !flag_lto && !flag_whopr)
632             continue;
633           ipa_count_arguments (cs);
634           if (ipa_get_cs_argument_count (IPA_EDGE_REF (cs))
635               != ipa_get_param_count (IPA_NODE_REF (cs->callee)))
636             ipa_set_called_with_variable_arg (IPA_NODE_REF (cs->callee));
637           ipa_compute_jump_functions (cs);
638         }
639     }
640 }
641
642 /* Return true if there are some formal parameters whose value is IPA_TOP (in
643    the whole compilation unit).  Change their values to IPA_BOTTOM, since they
644    most probably get their values from outside of this compilation unit.  */
645 static bool
646 ipcp_change_tops_to_bottom (void)
647 {
648   int i, count;
649   struct cgraph_node *node;
650   bool prop_again;
651
652   prop_again = false;
653   for (node = cgraph_nodes; node; node = node->next)
654     {
655       struct ipa_node_params *info = IPA_NODE_REF (node);
656       count = ipa_get_param_count (info);
657       for (i = 0; i < count; i++)
658         {
659           struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
660           if (lat->type == IPA_TOP)
661             {
662               prop_again = true;
663               if (dump_file)
664                 {
665                   fprintf (dump_file, "Forcing param ");
666                   print_generic_expr (dump_file, ipa_get_param (info, i), 0);
667                   fprintf (dump_file, " of node %s to bottom.\n",
668                            cgraph_node_name (node));
669                 }
670               lat->type = IPA_BOTTOM;
671             }
672         }
673     }
674   return prop_again;
675 }
676
677 /* Interprocedural analysis. The algorithm propagates constants from the
678    caller's parameters to the callee's arguments.  */
679 static void
680 ipcp_propagate_stage (void)
681 {
682   int i;
683   struct ipcp_lattice inc_lat = { IPA_BOTTOM, NULL };
684   struct ipcp_lattice new_lat = { IPA_BOTTOM, NULL };
685   struct ipcp_lattice *dest_lat;
686   struct cgraph_edge *cs;
687   struct ipa_jump_func *jump_func;
688   struct ipa_func_list *wl;
689   int count;
690
691   ipa_check_create_node_params ();
692   ipa_check_create_edge_args ();
693
694   /* Initialize worklist to contain all functions.  */
695   wl = ipa_init_func_list ();
696   while (wl)
697     {
698       struct cgraph_node *node = ipa_pop_func_from_list (&wl);
699       struct ipa_node_params *info = IPA_NODE_REF (node);
700
701       for (cs = node->callees; cs; cs = cs->next_callee)
702         {
703           struct ipa_node_params *callee_info = IPA_NODE_REF (cs->callee);
704           struct ipa_edge_args *args = IPA_EDGE_REF (cs);
705
706           if (ipa_is_called_with_var_arguments (callee_info)
707               || !cs->callee->analyzed
708               || ipa_is_called_with_var_arguments (callee_info))
709             continue;
710
711           count = ipa_get_cs_argument_count (args);
712           for (i = 0; i < count; i++)
713             {
714               jump_func = ipa_get_ith_jump_func (args, i);
715               ipcp_lattice_from_jfunc (info, &inc_lat, jump_func);
716               dest_lat = ipcp_get_lattice (callee_info, i);
717               ipa_lattice_meet (&new_lat, &inc_lat, dest_lat);
718               if (ipcp_lattice_changed (&new_lat, dest_lat))
719                 {
720                   dest_lat->type = new_lat.type;
721                   dest_lat->constant = new_lat.constant;
722                   ipa_push_func_to_list (&wl, cs->callee);
723                 }
724             }
725         }
726     }
727 }
728
729 /* Call the constant propagation algorithm and re-call it if necessary
730    (if there are undetermined values left).  */
731 static void
732 ipcp_iterate_stage (void)
733 {
734   struct cgraph_node *node;
735   n_cloning_candidates = 0;
736
737   if (dump_file)
738     fprintf (dump_file, "\nIPA iterate stage:\n\n");
739
740   if (in_lto_p)
741     ipa_update_after_lto_read ();
742
743   for (node = cgraph_nodes; node; node = node->next)
744     {
745       ipcp_initialize_node_lattices (node);
746       ipcp_compute_node_scale (node);
747     }
748   if (dump_file && (dump_flags & TDF_DETAILS))
749     {
750       ipcp_print_all_lattices (dump_file);
751       ipcp_function_scale_print (dump_file);
752     }
753
754   ipcp_propagate_stage ();
755   if (ipcp_change_tops_to_bottom ())
756     /* Some lattices have changed from IPA_TOP to IPA_BOTTOM.
757        This change should be propagated.  */
758     {
759       gcc_assert (n_cloning_candidates);
760       ipcp_propagate_stage ();
761     }
762   if (dump_file)
763     {
764       fprintf (dump_file, "\nIPA lattices after propagation:\n");
765       ipcp_print_all_lattices (dump_file);
766       if (dump_flags & TDF_DETAILS)
767         ipcp_print_profile_data (dump_file);
768     }
769 }
770
771 /* Check conditions to forbid constant insertion to function described by
772    NODE.  */
773 static inline bool
774 ipcp_node_modifiable_p (struct cgraph_node *node)
775 {
776   /* Once we will be able to do in-place replacement, we can be more
777      lax here.  */
778   return ipcp_versionable_function_p (node);
779 }
780
781 /* Print count scale data structures.  */
782 static void
783 ipcp_function_scale_print (FILE * f)
784 {
785   struct cgraph_node *node;
786
787   for (node = cgraph_nodes; node; node = node->next)
788     {
789       if (!node->analyzed)
790         continue;
791       fprintf (f, "printing scale for %s: ", cgraph_node_name (node));
792       fprintf (f, "value is  " HOST_WIDE_INT_PRINT_DEC
793                "  \n", (HOST_WIDE_INT) ipcp_get_node_scale (node));
794     }
795 }
796
797 /* Print counts of all cgraph nodes.  */
798 static void
799 ipcp_print_func_profile_counts (FILE * f)
800 {
801   struct cgraph_node *node;
802
803   for (node = cgraph_nodes; node; node = node->next)
804     {
805       fprintf (f, "function %s: ", cgraph_node_name (node));
806       fprintf (f, "count is  " HOST_WIDE_INT_PRINT_DEC
807                "  \n", (HOST_WIDE_INT) node->count);
808     }
809 }
810
811 /* Print counts of all cgraph edges.  */
812 static void
813 ipcp_print_call_profile_counts (FILE * f)
814 {
815   struct cgraph_node *node;
816   struct cgraph_edge *cs;
817
818   for (node = cgraph_nodes; node; node = node->next)
819     {
820       for (cs = node->callees; cs; cs = cs->next_callee)
821         {
822           fprintf (f, "%s -> %s ", cgraph_node_name (cs->caller),
823                    cgraph_node_name (cs->callee));
824           fprintf (f, "count is  " HOST_WIDE_INT_PRINT_DEC "  \n",
825                    (HOST_WIDE_INT) cs->count);
826         }
827     }
828 }
829
830 /* Print profile info for all functions.  */
831 static void
832 ipcp_print_profile_data (FILE * f)
833 {
834   fprintf (f, "\nNODE COUNTS :\n");
835   ipcp_print_func_profile_counts (f);
836   fprintf (f, "\nCS COUNTS stage:\n");
837   ipcp_print_call_profile_counts (f);
838 }
839
840 /* Build and initialize ipa_replace_map struct according to LAT. This struct is
841    processed by versioning, which operates according to the flags set.
842    PARM_TREE is the formal parameter found to be constant.  LAT represents the
843    constant.  */
844 static struct ipa_replace_map *
845 ipcp_create_replace_map (tree parm_tree, struct ipcp_lattice *lat)
846 {
847   struct ipa_replace_map *replace_map;
848   tree const_val;
849
850   replace_map = GGC_NEW (struct ipa_replace_map);
851   const_val = build_const_val (lat, TREE_TYPE (parm_tree));
852   if (dump_file)
853     {
854       fprintf (dump_file, "  replacing param ");
855       print_generic_expr (dump_file, parm_tree, 0);
856       fprintf (dump_file, " with const ");
857       print_generic_expr (dump_file, const_val, 0);
858       fprintf (dump_file, "\n");
859     }
860   replace_map->old_tree = parm_tree;
861   replace_map->new_tree = const_val;
862   replace_map->replace_p = true;
863   replace_map->ref_p = false;
864
865   return replace_map;
866 }
867
868 /* Return true if this callsite should be redirected to the original callee
869    (instead of the cloned one).  */
870 static bool
871 ipcp_need_redirect_p (struct cgraph_edge *cs)
872 {
873   struct ipa_node_params *orig_callee_info;
874   int i, count;
875   struct ipa_jump_func *jump_func;
876   struct cgraph_node *node = cs->callee, *orig;
877
878   if (!n_cloning_candidates)
879     return false;
880
881   if ((orig = ipcp_get_orig_node (node)) != NULL)
882     node = orig;
883   if (ipcp_get_orig_node (cs->caller))
884     return false;
885
886   orig_callee_info = IPA_NODE_REF (node);
887   count = ipa_get_param_count (orig_callee_info);
888   for (i = 0; i < count; i++)
889     {
890       struct ipcp_lattice *lat = ipcp_get_lattice (orig_callee_info, i);
891       if (ipcp_lat_is_const (lat))
892         {
893           jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
894           if (jump_func->type != IPA_JF_CONST)
895             return true;
896         }
897     }
898
899   return false;
900 }
901
902 /* Fix the callsites and the call graph after function cloning was done.  */
903 static void
904 ipcp_update_callgraph (void)
905 {
906   struct cgraph_node *node;
907
908   for (node = cgraph_nodes; node; node = node->next)
909     if (node->analyzed && ipcp_node_is_clone (node))
910       {
911         bitmap args_to_skip = BITMAP_ALLOC (NULL);
912         struct cgraph_node *orig_node = ipcp_get_orig_node (node);
913         struct ipa_node_params *info = IPA_NODE_REF (orig_node);
914         int i, count = ipa_get_param_count (info);
915         struct cgraph_edge *cs, *next;
916
917         for (i = 0; i < count; i++)
918           {
919             struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
920             tree parm_tree = ipa_get_param (info, i);
921
922             /* We can proactively remove obviously unused arguments.  */
923             if (is_gimple_reg (parm_tree)
924                 && !gimple_default_def (DECL_STRUCT_FUNCTION (orig_node->decl),
925                                         parm_tree))
926               {
927                 bitmap_set_bit (args_to_skip, i);
928                 continue;
929               }
930
931             if (lat->type == IPA_CONST_VALUE)
932               bitmap_set_bit (args_to_skip, i);
933           }
934         for (cs = node->callers; cs; cs = next)
935           {
936             next = cs->next_caller;
937             if (!ipcp_node_is_clone (cs->caller) && ipcp_need_redirect_p (cs))
938               cgraph_redirect_edge_callee (cs, orig_node);
939           }
940       }
941 }
942
943 /* Update profiling info for versioned functions and the functions they were
944    versioned from.  */
945 static void
946 ipcp_update_profiling (void)
947 {
948   struct cgraph_node *node, *orig_node;
949   gcov_type scale, scale_complement;
950   struct cgraph_edge *cs;
951
952   for (node = cgraph_nodes; node; node = node->next)
953     {
954       if (ipcp_node_is_clone (node))
955         {
956           orig_node = ipcp_get_orig_node (node);
957           scale = ipcp_get_node_scale (orig_node);
958           node->count = orig_node->count * scale / REG_BR_PROB_BASE;
959           scale_complement = REG_BR_PROB_BASE - scale;
960           orig_node->count =
961             orig_node->count * scale_complement / REG_BR_PROB_BASE;
962           for (cs = node->callees; cs; cs = cs->next_callee)
963             cs->count = cs->count * scale / REG_BR_PROB_BASE;
964           for (cs = orig_node->callees; cs; cs = cs->next_callee)
965             cs->count = cs->count * scale_complement / REG_BR_PROB_BASE;
966         }
967     }
968 }
969
970 /* If NODE was cloned, how much would program grow? */
971 static long
972 ipcp_estimate_growth (struct cgraph_node *node)
973 {
974   struct cgraph_edge *cs;
975   int redirectable_node_callers = 0;
976   int removable_args = 0;
977   bool need_original = !cgraph_only_called_directly_p (node);
978   struct ipa_node_params *info;
979   int i, count;
980   int growth;
981
982   for (cs = node->callers; cs != NULL; cs = cs->next_caller)
983     if (cs->caller == node || !ipcp_need_redirect_p (cs))
984       redirectable_node_callers++;
985     else
986       need_original = true;
987
988   /* If we will be able to fully replace orignal node, we never increase
989      program size.  */
990   if (!need_original)
991     return 0;
992
993   info = IPA_NODE_REF (node);
994   count = ipa_get_param_count (info);
995   for (i = 0; i < count; i++)
996     {
997       struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
998       tree parm_tree = ipa_get_param (info, i);
999
1000       /* We can proactively remove obviously unused arguments.  */
1001       if (is_gimple_reg (parm_tree)
1002           && !gimple_default_def (DECL_STRUCT_FUNCTION (node->decl),
1003                                   parm_tree))
1004         removable_args++;
1005
1006       if (lat->type == IPA_CONST_VALUE)
1007         removable_args++;
1008     }
1009
1010   /* We make just very simple estimate of savings for removal of operand from
1011      call site.  Precise cost is dificult to get, as our size metric counts
1012      constants and moves as free.  Generally we are looking for cases that
1013      small function is called very many times.  */
1014   growth = node->local.inline_summary.self_size
1015            - removable_args * redirectable_node_callers;
1016   if (growth < 0)
1017     return 0;
1018   return growth;
1019 }
1020
1021
1022 /* Estimate cost of cloning NODE.  */
1023 static long
1024 ipcp_estimate_cloning_cost (struct cgraph_node *node)
1025 {
1026   int freq_sum = 1;
1027   gcov_type count_sum = 1;
1028   struct cgraph_edge *e;
1029   int cost;
1030
1031   cost = ipcp_estimate_growth (node) * 1000;
1032   if (!cost)
1033     {
1034       if (dump_file)
1035         fprintf (dump_file, "Versioning of %s will save code size\n",
1036                  cgraph_node_name (node));
1037       return 0;
1038     }
1039
1040   for (e = node->callers; e; e = e->next_caller)
1041     if (!bitmap_bit_p (dead_nodes, e->caller->uid)
1042         && !ipcp_need_redirect_p (e))
1043       {
1044         count_sum += e->count;
1045         freq_sum += e->frequency + 1;
1046       }
1047
1048   if (max_count)
1049     cost /= count_sum * 1000 / max_count + 1;
1050   else
1051     cost /= freq_sum * 1000 / REG_BR_PROB_BASE + 1;
1052   if (dump_file)
1053     fprintf (dump_file, "Cost of versioning %s is %i, (size: %i, freq: %i)\n",
1054              cgraph_node_name (node), cost, node->local.inline_summary.self_size,
1055              freq_sum);
1056   return cost + 1;
1057 }
1058
1059 /* Return number of live constant parameters.  */
1060 static int
1061 ipcp_const_param_count (struct cgraph_node *node)
1062 {
1063   int const_param = 0;
1064   struct ipa_node_params *info = IPA_NODE_REF (node);
1065   int count = ipa_get_param_count (info);
1066   int i;
1067
1068   for (i = 0; i < count; i++)
1069     {
1070       struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
1071       tree parm_tree = ipa_get_param (info, i);
1072       if (ipcp_lat_is_insertable (lat)
1073           /* Do not count obviously unused arguments.  */
1074           && (!is_gimple_reg (parm_tree)
1075               || gimple_default_def (DECL_STRUCT_FUNCTION (node->decl),
1076                                      parm_tree)))
1077         const_param++;
1078     }
1079   return const_param;
1080 }
1081
1082 /* Propagate the constant parameters found by ipcp_iterate_stage()
1083    to the function's code.  */
1084 static void
1085 ipcp_insert_stage (void)
1086 {
1087   struct cgraph_node *node, *node1 = NULL;
1088   int i;
1089   VEC (cgraph_edge_p, heap) * redirect_callers;
1090   VEC (ipa_replace_map_p,gc)* replace_trees;
1091   int node_callers, count;
1092   tree parm_tree;
1093   struct ipa_replace_map *replace_param;
1094   fibheap_t heap;
1095   long overall_size = 0, new_size = 0;
1096   long max_new_size;
1097
1098   ipa_check_create_node_params ();
1099   ipa_check_create_edge_args ();
1100   if (dump_file)
1101     fprintf (dump_file, "\nIPA insert stage:\n\n");
1102
1103   dead_nodes = BITMAP_ALLOC (NULL);
1104
1105   for (node = cgraph_nodes; node; node = node->next)
1106     if (node->analyzed)
1107       {
1108         if (node->count > max_count)
1109           max_count = node->count;
1110         overall_size += node->local.inline_summary.self_size;
1111       }
1112
1113   max_new_size = overall_size;
1114   if (max_new_size < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
1115     max_new_size = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
1116   max_new_size = max_new_size * PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH) / 100 + 1;
1117
1118   /* First collect all functions we proved to have constant arguments to heap.  */
1119   heap = fibheap_new ();
1120   for (node = cgraph_nodes; node; node = node->next)
1121     {
1122       struct ipa_node_params *info;
1123       /* Propagation of the constant is forbidden in certain conditions.  */
1124       if (!node->analyzed || !ipcp_node_modifiable_p (node))
1125           continue;
1126       info = IPA_NODE_REF (node);
1127       if (ipa_is_called_with_var_arguments (info))
1128         continue;
1129       if (ipcp_const_param_count (node))
1130         node->aux = fibheap_insert (heap, ipcp_estimate_cloning_cost (node), node);
1131      }
1132
1133   /* Now clone in priority order until code size growth limits are met or
1134      heap is emptied.  */
1135   while (!fibheap_empty (heap))
1136     {
1137       struct ipa_node_params *info;
1138       int growth = 0;
1139       bitmap args_to_skip;
1140       struct cgraph_edge *cs;
1141
1142       node = (struct cgraph_node *)fibheap_extract_min (heap);
1143       node->aux = NULL;
1144       if (dump_file)
1145         fprintf (dump_file, "considering function %s\n",
1146                  cgraph_node_name (node));
1147
1148       growth = ipcp_estimate_growth (node);
1149
1150       if (new_size + growth > max_new_size)
1151         break;
1152       if (growth
1153           && optimize_function_for_size_p (DECL_STRUCT_FUNCTION (node->decl)))
1154         {
1155           if (dump_file)
1156             fprintf (dump_file, "Not versioning, cold code would grow");
1157           continue;
1158         }
1159
1160       new_size += growth;
1161
1162       /* Look if original function becomes dead after clonning.  */
1163       for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1164         if (cs->caller == node || ipcp_need_redirect_p (cs))
1165           break;
1166       if (!cs && cgraph_only_called_directly_p (node))
1167         bitmap_set_bit (dead_nodes, node->uid);
1168
1169       info = IPA_NODE_REF (node);
1170       count = ipa_get_param_count (info);
1171
1172       replace_trees = VEC_alloc (ipa_replace_map_p, gc, 1);
1173       args_to_skip = BITMAP_GGC_ALLOC ();
1174       for (i = 0; i < count; i++)
1175         {
1176           struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
1177           parm_tree = ipa_get_param (info, i);
1178
1179           /* We can proactively remove obviously unused arguments.  */
1180           if (is_gimple_reg (parm_tree)
1181               && !gimple_default_def (DECL_STRUCT_FUNCTION (node->decl),
1182                                       parm_tree))
1183             {
1184               bitmap_set_bit (args_to_skip, i);
1185               continue;
1186             }
1187
1188           if (lat->type == IPA_CONST_VALUE)
1189             {
1190               replace_param =
1191                 ipcp_create_replace_map (parm_tree, lat);
1192               VEC_safe_push (ipa_replace_map_p, gc, replace_trees, replace_param);
1193               bitmap_set_bit (args_to_skip, i);
1194             }
1195         }
1196
1197       /* Compute how many callers node has.  */
1198       node_callers = 0;
1199       for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1200         node_callers++;
1201       redirect_callers = VEC_alloc (cgraph_edge_p, heap, node_callers);
1202       for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1203         VEC_quick_push (cgraph_edge_p, redirect_callers, cs);
1204
1205       /* Redirecting all the callers of the node to the
1206          new versioned node.  */
1207       node1 =
1208         cgraph_create_virtual_clone (node, redirect_callers, replace_trees,
1209                                      args_to_skip);
1210       args_to_skip = NULL;
1211       VEC_free (cgraph_edge_p, heap, redirect_callers);
1212       replace_trees = NULL;
1213
1214       if (node1 == NULL)
1215         continue;
1216       if (dump_file)
1217         fprintf (dump_file, "versioned function %s with growth %i, overall %i\n",
1218                  cgraph_node_name (node), (int)growth, (int)new_size);
1219       ipcp_init_cloned_node (node, node1);
1220
1221       /* TODO: We can use indirect inlning info to produce new calls.  */
1222
1223       if (dump_file)
1224         dump_function_to_file (node1->decl, dump_file, dump_flags);
1225
1226       for (cs = node->callees; cs; cs = cs->next_callee)
1227         if (cs->callee->aux)
1228           {
1229             fibheap_delete_node (heap, (fibnode_t) cs->callee->aux);
1230             cs->callee->aux = fibheap_insert (heap,
1231                                               ipcp_estimate_cloning_cost (cs->callee),
1232                                               cs->callee);
1233           }
1234     }
1235
1236   while (!fibheap_empty (heap))
1237     {
1238       if (dump_file)
1239         fprintf (dump_file, "skipping function %s\n",
1240                  cgraph_node_name (node));
1241       node = (struct cgraph_node *) fibheap_extract_min (heap);
1242       node->aux = NULL;
1243     }
1244   fibheap_delete (heap);
1245   BITMAP_FREE (dead_nodes);
1246   ipcp_update_callgraph ();
1247   ipcp_update_profiling ();
1248 }
1249
1250 /* The IPCP driver.  */
1251 static unsigned int
1252 ipcp_driver (void)
1253 {
1254   cgraph_remove_unreachable_nodes (true,dump_file);
1255   if (dump_file)
1256     {
1257       fprintf (dump_file, "\nIPA structures before propagation:\n");
1258       if (dump_flags & TDF_DETAILS)
1259         ipa_print_all_params (dump_file);
1260       ipa_print_all_jump_functions (dump_file);
1261     }
1262   /* 2. Do the interprocedural propagation.  */
1263   ipcp_iterate_stage ();
1264   /* 3. Insert the constants found to the functions.  */
1265   ipcp_insert_stage ();
1266   if (dump_file && (dump_flags & TDF_DETAILS))
1267     {
1268       fprintf (dump_file, "\nProfiling info after insert stage:\n");
1269       ipcp_print_profile_data (dump_file);
1270     }
1271   /* Free all IPCP structures.  */
1272   ipa_free_all_structures_after_ipa_cp ();
1273   if (dump_file)
1274     fprintf (dump_file, "\nIPA constant propagation end\n");
1275   return 0;
1276 }
1277
1278 /* Note function body size.  */
1279 static void
1280 ipcp_generate_summary (void)
1281 {
1282   if (dump_file)
1283     fprintf (dump_file, "\nIPA constant propagation start:\n");
1284   ipa_check_create_node_params ();
1285   ipa_check_create_edge_args ();
1286   ipa_register_cgraph_hooks ();
1287   /* 1. Call the init stage to initialize
1288      the ipa_node_params and ipa_edge_args structures.  */
1289   ipcp_init_stage ();
1290 }
1291
1292 /* Write ipcp summary for nodes in SET.  */
1293 static void
1294 ipcp_write_summary (cgraph_node_set set,
1295                     varpool_node_set vset ATTRIBUTE_UNUSED)
1296 {
1297   ipa_prop_write_jump_functions (set);
1298 }
1299
1300 /* Read ipcp summary.  */
1301 static void
1302 ipcp_read_summary (void)
1303 {
1304   ipa_prop_read_jump_functions ();
1305 }
1306
1307 /* Gate for IPCP optimization.  */
1308 static bool
1309 cgraph_gate_cp (void)
1310 {
1311   return flag_ipa_cp;
1312 }
1313
1314 struct ipa_opt_pass_d pass_ipa_cp =
1315 {
1316  {
1317   IPA_PASS,
1318   "cp",                         /* name */
1319   cgraph_gate_cp,               /* gate */
1320   ipcp_driver,                  /* execute */
1321   NULL,                         /* sub */
1322   NULL,                         /* next */
1323   0,                            /* static_pass_number */
1324   TV_IPA_CONSTANT_PROP,         /* tv_id */
1325   0,                            /* properties_required */
1326   0,                            /* properties_provided */
1327   0,                            /* properties_destroyed */
1328   0,                            /* todo_flags_start */
1329   TODO_dump_cgraph | TODO_dump_func |
1330   TODO_remove_functions | TODO_ggc_collect /* todo_flags_finish */
1331  },
1332  ipcp_generate_summary,                 /* generate_summary */
1333  ipcp_write_summary,                    /* write_summary */
1334  ipcp_read_summary,                     /* read_summary */
1335  NULL,                                  /* write_optimization_summary */
1336  NULL,                                  /* read_optimization_summary */
1337  NULL,                                  /* stmt_fixup */
1338  0,                                     /* TODOs */
1339  NULL,                                  /* function_transform */
1340  NULL,                                  /* variable_transform */
1341 };