1 /* Interprocedural constant propagation
2 Copyright (C) 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
3 Contributed by Razya Ladelsky <RAZYA@il.ibm.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* Interprocedural constant propagation. The aim of interprocedural constant
22 propagation (IPCP) is to find which function's argument has the same
23 constant value in each invocation throughout the whole program. For example,
24 consider the following program:
28 printf ("value is %d",y);
48 The IPCP algorithm will find that g's formal argument y is always called
51 The algorithm used is based on "Interprocedural Constant Propagation", by
52 Challahan David, Keith D Cooper, Ken Kennedy, Linda Torczon, Comp86, pg
55 The optimization is divided into three stages:
57 First stage - intraprocedural analysis
58 =======================================
59 This phase computes jump_function and modification flags.
61 A jump function for a callsite represents the values passed as an actual
62 arguments of a given callsite. There are three types of values:
63 Pass through - the caller's formal parameter is passed as an actual argument.
64 Constant - a constant is passed as an actual argument.
65 Unknown - neither of the above.
67 The jump function info, ipa_jump_func, is stored in ipa_edge_args
68 structure (defined in ipa_prop.h and pointed to by cgraph_node->aux)
69 modified_flags are defined in ipa_node_params structure
70 (defined in ipa_prop.h and pointed to by cgraph_edge->aux).
72 -ipcp_init_stage() is the first stage driver.
74 Second stage - interprocedural analysis
75 ========================================
76 This phase does the interprocedural constant propagation.
77 It computes lattices for all formal parameters in the program
78 and their value that may be:
80 BOTTOM - non constant.
81 CONSTANT - constant value.
83 Lattice describing a formal parameter p will have a constant value if all
84 callsites invoking this function have the same constant value passed to p.
86 The lattices are stored in ipcp_lattice which is itself in ipa_node_params
87 structure (defined in ipa_prop.h and pointed to by cgraph_edge->aux).
89 -ipcp_iterate_stage() is the second stage driver.
91 Third phase - transformation of function code
92 ============================================
93 Propagates the constant-valued formals into the function.
94 For each function whose parameters are constants, we create its clone.
96 Then we process the clone in two ways:
97 1. We insert an assignment statement 'parameter = const' at the beginning
98 of the cloned function.
99 2. For read-only parameters that do not live in memory, we replace all their
100 uses with the constant.
102 We also need to modify some callsites to call the cloned functions instead
103 of the original ones. For a callsite passing an argument found to be a
104 constant by IPCP, there are two different cases to handle:
105 1. A constant is passed as an argument. In this case the callsite in the
106 should be redirected to call the cloned callee.
107 2. A parameter (of the caller) passed as an argument (pass through
108 argument). In such cases both the caller and the callee have clones and
109 only the callsite in the cloned caller is redirected to call to the
112 This update is done in two steps: First all cloned functions are created
113 during a traversal of the call graph, during which all callsites are
114 redirected to call the cloned function. Then the callsites are traversed
115 and many calls redirected back to fit the description above.
117 -ipcp_insert_stage() is the third phase driver.
123 #include "coretypes.h"
127 #include "ipa-prop.h"
128 #include "tree-flow.h"
129 #include "tree-pass.h"
132 #include "diagnostic.h"
133 #include "tree-dump.h"
134 #include "tree-inline.h"
138 /* Get the original node field of ipa_node_params associated with node NODE. */
139 static inline struct cgraph_node
*
140 ipcp_get_orig_node (struct cgraph_node
*node
)
142 return IPA_NODE_REF (node
)->ipcp_orig_node
;
145 /* Return true if NODE describes a cloned/versioned function. */
147 ipcp_node_is_clone (struct cgraph_node
*node
)
149 return (ipcp_get_orig_node (node
) != NULL
);
152 /* Create ipa_node_params and its data structures for NEW_NODE. Set ORIG_NODE
153 as the ipcp_orig_node field in ipa_node_params. */
155 ipcp_init_cloned_node (struct cgraph_node
*orig_node
,
156 struct cgraph_node
*new_node
)
158 ipa_check_create_node_params ();
159 IPA_NODE_REF (new_node
)->ipcp_orig_node
= orig_node
;
160 ipa_count_formal_params (new_node
);
161 ipa_create_param_decls_array (new_node
);
164 /* Perform intraprocedrual analysis needed for ipcp. */
166 ipcp_analyze_node (struct cgraph_node
*node
)
168 /* Unreachable nodes should have been eliminated before ipcp. */
169 gcc_assert (node
->needed
|| node
->reachable
);
171 ipa_count_formal_params (node
);
172 ipa_create_param_decls_array (node
);
173 ipa_detect_param_modifications (node
);
176 /* Recompute all local information since node might've got new
177 direct calls after clonning. */
179 ipcp_update_cloned_node (struct cgraph_node
*new_node
)
181 /* We might've introduced new direct calls. */
182 push_cfun (DECL_STRUCT_FUNCTION (new_node
->decl
));
183 current_function_decl
= new_node
->decl
;
184 rebuild_cgraph_edges ();
186 /* Indirect inlinng rely on fact that we've already analyzed
188 if (flag_indirect_inlining
)
190 struct cgraph_edge
*cs
;
192 ipcp_analyze_node (new_node
);
194 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
196 ipa_count_arguments (cs
);
197 ipa_compute_jump_functions (cs
);
201 current_function_decl
= NULL
;
204 /* Return scale for NODE. */
205 static inline gcov_type
206 ipcp_get_node_scale (struct cgraph_node
*node
)
208 return IPA_NODE_REF (node
)->count_scale
;
211 /* Set COUNT as scale for NODE. */
213 ipcp_set_node_scale (struct cgraph_node
*node
, gcov_type count
)
215 IPA_NODE_REF (node
)->count_scale
= count
;
218 /* Return whether LAT is a constant lattice. */
220 ipcp_lat_is_const (struct ipcp_lattice
*lat
)
222 if (lat
->type
== IPA_CONST_VALUE
)
228 /* Return whether LAT is a constant lattice that ipa-cp can actually insert
229 into the code (i.e. constants excluding member pointers and pointers). */
231 ipcp_lat_is_insertable (struct ipcp_lattice
*lat
)
233 return lat
->type
== IPA_CONST_VALUE
;
236 /* Return true if LAT1 and LAT2 are equal. */
238 ipcp_lats_are_equal (struct ipcp_lattice
*lat1
, struct ipcp_lattice
*lat2
)
240 gcc_assert (ipcp_lat_is_const (lat1
) && ipcp_lat_is_const (lat2
));
241 if (lat1
->type
!= lat2
->type
)
244 if (operand_equal_p (lat1
->constant
, lat2
->constant
, 0))
250 /* Compute Meet arithmetics:
251 Meet (IPA_BOTTOM, x) = IPA_BOTTOM
253 Meet (const_a,const_b) = IPA_BOTTOM, if const_a != const_b.
254 MEET (const_a,const_b) = const_a, if const_a == const_b.*/
256 ipa_lattice_meet (struct ipcp_lattice
*res
, struct ipcp_lattice
*lat1
,
257 struct ipcp_lattice
*lat2
)
259 if (lat1
->type
== IPA_BOTTOM
|| lat2
->type
== IPA_BOTTOM
)
261 res
->type
= IPA_BOTTOM
;
264 if (lat1
->type
== IPA_TOP
)
266 res
->type
= lat2
->type
;
267 res
->constant
= lat2
->constant
;
270 if (lat2
->type
== IPA_TOP
)
272 res
->type
= lat1
->type
;
273 res
->constant
= lat1
->constant
;
276 if (!ipcp_lats_are_equal (lat1
, lat2
))
278 res
->type
= IPA_BOTTOM
;
281 res
->type
= lat1
->type
;
282 res
->constant
= lat1
->constant
;
285 /* Return the lattice corresponding to the Ith formal parameter of the function
286 described by INFO. */
287 static inline struct ipcp_lattice
*
288 ipcp_get_ith_lattice (struct ipa_node_params
*info
, int i
)
290 return &(info
->ipcp_lattices
[i
]);
293 /* Given the jump function JFUNC, compute the lattice LAT that describes the
294 value coming down the callsite. INFO describes the caller node so that
295 pass-through jump functions can be evaluated. */
297 ipcp_lattice_from_jfunc (struct ipa_node_params
*info
, struct ipcp_lattice
*lat
,
298 struct ipa_jump_func
*jfunc
)
300 if (jfunc
->type
== IPA_CONST
)
302 lat
->type
= IPA_CONST_VALUE
;
303 lat
->constant
= jfunc
->value
.constant
;
305 else if (jfunc
->type
== IPA_PASS_THROUGH
)
307 struct ipcp_lattice
*caller_lat
;
309 caller_lat
= ipcp_get_ith_lattice (info
, jfunc
->value
.formal_id
);
310 lat
->type
= caller_lat
->type
;
311 lat
->constant
= caller_lat
->constant
;
314 lat
->type
= IPA_BOTTOM
;
317 /* True when OLD_LAT and NEW_LAT values are not the same. */
320 ipcp_lattice_changed (struct ipcp_lattice
*old_lat
,
321 struct ipcp_lattice
*new_lat
)
323 if (old_lat
->type
== new_lat
->type
)
325 if (!ipcp_lat_is_const (old_lat
))
327 if (ipcp_lats_are_equal (old_lat
, new_lat
))
333 /* Print all ipcp_lattices of all functions to F. */
335 ipcp_print_all_lattices (FILE * f
)
337 struct cgraph_node
*node
;
340 fprintf (f
, "\nLATTICE PRINT\n");
341 for (node
= cgraph_nodes
; node
; node
= node
->next
)
343 struct ipa_node_params
*info
;
347 info
= IPA_NODE_REF (node
);
348 fprintf (f
, "Printing lattices %s:\n", cgraph_node_name (node
));
349 count
= ipa_get_param_count (info
);
350 for (i
= 0; i
< count
; i
++)
352 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
354 fprintf (f
, " param [%d]: ", i
);
355 if (lat
->type
== IPA_CONST_VALUE
)
357 fprintf (f
, "type is CONST ");
358 print_generic_expr (f
, lat
->constant
, 0);
361 else if (lat
->type
== IPA_TOP
)
362 fprintf (f
, "type is TOP\n");
364 fprintf (f
, "type is BOTTOM\n");
369 /* Initialize ipcp_lattices array. The lattices corresponding to supported
370 types (integers, real types and Fortran constants defined as const_decls)
371 are initialized to IPA_TOP, the rest of them to IPA_BOTTOM. */
373 ipcp_initialize_node_lattices (struct cgraph_node
*node
)
376 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
378 info
->ipcp_lattices
= XCNEWVEC (struct ipcp_lattice
,
379 ipa_get_param_count (info
));
381 /* When cloning is allowed, we can assume that externally visible functions
382 are not called. We will compensate this by cloning later. */
383 if (flag_ipa_cp_clone
|| !node
->needed
)
384 for (i
= 0; i
< ipa_get_param_count (info
) ; i
++)
385 ipcp_get_ith_lattice (info
, i
)->type
= IPA_TOP
;
387 for (i
= 0; i
< ipa_get_param_count (info
) ; i
++)
388 ipcp_get_ith_lattice (info
, i
)->type
= IPA_BOTTOM
;
391 /* build INTEGER_CST tree with type TREE_TYPE and value according to LAT.
394 build_const_val (struct ipcp_lattice
*lat
, tree tree_type
)
398 gcc_assert (ipcp_lat_is_const (lat
));
401 if (!useless_type_conversion_p (tree_type
, TREE_TYPE (val
)))
403 if (fold_convertible_p (tree_type
, val
))
404 return fold_build1 (NOP_EXPR
, tree_type
, val
);
406 return fold_build1 (VIEW_CONVERT_EXPR
, tree_type
, val
);
411 /* Compute the proper scale for NODE. It is the ratio between the number of
412 direct calls (represented on the incoming cgraph_edges) and sum of all
413 invocations of NODE (represented as count in cgraph_node). */
415 ipcp_compute_node_scale (struct cgraph_node
*node
)
418 struct cgraph_edge
*cs
;
421 /* Compute sum of all counts of callers. */
422 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
424 if (node
->count
== 0)
425 ipcp_set_node_scale (node
, 0);
427 ipcp_set_node_scale (node
, sum
* REG_BR_PROB_BASE
/ node
->count
);
430 /* Initialization and computation of IPCP data structures. This is the initial
431 intraprocedural analysis of functions, which gathers information to be
432 propagated later on. */
434 ipcp_init_stage (void)
436 struct cgraph_node
*node
;
437 struct cgraph_edge
*cs
;
439 for (node
= cgraph_nodes
; node
; node
= node
->next
)
442 ipcp_analyze_node (node
);
443 ipcp_initialize_node_lattices (node
);
444 ipcp_compute_node_scale (node
);
446 for (node
= cgraph_nodes
; node
; node
= node
->next
)
450 /* building jump functions */
451 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
453 if (!cs
->callee
->analyzed
)
455 ipa_count_arguments (cs
);
456 if (ipa_get_cs_argument_count (IPA_EDGE_REF (cs
))
457 != ipa_get_param_count (IPA_NODE_REF (cs
->callee
)))
459 /* Handle cases of functions with
460 a variable number of parameters. */
461 ipa_set_called_with_variable_arg (IPA_NODE_REF (cs
->callee
));
462 if (flag_indirect_inlining
)
463 ipa_compute_jump_functions (cs
);
466 ipa_compute_jump_functions (cs
);
471 /* Return true if there are some formal parameters whose value is IPA_TOP (in
472 the whole compilation unit). Change their values to IPA_BOTTOM, since they
473 most probably get their values from outside of this compilation unit. */
475 ipcp_change_tops_to_bottom (void)
478 struct cgraph_node
*node
;
482 for (node
= cgraph_nodes
; node
; node
= node
->next
)
484 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
485 count
= ipa_get_param_count (info
);
486 for (i
= 0; i
< count
; i
++)
488 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
489 if (lat
->type
== IPA_TOP
)
492 lat
->type
= IPA_BOTTOM
;
499 /* Interprocedural analysis. The algorithm propagates constants from the
500 caller's parameters to the callee's arguments. */
502 ipcp_propagate_stage (void)
505 struct ipcp_lattice inc_lat
= { IPA_BOTTOM
, NULL
};
506 struct ipcp_lattice new_lat
= { IPA_BOTTOM
, NULL
};
507 struct ipcp_lattice
*dest_lat
;
508 struct cgraph_edge
*cs
;
509 struct ipa_jump_func
*jump_func
;
510 struct ipa_func_list
*wl
;
513 ipa_check_create_node_params ();
514 ipa_check_create_edge_args ();
515 /* Initialize worklist to contain all functions. */
516 wl
= ipa_init_func_list ();
519 struct cgraph_node
*node
= ipa_pop_func_from_list (&wl
);
520 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
522 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
524 struct ipa_node_params
*callee_info
= IPA_NODE_REF (cs
->callee
);
525 struct ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
527 if (ipa_is_called_with_var_arguments (callee_info
))
530 count
= ipa_get_cs_argument_count (args
);
531 for (i
= 0; i
< count
; i
++)
533 jump_func
= ipa_get_ith_jump_func (args
, i
);
534 ipcp_lattice_from_jfunc (info
, &inc_lat
, jump_func
);
535 dest_lat
= ipcp_get_ith_lattice (callee_info
, i
);
536 ipa_lattice_meet (&new_lat
, &inc_lat
, dest_lat
);
537 if (ipcp_lattice_changed (&new_lat
, dest_lat
))
539 dest_lat
->type
= new_lat
.type
;
540 dest_lat
->constant
= new_lat
.constant
;
541 ipa_push_func_to_list (&wl
, cs
->callee
);
548 /* Call the constant propagation algorithm and re-call it if necessary
549 (if there are undetermined values left). */
551 ipcp_iterate_stage (void)
553 ipcp_propagate_stage ();
554 if (ipcp_change_tops_to_bottom ())
555 /* Some lattices have changed from IPA_TOP to IPA_BOTTOM.
556 This change should be propagated. */
557 ipcp_propagate_stage ();
560 /* Check conditions to forbid constant insertion to function described by
563 ipcp_node_modifiable_p (struct cgraph_node
*node
)
565 /* Once we will be able to do in-place replacement, we can be more
567 return tree_versionable_function_p (node
->decl
);
570 /* Print count scale data structures. */
572 ipcp_function_scale_print (FILE * f
)
574 struct cgraph_node
*node
;
576 for (node
= cgraph_nodes
; node
; node
= node
->next
)
580 fprintf (f
, "printing scale for %s: ", cgraph_node_name (node
));
581 fprintf (f
, "value is " HOST_WIDE_INT_PRINT_DEC
582 " \n", (HOST_WIDE_INT
) ipcp_get_node_scale (node
));
586 /* Print counts of all cgraph nodes. */
588 ipcp_print_func_profile_counts (FILE * f
)
590 struct cgraph_node
*node
;
592 for (node
= cgraph_nodes
; node
; node
= node
->next
)
594 fprintf (f
, "function %s: ", cgraph_node_name (node
));
595 fprintf (f
, "count is " HOST_WIDE_INT_PRINT_DEC
596 " \n", (HOST_WIDE_INT
) node
->count
);
600 /* Print counts of all cgraph edges. */
602 ipcp_print_call_profile_counts (FILE * f
)
604 struct cgraph_node
*node
;
605 struct cgraph_edge
*cs
;
607 for (node
= cgraph_nodes
; node
; node
= node
->next
)
609 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
611 fprintf (f
, "%s -> %s ", cgraph_node_name (cs
->caller
),
612 cgraph_node_name (cs
->callee
));
613 fprintf (f
, "count is " HOST_WIDE_INT_PRINT_DEC
" \n",
614 (HOST_WIDE_INT
) cs
->count
);
619 /* Print all counts and probabilities of cfg edges of all functions. */
621 ipcp_print_edge_profiles (FILE * f
)
623 struct cgraph_node
*node
;
628 for (node
= cgraph_nodes
; node
; node
= node
->next
)
630 fprintf (f
, "function %s: \n", cgraph_node_name (node
));
634 ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node
->decl
));
635 fprintf (f
, "ENTRY: ");
636 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
637 " %d\n", (HOST_WIDE_INT
) bb
->count
, bb
->frequency
);
640 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
643 EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
645 fprintf (f
, "edge ENTRY -> EXIT, Count");
647 fprintf (f
, "edge ENTRY -> %d, Count", e
->dest
->index
);
648 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
649 " Prob %d\n", (HOST_WIDE_INT
) e
->count
,
652 FOR_EACH_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
654 fprintf (f
, "bb[%d]: ", bb
->index
);
655 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
656 " %d\n", (HOST_WIDE_INT
) bb
->count
, bb
->frequency
);
657 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
660 EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
662 fprintf (f
, "edge %d -> EXIT, Count", e
->src
->index
);
664 fprintf (f
, "edge %d -> %d, Count", e
->src
->index
,
666 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
" Prob %d\n",
667 (HOST_WIDE_INT
) e
->count
, e
->probability
);
674 /* Print counts and frequencies for all basic blocks of all functions. */
676 ipcp_print_bb_profiles (FILE * f
)
679 struct cgraph_node
*node
;
681 for (node
= cgraph_nodes
; node
; node
= node
->next
)
683 fprintf (f
, "function %s: \n", cgraph_node_name (node
));
687 ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node
->decl
));
688 fprintf (f
, "ENTRY: Count");
689 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
690 " Frequency %d\n", (HOST_WIDE_INT
) bb
->count
,
693 FOR_EACH_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
695 fprintf (f
, "bb[%d]: Count", bb
->index
);
696 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
697 " Frequency %d\n", (HOST_WIDE_INT
) bb
->count
,
701 EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node
->decl
));
702 fprintf (f
, "EXIT: Count");
703 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
704 " Frequency %d\n", (HOST_WIDE_INT
) bb
->count
,
711 /* Print all IPCP data structures to F. */
713 ipcp_print_all_structures (FILE * f
)
715 ipcp_print_all_lattices (f
);
716 ipcp_function_scale_print (f
);
717 ipa_print_all_tree_maps (f
);
718 ipa_print_all_param_flags (f
);
719 ipa_print_all_jump_functions (f
);
722 /* Print profile info for all functions. */
724 ipcp_print_profile_data (FILE * f
)
726 fprintf (f
, "\nNODE COUNTS :\n");
727 ipcp_print_func_profile_counts (f
);
728 fprintf (f
, "\nCS COUNTS stage:\n");
729 ipcp_print_call_profile_counts (f
);
730 fprintf (f
, "\nBB COUNTS and FREQUENCIES :\n");
731 ipcp_print_bb_profiles (f
);
732 fprintf (f
, "\nCFG EDGES COUNTS and PROBABILITIES :\n");
733 ipcp_print_edge_profiles (f
);
736 /* Build and initialize ipa_replace_map struct according to LAT. This struct is
737 processed by versioning, which operates according to the flags set.
738 PARM_TREE is the formal parameter found to be constant. LAT represents the
740 static struct ipa_replace_map
*
741 ipcp_create_replace_map (tree parm_tree
, struct ipcp_lattice
*lat
)
743 struct ipa_replace_map
*replace_map
;
746 replace_map
= XCNEW (struct ipa_replace_map
);
747 const_val
= build_const_val (lat
, TREE_TYPE (parm_tree
));
750 fprintf (dump_file
, " replacing param ");
751 print_generic_expr (dump_file
, parm_tree
, 0);
752 fprintf (dump_file
, " with const ");
753 print_generic_expr (dump_file
, const_val
, 0);
754 fprintf (dump_file
, "\n");
756 replace_map
->old_tree
= parm_tree
;
757 replace_map
->new_tree
= const_val
;
758 replace_map
->replace_p
= true;
759 replace_map
->ref_p
= false;
764 /* Return true if this callsite should be redirected to the original callee
765 (instead of the cloned one). */
767 ipcp_need_redirect_p (struct cgraph_edge
*cs
)
769 struct ipa_node_params
*orig_callee_info
;
771 struct ipa_jump_func
*jump_func
;
772 struct cgraph_node
*node
= cs
->callee
, *orig
;
774 if (!flag_ipa_cp_clone
)
777 if ((orig
= ipcp_get_orig_node (node
)) != NULL
)
779 if (ipcp_get_orig_node (cs
->caller
))
782 orig_callee_info
= IPA_NODE_REF (node
);
783 count
= ipa_get_param_count (orig_callee_info
);
784 for (i
= 0; i
< count
; i
++)
786 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (orig_callee_info
, i
);
787 if (ipcp_lat_is_const (lat
))
789 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
790 if (jump_func
->type
!= IPA_CONST
)
798 /* Fix the callsites and the call graph after function cloning was done. */
800 ipcp_update_callgraph (void)
802 struct cgraph_node
*node
;
804 for (node
= cgraph_nodes
; node
; node
= node
->next
)
805 if (node
->analyzed
&& ipcp_node_is_clone (node
))
807 bitmap args_to_skip
= BITMAP_ALLOC (NULL
);
808 struct cgraph_node
*orig_node
= ipcp_get_orig_node (node
);
809 struct ipa_node_params
*info
= IPA_NODE_REF (orig_node
);
810 int i
, count
= ipa_get_param_count (info
);
811 struct cgraph_edge
*cs
, *next
;
813 for (i
= 0; i
< count
; i
++)
815 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
816 tree parm_tree
= ipa_get_ith_param (info
, i
);
818 /* We can proactively remove obviously unused arguments. */
819 if (is_gimple_reg (parm_tree
)
820 && !gimple_default_def (DECL_STRUCT_FUNCTION (orig_node
->decl
),
823 bitmap_set_bit (args_to_skip
, i
);
827 if (lat
->type
== IPA_CONST_VALUE
)
828 bitmap_set_bit (args_to_skip
, i
);
830 for (cs
= node
->callers
; cs
; cs
= next
)
832 next
= cs
->next_caller
;
833 if (ipcp_node_is_clone (cs
->caller
) || !ipcp_need_redirect_p (cs
))
836 gimple_stmt_iterator gsi
;
838 current_function_decl
= cs
->caller
->decl
;
839 push_cfun (DECL_STRUCT_FUNCTION (cs
->caller
->decl
));
841 new_stmt
= giple_copy_call_skip_args (cs
->call_stmt
, args_to_skip
);
842 gsi
= gsi_for_stmt (cs
->call_stmt
);
843 gsi_replace (&gsi
, new_stmt
, true);
844 cgraph_set_call_stmt (cs
, new_stmt
);
846 current_function_decl
= NULL
;
850 cgraph_redirect_edge_callee (cs
, orig_node
);
851 gimple_call_set_fndecl (cs
->call_stmt
, orig_node
->decl
);
857 /* Update all cfg basic blocks in NODE according to SCALE. */
859 ipcp_update_bb_counts (struct cgraph_node
*node
, gcov_type scale
)
863 FOR_ALL_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
864 bb
->count
= bb
->count
* scale
/ REG_BR_PROB_BASE
;
867 /* Update all cfg edges in NODE according to SCALE. */
869 ipcp_update_edges_counts (struct cgraph_node
*node
, gcov_type scale
)
875 FOR_ALL_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
876 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
877 e
->count
= e
->count
* scale
/ REG_BR_PROB_BASE
;
880 /* Update profiling info for versioned functions and the functions they were
883 ipcp_update_profiling (void)
885 struct cgraph_node
*node
, *orig_node
;
886 gcov_type scale
, scale_complement
;
887 struct cgraph_edge
*cs
;
889 for (node
= cgraph_nodes
; node
; node
= node
->next
)
891 if (ipcp_node_is_clone (node
))
893 orig_node
= ipcp_get_orig_node (node
);
894 scale
= ipcp_get_node_scale (orig_node
);
895 node
->count
= orig_node
->count
* scale
/ REG_BR_PROB_BASE
;
896 scale_complement
= REG_BR_PROB_BASE
- scale
;
898 orig_node
->count
* scale_complement
/ REG_BR_PROB_BASE
;
899 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
900 cs
->count
= cs
->count
* scale
/ REG_BR_PROB_BASE
;
901 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
902 cs
->count
= cs
->count
* scale_complement
/ REG_BR_PROB_BASE
;
903 ipcp_update_bb_counts (node
, scale
);
904 ipcp_update_bb_counts (orig_node
, scale_complement
);
905 ipcp_update_edges_counts (node
, scale
);
906 ipcp_update_edges_counts (orig_node
, scale_complement
);
911 /* Maximal count found in program. */
912 static gcov_type max_count
;
915 /* Return true if original clone needs to be preserved. */
917 ipcp_need_original_clone_p (struct cgraph_node
*node
)
919 struct cgraph_edge
*e
;
923 for (e
= node
->callers
; e
; e
= e
->next_caller
)
924 if (!bitmap_bit_p (dead_nodes
, e
->caller
->uid
)
925 && ipcp_need_redirect_p (e
))
931 /* Estimate cost of cloning NODE. */
933 ipcp_estimate_cloning_cost (struct cgraph_node
*node
)
936 gcov_type count_sum
= 1;
937 struct cgraph_edge
*e
;
940 /* When we don't need original clone; we should always propagate. */
941 if (!ipcp_need_original_clone_p (node
))
944 fprintf (dump_file
, "Function %s can be fully propagated\n",
945 cgraph_node_name (node
));
949 for (e
= node
->callers
; e
; e
= e
->next_caller
)
950 if (!bitmap_bit_p (dead_nodes
, e
->caller
->uid
)
951 && !ipcp_need_redirect_p (e
))
953 count_sum
+= e
->count
;
954 freq_sum
+= e
->frequency
+ 1;
957 cost
= node
->local
.inline_summary
.self_insns
* 1000;
959 cost
/= count_sum
* 1000 / max_count
+ 1;
961 cost
/= freq_sum
* 1000 / REG_BR_PROB_BASE
+ 1;
963 fprintf (dump_file
, "Cost of versioning %s is %i, (size: %i, freq: %i)\n",
964 cgraph_node_name (node
), cost
, node
->local
.inline_summary
.self_insns
,
969 /* Return number of live constant parameters. */
971 ipcp_const_param_count (struct cgraph_node
*node
)
974 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
975 int count
= ipa_get_param_count (info
);
978 for (i
= 0; i
< count
; i
++)
980 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
981 tree parm_tree
= ipa_get_ith_param (info
, i
);
982 if (ipcp_lat_is_insertable (lat
)
983 /* Do not count obviously unused arguments. */
984 && (!is_gimple_reg (parm_tree
)
985 || gimple_default_def (DECL_STRUCT_FUNCTION (node
->decl
),
992 /* Propagate the constant parameters found by ipcp_iterate_stage()
993 to the function's code. */
995 ipcp_insert_stage (void)
997 struct cgraph_node
*node
, *node1
= NULL
;
999 VEC (cgraph_edge_p
, heap
) * redirect_callers
;
1000 varray_type replace_trees
;
1001 struct cgraph_edge
*cs
;
1002 int node_callers
, count
;
1004 struct ipa_replace_map
*replace_param
;
1006 long overall_insns
= 0, new_insns
= 0;
1009 ipa_check_create_node_params ();
1010 ipa_check_create_edge_args ();
1012 dead_nodes
= BITMAP_ALLOC (NULL
);
1014 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1017 if (node
->count
> max_count
)
1018 max_count
= node
->count
;
1019 overall_insns
+= node
->local
.inline_summary
.self_insns
;
1022 max_new_insns
= overall_insns
;
1023 if (max_new_insns
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
1024 max_new_insns
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
1025 max_new_insns
= max_new_insns
* PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH
) / 100 + 1;
1027 /* First collect all functions we proved to have constant arguments to heap. */
1028 heap
= fibheap_new ();
1029 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1031 struct ipa_node_params
*info
;
1032 /* Propagation of the constant is forbidden in certain conditions. */
1033 if (!node
->analyzed
|| !ipcp_node_modifiable_p (node
))
1035 info
= IPA_NODE_REF (node
);
1036 if (ipa_is_called_with_var_arguments (info
))
1038 if (ipcp_const_param_count (node
))
1039 node
->aux
= fibheap_insert (heap
, ipcp_estimate_cloning_cost (node
), node
);
1042 /* Now clone in priority order until code size growth limits are met or
1044 while (!fibheap_empty (heap
))
1046 struct ipa_node_params
*info
;
1048 bitmap args_to_skip
;
1050 node
= (struct cgraph_node
*)fibheap_extract_min (heap
);
1053 fprintf (dump_file
, "considering function %s\n",
1054 cgraph_node_name (node
));
1056 if (ipcp_need_original_clone_p (node
))
1057 growth
= node
->local
.inline_summary
.self_insns
;
1059 bitmap_set_bit (dead_nodes
, node
->uid
);
1061 if (new_insns
+ growth
> max_new_insns
)
1064 && optimize_function_for_size_p (DECL_STRUCT_FUNCTION (node
->decl
)))
1067 fprintf (dump_file
, "Not versioning, cold code would grow");
1071 new_insns
+= growth
;
1073 info
= IPA_NODE_REF (node
);
1074 count
= ipa_get_param_count (info
);
1076 VARRAY_GENERIC_PTR_INIT (replace_trees
, ipcp_const_param_count (node
),
1078 args_to_skip
= BITMAP_ALLOC (NULL
);
1079 for (i
= 0; i
< count
; i
++)
1081 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
1082 parm_tree
= ipa_get_ith_param (info
, i
);
1084 /* We can proactively remove obviously unused arguments. */
1085 if (is_gimple_reg (parm_tree
)
1086 && !gimple_default_def (DECL_STRUCT_FUNCTION (node
->decl
),
1089 bitmap_set_bit (args_to_skip
, i
);
1093 if (lat
->type
== IPA_CONST_VALUE
)
1096 ipcp_create_replace_map (parm_tree
, lat
);
1097 VARRAY_PUSH_GENERIC_PTR (replace_trees
, replace_param
);
1098 bitmap_set_bit (args_to_skip
, i
);
1102 /* Compute how many callers node has. */
1104 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
1106 redirect_callers
= VEC_alloc (cgraph_edge_p
, heap
, node_callers
);
1107 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
1108 VEC_quick_push (cgraph_edge_p
, redirect_callers
, cs
);
1110 /* Redirecting all the callers of the node to the
1111 new versioned node. */
1113 cgraph_function_versioning (node
, redirect_callers
, replace_trees
,
1115 BITMAP_FREE (args_to_skip
);
1116 VEC_free (cgraph_edge_p
, heap
, redirect_callers
);
1117 VARRAY_CLEAR (replace_trees
);
1121 fprintf (dump_file
, "versioned function %s with growth %i, overall %i\n",
1122 cgraph_node_name (node
), (int)growth
, (int)new_insns
);
1123 ipcp_init_cloned_node (node
, node1
);
1125 /* We've possibly introduced direct calls. */
1126 ipcp_update_cloned_node (node1
);
1129 dump_function_to_file (node1
->decl
, dump_file
, dump_flags
);
1131 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
1132 if (cs
->callee
->aux
)
1134 fibheap_delete_node (heap
, (fibnode_t
) cs
->callee
->aux
);
1135 cs
->callee
->aux
= fibheap_insert (heap
,
1136 ipcp_estimate_cloning_cost (cs
->callee
),
1141 while (!fibheap_empty (heap
))
1144 fprintf (dump_file
, "skipping function %s\n",
1145 cgraph_node_name (node
));
1146 node
= (struct cgraph_node
*) fibheap_extract_min (heap
);
1149 fibheap_delete (heap
);
1150 BITMAP_FREE (dead_nodes
);
1151 ipcp_update_callgraph ();
1152 ipcp_update_profiling ();
1155 /* The IPCP driver. */
1159 /* 2. Do the interprocedural propagation. */
1160 ipcp_iterate_stage ();
1163 fprintf (dump_file
, "\nIPA structures after propagation:\n");
1164 ipcp_print_all_structures (dump_file
);
1165 fprintf (dump_file
, "\nProfiling info before insert stage:\n");
1166 ipcp_print_profile_data (dump_file
);
1168 /* 3. Insert the constants found to the functions. */
1169 ipcp_insert_stage ();
1172 fprintf (dump_file
, "\nProfiling info after insert stage:\n");
1173 ipcp_print_profile_data (dump_file
);
1175 /* Free all IPCP structures. */
1176 free_all_ipa_structures_after_ipa_cp ();
1178 fprintf (dump_file
, "\nIPA constant propagation end\n");
1179 cgraph_remove_unreachable_nodes (true, NULL
);
1183 /* Note function body size. */
1185 ipcp_generate_summary (void)
1188 fprintf (dump_file
, "\nIPA constant propagation start:\n");
1189 ipa_check_create_node_params ();
1190 ipa_check_create_edge_args ();
1191 ipa_register_cgraph_hooks ();
1192 /* 1. Call the init stage to initialize
1193 the ipa_node_params and ipa_edge_args structures. */
1197 fprintf (dump_file
, "\nIPA structures before propagation:\n");
1198 ipcp_print_all_structures (dump_file
);
1202 /* Gate for IPCP optimization. */
1204 cgraph_gate_cp (void)
1209 struct ipa_opt_pass pass_ipa_cp
=
1214 cgraph_gate_cp
, /* gate */
1215 ipcp_driver
, /* execute */
1218 0, /* static_pass_number */
1219 TV_IPA_CONSTANT_PROP
, /* tv_id */
1220 0, /* properties_required */
1221 PROP_trees
, /* properties_provided */
1222 0, /* properties_destroyed */
1223 0, /* todo_flags_start */
1224 TODO_dump_cgraph
| TODO_dump_func
/* todo_flags_finish */
1226 ipcp_generate_summary
, /* generate_summary */
1227 NULL
, /* write_summary */
1228 NULL
, /* read_summary */
1229 NULL
, /* function_read_summary */
1231 NULL
, /* function_transform */
1232 NULL
, /* variable_transform */