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 /* Return scale for NODE. */
163 static inline gcov_type
164 ipcp_get_node_scale (struct cgraph_node
*node
)
166 return IPA_NODE_REF (node
)->count_scale
;
169 /* Set COUNT as scale for NODE. */
171 ipcp_set_node_scale (struct cgraph_node
*node
, gcov_type count
)
173 IPA_NODE_REF (node
)->count_scale
= count
;
176 /* Return whether LAT is a constant lattice. */
178 ipcp_lat_is_const (struct ipcp_lattice
*lat
)
180 if (lat
->type
== IPA_CONST_VALUE
|| lat
->type
== IPA_CONST_VALUE_REF
)
186 /* Return whether LAT is a constant lattice that ipa-cp can actually insert
187 into the code (i.e. constants excluding member pointers and pointers). */
189 ipcp_lat_is_insertable (struct ipcp_lattice
*lat
)
191 if ((lat
->type
== IPA_CONST_VALUE
|| lat
->type
== IPA_CONST_VALUE_REF
)
192 && !POINTER_TYPE_P (TREE_TYPE (lat
->constant
)))
198 /* Return true if LAT1 and LAT2 are equal. */
200 ipcp_lats_are_equal (struct ipcp_lattice
*lat1
, struct ipcp_lattice
*lat2
)
202 gcc_assert (ipcp_lat_is_const (lat1
) && ipcp_lat_is_const (lat2
));
203 if (lat1
->type
!= lat2
->type
)
206 if (operand_equal_p (lat1
->constant
, lat2
->constant
, 0))
212 /* Compute Meet arithmetics:
213 Meet (IPA_BOTTOM, x) = IPA_BOTTOM
215 Meet (const_a,const_b) = IPA_BOTTOM, if const_a != const_b.
216 MEET (const_a,const_b) = const_a, if const_a == const_b.*/
218 ipa_lattice_meet (struct ipcp_lattice
*res
, struct ipcp_lattice
*lat1
,
219 struct ipcp_lattice
*lat2
)
221 if (lat1
->type
== IPA_BOTTOM
|| lat2
->type
== IPA_BOTTOM
)
223 res
->type
= IPA_BOTTOM
;
226 if (lat1
->type
== IPA_TOP
)
228 res
->type
= lat2
->type
;
229 res
->constant
= lat2
->constant
;
232 if (lat2
->type
== IPA_TOP
)
234 res
->type
= lat1
->type
;
235 res
->constant
= lat1
->constant
;
238 if (!ipcp_lats_are_equal (lat1
, lat2
))
240 res
->type
= IPA_BOTTOM
;
243 res
->type
= lat1
->type
;
244 res
->constant
= lat1
->constant
;
247 /* Return the lattice corresponding to the Ith formal parameter of the function
248 described by INFO. */
249 static inline struct ipcp_lattice
*
250 ipcp_get_ith_lattice (struct ipa_node_params
*info
, int i
)
252 return &(info
->ipcp_lattices
[i
]);
255 /* Given the jump function JFUNC, compute the lattice LAT that describes the
256 value coming down the callsite. INFO describes the caller node so that
257 pass-through jump functions can be evaluated. */
259 ipcp_lattice_from_jfunc (struct ipa_node_params
*info
, struct ipcp_lattice
*lat
,
260 struct ipa_jump_func
*jfunc
)
262 if (jfunc
->type
== IPA_CONST
)
264 lat
->type
= IPA_CONST_VALUE
;
265 lat
->constant
= jfunc
->value
.constant
;
267 else if (jfunc
->type
== IPA_CONST_REF
)
269 lat
->type
= IPA_CONST_VALUE_REF
;
270 lat
->constant
= jfunc
->value
.constant
;
272 else if (jfunc
->type
== IPA_PASS_THROUGH
)
274 struct ipcp_lattice
*caller_lat
;
276 caller_lat
= ipcp_get_ith_lattice (info
, jfunc
->value
.formal_id
);
277 lat
->type
= caller_lat
->type
;
278 lat
->constant
= caller_lat
->constant
;
281 lat
->type
= IPA_BOTTOM
;
284 /* True when OLD and NEW values are not the same. */
286 ipcp_lattice_changed (struct ipcp_lattice
*old
, struct ipcp_lattice
*new)
288 if (old
->type
== new->type
)
290 if (!ipcp_lat_is_const (old
))
292 if (ipcp_lats_are_equal (old
, new))
298 /* Print all ipcp_lattices of all functions to F. */
300 ipcp_print_all_lattices (FILE * f
)
302 struct cgraph_node
*node
;
305 fprintf (f
, "\nLATTICE PRINT\n");
306 for (node
= cgraph_nodes
; node
; node
= node
->next
)
308 struct ipa_node_params
*info
;
312 info
= IPA_NODE_REF (node
);
313 fprintf (f
, "Printing lattices %s:\n", cgraph_node_name (node
));
314 count
= ipa_get_param_count (info
);
315 for (i
= 0; i
< count
; i
++)
317 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
319 fprintf (f
, " param [%d]: ", i
);
320 if (lat
->type
== IPA_CONST_VALUE
|| lat
->type
== IPA_CONST_VALUE_REF
)
322 fprintf (f
, "type is CONST ");
323 print_generic_expr (f
, lat
->constant
, 0);
326 else if (lat
->type
== IPA_TOP
)
327 fprintf (f
, "type is TOP\n");
329 fprintf (f
, "type is BOTTOM\n");
334 /* Initialize ipcp_lattices array. The lattices corresponding to supported
335 types (integers, real types and Fortran constants defined as const_decls)
336 are initialized to IPA_TOP, the rest of them to IPA_BOTTOM. */
338 ipcp_initialize_node_lattices (struct cgraph_node
*node
)
341 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
343 info
->ipcp_lattices
= XCNEWVEC (struct ipcp_lattice
,
344 ipa_get_param_count (info
));
345 for (i
= 0; i
< ipa_get_param_count (info
) ; i
++)
347 tree parm_tree
= ipa_get_ith_param (info
, i
);
348 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
350 if (INTEGRAL_TYPE_P (TREE_TYPE (parm_tree
))
351 || SCALAR_FLOAT_TYPE_P (TREE_TYPE (parm_tree
))
352 || POINTER_TYPE_P (TREE_TYPE (parm_tree
)))
355 lat
->type
= IPA_BOTTOM
;
359 /* Create a new assignment statement and make it the first statement in the
360 function. PARM1 is the lhs of the assignment and VAL is the rhs. */
362 constant_val_insert (tree parm1
, tree val
)
364 tree init_stmt
= NULL
;
367 init_stmt
= build_gimple_modify_stmt (parm1
, val
);
371 e_step
= single_succ_edge (ENTRY_BLOCK_PTR_FOR_FUNCTION (cfun
));
372 bsi_insert_on_edge_immediate (e_step
, init_stmt
);
376 /* build INTEGER_CST tree with type TREE_TYPE and value according to LAT.
379 build_const_val (struct ipcp_lattice
*lat
, tree tree_type
)
381 tree const_val
= NULL
;
383 gcc_assert (ipcp_lat_is_const (lat
));
384 const_val
= fold_convert (tree_type
, lat
->constant
);
388 /* Build the tree representing the constant and call constant_val_insert(). */
390 ipcp_propagate_one_const (struct cgraph_node
*node
, int param
,
391 struct ipcp_lattice
*lat
)
397 fprintf (dump_file
, "propagating const to %s\n", cgraph_node_name (node
));
398 parm_tree
= ipa_get_ith_param (IPA_NODE_REF (node
), param
);
399 const_val
= build_const_val (lat
, TREE_TYPE (parm_tree
));
400 constant_val_insert (parm_tree
, const_val
);
403 /* Compute the proper scale for NODE. It is the ratio between the number of
404 direct calls (represented on the incoming cgraph_edges) and sum of all
405 invocations of NODE (represented as count in cgraph_node). */
407 ipcp_compute_node_scale (struct cgraph_node
*node
)
410 struct cgraph_edge
*cs
;
413 /* Compute sum of all counts of callers. */
414 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
416 if (node
->count
== 0)
417 ipcp_set_node_scale (node
, 0);
419 ipcp_set_node_scale (node
, sum
* REG_BR_PROB_BASE
/ node
->count
);
422 /* Initialization and computation of IPCP data structures. This is the initial
423 intraprocedural analysis of functions, which gathers information to be
424 propagated later on. */
426 ipcp_init_stage (void)
428 struct cgraph_node
*node
;
429 struct cgraph_edge
*cs
;
431 for (node
= cgraph_nodes
; node
; node
= node
->next
)
435 /* Unreachable nodes should have been eliminated before ipcp. */
436 gcc_assert (node
->needed
|| node
->reachable
);
438 ipa_count_formal_params (node
);
439 ipa_create_param_decls_array (node
);
440 ipcp_initialize_node_lattices (node
);
441 ipa_detect_param_modifications (node
);
442 ipcp_compute_node_scale (node
);
444 for (node
= cgraph_nodes
; node
; node
= node
->next
)
448 /* building jump functions */
449 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
451 if (!cs
->callee
->analyzed
)
453 ipa_count_arguments (cs
);
454 if (ipa_get_cs_argument_count (IPA_EDGE_REF (cs
))
455 != ipa_get_param_count (IPA_NODE_REF (cs
->callee
)))
457 /* Handle cases of functions with
458 a variable number of parameters. */
459 ipa_set_called_with_variable_arg (IPA_NODE_REF (cs
->callee
));
462 ipa_compute_jump_functions (cs
);
467 /* Return true if there are some formal parameters whose value is IPA_TOP (in
468 the whole compilation unit). Change their values to IPA_BOTTOM, since they
469 most probably get their values from outside of this compilation unit. */
471 ipcp_change_tops_to_bottom (void)
474 struct cgraph_node
*node
;
478 for (node
= cgraph_nodes
; node
; node
= node
->next
)
480 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
481 count
= ipa_get_param_count (info
);
482 for (i
= 0; i
< count
; i
++)
484 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
485 if (lat
->type
== IPA_TOP
)
488 lat
->type
= IPA_BOTTOM
;
495 /* Interprocedural analysis. The algorithm propagates constants from the
496 caller's parameters to the callee's arguments. */
498 ipcp_propagate_stage (void)
501 struct ipcp_lattice inc_lat
= { IPA_BOTTOM
, NULL
};
502 struct ipcp_lattice new_lat
= { IPA_BOTTOM
, NULL
};
503 struct ipcp_lattice
*dest_lat
;
504 struct cgraph_edge
*cs
;
505 struct ipa_jump_func
*jump_func
;
506 struct ipa_func_list
*wl
;
509 ipa_check_create_node_params ();
510 ipa_check_create_edge_args ();
511 /* Initialize worklist to contain all functions. */
512 wl
= ipa_init_func_list ();
515 struct cgraph_node
*node
= ipa_pop_func_from_list (&wl
);
516 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
518 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
520 struct ipa_node_params
*callee_info
= IPA_NODE_REF (cs
->callee
);
521 struct ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
523 if (ipa_is_called_with_var_arguments (callee_info
))
526 count
= ipa_get_cs_argument_count (args
);
527 for (i
= 0; i
< count
; i
++)
529 jump_func
= ipa_get_ith_jump_func (args
, i
);
530 ipcp_lattice_from_jfunc (info
, &inc_lat
, jump_func
);
531 dest_lat
= ipcp_get_ith_lattice (callee_info
, i
);
532 ipa_lattice_meet (&new_lat
, &inc_lat
, dest_lat
);
533 if (ipcp_lattice_changed (&new_lat
, dest_lat
))
535 dest_lat
->type
= new_lat
.type
;
536 dest_lat
->constant
= new_lat
.constant
;
537 ipa_push_func_to_list (&wl
, cs
->callee
);
544 /* Call the constant propagation algorithm and re-call it if necessary
545 (if there are undetermined values left). */
547 ipcp_iterate_stage (void)
549 ipcp_propagate_stage ();
550 if (ipcp_change_tops_to_bottom ())
551 /* Some lattices have changed from IPA_TOP to IPA_BOTTOM.
552 This change should be propagated. */
553 ipcp_propagate_stage ();
556 /* Check conditions to forbid constant insertion to function described by
559 ipcp_node_not_modifiable_p (struct cgraph_node
*node
)
561 /* ??? Handle pending sizes case. */
562 if (DECL_UNINLINABLE (node
->decl
))
567 /* Print count scale data structures. */
569 ipcp_function_scale_print (FILE * f
)
571 struct cgraph_node
*node
;
573 for (node
= cgraph_nodes
; node
; node
= node
->next
)
577 fprintf (f
, "printing scale for %s: ", cgraph_node_name (node
));
578 fprintf (f
, "value is " HOST_WIDE_INT_PRINT_DEC
579 " \n", (HOST_WIDE_INT
) ipcp_get_node_scale (node
));
583 /* Print counts of all cgraph nodes. */
585 ipcp_print_func_profile_counts (FILE * f
)
587 struct cgraph_node
*node
;
589 for (node
= cgraph_nodes
; node
; node
= node
->next
)
591 fprintf (f
, "function %s: ", cgraph_node_name (node
));
592 fprintf (f
, "count is " HOST_WIDE_INT_PRINT_DEC
593 " \n", (HOST_WIDE_INT
) node
->count
);
597 /* Print counts of all cgraph edges. */
599 ipcp_print_call_profile_counts (FILE * f
)
601 struct cgraph_node
*node
;
602 struct cgraph_edge
*cs
;
604 for (node
= cgraph_nodes
; node
; node
= node
->next
)
606 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
608 fprintf (f
, "%s -> %s ", cgraph_node_name (cs
->caller
),
609 cgraph_node_name (cs
->callee
));
610 fprintf (f
, "count is " HOST_WIDE_INT_PRINT_DEC
" \n",
611 (HOST_WIDE_INT
) cs
->count
);
616 /* Print all counts and probabilities of cfg edges of all functions. */
618 ipcp_print_edge_profiles (FILE * f
)
620 struct cgraph_node
*node
;
625 for (node
= cgraph_nodes
; node
; node
= node
->next
)
627 fprintf (f
, "function %s: \n", cgraph_node_name (node
));
631 ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node
->decl
));
632 fprintf (f
, "ENTRY: ");
633 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
634 " %d\n", (HOST_WIDE_INT
) bb
->count
, bb
->frequency
);
637 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
640 EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
642 fprintf (f
, "edge ENTRY -> EXIT, Count");
644 fprintf (f
, "edge ENTRY -> %d, Count", e
->dest
->index
);
645 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
646 " Prob %d\n", (HOST_WIDE_INT
) e
->count
,
649 FOR_EACH_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
651 fprintf (f
, "bb[%d]: ", bb
->index
);
652 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
653 " %d\n", (HOST_WIDE_INT
) bb
->count
, bb
->frequency
);
654 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
657 EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
659 fprintf (f
, "edge %d -> EXIT, Count", e
->src
->index
);
661 fprintf (f
, "edge %d -> %d, Count", e
->src
->index
,
663 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
" Prob %d\n",
664 (HOST_WIDE_INT
) e
->count
, e
->probability
);
671 /* Print counts and frequencies for all basic blocks of all functions. */
673 ipcp_print_bb_profiles (FILE * f
)
676 struct cgraph_node
*node
;
678 for (node
= cgraph_nodes
; node
; node
= node
->next
)
680 fprintf (f
, "function %s: \n", cgraph_node_name (node
));
684 ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node
->decl
));
685 fprintf (f
, "ENTRY: Count");
686 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
687 " Frequency %d\n", (HOST_WIDE_INT
) bb
->count
,
690 FOR_EACH_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
692 fprintf (f
, "bb[%d]: Count", bb
->index
);
693 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
694 " Frequency %d\n", (HOST_WIDE_INT
) bb
->count
,
698 EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node
->decl
));
699 fprintf (f
, "EXIT: Count");
700 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
701 " Frequency %d\n", (HOST_WIDE_INT
) bb
->count
,
708 /* Print all IPCP data structures to F. */
710 ipcp_print_all_structures (FILE * f
)
712 ipcp_print_all_lattices (f
);
713 ipcp_function_scale_print (f
);
714 ipa_print_all_tree_maps (f
);
715 ipa_print_all_param_flags (f
);
716 ipa_print_all_jump_functions (f
);
719 /* Print profile info for all functions. */
721 ipcp_print_profile_data (FILE * f
)
723 fprintf (f
, "\nNODE COUNTS :\n");
724 ipcp_print_func_profile_counts (f
);
725 fprintf (f
, "\nCS COUNTS stage:\n");
726 ipcp_print_call_profile_counts (f
);
727 fprintf (f
, "\nBB COUNTS and FREQUENCIES :\n");
728 ipcp_print_bb_profiles (f
);
729 fprintf (f
, "\nCFG EDGES COUNTS and PROBABILITIES :\n");
730 ipcp_print_edge_profiles (f
);
733 /* Build and initialize ipa_replace_map struct according to LAT. This struct is
734 processed by versioning, which operates according to the flags set.
735 PARM_TREE is the formal parameter found to be constant. LAT represents the
737 static struct ipa_replace_map
*
738 ipcp_create_replace_map (struct function
*func
, tree parm_tree
,
739 struct ipcp_lattice
*lat
)
741 struct ipa_replace_map
*replace_map
;
744 replace_map
= XCNEW (struct ipa_replace_map
);
745 if (is_gimple_reg (parm_tree
) && gimple_default_def (func
, parm_tree
)
746 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_default_def (func
,
750 fprintf (dump_file
, "replacing param with const\n");
751 const_val
= build_const_val (lat
, TREE_TYPE (parm_tree
));
752 replace_map
->old_tree
=gimple_default_def (func
, parm_tree
);
753 replace_map
->new_tree
= const_val
;
754 replace_map
->replace_p
= true;
755 replace_map
->ref_p
= false;
759 replace_map
->old_tree
= NULL
;
760 replace_map
->new_tree
= NULL
;
761 replace_map
->replace_p
= false;
762 replace_map
->ref_p
= false;
768 /* Return true if this callsite should be redirected to the original callee
769 (instead of the cloned one). */
771 ipcp_need_redirect_p (struct cgraph_edge
*cs
)
773 struct ipa_node_params
*orig_callee_info
;
775 struct ipa_jump_func
*jump_func
;
777 orig_callee_info
= IPA_NODE_REF (ipcp_get_orig_node (cs
->callee
));
778 count
= ipa_get_param_count (orig_callee_info
);
779 for (i
= 0; i
< count
; i
++)
781 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (orig_callee_info
, i
);
782 if (ipcp_lat_is_const (lat
))
784 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
785 if (!ipcp_lat_is_const (lat
))
793 /* Fix the callsites and the call graph after function cloning was done. */
795 ipcp_update_callgraph (void)
797 struct cgraph_node
*node
, *orig_callee
;
798 struct cgraph_edge
*cs
;
800 for (node
= cgraph_nodes
; node
; node
= node
->next
)
802 /* want to fix only original nodes */
803 if (!node
->analyzed
|| ipcp_node_is_clone (node
))
805 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
806 if (ipcp_node_is_clone (cs
->callee
))
808 /* Callee is a cloned node */
809 orig_callee
= ipcp_get_orig_node (cs
->callee
);
810 if (ipcp_need_redirect_p (cs
))
812 cgraph_redirect_edge_callee (cs
, orig_callee
);
813 TREE_OPERAND (CALL_EXPR_FN (get_call_expr_in (cs
->call_stmt
)),
821 /* Update all cfg basic blocks in NODE according to SCALE. */
823 ipcp_update_bb_counts (struct cgraph_node
*node
, gcov_type scale
)
827 FOR_ALL_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
828 bb
->count
= bb
->count
* scale
/ REG_BR_PROB_BASE
;
831 /* Update all cfg edges in NODE according to SCALE. */
833 ipcp_update_edges_counts (struct cgraph_node
*node
, gcov_type scale
)
839 FOR_ALL_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
840 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
841 e
->count
= e
->count
* scale
/ REG_BR_PROB_BASE
;
844 /* Update profiling info for versioned functions and the functions they were
847 ipcp_update_profiling (void)
849 struct cgraph_node
*node
, *orig_node
;
850 gcov_type scale
, scale_complement
;
851 struct cgraph_edge
*cs
;
853 for (node
= cgraph_nodes
; node
; node
= node
->next
)
855 if (ipcp_node_is_clone (node
))
857 orig_node
= ipcp_get_orig_node (node
);
858 scale
= ipcp_get_node_scale (orig_node
);
859 node
->count
= orig_node
->count
* scale
/ REG_BR_PROB_BASE
;
860 scale_complement
= REG_BR_PROB_BASE
- scale
;
862 orig_node
->count
* scale_complement
/ REG_BR_PROB_BASE
;
863 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
864 cs
->count
= cs
->count
* scale
/ REG_BR_PROB_BASE
;
865 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
866 cs
->count
= cs
->count
* scale_complement
/ REG_BR_PROB_BASE
;
867 ipcp_update_bb_counts (node
, scale
);
868 ipcp_update_bb_counts (orig_node
, scale_complement
);
869 ipcp_update_edges_counts (node
, scale
);
870 ipcp_update_edges_counts (orig_node
, scale_complement
);
875 /* Propagate the constant parameters found by ipcp_iterate_stage()
876 to the function's code. */
878 ipcp_insert_stage (void)
880 struct cgraph_node
*node
, *node1
= NULL
;
882 VEC (cgraph_edge_p
, heap
) * redirect_callers
;
883 varray_type replace_trees
;
884 struct cgraph_edge
*cs
;
885 int node_callers
, count
;
887 struct ipa_replace_map
*replace_param
;
889 ipa_check_create_node_params ();
890 ipa_check_create_edge_args ();
892 for (node
= cgraph_nodes
; node
; node
= node
->next
)
894 struct ipa_node_params
*info
;
895 /* Propagation of the constant is forbidden in certain conditions. */
896 if (!node
->analyzed
|| ipcp_node_not_modifiable_p (node
))
898 info
= IPA_NODE_REF (node
);
899 if (ipa_is_called_with_var_arguments (info
))
902 count
= ipa_get_param_count (info
);
903 for (i
= 0; i
< count
; i
++)
905 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
906 if (ipcp_lat_is_insertable (lat
))
909 if (const_param
== 0)
911 VARRAY_GENERIC_PTR_INIT (replace_trees
, const_param
, "replace_trees");
912 for (i
= 0; i
< count
; i
++)
914 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
915 if (lat
->type
== IPA_CONST_VALUE
916 && !POINTER_TYPE_P (TREE_TYPE (lat
->constant
)))
918 parm_tree
= ipa_get_ith_param (info
, i
);
920 ipcp_create_replace_map (DECL_STRUCT_FUNCTION (node
->decl
),
922 VARRAY_PUSH_GENERIC_PTR (replace_trees
, replace_param
);
925 /* Compute how many callers node has. */
927 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
929 redirect_callers
= VEC_alloc (cgraph_edge_p
, heap
, node_callers
);
930 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
931 VEC_quick_push (cgraph_edge_p
, redirect_callers
, cs
);
932 /* Redirecting all the callers of the node to the
933 new versioned node. */
935 cgraph_function_versioning (node
, redirect_callers
, replace_trees
);
936 VEC_free (cgraph_edge_p
, heap
, redirect_callers
);
937 VARRAY_CLEAR (replace_trees
);
941 fprintf (dump_file
, "versioned function %s\n",
942 cgraph_node_name (node
));
943 ipcp_init_cloned_node (node
, node1
);
946 push_cfun (DECL_STRUCT_FUNCTION (node1
->decl
));
947 tree_register_cfg_hooks ();
948 current_function_decl
= node1
->decl
;
950 for (i
= 0; i
< count
; i
++)
952 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
953 if (ipcp_lat_is_insertable (lat
))
955 parm_tree
= ipa_get_ith_param (info
, i
);
956 if (lat
->type
!= IPA_CONST_VALUE_REF
957 && !is_gimple_reg (parm_tree
))
958 ipcp_propagate_one_const (node1
, i
, lat
);
961 if (gimple_in_ssa_p (cfun
))
963 update_ssa (TODO_update_ssa
);
964 #ifdef ENABLE_CHECKING
968 free_dominance_info (CDI_DOMINATORS
);
969 free_dominance_info (CDI_POST_DOMINATORS
);
971 current_function_decl
= NULL
;
974 dump_function_to_file (node1
->decl
, dump_file
, dump_flags
);
976 ipcp_update_callgraph ();
977 ipcp_update_profiling ();
980 /* The IPCP driver. */
985 fprintf (dump_file
, "\nIPA constant propagation start:\n");
986 ipa_check_create_node_params ();
987 ipa_check_create_edge_args ();
988 ipa_register_cgraph_hooks ();
989 /* 1. Call the init stage to initialize
990 the ipa_node_params and ipa_edge_args structures. */
994 fprintf (dump_file
, "\nIPA structures before propagation:\n");
995 ipcp_print_all_structures (dump_file
);
997 /* 2. Do the interprocedural propagation. */
998 ipcp_iterate_stage ();
1001 fprintf (dump_file
, "\nIPA structures after propagation:\n");
1002 ipcp_print_all_structures (dump_file
);
1003 fprintf (dump_file
, "\nProfiling info before insert stage:\n");
1004 ipcp_print_profile_data (dump_file
);
1006 /* 3. Insert the constants found to the functions. */
1007 ipcp_insert_stage ();
1010 fprintf (dump_file
, "\nProfiling info after insert stage:\n");
1011 ipcp_print_profile_data (dump_file
);
1013 /* Free all IPCP structures. */
1014 free_all_ipa_structures_after_ipa_cp ();
1016 fprintf (dump_file
, "\nIPA constant propagation end\n");
1017 cgraph_remove_unreachable_nodes (true, NULL
);
1021 /* Gate for IPCP optimization. */
1023 cgraph_gate_cp (void)
1028 struct simple_ipa_opt_pass pass_ipa_cp
=
1033 cgraph_gate_cp
, /* gate */
1034 ipcp_driver
, /* execute */
1037 0, /* static_pass_number */
1038 TV_IPA_CONSTANT_PROP
, /* tv_id */
1039 0, /* properties_required */
1040 PROP_trees
, /* properties_provided */
1041 0, /* properties_destroyed */
1042 0, /* todo_flags_start */
1043 TODO_dump_cgraph
| TODO_dump_func
/* todo_flags_finish */