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"
136 /* Get the original node field of ipa_node_params associated with node NODE. */
137 static inline struct cgraph_node
*
138 ipcp_get_orig_node (struct cgraph_node
*node
)
140 return IPA_NODE_REF (node
)->ipcp_orig_node
;
143 /* Return true if NODE describes a cloned/versioned function. */
145 ipcp_node_is_clone (struct cgraph_node
*node
)
147 return (ipcp_get_orig_node (node
) != NULL
);
150 /* Create ipa_node_params and its data structures for NEW_NODE. Set ORIG_NODE
151 as the ipcp_orig_node field in ipa_node_params. */
153 ipcp_init_cloned_node (struct cgraph_node
*orig_node
,
154 struct cgraph_node
*new_node
)
156 ipa_check_create_node_params ();
157 IPA_NODE_REF (new_node
)->ipcp_orig_node
= orig_node
;
158 ipa_count_formal_params (new_node
);
159 ipa_create_param_decls_array (new_node
);
162 /* Recompute all local information since node might've got new
163 direct calls after clonning. */
165 ipcp_update_cloned_node (struct cgraph_node
*new_node
)
167 /* We might've introduced new direct calls. */
168 push_cfun (DECL_STRUCT_FUNCTION (new_node
->decl
));
169 current_function_decl
= new_node
->decl
;
170 rebuild_cgraph_edges ();
172 if (flag_indirect_inlining
)
174 struct cgraph_edge
*cs
;
176 ipa_check_create_node_params ();
177 ipa_count_formal_params (new_node
);
178 ipa_create_param_decls_array (new_node
);
179 ipa_detect_param_modifications (new_node
);
180 ipa_analyze_params_uses (new_node
);
182 for (cs
= new_node
->callees
; cs
; cs
= cs
->next_callee
)
184 ipa_count_arguments (cs
);
185 ipa_compute_jump_functions (cs
);
189 current_function_decl
= NULL
;
192 /* Return scale for NODE. */
193 static inline gcov_type
194 ipcp_get_node_scale (struct cgraph_node
*node
)
196 return IPA_NODE_REF (node
)->count_scale
;
199 /* Set COUNT as scale for NODE. */
201 ipcp_set_node_scale (struct cgraph_node
*node
, gcov_type count
)
203 IPA_NODE_REF (node
)->count_scale
= count
;
206 /* Return whether LAT is a constant lattice. */
208 ipcp_lat_is_const (struct ipcp_lattice
*lat
)
210 if (lat
->type
== IPA_CONST_VALUE
)
216 /* Return whether LAT is a constant lattice that ipa-cp can actually insert
217 into the code (i.e. constants excluding member pointers and pointers). */
219 ipcp_lat_is_insertable (struct ipcp_lattice
*lat
)
221 return lat
->type
== IPA_CONST_VALUE
;
224 /* Return true if LAT1 and LAT2 are equal. */
226 ipcp_lats_are_equal (struct ipcp_lattice
*lat1
, struct ipcp_lattice
*lat2
)
228 gcc_assert (ipcp_lat_is_const (lat1
) && ipcp_lat_is_const (lat2
));
229 if (lat1
->type
!= lat2
->type
)
232 if (operand_equal_p (lat1
->constant
, lat2
->constant
, 0))
238 /* Compute Meet arithmetics:
239 Meet (IPA_BOTTOM, x) = IPA_BOTTOM
241 Meet (const_a,const_b) = IPA_BOTTOM, if const_a != const_b.
242 MEET (const_a,const_b) = const_a, if const_a == const_b.*/
244 ipa_lattice_meet (struct ipcp_lattice
*res
, struct ipcp_lattice
*lat1
,
245 struct ipcp_lattice
*lat2
)
247 if (lat1
->type
== IPA_BOTTOM
|| lat2
->type
== IPA_BOTTOM
)
249 res
->type
= IPA_BOTTOM
;
252 if (lat1
->type
== IPA_TOP
)
254 res
->type
= lat2
->type
;
255 res
->constant
= lat2
->constant
;
258 if (lat2
->type
== IPA_TOP
)
260 res
->type
= lat1
->type
;
261 res
->constant
= lat1
->constant
;
264 if (!ipcp_lats_are_equal (lat1
, lat2
))
266 res
->type
= IPA_BOTTOM
;
269 res
->type
= lat1
->type
;
270 res
->constant
= lat1
->constant
;
273 /* Return the lattice corresponding to the Ith formal parameter of the function
274 described by INFO. */
275 static inline struct ipcp_lattice
*
276 ipcp_get_ith_lattice (struct ipa_node_params
*info
, int i
)
278 return &(info
->ipcp_lattices
[i
]);
281 /* Given the jump function JFUNC, compute the lattice LAT that describes the
282 value coming down the callsite. INFO describes the caller node so that
283 pass-through jump functions can be evaluated. */
285 ipcp_lattice_from_jfunc (struct ipa_node_params
*info
, struct ipcp_lattice
*lat
,
286 struct ipa_jump_func
*jfunc
)
288 if (jfunc
->type
== IPA_CONST
)
290 lat
->type
= IPA_CONST_VALUE
;
291 lat
->constant
= jfunc
->value
.constant
;
293 else if (jfunc
->type
== IPA_PASS_THROUGH
)
295 struct ipcp_lattice
*caller_lat
;
297 caller_lat
= ipcp_get_ith_lattice (info
, jfunc
->value
.formal_id
);
298 lat
->type
= caller_lat
->type
;
299 lat
->constant
= caller_lat
->constant
;
302 lat
->type
= IPA_BOTTOM
;
305 /* True when OLD_LAT and NEW_LAT values are not the same. */
308 ipcp_lattice_changed (struct ipcp_lattice
*old_lat
,
309 struct ipcp_lattice
*new_lat
)
311 if (old_lat
->type
== new_lat
->type
)
313 if (!ipcp_lat_is_const (old_lat
))
315 if (ipcp_lats_are_equal (old_lat
, new_lat
))
321 /* Print all ipcp_lattices of all functions to F. */
323 ipcp_print_all_lattices (FILE * f
)
325 struct cgraph_node
*node
;
328 fprintf (f
, "\nLATTICE PRINT\n");
329 for (node
= cgraph_nodes
; node
; node
= node
->next
)
331 struct ipa_node_params
*info
;
335 info
= IPA_NODE_REF (node
);
336 fprintf (f
, "Printing lattices %s:\n", cgraph_node_name (node
));
337 count
= ipa_get_param_count (info
);
338 for (i
= 0; i
< count
; i
++)
340 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
342 fprintf (f
, " param [%d]: ", i
);
343 if (lat
->type
== IPA_CONST_VALUE
)
345 fprintf (f
, "type is CONST ");
346 print_generic_expr (f
, lat
->constant
, 0);
349 else if (lat
->type
== IPA_TOP
)
350 fprintf (f
, "type is TOP\n");
352 fprintf (f
, "type is BOTTOM\n");
357 /* Initialize ipcp_lattices array. The lattices corresponding to supported
358 types (integers, real types and Fortran constants defined as const_decls)
359 are initialized to IPA_TOP, the rest of them to IPA_BOTTOM. */
361 ipcp_initialize_node_lattices (struct cgraph_node
*node
)
364 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
366 info
->ipcp_lattices
= XCNEWVEC (struct ipcp_lattice
,
367 ipa_get_param_count (info
));
368 for (i
= 0; i
< ipa_get_param_count (info
) ; i
++)
369 ipcp_get_ith_lattice (info
, i
)->type
= IPA_TOP
;
372 /* Create a new assignment statement and make it the first statement in the
373 function. PARM1 is the lhs of the assignment and VAL is the rhs. */
375 constant_val_insert (tree parm1 ATTRIBUTE_UNUSED
, tree val ATTRIBUTE_UNUSED
)
377 gimple init_stmt
= NULL
;
380 init_stmt
= gimple_build_assign (parm1
, val
);
381 gcc_assert (init_stmt
);
382 e_step
= single_succ_edge (ENTRY_BLOCK_PTR_FOR_FUNCTION (cfun
));
383 gsi_insert_on_edge_immediate (e_step
, init_stmt
);
386 /* build INTEGER_CST tree with type TREE_TYPE and value according to LAT.
389 build_const_val (struct ipcp_lattice
*lat
, tree tree_type
)
393 gcc_assert (ipcp_lat_is_const (lat
));
396 if (!useless_type_conversion_p (tree_type
, TREE_TYPE (val
)))
398 if (fold_convertible_p (tree_type
, val
))
399 return fold_build1 (NOP_EXPR
, tree_type
, val
);
401 return fold_build1 (VIEW_CONVERT_EXPR
, tree_type
, val
);
406 /* Build the tree representing the constant and call constant_val_insert(). */
408 ipcp_propagate_one_const (struct cgraph_node
*node
, int param
,
409 struct ipcp_lattice
*lat
)
415 fprintf (dump_file
, "propagating const to %s\n", cgraph_node_name (node
));
416 parm_tree
= ipa_get_ith_param (IPA_NODE_REF (node
), param
);
417 const_val
= build_const_val (lat
, TREE_TYPE (parm_tree
));
418 constant_val_insert (parm_tree
, const_val
);
421 /* Compute the proper scale for NODE. It is the ratio between the number of
422 direct calls (represented on the incoming cgraph_edges) and sum of all
423 invocations of NODE (represented as count in cgraph_node). */
425 ipcp_compute_node_scale (struct cgraph_node
*node
)
428 struct cgraph_edge
*cs
;
431 /* Compute sum of all counts of callers. */
432 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
434 if (node
->count
== 0)
435 ipcp_set_node_scale (node
, 0);
437 ipcp_set_node_scale (node
, sum
* REG_BR_PROB_BASE
/ node
->count
);
440 /* Initialization and computation of IPCP data structures. This is the initial
441 intraprocedural analysis of functions, which gathers information to be
442 propagated later on. */
444 ipcp_init_stage (void)
446 struct cgraph_node
*node
;
447 struct cgraph_edge
*cs
;
449 for (node
= cgraph_nodes
; node
; node
= node
->next
)
453 /* Unreachable nodes should have been eliminated before ipcp. */
454 gcc_assert (node
->needed
|| node
->reachable
);
456 ipa_count_formal_params (node
);
457 ipa_create_param_decls_array (node
);
458 ipcp_initialize_node_lattices (node
);
459 ipa_detect_param_modifications (node
);
460 ipcp_compute_node_scale (node
);
462 for (node
= cgraph_nodes
; node
; node
= node
->next
)
466 /* building jump functions */
467 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
469 if (!cs
->callee
->analyzed
)
471 ipa_count_arguments (cs
);
472 if (ipa_get_cs_argument_count (IPA_EDGE_REF (cs
))
473 != ipa_get_param_count (IPA_NODE_REF (cs
->callee
)))
475 /* Handle cases of functions with
476 a variable number of parameters. */
477 ipa_set_called_with_variable_arg (IPA_NODE_REF (cs
->callee
));
478 if (flag_indirect_inlining
)
479 ipa_compute_jump_functions (cs
);
482 ipa_compute_jump_functions (cs
);
487 /* Return true if there are some formal parameters whose value is IPA_TOP (in
488 the whole compilation unit). Change their values to IPA_BOTTOM, since they
489 most probably get their values from outside of this compilation unit. */
491 ipcp_change_tops_to_bottom (void)
494 struct cgraph_node
*node
;
498 for (node
= cgraph_nodes
; node
; node
= node
->next
)
500 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
501 count
= ipa_get_param_count (info
);
502 for (i
= 0; i
< count
; i
++)
504 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
505 if (lat
->type
== IPA_TOP
)
508 lat
->type
= IPA_BOTTOM
;
515 /* Interprocedural analysis. The algorithm propagates constants from the
516 caller's parameters to the callee's arguments. */
518 ipcp_propagate_stage (void)
521 struct ipcp_lattice inc_lat
= { IPA_BOTTOM
, NULL
};
522 struct ipcp_lattice new_lat
= { IPA_BOTTOM
, NULL
};
523 struct ipcp_lattice
*dest_lat
;
524 struct cgraph_edge
*cs
;
525 struct ipa_jump_func
*jump_func
;
526 struct ipa_func_list
*wl
;
529 ipa_check_create_node_params ();
530 ipa_check_create_edge_args ();
531 /* Initialize worklist to contain all functions. */
532 wl
= ipa_init_func_list ();
535 struct cgraph_node
*node
= ipa_pop_func_from_list (&wl
);
536 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
538 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
540 struct ipa_node_params
*callee_info
= IPA_NODE_REF (cs
->callee
);
541 struct ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
543 if (ipa_is_called_with_var_arguments (callee_info
))
546 count
= ipa_get_cs_argument_count (args
);
547 for (i
= 0; i
< count
; i
++)
549 jump_func
= ipa_get_ith_jump_func (args
, i
);
550 ipcp_lattice_from_jfunc (info
, &inc_lat
, jump_func
);
551 dest_lat
= ipcp_get_ith_lattice (callee_info
, i
);
552 ipa_lattice_meet (&new_lat
, &inc_lat
, dest_lat
);
553 if (ipcp_lattice_changed (&new_lat
, dest_lat
))
555 dest_lat
->type
= new_lat
.type
;
556 dest_lat
->constant
= new_lat
.constant
;
557 ipa_push_func_to_list (&wl
, cs
->callee
);
564 /* Call the constant propagation algorithm and re-call it if necessary
565 (if there are undetermined values left). */
567 ipcp_iterate_stage (void)
569 ipcp_propagate_stage ();
570 if (ipcp_change_tops_to_bottom ())
571 /* Some lattices have changed from IPA_TOP to IPA_BOTTOM.
572 This change should be propagated. */
573 ipcp_propagate_stage ();
576 /* Check conditions to forbid constant insertion to function described by
579 ipcp_node_not_modifiable_p (struct cgraph_node
*node
)
581 /* ??? Handle pending sizes case. */
582 if (DECL_UNINLINABLE (node
->decl
))
587 /* Print count scale data structures. */
589 ipcp_function_scale_print (FILE * f
)
591 struct cgraph_node
*node
;
593 for (node
= cgraph_nodes
; node
; node
= node
->next
)
597 fprintf (f
, "printing scale for %s: ", cgraph_node_name (node
));
598 fprintf (f
, "value is " HOST_WIDE_INT_PRINT_DEC
599 " \n", (HOST_WIDE_INT
) ipcp_get_node_scale (node
));
603 /* Print counts of all cgraph nodes. */
605 ipcp_print_func_profile_counts (FILE * f
)
607 struct cgraph_node
*node
;
609 for (node
= cgraph_nodes
; node
; node
= node
->next
)
611 fprintf (f
, "function %s: ", cgraph_node_name (node
));
612 fprintf (f
, "count is " HOST_WIDE_INT_PRINT_DEC
613 " \n", (HOST_WIDE_INT
) node
->count
);
617 /* Print counts of all cgraph edges. */
619 ipcp_print_call_profile_counts (FILE * f
)
621 struct cgraph_node
*node
;
622 struct cgraph_edge
*cs
;
624 for (node
= cgraph_nodes
; node
; node
= node
->next
)
626 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
628 fprintf (f
, "%s -> %s ", cgraph_node_name (cs
->caller
),
629 cgraph_node_name (cs
->callee
));
630 fprintf (f
, "count is " HOST_WIDE_INT_PRINT_DEC
" \n",
631 (HOST_WIDE_INT
) cs
->count
);
636 /* Print all counts and probabilities of cfg edges of all functions. */
638 ipcp_print_edge_profiles (FILE * f
)
640 struct cgraph_node
*node
;
645 for (node
= cgraph_nodes
; node
; node
= node
->next
)
647 fprintf (f
, "function %s: \n", cgraph_node_name (node
));
651 ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node
->decl
));
652 fprintf (f
, "ENTRY: ");
653 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
654 " %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 ENTRY -> EXIT, Count");
664 fprintf (f
, "edge ENTRY -> %d, Count", e
->dest
->index
);
665 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
666 " Prob %d\n", (HOST_WIDE_INT
) e
->count
,
669 FOR_EACH_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
671 fprintf (f
, "bb[%d]: ", bb
->index
);
672 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
673 " %d\n", (HOST_WIDE_INT
) bb
->count
, bb
->frequency
);
674 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
677 EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
679 fprintf (f
, "edge %d -> EXIT, Count", e
->src
->index
);
681 fprintf (f
, "edge %d -> %d, Count", e
->src
->index
,
683 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
" Prob %d\n",
684 (HOST_WIDE_INT
) e
->count
, e
->probability
);
691 /* Print counts and frequencies for all basic blocks of all functions. */
693 ipcp_print_bb_profiles (FILE * f
)
696 struct cgraph_node
*node
;
698 for (node
= cgraph_nodes
; node
; node
= node
->next
)
700 fprintf (f
, "function %s: \n", cgraph_node_name (node
));
704 ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node
->decl
));
705 fprintf (f
, "ENTRY: Count");
706 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
707 " Frequency %d\n", (HOST_WIDE_INT
) bb
->count
,
710 FOR_EACH_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
712 fprintf (f
, "bb[%d]: Count", bb
->index
);
713 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
714 " Frequency %d\n", (HOST_WIDE_INT
) bb
->count
,
718 EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node
->decl
));
719 fprintf (f
, "EXIT: Count");
720 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
721 " Frequency %d\n", (HOST_WIDE_INT
) bb
->count
,
728 /* Print all IPCP data structures to F. */
730 ipcp_print_all_structures (FILE * f
)
732 ipcp_print_all_lattices (f
);
733 ipcp_function_scale_print (f
);
734 ipa_print_all_tree_maps (f
);
735 ipa_print_all_param_flags (f
);
736 ipa_print_all_jump_functions (f
);
739 /* Print profile info for all functions. */
741 ipcp_print_profile_data (FILE * f
)
743 fprintf (f
, "\nNODE COUNTS :\n");
744 ipcp_print_func_profile_counts (f
);
745 fprintf (f
, "\nCS COUNTS stage:\n");
746 ipcp_print_call_profile_counts (f
);
747 fprintf (f
, "\nBB COUNTS and FREQUENCIES :\n");
748 ipcp_print_bb_profiles (f
);
749 fprintf (f
, "\nCFG EDGES COUNTS and PROBABILITIES :\n");
750 ipcp_print_edge_profiles (f
);
753 /* Build and initialize ipa_replace_map struct according to LAT. This struct is
754 processed by versioning, which operates according to the flags set.
755 PARM_TREE is the formal parameter found to be constant. LAT represents the
757 static struct ipa_replace_map
*
758 ipcp_create_replace_map (struct function
*func
, tree parm_tree
,
759 struct ipcp_lattice
*lat
)
761 struct ipa_replace_map
*replace_map
;
764 replace_map
= XCNEW (struct ipa_replace_map
);
765 if (is_gimple_reg (parm_tree
)
766 && gimple_default_def (func
, parm_tree
)
767 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_default_def (func
,
771 fprintf (dump_file
, "replacing param with const\n");
772 const_val
= build_const_val (lat
, TREE_TYPE (parm_tree
));
773 replace_map
->old_tree
=gimple_default_def (func
, parm_tree
);
774 replace_map
->new_tree
= const_val
;
775 replace_map
->replace_p
= true;
776 replace_map
->ref_p
= false;
780 replace_map
->old_tree
= NULL
;
781 replace_map
->new_tree
= NULL
;
782 replace_map
->replace_p
= false;
783 replace_map
->ref_p
= false;
789 /* Return true if this callsite should be redirected to the original callee
790 (instead of the cloned one). */
792 ipcp_need_redirect_p (struct cgraph_edge
*cs
)
794 struct ipa_node_params
*orig_callee_info
;
796 struct ipa_jump_func
*jump_func
;
798 orig_callee_info
= IPA_NODE_REF (ipcp_get_orig_node (cs
->callee
));
799 count
= ipa_get_param_count (orig_callee_info
);
800 for (i
= 0; i
< count
; i
++)
802 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (orig_callee_info
, i
);
803 if (ipcp_lat_is_const (lat
))
805 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
806 if (jump_func
->type
!= IPA_CONST
)
814 /* Fix the callsites and the call graph after function cloning was done. */
816 ipcp_update_callgraph (void)
818 struct cgraph_node
*node
, *orig_callee
;
819 struct cgraph_edge
*cs
;
821 for (node
= cgraph_nodes
; node
; node
= node
->next
)
823 /* want to fix only original nodes */
824 if (!node
->analyzed
|| ipcp_node_is_clone (node
))
826 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
827 if (ipcp_node_is_clone (cs
->callee
))
829 /* Callee is a cloned node */
830 orig_callee
= ipcp_get_orig_node (cs
->callee
);
831 if (ipcp_need_redirect_p (cs
))
833 cgraph_redirect_edge_callee (cs
, orig_callee
);
834 gimple_call_set_fndecl (cs
->call_stmt
, orig_callee
->decl
);
840 /* Update all cfg basic blocks in NODE according to SCALE. */
842 ipcp_update_bb_counts (struct cgraph_node
*node
, gcov_type scale
)
846 FOR_ALL_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
847 bb
->count
= bb
->count
* scale
/ REG_BR_PROB_BASE
;
850 /* Update all cfg edges in NODE according to SCALE. */
852 ipcp_update_edges_counts (struct cgraph_node
*node
, gcov_type scale
)
858 FOR_ALL_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
859 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
860 e
->count
= e
->count
* scale
/ REG_BR_PROB_BASE
;
863 /* Update profiling info for versioned functions and the functions they were
866 ipcp_update_profiling (void)
868 struct cgraph_node
*node
, *orig_node
;
869 gcov_type scale
, scale_complement
;
870 struct cgraph_edge
*cs
;
872 for (node
= cgraph_nodes
; node
; node
= node
->next
)
874 if (ipcp_node_is_clone (node
))
876 orig_node
= ipcp_get_orig_node (node
);
877 scale
= ipcp_get_node_scale (orig_node
);
878 node
->count
= orig_node
->count
* scale
/ REG_BR_PROB_BASE
;
879 scale_complement
= REG_BR_PROB_BASE
- scale
;
881 orig_node
->count
* scale_complement
/ REG_BR_PROB_BASE
;
882 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
883 cs
->count
= cs
->count
* scale
/ REG_BR_PROB_BASE
;
884 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
885 cs
->count
= cs
->count
* scale_complement
/ REG_BR_PROB_BASE
;
886 ipcp_update_bb_counts (node
, scale
);
887 ipcp_update_bb_counts (orig_node
, scale_complement
);
888 ipcp_update_edges_counts (node
, scale
);
889 ipcp_update_edges_counts (orig_node
, scale_complement
);
894 /* Propagate the constant parameters found by ipcp_iterate_stage()
895 to the function's code. */
897 ipcp_insert_stage (void)
899 struct cgraph_node
*node
, *node1
= NULL
;
901 VEC (cgraph_edge_p
, heap
) * redirect_callers
;
902 varray_type replace_trees
;
903 struct cgraph_edge
*cs
;
904 int node_callers
, count
;
906 struct ipa_replace_map
*replace_param
;
908 ipa_check_create_node_params ();
909 ipa_check_create_edge_args ();
911 for (node
= cgraph_nodes
; node
; node
= node
->next
)
913 struct ipa_node_params
*info
;
914 /* Propagation of the constant is forbidden in certain conditions. */
915 if (!node
->analyzed
|| ipcp_node_not_modifiable_p (node
))
917 info
= IPA_NODE_REF (node
);
918 if (ipa_is_called_with_var_arguments (info
))
921 count
= ipa_get_param_count (info
);
922 for (i
= 0; i
< count
; i
++)
924 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
925 tree parm_tree
= ipa_get_ith_param (info
, i
);
926 if (ipcp_lat_is_insertable (lat
)
927 /* Do not count obviously unused arguments. */
928 && (!is_gimple_reg (parm_tree
)
929 || gimple_default_def (DECL_STRUCT_FUNCTION (node
->decl
), parm_tree
)))
932 if (const_param
== 0)
934 VARRAY_GENERIC_PTR_INIT (replace_trees
, const_param
, "replace_trees");
935 for (i
= 0; i
< count
; i
++)
937 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
938 if (lat
->type
== IPA_CONST_VALUE
)
940 parm_tree
= ipa_get_ith_param (info
, i
);
942 ipcp_create_replace_map (DECL_STRUCT_FUNCTION (node
->decl
),
944 VARRAY_PUSH_GENERIC_PTR (replace_trees
, replace_param
);
947 /* Compute how many callers node has. */
949 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
951 redirect_callers
= VEC_alloc (cgraph_edge_p
, heap
, node_callers
);
952 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
953 VEC_quick_push (cgraph_edge_p
, redirect_callers
, cs
);
954 /* Redirecting all the callers of the node to the
955 new versioned node. */
957 cgraph_function_versioning (node
, redirect_callers
, replace_trees
);
958 VEC_free (cgraph_edge_p
, heap
, redirect_callers
);
959 VARRAY_CLEAR (replace_trees
);
963 fprintf (dump_file
, "versioned function %s\n",
964 cgraph_node_name (node
));
965 ipcp_init_cloned_node (node
, node1
);
968 push_cfun (DECL_STRUCT_FUNCTION (node1
->decl
));
969 gimple_register_cfg_hooks ();
970 current_function_decl
= node1
->decl
;
972 for (i
= 0; i
< count
; i
++)
974 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
975 if (ipcp_lat_is_insertable (lat
))
977 parm_tree
= ipa_get_ith_param (info
, i
);
978 if (!is_gimple_reg (parm_tree
))
979 ipcp_propagate_one_const (node1
, i
, lat
);
982 if (gimple_in_ssa_p (cfun
))
984 update_ssa (TODO_update_ssa
);
985 #ifdef ENABLE_CHECKING
989 free_dominance_info (CDI_DOMINATORS
);
990 free_dominance_info (CDI_POST_DOMINATORS
);
992 current_function_decl
= NULL
;
993 /* We've possibly introduced direct calls. */
994 ipcp_update_cloned_node (node1
);
998 dump_function_to_file (node1
->decl
, dump_file
, dump_flags
);
1000 ipcp_update_callgraph ();
1001 ipcp_update_profiling ();
1004 /* The IPCP driver. */
1008 /* 2. Do the interprocedural propagation. */
1009 ipcp_iterate_stage ();
1012 fprintf (dump_file
, "\nIPA structures after propagation:\n");
1013 ipcp_print_all_structures (dump_file
);
1014 fprintf (dump_file
, "\nProfiling info before insert stage:\n");
1015 ipcp_print_profile_data (dump_file
);
1017 /* 3. Insert the constants found to the functions. */
1018 ipcp_insert_stage ();
1021 fprintf (dump_file
, "\nProfiling info after insert stage:\n");
1022 ipcp_print_profile_data (dump_file
);
1024 /* Free all IPCP structures. */
1025 free_all_ipa_structures_after_ipa_cp ();
1027 fprintf (dump_file
, "\nIPA constant propagation end\n");
1028 cgraph_remove_unreachable_nodes (true, NULL
);
1032 /* Note function body size. */
1034 ipcp_generate_summary (void)
1037 fprintf (dump_file
, "\nIPA constant propagation start:\n");
1038 ipa_check_create_node_params ();
1039 ipa_check_create_edge_args ();
1040 ipa_register_cgraph_hooks ();
1041 /* 1. Call the init stage to initialize
1042 the ipa_node_params and ipa_edge_args structures. */
1046 fprintf (dump_file
, "\nIPA structures before propagation:\n");
1047 ipcp_print_all_structures (dump_file
);
1051 /* Gate for IPCP optimization. */
1053 cgraph_gate_cp (void)
1058 struct ipa_opt_pass pass_ipa_cp
=
1063 cgraph_gate_cp
, /* gate */
1064 ipcp_driver
, /* execute */
1067 0, /* static_pass_number */
1068 TV_IPA_CONSTANT_PROP
, /* tv_id */
1069 0, /* properties_required */
1070 PROP_trees
, /* properties_provided */
1071 0, /* properties_destroyed */
1072 0, /* todo_flags_start */
1073 TODO_dump_cgraph
| TODO_dump_func
/* todo_flags_finish */
1075 ipcp_generate_summary
, /* generate_summary */
1076 NULL
, /* write_summary */
1077 NULL
, /* read_summary */
1078 NULL
, /* function_read_summary */
1080 NULL
, /* function_transform */
1081 NULL
, /* variable_transform */