OSDN Git Service

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