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_LAT and NEW_LAT values are not the same. */
287 ipcp_lattice_changed (struct ipcp_lattice
*old_lat
,
288 struct ipcp_lattice
*new_lat
)
290 if (old_lat
->type
== new_lat
->type
)
292 if (!ipcp_lat_is_const (old_lat
))
294 if (ipcp_lats_are_equal (old_lat
, new_lat
))
300 /* Print all ipcp_lattices of all functions to F. */
302 ipcp_print_all_lattices (FILE * f
)
304 struct cgraph_node
*node
;
307 fprintf (f
, "\nLATTICE PRINT\n");
308 for (node
= cgraph_nodes
; node
; node
= node
->next
)
310 struct ipa_node_params
*info
;
314 info
= IPA_NODE_REF (node
);
315 fprintf (f
, "Printing lattices %s:\n", cgraph_node_name (node
));
316 count
= ipa_get_param_count (info
);
317 for (i
= 0; i
< count
; i
++)
319 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
321 fprintf (f
, " param [%d]: ", i
);
322 if (lat
->type
== IPA_CONST_VALUE
|| lat
->type
== IPA_CONST_VALUE_REF
)
324 fprintf (f
, "type is CONST ");
325 print_generic_expr (f
, lat
->constant
, 0);
328 else if (lat
->type
== IPA_TOP
)
329 fprintf (f
, "type is TOP\n");
331 fprintf (f
, "type is BOTTOM\n");
336 /* Initialize ipcp_lattices array. The lattices corresponding to supported
337 types (integers, real types and Fortran constants defined as const_decls)
338 are initialized to IPA_TOP, the rest of them to IPA_BOTTOM. */
340 ipcp_initialize_node_lattices (struct cgraph_node
*node
)
343 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
345 info
->ipcp_lattices
= XCNEWVEC (struct ipcp_lattice
,
346 ipa_get_param_count (info
));
347 for (i
= 0; i
< ipa_get_param_count (info
) ; i
++)
349 tree parm_tree
= ipa_get_ith_param (info
, i
);
350 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
352 if (INTEGRAL_TYPE_P (TREE_TYPE (parm_tree
))
353 || SCALAR_FLOAT_TYPE_P (TREE_TYPE (parm_tree
))
354 || POINTER_TYPE_P (TREE_TYPE (parm_tree
)))
357 lat
->type
= IPA_BOTTOM
;
361 /* Create a new assignment statement and make it the first statement in the
362 function. PARM1 is the lhs of the assignment and VAL is the rhs. */
364 constant_val_insert (tree parm1 ATTRIBUTE_UNUSED
, tree val ATTRIBUTE_UNUSED
)
366 gimple init_stmt
= NULL
;
369 init_stmt
= gimple_build_assign (parm1
, val
);
370 gcc_assert (init_stmt
);
371 e_step
= single_succ_edge (ENTRY_BLOCK_PTR_FOR_FUNCTION (cfun
));
372 gsi_insert_on_edge_immediate (e_step
, init_stmt
);
375 /* build INTEGER_CST tree with type TREE_TYPE and value according to LAT.
378 build_const_val (struct ipcp_lattice
*lat
, tree tree_type
)
380 tree const_val
= NULL
;
382 gcc_assert (ipcp_lat_is_const (lat
));
383 const_val
= fold_convert (tree_type
, lat
->constant
);
387 /* Build the tree representing the constant and call constant_val_insert(). */
389 ipcp_propagate_one_const (struct cgraph_node
*node
, int param
,
390 struct ipcp_lattice
*lat
)
396 fprintf (dump_file
, "propagating const to %s\n", cgraph_node_name (node
));
397 parm_tree
= ipa_get_ith_param (IPA_NODE_REF (node
), param
);
398 const_val
= build_const_val (lat
, TREE_TYPE (parm_tree
));
399 constant_val_insert (parm_tree
, const_val
);
402 /* Compute the proper scale for NODE. It is the ratio between the number of
403 direct calls (represented on the incoming cgraph_edges) and sum of all
404 invocations of NODE (represented as count in cgraph_node). */
406 ipcp_compute_node_scale (struct cgraph_node
*node
)
409 struct cgraph_edge
*cs
;
412 /* Compute sum of all counts of callers. */
413 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
415 if (node
->count
== 0)
416 ipcp_set_node_scale (node
, 0);
418 ipcp_set_node_scale (node
, sum
* REG_BR_PROB_BASE
/ node
->count
);
421 /* Initialization and computation of IPCP data structures. This is the initial
422 intraprocedural analysis of functions, which gathers information to be
423 propagated later on. */
425 ipcp_init_stage (void)
427 struct cgraph_node
*node
;
428 struct cgraph_edge
*cs
;
430 for (node
= cgraph_nodes
; node
; node
= node
->next
)
434 /* Unreachable nodes should have been eliminated before ipcp. */
435 gcc_assert (node
->needed
|| node
->reachable
);
437 ipa_count_formal_params (node
);
438 ipa_create_param_decls_array (node
);
439 ipcp_initialize_node_lattices (node
);
440 ipa_detect_param_modifications (node
);
441 ipcp_compute_node_scale (node
);
443 for (node
= cgraph_nodes
; node
; node
= node
->next
)
447 /* building jump functions */
448 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
450 if (!cs
->callee
->analyzed
)
452 ipa_count_arguments (cs
);
453 if (ipa_get_cs_argument_count (IPA_EDGE_REF (cs
))
454 != ipa_get_param_count (IPA_NODE_REF (cs
->callee
)))
456 /* Handle cases of functions with
457 a variable number of parameters. */
458 ipa_set_called_with_variable_arg (IPA_NODE_REF (cs
->callee
));
461 ipa_compute_jump_functions (cs
);
466 /* Return true if there are some formal parameters whose value is IPA_TOP (in
467 the whole compilation unit). Change their values to IPA_BOTTOM, since they
468 most probably get their values from outside of this compilation unit. */
470 ipcp_change_tops_to_bottom (void)
473 struct cgraph_node
*node
;
477 for (node
= cgraph_nodes
; node
; node
= node
->next
)
479 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
480 count
= ipa_get_param_count (info
);
481 for (i
= 0; i
< count
; i
++)
483 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
484 if (lat
->type
== IPA_TOP
)
487 lat
->type
= IPA_BOTTOM
;
494 /* Interprocedural analysis. The algorithm propagates constants from the
495 caller's parameters to the callee's arguments. */
497 ipcp_propagate_stage (void)
500 struct ipcp_lattice inc_lat
= { IPA_BOTTOM
, NULL
};
501 struct ipcp_lattice new_lat
= { IPA_BOTTOM
, NULL
};
502 struct ipcp_lattice
*dest_lat
;
503 struct cgraph_edge
*cs
;
504 struct ipa_jump_func
*jump_func
;
505 struct ipa_func_list
*wl
;
508 ipa_check_create_node_params ();
509 ipa_check_create_edge_args ();
510 /* Initialize worklist to contain all functions. */
511 wl
= ipa_init_func_list ();
514 struct cgraph_node
*node
= ipa_pop_func_from_list (&wl
);
515 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
517 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
519 struct ipa_node_params
*callee_info
= IPA_NODE_REF (cs
->callee
);
520 struct ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
522 if (ipa_is_called_with_var_arguments (callee_info
))
525 count
= ipa_get_cs_argument_count (args
);
526 for (i
= 0; i
< count
; i
++)
528 jump_func
= ipa_get_ith_jump_func (args
, i
);
529 ipcp_lattice_from_jfunc (info
, &inc_lat
, jump_func
);
530 dest_lat
= ipcp_get_ith_lattice (callee_info
, i
);
531 ipa_lattice_meet (&new_lat
, &inc_lat
, dest_lat
);
532 if (ipcp_lattice_changed (&new_lat
, dest_lat
))
534 dest_lat
->type
= new_lat
.type
;
535 dest_lat
->constant
= new_lat
.constant
;
536 ipa_push_func_to_list (&wl
, cs
->callee
);
543 /* Call the constant propagation algorithm and re-call it if necessary
544 (if there are undetermined values left). */
546 ipcp_iterate_stage (void)
548 ipcp_propagate_stage ();
549 if (ipcp_change_tops_to_bottom ())
550 /* Some lattices have changed from IPA_TOP to IPA_BOTTOM.
551 This change should be propagated. */
552 ipcp_propagate_stage ();
555 /* Check conditions to forbid constant insertion to function described by
558 ipcp_node_not_modifiable_p (struct cgraph_node
*node
)
560 /* ??? Handle pending sizes case. */
561 if (DECL_UNINLINABLE (node
->decl
))
566 /* Print count scale data structures. */
568 ipcp_function_scale_print (FILE * f
)
570 struct cgraph_node
*node
;
572 for (node
= cgraph_nodes
; node
; node
= node
->next
)
576 fprintf (f
, "printing scale for %s: ", cgraph_node_name (node
));
577 fprintf (f
, "value is " HOST_WIDE_INT_PRINT_DEC
578 " \n", (HOST_WIDE_INT
) ipcp_get_node_scale (node
));
582 /* Print counts of all cgraph nodes. */
584 ipcp_print_func_profile_counts (FILE * f
)
586 struct cgraph_node
*node
;
588 for (node
= cgraph_nodes
; node
; node
= node
->next
)
590 fprintf (f
, "function %s: ", cgraph_node_name (node
));
591 fprintf (f
, "count is " HOST_WIDE_INT_PRINT_DEC
592 " \n", (HOST_WIDE_INT
) node
->count
);
596 /* Print counts of all cgraph edges. */
598 ipcp_print_call_profile_counts (FILE * f
)
600 struct cgraph_node
*node
;
601 struct cgraph_edge
*cs
;
603 for (node
= cgraph_nodes
; node
; node
= node
->next
)
605 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
607 fprintf (f
, "%s -> %s ", cgraph_node_name (cs
->caller
),
608 cgraph_node_name (cs
->callee
));
609 fprintf (f
, "count is " HOST_WIDE_INT_PRINT_DEC
" \n",
610 (HOST_WIDE_INT
) cs
->count
);
615 /* Print all counts and probabilities of cfg edges of all functions. */
617 ipcp_print_edge_profiles (FILE * f
)
619 struct cgraph_node
*node
;
624 for (node
= cgraph_nodes
; node
; node
= node
->next
)
626 fprintf (f
, "function %s: \n", cgraph_node_name (node
));
630 ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node
->decl
));
631 fprintf (f
, "ENTRY: ");
632 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
633 " %d\n", (HOST_WIDE_INT
) bb
->count
, bb
->frequency
);
636 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
639 EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
641 fprintf (f
, "edge ENTRY -> EXIT, Count");
643 fprintf (f
, "edge ENTRY -> %d, Count", e
->dest
->index
);
644 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
645 " Prob %d\n", (HOST_WIDE_INT
) e
->count
,
648 FOR_EACH_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
650 fprintf (f
, "bb[%d]: ", bb
->index
);
651 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
652 " %d\n", (HOST_WIDE_INT
) bb
->count
, bb
->frequency
);
653 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
656 EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
658 fprintf (f
, "edge %d -> EXIT, Count", e
->src
->index
);
660 fprintf (f
, "edge %d -> %d, Count", e
->src
->index
,
662 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
" Prob %d\n",
663 (HOST_WIDE_INT
) e
->count
, e
->probability
);
670 /* Print counts and frequencies for all basic blocks of all functions. */
672 ipcp_print_bb_profiles (FILE * f
)
675 struct cgraph_node
*node
;
677 for (node
= cgraph_nodes
; node
; node
= node
->next
)
679 fprintf (f
, "function %s: \n", cgraph_node_name (node
));
683 ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node
->decl
));
684 fprintf (f
, "ENTRY: Count");
685 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
686 " Frequency %d\n", (HOST_WIDE_INT
) bb
->count
,
689 FOR_EACH_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
691 fprintf (f
, "bb[%d]: Count", bb
->index
);
692 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
693 " Frequency %d\n", (HOST_WIDE_INT
) bb
->count
,
697 EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node
->decl
));
698 fprintf (f
, "EXIT: Count");
699 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
700 " Frequency %d\n", (HOST_WIDE_INT
) bb
->count
,
707 /* Print all IPCP data structures to F. */
709 ipcp_print_all_structures (FILE * f
)
711 ipcp_print_all_lattices (f
);
712 ipcp_function_scale_print (f
);
713 ipa_print_all_tree_maps (f
);
714 ipa_print_all_param_flags (f
);
715 ipa_print_all_jump_functions (f
);
718 /* Print profile info for all functions. */
720 ipcp_print_profile_data (FILE * f
)
722 fprintf (f
, "\nNODE COUNTS :\n");
723 ipcp_print_func_profile_counts (f
);
724 fprintf (f
, "\nCS COUNTS stage:\n");
725 ipcp_print_call_profile_counts (f
);
726 fprintf (f
, "\nBB COUNTS and FREQUENCIES :\n");
727 ipcp_print_bb_profiles (f
);
728 fprintf (f
, "\nCFG EDGES COUNTS and PROBABILITIES :\n");
729 ipcp_print_edge_profiles (f
);
732 /* Build and initialize ipa_replace_map struct according to LAT. This struct is
733 processed by versioning, which operates according to the flags set.
734 PARM_TREE is the formal parameter found to be constant. LAT represents the
736 static struct ipa_replace_map
*
737 ipcp_create_replace_map (struct function
*func
, tree parm_tree
,
738 struct ipcp_lattice
*lat
)
740 struct ipa_replace_map
*replace_map
;
743 replace_map
= XCNEW (struct ipa_replace_map
);
744 if (is_gimple_reg (parm_tree
) && gimple_default_def (func
, parm_tree
)
745 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_default_def (func
,
749 fprintf (dump_file
, "replacing param with const\n");
750 const_val
= build_const_val (lat
, TREE_TYPE (parm_tree
));
751 replace_map
->old_tree
=gimple_default_def (func
, parm_tree
);
752 replace_map
->new_tree
= const_val
;
753 replace_map
->replace_p
= true;
754 replace_map
->ref_p
= false;
758 replace_map
->old_tree
= NULL
;
759 replace_map
->new_tree
= NULL
;
760 replace_map
->replace_p
= false;
761 replace_map
->ref_p
= false;
767 /* Return true if this callsite should be redirected to the original callee
768 (instead of the cloned one). */
770 ipcp_need_redirect_p (struct cgraph_edge
*cs
)
772 struct ipa_node_params
*orig_callee_info
;
774 struct ipa_jump_func
*jump_func
;
776 orig_callee_info
= IPA_NODE_REF (ipcp_get_orig_node (cs
->callee
));
777 count
= ipa_get_param_count (orig_callee_info
);
778 for (i
= 0; i
< count
; i
++)
780 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (orig_callee_info
, i
);
781 if (ipcp_lat_is_const (lat
))
783 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
784 if (!ipcp_lat_is_const (lat
))
792 /* Fix the callsites and the call graph after function cloning was done. */
794 ipcp_update_callgraph (void)
796 struct cgraph_node
*node
, *orig_callee
;
797 struct cgraph_edge
*cs
;
799 for (node
= cgraph_nodes
; node
; node
= node
->next
)
801 /* want to fix only original nodes */
802 if (!node
->analyzed
|| ipcp_node_is_clone (node
))
804 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
805 if (ipcp_node_is_clone (cs
->callee
))
807 /* Callee is a cloned node */
808 orig_callee
= ipcp_get_orig_node (cs
->callee
);
809 if (ipcp_need_redirect_p (cs
))
811 cgraph_redirect_edge_callee (cs
, orig_callee
);
812 gimple_call_set_fn (cs
->call_stmt
, orig_callee
->decl
);
818 /* Update all cfg basic blocks in NODE according to SCALE. */
820 ipcp_update_bb_counts (struct cgraph_node
*node
, gcov_type scale
)
824 FOR_ALL_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
825 bb
->count
= bb
->count
* scale
/ REG_BR_PROB_BASE
;
828 /* Update all cfg edges in NODE according to SCALE. */
830 ipcp_update_edges_counts (struct cgraph_node
*node
, gcov_type scale
)
836 FOR_ALL_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
837 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
838 e
->count
= e
->count
* scale
/ REG_BR_PROB_BASE
;
841 /* Update profiling info for versioned functions and the functions they were
844 ipcp_update_profiling (void)
846 struct cgraph_node
*node
, *orig_node
;
847 gcov_type scale
, scale_complement
;
848 struct cgraph_edge
*cs
;
850 for (node
= cgraph_nodes
; node
; node
= node
->next
)
852 if (ipcp_node_is_clone (node
))
854 orig_node
= ipcp_get_orig_node (node
);
855 scale
= ipcp_get_node_scale (orig_node
);
856 node
->count
= orig_node
->count
* scale
/ REG_BR_PROB_BASE
;
857 scale_complement
= REG_BR_PROB_BASE
- scale
;
859 orig_node
->count
* scale_complement
/ REG_BR_PROB_BASE
;
860 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
861 cs
->count
= cs
->count
* scale
/ REG_BR_PROB_BASE
;
862 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
863 cs
->count
= cs
->count
* scale_complement
/ REG_BR_PROB_BASE
;
864 ipcp_update_bb_counts (node
, scale
);
865 ipcp_update_bb_counts (orig_node
, scale_complement
);
866 ipcp_update_edges_counts (node
, scale
);
867 ipcp_update_edges_counts (orig_node
, scale_complement
);
872 /* Propagate the constant parameters found by ipcp_iterate_stage()
873 to the function's code. */
875 ipcp_insert_stage (void)
877 struct cgraph_node
*node
, *node1
= NULL
;
879 VEC (cgraph_edge_p
, heap
) * redirect_callers
;
880 varray_type replace_trees
;
881 struct cgraph_edge
*cs
;
882 int node_callers
, count
;
884 struct ipa_replace_map
*replace_param
;
886 ipa_check_create_node_params ();
887 ipa_check_create_edge_args ();
889 for (node
= cgraph_nodes
; node
; node
= node
->next
)
891 struct ipa_node_params
*info
;
892 /* Propagation of the constant is forbidden in certain conditions. */
893 if (!node
->analyzed
|| ipcp_node_not_modifiable_p (node
))
895 info
= IPA_NODE_REF (node
);
896 if (ipa_is_called_with_var_arguments (info
))
899 count
= ipa_get_param_count (info
);
900 for (i
= 0; i
< count
; i
++)
902 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
903 if (ipcp_lat_is_insertable (lat
))
906 if (const_param
== 0)
908 VARRAY_GENERIC_PTR_INIT (replace_trees
, const_param
, "replace_trees");
909 for (i
= 0; i
< count
; i
++)
911 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
912 if (lat
->type
== IPA_CONST_VALUE
913 && !POINTER_TYPE_P (TREE_TYPE (lat
->constant
)))
915 parm_tree
= ipa_get_ith_param (info
, i
);
917 ipcp_create_replace_map (DECL_STRUCT_FUNCTION (node
->decl
),
919 VARRAY_PUSH_GENERIC_PTR (replace_trees
, replace_param
);
922 /* Compute how many callers node has. */
924 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
926 redirect_callers
= VEC_alloc (cgraph_edge_p
, heap
, node_callers
);
927 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
928 VEC_quick_push (cgraph_edge_p
, redirect_callers
, cs
);
929 /* Redirecting all the callers of the node to the
930 new versioned node. */
932 cgraph_function_versioning (node
, redirect_callers
, replace_trees
);
933 VEC_free (cgraph_edge_p
, heap
, redirect_callers
);
934 VARRAY_CLEAR (replace_trees
);
938 fprintf (dump_file
, "versioned function %s\n",
939 cgraph_node_name (node
));
940 ipcp_init_cloned_node (node
, node1
);
943 push_cfun (DECL_STRUCT_FUNCTION (node1
->decl
));
944 gimple_register_cfg_hooks ();
945 current_function_decl
= node1
->decl
;
947 for (i
= 0; i
< count
; i
++)
949 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
950 if (ipcp_lat_is_insertable (lat
))
952 parm_tree
= ipa_get_ith_param (info
, i
);
953 if (lat
->type
!= IPA_CONST_VALUE_REF
954 && !is_gimple_reg (parm_tree
))
955 ipcp_propagate_one_const (node1
, i
, lat
);
958 if (gimple_in_ssa_p (cfun
))
960 update_ssa (TODO_update_ssa
);
961 #ifdef ENABLE_CHECKING
965 free_dominance_info (CDI_DOMINATORS
);
966 free_dominance_info (CDI_POST_DOMINATORS
);
968 current_function_decl
= NULL
;
971 dump_function_to_file (node1
->decl
, dump_file
, dump_flags
);
973 ipcp_update_callgraph ();
974 ipcp_update_profiling ();
977 /* The IPCP driver. */
982 fprintf (dump_file
, "\nIPA constant propagation start:\n");
983 ipa_check_create_node_params ();
984 ipa_check_create_edge_args ();
985 ipa_register_cgraph_hooks ();
986 /* 1. Call the init stage to initialize
987 the ipa_node_params and ipa_edge_args structures. */
991 fprintf (dump_file
, "\nIPA structures before propagation:\n");
992 ipcp_print_all_structures (dump_file
);
994 /* 2. Do the interprocedural propagation. */
995 ipcp_iterate_stage ();
998 fprintf (dump_file
, "\nIPA structures after propagation:\n");
999 ipcp_print_all_structures (dump_file
);
1000 fprintf (dump_file
, "\nProfiling info before insert stage:\n");
1001 ipcp_print_profile_data (dump_file
);
1003 /* 3. Insert the constants found to the functions. */
1004 ipcp_insert_stage ();
1007 fprintf (dump_file
, "\nProfiling info after insert stage:\n");
1008 ipcp_print_profile_data (dump_file
);
1010 /* Free all IPCP structures. */
1011 free_all_ipa_structures_after_ipa_cp ();
1013 fprintf (dump_file
, "\nIPA constant propagation end\n");
1014 cgraph_remove_unreachable_nodes (true, NULL
);
1018 /* Gate for IPCP optimization. */
1020 cgraph_gate_cp (void)
1025 struct simple_ipa_opt_pass pass_ipa_cp
=
1030 cgraph_gate_cp
, /* gate */
1031 ipcp_driver
, /* execute */
1034 0, /* static_pass_number */
1035 TV_IPA_CONSTANT_PROP
, /* tv_id */
1036 0, /* properties_required */
1037 PROP_trees
, /* properties_provided */
1038 0, /* properties_destroyed */
1039 0, /* todo_flags_start */
1040 TODO_dump_cgraph
| TODO_dump_func
/* todo_flags_finish */