1 /* Interprocedural constant propagation
2 Copyright (C) 2005, 2006, 2007, 2008 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
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
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:
28 printf ("value is %d",y);
48 The IPCP algorithm will find that g's formal argument y is always called
51 The algorithm used is based on "Interprocedural Constant Propagation", by
52 Challahan David, Keith D Cooper, Ken Kennedy, Linda Torczon, Comp86, pg
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:
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
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.
123 #include "coretypes.h"
127 #include "ipa-prop.h"
128 #include "tree-flow.h"
129 #include "tree-pass.h"
132 #include "diagnostic.h"
133 #include "tree-dump.h"
134 #include "tree-inline.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. */
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. */
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. */
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. */
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. */
205 ipcp_lat_is_const (struct ipcp_lattice *lat)
207 if (lat->type == IPA_CONST_VALUE)
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). */
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. */
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)
229 if (operand_equal_p (lat1->constant, lat2->constant, 0))
235 /* Compute Meet arithmetics:
236 Meet (IPA_BOTTOM, x) = IPA_BOTTOM
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.*/
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;
249 if (lat1->type == IPA_TOP)
251 res->type = lat2->type;
252 res->constant = lat2->constant;
255 if (lat2->type == IPA_TOP)
257 res->type = lat1->type;
258 res->constant = lat1->constant;
261 if (!ipcp_lats_are_equal (lat1, lat2))
263 res->type = IPA_BOTTOM;
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. */
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;
299 lat->type = IPA_BOTTOM;
302 /* True when OLD_LAT and NEW_LAT values are not the same. */
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))
312 if (ipcp_lats_are_equal (old_lat, new_lat))
318 /* Print all ipcp_lattices of all functions to F. */
320 ipcp_print_all_lattices (FILE * f)
322 struct cgraph_node *node;
325 fprintf (f, "\nLattice:\n");
326 for (node = cgraph_nodes; node; node = node->next)
328 struct ipa_node_params *info;
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);
346 else if (lat->type == IPA_TOP)
347 fprintf (f, "type is TOP\n");
349 fprintf (f, "type is BOTTOM\n");
354 /* Return true if this NODE is viable candidate for cloning. */
356 ipcp_cloning_candidate_p (struct cgraph_node *node)
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)
370 if (cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE)
373 fprintf (dump_file, "Not considering %s for cloning; body is overwrittable.\n",
374 cgraph_node_name (node));
377 if (!tree_versionable_function_p (node->decl))
380 fprintf (dump_file, "Not considering %s for cloning; body is not versionable.\n",
381 cgraph_node_name (node));
384 for (e = node->callers; e; e = e->next_caller)
386 direct_call_sum += e->count;
388 if (cgraph_maybe_hot_edge_p (e))
395 fprintf (dump_file, "Not considering %s for cloning; no direct calls.\n",
396 cgraph_node_name (node));
399 if (node->local.inline_summary.self_insns < n_calls)
402 fprintf (dump_file, "Considering %s for cloning; code would shrink.\n",
403 cgraph_node_name (node));
407 if (!flag_ipa_cp_clone)
410 fprintf (dump_file, "Not considering %s for cloning; -fipa-cp-clone disabled.\n",
411 cgraph_node_name (node));
415 if (!optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node->decl)))
418 fprintf (dump_file, "Not considering %s for cloning; optimizing it for size.\n",
419 cgraph_node_name (node));
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
428 if (direct_call_sum > node->count * 90 / 100)
431 fprintf (dump_file, "Considering %s for cloning; usually called directly.\n",
432 cgraph_node_name (node));
439 fprintf (dump_file, "Not considering %s for cloning; no hot calls.\n",
440 cgraph_node_name (node));
443 fprintf (dump_file, "Considering %s for cloning.\n",
444 cgraph_node_name (node));
448 /* Initialize ipcp_lattices array. The lattices corresponding to supported
449 types (integers, real types and Fortran constants defined as const_decls)
450 are initialized to IPA_TOP, the rest of them to IPA_BOTTOM. */
452 ipcp_initialize_node_lattices (struct cgraph_node *node)
455 struct ipa_node_params *info = IPA_NODE_REF (node);
456 enum ipa_lattice_type type;
458 if (ipa_is_called_with_var_arguments (info))
460 else if (!node->needed)
462 /* When cloning is allowed, we can assume that externally visible functions
463 are not called. We will compensate this by cloning later. */
464 else if (ipcp_cloning_candidate_p (node))
465 type = IPA_TOP, n_cloning_candidates ++;
469 for (i = 0; i < ipa_get_param_count (info) ; i++)
470 ipcp_get_lattice (info, i)->type = type;
473 /* build INTEGER_CST tree with type TREE_TYPE and value according to LAT.
476 build_const_val (struct ipcp_lattice *lat, tree tree_type)
480 gcc_assert (ipcp_lat_is_const (lat));
483 if (!useless_type_conversion_p (tree_type, TREE_TYPE (val)))
485 if (fold_convertible_p (tree_type, val))
486 return fold_build1 (NOP_EXPR, tree_type, val);
488 return fold_build1 (VIEW_CONVERT_EXPR, tree_type, val);
493 /* Compute the proper scale for NODE. It is the ratio between the number of
494 direct calls (represented on the incoming cgraph_edges) and sum of all
495 invocations of NODE (represented as count in cgraph_node). */
497 ipcp_compute_node_scale (struct cgraph_node *node)
500 struct cgraph_edge *cs;
503 /* Compute sum of all counts of callers. */
504 for (cs = node->callers; cs != NULL; cs = cs->next_caller)
506 if (node->count == 0)
507 ipcp_set_node_scale (node, 0);
509 ipcp_set_node_scale (node, sum * REG_BR_PROB_BASE / node->count);
512 /* Initialization and computation of IPCP data structures. This is the initial
513 intraprocedural analysis of functions, which gathers information to be
514 propagated later on. */
516 ipcp_init_stage (void)
518 struct cgraph_node *node;
519 struct cgraph_edge *cs;
521 for (node = cgraph_nodes; node; node = node->next)
523 ipcp_analyze_node (node);
524 for (node = cgraph_nodes; node; node = node->next)
528 /* building jump functions */
529 for (cs = node->callees; cs; cs = cs->next_callee)
531 if (!cs->callee->analyzed)
533 ipa_count_arguments (cs);
534 if (ipa_get_cs_argument_count (IPA_EDGE_REF (cs))
535 != ipa_get_param_count (IPA_NODE_REF (cs->callee)))
537 /* Handle cases of functions with
538 a variable number of parameters. */
539 ipa_set_called_with_variable_arg (IPA_NODE_REF (cs->callee));
540 if (flag_indirect_inlining)
541 ipa_compute_jump_functions (cs);
544 ipa_compute_jump_functions (cs);
549 /* Return true if there are some formal parameters whose value is IPA_TOP (in
550 the whole compilation unit). Change their values to IPA_BOTTOM, since they
551 most probably get their values from outside of this compilation unit. */
553 ipcp_change_tops_to_bottom (void)
556 struct cgraph_node *node;
560 for (node = cgraph_nodes; node; node = node->next)
562 struct ipa_node_params *info = IPA_NODE_REF (node);
563 count = ipa_get_param_count (info);
564 for (i = 0; i < count; i++)
566 struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
567 if (lat->type == IPA_TOP)
572 fprintf (dump_file, "Forcing param ");
573 print_generic_expr (dump_file, ipa_get_param (info, i), 0);
574 fprintf (dump_file, " of node %s to bottom.\n",
575 cgraph_node_name (node));
577 lat->type = IPA_BOTTOM;
584 /* Interprocedural analysis. The algorithm propagates constants from the
585 caller's parameters to the callee's arguments. */
587 ipcp_propagate_stage (void)
590 struct ipcp_lattice inc_lat = { IPA_BOTTOM, NULL };
591 struct ipcp_lattice new_lat = { IPA_BOTTOM, NULL };
592 struct ipcp_lattice *dest_lat;
593 struct cgraph_edge *cs;
594 struct ipa_jump_func *jump_func;
595 struct ipa_func_list *wl;
598 ipa_check_create_node_params ();
599 ipa_check_create_edge_args ();
601 /* Initialize worklist to contain all functions. */
602 wl = ipa_init_func_list ();
605 struct cgraph_node *node = ipa_pop_func_from_list (&wl);
606 struct ipa_node_params *info = IPA_NODE_REF (node);
608 for (cs = node->callees; cs; cs = cs->next_callee)
610 struct ipa_node_params *callee_info = IPA_NODE_REF (cs->callee);
611 struct ipa_edge_args *args = IPA_EDGE_REF (cs);
613 if (ipa_is_called_with_var_arguments (callee_info))
616 count = ipa_get_cs_argument_count (args);
617 for (i = 0; i < count; i++)
619 jump_func = ipa_get_ith_jump_func (args, i);
620 ipcp_lattice_from_jfunc (info, &inc_lat, jump_func);
621 dest_lat = ipcp_get_lattice (callee_info, i);
622 ipa_lattice_meet (&new_lat, &inc_lat, dest_lat);
623 if (ipcp_lattice_changed (&new_lat, dest_lat))
625 dest_lat->type = new_lat.type;
626 dest_lat->constant = new_lat.constant;
627 ipa_push_func_to_list (&wl, cs->callee);
634 /* Call the constant propagation algorithm and re-call it if necessary
635 (if there are undetermined values left). */
637 ipcp_iterate_stage (void)
639 struct cgraph_node *node;
640 n_cloning_candidates = 0;
643 fprintf (dump_file, "\nIPA iterate stage:\n\n");
644 for (node = cgraph_nodes; node; node = node->next)
646 ipcp_initialize_node_lattices (node);
647 ipcp_compute_node_scale (node);
649 if (dump_file && (dump_flags & TDF_DETAILS))
651 ipcp_print_all_lattices (dump_file);
652 ipcp_function_scale_print (dump_file);
655 ipcp_propagate_stage ();
656 if (ipcp_change_tops_to_bottom ())
657 /* Some lattices have changed from IPA_TOP to IPA_BOTTOM.
658 This change should be propagated. */
660 gcc_assert (n_cloning_candidates);
661 ipcp_propagate_stage ();
665 fprintf (dump_file, "\nIPA lattices after propagation:\n");
666 ipcp_print_all_lattices (dump_file);
667 if (dump_flags & TDF_DETAILS)
668 ipcp_print_profile_data (dump_file);
672 /* Check conditions to forbid constant insertion to function described by
675 ipcp_node_modifiable_p (struct cgraph_node *node)
677 /* Once we will be able to do in-place replacement, we can be more
679 return tree_versionable_function_p (node->decl);
682 /* Print count scale data structures. */
684 ipcp_function_scale_print (FILE * f)
686 struct cgraph_node *node;
688 for (node = cgraph_nodes; node; node = node->next)
692 fprintf (f, "printing scale for %s: ", cgraph_node_name (node));
693 fprintf (f, "value is " HOST_WIDE_INT_PRINT_DEC
694 " \n", (HOST_WIDE_INT) ipcp_get_node_scale (node));
698 /* Print counts of all cgraph nodes. */
700 ipcp_print_func_profile_counts (FILE * f)
702 struct cgraph_node *node;
704 for (node = cgraph_nodes; node; node = node->next)
706 fprintf (f, "function %s: ", cgraph_node_name (node));
707 fprintf (f, "count is " HOST_WIDE_INT_PRINT_DEC
708 " \n", (HOST_WIDE_INT) node->count);
712 /* Print counts of all cgraph edges. */
714 ipcp_print_call_profile_counts (FILE * f)
716 struct cgraph_node *node;
717 struct cgraph_edge *cs;
719 for (node = cgraph_nodes; node; node = node->next)
721 for (cs = node->callees; cs; cs = cs->next_callee)
723 fprintf (f, "%s -> %s ", cgraph_node_name (cs->caller),
724 cgraph_node_name (cs->callee));
725 fprintf (f, "count is " HOST_WIDE_INT_PRINT_DEC " \n",
726 (HOST_WIDE_INT) cs->count);
731 /* Print profile info for all functions. */
733 ipcp_print_profile_data (FILE * f)
735 fprintf (f, "\nNODE COUNTS :\n");
736 ipcp_print_func_profile_counts (f);
737 fprintf (f, "\nCS COUNTS stage:\n");
738 ipcp_print_call_profile_counts (f);
741 /* Build and initialize ipa_replace_map struct according to LAT. This struct is
742 processed by versioning, which operates according to the flags set.
743 PARM_TREE is the formal parameter found to be constant. LAT represents the
745 static struct ipa_replace_map *
746 ipcp_create_replace_map (tree parm_tree, struct ipcp_lattice *lat)
748 struct ipa_replace_map *replace_map;
751 replace_map = GGC_NEW (struct ipa_replace_map);
752 const_val = build_const_val (lat, TREE_TYPE (parm_tree));
755 fprintf (dump_file, " replacing param ");
756 print_generic_expr (dump_file, parm_tree, 0);
757 fprintf (dump_file, " with const ");
758 print_generic_expr (dump_file, const_val, 0);
759 fprintf (dump_file, "\n");
761 replace_map->old_tree = parm_tree;
762 replace_map->new_tree = const_val;
763 replace_map->replace_p = true;
764 replace_map->ref_p = false;
769 /* Return true if this callsite should be redirected to the original callee
770 (instead of the cloned one). */
772 ipcp_need_redirect_p (struct cgraph_edge *cs)
774 struct ipa_node_params *orig_callee_info;
776 struct ipa_jump_func *jump_func;
777 struct cgraph_node *node = cs->callee, *orig;
779 if (!n_cloning_candidates)
782 if ((orig = ipcp_get_orig_node (node)) != NULL)
784 if (ipcp_get_orig_node (cs->caller))
787 orig_callee_info = IPA_NODE_REF (node);
788 count = ipa_get_param_count (orig_callee_info);
789 for (i = 0; i < count; i++)
791 struct ipcp_lattice *lat = ipcp_get_lattice (orig_callee_info, i);
792 if (ipcp_lat_is_const (lat))
794 jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
795 if (jump_func->type != IPA_JF_CONST)
803 /* Fix the callsites and the call graph after function cloning was done. */
805 ipcp_update_callgraph (void)
807 struct cgraph_node *node;
809 for (node = cgraph_nodes; node; node = node->next)
810 if (node->analyzed && ipcp_node_is_clone (node))
812 bitmap args_to_skip = BITMAP_ALLOC (NULL);
813 struct cgraph_node *orig_node = ipcp_get_orig_node (node);
814 struct ipa_node_params *info = IPA_NODE_REF (orig_node);
815 int i, count = ipa_get_param_count (info);
816 struct cgraph_edge *cs, *next;
818 for (i = 0; i < count; i++)
820 struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
821 tree parm_tree = ipa_get_param (info, i);
823 /* We can proactively remove obviously unused arguments. */
824 if (is_gimple_reg (parm_tree)
825 && !gimple_default_def (DECL_STRUCT_FUNCTION (orig_node->decl),
828 bitmap_set_bit (args_to_skip, i);
832 if (lat->type == IPA_CONST_VALUE)
833 bitmap_set_bit (args_to_skip, i);
835 for (cs = node->callers; cs; cs = next)
837 next = cs->next_caller;
838 if (!ipcp_node_is_clone (cs->caller) && ipcp_need_redirect_p (cs))
840 cgraph_redirect_edge_callee (cs, orig_node);
841 gimple_call_set_fndecl (cs->call_stmt, orig_node->decl);
847 /* Update profiling info for versioned functions and the functions they were
850 ipcp_update_profiling (void)
852 struct cgraph_node *node, *orig_node;
853 gcov_type scale, scale_complement;
854 struct cgraph_edge *cs;
856 for (node = cgraph_nodes; node; node = node->next)
858 if (ipcp_node_is_clone (node))
860 orig_node = ipcp_get_orig_node (node);
861 scale = ipcp_get_node_scale (orig_node);
862 node->count = orig_node->count * scale / REG_BR_PROB_BASE;
863 scale_complement = REG_BR_PROB_BASE - scale;
865 orig_node->count * scale_complement / REG_BR_PROB_BASE;
866 for (cs = node->callees; cs; cs = cs->next_callee)
867 cs->count = cs->count * scale / REG_BR_PROB_BASE;
868 for (cs = orig_node->callees; cs; cs = cs->next_callee)
869 cs->count = cs->count * scale_complement / REG_BR_PROB_BASE;
874 /* If NODE was cloned, how much would program grow? */
876 ipcp_estimate_growth (struct cgraph_node *node)
878 struct cgraph_edge *cs;
879 int redirectable_node_callers = 0;
880 int removable_args = 0;
881 bool need_original = node->needed;
882 struct ipa_node_params *info;
886 for (cs = node->callers; cs != NULL; cs = cs->next_caller)
887 if (cs->caller == node || !ipcp_need_redirect_p (cs))
888 redirectable_node_callers++;
890 need_original = true;
892 /* If we will be able to fully replace orignal node, we never increase
897 info = IPA_NODE_REF (node);
898 count = ipa_get_param_count (info);
899 for (i = 0; i < count; i++)
901 struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
902 tree parm_tree = ipa_get_param (info, i);
904 /* We can proactively remove obviously unused arguments. */
905 if (is_gimple_reg (parm_tree)
906 && !gimple_default_def (DECL_STRUCT_FUNCTION (node->decl),
910 if (lat->type == IPA_CONST_VALUE)
914 /* We make just very simple estimate of savings for removal of operand from
915 call site. Precise cost is dificult to get, as our size metric counts
916 constants and moves as free. Generally we are looking for cases that
917 small function is called very many times. */
918 growth = node->local.inline_summary.self_insns
919 - removable_args * redirectable_node_callers;
926 /* Estimate cost of cloning NODE. */
928 ipcp_estimate_cloning_cost (struct cgraph_node *node)
931 gcov_type count_sum = 1;
932 struct cgraph_edge *e;
935 cost = ipcp_estimate_growth (node) * 1000;
939 fprintf (dump_file, "Versioning of %s will save code size\n",
940 cgraph_node_name (node));
944 for (e = node->callers; e; e = e->next_caller)
945 if (!bitmap_bit_p (dead_nodes, e->caller->uid)
946 && !ipcp_need_redirect_p (e))
948 count_sum += e->count;
949 freq_sum += e->frequency + 1;
953 cost /= count_sum * 1000 / max_count + 1;
955 cost /= freq_sum * 1000 / REG_BR_PROB_BASE + 1;
957 fprintf (dump_file, "Cost of versioning %s is %i, (size: %i, freq: %i)\n",
958 cgraph_node_name (node), cost, node->local.inline_summary.self_insns,
963 /* Return number of live constant parameters. */
965 ipcp_const_param_count (struct cgraph_node *node)
968 struct ipa_node_params *info = IPA_NODE_REF (node);
969 int count = ipa_get_param_count (info);
972 for (i = 0; i < count; i++)
974 struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
975 tree parm_tree = ipa_get_param (info, i);
976 if (ipcp_lat_is_insertable (lat)
977 /* Do not count obviously unused arguments. */
978 && (!is_gimple_reg (parm_tree)
979 || gimple_default_def (DECL_STRUCT_FUNCTION (node->decl),
986 /* Propagate the constant parameters found by ipcp_iterate_stage()
987 to the function's code. */
989 ipcp_insert_stage (void)
991 struct cgraph_node *node, *node1 = NULL;
993 VEC (cgraph_edge_p, heap) * redirect_callers;
994 VEC (ipa_replace_map_p,gc)* replace_trees;
995 int node_callers, count;
997 struct ipa_replace_map *replace_param;
999 long overall_size = 0, new_size = 0;
1002 ipa_check_create_node_params ();
1003 ipa_check_create_edge_args ();
1005 fprintf (dump_file, "\nIPA insert stage:\n\n");
1007 dead_nodes = BITMAP_ALLOC (NULL);
1009 for (node = cgraph_nodes; node; node = node->next)
1012 if (node->count > max_count)
1013 max_count = node->count;
1014 overall_size += node->local.inline_summary.self_insns;
1017 max_new_size = overall_size;
1018 if (max_new_size < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
1019 max_new_size = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
1020 max_new_size = max_new_size * PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH) / 100 + 1;
1022 /* First collect all functions we proved to have constant arguments to heap. */
1023 heap = fibheap_new ();
1024 for (node = cgraph_nodes; node; node = node->next)
1026 struct ipa_node_params *info;
1027 /* Propagation of the constant is forbidden in certain conditions. */
1028 if (!node->analyzed || !ipcp_node_modifiable_p (node))
1030 info = IPA_NODE_REF (node);
1031 if (ipa_is_called_with_var_arguments (info))
1033 if (ipcp_const_param_count (node))
1034 node->aux = fibheap_insert (heap, ipcp_estimate_cloning_cost (node), node);
1037 /* Now clone in priority order until code size growth limits are met or
1039 while (!fibheap_empty (heap))
1041 struct ipa_node_params *info;
1043 bitmap args_to_skip;
1044 struct cgraph_edge *cs;
1046 node = (struct cgraph_node *)fibheap_extract_min (heap);
1049 fprintf (dump_file, "considering function %s\n",
1050 cgraph_node_name (node));
1052 growth = ipcp_estimate_growth (node);
1054 if (new_size + growth > max_new_size)
1057 && optimize_function_for_size_p (DECL_STRUCT_FUNCTION (node->decl)))
1060 fprintf (dump_file, "Not versioning, cold code would grow");
1066 /* Look if original function becomes dead after clonning. */
1067 for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1068 if (cs->caller == node || ipcp_need_redirect_p (cs))
1070 if (!cs && !node->needed)
1071 bitmap_set_bit (dead_nodes, node->uid);
1073 info = IPA_NODE_REF (node);
1074 count = ipa_get_param_count (info);
1076 replace_trees = VEC_alloc (ipa_replace_map_p, gc, 1);
1077 args_to_skip = BITMAP_GGC_ALLOC ();
1078 for (i = 0; i < count; i++)
1080 struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
1081 parm_tree = ipa_get_param (info, i);
1083 /* We can proactively remove obviously unused arguments. */
1084 if (is_gimple_reg (parm_tree)
1085 && !gimple_default_def (DECL_STRUCT_FUNCTION (node->decl),
1088 bitmap_set_bit (args_to_skip, i);
1092 if (lat->type == IPA_CONST_VALUE)
1095 ipcp_create_replace_map (parm_tree, lat);
1096 VEC_safe_push (ipa_replace_map_p, gc, replace_trees, replace_param);
1097 bitmap_set_bit (args_to_skip, i);
1101 /* Compute how many callers node has. */
1103 for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1105 redirect_callers = VEC_alloc (cgraph_edge_p, heap, node_callers);
1106 for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1107 VEC_quick_push (cgraph_edge_p, redirect_callers, cs);
1109 /* Redirecting all the callers of the node to the
1110 new versioned node. */
1112 cgraph_create_virtual_clone (node, redirect_callers, replace_trees,
1114 args_to_skip = NULL;
1115 VEC_free (cgraph_edge_p, heap, redirect_callers);
1116 replace_trees = NULL;
1121 fprintf (dump_file, "versioned function %s with growth %i, overall %i\n",
1122 cgraph_node_name (node), (int)growth, (int)new_size);
1123 ipcp_init_cloned_node (node, node1);
1125 /* TODO: We can use indirect inlning info to produce new calls. */
1128 dump_function_to_file (node1->decl, dump_file, dump_flags);
1130 for (cs = node->callees; cs; cs = cs->next_callee)
1131 if (cs->callee->aux)
1133 fibheap_delete_node (heap, (fibnode_t) cs->callee->aux);
1134 cs->callee->aux = fibheap_insert (heap,
1135 ipcp_estimate_cloning_cost (cs->callee),
1140 while (!fibheap_empty (heap))
1143 fprintf (dump_file, "skipping function %s\n",
1144 cgraph_node_name (node));
1145 node = (struct cgraph_node *) fibheap_extract_min (heap);
1148 fibheap_delete (heap);
1149 BITMAP_FREE (dead_nodes);
1150 ipcp_update_callgraph ();
1151 ipcp_update_profiling ();
1154 /* The IPCP driver. */
1158 cgraph_remove_unreachable_nodes (true,dump_file);
1161 fprintf (dump_file, "\nIPA structures before propagation:\n");
1162 if (dump_flags & TDF_DETAILS)
1163 ipa_print_all_params (dump_file);
1164 ipa_print_all_jump_functions (dump_file);
1166 /* 2. Do the interprocedural propagation. */
1167 ipcp_iterate_stage ();
1168 /* 3. Insert the constants found to the functions. */
1169 ipcp_insert_stage ();
1170 if (dump_file && (dump_flags & TDF_DETAILS))
1172 fprintf (dump_file, "\nProfiling info after insert stage:\n");
1173 ipcp_print_profile_data (dump_file);
1175 /* Free all IPCP structures. */
1176 free_all_ipa_structures_after_ipa_cp ();
1178 fprintf (dump_file, "\nIPA constant propagation end\n");
1182 /* Note function body size. */
1184 ipcp_generate_summary (void)
1187 fprintf (dump_file, "\nIPA constant propagation start:\n");
1188 ipa_check_create_node_params ();
1189 ipa_check_create_edge_args ();
1190 ipa_register_cgraph_hooks ();
1191 /* 1. Call the init stage to initialize
1192 the ipa_node_params and ipa_edge_args structures. */
1196 /* Gate for IPCP optimization. */
1198 cgraph_gate_cp (void)
1203 struct ipa_opt_pass pass_ipa_cp =
1208 cgraph_gate_cp, /* gate */
1209 ipcp_driver, /* execute */
1212 0, /* static_pass_number */
1213 TV_IPA_CONSTANT_PROP, /* tv_id */
1214 0, /* properties_required */
1215 0, /* properties_provided */
1216 0, /* properties_destroyed */
1217 0, /* todo_flags_start */
1218 TODO_dump_cgraph | TODO_dump_func |
1219 TODO_remove_functions /* todo_flags_finish */
1221 ipcp_generate_summary, /* generate_summary */
1222 NULL, /* write_summary */
1223 NULL, /* read_summary */
1224 NULL, /* function_read_summary */
1226 NULL, /* function_transform */
1227 NULL, /* variable_transform */