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 /* 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_NODE_REF (new_node
)->ipcp_orig_node
= orig_node
;
175 ipa_count_formal_params (new_node
);
176 ipa_create_param_decls_array (new_node
);
179 /* Perform intraprocedrual analysis needed for ipcp. */
181 ipcp_analyze_node (struct cgraph_node
*node
)
183 /* Unreachable nodes should have been eliminated before ipcp. */
184 gcc_assert (node
->needed
|| node
->reachable
);
186 ipa_count_formal_params (node
);
187 ipa_create_param_decls_array (node
);
188 ipa_detect_param_modifications (node
);
191 /* Recompute all local information since node might've got new
192 direct calls after cloning. */
194 ipcp_update_cloned_node (struct cgraph_node
*new_node
)
196 /* We might've introduced new direct calls. */
197 push_cfun (DECL_STRUCT_FUNCTION (new_node
->decl
));
198 current_function_decl
= new_node
->decl
;
199 rebuild_cgraph_edges ();
201 /* Indirect inlinng rely on fact that we've already analyzed
203 if (flag_indirect_inlining
)
205 struct cgraph_edge
*cs
;
207 ipcp_analyze_node (new_node
);
209 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
211 ipa_count_arguments (cs
);
212 ipa_compute_jump_functions (cs
);
216 current_function_decl
= NULL
;
219 /* Return scale for NODE. */
220 static inline gcov_type
221 ipcp_get_node_scale (struct cgraph_node
*node
)
223 return IPA_NODE_REF (node
)->count_scale
;
226 /* Set COUNT as scale for NODE. */
228 ipcp_set_node_scale (struct cgraph_node
*node
, gcov_type count
)
230 IPA_NODE_REF (node
)->count_scale
= count
;
233 /* Return whether LAT is a constant lattice. */
235 ipcp_lat_is_const (struct ipcp_lattice
*lat
)
237 if (lat
->type
== IPA_CONST_VALUE
)
243 /* Return whether LAT is a constant lattice that ipa-cp can actually insert
244 into the code (i.e. constants excluding member pointers and pointers). */
246 ipcp_lat_is_insertable (struct ipcp_lattice
*lat
)
248 return lat
->type
== IPA_CONST_VALUE
;
251 /* Return true if LAT1 and LAT2 are equal. */
253 ipcp_lats_are_equal (struct ipcp_lattice
*lat1
, struct ipcp_lattice
*lat2
)
255 gcc_assert (ipcp_lat_is_const (lat1
) && ipcp_lat_is_const (lat2
));
256 if (lat1
->type
!= lat2
->type
)
259 if (operand_equal_p (lat1
->constant
, lat2
->constant
, 0))
265 /* Compute Meet arithmetics:
266 Meet (IPA_BOTTOM, x) = IPA_BOTTOM
268 Meet (const_a,const_b) = IPA_BOTTOM, if const_a != const_b.
269 MEET (const_a,const_b) = const_a, if const_a == const_b.*/
271 ipa_lattice_meet (struct ipcp_lattice
*res
, struct ipcp_lattice
*lat1
,
272 struct ipcp_lattice
*lat2
)
274 if (lat1
->type
== IPA_BOTTOM
|| lat2
->type
== IPA_BOTTOM
)
276 res
->type
= IPA_BOTTOM
;
279 if (lat1
->type
== IPA_TOP
)
281 res
->type
= lat2
->type
;
282 res
->constant
= lat2
->constant
;
285 if (lat2
->type
== IPA_TOP
)
287 res
->type
= lat1
->type
;
288 res
->constant
= lat1
->constant
;
291 if (!ipcp_lats_are_equal (lat1
, lat2
))
293 res
->type
= IPA_BOTTOM
;
296 res
->type
= lat1
->type
;
297 res
->constant
= lat1
->constant
;
300 /* Return the lattice corresponding to the Ith formal parameter of the function
301 described by INFO. */
302 static inline struct ipcp_lattice
*
303 ipcp_get_ith_lattice (struct ipa_node_params
*info
, int i
)
305 return &(info
->ipcp_lattices
[i
]);
308 /* Given the jump function JFUNC, compute the lattice LAT that describes the
309 value coming down the callsite. INFO describes the caller node so that
310 pass-through jump functions can be evaluated. */
312 ipcp_lattice_from_jfunc (struct ipa_node_params
*info
, struct ipcp_lattice
*lat
,
313 struct ipa_jump_func
*jfunc
)
315 if (jfunc
->type
== IPA_CONST
)
317 lat
->type
= IPA_CONST_VALUE
;
318 lat
->constant
= jfunc
->value
.constant
;
320 else if (jfunc
->type
== IPA_PASS_THROUGH
)
322 struct ipcp_lattice
*caller_lat
;
324 caller_lat
= ipcp_get_ith_lattice (info
, jfunc
->value
.formal_id
);
325 lat
->type
= caller_lat
->type
;
326 lat
->constant
= caller_lat
->constant
;
329 lat
->type
= IPA_BOTTOM
;
332 /* True when OLD_LAT and NEW_LAT values are not the same. */
335 ipcp_lattice_changed (struct ipcp_lattice
*old_lat
,
336 struct ipcp_lattice
*new_lat
)
338 if (old_lat
->type
== new_lat
->type
)
340 if (!ipcp_lat_is_const (old_lat
))
342 if (ipcp_lats_are_equal (old_lat
, new_lat
))
348 /* Print all ipcp_lattices of all functions to F. */
350 ipcp_print_all_lattices (FILE * f
)
352 struct cgraph_node
*node
;
355 fprintf (f
, "\nLattice:\n");
356 for (node
= cgraph_nodes
; node
; node
= node
->next
)
358 struct ipa_node_params
*info
;
362 info
= IPA_NODE_REF (node
);
363 fprintf (f
, " Node: %s:\n", cgraph_node_name (node
));
364 count
= ipa_get_param_count (info
);
365 for (i
= 0; i
< count
; i
++)
367 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
369 fprintf (f
, " param [%d]: ", i
);
370 if (lat
->type
== IPA_CONST_VALUE
)
372 fprintf (f
, "type is CONST ");
373 print_generic_expr (f
, lat
->constant
, 0);
376 else if (lat
->type
== IPA_TOP
)
377 fprintf (f
, "type is TOP\n");
379 fprintf (f
, "type is BOTTOM\n");
384 /* Return true if this NODE is viable candidate for cloning. */
386 ipcp_cloning_candidate_p (struct cgraph_node
*node
)
390 gcov_type direct_call_sum
= 0;
391 struct cgraph_edge
*e
;
393 /* We never clone functions that are not visible from outside.
394 FIXME: in future we should clone such functions when they are called with
395 different constants, but current ipcp implementation is not good on this.
397 if (!node
->needed
|| !node
->analyzed
)
400 if (cgraph_function_body_availability (node
) <= AVAIL_OVERWRITABLE
)
403 fprintf (dump_file
, "Not considering %s for cloning; body is overwrittable.\n",
404 cgraph_node_name (node
));
407 if (!tree_versionable_function_p (node
->decl
))
410 fprintf (dump_file
, "Not considering %s for cloning; body is not versionable.\n",
411 cgraph_node_name (node
));
414 for (e
= node
->callers
; e
; e
= e
->next_caller
)
416 direct_call_sum
+= e
->count
;
418 if (cgraph_maybe_hot_edge_p (e
))
425 fprintf (dump_file
, "Not considering %s for cloning; no direct calls.\n",
426 cgraph_node_name (node
));
429 if (node
->local
.inline_summary
.self_insns
< n_calls
)
432 fprintf (dump_file
, "Considering %s for cloning; code would shrink.\n",
433 cgraph_node_name (node
));
437 if (!flag_ipa_cp_clone
)
440 fprintf (dump_file
, "Not considering %s for cloning; -fipa-cp-clone disabled.\n",
441 cgraph_node_name (node
));
445 if (!optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node
->decl
)))
448 fprintf (dump_file
, "Not considering %s for cloning; optimizing it for size.\n",
449 cgraph_node_name (node
));
453 /* When profile is available and function is hot, propagate into it even if
454 calls seems cold; constant propagation can improve function's speed
458 if (direct_call_sum
> node
->count
* 90 / 100)
461 fprintf (dump_file
, "Considering %s for cloning; usually called directly.\n",
462 cgraph_node_name (node
));
469 fprintf (dump_file
, "Not considering %s for cloning; no hot calls.\n",
470 cgraph_node_name (node
));
473 fprintf (dump_file
, "Considering %s for cloning.\n",
474 cgraph_node_name (node
));
478 /* Initialize ipcp_lattices array. The lattices corresponding to supported
479 types (integers, real types and Fortran constants defined as const_decls)
480 are initialized to IPA_TOP, the rest of them to IPA_BOTTOM. */
482 ipcp_initialize_node_lattices (struct cgraph_node
*node
)
485 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
486 enum ipa_lattice_type type
;
488 info
->ipcp_lattices
= XCNEWVEC (struct ipcp_lattice
,
489 ipa_get_param_count (info
));
491 if (ipa_is_called_with_var_arguments (info
))
493 else if (!node
->needed
)
495 /* When cloning is allowed, we can assume that externally visible functions
496 are not called. We will compensate this by cloning later. */
497 else if (ipcp_cloning_candidate_p (node
))
498 type
= IPA_TOP
, n_cloning_candidates
++;
502 for (i
= 0; i
< ipa_get_param_count (info
) ; i
++)
503 ipcp_get_ith_lattice (info
, i
)->type
= type
;
506 /* build INTEGER_CST tree with type TREE_TYPE and value according to LAT.
509 build_const_val (struct ipcp_lattice
*lat
, tree tree_type
)
513 gcc_assert (ipcp_lat_is_const (lat
));
516 if (!useless_type_conversion_p (tree_type
, TREE_TYPE (val
)))
518 if (fold_convertible_p (tree_type
, val
))
519 return fold_build1 (NOP_EXPR
, tree_type
, val
);
521 return fold_build1 (VIEW_CONVERT_EXPR
, tree_type
, val
);
526 /* Compute the proper scale for NODE. It is the ratio between the number of
527 direct calls (represented on the incoming cgraph_edges) and sum of all
528 invocations of NODE (represented as count in cgraph_node). */
530 ipcp_compute_node_scale (struct cgraph_node
*node
)
533 struct cgraph_edge
*cs
;
536 /* Compute sum of all counts of callers. */
537 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
539 if (node
->count
== 0)
540 ipcp_set_node_scale (node
, 0);
542 ipcp_set_node_scale (node
, sum
* REG_BR_PROB_BASE
/ node
->count
);
545 /* Initialization and computation of IPCP data structures. This is the initial
546 intraprocedural analysis of functions, which gathers information to be
547 propagated later on. */
549 ipcp_init_stage (void)
551 struct cgraph_node
*node
;
552 struct cgraph_edge
*cs
;
554 for (node
= cgraph_nodes
; node
; node
= node
->next
)
556 ipcp_analyze_node (node
);
557 for (node
= cgraph_nodes
; node
; node
= node
->next
)
561 /* building jump functions */
562 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
564 if (!cs
->callee
->analyzed
)
566 ipa_count_arguments (cs
);
567 if (ipa_get_cs_argument_count (IPA_EDGE_REF (cs
))
568 != ipa_get_param_count (IPA_NODE_REF (cs
->callee
)))
570 /* Handle cases of functions with
571 a variable number of parameters. */
572 ipa_set_called_with_variable_arg (IPA_NODE_REF (cs
->callee
));
573 if (flag_indirect_inlining
)
574 ipa_compute_jump_functions (cs
);
577 ipa_compute_jump_functions (cs
);
582 /* Return true if there are some formal parameters whose value is IPA_TOP (in
583 the whole compilation unit). Change their values to IPA_BOTTOM, since they
584 most probably get their values from outside of this compilation unit. */
586 ipcp_change_tops_to_bottom (void)
589 struct cgraph_node
*node
;
593 for (node
= cgraph_nodes
; node
; node
= node
->next
)
595 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
596 count
= ipa_get_param_count (info
);
597 for (i
= 0; i
< count
; i
++)
599 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
600 if (lat
->type
== IPA_TOP
)
605 fprintf (dump_file
, "Forcing param ");
606 print_generic_expr (dump_file
, ipa_get_ith_param (info
, i
), 0);
607 fprintf (dump_file
, " of node %s to bottom.\n",
608 cgraph_node_name (node
));
610 lat
->type
= IPA_BOTTOM
;
617 /* Interprocedural analysis. The algorithm propagates constants from the
618 caller's parameters to the callee's arguments. */
620 ipcp_propagate_stage (void)
623 struct ipcp_lattice inc_lat
= { IPA_BOTTOM
, NULL
};
624 struct ipcp_lattice new_lat
= { IPA_BOTTOM
, NULL
};
625 struct ipcp_lattice
*dest_lat
;
626 struct cgraph_edge
*cs
;
627 struct ipa_jump_func
*jump_func
;
628 struct ipa_func_list
*wl
;
631 ipa_check_create_node_params ();
632 ipa_check_create_edge_args ();
634 /* Initialize worklist to contain all functions. */
635 wl
= ipa_init_func_list ();
638 struct cgraph_node
*node
= ipa_pop_func_from_list (&wl
);
639 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
641 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
643 struct ipa_node_params
*callee_info
= IPA_NODE_REF (cs
->callee
);
644 struct ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
646 if (ipa_is_called_with_var_arguments (callee_info
))
649 count
= ipa_get_cs_argument_count (args
);
650 for (i
= 0; i
< count
; i
++)
652 jump_func
= ipa_get_ith_jump_func (args
, i
);
653 ipcp_lattice_from_jfunc (info
, &inc_lat
, jump_func
);
654 dest_lat
= ipcp_get_ith_lattice (callee_info
, i
);
655 ipa_lattice_meet (&new_lat
, &inc_lat
, dest_lat
);
656 if (ipcp_lattice_changed (&new_lat
, dest_lat
))
658 dest_lat
->type
= new_lat
.type
;
659 dest_lat
->constant
= new_lat
.constant
;
660 ipa_push_func_to_list (&wl
, cs
->callee
);
667 /* Call the constant propagation algorithm and re-call it if necessary
668 (if there are undetermined values left). */
670 ipcp_iterate_stage (void)
672 struct cgraph_node
*node
;
673 n_cloning_candidates
= 0;
676 fprintf (dump_file
, "\nIPA iterate stage:\n\n");
677 for (node
= cgraph_nodes
; node
; node
= node
->next
)
679 ipcp_initialize_node_lattices (node
);
680 ipcp_compute_node_scale (node
);
682 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
684 ipcp_print_all_lattices (dump_file
);
685 ipcp_function_scale_print (dump_file
);
688 ipcp_propagate_stage ();
689 if (ipcp_change_tops_to_bottom ())
690 /* Some lattices have changed from IPA_TOP to IPA_BOTTOM.
691 This change should be propagated. */
693 gcc_assert (n_cloning_candidates
);
694 ipcp_propagate_stage ();
698 fprintf (dump_file
, "\nIPA lattices after propagation:\n");
699 ipcp_print_all_lattices (dump_file
);
700 if (dump_flags
& TDF_DETAILS
)
701 ipcp_print_profile_data (dump_file
);
705 /* Check conditions to forbid constant insertion to function described by
708 ipcp_node_modifiable_p (struct cgraph_node
*node
)
710 /* Once we will be able to do in-place replacement, we can be more
712 return tree_versionable_function_p (node
->decl
);
715 /* Print count scale data structures. */
717 ipcp_function_scale_print (FILE * f
)
719 struct cgraph_node
*node
;
721 for (node
= cgraph_nodes
; node
; node
= node
->next
)
725 fprintf (f
, "printing scale for %s: ", cgraph_node_name (node
));
726 fprintf (f
, "value is " HOST_WIDE_INT_PRINT_DEC
727 " \n", (HOST_WIDE_INT
) ipcp_get_node_scale (node
));
731 /* Print counts of all cgraph nodes. */
733 ipcp_print_func_profile_counts (FILE * f
)
735 struct cgraph_node
*node
;
737 for (node
= cgraph_nodes
; node
; node
= node
->next
)
739 fprintf (f
, "function %s: ", cgraph_node_name (node
));
740 fprintf (f
, "count is " HOST_WIDE_INT_PRINT_DEC
741 " \n", (HOST_WIDE_INT
) node
->count
);
745 /* Print counts of all cgraph edges. */
747 ipcp_print_call_profile_counts (FILE * f
)
749 struct cgraph_node
*node
;
750 struct cgraph_edge
*cs
;
752 for (node
= cgraph_nodes
; node
; node
= node
->next
)
754 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
756 fprintf (f
, "%s -> %s ", cgraph_node_name (cs
->caller
),
757 cgraph_node_name (cs
->callee
));
758 fprintf (f
, "count is " HOST_WIDE_INT_PRINT_DEC
" \n",
759 (HOST_WIDE_INT
) cs
->count
);
764 /* Print all counts and probabilities of cfg edges of all functions. */
766 ipcp_print_edge_profiles (FILE * f
)
768 struct cgraph_node
*node
;
773 for (node
= cgraph_nodes
; node
; node
= node
->next
)
775 fprintf (f
, "function %s: \n", cgraph_node_name (node
));
779 ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node
->decl
));
780 fprintf (f
, "ENTRY: ");
781 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
782 " %d\n", (HOST_WIDE_INT
) bb
->count
, bb
->frequency
);
785 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
788 EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
790 fprintf (f
, "edge ENTRY -> EXIT, Count");
792 fprintf (f
, "edge ENTRY -> %d, Count", e
->dest
->index
);
793 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
794 " Prob %d\n", (HOST_WIDE_INT
) e
->count
,
797 FOR_EACH_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
799 fprintf (f
, "bb[%d]: ", bb
->index
);
800 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
801 " %d\n", (HOST_WIDE_INT
) bb
->count
, bb
->frequency
);
802 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
805 EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
807 fprintf (f
, "edge %d -> EXIT, Count", e
->src
->index
);
809 fprintf (f
, "edge %d -> %d, Count", e
->src
->index
,
811 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
" Prob %d\n",
812 (HOST_WIDE_INT
) e
->count
, e
->probability
);
819 /* Print counts and frequencies for all basic blocks of all functions. */
821 ipcp_print_bb_profiles (FILE * f
)
824 struct cgraph_node
*node
;
826 for (node
= cgraph_nodes
; node
; node
= node
->next
)
828 fprintf (f
, "function %s: \n", cgraph_node_name (node
));
832 ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node
->decl
));
833 fprintf (f
, "ENTRY: Count");
834 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
835 " Frequency %d\n", (HOST_WIDE_INT
) bb
->count
,
838 FOR_EACH_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
840 fprintf (f
, "bb[%d]: Count", bb
->index
);
841 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
842 " Frequency %d\n", (HOST_WIDE_INT
) bb
->count
,
846 EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node
->decl
));
847 fprintf (f
, "EXIT: Count");
848 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
849 " Frequency %d\n", (HOST_WIDE_INT
) bb
->count
,
856 /* Print profile info for all functions. */
858 ipcp_print_profile_data (FILE * f
)
860 fprintf (f
, "\nNODE COUNTS :\n");
861 ipcp_print_func_profile_counts (f
);
862 fprintf (f
, "\nCS COUNTS stage:\n");
863 ipcp_print_call_profile_counts (f
);
864 fprintf (f
, "\nBB COUNTS and FREQUENCIES :\n");
865 ipcp_print_bb_profiles (f
);
866 fprintf (f
, "\nCFG EDGES COUNTS and PROBABILITIES :\n");
867 ipcp_print_edge_profiles (f
);
870 /* Build and initialize ipa_replace_map struct according to LAT. This struct is
871 processed by versioning, which operates according to the flags set.
872 PARM_TREE is the formal parameter found to be constant. LAT represents the
874 static struct ipa_replace_map
*
875 ipcp_create_replace_map (tree parm_tree
, struct ipcp_lattice
*lat
)
877 struct ipa_replace_map
*replace_map
;
880 replace_map
= XCNEW (struct ipa_replace_map
);
881 const_val
= build_const_val (lat
, TREE_TYPE (parm_tree
));
884 fprintf (dump_file
, " replacing param ");
885 print_generic_expr (dump_file
, parm_tree
, 0);
886 fprintf (dump_file
, " with const ");
887 print_generic_expr (dump_file
, const_val
, 0);
888 fprintf (dump_file
, "\n");
890 replace_map
->old_tree
= parm_tree
;
891 replace_map
->new_tree
= const_val
;
892 replace_map
->replace_p
= true;
893 replace_map
->ref_p
= false;
898 /* Return true if this callsite should be redirected to the original callee
899 (instead of the cloned one). */
901 ipcp_need_redirect_p (struct cgraph_edge
*cs
)
903 struct ipa_node_params
*orig_callee_info
;
905 struct ipa_jump_func
*jump_func
;
906 struct cgraph_node
*node
= cs
->callee
, *orig
;
908 if (!n_cloning_candidates
)
911 if ((orig
= ipcp_get_orig_node (node
)) != NULL
)
913 if (ipcp_get_orig_node (cs
->caller
))
916 orig_callee_info
= IPA_NODE_REF (node
);
917 count
= ipa_get_param_count (orig_callee_info
);
918 for (i
= 0; i
< count
; i
++)
920 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (orig_callee_info
, i
);
921 if (ipcp_lat_is_const (lat
))
923 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
924 if (jump_func
->type
!= IPA_CONST
)
932 /* Fix the callsites and the call graph after function cloning was done. */
934 ipcp_update_callgraph (void)
936 struct cgraph_node
*node
;
938 for (node
= cgraph_nodes
; node
; node
= node
->next
)
939 if (node
->analyzed
&& ipcp_node_is_clone (node
))
941 bitmap args_to_skip
= BITMAP_ALLOC (NULL
);
942 struct cgraph_node
*orig_node
= ipcp_get_orig_node (node
);
943 struct ipa_node_params
*info
= IPA_NODE_REF (orig_node
);
944 int i
, count
= ipa_get_param_count (info
);
945 struct cgraph_edge
*cs
, *next
;
947 for (i
= 0; i
< count
; i
++)
949 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
950 tree parm_tree
= ipa_get_ith_param (info
, i
);
952 /* We can proactively remove obviously unused arguments. */
953 if (is_gimple_reg (parm_tree
)
954 && !gimple_default_def (DECL_STRUCT_FUNCTION (orig_node
->decl
),
957 bitmap_set_bit (args_to_skip
, i
);
961 if (lat
->type
== IPA_CONST_VALUE
)
962 bitmap_set_bit (args_to_skip
, i
);
964 for (cs
= node
->callers
; cs
; cs
= next
)
966 next
= cs
->next_caller
;
967 if (ipcp_node_is_clone (cs
->caller
) || !ipcp_need_redirect_p (cs
))
970 gimple_stmt_iterator gsi
;
972 current_function_decl
= cs
->caller
->decl
;
973 push_cfun (DECL_STRUCT_FUNCTION (cs
->caller
->decl
));
975 new_stmt
= giple_copy_call_skip_args (cs
->call_stmt
, args_to_skip
);
976 gsi
= gsi_for_stmt (cs
->call_stmt
);
977 gsi_replace (&gsi
, new_stmt
, true);
978 cgraph_set_call_stmt (cs
, new_stmt
);
980 current_function_decl
= NULL
;
984 cgraph_redirect_edge_callee (cs
, orig_node
);
985 gimple_call_set_fndecl (cs
->call_stmt
, orig_node
->decl
);
991 /* Update all cfg basic blocks in NODE according to SCALE. */
993 ipcp_update_bb_counts (struct cgraph_node
*node
, gcov_type scale
)
997 FOR_ALL_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
998 bb
->count
= bb
->count
* scale
/ REG_BR_PROB_BASE
;
1001 /* Update all cfg edges in NODE according to SCALE. */
1003 ipcp_update_edges_counts (struct cgraph_node
*node
, gcov_type scale
)
1009 FOR_ALL_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
1010 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1011 e
->count
= e
->count
* scale
/ REG_BR_PROB_BASE
;
1014 /* Update profiling info for versioned functions and the functions they were
1017 ipcp_update_profiling (void)
1019 struct cgraph_node
*node
, *orig_node
;
1020 gcov_type scale
, scale_complement
;
1021 struct cgraph_edge
*cs
;
1023 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1025 if (ipcp_node_is_clone (node
))
1027 orig_node
= ipcp_get_orig_node (node
);
1028 scale
= ipcp_get_node_scale (orig_node
);
1029 node
->count
= orig_node
->count
* scale
/ REG_BR_PROB_BASE
;
1030 scale_complement
= REG_BR_PROB_BASE
- scale
;
1032 orig_node
->count
* scale_complement
/ REG_BR_PROB_BASE
;
1033 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
1034 cs
->count
= cs
->count
* scale
/ REG_BR_PROB_BASE
;
1035 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
1036 cs
->count
= cs
->count
* scale_complement
/ REG_BR_PROB_BASE
;
1037 ipcp_update_bb_counts (node
, scale
);
1038 ipcp_update_bb_counts (orig_node
, scale_complement
);
1039 ipcp_update_edges_counts (node
, scale
);
1040 ipcp_update_edges_counts (orig_node
, scale_complement
);
1045 /* If NODE was cloned, how much would program grow? */
1047 ipcp_estimate_growth (struct cgraph_node
*node
)
1049 struct cgraph_edge
*cs
;
1050 int redirectable_node_callers
= 0;
1051 int removable_args
= 0;
1052 bool need_original
= node
->needed
;
1053 struct ipa_node_params
*info
;
1057 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
1058 if (!ipcp_need_redirect_p (cs
))
1059 redirectable_node_callers
++;
1061 need_original
= true;
1063 /* If we will be able to fully replace orignal node, we never increase
1068 info
= IPA_NODE_REF (node
);
1069 count
= ipa_get_param_count (info
);
1070 for (i
= 0; i
< count
; i
++)
1072 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
1073 tree parm_tree
= ipa_get_ith_param (info
, i
);
1075 /* We can proactively remove obviously unused arguments. */
1076 if (is_gimple_reg (parm_tree
)
1077 && !gimple_default_def (DECL_STRUCT_FUNCTION (node
->decl
),
1081 if (lat
->type
== IPA_CONST_VALUE
)
1085 /* We make just very simple estimate of savings for removal of operand from
1086 call site. Precise cost is dificult to get, as our size metric counts
1087 constants and moves as free. Generally we are looking for cases that
1088 small function is called very many times. */
1089 growth
= node
->local
.inline_summary
.self_insns
1090 - removable_args
* redirectable_node_callers
;
1097 /* Estimate cost of cloning NODE. */
1099 ipcp_estimate_cloning_cost (struct cgraph_node
*node
)
1102 gcov_type count_sum
= 1;
1103 struct cgraph_edge
*e
;
1106 cost
= ipcp_estimate_growth (node
) * 1000;
1110 fprintf (dump_file
, "Versioning of %s will save code size\n",
1111 cgraph_node_name (node
));
1115 for (e
= node
->callers
; e
; e
= e
->next_caller
)
1116 if (!bitmap_bit_p (dead_nodes
, e
->caller
->uid
)
1117 && !ipcp_need_redirect_p (e
))
1119 count_sum
+= e
->count
;
1120 freq_sum
+= e
->frequency
+ 1;
1124 cost
/= count_sum
* 1000 / max_count
+ 1;
1126 cost
/= freq_sum
* 1000 / REG_BR_PROB_BASE
+ 1;
1128 fprintf (dump_file
, "Cost of versioning %s is %i, (size: %i, freq: %i)\n",
1129 cgraph_node_name (node
), cost
, node
->local
.inline_summary
.self_insns
,
1134 /* Return number of live constant parameters. */
1136 ipcp_const_param_count (struct cgraph_node
*node
)
1138 int const_param
= 0;
1139 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1140 int count
= ipa_get_param_count (info
);
1143 for (i
= 0; i
< count
; i
++)
1145 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
1146 tree parm_tree
= ipa_get_ith_param (info
, i
);
1147 if (ipcp_lat_is_insertable (lat
)
1148 /* Do not count obviously unused arguments. */
1149 && (!is_gimple_reg (parm_tree
)
1150 || gimple_default_def (DECL_STRUCT_FUNCTION (node
->decl
),
1157 /* Propagate the constant parameters found by ipcp_iterate_stage()
1158 to the function's code. */
1160 ipcp_insert_stage (void)
1162 struct cgraph_node
*node
, *node1
= NULL
;
1164 VEC (cgraph_edge_p
, heap
) * redirect_callers
;
1165 varray_type replace_trees
;
1166 struct cgraph_edge
*cs
;
1167 int node_callers
, count
;
1169 struct ipa_replace_map
*replace_param
;
1171 long overall_insns
= 0, new_insns
= 0;
1174 ipa_check_create_node_params ();
1175 ipa_check_create_edge_args ();
1177 fprintf (dump_file
, "\nIPA insert stage:\n\n");
1179 dead_nodes
= BITMAP_ALLOC (NULL
);
1181 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1184 if (node
->count
> max_count
)
1185 max_count
= node
->count
;
1186 overall_insns
+= node
->local
.inline_summary
.self_insns
;
1189 max_new_insns
= overall_insns
;
1190 if (max_new_insns
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
1191 max_new_insns
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
1192 max_new_insns
= max_new_insns
* PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH
) / 100 + 1;
1194 /* First collect all functions we proved to have constant arguments to heap. */
1195 heap
= fibheap_new ();
1196 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1198 struct ipa_node_params
*info
;
1199 /* Propagation of the constant is forbidden in certain conditions. */
1200 if (!node
->analyzed
|| !ipcp_node_modifiable_p (node
))
1202 info
= IPA_NODE_REF (node
);
1203 if (ipa_is_called_with_var_arguments (info
))
1205 if (ipcp_const_param_count (node
))
1206 node
->aux
= fibheap_insert (heap
, ipcp_estimate_cloning_cost (node
), node
);
1209 /* Now clone in priority order until code size growth limits are met or
1211 while (!fibheap_empty (heap
))
1213 struct ipa_node_params
*info
;
1215 bitmap args_to_skip
;
1217 node
= (struct cgraph_node
*)fibheap_extract_min (heap
);
1220 fprintf (dump_file
, "considering function %s\n",
1221 cgraph_node_name (node
));
1223 growth
= ipcp_estimate_growth (node
);
1225 if (new_insns
+ growth
> max_new_insns
)
1228 && optimize_function_for_size_p (DECL_STRUCT_FUNCTION (node
->decl
)))
1231 fprintf (dump_file
, "Not versioning, cold code would grow");
1235 new_insns
+= growth
;
1237 info
= IPA_NODE_REF (node
);
1238 count
= ipa_get_param_count (info
);
1240 VARRAY_GENERIC_PTR_INIT (replace_trees
, ipcp_const_param_count (node
),
1242 args_to_skip
= BITMAP_ALLOC (NULL
);
1243 for (i
= 0; i
< count
; i
++)
1245 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
1246 parm_tree
= ipa_get_ith_param (info
, i
);
1248 /* We can proactively remove obviously unused arguments. */
1249 if (is_gimple_reg (parm_tree
)
1250 && !gimple_default_def (DECL_STRUCT_FUNCTION (node
->decl
),
1253 bitmap_set_bit (args_to_skip
, i
);
1257 if (lat
->type
== IPA_CONST_VALUE
)
1260 ipcp_create_replace_map (parm_tree
, lat
);
1261 VARRAY_PUSH_GENERIC_PTR (replace_trees
, replace_param
);
1262 bitmap_set_bit (args_to_skip
, i
);
1266 /* Compute how many callers node has. */
1268 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
1270 redirect_callers
= VEC_alloc (cgraph_edge_p
, heap
, node_callers
);
1271 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
1272 VEC_quick_push (cgraph_edge_p
, redirect_callers
, cs
);
1274 /* Redirecting all the callers of the node to the
1275 new versioned node. */
1277 cgraph_function_versioning (node
, redirect_callers
, replace_trees
,
1279 BITMAP_FREE (args_to_skip
);
1280 VEC_free (cgraph_edge_p
, heap
, redirect_callers
);
1281 VARRAY_CLEAR (replace_trees
);
1285 fprintf (dump_file
, "versioned function %s with growth %i, overall %i\n",
1286 cgraph_node_name (node
), (int)growth
, (int)new_insns
);
1287 ipcp_init_cloned_node (node
, node1
);
1289 /* We've possibly introduced direct calls. */
1290 ipcp_update_cloned_node (node1
);
1293 dump_function_to_file (node1
->decl
, dump_file
, dump_flags
);
1295 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
1296 if (cs
->callee
->aux
)
1298 fibheap_delete_node (heap
, (fibnode_t
) cs
->callee
->aux
);
1299 cs
->callee
->aux
= fibheap_insert (heap
,
1300 ipcp_estimate_cloning_cost (cs
->callee
),
1305 while (!fibheap_empty (heap
))
1308 fprintf (dump_file
, "skipping function %s\n",
1309 cgraph_node_name (node
));
1310 node
= (struct cgraph_node
*) fibheap_extract_min (heap
);
1313 fibheap_delete (heap
);
1314 BITMAP_FREE (dead_nodes
);
1315 ipcp_update_callgraph ();
1316 ipcp_update_profiling ();
1319 /* The IPCP driver. */
1323 cgraph_remove_unreachable_nodes (true,dump_file
);
1326 fprintf (dump_file
, "\nIPA structures before propagation:\n");
1327 if (dump_flags
& TDF_DETAILS
)
1328 ipa_print_all_params (dump_file
);
1329 ipa_print_all_jump_functions (dump_file
);
1331 /* 2. Do the interprocedural propagation. */
1332 ipcp_iterate_stage ();
1333 /* 3. Insert the constants found to the functions. */
1334 ipcp_insert_stage ();
1335 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1337 fprintf (dump_file
, "\nProfiling info after insert stage:\n");
1338 ipcp_print_profile_data (dump_file
);
1340 /* Free all IPCP structures. */
1341 free_all_ipa_structures_after_ipa_cp ();
1343 fprintf (dump_file
, "\nIPA constant propagation end\n");
1347 /* Note function body size. */
1349 ipcp_generate_summary (void)
1352 fprintf (dump_file
, "\nIPA constant propagation start:\n");
1353 ipa_check_create_node_params ();
1354 ipa_check_create_edge_args ();
1355 ipa_register_cgraph_hooks ();
1356 /* 1. Call the init stage to initialize
1357 the ipa_node_params and ipa_edge_args structures. */
1361 /* Gate for IPCP optimization. */
1363 cgraph_gate_cp (void)
1368 struct ipa_opt_pass pass_ipa_cp
=
1373 cgraph_gate_cp
, /* gate */
1374 ipcp_driver
, /* execute */
1377 0, /* static_pass_number */
1378 TV_IPA_CONSTANT_PROP
, /* tv_id */
1379 0, /* properties_required */
1380 PROP_trees
, /* properties_provided */
1381 0, /* properties_destroyed */
1382 0, /* todo_flags_start */
1383 TODO_dump_cgraph
| TODO_dump_func
|
1384 TODO_remove_functions
/* todo_flags_finish */
1386 ipcp_generate_summary
, /* generate_summary */
1387 NULL
, /* write_summary */
1388 NULL
, /* read_summary */
1389 NULL
, /* function_read_summary */
1391 NULL
, /* function_transform */
1392 NULL
, /* variable_transform */