* xcoffout.h (xcoffout_source_line): Update prototype.
[official-gcc.git] / gcc / ipa-cp.c
blob581a88a1b6ca9b686716faa39e7d6864e8e8a76b
1 /* Interprocedural constant propagation
2 Copyright (C) 2005, 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
3 Contributed by Razya Ladelsky <RAZYA@il.ibm.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* Interprocedural constant propagation. The aim of interprocedural constant
22 propagation (IPCP) is to find which function's argument has the same
23 constant value in each invocation throughout the whole program. For example,
24 consider the following program:
26 int g (int y)
28 printf ("value is %d",y);
31 int f (int x)
33 g (x);
36 int h (int y)
38 g (y);
41 void main (void)
43 f (3);
44 h (3);
48 The IPCP algorithm will find that g's formal argument y is always called
49 with the value 3.
51 The algorithm used is based on "Interprocedural Constant Propagation", by
52 Challahan David, Keith D Cooper, Ken Kennedy, Linda Torczon, Comp86, pg
53 152-161
55 The optimization is divided into three stages:
57 First stage - intraprocedural analysis
58 =======================================
59 This phase computes jump_function and modification flags.
61 A jump function for a callsite represents the values passed as an actual
62 arguments of a given callsite. There are three types of values:
63 Pass through - the caller's formal parameter is passed as an actual argument.
64 Constant - a constant is passed as an actual argument.
65 Unknown - neither of the above.
67 The jump function info, ipa_jump_func, is stored in ipa_edge_args
68 structure (defined in ipa_prop.h and pointed to by cgraph_node->aux)
69 modified_flags are defined in ipa_node_params structure
70 (defined in ipa_prop.h and pointed to by cgraph_edge->aux).
72 -ipcp_init_stage() is the first stage driver.
74 Second stage - interprocedural analysis
75 ========================================
76 This phase does the interprocedural constant propagation.
77 It computes lattices for all formal parameters in the program
78 and their value that may be:
79 TOP - unknown.
80 BOTTOM - non constant.
81 CONSTANT - constant value.
83 Lattice describing a formal parameter p will have a constant value if all
84 callsites invoking this function have the same constant value passed to p.
86 The lattices are stored in ipcp_lattice which is itself in ipa_node_params
87 structure (defined in ipa_prop.h and pointed to by cgraph_edge->aux).
89 -ipcp_iterate_stage() is the second stage driver.
91 Third phase - transformation of function code
92 ============================================
93 Propagates the constant-valued formals into the function.
94 For each function whose parameters are constants, we create its clone.
96 Then we process the clone in two ways:
97 1. We insert an assignment statement 'parameter = const' at the beginning
98 of the cloned function.
99 2. For read-only parameters that do not live in memory, we replace all their
100 uses with the constant.
102 We also need to modify some callsites to call the cloned functions instead
103 of the original ones. For a callsite passing an argument found to be a
104 constant by IPCP, there are two different cases to handle:
105 1. A constant is passed as an argument. In this case the callsite in the
106 should be redirected to call the cloned callee.
107 2. A parameter (of the caller) passed as an argument (pass through
108 argument). In such cases both the caller and the callee have clones and
109 only the callsite in the cloned caller is redirected to call to the
110 cloned callee.
112 This update is done in two steps: First all cloned functions are created
113 during a traversal of the call graph, during which all callsites are
114 redirected to call the cloned function. Then the callsites are traversed
115 and many calls redirected back to fit the description above.
117 -ipcp_insert_stage() is the third phase driver.
121 #include "config.h"
122 #include "system.h"
123 #include "coretypes.h"
124 #include "tree.h"
125 #include "target.h"
126 #include "cgraph.h"
127 #include "ipa-prop.h"
128 #include "tree-flow.h"
129 #include "tree-pass.h"
130 #include "flags.h"
131 #include "timevar.h"
132 #include "diagnostic.h"
133 #include "tree-dump.h"
134 #include "tree-inline.h"
135 #include "fibheap.h"
136 #include "params.h"
138 /* Number of functions identified as candidates for cloning. When not cloning
139 we can simplify iterate stage not forcing it to go through the decision
140 on what is profitable and what not. */
141 static int n_cloning_candidates;
143 /* Maximal count found in program. */
144 static gcov_type max_count;
146 /* Cgraph nodes that has been completely replaced by cloning during iterate
147 * stage and will be removed after ipcp is finished. */
148 static bitmap dead_nodes;
150 static void ipcp_print_profile_data (FILE *);
151 static void ipcp_function_scale_print (FILE *);
153 /* Get the original node field of ipa_node_params associated with node NODE. */
154 static inline struct cgraph_node *
155 ipcp_get_orig_node (struct cgraph_node *node)
157 return IPA_NODE_REF (node)->ipcp_orig_node;
160 /* Return true if NODE describes a cloned/versioned function. */
161 static inline bool
162 ipcp_node_is_clone (struct cgraph_node *node)
164 return (ipcp_get_orig_node (node) != NULL);
167 /* Create ipa_node_params and its data structures for NEW_NODE. Set ORIG_NODE
168 as the ipcp_orig_node field in ipa_node_params. */
169 static void
170 ipcp_init_cloned_node (struct cgraph_node *orig_node,
171 struct cgraph_node *new_node)
173 ipa_check_create_node_params ();
174 ipa_initialize_node_params (new_node);
175 IPA_NODE_REF (new_node)->ipcp_orig_node = orig_node;
178 /* Perform intraprocedrual analysis needed for ipcp. */
179 static void
180 ipcp_analyze_node (struct cgraph_node *node)
182 /* Unreachable nodes should have been eliminated before ipcp. */
183 gcc_assert (node->needed || node->reachable);
185 ipa_initialize_node_params (node);
186 ipa_detect_param_modifications (node);
189 /* Return scale for NODE. */
190 static inline gcov_type
191 ipcp_get_node_scale (struct cgraph_node *node)
193 return IPA_NODE_REF (node)->count_scale;
196 /* Set COUNT as scale for NODE. */
197 static inline void
198 ipcp_set_node_scale (struct cgraph_node *node, gcov_type count)
200 IPA_NODE_REF (node)->count_scale = count;
203 /* Return whether LAT is a constant lattice. */
204 static inline bool
205 ipcp_lat_is_const (struct ipcp_lattice *lat)
207 if (lat->type == IPA_CONST_VALUE)
208 return true;
209 else
210 return false;
213 /* Return whether LAT is a constant lattice that ipa-cp can actually insert
214 into the code (i.e. constants excluding member pointers and pointers). */
215 static inline bool
216 ipcp_lat_is_insertable (struct ipcp_lattice *lat)
218 return lat->type == IPA_CONST_VALUE;
221 /* Return true if LAT1 and LAT2 are equal. */
222 static inline bool
223 ipcp_lats_are_equal (struct ipcp_lattice *lat1, struct ipcp_lattice *lat2)
225 gcc_assert (ipcp_lat_is_const (lat1) && ipcp_lat_is_const (lat2));
226 if (lat1->type != lat2->type)
227 return false;
229 if (operand_equal_p (lat1->constant, lat2->constant, 0))
230 return true;
232 return false;
235 /* Compute Meet arithmetics:
236 Meet (IPA_BOTTOM, x) = IPA_BOTTOM
237 Meet (IPA_TOP,x) = x
238 Meet (const_a,const_b) = IPA_BOTTOM, if const_a != const_b.
239 MEET (const_a,const_b) = const_a, if const_a == const_b.*/
240 static void
241 ipa_lattice_meet (struct ipcp_lattice *res, struct ipcp_lattice *lat1,
242 struct ipcp_lattice *lat2)
244 if (lat1->type == IPA_BOTTOM || lat2->type == IPA_BOTTOM)
246 res->type = IPA_BOTTOM;
247 return;
249 if (lat1->type == IPA_TOP)
251 res->type = lat2->type;
252 res->constant = lat2->constant;
253 return;
255 if (lat2->type == IPA_TOP)
257 res->type = lat1->type;
258 res->constant = lat1->constant;
259 return;
261 if (!ipcp_lats_are_equal (lat1, lat2))
263 res->type = IPA_BOTTOM;
264 return;
266 res->type = lat1->type;
267 res->constant = lat1->constant;
270 /* Return the lattice corresponding to the Ith formal parameter of the function
271 described by INFO. */
272 static inline struct ipcp_lattice *
273 ipcp_get_lattice (struct ipa_node_params *info, int i)
275 return &(info->params[i].ipcp_lattice);
278 /* Given the jump function JFUNC, compute the lattice LAT that describes the
279 value coming down the callsite. INFO describes the caller node so that
280 pass-through jump functions can be evaluated. */
281 static void
282 ipcp_lattice_from_jfunc (struct ipa_node_params *info, struct ipcp_lattice *lat,
283 struct ipa_jump_func *jfunc)
285 if (jfunc->type == IPA_JF_CONST)
287 lat->type = IPA_CONST_VALUE;
288 lat->constant = jfunc->value.constant;
290 else if (jfunc->type == IPA_JF_PASS_THROUGH)
292 struct ipcp_lattice *caller_lat;
294 caller_lat = ipcp_get_lattice (info, jfunc->value.formal_id);
295 lat->type = caller_lat->type;
296 lat->constant = caller_lat->constant;
298 else
299 lat->type = IPA_BOTTOM;
302 /* True when OLD_LAT and NEW_LAT values are not the same. */
304 static bool
305 ipcp_lattice_changed (struct ipcp_lattice *old_lat,
306 struct ipcp_lattice *new_lat)
308 if (old_lat->type == new_lat->type)
310 if (!ipcp_lat_is_const (old_lat))
311 return false;
312 if (ipcp_lats_are_equal (old_lat, new_lat))
313 return false;
315 return true;
318 /* Print all ipcp_lattices of all functions to F. */
319 static void
320 ipcp_print_all_lattices (FILE * f)
322 struct cgraph_node *node;
323 int i, count;
325 fprintf (f, "\nLattice:\n");
326 for (node = cgraph_nodes; node; node = node->next)
328 struct ipa_node_params *info;
330 if (!node->analyzed)
331 continue;
332 info = IPA_NODE_REF (node);
333 fprintf (f, " Node: %s:\n", cgraph_node_name (node));
334 count = ipa_get_param_count (info);
335 for (i = 0; i < count; i++)
337 struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
339 fprintf (f, " param [%d]: ", i);
340 if (lat->type == IPA_CONST_VALUE)
342 fprintf (f, "type is CONST ");
343 print_generic_expr (f, lat->constant, 0);
344 fprintf (f, "\n");
346 else if (lat->type == IPA_TOP)
347 fprintf (f, "type is TOP\n");
348 else
349 fprintf (f, "type is BOTTOM\n");
354 /* Return true if this NODE is viable candidate for cloning. */
355 static bool
356 ipcp_cloning_candidate_p (struct cgraph_node *node)
358 int n_calls = 0;
359 int n_hot_calls = 0;
360 gcov_type direct_call_sum = 0;
361 struct cgraph_edge *e;
363 /* We never clone functions that are not visible from outside.
364 FIXME: in future we should clone such functions when they are called with
365 different constants, but current ipcp implementation is not good on this.
367 if (!node->needed || !node->analyzed)
368 return false;
370 if (cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE)
372 if (dump_file)
373 fprintf (dump_file, "Not considering %s for cloning; body is overwrittable.\n",
374 cgraph_node_name (node));
375 return false;
377 if (!tree_versionable_function_p (node->decl))
379 if (dump_file)
380 fprintf (dump_file, "Not considering %s for cloning; body is not versionable.\n",
381 cgraph_node_name (node));
382 return false;
384 for (e = node->callers; e; e = e->next_caller)
386 direct_call_sum += e->count;
387 n_calls ++;
388 if (cgraph_maybe_hot_edge_p (e))
389 n_hot_calls ++;
392 if (!n_calls)
394 if (dump_file)
395 fprintf (dump_file, "Not considering %s for cloning; no direct calls.\n",
396 cgraph_node_name (node));
397 return false;
399 if (node->local.inline_summary.self_size < n_calls)
401 if (dump_file)
402 fprintf (dump_file, "Considering %s for cloning; code would shrink.\n",
403 cgraph_node_name (node));
404 return true;
407 if (!flag_ipa_cp_clone)
409 if (dump_file)
410 fprintf (dump_file, "Not considering %s for cloning; -fipa-cp-clone disabled.\n",
411 cgraph_node_name (node));
412 return false;
415 if (!optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node->decl)))
417 if (dump_file)
418 fprintf (dump_file, "Not considering %s for cloning; optimizing it for size.\n",
419 cgraph_node_name (node));
420 return false;
423 /* When profile is available and function is hot, propagate into it even if
424 calls seems cold; constant propagation can improve function's speed
425 significandly. */
426 if (max_count)
428 if (direct_call_sum > node->count * 90 / 100)
430 if (dump_file)
431 fprintf (dump_file, "Considering %s for cloning; usually called directly.\n",
432 cgraph_node_name (node));
433 return true;
436 if (!n_hot_calls)
438 if (dump_file)
439 fprintf (dump_file, "Not considering %s for cloning; no hot calls.\n",
440 cgraph_node_name (node));
441 return false;
443 if (dump_file)
444 fprintf (dump_file, "Considering %s for cloning.\n",
445 cgraph_node_name (node));
446 return true;
449 /* Initialize ipcp_lattices array. The lattices corresponding to supported
450 types (integers, real types and Fortran constants defined as const_decls)
451 are initialized to IPA_TOP, the rest of them to IPA_BOTTOM. */
452 static void
453 ipcp_initialize_node_lattices (struct cgraph_node *node)
455 int i;
456 struct ipa_node_params *info = IPA_NODE_REF (node);
457 enum ipa_lattice_type type;
459 if (ipa_is_called_with_var_arguments (info))
460 type = IPA_BOTTOM;
461 else if (!node->needed)
462 type = IPA_TOP;
463 /* When cloning is allowed, we can assume that externally visible functions
464 are not called. We will compensate this by cloning later. */
465 else if (ipcp_cloning_candidate_p (node))
466 type = IPA_TOP, n_cloning_candidates ++;
467 else
468 type = IPA_BOTTOM;
470 for (i = 0; i < ipa_get_param_count (info) ; i++)
471 ipcp_get_lattice (info, i)->type = type;
474 /* build INTEGER_CST tree with type TREE_TYPE and value according to LAT.
475 Return the tree. */
476 static tree
477 build_const_val (struct ipcp_lattice *lat, tree tree_type)
479 tree val;
481 gcc_assert (ipcp_lat_is_const (lat));
482 val = lat->constant;
484 if (!useless_type_conversion_p (tree_type, TREE_TYPE (val)))
486 if (fold_convertible_p (tree_type, val))
487 return fold_build1 (NOP_EXPR, tree_type, val);
488 else
489 return fold_build1 (VIEW_CONVERT_EXPR, tree_type, val);
491 return val;
494 /* Compute the proper scale for NODE. It is the ratio between the number of
495 direct calls (represented on the incoming cgraph_edges) and sum of all
496 invocations of NODE (represented as count in cgraph_node). */
497 static void
498 ipcp_compute_node_scale (struct cgraph_node *node)
500 gcov_type sum;
501 struct cgraph_edge *cs;
503 sum = 0;
504 /* Compute sum of all counts of callers. */
505 for (cs = node->callers; cs != NULL; cs = cs->next_caller)
506 sum += cs->count;
507 if (node->count == 0)
508 ipcp_set_node_scale (node, 0);
509 else
510 ipcp_set_node_scale (node, sum * REG_BR_PROB_BASE / node->count);
513 /* Initialization and computation of IPCP data structures. This is the initial
514 intraprocedural analysis of functions, which gathers information to be
515 propagated later on. */
516 static void
517 ipcp_init_stage (void)
519 struct cgraph_node *node;
520 struct cgraph_edge *cs;
522 for (node = cgraph_nodes; node; node = node->next)
523 if (node->analyzed)
524 ipcp_analyze_node (node);
525 for (node = cgraph_nodes; node; node = node->next)
527 if (!node->analyzed)
528 continue;
529 /* building jump functions */
530 for (cs = node->callees; cs; cs = cs->next_callee)
532 if (!cs->callee->analyzed)
533 continue;
534 ipa_count_arguments (cs);
535 if (ipa_get_cs_argument_count (IPA_EDGE_REF (cs))
536 != ipa_get_param_count (IPA_NODE_REF (cs->callee)))
538 /* Handle cases of functions with
539 a variable number of parameters. */
540 ipa_set_called_with_variable_arg (IPA_NODE_REF (cs->callee));
541 if (flag_indirect_inlining)
542 ipa_compute_jump_functions (cs);
544 else
545 ipa_compute_jump_functions (cs);
550 /* Return true if there are some formal parameters whose value is IPA_TOP (in
551 the whole compilation unit). Change their values to IPA_BOTTOM, since they
552 most probably get their values from outside of this compilation unit. */
553 static bool
554 ipcp_change_tops_to_bottom (void)
556 int i, count;
557 struct cgraph_node *node;
558 bool prop_again;
560 prop_again = false;
561 for (node = cgraph_nodes; node; node = node->next)
563 struct ipa_node_params *info = IPA_NODE_REF (node);
564 count = ipa_get_param_count (info);
565 for (i = 0; i < count; i++)
567 struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
568 if (lat->type == IPA_TOP)
570 prop_again = true;
571 if (dump_file)
573 fprintf (dump_file, "Forcing param ");
574 print_generic_expr (dump_file, ipa_get_param (info, i), 0);
575 fprintf (dump_file, " of node %s to bottom.\n",
576 cgraph_node_name (node));
578 lat->type = IPA_BOTTOM;
582 return prop_again;
585 /* Interprocedural analysis. The algorithm propagates constants from the
586 caller's parameters to the callee's arguments. */
587 static void
588 ipcp_propagate_stage (void)
590 int i;
591 struct ipcp_lattice inc_lat = { IPA_BOTTOM, NULL };
592 struct ipcp_lattice new_lat = { IPA_BOTTOM, NULL };
593 struct ipcp_lattice *dest_lat;
594 struct cgraph_edge *cs;
595 struct ipa_jump_func *jump_func;
596 struct ipa_func_list *wl;
597 int count;
599 ipa_check_create_node_params ();
600 ipa_check_create_edge_args ();
602 /* Initialize worklist to contain all functions. */
603 wl = ipa_init_func_list ();
604 while (wl)
606 struct cgraph_node *node = ipa_pop_func_from_list (&wl);
607 struct ipa_node_params *info = IPA_NODE_REF (node);
609 for (cs = node->callees; cs; cs = cs->next_callee)
611 struct ipa_node_params *callee_info = IPA_NODE_REF (cs->callee);
612 struct ipa_edge_args *args = IPA_EDGE_REF (cs);
614 if (ipa_is_called_with_var_arguments (callee_info))
615 continue;
617 count = ipa_get_cs_argument_count (args);
618 for (i = 0; i < count; i++)
620 jump_func = ipa_get_ith_jump_func (args, i);
621 ipcp_lattice_from_jfunc (info, &inc_lat, jump_func);
622 dest_lat = ipcp_get_lattice (callee_info, i);
623 ipa_lattice_meet (&new_lat, &inc_lat, dest_lat);
624 if (ipcp_lattice_changed (&new_lat, dest_lat))
626 dest_lat->type = new_lat.type;
627 dest_lat->constant = new_lat.constant;
628 ipa_push_func_to_list (&wl, cs->callee);
635 /* Call the constant propagation algorithm and re-call it if necessary
636 (if there are undetermined values left). */
637 static void
638 ipcp_iterate_stage (void)
640 struct cgraph_node *node;
641 n_cloning_candidates = 0;
643 if (dump_file)
644 fprintf (dump_file, "\nIPA iterate stage:\n\n");
645 for (node = cgraph_nodes; node; node = node->next)
647 ipcp_initialize_node_lattices (node);
648 ipcp_compute_node_scale (node);
650 if (dump_file && (dump_flags & TDF_DETAILS))
652 ipcp_print_all_lattices (dump_file);
653 ipcp_function_scale_print (dump_file);
656 ipcp_propagate_stage ();
657 if (ipcp_change_tops_to_bottom ())
658 /* Some lattices have changed from IPA_TOP to IPA_BOTTOM.
659 This change should be propagated. */
661 gcc_assert (n_cloning_candidates);
662 ipcp_propagate_stage ();
664 if (dump_file)
666 fprintf (dump_file, "\nIPA lattices after propagation:\n");
667 ipcp_print_all_lattices (dump_file);
668 if (dump_flags & TDF_DETAILS)
669 ipcp_print_profile_data (dump_file);
673 /* Check conditions to forbid constant insertion to function described by
674 NODE. */
675 static inline bool
676 ipcp_node_modifiable_p (struct cgraph_node *node)
678 /* Once we will be able to do in-place replacement, we can be more
679 lax here. */
680 return tree_versionable_function_p (node->decl);
683 /* Print count scale data structures. */
684 static void
685 ipcp_function_scale_print (FILE * f)
687 struct cgraph_node *node;
689 for (node = cgraph_nodes; node; node = node->next)
691 if (!node->analyzed)
692 continue;
693 fprintf (f, "printing scale for %s: ", cgraph_node_name (node));
694 fprintf (f, "value is " HOST_WIDE_INT_PRINT_DEC
695 " \n", (HOST_WIDE_INT) ipcp_get_node_scale (node));
699 /* Print counts of all cgraph nodes. */
700 static void
701 ipcp_print_func_profile_counts (FILE * f)
703 struct cgraph_node *node;
705 for (node = cgraph_nodes; node; node = node->next)
707 fprintf (f, "function %s: ", cgraph_node_name (node));
708 fprintf (f, "count is " HOST_WIDE_INT_PRINT_DEC
709 " \n", (HOST_WIDE_INT) node->count);
713 /* Print counts of all cgraph edges. */
714 static void
715 ipcp_print_call_profile_counts (FILE * f)
717 struct cgraph_node *node;
718 struct cgraph_edge *cs;
720 for (node = cgraph_nodes; node; node = node->next)
722 for (cs = node->callees; cs; cs = cs->next_callee)
724 fprintf (f, "%s -> %s ", cgraph_node_name (cs->caller),
725 cgraph_node_name (cs->callee));
726 fprintf (f, "count is " HOST_WIDE_INT_PRINT_DEC " \n",
727 (HOST_WIDE_INT) cs->count);
732 /* Print profile info for all functions. */
733 static void
734 ipcp_print_profile_data (FILE * f)
736 fprintf (f, "\nNODE COUNTS :\n");
737 ipcp_print_func_profile_counts (f);
738 fprintf (f, "\nCS COUNTS stage:\n");
739 ipcp_print_call_profile_counts (f);
742 /* Build and initialize ipa_replace_map struct according to LAT. This struct is
743 processed by versioning, which operates according to the flags set.
744 PARM_TREE is the formal parameter found to be constant. LAT represents the
745 constant. */
746 static struct ipa_replace_map *
747 ipcp_create_replace_map (tree parm_tree, struct ipcp_lattice *lat)
749 struct ipa_replace_map *replace_map;
750 tree const_val;
752 replace_map = GGC_NEW (struct ipa_replace_map);
753 const_val = build_const_val (lat, TREE_TYPE (parm_tree));
754 if (dump_file)
756 fprintf (dump_file, " replacing param ");
757 print_generic_expr (dump_file, parm_tree, 0);
758 fprintf (dump_file, " with const ");
759 print_generic_expr (dump_file, const_val, 0);
760 fprintf (dump_file, "\n");
762 replace_map->old_tree = parm_tree;
763 replace_map->new_tree = const_val;
764 replace_map->replace_p = true;
765 replace_map->ref_p = false;
767 return replace_map;
770 /* Return true if this callsite should be redirected to the original callee
771 (instead of the cloned one). */
772 static bool
773 ipcp_need_redirect_p (struct cgraph_edge *cs)
775 struct ipa_node_params *orig_callee_info;
776 int i, count;
777 struct ipa_jump_func *jump_func;
778 struct cgraph_node *node = cs->callee, *orig;
780 if (!n_cloning_candidates)
781 return false;
783 if ((orig = ipcp_get_orig_node (node)) != NULL)
784 node = orig;
785 if (ipcp_get_orig_node (cs->caller))
786 return false;
788 orig_callee_info = IPA_NODE_REF (node);
789 count = ipa_get_param_count (orig_callee_info);
790 for (i = 0; i < count; i++)
792 struct ipcp_lattice *lat = ipcp_get_lattice (orig_callee_info, i);
793 if (ipcp_lat_is_const (lat))
795 jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
796 if (jump_func->type != IPA_JF_CONST)
797 return true;
801 return false;
804 /* Fix the callsites and the call graph after function cloning was done. */
805 static void
806 ipcp_update_callgraph (void)
808 struct cgraph_node *node;
810 for (node = cgraph_nodes; node; node = node->next)
811 if (node->analyzed && ipcp_node_is_clone (node))
813 bitmap args_to_skip = BITMAP_ALLOC (NULL);
814 struct cgraph_node *orig_node = ipcp_get_orig_node (node);
815 struct ipa_node_params *info = IPA_NODE_REF (orig_node);
816 int i, count = ipa_get_param_count (info);
817 struct cgraph_edge *cs, *next;
819 for (i = 0; i < count; i++)
821 struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
822 tree parm_tree = ipa_get_param (info, i);
824 /* We can proactively remove obviously unused arguments. */
825 if (is_gimple_reg (parm_tree)
826 && !gimple_default_def (DECL_STRUCT_FUNCTION (orig_node->decl),
827 parm_tree))
829 bitmap_set_bit (args_to_skip, i);
830 continue;
833 if (lat->type == IPA_CONST_VALUE)
834 bitmap_set_bit (args_to_skip, i);
836 for (cs = node->callers; cs; cs = next)
838 next = cs->next_caller;
839 if (!ipcp_node_is_clone (cs->caller) && ipcp_need_redirect_p (cs))
840 cgraph_redirect_edge_callee (cs, orig_node);
845 /* Update profiling info for versioned functions and the functions they were
846 versioned from. */
847 static void
848 ipcp_update_profiling (void)
850 struct cgraph_node *node, *orig_node;
851 gcov_type scale, scale_complement;
852 struct cgraph_edge *cs;
854 for (node = cgraph_nodes; node; node = node->next)
856 if (ipcp_node_is_clone (node))
858 orig_node = ipcp_get_orig_node (node);
859 scale = ipcp_get_node_scale (orig_node);
860 node->count = orig_node->count * scale / REG_BR_PROB_BASE;
861 scale_complement = REG_BR_PROB_BASE - scale;
862 orig_node->count =
863 orig_node->count * scale_complement / REG_BR_PROB_BASE;
864 for (cs = node->callees; cs; cs = cs->next_callee)
865 cs->count = cs->count * scale / REG_BR_PROB_BASE;
866 for (cs = orig_node->callees; cs; cs = cs->next_callee)
867 cs->count = cs->count * scale_complement / REG_BR_PROB_BASE;
872 /* If NODE was cloned, how much would program grow? */
873 static long
874 ipcp_estimate_growth (struct cgraph_node *node)
876 struct cgraph_edge *cs;
877 int redirectable_node_callers = 0;
878 int removable_args = 0;
879 bool need_original = node->needed;
880 struct ipa_node_params *info;
881 int i, count;
882 int growth;
884 for (cs = node->callers; cs != NULL; cs = cs->next_caller)
885 if (cs->caller == node || !ipcp_need_redirect_p (cs))
886 redirectable_node_callers++;
887 else
888 need_original = true;
890 /* If we will be able to fully replace orignal node, we never increase
891 program size. */
892 if (!need_original)
893 return 0;
895 info = IPA_NODE_REF (node);
896 count = ipa_get_param_count (info);
897 for (i = 0; i < count; i++)
899 struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
900 tree parm_tree = ipa_get_param (info, i);
902 /* We can proactively remove obviously unused arguments. */
903 if (is_gimple_reg (parm_tree)
904 && !gimple_default_def (DECL_STRUCT_FUNCTION (node->decl),
905 parm_tree))
906 removable_args++;
908 if (lat->type == IPA_CONST_VALUE)
909 removable_args++;
912 /* We make just very simple estimate of savings for removal of operand from
913 call site. Precise cost is dificult to get, as our size metric counts
914 constants and moves as free. Generally we are looking for cases that
915 small function is called very many times. */
916 growth = node->local.inline_summary.self_size
917 - removable_args * redirectable_node_callers;
918 if (growth < 0)
919 return 0;
920 return growth;
924 /* Estimate cost of cloning NODE. */
925 static long
926 ipcp_estimate_cloning_cost (struct cgraph_node *node)
928 int freq_sum = 1;
929 gcov_type count_sum = 1;
930 struct cgraph_edge *e;
931 int cost;
933 cost = ipcp_estimate_growth (node) * 1000;
934 if (!cost)
936 if (dump_file)
937 fprintf (dump_file, "Versioning of %s will save code size\n",
938 cgraph_node_name (node));
939 return 0;
942 for (e = node->callers; e; e = e->next_caller)
943 if (!bitmap_bit_p (dead_nodes, e->caller->uid)
944 && !ipcp_need_redirect_p (e))
946 count_sum += e->count;
947 freq_sum += e->frequency + 1;
950 if (max_count)
951 cost /= count_sum * 1000 / max_count + 1;
952 else
953 cost /= freq_sum * 1000 / REG_BR_PROB_BASE + 1;
954 if (dump_file)
955 fprintf (dump_file, "Cost of versioning %s is %i, (size: %i, freq: %i)\n",
956 cgraph_node_name (node), cost, node->local.inline_summary.self_size,
957 freq_sum);
958 return cost + 1;
961 /* Return number of live constant parameters. */
962 static int
963 ipcp_const_param_count (struct cgraph_node *node)
965 int const_param = 0;
966 struct ipa_node_params *info = IPA_NODE_REF (node);
967 int count = ipa_get_param_count (info);
968 int i;
970 for (i = 0; i < count; i++)
972 struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
973 tree parm_tree = ipa_get_param (info, i);
974 if (ipcp_lat_is_insertable (lat)
975 /* Do not count obviously unused arguments. */
976 && (!is_gimple_reg (parm_tree)
977 || gimple_default_def (DECL_STRUCT_FUNCTION (node->decl),
978 parm_tree)))
979 const_param++;
981 return const_param;
984 /* Propagate the constant parameters found by ipcp_iterate_stage()
985 to the function's code. */
986 static void
987 ipcp_insert_stage (void)
989 struct cgraph_node *node, *node1 = NULL;
990 int i;
991 VEC (cgraph_edge_p, heap) * redirect_callers;
992 VEC (ipa_replace_map_p,gc)* replace_trees;
993 int node_callers, count;
994 tree parm_tree;
995 struct ipa_replace_map *replace_param;
996 fibheap_t heap;
997 long overall_size = 0, new_size = 0;
998 long max_new_size;
1000 ipa_check_create_node_params ();
1001 ipa_check_create_edge_args ();
1002 if (dump_file)
1003 fprintf (dump_file, "\nIPA insert stage:\n\n");
1005 dead_nodes = BITMAP_ALLOC (NULL);
1007 for (node = cgraph_nodes; node; node = node->next)
1008 if (node->analyzed)
1010 if (node->count > max_count)
1011 max_count = node->count;
1012 overall_size += node->local.inline_summary.self_size;
1015 max_new_size = overall_size;
1016 if (max_new_size < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
1017 max_new_size = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
1018 max_new_size = max_new_size * PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH) / 100 + 1;
1020 /* First collect all functions we proved to have constant arguments to heap. */
1021 heap = fibheap_new ();
1022 for (node = cgraph_nodes; node; node = node->next)
1024 struct ipa_node_params *info;
1025 /* Propagation of the constant is forbidden in certain conditions. */
1026 if (!node->analyzed || !ipcp_node_modifiable_p (node))
1027 continue;
1028 info = IPA_NODE_REF (node);
1029 if (ipa_is_called_with_var_arguments (info))
1030 continue;
1031 if (ipcp_const_param_count (node))
1032 node->aux = fibheap_insert (heap, ipcp_estimate_cloning_cost (node), node);
1035 /* Now clone in priority order until code size growth limits are met or
1036 heap is emptied. */
1037 while (!fibheap_empty (heap))
1039 struct ipa_node_params *info;
1040 int growth = 0;
1041 bitmap args_to_skip;
1042 struct cgraph_edge *cs;
1044 node = (struct cgraph_node *)fibheap_extract_min (heap);
1045 node->aux = NULL;
1046 if (dump_file)
1047 fprintf (dump_file, "considering function %s\n",
1048 cgraph_node_name (node));
1050 growth = ipcp_estimate_growth (node);
1052 if (new_size + growth > max_new_size)
1053 break;
1054 if (growth
1055 && optimize_function_for_size_p (DECL_STRUCT_FUNCTION (node->decl)))
1057 if (dump_file)
1058 fprintf (dump_file, "Not versioning, cold code would grow");
1059 continue;
1062 new_size += growth;
1064 /* Look if original function becomes dead after clonning. */
1065 for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1066 if (cs->caller == node || ipcp_need_redirect_p (cs))
1067 break;
1068 if (!cs && !node->needed)
1069 bitmap_set_bit (dead_nodes, node->uid);
1071 info = IPA_NODE_REF (node);
1072 count = ipa_get_param_count (info);
1074 replace_trees = VEC_alloc (ipa_replace_map_p, gc, 1);
1075 args_to_skip = BITMAP_GGC_ALLOC ();
1076 for (i = 0; i < count; i++)
1078 struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
1079 parm_tree = ipa_get_param (info, i);
1081 /* We can proactively remove obviously unused arguments. */
1082 if (is_gimple_reg (parm_tree)
1083 && !gimple_default_def (DECL_STRUCT_FUNCTION (node->decl),
1084 parm_tree))
1086 bitmap_set_bit (args_to_skip, i);
1087 continue;
1090 if (lat->type == IPA_CONST_VALUE)
1092 replace_param =
1093 ipcp_create_replace_map (parm_tree, lat);
1094 VEC_safe_push (ipa_replace_map_p, gc, replace_trees, replace_param);
1095 bitmap_set_bit (args_to_skip, i);
1099 /* Compute how many callers node has. */
1100 node_callers = 0;
1101 for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1102 node_callers++;
1103 redirect_callers = VEC_alloc (cgraph_edge_p, heap, node_callers);
1104 for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1105 VEC_quick_push (cgraph_edge_p, redirect_callers, cs);
1107 /* Redirecting all the callers of the node to the
1108 new versioned node. */
1109 node1 =
1110 cgraph_create_virtual_clone (node, redirect_callers, replace_trees,
1111 args_to_skip);
1112 args_to_skip = NULL;
1113 VEC_free (cgraph_edge_p, heap, redirect_callers);
1114 replace_trees = NULL;
1116 if (node1 == NULL)
1117 continue;
1118 if (dump_file)
1119 fprintf (dump_file, "versioned function %s with growth %i, overall %i\n",
1120 cgraph_node_name (node), (int)growth, (int)new_size);
1121 ipcp_init_cloned_node (node, node1);
1123 /* TODO: We can use indirect inlning info to produce new calls. */
1125 if (dump_file)
1126 dump_function_to_file (node1->decl, dump_file, dump_flags);
1128 for (cs = node->callees; cs; cs = cs->next_callee)
1129 if (cs->callee->aux)
1131 fibheap_delete_node (heap, (fibnode_t) cs->callee->aux);
1132 cs->callee->aux = fibheap_insert (heap,
1133 ipcp_estimate_cloning_cost (cs->callee),
1134 cs->callee);
1138 while (!fibheap_empty (heap))
1140 if (dump_file)
1141 fprintf (dump_file, "skipping function %s\n",
1142 cgraph_node_name (node));
1143 node = (struct cgraph_node *) fibheap_extract_min (heap);
1144 node->aux = NULL;
1146 fibheap_delete (heap);
1147 BITMAP_FREE (dead_nodes);
1148 ipcp_update_callgraph ();
1149 ipcp_update_profiling ();
1152 /* The IPCP driver. */
1153 static unsigned int
1154 ipcp_driver (void)
1156 cgraph_remove_unreachable_nodes (true,dump_file);
1157 if (dump_file)
1159 fprintf (dump_file, "\nIPA structures before propagation:\n");
1160 if (dump_flags & TDF_DETAILS)
1161 ipa_print_all_params (dump_file);
1162 ipa_print_all_jump_functions (dump_file);
1164 /* 2. Do the interprocedural propagation. */
1165 ipcp_iterate_stage ();
1166 /* 3. Insert the constants found to the functions. */
1167 ipcp_insert_stage ();
1168 if (dump_file && (dump_flags & TDF_DETAILS))
1170 fprintf (dump_file, "\nProfiling info after insert stage:\n");
1171 ipcp_print_profile_data (dump_file);
1173 /* Free all IPCP structures. */
1174 free_all_ipa_structures_after_ipa_cp ();
1175 if (dump_file)
1176 fprintf (dump_file, "\nIPA constant propagation end\n");
1177 return 0;
1180 /* Note function body size. */
1181 static void
1182 ipcp_generate_summary (void)
1184 if (dump_file)
1185 fprintf (dump_file, "\nIPA constant propagation start:\n");
1186 ipa_check_create_node_params ();
1187 ipa_check_create_edge_args ();
1188 ipa_register_cgraph_hooks ();
1189 /* 1. Call the init stage to initialize
1190 the ipa_node_params and ipa_edge_args structures. */
1191 ipcp_init_stage ();
1194 /* Gate for IPCP optimization. */
1195 static bool
1196 cgraph_gate_cp (void)
1198 return flag_ipa_cp;
1201 struct ipa_opt_pass_d pass_ipa_cp =
1204 IPA_PASS,
1205 "cp", /* name */
1206 cgraph_gate_cp, /* gate */
1207 ipcp_driver, /* execute */
1208 NULL, /* sub */
1209 NULL, /* next */
1210 0, /* static_pass_number */
1211 TV_IPA_CONSTANT_PROP, /* tv_id */
1212 0, /* properties_required */
1213 0, /* properties_provided */
1214 0, /* properties_destroyed */
1215 0, /* todo_flags_start */
1216 TODO_dump_cgraph | TODO_dump_func |
1217 TODO_remove_functions /* todo_flags_finish */
1219 ipcp_generate_summary, /* generate_summary */
1220 NULL, /* write_summary */
1221 NULL, /* read_summary */
1222 NULL, /* function_read_summary */
1223 0, /* TODOs */
1224 NULL, /* function_transform */
1225 NULL, /* variable_transform */