1 /* Interprocedural constant propagation
2 Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Razya Ladelsky <RAZYA@il.ibm.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* Interprocedural constant propagation. The aim of interprocedural constant
23 propagation (IPCP) is to find which function's argument has the same
24 constant value in each invocation throughout the whole program. For example,
25 consider the following program:
29 printf ("value is %d",y);
49 The IPCP algorithm will find that g's formal argument y is always called
52 The algorithm used is based on "Interprocedural Constant Propagation", by
53 Challahan David, Keith D Cooper, Ken Kennedy, Linda Torczon, Comp86, pg
56 The optimization is divided into three stages:
58 First stage - intraprocedural analysis
59 =======================================
60 This phase computes jump_function and modification flags.
62 A jump function for a callsite represents the values passed as an actual
63 arguments of a given callsite. There are three types of values:
64 Pass through - the caller's formal parameter is passed as an actual argument.
65 Constant - a constant is passed as an actual argument.
66 Unknown - neither of the above.
68 The jump function info, ipa_jump_func, is stored in ipa_edge_args
69 structure (defined in ipa_prop.h and pointed to by cgraph_node->aux)
70 modified_flags are defined in ipa_node_params structure
71 (defined in ipa_prop.h and pointed to by cgraph_edge->aux).
73 -ipcp_init_stage() is the first stage driver.
75 Second stage - interprocedural analysis
76 ========================================
77 This phase does the interprocedural constant propagation.
78 It computes lattices for all formal parameters in the program
79 and their value that may be:
81 BOTTOM - non constant.
82 CONSTANT - constant value.
84 Lattice describing a formal parameter p will have a constant value if all
85 callsites invoking this function have the same constant value passed to p.
87 The lattices are stored in ipcp_lattice which is itself in ipa_node_params
88 structure (defined in ipa_prop.h and pointed to by cgraph_edge->aux).
90 -ipcp_iterate_stage() is the second stage driver.
92 Third phase - transformation of function code
93 ============================================
94 Propagates the constant-valued formals into the function.
95 For each function whose parameters are constants, we create its clone.
97 Then we process the clone in two ways:
98 1. We insert an assignment statement 'parameter = const' at the beginning
99 of the cloned function.
100 2. For read-only parameters that do not live in memory, we replace all their
101 uses with the constant.
103 We also need to modify some callsites to call the cloned functions instead
104 of the original ones. For a callsite passing an argument found to be a
105 constant by IPCP, there are two different cases to handle:
106 1. A constant is passed as an argument. In this case the callsite in the
107 should be redirected to call the cloned callee.
108 2. A parameter (of the caller) passed as an argument (pass through
109 argument). In such cases both the caller and the callee have clones and
110 only the callsite in the cloned caller is redirected to call to the
113 This update is done in two steps: First all cloned functions are created
114 during a traversal of the call graph, during which all callsites are
115 redirected to call the cloned function. Then the callsites are traversed
116 and many calls redirected back to fit the description above.
118 -ipcp_insert_stage() is the third phase driver.
124 #include "coretypes.h"
128 #include "ipa-prop.h"
129 #include "tree-flow.h"
130 #include "tree-pass.h"
133 #include "diagnostic.h"
134 #include "tree-dump.h"
135 #include "tree-inline.h"
139 /* Number of functions identified as candidates for cloning. When not cloning
140 we can simplify iterate stage not forcing it to go through the decision
141 on what is profitable and what not. */
142 static int n_cloning_candidates
;
144 /* Maximal count found in program. */
145 static gcov_type max_count
;
147 /* Cgraph nodes that has been completely replaced by cloning during iterate
148 * stage and will be removed after ipcp is finished. */
149 static bitmap dead_nodes
;
151 static void ipcp_print_profile_data (FILE *);
152 static void ipcp_function_scale_print (FILE *);
154 /* Get the original node field of ipa_node_params associated with node NODE. */
155 static inline struct cgraph_node
*
156 ipcp_get_orig_node (struct cgraph_node
*node
)
158 return IPA_NODE_REF (node
)->ipcp_orig_node
;
161 /* Return true if NODE describes a cloned/versioned function. */
163 ipcp_node_is_clone (struct cgraph_node
*node
)
165 return (ipcp_get_orig_node (node
) != NULL
);
168 /* Create ipa_node_params and its data structures for NEW_NODE. Set ORIG_NODE
169 as the ipcp_orig_node field in ipa_node_params. */
171 ipcp_init_cloned_node (struct cgraph_node
*orig_node
,
172 struct cgraph_node
*new_node
)
174 ipa_check_create_node_params ();
175 ipa_initialize_node_params (new_node
);
176 IPA_NODE_REF (new_node
)->ipcp_orig_node
= orig_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_initialize_node_params (node
);
187 ipa_detect_param_modifications (node
);
190 /* Return scale for NODE. */
191 static inline gcov_type
192 ipcp_get_node_scale (struct cgraph_node
*node
)
194 return IPA_NODE_REF (node
)->count_scale
;
197 /* Set COUNT as scale for NODE. */
199 ipcp_set_node_scale (struct cgraph_node
*node
, gcov_type count
)
201 IPA_NODE_REF (node
)->count_scale
= count
;
204 /* Return whether LAT is a constant lattice. */
206 ipcp_lat_is_const (struct ipcp_lattice
*lat
)
208 if (lat
->type
== IPA_CONST_VALUE
)
214 /* Return whether LAT is a constant lattice that ipa-cp can actually insert
215 into the code (i.e. constants excluding member pointers and pointers). */
217 ipcp_lat_is_insertable (struct ipcp_lattice
*lat
)
219 return lat
->type
== IPA_CONST_VALUE
;
222 /* Return true if LAT1 and LAT2 are equal. */
224 ipcp_lats_are_equal (struct ipcp_lattice
*lat1
, struct ipcp_lattice
*lat2
)
226 gcc_assert (ipcp_lat_is_const (lat1
) && ipcp_lat_is_const (lat2
));
227 if (lat1
->type
!= lat2
->type
)
230 if (TREE_CODE (lat1
->constant
) == ADDR_EXPR
231 && TREE_CODE (lat2
->constant
) == ADDR_EXPR
232 && TREE_CODE (TREE_OPERAND (lat1
->constant
, 0)) == CONST_DECL
233 && TREE_CODE (TREE_OPERAND (lat2
->constant
, 0)) == CONST_DECL
)
234 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (lat1
->constant
, 0)),
235 DECL_INITIAL (TREE_OPERAND (lat2
->constant
, 0)), 0);
237 return operand_equal_p (lat1
->constant
, lat2
->constant
, 0);
240 /* Compute Meet arithmetics:
241 Meet (IPA_BOTTOM, x) = IPA_BOTTOM
243 Meet (const_a,const_b) = IPA_BOTTOM, if const_a != const_b.
244 MEET (const_a,const_b) = const_a, if const_a == const_b.*/
246 ipa_lattice_meet (struct ipcp_lattice
*res
, struct ipcp_lattice
*lat1
,
247 struct ipcp_lattice
*lat2
)
249 if (lat1
->type
== IPA_BOTTOM
|| lat2
->type
== IPA_BOTTOM
)
251 res
->type
= IPA_BOTTOM
;
254 if (lat1
->type
== IPA_TOP
)
256 res
->type
= lat2
->type
;
257 res
->constant
= lat2
->constant
;
260 if (lat2
->type
== IPA_TOP
)
262 res
->type
= lat1
->type
;
263 res
->constant
= lat1
->constant
;
266 if (!ipcp_lats_are_equal (lat1
, lat2
))
268 res
->type
= IPA_BOTTOM
;
271 res
->type
= lat1
->type
;
272 res
->constant
= lat1
->constant
;
275 /* Return the lattice corresponding to the Ith formal parameter of the function
276 described by INFO. */
277 static inline struct ipcp_lattice
*
278 ipcp_get_lattice (struct ipa_node_params
*info
, int i
)
280 return &(info
->params
[i
].ipcp_lattice
);
283 /* Given the jump function JFUNC, compute the lattice LAT that describes the
284 value coming down the callsite. INFO describes the caller node so that
285 pass-through jump functions can be evaluated. */
287 ipcp_lattice_from_jfunc (struct ipa_node_params
*info
, struct ipcp_lattice
*lat
,
288 struct ipa_jump_func
*jfunc
)
290 if (jfunc
->type
== IPA_JF_CONST
)
292 lat
->type
= IPA_CONST_VALUE
;
293 lat
->constant
= jfunc
->value
.constant
;
295 else if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
297 struct ipcp_lattice
*caller_lat
;
300 caller_lat
= ipcp_get_lattice (info
, jfunc
->value
.pass_through
.formal_id
);
301 lat
->type
= caller_lat
->type
;
302 if (caller_lat
->type
!= IPA_CONST_VALUE
)
304 cst
= caller_lat
->constant
;
306 if (jfunc
->value
.pass_through
.operation
!= NOP_EXPR
)
309 if (TREE_CODE_CLASS (jfunc
->value
.pass_through
.operation
)
311 restype
= boolean_type_node
;
313 restype
= TREE_TYPE (cst
);
314 cst
= fold_binary (jfunc
->value
.pass_through
.operation
,
315 restype
, cst
, jfunc
->value
.pass_through
.operand
);
317 if (!cst
|| !is_gimple_ip_invariant (cst
))
318 lat
->type
= IPA_BOTTOM
;
321 else if (jfunc
->type
== IPA_JF_ANCESTOR
)
323 struct ipcp_lattice
*caller_lat
;
327 caller_lat
= ipcp_get_lattice (info
, jfunc
->value
.ancestor
.formal_id
);
328 lat
->type
= caller_lat
->type
;
329 if (caller_lat
->type
!= IPA_CONST_VALUE
)
331 if (TREE_CODE (caller_lat
->constant
) != ADDR_EXPR
)
333 /* This can happen when the constant is a NULL pointer. */
334 lat
->type
= IPA_BOTTOM
;
337 t
= TREE_OPERAND (caller_lat
->constant
, 0);
338 ok
= build_ref_for_offset (&t
, TREE_TYPE (t
),
339 jfunc
->value
.ancestor
.offset
,
340 jfunc
->value
.ancestor
.type
, false);
343 lat
->type
= IPA_BOTTOM
;
344 lat
->constant
= NULL_TREE
;
347 lat
->constant
= build_fold_addr_expr (t
);
350 lat
->type
= IPA_BOTTOM
;
353 /* True when OLD_LAT and NEW_LAT values are not the same. */
356 ipcp_lattice_changed (struct ipcp_lattice
*old_lat
,
357 struct ipcp_lattice
*new_lat
)
359 if (old_lat
->type
== new_lat
->type
)
361 if (!ipcp_lat_is_const (old_lat
))
363 if (ipcp_lats_are_equal (old_lat
, new_lat
))
369 /* Print all ipcp_lattices of all functions to F. */
371 ipcp_print_all_lattices (FILE * f
)
373 struct cgraph_node
*node
;
376 fprintf (f
, "\nLattice:\n");
377 for (node
= cgraph_nodes
; node
; node
= node
->next
)
379 struct ipa_node_params
*info
;
383 info
= IPA_NODE_REF (node
);
384 fprintf (f
, " Node: %s:\n", cgraph_node_name (node
));
385 count
= ipa_get_param_count (info
);
386 for (i
= 0; i
< count
; i
++)
388 struct ipcp_lattice
*lat
= ipcp_get_lattice (info
, i
);
390 fprintf (f
, " param [%d]: ", i
);
391 if (lat
->type
== IPA_CONST_VALUE
)
393 tree cst
= lat
->constant
;
394 fprintf (f
, "type is CONST ");
395 print_generic_expr (f
, cst
, 0);
396 if (TREE_CODE (cst
) == ADDR_EXPR
397 && TREE_CODE (TREE_OPERAND (cst
, 0)) == CONST_DECL
)
400 print_generic_expr (f
, DECL_INITIAL (TREE_OPERAND (cst
, 0)),
405 else if (lat
->type
== IPA_TOP
)
406 fprintf (f
, "type is TOP\n");
408 fprintf (f
, "type is BOTTOM\n");
413 /* Return true if ipcp algorithms would allow cloning NODE. */
416 ipcp_versionable_function_p (struct cgraph_node
*node
)
418 tree decl
= node
->decl
;
421 /* There are a number of generic reasons functions cannot be versioned. */
422 if (!tree_versionable_function_p (decl
))
425 /* Removing arguments doesn't work if the function takes varargs. */
426 if (DECL_STRUCT_FUNCTION (decl
)->stdarg
)
429 /* Removing arguments doesn't work if we use __builtin_apply_args. */
430 FOR_EACH_BB_FN (bb
, DECL_STRUCT_FUNCTION (decl
))
432 gimple_stmt_iterator gsi
;
433 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
435 const_gimple stmt
= gsi_stmt (gsi
);
438 if (!is_gimple_call (stmt
))
440 t
= gimple_call_fndecl (stmt
);
443 if (DECL_BUILT_IN_CLASS (t
) == BUILT_IN_NORMAL
444 && DECL_FUNCTION_CODE (t
) == BUILT_IN_APPLY_ARGS
)
452 /* Return true if this NODE is viable candidate for cloning. */
454 ipcp_cloning_candidate_p (struct cgraph_node
*node
)
458 gcov_type direct_call_sum
= 0;
459 struct cgraph_edge
*e
;
461 /* We never clone functions that are not visible from outside.
462 FIXME: in future we should clone such functions when they are called with
463 different constants, but current ipcp implementation is not good on this.
465 if (cgraph_only_called_directly_p (node
) || !node
->analyzed
)
468 if (cgraph_function_body_availability (node
) <= AVAIL_OVERWRITABLE
)
471 fprintf (dump_file
, "Not considering %s for cloning; body is overwrittable.\n",
472 cgraph_node_name (node
));
475 if (!ipcp_versionable_function_p (node
))
478 fprintf (dump_file
, "Not considering %s for cloning; body is not versionable.\n",
479 cgraph_node_name (node
));
482 for (e
= node
->callers
; e
; e
= e
->next_caller
)
484 direct_call_sum
+= e
->count
;
486 if (cgraph_maybe_hot_edge_p (e
))
493 fprintf (dump_file
, "Not considering %s for cloning; no direct calls.\n",
494 cgraph_node_name (node
));
497 if (node
->local
.inline_summary
.self_size
< n_calls
)
500 fprintf (dump_file
, "Considering %s for cloning; code would shrink.\n",
501 cgraph_node_name (node
));
505 if (!flag_ipa_cp_clone
)
508 fprintf (dump_file
, "Not considering %s for cloning; -fipa-cp-clone disabled.\n",
509 cgraph_node_name (node
));
513 if (!optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node
->decl
)))
516 fprintf (dump_file
, "Not considering %s for cloning; optimizing it for size.\n",
517 cgraph_node_name (node
));
521 /* When profile is available and function is hot, propagate into it even if
522 calls seems cold; constant propagation can improve function's speed
526 if (direct_call_sum
> node
->count
* 90 / 100)
529 fprintf (dump_file
, "Considering %s for cloning; usually called directly.\n",
530 cgraph_node_name (node
));
537 fprintf (dump_file
, "Not considering %s for cloning; no hot calls.\n",
538 cgraph_node_name (node
));
542 fprintf (dump_file
, "Considering %s for cloning.\n",
543 cgraph_node_name (node
));
547 /* Initialize ipcp_lattices array. The lattices corresponding to supported
548 types (integers, real types and Fortran constants defined as const_decls)
549 are initialized to IPA_TOP, the rest of them to IPA_BOTTOM. */
551 ipcp_initialize_node_lattices (struct cgraph_node
*node
)
554 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
555 enum ipa_lattice_type type
;
557 if (ipa_is_called_with_var_arguments (info
))
559 else if (cgraph_only_called_directly_p (node
))
561 /* When cloning is allowed, we can assume that externally visible functions
562 are not called. We will compensate this by cloning later. */
563 else if (ipcp_cloning_candidate_p (node
))
564 type
= IPA_TOP
, n_cloning_candidates
++;
568 for (i
= 0; i
< ipa_get_param_count (info
) ; i
++)
569 ipcp_get_lattice (info
, i
)->type
= type
;
572 /* build INTEGER_CST tree with type TREE_TYPE and value according to LAT.
575 build_const_val (struct ipcp_lattice
*lat
, tree tree_type
)
579 gcc_assert (ipcp_lat_is_const (lat
));
582 if (!useless_type_conversion_p (tree_type
, TREE_TYPE (val
)))
584 if (fold_convertible_p (tree_type
, val
))
585 return fold_build1 (NOP_EXPR
, tree_type
, val
);
587 return fold_build1 (VIEW_CONVERT_EXPR
, tree_type
, val
);
592 /* Compute the proper scale for NODE. It is the ratio between the number of
593 direct calls (represented on the incoming cgraph_edges) and sum of all
594 invocations of NODE (represented as count in cgraph_node).
596 FIXME: This code is wrong. Since the callers can be also clones and
597 the clones are not scaled yet, the sums gets unrealistically high.
598 To properly compute the counts, we would need to do propagation across
599 callgraph (as external call to A might imply call to non-clonned B
600 if A's clone calls clonned B). */
602 ipcp_compute_node_scale (struct cgraph_node
*node
)
605 struct cgraph_edge
*cs
;
608 /* Compute sum of all counts of callers. */
609 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
611 /* Work around the unrealistically high sum problem. We just don't want
612 the non-cloned body to have negative or very low frequency. Since
613 majority of execution time will be spent in clones anyway, this should
614 give good enough profile. */
615 if (sum
> node
->count
* 9 / 10)
616 sum
= node
->count
* 9 / 10;
617 if (node
->count
== 0)
618 ipcp_set_node_scale (node
, 0);
620 ipcp_set_node_scale (node
, sum
* REG_BR_PROB_BASE
/ node
->count
);
623 /* Initialization and computation of IPCP data structures. This is the initial
624 intraprocedural analysis of functions, which gathers information to be
625 propagated later on. */
627 ipcp_init_stage (void)
629 struct cgraph_node
*node
;
630 struct cgraph_edge
*cs
;
632 for (node
= cgraph_nodes
; node
; node
= node
->next
)
634 ipcp_analyze_node (node
);
635 for (node
= cgraph_nodes
; node
; node
= node
->next
)
639 /* building jump functions */
640 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
642 /* We do not need to bother analyzing calls to unknown
643 functions unless they may become known during lto/whopr. */
644 if (!cs
->callee
->analyzed
&& !flag_lto
&& !flag_whopr
)
646 ipa_count_arguments (cs
);
647 if (ipa_get_cs_argument_count (IPA_EDGE_REF (cs
))
648 != ipa_get_param_count (IPA_NODE_REF (cs
->callee
)))
649 ipa_set_called_with_variable_arg (IPA_NODE_REF (cs
->callee
));
650 ipa_compute_jump_functions (cs
);
655 /* Return true if there are some formal parameters whose value is IPA_TOP (in
656 the whole compilation unit). Change their values to IPA_BOTTOM, since they
657 most probably get their values from outside of this compilation unit. */
659 ipcp_change_tops_to_bottom (void)
662 struct cgraph_node
*node
;
666 for (node
= cgraph_nodes
; node
; node
= node
->next
)
668 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
669 count
= ipa_get_param_count (info
);
670 for (i
= 0; i
< count
; i
++)
672 struct ipcp_lattice
*lat
= ipcp_get_lattice (info
, i
);
673 if (lat
->type
== IPA_TOP
)
678 fprintf (dump_file
, "Forcing param ");
679 print_generic_expr (dump_file
, ipa_get_param (info
, i
), 0);
680 fprintf (dump_file
, " of node %s to bottom.\n",
681 cgraph_node_name (node
));
683 lat
->type
= IPA_BOTTOM
;
690 /* Interprocedural analysis. The algorithm propagates constants from the
691 caller's parameters to the callee's arguments. */
693 ipcp_propagate_stage (void)
696 struct ipcp_lattice inc_lat
= { IPA_BOTTOM
, NULL
};
697 struct ipcp_lattice new_lat
= { IPA_BOTTOM
, NULL
};
698 struct ipcp_lattice
*dest_lat
;
699 struct cgraph_edge
*cs
;
700 struct ipa_jump_func
*jump_func
;
701 struct ipa_func_list
*wl
;
704 ipa_check_create_node_params ();
705 ipa_check_create_edge_args ();
707 /* Initialize worklist to contain all functions. */
708 wl
= ipa_init_func_list ();
711 struct cgraph_node
*node
= ipa_pop_func_from_list (&wl
);
712 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
714 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
716 struct ipa_node_params
*callee_info
= IPA_NODE_REF (cs
->callee
);
717 struct ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
719 if (ipa_is_called_with_var_arguments (callee_info
)
720 || !cs
->callee
->analyzed
721 || ipa_is_called_with_var_arguments (callee_info
))
724 count
= ipa_get_cs_argument_count (args
);
725 for (i
= 0; i
< count
; i
++)
727 jump_func
= ipa_get_ith_jump_func (args
, i
);
728 ipcp_lattice_from_jfunc (info
, &inc_lat
, jump_func
);
729 dest_lat
= ipcp_get_lattice (callee_info
, i
);
730 ipa_lattice_meet (&new_lat
, &inc_lat
, dest_lat
);
731 if (ipcp_lattice_changed (&new_lat
, dest_lat
))
733 dest_lat
->type
= new_lat
.type
;
734 dest_lat
->constant
= new_lat
.constant
;
735 ipa_push_func_to_list (&wl
, cs
->callee
);
742 /* Call the constant propagation algorithm and re-call it if necessary
743 (if there are undetermined values left). */
745 ipcp_iterate_stage (void)
747 struct cgraph_node
*node
;
748 n_cloning_candidates
= 0;
751 fprintf (dump_file
, "\nIPA iterate stage:\n\n");
754 ipa_update_after_lto_read ();
756 for (node
= cgraph_nodes
; node
; node
= node
->next
)
758 ipcp_initialize_node_lattices (node
);
759 ipcp_compute_node_scale (node
);
761 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
763 ipcp_print_all_lattices (dump_file
);
764 ipcp_function_scale_print (dump_file
);
767 ipcp_propagate_stage ();
768 if (ipcp_change_tops_to_bottom ())
769 /* Some lattices have changed from IPA_TOP to IPA_BOTTOM.
770 This change should be propagated. */
772 gcc_assert (n_cloning_candidates
);
773 ipcp_propagate_stage ();
777 fprintf (dump_file
, "\nIPA lattices after propagation:\n");
778 ipcp_print_all_lattices (dump_file
);
779 if (dump_flags
& TDF_DETAILS
)
780 ipcp_print_profile_data (dump_file
);
784 /* Check conditions to forbid constant insertion to function described by
787 ipcp_node_modifiable_p (struct cgraph_node
*node
)
789 /* Once we will be able to do in-place replacement, we can be more
791 return ipcp_versionable_function_p (node
);
794 /* Print count scale data structures. */
796 ipcp_function_scale_print (FILE * f
)
798 struct cgraph_node
*node
;
800 for (node
= cgraph_nodes
; node
; node
= node
->next
)
804 fprintf (f
, "printing scale for %s: ", cgraph_node_name (node
));
805 fprintf (f
, "value is " HOST_WIDE_INT_PRINT_DEC
806 " \n", (HOST_WIDE_INT
) ipcp_get_node_scale (node
));
810 /* Print counts of all cgraph nodes. */
812 ipcp_print_func_profile_counts (FILE * f
)
814 struct cgraph_node
*node
;
816 for (node
= cgraph_nodes
; node
; node
= node
->next
)
818 fprintf (f
, "function %s: ", cgraph_node_name (node
));
819 fprintf (f
, "count is " HOST_WIDE_INT_PRINT_DEC
820 " \n", (HOST_WIDE_INT
) node
->count
);
824 /* Print counts of all cgraph edges. */
826 ipcp_print_call_profile_counts (FILE * f
)
828 struct cgraph_node
*node
;
829 struct cgraph_edge
*cs
;
831 for (node
= cgraph_nodes
; node
; node
= node
->next
)
833 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
835 fprintf (f
, "%s -> %s ", cgraph_node_name (cs
->caller
),
836 cgraph_node_name (cs
->callee
));
837 fprintf (f
, "count is " HOST_WIDE_INT_PRINT_DEC
" \n",
838 (HOST_WIDE_INT
) cs
->count
);
843 /* Print profile info for all functions. */
845 ipcp_print_profile_data (FILE * f
)
847 fprintf (f
, "\nNODE COUNTS :\n");
848 ipcp_print_func_profile_counts (f
);
849 fprintf (f
, "\nCS COUNTS stage:\n");
850 ipcp_print_call_profile_counts (f
);
853 /* Build and initialize ipa_replace_map struct according to LAT. This struct is
854 processed by versioning, which operates according to the flags set.
855 PARM_TREE is the formal parameter found to be constant. LAT represents the
857 static struct ipa_replace_map
*
858 ipcp_create_replace_map (tree parm_tree
, struct ipcp_lattice
*lat
)
860 struct ipa_replace_map
*replace_map
;
863 replace_map
= GGC_NEW (struct ipa_replace_map
);
864 const_val
= build_const_val (lat
, TREE_TYPE (parm_tree
));
867 fprintf (dump_file
, " replacing param ");
868 print_generic_expr (dump_file
, parm_tree
, 0);
869 fprintf (dump_file
, " with const ");
870 print_generic_expr (dump_file
, const_val
, 0);
871 fprintf (dump_file
, "\n");
873 replace_map
->old_tree
= parm_tree
;
874 replace_map
->new_tree
= const_val
;
875 replace_map
->replace_p
= true;
876 replace_map
->ref_p
= false;
881 /* Return true if this callsite should be redirected to the original callee
882 (instead of the cloned one). */
884 ipcp_need_redirect_p (struct cgraph_edge
*cs
)
886 struct ipa_node_params
*orig_callee_info
;
888 struct ipa_jump_func
*jump_func
;
889 struct cgraph_node
*node
= cs
->callee
, *orig
;
891 if (!n_cloning_candidates
)
894 if ((orig
= ipcp_get_orig_node (node
)) != NULL
)
896 if (ipcp_get_orig_node (cs
->caller
))
899 orig_callee_info
= IPA_NODE_REF (node
);
900 count
= ipa_get_param_count (orig_callee_info
);
901 for (i
= 0; i
< count
; i
++)
903 struct ipcp_lattice
*lat
= ipcp_get_lattice (orig_callee_info
, i
);
904 if (ipcp_lat_is_const (lat
))
906 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
907 if (jump_func
->type
!= IPA_JF_CONST
)
915 /* Fix the callsites and the call graph after function cloning was done. */
917 ipcp_update_callgraph (void)
919 struct cgraph_node
*node
;
921 for (node
= cgraph_nodes
; node
; node
= node
->next
)
922 if (node
->analyzed
&& ipcp_node_is_clone (node
))
924 bitmap args_to_skip
= BITMAP_ALLOC (NULL
);
925 struct cgraph_node
*orig_node
= ipcp_get_orig_node (node
);
926 struct ipa_node_params
*info
= IPA_NODE_REF (orig_node
);
927 int i
, count
= ipa_get_param_count (info
);
928 struct cgraph_edge
*cs
, *next
;
930 for (i
= 0; i
< count
; i
++)
932 struct ipcp_lattice
*lat
= ipcp_get_lattice (info
, i
);
933 tree parm_tree
= ipa_get_param (info
, i
);
935 /* We can proactively remove obviously unused arguments. */
936 if (is_gimple_reg (parm_tree
)
937 && !gimple_default_def (DECL_STRUCT_FUNCTION (orig_node
->decl
),
940 bitmap_set_bit (args_to_skip
, i
);
944 if (lat
->type
== IPA_CONST_VALUE
)
945 bitmap_set_bit (args_to_skip
, i
);
947 for (cs
= node
->callers
; cs
; cs
= next
)
949 next
= cs
->next_caller
;
950 if (!ipcp_node_is_clone (cs
->caller
) && ipcp_need_redirect_p (cs
))
951 cgraph_redirect_edge_callee (cs
, orig_node
);
956 /* Update profiling info for versioned functions and the functions they were
959 ipcp_update_profiling (void)
961 struct cgraph_node
*node
, *orig_node
;
962 gcov_type scale
, scale_complement
;
963 struct cgraph_edge
*cs
;
965 for (node
= cgraph_nodes
; node
; node
= node
->next
)
967 if (ipcp_node_is_clone (node
))
969 orig_node
= ipcp_get_orig_node (node
);
970 scale
= ipcp_get_node_scale (orig_node
);
971 node
->count
= orig_node
->count
* scale
/ REG_BR_PROB_BASE
;
972 scale_complement
= REG_BR_PROB_BASE
- scale
;
974 orig_node
->count
* scale_complement
/ REG_BR_PROB_BASE
;
975 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
976 cs
->count
= cs
->count
* scale
/ REG_BR_PROB_BASE
;
977 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
978 cs
->count
= cs
->count
* scale_complement
/ REG_BR_PROB_BASE
;
983 /* If NODE was cloned, how much would program grow? */
985 ipcp_estimate_growth (struct cgraph_node
*node
)
987 struct cgraph_edge
*cs
;
988 int redirectable_node_callers
= 0;
989 int removable_args
= 0;
990 bool need_original
= !cgraph_only_called_directly_p (node
);
991 struct ipa_node_params
*info
;
995 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
996 if (cs
->caller
== node
|| !ipcp_need_redirect_p (cs
))
997 redirectable_node_callers
++;
999 need_original
= true;
1001 /* If we will be able to fully replace orignal node, we never increase
1006 info
= IPA_NODE_REF (node
);
1007 count
= ipa_get_param_count (info
);
1008 for (i
= 0; i
< count
; i
++)
1010 struct ipcp_lattice
*lat
= ipcp_get_lattice (info
, i
);
1011 tree parm_tree
= ipa_get_param (info
, i
);
1013 /* We can proactively remove obviously unused arguments. */
1014 if (is_gimple_reg (parm_tree
)
1015 && !gimple_default_def (DECL_STRUCT_FUNCTION (node
->decl
),
1019 if (lat
->type
== IPA_CONST_VALUE
)
1023 /* We make just very simple estimate of savings for removal of operand from
1024 call site. Precise cost is dificult to get, as our size metric counts
1025 constants and moves as free. Generally we are looking for cases that
1026 small function is called very many times. */
1027 growth
= node
->local
.inline_summary
.self_size
1028 - removable_args
* redirectable_node_callers
;
1035 /* Estimate cost of cloning NODE. */
1037 ipcp_estimate_cloning_cost (struct cgraph_node
*node
)
1040 gcov_type count_sum
= 1;
1041 struct cgraph_edge
*e
;
1044 cost
= ipcp_estimate_growth (node
) * 1000;
1048 fprintf (dump_file
, "Versioning of %s will save code size\n",
1049 cgraph_node_name (node
));
1053 for (e
= node
->callers
; e
; e
= e
->next_caller
)
1054 if (!bitmap_bit_p (dead_nodes
, e
->caller
->uid
)
1055 && !ipcp_need_redirect_p (e
))
1057 count_sum
+= e
->count
;
1058 freq_sum
+= e
->frequency
+ 1;
1062 cost
/= count_sum
* 1000 / max_count
+ 1;
1064 cost
/= freq_sum
* 1000 / REG_BR_PROB_BASE
+ 1;
1066 fprintf (dump_file
, "Cost of versioning %s is %i, (size: %i, freq: %i)\n",
1067 cgraph_node_name (node
), cost
, node
->local
.inline_summary
.self_size
,
1072 /* Return number of live constant parameters. */
1074 ipcp_const_param_count (struct cgraph_node
*node
)
1076 int const_param
= 0;
1077 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
1078 int count
= ipa_get_param_count (info
);
1081 for (i
= 0; i
< count
; i
++)
1083 struct ipcp_lattice
*lat
= ipcp_get_lattice (info
, i
);
1084 tree parm_tree
= ipa_get_param (info
, i
);
1085 if (ipcp_lat_is_insertable (lat
)
1086 /* Do not count obviously unused arguments. */
1087 && (!is_gimple_reg (parm_tree
)
1088 || gimple_default_def (DECL_STRUCT_FUNCTION (node
->decl
),
1095 /* Propagate the constant parameters found by ipcp_iterate_stage()
1096 to the function's code. */
1098 ipcp_insert_stage (void)
1100 struct cgraph_node
*node
, *node1
= NULL
;
1102 VEC (cgraph_edge_p
, heap
) * redirect_callers
;
1103 VEC (ipa_replace_map_p
,gc
)* replace_trees
;
1104 int node_callers
, count
;
1106 struct ipa_replace_map
*replace_param
;
1108 long overall_size
= 0, new_size
= 0;
1111 ipa_check_create_node_params ();
1112 ipa_check_create_edge_args ();
1114 fprintf (dump_file
, "\nIPA insert stage:\n\n");
1116 dead_nodes
= BITMAP_ALLOC (NULL
);
1118 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1121 if (node
->count
> max_count
)
1122 max_count
= node
->count
;
1123 overall_size
+= node
->local
.inline_summary
.self_size
;
1126 max_new_size
= overall_size
;
1127 if (max_new_size
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
1128 max_new_size
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
1129 max_new_size
= max_new_size
* PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH
) / 100 + 1;
1131 /* First collect all functions we proved to have constant arguments to heap. */
1132 heap
= fibheap_new ();
1133 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1135 struct ipa_node_params
*info
;
1136 /* Propagation of the constant is forbidden in certain conditions. */
1137 if (!node
->analyzed
|| !ipcp_node_modifiable_p (node
))
1139 info
= IPA_NODE_REF (node
);
1140 if (ipa_is_called_with_var_arguments (info
))
1142 if (ipcp_const_param_count (node
))
1143 node
->aux
= fibheap_insert (heap
, ipcp_estimate_cloning_cost (node
), node
);
1146 /* Now clone in priority order until code size growth limits are met or
1148 while (!fibheap_empty (heap
))
1150 struct ipa_node_params
*info
;
1152 bitmap args_to_skip
;
1153 struct cgraph_edge
*cs
;
1155 node
= (struct cgraph_node
*)fibheap_extract_min (heap
);
1158 fprintf (dump_file
, "considering function %s\n",
1159 cgraph_node_name (node
));
1161 growth
= ipcp_estimate_growth (node
);
1163 if (new_size
+ growth
> max_new_size
)
1166 && optimize_function_for_size_p (DECL_STRUCT_FUNCTION (node
->decl
)))
1169 fprintf (dump_file
, "Not versioning, cold code would grow");
1175 /* Look if original function becomes dead after clonning. */
1176 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
1177 if (cs
->caller
== node
|| ipcp_need_redirect_p (cs
))
1179 if (!cs
&& cgraph_only_called_directly_p (node
))
1180 bitmap_set_bit (dead_nodes
, node
->uid
);
1182 info
= IPA_NODE_REF (node
);
1183 count
= ipa_get_param_count (info
);
1185 replace_trees
= VEC_alloc (ipa_replace_map_p
, gc
, 1);
1186 args_to_skip
= BITMAP_GGC_ALLOC ();
1187 for (i
= 0; i
< count
; i
++)
1189 struct ipcp_lattice
*lat
= ipcp_get_lattice (info
, i
);
1190 parm_tree
= ipa_get_param (info
, i
);
1192 /* We can proactively remove obviously unused arguments. */
1193 if (is_gimple_reg (parm_tree
)
1194 && !gimple_default_def (DECL_STRUCT_FUNCTION (node
->decl
),
1197 bitmap_set_bit (args_to_skip
, i
);
1201 if (lat
->type
== IPA_CONST_VALUE
)
1204 ipcp_create_replace_map (parm_tree
, lat
);
1205 VEC_safe_push (ipa_replace_map_p
, gc
, replace_trees
, replace_param
);
1206 bitmap_set_bit (args_to_skip
, i
);
1210 /* Compute how many callers node has. */
1212 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
1214 redirect_callers
= VEC_alloc (cgraph_edge_p
, heap
, node_callers
);
1215 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
1216 VEC_quick_push (cgraph_edge_p
, redirect_callers
, cs
);
1218 /* Redirecting all the callers of the node to the
1219 new versioned node. */
1221 cgraph_create_virtual_clone (node
, redirect_callers
, replace_trees
,
1223 args_to_skip
= NULL
;
1224 VEC_free (cgraph_edge_p
, heap
, redirect_callers
);
1225 replace_trees
= NULL
;
1230 fprintf (dump_file
, "versioned function %s with growth %i, overall %i\n",
1231 cgraph_node_name (node
), (int)growth
, (int)new_size
);
1232 ipcp_init_cloned_node (node
, node1
);
1234 /* TODO: We can use indirect inlning info to produce new calls. */
1237 dump_function_to_file (node1
->decl
, dump_file
, dump_flags
);
1239 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
1240 if (cs
->callee
->aux
)
1242 fibheap_delete_node (heap
, (fibnode_t
) cs
->callee
->aux
);
1243 cs
->callee
->aux
= fibheap_insert (heap
,
1244 ipcp_estimate_cloning_cost (cs
->callee
),
1249 while (!fibheap_empty (heap
))
1252 fprintf (dump_file
, "skipping function %s\n",
1253 cgraph_node_name (node
));
1254 node
= (struct cgraph_node
*) fibheap_extract_min (heap
);
1257 fibheap_delete (heap
);
1258 BITMAP_FREE (dead_nodes
);
1259 ipcp_update_callgraph ();
1260 ipcp_update_profiling ();
1263 /* The IPCP driver. */
1267 cgraph_remove_unreachable_nodes (true,dump_file
);
1270 fprintf (dump_file
, "\nIPA structures before propagation:\n");
1271 if (dump_flags
& TDF_DETAILS
)
1272 ipa_print_all_params (dump_file
);
1273 ipa_print_all_jump_functions (dump_file
);
1275 /* 2. Do the interprocedural propagation. */
1276 ipcp_iterate_stage ();
1277 /* 3. Insert the constants found to the functions. */
1278 ipcp_insert_stage ();
1279 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1281 fprintf (dump_file
, "\nProfiling info after insert stage:\n");
1282 ipcp_print_profile_data (dump_file
);
1284 /* Free all IPCP structures. */
1285 free_all_ipa_structures_after_ipa_cp ();
1287 fprintf (dump_file
, "\nIPA constant propagation end\n");
1291 /* Note function body size. */
1293 ipcp_generate_summary (void)
1296 fprintf (dump_file
, "\nIPA constant propagation start:\n");
1297 ipa_check_create_node_params ();
1298 ipa_check_create_edge_args ();
1299 ipa_register_cgraph_hooks ();
1300 /* 1. Call the init stage to initialize
1301 the ipa_node_params and ipa_edge_args structures. */
1305 /* Write ipcp summary for nodes in SET. */
1307 ipcp_write_summary (cgraph_node_set set
)
1309 ipa_prop_write_jump_functions (set
);
1312 /* Read ipcp summary. */
1314 ipcp_read_summary (void)
1316 ipa_prop_read_jump_functions ();
1319 /* Gate for IPCP optimization. */
1321 cgraph_gate_cp (void)
1326 struct ipa_opt_pass_d pass_ipa_cp
=
1331 cgraph_gate_cp
, /* gate */
1332 ipcp_driver
, /* execute */
1335 0, /* static_pass_number */
1336 TV_IPA_CONSTANT_PROP
, /* tv_id */
1337 0, /* properties_required */
1338 0, /* properties_provided */
1339 0, /* properties_destroyed */
1340 0, /* todo_flags_start */
1341 TODO_dump_cgraph
| TODO_dump_func
|
1342 TODO_remove_functions
/* todo_flags_finish */
1344 ipcp_generate_summary
, /* generate_summary */
1345 ipcp_write_summary
, /* write_summary */
1346 ipcp_read_summary
, /* read_summary */
1347 NULL
, /* function_read_summary */
1348 lto_ipa_fixup_call_notes
, /* stmt_fixup */
1350 NULL
, /* function_transform */
1351 NULL
, /* variable_transform */