1 /* Interprocedural constant propagation
2 Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011
3 Free Software Foundation, Inc.
4 Contributed by Razya Ladelsky <RAZYA@il.ibm.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* Interprocedural constant propagation. The aim of interprocedural constant
23 propagation (IPCP) is to find which function's argument has the same
24 constant value in each invocation throughout the whole program. For example,
25 consider the following program:
29 printf ("value is %d",y);
49 The IPCP algorithm will find that g's formal argument y is always called
52 The algorithm used is based on "Interprocedural Constant Propagation", by
53 David Callahan, Keith D Cooper, Ken Kennedy, Linda Torczon, Comp86, pg
56 The optimization is divided into three stages:
58 First stage - intraprocedural analysis
59 =======================================
60 This phase computes jump_function and modification flags.
62 A jump function for a callsite represents the values passed as an actual
63 arguments of a given callsite. There are three types of values:
64 Pass through - the caller's formal parameter is passed as an actual argument.
65 Constant - a constant is passed as an actual argument.
66 Unknown - neither of the above.
68 The jump function info, ipa_jump_func, is stored in ipa_edge_args
69 structure (defined in ipa_prop.h and pointed to by cgraph_node->aux)
70 modified_flags are defined in ipa_node_params structure
71 (defined in ipa_prop.h and pointed to by cgraph_edge->aux).
73 -ipcp_generate_summary() is the first stage driver.
75 Second stage - interprocedural analysis
76 ========================================
77 This phase does the interprocedural constant propagation.
78 It computes lattices for all formal parameters in the program
79 and their value that may be:
81 BOTTOM - non constant.
82 CONSTANT - constant value.
84 Lattice describing a formal parameter p will have a constant value if all
85 callsites invoking this function have the same constant value passed to p.
87 The lattices are stored in ipcp_lattice which is itself in ipa_node_params
88 structure (defined in ipa_prop.h and pointed to by cgraph_edge->aux).
90 -ipcp_iterate_stage() is the second stage driver.
92 Third phase - transformation of function code
93 ============================================
94 Propagates the constant-valued formals into the function.
95 For each function whose parameters are constants, we create its clone.
97 Then we process the clone in two ways:
98 1. We insert an assignment statement 'parameter = const' at the beginning
99 of the cloned function.
100 2. For read-only parameters that do not live in memory, we replace all their
101 uses with the constant.
103 We also need to modify some callsites to call the cloned functions instead
104 of the original ones. For a callsite passing an argument found to be a
105 constant by IPCP, there are two different cases to handle:
106 1. A constant is passed as an argument. In this case the callsite in the
107 should be redirected to call the cloned callee.
108 2. A parameter (of the caller) passed as an argument (pass through
109 argument). In such cases both the caller and the callee have clones and
110 only the callsite in the cloned caller is redirected to call to the
113 This update is done in two steps: First all cloned functions are created
114 during a traversal of the call graph, during which all callsites are
115 redirected to call the cloned function. Then the callsites are traversed
116 and many calls redirected back to fit the description above.
118 -ipcp_insert_stage() is the third phase driver.
121 This pass also performs devirtualization - turns virtual calls into direct
122 ones if it can prove that all invocations of the function call the same
123 callee. This is achieved by building a list of all base types (actually,
124 their BINFOs) that individual parameters can have in an iterative matter
125 just like propagating scalar constants and then examining whether virtual
126 calls which take a parameter as their object fold to the same target for all
127 these types. If we cannot enumerate all types or there is a type which does
128 not have any BINFO associated with it, cannot_devirtualize of the associated
129 parameter descriptor is set which is an equivalent of BOTTOM lattice value
130 in standard IPA constant propagation.
135 #include "coretypes.h"
140 #include "ipa-prop.h"
141 #include "tree-flow.h"
142 #include "tree-pass.h"
145 #include "diagnostic.h"
146 #include "tree-pretty-print.h"
147 #include "tree-dump.h"
148 #include "tree-inline.h"
151 #include "ipa-inline.h"
153 /* Number of functions identified as candidates for cloning. When not cloning
154 we can simplify iterate stage not forcing it to go through the decision
155 on what is profitable and what not. */
156 static int n_cloning_candidates;
158 /* Maximal count found in program. */
159 static gcov_type max_count;
161 /* Cgraph nodes that has been completely replaced by cloning during iterate
162 * stage and will be removed after ipcp is finished. */
163 static bitmap dead_nodes;
165 static void ipcp_print_profile_data (FILE *);
166 static void ipcp_function_scale_print (FILE *);
168 /* Get the original node field of ipa_node_params associated with node NODE. */
169 static inline struct cgraph_node *
170 ipcp_get_orig_node (struct cgraph_node *node)
172 return IPA_NODE_REF (node)->ipcp_orig_node;
175 /* Return true if NODE describes a cloned/versioned function. */
177 ipcp_node_is_clone (struct cgraph_node *node)
179 return (ipcp_get_orig_node (node) != NULL);
182 /* Create ipa_node_params and its data structures for NEW_NODE. Set ORIG_NODE
183 as the ipcp_orig_node field in ipa_node_params. */
185 ipcp_init_cloned_node (struct cgraph_node *orig_node,
186 struct cgraph_node *new_node)
188 gcc_checking_assert (ipa_node_params_vector
189 && (VEC_length (ipa_node_params_t,
190 ipa_node_params_vector)
191 > (unsigned) cgraph_max_uid));
192 gcc_checking_assert (IPA_NODE_REF (new_node)->params);
193 IPA_NODE_REF (new_node)->ipcp_orig_node = orig_node;
196 /* Return scale for NODE. */
197 static inline gcov_type
198 ipcp_get_node_scale (struct cgraph_node *node)
200 return IPA_NODE_REF (node)->count_scale;
203 /* Set COUNT as scale for NODE. */
205 ipcp_set_node_scale (struct cgraph_node *node, gcov_type count)
207 IPA_NODE_REF (node)->count_scale = count;
210 /* Return whether LAT is a constant lattice. */
212 ipcp_lat_is_const (struct ipcp_lattice *lat)
214 if (lat->type == IPA_CONST_VALUE)
220 /* Return whether LAT is a constant lattice that ipa-cp can actually insert
221 into the code (i.e. constants excluding member pointers and pointers). */
223 ipcp_lat_is_insertable (struct ipcp_lattice *lat)
225 return lat->type == IPA_CONST_VALUE;
228 /* Return true if LAT1 and LAT2 are equal. */
230 ipcp_lats_are_equal (struct ipcp_lattice *lat1, struct ipcp_lattice *lat2)
232 gcc_assert (ipcp_lat_is_const (lat1) && ipcp_lat_is_const (lat2));
233 if (lat1->type != lat2->type)
236 if (TREE_CODE (lat1->constant) == ADDR_EXPR
237 && TREE_CODE (lat2->constant) == ADDR_EXPR
238 && TREE_CODE (TREE_OPERAND (lat1->constant, 0)) == CONST_DECL
239 && TREE_CODE (TREE_OPERAND (lat2->constant, 0)) == CONST_DECL)
240 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (lat1->constant, 0)),
241 DECL_INITIAL (TREE_OPERAND (lat2->constant, 0)), 0);
243 return operand_equal_p (lat1->constant, lat2->constant, 0);
246 /* Compute Meet arithmetics:
247 Meet (IPA_BOTTOM, x) = IPA_BOTTOM
249 Meet (const_a,const_b) = IPA_BOTTOM, if const_a != const_b.
250 MEET (const_a,const_b) = const_a, if const_a == const_b.*/
252 ipa_lattice_meet (struct ipcp_lattice *res, struct ipcp_lattice *lat1,
253 struct ipcp_lattice *lat2)
255 if (lat1->type == IPA_BOTTOM || lat2->type == IPA_BOTTOM)
257 res->type = IPA_BOTTOM;
260 if (lat1->type == IPA_TOP)
262 res->type = lat2->type;
263 res->constant = lat2->constant;
266 if (lat2->type == IPA_TOP)
268 res->type = lat1->type;
269 res->constant = lat1->constant;
272 if (!ipcp_lats_are_equal (lat1, lat2))
274 res->type = IPA_BOTTOM;
277 res->type = lat1->type;
278 res->constant = lat1->constant;
281 /* Return the lattice corresponding to the Ith formal parameter of the function
282 described by INFO. */
283 static inline struct ipcp_lattice *
284 ipcp_get_lattice (struct ipa_node_params *info, int i)
286 return &(info->params[i].ipcp_lattice);
289 /* Given the jump function JFUNC, compute the lattice LAT that describes the
290 value coming down the callsite. INFO describes the caller node so that
291 pass-through jump functions can be evaluated. */
293 ipcp_lattice_from_jfunc (struct ipa_node_params *info, struct ipcp_lattice *lat,
294 struct ipa_jump_func *jfunc)
296 if (jfunc->type == IPA_JF_CONST)
298 lat->type = IPA_CONST_VALUE;
299 lat->constant = jfunc->value.constant;
301 else if (jfunc->type == IPA_JF_PASS_THROUGH)
303 struct ipcp_lattice *caller_lat;
306 caller_lat = ipcp_get_lattice (info, jfunc->value.pass_through.formal_id);
307 lat->type = caller_lat->type;
308 if (caller_lat->type != IPA_CONST_VALUE)
310 cst = caller_lat->constant;
312 if (jfunc->value.pass_through.operation != NOP_EXPR)
315 if (TREE_CODE_CLASS (jfunc->value.pass_through.operation)
317 restype = boolean_type_node;
319 restype = TREE_TYPE (cst);
320 cst = fold_binary (jfunc->value.pass_through.operation,
321 restype, cst, jfunc->value.pass_through.operand);
323 if (!cst || !is_gimple_ip_invariant (cst))
324 lat->type = IPA_BOTTOM;
327 else if (jfunc->type == IPA_JF_ANCESTOR)
329 struct ipcp_lattice *caller_lat;
332 caller_lat = ipcp_get_lattice (info, jfunc->value.ancestor.formal_id);
333 lat->type = caller_lat->type;
334 if (caller_lat->type != IPA_CONST_VALUE)
336 if (TREE_CODE (caller_lat->constant) != ADDR_EXPR)
338 /* This can happen when the constant is a NULL pointer. */
339 lat->type = IPA_BOTTOM;
342 t = TREE_OPERAND (caller_lat->constant, 0);
343 t = build_ref_for_offset (EXPR_LOCATION (t), t,
344 jfunc->value.ancestor.offset,
345 jfunc->value.ancestor.type, NULL, false);
346 lat->constant = build_fold_addr_expr (t);
349 lat->type = IPA_BOTTOM;
352 /* True when OLD_LAT and NEW_LAT values are not the same. */
355 ipcp_lattice_changed (struct ipcp_lattice *old_lat,
356 struct ipcp_lattice *new_lat)
358 if (old_lat->type == new_lat->type)
360 if (!ipcp_lat_is_const (old_lat))
362 if (ipcp_lats_are_equal (old_lat, new_lat))
368 /* Print all ipcp_lattices of all functions to F. */
370 ipcp_print_all_lattices (FILE * f)
372 struct cgraph_node *node;
375 fprintf (f, "\nLattice:\n");
376 for (node = cgraph_nodes; node; node = node->next)
378 struct ipa_node_params *info;
382 info = IPA_NODE_REF (node);
383 fprintf (f, " Node: %s:\n", cgraph_node_name (node));
384 count = ipa_get_param_count (info);
385 for (i = 0; i < count; i++)
387 struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
389 fprintf (f, " param [%d]: ", i);
390 if (lat->type == IPA_CONST_VALUE)
392 tree cst = lat->constant;
393 fprintf (f, "type is CONST ");
394 print_generic_expr (f, cst, 0);
395 if (TREE_CODE (cst) == ADDR_EXPR
396 && TREE_CODE (TREE_OPERAND (cst, 0)) == CONST_DECL)
399 print_generic_expr (f, DECL_INITIAL (TREE_OPERAND (cst, 0)),
403 else if (lat->type == IPA_TOP)
404 fprintf (f, "type is TOP");
406 fprintf (f, "type is BOTTOM");
407 if (ipa_param_cannot_devirtualize_p (info, i))
408 fprintf (f, " - cannot_devirtualize set\n");
409 else if (ipa_param_types_vec_empty (info, i))
410 fprintf (f, " - type list empty\n");
417 /* Return true if ipcp algorithms would allow cloning NODE. */
420 ipcp_versionable_function_p (struct cgraph_node *node)
422 struct cgraph_edge *edge;
424 /* There are a number of generic reasons functions cannot be versioned. We
425 also cannot remove parameters if there are type attributes such as fnspec
427 if (!inline_summary (node)->versionable
428 || TYPE_ATTRIBUTES (TREE_TYPE (node->decl)))
431 /* Removing arguments doesn't work if the function takes varargs
432 or use __builtin_apply_args. */
433 for (edge = node->callees; edge; edge = edge->next_callee)
435 tree t = edge->callee->decl;
436 if (DECL_BUILT_IN_CLASS (t) == BUILT_IN_NORMAL
437 && (DECL_FUNCTION_CODE (t) == BUILT_IN_APPLY_ARGS
438 || DECL_FUNCTION_CODE (t) == BUILT_IN_VA_START))
445 /* Return true if this NODE is viable candidate for cloning. */
447 ipcp_cloning_candidate_p (struct cgraph_node *node)
451 gcov_type direct_call_sum = 0;
452 struct cgraph_edge *e;
454 /* We never clone functions that are not visible from outside.
455 FIXME: in future we should clone such functions when they are called with
456 different constants, but current ipcp implementation is not good on this.
458 if (cgraph_only_called_directly_p (node) || !node->analyzed)
461 /* When function address is taken, we are pretty sure it will be called in hidden way. */
462 if (node->address_taken)
465 fprintf (dump_file, "Not considering %s for cloning; address is taken.\n",
466 cgraph_node_name (node));
470 if (cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE)
473 fprintf (dump_file, "Not considering %s for cloning; body is overwritable.\n",
474 cgraph_node_name (node));
477 if (!ipcp_versionable_function_p (node))
480 fprintf (dump_file, "Not considering %s for cloning; body is not versionable.\n",
481 cgraph_node_name (node));
484 for (e = node->callers; e; e = e->next_caller)
486 direct_call_sum += e->count;
488 if (cgraph_maybe_hot_edge_p (e))
495 fprintf (dump_file, "Not considering %s for cloning; no direct calls.\n",
496 cgraph_node_name (node));
499 if (inline_summary (node)->self_size < n_calls)
502 fprintf (dump_file, "Considering %s for cloning; code would shrink.\n",
503 cgraph_node_name (node));
507 if (!flag_ipa_cp_clone)
510 fprintf (dump_file, "Not considering %s for cloning; -fipa-cp-clone disabled.\n",
511 cgraph_node_name (node));
515 if (!optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node->decl)))
518 fprintf (dump_file, "Not considering %s for cloning; optimizing it for size.\n",
519 cgraph_node_name (node));
523 /* When profile is available and function is hot, propagate into it even if
524 calls seems cold; constant propagation can improve function's speed
528 if (direct_call_sum > node->count * 90 / 100)
531 fprintf (dump_file, "Considering %s for cloning; usually called directly.\n",
532 cgraph_node_name (node));
539 fprintf (dump_file, "Not considering %s for cloning; no hot calls.\n",
540 cgraph_node_name (node));
544 fprintf (dump_file, "Considering %s for cloning.\n",
545 cgraph_node_name (node));
549 /* Mark parameter with index I of function described by INFO as unsuitable for
550 devirtualization. Return true if it has already been marked so. */
553 ipa_set_param_cannot_devirtualize (struct ipa_node_params *info, int i)
555 bool ret = info->params[i].cannot_devirtualize;
556 info->params[i].cannot_devirtualize = true;
557 if (info->params[i].types)
558 VEC_free (tree, heap, info->params[i].types);
562 /* Initialize ipcp_lattices array. The lattices corresponding to supported
563 types (integers, real types and Fortran constants defined as const_decls)
564 are initialized to IPA_TOP, the rest of them to IPA_BOTTOM. */
566 ipcp_initialize_node_lattices (struct cgraph_node *node)
569 struct ipa_node_params *info = IPA_NODE_REF (node);
570 enum ipa_lattice_type type;
572 if (ipa_is_called_with_var_arguments (info))
574 else if (node->local.local)
576 /* When cloning is allowed, we can assume that externally visible functions
577 are not called. We will compensate this by cloning later. */
578 else if (ipcp_cloning_candidate_p (node))
579 type = IPA_TOP, n_cloning_candidates ++;
583 for (i = 0; i < ipa_get_param_count (info) ; i++)
585 ipcp_get_lattice (info, i)->type = type;
586 if (type == IPA_BOTTOM)
587 ipa_set_param_cannot_devirtualize (info, i);
591 /* Build a constant tree with type TREE_TYPE and value according to LAT.
592 Return the tree, or, if it is not possible to convert such value
593 to TREE_TYPE, NULL. */
595 build_const_val (struct ipcp_lattice *lat, tree tree_type)
599 gcc_assert (ipcp_lat_is_const (lat));
602 if (!useless_type_conversion_p (tree_type, TREE_TYPE (val)))
604 if (fold_convertible_p (tree_type, val))
605 return fold_build1 (NOP_EXPR, tree_type, val);
606 else if (TYPE_SIZE (tree_type) == TYPE_SIZE (TREE_TYPE (val)))
607 return fold_build1 (VIEW_CONVERT_EXPR, tree_type, val);
614 /* Compute the proper scale for NODE. It is the ratio between the number of
615 direct calls (represented on the incoming cgraph_edges) and sum of all
616 invocations of NODE (represented as count in cgraph_node).
618 FIXME: This code is wrong. Since the callers can be also clones and
619 the clones are not scaled yet, the sums gets unrealistically high.
620 To properly compute the counts, we would need to do propagation across
621 callgraph (as external call to A might imply call to non-cloned B
622 if A's clone calls cloned B). */
624 ipcp_compute_node_scale (struct cgraph_node *node)
627 struct cgraph_edge *cs;
630 /* Compute sum of all counts of callers. */
631 for (cs = node->callers; cs != NULL; cs = cs->next_caller)
633 /* Work around the unrealistically high sum problem. We just don't want
634 the non-cloned body to have negative or very low frequency. Since
635 majority of execution time will be spent in clones anyway, this should
636 give good enough profile. */
637 if (sum > node->count * 9 / 10)
638 sum = node->count * 9 / 10;
639 if (node->count == 0)
640 ipcp_set_node_scale (node, 0);
642 ipcp_set_node_scale (node, sum * REG_BR_PROB_BASE / node->count);
645 /* Return true if there are some formal parameters whose value is IPA_TOP (in
646 the whole compilation unit). Change their values to IPA_BOTTOM, since they
647 most probably get their values from outside of this compilation unit. */
649 ipcp_change_tops_to_bottom (void)
652 struct cgraph_node *node;
656 for (node = cgraph_nodes; node; node = node->next)
658 struct ipa_node_params *info = IPA_NODE_REF (node);
659 count = ipa_get_param_count (info);
660 for (i = 0; i < count; i++)
662 struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
663 if (lat->type == IPA_TOP)
668 fprintf (dump_file, "Forcing param ");
669 print_generic_expr (dump_file, ipa_get_param (info, i), 0);
670 fprintf (dump_file, " of node %s to bottom.\n",
671 cgraph_node_name (node));
673 lat->type = IPA_BOTTOM;
675 if (!ipa_param_cannot_devirtualize_p (info, i)
676 && ipa_param_types_vec_empty (info, i))
679 ipa_set_param_cannot_devirtualize (info, i);
682 fprintf (dump_file, "Marking param ");
683 print_generic_expr (dump_file, ipa_get_param (info, i), 0);
684 fprintf (dump_file, " of node %s as unusable for "
685 "devirtualization.\n",
686 cgraph_node_name (node));
694 /* Insert BINFO to the list of known types of parameter number I of the
695 function described by CALLEE_INFO. Return true iff the type information
696 associated with the callee parameter changed in any way. */
699 ipcp_add_param_type (struct ipa_node_params *callee_info, int i, tree binfo)
703 if (ipa_param_cannot_devirtualize_p (callee_info, i))
706 if (callee_info->params[i].types)
708 count = VEC_length (tree, callee_info->params[i].types);
709 for (j = 0; j < count; j++)
710 if (VEC_index (tree, callee_info->params[i].types, j) == binfo)
714 if (VEC_length (tree, callee_info->params[i].types)
715 == (unsigned) PARAM_VALUE (PARAM_DEVIRT_TYPE_LIST_SIZE))
716 return !ipa_set_param_cannot_devirtualize (callee_info, i);
718 VEC_safe_push (tree, heap, callee_info->params[i].types, binfo);
722 /* Copy known types information for parameter number CALLEE_IDX of CALLEE_INFO
723 from a parameter of CALLER_INFO as described by JF. Return true iff the
724 type information changed in any way. JF must be a pass-through or an
725 ancestor jump function. */
728 ipcp_copy_types (struct ipa_node_params *caller_info,
729 struct ipa_node_params *callee_info,
730 int callee_idx, struct ipa_jump_func *jf)
732 int caller_idx, j, count;
735 if (ipa_param_cannot_devirtualize_p (callee_info, callee_idx))
738 if (jf->type == IPA_JF_PASS_THROUGH)
740 if (jf->value.pass_through.operation != NOP_EXPR)
742 ipa_set_param_cannot_devirtualize (callee_info, callee_idx);
745 caller_idx = jf->value.pass_through.formal_id;
748 caller_idx = jf->value.ancestor.formal_id;
750 if (ipa_param_cannot_devirtualize_p (caller_info, caller_idx))
752 ipa_set_param_cannot_devirtualize (callee_info, callee_idx);
756 if (!caller_info->params[caller_idx].types)
760 count = VEC_length (tree, caller_info->params[caller_idx].types);
761 for (j = 0; j < count; j++)
763 tree binfo = VEC_index (tree, caller_info->params[caller_idx].types, j);
764 if (jf->type == IPA_JF_ANCESTOR)
766 binfo = get_binfo_at_offset (binfo, jf->value.ancestor.offset,
767 jf->value.ancestor.type);
770 ipa_set_param_cannot_devirtualize (callee_info, callee_idx);
774 res |= ipcp_add_param_type (callee_info, callee_idx, binfo);
779 /* Propagate type information for parameter of CALLEE_INFO number I as
780 described by JF. CALLER_INFO describes the caller. Return true iff the
781 type information changed in any way. */
784 ipcp_propagate_types (struct ipa_node_params *caller_info,
785 struct ipa_node_params *callee_info,
786 struct ipa_jump_func *jf, int i)
791 case IPA_JF_CONST_MEMBER_PTR:
795 case IPA_JF_KNOWN_TYPE:
796 return ipcp_add_param_type (callee_info, i, jf->value.base_binfo);
798 case IPA_JF_PASS_THROUGH:
799 case IPA_JF_ANCESTOR:
800 return ipcp_copy_types (caller_info, callee_info, i, jf);
803 /* If we reach this we cannot use this parameter for devirtualization. */
804 return !ipa_set_param_cannot_devirtualize (callee_info, i);
807 /* Interprocedural analysis. The algorithm propagates constants from the
808 caller's parameters to the callee's arguments. */
810 ipcp_propagate_stage (void)
813 struct ipcp_lattice inc_lat = { IPA_BOTTOM, NULL };
814 struct ipcp_lattice new_lat = { IPA_BOTTOM, NULL };
815 struct ipcp_lattice *dest_lat;
816 struct cgraph_edge *cs;
817 struct ipa_jump_func *jump_func;
818 struct ipa_func_list *wl;
821 ipa_check_create_node_params ();
822 ipa_check_create_edge_args ();
824 /* Initialize worklist to contain all functions. */
825 wl = ipa_init_func_list ();
828 struct cgraph_node *node = ipa_pop_func_from_list (&wl);
829 struct ipa_node_params *info = IPA_NODE_REF (node);
831 for (cs = node->callees; cs; cs = cs->next_callee)
833 struct ipa_node_params *callee_info = IPA_NODE_REF (cs->callee);
834 struct ipa_edge_args *args = IPA_EDGE_REF (cs);
836 if (ipa_is_called_with_var_arguments (callee_info)
837 || !cs->callee->analyzed
838 || ipa_is_called_with_var_arguments (callee_info))
841 count = ipa_get_cs_argument_count (args);
842 for (i = 0; i < count; i++)
844 jump_func = ipa_get_ith_jump_func (args, i);
845 ipcp_lattice_from_jfunc (info, &inc_lat, jump_func);
846 dest_lat = ipcp_get_lattice (callee_info, i);
847 ipa_lattice_meet (&new_lat, &inc_lat, dest_lat);
848 if (ipcp_lattice_changed (&new_lat, dest_lat))
850 dest_lat->type = new_lat.type;
851 dest_lat->constant = new_lat.constant;
852 ipa_push_func_to_list (&wl, cs->callee);
855 if (ipcp_propagate_types (info, callee_info, jump_func, i))
856 ipa_push_func_to_list (&wl, cs->callee);
862 /* Call the constant propagation algorithm and re-call it if necessary
863 (if there are undetermined values left). */
865 ipcp_iterate_stage (void)
867 struct cgraph_node *node;
868 n_cloning_candidates = 0;
871 fprintf (dump_file, "\nIPA iterate stage:\n\n");
874 ipa_update_after_lto_read ();
876 for (node = cgraph_nodes; node; node = node->next)
878 ipcp_initialize_node_lattices (node);
879 ipcp_compute_node_scale (node);
881 if (dump_file && (dump_flags & TDF_DETAILS))
883 ipcp_print_all_lattices (dump_file);
884 ipcp_function_scale_print (dump_file);
887 ipcp_propagate_stage ();
888 if (ipcp_change_tops_to_bottom ())
889 /* Some lattices have changed from IPA_TOP to IPA_BOTTOM.
890 This change should be propagated. */
892 gcc_assert (n_cloning_candidates);
893 ipcp_propagate_stage ();
897 fprintf (dump_file, "\nIPA lattices after propagation:\n");
898 ipcp_print_all_lattices (dump_file);
899 if (dump_flags & TDF_DETAILS)
900 ipcp_print_profile_data (dump_file);
904 /* Check conditions to forbid constant insertion to function described by
907 ipcp_node_modifiable_p (struct cgraph_node *node)
909 /* Once we will be able to do in-place replacement, we can be more
911 return ipcp_versionable_function_p (node);
914 /* Print count scale data structures. */
916 ipcp_function_scale_print (FILE * f)
918 struct cgraph_node *node;
920 for (node = cgraph_nodes; node; node = node->next)
924 fprintf (f, "printing scale for %s: ", cgraph_node_name (node));
925 fprintf (f, "value is " HOST_WIDE_INT_PRINT_DEC
926 " \n", (HOST_WIDE_INT) ipcp_get_node_scale (node));
930 /* Print counts of all cgraph nodes. */
932 ipcp_print_func_profile_counts (FILE * f)
934 struct cgraph_node *node;
936 for (node = cgraph_nodes; node; node = node->next)
938 fprintf (f, "function %s: ", cgraph_node_name (node));
939 fprintf (f, "count is " HOST_WIDE_INT_PRINT_DEC
940 " \n", (HOST_WIDE_INT) node->count);
944 /* Print counts of all cgraph edges. */
946 ipcp_print_call_profile_counts (FILE * f)
948 struct cgraph_node *node;
949 struct cgraph_edge *cs;
951 for (node = cgraph_nodes; node; node = node->next)
953 for (cs = node->callees; cs; cs = cs->next_callee)
955 fprintf (f, "%s -> %s ", cgraph_node_name (cs->caller),
956 cgraph_node_name (cs->callee));
957 fprintf (f, "count is " HOST_WIDE_INT_PRINT_DEC " \n",
958 (HOST_WIDE_INT) cs->count);
963 /* Print profile info for all functions. */
965 ipcp_print_profile_data (FILE * f)
967 fprintf (f, "\nNODE COUNTS :\n");
968 ipcp_print_func_profile_counts (f);
969 fprintf (f, "\nCS COUNTS stage:\n");
970 ipcp_print_call_profile_counts (f);
973 /* Build and initialize ipa_replace_map struct according to LAT. This struct is
974 processed by versioning, which operates according to the flags set.
975 PARM_TREE is the formal parameter found to be constant. LAT represents the
977 static struct ipa_replace_map *
978 ipcp_create_replace_map (tree parm_tree, struct ipcp_lattice *lat)
980 struct ipa_replace_map *replace_map;
983 const_val = build_const_val (lat, TREE_TYPE (parm_tree));
984 if (const_val == NULL_TREE)
988 fprintf (dump_file, " const ");
989 print_generic_expr (dump_file, lat->constant, 0);
990 fprintf (dump_file, " can't be converted to param ");
991 print_generic_expr (dump_file, parm_tree, 0);
992 fprintf (dump_file, "\n");
996 replace_map = ggc_alloc_ipa_replace_map ();
999 fprintf (dump_file, " replacing param ");
1000 print_generic_expr (dump_file, parm_tree, 0);
1001 fprintf (dump_file, " with const ");
1002 print_generic_expr (dump_file, const_val, 0);
1003 fprintf (dump_file, "\n");
1005 replace_map->old_tree = parm_tree;
1006 replace_map->new_tree = const_val;
1007 replace_map->replace_p = true;
1008 replace_map->ref_p = false;
1013 /* Return true if this callsite should be redirected to the original callee
1014 (instead of the cloned one). */
1016 ipcp_need_redirect_p (struct cgraph_edge *cs)
1018 struct ipa_node_params *orig_callee_info;
1020 struct cgraph_node *node = cs->callee, *orig;
1022 if (!n_cloning_candidates)
1025 if ((orig = ipcp_get_orig_node (node)) != NULL)
1027 if (ipcp_get_orig_node (cs->caller))
1030 orig_callee_info = IPA_NODE_REF (node);
1031 count = ipa_get_param_count (orig_callee_info);
1032 for (i = 0; i < count; i++)
1034 struct ipcp_lattice *lat = ipcp_get_lattice (orig_callee_info, i);
1035 struct ipa_jump_func *jump_func;
1037 jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
1038 if ((ipcp_lat_is_const (lat)
1039 && jump_func->type != IPA_JF_CONST)
1040 || (!ipa_param_cannot_devirtualize_p (orig_callee_info, i)
1041 && !ipa_param_types_vec_empty (orig_callee_info, i)
1042 && jump_func->type != IPA_JF_CONST
1043 && jump_func->type != IPA_JF_KNOWN_TYPE))
1050 /* Fix the callsites and the call graph after function cloning was done. */
1052 ipcp_update_callgraph (void)
1054 struct cgraph_node *node;
1056 for (node = cgraph_nodes; node; node = node->next)
1057 if (node->analyzed && ipcp_node_is_clone (node))
1059 bitmap args_to_skip = NULL;
1060 struct cgraph_node *orig_node = ipcp_get_orig_node (node);
1061 struct ipa_node_params *info = IPA_NODE_REF (orig_node);
1062 int i, count = ipa_get_param_count (info);
1063 struct cgraph_edge *cs, *next;
1065 if (node->local.can_change_signature)
1067 args_to_skip = BITMAP_ALLOC (NULL);
1068 for (i = 0; i < count; i++)
1070 struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
1072 /* We can proactively remove obviously unused arguments. */
1073 if (!ipa_is_param_used (info, i))
1075 bitmap_set_bit (args_to_skip, i);
1079 if (lat->type == IPA_CONST_VALUE)
1080 bitmap_set_bit (args_to_skip, i);
1083 for (cs = node->callers; cs; cs = next)
1085 next = cs->next_caller;
1086 if (!ipcp_node_is_clone (cs->caller) && ipcp_need_redirect_p (cs))
1089 fprintf (dump_file, "Redirecting edge %s/%i -> %s/%i "
1091 cgraph_node_name (cs->caller), cs->caller->uid,
1092 cgraph_node_name (cs->callee), cs->callee->uid,
1093 cgraph_node_name (orig_node), orig_node->uid);
1094 cgraph_redirect_edge_callee (cs, orig_node);
1100 /* Update profiling info for versioned functions and the functions they were
1103 ipcp_update_profiling (void)
1105 struct cgraph_node *node, *orig_node;
1106 gcov_type scale, scale_complement;
1107 struct cgraph_edge *cs;
1109 for (node = cgraph_nodes; node; node = node->next)
1111 if (ipcp_node_is_clone (node))
1113 orig_node = ipcp_get_orig_node (node);
1114 scale = ipcp_get_node_scale (orig_node);
1115 node->count = orig_node->count * scale / REG_BR_PROB_BASE;
1116 scale_complement = REG_BR_PROB_BASE - scale;
1118 /* Negative scale complement can result from insane profile data
1119 in which the total incoming edge counts in this module is
1120 larger than the callee's entry count. The insane profile data
1121 usually gets generated due to the following reasons:
1123 1) in multithreaded programs, when profile data is dumped
1124 to gcda files in gcov_exit, some other threads are still running.
1125 The profile counters are dumped in bottom up order (call graph).
1126 The caller's BB counters may still be updated while the callee's
1127 counter data is already saved to disk.
1129 2) Comdat functions: comdat functions' profile data are not
1130 allocated in comdat. When a comdat callee function gets inlined
1131 at some callsites after instrumentation, and the remaining calls
1132 to this function resolves to a comdat copy in another module,
1133 the profile counters for this function are split. This can
1134 result in sum of incoming edge counts from this module being
1135 larger than callee instance's entry count. */
1137 if (scale_complement < 0 && flag_profile_correction)
1138 scale_complement = 0;
1141 orig_node->count * scale_complement / REG_BR_PROB_BASE;
1142 for (cs = node->callees; cs; cs = cs->next_callee)
1143 cs->count = cs->count * scale / REG_BR_PROB_BASE;
1144 for (cs = orig_node->callees; cs; cs = cs->next_callee)
1145 cs->count = cs->count * scale_complement / REG_BR_PROB_BASE;
1150 /* If NODE was cloned, how much would program grow? */
1152 ipcp_estimate_growth (struct cgraph_node *node)
1154 struct cgraph_edge *cs;
1155 int redirectable_node_callers = 0;
1156 int removable_args = 0;
1158 = !cgraph_will_be_removed_from_program_if_no_direct_calls (node);
1159 struct ipa_node_params *info;
1163 for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1164 if (cs->caller == node || !ipcp_need_redirect_p (cs))
1165 redirectable_node_callers++;
1167 need_original = true;
1169 /* If we will be able to fully replace original node, we never increase
1174 info = IPA_NODE_REF (node);
1175 count = ipa_get_param_count (info);
1176 if (node->local.can_change_signature)
1177 for (i = 0; i < count; i++)
1179 struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
1181 /* We can proactively remove obviously unused arguments. */
1182 if (!ipa_is_param_used (info, i))
1185 if (lat->type == IPA_CONST_VALUE)
1189 /* We make just very simple estimate of savings for removal of operand from
1190 call site. Precise cost is difficult to get, as our size metric counts
1191 constants and moves as free. Generally we are looking for cases that
1192 small function is called very many times. */
1193 growth = inline_summary (node)->self_size
1194 - removable_args * redirectable_node_callers;
1201 /* Estimate cost of cloning NODE. */
1203 ipcp_estimate_cloning_cost (struct cgraph_node *node)
1206 gcov_type count_sum = 1;
1207 struct cgraph_edge *e;
1210 cost = ipcp_estimate_growth (node) * 1000;
1214 fprintf (dump_file, "Versioning of %s will save code size\n",
1215 cgraph_node_name (node));
1219 for (e = node->callers; e; e = e->next_caller)
1220 if (!bitmap_bit_p (dead_nodes, e->caller->uid)
1221 && !ipcp_need_redirect_p (e))
1223 count_sum += e->count;
1224 freq_sum += e->frequency + 1;
1228 cost /= count_sum * 1000 / max_count + 1;
1230 cost /= freq_sum * 1000 / REG_BR_PROB_BASE + 1;
1232 fprintf (dump_file, "Cost of versioning %s is %i, (size: %i, freq: %i)\n",
1233 cgraph_node_name (node), cost, inline_summary (node)->self_size,
1238 /* Walk indirect calls of NODE and if any polymorphic can be turned into a
1239 direct one now, do so. */
1242 ipcp_process_devirtualization_opportunities (struct cgraph_node *node)
1244 struct ipa_node_params *info = IPA_NODE_REF (node);
1245 struct cgraph_edge *ie, *next_ie;
1247 for (ie = node->indirect_calls; ie; ie = next_ie)
1249 int param_index, types_count, j;
1250 HOST_WIDE_INT token, anc_offset;
1251 tree target, delta, otr_type;
1253 next_ie = ie->next_callee;
1254 if (!ie->indirect_info->polymorphic)
1256 param_index = ie->indirect_info->param_index;
1257 if (param_index == -1
1258 || ipa_param_cannot_devirtualize_p (info, param_index)
1259 || ipa_param_types_vec_empty (info, param_index))
1262 token = ie->indirect_info->otr_token;
1263 anc_offset = ie->indirect_info->anc_offset;
1264 otr_type = ie->indirect_info->otr_type;
1266 types_count = VEC_length (tree, info->params[param_index].types);
1267 for (j = 0; j < types_count; j++)
1269 tree binfo = VEC_index (tree, info->params[param_index].types, j);
1272 binfo = get_binfo_at_offset (binfo, anc_offset, otr_type);
1279 t = gimple_get_virt_method_for_binfo (token, binfo, &d, true);
1290 else if (target != t || !tree_int_cst_equal (delta, d))
1298 ipa_make_edge_direct_to_target (ie, target, delta);
1302 /* Return number of live constant parameters. */
1304 ipcp_const_param_count (struct cgraph_node *node)
1306 int const_param = 0;
1307 struct ipa_node_params *info = IPA_NODE_REF (node);
1308 int count = ipa_get_param_count (info);
1311 for (i = 0; i < count; i++)
1313 struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
1314 if ((ipcp_lat_is_insertable (lat)
1315 /* Do not count obviously unused arguments. */
1316 && ipa_is_param_used (info, i))
1317 || (!ipa_param_cannot_devirtualize_p (info, i)
1318 && !ipa_param_types_vec_empty (info, i)))
1324 /* Given that a formal parameter of NODE given by INDEX is known to be constant
1325 CST, try to find any indirect edges that can be made direct and make them
1326 so. Note that INDEX is the number the parameter at the time of analyzing
1327 parameter uses and parameter removals should not be considered for it. (In
1328 fact, the parameter itself has just been removed.) */
1331 ipcp_discover_new_direct_edges (struct cgraph_node *node, int index, tree cst)
1333 struct cgraph_edge *ie, *next_ie;
1335 for (ie = node->indirect_calls; ie; ie = next_ie)
1337 struct cgraph_indirect_call_info *ici = ie->indirect_info;
1339 next_ie = ie->next_callee;
1340 if (ici->param_index != index
1341 || ici->polymorphic)
1344 ipa_make_edge_direct_to_target (ie, cst, NULL_TREE);
1349 /* Propagate the constant parameters found by ipcp_iterate_stage()
1350 to the function's code. */
1352 ipcp_insert_stage (void)
1354 struct cgraph_node *node, *node1 = NULL;
1356 VEC (cgraph_edge_p, heap) * redirect_callers;
1357 VEC (ipa_replace_map_p,gc)* replace_trees;
1358 int node_callers, count;
1360 struct ipa_replace_map *replace_param;
1362 long overall_size = 0, new_size = 0;
1365 ipa_check_create_node_params ();
1366 ipa_check_create_edge_args ();
1368 fprintf (dump_file, "\nIPA insert stage:\n\n");
1370 dead_nodes = BITMAP_ALLOC (NULL);
1372 for (node = cgraph_nodes; node; node = node->next)
1375 if (node->count > max_count)
1376 max_count = node->count;
1377 overall_size += inline_summary (node)->self_size;
1380 max_new_size = overall_size;
1381 if (max_new_size < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
1382 max_new_size = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
1383 max_new_size = max_new_size * PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH) / 100 + 1;
1385 /* First collect all functions we proved to have constant arguments to
1387 heap = fibheap_new ();
1388 for (node = cgraph_nodes; node; node = node->next)
1390 struct ipa_node_params *info;
1391 /* Propagation of the constant is forbidden in certain conditions. */
1392 if (!node->analyzed || !ipcp_node_modifiable_p (node))
1394 info = IPA_NODE_REF (node);
1395 if (ipa_is_called_with_var_arguments (info))
1397 if (ipcp_const_param_count (node))
1398 node->aux = fibheap_insert (heap, ipcp_estimate_cloning_cost (node),
1402 /* Now clone in priority order until code size growth limits are met or
1404 while (!fibheap_empty (heap))
1406 struct ipa_node_params *info;
1408 bitmap args_to_skip;
1409 struct cgraph_edge *cs;
1411 node = (struct cgraph_node *)fibheap_extract_min (heap);
1414 fprintf (dump_file, "considering function %s\n",
1415 cgraph_node_name (node));
1417 growth = ipcp_estimate_growth (node);
1419 if (new_size + growth > max_new_size)
1422 && cgraph_optimize_for_size_p (node))
1425 fprintf (dump_file, "Not versioning, cold code would grow");
1429 info = IPA_NODE_REF (node);
1430 count = ipa_get_param_count (info);
1432 replace_trees = VEC_alloc (ipa_replace_map_p, gc, 1);
1434 if (node->local.can_change_signature)
1435 args_to_skip = BITMAP_GGC_ALLOC ();
1437 args_to_skip = NULL;
1438 for (i = 0; i < count; i++)
1440 struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
1441 parm_tree = ipa_get_param (info, i);
1443 /* We can proactively remove obviously unused arguments. */
1444 if (!ipa_is_param_used (info, i))
1447 bitmap_set_bit (args_to_skip, i);
1451 if (lat->type == IPA_CONST_VALUE)
1454 ipcp_create_replace_map (parm_tree, lat);
1455 if (replace_param == NULL)
1457 VEC_safe_push (ipa_replace_map_p, gc, replace_trees, replace_param);
1459 bitmap_set_bit (args_to_skip, i);
1465 fprintf (dump_file, "Not versioning, some parameters couldn't be replaced");
1471 /* Look if original function becomes dead after cloning. */
1472 for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1473 if (cs->caller == node || ipcp_need_redirect_p (cs))
1475 if (!cs && cgraph_will_be_removed_from_program_if_no_direct_calls (node))
1476 bitmap_set_bit (dead_nodes, node->uid);
1478 /* Compute how many callers node has. */
1480 for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1482 redirect_callers = VEC_alloc (cgraph_edge_p, heap, node_callers);
1483 for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1484 if (!cs->indirect_inlining_edge)
1485 VEC_quick_push (cgraph_edge_p, redirect_callers, cs);
1487 /* Redirecting all the callers of the node to the
1488 new versioned node. */
1490 cgraph_create_virtual_clone (node, redirect_callers, replace_trees,
1491 args_to_skip, "constprop");
1492 args_to_skip = NULL;
1493 VEC_free (cgraph_edge_p, heap, redirect_callers);
1494 replace_trees = NULL;
1498 ipcp_process_devirtualization_opportunities (node1);
1501 fprintf (dump_file, "versioned function %s with growth %i, overall %i\n",
1502 cgraph_node_name (node), (int)growth, (int)new_size);
1503 ipcp_init_cloned_node (node, node1);
1505 info = IPA_NODE_REF (node);
1506 for (i = 0; i < count; i++)
1508 struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
1509 if (lat->type == IPA_CONST_VALUE)
1510 ipcp_discover_new_direct_edges (node1, i, lat->constant);
1514 dump_function_to_file (node1->decl, dump_file, dump_flags);
1516 for (cs = node->callees; cs; cs = cs->next_callee)
1517 if (cs->callee->aux)
1519 fibheap_delete_node (heap, (fibnode_t) cs->callee->aux);
1520 cs->callee->aux = fibheap_insert (heap,
1521 ipcp_estimate_cloning_cost (cs->callee),
1526 while (!fibheap_empty (heap))
1529 fprintf (dump_file, "skipping function %s\n",
1530 cgraph_node_name (node));
1531 node = (struct cgraph_node *) fibheap_extract_min (heap);
1534 fibheap_delete (heap);
1535 BITMAP_FREE (dead_nodes);
1536 ipcp_update_callgraph ();
1537 ipcp_update_profiling ();
1540 /* The IPCP driver. */
1544 cgraph_remove_unreachable_nodes (true,dump_file);
1547 fprintf (dump_file, "\nIPA structures before propagation:\n");
1548 if (dump_flags & TDF_DETAILS)
1549 ipa_print_all_params (dump_file);
1550 ipa_print_all_jump_functions (dump_file);
1552 ipa_check_create_node_params ();
1553 ipa_check_create_edge_args ();
1554 /* 2. Do the interprocedural propagation. */
1555 ipcp_iterate_stage ();
1556 /* 3. Insert the constants found to the functions. */
1557 ipcp_insert_stage ();
1558 if (dump_file && (dump_flags & TDF_DETAILS))
1560 fprintf (dump_file, "\nProfiling info after insert stage:\n");
1561 ipcp_print_profile_data (dump_file);
1563 /* Free all IPCP structures. */
1564 ipa_free_all_structures_after_ipa_cp ();
1566 fprintf (dump_file, "\nIPA constant propagation end\n");
1570 /* Initialization and computation of IPCP data structures. This is the initial
1571 intraprocedural analysis of functions, which gathers information to be
1572 propagated later on. */
1575 ipcp_generate_summary (void)
1577 struct cgraph_node *node;
1580 fprintf (dump_file, "\nIPA constant propagation start:\n");
1581 ipa_register_cgraph_hooks ();
1583 for (node = cgraph_nodes; node; node = node->next)
1586 /* Unreachable nodes should have been eliminated before ipcp. */
1587 gcc_assert (node->needed || node->reachable);
1589 inline_summary (node)->versionable = tree_versionable_function_p (node->decl);
1590 ipa_analyze_node (node);
1594 /* Write ipcp summary for nodes in SET. */
1596 ipcp_write_summary (cgraph_node_set set,
1597 varpool_node_set vset ATTRIBUTE_UNUSED)
1599 ipa_prop_write_jump_functions (set);
1602 /* Read ipcp summary. */
1604 ipcp_read_summary (void)
1606 ipa_prop_read_jump_functions ();
1609 /* Gate for IPCP optimization. */
1611 cgraph_gate_cp (void)
1613 /* FIXME: We should remove the optimize check after we ensure we never run
1614 IPA passes when not optimizing. */
1615 return flag_ipa_cp && optimize;
1618 struct ipa_opt_pass_d pass_ipa_cp =
1623 cgraph_gate_cp, /* gate */
1624 ipcp_driver, /* execute */
1627 0, /* static_pass_number */
1628 TV_IPA_CONSTANT_PROP, /* tv_id */
1629 0, /* properties_required */
1630 0, /* properties_provided */
1631 0, /* properties_destroyed */
1632 0, /* todo_flags_start */
1633 TODO_dump_cgraph | TODO_dump_func |
1634 TODO_remove_functions | TODO_ggc_collect /* todo_flags_finish */
1636 ipcp_generate_summary, /* generate_summary */
1637 ipcp_write_summary, /* write_summary */
1638 ipcp_read_summary, /* read_summary */
1639 NULL, /* write_optimization_summary */
1640 NULL, /* read_optimization_summary */
1641 NULL, /* stmt_fixup */
1643 NULL, /* function_transform */
1644 NULL, /* variable_transform */