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
;
295 caller_lat
= ipcp_get_lattice (info
, jfunc
->value
.pass_through
.formal_id
);
296 lat
->type
= caller_lat
->type
;
297 if (caller_lat
->type
!= IPA_CONST_VALUE
)
299 cst
= caller_lat
->constant
;
301 if (jfunc
->value
.pass_through
.operation
!= NOP_EXPR
)
304 if (TREE_CODE_CLASS (jfunc
->value
.pass_through
.operation
)
306 restype
= boolean_type_node
;
308 restype
= TREE_TYPE (cst
);
309 cst
= fold_binary (jfunc
->value
.pass_through
.operation
,
310 restype
, cst
, jfunc
->value
.pass_through
.operand
);
312 if (!cst
|| !is_gimple_ip_invariant (cst
))
313 lat
->type
= IPA_BOTTOM
;
316 else if (jfunc
->type
== IPA_JF_ANCESTOR
)
318 struct ipcp_lattice
*caller_lat
;
322 caller_lat
= ipcp_get_lattice (info
, jfunc
->value
.ancestor
.formal_id
);
323 lat
->type
= caller_lat
->type
;
324 if (caller_lat
->type
!= IPA_CONST_VALUE
)
326 if (TREE_CODE (caller_lat
->constant
) != ADDR_EXPR
)
328 /* This can happen when the constant is a NULL pointer. */
329 lat
->type
= IPA_BOTTOM
;
332 t
= TREE_OPERAND (caller_lat
->constant
, 0);
333 ok
= build_ref_for_offset (&t
, TREE_TYPE (t
),
334 jfunc
->value
.ancestor
.offset
,
335 jfunc
->value
.ancestor
.type
, false);
338 lat
->type
= IPA_BOTTOM
;
339 lat
->constant
= NULL_TREE
;
342 lat
->constant
= build_fold_addr_expr (t
);
345 lat
->type
= IPA_BOTTOM
;
348 /* True when OLD_LAT and NEW_LAT values are not the same. */
351 ipcp_lattice_changed (struct ipcp_lattice
*old_lat
,
352 struct ipcp_lattice
*new_lat
)
354 if (old_lat
->type
== new_lat
->type
)
356 if (!ipcp_lat_is_const (old_lat
))
358 if (ipcp_lats_are_equal (old_lat
, new_lat
))
364 /* Print all ipcp_lattices of all functions to F. */
366 ipcp_print_all_lattices (FILE * f
)
368 struct cgraph_node
*node
;
371 fprintf (f
, "\nLattice:\n");
372 for (node
= cgraph_nodes
; node
; node
= node
->next
)
374 struct ipa_node_params
*info
;
378 info
= IPA_NODE_REF (node
);
379 fprintf (f
, " Node: %s:\n", cgraph_node_name (node
));
380 count
= ipa_get_param_count (info
);
381 for (i
= 0; i
< count
; i
++)
383 struct ipcp_lattice
*lat
= ipcp_get_lattice (info
, i
);
385 fprintf (f
, " param [%d]: ", i
);
386 if (lat
->type
== IPA_CONST_VALUE
)
388 fprintf (f
, "type is CONST ");
389 print_generic_expr (f
, lat
->constant
, 0);
392 else if (lat
->type
== IPA_TOP
)
393 fprintf (f
, "type is TOP\n");
395 fprintf (f
, "type is BOTTOM\n");
400 /* Return true if ipcp algorithms would allow cloning NODE. */
403 ipcp_versionable_function_p (struct cgraph_node
*node
)
405 tree decl
= node
->decl
;
408 /* There are a number of generic reasons functions cannot be versioned. */
409 if (!tree_versionable_function_p (decl
))
412 /* Removing arguments doesn't work if the function takes varargs. */
413 if (DECL_STRUCT_FUNCTION (decl
)->stdarg
)
416 /* Removing arguments doesn't work if we use __builtin_apply_args. */
417 FOR_EACH_BB_FN (bb
, DECL_STRUCT_FUNCTION (decl
))
419 gimple_stmt_iterator gsi
;
420 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
422 const_gimple stmt
= gsi_stmt (gsi
);
425 if (!is_gimple_call (stmt
))
427 t
= gimple_call_fndecl (stmt
);
430 if (DECL_BUILT_IN_CLASS (t
) == BUILT_IN_NORMAL
431 && DECL_FUNCTION_CODE (t
) == BUILT_IN_APPLY_ARGS
)
439 /* Return true if this NODE is viable candidate for cloning. */
441 ipcp_cloning_candidate_p (struct cgraph_node
*node
)
445 gcov_type direct_call_sum
= 0;
446 struct cgraph_edge
*e
;
448 /* We never clone functions that are not visible from outside.
449 FIXME: in future we should clone such functions when they are called with
450 different constants, but current ipcp implementation is not good on this.
452 if (cgraph_only_called_directly_p (node
) || !node
->analyzed
)
455 if (cgraph_function_body_availability (node
) <= AVAIL_OVERWRITABLE
)
458 fprintf (dump_file
, "Not considering %s for cloning; body is overwrittable.\n",
459 cgraph_node_name (node
));
462 if (!ipcp_versionable_function_p (node
))
465 fprintf (dump_file
, "Not considering %s for cloning; body is not versionable.\n",
466 cgraph_node_name (node
));
469 for (e
= node
->callers
; e
; e
= e
->next_caller
)
471 direct_call_sum
+= e
->count
;
473 if (cgraph_maybe_hot_edge_p (e
))
480 fprintf (dump_file
, "Not considering %s for cloning; no direct calls.\n",
481 cgraph_node_name (node
));
484 if (node
->local
.inline_summary
.self_size
< n_calls
)
487 fprintf (dump_file
, "Considering %s for cloning; code would shrink.\n",
488 cgraph_node_name (node
));
492 if (!flag_ipa_cp_clone
)
495 fprintf (dump_file
, "Not considering %s for cloning; -fipa-cp-clone disabled.\n",
496 cgraph_node_name (node
));
500 if (!optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node
->decl
)))
503 fprintf (dump_file
, "Not considering %s for cloning; optimizing it for size.\n",
504 cgraph_node_name (node
));
508 /* When profile is available and function is hot, propagate into it even if
509 calls seems cold; constant propagation can improve function's speed
513 if (direct_call_sum
> node
->count
* 90 / 100)
516 fprintf (dump_file
, "Considering %s for cloning; usually called directly.\n",
517 cgraph_node_name (node
));
524 fprintf (dump_file
, "Not considering %s for cloning; no hot calls.\n",
525 cgraph_node_name (node
));
529 fprintf (dump_file
, "Considering %s for cloning.\n",
530 cgraph_node_name (node
));
534 /* Initialize ipcp_lattices array. The lattices corresponding to supported
535 types (integers, real types and Fortran constants defined as const_decls)
536 are initialized to IPA_TOP, the rest of them to IPA_BOTTOM. */
538 ipcp_initialize_node_lattices (struct cgraph_node
*node
)
541 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
542 enum ipa_lattice_type type
;
544 if (ipa_is_called_with_var_arguments (info
))
546 else if (cgraph_only_called_directly_p (node
))
548 /* When cloning is allowed, we can assume that externally visible functions
549 are not called. We will compensate this by cloning later. */
550 else if (ipcp_cloning_candidate_p (node
))
551 type
= IPA_TOP
, n_cloning_candidates
++;
555 for (i
= 0; i
< ipa_get_param_count (info
) ; i
++)
556 ipcp_get_lattice (info
, i
)->type
= type
;
559 /* build INTEGER_CST tree with type TREE_TYPE and value according to LAT.
562 build_const_val (struct ipcp_lattice
*lat
, tree tree_type
)
566 gcc_assert (ipcp_lat_is_const (lat
));
569 if (!useless_type_conversion_p (tree_type
, TREE_TYPE (val
)))
571 if (fold_convertible_p (tree_type
, val
))
572 return fold_build1 (NOP_EXPR
, tree_type
, val
);
574 return fold_build1 (VIEW_CONVERT_EXPR
, tree_type
, val
);
579 /* Compute the proper scale for NODE. It is the ratio between the number of
580 direct calls (represented on the incoming cgraph_edges) and sum of all
581 invocations of NODE (represented as count in cgraph_node). */
583 ipcp_compute_node_scale (struct cgraph_node
*node
)
586 struct cgraph_edge
*cs
;
589 /* Compute sum of all counts of callers. */
590 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
592 if (node
->count
== 0)
593 ipcp_set_node_scale (node
, 0);
595 ipcp_set_node_scale (node
, sum
* REG_BR_PROB_BASE
/ node
->count
);
598 /* Initialization and computation of IPCP data structures. This is the initial
599 intraprocedural analysis of functions, which gathers information to be
600 propagated later on. */
602 ipcp_init_stage (void)
604 struct cgraph_node
*node
;
605 struct cgraph_edge
*cs
;
607 for (node
= cgraph_nodes
; node
; node
= node
->next
)
609 ipcp_analyze_node (node
);
610 for (node
= cgraph_nodes
; node
; node
= node
->next
)
614 /* building jump functions */
615 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
617 /* We do not need to bother analyzing calls to unknown
618 functions unless they may become known during lto/whopr. */
619 if (!cs
->callee
->analyzed
&& !flag_lto
&& !flag_whopr
)
621 ipa_count_arguments (cs
);
622 if (ipa_get_cs_argument_count (IPA_EDGE_REF (cs
))
623 != ipa_get_param_count (IPA_NODE_REF (cs
->callee
)))
625 /* Handle cases of functions with
626 a variable number of parameters. */
627 ipa_set_called_with_variable_arg (IPA_NODE_REF (cs
->callee
));
628 if (flag_indirect_inlining
)
629 ipa_compute_jump_functions (cs
);
632 ipa_compute_jump_functions (cs
);
637 /* Return true if there are some formal parameters whose value is IPA_TOP (in
638 the whole compilation unit). Change their values to IPA_BOTTOM, since they
639 most probably get their values from outside of this compilation unit. */
641 ipcp_change_tops_to_bottom (void)
644 struct cgraph_node
*node
;
648 for (node
= cgraph_nodes
; node
; node
= node
->next
)
650 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
651 count
= ipa_get_param_count (info
);
652 for (i
= 0; i
< count
; i
++)
654 struct ipcp_lattice
*lat
= ipcp_get_lattice (info
, i
);
655 if (lat
->type
== IPA_TOP
)
660 fprintf (dump_file
, "Forcing param ");
661 print_generic_expr (dump_file
, ipa_get_param (info
, i
), 0);
662 fprintf (dump_file
, " of node %s to bottom.\n",
663 cgraph_node_name (node
));
665 lat
->type
= IPA_BOTTOM
;
672 /* Interprocedural analysis. The algorithm propagates constants from the
673 caller's parameters to the callee's arguments. */
675 ipcp_propagate_stage (void)
678 struct ipcp_lattice inc_lat
= { IPA_BOTTOM
, NULL
};
679 struct ipcp_lattice new_lat
= { IPA_BOTTOM
, NULL
};
680 struct ipcp_lattice
*dest_lat
;
681 struct cgraph_edge
*cs
;
682 struct ipa_jump_func
*jump_func
;
683 struct ipa_func_list
*wl
;
686 ipa_check_create_node_params ();
687 ipa_check_create_edge_args ();
689 /* Initialize worklist to contain all functions. */
690 wl
= ipa_init_func_list ();
693 struct cgraph_node
*node
= ipa_pop_func_from_list (&wl
);
694 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
696 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
698 struct ipa_node_params
*callee_info
= IPA_NODE_REF (cs
->callee
);
699 struct ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
701 if (ipa_is_called_with_var_arguments (callee_info
)
702 || !cs
->callee
->analyzed
703 || ipa_is_called_with_var_arguments (callee_info
))
706 count
= ipa_get_cs_argument_count (args
);
707 for (i
= 0; i
< count
; i
++)
709 jump_func
= ipa_get_ith_jump_func (args
, i
);
710 ipcp_lattice_from_jfunc (info
, &inc_lat
, jump_func
);
711 dest_lat
= ipcp_get_lattice (callee_info
, i
);
712 ipa_lattice_meet (&new_lat
, &inc_lat
, dest_lat
);
713 if (ipcp_lattice_changed (&new_lat
, dest_lat
))
715 dest_lat
->type
= new_lat
.type
;
716 dest_lat
->constant
= new_lat
.constant
;
717 ipa_push_func_to_list (&wl
, cs
->callee
);
724 /* Call the constant propagation algorithm and re-call it if necessary
725 (if there are undetermined values left). */
727 ipcp_iterate_stage (void)
729 struct cgraph_node
*node
;
730 n_cloning_candidates
= 0;
733 fprintf (dump_file
, "\nIPA iterate stage:\n\n");
736 ipa_update_after_lto_read ();
738 for (node
= cgraph_nodes
; node
; node
= node
->next
)
740 ipcp_initialize_node_lattices (node
);
741 ipcp_compute_node_scale (node
);
743 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
745 ipcp_print_all_lattices (dump_file
);
746 ipcp_function_scale_print (dump_file
);
749 ipcp_propagate_stage ();
750 if (ipcp_change_tops_to_bottom ())
751 /* Some lattices have changed from IPA_TOP to IPA_BOTTOM.
752 This change should be propagated. */
754 gcc_assert (n_cloning_candidates
);
755 ipcp_propagate_stage ();
759 fprintf (dump_file
, "\nIPA lattices after propagation:\n");
760 ipcp_print_all_lattices (dump_file
);
761 if (dump_flags
& TDF_DETAILS
)
762 ipcp_print_profile_data (dump_file
);
766 /* Check conditions to forbid constant insertion to function described by
769 ipcp_node_modifiable_p (struct cgraph_node
*node
)
771 /* Once we will be able to do in-place replacement, we can be more
773 return ipcp_versionable_function_p (node
);
776 /* Print count scale data structures. */
778 ipcp_function_scale_print (FILE * f
)
780 struct cgraph_node
*node
;
782 for (node
= cgraph_nodes
; node
; node
= node
->next
)
786 fprintf (f
, "printing scale for %s: ", cgraph_node_name (node
));
787 fprintf (f
, "value is " HOST_WIDE_INT_PRINT_DEC
788 " \n", (HOST_WIDE_INT
) ipcp_get_node_scale (node
));
792 /* Print counts of all cgraph nodes. */
794 ipcp_print_func_profile_counts (FILE * f
)
796 struct cgraph_node
*node
;
798 for (node
= cgraph_nodes
; node
; node
= node
->next
)
800 fprintf (f
, "function %s: ", cgraph_node_name (node
));
801 fprintf (f
, "count is " HOST_WIDE_INT_PRINT_DEC
802 " \n", (HOST_WIDE_INT
) node
->count
);
806 /* Print counts of all cgraph edges. */
808 ipcp_print_call_profile_counts (FILE * f
)
810 struct cgraph_node
*node
;
811 struct cgraph_edge
*cs
;
813 for (node
= cgraph_nodes
; node
; node
= node
->next
)
815 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
817 fprintf (f
, "%s -> %s ", cgraph_node_name (cs
->caller
),
818 cgraph_node_name (cs
->callee
));
819 fprintf (f
, "count is " HOST_WIDE_INT_PRINT_DEC
" \n",
820 (HOST_WIDE_INT
) cs
->count
);
825 /* Print profile info for all functions. */
827 ipcp_print_profile_data (FILE * f
)
829 fprintf (f
, "\nNODE COUNTS :\n");
830 ipcp_print_func_profile_counts (f
);
831 fprintf (f
, "\nCS COUNTS stage:\n");
832 ipcp_print_call_profile_counts (f
);
835 /* Build and initialize ipa_replace_map struct according to LAT. This struct is
836 processed by versioning, which operates according to the flags set.
837 PARM_TREE is the formal parameter found to be constant. LAT represents the
839 static struct ipa_replace_map
*
840 ipcp_create_replace_map (tree parm_tree
, struct ipcp_lattice
*lat
)
842 struct ipa_replace_map
*replace_map
;
845 replace_map
= GGC_NEW (struct ipa_replace_map
);
846 const_val
= build_const_val (lat
, TREE_TYPE (parm_tree
));
849 fprintf (dump_file
, " replacing param ");
850 print_generic_expr (dump_file
, parm_tree
, 0);
851 fprintf (dump_file
, " with const ");
852 print_generic_expr (dump_file
, const_val
, 0);
853 fprintf (dump_file
, "\n");
855 replace_map
->old_tree
= parm_tree
;
856 replace_map
->new_tree
= const_val
;
857 replace_map
->replace_p
= true;
858 replace_map
->ref_p
= false;
863 /* Return true if this callsite should be redirected to the original callee
864 (instead of the cloned one). */
866 ipcp_need_redirect_p (struct cgraph_edge
*cs
)
868 struct ipa_node_params
*orig_callee_info
;
870 struct ipa_jump_func
*jump_func
;
871 struct cgraph_node
*node
= cs
->callee
, *orig
;
873 if (!n_cloning_candidates
)
876 if ((orig
= ipcp_get_orig_node (node
)) != NULL
)
878 if (ipcp_get_orig_node (cs
->caller
))
881 orig_callee_info
= IPA_NODE_REF (node
);
882 count
= ipa_get_param_count (orig_callee_info
);
883 for (i
= 0; i
< count
; i
++)
885 struct ipcp_lattice
*lat
= ipcp_get_lattice (orig_callee_info
, i
);
886 if (ipcp_lat_is_const (lat
))
888 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
889 if (jump_func
->type
!= IPA_JF_CONST
)
897 /* Fix the callsites and the call graph after function cloning was done. */
899 ipcp_update_callgraph (void)
901 struct cgraph_node
*node
;
903 for (node
= cgraph_nodes
; node
; node
= node
->next
)
904 if (node
->analyzed
&& ipcp_node_is_clone (node
))
906 bitmap args_to_skip
= BITMAP_ALLOC (NULL
);
907 struct cgraph_node
*orig_node
= ipcp_get_orig_node (node
);
908 struct ipa_node_params
*info
= IPA_NODE_REF (orig_node
);
909 int i
, count
= ipa_get_param_count (info
);
910 struct cgraph_edge
*cs
, *next
;
912 for (i
= 0; i
< count
; i
++)
914 struct ipcp_lattice
*lat
= ipcp_get_lattice (info
, i
);
915 tree parm_tree
= ipa_get_param (info
, i
);
917 /* We can proactively remove obviously unused arguments. */
918 if (is_gimple_reg (parm_tree
)
919 && !gimple_default_def (DECL_STRUCT_FUNCTION (orig_node
->decl
),
922 bitmap_set_bit (args_to_skip
, i
);
926 if (lat
->type
== IPA_CONST_VALUE
)
927 bitmap_set_bit (args_to_skip
, i
);
929 for (cs
= node
->callers
; cs
; cs
= next
)
931 next
= cs
->next_caller
;
932 if (!ipcp_node_is_clone (cs
->caller
) && ipcp_need_redirect_p (cs
))
933 cgraph_redirect_edge_callee (cs
, orig_node
);
938 /* Update profiling info for versioned functions and the functions they were
941 ipcp_update_profiling (void)
943 struct cgraph_node
*node
, *orig_node
;
944 gcov_type scale
, scale_complement
;
945 struct cgraph_edge
*cs
;
947 for (node
= cgraph_nodes
; node
; node
= node
->next
)
949 if (ipcp_node_is_clone (node
))
951 orig_node
= ipcp_get_orig_node (node
);
952 scale
= ipcp_get_node_scale (orig_node
);
953 node
->count
= orig_node
->count
* scale
/ REG_BR_PROB_BASE
;
954 scale_complement
= REG_BR_PROB_BASE
- scale
;
956 orig_node
->count
* scale_complement
/ REG_BR_PROB_BASE
;
957 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
958 cs
->count
= cs
->count
* scale
/ REG_BR_PROB_BASE
;
959 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
960 cs
->count
= cs
->count
* scale_complement
/ REG_BR_PROB_BASE
;
965 /* If NODE was cloned, how much would program grow? */
967 ipcp_estimate_growth (struct cgraph_node
*node
)
969 struct cgraph_edge
*cs
;
970 int redirectable_node_callers
= 0;
971 int removable_args
= 0;
972 bool need_original
= !cgraph_only_called_directly_p (node
);
973 struct ipa_node_params
*info
;
977 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
978 if (cs
->caller
== node
|| !ipcp_need_redirect_p (cs
))
979 redirectable_node_callers
++;
981 need_original
= true;
983 /* If we will be able to fully replace orignal node, we never increase
988 info
= IPA_NODE_REF (node
);
989 count
= ipa_get_param_count (info
);
990 for (i
= 0; i
< count
; i
++)
992 struct ipcp_lattice
*lat
= ipcp_get_lattice (info
, i
);
993 tree parm_tree
= ipa_get_param (info
, i
);
995 /* We can proactively remove obviously unused arguments. */
996 if (is_gimple_reg (parm_tree
)
997 && !gimple_default_def (DECL_STRUCT_FUNCTION (node
->decl
),
1001 if (lat
->type
== IPA_CONST_VALUE
)
1005 /* We make just very simple estimate of savings for removal of operand from
1006 call site. Precise cost is dificult to get, as our size metric counts
1007 constants and moves as free. Generally we are looking for cases that
1008 small function is called very many times. */
1009 growth
= node
->local
.inline_summary
.self_size
1010 - removable_args
* redirectable_node_callers
;
1017 /* Estimate cost of cloning NODE. */
1019 ipcp_estimate_cloning_cost (struct cgraph_node
*node
)
1022 gcov_type count_sum
= 1;
1023 struct cgraph_edge
*e
;
1026 cost
= ipcp_estimate_growth (node
) * 1000;
1030 fprintf (dump_file
, "Versioning of %s will save code size\n",
1031 cgraph_node_name (node
));
1035 for (e
= node
->callers
; e
; e
= e
->next_caller
)
1036 if (!bitmap_bit_p (dead_nodes
, e
->caller
->uid
)
1037 && !ipcp_need_redirect_p (e
))
1039 count_sum
+= e
->count
;
1040 freq_sum
+= e
->frequency
+ 1;
1044 cost
/= count_sum
* 1000 / max_count
+ 1;
1046 cost
/= freq_sum
* 1000 / REG_BR_PROB_BASE
+ 1;
1048 fprintf (dump_file
, "Cost of versioning %s is %i, (size: %i, freq: %i)\n",
1049 cgraph_node_name (node
), cost
, node
->local
.inline_summary
.self_size
,
1054 /* Return number of live constant parameters. */
1056 ipcp_const_param_count (struct cgraph_node
*node
)
1058 int const_param
= 0;
1059 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1060 int count
= ipa_get_param_count (info
);
1063 for (i
= 0; i
< count
; i
++)
1065 struct ipcp_lattice
*lat
= ipcp_get_lattice (info
, i
);
1066 tree parm_tree
= ipa_get_param (info
, i
);
1067 if (ipcp_lat_is_insertable (lat
)
1068 /* Do not count obviously unused arguments. */
1069 && (!is_gimple_reg (parm_tree
)
1070 || gimple_default_def (DECL_STRUCT_FUNCTION (node
->decl
),
1077 /* Propagate the constant parameters found by ipcp_iterate_stage()
1078 to the function's code. */
1080 ipcp_insert_stage (void)
1082 struct cgraph_node
*node
, *node1
= NULL
;
1084 VEC (cgraph_edge_p
, heap
) * redirect_callers
;
1085 VEC (ipa_replace_map_p
,gc
)* replace_trees
;
1086 int node_callers
, count
;
1088 struct ipa_replace_map
*replace_param
;
1090 long overall_size
= 0, new_size
= 0;
1093 ipa_check_create_node_params ();
1094 ipa_check_create_edge_args ();
1096 fprintf (dump_file
, "\nIPA insert stage:\n\n");
1098 dead_nodes
= BITMAP_ALLOC (NULL
);
1100 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1103 if (node
->count
> max_count
)
1104 max_count
= node
->count
;
1105 overall_size
+= node
->local
.inline_summary
.self_size
;
1108 max_new_size
= overall_size
;
1109 if (max_new_size
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
1110 max_new_size
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
1111 max_new_size
= max_new_size
* PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH
) / 100 + 1;
1113 /* First collect all functions we proved to have constant arguments to heap. */
1114 heap
= fibheap_new ();
1115 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1117 struct ipa_node_params
*info
;
1118 /* Propagation of the constant is forbidden in certain conditions. */
1119 if (!node
->analyzed
|| !ipcp_node_modifiable_p (node
))
1121 info
= IPA_NODE_REF (node
);
1122 if (ipa_is_called_with_var_arguments (info
))
1124 if (ipcp_const_param_count (node
))
1125 node
->aux
= fibheap_insert (heap
, ipcp_estimate_cloning_cost (node
), node
);
1128 /* Now clone in priority order until code size growth limits are met or
1130 while (!fibheap_empty (heap
))
1132 struct ipa_node_params
*info
;
1134 bitmap args_to_skip
;
1135 struct cgraph_edge
*cs
;
1137 node
= (struct cgraph_node
*)fibheap_extract_min (heap
);
1140 fprintf (dump_file
, "considering function %s\n",
1141 cgraph_node_name (node
));
1143 growth
= ipcp_estimate_growth (node
);
1145 if (new_size
+ growth
> max_new_size
)
1148 && optimize_function_for_size_p (DECL_STRUCT_FUNCTION (node
->decl
)))
1151 fprintf (dump_file
, "Not versioning, cold code would grow");
1157 /* Look if original function becomes dead after clonning. */
1158 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
1159 if (cs
->caller
== node
|| ipcp_need_redirect_p (cs
))
1161 if (!cs
&& cgraph_only_called_directly_p (node
))
1162 bitmap_set_bit (dead_nodes
, node
->uid
);
1164 info
= IPA_NODE_REF (node
);
1165 count
= ipa_get_param_count (info
);
1167 replace_trees
= VEC_alloc (ipa_replace_map_p
, gc
, 1);
1168 args_to_skip
= BITMAP_GGC_ALLOC ();
1169 for (i
= 0; i
< count
; i
++)
1171 struct ipcp_lattice
*lat
= ipcp_get_lattice (info
, i
);
1172 parm_tree
= ipa_get_param (info
, i
);
1174 /* We can proactively remove obviously unused arguments. */
1175 if (is_gimple_reg (parm_tree
)
1176 && !gimple_default_def (DECL_STRUCT_FUNCTION (node
->decl
),
1179 bitmap_set_bit (args_to_skip
, i
);
1183 if (lat
->type
== IPA_CONST_VALUE
)
1186 ipcp_create_replace_map (parm_tree
, lat
);
1187 VEC_safe_push (ipa_replace_map_p
, gc
, replace_trees
, replace_param
);
1188 bitmap_set_bit (args_to_skip
, i
);
1192 /* Compute how many callers node has. */
1194 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
1196 redirect_callers
= VEC_alloc (cgraph_edge_p
, heap
, node_callers
);
1197 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
1198 VEC_quick_push (cgraph_edge_p
, redirect_callers
, cs
);
1200 /* Redirecting all the callers of the node to the
1201 new versioned node. */
1203 cgraph_create_virtual_clone (node
, redirect_callers
, replace_trees
,
1205 args_to_skip
= NULL
;
1206 VEC_free (cgraph_edge_p
, heap
, redirect_callers
);
1207 replace_trees
= NULL
;
1212 fprintf (dump_file
, "versioned function %s with growth %i, overall %i\n",
1213 cgraph_node_name (node
), (int)growth
, (int)new_size
);
1214 ipcp_init_cloned_node (node
, node1
);
1216 /* TODO: We can use indirect inlning info to produce new calls. */
1219 dump_function_to_file (node1
->decl
, dump_file
, dump_flags
);
1221 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
1222 if (cs
->callee
->aux
)
1224 fibheap_delete_node (heap
, (fibnode_t
) cs
->callee
->aux
);
1225 cs
->callee
->aux
= fibheap_insert (heap
,
1226 ipcp_estimate_cloning_cost (cs
->callee
),
1231 while (!fibheap_empty (heap
))
1234 fprintf (dump_file
, "skipping function %s\n",
1235 cgraph_node_name (node
));
1236 node
= (struct cgraph_node
*) fibheap_extract_min (heap
);
1239 fibheap_delete (heap
);
1240 BITMAP_FREE (dead_nodes
);
1241 ipcp_update_callgraph ();
1242 ipcp_update_profiling ();
1245 /* The IPCP driver. */
1249 cgraph_remove_unreachable_nodes (true,dump_file
);
1252 fprintf (dump_file
, "\nIPA structures before propagation:\n");
1253 if (dump_flags
& TDF_DETAILS
)
1254 ipa_print_all_params (dump_file
);
1255 ipa_print_all_jump_functions (dump_file
);
1257 /* 2. Do the interprocedural propagation. */
1258 ipcp_iterate_stage ();
1259 /* 3. Insert the constants found to the functions. */
1260 ipcp_insert_stage ();
1261 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1263 fprintf (dump_file
, "\nProfiling info after insert stage:\n");
1264 ipcp_print_profile_data (dump_file
);
1266 /* Free all IPCP structures. */
1267 free_all_ipa_structures_after_ipa_cp ();
1269 fprintf (dump_file
, "\nIPA constant propagation end\n");
1273 /* Note function body size. */
1275 ipcp_generate_summary (void)
1278 fprintf (dump_file
, "\nIPA constant propagation start:\n");
1279 ipa_check_create_node_params ();
1280 ipa_check_create_edge_args ();
1281 ipa_register_cgraph_hooks ();
1282 /* 1. Call the init stage to initialize
1283 the ipa_node_params and ipa_edge_args structures. */
1287 /* Write ipcp summary for nodes in SET. */
1289 ipcp_write_summary (cgraph_node_set set
)
1291 ipa_prop_write_jump_functions (set
);
1294 /* Read ipcp summary. */
1296 ipcp_read_summary (void)
1298 ipa_prop_read_jump_functions ();
1301 /* Gate for IPCP optimization. */
1303 cgraph_gate_cp (void)
1308 struct ipa_opt_pass_d pass_ipa_cp
=
1313 cgraph_gate_cp
, /* gate */
1314 ipcp_driver
, /* execute */
1317 0, /* static_pass_number */
1318 TV_IPA_CONSTANT_PROP
, /* tv_id */
1319 0, /* properties_required */
1320 0, /* properties_provided */
1321 0, /* properties_destroyed */
1322 0, /* todo_flags_start */
1323 TODO_dump_cgraph
| TODO_dump_func
|
1324 TODO_remove_functions
/* todo_flags_finish */
1326 ipcp_generate_summary
, /* generate_summary */
1327 ipcp_write_summary
, /* write_summary */
1328 ipcp_read_summary
, /* read_summary */
1329 NULL
, /* function_read_summary */
1330 NULL
, /* stmt_fixup */
1332 NULL
, /* function_transform */
1333 NULL
, /* variable_transform */