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
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 ipcp algorithms would allow cloning NODE. */
357 ipcp_versionable_function_p (struct cgraph_node *node)
359 tree decl = node->decl;
362 /* There are a number of generic reasons functions cannot be versioned. */
363 if (!tree_versionable_function_p (decl))
366 /* Removing arguments doesn't work if the function takes varargs. */
367 if (DECL_STRUCT_FUNCTION (decl)->stdarg)
370 /* Removing arguments doesn't work if we use __builtin_apply_args. */
371 FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (decl))
373 gimple_stmt_iterator gsi;
374 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
376 const_gimple stmt = gsi_stmt (gsi);
379 if (!is_gimple_call (stmt))
381 t = gimple_call_fndecl (stmt);
384 if (DECL_BUILT_IN_CLASS (t) == BUILT_IN_NORMAL
385 && DECL_FUNCTION_CODE (t) == BUILT_IN_APPLY_ARGS)
393 /* Return true if this NODE is viable candidate for cloning. */
395 ipcp_cloning_candidate_p (struct cgraph_node *node)
399 gcov_type direct_call_sum = 0;
400 struct cgraph_edge *e;
402 /* We never clone functions that are not visible from outside.
403 FIXME: in future we should clone such functions when they are called with
404 different constants, but current ipcp implementation is not good on this.
406 if (!node->needed || !node->analyzed)
409 if (cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE)
412 fprintf (dump_file, "Not considering %s for cloning; body is overwrittable.\n",
413 cgraph_node_name (node));
416 if (!ipcp_versionable_function_p (node))
419 fprintf (dump_file, "Not considering %s for cloning; body is not versionable.\n",
420 cgraph_node_name (node));
423 for (e = node->callers; e; e = e->next_caller)
425 direct_call_sum += e->count;
427 if (cgraph_maybe_hot_edge_p (e))
434 fprintf (dump_file, "Not considering %s for cloning; no direct calls.\n",
435 cgraph_node_name (node));
438 if (node->local.inline_summary.self_size < n_calls)
441 fprintf (dump_file, "Considering %s for cloning; code would shrink.\n",
442 cgraph_node_name (node));
446 if (!flag_ipa_cp_clone)
449 fprintf (dump_file, "Not considering %s for cloning; -fipa-cp-clone disabled.\n",
450 cgraph_node_name (node));
454 if (!optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node->decl)))
457 fprintf (dump_file, "Not considering %s for cloning; optimizing it for size.\n",
458 cgraph_node_name (node));
462 /* When profile is available and function is hot, propagate into it even if
463 calls seems cold; constant propagation can improve function's speed
467 if (direct_call_sum > node->count * 90 / 100)
470 fprintf (dump_file, "Considering %s for cloning; usually called directly.\n",
471 cgraph_node_name (node));
478 fprintf (dump_file, "Not considering %s for cloning; no hot calls.\n",
479 cgraph_node_name (node));
483 fprintf (dump_file, "Considering %s for cloning.\n",
484 cgraph_node_name (node));
488 /* Initialize ipcp_lattices array. The lattices corresponding to supported
489 types (integers, real types and Fortran constants defined as const_decls)
490 are initialized to IPA_TOP, the rest of them to IPA_BOTTOM. */
492 ipcp_initialize_node_lattices (struct cgraph_node *node)
495 struct ipa_node_params *info = IPA_NODE_REF (node);
496 enum ipa_lattice_type type;
498 if (ipa_is_called_with_var_arguments (info))
500 else if (!node->needed)
502 /* When cloning is allowed, we can assume that externally visible functions
503 are not called. We will compensate this by cloning later. */
504 else if (ipcp_cloning_candidate_p (node))
505 type = IPA_TOP, n_cloning_candidates ++;
509 for (i = 0; i < ipa_get_param_count (info) ; i++)
510 ipcp_get_lattice (info, i)->type = type;
513 /* build INTEGER_CST tree with type TREE_TYPE and value according to LAT.
516 build_const_val (struct ipcp_lattice *lat, tree tree_type)
520 gcc_assert (ipcp_lat_is_const (lat));
523 if (!useless_type_conversion_p (tree_type, TREE_TYPE (val)))
525 if (fold_convertible_p (tree_type, val))
526 return fold_build1 (NOP_EXPR, tree_type, val);
528 return fold_build1 (VIEW_CONVERT_EXPR, tree_type, val);
533 /* Compute the proper scale for NODE. It is the ratio between the number of
534 direct calls (represented on the incoming cgraph_edges) and sum of all
535 invocations of NODE (represented as count in cgraph_node). */
537 ipcp_compute_node_scale (struct cgraph_node *node)
540 struct cgraph_edge *cs;
543 /* Compute sum of all counts of callers. */
544 for (cs = node->callers; cs != NULL; cs = cs->next_caller)
546 if (node->count == 0)
547 ipcp_set_node_scale (node, 0);
549 ipcp_set_node_scale (node, sum * REG_BR_PROB_BASE / node->count);
552 /* Initialization and computation of IPCP data structures. This is the initial
553 intraprocedural analysis of functions, which gathers information to be
554 propagated later on. */
556 ipcp_init_stage (void)
558 struct cgraph_node *node;
559 struct cgraph_edge *cs;
561 for (node = cgraph_nodes; node; node = node->next)
563 ipcp_analyze_node (node);
564 for (node = cgraph_nodes; node; node = node->next)
568 /* building jump functions */
569 for (cs = node->callees; cs; cs = cs->next_callee)
571 if (!cs->callee->analyzed)
573 ipa_count_arguments (cs);
574 if (ipa_get_cs_argument_count (IPA_EDGE_REF (cs))
575 != ipa_get_param_count (IPA_NODE_REF (cs->callee)))
577 /* Handle cases of functions with
578 a variable number of parameters. */
579 ipa_set_called_with_variable_arg (IPA_NODE_REF (cs->callee));
580 if (flag_indirect_inlining)
581 ipa_compute_jump_functions (cs);
584 ipa_compute_jump_functions (cs);
589 /* Return true if there are some formal parameters whose value is IPA_TOP (in
590 the whole compilation unit). Change their values to IPA_BOTTOM, since they
591 most probably get their values from outside of this compilation unit. */
593 ipcp_change_tops_to_bottom (void)
596 struct cgraph_node *node;
600 for (node = cgraph_nodes; node; node = node->next)
602 struct ipa_node_params *info = IPA_NODE_REF (node);
603 count = ipa_get_param_count (info);
604 for (i = 0; i < count; i++)
606 struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
607 if (lat->type == IPA_TOP)
612 fprintf (dump_file, "Forcing param ");
613 print_generic_expr (dump_file, ipa_get_param (info, i), 0);
614 fprintf (dump_file, " of node %s to bottom.\n",
615 cgraph_node_name (node));
617 lat->type = IPA_BOTTOM;
624 /* Interprocedural analysis. The algorithm propagates constants from the
625 caller's parameters to the callee's arguments. */
627 ipcp_propagate_stage (void)
630 struct ipcp_lattice inc_lat = { IPA_BOTTOM, NULL };
631 struct ipcp_lattice new_lat = { IPA_BOTTOM, NULL };
632 struct ipcp_lattice *dest_lat;
633 struct cgraph_edge *cs;
634 struct ipa_jump_func *jump_func;
635 struct ipa_func_list *wl;
638 ipa_check_create_node_params ();
639 ipa_check_create_edge_args ();
641 /* Initialize worklist to contain all functions. */
642 wl = ipa_init_func_list ();
645 struct cgraph_node *node = ipa_pop_func_from_list (&wl);
646 struct ipa_node_params *info = IPA_NODE_REF (node);
648 for (cs = node->callees; cs; cs = cs->next_callee)
650 struct ipa_node_params *callee_info = IPA_NODE_REF (cs->callee);
651 struct ipa_edge_args *args = IPA_EDGE_REF (cs);
653 if (ipa_is_called_with_var_arguments (callee_info))
656 count = ipa_get_cs_argument_count (args);
657 for (i = 0; i < count; i++)
659 jump_func = ipa_get_ith_jump_func (args, i);
660 ipcp_lattice_from_jfunc (info, &inc_lat, jump_func);
661 dest_lat = ipcp_get_lattice (callee_info, i);
662 ipa_lattice_meet (&new_lat, &inc_lat, dest_lat);
663 if (ipcp_lattice_changed (&new_lat, dest_lat))
665 dest_lat->type = new_lat.type;
666 dest_lat->constant = new_lat.constant;
667 ipa_push_func_to_list (&wl, cs->callee);
674 /* Call the constant propagation algorithm and re-call it if necessary
675 (if there are undetermined values left). */
677 ipcp_iterate_stage (void)
679 struct cgraph_node *node;
680 n_cloning_candidates = 0;
683 fprintf (dump_file, "\nIPA iterate stage:\n\n");
684 for (node = cgraph_nodes; node; node = node->next)
686 ipcp_initialize_node_lattices (node);
687 ipcp_compute_node_scale (node);
689 if (dump_file && (dump_flags & TDF_DETAILS))
691 ipcp_print_all_lattices (dump_file);
692 ipcp_function_scale_print (dump_file);
695 ipcp_propagate_stage ();
696 if (ipcp_change_tops_to_bottom ())
697 /* Some lattices have changed from IPA_TOP to IPA_BOTTOM.
698 This change should be propagated. */
700 gcc_assert (n_cloning_candidates);
701 ipcp_propagate_stage ();
705 fprintf (dump_file, "\nIPA lattices after propagation:\n");
706 ipcp_print_all_lattices (dump_file);
707 if (dump_flags & TDF_DETAILS)
708 ipcp_print_profile_data (dump_file);
712 /* Check conditions to forbid constant insertion to function described by
715 ipcp_node_modifiable_p (struct cgraph_node *node)
717 /* Once we will be able to do in-place replacement, we can be more
719 return ipcp_versionable_function_p (node);
722 /* Print count scale data structures. */
724 ipcp_function_scale_print (FILE * f)
726 struct cgraph_node *node;
728 for (node = cgraph_nodes; node; node = node->next)
732 fprintf (f, "printing scale for %s: ", cgraph_node_name (node));
733 fprintf (f, "value is " HOST_WIDE_INT_PRINT_DEC
734 " \n", (HOST_WIDE_INT) ipcp_get_node_scale (node));
738 /* Print counts of all cgraph nodes. */
740 ipcp_print_func_profile_counts (FILE * f)
742 struct cgraph_node *node;
744 for (node = cgraph_nodes; node; node = node->next)
746 fprintf (f, "function %s: ", cgraph_node_name (node));
747 fprintf (f, "count is " HOST_WIDE_INT_PRINT_DEC
748 " \n", (HOST_WIDE_INT) node->count);
752 /* Print counts of all cgraph edges. */
754 ipcp_print_call_profile_counts (FILE * f)
756 struct cgraph_node *node;
757 struct cgraph_edge *cs;
759 for (node = cgraph_nodes; node; node = node->next)
761 for (cs = node->callees; cs; cs = cs->next_callee)
763 fprintf (f, "%s -> %s ", cgraph_node_name (cs->caller),
764 cgraph_node_name (cs->callee));
765 fprintf (f, "count is " HOST_WIDE_INT_PRINT_DEC " \n",
766 (HOST_WIDE_INT) cs->count);
771 /* Print profile info for all functions. */
773 ipcp_print_profile_data (FILE * f)
775 fprintf (f, "\nNODE COUNTS :\n");
776 ipcp_print_func_profile_counts (f);
777 fprintf (f, "\nCS COUNTS stage:\n");
778 ipcp_print_call_profile_counts (f);
781 /* Build and initialize ipa_replace_map struct according to LAT. This struct is
782 processed by versioning, which operates according to the flags set.
783 PARM_TREE is the formal parameter found to be constant. LAT represents the
785 static struct ipa_replace_map *
786 ipcp_create_replace_map (tree parm_tree, struct ipcp_lattice *lat)
788 struct ipa_replace_map *replace_map;
791 replace_map = GGC_NEW (struct ipa_replace_map);
792 const_val = build_const_val (lat, TREE_TYPE (parm_tree));
795 fprintf (dump_file, " replacing param ");
796 print_generic_expr (dump_file, parm_tree, 0);
797 fprintf (dump_file, " with const ");
798 print_generic_expr (dump_file, const_val, 0);
799 fprintf (dump_file, "\n");
801 replace_map->old_tree = parm_tree;
802 replace_map->new_tree = const_val;
803 replace_map->replace_p = true;
804 replace_map->ref_p = false;
809 /* Return true if this callsite should be redirected to the original callee
810 (instead of the cloned one). */
812 ipcp_need_redirect_p (struct cgraph_edge *cs)
814 struct ipa_node_params *orig_callee_info;
816 struct ipa_jump_func *jump_func;
817 struct cgraph_node *node = cs->callee, *orig;
819 if (!n_cloning_candidates)
822 if ((orig = ipcp_get_orig_node (node)) != NULL)
824 if (ipcp_get_orig_node (cs->caller))
827 orig_callee_info = IPA_NODE_REF (node);
828 count = ipa_get_param_count (orig_callee_info);
829 for (i = 0; i < count; i++)
831 struct ipcp_lattice *lat = ipcp_get_lattice (orig_callee_info, i);
832 if (ipcp_lat_is_const (lat))
834 jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
835 if (jump_func->type != IPA_JF_CONST)
843 /* Fix the callsites and the call graph after function cloning was done. */
845 ipcp_update_callgraph (void)
847 struct cgraph_node *node;
849 for (node = cgraph_nodes; node; node = node->next)
850 if (node->analyzed && ipcp_node_is_clone (node))
852 bitmap args_to_skip = BITMAP_ALLOC (NULL);
853 struct cgraph_node *orig_node = ipcp_get_orig_node (node);
854 struct ipa_node_params *info = IPA_NODE_REF (orig_node);
855 int i, count = ipa_get_param_count (info);
856 struct cgraph_edge *cs, *next;
858 for (i = 0; i < count; i++)
860 struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
861 tree parm_tree = ipa_get_param (info, i);
863 /* We can proactively remove obviously unused arguments. */
864 if (is_gimple_reg (parm_tree)
865 && !gimple_default_def (DECL_STRUCT_FUNCTION (orig_node->decl),
868 bitmap_set_bit (args_to_skip, i);
872 if (lat->type == IPA_CONST_VALUE)
873 bitmap_set_bit (args_to_skip, i);
875 for (cs = node->callers; cs; cs = next)
877 next = cs->next_caller;
878 if (!ipcp_node_is_clone (cs->caller) && ipcp_need_redirect_p (cs))
879 cgraph_redirect_edge_callee (cs, orig_node);
884 /* Update profiling info for versioned functions and the functions they were
887 ipcp_update_profiling (void)
889 struct cgraph_node *node, *orig_node;
890 gcov_type scale, scale_complement;
891 struct cgraph_edge *cs;
893 for (node = cgraph_nodes; node; node = node->next)
895 if (ipcp_node_is_clone (node))
897 orig_node = ipcp_get_orig_node (node);
898 scale = ipcp_get_node_scale (orig_node);
899 node->count = orig_node->count * scale / REG_BR_PROB_BASE;
900 scale_complement = REG_BR_PROB_BASE - scale;
902 orig_node->count * scale_complement / REG_BR_PROB_BASE;
903 for (cs = node->callees; cs; cs = cs->next_callee)
904 cs->count = cs->count * scale / REG_BR_PROB_BASE;
905 for (cs = orig_node->callees; cs; cs = cs->next_callee)
906 cs->count = cs->count * scale_complement / REG_BR_PROB_BASE;
911 /* If NODE was cloned, how much would program grow? */
913 ipcp_estimate_growth (struct cgraph_node *node)
915 struct cgraph_edge *cs;
916 int redirectable_node_callers = 0;
917 int removable_args = 0;
918 bool need_original = node->needed;
919 struct ipa_node_params *info;
923 for (cs = node->callers; cs != NULL; cs = cs->next_caller)
924 if (cs->caller == node || !ipcp_need_redirect_p (cs))
925 redirectable_node_callers++;
927 need_original = true;
929 /* If we will be able to fully replace orignal node, we never increase
934 info = IPA_NODE_REF (node);
935 count = ipa_get_param_count (info);
936 for (i = 0; i < count; i++)
938 struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
939 tree parm_tree = ipa_get_param (info, i);
941 /* We can proactively remove obviously unused arguments. */
942 if (is_gimple_reg (parm_tree)
943 && !gimple_default_def (DECL_STRUCT_FUNCTION (node->decl),
947 if (lat->type == IPA_CONST_VALUE)
951 /* We make just very simple estimate of savings for removal of operand from
952 call site. Precise cost is dificult to get, as our size metric counts
953 constants and moves as free. Generally we are looking for cases that
954 small function is called very many times. */
955 growth = node->local.inline_summary.self_size
956 - removable_args * redirectable_node_callers;
963 /* Estimate cost of cloning NODE. */
965 ipcp_estimate_cloning_cost (struct cgraph_node *node)
968 gcov_type count_sum = 1;
969 struct cgraph_edge *e;
972 cost = ipcp_estimate_growth (node) * 1000;
976 fprintf (dump_file, "Versioning of %s will save code size\n",
977 cgraph_node_name (node));
981 for (e = node->callers; e; e = e->next_caller)
982 if (!bitmap_bit_p (dead_nodes, e->caller->uid)
983 && !ipcp_need_redirect_p (e))
985 count_sum += e->count;
986 freq_sum += e->frequency + 1;
990 cost /= count_sum * 1000 / max_count + 1;
992 cost /= freq_sum * 1000 / REG_BR_PROB_BASE + 1;
994 fprintf (dump_file, "Cost of versioning %s is %i, (size: %i, freq: %i)\n",
995 cgraph_node_name (node), cost, node->local.inline_summary.self_size,
1000 /* Return number of live constant parameters. */
1002 ipcp_const_param_count (struct cgraph_node *node)
1004 int const_param = 0;
1005 struct ipa_node_params *info = IPA_NODE_REF (node);
1006 int count = ipa_get_param_count (info);
1009 for (i = 0; i < count; i++)
1011 struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
1012 tree parm_tree = ipa_get_param (info, i);
1013 if (ipcp_lat_is_insertable (lat)
1014 /* Do not count obviously unused arguments. */
1015 && (!is_gimple_reg (parm_tree)
1016 || gimple_default_def (DECL_STRUCT_FUNCTION (node->decl),
1023 /* Propagate the constant parameters found by ipcp_iterate_stage()
1024 to the function's code. */
1026 ipcp_insert_stage (void)
1028 struct cgraph_node *node, *node1 = NULL;
1030 VEC (cgraph_edge_p, heap) * redirect_callers;
1031 VEC (ipa_replace_map_p,gc)* replace_trees;
1032 int node_callers, count;
1034 struct ipa_replace_map *replace_param;
1036 long overall_size = 0, new_size = 0;
1039 ipa_check_create_node_params ();
1040 ipa_check_create_edge_args ();
1042 fprintf (dump_file, "\nIPA insert stage:\n\n");
1044 dead_nodes = BITMAP_ALLOC (NULL);
1046 for (node = cgraph_nodes; node; node = node->next)
1049 if (node->count > max_count)
1050 max_count = node->count;
1051 overall_size += node->local.inline_summary.self_size;
1054 max_new_size = overall_size;
1055 if (max_new_size < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
1056 max_new_size = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
1057 max_new_size = max_new_size * PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH) / 100 + 1;
1059 /* First collect all functions we proved to have constant arguments to heap. */
1060 heap = fibheap_new ();
1061 for (node = cgraph_nodes; node; node = node->next)
1063 struct ipa_node_params *info;
1064 /* Propagation of the constant is forbidden in certain conditions. */
1065 if (!node->analyzed || !ipcp_node_modifiable_p (node))
1067 info = IPA_NODE_REF (node);
1068 if (ipa_is_called_with_var_arguments (info))
1070 if (ipcp_const_param_count (node))
1071 node->aux = fibheap_insert (heap, ipcp_estimate_cloning_cost (node), node);
1074 /* Now clone in priority order until code size growth limits are met or
1076 while (!fibheap_empty (heap))
1078 struct ipa_node_params *info;
1080 bitmap args_to_skip;
1081 struct cgraph_edge *cs;
1083 node = (struct cgraph_node *)fibheap_extract_min (heap);
1086 fprintf (dump_file, "considering function %s\n",
1087 cgraph_node_name (node));
1089 growth = ipcp_estimate_growth (node);
1091 if (new_size + growth > max_new_size)
1094 && optimize_function_for_size_p (DECL_STRUCT_FUNCTION (node->decl)))
1097 fprintf (dump_file, "Not versioning, cold code would grow");
1103 /* Look if original function becomes dead after clonning. */
1104 for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1105 if (cs->caller == node || ipcp_need_redirect_p (cs))
1107 if (!cs && !node->needed)
1108 bitmap_set_bit (dead_nodes, node->uid);
1110 info = IPA_NODE_REF (node);
1111 count = ipa_get_param_count (info);
1113 replace_trees = VEC_alloc (ipa_replace_map_p, gc, 1);
1114 args_to_skip = BITMAP_GGC_ALLOC ();
1115 for (i = 0; i < count; i++)
1117 struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
1118 parm_tree = ipa_get_param (info, i);
1120 /* We can proactively remove obviously unused arguments. */
1121 if (is_gimple_reg (parm_tree)
1122 && !gimple_default_def (DECL_STRUCT_FUNCTION (node->decl),
1125 bitmap_set_bit (args_to_skip, i);
1129 if (lat->type == IPA_CONST_VALUE)
1132 ipcp_create_replace_map (parm_tree, lat);
1133 VEC_safe_push (ipa_replace_map_p, gc, replace_trees, replace_param);
1134 bitmap_set_bit (args_to_skip, i);
1138 /* Compute how many callers node has. */
1140 for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1142 redirect_callers = VEC_alloc (cgraph_edge_p, heap, node_callers);
1143 for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1144 VEC_quick_push (cgraph_edge_p, redirect_callers, cs);
1146 /* Redirecting all the callers of the node to the
1147 new versioned node. */
1149 cgraph_create_virtual_clone (node, redirect_callers, replace_trees,
1151 args_to_skip = NULL;
1152 VEC_free (cgraph_edge_p, heap, redirect_callers);
1153 replace_trees = NULL;
1158 fprintf (dump_file, "versioned function %s with growth %i, overall %i\n",
1159 cgraph_node_name (node), (int)growth, (int)new_size);
1160 ipcp_init_cloned_node (node, node1);
1162 /* TODO: We can use indirect inlning info to produce new calls. */
1165 dump_function_to_file (node1->decl, dump_file, dump_flags);
1167 for (cs = node->callees; cs; cs = cs->next_callee)
1168 if (cs->callee->aux)
1170 fibheap_delete_node (heap, (fibnode_t) cs->callee->aux);
1171 cs->callee->aux = fibheap_insert (heap,
1172 ipcp_estimate_cloning_cost (cs->callee),
1177 while (!fibheap_empty (heap))
1180 fprintf (dump_file, "skipping function %s\n",
1181 cgraph_node_name (node));
1182 node = (struct cgraph_node *) fibheap_extract_min (heap);
1185 fibheap_delete (heap);
1186 BITMAP_FREE (dead_nodes);
1187 ipcp_update_callgraph ();
1188 ipcp_update_profiling ();
1191 /* The IPCP driver. */
1195 cgraph_remove_unreachable_nodes (true,dump_file);
1198 fprintf (dump_file, "\nIPA structures before propagation:\n");
1199 if (dump_flags & TDF_DETAILS)
1200 ipa_print_all_params (dump_file);
1201 ipa_print_all_jump_functions (dump_file);
1203 /* 2. Do the interprocedural propagation. */
1204 ipcp_iterate_stage ();
1205 /* 3. Insert the constants found to the functions. */
1206 ipcp_insert_stage ();
1207 if (dump_file && (dump_flags & TDF_DETAILS))
1209 fprintf (dump_file, "\nProfiling info after insert stage:\n");
1210 ipcp_print_profile_data (dump_file);
1212 /* Free all IPCP structures. */
1213 free_all_ipa_structures_after_ipa_cp ();
1215 fprintf (dump_file, "\nIPA constant propagation end\n");
1219 /* Note function body size. */
1221 ipcp_generate_summary (void)
1224 fprintf (dump_file, "\nIPA constant propagation start:\n");
1225 ipa_check_create_node_params ();
1226 ipa_check_create_edge_args ();
1227 ipa_register_cgraph_hooks ();
1228 /* 1. Call the init stage to initialize
1229 the ipa_node_params and ipa_edge_args structures. */
1233 /* Gate for IPCP optimization. */
1235 cgraph_gate_cp (void)
1240 struct ipa_opt_pass_d pass_ipa_cp =
1245 cgraph_gate_cp, /* gate */
1246 ipcp_driver, /* execute */
1249 0, /* static_pass_number */
1250 TV_IPA_CONSTANT_PROP, /* tv_id */
1251 0, /* properties_required */
1252 0, /* properties_provided */
1253 0, /* properties_destroyed */
1254 0, /* todo_flags_start */
1255 TODO_dump_cgraph | TODO_dump_func |
1256 TODO_remove_functions /* todo_flags_finish */
1258 ipcp_generate_summary, /* generate_summary */
1259 NULL, /* write_summary */
1260 NULL, /* read_summary */
1261 NULL, /* function_read_summary */
1263 NULL, /* function_transform */
1264 NULL, /* variable_transform */