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 /* build INTEGER_CST tree with type TREE_TYPE and value according to LAT.
375 build_const_val (struct ipcp_lattice
*lat
, tree tree_type
)
379 gcc_assert (ipcp_lat_is_const (lat
));
382 if (!useless_type_conversion_p (tree_type
, TREE_TYPE (val
)))
384 if (fold_convertible_p (tree_type
, val
))
385 return fold_build1 (NOP_EXPR
, tree_type
, val
);
387 return fold_build1 (VIEW_CONVERT_EXPR
, tree_type
, val
);
392 /* Compute the proper scale for NODE. It is the ratio between the number of
393 direct calls (represented on the incoming cgraph_edges) and sum of all
394 invocations of NODE (represented as count in cgraph_node). */
396 ipcp_compute_node_scale (struct cgraph_node
*node
)
399 struct cgraph_edge
*cs
;
402 /* Compute sum of all counts of callers. */
403 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
405 if (node
->count
== 0)
406 ipcp_set_node_scale (node
, 0);
408 ipcp_set_node_scale (node
, sum
* REG_BR_PROB_BASE
/ node
->count
);
411 /* Initialization and computation of IPCP data structures. This is the initial
412 intraprocedural analysis of functions, which gathers information to be
413 propagated later on. */
415 ipcp_init_stage (void)
417 struct cgraph_node
*node
;
418 struct cgraph_edge
*cs
;
420 for (node
= cgraph_nodes
; node
; node
= node
->next
)
424 /* Unreachable nodes should have been eliminated before ipcp. */
425 gcc_assert (node
->needed
|| node
->reachable
);
427 ipa_count_formal_params (node
);
428 ipa_create_param_decls_array (node
);
429 ipcp_initialize_node_lattices (node
);
430 ipa_detect_param_modifications (node
);
431 ipcp_compute_node_scale (node
);
433 for (node
= cgraph_nodes
; node
; node
= node
->next
)
437 /* building jump functions */
438 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
440 if (!cs
->callee
->analyzed
)
442 ipa_count_arguments (cs
);
443 if (ipa_get_cs_argument_count (IPA_EDGE_REF (cs
))
444 != ipa_get_param_count (IPA_NODE_REF (cs
->callee
)))
446 /* Handle cases of functions with
447 a variable number of parameters. */
448 ipa_set_called_with_variable_arg (IPA_NODE_REF (cs
->callee
));
449 if (flag_indirect_inlining
)
450 ipa_compute_jump_functions (cs
);
453 ipa_compute_jump_functions (cs
);
458 /* Return true if there are some formal parameters whose value is IPA_TOP (in
459 the whole compilation unit). Change their values to IPA_BOTTOM, since they
460 most probably get their values from outside of this compilation unit. */
462 ipcp_change_tops_to_bottom (void)
465 struct cgraph_node
*node
;
469 for (node
= cgraph_nodes
; node
; node
= node
->next
)
471 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
472 count
= ipa_get_param_count (info
);
473 for (i
= 0; i
< count
; i
++)
475 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
476 if (lat
->type
== IPA_TOP
)
479 lat
->type
= IPA_BOTTOM
;
486 /* Interprocedural analysis. The algorithm propagates constants from the
487 caller's parameters to the callee's arguments. */
489 ipcp_propagate_stage (void)
492 struct ipcp_lattice inc_lat
= { IPA_BOTTOM
, NULL
};
493 struct ipcp_lattice new_lat
= { IPA_BOTTOM
, NULL
};
494 struct ipcp_lattice
*dest_lat
;
495 struct cgraph_edge
*cs
;
496 struct ipa_jump_func
*jump_func
;
497 struct ipa_func_list
*wl
;
500 ipa_check_create_node_params ();
501 ipa_check_create_edge_args ();
502 /* Initialize worklist to contain all functions. */
503 wl
= ipa_init_func_list ();
506 struct cgraph_node
*node
= ipa_pop_func_from_list (&wl
);
507 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
509 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
511 struct ipa_node_params
*callee_info
= IPA_NODE_REF (cs
->callee
);
512 struct ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
514 if (ipa_is_called_with_var_arguments (callee_info
))
517 count
= ipa_get_cs_argument_count (args
);
518 for (i
= 0; i
< count
; i
++)
520 jump_func
= ipa_get_ith_jump_func (args
, i
);
521 ipcp_lattice_from_jfunc (info
, &inc_lat
, jump_func
);
522 dest_lat
= ipcp_get_ith_lattice (callee_info
, i
);
523 ipa_lattice_meet (&new_lat
, &inc_lat
, dest_lat
);
524 if (ipcp_lattice_changed (&new_lat
, dest_lat
))
526 dest_lat
->type
= new_lat
.type
;
527 dest_lat
->constant
= new_lat
.constant
;
528 ipa_push_func_to_list (&wl
, cs
->callee
);
535 /* Call the constant propagation algorithm and re-call it if necessary
536 (if there are undetermined values left). */
538 ipcp_iterate_stage (void)
540 ipcp_propagate_stage ();
541 if (ipcp_change_tops_to_bottom ())
542 /* Some lattices have changed from IPA_TOP to IPA_BOTTOM.
543 This change should be propagated. */
544 ipcp_propagate_stage ();
547 /* Check conditions to forbid constant insertion to function described by
550 ipcp_node_not_modifiable_p (struct cgraph_node
*node
)
552 /* ??? Handle pending sizes case. */
553 if (DECL_UNINLINABLE (node
->decl
))
558 /* Print count scale data structures. */
560 ipcp_function_scale_print (FILE * f
)
562 struct cgraph_node
*node
;
564 for (node
= cgraph_nodes
; node
; node
= node
->next
)
568 fprintf (f
, "printing scale for %s: ", cgraph_node_name (node
));
569 fprintf (f
, "value is " HOST_WIDE_INT_PRINT_DEC
570 " \n", (HOST_WIDE_INT
) ipcp_get_node_scale (node
));
574 /* Print counts of all cgraph nodes. */
576 ipcp_print_func_profile_counts (FILE * f
)
578 struct cgraph_node
*node
;
580 for (node
= cgraph_nodes
; node
; node
= node
->next
)
582 fprintf (f
, "function %s: ", cgraph_node_name (node
));
583 fprintf (f
, "count is " HOST_WIDE_INT_PRINT_DEC
584 " \n", (HOST_WIDE_INT
) node
->count
);
588 /* Print counts of all cgraph edges. */
590 ipcp_print_call_profile_counts (FILE * f
)
592 struct cgraph_node
*node
;
593 struct cgraph_edge
*cs
;
595 for (node
= cgraph_nodes
; node
; node
= node
->next
)
597 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
599 fprintf (f
, "%s -> %s ", cgraph_node_name (cs
->caller
),
600 cgraph_node_name (cs
->callee
));
601 fprintf (f
, "count is " HOST_WIDE_INT_PRINT_DEC
" \n",
602 (HOST_WIDE_INT
) cs
->count
);
607 /* Print all counts and probabilities of cfg edges of all functions. */
609 ipcp_print_edge_profiles (FILE * f
)
611 struct cgraph_node
*node
;
616 for (node
= cgraph_nodes
; node
; node
= node
->next
)
618 fprintf (f
, "function %s: \n", cgraph_node_name (node
));
622 ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node
->decl
));
623 fprintf (f
, "ENTRY: ");
624 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
625 " %d\n", (HOST_WIDE_INT
) bb
->count
, bb
->frequency
);
628 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
631 EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
633 fprintf (f
, "edge ENTRY -> EXIT, Count");
635 fprintf (f
, "edge ENTRY -> %d, Count", e
->dest
->index
);
636 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
637 " Prob %d\n", (HOST_WIDE_INT
) e
->count
,
640 FOR_EACH_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
642 fprintf (f
, "bb[%d]: ", bb
->index
);
643 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
644 " %d\n", (HOST_WIDE_INT
) bb
->count
, bb
->frequency
);
645 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
648 EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
650 fprintf (f
, "edge %d -> EXIT, Count", e
->src
->index
);
652 fprintf (f
, "edge %d -> %d, Count", e
->src
->index
,
654 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
" Prob %d\n",
655 (HOST_WIDE_INT
) e
->count
, e
->probability
);
662 /* Print counts and frequencies for all basic blocks of all functions. */
664 ipcp_print_bb_profiles (FILE * f
)
667 struct cgraph_node
*node
;
669 for (node
= cgraph_nodes
; node
; node
= node
->next
)
671 fprintf (f
, "function %s: \n", cgraph_node_name (node
));
675 ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node
->decl
));
676 fprintf (f
, "ENTRY: Count");
677 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
678 " Frequency %d\n", (HOST_WIDE_INT
) bb
->count
,
681 FOR_EACH_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
683 fprintf (f
, "bb[%d]: Count", bb
->index
);
684 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
685 " Frequency %d\n", (HOST_WIDE_INT
) bb
->count
,
689 EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node
->decl
));
690 fprintf (f
, "EXIT: Count");
691 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
692 " Frequency %d\n", (HOST_WIDE_INT
) bb
->count
,
699 /* Print all IPCP data structures to F. */
701 ipcp_print_all_structures (FILE * f
)
703 ipcp_print_all_lattices (f
);
704 ipcp_function_scale_print (f
);
705 ipa_print_all_tree_maps (f
);
706 ipa_print_all_param_flags (f
);
707 ipa_print_all_jump_functions (f
);
710 /* Print profile info for all functions. */
712 ipcp_print_profile_data (FILE * f
)
714 fprintf (f
, "\nNODE COUNTS :\n");
715 ipcp_print_func_profile_counts (f
);
716 fprintf (f
, "\nCS COUNTS stage:\n");
717 ipcp_print_call_profile_counts (f
);
718 fprintf (f
, "\nBB COUNTS and FREQUENCIES :\n");
719 ipcp_print_bb_profiles (f
);
720 fprintf (f
, "\nCFG EDGES COUNTS and PROBABILITIES :\n");
721 ipcp_print_edge_profiles (f
);
724 /* Build and initialize ipa_replace_map struct according to LAT. This struct is
725 processed by versioning, which operates according to the flags set.
726 PARM_TREE is the formal parameter found to be constant. LAT represents the
728 static struct ipa_replace_map
*
729 ipcp_create_replace_map (tree parm_tree
, struct ipcp_lattice
*lat
)
731 struct ipa_replace_map
*replace_map
;
734 replace_map
= XCNEW (struct ipa_replace_map
);
736 fprintf (dump_file
, "replacing param with const\n");
737 const_val
= build_const_val (lat
, TREE_TYPE (parm_tree
));
738 replace_map
->old_tree
= parm_tree
;
739 replace_map
->new_tree
= const_val
;
740 replace_map
->replace_p
= true;
741 replace_map
->ref_p
= false;
746 /* Return true if this callsite should be redirected to the original callee
747 (instead of the cloned one). */
749 ipcp_need_redirect_p (struct cgraph_edge
*cs
)
751 struct ipa_node_params
*orig_callee_info
;
753 struct ipa_jump_func
*jump_func
;
755 orig_callee_info
= IPA_NODE_REF (ipcp_get_orig_node (cs
->callee
));
756 count
= ipa_get_param_count (orig_callee_info
);
757 for (i
= 0; i
< count
; i
++)
759 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (orig_callee_info
, i
);
760 if (ipcp_lat_is_const (lat
))
762 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
763 if (jump_func
->type
!= IPA_CONST
)
771 /* Fix the callsites and the call graph after function cloning was done. */
773 ipcp_update_callgraph (void)
775 struct cgraph_node
*node
, *orig_callee
;
776 struct cgraph_edge
*cs
;
778 for (node
= cgraph_nodes
; node
; node
= node
->next
)
780 /* want to fix only original nodes */
781 if (!node
->analyzed
|| ipcp_node_is_clone (node
))
783 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
784 if (ipcp_node_is_clone (cs
->callee
))
786 /* Callee is a cloned node */
787 orig_callee
= ipcp_get_orig_node (cs
->callee
);
788 if (ipcp_need_redirect_p (cs
))
790 cgraph_redirect_edge_callee (cs
, orig_callee
);
791 gimple_call_set_fndecl (cs
->call_stmt
, orig_callee
->decl
);
797 /* Update all cfg basic blocks in NODE according to SCALE. */
799 ipcp_update_bb_counts (struct cgraph_node
*node
, gcov_type scale
)
803 FOR_ALL_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
804 bb
->count
= bb
->count
* scale
/ REG_BR_PROB_BASE
;
807 /* Update all cfg edges in NODE according to SCALE. */
809 ipcp_update_edges_counts (struct cgraph_node
*node
, gcov_type scale
)
815 FOR_ALL_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
816 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
817 e
->count
= e
->count
* scale
/ REG_BR_PROB_BASE
;
820 /* Update profiling info for versioned functions and the functions they were
823 ipcp_update_profiling (void)
825 struct cgraph_node
*node
, *orig_node
;
826 gcov_type scale
, scale_complement
;
827 struct cgraph_edge
*cs
;
829 for (node
= cgraph_nodes
; node
; node
= node
->next
)
831 if (ipcp_node_is_clone (node
))
833 orig_node
= ipcp_get_orig_node (node
);
834 scale
= ipcp_get_node_scale (orig_node
);
835 node
->count
= orig_node
->count
* scale
/ REG_BR_PROB_BASE
;
836 scale_complement
= REG_BR_PROB_BASE
- scale
;
838 orig_node
->count
* scale_complement
/ REG_BR_PROB_BASE
;
839 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
840 cs
->count
= cs
->count
* scale
/ REG_BR_PROB_BASE
;
841 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
842 cs
->count
= cs
->count
* scale_complement
/ REG_BR_PROB_BASE
;
843 ipcp_update_bb_counts (node
, scale
);
844 ipcp_update_bb_counts (orig_node
, scale_complement
);
845 ipcp_update_edges_counts (node
, scale
);
846 ipcp_update_edges_counts (orig_node
, scale_complement
);
851 /* Propagate the constant parameters found by ipcp_iterate_stage()
852 to the function's code. */
854 ipcp_insert_stage (void)
856 struct cgraph_node
*node
, *node1
= NULL
;
858 VEC (cgraph_edge_p
, heap
) * redirect_callers
;
859 varray_type replace_trees
;
860 struct cgraph_edge
*cs
;
861 int node_callers
, count
;
863 struct ipa_replace_map
*replace_param
;
865 ipa_check_create_node_params ();
866 ipa_check_create_edge_args ();
868 for (node
= cgraph_nodes
; node
; node
= node
->next
)
870 struct ipa_node_params
*info
;
871 /* Propagation of the constant is forbidden in certain conditions. */
872 if (!node
->analyzed
|| ipcp_node_not_modifiable_p (node
))
874 info
= IPA_NODE_REF (node
);
875 if (ipa_is_called_with_var_arguments (info
))
878 count
= ipa_get_param_count (info
);
879 for (i
= 0; i
< count
; i
++)
881 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
882 tree parm_tree
= ipa_get_ith_param (info
, i
);
883 if (ipcp_lat_is_insertable (lat
)
884 /* Do not count obviously unused arguments. */
885 && (!is_gimple_reg (parm_tree
)
886 || gimple_default_def (DECL_STRUCT_FUNCTION (node
->decl
), parm_tree
)))
889 if (const_param
== 0)
891 VARRAY_GENERIC_PTR_INIT (replace_trees
, const_param
, "replace_trees");
892 for (i
= 0; i
< count
; i
++)
894 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
895 if (lat
->type
== IPA_CONST_VALUE
)
897 parm_tree
= ipa_get_ith_param (info
, i
);
899 ipcp_create_replace_map (parm_tree
, lat
);
900 VARRAY_PUSH_GENERIC_PTR (replace_trees
, replace_param
);
903 /* Compute how many callers node has. */
905 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
907 redirect_callers
= VEC_alloc (cgraph_edge_p
, heap
, node_callers
);
908 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
909 VEC_quick_push (cgraph_edge_p
, redirect_callers
, cs
);
910 /* Redirecting all the callers of the node to the
911 new versioned node. */
913 cgraph_function_versioning (node
, redirect_callers
, replace_trees
);
914 VEC_free (cgraph_edge_p
, heap
, redirect_callers
);
915 VARRAY_CLEAR (replace_trees
);
919 fprintf (dump_file
, "versioned function %s\n",
920 cgraph_node_name (node
));
921 ipcp_init_cloned_node (node
, node1
);
922 /* We've possibly introduced direct calls. */
923 ipcp_update_cloned_node (node1
);
926 dump_function_to_file (node1
->decl
, dump_file
, dump_flags
);
928 ipcp_update_callgraph ();
929 ipcp_update_profiling ();
932 /* The IPCP driver. */
936 /* 2. Do the interprocedural propagation. */
937 ipcp_iterate_stage ();
940 fprintf (dump_file
, "\nIPA structures after propagation:\n");
941 ipcp_print_all_structures (dump_file
);
942 fprintf (dump_file
, "\nProfiling info before insert stage:\n");
943 ipcp_print_profile_data (dump_file
);
945 /* 3. Insert the constants found to the functions. */
946 ipcp_insert_stage ();
949 fprintf (dump_file
, "\nProfiling info after insert stage:\n");
950 ipcp_print_profile_data (dump_file
);
952 /* Free all IPCP structures. */
953 free_all_ipa_structures_after_ipa_cp ();
955 fprintf (dump_file
, "\nIPA constant propagation end\n");
956 cgraph_remove_unreachable_nodes (true, NULL
);
960 /* Note function body size. */
962 ipcp_generate_summary (void)
965 fprintf (dump_file
, "\nIPA constant propagation start:\n");
966 ipa_check_create_node_params ();
967 ipa_check_create_edge_args ();
968 ipa_register_cgraph_hooks ();
969 /* 1. Call the init stage to initialize
970 the ipa_node_params and ipa_edge_args structures. */
974 fprintf (dump_file
, "\nIPA structures before propagation:\n");
975 ipcp_print_all_structures (dump_file
);
979 /* Gate for IPCP optimization. */
981 cgraph_gate_cp (void)
986 struct ipa_opt_pass pass_ipa_cp
=
991 cgraph_gate_cp
, /* gate */
992 ipcp_driver
, /* execute */
995 0, /* static_pass_number */
996 TV_IPA_CONSTANT_PROP
, /* tv_id */
997 0, /* properties_required */
998 PROP_trees
, /* properties_provided */
999 0, /* properties_destroyed */
1000 0, /* todo_flags_start */
1001 TODO_dump_cgraph
| TODO_dump_func
/* todo_flags_finish */
1003 ipcp_generate_summary
, /* generate_summary */
1004 NULL
, /* write_summary */
1005 NULL
, /* read_summary */
1006 NULL
, /* function_read_summary */
1008 NULL
, /* function_transform */
1009 NULL
, /* variable_transform */