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 /* True when OLD_LAT and NEW_LAT values are not the same. */
284 ipcp_lattice_changed (struct ipcp_lattice *old_lat,
285 struct ipcp_lattice *new_lat)
287 if (old_lat->type == new_lat->type)
289 if (!ipcp_lat_is_const (old_lat))
291 if (ipcp_lats_are_equal (old_lat, new_lat))
297 /* Print all ipcp_lattices of all functions to F. */
299 ipcp_print_all_lattices (FILE * f)
301 struct cgraph_node *node;
304 fprintf (f, "\nLattice:\n");
305 for (node = cgraph_nodes; node; node = node->next)
307 struct ipa_node_params *info;
311 info = IPA_NODE_REF (node);
312 fprintf (f, " Node: %s:\n", cgraph_node_name (node));
313 count = ipa_get_param_count (info);
314 for (i = 0; i < count; i++)
316 struct ipcp_lattice *lat = ipa_get_lattice (info, i);
318 fprintf (f, " param [%d]: ", i);
319 if (lat->type == IPA_CONST_VALUE)
321 tree cst = lat->constant;
322 fprintf (f, "type is CONST ");
323 print_generic_expr (f, cst, 0);
324 if (TREE_CODE (cst) == ADDR_EXPR
325 && TREE_CODE (TREE_OPERAND (cst, 0)) == CONST_DECL)
328 print_generic_expr (f, DECL_INITIAL (TREE_OPERAND (cst, 0)),
332 else if (lat->type == IPA_TOP)
333 fprintf (f, "type is TOP");
335 fprintf (f, "type is BOTTOM");
336 if (ipa_param_cannot_devirtualize_p (info, i))
337 fprintf (f, " - cannot_devirtualize set\n");
338 else if (ipa_param_types_vec_empty (info, i))
339 fprintf (f, " - type list empty\n");
346 /* Return true if ipcp algorithms would allow cloning NODE. */
349 ipcp_versionable_function_p (struct cgraph_node *node)
351 struct cgraph_edge *edge;
353 /* We always version the actual function and redirect through the aliases. */
357 /* There are a number of generic reasons functions cannot be versioned. We
358 also cannot remove parameters if there are type attributes such as fnspec
360 if (!inline_summary (node)->versionable
361 || TYPE_ATTRIBUTES (TREE_TYPE (node->decl)))
364 /* Removing arguments doesn't work if the function takes varargs
365 or use __builtin_apply_args.
366 FIXME: handle this together with can_change_signature flag. */
367 for (edge = node->callees; edge; edge = edge->next_callee)
369 tree t = edge->callee->decl;
370 if (DECL_BUILT_IN_CLASS (t) == BUILT_IN_NORMAL
371 && (DECL_FUNCTION_CODE (t) == BUILT_IN_APPLY_ARGS
372 || DECL_FUNCTION_CODE (t) == BUILT_IN_VA_START))
379 /* Return true if this NODE is viable candidate for cloning. */
381 ipcp_cloning_candidate_p (struct cgraph_node *node)
385 gcov_type direct_call_sum = 0;
386 struct cgraph_edge *e;
388 /* We look through aliases, so we clone the aliased function instead. */
392 /* We never clone functions that are not visible from outside.
393 FIXME: in future we should clone such functions when they are called with
394 different constants, but current ipcp implementation is not good on this.
396 if (cgraph_only_called_directly_p (node) || !node->analyzed)
399 /* When function address is taken, we are pretty sure it will be called in hidden way. */
400 if (node->address_taken)
403 fprintf (dump_file, "Not considering %s for cloning; address is taken.\n",
404 cgraph_node_name (node));
408 if (cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE)
411 fprintf (dump_file, "Not considering %s for cloning; body is overwritable.\n",
412 cgraph_node_name (node));
415 if (!ipcp_versionable_function_p (node))
418 fprintf (dump_file, "Not considering %s for cloning; body is not versionable.\n",
419 cgraph_node_name (node));
422 for (e = node->callers; e; e = e->next_caller)
424 direct_call_sum += e->count;
426 if (cgraph_maybe_hot_edge_p (e))
433 fprintf (dump_file, "Not considering %s for cloning; no direct calls.\n",
434 cgraph_node_name (node));
437 if (inline_summary (node)->self_size < n_calls)
440 fprintf (dump_file, "Considering %s for cloning; code would shrink.\n",
441 cgraph_node_name (node));
445 if (!flag_ipa_cp_clone)
448 fprintf (dump_file, "Not considering %s for cloning; -fipa-cp-clone disabled.\n",
449 cgraph_node_name (node));
453 if (!optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node->decl)))
456 fprintf (dump_file, "Not considering %s for cloning; optimizing it for size.\n",
457 cgraph_node_name (node));
461 /* When profile is available and function is hot, propagate into it even if
462 calls seems cold; constant propagation can improve function's speed
466 if (direct_call_sum > node->count * 90 / 100)
469 fprintf (dump_file, "Considering %s for cloning; usually called directly.\n",
470 cgraph_node_name (node));
477 fprintf (dump_file, "Not considering %s for cloning; no hot calls.\n",
478 cgraph_node_name (node));
482 fprintf (dump_file, "Considering %s for cloning.\n",
483 cgraph_node_name (node));
487 /* Mark parameter with index I of function described by INFO as unsuitable for
488 devirtualization. Return true if it has already been marked so. */
491 ipa_set_param_cannot_devirtualize (struct ipa_node_params *info, int i)
493 bool ret = info->params[i].cannot_devirtualize;
494 info->params[i].cannot_devirtualize = true;
495 if (info->params[i].types)
496 VEC_free (tree, heap, info->params[i].types);
500 /* Initialize ipcp_lattices array. The lattices corresponding to supported
501 types (integers, real types and Fortran constants defined as const_decls)
502 are initialized to IPA_TOP, the rest of them to IPA_BOTTOM. */
504 ipcp_initialize_node_lattices (struct cgraph_node *node)
507 struct ipa_node_params *info = IPA_NODE_REF (node);
508 enum ipa_lattice_type type;
510 if (ipa_is_called_with_var_arguments (info) || node->alias)
512 else if (node->local.local)
514 /* When cloning is allowed, we can assume that externally visible functions
515 are not called. We will compensate this by cloning later. */
516 else if (ipcp_cloning_candidate_p (node))
517 type = IPA_TOP, n_cloning_candidates ++;
521 for (i = 0; i < ipa_get_param_count (info) ; i++)
523 ipa_get_lattice (info, i)->type = type;
524 if (type == IPA_BOTTOM)
525 ipa_set_param_cannot_devirtualize (info, i);
529 /* Build a constant tree with type TREE_TYPE and value according to LAT.
530 Return the tree, or, if it is not possible to convert such value
531 to TREE_TYPE, NULL. */
533 build_const_val (struct ipcp_lattice *lat, tree tree_type)
537 gcc_assert (ipcp_lat_is_const (lat));
540 if (!useless_type_conversion_p (tree_type, TREE_TYPE (val)))
542 if (fold_convertible_p (tree_type, val))
543 return fold_build1 (NOP_EXPR, tree_type, val);
544 else if (TYPE_SIZE (tree_type) == TYPE_SIZE (TREE_TYPE (val)))
545 return fold_build1 (VIEW_CONVERT_EXPR, tree_type, val);
552 /* Compute the proper scale for NODE. It is the ratio between the number of
553 direct calls (represented on the incoming cgraph_edges) and sum of all
554 invocations of NODE (represented as count in cgraph_node).
556 FIXME: This code is wrong. Since the callers can be also clones and
557 the clones are not scaled yet, the sums gets unrealistically high.
558 To properly compute the counts, we would need to do propagation across
559 callgraph (as external call to A might imply call to non-cloned B
560 if A's clone calls cloned B). */
562 ipcp_compute_node_scale (struct cgraph_node *node)
565 struct cgraph_edge *cs;
568 /* Compute sum of all counts of callers. */
569 for (cs = node->callers; cs != NULL; cs = cs->next_caller)
571 /* Work around the unrealistically high sum problem. We just don't want
572 the non-cloned body to have negative or very low frequency. Since
573 majority of execution time will be spent in clones anyway, this should
574 give good enough profile. */
575 if (sum > node->count * 9 / 10)
576 sum = node->count * 9 / 10;
577 if (node->count == 0)
578 ipcp_set_node_scale (node, 0);
580 ipcp_set_node_scale (node, sum * REG_BR_PROB_BASE / node->count);
583 /* Return true if there are some formal parameters whose value is IPA_TOP (in
584 the whole compilation unit). Change their values to IPA_BOTTOM, since they
585 most probably get their values from outside of this compilation unit. */
587 ipcp_change_tops_to_bottom (void)
590 struct cgraph_node *node;
594 for (node = cgraph_nodes; node; node = node->next)
596 struct ipa_node_params *info = IPA_NODE_REF (node);
597 count = ipa_get_param_count (info);
598 for (i = 0; i < count; i++)
600 struct ipcp_lattice *lat = ipa_get_lattice (info, i);
601 if (lat->type == IPA_TOP)
606 fprintf (dump_file, "Forcing param ");
607 print_generic_expr (dump_file, ipa_get_param (info, i), 0);
608 fprintf (dump_file, " of node %s to bottom.\n",
609 cgraph_node_name (node));
611 lat->type = IPA_BOTTOM;
613 if (!ipa_param_cannot_devirtualize_p (info, i)
614 && ipa_param_types_vec_empty (info, i))
617 ipa_set_param_cannot_devirtualize (info, i);
620 fprintf (dump_file, "Marking param ");
621 print_generic_expr (dump_file, ipa_get_param (info, i), 0);
622 fprintf (dump_file, " of node %s as unusable for "
623 "devirtualization.\n",
624 cgraph_node_name (node));
632 /* Insert BINFO to the list of known types of parameter number I of the
633 function described by CALLEE_INFO. Return true iff the type information
634 associated with the callee parameter changed in any way. */
637 ipcp_add_param_type (struct ipa_node_params *callee_info, int i, tree binfo)
641 if (ipa_param_cannot_devirtualize_p (callee_info, i))
644 if (callee_info->params[i].types)
646 count = VEC_length (tree, callee_info->params[i].types);
647 for (j = 0; j < count; j++)
648 if (VEC_index (tree, callee_info->params[i].types, j) == binfo)
652 if (VEC_length (tree, callee_info->params[i].types)
653 == (unsigned) PARAM_VALUE (PARAM_DEVIRT_TYPE_LIST_SIZE))
654 return !ipa_set_param_cannot_devirtualize (callee_info, i);
656 VEC_safe_push (tree, heap, callee_info->params[i].types, binfo);
660 /* Copy known types information for parameter number CALLEE_IDX of CALLEE_INFO
661 from a parameter of CALLER_INFO as described by JF. Return true iff the
662 type information changed in any way. JF must be a pass-through or an
663 ancestor jump function. */
666 ipcp_copy_types (struct ipa_node_params *caller_info,
667 struct ipa_node_params *callee_info,
668 int callee_idx, struct ipa_jump_func *jf)
670 int caller_idx, j, count;
673 if (ipa_param_cannot_devirtualize_p (callee_info, callee_idx))
676 if (jf->type == IPA_JF_PASS_THROUGH)
678 if (jf->value.pass_through.operation != NOP_EXPR)
680 ipa_set_param_cannot_devirtualize (callee_info, callee_idx);
683 caller_idx = jf->value.pass_through.formal_id;
686 caller_idx = jf->value.ancestor.formal_id;
688 if (ipa_param_cannot_devirtualize_p (caller_info, caller_idx))
690 ipa_set_param_cannot_devirtualize (callee_info, callee_idx);
694 if (!caller_info->params[caller_idx].types)
698 count = VEC_length (tree, caller_info->params[caller_idx].types);
699 for (j = 0; j < count; j++)
701 tree binfo = VEC_index (tree, caller_info->params[caller_idx].types, j);
702 if (jf->type == IPA_JF_ANCESTOR)
704 binfo = get_binfo_at_offset (binfo, jf->value.ancestor.offset,
705 jf->value.ancestor.type);
708 ipa_set_param_cannot_devirtualize (callee_info, callee_idx);
712 res |= ipcp_add_param_type (callee_info, callee_idx, binfo);
717 /* Propagate type information for parameter of CALLEE_INFO number I as
718 described by JF. CALLER_INFO describes the caller. Return true iff the
719 type information changed in any way. */
722 ipcp_propagate_types (struct ipa_node_params *caller_info,
723 struct ipa_node_params *callee_info,
724 struct ipa_jump_func *jf, int i)
729 case IPA_JF_CONST_MEMBER_PTR:
733 case IPA_JF_KNOWN_TYPE:
734 return ipcp_add_param_type (callee_info, i, jf->value.base_binfo);
736 case IPA_JF_PASS_THROUGH:
737 case IPA_JF_ANCESTOR:
738 return ipcp_copy_types (caller_info, callee_info, i, jf);
741 /* If we reach this we cannot use this parameter for devirtualization. */
742 return !ipa_set_param_cannot_devirtualize (callee_info, i);
745 /* Interprocedural analysis. The algorithm propagates constants from the
746 caller's parameters to the callee's arguments. */
748 ipcp_propagate_stage (void)
751 struct ipcp_lattice inc_lat = { IPA_BOTTOM, NULL };
752 struct ipcp_lattice new_lat = { IPA_BOTTOM, NULL };
753 struct ipcp_lattice *dest_lat;
754 struct cgraph_edge *cs;
755 struct ipa_jump_func *jump_func;
756 struct ipa_func_list *wl;
759 ipa_check_create_node_params ();
760 ipa_check_create_edge_args ();
762 /* Initialize worklist to contain all functions. */
763 wl = ipa_init_func_list ();
766 struct cgraph_node *node = ipa_pop_func_from_list (&wl);
767 struct ipa_node_params *info = IPA_NODE_REF (node);
769 for (cs = node->callees; cs; cs = cs->next_callee)
771 struct cgraph_node *callee = cgraph_function_or_thunk_node (cs->callee, NULL);
772 struct ipa_node_params *callee_info = IPA_NODE_REF (callee);
773 struct ipa_edge_args *args = IPA_EDGE_REF (cs);
775 if (ipa_is_called_with_var_arguments (callee_info)
776 || !cs->callee->analyzed
777 || ipa_is_called_with_var_arguments (callee_info))
780 count = ipa_get_cs_argument_count (args);
781 for (i = 0; i < count; i++)
783 jump_func = ipa_get_ith_jump_func (args, i);
784 ipa_lattice_from_jfunc (info, &inc_lat, jump_func);
785 dest_lat = ipa_get_lattice (callee_info, i);
786 ipa_lattice_meet (&new_lat, &inc_lat, dest_lat);
787 if (ipcp_lattice_changed (&new_lat, dest_lat))
789 dest_lat->type = new_lat.type;
790 dest_lat->constant = new_lat.constant;
791 ipa_push_func_to_list (&wl, callee);
794 if (ipcp_propagate_types (info, callee_info, jump_func, i))
795 ipa_push_func_to_list (&wl, callee);
801 /* Call the constant propagation algorithm and re-call it if necessary
802 (if there are undetermined values left). */
804 ipcp_iterate_stage (void)
806 struct cgraph_node *node;
807 n_cloning_candidates = 0;
810 fprintf (dump_file, "\nIPA iterate stage:\n\n");
813 ipa_update_after_lto_read ();
815 for (node = cgraph_nodes; node; node = node->next)
817 ipcp_initialize_node_lattices (node);
818 ipcp_compute_node_scale (node);
820 if (dump_file && (dump_flags & TDF_DETAILS))
822 ipcp_print_all_lattices (dump_file);
823 ipcp_function_scale_print (dump_file);
826 ipcp_propagate_stage ();
827 if (ipcp_change_tops_to_bottom ())
828 /* Some lattices have changed from IPA_TOP to IPA_BOTTOM.
829 This change should be propagated. */
831 /*gcc_assert (n_cloning_candidates);*/
832 ipcp_propagate_stage ();
836 fprintf (dump_file, "\nIPA lattices after propagation:\n");
837 ipcp_print_all_lattices (dump_file);
838 if (dump_flags & TDF_DETAILS)
839 ipcp_print_profile_data (dump_file);
843 /* Check conditions to forbid constant insertion to function described by
846 ipcp_node_modifiable_p (struct cgraph_node *node)
848 /* Once we will be able to do in-place replacement, we can be more
850 return ipcp_versionable_function_p (node);
853 /* Print count scale data structures. */
855 ipcp_function_scale_print (FILE * f)
857 struct cgraph_node *node;
859 for (node = cgraph_nodes; node; node = node->next)
863 fprintf (f, "printing scale for %s: ", cgraph_node_name (node));
864 fprintf (f, "value is " HOST_WIDE_INT_PRINT_DEC
865 " \n", (HOST_WIDE_INT) ipcp_get_node_scale (node));
869 /* Print counts of all cgraph nodes. */
871 ipcp_print_func_profile_counts (FILE * f)
873 struct cgraph_node *node;
875 for (node = cgraph_nodes; node; node = node->next)
877 fprintf (f, "function %s: ", cgraph_node_name (node));
878 fprintf (f, "count is " HOST_WIDE_INT_PRINT_DEC
879 " \n", (HOST_WIDE_INT) node->count);
883 /* Print counts of all cgraph edges. */
885 ipcp_print_call_profile_counts (FILE * f)
887 struct cgraph_node *node;
888 struct cgraph_edge *cs;
890 for (node = cgraph_nodes; node; node = node->next)
892 for (cs = node->callees; cs; cs = cs->next_callee)
894 fprintf (f, "%s -> %s ", cgraph_node_name (cs->caller),
895 cgraph_node_name (cs->callee));
896 fprintf (f, "count is " HOST_WIDE_INT_PRINT_DEC " \n",
897 (HOST_WIDE_INT) cs->count);
902 /* Print profile info for all functions. */
904 ipcp_print_profile_data (FILE * f)
906 fprintf (f, "\nNODE COUNTS :\n");
907 ipcp_print_func_profile_counts (f);
908 fprintf (f, "\nCS COUNTS stage:\n");
909 ipcp_print_call_profile_counts (f);
912 /* Build and initialize ipa_replace_map struct according to LAT. This struct is
913 processed by versioning, which operates according to the flags set.
914 PARM_TREE is the formal parameter found to be constant. LAT represents the
916 static struct ipa_replace_map *
917 ipcp_create_replace_map (tree parm_tree, struct ipcp_lattice *lat)
919 struct ipa_replace_map *replace_map;
922 const_val = build_const_val (lat, TREE_TYPE (parm_tree));
923 if (const_val == NULL_TREE)
927 fprintf (dump_file, " const ");
928 print_generic_expr (dump_file, lat->constant, 0);
929 fprintf (dump_file, " can't be converted to param ");
930 print_generic_expr (dump_file, parm_tree, 0);
931 fprintf (dump_file, "\n");
935 replace_map = ggc_alloc_ipa_replace_map ();
938 fprintf (dump_file, " replacing param ");
939 print_generic_expr (dump_file, parm_tree, 0);
940 fprintf (dump_file, " with const ");
941 print_generic_expr (dump_file, const_val, 0);
942 fprintf (dump_file, "\n");
944 replace_map->old_tree = parm_tree;
945 replace_map->new_tree = const_val;
946 replace_map->replace_p = true;
947 replace_map->ref_p = false;
952 /* Return true if this callsite should be redirected to the original callee
953 (instead of the cloned one). */
955 ipcp_need_redirect_p (struct cgraph_edge *cs)
957 struct ipa_node_params *orig_callee_info;
959 struct cgraph_node *node = cgraph_function_or_thunk_node (cs->callee, NULL);
960 struct cgraph_node *orig;
962 if (!n_cloning_candidates)
965 /* We can't redirect anything in thunks, yet. */
966 if (cs->caller->thunk.thunk_p)
969 if ((orig = ipcp_get_orig_node (node)) != NULL)
971 if (ipcp_get_orig_node (cs->caller))
974 orig_callee_info = IPA_NODE_REF (node);
975 count = ipa_get_param_count (orig_callee_info);
976 for (i = 0; i < count; i++)
978 struct ipcp_lattice *lat = ipa_get_lattice (orig_callee_info, i);
979 struct ipa_jump_func *jump_func;
981 jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
982 if ((ipcp_lat_is_const (lat)
983 && jump_func->type != IPA_JF_CONST)
984 || (!ipa_param_cannot_devirtualize_p (orig_callee_info, i)
985 && !ipa_param_types_vec_empty (orig_callee_info, i)
986 && jump_func->type != IPA_JF_CONST
987 && jump_func->type != IPA_JF_KNOWN_TYPE))
994 /* Fix the callsites and the call graph after function cloning was done. */
996 ipcp_update_callgraph (void)
998 struct cgraph_node *node;
1000 for (node = cgraph_nodes; node; node = node->next)
1001 if (node->analyzed && ipcp_node_is_clone (node))
1003 bitmap args_to_skip = NULL;
1004 struct cgraph_node *orig_node = ipcp_get_orig_node (node);
1005 struct ipa_node_params *info = IPA_NODE_REF (orig_node);
1006 int i, count = ipa_get_param_count (info);
1007 struct cgraph_edge *cs, *next;
1009 if (node->local.can_change_signature)
1011 args_to_skip = BITMAP_ALLOC (NULL);
1012 for (i = 0; i < count; i++)
1014 struct ipcp_lattice *lat = ipa_get_lattice (info, i);
1016 /* We can proactively remove obviously unused arguments. */
1017 if (!ipa_is_param_used (info, i))
1019 bitmap_set_bit (args_to_skip, i);
1023 if (lat->type == IPA_CONST_VALUE)
1024 bitmap_set_bit (args_to_skip, i);
1027 for (cs = node->callers; cs; cs = next)
1029 next = cs->next_caller;
1030 if (!ipcp_node_is_clone (cs->caller) && ipcp_need_redirect_p (cs))
1033 fprintf (dump_file, "Redirecting edge %s/%i -> %s/%i "
1035 cgraph_node_name (cs->caller), cs->caller->uid,
1036 cgraph_node_name (cs->callee), cs->callee->uid,
1037 cgraph_node_name (orig_node), orig_node->uid);
1038 cgraph_redirect_edge_callee (cs, orig_node);
1044 /* Update profiling info for versioned functions and the functions they were
1047 ipcp_update_profiling (void)
1049 struct cgraph_node *node, *orig_node;
1050 gcov_type scale, scale_complement;
1051 struct cgraph_edge *cs;
1053 for (node = cgraph_nodes; node; node = node->next)
1055 if (ipcp_node_is_clone (node))
1057 orig_node = ipcp_get_orig_node (node);
1058 scale = ipcp_get_node_scale (orig_node);
1059 node->count = orig_node->count * scale / REG_BR_PROB_BASE;
1060 scale_complement = REG_BR_PROB_BASE - scale;
1062 gcc_assert (scale_complement >= 0);
1064 orig_node->count * scale_complement / REG_BR_PROB_BASE;
1065 for (cs = node->callees; cs; cs = cs->next_callee)
1066 cs->count = cs->count * scale / REG_BR_PROB_BASE;
1067 for (cs = orig_node->callees; cs; cs = cs->next_callee)
1068 cs->count = cs->count * scale_complement / REG_BR_PROB_BASE;
1073 /* If NODE was cloned, how much would program grow? */
1075 ipcp_estimate_growth (struct cgraph_node *node)
1077 struct cgraph_edge *cs;
1078 int redirectable_node_callers = 0;
1079 int removable_args = 0;
1081 = !cgraph_will_be_removed_from_program_if_no_direct_calls (node);
1082 VEC (tree, heap) *known_vals = NULL;
1083 struct ipa_node_params *info;
1087 for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1088 if (cs->caller == node || !ipcp_need_redirect_p (cs))
1089 redirectable_node_callers++;
1091 need_original = true;
1093 /* If we will be able to fully replace original node, we never increase
1098 info = IPA_NODE_REF (node);
1099 count = ipa_get_param_count (info);
1100 VEC_safe_grow_cleared (tree, heap, known_vals, count);
1101 if (node->local.can_change_signature)
1102 for (i = 0; i < count; i++)
1104 struct ipcp_lattice *lat = ipa_get_lattice (info, i);
1106 /* We can proactively remove obviously unused arguments. */
1107 if (!ipa_is_param_used (info, i))
1110 if (lat->type == IPA_CONST_VALUE)
1113 VEC_replace (tree, known_vals, i, lat->constant);
1117 /* We make just very simple estimate of savings for removal of operand from
1118 call site. Precise cost is difficult to get, as our size metric counts
1119 constants and moves as free. Generally we are looking for cases that
1120 small function is called very many times. */
1121 estimate_ipcp_clone_size_and_time (node, known_vals, &growth, NULL);
1122 VEC_free (tree, heap, known_vals);
1124 - removable_args * redirectable_node_callers;
1131 /* Estimate cost of cloning NODE. */
1133 ipcp_estimate_cloning_cost (struct cgraph_node *node)
1136 gcov_type count_sum = 1;
1137 struct cgraph_edge *e;
1140 cost = ipcp_estimate_growth (node) * 1000;
1144 fprintf (dump_file, "Versioning of %s will save code size\n",
1145 cgraph_node_name (node));
1149 for (e = node->callers; e; e = e->next_caller)
1150 if (!bitmap_bit_p (dead_nodes, e->caller->uid)
1151 && !ipcp_need_redirect_p (e))
1153 count_sum += e->count;
1154 freq_sum += e->frequency + 1;
1158 cost /= count_sum * 1000 / max_count + 1;
1160 cost /= freq_sum * 1000 / REG_BR_PROB_BASE + 1;
1162 fprintf (dump_file, "Cost of versioning %s is %i, (size: %i, freq: %i)\n",
1163 cgraph_node_name (node), cost, inline_summary (node)->self_size,
1168 /* Walk indirect calls of NODE and if any polymorphic can be turned into a
1169 direct one now, do so. */
1172 ipcp_process_devirtualization_opportunities (struct cgraph_node *node)
1174 struct ipa_node_params *info = IPA_NODE_REF (node);
1175 struct cgraph_edge *ie, *next_ie;
1177 for (ie = node->indirect_calls; ie; ie = next_ie)
1180 HOST_WIDE_INT token, anc_offset;
1181 tree target, delta, otr_type;
1182 struct ipcp_lattice *lat;
1184 next_ie = ie->next_callee;
1185 if (!ie->indirect_info->polymorphic)
1187 param_index = ie->indirect_info->param_index;
1188 if (param_index == -1)
1191 lat = ipa_get_lattice (info, param_index);
1192 token = ie->indirect_info->otr_token;
1193 anc_offset = ie->indirect_info->anc_offset;
1194 otr_type = ie->indirect_info->otr_type;
1196 if (lat->type == IPA_CONST_VALUE)
1198 tree binfo = gimple_extract_devirt_binfo_from_cst (lat->constant);
1201 binfo = get_binfo_at_offset (binfo, anc_offset, otr_type);
1204 target = gimple_get_virt_method_for_binfo (token, binfo, &delta);
1210 if (ipa_param_cannot_devirtualize_p (info, param_index)
1211 || ipa_param_types_vec_empty (info, param_index))
1214 types_count = VEC_length (tree, info->params[param_index].types);
1215 for (j = 0; j < types_count; j++)
1217 tree binfo = VEC_index (tree, info->params[param_index].types, j);
1220 binfo = get_binfo_at_offset (binfo, anc_offset, otr_type);
1227 t = gimple_get_virt_method_for_binfo (token, binfo, &d);
1238 else if (target != t || !tree_int_cst_equal (delta, d))
1247 ipa_make_edge_direct_to_target (ie, target, delta);
1251 /* Return number of live constant parameters. */
1253 ipcp_const_param_count (struct cgraph_node *node)
1255 int const_param = 0;
1256 struct ipa_node_params *info = IPA_NODE_REF (node);
1257 int count = ipa_get_param_count (info);
1260 for (i = 0; i < count; i++)
1262 struct ipcp_lattice *lat = ipa_get_lattice (info, i);
1263 if ((ipcp_lat_is_insertable (lat)
1264 /* Do not count obviously unused arguments. */
1265 && ipa_is_param_used (info, i))
1266 || (!ipa_param_cannot_devirtualize_p (info, i)
1267 && !ipa_param_types_vec_empty (info, i)))
1273 /* Given that a formal parameter of NODE given by INDEX is known to be constant
1274 CST, try to find any indirect edges that can be made direct and make them
1275 so. Note that INDEX is the number the parameter at the time of analyzing
1276 parameter uses and parameter removals should not be considered for it. (In
1277 fact, the parameter itself has just been removed.) */
1280 ipcp_discover_new_direct_edges (struct cgraph_node *node, int index, tree cst)
1282 struct cgraph_edge *ie, *next_ie;
1284 for (ie = node->indirect_calls; ie; ie = next_ie)
1286 struct cgraph_indirect_call_info *ici = ie->indirect_info;
1288 next_ie = ie->next_callee;
1289 if (ici->param_index != index
1290 || ici->polymorphic)
1293 ipa_make_edge_direct_to_target (ie, cst, NULL_TREE);
1298 /* Propagate the constant parameters found by ipcp_iterate_stage()
1299 to the function's code. */
1301 ipcp_insert_stage (void)
1303 struct cgraph_node *node, *node1 = NULL;
1305 VEC (cgraph_edge_p, heap) * redirect_callers;
1306 VEC (ipa_replace_map_p,gc)* replace_trees;
1309 struct ipa_replace_map *replace_param;
1311 long overall_size = 0, new_size = 0;
1314 ipa_check_create_node_params ();
1315 ipa_check_create_edge_args ();
1317 fprintf (dump_file, "\nIPA insert stage:\n\n");
1319 dead_nodes = BITMAP_ALLOC (NULL);
1321 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
1323 if (node->count > max_count)
1324 max_count = node->count;
1325 overall_size += inline_summary (node)->self_size;
1328 max_new_size = overall_size;
1329 if (max_new_size < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
1330 max_new_size = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
1331 max_new_size = max_new_size * PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH) / 100 + 1;
1333 /* First collect all functions we proved to have constant arguments to
1335 heap = fibheap_new ();
1336 for (node = cgraph_nodes; node; node = node->next)
1338 struct ipa_node_params *info;
1339 /* Propagation of the constant is forbidden in certain conditions. */
1340 if (!node->analyzed || !ipcp_node_modifiable_p (node))
1342 info = IPA_NODE_REF (node);
1343 if (ipa_is_called_with_var_arguments (info))
1345 if (ipcp_const_param_count (node))
1346 node->aux = fibheap_insert (heap, ipcp_estimate_cloning_cost (node),
1350 /* Now clone in priority order until code size growth limits are met or
1352 while (!fibheap_empty (heap))
1354 struct ipa_node_params *info;
1356 bitmap args_to_skip;
1357 struct cgraph_edge *cs;
1359 node = (struct cgraph_node *)fibheap_extract_min (heap);
1362 fprintf (dump_file, "considering function %s\n",
1363 cgraph_node_name (node));
1365 growth = ipcp_estimate_growth (node);
1367 if (new_size + growth > max_new_size)
1370 && cgraph_optimize_for_size_p (node))
1373 fprintf (dump_file, "Not versioning, cold code would grow");
1377 info = IPA_NODE_REF (node);
1378 count = ipa_get_param_count (info);
1380 replace_trees = VEC_alloc (ipa_replace_map_p, gc, 1);
1382 if (node->local.can_change_signature)
1383 args_to_skip = BITMAP_GGC_ALLOC ();
1385 args_to_skip = NULL;
1386 for (i = 0; i < count; i++)
1388 struct ipcp_lattice *lat = ipa_get_lattice (info, i);
1389 parm_tree = ipa_get_param (info, i);
1391 /* We can proactively remove obviously unused arguments. */
1392 if (!ipa_is_param_used (info, i))
1395 bitmap_set_bit (args_to_skip, i);
1399 if (lat->type == IPA_CONST_VALUE)
1402 ipcp_create_replace_map (parm_tree, lat);
1403 if (replace_param == NULL)
1405 VEC_safe_push (ipa_replace_map_p, gc, replace_trees, replace_param);
1407 bitmap_set_bit (args_to_skip, i);
1413 fprintf (dump_file, "Not versioning, some parameters couldn't be replaced");
1419 /* Look if original function becomes dead after cloning. */
1420 for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1421 if (cs->caller == node || ipcp_need_redirect_p (cs))
1423 if (!cs && cgraph_will_be_removed_from_program_if_no_direct_calls (node))
1424 bitmap_set_bit (dead_nodes, node->uid);
1426 redirect_callers = collect_callers_of_node (node);
1428 /* Redirecting all the callers of the node to the
1429 new versioned node. */
1431 cgraph_create_virtual_clone (node, redirect_callers, replace_trees,
1432 args_to_skip, "constprop");
1433 args_to_skip = NULL;
1434 VEC_free (cgraph_edge_p, heap, redirect_callers);
1435 replace_trees = NULL;
1439 ipcp_process_devirtualization_opportunities (node1);
1442 fprintf (dump_file, "versioned function %s with growth %i, overall %i\n",
1443 cgraph_node_name (node), (int)growth, (int)new_size);
1444 ipcp_init_cloned_node (node, node1);
1446 info = IPA_NODE_REF (node);
1447 for (i = 0; i < count; i++)
1449 struct ipcp_lattice *lat = ipa_get_lattice (info, i);
1450 if (lat->type == IPA_CONST_VALUE)
1451 ipcp_discover_new_direct_edges (node1, i, lat->constant);
1455 dump_function_to_file (node1->decl, dump_file, dump_flags);
1457 for (cs = node->callees; cs; cs = cs->next_callee)
1459 struct cgraph_node *callee = cgraph_function_or_thunk_node (cs->callee, NULL);
1462 fibheap_delete_node (heap, (fibnode_t) callee->aux);
1463 callee->aux = fibheap_insert (heap,
1464 ipcp_estimate_cloning_cost (callee),
1470 while (!fibheap_empty (heap))
1473 fprintf (dump_file, "skipping function %s\n",
1474 cgraph_node_name (node));
1475 node = (struct cgraph_node *) fibheap_extract_min (heap);
1478 fibheap_delete (heap);
1479 BITMAP_FREE (dead_nodes);
1480 ipcp_update_callgraph ();
1481 ipcp_update_profiling ();
1484 /* The IPCP driver. */
1488 cgraph_remove_unreachable_nodes (true,dump_file);
1491 fprintf (dump_file, "\nIPA structures before propagation:\n");
1492 if (dump_flags & TDF_DETAILS)
1493 ipa_print_all_params (dump_file);
1494 ipa_print_all_jump_functions (dump_file);
1496 ipa_check_create_node_params ();
1497 ipa_check_create_edge_args ();
1498 /* 2. Do the interprocedural propagation. */
1499 ipcp_iterate_stage ();
1500 /* 3. Insert the constants found to the functions. */
1501 ipcp_insert_stage ();
1502 if (dump_file && (dump_flags & TDF_DETAILS))
1504 fprintf (dump_file, "\nProfiling info after insert stage:\n");
1505 ipcp_print_profile_data (dump_file);
1507 /* Free all IPCP structures. */
1508 ipa_free_all_structures_after_ipa_cp ();
1510 fprintf (dump_file, "\nIPA constant propagation end\n");
1514 /* Initialization and computation of IPCP data structures. This is the initial
1515 intraprocedural analysis of functions, which gathers information to be
1516 propagated later on. */
1519 ipcp_generate_summary (void)
1521 struct cgraph_node *node;
1524 fprintf (dump_file, "\nIPA constant propagation start:\n");
1525 ipa_register_cgraph_hooks ();
1527 /* FIXME: We could propagate through thunks happily and we could be
1528 even able to clone them, if needed. Do that later. */
1529 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
1531 /* Unreachable nodes should have been eliminated before ipcp. */
1532 gcc_assert (node->needed || node->reachable);
1534 inline_summary (node)->versionable = tree_versionable_function_p (node->decl);
1535 ipa_analyze_node (node);
1539 /* Write ipcp summary for nodes in SET. */
1541 ipcp_write_summary (cgraph_node_set set,
1542 varpool_node_set vset ATTRIBUTE_UNUSED)
1544 ipa_prop_write_jump_functions (set);
1547 /* Read ipcp summary. */
1549 ipcp_read_summary (void)
1551 ipa_prop_read_jump_functions ();
1554 /* Gate for IPCP optimization. */
1556 cgraph_gate_cp (void)
1558 /* FIXME: We should remove the optimize check after we ensure we never run
1559 IPA passes when not optimizing. */
1560 return flag_ipa_cp && optimize;
1563 struct ipa_opt_pass_d pass_ipa_cp =
1568 cgraph_gate_cp, /* gate */
1569 ipcp_driver, /* execute */
1572 0, /* static_pass_number */
1573 TV_IPA_CONSTANT_PROP, /* tv_id */
1574 0, /* properties_required */
1575 0, /* properties_provided */
1576 0, /* properties_destroyed */
1577 0, /* todo_flags_start */
1578 TODO_dump_cgraph | TODO_dump_func |
1579 TODO_remove_functions | TODO_ggc_collect /* todo_flags_finish */
1581 ipcp_generate_summary, /* generate_summary */
1582 ipcp_write_summary, /* write_summary */
1583 ipcp_read_summary, /* read_summary */
1584 NULL, /* write_optimization_summary */
1585 NULL, /* read_optimization_summary */
1586 NULL, /* stmt_fixup */
1588 NULL, /* function_transform */
1589 NULL, /* variable_transform */